/******************************************************************************* * Copyright (c) 2000, 2003 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 net.sourceforge.phpdt.internal.core.jdom; import java.util.Enumeration; import net.sourceforge.phpdt.core.jdom.DOMException; import net.sourceforge.phpdt.core.jdom.DOMFactory; import net.sourceforge.phpdt.core.jdom.IDOMCompilationUnit; import net.sourceforge.phpdt.core.jdom.IDOMFactory; import net.sourceforge.phpdt.core.jdom.IDOMMethod; import net.sourceforge.phpdt.core.jdom.IDOMNode; import net.sourceforge.phpdt.internal.compiler.util.Util; import net.sourceforge.phpdt.internal.core.util.CharArrayBuffer; /** * DOMNode provides an implementation for IDOMNode. * *

* A node represents a document fragment. When a node is created, its contents * are located in a contiguous range of a shared document. A shared document is * a char array, and is shared in the sense that the contents of other document * fragments may also be contained in the array. * *

* A node maintains indicies of relevant portions of its contents in the shared * document. Thus the original document and indicies create a form from which to * generate the contents of the document fragment. As attributes of a node are * changed, the node attempts to maintain the original formatting by only * replacing relevant portions of the shared document with the value of new * attributes (that is, filling in the form with replacement values). * *

* When a node is first created, it is considered unfragmented. When any * attribute of the node is altered, the node is then considered fragmented from * that point on. A node is also considered fragmented if any of its descendants * are fragmented. When a node is unfragmented, the contents of the node can be * efficiently generated from the original shared document. When a node is * fragmented, the contents of the node must be created using the original * document and indicies as a form, filling in replacement values as required. * *

* Generally, a node's contents consists of complete lines in a shared document. * The contents of the node are normalized on creation to include any whitespace * preceding the node on the line where the node begins, and to include and * trailing whitespace up to the line where the next node begins. Any trailing // * comments that begin on the line where the current node ends, are considered * part of that node. * * @see IDOMNode */ public abstract class DOMNode implements IDOMNode { /** * The first child of this node - null when this node has no * children. (Children of a node are implemented as a doubly linked list). */ protected DOMNode fFirstChild = null; /** * The last child of this node - null when this node has no * children. Used for efficient access to the last child when adding new * children at the end of the linked list of children. */ protected DOMNode fLastChild = null; /** * The sibling node following this node - null for the last * node in the sibling list. */ protected DOMNode fNextNode = null; /** * The parent of this node. A null parent indicates that this * node is a root node of a document fragment. */ protected DOMNode fParent = null; /** * The sibling node preceding this node - null for the first * node in the sibling list. */ protected DOMNode fPreviousNode = null; /** * True when this node has attributes that have been altered from their * original state in the shared document, or when the attributes of a * descendant have been altered. False when the contents of this node and * all descendants are consistent with the content of the shared document. */ protected boolean fIsFragmented = false; /** * The name of this node. For efficiency, the name of a node is duplicated * in this variable on creation, rather than always having to fetch the name * from the shared document. */ protected String fName = null; /** * The original inclusive indicies of this node's name in the shared * document. Values of -1 indiciate the name does not exist in the document. */ protected int[] fNameRange; /** * The shared document that the contents for this node are contained in. * Attribute indicies are positions in this character array. */ protected char[] fDocument = null; /** * The original entire inclusive range of this node's contents within its * document. Values of -1 indicate the contents of this node do not exist in * the document. */ protected int[] fSourceRange; /** * The current state of bit masks defined by this node. Initially all bit * flags are turned off. All bit masks are defined by this class to avoid * overlap, although bit masks are node type specific. * * @see #setMask * @see #getMask */ protected int fStateMask = 0; /** * This position is the position of the end of the last line separator * before the closing brace starting position of the receiver. */ protected int fInsertionPosition; /** * A bit mask indicating this field has an initializer expression */ protected static final int MASK_FIELD_HAS_INITIALIZER = 0x00000001; /** * A bit mask indicating this field is a secondary variable declarator for a * previous field declaration. */ protected static final int MASK_FIELD_IS_VARIABLE_DECLARATOR = 0x00000002; /** * A bit mask indicating this field's type has been altered from its * original contents in the document. */ protected static final int MASK_FIELD_TYPE_ALTERED = 0x00000004; /** * A bit mask indicating this node's name has been altered from its original * contents in the document. */ protected static final int MASK_NAME_ALTERED = 0x00000008; /** * A bit mask indicating this node currently has a body. */ protected static final int MASK_HAS_BODY = 0x00000010; /** * A bit mask indicating this node currently has a preceding comment. */ protected static final int MASK_HAS_COMMENT = 0x00000020; /** * A bit mask indicating this method is a constructor. */ protected static final int MASK_IS_CONSTRUCTOR = 0x00000040; /** * A bit mask indicating this type is a class. */ protected static final int MASK_TYPE_IS_CLASS = 0x00000080; /** * A bit mask indicating this type has a superclass (requires or has an * 'extends' clause). */ protected static final int MASK_TYPE_HAS_SUPERCLASS = 0x00000100; /** * A bit mask indicating this type implements or extends some interfaces */ protected static final int MASK_TYPE_HAS_INTERFACES = 0x00000200; /** * A bit mask indicating this return type of this method has been altered * from the original contents. */ protected static final int MASK_RETURN_TYPE_ALTERED = 0x00000400; /** * A bit mask indicating this node has detailed source indexes */ protected static final int MASK_DETAILED_SOURCE_INDEXES = 0x00000800; /** * Creates a new empty document fragment. */ DOMNode() { fName = null; fDocument = null; fSourceRange = new int[] { -1, -1 }; fNameRange = new int[] { -1, -1 }; fragment(); } /** * Creates a new document fragment on the given range of the document. * * @param document - * the document containing this node's original contents * @param sourceRange - * a two element array of integers describing the entire * inclusive source range of this node within its document. * Contents start on and include the character at the first * position. Contents end on and include the character at the * last position. An array of -1's indicates this node's contents * do not exist in the document. * @param name - * the identifier portion of the name of this node, or * null if this node does not have a name * @param nameRange - * a two element array of integers describing the entire * inclusive source range of this node's name within its * document, including any array qualifiers that might * immediately follow the name or -1's if this node does not have * a name. */ DOMNode(char[] document, int[] sourceRange, String name, int[] nameRange) { super(); fDocument = document; fSourceRange = sourceRange; fName = name; fNameRange = nameRange; } /** * Adds the given un-parented node (document fragment) as the last child of * this node. * *

* When a child is added, this node must be considered fragmented such that * the contents of this node are properly generated. * * @see IDOMNode#addChild(IDOMNode) */ public void addChild(IDOMNode child) throws IllegalArgumentException, DOMException { basicAddChild(child); // if the node is a constructor, it must also be fragmented to update // the constructor's name if (child.getNodeType() == IDOMNode.METHOD && ((IDOMMethod) child).isConstructor()) { ((DOMNode) child).fragment(); } else { fragment(); } } /** * Appends the current contents of this document fragment to the given * CharArrayBuffer. * *

* If this node is fragmented, contents must be generated by using the * original document and indicies as a form for the current attribute values * of this node. If this node not fragmented, the contents can be obtained * from the document. * */ protected void appendContents(CharArrayBuffer buffer) { if (isFragmented()) { appendFragmentedContents(buffer); } else { buffer.append(fDocument, fSourceRange[0], fSourceRange[1] + 1 - fSourceRange[0]); } } /** * Appends the contents of all children of this node to the given * CharArrayBuffer. * *

* This algorithm used minimizes String generation by merging adjacent * unfragmented children into one substring operation. * */ protected void appendContentsOfChildren(CharArrayBuffer buffer) { DOMNode child = fFirstChild; DOMNode sibling; int start = 0, end = 0; if (child != null) { start = child.getStartPosition(); end = child.getEndPosition(); } while (child != null) { sibling = child.fNextNode; if (sibling != null) { if (sibling.isContentMergableWith(child)) { end = sibling.getEndPosition(); } else { if (child.isFragmented()) { child.appendContents(buffer); } else { buffer.append(child.getDocument(), start, end + 1 - start); } start = sibling.getStartPosition(); end = sibling.getEndPosition(); } } else { if (child.isFragmented()) { child.appendContents(buffer); } else { buffer.append(child.getDocument(), start, end + 1 - start); } } child = sibling; } } /** * Appends the contents of this node to the given * CharArrayBufer, using the original document and indicies * as a form for the current attribute values of this node. */ protected abstract void appendFragmentedContents(CharArrayBuffer buffer); /** * Adds the given un-parented node (document fragment) as the last child of * this node without setting this node's 'fragmented' flag. This method is * only used by the DOMBuilder when creating a new DOM such * that a new DOM is unfragmented. */ void basicAddChild(IDOMNode child) throws IllegalArgumentException, DOMException { // verify child may be added if (!canHaveChildren()) { throw new DOMException(Util.bind("dom.unableAddChild")); //$NON-NLS-1$ } if (child == null) { throw new IllegalArgumentException(Util.bind("dom.addNullChild")); //$NON-NLS-1$ } if (!isAllowableChild(child)) { throw new DOMException(Util.bind("dom.addIncompatibleChild")); //$NON-NLS-1$ } if (child.getParent() != null) { throw new DOMException(Util.bind("dom.addChildWithParent")); //$NON-NLS-1$ } /* * NOTE: To test if the child is an ancestor of this node, we need only * test if the root of this node is the child (the child is already a * root since we have just guarenteed it has no parent). */ if (child == getRoot()) { throw new DOMException(Util.bind("dom.addAncestorAsChild")); //$NON-NLS-1$ } DOMNode node = (DOMNode) child; // if the child is not already part of this document, localize its // contents // before adding it to the tree if (node.getDocument() != getDocument()) { node.localizeContents(); } // add the child last if (fFirstChild == null) { // this is the first and only child fFirstChild = node; } else { fLastChild.fNextNode = node; node.fPreviousNode = fLastChild; } fLastChild = node; node.fParent = this; } /** * Generates detailed source indexes for this node if possible. * * @exception DOMException * if unable to generate detailed source indexes for this * node */ protected void becomeDetailed() throws DOMException { if (!isDetailed()) { DOMNode detailed = getDetailedNode(); if (detailed == null) { throw new DOMException(Util.bind("dom.cannotDetail")); //$NON-NLS-1$ } if (detailed != this) { shareContents(detailed); } } } /** * Returns true if this node is allowed to have children, otherwise false. * *

* Default implementation of IDOMNode interface method * returns false; this method must be overridden by subclasses that * implement nodes that allow children. * * @see IDOMNode#canHaveChildren() */ public boolean canHaveChildren() { return false; } /** * @see IDOMNode#clone() */ public Object clone() { // create a new buffer with all my contents and children contents int length = 0; char[] buffer = null; int offset = fSourceRange[0]; if (offset >= 0) { length = fSourceRange[1] - offset + 1; buffer = new char[length]; System.arraycopy(fDocument, offset, buffer, 0, length); } DOMNode clone = newDOMNode(); clone.shareContents(this); clone.fDocument = buffer; if (offset > 0) { clone.offset(0 - offset); } // clone my children if (canHaveChildren()) { Enumeration children = getChildren(); while (children.hasMoreElements()) { DOMNode child = (DOMNode) children.nextElement(); if (child.fDocument == fDocument) { DOMNode childClone = child.cloneSharingDocument(buffer, offset); clone.basicAddChild(childClone); } else { DOMNode childClone = (DOMNode) child.clone(); clone.addChild(childClone); } } } return clone; } private DOMNode cloneSharingDocument(char[] document, int rootOffset) { DOMNode clone = newDOMNode(); clone.shareContents(this); clone.fDocument = document; if (rootOffset > 0) { clone.offset(0 - rootOffset); } if (canHaveChildren()) { Enumeration children = getChildren(); while (children.hasMoreElements()) { DOMNode child = (DOMNode) children.nextElement(); if (child.fDocument == fDocument) { DOMNode childClone = child.cloneSharingDocument(document, rootOffset); clone.basicAddChild(childClone); } else { DOMNode childClone = (DOMNode) child.clone(); clone.addChild(childClone); } } } return clone; } /** * Sets this node's fragmented flag and all ancestor fragmented flags to * true. This happens when an attribute of this node or a descendant * node has been altered. When a node is fragmented, its contents must * be generated from its attributes and original "form" rather than * from the original contents in the document. */ protected void fragment() { if (!isFragmented()) { fIsFragmented = true; if (fParent != null) { fParent.fragment(); } } } /** * @see IDOMNode#getCharacters() */ public char[] getCharacters() { CharArrayBuffer buffer = new CharArrayBuffer(); appendContents(buffer); return buffer.getContents(); } /** * @see IDOMNode#getChild(String) */ public IDOMNode getChild(String name) { DOMNode child = fFirstChild; while (child != null) { String n = child.getName(); if (name == null) { if (n == null) { return child; } } else { if (name.equals(n)) { return child; } } child = child.fNextNode; } return null; } /** * @see IDOMNode#getChildren() */ public Enumeration getChildren() { return new SiblingEnumeration(fFirstChild); } /** * Returns the current contents of this document fragment, or * null if this node has no contents. * *

* If this node is fragmented, contents must be generated by using the * original document and indicies as a form for the current attribute values * of this node. If this node not fragmented, the contents can be obtained * from the document. * * @see IDOMNode#getContents() */ public String getContents() { CharArrayBuffer buffer = new CharArrayBuffer(); appendContents(buffer); return buffer.toString(); } /** * Returns a new document fragment representing this node with detailed * source indexes. Subclasses that provide a detailed implementation must * override this method. */ protected DOMNode getDetailedNode() { return this; } /** * Returns the document containing this node's original contents. The * document may be shared by other nodes. */ protected char[] getDocument() { return fDocument; } /** * Returns the original position of the last character of this node's * contents in its document. */ public int getEndPosition() { return fSourceRange[1]; } /** * Returns a factory with which to create new document fragments. */ protected IDOMFactory getFactory() { return new DOMFactory(); } /** * @see IDOMNode#getFirstChild() */ public IDOMNode getFirstChild() { return fFirstChild; } /** * Returns the position at which the first child of this node should be * inserted. */ public int getInsertionPosition() { return fInsertionPosition; } /** * Returns true if the given mask of this node's state flag * is turned on, otherwise false. */ protected boolean getMask(int mask) { return (fStateMask & mask) > 0; } /** * @see IDOMNode#getName() */ public String getName() { return fName; } /** * Returns the source code to be used for this node's name. */ protected char[] getNameContents() { if (isNameAltered()) { return fName.toCharArray(); } else { if (fName == null || fNameRange[0] < 0) { return null; } else { int length = fNameRange[1] + 1 - fNameRange[0]; char[] result = new char[length]; System.arraycopy(fDocument, fNameRange[0], result, 0, length); return result; } } } /** * @see IDOMNode#getNextNode() */ public IDOMNode getNextNode() { return fNextNode; } /** * @see IDOMNode#getParent() */ public IDOMNode getParent() { return fParent; } /** * Answers a source position which corresponds to the end of the parent * element's declaration. */ protected int getParentEndDeclaration() { IDOMNode parent = getParent(); if (parent == null) { return 0; } else { if (parent instanceof IDOMCompilationUnit) { return 0; } else { return ((DOMType) parent).getOpenBodyEnd(); } } } /** * @see IDOMNode#getPreviousNode() */ public IDOMNode getPreviousNode() { return fPreviousNode; } /** * Returns the root node of this document fragment. */ protected IDOMNode getRoot() { if (fParent == null) { return this; } else { return fParent.getRoot(); } } /** * Returns the original position of the first character of this node's * contents in its document. */ public int getStartPosition() { return fSourceRange[0]; } /** * @see IDOMNode#insertSibling(IDOMNode) */ public void insertSibling(IDOMNode sibling) throws IllegalArgumentException, DOMException { // verify sibling may be added if (sibling == null) { throw new IllegalArgumentException(Util.bind("dom.addNullSibling")); //$NON-NLS-1$ } if (fParent == null) { throw new DOMException(Util.bind("dom.addSiblingBeforeRoot")); //$NON-NLS-1$ } if (!fParent.isAllowableChild(sibling)) { throw new DOMException(Util.bind("dom.addIncompatibleSibling")); //$NON-NLS-1$ } if (sibling.getParent() != null) { throw new DOMException(Util.bind("dom.addSiblingWithParent")); //$NON-NLS-1$ } /* * NOTE: To test if the sibling is an ancestor of this node, we need * only test if the root of this node is the child (the sibling is * already a root since we have just guaranteed it has no parent). */ if (sibling == getRoot()) { throw new DOMException(Util.bind("dom.addAncestorAsSibling")); //$NON-NLS-1$ } DOMNode node = (DOMNode) sibling; // if the sibling is not already part of this document, localize its // contents // before inserting it into the tree if (node.getDocument() != getDocument()) { node.localizeContents(); } // insert the node if (fPreviousNode == null) { fParent.fFirstChild = node; } else { fPreviousNode.fNextNode = node; } node.fParent = fParent; node.fPreviousNode = fPreviousNode; node.fNextNode = this; fPreviousNode = node; // if the node is a constructor, it must also be fragmented to update // the constructor's name if (node.getNodeType() == IDOMNode.METHOD && ((IDOMMethod) node).isConstructor()) { node.fragment(); } else { fParent.fragment(); } } /** * @see IDOMNode */ public boolean isAllowableChild(IDOMNode node) { return false; } /** * Returns true if the contents of this node are from the * same document as the given node, the contents of this node immediately * follow the contents of the given node, and neither this node or the given * node are fragmented - otherwise false. */ protected boolean isContentMergableWith(DOMNode node) { return !node.isFragmented() && !isFragmented() && node.getDocument() == getDocument() && node.getEndPosition() + 1 == getStartPosition(); } /** * Returns true if this node has detailed source index * information, or false if this node has limited source * index information. To perform some manipulations, detailed indexes are * required. */ protected boolean isDetailed() { return getMask(MASK_DETAILED_SOURCE_INDEXES); } /** * Returns true if this node's or a descendant node's * contents have been altered since this node was created. This indicates * that the contents of this node are no longer consistent with the contents * of this node's document. */ protected boolean isFragmented() { return fIsFragmented; } /** * Returns true if this noed's name has been altered from the * original document contents. */ protected boolean isNameAltered() { return getMask(MASK_NAME_ALTERED); } /** * @see IDOMNode#isSignatureEqual(IDOMNode). * *

* By default, the signatures of two nodes are equal if their type and names * are equal. Node types that have other requirements for equality must * override this method. */ public boolean isSignatureEqual(IDOMNode node) { return getNodeType() == node.getNodeType() && getName().equals(node.getName()); } /** * Localizes the contents of this node and all descendant nodes, such that * this node is no longer dependent on its original document in order to * generate its contents. This node and all descendant nodes become * unfragmented and share a new document. */ protected void localizeContents() { DOMNode clone = (DOMNode) clone(); shareContents(clone); } /** * Returns a new empty DOMNode for this instance. */ protected abstract DOMNode newDOMNode(); /** * Normalizes this DOMNode's source positions to include * whitespace preceeding the node on the line on which the node starts, and * all whitespace after the node up to the next node's start */ void normalize(ILineStartFinder finder) { if (getPreviousNode() == null) normalizeStartPosition(getParentEndDeclaration(), finder); // Set the children's position if (canHaveChildren()) { Enumeration children = getChildren(); while (children.hasMoreElements()) ((DOMNode) children.nextElement()).normalize(finder); } normalizeEndPosition(finder, (DOMNode) getNextNode()); } /** * Normalizes this DOMNode's end position. */ void normalizeEndPosition(ILineStartFinder finder, DOMNode next) { if (next == null) { // this node's end position includes all of the characters up // to the end of the enclosing node DOMNode parent = (DOMNode) getParent(); if (parent == null || parent instanceof DOMCompilationUnit) { setSourceRangeEnd(fDocument.length - 1); } else { // parent is a type int temp = ((DOMType) parent).getCloseBodyPosition() - 1; setSourceRangeEnd(temp); fInsertionPosition = Math.max(finder.getLineStart(temp + 1), getEndPosition()); } } else { // this node's end position is just before the start of the next // node int temp = next.getStartPosition() - 1; fInsertionPosition = Math.max(finder.getLineStart(temp + 1), getEndPosition()); next.normalizeStartPosition(getEndPosition(), finder); setSourceRangeEnd(next.getStartPosition() - 1); } } /** * Normalizes this DOMNode's start position. */ void normalizeStartPosition(int previousEnd, ILineStartFinder finder) { int nodeStart = getStartPosition(); int lineStart = finder.getLineStart(nodeStart); if (nodeStart > lineStart && (lineStart > previousEnd || (previousEnd == 0 && lineStart == 0))) setStartPosition(lineStart); } /** * Offsets all the source indexes in this node by the given amount. */ protected void offset(int offset) { offsetRange(fNameRange, offset); offsetRange(fSourceRange, offset); } /** * Offsets the source range by the given amount */ protected void offsetRange(int[] range, int offset) { for (int i = 0; i < range.length; i++) { range[i] += offset; if (range[i] < 0) { range[i] = -1; } } } /** * Returns a copy of the given range. */ protected int[] rangeCopy(int[] range) { int[] copy = new int[range.length]; for (int i = 0; i < range.length; i++) { copy[i] = range[i]; } return copy; } /** * Separates this node from its parent and siblings, maintaining any ties * that this node has to the underlying document fragment. * *

* When a child is removed, its parent is fragmented such that it properly * generates its contents. * * @see IDOMNode#remove() */ public void remove() { if (fParent != null) { fParent.fragment(); } // link siblings if (fNextNode != null) { fNextNode.fPreviousNode = fPreviousNode; } if (fPreviousNode != null) { fPreviousNode.fNextNode = fNextNode; } // fix parent's pointers if (fParent != null) { if (fParent.fFirstChild == this) { fParent.fFirstChild = fNextNode; } if (fParent.fLastChild == this) { fParent.fLastChild = fPreviousNode; } } // remove myself fParent = null; fNextNode = null; fPreviousNode = null; } /** * Sets the specified mask of this node's state mask on or off based on the * boolean value - true -> on, false -> off. */ protected void setMask(int mask, boolean on) { if (on) { fStateMask |= mask; } else { fStateMask &= ~mask; } } /** * @see IDOMNode#setName */ public void setName(String name) { fName = name; setNameAltered(true); fragment(); } /** * Sets the state of this node as having its name attribute altered from the * original document contents. */ protected void setNameAltered(boolean altered) { setMask(MASK_NAME_ALTERED, altered); } /** * Sets the original position of the last character of this node's contents * in its document. This method is only used during DOM creation while * normalizing the source range of each node. */ protected void setSourceRangeEnd(int end) { fSourceRange[1] = end; } /** * Sets the original position of the first character of this node's contents * in its document. This method is only used during DOM creation while * normalizing the source range of each node. */ protected void setStartPosition(int start) { fSourceRange[0] = start; } /** * Sets the contents of this node and descendant nodes to be the (identical) * contents of the given node and its descendants. This does not effect this * node's parent and sibling configuration, only the contents of this node. * This is used only to localize the contents of this node. */ protected void shareContents(DOMNode node) { fDocument = node.fDocument; fIsFragmented = node.fIsFragmented; fName = node.fName; fNameRange = rangeCopy(node.fNameRange); fSourceRange = rangeCopy(node.fSourceRange); fStateMask = node.fStateMask; if (canHaveChildren()) { Enumeration myChildren = getChildren(); Enumeration otherChildren = node.getChildren(); DOMNode myChild, otherChild; while (myChildren.hasMoreElements()) { myChild = (DOMNode) myChildren.nextElement(); otherChild = (DOMNode) otherChildren.nextElement(); myChild.shareContents(otherChild); } } } /** * Returns a String representing this node - for Debug * purposes only. */ public abstract String toString(); }