cpp_parser 0.2.0

A lossless C++ parser over the preprocessed text: the tree every layer above it reads.
Documentation
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
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
//! The typed AST layer on top of the untyped rowan tree.
//!
//! # How this layer works
//!
//! The syntax tree is *untyped*: every node knows only its [`CppSyntaxKind`]. This layer adds the
//! types — `CppFunctionDef`, `CppBinaryExpr`, `CppParameter` — as cheap newtypes around a red
//! [`CppSyntaxNode`], with `cast`/`can_cast` deciding whether a node is of that type.
//!
//! That shape (and the names in it) follows the Lua implementation this project grew out of, so code
//! written against the old API keeps working. See `reference/README.md` for where that code lives now.
//!
//! # The three traits
//!
//! * [`CppAstNode`] — a **node** type. Gives typed child/token access and tree navigation.
//! * [`CppAstToken`] — a **token** type. Gives access to the token's text.
//! * [`CppAst`] — a sum type over every node kind, for callers that want to dispatch on what a node
//!   actually is.
//!
//! # Why accessors return `Option`
//!
//! An editor parses files that are being typed, so every construct may be missing, half-written or
//! wrong. An accessor that panicked on a malformed node would turn a typo into a crash, so they
//! return `Option` and callers degrade gracefully. This is also why nothing here validates
//! structure: `get_name()` on a function returns the first name token it can find, whatever the
//! rest of the declaration looks like.

use std::marker::PhantomData;

use rowan::{TextRange, TextSize, WalkEvent};

use crate::kind::{CppKind, CppSyntaxKind, CppTokenKind};
use crate::kind::{CppSyntaxElementChildren, CppSyntaxNodeChildren};

use crate::lexer::CppTokenData;
use crate::syntax::{CppSyntaxId, CppSyntaxNode, CppSyntaxToken};

pub use super::cpp::*;
pub use super::token::*;

/// A typed syntax **node**.
pub trait CppAstNode {
    fn syntax(&self) -> &CppSyntaxNode;

    /// Is a node of this kind a node of type `Self`?
    ///
    /// Separate from `cast` so callers can test a kind without building the wrapper, which is what
    /// [`CppAstChildren`] does on every step of an iteration.
    fn can_cast(kind: CppSyntaxKind) -> bool
    where
        Self: Sized;

    fn cast(syntax: CppSyntaxNode) -> Option<Self>
    where
        Self: Sized;

    /// The first child node of type `N`.
    fn child<N: CppAstNode>(&self) -> Option<N> {
        self.syntax().children().find_map(N::cast)
    }

    /// The first child token of type `N`.
    fn token<N: CppAstToken>(&self) -> Option<N> {
        self.syntax()
            .children_with_tokens()
            .find_map(|it| it.into_token().and_then(N::cast))
    }

    /// The first child token with the given kind, as a generic token.
    fn token_by_kind(&self, kind: CppTokenKind) -> Option<super::token::CppGeneralToken> {
        let token = self
            .syntax()
            .children_with_tokens()
            .filter_map(|it| it.into_token())
            .find(|it| it.kind() == CppKind::Token(kind))?;

        super::token::CppGeneralToken::cast(token)
    }

    /// All child nodes of type `N`.
    fn children<N: CppAstNode>(&self) -> CppAstChildren<N> {
        CppAstChildren::new(self.syntax())
    }

    /// All child tokens of type `N`.
    fn tokens<N: CppAstToken>(&self) -> CppAstTokenChildren<N> {
        CppAstTokenChildren::new(self.syntax())
    }

    /// All descendant nodes of type `N`.
    fn descendants<N: CppAstNode>(&self) -> impl Iterator<Item = N> {
        self.syntax().descendants().filter_map(N::cast)
    }

    /// All descendants of type `N`, with enter/leave events.
    fn walk_descendants<N: CppAstNode>(&self) -> impl Iterator<Item = WalkEvent<N>> {
        self.syntax().preorder().filter_map(|event| match event {
            WalkEvent::Enter(node) => N::cast(node).map(WalkEvent::Enter),
            WalkEvent::Leave(node) => N::cast(node).map(WalkEvent::Leave),
        })
    }

    /// All ancestor nodes of type `N`, innermost first.
    fn ancestors<N: CppAstNode>(&self) -> impl Iterator<Item = N> {
        self.syntax().ancestors().filter_map(N::cast)
    }

