nandi.uk
Fork of daniellemaywood.uk/gleam — Wasm codegen work
18 kB
548 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, BitArrayOption, ClauseGuard, Constant, Pattern, SrcSpan, Statement,
11 UntypedClauseGuard, UntypedExpr, UntypedFunction, UntypedModuleConstant, UntypedPattern,
12 UntypedStatement,
13 },
14 type_::Error,
15};
16use itertools::Itertools;
17use petgraph::stable_graph::NodeIndex;
18use petgraph::{Directed, stable_graph::StableGraph};
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 Statement::Assert(assert) => {
161 self.expression(&assert.value);
162 }
163 };
164 }
165
166 fn expression(&mut self, expression: &'a UntypedExpr) {
167 match expression {
168 UntypedExpr::Int { .. }
169 | UntypedExpr::Float { .. }
170 | UntypedExpr::String { .. }
171 | UntypedExpr::Placeholder { .. } => (),
172
173 UntypedExpr::Todo { message, .. } => {
174 if let Some(msg_expr) = message {
175 self.expression(msg_expr)
176 }
177 }
178
179 UntypedExpr::Panic { message, .. } => {
180 if let Some(msg_expr) = message {
181 self.expression(msg_expr)
182 }
183 }
184
185 UntypedExpr::Echo {
186 expression,
187 location: _,
188 } => {
189 if let Some(expression) = expression {
190 self.expression(expression);
191 }
192 }
193
194 // Aha! A variable is being referenced.
195 UntypedExpr::Var { name, .. } => {
196 self.referenced(name);
197 }
198
199 UntypedExpr::Call { fun, arguments, .. } => {
200 self.expression(fun);
201 for argument in arguments {
202 self.expression(&argument.value);
203 }
204 }
205
206 UntypedExpr::PipeLine { expressions } => {
207 for expression in expressions {
208 self.expression(expression);
209 }
210 }
211
212 UntypedExpr::Tuple { elements, .. } => {
213 for expression in elements {
214 self.expression(expression);
215 }
216 }
217
218 UntypedExpr::Block { statements, .. } => {
219 let names = self.names.clone();
220 self.statements(statements);
221 self.names = names;
222 }
223
224 UntypedExpr::BinOp { left, right, .. } => {
225 self.expression(left);
226 self.expression(right);
227 }
228
229 UntypedExpr::List { elements, tail, .. } => {
230 for element in elements {
231 self.expression(element);
232 }
233 if let Some(tail) = tail {
234 self.expression(tail);
235 }
236 }
237
238 UntypedExpr::NegateInt {
239 value: expression, ..
240 }
241 | UntypedExpr::NegateBool {
242 value: expression, ..
243 }
244 | UntypedExpr::TupleIndex {
245 tuple: expression, ..
246 }
247 | UntypedExpr::FieldAccess {
248 container: expression,
249 ..
250 } => {
251 self.expression(expression);
252 }
253
254 UntypedExpr::BitArray { segments, .. } => {
255 for segment in segments {
256 self.expression(&segment.value);
257 for option in &segment.options {
258 if let BitArrayOption::Size { value, .. } = option {
259 self.expression(value);
260 }
261 }
262 }
263 }
264
265 UntypedExpr::RecordUpdate {
266 record, arguments, ..
267 } => {
268 self.expression(&record.base);
269 for argument in arguments {
270 self.expression(&argument.value);
271 }
272 }
273
274 UntypedExpr::Fn {
275 arguments, body, ..
276 } => {
277 let names = self.names.clone();
278 for argument in arguments {
279 if let Some(name) = argument.names.get_variable_name() {
280 self.define(name)
281 }
282 }
283 self.statements(body);
284 self.names = names;
285 }
286
287 UntypedExpr::Case {
288 subjects, clauses, ..
289 } => {
290 for subject in subjects {
291 self.expression(subject);
292 }
293 for clause in clauses.as_deref().unwrap_or_default() {
294 let names = self.names.clone();
295 for pattern in &clause.pattern {
296 self.pattern(pattern);
297 }
298 if let Some(guard) = &clause.guard {
299 self.guard(guard);
300 }
301 self.expression(&clause.then);
302 self.names = names;
303 }
304 }
305 }
306 }
307
308 fn pattern(&mut self, pattern: &'a UntypedPattern) {
309 match pattern {
310 Pattern::Discard { .. }
311 | Pattern::Int { .. }
312 | Pattern::Float { .. }
313 | Pattern::String { .. }
314 | Pattern::StringPrefix {
315 right_side_assignment: AssignName::Discard(_),
316 ..
317 }
318 | Pattern::Invalid { .. } => (),
319
320 Pattern::StringPrefix {
321 right_side_assignment: AssignName::Variable(name),
322 ..
323 }
324 | Pattern::Variable { name, .. } => {
325 self.define(name);
326 }
327
328 Pattern::Tuple {
329 elements: patterns, ..
330 } => {
331 for pattern in patterns {
332 self.pattern(pattern);
333 }
334 }
335
336 Pattern::List { elements, tail, .. } => {
337 for element in elements {
338 self.pattern(element);
339 }
340 if let Some(tail) = tail {
341 self.pattern(tail);
342 }
343 }
344
345 Pattern::VarUsage { name, .. } => {
346 self.referenced(name);
347 }
348
349 Pattern::Assign { name, pattern, .. } => {
350 self.define(name);
351 self.pattern(pattern);
352 }
353
354 Pattern::Constructor { arguments, .. } => {
355 for argument in arguments {
356 self.pattern(&argument.value);
357 }
358 }
359
360 Pattern::BitArray { segments, .. } => {
361 for segment in segments {
362 for option in &segment.options {
363 self.bit_array_option(option, |s, p| s.pattern(p));
364 }
365 self.pattern(&segment.value);
366 }
367 }
368 }
369 }
370
371 fn define(&mut self, name: &'a str) {
372 _ = self.names.insert(name, None);
373 }
374
375 fn bit_array_option<T>(
376 &mut self,
377 option: &'a BitArrayOption<T>,
378 process: impl Fn(&mut Self, &'a T),
379 ) {
380 match option {
381 BitArrayOption::Big { .. }
382 | BitArrayOption::Bytes { .. }
383 | BitArrayOption::Bits { .. }
384 | BitArrayOption::Float { .. }
385 | BitArrayOption::Int { .. }
386 | BitArrayOption::Little { .. }
387 | BitArrayOption::Native { .. }
388 | BitArrayOption::Signed { .. }
389 | BitArrayOption::Unit { .. }
390 | BitArrayOption::Unsigned { .. }
391 | BitArrayOption::Utf16 { .. }
392 | BitArrayOption::Utf16Codepoint { .. }
393 | BitArrayOption::Utf32 { .. }
394 | BitArrayOption::Utf32Codepoint { .. }
395 | BitArrayOption::Utf8 { .. }
396 | BitArrayOption::Utf8Codepoint { .. } => (),
397
398 BitArrayOption::Size { value: pattern, .. } => {
399 process(self, pattern);
400 }
401 }
402 }
403
404 fn guard(&mut self, guard: &'a UntypedClauseGuard) {
405 match guard {
406 ClauseGuard::Equals { left, right, .. }
407 | ClauseGuard::NotEquals { left, right, .. }
408 | ClauseGuard::GtInt { left, right, .. }
409 | ClauseGuard::GtEqInt { left, right, .. }
410 | ClauseGuard::LtInt { left, right, .. }
411 | ClauseGuard::LtEqInt { left, right, .. }
412 | ClauseGuard::GtFloat { left, right, .. }
413 | ClauseGuard::GtEqFloat { left, right, .. }
414 | ClauseGuard::LtFloat { left, right, .. }
415 | ClauseGuard::LtEqFloat { left, right, .. }
416 | ClauseGuard::AddInt { left, right, .. }
417 | ClauseGuard::AddFloat { left, right, .. }
418 | ClauseGuard::SubInt { left, right, .. }
419 | ClauseGuard::SubFloat { left, right, .. }
420 | ClauseGuard::MultInt { left, right, .. }
421 | ClauseGuard::MultFloat { left, right, .. }
422 | ClauseGuard::DivInt { left, right, .. }
423 | ClauseGuard::DivFloat { left, right, .. }
424 | ClauseGuard::RemainderInt { left, right, .. }
425 | ClauseGuard::Or { left, right, .. }
426 | ClauseGuard::And { left, right, .. } => {
427 self.guard(left);
428 self.guard(right);
429 }
430
431 ClauseGuard::Not { expression, .. } => self.guard(expression),
432
433 ClauseGuard::Var { name, .. } => self.referenced(name),
434
435 ClauseGuard::TupleIndex { tuple, .. } => self.guard(tuple),
436
437 ClauseGuard::FieldAccess { container, .. } => self.guard(container),
438
439 ClauseGuard::ModuleSelect { module_name, .. } => self.referenced(module_name),
440
441 ClauseGuard::Constant(constant) => self.constant(constant),
442 }
443 }
444
445 fn constant(&mut self, constant: &'a Constant<(), ()>) {
446 match constant {
447 Constant::Int { .. }
448 | Constant::Float { .. }
449 | Constant::String { .. }
450 | Constant::Invalid { .. }
451 | Constant::Var {
452 module: Some(_), ..
453 } => (),
454
455 Constant::List { elements, .. } | Constant::Tuple { elements, .. } => {
456 for element in elements {
457 self.constant(element);
458 }
459 }
460
461 Constant::Record { args, .. } => {
462 for arg in args {
463 self.constant(&arg.value);
464 }
465 }
466
467 Constant::Var {
468 module: None, name, ..
469 } => self.referenced(name),
470
471 Constant::BitArray { segments, .. } => {
472 for segment in segments {
473 for option in &segment.options {
474 self.bit_array_option(option, |s, c| s.constant(c));
475 }
476 self.constant(&segment.value);
477 }
478 }
479
480 Constant::StringConcatenation { left, right, .. } => {
481 self.constant(left);
482 self.constant(right);
483 }
484 }
485 }
486}
487
488/// Determine the order in which functions and constants should be compiled and if any
489/// mutually recursive functions need to be compiled together.
490///
491pub fn into_dependency_order(
492 functions: Vec<UntypedFunction>,
493 constants: Vec<UntypedModuleConstant>,
494) -> Result<Vec<Vec<CallGraphNode>>, Error> {
495 let mut grapher = CallGraphBuilder::default();
496
497 for function in &functions {
498 grapher.register_module_function_existence(function)?;
499 }
500
501 for constant in &constants {
502 grapher.register_module_const_existence(constant)?;
503 }
504
505 // Build the call graph between the module functions.
506 for function in &functions {
507 grapher.register_references(function);
508 }
509
510 for constant in &constants {
511 grapher.register_references_constant(constant);
512 }
513
514 // Consume the grapher to get the graph
515 let graph = grapher.into_graph();
516
517 // Determine the order in which the functions should be compiled by looking
518 // at which other functions they depend on.
519 let indices = crate::graph::into_dependency_order(graph);
520
521 // We got node indices back, so we need to map them back to the functions
522 // they represent.
523 // We wrap them each with `Some` so we can use `.take()`.
524 let mut definitions = functions
525 .into_iter()
526 .map(CallGraphNode::Function)
527 .chain(constants.into_iter().map(CallGraphNode::ModuleConstant))
528 .map(Some)
529 .collect_vec();
530
531 let ordered = indices
532 .into_iter()
533 .map(|level| {
534 level
535 .into_iter()
536 .map(|index| {
537 definitions
538 .get_mut(index.index())
539 .expect("Index out of bounds")
540 .take()
541 .expect("Function already taken")
542 })
543 .collect_vec()
544 })
545 .collect_vec();
546
547 Ok(ordered)
548}