// 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 'package:collection/collection.dart';
import 'package:kernel/ast.dart' as ir;
import 'package:kernel/type_environment.dart' as ir;

import '../../compiler_api.dart' as api;
import '../closure.dart';
import '../common.dart';
import '../common/elements.dart';
import '../common/metrics.dart';
import '../common/names.dart';
import '../compiler.dart';
import '../constants/values.dart';
import '../elements/entities.dart';
import '../elements/names.dart';
import '../elements/types.dart';
import '../js_backend/inferred_data.dart';
import '../js_backend/no_such_method_registry.dart';
import '../js_model/element_map.dart';
import '../js_model/elements.dart';
import '../js_model/js_world.dart';
import '../js_model/locals.dart';
import '../native/behavior.dart';
import '../options.dart';
import '../serialization/serialization.dart';
import '../universe/call_structure.dart';
import '../universe/member_hierarchy.dart';
import '../universe/selector.dart';
import '../universe/side_effects.dart';
import 'abstract_value_domain.dart';
import 'builder.dart';
import 'closure_tracer.dart';
import 'debug.dart' as debug;
import 'list_tracer.dart';
import 'locals_handler.dart';
import 'map_tracer.dart';
import 'record_tracer.dart';
import 'set_tracer.dart';
import 'type_graph_dump.dart';
import 'type_graph_nodes.dart';
import 'type_system.dart';
import 'types.dart';
import 'work_queue.dart';

/// An inferencing engine that computes a call graph of [TypeInformation] nodes
/// by visiting the AST of the application, and then does the inferencing on the
/// graph.
class InferrerEngine {
  /// A set of selector names that [List] implements, that we know return their
  /// element type.
  final Set<Selector> returnsListElementTypeSet = <Selector>{
    Selector.getter(const PublicName('first')),
    Selector.getter(const PublicName('last')),
    Selector.getter(const PublicName('single')),
    Selector.call(const PublicName('singleWhere'), CallStructure.oneArg),
    Selector.call(const PublicName('elementAt'), CallStructure.oneArg),
    Selector.index(),
    Selector.call(const PublicName('removeAt'), CallStructure.oneArg),
    Selector.call(const PublicName('removeLast'), CallStructure.noArgs),
  };

  /// The [JClosedWorld] on which inference reasoning is based.
  final JClosedWorld closedWorld;

  final TypeSystem types;
  final Map<ir.TreeNode, TypeInformation> concreteTypes = {};
  final GlobalLocalsMap globalLocalsMap;
  final InferredDataBuilder inferredDataBuilder;

  final FunctionEntity mainElement;

  final Map<Local, TypeInformation> _defaultTypeOfParameter = {};

  final WorkQueue _workQueue = WorkQueue();

  late final InferrerEngineMetrics metrics = InferrerEngineMetrics(
    closedWorld.abstractValueDomain.metrics,
  );

  final Set<MemberEntity> _analyzedElements = {};

  /// The maximum number of times we allow a node in the graph to
  /// change types. If a node reaches that limit, we give up
  /// inferencing on it and give it the dynamic type.
  /// TODO(natebiggs): This value is needed right now because some types
  /// do not converge. See https://github.com/dart-lang/sdk/issues/50626
  ///
  /// Note: Due to the encoding to track refine count for a given node this
  /// value must be less than 2^(64-N) where N is the number of values in the
  /// TypeInformation flags enum.
  static const int _maxChangeCount = 1000;

  int _overallRefineCount = 0;
  int _addedInGraph = 0;

  final CompilerOptions _options;
  final Progress _progress;
  final DiagnosticReporter _reporter;
  final api.CompilerOutput _compilerOutput;

  final Set<ConstructorEntity> _generativeConstructorsExposingThis =
      <ConstructorEntity>{};

  /// Data computed internally within elements, like the type-mask of a send a
  /// list allocation, or a for-in loop.
  final Map<MemberEntity, KernelGlobalTypeInferenceElementData> _memberData =
      <MemberEntity, KernelGlobalTypeInferenceElementData>{};

  ElementEnvironment get _elementEnvironment => closedWorld.elementEnvironment;

  AbstractValueDomain get abstractValueDomain =>
      closedWorld.abstractValueDomain;
  CommonElements get commonElements => closedWorld.commonElements;

  NoSuchMethodData get noSuchMethodData => closedWorld.noSuchMethodData;

  final MemberHierarchyBuilder memberHierarchyBuilder;
  Set<MemberEntity>? _initializedVirtualMembers = {};

  InferrerEngine(
    this._options,
    this._progress,
    this._reporter,
    this._compilerOutput,
    this.closedWorld,
    this.mainElement,
    this.globalLocalsMap,
    this.inferredDataBuilder,
  ) : types = TypeSystem(
        closedWorld,
        KernelTypeSystemStrategy(closedWorld, globalLocalsMap),
      ),
      memberHierarchyBuilder = MemberHierarchyBuilder(closedWorld),
      // Ensure `_MAX_CHANGE_COUNT` conforms to TypeInformation flag encoding.
      assert(_maxChangeCount.bitLength < 64 - TypeInformation.numTypeInfoFlags);

  /// Applies [f] to all elements in the universe that match [selector] and
  /// [mask]. If [f] returns false, aborts the iteration.
  void forEachElementMatching(
    Selector selector,
    AbstractValue? mask,
    bool Function(MemberEntity element) f,
  ) {
    final targets = memberHierarchyBuilder.rootsForCall(mask, selector);
    for (final target in targets) {
      memberHierarchyBuilder.forEachTargetMember(
        target,
        (member) => member.isAbstract || f(member),
      );
    }
  }

  // TODO(johnniwinther): Make this private again.
  KernelGlobalTypeInferenceElementData dataOfMember(MemberEntity element) =>
      _memberData[element] ??= KernelGlobalTypeInferenceElementData();

  /// Update [sideEffects] with the side effects of [callee] being
  /// called with [selector].
  void _updateSideEffects(
    SideEffectsBuilder sideEffectsBuilder,
    Selector? selector,
    MemberEntity callee,
  ) {
    if (callee is FieldEntity) {
      if (callee.isInstanceMember) {
        if (selector!.isSetter) {
          sideEffectsBuilder.setChangesInstanceProperty();
        } else if (selector.isGetter) {
          sideEffectsBuilder.setDependsOnInstancePropertyStore();
        } else {
          sideEffectsBuilder.setAllSideEffectsAndDependsOnSomething();
        }
      } else {
        if (selector!.isSetter) {
          sideEffectsBuilder.setChangesStaticProperty();
        } else if (selector.isGetter) {
          sideEffectsBuilder.setDependsOnStaticPropertyStore();
        } else {
          sideEffectsBuilder.setAllSideEffectsAndDependsOnSomething();
        }
      }
    } else if (callee.isGetter && !selector!.isGetter) {
      sideEffectsBuilder.setAllSideEffectsAndDependsOnSomething();
    } else {
      sideEffectsBuilder.addInput(
        inferredDataBuilder.getSideEffectsBuilder(callee as FunctionEntity),
      );
    }
  }

  /// Returns the type for [nativeBehavior]. See documentation on
  /// [NativeBehavior].
  TypeInformation typeOfNativeBehavior(NativeBehavior? nativeBehavior) {
    if (nativeBehavior == null) return types.dynamicType;
    List<Object> typesReturned = nativeBehavior.typesReturned;
    if (typesReturned.isEmpty) return types.dynamicType;
    TypeInformation? returnType;
    for (var type in typesReturned) {
      TypeInformation? mappedType;
      if (type == SpecialType.jsObject) {
        mappedType = types.nonNullExact(commonElements.objectClass);
      } else if (type == commonElements.stringType) {
        mappedType = types.stringType;
      } else if (type == commonElements.intType) {
        mappedType = types.intType;
      } else if (type == commonElements.numType ||
          type == commonElements.doubleType) {
        // Note: the backend double class is specifically for non-integer
        // doubles, and a native behavior returning 'double' does not guarantee
        // a non-integer return type, so we return the number type for those.
        mappedType = types.numType;
      } else if (type == commonElements.boolType) {
        mappedType = types.boolType;
      } else if (type == commonElements.nullType) {
        mappedType = types.nullType;
      } else if (type is VoidType) {
        mappedType = types.nullType;
      } else if (type is DynamicType) {
        return types.dynamicType;
      } else if (type is InterfaceType) {
        mappedType = types.nonNullSubtype(type.element);
      } else {
        mappedType = types.dynamicType;
      }
      returnType = types.computeLUB(returnType, mappedType);
      if (returnType == types.dynamicType) {
        break;
      }
    }
    return returnType!;
  }

