FastPartitioner: new optimized Partitioner replacing DefaultPartitioner. see buildnotes_text.html for a summary of the changes.

8 files changed, 849 insertions, 19 deletions

diff --git a/org.eclipse.jface.text.tests/src/org/eclipse/jface/text/tests/rules/DefaultPartitionerTest.java b/org.eclipse.jface.text.tests/src/org/eclipse/jface/text/tests/rules/DefaultPartitionerTest.java
index 629f5773115..6bc028c548a 100644
--- a/org.eclipse.jface.text.tests/src/org/eclipse/jface/text/tests/rules/DefaultPartitionerTest.java
+++ b/org.eclipse.jface.text.tests/src/org/eclipse/jface/text/tests/rules/DefaultPartitionerTest.java
@@ -16,7 +16,7 @@ import junit.framework.TestCase;
 import org.eclipse.jface.text.Document;
 import org.eclipse.jface.text.IDocument;
 import org.eclipse.jface.text.ITypedRegion;
-import org.eclipse.jface.text.rules.DefaultPartitioner;
+import org.eclipse.jface.text.rules.FastPartitioner;
 import org.eclipse.jface.text.rules.IPartitionTokenScanner;
 import org.eclipse.jface.text.rules.IPredicateRule;
 import org.eclipse.jface.text.rules.IToken;
@@ -34,7 +34,7 @@ public class DefaultPartitionerTest extends TestCase {
 	private static final String DEFAULT= IDocument.DEFAULT_CONTENT_TYPE;
 	
 	private IDocument fDoc;
-	private DefaultPartitioner fPartitioner;
+	private FastPartitioner fPartitioner;
 
 	public void setUp() {
 		fDoc= new Document();
@@ -46,7 +46,7 @@ public class DefaultPartitionerTest extends TestCase {
 
 			}
 		};
-		fPartitioner= new DefaultPartitioner(scanner, new String[] { DEFAULT, COMMENT });
+		fPartitioner= new FastPartitioner(scanner, new String[] { DEFAULT, COMMENT });
 		fDoc.setDocumentPartitioner(fPartitioner);
 		fPartitioner.connect(fDoc);
 	}
diff --git a/org.eclipse.jface.text.tests/src/org/eclipse/jface/text/tests/rules/DefaultPartitionerZeroLengthTest.java b/org.eclipse.jface.text.tests/src/org/eclipse/jface/text/tests/rules/DefaultPartitionerZeroLengthTest.java
index 6a84a3eed79..84fc10cb580 100644
--- a/org.eclipse.jface.text.tests/src/org/eclipse/jface/text/tests/rules/DefaultPartitionerZeroLengthTest.java
+++ b/org.eclipse.jface.text.tests/src/org/eclipse/jface/text/tests/rules/DefaultPartitionerZeroLengthTest.java
@@ -16,7 +16,7 @@ import junit.framework.TestCase;
 import org.eclipse.jface.text.Document;
 import org.eclipse.jface.text.IDocument;
 import org.eclipse.jface.text.ITypedRegion;
-import org.eclipse.jface.text.rules.DefaultPartitioner;
+import org.eclipse.jface.text.rules.FastPartitioner;
 import org.eclipse.jface.text.rules.IPartitionTokenScanner;
 import org.eclipse.jface.text.rules.IPredicateRule;
 import org.eclipse.jface.text.rules.IToken;
@@ -34,7 +34,7 @@ public class DefaultPartitionerZeroLengthTest extends TestCase {
 	private static final String DEFAULT= IDocument.DEFAULT_CONTENT_TYPE;
 	
 	private IDocument fDoc;
-	private DefaultPartitioner fPartitioner;
+	private FastPartitioner fPartitioner;
 
 	public void setUp() {
 		fDoc= new Document();
@@ -46,7 +46,7 @@ public class DefaultPartitionerZeroLengthTest extends TestCase {
 
 			}
 		};
-		fPartitioner= new DefaultPartitioner(scanner, new String[] { DEFAULT, COMMENT });
+		fPartitioner= new FastPartitioner(scanner, new String[] { DEFAULT, COMMENT });
 		fDoc.setDocumentPartitioner(fPartitioner);
 		fPartitioner.connect(fDoc);
 	}
