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
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
use crate::{
kind::{CppSyntaxKind, CppTokenKind},
text::SourceRange,
};
#[derive(Debug, Clone)]
pub enum MarkEvent {
NodeStart {
kind: CppSyntaxKind,
/// Forward parent: another `NodeStart` that must be opened *outside* this one. Uses
/// [`NO_FORWARD_PARENT`] when there is none, so that position `0` stays addressable.
parent: usize,
},
EatToken {
kind: CppTokenKind,
range: SourceRange,
},
NodeEnd,
Trivia,
}
/// Sentinel for "this node has no forward parent". Must never collide with a real event index.
pub(crate) const NO_FORWARD_PARENT: usize = usize::MAX;
impl MarkEvent {
pub fn none() -> Self {
MarkEvent::NodeStart {
kind: CppSyntaxKind::None,
parent: NO_FORWARD_PARENT,
}
}
}
pub(crate) trait MarkerEventContainer {
/// Number of nodes currently open. Snapshot it before a speculative or fallible sub-parse so
/// that [`MarkerEventContainer::finish_marks_to`] can undo the damage on failure.
fn get_mark_level(&self) -> usize;
/// Register a newly opened node, so that it can be closed by `finish_marks_to`.
fn push_mark(&mut self, position: usize);
fn get_events(&mut self) -> &mut Vec<MarkEvent>;
fn mark(&mut self, kind: CppSyntaxKind) -> Marker {
let position = self.get_events().len();
self.get_events().push(MarkEvent::NodeStart {
kind,
parent: NO_FORWARD_PARENT,
});
self.push_mark(position);
Marker::new(position)
}
/// Close every node opened after `target` was snapshotted with
/// [`MarkerEventContainer::get_mark_level`].
///
/// This is the error-recovery counterpart to `?`: it turns "returning early from the middle
/// of a grammar rule" from a silent tree corruption into a no-op, because the leaked
/// `NodeStart` events stop being able to swallow the tokens that follow.
///
/// Nodes are closed **by identity, not by counting**. Emitting `level - target` `NodeEnd`
/// events is wrong: `target` is a snapshot taken by an *ancestor*, and the nodes opened since
/// are not necessarily still nested the way a naive pop order assumes. Worse, closing by count
/// can close a node whose rule is still on the stack, and then that rule's own `complete()`
/// emits a *second* `NodeEnd` — which closes somebody else's node and unbalances everything
/// after it.
///
/// So the recovered nodes are detached **without** an event. Their `NodeEnd` is left to their
/// owner: a rule still on the stack will reach its `complete()` and emit it then, paired with
/// the matching `NodeStart`. Rules that are genuinely abandoned simply leave a `NodeStart`
/// behind, which the tree builder balances by appending `NodeEnd`s at the end of the stream.
fn finish_marks_to(&mut self, target: usize) {
if self.get_mark_level() <= target {
return;
}
for position in self.drain_marks(target) {
self.close_mark(position, false);
}
}
/// Close every node opened after `target` **and emit each one's `NodeEnd`**.
///
/// The counterpart of [`MarkerEventContainer::finish_marks_to`] for the one caller that is *not*
/// abandoning the tokens: a class body whose member declaration failed **after** consuming them.
/// Detaching is wrong there, and the cost is not local. An unpaired `NodeStart` is balanced by the tree
/// builder at the **end of the stream**, so the abandoned declaration swallows every token written after
/// it — the members below it stop being members, and nothing reports anything:
///
/// ```cpp
/// struct Base {
/// _GLIBCXX20_CONSTEXPR void f(size_type) { } // a declaration the general rule cannot finish
/// int after; // …and this became a *child* of it
/// };
/// ```
///
/// That is `bits/stl_vector.h`'s `_Vector_impl` and, through it, all of `std::vector`: one declaration
/// the parser gave up on took the rest of the class with it, silently (, tenth
/// round). Emitting the ends keeps what was read — the declaration node is there, with its specifiers and
/// its declarator — and lets the recovery carry on beside it rather than inside it.
///
/// Innermost first, which is the order a tree builder pairs them in; the `NodeStart`s are opened
/// outermost first, so the stack is walked backwards. Closing a mark that already has its end event is a
/// no-op, so a node whose owner did reach its own `complete()` is not closed twice.
fn end_marks_to(&mut self, target: usize) {
if self.get_mark_level() <= target {
return;
}
let mut positions = self.drain_marks(target);
positions.reverse();
for position in positions {
self.close_mark(position, true);
}
}
/// Remove and return the open-node positions above `target`.
fn drain_marks(&mut self, target: usize) -> Vec<usize>;
/// Mark a node as closed, optionally emitting its `NodeEnd`.
///
/// The open set and the event stream are updated together here, so they can never disagree
/// about whether a node has been closed. Returns whether an event was emitted.
fn close_mark(&mut self, position: usize, want_event: bool) -> bool;
/// Has a `NodeEnd` already been emitted for the node opened at `position`?
fn mark_has_end_event(&self, position: usize) -> bool;
/// Was this node closed *without* emitting its `NodeEnd`?
///
/// This is distinct from "not open" and the distinction is load-bearing. Recovery detaches a
/// node without an event, on the understanding that its owner will emit the event when it
/// reaches its own `complete()`. But the owner may instead be dropped as empty and emit
/// nothing at all — and then the *grandparent* emits an event that pairs with nothing, which
/// silently closes an unrelated ancestor in the tree builder.
///
/// [`Marker::complete`] therefore asks this question rather than "is it open?".
fn mark_was_detached(&self, position: usize) -> bool;
/// Is the node opened at `position` still open?
fn mark_is_open(&self, position: usize) -> bool;
}
pub(crate) struct Marker {
pub position: usize,
}
impl Marker {
pub fn new(position: usize) -> Self {
Marker { position }
}
/// Overwrite the kind of the node this marker opened. Used by callers that discover the
/// concrete construct only after parsing it (e.g. `class X;` vs `class X { ... };`).
#[allow(dead_code)]
pub fn set_kind<P: MarkerEventContainer>(&mut self, p: &mut P, kind: CppSyntaxKind) {
match &mut p.get_events()[self.position] {
MarkEvent::NodeStart { kind: k, .. } => *k = kind,
_ => unreachable!(),
}
}
pub fn complete<P: MarkerEventContainer>(self, p: &mut P) -> CompleteMarker {
let kind = match p.get_events()[self.position] {
MarkEvent::NodeStart { kind: k, .. } => k,
_ => unreachable!(),
};
// Already closed with an event: nothing left to do.
if p.mark_has_end_event(self.position) {
return CompleteMarker {
start: self.position,
kind,
};
}
// Detached by recovery without an event. That event is still owed, and the reason is not
// obvious: recovery detaches a node on the understanding that its owner will emit the event
// when it reaches its own `complete()`. If that owner is then *dropped as empty*, it emits
// nothing, and the grandparent's own event — emitted on the assumption that its children
// paired up — ends up closing an unrelated ancestor instead. The tree stays well formed;
// only its nesting is wrong, which is the failure mode this whole marker stack exists to
// make impossible.
//
// So a detached node always gets its event, even when it looks empty: the emptiness is
// exactly what the owner is about to be wrong about.
if p.mark_was_detached(self.position) {
p.close_mark(self.position, true);
return CompleteMarker {
start: self.position,
kind,
};
}
// A node that never produced content carries no information, so drop it. Deregistering the
// mark is still mandatory, or the open-node stack drifts upwards forever.
//
// The `NodeEnd` is emitted *anyway*, and that is the whole point rather than an oversight.
// The event stream has to pair one-to-one — that is what lets the tree builder translate it
// by simply opening on a start and closing on an end — so an empty node that emits only its
// `NodeStart` leaves the *next* `NodeEnd`, which belongs to its parent, closing the wrong
// node. One short close is enough to re-parent everything that follows, silently.
//
// Emitting both events keeps the stream a 1:1 mapping at every point in the parse, and
// `balance_events` then removes the empty *pair* together, which is where dropping belongs.
if p.mark_is_open(self.position) && p.get_events().len() == self.position + 1 {
p.close_mark(self.position, true);
return CompleteMarker {
start: EMPTY_NODE_POSITION,
kind: CppSyntaxKind::None,
};
}
p.close_mark(self.position, true);
CompleteMarker {
start: self.position,
kind,
}
}
/// Complete the node, but keep the result usable as a positioned node.
///
/// `Marker::complete` degrades to `CompleteMarker::empty()` when the node turns out to be
/// empty, which makes it impossible to tell "the construct was there but produced no
/// events" from "the construct was not there". This variant keeps the original position so
/// the caller can still call `set_kind` afterwards.
#[allow(dead_code)]
pub fn complete_non_empty<P: MarkerEventContainer>(self, p: &mut P) -> CompleteMarker {
let kind = match p.get_events()[self.position] {
MarkEvent::NodeStart { kind: k, .. } => k,
_ => unreachable!(),
};
if p.mark_has_end_event(self.position) {
return CompleteMarker {
start: self.position,
kind,
};
}
if p.mark_was_detached(self.position) {
p.close_mark(self.position, true);
return CompleteMarker {
start: self.position,
kind,
};
}
if p.get_events().len() == self.position + 1 {
p.close_mark(self.position, false);
return CompleteMarker {
start: self.position,
kind: CppSyntaxKind::None,
};
}
p.close_mark(self.position, true);
CompleteMarker {
start: self.position,
kind,
}
}
#[allow(unused)]
pub fn undo<P: MarkerEventContainer>(self, p: &mut P) {
match &mut p.get_events()[self.position] {
MarkEvent::NodeStart { kind, .. } => {
*kind = CppSyntaxKind::None;
}
_ => unreachable!(),
}
// **And off the open stack**, which is the half that was missing. An undone node keeps its events — the tokens
// it consumed are in the tree either way — but it is not a node any more, so leaving it registered is a mark
// no owner will ever complete: the rule that opened it has just said so.
//
// Measured: `class A { A(; };` — a constructor whose parameter list has no closer — left one undone marker
// open for the rest of the file, and `parse_cpp_unit`'s own check (`open_marks == base + 1`) is what caught
// it. The rule's caller does unwind with `close_marks_above(base)`, which would have drained it, but a
// *snapshot taken after the leak* cannot: the undone mark is below it, so every later recovery in the file
// closes down to a level that still holds it.
p.close_mark(self.position, false);
}
}
pub(crate) struct CompleteMarker {
start: usize,
#[allow(dead_code)]
pub kind: CppSyntaxKind,
}
/// Sentinel used by [`CompleteMarker::empty`]: it never points at a real event and every
/// consumer must treat it as "no node here".
pub(crate) const EMPTY_NODE_POSITION: usize = usize::MAX;
#[allow(dead_code)]
impl CompleteMarker {
pub fn precede<P: MarkerEventContainer>(&self, p: &mut P, kind: CppSyntaxKind) -> Marker {
let m = p.mark(kind);
match &mut p.get_events()[self.start] {
MarkEvent::NodeStart { parent, .. } => *parent = m.position,
_ => unreachable!(),
}
p.get_events().push(MarkEvent::Trivia);
m
}
/// Like [`CompleteMarker::precede`], but safe to call on an empty marker: if the completed
/// node produced no events there is nothing to re-parent, so the newly created marker is
/// undone and the empty marker is returned unchanged.
pub fn precede_or_noop<P: MarkerEventContainer>(
self,
p: &mut P,
kind: CppSyntaxKind,
) -> CompleteMarker {
if self.is_empty() {
return self;
}
let m = self.precede(p, kind);
CompleteMarker {
start: m.position,
kind,
}
}
pub fn empty() -> Self {
CompleteMarker {
start: EMPTY_NODE_POSITION,
kind: CppSyntaxKind::None,
}
}
pub fn is_empty(&self) -> bool {
self.start == EMPTY_NODE_POSITION || self.kind == CppSyntaxKind::None
}
pub fn start_position(&self) -> usize {
self.start
}
}