  void updateSelectorInMember(
    MemberEntity owner,
    CallType callType,
    ir.TreeNode node,
    Selector? selector,
    AbstractValue? mask,
  ) {
    final data = dataOfMember(owner);
    assert(validCallType(callType, node));
    switch (callType) {
      case CallType.access:
        data.setReceiverTypeMask(node, mask);
        break;
      case CallType.forIn:
        if (selector == Selectors.iterator) {
          data.setIteratorTypeMask(node as ir.ForInStatement, mask);
        } else if (selector == Selectors.current) {
          data.setCurrentTypeMask(node as ir.ForInStatement, mask);
        } else {
          assert(selector == Selectors.moveNext);
          data.setMoveNextTypeMask(node as ir.ForInStatement, mask);
        }
        break;
    }
  }

  bool checkIfExposesThis(ConstructorEntity element) {
    return _generativeConstructorsExposingThis.contains(element);
  }

  void recordExposesThis(ConstructorEntity element, bool exposesThis) {
    if (exposesThis) {
      _generativeConstructorsExposingThis.add(element);
    }
  }

  bool returnsListElementType(Selector selector, AbstractValue mask) {
    return abstractValueDomain.isContainer(mask) &&
        returnsListElementTypeSet.contains(selector);
  }

  bool returnsMapValueType(Selector selector, AbstractValue mask) {
    return abstractValueDomain.isMap(mask) && selector.isIndex;
  }

  void analyzeListAndEnqueue(ListTypeInformation info) {
    if (info.analyzed) return;
    info.analyzed = true;

    ListTracerVisitor tracer = ListTracerVisitor(info, this);
    bool succeeded = tracer.run();
    if (!succeeded) return;

    info.bailedOut = false;
    info.elementType.inferred = true;
    tracer.inputs.forEach(info.elementType.addInput);
    // Enqueue the list for later refinement
    _workQueue.add(info);
    _workQueue.add(info.elementType);
  }

  void analyzeSetAndEnqueue(SetTypeInformation info) {
    if (info.analyzed) return;
    info.analyzed = true;

    SetTracerVisitor tracer = SetTracerVisitor(info, this);
    bool succeeded = tracer.run();
    if (!succeeded) return;

    info.bailedOut = false;
    info.elementType.inferred = true;

    tracer.inputs.forEach(info.elementType.addInput);
    // Enqueue the set for later refinement.
    _workQueue.add(info);
    _workQueue.add(info.elementType);
  }

  void analyzeMapAndEnqueue(MapTypeInformation info) {
    if (info.analyzed) return;
    info.analyzed = true;
    MapTracerVisitor tracer = MapTracerVisitor(info, this);

    bool succeeded = tracer.run();
    if (!succeeded) return;

    info.bailedOut = false;
    for (int i = 0; i < tracer.keyInputs.length; ++i) {
      final newType = info.addEntryInput(
        abstractValueDomain,
        tracer.keyInputs[i],
        tracer.valueInputs[i],
      );
      if (newType != null) _workQueue.add(newType);
    }
    for (final map in tracer.mapInputs) {
      _workQueue.addAll(info.addMapInput(abstractValueDomain, map));
    }

    info.markAsInferred();
    _workQueue.add(info.keyType);
    _workQueue.add(info.valueType);
    _workQueue.addAll(info.typeInfoMap.values);
    _workQueue.add(info);
  }

  void analyzeRecordAndEnqueue(RecordTypeInformation info) {
    if (info.analyzed) return;
    info.analyzed = true;
    RecordTracerVisitor tracer = RecordTracerVisitor(info, this);

    bool succeeded = tracer.run();
    if (!succeeded) return;

    info.bailedOut = false;
    _workQueue.add(info);
  }

  void runOverAllElements() {
    metrics.time.measure(_runOverAllElements);
  }

