Skip to content
← Back

src/ir/program/class_id_numbering.ghul

1
namespace IR.Program is
2
use Collections.LIST
3
use Collections.MAP
4
5
/// Numbers a class tree depth first, so a class and everything derived
6
/// from it hold one unbroken run of numbers, and a union's variants
7
/// number consecutively. Children are numbered in the order added.
8
class CLASS_ID_NUMBERING[T] is
9
_roots: LIST[T]
10
_children: MAP[T, LIST[T]]
11
_ids: MAP[T, int]
12
_last_descendants: MAP[T, int]
13
14
init() is
15
_roots = LIST[T]()
16
_children = MAP[T, LIST[T]]()
17
_ids = MAP[T, int]()
18
_last_descendants = MAP[T, int]()
19
si
20
21
/// Adds a tree's root.
22
add_root(node: T) is
23
_roots.add(node)
24
_children[node] = LIST[T]()
25
si
26
27
/// Adds `node` under `parent`, which must already have been added.
28
add(node: T, parent: T) is
29
_children[parent].add(node)
30
_children[node] = LIST[T]()
31
si
32
33
/// Assigns the numbers; call after the last node is added.
34
number() is
35
_ids.clear()
36
_last_descendants.clear()
37
38
let next mut = 0
39
40
for root in _roots do
41
next = _number(root, next)
42
od
43
si
44
45
_number(node: T, first: int) -> int is
46
_ids[node] = first
47
48
let next mut = first + 1
49
50
for child in _children[node] do
51
next = _number(child, next)
52
od
53
54
_last_descendants[node] = next - 1
55
56
return next
57
si
58
59
/// The number of `node`.
60
id(node: T) -> int => _ids[node]
61
62
/// The highest number held by `node` or anything derived from it.
63
last_descendant(node: T) -> int => _last_descendants[node]
64
65
/// Whether anything was added under `node`.
66
has_children(node: T) -> bool => _children[node].count > 0
67
68
/// The nodes added directly under `node`, in the order added.
69
children(node: T) -> Collections.List[T] => _children[node]
70
71
/// Whether `node` is `ancestor` or derives from it.
72
is_within(node: T, ancestor: T) -> bool is
73
let id = _ids[node]
74
75
return id >= _ids[ancestor] /\ id <= _last_descendants[ancestor]
76
si
77
78
/// Every node, parents before their children, in number order.
79
in_order() -> Collections.List[T] is
80
let result = LIST[T]()
81
82
for root in _roots do
83
_collect(root, result)
84
od
85
86
return result
87
si
88
89
_collect(node: T, into: LIST[T]) is
90
into.add(node)
91
92
for child in _children[node] do
93
_collect(child, into)
94
od
95
si
96
si
97
si