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