Skip to main content

nu_protocol/ast/
cell_path.rs

1use super::Expression;
2use crate::{Span, casing::Casing};
3use nu_utils::{escape_quote_string, needs_quoting};
4use serde::{Deserialize, Serialize};
5use std::{
6    cmp::Ordering,
7    fmt::Display,
8    hash::{Hash, Hasher},
9    str::FromStr,
10};
11use winnow::Parser;
12
13/// One level of access of a [`CellPath`]
14#[derive(Debug, Clone)]
15pub enum PathMember {
16    /// Accessing a member by string (i.e. columns of a table or [`Record`](crate::Record))
17    String {
18        val: String,
19        span: Span,
20        /// If marked as optional don't throw an error if not found but perform default handling
21        /// (e.g. return `Value::Nothing`)
22        optional: bool,
23        /// Affects column lookup
24        casing: Casing,
25    },
26    /// Accessing a member by index (i.e. row of a table or item in a list)
27    Int {
28        val: usize,
29        span: Span,
30        /// If marked as optional don't throw an error if not found but perform default handling
31        /// (e.g. return `Value::Nothing`)
32        optional: bool,
33    },
34}
35
36impl PathMember {
37    pub fn int(val: usize, optional: bool, span: Span) -> Self {
38        PathMember::Int {
39            val,
40            span,
41            optional,
42        }
43    }
44
45    pub fn string(val: String, optional: bool, casing: Casing, span: Span) -> Self {
46        PathMember::String {
47            val,
48            span,
49            optional,
50            casing,
51        }
52    }
53
54    pub fn test_int(val: usize, optional: bool) -> Self {
55        PathMember::Int {
56            val,
57            optional,
58            span: Span::test_data(),
59        }
60    }
61
62    pub fn test_string(val: impl Into<String>, optional: bool, casing: Casing) -> Self {
63        PathMember::String {
64            val: val.into(),
65            optional,
66            casing,
67            span: Span::test_data(),
68        }
69    }
70
71    pub fn make_optional(&mut self) {
72        match self {
73            PathMember::String { optional, .. } => *optional = true,
74            PathMember::Int { optional, .. } => *optional = true,
75        }
76    }
77
78    pub fn make_insensitive(&mut self) {
79        match self {
80            PathMember::String { casing, .. } => *casing = Casing::Insensitive,
81            PathMember::Int { .. } => {}
82        }
83    }
84
85    pub fn span(&self) -> Span {
86        match self {
87            PathMember::String { span, .. } => *span,
88            PathMember::Int { span, .. } => *span,
89        }
90    }
91
92    /// Update the span of a path member with a new span if the current span is unknown or test data.
93    pub fn fallback_span(&mut self, span: Span) -> Span {
94        let fallback = span;
95        match self {
96            PathMember::String { span, .. } => span.fallback(fallback),
97            PathMember::Int { span, .. } => span.fallback(fallback),
98        }
99    }
100
101    /// Returns an estimate of the memory size used by this PathMember in bytes
102    pub fn memory_size(&self) -> usize {
103        match self {
104            PathMember::String { val, .. } => std::mem::size_of::<Self>() + val.capacity(),
105            PathMember::Int { .. } => std::mem::size_of::<Self>(),
106        }
107    }
108}
109
110impl PartialEq for PathMember {
111    fn eq(&self, other: &Self) -> bool {
112        self.partial_cmp(other) == Some(Ordering::Equal)
113    }
114}
115
116impl PartialOrd for PathMember {
117    /// Orders by variant (strings before ints), then `val`, `optional` and `casing`.
118    /// `span` is ignored, so [`PartialEq`] and [`Hash`] ignore it too.
119    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
120        match (self, other) {
121            (
122                Self::String {
123                    val: l_val,
124                    optional: l_opt,
125                    casing: l_casing,
126                    ..
127                },
128                Self::String {
129                    val: r_val,
130                    optional: r_opt,
131                    casing: r_casing,
132                    ..
133                },
134            ) => Some((l_val, l_opt, l_casing).cmp(&(r_val, r_opt, r_casing))),
135            (
136                Self::Int {
137                    val: l_val,
138                    optional: l_opt,
139                    ..
140                },
141                Self::Int {
142                    val: r_val,
143                    optional: r_opt,
144                    ..
145                },
146            ) => Some((l_val, l_opt).cmp(&(r_val, r_opt))),
147            (Self::Int { .. }, Self::String { .. }) => Some(Ordering::Greater),
148            (Self::String { .. }, Self::Int { .. }) => Some(Ordering::Less),
149        }
150    }
151}
152
153impl Hash for PathMember {
154    fn hash<H: Hasher>(&self, state: &mut H) {
155        std::mem::discriminant(self).hash(state);
156        match self {
157            Self::String {
158                val,
159                optional,
160                casing,
161                ..
162            } => (val, optional, casing).hash(state),
163            Self::Int { val, optional, .. } => (val, optional).hash(state),
164        }
165    }
166}
167
168impl Display for PathMember {
169    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
170        match self {
171            PathMember::Int { val, optional, .. } => {
172                let question_mark = if *optional { "?" } else { "" };
173                write!(f, "{val}{question_mark}")
174            }
175            PathMember::String {
176                val,
177                optional,
178                casing,
179                ..
180            } => {
181                let question_mark = if *optional { "?" } else { "" };
182                let exclamation_mark = if *casing == Casing::Insensitive {
183                    "!"
184                } else {
185                    ""
186                };
187                let val = if needs_quoting(val) {
188                    &escape_quote_string(val)
189                } else {
190                    val
191                };
192                write!(f, "{val}{exclamation_mark}{question_mark}")
193            }
194        }
195    }
196}
197
198#[derive(Debug, thiserror::Error)]
199#[error("could not parse path member {attempted:?}")]
200pub struct ParsePathMemberError {
201    attempted: String,
202}
203
204impl FromStr for PathMember {
205    type Err = ParsePathMemberError;
206
207    fn from_str(s: &str) -> Result<Self, Self::Err> {
208        parse::path_member
209            .parse(s)
210            .map_err(|_| ParsePathMemberError {
211                attempted: s.to_owned(),
212            })
213    }
214}
215
216impl Serialize for PathMember {
217    fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
218    where
219        S: serde::Serializer,
220    {
221        self.to_string().serialize(serializer)
222    }
223}
224
225impl<'de> Deserialize<'de> for PathMember {
226    fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
227    where
228        D: serde::Deserializer<'de>,
229    {
230        let s = String::deserialize(deserializer)?;
231        Self::from_str(&s).map_err(serde::de::Error::custom)
232    }
233}
234
235/// [`PathMember`] for testing purposes.
236///
237/// This path member may be converted via [`into_path_member`](Self::into_path_member) into a
238/// [`PathMember`] that is using a [`Span::test_data()`](crate::Span::test_data) span.
239#[doc(hidden)]
240pub struct TestPathMember<T>(T);
241
242impl<S: Into<String>> From<S> for TestPathMember<String> {
243    fn from(value: S) -> Self {
244        Self(value.into())
245    }
246}
247
248impl TestPathMember<String> {
249    pub fn into_path_member(self) -> PathMember {
250        PathMember::test_string(self.0, false, Casing::Sensitive)
251    }
252}
253
254impl From<usize> for TestPathMember<usize> {
255    fn from(value: usize) -> Self {
256        Self(value)
257    }
258}
259
260impl TestPathMember<usize> {
261    pub fn into_path_member(self) -> PathMember {
262        PathMember::test_int(self.0, false)
263    }
264}
265
266/// Represents the potentially nested access to fields/cells of a container type
267///
268/// In our current implementation for table access the order of row/column is commutative.
269/// This limits the number of possible rows to select in one [`CellPath`] to 1 as it could
270/// otherwise be ambiguous
271///
272/// ```nushell
273/// col1.0
274/// 0.col1
275/// col2
276/// 42
277/// ```
278#[derive(Debug, Clone, PartialEq, PartialOrd, Hash)]
279pub struct CellPath {
280    pub members: Vec<PathMember>,
281}
282
283impl CellPath {
284    pub fn empty() -> Self {
285        Self {
286            members: Vec::new(),
287        }
288    }
289
290    pub fn make_optional(&mut self) {
291        for member in &mut self.members {
292            member.make_optional();
293        }
294    }
295
296    pub fn make_insensitive(&mut self) {
297        for member in &mut self.members {
298            member.make_insensitive();
299        }
300    }
301
302    /// Compares like `==`, except that a string member's casing is ignored, so `a` equals `a!`.
303    ///
304    /// `select` and `reject` use this to skip a column that is requested twice as `a` and `a!`.
305    pub fn eq_ignore_casing(&self, other: &CellPath) -> bool {
306        self.members.len() == other.members.len()
307            && self
308                .members
309                .iter()
310                .zip(&other.members)
311                .all(|(lhs, rhs)| match (lhs, rhs) {
312                    (
313                        PathMember::String {
314                            val: l_val,
315                            optional: l_opt,
316                            ..
317                        },
318                        PathMember::String {
319                            val: r_val,
320                            optional: r_opt,
321                            ..
322                        },
323                    ) => l_val == r_val && l_opt == r_opt,
324                    _ => lhs == rhs,
325                })
326    }
327
328    // Formats the cell-path as a column name, i.e. without quoting and optional markers ('?').
329    pub fn to_column_name(&self) -> String {
330        let mut s = String::new();
331
332        for member in &self.members {
333            match member {
334                PathMember::Int { val, .. } => {
335                    s += &val.to_string();
336                }
337                PathMember::String { val, .. } => {
338                    s += val;
339                }
340            }
341
342            s.push('.');
343        }
344
345        s.pop(); // Easier than checking whether to insert the '.' on every iteration.
346        s
347    }
348
349    /// Returns an estimate of the memory size used by this CellPath in bytes
350    pub fn memory_size(&self) -> usize {
351        std::mem::size_of::<Self>() + self.members.iter().map(|m| m.memory_size()).sum::<usize>()
352    }
353
354    /// Update all path members with a new span if their current span is either unknown or test data.
355    pub fn fallback_span(&mut self, span: Span) {
356        for member in self.members.iter_mut() {
357            member.fallback_span(span);
358        }
359    }
360
361    /// Like [`fallback_span`] but allows chaining.
362    ///
363    /// This method is often used in parsing of data formats and therefore is constructed newly
364    /// where chaining is more ergonomic.
365    ///
366    /// # Example
367    /// ```
368    /// # use std::str::FromStr;
369    /// # use nu_protocol::{ast::CellPath, Span};
370    /// #
371    /// # let span = Span::test_data();
372    /// #
373    /// let cell_path = CellPath::from_str("$.abc").unwrap().with_fallback_span(span);
374    /// assert_eq!(cell_path.members[0].span(), span);
375    /// ```
376    pub fn with_fallback_span(mut self, span: Span) -> Self {
377        self.fallback_span(span);
378        self
379    }
380}
381
382impl Display for CellPath {
383    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
384        write!(f, "$")?;
385        for member in self.members.iter() {
386            write!(f, ".{member}")?;
387        }
388        // Empty cell-paths are `$.` not `$`
389        if self.members.is_empty() {
390            write!(f, ".")?;
391        }
392        Ok(())
393    }
394}
395
396#[derive(Debug, thiserror::Error)]
397#[error("could not parse cell path {attempted:?}")]
398pub struct ParseCellPathError {
399    attempted: String,
400}
401
402impl FromStr for CellPath {
403    type Err = ParseCellPathError;
404
405    fn from_str(s: &str) -> Result<Self, Self::Err> {
406        parse::cell_path.parse(s).map_err(|_| ParseCellPathError {
407            attempted: s.to_owned(),
408        })
409    }
410}
411
412impl Serialize for CellPath {
413    fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
414    where
415        S: serde::Serializer,
416    {
417        self.to_string().serialize(serializer)
418    }
419}
420
421impl<'de> Deserialize<'de> for CellPath {
422    fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
423    where
424        D: serde::Deserializer<'de>,
425    {
426        let s = String::deserialize(deserializer)?;
427        Self::from_str(&s).map_err(serde::de::Error::custom)
428    }
429}
430
431#[derive(Debug, Clone, PartialEq, Serialize, Deserialize)]
432pub struct FullCellPath {
433    pub head: Expression,
434    pub tail: Vec<PathMember>,
435}
436
437mod parse {
438    use super::*;
439    use winnow::{
440        Result, Str, combinator::*, error::*, prelude::*, stream::ContainsToken, token::*,
441    };
442
443    pub fn cell_path(input: &mut &str) -> Result<CellPath> {
444        preceded(opt("$."), repeat(0.., terminated(path_member, opt('.'))))
445            .parse_next(input)
446            .map(|members| CellPath { members })
447    }
448
449    pub fn path_member(input: &mut &str) -> Result<PathMember> {
450        if input.is_empty() {
451            return Err(ParserError::from_input(input));
452        }
453
454        let member = alt((int_path_member, string_path_member)).parse_next(input)?;
455
456        // ensure there's no more content after a member
457        peek(alt((".", eof))).parse_next(input)?;
458
459        Ok(member)
460    }
461
462    fn int_path_member(input: &mut &str) -> Result<PathMember> {
463        let int = digits.parse_next(input)?;
464        let modifier = modifier.parse_next(input)?;
465        Ok(PathMember::Int {
466            val: int,
467            span: Span::unknown(),
468            optional: modifier.optional,
469        })
470    }
471
472    fn digits(input: &mut &str) -> Result<usize> {
473        let start = input.checkpoint();
474        if let Ok(prefix) = digit_prefix.parse_next(input) {
475            return match prefix {
476                DigitPrefix::Bin => bin_digits.parse_next(input),
477                DigitPrefix::Oct => oct_digits.parse_next(input),
478                DigitPrefix::Hex => hex_digits.parse_next(input),
479            };
480        }
481
482        input.reset(&start);
483        dec_digits.parse_next(input)
484    }
485
486    enum DigitPrefix {
487        Bin,
488        Oct,
489        Hex,
490    }
491
492    fn digit_prefix(input: &mut &str) -> Result<DigitPrefix> {
493        let prefix = take(2usize).parse_next(input)?;
494        Ok(match prefix {
495            "0b" => DigitPrefix::Bin,
496            "0o" => DigitPrefix::Oct,
497            "0x" => DigitPrefix::Hex,
498            _ => return fail(input),
499        })
500    }
501
502    fn bin_digits(input: &mut &str) -> Result<usize> {
503        any_radix_digits(2, ('_', '0', '1')).parse_next(input)
504    }
505
506    fn oct_digits(input: &mut &str) -> Result<usize> {
507        any_radix_digits(8, ('_', '0'..='7')).parse_next(input)
508    }
509
510    fn dec_digits(input: &mut &str) -> Result<usize> {
511        any_radix_digits(10, ('_', '0'..='9')).parse_next(input)
512    }
513
514    fn hex_digits(input: &mut &str) -> Result<usize> {
515        any_radix_digits(16, ('_', '0'..='9', 'a'..='f', 'A'..='F')).parse_next(input)
516    }
517
518    fn any_radix_digits<'i>(
519        radix: u32,
520        tokens: impl ContainsToken<char>,
521    ) -> impl Parser<Str<'i>, usize, ContextError> {
522        take_while(1.., tokens)
523            .map(|d: &str| d.replace('_', ""))
524            .verify(|d: &str| !d.is_empty())
525            .try_map(move |d| usize::from_str_radix(&d, radix))
526    }
527
528    fn string_path_member(input: &mut &str) -> Result<PathMember> {
529        let string = alt((
530            single_quoted_string,
531            bare_word_string,
532            double_quoted_string,
533            unquoted_string,
534        ))
535        .parse_next(input)?;
536
537        let modifier = modifier.parse_next(input)?;
538
539        Ok(PathMember::String {
540            val: string,
541            span: Span::unknown(),
542            optional: modifier.optional,
543            casing: match modifier.case_insensitive {
544                true => Casing::Insensitive,
545                false => Default::default(),
546            },
547        })
548    }
549
550    fn unquoted_string(input: &mut &str) -> Result<String> {
551        struct UnquotedTokens;
552
553        impl ContainsToken<char> for UnquotedTokens {
554            fn contains_token(&self, token: char) -> bool {
555                match token {
556                    // spaces and tabs
557                    ' ' | '\n' | '\t' => false,
558
559                    // syntax characters
560                    '!' | '?' | '.' => false,
561
562                    // brackets
563                    '(' | ')' => false,
564
565                    _ => true,
566                }
567            }
568        }
569
570        take_while(0.., UnquotedTokens)
571            .parse_next(input)
572            .map(|s| s.to_owned())
573    }
574
575    fn single_quoted_string(input: &mut &str) -> Result<String> {
576        delimited("'", take_while(0.., |c| c != '\''), "'")
577            .parse_next(input)
578            .map(|s| s.to_owned())
579    }
580
581    fn bare_word_string(input: &mut &str) -> Result<String> {
582        delimited("`", take_while(0.., |c| c != '`'), "`")
583            .parse_next(input)
584            .map(|s| s.to_owned())
585    }
586
587    fn double_quoted_string(input: &mut &str) -> Result<String> {
588        fn escaped(input: &mut &str) -> Result<char> {
589            preceded(
590                '\\',
591                alt((
592                    'n'.value('\n'),
593                    'r'.value('\r'),
594                    't'.value('\t'),
595                    '\\'.value('\\'),
596                    '/'.value('/'),
597                    '"'.value('"'),
598                    // `PathMember`'s `Display` escapes a NUL as `\0`, and `alt` falls through
599                    // to the bare `char` parser on an unknown escape, which would read that as
600                    // a backslash followed by a `0` and hand back a four-character string.
601                    '0'.value('\0'),
602                )),
603            )
604            .parse_next(input)
605        }
606
607        fn char(input: &mut &str) -> Result<char> {
608            any.verify(|c| *c != '"').parse_next(input)
609        }
610
611        let content = repeat(0.., alt((escaped, char))).fold(String::new, |mut string, char| {
612            string.push(char);
613            string
614        });
615
616        delimited('"', content, '"').parse_next(input)
617    }
618
619    #[derive(Default)]
620    struct Modifier {
621        optional: bool,
622        case_insensitive: bool,
623    }
624
625    fn modifier(input: &mut &str) -> Result<Modifier> {
626        let mut modifier = Modifier::default();
627
628        loop {
629            let Some(next) = opt(alt(('!', '?'))).parse_next(input)? else {
630                break;
631            };
632
633            let expected = match (next, modifier.optional, modifier.case_insensitive) {
634                ('!', _, false) => {
635                    modifier.case_insensitive = true;
636                    continue;
637                }
638                ('?', false, _) => {
639                    modifier.optional = true;
640                    continue;
641                }
642                ('!', false, true) => "'?' or '.'",
643                ('!', true, true) => "'.'",
644                ('?', true, false) => "'!' or '.'",
645                ('?', true, true) => "'.'",
646                (c, _, _) => unreachable!("parser only returns with '!' or '?', got {c:?}"),
647            };
648
649            fail.context(StrContext::Expected(StrContextValue::Description(expected)))
650                .parse_next(input)?
651        }
652
653        Ok(modifier)
654    }
655}
656
657#[cfg(test)]
658mod test {
659    use super::*;
660    use std::cmp::Ordering::Greater;
661
662    #[test]
663    fn path_member_partial_ord() {
664        assert_eq!(
665            Some(Greater),
666            PathMember::test_int(5, true).partial_cmp(&PathMember::test_string(
667                "e",
668                true,
669                Casing::Sensitive
670            ))
671        );
672
673        assert_eq!(
674            Some(Greater),
675            PathMember::test_int(5, true).partial_cmp(&PathMember::test_int(5, false))
676        );
677
678        assert_eq!(
679            Some(Greater),
680            PathMember::test_int(6, true).partial_cmp(&PathMember::test_int(5, true))
681        );
682
683        assert_eq!(
684            Some(Greater),
685            PathMember::test_string("e", true, Casing::Sensitive)
686                .partial_cmp(&PathMember::test_string("e", false, Casing::Sensitive))
687        );
688
689        assert_eq!(
690            Some(Greater),
691            PathMember::test_string("f", true, Casing::Sensitive)
692                .partial_cmp(&PathMember::test_string("e", true, Casing::Sensitive))
693        );
694
695        // `e!` (case-insensitive) is a different member from `e`.
696        assert_eq!(
697            Some(Greater),
698            PathMember::test_string("e", true, Casing::Insensitive)
699                .partial_cmp(&PathMember::test_string("e", true, Casing::Sensitive))
700        );
701        assert_ne!(
702            PathMember::test_string("e", true, Casing::Insensitive),
703            PathMember::test_string("e", true, Casing::Sensitive)
704        );
705    }
706}