chore: add vendor directory

1 files changed, 268 insertions, 0 deletions

diff --git a/vendor/logos-codegen/src/generator/mod.rs b/vendor/logos-codegen/src/generator/mod.rs
new file mode 100644
index 00000000..1b8bf8bf
--- /dev/null
+++ b/vendor/logos-codegen/src/generator/mod.rs
@@ -0,0 +1,268 @@
+use fnv::{FnvHashMap as Map, FnvHashSet as Set};
+use proc_macro2::TokenStream;
+use quote::{quote, ToTokens, TokenStreamExt};
+use syn::Ident;
+
+use crate::graph::{Graph, Meta, Node, NodeId, Range};
+use crate::leaf::Leaf;
+use crate::util::ToIdent;
+
+mod context;
+mod fork;
+mod leaf;
+mod rope;
+mod tables;
+
+use self::context::Context;
+use self::tables::TableStack;
+
+pub struct Generator<'a> {
+    /// Name of the type we are implementing the `Logos` trait for
+    name: &'a Ident,
+    /// Name of the type with any generics it might need
+    this: &'a TokenStream,
+    /// Id to the root node
+    root: NodeId,
+    /// Reference to the graph with all of the nodes
+    graph: &'a Graph<Leaf<'a>>,
+    /// Meta data collected for the nodes
+    meta: Meta,
+    /// Buffer with functions growing during generation
+    rendered: TokenStream,
+    /// Set of functions that have already been rendered
+    fns: Set<(NodeId, Context)>,
+    /// Function name identifiers
+    idents: Map<(NodeId, Context), Ident>,
+    /// Local function calls. Note: a call might change its context,
+    /// so we can't use `idents` for this purpose.
+    gotos: Map<(NodeId, Context), TokenStream>,
+    /// Identifiers for helper functions matching a byte to a given
+    /// set of ranges
+    tests: Map<Vec<Range>, Ident>,
+    /// Related to above, table stack manages tables that need to be
+    tables: TableStack,
+}
+
+impl<'a> Generator<'a> {
+    pub fn new(
+        name: &'a Ident,
+        this: &'a TokenStream,
+        root: NodeId,
+        graph: &'a Graph<Leaf>,
+    ) -> Self {
+        let rendered = Self::fast_loop_macro();
+        let meta = Meta::analyze(root, graph);
+
+        Generator {
+            name,
+            this,
+            root,
+            graph,
+            meta,
+            rendered,
+            fns: Set::default(),
+            idents: Map::default(),
+            gotos: Map::default(),
+            tests: Map::default(),
+            tables: TableStack::new(),
+        }
+    }
+
+    pub fn generate(mut self) -> TokenStream {
+        let root = self.goto(self.root, Context::default()).clone();
+        let rendered = &self.rendered;
+        let tables = &self.tables;
+
+        quote! {
+            #tables
+            #rendered
+            #root
+        }
+    }
+
+    fn generate_fn(&mut self, id: NodeId, ctx: Context) {
+        if self.fns.contains(&(id, ctx)) {
+            return;
+        }
+        self.fns.insert((id, ctx));
+
+        let body = match &self.graph[id] {
+            Node::Fork(fork) => self.generate_fork(id, fork, ctx),
+            Node::Rope(rope) => self.generate_rope(rope, ctx),
+            Node::Leaf(leaf) => self.generate_leaf(leaf, ctx),
+        };
+        let ident = self.generate_ident(id, ctx);
+        let out = quote! {
+            #[inline]
+            fn #ident<'s>(lex: &mut Lexer<'s>) {
+                #body
+            }
+        };
+
+        self.rendered.append_all(out);
+    }
+
+    fn goto(&mut self, id: NodeId, mut ctx: Context) -> &TokenStream {
+        let key = (id, ctx);
+
+        // Allow contains_key + insert because self.generate_ident borrows a mutable ref to self
+        // too.
+        #[allow(clippy::map_entry)]
+        if !self.gotos.contains_key(&key) {
+            let meta = &self.meta[id];
+            let enters_loop = !meta.loop_entry_from.is_empty();
+
+            let bump = if enters_loop || !ctx.can_backtrack() {
+                ctx.switch(self.graph[id].miss())
+            } else {
+                None
+            };
+
+            let bump = match (bump, enters_loop, meta.min_read) {
+                (Some(t), _, _) => Some(t),
+                (None, true, _) => ctx.bump(),
+                (None, false, 0) => ctx.bump(),
+                (None, false, _) => None,
+            };
+
+            if meta.min_read == 0 || ctx.remainder() < meta.min_read {
+                ctx.wipe();
+            }
+
+            let ident = self.generate_ident(id, ctx);
+            let mut call_site = quote!(#ident(lex));
+
+            if let Some(bump) = bump {
+                call_site = quote!({
+                    #bump
+                    #call_site
+                });
+            }
+            self.gotos.insert(key, call_site);
+            self.generate_fn(id, ctx);
+        }
+        &self.gotos[&key]
+    }
+
+    fn generate_ident(&mut self, id: NodeId, ctx: Context) -> &Ident {
+        self.idents.entry((id, ctx)).or_insert_with(|| {
+            let mut ident = format!("goto{}", id);
+
+            ctx.write_suffix(&mut ident);
+
+            ident.to_ident()
+        })
+    }
+
+    /// Returns an identifier to a function that matches a byte to any
+    /// of the provided ranges. This will generate either a simple
+    /// match expression, or use a lookup table internally.
+    fn generate_test(&mut self, ranges: Vec<Range>) -> &Ident {
+        if !self.tests.contains_key(&ranges) {
+            let idx = self.tests.len();
+            let ident = format!("pattern{}", idx).to_ident();
+
+            let lo = ranges.first().unwrap().start;
+            let hi = ranges.last().unwrap().end;
+
+            let body = match ranges.len() {
+                0..=2 => {
+                    quote! {
+                        match byte {
+                            #(#ranges)|* => true,
+                            _ => false,
+                        }
+                    }
+                }
+                _ if hi - lo < 64 => {
+                    let mut offset = hi.saturating_sub(63);
+
+                    while offset.count_ones() > 1 && lo - offset > 0 {
+                        offset += 1;
+                    }
+
+                    let mut table = 0u64;
+
+                    for byte in ranges.iter().flat_map(|range| *range) {
+                        if byte - offset >= 64 {
+                            panic!("{:#?} {} {} {}", ranges, hi, lo, offset);
+                        }
+                        table |= 1 << (byte - offset);
+                    }
+
+                    let search = match offset {
+                        0 => quote!(byte),
+                        _ => quote!(byte.wrapping_sub(#offset)),
+                    };
+
+                    quote! {
+                        const LUT: u64 = #table;
+
+                        match 1u64.checked_shl(#search as u32) {
+                            Some(shift) => LUT & shift != 0,
+                            None => false,
+                        }
+                    }
+                }
+                _ => {
+                    let mut view = self.tables.view();
+
+                    for byte in ranges.iter().flat_map(|range| *range) {
+                        view.flag(byte);
+                    }
+
+                    let mask = view.mask();
+                    let lut = view.ident();
+
+                    quote! {
+                        #lut[byte as usize] & #mask > 0
+                    }
+                }
+            };
+            self.rendered.append_all(quote! {
+                #[inline]
+                fn #ident(byte: u8) -> bool {
+                    #body
+                }
+            });
+            self.tests.insert(ranges.clone(), ident);
+        }
+        &self.tests[&ranges]
+    }
+}
+
+macro_rules! match_quote {
+    ($source:expr; $($byte:tt,)* ) => {match $source {
+        $( $byte => quote!($byte), )*
+        byte => quote!(#byte),
+    }}
+}
+
+fn byte_to_tokens(byte: u8) -> TokenStream {
+    match_quote! {
+        byte;
+        b'0', b'1', b'2', b'3', b'4', b'5', b'6', b'7', b'8', b'9',
+        b'a', b'b', b'c', b'd', b'e', b'f', b'g', b'h', b'i', b'j',
+        b'k', b'l', b'm', b'n', b'o', b'p', b'q', b'r', b's', b't',
+        b'u', b'v', b'w', b'x', b'y', b'z',
+        b'A', b'B', b'C', b'D', b'E', b'F', b'G', b'H', b'I', b'J',
+        b'K', b'L', b'M', b'N', b'O', b'P', b'Q', b'R', b'S', b'T',
+        b'U', b'V', b'W', b'X', b'Y', b'Z',
+        b'!', b'@', b'#', b'$', b'%', b'^', b'&', b'*', b'(', b')',
+        b'{', b'}', b'[', b']', b'<', b'>', b'-', b'=', b'_', b'+',
+        b':', b';', b',', b'.', b'/', b'?', b'|', b'"', b'\'', b'\\',
+    }
+}
+
+impl ToTokens for Range {
+    fn to_tokens(&self, tokens: &mut TokenStream) {
+        let Range { start, end } = self;
+
+        tokens.append_all(byte_to_tokens(*start));
+
+        if start != end {
+            tokens.append_all(quote!(..=));
+            tokens.append_all(byte_to_tokens(*end));
+        }
+    }
+}