core/plugins/org.eclipse.dltk.core/model/org/eclipse/dltk/internal/core/hierarchy/IndexBasedHierarchyBuilder.java - dltk/org.eclipse.dltk.core - Git at Google

 /*******************************************************************************
  * Copyright (c) 2000, 2017 IBM Corporation and others.
  * This program and the accompanying materials are made available under the
  * terms of the Eclipse Public License v. 2.0 which is available at
  * http://www.eclipse.org/legal/epl-2.0.
  *
  * SPDX-License-Identifier: EPL-2.0
  *
  *******************************************************************************/
 package org.eclipse.dltk.internal.core.hierarchy;

 import java.util.ArrayList;
 import java.util.Arrays;
 import java.util.HashMap;
 import java.util.HashSet;
 import java.util.Iterator;
 import java.util.Map;

 import org.eclipse.core.resources.IFile;
 import org.eclipse.core.runtime.IProgressMonitor;
 import org.eclipse.core.runtime.SubProgressMonitor;
 import org.eclipse.dltk.compiler.CharOperation;
 import org.eclipse.dltk.compiler.util.HashtableOfObject;
 import org.eclipse.dltk.compiler.util.HashtableOfObjectToInt;
 import org.eclipse.dltk.core.IModelElement;
 import org.eclipse.dltk.core.IProjectFragment;
 import org.eclipse.dltk.core.IScriptProject;
 import org.eclipse.dltk.core.ISearchableEnvironment;
 import org.eclipse.dltk.core.ISourceModule;
 import org.eclipse.dltk.core.IType;
 import org.eclipse.dltk.core.ModelException;
 import org.eclipse.dltk.core.search.DLTKSearchParticipant;
 import org.eclipse.dltk.core.search.IDLTKSearchConstants;
 import org.eclipse.dltk.core.search.IDLTKSearchScope;
 import org.eclipse.dltk.core.search.SearchParticipant;
 import org.eclipse.dltk.core.search.SearchPattern;
 import org.eclipse.dltk.core.search.indexing.IIndexConstants;
 import org.eclipse.dltk.core.search.indexing.IndexManager;
 import org.eclipse.dltk.core.search.matching.MatchLocator;
 import org.eclipse.dltk.internal.compiler.env.AccessRuleSet;
 import org.eclipse.dltk.internal.core.IPathRequestor;
 import org.eclipse.dltk.internal.core.Member;
 import org.eclipse.dltk.internal.core.ModelManager;
 import org.eclipse.dltk.internal.core.Openable;
 import org.eclipse.dltk.internal.core.ScriptProject;
 import org.eclipse.dltk.internal.core.search.IndexQueryRequestor;
 import org.eclipse.dltk.internal.core.search.SubTypeSearchJob;
 import org.eclipse.dltk.internal.core.search.matching.SuperTypeReferencePattern;
 import org.eclipse.dltk.internal.core.util.HandleFactory;

 public class IndexBasedHierarchyBuilder extends HierarchyBuilder {
 	public static final int MAXTICKS = 800; // heuristic so that there still
 											// progress for deep hierachies
 	/**
 	 * A temporary cache of compilation units to handles to speed info to handle
 	 * translation - it only contains the entries for the types in the region
 	 * (in other words, it contains no supertypes outside the region).
 	 */
 	protected Map cuToHandle;

 	/**
 	 * The scope this hierarchy builder should restrain results to.
 	 */
 	protected IDLTKSearchScope scope;

 	/**
 	 * Cache used to record binaries recreated from index matches
 	 */
 	protected Map binariesFromIndexMatches;

 	/**
 	 * Collection used to queue subtype index queries
 	 */
 	static class Queue {
 		public char[][] names = new char[10][];
 		public int start = 0;
 		public int end = -1;

 		public void add(char[] name) {
 			if (++this.end == this.names.length) {
 				this.end -= this.start;
 				System.arraycopy(this.names, this.start,
 						this.names = new char[this.end * 2][], 0, this.end);
 				this.start = 0;
 			}
 			this.names[this.end] = name;
 		}

 		public char[] retrieve() {
 			if (this.start > this.end) {
 				return null; // none
 			}

 			char[] name = this.names[this.start++];
 			if (this.start > this.end) {
 				this.start = 0;
 				this.end = -1;
 			}
 			return name;
 		}

 		@Override
 		public String toString() {
 			StringBuffer buffer = new StringBuffer("Queue:\n"); //$NON-NLS-1$
 			for (int i = this.start; i <= this.end; i++) {
 				buffer.append(this.names[i]).append('\n');
 			}
 			return buffer.toString();
 		}
 	}

 	public IndexBasedHierarchyBuilder(TypeHierarchy hierarchy,
 			IDLTKSearchScope scope) throws ModelException {
 		super();
 		setRequestor(hierarchy);
 		this.cuToHandle = new HashMap(5);
 		this.binariesFromIndexMatches = new HashMap(10);
 		this.scope = scope;
 	}

 	@Override
 	public void build(boolean computeSubtypes) {
 		ModelManager manager = ModelManager.getModelManager();
 		try {
 			// optimize access to zip files while building hierarchy
 			manager.cacheZipFiles();

 			if (computeSubtypes) {
 				// Note by construction there always is a focus type here
 				IType focusType = getType();
 				boolean focusIsObject = focusType.getElementName().equals(
 						new String(IIndexConstants.OBJECT));
 				int amountOfWorkForSubtypes = focusIsObject ? 5 : 80; // percentage
 																		// of
 																		// work
 																		// needed
 																		// to
 																		// get
 																		// possible
 																		// subtypes
 				IProgressMonitor possibleSubtypesMonitor = this.hierarchy.progressMonitor == null ? null
 						: new SubProgressMonitor(
 								this.hierarchy.progressMonitor,
 								amountOfWorkForSubtypes);
 				HashSet localTypes = new HashSet(10); // contains the paths
 														// that have potential
 														// subtypes that are
 														// local/anonymous types
 				String[] allPossibleSubtypes;
 				if (((Member) focusType).getOuterMostLocalContext() == null) {
 					// top level or member type
 					allPossibleSubtypes = this.determinePossibleSubTypes(
 							localTypes, possibleSubtypesMonitor);
 				} else {
 					// local or anonymous type
 					allPossibleSubtypes = CharOperation.NO_STRINGS;
 				}
 				if (allPossibleSubtypes != null) {
 					IProgressMonitor buildMonitor = this.hierarchy.progressMonitor == null ? null
 							: new SubProgressMonitor(
 									this.hierarchy.progressMonitor,
 									100 - amountOfWorkForSubtypes);
 					this.hierarchy.initialize(allPossibleSubtypes.length);
 					buildFromPotentialSubtypes(allPossibleSubtypes, localTypes,
 							buildMonitor);
 				}
 			} else {
 				this.hierarchy.initialize(1);
 				this.buildSupertypes();
 			}
 		} finally {
 			manager.flushZipFiles();
 		}
 	}

 	private void buildForProject(ScriptProject project,
 			ArrayList potentialSubtypes,
 			org.eclipse.dltk.core.ISourceModule[] workingCopies,
 			HashSet localTypes, IProgressMonitor monitor) throws ModelException {
 		// resolve
 		int openablesLength = potentialSubtypes.size();
 		if (openablesLength > 0) {
 			// copy vectors into arrays
 			Openable[] openables = new Openable[openablesLength];
 			potentialSubtypes.toArray(openables);

 			// sort in the order of roots and in reverse alphabetical order for
 			// .class file
 			// since requesting top level types in the process of caching an
 			// enclosing type is
 			// not supported by the lookup environment
 			IProjectFragment[] roots = project.getProjectFragments();
 			int rootsLength = roots.length;
 			final HashtableOfObjectToInt indexes = new HashtableOfObjectToInt(
 					openablesLength);
 			for (int i = 0; i < openablesLength; i++) {
 				IModelElement root = openables[i]
 						.getAncestor(IModelElement.PROJECT_FRAGMENT);
 				int index;
 				for (index = 0; index < rootsLength; index++) {
 					if (roots[index].equals(root)) {
 						break;
 					}
 				}
 				indexes.put(openables[i], index);
 			}
 			Arrays.sort(openables, (a, b) -> {
 				int aIndex = indexes.get(a);
 				int bIndex = indexes.get(b);
 				if (aIndex != bIndex) {
 					return aIndex - bIndex;
 				}
 				return b.getElementName()
 						.compareTo(a.getElementName());
 			});

 			IType focusType = this.getType();
 			boolean inProjectOfFocusType = focusType != null
 					&& focusType.getScriptProject().equals(project);
 			org.eclipse.dltk.core.ISourceModule[] unitsToLookInside = null;
 			if (inProjectOfFocusType) {
 				org.eclipse.dltk.core.ISourceModule unitToLookInside = focusType
 						.getSourceModule();
 				if (unitToLookInside != null) {
 					int wcLength = workingCopies == null ? 0
 							: workingCopies.length;
 					if (wcLength == 0) {
 						unitsToLookInside = new org.eclipse.dltk.core.ISourceModule[] { unitToLookInside };
 					} else {
 						unitsToLookInside = new org.eclipse.dltk.core.ISourceModule[wcLength + 1];
 						unitsToLookInside[0] = unitToLookInside;
 						System.arraycopy(workingCopies, 0, unitsToLookInside,
 								1, wcLength);
 					}
 				} else {
 					unitsToLookInside = workingCopies;
 				}
 			}

 			ISearchableEnvironment searchableEnvironment = project
 					.newSearchableNameEnvironment(unitsToLookInside);
 			this.nameLookup = searchableEnvironment.getNameLookup();
 //			Map options = project.getOptions(true);
 			// disable task tags to speed up parsing
 			// options.put(DLTKCore.COMPILER_TASK_TAGS, ""); //$NON-NLS-1$
 			this.hierarchyResolver = new HierarchyResolver(this);
 				//	searchableEnvironment, options, this,
 					//new DefaultProblemFactory());

 			if (focusType != null) {
 				Member declaringMember = ((Member) focusType)
 						.getOuterMostLocalContext();
 				if (declaringMember == null) {
 					// top level or member type
 //					if (!inProjectOfFocusType) {
 //						char[] typeQualifiedName = focusType
 //								.getTypeQualifiedName('.').toCharArray();
 //						String[] packageName = ((PackageFragment) focusType
 //								.getPackageFragment()).names;
 //						if (searchableEnvironment.findType(typeQualifiedName,
 //								Util.toCharArrays(packageName)) == null) {
 //							// focus type is not visible in this project: no
 //							// need to go further
 //							return;
 //						}
 //					}
 				} else {
 					// local or anonymous type
 					Openable openable;
 					openable = (Openable) declaringMember.getSourceModule();
 					localTypes = new HashSet();
 					localTypes.add(openable.getPath().toString());
 					this.hierarchyResolver.resolve(new Openable[] { openable }, localTypes);
 					return;
 				}
 			}
 			this.hierarchyResolver.resolve(openables, localTypes);
 		}
 	}

 	/**
 	 * Configure this type hierarchy based on the given potential subtypes.
 	 */
 	private void buildFromPotentialSubtypes(String[] allPotentialSubTypes,
 			HashSet localTypes, IProgressMonitor monitor) {
 		IType focusType = this.getType();

 		// substitute compilation units with working copies
 		HashMap wcPaths = new HashMap(); // a map from path to working copies
 		int wcLength;
 		org.eclipse.dltk.core.ISourceModule[] workingCopies = this.hierarchy.workingCopies;
 		if (workingCopies != null && (wcLength = workingCopies.length) > 0) {
 			String[] newPaths = new String[wcLength];
 			for (int i = 0; i < wcLength; i++) {
 				org.eclipse.dltk.core.ISourceModule workingCopy = workingCopies[i];
 				String path = workingCopy.getPath().toString();
 				wcPaths.put(path, workingCopy);
 				newPaths[i] = path;
 			}
 			int potentialSubtypesLength = allPotentialSubTypes.length;
 			System.arraycopy(allPotentialSubTypes, 0,
 					allPotentialSubTypes = new String[potentialSubtypesLength
 							+ wcLength], 0, potentialSubtypesLength);
 			System.arraycopy(newPaths, 0, allPotentialSubTypes,
 					potentialSubtypesLength, wcLength);
 		}

 		int length = allPotentialSubTypes.length;

 		// inject the compilation unit of the focus type (so that types in
 		// this cu have special visibility permission (this is also usefull
 		// when the cu is a working copy)
 		Openable focusCU = (Openable) focusType.getSourceModule();
 		String focusPath = null;
 		if (focusCU != null) {
 			focusPath = focusCU.getPath().toString();
 			if (length > 0) {
 				System.arraycopy(allPotentialSubTypes, 0,
 						allPotentialSubTypes = new String[length + 1], 0,
 						length);
 				allPotentialSubTypes[length] = focusPath;
 			} else {
 				allPotentialSubTypes = new String[] { focusPath };
 			}
 			length++;
 		}

 		/*
 		 * Sort in alphabetical order so that potential subtypes are grouped per
 		 * project
 		 */
 		Arrays.sort(allPotentialSubTypes);

 		ArrayList potentialSubtypes = new ArrayList();
 		try {
 			// create element infos for subtypes
 			HandleFactory factory = new HandleFactory();
 			IScriptProject currentProject = null;
 			if (monitor != null) {
 				monitor.beginTask("", length * 2); //$NON-NLS-1$ // 1 for build binding, 1 for connect hierarchy
 			}
 			for (int i = 0; i < length; i++) {
 				try {
 					String resourcePath = allPotentialSubTypes[i];

 					// skip duplicate paths (e.g. if focus path was injected
 					// when it was already a potential subtype)
 					if (i > 0
 							&& resourcePath.equals(allPotentialSubTypes[i - 1])) {
 						continue;
 					}

 					Openable handle;
 					org.eclipse.dltk.core.ISourceModule workingCopy = (org.eclipse.dltk.core.ISourceModule) wcPaths
 							.get(resourcePath);
 					if (workingCopy != null) {
 						handle = (Openable) workingCopy;
 					} else {
 						handle = resourcePath.equals(focusPath) ? focusCU
 								: factory.createOpenable(resourcePath,
 										this.scope);
 						if (handle == null) {
 							continue; // match is outside classpath
 						}
 					}

 					IScriptProject project = handle.getScriptProject();
 					if (currentProject == null) {
 						currentProject = project;
 						potentialSubtypes = new ArrayList(5);
 					} else if (!currentProject.equals(project)) {
 						// build current project
 						this.buildForProject((ScriptProject) currentProject,
 								potentialSubtypes, workingCopies, localTypes,
 								monitor);
 						currentProject = project;
 						potentialSubtypes = new ArrayList(5);
 					}

 					potentialSubtypes.add(handle);
 				} catch (ModelException e) {
 					continue;
 				}
 			}

 			// build last project
 			try {
 				if (currentProject == null) {
 					// case of no potential subtypes
 					currentProject = focusType.getScriptProject();
 					potentialSubtypes.add(focusType.getSourceModule());
 				}
 				this.buildForProject((ScriptProject) currentProject,
 						potentialSubtypes, workingCopies, localTypes, monitor);
 			} catch (ModelException e) {
 				// ignore
 			}

 			// Compute hierarchy of focus type if not already done (case of a
 			// type with potential subtypes that are not real subtypes)
 			if (!this.hierarchy.contains(focusType)) {
 				try {
 					currentProject = focusType.getScriptProject();
 					potentialSubtypes = new ArrayList();
 					potentialSubtypes.add(focusType.getSourceModule());

 					this.buildForProject((ScriptProject) currentProject,
 							potentialSubtypes, workingCopies, localTypes,
 							monitor);
 				} catch (ModelException e) {
 					// ignore
 				}
 			}

 			// Add focus if not already in (case of a type with no explicit
 			// super type)
 //			if (!this.hierarchy.contains(focusType)) {
 //				this.hierarchy.addRootClass(focusType);
 //			}
 		} finally {
 			if (monitor != null) {
 				monitor.done();
 			}
 		}
 	}

 	@Override
 	protected ISourceModule createCompilationUnitFromPath(Openable handle,
 			IFile file) {
 		ISourceModule unit = super.createCompilationUnitFromPath(handle,
 				file);
 		this.cuToHandle.put(unit, handle);
 		return unit;
 	}

 	/**
 	 * Returns all of the possible subtypes of this type hierarchy. Returns null
 	 * if they could not be determine.
 	 */
 	protected String[] determinePossibleSubTypes(final HashSet localTypes,
 			IProgressMonitor monitor) {

 		class PathCollector implements IPathRequestor {
 			HashSet paths = new HashSet(10);

 			@Override
 			public void acceptPath(String path, boolean containsLocalTypes) {
 				this.paths.add(path);
 				if (containsLocalTypes) {
 					localTypes.add(path);
 				}
 			}
 		}
 		PathCollector collector = new PathCollector();

 		try {
 			if (monitor != null) {
 				monitor.beginTask("", MAXTICKS); //$NON-NLS-1$
 			}
 			searchAllPossibleSubTypes(this.getType(), this.scope,
 					this.binariesFromIndexMatches, collector,
 					IDLTKSearchConstants.WAIT_UNTIL_READY_TO_SEARCH, monitor);
 		} finally {
 			if (monitor != null) {
 				monitor.done();
 			}
 		}

 		HashSet paths = collector.paths;
 		int length = paths.size();
 		String[] result = new String[length];
 		int count = 0;
 		for (Iterator iter = paths.iterator(); iter.hasNext();) {
 			result[count++] = (String) iter.next();
 		}
 		return result;
 	}

 	/**
 	 * Find the set of candidate subtypes of a given type.
 	 *
 	 * The requestor is notified of super type references (with actual path of
 	 * its occurrence) for all types which are potentially involved inside a
 	 * particular hierarchy. The match locator is not used here to narrow down
 	 * the results, the type hierarchy resolver is rather used to compute the
 	 * whole hierarchy at once.
 	 *
 	 * @param type
 	 * @param scope
 	 * @param binariesFromIndexMatches
 	 * @param pathRequestor
 	 * @param waitingPolicy
 	 * @param progressMonitor
 	 */
 	public static void searchAllPossibleSubTypes(IType type,
 			IDLTKSearchScope scope, final Map binariesFromIndexMatches,
 			final IPathRequestor pathRequestor, int waitingPolicy, // WaitUntilReadyToSearch
 																	// |
 																	// ForceImmediateSearch
 																	// |
 																	// CancelIfNotReadyToSearch
 			IProgressMonitor progressMonitor) {

 		/*
 		 * embed constructs inside arrays so as to pass them to (inner)
 		 * collector
 		 */
 		final Queue queue = new Queue();
 		final HashtableOfObject foundSuperNames = new HashtableOfObject(5);

 		IndexManager indexManager = ModelManager.getModelManager()
 				.getIndexManager();

 		/* use a special collector to collect paths and queue new subtype names */
 		IndexQueryRequestor searchRequestor = new IndexQueryRequestor() {
 			@Override
 			public boolean acceptIndexMatch(String documentPath,
 					SearchPattern indexRecord, SearchParticipant participant,
 					AccessRuleSet access) {
 				SuperTypeReferencePattern record = (SuperTypeReferencePattern) indexRecord;
 				boolean isLocalOrAnonymous = record.enclosingTypeName == IIndexConstants.ONE_ZERO;
 				pathRequestor.acceptPath(documentPath, isLocalOrAnonymous);
 				char[] typeName = record.simpleName;

 				if (!isLocalOrAnonymous // local or anonymous types cannot have
 										// subtypes outside the cu that define
 										// them
 						&& !foundSuperNames.containsKey(typeName)) {
 					foundSuperNames.put(typeName, typeName);
 					queue.add(typeName);
 				}
 				return true;
 			}
 		};

 		int superRefKind;
 		superRefKind = SuperTypeReferencePattern.ALL_SUPER_TYPES;
 		SuperTypeReferencePattern pattern = new SuperTypeReferencePattern(null,
 				null, superRefKind, SearchPattern.R_EXACT_MATCH
 						| SearchPattern.R_CASE_SENSITIVE, scope.getLanguageToolkit());
 		MatchLocator.setFocus(pattern, type);
 		SubTypeSearchJob job = new SubTypeSearchJob(pattern,
 				new DLTKSearchParticipant(), // java search only
 				scope, searchRequestor);

 		int ticks = 0;
 		queue.add(type.getElementName().toCharArray());
 		try {
 			while (queue.start <= queue.end) {
 				if (progressMonitor != null && progressMonitor.isCanceled()) {
 					return;
 				}

 				// all subclasses of OBJECT are actually all types
 				char[] currentTypeName = queue.retrieve();
 				if (CharOperation.equals(currentTypeName,
 						IIndexConstants.OBJECT)) {
 					currentTypeName = null;
 				}

 				// search all index references to a given supertype
 				pattern.superSimpleName = currentTypeName;
 				indexManager.performConcurrentJob(job, waitingPolicy, null); // no
 																				// sub
 																				// progress
 																				// monitor
 																				// since
 																				// its
 																				// too
 																				// costly
 																				// for
 																				// deep
 																				// hierarchies
 				if (progressMonitor != null && ++ticks <= MAXTICKS) {
 					progressMonitor.worked(1);
 				}

 				// in case, we search all subtypes, no need to search further
 				if (currentTypeName == null) {
 					break;
 				}
 			}
 		} finally {
 			job.finished();
 		}
 	}
 }
	/*******************************************************************************
	* Copyright (c) 2000, 2017 IBM Corporation and others.
	* This program and the accompanying materials are made available under the
	* terms of the Eclipse Public License v. 2.0 which is available at
	* http://www.eclipse.org/legal/epl-2.0.
	*
	* SPDX-License-Identifier: EPL-2.0
	*
	*******************************************************************************/
	package org.eclipse.dltk.internal.core.hierarchy;

	import java.util.ArrayList;
	import java.util.Arrays;
	import java.util.HashMap;
	import java.util.HashSet;
	import java.util.Iterator;
	import java.util.Map;

	import org.eclipse.core.resources.IFile;
	import org.eclipse.core.runtime.IProgressMonitor;
	import org.eclipse.core.runtime.SubProgressMonitor;
	import org.eclipse.dltk.compiler.CharOperation;
	import org.eclipse.dltk.compiler.util.HashtableOfObject;
	import org.eclipse.dltk.compiler.util.HashtableOfObjectToInt;
	import org.eclipse.dltk.core.IModelElement;
	import org.eclipse.dltk.core.IProjectFragment;
	import org.eclipse.dltk.core.IScriptProject;
	import org.eclipse.dltk.core.ISearchableEnvironment;
	import org.eclipse.dltk.core.ISourceModule;
	import org.eclipse.dltk.core.IType;
	import org.eclipse.dltk.core.ModelException;
	import org.eclipse.dltk.core.search.DLTKSearchParticipant;
	import org.eclipse.dltk.core.search.IDLTKSearchConstants;
	import org.eclipse.dltk.core.search.IDLTKSearchScope;
	import org.eclipse.dltk.core.search.SearchParticipant;
	import org.eclipse.dltk.core.search.SearchPattern;
	import org.eclipse.dltk.core.search.indexing.IIndexConstants;
	import org.eclipse.dltk.core.search.indexing.IndexManager;
	import org.eclipse.dltk.core.search.matching.MatchLocator;
	import org.eclipse.dltk.internal.compiler.env.AccessRuleSet;
	import org.eclipse.dltk.internal.core.IPathRequestor;
	import org.eclipse.dltk.internal.core.Member;
	import org.eclipse.dltk.internal.core.ModelManager;
	import org.eclipse.dltk.internal.core.Openable;
	import org.eclipse.dltk.internal.core.ScriptProject;
	import org.eclipse.dltk.internal.core.search.IndexQueryRequestor;
	import org.eclipse.dltk.internal.core.search.SubTypeSearchJob;
	import org.eclipse.dltk.internal.core.search.matching.SuperTypeReferencePattern;
	import org.eclipse.dltk.internal.core.util.HandleFactory;

	public class IndexBasedHierarchyBuilder extends HierarchyBuilder {
	public static final int MAXTICKS = 800; // heuristic so that there still
	// progress for deep hierachies
	/**
	* A temporary cache of compilation units to handles to speed info to handle
	* translation - it only contains the entries for the types in the region
	* (in other words, it contains no supertypes outside the region).
	*/
	protected Map cuToHandle;

	/**
	* The scope this hierarchy builder should restrain results to.
	*/
	protected IDLTKSearchScope scope;

	/**
	* Cache used to record binaries recreated from index matches
	*/
	protected Map binariesFromIndexMatches;

	/**
	* Collection used to queue subtype index queries
	*/
	static class Queue {
	public char[][] names = new char[10][];
	public int start = 0;
	public int end = -1;

	public void add(char[] name) {
	if (++this.end == this.names.length) {
	this.end -= this.start;
	System.arraycopy(this.names, this.start,
	this.names = new char[this.end * 2][], 0, this.end);
	this.start = 0;
	}
	this.names[this.end] = name;
	}

	public char[] retrieve() {
	if (this.start > this.end) {
	return null; // none
	}

	char[] name = this.names[this.start++];
	if (this.start > this.end) {
	this.start = 0;
	this.end = -1;
	}
	return name;
	}

	@Override
	public String toString() {
	StringBuffer buffer = new StringBuffer("Queue:\n"); //$NON-NLS-1$
	for (int i = this.start; i <= this.end; i++) {
	buffer.append(this.names[i]).append('\n');
	}
	return buffer.toString();
	}
	}

	public IndexBasedHierarchyBuilder(TypeHierarchy hierarchy,
	IDLTKSearchScope scope) throws ModelException {
	super();
	setRequestor(hierarchy);
	this.cuToHandle = new HashMap(5);
	this.binariesFromIndexMatches = new HashMap(10);
	this.scope = scope;
	}

	@Override
	public void build(boolean computeSubtypes) {
	ModelManager manager = ModelManager.getModelManager();
	try {
	// optimize access to zip files while building hierarchy
	manager.cacheZipFiles();

	if (computeSubtypes) {
	// Note by construction there always is a focus type here
	IType focusType = getType();
	boolean focusIsObject = focusType.getElementName().equals(
	new String(IIndexConstants.OBJECT));
	int amountOfWorkForSubtypes = focusIsObject ? 5 : 80; // percentage
	// of
	// work
	// needed
	// to
	// get
	// possible
	// subtypes
	IProgressMonitor possibleSubtypesMonitor = this.hierarchy.progressMonitor == null ? null
	: new SubProgressMonitor(
	this.hierarchy.progressMonitor,
	amountOfWorkForSubtypes);
	HashSet localTypes = new HashSet(10); // contains the paths
	// that have potential
	// subtypes that are
	// local/anonymous types
	String[] allPossibleSubtypes;
	if (((Member) focusType).getOuterMostLocalContext() == null) {
	// top level or member type
	allPossibleSubtypes = this.determinePossibleSubTypes(
	localTypes, possibleSubtypesMonitor);
	} else {
	// local or anonymous type
	allPossibleSubtypes = CharOperation.NO_STRINGS;
	}
	if (allPossibleSubtypes != null) {
	IProgressMonitor buildMonitor = this.hierarchy.progressMonitor == null ? null
	: new SubProgressMonitor(
	this.hierarchy.progressMonitor,
	100 - amountOfWorkForSubtypes);
	this.hierarchy.initialize(allPossibleSubtypes.length);
	buildFromPotentialSubtypes(allPossibleSubtypes, localTypes,
	buildMonitor);
	}
	} else {
	this.hierarchy.initialize(1);
	this.buildSupertypes();
	}
	} finally {
	manager.flushZipFiles();
	}
	}

	private void buildForProject(ScriptProject project,
	ArrayList potentialSubtypes,
	org.eclipse.dltk.core.ISourceModule[] workingCopies,
	HashSet localTypes, IProgressMonitor monitor) throws ModelException {
	// resolve
	int openablesLength = potentialSubtypes.size();
	if (openablesLength > 0) {
	// copy vectors into arrays
	Openable[] openables = new Openable[openablesLength];
	potentialSubtypes.toArray(openables);

	// sort in the order of roots and in reverse alphabetical order for
	// .class file
	// since requesting top level types in the process of caching an
	// enclosing type is
	// not supported by the lookup environment
	IProjectFragment[] roots = project.getProjectFragments();
	int rootsLength = roots.length;
	final HashtableOfObjectToInt indexes = new HashtableOfObjectToInt(
	openablesLength);
	for (int i = 0; i < openablesLength; i++) {
	IModelElement root = openables[i]
	.getAncestor(IModelElement.PROJECT_FRAGMENT);
	int index;
	for (index = 0; index < rootsLength; index++) {
	if (roots[index].equals(root)) {
	break;
	}
	}
	indexes.put(openables[i], index);
	}
	Arrays.sort(openables, (a, b) -> {
	int aIndex = indexes.get(a);
	int bIndex = indexes.get(b);
	if (aIndex != bIndex) {
	return aIndex - bIndex;
	}
	return b.getElementName()
	.compareTo(a.getElementName());
	});

	IType focusType = this.getType();
	boolean inProjectOfFocusType = focusType != null
	&& focusType.getScriptProject().equals(project);
	org.eclipse.dltk.core.ISourceModule[] unitsToLookInside = null;
	if (inProjectOfFocusType) {
	org.eclipse.dltk.core.ISourceModule unitToLookInside = focusType
	.getSourceModule();
	if (unitToLookInside != null) {
	int wcLength = workingCopies == null ? 0
	: workingCopies.length;
	if (wcLength == 0) {
	unitsToLookInside = new org.eclipse.dltk.core.ISourceModule[] { unitToLookInside };
	} else {
	unitsToLookInside = new org.eclipse.dltk.core.ISourceModule[wcLength + 1];
	unitsToLookInside[0] = unitToLookInside;
	System.arraycopy(workingCopies, 0, unitsToLookInside,
	1, wcLength);
	}
	} else {
	unitsToLookInside = workingCopies;
	}
	}

	ISearchableEnvironment searchableEnvironment = project
	.newSearchableNameEnvironment(unitsToLookInside);
	this.nameLookup = searchableEnvironment.getNameLookup();
	// Map options = project.getOptions(true);
	// disable task tags to speed up parsing
	// options.put(DLTKCore.COMPILER_TASK_TAGS, ""); //$NON-NLS-1$
	this.hierarchyResolver = new HierarchyResolver(this);
	// searchableEnvironment, options, this,
	//new DefaultProblemFactory());

	if (focusType != null) {
	Member declaringMember = ((Member) focusType)
	.getOuterMostLocalContext();
	if (declaringMember == null) {
	// top level or member type
	// if (!inProjectOfFocusType) {
	// char[] typeQualifiedName = focusType
	// .getTypeQualifiedName('.').toCharArray();
	// String[] packageName = ((PackageFragment) focusType
	// .getPackageFragment()).names;
	// if (searchableEnvironment.findType(typeQualifiedName,
	// Util.toCharArrays(packageName)) == null) {
	// // focus type is not visible in this project: no
	// // need to go further
	// return;
	// }
	// }
	} else {
	// local or anonymous type
	Openable openable;
	openable = (Openable) declaringMember.getSourceModule();
	localTypes = new HashSet();
	localTypes.add(openable.getPath().toString());
	this.hierarchyResolver.resolve(new Openable[] { openable }, localTypes);
	return;
	}
	}
	this.hierarchyResolver.resolve(openables, localTypes);
	}
	}

	/**
	* Configure this type hierarchy based on the given potential subtypes.
	*/
	private void buildFromPotentialSubtypes(String[] allPotentialSubTypes,
	HashSet localTypes, IProgressMonitor monitor) {
	IType focusType = this.getType();

	// substitute compilation units with working copies
	HashMap wcPaths = new HashMap(); // a map from path to working copies
	int wcLength;
	org.eclipse.dltk.core.ISourceModule[] workingCopies = this.hierarchy.workingCopies;
	if (workingCopies != null && (wcLength = workingCopies.length) > 0) {
	String[] newPaths = new String[wcLength];
	for (int i = 0; i < wcLength; i++) {
	org.eclipse.dltk.core.ISourceModule workingCopy = workingCopies[i];
	String path = workingCopy.getPath().toString();
	wcPaths.put(path, workingCopy);
	newPaths[i] = path;
	}
	int potentialSubtypesLength = allPotentialSubTypes.length;
	System.arraycopy(allPotentialSubTypes, 0,
	allPotentialSubTypes = new String[potentialSubtypesLength
	+ wcLength], 0, potentialSubtypesLength);
	System.arraycopy(newPaths, 0, allPotentialSubTypes,
	potentialSubtypesLength, wcLength);
	}

	int length = allPotentialSubTypes.length;

	// inject the compilation unit of the focus type (so that types in
	// this cu have special visibility permission (this is also usefull
	// when the cu is a working copy)
	Openable focusCU = (Openable) focusType.getSourceModule();
	String focusPath = null;
	if (focusCU != null) {
	focusPath = focusCU.getPath().toString();
	if (length > 0) {
	System.arraycopy(allPotentialSubTypes, 0,
	allPotentialSubTypes = new String[length + 1], 0,
	length);
	allPotentialSubTypes[length] = focusPath;
	} else {
	allPotentialSubTypes = new String[] { focusPath };
	}
	length++;
	}

	/*
	* Sort in alphabetical order so that potential subtypes are grouped per
	* project
	*/
	Arrays.sort(allPotentialSubTypes);

	ArrayList potentialSubtypes = new ArrayList();
	try {
	// create element infos for subtypes
	HandleFactory factory = new HandleFactory();
	IScriptProject currentProject = null;
	if (monitor != null) {
	monitor.beginTask("", length * 2); //$NON-NLS-1$ // 1 for build binding, 1 for connect hierarchy
	}
	for (int i = 0; i < length; i++) {
	try {
	String resourcePath = allPotentialSubTypes[i];

	// skip duplicate paths (e.g. if focus path was injected
	// when it was already a potential subtype)
	if (i > 0
	&& resourcePath.equals(allPotentialSubTypes[i - 1])) {
	continue;
	}

	Openable handle;
	org.eclipse.dltk.core.ISourceModule workingCopy = (org.eclipse.dltk.core.ISourceModule) wcPaths
	.get(resourcePath);
	if (workingCopy != null) {
	handle = (Openable) workingCopy;
	} else {
	handle = resourcePath.equals(focusPath) ? focusCU
	: factory.createOpenable(resourcePath,
	this.scope);
	if (handle == null) {
	continue; // match is outside classpath
	}
	}

	IScriptProject project = handle.getScriptProject();
	if (currentProject == null) {
	currentProject = project;
	potentialSubtypes = new ArrayList(5);
	} else if (!currentProject.equals(project)) {
	// build current project
	this.buildForProject((ScriptProject) currentProject,
	potentialSubtypes, workingCopies, localTypes,
	monitor);
	currentProject = project;
	potentialSubtypes = new ArrayList(5);
	}

	potentialSubtypes.add(handle);
	} catch (ModelException e) {
	continue;
	}
	}

	// build last project
	try {
	if (currentProject == null) {
	// case of no potential subtypes
	currentProject = focusType.getScriptProject();
	potentialSubtypes.add(focusType.getSourceModule());
	}
	this.buildForProject((ScriptProject) currentProject,
	potentialSubtypes, workingCopies, localTypes, monitor);
	} catch (ModelException e) {
	// ignore
	}

	// Compute hierarchy of focus type if not already done (case of a
	// type with potential subtypes that are not real subtypes)
	if (!this.hierarchy.contains(focusType)) {
	try {
	currentProject = focusType.getScriptProject();
	potentialSubtypes = new ArrayList();
	potentialSubtypes.add(focusType.getSourceModule());

	this.buildForProject((ScriptProject) currentProject,
	potentialSubtypes, workingCopies, localTypes,
	monitor);
	} catch (ModelException e) {
	// ignore
	}
	}

	// Add focus if not already in (case of a type with no explicit
	// super type)
	// if (!this.hierarchy.contains(focusType)) {
	// this.hierarchy.addRootClass(focusType);
	// }
	} finally {
	if (monitor != null) {
	monitor.done();
	}
	}
	}

	@Override
	protected ISourceModule createCompilationUnitFromPath(Openable handle,
	IFile file) {
	ISourceModule unit = super.createCompilationUnitFromPath(handle,
	file);
	this.cuToHandle.put(unit, handle);
	return unit;
	}

	/**
	* Returns all of the possible subtypes of this type hierarchy. Returns null
	* if they could not be determine.
	*/
	protected String[] determinePossibleSubTypes(final HashSet localTypes,
	IProgressMonitor monitor) {

	class PathCollector implements IPathRequestor {
	HashSet paths = new HashSet(10);

	@Override
	public void acceptPath(String path, boolean containsLocalTypes) {
	this.paths.add(path);
	if (containsLocalTypes) {
	localTypes.add(path);
	}
	}
	}
	PathCollector collector = new PathCollector();

	try {
	if (monitor != null) {
	monitor.beginTask("", MAXTICKS); //$NON-NLS-1$
	}
	searchAllPossibleSubTypes(this.getType(), this.scope,
	this.binariesFromIndexMatches, collector,
	IDLTKSearchConstants.WAIT_UNTIL_READY_TO_SEARCH, monitor);
	} finally {
	if (monitor != null) {
	monitor.done();
	}
	}

	HashSet paths = collector.paths;
	int length = paths.size();
	String[] result = new String[length];
	int count = 0;
	for (Iterator iter = paths.iterator(); iter.hasNext();) {
	result[count++] = (String) iter.next();
	}
	return result;
	}

	/**
	* Find the set of candidate subtypes of a given type.
	*
	* The requestor is notified of super type references (with actual path of
	* its occurrence) for all types which are potentially involved inside a
	* particular hierarchy. The match locator is not used here to narrow down
	* the results, the type hierarchy resolver is rather used to compute the
	* whole hierarchy at once.
	*
	* @param type
	* @param scope
	* @param binariesFromIndexMatches
	* @param pathRequestor
	* @param waitingPolicy
	* @param progressMonitor
	*/
	public static void searchAllPossibleSubTypes(IType type,
	IDLTKSearchScope scope, final Map binariesFromIndexMatches,
	final IPathRequestor pathRequestor, int waitingPolicy, // WaitUntilReadyToSearch
	// \|
	// ForceImmediateSearch
	// \|
	// CancelIfNotReadyToSearch
	IProgressMonitor progressMonitor) {

	/*
	* embed constructs inside arrays so as to pass them to (inner)
	* collector
	*/
	final Queue queue = new Queue();
	final HashtableOfObject foundSuperNames = new HashtableOfObject(5);

	IndexManager indexManager = ModelManager.getModelManager()
	.getIndexManager();

	/* use a special collector to collect paths and queue new subtype names */
	IndexQueryRequestor searchRequestor = new IndexQueryRequestor() {
	@Override
	public boolean acceptIndexMatch(String documentPath,
	SearchPattern indexRecord, SearchParticipant participant,
	AccessRuleSet access) {
	SuperTypeReferencePattern record = (SuperTypeReferencePattern) indexRecord;
	boolean isLocalOrAnonymous = record.enclosingTypeName == IIndexConstants.ONE_ZERO;
	pathRequestor.acceptPath(documentPath, isLocalOrAnonymous);
	char[] typeName = record.simpleName;

	if (!isLocalOrAnonymous // local or anonymous types cannot have
	// subtypes outside the cu that define
	// them
	&& !foundSuperNames.containsKey(typeName)) {
	foundSuperNames.put(typeName, typeName);
	queue.add(typeName);
	}
	return true;
	}
	};

	int superRefKind;
	superRefKind = SuperTypeReferencePattern.ALL_SUPER_TYPES;
	SuperTypeReferencePattern pattern = new SuperTypeReferencePattern(null,
	null, superRefKind, SearchPattern.R_EXACT_MATCH
	\| SearchPattern.R_CASE_SENSITIVE, scope.getLanguageToolkit());
	MatchLocator.setFocus(pattern, type);
	SubTypeSearchJob job = new SubTypeSearchJob(pattern,
	new DLTKSearchParticipant(), // java search only
	scope, searchRequestor);

	int ticks = 0;
	queue.add(type.getElementName().toCharArray());
	try {
	while (queue.start <= queue.end) {
	if (progressMonitor != null && progressMonitor.isCanceled()) {
	return;
	}

	// all subclasses of OBJECT are actually all types
	char[] currentTypeName = queue.retrieve();
	if (CharOperation.equals(currentTypeName,
	IIndexConstants.OBJECT)) {
	currentTypeName = null;
	}

	// search all index references to a given supertype
	pattern.superSimpleName = currentTypeName;
	indexManager.performConcurrentJob(job, waitingPolicy, null); // no
	// sub
	// progress
	// monitor
	// since
	// its
	// too
	// costly
	// for
	// deep
	// hierarchies
	if (progressMonitor != null && ++ticks <= MAXTICKS) {
	progressMonitor.worked(1);
	}

	// in case, we search all subtypes, no need to search further
	if (currentTypeName == null) {
	break;
	}
	}
	} finally {
	job.finished();
	}
	}
	}