    /// The root of the tree this node belongs to.
    fn get_root(&self) -> CppSyntaxNode {
        let syntax = self.syntax();
        // `TranslationUnit` is the root, so reaching it means there is nothing above. Using
        // `ancestors().last()` unconditionally would clone the whole chain for the common case.
        if syntax.kind() == CppKind::Syntax(CppSyntaxKind::TranslationUnit) {
            syntax.clone()
        } else {
            syntax.ancestors().last().unwrap_or_else(|| syntax.clone())
        }
    }

    /// **The sibling node immediately before this one**, when it is of type `N`.
    ///
    /// A declaration's attribute list is written before the declaration and is its **sibling**, not its child
    /// (`[[maybe_unused]] int x;` at file scope is `AttributeList` then `Declaration`), and so are several other C++ shapes: a
    /// `template` header before a declaration, a `case` label before a statement. Rowan's `prev_sibling` is untyped; this is the
    /// typed form.
    fn previous_sibling<N: CppAstNode>(&self) -> Option<N> {
        self.syntax().prev_sibling().and_then(N::cast)
    }

    /// The sibling node immediately after this one, when it is of type `N`.
    fn next_sibling<N: CppAstNode>(&self) -> Option<N> {
        self.syntax().next_sibling().and_then(N::cast)
    }

    /// The parent node, if it is of type `N`.
    fn get_parent<N: CppAstNode>(&self) -> Option<N> {
        self.syntax().parent().and_then(N::cast)
    }

    fn get_position(&self) -> TextSize {
        self.syntax().text_range().start()
    }

    fn get_range(&self) -> TextRange {
        self.syntax().text_range()
    }

    /// The containing node of type `N`, starting from this node itself.
    fn get_self_or_ancestor<N: CppAstNode>(&self) -> Option<N> {
        N::cast(self.syntax().clone()).or_else(|| self.ancestors().next())
    }

    /// A storable, comparable handle to this node. See [`CppSyntaxId`].
    fn get_syntax_id(&self) -> CppSyntaxId {
        CppSyntaxId::from_node(self.syntax())
    }

    /// The tree, rendered for debugging.
    fn dump(&self) -> String {
        format!("{:#?}", self.syntax())
    }
}

/// An iterator over the child **nodes** of a particular AST type.
#[derive(Debug, Clone)]
pub struct CppAstChildren<N> {
    inner: CppSyntaxNodeChildren,
    ph: PhantomData<N>,
}

impl<N> CppAstChildren<N> {
    pub fn new(parent: &CppSyntaxNode) -> CppAstChildren<N> {
        CppAstChildren {
            inner: parent.children(),
            ph: PhantomData,
        }
    }
}

impl<N: CppAstNode> Iterator for CppAstChildren<N> {
    type Item = N;

    fn next(&mut self) -> Option<N> {
        self.inner.find_map(N::cast)
    }
}

/// A typed syntax **token**.
pub trait CppAstToken {
    fn syntax(&self) -> &CppSyntaxToken;

    fn can_cast(kind: CppTokenKind) -> bool
    where
        Self: Sized;

    fn cast(syntax: CppSyntaxToken) -> Option<Self>
    where
        Self: Sized;

    fn get_token_kind(&self) -> CppTokenKind {
        self.syntax().kind().into()
    }

    /// The token's own data, for callers that want to pass it around without the tree.
    fn get_token_data(&self) -> CppTokenData {
        CppTokenData::new(
            self.get_token_kind(),
            source_range(self.syntax().text_range()),
        )
    }

    fn get_position(&self) -> TextSize {
        self.syntax().text_range().start()
    }

    fn get_range(&self) -> TextRange {
        self.syntax().text_range()
    }

    fn get_syntax_id(&self) -> CppSyntaxId {
        CppSyntaxId::from_token(self.syntax())
    }

    fn get_text(&self) -> &str {
        self.syntax().text()
    }

    fn get_parent<N: CppAstNode>(&self) -> Option<N> {
        self.syntax().parent().and_then(N::cast)
    }

    fn ancestors<N: CppAstNode>(&self) -> impl Iterator<Item = N> {
        self.syntax().parent_ancestors().filter_map(N::cast)
    }

    fn dump(&self) -> String {
        format!("{:#?}", self.syntax())
    }
}

