runtime/observatory/test/dominator_tree_test.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.

import 'package:observatory/dominator_tree.dart';
import 'package:unittest/unittest.dart';

void main() {
  test('small example from [Lenguaer & Tarjan 1979]', smallTest);
  test('non-flowgraph', nonFlowgraph);
}

void smallTest() {
  var g = {
    'R': ['A', 'B', 'C'],
    'A': ['D'],
    'B': ['A', 'D', 'E'],
    'C': ['F', 'G'],
    'D': ['L'],
    'E': ['H'],
    'F': ['I'],
    'G': ['I', 'J'],
    'H': ['E', 'K'],
    'I': ['K'],
    'J': ['I'],
    'K': ['I', 'R'],
    'L': ['H'],
  };
  var d = new Dominator();
  for (String u in g.keys) {
    d.addEdges(u, g[u]);
  }
  d.computeDominatorTree('R');
  expect(d.dominator('I'), equals('R'));
  expect(d.dominator('K'), equals('R'));
  expect(d.dominator('C'), equals('R'));
  expect(d.dominator('H'), equals('R'));
  expect(d.dominator('E'), equals('R'));
  expect(d.dominator('A'), equals('R'));
  expect(d.dominator('D'), equals('R'));
  expect(d.dominator('B'), equals('R'));
  
  expect(d.dominator('F'), equals('C'));
  expect(d.dominator('G'), equals('C'));
  expect(d.dominator('J'), equals('G'));
  expect(d.dominator('L'), equals('D'));
  expect(d.dominator('R'), isNull);
}

void nonFlowgraph() {
  var d = new Dominator();
  d.addEdges('A', ['B']);
  expect(() => d.computeDominatorTree('B'), throwsStateError);
}