core/plugins/org.eclipse.dltk.core/model/org/eclipse/dltk/internal/core/hierarchy/TypeHierarchy.java

/*******************************************************************************
 * 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.io.IOException;
import java.io.InputStream;
import java.io.OutputStream;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Hashtable;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.Map;
import java.util.Set;

import org.eclipse.core.runtime.CoreException;
import org.eclipse.core.runtime.IPath;
import org.eclipse.core.runtime.IProgressMonitor;
import org.eclipse.core.runtime.ISafeRunnable;
import org.eclipse.core.runtime.IStatus;
import org.eclipse.core.runtime.OperationCanceledException;
import org.eclipse.core.runtime.SafeRunner;
import org.eclipse.dltk.core.DLTKCore;
import org.eclipse.dltk.core.DLTKLanguageManager;
import org.eclipse.dltk.core.ElementChangedEvent;
import org.eclipse.dltk.core.IBuildpathEntry;
import org.eclipse.dltk.core.IElementChangedListener;
import org.eclipse.dltk.core.IModelElement;
import org.eclipse.dltk.core.IModelElementDelta;
import org.eclipse.dltk.core.IModelStatusConstants;
import org.eclipse.dltk.core.IOpenable;
import org.eclipse.dltk.core.IProjectFragment;
import org.eclipse.dltk.core.IScriptFolder;
import org.eclipse.dltk.core.IScriptProject;
import org.eclipse.dltk.core.ISourceModule;
import org.eclipse.dltk.core.IType;
import org.eclipse.dltk.core.ITypeHierarchy;
import org.eclipse.dltk.core.ITypeHierarchyChangedListener;
import org.eclipse.dltk.core.ModelException;
import org.eclipse.dltk.core.WorkingCopyOwner;
import org.eclipse.dltk.core.search.IDLTKSearchScope;
import org.eclipse.dltk.core.search.SearchEngine;
import org.eclipse.dltk.internal.core.ModelElement;
import org.eclipse.dltk.internal.core.ModelStatus;
import org.eclipse.dltk.internal.core.Openable;
import org.eclipse.dltk.internal.core.Region;
import org.eclipse.dltk.internal.core.ScriptProject;
import org.eclipse.dltk.internal.core.SourceModule;
import org.eclipse.dltk.internal.core.TypeVector;
import org.eclipse.dltk.internal.core.util.Messages;
import org.eclipse.dltk.internal.core.util.Util;

/**
 * @see ITypeHierarchy
 */
public class TypeHierarchy implements ITypeHierarchy, IElementChangedListener {

	public static boolean DEBUG = false;

	static final byte VERSION = 0x0000;
	// SEPARATOR
	static final byte SEPARATOR1 = '\n';
	static final byte SEPARATOR2 = ',';
	static final byte SEPARATOR3 = '>';
	static final byte SEPARATOR4 = '\r';
	// general info
	static final byte COMPUTE_SUBTYPES = 0x0001;

	// type info
	static final byte CLASS = 0x0000;
	static final byte INTERFACE = 0x0001;
	static final byte COMPUTED_FOR = 0x0002;
	static final byte ROOT = 0x0004;

	// cst
	static final byte[] NO_FLAGS = new byte[] {};
	static final int SIZE = 10;

	/**
	 * The Java Project in which the hierarchy is being built - this provides
	 * the context for determining a classpath and namelookup rules. Possibly
	 * null.
	 */
	protected IScriptProject project;
	/**
	 * The type the hierarchy was specifically computed for, possibly null.
	 */
	protected IType focusType;

	/*
	 * The working copies that take precedence over original compilation units
	 */
	protected ISourceModule[] workingCopies;

	protected Map<IType, TypeVector> classToSuperclass;
	protected Map<IType, TypeVector> typeToSubtypes;
	protected Map<IType, Integer> typeFlags;
	protected Set<IType> exploredClasses;
	protected Set<IType> cyclicClasses;
	protected TypeVector rootClasses = new TypeVector();
	public ArrayList<String> missingTypes = new ArrayList<>(4);

	protected static final IType[] NO_TYPE = new IType[0];

	/**
	 * The progress monitor to report work completed too.
	 */
	protected IProgressMonitor progressMonitor = null;

	/**
	 * Change listeners - null if no one is listening.
	 */
	protected ArrayList<ITypeHierarchyChangedListener> changeListeners = null;

	/*
	 * A map from Openables to ArrayLists of ITypes
	 */
	public Map<IOpenable, ArrayList<IType>> files = null;

	/**
	 * A region describing the packages considered by this hierarchy. Null if
	 * not activated.
	 */
	protected Region packageRegion = null;

	/**
	 * A region describing the projects considered by this hierarchy. Null if
	 * not activated.
	 */
	protected Region projectRegion = null;

	/**
	 * Whether this hierarchy should contains subtypes.
	 */
	protected boolean computeSubtypes;

	/**
	 * The scope this hierarchy should restrain itsef in.
	 */
	IDLTKSearchScope scope;

	/*
	 * Whether this hierarchy needs refresh
	 */
	public boolean needsRefresh = true;

	/*
	 * Collects changes to types
	 */
	protected ChangeCollector changeCollector;

	/**
	 * Creates an empty TypeHierarchy
	 */
	public TypeHierarchy() {
		// Creates an empty TypeHierarchy
	}

	/**
	 * Creates a TypeHierarchy on the given type.
	 */
	public TypeHierarchy(IType type, ISourceModule[] workingCopies,
			IScriptProject project, boolean computeSubtypes) {
		this(type, workingCopies, SearchEngine.createSearchScope(project),
				computeSubtypes);
		this.project = project;
	}

	/**
	 * Creates a TypeHierarchy on the given type.
	 */
	public TypeHierarchy(IType type, ISourceModule[] workingCopies,
			IDLTKSearchScope scope, boolean computeSubtypes) {
		this.focusType = type == null ? null : (IType) ((ModelElement) type); // unsure
		// the
		// focus
		// type
		// is
		// unresolved
		// (see
		// https://bugs.eclipse.org/bugs/show_bug.cgi?id=92357)
		if (DLTKCore.DEBUG) {
			System.err.println("Bu possible. type should be unresolved..."); //$NON-NLS-1$
		}
		this.workingCopies = workingCopies;
		this.computeSubtypes = computeSubtypes;
		this.scope = scope;
	}

