Thu, 12 Jan 2012 15:28:34 +0000
7123100: javac fails with java.lang.StackOverflowError
Summary: Inference of under-constrained type-variables creates erroneous recursive wildcard types
Reviewed-by: jjg
1 /*
2 * Copyright (c) 2009, 2011, Oracle and/or its affiliates. All rights reserved.
3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
4 *
5 * This code is free software; you can redistribute it and/or modify it
6 * under the terms of the GNU General Public License version 2 only, as
7 * published by the Free Software Foundation. Oracle designates this
8 * particular file as subject to the "Classpath" exception as provided
9 * by Oracle in the LICENSE file that accompanied this code.
10 *
11 * This code is distributed in the hope that it will be useful, but WITHOUT
12 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
14 * version 2 for more details (a copy is included in the LICENSE file that
15 * accompanied this code).
16 *
17 * You should have received a copy of the GNU General Public License version
18 * 2 along with this work; if not, write to the Free Software Foundation,
19 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
20 *
21 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
22 * or visit www.oracle.com if you need additional information or have any
23 * questions.
24 */
25 package com.sun.tools.classfile;
27 import java.util.Deque;
28 import java.util.HashMap;
29 import java.util.HashSet;
30 import java.util.LinkedList;
31 import java.util.List;
32 import java.util.Map;
33 import java.util.Set;
34 import java.util.regex.Pattern;
36 import com.sun.tools.classfile.Dependency.Finder;
37 import com.sun.tools.classfile.Dependency.Filter;
38 import com.sun.tools.classfile.Dependency.Location;
39 import com.sun.tools.classfile.Type.ArrayType;
40 import com.sun.tools.classfile.Type.ClassSigType;
41 import com.sun.tools.classfile.Type.ClassType;
42 import com.sun.tools.classfile.Type.MethodType;
43 import com.sun.tools.classfile.Type.SimpleType;
44 import com.sun.tools.classfile.Type.TypeParamType;
45 import com.sun.tools.classfile.Type.WildcardType;
47 import static com.sun.tools.classfile.ConstantPool.*;
49 /**
50 * A framework for determining {@link Dependency dependencies} between class files.
51 *
52 * A {@link Dependency.Finder finder} is used to identify the dependencies of
53 * individual classes. Some finders may return subtypes of {@code Dependency} to
54 * further characterize the type of dependency, such as a dependency on a
55 * method within a class.
56 *
57 * A {@link Dependency.Filter filter} may be used to restrict the set of
58 * dependencies found by a finder.
59 *
60 * Dependencies that are found may be passed to a {@link Dependencies.Recorder
61 * recorder} so that the dependencies can be stored in a custom data structure.
62 */
63 public class Dependencies {
64 /**
65 * Thrown when a class file cannot be found.
66 */
67 public static class ClassFileNotFoundException extends Exception {
68 private static final long serialVersionUID = 3632265927794475048L;
70 public ClassFileNotFoundException(String className) {
71 super(className);
72 this.className = className;
73 }
75 public ClassFileNotFoundException(String className, Throwable cause) {
76 this(className);
77 initCause(cause);
78 }
80 public final String className;
81 }
83 /**
84 * Thrown when an exception is found processing a class file.
85 */
86 public static class ClassFileError extends Error {
87 private static final long serialVersionUID = 4111110813961313203L;
89 public ClassFileError(Throwable cause) {
90 initCause(cause);
91 }
92 }
94 /**
95 * Service provider interface to locate and read class files.
96 */
97 public interface ClassFileReader {
98 /**
99 * Get the ClassFile object for a specified class.
100 * @param className the name of the class to be returned.
101 * @return the ClassFile for the given class
102 * @throws Dependencies#ClassFileNotFoundException if the classfile cannot be
103 * found
104 */
105 public ClassFile getClassFile(String className)
106 throws ClassFileNotFoundException;
107 }
109 /**
110 * Service provide interface to handle results.
111 */
112 public interface Recorder {
113 /**
114 * Record a dependency that has been found.
115 * @param d
116 */
117 public void addDependency(Dependency d);
118 }
120 /**
121 * Get the default finder used to locate the dependencies for a class.
122 * @return the default finder
123 */
124 public static Finder getDefaultFinder() {
125 return new APIDependencyFinder(AccessFlags.ACC_PRIVATE);
126 }
128 /**
129 * Get a finder used to locate the API dependencies for a class.
130 * These include the superclass, superinterfaces, and classes referenced in
131 * the declarations of fields and methods. The fields and methods that
132 * are checked can be limited according to a specified access.
133 * The access parameter must be one of {@link AccessFlags#ACC_PUBLIC ACC_PUBLIC},
134 * {@link AccessFlags#ACC_PRIVATE ACC_PRIVATE},
135 * {@link AccessFlags#ACC_PROTECTED ACC_PROTECTED}, or 0 for
136 * package private access. Members with greater than or equal accessibility
137 * to that specified will be searched for dependencies.
138 * @param access the access of members to be checked
139 * @return an API finder
140 */
141 public static Finder getAPIFinder(int access) {
142 return new APIDependencyFinder(access);
143 }
145 /**
146 * Get the finder used to locate the dependencies for a class.
147 * @return the finder
148 */
149 public Finder getFinder() {
150 if (finder == null)
151 finder = getDefaultFinder();
152 return finder;
153 }
155 /**
156 * Set the finder used to locate the dependencies for a class.
157 * @param f the finder
158 */
159 public void setFinder(Finder f) {
160 f.getClass(); // null check
161 finder = f;
162 }
164 /**
165 * Get the default filter used to determine included when searching
166 * the transitive closure of all the dependencies.
167 * Unless overridden, the default filter accepts all dependencies.
168 * @return the default filter.
169 */
170 public static Filter getDefaultFilter() {
171 return DefaultFilter.instance();
172 }
174 /**
175 * Get a filter which uses a regular expression on the target's class name
176 * to determine if a dependency is of interest.
177 * @param pattern the pattern used to match the target's class name
178 * @return a filter for matching the target class name with a regular expression
179 */
180 public static Filter getRegexFilter(Pattern pattern) {
181 return new TargetRegexFilter(pattern);
182 }
184 /**
185 * Get a filter which checks the package of a target's class name
186 * to determine if a dependency is of interest. The filter checks if the
187 * package of the target's class matches any of a set of given package
188 * names. The match may optionally match subpackages of the given names as well.
189 * @param packageNames the package names used to match the target's class name
190 * @param matchSubpackages whether or not to match subpackages as well
191 * @return a filter for checking the target package name against a list of package names
192 */
193 public static Filter getPackageFilter(Set<String> packageNames, boolean matchSubpackages) {
194 return new TargetPackageFilter(packageNames, matchSubpackages);
195 }
197 /**
198 * Get the filter used to determine the dependencies included when searching
199 * the transitive closure of all the dependencies.
200 * Unless overridden, the default filter accepts all dependencies.
201 * @return the filter
202 */
203 public Filter getFilter() {
204 if (filter == null)
205 filter = getDefaultFilter();
206 return filter;
207 }
209 /**
210 * Set the filter used to determine the dependencies included when searching
211 * the transitive closure of all the dependencies.
212 * @param f the filter
213 */
214 public void setFilter(Filter f) {
215 f.getClass(); // null check
216 filter = f;
217 }
219 /**
220 * Find the dependencies of a class, using the current
221 * {@link Dependencies#getFinder finder} and
222 * {@link Dependencies#getFilter filter}.
223 * The search may optionally include the transitive closure of all the
224 * filtered dependencies, by also searching in the classes named in those
225 * dependencies.
226 * @param classFinder a finder to locate class files
227 * @param rootClassNames the names of the root classes from which to begin
228 * searching
229 * @param transitiveClosure whether or not to also search those classes
230 * named in any filtered dependencies that are found.
231 * @return the set of dependencies that were found
232 * @throws ClassFileNotFoundException if a required class file cannot be found
233 * @throws ClassFileError if an error occurs while processing a class file,
234 * such as an error in the internal class file structure.
235 */
236 public Set<Dependency> findAllDependencies(
237 ClassFileReader classFinder, Set<String> rootClassNames,
238 boolean transitiveClosure)
239 throws ClassFileNotFoundException {
240 final Set<Dependency> results = new HashSet<Dependency>();
241 Recorder r = new Recorder() {
242 public void addDependency(Dependency d) {
243 results.add(d);
244 }
245 };
246 findAllDependencies(classFinder, rootClassNames, transitiveClosure, r);
247 return results;
248 }
252 /**
253 * Find the dependencies of a class, using the current
254 * {@link Dependencies#getFinder finder} and
255 * {@link Dependencies#getFilter filter}.
256 * The search may optionally include the transitive closure of all the
257 * filtered dependencies, by also searching in the classes named in those
258 * dependencies.
259 * @param classFinder a finder to locate class files
260 * @param rootClassNames the names of the root classes from which to begin
261 * searching
262 * @param transitiveClosure whether or not to also search those classes
263 * named in any filtered dependencies that are found.
264 * @param recorder a recorder for handling the results
265 * @throws ClassFileNotFoundException if a required class file cannot be found
266 * @throws ClassFileError if an error occurs while processing a class file,
267 * such as an error in the internal class file structure.
268 */
269 public void findAllDependencies(
270 ClassFileReader classFinder, Set<String> rootClassNames,
271 boolean transitiveClosure, Recorder recorder)
272 throws ClassFileNotFoundException {
273 Set<String> doneClasses = new HashSet<String>();
275 getFinder(); // ensure initialized
276 getFilter(); // ensure initialized
278 // Work queue of names of classfiles to be searched.
279 // Entries will be unique, and for classes that do not yet have
280 // dependencies in the results map.
281 Deque<String> deque = new LinkedList<String>(rootClassNames);
283 String className;
284 while ((className = deque.poll()) != null) {
285 assert (!doneClasses.contains(className));
286 doneClasses.add(className);
288 ClassFile cf = classFinder.getClassFile(className);
290 // The following code just applies the filter to the dependencies
291 // followed for the transitive closure.
292 for (Dependency d: finder.findDependencies(cf)) {
293 recorder.addDependency(d);
294 if (transitiveClosure && filter.accepts(d)) {
295 String cn = d.getTarget().getClassName();
296 if (!doneClasses.contains(cn))
297 deque.add(cn);
298 }
299 }
300 }
301 }
303 private Filter filter;
304 private Finder finder;
306 /**
307 * A location identifying a class.
308 */
309 static class SimpleLocation implements Location {
310 public SimpleLocation(String className) {
311 this.className = className;
312 }
314 /**
315 * Get the name of the class being depended on. This name will be used to
316 * locate the class file for transitive dependency analysis.
317 * @return the name of the class being depended on
318 */
319 public String getClassName() {
320 return className;
321 }
323 @Override
324 public boolean equals(Object other) {
325 if (this == other)
326 return true;
327 if (!(other instanceof SimpleLocation))
328 return false;
329 return (className.equals(((SimpleLocation) other).className));
330 }
332 @Override
333 public int hashCode() {
334 return className.hashCode();
335 }
337 @Override
338 public String toString() {
339 return className;
340 }
342 private String className;
343 }
345 /**
346 * A dependency of one class on another.
347 */
348 static class SimpleDependency implements Dependency {
349 public SimpleDependency(Location origin, Location target) {
350 this.origin = origin;
351 this.target = target;
352 }
354 public Location getOrigin() {
355 return origin;
356 }
358 public Location getTarget() {
359 return target;
360 }
362 @Override
363 public boolean equals(Object other) {
364 if (this == other)
365 return true;
366 if (!(other instanceof SimpleDependency))
367 return false;
368 SimpleDependency o = (SimpleDependency) other;
369 return (origin.equals(o.origin) && target.equals(o.target));
370 }
372 @Override
373 public int hashCode() {
374 return origin.hashCode() * 31 + target.hashCode();
375 }
377 @Override
378 public String toString() {
379 return origin + ":" + target;
380 }
382 private Location origin;
383 private Location target;
384 }
387 /**
388 * This class accepts all dependencies.
389 */
390 static class DefaultFilter implements Filter {
391 private static DefaultFilter instance;
393 static DefaultFilter instance() {
394 if (instance == null)
395 instance = new DefaultFilter();
396 return instance;
397 }
399 public boolean accepts(Dependency dependency) {
400 return true;
401 }
402 }
404 /**
405 * This class accepts those dependencies whose target's class name matches a
406 * regular expression.
407 */
408 static class TargetRegexFilter implements Filter {
409 TargetRegexFilter(Pattern pattern) {
410 this.pattern = pattern;
411 }
413 public boolean accepts(Dependency dependency) {
414 return pattern.matcher(dependency.getTarget().getClassName()).matches();
415 }
417 private final Pattern pattern;
418 }
420 /**
421 * This class accepts those dependencies whose class name is in a given
422 * package.
423 */
424 static class TargetPackageFilter implements Filter {
425 TargetPackageFilter(Set<String> packageNames, boolean matchSubpackages) {
426 for (String pn: packageNames) {
427 if (pn.length() == 0) // implies null check as well
428 throw new IllegalArgumentException();
429 }
430 this.packageNames = packageNames;
431 this.matchSubpackages = matchSubpackages;
432 }
434 public boolean accepts(Dependency dependency) {
435 String cn = dependency.getTarget().getClassName();
436 int lastSep = cn.lastIndexOf("/");
437 String pn = (lastSep == -1 ? "" : cn.substring(0, lastSep));
438 if (packageNames.contains(pn))
439 return true;
441 if (matchSubpackages) {
442 for (String n: packageNames) {
443 if (pn.startsWith(n + "."))
444 return true;
445 }
446 }
448 return false;
449 }
451 private final Set<String> packageNames;
452 private final boolean matchSubpackages;
453 }
457 /**
458 * This class identifies class names directly or indirectly in the constant pool.
459 */
460 static class ClassDependencyFinder extends BasicDependencyFinder {
461 public Iterable<? extends Dependency> findDependencies(ClassFile classfile) {
462 Visitor v = new Visitor(classfile);
463 for (CPInfo cpInfo: classfile.constant_pool.entries()) {
464 v.scan(cpInfo);
465 }
466 return v.deps;
467 }
468 }
470 /**
471 * This class identifies class names in the signatures of classes, fields,
472 * and methods in a class.
473 */
474 static class APIDependencyFinder extends BasicDependencyFinder {
475 APIDependencyFinder(int access) {
476 switch (access) {
477 case AccessFlags.ACC_PUBLIC:
478 case AccessFlags.ACC_PROTECTED:
479 case AccessFlags.ACC_PRIVATE:
480 case 0:
481 showAccess = access;
482 break;
483 default:
484 throw new IllegalArgumentException("invalid access 0x"
485 + Integer.toHexString(access));
486 }
487 }
489 public Iterable<? extends Dependency> findDependencies(ClassFile classfile) {
490 try {
491 Visitor v = new Visitor(classfile);
492 v.addClass(classfile.super_class);
493 v.addClasses(classfile.interfaces);
494 // inner classes?
495 for (Field f : classfile.fields) {
496 if (checkAccess(f.access_flags))
497 v.scan(f.descriptor, f.attributes);
498 }
499 for (Method m : classfile.methods) {
500 if (checkAccess(m.access_flags)) {
501 v.scan(m.descriptor, m.attributes);
502 Exceptions_attribute e =
503 (Exceptions_attribute) m.attributes.get(Attribute.Exceptions);
504 if (e != null)
505 v.addClasses(e.exception_index_table);
506 }
507 }
508 return v.deps;
509 } catch (ConstantPoolException e) {
510 throw new ClassFileError(e);
511 }
512 }
514 boolean checkAccess(AccessFlags flags) {
515 // code copied from javap.Options.checkAccess
516 boolean isPublic = flags.is(AccessFlags.ACC_PUBLIC);
517 boolean isProtected = flags.is(AccessFlags.ACC_PROTECTED);
518 boolean isPrivate = flags.is(AccessFlags.ACC_PRIVATE);
519 boolean isPackage = !(isPublic || isProtected || isPrivate);
521 if ((showAccess == AccessFlags.ACC_PUBLIC) && (isProtected || isPrivate || isPackage))
522 return false;
523 else if ((showAccess == AccessFlags.ACC_PROTECTED) && (isPrivate || isPackage))
524 return false;
525 else if ((showAccess == 0) && (isPrivate))
526 return false;
527 else
528 return true;
529 }
531 private int showAccess;
532 }
534 static abstract class BasicDependencyFinder implements Finder {
535 private Map<String,Location> locations = new HashMap<String,Location>();
537 Location getLocation(String className) {
538 Location l = locations.get(className);
539 if (l == null)
540 locations.put(className, l = new SimpleLocation(className));
541 return l;
542 }
544 class Visitor implements ConstantPool.Visitor<Void,Void>, Type.Visitor<Void, Void> {
545 private ConstantPool constant_pool;
546 private Location origin;
547 Set<Dependency> deps;
549 Visitor(ClassFile classFile) {
550 try {
551 constant_pool = classFile.constant_pool;
552 origin = getLocation(classFile.getName());
553 deps = new HashSet<Dependency>();
554 } catch (ConstantPoolException e) {
555 throw new ClassFileError(e);
556 }
557 }
559 void scan(Descriptor d, Attributes attrs) {
560 try {
561 scan(new Signature(d.index).getType(constant_pool));
562 Signature_attribute sa = (Signature_attribute) attrs.get(Attribute.Signature);
563 if (sa != null)
564 scan(new Signature(sa.signature_index).getType(constant_pool));
565 } catch (ConstantPoolException e) {
566 throw new ClassFileError(e);
567 }
568 }
570 void scan(CPInfo cpInfo) {
571 cpInfo.accept(this, null);
572 }
574 void scan(Type t) {
575 t.accept(this, null);
576 }
578 void addClass(int index) throws ConstantPoolException {
579 if (index != 0) {
580 String name = constant_pool.getClassInfo(index).getBaseName();
581 if (name != null)
582 addDependency(name);
583 }
584 }
586 void addClasses(int[] indices) throws ConstantPoolException {
587 for (int i: indices)
588 addClass(i);
589 }
591 private void addDependency(String name) {
592 deps.add(new SimpleDependency(origin, getLocation(name)));
593 }
595 // ConstantPool.Visitor methods
597 public Void visitClass(CONSTANT_Class_info info, Void p) {
598 try {
599 if (info.getName().startsWith("["))
600 new Signature(info.name_index).getType(constant_pool).accept(this, null);
601 else
602 addDependency(info.getBaseName());
603 return null;
604 } catch (ConstantPoolException e) {
605 throw new ClassFileError(e);
606 }
607 }
609 public Void visitDouble(CONSTANT_Double_info info, Void p) {
610 return null;
611 }
613 public Void visitFieldref(CONSTANT_Fieldref_info info, Void p) {
614 return visitRef(info, p);
615 }
617 public Void visitFloat(CONSTANT_Float_info info, Void p) {
618 return null;
619 }
621 public Void visitInteger(CONSTANT_Integer_info info, Void p) {
622 return null;
623 }
625 public Void visitInterfaceMethodref(CONSTANT_InterfaceMethodref_info info, Void p) {
626 return visitRef(info, p);
627 }
629 public Void visitInvokeDynamic(CONSTANT_InvokeDynamic_info info, Void p) {
630 return null;
631 }
633 public Void visitLong(CONSTANT_Long_info info, Void p) {
634 return null;
635 }
637 public Void visitMethodHandle(CONSTANT_MethodHandle_info info, Void p) {
638 return null;
639 }
641 public Void visitMethodType(CONSTANT_MethodType_info info, Void p) {
642 return null;
643 }
645 public Void visitMethodref(CONSTANT_Methodref_info info, Void p) {
646 return visitRef(info, p);
647 }
649 public Void visitNameAndType(CONSTANT_NameAndType_info info, Void p) {
650 try {
651 new Signature(info.type_index).getType(constant_pool).accept(this, null);
652 return null;
653 } catch (ConstantPoolException e) {
654 throw new ClassFileError(e);
655 }
656 }
658 public Void visitString(CONSTANT_String_info info, Void p) {
659 return null;
660 }
662 public Void visitUtf8(CONSTANT_Utf8_info info, Void p) {
663 return null;
664 }
666 private Void visitRef(CPRefInfo info, Void p) {
667 try {
668 visitClass(info.getClassInfo(), p);
669 return null;
670 } catch (ConstantPoolException e) {
671 throw new ClassFileError(e);
672 }
673 }
675 // Type.Visitor methods
677 private void findDependencies(Type t) {
678 if (t != null)
679 t.accept(this, null);
680 }
682 private void findDependencies(List<? extends Type> ts) {
683 if (ts != null) {
684 for (Type t: ts)
685 t.accept(this, null);
686 }
687 }
689 public Void visitSimpleType(SimpleType type, Void p) {
690 return null;
691 }
693 public Void visitArrayType(ArrayType type, Void p) {
694 findDependencies(type.elemType);
695 return null;
696 }
698 public Void visitMethodType(MethodType type, Void p) {
699 findDependencies(type.paramTypes);
700 findDependencies(type.returnType);
701 findDependencies(type.throwsTypes);
702 return null;
703 }
705 public Void visitClassSigType(ClassSigType type, Void p) {
706 findDependencies(type.superclassType);
707 findDependencies(type.superinterfaceTypes);
708 return null;
709 }
711 public Void visitClassType(ClassType type, Void p) {
712 findDependencies(type.outerType);
713 addDependency(type.name);
714 findDependencies(type.typeArgs);
715 return null;
716 }
718 public Void visitTypeParamType(TypeParamType type, Void p) {
719 findDependencies(type.classBound);
720 findDependencies(type.interfaceBounds);
721 return null;
722 }
724 public Void visitWildcardType(WildcardType type, Void p) {
725 findDependencies(type.boundType);
726 return null;
727 }
728 }
729 }
730 }