Copyright (c) 2010, 2019 Darmstadt University of Technology and others.
All rights reserved. This program and the accompanying materials
are made available under the terms of the Eclipse Public License v1.0
which accompanies this distribution, and is available at
http://www.eclipse.org/legal/epl-v10.html
Contributors:
   Marcel Bruch - initial API and implementation.
   Stefan Henss - re-implementation in response to https://bugs.eclipse.org/bugs/show_bug.cgi?id=376796.
/**
 * Copyright (c) 2010, 2019 Darmstadt University of Technology and others.
 * All rights reserved. This program and the accompanying materials
 * are made available under the terms of the Eclipse Public License v1.0
 * which accompanies this distribution, and is available at
 * http://www.eclipse.org/legal/epl-v10.html
 *
 * Contributors:
 *    Marcel Bruch - initial API and implementation.
 *    Stefan Henss - re-implementation in response to https://bugs.eclipse.org/bugs/show_bug.cgi?id=376796.
 */
package org.eclipse.jdt.internal.ui.text;

import java.util.Collection;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;

import org.eclipse.jdt.core.IJavaElement;
import org.eclipse.jdt.core.IType;

import org.eclipse.jdt.internal.ui.text.ChainElement.ElementType;

public class ChainFinder {

	private final List<ChainType> expectedTypes;

	private final List<String> excludedTypes;

	private final IType receiverType;

	private final List<Chain> chains= new LinkedList<>();

	private final Map<IJavaElement, ChainElement> edgeCache= new HashMap<>();

	private final Map<String, List<IJavaElement>> fieldsAndMethodsCache= new HashMap<>();

	private final Map<String, Boolean> assignableCache= new HashMap<>();

	public ChainFinder(final List<ChainType> expectedTypes, final List<String> excludedTypes,
			final IType receiverType) {
		this.expectedTypes= expectedTypes;
		this.excludedTypes= excludedTypes;
		this.receiverType= receiverType;
	}

	public void startChainSearch(final List<ChainElement> entrypoints, final int maxChains, final int minDepth,
			final int maxDepth) {
		for (final ChainType expected : expectedTypes) {
			if (expected != null && !ChainFinder.isFromExcludedType(excludedTypes, expected)) {
				ChainType expectedType= expected;
				int expectedDimension= 0;
				if (expectedType.getDimension() > 0) {
					expectedDimension= expectedType.getDimension();
				}
				searchChainsForExpectedType(expectedType, expectedDimension, entrypoints, maxChains, minDepth,
						maxDepth);
			}
		}
	}

	private void searchChainsForExpectedType(final ChainType expectedType, final int expectedDimensions,
			final List<ChainElement> entrypoints, final int maxChains, final int minDepth, final int maxDepth) {
		final LinkedList<LinkedList<ChainElement>> incompleteChains= prepareQueue(entrypoints);

		while (!incompleteChains.isEmpty()) {
			final LinkedList<ChainElement> chain= incompleteChains.poll();
			final ChainElement edge= chain.getLast();
			if (isValidEndOfChain(edge, expectedType, expectedDimensions)) {
				if (chain.size() >= minDepth) {
					chains.add(new Chain(chain, expectedDimensions));
					if (chains.size() == maxChains) {
						break;
					}
				}
				continue;
			}
			if (chain.size() < maxDepth && incompleteChains.size() <= 50000) {
				searchDeeper(chain, incompleteChains, edge.getReturnType());
			}
		}
	}

	
Returns the potentially incomplete list of call chains that could be found before a time out
happened. The contents of this list are mutable and may change as the search makes progress.
Returns:
The list of call chains/**
	 * Returns the potentially incomplete list of call chains that could be found before a time out
	 * happened. The contents of this list are mutable and may change as the search makes progress.
	 *
	 * @return The list of call chains
	 */
	public List<Chain> getChains() {
		return chains;
	}