  void _runOverAllElements() {
    _initMemberHierarchy();

    metrics.analyze.measure(_analyzeAllElements);
    final dump = debug.printGraph ? TypeGraphDump(_compilerOutput, this) : null;

    dump?.beforeAnalysis();
    _buildWorkQueue();
    metrics.refine1.measure(_refine);

    // Process the refined targets of calls labeling closureized members. We do
    // not need to mark targets as called in this pass because we don't use this
    // information in global inference.
    _processCalledTargets(shouldMarkCalled: false);

    metrics.trace.measure(() {
      // Try to infer element types of lists and compute their escape information.
      for (var info in types.allocatedLists.values) {
        analyzeListAndEnqueue(info);
      }

      // Try to infer element types of sets and compute their escape information.
      for (var info in types.allocatedSets.values) {
        analyzeSetAndEnqueue(info);
      }

      // Try to infer the key and value types for maps and compute the values'
      // escape information.
      for (var info in types.allocatedMaps.values) {
        analyzeMapAndEnqueue(info);
      }

      Set<FunctionEntity> bailedOutOn = <FunctionEntity>{};

      // Trace closures to potentially infer argument types.
      for (var info in types.allocatedClosures) {
        void trace(
          Iterable<FunctionEntity> elements,
          ClosureTracerVisitor tracer,
        ) {
          tracer.run();
          if (!tracer.continueAnalyzing) {
            for (var element in elements) {
              inferredDataBuilder.registerMightBePassedToApply(element);
              if (debug.verbose) {
                print("traced closure $element as ${true} (bail)");
              }
              types.strategy.forEachParameter(element, (Local parameter) {
                types
                    .getInferredTypeOfParameter(parameter)
                    .giveUp(this, clearInputs: false);
              });
            }
            bailedOutOn.addAll(elements);
            return;
          }
          elements.where((e) => !bailedOutOn.contains(e)).forEach((
            FunctionEntity element,
          ) {
            types.strategy.forEachParameter(element, (Local parameter) {
              ParameterTypeInformation info = types.getInferredTypeOfParameter(
                parameter,
              );
              info.maybeResume();
              _workQueue.add(info);
            });
            if (tracer.tracedType.mightBePassedToFunctionApply) {
              inferredDataBuilder.registerMightBePassedToApply(element);
            }
            if (debug.verbose) {
              print(
                "traced closure $element as "
                "${inferredDataBuilder.getCurrentlyKnownMightBePassedToApply(element)}",
              );
            }
          });
        }

        if (info is ClosureTypeInformation) {
          Iterable<FunctionEntity> elements = [info.closure];
          trace(elements, ClosureTracerVisitor(elements, info, this));
        } else if (info is CallSiteTypeInformation) {
          final selector = info.selector;
          List<FunctionEntity> elements;
          if (info is StaticCallSiteTypeInformation) {
            if (selector != null && selector.isCall) {
              // This is a constructor call to a class with a call method. So we
              // need to trace the call method here.
              final calledElement = info.calledElement;
              assert(
                calledElement is ConstructorEntity &&
                    calledElement.isGenerativeConstructor,
              );
              final cls = calledElement.enclosingClass!;
              final callMethod = _lookupCallMethod(cls)!;
              elements = [callMethod];
            } else {
              elements = [info.calledElement as FunctionEntity];
            }
          } else if (info is DynamicCallSiteTypeInformation) {
            // We only are interested in functions here, as other targets
            // of this closure call are not a root to trace but an intermediate
            // for some other function.
            elements = [];
            bool processTarget(MemberEntity entity) {
              if (entity.isFunction && !entity.isAbstract) {
                elements.add(entity as FunctionEntity);
              }
              return true;
            }

            info.forEachConcreteTarget(memberHierarchyBuilder, processTarget);
          } else {
            elements = const [];
          }
          trace(elements, ClosureTracerVisitor(elements, info, this));
        } else if (info is MemberTypeInformation) {
          final member = info.member as FunctionEntity;
          trace([
            member,
          ], StaticTearOffClosureTracerVisitor(member, info, this));
        } else if (info is ParameterTypeInformation) {
          failedAt(
            noLocationSpannable,
            'Unexpected closure allocation info $info',
          );
        }
      }
    });

    dump?.beforeTracing();

    // Reset all nodes that use lists/maps that have been inferred, as well
    // as nodes that use elements fetched from these lists/maps. The
    // workset for a new run of the analysis will be these nodes.
    Set<TypeInformation> seenTypes = <TypeInformation>{};
    while (!_workQueue.isEmpty) {
      TypeInformation info = _workQueue.remove();
      if (seenTypes.contains(info)) continue;
      // If the node cannot be reset, we do not need to update its users either.
      if (!info.reset(this)) continue;
      seenTypes.add(info);
      _workQueue.addAll(info.users);
    }

    _workQueue.addAll(seenTypes);
    metrics.refine2.measure(_refine);

    // Process the refined targets of calls labeling closureized members and
    // marking targeted members as called.
    _processCalledTargets(shouldMarkCalled: true);

    if (debug.printSummary) {
      void printSorted(Iterable<String> toSort) {
        print(toSort.sorted((a, b) => a.compareTo(b)).join('\n'));
      }

      printSorted(
        types.allocatedLists.values.map((info) {
          return '${info.type} '
              'for ${abstractValueDomain.getAllocationNode(info.originalType)} '
              'at ${abstractValueDomain.getAllocationElement(info.originalType)}'
              'after ${info.refineCount}';
        }),
      );
      printSorted(
        types.allocatedSets.values.map((info) {
          return ('${info.type} '
              'for ${abstractValueDomain.getAllocationNode(info.originalType)} '
              'at ${abstractValueDomain.getAllocationElement(info.originalType)} '
              'after ${info.refineCount}');
        }),
      );
      printSorted(
        types.allocatedMaps.values.map((info) {
          return '${info.type} '
              'for ${abstractValueDomain.getAllocationNode(info.originalType)} '
              'at ${abstractValueDomain.getAllocationElement(info.originalType)}'
              'after ${info.refineCount}';
        }),
      );
      printSorted(
        types.allocatedClosures.map((TypeInformation info) {
          if (info is ElementTypeInformation) {
            return '${info.getInferredSignature(types)} for '
                '${info.debugName}';
          } else if (info is ClosureTypeInformation) {
            return '${info.getInferredSignature(types)} for '
                '${info.debugName}';
          } else if (info is DynamicCallSiteTypeInformation) {
            var str = '';
            if (info.hasClosureCallTargets) {
              str += '<Closure.call>';
            }
            info.forEachConcreteTarget(memberHierarchyBuilder, (member) {
              if (member is FunctionEntity) {
                str +=
                    '${types.getInferredSignatureOfMethod(member)} '
                    'for $member';
              } else {
                str +=
                    '${types.getInferredTypeOfMember(member).type} '
                    'for $member';
              }
              return true;
            });
            return str;
          } else if (info is StaticCallSiteTypeInformation) {
            final cls = info.calledElement.enclosingClass!;
            final callMethod = _lookupCallMethod(cls)!;
            return '${types.getInferredSignatureOfMethod(callMethod)} for $cls';
          } else {
            return '${info.type} for some unknown kind of closure';
          }
        }),
      );
      printSorted(
        _analyzedElements.map((MemberEntity elem) {
          TypeInformation type = types.getInferredTypeOfMember(elem);
          return '$elem :: $type from ${type.inputs} ';
        }),
      );
    }
    dump?.afterAnalysis();

    metrics.overallRefineCount.add(_overallRefineCount);
    _reporter.log('Inferred $_overallRefineCount types.');

    _processLoopInformation();
  }

  /// Call [analyze] for all live members.
  void _analyzeAllElements() {
    _progress.startPhase();
    final toProcess = {
      ...closedWorld.processedMembers,
      ...closedWorld.liveAbstractInstanceMembers,
    };
    for (var member in toProcess) {
      _progress.showProgress(
        'Added ',
        _addedInGraph,
        ' elements in inferencing graph.',
      );
      // This also forces the creation of the [ElementTypeInformation] to ensure
      // it is in the graph.
      types.withMember(member, () => analyze(member));
    }
    metrics.elementsInGraph.add(_addedInGraph);
    _reporter.log('Added $_addedInGraph elements in inferencing graph.');
    metrics.allTypesCount.add(types.allTypes.length);
  }

  void _initMemberHierarchy() {
    metrics.memberHierarchy.measure(
      () => memberHierarchyBuilder.init(_initializeOverrideEdges),
    );
    // Once the hierarchy is set up we will not need to initialize new
    // virtual members and can clear the initialization cache.
    _initializedVirtualMembers = null;
  }

  /// Returns the body node for [member].
  ir.Node? _computeMemberBody(MemberEntity member) {
    MemberDefinition definition = closedWorld.elementMap.getMemberDefinition(
      member,
    );
    switch (definition.kind) {
      case MemberKind.regular:
        final node = definition.node;
        if (node is ir.Field) {
          return getFieldInitializer(
            closedWorld.elementMap,
            member as FieldEntity,
          );
        } else if (node is ir.Procedure) {
          return node.function;
        }
        break;
      case MemberKind.constructor:
        return definition.node;
      case MemberKind.constructorBody:
        final node = definition.node;
        if (node is ir.Constructor) {
          return node.function;
        } else if (node is ir.Procedure) {
          return node.function;
        }
        break;
      case MemberKind.closureCall:
        final node = definition.node as ir.LocalFunction;
        return node.function;
      case MemberKind.closureField:
      case MemberKind.signature:
      case MemberKind.generatorBody:
      case MemberKind.recordGetter:
      case MemberKind.parameterStub:
        break;
    }
    failedAt(member, 'Unexpected member definition: $definition.');
  }

  /// Returns the `call` method on [cls] or the `noSuchMethod` if [cls] doesn't
  /// implement `call`.
  FunctionEntity? _lookupCallMethod(ClassEntity cls) {
    var function =
        _elementEnvironment.lookupClassMember(cls, Names.call)
            as FunctionEntity?;
    if (function == null || function.isAbstract) {
      function =
          _elementEnvironment.lookupClassMember(cls, Names.noSuchMethod_)
              as FunctionEntity?;
    }
    return function;
  }

  void analyze(MemberEntity element) {
    if (_analyzedElements.contains(element)) return;
    _analyzedElements.add(element);

    final body = _computeMemberBody(element);

    TypeInformation? type;
    _reporter.withCurrentElement(element, () {
      type = _computeMemberTypeInformation(element, body);
    });
    _addedInGraph++;

    if (element is FieldEntity) {
      final field = element;
      if (!field.isAssignable) {
        // If [element] is final and has an initializer, we record
        // the inferred type.
        if (body != null) {
          if (type is! ListTypeInformation && type is! MapTypeInformation) {
            // For non-container types, the constant handler does
            // constant folding that could give more precise results.
            final value = _getFieldConstant(field as JField);
            if (value != null) {
              if (value is FunctionConstantValue) {
                type = types.allocateClosure(value.element);
              } else {
                // Although we might find a better type, we have to keep
                // the old type around to ensure that we get a complete view
                // of the type graph and do not drop any flow edges.
                AbstractValue refinedType = abstractValueDomain
                    .computeAbstractValueForConstant(value);
                type = NarrowTypeInformation(
                  abstractValueDomain,
                  type!,
                  refinedType,
                );
                types.allocatedTypes.add(type!);
              }
            }
          }
          recordTypeOfField(field, type!);
        } else if (!element.isInstanceMember) {
          recordTypeOfField(field, types.nullType);
        }
      } else if (body == null) {
        // Only update types of static fields if there is no
        // assignment. Instance fields are dealt with in the constructor.
        if (element.isStatic || element.isTopLevel) {
          recordTypeOfField(field, type!);
        }
      } else {
        recordTypeOfField(field, type!);
      }
      if ((element.isStatic || element.isTopLevel) &&
          body != null &&
          !element.isConst) {
        if (_isFieldInitializerPotentiallyNull(element, body)) {
          recordTypeOfField(field, types.nullType);
        }
      }
    } else {
      final method = element as FunctionEntity;
      // Abstract methods don't have a body so they won't have a return type.
      if (!method.isAbstract) recordReturnType(method, type!);
    }
  }

