nandi.uk
Fork of daniellemaywood.uk/gleam — Wasm codegen work
114 kB
3041 lines
1//! An implementation of the algorithm described in:
2//!
3//! - How to compile pattern matching, Jules Jacobs.
4//! <https://julesjacobs.com/notes/patternmatching/patternmatching.pdf>
5//!
6//! - Efficient manipulation of binary data using pattern matching,
7//! Per Gustafsson and Konstantinos Sagonas.
8//! <https://user.it.uu.se/~kostis/Papers/JFP_06.pdf>
9//!
10//! Adapted from Yorick Peterse's implementation at
11//! <https://github.com/yorickpeterse/pattern-matching-in-rust>.
12//! Thank you Yorick!
13//!
14//! > This module comment (and all the following doc comments) are a rough
15//! > explanation. It's great to set some expectations on what to expect from
16//! > the following code and why the data looks the way it does.
17//! > If you want a more detailed explanation, the original paper is a lot more
18//! > detailed!
19//!
20//! A case to be compiled looks a bit different from the case expressions we're
21//! used to in Gleam: instead of having a variable to match on and a series of
22//! branches, a `CaseToCompile` is made up of a series of branches that can each
23//! contain multiple pattern checks. With a psedo-Gleam syntax, this is what it
24//! would look like:
25//!
26//! ```text
27//! case {
28//! a is Some, b is 1, c is _ -> todo
29//! a is wibble -> todo
30//! }
31//! ```
32//!
33//! > You may wonder, why are we writing branches like this? Usually a case
34//! > expression matches on a single variable and each branch refers to it. For
35//! > example in gleam you'd write:
36//! >
37//! > ```gleam
38//! > case a {
39//! > Some(_) -> todo
40//! > None -> todo
41//! > }
42//! > ```
43//! >
44//! > In out representation that would turn into:
45//! >
46//! > ```text
47//! > case {
48//! > a is Some(_) -> todo
49//! > a is None -> todo
50//! > }
51//! > ```
52//! >
53//! > This change makes it way easier to compile the pattern matching into a
54//! > decision tree, because now we can add multiple checks on different
55//! > variables in each branch.
56//!
57//! Starting from this data structure, we'll be splitting all the branches into
58//! a decision tree that can be used to perform exhaustiveness checking and code
59//! generation.
60//!
61
62mod missing_patterns;
63pub mod printer;
64
65use crate::{
66 ast::{
67 self, AssignName, BitArraySize, Endianness, TypedBitArraySize, TypedClause, TypedPattern,
68 TypedPatternBitArraySegment,
69 },
70 strings::{convert_string_escape_chars, length_utf16, length_utf32},
71 type_::{
72 Environment, Opaque, Type, TypeValueConstructor, TypeValueConstructorField, TypeVar,
73 TypeVariantConstructors, collapse_links, error::UnreachablePatternReason,
74 is_prelude_module, string,
75 },
76};
77use ecow::EcoString;
78use id_arena::{Arena, Id};
79use itertools::Itertools;
80use num_bigint::BigInt;
81use radix_trie::{Trie, TrieCommon};
82use std::{
83 cell::RefCell,
84 collections::{HashMap, HashSet, VecDeque},
85 hash::Hash,
86 sync::Arc,
87};
88
89/// A single branch composing a `case` expression to be compiled into a decision
90/// tree.
91///
92/// As shown in the module documentation, branches are a bit different from the
93/// usual branches we see in Gleam's case expressions. Each branch can perform
94/// multiple checks (each on a different variable, which appears in the check
95/// itself!):
96///
97/// ```text
98/// a is Some, b is 1 if condition -> todo
99/// ─┬─────── ─┬──── ─┬────────── ─┬──
100/// │ │ │ ╰── body: an arbitrary expression
101/// │ │ ╰── guard: an additional boolean condition
102/// ╰──────────┴── checks: check that a variable matches with a pattern
103/// ─┬────────────────────────────────────
104/// ╰── branch: one of the branches making up a pattern matching expression
105/// ```
106///
107/// As shown here a branch can also optionally include a guard with a boolean
108/// condition and is followed by a body that is to be executed if all the checks
109/// match (and the guard evaluates to true).
110///
111#[derive(Clone, Eq, PartialEq, Debug)]
112struct Branch {
113 /// Each branch is identified by a numeric index, so we can nicely
114 /// report errors once we find something's wrong with a branch.
115 ///
116 clause_index: usize,
117
118 /// Each alternative pattern in an alternative pattern matching (e.g.
119 /// `one | two | three -> todo`) gets turned into its own branch in this
120 /// internal representation. So we also keep track of the index of the
121 /// alternative this comes from (0 being the first one and so on...)
122 ///
123 alternative_index: usize,
124 checks: Vec<PatternCheck>,
125 guard: Option<usize>,
126 body: Body,
127}
128
129impl Branch {
130 fn new(
131 clause_index: usize,
132 alternative_index: usize,
133 checks: Vec<PatternCheck>,
134 has_guard: bool,
135 ) -> Self {
136 Self {
137 clause_index,
138 alternative_index,
139 checks,
140 guard: if has_guard { Some(clause_index) } else { None },
141 body: Body::new(clause_index),
142 }
143 }
144
145 /// Removes and returns a `PatternCheck` on the given variable from this
146 /// branch.
147 ///
148 fn pop_check_on_var(&mut self, var: &Variable) -> Option<PatternCheck> {
149 let index = self.checks.iter().position(|check| check.var == *var)?;
150 Some(self.checks.remove(index))
151 }
152
153 fn add_check(&mut self, check: PatternCheck) {
154 self.checks.push(check);
155 }
156
157 /// To simplify compiling the pattern we can get rid of all catch-all
158 /// patterns that are guaranteed to match by turning those into assignments.
159 ///
160 /// What does this look like in practice? Let's go over an example.
161 /// Let's say we have this case to compile:
162 ///
163 /// ```gleam
164 /// case a {
165 /// Some(1) -> Some(2)
166 /// otherwise -> otherwise
167 /// }
168 /// ```
169 ///
170 /// In our internal representation this would become:
171 ///
172 /// ```text
173 /// case {
174 /// a is Some(1) -> Some(2)
175 /// a is otherwise -> otherwise
176 /// ─┬────────────
177 /// ╰── `a` will always match with this "catch all" variable pattern
178 /// }
179 /// ```
180 ///
181 /// Focusing on the last branch, we can remove that check that always matches
182 /// by keeping track in its body of the correspondence. So it would end up
183 /// looking like this:
184 ///
185 /// ```text
186 /// case {
187 /// a is Some(1) -> Some(2)
188 /// ∅ -> {
189 /// ┬
190 /// ╰── This represents the fact that there's no checks left for this branch!
191 /// So we can make another observation: if there's no checks left in a
192 /// branch we know it will always match and we can produce a leaf in the
193 /// decision tree (there's an exception when we have guards, but we'll
194 /// get to it later)!
195 ///
196 /// let otherwise = a
197 /// ─┬───────────────
198 /// ╰── And now we can understand what those `bindings` at the start of
199 /// a body are: as we remove variable patterns, we will rewrite those
200 /// as assignments at the top of the body of the corresponding branch.
201 ///
202 /// otherwise
203 /// }
204 /// }
205 /// ```
206 ///
207 fn move_unconditional_patterns(&mut self, compiler: &mut Compiler<'_>) {
208 self.checks.retain_mut(|check| {
209 loop {
210 match compiler.pattern(check.pattern) {
211 // Variable patterns always match, so we move those to the body
212 // and remove them from the branch's checks.
213 Pattern::Variable { name } => {
214 self.body.assign(name.clone(), check.var.clone());
215 return false;
216 }
217 // A discard pattern always matches, but since the value is not
218 // used we can just remove it without even adding an assignment
219 // to the body!
220 Pattern::Discard => return false,
221 // Assigns are kind of special: they get turned into assignments
222 // (shocking) but then we can't discard the pattern they wrap.
223 // So we replace the assignment pattern with the one it's wrapping
224 // and try again.
225 Pattern::Assign { name, pattern } => {
226 self.body.assign(name.clone(), check.var.clone());
227 check.pattern = *pattern;
228 }
229 // There's a special case of assignments when it comes to string
230 // prefix patterns. We can give a name to a literal prefix like this:
231 // `"0" as digit <> rest`.
232 // We also want to move this special case of an assignment to the
233 // branch body!
234 Pattern::StringPrefix {
235 prefix,
236 prefix_name,
237 rest: _,
238 } => {
239 if let Some(variable) = std::mem::take(prefix_name) {
240 self.body
241 .assign_literal_string(variable.clone(), prefix.clone());
242 }
243 return true;
244 }
245 // There's a special case of assignments when it comes to bit
246 // array patterns. We can give a name to one slice of the array and
247 // bind it to a variable to be used by later steps of the pattern
248 // like this: `<<len, payload:size(len)>>` (here we're binding
249 // two variables! `len` and `payload`).
250 //
251 // This kind of slicing will always match if it's not guarded by
252 // any size test, so if we find a `ReadAction` that is the first
253 // test to perform in a bit array pattern we know it's always
254 // going to match and can be safely moved into the branch's body.
255 Pattern::BitArray { tests } => match tests.front_mut() {
256 Some(BitArrayTest::Match(MatchTest {
257 value: BitArrayMatchedValue::Variable(name),
258 read_action,
259 })) => {
260 let bit_array = check.var.clone();
261 self.body.assign_bit_array_slice(
262 name.clone(),
263 bit_array,
264 read_action.clone(),
265 );
266 let _ = tests.pop_front();
267 }
268
269 Some(test) => match test {
270 // If we have `_ as a` we treat that as a regular variable
271 // assignment.
272 BitArrayTest::Match(MatchTest {
273 value: BitArrayMatchedValue::Assign { name, value },
274 read_action,
275 }) if value.is_discard() => {
276 *test = BitArrayTest::Match(MatchTest {
277 value: BitArrayMatchedValue::Variable(name.clone()),
278 read_action: read_action.clone(),
279 });
280 }
281
282 // Just like regular assigns, those patterns are unrefutable
283 // and will become assignments in the branch's body.
284 BitArrayTest::Match(MatchTest {
285 value: BitArrayMatchedValue::Assign { name, value },
286 read_action,
287 }) => {
288 self.body
289 .assign_segment_constant_value(name.clone(), value.as_ref());
290
291 // We will still need to check the aliased value!
292 *test = BitArrayTest::Match(MatchTest {
293 value: value.as_ref().clone(),
294 read_action: read_action.clone(),
295 });
296 }
297
298 // Discards are removed directly without even binding them
299 // in the branch's body.
300 _ if test.is_discard() => {
301 let _ = tests.pop_front();
302 }
303
304 // Otherwise there's no unconditional test to pop, we
305 // keep the pattern without changing it.
306 _ => return true,
307 },
308
309 // If a bit array pattern has no tests then it's always
310 // going to match, no matter what. We just remove it.
311 None => return false,
312 },
313
314 // All other patterns are not unconditional, so we just keep them.
315 _ => return true,
316 }
317 }
318 });
319 }
320}
321
322/// The body of a branch. It always starts with a series of variable assignments
323/// in the form: `let a = b`. As explained in `move_unconditional_patterns`' doc,
324/// each body starts with a series of assignments we keep track of as we're
325/// compiling each branch.
326///
327#[derive(Clone, Eq, PartialEq, Debug)]
328pub struct Body {
329 /// Any variables to bind before running the code.
330 ///
331 /// The tuples are in the form `(name, value)`, so `(wibble, var)`
332 /// corresponds to `let wibble = var`.
333 ///
334 pub bindings: Vec<(EcoString, BoundValue)>,
335
336 /// The index of the clause in the case expression that should be run.
337 ///
338 pub clause_index: usize,
339}
340
341/// A value that can appear on the right hand side of one of the assignments we
342/// find at the top of a body.
343///
344#[derive(Clone, Eq, PartialEq, Debug)]
345pub enum BoundValue {
346 /// `let a = variable`
347 ///
348 Variable(Variable),
349
350 /// `let a = "a literal string"`
351 ///
352 LiteralString(EcoString),
353
354 /// `let a = 123`
355 ///
356 LiteralInt(BigInt),
357
358 /// `let a = 12.2`
359 ///
360 LiteralFloat(EcoString),
361
362 /// `let a = sliceAsInt(bit_array, 0, 16, ...)`
363 ///
364 BitArraySlice {
365 bit_array: Variable,
366 read_action: ReadAction,
367 },
368}
369
370impl Body {
371 pub fn new(clause_index: usize) -> Self {
372 Self {
373 bindings: vec![],
374 clause_index,
375 }
376 }
377
378 /// Adds a new assignment to the body, binding `let variable = value`
379 ///
380 pub fn assign(&mut self, variable: EcoString, value: Variable) {
381 self.bindings.push((variable, BoundValue::Variable(value)));
382 }
383
384 fn assign_literal_string(&mut self, variable: EcoString, value: EcoString) {
385 self.bindings
386 .push((variable, BoundValue::LiteralString(value)));
387 }
388
389 fn assign_bit_array_slice(
390 &mut self,
391 segment_name: EcoString,
392 bit_array: Variable,
393 value: ReadAction,
394 ) {
395 self.bindings.push((
396 segment_name,
397 BoundValue::BitArraySlice {
398 bit_array,
399 read_action: value,
400 },
401 ))
402 }
403
404 fn assign_segment_constant_value(&mut self, name: EcoString, value: &BitArrayMatchedValue) {
405 let value = match value {
406 BitArrayMatchedValue::LiteralFloat(value) => BoundValue::LiteralFloat(value.clone()),
407 BitArrayMatchedValue::LiteralInt(value) => BoundValue::LiteralInt(value.clone()),
408 BitArrayMatchedValue::LiteralString { value, .. } => {
409 BoundValue::LiteralString(value.clone())
410 }
411 BitArrayMatchedValue::Variable(_)
412 | BitArrayMatchedValue::Discard(_)
413 | BitArrayMatchedValue::Assign { .. } => {
414 panic!("aliased non constant value: {value:#?}")
415 }
416 };
417
418 self.bindings.push((name, value))
419 }
420}
421
422/// A user defined pattern such as `Some((x, 10))`.
423/// This is a bit simpler than the full fledged `TypedPattern` used for code analysis
424/// and only focuses on the relevant bits needed to perform exhaustiveness checking
425/// and code generation.
426///
427/// Using this simplified version of a pattern for the case compiler makes it a
428/// whole lot simpler and more efficient (patterns will have to be cloned, so
429/// we use an arena to allocate those and only store ids to make this operation
430/// extra cheap).
431///
432#[derive(Clone, Eq, PartialEq, Debug)]
433pub enum Pattern {
434 Discard,
435 Int {
436 value: EcoString,
437 },
438 Float {
439 value: EcoString,
440 },
441 String {
442 value: EcoString,
443 },
444 StringPrefix {
445 prefix: EcoString,
446 prefix_name: Option<EcoString>,
447 rest: Id<Pattern>,
448 },
449 Assign {
450 name: EcoString,
451 pattern: Id<Pattern>,
452 },
453 Variable {
454 name: EcoString,
455 },
456 Tuple {
457 elements: Vec<Id<Pattern>>,
458 },
459 Variant {
460 index: usize,
461 name: EcoString,
462 module: Option<EcoString>,
463 fields: Vec<Id<Pattern>>,
464 },
465 NonEmptyList {
466 first: Id<Pattern>,
467 rest: Id<Pattern>,
468 },
469 EmptyList,
470 BitArray {
471 tests: VecDeque<BitArrayTest>,
472 },
473}
474
475impl Pattern {
476 /// Each pattern (with a couple exceptions) can be turned into a
477 /// simpler `RuntimeCheck`: that is a check that can be performed at runtime
478 /// to make sure a `PatternCheck` can succeed on a specific value.
479 ///
480 fn to_runtime_check_kind(&self) -> Option<RuntimeCheckKind> {
481 let kind = match self {
482 // These patterns are unconditional: they will always match and be moved
483 // out of a branch's checks. So there's no corresponding runtime check
484 // we can perform for them.
485 Pattern::Discard | Pattern::Variable { .. } | Pattern::Assign { .. } => return None,
486 Pattern::Int { value } => RuntimeCheckKind::Int {
487 value: value.clone(),
488 },
489 Pattern::Float { value } => RuntimeCheckKind::Float {
490 value: value.clone(),
491 },
492 Pattern::String { value } => RuntimeCheckKind::String {
493 value: value.clone(),
494 },
495 Pattern::StringPrefix { prefix, .. } => RuntimeCheckKind::StringPrefix {
496 prefix: prefix.clone(),
497 },
498 Pattern::Tuple { elements } => RuntimeCheckKind::Tuple {
499 size: elements.len(),
500 },
501 Pattern::Variant { index, .. } => RuntimeCheckKind::Variant { index: *index },
502 Pattern::NonEmptyList { .. } => RuntimeCheckKind::NonEmptyList,
503 Pattern::EmptyList => RuntimeCheckKind::EmptyList,
504 // Bit arrays have no corresponding kind as they're dealt with in a
505 // completely different way.
506 Pattern::BitArray { .. } => return None,
507 };
508
509 Some(kind)
510 }
511
512 fn is_matching_on_unreachable_variant(&self, branch_mode: &BranchMode) -> bool {
513 match (self, branch_mode) {
514 (
515 Self::Variant { index, .. },
516 BranchMode::NamedType {
517 inferred_variant: Some(variant),
518 ..
519 },
520 ) if index != variant => true,
521 _ => false,
522 }
523 }
524}
525
526/// A single check making up a branch, checking that a variable matches with a
527/// given pattern. For example, the following branch has 2 checks:
528///
529/// ```text
530/// a is Some, b is 1 -> todo
531/// ┬ ─┬──
532/// │ ╰── This is the pattern being checked
533/// ╰── This is the variable being pattern matched on
534/// ─┬─────── ─┬────
535/// ╰─────────┴── Two `PatternCheck`s
536/// ```
537///
538#[derive(Clone, Eq, PartialEq, Debug)]
539struct PatternCheck {
540 var: Variable,
541 pattern: Id<Pattern>,
542}
543
544/// This is one of the checks we can take at runtime to decide how to move
545/// forward in the decision tree.
546///
547/// After performing a successful check on a value we will discover something
548/// about its shape: it might be an int, an variant of a custom type, ...
549/// Some values (like variants and lists) might hold onto additional data we
550/// will have to pattern match on: in order to do that we need a name to refer
551/// to those new variables we've discovered after performing a check. That's
552/// what `args` is for.
553///
554/// Let's have a look at an example. Imagine we have a pattern like this one:
555/// `a is Wibble(1, _, [])`; after performing a runtime check to make sure `a`
556/// is indeed a `Wibble`, we'll need to perform additional checks on it's
557/// arguments: that pattern will be replaced by three new ones `a0 is 1`,
558/// `a1 is _` and `a2 is []`. Those new variables are the `args`.
559///
560#[derive(Clone, Debug, PartialEq, Eq)]
561pub enum RuntimeCheck {
562 Int {
563 value: EcoString,
564 },
565 Float {
566 value: EcoString,
567 },
568 String {
569 value: EcoString,
570 },
571 StringPrefix {
572 prefix: EcoString,
573 rest: Variable,
574 },
575 Tuple {
576 size: usize,
577 elements: Vec<Variable>,
578 },
579 BitArray {
580 test: BitArrayTest,
581 },
582 Variant {
583 match_: VariantMatch,
584 index: usize,
585 labels: HashMap<usize, EcoString>,
586 fields: Vec<Variable>,
587 },
588 NonEmptyList {
589 first: Variable,
590 rest: Variable,
591 },
592 EmptyList,
593}
594
595impl RuntimeCheck {
596 fn kind(&self) -> Option<RuntimeCheckKind> {
597 let kind = match self {
598 RuntimeCheck::Int { value } => RuntimeCheckKind::Int {
599 value: value.clone(),
600 },
601 RuntimeCheck::Float { value } => RuntimeCheckKind::Float {
602 value: value.clone(),
603 },
604 RuntimeCheck::String { value } => RuntimeCheckKind::String {
605 value: value.clone(),
606 },
607 RuntimeCheck::StringPrefix { prefix, rest: _ } => RuntimeCheckKind::StringPrefix {
608 prefix: prefix.clone(),
609 },
610 RuntimeCheck::Tuple { size, elements: _ } => RuntimeCheckKind::Tuple { size: *size },
611 RuntimeCheck::Variant { index, .. } => RuntimeCheckKind::Variant { index: *index },
612 RuntimeCheck::EmptyList => RuntimeCheckKind::EmptyList,
613 RuntimeCheck::NonEmptyList { first: _, rest: _ } => RuntimeCheckKind::NonEmptyList,
614 RuntimeCheck::BitArray { .. } => return None,
615 };
616 Some(kind)
617 }
618
619 pub(crate) fn is_ignored(&self) -> bool {
620 match self {
621 RuntimeCheck::Variant {
622 match_: VariantMatch::NeverExplicitlyMatchedOn { .. },
623 ..
624 } => true,
625 _ => false,
626 }
627 }
628
629 /// Returns all the bit array segments referenced in this check.
630 /// For each segment it returns its name and the read action used to access
631 /// such segment.
632 ///
633 pub(crate) fn referenced_segment_patterns(&self) -> Vec<(&EcoString, &ReadAction)> {
634 match self {
635 RuntimeCheck::BitArray { test } => test.referenced_segment_patterns(),
636 RuntimeCheck::Int { .. }
637 | RuntimeCheck::Float { .. }
638 | RuntimeCheck::String { .. }
639 | RuntimeCheck::StringPrefix { .. }
640 | RuntimeCheck::Tuple { .. }
641 | RuntimeCheck::Variant { .. }
642 | RuntimeCheck::NonEmptyList { .. }
643 | RuntimeCheck::EmptyList => vec![],
644 }
645 }
646}
647
648#[derive(Eq, PartialEq, Clone, Hash, Debug)]
649pub enum RuntimeCheckKind {
650 Int { value: EcoString },
651 Float { value: EcoString },
652 String { value: EcoString },
653 StringPrefix { prefix: EcoString },
654 Tuple { size: usize },
655 Variant { index: usize },
656 EmptyList,
657 NonEmptyList,
658}
659
660/// All possible variant checks are automatically generated beforehand once we
661/// know we are matching on a value with a custom type.
662/// Then if the compiled case is explicitly matching on one of those, we update
663/// it to store additional information: for example how the variant is used
664/// (if qualified or unqualified and if it is aliased).
665///
666/// This way when we get to code generation we can clump all variants that were
667/// never explicitly matched on in a single `else` block without blowing up code
668/// size!
669///
670#[derive(Clone, Debug, PartialEq, Eq)]
671pub enum VariantMatch {
672 ExplicitlyMatchedOn {
673 name: EcoString,
674 module: Option<EcoString>,
675 },
676 NeverExplicitlyMatchedOn {
677 name: EcoString,
678 },
679}
680
681impl VariantMatch {
682 pub(crate) fn name(&self) -> EcoString {
683 match self {
684 VariantMatch::ExplicitlyMatchedOn { name, module: _ } => name.clone(),
685 VariantMatch::NeverExplicitlyMatchedOn { name } => name.clone(),
686 }
687 }
688
689 pub(crate) fn module(&self) -> Option<EcoString> {
690 match self {
691 VariantMatch::ExplicitlyMatchedOn { name: _, module } => module.clone(),
692 VariantMatch::NeverExplicitlyMatchedOn { name: _ } => None,
693 }
694 }
695}
696
697/// A variable that can be matched on in a branch.
698///
699#[derive(Eq, PartialEq, Clone, Debug)]
700pub struct Variable {
701 pub id: usize,
702 pub type_: Arc<Type>,
703}
704
705impl Variable {
706 fn new(id: usize, type_: Arc<Type>) -> Self {
707 Self { id, type_ }
708 }
709
710 /// Builds a `PatternCheck` that checks this variable matches the given pattern.
711 /// So we can build pattern checks the same way we informally describe them:
712 /// ```text
713 /// var is pattern
714 /// ```
715 /// With this builder method would become:
716 /// ```rs
717 /// var.is(pattern)
718 /// ```
719 ///
720 fn is(&self, pattern: Id<Pattern>) -> PatternCheck {
721 PatternCheck {
722 var: self.clone(),
723 pattern,
724 }
725 }
726}
727
728#[derive(Debug)]
729/// Different types need to be handled differently when compiling a case expression
730/// into a decision tree. There's some types that have infinite matching patterns
731/// (like ints, strings, ...) and thus will always need a fallback option.
732///
733/// Other types, like custom types, only have a well defined and finite number
734/// of patterns that could match: when matching on a `Result` we know that we can
735/// only have an `Ok(_)` and an `Error(_)`, anything else would end up being a
736/// type error!
737///
738/// So this enum is used to pick the correct strategy to compile a case that's
739/// performing a `PatternCheck` on a variable with a specific type.
740///
741enum BranchMode {
742 /// This covers numbers, functions, variables, strings, and bitarrays.
743 Infinite,
744 Tuple {
745 elements: Vec<Arc<Type>>,
746 },
747 List {
748 inner_type: Arc<Type>,
749 },
750 NamedType {
751 constructors: Vec<TypeValueConstructor>,
752 inferred_variant: Option<usize>,
753 },
754}
755
756impl BranchMode {
757 fn is_infinite(&self) -> bool {
758 match self {
759 BranchMode::Infinite => true,
760 BranchMode::Tuple { .. } | BranchMode::List { .. } | BranchMode::NamedType { .. } => {
761 false
762 }
763 }
764 }
765}
766
767impl Variable {
768 fn branch_mode(&self, env: &Environment<'_>) -> BranchMode {
769 match collapse_links(self.type_.clone()).as_ref() {
770 Type::Fn { .. } | Type::Var { .. } => BranchMode::Infinite,
771 Type::Named { module, name, .. }
772 if is_prelude_module(module)
773 && (name == "Int"
774 || name == "Float"
775 || name == "BitArray"
776 || name == "String") =>
777 {
778 BranchMode::Infinite
779 }
780
781 Type::Named {
782 module, name, args, ..
783 } if is_prelude_module(module) && name == "List" => BranchMode::List {
784 inner_type: args.first().expect("list has a type argument").clone(),
785 },
786
787 Type::Tuple { elements } => BranchMode::Tuple {
788 elements: elements.clone(),
789 },
790
791 Type::Named {
792 module,
793 name,
794 args,
795 inferred_variant,
796 ..
797 } => {
798 let constructors = ConstructorSpecialiser::specialise_constructors(
799 env.get_constructors_for_type(module, name)
800 .expect("Custom type variants must exist"),
801 args.as_slice(),
802 &env.current_module,
803 module,
804 );
805
806 let inferred_variant = inferred_variant.map(|i| i as usize);
807 BranchMode::NamedType {
808 constructors,
809 inferred_variant,
810 }
811 }
812 }
813 }
814}
815
816/// When compiling a bit array pattern each segment is turned into a series of
817/// tests that all need to match in order for the pattern to succeed.
818/// Each segment might add some requirements on the total size of a bit array
819/// and/or on the value of some of its specific parts.
820///
821/// Let's look at a simple example to get started:
822///
823/// ```txt
824/// <<0:size(12), 1, rest:bits>>
825/// ─┬────────
826/// ╰── This first segment requires that the bit array must have at least
827/// 12 bits and their value must be the Int `0`. So this first
828/// segment would be turned into the following series of tests:
829/// `Size(>=, 12)` and `Match(0, ReadAction(0, 12, int))`
830/// ```
831///
832/// However, the various sizes and offsets of the different segments might not
833/// always be known at compile time and depend on previous sections of the
834/// pattern. This is no big deal: as you'll discover in more detail in the
835/// `SizeExpression`'s doc we can also represent those variable sizes:
836///
837/// ```txt
838/// <<len, payload:size(len), rest:bits>>
839/// ─┬─ ─┬───────────────
840/// │ ╰── For this segment to match the bit array must have enough bits
841/// │ for the previous segment (8 bits) and for this one (`len` bits),
842/// │ so it will turn into the following series of tests:
843/// │ `Size(>=, 8 + len)` and `Match(len, ReadAction(8, len, int))`
844/// │
845/// ╰── This first segment is 8 bits and an int (it's the default Gleam picks
846/// if no options are supplied)
847/// ```
848///
849#[derive(Clone, Eq, PartialEq, Debug)]
850pub enum BitArrayTest {
851 Size(SizeTest),
852 Match(MatchTest),
853
854 /// This is a special test to check that the remaining part of a bit array
855 /// has a whole number of bytes when using the `:bytes` option.
856 ///
857 CatchAllIsBytes {
858 size_so_far: Offset,
859 },
860
861 /// This test is made to ensure a given variable is positive: a segment
862 /// pattern where the size is a variable with a negative value will never
863 /// match. So we check this to make sure the test will fail.
864 ///
865 VariableIsNotNegative {
866 variable: VariableUsage,
867 },
868
869 /// This test checks that the segment read by the given read action is a
870 /// finite Float and not a `NaN` or `Infinity`.
871 ///
872 /// We need this check as `NaN` and `Infinity` will not match with float
873 /// segments (like `<<_:32-float>>`) on the Erlang target and we must
874 /// replicate the same behavious on the JavaScript target as well.
875 ///
876 SegmentIsFiniteFloat {
877 read_action: ReadAction,
878 },
879}
880
881impl BitArrayTest {
882 fn is_discard(&self) -> bool {
883 match self {
884 BitArrayTest::Match(MatchTest {
885 value: BitArrayMatchedValue::Discard(_),
886 ..
887 }) => true,
888 _ => false,
889 }
890 }
891
892 pub(crate) fn referenced_segment_patterns(&self) -> Vec<(&EcoString, &ReadAction)> {
893 match self {
894 BitArrayTest::VariableIsNotNegative { variable } => match variable {
895 VariableUsage::PatternSegment(segment_value, read_action) => {
896 vec![(segment_value, read_action)]
897 }
898 VariableUsage::OutsideVariable(..) => vec![],
899 },
900
901 BitArrayTest::Size(SizeTest { operator: _, size })
902 | BitArrayTest::CatchAllIsBytes { size_so_far: size } => {
903 size.referenced_segment_patterns()
904 }
905
906 BitArrayTest::SegmentIsFiniteFloat {
907 read_action: ReadAction { from, size, .. },
908 }
909 | BitArrayTest::Match(MatchTest {
910 read_action: ReadAction { from, size, .. },
911 ..
912 }) => {
913 let mut references = vec![];
914 references.append(&mut from.referenced_segment_patterns());
915 match size {
916 ReadSize::VariableBits { variable, unit: _ } => match variable.as_ref() {
917 VariableUsage::PatternSegment(segment_value, read_action) => {
918 references.push((segment_value, read_action))
919 }
920 VariableUsage::OutsideVariable(..) => (),
921 },
922
923 ReadSize::ConstantBits(..)
924 | ReadSize::RemainingBits
925 | ReadSize::RemainingBytes => (),
926 };
927
928 references
929 }
930 }
931 }
932}
933
934/// Test to make sure the bit array has a specific number of bits.
935///
936#[derive(Clone, Eq, PartialEq, Debug)]
937pub struct SizeTest {
938 pub operator: SizeOperator,
939 pub size: Offset,
940}
941
942impl SizeTest {
943 /// Tells us if this test is guaranteed to succeed given another test that
944 /// we know has already succeeded.
945 ///
946 /// For example, ">= 5" is certainly going to succeed if ">= 6" has already
947 /// succeeded.
948 ///
949 fn succeeds_if_succeeding(&self, succeeding: &SizeTest) -> Confidence {
950 match (succeeding.operator, self.operator) {
951 (SizeOperator::Equal, SizeOperator::Equal) if succeeding.size == self.size => {
952 Confidence::Certain
953 }
954 (_, SizeOperator::GreaterEqual) => succeeding.size.greater_equal(&self.size),
955 _ => Confidence::Uncertain,
956 }
957 }
958
959 /// Tells us if this test is guaranteed to fail given another test that
960 /// we know has already failed.
961 ///
962 /// For example, ">= 5" is certainly going to fail if ">= 4" has already
963 /// failed.
964 ///
965 fn fails_if_failing(&self, failing: &SizeTest) -> Confidence {
966 match (failing.operator, self.operator) {
967 (SizeOperator::GreaterEqual, _) => self.size.greater_equal(&failing.size),
968 (_, _) if self == failing => Confidence::Certain,
969 _ => Confidence::Uncertain,
970 }
971 }
972
973 /// Tells us if this test is guaranteed to fail given another test that
974 /// we know has already succeeded.
975 ///
976 /// For example, "= 1" is certainly going to fail if "= 2" has already
977 /// succeeded.
978 ///
979 fn fails_if_succeeding(&self, succeeding: &SizeTest) -> Confidence {
980 match (succeeding.operator, self.operator) {
981 (SizeOperator::GreaterEqual, SizeOperator::Equal) => {
982 succeeding.size.greater(&self.size)
983 }
984 (SizeOperator::Equal, SizeOperator::GreaterEqual) => {
985 self.size.greater(&succeeding.size)
986 }
987 (SizeOperator::Equal, SizeOperator::Equal) => succeeding.size.different(&self.size),
988 _ => Confidence::Uncertain,
989 }
990 }
991}
992
993/// Test to make sure the segment read by the specified `read_action` matches
994/// a given value.
995///
996#[derive(Clone, Eq, PartialEq, Debug)]
997pub struct MatchTest {
998 pub value: BitArrayMatchedValue,
999 pub read_action: ReadAction,
1000}
1001
1002/// A value that can be matched in a bit array pattern's segment. We do not use
1003/// a `Pattern` directly since the allowed values are actually a subset of all
1004/// the possible patterns: it can only contain literal floats, ints, strings,
1005/// a variable name, and a discard.
1006///
1007#[derive(Clone, Eq, PartialEq, Debug)]
1008pub enum BitArrayMatchedValue {
1009 LiteralFloat(EcoString),
1010 LiteralInt(BigInt),
1011 LiteralString {
1012 value: EcoString,
1013 encoding: StringEncoding,
1014 },
1015 Variable(EcoString),
1016 Discard(EcoString),
1017 Assign {
1018 name: EcoString,
1019 value: Box<BitArrayMatchedValue>,
1020 },
1021}
1022
1023impl BitArrayMatchedValue {
1024 pub(crate) fn is_literal(&self) -> bool {
1025 match self {
1026 BitArrayMatchedValue::LiteralFloat(_)
1027 | BitArrayMatchedValue::LiteralInt(_)
1028 | BitArrayMatchedValue::LiteralString { .. } => true,
1029 BitArrayMatchedValue::Variable(..) | BitArrayMatchedValue::Discard(..) => false,
1030 BitArrayMatchedValue::Assign { value, .. } => value.is_literal(),
1031 }
1032 }
1033}
1034
1035#[derive(Clone, Copy, Eq, PartialEq, Debug)]
1036pub enum StringEncoding {
1037 Utf8,
1038 Utf16,
1039 Utf32,
1040}
1041
1042impl BitArrayMatchedValue {
1043 pub fn is_discard(&self) -> bool {
1044 match self {
1045 BitArrayMatchedValue::Discard(_) => true,
1046 BitArrayMatchedValue::LiteralFloat(_)
1047 | BitArrayMatchedValue::LiteralInt(_)
1048 | BitArrayMatchedValue::LiteralString { .. }
1049 | BitArrayMatchedValue::Variable(_)
1050 | BitArrayMatchedValue::Assign { .. } => false,
1051 }
1052 }
1053}
1054
1055impl BitArrayTest {
1056 // TODO: for these tests we could also implement a more sophisticated
1057 // approach for `Match` tests. This is described in the linked paper as
1058 // read action interference and can help making the tree smaller in some
1059 // specific cases.
1060 // This could be an interesting optimisation once we start using the tree
1061 // for code generation as well.
1062
1063 /// Tells us if this test is guaranteed to succeed given another test that
1064 /// we know has already succeeded.
1065 ///
1066 /// For example, "size >= 5" is certainly going to succeed if "size >= 6"
1067 /// has already succeeded.
1068 ///
1069 #[must_use]
1070 fn succeeds_if_succeeding(&self, succeeding: &BitArrayTest) -> Confidence {
1071 match (succeeding, self) {
1072 (one, other) if one == other => Confidence::Certain,
1073 (BitArrayTest::Size(succeeding), BitArrayTest::Size(test)) => {
1074 test.succeeds_if_succeeding(succeeding)
1075 }
1076 // The tests are not comparable, we can't deduce any new information.
1077 _ => Confidence::Uncertain,
1078 }
1079 }
1080
1081 /// Tells us if this test is guaranteed to fail given another test that
1082 /// we know has already failed.
1083 ///
1084 /// For example, "size >= 5" is certainly going to fail if "size >= 4"
1085 /// has already failed.
1086 ///
1087 #[must_use]
1088 fn fails_if_failing(&self, failing: &BitArrayTest) -> Confidence {
1089 match (failing, self) {
1090 (one, other) if one == other => Confidence::Certain,
1091 (BitArrayTest::Size(failing), BitArrayTest::Size(test)) => {
1092 test.fails_if_failing(failing)
1093 }
1094 // The tests are not comparable, we can't deduce any new information.
1095 _ => Confidence::Uncertain,
1096 }
1097 }
1098
1099 /// Tells us if this test is guaranteed to fail given another test that
1100 /// we know has already succeeded.
1101 ///
1102 /// For example, "size = 1" is certainly going to fail if "size = 2" has already
1103 /// succeeded.
1104 ///
1105 #[must_use]
1106 fn fails_if_succeeding(&self, succeeding: &BitArrayTest) -> Confidence {
1107 match (succeeding, self) {
1108 // This is an implementation of Table 6 (a) of the bit array pattern
1109 // matching paper linked at the top of this module's documentation!
1110 (BitArrayTest::Size(succeeding), BitArrayTest::Size(test)) => {
1111 test.fails_if_succeeding(succeeding)
1112 }
1113 // The tests are not comparable, we can't deduce any new information.
1114 _ => Confidence::Uncertain,
1115 }
1116 }
1117}
1118
1119/// When performing a size test it could require that a size is exactly some
1120/// specific number of bits (for example if we're matching the last segment
1121/// of a bit array) or that it has at least some number of bits. For example:
1122///
1123/// ```text
1124/// <<0:size(12), 1:size(8)>>
1125/// ─┬──────── ─┬───────
1126/// │ ╰── For this segment to successfully match the bit array must
1127/// │ have exactly 20 bits: because it will need to read 8 bits
1128/// │ from bit 13 where the previous one ends: `Size(=, 20)`
1129/// │
1130/// ╰── For this segment to successfully match, the bit array must have at
1131/// least 12 bits: `Size(>, 12)`
1132/// ```
1133///
1134#[derive(Clone, Eq, PartialEq, Debug, Copy)]
1135pub enum SizeOperator {
1136 GreaterEqual,
1137 Equal,
1138}
1139
1140/// Represents the action of reading a certain number of bits from a bit array
1141/// at a given position, returning a value with the given type.
1142///
1143/// Notice how the starting position and number of bits to read might not be
1144/// known at compile time but also include variables! For example here:
1145///
1146/// ```txt
1147// <<len, payload:size(len), rest:bits>>
1148/// ─┬─ ─┬───────────────
1149/// │ ╰── Here payload has a variable size, given by the `len` variable
1150/// │
1151/// ╰── While this segment has a constant size of 8 bits
1152/// ```
1153///
1154#[derive(Clone, Eq, PartialEq, Debug, Hash)]
1155pub struct ReadAction {
1156 /// The offset to start reading the bits from.
1157 ///
1158 pub from: Offset,
1159 /// Number of _bits_ to read.
1160 ///
1161 pub size: ReadSize,
1162 /// The type of the read value.
1163 ///
1164 pub type_: ReadType,
1165 /// Endianness of the read value.
1166 ///
1167 pub endianness: Endianness,
1168 /// Signedness of the read value.
1169 ///
1170 pub signed: bool,
1171}
1172
1173/// Only a subset of all the possible Gleam types can be used for a pattern
1174/// segment. We enumerate those out explicitly here.
1175///
1176#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
1177pub enum ReadType {
1178 Float,
1179 Int,
1180 String,
1181 BitArray,
1182 UtfCodepoint,
1183}
1184
1185impl ReadType {
1186 pub(crate) fn is_int(&self) -> bool {
1187 match self {
1188 ReadType::Int => true,
1189 ReadType::Float | ReadType::String | ReadType::BitArray | ReadType::UtfCodepoint => {
1190 false
1191 }
1192 }
1193 }
1194
1195 pub(crate) fn is_float(&self) -> bool {
1196 match self {
1197 ReadType::Float => true,
1198 ReadType::Int | ReadType::String | ReadType::BitArray | ReadType::UtfCodepoint => false,
1199 }
1200 }
1201}
1202
1203#[derive(Debug, Clone, Copy, PartialEq, Eq)]
1204enum Confidence {
1205 Certain,
1206 Uncertain,
1207}
1208
1209impl Confidence {
1210 fn is_certain(&self) -> bool {
1211 match self {
1212 Confidence::Certain => true,
1213 Confidence::Uncertain => false,
1214 }
1215 }
1216
1217 fn or_else(&self, fun: impl Fn() -> Confidence) -> Confidence {
1218 match self {
1219 Confidence::Certain => Confidence::Certain,
1220 Confidence::Uncertain => fun(),
1221 }
1222 }
1223}
1224
1225#[derive(Clone, Eq, PartialEq, Debug, Hash)]
1226pub struct Offset {
1227 pub constant: BigInt,
1228 pub variables: im::HashMap<VariableUsage, usize>,
1229}
1230
1231impl Offset {
1232 pub fn constant(value: impl Into<BigInt>) -> Self {
1233 Self {
1234 constant: value.into(),
1235 variables: im::HashMap::new(),
1236 }
1237 }
1238
1239 fn add_size(self, size: &ReadSize) -> Offset {
1240 match size {
1241 ReadSize::ConstantBits(value) => Self {
1242 constant: self.constant + value,
1243 variables: self.variables,
1244 },
1245 ReadSize::VariableBits { variable, unit } => Self {
1246 constant: self.constant,
1247 variables: self.variables.alter(
1248 |value| match value {
1249 Some(value) => Some(value + (*unit as usize)),
1250 None => Some(*unit as usize),
1251 },
1252 variable.as_ref().clone(),
1253 ),
1254 },
1255 ReadSize::RemainingBits | ReadSize::RemainingBytes => self,
1256 }
1257 }
1258
1259 pub fn add_constant(&self, constant: impl Into<BigInt>) -> Offset {
1260 Offset {
1261 constant: self.constant.clone() + constant.into(),
1262 variables: self.variables.clone(),
1263 }
1264 }
1265
1266 /// Returns `true` if we can tell for certain this offset is greater than
1267 /// another one.
1268 ///
1269 fn greater(&self, other: &Offset) -> Confidence {
1270 if self.constant > other.constant && superset(&self.variables, &other.variables) {
1271 Confidence::Certain
1272 } else {
1273 Confidence::Uncertain
1274 }
1275 }
1276
1277 /// Returns `true` if we can tell for certain this offset is greater or equal
1278 /// to another one.
1279 ///
1280 fn greater_equal(&self, other: &Offset) -> Confidence {
1281 if self == other
1282 || (self.constant >= other.constant && superset(&self.variables, &other.variables))
1283 {
1284 Confidence::Certain
1285 } else {
1286 Confidence::Uncertain
1287 }
1288 }
1289
1290 /// Returns `true` if we can tell for certain this offset is different from
1291 /// another one.
1292 ///
1293 fn different(&self, other: &Offset) -> Confidence {
1294 self.greater(other).or_else(|| other.greater(self))
1295 }
1296
1297 pub(crate) fn is_zero(&self) -> bool {
1298 self.constant == BigInt::ZERO && self.variables.is_empty()
1299 }
1300
1301 /// If this offset has a constant size, returns its size in bits.
1302 ///
1303 pub(crate) fn constant_bits(&self) -> Option<BigInt> {
1304 if self.variables.is_empty() {
1305 Some(self.constant.clone())
1306 } else {
1307 None
1308 }
1309 }
1310
1311 /// If this offset has a constant size that's a whole number of bytes,
1312 /// returns its size in bytes.
1313 ///
1314 pub(crate) fn constant_bytes(&self) -> Option<BigInt> {
1315 let bits = self.constant_bits()?;
1316 if bits.clone() % 8 == BigInt::ZERO {
1317 Some(bits / 8)
1318 } else {
1319 None
1320 }
1321 }
1322
1323 fn referenced_segment_patterns(&self) -> Vec<(&EcoString, &ReadAction)> {
1324 self.variables
1325 .keys()
1326 .filter_map(|variable_usage| match variable_usage {
1327 VariableUsage::PatternSegment(segment_name, read_action) => {
1328 Some((segment_name, read_action))
1329 }
1330 VariableUsage::OutsideVariable(..) => None,
1331 })
1332 .collect_vec()
1333 }
1334}
1335
1336/// The number of bits to read in a read action when reading a segment.
1337///
1338#[derive(Clone, Eq, PartialEq, Debug, Hash)]
1339pub enum ReadSize {
1340 /// Read a constant, compile-time-known number of bits.
1341 ///
1342 /// ```txt
1343 /// <<tag:size(8)>>
1344 /// ─┬─────────
1345 /// ╰─ Here we know that we have to read exactly 8 bits
1346 /// ```
1347 ///
1348 ConstantBits(BigInt),
1349 /// Read a variable number of bits.
1350 ///
1351 /// ```txt
1352 /// <<len, payload:size(len)>>
1353 /// ─┬───────────────
1354 /// ╰─ Here we will know how many bits to read only at runtime since
1355 /// the length is a variable
1356 /// ```
1357 ///
1358 VariableBits {
1359 variable: Box<VariableUsage>,
1360 unit: u8,
1361 },
1362 /// Read all the remaining bits in the bit array when using a catch all
1363 /// pattern.
1364 ///
1365 /// ```txt
1366 /// <<_, rest:bits>>
1367 /// ─┬───────
1368 /// ╰─ We take all the remaining bits from the bit array
1369 /// ```
1370 ///
1371 RemainingBits,
1372 RemainingBytes,
1373}
1374
1375impl ReadSize {
1376 /// If this is a constant number of bits returns it wrapped in `Some`.
1377 pub(crate) fn constant_bits(&self) -> Option<BigInt> {
1378 match self {
1379 ReadSize::ConstantBits(value) => Some(value.clone()),
1380 ReadSize::VariableBits { .. } | ReadSize::RemainingBits | ReadSize::RemainingBytes => {
1381 None
1382 }
1383 }
1384 }
1385
1386 /// If this is a constant number of bytes returns it wrapped in `Some`.
1387 pub(crate) fn constant_bytes(&self) -> Option<BigInt> {
1388 let bits = self.constant_bits()?;
1389 if bits.clone() % 8 == BigInt::ZERO {
1390 Some(bits / 8)
1391 } else {
1392 None
1393 }
1394 }
1395}
1396
1397#[derive(Clone, Eq, PartialEq, Debug, Hash)]
1398pub enum VariableUsage {
1399 /// A bit array named segment that was brought into scope in the bit array
1400 /// pattern itself and might be referenced by later segments.
1401 PatternSegment(EcoString, ReadAction),
1402 /// A variable defined somewhere else
1403 OutsideVariable(EcoString),
1404}
1405
1406impl VariableUsage {
1407 pub fn name(&self) -> &EcoString {
1408 match self {
1409 VariableUsage::PatternSegment(name, _) | VariableUsage::OutsideVariable(name) => name,
1410 }
1411 }
1412}
1413
1414/// This is the decision tree that a pattern matching expression gets turned
1415/// into: it's a tree-like structure where each path to a root node contains a
1416/// series of checks to perform at runtime to understand if a value matches with
1417/// a given pattern.
1418///
1419#[derive(Debug, Clone, PartialEq, Eq)]
1420pub enum Decision {
1421 /// This is the final node of the tree, once we get to this one we know we
1422 /// have a body to run because a given pattern matched.
1423 ///
1424 Run { body: Body },
1425
1426 /// We have to make this decision when we run into a branch that also has a
1427 /// guard: if it is true we can finally run the body of the branch, stored in
1428 /// `if_true`.
1429 /// If it is false we might still have to take other decisions and so we might
1430 /// have another `DecisionTree` to traverse, stored in `if_false`.
1431 ///
1432 Guard {
1433 guard: usize,
1434 if_true: Body,
1435 if_false: Box<Decision>,
1436 },
1437
1438 /// When reaching this node we'll have to see if any of the possible checks
1439 /// in `choices` will succeed on `var`. If it does, we know that's the path
1440 /// we have to go down to. If none of the checks matches, then we'll have to
1441 /// go down the `fallback` branch.
1442 ///
1443 /// The type system guarantees that all switches will always have at least
1444 /// one last choice that acts as a fallback to pick if none of the others
1445 /// matches; no matter the value we're matching on.
1446 ///
1447 /// In case we're dealing with exhaustive cases (for example on lists/custom
1448 /// types) we also keep track of the final check associated with the final
1449 /// branch: keep in mind, we don't actually have to run that check because
1450 /// we know that the type system guarantees it will always match; but it
1451 /// can hold useful informations for type generation so we keep it around.
1452 /// You can read the doc for `FallbackCheck` to find out a more in depth
1453 /// explanation and some examples!
1454 ///
1455 Switch {
1456 var: Variable,
1457 choices: Vec<(RuntimeCheck, Box<Decision>)>,
1458 fallback: Box<Decision>,
1459 fallback_check: FallbackCheck,
1460 },
1461
1462 /// This is a special node: it represents a missing pattern. If a tree
1463 /// contains such a node, then we know that the patterns it was compiled
1464 /// from are not exhaustive and the path leading to this node will describe
1465 /// what kind of pattern doesn't match!
1466 ///
1467 Fail,
1468}
1469
1470/// When we have a swith in the decision tree we know there's always going to be
1471/// at least one choice that comes last and we know is going to match no matter
1472/// what. This might fall under three different categories.
1473///
1474#[derive(Debug, Eq, PartialEq, Clone)]
1475pub enum FallbackCheck {
1476 /// This corresponds to the catch all added at the end of a case expression
1477 /// matching on an infinite type.
1478 ///
1479 /// ```txt
1480 /// case todo {
1481 /// 1 -> todo
1482 /// _ -> todo
1483 /// ─┬───────
1484 // ╰── when matching on an infinite type there's going to be a catch all
1485 /// }
1486 ///
1487 InfiniteCatchAll,
1488
1489 /// This happens when we're matching on a variant whose checks are all
1490 /// explicitly written down:
1491 ///
1492 /// ```txt
1493 /// case todo {
1494 /// Ok(_) -> todo
1495 /// Error(Nil) -> todo
1496 /// ─┬────────────────
1497 // ╰── when matching on a custom type (or list!) we'll have to write all
1498 // variants down, so there's always going to be a last one.
1499 /// }
1500 /// ```
1501 ///
1502 /// The type system will make sure that this last check will always match,
1503 /// no matter what, if none of the other checks matches. We still keep the
1504 /// corresponding runtime check around because it's useful for code generation!
1505 ///
1506 RuntimeCheck { check: RuntimeCheck },
1507
1508 /// This is a special case for a catch all! It happens when we're matching
1509 /// on a variant and use a catch all pattern:
1510 ///
1511 /// ```txt
1512 /// case todo {
1513 /// Ok(_) -> todo
1514 /// _ -> todo
1515 /// ─┬───────
1516 /// ╰── here we know we're just skipping over the `Error` variant with
1517 /// this catch all.
1518 /// }
1519 /// ```
1520 ///
1521 /// We know exactly which variants we're skipping, so we keep track of
1522 /// those skipped checks (they will end up being useful for reporting
1523 /// missing patterns!)
1524 ///
1525 CatchAll { ignored_checks: Vec<RuntimeCheck> },
1526}
1527
1528impl Decision {
1529 pub fn run(body: Body) -> Self {
1530 Decision::Run { body }
1531 }
1532
1533 pub fn guard(guard: usize, if_true: Body, if_false: Self) -> Self {
1534 Decision::Guard {
1535 guard,
1536 if_true,
1537 if_false: Box::new(if_false),
1538 }
1539 }
1540}
1541
1542/// The `case` compiler itself (shocking, I know).
1543///
1544#[derive(Debug)]
1545struct Compiler<'a> {
1546 environment: &'a Environment<'a>,
1547 patterns: Arena<Pattern>,
1548 variable_id: usize,
1549 diagnostics: Diagnostics,
1550}
1551
1552/// The result of compiling a pattern match expression.
1553///
1554pub struct CompileCaseResult {
1555 pub compiled_case: CompiledCase,
1556 pub diagnostics: Diagnostics,
1557}
1558
1559impl CompileCaseResult {
1560 pub fn is_reachable(&self, clause: usize, pattern_index: usize) -> Reachability {
1561 if self
1562 .diagnostics
1563 .reachable
1564 .contains(&(clause, pattern_index))
1565 {
1566 Reachability::Reachable
1567 } else if self
1568 .diagnostics
1569 .match_impossible_variants
1570 .contains(&(clause, pattern_index))
1571 {
1572 Reachability::Unreachable(UnreachablePatternReason::ImpossibleVariant)
1573 } else {
1574 Reachability::Unreachable(UnreachablePatternReason::DuplicatePattern)
1575 }
1576 }
1577
1578 pub fn missing_patterns(&self, environment: &Environment<'_>) -> Vec<EcoString> {
1579 missing_patterns::missing_patterns(self, environment)
1580 }
1581}
1582
1583#[derive(Debug, PartialEq, Eq, Clone)]
1584pub struct CompiledCase {
1585 pub tree: Decision,
1586 pub subject_variables: Vec<Variable>,
1587}
1588
1589impl CompiledCase {
1590 pub fn failure() -> Self {
1591 Self {
1592 tree: Decision::Fail,
1593 subject_variables: vec![],
1594 }
1595 }
1596}
1597
1598/// Whether a pattern is reachable, or why it is unreachable.
1599///
1600#[derive(Debug, Clone, Copy, PartialEq, Eq)]
1601pub enum Reachability {
1602 Reachable,
1603 Unreachable(UnreachablePatternReason),
1604}
1605
1606/// A type for storing diagnostics produced by the decision tree compiler.
1607///
1608#[derive(Debug)]
1609pub struct Diagnostics {
1610 /// A flag indicating the match is missing one or more pattern.
1611 pub missing: bool,
1612
1613 /// The patterns that are reachable. If a pattern isn't in this list it
1614 /// means it is redundant.
1615 /// Each entry is a pair of indices: The index of the clause the pattern
1616 /// belongs to, followed by the index of the pattern itself within the
1617 /// clause. For example, in this case expression:
1618 /// ```gleam
1619 /// case x {
1620 /// 1 -> todo
1621 /// 2 | 3 -> todo
1622 /// _ -> todo
1623 /// }
1624 /// ```
1625 ///
1626 /// The `3` pattern would be `(1, 1)`, because it is the second pattern of
1627 /// the second clause, and both are zero-indexed.
1628 ///
1629 pub reachable: HashSet<(usize, usize)>,
1630
1631 /// Patterns which match on variants of a type which the compiler
1632 /// can tell will never be present, due to variant inference.
1633 ///
1634 /// See `reachable` for an explanation of its structure.
1635 ///
1636 pub match_impossible_variants: HashSet<(usize, usize)>,
1637}
1638
1639impl<'a> Compiler<'a> {
1640 fn new(environment: &'a Environment<'a>, variable_id: usize, patterns: Arena<Pattern>) -> Self {
1641 Self {
1642 environment,
1643 patterns,
1644 variable_id,
1645 diagnostics: Diagnostics {
1646 missing: false,
1647 reachable: HashSet::new(),
1648 match_impossible_variants: HashSet::new(),
1649 },
1650 }
1651 }
1652
1653 fn pattern(&mut self, pattern_id: Id<Pattern>) -> &mut Pattern {
1654 self.patterns
1655 .get_mut(pattern_id)
1656 .expect("unknown pattern id")
1657 }
1658
1659 /// Returns a new fresh variable (i.e. guaranteed to have a unique `variable_id`)
1660 /// with the given type.
1661 ///
1662 fn fresh_variable(&mut self, type_: Arc<Type>) -> Variable {
1663 let var = Variable::new(self.variable_id, type_);
1664 self.variable_id += 1;
1665 var
1666 }
1667
1668 fn mark_as_reached(&mut self, branch: &Branch) {
1669 let _ = self
1670 .diagnostics
1671 .reachable
1672 .insert((branch.clause_index, branch.alternative_index));
1673 }
1674
1675 fn mark_as_matching_impossible_variant(&mut self, branch: &Branch) {
1676 let _ = self
1677 .diagnostics
1678 .reachable
1679 .remove(&(branch.clause_index, branch.alternative_index));
1680 let _ = self
1681 .diagnostics
1682 .match_impossible_variants
1683 .insert((branch.clause_index, branch.alternative_index));
1684 }
1685
1686 fn compile(&mut self, mut branches: VecDeque<Branch>) -> Decision {
1687 branches
1688 .iter_mut()
1689 .for_each(|branch| branch.move_unconditional_patterns(self));
1690
1691 let Some(first_branch) = branches.front() else {
1692 // If there's no branches, that means we have a pattern that is not
1693 // exhaustive as there's nothing that could match!
1694 self.diagnostics.missing = true;
1695 return Decision::Fail;
1696 };
1697
1698 self.mark_as_reached(first_branch);
1699
1700 // In order to compile the branches, we need to pick a `PatternCheck` from
1701 // the first branch, and use the variable it's pattern matching on to create
1702 // a new node in the tree. All the branches will be split into different
1703 // possible paths of this tree.
1704 match find_pivot_check(first_branch, &branches) {
1705 Some(PatternCheck { var, .. }) => self.split_and_compile_with_pivot_var(var, branches),
1706
1707 // If the branch has no remaining checks, it means that we've moved all
1708 // its variable patterns as assignments into the body and there's no
1709 // additional checks remaining. So the only thing left that could result
1710 // in the match failing is the additional guard.
1711 None => match first_branch.guard {
1712 // If there's no guard we're in the following situation:
1713 // `∅ -> body`. It means that this branch will always match no
1714 // matter what, all the remaining branches are just discarded and
1715 // we can produce a terminating node to run the body
1716 // unconditionally.
1717 None => Decision::run(first_branch.body.clone()),
1718 // If we have a guard we're in this scenario:
1719 // `∅ if condition -> body`. We can produce a `Guard` node:
1720 // if the condition evaluates to `True` we can run its body.
1721 // Otherwise, we'll have to keep looking at the remaining branches
1722 // to know what to do if this branch doesn't match.
1723 Some(guard) => {
1724 let if_true = first_branch.body.clone();
1725 // All the remaining branches will be compiled and end up
1726 // in the path of the tree to choose if the guard is false.
1727 let _ = branches.pop_front();
1728 let if_false = self.compile(branches);
1729 Decision::guard(guard, if_true, if_false)
1730 }
1731 },
1732 }
1733 }
1734
1735 fn split_and_compile_with_pivot_var(
1736 &mut self,
1737 pivot_var: Variable,
1738 branches: VecDeque<Branch>,
1739 ) -> Decision {
1740 // We first try and come up with a list of all the runtime checks we might
1741 // have to perform on the variable at runtime. In most cases it's a limited
1742 // number of checks that we know before hand (for example, when matching
1743 // on a list, or on a custom type).
1744 let branch_mode = pivot_var.branch_mode(self.environment);
1745 let known_checks = match &branch_mode {
1746 // If the type being matched on is infinite there's no known runtime
1747 // check we could come up with in advance. So we'll build them as
1748 // we go.
1749 BranchMode::Infinite => vec![],
1750
1751 // If the type is a tuple there's only one runtime check we could
1752 // perform that actually makes sense.
1753 BranchMode::Tuple { elements } => vec![self.is_tuple_check(elements)],
1754
1755 // If the type being matched on is a list we know the resulting
1756 // decision tree node is only ever going to have two different paths:
1757 // one to follow if the list is empty, and one to follow if it's not.
1758 BranchMode::List { inner_type } => {
1759 vec![
1760 RuntimeCheck::EmptyList,
1761 self.is_list_check(inner_type.clone()),
1762 ]
1763 }
1764
1765 // If we know that a specific variant is inferred we will require just
1766 // that one and not all the other ones we know for sure are not going to
1767 // be there.
1768 BranchMode::NamedType {
1769 constructors,
1770 inferred_variant: Some(index),
1771 } => {
1772 let constructor = constructors
1773 .get(*index)
1774 .expect("wrong index for inferred variant");
1775 vec![self.is_variant_check(*index, constructor)]
1776 }
1777
1778 // Otherwise we know we'll need a check for each of its possible variants.
1779 BranchMode::NamedType { constructors, .. } => constructors
1780 .iter()
1781 .enumerate()
1782 .map(|(index, constructor)| self.is_variant_check(index, constructor))
1783 .collect_vec(),
1784 };
1785
1786 // We then split all the branches using these checks and compile the
1787 // choices they've been split up into.
1788 let mut splitter = BranchSplitter::from_checks(known_checks);
1789 self.split_branches(&mut splitter, branches, pivot_var.clone(), &branch_mode);
1790 if branch_mode.is_infinite() {
1791 // If the branching is infinite, that means we always need to also have
1792 // a fallback (imagine you're pattern matching on an `Int` and put no
1793 // `_` at the end of the case expression).
1794 self.splitter_to_switch(pivot_var, splitter)
1795 } else if splitter.choices.is_empty() {
1796 // If the branching doesn't need any fallback but we ended up with no
1797 // checks it means we're trying to pattern match on an external type
1798 // but haven't provided a catch-all case.
1799 // That's never going to match, so we produce a failure node.
1800 self.diagnostics.missing = true;
1801 Decision::Fail
1802 } else {
1803 // Otherwise we know that one of the possible runtime checks is always
1804 // going to succeed and there's no need to also have a fallback branch.
1805 self.splitter_to_exhaustive_switch(pivot_var, splitter)
1806 }
1807 }
1808
1809 fn split_branches(
1810 &mut self,
1811 splitter: &mut BranchSplitter,
1812 branches: VecDeque<Branch>,
1813 pivot_var: Variable,
1814 branch_mode: &BranchMode,
1815 ) {
1816 for mut branch in branches {
1817 let Some(pattern_check) = branch.pop_check_on_var(&pivot_var) else {
1818 // If the branch doesn't perform any check on the pivot variable, it means
1819 // it could still match no matter what shape `pivot_var` has. So we must
1820 // add it as a fallback branch, that is a branch that is still relevant
1821 // for all possible paths in the decision tree.
1822 splitter.add_fallback_branch(branch);
1823 continue;
1824 };
1825
1826 let checked_pattern = self.pattern(pattern_check.pattern);
1827 if checked_pattern.is_matching_on_unreachable_variant(branch_mode) {
1828 self.mark_as_matching_impossible_variant(&branch);
1829 continue;
1830 }
1831
1832 splitter.add_checked_branch(pattern_check, branch, branch_mode, self);
1833 }
1834 }
1835
1836 /// Compiles the branches in a splitter down to a switch matching on a type
1837 /// with infinite variants (like ints, floats and strings). With a fallaback
1838 /// branch.
1839 ///
1840 fn splitter_to_switch(&mut self, var: Variable, splitter: BranchSplitter) -> Decision {
1841 let choices = self.compile_all_choices(splitter.choices);
1842 let last_choice = self.compile(splitter.fallback);
1843 Decision::Switch {
1844 var,
1845 choices,
1846 fallback: Box::new(last_choice),
1847 fallback_check: FallbackCheck::InfiniteCatchAll,
1848 }
1849 }
1850
1851 /// Compiles the branches in a splitter down to a switch matching on a type
1852 /// with a finite known number of variants.
1853 ///
1854 fn splitter_to_exhaustive_switch(
1855 &mut self,
1856 var: Variable,
1857 splitter: BranchSplitter,
1858 ) -> Decision {
1859 let mut choices = splitter.choices;
1860 let (choices, fallback, fallback_check) =
1861 if choices.iter().any(|(check, _)| check.is_ignored()) {
1862 // If there's any check that is ignored and not explicitly being
1863 // matched on then we want to ignore all of those and clump them
1864 // into a single "fallback" branch to avoid bloating the generated
1865 // tree.
1866 let mut ignored_checks = vec![];
1867 let mut remaining_choices = vec![];
1868 for choice in choices.into_iter() {
1869 if choice.0.is_ignored() {
1870 ignored_checks.push(choice.0)
1871 } else {
1872 remaining_choices.push(choice)
1873 }
1874 }
1875
1876 let fallback_check = FallbackCheck::CatchAll { ignored_checks };
1877 (remaining_choices, splitter.fallback, fallback_check)
1878 } else {
1879 // Otherwise we just use the last check as the final one that
1880 // can be outright skipped.
1881 let (last_check, last_choice) = choices.pop().expect("at least one choice");
1882 let fallback_check = FallbackCheck::RuntimeCheck { check: last_check };
1883 (choices, last_choice, fallback_check)
1884 };
1885
1886 let choices = self.compile_all_choices(choices);
1887 let fallback = Box::new(self.compile(fallback));
1888 Decision::Switch {
1889 var,
1890 choices,
1891 fallback,
1892 fallback_check,
1893 }
1894 }
1895
1896 fn compile_all_choices(
1897 &mut self,
1898 choices: Vec<(RuntimeCheck, VecDeque<Branch>)>,
1899 ) -> Vec<(RuntimeCheck, Box<Decision>)> {
1900 choices
1901 .into_iter()
1902 .map(|(check, branches)| (check, Box::new(self.compile(branches))))
1903 .collect_vec()
1904 }
1905
1906 /// Turns a `RuntimeCheckKind` into a new `RuntimeCheck` by coming up with
1907 /// the needed new fresh variables.
1908 /// All the type information needed to create these variables is in the
1909 /// `branch_mode` arg.
1910 ///
1911 fn fresh_runtime_check(
1912 &mut self,
1913 kind: RuntimeCheckKind,
1914 branch_mode: &BranchMode,
1915 ) -> RuntimeCheck {
1916 match (kind, branch_mode) {
1917 (RuntimeCheckKind::Int { value }, _) => RuntimeCheck::Int {
1918 value: value.clone(),
1919 },
1920 (RuntimeCheckKind::Float { value }, _) => RuntimeCheck::Float {
1921 value: value.clone(),
1922 },
1923 (RuntimeCheckKind::String { value }, _) => RuntimeCheck::String {
1924 value: value.clone(),
1925 },
1926 (RuntimeCheckKind::StringPrefix { prefix }, _) => RuntimeCheck::StringPrefix {
1927 prefix: prefix.clone(),
1928 rest: self.fresh_variable(string()),
1929 },
1930 (RuntimeCheckKind::Tuple { .. }, BranchMode::Tuple { elements }) => {
1931 self.is_tuple_check(elements)
1932 }
1933 (RuntimeCheckKind::Variant { index }, BranchMode::NamedType { constructors, .. }) => {
1934 self.is_variant_check(
1935 index,
1936 constructors.get(index).expect("unknown variant index"),
1937 )
1938 }
1939 (RuntimeCheckKind::EmptyList, _) => RuntimeCheck::EmptyList,
1940 (RuntimeCheckKind::NonEmptyList, BranchMode::List { inner_type }) => {
1941 self.is_list_check(inner_type.clone())
1942 }
1943 (_, _) => unreachable!("type checking should make this impossible"),
1944 }
1945 }
1946
1947 /// Comes up with new pattern cecks that have to match in case a given
1948 /// runtime check succeeds for the given pattern.
1949 ///
1950 /// Let's make an example: when we have a pattern - say `a is Wibble(1, [])` -
1951 /// we come up with a runtime check to perform on it. For our example the
1952 /// runtime check is to make sure that `a` is indeed a `Wibble` variant.
1953 /// However, after successfully performing that check we're left with much to
1954 /// do! We know that `a` is `Wibble` but now we'll have to make sure that its
1955 /// inner arguments also match the given patterns. So the new additional checks
1956 /// we have to add are `a0 is 1, a1 is []` (where `a0` and `a1` are the fresh
1957 /// variable names we use to refer to the constructor's arguments).
1958 ///
1959 fn new_checks(
1960 &mut self,
1961 for_pattern: &Pattern,
1962 after_succeding_check: &RuntimeCheck,
1963 ) -> Vec<PatternCheck> {
1964 match (for_pattern, after_succeding_check) {
1965 // These patterns never result in adding new checks. After a runtime
1966 // check matches on them there's nothing else to discover.
1967 (
1968 Pattern::Discard
1969 | Pattern::Assign { .. }
1970 | Pattern::Variable { .. }
1971 | Pattern::Int { .. }
1972 | Pattern::Float { .. }
1973 | Pattern::BitArray { .. }
1974 | Pattern::EmptyList,
1975 _,
1976 )
1977 | (Pattern::String { .. }, RuntimeCheck::String { .. }) => vec![],
1978
1979 // After making sure a value is not an empty list we'll have to perform
1980 // additional checks on its first item and on the tail.
1981 (
1982 Pattern::NonEmptyList {
1983 first: first_pattern,
1984 rest: rest_pattern,
1985 },
1986 RuntimeCheck::NonEmptyList {
1987 first: first_variable,
1988 rest: rest_variable,
1989 },
1990 ) => vec![
1991 first_variable.is(*first_pattern),
1992 rest_variable.is(*rest_pattern),
1993 ],
1994
1995 // After making sure a value is a specific variant we'll have to check each
1996 // of its arguments respects the given patterns (as shown in the doc example for
1997 // this function!)
1998 (
1999 Pattern::Variant {
2000 fields: patterns, ..
2001 },
2002 RuntimeCheck::Variant {
2003 fields: variables, ..
2004 },
2005 ) => (variables.iter().zip(patterns))
2006 .map(|(field, pattern)| field.is(*pattern))
2007 .collect_vec(),
2008
2009 // Tuples are exactly the same as variants: after making sure we're dealing with
2010 // a tuple, we will have to check that each of its elements matches the given
2011 // pattern: `a is #(1, _)` will result in the following checks
2012 // `a0 is 1, a1 is _` (where `a0` and `a1` are fresh variable names we use to
2013 // refer to each of the tuple's elements).
2014 (
2015 Pattern::Tuple { elements: patterns },
2016 RuntimeCheck::Tuple {
2017 elements: variables,
2018 ..
2019 },
2020 ) => (variables.iter().zip(patterns))
2021 .map(|(element, pattern)| element.is(*pattern))
2022 .collect_vec(),
2023
2024 // Strings are quite fun: if we've checked at runtime a string starts with a given
2025 // prefix and we want to check that it's some overlapping literal value we'll still
2026 // have some amount of work to perform.
2027 //
2028 // Let's have a look at an example: the pattern we care about is `a is "wibble"`
2029 // and we've just successfully ran the runtime check for `a is "wib" <> rest`.
2030 // So we know the string already starts with `"wib"` what we have to check now
2031 // is that the remaining part `rest` is `"ble"`.
2032 (Pattern::String { value }, RuntimeCheck::StringPrefix { prefix, rest, .. }) => {
2033 let remaining = value.strip_prefix(prefix.as_str()).unwrap_or(value);
2034 vec![rest.is(self.string_pattern(remaining))]
2035 }
2036
2037 // String prefixes are similar to strings, but a bit more involved. Let's say we're
2038 // checking the pattern:
2039 //
2040 // ```text
2041 // "wibblest" <> rest1
2042 // ─┬────────
2043 // ╰── We will refer to this as `prefix1`
2044 // ```
2045 //
2046 // And we know that the following overlapping runtime check has already succeeded:
2047 //
2048 // ```text
2049 // "wibble" <> rest0
2050 // ─┬──────
2051 // ╰── We will refer to this as `prefix0`
2052 // ```
2053 //
2054 // We're lucky because we now know quite a bit about the shape of the string. Since
2055 // we know it already starts with `"wibble"` we can just check that the remaining
2056 // part after that starts with the missing part of the prefix:
2057 // `prefix0 is "st" <> rest1`.
2058 (
2059 Pattern::StringPrefix {
2060 prefix: prefix1,
2061 prefix_name: _,
2062 rest: rest1,
2063 },
2064 RuntimeCheck::StringPrefix {
2065 prefix: prefix0,
2066 rest: rest0,
2067 },
2068 ) => {
2069 let remaining = prefix1.strip_prefix(prefix0.as_str()).unwrap_or(prefix1);
2070 // If the prefixes are exactly the same then the only remaining check
2071 // is for the two remaining bits to be the same.
2072 if remaining.is_empty() {
2073 vec![rest0.is(*rest1)]
2074 } else {
2075 vec![rest0.is(self.string_prefix_pattern(remaining, *rest1))]
2076 }
2077 }
2078
2079 (_, _) => unreachable!("invalid pattern overlapping"),
2080 }
2081 }
2082
2083 /// Builds an `IsVariant` runtime check, coming up with new fresh variable names
2084 /// for its arguments.
2085 ///
2086 fn is_variant_check(
2087 &mut self,
2088 index: usize,
2089 constructor: &TypeValueConstructor,
2090 ) -> RuntimeCheck {
2091 RuntimeCheck::Variant {
2092 index,
2093 match_: VariantMatch::NeverExplicitlyMatchedOn {
2094 name: constructor.name.clone(),
2095 },
2096 labels: constructor
2097 .parameters
2098 .iter()
2099 .enumerate()
2100 .filter_map(|(i, parameter)| Some((i, parameter.label.clone()?)))
2101 .collect(),
2102 fields: constructor
2103 .parameters
2104 .iter()
2105 .map(|parameter| parameter.type_.clone())
2106 .map(|type_| self.fresh_variable(type_))
2107 .collect_vec(),
2108 }
2109 }
2110
2111 /// Builds an `IsNonEmptyList` runtime check, coming up with fresh variable
2112 /// names for its arguments.
2113 ///
2114 fn is_list_check(&mut self, inner_type: Arc<Type>) -> RuntimeCheck {
2115 RuntimeCheck::NonEmptyList {
2116 first: self.fresh_variable(inner_type.clone()),
2117 rest: self.fresh_variable(Arc::new(Type::list(inner_type))),
2118 }
2119 }
2120
2121 /// Builds an `IsTuple` runtime check, coming up with fresh variable
2122 /// names for its arguments.
2123 ///
2124 fn is_tuple_check(&mut self, elements: &[Arc<Type>]) -> RuntimeCheck {
2125 RuntimeCheck::Tuple {
2126 size: elements.len(),
2127 elements: elements
2128 .iter()
2129 .map(|type_| self.fresh_variable(type_.clone()))
2130 .collect_vec(),
2131 }
2132 }
2133
2134 /// Allocates a new `StringPattern` with the given value.
2135 ///
2136 fn string_pattern(&mut self, value: &str) -> Id<Pattern> {
2137 self.patterns.alloc(Pattern::String {
2138 value: EcoString::from(value),
2139 })
2140 }
2141
2142 fn bit_array_pattern(&mut self, tests: VecDeque<BitArrayTest>) -> Id<Pattern> {
2143 self.patterns.alloc(Pattern::BitArray { tests })
2144 }
2145
2146 /// Allocates a new `StringPrefix` pattern with the given prefix and pattern
2147 /// for the rest of the string.
2148 ///
2149 fn string_prefix_pattern(&mut self, prefix: &str, rest: Id<Pattern>) -> Id<Pattern> {
2150 self.patterns.alloc(Pattern::StringPrefix {
2151 prefix: EcoString::from(prefix),
2152 prefix_name: None,
2153 rest,
2154 })
2155 }
2156}
2157
2158/// Returns a pattern check from `first_branch` to be used as a pivot to split all
2159/// the `branches`.
2160///
2161fn find_pivot_check(first_branch: &Branch, branches: &VecDeque<Branch>) -> Option<PatternCheck> {
2162 // To try and minimise code duplication, we use the following heuristic: we
2163 // choose the check matching on the variable that is referenced the most
2164 // across all checks in all branches.
2165 let mut var_references = HashMap::new();
2166 for branch in branches {
2167 for check in &branch.checks {
2168 let _ = var_references
2169 .entry(check.var.id)
2170 .and_modify(|references| *references += 1)
2171 .or_insert(0);
2172 }
2173 }
2174
2175 first_branch
2176 .checks
2177 .iter()
2178 .max_by_key(|check| var_references.get(&check.var.id).cloned().unwrap_or(0))
2179 .cloned()
2180}
2181
2182/// A handy data structure we use to split branches in different possible paths
2183/// based on a check.
2184///
2185struct BranchSplitter {
2186 pub choices: Vec<(RuntimeCheck, VecDeque<Branch>)>,
2187 pub fallback: VecDeque<Branch>,
2188
2189 /// This is used to allow quickly looking up a choice in the `choices`
2190 /// vector, without loosing track of the checks' order.
2191 indices: HashMap<RuntimeCheckKind, usize>,
2192
2193 /// This is used to store the indices of just the prefix checks as they have
2194 /// different rules from all the other `RuntimeCheckKinds` whose indices are
2195 /// instead stored in the `indices` field.
2196 ///
2197 /// We discuss this in more detail in the `index_of_overlapping_runtime_check`
2198 /// function!
2199 prefix_indices: Trie<String, usize>,
2200}
2201
2202impl BranchSplitter {
2203 /// Creates a new splitter with the given starting checks.
2204 ///
2205 fn from_checks(checks: Vec<RuntimeCheck>) -> Self {
2206 let mut choices = Vec::with_capacity(checks.len());
2207 let mut indices = HashMap::new();
2208
2209 for (index, runtime_check) in checks.into_iter().enumerate() {
2210 let Some(kind) = runtime_check.kind() else {
2211 continue;
2212 };
2213 let _ = indices.insert(kind, index);
2214 choices.push((runtime_check, VecDeque::new()));
2215 }
2216
2217 Self {
2218 fallback: VecDeque::new(),
2219 choices,
2220 indices,
2221 prefix_indices: Trie::new(),
2222 }
2223 }
2224
2225 /// Add a fallback branch: this is a branch that is relevant to all possible
2226 /// paths as it could still run, no matter the result of any of the `Check`s
2227 /// we've stored!
2228 ///
2229 fn add_fallback_branch(&mut self, branch: Branch) {
2230 self.choices
2231 .iter_mut()
2232 .for_each(|(_, branches)| branches.push_back(branch.clone()));
2233 self.fallback.push_back(branch);
2234 }
2235
2236 /// Given a branch and the pattern its using to check on the pivot variable,
2237 /// adds it to the paths where it's relevant, that is where we know from
2238 /// previous checks that this pattern has a chance of matching.
2239 ///
2240 fn add_checked_branch(
2241 &mut self,
2242 pattern_check: PatternCheck,
2243 mut branch: Branch,
2244 branch_mode: &BranchMode,
2245 compiler: &mut Compiler<'_>,
2246 ) {
2247 let pattern = compiler.pattern(pattern_check.pattern).clone();
2248
2249 // Bit array patterns are split in a different way that requires special
2250 // handling. Instead of reasoning on overlapping checks what we do it we
2251 // always split the decision tree in two distinct paths based on one of
2252 // the bit array pattern's tests.
2253 if let Pattern::BitArray { tests } = pattern {
2254 self.add_checked_bit_array_branch(pattern_check, tests, branch, compiler);
2255 return;
2256 };
2257
2258 let kind = pattern
2259 .to_runtime_check_kind()
2260 .expect("no unconditional patterns left");
2261
2262 let indices_of_overlapping_checks = self.indices_of_overlapping_checks(&kind);
2263 if indices_of_overlapping_checks.is_empty() {
2264 // This is a new choice we haven't yet discovered as it is not overlapping
2265 // with any of the existing ones. So we add it as a possible new path
2266 // we might have to go down to in the decision tree.
2267 self.save_index_of_new_choice(kind.clone());
2268
2269 let check = compiler.fresh_runtime_check(kind, branch_mode);
2270 for new_check in compiler.new_checks(&pattern, &check) {
2271 branch.add_check(new_check);
2272 }
2273 let mut branches = self.fallback.clone();
2274 branches.push_back(branch);
2275
2276 self.choices.push((check, branches));
2277 } else {
2278 // Otherwise, we know that the check for this branch overlaps with
2279 // (possibly more than one) existing checks and so is relevant only
2280 // as part of those existing paths.
2281 // We'll add the branch with its newly discovered checks only to those
2282 // paths.
2283 for index in indices_of_overlapping_checks.iter() {
2284 let (overlapping_check, branches) = self
2285 .choices
2286 .get_mut(*index)
2287 .expect("check to already be a choice");
2288
2289 let mut branch = branch.clone();
2290 for new_check in compiler.new_checks(&pattern, overlapping_check) {
2291 branch.add_check(new_check);
2292 }
2293 branches.push_back(branch);
2294 }
2295 }
2296
2297 // Then we have to update all variant checks with any new name/module
2298 // we might have discovered from the pattern to make sure we're using
2299 // the correct qualification to refer to each constructor.
2300 if let Pattern::Variant { name, module, .. } = pattern {
2301 for index in indices_of_overlapping_checks {
2302 let (check, _) = self
2303 .choices
2304 .get_mut(index)
2305 .expect("check to already be a choice");
2306 if let RuntimeCheck::Variant { match_, .. } = check {
2307 *match_ = VariantMatch::ExplicitlyMatchedOn {
2308 module: module.clone(),
2309 name: name.clone(),
2310 }
2311 }
2312 }
2313 }
2314 }
2315
2316 /// When we work with bit array patterns the splitter follows a different
2317 /// strategy to split branches: instead of trying to create a multiway
2318 /// decision tree with possibly many branches, we create only two branches
2319 /// based on the first segment test we run into.
2320 /// One path is going to be for the branches that can match if the test is
2321 /// successful, and the other one is going to be the usual fallback to go
2322 /// down to if it's not successful.
2323 ///
2324 /// > "And now for the tricky bit..."
2325 /// > <https://youtu.be/lKXe3HUG2l4?si=i1thYB-kjfMU8NSe&t=645>
2326 ///
2327 fn add_checked_bit_array_branch(
2328 &mut self,
2329 pattern_check: PatternCheck,
2330 tests: VecDeque<BitArrayTest>,
2331 mut branch: Branch,
2332 compiler: &mut Compiler<'_>,
2333 ) {
2334 // If we haven't found a test yet we just use the first one we find
2335 // as the pivot to split all the branches.
2336 let pivot_test = match self.choices.as_slice() {
2337 [] => {
2338 let test = tests.front().expect("empty bit array test").clone();
2339 self.choices.push((
2340 RuntimeCheck::BitArray { test: test.clone() },
2341 VecDeque::new(),
2342 ));
2343 test
2344 }
2345 [(RuntimeCheck::BitArray { test }, _)] => test.clone(),
2346 _ => unreachable!("non bit array check when splitting bit array patterns"),
2347 };
2348
2349 let pattern_fails_if_test_succeeds = tests
2350 .iter()
2351 .any(|test| test.fails_if_succeeding(&pivot_test).is_certain());
2352
2353 let pattern_fails_if_test_fails = tests
2354 .iter()
2355 .any(|test| test.fails_if_failing(&pivot_test).is_certain());
2356
2357 // The branch is still relevant for the if_true path if it still has a
2358 // chance of matching knowing that the pivot test has matched.
2359 // So if we know for certain that the pattern would fail, we don't even
2360 // bother adding it to the if_true path.
2361 if !pattern_fails_if_test_succeeds {
2362 // If the branch is relevant we can further simplify it by removing
2363 // all those tests that are guaranteed to succeed. For example,
2364 // if the succeeding pivot test is `size >= 20` there's no point
2365 // in checking that `size >= 10`, we know that's always true in this
2366 // path of the decision tree!
2367 let tests = tests
2368 .into_iter()
2369 .filter(|test| test.succeeds_if_succeeding(&pivot_test) == Confidence::Uncertain)
2370 .collect::<VecDeque<_>>();
2371
2372 let mut branch = branch.clone();
2373 let variable = &pattern_check.var;
2374 branch.add_check(variable.is(compiler.bit_array_pattern(tests)));
2375
2376 // We know that there's always going to be a single choice for the
2377 // successful check, so we get that and add the branch to it.
2378 let (_, if_true_branches) = self
2379 .choices
2380 .get_mut(0)
2381 .expect("bit array compilation with no choice");
2382 if_true_branches.push_back(branch);
2383 }
2384
2385 // Same goes for the if_false branch: knowing the pivot test has failed
2386 // we only want to keep those branches with a pattern that still have a
2387 // chance to match.
2388 if !pattern_fails_if_test_fails {
2389 // The main difference with the if true case is that we have no way
2390 // of pruning the number of needed tests, so we add this check back
2391 // exactly as it is.
2392 branch.add_check(pattern_check);
2393 self.fallback.push_back(branch);
2394 }
2395 }
2396
2397 fn save_index_of_new_choice(&mut self, kind: RuntimeCheckKind) {
2398 let _ = match kind {
2399 RuntimeCheckKind::Int { .. }
2400 | RuntimeCheckKind::Float { .. }
2401 | RuntimeCheckKind::String { .. }
2402 | RuntimeCheckKind::Tuple { .. }
2403 | RuntimeCheckKind::Variant { .. }
2404 | RuntimeCheckKind::EmptyList
2405 | RuntimeCheckKind::NonEmptyList => self.indices.insert(kind, self.choices.len()),
2406
2407 RuntimeCheckKind::StringPrefix { prefix } => self
2408 .prefix_indices
2409 .insert(prefix.to_string(), self.choices.len()),
2410 };
2411 }
2412
2413 fn indices_of_overlapping_checks(&self, kind: &RuntimeCheckKind) -> Vec<usize> {
2414 match kind {
2415 // All these checks will only overlap with a check that is exactly the
2416 // same, so we just look up their index in the `indices` map using the
2417 // kind as the lookup.
2418 RuntimeCheckKind::Int { .. }
2419 | RuntimeCheckKind::Float { .. }
2420 | RuntimeCheckKind::Tuple { .. }
2421 | RuntimeCheckKind::Variant { .. }
2422 | RuntimeCheckKind::EmptyList
2423 | RuntimeCheckKind::NonEmptyList => {
2424 self.indices.get(kind).cloned().into_iter().collect_vec()
2425 }
2426
2427 // String patterns are a bit more tricky as they might end up overlapping
2428 // even if they're not exactly the same kind of check! Let's have a look
2429 // at an example. Say we're compiling these branches:
2430 //
2431 // ```
2432 // a is "wibble" <> rest -> todo
2433 // a is "wibbler" <> rest -> todo
2434 // ```
2435 //
2436 // We use the first (and only) check in the first branch as the pivot and
2437 // now we have to decide where to put the next branch. Is it matching with
2438 // the first one or completely unrelated?
2439 // Since `"wibbler"` starts with `"wibble"` we know it's overlapping and
2440 // it cannot possibly match if the previous one doesn't!
2441 //
2442 // So when we find a `String`/`StringPrefix` pattern we look for a prefix
2443 // among the ones we have discovered so far that could match with it.
2444 // That is, we look for a prefix of the pattern we're checking in the prefix
2445 // trie.
2446 RuntimeCheckKind::StringPrefix { prefix: value } => {
2447 ancestors_values(&self.prefix_indices, value).collect_vec()
2448 }
2449
2450 // Strings are almost exactly the same, except they could also have an exact
2451 // match with other string patterns. So a string pattern could overlap with
2452 // another string pattern (if they're matching on the same value), or with
2453 // one or more string prefix patterns with a matching prefix.
2454 RuntimeCheckKind::String { value } => {
2455 let first_index = self.indices.get(kind).cloned();
2456 first_index
2457 .into_iter()
2458 .chain(ancestors_values(&self.prefix_indices, value))
2459 .collect_vec()
2460 }
2461 }
2462 }
2463}
2464
2465fn ancestors_values(trie: &Trie<String, usize>, key: &str) -> impl Iterator<Item = usize> {
2466 trie.get_ancestor(key)
2467 .into_iter()
2468 .flat_map(|ancestor| ancestor.values().copied())
2469}
2470
2471pub struct ConstructorSpecialiser {
2472 specialised_types: HashMap<u64, Arc<Type>>,
2473}
2474
2475impl ConstructorSpecialiser {
2476 fn specialise_constructors(
2477 constructors: &TypeVariantConstructors,
2478 type_arguments: &[Arc<Type>],
2479 current_module: &EcoString,
2480 type_module: &EcoString,
2481 ) -> Vec<TypeValueConstructor> {
2482 match constructors.opaque {
2483 // If the type is opaque and we are not in the definition module of
2484 // that type, we don't have access to any constructors so we treat
2485 // it the same as an external type.
2486 Opaque::Opaque if current_module != type_module => return Vec::new(),
2487 Opaque::Opaque | Opaque::NotOpaque => {}
2488 };
2489
2490 let specialiser = Self::new(constructors.type_parameters_ids.as_slice(), type_arguments);
2491 constructors
2492 .variants
2493 .iter()
2494 .map(|v| specialiser.specialise_type_value_constructor(v))
2495 .collect_vec()
2496 }
2497
2498 fn new(parameters: &[u64], type_arguments: &[Arc<Type>]) -> Self {
2499 let specialised_types = parameters
2500 .iter()
2501 .copied()
2502 .zip(type_arguments.iter().cloned())
2503 .collect();
2504 Self { specialised_types }
2505 }
2506
2507 fn specialise_type_value_constructor(&self, v: &TypeValueConstructor) -> TypeValueConstructor {
2508 let TypeValueConstructor {
2509 name,
2510 parameters,
2511 documentation,
2512 } = v;
2513 let parameters = parameters
2514 .iter()
2515 .map(|p| TypeValueConstructorField {
2516 type_: self.specialise_type(p.type_.as_ref()),
2517 label: p.label.clone(),
2518 })
2519 .collect_vec();
2520 TypeValueConstructor {
2521 name: name.clone(),
2522 parameters,
2523 documentation: documentation.clone(),
2524 }
2525 }
2526
2527 fn specialise_type(&self, type_: &Type) -> Arc<Type> {
2528 Arc::new(match type_ {
2529 Type::Named {
2530 publicity,
2531 package,
2532 module,
2533 name,
2534 args,
2535 inferred_variant,
2536 } => Type::Named {
2537 publicity: *publicity,
2538 package: package.clone(),
2539 module: module.clone(),
2540 name: name.clone(),
2541 args: args.iter().map(|a| self.specialise_type(a)).collect(),
2542 inferred_variant: *inferred_variant,
2543 },
2544
2545 Type::Fn { args, return_ } => Type::Fn {
2546 args: args.iter().map(|a| self.specialise_type(a)).collect(),
2547 return_: return_.clone(),
2548 },
2549
2550 Type::Var { type_ } => Type::Var {
2551 type_: Arc::new(RefCell::new(self.specialise_var(type_))),
2552 },
2553
2554 Type::Tuple { elements } => Type::Tuple {
2555 elements: elements
2556 .iter()
2557 .map(|element| self.specialise_type(element))
2558 .collect(),
2559 },
2560 })
2561 }
2562
2563 fn specialise_var(&self, type_: &RefCell<TypeVar>) -> TypeVar {
2564 match &*type_.borrow() {
2565 TypeVar::Unbound { id } => TypeVar::Unbound { id: *id },
2566
2567 TypeVar::Link { type_ } => TypeVar::Link {
2568 type_: self.specialise_type(type_.as_ref()),
2569 },
2570
2571 TypeVar::Generic { id } => match self.specialised_types.get(id) {
2572 Some(type_) => TypeVar::Link {
2573 type_: type_.clone(),
2574 },
2575 None => TypeVar::Generic { id: *id },
2576 },
2577 }
2578 }
2579}
2580
2581/// Intermiate data structure that's used to set up everything that's needed by
2582/// the pattern matching compiler and get a case expression ready to be compiled,
2583/// while hiding the intricacies of handling an arena to record different patterns.
2584///
2585pub struct CaseToCompile {
2586 patterns: Arena<Pattern>,
2587 branches: Vec<Branch>,
2588 subject_variables: Vec<Variable>,
2589 /// The number of clauses in this case to compile.
2590 number_of_clauses: usize,
2591 variable_id: usize,
2592}
2593
2594impl CaseToCompile {
2595 pub fn new(subject_types: &[Arc<Type>]) -> Self {
2596 let mut variable_id = 0;
2597 let subject_variables = subject_types
2598 .iter()
2599 .map(|type_| {
2600 let id = variable_id;
2601 variable_id += 1;
2602 Variable::new(id, type_.clone())
2603 })
2604 .collect_vec();
2605
2606 Self {
2607 patterns: Arena::new(),
2608 branches: vec![],
2609 number_of_clauses: 0,
2610 subject_variables,
2611 variable_id,
2612 }
2613 }
2614
2615 /// Registers a `TypedClause` as one of the branches to be compiled.
2616 ///
2617 /// If you don't have a clause and just have a simple `TypedPattern` you want
2618 /// to generate a decision tree for you can use `add_pattern`.
2619 ///
2620 pub fn add_clause(&mut self, branch: &TypedClause) {
2621 let all_patterns =
2622 std::iter::once(&branch.pattern).chain(branch.alternative_patterns.iter());
2623
2624 for (alternative_index, patterns) in all_patterns.enumerate() {
2625 let mut checks = Vec::with_capacity(patterns.len());
2626
2627 // We're doing the zipping ourselves instead of using iters.zip as the
2628 // borrow checker would complain and the only workaround would be to
2629 // allocate an entire new vector each time.
2630 for i in 0..patterns.len() {
2631 let pattern = self.register(patterns.get(i).expect("pattern index"));
2632 let var = self
2633 .subject_variables
2634 .get(i)
2635 .expect("wrong number of subjects");
2636 checks.push(var.is(pattern))
2637 }
2638
2639 let has_guard = branch.guard.is_some();
2640 let branch = Branch::new(self.number_of_clauses, alternative_index, checks, has_guard);
2641 self.branches.push(branch);
2642 }
2643
2644 self.number_of_clauses += 1;
2645 }
2646
2647 /// Add a single pattern as a branch to be compiled.
2648 ///
2649 /// This is useful in case one wants to check exhaustiveness of a single
2650 /// pattern without having a fully fledged `TypedClause` to pass to the `add_clause`
2651 /// method. For example, in `let` destructurings.
2652 ///
2653 pub fn add_pattern(&mut self, pattern: &TypedPattern) {
2654 let pattern = self.register(pattern);
2655 let var = self
2656 .subject_variables
2657 .first()
2658 .expect("wrong number of subject variables for pattern");
2659 let branch = Branch::new(self.number_of_clauses, 0, vec![var.is(pattern)], false);
2660 self.number_of_clauses += 1;
2661 self.branches.push(branch);
2662 }
2663
2664 pub fn compile(self, env: &Environment<'_>) -> CompileCaseResult {
2665 let mut compiler = Compiler::new(env, self.variable_id, self.patterns);
2666
2667 let decision = if self.branches.is_empty() {
2668 let var = self
2669 .subject_variables
2670 .first()
2671 .expect("case with no subjects")
2672 .clone();
2673
2674 compiler.split_and_compile_with_pivot_var(var, VecDeque::new())
2675 } else {
2676 compiler.compile(self.branches.into())
2677 };
2678
2679 CompileCaseResult {
2680 diagnostics: compiler.diagnostics,
2681 compiled_case: CompiledCase {
2682 tree: decision,
2683 subject_variables: self.subject_variables,
2684 },
2685 }
2686 }
2687
2688 /// Registers a typed pattern (and all its sub-patterns) into this
2689 /// `CaseToCompile`'s pattern arena, returning an id to get the pattern back.
2690 ///
2691 fn register(&mut self, pattern: &TypedPattern) -> Id<Pattern> {
2692 match pattern {
2693 TypedPattern::Invalid { .. } => self.insert(Pattern::Discard),
2694 TypedPattern::Discard { .. } => self.insert(Pattern::Discard),
2695
2696 TypedPattern::Int { value, .. } => {
2697 let value = value.clone();
2698 self.insert(Pattern::Int { value })
2699 }
2700
2701 TypedPattern::Float { value, .. } => {
2702 let value = value.clone();
2703 self.insert(Pattern::Float { value })
2704 }
2705
2706 TypedPattern::String { value, .. } => {
2707 let value = value.clone();
2708 self.insert(Pattern::String { value })
2709 }
2710
2711 TypedPattern::Variable { name, .. } => {
2712 let name = name.clone();
2713 self.insert(Pattern::Variable { name })
2714 }
2715
2716 TypedPattern::Assign { name, pattern, .. } => {
2717 let name = name.clone();
2718 let pattern = self.register(pattern);
2719 self.insert(Pattern::Assign { name, pattern })
2720 }
2721
2722 TypedPattern::Tuple { elements, .. } => {
2723 let elements = elements
2724 .iter()
2725 .map(|element| self.register(element))
2726 .collect_vec();
2727 self.insert(Pattern::Tuple { elements })
2728 }
2729
2730 TypedPattern::List { elements, tail, .. } => {
2731 let mut list = match tail {
2732 Some(tail) => self.register(tail),
2733 None => self.insert(Pattern::EmptyList),
2734 };
2735 for element in elements.iter().rev() {
2736 let first = self.register(element);
2737 list = self.insert(Pattern::NonEmptyList { first, rest: list });
2738 }
2739 list
2740 }
2741
2742 TypedPattern::Constructor {
2743 arguments,
2744 constructor,
2745 name,
2746 module,
2747 ..
2748 } => {
2749 let index = constructor.expect_ref("must be inferred").constructor_index as usize;
2750 let module = module.as_ref().map(|(module, _)| module.clone());
2751 let fields = arguments
2752 .iter()
2753 .map(|argument| self.register(&argument.value))
2754 .collect_vec();
2755 self.insert(Pattern::Variant {
2756 name: name.clone(),
2757 module,
2758 index,
2759 fields,
2760 })
2761 }
2762
2763 TypedPattern::BitArray { segments, .. } => {
2764 let tests = self.bit_array_to_tests(segments);
2765 self.insert(Pattern::BitArray { tests })
2766 }
2767
2768 TypedPattern::StringPrefix {
2769 left_side_string,
2770 left_side_assignment,
2771 right_side_assignment,
2772 ..
2773 } => {
2774 let prefix = left_side_string.clone();
2775 let prefix_name = left_side_assignment
2776 .as_ref()
2777 .map(|(label, _)| label.clone());
2778 let rest_pattern = match right_side_assignment {
2779 AssignName::Variable(name) => Pattern::Variable { name: name.clone() },
2780 AssignName::Discard(_) => Pattern::Discard,
2781 };
2782 let rest = self.insert(rest_pattern);
2783 self.insert(Pattern::StringPrefix {
2784 prefix,
2785 prefix_name,
2786 rest,
2787 })
2788 }
2789
2790 TypedPattern::BitArraySize { .. } => {
2791 unreachable!("Cannot convert BitArraySize to exhaustiveness pattern")
2792 }
2793 }
2794 }
2795
2796 fn insert(&mut self, pattern: Pattern) -> Id<Pattern> {
2797 self.patterns.alloc(pattern)
2798 }
2799
2800 fn bit_array_to_tests(
2801 &mut self,
2802 segments: &[TypedPatternBitArraySegment],
2803 ) -> VecDeque<BitArrayTest> {
2804 // If there's no segments then we just add a single check to make sure
2805 // the bit array is empty.
2806 if segments.is_empty() {
2807 let mut test = VecDeque::new();
2808 test.push_front(BitArrayTest::Size(SizeTest {
2809 operator: SizeOperator::Equal,
2810 size: Offset::constant(0),
2811 }));
2812 return test;
2813 }
2814
2815 let mut previous_end = Offset::constant(0);
2816 let mut tests = VecDeque::with_capacity(segments.len() * 2);
2817 let mut pattern_variables = HashMap::new();
2818
2819 let segments_count = segments.len();
2820 for (i, segment) in segments.iter().enumerate() {
2821 let segment_size = segment_size(segment, &pattern_variables, None);
2822
2823 // If we're reading a variable number of bits we need to make sure
2824 // that that variable is not negative!
2825 if let ReadSize::VariableBits { variable, .. } = &segment_size {
2826 match variable.as_ref() {
2827 // If the size variable comes from reading an unsigned
2828 // number we know that it can't be negative! So we can skip
2829 // checking it.
2830 VariableUsage::PatternSegment(_, read_action) if !read_action.signed => (),
2831
2832 // Otherwise we must make sure that the read size is not
2833 // negative.
2834 VariableUsage::PatternSegment(..) | VariableUsage::OutsideVariable(_) => tests
2835 .push_back(BitArrayTest::VariableIsNotNegative {
2836 variable: variable.as_ref().clone(),
2837 }),
2838 }
2839 }
2840
2841 // All segments but the last will require the original bit array to
2842 // have a minimum number of bits for the pattern to succeed. The
2843 // final segment is special as it could require a specific size, or
2844 // be a catch all that matches with any number of remaining bits.
2845 let is_last_segment = i + 1 == segments_count;
2846 match &segment_size {
2847 ReadSize::RemainingBits => (),
2848 ReadSize::RemainingBytes => tests.push_back(BitArrayTest::CatchAllIsBytes {
2849 size_so_far: previous_end.clone(),
2850 }),
2851 segment_size => {
2852 let size = previous_end.clone().add_size(segment_size);
2853 let operator = if is_last_segment {
2854 SizeOperator::Equal
2855 } else {
2856 SizeOperator::GreaterEqual
2857 };
2858 tests.push_back(BitArrayTest::Size(SizeTest { operator, size }));
2859 }
2860 };
2861
2862 // Each segment is also turned into a match test, checking the
2863 // selected bits match with the pattern's value.
2864 let value = segment_matched_value(segment, None);
2865
2866 let type_ = match &segment.type_ {
2867 type_ if type_.is_int() => ReadType::Int,
2868 type_ if type_.is_float() => ReadType::Float,
2869 type_ if type_.is_string() => ReadType::String,
2870 type_ if type_.is_bit_array() => ReadType::BitArray,
2871 type_ if type_.is_utf_codepoint() => ReadType::UtfCodepoint,
2872 x => panic!("invalid segment type in exhaustiveness {x:?}"),
2873 };
2874
2875 let read_action = ReadAction {
2876 size: segment_size.clone(),
2877 from: previous_end.clone(),
2878 type_,
2879 endianness: segment.endianness(),
2880 signed: segment.signed(),
2881 };
2882
2883 // Then if the matched value is a variable that is in scope for the
2884 // rest of the pattern we keep track of it, so it can be used in the
2885 // following read actions as a valid size.
2886 match &value {
2887 BitArrayMatchedValue::LiteralFloat(_)
2888 | BitArrayMatchedValue::LiteralInt(_)
2889 | BitArrayMatchedValue::LiteralString { .. }
2890 | BitArrayMatchedValue::Discard(_) => {}
2891 BitArrayMatchedValue::Variable(name)
2892 | BitArrayMatchedValue::Assign { name, .. } => {
2893 let _ = pattern_variables.insert(name.clone(), read_action.clone());
2894 }
2895 }
2896
2897 // If we are matching on a float segment that is not a literal we want
2898 // to add an additional check to make sure that we won't match with
2899 // `NaN` and `Infinity`!
2900 if type_.is_float() && !value.is_literal() {
2901 tests.push_back(BitArrayTest::SegmentIsFiniteFloat {
2902 read_action: read_action.clone(),
2903 });
2904 }
2905 tests.push_back(BitArrayTest::Match(MatchTest { value, read_action }));
2906
2907 previous_end = previous_end.add_size(&segment_size);
2908 }
2909 tests
2910 }
2911}
2912
2913fn segment_matched_value(
2914 segment: &TypedPatternBitArraySegment,
2915 // If we are compiling an assignment pattern, we still need access to the
2916 // `type_` and `options` fields of the `segment`, so we must still pass that
2917 // in above. However, we need to check the correct sub-pattern of the original
2918 // pattern, so if they are different we set this argument to `Some`.
2919 pattern: Option<&TypedPattern>,
2920) -> BitArrayMatchedValue {
2921 let pattern = pattern.unwrap_or(&segment.value);
2922 match pattern {
2923 ast::Pattern::Int { int_value, .. } => BitArrayMatchedValue::LiteralInt(int_value.clone()),
2924 ast::Pattern::Float { value, .. } => BitArrayMatchedValue::LiteralFloat(value.clone()),
2925 ast::Pattern::String { value, .. } if segment.has_utf16_option() => {
2926 BitArrayMatchedValue::LiteralString {
2927 value: value.clone(),
2928 encoding: StringEncoding::Utf16,
2929 }
2930 }
2931 ast::Pattern::String { value, .. } if segment.has_utf32_option() => {
2932 BitArrayMatchedValue::LiteralString {
2933 value: value.clone(),
2934 encoding: StringEncoding::Utf32,
2935 }
2936 }
2937 ast::Pattern::String { value, .. } => BitArrayMatchedValue::LiteralString {
2938 value: value.clone(),
2939 encoding: StringEncoding::Utf8,
2940 },
2941 ast::Pattern::Variable { name, .. } => BitArrayMatchedValue::Variable(name.clone()),
2942 ast::Pattern::Discard { name, .. } => BitArrayMatchedValue::Discard(name.clone()),
2943 ast::Pattern::Assign { name, pattern, .. } => BitArrayMatchedValue::Assign {
2944 name: name.clone(),
2945 value: Box::new(segment_matched_value(segment, Some(pattern))),
2946 },
2947 x => panic!("unexpected segment value pattern {x:?}"),
2948 }
2949}
2950
2951fn segment_size(
2952 segment: &TypedPatternBitArraySegment,
2953 pattern_variables: &HashMap<EcoString, ReadAction>,
2954 // If we are compiling an assignment pattern, we still need access to the
2955 // `type_` and `options` fields of the `segment`, so we must still pass that
2956 // in above. However, we need to check the correct sub-pattern of the original
2957 // pattern, so if they are different we set this argument to `Some`.
2958 pattern: Option<&TypedPattern>,
2959) -> ReadSize {
2960 let pattern = pattern.unwrap_or(&segment.value);
2961
2962 match segment.size() {
2963 // The size of a segment must be a `BitArraySize` pattern.
2964 Some(ast::Pattern::BitArraySize(size)) => bit_array_size(segment, pattern_variables, size),
2965 Some(x) => panic!("invalid pattern size made it to code generation {x:?}"),
2966
2967 // If a segment has the `bits`/`bytes` option and has no size, that
2968 // means it's the final catch all segment: we'll have to read any number
2969 // of bits.
2970 _ if segment.has_bits_option() => ReadSize::RemainingBits,
2971 _ if segment.has_bytes_option() => ReadSize::RemainingBytes,
2972
2973 // If there's no size option we go for a default: 8 bits for int
2974 // segments, and 64 for anything else.
2975 None if segment.type_.is_int() => ReadSize::ConstantBits(8.into()),
2976 None => match pattern {
2977 ast::Pattern::Assign { pattern, .. } => {
2978 segment_size(segment, pattern_variables, Some(pattern))
2979 }
2980
2981 ast::Pattern::String { value, .. } if segment.has_utf16_option() => {
2982 ReadSize::ConstantBits(
2983 // Each utf16 code unit is 16 bits
2984 length_utf16(&convert_string_escape_chars(value)) * BigInt::from(16),
2985 )
2986 }
2987 ast::Pattern::String { value, .. } if segment.has_utf32_option() => {
2988 // Each utf32 code unit is 32 bits
2989 ReadSize::ConstantBits(
2990 length_utf32(&convert_string_escape_chars(value)) * BigInt::from(32),
2991 )
2992 }
2993 // If the segment is a literal string then it has an automatic size
2994 // given by its number of bytes.
2995 ast::Pattern::String { value, .. } => {
2996 ReadSize::ConstantBits(convert_string_escape_chars(value).len() * BigInt::from(8))
2997 }
2998 // In all other cases the segment is considered to be 64 bits.
2999 _ => ReadSize::ConstantBits(64.into()),
3000 },
3001 }
3002}
3003
3004fn bit_array_size(
3005 segment: &TypedPatternBitArraySegment,
3006 pattern_variables: &HashMap<EcoString, ReadAction>,
3007 size: &TypedBitArraySize,
3008) -> ReadSize {
3009 match size {
3010 BitArraySize::Int { int_value, .. } => ReadSize::ConstantBits(int_value * segment.unit()),
3011 BitArraySize::Variable { name, .. } => {
3012 let variable = match pattern_variables.get(name) {
3013 Some(read_action) => {
3014 VariableUsage::PatternSegment(name.clone(), read_action.clone())
3015 }
3016 None => VariableUsage::OutsideVariable(name.clone()),
3017 };
3018 ReadSize::VariableBits {
3019 variable: Box::new(variable),
3020 unit: segment.unit(),
3021 }
3022 }
3023 _ => todo!(),
3024 }
3025}
3026
3027/// Returns `true` if one bag is a superset of the other: that is it contains
3028/// all the keys of `other` in a quantity that's greater or equal.
3029///
3030#[must_use]
3031fn superset(
3032 one: &im::HashMap<VariableUsage, usize>,
3033 other: &im::HashMap<VariableUsage, usize>,
3034) -> bool {
3035 other
3036 .iter()
3037 .all(|(key, other_occurrences)| match one.get(key) {
3038 Some(occurrences) => occurrences >= other_occurrences,
3039 None => false,
3040 })
3041}