squawk_parser/
output.rs

1// via https://github.com/rust-lang/rust-analyzer/blob/master/crates/parser/src/output.rs
2//
3// Permission is hereby granted, free of charge, to any
4// person obtaining a copy of this software and associated
5// documentation files (the "Software"), to deal in the
6// Software without restriction, including without
7// limitation the rights to use, copy, modify, merge,
8// publish, distribute, sublicense, and/or sell copies of
9// the Software, and to permit persons to whom the Software
10// is furnished to do so, subject to the following
11// conditions:
12//
13// The above copyright notice and this permission notice
14// shall be included in all copies or substantial portions
15// of the Software.
16//
17// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF
18// ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED
19// TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A
20// PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT
21// SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY
22// CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
23// OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR
24// IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
25// DEALINGS IN THE SOFTWARE.
26
27//! See [`Output`]
28
29use crate::SyntaxKind;
30
31/// Output of the parser -- a DFS traversal of a concrete syntax tree.
32///
33/// Use the [`Output::iter`] method to iterate over traversal steps and consume
34/// a syntax tree.
35///
36/// In a sense, this is just a sequence of [`SyntaxKind`]-colored parenthesis
37/// interspersed into the original [`crate::Input`]. The output is fundamentally
38/// coordinated with the input and `n_input_tokens` refers to the number of
39/// times [`crate::Input::push`] was called.
40#[derive(Default)]
41pub struct Output {
42    /// 32-bit encoding of events. If LSB is zero, then that's an index into the
43    /// error vector. Otherwise, it's one of the thee other variants, with data encoded as
44    ///
45    ///     |16 bit kind|8 bit n_input_tokens|4 bit tag|4 bit leftover|
46    ///
47    event: Vec<u32>,
48    error: Vec<String>,
49}
50
51#[derive(Debug)]
52pub(crate) enum Step<'a> {
53    Token {
54        kind: SyntaxKind,
55        n_input_tokens: u8,
56    },
57    Enter {
58        kind: SyntaxKind,
59    },
60    Exit,
61    Error {
62        msg: &'a str,
63    },
64}
65
66impl Output {
67    const EVENT_MASK: u32 = 0b1;
68    const TAG_MASK: u32 = 0x0000_00F0;
69    const N_INPUT_TOKEN_MASK: u32 = 0x0000_FF00;
70    const KIND_MASK: u32 = 0xFFFF_0000;
71
72    const ERROR_SHIFT: u32 = Self::EVENT_MASK.trailing_ones();
73    const TAG_SHIFT: u32 = Self::TAG_MASK.trailing_zeros();
74    const N_INPUT_TOKEN_SHIFT: u32 = Self::N_INPUT_TOKEN_MASK.trailing_zeros();
75    const KIND_SHIFT: u32 = Self::KIND_MASK.trailing_zeros();
76
77    const TOKEN_EVENT: u8 = 0;
78    const ENTER_EVENT: u8 = 1;
79    const EXIT_EVENT: u8 = 2;
80
81    pub(crate) fn iter(&self) -> impl Iterator<Item = Step<'_>> {
82        self.event.iter().map(|&event| {
83            if event & Self::EVENT_MASK == 0 {
84                return Step::Error {
85                    msg: self.error[(event as usize) >> Self::ERROR_SHIFT].as_str(),
86                };
87            }
88            let tag = ((event & Self::TAG_MASK) >> Self::TAG_SHIFT) as u8;
89            match tag {
90                Self::TOKEN_EVENT => {
91                    let kind: SyntaxKind =
92                        (((event & Self::KIND_MASK) >> Self::KIND_SHIFT) as u16).into();
93                    let n_input_tokens =
94                        ((event & Self::N_INPUT_TOKEN_MASK) >> Self::N_INPUT_TOKEN_SHIFT) as u8;
95                    Step::Token {
96                        kind,
97                        n_input_tokens,
98                    }
99                }
100                Self::ENTER_EVENT => {
101                    let kind: SyntaxKind =
102                        (((event & Self::KIND_MASK) >> Self::KIND_SHIFT) as u16).into();
103                    Step::Enter { kind }
104                }
105                Self::EXIT_EVENT => Step::Exit,
106                _ => unreachable!(),
107            }
108        })
109    }
110
111    pub(crate) fn token(&mut self, kind: SyntaxKind, n_tokens: u8) {
112        let e = ((kind as u16 as u32) << Self::KIND_SHIFT)
113            | ((n_tokens as u32) << Self::N_INPUT_TOKEN_SHIFT)
114            | Self::EVENT_MASK;
115        self.event.push(e)
116    }
117
118    pub(crate) fn enter_node(&mut self, kind: SyntaxKind) {
119        let e = ((kind as u16 as u32) << Self::KIND_SHIFT)
120            | ((Self::ENTER_EVENT as u32) << Self::TAG_SHIFT)
121            | Self::EVENT_MASK;
122        self.event.push(e)
123    }
124
125    pub(crate) fn leave_node(&mut self) {
126        let e = (Self::EXIT_EVENT as u32) << Self::TAG_SHIFT | Self::EVENT_MASK;
127        self.event.push(e)
128    }
129
130    pub(crate) fn error(&mut self, error: String) {
131        let idx = self.error.len();
132        self.error.push(error);
133        let e = (idx as u32) << Self::ERROR_SHIFT;
134        self.event.push(e);
135    }
136}
squawk_parser/output.rs

squawk_parser/
output.rs
