nandi.uk
Fork of daniellemaywood.uk/gleam — Wasm codegen work
63 kB
1692 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//! ```text
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//! > ```text
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, string,
86 },
87};
88use ecow::EcoString;
89use id_arena::{Arena, Id};
90use itertools::Itertools;
91use radix_trie::{Trie, TrieCommon};
92use std::{
93 cell::RefCell,
94 collections::{HashMap, HashSet, VecDeque},
95 hash::Hash,
96 sync::Arc,
97};
98
99/// A single branch composing a `case` expression to be compiled into a decision
100/// tree.
101///
102/// As shown in the module documentation, branches are a bit different from the
103/// usual branches we see in Gleam's case expressions. Each branch can perform
104/// multiple checks (each on a different variable, which appears in the check
105/// itself!):
106///
107/// ```text
108/// a is Some, b is 1 if condition -> todo
109/// ─┬─────── ─┬──── ─┬────────── ─┬──
110/// │ │ │ ╰── body: an arbitrary expression
111/// │ │ ╰── guard: an additional boolean condition
112/// ╰──────────┴── checks: check that a variable matches with a pattern
113/// ─┬────────────────────────────────────
114/// ╰── branch: one of the branches making up a pattern matching expression
115/// ```
116///
117/// As shown here a branch can also optionally include a guard with a boolean
118/// condition and is followed by a body that is to be executed if all the checks
119/// match (and the guard evaluates to true).
120///
121#[derive(Clone, Eq, PartialEq, Debug)]
122struct Branch {
123 /// Each branch is identified by a numeric index, so we can nicely
124 /// report errors once we find something's wrong with a branch.
125 ///
126 clause_index: usize,
127
128 /// Each alternative pattern in an alternative pattern matching (e.g.
129 /// `one | two | three -> todo`) gets turned into its own branch in this
130 /// internal representation. So we also keep track of the index of the
131 /// alternative this comes from (0 being the first one and so on...)
132 ///
133 alternative_index: usize,
134 checks: Vec<PatternCheck>,
135 guard: Option<usize>,
136 body: Body,
137}
138
139impl Branch {
140 fn new(
141 clause_index: usize,
142 alternative_index: usize,
143 checks: Vec<PatternCheck>,
144 has_guard: bool,
145 ) -> Self {
146 Self {
147 clause_index,
148 alternative_index,
149 checks,
150 guard: if has_guard { Some(clause_index) } else { None },
151 body: Body::new(clause_index),
152 }
153 }
154
155 /// Removes and returns a `PatternCheck` on the given variable from this
156 /// branch.
157 ///
158 fn pop_check_on_var(&mut self, var: &Variable) -> Option<PatternCheck> {
159 let index = self.checks.iter().position(|check| check.var == *var)?;
160 Some(self.checks.remove(index))
161 }
162
163 fn add_check(&mut self, check: PatternCheck) {
164 self.checks.push(check);
165 }
166
167 /// To simplify compiling the pattern we can get rid of all catch-all
168 /// patterns that are guaranteed to match by turning those into assignments.
169 ///
170 /// What does this look like in practice? Let's go over an example.
171 /// Let's say we have this case to compile:
172 ///
173 /// ```gleam
174 /// case a {
175 /// Some(1) -> Some(2)
176 /// otherwise -> otherwise
177 /// }
178 /// ```
179 ///
180 /// In our internal representation this would become:
181 ///
182 /// ```text
183 /// case {
184 /// a is Some(1) -> Some(2)
185 /// a is otherwise -> otherwise
186 /// ─┬────────────
187 /// ╰── `a` will always match with this "catch all" variable pattern
188 /// }
189 /// ```
190 ///
191 /// Focusing on the last branch, we can remove that check that always matches
192 /// by keeping track in its body of the correspondence. So it would end up
193 /// looking like this:
194 ///
195 /// ```text
196 /// case {
197 /// a is Some(1) -> Some(2)
198 /// ∅ -> {
199 /// ┬
200 /// ╰── This represents the fact that there's no checks left for this branch!
201 /// So we can make another observation: if there's no checks left in a
202 /// branch we know it will always match and we can produce a leaf in the
203 /// decision tree (there's an exception when we have guards, but we'll
204 /// get to it later)!
205 ///
206 /// let otherwise = a
207 /// ─┬───────────────
208 /// ╰── And now we can understand what those `bindings` at the start of
209 /// a body are: as we remove variable patterns, we will rewrite those
210 /// as assignments at the top of the body of the corresponding branch.
211 ///
212 /// otherwise
213 /// }
214 /// }
215 /// ```
216 ///
217 fn move_unconditional_patterns(&mut self, compiler: &Compiler<'_>) {
218 self.checks.retain_mut(|check| {
219 loop {
220 match compiler.pattern(check.pattern) {
221 // Variable patterns always match, so we move those to the body
222 // and remove them from the branch's checks.
223 Pattern::Variable { name } => {
224 self.body.assign(name.clone(), check.var.clone());
225 return false;
226 }
227 // A discard pattern always matches, but since the value is not
228 // used we can just remove it without even adding an assignment
229 // to the body!
230 Pattern::Discard => return false,
231 // Assigns are kind of special: they get turned into assignments
232 // (shocking) but then we can't discard the pattern they wrap.
233 // So we replace the assignment pattern with the one it's wrapping
234 // and try again.
235 Pattern::Assign { name, pattern } => {
236 self.body.assign(name.clone(), check.var.clone());
237 check.pattern = *pattern;
238 continue;
239 }
240 // All other patterns are not unconditional, so we just keep them.
241 _ => return true,
242 }
243 }
244 });
245 }
246}
247
248/// The body of a branch. It always starts with a series of variable assignments
249/// in the form: `let a = b`. As explained in `move_unconditional_patterns`' doc,
250/// each body starts with a series of assignments we keep track of as we're
251/// compiling each branch.
252///
253#[derive(Clone, Eq, PartialEq, Debug)]
254pub struct Body {
255 /// Any variables to bind before running the code.
256 ///
257 /// The tuples are in the form `(name, value)`, so `(wibble, var)`
258 /// corresponds to `let wibble = var`.
259 ///
260 bindings: Vec<(EcoString, Variable)>,
261
262 /// The index of the clause in the case expression that should be run.
263 ///
264 clause_index: usize,
265}
266
267impl Body {
268 pub fn new(clause_index: usize) -> Self {
269 Self {
270 bindings: vec![],
271 clause_index,
272 }
273 }
274
275 /// Adds a new assignment to the body, binding `let var = value`
276 ///
277 pub fn assign(&mut self, var: EcoString, value: Variable) {
278 self.bindings.push((var, value));
279 }
280}
281
282/// A user defined pattern such as `Some((x, 10))`.
283/// This is a bit simpler than the full fledged `TypedPattern` used for code analysis
284/// and only focuses on the relevant bits needed to perform exhaustiveness checking
285/// and code generation.
286///
287/// Using this simplified version of a pattern for the case compiler makes it a
288/// whole lot simpler and more efficient (patterns will have to be cloned, so
289/// we use an arena to allocate those and only store ids to make this operation
290/// extra cheap).
291///
292#[derive(Clone, Eq, PartialEq, Debug)]
293pub enum Pattern {
294 Discard,
295 Int {
296 value: EcoString,
297 },
298 Float {
299 value: EcoString,
300 },
301 String {
302 value: EcoString,
303 },
304 StringPrefix {
305 prefix: EcoString,
306 rest_pattern: Id<Pattern>,
307 },
308 Assign {
309 name: EcoString,
310 pattern: Id<Pattern>,
311 },
312 Variable {
313 name: EcoString,
314 },
315 Tuple {
316 elems_patterns: Vec<Id<Pattern>>,
317 },
318 Variant {
319 index: usize,
320 args_patterns: Vec<Id<Pattern>>,
321 },
322 List {
323 first_pattern: Id<Pattern>,
324 rest_pattern: Id<Pattern>,
325 },
326 EmptyList,
327 // TODO: Compile the matching within the bit strings
328 BitArray {
329 value: EcoString,
330 },
331}
332
333impl Pattern {
334 /// Each pattern (with a couple exceptions) can be turned into a
335 /// simpler `RuntimeCheck`: that is a check that can be performed at runtime
336 /// to make sure a `PatternCheck` can succeed on a specific value.
337 ///
338 fn to_runtime_check_kind(&self) -> Option<RuntimeCheckKind> {
339 let kind = match self {
340 // These patterns are unconditional: they will always match and be moved
341 // out of a branch's checks. So there's no corresponding runtime check
342 // we can perform for them.
343 Pattern::Discard | Pattern::Variable { .. } | Pattern::Assign { .. } => return None,
344 Pattern::Int { value } => RuntimeCheckKind::Int {
345 value: value.clone(),
346 },
347 Pattern::Float { value } => RuntimeCheckKind::Float {
348 value: value.clone(),
349 },
350 Pattern::String { value } => RuntimeCheckKind::String {
351 value: value.clone(),
352 },
353 Pattern::StringPrefix { prefix, .. } => RuntimeCheckKind::StringPrefix {
354 prefix: prefix.clone(),
355 },
356 Pattern::Tuple { elems_patterns } => RuntimeCheckKind::Tuple {
357 size: elems_patterns.len(),
358 },
359 Pattern::Variant { index, .. } => RuntimeCheckKind::Variant { index: *index },
360 Pattern::BitArray { value } => RuntimeCheckKind::BitArray {
361 value: value.clone(),
362 },
363 Pattern::List { .. } => RuntimeCheckKind::NonEmptyList,
364 Pattern::EmptyList => RuntimeCheckKind::EmptyList,
365 };
366
367 Some(kind)
368 }
369
370 fn is_matching_on_unreachable_variant(&self, branch_mode: &BranchMode) -> bool {
371 match (self, branch_mode) {
372 (
373 Self::Variant { index, .. },
374 BranchMode::NamedType {
375 inferred_variant: Some(variant),
376 ..
377 },
378 ) if index != variant => true,
379 _ => false,
380 }
381 }
382}
383
384/// A single check making up a branch, checking that a variable matches with a
385/// given pattern. For example, the following branch has 2 checks:
386///
387/// ```text
388/// a is Some, b is 1 -> todo
389/// ┬ ─┬──
390/// │ ╰── This is the pattern being checked
391/// ╰── This is the variable being pattern matched on
392/// ─┬─────── ─┬────
393/// ╰─────────┴── Two `PatternCheck`s
394/// ```
395///
396#[derive(Clone, Eq, PartialEq, Debug)]
397struct PatternCheck {
398 var: Variable,
399 pattern: Id<Pattern>,
400}
401
402/// This is one of the checks we can take at runtime to decide how to move
403/// forward in the decision tree.
404///
405/// After performing a successful check on a value we will discover something
406/// about its shape: it might be an int, an variant of a custom type, ...
407/// Some values (like variants and lists) might hold onto additional data we
408/// will have to pattern match on: in order to do that we need a name to refer
409/// to those new variables we've discovered after performing a check. That's
410/// what `args` is for.
411///
412/// Let's have a look at an example. Imagine we have a pattern like this one:
413/// `a is Wibble(1, _, [])`; after performing a runtime check to make sure `a`
414/// is indeed a `Wibble`, we'll need to perform additional checks on it's
415/// arguments: that pattern will be replaced by three new ones `a0 is 1`,
416/// `a1 is _` and `a2 is []`. Those new variables are the `args`.
417///
418#[derive(Clone, Debug)]
419pub enum RuntimeCheck {
420 Int {
421 value: EcoString,
422 },
423 Float {
424 value: EcoString,
425 },
426 String {
427 value: EcoString,
428 },
429 StringPrefix {
430 prefix: EcoString,
431 rest_arg: Variable,
432 },
433 Tuple {
434 size: usize,
435 args: Vec<Variable>,
436 },
437 BitArray {
438 value: EcoString,
439 },
440 Variant {
441 index: usize,
442 args: Vec<Variable>,
443 },
444 EmptyList,
445 List {
446 first_arg: Variable,
447 rest_arg: Variable,
448 },
449}
450
451impl RuntimeCheck {
452 fn kind(&self) -> RuntimeCheckKind {
453 match self {
454 RuntimeCheck::Int { value } => RuntimeCheckKind::Int {
455 value: value.clone(),
456 },
457 RuntimeCheck::Float { value } => RuntimeCheckKind::Float {
458 value: value.clone(),
459 },
460 RuntimeCheck::String { value } => RuntimeCheckKind::String {
461 value: value.clone(),
462 },
463 RuntimeCheck::StringPrefix {
464 prefix,
465 rest_arg: _,
466 } => RuntimeCheckKind::StringPrefix {
467 prefix: prefix.clone(),
468 },
469 RuntimeCheck::Tuple { size, args: _ } => RuntimeCheckKind::Tuple { size: *size },
470 RuntimeCheck::BitArray { value } => RuntimeCheckKind::BitArray {
471 value: value.clone(),
472 },
473 RuntimeCheck::Variant { index, args: _ } => RuntimeCheckKind::Variant { index: *index },
474 RuntimeCheck::EmptyList => RuntimeCheckKind::EmptyList,
475 RuntimeCheck::List {
476 first_arg: _,
477 rest_arg: _,
478 } => RuntimeCheckKind::NonEmptyList,
479 }
480 }
481}
482
483#[derive(Eq, PartialEq, Clone, Hash, Debug)]
484pub enum RuntimeCheckKind {
485 Int { value: EcoString },
486 Float { value: EcoString },
487 String { value: EcoString },
488 StringPrefix { prefix: EcoString },
489 Tuple { size: usize },
490 BitArray { value: EcoString },
491 Variant { index: usize },
492 EmptyList,
493 NonEmptyList,
494}
495
496/// A variable that can be matched on in a branch.
497///
498#[derive(Eq, PartialEq, Clone, Debug)]
499pub struct Variable {
500 id: usize,
501 type_: Arc<Type>,
502}
503
504impl Variable {
505 fn new(id: usize, type_: Arc<Type>) -> Self {
506 Self { id, type_ }
507 }
508
509 fn is(&self, pattern: Id<Pattern>) -> PatternCheck {
510 PatternCheck {
511 var: self.clone(),
512 pattern,
513 }
514 }
515}
516
517#[derive(Debug)]
518/// Different types need to be handled differently when compiling a case expression
519/// into a decision tree. There's some types that have infinite matching patterns
520/// (like ints, strings, ...) and thus will always need a fallback option.
521///
522/// Other types, like custom types, only have a well defined and finite number
523/// of patterns that could match: when matching on a `Result` we know that we can
524/// only have an `Ok(_)` and an `Error(_)`, anything else would end up being a
525/// type error!
526///
527/// So this enum is used to pick the correct strategy to compile a case that's
528/// performing a `PatternCheck` on a variable with a specific type.
529///
530enum BranchMode {
531 /// This covers numbers, functions, variables, bitarrays and strings.
532 ///
533 /// TODO)) In the future it won't be the case: strings and bitarrays will be
534 /// special cased to improve on exhaustiveness checking and to be used for
535 /// code generation.
536 ///
537 Infinite,
538 Tuple {
539 elems: Vec<Arc<Type>>,
540 },
541 List {
542 inner_type: Arc<Type>,
543 },
544 NamedType {
545 constructors: Vec<TypeValueConstructor>,
546 inferred_variant: Option<usize>,
547 },
548}
549
550impl BranchMode {
551 fn needs_fallback(&self) -> bool {
552 match self {
553 BranchMode::Infinite => true,
554 BranchMode::Tuple { .. } | BranchMode::List { .. } | BranchMode::NamedType { .. } => {
555 false
556 }
557 }
558 }
559}
560
561impl Variable {
562 fn branch_mode(&self, env: &Environment<'_>) -> BranchMode {
563 match collapse_links(self.type_.clone()).as_ref() {
564 Type::Fn { .. } | Type::Var { .. } => BranchMode::Infinite,
565 Type::Named { module, name, .. }
566 if is_prelude_module(module)
567 && (name == "Int"
568 || name == "Float"
569 || name == "BitArray"
570 || name == "String") =>
571 {
572 BranchMode::Infinite
573 }
574
575 Type::Named {
576 module, name, args, ..
577 } if is_prelude_module(module) && name == "List" => BranchMode::List {
578 inner_type: args.first().expect("list has a type argument").clone(),
579 },
580
581 Type::Tuple { elems } => BranchMode::Tuple {
582 elems: elems.clone(),
583 },
584
585 Type::Named {
586 module,
587 name,
588 args,
589 inferred_variant,
590 ..
591 } => {
592 let constructors = ConstructorSpecialiser::specialise_constructors(
593 env.get_constructors_for_type(module, name)
594 .expect("Custom type variants must exist"),
595 args.as_slice(),
596 );
597
598 let inferred_variant = inferred_variant.map(|i| i as usize);
599 BranchMode::NamedType {
600 constructors,
601 inferred_variant,
602 }
603 }
604 }
605 }
606}
607
608/// This is the decision tree that a pattern matching expression gets turned
609/// into: it's a tree-like structure where each path to a root node contains a
610/// series of checks to perform at runtime to understand if a value matches with
611/// a given pattern.
612///
613pub enum Decision {
614 /// This is the final node of the tree, once we get to this one we know we
615 /// have a body to run because a given pattern matched.
616 ///
617 Run {
618 // todo)) since the tree is not used for code generation, this field is unused.
619 // But it will be useful once we also use this for code gen purposes and not
620 // just for exhaustiveness checking
621 #[allow(dead_code)]
622 body: Body,
623 },
624
625 /// We have to make this decision when we run into a branch that also has a
626 /// guard: if it is true we can finally run the body of the branch, stored in
627 /// `if_true`.
628 /// If it is false we might still have to take other decisions and so we might
629 /// have another `DecisionTree` to traverse, stored in `if_false`.
630 ///
631 Guard {
632 // todo)) since the tree is not used for code generation, the `guard` and
633 // `if_true` fields are unused.
634 // But they will be useful once we also use this for code gen purposes and not
635 // just for exhaustiveness checking
636 #[allow(dead_code)]
637 guard: usize,
638 #[allow(dead_code)]
639 if_true: Body,
640 if_false: Box<Decision>,
641 },
642
643 /// When reaching this node we'll have to see if any of the possible checks
644 /// in `choices` will succeed on `var`. If it does, we know that's the path
645 /// we have to go down to. If none of the checks matches, then we'll have to
646 /// go down the `fallback` branch.
647 ///
648 Switch {
649 var: Variable,
650 choices: Vec<(RuntimeCheck, Box<Decision>)>,
651 fallback: Box<Decision>,
652 },
653
654 /// This is similar to a `Switch` node: we're still picking a possible path
655 /// to follow based on a runtime check. The key difference is that we know
656 /// that one of those is always going to match and so there's no use for a
657 /// fallback branch.
658 ///
659 /// This is used when matching on custom types (and lists!) when we know
660 /// that there's a limited number of choices and exhaustiveness checking
661 /// ensures we'll always deal with all the possible cases.
662 ///
663 ExhaustiveSwitch {
664 var: Variable,
665 choices: Vec<(RuntimeCheck, Box<Decision>)>,
666 },
667
668 /// This is a special node: it represents a missing pattern. If a tree
669 /// contains such a node, then we know that the patterns it was compiled
670 /// from are not exhaustive and the path leading to this node will describe
671 /// what kind of pattern doesn't match!
672 ///
673 Fail,
674}
675
676impl Decision {
677 pub fn run(body: Body) -> Self {
678 Decision::Run { body }
679 }
680
681 pub fn guard(guard: usize, if_true: Body, if_false: Self) -> Self {
682 Decision::Guard {
683 guard,
684 if_true,
685 if_false: Box::new(if_false),
686 }
687 }
688
689 pub fn switch(
690 var: Variable,
691 choices: Vec<(RuntimeCheck, Box<Decision>)>,
692 fallback: Decision,
693 ) -> Self {
694 Self::Switch {
695 var,
696 choices,
697 fallback: Box::new(fallback),
698 }
699 }
700
701 fn exhaustive_switch(var: Variable, choices: Vec<(RuntimeCheck, Box<Decision>)>) -> Decision {
702 Self::ExhaustiveSwitch { var, choices }
703 }
704}
705
706/// The `case` compiler itself (shocking, I know).
707///
708#[derive(Debug)]
709struct Compiler<'a> {
710 environment: &'a Environment<'a>,
711 patterns: Arena<Pattern>,
712 variable_id: usize,
713 diagnostics: Diagnostics,
714}
715
716/// The result of compiling a pattern match expression.
717///
718pub struct Match {
719 pub tree: Decision,
720 pub diagnostics: Diagnostics,
721 pub subject_variables: Vec<Variable>,
722}
723
724/// Whether a clause is reachable, or why it is unreachable.
725///
726#[derive(Debug, Clone, Copy, PartialEq, Eq)]
727pub enum Reachability {
728 Reachable,
729 Unreachable(UnreachableCaseClauseReason),
730}
731
732impl Match {
733 pub fn is_reachable(&self, clause: usize) -> Reachability {
734 if self.diagnostics.reachable.contains(&clause) {
735 Reachability::Reachable
736 } else if self.diagnostics.match_impossible_variants.contains(&clause) {
737 Reachability::Unreachable(UnreachableCaseClauseReason::ImpossibleVariant)
738 } else {
739 Reachability::Unreachable(UnreachableCaseClauseReason::DuplicatePattern)
740 }
741 }
742
743 pub fn missing_patterns(&self, environment: &Environment<'_>) -> Vec<EcoString> {
744 missing_patterns::missing_patterns(self, environment)
745 }
746}
747
748/// A type for storing diagnostics produced by the decision tree compiler.
749///
750#[derive(Debug)]
751pub struct Diagnostics {
752 /// A flag indicating the match is missing one or more pattern.
753 pub missing: bool,
754
755 /// The right-hand sides that are reachable.
756 /// If a right-hand side isn't in this list it means its pattern is
757 /// redundant.
758 pub reachable: HashSet<usize>,
759
760 /// Clauses which match on variants of a type which the compiler
761 /// can tell will never be present, due to variant inference.
762 pub match_impossible_variants: HashSet<usize>,
763}
764
765impl<'a> Compiler<'a> {
766 fn new(environment: &'a Environment<'a>, variable_id: usize, patterns: Arena<Pattern>) -> Self {
767 Self {
768 environment,
769 patterns,
770 variable_id,
771 diagnostics: Diagnostics {
772 missing: false,
773 reachable: HashSet::new(),
774 match_impossible_variants: HashSet::new(),
775 },
776 }
777 }
778
779 fn pattern(&self, pattern_id: Id<Pattern>) -> &Pattern {
780 self.patterns.get(pattern_id).expect("unknown pattern id")
781 }
782
783 /// Returns a new fresh variable (i.e. guaranteed to have a unique `variable_id`)
784 /// with the given type.
785 ///
786 fn fresh_variable(&mut self, type_: Arc<Type>) -> Variable {
787 let var = Variable::new(self.variable_id, type_);
788 self.variable_id += 1;
789 var
790 }
791
792 fn mark_as_reached(&mut self, branch: &Branch) {
793 let _ = self.diagnostics.reachable.insert(branch.clause_index);
794 }
795
796 fn mark_as_matching_impossible_variant(&mut self, branch: &Branch) {
797 let _ = self.diagnostics.reachable.remove(&branch.clause_index);
798 let _ = self
799 .diagnostics
800 .match_impossible_variants
801 .insert(branch.clause_index);
802 }
803
804 fn compile(&mut self, mut branches: VecDeque<Branch>) -> Decision {
805 branches
806 .iter_mut()
807 .for_each(|branch| branch.move_unconditional_patterns(self));
808
809 let Some(first_branch) = branches.front() else {
810 // If there's no branches, that means we have a pattern that is not
811 // exhaustive as there's nothing that could match!
812 self.diagnostics.missing = true;
813 return Decision::Fail;
814 };
815
816 self.mark_as_reached(first_branch);
817
818 // In order to compile the branches, we need to pick a `PatternCheck` from
819 // the first branch, and use the variable it's pattern matching on to create
820 // a new node in the tree. All the branches will be split into different
821 // possible paths of this tree.
822 match find_pivot_check(first_branch, &branches) {
823 Some(PatternCheck { var, .. }) => self.split_and_compile_with_pivot_var(var, branches),
824
825 // If the branch has no remaining checks, it means that we've moved all
826 // its variable patterns as assignments into the body and there's no
827 // additional checks remaining. So the only thing left that could result
828 // in the match failing is the additional guard.
829 None => match first_branch.guard {
830 // If there's no guard we're in the following situation:
831 // `∅ -> body`. It means that this branch will always match no
832 // matter what, all the remaining branches are just discarded and
833 // we can produce a terminating node to run the body
834 // unconditionally.
835 None => Decision::run(first_branch.body.clone()),
836 // If we have a guard we're in this scenario:
837 // `∅ if condition -> body`. We can produce a `Guard` node:
838 // if the condition evaluates to `True` we can run its body.
839 // Otherwise, we'll have to keep looking at the remaining branches
840 // to know what to do if this branch doesn't match.
841 Some(guard) => {
842 let if_true = first_branch.body.clone();
843 // All the remaining branches will be compiled and end up
844 // in the path of the tree to choose if the guard is false.
845 let _ = branches.pop_front();
846 let if_false = self.compile(branches);
847 Decision::guard(guard, if_true, if_false)
848 }
849 },
850 }
851 }
852
853 fn split_and_compile_with_pivot_var(
854 &mut self,
855 pivot_var: Variable,
856 branches: VecDeque<Branch>,
857 ) -> Decision {
858 // We first try and come up with a list of all the runtime checks we might
859 // have to perform on the variable at runtime. In most cases it's a limited
860 // number of checks that we know before hand (for example, when matching
861 // on a list, or on a custom type).
862 let branch_mode = pivot_var.branch_mode(self.environment);
863 let known_checks = match &branch_mode {
864 // If the type being matched on is infinite there's no known runtime
865 // check we could come up with in advance. So we'll build them as
866 // we go.
867 BranchMode::Infinite => vec![],
868
869 // If the type is a tuple there's only one runtime check we could
870 // perform that actually makes sense.
871 BranchMode::Tuple { elems } => vec![self.is_tuple_check(elems)],
872
873 // If the type being matched on is a list we know the resulting
874 // decision tree node is only ever going to have two different paths:
875 // one to follow if the list is empty, and one to follow if it's not.
876 BranchMode::List { inner_type } => {
877 vec![
878 RuntimeCheck::EmptyList,
879 self.is_list_check(inner_type.clone()),
880 ]
881 }
882
883 // If we know that a specific variant is inferred we will require just
884 // that one and not all the other ones we know for sure are not going to
885 // be there.
886 BranchMode::NamedType {
887 constructors,
888 inferred_variant: Some(index),
889 } => {
890 let constructor = constructors
891 .get(*index)
892 .expect("wrong index for inferred variant");
893 vec![self.is_variant_check(*index, constructor)]
894 }
895
896 // Otherwise we know we'll need a check for each of its possible variants.
897 BranchMode::NamedType { constructors, .. } => constructors
898 .iter()
899 .enumerate()
900 .map(|(index, constructor)| self.is_variant_check(index, constructor))
901 .collect_vec(),
902 };
903
904 // We then split all the branches using these checks and compile the
905 // choices they've been split up into.
906 let mut splitter = BranchSplitter::from_checks(known_checks);
907 self.split_branches(&mut splitter, branches, pivot_var.clone(), &branch_mode);
908 let choices = splitter
909 .choices
910 .into_iter()
911 .map(|(check, branches)| (check, Box::new(self.compile(branches))))
912 .collect_vec();
913
914 if branch_mode.needs_fallback() {
915 // If the branching is infinite, that means we always need to also have
916 // a fallback (imagine you're pattern matching on an `Int` and put no
917 // `_` at the end of the case expression).
918 let fallback = self.compile(splitter.fallback);
919 Decision::switch(pivot_var, choices, fallback)
920 } else if choices.is_empty() {
921 // If the branching doesn't need any fallback but we ended up with no
922 // checks it means we're trying to pattern match on an external type
923 // but haven't provided a catch-all case.
924 // That's never going to match, so we produce a failure node.
925 self.diagnostics.missing = true;
926 Decision::Fail
927 } else {
928 // Otherwise we know that one of the possible runtime checks is always
929 // going to succeed and there's no need to also have a fallback branch.
930 Decision::exhaustive_switch(pivot_var, choices)
931 }
932 }
933
934 fn split_branches(
935 &mut self,
936 splitter: &mut BranchSplitter,
937 branches: VecDeque<Branch>,
938 pivot_var: Variable,
939 branch_mode: &BranchMode,
940 ) {
941 for mut branch in branches {
942 let Some(pattern_check) = branch.pop_check_on_var(&pivot_var) else {
943 // If the branch doesn't perform any check on the pivot variable, it means
944 // it could still match no matter what shape `pivot_var` has. So we must
945 // add it as a fallback branch, that is a branch that is still relevant
946 // for all possible paths in the decision tree.
947 splitter.add_fallback_branch(branch);
948 continue;
949 };
950
951 let checked_pattern = self.pattern(pattern_check.pattern).clone();
952 if checked_pattern.is_matching_on_unreachable_variant(branch_mode) {
953 self.mark_as_matching_impossible_variant(&branch);
954 continue;
955 }
956
957 splitter.add_checked_branch(checked_pattern, branch, branch_mode, self);
958 }
959 }
960
961 /// Turns a `RuntimeCheckKind` into a new `RuntimeCheck` by coming up with
962 /// the needed new fresh variables.
963 /// All the type information needed to create these variables is in the
964 /// `branch_mode` arg.
965 ///
966 fn fresh_runtime_check(
967 &mut self,
968 kind: RuntimeCheckKind,
969 branch_mode: &BranchMode,
970 ) -> RuntimeCheck {
971 match (kind, branch_mode) {
972 (RuntimeCheckKind::Int { value }, _) => RuntimeCheck::Int {
973 value: value.clone(),
974 },
975 (RuntimeCheckKind::Float { value }, _) => RuntimeCheck::Float {
976 value: value.clone(),
977 },
978 (RuntimeCheckKind::String { value }, _) => RuntimeCheck::String {
979 value: value.clone(),
980 },
981 (RuntimeCheckKind::BitArray { value }, _) => RuntimeCheck::BitArray {
982 value: value.clone(),
983 },
984 (RuntimeCheckKind::StringPrefix { prefix }, _) => RuntimeCheck::StringPrefix {
985 prefix: prefix.clone(),
986 rest_arg: self.fresh_variable(string()),
987 },
988 (RuntimeCheckKind::Tuple { .. }, BranchMode::Tuple { elems }) => {
989 self.is_tuple_check(elems)
990 }
991 (RuntimeCheckKind::Variant { index }, BranchMode::NamedType { constructors, .. }) => {
992 self.is_variant_check(
993 index,
994 constructors.get(index).expect("unknown variant index"),
995 )
996 }
997 (RuntimeCheckKind::EmptyList, _) => RuntimeCheck::EmptyList,
998 (RuntimeCheckKind::NonEmptyList, BranchMode::List { inner_type }) => {
999 self.is_list_check(inner_type.clone())
1000 }
1001 (_, _) => unreachable!("type checking should make this impossible"),
1002 }
1003 }
1004
1005 /// Comes up with new pattern cecks that have to match in case a given
1006 /// runtime check succeeds for the given pattern.
1007 ///
1008 /// Let's make an example: when we have a pattern - say `a is Wibble(1, [])` -
1009 /// we come up with a runtime check to perform on it. For our example the
1010 /// runtime check is to make sure that `a` is indeed a `Wibble` variant.
1011 /// However, after successfully performing that check we're left with much to
1012 /// do! We know that `a` is `Wibble` but now we'll have to make sure that its
1013 /// inner arguments also match the given patterns. So the new additional checks
1014 /// we have to add are `a0 is 1, a1 is []` (where `a0` and `a1` are the fresh
1015 /// variable names we use to refer to the constructor's arguments).
1016 ///
1017 fn new_checks(
1018 &mut self,
1019 for_pattern: &Pattern,
1020 after_succeding_check: &RuntimeCheck,
1021 ) -> Vec<PatternCheck> {
1022 match (for_pattern, after_succeding_check) {
1023 // These patterns never result in adding new checks. After a runtime
1024 // check matches on them there's nothing else to discover.
1025 (
1026 Pattern::Discard
1027 | Pattern::Assign { .. }
1028 | Pattern::Variable { .. }
1029 | Pattern::Int { .. }
1030 | Pattern::Float { .. }
1031 | Pattern::BitArray { .. }
1032 | Pattern::EmptyList,
1033 _,
1034 )
1035 | (Pattern::String { .. }, RuntimeCheck::String { .. }) => vec![],
1036
1037 // After making sure a value is not an empty list we'll have to perform
1038 // additional checks on its first item and on the tail.
1039 (
1040 Pattern::List {
1041 first_pattern,
1042 rest_pattern,
1043 },
1044 RuntimeCheck::List {
1045 first_arg,
1046 rest_arg,
1047 },
1048 ) => vec![first_arg.is(*first_pattern), rest_arg.is(*rest_pattern)],
1049
1050 // After making sure a value is a specific variant we'll have to check each
1051 // of its arguments respects the given patterns (as shown in the doc example for
1052 // this function!)
1053 (Pattern::Variant { args_patterns, .. }, RuntimeCheck::Variant { args, .. }) => {
1054 (args.iter().zip(args_patterns))
1055 .map(|(arg, pattern)| arg.is(*pattern))
1056 .collect_vec()
1057 }
1058
1059 // Tuples are exactly the same as variants: after making sure we're dealing with
1060 // a tuple, we will have to check that each of its elements matches the given
1061 // pattern: `a is #(1, _)` will result in the following checks
1062 // `a0 is 1, a1 is _` (where `a0` and `a1` are fresh variable names we use to
1063 // refer to each of the tuple's elements).
1064 (Pattern::Tuple { elems_patterns }, RuntimeCheck::Tuple { args, .. }) => {
1065 (args.iter().zip(elems_patterns))
1066 .map(|(arg, pattern)| arg.is(*pattern))
1067 .collect_vec()
1068 }
1069
1070 // Strings are quite fun: if we've checked at runtime a string starts with a given
1071 // prefix and we want to check that it's some overlapping literal value we'll still
1072 // have some amount of work to perform.
1073 //
1074 // Let's have a look at an example: the pattern we care about is `a is "wibble"`
1075 // and we've just successfully ran the runtime check for `a is "wib" <> rest`.
1076 // So we know the string already starts with `"wib"` what we have to check now
1077 // is that the remaining part `rest` is `"ble"`.
1078 (
1079 Pattern::String { value },
1080 RuntimeCheck::StringPrefix {
1081 prefix, rest_arg, ..
1082 },
1083 ) => {
1084 let remaining = value.strip_prefix(prefix.as_str()).unwrap_or(value);
1085 vec![rest_arg.is(self.string_pattern(remaining))]
1086 }
1087
1088 // String prefixes are similar to strings, but a bit more involved. Let's say we're
1089 // checking the pattern:
1090 //
1091 // ```text
1092 // "wibblest" <> rest1
1093 // ─┬────────
1094 // ╰── We will refer to this as `prefix1`
1095 // ```
1096 //
1097 // And we know that the following overlapping runtime check has already succeeded:
1098 //
1099 // ```text
1100 // "wibble" <> rest0
1101 // ─┬──────
1102 // ╰── We will refer to this as `prefix0`
1103 // ```
1104 //
1105 // We're lucky because we now know quite a bit about the shape of the string. Since
1106 // we know it already starts with `"wibble"` we can just check that the remaining
1107 // part after that starts with the missing part of the prefix:
1108 // `prefix0 is "st" <> rest1`.
1109 (
1110 Pattern::StringPrefix {
1111 prefix: prefix1,
1112 rest_pattern: rest1,
1113 },
1114 RuntimeCheck::StringPrefix {
1115 prefix: prefix0,
1116 rest_arg: rest0,
1117 },
1118 ) => {
1119 let remaining = prefix1.strip_prefix(prefix0.as_str()).unwrap_or(prefix1);
1120 vec![rest0.is(self.string_prefix_pattern(remaining, *rest1))]
1121 }
1122
1123 (_, _) => unreachable!("invalid pattern overlapping"),
1124 }
1125 }
1126
1127 /// Builds an `IsVariant` runtime check, coming up with new fresh variable names
1128 /// for its arguments.
1129 ///
1130 fn is_variant_check(
1131 &mut self,
1132 index: usize,
1133 constructor: &TypeValueConstructor,
1134 ) -> RuntimeCheck {
1135 RuntimeCheck::Variant {
1136 index,
1137 args: constructor
1138 .parameters
1139 .iter()
1140 .map(|p| p.type_.clone())
1141 .map(|type_| self.fresh_variable(type_))
1142 .collect_vec(),
1143 }
1144 }
1145
1146 /// Builds an `IsNonEmptyList` runtime check, coming up with fresh variable
1147 /// names for its arguments.
1148 ///
1149 fn is_list_check(&mut self, inner_type: Arc<Type>) -> RuntimeCheck {
1150 RuntimeCheck::List {
1151 first_arg: self.fresh_variable(inner_type.clone()),
1152 rest_arg: self.fresh_variable(Arc::new(Type::list(inner_type))),
1153 }
1154 }
1155
1156 /// Builds an `IsTuple` runtime check, coming up with fresh variable
1157 /// names for its arguments.
1158 ///
1159 fn is_tuple_check(&mut self, elems: &[Arc<Type>]) -> RuntimeCheck {
1160 RuntimeCheck::Tuple {
1161 size: elems.len(),
1162 args: elems
1163 .iter()
1164 .map(|type_| self.fresh_variable(type_.clone()))
1165 .collect_vec(),
1166 }
1167 }
1168
1169 /// Allocates a new `StringPattern` with the given value.
1170 ///
1171 fn string_pattern(&mut self, value: &str) -> Id<Pattern> {
1172 self.patterns.alloc(Pattern::String {
1173 value: EcoString::from(value),
1174 })
1175 }
1176
1177 /// Allocates a new `StringPrefix` pattern with the given prefix and pattern
1178 /// for the rest of the string.
1179 ///
1180 fn string_prefix_pattern(&mut self, prefix: &str, rest_pattern: Id<Pattern>) -> Id<Pattern> {
1181 self.patterns.alloc(Pattern::StringPrefix {
1182 prefix: EcoString::from(prefix),
1183 rest_pattern,
1184 })
1185 }
1186}
1187
1188/// Returns a pattern check from `first_branch` to be used as a pivot to split all
1189/// the `branches`.
1190///
1191fn find_pivot_check(first_branch: &Branch, branches: &VecDeque<Branch>) -> Option<PatternCheck> {
1192 // To try and minimise code duplication, we use the following heuristic: we
1193 // choose the check matching on the variable that is referenced the most
1194 // across all checks in all branches.
1195 let mut var_references = HashMap::new();
1196 for branch in branches {
1197 for check in &branch.checks {
1198 let _ = var_references
1199 .entry(check.var.id)
1200 .and_modify(|references| *references += 1)
1201 .or_insert(0);
1202 }
1203 }
1204
1205 first_branch
1206 .checks
1207 .iter()
1208 .max_by_key(|check| var_references.get(&check.var.id).cloned().unwrap_or(0))
1209 .cloned()
1210}
1211
1212/// A handy data structure we use to split branches in different possible paths
1213/// based on a check.
1214///
1215struct BranchSplitter {
1216 pub choices: Vec<(RuntimeCheck, VecDeque<Branch>)>,
1217 pub fallback: VecDeque<Branch>,
1218 /// This is used to allow quickly looking up a choice in the `choices`
1219 /// vector, without loosing track of the checks' order.
1220 indices: HashMap<RuntimeCheckKind, usize>,
1221
1222 /// This is used to store the indices of just the prefix checks as they have
1223 /// different rules from all the other `RuntimeCheckKinds` whose indices are
1224 /// instead stored in the `indices` field.
1225 ///
1226 /// We discuss this in more detail in the `index_of_overlapping_runtime_check`
1227 /// function!
1228 prefix_indices: Trie<String, usize>,
1229}
1230
1231impl BranchSplitter {
1232 /// Creates a new splitter with the given starting checks.
1233 ///
1234 fn from_checks(checks: Vec<RuntimeCheck>) -> Self {
1235 let mut choices = Vec::with_capacity(checks.len());
1236 let mut indices = HashMap::new();
1237
1238 for (index, runtime_check) in checks.into_iter().enumerate() {
1239 let _ = indices.insert(runtime_check.kind(), index);
1240 choices.push((runtime_check, VecDeque::new()));
1241 }
1242
1243 Self {
1244 fallback: VecDeque::new(),
1245 choices,
1246 indices,
1247 prefix_indices: Trie::new(),
1248 }
1249 }
1250
1251 /// Add a fallback branch: this is a branch that is relevant to all possible
1252 /// paths as it could still run, no matter the result of any of the `Check`s
1253 /// we've stored!
1254 ///
1255 fn add_fallback_branch(&mut self, branch: Branch) {
1256 self.choices
1257 .iter_mut()
1258 .for_each(|(_, branches)| branches.push_back(branch.clone()));
1259 self.fallback.push_back(branch);
1260 }
1261
1262 /// Given a branch and the pattern its using to check on the pivot variable,
1263 /// adds it to the paths where it's relevant, that is where we know from
1264 /// previous checks that this pattern has a chance of matching.
1265 ///
1266 fn add_checked_branch(
1267 &mut self,
1268 pattern: Pattern,
1269 branch: Branch,
1270 branch_mode: &BranchMode,
1271 compiler: &mut Compiler<'_>,
1272 ) {
1273 let kind = pattern
1274 .to_runtime_check_kind()
1275 .expect("no unconditional patterns left");
1276
1277 let indices_of_overlapping_checks = self.indices_of_overlapping_checks(&kind);
1278 if indices_of_overlapping_checks.is_empty() {
1279 // This is a new choice we haven't yet discovered as it is not overlapping
1280 // with any of the existing ones. So we add it as a possible new path
1281 // we might have to go down to in the decision tree.
1282 self.save_index_of_new_choice(kind.clone());
1283 let mut branches = self.fallback.clone();
1284 branches.push_back(branch);
1285 let check = compiler.fresh_runtime_check(kind, branch_mode);
1286 self.choices.push((check, branches));
1287 } else {
1288 // Otherwise, we know that the check for this branch overlaps with
1289 // (possibly more than one) existing checks and so is relevant only
1290 // as part of those existing paths.
1291 // We'll add the branch with its newly discovered checks only to those
1292 // paths.
1293 for index in indices_of_overlapping_checks {
1294 let (overlapping_check, branches) = self
1295 .choices
1296 .get_mut(index)
1297 .expect("check to already be a choice");
1298
1299 let mut branch = branch.clone();
1300 for new_check in compiler.new_checks(&pattern, overlapping_check) {
1301 branch.add_check(new_check);
1302 }
1303 branches.push_back(branch);
1304 }
1305 }
1306 }
1307
1308 fn save_index_of_new_choice(&mut self, kind: RuntimeCheckKind) {
1309 let _ = match kind {
1310 RuntimeCheckKind::Int { .. }
1311 | RuntimeCheckKind::Float { .. }
1312 | RuntimeCheckKind::String { .. }
1313 | RuntimeCheckKind::Tuple { .. }
1314 | RuntimeCheckKind::BitArray { .. }
1315 | RuntimeCheckKind::Variant { .. }
1316 | RuntimeCheckKind::EmptyList
1317 | RuntimeCheckKind::NonEmptyList => self.indices.insert(kind, self.choices.len()),
1318
1319 RuntimeCheckKind::StringPrefix { prefix } => self
1320 .prefix_indices
1321 .insert(prefix.to_string(), self.choices.len()),
1322 };
1323 }
1324
1325 fn indices_of_overlapping_checks(&self, kind: &RuntimeCheckKind) -> Vec<usize> {
1326 match kind {
1327 // All these checks will only overlap with a check that is exactly the
1328 // same, so we just look up their index in the `indices` map using the
1329 // kind as the lookup.
1330 RuntimeCheckKind::Int { .. }
1331 | RuntimeCheckKind::Float { .. }
1332 | RuntimeCheckKind::Tuple { .. }
1333 | RuntimeCheckKind::BitArray { .. }
1334 | RuntimeCheckKind::Variant { .. }
1335 | RuntimeCheckKind::EmptyList
1336 | RuntimeCheckKind::NonEmptyList => {
1337 self.indices.get(kind).cloned().into_iter().collect_vec()
1338 }
1339
1340 // String patterns are a bit more tricky as they might end up overlapping
1341 // even if they're not exactly the same kind of check! Let's have a look
1342 // at an example. Say we're compiling these branches:
1343 //
1344 // ```
1345 // a is "wibble" <> rest -> todo
1346 // a is "wibbler" <> rest -> todo
1347 // ```
1348 //
1349 // We use the first (and only) check in the first branch as the pivot and
1350 // now we have to decide where to put the next branch. Is it matching with
1351 // the first one or completely unrelated?
1352 // Since `"wibbler"` starts with `"wibble"` we know it's overlapping and
1353 // it cannot possibly match if the previous one doesn't!
1354 //
1355 // So when we find a `String`/`StringPrefix` pattern we look for a prefix
1356 // among the ones we have discovered so far that could match with it.
1357 // That is, we look for a prefix of the pattern we're checking in the prefix
1358 // trie.
1359 RuntimeCheckKind::StringPrefix { prefix: value } => {
1360 ancestors_values(&self.prefix_indices, value).collect_vec()
1361 }
1362
1363 // Strings are almost exactly the same, except they could also have an exact
1364 // match with other string patterns. So a string pattern could overlap with
1365 // another string pattern (if they're matching on the same value), or with
1366 // one or more string prefix patterns with a matching prefix.
1367 RuntimeCheckKind::String { value } => {
1368 let first_index = self.indices.get(kind).cloned();
1369 first_index
1370 .into_iter()
1371 .chain(ancestors_values(&self.prefix_indices, value))
1372 .collect_vec()
1373 }
1374 }
1375 }
1376}
1377
1378fn ancestors_values(trie: &Trie<String, usize>, key: &str) -> impl Iterator<Item = usize> {
1379 trie.get_ancestor(key)
1380 .into_iter()
1381 .flat_map(|ancestor| ancestor.values().copied())
1382}
1383
1384pub struct ConstructorSpecialiser {
1385 specialised_types: HashMap<u64, Arc<Type>>,
1386}
1387
1388impl ConstructorSpecialiser {
1389 fn specialise_constructors(
1390 constructors: &TypeVariantConstructors,
1391 type_arguments: &[Arc<Type>],
1392 ) -> Vec<TypeValueConstructor> {
1393 let specialiser = Self::new(constructors.type_parameters_ids.as_slice(), type_arguments);
1394 constructors
1395 .variants
1396 .iter()
1397 .map(|v| specialiser.specialise_type_value_constructor(v))
1398 .collect_vec()
1399 }
1400
1401 fn new(parameters: &[u64], type_arguments: &[Arc<Type>]) -> Self {
1402 let specialised_types = parameters
1403 .iter()
1404 .copied()
1405 .zip(type_arguments.iter().cloned())
1406 .collect();
1407 Self { specialised_types }
1408 }
1409
1410 fn specialise_type_value_constructor(&self, v: &TypeValueConstructor) -> TypeValueConstructor {
1411 let TypeValueConstructor {
1412 name,
1413 parameters,
1414 documentation,
1415 } = v;
1416 let parameters = parameters
1417 .iter()
1418 .map(|p| TypeValueConstructorField {
1419 type_: self.specialise_type(p.type_.as_ref()),
1420 label: p.label.clone(),
1421 })
1422 .collect_vec();
1423 TypeValueConstructor {
1424 name: name.clone(),
1425 parameters,
1426 documentation: documentation.clone(),
1427 }
1428 }
1429
1430 fn specialise_type(&self, type_: &Type) -> Arc<Type> {
1431 Arc::new(match type_ {
1432 Type::Named {
1433 publicity,
1434 package,
1435 module,
1436 name,
1437 args,
1438 inferred_variant,
1439 } => Type::Named {
1440 publicity: *publicity,
1441 package: package.clone(),
1442 module: module.clone(),
1443 name: name.clone(),
1444 args: args.iter().map(|a| self.specialise_type(a)).collect(),
1445 inferred_variant: *inferred_variant,
1446 },
1447
1448 Type::Fn { args, retrn } => Type::Fn {
1449 args: args.iter().map(|a| self.specialise_type(a)).collect(),
1450 retrn: retrn.clone(),
1451 },
1452
1453 Type::Var { type_ } => Type::Var {
1454 type_: Arc::new(RefCell::new(self.specialise_var(type_))),
1455 },
1456
1457 Type::Tuple { elems } => Type::Tuple {
1458 elems: elems.iter().map(|e| self.specialise_type(e)).collect(),
1459 },
1460 })
1461 }
1462
1463 fn specialise_var(&self, type_: &RefCell<TypeVar>) -> TypeVar {
1464 match &*type_.borrow() {
1465 TypeVar::Unbound { id } => TypeVar::Unbound { id: *id },
1466
1467 TypeVar::Link { type_ } => TypeVar::Link {
1468 type_: self.specialise_type(type_.as_ref()),
1469 },
1470
1471 TypeVar::Generic { id } => match self.specialised_types.get(id) {
1472 Some(type_) => TypeVar::Link {
1473 type_: type_.clone(),
1474 },
1475 None => TypeVar::Generic { id: *id },
1476 },
1477 }
1478 }
1479}
1480
1481/// Intermiate data structure that's used to set up everything that's needed by
1482/// the pattern matching compiler and get a case expression ready to be compiled,
1483/// while hiding the intricacies of handling an arena to record different patterns.
1484///
1485pub struct CaseToCompile {
1486 patterns: Arena<Pattern>,
1487 branches: Vec<Branch>,
1488 subject_variables: Vec<Variable>,
1489 /// The number of clauses in this case to compile.
1490 number_of_clauses: usize,
1491 variable_id: usize,
1492}
1493
1494impl CaseToCompile {
1495 pub fn new(subject_types: &[Arc<Type>]) -> Self {
1496 let mut variable_id = 0;
1497 let subject_variables = subject_types
1498 .iter()
1499 .map(|type_| {
1500 let id = variable_id;
1501 variable_id += 1;
1502 Variable::new(id, type_.clone())
1503 })
1504 .collect_vec();
1505
1506 Self {
1507 patterns: Arena::new(),
1508 branches: vec![],
1509 number_of_clauses: 0,
1510 subject_variables,
1511 variable_id,
1512 }
1513 }
1514
1515 /// Registers a `TypedClause` as one of the branches to be compiled.
1516 ///
1517 /// If you don't have a clause and just have a simple `TypedPattern` you want
1518 /// to generate a decision tree for you can use `add_pattern`.
1519 ///
1520 pub fn add_clause(&mut self, branch: &TypedClause) {
1521 let all_patterns =
1522 std::iter::once(&branch.pattern).chain(branch.alternative_patterns.iter());
1523
1524 for (alternative_index, patterns) in all_patterns.enumerate() {
1525 let mut checks = Vec::with_capacity(patterns.len());
1526
1527 // We're doing the zipping ourselves instead of using iters.zip as the
1528 // borrow checker would complain and the only workaround would be to
1529 // allocate an entire new vector each time.
1530 for i in 0..patterns.len() {
1531 let pattern = self.register(patterns.get(i).expect("pattern index"));
1532 let var = self
1533 .subject_variables
1534 .get(i)
1535 .expect("wrong number of subjects");
1536 checks.push(var.is(pattern))
1537 }
1538
1539 let has_guard = branch.guard.is_some();
1540 let branch = Branch::new(self.number_of_clauses, alternative_index, checks, has_guard);
1541 self.branches.push(branch);
1542 }
1543
1544 self.number_of_clauses += 1;
1545 }
1546
1547 /// Add a single pattern as a branch to be compiled.
1548 ///
1549 /// This is useful in case one wants to check exhaustiveness of a single
1550 /// pattern without having a fully fledged `TypedClause` to pass to the `add_clause`
1551 /// method. For example, in `let` destructurings.
1552 ///
1553 pub fn add_pattern(&mut self, pattern: &TypedPattern) {
1554 let pattern = self.register(pattern);
1555 let var = self
1556 .subject_variables
1557 .first()
1558 .expect("wrong number of subject variables for pattern");
1559 let branch = Branch::new(self.number_of_clauses, 0, vec![var.is(pattern)], false);
1560 self.number_of_clauses += 1;
1561 self.branches.push(branch);
1562 }
1563
1564 pub fn compile(self, env: &Environment<'_>) -> Match {
1565 let mut compiler = Compiler::new(env, self.variable_id, self.patterns);
1566
1567 let decision = if self.branches.is_empty() {
1568 let var = self
1569 .subject_variables
1570 .first()
1571 .expect("case with no subjects")
1572 .clone();
1573
1574 compiler.split_and_compile_with_pivot_var(var, VecDeque::new())
1575 } else {
1576 compiler.compile(self.branches.into())
1577 };
1578
1579 Match {
1580 tree: decision,
1581 diagnostics: compiler.diagnostics,
1582 subject_variables: self.subject_variables,
1583 }
1584 }
1585
1586 /// Registers a typed pattern (and all its sub-patterns) into this
1587 /// `CaseToCompile`'s pattern arena, returning an id to get the pattern back.
1588 ///
1589 fn register(&mut self, pattern: &TypedPattern) -> Id<Pattern> {
1590 match pattern {
1591 TypedPattern::Invalid { .. } => self.insert(Pattern::Discard),
1592 TypedPattern::Discard { .. } => self.insert(Pattern::Discard),
1593
1594 TypedPattern::Int { value, .. } => {
1595 let value = value.clone();
1596 self.insert(Pattern::Int { value })
1597 }
1598
1599 TypedPattern::Float { value, .. } => {
1600 let value = value.clone();
1601 self.insert(Pattern::Float { value })
1602 }
1603
1604 TypedPattern::String { value, .. } => {
1605 let value = value.clone();
1606 self.insert(Pattern::String { value })
1607 }
1608
1609 TypedPattern::Variable { name, .. } => {
1610 let name = name.clone();
1611 self.insert(Pattern::Variable { name })
1612 }
1613
1614 TypedPattern::Assign { name, pattern, .. } => {
1615 let name = name.clone();
1616 let pattern = self.register(pattern);
1617 self.insert(Pattern::Assign { name, pattern })
1618 }
1619
1620 TypedPattern::Tuple { elems, .. } => {
1621 let elems_patterns = elems.iter().map(|elem| self.register(elem)).collect_vec();
1622 self.insert(Pattern::Tuple { elems_patterns })
1623 }
1624
1625 TypedPattern::List { elements, tail, .. } => {
1626 let mut list = match tail {
1627 Some(tail) => self.register(tail),
1628 None => self.insert(Pattern::EmptyList),
1629 };
1630 for element in elements.iter().rev() {
1631 let first_pattern = self.register(element);
1632 list = self.insert(Pattern::List {
1633 first_pattern,
1634 rest_pattern: list,
1635 });
1636 }
1637 list
1638 }
1639
1640 TypedPattern::Constructor {
1641 arguments,
1642 constructor,
1643 ..
1644 } => {
1645 let index = constructor.expect_ref("must be inferred").constructor_index as usize;
1646 let args_patterns = arguments
1647 .iter()
1648 .map(|argument| self.register(&argument.value))
1649 .collect_vec();
1650 self.insert(Pattern::Variant {
1651 index,
1652 args_patterns,
1653 })
1654 }
1655
1656 TypedPattern::BitArray { location, .. } => {
1657 // TODO: in future support bit strings fully and check the
1658 // exhaustiveness of their segment patterns.
1659 // For now we use the location to give each bit string a pattern
1660 // a unique value.
1661 self.insert(Pattern::BitArray {
1662 value: format!("{}:{}", location.start, location.end).into(),
1663 })
1664 }
1665
1666 TypedPattern::StringPrefix {
1667 left_side_string,
1668 right_side_assignment,
1669 ..
1670 } => {
1671 let prefix = left_side_string.clone();
1672 let rest_pattern = match right_side_assignment {
1673 AssignName::Variable(name) => Pattern::Variable { name: name.clone() },
1674 AssignName::Discard(_) => Pattern::Discard,
1675 };
1676 let rest_pattern = self.insert(rest_pattern);
1677 self.insert(Pattern::StringPrefix {
1678 prefix,
1679 rest_pattern,
1680 })
1681 }
1682
1683 TypedPattern::VarUsage { .. } => {
1684 unreachable!("Cannot convert VarUsage to exhaustiveness pattern")
1685 }
1686 }
1687 }
1688
1689 fn insert(&mut self, pattern: Pattern) -> Id<Pattern> {
1690 self.patterns.alloc(pattern)
1691 }
1692}