1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
//! Subtree representation and manipulation.
#![cfg_attr(feature = "strict_docs", allow(missing_docs))]
// Subtree representation with dynamic precedence support
use adze_ir::SymbolId;
use smallvec::SmallVec;
use std::sync::Arc;
/// Node information for a subtree
#[derive(Debug, Clone)]
pub struct SubtreeNode {
/// Symbol ID for this node
pub symbol_id: SymbolId,
/// Whether this node is an error node
pub is_error: bool,
/// Byte range in source text
pub byte_range: std::ops::Range<usize>,
}
/// A child edge with optional field information
#[derive(Debug, Clone)]
#[non_exhaustive]
pub struct ChildEdge {
/// The child subtree
pub subtree: Arc<Subtree>,
/// Field ID for this child (u16::MAX means no field)
pub field_id: u16,
}
/// Constant representing "no field" for a child edge
pub const FIELD_NONE: u16 = u16::MAX;
impl ChildEdge {
/// Create a new ChildEdge
pub fn new(subtree: Arc<Subtree>, field_id: u16) -> Self {
Self { subtree, field_id }
}
/// Create a ChildEdge without a field
pub fn new_without_field(subtree: Arc<Subtree>) -> Self {
Self {
subtree,
field_id: FIELD_NONE,
}
}
}
/// A subtree in the parse tree, potentially with dynamic precedence
#[derive(Debug, Clone)]
pub struct Subtree {
/// The tree node data
pub node: SubtreeNode,
/// Dynamic precedence value for this subtree
/// Set by prec.dynamic(n) annotations in the grammar
pub dynamic_prec: i32,
/// Child subtrees with optional field information
pub children: Vec<ChildEdge>,
/// Alternative parse trees for ambiguous nodes
/// Empty = single parse, non-empty = ambiguity pack
pub alternatives: SmallVec<[Arc<Subtree>; 2]>,
}
#[allow(dead_code)]
impl Subtree {
/// Create a new subtree with the given node and children (no field info)
pub fn new(node: SubtreeNode, children: Vec<Arc<Subtree>>) -> Self {
// Convert to ChildEdge with no field
let children_with_fields = children
.into_iter()
.map(|subtree| ChildEdge {
subtree,
field_id: FIELD_NONE,
})
.collect::<Vec<_>>();
// Propagate dynamic precedence upward (max of children)
let max_child_prec = children_with_fields
.iter()
.map(|c| c.subtree.dynamic_prec)
.max()
.unwrap_or(0);
Self {
node,
dynamic_prec: max_child_prec,
children: children_with_fields,
alternatives: SmallVec::new(),
}
}
/// Create a new subtree with field information for children
pub fn new_with_fields(node: SubtreeNode, children: Vec<ChildEdge>) -> Self {
// Propagate dynamic precedence upward (max of children)
let max_child_prec = children
.iter()
.map(|c| c.subtree.dynamic_prec)
.max()
.unwrap_or(0);
Self {
node,
dynamic_prec: max_child_prec,
children,
alternatives: SmallVec::new(),
}
}
/// Create a new subtree with explicit dynamic precedence (no field info)
pub fn with_dynamic_prec(
node: SubtreeNode,
children: Vec<Arc<Subtree>>,
dynamic_prec: i32,
) -> Self {
// Convert to ChildEdge with no field
let children_with_fields = children
.into_iter()
.map(|subtree| ChildEdge {
subtree,
field_id: FIELD_NONE,
})
.collect::<Vec<_>>();
// Take max of explicit precedence and children's precedence
let max_child_prec = children_with_fields
.iter()
.map(|c| c.subtree.dynamic_prec)
.max()
.unwrap_or(0);
Self {
node,
dynamic_prec: dynamic_prec.max(max_child_prec),
children: children_with_fields,
alternatives: SmallVec::new(),
}
}
/// Create a new subtree with explicit dynamic precedence and field info
pub fn with_dynamic_prec_and_fields(
node: SubtreeNode,
children: Vec<ChildEdge>,
dynamic_prec: i32,
) -> Self {
// Take max of explicit precedence and children's precedence
let max_child_prec = children
.iter()
.map(|c| c.subtree.dynamic_prec)
.max()
.unwrap_or(0);
Self {
node,
dynamic_prec: dynamic_prec.max(max_child_prec),
children,
alternatives: SmallVec::new(),
}
}
/// Get the symbol ID for this subtree
pub fn symbol(&self) -> u16 {
self.node.symbol_id.0
}
/// Check if this subtree is in error
pub fn is_error(&self) -> bool {
self.node.is_error
}
/// Get the byte range for this subtree
pub fn byte_range(&self) -> std::ops::Range<usize> {
self.node.byte_range.clone()
}
/// Check if this subtree has ambiguous alternatives
pub fn is_ambiguous(&self) -> bool {
!self.alternatives.is_empty()
}
/// Check if this subtree has alternatives
pub fn has_alts(&self) -> bool {
!self.alternatives.is_empty()
}
/// Get all alternatives (not including the primary tree)
pub fn alternatives_iter(&self) -> impl Iterator<Item = &Arc<Subtree>> {
self.alternatives.iter()
}
/// Merge two subtrees with the same top, preserving all alternatives
pub fn merge_ambiguous(mut self, other: Arc<Subtree>) -> Self {
// If the other tree also has alternatives, merge them all
if !other.alternatives.is_empty() {
for alt in &other.alternatives {
if !self
.alternatives
.iter()
.any(|a: &Arc<Subtree>| Arc::ptr_eq(a, alt))
{
self.alternatives.push(alt.clone());
}
}
}
// Add the other tree itself as an alternative (if not already present)
// Need to check by pointer equality since we're moving other
let other_ptr = Arc::as_ptr(&other);
if !self
.alternatives
.iter()
.any(|a: &Arc<Subtree>| Arc::as_ptr(a) == other_ptr)
{
// Keep the highest dynamic precedence before moving
self.dynamic_prec = self.dynamic_prec.max(other.dynamic_prec);
self.alternatives.push(other);
} else {
// Still update precedence even if not adding
self.dynamic_prec = self.dynamic_prec.max(other.dynamic_prec);
}
self
}
/// Create a new subtree with the given alternative
pub fn with_alts(mut self, alt: Arc<Subtree>) -> Self {
if !self.alternatives.iter().any(|a| Arc::ptr_eq(a, &alt)) {
self.alternatives.push(alt);
}
self
}
/// Add an alternative to this subtree (deduplicating by pointer)
pub fn push_alt(mut self, alt: Arc<Subtree>) -> Self {
let alt_ptr = Arc::as_ptr(&alt);
if !self.alternatives.iter().any(|a| Arc::as_ptr(a) == alt_ptr) {
self.dynamic_prec = self.dynamic_prec.max(alt.dynamic_prec);
self.alternatives.push(alt);
}
self
}
/// Concatenate alternatives from two subtrees (deduplicating)
pub fn concat_alts(mut self, other: Arc<Subtree>) -> Self {
// First add the other tree as an alternative
self = self.push_alt(other.clone());
// Then add all of its alternatives
for alt in &other.alternatives {
if !self
.alternatives
.iter()
.any(|a: &Arc<Subtree>| Arc::ptr_eq(a, alt))
{
self.alternatives.push(alt.clone());
}
}
self
}
}