	/**
	 * Initializes the file, package and project regions
	 */
	protected void initializeRegions() {

		IType[] allTypes = getAllTypes();
		for (int i = 0; i < allTypes.length; i++) {
			IType type = allTypes[i];
			Openable o = (Openable) ((ModelElement) type).getOpenableParent();
			if (o != null) {
				ArrayList<IType> types = this.files.get(o);
				if (types == null) {
					types = new ArrayList<>();
					this.files.put(o, types);
				}
				types.add(type);
			}
			IScriptFolder pkg = type.getScriptFolder();
			this.packageRegion.add(pkg);
			IScriptProject declaringProject = type.getScriptProject();
			if (declaringProject != null) {
				this.projectRegion.add(declaringProject);
			}
			checkCanceled();
		}
	}

	/**
	 * Adds all of the elements in the collection to the list if the element is
	 * not already in the list.
	 */
	private void addAllCheckingDuplicates(ArrayList<IType> list,
			IType[] collection) {
		for (int i = 0; i < collection.length; i++) {
			IType element = collection[i];
			if (!list.contains(element)) {
				list.add(element);
			}
		}
	}

	/**
	 * Adds the type to the collection of root classes if the classes is not
	 * already present in the collection.
	 */
	protected void addRootClass(IType type) {
		if (this.rootClasses.contains(type)) {
			return;
		}
		this.rootClasses.add(type);
	}

	/**
	 * Adds the given subtype to the type.
	 */
	protected void addSubtype(IType type, IType subtype) {
		cacheSuperclass(subtype, type);
	}

	/**
	 * @see ITypeHierarchy
	 */
	@Override
	public synchronized void addTypeHierarchyChangedListener(
			ITypeHierarchyChangedListener listener) {
		ArrayList<ITypeHierarchyChangedListener> listeners = this.changeListeners;
		if (listeners == null) {
			this.changeListeners = listeners = new ArrayList<>();
		}

		// register with JavaCore to get Java element delta on first listener
		// added
		if (listeners.size() == 0) {
			DLTKCore.addElementChangedListener(this);
		}

		// add listener only if it is not already present
		if (listeners.indexOf(listener) == -1) {
			listeners.add(listener);
		}
	}

	private static Integer bytesToFlags(byte[] bytes) {
		if (bytes != null && bytes.length > 0) {
			return Integer.valueOf(new String(bytes));
		} else {
			return null;
		}
	}

	/**
	 * cacheFlags.
	 */
	public void cacheFlags(IType type, int flags) {
		this.typeFlags.put(type, flags);
	}

	/**
	 * Caches the handle of the superclass for the specified type. As a side
	 * effect cache this type as a subtype of the superclass.
	 */
	protected void cacheSuperclass(IType type, IType superclass) {
		if (superclass != null) {
			TypeVector superTypes = this.classToSuperclass.get(type);
			if (superTypes == null) {
				superTypes = new TypeVector();
				this.classToSuperclass.put(type, superTypes);
			}
			if (!superTypes.contains(superclass)) {
				superTypes.add(superclass);
				resetClassPaths();
			}
			TypeVector subtypes = this.typeToSubtypes.get(superclass);
			if (subtypes == null) {
				subtypes = new TypeVector();
				this.typeToSubtypes.put(superclass, subtypes);
			}
			if (!subtypes.contains(type)) {
				subtypes.add(type);
				resetClassPaths();
			}
		}
	}

	/**
	 * Checks with the progress monitor to see whether the creation of the type
	 * hierarchy should be canceled. Should be regularly called so that the user
	 * can cancel.
	 *
	 * @exception OperationCanceledException
	 *                if cancelling the operation has been requested
	 * @see IProgressMonitor#isCanceled
	 */
	protected void checkCanceled() {
		if (this.progressMonitor != null && this.progressMonitor.isCanceled()) {
			throw new OperationCanceledException();
		}
	}

	/**
	 * Compute this type hierarchy.
	 */
	protected void compute() throws ModelException, CoreException {
		if (this.focusType != null) {
			HierarchyBuilder builder = new IndexBasedHierarchyBuilder(this,
					this.scope);
			builder.build(this.computeSubtypes);
		} // else a RegionBasedTypeHierarchy should be used
	}

	/**
	 * @see ITypeHierarchy
	 */
	@Override
	public boolean contains(IType type) {

		// classes
		if (this.classToSuperclass.get(type) != null) {
			return true;
		}

		// root classes
		if (this.rootClasses.contains(type)) {
			return true;
		}

		return false;
	}

	/**
	 * Determines if the change effects this hierarchy, and fires change
	 * notification if required.
	 */
	@Override
	public void elementChanged(ElementChangedEvent event) {
		// type hierarchy change has already been fired
		if (this.needsRefresh) {
			return;
		}

		if (isAffected(event.getDelta())) {
			this.needsRefresh = true;
			fireChange();
		}
	}

	/**
	 * @see ITypeHierarchy
	 */
	@Override
	public boolean exists() {
		if (!this.needsRefresh) {
			return true;
		}

		return (this.focusType == null || this.focusType.exists())
				&& this.javaProject().exists();
	}

	/**
	 * Notifies listeners that this hierarchy has changed and needs refreshing.
	 * Note that listeners can be removed as we iterate through the list.
	 */
	public void fireChange() {
		ArrayList<ITypeHierarchyChangedListener> listeners = this.changeListeners;
		if (listeners == null) {
			return;
		}
		if (DEBUG) {
			System.out.println(
					"FIRING hierarchy change [" + Thread.currentThread() + "]"); //$NON-NLS-1$ //$NON-NLS-2$
			if (this.focusType != null) {
				System.out.println("    for hierarchy focused on " //$NON-NLS-1$
						+ ((ModelElement) this.focusType)
								.toStringWithAncestors());
			}
		}
		// clone so that a listener cannot have a side-effect on this list when
		// being notified
		listeners = (ArrayList<ITypeHierarchyChangedListener>) listeners
				.clone();
		for (int i = 0; i < listeners.size(); i++) {
			final ITypeHierarchyChangedListener listener = listeners.get(i);
			SafeRunner.run(new ISafeRunnable() {
				@Override
				public void handleException(Throwable exception) {
					Util.log(exception,
							"Exception occurred in listener of Type hierarchy change notification"); //$NON-NLS-1$
				}

				@Override
				public void run() throws Exception {
					listener.typeHierarchyChanged(TypeHierarchy.this);
				}
			});
		}
	}