  /// Visits [body] to compute the [TypeInformation] node for [member].
  TypeInformation _computeMemberTypeInformation(
    MemberEntity member,
    ir.Node? body,
  ) {
    final node = closedWorld.elementMap.getMemberContextNode(member);

    KernelTypeGraphBuilder visitor = KernelTypeGraphBuilder(
      _options,
      closedWorld,
      this,
      member,
      body,
      globalLocalsMap.getLocalsMap(member),
      node != null
          ? ir.StaticTypeContext(
              node,
              closedWorld.elementMap.typeEnvironment,
              cache: ir.StaticTypeCacheImpl(),
            )
          : null,
      memberHierarchyBuilder,
    );
    return visitor.run();
  }

  /// Returns `true` if the [initializer] of the non-const static or top-level
  /// [field] is potentially `null`.
  bool _isFieldInitializerPotentiallyNull(
    FieldEntity field,
    ir.Node initializer,
  ) {
    // TODO(13429): We could do better here by using the
    // constant handler to figure out if it's a lazy field or not.
    // TODO(johnniwinther): Implement the ad-hoc check in ast inferrer? This
    // mimics that ast inferrer which return `true` for [ast.Send] and
    // non-const [ast.NewExpression].
    if (initializer is ir.InstanceInvocation ||
        initializer is ir.InstanceGetterInvocation ||
        initializer is ir.DynamicInvocation ||
        initializer is ir.FunctionInvocation ||
        initializer is ir.LocalFunctionInvocation ||
        initializer is ir.EqualsNull ||
        initializer is ir.EqualsCall ||
        initializer is ir.InstanceGet ||
        initializer is ir.DynamicGet ||
        initializer is ir.InstanceTearOff ||
        initializer is ir.FunctionTearOff ||
        initializer is ir.InstanceSet ||
        initializer is ir.DynamicSet ||
        initializer is ir.StaticInvocation ||
        initializer is ir.StaticGet ||
        initializer is ir.StaticTearOff ||
        initializer is ir.StaticSet ||
        initializer is ir.Let ||
        initializer is ir.ConstructorInvocation && !initializer.isConst) {
      return true;
    }
    return false;
  }

  /// Returns the [ConstantValue] for the initial value of [field], or
  /// `null` if the initializer is not a constant value.
  ConstantValue? _getFieldConstant(JField field) {
    return closedWorld.fieldAnalysis.getFieldData(field).initialValue;
  }

  /// Returns `true` if [cls] has a 'call' method.
  bool _hasCallType(ClassEntity cls) {
    return closedWorld.dartTypes.getCallType(
          closedWorld.elementEnvironment.getThisType(cls),
        ) !=
        null;
  }

  void _processLoopInformation() {
    for (var info in types.allocatedCalls) {
      if (!info.inLoop) continue;
      // We can't compute the callees of closures, no new information to add.
      if (info is ClosureCallSiteTypeInformation) {
        continue;
      }
      if (info is StaticCallSiteTypeInformation) {
        MemberEntity member = info.calledElement;
        inferredDataBuilder.addFunctionCalledInLoop(member);
      } else if (info is DynamicCallSiteTypeInformation &&
          info.mask != null &&
          abstractValueDomain.containsAll(info.mask!).isDefinitelyFalse) {
        // For instance methods, we only register a selector called in a
        // loop if it is a typed selector, to avoid marking too many
        // methods as being called from within a loop. This cuts down
        // on the code bloat.
        info.forEachConcreteTarget(memberHierarchyBuilder, (
          MemberEntity element,
        ) {
          inferredDataBuilder.addFunctionCalledInLoop(element);
          return true;
        });
      }
    }
  }

  void _refine() {
    _progress.startPhase();
    while (!_workQueue.isEmpty) {
      _progress.showProgress('Inferred ', _overallRefineCount, ' types.');
      TypeInformation info = _workQueue.remove();
      AbstractValue oldType = info.type;

      // In order to ensure that types are always getting wider we union the old
      // and new refined types. This ensures that we do not get caught in any
      // refinement loops that can arise from horizontal or downward
      // (i.e. narrowing) moves in the type lattice.
      //
      // This tends to produce comparable results to not doing the union and
      // often with fewer refine steps since the natural progression of these
      // refines is to take us up the lattice anyway.
      AbstractValue newType = abstractValueDomain.union(
        oldType,
        info.refine(this),
      );
      // Check that refinement has not accidentally changed the type.
      assert(oldType == info.type);
      if (info.abandonInferencing) info.doNotEnqueue = true;
      if ((info.type = newType) != oldType) {
        _overallRefineCount++;
        info.incrementRefineCount();
        if (info.refineCount > _maxChangeCount) {
          metrics.exceededMaxChangeCount.add();
          if (debug.anomalyWarn) {
            print("ANOMALY WARNING: max refinement reached for $info");
          }
          info.giveUp(this);
          info.type = info.refine(this);
          info.doNotEnqueue = true;
        }
        _workQueue.addAll(info.users);
        if (info.hasStableType(this)) {
          info.stabilize(this);
        }
      }
    }
  }

  void _buildWorkQueue() {
    _workQueue.addAll(types.orderedTypeInformations);
    _workQueue.addAll(types.allocatedTypes);
    _workQueue.addAll(types.allocatedClosures);
    _workQueue.addAll(types.allocatedCalls);
  }

  /// Update the inputs to parameters in the graph. [remove] tells whether
  /// inputs must be added or removed. If [addToQueue] is `true`, parameters are
  /// added to the work queue. Returns `true` if the call requires [callee] to
  /// be closurized. If [virtualCall] is `true` inputs are added and removed
  /// from the virtual types for [callee].
  bool updateParameterInputs(
    TypeInformation callSiteType,
    MemberEntity callee,
    ArgumentsTypes? arguments,
    Selector? selector, {
    required bool remove,
    required bool addToQueue,
    bool virtualCall = false,
  }) {
    if (callee.name == Identifiers.noSuchMethod_) return false;
    if (callee is FieldEntity) {
      if (selector!.isSetter) {
        ElementTypeInformation info = types.getInferredTypeOfMember(
          callee,
          virtual: virtualCall,
        );
        if (remove) {
          info.removeInput(arguments!.positional[0]);
        } else {
          info.addInput(arguments!.positional[0]);
        }
        if (addToQueue) _workQueue.add(info);
      }
    } else if (callee.isGetter) {
      return false;
    } else if (selector != null && selector.isGetter) {
      // We are tearing a function off and thus create a closure.
      assert(callee.isFunction);
      final memberInfo = types.getInferredTypeOfMember(
        callee,
        virtual: virtualCall,
      );
      _markForClosurization(
        memberInfo,
        callSiteType,
        remove: remove,
        addToQueue: addToQueue,
        isVirtualCall: virtualCall,
      );
      return true;
    } else {
      final method = callee as FunctionEntity;
      ParameterStructure parameterStructure = method.parameterStructure;
      int parameterIndex = 0;
      final localArguments = arguments!;
      types.strategy.forEachParameter(callee, (Local parameter) {
        TypeInformation? type;
        if (parameterIndex < parameterStructure.requiredPositionalParameters) {
          type = localArguments.positional[parameterIndex];
        } else if (parameterStructure.namedParameters.isNotEmpty) {
          type = localArguments.named[parameter.name];
        } else if (parameterIndex < localArguments.positional.length) {
          type = localArguments.positional[parameterIndex];
        }
        type ??= getDefaultTypeOfParameter(parameter);
        TypeInformation info = types.getInferredTypeOfParameter(
          parameter,
          isVirtual: virtualCall,
        );
        if (remove) {
          info.removeInput(type);
        } else {
          info.addInput(type);
        }
        parameterIndex++;
        if (addToQueue) _workQueue.add(info);
      });
    }
    return false;
  }

