// Copyright (c) 2014, 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.

/// *Overview of deferred loading*
///
/// Deferred loading allows developers to specify deferred imports. These
/// imports represent explicit asynchronous splits of the application that
/// allows code to be delivered in pieces.
///
/// The initial download of an application will exclude code used only by
/// deferred imports. As the application reaches a
/// `deferred_import.loadLibrary()` instruction, it will download and initialize
/// any code needed by that deferred import.
///
/// Very often separate deferred imports access common code.  When that happens,
/// the compiler places the shared code in separate files. At runtime, the
/// application will only download shared code once when the first deferred
/// import that needs that code gets loaded. To achieve this, the compiler
/// generates _load lists_: a list of JavaScript files that need to be
/// downloaded for every deferred import in the program.
///
/// Each generated JavaScript file has an initialzation within it. The files can
/// be concatenated together in a bundle without affecting the initialization
/// logic. This is used by customers to reduce the download latency when they
/// know that multiple files will be loaded at once.
///
/// *The code splitting algorithm*
///
/// The goal of this library and the [DeferredLoadingTask] is to determine how
/// to best split code in multiple files according to the principles described
/// above.
///
/// We do so by partitioning code into output units ([OutputUnit]s in our
/// implementation). The partitioning reflects how code is shared between
/// different deferred imports. Each output unit is associated a set of deferred
/// imports (an [ImportSet] in our implementation). These are the deferred
/// imports that need the code that is stored in that output unit. Code that is
/// needed by a single deferred import, will be associated with a set containing
/// that deferred import only (a singleton set), but code that is shared by 10
/// deferred imports will be associated with a set containing all of those
/// imports instead.  We determine whether code is shared based on how code is
/// accessed in the program. An element is considered to be accessed by a
/// deferred import if it is either loaded and invoked from that import or
/// transitively accessed by an element that was invoked by that import.
///
/// In theory, there could be an exponential number of output units: one per
/// subset of deferred imports in the program. In practice, large apps do have a
/// large number of output units, but the result is not exponential. This is
/// both because not all deferred imports have code in common and because many
/// deferred imports end up having the same code in common.
///
/// *Main output unit*:
///
/// The main output unit contains any code accessed directly from main. Such
/// code may be accessed by deferred imports too, but because it is accessed
/// from the main entrypoint of the program, possibly synchronously, we do not
/// split out the code or defer it. Our current implementation uses an empty
/// import-set as a sentinel value to represent this output unit.
///
/// *Dependency graph*:
///
/// We use the element model to discover dependencies between elements.
/// We distinguish two kinds of dependencies: deferred or direct (aka.
/// non-deferred):
///
///   * Deferred dependencies are only used to discover root elements. Roots
///   are elements immediately loaded and used from deferred import prefixes in
///   a program.
///
///   * Direct dependencies are used to recursively update which output unit
///   should be associated with an element.
///
/// *Algorithm Principle*:
///
/// Conceptually the algorithm consists of associating an element with an
/// import-set. When we discover a root, we mark it and everything it can reach
/// as being used by that import. Marking elements as used by that import
/// consists of adding the import to the import-set of all those reachable
/// elements.
///
/// An earlier version of this algorithm was implemented with this simple
/// approach: we kept a map from entities to a [Set] of imports and updated the
/// sets iteratively. However, as customer applications grew, we needed a more
/// specialized and efficient implementation.
///
/// *ImportSet representation and related optimizations*:
///
/// The most important change to scale the algorithm was to use an efficient
/// representation of entity to import-set associations. For large apps there
/// are a lot of entities, and the simple representation of having a [Set] per
/// entity was too expensive. We observed that many of such sets had the same
/// imports (which makes sense given that many elements ended up together in the
/// same output units). This led us to design the [ImportSet] abstraction: a
/// representation of import-sets that guarantees that each import-set has a
/// canonical representation. Memory-wise this was a big win: we now bounded
/// the heap utilization to one [ImportSet] instance per unique import-set.
///
/// This representation is not perfect. Simple operations, like adding an import
/// to an import-set, are now worse-case linear. So it was important to add a
/// few optimizations in the algorithm in order to adapt to the new
/// representation.
///
/// The principle of our optimizations is to make bulk updates. Rather than
/// adding an import at a time for all reachable elements, we changed the
/// algorithm to make updates in bulk in two ways:
///
///   * Batch unions: when possible add more than one import at once, and
///
///   * Update elements in segments: when an element and its reachable
///   dependencies would change in the same way, update them all together.
///
/// To achieve these bulk updates, the algorithm uses a two tier algorithm:
///
///   * The top tier uses a worklist to track the start of a bulk update, either
///   from a root (entities that dominate code used by a single deferred import)
///   or from a merge point in the dependency graph (entities that dominate
///   shared code between multiple imports).
///
///   * The second tier is where bulk updates are made, these don't use a
///   worklist, but simply a DFS recursive traversal of the dependency graph.
///   The DFS traversal stops at merge points and makes note of them by
///   updating the top tier worklist.
///
///
/// *Example*:
///
/// Consider this dependency graph (ignoring elements in the main output unit):
///
///   deferred import A: a1 ---> s1 ---> s2  -> s3
///                              ^       ^
///                              |       |
///   deferred import B: b1 -----+       |
///                                      |
///   deferred import C: c1 ---> c2 ---> c3
///
/// Here a1, b1, and c1 are roots, while s1 and s2 are merge points. The
/// algorithm will compute a result with 5 deferred output units:
//
///   * unit {A}:        contains a1
///   * unit {B}:        contains b1
///   * unit {C}:        contains c1, c2, and c3
///   * unit {A, B}:     contains s1
///   * unit {A, B, C}:  contains s2, and s3
///
/// After marking everything reachable from main as part of the main output
/// unit, our algorithm will work as follows:
///
///   * Initially all deferred elements have no mapping.
///   * We make note of work to do, initially to mark the root of each
///     deferred import:
///        * a1 with A, and recurse from there.
///        * b1 with B, and recurse from there.
///        * c1 with C, and recurse from there.
///   * We update a1, s1, s2, s3 in bulk, from no mapping to {A}.
///   * We update b1 from no mapping to {B}, and when we find s1 we notice
///     that s1 is already associated with another import set {A}. This is a
///     merge point that can't be updated in bulk, so we make
///     note of additional work for later to mark s1 with {A, B}
///   * We update in bulk c1, c2, c3 to {C}, and make a note to update s2 with
///     {A, C} (another merge point).
///   * We update s1 to {A, B}, and update the existing note to update s2, now
///     with {A, B, C}
///   * Finally we update s2 and s3 with {A, B, C} in bulk, without ever
///     updating them to the intermediate state {A, C}.
///
/// *How bulk segment updates work?*
///
/// The principle of the bulk segment update is similar to memoizing the result
/// of a union operation. We replace a union operation with a cached result if
/// we can tell that the inputs to the operation are the same.
///
/// Our implementation doesn't use a cache table to memoize arbitrary unions.
/// Instead it only memoizes one union at a time: it tries to reuse the result
/// of a union applied to one entity, when updating the import-sets of its
/// transitive dependencies.
///
/// Consider a modification of the example above where we add s4 and s5 as
/// additional dependencies of s3. Conceptually, we are applying this sequence
/// of union operations:
///
///    importSet[s2] = importSet[s2] UNION {B, C}
///    importSet[s3] = importSet[s3] UNION {B, C}
///    importSet[s4] = importSet[s4] UNION {B, C}
///    importSet[s5] = importSet[s5] UNION {B, C}
///
/// When the algorithm is updating s2, it checks whether any of the entities
/// reachable from s2 also have the same import-set as s2, and if so, we know
/// that the union result is the same.
///
/// Our implementation uses the term `oldSet` to represent the first input of
/// the memoized union operation, and `newSet` to represent the result:
///
///    oldSet = importSet[s2]        // = A
///    newSet = oldSet UNION {B, C}  // = {A, B, C}
///
/// Then the updates are encoded as:
///
///    update(s2, oldSet, newSet);
///    update(s3, oldSet, newSet);
///    update(s4, oldSet, newSet);
///    update(s5, oldSet, newSet);
///
/// where:
///
///    update(s5, oldSet, newSet) {
///      var currentSet = importSet[s];
///      if (currentSet == oldSet) {
///        // Use the memoized result, whohoo!
///        importSet[s] = newSet;
///      } else {
///        // Don't use the memoized result, instead use the worklist to later
///        // update `s` with the appropriate union operation.
///      }
///    }
///
/// As a result of this, the update to the import set for s2, s3, s4 and s5
/// becomes a single if-check and an assignment, but the union operation was
/// only executed once.
///
/// *Constraints*:
///
/// By default our algorithm considers all deferred imports equally and
/// potentially occurring at any time in the application lifetime. In practice,
/// apps use deferred imports to layer the load of their application and, often,
/// developers know how imports will be loaded over time.
///
/// Dart2js accepts a configuration file to specify constraints about deferred
/// imports. There are many kinds of constraints that help developers encode how
/// their applications work.
///
/// To model constraints, the deferred loading algorithm was changed to include
/// _set transitions_: these are changes made to import-sets to effectively
/// encode the constraints.
///
/// Consider, for example, a program with two deferred imports `A` and `B`. Our
/// unconstrained algorithm will split the code in 3 files:
///
///   * code unique to `A` (represented by the import set `{A}`)
///
///   * code unique to `B` (represented by the import set `{B}`)
///
///   * code shared between `A and `B (represented by the import set `{A, B}`)
///
/// When an end-user loads the user journey corresponding to `A`, the code for
/// `{A}` and `{A,B}` gets loaded. When they load the user journey corresponding
/// to `B`, `{B}` and `{A, B}` gets loaded.
///
/// An ordering constraint saying that `B` always loads after `A` tells our
/// algorithm that, even though there exists code that is unique to `A`, we
/// could merge it together with the shared code between `A` and `B`, since the
/// user never intends to load `B` first. The result would be to have two files
/// instead:
///
///   * code unique to `B` (represented by the import set `{B}`)
///
///   * code unique to A and code shared between A and B (represented by the
///   import set `{A, B}`)
///
///
/// In this example, the set transition is to convert any set containing `{A}`
/// into a set containing `{A, B}`.
///
// TODO(joshualitt): update doc above when main is represented by a set
// containing an implict import corresponding to `main`.
// TODO(sigmund): investigate different heuristics for how to select the next
// work item (e.g. we might converge faster if we pick first the update that
// contains a bigger delta.)
library deferred_load;

