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