/// An iterator over the child **tokens** of a particular AST type.
#[derive(Debug, Clone)]
pub struct CppAstTokenChildren<N> {
    inner: CppSyntaxElementChildren,
    ph: PhantomData<N>,
}

impl<N> CppAstTokenChildren<N> {
    pub fn new(parent: &CppSyntaxNode) -> CppAstTokenChildren<N> {
        CppAstTokenChildren {
            inner: parent.children_with_tokens(),
            ph: PhantomData,
        }
    }
}

impl<N: CppAstToken> Iterator for CppAstTokenChildren<N> {
    type Item = N;

    fn next(&mut self) -> Option<N> {
        self.inner.find_map(|it| it.into_token().and_then(N::cast))
    }
}

/// **The typed descendants of a raw node**, in document order.
///
/// The bridge for a caller that holds a [`CppSyntaxNode`](crate::CppSyntaxNode) rather than a typed node — a scope tree over a
/// file, say — and wants the typed layer's walk. `node.descendants()` is rowan's untyped walk; this one answers types.
pub fn typed_descendants<N: CppAstNode + 'static>(
    node: &CppSyntaxNode,
) -> impl Iterator<Item = N> + '_ {
    node.descendants().filter_map(N::cast)
}

/// **The typed children of a raw node.**
pub fn typed_children<N: CppAstNode + 'static>(
    node: &CppSyntaxNode,
) -> impl Iterator<Item = N> + '_ {
    node.children().filter_map(N::cast)
}

/// **The typed ancestors of a raw node**, innermost first.
pub fn typed_ancestors<N: CppAstNode + 'static>(
    node: &CppSyntaxNode,
) -> impl Iterator<Item = N> + '_ {
    node.ancestors().filter_map(N::cast)
}

/// **The typed ancestors of a raw node, stopping before `stop`.**
///
/// `stop` is exclusive: the walk answers the nodes strictly between `node` and `stop` in the tree. Its use is the question "is
/// there a lambda between this return statement and the body that owns it" — a walk without the bound ascends into the
/// enclosing function and can never answer no.
/// **The typed sibling before a raw node**, when it is of type N.
pub fn typed_previous_sibling<N: CppAstNode + 'static>(node: &CppSyntaxNode) -> Option<N> {
    node.prev_sibling().and_then(N::cast)
}

/// **The typed sibling after a raw node**, when it is of type N.
pub fn typed_next_sibling<N: CppAstNode + 'static>(node: &CppSyntaxNode) -> Option<N> {
    node.next_sibling().and_then(N::cast)
}

pub fn typed_ancestors_until<'a, N: CppAstNode + 'static>(
    node: &'a CppSyntaxNode,
    stop: &'a CppSyntaxNode,
) -> impl Iterator<Item = N> + 'a {
    node.ancestors()
        .take_while(move |ancestor| ancestor != stop)
        .filter_map(N::cast)
}

/// Is this node covered by one of `kinds`?
///
/// A helper for the `can_cast` bodies, which are otherwise the same match repeated for every type.
pub fn node_kind_in(kind: CppSyntaxKind, kinds: &[CppSyntaxKind]) -> bool {
    kinds.contains(&kind)
}

/// The token kinds that may appear as trivia, in the order the lexer emits them.
///
/// Exposed because the AST layer frequently has to step over trivia to find the *significant* token
/// next to a construct — "is this declaration followed by a `;`" has to ignore a comment.
pub const TRIVIA_KINDS: &[CppTokenKind] = &[
    CppTokenKind::Whitespace,
    CppTokenKind::Newline,
    CppTokenKind::LineContinuation,
    CppTokenKind::LineComment,
    CppTokenKind::BlockComment,
];

/// Is this token trivia (invisible to the grammar)?
pub fn is_trivia(kind: CppTokenKind) -> bool {
    TRIVIA_KINDS.contains(&kind)
}

/// The significant children of a node, with trivia skipped.
///
/// "Significant" means "not whitespace, newline, line splice or comment" — the tokens the grammar
/// actually sees.
pub fn significant_children(node: &CppSyntaxNode) -> impl Iterator<Item = CppSyntaxToken> {
    node.children_with_tokens()
        .filter_map(|it| it.into_token())
        .filter(|token| !is_trivia(token.kind().into()))
}

