logos_codegen/graph/
meta.rs

1use std::cmp::min;
2use std::collections::BTreeMap;
3use std::ops::{Index, IndexMut};
4
5use crate::graph::{Graph, Node, NodeId};
6
7#[derive(Debug)]
8pub struct Meta {
9    map: BTreeMap<NodeId, MetaItem>,
10}
11
12#[derive(Debug, Default)]
13pub struct MetaItem {
14    /// Number of references to this node
15    pub refcount: usize,
16    /// Minimum number of bytes that ought to be read for this
17    /// node to find a match
18    pub min_read: usize,
19    /// Marks whether or not this node leads to a loop entry node.
20    pub is_loop_init: bool,
21    /// Ids of other nodes that point to this node while this
22    /// node is on a stack (creating a loop)
23    pub loop_entry_from: Vec<NodeId>,
24}
25
26impl Index<NodeId> for Meta {
27    type Output = MetaItem;
28
29    fn index(&self, id: NodeId) -> &MetaItem {
30        &self.map[&id]
31    }
32}
33
34impl IndexMut<NodeId> for Meta {
35    fn index_mut(&mut self, id: NodeId) -> &mut MetaItem {
36        self.map.entry(id).or_default()
37    }
38}
39
40impl MetaItem {
41    fn loop_entry(&mut self, id: NodeId) {
42        if let Err(idx) = self.loop_entry_from.binary_search(&id) {
43            self.loop_entry_from.insert(idx, id);
44        }
45    }
46}
47
48impl Meta {
49    pub fn analyze<T>(root: NodeId, graph: &Graph<T>) -> Self {
50        let mut meta = Meta {
51            map: Default::default(),
52        };
53
54        meta.first_pass(root, root, graph, &mut Vec::new());
55
56        meta
57    }
58
59    pub fn first_pass<T>(
60        &mut self,
61        this: NodeId,
62        parent: NodeId,
63        graph: &Graph<T>,
64        stack: &mut Vec<NodeId>,
65    ) -> &MetaItem {
66        let meta = &mut self[this];
67        let is_done = meta.refcount > 0;
68
69        meta.refcount += 1;
70
71        if stack.contains(&this) {
72            meta.loop_entry(parent);
73            self[parent].is_loop_init = true;
74        }
75        if is_done {
76            return &self[this];
77        }
78
79        stack.push(this);
80
81        let mut min_read;
82
83        match &graph[this] {
84            Node::Fork(fork) => {
85                min_read = usize::MAX;
86                for (_, id) in fork.branches() {
87                    let meta = self.first_pass(id, this, graph, stack);
88
89                    if meta.is_loop_init {
90                        min_read = 1;
91                    } else {
92                        min_read = min(min_read, meta.min_read + 1);
93                    }
94                }
95                if let Some(id) = fork.miss {
96                    let meta = self.first_pass(id, this, graph, stack);
97
98                    if meta.is_loop_init {
99                        min_read = 0;
100                    } else {
101                        min_read = min(min_read, meta.min_read);
102                    }
103                }
104                if min_read == usize::MAX {
105                    min_read = 0;
106                }
107            }
108            Node::Rope(rope) => {
109                min_read = rope.pattern.len();
110                let meta = self.first_pass(rope.then, this, graph, stack);
111
112                if !meta.is_loop_init {
113                    min_read += meta.min_read;
114                }
115
116                if let Some(id) = rope.miss.first() {
117                    let meta = self.first_pass(id, this, graph, stack);
118
119                    if meta.is_loop_init {
120                        min_read = 0;
121                    } else {
122                        min_read = min(min_read, meta.min_read);
123                    }
124                }
125            }
126            Node::Leaf(_) => min_read = 0,
127        }
128
129        stack.pop();
130
131        let meta = &mut self[this];
132        meta.min_read = min_read;
133        let second_pass = meta.loop_entry_from.clone();
134
135        for id in second_pass {
136            self.meta_second_pass(id, graph);
137        }
138
139        &self[this]
140    }
141
142    fn meta_second_pass<T>(&mut self, id: NodeId, graph: &Graph<T>) {
143        let mut min_read;
144
145        match &graph[id] {
146            Node::Fork(fork) => {
147                min_read = usize::MAX;
148                for (_, id) in fork.branches() {
149                    let meta = &self[id];
150
151                    if meta.is_loop_init {
152                        min_read = 1;
153                    } else {
154                        min_read = min(min_read, meta.min_read + 1);
155                    }
156                }
157                if min_read == usize::MAX {
158                    min_read = 0;
159                }
160            }
161            Node::Rope(rope) => {
162                min_read = rope.pattern.len();
163                let meta = &self[rope.then];
164
165                if !meta.is_loop_init {
166                    min_read += meta.min_read;
167                }
168            }
169            Node::Leaf(_) => unreachable!(),
170        }
171
172        self[id].min_read = min_read;
173    }
174}
logos_codegen/graph/meta.rs

logos_codegen/graph/
meta.rs
