earley_omnitool/forest/bocage/
node.rs

1use std::cell::Cell;
2use std::hint;
3
4use cfg::symbol::Symbol;
5
6pub use self::Node::*;
7use self::Tag::*;
8use forest::node_handle::{NodeHandle, NULL_HANDLE};
9
10// Node variants `Sum`/`Product` are better known in literature as `OR`/`AND`.
11#[derive(Copy, Clone, Debug)]
12pub enum Node {
13    Sum {
14        /// 8 bytes.
15        /// Invariant: count > 1.
16        /// Invariant: This node can only be directly followed by `Product`.
17        nonterminal: Symbol,
18        count: u32,
19    },
20    Product {
21        /// 12+ bytes.
22        action: u32,
23        left_factor: NodeHandle,
24        right_factor: Option<NodeHandle>,
25    },
26    NullingLeaf {
27        /// 4 bytes.
28        symbol: Symbol,
29    },
30    Evaluated {
31        /// 8 bytes.
32        symbol: Symbol,
33        values: u32,
34    },
35}
36
37#[derive(Clone)]
38pub struct CompactNode {
39    cell: Cell<[CompactField; 3]>,
40}
41
42// Node variants `Sum`/`Product` are better known in literature as `OR`/`AND`.
43#[derive(Copy, Clone)]
44union CompactField {
45    // sum
46    nonterminal: Symbol,
47    count: u32,
48
49    // product
50    action: u32,
51    factor: NodeHandle,
52    // right_factor: NodeHandle,
53
54    // leaf
55    symbol: Symbol,
56    values: u32,
57
58    // tag
59    tag: u32,
60}
61
62#[derive(Copy, Clone)]
63enum Tag {
64    LeafTag = 0b00 << TAG_BIT,
65    SumTag = 0b01 << TAG_BIT,
66    ProductTag = 0b10 << TAG_BIT,
67}
68
69impl Tag {
70    #[inline]
71    fn from_u32(n: u32) -> Option<Self> {
72        let n = n & TAG_MASK;
73        if n == LeafTag.to_u32() {
74            Some(LeafTag)
75        } else if n == SumTag.to_u32() {
76            Some(SumTag)
77        } else if n == ProductTag.to_u32() {
78            Some(ProductTag)
79        } else {
80            None
81        }
82    }
83
84    #[inline]
85    fn to_u32(&self) -> u32 {
86        match *self {
87            LeafTag => 0b00 << TAG_BIT,
88            SumTag => 0b01 << TAG_BIT,
89            ProductTag => 0b10 << TAG_BIT,
90        }
91    }
92}
93
94const TAG_BIT: usize = 30;
95const TAG_MASK: u32 = 0b11 << TAG_BIT;
96const NULL_VALUES: u32 = 0xFFFF_FFFF;
97pub(super) const NULL_ACTION: u32 = !TAG_MASK;
98
99impl Node {
100    #[inline]
101    pub(super) fn compact(self) -> CompactNode {
102        let mut fields = match self {
103            Product {
104                left_factor,
105                right_factor,
106                action,
107            } => {
108                let right_factor = right_factor.unwrap_or(NULL_HANDLE);
109                [
110                    CompactField { action },
111                    CompactField {
112                        factor: left_factor,
113                    },
114                    CompactField {
115                        factor: right_factor,
116                    },
117                ]
118            }
119            Sum { nonterminal, count } => [
120                CompactField { nonterminal },
121                CompactField { count },
122                CompactField { tag: 0 },
123            ],
124            NullingLeaf { symbol } => [
125                CompactField { symbol },
126                CompactField {
127                    values: NULL_VALUES,
128                },
129                CompactField { tag: 0 },
130            ],
131            Evaluated { symbol, values } => [
132                CompactField { symbol },
133                CompactField { values },
134                CompactField { tag: 0 },
135            ],
136        };
137        unsafe {
138            set_tag(&mut fields, self.tag());
139        }
140        CompactNode {
141            cell: Cell::new(fields),
142        }
143    }
144
145    #[inline]
146    fn tag(&self) -> Tag {
147        match self {
148            Product { .. } => ProductTag,
149            Sum { .. } => SumTag,
150            NullingLeaf { .. } | Evaluated { .. } => LeafTag,
151        }
152    }
153}
154
155impl CompactNode {
156    #[inline]
157    pub(super) fn set(&self, node: Node) {
158        self.cell.set(node.compact().cell.get());
159    }
160
161    #[inline]
162    pub(super) fn expand(&self) -> Node {
163        let mut fields = self.cell.get();
164        unsafe {
165            let tag = get_and_erase_tag(&mut fields);
166            match tag {
167                LeafTag => {
168                    if fields[1].values == NULL_VALUES {
169                        NullingLeaf {
170                            symbol: fields[0].symbol,
171                        }
172                    } else {
173                        Evaluated {
174                            symbol: fields[0].symbol,
175                            values: fields[1].values,
176                        }
177                    }
178                }
179                ProductTag => Product {
180                    action: fields[0].action,
181                    left_factor: fields[1].factor,
182                    right_factor: fields[2].factor.to_option(),
183                },
184                SumTag => Sum {
185                    nonterminal: fields[0].nonterminal,
186                    count: fields[1].count,
187                },
188            }
189        }
190    }
191}
192
193#[inline]
194unsafe fn unwrap_unchecked<T>(opt: Option<T>) -> T {
195    match opt {
196        Some(val) => val,
197        None => hint::unreachable_unchecked(),
198    }
199}
200
201#[inline]
202unsafe fn set_tag(fields: &mut [CompactField; 3], tag: Tag) {
203    fields[0].tag |= tag.to_u32();
204}
205
206#[inline]
207unsafe fn get_and_erase_tag(fields: &mut [CompactField; 3]) -> Tag {
208    let &mut CompactField { ref mut tag } = &mut fields[0];
209    let extract_tag = *tag;
210    *tag = *tag & !TAG_MASK;
211    unwrap_unchecked(Tag::from_u32(extract_tag))
212}
earley_omnitool/forest/bocage/node.rs

earley_omnitool/forest/bocage/
node.rs
