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