pkg/compiler/lib/src/deferred_load/program_split_constraints/builder.dart

// Copyright (c) 2021, 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 'nodes.dart';

import '../../elements/entities.dart';

/// A [Constraint] is a node in a constraint graph which wraps an
/// [ImportEntity].
class Constraint {
  /// The name of the [NamedNode] this [Constraint] was created to
  /// represent.
  final String name;

  /// The [CombinerType] which should be used to combine [imports]. Either
  /// [imports] will be a singleton, or [combinerType] will be non-null.
  final CombinerType combinerType;

  /// The [ImportEntity]s underlying this [Constraint].
  final Set<ImportEntity> imports;

  /// Imports which load after [import].
  final Set<Constraint> successors = {};

  /// Imports which load before [import].
  final Set<Constraint> predecessors = {};

  Constraint(this.name, this.imports, this.combinerType) {
    assert((this.imports.length == 1 && combinerType == null) ||
        (this.imports.length > 1 && combinerType != null));
  }

  @override
  String toString() {
    var predecessorNames =
        predecessors.map((constraint) => constraint.name).join(', ');
    var successorNames =
        successors.map((constraint) => constraint.name).join(', ');
    return 'Constraint(imports=$imports, predecessors={$predecessorNames}, '
        'successors={$successorNames})';
  }
}

/// [_WorkItem] is an private class used to compute the transitive closure of
/// transitions.
class _WorkItem {
  /// The [Constraint] to process.
  final Constraint child;

  /// The set of [ImportEntity]s guaranteed to be loaded after [child]
  /// transitively.
  final Set<ImportEntity> transitiveChildren;

  _WorkItem(this.child, {this.transitiveChildren = const {}});
}

/// [Builder] is converts parsed [Node] objects into transitions which
/// can be applied while splitting a program.
class Builder {
  /// The [ConstraintData] object which result from parsing json constraints.
  final ConstraintData nodes;

  Builder(this.nodes);

  /// Builds a map of transitions which can be applied by an [ImportSetLattice]
  /// when generating [ImportSet]s.
  Map<ImportEntity, Set<ImportEntity>> buildTransitionsMap(
      Iterable<ImportEntity> imports) {
    // 1) Create a map of uri#prefix to [ImportEntity].
    Map<Uri, Map<String, ImportEntity>> importsByUriAndPrefix = {};
    for (var import in imports) {
      var libraryUri = import.enclosingLibraryUri;
      var prefix = import.name;
      var uriNodes = importsByUriAndPrefix[libraryUri] ??= {};
      uriNodes[prefix] = import;
    }

    // A helper function for looking up an [ImportEntity] from a
    // [ReferenceNode].
    ImportEntity _lookupReference(ReferenceNode node) {
      var uri = node.uri;
      if (!importsByUriAndPrefix.containsKey(uri)) {
        throw 'Uri for constraint not found $uri';
      }
      var prefix = node.prefix;
      if (!importsByUriAndPrefix[uri].containsKey(prefix)) {
        throw 'Prefix: $prefix not found for uri: $uri';
      }
      return importsByUriAndPrefix[uri][prefix];
    }

    // 2) Create a [Constraint] for each [NamedNode]. Also,
    // index each [Constraint] by [NamedNode].
    Map<NamedNode, Constraint> nodeToConstraintMap = {};
    for (var constraint in nodes.named) {
      CombinerType combinerType = null;
      Set<ImportEntity> imports = {};
      if (constraint is ReferenceNode) {
        imports.add(_lookupReference(constraint));
      } else if (constraint is CombinerNode) {
        combinerType = constraint.type;
        for (var child in constraint.nodes) {
          imports.add(_lookupReference(child));
        }
      } else {
        throw 'Unexpected Node Type $constraint';
      }

      nodeToConstraintMap[constraint] =
          Constraint(constraint.name, imports, combinerType);
    }

    // 3) Build a graph of [Constraint]s by processing user constraints and
    // intializing each [Constraint]'s predecessor / successor members.
    for (var constraint in nodes.ordered) {
      var successor = nodeToConstraintMap[constraint.successor];
      var predecessor = nodeToConstraintMap[constraint.predecessor];
      successor.predecessors.add(predecessor);
      predecessor.successors.add(successor);
    }

    // 4) Compute the transitive closure of constraints. This gives us a map of
    // transitiveTransitions, where each key is a parent [ImportEntity] and each
    // value represents the transitive set of child [ImportEntity]s which are
    // always loaded after the parent.
    Map<ImportEntity, Set<ImportEntity>> transitiveTransitions = {};
    Queue<_WorkItem> queue = Queue.from(nodeToConstraintMap.values
        .where((node) => node.successors.isEmpty)
        .map((node) => _WorkItem(node)));
    while (queue.isNotEmpty) {
      var item = queue.removeFirst();
      var constraint = item.child;
      var imports = constraint.imports;

      // Update [transitiveTransitions] with reachable transitions for this
      // [_WorkItem]
      var transitiveChildren = item.transitiveChildren;
      for (var import in imports) {
        // We insert an implicit 'self' transition for every import.
        var transitions = transitiveTransitions[import] ??= {import};

        // In the case of [CombinerType.fuse], the nodes in the
        // [Constraint] form a strongly connected component,
        // i.e. [ImportEntity]s that are always part of a
        // single [ImportSet].
        if (constraint.combinerType == CombinerType.fuse) {
          transitions.addAll(imports);
        }
        transitions.addAll(transitiveChildren);
      }

      // Propagate constraints transitively to the parent.
      var predecessorTransitiveChildren = {
        ...imports,
        ...transitiveChildren,
      };
      for (var predecessor in constraint.predecessors) {
        queue.add(_WorkItem(predecessor,
            transitiveChildren: predecessorTransitiveChildren));
      }
    }
    return transitiveTransitions;
  }
}