// Copyright (c) 2020, 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 'dart:collection';
import '../../common_elements.dart' show ElementEnvironment;
import '../../deferred_load.dart'
    show ImportDescription, OutputUnit, OutputUnitData, deferredPartFileName;
import '../../elements/entities.dart';
import '../../deferred_load.dart' show OutputUnit;
import '../../js/js.dart' as js;
import '../../options.dart';
import '../model.dart';

/// This file contains a number of abstractions used by dart2js for emitting and
/// merging deferred fragments.
///
/// The initial deferred loading algorithm breaks a program up into multiple
/// [OutputUnits] where each [OutputUnit] represents part of the user's
/// program. [OutputUnits] are represented by a unique intersection of imports
/// known as an import set. Thus, each [OutputUnit] is a node in a deferred
/// graph. Edges in this graph are dependencies between [OutputUnits].
///
/// [OutputUnits] have a notion of successors and predecessors, that is a
/// successor to an [OutputUnit] is an [OutputUnit] that must be loaded first. A
/// predecessor to an [OutputUnit] is an [OutputUnit] that must be loaded later.
///
/// To load some given deferred library, a list of [OutputUnits] must be loaded
/// in the correct order, with their successors loaded first, then the given
/// [OutputUnit], then the [OutputUnits] predecessors.
///
/// To give a concrete example, say our graph looks like:
///    {a}   {b}   {c}
///
///     {a, b} {b, c}
///
///       {a, b, c}
///
/// Where each set above is the import set of an [OutputUnit]. We say that
/// {a}, {b}, and {c} are root [OutputUnits], i.e. [OutputUnits] with no
/// predecessors, and {a, b, c} is a leaf [OutputUnit], i.e. [OutputUnits]
/// with no successors.
///
/// We then have three load lists:
///   a: {a, b, c}, {a, b}, {a}
///   b: {a, b, c}, {a, b}, {b, c}, {b}
///   c: {a, b, c}, {b, c}, {c}
///
/// In all 3 load lists, {a, b, c} must be loaded first. All of the other
/// [OutputUnits] are predecessors of {a, b, c}. {a, b, c} is a successor to all
/// other [OutputUnits].
///
/// However, the dart2js deferred loading algorithm generates a very granular
/// sparse graph of [OutputUnits] and in many cases it is desireable to coalesce
/// smaller [OutputUnits] together into larger chunks of code to reduce the
/// number of files which have to be sent to the client. To do this
/// cleanly, we use various abstractions to merge [OutputUnits].
///
/// First, we emit the code for each [OutputUnit] into an [EmittedOutputUnit].
/// An [EmittedOutputUnit] is the Javascript representation of an [OutputUnit].
/// [EmittedOutputUnits] map 1:1 to [OutputUnits].
///
/// We wrap each [EmittedOutputUnit] in a [PreFragment], which is just a wrapper
/// to facilitate merging of [EmittedOutputUnits]. Then, we run a merge
/// algorithm on these [PreFragments], merging them together until some
/// threshold.
///
/// Once we are finished merging [PreFragments], we must now decide on their
/// final representation in Javascript.
///
/// Depending on the results of the merge, we chose one of two representations.
/// For example, say we merge {a, b} and {a} into {a, b}+{a}. In this case our
/// new load lists look like:
///
///   a: {a, b, c}, {a, b}+{a}
///   b: {a, b, c}, {a, b}+{a}, {b, c}, {b}
///   c: {a, b, c}, {b, c}, {c}
///
/// This adds a bit of extra code to the 'b' load list, but otherwise there are
/// no problems. In this case, we will interleave [EmittedOutputUnits] into a
/// single [CodeFragment], with a single top level initialization function. This
/// approach results in lower overhead, because the runtime can initialize the
/// {a, b}+{a} [CodeFragment] with a single invocation of a top level function.
///
/// Ideally we would interleave all [EmittedOutputUnits] in each [PreFragment]
/// into a single [CodeFragment]. We would then write this single
/// [CodeFragment] into a single [FinalizedFragment], where a
/// [FinalizedFragment] is just an abstraction representing a single file on
/// disk. Unfortunately this is not always possible to do efficiently.
///
/// Specifically, lets say we decide to merge {a} and {c} into {a}+{c}
/// In this case, our load lists now look like:
///
///   a: {a, b, c}, {a, b}, {a}+{c}
///   b: {a, b, c}, {a, b}, {b, c}, {b}
///   c: {a, b, c}, {b, c}, {a}+{c}
///
/// Now, load lists 'a' and 'c' are invalid. Specifically, load list 'a' is
/// missing {c}'s dependency {b, c} and load list 'c' is missing {a}'s
/// dependency {a, b}. We could bloat both load lists with the necessary
/// dependencies, but this would negate any performance benefit from
/// interleaving.
///
/// Instead, when this happens we emit {a} and {c} into separate
/// [CodeFragments], with separate top level initalization functions that are
/// only called when the necessary dependencies for initialization are
/// present. These [CodeFragments] end up in a single [FinalizedFragment].
/// While this approach doesn't have the performance benefits of
/// interleaving, it at least reduces the total number of files which need to be
/// sent to the client.

