type_dependency_graph.go
1 package x64dbg 2 3 import ( 4 "fmt" 5 "slices" 6 "sort" 7 ) 8 9 type type_dependency_graph struct { 10 all_types map[string]*type_graph_node 11 } 12 13 func (graph *type_dependency_graph) get(name string) *type_graph_node { 14 return graph.all_types[name] 15 } 16 17 func new_type_dependency_graph() *type_dependency_graph { 18 t := new(type_dependency_graph) 19 t.all_types = make(map[string]*type_graph_node) 20 return t 21 } 22 23 func new_type_graph_node() *type_graph_node { 24 t := new(type_graph_node) 25 return t 26 } 27 28 func (graph *type_dependency_graph) get_node_dependencies(t *type_graph_node) (nodes []*type_graph_node, err error) { 29 nodes = t.depends_on 30 return 31 } 32 33 func (graph *type_dependency_graph) check_sub_dependency_cycle(root_node, sub_node *type_graph_node) (err error) { 34 var sub_node_deps []*type_graph_node 35 sub_node_deps, err = graph.get_node_dependencies(sub_node) 36 for _, dependency_node := range sub_node_deps { 37 if dependency_node == root_node { 38 return fmt.Errorf("cycle detected with %s", root_node.t.GetName()) 39 } 40 41 // recursively check for deeper dependency cycles 42 if err = graph.check_sub_dependency_cycle(root_node, dependency_node); err != nil { 43 return 44 } 45 } 46 47 return 48 } 49 50 func (graph *type_dependency_graph) check_root_dependency_cycle(node *type_graph_node) (err error) { 51 var node_deps []*type_graph_node 52 node_deps, err = graph.get_node_dependencies(node) 53 for _, dependency_node := range node_deps { 54 // check for obvious self-referential 55 if dependency_node == node { 56 return fmt.Errorf("immediate %s->%s self-reference", node.t.GetName(), node.t.GetName()) 57 } 58 59 // recursively check for deeper dependency cycles 60 if err = graph.check_sub_dependency_cycle(node, dependency_node); err != nil { 61 return 62 } 63 } 64 65 return 66 } 67 68 func (graph *type_dependency_graph) remove_edge(dependency, dependent *type_graph_node) (err error) { 69 dependent_index := slices.Index(dependent.depends_on, dependency) 70 if dependent_index == -1 { 71 err = fmt.Errorf("dependency %s not found in dependent %s", dependency.t.GetName(), dependent.t.GetName()) 72 return 73 } 74 75 dependency_index := slices.Index(dependency.is_depended_on_by, dependent) 76 77 if dependency_index == -1 { 78 err = fmt.Errorf("dependent %s not found in dependency %s", dependent.t.GetName(), dependency.t.GetName()) 79 return 80 } 81 82 dependent.depends_on = slices.Delete(dependent.depends_on, dependent_index, dependent_index+1) 83 dependency.is_depended_on_by = slices.Delete(dependency.is_depended_on_by, dependency_index, dependency_index+1) 84 85 return nil 86 } 87 88 func (graph *type_dependency_graph) Load(types *Types) (err error) { 89 // combine all types into an array 90 var all_types []*type_graph_node 91 92 type_exists := map[string]bool{} 93 94 for _, alias_type := range types.Types { 95 t := new_type_graph_node() 96 at := alias_type 97 t.t = &at 98 99 if !type_exists[t.String()] { 100 type_exists[t.String()] = true 101 all_types = append(all_types, t) 102 } 103 } 104 105 for _, struct_type := range types.Structs { 106 t := new_type_graph_node() 107 st := struct_type 108 t.t = &st 109 110 if !type_exists[t.String()] { 111 type_exists[t.String()] = true 112 all_types = append(all_types, t) 113 } 114 } 115 116 for _, union_type := range types.Unions { 117 t := new_type_graph_node() 118 ut := union_type 119 t.t = &ut 120 121 if !type_exists[t.String()] { 122 type_exists[t.String()] = true 123 all_types = append(all_types, t) 124 } 125 } 126 127 for _, func_type := range types.Functions { 128 t := new_type_graph_node() 129 ft := func_type 130 t.t = &ft 131 132 if !type_exists[t.String()] { 133 type_exists[t.String()] = true 134 all_types = append(all_types, t) 135 } 136 } 137 138 // load types into map 139 graph.all_types = make(map[string]*type_graph_node) 140 for _, t := range all_types { 141 graph.all_types[t.t.GetName()] = t 142 } 143 144 // build graph 145 for _, t := range all_types { 146 for _, dependency_name := range t.t.Dependencies() { 147 if is_type_name_builtin(dependency_name) { 148 continue 149 } 150 151 dependency_type := graph.get(dependency_name) 152 if dependency_type == nil { 153 err = fmt.Errorf("unknown dependency name '%s' from type '%s'", dependency_name, t.t.GetName()) 154 return 155 } 156 157 if !slices.Contains(t.depends_on, dependency_type) { 158 t.depends_on = append(t.depends_on, dependency_type) 159 } 160 161 if !slices.Contains(dependency_type.is_depended_on_by, t) { 162 dependency_type.is_depended_on_by = append(dependency_type.is_depended_on_by, t) 163 } 164 } 165 } 166 167 // check for cycles 168 for _, t := range all_types { 169 if err = graph.check_root_dependency_cycle(t); err != nil { 170 return 171 } 172 } 173 174 return 175 } 176 177 type type_dependency_sorter struct { 178 graph *type_dependency_graph 179 type_names []string 180 } 181 182 func new_type_dependency_sorter(graph *type_dependency_graph) *type_dependency_sorter { 183 sorter := new(type_dependency_sorter) 184 sorter.graph = graph 185 for k := range sorter.graph.all_types { 186 sorter.type_names = append(sorter.type_names, k) 187 } 188 sort.Strings(sorter.type_names) 189 return sorter 190 } 191 192 func (sorter *type_dependency_sorter) sort() (sorted []*type_graph_node, err error) { 193 // first, peel off types with no dependencies. 194 var s []*type_graph_node 195 var l []*type_graph_node 196 197 for _, type_name := range sorter.type_names { 198 node := sorter.graph.all_types[type_name] 199 // 200 if len(node.depends_on) == 0 { 201 s = append(s, node) 202 } 203 } 204 205 for len(s) != 0 { 206 n := s[0] 207 s = s[1:] 208 209 l = append(l, n) 210 211 n_dependents := make([]*type_graph_node, len(n.is_depended_on_by)) 212 copy(n_dependents, n.is_depended_on_by) 213 for i := range n_dependents { 214 m := n_dependents[i] 215 216 if err = sorter.graph.remove_edge(n, m); err != nil { 217 return 218 } 219 220 if len(m.depends_on) == 0 { 221 s = append(s, m) 222 } 223 } 224 } 225 226 sorted = l 227 return 228 } 229 230 func (graph *type_dependency_graph) Save() (types *Types, err error) { 231 sorter := new_type_dependency_sorter(graph) 232 233 var sorted []*type_graph_node 234 sorted, err = sorter.sort() 235 if err != nil { 236 return 237 } 238 types = new(Types) 239 240 for _, t := range sorted { 241 switch xt := t.t.(type) { 242 case *AliasType: 243 types.Types = append(types.Types, *xt) 244 case *StructType: 245 types.Structs = append(types.Structs, *xt) 246 case *UnionType: 247 types.Unions = append(types.Unions, *xt) 248 case *FunctionType: 249 types.Functions = append(types.Functions, *xt) 250 default: 251 panic(t) 252 } 253 } 254 255 return 256 257 }