	private static byte[] flagsToBytes(Integer flags) {
		if (flags != null) {
			return flags.toString().getBytes();
		} else {
			return NO_FLAGS;
		}
	}

	/**
	 * @see ITypeHierarchy
	 */
	@Override
	public IType[] getAllClasses() {
		TypeVector classes = this.rootClasses.copy();
		for (Iterator<IType> iter = this.classToSuperclass.keySet()
				.iterator(); iter.hasNext();) {
			classes.add(iter.next());
		}
		return classes.elements();
	}

	/**
	 * @see ITypeHierarchy
	 */
	@Override
	public IType[] getAllSubtypes(IType type) {
		return getAllSubtypesForType(type);
	}

	/**
	 * @see #getAllSubtypes(IType)
	 */
	private IType[] getAllSubtypesForType(IType type) {
		ArrayList<IType> subTypes = new ArrayList<>();
		getAllSubtypesForType0(type, subTypes, new HashSet<IType>());
		IType[] subClasses = new IType[subTypes.size()];
		subTypes.toArray(subClasses);
		return subClasses;
	}

	/**
	 */
	private void getAllSubtypesForType0(IType type, ArrayList<IType> subs,
			Set<IType> alreadyProcessed) {
		IType[] subTypes = getSubtypesForType(type);
		if (subTypes.length != 0) {
			for (int i = 0; i < subTypes.length; i++) {
				IType subType = subTypes[i];
				if (!alreadyProcessed.contains(subType)) {
					alreadyProcessed.add(subType);
					subs.add(subType);
					getAllSubtypesForType0(subType, subs, alreadyProcessed);
				}
			}
		}
	}

	/**
	 * @see ITypeHierarchy
	 */
	@Override
	public IType[] getAllSuperclasses(IType type) {
		IType[] superclass = getSuperclass(type);
		TypeVector supers = new TypeVector();
		if (superclass == null) {
			return supers.elements();
		}

		for (int i = 0; i < superclass.length; i++) {
			// to eliminate conflicts in dynamic situations
			if (!type.equals(superclass[i])) {
				supers.add(superclass[i]);
				IType[] superclass2 = getAllSuperclasses(superclass[i]);
				supers.addAll(superclass2);
			}
		}

		return supers.elements();
	}

	/**
	 * @see ITypeHierarchy
	 */
	@Override
	public IType[] getAllSupertypes(IType type) {
		ArrayList<IType> supers = new ArrayList<>();
		getAllSupertypes0(type, supers);
		IType[] supertypes = new IType[supers.size()];
		supers.toArray(supertypes);
		return supertypes;
	}

	private void getAllSupertypes0(IType type, ArrayList<IType> supers) {
		TypeVector superTypes = this.classToSuperclass.get(type);
		if (superTypes != null) {
			IType[] superclasses = superTypes.elements();
			if (superclasses.length != 0) {
				addAllCheckingDuplicates(supers, superclasses);
				for (int i = 0; i < superclasses.length; i++) {
					getAllSupertypes0(superclasses[i], supers);
				}
			}
		}
	}

	/**
	 * @see ITypeHierarchy
	 */
	@Override
	public IType[] getAllTypes() {
		// IType[] classes = getAllClasses();
		// int classesLength = classes.length;
		// IType[] all = new IType[classesLength];
		// System.arraycopy(classes, 0, all, 0, classesLength);
		return getAllClasses();
	}

	/**
	 * @see ITypeHierarchy#getCachedFlags(IType)
	 */
	@Override
	public int getCachedFlags(IType type) {
		Integer flagObject = this.typeFlags.get(type);
		if (flagObject != null) {
			return flagObject.intValue();
		}
		return -1;
	}

	/**
	 * @see ITypeHierarchy
	 */
	@Override
	public IType[] getRootClasses() {
		return this.rootClasses.elements();
	}

	/**
	 * @see ITypeHierarchy
	 */
	@Override
	public IType[] getSubclasses(IType type) {
		return getSubtypesForType(type);
	}

	/**
	 * @see ITypeHierarchy
	 */
	@Override
	public IType[] getSubtypes(IType type) {
		return getSubtypesForType(type);
	}

	/**
	 * Returns an array of subtypes for the given type - will never return null.
	 */
	private IType[] getSubtypesForType(IType type) {
		return filterSuperOrSubclasses(type, true);
	}

	/**
	 * @see ITypeHierarchy
	 */
	@Override
	public IType[] getSuperclass(IType type) {
		return filterSuperOrSubclasses(type, false);
	}

	/**
	 * @see ITypeHierarchy
	 */
	@Override
	public IType[] getSupertypes(IType type) {
		return getSuperclass(type);
	}

	/**
	 * @see ITypeHierarchy
	 */
	@Override
	public IType getType() {
		return this.focusType;
	}

	/**
	 * Adds the new elements to a new array that contains all of the elements of
	 * the old array. Returns the new array.
	 */
	protected IType[] growAndAddToArray(IType[] array, IType[] additions) {
		if (array == null || array.length == 0) {
			return additions;
		}
		IType[] old = array;
		array = new IType[old.length + additions.length];
		System.arraycopy(old, 0, array, 0, old.length);
		System.arraycopy(additions, 0, array, old.length, additions.length);
		return array;
	}

	/**
	 * Adds the new element to a new array that contains all of the elements of
	 * the old array. Returns the new array.
	 */
	protected IType[] growAndAddToArray(IType[] array, IType addition) {
		if (array == null || array.length == 0) {
			return new IType[] { addition };
		}
		IType[] old = array;
		array = new IType[old.length + 1];
		System.arraycopy(old, 0, array, 0, old.length);
		array[old.length] = addition;
		return array;
	}

	/*
	 * Whether fine-grained deltas where collected and affects this hierarchy.
	 */
	public boolean hasFineGrainChanges() {
		ChangeCollector collector = this.changeCollector;
		return collector != null && collector.needsRefresh();
	}

