pkg/analyzer/lib/src/generated/utilities_collection.dart

// 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.

library analyzer.src.generated.utilities_collection;

import 'dart:collection';
import "dart:math" as math;

import 'package:analyzer/dart/ast/token.dart';
import 'package:analyzer/src/generated/java_core.dart';

/**
 * Returns `true` if a and b contain equal elements in the same order.
 */
bool listsEqual(List a, List b) {
  // TODO(rnystrom): package:collection also implements this, and analyzer
  // already transitively depends on that package. Consider using it instead.
  if (identical(a, b)) {
    return true;
  }

  if (a.length != b.length) {
    return false;
  }

  for (int i = 0; i < a.length; i++) {
    if (a[i] != b[i]) {
      return false;
    }
  }

  return true;
}

/**
 * Methods for operating on integers as if they were arrays of booleans. These
 * arrays can be indexed by either integers or by enumeration constants.
 */
class BooleanArray {
  /**
   * Return the value of the element of the given [array] at the given [index].
   */
  static bool get(int array, int index) {
    _checkIndex(index);
    return (array & (1 << index)) > 0;
  }

  /**
   * Return the value of the element at the given index.
   */
  @deprecated
  static bool getEnum<E extends Enum<E>>(int array, Enum<E> index) =>
      get(array, index.ordinal);

  /**
   * Set the value of the element of the given [array] at the given [index] to
   * the given [value].
   */
  static int set(int array, int index, bool value) {
    _checkIndex(index);
    if (value) {
      return array | (1 << index);
    } else {
      return array & ~(1 << index);
    }
  }

  /**
   * Set the value of the element at the given index to the given value.
   */
  @deprecated
  static int setEnum<E extends Enum<E>>(int array, Enum<E> index, bool value) =>
      set(array, index.ordinal, value);

  /**
   * Throw an exception if the index is not within the bounds allowed for an
   * integer-encoded array of boolean values.
   */
  static void _checkIndex(int index) {
    if (index < 0 || index > 30) {
      throw new RangeError("Index not between 0 and 30: $index");
    }
  }
}

/**
 * Instances of the class `DirectedGraph` implement a directed graph in which the nodes are
 * arbitrary (client provided) objects and edges are represented implicitly. The graph will allow an
 * edge from any node to any other node, including itself, but will not represent multiple edges
 * between the same pair of nodes.
 *
 * @param N the type of the nodes in the graph
 */
class DirectedGraph<N> {
  /**
   * The table encoding the edges in the graph. An edge is represented by an entry mapping the head
   * to a set of tails. Nodes that are not the head of any edge are represented by an entry mapping
   * the node to an empty set of tails.
   */
  Map<N, HashSet<N>> _edges = new HashMap<N, HashSet<N>>();

  /**
   * Return `true` if this graph is empty.
   *
   * @return `true` if this graph is empty
   */
  bool get isEmpty => _edges.isEmpty;

  /**
   * Return the number of nodes in this graph.
   *
   * @return the number of nodes in this graph
   */
  int get nodeCount => _edges.length;

  /**
   * Return a set of all nodes in the graph.
   */
  Set<N> get nodes => _edges.keys.toSet();

  /**
   * Add an edge from the given head node to the given tail node. Both nodes will be a part of the
   * graph after this method is invoked, whether or not they were before.
   *
   * @param head the node at the head of the edge
   * @param tail the node at the tail of the edge
   */
  void addEdge(N head, N tail) {
    //
    // First, ensure that the tail is a node known to the graph.
    //
    if (_edges[tail] == null) {
      _edges[tail] = new HashSet<N>();
    }
    //
    // Then create the edge.
    //
    HashSet<N> tails = _edges[head];
    if (tails == null) {
      tails = new HashSet<N>();
      _edges[head] = tails;
    }
    tails.add(tail);
  }

  /**
   * Add the given node to the set of nodes in the graph.
   *
   * @param node the node to be added
   */
  void addNode(N node) {
    HashSet<N> tails = _edges[node];
    if (tails == null) {
      _edges[node] = new HashSet<N>();
    }
  }

  /**
   * Run a topological sort of the graph. Since the graph may contain cycles, this results in a list
   * of strongly connected components rather than a list of nodes. The nodes in each strongly
   * connected components only have edges that point to nodes in the same component or earlier
   * components.
   */
  List<List<N>> computeTopologicalSort() {
    DirectedGraph_SccFinder<N> finder = new DirectedGraph_SccFinder<N>(this);
    return finder.computeTopologicalSort();
  }

  /**
   * Return true if the graph contains at least one path from `source` to `destination`.
   */
  bool containsPath(N source, N destination) {
    HashSet<N> nodesVisited = new HashSet<N>();
    return _containsPathInternal(source, destination, nodesVisited);
  }