  /// Adds edges between the virtual type information for [parent] and
  /// [override] based on the type of each member. If the virtual type
  /// information for either does not exist yet, create it and initialize
  /// it by adding edges to the concrete type information for that member.
  /// Passed to [MemberHierarchyBuilder.init] to be called as it discovers
  /// overrides.
  ///
  /// Possible override configurations (parent/override):
  /// - field/getter
  /// - field/setter
  /// - field/field
  /// - getter/getter
  /// - getter/field
  /// - setter/setter
  /// - setter/field
  /// - method/method
  void _initializeOverrideEdges(MemberEntity parent, MemberEntity override) {
    // Skip adding edges for Object.noSuchMethod since it cannot virtually
    // dispatch to other implementations of NSM. However, user-defined NSM
    // methods do need to handle virtual dispatch.
    if (parent == commonElements.objectNoSuchMethod) return;
    final parentType = _getAndSetupVirtualMember(parent);
    final overrideType = _getAndSetupVirtualMember(override);

    _addOverrideTypeInputs(parent, override, parentType, overrideType);
  }

  void _setupVirtualCall(
    MemberTypeInformation virtualCallType,
    MemberEntity member,
  ) {
    if (member is FieldEntity || member.isGetter) {
      final realMember = types.getInferredTypeOfMember(member);
      virtualCallType.addInput(realMember);
      if (member.isAssignable) {
        realMember.addInput(virtualCallType);
      }
    } else {
      assert(member.isSetter || member.isFunction);
      types.strategy.forEachParameter(member as FunctionEntity, (
        Local parameter,
      ) {
        final virtualParamInfo = types.getInferredTypeOfParameter(
          parameter,
          isVirtual: true,
        );
        final realParamInfo = types.getInferredTypeOfParameter(parameter);
        realParamInfo.addInput(virtualParamInfo);
        assert(virtualParamInfo.users.first == realParamInfo);
      });
      if (member.isFunction) {
        virtualCallType.addInput(types.getInferredTypeOfMember(member));
      }
    }
  }

  void _addOverrideParameterEdges(MemberEntity parent, MemberEntity override) {
    final method = parent as FunctionEntity;
    ParameterStructure parameterStructure = method.parameterStructure;
    int parameterIndex = 0;
    // Collect the parent parameter type infos.
    final List<TypeInformation> positional = [];
    final Map<String, TypeInformation> named = {};
    types.strategy.forEachParameter(parent, (Local parameter) {
      TypeInformation type = types.getInferredTypeOfParameter(
        parameter,
        isVirtual: true,
      );
      if (parameterIndex < parameterStructure.requiredPositionalParameters) {
        positional.add(type);
      } else if (parameterStructure.namedParameters.isNotEmpty) {
        named[parameter.name!] = type;
      } else if (parameterIndex < parameterStructure.positionalParameters) {
        positional.add(type);
      }
      parameterIndex++;
    });
    parameterIndex = 0;

    // Add the parent parameter type infos as inputs to the override's
    // parameters.
    types.strategy.forEachParameter(override as FunctionEntity, (
      Local parameter,
    ) {
      TypeInformation? parentParamInfo;
      if (parameterIndex < parameterStructure.requiredPositionalParameters) {
        parentParamInfo = positional[parameterIndex];
      } else if (parameterStructure.namedParameters.isNotEmpty) {
        parentParamInfo = named[parameter.name];
      } else if (parameterIndex < positional.length) {
        parentParamInfo = positional[parameterIndex];
      }
      // If the override includes parameters that the parent doesn't
      // (optional parameters) then use the override's default type as any
      // default value will be used within the body of the override.
      parentParamInfo ??= getDefaultTypeOfParameter(parameter);
      TypeInformation overrideParamInfo = types.getInferredTypeOfParameter(
        parameter,
        isVirtual: true,
      );
      overrideParamInfo.addInput(parentParamInfo);
      parameterIndex++;
    });
  }

  MemberTypeInformation _getAndSetupVirtualMember(MemberEntity member) {
    final memberType = types.getInferredTypeOfMember(member, virtual: true);
    if (_initializedVirtualMembers!.add(member)) {
      _setupVirtualCall(memberType, member);
    }
    return memberType;
  }

  void _addOverrideTypeInputs(
    MemberEntity parent,
    MemberEntity override,
    MemberTypeInformation parentType,
    MemberTypeInformation overrideType,
  ) {
    if (parent is FieldEntity) {
      if (override.isGetter) {
        parentType.addInput(overrideType);
      } else if (override.isSetter) {
        types.strategy.forEachParameter(override as FunctionEntity, (
          Local parameter,
        ) {
          final paramInfo = types.getInferredTypeOfParameter(
            parameter,
            isVirtual: true,
          );
          paramInfo.addInput(parentType);
        });
      } else {
        assert(override is FieldEntity);
        parentType.addInput(overrideType);
        if (parent.isAssignable) {
          // Parent has an implicit setter so the types of set values need to
          // flow into the override.
          overrideType.addInput(parentType);
        }
      }
    } else if (parent.isGetter) {
      assert(override.isGetter || override is FieldEntity);
      parentType.addInput(overrideType);
    } else if (parent.isSetter) {
      if (override.isSetter) {
        _addOverrideParameterEdges(parent, override);
      } else {
        assert(override is FieldEntity);
        types.strategy.forEachParameter(parent as FunctionEntity, (
          Local parameter,
        ) {
          final paramInfo = types.getInferredTypeOfParameter(
            parameter,
            isVirtual: true,
          );
          overrideType.addInput(paramInfo);
        });
      }
    } else {
      assert(parent.isFunction && override.isFunction);
      parentType.addInput(overrideType);
      _addOverrideParameterEdges(parent, override);
    }
  }

  void _markForClosurization(
    MemberTypeInformation memberInfo,
    TypeInformation callSiteType, {
    required bool remove,
    required bool addToQueue,
    required bool isVirtualCall,
  }) {
    final member = memberInfo.member;
    if (remove) {
      memberInfo.closurizedCount--;
    } else {
      memberInfo.closurizedCount++;
      if (member.isStatic || member.isTopLevel) {
        types.allocatedClosures.add(memberInfo);
      } else {
        // We add the call-site type information here so that we
        // can benefit from further refinement of the selector.
        types.allocatedClosures.add(callSiteType);
      }
      types.strategy.forEachParameter(member as FunctionEntity, (
        Local parameter,
      ) {
        ParameterTypeInformation info = types.getInferredTypeOfParameter(
          parameter,
          isVirtual: isVirtualCall,
        );
        info.tagAsTearOffClosureParameter(this);
        if (addToQueue) _workQueue.add(info);
      });
    }
  }

  /// Iterate through reachable members for the given target. Label relevant
  /// members as needing closurization if necessary. If [shouldMarkCalled] then
  /// also mark reachable members as called.
  void _processDynamicTarget(
    DynamicCallTarget target,
    DynamicCallSiteTypeInformation callSiteType, {
    required bool shouldMarkCalled,
  }) {
    final virtualType = types.getInferredTypeOfMember(
      target.member,
      virtual: true,
    );
    final needsClosurization = virtualType.closurizedCount > 0;

    // There is nothing to do so no need to iterate over target members.
    if (!needsClosurization && !shouldMarkCalled) return;

    bool handleTarget(MemberEntity member) {
      if (!member.isAbstract) {
        MemberTypeInformation info = types.getInferredTypeOfMember(member);
        if (shouldMarkCalled) info.markCalled();

        if (needsClosurization) {
          _markForClosurization(
            info,
            callSiteType,
            remove: false,
            addToQueue: false,
            isVirtualCall: target.isVirtual,
          );
        }
      }
      return true;
    }

    memberHierarchyBuilder.forEachTargetMember(target, handleTarget);
  }