	/**
	 * Returns whether one of the subtypes in this hierarchy has the given
	 * simple name or this type has the given simple name.
	 */
	private boolean hasSubtypeNamed(String simpleName) {
		if (this.focusType != null
				&& this.focusType.getElementName().equals(simpleName)) {
			return true;
		}
		IType[] types = this.focusType == null ? getAllTypes()
				: getAllSubtypes(this.focusType);
		for (int i = 0; i < types.length; i++) {
			if (types[i].getElementName().equals(simpleName)) {
				return true;
			}
		}
		return false;
	}

	/**
	 * Returns whether one of the types in this hierarchy has the given simple
	 * name.
	 */
	private boolean hasTypeNamed(String simpleName) {
		IType[] types = this.getAllTypes();
		for (int i = 0; i < types.length; i++) {
			if (types[i].getElementName().equals(simpleName)) {
				return true;
			}
		}
		return false;
	}

	/**
	 * Returns whether the simple name of the given type or one of its
	 * supertypes is the simple name of one of the types in this hierarchy.
	 */
	boolean includesTypeOrSupertype(IType type) {
		try {
			// check type
			if (hasTypeNamed(type.getElementName())) {
				return true;
			}

			// check superclass
			String[] superclassNames = type.getSuperClasses();
			if (superclassNames != null) {
				// int lastSeparator = superclassName.lastIndexOf('.');
				// String simpleName =
				// superclassName.substring(lastSeparator+1);
				// if (hasTypeNamed(simpleName)) return true;
				for (int i = 0; i < superclassNames.length; i++) {
					String superinterfaceName = superclassNames[i];
					// for (String superinterfaceName : superclassNames) {
					int lastSeparator = superinterfaceName.lastIndexOf('.');
					String simpleName = superinterfaceName
							.substring(lastSeparator + 1);
					if (hasTypeNamed(simpleName)) {
						return true;
					}
				}
			}

			// // check superinterfaces
			// String[] superinterfaceNames = type.getSuperInterfaceNames();
			// if (superinterfaceNames != null) {
			// for (int i = 0, length = superinterfaceNames.length; i < length;
			// i++) {
			// String superinterfaceName = superinterfaceNames[i];
			// int lastSeparator = superinterfaceName.lastIndexOf('.');
			// String simpleName =
			// superinterfaceName.substring(lastSeparator+1);
			// if (hasTypeNamed(simpleName)) return true;
			// }
			// }
		} catch (ModelException e) {
			// ignore
		}
		return false;
	}

	/**
	 * Initializes this hierarchy's internal tables with the given size.
	 */
	protected void initialize(int size) {
		if (size < 10) {
			size = 10;
		}
		int smallSize = (size / 2);
		this.classToSuperclass = new HashMap<>(size);
		this.missingTypes = new ArrayList<>(smallSize);
		this.rootClasses = new TypeVector();
		this.typeToSubtypes = new HashMap<>(smallSize);
		this.typeFlags = new HashMap<>(smallSize);
		this.exploredClasses = new HashSet<>(smallSize);
		this.cyclicClasses = new HashSet<>(smallSize);

		this.projectRegion = new Region();
		this.packageRegion = new Region();
		this.files = new HashMap<>(5);
	}

	/**
	 * Returns true if the given delta could change this type hierarchy
	 */
	public synchronized boolean isAffected(IModelElementDelta delta) {
		IModelElement element = delta.getElement();
		switch (element.getElementType()) {
		case IModelElement.SCRIPT_MODEL:
			return isAffectedByJavaModel(delta, element);
		case IModelElement.SCRIPT_PROJECT:
			return isAffectedByJavaProject(delta, element);
		case IModelElement.PROJECT_FRAGMENT:
			return isAffectedByPackageFragmentRoot(delta, element);
		case IModelElement.SCRIPT_FOLDER:
			return isAffectedByPackageFragment(delta, (IScriptFolder) element);
		case IModelElement.SOURCE_MODULE:
			return isAffectedByOpenable(delta, element);
		}
		return false;
	}

	/**
	 * Returns true if any of the children of a project, package fragment root,
	 * or package fragment have changed in a way that effects this type
	 * hierarchy.
	 */
	private boolean isAffectedByChildren(IModelElementDelta delta) {
		if ((delta.getFlags() & IModelElementDelta.F_CHILDREN) > 0) {
			IModelElementDelta[] children = delta.getAffectedChildren();
			for (int i = 0; i < children.length; i++) {
				if (isAffected(children[i])) {
					return true;
				}
			}
		}
		return false;
	}

	/**
	 * Returns true if the given java model delta could affect this type
	 * hierarchy
	 */
	private boolean isAffectedByJavaModel(IModelElementDelta delta,
			IModelElement element) {
		switch (delta.getKind()) {
		case IModelElementDelta.ADDED:
		case IModelElementDelta.REMOVED:
			return element.equals(this.javaProject().getModel());
		case IModelElementDelta.CHANGED:
			return isAffectedByChildren(delta);
		}
		return false;
	}

	/**
	 * Returns true if the given java project delta could affect this type
	 * hierarchy
	 */
	private boolean isAffectedByJavaProject(IModelElementDelta delta,
			IModelElement element) {
		int kind = delta.getKind();
		int flags = delta.getFlags();
		if ((flags & IModelElementDelta.F_OPENED) != 0) {
			kind = IModelElementDelta.ADDED; // affected in the same way
		}
		if ((flags & IModelElementDelta.F_CLOSED) != 0) {
			kind = IModelElementDelta.REMOVED; // affected in the same way
		}
		switch (kind) {
		case IModelElementDelta.ADDED:
			try {
				// if the added project is on the classpath, then the hierarchy
				// has changed
				IBuildpathEntry[] classpath = ((ScriptProject) this
						.javaProject()).getExpandedBuildpath();
				for (int j = 0; j < classpath.length; j++) {
					IBuildpathEntry element2 = classpath[j];
					if (element2.getEntryKind() == IBuildpathEntry.BPE_PROJECT
							&& element2.getPath().equals(element.getPath())) {
						return true;
					}
				}
				if (this.focusType != null) {
					// if the hierarchy's project is on the added project
					// classpath, then the hierarchy has changed
					classpath = ((ScriptProject) element)
							.getExpandedBuildpath();
					IPath hierarchyProject = javaProject().getPath();
					for (int j = 0; j < classpath.length; j++) {
						IBuildpathEntry element2 = classpath[j];
						if (element2
								.getEntryKind() == IBuildpathEntry.BPE_PROJECT
								&& element2.getPath()
										.equals(hierarchyProject)) {
							return true;
						}
					}
				}
				return false;
			} catch (ModelException e) {
				return false;
			}
		case IModelElementDelta.REMOVED:
			// removed project - if it contains packages we are interested in
			// then the type hierarchy has changed
			IModelElement[] pkgs = this.packageRegion.getElements();
			for (int i = 0; i < pkgs.length; i++) {
				IModelElement pkg = pkgs[i];
				IScriptProject javaProject = pkg.getScriptProject();
				if (javaProject != null && javaProject.equals(element)) {
					return true;
				}
			}
			return false;
		case IModelElementDelta.CHANGED:
			return isAffectedByChildren(delta);
		}
		return false;
	}

