match_lang/model.rs
1//! The constructor model: how a language tells the checker what its types'
2//! values look like.
3
4use alloc::vec::Vec;
5
6/// A language's constructor model.
7///
8/// The checker never sees the language's types directly. It asks the model
9/// two questions about a type: what its [`Signature`] is (which constructors
10/// build its values), and what the field types of a constructor are. That is
11/// enough to decide exhaustiveness and usefulness for every type the
12/// signatures can describe: sums, products, booleans, bounded and unbounded
13/// integers, characters, opaque literals, arrays, and slices.
14///
15/// The model must answer consistently: the same type must get the same
16/// signature and fields every time during one check. A model that changes
17/// its answers mid-check is reported as [`Error::Model`](crate::Error::Model),
18/// never a panic.
19///
20/// `Ty` is whatever names a type in the language: an interned id is ideal,
21/// since the checker clones types as it descends into fields.
22///
23/// # Examples
24///
25/// A model for `bool` and `Option<T>`:
26///
27/// ```
28/// use match_lang::{Model, Signature};
29///
30/// #[derive(Clone)]
31/// enum Ty {
32/// Bool,
33/// Option(Box<Ty>),
34/// }
35///
36/// struct Lang;
37///
38/// impl Model for Lang {
39/// type Ty = Ty;
40///
41/// fn signature(&self, ty: &Ty) -> Signature<Ty> {
42/// match ty {
43/// Ty::Bool => Signature::Bool,
44/// Ty::Option(_) => Signature::Sum { count: 2 },
45/// }
46/// }
47///
48/// fn fields(&self, ty: &Ty, variant: u32, out: &mut Vec<Ty>) {
49/// // `None` (variant 0) has no fields; `Some` (variant 1) has one.
50/// if let (Ty::Option(inner), 1) = (ty, variant) {
51/// out.push((**inner).clone());
52/// }
53/// }
54///
55/// fn variant_name(&self, ty: &Ty, variant: u32) -> Option<&str> {
56/// match (ty, variant) {
57/// (Ty::Option(_), 0) => Some("None"),
58/// (Ty::Option(_), 1) => Some("Some"),
59/// _ => None,
60/// }
61/// }
62/// }
63///
64/// let mut fields = Vec::new();
65/// Lang.fields(&Ty::Option(Box::new(Ty::Bool)), 1, &mut fields);
66/// assert!(matches!(fields[..], [Ty::Bool]));
67/// ```
68pub trait Model {
69 /// A type of the language.
70 type Ty: Clone;
71
72 /// The constructors that build values of `ty`.
73 ///
74 /// # Examples
75 ///
76 /// ```
77 /// use match_lang::{Model, Signature};
78 ///
79 /// struct Bytes;
80 ///
81 /// impl Model for Bytes {
82 /// type Ty = ();
83 /// fn signature(&self, _: &()) -> Signature<()> {
84 /// Signature::Int { min: 0, max: 255 }
85 /// }
86 /// fn fields(&self, _: &(), _: u32, _: &mut Vec<()>) {}
87 /// }
88 ///
89 /// assert_eq!(Bytes.signature(&()), Signature::Int { min: 0, max: 255 });
90 /// ```
91 fn signature(&self, ty: &Self::Ty) -> Signature<Self::Ty>;
92
93 /// Pushes onto `out` the field types of a constructor of `ty`, in field
94 /// order: variant `variant` of a [`Sum`](Signature::Sum), or the single
95 /// constructor of a [`Product`](Signature::Product) (`variant` is then
96 /// 0). `out` is empty when called. It is not called for other
97 /// signatures: booleans, integers, characters, and opaque literals have
98 /// no fields, and arrays and slices name their element type in the
99 /// signature.
100 ///
101 /// # Examples
102 ///
103 /// ```
104 /// use match_lang::{Model, Signature};
105 ///
106 /// // A model of `(bool, bool)`: the unit type `()` stands for `bool`
107 /// // inside, and `None` for the pair.
108 /// struct Pair;
109 ///
110 /// impl Model for Pair {
111 /// type Ty = Option<()>;
112 /// fn signature(&self, ty: &Option<()>) -> Signature<Option<()>> {
113 /// match ty {
114 /// None => Signature::Product,
115 /// Some(()) => Signature::Bool,
116 /// }
117 /// }
118 /// fn fields(&self, _: &Option<()>, _: u32, out: &mut Vec<Option<()>>) {
119 /// out.extend([Some(()), Some(())]);
120 /// }
121 /// }
122 ///
123 /// let mut out = Vec::new();
124 /// Pair.fields(&None, 0, &mut out);
125 /// assert_eq!(out.len(), 2);
126 /// ```
127 fn fields(&self, ty: &Self::Ty, variant: u32, out: &mut Vec<Self::Ty>);
128
129 /// Whether `ty` has no values at all, like `!` or an enum with no
130 /// variants.
131 ///
132 /// The checker treats a constructor as impossible when one of its fields
133 /// is empty, so `Err(_)` is not required, and is reported unreachable,
134 /// for a `Result<T, !>`. For that to be exact the answer should be deep:
135 /// a tuple or struct with an empty field is itself empty. The default
136 /// recognizes only `Sum { count: 0 }`.
137 ///
138 /// # Examples
139 ///
140 /// ```
141 /// use match_lang::{Model, Signature};
142 ///
143 /// struct Never;
144 ///
145 /// impl Model for Never {
146 /// type Ty = ();
147 /// fn signature(&self, _: &()) -> Signature<()> {
148 /// Signature::Sum { count: 0 }
149 /// }
150 /// fn fields(&self, _: &(), _: u32, _: &mut Vec<()>) {}
151 /// }
152 ///
153 /// assert!(Never.is_empty(&()));
154 /// ```
155 fn is_empty(&self, ty: &Self::Ty) -> bool {
156 matches!(self.signature(ty), Signature::Sum { count: 0 })
157 }
158
159 /// A name for variant `variant` of `ty` (or, with `variant` 0, for a
160 /// product type), used only when printing witnesses with
161 /// [`Witness::display`](crate::Witness::display). Without a name a
162 /// variant prints as `#index` and a product as a tuple.
163 ///
164 /// # Examples
165 ///
166 /// ```
167 /// use match_lang::{Model, Signature};
168 ///
169 /// struct Unit;
170 ///
171 /// impl Model for Unit {
172 /// type Ty = ();
173 /// fn signature(&self, _: &()) -> Signature<()> {
174 /// Signature::Product
175 /// }
176 /// fn fields(&self, _: &(), _: u32, _: &mut Vec<()>) {}
177 /// }
178 ///
179 /// assert_eq!(Unit.variant_name(&(), 0), None);
180 /// ```
181 fn variant_name(&self, ty: &Self::Ty, variant: u32) -> Option<&str> {
182 let _unnamed = (ty, variant);
183 None
184 }
185}
186
187/// The constructors that build the values of one type.
188///
189/// Each signature fixes which [`Pat`](crate::Pat) constructors fit the type
190/// and how they partition its values. Finite signatures can be covered
191/// constructor by constructor; infinite ones need a wildcard (or, for
192/// integers and characters, ranges that cover every value).
193///
194/// Types the signatures do not name directly map onto them:
195///
196/// - `()`, tuples, structs, records, `Box<T>` and `&T`: [`Product`](Self::Product).
197/// - enums and other tagged unions, including the never type
198/// (`Sum { count: 0 }`): [`Sum`](Self::Sum).
199/// - fixed-width integers: [`Int`](Self::Int) with the type's bounds. A
200/// `u128` maps into `i128` by flipping the top bit (`(v ^ (1 << 127)) as
201/// i128`), which preserves order.
202/// - floats: [`Opaque`](Self::Opaque) when compared by equality, or
203/// [`Int`](Self::Int) over a total-order key of the bits when ranges are
204/// allowed.
205/// - strings and other interned values: [`Opaque`](Self::Opaque).
206///
207/// # Examples
208///
209/// ```
210/// use match_lang::Signature;
211///
212/// let u8_sig: Signature<()> = Signature::Int { min: 0, max: 255 };
213/// let option_sig: Signature<()> = Signature::Sum { count: 2 };
214/// assert_ne!(u8_sig, option_sig);
215/// ```
216#[derive(Clone, Debug, PartialEq, Eq, Hash)]
217#[non_exhaustive]
218pub enum Signature<T> {
219 /// A tagged union with variants `0..count`, matched by
220 /// [`Pat::variant`](crate::Pat::variant). Each variant's fields come from
221 /// [`Model::fields`]. `count` 0 is an empty type: no value, so a match
222 /// on it needs no arms.
223 Sum {
224 /// The number of variants.
225 count: u32,
226 },
227 /// A type with exactly one constructor (a tuple, struct, record, box, or
228 /// reference), matched by [`Pat::product`](crate::Pat::product). Its
229 /// fields come from [`Model::fields`] with variant 0.
230 Product,
231 /// `false` and `true`, matched by [`Pat::bool`](crate::Pat::bool).
232 Bool,
233 /// The integers `min..=max`, matched by [`Pat::int`](crate::Pat::int)
234 /// and [`Pat::range`](crate::Pat::range). Covering every value from
235 /// `min` to `max` makes a match exhaustive.
236 Int {
237 /// The smallest value of the type.
238 min: i128,
239 /// The largest value of the type.
240 max: i128,
241 },
242 /// The Unicode scalar values (`'\0'..='\u{10FFFF}'` without the
243 /// surrogates), matched by [`Pat::char`](crate::Pat::char) and
244 /// [`Pat::char_range`](crate::Pat::char_range).
245 Char,
246 /// Integers without bounds (arbitrary precision). Patterns are `i128`
247 /// literals and ranges; values outside `i128` can only be matched by a
248 /// wildcard, so a match is never exhaustive without one.
249 BigInt,
250 /// Infinitely many values told apart only by equality: strings, floats
251 /// compared by value, symbols. Matched by [`Pat::lit`](crate::Pat::lit);
252 /// a match always needs a wildcard.
253 Opaque,
254 /// Arrays of exactly `len` elements of type `elem`, matched by
255 /// [`Pat::slice`](crate::Pat::slice) (with exactly `len` elements) and
256 /// [`Pat::slice_rest`](crate::Pat::slice_rest).
257 Array {
258 /// The array length.
259 len: u32,
260 /// The element type.
261 elem: T,
262 },
263 /// Sequences of any length of elements of type `elem`, matched by
264 /// [`Pat::slice`](crate::Pat::slice) and
265 /// [`Pat::slice_rest`](crate::Pat::slice_rest).
266 Slice {
267 /// The element type.
268 elem: T,
269 },
270}