import 'dart:collection' show Queue;

import 'package:kernel/ast.dart' as ir;

import 'dependencies.dart';
import 'import_set.dart';
import 'output_unit.dart';

import '../../compiler_new.dart' show OutputType;
import '../common/metrics.dart' show Metric, Metrics, CountMetric, DurationMetric;
import '../common/tasks.dart' show CompilerTask;
import '../common.dart';
import '../common_elements.dart' show CommonElements, KElementEnvironment;
import '../compiler.dart' show Compiler;
import '../constants/values.dart'
    show
        ConstantValue,
        ConstructedConstantValue,
        InstantiationConstantValue;
import '../elements/types.dart';
import '../elements/entities.dart';
import '../kernel/kelements.dart' show KLocalFunction;
import '../kernel/element_map.dart';
import '../universe/use.dart';
import '../universe/world_impact.dart'
    show ImpactUseCase, WorldImpact, WorldImpactVisitorImpl;
import '../util/util.dart' show makeUnique;
import '../world.dart' show KClosedWorld;

// TODO(joshualitt): Refactor logic out of DeferredLoadTask so work_queue.dart
// can be its own independent library.
part 'work_queue.dart';

class _DeferredLoadTaskMetrics implements Metrics {
  @override
  String get namespace => 'deferred_load';