	/**
	 * Returns true if the given package fragment delta could affect this type
	 * hierarchy
	 */
	private boolean isAffectedByPackageFragment(IModelElementDelta delta,
			IScriptFolder element) {
		switch (delta.getKind()) {
		case IModelElementDelta.ADDED:
			// if the package fragment is in the projects being considered, this
			// could
			// introduce new types, changing the hierarchy
			return this.projectRegion.contains(element);
		case IModelElementDelta.REMOVED:
			// is a change if the package fragment contains types in this
			// hierarchy
			return packageRegionContainsSamePackageFragment(element);
		case IModelElementDelta.CHANGED:
			// look at the files in the package fragment
			return isAffectedByChildren(delta);
		}
		return false;
	}

	/**
	 * Returns true if the given package fragment root delta could affect this
	 * type hierarchy
	 */
	private boolean isAffectedByPackageFragmentRoot(IModelElementDelta delta,
			IModelElement element) {
		switch (delta.getKind()) {
		case IModelElementDelta.ADDED:
			return this.projectRegion.contains(element);
		case IModelElementDelta.REMOVED:
		case IModelElementDelta.CHANGED:
			int flags = delta.getFlags();
			if ((flags & IModelElementDelta.F_ADDED_TO_BUILDPATH) > 0) {
				// check if the root is in the classpath of one of the projects
				// of this hierarchy
				if (this.projectRegion != null) {
					IProjectFragment root = (IProjectFragment) element;
					IPath rootPath = root.getPath();
					IModelElement[] elements = this.projectRegion.getElements();
					for (int i = 0; i < elements.length; i++) {
						IModelElement element2 = elements[i];
						ScriptProject javaProject = (ScriptProject) element2;
						try {
							IBuildpathEntry[] classpath = javaProject
									.getResolvedBuildpath();
							for (int j = 0; j < classpath.length; j++) {
								IBuildpathEntry entry = classpath[j];
								if (entry.getPath().equals(rootPath)) {
									return true;
								}
							}
						} catch (ModelException e) {
							// igmore this project
						}
					}
				}
			}
			if ((flags & IModelElementDelta.F_REMOVED_FROM_BUILDPATH) > 0
					|| (flags & IModelElementDelta.F_CONTENT) > 0) {
				// 1. removed from classpath - if it contains packages we are
				// interested in
				// the the type hierarchy has changed
				// 2. content of a jar changed - if it contains packages we are
				// interested in
				// the the type hierarchy has changed
				IModelElement[] pkgs = this.packageRegion.getElements();
				for (int i = 0; i < pkgs.length; i++) {
					if (pkgs[i].getParent().equals(element)) {
						return true;
					}
				}
				return false;
			}
		}
		return isAffectedByChildren(delta);
	}

	/**
	 * Returns true if the given type delta (a compilation unit delta or a class
	 * file delta) could affect this type hierarchy.
	 */
	protected boolean isAffectedByOpenable(IModelElementDelta delta,
			IModelElement element) {
		if (element instanceof SourceModule) {
			SourceModule cu = (SourceModule) element;
			ChangeCollector collector = this.changeCollector;
			if (collector == null) {
				collector = new ChangeCollector(this);
			}
			try {
				collector.addChange(cu, delta);
			} catch (ModelException e) {
				if (DEBUG) {
					e.printStackTrace();
				}
			}
			if (cu.isWorkingCopy()) {
				// changes to working copies are batched
				this.changeCollector = collector;
				return false;
			} else {
				return collector.needsRefresh();
			}
		}
		return false;
	}

	/**
	 * Returns the java project this hierarchy was created in.
	 */
	public IScriptProject javaProject() {
		return this.focusType.getScriptProject();
	}

	protected static byte[] readUntil(InputStream input, byte separator)
			throws ModelException, IOException {
		return readUntil(input, separator, 0);
	}

	protected static byte[] readUntil(InputStream input, byte separator,
			int offset) throws IOException, ModelException {
		int length = 0;
		byte[] bytes = new byte[SIZE];
		byte b;
		while ((b = (byte) input.read()) != separator && b != -1) {
			if (bytes.length == length) {
				System.arraycopy(bytes, 0, bytes = new byte[length * 2], 0,
						length);
			}
			bytes[length++] = b;
		}
		if (b == -1) {
			throw new ModelException(new ModelStatus(IStatus.ERROR));
		}
		System.arraycopy(bytes, 0, bytes = new byte[length + offset], offset,
				length);
		return bytes;
	}

