
1 // 2 // Copyright (c) 2008, John Sublett 3 // Licensed under the Academic Free License version 3.0 4 // 5 // History: 6 // 01 Jan 08 John Sublett Creation 7 // 8 9 ** 10 ** TypeGraph is used to sort a set of types based on 11 ** their dependencies on each other. A set of types 12 ** cannot be sorted if the types have cyclic dependencies. 13 ** 14 class TypeGraph 15 { 16 ** 17 ** Add a type to the graph without specifying a dependency. 18 ** 19 Void addType(Type t) 20 { 21 node(t) 22 } 23 24 ** 25 ** Add a dependency from the 'from' type to the 'to' type. 26 ** 27 Void addDependency(Type from, Type to) 28 { 29 parent := node(to) 30 child := node(from) 31 32 parent.addChild(child); 33 } 34 35 ** 36 ** Get the list of types in the graph sorted by dependency. 37 ** A type will always be later in the list than the types 38 ** it depends on. That is, if type B depends on type A, the 39 ** sorted result will be '[A, B]'. 40 ** 41 Type[] sort() 42 { 43 return rsort.reverse 44 } 45 46 ** 47 ** Get the list of types in the graph sorted in reverse order. 48 ** 49 Type[] rsort() 50 { 51 nodes.each |TypeGraphNode n| { n.nodeState = NodeState.unvisited } 52 53 Type[] rsorted := Type[,] 54 nodes.each |TypeGraphNode n| { n.visit(rsorted) } 55 return rsorted 56 } 57 58 ** 59 ** Get the existing node for the specified 60 ** type or create a new node if one does not 61 ** already exist. 62 ** 63 private TypeGraphNode node(Type nodeType) 64 { 65 n := nodes[nodeType.qname] 66 if (n == null) 67 { 68 n = TypeGraphNode.make(nodeType) 69 nodes[nodeType.qname] = n 70 } 71 return n 72 } 73 74 ** 75 ** The list of nodes in the graph. A node wraps 76 ** a Type and contains a child node for each dependent 77 ** Type. 78 ** 79 private Str:TypeGraphNode nodes := Str:TypeGraphNode[:] 80 } 81 82 ////////////////////////////////////////////////////////////////////////// 83 // TypeGraphNode 84 ////////////////////////////////////////////////////////////////////////// 85 86 internal class TypeGraphNode 87 { 88 new make(Type nodeType) 89 { 90 this.nodeType = nodeType 91 } 92 93 Void visit(Type[] rsorted, TypeGraphNode[] path := TypeGraphNode[,]) 94 { 95 path.add(this) 96 switch (nodeState) 97 { 98 case NodeState.unvisited: 99 nodeState = NodeState.visiting 100 if (!children.isEmpty) 101 children.each |TypeGraphNode child| { child.visit(rsorted, path) } 102 nodeState = NodeState.visited 103 rsorted.add(nodeType) 104 105 case NodeState.visiting: 106 pathStr := path.join(" > ") |TypeGraphNode n->Str| { return n.nodeType.toStr } 107 throw Err.make("Cycle detected: $pathStr") 108 109 case NodeState.visited: 110 return 111 } 112 } 113 114 Void addChild(TypeGraphNode child) 115 { 116 children.add(child) 117 } 118 119 Type nodeType 120 TypeGraphNode[] children := TypeGraphNode[,] 121 NodeState nodeState := NodeState.unvisited 122 } 123 124 ////////////////////////////////////////////////////////////////////////// 125 // NodeState 126 ////////////////////////////////////////////////////////////////////////// 127 128 internal enum NodeState { visited, unvisited, visiting }