  /// Update call information for targets of calls.
  ///
  /// Marks targets of dynamic calls that need closuraization. If [shouldMarkCalled]
  /// is true any members targeted by a dynamic or static call is also marked
  /// as being called.
  void _processCalledTargets({required bool shouldMarkCalled}) {
    for (final call in types.allocatedCalls) {
      if (call is DynamicCallSiteTypeInformation) {
        for (final target in call.targets) {
          _processDynamicTarget(
            target,
            call,
            shouldMarkCalled: shouldMarkCalled,
          );
        }
      } else if (shouldMarkCalled && call is StaticCallSiteTypeInformation) {
        types.getInferredTypeOfMember(call.calledElement).markCalled();
      }
    }
  }

  /// Sets the type of a parameter's default value to [type]. If the global
  /// mapping in `_defaultTypeOfParameter` already contains a type, it must be
  /// a [PlaceholderTypeInformation], which will be replaced. All its uses are
  /// updated.
  void setDefaultTypeOfParameter(Local parameter, TypeInformation type) {
    final existing = _defaultTypeOfParameter[parameter];
    _defaultTypeOfParameter[parameter] = type;
    TypeInformation info = types.getInferredTypeOfParameter(parameter);
    if (existing != null && existing is PlaceholderTypeInformation) {
      TypeInformation virtualInfo = types.getInferredTypeOfParameter(
        parameter,
        isVirtual: true,
      );
      // Replace references to [existing] to use [type] instead.
      info.inputs.replace(existing, type);
      virtualInfo.inputs.replace(existing, type);
      // Also forward all users.
      type.addUsersOf(existing);
    } else {
      assert(existing == null);
    }
  }

  /// Returns the [TypeInformation] node for the default value of a parameter.
  /// If this is queried before it is set by [setDefaultTypeOfParameter], a
  /// [PlaceholderTypeInformation] is returned, which will later be replaced
  /// by the actual node when [setDefaultTypeOfParameter] is called.
  ///
  /// Invariant: After graph construction, no [PlaceholderTypeInformation] nodes
  /// should be present and a default type for each parameter should exist.
  TypeInformation getDefaultTypeOfParameter(Local parameter) {
    return _defaultTypeOfParameter.putIfAbsent(parameter, () {
      return PlaceholderTypeInformation(
        abstractValueDomain,
        types.currentMember,
      );
    });
  }

  /// Returns the type of [element].
  ParameterTypeInformation typeOfParameter(Local element) {
    return types.getInferredTypeOfParameter(element);
  }

  MemberTypeInformation _inferredTypeOfMember(
    MemberEntity element, {
    required bool isVirtual,
  }) {
    return types.getInferredTypeOfMember(element, virtual: isVirtual);
  }

  MemberTypeInformation inferredTypeOfTarget(DynamicCallTarget target) {
    return _inferredTypeOfMember(target.member, isVirtual: target.isVirtual);
  }

  /// Returns the type of [element].
  TypeInformation typeOfMember(MemberEntity element, {bool isVirtual = false}) {
    if (element is FunctionEntity) return types.functionType;
    return _inferredTypeOfMember(element, isVirtual: isVirtual);
  }

  /// Returns the return type of [element].
  TypeInformation returnTypeOfMember(
    MemberEntity element, {
    bool isVirtual = false,
  }) {
    if (element is! FunctionEntity) return types.dynamicType;
    return _inferredTypeOfMember(element, isVirtual: isVirtual);
  }

  /// Records that [element] is of type [type].
  void recordTypeOfField(FieldEntity element, TypeInformation type) {
    types.getInferredTypeOfMember(element).addInput(type);
  }

  /// Records that the return type [element] is of type [type].
  void recordReturnType(FunctionEntity element, TypeInformation type) {
    TypeInformation info = types.getInferredTypeOfMember(element);
    if (element.name == '==') {
      // Even if x.== doesn't return a bool, 'x == null' evaluates to 'false'.
      info.addInput(types.boolType);
    }

    if (info.inputs.isEmpty) info.addInput(type);
  }

  /// Notifies to the inferrer that [analyzedElement] can have return type
  /// [newType]. [currentType] is the type the inference has currently found.
  ///
  /// Returns the new type for [analyzedElement].
  TypeInformation addReturnTypeForMethod(
    FunctionEntity element,
    TypeInformation newType,
  ) {
    TypeInformation type = types.getInferredTypeOfMember(element);
    // TODO(ngeoffray): Clean up. We do this check because
    // [SimpleTypesInferrer] deals with two different inferrers.
    if (element is ConstructorEntity && element.isGenerativeConstructor) {
      return type;
    }
    type.addInput(newType);
    return type;
  }

  /// Registers that [caller] calls [callee] at location [node], with
  /// [selector], and [arguments]. Note that [selector] is null for forwarding
  /// constructors.
  ///
  /// [sideEffectsBuilder] will be updated to incorporate [callee]'s side
  /// effects.
  ///
  /// [inLoop] tells whether the call happens in a loop.
  TypeInformation registerCalledMember(
    ir.Node node,
    Selector? selector,
    MemberEntity caller,
    MemberEntity callee,
    ArgumentsTypes? arguments,
    SideEffectsBuilder sideEffectsBuilder,
    bool inLoop,
  ) {
    CallSiteTypeInformation info = StaticCallSiteTypeInformation(
      abstractValueDomain,
      types.currentMember,
      node,
      caller,
      callee,
      selector,
      arguments,
      inLoop,
    );
    // If this class has a 'call' method then we have essentially created a
    // closure here. Register it as such so that it is traced.
    // Note: we exclude factory constructors because they don't always create an
    // instance of the type. They are static methods that delegate to some other
    // generative constructor to do the actual creation of the object.
    if (selector != null &&
        selector.isCall &&
        callee is ConstructorEntity &&
        callee.isGenerativeConstructor) {
      ClassEntity cls = callee.enclosingClass;
      if (_hasCallType(cls)) {
        types.allocatedClosures.add(info);
      }
    }
    info.addToGraph(this);
    types.allocatedCalls.add(info);
    _updateSideEffects(sideEffectsBuilder, selector, callee);
    return info;
  }

  /// Registers that [caller] calls [selector] with [receiverType] as receiver,
  /// and [arguments].
  ///
  /// [sideEffectsBuilder] will be updated to incorporate the potential callees'
  /// side effects.
  ///
  /// [inLoop] tells whether the call happens in a loop.
  TypeInformation registerCalledSelector(
    CallType callType,
    ir.Node node,
    Selector selector,
    AbstractValue? mask,
    TypeInformation receiverType,
    MemberEntity caller,
    ArgumentsTypes? arguments,
    SideEffectsBuilder sideEffectsBuilder, {
    required bool inLoop,
    required bool isConditional,
  }) {
    if (selector.isMaybeClosureCall && node is! ir.InstanceGetterInvocation) {
      // If node is an InstanceGetterInvocation then the target is an invocation
      // of a closure retreived from an instance member (field or getter) rather
      // than a method invocation.
      return registerCalledClosure(
        node,
        selector,
        receiverType,
        caller,
        arguments,
        sideEffectsBuilder,
        inLoop: inLoop,
      );
    }

    if (closedWorld.includesClosureCall(selector, mask)) {
      sideEffectsBuilder.setAllSideEffectsAndDependsOnSomething();
    }

    forEachElementMatching(selector, mask, (element) {
      _updateSideEffects(sideEffectsBuilder, selector, element);
      return true;
    });

    CallSiteTypeInformation info = DynamicCallSiteTypeInformation(
      abstractValueDomain,
      types.currentMember,
      callType,
      node,
      caller,
      selector,
      mask,
      receiverType,
      arguments,
      inLoop,
      isConditional,
    );
    info.addToGraph(this);
    types.allocatedCalls.add(info);
    return info;
  }

  /// Registers a call to await with an expression of type [argumentType] as
  /// argument.
  TypeInformation registerAwait(
    ir.AwaitExpression node,
    TypeInformation argument,
  ) {
    AwaitTypeInformation info = AwaitTypeInformation(
      abstractValueDomain,
      types.currentMember!,
      node,
    );
    info.addInput(argument);
    types.allocatedTypes.add(info);
    return info;
  }