	public static ITypeHierarchy load(IType type, InputStream input,
			WorkingCopyOwner owner) throws ModelException {
		try {
			TypeHierarchy typeHierarchy = new TypeHierarchy();
			typeHierarchy.initialize(1);

			IType[] types = new IType[SIZE];
			int typeCount = 0;

			byte version = (byte) input.read();

			if (version != VERSION) {
				throw new ModelException(new ModelStatus(IStatus.ERROR));
			}
			byte generalInfo = (byte) input.read();
			if ((generalInfo & COMPUTE_SUBTYPES) != 0) {
				typeHierarchy.computeSubtypes = true;
			}

			byte b;
			byte[] bytes;

			// read project
			bytes = readUntil(input, SEPARATOR1);
			if (bytes.length > 0) {
				typeHierarchy.project = (IScriptProject) DLTKCore
						.create(new String(bytes));
				typeHierarchy.scope = SearchEngine
						.createSearchScope(typeHierarchy.project);
			} else {
				typeHierarchy.project = null;
				typeHierarchy.scope = SearchEngine.createWorkspaceScope(
						DLTKLanguageManager.getLanguageToolkit(type));
			}

			// read missing type
			{
				bytes = readUntil(input, SEPARATOR1);
				byte[] missing;
				int j = 0;
				int length = bytes.length;
				for (int i = 0; i < length; i++) {
					b = bytes[i];
					if (b == SEPARATOR2) {
						missing = new byte[i - j];
						System.arraycopy(bytes, j, missing, 0, i - j);
						typeHierarchy.missingTypes.add(new String(missing));
						j = i + 1;
					}
				}
				System.arraycopy(bytes, j, missing = new byte[length - j], 0,
						length - j);
				typeHierarchy.missingTypes.add(new String(missing));
			}

			// read types
			while ((b = (byte) input.read()) != SEPARATOR1 && b != -1) {
				bytes = readUntil(input, SEPARATOR4, 1);
				bytes[0] = b;
				IType element = (IType) DLTKCore.create(new String(bytes),
						owner);

				if (types.length == typeCount) {
					System.arraycopy(types, 0, types = new IType[typeCount * 2],
							0, typeCount);
				}
				types[typeCount++] = element;

				// read flags
				bytes = readUntil(input, SEPARATOR4);
				Integer flags = bytesToFlags(bytes);
				if (flags != null) {
					typeHierarchy.cacheFlags(element, flags.intValue());
				}

				// read info
				byte info = (byte) input.read();

				// if ((info & INTERFACE) != 0) {
				// typeHierarchy.addInterface(element);
				// }
				if ((info & COMPUTED_FOR) != 0) {
					if (!element.equals(type)) {
						throw new ModelException(
								new ModelStatus(IStatus.ERROR));
					}
					typeHierarchy.focusType = element;
				}
				if ((info & ROOT) != 0) {
					typeHierarchy.addRootClass(element);
				}
			}

			// read super class
			while ((b = (byte) input.read()) != SEPARATOR1 && b != -1) {
				bytes = readUntil(input, SEPARATOR3, 1);
				bytes[0] = b;
				int subClass = Integer.parseInt(new String(bytes));

				// read super type
				bytes = readUntil(input, SEPARATOR1);
				int superClass = Integer.parseInt(new String(bytes));

				typeHierarchy.cacheSuperclass(types[subClass],
						types[superClass]);
			}

			// read super interface
			while ((b = (byte) input.read()) != SEPARATOR1 && b != -1) {
				bytes = readUntil(input, SEPARATOR3, 1);
				bytes[0] = b;
				// int subClass = Integer.parseInt(new String(bytes));

				// read super interface
				bytes = readUntil(input, SEPARATOR1);
				IType[] superInterfaces = new IType[(bytes.length / 2) + 1];
				int interfaceCount = 0;

				int j = 0;
				byte[] b2;
				for (int i = 0; i < bytes.length; i++) {
					if (bytes[i] == SEPARATOR2) {
						b2 = new byte[i - j];
						System.arraycopy(bytes, j, b2, 0, i - j);
						j = i + 1;
						superInterfaces[interfaceCount++] = types[Integer
								.parseInt(new String(b2))];
					}
				}
				b2 = new byte[bytes.length - j];
				System.arraycopy(bytes, j, b2, 0, bytes.length - j);
				superInterfaces[interfaceCount++] = types[Integer
						.parseInt(new String(b2))];
				System.arraycopy(superInterfaces, 0,
						superInterfaces = new IType[interfaceCount], 0,
						interfaceCount);

			}
			if (b == -1) {
				throw new ModelException(new ModelStatus(IStatus.ERROR));
			}
			return typeHierarchy;
		} catch (IOException e) {
			throw new ModelException(e, IModelStatusConstants.IO_EXCEPTION);
		} catch (CoreException e) {
			throw new ModelException(e, IModelStatusConstants.INTERNAL_ERROR);
		}
	}

	/**
	 * Returns <code>true</code> if an equivalent package fragment is included
	 * in the package region. Package fragments are equivalent if they both have
	 * the same name.
	 */
	protected boolean packageRegionContainsSamePackageFragment(
			IScriptFolder element) {
		IModelElement[] pkgs = this.packageRegion.getElements();
		for (int i = 0; i < pkgs.length; i++) {
			IScriptFolder pkg = (IScriptFolder) pkgs[i];
			if (pkg.getElementName().equals(element.getElementName())) {
				return true;
			}
		}
		return false;
	}

	/**
	 * @see ITypeHierarchy TODO (jerome) should use a PerThreadObject to build
	 *      the hierarchy instead of synchronizing (see also
	 *      isAffected(IJavaElementDelta))
	 */
	@Override
	public synchronized void refresh(IProgressMonitor monitor)
			throws ModelException {
		try {
			this.progressMonitor = monitor;
			if (monitor != null) {
				if (this.focusType != null) {
					monitor.beginTask(
							Messages.bind(Messages.hierarchy_creatingOnType,
									this.focusType.getFullyQualifiedName()),
							100);
				} else {
					monitor.beginTask(Messages.hierarchy_creating, 100);
				}
			}
			long start = -1;
			if (DEBUG) {
				start = System.currentTimeMillis();
				if (this.computeSubtypes) {
					System.out.println("CREATING TYPE HIERARCHY [" //$NON-NLS-1$
							+ Thread.currentThread() + "]"); //$NON-NLS-1$
				} else {
					System.out.println("CREATING SUPER TYPE HIERARCHY [" //$NON-NLS-1$
							+ Thread.currentThread() + "]"); //$NON-NLS-1$
				}
				if (this.focusType != null) {
					System.out.println(
							"  on type " + ((ModelElement) this.focusType) //$NON-NLS-1$
									.toStringWithAncestors());
				}
			}

			compute();
			initializeRegions();
			this.needsRefresh = false;
			this.changeCollector = null;

			if (DEBUG) {
				if (this.computeSubtypes) {
					System.out.println("CREATED TYPE HIERARCHY in " //$NON-NLS-1$
							+ (System.currentTimeMillis() - start) + "ms"); //$NON-NLS-1$
				} else {
					System.out.println("CREATED SUPER TYPE HIERARCHY in " //$NON-NLS-1$
							+ (System.currentTimeMillis() - start) + "ms"); //$NON-NLS-1$
				}
				System.out.println(this.toString());
			}
		} catch (ModelException e) {
			throw e;
		} catch (CoreException e) {
			throw new ModelException(e);
		} finally {
			if (monitor != null) {
				monitor.done();
			}
			this.progressMonitor = null;
		}
	}

