gt: 			innerList= new ArrayList(2);
context: /*******************************************************************************
   * Copyright (c) 2000, 2013 IBM Corporation and others.
   *
   * This program and the accompanying materials
   * are made available under the terms of the Eclipse Public License 2.0
   * which accompanies this distribution, and is available at
   * https://www.eclipse.org/legal/epl-2.0/
   *
   * SPDX-License-Identifier: EPL-2.0
   *
   * Contributors:
   *     IBM Corporation - initial API and implementation
   *******************************************************************************/
  package org.eclipse.jdt.internal.core.dom.rewrite;
  
  import java.util.*;
  
  import org.eclipse.jdt.core.Signature;
  import org.eclipse.jdt.core.dom.ASTNode;
  import org.eclipse.jdt.core.dom.Block;
  import org.eclipse.jdt.core.dom.StructuralPropertyDescriptor;
  import org.eclipse.jdt.core.dom.rewrite.ASTRewrite;
  import org.eclipse.jdt.core.dom.rewrite.ListRewrite;
  import org.eclipse.jdt.core.dom.rewrite.TargetSourceRangeComputer;
  import org.eclipse.text.edits.TextEditGroup;
  
  
  /**
   * Stores all rewrite events, descriptions of events and knows which nodes
   * are copy or move sources or tracked.
   */
  @SuppressWarnings({ "rawtypes", "unchecked" })
  public final class RewriteEventStore {
  
  	/**
  	 * Debug AST rewrite events.
  	 * <p>
  	 * If enabled, then {@link ASTRewrite} and {@link ListRewrite}
  	 * throw an {@link IllegalArgumentException} if a rewrite operation tries to insert an
  	 * AST node in a place where nodes of this type are not allowed (node type not a subtype of
  	 * the structural property's type). 
  	 * </p>
  	 * <p>
  	 * Disabled by default, since this hasn't been enforced from the beginning, and there are clients
  	 * (e.g. in JDT UI refactorings) that rely on a bit of leeway here.
  	 * E.g. the qualifier of a QualifiedName cannot be a MethodInvocation expression or a SimpleType, but
  	 * that's sometimes the easiest solution for such a change, and ASTRewrite has no problems with it.  
  	 * </p>
  	 */
  	public static boolean DEBUG = false;
  
  	public static final class PropertyLocation {
  		private final ASTNode parent;
  		private final StructuralPropertyDescriptor property;
  
  		public PropertyLocation(ASTNode parent, StructuralPropertyDescriptor property) {
  			this.parent= parent;
  			this.property= property;
  		}
  
  		public ASTNode getParent() {
  			return this.parent;
  		}
  
  		public StructuralPropertyDescriptor getProperty() {
  			return this.property;
  		}
  
  		@Override
  		public boolean equals(Object obj) {
  			if (obj != null && obj.getClass().equals(getClass())) {
  				PropertyLocation other= (PropertyLocation) obj;
  				return other.getParent().equals(getParent()) && other.getProperty().equals(getProperty());
  			}
  			return false;
  		}
  
  		@Override
  		public int hashCode() {
  			return getParent().hashCode() + getProperty().hashCode();
  		}
  
  	}
  
  	/**
  	 * Interface that allows to override the way how children are accessed from
  	 * a parent. Use this interface when the rewriter is set up on an already
  	 * modified AST's (as it is the case in the old ASTRewrite infrastructure)
  	 */
  	public static interface INodePropertyMapper {
  		/**
  		 * Returns the node attribute for a given property name.
  		 * @param parent The parent node
  		 * @param childProperty The child property to access
  		 * @return The child node at the given property location.
  		 */
  		Object getOriginalValue(ASTNode parent, StructuralPropertyDescriptor childProperty);
  	}
  
  	/*
  	 * Store element to associate event and node position/
  	 */
  	private static class EventHolder {
  		public final ASTNode parent;
  		public final StructuralPropertyDescriptor childProperty;
  		public final RewriteEvent event;
  
  		public EventHolder(ASTNode parent, StructuralPropertyDescriptor childProperty, RewriteEvent change) {
  			this.parent= parent;
  			this.childProperty= childProperty;
  			this.event= change;
  		}
  
  		@Override
  		public String toString() {
  			StringBuffer buf= new StringBuffer();
  			buf.append(this.parent).append(" - "); //$NON-NLS-1$
  			buf.append(this.childProperty.getId()).append(": "); //$NON-NLS-1$
  			buf.append(this.event).append('\n');
  			return buf.toString();
  		}
  	}
  
  	public static class CopySourceInfo implements Comparable {
  		public final PropertyLocation location; // can be null, only used to mark as removed on move
  		private final ASTNode node;
  		public final boolean isMove;
  
  		public CopySourceInfo(PropertyLocation location, ASTNode node, boolean isMove) {
  			this.location= location;
  			this.node= node;
  			this.isMove= isMove;
  		}
  
  		public ASTNode getNode() {
  			return this.node;
  		}
  
  		@Override
  		public int compareTo(Object o2) {
  			CopySourceInfo r2= (CopySourceInfo) o2;
  
  			int startDiff= getNode().getStartPosition() - r2.getNode().getStartPosition();
  			if (startDiff != 0) {
  				return startDiff; // insert before if start node is first
  			}
  
  			if (r2.isMove != this.isMove) {
  				return this.isMove ? -1 : 1; // first move then copy
  			}
  			return 0;
  		}
  
  		@Override
  		public String toString() {
  			StringBuffer buf= new StringBuffer();
  			if (this.isMove) {
  				buf.append("move source: "); //$NON-NLS-1$
  			} else {
  				buf.append("copy source: "); //$NON-NLS-1$
  			}
  			buf.append(this.node);
  			return buf.toString();
  		}
  	}
  
  	private static class NodeRangeInfo implements Comparable {
  		private final ASTNode first;
  		private final ASTNode last;
  		public final CopySourceInfo copyInfo; // containing the internal placeholder and the 'isMove' flag
  		public final ASTNode replacingNode;
  		public final TextEditGroup editGroup;
  
  		public NodeRangeInfo(ASTNode parent, StructuralPropertyDescriptor childProperty, ASTNode first, ASTNode last, CopySourceInfo copyInfo, ASTNode replacingNode, TextEditGroup editGroup) {
  			this.first= first;
  			this.last= last;
  			this.copyInfo= copyInfo;
  			this.replacingNode= replacingNode;
  			this.editGroup= editGroup;
  		}
  
  		public ASTNode getStartNode() {
  			return this.first;
  		}
  
  		public ASTNode getEndNode() {
  			return this.last;
  		}
  
  		public boolean isMove() {
  			return this.copyInfo.isMove;
  		}
  
  		public Block getInternalPlaceholder() {
  			return (Block) this.copyInfo.getNode();
  		}
  
  		@Override
  		public int compareTo(Object o2) {
  			NodeRangeInfo r2= (NodeRangeInfo) o2;
  
  			int startDiff= getStartNode().getStartPosition() - r2.getStartNode().getStartPosition();
  			if (startDiff != 0) {
  				return startDiff; // insert before if start node is first
  			}
  			int endDiff= getEndNode().getStartPosition() - r2.getEndNode().getStartPosition();
  			if (endDiff != 0) {
  				return -endDiff; // insert before if length is longer
  			}
  			if (r2.isMove() != isMove()) {
  				return isMove() ? -1 : 1; // first move then copy
  			}
  			return 0;
  		}
  
  		public void updatePlaceholderSourceRanges(TargetSourceRangeComputer sourceRangeComputer) {
  			TargetSourceRangeComputer.SourceRange startRange= sourceRangeComputer.computeSourceRange(getStartNode());
  			TargetSourceRangeComputer.SourceRange endRange= sourceRangeComputer.computeSourceRange(getEndNode());
  			int startPos= startRange.getStartPosition();
  			int endPos= endRange.getStartPosition() + endRange.getLength();
  
  			Block internalPlaceholder= getInternalPlaceholder();
  			internalPlaceholder.setSourceRange(startPos, endPos - startPos);
  		}
  
  		@Override
  		public String toString() {
  			StringBuffer buf= new StringBuffer();
  			if (this.first != this.last) {
  				buf.append("range ");  //$NON-NLS-1$
  			}
  			if (isMove()) {
  				buf.append("move source: "); //$NON-NLS-1$
  			} else {
  				buf.append("copy source: "); //$NON-NLS-1$
  			}
  			buf.append(this.first);
  			buf.append(" - "); //$NON-NLS-1$
  			buf.append(this.last);
  			return buf.toString();
  		}
  
  
  	}
  
  	/**
  	 * Iterates over all event parent nodes, tracked nodes and all copy/move sources
  	 */
  	private class ParentIterator implements Iterator {
  
  		private Iterator eventIter;
  		private Iterator sourceNodeIter;
  		private Iterator rangeNodeIter;
  		private Iterator trackedNodeIter;
  
  		public ParentIterator() {
  			this.eventIter= RewriteEventStore.this.eventLookup.keySet().iterator();
  			if (RewriteEventStore.this.nodeCopySources != null) {
  				this.sourceNodeIter= RewriteEventStore.this.nodeCopySources.iterator();
  			} else {
  				this.sourceNodeIter= Collections.EMPTY_LIST.iterator();
  			}
  			if (RewriteEventStore.this.nodeRangeInfos != null) {
  				this.rangeNodeIter= RewriteEventStore.this.nodeRangeInfos.keySet().iterator();
  			} else {
  				this.rangeNodeIter= Collections.EMPTY_LIST.iterator();
  			}
  			if (RewriteEventStore.this.trackedNodes != null) {
  				this.trackedNodeIter= RewriteEventStore.this.trackedNodes.keySet().iterator();
  			} else {
  				this.trackedNodeIter= Collections.EMPTY_LIST.iterator();
  			}
  		}
  
  		@Override
  		public boolean hasNext() {
  			return this.eventIter.hasNext() || this.sourceNodeIter.hasNext() || this.rangeNodeIter.hasNext() || this.trackedNodeIter.hasNext();
  		}
  
  		@Override
  		public Object next() {
  			if (this.eventIter.hasNext()) {
  				return this.eventIter.next();
  			}
  			if (this.sourceNodeIter.hasNext()) {
  				return ((CopySourceInfo) this.sourceNodeIter.next()).getNode();
  			}
  			if (this.rangeNodeIter.hasNext()) {
  				return ((PropertyLocation) this.rangeNodeIter.next()).getParent();
  			}
  			return this.trackedNodeIter.next();
  		}
  
  		@Override
  		public void remove() {
  			throw new UnsupportedOperationException();
  		}
  	}
  
  	public final static int NEW= 1;
  	public final static int ORIGINAL= 2;
  	public final static int BOTH= NEW | ORIGINAL;
  
  
  	/** all events by parent*/
  	final Map eventLookup;
  
  	/** cache for last accessed event */
  	private EventHolder lastEvent;
  
  	/** Maps events to group descriptions */
  	private Map editGroups;
  
  	/** Stores which nodes are source of a copy or move (list of CopySourceInfo)*/
  	List nodeCopySources;
  
  	/** Stores node ranges that are used to copy or move (map of <PropertyLocation, CopyRangeInfo>)*/
  	Map nodeRangeInfos;
  
  	/** Stores which nodes are tracked and the corresponding edit group*/
  	Map trackedNodes;
  
  	/** Stores which inserted nodes bound to the previous node. If not, a node is
  	 * always bound to the next node */
  	private Set insertBoundToPrevious;
  
  	/** optional mapper to allow fix already modified AST trees */
  	private INodePropertyMapper nodePropertyMapper;
  
  	private static final String INTERNAL_PLACEHOLDER_PROPERTY= "rewrite_internal_placeholder"; //$NON-NLS-1$
  
  	public RewriteEventStore() {
  		this.eventLookup= new HashMap();
  		this.lastEvent= null;
  
  		this.editGroups= null; // lazy initialization
  
  		this.trackedNodes= null;
  		this.insertBoundToPrevious= null;
  
  		this.nodePropertyMapper= null;
  		this.nodeCopySources= null;
  		this.nodeRangeInfos= null;
  	}
  
  	/**
  	 * Override the default way how to access children from a parent node.
  	 * @param nodePropertyMapper The new <code>INodePropertyMapper</code> or
  	 * <code>null</code>. to use the default.
  	 */
  	public void setNodePropertyMapper(INodePropertyMapper nodePropertyMapper) {
  		this.nodePropertyMapper= nodePropertyMapper;
  	}
  
  	public void clear() {
  		this.eventLookup.clear();
  		this.lastEvent= null;
  		this.trackedNodes= null;
  
  		this.editGroups= null; // lazy initialization
  		this.insertBoundToPrevious= null;
  		this.nodeCopySources= null;
  	}
  
  	public void addEvent(ASTNode parent, StructuralPropertyDescriptor childProperty, RewriteEvent event) {
  		validateHasChildProperty(parent, childProperty);
  
  		if (event.isListRewrite()) {
  			validateIsListProperty(childProperty);
  		}
  
  		EventHolder holder= new EventHolder(parent, childProperty, event);
  
  		List entriesList = (List) this.eventLookup.get(parent);
  		if (entriesList != null) {
  			for (int i= 0; i < entriesList.size(); i++) {
  				EventHolder curr= (EventHolder) entriesList.get(i);
  				if (curr.childProperty == childProperty) {
  					entriesList.set(i, holder);
  					this.lastEvent= null;
  					return;
  				}
  			}
  		} else {
  			entriesList= new ArrayList(3);
  			this.eventLookup.put(parent, entriesList);
  		}
  		entriesList.add(holder);
  	}
  
  	public RewriteEvent getEvent(ASTNode parent, StructuralPropertyDescriptor property) {
  		validateHasChildProperty(parent, property);
  
  		if (this.lastEvent != null && this.lastEvent.parent == parent && this.lastEvent.childProperty == property) {
  			return this.lastEvent.event;
  		}
  
  		List entriesList = (List) this.eventLookup.get(parent);
  		if (entriesList != null) {
  			for (int i= 0; i < entriesList.size(); i++) {
  				EventHolder holder= (EventHolder) entriesList.get(i);
  				if (holder.childProperty == property) {
  					this.lastEvent= holder;
  					return holder.event;
  				}
  			}
  		}
  		return null;
  	}
  
  	public NodeRewriteEvent getNodeEvent(ASTNode parent, StructuralPropertyDescriptor childProperty, boolean forceCreation) {
  		validateIsNodeProperty(childProperty);
  		NodeRewriteEvent event= (NodeRewriteEvent) getEvent(parent, childProperty);
  		if (event == null && forceCreation) {
  			Object originalValue= accessOriginalValue(parent, childProperty);
  			event= new NodeRewriteEvent(originalValue, originalValue);
  			addEvent(parent, childProperty, event);
  		}
  		return event;
  	}
  
  	public ListRewriteEvent getListEvent(ASTNode parent, StructuralPropertyDescriptor childProperty, boolean forceCreation) {
  		validateIsListProperty(childProperty);
  		ListRewriteEvent event= (ListRewriteEvent) getEvent(parent, childProperty);
  		if (event == null && forceCreation) {
  			List originalValue= (List) accessOriginalValue(parent, childProperty);
  			event= new ListRewriteEvent(originalValue);
  			addEvent(parent, childProperty, event);
  		}
  		return event;
  	}
  
  	public Iterator getChangeRootIterator() {
  		return new ParentIterator();
  	}
  
  
  	public boolean hasChangedProperties(ASTNode parent) {
  		List entriesList = (List) this.eventLookup.get(parent);
  		if (entriesList != null) {
  			for (int i= 0; i < entriesList.size(); i++) {
  				EventHolder holder= (EventHolder) entriesList.get(i);
  				if (holder.event.getChangeKind() != RewriteEvent.UNCHANGED) {
  					return true;
  				}
  			}
  		}
  		return false;
  	}
  
  	public PropertyLocation getPropertyLocation(Object value, int kind) {
  		for (Iterator iter= this.eventLookup.values().iterator(); iter.hasNext();) {
  			List events= (List) iter.next();
  			for (int i= 0; i < events.size(); i++) {
  				EventHolder holder= (EventHolder) events.get(i);
  				RewriteEvent event= holder.event;
  				if (isNodeInEvent(event, value, kind)) {
  					return new PropertyLocation(holder.parent, holder.childProperty);
  				}
  				if (event.isListRewrite()) {
  					RewriteEvent[] children= event.getChildren();
  					for (int k= 0; k < children.length; k++) {
  						if (isNodeInEvent(children[k], value, kind)) {
  							return new PropertyLocation(holder.parent, holder.childProperty);
  						}
  					}
  				}
  			}
  		}
  		if (value instanceof ASTNode) {
  			ASTNode node= (ASTNode) value;
  			return new PropertyLocation(node.getParent(), node.getLocationInParent());
  		}
  		return null;
  	}
  
  
  	/**
  	 * Kind is either ORIGINAL, NEW, or BOTH
  	 * @param value
  	 * @param kind
  	 * @return Returns the event with the given value of <code>null</code>.
  	 */
  	public RewriteEvent findEvent(Object value, int kind) {
  		for (Iterator iter= this.eventLookup.values().iterator(); iter.hasNext();) {
  			List events= (List) iter.next();
  			for (int i= 0; i < events.size(); i++) {
  				RewriteEvent event= ((EventHolder) events.get(i)).event;
  				if (isNodeInEvent(event, value, kind)) {
  					return event;
  				}
  				if (event.isListRewrite()) {
  					RewriteEvent[] children= event.getChildren();
  					for (int k= 0; k < children.length; k++) {
  						if (isNodeInEvent(children[k], value, kind)) {
  							return children[k];
  						}
  					}
  				}
  			}
  		}
  		return null;
  	}
  
  	private boolean isNodeInEvent(RewriteEvent event, Object value, int kind) {
  		if (((kind & NEW) != 0) && event.getNewValue() == value) {
  			return true;
  		}
  		if (((kind & ORIGINAL) != 0) && event.getOriginalValue() == value) {
  			return true;
  		}
  		return false;
  	}
  
  
  	public Object getOriginalValue(ASTNode parent, StructuralPropertyDescriptor property) {
  		RewriteEvent event= getEvent(parent, property);
  		if (event != null) {
  			return event.getOriginalValue();
  		}
  		return accessOriginalValue(parent, property);
  	}
  
  	public Object getNewValue(ASTNode parent, StructuralPropertyDescriptor property) {
  		RewriteEvent event= getEvent(parent, property);
  		if (event != null) {
  			return event.getNewValue();
  		}
  		return accessOriginalValue(parent, property);
  	}
  	
  	public List getChangedPropertieEvents(ASTNode parent) {
  		List changedPropertiesEvent = new ArrayList();
  		
  		List entriesList = (List) this.eventLookup.get(parent);
  		if (entriesList != null) {
  			for (int i= 0; i < entriesList.size(); i++) {
  				EventHolder holder= (EventHolder) entriesList.get(i);
  				if (holder.event.getChangeKind() != RewriteEvent.UNCHANGED) {
  					changedPropertiesEvent.add(holder.event);
  				}
  			}
  		}
  		return changedPropertiesEvent;
  	}
  
  	public int getChangeKind(ASTNode node) {
  		RewriteEvent event= findEvent(node, ORIGINAL);
  		if (event != null) {
  			return event.getChangeKind();
  		}
  		return RewriteEvent.UNCHANGED;
  	}
  
  	/*
  	 * Gets an original child from the AST.
  	 * Temporarily overridden to port the old rewriter to the new infrastructure.
  	 */
  	private Object accessOriginalValue(ASTNode parent, StructuralPropertyDescriptor childProperty) {
  		if (this.nodePropertyMapper != null) {
  			return this.nodePropertyMapper.getOriginalValue(parent, childProperty);
  		}
  
  		return parent.getStructuralProperty(childProperty);
  	}
  
  	public TextEditGroup getEventEditGroup(RewriteEvent event) {
  		if (this.editGroups == null) {
  			return null;
  		}
  		return (TextEditGroup) this.editGroups.get(event);
  	}
  
  	public void setEventEditGroup(RewriteEvent event, TextEditGroup editGroup) {
  		if (this.editGroups == null) {
  			this.editGroups= new IdentityHashMap(5);
  		}
  		this.editGroups.put(event, editGroup);
  	}
  
  
  	public final TextEditGroup getTrackedNodeData(ASTNode node) {
  		if (this.trackedNodes != null) {
  			return (TextEditGroup) this.trackedNodes.get(node);
  		}
  		return null;
  	}
  
  	public void setTrackedNodeData(ASTNode node, TextEditGroup editGroup) {
  		if (this.trackedNodes == null) {
  			this.trackedNodes= new IdentityHashMap();
  		}
  		this.trackedNodes.put(node, editGroup);
  	}
  
  	/**
  	 * Marks a node as tracked. The edits added to the group editGroup can be used to get the
  	 * position of the node after the rewrite operation.
  	 * @param node The node to track
  	 * @param editGroup Collects the range markers describing the node position.
  	 */
  	public final void markAsTracked(ASTNode node, TextEditGroup editGroup) {
  		if (getTrackedNodeData(node) != null) {
  			throw new IllegalArgumentException("Node is already marked as tracked"); //$NON-NLS-1$
  		}
  		setTrackedNodeData(node, editGroup);
  	}
  
  	private final CopySourceInfo createCopySourceInfo(PropertyLocation location, ASTNode node, boolean isMove) {
  		CopySourceInfo copySource= new CopySourceInfo(location, node, isMove);
  
  		if (this.nodeCopySources == null) {
  			this.nodeCopySources= new ArrayList();
  		}
  		this.nodeCopySources.add(copySource);
  		return copySource;
  	}
  
  	public final CopySourceInfo markAsCopySource(ASTNode parent, StructuralPropertyDescriptor property, ASTNode node, boolean isMove) {
  		return createCopySourceInfo(new PropertyLocation(parent, property), node, isMove);
  	}
  
  	public final boolean isRangeCopyPlaceholder(ASTNode node) {
  		return node.getProperty(INTERNAL_PLACEHOLDER_PROPERTY) != null;
  	}
  
  	public final CopySourceInfo createRangeCopy(ASTNode parent, StructuralPropertyDescriptor childProperty, ASTNode first, ASTNode last, boolean isMove, ASTNode internalPlaceholder, ASTNode replacingNode, TextEditGroup editGroup) {
  		CopySourceInfo copyInfo= createCopySourceInfo(null, internalPlaceholder, isMove);
  		internalPlaceholder.setProperty(INTERNAL_PLACEHOLDER_PROPERTY, internalPlaceholder);
  
  		NodeRangeInfo copyRangeInfo= new NodeRangeInfo(parent, childProperty, first, last, copyInfo, replacingNode, editGroup);
  
  		ListRewriteEvent listEvent= getListEvent(parent, childProperty, true);
  
  		int indexFirst= listEvent.getIndex(first, ListRewriteEvent.OLD);
  		if (indexFirst == -1) {
  			throw new IllegalArgumentException("Start node is not a original child of the given list"); //$NON-NLS-1$
  		}
  		int indexLast= listEvent.getIndex(last, ListRewriteEvent.OLD);
  		if (indexLast == -1) {
  			throw new IllegalArgumentException("End node is not a original child of the given list"); //$NON-NLS-1$
  		}
  
  		if (indexFirst > indexLast) {
  			throw new IllegalArgumentException("Start node must be before end node"); //$NON-NLS-1$
  		}
  
  		if (this.nodeRangeInfos == null) {
  			this.nodeRangeInfos= new HashMap();
  		}
  		PropertyLocation loc= new PropertyLocation(parent, childProperty);
  		List innerList= (List) this.nodeRangeInfos.get(loc);
  		if (innerList == null) {
  