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