nandi.uk
Fork of daniellemaywood.uk/gleam — Wasm codegen work
18 kB
536 lines
1//! Graphs that represent the relationships between entities in a Gleam module,
2//! such as module functions or constants.
3
4#[cfg(test)]
5mod into_dependency_order_tests;
6
7use crate::{
8 ast::{
9 AssignName, BitArrayOption, ClauseGuard, Constant, Pattern, SrcSpan, Statement,
10 UntypedClauseGuard, UntypedExpr, UntypedFunction, UntypedModuleConstant, UntypedPattern,
11 UntypedStatement,
12 },
13 type_::Error,
14 Result,
15};
16use itertools::Itertools;
17use petgraph::stable_graph::NodeIndex;
18use petgraph::{stable_graph::StableGraph, Directed};
19
20#[derive(Debug, Default)]
21struct CallGraphBuilder<'a> {
22 names: im::HashMap<&'a str, Option<(NodeIndex, SrcSpan)>>,
23 graph: StableGraph<(), (), Directed>,
24 current_function: NodeIndex,
25}
26
27#[derive(Debug, Clone, PartialEq, Eq)]
28pub enum CallGraphNode {
29 Function(UntypedFunction),
30
31 ModuleConstant(UntypedModuleConstant),
32}
33
34impl<'a> CallGraphBuilder<'a> {
35 fn into_graph(self) -> StableGraph<(), (), Directed> {
36 self.graph
37 }
38
39 /// Add each function to the graph, storing the index of the node under the
40 /// name of the function.
41 fn register_module_function_existence(
42 &mut self,
43 function: &'a UntypedFunction,
44 ) -> Result<(), Error> {
45 let (_, name) = function
46 .name
47 .as_ref()
48 .expect("A module's function must be named");
49 let location = function.location;
50
51 let index = self.graph.add_node(());
52 let previous = self.names.insert(name, Some((index, location)));
53
54 if let Some(Some((_, previous_location))) = previous {
55 return Err(Error::DuplicateName {
56 location_a: location,
57 location_b: previous_location,
58 name: name.clone(),
59 });
60 }
61 Ok(())
62 }
63
64 /// Add each constant to the graph, storing the index of the node under the
65 /// name of the constant.
66 fn register_module_const_existence(
67 &mut self,
68 constant: &'a UntypedModuleConstant,
69 ) -> Result<(), Error> {
70 let name = &constant.name;
71 let location = constant.location;
72
73 let index = self.graph.add_node(());
74 let previous = self.names.insert(name, Some((index, location)));
75
76 if let Some(Some((_, previous_location))) = previous {
77 return Err(Error::DuplicateName {
78 location_a: location,
79 location_b: previous_location,
80 name: name.clone(),
81 });
82 }
83 Ok(())
84 }
85
86 fn register_references_constant(&mut self, constant: &'a UntypedModuleConstant) {
87 self.current_function = self
88 .names
89 .get(constant.name.as_str())
90 .expect("Constant must already have been registered as existing")
91 .expect("Constant must not be shadowed at module level")
92 .0;
93 self.constant(&constant.value);
94 }
95
96 fn register_references(&mut self, function: &'a UntypedFunction) {
97 let names = self.names.clone();
98
99 self.current_function = self
100 .names
101 .get(
102 function
103 .name
104 .as_ref()
105 .map(|(_, name)| name.as_str())
106 .expect("A module's function must be named"),
107 )
108 .expect("Function must already have been registered as existing")
109 .expect("Function must not be shadowed at module level")
110 .0;
111 for name in function
112 .arguments
113 .iter()
114 .flat_map(|a| a.get_variable_name())
115 {
116 self.define(name);
117 }
118 self.statements(&function.body);
119 self.names = names;
120 }
121
122 fn referenced(&mut self, name: &str) {
123 // If we don't know what the target is then it's either a programmer
124 // error to be detected later, or it's not a module function and as such
125 // is not a value we are tracking.
126 let Some(target) = self.names.get(name) else {
127 return;
128 };
129
130 // If the target is known but registered as None then it's local value
131 // that shadows a module function.
132 let Some((target, _)) = target else { return };
133
134 _ = self.graph.add_edge(self.current_function, *target, ());
135 }
136
137 fn statements(&mut self, statements: &'a [UntypedStatement]) {
138 let names = self.names.clone();
139 for statement in statements {
140 self.statement(statement);
141 }
142 self.names = names;
143 }
144
145 fn statement(&mut self, statement: &'a UntypedStatement) {
146 match statement {
147 Statement::Expression(expression) => {
148 self.expression(expression);
149 }
150 Statement::Assignment(assignment) => {
151 self.expression(&assignment.value);
152 self.pattern(&assignment.pattern);
153 }
154 Statement::Use(use_) => {
155 self.expression(&use_.call);
156 for assignment in &use_.assignments {
157 self.pattern(&assignment.pattern);
158 }
159 }
160 };
161 }
162
163 fn expression(&mut self, expression: &'a UntypedExpr) {
164 match expression {
165 UntypedExpr::Int { .. }
166 | UntypedExpr::Float { .. }
167 | UntypedExpr::String { .. }
168 | UntypedExpr::Placeholder { .. } => (),
169
170 UntypedExpr::Todo { message, .. } => {
171 if let Some(msg_expr) = message {
172 self.expression(msg_expr)
173 }
174 }
175
176 UntypedExpr::Panic { message, .. } => {
177 if let Some(msg_expr) = message {
178 self.expression(msg_expr)
179 }
180 }
181
182 // Aha! A variable is being referenced.
183 UntypedExpr::Var { name, .. } => {
184 self.referenced(name);
185 }
186
187 UntypedExpr::Call { fun, arguments, .. } => {
188 self.expression(fun);
189 for argument in arguments {
190 self.expression(&argument.value);
191 }
192 }
193
194 UntypedExpr::PipeLine { expressions } => {
195 for expression in expressions {
196 self.expression(expression);
197 }
198 }
199
200 UntypedExpr::Tuple { elems, .. } => {
201 for expression in elems {
202 self.expression(expression);
203 }
204 }
205
206 UntypedExpr::Block { statements, .. } => {
207 let names = self.names.clone();
208 self.statements(statements);
209 self.names = names;
210 }
211
212 UntypedExpr::BinOp { left, right, .. } => {
213 self.expression(left);
214 self.expression(right);
215 }
216
217 UntypedExpr::List { elements, tail, .. } => {
218 for element in elements {
219 self.expression(element);
220 }
221 if let Some(tail) = tail {
222 self.expression(tail);
223 }
224 }
225
226 UntypedExpr::NegateInt {
227 value: expression, ..
228 }
229 | UntypedExpr::NegateBool {
230 value: expression, ..
231 }
232 | UntypedExpr::TupleIndex {
233 tuple: expression, ..
234 }
235 | UntypedExpr::FieldAccess {
236 container: expression,
237 ..
238 } => {
239 self.expression(expression);
240 }
241
242 UntypedExpr::BitArray { segments, .. } => {
243 for segment in segments {
244 self.expression(&segment.value);
245 for option in &segment.options {
246 if let BitArrayOption::Size { value, .. } = option {
247 self.expression(value);
248 }
249 }
250 }
251 }
252
253 UntypedExpr::RecordUpdate {
254 record, arguments, ..
255 } => {
256 self.expression(&record.base);
257 for argument in arguments {
258 self.expression(&argument.value);
259 }
260 }
261
262 UntypedExpr::Fn {
263 arguments, body, ..
264 } => {
265 let names = self.names.clone();
266 for argument in arguments {
267 if let Some(name) = argument.names.get_variable_name() {
268 self.define(name)
269 }
270 }
271 self.statements(body);
272 self.names = names;
273 }
274
275 UntypedExpr::Case {
276 subjects, clauses, ..
277 } => {
278 for subject in subjects {
279 self.expression(subject);
280 }
281 for clause in clauses.as_deref().unwrap_or_default() {
282 let names = self.names.clone();
283 for pattern in &clause.pattern {
284 self.pattern(pattern);
285 }
286 if let Some(guard) = &clause.guard {
287 self.guard(guard);
288 }
289 self.expression(&clause.then);
290 self.names = names;
291 }
292 }
293 }
294 }
295
296 fn pattern(&mut self, pattern: &'a UntypedPattern) {
297 match pattern {
298 Pattern::Discard { .. }
299 | Pattern::Int { .. }
300 | Pattern::Float { .. }
301 | Pattern::String { .. }
302 | Pattern::StringPrefix {
303 right_side_assignment: AssignName::Discard(_),
304 ..
305 }
306 | Pattern::Invalid { .. } => (),
307
308 Pattern::StringPrefix {
309 right_side_assignment: AssignName::Variable(name),
310 ..
311 }
312 | Pattern::Variable { name, .. } => {
313 self.define(name);
314 }
315
316 Pattern::Tuple {
317 elems: patterns, ..
318 } => {
319 for pattern in patterns {
320 self.pattern(pattern);
321 }
322 }
323
324 Pattern::List { elements, tail, .. } => {
325 for element in elements {
326 self.pattern(element);
327 }
328 if let Some(tail) = tail {
329 self.pattern(tail);
330 }
331 }
332
333 Pattern::VarUsage { name, .. } => {
334 self.referenced(name);
335 }
336
337 Pattern::Assign { name, pattern, .. } => {
338 self.define(name);
339 self.pattern(pattern);
340 }
341
342 Pattern::Constructor { arguments, .. } => {
343 for argument in arguments {
344 self.pattern(&argument.value);
345 }
346 }
347
348 Pattern::BitArray { segments, .. } => {
349 for segment in segments {
350 for option in &segment.options {
351 self.bit_array_option(option, |s, p| s.pattern(p));
352 }
353 self.pattern(&segment.value);
354 }
355 }
356 }
357 }
358
359 fn define(&mut self, name: &'a str) {
360 _ = self.names.insert(name, None);
361 }
362
363 fn bit_array_option<T>(
364 &mut self,
365 option: &'a BitArrayOption<T>,
366 process: impl Fn(&mut Self, &'a T),
367 ) {
368 match option {
369 BitArrayOption::Big { .. }
370 | BitArrayOption::Bytes { .. }
371 | BitArrayOption::Bits { .. }
372 | BitArrayOption::Float { .. }
373 | BitArrayOption::Int { .. }
374 | BitArrayOption::Little { .. }
375 | BitArrayOption::Native { .. }
376 | BitArrayOption::Signed { .. }
377 | BitArrayOption::Unit { .. }
378 | BitArrayOption::Unsigned { .. }
379 | BitArrayOption::Utf16 { .. }
380 | BitArrayOption::Utf16Codepoint { .. }
381 | BitArrayOption::Utf32 { .. }
382 | BitArrayOption::Utf32Codepoint { .. }
383 | BitArrayOption::Utf8 { .. }
384 | BitArrayOption::Utf8Codepoint { .. } => (),
385
386 BitArrayOption::Size { value: pattern, .. } => {
387 process(self, pattern);
388 }
389 }
390 }
391
392 fn guard(&mut self, guard: &'a UntypedClauseGuard) {
393 match guard {
394 ClauseGuard::Equals { left, right, .. }
395 | ClauseGuard::NotEquals { left, right, .. }
396 | ClauseGuard::GtInt { left, right, .. }
397 | ClauseGuard::GtEqInt { left, right, .. }
398 | ClauseGuard::LtInt { left, right, .. }
399 | ClauseGuard::LtEqInt { left, right, .. }
400 | ClauseGuard::GtFloat { left, right, .. }
401 | ClauseGuard::GtEqFloat { left, right, .. }
402 | ClauseGuard::LtFloat { left, right, .. }
403 | ClauseGuard::LtEqFloat { left, right, .. }
404 | ClauseGuard::AddInt { left, right, .. }
405 | ClauseGuard::AddFloat { left, right, .. }
406 | ClauseGuard::SubInt { left, right, .. }
407 | ClauseGuard::SubFloat { left, right, .. }
408 | ClauseGuard::MultInt { left, right, .. }
409 | ClauseGuard::MultFloat { left, right, .. }
410 | ClauseGuard::DivInt { left, right, .. }
411 | ClauseGuard::DivFloat { left, right, .. }
412 | ClauseGuard::RemainderInt { left, right, .. }
413 | ClauseGuard::Or { left, right, .. }
414 | ClauseGuard::And { left, right, .. } => {
415 self.guard(left);
416 self.guard(right);
417 }
418
419 ClauseGuard::Not { expression, .. } => self.guard(expression),
420
421 ClauseGuard::Var { name, .. } => self.referenced(name),
422
423 ClauseGuard::TupleIndex { tuple, .. } => self.guard(tuple),
424
425 ClauseGuard::FieldAccess { container, .. } => self.guard(container),
426
427 ClauseGuard::ModuleSelect { module_name, .. } => self.referenced(module_name),
428
429 ClauseGuard::Constant(constant) => self.constant(constant),
430 }
431 }
432
433 fn constant(&mut self, constant: &'a Constant<(), ()>) {
434 match constant {
435 Constant::Int { .. }
436 | Constant::Float { .. }
437 | Constant::String { .. }
438 | Constant::Invalid { .. }
439 | Constant::Var {
440 module: Some(_), ..
441 } => (),
442
443 Constant::List { elements, .. } | Constant::Tuple { elements, .. } => {
444 for element in elements {
445 self.constant(element);
446 }
447 }
448
449 Constant::Record { args, .. } => {
450 for arg in args {
451 self.constant(&arg.value);
452 }
453 }
454
455 Constant::Var {
456 module: None, name, ..
457 } => self.referenced(name),
458
459 Constant::BitArray { segments, .. } => {
460 for segment in segments {
461 for option in &segment.options {
462 self.bit_array_option(option, |s, c| s.constant(c));
463 }
464 self.constant(&segment.value);
465 }
466 }
467
468 Constant::StringConcatenation { left, right, .. } => {
469 self.constant(left);
470 self.constant(right);
471 }
472 }
473 }
474}
475
476/// Determine the order in which functions and constants should be compiled and if any
477/// mutually recursive functions need to be compiled together.
478///
479pub fn into_dependency_order(
480 functions: Vec<UntypedFunction>,
481 constants: Vec<UntypedModuleConstant>,
482) -> Result<Vec<Vec<CallGraphNode>>, Error> {
483 let mut grapher = CallGraphBuilder::default();
484
485 for function in &functions {
486 grapher.register_module_function_existence(function)?;
487 }
488
489 for constant in &constants {
490 grapher.register_module_const_existence(constant)?;
491 }
492
493 // Build the call graph between the module functions.
494 for function in &functions {
495 grapher.register_references(function);
496 }
497
498 for constant in &constants {
499 grapher.register_references_constant(constant);
500 }
501
502 // Consume the grapher to get the graph
503 let graph = grapher.into_graph();
504
505 // Determine the order in which the functions should be compiled by looking
506 // at which other functions they depend on.
507 let indices = crate::graph::into_dependency_order(graph);
508
509 // We got node indices back, so we need to map them back to the functions
510 // they represent.
511 // We wrap them each with `Some` so we can use `.take()`.
512 let mut definitions = functions
513 .into_iter()
514 .map(CallGraphNode::Function)
515 .chain(constants.into_iter().map(CallGraphNode::ModuleConstant))
516 .map(Some)
517 .collect_vec();
518
519 let ordered = indices
520 .into_iter()
521 .map(|level| {
522 level
523 .into_iter()
524 .map(|index| {
525 definitions
526 .get_mut(index.index())
527 .expect("Index out of bounds")
528 .take()
529 .expect("Function already taken")
530 })
531 .collect_vec()
532 })
533 .collect_vec();
534
535 Ok(ordered)
536}