gll/
runtime.rs

1pub use grammar::ParseNodeShape;
2
3use indexing::container_traits::{Contiguous, Trustworthy};
4use indexing::{self, scope, Container};
5use std::cmp::{Ordering, Reverse};
6use std::collections::{BTreeSet, BinaryHeap, HashMap, VecDeque};
7use std::fmt;
8use std::hash::{Hash, Hasher};
9use std::io::{self, Write};
10use std::ops::{self, Deref, RangeInclusive};
11use std::str;
12
13#[derive(Copy, Clone, PartialEq, Eq, Debug)]
14pub struct Range<'i>(pub indexing::Range<'i>);
15
16impl<'i> Deref for Range<'i> {
17    type Target = indexing::Range<'i>;
18    fn deref(&self) -> &Self::Target {
19        &self.0
20    }
21}
22
23impl<'i> PartialOrd for Range<'i> {
24    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
25        (self.start(), self.end()).partial_cmp(&(other.start(), other.end()))
26    }
27}
28
29impl<'i> Ord for Range<'i> {
30    fn cmp(&self, other: &Self) -> Ordering {
31        (self.start(), self.end()).cmp(&(other.start(), other.end()))
32    }
33}
34
35impl<'i> Hash for Range<'i> {
36    fn hash<H: Hasher>(&self, state: &mut H) {
37        (self.start(), self.end()).hash(state);
38    }
39}
40
41impl<'i> Range<'i> {
42    pub fn subtract_suffix(self, other: Self) -> Self {
43        assert_eq!(self.end(), other.end());
44        Range(self.split_at(other.start() - self.start()).0)
45    }
46}
47
48#[derive(Copy, Clone, Default, PartialEq, Eq, PartialOrd, Ord)]
49pub struct LineColumn {
50    pub line: usize,
51    pub column: usize,
52}
53
54impl fmt::Debug for LineColumn {
55    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
56        write!(f, "{}:{}", 1 + self.line, 1 + self.column)
57    }
58}
59
60impl LineColumn {
61    fn count(prefix: &str) -> Self {
62        let (line, column) = prefix
63            .split("\n")
64            .enumerate()
65            .last()
66            .map_or((0, 0), |(i, s)| (i, s.chars().count()));
67        LineColumn { line, column }
68    }
69}
70
71#[derive(Copy, Clone, PartialEq, Eq, PartialOrd, Ord)]
72pub struct LineColumnRange {
73    pub start: LineColumn,
74    pub end: LineColumn,
75}
76
77impl fmt::Debug for LineColumnRange {
78    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
79        write!(f, "{:?}-{:?}", self.start, self.end)
80    }
81}
82
83pub struct Str(str);
84
85impl<'a> From<&'a str> for &'a Str {
86    fn from(s: &'a str) -> Self {
87        unsafe { &*(s as *const str as *const Str) }
88    }
89}
90
91unsafe impl Trustworthy for Str {
92    type Item = u8;
93    fn base_len(&self) -> usize {
94        self.0.len()
95    }
96}
97
98unsafe impl Contiguous for Str {
99    fn begin(&self) -> *const Self::Item {
100        self.0.as_ptr()
101    }
102    fn end(&self) -> *const Self::Item {
103        unsafe { self.begin().offset(self.0.len() as isize) }
104    }
105    fn as_slice(&self) -> &[Self::Item] {
106        self.0.as_bytes()
107    }
108}
109
110pub trait Input: Sized {
111    type Container: Trustworthy;
112    type Slice: ?Sized;
113    type SourceInfo: fmt::Debug;
114    fn to_container(self) -> Self::Container;
115    fn slice<'a, 'i>(
116        input: &'a Container<'i, Self::Container>,
117        range: Range<'i>,
118    ) -> &'a Self::Slice;
119    fn source_info<'i>(
120        input: &Container<'i, Self::Container>,
121        range: Range<'i>,
122    ) -> Self::SourceInfo;
123}
124
125impl<'a, T> Input for &'a [T] {
126    type Container = Self;
127    type Slice = [T];
128    type SourceInfo = ops::Range<usize>;
129    fn to_container(self) -> Self::Container {
130        self
131    }
132    fn slice<'b, 'i>(
133        input: &'b Container<'i, Self::Container>,
134        range: Range<'i>,
135    ) -> &'b Self::Slice {
136        &input[range.0]
137    }
138    fn source_info<'i>(_: &Container<'i, Self::Container>, range: Range<'i>) -> Self::SourceInfo {
139        range.as_range()
140    }
141}
142
143impl<'a> Input for &'a str {
144    type Container = &'a Str;
145    type Slice = str;
146    type SourceInfo = LineColumnRange;
147    fn to_container(self) -> Self::Container {
148        self.into()
149    }
150    fn slice<'b, 'i>(
151        input: &'b Container<'i, Self::Container>,
152        range: Range<'i>,
153    ) -> &'b Self::Slice {
154        unsafe { str::from_utf8_unchecked(&input[range.0]) }
155    }
156    fn source_info<'i>(
157        input: &Container<'i, Self::Container>,
158        range: Range<'i>,
159    ) -> Self::SourceInfo {
160        let prefix_range = Range(input.range().split_at(range.start()).0);
161        let start = LineColumn::count(Self::slice(input, prefix_range));
162        // HACK(eddyb) add up `LineColumn`s to avoid counting twice.
163        // Ideally we'd cache around a line map, like rustc's `SourceMap`.
164        let mut end = LineColumn::count(Self::slice(input, range));
165        end.line += start.line;
166        if end.line == start.line {
167            end.column += start.column;
168        }
169        LineColumnRange { start, end }
170    }
171}
172
173pub trait InputMatch<Pat> {
174    fn match_left(&self, pat: Pat) -> Option<usize>;
175    fn match_right(&self, pat: Pat) -> Option<usize>;
176}
177
178impl<'a, T: PartialEq> InputMatch<&'a [T]> for [T] {
179    fn match_left(&self, pat: &[T]) -> Option<usize> {
180        if self.starts_with(pat) {
181            Some(pat.len())
182        } else {
183            None
184        }
185    }
186    fn match_right(&self, pat: &[T]) -> Option<usize> {
187        if self.ends_with(pat) {
188            Some(pat.len())
189        } else {
190            None
191        }
192    }
193}
194
195impl<T: PartialOrd> InputMatch<RangeInclusive<T>> for [T] {
196    fn match_left(&self, pat: RangeInclusive<T>) -> Option<usize> {
197        let x = self.first()?;
198        if pat.start() <= x && x <= pat.end() {
199            Some(1)
200        } else {
201            None
202        }
203    }
204    fn match_right(&self, pat: RangeInclusive<T>) -> Option<usize> {
205        let x = self.last()?;
206        if pat.start() <= x && x <= pat.end() {
207            Some(1)
208        } else {
209            None
210        }
211    }
212}
213
214impl<'a> InputMatch<&'a str> for str {
215    fn match_left(&self, pat: &str) -> Option<usize> {
216        if self.starts_with(pat) {
217            Some(pat.len())
218        } else {
219            None
220        }
221    }
222    fn match_right(&self, pat: &str) -> Option<usize> {
223        if self.ends_with(pat) {
224            Some(pat.len())
225        } else {
226            None
227        }
228    }
229}
230
231impl InputMatch<RangeInclusive<char>> for str {
232    fn match_left(&self, pat: RangeInclusive<char>) -> Option<usize> {
233        let c = self.chars().next()?;
234        if *pat.start() <= c && c <= *pat.end() {
235            Some(c.len_utf8())
236        } else {
237            None
238        }
239    }
240    fn match_right(&self, pat: RangeInclusive<char>) -> Option<usize> {
241        let c = self.chars().rev().next()?;
242        if *pat.start() <= c && c <= *pat.end() {
243            Some(c.len_utf8())
244        } else {
245            None
246        }
247    }
248}
249
250pub struct Parser<'i, P: ParseNodeKind, C: CodeLabel, I: Input> {
251    input: Container<'i, I::Container>,
252    pub threads: Threads<'i, C>,
253    pub gss: GraphStack<'i, C>,
254    pub memoizer: Memoizer<'i, C>,
255    pub sppf: ParseForest<'i, P>,
256}
257
258impl<'i, P: ParseNodeKind, C: CodeLabel, I: Input> Parser<'i, P, C, I> {
259    pub fn with<R>(input: I, f: impl for<'i2> FnOnce(Parser<'i2, P, C, I>, Range<'i2>) -> R) -> R {
260        scope(input.to_container(), |input| {
261            let range = input.range();
262            f(
263                Parser {
264                    input,
265                    threads: Threads {
266                        queue: BinaryHeap::new(),
267                        seen: BTreeSet::new(),
268                    },
269                    gss: GraphStack {
270                        returns: HashMap::new(),
271                    },
272                    memoizer: Memoizer {
273                        lengths: HashMap::new(),
274                    },
275                    sppf: ParseForest {
276                        possibilities: HashMap::new(),
277                    },
278                },
279                Range(range),
280            )
281        })
282    }
283    pub fn input(&self, range: Range<'i>) -> &I::Slice {
284        I::slice(&self.input, range)
285    }
286    pub fn source_info(&self, range: Range<'i>) -> I::SourceInfo {
287        I::source_info(&self.input, range)
288    }
289    pub fn input_consume_left<Pat>(&self, range: Range<'i>, pat: Pat) -> Option<Range<'i>>
290    where
291        I::Slice: InputMatch<Pat>,
292    {
293        self.input(range)
294            .match_left(pat)
295            .map(|n| Range(range.split_at(n).1))
296    }
297    pub fn input_consume_right<Pat>(&self, range: Range<'i>, pat: Pat) -> Option<Range<'i>>
298    where
299        I::Slice: InputMatch<Pat>,
300    {
301        self.input(range)
302            .match_right(pat)
303            .map(|n| Range(range.split_at(range.len() - n).0))
304    }
305    pub fn call(&mut self, call: Call<'i, C>, next: Continuation<'i, C>) {
306        let returns = self.gss.returns.entry(call).or_default();
307        if returns.insert(next) {
308            if returns.len() > 1 {
309                if let Some(lengths) = self.memoizer.lengths.get(&call) {
310                    for &len in lengths {
311                        self.threads.spawn(next, Range(call.range.split_at(len).1));
312                    }
313                }
314            } else {
315                self.threads.spawn(
316                    Continuation {
317                        code: call.callee,
318                        fn_input: call.range,
319                        state: 0,
320                    },
321                    call.range,
322                );
323            }
324        }
325    }
326    pub fn ret(&mut self, from: Continuation<'i, C>, remaining: Range<'i>) {
327        let call = Call {
328            callee: from.code.enclosing_fn(),
329            range: from.fn_input,
330        };
331        if self
332            .memoizer
333            .lengths
334            .entry(call)
335            .or_default()
336            .insert(call.range.subtract_suffix(remaining).len())
337        {
338            if let Some(returns) = self.gss.returns.get(&call) {
339                for &next in returns {
340                    self.threads.spawn(next, remaining);
341                }
342            }
343        }
344    }
345}
346
347pub struct Threads<'i, C: CodeLabel> {
348    queue: BinaryHeap<Call<'i, Continuation<'i, C>>>,
349    seen: BTreeSet<Call<'i, Continuation<'i, C>>>,
350}
351
352impl<'i, C: CodeLabel> Threads<'i, C> {
353    pub fn spawn(&mut self, next: Continuation<'i, C>, range: Range<'i>) {
354        let t = Call {
355            callee: next,
356            range,
357        };
358        if self.seen.insert(t) {
359            self.queue.push(t);
360        }
361    }
362    pub fn steal(&mut self) -> Option<Call<'i, Continuation<'i, C>>> {
363        if let Some(t) = self.queue.pop() {
364            loop {
365                let old = self.seen.iter().rev().next().cloned();
366                if let Some(old) = old {
367                    // TODO also check end point for proper "t.range includes old.range".
368                    if !t.range.contains(old.range.start()).is_some() {
369                        self.seen.remove(&old);
370                        continue;
371                    }
372                }
373                break;
374            }
375            Some(t)
376        } else {
377            self.seen.clear();
378            None
379        }
380    }
381}
382
383#[derive(Copy, Clone, PartialEq, Eq, PartialOrd, Ord)]
384pub struct Continuation<'i, C: CodeLabel> {
385    pub code: C,
386    pub fn_input: Range<'i>,
387    pub state: usize,
388}
389
390#[derive(Copy, Clone, Debug, PartialEq, Eq, Hash)]
391pub struct Call<'i, C> {
392    pub callee: C,
393    pub range: Range<'i>,
394}
395
396impl<'i, C: fmt::Display> fmt::Display for Call<'i, C> {
397    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
398        write!(
399            f,
400            "{}({}..{})",
401            self.callee,
402            self.range.start(),
403            self.range.end()
404        )
405    }
406}
407
408impl<'i, C: PartialOrd> PartialOrd for Call<'i, C> {
409    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
410        (Reverse(self.range), &self.callee).partial_cmp(&(Reverse(other.range), &other.callee))
411    }
412}
413
414impl<'i, C: Ord> Ord for Call<'i, C> {
415    fn cmp(&self, other: &Self) -> Ordering {
416        (Reverse(self.range), &self.callee).cmp(&(Reverse(other.range), &other.callee))
417    }
418}
419
420pub struct GraphStack<'i, C: CodeLabel> {
421    returns: HashMap<Call<'i, C>, BTreeSet<Continuation<'i, C>>>,
422}
423
424impl<'i, C: CodeLabel> GraphStack<'i, C> {
425    pub fn dump_graphviz(&self, out: &mut Write) -> io::Result<()> {
426        writeln!(out, "digraph gss {{")?;
427        writeln!(out, "    graph [rankdir=RL]")?;
428        for (call, returns) in &self.returns {
429            for next in returns {
430                writeln!(
431                    out,
432                    r#"    "{:?}" -> "{:?}" [label="{:?}"]"#,
433                    call,
434                    Call {
435                        callee: next.code.enclosing_fn(),
436                        range: next.fn_input
437                    },
438                    next.code
439                )?;
440            }
441        }
442        writeln!(out, "}}")
443    }
444}
445
446pub struct Memoizer<'i, C: CodeLabel> {
447    lengths: HashMap<Call<'i, C>, BTreeSet<usize>>,
448}
449
450impl<'i, C: CodeLabel> Memoizer<'i, C> {
451    pub fn results<'a>(
452        &'a self,
453        call: Call<'i, C>,
454    ) -> impl DoubleEndedIterator<Item = Range<'i>> + 'a {
455        self.lengths
456            .get(&call)
457            .into_iter()
458            .flat_map(move |lengths| {
459                lengths
460                    .iter()
461                    .map(move |&len| Range(call.range.split_at(len).0))
462            })
463    }
464    pub fn longest_result(&self, call: Call<'i, C>) -> Option<Range<'i>> {
465        self.results(call).rev().next()
466    }
467}
468
469pub struct ParseForest<'i, P: ParseNodeKind> {
470    pub possibilities: HashMap<ParseNode<'i, P>, BTreeSet<usize>>,
471}
472
473#[derive(Debug)]
474pub struct MoreThanOne;
475
476impl<'i, P: ParseNodeKind> ParseForest<'i, P> {
477    pub fn add(&mut self, kind: P, range: Range<'i>, possibility: usize) {
478        self.possibilities
479            .entry(ParseNode { kind, range })
480            .or_default()
481            .insert(possibility);
482    }
483
484    pub fn one_choice(&self, node: ParseNode<'i, P>) -> Result<ParseNode<'i, P>, MoreThanOne> {
485        match node.kind.shape() {
486            ParseNodeShape::Choice => {
487                let choices = &self.possibilities[&node];
488                if choices.len() > 1 {
489                    return Err(MoreThanOne);
490                }
491                let &choice = choices.iter().next().unwrap();
492                Ok(ParseNode {
493                    kind: P::from_usize(choice),
494                    range: node.range,
495                })
496            }
497            shape => unreachable!("one_choice({}): non-choice shape {}", node, shape),
498        }
499    }
500
501    pub fn all_choices<'a>(
502        &'a self,
503        node: ParseNode<'i, P>,
504    ) -> impl Iterator<Item = ParseNode<'i, P>> + Clone + 'a {
505        match node.kind.shape() {
506            ParseNodeShape::Choice => self
507                .possibilities
508                .get(&node)
509                .into_iter()
510                .flatten()
511                .cloned()
512                .map(move |i| ParseNode {
513                    kind: P::from_usize(i),
514                    range: node.range,
515                }),
516            shape => unreachable!("all_choices({}): non-choice shape {}", node, shape),
517        }
518    }
519
520    pub fn one_split(
521        &self,
522        node: ParseNode<'i, P>,
523    ) -> Result<(ParseNode<'i, P>, ParseNode<'i, P>), MoreThanOne> {
524        match node.kind.shape() {
525            ParseNodeShape::Split(left_kind, right_kind) => {
526                let splits = &self.possibilities[&node];
527                if splits.len() > 1 {
528                    return Err(MoreThanOne);
529                }
530                let &split = splits.iter().next().unwrap();
531                let (left, right, _) = node.range.split_at(split);
532                Ok((
533                    ParseNode {
534                        kind: left_kind,
535                        range: Range(left),
536                    },
537                    ParseNode {
538                        kind: right_kind,
539                        range: Range(right),
540                    },
541                ))
542            }
543            shape => unreachable!("one_split({}): non-split shape {}", node, shape),
544        }
545    }
546
547    pub fn all_splits<'a>(
548        &'a self,
549        node: ParseNode<'i, P>,
550    ) -> impl Iterator<Item = (ParseNode<'i, P>, ParseNode<'i, P>)> + Clone + 'a {
551        match node.kind.shape() {
552            ParseNodeShape::Split(left_kind, right_kind) => self
553                .possibilities
554                .get(&node)
555                .into_iter()
556                .flatten()
557                .cloned()
558                .map(move |i| {
559                    let (left, right, _) = node.range.split_at(i);
560                    (
561                        ParseNode {
562                            kind: left_kind,
563                            range: Range(left),
564                        },
565                        ParseNode {
566                            kind: right_kind,
567                            range: Range(right),
568                        },
569                    )
570                }),
571            shape => unreachable!("all_splits({}): non-split shape {}", node, shape),
572        }
573    }
574
575    pub fn dump_graphviz(&self, out: &mut Write) -> io::Result<()> {
576        writeln!(out, "digraph sppf {{")?;
577        let mut queue: VecDeque<_> = self.possibilities.keys().cloned().collect();
578        let mut seen: BTreeSet<_> = queue.iter().cloned().collect();
579        let mut p = 0;
580        while let Some(source) = queue.pop_front() {
581            writeln!(out, "    {:?} [shape=box]", source.to_string())?;
582            let mut add_children = |children: &[(&str, ParseNode<'i, P>)]| -> io::Result<()> {
583                writeln!(out, r#"    p{} [label="" shape=point]"#, p)?;
584                writeln!(out, "    {:?} -> p{}:n", source.to_string(), p)?;
585                for &(port, child) in children {
586                    writeln!(
587                        out,
588                        "    p{}:{} -> {:?}:n [dir=none]",
589                        p,
590                        port,
591                        child.to_string()
592                    )?;
593                    if seen.insert(child) {
594                        queue.push_back(child);
595                    }
596                }
597                p += 1;
598                Ok(())
599            };
600            match source.kind.shape() {
601                ParseNodeShape::Opaque => {}
602
603                ParseNodeShape::Alias(_) => {
604                    add_children(&[("s", source.unpack_alias())])?;
605                }
606
607                ParseNodeShape::Opt(_) => {
608                    if let Some(child) = source.unpack_opt() {
609                        add_children(&[("s", child)])?;
610                    }
611                }
612
613                ParseNodeShape::Choice => {
614                    for child in self.all_choices(source) {
615                        add_children(&[("s", child)])?;
616                    }
617                }
618
619                ParseNodeShape::Split(..) => {
620                    for (left, right) in self.all_splits(source) {
621                        add_children(&[("sw", left), ("se", right)])?;
622                    }
623                }
624            }
625        }
626        writeln!(out, "}}")
627    }
628}
629
630#[derive(Copy, Clone, PartialEq, Eq, PartialOrd, Ord, Hash)]
631pub struct ParseNode<'i, P: ParseNodeKind> {
632    pub kind: P,
633    pub range: Range<'i>,
634}
635
636impl<'i, P: ParseNodeKind> ParseNode<'i, P> {
637    pub fn unpack_alias(self) -> Self {
638        match self.kind.shape() {
639            ParseNodeShape::Alias(inner) => ParseNode {
640                kind: inner,
641                range: self.range,
642            },
643            shape => unreachable!("unpack_alias({}): non-alias shape {}", self, shape),
644        }
645    }
646
647    pub fn unpack_opt(self) -> Option<Self> {
648        match self.kind.shape() {
649            ParseNodeShape::Opt(inner) => {
650                if self.range.is_empty() {
651                    None
652                } else {
653                    Some(ParseNode {
654                        kind: inner,
655                        range: self.range,
656                    })
657                }
658            }
659            shape => unreachable!("unpack_opt({}): non-opt shape {}", self, shape),
660        }
661    }
662}
663
664impl<'i, P: ParseNodeKind> fmt::Display for ParseNode<'i, P> {
665    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
666        write!(
667            f,
668            "{} @ {}..{}",
669            self.kind,
670            self.range.start(),
671            self.range.end()
672        )
673    }
674}
675
676impl<'i, P: ParseNodeKind> fmt::Debug for ParseNode<'i, P> {
677    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
678        write!(
679            f,
680            "{} @ {}..{}",
681            self.kind,
682            self.range.start(),
683            self.range.end()
684        )
685    }
686}
687
688pub trait ParseNodeKind: fmt::Display + Ord + Hash + Copy + 'static {
689    fn shape(self) -> ParseNodeShape<Self>;
690    fn from_usize(i: usize) -> Self;
691    fn to_usize(self) -> usize;
692}
693
694pub trait CodeLabel: fmt::Debug + Ord + Hash + Copy + 'static {
695    fn enclosing_fn(self) -> Self;
696}
697
698// FIXME(rust-lang/rust#54175) work around iterator adapter compile-time
699// blowup issues by using a makeshift "non-determinism arrow toolkit".
700pub mod nd {
701    use std::iter;
702    use std::marker::PhantomData;
703
704    pub trait Arrow: Copy {
705        type Input;
706        type Output;
707        type Iter: Iterator<Item = Self::Output> + Clone;
708        fn apply(&self, x: Self::Input) -> Self::Iter;
709
710        fn map<F: Fn(Self::Output) -> R, R>(self, f: F) -> Map<Self, F> {
711            Map(self, f)
712        }
713        fn then<B: Arrow<Input = Self::Output>>(self, b: B) -> Then<Self, B> {
714            Then(self, b)
715        }
716        fn pairs<B: Arrow>(self, b: B) -> Pairs<Self, B>
717        where
718            Self::Output: Copy,
719            B::Input: Copy,
720        {
721            Pairs(self, b)
722        }
723    }
724
725    macro_rules! derive_copy {
726        ($name:ident<$($param:ident $(: $bound:ident)*),*>) => {
727            impl<$($param $(: $bound)*),*> Copy for $name<$($param),*> {}
728            impl<$($param $(: $bound)*),*> Clone for $name<$($param),*> {
729                fn clone(&self) -> Self {
730                    *self
731                }
732            }
733        }
734    }
735
736    pub struct Id<T>(PhantomData<T>);
737    derive_copy!(Id<T>);
738    impl<T> Id<T> {
739        pub fn new() -> Self {
740            Id(PhantomData)
741        }
742    }
743    impl<T: Clone> Arrow for Id<T> {
744        type Input = T;
745        type Output = T;
746        type Iter = iter::Once<T>;
747        fn apply(&self, x: T) -> Self::Iter {
748            iter::once(x)
749        }
750    }
751
752    pub struct FromIter<T, F>(F, PhantomData<T>);
753    derive_copy!(FromIter<T, F: Copy>);
754    impl<T, F> FromIter<T, F> {
755        pub fn new(f: F) -> Self {
756            FromIter(f, PhantomData)
757        }
758    }
759    impl<T, F: Copy + Fn(T) -> I, I: Iterator + Clone> Arrow for FromIter<T, F> {
760        type Input = T;
761        type Output = I::Item;
762        type Iter = I;
763        fn apply(&self, x: T) -> I {
764            self.0(x)
765        }
766    }
767
768    pub struct FromIterK<K, T, F>(K, F, PhantomData<T>);
769    derive_copy!(FromIterK<K: Copy, T, F: Copy>);
770    impl<K, T, F> FromIterK<K, T, F> {
771        pub fn new(k: K, f: F) -> Self {
772            FromIterK(k, f, PhantomData)
773        }
774    }
775    impl<K: Copy, T, F: Copy + Fn(K, T) -> I, I: Iterator + Clone> Arrow for FromIterK<K, T, F> {
776        type Input = T;
777        type Output = I::Item;
778        type Iter = I;
779        fn apply(&self, x: T) -> I {
780            self.1(self.0, x)
781        }
782    }
783
784    #[derive(Copy, Clone)]
785    pub struct Map<A, F>(A, F);
786    impl<A: Arrow, F: Copy + Fn(A::Output) -> R, R> Arrow for Map<A, F> {
787        type Input = A::Input;
788        type Output = R;
789        type Iter = iter::Map<A::Iter, F>;
790        fn apply(&self, x: Self::Input) -> Self::Iter {
791            self.0.apply(x).map(self.1)
792        }
793    }
794
795    #[derive(Clone)]
796    pub struct ThenIter<A: Arrow, B: Arrow<Input = A::Output>> {
797        a_iter: A::Iter,
798        b_arrow: B,
799        b_iter: Option<B::Iter>,
800        // HACK(eddyb) this field is useless (never set to `Some`)
801        // (see `match self.b_iter_backwards` below for more details).
802        b_iter_backwards: Option<B::Iter>,
803    }
804    impl<A: Arrow, B: Arrow<Input = A::Output>> Iterator for ThenIter<A, B> {
805        type Item = B::Output;
806        fn next(&mut self) -> Option<Self::Item> {
807            loop {
808                if let Some(ref mut b_iter) = self.b_iter {
809                    if let x @ Some(_) = b_iter.next() {
810                        return x;
811                    }
812                }
813                match self.a_iter.next() {
814                    // HACK(eddyb) this never does anything, but without a *second*
815                    // call to `B::Iter::next`, LLVM spends more time optimizing.
816                    None => {
817                        return match self.b_iter_backwards {
818                            Some(ref mut b_iter) => b_iter.next(),
819                            None => None,
820                        }
821                    }
822                    Some(x) => self.b_iter = Some(self.b_arrow.apply(x)),
823                }
824            }
825        }
826    }
827
828    #[derive(Copy, Clone)]
829    pub struct Then<A, B>(A, B);
830    impl<A: Arrow, B: Arrow<Input = A::Output>> Arrow for Then<A, B> {
831        type Input = A::Input;
832        type Output = B::Output;
833        type Iter = ThenIter<A, B>;
834        fn apply(&self, x: Self::Input) -> Self::Iter {
835            ThenIter {
836                a_iter: self.0.apply(x),
837                b_arrow: self.1,
838                b_iter: None,
839                b_iter_backwards: None,
840            }
841        }
842    }
843
844    #[derive(Clone)]
845    pub struct PairsIter<A: Arrow, B: Arrow>
846    where
847        A::Output: Copy,
848        B::Input: Copy,
849    {
850        a_iter: A::Iter,
851        b_iter0: B::Iter,
852        a_output_b_iter: Option<(A::Output, B::Iter)>,
853    }
854    impl<A: Arrow, B: Arrow> Iterator for PairsIter<A, B>
855    where
856        A::Output: Copy,
857        B::Input: Copy,
858    {
859        type Item = (A::Output, B::Output);
860        fn next(&mut self) -> Option<Self::Item> {
861            loop {
862                if let Some((x, ref mut b_iter)) = self.a_output_b_iter {
863                    if let Some(y) = b_iter.next() {
864                        return Some((x, y));
865                    }
866                }
867                match self.a_iter.next() {
868                    None => return None,
869                    Some(x) => {
870                        self.a_output_b_iter = Some((x, self.b_iter0.clone()));
871                    }
872                }
873            }
874        }
875    }
876
877    #[derive(Copy, Clone)]
878    pub struct Pairs<A, B>(A, B);
879    impl<A: Arrow, B: Arrow> Arrow for Pairs<A, B>
880    where
881        A::Output: Copy,
882        B::Input: Copy,
883    {
884        type Input = (A::Input, B::Input);
885        type Output = (A::Output, B::Output);
886        type Iter = PairsIter<A, B>;
887        fn apply(&self, (x, y): Self::Input) -> Self::Iter {
888            PairsIter {
889                a_iter: self.0.apply(x),
890                b_iter0: self.1.apply(y),
891                a_output_b_iter: None,
892            }
893        }
894    }
895}
896
897// HACK(eddyb) work around `macro_rules` not being `use`-able.
898pub use crate::traverse;
899
900#[macro_export]
901macro_rules! traverse {
902    (typeof($leaf:ty) _) => { $leaf };
903    (typeof($leaf:ty) ?) => { Option<traverse!(typeof($leaf) _)> };
904    (typeof($leaf:ty) ($l_shape:tt, $r_shape:tt)) => { (traverse!(typeof($leaf) $l_shape), traverse!(typeof($leaf) $r_shape)) };
905    (typeof($leaf:ty) { $($i:tt $_i:ident: $kind:pat => $shape:tt,)* }) => { ($(traverse!(typeof($leaf) $shape),)*) };
906    (typeof($leaf:ty) [$shape:tt]) => { (traverse!(typeof($leaf) $shape),) };
907
908    (one($sppf:ident, $node:ident) _) => {
909        $node
910    };
911    (one($sppf:ident, $node:ident) ?) => {
912        Some($node)
913    };
914    (one($sppf:ident, $node:ident) ($l_shape:tt, $r_shape:tt)) => {
915        {
916            let (left, right) = $sppf.one_split($node)?;
917            (
918                traverse!(one($sppf, left) $l_shape),
919                traverse!(one($sppf, right) $r_shape),
920            )
921        }
922    };
923    (one($sppf:ident, $node:ident) { $($i:tt $_i:ident: $kind:pat => $shape:tt,)* }) => {
924        {
925            let node = $sppf.one_choice($node)?;
926            let mut r = <($(traverse!(typeof(_) $shape),)*)>::default();
927            match node.kind {
928                $($kind => r.$i = traverse!(one($sppf, node) $shape),)*
929                _ => unreachable!(),
930            }
931            r
932        }
933    };
934    (one($sppf:ident, $node:ident) [$shape:tt]) => {
935        {
936            let mut r = <(traverse!(typeof(_) $shape),)>::default();
937            if let Some(node) = $node.unpack_opt() {
938                r.0 = traverse!(one($sppf, node) $shape);
939            }
940            r
941        }
942    };
943
944    (all($sppf:ident) _) => {
945        $crate::runtime::nd::Id::new()
946    };
947    (all($sppf:ident) ?) => {
948        $crate::runtime::nd::Id::new().map(Some)
949    };
950    (all($sppf:ident) ($l_shape:tt, $r_shape:tt)) => {
951        $crate::runtime::nd::FromIterK::new($sppf, $crate::runtime::ParseForest::all_splits)
952            .then(traverse!(all($sppf) $l_shape).pairs(traverse!(all($sppf) $r_shape)))
953    };
954    (all($sppf:ident) { $($i:tt $_i:ident: $kind:pat => $shape:tt,)* }) => {
955        $crate::runtime::nd::FromIter::new(move |node| {
956            #[derive(Clone)]
957            enum Iter<$($_i),*> {
958                $($_i($_i)),*
959            }
960            impl<$($_i: Iterator),*> Iterator for Iter<$($_i),*>
961                where $($_i::Item: Default),*
962            {
963                type Item = ($($_i::Item),*);
964                fn next(&mut self) -> Option<Self::Item> {
965                    let mut r = Self::Item::default();
966                    match self {
967                        $(Iter::$_i(iter) => r.$i = iter.next()?),*
968                    }
969                    Some(r)
970                }
971            }
972            $sppf.all_choices(node).flat_map(move |node| {
973                match node.kind {
974                    $($kind => Iter::$_i(traverse!(all($sppf) $shape).apply(node)),)*
975                    _ => unreachable!(),
976                }
977            })
978        })
979    };
980    (all($sppf:ident) [$shape:tt]) => {
981        $crate::runtime::nd::FromIter::new(move |node| {
982            match $crate::runtime::ParseNode::unpack_opt(node) {
983                Some(node) => {
984                    Some(traverse!(all($sppf) $shape).apply(node).map(|x| (x,)))
985                        .into_iter().flatten().chain(None)
986                }
987                None => {
988                    None.into_iter().flatten().chain(Some(<_>::default()))
989                }
990            }
991        })
992    }
993}
gll/runtime.rs

gll/
runtime.rs
