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