	private static LinkedList<LinkedList<ChainElement>> prepareQueue(final List<ChainElement> entrypoints) {
		final LinkedList<LinkedList<ChainElement>> incompleteChains= new LinkedList<>();
		for (final ChainElement entrypoint : entrypoints) {
			final LinkedList<ChainElement> chain= new LinkedList<>();
			chain.add(entrypoint);
			incompleteChains.add(chain);
		}
		return incompleteChains;
	}

	public static boolean isFromExcludedType(final List<String> excluded, final IJavaElement element) {
		if (element instanceof IType) {
			return excluded.contains(((IType) element).getFullyQualifiedName());
		} else {
			return excluded.contains(element.getElementName());
		}
	}

	public static boolean isFromExcludedType(final List<String> excluded, final ChainType element) {
		if (element.getType() != null) {
			return isFromExcludedType(excluded, element.getType());
		}
		return excluded.contains(element.getPrimitiveType());
	}

	private boolean isValidEndOfChain(final ChainElement edge, final ChainType expectedType,
			final int expectedDimension) {
		if (edge.getElementType() == ElementType.TYPE) {
			return false;
		}
		if ((edge.getReturnType().getPrimitiveType() != null)) {
			return edge.getReturnType().getPrimitiveType().equals(expectedType.getPrimitiveType());
		}
		if (expectedType.getPrimitiveType() != null) {
			return expectedType.getPrimitiveType().equals(edge.getReturnType().getPrimitiveType());
		}
		Boolean isAssignable= assignableCache.get(edge.toString() + expectedType.toString());
		if (isAssignable == null) {
			isAssignable= ChainElementAnalyzer.isAssignable(edge, expectedType.getType(), expectedDimension);
			assignableCache.put(edge.toString() + expectedType.toString(), isAssignable);
		}
		return isAssignable.booleanValue();
	}

	private void searchDeeper(final LinkedList<ChainElement> chain,
			final List<LinkedList<ChainElement>> incompleteChains, final ChainType currentlyVisitedType) {
		boolean staticOnly= false;
		if (chain.getLast().getElementType() == ElementType.TYPE) {
			staticOnly= true;
		}

		for (final IJavaElement element : findAllFieldsAndMethods(currentlyVisitedType, staticOnly)) {
			final ChainElement newEdge= createEdge(element);
			if (newEdge.getElementType() != null && !chain.contains(newEdge)) {
				incompleteChains.add(cloneChainAndAppendEdge(chain, newEdge));
			}
		}
	}

	private List<IJavaElement> findAllFieldsAndMethods(final ChainType chainElementType, boolean staticOnly) {
		List<IJavaElement> cached= fieldsAndMethodsCache.get(chainElementType.toString() + Boolean.toString(staticOnly));
		if (cached == null) {
			cached= new LinkedList<>();
			Collection<IJavaElement> candidates= staticOnly
					? ChainElementAnalyzer.findAllPublicStaticFieldsAndNonVoidNonPrimitiveStaticMethods(chainElementType, new ChainType(receiverType))
					: ChainElementAnalyzer.findVisibleInstanceFieldsAndRelevantInstanceMethods(chainElementType, new ChainType(receiverType));
			for (final IJavaElement e : candidates) {
				if (!ChainFinder.isFromExcludedType(excludedTypes, e)) {
					cached.add(e);
				}
			}
			fieldsAndMethodsCache.put(chainElementType.toString() + Boolean.toString(staticOnly), cached);
		}
		return cached;
	}

	private ChainElement createEdge(final IJavaElement member) {
		ChainElement cached= edgeCache.get(member);
		if (cached == null) {
			cached= new ChainElement(member, false);
			edgeCache.put(member, cached);
		}
		return cached;
	}

	private static LinkedList<ChainElement> cloneChainAndAppendEdge(final LinkedList<ChainElement> chain,
			final ChainElement newEdge) {
		@SuppressWarnings("unchecked")
		final LinkedList<ChainElement> chainCopy= (LinkedList<ChainElement>) chain.clone();
		chainCopy.add(newEdge);
		return chainCopy;
	}
}