Skip to content
← Back

src/ir/program/function_worklist.ghul

1
namespace IR.Program is
2
use Collections.LIST
3
use Collections.MAP
4
5
use Semantic.Symbols.Function
6
7
/// The function instances a whole program compiles, each given an
8
/// ordinal the first time something asks for it, so only what is
9
/// reached is compiled.
10
///
11
/// Asking for an instance adds it to the list `next` drains. A function
12
/// the target generates for itself takes an ordinal from `reserve` and
13
/// is never handed out. Ordinals are never taken back or changed:
14
/// asking twice answers the same ordinal, and `restart` walks the
15
/// instances again, in order, without adding anything.
16
class FUNCTION_WORKLIST is
17
_has_body: (Function) -> bool
18
19
_ordinals: MAP[FUNCTION_INSTANCE, int]
20
_entries: LIST[FUNCTION_INSTANCE?]
21
22
_cursor: int
23
24
_is_sealed: bool
25
26
/// A worklist for the functions `has_body` says the program
27
/// compiles.
28
///
29
/// - has_body: whether a function has a body the program compiles
30
init(has_body: (Function) -> bool) is
31
_has_body = has_body
32
33
_ordinals = MAP[FUNCTION_INSTANCE, int]()
34
_entries = LIST[FUNCTION_INSTANCE?]()
35
si
36
37
/// How many ordinals have been given out, reserved ones included.
38
count: int => _entries.count
39
40
/// The ordinal of `function`, taking no type arguments, adding it
41
/// the first time it is asked for, or null where it has no body to
42
/// compile.
43
add(function: Function) -> int? => add(FUNCTION_INSTANCE.of(function))
44
45
/// The ordinal of `instance`, adding it the first time it is asked
46
/// for, or null where its definition has no body to compile, or
47
/// where its type arguments nest too deeply to compile.
48
add(instance: FUNCTION_INSTANCE) -> int? is
49
let ordinal mut = 0
50
51
if _ordinals.try_get_value(instance, ordinal ref) then
52
return ordinal
53
fi
54
55
if !_has_body(instance.definition) then
56
return null
57
fi
58
59
// A function that calls itself at deeper and deeper type
60
// arguments would be added without end.
61
if TYPE_MAPS.depth(instance.type_map.values) > INSTANTIATION_LIMITS.MAXIMUM_TYPE_ARGUMENT_DEPTH then
62
return null
63
fi
64
65
assert !_is_sealed else "{instance} was first asked for after every body was compiled, so it never would be"
66
67
ordinal = _entries.count
68
69
_ordinals[instance] = ordinal
70
_entries.add(instance)
71
72
return ordinal
73
si
74
75
/// The ordinal `instance` already has, or null where nothing has
76
/// asked for it. Unlike `add`, this adds nothing.
77
ordinal_of(instance: FUNCTION_INSTANCE) -> int? is
78
let ordinal mut = 0
79
80
if _ordinals.try_get_value(instance, ordinal ref) then
81
return ordinal
82
fi
83
84
return null
85
si
86
87
/// The instance holding `ordinal`, or null where the ordinal was
88
/// reserved.
89
instance_at(ordinal: int) -> FUNCTION_INSTANCE? => _entries[ordinal]
90
91
/// Takes an ordinal for a function the target generates for
92
/// itself, which `next` never hands out.
93
reserve() -> int is
94
let ordinal = _entries.count
95
96
_entries.add(null)
97
98
return ordinal
99
si
100
101
/// The next instance not yet handed out, or null when every one has
102
/// been.
103
next() -> FUNCTION_INSTANCE? is
104
while _cursor < _entries.count do
105
let instance = _entries[_cursor]
106
107
_cursor = _cursor + 1
108
109
if instance? then
110
return instance
111
fi
112
od
113
114
return null
115
si
116
117
/// Records that every body has been compiled. An instance with a
118
/// body that is first asked for after this would never be compiled,
119
/// which `add` then asserts against.
120
seal() is
121
_is_sealed = true
122
si
123
124
/// Hands out the instances again from the first, in ordinal order,
125
/// keeping every ordinal.
126
restart() is
127
_cursor = 0
128
si
129
si
130
si