  DurationMetric time = DurationMetric('time');
  CountMetric outputUnitElements = CountMetric('outputUnitElements');

  @override
  Iterable<Metric> get primary => [time];

  @override
  Iterable<Metric> get secondary => [outputUnitElements];
}

/// For each deferred import, find elements and constants to be loaded when that
/// import is loaded. Elements that are used by several deferred imports are in
/// shared OutputUnits.
class DeferredLoadTask extends CompilerTask {
  @override
  String get name => 'Deferred Loading';

  /// The OutputUnit that will be loaded when the program starts.
  OutputUnit _mainOutputUnit;

  /// A set containing (eventually) all output units that will result from the
  /// program.
  final List<OutputUnit> _allOutputUnits = [];

  /// Will be `true` if the program contains deferred libraries.
  bool isProgramSplit = false;

  static const ImpactUseCase IMPACT_USE = ImpactUseCase('Deferred load');

  /// A cache of the result of calling `computeImportDeferName` on the keys of
  /// this map.
  final Map<ImportEntity, String> importDeferName = {};

  /// A mapping from classes to their import set.
  Map<ClassEntity, ImportSet> _classToSet = {};

  /// A mapping from interface types (keyed by classes) to their import set.
  Map<ClassEntity, ImportSet> _classTypeToSet = {};

  /// A mapping from members to their import set.
  Map<MemberEntity, ImportSet> _memberToSet = {};

  /// A mapping from local functions to their import set.
  Map<Local, ImportSet> _localFunctionToSet = {};

  /// A mapping from constants to their import set.
  Map<ConstantValue, ImportSet> _constantToSet = {};

  Iterable<ImportEntity> get _allDeferredImports =>
      _deferredImportDescriptions.keys;

  /// Because the token-stream is forgotten later in the program, we cache a
  /// description of each deferred import.
  final Map<ImportEntity, ImportDescription> _deferredImportDescriptions = {};

  /// A lattice to compactly represent multiple subsets of imports.
  ImportSetLattice importSets = ImportSetLattice();

  final Compiler compiler;

  KernelToElementMap _elementMap;

  @override
  final _DeferredLoadTaskMetrics metrics = _DeferredLoadTaskMetrics();

  bool get disableProgramSplit => compiler.options.disableProgramSplit;

  DeferredLoadTask(this.compiler, this._elementMap) : super(compiler.measurer) {
    _mainOutputUnit = OutputUnit(true, 'main', {});
    importSets.mainSet.unit = _mainOutputUnit;
    _allOutputUnits.add(_mainOutputUnit);
  }

  KElementEnvironment get elementEnvironment =>
      compiler.frontendStrategy.elementEnvironment;

  CommonElements get commonElements => compiler.frontendStrategy.commonElements;
  DartTypes get dartTypes => commonElements.dartTypes;

  DiagnosticReporter get reporter => compiler.reporter;

  /// Collects all direct dependencies of [element].
  ///
  /// The collected dependent elements and constants are are added to
  /// [elements] and [constants] respectively.
  void _collectDirectMemberDependencies(KClosedWorld closedWorld,
      MemberEntity element, Dependencies dependencies) {
    // TODO(sigurdm): We want to be more specific about this - need a better
    // way to query "liveness".
    if (!closedWorld.isMemberUsed(element)) {
      return;
    }
    _collectDependenciesFromImpact(closedWorld, element, dependencies);
    collectConstantsInBody(element, dependencies);
  }

