Build Observatory with runtime

runtime/bin/vmservice/observatory/lib/dominator_tree.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 dominator_tree;
-
-// Flowgraph dominators in O(m log n) time. Implements the algorithm from
-// [Lengauer & Tarjan 1979]
-// T. Lengauer and R.E. Tarjan,
-// "A fast algorithm for finding dominators in a flowgraph",
-// ACM Transactions on Programming Language and Systems, 1(1):121-141, 1979.
-
-// Internal vertex information used inside 'Dominator'.
-// Field names mostly follow naming in [Lengauer & Tarjan 1979].
-class _Vertex {
-  final Object id;
-  _Vertex dom;
-  _Vertex parent;
-  _Vertex ancestor;
-  _Vertex label;
-  int semi;
-  final List<_Vertex> pred = new List<_Vertex>();
-  final List<_Vertex> bucket = new List<_Vertex>();
-  // TODO(koda): Avoid duplication by having an interface for 'id' with
-  // access to outgoing edges, and/or clearing 'succ' after constructing
-  // inverse graph in 'pred'.
-  final List<_Vertex> succ = new List<_Vertex>();
-  _Vertex(this.id) { label = this; }
-}
-
-// Utility to compute immediate dominators. Usage:
-// 1. Build the flowgraph using 'addEdges'.
-// 2. Call 'computeDominatorTree' once.
-// 3. Use 'dominator' to access result.
-// The instance can only be used once.
-class Dominator {
-  final Map<Object, _Vertex> _idToVertex = new Map<Object, _Vertex>();
-  final List<_Vertex> _vertex = new List<_Vertex>();
-  
-  void addEdges(Object u, Iterable<Object> vs) {
-    _asVertex(u).succ.addAll(vs.map(_asVertex));
-  }
-  
-  // Returns the immediate dominator of 'v', or null if 'v' is the root.
-  Object dominator(Object v) {
-    _Vertex dom = _asVertex(v).dom;
-    return dom == null ? null : dom.id;
-  }
-  
-  _Vertex _asVertex(Object u) {
-    return _idToVertex.putIfAbsent(u, () => new _Vertex(u));
-  }
-  
-  void _dfs(_Vertex v) {
-    v.semi = _vertex.length;
-    _vertex.add(v);
-    for (_Vertex w in v.succ) {
-      if (w.semi == null) {
-        w.parent = v;
-        _dfs(w);
-      }
-      w.pred.add(v);
-    }
-  }
-
-  void _compress(_Vertex v) {
-    if (v.ancestor.ancestor != null) {
-      _compress(v.ancestor);
-      if (v.ancestor.label.semi < v.label.semi) {
-        v.label = v.ancestor.label;
-      }
-      v.ancestor = v.ancestor.ancestor;
-    }
-  }
-
-  _Vertex _eval(_Vertex v) {
-    if (v.ancestor == null) {
-      return v;
-    } else {
-      _compress(v);
-      return v.label;
-    }
-  }
-
-  void _link(_Vertex v, _Vertex w) {
-    w.ancestor = v;
-  }
-  
-  void computeDominatorTree(Object root) {
-    _Vertex r = _asVertex(root);
-    int n = _idToVertex.length;
-    _dfs(r);
-    if (_vertex.length != n) {
-      throw new StateError("Not a flowgraph: "
-          "only ${_vertex.length} of $n vertices reachable");
-    }
-    for (int i = n - 1; i >= 1; --i) {
-      _Vertex w = _vertex[i];
-      for (_Vertex v in w.pred) {
-        _Vertex u = _eval(v);
-        if (u.semi < w.semi) {
-          w.semi = u.semi;
-        }
-      }
-      _vertex[w.semi].bucket.add(w);
-      _link(w.parent, w);
-      for (_Vertex v in w.parent.bucket) {
-        _Vertex u = _eval(v);
-        v.dom = u.semi < v.semi ? u : w.parent;
-      }
-      w.parent.bucket.clear();
-    }
-    for (int i = 1; i < n; ++i) {
-      _Vertex w = _vertex[i];
-      if (w.dom != _vertex[w.semi]) {
-        w.dom = w.dom.dom;
-      }
-    }
-    r.dom = null;
-  }
-}