pkg/compiler/lib/src/deferred_load/import_set.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 'output_unit.dart';

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

/// Indirectly represents a deferred import in an [ImportSet].
///
/// We could directly store the [declaration] in [ImportSet], but adding this
/// class makes some of the import set operations more efficient.
class _DeferredImport {
  final ImportEntity declaration;

  /// Canonical index associated with [declaration]. This is used to efficiently
  /// implement [ImportSetLattice.union].
  final int index;

  _DeferredImport(this.declaration, this.index);
}

/// A compact lattice representation of import sets and subsets.
///
/// We use a graph of nodes to represent elements of the lattice, but only
/// create new nodes on-demand as they are needed by the deferred loading
/// algorithm.
///
/// The constructions of nodes is carefully done by storing imports in a
/// specific order. This ensures that we have a unique and canonical
/// representation for each subset.
class ImportSetLattice {
  /// Index of deferred imports that defines the canonical order used by the
  /// operations below.
  Map<ImportEntity, _DeferredImport> _importIndex = {};

  /// The canonical instance representing the empty import set.
  ImportSet _emptySet = ImportSet.empty();

  /// The import set representing the main output unit, which happens to be
  /// implemented as an empty set in our algorithm.
  ImportSet get mainSet => _emptySet;

  /// Get the singleton import set that only contains [import].
  ImportSet singleton(ImportEntity import) {
    // Ensure we have import in the index.
    return _emptySet._add(_wrap(import));
  }

  /// Get the import set that includes the union of [a] and [b].
  ImportSet union(ImportSet a, ImportSet b) {
    if (a == null || a.isEmpty) return b;
    if (b == null || b.isEmpty) return a;

    // Create the union by merging the imports in canonical order. The sets are
    // basically lists linked by the `_previous` field in reverse order. We do a
    // merge-like scan 'backwards' removing the biggest element until we hit an
    // empty set or a common prefix, and the add the 'merge-sorted' elements
    // back onto the prefix.
    ImportSet result;
    // 'removed' imports in decreasing canonical order.
    List<_DeferredImport> imports = [];

    while (true) {
      if (a.isEmpty) {
        result = b;
        break;
      }
      if (b.isEmpty || identical(a, b)) {
        result = a;
        break;
      }
      if (a._import.index > b._import.index) {
        imports.add(a._import);
        a = a._previous;
      } else if (b._import.index > a._import.index) {
        imports.add(b._import);
        b = b._previous;
      } else {
        assert(identical(a._import, b._import));
        imports.add(a._import);
        a = a._previous;
        b = b._previous;
      }
    }

    // Add merged elements back in reverse order. It is tempting to pop them off
    // with `removeLast()` but that causes measurable shrinking reallocations.
    for (int i = imports.length - 1; i >= 0; i--) {
      result = result._add(imports[i]);
    }
    return result;
  }

  /// Get the index for an [import] according to the canonical order.
  _DeferredImport _wrap(ImportEntity import) {
    return _importIndex[import] ??=
        _DeferredImport(import, _importIndex.length);
  }
}

/// A canonical set of deferred imports.
class ImportSet {
  /// Last element added to set.
  ///
  /// This set comprises [_import] appended onto [_previous]. *Note*: [_import]
  /// is the last element in the set in the canonical order imposed by
  /// [ImportSetLattice].
  final _DeferredImport _import; // `null` for empty ImportSet
  /// The set containing all previous elements.
  final ImportSet _previous;
  final int length;

  bool get isEmpty => _import == null;
  bool get isNotEmpty => _import != null;

  /// Returns an iterable over the imports in this set in canonical order.
  Iterable<_DeferredImport> collectImports() {
    List<_DeferredImport> result = [];
    ImportSet current = this;
    while (current.isNotEmpty) {
      result.add(current._import);
      current = current._previous;
    }
    assert(result.length == this.length);
    return result.reversed;
  }

  /// Links to other import sets in the lattice by adding one import.
  final Map<_DeferredImport, ImportSet> _transitions = Maplet();

  ImportSet.empty()
      : _import = null,
        _previous = null,
        length = 0;

  ImportSet(this._import, this._previous, this.length);

  /// The output unit corresponding to this set of imports, if any.
  OutputUnit unit;

  /// Create an import set that adds [import] to all the imports on this set.
  /// This assumes that import's canonical order comes after all imports in
  /// this current set. This should only be called from [ImportSetLattice],
  /// since it is where we preserve this invariant.
  ImportSet _add(_DeferredImport import) {
    assert(_import == null || import.index > _import.index);
    return _transitions[import] ??= ImportSet(import, this, length + 1);
  }

  @override
  String toString() {
    StringBuffer sb = StringBuffer();
    sb.write('ImportSet(size: $length, ');
    for (var import in collectImports()) {
      sb.write('${import.declaration.name} ');
    }
    sb.write(')');
    return '$sb';
  }
}