shuck_parser/parser/lexer/
mod.rs

1//! Lexer for bash scripts
2//!
3//! Tokenizes input into a stream of tokens with source position tracking.
4
5use std::{collections::VecDeque, ops::Range, sync::Arc};
6
7use memchr::{memchr, memchr_iter, memrchr};
8use shuck_ast::{Position, Span, TokenKind};
9use smallvec::SmallVec;
10
11use super::{ShellDialect, ShellProfile, ZshOptionState, ZshOptionTimeline};
12
13#[derive(Debug, Clone, Copy, PartialEq, Eq, Default)]
14pub(crate) struct TokenFlags(u8);
15
16impl TokenFlags {
17    const COOKED_TEXT: u8 = 1 << 0;
18    const SYNTHETIC: u8 = 1 << 1;
19
20    const fn empty() -> Self {
21        Self(0)
22    }
23
24    const fn cooked_text() -> Self {
25        Self(Self::COOKED_TEXT)
26    }
27
28    pub(crate) const fn with_synthetic(self) -> Self {
29        Self(self.0 | Self::SYNTHETIC)
30    }
31
32    pub(crate) const fn has_cooked_text(self) -> bool {
33        self.0 & Self::COOKED_TEXT != 0
34    }
35
36    pub(crate) const fn is_synthetic(self) -> bool {
37        self.0 & Self::SYNTHETIC != 0
38    }
39}
40
41#[derive(Debug, Clone, PartialEq, Eq)]
42pub(crate) enum TokenText<'a> {
43    Borrowed(&'a str),
44    Shared {
45        source: Arc<str>,
46        range: Range<usize>,
47    },
48    Owned(String),
49}
50
51impl TokenText<'_> {
52    pub(crate) fn as_str(&self) -> &str {
53        match self {
54            Self::Borrowed(text) => text,
55            Self::Shared { source, range } => &source[range.clone()],
56            Self::Owned(text) => text,
57        }
58    }
59
60    fn into_owned<'a>(self) -> TokenText<'a> {
61        match self {
62            Self::Borrowed(text) => TokenText::Owned(text.to_string()),
63            Self::Shared { source, range } => TokenText::Shared { source, range },
64            Self::Owned(text) => TokenText::Owned(text),
65        }
66    }
67
68    fn into_shared<'a>(self, source: &Arc<str>, span: Option<Span>) -> TokenText<'a> {
69        match self {
70            Self::Borrowed(text) => span
71                .filter(|span| span.end.offset <= source.len())
72                .map_or_else(
73                    || TokenText::Owned(text.to_string()),
74                    |span| TokenText::Shared {
75                        source: Arc::clone(source),
76                        range: span.start.offset..span.end.offset,
77                    },
78                ),
79            Self::Shared { source, range } => TokenText::Shared { source, range },
80            Self::Owned(text) => TokenText::Owned(text),
81        }
82    }
83}
84
85/// Classification of one segment inside a lexed shell word.
86#[derive(Debug, Clone, Copy, PartialEq, Eq)]
87pub(crate) enum LexedWordSegmentKind {
88    /// Unquoted or otherwise plain text.
89    Plain,
90    /// Text from a single-quoted string.
91    SingleQuoted,
92    /// Text from a `$'...'` string.
93    DollarSingleQuoted,
94    /// Text from a double-quoted string.
95    DoubleQuoted,
96    /// Text from a `$"..."` string.
97    DollarDoubleQuoted,
98    /// Text composed from multiple lexical forms.
99    Composite,
100}
101
102/// One segment of a lexed shell word, optionally backed by source text.
103#[derive(Debug, Clone, PartialEq, Eq)]
104pub(crate) struct LexedWordSegment<'a> {
105    kind: LexedWordSegmentKind,
106    text: TokenText<'a>,
107    span: Option<Span>,
108    wrapper_span: Option<Span>,
109}
110
111impl<'a> LexedWordSegment<'a> {
112    fn borrowed(kind: LexedWordSegmentKind, text: &'a str, span: Option<Span>) -> Self {
113        Self {
114            kind,
115            text: TokenText::Borrowed(text),
116            span,
117            wrapper_span: span,
118        }
119    }
120
121    fn borrowed_with_spans(
122        kind: LexedWordSegmentKind,
123        text: &'a str,
124        span: Option<Span>,
125        wrapper_span: Option<Span>,
126    ) -> Self {
127        Self {
128            kind,
129            text: TokenText::Borrowed(text),
130            span,
131            wrapper_span,
132        }
133    }
134
135    fn owned(kind: LexedWordSegmentKind, text: String) -> Self {
136        Self {
137            kind,
138            text: TokenText::Owned(text),
139            span: None,
140            wrapper_span: None,
141        }
142    }
143
144    fn owned_with_spans(
145        kind: LexedWordSegmentKind,
146        text: String,
147        span: Option<Span>,
148        wrapper_span: Option<Span>,
149    ) -> Self {
150        Self {
151            kind,
152            text: TokenText::Owned(text),
153            span,
154            wrapper_span,
155        }
156    }
157
158    /// Borrow this segment's cooked text.
159    pub(crate) fn as_str(&self) -> &str {
160        self.text.as_str()
161    }
162
163    pub(crate) const fn text_is_source_backed(&self) -> bool {
164        matches!(self.text, TokenText::Borrowed(_) | TokenText::Shared { .. })
165    }
166
167    /// Return the lexical classification of this segment.
168    pub(crate) const fn kind(&self) -> LexedWordSegmentKind {
169        self.kind
170    }
171
172    /// Return the span of the inner text, if it is tracked.
173    pub(crate) const fn span(&self) -> Option<Span> {
174        self.span
175    }
176
177    /// Return the span including surrounding quoting syntax when available.
178    pub(crate) fn wrapper_span(&self) -> Option<Span> {
179        self.wrapper_span.or(self.span)
180    }
181
182    fn rebased(mut self, base: Position) -> Self {
183        self.span = self.span.map(|span| span.rebased(base));
184        self.wrapper_span = self.wrapper_span.map(|span| span.rebased(base));
185        self
186    }
187
188    fn into_owned<'b>(self) -> LexedWordSegment<'b> {
189        LexedWordSegment {
190            kind: self.kind,
191            text: self.text.into_owned(),
192            span: self.span,
193            wrapper_span: self.wrapper_span,
194        }
195    }
196
197    fn into_shared<'b>(self, source: &Arc<str>) -> LexedWordSegment<'b> {
198        LexedWordSegment {
199            kind: self.kind,
200            text: self.text.into_shared(source, self.span),
201            span: self.span,
202            wrapper_span: self.wrapper_span,
203        }
204    }
205}
206
207/// Source-backed representation of a shell word produced by the lexer.
208#[derive(Debug, Clone, PartialEq, Eq)]
209pub(crate) struct LexedWord<'a> {
210    primary_segment: LexedWordSegment<'a>,
211    trailing_segments: Vec<LexedWordSegment<'a>>,
212}
213
214impl<'a> LexedWord<'a> {
215    fn from_segment(primary_segment: LexedWordSegment<'a>) -> Self {
216        Self {
217            primary_segment,
218            trailing_segments: Vec::new(),
219        }
220    }
221
222    fn borrowed(kind: LexedWordSegmentKind, text: &'a str, span: Option<Span>) -> Self {
223        Self::from_segment(LexedWordSegment::borrowed(kind, text, span))
224    }
225
226    fn owned(kind: LexedWordSegmentKind, text: String) -> Self {
227        Self::from_segment(LexedWordSegment::owned(kind, text))
228    }
229
230    fn push_segment(&mut self, segment: LexedWordSegment<'a>) {
231        self.trailing_segments.push(segment);
232    }
233
234    /// Iterate over the segments that make up this word.
235    pub(crate) fn segments(&self) -> impl Iterator<Item = &LexedWordSegment<'a>> {
236        std::iter::once(&self.primary_segment).chain(self.trailing_segments.iter())
237    }
238
239    /// Return the word text when it is represented by a single segment.
240    pub(crate) fn text(&self) -> Option<&str> {
241        self.single_segment().map(LexedWordSegment::as_str)
242    }
243
244    /// Join all segments into an owned string.
245    pub(crate) fn joined_text(&self) -> String {
246        let mut text = String::new();
247        for segment in self.segments() {
248            text.push_str(segment.as_str());
249        }
250        text
251    }
252
253    /// Return the only segment when this word is not segmented.
254    pub(crate) fn single_segment(&self) -> Option<&LexedWordSegment<'a>> {
255        self.trailing_segments
256            .is_empty()
257            .then_some(&self.primary_segment)
258    }
259
260    fn has_cooked_text(&self) -> bool {
261        self.segments()
262            .any(|segment| matches!(segment.text, TokenText::Owned(_)))
263    }
264
265    fn rebased(mut self, base: Position) -> Self {
266        self.primary_segment = self.primary_segment.rebased(base);
267        self.trailing_segments = self
268            .trailing_segments
269            .into_iter()
270            .map(|segment| segment.rebased(base))
271            .collect();
272        self
273    }
274
275    fn into_owned<'b>(self) -> LexedWord<'b> {
276        LexedWord {
277            primary_segment: self.primary_segment.into_owned(),
278            trailing_segments: self
279                .trailing_segments
280                .into_iter()
281                .map(LexedWordSegment::into_owned)
282                .collect(),
283        }
284    }
285
286    fn into_shared<'b>(self, source: &Arc<str>) -> LexedWord<'b> {
287        LexedWord {
288            primary_segment: self.primary_segment.into_shared(source),
289            trailing_segments: self
290                .trailing_segments
291                .into_iter()
292                .map(|segment| segment.into_shared(source))
293                .collect(),
294        }
295    }
296}
297
298/// Kinds of lexer error payloads attached to `TokenKind::Error`.
299#[derive(Debug, Clone, Copy, PartialEq, Eq)]
300pub(crate) enum LexerErrorKind {
301    /// Unterminated `$()` command substitution.
302    CommandSubstitution,
303    /// Unterminated backtick command substitution.
304    BacktickSubstitution,
305    /// Unterminated single-quoted string.
306    SingleQuote,
307    /// Unterminated double-quoted string.
308    DoubleQuote,
309}
310
311impl LexerErrorKind {
312    /// Human-readable message for this lexer error kind.
313    pub(crate) const fn message(self) -> &'static str {
314        match self {
315            Self::CommandSubstitution => "unterminated command substitution",
316            Self::BacktickSubstitution => "unterminated backtick substitution",
317            Self::SingleQuote => "unterminated single quote",
318            Self::DoubleQuote => "unterminated double quote",
319        }
320    }
321}
322
323#[derive(Debug, Clone, Copy, PartialEq, Eq)]
324pub(crate) struct LexerError {
325    kind: LexerErrorKind,
326    position: Position,
327}
328
329impl LexerError {
330    fn new(kind: LexerErrorKind, position: Position) -> Self {
331        Self { kind, position }
332    }
333}
334
335#[derive(Debug, Clone, PartialEq, Eq)]
336pub(crate) enum TokenPayload<'a> {
337    None,
338    Word(LexedWord<'a>),
339    Fd(i32),
340    FdPair(i32, i32),
341    Error(LexerErrorKind),
342}
343
344/// Token produced by the shell lexer.
345///
346/// Public consumers can inspect the token kind and source span. Word payloads,
347/// descriptor payloads, and lexer recovery details are currently parser-internal
348/// so the lexer can evolve without expanding the public API.
349#[derive(Debug, Clone, PartialEq, Eq)]
350pub struct LexedToken<'a> {
351    /// Token kind used by the parser.
352    pub kind: TokenKind,
353    /// Source span covered by the token.
354    pub span: Span,
355    pub(crate) flags: TokenFlags,
356    payload: TokenPayload<'a>,
357}
358
359impl<'a> LexedToken<'a> {
360    fn word_segment_kind(kind: TokenKind) -> LexedWordSegmentKind {
361        match kind {
362            TokenKind::Word => LexedWordSegmentKind::Plain,
363            TokenKind::LiteralWord => LexedWordSegmentKind::SingleQuoted,
364            TokenKind::QuotedWord => LexedWordSegmentKind::DoubleQuoted,
365            _ => LexedWordSegmentKind::Composite,
366        }
367    }
368
369    pub(crate) fn punctuation(kind: TokenKind) -> Self {
370        Self {
371            kind,
372            span: Span::new(),
373            flags: TokenFlags::empty(),
374            payload: TokenPayload::None,
375        }
376    }
377
378    fn with_word_payload(kind: TokenKind, word: LexedWord<'a>) -> Self {
379        let flags = if word.has_cooked_text() {
380            TokenFlags::cooked_text()
381        } else {
382            TokenFlags::empty()
383        };
384
385        Self {
386            kind,
387            span: Span::new(),
388            flags,
389            payload: TokenPayload::Word(word),
390        }
391    }
392
393    fn borrowed_word(kind: TokenKind, text: &'a str, text_span: Option<Span>) -> Self {
394        Self::with_word_payload(
395            kind,
396            LexedWord::borrowed(Self::word_segment_kind(kind), text, text_span),
397        )
398    }
399
400    fn owned_word(kind: TokenKind, text: String) -> Self {
401        Self::with_word_payload(kind, LexedWord::owned(Self::word_segment_kind(kind), text))
402    }
403
404    fn comment() -> Self {
405        Self {
406            kind: TokenKind::Comment,
407            span: Span::new(),
408            flags: TokenFlags::empty(),
409            payload: TokenPayload::None,
410        }
411    }
412
413    fn fd(kind: TokenKind, fd: i32) -> Self {
414        Self {
415            kind,
416            span: Span::new(),
417            flags: TokenFlags::empty(),
418            payload: TokenPayload::Fd(fd),
419        }
420    }
421
422    fn fd_pair(kind: TokenKind, src_fd: i32, dst_fd: i32) -> Self {
423        Self {
424            kind,
425            span: Span::new(),
426            flags: TokenFlags::empty(),
427            payload: TokenPayload::FdPair(src_fd, dst_fd),
428        }
429    }
430
431    fn error(error: LexerError) -> Self {
432        Self {
433            kind: TokenKind::Error,
434            span: Span::at(error.position),
435            flags: TokenFlags::empty(),
436            payload: TokenPayload::Error(error.kind),
437        }
438    }
439
440    pub(crate) fn with_span(mut self, span: Span) -> Self {
441        // The error constructor records the failing construct's start; the
442        // outer token wrapper supplies the end reached while lexing it.
443        self.span = if self.kind == TokenKind::Error {
444            Span::from_positions(self.span.start, span.end)
445        } else {
446            span
447        };
448        self
449    }
450
451    pub(crate) fn rebased(mut self, base: Position) -> Self {
452        self.span = self.span.rebased(base);
453        self.payload = match self.payload {
454            TokenPayload::Word(word) => TokenPayload::Word(word.rebased(base)),
455            payload => payload,
456        };
457        self
458    }
459
460    pub(crate) fn with_synthetic_flag(mut self) -> Self {
461        self.flags = self.flags.with_synthetic();
462        self
463    }
464
465    pub(crate) fn into_owned<'b>(self) -> LexedToken<'b> {
466        let payload = match self.payload {
467            TokenPayload::None => TokenPayload::None,
468            TokenPayload::Word(word) => TokenPayload::Word(word.into_owned()),
469            TokenPayload::Fd(fd) => TokenPayload::Fd(fd),
470            TokenPayload::FdPair(src_fd, dst_fd) => TokenPayload::FdPair(src_fd, dst_fd),
471            TokenPayload::Error(kind) => TokenPayload::Error(kind),
472        };
473
474        LexedToken {
475            kind: self.kind,
476            span: self.span,
477            flags: self.flags,
478            payload,
479        }
480    }
481
482    pub(crate) fn into_shared<'b>(self, source: &Arc<str>) -> LexedToken<'b> {
483        let payload = match self.payload {
484            TokenPayload::None => TokenPayload::None,
485            TokenPayload::Word(word) => TokenPayload::Word(word.into_shared(source)),
486            TokenPayload::Fd(fd) => TokenPayload::Fd(fd),
487            TokenPayload::FdPair(src_fd, dst_fd) => TokenPayload::FdPair(src_fd, dst_fd),
488            TokenPayload::Error(kind) => TokenPayload::Error(kind),
489        };
490
491        LexedToken {
492            kind: self.kind,
493            span: self.span,
494            flags: self.flags,
495            payload,
496        }
497    }
498
499    /// Borrow the token text when it is a single-segment word token.
500    pub(crate) fn word_text(&self) -> Option<&str> {
501        self.kind
502            .is_word_like()
503            .then_some(())
504            .and_then(|_| match &self.payload {
505                TokenPayload::Word(word) => word.text(),
506                _ => None,
507            })
508    }
509
510    /// Return an owned string containing the token's word text.
511    pub(crate) fn word_string(&self) -> Option<String> {
512        self.kind
513            .is_word_like()
514            .then_some(())
515            .and_then(|_| match &self.payload {
516                TokenPayload::Word(word) => Some(word.joined_text()),
517                _ => None,
518            })
519    }
520
521    /// Borrow the structured word payload for word-like tokens.
522    pub(crate) fn word(&self) -> Option<&LexedWord<'a>> {
523        match &self.payload {
524            TokenPayload::Word(word) => Some(word),
525            _ => None,
526        }
527    }
528
529    /// Borrow the original source slice when the token is source-backed and uncooked.
530    pub(crate) fn source_slice<'b>(&self, source: &'b str) -> Option<&'b str> {
531        if !self.kind.is_word_like() || self.flags.has_cooked_text() || self.flags.is_synthetic() {
532            return None;
533        }
534
535        (self.span.start.offset <= self.span.end.offset && self.span.end.offset <= source.len())
536            .then(|| &source[self.span.start.offset..self.span.end.offset])
537    }
538
539    /// Return the file-descriptor payload for redirection tokens that carry one.
540    pub(crate) fn fd_value(&self) -> Option<i32> {
541        match self.payload {
542            TokenPayload::Fd(fd) => Some(fd),
543            _ => None,
544        }
545    }
546
547    /// Return the `(source_fd, target_fd)` payload for descriptor-pair redirections.
548    pub(crate) fn fd_pair_value(&self) -> Option<(i32, i32)> {
549        match self.payload {
550            TokenPayload::FdPair(src_fd, dst_fd) => Some((src_fd, dst_fd)),
551            _ => None,
552        }
553    }
554
555    /// Return the lexer error payload when this token represents `TokenKind::Error`.
556    pub(crate) fn error_kind(&self) -> Option<LexerErrorKind> {
557        match self.payload {
558            TokenPayload::Error(kind) => Some(kind),
559            _ => None,
560        }
561    }
562}
563
564/// Result of reading a heredoc body from the source.
565#[derive(Debug, Clone, PartialEq)]
566pub(crate) struct HeredocRead {
567    /// Decoded heredoc content.
568    pub content: String,
569    /// Source span covering the heredoc body content.
570    pub content_span: Span,
571}
572
573/// Maximum nesting depth for command substitution in the lexer.
574/// Prevents stack overflow from deeply nested $() patterns.
575const DEFAULT_MAX_SUBST_DEPTH: usize = 50;
576const MAX_PARAMETER_EXPANSION_SCAN_DEPTH: usize = 4;
577
578#[derive(Clone, Debug)]
579struct Cursor<'a> {
580    rest: &'a str,
581}
582
583impl<'a> Cursor<'a> {
584    fn new(source: &'a str) -> Self {
585        Self { rest: source }
586    }
587
588    fn first(&self) -> Option<char> {
589        self.rest.chars().next()
590    }
591
592    fn second(&self) -> Option<char> {
593        let mut chars = self.rest.chars();
594        chars.next()?;
595        chars.next()
596    }
597
598    fn third(&self) -> Option<char> {
599        let mut chars = self.rest.chars();
600        chars.next()?;
601        chars.next()?;
602        chars.next()
603    }
604
605    fn bump(&mut self) -> Option<char> {
606        let ch = self.first()?;
607        self.rest = &self.rest[ch.len_utf8()..];
608        Some(ch)
609    }
610
611    fn eat_while(&mut self, mut predicate: impl FnMut(char) -> bool) -> &'a str {
612        let start = self.rest;
613        let mut end = 0;
614
615        for ch in start.chars() {
616            if !predicate(ch) {
617                break;
618            }
619            end += ch.len_utf8();
620        }
621
622        self.rest = &start[end..];
623        &start[..end]
624    }
625
626    fn rest(&self) -> &'a str {
627        self.rest
628    }
629
630    fn skip_bytes(&mut self, count: usize) {
631        self.rest = &self.rest[count..];
632    }
633
634    fn find_byte(&self, byte: u8) -> Option<usize> {
635        memchr(byte, self.rest.as_bytes())
636    }
637}
638
639#[derive(Clone, Debug)]
640struct PositionMap<'a> {
641    source: &'a str,
642    line_starts: Arc<[usize]>,
643    cached: Position,
644}
645
646#[cfg(feature = "benchmarking")]
647#[derive(Clone, Copy, Debug, Default)]
648pub(crate) struct LexerBenchmarkCounters {
649    pub(crate) current_position_calls: u64,
650}
651
652impl<'a> PositionMap<'a> {
653    fn new(source: &'a str) -> Self {
654        let mut line_starts =
655            Vec::with_capacity(source.bytes().filter(|byte| *byte == b'\n').count() + 1);
656        line_starts.push(0);
657        line_starts.extend(
658            source
659                .bytes()
660                .enumerate()
661                .filter_map(|(index, byte)| (byte == b'\n').then_some(index + 1)),
662        );
663
664        Self {
665            source,
666            line_starts: line_starts.into(),
667            cached: Position::new(),
668        }
669    }
670
671    fn position(&mut self, offset: usize) -> Position {
672        if offset == self.cached.offset {
673            return self.cached;
674        }
675
676        let position = if offset > self.cached.offset && offset <= self.source.len() {
677            Self::advance_from(self.cached, &self.source[self.cached.offset..offset])
678        } else {
679            self.position_uncached(offset)
680        };
681        self.cached = position;
682        position
683    }
684
685    fn position_uncached(&self, offset: usize) -> Position {
686        let offset = offset.min(self.source.len());
687        let line_index = self
688            .line_starts
689            .partition_point(|start| *start <= offset)
690            .saturating_sub(1);
691        let line_start = self.line_starts[line_index];
692        let line_text = &self.source[line_start..offset];
693        let column = if line_text.is_ascii() {
694            line_text.len() + 1
695        } else {
696            line_text.chars().count() + 1
697        };
698
699        Position {
700            line: line_index + 1,
701            column,
702            offset,
703        }
704    }
705
706    fn advance_from(mut position: Position, text: &str) -> Position {
707        position.offset += text.len();
708        let newline_count = memchr_iter(b'\n', text.as_bytes()).count();
709        if newline_count == 0 {
710            position.column += if text.is_ascii() {
711                text.len()
712            } else {
713                text.chars().count()
714            };
715            return position;
716        }
717
718        position.line += newline_count;
719        let tail_start = memrchr(b'\n', text.as_bytes())
720            .map(|index| index + 1)
721            .unwrap_or_default();
722        let tail = &text[tail_start..];
723        position.column = if tail.is_ascii() {
724            tail.len() + 1
725        } else {
726            tail.chars().count() + 1
727        };
728        position
729    }
730}
731
732/// Source-backed lexer for shell scripts.
733///
734/// The public lexer surface is intended for lower-level tooling and
735/// benchmarks. It tokenizes using the default bash profile; use the parser
736/// constructors when dialect or zsh option state matters.
737#[derive(Clone)]
738pub struct Lexer<'a> {
739    input: &'a str,
740    /// Current byte offset in the input/reinjected stream.
741    offset: usize,
742    cursor: Cursor<'a>,
743    position_map: PositionMap<'a>,
744    /// Buffer for re-injected characters (e.g., rest-of-line after heredoc delimiter).
745    /// Consumed before `cursor`.
746    reinject_buf: VecDeque<char>,
747    /// Cursor byte offset to restore once a heredoc replay buffer is exhausted.
748    reinject_resume_offset: Option<usize>,
749    /// Maximum allowed nesting depth for command substitution
750    max_subst_depth: usize,
751    initial_zsh_options: Option<ZshOptionState>,
752    zsh_timeline: Option<Arc<ZshOptionTimeline>>,
753    zsh_timeline_index: usize,
754    #[cfg(feature = "benchmarking")]
755    benchmark_counters: Option<LexerBenchmarkCounters>,
756}
757
758mod cursor;
759mod heredoc;
760mod quotes;
761mod substitutions;
762mod tokens;
763mod word;
764
765pub(super) use heredoc::heredoc_line_matches_delimiter;
766pub(super) use substitutions::{
767    line_has_unclosed_double_paren, scan_command_substitution_body_len,
768    scan_command_substitution_body_len_inner,
769};
770#[cfg(test)]
771mod tests;
shuck_parser/parser/lexer/mod.rs

shuck_parser/parser/lexer/
mod.rs
