001: /*******************************************************************************
002: * Copyright (c) 2000, 2007 IBM Corporation and others.
003: * All rights reserved. This program and the accompanying materials
004: * are made available under the terms of the Eclipse Public License v1.0
005: * which accompanies this distribution, and is available at
006: * http://www.eclipse.org/legal/epl-v10.html
007: *
008: * Contributors:
009: * IBM Corporation - initial API and implementation
010: *******************************************************************************/package org.eclipse.jdt.internal.core.hierarchy;
011:
012: import java.util.*;
013:
014: import org.eclipse.core.resources.IFile;
015: import org.eclipse.core.resources.IResource;
016: import org.eclipse.core.runtime.IPath;
017: import org.eclipse.core.runtime.IProgressMonitor;
018: import org.eclipse.core.runtime.NullProgressMonitor;
019: import org.eclipse.core.runtime.SubProgressMonitor;
020: import org.eclipse.jdt.core.*;
021: import org.eclipse.jdt.core.compiler.CharOperation;
022: import org.eclipse.jdt.core.search.*;
023: import org.eclipse.jdt.internal.compiler.env.AccessRuleSet;
024: import org.eclipse.jdt.internal.compiler.env.IBinaryType;
025: import org.eclipse.jdt.internal.compiler.env.ICompilationUnit;
026: import org.eclipse.jdt.internal.compiler.problem.DefaultProblemFactory;
027: import org.eclipse.jdt.internal.compiler.util.HashtableOfObject;
028: import org.eclipse.jdt.internal.compiler.util.HashtableOfObjectToInt;
029: import org.eclipse.jdt.internal.compiler.util.SuffixConstants;
030: import org.eclipse.jdt.internal.core.*;
031: import org.eclipse.jdt.internal.core.search.IndexQueryRequestor;
032: import org.eclipse.jdt.internal.core.search.JavaSearchParticipant;
033: import org.eclipse.jdt.internal.core.search.SubTypeSearchJob;
034: import org.eclipse.jdt.internal.core.search.indexing.IIndexConstants;
035: import org.eclipse.jdt.internal.core.search.indexing.IndexManager;
036: import org.eclipse.jdt.internal.core.search.matching.MatchLocator;
037: import org.eclipse.jdt.internal.core.search.matching.SuperTypeReferencePattern;
038: import org.eclipse.jdt.internal.core.util.HandleFactory;
039: import org.eclipse.jdt.internal.core.util.Util;
040:
041: public class IndexBasedHierarchyBuilder extends HierarchyBuilder
042: implements SuffixConstants {
043: public static final int MAXTICKS = 800; // heuristic so that there still progress for deep hierachies
044: /**
045: * A temporary cache of compilation units to handles to speed info
046: * to handle translation - it only contains the entries
047: * for the types in the region (in other words, it contains no supertypes outside
048: * the region).
049: */
050: protected Map cuToHandle;
051:
052: /**
053: * The scope this hierarchy builder should restrain results to.
054: */
055: protected IJavaSearchScope scope;
056:
057: /**
058: * Cache used to record binaries recreated from index matches
059: */
060: protected Map binariesFromIndexMatches;
061:
062: /**
063: * Collection used to queue subtype index queries
064: */
065: static class Queue {
066: public char[][] names = new char[10][];
067: public int start = 0;
068: public int end = -1;
069:
070: public void add(char[] name) {
071: if (++this .end == this .names.length) {
072: this .end -= this .start;
073: System.arraycopy(this .names, this .start,
074: this .names = new char[this .end * 2][], 0,
075: this .end);
076: this .start = 0;
077: }
078: this .names[this .end] = name;
079: }
080:
081: public char[] retrieve() {
082: if (this .start > this .end)
083: return null; // none
084:
085: char[] name = this .names[this .start++];
086: if (this .start > this .end) {
087: this .start = 0;
088: this .end = -1;
089: }
090: return name;
091: }
092:
093: public String toString() {
094: StringBuffer buffer = new StringBuffer("Queue:\n"); //$NON-NLS-1$
095: for (int i = this .start; i <= this .end; i++) {
096: buffer.append(this .names[i]).append('\n');
097: }
098: return buffer.toString();
099: }
100: }
101:
102: public IndexBasedHierarchyBuilder(TypeHierarchy hierarchy,
103: IJavaSearchScope scope) throws JavaModelException {
104: super (hierarchy);
105: this .cuToHandle = new HashMap(5);
106: this .binariesFromIndexMatches = new HashMap(10);
107: this .scope = scope;
108: }
109:
110: public void build(boolean computeSubtypes) {
111: JavaModelManager manager = JavaModelManager
112: .getJavaModelManager();
113: try {
114: // optimize access to zip files while building hierarchy
115: manager.cacheZipFiles();
116:
117: if (computeSubtypes) {
118: // Note by construction there always is a focus type here
119: IType focusType = getType();
120: boolean focusIsObject = focusType.getElementName()
121: .equals(new String(IIndexConstants.OBJECT));
122: int amountOfWorkForSubtypes = focusIsObject ? 5 : 80; // percentage of work needed to get possible subtypes
123: IProgressMonitor possibleSubtypesMonitor = this .hierarchy.progressMonitor == null ? null
124: : new SubProgressMonitor(
125: this .hierarchy.progressMonitor,
126: amountOfWorkForSubtypes);
127: HashSet localTypes = new HashSet(10); // contains the paths that have potential subtypes that are local/anonymous types
128: String[] allPossibleSubtypes;
129: if (((Member) focusType).getOuterMostLocalContext() == null) {
130: // top level or member type
131: allPossibleSubtypes = this
132: .determinePossibleSubTypes(localTypes,
133: possibleSubtypesMonitor);
134: } else {
135: // local or anonymous type
136: allPossibleSubtypes = CharOperation.NO_STRINGS;
137: }
138: if (allPossibleSubtypes != null) {
139: IProgressMonitor buildMonitor = this .hierarchy.progressMonitor == null ? null
140: : new SubProgressMonitor(
141: this .hierarchy.progressMonitor,
142: 100 - amountOfWorkForSubtypes);
143: this .hierarchy
144: .initialize(allPossibleSubtypes.length);
145: buildFromPotentialSubtypes(allPossibleSubtypes,
146: localTypes, buildMonitor);
147: }
148: } else {
149: this .hierarchy.initialize(1);
150: this .buildSupertypes();
151: }
152: } finally {
153: manager.flushZipFiles();
154: }
155: }
156:
157: private void buildForProject(JavaProject project,
158: ArrayList potentialSubtypes,
159: org.eclipse.jdt.core.ICompilationUnit[] workingCopies,
160: HashSet localTypes, IProgressMonitor monitor)
161: throws JavaModelException {
162: // resolve
163: int openablesLength = potentialSubtypes.size();
164: if (openablesLength > 0) {
165: // copy vectors into arrays
166: Openable[] openables = new Openable[openablesLength];
167: potentialSubtypes.toArray(openables);
168:
169: // sort in the order of roots and in reverse alphabetical order for .class file
170: // since requesting top level types in the process of caching an enclosing type is
171: // not supported by the lookup environment
172: IPackageFragmentRoot[] roots = project
173: .getPackageFragmentRoots();
174: int rootsLength = roots.length;
175: final HashtableOfObjectToInt indexes = new HashtableOfObjectToInt(
176: openablesLength);
177: for (int i = 0; i < openablesLength; i++) {
178: IJavaElement root = openables[i]
179: .getAncestor(IJavaElement.PACKAGE_FRAGMENT_ROOT);
180: int index;
181: for (index = 0; index < rootsLength; index++) {
182: if (roots[index].equals(root))
183: break;
184: }
185: indexes.put(openables[i], index);
186: }
187: Arrays.sort(openables, new Comparator() {
188: public int compare(Object a, Object b) {
189: int aIndex = indexes.get(a);
190: int bIndex = indexes.get(b);
191: if (aIndex != bIndex)
192: return aIndex - bIndex;
193: return ((Openable) b).getElementName().compareTo(
194: ((Openable) a).getElementName());
195: }
196: });
197:
198: IType focusType = this .getType();
199: boolean inProjectOfFocusType = focusType != null
200: && focusType.getJavaProject().equals(project);
201: org.eclipse.jdt.core.ICompilationUnit[] unitsToLookInside = null;
202: if (inProjectOfFocusType) {
203: org.eclipse.jdt.core.ICompilationUnit unitToLookInside = focusType
204: .getCompilationUnit();
205: if (unitToLookInside != null) {
206: int wcLength = workingCopies == null ? 0
207: : workingCopies.length;
208: if (wcLength == 0) {
209: unitsToLookInside = new org.eclipse.jdt.core.ICompilationUnit[] { unitToLookInside };
210: } else {
211: unitsToLookInside = new org.eclipse.jdt.core.ICompilationUnit[wcLength + 1];
212: unitsToLookInside[0] = unitToLookInside;
213: System.arraycopy(workingCopies, 0,
214: unitsToLookInside, 1, wcLength);
215: }
216: } else {
217: unitsToLookInside = workingCopies;
218: }
219: }
220:
221: SearchableEnvironment searchableEnvironment = project
222: .newSearchableNameEnvironment(unitsToLookInside);
223: this .nameLookup = searchableEnvironment.nameLookup;
224: Map options = project.getOptions(true);
225: // disable task tags to speed up parsing
226: options.put(JavaCore.COMPILER_TASK_TAGS, ""); //$NON-NLS-1$
227: this .hierarchyResolver = new HierarchyResolver(
228: searchableEnvironment, options, this ,
229: new DefaultProblemFactory());
230: if (focusType != null) {
231: Member declaringMember = ((Member) focusType)
232: .getOuterMostLocalContext();
233: if (declaringMember == null) {
234: // top level or member type
235: if (!inProjectOfFocusType) {
236: char[] typeQualifiedName = focusType
237: .getTypeQualifiedName('.')
238: .toCharArray();
239: String[] packageName = ((PackageFragment) focusType
240: .getPackageFragment()).names;
241: if (searchableEnvironment.findType(
242: typeQualifiedName, Util
243: .toCharArrays(packageName)) == null) {
244: // focus type is not visible in this project: no need to go further
245: return;
246: }
247: }
248: } else {
249: // local or anonymous type
250: Openable openable;
251: if (declaringMember.isBinary()) {
252: openable = (Openable) declaringMember
253: .getClassFile();
254: } else {
255: openable = (Openable) declaringMember
256: .getCompilationUnit();
257: }
258: localTypes = new HashSet();
259: localTypes.add(openable.getPath().toString());
260: this .hierarchyResolver.resolve(
261: new Openable[] { openable }, localTypes,
262: monitor);
263: return;
264: }
265: }
266: this .hierarchyResolver.resolve(openables, localTypes,
267: monitor);
268: }
269: }
270:
271: /**
272: * Configure this type hierarchy based on the given potential subtypes.
273: */
274: private void buildFromPotentialSubtypes(
275: String[] allPotentialSubTypes, HashSet localTypes,
276: IProgressMonitor monitor) {
277: IType focusType = this .getType();
278:
279: // substitute compilation units with working copies
280: HashMap wcPaths = new HashMap(); // a map from path to working copies
281: int wcLength;
282: org.eclipse.jdt.core.ICompilationUnit[] workingCopies = this .hierarchy.workingCopies;
283: if (workingCopies != null
284: && (wcLength = workingCopies.length) > 0) {
285: String[] newPaths = new String[wcLength];
286: for (int i = 0; i < wcLength; i++) {
287: org.eclipse.jdt.core.ICompilationUnit workingCopy = workingCopies[i];
288: String path = workingCopy.getPath().toString();
289: wcPaths.put(path, workingCopy);
290: newPaths[i] = path;
291: }
292: int potentialSubtypesLength = allPotentialSubTypes.length;
293: System
294: .arraycopy(
295: allPotentialSubTypes,
296: 0,
297: allPotentialSubTypes = new String[potentialSubtypesLength
298: + wcLength], 0,
299: potentialSubtypesLength);
300: System.arraycopy(newPaths, 0, allPotentialSubTypes,
301: potentialSubtypesLength, wcLength);
302: }
303:
304: int length = allPotentialSubTypes.length;
305:
306: // inject the compilation unit of the focus type (so that types in
307: // this cu have special visibility permission (this is also usefull
308: // when the cu is a working copy)
309: Openable focusCU = (Openable) focusType.getCompilationUnit();
310: String focusPath = null;
311: if (focusCU != null) {
312: focusPath = focusCU.getPath().toString();
313: if (length > 0) {
314: System.arraycopy(allPotentialSubTypes, 0,
315: allPotentialSubTypes = new String[length + 1],
316: 0, length);
317: allPotentialSubTypes[length] = focusPath;
318: } else {
319: allPotentialSubTypes = new String[] { focusPath };
320: }
321: length++;
322: }
323:
324: /*
325: * Sort in alphabetical order so that potential subtypes are grouped per project
326: */
327: Arrays.sort(allPotentialSubTypes);
328:
329: ArrayList potentialSubtypes = new ArrayList();
330: try {
331: // create element infos for subtypes
332: HandleFactory factory = new HandleFactory();
333: IJavaProject currentProject = null;
334: if (monitor != null)
335: monitor
336: .beginTask("", length * 2 /* 1 for build binding, 1 for connect hierarchy*/); //$NON-NLS-1$
337: for (int i = 0; i < length; i++) {
338: try {
339: String resourcePath = allPotentialSubTypes[i];
340:
341: // skip duplicate paths (e.g. if focus path was injected when it was already a potential subtype)
342: if (i > 0
343: && resourcePath
344: .equals(allPotentialSubTypes[i - 1]))
345: continue;
346:
347: Openable handle;
348: org.eclipse.jdt.core.ICompilationUnit workingCopy = (org.eclipse.jdt.core.ICompilationUnit) wcPaths
349: .get(resourcePath);
350: if (workingCopy != null) {
351: handle = (Openable) workingCopy;
352: } else {
353: handle = resourcePath.equals(focusPath) ? focusCU
354: : factory.createOpenable(resourcePath,
355: this .scope);
356: if (handle == null)
357: continue; // match is outside classpath
358: }
359:
360: IJavaProject project = handle.getJavaProject();
361: if (currentProject == null) {
362: currentProject = project;
363: potentialSubtypes = new ArrayList(5);
364: } else if (!currentProject.equals(project)) {
365: // build current project
366: this .buildForProject(
367: (JavaProject) currentProject,
368: potentialSubtypes, workingCopies,
369: localTypes, monitor);
370: currentProject = project;
371: potentialSubtypes = new ArrayList(5);
372: }
373:
374: potentialSubtypes.add(handle);
375: } catch (JavaModelException e) {
376: continue;
377: }
378: }
379:
380: // build last project
381: try {
382: if (currentProject == null) {
383: // case of no potential subtypes
384: currentProject = focusType.getJavaProject();
385: if (focusType.isBinary()) {
386: potentialSubtypes.add(focusType.getClassFile());
387: } else {
388: potentialSubtypes.add(focusType
389: .getCompilationUnit());
390: }
391: }
392: this .buildForProject((JavaProject) currentProject,
393: potentialSubtypes, workingCopies, localTypes,
394: monitor);
395: } catch (JavaModelException e) {
396: // ignore
397: }
398:
399: // Compute hierarchy of focus type if not already done (case of a type with potential subtypes that are not real subtypes)
400: if (!this .hierarchy.contains(focusType)) {
401: try {
402: currentProject = focusType.getJavaProject();
403: potentialSubtypes = new ArrayList();
404: if (focusType.isBinary()) {
405: potentialSubtypes.add(focusType.getClassFile());
406: } else {
407: potentialSubtypes.add(focusType
408: .getCompilationUnit());
409: }
410: this .buildForProject((JavaProject) currentProject,
411: potentialSubtypes, workingCopies,
412: localTypes, monitor);
413: } catch (JavaModelException e) {
414: // ignore
415: }
416: }
417:
418: // Add focus if not already in (case of a type with no explicit super type)
419: if (!this .hierarchy.contains(focusType)) {
420: this .hierarchy.addRootClass(focusType);
421: }
422: } finally {
423: if (monitor != null)
424: monitor.done();
425: }
426: }
427:
428: protected ICompilationUnit createCompilationUnitFromPath(
429: Openable handle, IFile file) {
430: ICompilationUnit unit = super .createCompilationUnitFromPath(
431: handle, file);
432: this .cuToHandle.put(unit, handle);
433: return unit;
434: }
435:
436: protected IBinaryType createInfoFromClassFile(Openable classFile,
437: IResource file) {
438: String documentPath = classFile.getPath().toString();
439: IBinaryType binaryType = (IBinaryType) this .binariesFromIndexMatches
440: .get(documentPath);
441: if (binaryType != null) {
442: this .infoToHandle.put(binaryType, classFile);
443: return binaryType;
444: } else {
445: return super .createInfoFromClassFile(classFile, file);
446: }
447: }
448:
449: protected IBinaryType createInfoFromClassFileInJar(
450: Openable classFile) {
451: String filePath = (((ClassFile) classFile).getType()
452: .getFullyQualifiedName('$')).replace('.', '/')
453: + SuffixConstants.SUFFIX_STRING_class;
454: IPackageFragmentRoot root = classFile.getPackageFragmentRoot();
455: IPath path = root.getPath();
456: // take the OS path for external jars, and the forward slash path for internal jars
457: String rootPath = path.getDevice() == null ? path.toString()
458: : path.toOSString();
459: String documentPath = rootPath
460: + IJavaSearchScope.JAR_FILE_ENTRY_SEPARATOR + filePath;
461: IBinaryType binaryType = (IBinaryType) this .binariesFromIndexMatches
462: .get(documentPath);
463: if (binaryType != null) {
464: this .infoToHandle.put(binaryType, classFile);
465: return binaryType;
466: } else {
467: return super .createInfoFromClassFileInJar(classFile);
468: }
469: }
470:
471: /**
472: * Returns all of the possible subtypes of this type hierarchy.
473: * Returns null if they could not be determine.
474: */
475: private String[] determinePossibleSubTypes(
476: final HashSet localTypes, IProgressMonitor monitor) {
477:
478: class PathCollector implements IPathRequestor {
479: HashSet paths = new HashSet(10);
480:
481: public void acceptPath(String path,
482: boolean containsLocalTypes) {
483: this .paths.add(path);
484: if (containsLocalTypes) {
485: localTypes.add(path);
486: }
487: }
488: }
489: PathCollector collector = new PathCollector();
490:
491: try {
492: if (monitor != null)
493: monitor.beginTask("", MAXTICKS); //$NON-NLS-1$
494: searchAllPossibleSubTypes(this .getType(), this .scope,
495: this .binariesFromIndexMatches, collector,
496: IJavaSearchConstants.WAIT_UNTIL_READY_TO_SEARCH,
497: monitor);
498: } finally {
499: if (monitor != null)
500: monitor.done();
501: }
502:
503: HashSet paths = collector.paths;
504: int length = paths.size();
505: String[] result = new String[length];
506: int count = 0;
507: for (Iterator iter = paths.iterator(); iter.hasNext();) {
508: result[count++] = (String) iter.next();
509: }
510: return result;
511: }
512:
513: /**
514: * Find the set of candidate subtypes of a given type.
515: *
516: * The requestor is notified of super type references (with actual path of
517: * its occurrence) for all types which are potentially involved inside a particular
518: * hierarchy.
519: * The match locator is not used here to narrow down the results, the type hierarchy
520: * resolver is rather used to compute the whole hierarchy at once.
521: * @param type
522: * @param scope
523: * @param binariesFromIndexMatches
524: * @param pathRequestor
525: * @param waitingPolicy
526: * @param progressMonitor
527: */
528: public static void searchAllPossibleSubTypes(IType type,
529: IJavaSearchScope scope, final Map binariesFromIndexMatches,
530: final IPathRequestor pathRequestor, int waitingPolicy, // WaitUntilReadyToSearch | ForceImmediateSearch | CancelIfNotReadyToSearch
531: final IProgressMonitor progressMonitor) {
532:
533: /* embed constructs inside arrays so as to pass them to (inner) collector */
534: final Queue queue = new Queue();
535: final HashtableOfObject foundSuperNames = new HashtableOfObject(
536: 5);
537:
538: IndexManager indexManager = JavaModelManager.getIndexManager();
539:
540: /* use a special collector to collect paths and queue new subtype names */
541: IndexQueryRequestor searchRequestor = new IndexQueryRequestor() {
542: public boolean acceptIndexMatch(String documentPath,
543: SearchPattern indexRecord,
544: SearchParticipant participant, AccessRuleSet access) {
545: SuperTypeReferencePattern record = (SuperTypeReferencePattern) indexRecord;
546: boolean isLocalOrAnonymous = record.enclosingTypeName == IIndexConstants.ONE_ZERO;
547: pathRequestor.acceptPath(documentPath,
548: isLocalOrAnonymous);
549: char[] typeName = record.simpleName;
550: int suffix = documentPath.toLowerCase().lastIndexOf(
551: SUFFIX_STRING_class);
552: if (suffix != -1) {
553: HierarchyBinaryType binaryType = (HierarchyBinaryType) binariesFromIndexMatches
554: .get(documentPath);
555: if (binaryType == null) {
556: char[] enclosingTypeName = record.enclosingTypeName;
557: if (isLocalOrAnonymous) {
558: int lastSlash = documentPath
559: .lastIndexOf('/');
560: int lastDollar = documentPath
561: .lastIndexOf('$');
562: if (lastDollar == -1) {
563: // malformed local or anonymous type: it doesn't contain a $ in its name
564: // treat it as a top level type
565: enclosingTypeName = null;
566: typeName = documentPath.substring(
567: lastSlash + 1, suffix)
568: .toCharArray();
569: } else {
570: enclosingTypeName = documentPath
571: .substring(lastSlash + 1,
572: lastDollar)
573: .toCharArray();
574: typeName = documentPath.substring(
575: lastDollar + 1, suffix)
576: .toCharArray();
577: }
578: }
579: binaryType = new HierarchyBinaryType(
580: record.modifiers, record.pkgName,
581: typeName, enclosingTypeName,
582: record.typeParameterSignatures,
583: record.classOrInterface);
584: binariesFromIndexMatches.put(documentPath,
585: binaryType);
586: }
587: binaryType.recordSuperType(record.super SimpleName,
588: record.super Qualification,
589: record.super ClassOrInterface);
590: }
591: if (!isLocalOrAnonymous // local or anonymous types cannot have subtypes outside the cu that define them
592: && !foundSuperNames.containsKey(typeName)) {
593: foundSuperNames.put(typeName, typeName);
594: queue.add(typeName);
595: }
596: return true;
597: }
598: };
599:
600: int super RefKind;
601: try {
602: super RefKind = type.isClass() ? SuperTypeReferencePattern.ONLY_SUPER_CLASSES
603: : SuperTypeReferencePattern.ALL_SUPER_TYPES;
604: } catch (JavaModelException e) {
605: super RefKind = SuperTypeReferencePattern.ALL_SUPER_TYPES;
606: }
607: SuperTypeReferencePattern pattern = new SuperTypeReferencePattern(
608: null, null, super RefKind, SearchPattern.R_EXACT_MATCH
609: | SearchPattern.R_CASE_SENSITIVE);
610: MatchLocator.setFocus(pattern, type);
611: SubTypeSearchJob job = new SubTypeSearchJob(pattern,
612: new JavaSearchParticipant(), // java search only
613: scope, searchRequestor);
614:
615: int ticks = 0;
616: queue.add(type.getElementName().toCharArray());
617: try {
618: while (queue.start <= queue.end) {
619: if (progressMonitor != null
620: && progressMonitor.isCanceled())
621: return;
622:
623: // all subclasses of OBJECT are actually all types
624: char[] currentTypeName = queue.retrieve();
625: if (CharOperation.equals(currentTypeName,
626: IIndexConstants.OBJECT))
627: currentTypeName = null;
628:
629: // search all index references to a given supertype
630: pattern.super SimpleName = currentTypeName;
631: indexManager.performConcurrentJob(job, waitingPolicy,
632: progressMonitor == null ? null
633: : new NullProgressMonitor() {
634: // don't report progress since this is too costly for deep hierarchies
635: // just handle isCanceled() (seehttps://bugs.eclipse.org/bugs/show_bug.cgi?id=179511)
636: public void setCanceled(
637: boolean value) {
638: progressMonitor
639: .setCanceled(value);
640: }
641:
642: public boolean isCanceled() {
643: return progressMonitor
644: .isCanceled();
645: }
646: });
647: if (progressMonitor != null && ++ticks <= MAXTICKS)
648: progressMonitor.worked(1);
649:
650: // in case, we search all subtypes, no need to search further
651: if (currentTypeName == null)
652: break;
653: }
654: } finally {
655: job.finished();
656: }
657: }
658: }
|