match_lang/pat.rs
1//! Patterns and match arms, as the caller builds them.
2//!
3//! A [`Pat`] is an owned tree. Everything that walks one (`Drop`, `Clone`,
4//! `Display`, and the checker's flattening pass) does so with an explicit
5//! stack, so a pattern nested a hundred thousand levels deep is as safe as a
6//! shallow one.
7
8use alloc::vec::Vec;
9use core::fmt;
10
11/// What a single pattern node tests. Private: callers build nodes through
12/// [`Pat`]'s constructors, which keep each kind's children consistent.
13#[derive(Clone, Copy, Debug, PartialEq, Eq)]
14pub(crate) enum PatKind {
15 /// `_`: matches every value; no children.
16 Wild,
17 /// `p | q | ...`: children are the alternatives.
18 Or,
19 /// Variant `index` of a sum type; children are its fields.
20 Variant(u32),
21 /// The single constructor of a product type; children are its fields.
22 Product,
23 /// `true` or `false`.
24 Bool(bool),
25 /// An inclusive integer range; `lo == hi` for a single value.
26 Int { lo: i128, hi: i128 },
27 /// An inclusive range of Unicode scalar values.
28 Char { lo: char, hi: char },
29 /// An opaque literal, identified by the caller's id.
30 Lit(u64),
31 /// A slice or array pattern. The first `prefix` children come before the
32 /// `..`, the rest after it; without `rest` there is no `..` and every
33 /// child is in the prefix.
34 Slice { prefix: u32, rest: bool },
35}
36
37/// A pattern: the left-hand side of one match arm, or a part of one.
38///
39/// Patterns are built bottom-up with the constructors below and describe
40/// values of the type they are checked against, in terms of the
41/// [`Signature`](crate::Signature) the [`Model`](crate::Model) gives that
42/// type. Which constructor fits which signature:
43///
44/// | Signature | Patterns |
45/// |---|---|
46/// | `Sum` | [`variant`](Pat::variant) |
47/// | `Product` | [`product`](Pat::product) |
48/// | `Bool` | [`bool`](Pat::bool) |
49/// | `Int`, `BigInt` | [`int`](Pat::int), [`range`](Pat::range) |
50/// | `Char` | [`char`](Pat::char), [`char_range`](Pat::char_range) |
51/// | `Opaque` | [`lit`](Pat::lit) |
52/// | `Array`, `Slice` | [`slice`](Pat::slice), [`slice_rest`](Pat::slice_rest) |
53/// | any | [`wild`](Pat::wild), [`or`](Pat::or) |
54///
55/// A binding such as `x` or `x @ p` is, for matching purposes, `_` or `p`.
56///
57/// # Node numbering
58///
59/// Diagnostics about part of a pattern (see
60/// [`Redundant`](crate::Redundant)) name the part by its **preorder index**
61/// in the arm's pattern: the root is node 0, and each node is followed by
62/// its children (fields, alternatives, or slice elements, prefix before
63/// suffix) left to right, each child's whole subtree before the next child.
64///
65/// # Examples
66///
67/// ```
68/// use match_lang::Pat;
69///
70/// // `Some(1 | 2..=5)`, with `Some` as variant 1 of its sum type.
71/// let pat = Pat::variant(1, [Pat::or([Pat::int(1), Pat::range(2, 5)])]);
72/// assert_eq!(pat.to_string(), "#1(1 | 2..=5)");
73/// ```
74pub struct Pat {
75 pub(crate) kind: PatKind,
76 pub(crate) children: Vec<Pat>,
77}
78
79impl Pat {
80 fn leaf(kind: PatKind) -> Pat {
81 Pat {
82 kind,
83 children: Vec::new(),
84 }
85 }
86
87 /// The wildcard `_`, which matches every value of any type. A binding
88 /// pattern (`x`) is a wildcard to the checker.
89 ///
90 /// # Examples
91 ///
92 /// ```
93 /// use match_lang::Pat;
94 ///
95 /// assert_eq!(Pat::wild().to_string(), "_");
96 /// ```
97 #[must_use]
98 pub fn wild() -> Pat {
99 Pat::leaf(PatKind::Wild)
100 }
101
102 /// Variant `index` of a [`Sum`](crate::Signature::Sum) type, with one
103 /// pattern per field of that variant, in field order.
104 ///
105 /// The number of fields must match what the model's
106 /// [`fields`](crate::Model::fields) reports for the variant; a mismatch
107 /// is reported as [`Reason::Fields`](crate::Reason::Fields).
108 ///
109 /// # Examples
110 ///
111 /// ```
112 /// use match_lang::Pat;
113 ///
114 /// let none = Pat::variant(0, []);
115 /// let some = Pat::variant(1, [Pat::wild()]);
116 /// assert_eq!(none.to_string(), "#0");
117 /// assert_eq!(some.to_string(), "#1(_)");
118 /// ```
119 #[must_use]
120 pub fn variant(index: u32, fields: impl IntoIterator<Item = Pat>) -> Pat {
121 Pat {
122 kind: PatKind::Variant(index),
123 children: fields.into_iter().collect(),
124 }
125 }
126
127 /// The single constructor of a [`Product`](crate::Signature::Product)
128 /// type: a tuple, struct, record, box, or reference. One pattern per
129 /// field, in the field order the model reports; a struct pattern with
130 /// `..` is written with `_` for the omitted fields.
131 ///
132 /// # Examples
133 ///
134 /// ```
135 /// use match_lang::Pat;
136 ///
137 /// let pair = Pat::product([Pat::bool(true), Pat::wild()]);
138 /// assert_eq!(pair.to_string(), "(true, _)");
139 /// ```
140 #[must_use]
141 pub fn product(fields: impl IntoIterator<Item = Pat>) -> Pat {
142 Pat {
143 kind: PatKind::Product,
144 children: fields.into_iter().collect(),
145 }
146 }
147
148 /// A boolean literal, for a [`Bool`](crate::Signature::Bool) type.
149 ///
150 /// # Examples
151 ///
152 /// ```
153 /// use match_lang::Pat;
154 ///
155 /// assert_eq!(Pat::bool(false).to_string(), "false");
156 /// ```
157 #[must_use]
158 pub fn bool(value: bool) -> Pat {
159 Pat::leaf(PatKind::Bool(value))
160 }
161
162 /// An integer literal, for an [`Int`](crate::Signature::Int) or
163 /// [`BigInt`](crate::Signature::BigInt) type. Equivalent to
164 /// `Pat::range(value, value)`.
165 ///
166 /// # Examples
167 ///
168 /// ```
169 /// use match_lang::Pat;
170 ///
171 /// assert_eq!(Pat::int(-7).to_string(), "-7");
172 /// ```
173 #[must_use]
174 pub fn int(value: i128) -> Pat {
175 Pat::range(value, value)
176 }
177
178 /// An inclusive integer range `lo..=hi`. An exclusive range `lo..hi` is
179 /// `range(lo, hi - 1)`; a half-open range takes the type's bound for the
180 /// open end. `lo > hi` is reported as
181 /// [`Reason::EmptyRange`](crate::Reason::EmptyRange), and a range that
182 /// leaves an `Int` type's bounds as
183 /// [`Reason::OutOfDomain`](crate::Reason::OutOfDomain).
184 ///
185 /// # Examples
186 ///
187 /// ```
188 /// use match_lang::Pat;
189 ///
190 /// assert_eq!(Pat::range(0, 9).to_string(), "0..=9");
191 /// ```
192 #[must_use]
193 pub fn range(lo: i128, hi: i128) -> Pat {
194 Pat::leaf(PatKind::Int { lo, hi })
195 }
196
197 /// A character literal, for a [`Char`](crate::Signature::Char) type.
198 ///
199 /// # Examples
200 ///
201 /// ```
202 /// use match_lang::Pat;
203 ///
204 /// assert_eq!(Pat::char('x').to_string(), "'x'");
205 /// ```
206 #[must_use]
207 pub fn char(value: char) -> Pat {
208 Pat::char_range(value, value)
209 }
210
211 /// An inclusive character range `lo..=hi`. It covers every Unicode scalar
212 /// value between the two, so a range across the surrogate block simply
213 /// skips it.
214 ///
215 /// # Examples
216 ///
217 /// ```
218 /// use match_lang::Pat;
219 ///
220 /// assert_eq!(Pat::char_range('a', 'z').to_string(), "'a'..='z'");
221 /// ```
222 #[must_use]
223 pub fn char_range(lo: char, hi: char) -> Pat {
224 Pat::leaf(PatKind::Char { lo, hi })
225 }
226
227 /// An opaque literal, for an [`Opaque`](crate::Signature::Opaque) type
228 /// such as strings or floats compared by equality. Two literals are the
229 /// same value exactly when their ids are equal, so the caller interns
230 /// the literal (for example a string through `intern-lang`) and passes
231 /// the id.
232 ///
233 /// # Examples
234 ///
235 /// ```
236 /// use match_lang::Pat;
237 ///
238 /// assert_eq!(Pat::lit(3).to_string(), "lit#3");
239 /// ```
240 #[must_use]
241 pub fn lit(id: u64) -> Pat {
242 Pat::leaf(PatKind::Lit(id))
243 }
244
245 /// An or-pattern: matches when any alternative matches, trying them left
246 /// to right. Alternatives may themselves be or-patterns. An or-pattern
247 /// with no alternatives matches nothing.
248 ///
249 /// # Examples
250 ///
251 /// ```
252 /// use match_lang::Pat;
253 ///
254 /// let p = Pat::or([Pat::int(1), Pat::int(2)]);
255 /// assert_eq!(p.to_string(), "1 | 2");
256 /// ```
257 #[must_use]
258 pub fn or(alternatives: impl IntoIterator<Item = Pat>) -> Pat {
259 Pat {
260 kind: PatKind::Or,
261 children: alternatives.into_iter().collect(),
262 }
263 }
264
265 /// A fixed-length slice or array pattern `[p1, ..., pn]`: matches a
266 /// sequence of exactly `n` elements. Against an
267 /// [`Array`](crate::Signature::Array) type, `n` must equal the array's
268 /// length ([`Reason::Length`](crate::Reason::Length) otherwise).
269 ///
270 /// # Examples
271 ///
272 /// ```
273 /// use match_lang::Pat;
274 ///
275 /// assert_eq!(Pat::slice([Pat::int(1), Pat::wild()]).to_string(), "[1, _]");
276 /// ```
277 #[must_use]
278 pub fn slice(elements: impl IntoIterator<Item = Pat>) -> Pat {
279 let children: Vec<Pat> = elements.into_iter().collect();
280 let prefix = u32::try_from(children.len()).unwrap_or(u32::MAX);
281 Pat {
282 kind: PatKind::Slice {
283 prefix,
284 rest: false,
285 },
286 children,
287 }
288 }
289
290 /// A slice pattern with a rest, `[p1, ..., pk, .., q1, ..., qm]`:
291 /// matches any sequence of at least `k + m` elements whose first `k` match
292 /// `prefix` and whose last `m` match `suffix`.
293 ///
294 /// # Examples
295 ///
296 /// ```
297 /// use match_lang::Pat;
298 ///
299 /// let first_and_last = Pat::slice_rest([Pat::int(0)], [Pat::int(9)]);
300 /// assert_eq!(first_and_last.to_string(), "[0, .., 9]");
301 /// assert_eq!(Pat::slice_rest([], []).to_string(), "[..]");
302 /// ```
303 #[must_use]
304 pub fn slice_rest(
305 prefix: impl IntoIterator<Item = Pat>,
306 suffix: impl IntoIterator<Item = Pat>,
307 ) -> Pat {
308 let mut children: Vec<Pat> = prefix.into_iter().collect();
309 let prefix = u32::try_from(children.len()).unwrap_or(u32::MAX);
310 children.extend(suffix);
311 Pat {
312 kind: PatKind::Slice { prefix, rest: true },
313 children,
314 }
315 }
316}
317
318impl Drop for Pat {
319 /// Drops the tree with an explicit stack instead of recursion.
320 fn drop(&mut self) {
321 // Leaves and flat patterns, the overwhelmingly common case, need no
322 // stack at all.
323 if self.children.iter().all(|c| c.children.is_empty()) {
324 return;
325 }
326 let mut stack = core::mem::take(&mut self.children);
327 while let Some(mut pat) = stack.pop() {
328 stack.append(&mut pat.children);
329 // `pat` now has no children, so dropping it does not recurse.
330 }
331 }
332}
333
334impl Clone for Pat {
335 /// Clones the tree with an explicit stack instead of recursion.
336 fn clone(&self) -> Pat {
337 // `work` holds nodes whose children are being cloned, with the index
338 // of the next child; `done` holds finished clones, children of the
339 // node on top of `work` last.
340 let mut work: Vec<(&Pat, usize)> = Vec::new();
341 let mut done: Vec<Pat> = Vec::new();
342 work.push((self, 0));
343 while let Some(top) = work.last_mut() {
344 let (pat, next) = *top;
345 if let Some(child) = pat.children.get(next) {
346 top.1 += 1;
347 work.push((child, 0));
348 continue;
349 }
350 let _finished = work.pop();
351 let children = done.split_off(done.len().saturating_sub(pat.children.len()));
352 done.push(Pat {
353 kind: pat.kind,
354 children,
355 });
356 }
357 // The root is the only clone left once its own children were taken.
358 done.pop().unwrap_or_else(Pat::wild)
359 }
360}
361
362/// A step of the iterative pattern printer.
363enum Print<'a> {
364 Pat(&'a Pat),
365 Text(&'static str),
366}
367
368impl fmt::Display for Pat {
369 /// Prints the pattern in a neutral syntax: `_`, `#i(..)` for variants,
370 /// `(..)` for products, literals and `lo..=hi` ranges, `lit#id` for opaque
371 /// literals, `[..]` for slices, and `p | q` for alternatives.
372 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
373 let mut stack = Vec::new();
374 stack.push(Print::Pat(self));
375 while let Some(item) = stack.pop() {
376 let pat = match item {
377 Print::Text(text) => {
378 f.write_str(text)?;
379 continue;
380 }
381 Print::Pat(pat) => pat,
382 };
383 let (open, close, sep) = match pat.kind {
384 PatKind::Wild => {
385 f.write_str("_")?;
386 continue;
387 }
388 PatKind::Bool(b) => {
389 write!(f, "{b}")?;
390 continue;
391 }
392 PatKind::Int { lo, hi } => {
393 if lo == hi {
394 write!(f, "{lo}")?;
395 } else {
396 write!(f, "{lo}..={hi}")?;
397 }
398 continue;
399 }
400 PatKind::Char { lo, hi } => {
401 if lo == hi {
402 write!(f, "{lo:?}")?;
403 } else {
404 write!(f, "{lo:?}..={hi:?}")?;
405 }
406 continue;
407 }
408 PatKind::Lit(id) => {
409 write!(f, "lit#{id}")?;
410 continue;
411 }
412 PatKind::Or if pat.children.is_empty() => {
413 f.write_str("!")?;
414 continue;
415 }
416 PatKind::Or => ("", "", " | "),
417 PatKind::Variant(index) => {
418 write!(f, "#{index}")?;
419 if pat.children.is_empty() {
420 continue;
421 }
422 ("(", ")", ", ")
423 }
424 PatKind::Product if pat.children.len() == 1 => ("(", ",)", ", "),
425 PatKind::Product => ("(", ")", ", "),
426 PatKind::Slice { prefix, rest } => {
427 f.write_str("[")?;
428 stack.push(Print::Text("]"));
429 let split = (prefix as usize).min(pat.children.len());
430 let (pre, post) = pat.children.split_at(split);
431 push_list(&mut stack, post, ", ");
432 if rest {
433 match (pre.is_empty(), post.is_empty()) {
434 (true, true) => stack.push(Print::Text("..")),
435 (true, false) => stack.push(Print::Text(".., ")),
436 (false, true) => stack.push(Print::Text(", ..")),
437 (false, false) => stack.push(Print::Text(", .., ")),
438 }
439 } else if !pre.is_empty() && !post.is_empty() {
440 stack.push(Print::Text(", "));
441 }
442 push_list(&mut stack, pre, ", ");
443 continue;
444 }
445 };
446 f.write_str(open)?;
447 stack.push(Print::Text(close));
448 push_list(&mut stack, &pat.children, sep);
449 }
450 Ok(())
451 }
452}
453
454/// Pushes `items` so that they pop in order, separated by `sep`.
455fn push_list<'a>(stack: &mut Vec<Print<'a>>, items: &'a [Pat], sep: &'static str) {
456 for (i, item) in items.iter().enumerate().rev() {
457 stack.push(Print::Pat(item));
458 if i > 0 {
459 stack.push(Print::Text(sep));
460 }
461 }
462}
463
464impl fmt::Debug for Pat {
465 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
466 write!(f, "Pat({self})")
467 }
468}
469
470/// One arm of a match: a pattern, and whether the arm has a guard.
471///
472/// A guard is treated as possibly failing: a guarded arm never makes later
473/// arms unreachable and never counts toward exhaustiveness, but it is itself
474/// reachable whenever a value matching its pattern can get past the earlier
475/// unguarded arms. With an or-pattern, the guard is assumed to be tried again
476/// for each alternative that matches, so alternatives of a guarded arm never
477/// make each other redundant.
478///
479/// # Examples
480///
481/// ```
482/// use match_lang::{Arm, Pat};
483///
484/// let plain = Arm::new(Pat::wild());
485/// let guarded = Arm::guarded(Pat::int(0));
486/// assert!(!plain.is_guarded());
487/// assert!(guarded.is_guarded());
488/// assert_eq!(guarded.pat().to_string(), "0");
489/// ```
490#[derive(Clone, Debug)]
491pub struct Arm {
492 pat: Pat,
493 guarded: bool,
494}
495
496impl Arm {
497 /// An arm without a guard.
498 ///
499 /// # Examples
500 ///
501 /// ```
502 /// use match_lang::{Arm, Pat};
503 ///
504 /// let arm = Arm::new(Pat::bool(true));
505 /// assert!(!arm.is_guarded());
506 /// ```
507 #[must_use]
508 pub fn new(pat: Pat) -> Arm {
509 Arm {
510 pat,
511 guarded: false,
512 }
513 }
514
515 /// An arm with a guard (`pat if condition`). The condition itself is not
516 /// analysed.
517 ///
518 /// # Examples
519 ///
520 /// ```
521 /// use match_lang::{Arm, Pat};
522 ///
523 /// let arm = Arm::guarded(Pat::wild());
524 /// assert!(arm.is_guarded());
525 /// ```
526 #[must_use]
527 pub fn guarded(pat: Pat) -> Arm {
528 Arm { pat, guarded: true }
529 }
530
531 /// The arm's pattern.
532 ///
533 /// # Examples
534 ///
535 /// ```
536 /// use match_lang::{Arm, Pat};
537 ///
538 /// assert_eq!(Arm::new(Pat::int(3)).pat().to_string(), "3");
539 /// ```
540 #[must_use]
541 pub fn pat(&self) -> &Pat {
542 &self.pat
543 }
544
545 /// Whether the arm has a guard.
546 ///
547 /// # Examples
548 ///
549 /// ```
550 /// use match_lang::{Arm, Pat};
551 ///
552 /// assert!(Arm::guarded(Pat::wild()).is_guarded());
553 /// ```
554 #[must_use]
555 pub fn is_guarded(&self) -> bool {
556 self.guarded
557 }
558}
559
560#[cfg(test)]
561mod tests {
562 use alloc::string::ToString;
563
564 use super::*;
565
566 fn deep(depth: usize) -> Pat {
567 let mut pat = Pat::wild();
568 for _ in 0..depth {
569 pat = Pat::variant(1, [pat]);
570 }
571 pat
572 }
573
574 #[test]
575 fn test_display_covers_every_kind() {
576 let pat = Pat::or([
577 Pat::variant(2, [Pat::product([Pat::bool(true), Pat::range(1, 3)])]),
578 Pat::product([Pat::char('a')]),
579 Pat::product([]),
580 Pat::slice_rest([Pat::lit(4)], [Pat::char_range('a', 'c')]),
581 Pat::slice_rest([], [Pat::int(1)]),
582 Pat::slice_rest([Pat::int(1)], []),
583 Pat::slice([]),
584 Pat::or([]),
585 ]);
586 assert_eq!(
587 pat.to_string(),
588 "#2((true, 1..=3)) | ('a',) | () | [lit#4, .., 'a'..='c'] | [.., 1] | [1, ..] | [] | !"
589 );
590 assert_eq!(alloc::format!("{pat:?}").len(), pat.to_string().len() + 5);
591 }
592
593 #[test]
594 fn test_deep_pattern_clone_display_drop_do_not_recurse() {
595 let pat = deep(200_000);
596 let copy = pat.clone();
597 let text = copy.to_string();
598 assert_eq!(text.len(), 200_000 * 4 + 1);
599 drop(pat);
600 drop(copy);
601 }
602
603 #[test]
604 fn test_clone_preserves_shape() {
605 let pat = Pat::or([
606 Pat::variant(1, [Pat::int(1), Pat::wild()]),
607 Pat::slice([Pat::lit(2)]),
608 ]);
609 assert_eq!(pat.clone().to_string(), pat.to_string());
610 }
611}