class EmittedOutputUnit {
  final OutputUnit outputUnit;
  final List<Library> libraries;
  final js.Statement classPrototypes;
  final js.Statement closurePrototypes;
  final js.Statement inheritance;
  final js.Statement methodAliases;
  final js.Statement tearOffs;
  final js.Statement constants;
  final js.Statement typeRules;
  final js.Statement variances;
  final js.Statement staticNonFinalFields;
  final js.Statement lazyInitializers;
  final js.Statement nativeSupport;

  EmittedOutputUnit(
      this.outputUnit,
      this.libraries,
      this.classPrototypes,
      this.closurePrototypes,
      this.inheritance,
      this.methodAliases,
      this.tearOffs,
      this.constants,
      this.typeRules,
      this.variances,
      this.staticNonFinalFields,
      this.lazyInitializers,
      this.nativeSupport);

  CodeFragment toCodeFragment(Program program) {
    return CodeFragment(
        [outputUnit],
        libraries,
        classPrototypes,
        closurePrototypes,
        inheritance,
        methodAliases,
        tearOffs,
        constants,
        typeRules,
        variances,
        staticNonFinalFields,
        lazyInitializers,
        nativeSupport,
        program.metadataTypesForOutputUnit(outputUnit));
  }
}

class PreFragment {
  final String outputFileName;
  final List<EmittedOutputUnit> emittedOutputUnits = [];
  final Set<PreFragment> successors = {};
  final Set<PreFragment> predecessors = {};
  FinalizedFragment finalizedFragment;
  int size = 0;
  // TODO(joshualitt): interleave dynamically when it makes sense.
  bool shouldInterleave = false;

  PreFragment(
      this.outputFileName, EmittedOutputUnit emittedOutputUnit, this.size) {
    emittedOutputUnits.add(emittedOutputUnit);
  }

  PreFragment mergeAfter(PreFragment that) {
    assert(this != that);
    this.emittedOutputUnits.addAll(that.emittedOutputUnits);
    this.successors.remove(that);
    this.predecessors.remove(that);
    that.successors.forEach((fragment) {
      if (fragment == this) return;
      this.successors.add(fragment);
      fragment.predecessors.remove(that);
      fragment.predecessors.add(this);
    });
    that.predecessors.forEach((fragment) {
      if (fragment == this) return;
      this.predecessors.add(fragment);
      fragment.successors.remove(that);
      fragment.successors.add(this);
    });
    that.clearAll();
    this.size += that.size;
    return this;
  }