	/**
	 * @see ITypeHierarchy
	 */
	@Override
	public synchronized void removeTypeHierarchyChangedListener(
			ITypeHierarchyChangedListener listener) {
		ArrayList<ITypeHierarchyChangedListener> listeners = this.changeListeners;
		if (listeners == null) {
			return;
		}
		listeners.remove(listener);

		// deregister from JavaCore on last listener removed
		if (listeners.isEmpty()) {
			DLTKCore.removeElementChangedListener(this);
		}
	}

	/**
	 * @see ITypeHierarchy
	 */
	@Override
	public void store(OutputStream output, IProgressMonitor monitor)
			throws ModelException {
		try {
			// compute types in hierarchy
			Hashtable<IType, Integer> hashtable = new Hashtable<>();
			Hashtable<Integer, IType> hashtable2 = new Hashtable<>();
			int count = 0;

			if (this.focusType != null) {
				Integer index = Integer.valueOf(count++);
				hashtable.put(this.focusType, index);
				hashtable2.put(index, this.focusType);
			}
			Object[] types = this.classToSuperclass.entrySet().toArray();
			for (int k = 0; k < types.length; k++) {
				Object type = types[k];
				@SuppressWarnings("unchecked")
				Map.Entry<IType, TypeVector> entry = (Map.Entry<IType, TypeVector>) type;
				final IType t = entry.getKey();
				if (hashtable.get(t) == null) {
					Integer index = Integer.valueOf(count++);
					hashtable.put(t, index);
					hashtable2.put(index, t);
				}
				TypeVector superClasses = entry.getValue();
				if (superClasses != null) {
					IType[] sp = superClasses.elements();
					for (int i = 0; i < sp.length; i++) {

						IType superInterface = sp[i];
						if (superInterface != null
								&& hashtable.get(superInterface) == null) {
							Integer index = Integer.valueOf(count++);
							hashtable.put(superInterface, index);
							hashtable2.put(index, superInterface);
						}
					}
				}
			}
			// save version of the hierarchy format
			output.write(VERSION);

			// save general info
			byte generalInfo = 0;
			if (this.computeSubtypes) {
				generalInfo |= COMPUTE_SUBTYPES;
			}
			output.write(generalInfo);

			// save project
			if (this.project != null) {
				output.write(this.project.getHandleIdentifier().getBytes());
			}
			output.write(SEPARATOR1);

			// save missing types
			for (int i = 0; i < this.missingTypes.size(); i++) {
				if (i != 0) {
					output.write(SEPARATOR2);
				}
				output.write(this.missingTypes.get(i).getBytes());

			}
			output.write(SEPARATOR1);

			// save types
			for (int i = 0; i < count; i++) {
				IType t = hashtable2.get(Integer.valueOf(i));

				// n bytes
				output.write(t.getHandleIdentifier().getBytes());
				output.write(SEPARATOR4);
				output.write(flagsToBytes(this.typeFlags.get(t)));
				output.write(SEPARATOR4);
				byte info = CLASS;
				if (this.focusType != null && this.focusType.equals(t)) {
					info |= COMPUTED_FOR;
				}
				if (this.rootClasses.contains(t)) {
					info |= ROOT;
				}
				output.write(info);
			}
			output.write(SEPARATOR1);

			// save superclasses
			types = this.classToSuperclass.entrySet().toArray();
			for (int q = 0; q < types.length; q++) {
				Object type = types[q];
				@SuppressWarnings("unchecked")
				Map.Entry<IType, TypeVector> entry = (Map.Entry<IType, TypeVector>) type;
				IModelElement key = entry.getKey();

				TypeVector superTypes = entry.getValue();
				if (superTypes != null) {

					IType[] values = superTypes.elements();
					if (values.length > 0) {
						output.write(
								(hashtable.get(key)).toString().getBytes());
						output.write(SEPARATOR3);
						for (int j = 0; j < values.length; j++) {
							IModelElement value = values[j];
							if (j != 0) {
								output.write(SEPARATOR2);
							}
							output.write((hashtable.get(value)).toString()
									.getBytes());
						}
						output.write(SEPARATOR1);
					}
				}
			}
			output.write(SEPARATOR1);
		} catch (IOException e) {
			throw new ModelException(e, IModelStatusConstants.IO_EXCEPTION);
		}
	}

	/**
	 * Returns whether the simple name of a supertype of the given type is the
	 * simple name of one of the subtypes in this hierarchy or the simple name
	 * of this type.
	 */
	boolean subtypesIncludeSupertypeOf(IType type) {

		// look for super classes
		String[] superclassNames = null;
		try {
			superclassNames = type.getSuperClasses();
		} catch (ModelException e) {
			if (DEBUG) {
				e.printStackTrace();
			}
			return false;
		}
		int dot;
		if (superclassNames != null) {
			for (int i = 0; i < superclassNames.length; i++) {
				String interfaceName = superclassNames[i];
				dot = -1;
				String simpleInterface = (dot = interfaceName
						.lastIndexOf('.')) > -1 ? interfaceName.substring(dot)
								: interfaceName;
				if (hasSubtypeNamed(simpleInterface)) {
					return true;
				}
			}
		}

		return false;
	}

	/**
	 * @see ITypeHierarchy
	 */
	@Override
	public String toString() {
		StringBuffer buffer = new StringBuffer();
		buffer.append("Focus: "); //$NON-NLS-1$
		buffer.append(this.focusType == null ? "<NONE>" //$NON-NLS-1$
				: ((ModelElement) this.focusType)
						.toStringWithAncestors(false/*
													 * don't show key
													 */));
		buffer.append("\n"); //$NON-NLS-1$
		if (exists()) {
			if (this.focusType != null) {
				buffer.append("Super types:\n"); //$NON-NLS-1$
				toString(buffer, this.focusType, 1, true);
				buffer.append("Sub types:\n"); //$NON-NLS-1$
				toString(buffer, this.focusType, 1, false);
			} else {
				buffer.append("Sub types of root classes:\n"); //$NON-NLS-1$
				IModelElement[] roots = Util.sortCopy(getRootClasses());
				for (int i = 0; i < roots.length; i++) {
					toString(buffer, (IType) roots[i], 1, false);
				}
			}
			if (this.rootClasses.size > 1) {
				buffer.append("Root classes:\n"); //$NON-NLS-1$
				IModelElement[] roots = Util.sortCopy(getRootClasses());
				for (int i = 0; i < roots.length; i++) {
					toString(buffer, (IType) roots[i], 1, false);
				}
			} else if (this.rootClasses.size == 0) {
				// see http://bugs.eclipse.org/bugs/show_bug.cgi?id=24691
				buffer.append("No root classes"); //$NON-NLS-1$
			}
		} else {
			buffer.append("(Hierarchy became stale)"); //$NON-NLS-1$
		}
		return buffer.toString();
	}