diff --git a/org.eclipse.jface.text/src/org/eclipse/jface/text/rules/DefaultPartitioner.java b/org.eclipse.jface.text/src/org/eclipse/jface/text/rules/DefaultPartitioner.java
index ce187e39952..f3bec9b5d74 100644
--- a/org.eclipse.jface.text/src/org/eclipse/jface/text/rules/DefaultPartitioner.java
+++ b/org.eclipse.jface.text/src/org/eclipse/jface/text/rules/DefaultPartitioner.java
@@ -1,5 +1,5 @@
 /*******************************************************************************
- * Copyright (c) 2000, 2004 IBM Corporation and others.
+ * Copyright (c) 2000, 2004, 2005 IBM Corporation and others.
  * All rights reserved. This program and the accompanying materials 
  * are made available under the terms of the Common Public License v1.0
  * which accompanies this distribution, and is available at
@@ -36,15 +36,16 @@ import org.eclipse.jface.text.TypedRegion;
 
 
 /**
- * A standard implementation of a document partitioner.
- * It uses a partition token scanner to scan the document and to determine
- * the document's partitioning. The tokens returned by the
- * scanner are supposed to return the partition type
- * as their data. The partitioner remembers the document's partitions
- * in the document itself rather than maintaining its own data structure.
- *
+ * A standard implementation of a document partitioner. It uses a partition
+ * token scanner to scan the document and to determine the document's
+ * partitioning. The tokens returned by the scanner are supposed to return the
+ * partition type as their data. The partitioner remembers the document's
+ * partitions in the document itself rather than maintaining its own data
+ * structure.
+ * 
  * @see IPartitionTokenScanner
  * @since 2.0
+ * @deprecated as of 3.1 use {@link org.eclipse.jface.text.rules.FastPartitioner} instead
  */
 public class DefaultPartitioner implements IDocumentPartitioner, IDocumentPartitionerExtension, IDocumentPartitionerExtension2, IDocumentPartitionerExtension3 {
 	
diff --git a/org.eclipse.jface.text/src/org/eclipse/jface/text/rules/FastPartitioner.java b/org.eclipse.jface.text/src/org/eclipse/jface/text/rules/FastPartitioner.java
new file mode 100644
index 00000000000..1db386d924b
--- /dev/null
+++ b/org.eclipse.jface.text/src/org/eclipse/jface/text/rules/FastPartitioner.java
@@ -0,0 +1,819 @@
+/*******************************************************************************
+ * Copyright (c) 2000, 2005 IBM Corporation and others.
+ * All rights reserved. This program and the accompanying materials 
+ * are made available under the terms of the Common Public License v1.0
+ * which accompanies this distribution, and is available at
+ * http://www.eclipse.org/legal/cpl-v10.html
+ * 
+ * Contributors:
+ *     IBM Corporation - initial API and implementation
+ *******************************************************************************/
+package org.eclipse.jface.text.rules;
+
+
+import java.util.ArrayList;
+import java.util.List;
+
+import org.eclipse.core.runtime.Platform;
+
+import org.eclipse.jface.text.Assert;
+import org.eclipse.jface.text.BadLocationException;
+import org.eclipse.jface.text.BadPositionCategoryException;
+import org.eclipse.jface.text.DefaultPositionUpdater;
+import org.eclipse.jface.text.DocumentEvent;
+import org.eclipse.jface.text.DocumentRewriteSession;
+import org.eclipse.jface.text.IDocument;
+import org.eclipse.jface.text.IDocumentPartitioner;
+import org.eclipse.jface.text.IDocumentPartitionerExtension;
+import org.eclipse.jface.text.IDocumentPartitionerExtension2;
+import org.eclipse.jface.text.IDocumentPartitionerExtension3;
+import org.eclipse.jface.text.IRegion;
+import org.eclipse.jface.text.ITypedRegion;
+import org.eclipse.jface.text.Position;
+import org.eclipse.jface.text.Region;
+import org.eclipse.jface.text.TextUtilities;
+import org.eclipse.jface.text.TypedPosition;
+import org.eclipse.jface.text.TypedRegion;
+
+
+
+/**
+ * A standard implementation of a document partitioner. It uses an
+ * {@link IPartitionTokenScanner} to scan the document and to determine the
+ * document's partitioning. The tokens returned by the scanner must return the
+ * partition type as their data. The partitioner remembers the document's
+ * partitions in the document itself rather than maintaining its own data
+ * structure.
+ * <p>
+ * To reduce array creations in {@link IDocument#getPositions(String)}, the
+ * positions get cached. The cache is cleared after updating the positions in
+ * {@link #documentChanged2(DocumentEvent)}. Subclasses need to call
+ * {@link #clearPositionCache()} after modifying the partitioner's positions.
+ * The cached positions may be accessed through {@link #getPositions()}.
+ * </p>
+ * 
+ * @see IPartitionTokenScanner
+ * @since 3.1
+ */
+public class FastPartitioner implements IDocumentPartitioner, IDocumentPartitionerExtension, IDocumentPartitionerExtension2, IDocumentPartitionerExtension3 {
+	
+	/** 
+	 * The position category this partitioner uses to store the document's partitioning information.
+	 */
+	private static final String CONTENT_TYPES_CATEGORY= "__content_types_category"; //$NON-NLS-1$
+	/** The partitioner's scanner */
+	protected final IPartitionTokenScanner fScanner;
+	/** The legal content types of this partitioner */
+	protected final String[] fLegalContentTypes;
+	/** The partitioner's document */
+	protected IDocument fDocument;
+	/** The document length before a document change occurred */
+	protected int fPreviousDocumentLength;
+	/** The position updater used to for the default updating of partitions */
+	protected final DefaultPositionUpdater fPositionUpdater;
+	/** The offset at which the first changed partition starts */
+	protected int fStartOffset;
+	/** The offset at which the last changed partition ends */
+	protected int fEndOffset;
+	/**The offset at which a partition has been deleted */
+	protected int fDeleteOffset;
+	/**
+	 * The position category this partitioner uses to store the document's partitioning information.
+	 */
+	private final String fPositionCategory;
+	/**
+	 * The active document rewrite session.
+	 */
+	private DocumentRewriteSession fActiveRewriteSession;
+	/**
+	 * Flag indicating whether this partitioner has been initialized.
+	 */
+	private boolean fIsInitialized= false;
+	/**
+	 * The cached positions from our document, so we don't create a new array every time
+	 * someone requests partition information.
+	 */
+	private Position[] fCachedPositions= null;
+	/** Debug option for cache consistency checking. */
+	private static final boolean CHECK_CACHE_CONSISTENCY= "true".equalsIgnoreCase(Platform.getDebugOption("org.eclipse.jface.text/debug/FastPartitioner/PositionCache"));  //$NON-NLS-1$//$NON-NLS-2$;
+	
+	/**
+	 * Creates a new partitioner that uses the given scanner and may return 
+	 * partitions of the given legal content types.
+	 *
+	 * @param scanner the scanner this partitioner is supposed to use
+	 * @param legalContentTypes the legal content types of this partitioner
+	 */
+	public FastPartitioner(IPartitionTokenScanner scanner, String[] legalContentTypes) {
+		fScanner= scanner;
+		fLegalContentTypes= TextUtilities.copy(legalContentTypes);
+		fPositionCategory= CONTENT_TYPES_CATEGORY + hashCode();
+		fPositionUpdater= new DefaultPositionUpdater(fPositionCategory);
+	}
+	
+	/*
+	 * @see org.eclipse.jface.text.IDocumentPartitionerExtension2#getManagingPositionCategories()
+	 */
+	public String[] getManagingPositionCategories() {
+		return new String[] { fPositionCategory };
+	}
+	
+	/*
+	 * @see org.eclipse.jface.text.IDocumentPartitioner#connect(org.eclipse.jface.text.IDocument)
+	 */
+	public final void connect(IDocument document) {
+		connect(document, false);
+	}
+	
+	/**
+	 * {@inheritDoc}
+	 * <p>
+	 * May be extended by subclasses.
+	 * </p>
+	 */
+	public void connect(IDocument document, boolean delayInitialization) {
+		Assert.isNotNull(document);
+		Assert.isTrue(!document.containsPositionCategory(fPositionCategory));
+		
+		fDocument= document;
+		fDocument.addPositionCategory(fPositionCategory);
+		
+		fIsInitialized= false;
+		if (!delayInitialization)
+			checkInitialization();
+	}
+	
+	/**
+	 * Calls {@link #initialize()} if the receiver is not yet initialized.
+	 */
+	protected final void checkInitialization() {
+		if (!fIsInitialized)
+			initialize();
+	}
+	
+	/**
+	 * Performs the initial partitioning of the partitioner's document.
+	 * <p>
+	 * May be extended by subclasses.
+	 * </p>
+	 */
+	protected void initialize() {
+		fIsInitialized= true;
+		clearPositionCache();
+		fScanner.setRange(fDocument, 0, fDocument.getLength());
+		
+		try {
+			IToken token= fScanner.nextToken();
+			while (!token.isEOF()) {
+				
+				String contentType= getTokenContentType(token);
+				
+				if (isSupportedContentType(contentType)) {
+					TypedPosition p= new TypedPosition(fScanner.getTokenOffset(), fScanner.getTokenLength(), contentType);
+					fDocument.addPosition(fPositionCategory, p);
+				}
+								
+				token= fScanner.nextToken();
+			}
+		} catch (BadLocationException x) {
+			// cannot happen as offsets come from scanner
+		} catch (BadPositionCategoryException x) {
+			// cannot happen if document has been connected before
+		}
+	}	
+	
+	/**
+	 * {@inheritDoc}
+	 * <p>
+	 * May be extended by subclasses.
+	 * </p>
+	 */
+	public void disconnect() {
+		
+		Assert.isTrue(fDocument.containsPositionCategory(fPositionCategory));
+		
+		try {
+			fDocument.removePositionCategory(fPositionCategory);
+		} catch (BadPositionCategoryException x) {
+			// can not happen because of Assert
+		}
+	}
+	
+	/**
+	 * {@inheritDoc}
+	 * <p>
+	 * May be extended by subclasses.
+	 * </p>
+	 */
+	public void documentAboutToBeChanged(DocumentEvent e) {
+		if (fIsInitialized) {
+			
+			Assert.isTrue(e.getDocument() == fDocument);
+			
+			fPreviousDocumentLength= e.getDocument().getLength();
+			fStartOffset= -1;
+			fEndOffset= -1;
+			fDeleteOffset= -1;
+		}
+	}
+	
+	/*
+	 * @see IDocumentPartitioner#documentChanged(DocumentEvent)
+	 */
+	public final boolean documentChanged(DocumentEvent e) {
+		if (fIsInitialized) {
+			IRegion region= documentChanged2(e);
+			return (region != null);
+		}
+		return false;
+	}
+		
+	/**
+	 * Helper method for tracking the minimal region containing all partition changes.
+	 * If <code>offset</code> is smaller than the remembered offset, <code>offset</code>
+	 * will from now on be remembered. If <code>offset  + length</code> is greater than
+	 * the remembered end offset, it will be remembered from now on.
+	 * 
+	 * @param offset the offset
+	 * @param length the length
+	 */
+	private void rememberRegion(int offset, int length) {
+		// remember start offset
+		if (fStartOffset == -1)
+			fStartOffset= offset;
+		else if (offset < fStartOffset)
+			fStartOffset= offset;
+			
+		// remember end offset
+		int endOffset= offset + length;
+		if (fEndOffset == -1)
+			fEndOffset= endOffset;
+		else if (endOffset > fEndOffset)
+			fEndOffset= endOffset;
+	}
+	
+	/**
+	 * Remembers the given offset as the deletion offset.
+	 * 
+	 * @param offset the offset
+	 */
+	private void rememberDeletedOffset(int offset) {
+		fDeleteOffset= offset;
+	}
+	
+	/**
+	 * Creates the minimal region containing all partition changes using the
+	 * remembered offset, end offset, and deletion offset.
+	 * 
+	 * @return the minimal region containing all the partition changes
+	 */
+	private IRegion createRegion() {
+		if (fDeleteOffset == -1) {
+			if (fStartOffset == -1 || fEndOffset == -1)
+				return null;
+			return new Region(fStartOffset, fEndOffset - fStartOffset); 
+		} else if (fStartOffset == -1 || fEndOffset == -1) {
+			return new Region(fDeleteOffset, 0);
+		} else {
+			int offset= Math.min(fDeleteOffset, fStartOffset);
+			int endOffset= Math.max(fDeleteOffset, fEndOffset);
+			return new Region(offset, endOffset - offset);
+		}
+	}
+
+	/**
+	 * {@inheritDoc}
+	 * <p>
+	 * May be extended by subclasses.
+	 * </p>
+	 */
+	public IRegion documentChanged2(DocumentEvent e) {
+		
+		if (!fIsInitialized)
+			return null;
+		
+		try {
+			Assert.isTrue(e.getDocument() == fDocument);
+			
+			Position[] category= getPositions();
+			IRegion line= fDocument.getLineInformationOfOffset(e.getOffset());
+			int reparseStart= line.getOffset();
+			int partitionStart= -1;
+			String contentType= null;
+			int newLength= e.getText() == null ? 0 : e.getText().length();
+			
+			int first= fDocument.computeIndexInCategory(fPositionCategory, reparseStart);
+			if (first > 0)	{
+				TypedPosition partition= (TypedPosition) category[first - 1];
+				if (partition.includes(reparseStart)) {
+					partitionStart= partition.getOffset();
+					contentType= partition.getType();
+					if (e.getOffset() == partition.getOffset() + partition.getLength())
+						reparseStart= partitionStart;
+					-- first;
+				} else if (reparseStart == e.getOffset() && reparseStart == partition.getOffset() + partition.getLength()) {
+					partitionStart= partition.getOffset();
+					contentType= partition.getType();
+					reparseStart= partitionStart;
+					-- first;
+				} else {
+					partitionStart= partition.getOffset() + partition.getLength();
+					contentType= IDocument.DEFAULT_CONTENT_TYPE;
+				}
+			}
+								
+			fPositionUpdater.update(e);
+			for (int i= first; i < category.length; i++) {
+				Position p= category[i];
+				if (p.isDeleted) {
+					rememberDeletedOffset(e.getOffset());
+					break;
+				}
+			}
+			clearPositionCache();
+			category= getPositions();
+
+			fScanner.setPartialRange(fDocument, reparseStart, fDocument.getLength() - reparseStart, contentType, partitionStart);
+			
+			int lastScannedPosition= reparseStart;
+			IToken token= fScanner.nextToken();
+			
+			while (!token.isEOF()) {
+				
+				contentType= getTokenContentType(token);
+				
+				if (!isSupportedContentType(contentType)) {
+					token= fScanner.nextToken();
+					continue;
+				}
+				
+				int start= fScanner.getTokenOffset();
+				int length= fScanner.getTokenLength();
+				
+				lastScannedPosition= start + length - 1; 
+				
+				// remove all affected positions
+				while (first < category.length) {
+					TypedPosition p= (TypedPosition) category[first];
+					if (lastScannedPosition >= p.offset + p.length || 
+							(p.overlapsWith(start, length) && 
+							 	(!fDocument.containsPosition(fPositionCategory, start, length) || 
+							 	 !contentType.equals(p.getType())))) {
+								
+						rememberRegion(p.offset, p.length);
+						fDocument.removePosition(fPositionCategory, p);
+						++ first;
+						
+					} else
+						break;
+				}
+				
+				// if position already exists and we have scanned at least the
+				// area covered by the event, we are done
+				if (fDocument.containsPosition(fPositionCategory, start, length)) {
+					if (lastScannedPosition >= e.getOffset() + newLength)
+						return createRegion();
+					++ first;
+				} else {
+					// insert the new type position
+					try {
+						fDocument.addPosition(fPositionCategory, new TypedPosition(start, length, contentType));
+						rememberRegion(start, length);
+					} catch (BadPositionCategoryException x) {
+					} catch (BadLocationException x) {
+					}
+				}
+				
+				token= fScanner.nextToken();
+			}
+			
+			
+			// remove all positions behind lastScannedPosition since there aren't any further types
+			if (lastScannedPosition != reparseStart) {
+				// if this condition is not met, nothing has been scanned because of a deletion
+				++ lastScannedPosition;
+			}
+			first= fDocument.computeIndexInCategory(fPositionCategory, lastScannedPosition);
+			
+			TypedPosition p;
+			while (first < category.length) {
+				p= (TypedPosition) category[first++];
+				fDocument.removePosition(fPositionCategory, p);
+				rememberRegion(p.offset, p.length);
+			}
+			
+		} catch (BadPositionCategoryException x) {
+			// should never happen on connected documents
+		} catch (BadLocationException x) {
+		} finally {
+			clearPositionCache();
+		}
+
+		return createRegion();
+	}
+
+	/**
+	 * Returns the position in the partitoner's position category which is
+	 * close to the given offset. This is, the position has either an offset which
+	 * is the same as the given offset or an offset which is smaller than the given
+	 * offset. This method profits from the knowledge that a partitioning is
+	 * a ordered set of disjoint position.
+	 * <p>
+	 * May be extended or replaced by subclasses.
+	 * </p>
+	 * @param offset the offset for which to search the closest position
+	 * @return the closest position in the partitioner's category
+	 */ 
+	protected TypedPosition findClosestPosition(int offset) {
+		
+		try {
+			
+			int index= fDocument.computeIndexInCategory(fPositionCategory, offset);
+			Position[] category= getPositions();
+			
+			if (category.length == 0)
+				return null;
+				
+			if (index < category.length) {
+				if (offset == category[index].offset)
+					return (TypedPosition) category[index];
+			}
+			
+			if (index > 0)
+				index--;
+				
+			return (TypedPosition) category[index];
+			
+		} catch (BadPositionCategoryException x) {
+		} catch (BadLocationException x) {
+		}
+		
+		return null;
+	}
+	
+	
+	/**
+	 * {@inheritDoc}
+	 * <p>
+	 * May be replaced or extended by subclasses.
+	 * </p>
+	 */
+	public String getContentType(int offset) {
+		checkInitialization();
+		
+		TypedPosition p= findClosestPosition(offset);
+		if (p != null && p.includes(offset))
+			return p.getType();
+			
+		return IDocument.DEFAULT_CONTENT_TYPE;
+	}
+
+	/**
+	 * {@inheritDoc}
+	 * <p>
+	 * May be replaced or extended by subclasses.
+	 * </p>
+	 */
+	public ITypedRegion getPartition(int offset) {
+		checkInitialization();
+		
+		try {
+		
+			Position[] category = getPositions();
+			
+			if (category == null || category.length == 0)
+				return new TypedRegion(0, fDocument.getLength(), IDocument.DEFAULT_CONTENT_TYPE);
+				
+			int index= fDocument.computeIndexInCategory(fPositionCategory, offset);
+			
+			if (index < category.length) {
+				
+				TypedPosition next= (TypedPosition) category[index];
+				
+				if (offset == next.offset)
+					return new TypedRegion(next.getOffset(), next.getLength(), next.getType());
+				
+				if (index == 0)
+					return new TypedRegion(0, next.offset, IDocument.DEFAULT_CONTENT_TYPE);
+				
+				TypedPosition previous= (TypedPosition) category[index - 1];
+				if (previous.includes(offset))
+					return new TypedRegion(previous.getOffset(), previous.getLength(), previous.getType());
+				
+				int endOffset= previous.getOffset() + previous.getLength();
+				return new TypedRegion(endOffset, next.getOffset() - endOffset, IDocument.DEFAULT_CONTENT_TYPE);	
+			}
+			
+			TypedPosition previous= (TypedPosition) category[category.length - 1];
+			if (previous.includes(offset))
+				return new TypedRegion(previous.getOffset(), previous.getLength(), previous.getType());
+			
+			int endOffset= previous.getOffset() + previous.getLength();
+			return new TypedRegion(endOffset, fDocument.getLength() - endOffset, IDocument.DEFAULT_CONTENT_TYPE);
+			
+		} catch (BadPositionCategoryException x) {
+		} catch (BadLocationException x) {
+		}
+		
+		return new TypedRegion(0, fDocument.getLength(), IDocument.DEFAULT_CONTENT_TYPE);
+	}
+	
+	/*
+	 * @see IDocumentPartitioner#computePartitioning(int, int)
+	 */
+	public final ITypedRegion[] computePartitioning(int offset, int length) {
+		return computePartitioning(offset, length, false);
+	}
+	
+	/**
+	 * {@inheritDoc}
+	 * <p>
+	 * May be replaced or extended by subclasses.
+	 * </p>
+	 */
+	public String[] getLegalContentTypes() {
+		return TextUtilities.copy(fLegalContentTypes);
+	}
+	
+	/**
+	 * Returns whether the given type is one of the legal content types.
+	 * <p>
+	 * May be extended by subclasses.
+	 * </p>
+	 *
+	 * @param contentType the content type to check
+	 * @return <code>true</code> if the content type is a legal content type
+	 */
+	protected boolean isSupportedContentType(String contentType) {
+		if (contentType != null) {
+			for (int i= 0; i < fLegalContentTypes.length; i++) {
+				if (fLegalContentTypes[i].equals(contentType))
+					return true;
+			}
+		}
+		
+		return false;
+	}
+	
+	/**
+	 * Returns a content type encoded in the given token. If the token's
+	 * data is not <code>null</code> and a string it is assumed that
+	 * it is the encoded content type.
+	 * <p>
+	 * May be replaced or extended by subclasses.
+	 * </p>
+	 *
+	 * @param token the token whose content type is to be determined
+	 * @return the token's content type
+	 */
+	protected String getTokenContentType(IToken token) {
+		Object data= token.getData();
+		if (data instanceof String) 
+			return (String) data;
+		return null;
+	}
+
+    /* zero-length partition support */
+    
+	/**
+	 * {@inheritDoc}
+	 * <p>
+	 * May be replaced or extended by subclasses.
+	 * </p>
+	 */
+	public String getContentType(int offset, boolean preferOpenPartitions) {
+		return getPartition(offset, preferOpenPartitions).getType();
+	}
+
+	/**
+	 * {@inheritDoc}
+	 * <p>
+	 * May be replaced or extended by subclasses.
+	 * </p>
+	 */
+	public ITypedRegion getPartition(int offset, boolean preferOpenPartitions) {
+		ITypedRegion region= getPartition(offset);
+		if (preferOpenPartitions) {
+			if (region.getOffset() == offset && !region.getType().equals(IDocument.DEFAULT_CONTENT_TYPE)) {
+				if (offset > 0) {
+					region= getPartition(offset - 1);
+					if (region.getType().equals(IDocument.DEFAULT_CONTENT_TYPE))
+						return region;
+				}
+				return new TypedRegion(offset, 0, IDocument.DEFAULT_CONTENT_TYPE);
+			}
+		}
+        return region;
+	}
+
+	/**
+	 * {@inheritDoc}
+	 * <p>
+	 * May be replaced or extended by subclasses.
+	 * </p>
+	 */
+	public ITypedRegion[] computePartitioning(int offset, int length, boolean includeZeroLengthPartitions) {
+		checkInitialization();
+		List list= new ArrayList();
+		
+		try {
+			
+			int endOffset= offset + length;
+			
+			Position[] category= getPositions();
+			
+			TypedPosition previous= null, current= null;
+			int start, end, gapOffset;
+			Position gap= new Position(0);
+			
+			int startIndex= getFirstIndexEndingAfterOffset(category, offset);
+			int endIndex= getFirstIndexStartingAfterOffset(category, endOffset);
+			for (int i= startIndex; i < endIndex; i++) {
+				
+				current= (TypedPosition) category[i];
+				
+				gapOffset= (previous != null) ? previous.getOffset() + previous.getLength() : 0;
+				gap.setOffset(gapOffset);
+				gap.setLength(current.getOffset() - gapOffset);
+				if ((includeZeroLengthPartitions && overlapsOrTouches(gap, offset, length)) || 
+						(gap.getLength() > 0 && gap.overlapsWith(offset, length))) {
+					start= Math.max(offset, gapOffset);
+					end= Math.min(endOffset, gap.getOffset() + gap.getLength());
+					list.add(new TypedRegion(start, end - start, IDocument.DEFAULT_CONTENT_TYPE));
+				}
+				
+				if (current.overlapsWith(offset, length)) {
+					start= Math.max(offset, current.getOffset());
+					end= Math.min(endOffset, current.getOffset() + current.getLength());
+					list.add(new TypedRegion(start, end - start, current.getType()));
+				}
+				
+				previous= current;
+			}
+			
+			if (previous != null) {
+				gapOffset= previous.getOffset() + previous.getLength();
+				gap.setOffset(gapOffset);
+				gap.setLength(fDocument.getLength() - gapOffset);
+				if ((includeZeroLengthPartitions && overlapsOrTouches(gap, offset, length)) ||
+						(gap.getLength() > 0 && gap.overlapsWith(offset, length))) {
+					start= Math.max(offset, gapOffset);
+					end= Math.min(endOffset, fDocument.getLength());
+					list.add(new TypedRegion(start, end - start, IDocument.DEFAULT_CONTENT_TYPE));
+				}
+			}
+			
+			if (list.isEmpty())
+				list.add(new TypedRegion(offset, length, IDocument.DEFAULT_CONTENT_TYPE));
+				
+		} catch (BadPositionCategoryException x) {
+		}
+		
+		TypedRegion[] result= new TypedRegion[list.size()];
+		list.toArray(result);
+		return result;
+	}
+
+	/**
+	 * Returns <code>true</code> if the given ranges overlap with or touch each other.
+	 * 
+	 * @param gap the first range
+	 * @param offset the offset of the second range
+	 * @param length the length of the second range
+	 * @return <code>true</code> if the given ranges overlap with or touch each other
+	 */
+	private boolean overlapsOrTouches(Position gap, int offset, int length) {
+		return gap.getOffset() <= offset + length && offset <= gap.getOffset() + gap.getLength();
+	}
+	
+	/**
+	 * Returns the index of the first position which ends after the given offset.
+	 *
+	 * @param positions the positions in linear order
+	 * @param offset the offset
+	 * @return the index of the first position which ends after the offset
+	 */
+	private int getFirstIndexEndingAfterOffset(Position[] positions, int offset) {
+		int i= -1, j= positions.length;
+		while (j - i > 1) {
+			int k= (i + j) >> 1;
+			Position p= positions[k];
+			if (p.getOffset() + p.getLength() > offset)
+				j= k;
+			else
+				i= k;
+		}
+		return j;
+	}
+	
+	/**
+	 * Returns the index of the first position which starts at or after the given offset.
+	 *
+	 * @param positions the positions in linear order
+	 * @param offset the offset
+	 * @return the index of the first position which starts after the offset
+	 */
+	private int getFirstIndexStartingAfterOffset(Position[] positions, int offset) {
+		int i= -1, j= positions.length;
+		while (j - i > 1) {
+			int k= (i + j) >> 1;
+			Position p= positions[k];
+			if (p.getOffset() >= offset)
+				j= k;
+			else
+				i= k;
+		}
+		return j;
+	}
+
+	/*
+	 * @see org.eclipse.jface.text.IDocumentPartitionerExtension3#startRewriteSession(org.eclipse.jface.text.DocumentRewriteSession)
+	 */
+	public void startRewriteSession(DocumentRewriteSession session) throws IllegalStateException {
+		if (fActiveRewriteSession != null)
+			throw new IllegalStateException();
+		fActiveRewriteSession= session;		
+	}
+	
+	/**
+	 * {@inheritDoc}
+	 * <p>
+	 * May be extended by subclasses.
+	 * </p>
+	 */
+	public void stopRewriteSession(DocumentRewriteSession session) {
+		if (fActiveRewriteSession == session)
+			flushRewriteSession();
+	}
+	
+	/**
+	 * {@inheritDoc}
+	 * <p>
+	 * May be extended by subclasses.
+	 * </p>
+	 */
+	public DocumentRewriteSession getActiveRewriteSession() {
+		return fActiveRewriteSession;
+	}
+	
+	/**
+	 * Not yet for public use. API under construction.
+	 */
+	protected final void flushRewriteSession() {
+		fActiveRewriteSession= null;
+
+		// remove all position belonging to the partitioner position category
+		try {
+			fDocument.removePositionCategory(fPositionCategory);
+		} catch (BadPositionCategoryException x) {
+		}
+		fDocument.addPositionCategory(fPositionCategory);
+		
+		fIsInitialized= false;
+	}
+	
+	/**
+	 * Clears the position cache. Needs to be called whenever the positions have
+	 * been updated.
+	 */
+	protected final void clearPositionCache() {
+		if (fCachedPositions != null) {
+			fCachedPositions= null;
+		}
+	}
+
+	/**
+	 * Returns the partitioners positions.
+	 * 
+	 * @return the partitioners positions
+	 * @throws BadPositionCategoryException if getting the positions from the
+	 *         document fails
+	 */
+	protected final Position[] getPositions() throws BadPositionCategoryException {
+		if (fCachedPositions == null) {
+			fCachedPositions= fDocument.getPositions(fPositionCategory);
+		} else if (CHECK_CACHE_CONSISTENCY) {
+			Position[] positions= fDocument.getPositions(fPositionCategory);
+			int len= Math.min(positions.length, fCachedPositions.length);
+			for (int i= 0; i < len; i++) {
+				if (!positions[i].equals(fCachedPositions[i]))
+					System.err.println("FastPartitioner.getPositions(): cached position is not up to date: from document: " + toString(positions[i]) + " in cache: " + toString(fCachedPositions[i])); //$NON-NLS-1$ //$NON-NLS-2$
+			}
+			for (int i= len; i < positions.length; i++)
+				System.err.println("FastPartitioner.getPositions(): new position in document: " + toString(positions[i])); //$NON-NLS-1$
+			for (int i= len; i < fCachedPositions.length; i++)
+				System.err.println("FastPartitioner.getPositions(): stale position in cache: " + toString(fCachedPositions[i])); //$NON-NLS-1$
+		}
+		return fCachedPositions;
+	}
+
+	/**
+	 * Pretty print a <code>Position</code>.
+	 * 
+	 * @param position the position to format 
+	 * @return a formatted string
+	 */
+	private String toString(Position position) {
+		return "P[" + position.getOffset() + "+" + position.getLength() + "]"; //$NON-NLS-1$ //$NON-NLS-2$ //$NON-NLS-3$
+	}
+}
diff --git a/org.eclipse.jface.text/src/org/eclipse/jface/text/rules/RuleBasedPartitioner.java b/org.eclipse.jface.text/src/org/eclipse/jface/text/rules/RuleBasedPartitioner.java
index 68b94e59756..ce25bdb78cf 100644
--- a/org.eclipse.jface.text/src/org/eclipse/jface/text/rules/RuleBasedPartitioner.java
+++ b/org.eclipse.jface.text/src/org/eclipse/jface/text/rules/RuleBasedPartitioner.java
@@ -45,7 +45,7 @@ import org.eclipse.jface.text.TypedRegion;
  * @see IRule
  * @see RuleBasedScanner
  * 
- * @deprecated use <code>DefaultPartitioner</code> instead
+ * @deprecated use <code>FastPartitioner</code> instead
  */
 public class RuleBasedPartitioner implements IDocumentPartitioner, IDocumentPartitionerExtension, IDocumentPartitionerExtension2 {
 	
diff --git a/org.eclipse.ui.editors/buildnotes_text.html b/org.eclipse.ui.editors/buildnotes_text.html
index 8476401bdba..1a7fbb0a4f8 100644
--- a/org.eclipse.ui.editors/buildnotes_text.html
+++ b/org.eclipse.ui.editors/buildnotes_text.html
@@ -20,6 +20,16 @@ To see which bugs have been addressed in one of the builds simply open the <a hr
 <br>
 <br>
 <br>
+========== Eclipse Build Input February 1st 2005 ==========<br>
+<pre>
+- added FastPartitioner, replacing DefaultPartitioner which is deprecated.
+  FastPartitioner has the same interface as DefaultPartitioner, but internally
+  caches the partitioning positions set on the document to avoid multiple array
+  creations. Current users of DefaultPartitioner are encouraged to migrate to
+  FastPartitioner; subclasses of DefaultPartitioner that do not modify the positions 
+  will work when subclassing FastPartioner as well, those that do will need to call
+  clearPositionCache() when positions are modified.
+</pre>
 ========== Eclipse Build Input January 25th 2005 ==========<br>
 <pre>
 - added Hippie (emacs style) Completion, contributed by Genady Beryozkin. The action (bound to Alt+/ per default)
diff --git a/org.eclipse.ui.examples.javaeditor/Eclipse Java Editor Example/org/eclipse/ui/examples/javaeditor/JavaDocumentSetupParticipant.java b/org.eclipse.ui.examples.javaeditor/Eclipse Java Editor Example/org/eclipse/ui/examples/javaeditor/JavaDocumentSetupParticipant.java
index 3c468a93402..c0bf267148f 100644
--- a/org.eclipse.ui.examples.javaeditor/Eclipse Java Editor Example/org/eclipse/ui/examples/javaeditor/JavaDocumentSetupParticipant.java
+++ b/org.eclipse.ui.examples.javaeditor/Eclipse Java Editor Example/org/eclipse/ui/examples/javaeditor/JavaDocumentSetupParticipant.java
@@ -15,7 +15,7 @@ import org.eclipse.core.filebuffers.IDocumentSetupParticipant;
 import org.eclipse.jface.text.IDocument;
 import org.eclipse.jface.text.IDocumentExtension3;
 import org.eclipse.jface.text.IDocumentPartitioner;
-import org.eclipse.jface.text.rules.DefaultPartitioner;
+import org.eclipse.jface.text.rules.FastPartitioner;
 
 /**
  * 
@@ -33,7 +33,7 @@ public class JavaDocumentSetupParticipant implements IDocumentSetupParticipant {
 	public void setup(IDocument document) {
 		if (document instanceof IDocumentExtension3) {
 			IDocumentExtension3 extension3= (IDocumentExtension3) document;
-			IDocumentPartitioner partitioner= new DefaultPartitioner(JavaEditorExamplePlugin.getDefault().getJavaPartitionScanner(), JavaPartitionScanner.JAVA_PARTITION_TYPES);
+			IDocumentPartitioner partitioner= new FastPartitioner(JavaEditorExamplePlugin.getDefault().getJavaPartitionScanner(), JavaPartitionScanner.JAVA_PARTITION_TYPES);
 			extension3.setDocumentPartitioner(JavaEditorExamplePlugin.JAVA_PARTITIONING, partitioner);
 			partitioner.connect(document);
 		}
diff --git a/org.eclipse.ui.examples.javaeditor/Template Editor Example/org/eclipse/ui/examples/templateeditor/editors/XMLDocumentProvider.java b/org.eclipse.ui.examples.javaeditor/Template Editor Example/org/eclipse/ui/examples/templateeditor/editors/XMLDocumentProvider.java
index c1da4536b3e..01b6e19b610 100644
--- a/org.eclipse.ui.examples.javaeditor/Template Editor Example/org/eclipse/ui/examples/templateeditor/editors/XMLDocumentProvider.java
+++ b/org.eclipse.ui.examples.javaeditor/Template Editor Example/org/eclipse/ui/examples/templateeditor/editors/XMLDocumentProvider.java
@@ -13,7 +13,7 @@ package org.eclipse.ui.examples.templateeditor.editors;
 import org.eclipse.core.runtime.CoreException;
 import org.eclipse.jface.text.IDocument;
 import org.eclipse.jface.text.IDocumentPartitioner;
-import org.eclipse.jface.text.rules.DefaultPartitioner;
+import org.eclipse.jface.text.rules.FastPartitioner;
 import org.eclipse.ui.editors.text.FileDocumentProvider;
 
 public class XMLDocumentProvider extends FileDocumentProvider {
@@ -22,7 +22,7 @@ public class XMLDocumentProvider extends FileDocumentProvider {
 		IDocument document = super.createDocument(element);
 		if (document != null) {
 			IDocumentPartitioner partitioner =
-				new DefaultPartitioner(
+				new FastPartitioner(
 					new XMLPartitionScanner(),
 					new String[] {
 						XMLPartitionScanner.XML_TAG,