/// The token at a **byte offset**, if any: the one that starts there, or the one after it.
///
/// A helper rather than an expression at each call site, and the reason is the type: the tree's own offsets are
/// `TextSize`, which is `rowan`'s, so a caller outside this crate would have to depend on `rowan` to ask this
/// question at all. Asking "what token is under this byte" is a question about the tree, and the tree is here.
///
/// `None` past the last token. At a boundary between two tokens the one that *follows* is the answer, which is what
/// an editor wants: a cursor at the end of a word is at the start of whatever comes next, and the word it just left
/// is the one the user can see.
pub fn token_at(node: &CppSyntaxNode, offset: usize) -> Option<CppSyntaxToken> {
    // **An offset past the tree is not a token, and rowan asserts rather than answering.** `token_at_offset`
    // panics with "Bad offset: range 0..N offset M" for `M > N`, and that panic reached a language server as an
    // internal error on `textDocument/signatureHelp`: the request carried an offset in the file's coordinates while
    // the tree was a rendering (`#if` branches removed), so 1311 stood where the rendering had 953 bytes. A query
    // that cannot place its offset has no token to report, which is `None` — the same answer as an offset in the
    // middle of nothing.
    if offset > usize::from(node.text_range().end()) {
        return None;
    }

    let at = TextSize::from(u32::try_from(offset).ok()?);
    node.token_at_offset(at).right_biased()
}

/// The byte range covered by a run of tokens, or `None` for an empty run.
pub fn tokens_range(tokens: &[CppSyntaxToken]) -> Option<TextRange> {
    let first = tokens.first()?.text_range();
    let last = tokens.last()?.text_range();
    Some(TextRange::new(first.start(), last.end()))
}

/// Convert a rowan range into the parser's own range type.
///
/// A free function rather than a `From` impl: `SourceRange` lives in `crate::text` and `TextRange` is
/// rowan's, so the orphan rule forbids implementing the conversion from either side.
pub fn source_range(range: TextRange) -> crate::text::SourceRange {
    crate::text::SourceRange::new(
        u32::from(range.start()) as usize,
        u32::from(range.end() - range.start()) as usize,
    )
}
/// The first child node with one of `kinds`.
///
/// A companion to [`CppAstNode::child`] for the cases where "what kind is this?" is the question
/// being asked, so there is no `N` to infer and `child::<N>()` cannot be used.
pub fn first_child_of_kind(node: &CppSyntaxNode, kinds: &[CppSyntaxKind]) -> Option<CppSyntaxNode> {
    node.children()
        .find(|child| kinds.contains(&CppSyntaxKind::from(child.kind())))
}

/// The first significant token of a node, skipping trivia.
pub fn first_significant_token(node: &CppSyntaxNode) -> Option<CppSyntaxToken> {
    significant_children(node).next()
}

/// The text of a node's **whole subtree**, with trivia removed.
///
/// The token walkers in this module only see *direct* token children, which is the wrong answer for
/// a node whose content is itself a node: `DeclSpecifierSeq` holds a `BuiltinType` holding `int`,
/// so a token-only walk reports nothing at all. This descends instead.
///
/// Whitespace is dropped rather than collapsed, because the callers present these strings as a type
/// spelling — `const int * const` comes out as `constint*const` — so it is for display, and no
/// caller should re-lex the result.
pub fn subtree_text(node: &CppSyntaxNode) -> String {
    let mut out = String::new();
    collect_subtree_text(node, &mut out);
    out
}

fn collect_subtree_text(node: &CppSyntaxNode, out: &mut String) {
    for element in node.children_with_tokens() {
        match element {
            rowan::NodeOrToken::Node(child) => collect_subtree_text(&child, out),
            rowan::NodeOrToken::Token(token) => {
                if !is_trivia(token.kind().into()) {
                    out.push_str(token.text());
                }
            }
        }
    }
}

/// The text of a node's subtree, with whitespace collapsed to single spaces.
///
/// Like [`subtree_text`] but keeps one space between tokens, so `unsigned char` stays readable.
pub fn subtree_text_spaced(node: &CppSyntaxNode) -> String {
    // **The file's own spelling with runs of whitespace collapsed** — `std::vector<int>` stays one spelling and
    // `unsigned char` keeps its single space. Presentation rather than structure: a caller that needs to know what the type
    // *is* asks the typed accessors (`CppDeclSpecifierSeq::get_type_text`, `CppParam::get_type_text`), not this.
    let raw = node.text().to_string();
    raw.split_whitespace().collect::<Vec<_>>().join(" ")
}