  /// Interleaves the [EmittedOutputUnits] into a single [CodeFragment].
  CodeFragment interleaveEmittedOutputUnits(Program program) {
    var seedEmittedOutputUnit = emittedOutputUnits.first;
    if (emittedOutputUnits.length == 1) {
      return seedEmittedOutputUnit.toCodeFragment(program);
    } else {
      var seedOutputUnit = seedEmittedOutputUnit.outputUnit;
      List<Library> libraries = [];
      List<OutputUnit> outputUnits = [seedOutputUnit];
      List<js.Statement> classPrototypes = [];
      List<js.Statement> closurePrototypes = [];
      List<js.Statement> inheritance = [];
      List<js.Statement> methodAliases = [];
      List<js.Statement> tearOffs = [];
      List<js.Statement> constants = [];
      List<js.Statement> typeRules = [];
      List<js.Statement> variances = [];
      List<js.Statement> staticNonFinalFields = [];
      List<js.Statement> lazyInitializers = [];
      List<js.Statement> nativeSupport = [];
      for (var emittedOutputUnit in emittedOutputUnits) {
        var thatOutputUnit = emittedOutputUnit.outputUnit;
        if (seedOutputUnit != thatOutputUnit) {
          program.mergeOutputUnitMetadata(seedOutputUnit, thatOutputUnit);
          outputUnits.add(thatOutputUnit);
        }
        libraries.addAll(emittedOutputUnit.libraries);
        classPrototypes.add(emittedOutputUnit.classPrototypes);
        closurePrototypes.add(emittedOutputUnit.closurePrototypes);
        inheritance.add(emittedOutputUnit.inheritance);
        methodAliases.add(emittedOutputUnit.methodAliases);
        tearOffs.add(emittedOutputUnit.tearOffs);
        constants.add(emittedOutputUnit.constants);
        typeRules.add(emittedOutputUnit.typeRules);
        variances.add(emittedOutputUnit.variances);
        staticNonFinalFields.add(emittedOutputUnit.staticNonFinalFields);
        lazyInitializers.add(emittedOutputUnit.lazyInitializers);
        nativeSupport.add(emittedOutputUnit.nativeSupport);
      }
      return CodeFragment(
          outputUnits,
          libraries,
          js.Block(classPrototypes),
          js.Block(closurePrototypes),
          js.Block(inheritance),
          js.Block(methodAliases),
          js.Block(tearOffs),
          js.Block(constants),
          js.Block(typeRules),
          js.Block(variances),
          js.Block(staticNonFinalFields),
          js.Block(lazyInitializers),
          js.Block(nativeSupport),
          program.metadataTypesForOutputUnit(seedOutputUnit));
    }
  }

  /// Bundles [EmittedOutputUnits] into multiple [CodeFragments].
  List<CodeFragment> bundleEmittedOutputUnits(Program program) {
    List<CodeFragment> codeFragments = [];
    for (var emittedOutputUnit in emittedOutputUnits) {
      codeFragments.add(emittedOutputUnit.toCodeFragment(program));
    }
    return codeFragments;
  }

  /// Finalizes this [PreFragment] into a single [FinalizedFragment] by either
  /// interleaving [EmittedOutputUnits] into a single [CodeFragment] or by
  /// bundling [EmittedOutputUnits] into multiple [CodeFragments].
  FinalizedFragment finalize(
      Program program,
      Map<OutputUnit, CodeFragment> outputUnitMap,
      Map<CodeFragment, FinalizedFragment> codeFragmentMap) {
    assert(finalizedFragment == null);
    List<CodeFragment> codeFragments = shouldInterleave
        ? [interleaveEmittedOutputUnits(program)]
        : bundleEmittedOutputUnits(program);
    finalizedFragment = FinalizedFragment(outputFileName, codeFragments);
    codeFragments.forEach((codeFragment) {
      codeFragmentMap[codeFragment] = finalizedFragment;
      codeFragment.outputUnits.forEach((outputUnit) {
        outputUnitMap[outputUnit] = codeFragment;
      });
    });
    return finalizedFragment;
  }

  @override
  String toString() {
    // This is not an efficient operation and should only be used for debugging.
    var successors =
        this.successors.map((fragment) => fragment.debugName()).join(',');
    var predecessors =
        this.predecessors.map((fragment) => fragment.debugName()).join(',');
    var name = debugName();
    return 'PreFragment(fragments=[$name], successors=[$successors], '
        'predecessors=[$predecessors])';
  }

  String debugName() {
    var outputUnitStrings = [];
    for (var emittedOutputUnit in emittedOutputUnits) {
      var importString = [];
      for (var import in emittedOutputUnit.outputUnit.imports) {
        importString.add(import.name);
      }
      outputUnitStrings.add('{${importString.join(', ')}}');
    }
    return "${outputUnitStrings.join('+')}";
  }

  /// Clears all [PreFragment] data structure and zeros out the size. Should be
  /// used only after merging to GC internal data structures.
  void clearAll() {
    emittedOutputUnits.clear();
    successors.clear();
    predecessors.clear();
    size = 0;
  }
}

class CodeFragment {
  final List<OutputUnit> outputUnits;
  final List<Library> libraries;
  final js.Statement classPrototypes;
  final js.Statement closurePrototypes;
  final js.Statement inheritance;
  final js.Statement methodAliases;
  final js.Statement tearOffs;
  final js.Statement constants;
  final js.Statement typeRules;
  final js.Statement variances;
  final js.Statement staticNonFinalFields;
  final js.Statement lazyInitializers;
  final js.Statement nativeSupport;
  final js.Expression deferredTypes;

