nandi.uk
Fork of daniellemaywood.uk/gleam — Wasm codegen work
50 kB
1369 lines
1//! An implementation of the algorithm described at
2//! <https://julesjacobs.com/notes/patternmatching/patternmatching.pdf>.
3//!
4//! Adapted from Yorick Peterse's implementation at
5//! <https://github.com/yorickpeterse/pattern-matching-in-rust>. Thank you Yorick!
6//!
7//! > This module comment (and all the following doc comments) are a rough
8//! > explanation. It's great to set some expectations on what to expect from
9//! > the following code and why the data looks the way it does.
10//! > If you want a more detailed explanation, the original paper is a lot more
11//! > detailed!
12//!
13//! A case to be compiled looks a bit different from the case expressions we're
14//! used to in Gleam: instead of having a variable to match on and a series of
15//! branches, a `CaseToCompile` is made up of a series of branches that can each
16//! contain multiple pattern checks. With a psedo-Gleam syntax, this is what it
17//! would look like:
18//!
19//! ```
20//! case {
21//! a is Some, b is 1, c is _ -> todo
22//! a is wibble -> todo
23//! }
24//! ```
25//!
26//! > You may wonder, why are we writing branches like this? Usually a case
27//! > expression matches on a single variable and each branch refers to it. For
28//! > example in gleam you'd write:
29//! >
30//! > ```gleam
31//! > case a {
32//! > Some(_) -> todo
33//! > None -> todo
34//! > }
35//! > ```
36//! >
37//! > In out representation that would turn into:
38//! >
39//! > ```
40//! > case {
41//! > a is Some(_) -> todo
42//! > a is None -> todo
43//! > }
44//! > ```
45//! >
46//! > This change makes it way easier to compile the pattern matching into a
47//! > decision tree, because now we can add multiple checks on different
48//! > variables in each branch.
49//!
50//! Starting from this data structure, we'll be splitting all the branches into
51//! a decision tree that can be used to perform exhaustiveness checking and code
52//! generation.
53//!
54//! At the moment this tree is not suitable for use in code generation yet as it
55//! is incomplete. The tree is not correctly formed for:
56//! - Bit strings
57//! - String prefixes
58//!
59//! These were not implemented as they are more complex and I've not worked out
60//! a good way to do them yet. The tricky bit is that unlike the others they are
61//! not an exact match and they can overlap with other patterns. Take this
62//! example:
63//!
64//! ```text
65//! case x {
66//! "1" <> _ -> ...
67//! "12" <> _ -> ...
68//! "123" -> ...
69//! _ -> ...
70//! }
71//! ```
72//!
73//! The decision tree needs to take into account that the first pattern is a
74//! super-pattern of the second, and the second is a super-pattern of the third.
75//!
76
77mod missing_patterns;
78pub mod printer;
79
80use crate::{
81 ast::{AssignName, TypedClause, TypedPattern},
82 type_::{
83 Environment, Type, TypeValueConstructor, TypeValueConstructorField, TypeVar,
84 TypeVariantConstructors, collapse_links, error::UnreachableCaseClauseReason,
85 is_prelude_module,
86 },
87};
88use ecow::EcoString;
89use id_arena::{Arena, Id};
90use itertools::Itertools;
91use std::{
92 cell::RefCell,
93 collections::{HashMap, VecDeque},
94 hash::Hash,
95 sync::Arc,
96};
97
98/// A single branch composing a `case` expression to be compiled into a decision
99/// tree.
100///
101/// As shown in the module documentation, branches are a bit different from the
102/// usual branches we see in Gleam's case expressions. Each branch can perform
103/// multiple checks (each on a different variable, which appears in the check
104/// itself!):
105///
106/// ```
107/// a is Some, b is 1 if condition -> todo
108/// ─┬─────── ─┬──── ─┬────────── ─┬──
109/// │ │ │ ╰── body: an arbitrary expression
110/// │ │ ╰── guard: an additional boolean condition
111/// ╰──────────┴── checks: check that a variable matches with a pattern
112/// ─┬────────────────────────────────────
113/// ╰── branch: one of the branches making up a pattern matching expression
114/// ```
115///
116/// As shown here a branch can also optionally include a guard with a boolean
117/// condition and is followed by a body that is to be executed if all the checks
118/// match (and the guard evaluates to true).
119///
120#[derive(Clone, Eq, PartialEq, Debug)]
121struct Branch {
122 /// Each branch is identified by a numeric index, so we can nicely
123 /// report errors once we find something's wrong with a branch.
124 ///
125 branch_index: usize,
126
127 /// Each alternative pattern in an alternative pattern matching (e.g.
128 /// `one | two | three -> todo`) gets turned into its own branch in this
129 /// internal representation. So we also keep track of the index of the
130 /// alternative this comes from (0 being the first one and so on...)
131 ///
132 alternative_index: usize,
133 checks: Vec<PatternCheck>,
134 guard: Option<usize>,
135 body: Body,
136}
137
138impl Branch {
139 fn new(
140 branch_index: usize,
141 alternative_index: usize,
142 checks: Vec<PatternCheck>,
143 has_guard: bool,
144 ) -> Self {
145 Self {
146 branch_index,
147 alternative_index,
148 checks,
149 guard: if has_guard { Some(branch_index) } else { None },
150 body: Body::new(branch_index),
151 }
152 }
153
154 /// Removes and returns a `PatternCheck` on the given variable from this
155 /// branch.
156 ///
157 fn pop_check_on_var(&mut self, var: &Variable) -> Option<PatternCheck> {
158 let index = self.checks.iter().position(|check| check.var == *var)?;
159 Some(self.checks.remove(index))
160 }
161
162 fn add_check(&mut self, check: PatternCheck) {
163 self.checks.push(check);
164 }
165
166 /// To simplify compiling the pattern we can get rid of all catch-all
167 /// patterns that are guaranteed to match by turning those into assignments.
168 ///
169 /// What does this look like in practice? Let's go over an example.
170 /// Let's say we have this case to compile:
171 ///
172 /// ```gleam
173 /// case a {
174 /// Some(1) -> Some(2)
175 /// otherwise -> otherwise
176 /// }
177 /// ```
178 ///
179 /// In our internal representation this would become:
180 ///
181 /// ```
182 /// case {
183 /// a is Some(1) -> Some(2)
184 /// a is otherwise -> otherwise
185 /// ─┬────────────
186 /// ╰── `a` will always match with this "catch all" variable pattern
187 /// }
188 /// ```
189 ///
190 /// Focusing on the last branch, we can remove that check that always matches
191 /// by keeping track in its body of the correspondence. So it would end up
192 /// looking like this:
193 ///
194 /// ```
195 /// case {
196 /// a is Some(1) -> Some(2)
197 /// ∅ -> {
198 /// ┬
199 /// ╰── This represents the fact that there's no checks left for this branch!
200 /// So we can make another observation: if there's no checks left in a
201 /// branch we know it will always match and we can produce a leaf in the
202 /// decision tree (there's an exception when we have guards, but we'll
203 /// get to it later)!
204 ///
205 /// let otherwise = a
206 /// ─┬───────────────
207 /// ╰── And now we can understand what those `bindings` at the start of
208 /// a body are: as we remove variable patterns, we will rewrite those
209 /// as assignments at the top of the body of the corresponding branch.
210 ///
211 /// otherwise
212 /// }
213 /// }
214 /// ```
215 ///
216 fn move_unconditional_patterns(&mut self, compiler: &Compiler<'_>) {
217 self.checks.retain_mut(|check| {
218 loop {
219 match compiler.pattern(check.pattern) {
220 // Variable patterns always match, so we move those to the body
221 // and remove them from the branch's checks.
222 Pattern::Variable { name } => {
223 self.body.assign(name.clone(), check.var.clone());
224 return false;
225 }
226 // A discard pattern always matches, but since the value is not
227 // used we can just remove it without even adding an assignment
228 // to the body!
229 Pattern::Discard => return false,
230 // Assigns are kind of special: they get turned into assignments
231 // (shocking) but then we can't discard the pattern they wrap.
232 // So we replace the assignment pattern with the one it's wrapping
233 // and try again.
234 Pattern::Assign { name, pattern } => {
235 self.body.assign(name.clone(), check.var.clone());
236 check.pattern = *pattern;
237 continue;
238 }
239 // All other patterns are not unconditional, so we just keep them.
240 _ => return true,
241 }
242 }
243 });
244 }
245}
246
247/// The body of a branch. It always starts with a series of variable assignments
248/// in the form: `let a = b`. As explained in `move_unconditional_patterns`' doc,
249/// each body starts with a series of assignments we keep track of as we're
250/// compiling each branch.
251///
252#[derive(Clone, Eq, PartialEq, Debug)]
253pub struct Body {
254 /// Any variables to bind before running the code.
255 ///
256 /// The tuples are in the form `(name, value)`, so `(wibble, var)`
257 /// corresponds to `let wibble = var`.
258 ///
259 bindings: Vec<(EcoString, Variable)>,
260
261 /// The index of the clause in the case expression that should be run.
262 ///
263 branch_index: usize,
264}
265
266impl Body {
267 pub fn new(branch_index: usize) -> Self {
268 Self {
269 bindings: vec![],
270 branch_index,
271 }
272 }
273
274 /// Adds a new assignment to the body, binding `let var = value`
275 ///
276 pub fn assign(&mut self, var: EcoString, value: Variable) {
277 self.bindings.push((var, value));
278 }
279}
280
281/// A user defined pattern such as `Some((x, 10))`.
282/// This is a bit simpler than the full fledged `TypedPattern` used for code analysis
283/// and only focuses on the relevant bits needed to perform exhaustiveness checking
284/// and code generation.
285///
286/// Using this simplified version of a pattern for the case compiler makes it a
287/// whole lot simpler and more efficient (patterns will have to be cloned, so
288/// we use an arena to allocate those and only store ids to make this operation
289/// extra cheap).
290///
291#[derive(Clone, Eq, PartialEq, Debug)]
292pub enum Pattern {
293 Discard,
294 Int {
295 value: EcoString,
296 },
297 Float {
298 value: EcoString,
299 },
300 String {
301 value: EcoString,
302 },
303 StringPrefix {
304 prefix: EcoString,
305 rest: Id<Pattern>,
306 },
307 Assign {
308 name: EcoString,
309 pattern: Id<Pattern>,
310 },
311 Variable {
312 name: EcoString,
313 },
314 Tuple {
315 elements: Vec<Id<Pattern>>,
316 },
317 Constructor {
318 variant_index: usize,
319 arguments: Vec<Id<Pattern>>,
320 },
321 List {
322 first: Id<Pattern>,
323 rest: Id<Pattern>,
324 },
325 EmptyList,
326 // TODO: Compile the matching within the bit strings
327 BitArray {
328 value: EcoString,
329 },
330}
331
332impl Pattern {
333 fn inner_patterns(&self) -> Vec<Id<Pattern>> {
334 match self {
335 Pattern::Discard
336 | Pattern::Int { .. }
337 | Pattern::Float { .. }
338 | Pattern::String { .. }
339 | Pattern::Assign { .. }
340 | Pattern::Variable { .. }
341 | Pattern::BitArray { .. }
342 | Pattern::EmptyList => vec![],
343
344 Pattern::StringPrefix { rest, .. } => vec![*rest],
345
346 Pattern::Tuple { elements } => elements.clone(),
347 Pattern::Constructor { arguments, .. } => arguments.clone(),
348 Pattern::List { first, rest } => vec![*first, *rest],
349 }
350 }
351}
352
353/// A single check making up a branch, checking that a variable matches with a
354/// given pattern. For example, the following branch has 2 checks:
355///
356/// ```
357/// a is Some, b is 1 -> todo
358/// ┬ ─┬──
359/// │ ╰── This is the pattern being checked
360/// ╰── This is the variable being pattern matched on
361/// ─┬─────── ─┬────
362/// ╰─────────┴── Two `PatternCheck`s
363/// ```
364///
365#[derive(Clone, Eq, PartialEq, Debug)]
366struct PatternCheck {
367 var: Variable,
368 pattern: Id<Pattern>,
369}
370
371impl PatternCheck {
372 fn new(var: Variable, pattern: Id<Pattern>) -> Self {
373 Self { var, pattern }
374 }
375
376 /// Each pattern check (with a couple exceptions) can be turned into a
377 /// simpler `RuntimeCheck`: that is a check that can be performed at runtime
378 /// to make sure the `PatternCheck` can succeed on a specific value.
379 ///
380 fn to_runtime_check_kind(&self, compiler: &Compiler<'_>) -> Option<RuntimeCheckKind> {
381 let kind = match compiler.pattern(self.pattern) {
382 // These patterns are unconditional: they will always match and be moved
383 // out of a branch's checks. So there's no corresponding runtime check
384 // we can perform for them.
385 Pattern::Discard | Pattern::Variable { .. } | Pattern::Assign { .. } => return None,
386 Pattern::Int { value } => {
387 let value = value.clone();
388 RuntimeCheckKind::IsInt { value }
389 }
390 Pattern::Float { value } => {
391 let value = value.clone();
392 RuntimeCheckKind::IsFloat { value }
393 }
394 Pattern::String { value } => {
395 let value = value.clone();
396 RuntimeCheckKind::IsString { value }
397 }
398 Pattern::StringPrefix { prefix, .. } => {
399 let prefix = prefix.clone();
400 RuntimeCheckKind::IsStringPrefix { prefix }
401 }
402 Pattern::Tuple { elements } => {
403 let size = elements.len();
404 RuntimeCheckKind::IsTuple { size }
405 }
406 Pattern::Constructor { variant_index, .. } => {
407 let index = *variant_index;
408 RuntimeCheckKind::IsVariant { index }
409 }
410 Pattern::BitArray { value } => {
411 let value = value.clone();
412 RuntimeCheckKind::IsBitArray { value }
413 }
414 Pattern::List { .. } => RuntimeCheckKind::IsNonEmptyList,
415 Pattern::EmptyList => RuntimeCheckKind::IsEmptyList,
416 };
417
418 Some(kind)
419 }
420}
421
422/// This is one of the checks we can take at runtime to decide how to move
423/// forward in the decision tree.
424///
425/// After performing a successful check on a value we will discover something
426/// about its shape: it might be an int, an variant of a custom type, ...
427/// Some values (like variants and lists) might hold onto additional data we
428/// will have to pattern match on: in order to do that we need a name to refer
429/// to those new variables we've discovered after performing a check. That's
430/// what `args` is for.
431///
432/// Let's have a look at an example. Imagine we have a pattern like this one:
433/// `a is Wibble(1, _, [])`; after performing a runtime check to make sure `a`
434/// is indeed a `Wibble`, we'll need to perform additional checks on it's
435/// arguments: that pattern will be replaced by three new ones `a0 is 1`,
436/// `a1 is _` and `a2 is []`. Those new variables are the `args`.
437///
438#[derive(Clone, Debug)]
439pub struct RuntimeCheck {
440 kind: RuntimeCheckKind,
441 args: Vec<Variable>,
442}
443
444#[derive(Eq, PartialEq, Clone, Hash, Debug)]
445pub enum RuntimeCheckKind {
446 IsInt { value: EcoString },
447 IsFloat { value: EcoString },
448 IsString { value: EcoString },
449 IsStringPrefix { prefix: EcoString },
450 IsTuple { size: usize },
451 IsBitArray { value: EcoString },
452 IsVariant { index: usize },
453 IsEmptyList,
454 IsNonEmptyList,
455}
456
457impl RuntimeCheck {
458 fn is_empty_list() -> RuntimeCheck {
459 RuntimeCheck {
460 kind: RuntimeCheckKind::IsEmptyList,
461 args: vec![],
462 }
463 }
464}
465
466/// A variable that can be matched on in a branch.
467///
468#[derive(Eq, PartialEq, Clone, Debug)]
469pub struct Variable {
470 id: usize,
471 type_: Arc<Type>,
472}
473
474impl Variable {
475 fn new(id: usize, type_: Arc<Type>) -> Self {
476 Self { id, type_ }
477 }
478}
479
480#[derive(Debug)]
481/// Different types need to be handled differently when compiling a case expression
482/// into a decision tree. There's some types that have infinite matching patterns
483/// (like ints, strings, ...) and thus will always need a fallback option.
484///
485/// Other types, like custom types, only have a well defined and finite number
486/// of patterns that could match: when matching on a `Result` we know that we can
487/// only have an `Ok(_)` and an `Error(_)`, anything else would end up being a
488/// type error!
489///
490/// So this enum is used to pick the correct strategy to compile a case that's
491/// performing a `PatternCheck` on a variable with a specific type.
492///
493enum BranchMode {
494 /// This covers numbers, functions, variables, bitarrays and strings.
495 ///
496 /// TODO)) In the future it won't be the case: strings and bitarrays will be
497 /// special cased to improve on exhaustiveness checking and to be used for
498 /// code generation.
499 ///
500 Infinite,
501 Tuple {
502 elems: Vec<Arc<Type>>,
503 },
504 List {
505 inner_type: Arc<Type>,
506 },
507 NamedType {
508 constructors: Vec<TypeValueConstructor>,
509 inferred_variant: Option<usize>,
510 },
511}
512
513impl BranchMode {
514 fn is_infinite(&self) -> bool {
515 match self {
516 BranchMode::Infinite => true,
517 BranchMode::Tuple { .. } | BranchMode::List { .. } | BranchMode::NamedType { .. } => {
518 false
519 }
520 }
521 }
522}
523
524impl Variable {
525 fn branch_mode(&self, env: &Environment<'_>) -> BranchMode {
526 match collapse_links(self.type_.clone()).as_ref() {
527 Type::Fn { .. } | Type::Var { .. } => BranchMode::Infinite,
528 Type::Named { module, name, .. }
529 if is_prelude_module(module)
530 && (name == "Int"
531 || name == "Float"
532 || name == "BitArray"
533 || name == "String") =>
534 {
535 BranchMode::Infinite
536 }
537
538 Type::Named {
539 module, name, args, ..
540 } if is_prelude_module(module) && name == "List" => BranchMode::List {
541 inner_type: args.first().expect("list has a type argument").clone(),
542 },
543
544 Type::Tuple { elems } => BranchMode::Tuple {
545 elems: elems.clone(),
546 },
547
548 Type::Named {
549 module,
550 name,
551 args,
552 inferred_variant,
553 ..
554 } => {
555 let constructors = ConstructorSpecialiser::specialise_constructors(
556 env.get_constructors_for_type(module, name)
557 .expect("Custom type variants must exist"),
558 args.as_slice(),
559 );
560
561 let inferred_variant = inferred_variant.map(|i| i as usize);
562 BranchMode::NamedType {
563 constructors,
564 inferred_variant,
565 }
566 }
567 }
568 }
569}
570
571/// This is the decision tree that a pattern matching expression gets turned
572/// into: it's a tree-like structure where each path to a root node contains a
573/// series of checks to perform at runtime to understand if a value matches with
574/// a given pattern.
575///
576pub enum Decision {
577 /// This is the final node of the tree, once we get to this one we know we
578 /// have a body to run because a given pattern matched.
579 ///
580 // todo)) since the tree is not used for code generation, this field is unused.
581 // But it will be useful once we also use this for code gen purposes and not
582 // just for exhaustiveness checking
583 #[allow(dead_code)]
584 Run { body: Body },
585
586 /// We have to make this decision when we run into a branch that also has a
587 /// guard: if it is true we can finally run the body of the branch, stored in
588 /// `if_true`.
589 /// If it is false we might still have to take other decisions and so we might
590 /// have another `DecisionTree` to traverse, stored in `if_false`.
591 ///
592 // todo)) since the tree is not used for code generation, the `guard` and
593 // `if_true` fields are unused.
594 // But they will be useful once we also use this for code gen purposes and not
595 // just for exhaustiveness checking
596 #[allow(dead_code)]
597 Guard {
598 guard: usize,
599 if_true: Body,
600 if_false: Box<Decision>,
601 },
602
603 /// When reaching this node we'll have to see if any of the possible checks
604 /// in `choices` will succeed on `var`. If it does, we know that's the path
605 /// we have to go down to. If none of the checks matches, then we'll have to
606 /// go down the `fallback` branch.
607 ///
608 Switch {
609 var: Variable,
610 choices: Vec<(RuntimeCheck, Box<Decision>)>,
611 fallback: Box<Decision>,
612 },
613
614 /// This is similar to a `Switch` node: we're still picking a possible path
615 /// to follow based on a runtime check. The key difference is that we know
616 /// that one of those is always going to match and so there's no use for a
617 /// fallback branch.
618 ///
619 /// This is used when matching on custom types (and lists!) when we know
620 /// that there's a limited number of choices and exhaustiveness checking
621 /// ensures we'll always deal with all the possible cases.
622 ///
623 ExhaustiveSwitch {
624 var: Variable,
625 choices: Vec<(RuntimeCheck, Box<Decision>)>,
626 },
627
628 /// This is a special node: it represents a missing pattern. If a tree
629 /// contains such a node, then we know that the patterns it was compiled
630 /// from are not exhaustive and the path leading to this node will describe
631 /// what kind of pattern doesn't match!
632 ///
633 Fail,
634}
635
636impl Decision {
637 pub fn run(body: Body) -> Self {
638 Decision::Run { body }
639 }
640
641 pub fn guard(guard: usize, if_true: Body, if_false: Self) -> Self {
642 Decision::Guard {
643 guard,
644 if_true,
645 if_false: Box::new(if_false),
646 }
647 }
648
649 pub fn switch(
650 var: Variable,
651 choices: Vec<(RuntimeCheck, Box<Decision>)>,
652 fallback: Decision,
653 ) -> Self {
654 Self::Switch {
655 var,
656 choices,
657 fallback: Box::new(fallback),
658 }
659 }
660
661 fn exhaustive_switch(var: Variable, choices: Vec<(RuntimeCheck, Box<Decision>)>) -> Decision {
662 Self::ExhaustiveSwitch { var, choices }
663 }
664}
665
666/// The `case` compiler itself (shocking, I know).
667///
668#[derive(Debug)]
669struct Compiler<'a> {
670 environment: &'a Environment<'a>,
671 patterns: Arena<Pattern>,
672 variable_id: usize,
673 diagnostics: Diagnostics,
674}
675
676/// The result of compiling a pattern match expression.
677///
678pub struct Match {
679 pub tree: Decision,
680 pub diagnostics: Diagnostics,
681 pub subject_variables: Vec<Variable>,
682}
683
684/// Whether a clause is reachable, or why it is unreachable.
685///
686#[derive(Debug, Clone, Copy, PartialEq, Eq)]
687pub enum Reachability {
688 Reachable,
689 Unreachable(UnreachableCaseClauseReason),
690}
691
692impl Match {
693 pub fn is_reachable(&self, clause: usize) -> Reachability {
694 if self.diagnostics.reachable.contains(&clause) {
695 Reachability::Reachable
696 } else if self.diagnostics.match_impossible_variants.contains(&clause) {
697 Reachability::Unreachable(UnreachableCaseClauseReason::ImpossibleVariant)
698 } else {
699 Reachability::Unreachable(UnreachableCaseClauseReason::DuplicatePattern)
700 }
701 }
702
703 pub fn missing_patterns(&self, environment: &Environment<'_>) -> Vec<EcoString> {
704 missing_patterns::missing_patterns(self, environment)
705 }
706}
707
708/// A type for storing diagnostics produced by the decision tree compiler.
709///
710#[derive(Debug)]
711pub struct Diagnostics {
712 /// A flag indicating the match is missing one or more pattern.
713 pub missing: bool,
714
715 /// The right-hand sides that are reachable.
716 /// If a right-hand side isn't in this list it means its pattern is
717 /// redundant.
718 pub reachable: Vec<usize>,
719
720 /// Clauses which match on variants of a type which the compiler
721 /// can tell will never be present, due to variant inference.
722 pub match_impossible_variants: Vec<usize>,
723}
724
725impl<'a> Compiler<'a> {
726 fn new(environment: &'a Environment<'a>, variable_id: usize, patterns: Arena<Pattern>) -> Self {
727 Self {
728 environment,
729 patterns,
730 variable_id,
731 diagnostics: Diagnostics {
732 missing: false,
733 reachable: Vec::new(),
734 match_impossible_variants: Vec::new(),
735 },
736 }
737 }
738
739 fn pattern(&self, pattern_id: Id<Pattern>) -> &Pattern {
740 self.patterns.get(pattern_id).expect("unknown pattern id")
741 }
742
743 /// Returns a new fresh variable (i.e. guaranteed to have a unique `variable_id`)
744 /// with the given type.
745 ///
746 fn fresh_variable(&mut self, type_: Arc<Type>) -> Variable {
747 let var = Variable::new(self.variable_id, type_);
748 self.variable_id += 1;
749 var
750 }
751
752 fn mark_as_reached(&mut self, branch: &Branch) {
753 self.diagnostics.reachable.push(branch.branch_index)
754 }
755
756 fn compile(&mut self, mut branches: VecDeque<Branch>) -> Decision {
757 branches
758 .iter_mut()
759 .for_each(|branch| branch.move_unconditional_patterns(self));
760
761 let Some(first_branch) = branches.front() else {
762 // If there's no branches, that means we have a pattern that is not
763 // exhaustive as there's nothing that could match!
764 self.diagnostics.missing = true;
765 return Decision::Fail;
766 };
767
768 self.mark_as_reached(first_branch);
769
770 // In order to compile the branches, we need to pick a `PatternCheck` from
771 // the first branch, and use the variable it's pattern matching on to create
772 // a new node in the tree. All the branches will be split into different
773 // possible paths of this tree.
774 match find_pivot_check(first_branch, &branches) {
775 Some(PatternCheck { var, .. }) => self.split_and_compile_with_pivot_var(var, branches),
776
777 // If the branch has no remaining checks, it means that we've moved all
778 // its variable patterns as assignments into the body and there's no
779 // additional checks remaining. So the only thing left that could result
780 // in the match failing is the additional guard.
781 None => match first_branch.guard {
782 // If there's no guard we're in the following situation:
783 // `∅ -> body`. It means that this branch will always match no
784 // matter what, all the remaining branches are just discarded and
785 // we can produce a terminating node to run the body
786 // unconditionally.
787 None => Decision::run(first_branch.body.clone()),
788 // If we have a guard we're in this scenario:
789 // `∅ if condition -> body`. We can produce a `Guard` node:
790 // if the condition evaluates to `True` we can run its body.
791 // Otherwise, we'll have to keep looking at the remaining branches
792 // to know what to do if this branch doesn't match.
793 Some(guard) => {
794 let if_true = first_branch.body.clone();
795 // All the remaining branches will be compiled and end up
796 // in the path of the tree to choose if the guard is false.
797 let _ = branches.pop_front();
798 let if_false = self.compile(branches);
799 Decision::guard(guard, if_true, if_false)
800 }
801 },
802 }
803 }
804
805 fn split_and_compile_with_pivot_var(
806 &mut self,
807 pivot_var: Variable,
808 branches: VecDeque<Branch>,
809 ) -> Decision {
810 // We first try and come up with a list of all the runtime checks we might
811 // have to perform on the variable at runtime. In most cases it's a limited
812 // number of checks that we know before hand (for example, when matching
813 // on a list, or on a custom type).
814 let branch_mode = pivot_var.branch_mode(self.environment);
815 let known_checks = match &branch_mode {
816 // If the type being matched on is infinite there's no known runtime
817 // check we could come up with in advance. So we'll build them as
818 // we go.
819 BranchMode::Infinite => vec![],
820
821 // If the type is a tuple there's only one runtime check we could
822 // perform that actually makes sense.
823 BranchMode::Tuple { elems } => vec![self.is_tuple_check(elems)],
824
825 // If the type being matched on is a list we know the resulting
826 // decision tree node is only ever going to have two different paths:
827 // one to follow if the list is empty, and one to follow if it's not.
828 BranchMode::List { inner_type } => {
829 vec![
830 RuntimeCheck::is_empty_list(),
831 self.is_list_check(inner_type.clone()),
832 ]
833 }
834
835 // If we know that a specific variant is inferred we will require just
836 // that one and not all the other ones we know for sure are not going to
837 // be there.
838 BranchMode::NamedType {
839 constructors,
840 inferred_variant: Some(index),
841 } => {
842 let constructor = constructors
843 .get(*index)
844 .expect("wrong index for inferred variant");
845 vec![self.is_variant_check(*index, constructor)]
846 }
847
848 // Otherwise we know we'll need a check for each of its possible variants.
849 BranchMode::NamedType { constructors, .. } => constructors
850 .iter()
851 .enumerate()
852 .map(|(index, constructor)| self.is_variant_check(index, constructor))
853 .collect_vec(),
854 };
855
856 // We then split all the branches using these checks and compile the
857 // choices they've been split up into.
858 let mut splitter = BranchSplitter::from_checks(known_checks);
859 self.split_branches(&mut splitter, branches, pivot_var.clone());
860 let choices = splitter
861 .choices
862 .into_iter()
863 .map(|(check, branches)| (check, Box::new(self.compile(branches))))
864 .collect_vec();
865
866 if branch_mode.is_infinite() {
867 // If the branching is infinite, that means we always need to also have
868 // a fallback (imagine you're pattern matching on an `Int` and put no
869 // `_` at the end of the case expression).
870 let fallback = self.compile(splitter.fallback);
871 Decision::switch(pivot_var, choices, fallback)
872 } else {
873 // Otherwise we know that one of the possible runtime checks is always
874 // going to succeed and there's no need to also have a fallback branch.
875 Decision::exhaustive_switch(pivot_var, choices)
876 }
877 }
878
879 fn split_branches(
880 &mut self,
881 splitter: &mut BranchSplitter,
882 branches: VecDeque<Branch>,
883 pivot_var: Variable,
884 ) {
885 for mut branch in branches {
886 let Some(pattern_check) = branch.pop_check_on_var(&pivot_var) else {
887 // If the branch doesn't perform any check on the pivot variable, it means
888 // it could still match no matter what shape `pivot_var` has. So we must
889 // add it as a fallback branch, that is a branch that is still relevant
890 // for all possible paths in the decision tree.
891 splitter.add_fallback_branch(branch);
892 continue;
893 };
894
895 // If it does check the same variable, we know that this branch is only relevant
896 // for some specific shape of `pivot_var`, determined by the runtime check that
897 // it is performing.
898 let kind = pattern_check
899 .to_runtime_check_kind(self)
900 .expect("no var patterns left");
901
902 // We now replace the pattern check we've just removed with the new ones we might
903 // have discovered.
904 //
905 // This is a tricky part, so let's have a look at an example: let's say this is
906 // the pattern check `a is Wibble(1, _, [])`.
907 // After making the runtime check that `a` is indeed a `Wibble` we're still
908 // left with many things to consider! We'll need to also make sure that `a`'s
909 // fields match with the respective patterns `1`, `_` and `[]`.
910 // So we would have to add new pattern checks to this branch:
911 // `a_0 is 1`, `a_1 is _` and `a_2 is []` (where `a_n` are fresh names we use
912 // to refer to `a`'s fields).
913 let args_patterns = self.pattern(pattern_check.pattern).inner_patterns();
914 let args = match splitter.get_overlapping_runtime_check(&kind) {
915 Some(RuntimeCheck { args, .. }) => args,
916 None => vec![],
917 };
918
919 (args.clone().into_iter().zip(args_patterns))
920 .map(|(arg, pattern)| PatternCheck::new(arg, pattern))
921 .for_each(|check| branch.add_check(check));
922
923 splitter.add_checked_branch(RuntimeCheck { kind, args }, branch);
924 }
925 }
926
927 /// Builds an `IsVariant` runtime check, coming up with new fresh variable names
928 /// for its arguments.
929 ///
930 fn is_variant_check(
931 &mut self,
932 index: usize,
933 constructor: &TypeValueConstructor,
934 ) -> RuntimeCheck {
935 RuntimeCheck {
936 kind: RuntimeCheckKind::IsVariant { index },
937 args: constructor
938 .parameters
939 .iter()
940 .map(|p| p.type_.clone())
941 .map(|type_| self.fresh_variable(type_))
942 .collect_vec(),
943 }
944 }
945
946 /// Builds an `IsNonEmptyList` runtime check, coming up with fresh variable
947 /// names for its arguments.
948 ///
949 fn is_list_check(&mut self, inner_type: Arc<Type>) -> RuntimeCheck {
950 RuntimeCheck {
951 kind: RuntimeCheckKind::IsNonEmptyList,
952 args: vec![
953 self.fresh_variable(inner_type.clone()),
954 self.fresh_variable(Arc::new(Type::list(inner_type))),
955 ],
956 }
957 }
958
959 /// Builds an `IsTuple` runtime check, coming up with fresh variable
960 /// names for its arguments.
961 ///
962 fn is_tuple_check(&mut self, elems: &Vec<Arc<Type>>) -> RuntimeCheck {
963 RuntimeCheck {
964 kind: RuntimeCheckKind::IsTuple { size: elems.len() },
965 args: elems
966 .iter()
967 .map(|type_| self.fresh_variable(type_.clone()))
968 .collect_vec(),
969 }
970 }
971}
972
973/// Returns a pattern check from `first_branch` to be used as a pivot to split all
974/// the `branches`.
975///
976fn find_pivot_check(first_branch: &Branch, branches: &VecDeque<Branch>) -> Option<PatternCheck> {
977 // To try and minimise code duplication, we use the following heuristic: we
978 // choose the check matching on the variable that is referenced the most
979 // across all checks in all branches.
980 let mut var_references = HashMap::new();
981 for branch in branches {
982 for check in &branch.checks {
983 let _ = var_references
984 .entry(check.var.id)
985 .and_modify(|references| *references += 1)
986 .or_insert(0);
987 }
988 }
989
990 first_branch
991 .checks
992 .iter()
993 .max_by_key(|check| var_references.get(&check.var.id).cloned().unwrap_or(0))
994 .cloned()
995}
996
997/// A handy data structure we use to split branches in different possible paths
998/// based on a check.
999///
1000struct BranchSplitter {
1001 pub choices: Vec<(RuntimeCheck, VecDeque<Branch>)>,
1002 pub fallback: VecDeque<Branch>,
1003 /// This is used to allow quickly looking up a choice in the `choices`
1004 /// vector, without loosing track of the checks' order.
1005 indices: HashMap<RuntimeCheckKind, usize>,
1006}
1007
1008impl BranchSplitter {
1009 /// Creates a new splitter with the given starting checks.
1010 ///
1011 fn from_checks(checks: Vec<RuntimeCheck>) -> Self {
1012 let mut choices = Vec::with_capacity(checks.len());
1013 let mut indices = HashMap::new();
1014
1015 for (index, RuntimeCheck { kind, args }) in checks.into_iter().enumerate() {
1016 let _ = indices.insert(kind.clone(), index);
1017 choices.push((RuntimeCheck { kind, args }, VecDeque::new()));
1018 }
1019
1020 Self {
1021 fallback: VecDeque::new(),
1022 choices,
1023 indices,
1024 }
1025 }
1026
1027 /// Add a fallback branch: this is a branch that is relevant to all possible
1028 /// paths as it could still run, no matter the result of any of the `Check`s
1029 /// we've stored!
1030 ///
1031 fn add_fallback_branch(&mut self, branch: Branch) {
1032 self.choices
1033 .iter_mut()
1034 .for_each(|(_, branches)| branches.push_back(branch.clone()));
1035 self.fallback.push_back(branch);
1036 }
1037
1038 /// Add a branch that we know will only ever run if the `check` is true.
1039 ///
1040 fn add_checked_branch(&mut self, check: RuntimeCheck, branch: Branch) {
1041 match self.indices.get(&check.kind) {
1042 Some(index) => {
1043 let (_, branches) = self
1044 .choices
1045 .get_mut(*index)
1046 .expect("check to already be a choice");
1047 branches.push_back(branch);
1048 }
1049
1050 None => {
1051 let _ = self.indices.insert(check.kind.clone(), self.choices.len());
1052 let mut branches = self.fallback.clone();
1053 branches.push_back(branch);
1054 self.choices.push((check, branches));
1055 }
1056 }
1057 }
1058
1059 fn get_overlapping_runtime_check(&self, kind: &RuntimeCheckKind) -> Option<RuntimeCheck> {
1060 let index = self.indices.get(kind)?;
1061 let (runtime_check, _) = self.choices.get(*index)?;
1062 Some(runtime_check.clone())
1063 }
1064}
1065
1066pub struct ConstructorSpecialiser {
1067 specialised_types: HashMap<u64, Arc<Type>>,
1068}
1069
1070impl ConstructorSpecialiser {
1071 fn specialise_constructors(
1072 constructors: &TypeVariantConstructors,
1073 type_arguments: &[Arc<Type>],
1074 ) -> Vec<TypeValueConstructor> {
1075 let specialiser = Self::new(constructors.type_parameters_ids.as_slice(), type_arguments);
1076 constructors
1077 .variants
1078 .iter()
1079 .map(|v| specialiser.specialise_type_value_constructor(v))
1080 .collect_vec()
1081 }
1082
1083 fn new(parameters: &[u64], type_arguments: &[Arc<Type>]) -> Self {
1084 let specialised_types = parameters
1085 .iter()
1086 .copied()
1087 .zip(type_arguments.iter().cloned())
1088 .collect();
1089 Self { specialised_types }
1090 }
1091
1092 fn specialise_type_value_constructor(&self, v: &TypeValueConstructor) -> TypeValueConstructor {
1093 let TypeValueConstructor {
1094 name,
1095 parameters,
1096 documentation,
1097 } = v;
1098 let parameters = parameters
1099 .iter()
1100 .map(|p| TypeValueConstructorField {
1101 type_: self.specialise_type(p.type_.as_ref()),
1102 label: p.label.clone(),
1103 })
1104 .collect_vec();
1105 TypeValueConstructor {
1106 name: name.clone(),
1107 parameters,
1108 documentation: documentation.clone(),
1109 }
1110 }
1111
1112 fn specialise_type(&self, type_: &Type) -> Arc<Type> {
1113 Arc::new(match type_ {
1114 Type::Named {
1115 publicity,
1116 package,
1117 module,
1118 name,
1119 args,
1120 inferred_variant,
1121 } => Type::Named {
1122 publicity: *publicity,
1123 package: package.clone(),
1124 module: module.clone(),
1125 name: name.clone(),
1126 args: args.iter().map(|a| self.specialise_type(a)).collect(),
1127 inferred_variant: *inferred_variant,
1128 },
1129
1130 Type::Fn { args, retrn } => Type::Fn {
1131 args: args.iter().map(|a| self.specialise_type(a)).collect(),
1132 retrn: retrn.clone(),
1133 },
1134
1135 Type::Var { type_ } => Type::Var {
1136 type_: Arc::new(RefCell::new(self.specialise_var(type_))),
1137 },
1138
1139 Type::Tuple { elems } => Type::Tuple {
1140 elems: elems.iter().map(|e| self.specialise_type(e)).collect(),
1141 },
1142 })
1143 }
1144
1145 fn specialise_var(&self, type_: &RefCell<TypeVar>) -> TypeVar {
1146 match &*type_.borrow() {
1147 TypeVar::Unbound { id } => TypeVar::Unbound { id: *id },
1148
1149 TypeVar::Link { type_ } => TypeVar::Link {
1150 type_: self.specialise_type(type_.as_ref()),
1151 },
1152
1153 TypeVar::Generic { id } => match self.specialised_types.get(id) {
1154 Some(type_) => TypeVar::Link {
1155 type_: type_.clone(),
1156 },
1157 None => TypeVar::Generic { id: *id },
1158 },
1159 }
1160 }
1161}
1162
1163/// Intermiate data structure that's used to set up everything that's needed by
1164/// the pattern matching compiler and get a case expression ready to be compiled,
1165/// while hiding the intricacies of handling an arena to record different patterns.
1166///
1167pub struct CaseToCompile {
1168 patterns: Arena<Pattern>,
1169 branches: Vec<Branch>,
1170 subject_variables: Vec<Variable>,
1171 variable_id: usize,
1172}
1173
1174impl CaseToCompile {
1175 pub fn new(subject_types: &[Arc<Type>]) -> Self {
1176 let mut variable_id = 0;
1177 let subject_variables = subject_types
1178 .iter()
1179 .map(|type_| {
1180 let id = variable_id;
1181 variable_id += 1;
1182 Variable::new(id, type_.clone())
1183 })
1184 .collect_vec();
1185
1186 Self {
1187 patterns: Arena::new(),
1188 branches: vec![],
1189 subject_variables,
1190 variable_id,
1191 }
1192 }
1193
1194 /// Registers a `TypedClause` as one of the branches to be compiled.
1195 ///
1196 /// If you don't have a clause and just have a simple `TypedPattern` you want
1197 /// to generate a decision tree for you can use `add_pattern`.
1198 ///
1199 pub fn add_clause(&mut self, branch: &TypedClause) {
1200 let branch_index = self.branches.len();
1201 let all_patterns =
1202 std::iter::once(&branch.pattern).chain(branch.alternative_patterns.iter());
1203
1204 for (alternative_index, patterns) in all_patterns.enumerate() {
1205 let mut checks = Vec::with_capacity(patterns.len());
1206
1207 // We're doing the zipping ourselves instead of using iters.zip as the
1208 // borrow checker would complain and the only workaround would be to
1209 // allocate an entire new vector each time.
1210 for i in 0..patterns.len() {
1211 let pattern = self.register(patterns.get(i).expect("pattern index"));
1212 let var = self
1213 .subject_variables
1214 .get(i)
1215 .expect("wrong number of subjects")
1216 .clone();
1217
1218 checks.push(PatternCheck::new(var, pattern))
1219 }
1220
1221 let has_guard = branch.guard.is_some();
1222 let branch = Branch::new(branch_index, alternative_index, checks, has_guard);
1223 self.branches.push(branch);
1224 }
1225 }
1226
1227 /// Add a single pattern as a branch to be compiled.
1228 ///
1229 /// This is useful in case one wants to check exhaustiveness of a single
1230 /// pattern without having a fully fledged `TypedClause` to pass to the `add_clause`
1231 /// method. For example, in `let` destructurings.
1232 ///
1233 pub fn add_pattern(&mut self, pattern: &TypedPattern) {
1234 let branch_index = self.branches.len();
1235 let pattern = self.register(pattern);
1236 let var = self
1237 .subject_variables
1238 .first()
1239 .expect("wrong number of subject variables for pattern")
1240 .clone();
1241 let checks = vec![PatternCheck::new(var, pattern)];
1242 let branch = Branch::new(branch_index, 0, checks, false);
1243 self.branches.push(branch);
1244 }
1245
1246 pub fn compile(self, env: &Environment<'_>) -> Match {
1247 let mut compiler = Compiler::new(env, self.variable_id, self.patterns);
1248
1249 let decision = if self.branches.is_empty() {
1250 let var = self
1251 .subject_variables
1252 .first()
1253 .expect("case with no subjects")
1254 .clone();
1255
1256 compiler.split_and_compile_with_pivot_var(var, VecDeque::new())
1257 } else {
1258 compiler.compile(self.branches.into())
1259 };
1260
1261 Match {
1262 tree: decision,
1263 diagnostics: compiler.diagnostics,
1264 subject_variables: self.subject_variables,
1265 }
1266 }
1267
1268 /// Registers a typed pattern (and all its sub-patterns) into this
1269 /// `CaseToCompile`'s pattern arena, returning an id to get the pattern back.
1270 ///
1271 fn register(&mut self, pattern: &TypedPattern) -> Id<Pattern> {
1272 match pattern {
1273 TypedPattern::Invalid { .. } => self.insert(Pattern::Discard),
1274 TypedPattern::Discard { .. } => self.insert(Pattern::Discard),
1275
1276 TypedPattern::Int { value, .. } => {
1277 let value = value.clone();
1278 self.insert(Pattern::Int { value })
1279 }
1280
1281 TypedPattern::Float { value, .. } => {
1282 let value = value.clone();
1283 self.insert(Pattern::Float { value })
1284 }
1285
1286 TypedPattern::String { value, .. } => {
1287 let value = value.clone();
1288 self.insert(Pattern::String { value })
1289 }
1290
1291 TypedPattern::Variable { name, .. } => {
1292 let name = name.clone();
1293 self.insert(Pattern::Variable { name })
1294 }
1295
1296 TypedPattern::Assign { name, pattern, .. } => {
1297 let name = name.clone();
1298 let pattern = self.register(pattern);
1299 self.insert(Pattern::Assign { name, pattern })
1300 }
1301
1302 TypedPattern::Tuple { elems, .. } => {
1303 let elements = elems.iter().map(|elem| self.register(elem)).collect_vec();
1304 self.insert(Pattern::Tuple { elements })
1305 }
1306
1307 TypedPattern::List { elements, tail, .. } => {
1308 let mut list = match tail {
1309 Some(tail) => self.register(tail),
1310 None => self.insert(Pattern::EmptyList),
1311 };
1312 for element in elements.iter().rev() {
1313 let first = self.register(element);
1314 list = self.insert(Pattern::List { first, rest: list });
1315 }
1316 list
1317 }
1318
1319 TypedPattern::Constructor {
1320 arguments,
1321 constructor,
1322 ..
1323 } => {
1324 let variant_index =
1325 constructor.expect_ref("must be inferred").constructor_index as usize;
1326 let arguments = arguments
1327 .iter()
1328 .map(|argument| self.register(&argument.value))
1329 .collect_vec();
1330 self.insert(Pattern::Constructor {
1331 variant_index,
1332 arguments,
1333 })
1334 }
1335
1336 TypedPattern::BitArray { location, .. } => {
1337 // TODO: in future support bit strings fully and check the
1338 // exhaustiveness of their segment patterns.
1339 // For now we use the location to give each bit string a pattern
1340 // a unique value.
1341 self.insert(Pattern::BitArray {
1342 value: format!("{}:{}", location.start, location.end).into(),
1343 })
1344 }
1345
1346 TypedPattern::StringPrefix {
1347 left_side_string,
1348 right_side_assignment,
1349 ..
1350 } => {
1351 let prefix = left_side_string.clone();
1352 let rest_pattern = match right_side_assignment {
1353 AssignName::Variable(name) => Pattern::Variable { name: name.clone() },
1354 AssignName::Discard(_) => Pattern::Discard,
1355 };
1356 let rest = self.insert(rest_pattern);
1357 self.insert(Pattern::StringPrefix { prefix, rest })
1358 }
1359
1360 TypedPattern::VarUsage { .. } => {
1361 unreachable!("Cannot convert VarUsage to exhaustiveness pattern")
1362 }
1363 }
1364 }
1365
1366 fn insert(&mut self, pattern: Pattern) -> Id<Pattern> {
1367 self.patterns.alloc(pattern)
1368 }
1369}