  /// Finds all elements and constants that [element] depends directly on.
  /// (not the transitive closure.)
  ///
  /// Adds the results to [elements] and [constants].
  void _collectAllElementsAndConstantsResolvedFromClass(
      KClosedWorld closedWorld,
      ClassEntity element,
      Dependencies dependencies) {
    // If we see a class, add everything its live instance members refer
    // to.  Static members are not relevant, unless we are processing
    // extra dependencies due to mirrors.
    void addLiveInstanceMember(MemberEntity member) {
      if (!closedWorld.isMemberUsed(member)) return;
      if (!member.isInstanceMember) return;
      dependencies.addMember(member);
      _collectDirectMemberDependencies(closedWorld, member, dependencies);
    }

    void addClassAndMaybeAddEffectiveMixinClass(ClassEntity cls) {
      dependencies.addClass(cls);
      if (elementEnvironment.isMixinApplication(cls)) {
        dependencies.addClass(elementEnvironment.getEffectiveMixinClass(cls));
      }
    }

    ClassEntity cls = element;
    elementEnvironment.forEachLocalClassMember(cls, addLiveInstanceMember);
    elementEnvironment.forEachSupertype(cls, (InterfaceType type) {
      _collectTypeDependencies(type, dependencies);
    });
    elementEnvironment.forEachSuperClass(cls, (superClass) {
      addClassAndMaybeAddEffectiveMixinClass(superClass);
      _collectTypeDependencies(
          elementEnvironment.getThisType(superClass), dependencies);
    });
    addClassAndMaybeAddEffectiveMixinClass(cls);
  }

  /// Finds all elements and constants that [element] depends directly on.
  /// (not the transitive closure.)
  ///
  /// Adds the results to [elements] and [constants].
  void _collectAllElementsAndConstantsResolvedFromMember(
      KClosedWorld closedWorld,
      MemberEntity element,
      Dependencies dependencies) {
    if (element is FunctionEntity) {
      _collectTypeDependencies(
          elementEnvironment.getFunctionType(element), dependencies);
    }
    if (element.isStatic || element.isTopLevel || element.isConstructor) {
      dependencies.addMember(element);
      _collectDirectMemberDependencies(closedWorld, element, dependencies);
    }
    if (element is ConstructorEntity && element.isGenerativeConstructor) {
      // When instantiating a class, we record a reference to the
      // constructor, not the class itself.  We must add all the
      // instance members of the constructor's class.
      ClassEntity cls = element.enclosingClass;
      _collectAllElementsAndConstantsResolvedFromClass(
          closedWorld, cls, dependencies);
    }

    // Other elements, in particular instance members, are ignored as
    // they are processed as part of the class.
  }

  /// Extract the set of constants that are used in the body of [element].
  void collectConstantsInBody(MemberEntity element, Dependencies dependencies) {
    ir.Member node = _elementMap.getMemberNode(element);

    // Fetch the internal node in order to skip annotations on the member.
    // TODO(sigmund): replace this pattern when the kernel-ast provides a better
    // way to skip annotations (issue 31565).
    var visitor = ConstantCollector(
        _elementMap, _elementMap.getStaticTypeContext(element), dependencies);
    if (node is ir.Field) {
      node.initializer?.accept(visitor);
      return;
    }

    if (node is ir.Constructor) {
      node.initializers.forEach((i) => i.accept(visitor));
    }
    node.function?.accept(visitor);
  }

  /// Recursively collects all the dependencies of [type].
  void _collectTypeDependencies(DartType type, Dependencies dependencies,
      [ImportEntity import]) {
    TypeDependencyVisitor(dependencies, import, commonElements).visit(type);
  }

  void _collectTypeArgumentDependencies(
      Iterable<DartType> typeArguments, Dependencies dependencies,
      [ImportEntity import]) {
    if (typeArguments == null) return;
    TypeDependencyVisitor(dependencies, import, commonElements)
        .visitList(typeArguments);
  }