  CodeFragment(
      this.outputUnits,
      this.libraries,
      this.classPrototypes,
      this.closurePrototypes,
      this.inheritance,
      this.methodAliases,
      this.tearOffs,
      this.constants,
      this.typeRules,
      this.variances,
      this.staticNonFinalFields,
      this.lazyInitializers,
      this.nativeSupport,
      this.deferredTypes);

  bool isEmptyStatement(js.Statement statement) {
    if (statement is js.Block) {
      return statement.statements.isEmpty;
    }
    return statement is js.EmptyStatement;
  }

  bool get isEmpty {
    // TODO(sra): How do we tell if [deferredTypes] is empty? It is filled-in
    // later via the program finalizers. So we should defer the decision on the
    // emptiness of the fragment until the finalizers have run.  For now we seem
    // to get away with the fact that type indexes are either (1) main unit or
    // (2) local to the emitted unit, so there is no such thing as a type in a
    // deferred unit that is referenced from another deferred unit.  If we did
    // not emit any functions, then we probably did not use the signature types
    // in the OutputUnit's types, leaving them unused and tree-shaken.
    // TODO(joshualitt): Currently, we ignore [typeRules] when determining
    // emptiness because the type rules never seem to be empty.
    return isEmptyStatement(classPrototypes) &&
        isEmptyStatement(closurePrototypes) &&
        isEmptyStatement(inheritance) &&
        isEmptyStatement(methodAliases) &&
        isEmptyStatement(tearOffs) &&
        isEmptyStatement(constants) &&
        isEmptyStatement(staticNonFinalFields) &&
        isEmptyStatement(lazyInitializers) &&
        isEmptyStatement(nativeSupport);
  }

  @override
  String toString() {
    List<String> outputUnitStrings = [];
    for (var outputUnit in outputUnits) {
      List<String> importStrings = [];
      for (var import in outputUnit.imports) {
        importStrings.add(import.name);
      }
      outputUnitStrings.add('{${importStrings.join(', ')}}');
    }
    return outputUnitStrings.join('+');
  }
}

class FinalizedFragment {
  final String outputFileName;
  final List<CodeFragment> codeFragments;

  FinalizedFragment(this.outputFileName, this.codeFragments);

  // The 'main' [OutputUnit] for this [FinalizedFragment].
  // TODO(joshualitt): Refactor this to more clearly disambiguate between
  // [OutputUnits](units of deferred merging), fragments(units of emitted code),
  // and files.
  OutputUnit get canonicalOutputUnit => codeFragments.first.outputUnits.first;

  @override
  String toString() {
    List<String> strings = [];
    for (var codeFragment in codeFragments) {
      strings.add(codeFragment.toString());
    }
    return 'FinalizedFragment([${strings.join(', ')}])';
  }
}

class _Partition {
  int size = 0;
  List<PreFragment> fragments = [];
  bool isClosed = false;

  void add(PreFragment that) {
    size += that.size;
    fragments.add(that);
  }
}

class FragmentMerger {
  final CompilerOptions _options;
  final ElementEnvironment _elementEnvironment;
  final OutputUnitData outputUnitData;
  int totalSize = 0;

  FragmentMerger(this._options, this._elementEnvironment, this.outputUnitData);

  // Converts a map of (loadId, List<OutputUnit>) to two maps.
  // The first is a map of (loadId, List<FinalizedFragment>), which is used to
  // compute which files need to be loaded for a given loadId.
  // The second is a map of (loadId, List<CodeFragment>) which is used to
  // compute which CodeFragments need to be loaded for a given loadId.
  void computeFragmentsToLoad(
      Map<String, List<OutputUnit>> outputUnitsToLoad,
      Map<OutputUnit, CodeFragment> outputUnitMap,
      Map<CodeFragment, FinalizedFragment> codeFragmentMap,
      Set<OutputUnit> omittedOutputUnits,
      Map<String, List<CodeFragment>> codeFragmentsToLoad,
      Map<String, List<FinalizedFragment>> finalizedFragmentsToLoad) {
    outputUnitsToLoad.forEach((loadId, outputUnits) {
      Set<CodeFragment> uniqueCodeFragments = {};
      Set<FinalizedFragment> uniqueFinalizedFragments = {};
      List<FinalizedFragment> finalizedFragments = [];
      List<CodeFragment> codeFragments = [];
      for (var outputUnit in outputUnits) {
        if (omittedOutputUnits.contains(outputUnit)) continue;
        var codeFragment = outputUnitMap[outputUnit];
        if (uniqueCodeFragments.add(codeFragment)) {
          codeFragments.add(codeFragment);
        }
        var finalizedFragment = codeFragmentMap[codeFragment];
        if (uniqueFinalizedFragments.add(finalizedFragment)) {
          finalizedFragments.add(finalizedFragment);
        }
      }
      codeFragmentsToLoad[loadId] = codeFragments;
      finalizedFragmentsToLoad[loadId] = finalizedFragments;
    });
  }

