1 files changed, 174 insertions, 0 deletions
diff --git a/vendor/logos-codegen/src/graph/meta.rs b/vendor/logos-codegen/src/graph/meta.rs
new file mode 100644
index 00000000..757ced09
--- /dev/null
+++ b/vendor/logos-codegen/src/graph/meta.rs
@@ -0,0 +1,174 @@
+use std::cmp::min;
+use std::collections::BTreeMap;
+use std::ops::{Index, IndexMut};
+
+use crate::graph::{Graph, Node, NodeId};
+
+#[derive(Debug)]
+pub struct Meta {
+    map: BTreeMap<NodeId, MetaItem>,
+}
+
+#[derive(Debug, Default)]
+pub struct MetaItem {
+    /// Number of references to this node
+    pub refcount: usize,
+    /// Minimum number of bytes that ought to be read for this
+    /// node to find a match
+    pub min_read: usize,
+    /// Marks whether or not this node leads to a loop entry node.
+    pub is_loop_init: bool,
+    /// Ids of other nodes that point to this node while this
+    /// node is on a stack (creating a loop)
+    pub loop_entry_from: Vec<NodeId>,
+}
+
+impl Index<NodeId> for Meta {
+    type Output = MetaItem;
+
+    fn index(&self, id: NodeId) -> &MetaItem {
+        &self.map[&id]
+    }
+}
+
+impl IndexMut<NodeId> for Meta {
+    fn index_mut(&mut self, id: NodeId) -> &mut MetaItem {
+        self.map.entry(id).or_default()
+    }
+}
+
+impl MetaItem {
+    fn loop_entry(&mut self, id: NodeId) {
+        if let Err(idx) = self.loop_entry_from.binary_search(&id) {
+            self.loop_entry_from.insert(idx, id);
+        }
+    }
+}
+
+impl Meta {
+    pub fn analyze<T>(root: NodeId, graph: &Graph<T>) -> Self {
+        let mut meta = Meta {
+            map: Default::default(),
+        };
+
+        meta.first_pass(root, root, graph, &mut Vec::new());
+
+        meta
+    }
+
+    pub fn first_pass<T>(
+        &mut self,
+        this: NodeId,
+        parent: NodeId,
+        graph: &Graph<T>,
+        stack: &mut Vec<NodeId>,
+    ) -> &MetaItem {
+        let meta = &mut self[this];
+        let is_done = meta.refcount > 0;
+
+        meta.refcount += 1;
+
+        if stack.contains(&this) {
+            meta.loop_entry(parent);
+            self[parent].is_loop_init = true;
+        }
+        if is_done {
+            return &self[this];
+        }
+
+        stack.push(this);
+
+        let mut min_read;
+
+        match &graph[this] {
+            Node::Fork(fork) => {
+                min_read = usize::MAX;
+                for (_, id) in fork.branches() {
+                    let meta = self.first_pass(id, this, graph, stack);
+
+                    if meta.is_loop_init {
+                        min_read = 1;
+                    } else {
+                        min_read = min(min_read, meta.min_read + 1);
+                    }
+                }
+                if let Some(id) = fork.miss {
+                    let meta = self.first_pass(id, this, graph, stack);
+
+                    if meta.is_loop_init {
+                        min_read = 0;
+                    } else {
+                        min_read = min(min_read, meta.min_read);
+                    }
+                }
+                if min_read == usize::MAX {
+                    min_read = 0;
+                }
+            }
+            Node::Rope(rope) => {
+                min_read = rope.pattern.len();
+                let meta = self.first_pass(rope.then, this, graph, stack);
+
+                if !meta.is_loop_init {
+                    min_read += meta.min_read;
+                }
+
+                if let Some(id) = rope.miss.first() {
+                    let meta = self.first_pass(id, this, graph, stack);
+
+                    if meta.is_loop_init {
+                        min_read = 0;
+                    } else {
+                        min_read = min(min_read, meta.min_read);
+                    }
+                }
+            }
+            Node::Leaf(_) => min_read = 0,
+        }
+
+        stack.pop();
+
+        let meta = &mut self[this];
+        meta.min_read = min_read;
+        let second_pass = meta.loop_entry_from.clone();
+
+        for id in second_pass {
+            self.meta_second_pass(id, graph);
+        }
+
+        &self[this]
+    }
+
+    fn meta_second_pass<T>(&mut self, id: NodeId, graph: &Graph<T>) {
+        let mut min_read;
+
+        match &graph[id] {
+            Node::Fork(fork) => {
+                min_read = usize::MAX;
+                for (_, id) in fork.branches() {
+                    let meta = &self[id];
+
+                    if meta.is_loop_init {
+                        min_read = 1;
+                    } else {
+                        min_read = min(min_read, meta.min_read + 1);
+                    }
+                }
+                if min_read == usize::MAX {
+                    min_read = 0;
+                }
+            }
+            Node::Rope(rope) => {
+                min_read = rope.pattern.len();
+                let meta = &self[rope.then];
+
+                if !meta.is_loop_init {
+                    min_read += meta.min_read;
+                }
+            }
+            Node::Leaf(_) => unreachable!(),
+        }
+
+        self[id].min_read = min_read;
+    }
+}