core/tests/org.eclipse.dltk.core.tests/src/org/eclipse/dltk/core/tests/model/TypeHierarchyTests.java - dltk/org.eclipse.dltk.core - Git at Google

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

 import java.util.HashMap;
 import java.util.HashSet;
 import java.util.Map;
 import java.util.Set;
 import java.util.TreeSet;

 import org.eclipse.core.runtime.CoreException;
 import org.eclipse.dltk.core.IBuffer;
 import org.eclipse.dltk.core.IModelElement;
 import org.eclipse.dltk.core.ISourceModule;
 import org.eclipse.dltk.core.IType;
 import org.eclipse.dltk.core.WorkingCopyOwner;
 import org.eclipse.dltk.internal.core.ModelElement;
 import org.eclipse.dltk.internal.core.SourceType;
 import org.eclipse.dltk.internal.core.hierarchy.TypeHierarchy;

 public class TypeHierarchyTests extends ModifyingResourceTests {
 	private static boolean DEBUG = false;
 	private static final String[] TEST_NATURE = new String[] {
 			"org.eclipse.dltk.core.tests.testnature" };

 	private ISourceModule cu = null;
 	private ISourceModule copy = null;

 	public class TestWorkingCopyOwner extends WorkingCopyOwner {
 		@Override
 		public IBuffer createBuffer(ISourceModule workingCopy) {
 			return new TestBuffer(workingCopy);
 		}
 	}

 	private final Set<IType> expectedExploredClasses = new HashSet<>();
 	private final Set<IType> expectedCyclicClasses = new HashSet<>();
 	private final FakeTypeHierarchy typeHierarchy = new FakeTypeHierarchy();
 	private boolean useCacheSuperclass = true;

 	public TypeHierarchyTests(String name) {
 		super(ModelTestsPlugin.PLUGIN_NAME, name);
 	}

 	public static Suite suite() {
 		return new Suite(TypeHierarchyTests.class);
 	}

 	@Override
 	protected void setUp() throws Exception {
 		super.setUp();
 		typeHierarchy.initialize(1);
 		expectedExploredClasses.clear();
 		expectedCyclicClasses.clear();
 		useCacheSuperclass = true;
 		try {

 			this.createScriptProject("P", TEST_NATURE, new String[] { "src" });
 			this.createFolder("P/src/x/y");
 			this.createFile("P/src/x/y/Z.txt", "");
 			this.cu = this.getSourceModule("P/src/x/y/Z.txt");
 			this.copy = cu.getWorkingCopy(null);
 		} catch (CoreException e) {
 			e.printStackTrace();
 			throw new RuntimeException(e.getMessage());
 		}
 	}

 	@Override
 	protected void tearDown() throws Exception {
 		if (this.copy != null)
 			this.copy.discardWorkingCopy();
 		AbstractModelTests.deleteProject("P");
 		super.tearDown();
 	}

 	static class FakeTypeHierarchy extends TypeHierarchy {
 		@Override
 		public void addSubtype(IType type, IType subtype) {
 			super.addSubtype(type, subtype);
 		}

 		@Override
 		protected void cacheSuperclass(IType type, IType superclass) {
 			super.cacheSuperclass(type, superclass);
 		}

 		@Override
 		public void resetClassPaths() {
 			super.resetClassPaths();
 		}

 		public Set<IType> getExploredClasses() {
 			return this.exploredClasses;
 		}

 		public Set<IType> getCyclicClasses() {
 			return this.cyclicClasses;
 		}

 		@Override
 		protected void initialize(int size) {
 			super.initialize(size);
 		}
 	}

 	private Map<String, SourceType> createFakeTypes(char begin, char end,
 			ModelElement modelElement) {
 		Map<String, SourceType> types = new HashMap<>();
 		for (char i = begin; i <= end; i++) {
 			String name = Character.toString(i);
 			types.put(name, new SourceType(modelElement, name));
 		}
 		return types;
 	}

 	private void populate(SourceType parent, boolean isParentOnCyclicPath,
 			SourceType child, boolean isChildOnCyclicPath) {
 		assertNotNull(parent);
 		assertNotNull(child);

 		if (useCacheSuperclass) {
 			typeHierarchy.cacheSuperclass(parent, child);
 		} else {
 			typeHierarchy.addSubtype(child, parent);
 		}
 		expectedExploredClasses.add(parent);
 		expectedExploredClasses.add(child);
 		if (isParentOnCyclicPath) {
 			expectedCyclicClasses.add(parent);
 		}
 		if (isChildOnCyclicPath) {
 			expectedCyclicClasses.add(child);
 		}

 		explorePartialGraphThroughSubclasses(parent, false);
 		explorePartialGraphThroughSubclasses(child, false);

 		explorePartialGraphThroughSuperclasses(parent, false);
 		explorePartialGraphThroughSuperclasses(child, false);
 	}

 	private void print(Set<IType> classPaths) {
 		Set<IType> sortedClassPaths = new TreeSet<>((arg0, arg1) -> {
 			if (arg0 == arg1 || arg0.equals(arg1)) {
 				return 0;
 			}
 			return arg0.getElementName().compareTo(arg1.getElementName());
 		});
 		sortedClassPaths.addAll(classPaths);
 		System.out.println(sortedClassPaths);
 	}

 	private void printCurrentState() {
 		if (!DEBUG) {
 			return;
 		}
 		print(typeHierarchy.getExploredClasses());
 		print(expectedExploredClasses);
 		System.out.println();
 		print(typeHierarchy.getCyclicClasses());
 		print(expectedCyclicClasses);
 		System.out.println();
 	}

 	private void exploreAllGraphThroughSubclasses(SourceType type,
 			boolean doReset) {
 		assertNotNull(type);
 		if (doReset) {
 			typeHierarchy.resetClassPaths();
 		}
 		typeHierarchy.getSubclasses(type);
 		printCurrentState();
 		assertEquals(typeHierarchy.getExploredClasses(),
 				expectedExploredClasses);
 		assertEquals(typeHierarchy.getCyclicClasses(), expectedCyclicClasses);
 	}

 	private void exploreAllGraphThroughSuperclasses(SourceType type,
 			boolean doReset) {
 		assertNotNull(type);
 		if (doReset) {
 			typeHierarchy.resetClassPaths();
 		}
 		typeHierarchy.getSuperclass(type);
 		printCurrentState();
 		assertEquals(typeHierarchy.getExploredClasses(),
 				expectedExploredClasses);
 		assertEquals(typeHierarchy.getCyclicClasses(), expectedCyclicClasses);
 	}

 	private void explorePartialGraphThroughSubclasses(SourceType type,
 			boolean doReset) {
 		assertNotNull(type);
 		if (doReset) {
 			typeHierarchy.resetClassPaths();
 		}
 		typeHierarchy.getSubclasses(type);
 		printCurrentState();
 		assertTrue(!expectedExploredClasses.contains(type)
 				|| !typeHierarchy.getExploredClasses().isEmpty());
 		assertTrue(typeHierarchy.getExploredClasses()
 				.containsAll(typeHierarchy.getCyclicClasses()));
 		assertTrue(expectedExploredClasses
 				.containsAll(typeHierarchy.getExploredClasses()));
 		assertTrue(expectedExploredClasses
 				.containsAll(typeHierarchy.getCyclicClasses()));
 		assertTrue(expectedCyclicClasses
 				.containsAll(typeHierarchy.getCyclicClasses()));
 	}

 	private void explorePartialGraphThroughSuperclasses(SourceType type,
 			boolean doReset) {
 		assertNotNull(type);
 		if (doReset) {
 			typeHierarchy.resetClassPaths();
 		}
 		typeHierarchy.getSuperclass(type);
 		printCurrentState();
 		assertTrue(!expectedExploredClasses.contains(type)
 				|| !typeHierarchy.getExploredClasses().isEmpty());
 		assertTrue(typeHierarchy.getExploredClasses()
 				.containsAll(typeHierarchy.getCyclicClasses()));
 		assertTrue(expectedExploredClasses
 				.containsAll(typeHierarchy.getExploredClasses()));
 		assertTrue(expectedExploredClasses
 				.containsAll(typeHierarchy.getCyclicClasses()));
 		assertTrue(expectedCyclicClasses
 				.containsAll(typeHierarchy.getCyclicClasses()));
 	}

 	public void testCyclicHierarchy001() throws Exception {
 		assertNotNull(cu);
 		IModelElement p = cu.getParent();
 		assertTrue(p instanceof ModelElement);

 		typeHierarchy.resetClassPaths();
 		Map<String, SourceType> types = createFakeTypes('A', 'U',
 				(ModelElement) p);

 		// * Class hierarchy representation, "(c)" means that the relevant class
 		// in on a cyclic path
 		// *
 		// * +------+
 		// * | L |
 		// * +------+
 		// * ^
 		// * | +-------------------------------------+
 		// * | v |
 		// * +------+ +------+ +------+ +------+ +------+ +------+ +---+
 		// +------+ +---+ +---+ +---+ |
 		// * +> | B(c) | <-- | A(c) | --> | H(c) | --> | | --> | J(c) | --> |
 		// K(c) | --> | O | --> | P(c) | --> | R | --> | S | --> | U | |
 		// * | +------+ +------+ +------+ | | +------+ +------+ +---+ +------+
 		// +---+ +---+ +---+ |
 		// * | | ^ | | | | | ^ |
 		// * | | +---------------------- | I(c) | <------------------+ | | | |
 		// * | v | | v v | |
 		// * | +------+ | | +------+ +---+ | |
 		// * | | C(c) | <------------------+ +- | | --------------+ | Q(c) | | T
 		// | ----------------+ |
 		// * | +------+ | | +------+ | +------+ +---+ |
 		// * | | | | | | |
 		// * | | | | +------------+ | | |
 		// * | v | | v | | | |
 		// * | +------+ +------+ +------+ | +------+ +------+ | | |
 		// * +- | D(c) | --> | E(c) | --> | F(c) | +> | M(c) | --> | N(c) | |
 		// +-------------------------------------+
 		// * +------+ +------+ +------+ +------+ +------+ |
 		// * | ^ |
 		// * | +---------------------------------+
 		// * v
 		// * +------+
 		// * | G |
 		// * +------+
 		// *
 		populate(types.get("A"), true, types.get("B"), true);
 		populate(types.get("B"), true, types.get("C"), true);
 		populate(types.get("C"), true, types.get("D"), true);
 		populate(types.get("D"), true, types.get("E"), true);
 		populate(types.get("E"), true, types.get("F"), true);
 		populate(types.get("E"), true, types.get("G"), false);
 		populate(types.get("F"), true, types.get("C"), true);
 		populate(types.get("D"), true, types.get("B"), true);
 		populate(types.get("A"), true, types.get("H"), true);
 		populate(types.get("H"), true, types.get("I"), true);
 		populate(types.get("I"), true, types.get("F"), true);
 		populate(types.get("I"), true, types.get("A"), true);
 		populate(types.get("I"), true, types.get("J"), true);
 		populate(types.get("J"), true, types.get("K"), true);
 		populate(types.get("K"), true, types.get("I"), true);
 		populate(types.get("K"), true, types.get("L"), false);
 		populate(types.get("K"), true, types.get("O"), false);
 		populate(types.get("O"), false, types.get("P"), true);
 		populate(types.get("P"), true, types.get("Q"), true);
 		populate(types.get("Q"), true, types.get("P"), true);
 		populate(types.get("P"), true, types.get("R"), false);
 		populate(types.get("I"), true, types.get("M"), true);
 		populate(types.get("M"), true, types.get("N"), true);
 		populate(types.get("N"), true, types.get("M"), true);
 		populate(types.get("R"), false, types.get("S"), false);
 		populate(types.get("R"), false, types.get("T"), false);
 		populate(types.get("S"), false, types.get("U"), false);
 		populate(types.get("T"), false, types.get("U"), false);
 		assertTrue(expectedExploredClasses.containsAll(expectedCyclicClasses));

 		exploreAllGraphThroughSuperclasses(types.get("A"), false);
 		exploreAllGraphThroughSuperclasses(types.get("A"), true);
 		exploreAllGraphThroughSuperclasses(types.get("K"), true);
 		explorePartialGraphThroughSuperclasses(types.get("O"), true);
 		exploreAllGraphThroughSuperclasses(types.get("K"), false);
 		explorePartialGraphThroughSuperclasses(types.get("D"), true);

 		for (String typeName : types.keySet()) {
 			explorePartialGraphThroughSuperclasses(types.get(typeName), true);
 		}

 		exploreAllGraphThroughSubclasses(types.get("B"), true);
 		exploreAllGraphThroughSubclasses(types.get("O"), true);

 		for (String typeName : types.keySet()) {
 			explorePartialGraphThroughSubclasses(types.get(typeName), true);
 		}
 	}

 	public void testCyclicHierarchy002() throws Exception {
 		useCacheSuperclass = false;
 		testCyclicHierarchy001();
 	}

 	public void testCyclicHierarchy003() throws Exception {
 		assertNotNull(cu);
 		IModelElement p = cu.getParent();
 		assertTrue(p instanceof ModelElement);

 		typeHierarchy.resetClassPaths();
 		Map<String, SourceType> types = createFakeTypes('A', 'Z',
 				(ModelElement) p);

 		// * Class hierarchy representation, "(c)" means that the relevant class
 		// in on a cyclic path
 		// *
 		// * +------+ +---+ +---+
 		// * +> | W(c) | --> | V | --> | H |
 		// * | +------+ +---+ +---+
 		// * | |
 		// * | |
 		// * | v
 		// * | +------+
 		// * +- | X(c) |
 		// * +------+
 		// *
 		populate(types.get("W"), true, types.get("X"), true);
 		populate(types.get("W"), true, types.get("V"), false);
 		populate(types.get("V"), false, types.get("H"), false);
 		populate(types.get("X"), true, types.get("W"), true);
 		assertTrue(expectedExploredClasses.containsAll(expectedCyclicClasses));

 		explorePartialGraphThroughSuperclasses(types.get("H"), true);

 		for (String typeName : types.keySet()) {
 			explorePartialGraphThroughSuperclasses(types.get(typeName), true);
 		}

 		for (String typeName : types.keySet()) {
 			explorePartialGraphThroughSubclasses(types.get(typeName), true);
 		}
 	}

 	public void testCyclicHierarchy004() throws Exception {
 		useCacheSuperclass = false;
 		testCyclicHierarchy003();
 	}

 	public void testNonCyclicHierarchy005() throws Exception {
 		assertNotNull(cu);
 		IModelElement p = cu.getParent();
 		assertTrue(p instanceof ModelElement);

 		typeHierarchy.resetClassPaths();
 		Map<String, SourceType> types = createFakeTypes('A', 'F',
 				(ModelElement) p);

 		// * Class hierarchy representation, "(c)" means that the relevant class
 		// in on a cyclic path
 		// *
 		// * +---+
 		// * | F |
 		// * +---+
 		// * ^
 		// * |
 		// * |
 		// * +---+ +---+ +---+ +---+
 		// * | A | --> | B | --> | D | --> | E |
 		// * +---+ +---+ +---+ +---+
 		// * | ^
 		// * | |
 		// * v |
 		// * +---+ |
 		// * | C | ----------------+
 		// * +---+
 		// *
 		populate(types.get("A"), false, types.get("B"), false);
 		populate(types.get("A"), false, types.get("C"), false);
 		populate(types.get("B"), false, types.get("D"), false);
 		populate(types.get("C"), false, types.get("D"), false);
 		populate(types.get("D"), false, types.get("E"), false);
 		populate(types.get("D"), false, types.get("F"), false);
 		assertTrue(expectedExploredClasses.containsAll(expectedCyclicClasses));

 		exploreAllGraphThroughSuperclasses(types.get("A"), false);

 		for (String typeName : types.keySet()) {
 			explorePartialGraphThroughSuperclasses(types.get(typeName), true);
 		}

 		for (String typeName : types.keySet()) {
 			explorePartialGraphThroughSubclasses(types.get(typeName), true);
 		}
 	}

 	public void testCyclicHierarchy006() throws Exception {
 		useCacheSuperclass = false;
 		testNonCyclicHierarchy005();
 	}

 	public void testEmptyHierarchy007() throws Exception {
 		assertNotNull(cu);
 		IModelElement p = cu.getParent();
 		assertTrue(p instanceof ModelElement);

 		typeHierarchy.resetClassPaths();

 		SourceType type = new SourceType((ModelElement) p, "A");
 		if (useCacheSuperclass) {
 			typeHierarchy.cacheSuperclass(type, null);
 		} else {
 			typeHierarchy.addSubtype(null, type);
 		}

 		assertTrue(typeHierarchy.getSuperclass(type).length == 0);
 		assertTrue(typeHierarchy.getSubclasses(type).length == 0);

 		assertTrue(typeHierarchy.getExploredClasses().isEmpty());
 		assertTrue(typeHierarchy.getCyclicClasses().isEmpty());
 	}

 	public void testEmptyHierarchy008() throws Exception {
 		useCacheSuperclass = false;
 		testEmptyHierarchy007();
 	}

 	public void testFullyCyclicHierarchy009() throws Exception {
 		assertNotNull(cu);
 		IModelElement p = cu.getParent();
 		assertTrue(p instanceof ModelElement);

 		typeHierarchy.resetClassPaths();
 		Map<String, SourceType> types = createFakeTypes('A', 'H',
 				(ModelElement) p);

 		// * Class hierarchy representation, "(c)" means that the relevant class
 		// in on a cyclic path
 		// *
 		// * +---------------------------------------------------+
 		// * v |
 		// * +------+ +------+ +------+ +------+ +------+ +------+
 		// * | A(c) | --> | B(c) | --> | C(c) | --> | G(c) | --> | H(c) | --> |
 		// F(c) |
 		// * +------+ +------+ +------+ +------+ +------+ +------+
 		// * ^ |
 		// * | |
 		// * | v
 		// * | +------+ +------+
 		// * | | D(c) | --> | E(c) |
 		// * | +------+ +------+
 		// * | |
 		// * +--------------------------------------+
 		// *
 		populate(types.get("A"), true, types.get("B"), true);
 		populate(types.get("B"), true, types.get("C"), true);
 		populate(types.get("C"), true, types.get("D"), true);
 		populate(types.get("D"), true, types.get("E"), true);
 		populate(types.get("E"), true, types.get("A"), true);
 		populate(types.get("F"), true, types.get("B"), true);
 		populate(types.get("C"), true, types.get("G"), true);
 		populate(types.get("G"), true, types.get("H"), true);
 		populate(types.get("H"), true, types.get("F"), true);
 		assertTrue(expectedExploredClasses.containsAll(expectedCyclicClasses));
 		assertEquals(expectedExploredClasses, expectedCyclicClasses);

 		for (String typeName : types.keySet()) {
 			exploreAllGraphThroughSuperclasses(types.get(typeName), true);
 		}

 		for (String typeName : types.keySet()) {
 			exploreAllGraphThroughSubclasses(types.get(typeName), true);
 		}
 	}

 	public void testFullyCyclicHierarchy010() throws Exception {
 		useCacheSuperclass = false;
 		testFullyCyclicHierarchy009();
 	}
 }
	/*******************************************************************************
	* Copyright (c) 2016, 2017 IBM Corporation and others.
	* All rights reserved. This program and the accompanying materials
	* are made available under the terms of the Eclipse Public License v1.0
	* which accompanies this distribution, and is available at
	* http://www.eclipse.org/legal/epl-v10.html
	*
	*******************************************************************************/
	package org.eclipse.dltk.core.tests.model;

	import java.util.HashMap;
	import java.util.HashSet;
	import java.util.Map;
	import java.util.Set;
	import java.util.TreeSet;

	import org.eclipse.core.runtime.CoreException;
	import org.eclipse.dltk.core.IBuffer;
	import org.eclipse.dltk.core.IModelElement;
	import org.eclipse.dltk.core.ISourceModule;
	import org.eclipse.dltk.core.IType;
	import org.eclipse.dltk.core.WorkingCopyOwner;
	import org.eclipse.dltk.internal.core.ModelElement;
	import org.eclipse.dltk.internal.core.SourceType;
	import org.eclipse.dltk.internal.core.hierarchy.TypeHierarchy;

	public class TypeHierarchyTests extends ModifyingResourceTests {
	private static boolean DEBUG = false;
	private static final String[] TEST_NATURE = new String[] {
	"org.eclipse.dltk.core.tests.testnature" };

	private ISourceModule cu = null;
	private ISourceModule copy = null;

	public class TestWorkingCopyOwner extends WorkingCopyOwner {
	@Override
	public IBuffer createBuffer(ISourceModule workingCopy) {
	return new TestBuffer(workingCopy);
	}
	}

	private final Set<IType> expectedExploredClasses = new HashSet<>();
	private final Set<IType> expectedCyclicClasses = new HashSet<>();
	private final FakeTypeHierarchy typeHierarchy = new FakeTypeHierarchy();
	private boolean useCacheSuperclass = true;

	public TypeHierarchyTests(String name) {
	super(ModelTestsPlugin.PLUGIN_NAME, name);
	}

	public static Suite suite() {
	return new Suite(TypeHierarchyTests.class);
	}

	@Override
	protected void setUp() throws Exception {
	super.setUp();
	typeHierarchy.initialize(1);
	expectedExploredClasses.clear();
	expectedCyclicClasses.clear();
	useCacheSuperclass = true;
	try {

	this.createScriptProject("P", TEST_NATURE, new String[] { "src" });
	this.createFolder("P/src/x/y");
	this.createFile("P/src/x/y/Z.txt", "");
	this.cu = this.getSourceModule("P/src/x/y/Z.txt");
	this.copy = cu.getWorkingCopy(null);
	} catch (CoreException e) {
	e.printStackTrace();
	throw new RuntimeException(e.getMessage());
	}
	}

	@Override
	protected void tearDown() throws Exception {
	if (this.copy != null)
	this.copy.discardWorkingCopy();
	AbstractModelTests.deleteProject("P");
	super.tearDown();
	}

	static class FakeTypeHierarchy extends TypeHierarchy {
	@Override
	public void addSubtype(IType type, IType subtype) {
	super.addSubtype(type, subtype);
	}

	@Override
	protected void cacheSuperclass(IType type, IType superclass) {
	super.cacheSuperclass(type, superclass);
	}

	@Override
	public void resetClassPaths() {
	super.resetClassPaths();
	}

	public Set<IType> getExploredClasses() {
	return this.exploredClasses;
	}

	public Set<IType> getCyclicClasses() {
	return this.cyclicClasses;
	}

	@Override
	protected void initialize(int size) {
	super.initialize(size);
	}
	}

	private Map<String, SourceType> createFakeTypes(char begin, char end,
	ModelElement modelElement) {
	Map<String, SourceType> types = new HashMap<>();
	for (char i = begin; i <= end; i++) {
	String name = Character.toString(i);
	types.put(name, new SourceType(modelElement, name));
	}
	return types;
	}

	private void populate(SourceType parent, boolean isParentOnCyclicPath,
	SourceType child, boolean isChildOnCyclicPath) {
	assertNotNull(parent);
	assertNotNull(child);

	if (useCacheSuperclass) {
	typeHierarchy.cacheSuperclass(parent, child);
	} else {
	typeHierarchy.addSubtype(child, parent);
	}
	expectedExploredClasses.add(parent);
	expectedExploredClasses.add(child);
	if (isParentOnCyclicPath) {
	expectedCyclicClasses.add(parent);
	}
	if (isChildOnCyclicPath) {
	expectedCyclicClasses.add(child);
	}

	explorePartialGraphThroughSubclasses(parent, false);
	explorePartialGraphThroughSubclasses(child, false);

	explorePartialGraphThroughSuperclasses(parent, false);
	explorePartialGraphThroughSuperclasses(child, false);
	}

	private void print(Set<IType> classPaths) {
	Set<IType> sortedClassPaths = new TreeSet<>((arg0, arg1) -> {
	if (arg0 == arg1 \|\| arg0.equals(arg1)) {
	return 0;
	}
	return arg0.getElementName().compareTo(arg1.getElementName());
	});
	sortedClassPaths.addAll(classPaths);
	System.out.println(sortedClassPaths);
	}

	private void printCurrentState() {
	if (!DEBUG) {
	return;
	}
	print(typeHierarchy.getExploredClasses());
	print(expectedExploredClasses);
	System.out.println();
	print(typeHierarchy.getCyclicClasses());
	print(expectedCyclicClasses);
	System.out.println();
	}

	private void exploreAllGraphThroughSubclasses(SourceType type,
	boolean doReset) {
	assertNotNull(type);
	if (doReset) {
	typeHierarchy.resetClassPaths();
	}
	typeHierarchy.getSubclasses(type);
	printCurrentState();
	assertEquals(typeHierarchy.getExploredClasses(),
	expectedExploredClasses);
	assertEquals(typeHierarchy.getCyclicClasses(), expectedCyclicClasses);
	}

	private void exploreAllGraphThroughSuperclasses(SourceType type,
	boolean doReset) {
	assertNotNull(type);
	if (doReset) {
	typeHierarchy.resetClassPaths();
	}
	typeHierarchy.getSuperclass(type);
	printCurrentState();
	assertEquals(typeHierarchy.getExploredClasses(),
	expectedExploredClasses);
	assertEquals(typeHierarchy.getCyclicClasses(), expectedCyclicClasses);
	}

	private void explorePartialGraphThroughSubclasses(SourceType type,
	boolean doReset) {
	assertNotNull(type);
	if (doReset) {
	typeHierarchy.resetClassPaths();
	}
	typeHierarchy.getSubclasses(type);
	printCurrentState();
	assertTrue(!expectedExploredClasses.contains(type)
	\|\| !typeHierarchy.getExploredClasses().isEmpty());
	assertTrue(typeHierarchy.getExploredClasses()
	.containsAll(typeHierarchy.getCyclicClasses()));
	assertTrue(expectedExploredClasses
	.containsAll(typeHierarchy.getExploredClasses()));
	assertTrue(expectedExploredClasses
	.containsAll(typeHierarchy.getCyclicClasses()));
	assertTrue(expectedCyclicClasses
	.containsAll(typeHierarchy.getCyclicClasses()));
	}

	private void explorePartialGraphThroughSuperclasses(SourceType type,
	boolean doReset) {
	assertNotNull(type);
	if (doReset) {
	typeHierarchy.resetClassPaths();
	}
	typeHierarchy.getSuperclass(type);
	printCurrentState();
	assertTrue(!expectedExploredClasses.contains(type)
	\|\| !typeHierarchy.getExploredClasses().isEmpty());
	assertTrue(typeHierarchy.getExploredClasses()
	.containsAll(typeHierarchy.getCyclicClasses()));
	assertTrue(expectedExploredClasses
	.containsAll(typeHierarchy.getExploredClasses()));
	assertTrue(expectedExploredClasses
	.containsAll(typeHierarchy.getCyclicClasses()));
	assertTrue(expectedCyclicClasses
	.containsAll(typeHierarchy.getCyclicClasses()));
	}

	public void testCyclicHierarchy001() throws Exception {
	assertNotNull(cu);
	IModelElement p = cu.getParent();
	assertTrue(p instanceof ModelElement);

	typeHierarchy.resetClassPaths();
	Map<String, SourceType> types = createFakeTypes('A', 'U',
	(ModelElement) p);

	// * Class hierarchy representation, "(c)" means that the relevant class
	// in on a cyclic path
	// *
	// * +------+
	// * \| L \|
	// * +------+
	// * ^
	// * \| +-------------------------------------+
	// * \| v \|
	// * +------+ +------+ +------+ +------+ +------+ +------+ +---+
	// +------+ +---+ +---+ +---+ \|
	// * +> \| B(c) \| <-- \| A(c) \| --> \| H(c) \| --> \| \| --> \| J(c) \| --> \|
	// K(c) \| --> \| O \| --> \| P(c) \| --> \| R \| --> \| S \| --> \| U \| \|
	// * \| +------+ +------+ +------+ \| \| +------+ +------+ +---+ +------+
	// +---+ +---+ +---+ \|
	// * \| \| ^ \| \| \| \| \| ^ \|
	// * \| \| +---------------------- \| I(c) \| <------------------+ \| \| \| \|
	// * \| v \| \| v v \| \|
	// * \| +------+ \| \| +------+ +---+ \| \|
	// * \| \| C(c) \| <------------------+ +- \| \| --------------+ \| Q(c) \| \| T
	// \| ----------------+ \|
	// * \| +------+ \| \| +------+ \| +------+ +---+ \|
	// * \| \| \| \| \| \| \|
	// * \| \| \| \| +------------+ \| \| \|
	// * \| v \| \| v \| \| \| \|
	// * \| +------+ +------+ +------+ \| +------+ +------+ \| \| \|
	// * +- \| D(c) \| --> \| E(c) \| --> \| F(c) \| +> \| M(c) \| --> \| N(c) \| \|
	// +-------------------------------------+
	// * +------+ +------+ +------+ +------+ +------+ \|
	// * \| ^ \|
	// * \| +---------------------------------+
	// * v
	// * +------+
	// * \| G \|
	// * +------+
	// *
	populate(types.get("A"), true, types.get("B"), true);
	populate(types.get("B"), true, types.get("C"), true);
	populate(types.get("C"), true, types.get("D"), true);
	populate(types.get("D"), true, types.get("E"), true);
	populate(types.get("E"), true, types.get("F"), true);
	populate(types.get("E"), true, types.get("G"), false);
	populate(types.get("F"), true, types.get("C"), true);
	populate(types.get("D"), true, types.get("B"), true);
	populate(types.get("A"), true, types.get("H"), true);
	populate(types.get("H"), true, types.get("I"), true);
	populate(types.get("I"), true, types.get("F"), true);
	populate(types.get("I"), true, types.get("A"), true);
	populate(types.get("I"), true, types.get("J"), true);
	populate(types.get("J"), true, types.get("K"), true);
	populate(types.get("K"), true, types.get("I"), true);
	populate(types.get("K"), true, types.get("L"), false);
	populate(types.get("K"), true, types.get("O"), false);
	populate(types.get("O"), false, types.get("P"), true);
	populate(types.get("P"), true, types.get("Q"), true);
	populate(types.get("Q"), true, types.get("P"), true);
	populate(types.get("P"), true, types.get("R"), false);
	populate(types.get("I"), true, types.get("M"), true);
	populate(types.get("M"), true, types.get("N"), true);
	populate(types.get("N"), true, types.get("M"), true);
	populate(types.get("R"), false, types.get("S"), false);
	populate(types.get("R"), false, types.get("T"), false);
	populate(types.get("S"), false, types.get("U"), false);
	populate(types.get("T"), false, types.get("U"), false);
	assertTrue(expectedExploredClasses.containsAll(expectedCyclicClasses));

	exploreAllGraphThroughSuperclasses(types.get("A"), false);
	exploreAllGraphThroughSuperclasses(types.get("A"), true);
	exploreAllGraphThroughSuperclasses(types.get("K"), true);
	explorePartialGraphThroughSuperclasses(types.get("O"), true);
	exploreAllGraphThroughSuperclasses(types.get("K"), false);
	explorePartialGraphThroughSuperclasses(types.get("D"), true);

	for (String typeName : types.keySet()) {
	explorePartialGraphThroughSuperclasses(types.get(typeName), true);
	}

	exploreAllGraphThroughSubclasses(types.get("B"), true);
	exploreAllGraphThroughSubclasses(types.get("O"), true);

	for (String typeName : types.keySet()) {
	explorePartialGraphThroughSubclasses(types.get(typeName), true);
	}
	}

	public void testCyclicHierarchy002() throws Exception {
	useCacheSuperclass = false;
	testCyclicHierarchy001();
	}

	public void testCyclicHierarchy003() throws Exception {
	assertNotNull(cu);
	IModelElement p = cu.getParent();
	assertTrue(p instanceof ModelElement);

	typeHierarchy.resetClassPaths();
	Map<String, SourceType> types = createFakeTypes('A', 'Z',
	(ModelElement) p);

	// * Class hierarchy representation, "(c)" means that the relevant class
	// in on a cyclic path
	// *
	// * +------+ +---+ +---+
	// * +> \| W(c) \| --> \| V \| --> \| H \|
	// * \| +------+ +---+ +---+
	// * \| \|
	// * \| \|
	// * \| v
	// * \| +------+
	// * +- \| X(c) \|
	// * +------+
	// *
	populate(types.get("W"), true, types.get("X"), true);
	populate(types.get("W"), true, types.get("V"), false);
	populate(types.get("V"), false, types.get("H"), false);
	populate(types.get("X"), true, types.get("W"), true);
	assertTrue(expectedExploredClasses.containsAll(expectedCyclicClasses));

	explorePartialGraphThroughSuperclasses(types.get("H"), true);

	for (String typeName : types.keySet()) {
	explorePartialGraphThroughSuperclasses(types.get(typeName), true);
	}

	for (String typeName : types.keySet()) {
	explorePartialGraphThroughSubclasses(types.get(typeName), true);
	}
	}

	public void testCyclicHierarchy004() throws Exception {
	useCacheSuperclass = false;
	testCyclicHierarchy003();
	}

	public void testNonCyclicHierarchy005() throws Exception {
	assertNotNull(cu);
	IModelElement p = cu.getParent();
	assertTrue(p instanceof ModelElement);

	typeHierarchy.resetClassPaths();
	Map<String, SourceType> types = createFakeTypes('A', 'F',
	(ModelElement) p);

	// * Class hierarchy representation, "(c)" means that the relevant class
	// in on a cyclic path
	// *
	// * +---+
	// * \| F \|
	// * +---+
	// * ^
	// * \|
	// * \|
	// * +---+ +---+ +---+ +---+
	// * \| A \| --> \| B \| --> \| D \| --> \| E \|
	// * +---+ +---+ +---+ +---+
	// * \| ^
	// * \| \|
	// * v \|
	// * +---+ \|
	// * \| C \| ----------------+
	// * +---+
	// *
	populate(types.get("A"), false, types.get("B"), false);
	populate(types.get("A"), false, types.get("C"), false);
	populate(types.get("B"), false, types.get("D"), false);
	populate(types.get("C"), false, types.get("D"), false);
	populate(types.get("D"), false, types.get("E"), false);
	populate(types.get("D"), false, types.get("F"), false);
	assertTrue(expectedExploredClasses.containsAll(expectedCyclicClasses));

	exploreAllGraphThroughSuperclasses(types.get("A"), false);

	for (String typeName : types.keySet()) {
	explorePartialGraphThroughSuperclasses(types.get(typeName), true);
	}

	for (String typeName : types.keySet()) {
	explorePartialGraphThroughSubclasses(types.get(typeName), true);
	}
	}

	public void testCyclicHierarchy006() throws Exception {
	useCacheSuperclass = false;
	testNonCyclicHierarchy005();
	}

	public void testEmptyHierarchy007() throws Exception {
	assertNotNull(cu);
	IModelElement p = cu.getParent();
	assertTrue(p instanceof ModelElement);

	typeHierarchy.resetClassPaths();

	SourceType type = new SourceType((ModelElement) p, "A");
	if (useCacheSuperclass) {
	typeHierarchy.cacheSuperclass(type, null);
	} else {
	typeHierarchy.addSubtype(null, type);
	}

	assertTrue(typeHierarchy.getSuperclass(type).length == 0);
	assertTrue(typeHierarchy.getSubclasses(type).length == 0);

	assertTrue(typeHierarchy.getExploredClasses().isEmpty());
	assertTrue(typeHierarchy.getCyclicClasses().isEmpty());
	}

	public void testEmptyHierarchy008() throws Exception {
	useCacheSuperclass = false;
	testEmptyHierarchy007();
	}

	public void testFullyCyclicHierarchy009() throws Exception {
	assertNotNull(cu);
	IModelElement p = cu.getParent();
	assertTrue(p instanceof ModelElement);

	typeHierarchy.resetClassPaths();
	Map<String, SourceType> types = createFakeTypes('A', 'H',
	(ModelElement) p);

	// * Class hierarchy representation, "(c)" means that the relevant class
	// in on a cyclic path
	// *
	// * +---------------------------------------------------+
	// * v \|
	// * +------+ +------+ +------+ +------+ +------+ +------+
	// * \| A(c) \| --> \| B(c) \| --> \| C(c) \| --> \| G(c) \| --> \| H(c) \| --> \|
	// F(c) \|
	// * +------+ +------+ +------+ +------+ +------+ +------+
	// * ^ \|
	// * \| \|
	// * \| v
	// * \| +------+ +------+
	// * \| \| D(c) \| --> \| E(c) \|
	// * \| +------+ +------+
	// * \| \|
	// * +--------------------------------------+
	// *
	populate(types.get("A"), true, types.get("B"), true);
	populate(types.get("B"), true, types.get("C"), true);
	populate(types.get("C"), true, types.get("D"), true);
	populate(types.get("D"), true, types.get("E"), true);
	populate(types.get("E"), true, types.get("A"), true);
	populate(types.get("F"), true, types.get("B"), true);
	populate(types.get("C"), true, types.get("G"), true);
	populate(types.get("G"), true, types.get("H"), true);
	populate(types.get("H"), true, types.get("F"), true);
	assertTrue(expectedExploredClasses.containsAll(expectedCyclicClasses));
	assertEquals(expectedExploredClasses, expectedCyclicClasses);

	for (String typeName : types.keySet()) {
	exploreAllGraphThroughSuperclasses(types.get(typeName), true);
	}

	for (String typeName : types.keySet()) {
	exploreAllGraphThroughSubclasses(types.get(typeName), true);
	}
	}

	public void testFullyCyclicHierarchy010() throws Exception {
	useCacheSuperclass = false;
	testFullyCyclicHierarchy009();
	}
	}