  /// Given a list of OutputUnits sorted by their import entites,
  /// returns a map of all the direct edges between output units.
  Map<OutputUnit, Set<OutputUnit>> createDirectEdges(
      List<OutputUnit> allOutputUnits) {
    Map<OutputUnit, Set<OutputUnit>> backEdges = {};
    for (int i = 0; i < allOutputUnits.length; i++) {
      var a = allOutputUnits[i];
      var aImports = a.imports;
      for (int j = i + 1; j < allOutputUnits.length; j++) {
        var b = allOutputUnits[j];
        if (b.imports.containsAll(aImports)) {
          backEdges[b] ??= {};

          // Remove transitive edges from nodes that will reach 'b' from the
          // edge we just added.
          // Note: Because we add edges in order (starting from the smallest
          // sets) we always add transitive edges before the last direct edge.
          backEdges[b].removeWhere((c) => aImports.containsAll(c.imports));

          // Create an edge to denote that 'b' must be loaded before 'a'.
          backEdges[b].add(a);
        }
      }
    }

    Map<OutputUnit, Set<OutputUnit>> forwardEdges = {};
    backEdges.forEach((b, edges) {
      for (var a in edges) {
        (forwardEdges[a] ??= {}).add(b);
      }
    });
    return forwardEdges;
  }

  /// Attachs predecessors and successors to each PreFragment.
  /// Expects outputUnits to be sorted.
  void attachDependencies(
      List<OutputUnit> outputUnits, List<PreFragment> preDeferredFragments) {
    // Create a map of OutputUnit to Fragment.
    Map<OutputUnit, PreFragment> outputUnitMap = {};
    for (var preFragment in preDeferredFragments) {
      var outputUnit = preFragment.emittedOutputUnits.single.outputUnit;
      outputUnitMap[outputUnit] = preFragment;
      totalSize += preFragment.size;
    }

    // Get a list of direct edges and then attach them to PreFragments.
    var allEdges = createDirectEdges(outputUnits);
    allEdges.forEach((outputUnit, edges) {
      var predecessor = outputUnitMap[outputUnit];
      for (var edge in edges) {
        var successor = outputUnitMap[edge];
        predecessor.successors.add(successor);
        successor.predecessors.add(predecessor);
      }
    });
  }

  /// Given a list of [PreFragments], returns a list of lists of [PreFragments]
  /// where each list represents a component in the graph.
  List<List<PreFragment>> separateComponents(
      List<PreFragment> preDeferredFragments) {
    List<List<PreFragment>> components = [];
    Set<PreFragment> visited = {};

    // Starting from each 'root' in the graph, use bfs to find a component.
    for (var preFragment in preDeferredFragments) {
      if (preFragment.predecessors.isEmpty && visited.add(preFragment)) {
        List<PreFragment> component = [];
        var queue = Queue<PreFragment>();
        queue.add(preFragment);
        while (queue.isNotEmpty) {
          var preFragment = queue.removeFirst();
          component.add(preFragment);
          preFragment.predecessors.where(visited.add).forEach(queue.add);
          preFragment.successors.where(visited.add).forEach(queue.add);
        }

        // Sort the fragments in the component so they will be in a canonical
        // order.
        component.sort((a, b) {
          return a.emittedOutputUnits.single.outputUnit
              .compareTo(b.emittedOutputUnits.single.outputUnit);
        });
        components.add(component);
      }
    }
    return components;
  }

