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

 // Copyright (c) 2022, 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 'package:compiler/src/common/names.dart';
 import 'package:compiler/src/elements/entities.dart';
 import 'package:compiler/src/elements/names.dart';
 import 'package:compiler/src/inferrer/abstract_value_domain.dart';
 import 'package:compiler/src/js_model/js_world.dart';
 import 'package:compiler/src/universe/call_structure.dart';
 import 'package:compiler/src/universe/class_set.dart';
 import 'package:compiler/src/universe/function_set.dart';
 import 'package:compiler/src/universe/selector.dart';
 import 'package:compiler/src/util/util.dart';

 class DynamicCallTarget {
   final MemberEntity member;
   final bool isVirtual;

   factory DynamicCallTarget.virtual(MemberEntity member) =>
       DynamicCallTarget(member, isVirtual: true);
   factory DynamicCallTarget.concrete(MemberEntity member) =>
       DynamicCallTarget(member, isVirtual: false);
   DynamicCallTarget(this.member, {required this.isVirtual});

   @override
   int get hashCode => Object.hash(member, isVirtual);

   @override
   bool operator ==(Object other) {
     return identical(this, other) ||
         (other is DynamicCallTarget &&
             member == other.member &&
             isVirtual == other.isVirtual);
   }

   @override
   String toString() => 'TargetResult($member, virtual: $isVirtual)';
 }

 /// Builds and maintains member override hierarchy for easy querying of targets
 /// when refining call sites during type inference.
 ///
 /// We introduce the idea of a [DynamicCallTarget] which can either target a
 /// 'concrete' or 'virtual' member. A concrete member is one in which we know
 /// the target member is being called directly. A virtual member is one in which
 /// the call is to the target member or one of its overrides. Each member can
 /// have 2 types in the type inference graph, to represent its concrete and
 /// virtual versions. The type of a concrete member is based solely on the body
 /// of the member. The type of a virtual member is a union of the types of
 /// all its overrides. Abstract members only have virtual types since they do
 /// not have bodies and cannot be invoked directly.
 ///
 /// Init phase:
 /// This class begins by processing all 'live' members, both abstract and not,
 /// and constructing an override graph for these members. We track the direct
 /// overrides of a member based on the class hierarchy. For every direct
 /// override in this graph we also add edges into the type graph. One to join
 /// the concrete and virtual version of a member and then one between its
 /// virtual type and the virtual type of each direct override.
 ///
 /// Example type flow:
 /// ```
 /// class A {
 ///   T foo(U arg) => ...;
 /// }
 ///
 /// class B extends A {
 ///   T foo(U arg) => ...;
 /// }
 /// ```
 /// Parameter types flow to overrides:
 /// A.fooConcrete#arg <- A.fooVirtual#arg -> B.fooVirtual#arg
 ///
 /// Return types flow from overrides:
 /// A.fooConcrete#Return -> A.fooVirtual#Return <- B.fooVirtual#Return
 ///
 /// We also maintain a list of 'dynamic roots' for each possible selector we can
 /// encounter. These dynamic roots are methods that are not overrides and
 /// therefore are the minimal set of targets for a dynamic call to that
 /// selector. This preprocessing makes handling dynamic calls very fast.
 /// See [rootsForSelector].
 ///
 /// Query phase:
 /// For each query during type refinement we attempt to return as few targets as
 /// possible to represent calls on a receiver type cone. We start by trying to
 /// find the call that would be invoked if the call were on the root of the type
 /// cone by finding a matching member on a superclass (or the class itself).
 /// If we can find one then we determine if the call to this target would be
 /// virtual or concrete. The call can be concrete if:
 /// 1) The type cone is 'exact' so there is only one receiver class.
 /// 2) The type cone is 'subclass' but none of subclasses in the cone override
 ///    the target.
 /// 3) The target we found has no overrides so it must be the actual target.
 /// See [findSuperclassTarget].
 ///
 /// The above step produces a single target (virtual or concrete) reducing the
 /// number of edges in the type graph. However, since our type masks lose some
 /// precision as they get unioned, its possible that neither of those steps
 /// finds a target. In these cases we finally iterate over the subclasses (or
 /// subtypes for a subtype-cone) and find a set of targets that cover all
 /// classes in the cone. See [findMatchingAncestors].
 ///
 /// We handle receiver masks that include `null` as well as no such method
 /// handling separately. See [rootsForCall].
 ///
 /// All results returned from the query phase are cached on the pair of receiver
 /// type and selector for use in subsequent queries.
 class MemberHierarchyBuilder {
   final JClosedWorld closedWorld;
   final Map<SelectorMask, Iterable<DynamicCallTarget>> _callCache = {};
   final Map<Selector, Setlet<MemberEntity>> _dynamicRoots = {};
   final Map<MemberEntity, Setlet<MemberEntity>> _overrides = {};

   MemberHierarchyBuilder(this.closedWorld);

   /// Applies [f] to each override of [entity].
   ///
   /// If [f] returns `true` for a given input then its children are also
   /// visited.
   void forEachOverride(
       MemberEntity entity, IterationStep Function(MemberEntity override) f) {
     final overrides = _overrides[entity];
     if (overrides == null) return;
     for (final override in overrides) {
       final result = f(override);
       if (result == IterationStep.SKIP_SUBCLASSES) continue;
       if (result == IterationStep.STOP) return;
       forEachOverride(override, f);
     }
   }

   /// Check to see if any override of [match] is a target for a subclass call on
   /// [cls]. If not then the call can be concrete rather than virtual.
   bool _subclassNeedsVirtual(MemberEntity match, ClassEntity cls) {
     final visited = <MemberEntity>{};
     bool needsVirtual = false;
     final classHierarchy = closedWorld.classHierarchy;
     forEachOverride(match, (override) {
       if (!visited.add(override)) return IterationStep.SKIP_SUBCLASSES;
       if (classHierarchy.isSubclassOf(override.enclosingClass!, cls) ||
           closedWorld.hasAnySubclassThatMixes(cls, override.enclosingClass!)) {
         needsVirtual = true;
         return IterationStep.STOP;
       }
       return IterationStep.CONTINUE;
     });
     return needsVirtual;
   }

   /// Finds the first non-strict superclass of [cls] that contains a member
   /// matching [selector] and returns that member.
   ///
   /// Returns the first non-abstract match found while ascending the class
   /// hierarchy. If no non-abstract matches are found then the first abstract
   /// match is used.
   ///
   /// If [isExact] is true, the resulting [DynamicCallTarget] will be
   /// virtual when the match is non-abstract and has overrides.
   /// Otherwise the resulting [DynamicCallTarget] is concrete.
   ///
   /// For some selectors susceptible to degraded interceptor results,
   /// when [isSubclass] is true, this will return a set of concrete subclass
   /// targets rather than attempting to find a single virtual target.
   Iterable<DynamicCallTarget> findSuperclassTarget(
       ClassEntity cls, Selector selector,
       {bool isExact = false, bool isSubclass = false}) {
     MemberEntity? firstAbstractMatch;
     ClassEntity? current = cls;
     final elementEnv = closedWorld.elementEnvironment;
     while (current != null) {
       final match =
           elementEnv.lookupLocalClassMember(current, selector.memberName);
       if (match != null && !skipMember(match, selector)) {
         if (match.isAbstract) {
           firstAbstractMatch ??= match;
         } else {
           return [
             DynamicCallTarget(match,
                 isVirtual: !isExact &&
                     _hasOverride(match) &&
                     (!isSubclass || _subclassNeedsVirtual(match, cls)))
           ];
         }
       }
       current = elementEnv.getSuperClass(current);
     }
     return firstAbstractMatch != null
         ? [DynamicCallTarget.virtual(firstAbstractMatch)]
         : const [];
   }

   /// For each subclass/subtype try to find a member matching selector.
   ///
   /// If we find a match then it covers the entire subtree below that match so
   /// we do not need to check subclasses/subtypes below it.
   Iterable<DynamicCallTarget> findMatchingAncestors(
       ClassEntity baseCls, Selector selector,
       {required bool isSubtype}) {
     final results = Setlet<DynamicCallTarget>();
     IterationStep handleEntity(entity) {
       final match = findSuperclassTarget(entity, selector);
       if (match.isNotEmpty) {
         results.addAll(match);
         return IterationStep.SKIP_SUBCLASSES;
       }
       return IterationStep.CONTINUE;
     }

     if (isSubtype) {
       closedWorld.classHierarchy.forEachStrictSubtypeOf(baseCls, handleEntity);
     } else {
       closedWorld.classHierarchy.forEachStrictSubclassOf(baseCls, handleEntity);
     }
     return results;
   }

   /// Returns the set of root member declarations for [selector]. [cls] acts as
   /// a subclass filter for these roots.
   ///
   /// The set of roots is the smallest set of members that are an ancestor of
   /// every implementation of [selector]. This is with the caveat that we
   /// consider each mixin application to declare a "copy" of each member of that
   /// mixin. They share the same [MemberEntity] but each copy is considered a
   /// separate potential root.
   Iterable<DynamicCallTarget> rootsForSelector(
       ClassEntity cls, Selector selector) {
     final roots = _dynamicRoots[_normalizeSelector(selector)];
     if (roots == null) return const [];
     final classHierarchy = closedWorld.classHierarchy;
     return Setlet.of(roots
         .where((r) =>
             selector.appliesStructural(r) &&
             classHierarchy.isSubclassOf(r.enclosingClass!, cls))
         .map((r) => DynamicCallTarget(r, isVirtual: _hasOverride(r))));
   }

   /// Returns a set of common ancestors (not necessarily the smallest) for all
   /// possible targets when calling [selector] on an object with type
   /// [receiverType].
   ///
   /// Caches results for each receiver/selector pair. If [receiverType] is
   /// `null` the receiver is considered dynamic and any member that matches
   /// [selector] is a possible target. Also adds relevant [noSuchMethod] and
   /// `null` targets if needed for the call.
   Iterable<DynamicCallTarget> rootsForCall(
       AbstractValue? receiverType, Selector selector) {
     final domain = closedWorld.abstractValueDomain;
     receiverType ??= domain.dynamicType;
     final selectorMask = SelectorMask(selector, receiverType);
     final cachedResult = _callCache[selectorMask];
     if (cachedResult != null) return cachedResult;

     Iterable<DynamicCallTarget> targetsForReceiver =
         domain.findRootsOfTargets(receiverType, selector, this);

     // TODO(natebiggs): Can we calculate this as part of the above call to
     // findRootsOfTargets?
     final needsNoSuchMethod = selector != Selectors.noSuchMethod_ &&
         domain
             .needsNoSuchMethodHandling(receiverType, selector)
             .isPotentiallyTrue;

     final isNull = domain.isNull(receiverType);

     if (isNull.isPotentiallyTrue) {
       // Add relevant member if null is a potential target.
       final nullMatch = closedWorld.elementEnvironment.lookupLocalClassMember(
           closedWorld.commonElements.jsNullClass, selector.memberName);
       if (nullMatch != null) {
         targetsForReceiver = {
           ...targetsForReceiver,
           DynamicCallTarget.concrete(nullMatch)
         };
       }
     }

     final result = needsNoSuchMethod
         ? Setlet.of(targetsForReceiver
             .followedBy(rootsForCall(receiverType, Selectors.noSuchMethod_)))
         : targetsForReceiver;

     return _callCache[selectorMask] = result;
   }

   /// Map call selectors to a getter with the same name. This allows us to
   /// ignore their call structure since overridden methods can have different
   /// call structures. This also handles method tear-offs.
   static Selector _normalizeSelector(Selector selector) =>
       selector.isCall ? Selector.getter(selector.memberName) : selector;

   static bool _skipMemberInternal(MemberEntity member) {
     return member.isStatic;
   }

   static bool skipMember(MemberEntity member, Selector selector) {
     return _skipMemberInternal(member) || !selector.appliesStructural(member);
   }

   bool _hasOverride(MemberEntity member) {
     return _overrides.containsKey(member);
   }

   static List<Selector> _selectorsForMember(MemberEntity member) {
     final List<Selector> result = [];
     if (member is FieldEntity) {
       // A field implicitly defines both a getter and setter. Each of these can
       // have different overrides so we consider them separately.
       result.add(Selector.getter(member.memberName));
       result.add(Selector.setter(member.memberName));
     } else {
       final selector = Selector.fromElement(member);
       result.add(_normalizeSelector(selector));
     }
     return result;
   }

   void _handleMember(MemberEntity member, ClassEntity cls, Selector selector,
       void Function(MemberEntity parent, MemberEntity override) join) {
     final elementEnv = closedWorld.elementEnvironment;
     final name = selector.memberName;
     bool foundSuperclass = false;

     void addParent(MemberEntity child, ClassEntity childCls,
         MemberEntity parent, ClassEntity parentCls) {
       if (child == parent) return;
       if ((_overrides[parent] ??= Setlet()).add(child)) {
         join(parent, child);
       }
     }

     // Check each superclass in ascending order until we find an ancestor.
     ClassEntity? current = elementEnv.getSuperClass(cls);
     while (current != null) {
       final match = elementEnv.lookupLocalClassMember(current, name);
       if (match != null && !MemberHierarchyBuilder._skipMemberInternal(match)) {
         addParent(member, cls, match, current);
         foundSuperclass = true;
         break;
       }
       current = elementEnv.getSuperClass(current);
     }

     closedWorld.classHierarchy.getClassSet(cls).forEachSubtype((subtype) {
       final override = elementEnv.lookupClassMember(subtype, name);
       if (override == null) return IterationStep.CONTINUE;
       addParent(override, subtype, member, cls);
       return IterationStep.CONTINUE;
     }, ClassHierarchyNode.INSTANTIATED, strict: true);

     if (!foundSuperclass) {
       (_dynamicRoots[selector] ??= Setlet()).add(member);
     }
   }

   void _processMember(MemberEntity member,
       void Function(MemberEntity parent, MemberEntity override) join) {
     if (_skipMemberInternal(member)) return;
     final cls = member.enclosingClass!;
     final mixinUses = closedWorld.mixinUsesOf(cls);
     // Process each selector matching member separately.
     for (final selector in _selectorsForMember(member)) {
       for (final mixinUse in mixinUses) {
         _handleMember(member, mixinUse, selector, join);
       }
       _handleMember(member, cls, selector, join);
     }
   }

   void init(void Function(MemberEntity parent, MemberEntity override) join) {
     final liveMembers = closedWorld.liveInstanceMembers
         .followedBy(closedWorld.liveAbstractInstanceMembers);

     for (final member in liveMembers) {
       _processMember(member, join);
     }
   }

   // TODO(natebiggs): Clean up debug code below.
   void debugCall(String selectorName, String className,
       {bool nullReceiver = false,
       bool nullValue = false,
       bool subClass = false,
       bool subType = false,
       bool setter = false,
       CallStructure? call}) {
     final allMembers = closedWorld.liveInstanceMembers
         .followedBy(closedWorld.liveAbstractInstanceMembers);
     final cls = allMembers
         .firstWhere((e) => e.enclosingClass!.name == className)
         .enclosingClass!;
     final domain = closedWorld.abstractValueDomain;
     final receiver = nullValue
         ? domain.nullType
         : (nullReceiver
             ? null
             : (subClass
                 ? domain.createNonNullSubclass(cls)
                 : (subType
                     ? domain.createNonNullSubtype(cls)
                     : domain.createNullableExact(cls))));
     final name = Name(selectorName, null);
     final selector = call != null
         ? Selector.call(name, call)
         : (setter ? Selector.setter(name) : Selector.getter(name));

     print('Receiver: $receiver, Selector: $selector');
     print('Locate members: ${closedWorld.locateMembers(selector, receiver)}');
     print('Targets for call: ${rootsForCall(receiver, selector).toList()}');
   }

   void dumpOverrides([String? memberName]) {
     print(_overrides.entries
         .where((e) => memberName == null || e.key.name == memberName)
         .map((e) => '${e.key}\n  ${e.value.join('\n  ')}')
         .join('\n'));
   }

   void dumpRoots([String? selectorName]) {
     (_dynamicRoots.entries
             .where((e) => selectorName == null || e.key.name == selectorName)
             .map((e) {
       final members = e.value.map((m) => m).toList();
       members.sort((a, b) => a.toString().compareTo(b.toString()));
       return MapEntry(e.key, members.join(', '));
     }).toList()
           ..sort((a, b) {
             final keyComp = a.key.toString().compareTo(b.key.toString());
             return keyComp != 0 ? keyComp : a.value.compareTo(b.value);
           }))
         .forEach((e) => print('${e.key}: ${e.value}'));
   }

   void dumpCache({String? selectorName, String? receiverString}) {
     _callCache.entries
         .where((e) =>
             (selectorName == null || e.key.name == selectorName) &&
             (receiverString == null ||
                 e.key.receiver.toString().contains(receiverString)))
         .forEach((e) => print('${e.key}: ${e.value.join(', ')}'));
   }
 }
	// Copyright (c) 2022, 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 'package:compiler/src/common/names.dart';
	import 'package:compiler/src/elements/entities.dart';
	import 'package:compiler/src/elements/names.dart';
	import 'package:compiler/src/inferrer/abstract_value_domain.dart';
	import 'package:compiler/src/js_model/js_world.dart';
	import 'package:compiler/src/universe/call_structure.dart';
	import 'package:compiler/src/universe/class_set.dart';
	import 'package:compiler/src/universe/function_set.dart';
	import 'package:compiler/src/universe/selector.dart';
	import 'package:compiler/src/util/util.dart';

	class DynamicCallTarget {
	final MemberEntity member;
	final bool isVirtual;

	factory DynamicCallTarget.virtual(MemberEntity member) =>
	DynamicCallTarget(member, isVirtual: true);
	factory DynamicCallTarget.concrete(MemberEntity member) =>
	DynamicCallTarget(member, isVirtual: false);
	DynamicCallTarget(this.member, {required this.isVirtual});

	@override
	int get hashCode => Object.hash(member, isVirtual);

	@override
	bool operator ==(Object other) {
	return identical(this, other) \|\|
	(other is DynamicCallTarget &&
	member == other.member &&
	isVirtual == other.isVirtual);
	}

	@override
	String toString() => 'TargetResult($member, virtual: $isVirtual)';
	}

	/// Builds and maintains member override hierarchy for easy querying of targets
	/// when refining call sites during type inference.
	///
	/// We introduce the idea of a [DynamicCallTarget] which can either target a
	/// 'concrete' or 'virtual' member. A concrete member is one in which we know
	/// the target member is being called directly. A virtual member is one in which
	/// the call is to the target member or one of its overrides. Each member can
	/// have 2 types in the type inference graph, to represent its concrete and
	/// virtual versions. The type of a concrete member is based solely on the body
	/// of the member. The type of a virtual member is a union of the types of
	/// all its overrides. Abstract members only have virtual types since they do
	/// not have bodies and cannot be invoked directly.
	///
	/// Init phase:
	/// This class begins by processing all 'live' members, both abstract and not,
	/// and constructing an override graph for these members. We track the direct
	/// overrides of a member based on the class hierarchy. For every direct
	/// override in this graph we also add edges into the type graph. One to join
	/// the concrete and virtual version of a member and then one between its
	/// virtual type and the virtual type of each direct override.
	///
	/// Example type flow:
	/// ```
	/// class A {
	/// T foo(U arg) => ...;
	/// }
	///
	/// class B extends A {
	/// T foo(U arg) => ...;
	/// }
	/// ```
	/// Parameter types flow to overrides:
	/// A.fooConcrete#arg <- A.fooVirtual#arg -> B.fooVirtual#arg
	///
	/// Return types flow from overrides:
	/// A.fooConcrete#Return -> A.fooVirtual#Return <- B.fooVirtual#Return
	///
	/// We also maintain a list of 'dynamic roots' for each possible selector we can
	/// encounter. These dynamic roots are methods that are not overrides and
	/// therefore are the minimal set of targets for a dynamic call to that
	/// selector. This preprocessing makes handling dynamic calls very fast.
	/// See [rootsForSelector].
	///
	/// Query phase:
	/// For each query during type refinement we attempt to return as few targets as
	/// possible to represent calls on a receiver type cone. We start by trying to
	/// find the call that would be invoked if the call were on the root of the type
	/// cone by finding a matching member on a superclass (or the class itself).
	/// If we can find one then we determine if the call to this target would be
	/// virtual or concrete. The call can be concrete if:
	/// 1) The type cone is 'exact' so there is only one receiver class.
	/// 2) The type cone is 'subclass' but none of subclasses in the cone override
	/// the target.
	/// 3) The target we found has no overrides so it must be the actual target.
	/// See [findSuperclassTarget].
	///
	/// The above step produces a single target (virtual or concrete) reducing the
	/// number of edges in the type graph. However, since our type masks lose some
	/// precision as they get unioned, its possible that neither of those steps
	/// finds a target. In these cases we finally iterate over the subclasses (or
	/// subtypes for a subtype-cone) and find a set of targets that cover all
	/// classes in the cone. See [findMatchingAncestors].
	///
	/// We handle receiver masks that include `null` as well as no such method
	/// handling separately. See [rootsForCall].
	///
	/// All results returned from the query phase are cached on the pair of receiver
	/// type and selector for use in subsequent queries.
	class MemberHierarchyBuilder {
	final JClosedWorld closedWorld;
	final Map<SelectorMask, Iterable<DynamicCallTarget>> _callCache = {};
	final Map<Selector, Setlet<MemberEntity>> _dynamicRoots = {};
	final Map<MemberEntity, Setlet<MemberEntity>> _overrides = {};

	MemberHierarchyBuilder(this.closedWorld);

	/// Applies [f] to each override of [entity].
	///
	/// If [f] returns `true` for a given input then its children are also
	/// visited.
	void forEachOverride(
	MemberEntity entity, IterationStep Function(MemberEntity override) f) {
	final overrides = _overrides[entity];
	if (overrides == null) return;
	for (final override in overrides) {
	final result = f(override);
	if (result == IterationStep.SKIP_SUBCLASSES) continue;
	if (result == IterationStep.STOP) return;
	forEachOverride(override, f);
	}
	}

	/// Check to see if any override of [match] is a target for a subclass call on
	/// [cls]. If not then the call can be concrete rather than virtual.
	bool _subclassNeedsVirtual(MemberEntity match, ClassEntity cls) {
	final visited = <MemberEntity>{};
	bool needsVirtual = false;
	final classHierarchy = closedWorld.classHierarchy;
	forEachOverride(match, (override) {
	if (!visited.add(override)) return IterationStep.SKIP_SUBCLASSES;
	if (classHierarchy.isSubclassOf(override.enclosingClass!, cls) \|\|
	closedWorld.hasAnySubclassThatMixes(cls, override.enclosingClass!)) {
	needsVirtual = true;
	return IterationStep.STOP;
	}
	return IterationStep.CONTINUE;
	});
	return needsVirtual;
	}

	/// Finds the first non-strict superclass of [cls] that contains a member
	/// matching [selector] and returns that member.
	///
	/// Returns the first non-abstract match found while ascending the class
	/// hierarchy. If no non-abstract matches are found then the first abstract
	/// match is used.
	///
	/// If [isExact] is true, the resulting [DynamicCallTarget] will be
	/// virtual when the match is non-abstract and has overrides.
	/// Otherwise the resulting [DynamicCallTarget] is concrete.
	///
	/// For some selectors susceptible to degraded interceptor results,
	/// when [isSubclass] is true, this will return a set of concrete subclass
	/// targets rather than attempting to find a single virtual target.
	Iterable<DynamicCallTarget> findSuperclassTarget(
	ClassEntity cls, Selector selector,
	{bool isExact = false, bool isSubclass = false}) {
	MemberEntity? firstAbstractMatch;
	ClassEntity? current = cls;
	final elementEnv = closedWorld.elementEnvironment;
	while (current != null) {
	final match =
	elementEnv.lookupLocalClassMember(current, selector.memberName);
	if (match != null && !skipMember(match, selector)) {
	if (match.isAbstract) {
	firstAbstractMatch ??= match;
	} else {
	return [
	DynamicCallTarget(match,
	isVirtual: !isExact &&
	_hasOverride(match) &&
	(!isSubclass \|\| _subclassNeedsVirtual(match, cls)))
	];
	}
	}
	current = elementEnv.getSuperClass(current);
	}
	return firstAbstractMatch != null
	? [DynamicCallTarget.virtual(firstAbstractMatch)]
	: const [];
	}

	/// For each subclass/subtype try to find a member matching selector.
	///
	/// If we find a match then it covers the entire subtree below that match so
	/// we do not need to check subclasses/subtypes below it.
	Iterable<DynamicCallTarget> findMatchingAncestors(
	ClassEntity baseCls, Selector selector,
	{required bool isSubtype}) {
	final results = Setlet<DynamicCallTarget>();
	IterationStep handleEntity(entity) {
	final match = findSuperclassTarget(entity, selector);
	if (match.isNotEmpty) {
	results.addAll(match);
	return IterationStep.SKIP_SUBCLASSES;
	}
	return IterationStep.CONTINUE;
	}

	if (isSubtype) {
	closedWorld.classHierarchy.forEachStrictSubtypeOf(baseCls, handleEntity);
	} else {
	closedWorld.classHierarchy.forEachStrictSubclassOf(baseCls, handleEntity);
	}
	return results;
	}

	/// Returns the set of root member declarations for [selector]. [cls] acts as
	/// a subclass filter for these roots.
	///
	/// The set of roots is the smallest set of members that are an ancestor of
	/// every implementation of [selector]. This is with the caveat that we
	/// consider each mixin application to declare a "copy" of each member of that
	/// mixin. They share the same [MemberEntity] but each copy is considered a
	/// separate potential root.
	Iterable<DynamicCallTarget> rootsForSelector(
	ClassEntity cls, Selector selector) {
	final roots = _dynamicRoots[_normalizeSelector(selector)];
	if (roots == null) return const [];
	final classHierarchy = closedWorld.classHierarchy;
	return Setlet.of(roots
	.where((r) =>
	selector.appliesStructural(r) &&
	classHierarchy.isSubclassOf(r.enclosingClass!, cls))
	.map((r) => DynamicCallTarget(r, isVirtual: _hasOverride(r))));
	}

	/// Returns a set of common ancestors (not necessarily the smallest) for all
	/// possible targets when calling [selector] on an object with type
	/// [receiverType].
	///
	/// Caches results for each receiver/selector pair. If [receiverType] is
	/// `null` the receiver is considered dynamic and any member that matches
	/// [selector] is a possible target. Also adds relevant [noSuchMethod] and
	/// `null` targets if needed for the call.
	Iterable<DynamicCallTarget> rootsForCall(
	AbstractValue? receiverType, Selector selector) {
	final domain = closedWorld.abstractValueDomain;
	receiverType ??= domain.dynamicType;
	final selectorMask = SelectorMask(selector, receiverType);
	final cachedResult = _callCache[selectorMask];
	if (cachedResult != null) return cachedResult;

	Iterable<DynamicCallTarget> targetsForReceiver =
	domain.findRootsOfTargets(receiverType, selector, this);

	// TODO(natebiggs): Can we calculate this as part of the above call to
	// findRootsOfTargets?
	final needsNoSuchMethod = selector != Selectors.noSuchMethod_ &&
	domain
	.needsNoSuchMethodHandling(receiverType, selector)
	.isPotentiallyTrue;

	final isNull = domain.isNull(receiverType);

	if (isNull.isPotentiallyTrue) {
	// Add relevant member if null is a potential target.
	final nullMatch = closedWorld.elementEnvironment.lookupLocalClassMember(
	closedWorld.commonElements.jsNullClass, selector.memberName);
	if (nullMatch != null) {
	targetsForReceiver = {
	...targetsForReceiver,
	DynamicCallTarget.concrete(nullMatch)
	};
	}
	}

	final result = needsNoSuchMethod
	? Setlet.of(targetsForReceiver
	.followedBy(rootsForCall(receiverType, Selectors.noSuchMethod_)))
	: targetsForReceiver;

	return _callCache[selectorMask] = result;
	}

	/// Map call selectors to a getter with the same name. This allows us to
	/// ignore their call structure since overridden methods can have different
	/// call structures. This also handles method tear-offs.
	static Selector _normalizeSelector(Selector selector) =>
	selector.isCall ? Selector.getter(selector.memberName) : selector;

	static bool _skipMemberInternal(MemberEntity member) {
	return member.isStatic;
	}

	static bool skipMember(MemberEntity member, Selector selector) {
	return _skipMemberInternal(member) \|\| !selector.appliesStructural(member);
	}

	bool _hasOverride(MemberEntity member) {
	return _overrides.containsKey(member);
	}

	static List<Selector> _selectorsForMember(MemberEntity member) {
	final List<Selector> result = [];
	if (member is FieldEntity) {
	// A field implicitly defines both a getter and setter. Each of these can
	// have different overrides so we consider them separately.
	result.add(Selector.getter(member.memberName));
	result.add(Selector.setter(member.memberName));
	} else {
	final selector = Selector.fromElement(member);
	result.add(_normalizeSelector(selector));
	}
	return result;
	}

	void _handleMember(MemberEntity member, ClassEntity cls, Selector selector,
	void Function(MemberEntity parent, MemberEntity override) join) {
	final elementEnv = closedWorld.elementEnvironment;
	final name = selector.memberName;
	bool foundSuperclass = false;

	void addParent(MemberEntity child, ClassEntity childCls,
	MemberEntity parent, ClassEntity parentCls) {
	if (child == parent) return;
	if ((_overrides[parent] ??= Setlet()).add(child)) {
	join(parent, child);
	}
	}

	// Check each superclass in ascending order until we find an ancestor.
	ClassEntity? current = elementEnv.getSuperClass(cls);
	while (current != null) {
	final match = elementEnv.lookupLocalClassMember(current, name);
	if (match != null && !MemberHierarchyBuilder._skipMemberInternal(match)) {
	addParent(member, cls, match, current);
	foundSuperclass = true;
	break;
	}
	current = elementEnv.getSuperClass(current);
	}

	closedWorld.classHierarchy.getClassSet(cls).forEachSubtype((subtype) {
	final override = elementEnv.lookupClassMember(subtype, name);
	if (override == null) return IterationStep.CONTINUE;
	addParent(override, subtype, member, cls);
	return IterationStep.CONTINUE;
	}, ClassHierarchyNode.INSTANTIATED, strict: true);

	if (!foundSuperclass) {
	(_dynamicRoots[selector] ??= Setlet()).add(member);
	}
	}

	void _processMember(MemberEntity member,
	void Function(MemberEntity parent, MemberEntity override) join) {
	if (_skipMemberInternal(member)) return;
	final cls = member.enclosingClass!;
	final mixinUses = closedWorld.mixinUsesOf(cls);
	// Process each selector matching member separately.
	for (final selector in _selectorsForMember(member)) {
	for (final mixinUse in mixinUses) {
	_handleMember(member, mixinUse, selector, join);
	}
	_handleMember(member, cls, selector, join);
	}
	}

	void init(void Function(MemberEntity parent, MemberEntity override) join) {
	final liveMembers = closedWorld.liveInstanceMembers
	.followedBy(closedWorld.liveAbstractInstanceMembers);

	for (final member in liveMembers) {
	_processMember(member, join);
	}
	}

	// TODO(natebiggs): Clean up debug code below.
	void debugCall(String selectorName, String className,
	{bool nullReceiver = false,
	bool nullValue = false,
	bool subClass = false,
	bool subType = false,
	bool setter = false,
	CallStructure? call}) {
	final allMembers = closedWorld.liveInstanceMembers
	.followedBy(closedWorld.liveAbstractInstanceMembers);
	final cls = allMembers
	.firstWhere((e) => e.enclosingClass!.name == className)
	.enclosingClass!;
	final domain = closedWorld.abstractValueDomain;
	final receiver = nullValue
	? domain.nullType
	: (nullReceiver
	? null
	: (subClass
	? domain.createNonNullSubclass(cls)
	: (subType
	? domain.createNonNullSubtype(cls)
	: domain.createNullableExact(cls))));
	final name = Name(selectorName, null);
	final selector = call != null
	? Selector.call(name, call)
	: (setter ? Selector.setter(name) : Selector.getter(name));

	print('Receiver: $receiver, Selector: $selector');
	print('Locate members: ${closedWorld.locateMembers(selector, receiver)}');
	print('Targets for call: ${rootsForCall(receiver, selector).toList()}');
	}

	void dumpOverrides([String? memberName]) {
	print(_overrides.entries
	.where((e) => memberName == null \|\| e.key.name == memberName)
	.map((e) => '${e.key}\n ${e.value.join('\n ')}')
	.join('\n'));
	}

	void dumpRoots([String? selectorName]) {
	(_dynamicRoots.entries
	.where((e) => selectorName == null \|\| e.key.name == selectorName)
	.map((e) {
	final members = e.value.map((m) => m).toList();
	members.sort((a, b) => a.toString().compareTo(b.toString()));
	return MapEntry(e.key, members.join(', '));
	}).toList()
	..sort((a, b) {
	final keyComp = a.key.toString().compareTo(b.key.toString());
	return keyComp != 0 ? keyComp : a.value.compareTo(b.value);
	}))
	.forEach((e) => print('${e.key}: ${e.value}'));
	}

	void dumpCache({String? selectorName, String? receiverString}) {
	_callCache.entries
	.where((e) =>
	(selectorName == null \|\| e.key.name == selectorName) &&
	(receiverString == null \|\|
	e.key.receiver.toString().contains(receiverString)))
	.forEach((e) => print('${e.key}: ${e.value.join(', ')}'));
	}
	}