  /// Registers a call to yield with an expression of type [argumentType] as
  /// argument.
  TypeInformation registerYield(ir.Node node, TypeInformation argument) {
    YieldTypeInformation info = YieldTypeInformation(
      abstractValueDomain,
      types.currentMember,
      node,
    );
    info.addInput(argument);
    types.allocatedTypes.add(info);
    return info;
  }

  /// Registers that [caller] calls [closure] with [arguments].
  ///
  /// [sideEffectsBuilder] will be updated to incorporate the potential callees'
  /// side effects.
  ///
  /// [inLoop] tells whether the call happens in a loop.
  TypeInformation registerCalledClosure(
    ir.Node node,
    Selector selector,
    TypeInformation closure,
    MemberEntity caller,
    ArgumentsTypes? arguments,
    SideEffectsBuilder sideEffectsBuilder, {
    required bool inLoop,
  }) {
    sideEffectsBuilder.setAllSideEffectsAndDependsOnSomething();
    CallSiteTypeInformation info = ClosureCallSiteTypeInformation(
      abstractValueDomain,
      types.currentMember,
      node,
      caller,
      selector,
      closure,
      arguments,
      inLoop,
    );
    info.addToGraph(this);
    types.allocatedCalls.add(info);
    return info;
  }

  void clear() {
    if (retainDataForTesting) return;

    void cleanup(TypeInformation info) {
      info.cleanup();
    }

    types.allocatedCalls.forEach(cleanup);
    types.allocatedCalls.clear();

    _defaultTypeOfParameter.clear();

    types.parameterTypeInformations.values.forEach(cleanup);
    types.memberTypeInformations.values.forEach(cleanup);

    types.allocatedTypes.forEach(cleanup);
    types.allocatedTypes.clear();

    types.concreteTypes.clear();

    types.allocatedClosures.forEach(cleanup);
    types.allocatedClosures.clear();

    _analyzedElements.clear();
    _generativeConstructorsExposingThis.clear();

    types.allocatedMaps.values.forEach(cleanup);
    types.allocatedSets.values.forEach(cleanup);
    types.allocatedLists.values.forEach(cleanup);

    _memberData.clear();
  }

  Map<MemberEntity, Set<MemberEntity>>? _cachedCallersOfForTesting;

  Iterable<MemberEntity>? getCallersOfForTesting(MemberEntity element) {
    if (_cachedCallersOfForTesting == null) {
      final callers = _cachedCallersOfForTesting = {};
      for (final callSite in types.allocatedCalls) {
        if (callSite is StaticCallSiteTypeInformation) {
          (callers[callSite.calledElement] ??= {}).add(callSite.caller);
        } else if (callSite is DynamicCallSiteTypeInformation) {
          callSite.forEachConcreteTarget(memberHierarchyBuilder, (member) {
            (callers[member] ??= {}).add(callSite.caller);
            return true;
          });
        }
      }
    }
    return _cachedCallersOfForTesting![element];
  }

  /// Returns the type of [element] when being called with [selector].
  TypeInformation typeOfMemberWithSelector(
    MemberEntity element,
    Selector? selector, {
    required bool isVirtual,
  }) {
    if (element.name == Identifiers.noSuchMethod_ &&
        selector!.name != element.name) {
      // An invocation can resolve to a [noSuchMethod], in which case
      // we get the return type of [noSuchMethod].
      return returnTypeOfMember(element);
    } else if (selector!.isGetter) {
      if (element.isFunction) {
        return types.functionType;
      } else if (element is FieldEntity) {
        return typeOfMember(element, isVirtual: isVirtual);
      } else if (element.isGetter) {
        return returnTypeOfMember(element, isVirtual: isVirtual);
      } else {
        assert(false, failedAt(element, "Unexpected member $element"));
        return types.dynamicType;
      }
    } else if (element.isGetter || element is FieldEntity) {
      assert(selector.isCall || selector.isSetter);
      return types.dynamicType;
    } else {
      return returnTypeOfMember(element, isVirtual: isVirtual);
    }
  }

  /// Returns true if global optimizations such as type inferencing can apply to
  /// the field [element].
  ///
  /// One category of elements that do not apply is runtime helpers that the
  /// backend calls, but the optimizations don't see those calls.
  bool canFieldBeUsedForGlobalOptimizations(FieldEntity element) {
    if (closedWorld.backendUsage.isFieldUsedByBackend(element)) {
      return false;
    }
    if ((element.isTopLevel || element.isStatic) && !element.isAssignable) {
      return true;
    }
    return true;
  }

  /// Returns true if global optimizations such as type inferencing can apply to
  /// the parameter [element].
  ///
  /// One category of elements that do not apply is runtime helpers that the
  /// backend calls, but the optimizations don't see those calls.
  bool canFunctionParametersBeUsedForGlobalOptimizations(
    FunctionEntity function,
  ) {
    return !closedWorld.backendUsage.isFunctionUsedByBackend(function);
  }

  /// Returns `true` if inference of parameter types is disabled for [member].
  bool assumeDynamic(MemberEntity member) {
    return closedWorld.annotationsData.hasAssumeDynamic(member);
  }
}

class InferrerEngineMetrics extends MetricsBase {
  final time = DurationMetric('time');
  final analyze = DurationMetric('time.analyze');
  final memberHierarchy = DurationMetric('time.memberHierarchy');
  final refine1 = DurationMetric('time.refine1');
  final trace = DurationMetric('time.trace');
  final refine2 = DurationMetric('time.refine2');
  final elementsInGraph = CountMetric('count.elementsInGraph');
  final allTypesCount = CountMetric('count.allTypes');
  final exceededMaxChangeCount = CountMetric('count.exceededMaxChange');
  final overallRefineCount = CountMetric('count.overallRefines');

  InferrerEngineMetrics(Metrics subMetrics) {
    primary = [time, ...subMetrics.primary];
    secondary = [
      analyze,
      memberHierarchy,
      refine1,
      trace,
      refine2,
      elementsInGraph,
      allTypesCount,
      exceededMaxChangeCount,
      overallRefineCount,
      ...subMetrics.secondary,
    ];
  }
}

class KernelTypeSystemStrategy implements TypeSystemStrategy {
  final JClosedWorld _closedWorld;
  final GlobalLocalsMap _globalLocalsMap;

  KernelTypeSystemStrategy(this._closedWorld, this._globalLocalsMap);

  JElementEnvironment get _elementEnvironment =>
      _closedWorld.elementEnvironment;

  @override
  bool checkClassEntity(ClassEntity cls) => true;

  @override
  bool checkMapNode(ir.Node node) => true;

  @override
  bool checkSetNode(ir.Node node) => true;

  @override
  bool checkListNode(ir.Node node) => true;

  @override
  bool checkLoopPhiNode(ir.Node node) => true;

  @override
  bool checkPhiNode(ir.Node? node) =>
      node == null || node is ir.TryCatch || node is ir.TryFinally;

  @override
  void forEachParameter(
    FunctionEntity function,
    void Function(Local parameter) f,
  ) {
    forEachOrderedParameterAsLocal(
      _globalLocalsMap,
      _closedWorld.elementMap,
      function,
      (Local parameter, {required bool isElided}) {
        f(parameter);
      },
    );
  }

  @override
  ParameterTypeInformation createParameterTypeInformation(
    AbstractValueDomain abstractValueDomain,
    covariant JLocal parameter,
    TypeSystem types, {
    required bool isVirtual,
  }) {
    MemberEntity context = parameter.memberContext;
    KernelToLocalsMap localsMap = _globalLocalsMap.getLocalsMap(context);
    ir.FunctionNode functionNode = localsMap.getFunctionNodeForParameter(
      parameter,
    );
    DartType type = localsMap.getLocalType(_closedWorld.elementMap, parameter);
    late final MemberEntity member;
    bool isClosure = false;
    final parent = functionNode.parent;
    if (parent is ir.Member) {
      member = _closedWorld.elementMap.getMember(parent);
    } else if (parent is ir.LocalFunction) {
      ClosureRepresentationInfo info = _closedWorld.closureDataLookup
          .getClosureInfo(parent);
      member = info.callMethod!;
      isClosure = true;
    }
    MemberTypeInformation memberTypeInformation = types.getInferredTypeOfMember(
      member,
    );
    if (isClosure) {
      return ParameterTypeInformation.localFunction(
        abstractValueDomain,
        memberTypeInformation,
        parameter,
        type,
        member as FunctionEntity,
      );
    } else if (member.isInstanceMember) {
      return ParameterTypeInformation.instanceMember(
        abstractValueDomain,
        memberTypeInformation,
        parameter,
        type,
        member as FunctionEntity,
        ParameterInputs.instanceMember(),
        isVirtual: isVirtual,
      );
    } else {
      return ParameterTypeInformation.static(
        abstractValueDomain,
        memberTypeInformation,
        parameter,
        type,
        member as FunctionEntity,
      );
    }
  }