  /// Extract any dependencies that are known from the impact of [element].
  void _collectDependenciesFromImpact(KClosedWorld closedWorld,
      MemberEntity element, Dependencies dependencies) {
    WorldImpact worldImpact = compiler.impactCache[element];
    compiler.impactStrategy.visitImpact(
        element,
        worldImpact,
        WorldImpactVisitorImpl(
            visitStaticUse: (MemberEntity member, StaticUse staticUse) {
          void processEntity() {
            Entity usedEntity = staticUse.element;
            if (usedEntity is MemberEntity) {
              dependencies.addMember(usedEntity, staticUse.deferredImport);
            } else {
              assert(usedEntity is KLocalFunction,
                  failedAt(usedEntity, "Unexpected static use $staticUse."));
              KLocalFunction localFunction = usedEntity;
              // TODO(sra): Consult KClosedWorld to see if signature is needed.
              _collectTypeDependencies(
                  localFunction.functionType, dependencies);
              dependencies.localFunctions.add(localFunction);
            }
          }

          switch (staticUse.kind) {
            case StaticUseKind.CONSTRUCTOR_INVOKE:
            case StaticUseKind.CONST_CONSTRUCTOR_INVOKE:
              // The receiver type of generative constructors is a dependency of
              // the constructor (handled by `addMember` above) and not a
              // dependency at the call site.
              // Factory methods, on the other hand, are like static methods so
              // the target type is not relevant.
              // TODO(johnniwinther): Use rti need data to skip unneeded type
              // arguments.
              _collectTypeArgumentDependencies(
                  staticUse.type.typeArguments, dependencies);
              processEntity();
              break;
            case StaticUseKind.STATIC_INVOKE:
            case StaticUseKind.CLOSURE_CALL:
            case StaticUseKind.DIRECT_INVOKE:
              // TODO(johnniwinther): Use rti need data to skip unneeded type
              // arguments.
              _collectTypeArgumentDependencies(
                  staticUse.typeArguments, dependencies);
              processEntity();
              break;
            case StaticUseKind.STATIC_TEAR_OFF:
            case StaticUseKind.CLOSURE:
            case StaticUseKind.STATIC_GET:
            case StaticUseKind.STATIC_SET:
              processEntity();
              break;
            case StaticUseKind.SUPER_TEAR_OFF:
            case StaticUseKind.SUPER_FIELD_SET:
            case StaticUseKind.SUPER_GET:
            case StaticUseKind.SUPER_SETTER_SET:
            case StaticUseKind.SUPER_INVOKE:
            case StaticUseKind.INSTANCE_FIELD_GET:
            case StaticUseKind.INSTANCE_FIELD_SET:
            case StaticUseKind.FIELD_INIT:
            case StaticUseKind.FIELD_CONSTANT_INIT:
              // These static uses are not relevant for this algorithm.
              break;
            case StaticUseKind.CALL_METHOD:
            case StaticUseKind.INLINING:
              failedAt(element, "Unexpected static use: $staticUse.");
              break;
          }
        }, visitTypeUse: (MemberEntity member, TypeUse typeUse) {
          void addClassIfInterfaceType(DartType t, [ImportEntity import]) {
            var typeWithoutNullability = t.withoutNullability;
            if (typeWithoutNullability is InterfaceType) {
              dependencies.addClass(typeWithoutNullability.element, import);
            }
          }

          DartType type = typeUse.type;
          switch (typeUse.kind) {
            case TypeUseKind.TYPE_LITERAL:
              _collectTypeDependencies(
                  type, dependencies, typeUse.deferredImport);
              break;
            case TypeUseKind.CONST_INSTANTIATION:
              addClassIfInterfaceType(type, typeUse.deferredImport);
              _collectTypeDependencies(
                  type, dependencies, typeUse.deferredImport);
              break;
            case TypeUseKind.INSTANTIATION:
            case TypeUseKind.NATIVE_INSTANTIATION:
              addClassIfInterfaceType(type);
              _collectTypeDependencies(type, dependencies);
              break;
            case TypeUseKind.IS_CHECK:
            case TypeUseKind.CATCH_TYPE:
              _collectTypeDependencies(type, dependencies);
              break;
            case TypeUseKind.AS_CAST:
              if (closedWorld.annotationsData
                  .getExplicitCastCheckPolicy(element)
                  .isEmitted) {
                _collectTypeDependencies(type, dependencies);
              }
              break;
            case TypeUseKind.IMPLICIT_CAST:
              if (closedWorld.annotationsData
                  .getImplicitDowncastCheckPolicy(element)
                  .isEmitted) {
                _collectTypeDependencies(type, dependencies);
              }
              break;
            case TypeUseKind.PARAMETER_CHECK:
            case TypeUseKind.TYPE_VARIABLE_BOUND_CHECK:
              if (closedWorld.annotationsData
                  .getParameterCheckPolicy(element)
                  .isEmitted) {
                _collectTypeDependencies(type, dependencies);
              }
              break;
            case TypeUseKind.RTI_VALUE:
            case TypeUseKind.TYPE_ARGUMENT:
            case TypeUseKind.NAMED_TYPE_VARIABLE_NEW_RTI:
            case TypeUseKind.CONSTRUCTOR_REFERENCE:
              failedAt(element, "Unexpected type use: $typeUse.");
              break;
          }
        }, visitDynamicUse: (MemberEntity member, DynamicUse dynamicUse) {
          // TODO(johnniwinther): Use rti need data to skip unneeded type
          // arguments.
          _collectTypeArgumentDependencies(
              dynamicUse.typeArguments, dependencies);
        }),
        DeferredLoadTask.IMPACT_USE);
  }

  /// Update the import set of all constants reachable from [constant], as long
  /// as they had the [oldSet]. As soon as we see a constant with a different
  /// import set, we stop and enqueue a new recursive update in [queue].
  ///
  /// Invariants: oldSet is either null or a subset of newSet.
  void _updateConstantRecursive(
      KClosedWorld closedWorld,
      ConstantValue constant,
      ImportSet oldSet,
      ImportSet newSet,
      WorkQueue queue) {
    if (constant == null) return;
    var currentSet = _constantToSet[constant];

    // Already visited.
    if (currentSet == newSet) return;

    // Elements in the main output unit always remain there.
    if (currentSet == importSets.mainSet) return;

    if (currentSet == oldSet) {
      _constantToSet[constant] = newSet;
      if (constant is ConstructedConstantValue) {
        ClassEntity cls = constant.type.element;
        _updateClassRecursive(closedWorld, cls, oldSet, newSet, queue);
      }
      if (constant is InstantiationConstantValue) {
        for (DartType type in constant.typeArguments) {
          type = type.withoutNullability;
          if (type is InterfaceType) {
            _updateClassRecursive(
                closedWorld, type.element, oldSet, newSet, queue);
          }
        }
      }
      constant.getDependencies().forEach((ConstantValue dependency) {
        // Constants are not allowed to refer to deferred constants, so
        // no need to check for a deferred type literal here.
        _updateConstantRecursive(
            closedWorld, dependency, oldSet, newSet, queue);
      });
    } else {
      assert(
          // Invariant: we must mark main before we mark any deferred import.
          newSet != importSets.mainSet || oldSet != null,
          failedAt(
              NO_LOCATION_SPANNABLE,
              "Tried to assign ${constant.toDartText(closedWorld.dartTypes)} "
              "to the main output unit, but it was assigned to $currentSet."));
      queue.addConstant(constant, newSet);
    }
  }

