pkg/compiler/lib/src/universe/class_hierarchy.dart - sdk.git - Git at Google

 // Copyright (c) 2017, the Dart project authors.  Please see the AUTHORS file
 // for details. All rights reserved. Use of this source code is governed by a
 // BSD-style license that can be found in the LICENSE file.

 import '../common.dart';
 import '../common_elements.dart';
 import '../elements/entities.dart';
 import '../elements/types.dart' show InterfaceType;
 import 'class_set.dart';

 // TODO(johnniwinther): Move more methods from `JClosedWorld` to
 // `ClassHierarchy`.
 abstract class ClassHierarchy {
   /// Returns [ClassHierarchyNode] for [cls] used to model the class hierarchies
   /// of known classes.
   ///
   /// This method is only provided for testing. For queries on classes, use the
   /// methods defined in [JClosedWorld].
   ClassHierarchyNode getClassHierarchyNode(ClassEntity cls);

   /// Returns [ClassSet] for [cls] used to model the extends and implements
   /// relations of known classes.
   ///
   /// This method is only provided for testing. For queries on classes, use the
   /// methods defined in [JClosedWorld].
   ClassSet getClassSet(ClassEntity cls);

   /// Returns `true` if [x] is a subtype of [y], that is, if [x] implements an
   /// instance of [y].
   bool isSubtypeOf(ClassEntity x, ClassEntity y);

   /// Returns a [SubclassResult] for the subclasses that are contained in
   /// the subclass/subtype sets of both [cls1] and [cls2].
   ///
   /// Classes that are implied by included superclasses/supertypes are not
   /// returned.
   ///
   /// For instance for this hierarchy
   ///
   ///     class A {}
   ///     class B {}
   ///     class C implements A, B {}
   ///     class D extends C {}
   ///
   /// the query
   ///
   ///     commonSubclasses(A, ClassQuery.SUBTYPE, B, ClassQuery.SUBTYPE)
   ///
   /// return the set {C} because [D] is implied by [C].
   SubclassResult commonSubclasses(
       ClassEntity cls1, ClassQuery query1, ClassEntity cls2, ClassQuery query2);

   /// Returns an iterable over the directly instantiated that implement [cls]
   /// possibly including [cls] itself, if it is live.
   Iterable<ClassEntity> subtypesOf(ClassEntity cls);

   /// Returns an iterable over the live classes that extend [cls] including
   /// [cls] itself.
   Iterable<ClassEntity> subclassesOf(ClassEntity cls);

   /// Applies [f] to each live class that implements [cls] _not_ including [cls]
   /// itself.
   void forEachStrictSubtypeOf(
       ClassEntity cls, IterationStep f(ClassEntity cls));
 }

 class ClassHierarchyImpl implements ClassHierarchy {
   final CommonElements _commonElements;
   final Map<ClassEntity, ClassHierarchyNode> _classHierarchyNodes;
   final Map<ClassEntity, ClassSet> _classSets;

   ClassHierarchyImpl(
       this._commonElements, this._classHierarchyNodes, this._classSets);

   /// Returns [ClassHierarchyNode] for [cls] used to model the class hierarchies
   /// of known classes.
   ///
   /// This method is only provided for testing. For queries on classes, use the
   /// methods defined in [JClosedWorld].
   ClassHierarchyNode getClassHierarchyNode(ClassEntity cls) {
     return _classHierarchyNodes[cls];
   }

   /// Returns [ClassSet] for [cls] used to model the extends and implements
   /// relations of known classes.
   ///
   /// This method is only provided for testing. For queries on classes, use the
   /// methods defined in [JClosedWorld].
   ClassSet getClassSet(ClassEntity cls) {
     return _classSets[cls];
   }

   /// Returns `true` if [x] is a subtype of [y], that is, if [x] implements an
   /// instance of [y].
   bool isSubtypeOf(ClassEntity x, ClassEntity y) {
     ClassSet classSet = _classSets[y];
     assert(classSet != null,
         failedAt(y, "No ClassSet for $y (${y.runtimeType}): ${_classSets}"));
     ClassHierarchyNode classHierarchyNode = _classHierarchyNodes[x];
     assert(classHierarchyNode != null,
         failedAt(x, "No ClassHierarchyNode for $x"));
     return classSet.hasSubtype(classHierarchyNode);
   }

   /// Return `true` if [x] is a (non-strict) subclass of [y].
   bool isSubclassOf(ClassEntity x, ClassEntity y) {
     return _classHierarchyNodes[y].hasSubclass(_classHierarchyNodes[x]);
   }

   /// Returns an iterable over the directly instantiated that implement [cls]
   /// possibly including [cls] itself, if it is live.
   Iterable<ClassEntity> subtypesOf(ClassEntity cls) {
     ClassSet classSet = _classSets[cls];
     if (classSet == null) {
       return const <ClassEntity>[];
     } else {
       return classSet
           .subtypesByMask(ClassHierarchyNode.EXPLICITLY_INSTANTIATED);
     }
   }

   /// Returns an iterable over the directly instantiated classes that extend
   /// [cls] possibly including [cls] itself, if it is live.
   Iterable<ClassEntity> subclassesOf(ClassEntity cls) {
     ClassHierarchyNode hierarchy = _classHierarchyNodes[cls];
     if (hierarchy == null) return const <ClassEntity>[];
     return hierarchy
         .subclassesByMask(ClassHierarchyNode.EXPLICITLY_INSTANTIATED);
   }

   /// Returns an iterable over the directly instantiated that implement [cls]
   /// _not_ including [cls].
   Iterable<ClassEntity> strictSubtypesOf(ClassEntity cls) {
     ClassSet classSet = _classSets[cls];
     if (classSet == null) {
       return const <ClassEntity>[];
     } else {
       return classSet.subtypesByMask(ClassHierarchyNode.EXPLICITLY_INSTANTIATED,
           strict: true);
     }
   }

   /// Returns an iterable over the directly instantiated classes that extend
   /// [cls] _not_ including [cls] itself.
   Iterable<ClassEntity> strictSubclassesOf(ClassEntity cls) {
     ClassHierarchyNode subclasses = _classHierarchyNodes[cls];
     if (subclasses == null) return const <ClassEntity>[];
     return subclasses.subclassesByMask(
         ClassHierarchyNode.EXPLICITLY_INSTANTIATED,
         strict: true);
   }

   /// Applies [f] to each live class that extend [cls] _not_ including [cls]
   /// itself.
   void forEachStrictSubclassOf(
       ClassEntity cls, IterationStep f(ClassEntity cls)) {
     ClassHierarchyNode subclasses = _classHierarchyNodes[cls];
     if (subclasses == null) return;
     subclasses.forEachSubclass(f, ClassHierarchyNode.EXPLICITLY_INSTANTIATED,
         strict: true);
   }

   /// Applies [f] to each live class that implements [cls] _not_ including [cls]
   /// itself.
   void forEachStrictSubtypeOf(
       ClassEntity cls, IterationStep f(ClassEntity cls)) {
     ClassSet classSet = _classSets[cls];
     if (classSet == null) return;
     classSet.forEachSubtype(f, ClassHierarchyNode.EXPLICITLY_INSTANTIATED,
         strict: true);
   }

   SubclassResult commonSubclasses(ClassEntity cls1, ClassQuery query1,
       ClassEntity cls2, ClassQuery query2) {
     if (query1 == ClassQuery.EXACT && query2 == ClassQuery.EXACT) {
       // Exact classes [cls1] and [cls2] must be identical to have any classes
       // in common.
       if (cls1 != cls2) {
         return const SubclassResult.empty();
       }
       return new SubclassResult.exact(cls1);
     } else if (query1 == ClassQuery.EXACT) {
       if (query2 == ClassQuery.SUBCLASS) {
         // Exact [cls1] must be a subclass of [cls2] to have any classes in
         // common.
         if (isSubclassOf(cls1, cls2)) {
           return new SubclassResult.exact(cls1);
         }
       } else if (query2 == ClassQuery.SUBTYPE) {
         // Exact [cls1] must be a subtype of [cls2] to have any classes in
         // common.
         if (isSubtypeOf(cls1, cls2)) {
           return new SubclassResult.exact(cls1);
         }
       }
       return const SubclassResult.empty();
     } else if (query2 == ClassQuery.EXACT) {
       if (query1 == ClassQuery.SUBCLASS) {
         // Exact [cls2] must be a subclass of [cls1] to have any classes in
         // common.
         if (isSubclassOf(cls2, cls1)) {
           return new SubclassResult.exact(cls2);
         }
       } else if (query1 == ClassQuery.SUBTYPE) {
         // Exact [cls2] must be a subtype of [cls1] to have any classes in
         // common.
         if (isSubtypeOf(cls2, cls1)) {
           return new SubclassResult.exact(cls2);
         }
       }
       return const SubclassResult.empty();
     } else if (query1 == ClassQuery.SUBCLASS && query2 == ClassQuery.SUBCLASS) {
       // [cls1] must be a subclass of [cls2] or vice versa to have any classes
       // in common.
       if (cls1 == cls2 || isSubclassOf(cls1, cls2)) {
         // The subclasses of [cls1] are contained within the subclasses of
         // [cls2].
         return new SubclassResult.subclass(cls1);
       } else if (isSubclassOf(cls2, cls1)) {
         // The subclasses of [cls2] are contained within the subclasses of
         // [cls1].
         return new SubclassResult.subclass(cls2);
       }
       return const SubclassResult.empty();
     } else if (query1 == ClassQuery.SUBCLASS) {
       if (isSubtypeOf(cls1, cls2)) {
         // The subclasses of [cls1] are all subtypes of [cls2].
         return new SubclassResult.subclass(cls1);
       }
       if (cls1 == _commonElements.objectClass) {
         // Since [cls1] is `Object` all subtypes of [cls2] are contained within
         // the subclasses of [cls1].
         return new SubclassResult.subtype(cls2);
       }
       // Find all the root subclasses of [cls1] of that implement [cls2].
       //
       // For this hierarchy:
       //
       //     class I {}
       //     class A {}
       //     class B extends A implements I {}
       //     class C extends B {}
       //     class D extends A implements I {}
       //
       // the common subclasses of "subclass of A" and "subtype of I" returns
       // "subclasses of {B, D}". The inclusion of class `C` is implied because
       // it is a subclass of `B`.
       List<ClassEntity> classes = <ClassEntity>[];
       forEachStrictSubclassOf(cls1, (ClassEntity subclass) {
         if (isSubtypeOf(subclass, cls2)) {
           classes.add(subclass);
           // Skip subclasses of [subclass]; they all implement [cls2] by
           // inheritance and are included in the subclasses of [subclass].
           return IterationStep.SKIP_SUBCLASSES;
         }
         return IterationStep.CONTINUE;
       });
       return new SubclassResult.subclasses(classes);
     } else if (query2 == ClassQuery.SUBCLASS) {
       if (isSubtypeOf(cls2, cls1)) {
         // The subclasses of [cls2] are all subtypes of [cls1].
         return new SubclassResult.subclass(cls2);
       }
       if (cls2 == _commonElements.objectClass) {
         // Since [cls2] is `Object` all subtypes of [cls1] are contained within
         // the subclasses of [cls2].
         return new SubclassResult.subtype(cls1);
       }
       // Find all the root subclasses of [cls2] of that implement [cls1].
       List<ClassEntity> classes = <ClassEntity>[];
       forEachStrictSubclassOf(cls2, (ClassEntity subclass) {
         if (isSubtypeOf(subclass, cls1)) {
           classes.add(subclass);
           // Skip subclasses of [subclass]; they all implement [cls1] by
           // inheritance and are included in the subclasses of [subclass].
           return IterationStep.SKIP_SUBCLASSES;
         }
         return IterationStep.CONTINUE;
       });
       return new SubclassResult.subclasses(classes);
     } else {
       if (cls1 == cls2 || isSubtypeOf(cls1, cls2)) {
         // The subtypes of [cls1] are contained within the subtypes of [cls2].
         return new SubclassResult.subtype(cls1);
       } else if (isSubtypeOf(cls2, cls1)) {
         // The subtypes of [cls2] are contained within the subtypes of [cls1].
         return new SubclassResult.subtype(cls2);
       }
       // Find all the root subclasses of [cls1] of that implement [cls2].
       //
       // For this hierarchy:
       //
       //     class I {}
       //     class A {}
       //     class B extends A implements I {}
       //     class C extends B {}
       //     class D extends A implements I {}
       //     class E implements B {}
       //     class F extends E {}
       //
       // the common subclasses of "subtype of A" and "subtype of I" returns
       // "subclasses of {B, D, E}". The inclusion of classes `C` and `F` is
       // implied because they are subclasses of `B` and `E`, respectively.
       List<ClassEntity> classes = <ClassEntity>[];
       forEachStrictSubtypeOf(cls1, (ClassEntity subclass) {
         if (isSubtypeOf(subclass, cls2)) {
           classes.add(subclass);
           // Skip subclasses of [subclass]; they all implement [cls2] by
           // inheritance and are included in the subclasses of [subclass].
           return IterationStep.SKIP_SUBCLASSES;
         }
         return IterationStep.CONTINUE;
       });
       return new SubclassResult.subclasses(classes);
     }
   }
 }

 class ClassHierarchyBuilder {
   // We keep track of subtype and subclass relationships in four
   // distinct sets to make class hierarchy analysis faster.
   final Map<ClassEntity, ClassHierarchyNode> classHierarchyNodes =
       <ClassEntity, ClassHierarchyNode>{};
   final Map<ClassEntity, ClassSet> classSets = <ClassEntity, ClassSet>{};
   final Map<ClassEntity, Set<ClassEntity>> mixinUses =
       new Map<ClassEntity, Set<ClassEntity>>();

   final CommonElements _commonElements;
   final ClassQueries _classQueries;

   ClassHierarchyBuilder(this._commonElements, this._classQueries);

   void registerClass(ClassEntity cls) {
     _ensureClassSet(_classQueries.getDeclaration(cls));
   }

   ClassHierarchyNode _ensureClassHierarchyNode(ClassEntity cls) {
     assert(_classQueries.checkClass(cls));
     return classHierarchyNodes.putIfAbsent(cls, () {
       ClassHierarchyNode parentNode;
       ClassEntity superclass = _classQueries.getSuperClass(cls);
       if (superclass != null) {
         parentNode = _ensureClassHierarchyNode(superclass);
       }
       return new ClassHierarchyNode(
           parentNode, cls, _classQueries.getHierarchyDepth(cls));
     });
   }

   ClassSet _ensureClassSet(ClassEntity cls) {
     assert(_classQueries.checkClass(cls));
     return classSets.putIfAbsent(cls, () {
       ClassHierarchyNode node = _ensureClassHierarchyNode(cls);
       ClassSet classSet = new ClassSet(node);

       for (InterfaceType type in _classQueries.getSupertypes(cls)) {
         // TODO(johnniwinther): Optimization: Avoid adding [cls] to
         // superclasses.
         ClassSet subtypeSet = _ensureClassSet(type.element);
         subtypeSet.addSubtype(node);
       }

       ClassEntity appliedMixin = _classQueries.getAppliedMixin(cls);
       while (appliedMixin != null) {
         // TODO(johnniwinther): Use the data stored in [ClassSet].
         registerMixinUse(cls, appliedMixin);
         ClassSet mixinSet = _ensureClassSet(appliedMixin);
         mixinSet.addMixinApplication(node);

         // In case of
         //
         //    class A {}
         //    class B = Object with A;
         //    class C = Object with B;
         //
         // we need to register that C not only mixes in B but also A.
         appliedMixin = _classQueries.getAppliedMixin(appliedMixin);
       }
       return classSet;
     });
   }

   void _updateSuperClassHierarchyNodeForClass(ClassHierarchyNode node) {
     // Ensure that classes implicitly implementing `Function` are in its
     // subtype set.
     ClassEntity cls = node.cls;
     if (cls != _commonElements.functionClass &&
         _classQueries.implementsFunction(cls)) {
       ClassSet subtypeSet = _ensureClassSet(_commonElements.functionClass);
       subtypeSet.addSubtype(node);
     }
     if (!node.isInstantiated && node.parentNode != null) {
       _updateSuperClassHierarchyNodeForClass(node.parentNode);
     }
   }

   void updateClassHierarchyNodeForClass(ClassEntity cls,
       {bool directlyInstantiated: false, bool abstractlyInstantiated: false}) {
     ClassHierarchyNode node = _ensureClassSet(cls).node;
     _updateSuperClassHierarchyNodeForClass(node);
     if (directlyInstantiated) {
       node.isDirectlyInstantiated = true;
     }
     if (abstractlyInstantiated) {
       node.isAbstractlyInstantiated = true;
     }
   }

   void registerMixinUse(ClassEntity mixinApplication, ClassEntity mixin) {
     // TODO(johnniwinther): Add map restricted to live classes.
     // We don't support patch classes as mixin.
     Set<ClassEntity> users =
         mixinUses.putIfAbsent(mixin, () => new Set<ClassEntity>());
     users.add(mixinApplication);
   }

   bool _isSubtypeOf(ClassEntity x, ClassEntity y) {
     assert(
         classSets.containsKey(x), "ClassSet for $x has not been computed yet.");
     ClassSet classSet = classSets[y];
     assert(classSet != null,
         failedAt(y, "No ClassSet for $y (${y.runtimeType}): ${classSets}"));
     ClassHierarchyNode classHierarchyNode = classHierarchyNodes[x];
     assert(classHierarchyNode != null,
         failedAt(x, "No ClassHierarchyNode for $x"));
     return classSet.hasSubtype(classHierarchyNode);
   }

   bool isInheritedInSubtypeOf(ClassEntity x, ClassEntity y) {
     ClassSet classSet = classSets[x];
     assert(classSet != null,
         failedAt(x, "No ClassSet for $x (${x.runtimeType}): ${classSets}"));

     if (_isSubtypeOf(x, y)) {
       // [x] implements [y] itself, possible through supertypes.
       return true;
     }

     /// Returns `true` if any live subclass of [node] implements [y].
     bool subclassImplements(ClassHierarchyNode node, {bool strict}) {
       return node.anySubclass((ClassEntity z) => _isSubtypeOf(z, y),
           ClassHierarchyNode.INSTANTIATED,
           strict: strict);
     }

     if (subclassImplements(classSet.node, strict: true)) {
       // A subclass of [x] implements [y].
       return true;
     }

     for (ClassHierarchyNode mixinApplication
         in classSet.mixinApplicationNodes) {
       if (subclassImplements(mixinApplication, strict: false)) {
         // A subclass of [mixinApplication] implements [y].
         return true;
       }
     }
     return false;
   }
 }

 abstract class ClassQueries {
   bool checkClass(covariant ClassEntity cls);
   bool validateClass(covariant ClassEntity cls);

   /// Returns the declaration of [cls].
   ClassEntity getDeclaration(covariant ClassEntity cls);

   /// Returns the class mixed into [cls] if any.
   // TODO(johnniwinther): Replace this by a `getAppliedMixins` function that
   // return transitively mixed in classes like in:
   //     class A {}
   //     class B = Object with A;
   //     class C = Object with B;
   ClassEntity getAppliedMixin(covariant ClassEntity cls);

   /// Returns the hierarchy depth of [cls].
   int getHierarchyDepth(covariant ClassEntity cls);

   /// Returns `true` if [cls] implements `Function` either explicitly or through
   /// a `call` method.
   bool implementsFunction(covariant ClassEntity cls);

   /// Returns the superclass of [cls] if any.
   ClassEntity getSuperClass(covariant ClassEntity cls);

   /// Returns all supertypes of [cls].
   Iterable<InterfaceType> getSupertypes(covariant ClassEntity cls);
 }

 /// Enum values defining subset of classes included in queries.
 enum ClassQuery {
   /// Only the class itself is included.
   EXACT,

   /// The class and all subclasses (transitively) are included.
   SUBCLASS,

   /// The class and all classes that implement or subclass it (transitively)
   /// are included.
   SUBTYPE,
 }

 /// Result computed in [ClassHierarchy.commonSubclasses].
 class SubclassResult {
   /// The classes in the result set. The classes are always disjoint wrt. the
   /// interpretation of [query].
   final List<ClassEntity> classes;

   /// How [classes] should be interpreted: If `ClassQuery.EXACT`, only the
   /// classes in [classes] are on the result set. If `ClassQuery.SUBCLASS`,
   /// non-strict subclasses of the classes in [classes] are in the result set.
   /// If `ClassQuery.SUBTYPE`, non-strict subtypes of the classes in [classes]
   /// are in the result set.
   final ClassQuery query;

   /// Creates the empty result set.
   const SubclassResult.empty()
       : query = ClassQuery.EXACT,
         classes = const <ClassEntity>[];

   /// Creates the single set of [cls].
   SubclassResult.exact(ClassEntity cls)
       : query = ClassQuery.EXACT,
         classes = <ClassEntity>[cls];

   /// Creates the set of subclasses of [cls].
   SubclassResult.subclass(ClassEntity cls)
       : query = ClassQuery.SUBCLASS,
         classes = <ClassEntity>[cls];

   /// Creates the set of subtypes of [cls].
   SubclassResult.subtype(ClassEntity cls)
       : query = ClassQuery.SUBTYPE,
         classes = <ClassEntity>[cls];

   /// Creates the set of classes that are subclasses of a class in [classes].
   SubclassResult.subclasses(this.classes) : query = ClassQuery.SUBCLASS;

   SubclassResult.internal(this.query, this.classes);

   String toString() => 'SubclassResult($query,$classes)';
 }
	// Copyright (c) 2017, the Dart project authors. Please see the AUTHORS file
	// for details. All rights reserved. Use of this source code is governed by a
	// BSD-style license that can be found in the LICENSE file.

	import '../common.dart';
	import '../common_elements.dart';
	import '../elements/entities.dart';
	import '../elements/types.dart' show InterfaceType;
	import 'class_set.dart';

	// TODO(johnniwinther): Move more methods from `JClosedWorld` to
	// `ClassHierarchy`.
	abstract class ClassHierarchy {
	/// Returns [ClassHierarchyNode] for [cls] used to model the class hierarchies
	/// of known classes.
	///
	/// This method is only provided for testing. For queries on classes, use the
	/// methods defined in [JClosedWorld].
	ClassHierarchyNode getClassHierarchyNode(ClassEntity cls);

	/// Returns [ClassSet] for [cls] used to model the extends and implements
	/// relations of known classes.
	///
	/// This method is only provided for testing. For queries on classes, use the
	/// methods defined in [JClosedWorld].
	ClassSet getClassSet(ClassEntity cls);

	/// Returns `true` if [x] is a subtype of [y], that is, if [x] implements an
	/// instance of [y].
	bool isSubtypeOf(ClassEntity x, ClassEntity y);

	/// Returns a [SubclassResult] for the subclasses that are contained in
	/// the subclass/subtype sets of both [cls1] and [cls2].
	///
	/// Classes that are implied by included superclasses/supertypes are not
	/// returned.
	///
	/// For instance for this hierarchy
	///
	/// class A {}
	/// class B {}
	/// class C implements A, B {}
	/// class D extends C {}
	///
	/// the query
	///
	/// commonSubclasses(A, ClassQuery.SUBTYPE, B, ClassQuery.SUBTYPE)
	///
	/// return the set {C} because [D] is implied by [C].
	SubclassResult commonSubclasses(
	ClassEntity cls1, ClassQuery query1, ClassEntity cls2, ClassQuery query2);

	/// Returns an iterable over the directly instantiated that implement [cls]
	/// possibly including [cls] itself, if it is live.
	Iterable<ClassEntity> subtypesOf(ClassEntity cls);

	/// Returns an iterable over the live classes that extend [cls] including
	/// [cls] itself.
	Iterable<ClassEntity> subclassesOf(ClassEntity cls);

	/// Applies [f] to each live class that implements [cls] _not_ including [cls]
	/// itself.
	void forEachStrictSubtypeOf(
	ClassEntity cls, IterationStep f(ClassEntity cls));
	}

	class ClassHierarchyImpl implements ClassHierarchy {
	final CommonElements _commonElements;
	final Map<ClassEntity, ClassHierarchyNode> _classHierarchyNodes;
	final Map<ClassEntity, ClassSet> _classSets;

	ClassHierarchyImpl(
	this._commonElements, this._classHierarchyNodes, this._classSets);

	/// Returns [ClassHierarchyNode] for [cls] used to model the class hierarchies
	/// of known classes.
	///
	/// This method is only provided for testing. For queries on classes, use the
	/// methods defined in [JClosedWorld].
	ClassHierarchyNode getClassHierarchyNode(ClassEntity cls) {
	return _classHierarchyNodes[cls];
	}

	/// Returns [ClassSet] for [cls] used to model the extends and implements
	/// relations of known classes.
	///
	/// This method is only provided for testing. For queries on classes, use the
	/// methods defined in [JClosedWorld].
	ClassSet getClassSet(ClassEntity cls) {
	return _classSets[cls];
	}

	/// Returns `true` if [x] is a subtype of [y], that is, if [x] implements an
	/// instance of [y].
	bool isSubtypeOf(ClassEntity x, ClassEntity y) {
	ClassSet classSet = _classSets[y];
	assert(classSet != null,
	failedAt(y, "No ClassSet for $y (${y.runtimeType}): ${_classSets}"));
	ClassHierarchyNode classHierarchyNode = _classHierarchyNodes[x];
	assert(classHierarchyNode != null,
	failedAt(x, "No ClassHierarchyNode for $x"));
	return classSet.hasSubtype(classHierarchyNode);
	}

	/// Return `true` if [x] is a (non-strict) subclass of [y].
	bool isSubclassOf(ClassEntity x, ClassEntity y) {
	return _classHierarchyNodes[y].hasSubclass(_classHierarchyNodes[x]);
	}

	/// Returns an iterable over the directly instantiated that implement [cls]
	/// possibly including [cls] itself, if it is live.
	Iterable<ClassEntity> subtypesOf(ClassEntity cls) {
	ClassSet classSet = _classSets[cls];
	if (classSet == null) {
	return const <ClassEntity>[];
	} else {
	return classSet
	.subtypesByMask(ClassHierarchyNode.EXPLICITLY_INSTANTIATED);
	}
	}

	/// Returns an iterable over the directly instantiated classes that extend
	/// [cls] possibly including [cls] itself, if it is live.
	Iterable<ClassEntity> subclassesOf(ClassEntity cls) {
	ClassHierarchyNode hierarchy = _classHierarchyNodes[cls];
	if (hierarchy == null) return const <ClassEntity>[];
	return hierarchy
	.subclassesByMask(ClassHierarchyNode.EXPLICITLY_INSTANTIATED);
	}

	/// Returns an iterable over the directly instantiated that implement [cls]
	/// _not_ including [cls].
	Iterable<ClassEntity> strictSubtypesOf(ClassEntity cls) {
	ClassSet classSet = _classSets[cls];
	if (classSet == null) {
	return const <ClassEntity>[];
	} else {
	return classSet.subtypesByMask(ClassHierarchyNode.EXPLICITLY_INSTANTIATED,
	strict: true);
	}
	}

	/// Returns an iterable over the directly instantiated classes that extend
	/// [cls] _not_ including [cls] itself.
	Iterable<ClassEntity> strictSubclassesOf(ClassEntity cls) {
	ClassHierarchyNode subclasses = _classHierarchyNodes[cls];
	if (subclasses == null) return const <ClassEntity>[];
	return subclasses.subclassesByMask(
	ClassHierarchyNode.EXPLICITLY_INSTANTIATED,
	strict: true);
	}

	/// Applies [f] to each live class that extend [cls] _not_ including [cls]
	/// itself.
	void forEachStrictSubclassOf(
	ClassEntity cls, IterationStep f(ClassEntity cls)) {
	ClassHierarchyNode subclasses = _classHierarchyNodes[cls];
	if (subclasses == null) return;
	subclasses.forEachSubclass(f, ClassHierarchyNode.EXPLICITLY_INSTANTIATED,
	strict: true);
	}

	/// Applies [f] to each live class that implements [cls] _not_ including [cls]
	/// itself.
	void forEachStrictSubtypeOf(
	ClassEntity cls, IterationStep f(ClassEntity cls)) {
	ClassSet classSet = _classSets[cls];
	if (classSet == null) return;
	classSet.forEachSubtype(f, ClassHierarchyNode.EXPLICITLY_INSTANTIATED,
	strict: true);
	}

	SubclassResult commonSubclasses(ClassEntity cls1, ClassQuery query1,
	ClassEntity cls2, ClassQuery query2) {
	if (query1 == ClassQuery.EXACT && query2 == ClassQuery.EXACT) {
	// Exact classes [cls1] and [cls2] must be identical to have any classes
	// in common.
	if (cls1 != cls2) {
	return const SubclassResult.empty();
	}
	return new SubclassResult.exact(cls1);
	} else if (query1 == ClassQuery.EXACT) {
	if (query2 == ClassQuery.SUBCLASS) {
	// Exact [cls1] must be a subclass of [cls2] to have any classes in
	// common.
	if (isSubclassOf(cls1, cls2)) {
	return new SubclassResult.exact(cls1);
	}
	} else if (query2 == ClassQuery.SUBTYPE) {
	// Exact [cls1] must be a subtype of [cls2] to have any classes in
	// common.
	if (isSubtypeOf(cls1, cls2)) {
	return new SubclassResult.exact(cls1);
	}
	}
	return const SubclassResult.empty();
	} else if (query2 == ClassQuery.EXACT) {
	if (query1 == ClassQuery.SUBCLASS) {
	// Exact [cls2] must be a subclass of [cls1] to have any classes in
	// common.
	if (isSubclassOf(cls2, cls1)) {
	return new SubclassResult.exact(cls2);
	}
	} else if (query1 == ClassQuery.SUBTYPE) {
	// Exact [cls2] must be a subtype of [cls1] to have any classes in
	// common.
	if (isSubtypeOf(cls2, cls1)) {
	return new SubclassResult.exact(cls2);
	}
	}
	return const SubclassResult.empty();
	} else if (query1 == ClassQuery.SUBCLASS && query2 == ClassQuery.SUBCLASS) {
	// [cls1] must be a subclass of [cls2] or vice versa to have any classes
	// in common.
	if (cls1 == cls2 \|\| isSubclassOf(cls1, cls2)) {
	// The subclasses of [cls1] are contained within the subclasses of
	// [cls2].
	return new SubclassResult.subclass(cls1);
	} else if (isSubclassOf(cls2, cls1)) {
	// The subclasses of [cls2] are contained within the subclasses of
	// [cls1].
	return new SubclassResult.subclass(cls2);
	}
	return const SubclassResult.empty();
	} else if (query1 == ClassQuery.SUBCLASS) {
	if (isSubtypeOf(cls1, cls2)) {
	// The subclasses of [cls1] are all subtypes of [cls2].
	return new SubclassResult.subclass(cls1);
	}
	if (cls1 == _commonElements.objectClass) {
	// Since [cls1] is `Object` all subtypes of [cls2] are contained within
	// the subclasses of [cls1].
	return new SubclassResult.subtype(cls2);
	}
	// Find all the root subclasses of [cls1] of that implement [cls2].
	//
	// For this hierarchy:
	//
	// class I {}
	// class A {}
	// class B extends A implements I {}
	// class C extends B {}
	// class D extends A implements I {}
	//
	// the common subclasses of "subclass of A" and "subtype of I" returns
	// "subclasses of {B, D}". The inclusion of class `C` is implied because
	// it is a subclass of `B`.
	List<ClassEntity> classes = <ClassEntity>[];
	forEachStrictSubclassOf(cls1, (ClassEntity subclass) {
	if (isSubtypeOf(subclass, cls2)) {
	classes.add(subclass);
	// Skip subclasses of [subclass]; they all implement [cls2] by
	// inheritance and are included in the subclasses of [subclass].
	return IterationStep.SKIP_SUBCLASSES;
	}
	return IterationStep.CONTINUE;
	});
	return new SubclassResult.subclasses(classes);
	} else if (query2 == ClassQuery.SUBCLASS) {
	if (isSubtypeOf(cls2, cls1)) {
	// The subclasses of [cls2] are all subtypes of [cls1].
	return new SubclassResult.subclass(cls2);
	}
	if (cls2 == _commonElements.objectClass) {
	// Since [cls2] is `Object` all subtypes of [cls1] are contained within
	// the subclasses of [cls2].
	return new SubclassResult.subtype(cls1);
	}
	// Find all the root subclasses of [cls2] of that implement [cls1].
	List<ClassEntity> classes = <ClassEntity>[];
	forEachStrictSubclassOf(cls2, (ClassEntity subclass) {
	if (isSubtypeOf(subclass, cls1)) {
	classes.add(subclass);
	// Skip subclasses of [subclass]; they all implement [cls1] by
	// inheritance and are included in the subclasses of [subclass].
	return IterationStep.SKIP_SUBCLASSES;
	}
	return IterationStep.CONTINUE;
	});
	return new SubclassResult.subclasses(classes);
	} else {
	if (cls1 == cls2 \|\| isSubtypeOf(cls1, cls2)) {
	// The subtypes of [cls1] are contained within the subtypes of [cls2].
	return new SubclassResult.subtype(cls1);
	} else if (isSubtypeOf(cls2, cls1)) {
	// The subtypes of [cls2] are contained within the subtypes of [cls1].
	return new SubclassResult.subtype(cls2);
	}
	// Find all the root subclasses of [cls1] of that implement [cls2].
	//
	// For this hierarchy:
	//
	// class I {}
	// class A {}
	// class B extends A implements I {}
	// class C extends B {}
	// class D extends A implements I {}
	// class E implements B {}
	// class F extends E {}
	//
	// the common subclasses of "subtype of A" and "subtype of I" returns
	// "subclasses of {B, D, E}". The inclusion of classes `C` and `F` is
	// implied because they are subclasses of `B` and `E`, respectively.
	List<ClassEntity> classes = <ClassEntity>[];
	forEachStrictSubtypeOf(cls1, (ClassEntity subclass) {
	if (isSubtypeOf(subclass, cls2)) {
	classes.add(subclass);
	// Skip subclasses of [subclass]; they all implement [cls2] by
	// inheritance and are included in the subclasses of [subclass].
	return IterationStep.SKIP_SUBCLASSES;
	}
	return IterationStep.CONTINUE;
	});
	return new SubclassResult.subclasses(classes);
	}
	}
	}

	class ClassHierarchyBuilder {
	// We keep track of subtype and subclass relationships in four
	// distinct sets to make class hierarchy analysis faster.
	final Map<ClassEntity, ClassHierarchyNode> classHierarchyNodes =
	<ClassEntity, ClassHierarchyNode>{};
	final Map<ClassEntity, ClassSet> classSets = <ClassEntity, ClassSet>{};
	final Map<ClassEntity, Set<ClassEntity>> mixinUses =
	new Map<ClassEntity, Set<ClassEntity>>();

	final CommonElements _commonElements;
	final ClassQueries _classQueries;

	ClassHierarchyBuilder(this._commonElements, this._classQueries);

	void registerClass(ClassEntity cls) {
	_ensureClassSet(_classQueries.getDeclaration(cls));
	}

	ClassHierarchyNode _ensureClassHierarchyNode(ClassEntity cls) {
	assert(_classQueries.checkClass(cls));
	return classHierarchyNodes.putIfAbsent(cls, () {
	ClassHierarchyNode parentNode;
	ClassEntity superclass = _classQueries.getSuperClass(cls);
	if (superclass != null) {
	parentNode = _ensureClassHierarchyNode(superclass);
	}
	return new ClassHierarchyNode(
	parentNode, cls, _classQueries.getHierarchyDepth(cls));
	});
	}

	ClassSet _ensureClassSet(ClassEntity cls) {
	assert(_classQueries.checkClass(cls));
	return classSets.putIfAbsent(cls, () {
	ClassHierarchyNode node = _ensureClassHierarchyNode(cls);
	ClassSet classSet = new ClassSet(node);

	for (InterfaceType type in _classQueries.getSupertypes(cls)) {
	// TODO(johnniwinther): Optimization: Avoid adding [cls] to
	// superclasses.
	ClassSet subtypeSet = _ensureClassSet(type.element);
	subtypeSet.addSubtype(node);
	}

	ClassEntity appliedMixin = _classQueries.getAppliedMixin(cls);
	while (appliedMixin != null) {
	// TODO(johnniwinther): Use the data stored in [ClassSet].
	registerMixinUse(cls, appliedMixin);
	ClassSet mixinSet = _ensureClassSet(appliedMixin);
	mixinSet.addMixinApplication(node);

	// In case of
	//
	// class A {}
	// class B = Object with A;
	// class C = Object with B;
	//
	// we need to register that C not only mixes in B but also A.
	appliedMixin = _classQueries.getAppliedMixin(appliedMixin);
	}
	return classSet;
	});
	}

	void _updateSuperClassHierarchyNodeForClass(ClassHierarchyNode node) {
	// Ensure that classes implicitly implementing `Function` are in its
	// subtype set.
	ClassEntity cls = node.cls;
	if (cls != _commonElements.functionClass &&
	_classQueries.implementsFunction(cls)) {
	ClassSet subtypeSet = _ensureClassSet(_commonElements.functionClass);
	subtypeSet.addSubtype(node);
	}
	if (!node.isInstantiated && node.parentNode != null) {
	_updateSuperClassHierarchyNodeForClass(node.parentNode);
	}
	}

	void updateClassHierarchyNodeForClass(ClassEntity cls,
	{bool directlyInstantiated: false, bool abstractlyInstantiated: false}) {
	ClassHierarchyNode node = _ensureClassSet(cls).node;
	_updateSuperClassHierarchyNodeForClass(node);
	if (directlyInstantiated) {
	node.isDirectlyInstantiated = true;
	}
	if (abstractlyInstantiated) {
	node.isAbstractlyInstantiated = true;
	}
	}

	void registerMixinUse(ClassEntity mixinApplication, ClassEntity mixin) {
	// TODO(johnniwinther): Add map restricted to live classes.
	// We don't support patch classes as mixin.
	Set<ClassEntity> users =
	mixinUses.putIfAbsent(mixin, () => new Set<ClassEntity>());
	users.add(mixinApplication);
	}

	bool _isSubtypeOf(ClassEntity x, ClassEntity y) {
	assert(
	classSets.containsKey(x), "ClassSet for $x has not been computed yet.");
	ClassSet classSet = classSets[y];
	assert(classSet != null,
	failedAt(y, "No ClassSet for $y (${y.runtimeType}): ${classSets}"));
	ClassHierarchyNode classHierarchyNode = classHierarchyNodes[x];
	assert(classHierarchyNode != null,
	failedAt(x, "No ClassHierarchyNode for $x"));
	return classSet.hasSubtype(classHierarchyNode);
	}

	bool isInheritedInSubtypeOf(ClassEntity x, ClassEntity y) {
	ClassSet classSet = classSets[x];
	assert(classSet != null,
	failedAt(x, "No ClassSet for $x (${x.runtimeType}): ${classSets}"));

	if (_isSubtypeOf(x, y)) {
	// [x] implements [y] itself, possible through supertypes.
	return true;
	}

	/// Returns `true` if any live subclass of [node] implements [y].
	bool subclassImplements(ClassHierarchyNode node, {bool strict}) {
	return node.anySubclass((ClassEntity z) => _isSubtypeOf(z, y),
	ClassHierarchyNode.INSTANTIATED,
	strict: strict);
	}

	if (subclassImplements(classSet.node, strict: true)) {
	// A subclass of [x] implements [y].
	return true;
	}

	for (ClassHierarchyNode mixinApplication
	in classSet.mixinApplicationNodes) {
	if (subclassImplements(mixinApplication, strict: false)) {
	// A subclass of [mixinApplication] implements [y].
	return true;
	}
	}
	return false;
	}
	}

	abstract class ClassQueries {
	bool checkClass(covariant ClassEntity cls);
	bool validateClass(covariant ClassEntity cls);

	/// Returns the declaration of [cls].
	ClassEntity getDeclaration(covariant ClassEntity cls);

	/// Returns the class mixed into [cls] if any.
	// TODO(johnniwinther): Replace this by a `getAppliedMixins` function that
	// return transitively mixed in classes like in:
	// class A {}
	// class B = Object with A;
	// class C = Object with B;
	ClassEntity getAppliedMixin(covariant ClassEntity cls);

	/// Returns the hierarchy depth of [cls].
	int getHierarchyDepth(covariant ClassEntity cls);

	/// Returns `true` if [cls] implements `Function` either explicitly or through
	/// a `call` method.
	bool implementsFunction(covariant ClassEntity cls);

	/// Returns the superclass of [cls] if any.
	ClassEntity getSuperClass(covariant ClassEntity cls);

	/// Returns all supertypes of [cls].
	Iterable<InterfaceType> getSupertypes(covariant ClassEntity cls);
	}

	/// Enum values defining subset of classes included in queries.
	enum ClassQuery {
	/// Only the class itself is included.
	EXACT,

	/// The class and all subclasses (transitively) are included.
	SUBCLASS,

	/// The class and all classes that implement or subclass it (transitively)
	/// are included.
	SUBTYPE,
	}

	/// Result computed in [ClassHierarchy.commonSubclasses].
	class SubclassResult {
	/// The classes in the result set. The classes are always disjoint wrt. the
	/// interpretation of [query].
	final List<ClassEntity> classes;

	/// How [classes] should be interpreted: If `ClassQuery.EXACT`, only the
	/// classes in [classes] are on the result set. If `ClassQuery.SUBCLASS`,
	/// non-strict subclasses of the classes in [classes] are in the result set.
	/// If `ClassQuery.SUBTYPE`, non-strict subtypes of the classes in [classes]
	/// are in the result set.
	final ClassQuery query;

	/// Creates the empty result set.
	const SubclassResult.empty()
	: query = ClassQuery.EXACT,
	classes = const <ClassEntity>[];

	/// Creates the single set of [cls].
	SubclassResult.exact(ClassEntity cls)
	: query = ClassQuery.EXACT,
	classes = <ClassEntity>[cls];

	/// Creates the set of subclasses of [cls].
	SubclassResult.subclass(ClassEntity cls)
	: query = ClassQuery.SUBCLASS,
	classes = <ClassEntity>[cls];

	/// Creates the set of subtypes of [cls].
	SubclassResult.subtype(ClassEntity cls)
	: query = ClassQuery.SUBTYPE,
	classes = <ClassEntity>[cls];

	/// Creates the set of classes that are subclasses of a class in [classes].
	SubclassResult.subclasses(this.classes) : query = ClassQuery.SUBCLASS;

	SubclassResult.internal(this.query, this.classes);

	String toString() => 'SubclassResult($query,$classes)';
	}