  /**
   * Return a list of nodes that form a cycle containing the given node. If the node is not part of
   * this graph, then a list containing only the node itself will be returned.
   *
   * @return a list of nodes that form a cycle containing the given node
   */
  List<N> findCycleContaining(N node) {
    if (node == null) {
      throw new ArgumentError();
    }
    DirectedGraph_SccFinder<N> finder = new DirectedGraph_SccFinder<N>(this);
    return finder.componentContaining(node);
  }

  /**
   * Return a set containing the tails of edges that have the given node as their head. The set will
   * be empty if there are no such edges or if the node is not part of the graph. Clients must not
   * modify the returned set.
   *
   * @param head the node at the head of all of the edges whose tails are to be returned
   * @return a set containing the tails of edges that have the given node as their head
   */
  Set<N> getTails(N head) {
    HashSet<N> tails = _edges[head];
    if (tails == null) {
      return new HashSet<N>();
    }
    return tails;
  }

  /**
   * Remove all of the given nodes from this graph. As a consequence, any edges for which those
   * nodes were either a head or a tail will also be removed.
   *
   * @param nodes the nodes to be removed
   */
  void removeAllNodes(List<N> nodes) {
    for (N node in nodes) {
      removeNode(node);
    }
  }

  /**
   * Remove the edge from the given head node to the given tail node. If there was no such edge then
   * the graph will be unmodified: the number of edges will be the same and the set of nodes will be
   * the same (neither node will either be added or removed).
   *
   * @param head the node at the head of the edge
   * @param tail the node at the tail of the edge
   * @return `true` if the graph was modified as a result of this operation
   */
  void removeEdge(N head, N tail) {
    HashSet<N> tails = _edges[head];
    if (tails != null) {
      tails.remove(tail);
    }
  }

  /**
   * Remove the given node from this graph. As a consequence, any edges for which that node was
   * either a head or a tail will also be removed.
   *
   * @param node the node to be removed
   */
  void removeNode(N node) {
    _edges.remove(node);
    for (HashSet<N> tails in _edges.values) {
      tails.remove(node);
    }
  }

  /**
   * Find one node (referred to as a sink node) that has no outgoing edges (that is, for which there
   * are no edges that have that node as the head of the edge) and remove it from this graph. Return
   * the node that was removed, or `null` if there are no such nodes either because the graph
   * is empty or because every node in the graph has at least one outgoing edge. As a consequence of
   * removing the node from the graph any edges for which that node was a tail will also be removed.
   *
   * @return the sink node that was removed
   */
  N removeSink() {
    N sink = _findSink();
    if (sink == null) {
      return null;
    }
    removeNode(sink);
    return sink;
  }

  bool _containsPathInternal(N source, N destination, HashSet<N> nodesVisited) {
    if (identical(source, destination)) {
      return true;
    }
    HashSet<N> tails = _edges[source];
    if (tails != null) {
      nodesVisited.add(source);
      for (N tail in tails) {
        if (!nodesVisited.contains(tail)) {
          if (_containsPathInternal(tail, destination, nodesVisited)) {
            return true;
          }
        }
      }
    }
    return false;
  }

  /**
   * Return one node that has no outgoing edges (that is, for which there are no edges that have
   * that node as the head of the edge), or `null` if there are no such nodes.
   *
   * @return a sink node
   */
  N _findSink() {
    for (N key in _edges.keys) {
      if (_edges[key].isEmpty) return key;
    }
    return null;
  }
}

/**
 * Instances of the class `NodeInfo` are used by the [SccFinder] to maintain
 * information about the nodes that have been examined.
 *
 * @param N the type of the nodes corresponding to the entries
 */
class DirectedGraph_NodeInfo<N> {
  /**
   * The depth of this node.
   */
  int index = 0;

  /**
   * The depth of the first node in a cycle.
   */
  int lowlink = 0;

  /**
   * A flag indicating whether the corresponding node is on the stack. Used to remove the need for
   * searching a collection for the node each time the question needs to be asked.
   */
  bool onStack = false;

  /**
   * The component that contains the corresponding node.
   */
  List<N> component;

  /**
   * Initialize a newly created information holder to represent a node at the given depth.
   *
   * @param depth the depth of the node being represented
   */
  DirectedGraph_NodeInfo(int depth) {
    index = depth;
    lowlink = depth;
    onStack = false;
  }
}

/**
 * Instances of the class `SccFinder` implement Tarjan's Algorithm for finding the strongly
 * connected components in a graph.
 */
class DirectedGraph_SccFinder<N> {
  /**
   * The graph to work with.
   */
  final DirectedGraph<N> _graph;

  /**
   * The index used to uniquely identify the depth of nodes.
   */
  int _index = 0;

  /**
   * The stack of nodes that are being visited in order to identify components.
   */
  List<N> _stack = new List<N>();

