| Index: pkg/servicec/lib/cycle_detection.dart
|
| diff --git a/pkg/servicec/lib/cycle_detection.dart b/pkg/servicec/lib/cycle_detection.dart
|
| deleted file mode 100644
|
| index ca2e9b164e9cd710164e8cf893409d35f6e2ac02..0000000000000000000000000000000000000000
|
| --- a/pkg/servicec/lib/cycle_detection.dart
|
| +++ /dev/null
|
| @@ -1,142 +0,0 @@
|
| -// Copyright (c) 2015, the Dartino 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 servicec.cycle_detection;
|
| -
|
| -import 'dart:collection' show
|
| - LinkedHashSet;
|
| -
|
| -import 'node.dart' show
|
| - MemberNode,
|
| - FieldNode,
|
| - SimpleType,
|
| - StructNode,
|
| - TypeNode,
|
| - UnionNode;
|
| -
|
| -import 'errors.dart' show
|
| - CompilationError,
|
| - CyclicStructError,
|
| - ErrorTag;
|
| -
|
| -class GraphNode {
|
| - GraphNodeState state = GraphNodeState.UNVISITED;
|
| - StructNode struct;
|
| -
|
| - GraphNode(this.struct);
|
| -
|
| - bool get isNotVisited => GraphNodeState.UNVISITED == state;
|
| -
|
| - bool operator ==(GraphNode other) {
|
| - return struct == other.struct;
|
| - }
|
| - int get hashCode => struct.hashCode;
|
| -
|
| - String toString() => "Node[${struct.identifier.value}, ${state.toString()}]";
|
| -}
|
| -
|
| -enum GraphNodeState {
|
| - VISITED,
|
| - VISITING,
|
| - UNVISITED
|
| -}
|
| -
|
| -class StructGraph {
|
| - Set<GraphNode> nodes;
|
| - Map<GraphNode, Set<GraphNode>> neighbours;
|
| -
|
| - StructGraph()
|
| - : nodes = new LinkedHashSet<GraphNode>(), // Maintain node order.
|
| - neighbours = new Map<GraphNode, Set<GraphNode>>();
|
| -
|
| - void add(StructNode struct) {
|
| - for (MemberNode member in struct.members) {
|
| - if (member is FieldNode) {
|
| - addStructField(struct, member);
|
| - } else {
|
| - UnionNode union = member;
|
| - union.fields.forEach((field) => addStructField(struct, field));
|
| - }
|
| - }
|
| - }
|
| -
|
| - // Helper function.
|
| - void addStructField(StructNode struct, FieldNode field) {
|
| - TypeNode type = field.type;
|
| - if (type != null && type.isStruct()) {
|
| - SimpleType simpleType = type;
|
| - addLink(struct, simpleType.resolved);
|
| - }
|
| - }
|
| -
|
| - void addLink(StructNode from, StructNode to) {
|
| - GraphNode fromNode = addNodeIfNew(from);
|
| - GraphNode toNode = addNodeIfNew(to);
|
| - neighbours[fromNode].add(toNode);
|
| - }
|
| -
|
| - GraphNode addNodeIfNew(StructNode node) {
|
| - GraphNode result = nodes.firstWhere(
|
| - (graphNode) => graphNode.struct == node,
|
| - orElse: () => null);
|
| - if (null == result) {
|
| - result = new GraphNode(node);
|
| - nodes.add(result);
|
| - neighbours[result] = new Set<GraphNode>();
|
| - }
|
| - return result;
|
| - }
|
| -
|
| - List<CompilationError> findCycles() {
|
| - List<CompilationError> errors = <CompilationError>[];
|
| - List<GraphNode> stack = new List<GraphNode>();
|
| - stack.addAll(nodes.toList().reversed.toList());
|
| - while (stack.isNotEmpty) {
|
| - GraphNode node = stack.last;
|
| - switch (node.state) {
|
| - case GraphNodeState.UNVISITED:
|
| - node.state = GraphNodeState.VISITING;
|
| - for (GraphNode neighbour in neighbours[node]) {
|
| - switch (neighbour.state) {
|
| - case GraphNodeState.UNVISITED:
|
| - // The `neighbour` hasn't been seen yet - add to stack.
|
| - stack.add(neighbour);
|
| - break;
|
| - case GraphNodeState.VISITING:
|
| - // The `neighbour` is in the current route from the root to the
|
| - // `node` - there is a cycle.
|
| - errors.add(createError(neighbour.struct, stack));
|
| - break;
|
| - case GraphNodeState.VISITED:
|
| - // The `neighbour` has already been searched - ignore.
|
| - break;
|
| - }
|
| - }
|
| - break;
|
| - case GraphNodeState.VISITING:
|
| - node.state = GraphNodeState.VISITED;
|
| - stack.removeLast();
|
| - break;
|
| - case GraphNodeState.VISITED:
|
| - // In this case the graph is a DAG.
|
| - stack.removeLast();
|
| - break;
|
| - }
|
| - }
|
| - return errors;
|
| - }
|
| -
|
| - CyclicStructError createError(StructNode struct, List<GraphNode> stack) {
|
| - LinkedHashSet<StructNode> reversedChain = new LinkedHashSet<StructNode>();
|
| - reversedChain.add(struct);
|
| - for (int i = stack.length - 1; i >= 0; --i) {
|
| - if (stack[i].state == GraphNodeState.VISITING) {
|
| - reversedChain.add(stack[i].struct);
|
| - }
|
| - if (stack[i].struct == struct) break;
|
| - }
|
| -
|
| - return new CyclicStructError(reversedChain.toList().reversed);
|
| - }
|
| -}
|
|
|