  /// A trivial greedy merge that uses the sorted order of the output units to
  /// merge contiguous runs of fragments without creating cycles.
  /// ie, if our sorted output units look like:
  ///   {a}, {b}, {c}, {a, b}, {b, c}, {a, b, c},
  /// Assuming singletons have size 3, doubles have size 2, and triples have
  /// size 1, total size would be 14. If we want 3 fragments, we have an ideal
  /// fragment size of 5. Our final partitions would look like:
  ///   {a}, {b}, {c}+{a, b}, {b, c}+{a, b, c}.
  List<PreFragment> mergeFragments(List<PreFragment> preDeferredFragments) {
    var components = separateComponents(preDeferredFragments);
    int desiredNumberOfFragment = _options.mergeFragmentsThreshold;
    int idealFragmentSize = (totalSize / desiredNumberOfFragment).ceil();
    List<_Partition> partitions = [];
    void add(PreFragment next) {
      // Create a new partition if the current one grows too large, otherwise
      // just add to the most recent partition.
      if (partitions.isEmpty ||
          partitions.last.isClosed ||
          partitions.last.size + next.size > idealFragmentSize) {
        partitions.add(_Partition());
      }
      partitions.last.add(next);
    }

    // Greedily group fragments into partitions, but only within each component.
    for (var component in components) {
      component.forEach(add);
      partitions.last.isClosed = true;
    }

    // Reduce fragments by merging fragments with fewer imports into fragments
    // with more imports.
    List<PreFragment> merged = [];
    for (var partition in partitions) {
      merged.add(partition.fragments.reduce((a, b) => b.mergeAfter(a)));
    }
    return merged;
  }

  /// Computes load lists using a list of sorted OutputUnits.
  Map<String, List<OutputUnit>> computeOutputUnitsToLoad(
      List<OutputUnit> outputUnits) {
    // Sort the output units in descending order of the number of imports they
    // include.

    // The loading of the output units must be ordered because a superclass
    // needs to be initialized before its subclass.
    // But a class can only depend on another class in an output unit shared by
    // a strict superset of the imports:
    // By contradiction: Assume a class C in output unit shared by imports in
    // the set S1 = (lib1,.., lib_n) depends on a class D in an output unit
    // shared by S2 such that S2 not a superset of S1. Let lib_s be a library in
    // S1 not in S2. lib_s must depend on C, and then in turn on D. Therefore D
    // is not in the right output unit.
    List<OutputUnit> sortedOutputUnits = outputUnits.reversed.toList();

    Map<String, List<OutputUnit>> outputUnitsToLoad = {};
    for (var import in outputUnitData.deferredImportDescriptions.keys) {
      var loadId = outputUnitData.importDeferName[import];
      List<OutputUnit> loadList = [];
      for (var outputUnit in sortedOutputUnits) {
        assert(!outputUnit.isMainOutput);
        if (outputUnit.imports.contains(import)) {
          loadList.add(outputUnit);
        }
      }
      outputUnitsToLoad[loadId] = loadList;
    }
    return outputUnitsToLoad;
  }

  /// Returns a json-style map for describing what files that are loaded by a
  /// given deferred import.
  /// The mapping is structured as:
  /// library uri -> {"name": library name, "files": (prefix -> list of files)}
  /// Where
  ///
  /// - <library uri> is the import uri of the library making a deferred
  ///   import.
  /// - <library name> is the name of the library, or "<unnamed>" if it is
  ///   unnamed.
  /// - <prefix> is the `as` prefix used for a given deferred import.
  /// - <list of files> is a list of the filenames the must be loaded when that
  ///   import is loaded.
  /// TODO(joshualitt): the library name is unused and should be removed. This
  /// will be a breaking change.
  Map<String, Map<String, dynamic>> computeDeferredMap(
      Map<String, List<FinalizedFragment>> fragmentsToLoad) {
    Map<String, Map<String, dynamic>> mapping = {};

    outputUnitData.deferredImportDescriptions.keys
        .forEach((ImportEntity import) {
      var importDeferName = outputUnitData.importDeferName[import];
      List<FinalizedFragment> fragments = fragmentsToLoad[importDeferName];
      ImportDescription description =
          outputUnitData.deferredImportDescriptions[import];
      String getName(LibraryEntity library) {
        var name = _elementEnvironment.getLibraryName(library);
        return name == '' ? '<unnamed>' : name;
      }

      Map<String, dynamic> libraryMap = mapping.putIfAbsent(
          description.importingUri,
          () => {"name": getName(description.importingLibrary), "imports": {}});

      List<String> partFileNames = fragments
          .map((fragment) =>
              deferredPartFileName(_options, fragment.canonicalOutputUnit.name))
          .toList();
      libraryMap["imports"][importDeferName] = partFileNames;
    });
    return mapping;
  }
}