  void _updateClassRecursive(KClosedWorld closedWorld, ClassEntity element,
      ImportSet oldSet, ImportSet newSet, WorkQueue queue) {
    if (element == null) return;

    ImportSet currentSet = _classToSet[element];

    // Already visited. We may visit some root nodes a second time with
    // [isMirrorUsage] in order to mark static members used reflectively.
    if (currentSet == newSet) return;

    // Elements in the main output unit always remain there.
    if (currentSet == importSets.mainSet) return;

    if (currentSet == oldSet) {
      // Continue recursively updating from [oldSet] to [newSet].
      _classToSet[element] = newSet;

      Dependencies dependencies = Dependencies();
      _collectAllElementsAndConstantsResolvedFromClass(
          closedWorld, element, dependencies);
      LibraryEntity library = element.library;
      _processDependencies(
          closedWorld, library, dependencies, oldSet, newSet, queue, element);
    } else {
      queue.addClass(element, newSet);
    }
  }

  void _updateClassTypeRecursive(KClosedWorld closedWorld, ClassEntity element,
      ImportSet oldSet, ImportSet newSet, WorkQueue queue) {
    if (element == null) return;

    ImportSet currentSet = _classTypeToSet[element];

    // Already visited. We may visit some root nodes a second time with
    // [isMirrorUsage] in order to mark static members used reflectively.
    if (currentSet == newSet) return;

    // Elements in the main output unit always remain there.
    if (currentSet == importSets.mainSet) return;

    if (currentSet == oldSet) {
      // Continue recursively updating from [oldSet] to [newSet].
      _classTypeToSet[element] = newSet;

      Dependencies dependencies = Dependencies();
      dependencies.addClassType(element);
      LibraryEntity library = element.library;
      _processDependencies(
          closedWorld, library, dependencies, oldSet, newSet, queue, element);
    } else {
      queue.addClassType(element, newSet);
    }
  }

  void _updateMemberRecursive(KClosedWorld closedWorld, MemberEntity element,
      ImportSet oldSet, ImportSet newSet, WorkQueue queue) {
    if (element == null) return;

    ImportSet currentSet = _memberToSet[element];

    // Already visited. We may visit some root nodes a second time with
    // [isMirrorUsage] in order to mark static members used reflectively.
    if (currentSet == newSet) return;

    // Elements in the main output unit always remain there.
    if (currentSet == importSets.mainSet) return;

    if (currentSet == oldSet) {
      // Continue recursively updating from [oldSet] to [newSet].
      _memberToSet[element] = newSet;

      Dependencies dependencies = Dependencies();
      _collectAllElementsAndConstantsResolvedFromMember(
          closedWorld, element, dependencies);

      LibraryEntity library = element.library;
      _processDependencies(
          closedWorld, library, dependencies, oldSet, newSet, queue, element);
    } else {
      queue.addMember(element, newSet);
    }
  }

  void _updateLocalFunction(
      Local localFunction, ImportSet oldSet, ImportSet newSet) {
    ImportSet currentSet = _localFunctionToSet[localFunction];
    if (currentSet == newSet) return;

    // Elements in the main output unit always remain there.
    if (currentSet == importSets.mainSet) return;

    if (currentSet == oldSet) {
      _localFunctionToSet[localFunction] = newSet;
    } else {
      _localFunctionToSet[localFunction] = importSets.union(currentSet, newSet);
    }
    // Note: local functions are not updated recursively because the
    // dependencies are already visited as dependencies of the enclosing member.
  }

  /// Whether to enqueue a deferred dependency.
  ///
  /// Due to the nature of the algorithm, some dependencies may be visited more
  /// than once. However, we know that new deferred-imports are only discovered
  /// when we are visiting the main output unit (size == 0) or code reachable
  /// from a deferred import (size == 1). After that, we are rediscovering the
  /// same nodes we have already seen.
  _shouldAddDeferredDependency(ImportSet newSet) => newSet.length <= 1;

  void _processDependencies(
      KClosedWorld closedWorld,
      LibraryEntity library,
      Dependencies dependencies,
      ImportSet oldSet,
      ImportSet newSet,
      WorkQueue queue,
      Spannable context) {
    dependencies.classes.forEach((ClassEntity cls, DependencyInfo info) {
      if (info.isDeferred) {
        if (_shouldAddDeferredDependency(newSet)) {
          for (ImportEntity deferredImport in info.imports) {
            queue.addClass(cls, importSets.singleton(deferredImport));
          }
        }
      } else {
        _updateClassRecursive(closedWorld, cls, oldSet, newSet, queue);
      }
    });

    dependencies.classType.forEach((ClassEntity cls, DependencyInfo info) {
      if (info.isDeferred) {
        if (_shouldAddDeferredDependency(newSet)) {
          for (ImportEntity deferredImport in info.imports) {
            queue.addClassType(cls, importSets.singleton(deferredImport));
          }
        }
      } else {
        _updateClassTypeRecursive(closedWorld, cls, oldSet, newSet, queue);
      }
    });

    dependencies.members.forEach((MemberEntity member, DependencyInfo info) {
      if (info.isDeferred) {
        if (_shouldAddDeferredDependency(newSet)) {
          for (ImportEntity deferredImport in info.imports) {
            queue.addMember(member, importSets.singleton(deferredImport));
          }
        }
      } else {
        _updateMemberRecursive(closedWorld, member, oldSet, newSet, queue);
      }
    });

    for (Local localFunction in dependencies.localFunctions) {
      _updateLocalFunction(localFunction, oldSet, newSet);
    }

    dependencies.constants
        .forEach((ConstantValue constant, DependencyInfo info) {
      if (info.isDeferred) {
        if (_shouldAddDeferredDependency(newSet)) {
          for (ImportEntity deferredImport in info.imports) {
            queue.addConstant(constant, importSets.singleton(deferredImport));
          }
        }
      } else {
        _updateConstantRecursive(closedWorld, constant, oldSet, newSet, queue);
      }
    });
  }

