arithmetic_typing/types/
tuple.rs

1//! Tuple types.
2
3use core::{cmp, fmt, iter, ops};
4
5use crate::{
6    alloc::{format, Box, Cow, Vec},
7    arith::Num,
8    PrimitiveType, Type,
9};
10
11/// Length variable.
12///
13/// A variable represents a certain unknown length. Variables can be either *free*
14/// or *bound* to a [`Function`](crate::Function) (similar to const params in Rust, except lengths
15/// always have the `usize` type).
16/// Just as with [`TypeVar`](crate::TypeVar)s, types input to a [`TypeEnvironment`]
17/// can only have bounded length variables (this is
18/// verified in runtime), but types output by the inference process can contain both.
19///
20/// # Notation
21///
22/// - Bounded length variables are represented as `N`, `M`, `L`, etc.
23/// - Free variables are represented as `_`.
24///
25/// [`TypeEnvironment`]: crate::TypeEnvironment
26#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
27pub struct LengthVar {
28    index: usize,
29    is_free: bool,
30}
31
32impl fmt::Display for LengthVar {
33    fn fmt(&self, formatter: &mut fmt::Formatter<'_>) -> fmt::Result {
34        if self.is_free {
35            formatter.write_str("_")
36        } else {
37            formatter.write_str(Self::param_str(self.index).as_ref())
38        }
39    }
40}
41
42impl LengthVar {
43    pub(crate) fn param_str(index: usize) -> Cow<'static, str> {
44        const PARAM_NAMES: &str = "NMLKJI";
45        PARAM_NAMES.get(index..=index).map_or_else(
46            || Cow::from(format!("N{}", index - PARAM_NAMES.len())),
47            Cow::from,
48        )
49    }
50
51    /// Creates a bounded length variable that can be used to
52    /// [build functions](crate::FunctionBuilder).
53    pub const fn param(index: usize) -> Self {
54        Self {
55            index,
56            is_free: false,
57        }
58    }
59
60    /// Returns the 0-based index of this variable.
61    pub fn index(self) -> usize {
62        self.index
63    }
64
65    /// Is this variable free (not bounded in a function declaration)?
66    pub fn is_free(self) -> bool {
67        self.is_free
68    }
69}
70
71/// Unknown / variable length, e.g., of a tuple.
72#[derive(Debug, Clone, Copy, PartialEq, Eq)]
73#[non_exhaustive]
74pub enum UnknownLen {
75    /// Length that can vary at runtime, similar to lengths of slices in Rust.
76    Dynamic,
77    /// Length variable.
78    Var(LengthVar),
79}
80
81impl fmt::Display for UnknownLen {
82    fn fmt(&self, formatter: &mut fmt::Formatter<'_>) -> fmt::Result {
83        match self {
84            Self::Dynamic => formatter.write_str("*"),
85            Self::Var(var) => fmt::Display::fmt(var, formatter),
86        }
87    }
88}
89
90impl ops::Add<usize> for UnknownLen {
91    type Output = TupleLen;
92
93    fn add(self, rhs: usize) -> Self::Output {
94        TupleLen {
95            var: Some(self),
96            exact: rhs,
97        }
98    }
99}
100
101impl UnknownLen {
102    /// Creates a bounded type variable that can be used to [build functions](crate::FunctionBuilder).
103    pub const fn param(index: usize) -> Self {
104        Self::Var(LengthVar::param(index))
105    }
106
107    pub(crate) const fn free_var(index: usize) -> Self {
108        Self::Var(LengthVar {
109            index,
110            is_free: true,
111        })
112    }
113}
114
115/// Generic tuple length.
116///
117/// A tuple length consists of the two components: an unknown / variable length,
118/// such as [`UnknownLen::Var`], and a non-negative increment.
119/// These components can be obtained via [`Self::components()`].
120///
121/// # Static lengths
122///
123/// Tuple lengths can be either *static* or *dynamic*. Dynamic lengths are lengths
124/// that contain [`UnknownLen::Dynamic`].
125///
126/// Functions, [`TypeArithmetic`]s, etc. can specify constraints on lengths being static.
127/// For example, this is a part of [`Ops`];
128/// dynamically sized slices such as `[Num]` cannot be added / multiplied / etc.,
129/// even if they are of the same type. This constraint is denoted as `len! N, M, ...`
130/// in the function quantifier, e.g., `for<len! N> (['T; N]) -> 'T`.
131///
132/// If the constraint fails, an error will be raised with the [kind](crate::error::Error::kind)
133/// set to [`ErrorKind::DynamicLen`].
134///
135/// [`TypeArithmetic`]: crate::arith::TypeArithmetic
136/// [`Ops`]: crate::arith::Ops
137/// [`ErrorKind::DynamicLen`]: crate::error::ErrorKind::DynamicLen
138#[derive(Debug, Clone, Copy, PartialEq, Eq)]
139pub struct TupleLen {
140    var: Option<UnknownLen>,
141    exact: usize,
142}
143
144impl fmt::Display for TupleLen {
145    fn fmt(&self, formatter: &mut fmt::Formatter<'_>) -> fmt::Result {
146        match (&self.var, self.exact) {
147            (Some(var), 0) => fmt::Display::fmt(var, formatter),
148            (Some(var), exact) => write!(formatter, "{var} + {exact}"),
149            (None, exact) => fmt::Display::fmt(&exact, formatter),
150        }
151    }
152}
153
154impl ops::Add<usize> for TupleLen {
155    type Output = Self;
156
157    fn add(self, rhs: usize) -> Self::Output {
158        Self {
159            var: self.var,
160            exact: self.exact + rhs,
161        }
162    }
163}
164
165impl From<UnknownLen> for TupleLen {
166    fn from(var: UnknownLen) -> Self {
167        Self {
168            var: Some(var),
169            exact: 0,
170        }
171    }
172}
173
174impl From<usize> for TupleLen {
175    fn from(exact: usize) -> Self {
176        Self { var: None, exact }
177    }
178}
179
180impl TupleLen {
181    /// Zero length.
182    pub(crate) const ZERO: Self = Self {
183        var: None,
184        exact: 0,
185    };
186
187    fn is_concrete(&self) -> bool {
188        !matches!(&self.var, Some(UnknownLen::Var(var)) if var.is_free())
189    }
190
191    /// Returns components of this length.
192    pub fn components(&self) -> (Option<UnknownLen>, usize) {
193        (self.var, self.exact)
194    }
195
196    /// Returns mutable references to the components of this length.
197    pub fn components_mut(&mut self) -> (Option<&mut UnknownLen>, &mut usize) {
198        (self.var.as_mut(), &mut self.exact)
199    }
200}
201
202/// Index of an element within a tuple.
203#[derive(Debug, Clone, Copy, PartialEq, Eq)]
204#[non_exhaustive]
205pub enum TupleIndex {
206    /// 0-based index from the start of the tuple.
207    Start(usize),
208    /// Middle element.
209    Middle,
210    /// 0-based index from the end of the tuple.
211    End(usize),
212}
213
214/// Tuple type.
215///
216/// Most generally, a tuple type consists of three fragments: *start*,
217/// *middle* and *end*. Types at the start and at the end are heterogeneous,
218/// while the middle always contains items of the same type (but the number
219/// of these items can generally vary). A [`Slice`] is a partial case of a tuple type;
220/// i.e., a type with the empty start and end. Likewise, a Rust-like tuple is a tuple
221/// that only has a start.
222///
223/// # Notation
224///
225/// A tuple type is denoted like `(T, U, ...[V; _], X, Y)`, where `T` and `U` are types
226/// at the start, `V` is the middle type, and `X`, `Y` are types at the end.
227/// The number of middle elements can be parametric, such as `N`.
228/// If a tuple only has a start, this notation collapses into Rust-like `(T, U)`.
229/// If a tuple only has a middle part ([`Self::as_slice()`] returns `Some(_)`),
230/// it is denoted as the corresponding slice, something like `[T; N]`.
231///
232/// # Indexing
233///
234/// *Indexing* is accessing tuple elements via an expression like `xs.0`.
235/// Tuple indexing is supported via [`FieldAccess`](arithmetic_parser::Expr::FieldAccess) expr,
236/// where the field name is a decimal `usize` number.
237///
238/// The indexing support for type inference is quite limited.
239/// For it to work, the receiver type must be known to be a tuple, and the index must be such
240/// that the type of the corresponding element is decidable. Otherwise,
241/// an [`UnsupportedIndex`] error will be raised.
242///
243/// | Tuple type | Index | Outcome |
244/// |------------|-------|---------|
245/// | `(Num, Bool)` | 0 | `Num` |
246/// | `(Num, Bool)` | 1 | `Bool` |
247/// | `(Num, Bool)` | 2 | Hard error; the index is out of bounds. |
248/// | `Num` | 0 | Hard error; only tuples can be indexed. |
249/// | `[Num; _]` | 0 | Error; the slice may be empty. |
250/// | `[Num; _ + 1]` | 0 | `Num`; the slice is guaranteed to have 0th element. |
251/// | `(Bool, ...[Num; _])` | 0 | `Bool` |
252/// | `(Bool, ...[Num; _])` | 1 | Error; the slice part may be empty. |
253/// | `(...[Num; _], Bool)` | 0 | Error; cannot decide if the result is `Num` or `Bool`. |
254///
255/// [`UnsupportedIndex`]: crate::error::ErrorKind::UnsupportedIndex
256///
257/// # Examples
258///
259/// Simple tuples can be created using the [`From`] trait. Complex tuples can be created
260/// via [`Self::new()`].
261///
262/// ```
263/// # use arithmetic_typing::{Slice, Tuple, UnknownLen, Type};
264/// # use assert_matches::assert_matches;
265/// let simple_tuple = Tuple::from(vec![Type::NUM, Type::BOOL]);
266/// assert_matches!(simple_tuple.parts(), ([_, _], None, []));
267/// assert!(simple_tuple.as_slice().is_none());
268/// assert_eq!(simple_tuple.to_string(), "(Num, Bool)");
269///
270/// let slice_tuple = Tuple::from(
271///    Type::NUM.repeat(UnknownLen::param(0)),
272/// );
273/// assert_matches!(slice_tuple.parts(), ([], Some(_), []));
274/// assert!(slice_tuple.as_slice().is_some());
275/// assert_eq!(slice_tuple.to_string(), "[Num; N]");
276///
277/// let complex_tuple = Tuple::new(
278///     vec![Type::NUM],
279///     Type::NUM.repeat(UnknownLen::param(0)),
280///     vec![Type::BOOL, Type::param(0)],
281/// );
282/// assert_matches!(complex_tuple.parts(), ([_], Some(_), [_, _]));
283/// assert_eq!(complex_tuple.to_string(), "(Num, ...[Num; N], Bool, 'T)");
284/// ```
285#[derive(Debug, Clone)]
286pub struct Tuple<Prim: PrimitiveType = Num> {
287    start: Vec<Type<Prim>>,
288    middle: Option<Slice<Prim>>,
289    end: Vec<Type<Prim>>,
290}
291
292impl<Prim: PrimitiveType> PartialEq for Tuple<Prim> {
293    fn eq(&self, other: &Self) -> bool {
294        let this_len = self.len();
295        if this_len != other.len() {
296            false
297        } else if let (None, len) = this_len.components() {
298            self.iter(len).zip(other.iter(len)).all(|(x, y)| x == y)
299        } else {
300            self.equal_elements_dyn(other).all(|(x, y)| x == y)
301        }
302    }
303}
304
305impl<Prim: PrimitiveType> fmt::Display for Tuple<Prim> {
306    fn fmt(&self, formatter: &mut fmt::Formatter<'_>) -> fmt::Result {
307        if let Some(slice) = self.as_slice() {
308            if let (Some(_), _) = slice.length.components() {
309                return fmt::Display::fmt(slice, formatter);
310            }
311        }
312        self.format_as_tuple(formatter)
313    }
314}
315
316impl<Prim: PrimitiveType> Tuple<Prim> {
317    pub(crate) fn from_parts(
318        start: Vec<Type<Prim>>,
319        middle: Option<Slice<Prim>>,
320        end: Vec<Type<Prim>>,
321    ) -> Self {
322        Self { start, middle, end }
323    }
324
325    /// Creates a new complex tuple.
326    pub fn new(start: Vec<Type<Prim>>, middle: Slice<Prim>, end: Vec<Type<Prim>>) -> Self {
327        Self::from_parts(start, Some(middle), end)
328    }
329
330    pub(crate) fn empty() -> Self {
331        Self {
332            start: Vec::new(),
333            middle: None,
334            end: Vec::new(),
335        }
336    }
337
338    pub(crate) fn is_concrete(&self) -> bool {
339        self.start.iter().chain(&self.end).all(Type::is_concrete)
340            && self.middle.as_ref().map_or(true, Slice::is_concrete)
341    }
342
343    /// Returns this tuple as slice if it fits (has no start or end components).
344    pub fn as_slice(&self) -> Option<&Slice<Prim>> {
345        self.middle
346            .as_ref()
347            .filter(|_| self.start.is_empty() && self.end.is_empty())
348    }
349
350    pub(crate) fn format_as_tuple(&self, formatter: &mut fmt::Formatter<'_>) -> fmt::Result {
351        formatter.write_str("(")?;
352
353        for (i, element) in self.start.iter().enumerate() {
354            fmt::Display::fmt(element, formatter)?;
355            if i + 1 < self.start.len() || self.middle.is_some() {
356                formatter.write_str(", ")?;
357            }
358        }
359
360        if let Some(middle) = &self.middle {
361            if let (None, len) = middle.length.components() {
362                // Write the slice inline, not separating it into square brackets.
363                for i in 0..len {
364                    fmt::Display::fmt(&middle.element, formatter)?;
365                    if i + 1 < len {
366                        formatter.write_str(", ")?;
367                    }
368                }
369            } else {
370                formatter.write_str("...")?;
371                fmt::Display::fmt(middle, formatter)?;
372            }
373        }
374        if !self.end.is_empty() {
375            formatter.write_str(", ")?;
376        }
377
378        for (i, element) in self.end.iter().enumerate() {
379            fmt::Display::fmt(element, formatter)?;
380            if i + 1 < self.end.len() {
381                formatter.write_str(", ")?;
382            }
383        }
384
385        formatter.write_str(")")
386    }
387
388    fn resolved_middle_len(&self) -> TupleLen {
389        self.middle
390            .as_ref()
391            .map_or(TupleLen::ZERO, |middle| middle.length)
392    }
393
394    /// Returns shared references to the parts comprising this tuple: start, middle, and end.
395    #[allow(clippy::type_complexity)]
396    pub fn parts(&self) -> (&[Type<Prim>], Option<&Slice<Prim>>, &[Type<Prim>]) {
397        (&self.start, self.middle.as_ref(), &self.end)
398    }
399
400    /// Returns exclusive references to the parts comprising this tuple: start, middle, and end.
401    #[allow(clippy::type_complexity)]
402    pub fn parts_mut(
403        &mut self,
404    ) -> (
405        &mut [Type<Prim>],
406        Option<&mut Slice<Prim>>,
407        &mut [Type<Prim>],
408    ) {
409        (&mut self.start, self.middle.as_mut(), &mut self.end)
410    }
411
412    /// Returns the length of this tuple.
413    ///
414    /// # Examples
415    ///
416    /// ```
417    /// # use arithmetic_typing::{Slice, Tuple, Type, UnknownLen, TupleLen};
418    /// let tuple = Tuple::from(vec![Type::NUM, Type::BOOL]);
419    /// assert_eq!(tuple.len(), TupleLen::from(2));
420    ///
421    /// let slice = Slice::new(Type::NUM, UnknownLen::param(0));
422    /// let tuple = Tuple::from(slice.clone());
423    /// assert_eq!(tuple.len(), TupleLen::from(UnknownLen::param(0)));
424    ///
425    /// let tuple = Tuple::new(vec![], slice, vec![Type::BOOL]);
426    /// assert_eq!(tuple.len(), UnknownLen::param(0) + 1);
427    /// ```
428    pub fn len(&self) -> TupleLen {
429        let increment = self.start.len() + self.end.len();
430        self.resolved_middle_len() + increment
431    }
432
433    /// Returns `true` iff this tuple is guaranteed to be empty.
434    pub fn is_empty(&self) -> bool {
435        self.start.is_empty() && self.end.is_empty() && self.resolved_middle_len() == TupleLen::ZERO
436    }
437
438    pub(crate) fn push(&mut self, element: Type<Prim>) {
439        if self.middle.is_some() {
440            self.end.push(element);
441        } else {
442            self.start.push(element);
443        }
444    }
445
446    pub(crate) fn set_middle(&mut self, element: Type<Prim>, len: TupleLen) {
447        self.middle = Some(Slice::new(element, len));
448    }
449
450    /// Returns iterator over elements of this tuple assuming it has the given total length.
451    pub(crate) fn iter(&self, total_len: usize) -> impl Iterator<Item = &Type<Prim>> + '_ {
452        let middle_len = total_len - self.start.len() - self.end.len();
453        let middle_element = self.middle.as_ref().map(Slice::element);
454
455        self.start
456            .iter()
457            .chain(iter::repeat_with(move || middle_element.unwrap()).take(middle_len))
458            .chain(&self.end)
459    }
460
461    /// Attempts to index into this tuple. `middle_len` specifies the resolved middle length.
462    pub(crate) fn get_element(
463        &self,
464        index: usize,
465        middle_len: TupleLen,
466    ) -> Result<&Type<Prim>, IndexError> {
467        if let Some(element) = self.start.get(index) {
468            Ok(element)
469        } else {
470            self.middle
471                .as_ref()
472                .map_or(Err(IndexError::OutOfBounds), |middle| {
473                    let middle_index = index - self.start.len();
474                    if middle_index < middle_len.exact {
475                        // The element is definitely in the middle.
476                        Ok(middle.element.as_ref())
477                    } else if middle_len.var.is_none() {
478                        // The element is definitely in the end.
479                        let end_index = middle_index - middle_len.exact;
480                        self.end.get(end_index).ok_or(IndexError::OutOfBounds)
481                    } else {
482                        Err(IndexError::NoInfo)
483                    }
484                })
485        }
486    }
487
488    /// Returns pairs of elements of this and `other` tuple that should be equal to each other.
489    ///
490    /// This method is specialized for the case when the length of middles is unknown.
491    pub(crate) fn equal_elements_dyn<'a>(
492        &'a self,
493        other: &'a Self,
494    ) -> impl Iterator<Item = (&'a Type<Prim>, &'a Type<Prim>)> + 'a {
495        let middle_elem = self.middle.as_ref().unwrap().element.as_ref();
496        let other_middle_elem = other.middle.as_ref().unwrap().element.as_ref();
497        let iter = iter::once((middle_elem, other_middle_elem));
498
499        let borders_iter = self
500            .start
501            .iter()
502            .zip(&other.start)
503            .chain(self.end.iter().rev().zip(other.end.iter().rev()));
504        let iter = iter.chain(borders_iter);
505
506        let skip_at_start = cmp::min(self.start.len(), other.start.len());
507        let skip_at_end = cmp::min(self.end.len(), other.end.len());
508        let middle = self
509            .start
510            .iter()
511            .skip(skip_at_start)
512            .chain(self.end.iter().rev().skip(skip_at_end));
513        let iter = iter.chain(middle.map(move |elem| (middle_elem, elem)));
514
515        let other_middle = other
516            .start
517            .iter()
518            .skip(skip_at_start)
519            .chain(other.end.iter().rev().skip(skip_at_end));
520        iter.chain(other_middle.map(move |elem| (middle_elem, elem)))
521    }
522
523    /// Iterates over all distinct elements in this tuple. The iteration is performed in order.
524    ///
525    /// # Examples
526    ///
527    /// ```
528    /// # use arithmetic_typing::{Slice, Tuple, TupleIndex, UnknownLen, Type};
529    /// let complex_tuple = Tuple::new(
530    ///     vec![Type::NUM],
531    ///     Slice::new(Type::NUM, UnknownLen::param(0)),
532    ///     vec![Type::BOOL, Type::param(0)],
533    /// );
534    /// let elements: Vec<_> = complex_tuple.element_types().collect();
535    /// assert_eq!(elements, [
536    ///     (TupleIndex::Start(0), &Type::NUM),
537    ///     (TupleIndex::Middle, &Type::NUM),
538    ///     (TupleIndex::End(0), &Type::BOOL),
539    ///     (TupleIndex::End(1), &Type::param(0)),
540    /// ]);
541    /// ```
542    pub fn element_types(&self) -> impl Iterator<Item = (TupleIndex, &Type<Prim>)> + '_ {
543        let middle_element = self
544            .middle
545            .as_ref()
546            .map(|slice| (TupleIndex::Middle, slice.element.as_ref()));
547        let start = self
548            .start
549            .iter()
550            .enumerate()
551            .map(|(i, elem)| (TupleIndex::Start(i), elem));
552        let end = self
553            .end
554            .iter()
555            .enumerate()
556            .map(|(i, elem)| (TupleIndex::End(i), elem));
557        start.chain(middle_element).chain(end)
558    }
559
560    pub(crate) fn element_types_mut(&mut self) -> impl Iterator<Item = &mut Type<Prim>> + '_ {
561        let middle_element = self.middle.as_mut().map(|slice| slice.element.as_mut());
562        self.start
563            .iter_mut()
564            .chain(middle_element)
565            .chain(&mut self.end)
566    }
567}
568
569impl<Prim: PrimitiveType> From<Vec<Type<Prim>>> for Tuple<Prim> {
570    fn from(elements: Vec<Type<Prim>>) -> Self {
571        Self {
572            start: elements,
573            middle: None,
574            end: Vec::new(),
575        }
576    }
577}
578
579/// Errors that can occur when indexing into a tuple.
580#[derive(Debug)]
581pub(crate) enum IndexError {
582    /// Index is out of bounds.
583    OutOfBounds,
584    /// Not enough info to determine the type.
585    NoInfo,
586}
587
588/// Slice type. Unlike in Rust, slices are a subset of tuples. If `length` is
589/// exact (has no [`UnknownLen`] part), the slice is completely equivalent
590/// to the corresponding tuple.
591///
592/// # Notation
593///
594/// A slice is denoted as `[T; N]` where `T` is the slice [element](Self::element())
595/// and `N` is the slice [length](Self::len()). A special case is `[T]`, a slice
596/// with a dynamic length.
597///
598/// # Examples
599///
600/// ```
601/// use arithmetic_parser::grammars::{F32Grammar, Parse};
602/// use arithmetic_typing::{Annotated, TupleLen, TypeEnvironment, Type};
603///
604/// # fn main() -> anyhow::Result<()> {
605/// type Parser = Annotated<F32Grammar>;
606/// let ast = Parser::parse_statements("xs: [Num; _] = (1, 2, 3);")?;
607/// let mut env = TypeEnvironment::new();
608/// env.process_statements(&ast)?;
609/// // Slices with fixed length are equivalent to tuples.
610/// assert_eq!(env["xs"].to_string(), "(Num, Num, Num)");
611///
612/// let code = "
613///     xs: [Num] = (1, 2, 3);
614///     ys = xs + 1; // works fine: despite `xs` having unknown length,
615///                  // it's always possible to add a number to it
616///     (_, _, z) = xs; // does not work: the tuple length is erased
617/// ";
618/// let ast = Parser::parse_statements(code)?;
619/// let errors = env.process_statements(&ast).unwrap_err();
620///
621/// let err = errors.iter().next().unwrap();
622/// assert_eq!(err.main_location().span(code), "(_, _, z)");
623/// assert_eq!(env["ys"], env["xs"]);
624/// # Ok(())
625/// # }
626/// ```
627#[derive(Debug, Clone, PartialEq)]
628pub struct Slice<Prim: PrimitiveType = Num> {
629    element: Box<Type<Prim>>,
630    length: TupleLen,
631}
632
633impl<Prim: PrimitiveType> fmt::Display for Slice<Prim> {
634    fn fmt(&self, formatter: &mut fmt::Formatter<'_>) -> fmt::Result {
635        if self.length == TupleLen::from(UnknownLen::Dynamic) {
636            write!(formatter, "[{}]", self.element)
637        } else {
638            write!(formatter, "[{}; {}]", self.element, self.length)
639        }
640    }
641}
642
643impl<Prim: PrimitiveType> Slice<Prim> {
644    /// Creates a new slice.
645    pub fn new(element: Type<Prim>, length: impl Into<TupleLen>) -> Self {
646        Self {
647            element: Box::new(element),
648            length: length.into(),
649        }
650    }
651
652    /// Returns the element type of this slice.
653    pub fn element(&self) -> &Type<Prim> {
654        self.element.as_ref()
655    }
656
657    /// Returns the length of this slice.
658    pub fn len(&self) -> TupleLen {
659        self.length
660    }
661
662    pub(crate) fn len_mut(&mut self) -> &mut TupleLen {
663        &mut self.length
664    }
665
666    /// Returns `true` iff this slice is definitely empty.
667    pub fn is_empty(&self) -> bool {
668        self.length == TupleLen::ZERO
669    }
670
671    fn is_concrete(&self) -> bool {
672        self.length.is_concrete() && self.element.is_concrete()
673    }
674}
675
676impl<Prim: PrimitiveType> From<Slice<Prim>> for Tuple<Prim> {
677    fn from(slice: Slice<Prim>) -> Self {
678        Self {
679            start: Vec::new(),
680            middle: Some(slice),
681            end: Vec::new(),
682        }
683    }
684}
685
686#[cfg(test)]
687mod tests {
688    use assert_matches::assert_matches;
689
690    use super::*;
691    use crate::alloc::{vec, ToString};
692
693    #[test]
694    fn tuple_length_display() {
695        let len = TupleLen::from(3);
696        assert_eq!(len.to_string(), "3");
697        let len = UnknownLen::param(0) + 2;
698        assert_eq!(len.to_string(), "N + 2");
699    }
700
701    #[test]
702    fn slice_display() {
703        let slice = Slice::new(Type::NUM, UnknownLen::param(0));
704        assert_eq!(slice.to_string(), "[Num; N]");
705        let slice = Slice::new(Type::NUM, UnknownLen::free_var(0));
706        assert_eq!(slice.to_string(), "[Num; _]");
707        let slice = Slice::new(Type::NUM, TupleLen::from(3));
708        assert_eq!(slice.to_string(), "[Num; 3]");
709    }
710
711    #[test]
712    fn tuple_display() {
713        // Simple tuples.
714        let tuple = Tuple::from(vec![Type::NUM, Type::BOOL]);
715        assert_eq!(tuple.to_string(), "(Num, Bool)");
716        let tuple = Tuple::from(Slice::new(Type::NUM, UnknownLen::param(0)));
717        assert_eq!(tuple.to_string(), "[Num; N]");
718        let tuple = Tuple::from(Slice::new(Type::NUM, TupleLen::from(3)));
719        assert_eq!(tuple.to_string(), "(Num, Num, Num)");
720
721        let tuple = Tuple {
722            start: vec![Type::NUM, Type::BOOL],
723            middle: Some(Slice::new(Type::NUM, UnknownLen::param(0))),
724            end: vec![],
725        };
726        assert_eq!(tuple.to_string(), "(Num, Bool, ...[Num; N])");
727
728        let tuple = Tuple {
729            start: vec![Type::NUM, Type::BOOL],
730            middle: Some(Slice::new(Type::NUM, TupleLen::from(2))),
731            end: vec![],
732        };
733        assert_eq!(tuple.to_string(), "(Num, Bool, Num, Num)");
734
735        let tuple = Tuple {
736            start: vec![Type::NUM, Type::BOOL],
737            middle: Some(Slice::new(Type::NUM, UnknownLen::param(0))),
738            end: vec![Type::param(0)],
739        };
740        assert_eq!(tuple.to_string(), "(Num, Bool, ...[Num; N], 'T)");
741    }
742
743    #[test]
744    fn equal_elements_static_two_simple_tuples() {
745        let tuple = Tuple::from(vec![Type::NUM, Type::BOOL, Type::free_var(0)]);
746        let other_tuple = <Tuple>::from(vec![Type::free_var(1), Type::BOOL, Type::free_var(0)]);
747        let equal_elements: Vec<_> = tuple.iter(3).zip(other_tuple.iter(3)).collect();
748
749        assert_eq!(
750            equal_elements,
751            vec![
752                (&Type::NUM, &Type::free_var(1)),
753                (&Type::BOOL, &Type::BOOL),
754                (&Type::free_var(0), &Type::free_var(0)),
755            ]
756        );
757    }
758
759    #[test]
760    fn equal_elements_static_simple_tuple_and_slice() {
761        let tuple = Tuple::from(vec![Type::NUM, Type::BOOL, Type::free_var(0)]);
762        let slice = <Tuple>::from(Slice::new(Type::free_var(1), UnknownLen::free_var(0)));
763        let equal_elements: Vec<_> = tuple.iter(3).zip(slice.iter(3)).collect();
764
765        assert_eq!(
766            equal_elements,
767            vec![
768                (&Type::NUM, &Type::free_var(1)),
769                (&Type::BOOL, &Type::free_var(1)),
770                (&Type::free_var(0), &Type::free_var(1)),
771            ]
772        );
773    }
774
775    #[test]
776    fn equal_elements_static_slice_and_complex_tuple() {
777        let slice = <Tuple>::from(Slice::new(Type::free_var(1), UnknownLen::free_var(0)));
778        let tuple = Tuple {
779            start: vec![Type::NUM],
780            middle: Some(Slice::new(Type::free_var(0), UnknownLen::free_var(1))),
781            end: vec![Type::BOOL, Type::free_var(2)],
782        };
783
784        let mut expected_pairs = vec![
785            (Type::free_var(1), Type::NUM),
786            (Type::free_var(1), Type::BOOL),
787            (Type::free_var(1), Type::free_var(2)),
788        ];
789        let equal_elements: Vec<_> = slice
790            .iter(3)
791            .zip(tuple.iter(3))
792            .map(|(x, y)| (x.clone(), y.clone()))
793            .collect();
794        assert_eq!(equal_elements, expected_pairs);
795
796        let equal_elements: Vec<_> = slice
797            .iter(4)
798            .zip(tuple.iter(4))
799            .map(|(x, y)| (x.clone(), y.clone()))
800            .collect();
801        expected_pairs.insert(1, (Type::free_var(1), Type::free_var(0)));
802        assert_eq!(equal_elements, expected_pairs);
803
804        let equal_elements: Vec<_> = slice
805            .iter(5)
806            .zip(tuple.iter(5))
807            .map(|(x, y)| (x.clone(), y.clone()))
808            .collect();
809        expected_pairs.insert(2, (Type::free_var(1), Type::free_var(0)));
810        assert_eq!(equal_elements, expected_pairs);
811    }
812
813    fn create_test_tuples() -> (Tuple, Tuple) {
814        let tuple = Tuple {
815            start: vec![Type::NUM],
816            middle: Some(Slice::new(Type::free_var(0), UnknownLen::free_var(1))),
817            end: vec![Type::BOOL, Type::free_var(2)],
818        };
819        let other_tuple = Tuple {
820            start: vec![Type::NUM, Type::free_var(3)],
821            middle: Some(Slice::new(Type::BOOL, UnknownLen::free_var(1))),
822            end: vec![Type::free_var(1)],
823        };
824        (tuple, other_tuple)
825    }
826
827    #[test]
828    fn equal_elements_static_two_complex_tuples() {
829        let (tuple, other_tuple) = create_test_tuples();
830
831        let equal_elements: Vec<_> = tuple.iter(3).zip(other_tuple.iter(3)).collect();
832        assert_eq!(
833            equal_elements,
834            vec![
835                (&Type::NUM, &Type::NUM),
836                (&Type::BOOL, &Type::free_var(3)),
837                (&Type::free_var(2), &Type::free_var(1)),
838            ]
839        );
840
841        let equal_elements: Vec<_> = tuple.iter(4).zip(other_tuple.iter(4)).collect();
842        assert_eq!(
843            equal_elements,
844            vec![
845                (&Type::NUM, &Type::NUM),
846                (&Type::free_var(0), &Type::free_var(3)),
847                (&Type::BOOL, &Type::BOOL),
848                (&Type::free_var(2), &Type::free_var(1)),
849            ]
850        );
851    }
852
853    #[test]
854    fn equal_elements_dyn_two_slices() {
855        let slice = Tuple::from(Slice::new(Type::free_var(0), UnknownLen::free_var(0)));
856        let other_slice = Tuple::from(Slice::new(Type::NUM, UnknownLen::free_var(1)));
857        let equal_elements: Vec<_> = slice.equal_elements_dyn(&other_slice).collect();
858
859        assert_eq!(equal_elements, vec![(&Type::free_var(0), &Type::NUM)]);
860    }
861
862    #[test]
863    fn equal_elements_dyn_two_complex_tuples() {
864        let (tuple, other_tuple) = create_test_tuples();
865        let equal_elements: Vec<_> = tuple.equal_elements_dyn(&other_tuple).collect();
866
867        assert_eq!(
868            equal_elements,
869            vec![
870                // Middle elements
871                (&Type::free_var(0), &Type::BOOL),
872                // Borders
873                (&Type::NUM, &Type::NUM),
874                (&Type::free_var(2), &Type::free_var(1)),
875                // Non-borders in first tuple.
876                (&Type::free_var(0), &Type::BOOL),
877                // Non-borders in second tuple.
878                (&Type::free_var(0), &Type::free_var(3)),
879            ]
880        );
881    }
882
883    #[test]
884    fn tuple_indexing() {
885        // Ordinary tuple.
886        let tuple = Tuple::from(vec![Type::NUM, Type::BOOL]);
887        assert_eq!(*tuple.get_element(0, TupleLen::ZERO).unwrap(), Type::NUM,);
888        assert_eq!(*tuple.get_element(1, TupleLen::ZERO).unwrap(), Type::BOOL,);
889        assert_matches!(
890            tuple.get_element(2, TupleLen::ZERO).unwrap_err(),
891            IndexError::OutOfBounds
892        );
893
894        // Slice.
895        let tuple = Tuple::from(Slice::new(Type::NUM, UnknownLen::param(0)));
896        assert_eq!(*tuple.get_element(0, TupleLen::from(3)).unwrap(), Type::NUM);
897        assert_matches!(
898            tuple.get_element(3, TupleLen::from(3)).unwrap_err(),
899            IndexError::OutOfBounds
900        );
901        assert_matches!(
902            tuple
903                .get_element(0, UnknownLen::free_var(0).into())
904                .unwrap_err(),
905            IndexError::NoInfo
906        );
907        assert_eq!(
908            *tuple.get_element(0, UnknownLen::free_var(0) + 1).unwrap(),
909            Type::NUM
910        );
911
912        // Tuple with all three components.
913        let (tuple, _) = create_test_tuples();
914        assert_eq!(
915            *tuple
916                .get_element(0, UnknownLen::free_var(0).into())
917                .unwrap(),
918            Type::NUM
919        );
920        assert_matches!(
921            tuple
922                .get_element(1, UnknownLen::free_var(0).into())
923                .unwrap_err(),
924            IndexError::NoInfo
925        );
926
927        assert_eq!(*tuple.get_element(1, 2.into()).unwrap(), Type::free_var(0));
928        assert_eq!(*tuple.get_element(3, 2.into()).unwrap(), Type::BOOL);
929        assert_matches!(
930            tuple.get_element(5, 2.into()).unwrap_err(),
931            IndexError::OutOfBounds
932        );
933    }
934}
arithmetic_typing/types/tuple.rs

arithmetic_typing/types/
tuple.rs
