Repository navigation
Expand file tree
/
Copy pathgraph.tl
More file actions
280 lines (248 loc) · 7.36 KB
/
Copy pathgraph.tl
File metadata and controls
280 lines (248 loc) · 7.36 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
---@brief
--- A utility for building directed acyclic graphs of Teal source files
---
--- This is the main driver behind the `build` command
local common <const> = require("cyan.tlcommon")
local fs <const> = require("cyan.fs")
local util <const> = require("cyan.util")
local values <const>, ivalues <const>, keys <const>, from <const>
= util.tab.values, util.tab.ivalues, util.tab.keys, util.tab.from
---@desc
--- The nodes that are stored in the graph
local record Node
input: fs.Path
output: fs.Path
modules: {string:fs.Path} -- require argument -> path found
enum Mark
"typecheck"
"compile"
end
mark: Mark
dependents: {Node:boolean}
end
local function make_node(input: fs.Path): Node
return {
input = input,
modules = {},
dependents = {},
}
end
---@desc
--- The graph object
local record Dag
_nodes_by_filename: {string:Node}
end
local function mark_for_typecheck(n: Node)
if n.mark then return end
n.mark = "typecheck"
for child in keys(n.dependents) do
mark_for_typecheck(child)
end
end
local function mark_for_compile(n: Node)
if n.mark == "compile" then return end
n.mark = "compile"
for child in keys(n.dependents) do
mark_for_typecheck(child)
end
end
local function make_dependent_counter(): function(Node): integer
local cache <const>: {Node:integer} = {}
local function count_dependents(n: Node): integer
if cache[n] then return cache[n] end
local deps = 0
for v in keys(n.dependents) do
deps = deps + count_dependents(v) + 1
end
cache[n] = deps
return deps
end
return count_dependents
end
---@desc
--- Iterate over nodes in order of dependents
---
--- If two nodes have the same number of dependent nodes, the order of
--- iteration between those two nodes is not guaranteed
function Dag:nodes(): function(): Node
local count <const> = make_dependent_counter()
local most_deps = 0
local nodes_by_deps <const>: {integer:{Node}} = setmetatable({}, {
__index = function(self: {integer:{Node}}, key: integer): {Node}
if key > most_deps then
most_deps = key
end
local arr <const> = {}
rawset(self, key, arr)
return arr
end,
})
for n in values(self._nodes_by_filename) do
table.insert(nodes_by_deps[count(n)], n)
end
setmetatable(nodes_by_deps, nil)
local i = most_deps
if not nodes_by_deps[i] then
return function(): nil end
end
local iter = values(nodes_by_deps[i])
return function(): Node
local n: Node
while i >= 0 do
n = iter()
if n then
return n
end
repeat i = i - 1
until i < 0 or nodes_by_deps[i] as boolean
if nodes_by_deps[i] then
iter = values(nodes_by_deps[i])
end
end
end
end
---@desc
--- For each node in the graph, if `predicate` returns true for that input
--- path, the node is marked for compilation, and that node's children are marked
--- for type checking
function Dag:mark_each(predicate: function(fs.Path): boolean)
for n in self:nodes() do
if predicate(n.input) then
mark_for_compile(n)
end
end
end
---@desc
--- Iterate over every node with the given mark `m`. Iterates in order of most dependents to least
function Dag:marked_nodes(m: Node.Mark): function(): Node
local iter = self:nodes()
return function(): Node
local n: Node
repeat n = iter()
until not n
or n.mark == m
return n
end
end
local graph <const> = {
Node = Node,
Dag = Dag,
}
---@desc
--- Initializes an empty graph
function graph.empty(): Dag
return setmetatable({
_nodes_by_filename = {},
}, { __index = Dag })
end
local function add_deps(t: {Node:boolean}, n: Node)
for child in pairs(n.dependents) do
if not t[child] then
t[child] = true
add_deps(t, child)
end
end
t[n] = true
end
local function unchecked_insert(dag: Dag, f: fs.Path, in_dir: fs.Path)
if f:is_absolute() then
-- If a path is absolute, assume it is out of the project
return
end
local real_path <const> = f:to_real_path()
if dag._nodes_by_filename[real_path] then
-- We already have this in the graph
return
end
local res <const> = common.parse_file(real_path)
if not res then return end
local n <const>: Node = make_node(f)
dag._nodes_by_filename[real_path] = n
for mod_name in ivalues(res.reqs or {}) do
-- We don't search for .d.tl files here because we don't want to generate
-- anything for them
local search_result = common.search_module(mod_name)
if search_result then
if in_dir and search_result:is_absolute() and search_result:is_in(in_dir) then
search_result = search_result:relative_to(in_dir)
assert(not search_result:is_absolute())
end
n.modules[mod_name] = search_result
if not in_dir or search_result:is_in(in_dir) then
unchecked_insert(dag, search_result, in_dir)
end
end
end
for node in values(dag._nodes_by_filename) do
for mod_path in values(node.modules) do
local dep_node = dag._nodes_by_filename[mod_path:to_real_path()]
if dep_node then
add_deps(dep_node.dependents, node)
end
end
end
end
-- returns the list of filenames that depend on themselves
local function check_for_cycles(dag: Dag): {string}
local ret = {}
for fname, n in pairs(dag._nodes_by_filename) do
if n.dependents[n] then
ret[fname] = true
end
end
if next(ret) then
return from(keys(ret))
end
end
---@desc
--- Inserts a file and its dependencies into a graph
---
--- Ignores absolute paths and non `.tl` or `.lua` files
---
--- If in_dir is provided, dependencies of the given file will not be added to
--- the graph unless they are inside of the given dir
---
--- Returns `false` if inserting the file introduced a circular dependency along
--- with a list of the filenames in the cycle
function Dag:insert_file(fstr: string | fs.Path, in_dir: string | fs.Path): boolean, {string}
local f <const> = fstr is fs.Path
and fstr
or fs.path.new(fstr as string)
assert(f, "No path given")
unchecked_insert(self, f, fs.path.ensure(in_dir))
local cycles <const> = check_for_cycles(self)
if cycles then
return false, cycles
else
return true
end
end
---@desc
--- Find a node in the graph with the given path name
function Dag:find(fstr: string | fs.Path): Node
local f <const> = fs.path.ensure(fstr)
return self._nodes_by_filename[f:to_real_path()]
end
---@desc
--- Recursively scan a directory (using `fs.scan_dir`) and build up a graph,
--- respecting the given `include` and `exclude` patterns
---
--- Returns `nil` if a circular dependency was found, along
--- with a list of the filenames in the cycle
function graph.scan_dir(dir: string | fs.Path, include: {string}, exclude: {string}): Dag, {string}
local d <const> = graph.empty()
dir = fs.path.ensure(dir)
for p in fs.scan_dir(dir, include, exclude) do
local _, ext = fs.extension_split(p, 2)
if ext == ".tl" or ext == ".lua" then
unchecked_insert(d, (d
3904
ir as fs.Path) .. p, dir as fs.Path)
end
end
local cycles <const> = check_for_cycles(d)
if cycles then
return nil, cycles
else
return d
end
end
return graph