arithmetic_typing/types/
mod.rs

1//! Base types, such as `Type` and `DynConstraints`.
2
3use std::{borrow::Cow, fmt};
4
5use crate::{
6    arith::{CompleteConstraints, ConstraintSet, Num, ObjectSafeConstraint, WithBoolean},
7    PrimitiveType,
8};
9
10mod fn_type;
11mod object;
12mod quantifier;
13mod tuple;
14
15pub(crate) use self::{
16    fn_type::{FnParams, ParamConstraints},
17    quantifier::ParamQuantifier,
18    tuple::IndexError,
19};
20pub use self::{
21    fn_type::{FnWithConstraints, Function, FunctionBuilder},
22    object::Object,
23    tuple::{LengthVar, Slice, Tuple, TupleIndex, TupleLen, UnknownLen},
24};
25
26/// Type variable.
27///
28/// A variable represents a certain unknown type. Variables can be either *free*
29/// or *bound* to a [`Function`] (these are known as type params in Rust).
30/// Types input to a [`TypeEnvironment`] can only have bounded variables (this is
31/// verified in runtime), but types output by the inference process can contain both.
32///
33/// # Notation
34///
35/// - Bounded type variables are represented as `'T`, `'U`, `'V`, etc.
36///   The tick is inspired by lifetimes in Rust and implicit type params in [F*]. It allows
37///   to easily distinguish between vars and primitive types.
38/// - Free variables are represented as `_`.
39///
40/// [`TypeEnvironment`]: crate::TypeEnvironment
41/// [F*]: http://www.fstar-lang.org/tutorial/
42#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
43pub struct TypeVar {
44    index: usize,
45    is_free: bool,
46}
47
48impl fmt::Display for TypeVar {
49    fn fmt(&self, formatter: &mut fmt::Formatter<'_>) -> fmt::Result {
50        if self.is_free {
51            formatter.write_str("_")
52        } else {
53            write!(formatter, "'{}", Self::param_str(self.index))
54        }
55    }
56}
57
58impl TypeVar {
59    fn param_str(index: usize) -> Cow<'static, str> {
60        const PARAM_NAMES: &str = "TUVXYZ";
61        PARAM_NAMES.get(index..=index).map_or_else(
62            || Cow::from(format!("T{}", index - PARAM_NAMES.len())),
63            Cow::from,
64        )
65    }
66
67    /// Creates a bounded type variable that can be used to [build functions](FunctionBuilder).
68    pub const fn param(index: usize) -> Self {
69        Self {
70            index,
71            is_free: false,
72        }
73    }
74
75    /// Returns the 0-based index of this variable.
76    pub fn index(self) -> usize {
77        self.index
78    }
79
80    /// Is this variable free (not bounded in a function declaration)?
81    pub fn is_free(self) -> bool {
82        self.is_free
83    }
84}
85
86/// Enumeration encompassing all types supported by the type system.
87///
88/// Parametric by the [`PrimitiveType`].
89///
90/// # Notation
91///
92/// - [`Self::Any`] is represented as `any`.
93/// - [`Self::Dyn`] types are represented as documented in [`DynConstraints`].
94/// - [`Prim`](Self::Prim)itive types are represented using the [`Display`](fmt::Display)
95///   implementation of the corresponding [`PrimitiveType`].
96/// - [`Var`](Self::Var)s are represented as documented in [`TypeVar`].
97/// - Notation for [functional](Function) and [tuple](Tuple) types is documented separately.
98///
99/// [`ConstraintSet`]: crate::arith::ConstraintSet
100///
101/// # Examples
102///
103/// There are conversions to construct `Type`s eloquently:
104///
105/// ```
106/// # use arithmetic_typing::{Function, UnknownLen, Type};
107/// let tuple: Type = (Type::BOOL, Type::NUM).into();
108/// assert_eq!(tuple.to_string(), "(Bool, Num)");
109/// let slice = tuple.repeat(UnknownLen::param(0));
110/// assert_eq!(slice.to_string(), "[(Bool, Num); N]");
111/// let fn_type: Type = Function::builder()
112///     .with_arg(slice)
113///     .returning(Type::NUM)
114///     .into();
115/// assert_eq!(fn_type.to_string(), "([(Bool, Num); N]) -> Num");
116/// ```
117///
118/// A `Type` can also be parsed from a string:
119///
120/// ```
121/// # use arithmetic_typing::{ast::TypeAst, Type};
122/// # use std::convert::TryFrom;
123/// # use assert_matches::assert_matches;
124/// # fn main() -> anyhow::Result<()> {
125/// let slice = <Type>::try_from(&TypeAst::try_from("[(Bool, Num)]")?)?;
126/// assert_matches!(slice, Type::Tuple(t) if t.as_slice().is_some());
127/// let fn_type = <Type>::try_from(&TypeAst::try_from("([(Bool, Num); N]) -> Num")?)?;
128/// assert_matches!(fn_type, Type::Function(_));
129/// # Ok(())
130/// # }
131/// ```
132///
133/// # `Any` type
134///
135/// [`Self::Any`], denoted as `any`, is a catch-all type similar to `any` in TypeScript.
136/// It allows to circumvent type system limitations at the cost of being exteremely imprecise.
137/// `any` type can be used in any context (destructured, called with args of any quantity
138/// and type and so on), with each application of the type evaluated independently.
139/// Thus, the same `any` variable can be treated as a function, a tuple, a primitive type, etc.
140///
141/// ```
142/// # use arithmetic_parser::grammars::{F32Grammar, Parse};
143/// # use arithmetic_typing::{Annotated, TypeEnvironment, Type};
144/// # use assert_matches::assert_matches;
145///
146/// # fn main() -> anyhow::Result<()> {
147/// let code = r#"
148///     wildcard: any = 1; // `any` can be assigned from anything
149///     wildcard == 1 && wildcard == (2, 3);
150///     (x, y, ...) = wildcard; // destructuring `any` always succeeds
151///     wildcard(1, |x| x + 1); // calling `any` as a funcion works as well
152/// "#;
153/// let ast = Annotated::<F32Grammar>::parse_statements(code)?;
154/// let mut env = TypeEnvironment::new();
155/// env.process_statements(&ast)?;
156///
157/// // Destructure outputs are certain types that can be inferred
158/// // from their usage, rather than `any`!
159/// assert_matches!(env["x"], Type::Var(_));
160/// let bogus_code = "x + 1 == 2; x(1)";
161/// let ast = Annotated::<F32Grammar>::parse_statements(bogus_code)?;
162/// let errors = env.process_statements(&ast).unwrap_err();
163/// # assert_eq!(errors.len(), 1);
164/// let err = errors.iter().next().unwrap();
165/// assert_eq!(*err.main_span().fragment(), "x(1)");
166/// # Ok(())
167/// # }
168/// ```
169#[derive(Debug, Clone)]
170#[non_exhaustive]
171pub enum Type<Prim: PrimitiveType = Num> {
172    /// Any type aka "I'll think about typing later". Similar to `any` type in TypeScript.
173    /// See [the dedicated section](#any-type) for more details.
174    Any,
175    /// Arbitrary type implementing certain constraints. Similar to `dyn _` types in Rust or use of
176    /// interfaces in type position in TypeScript.
177    ///
178    /// See [`DynConstraints`] for details.
179    Dyn(DynConstraints<Prim>),
180    /// Primitive type.
181    Prim(Prim),
182    /// Functional type.
183    Function(Box<Function<Prim>>),
184    /// Tuple type.
185    Tuple(Tuple<Prim>),
186    /// Object type.
187    Object(Object<Prim>),
188    /// Type variable.
189    Var(TypeVar),
190}
191
192impl<Prim: PrimitiveType> PartialEq for Type<Prim> {
193    fn eq(&self, other: &Self) -> bool {
194        match (self, other) {
195            (Self::Any, _) | (_, Self::Any) => true,
196            (Self::Dyn(x), Self::Dyn(y)) => x == y,
197            (Self::Prim(x), Self::Prim(y)) => x == y,
198            (Self::Var(x), Self::Var(y)) => x == y,
199            (Self::Tuple(xs), Self::Tuple(ys)) => xs == ys,
200            (Self::Object(x), Self::Object(y)) => x == y,
201            (Self::Function(x), Self::Function(y)) => x == y,
202            _ => false,
203        }
204    }
205}
206
207impl<Prim: PrimitiveType> fmt::Display for Type<Prim> {
208    fn fmt(&self, formatter: &mut fmt::Formatter<'_>) -> fmt::Result {
209        match self {
210            Self::Any => formatter.write_str("any"),
211            Self::Dyn(constraints) => {
212                if constraints.inner.is_empty() {
213                    formatter.write_str("dyn")
214                } else {
215                    write!(formatter, "dyn {}", constraints)
216                }
217            }
218            Self::Var(var) => fmt::Display::fmt(var, formatter),
219            Self::Prim(num) => fmt::Display::fmt(num, formatter),
220            Self::Function(fn_type) => fmt::Display::fmt(fn_type, formatter),
221            Self::Tuple(tuple) => fmt::Display::fmt(tuple, formatter),
222            Self::Object(obj) => fmt::Display::fmt(obj, formatter),
223        }
224    }
225}
226
227impl<Prim: PrimitiveType> From<Function<Prim>> for Type<Prim> {
228    fn from(fn_type: Function<Prim>) -> Self {
229        Self::Function(Box::new(fn_type))
230    }
231}
232
233impl<Prim: PrimitiveType> From<Tuple<Prim>> for Type<Prim> {
234    fn from(tuple: Tuple<Prim>) -> Self {
235        Self::Tuple(tuple)
236    }
237}
238
239impl<Prim: PrimitiveType> From<Slice<Prim>> for Type<Prim> {
240    fn from(slice: Slice<Prim>) -> Self {
241        Self::Tuple(slice.into())
242    }
243}
244
245impl<Prim: PrimitiveType> From<Object<Prim>> for Type<Prim> {
246    fn from(object: Object<Prim>) -> Self {
247        Self::Object(object)
248    }
249}
250
251impl<Prim: PrimitiveType> From<DynConstraints<Prim>> for Type<Prim> {
252    fn from(constraints: DynConstraints<Prim>) -> Self {
253        Self::Dyn(constraints)
254    }
255}
256
257macro_rules! impl_from_tuple_for_type {
258    ($($var:tt : $ty:ident),*) => {
259        impl<Prim, $($ty : Into<Type<Prim>>,)*> From<($($ty,)*)> for Type<Prim>
260        where
261            Prim: PrimitiveType,
262        {
263            #[allow(unused_variables)] // `tuple` is unused for empty tuple
264            fn from(tuple: ($($ty,)*)) -> Self {
265                Self::Tuple(Tuple::from(vec![$(tuple.$var.into(),)*]))
266            }
267        }
268    };
269}
270
271impl_from_tuple_for_type!();
272impl_from_tuple_for_type!(0: T);
273impl_from_tuple_for_type!(0: T, 1: U);
274impl_from_tuple_for_type!(0: T, 1: U, 2: V);
275impl_from_tuple_for_type!(0: T, 1: U, 2: V, 3: W);
276impl_from_tuple_for_type!(0: T, 1: U, 2: V, 3: W, 4: X);
277impl_from_tuple_for_type!(0: T, 1: U, 2: V, 3: W, 4: X, 5: Y);
278impl_from_tuple_for_type!(0: T, 1: U, 2: V, 3: W, 4: X, 5: Y, 6: Z);
279impl_from_tuple_for_type!(0: T, 1: U, 2: V, 3: W, 4: X, 5: Y, 6: Z, 7: A);
280impl_from_tuple_for_type!(0: T, 1: U, 2: V, 3: W, 4: X, 5: Y, 6: Z, 7: A, 8: B);
281impl_from_tuple_for_type!(0: T, 1: U, 2: V, 3: W, 4: X, 5: Y, 6: Z, 7: A, 8: B, 9: C);
282
283impl Type {
284    /// Numeric primitive type.
285    pub const NUM: Self = Type::Prim(Num::Num);
286}
287
288impl<Prim: WithBoolean> Type<Prim> {
289    /// Boolean primitive type.
290    pub const BOOL: Self = Type::Prim(Prim::BOOL);
291}
292
293impl<Prim: PrimitiveType> Type<Prim> {
294    /// Returns a void type (an empty tuple).
295    pub fn void() -> Self {
296        Self::Tuple(Tuple::empty())
297    }
298
299    /// Creates a bounded type variable with the specified `index`.
300    pub fn param(index: usize) -> Self {
301        Self::Var(TypeVar::param(index))
302    }
303
304    pub(crate) fn free_var(index: usize) -> Self {
305        Self::Var(TypeVar {
306            index,
307            is_free: true,
308        })
309    }
310
311    /// Creates a slice type.
312    pub fn slice(element: impl Into<Type<Prim>>, length: impl Into<TupleLen>) -> Self {
313        Self::Tuple(Slice::new(element.into(), length).into())
314    }
315
316    /// Creates a slice type by repeating this type.
317    pub fn repeat(self, length: impl Into<TupleLen>) -> Slice<Prim> {
318        Slice::new(self, length)
319    }
320
321    /// Checks if this type is void (i.e., an empty tuple).
322    pub fn is_void(&self) -> bool {
323        matches!(self, Self::Tuple(tuple) if tuple.is_empty())
324    }
325
326    /// Returns `Some(true)` if this type is known to be primitive,
327    /// `Some(false)` if it's known not to be primitive, and `None` if either case is possible.
328    pub(crate) fn is_primitive(&self) -> Option<bool> {
329        match self {
330            Self::Prim(_) => Some(true),
331            Self::Tuple(_) | Self::Object(_) | Self::Function(_) => Some(false),
332            _ => None,
333        }
334    }
335
336    /// Returns `true` iff this type does not contain type / length variables.
337    ///
338    /// See [`TypeEnvironment`](crate::TypeEnvironment) for caveats of dealing with
339    /// non-concrete types.
340    pub fn is_concrete(&self) -> bool {
341        match self {
342            Self::Var(var) => !var.is_free,
343            Self::Any | Self::Prim(_) => true,
344            Self::Dyn(constraints) => constraints.is_concrete(),
345            Self::Function(fn_type) => fn_type.is_concrete(),
346            Self::Tuple(tuple) => tuple.is_concrete(),
347            Self::Object(obj) => obj.is_concrete(),
348        }
349    }
350}
351
352/// Arbitrary type implementing certain constraints. Similar to `dyn _` types in Rust or use of
353/// interfaces in type position in TypeScript.
354///
355/// [`Constraint`]s in this type must be [object-safe](crate::arith::ObjectSafeConstraint).
356/// `DynConstraints` can also specify an [`Object`] constraint, which can be converted to it
357/// using the [`From`] trait.
358///
359/// [`Constraint`]: crate::arith::Constraint
360///
361/// # Notation
362///
363/// - If the constraints do not include an object constraint, they are [`Display`](fmt::Display)ed
364///   like a [`ConstraintSet`] with `dyn` prefix; e.g, `dyn Lin + Hash`.
365/// - If the constraints include an object constraint, it is specified before all other constraints,
366///   but after the `dyn` prefix; e.g., `dyn { x: Num } + Lin`.
367///
368/// # Examples
369///
370/// `dyn _` types can be used to express that any types satisfying certain constraints
371/// should be accepted.
372///
373/// ```
374/// # use arithmetic_parser::grammars::{F32Grammar, Parse};
375/// # use arithmetic_typing::{defs::Prelude, Annotated, TypeEnvironment, Type, Function};
376/// #
377/// # fn main() -> anyhow::Result<()> {
378/// let code = r#"
379///     sum_lengths = |...pts: dyn { x: _, y: _ }| {
380///         pts.fold(0, |acc, { x, y }| acc + sqrt(x * x + y * y))
381///     };
382///     sum_lengths(#{ x: 1, y: 2 }, #{ x: 3, y: 4, z: 5 })
383/// "#;
384/// let ast = Annotated::<F32Grammar>::parse_statements(code)?;
385///
386/// let mut env = TypeEnvironment::new();
387/// let sqrt = Function::builder().with_arg(Type::NUM).returning(Type::NUM);
388/// env.insert("fold", Prelude::Fold).insert("sqrt", sqrt);
389/// env.process_statements(&ast)?;
390///
391/// assert_eq!(
392///     env["sum_lengths"].to_string(),
393///     "(...[dyn { x: Num, y: Num }; N]) -> Num"
394/// );
395/// # Ok(())
396/// # }
397/// ```
398///
399/// One of primary use cases of `dyn _` is restricting varargs of a function:
400///
401/// ```
402/// # use arithmetic_parser::grammars::{F32Grammar, Parse};
403/// # use arithmetic_typing::{
404/// #     ast::TypeAst, defs::Prelude, error::ErrorKind, Annotated, TypeEnvironment, Type,
405/// # };
406/// # use std::convert::TryFrom;
407/// # use assert_matches::assert_matches;
408/// #
409/// # fn main() -> anyhow::Result<()> {
410/// // Function that accepts any amount of linear args (not necessarily
411/// // of the same type) and returns a number.
412/// let digest_fn = Type::try_from(&TypeAst::try_from("(...[dyn Lin; N]) -> Num")?)?;
413/// let mut env = TypeEnvironment::new();
414/// env.insert("true", Prelude::True).insert("digest", digest_fn);
415///
416/// let code = r#"
417///     digest(1, 2, (3, 4), #{ x: 5, y: (6,) }) == 1;
418///     digest(3, true) == 0; // fails: `true` is not linear
419/// "#;
420/// let ast = Annotated::<F32Grammar>::parse_statements(code)?;
421/// let errors = env.process_statements(&ast).unwrap_err();
422///
423/// let err = errors.iter().next().unwrap();
424/// assert_eq!(*err.main_span().fragment(), "true");
425/// assert_matches!(err.kind(), ErrorKind::FailedConstraint { .. });
426/// # Ok(())
427/// # }
428/// ```
429#[derive(Clone, PartialEq)]
430pub struct DynConstraints<Prim: PrimitiveType> {
431    pub(crate) inner: CompleteConstraints<Prim>,
432}
433
434impl<Prim: PrimitiveType> fmt::Debug for DynConstraints<Prim> {
435    fn fmt(&self, formatter: &mut fmt::Formatter<'_>) -> fmt::Result {
436        fmt::Debug::fmt(&self.inner, formatter)
437    }
438}
439
440impl<Prim: PrimitiveType> fmt::Display for DynConstraints<Prim> {
441    fn fmt(&self, formatter: &mut fmt::Formatter<'_>) -> fmt::Result {
442        fmt::Display::fmt(&self.inner, formatter)
443    }
444}
445
446impl<Prim: PrimitiveType> From<Object<Prim>> for DynConstraints<Prim> {
447    fn from(object: Object<Prim>) -> Self {
448        Self {
449            inner: object.into(),
450        }
451    }
452}
453
454impl<Prim: PrimitiveType> DynConstraints<Prim> {
455    /// Creates constraints based on a single constraint.
456    pub fn just(constraint: impl ObjectSafeConstraint<Prim>) -> Self {
457        Self {
458            inner: CompleteConstraints::from(ConstraintSet::just(constraint)),
459        }
460    }
461
462    /// Checks if this constraint set is empty.
463    pub fn is_empty(&self) -> bool {
464        self.inner.is_empty()
465    }
466
467    /// Returns the enclosed object constraint, if any.
468    pub fn object(&self) -> Option<&Object<Prim>> {
469        self.inner.object.as_ref()
470    }
471
472    fn is_concrete(&self) -> bool {
473        self.inner.object.as_ref().map_or(true, Object::is_concrete)
474    }
475
476    /// Adds the specified `constraint` to these constraints.
477    pub fn insert(&mut self, constraint: impl ObjectSafeConstraint<Prim>) {
478        self.inner.simple.insert(constraint);
479    }
480}
481
482#[cfg(test)]
483mod tests {
484    use super::*;
485    use crate::ast::TypeAst;
486
487    use std::convert::TryFrom;
488
489    #[test]
490    fn types_are_equal_to_self() -> anyhow::Result<()> {
491        const SAMPLE_TYPES: &[&str] = &[
492            "Num",
493            "(Num, Bool)",
494            "(Num, ...[Bool; N]) -> ()",
495            "(Num) -> Num",
496            "for<'T: Lin> (['T; N]) -> 'T",
497        ];
498
499        for &sample_type in SAMPLE_TYPES {
500            let ty = <Type>::try_from(&TypeAst::try_from(sample_type)?)?;
501            assert!(ty.eq(&ty), "Type is not equal to self: {}", ty);
502        }
503        Ok(())
504    }
505
506    #[test]
507    fn equality_is_preserved_on_renaming_params() {
508        const EQUAL_FNS: &[&str] = &[
509            "for<'T: Lin> (['T; N]) -> 'T",
510            "for<'T: Lin> (['T; L]) -> 'T",
511            "for<'Ty: Lin> (['Ty; N]) -> 'Ty",
512            "for<'N: Lin> (['N; T]) -> 'N",
513        ];
514
515        let functions: Vec<Type> = EQUAL_FNS
516            .iter()
517            .map(|&s| Type::try_from(&TypeAst::try_from(s).unwrap()).unwrap())
518            .collect();
519        for (i, function) in functions.iter().enumerate() {
520            for other_function in &functions[(i + 1)..] {
521                assert_eq!(function, other_function);
522            }
523        }
524    }
525
526    #[test]
527    fn unequal_functions() {
528        const FUNCTIONS: &[&str] = &[
529            "for<'T: Lin> (['T; N]) -> 'T",
530            "for<len! N; 'T: Lin> (['T; N]) -> 'T",
531            "(['T; N]) -> 'T",
532            "for<'T: Lin> (['T; N], 'T) -> 'T",
533            "for<'T: Lin> (['T; N]) -> ('T)",
534        ];
535
536        let functions: Vec<Type> = FUNCTIONS
537            .iter()
538            .map(|&s| Type::try_from(&TypeAst::try_from(s).unwrap()).unwrap())
539            .collect();
540        for (i, function) in functions.iter().enumerate() {
541            for other_function in &functions[(i + 1)..] {
542                assert_ne!(function, other_function);
543            }
544        }
545    }
546
547    #[test]
548    fn concrete_types() {
549        let sample_types = &[
550            Type::NUM,
551            Type::BOOL,
552            Type::Any,
553            (Type::BOOL, Type::NUM).into(),
554            Type::try_from(&TypeAst::try_from("for<'T: Lin> (['T; N]) -> 'T").unwrap()).unwrap(),
555        ];
556
557        for ty in sample_types {
558            assert!(ty.is_concrete(), "{:?}", ty);
559        }
560    }
561
562    #[test]
563    fn non_concrete_types() {
564        let sample_types = &[
565            Type::free_var(2),
566            (Type::NUM, Type::free_var(0)).into(),
567            Function::builder()
568                .with_arg(Type::free_var(0))
569                .returning(Type::void())
570                .into(),
571        ];
572
573        for ty in sample_types {
574            assert!(!ty.is_concrete(), "{:?}", ty);
575        }
576    }
577}
arithmetic_typing/types/mod.rs

arithmetic_typing/types/
mod.rs