	/**
	 * Append a String to the given buffer representing the hierarchy for the
	 * type, beginning with the specified indentation level. If ascendant, shows
	 * the super types, otherwise show the sub types.
	 */
	private void toString(StringBuffer buffer, IType type, int indent,
			boolean ascendant) {
		IType[] types = ascendant ? getSupertypes(type) : getSubtypes(type);
		IModelElement[] sortedTypes = Util.sortCopy(types);
		for (int i = 0; i < sortedTypes.length; i++) {
			for (int j = 0; j < indent; j++) {
				buffer.append("  "); //$NON-NLS-1$
			}
			ModelElement element = (ModelElement) sortedTypes[i];
			buffer.append(
					element.toStringWithAncestors(false/* don't show key */));
			buffer.append('\n');
			toString(buffer, types[i], indent + 1, ascendant);
		}
	}

	/**
	 * Returns whether one of the types in this hierarchy has a supertype whose
	 * simple name is the given simple name.
	 */
	boolean hasSupertype(String simpleName) {
		for (Iterator<TypeVector> iter = this.classToSuperclass.values()
				.iterator(); iter.hasNext();) {
			TypeVector typeVector = iter.next();
			if (typeVector != null) {
				IType[] elements = typeVector.elements();
				for (int i = 0; i < elements.length; i++) {
					IType superType = elements[i];
					if (superType.getElementName().equals(simpleName)) {
						return true;
					}
				}
			}
		}
		return false;
	}

	/**
	 * @see IProgressMonitor
	 */
	protected void worked(int work) {
		if (this.progressMonitor != null) {
			this.progressMonitor.worked(work);
			checkCanceled();
		}
	}

	/**
	 * Returns whether a class belongs to an explored class path or not.
	 */
	protected boolean isExplored(IType type) {
		return this.exploredClasses.contains(type);
	}

	/**
	 * Returns whether a class belongs to a cyclic class path or not.
	 */
	protected boolean isCyclic(IType type) {
		return this.cyclicClasses.contains(type);
	}

	/**
	 * Removes all explored class paths. Necessary when new types are added to
	 * maps "classToSuperclass" or "typeToSubtypes" otherwise new cyclic paths
	 * won't be detected.
	 */
	protected void resetClassPaths() {
		this.exploredClasses.clear();
		this.cyclicClasses.clear();
	}

	/**
	 * Main method to discover cyclic and non-cyclic (graph) paths. It is a
	 * depth-first search that will mark as explored (in set "exploredClasses")
	 * all children (i.e. super classes) of "currentClass" and will store (in
	 * set "cyclicClasses") every child that is on a cyclic graph path. All
	 * cyclic paths will be fully explored and list "currentClassPath" avoids
	 * infinite recursion of this method by storing current class path going
	 * from first explored "currentClass" (included) to actual explored
	 * "currentClass" (excluded).
	 */
	void explore(LinkedList<IType> currentClassPath, IType currentClass) {
		if (currentClass == null) {
			return;
		}
		int idx = currentClassPath.indexOf(currentClass);
		if (idx == -1 && isExplored(currentClass) && !isCyclic(currentClass)) {
			// we already explored currentClass and its super classes (if any),
			// we can stop here, this class path (without "currentClass") being
			// a non-cyclic path
			return;
		}
		this.exploredClasses.add(currentClass);
		if (idx != -1) {
			// We found a cyclic path.
			// Split class path in 2, the delimiter being "currentClass". First
			// part is non-cyclic whereas second part is cyclic (and includes
			// "currentClass").
			this.cyclicClasses.addAll(
					currentClassPath.subList(idx, currentClassPath.size()));
			return;
		}
		TypeVector superclasses = this.classToSuperclass.get(currentClass);
		if (superclasses != null && superclasses.size > 0) {
			// add current class to current class path
			currentClassPath.addLast(currentClass);
			// visit all super classes
			for (IType superclass : superclasses.elements()) {
				explore(currentClassPath, superclass);
			}
			// remove current class from current class path
			currentClassPath.removeLast();
		}
	}

	/**
	 * Filters either super or subclasses (depending on value of parameter
	 * "isFilterForSubclasses"). Only super or subclasses having no cyclic
	 * path/hierarchy will be returned.
	 */
	IType[] filterSuperOrSubclasses(IType type, boolean isFilterForSubclasses) {
		if (type == null) {
			return TypeVector.NoElements;
		}
		if (!this.typeToSubtypes.containsKey(type)
				&& !this.classToSuperclass.containsKey(type)) {
			// this type is not handled by current type hierarchy,
			// do not cache its path informations
			return TypeVector.NoElements;
		}
		if (!isExplored(type)) {
			// this type was never explored, go through this type and its
			// unexplored super classes to cache all path informations
			explore(new LinkedList<IType>(), type);
		}
		assert isExplored(type);
		TypeVector superOrSubclasses = isFilterForSubclasses
				? typeToSubtypes.get(type)
				: classToSuperclass.get(type);
		if (superOrSubclasses == null) {
			return TypeVector.NoElements;
		}
		ArrayList<IType> l = new ArrayList<>();
		for (IType superOrSubclass : superOrSubclasses.elements()) {
			if (isFilterForSubclasses && superOrSubclass != null
					&& !isExplored(superOrSubclass)) {
				// this type was never explored, go through this type and its
				// unexplored super classes to cache all path informations
				explore(new LinkedList<IType>(), superOrSubclass);
			}
			assert superOrSubclass == null || isExplored(superOrSubclass);
			if (superOrSubclass == null || !isCyclic(superOrSubclass)) {
				l.add(superOrSubclass);
			}
		}
		return l.toArray(new IType[l.size()]);
	}
}