arithmetic_typing/types/
tuple.rs

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

arithmetic_typing/types/
tuple.rs
