nu_protocol/
ty.rs

1use crate::{
2    CollectionColumns, CompareTypes, OneOf, SyntaxShape, TypeRelation, TypeSet, ast::PathMember,
3};
4use serde::{Deserialize, Serialize};
5use std::{borrow::Cow, fmt::Display};
6#[cfg(test)]
7use strum_macros::EnumIter;
8
9#[derive(Clone, Debug, Default, PartialEq, Eq, Serialize, Deserialize, Hash, Ord, PartialOrd)]
10#[cfg_attr(test, derive(EnumIter))]
11pub enum Type {
12    /// Top type, supertype of all types
13    Any,
14    Binary,
15    Block,
16    Bool,
17    CellPath,
18    Closure,
19    Custom(Box<str>),
20    Date,
21    Duration,
22    Error,
23    Filesize,
24    Float,
25    Int,
26    List(Box<Type>),
27    #[default]
28    Nothing,
29    /// Supertype of Int and Float. Equivalent to `oneof<int, float>`
30    Number,
31    /// Supertype of all types it contains.
32    OneOf(OneOf),
33    Range,
34    Record(CollectionColumns<Type>),
35    String,
36    Glob,
37    Table(CollectionColumns<Type>),
38}
39
40fn follow_cell_path_recursive<'a>(
41    current: Cow<'a, Type>,
42    path_members: &mut dyn Iterator<Item = &'a PathMember>,
43) -> Option<Cow<'a, Type>> {
44    let Some(first) = path_members.next() else {
45        return Some(current);
46    };
47    match (current.as_ref(), first) {
48        (Type::Record(_), PathMember::String { val, .. }) => {
49            let next = match current {
50                Cow::Borrowed(Type::Record(f)) => {
51                    Cow::Borrowed(&f.iter().find(|(name, _)| name == val)?.1)
52                }
53                Cow::Owned(Type::Record(f)) => {
54                    Cow::Owned(f.into_iter().find(|(name, _)| name == val)?.1)
55                }
56                _ => unreachable!(),
57            };
58            follow_cell_path_recursive(next, path_members)
59        }
60
61        // Table to Record (Int)
62        (Type::Table(f), PathMember::Int { .. }) => {
63            follow_cell_path_recursive(Cow::Owned(Type::Record(f.clone())), path_members)
64        }
65
66        // Table to List (String)
67        (Type::Table(columns), PathMember::String { val, .. }) => {
68            let (_, sub_type) = columns.iter().find(|(name, _)| name == val)?;
69            let list_type = Type::List(Box::new(sub_type.clone()));
70            follow_cell_path_recursive(Cow::Owned(list_type), path_members)
71        }
72
73        (Type::List(_), PathMember::Int { .. }) => {
74            let next = match current {
75                Cow::Borrowed(Type::List(i)) => Cow::Borrowed(i.as_ref()),
76                Cow::Owned(Type::List(i)) => Cow::Owned(*i),
77                _ => unreachable!(),
78            };
79            follow_cell_path_recursive(next, path_members)
80        }
81
82        // List of Records indexed by key names
83        (Type::List(_), PathMember::String { .. }) => {
84            let next = match current {
85                Cow::Borrowed(Type::List(i)) => Cow::Borrowed(i.as_ref()),
86                Cow::Owned(Type::List(i)) => Cow::Owned(*i),
87                _ => unreachable!(),
88            };
89
90            let mut found_int_member = false;
91            let mut new_iter = std::iter::once(first).chain(path_members).filter(|pm| {
92                let first_int = !found_int_member && matches!(pm, PathMember::Int { .. });
93                if first_int {
94                    found_int_member = true;
95                }
96                !first_int
97            });
98            let inner_ty = follow_cell_path_recursive(next, &mut new_iter);
99
100            // If there's no int path member, need to wrap in a List type
101            // e.g. [{foo: bar}].foo -> [bar], list<record<foo: string>> -> list<string>
102            if found_int_member {
103                inner_ty
104            } else {
105                inner_ty.map(|inner_ty| Cow::Owned(Type::List(Box::new(inner_ty.into_owned()))))
106            }
107        }
108
109        _ => None,
110    }
111}
112
113impl Type {
114    pub fn list(inner: Type) -> Self {
115        Self::List(Box::new(inner))
116    }
117
118    /// Creates a OneOf type from an iterator of types.
119    /// Flattens any nested OneOf types and removes duplicates.
120    pub fn one_of(types: impl IntoIterator<Item = Type>) -> Self {
121        Self::OneOf(OneOf::from_iter(types))
122    }
123
124    pub fn record() -> Self {
125        Self::Record(Default::default())
126    }
127
128    pub fn table() -> Self {
129        Self::Table(Default::default())
130    }
131
132    pub fn custom(name: impl Into<Box<str>>) -> Self {
133        Self::Custom(name.into())
134    }
135
136    /// Returns supertype of arguments without creating a `oneof`, or falling back to `any` (unless one or both of the arguments are `any`)
137    pub(crate) fn flat_widen(lhs: Type, rhs: Type) -> Result<Type, (Type, Type)> {
138        match (lhs, rhs) {
139            // short circuit on `any`
140            (Type::Any, _) | (_, Type::Any) => Ok(Type::Any),
141
142            // primitive number hierarchy is extremely common
143            (Type::Int, Type::Float) | (Type::Float, Type::Int) => Ok(Type::Number),
144
145            // despite their subtyping relation, these pairs should not combine into one or the other
146            tys @ ((Type::Glob, Type::String)
147            | (Type::String, Type::Glob)
148            | (Type::String | Type::Int, Type::CellPath)
149            | (Type::CellPath, Type::String | Type::Int)) => Err(tys),
150
151            // widen structural collections without checking for subtyping
152            (Type::Record(lhs), Type::Record(rhs)) => Ok(Type::Record(lhs.union(rhs))),
153            (Type::Table(lhs), Type::Table(rhs)) => Ok(Type::Table(lhs.union(rhs))),
154
155            // We want to have `oneof<list<T>, table>`, regardless whether one counts as a subtype
156            // of the other.
157            tys @ ((Type::List(_), Type::Table(_)) | (Type::Table(_), Type::List(_))) => Err(tys),
158
159            // If one type is already a subtype of the other, we can skip all of the heavier logic below.
160            (lhs, rhs) => match lhs.compare_types(&rhs) {
161                Some(rel) => Ok(match rel {
162                    TypeRelation::Subtype => rhs,
163                    TypeRelation::Equal => lhs,
164                    TypeRelation::Supertype => lhs,
165                }),
166                // Fallback - the two types are unrelated. Move them out so that callers don't have to clone again.
167                None => Err((lhs, rhs)),
168            },
169        }
170    }
171
172    /// Returns a supertype of all types within `it` *that is not `Any`*.
173    /// If `it` contains `Type::Any`, short circuits and returns `None`.
174    pub fn supertype_of(it: impl IntoIterator<Item = Type>) -> Option<Self> {
175        let mut it = it.into_iter();
176        it.next().and_then(|head| {
177            it.try_fold(head, |acc, e| match acc.union(e) {
178                Type::Any => None,
179                r => Some(r),
180            })
181        })
182    }
183
184    pub fn is_numeric(&self) -> bool {
185        matches!(self, Type::Int | Type::Float | Type::Number)
186    }
187
188    pub fn is_list(&self) -> bool {
189        matches!(self, Type::List(_))
190    }
191
192    /// Does this type represent a data structure containing values that can be addressed using 'cell paths'?
193    pub fn accepts_cell_paths(&self) -> bool {
194        matches!(self, Type::List(_) | Type::Record(_) | Type::Table(_))
195    }
196
197    pub fn to_shape(&self) -> SyntaxShape {
198        match self {
199            Type::Int => SyntaxShape::Int,
200            Type::Float => SyntaxShape::Float,
201            Type::Range => SyntaxShape::Range,
202            Type::Bool => SyntaxShape::Boolean,
203            Type::String => SyntaxShape::String,
204            Type::Block => SyntaxShape::Block, // FIXME needs more accuracy
205            Type::Closure => SyntaxShape::Closure(None), // FIXME needs more accuracy
206            Type::CellPath => SyntaxShape::CellPath,
207            Type::Duration => SyntaxShape::Duration,
208            Type::Date => SyntaxShape::DateTime,
209            Type::Filesize => SyntaxShape::Filesize,
210            Type::List(x) => SyntaxShape::List(Box::new(x.to_shape())),
211            Type::Number => SyntaxShape::Number,
212            Type::OneOf(types) => SyntaxShape::OneOf(types.iter().map(Type::to_shape).collect()),
213            Type::Nothing => SyntaxShape::Nothing,
214            Type::Record(entries) => SyntaxShape::Record(entries.map(Type::to_shape)),
215            Type::Table(columns) => SyntaxShape::Table(columns.map(Type::to_shape)),
216            Type::Any => SyntaxShape::Any,
217            Type::Error => SyntaxShape::Any,
218            Type::Binary => SyntaxShape::Binary,
219            Type::Custom(_) => SyntaxShape::Any,
220            Type::Glob => SyntaxShape::GlobPattern,
221        }
222    }
223
224    /// Get a string representation, without inner type specification of lists,
225    /// tables and records (get `list` instead of `list<any>`
226    pub fn get_non_specified_string(&self) -> String {
227        match self {
228            Type::Closure => String::from("closure"),
229            Type::Bool => String::from("bool"),
230            Type::Block => String::from("block"),
231            Type::CellPath => String::from("cell-path"),
232            Type::Date => String::from("datetime"),
233            Type::Duration => String::from("duration"),
234            Type::Filesize => String::from("filesize"),
235            Type::Float => String::from("float"),
236            Type::Int => String::from("int"),
237            Type::Range => String::from("range"),
238            Type::Record(_) => String::from("record"),
239            Type::Table(_) => String::from("table"),
240            Type::List(_) => String::from("list"),
241            Type::Nothing => String::from("nothing"),
242            Type::Number => String::from("number"),
243            Type::OneOf(_) => String::from("oneof"),
244            Type::String => String::from("string"),
245            Type::Any => String::from("any"),
246            Type::Error => String::from("error"),
247            Type::Binary => String::from("binary"),
248            Type::Custom(_) => String::from("custom"),
249            Type::Glob => String::from("glob"),
250        }
251    }
252
253    pub fn follow_cell_path<'a>(&'a self, path_members: &'a [PathMember]) -> Option<Cow<'a, Self>> {
254        follow_cell_path_recursive(Cow::Borrowed(self), &mut path_members.iter())
255    }
256}
257
258impl CompareTypes for Type {
259    fn compare_types(&self, other: &Self) -> Option<TypeRelation> {
260        match (self, other) {
261            (_, Type::Any) => Some(TypeRelation::Subtype),
262            (Type::Any, _) => Some(TypeRelation::Supertype),
263
264            // I don't know how this was decided but this is the behavior that was present in the
265            // parser
266            (Type::Closure, Type::Block) => Some(TypeRelation::Supertype),
267            (Type::Block, Type::Closure) => Some(TypeRelation::Subtype),
268
269            // We want `get`/`select`/etc to accept string and int values, so it's convenient to
270            // use them with variables, without having to explicitly convert them into cell-paths
271            (Type::String | Type::Int, Type::CellPath) => Some(TypeRelation::Subtype),
272            (Type::CellPath, Type::String | Type::Int) => Some(TypeRelation::Supertype),
273
274            (Type::Float | Type::Int, Type::Number) => Some(TypeRelation::Subtype),
275            (Type::Number, Type::Float | Type::Int) => Some(TypeRelation::Supertype),
276
277            (Type::Glob, Type::String) => Some(TypeRelation::Supertype),
278            (Type::String, Type::Glob) => Some(TypeRelation::Subtype),
279
280            // List is covariant
281            (Type::List(t), Type::List(u)) => t.compare_types(u.as_ref()),
282
283            (Type::Record(this), Type::Record(that)) | (Type::Table(this), Type::Table(that)) => {
284                this.compare_types(that)
285            }
286
287            (Type::Table(table_cols), Type::List(list_elem)) => match list_elem.as_ref() {
288                Type::Any => Some(TypeRelation::Subtype),
289                Type::Record(record_cols) => table_cols.compare_types(record_cols),
290                ty => Type::Record(table_cols.clone()).compare_types(ty),
291            },
292            (Type::List(list_elem), Type::Table(table_cols)) => match list_elem.as_ref() {
293                Type::Any => Some(TypeRelation::Supertype),
294                Type::Record(record_cols) => record_cols.compare_types(table_cols),
295                ty => ty.compare_types(&Type::Record(table_cols.clone())),
296            },
297
298            (Type::OneOf(lhs_oneof), Type::OneOf(rhs_oneof)) => lhs_oneof.compare_types(rhs_oneof),
299            (Type::OneOf(lhs_oneof), rhs) => lhs_oneof.compare_types(rhs),
300            (lhs, Type::OneOf(rhs_oneof)) => lhs.compare_types(rhs_oneof),
301
302            (t, u) if t == u => Some(TypeRelation::Equal),
303
304            _ => None,
305        }
306    }
307
308    /// Determine of the [`Type`] is a [subtype](https://en.wikipedia.org/wiki/Subtyping) of `other`.
309    ///
310    /// This should only be used at parse-time.
311    /// If you have a concrete [`Value`](crate::Value) or [`PipelineData`](crate::PipelineData),
312    /// you should use their respective `is_subtype_of` methods instead.
313    // This is identical to this method's default implementation. Written here to attach doccomment.
314    fn is_subtype_of(&self, other: &Self) -> bool {
315        matches!(
316            self.compare_types(other),
317            Some(TypeRelation::Subtype | TypeRelation::Equal)
318        )
319    }
320
321    fn is_any(&self) -> bool {
322        matches!(self, Type::Any)
323    }
324
325    fn is_assignable_to(&self, dst: &Self) -> bool {
326        let src = self;
327        match (dst, src) {
328            (Type::Table(dst_cols), Type::List(src_ty)) => match src_ty.as_ref() {
329                Type::Any => true,
330                Type::Record(src_cols) => src_cols.is_assignable_to(dst_cols),
331                src_ty => src_ty.is_assignable_to(&Type::Record(dst_cols.clone())),
332            },
333            (Type::List(dst_ty), Type::Table(src_cols)) => match dst_ty.as_ref() {
334                Type::Any => true,
335                Type::Record(dst_cols) => src_cols.is_assignable_to(dst_cols),
336                dst_ty => Type::Record(src_cols.clone()).is_assignable_to(dst_ty),
337            },
338            (Type::List(dst_ty), Type::List(src_ty)) => src_ty.is_assignable_to(dst_ty.as_ref()),
339            (Type::Record(dst_cols), Type::Record(src_cols))
340            | (Type::Table(dst_cols), Type::Table(src_cols)) => src_cols.is_assignable_to(dst_cols),
341            // strings can be coerced globs
342            (Type::Glob, Type::String) => true,
343            // but not the other way around
344            (Type::String, Type::Glob) => false,
345            // strings can be coerced to semver
346            (Type::OneOf(dst_tys), Type::OneOf(src_tys)) => src_tys.is_assignable_to(dst_tys),
347            (Type::OneOf(dst_tys), src_ty) => src_ty.is_assignable_to(dst_tys),
348            (dst_ty, Type::OneOf(src_tys)) => src_tys.is_assignable_to(dst_ty),
349            // leave it to the runtime
350            (Type::List(_) | Type::Table(_) | Type::Record(_), Type::Custom(_)) => true,
351            (lhs, rhs @ Type::CellPath) => rhs.is_subtype_of(lhs),
352            (lhs, rhs) => rhs.compare_types(lhs).is_some(),
353        }
354    }
355}
356
357impl TypeSet for Type {
358    fn union(self, other: Self) -> Self {
359        let (lhs, rhs) = match Self::flat_widen(self, other) {
360            Ok(t) => return t,
361            Err(tys) => tys,
362        };
363
364        match (lhs, rhs) {
365            (Type::OneOf(ts), Type::OneOf(us)) => Type::OneOf(ts.union(us)),
366            (Type::OneOf(oneof), t) | (t, Type::OneOf(oneof)) => Type::OneOf(oneof.add_ty(t)),
367            (this, other) => Type::one_of([this, other]),
368        }
369    }
370}
371
372impl Display for Type {
373    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
374        match self {
375            Type::Block => write!(f, "block"),
376            Type::Closure => write!(f, "closure"),
377            Type::Bool => write!(f, "bool"),
378            Type::CellPath => write!(f, "cell-path"),
379            Type::Date => write!(f, "datetime"),
380            Type::Duration => write!(f, "duration"),
381            Type::Filesize => write!(f, "filesize"),
382            Type::Float => write!(f, "float"),
383            Type::Int => write!(f, "int"),
384            Type::Range => write!(f, "range"),
385            Type::Record(columns) => write!(f, "record{columns}"),
386            Type::Table(columns) => write!(f, "table{columns}"),
387            Type::List(l) => write!(f, "list<{l}>"),
388            Type::Nothing => write!(f, "nothing"),
389            Type::Number => write!(f, "number"),
390            Type::OneOf(oneof) => write!(f, "{oneof}"),
391            Type::String => write!(f, "string"),
392            Type::Any => write!(f, "any"),
393            Type::Error => write!(f, "error"),
394            Type::Binary => write!(f, "binary"),
395            Type::Custom(custom) => write!(f, "{custom}"),
396            Type::Glob => write!(f, "glob"),
397        }
398    }
399}
400
401/// Get a string nicely combining multiple types
402///
403/// Helpful for listing types in errors
404pub fn combined_type_string<'a, I>(types: I, join_word: &str) -> Option<String>
405where
406    I: IntoIterator<Item = &'a Type>,
407{
408    use std::fmt::Write as _;
409
410    // Deduplicate types to avoid confusing repeated entries like
411    // "binary, binary, binary, or binary" in error messages.
412    let mut seen = Vec::new();
413    for t in types {
414        if !seen.contains(t) {
415            seen.push(t.clone());
416        }
417    }
418
419    match seen.as_slice() {
420        [] => None,
421        [one] => Some(one.to_string()),
422        [one, two] => Some(format!("{one} {join_word} {two}")),
423        [initial @ .., last] => {
424            let mut out = String::new();
425            for ele in initial {
426                let _ = write!(out, "{ele}, ");
427            }
428            let _ = write!(out, "{join_word} {last}");
429            Some(out)
430        }
431    }
432}
433
434#[cfg(test)]
435mod tests {
436    use super::*;
437    use strum::IntoEnumIterator;
438
439    mod subtype_relation {
440        use super::*;
441
442        #[test]
443        fn test_reflexivity() {
444            for ty in Type::iter() {
445                assert!(ty.is_subtype_of(&ty));
446            }
447        }
448
449        #[test]
450        fn test_any_is_top_type() {
451            for ty in Type::iter() {
452                assert!(ty.is_subtype_of(&Type::Any));
453            }
454        }
455
456        #[test]
457        fn test_number_supertype() {
458            assert!(Type::Int.is_subtype_of(&Type::Number));
459            assert!(Type::Float.is_subtype_of(&Type::Number));
460        }
461
462        #[test]
463        fn test_list_covariance() {
464            for ty1 in Type::iter() {
465                for ty2 in Type::iter() {
466                    let list_ty1 = Type::List(Box::new(ty1.clone()));
467                    let list_ty2 = Type::List(Box::new(ty2.clone()));
468                    assert_eq!(list_ty1.is_subtype_of(&list_ty2), ty1.is_subtype_of(&ty2));
469                }
470            }
471        }
472
473        #[test]
474        fn table_list_oneof_covariance() {
475            let columns = CollectionColumns::<Type>::default();
476
477            let single_ty = Type::Record(columns.clone());
478            let union_ty = Type::one_of([Type::Number, Type::Record(columns.clone())]);
479
480            let direct_cmp = union_ty.compare_types(&single_ty);
481            let list_cmp = Type::list(union_ty.clone()).compare_types(&Type::list(single_ty));
482
483            let table_cmp = Type::list(union_ty).compare_types(&Type::Table(columns));
484
485            assert_eq!(list_cmp, direct_cmp);
486            assert_eq!(table_cmp, list_cmp);
487        }
488    }
489
490    mod oneof {
491        use super::*;
492
493        #[test]
494        fn oneof_lhs() {
495            let rel = Type::one_of([Type::Int, Type::Nothing]).compare_types(&Type::Int);
496            assert_eq!(rel, Some(TypeRelation::Supertype));
497        }
498
499        #[test]
500        fn oneof_rhs() {
501            let rel = Type::Int.compare_types(&Type::one_of([Type::Int, Type::Nothing]));
502            assert_eq!(rel, Some(TypeRelation::Subtype));
503        }
504    }
505
506    mod oneof_flattening {
507        use super::*;
508
509        #[test]
510        fn test_oneof_creation_flattens() {
511            let nested = Type::one_of([
512                Type::String,
513                Type::one_of([Type::Int, Type::Float]),
514                Type::Bool,
515            ]);
516            if let Type::OneOf(oneof) = nested {
517                let types_vec: Vec<Type> = oneof.into_iter().collect();
518                assert_eq!(types_vec.len(), 3);
519                assert!(types_vec.contains(&Type::String));
520                assert!(types_vec.contains(&Type::Number));
521                assert!(types_vec.contains(&Type::Bool));
522            } else {
523                panic!("Expected OneOf");
524            }
525        }
526
527        #[test]
528        fn test_widen_flattens_oneof() {
529            let a = Type::one_of([Type::String, Type::Int]);
530            let b = Type::one_of([Type::Float, Type::Bool]);
531            let widened = a.union(b);
532            if let Type::OneOf(oneof) = widened {
533                let types_vec: Vec<Type> = oneof.into_iter().collect();
534                assert_eq!(types_vec.len(), 3);
535                assert!(types_vec.contains(&Type::String));
536                assert!(types_vec.contains(&Type::Number)); // Int + Float -> Number
537                assert!(types_vec.contains(&Type::Bool));
538            } else {
539                panic!("Expected OneOf");
540            }
541        }
542
543        #[test]
544        fn test_oneof_deduplicates() {
545            let record_type =
546                Type::Record(vec![("content".to_string(), Type::list(Type::String))].into());
547            let oneof = Type::one_of([Type::String, record_type.clone(), record_type.clone()]);
548            if let Type::OneOf(oneof) = oneof {
549                let types_vec: Vec<Type> = oneof.into_iter().collect();
550                assert_eq!(types_vec.len(), 2);
551                assert!(types_vec.contains(&Type::String));
552                assert!(types_vec.contains(&record_type));
553            } else {
554                panic!("Expected OneOf");
555            }
556        }
557    }
558
559    // regressions and performance tests for the subtype shortcut added above
560    mod widen_shortcuts {
561        use super::*;
562
563        #[test]
564        fn test_widen_subtype_shortcut() {
565            // widening a union that already covers the new type should return the original union unchanged.
566            let union = Type::one_of([Type::String, Type::Number]);
567            let result = union.clone().union(Type::Int);
568            assert_eq!(result, union);
569
570            // symmetric case where the left side is the subtype
571            let union2 = Type::one_of([Type::Int, Type::String]);
572            let result2 = Type::Int.union(union2.clone());
573            assert_eq!(result2, union2);
574        }
575
576        #[test]
577        fn test_chain_shortcut() {
578            // repeatedly widen the same type pair
579            let mut t = Type::String;
580            for _ in 0..100 {
581                t = t.union(Type::Int);
582            }
583            let expected = Type::one_of([Type::String, Type::Int]);
584            assert_eq!(t, expected);
585        }
586
587        #[test]
588        fn test_list_table_widen_preserves_list() {
589            let list_record = Type::list(Type::Record(vec![("a".to_string(), Type::Int)].into()));
590            let table = Type::Table(vec![("a".to_string(), Type::Int)].into());
591
592            let widened = list_record.clone().union(table.clone());
593            let expected = Type::one_of([list_record, table]);
594
595            assert_eq!(widened, expected);
596        }
597
598        #[test]
599        fn test_glob_string_union() {
600            let g = Type::Glob;
601            let s = Type::String;
602            let w1 = g.clone().union(s.clone());
603            let w2 = s.clone().union(g.clone());
604            let expected1 = Type::one_of([Type::Glob, Type::String]);
605            let expected2 = Type::one_of([Type::String, Type::Glob]);
606            assert_eq!(w1, expected1);
607            assert_eq!(w2, expected2);
608        }
609    }
610}
nu_protocol/ty.rs

nu_protocol/
ty.rs