  @override
  MemberTypeInformation createMemberTypeInformation(
    AbstractValueDomain abstractValueDomain,
    MemberEntity member,
  ) {
    if (member is FieldEntity) {
      final field = member;
      DartType type = _elementEnvironment.getFieldType(field);
      return FieldTypeInformation(abstractValueDomain, field, type);
    } else if (member.isGetter) {
      final getter = member as FunctionEntity;
      DartType type = _elementEnvironment.getFunctionType(getter);
      return GetterTypeInformation(
        abstractValueDomain,
        getter,
        type as FunctionType,
      );
    } else if (member.isSetter) {
      final setter = member as FunctionEntity;
      return SetterTypeInformation(abstractValueDomain, setter);
    } else if (member.isFunction) {
      final method = member as FunctionEntity;
      DartType type = _elementEnvironment.getFunctionType(method);
      return MethodTypeInformation(
        abstractValueDomain,
        method,
        type as FunctionType,
      );
    } else {
      final constructor = member as ConstructorEntity;
      if (constructor.isFactoryConstructor) {
        DartType type = _elementEnvironment.getFunctionType(constructor);
        return FactoryConstructorTypeInformation(
          abstractValueDomain,
          constructor,
          type as FunctionType,
        );
      } else {
        return GenerativeConstructorTypeInformation(
          abstractValueDomain,
          constructor,
        );
      }
    }
  }
}

class KernelGlobalTypeInferenceElementData
    implements GlobalTypeInferenceElementData {
  /// Tag used for identifying serialized [GlobalTypeInferenceElementData]
  /// objects in a debugging data stream.
  static const String tag = 'global-type-inference-element-data';

  // TODO(natebiggs): Can we remove nulls from these maps.
  Map<ir.TreeNode, AbstractValue?>? _receiverMap;

  Map<ir.ForInStatement, AbstractValue?>? _iteratorMap;
  Map<ir.ForInStatement, AbstractValue?>? _currentMap;
  Map<ir.ForInStatement, AbstractValue?>? _moveNextMap;

  KernelGlobalTypeInferenceElementData();

  KernelGlobalTypeInferenceElementData.internal(
    this._receiverMap,
    this._iteratorMap,
    this._currentMap,
    this._moveNextMap,
  );

  /// Deserializes a [GlobalTypeInferenceElementData] object from [source].
  factory KernelGlobalTypeInferenceElementData.readFromDataSource(
    DataSourceReader source,
    ir.Member? context,
    AbstractValueDomain abstractValueDomain,
  ) {
    return source.inMemberContext(context, () {
      source.begin(tag);
      Map<ir.TreeNode, AbstractValue>? sendMap = source
          .readTreeNodeMapInContextOrNull(
            () => abstractValueDomain.readAbstractValueFromDataSource(source),
          );
      Map<ir.ForInStatement, AbstractValue>? iteratorMap = source
          .readTreeNodeMapInContextOrNull(
            () => abstractValueDomain.readAbstractValueFromDataSource(source),
          );
      Map<ir.ForInStatement, AbstractValue>? currentMap = source
          .readTreeNodeMapInContextOrNull(
            () => abstractValueDomain.readAbstractValueFromDataSource(source),
          );
      Map<ir.ForInStatement, AbstractValue>? moveNextMap = source
          .readTreeNodeMapInContextOrNull(
            () => abstractValueDomain.readAbstractValueFromDataSource(source),
          );
      source.end(tag);
      return KernelGlobalTypeInferenceElementData.internal(
        sendMap,
        iteratorMap,
        currentMap,
        moveNextMap,
      );
    });
  }

  @override
  void writeToDataSink(
    DataSinkWriter sink,
    ir.Member? context,
    AbstractValueDomain abstractValueDomain,
  ) {
    sink.inMemberContext(context, () {
      sink.begin(tag);
      sink.writeTreeNodeMapInContextOrNull(
        _receiverMap,
        (AbstractValue? value) =>
            abstractValueDomain.writeAbstractValueToDataSink(sink, value),
      );
      sink.writeTreeNodeMapInContextOrNull(
        _iteratorMap,
        (AbstractValue? value) =>
            abstractValueDomain.writeAbstractValueToDataSink(sink, value),
      );
      sink.writeTreeNodeMapInContextOrNull(
        _currentMap,
        (AbstractValue? value) =>
            abstractValueDomain.writeAbstractValueToDataSink(sink, value),
      );
      sink.writeTreeNodeMapInContextOrNull(
        _moveNextMap,
        (AbstractValue? value) =>
            abstractValueDomain.writeAbstractValueToDataSink(sink, value),
      );
      sink.end(tag);
    });
  }

  @override
  GlobalTypeInferenceElementData? compress() {
    final receiverMap = _receiverMap;
    if (receiverMap != null) {
      receiverMap.removeWhere(_mapsToNull);
      if (receiverMap.isEmpty) {
        _receiverMap = null;
      }
    }
    final iteratorMap = _iteratorMap;
    if (iteratorMap != null) {
      iteratorMap.removeWhere(_mapsToNull);
      if (iteratorMap.isEmpty) {
        _iteratorMap = null;
      }
    }
    final currentMap = _currentMap;
    if (currentMap != null) {
      currentMap.removeWhere(_mapsToNull);
      if (currentMap.isEmpty) {
        _currentMap = null;
      }
    }
    final moveNextMap = _moveNextMap;
    if (moveNextMap != null) {
      moveNextMap.removeWhere(_mapsToNull);
      if (moveNextMap.isEmpty) {
        _moveNextMap = null;
      }
    }
    if (_receiverMap == null &&
        _iteratorMap == null &&
        _currentMap == null &&
        _moveNextMap == null) {
      return null;
    }
    return this;
  }

  @override
  AbstractValue? typeOfReceiver(ir.TreeNode node) {
    if (_receiverMap == null) return null;
    return _receiverMap![node];
  }

  void setCurrentTypeMask(ir.ForInStatement node, AbstractValue? mask) {
    final currentMap = _currentMap ??= <ir.ForInStatement, AbstractValue?>{};
    currentMap[node] = mask;
  }

  void setMoveNextTypeMask(ir.ForInStatement node, AbstractValue? mask) {
    final moveNextMap = _moveNextMap ??= <ir.ForInStatement, AbstractValue?>{};
    moveNextMap[node] = mask;
  }

  void setIteratorTypeMask(ir.ForInStatement node, AbstractValue? mask) {
    final iteratorMap = _iteratorMap ??= <ir.ForInStatement, AbstractValue?>{};
    iteratorMap[node] = mask;
  }

  @override
  AbstractValue? typeOfIteratorCurrent(covariant ir.ForInStatement node) {
    if (_currentMap == null) return null;
    return _currentMap![node];
  }

  @override
  AbstractValue? typeOfIteratorMoveNext(covariant ir.ForInStatement node) {
    if (_moveNextMap == null) return null;
    return _moveNextMap![node];
  }

  @override
  AbstractValue? typeOfIterator(covariant ir.ForInStatement node) {
    if (_iteratorMap == null) return null;
    return _iteratorMap![node];
  }

  void setReceiverTypeMask(ir.TreeNode node, AbstractValue? mask) {
    final receiverMap = _receiverMap ??= <ir.TreeNode, AbstractValue?>{};
    receiverMap[node] = mask;
  }
}

bool _mapsToNull(ir.TreeNode node, AbstractValue? value) => value == null;