use rowan::{GreenNode, NodeCache};
use crate::{
kind::{CppSyntaxKind, CppTokenKind},
text::SourceRange,
};
#[derive(Debug, Clone, Default)]
enum CppGreenElement {
Node {
kind: CppSyntaxKind,
children: Vec<usize>,
},
Token {
kind: CppTokenKind,
range: SourceRange,
},
#[default]
Gap,
}
#[derive(Default, Debug)]
pub struct CppGreenNodeBuilder<'cache> {
open_nodes: Vec<(CppSyntaxKind, usize)>,
elements: Vec<CppGreenElement>,
children: Vec<usize>,
roots: Vec<usize>,
builder: rowan::GreenNodeBuilder<'cache>,
}
impl CppGreenNodeBuilder<'_> {
pub fn new() -> CppGreenNodeBuilder<'static> {
CppGreenNodeBuilder::default()
}
pub fn with_cache(cache: &mut NodeCache) -> CppGreenNodeBuilder<'_> {
CppGreenNodeBuilder {
open_nodes: Vec::new(),
elements: Vec::new(),
children: Vec::new(),
roots: Vec::new(),
builder: rowan::GreenNodeBuilder::with_cache(cache),
}
}
#[inline]
pub fn token(&mut self, kind: CppTokenKind, range: SourceRange) {
let at = self.elements.len();
self.elements.push(CppGreenElement::Token { kind, range });
self.children.push(at);
}
#[inline]
pub fn start_node(&mut self, kind: CppSyntaxKind) {
let at = self.children.len();
self.open_nodes.push((kind, at));
}
#[inline]
pub fn finish_node(&mut self) {
let Some((kind, recorded_start)) = self.open_nodes.pop() else {
debug_assert!(false, "finish_node called with no open node");
return;
};
let mut child_start = recorded_start;
let mut child_end = self.children.len().saturating_sub(1);
let child_count = self.children.len();
match kind {
CppSyntaxKind::CompoundStat | CppSyntaxKind::TranslationUnit => {
while child_start > 0 && self.is_layout(self.children[child_start - 1]) {
child_start -= 1;
}
}
CppSyntaxKind::DocComment
| CppSyntaxKind::LineComment
| CppSyntaxKind::BlockComment => {
while child_start < child_count && self.is_layout(self.children[child_start]) {
child_start += 1;
}
while child_end > child_start && self.is_layout(self.children[child_end]) {
child_end -= 1;
}
}
_ => {
while child_start < child_count && self.is_layout(self.children[child_start]) {
child_start += 1;
}
while child_end > child_start && self.is_layout(self.children[child_end]) {
child_end -= 1;
}
}
}
let children: Vec<usize> = if child_start <= child_end && !self.children.is_empty() {
self.children.drain(child_start..=child_end).collect()
} else {
Vec::new()
};
let at = self.elements.len();
self.elements.push(CppGreenElement::Node { kind, children });
self.children.insert(child_start, at);
debug_assert!(
self.is_ordered(),
"the children list is no longer in document order after finishing {kind:?}"
);
}
#[allow(dead_code)]
fn is_ordered(&self) -> bool {
let mut previous = None;
for at in &self.children {
let Some(start) = self.starts_at(*at) else {
continue;
};
if previous.is_some_and(|before| before > start) {
return false;
}
previous = Some(start);
}
true
}
#[allow(dead_code)]
fn starts_at(&self, at: usize) -> Option<usize> {
match self.elements.get(at) {
Some(CppGreenElement::Token { range, .. }) => Some(range.start_offset),
Some(CppGreenElement::Node { children, .. }) => {
children.first().and_then(|first| self.starts_at(*first))
}
_ => None,
}
}
#[cfg(test)]
fn is_layout_of(&self, element: &CppGreenElement) -> bool {
matches!(
element,
CppGreenElement::Token {
kind: CppTokenKind::Whitespace
| CppTokenKind::Newline
| CppTokenKind::LineContinuation
| CppTokenKind::None,
..
}
)
}
fn is_layout(&self, at: usize) -> bool {
matches!(
self.elements.get(at),
Some(CppGreenElement::Token {
kind: CppTokenKind::Whitespace
| CppTokenKind::Newline
| CppTokenKind::LineContinuation
| CppTokenKind::None,
..
})
)
}
pub fn open_node_count(&self) -> usize {
self.open_nodes.len()
}
#[inline]
pub fn finish(mut self, text: &str) -> GreenNode {
debug_assert!(
self.open_nodes.is_empty(),
"finishing a green tree with {} node(s) still open; the tree would be wrongly nested",
self.open_nodes.len()
);
while !self.open_nodes.is_empty() {
self.finish_node();
}
self.roots = std::mem::take(&mut self.children);
let already_rooted = matches!(
self.roots.as_slice(),
[at] if matches!(self.elements.get(*at), Some(CppGreenElement::Node {
kind: CppSyntaxKind::TranslationUnit,
..
}))
);
let mut elements = std::mem::take(&mut self.elements);
if already_rooted {
let root = self.roots.pop().expect("checked just above");
emit_element(&mut self.builder, &mut elements, root, text);
} else {
self.builder
.start_node(CppSyntaxKind::TranslationUnit.into());
for root in std::mem::take(&mut self.roots) {
emit_element(&mut self.builder, &mut elements, root, text);
}
self.builder.finish_node();
}
self.builder.finish()
}
}
fn emit_element(
builder: &mut rowan::GreenNodeBuilder<'_>,
elements: &mut [CppGreenElement],
at: usize,
text: &str,
) {
let element = std::mem::take(&mut elements[at]);
match element {
CppGreenElement::Node { kind, children } => {
builder.start_node(kind.into());
for child in children {
emit_element(builder, elements, child, text);
}
builder.finish_node();
}
CppGreenElement::Token { kind, range } => {
let start = range.start_offset;
let end = range.end_offset();
builder.token(kind.into(), &text[start..end]);
}
CppGreenElement::Gap => {}
}
}
#[cfg(test)]
mod tests {
use super::*;
#[cfg(test)]
fn is_a_comment(element: &CppGreenElement) -> bool {
match element {
CppGreenElement::Node { kind, .. } => matches!(
kind,
CppSyntaxKind::DocComment
| CppSyntaxKind::LineComment
| CppSyntaxKind::BlockComment
),
CppGreenElement::Token { kind, .. } => {
matches!(kind, CppTokenKind::LineComment | CppTokenKind::BlockComment)
}
CppGreenElement::Gap => false,
}
}
fn shape(node: &rowan::GreenNodeData) -> String {
let mut out = String::new();
for child in node.children() {
match child {
rowan::NodeOrToken::Node(n) => {
out.push_str(&format!("{:?}(", n.kind()));
out.push_str(&shape(n));
out.push(')');
}
rowan::NodeOrToken::Token(t) => out.push_str(&format!("{:?}", t.text())),
}
}
out
}
#[test]
fn nests_children_under_their_node() {
let text = "ab";
let mut builder = CppGreenNodeBuilder::new();
builder.start_node(CppSyntaxKind::TranslationUnit);
builder.token(CppTokenKind::Identifier, SourceRange::new(0, 1));
builder.start_node(CppSyntaxKind::DeclStat);
builder.token(CppTokenKind::Identifier, SourceRange::new(1, 1));
builder.finish_node();
builder.finish_node();
let green = builder.finish(text);
assert_eq!(
shape(&green),
format!(
"\"a\"{:?}(\"b\")",
rowan::SyntaxKind::from(CppSyntaxKind::DeclStat)
),
"children were not nested under their node"
);
assert_eq!(green.kind(), CppSyntaxKind::TranslationUnit.into());
}
#[test]
fn a_node_gives_its_trailing_layout_back() {
let text = "a; \n";
let mut builder = CppGreenNodeBuilder::new();
builder.start_node(CppSyntaxKind::TranslationUnit);
builder.start_node(CppSyntaxKind::Declaration);
builder.token(CppTokenKind::Identifier, SourceRange::new(0, 1));
builder.token(CppTokenKind::Semicolon, SourceRange::new(1, 1));
builder.token(CppTokenKind::Whitespace, SourceRange::new(2, 2));
builder.token(CppTokenKind::Newline, SourceRange::new(4, 1));
builder.finish_node();
builder.finish_node();
let green = builder.finish(text);
let declaration = green
.children()
.find_map(|child| match child {
rowan::NodeOrToken::Node(node)
if node.kind() == CppSyntaxKind::Declaration.into() =>
{
Some(node)
}
_ => None,
})
.expect("the declaration");
assert_eq!(
declaration.to_string(),
"a;",
"the `;` is this node's own token and the whitespace after it is not"
);
assert_eq!(
green.to_string(),
text,
"giving the layout back must not drop it"
);
}
#[test]
fn a_block_comes_forward_over_the_layout_before_it() {
let text = " { a }";
let mut builder = CppGreenNodeBuilder::new();
builder.start_node(CppSyntaxKind::TranslationUnit);
builder.token(CppTokenKind::Whitespace, SourceRange::new(0, 2));
builder.start_node(CppSyntaxKind::CompoundStat);
builder.token(CppTokenKind::LeftBrace, SourceRange::new(2, 1));
builder.token(CppTokenKind::Whitespace, SourceRange::new(3, 1));
builder.token(CppTokenKind::Identifier, SourceRange::new(4, 1));
builder.token(CppTokenKind::Whitespace, SourceRange::new(5, 1));
builder.token(CppTokenKind::RightBrace, SourceRange::new(6, 1));
builder.finish_node();
builder.finish_node();
let green = builder.finish(text);
let block = green
.children()
.find_map(|child| match child {
rowan::NodeOrToken::Node(node)
if node.kind() == CppSyntaxKind::CompoundStat.into() =>
{
Some(node)
}
_ => None,
})
.expect("the block");
assert_eq!(
block.to_string(),
" { a }",
"the whitespace before the block is the block's, not the root's"
);
assert_eq!(green.to_string(), text);
}
#[test]
fn a_comment_is_content_and_layout_is_not() {
for kind in [
CppSyntaxKind::DocComment,
CppSyntaxKind::LineComment,
CppSyntaxKind::BlockComment,
] {
let comment = CppGreenElement::Node {
kind,
children: Vec::new(),
};
assert!(is_a_comment(&comment), "{kind:?} is a comment");
assert!(
!CppGreenNodeBuilder::new().is_layout_of(&comment),
"{kind:?} is not layout"
);
}
for kind in [CppTokenKind::LineComment, CppTokenKind::BlockComment] {
let bare = CppGreenElement::Token {
kind,
range: SourceRange::new(0, 4),
};
assert!(is_a_comment(&bare), "{kind:?} is a comment");
assert!(
!CppGreenNodeBuilder::new().is_layout_of(&bare),
"{kind:?} is not layout"
);
}
for kind in [
CppTokenKind::Whitespace,
CppTokenKind::Newline,
CppTokenKind::LineContinuation,
] {
let layout = CppGreenElement::Token {
kind,
range: SourceRange::new(0, 1),
};
assert!(
CppGreenNodeBuilder::new().is_layout_of(&layout),
"{kind:?} is layout"
);
assert!(!is_a_comment(&layout), "{kind:?} is not a comment");
}
}
#[test]
fn wraps_bare_tokens_in_a_translation_unit() {
let text = "int x;";
let mut builder = CppGreenNodeBuilder::new();
builder.token(CppTokenKind::IntKeyword, SourceRange::new(0, 3));
builder.token(CppTokenKind::Whitespace, SourceRange::new(3, 1));
builder.token(CppTokenKind::Identifier, SourceRange::new(4, 1));
builder.token(CppTokenKind::Semicolon, SourceRange::new(5, 1));
let green = builder.finish(text);
assert_eq!(green.kind(), CppSyntaxKind::TranslationUnit.into());
assert_eq!(usize::from(green.text_len()), text.len());
assert_eq!(green.children().len(), 4);
}
#[test]
fn does_not_double_wrap_an_existing_root() {
let text = "int";
let mut builder = CppGreenNodeBuilder::new();
builder.start_node(CppSyntaxKind::TranslationUnit);
builder.token(CppTokenKind::IntKeyword, SourceRange::new(0, 3));
builder.finish_node();
let green = builder.finish(text);
assert_eq!(green.kind(), CppSyntaxKind::TranslationUnit.into());
assert_eq!(shape(&green), r#""int""#);
}
#[test]
fn empty_input_still_yields_a_root() {
let green = CppGreenNodeBuilder::new().finish("");
assert_eq!(green.kind(), CppSyntaxKind::TranslationUnit.into());
assert_eq!(green.children().len(), 0);
}
#[test]
fn multiple_roots_are_wrapped_in_order() {
let text = "ab";
let mut builder = CppGreenNodeBuilder::new();
builder.token(CppTokenKind::Identifier, SourceRange::new(0, 1));
builder.start_node(CppSyntaxKind::DeclStat);
builder.token(CppTokenKind::Identifier, SourceRange::new(1, 1));
builder.finish_node();
let green = builder.finish(text);
assert_eq!(
shape(&green),
format!(
"\"a\"{:?}(\"b\")",
rowan::SyntaxKind::from(CppSyntaxKind::DeclStat)
)
);
}
}