  /// Computes a unique string for the name field for each outputUnit.
  void _createOutputUnits() {
    int counter = 1;
    void addUnit(ImportSet importSet) {
      if (importSet.unit != null) return;
      var unit = OutputUnit(false, '$counter',
          importSet.collectImports().map((i) => i.declaration).toSet());
      counter++;
      importSet.unit = unit;
      _allOutputUnits.add(unit);
      metrics.outputUnitElements.add(1);
    }

    // Generate an output unit for all import sets that are associated with an
    // element or constant.
    _classToSet.values.forEach(addUnit);
    _classTypeToSet.values.forEach(addUnit);
    _memberToSet.values.forEach(addUnit);
    _localFunctionToSet.values.forEach(addUnit);
    _constantToSet.values.forEach(addUnit);

    // Sort output units to make the output of the compiler more stable.
    _allOutputUnits.sort();
  }

  void _setupImportNames() {
    // If useSimpleLoadIds is true then we use a monotonically increasing number
    // to generate loadIds. Otherwise, we will use the user provided names.
    bool useIds = compiler.options.useSimpleLoadIds;
    var allDeferredImports = _allDeferredImports.toList();
    if (useIds) {
      // Sort for a canonical order of [ImportEntity]s.
      allDeferredImports.sort(compareImportEntities);
    }
    int nextDeferId = 0;
    Set<String> usedImportNames = {};
    for (ImportEntity import in allDeferredImports) {
      String result = computeImportDeferName(import, compiler);
      assert(result != null);
      if (useIds) {
        importDeferName[import] = (++nextDeferId).toString();
      } else {
        // Note: tools that process the json file to build multi-part initial load
        // bundles depend on the fact that makeUnique appends only digits, or a
        // period followed by digits.
        importDeferName[import] = makeUnique(result, usedImportNames, '.');
      }
    }
  }

  /// Returns a name for a deferred import.
  String computeImportDeferName(ImportEntity declaration, Compiler compiler) {
    assert(declaration.isDeferred);
    if (declaration.name != null) {
      return declaration.name;
    } else {
      // This happens when the deferred import isn't declared with a prefix.
      assert(compiler.compilationFailed);
      return '';
    }
  }

  /// Performs the deferred loading algorithm.
  ///
  /// See the top-level library comment for details.
  OutputUnitData run(FunctionEntity main, KClosedWorld closedWorld) {
    return metrics.time.measure(() => _run(main, closedWorld));
  }

  OutputUnitData _run(FunctionEntity main, KClosedWorld closedWorld) {
    if (!isProgramSplit || main == null || disableProgramSplit) {
      return _buildResult();
    }

    work() {
      var queue = WorkQueue(this.importSets);

      // Add `main` and their recursive dependencies to the main output unit.
      // We do this upfront to avoid wasting time visiting these elements when
      // analyzing deferred imports.
      queue.addMember(main, importSets.mainSet);

      // Also add "global" dependencies to the main output unit.  These are
      // things that the backend needs but cannot associate with a particular
      // element. This set also contains elements for which we lack precise
      // information.
      for (MemberEntity element
          in closedWorld.backendUsage.globalFunctionDependencies) {
        queue.addMember(element, importSets.mainSet);
      }
      for (ClassEntity element
          in closedWorld.backendUsage.globalClassDependencies) {
        queue.addClass(element, importSets.mainSet);
      }

      void emptyQueue() {
        while (queue.isNotEmpty) {
          WorkItem item = queue.nextItem();
          item.update(this, closedWorld, queue);
        }
      }

      emptyQueue();
    }

    reporter.withCurrentElement(main.library, () => measure(work));

    // Notify that we no longer need impacts for deferred load, so they can be
    // discarded at this time.
    compiler.impactStrategy.onImpactUsed(DeferredLoadTask.IMPACT_USE);
    return _buildResult();
  }

  // Dumps a graph as a list of strings of 0 and 1. There is one 'bit' for each
  // import entity in the graph, and each string in the list represents an
  // output unit.
  void _dumpDeferredGraph() {
    int id = 0;
    Map<ImportEntity, int> importMap = {};
    var entities = _deferredImportDescriptions.keys.toList();
    entities.sort(compareImportEntities);
    entities = entities.reversed.toList();
    for (var key in entities) {
      importMap[key] = id++;
    }
    List<String> graph = [];
    for (var outputUnit in _allOutputUnits) {
      if (!outputUnit.isMainOutput) {
        List<int> representation = List.filled(id, 0);
        for (var entity in outputUnit.imports) {
          representation[importMap[entity]] = 1;
        }
        graph.add(representation.join());
      }
    }
    compiler.outputProvider.createOutputSink(
        compiler.options.deferredGraphUri.path, '', OutputType.debug)
      ..add(graph.join('\n'))
      ..close();
  }