  /**
   * A table mapping nodes to information about the nodes that is used by this algorithm.
   */
  Map<N, DirectedGraph_NodeInfo<N>> _nodeMap =
      new HashMap<N, DirectedGraph_NodeInfo<N>>();

  /**
   * A list of all strongly connected components found, in topological sort order (each node in a
   * strongly connected component only has edges that point to nodes in the same component or
   * earlier components).
   */
  List<List<N>> _allComponents = new List<List<N>>();

  /**
   * Initialize a newly created finder.
   */
  DirectedGraph_SccFinder(this._graph) : super();

  /**
   * Return a list containing the nodes that are part of the strongly connected component that
   * contains the given node.
   *
   * @param node the node used to identify the strongly connected component to be returned
   * @return the nodes that are part of the strongly connected component that contains the given
   *         node
   */
  List<N> componentContaining(N node) => _strongConnect(node).component;

  /**
   * Run Tarjan's algorithm and return the resulting list of strongly connected components. The
   * list is in topological sort order (each node in a strongly connected component only has edges
   * that point to nodes in the same component or earlier components).
   */
  List<List<N>> computeTopologicalSort() {
    for (N node in _graph._edges.keys.toSet()) {
      DirectedGraph_NodeInfo<N> nodeInfo = _nodeMap[node];
      if (nodeInfo == null) {
        _strongConnect(node);
      }
    }
    return _allComponents;
  }

  /**
   * Remove and return the top-most element from the stack.
   *
   * @return the element that was removed
   */
  N _pop() {
    N node = _stack.removeAt(_stack.length - 1);
    _nodeMap[node].onStack = false;
    return node;
  }

  /**
   * Add the given node to the stack.
   *
   * @param node the node to be added to the stack
   */
  void _push(N node) {
    _nodeMap[node].onStack = true;
    _stack.add(node);
  }

  /**
   * Compute the strongly connected component that contains the given node as well as any
   * components containing nodes that are reachable from the given component.
   *
   * @param v the node from which the search will begin
   * @return the information about the given node
   */
  DirectedGraph_NodeInfo<N> _strongConnect(N v) {
    //
    // Set the depth index for v to the smallest unused index
    //
    DirectedGraph_NodeInfo<N> vInfo = new DirectedGraph_NodeInfo<N>(_index++);
    _nodeMap[v] = vInfo;
    _push(v);
    //
    // Consider successors of v
    //
    HashSet<N> tails = _graph._edges[v];
    if (tails != null) {
      for (N w in tails) {
        DirectedGraph_NodeInfo<N> wInfo = _nodeMap[w];
        if (wInfo == null) {
          // Successor w has not yet been visited; recurse on it
          wInfo = _strongConnect(w);
          vInfo.lowlink = math.min(vInfo.lowlink, wInfo.lowlink);
        } else if (wInfo.onStack) {
          // Successor w is in stack S and hence in the current SCC
          vInfo.lowlink = math.min(vInfo.lowlink, wInfo.index);
        }
      }
    }
    //
    // If v is a root node, pop the stack and generate an SCC
    //
    if (vInfo.lowlink == vInfo.index) {
      List<N> component = new List<N>();
      N w;
      do {
        w = _pop();
        component.add(w);
        _nodeMap[w].component = component;
      } while (!identical(w, v));
      _allComponents.add(component);
    }
    return vInfo;
  }
}

/**
 * The interface `MapIterator` defines the behavior of objects that iterate over the entries
 * in a map.
 *
 * This interface defines the concept of a current entry and provides methods to access the key and
 * value in the current entry. When an iterator is first created it will be positioned before the
 * first entry and there is no current entry until [moveNext] is invoked. When all of the
 * entries have been accessed there will also be no current entry.
 *
 * There is no guarantee made about the order in which the entries are accessible.
 */
abstract class MapIterator<K, V> {
  /**
   * Return the key associated with the current element.
   *
   * @return the key associated with the current element
   * @throws NoSuchElementException if there is no current element
   */
  K get key;

  /**
   * Return the value associated with the current element.
   *
   * @return the value associated with the current element
   * @throws NoSuchElementException if there is no current element
   */
  V get value;

  /**
   * Set the value associated with the current element to the given value.
   *
   * @param newValue the new value to be associated with the current element
   * @throws NoSuchElementException if there is no current element
   */
  void set value(V newValue);

  /**
   * Advance to the next entry in the map. Return `true` if there is a current element that
   * can be accessed after this method returns. It is safe to invoke this method even if the
   * previous invocation returned `false`.
   *
   * @return `true` if there is a current element that can be accessed
   */
  bool moveNext();
}

/**
 * Instances of the class `MultipleMapIterator` implement an iterator that can be used to
 * sequentially access the entries in multiple maps.
 */
