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