  OutputUnitData _buildResult() {
    _createOutputUnits();
    _setupImportNames();
    if (compiler.options.deferredGraphUri != null) {
      _dumpDeferredGraph();
    }
    Map<ClassEntity, OutputUnit> classMap = {};
    Map<ClassEntity, OutputUnit> classTypeMap = {};
    Map<MemberEntity, OutputUnit> memberMap = {};
    Map<Local, OutputUnit> localFunctionMap = {};
    Map<ConstantValue, OutputUnit> constantMap = {};
    _classToSet.forEach((cls, s) => classMap[cls] = s.unit);
    _classTypeToSet.forEach((cls, s) => classTypeMap[cls] = s.unit);
    _memberToSet.forEach((member, s) => memberMap[member] = s.unit);
    _localFunctionToSet.forEach(
        (localFunction, s) => localFunctionMap[localFunction] = s.unit);
    _constantToSet.forEach((constant, s) => constantMap[constant] = s.unit);

    _classToSet = null;
    _classTypeToSet = null;
    _memberToSet = null;
    _localFunctionToSet = null;
    _constantToSet = null;
    importSets = null;
    return OutputUnitData(
        this.isProgramSplit && !disableProgramSplit,
        this._mainOutputUnit,
        classMap,
        classTypeMap,
        memberMap,
        localFunctionMap,
        constantMap,
        _allOutputUnits,
        importDeferName,
        _deferredImportDescriptions);
  }

  void beforeResolution(Uri rootLibraryUri, Iterable<Uri> libraries) {
    measureSubtask('prepare', () {
      for (Uri uri in libraries) {
        LibraryEntity library = elementEnvironment.lookupLibrary(uri);
        reporter.withCurrentElement(library, () {
          for (ImportEntity import in elementEnvironment.getImports(library)) {
            if (import.isDeferred) {
              _deferredImportDescriptions[import] =
                  ImportDescription(import, library, rootLibraryUri);
              isProgramSplit = true;
            }
          }
        });
      }
    });
  }

  bool ignoreEntityInDump(Entity element) => false;

  /// Creates a textual representation of the output unit content.
  String dump() {
    Map<OutputUnit, List<String>> elementMap = {};
    Map<OutputUnit, List<String>> constantMap = {};
    _classToSet.forEach((ClassEntity element, ImportSet importSet) {
      if (ignoreEntityInDump(element)) return;
      var elements = elementMap.putIfAbsent(importSet.unit, () => <String>[]);
      var id = element.name ?? '$element';
      id = '$id cls';
      elements.add(id);
    });
    _classTypeToSet.forEach((ClassEntity element, ImportSet importSet) {
      if (ignoreEntityInDump(element)) return;
      var elements = elementMap.putIfAbsent(importSet.unit, () => <String>[]);
      var id = element.name ?? '$element';
      id = '$id type';
      elements.add(id);
    });
    _memberToSet.forEach((MemberEntity element, ImportSet importSet) {
      if (ignoreEntityInDump(element)) return;
      var elements = elementMap.putIfAbsent(importSet.unit, () => []);
      var id = element.name ?? '$element';
      var cls = element.enclosingClass?.name;
      if (cls != null) id = '$cls.$id';
      if (element.isSetter) id = '$id=';
      id = '$id member';
      elements.add(id);
    });
    _localFunctionToSet.forEach((Local element, ImportSet importSet) {
      if (ignoreEntityInDump(element)) return;
      var elements = elementMap.putIfAbsent(importSet.unit, () => []);
      var id = element.name ?? '$element';
      var context = (element as dynamic).memberContext.name;
      id = element.name == null || element.name == '' ? '<anonymous>' : id;
      id = '$context.$id';
      id = '$id local';
      elements.add(id);
    });
    _constantToSet.forEach((ConstantValue value, ImportSet importSet) {
      // Skip primitive values: they are not stored in the constant tables and
      // if they are shared, they end up duplicated anyways across output units.
      if (value.isPrimitive) return;
      constantMap
          .putIfAbsent(importSet.unit, () => [])
          .add(value.toStructuredText(dartTypes));
    });

    Map<OutputUnit, String> text = {};
    for (OutputUnit outputUnit in _allOutputUnits) {
      StringBuffer unitText = StringBuffer();
      if (outputUnit.isMainOutput) {
        unitText.write(' <MAIN UNIT>');
      } else {
        unitText.write(' imports:');
        var imports = outputUnit.imports
            .map((i) => '${i.enclosingLibraryUri.resolveUri(i.uri)}')
            .toList();
        for (var i in imports..sort()) {
          unitText.write('\n   $i:');
        }
      }
      List<String> elements = elementMap[outputUnit];
      if (elements != null) {
        unitText.write('\n elements:');
        for (String element in elements..sort()) {
          unitText.write('\n  $element');
        }
      }
      List<String> constants = constantMap[outputUnit];
      if (constants != null) {
        unitText.write('\n constants:');
        for (String value in constants..sort()) {
          unitText.write('\n  $value');
        }
      }
      text[outputUnit] = '$unitText';
    }

    StringBuffer sb = StringBuffer();
    for (OutputUnit outputUnit in _allOutputUnits.toList()
      ..sort((a, b) => text[a].compareTo(text[b]))) {
      sb.write('\n\n-------------------------------\n');
      sb.write('Output unit: ${outputUnit.name}');
      sb.write('\n ${text[outputUnit]}');
    }
    return sb.toString();
  }
}