class MultipleMapIterator<K, V> implements MapIterator<K, V> {
  /**
   * The iterators used to access the entries.
   */
  List<MapIterator<K, V>> _iterators;

  /**
   * The index of the iterator currently being used to access the entries.
   */
  int _iteratorIndex = -1;

  /**
   * The current iterator, or `null` if there is no current iterator.
   */
  MapIterator<K, V> _currentIterator;

  /**
   * Initialize a newly created iterator to return the entries from the given maps.
   *
   * @param maps the maps containing the entries to be iterated
   */
  MultipleMapIterator(List<Map<K, V>> maps) {
    int count = maps.length;
    _iterators = new List<MapIterator<K, V>>(count);
    for (int i = 0; i < count; i++) {
      _iterators[i] = new SingleMapIterator<K, V>(maps[i]);
    }
  }

  @override
  K get key {
    if (_currentIterator == null) {
      throw new StateError('No element');
    }
    return _currentIterator.key;
  }

  @override
  V get value {
    if (_currentIterator == null) {
      throw new StateError('No element');
    }
    return _currentIterator.value;
  }

  @override
  void set value(V newValue) {
    if (_currentIterator == null) {
      throw new StateError('No element');
    }
    _currentIterator.value = newValue;
  }

  @override
  bool moveNext() {
    if (_iteratorIndex < 0) {
      if (_iterators.length == 0) {
        _currentIterator = null;
        return false;
      }
      if (_advanceToNextIterator()) {
        return true;
      } else {
        _currentIterator = null;
        return false;
      }
    }
    if (_currentIterator.moveNext()) {
      return true;
    } else if (_advanceToNextIterator()) {
      return true;
    } else {
      _currentIterator = null;
      return false;
    }
  }

  /**
   * Under the assumption that there are no more entries that can be returned using the current
   * iterator, advance to the next iterator that has entries.
   *
   * @return `true` if there is a current iterator that has entries
   */
  bool _advanceToNextIterator() {
    _iteratorIndex++;
    while (_iteratorIndex < _iterators.length) {
      MapIterator<K, V> iterator = _iterators[_iteratorIndex];
      if (iterator.moveNext()) {
        _currentIterator = iterator;
        return true;
      }
      _iteratorIndex++;
    }
    return false;
  }
}

/**
 * Instances of the class `SingleMapIterator` implement an iterator that can be used to access
 * the entries in a single map.
 */
class SingleMapIterator<K, V> implements MapIterator<K, V> {
  /**
   * The [Map] containing the entries to be iterated over.
   */
  final Map<K, V> _map;

  /**
   * The iterator used to access the entries.
   */
  Iterator<K> _keyIterator;

  /**
   * The current key, or `null` if there is no current key.
   */
  K _currentKey;

  /**
   * The current value.
   */
  V _currentValue;

  /**
   * Initialize a newly created iterator to return the entries from the given map.
   *
   * @param map the map containing the entries to be iterated over
   */
  SingleMapIterator(this._map) {
    this._keyIterator = _map.keys.iterator;
  }

  @override
  K get key {
    if (_currentKey == null) {
      throw new StateError('No element');
    }
    return _currentKey;
  }

  @override
  V get value {
    if (_currentKey == null) {
      throw new StateError('No element');
    }
    if (_currentValue == null) {
      _currentValue = _map[_currentKey];
    }
    return _currentValue;
  }

  @override
  void set value(V newValue) {
    if (_currentKey == null) {
      throw new StateError('No element');
    }
    _currentValue = newValue;
    _map[_currentKey] = newValue;
  }

  @override
  bool moveNext() {
    if (_keyIterator.moveNext()) {
      _currentKey = _keyIterator.current;
      _currentValue = null;
      return true;
    } else {
      _currentKey = null;
      return false;
    }
  }

  /**
   * Returns a new [SingleMapIterator] instance for the given [Map].
   */
  static SingleMapIterator forMap(Map map) => new SingleMapIterator(map);
}

/**
 * Instances of the class `TokenMap` map one set of tokens to another set of tokens.
 */
class TokenMap {
  /**
   * A table mapping tokens to tokens. This should be replaced by a more performant implementation.
   * One possibility is a pair of parallel arrays, with keys being sorted by their offset and a
   * cursor indicating where to start searching.
   */
  Map<Token, Token> _map = new HashMap<Token, Token>();

  /**
   * Return the token that is mapped to the given token, or `null` if there is no token
   * corresponding to the given token.
   *
   * @param key the token being mapped to another token
   * @return the token that is mapped to the given token
   */
  Token get(Token key) => _map[key];

  /**
   * Map the key to the value.
   *
   * @param key the token being mapped to the value
   * @param value the token to which the key will be mapped
   */
  void put(Token key, Token value) {
    _map[key] = value;
  }
}