org.eclipse.jdt.core/dom/org/eclipse/jdt/core/dom/DefaultCommentMapper.java - gerrit/aspectj/org.aspectj.shadows - Git at Google

 /*******************************************************************************
  * Copyright (c) 2004 IBM Corporation and others.
  * All rights reserved. This program and the accompanying materials
  * are made available under the terms of the Eclipse Public License v1.0
  * which accompanies this distribution, and is available at
  * http://www.eclipse.org/legal/epl-v10.html
  *
  * Contributors:
  *     IBM Corporation - initial API and implementation
  *******************************************************************************/
 package org.eclipse.jdt.core.dom;

 import java.util.HashMap;

 import org.eclipse.jdt.core.compiler.CharOperation;
 import org.eclipse.jdt.core.compiler.InvalidInputException;
 import org.eclipse.jdt.internal.compiler.parser.Scanner;
 import org.eclipse.jdt.internal.compiler.parser.TerminalTokens;

 /**
  * Internal class for associating comments with AST nodes.
  *
  * @since 3.0
  */
 class DefaultCommentMapper {
 	Comment[] comments;
 	Scanner scanner;

 	// extended nodes storage
 	int leadingPtr;
 	ASTNode[] leadingNodes;
 	int[][] leadingIndexes;
 	int trailingPtr, lastTrailingPtr;
 	ASTNode[] trailingNodes;
 	int[][] trailingIndexes;
 	static final int STORAGE_INCREMENT = 16;

 	/**
 	 * @param table the given table of comments
 	 */
 	DefaultCommentMapper(Comment[] table) {
 		this.comments = table;
 	}

 	boolean hasSameTable(Comment[] table) {
 		return this.comments == table;
 	}

 	/**
 	 * Get comment of the list which includes a given position
 	 *
 	 * @param position The position belonging to the looked up comment
 	 * @return comment which includes the given position or null if none was found
 	 */
 	Comment getComment(int position) {

 		if (this.comments == null) {
 			return null;
 		}
 		int size = this.comments.length;
 		if (size == 0) {
 			return null;
 		}
 		int index = getCommentIndex(0, position, 0);
 		if (index<0) {
 			return null;
 		}
 		return this.comments[index];
 	}

 	/*
 	 * Get the index of comment which contains given position.
 	 * If there's no matching comment, then return depends on exact parameter:
 	 *		= 0: return -1
 	 *		< 0: return index of the comment before the given position
 	 *		> 0: return index of the comment after the given position
 	 */
 	private int getCommentIndex(int start, int position, int exact) {
 		if (position == 0) {
 			if (this.comments.length > 0 && this.comments[0].getStartPosition() == 0) {
 				return 0;
 			}
 			return -1;
 		}
 		int bottom = start, top = this.comments.length - 1;
 		int i = 0, index = -1;
 		Comment comment = null;
 		while (bottom <= top) {
 			i = (bottom + top) /2;
 			comment = this.comments[i];
 			int commentStart = comment.getStartPosition();
 			if (position < commentStart) {
 				top = i-1;
 			} else if (position >=(commentStart+comment.getLength())) {
 				bottom = i+1;
 			} else {
 				index = i;
 				break;
 			}
 		}
 		if (index<0 && exact!=0) {
 			comment = this.comments[i];
 			if (position < comment.getStartPosition()) {
 				return exact<0 ? i-1 : i;
 			} else {
 				return exact<0 ? i : i+1;
 			}
 		}
 		return index;
 	}

 	/**
 	 * Return all leading comments of a given node.
 	 * @param node
 	 * @return an array of Comment or null if there's no leading comment
 	 */
 	Comment[] getLeadingComments(ASTNode node) {
 		if (this.leadingPtr >= 0) {
 			int[] range = null;
 			for (int i=0; range==null && i<=this.leadingPtr; i++) {
 				if (this.leadingNodes[i] == node) range = this.leadingIndexes[i];
 			}
 			if (range != null) {
 				int length = range[1]-range[0]+1;
 				Comment[] leadComments = new Comment[length];
 				System.arraycopy(this.comments, range[0], leadComments, 0, length);
 				return  leadComments;
 			}
 		}
 		return null;
 	}

 	/**
 	 * Return all trailing comments of a given node.
 	 * @param node
 	 * @return an array of Comment or null if there's no trailing comment
 	 */
 	Comment[] getTrailingComments(ASTNode node) {
 		if (this.trailingPtr >= 0) {
 			int[] range = null;
 			for (int i=0; range==null && i<=this.trailingPtr; i++) {
 				if (this.trailingNodes[i] == node) range = this.trailingIndexes[i];
 			}
 			if (range != null) {
 				int length = range[1]-range[0]+1;
 				Comment[] trailComments = new Comment[length];
 				System.arraycopy(this.comments, range[0], trailComments, 0, length);
 				return  trailComments;
 			}
 		}
 		return null;
 	}

 	/**
 	 * Returns the extended start position of the given node. Unlike
 	 * {@link ASTNode#getStartPosition()} and {@link ASTNode#getLength()},
 	 * the extended source range may include comments and whitespace
 	 * immediately before or after the normal source range for the node.
 	 *
 	 * @param node the node
 	 * @return the 0-based character index, or <code>-1</code>
 	 *    if no source position information is recorded for this node
 	 * @see #getExtendedLength(ASTNode)
 	 * @since 3.0
 	 */
 	public int getExtendedStartPosition(ASTNode node) {
 		if (this.leadingPtr >= 0) {
 			int[] range = null;
 			for (int i=0; range==null && i<=this.leadingPtr; i++) {
 				if (this.leadingNodes[i] == node) range = this.leadingIndexes[i];
 			}
 			if (range != null) {
 				return  this.comments[range[0]].getStartPosition() ;
 			}
 		}
 		return node.getStartPosition();
 	}

 	/*
 	 * Returns the extended end position of the given node.
 	 */
 	public int getExtendedEnd(ASTNode node) {
 		int end = node.getStartPosition() + node.getLength();
 		if (this.trailingPtr >= 0) {
 			int[] range = null;
 			for (int i=0; range==null && i<=this.trailingPtr; i++) {
 				if (this.trailingNodes[i] == node) range = this.trailingIndexes[i];
 			}
 			if (range != null) {
 				Comment lastComment = this.comments[range[1]];
 				end = lastComment.getStartPosition() + lastComment.getLength();
 			}
 		}
 		return end-1;
 	}

 	/**
 	 * Returns the extended source length of the given node. Unlike
 	 * {@link ASTNode#getStartPosition()} and {@link ASTNode#getLength()},
 	 * the extended source range may include comments and whitespace
 	 * immediately before or after the normal source range for the node.
 	 *
 	 * @param node the node
 	 * @return a (possibly 0) length, or <code>0</code>
 	 *    if no source position information is recorded for this node
 	 * @see #getExtendedStartPosition(ASTNode)
 	 * @see #getExtendedEnd(ASTNode)
 	 * @since 3.0
 	 */
 	public int getExtendedLength(ASTNode node) {
 		return getExtendedEnd(node) - getExtendedStartPosition(node) + 1;
 	}

 	/*
 	 * Initialize leading and trailing comments tables in whole nodes hierarchy of a compilation
 	 * unit.
 	 * Scanner is necessary to scan between nodes and comments and verify if there's
 	 * nothing else than white spaces.
 	 */
 	void initialize(CompilationUnit unit, Scanner sc) {

 		// Init array pointers
 		this.leadingPtr = -1;
 		this.trailingPtr = -1;

 		// Init comments
 		this.comments = unit.optionalCommentTable;
 		if (this.comments == null) {
 			return;
 		}
 		int size = this.comments.length;
 		if (size == 0) {
 			return;
 		}

 		// Init scanner and start ranges computing
 		this.scanner = sc;
 		this.scanner.tokenizeWhiteSpace = true;

 		// Start unit visit
 		DefaultASTVisitor commentVisitor = new CommentMapperVisitor();
 		unit.accept(commentVisitor);

 		// Reduce leading arrays if necessary
 		int leadingCount = this.leadingPtr + 1;
 		if (leadingCount > 0 && leadingCount < this.leadingIndexes.length) {
 			System.arraycopy(this.leadingNodes, 0, this.leadingNodes = new ASTNode[leadingCount], 0, leadingCount);
 			System.arraycopy(this.leadingIndexes, 0, this.leadingIndexes= new int[leadingCount][], 0, leadingCount);
 		}

 		// Reduce trailing arrays if necessary
 		if (this.trailingPtr >= 0) {
 			// remove last remaining unresolved nodes
 			while (this.trailingIndexes[this.trailingPtr][0] == -1) {
 				this.trailingPtr--;
 				if (this.trailingPtr < 0) {
 					this.trailingIndexes = null;
 					this.trailingNodes = null;
 					break;
 				}
 			}

 			// reduce array size
 			int trailingCount = this.trailingPtr + 1;
 			if (trailingCount > 0 && trailingCount < this.trailingIndexes.length) {
 				System.arraycopy(this.trailingNodes, 0, this.trailingNodes = new ASTNode[trailingCount], 0, trailingCount);
 				System.arraycopy(this.trailingIndexes, 0, this.trailingIndexes= new int[trailingCount][], 0, trailingCount);
 			}
 		}
 	}

 	/**
 	 * Search and store node leading comments. Comments are searched in position range
 	 * from previous extended position to node start position. If one or several comment are found,
 	 * returns first comment start position, otherwise returns node start position.
 	 *
 	 * First look after first comment before node start position and return if none was found...
 	 *
 	 * When first comment was found before node, goes up in comment list until one of
 	 * following condition becomes true:
 	 * 	1) comment end is before previous end
 	 * 	2) comment start and previous end is on the same line but not on same line of node start
 	 * 	3) there's other than white characters between current node and comment
 	 * 	4) there's more than 1 line between current node and comment
 	 *
 	 * If at least one potential comment has been found, then no token should be on
 	 * on the same line before, so remove all comments which do not verify this assumption.
 	 *
 	 * If finally there is a subset of comments, then store start and end indexes
 	 * in leading comments table.
 	 */
 	int storeLeadingComments(ASTNode node, int previousEnd) {
 		// Init extended position
 		int nodeStart = node.getStartPosition();
 		int extended = nodeStart;

 		// Get line of node start position
 		int previousEndLine = this.scanner.getLineNumber(previousEnd);
 		int nodeStartLine = this.scanner.getLineNumber(nodeStart);

 		// Find first comment index
 		int idx = getCommentIndex(0, nodeStart, -1);
 		if (idx == -1) {
 			return nodeStart;
 		}

 		// Look after potential comments
 		int startIdx = -1;
 		int endIdx = idx;
 		int previousStart = nodeStart;
 		while (idx >= 0 && previousStart  >= previousEnd) {
 			// Verify for each comment that there's only white spaces between end and start of {following comment|node}
 			Comment comment = this.comments[idx];
 			int commentStart = comment.getStartPosition();
 			int end = commentStart+comment.getLength()-1;
 			int commentLine = this.scanner.getLineNumber(commentStart);
 			if (end <= previousEnd || (commentLine == previousEndLine && commentLine != nodeStartLine)) {
 				// stop search on condition 1) and 2)
 				break;
 			} else if ((end+1) < previousStart) { // may be equals => then no scan is necessary
 				this.scanner.resetTo(end+1, previousStart);
 				try {
 					int token = this.scanner.getNextToken();
 					if (token != TerminalTokens.TokenNameWHITESPACE || this.scanner.currentPosition != previousStart) {
 						// stop search on condition 3)
 						// if first comment fails, then there's no extended position in fact
 						if (idx == endIdx) {
 							return nodeStart;
 						}
 						break;
 					}
 				} catch (InvalidInputException e) {
 					// Should not happen, but return no extended position...
 					return nodeStart;
 				}
 				// verify that there's no more than one line between node/comments
 				char[] gap = this.scanner.getCurrentIdentifierSource();
 				int nbrLine = 0;
 				int pos = -1;
 				while ((pos=CharOperation.indexOf('\n', gap,pos+1)) >= 0) {
 					nbrLine++;
 				}
 				if (nbrLine > 1) {
 					// stop search on condition 4)
 					break;
 				}
 			}
 			// Store previous infos
 			previousStart = commentStart;
 			startIdx = idx--;
 		}
 		if (startIdx != -1) {
 			// Verify that there's no token on the same line before first leading comment
 			int commentStart = this.comments[startIdx].getStartPosition();
 			if (previousEnd < commentStart && previousEndLine != nodeStartLine) {
 				int lastTokenEnd = previousEnd;
 				this.scanner.resetTo(previousEnd, commentStart);
 				try {
 					while (this.scanner.currentPosition < commentStart) {
 						if (this.scanner.getNextToken() != TerminalTokens.TokenNameWHITESPACE) {
 							lastTokenEnd =  this.scanner.getCurrentTokenEndPosition();
 						}
 					}
 				} catch (InvalidInputException e) {
 					// do nothing
 				}
 				int lastTokenLine = this.scanner.getLineNumber(lastTokenEnd);
 				int length = this.comments.length;
 				while (startIdx<length && lastTokenLine == this.scanner.getLineNumber(this.comments[startIdx].getStartPosition()) && nodeStartLine != lastTokenLine) {
 					startIdx++;
 				}
 			}
 			// Store leading comments indexes
 			if (startIdx <= endIdx) {
 				if (++this.leadingPtr == 0) {
 					this.leadingNodes = new ASTNode[STORAGE_INCREMENT];
 					this.leadingIndexes = new int[STORAGE_INCREMENT][];
 				} else if (this.leadingPtr == this.leadingNodes.length) {
 					int newLength = (this.leadingPtr*3/2)+STORAGE_INCREMENT;
 					System.arraycopy(this.leadingNodes, 0, this.leadingNodes = new ASTNode[newLength], 0, this.leadingPtr);
 					System.arraycopy(this.leadingIndexes, 0, this.leadingIndexes = new int[newLength][], 0, this.leadingPtr);
 				}
 				this.leadingNodes[this.leadingPtr] = node;
 				this.leadingIndexes[this.leadingPtr] = new int[] { startIdx, endIdx };
 				extended = this.comments[endIdx].getStartPosition();
 			}
 		}
 		return extended;
 	}

 	/**
 	 * Search and store node trailing comments. Comments are searched in position range
 	 * from node end position to specified next start. If one or several comment are found,
 	 * returns last comment end position, otherwise returns node end position.
 	 *
 	 * First look after first comment after node end position and return if none was found...
 	 *
 	 * When first comment was found after node, goes down in comment list until one of
 	 * following condition becomes true:
 	 * 	1) comment start is after next start
 	 * 	2) there's other than white characters between current node and comment
 	 * 	3) there's more than 1 line between current node and comment
 	 *
 	 * If at least one potential comment has been found, then all of them has to be separated
 	 * from following node. So, remove all comments which do not verify this assumption.
 	 * Note that this verification is not applicable on last node.
 	 *
 	 * If finally there is a subset of comments, then store start and end indexes
 	 * in trailing comments table.
 	 */
 	int storeTrailingComments(ASTNode node, int nextStart,  boolean lastChild) {

 		// Init extended position
 		int nodeEnd = node.getStartPosition()+node.getLength()-1;
 		if (nodeEnd == nextStart) {
 			// special case for last child of its parent
 			if (++this.trailingPtr == 0) {
 				this.trailingNodes = new ASTNode[STORAGE_INCREMENT];
 				this.trailingIndexes = new int[STORAGE_INCREMENT][];
 				this.lastTrailingPtr = -1;
 			} else if (this.trailingPtr == this.trailingNodes.length) {
 				int newLength = (this.trailingPtr*3/2)+STORAGE_INCREMENT;
 				System.arraycopy(this.trailingNodes, 0, this.trailingNodes = new ASTNode[newLength], 0, this.trailingPtr);
 				System.arraycopy(this.trailingIndexes, 0, this.trailingIndexes = new int[newLength][], 0, this.trailingPtr);
 			}
 			this.trailingNodes[this.trailingPtr] = node;
 			this.trailingIndexes[this.trailingPtr] = new int[] { -1, -1 };
 			return nodeEnd;
 		}
 		int extended = nodeEnd;

 		// Get line number
 		int nodeEndLine = this.scanner.getLineNumber(nodeEnd);

 		// Find comments range index
 		int idx = getCommentIndex(0, nodeEnd, 1);
 		if (idx == -1) {
 			return nodeEnd;
 		}

 		// Look after potential comments
 		int startIdx = idx;
 		int endIdx = -1;
 		int length = this.comments.length;
 		int commentStart = extended+1;
 		int previousEnd = nodeEnd+1;
 		int sameLineIdx = -1;
 		while (idx<length && commentStart < nextStart) {
 			// get comment and leave if next starting position has been reached
 			Comment comment = this.comments[idx];
 			commentStart = comment.getStartPosition();
 			// verify that there's nothing else than white spaces between node/comments
 			if (commentStart >= nextStart) {
 				// stop search on condition 1)
 				break;
 			} else if (previousEnd < commentStart) {
 				this.scanner.resetTo(previousEnd, commentStart);
 				try {
 					int token = this.scanner.getNextToken();
 					if (token != TerminalTokens.TokenNameWHITESPACE || this.scanner.currentPosition != commentStart) {
 						// stop search on condition 2)
 						// if first index fails, then there's no extended position in fact...
 						if (idx == startIdx) {
 							return nodeEnd;
 						}
 						// otherwise we get the last index of trailing comment => break
 						break;
 					}
 				} catch (InvalidInputException e) {
 					// Should not happen, but return no extended position...
 					return nodeEnd;
 				}
 				// verify that there's no more than one line between node/comments
 				char[] gap = this.scanner.getCurrentIdentifierSource();
 				int nbrLine = 0;
 				int pos = -1;
 				while ((pos=CharOperation.indexOf('\n', gap,pos+1)) >= 0) {
 					nbrLine++;
 				}
 				if (nbrLine > 1) {
 					// stop search on condition 3)
 					break;
 				}
 			}
 			// Store index if we're on the same line than node end
 			int commentLine = this.scanner.getLineNumber(commentStart);
 			if (commentLine == nodeEndLine) {
 				sameLineIdx = idx;
 			}
 			// Store previous infos
 			previousEnd = commentStart+comment.getLength();
 			endIdx = idx++;
 		}
 		if (endIdx != -1) {
 			// Verify that following node start is separated
 			if (!lastChild) {
 				int nextLine = this.scanner.getLineNumber(nextStart);
 				int previousLine = this.scanner.getLineNumber(previousEnd);
 				if((nextLine - previousLine) <= 1) {
 					if (sameLineIdx == -1) return nodeEnd;
 					endIdx = sameLineIdx;
 				}
 			}
 			// Store trailing comments indexes
 			if (++this.trailingPtr == 0) {
 				this.trailingNodes = new ASTNode[STORAGE_INCREMENT];
 				this.trailingIndexes = new int[STORAGE_INCREMENT][];
 				this.lastTrailingPtr = -1;
 			} else if (this.trailingPtr == this.trailingNodes.length) {
 				int newLength = (this.trailingPtr*3/2)+STORAGE_INCREMENT;
 				System.arraycopy(this.trailingNodes, 0, this.trailingNodes = new ASTNode[newLength], 0, this.trailingPtr);
 				System.arraycopy(this.trailingIndexes, 0, this.trailingIndexes = new int[newLength][], 0, this.trailingPtr);
 			}
 			this.trailingNodes[this.trailingPtr] = node;
 			int[] nodeRange = new int[] { startIdx, endIdx };
 			this.trailingIndexes[this.trailingPtr] = nodeRange;
 			// Compute new extended end
 			extended = this.comments[endIdx].getStartPosition()+this.comments[endIdx].getLength()-1;
 			// Look for children unresolved extended end
 			ASTNode previousNode = node;
 			int ptr = this.trailingPtr - 1; // children extended end were stored before
 			unresolved: while (ptr >= 0) {
 				int[] range = this.trailingIndexes[ptr];
 				if (range[0] != -1 || range[1] != -1) break; // there's no more unresolved nodes
 				ASTNode unresolved = this.trailingNodes[ptr];
 				if (previousNode != unresolved.getParent()) break; // we're no longer in node ancestor hierarchy
 				this.trailingIndexes[ptr] = nodeRange;
 				previousNode = unresolved;
 				ptr--; // get previous node
 			}
 			// Remove remaining unresolved nodes
 			if (ptr > this.lastTrailingPtr) {
 				int offset = ptr - this.lastTrailingPtr;
 				for (int i=ptr+1; i<=this.trailingPtr; i++) {
 					this.trailingNodes[i-offset] = this.trailingNodes[i];
 					this.trailingIndexes[i-offset] = this.trailingIndexes[i];
 				}
 				this.trailingPtr -= offset;
 			}
 			this.lastTrailingPtr = this.trailingPtr;
 		}
 		return extended;
 	}

 	class CommentMapperVisitor extends DefaultASTVisitor {

 		HashMap waitingSiblings = new HashMap(10);

 		protected boolean visitNode(ASTNode node) {

 			// Get default previous end
 			ASTNode parent = node.getParent();
 			int previousEnd = parent.getStartPosition();

 			// Look for sibling node
 			ASTNode sibling = (ASTNode) this.waitingSiblings.get(parent);
 			if (sibling != null) {
 				// Found one previous sibling, so compute its trailing comments using current node start position
 				try {
 					previousEnd = storeTrailingComments(sibling, node.getStartPosition(), false);
 				} catch (Exception ex) {
 					// Give up extended ranges at this level if unexpected exception happens...
 				}
 			}

 			// Compute leading comments for current node
 			try {
 				storeLeadingComments(node, previousEnd);
 			} catch (Exception ex) {
 				// Give up extended ranges at this level if unexpected exception happens...
 			}

 			// Store current node as waiting sibling for its parent
 			this.waitingSiblings.put(parent, node);

 			// We're always ok to visit sub-levels
 			return true;
 		}

 		protected void endVisitNode(ASTNode node) {

 			// Look if a child node is waiting for trailing comments computing
 			ASTNode sibling = (ASTNode) this.waitingSiblings.get(node);
 			if (sibling != null) {
 				try {
 					storeTrailingComments(sibling, node.getStartPosition()+node.getLength()-1, true);
 				} catch (Exception ex) {
 					// Give up extended ranges at this level if unexpected exception happens...
 				}
 			}
 		}

 		public boolean visit ( CompilationUnit node) {
 			// do nothing special, just go down in sub-levels
 			return true;
 		}
 	}
 }
	/*******************************************************************************
	* Copyright (c) 2004 IBM Corporation and others.
	* All rights reserved. This program and the accompanying materials
	* are made available under the terms of the Eclipse Public License v1.0
	* which accompanies this distribution, and is available at
	* http://www.eclipse.org/legal/epl-v10.html
	*
	* Contributors:
	* IBM Corporation - initial API and implementation
	*******************************************************************************/
	package org.eclipse.jdt.core.dom;

	import java.util.HashMap;

	import org.eclipse.jdt.core.compiler.CharOperation;
	import org.eclipse.jdt.core.compiler.InvalidInputException;
	import org.eclipse.jdt.internal.compiler.parser.Scanner;
	import org.eclipse.jdt.internal.compiler.parser.TerminalTokens;

	/**
	* Internal class for associating comments with AST nodes.
	*
	* @since 3.0
	*/
	class DefaultCommentMapper {
	Comment[] comments;
	Scanner scanner;

	// extended nodes storage
	int leadingPtr;
	ASTNode[] leadingNodes;
	int[][] leadingIndexes;
	int trailingPtr, lastTrailingPtr;
	ASTNode[] trailingNodes;
	int[][] trailingIndexes;
	static final int STORAGE_INCREMENT = 16;

	/**
	* @param table the given table of comments
	*/
	DefaultCommentMapper(Comment[] table) {
	this.comments = table;
	}

	boolean hasSameTable(Comment[] table) {
	return this.comments == table;
	}

	/**
	* Get comment of the list which includes a given position
	*
	* @param position The position belonging to the looked up comment
	* @return comment which includes the given position or null if none was found
	*/
	Comment getComment(int position) {

	if (this.comments == null) {
	return null;
	}
	int size = this.comments.length;
	if (size == 0) {
	return null;
	}
	int index = getCommentIndex(0, position, 0);
	if (index<0) {
	return null;
	}
	return this.comments[index];
	}

	/*
	* Get the index of comment which contains given position.
	* If there's no matching comment, then return depends on exact parameter:
	* = 0: return -1
	* < 0: return index of the comment before the given position
	* > 0: return index of the comment after the given position
	*/
	private int getCommentIndex(int start, int position, int exact) {
	if (position == 0) {
	if (this.comments.length > 0 && this.comments[0].getStartPosition() == 0) {
	return 0;
	}
	return -1;
	}
	int bottom = start, top = this.comments.length - 1;
	int i = 0, index = -1;
	Comment comment = null;
	while (bottom <= top) {
	i = (bottom + top) /2;
	comment = this.comments[i];
	int commentStart = comment.getStartPosition();
	if (position < commentStart) {
	top = i-1;
	} else if (position >=(commentStart+comment.getLength())) {
	bottom = i+1;
	} else {
	index = i;
	break;
	}
	}
	if (index<0 && exact!=0) {
	comment = this.comments[i];
	if (position < comment.getStartPosition()) {
	return exact<0 ? i-1 : i;
	} else {
	return exact<0 ? i : i+1;
	}
	}
	return index;
	}

	/**
	* Return all leading comments of a given node.
	* @param node
	* @return an array of Comment or null if there's no leading comment
	*/
	Comment[] getLeadingComments(ASTNode node) {
	if (this.leadingPtr >= 0) {
	int[] range = null;
	for (int i=0; range==null && i<=this.leadingPtr; i++) {
	if (this.leadingNodes[i] == node) range = this.leadingIndexes[i];
	}
	if (range != null) {
	int length = range[1]-range[0]+1;
	Comment[] leadComments = new Comment[length];
	System.arraycopy(this.comments, range[0], leadComments, 0, length);
	return leadComments;
	}
	}
	return null;
	}

	/**
	* Return all trailing comments of a given node.
	* @param node
	* @return an array of Comment or null if there's no trailing comment
	*/
	Comment[] getTrailingComments(ASTNode node) {
	if (this.trailingPtr >= 0) {
	int[] range = null;
	for (int i=0; range==null && i<=this.trailingPtr; i++) {
	if (this.trailingNodes[i] == node) range = this.trailingIndexes[i];
	}
	if (range != null) {
	int length = range[1]-range[0]+1;
	Comment[] trailComments = new Comment[length];
	System.arraycopy(this.comments, range[0], trailComments, 0, length);
	return trailComments;
	}
	}
	return null;
	}

	/**
	* Returns the extended start position of the given node. Unlike
	* {@link ASTNode#getStartPosition()} and {@link ASTNode#getLength()},
	* the extended source range may include comments and whitespace
	* immediately before or after the normal source range for the node.
	*
	* @param node the node
	* @return the 0-based character index, or <code>-1</code>
	* if no source position information is recorded for this node
	* @see #getExtendedLength(ASTNode)
	* @since 3.0
	*/
	public int getExtendedStartPosition(ASTNode node) {
	if (this.leadingPtr >= 0) {
	int[] range = null;
	for (int i=0; range==null && i<=this.leadingPtr; i++) {
	if (this.leadingNodes[i] == node) range = this.leadingIndexes[i];
	}
	if (range != null) {
	return this.comments[range[0]].getStartPosition() ;
	}
	}
	return node.getStartPosition();
	}

	/*
	* Returns the extended end position of the given node.
	*/
	public int getExtendedEnd(ASTNode node) {
	int end = node.getStartPosition() + node.getLength();
	if (this.trailingPtr >= 0) {
	int[] range = null;
	for (int i=0; range==null && i<=this.trailingPtr; i++) {
	if (this.trailingNodes[i] == node) range = this.trailingIndexes[i];
	}
	if (range != null) {
	Comment lastComment = this.comments[range[1]];
	end = lastComment.getStartPosition() + lastComment.getLength();
	}
	}
	return end-1;
	}

	/**
	* Returns the extended source length of the given node. Unlike
	* {@link ASTNode#getStartPosition()} and {@link ASTNode#getLength()},
	* the extended source range may include comments and whitespace
	* immediately before or after the normal source range for the node.
	*
	* @param node the node
	* @return a (possibly 0) length, or <code>0</code>
	* if no source position information is recorded for this node
	* @see #getExtendedStartPosition(ASTNode)
	* @see #getExtendedEnd(ASTNode)
	* @since 3.0
	*/
	public int getExtendedLength(ASTNode node) {
	return getExtendedEnd(node) - getExtendedStartPosition(node) + 1;
	}

	/*
	* Initialize leading and trailing comments tables in whole nodes hierarchy of a compilation
	* unit.
	* Scanner is necessary to scan between nodes and comments and verify if there's
	* nothing else than white spaces.
	*/
	void initialize(CompilationUnit unit, Scanner sc) {

	// Init array pointers
	this.leadingPtr = -1;
	this.trailingPtr = -1;

	// Init comments
	this.comments = unit.optionalCommentTable;
	if (this.comments == null) {
	return;
	}
	int size = this.comments.length;
	if (size == 0) {
	return;
	}

	// Init scanner and start ranges computing
	this.scanner = sc;
	this.scanner.tokenizeWhiteSpace = true;

	// Start unit visit
	DefaultASTVisitor commentVisitor = new CommentMapperVisitor();
	unit.accept(commentVisitor);

	// Reduce leading arrays if necessary
	int leadingCount = this.leadingPtr + 1;
	if (leadingCount > 0 && leadingCount < this.leadingIndexes.length) {
	System.arraycopy(this.leadingNodes, 0, this.leadingNodes = new ASTNode[leadingCount], 0, leadingCount);
	System.arraycopy(this.leadingIndexes, 0, this.leadingIndexes= new int[leadingCount][], 0, leadingCount);
	}

	// Reduce trailing arrays if necessary
	if (this.trailingPtr >= 0) {
	// remove last remaining unresolved nodes
	while (this.trailingIndexes[this.trailingPtr][0] == -1) {
	this.trailingPtr--;
	if (this.trailingPtr < 0) {
	this.trailingIndexes = null;
	this.trailingNodes = null;
	break;
	}
	}

	// reduce array size
	int trailingCount = this.trailingPtr + 1;
	if (trailingCount > 0 && trailingCount < this.trailingIndexes.length) {
	System.arraycopy(this.trailingNodes, 0, this.trailingNodes = new ASTNode[trailingCount], 0, trailingCount);
	System.arraycopy(this.trailingIndexes, 0, this.trailingIndexes= new int[trailingCount][], 0, trailingCount);
	}
	}
	}

	/**
	* Search and store node leading comments. Comments are searched in position range
	* from previous extended position to node start position. If one or several comment are found,
	* returns first comment start position, otherwise returns node start position.
	*
	* First look after first comment before node start position and return if none was found...
	*
	* When first comment was found before node, goes up in comment list until one of
	* following condition becomes true:
	* 1) comment end is before previous end
	* 2) comment start and previous end is on the same line but not on same line of node start
	* 3) there's other than white characters between current node and comment
	* 4) there's more than 1 line between current node and comment
	*
	* If at least one potential comment has been found, then no token should be on
	* on the same line before, so remove all comments which do not verify this assumption.
	*
	* If finally there is a subset of comments, then store start and end indexes
	* in leading comments table.
	*/
	int storeLeadingComments(ASTNode node, int previousEnd) {
	// Init extended position
	int nodeStart = node.getStartPosition();
	int extended = nodeStart;

	// Get line of node start position
	int previousEndLine = this.scanner.getLineNumber(previousEnd);
	int nodeStartLine = this.scanner.getLineNumber(nodeStart);

	// Find first comment index
	int idx = getCommentIndex(0, nodeStart, -1);
	if (idx == -1) {
	return nodeStart;
	}

	// Look after potential comments
	int startIdx = -1;
	int endIdx = idx;
	int previousStart = nodeStart;
	while (idx >= 0 && previousStart >= previousEnd) {
	// Verify for each comment that there's only white spaces between end and start of {following comment\|node}
	Comment comment = this.comments[idx];
	int commentStart = comment.getStartPosition();
	int end = commentStart+comment.getLength()-1;
	int commentLine = this.scanner.getLineNumber(commentStart);
	if (end <= previousEnd \|\| (commentLine == previousEndLine && commentLine != nodeStartLine)) {
	// stop search on condition 1) and 2)
	break;
	} else if ((end+1) < previousStart) { // may be equals => then no scan is necessary
	this.scanner.resetTo(end+1, previousStart);
	try {
	int token = this.scanner.getNextToken();
	if (token != TerminalTokens.TokenNameWHITESPACE \|\| this.scanner.currentPosition != previousStart) {
	// stop search on condition 3)
	// if first comment fails, then there's no extended position in fact
	if (idx == endIdx) {
	return nodeStart;
	}
	break;
	}
	} catch (InvalidInputException e) {
	// Should not happen, but return no extended position...
	return nodeStart;
	}
	// verify that there's no more than one line between node/comments
	char[] gap = this.scanner.getCurrentIdentifierSource();
	int nbrLine = 0;
	int pos = -1;
	while ((pos=CharOperation.indexOf('\n', gap,pos+1)) >= 0) {
	nbrLine++;
	}
	if (nbrLine > 1) {
	// stop search on condition 4)
	break;
	}
	}
	// Store previous infos
	previousStart = commentStart;
	startIdx = idx--;
	}
	if (startIdx != -1) {
	// Verify that there's no token on the same line before first leading comment
	int commentStart = this.comments[startIdx].getStartPosition();
	if (previousEnd < commentStart && previousEndLine != nodeStartLine) {
	int lastTokenEnd = previousEnd;
	this.scanner.resetTo(previousEnd, commentStart);
	try {
	while (this.scanner.currentPosition < commentStart) {
	if (this.scanner.getNextToken() != TerminalTokens.TokenNameWHITESPACE) {
	lastTokenEnd = this.scanner.getCurrentTokenEndPosition();
	}
	}
	} catch (InvalidInputException e) {
	// do nothing
	}
	int lastTokenLine = this.scanner.getLineNumber(lastTokenEnd);
	int length = this.comments.length;
	while (startIdx<length && lastTokenLine == this.scanner.getLineNumber(this.comments[startIdx].getStartPosition()) && nodeStartLine != lastTokenLine) {
	startIdx++;
	}
	}
	// Store leading comments indexes
	if (startIdx <= endIdx) {
	if (++this.leadingPtr == 0) {
	this.leadingNodes = new ASTNode[STORAGE_INCREMENT];
	this.leadingIndexes = new int[STORAGE_INCREMENT][];
	} else if (this.leadingPtr == this.leadingNodes.length) {
	int newLength = (this.leadingPtr*3/2)+STORAGE_INCREMENT;
	System.arraycopy(this.leadingNodes, 0, this.leadingNodes = new ASTNode[newLength], 0, this.leadingPtr);
	System.arraycopy(this.leadingIndexes, 0, this.leadingIndexes = new int[newLength][], 0, this.leadingPtr);
	}
	this.leadingNodes[this.leadingPtr] = node;
	this.leadingIndexes[this.leadingPtr] = new int[] { startIdx, endIdx };
	extended = this.comments[endIdx].getStartPosition();
	}
	}
	return extended;
	}

	/**
	* Search and store node trailing comments. Comments are searched in position range
	* from node end position to specified next start. If one or several comment are found,
	* returns last comment end position, otherwise returns node end position.
	*
	* First look after first comment after node end position and return if none was found...
	*
	* When first comment was found after node, goes down in comment list until one of
	* following condition becomes true:
	* 1) comment start is after next start
	* 2) there's other than white characters between current node and comment
	* 3) there's more than 1 line between current node and comment
	*
	* If at least one potential comment has been found, then all of them has to be separated
	* from following node. So, remove all comments which do not verify this assumption.
	* Note that this verification is not applicable on last node.
	*
	* If finally there is a subset of comments, then store start and end indexes
	* in trailing comments table.
	*/
	int storeTrailingComments(ASTNode node, int nextStart, boolean lastChild) {

	// Init extended position
	int nodeEnd = node.getStartPosition()+node.getLength()-1;
	if (nodeEnd == nextStart) {
	// special case for last child of its parent
	if (++this.trailingPtr == 0) {
	this.trailingNodes = new ASTNode[STORAGE_INCREMENT];
	this.trailingIndexes = new int[STORAGE_INCREMENT][];
	this.lastTrailingPtr = -1;
	} else if (this.trailingPtr == this.trailingNodes.length) {
	int newLength = (this.trailingPtr*3/2)+STORAGE_INCREMENT;
	System.arraycopy(this.trailingNodes, 0, this.trailingNodes = new ASTNode[newLength], 0, this.trailingPtr);
	System.arraycopy(this.trailingIndexes, 0, this.trailingIndexes = new int[newLength][], 0, this.trailingPtr);
	}
	this.trailingNodes[this.trailingPtr] = node;
	this.trailingIndexes[this.trailingPtr] = new int[] { -1, -1 };
	return nodeEnd;
	}
	int extended = nodeEnd;

	// Get line number
	int nodeEndLine = this.scanner.getLineNumber(nodeEnd);

	// Find comments range index
	int idx = getCommentIndex(0, nodeEnd, 1);
	if (idx == -1) {
	return nodeEnd;
	}

	// Look after potential comments
	int startIdx = idx;
	int endIdx = -1;
	int length = this.comments.length;
	int commentStart = extended+1;
	int previousEnd = nodeEnd+1;
	int sameLineIdx = -1;
	while (idx<length && commentStart < nextStart) {
	// get comment and leave if next starting position has been reached
	Comment comment = this.comments[idx];
	commentStart = comment.getStartPosition();
	// verify that there's nothing else than white spaces between node/comments
	if (commentStart >= nextStart) {
	// stop search on condition 1)
	break;
	} else if (previousEnd < commentStart) {
	this.scanner.resetTo(previousEnd, commentStart);
	try {
	int token = this.scanner.getNextToken();
	if (token != TerminalTokens.TokenNameWHITESPACE \|\| this.scanner.currentPosition != commentStart) {
	// stop search on condition 2)
	// if first index fails, then there's no extended position in fact...
	if (idx == startIdx) {
	return nodeEnd;
	}
	// otherwise we get the last index of trailing comment => break
	break;
	}
	} catch (InvalidInputException e) {
	// Should not happen, but return no extended position...
	return nodeEnd;
	}
	// verify that there's no more than one line between node/comments
	char[] gap = this.scanner.getCurrentIdentifierSource();
	int nbrLine = 0;
	int pos = -1;
	while ((pos=CharOperation.indexOf('\n', gap,pos+1)) >= 0) {
	nbrLine++;
	}
	if (nbrLine > 1) {
	// stop search on condition 3)
	break;
	}
	}
	// Store index if we're on the same line than node end
	int commentLine = this.scanner.getLineNumber(commentStart);
	if (commentLine == nodeEndLine) {
	sameLineIdx = idx;
	}
	// Store previous infos
	previousEnd = commentStart+comment.getLength();
	endIdx = idx++;
	}
	if (endIdx != -1) {
	// Verify that following node start is separated
	if (!lastChild) {
	int nextLine = this.scanner.getLineNumber(nextStart);
	int previousLine = this.scanner.getLineNumber(previousEnd);
	if((nextLine - previousLine) <= 1) {
	if (sameLineIdx == -1) return nodeEnd;
	endIdx = sameLineIdx;
	}
	}
	// Store trailing comments indexes
	if (++this.trailingPtr == 0) {
	this.trailingNodes = new ASTNode[STORAGE_INCREMENT];
	this.trailingIndexes = new int[STORAGE_INCREMENT][];
	this.lastTrailingPtr = -1;
	} else if (this.trailingPtr == this.trailingNodes.length) {
	int newLength = (this.trailingPtr*3/2)+STORAGE_INCREMENT;
	System.arraycopy(this.trailingNodes, 0, this.trailingNodes = new ASTNode[newLength], 0, this.trailingPtr);
	System.arraycopy(this.trailingIndexes, 0, this.trailingIndexes = new int[newLength][], 0, this.trailingPtr);
	}
	this.trailingNodes[this.trailingPtr] = node;
	int[] nodeRange = new int[] { startIdx, endIdx };
	this.trailingIndexes[this.trailingPtr] = nodeRange;
	// Compute new extended end
	extended = this.comments[endIdx].getStartPosition()+this.comments[endIdx].getLength()-1;
	// Look for children unresolved extended end
	ASTNode previousNode = node;
	int ptr = this.trailingPtr - 1; // children extended end were stored before
	unresolved: while (ptr >= 0) {
	int[] range = this.trailingIndexes[ptr];
	if (range[0] != -1 \|\| range[1] != -1) break; // there's no more unresolved nodes
	ASTNode unresolved = this.trailingNodes[ptr];
	if (previousNode != unresolved.getParent()) break; // we're no longer in node ancestor hierarchy
	this.trailingIndexes[ptr] = nodeRange;
	previousNode = unresolved;
	ptr--; // get previous node
	}
	// Remove remaining unresolved nodes
	if (ptr > this.lastTrailingPtr) {
	int offset = ptr - this.lastTrailingPtr;
	for (int i=ptr+1; i<=this.trailingPtr; i++) {
	this.trailingNodes[i-offset] = this.trailingNodes[i];
	this.trailingIndexes[i-offset] = this.trailingIndexes[i];
	}
	this.trailingPtr -= offset;
	}
	this.lastTrailingPtr = this.trailingPtr;
	}
	return extended;
	}

	class CommentMapperVisitor extends DefaultASTVisitor {

	HashMap waitingSiblings = new HashMap(10);

	protected boolean visitNode(ASTNode node) {

	// Get default previous end
	ASTNode parent = node.getParent();
	int previousEnd = parent.getStartPosition();

	// Look for sibling node
	ASTNode sibling = (ASTNode) this.waitingSiblings.get(parent);
	if (sibling != null) {
	// Found one previous sibling, so compute its trailing comments using current node start position
	try {
	previousEnd = storeTrailingComments(sibling, node.getStartPosition(), false);
	} catch (Exception ex) {
	// Give up extended ranges at this level if unexpected exception happens...
	}
	}

	// Compute leading comments for current node
	try {
	storeLeadingComments(node, previousEnd);
	} catch (Exception ex) {
	// Give up extended ranges at this level if unexpected exception happens...
	}

	// Store current node as waiting sibling for its parent
	this.waitingSiblings.put(parent, node);

	// We're always ok to visit sub-levels
	return true;
	}

	protected void endVisitNode(ASTNode node) {

	// Look if a child node is waiting for trailing comments computing
	ASTNode sibling = (ASTNode) this.waitingSiblings.get(node);
	if (sibling != null) {
	try {
	storeTrailingComments(sibling, node.getStartPosition()+node.getLength()-1, true);
	} catch (Exception ex) {
	// Give up extended ranges at this level if unexpected exception happens...
	}
	}
	}

	public boolean visit ( CompilationUnit node) {
	// do nothing special, just go down in sub-levels
	return true;
	}
	}
	}