aboutsummaryrefslogtreecommitdiff
path: root/crates/libsyntax2/src/yellow
diff options
context:
space:
mode:
Diffstat (limited to 'crates/libsyntax2/src/yellow')
-rw-r--r--crates/libsyntax2/src/yellow/builder.rs65
-rw-r--r--crates/libsyntax2/src/yellow/green.rs95
-rw-r--r--crates/libsyntax2/src/yellow/mod.rs62
-rw-r--r--crates/libsyntax2/src/yellow/red.rs94
-rw-r--r--crates/libsyntax2/src/yellow/syntax.rs122
5 files changed, 438 insertions, 0 deletions
diff --git a/crates/libsyntax2/src/yellow/builder.rs b/crates/libsyntax2/src/yellow/builder.rs
new file mode 100644
index 000000000..5e94e5055
--- /dev/null
+++ b/crates/libsyntax2/src/yellow/builder.rs
@@ -0,0 +1,65 @@
1use {
2 parser_impl::Sink,
3 yellow::{GreenNode, SyntaxError, SyntaxNode, SyntaxRoot},
4 SyntaxKind, TextRange, TextUnit,
5};
6
7pub(crate) struct GreenBuilder<'a> {
8 text: &'a str,
9 parents: Vec<(SyntaxKind, usize)>,
10 children: Vec<GreenNode>,
11 pos: TextUnit,
12 errors: Vec<SyntaxError>,
13}
14
15impl<'a> Sink<'a> for GreenBuilder<'a> {
16 type Tree = SyntaxNode;
17
18 fn new(text: &'a str) -> Self {
19 GreenBuilder {
20 text,
21 parents: Vec::new(),
22 children: Vec::new(),
23 pos: 0.into(),
24 errors: Vec::new(),
25 }
26 }
27
28 fn leaf(&mut self, kind: SyntaxKind, len: TextUnit) {
29 let range = TextRange::offset_len(self.pos, len);
30 self.pos += len;
31 let text = &self.text[range];
32 self.children.push(
33 GreenNode::new_leaf(kind, text)
34 );
35 }
36
37 fn start_internal(&mut self, kind: SyntaxKind) {
38 let len = self.children.len();
39 self.parents.push((kind, len));
40 }
41
42 fn finish_internal(&mut self) {
43 let (kind, first_child) = self.parents.pop().unwrap();
44 let children: Vec<_> = self.children
45 .drain(first_child..)
46 .collect();
47 self.children.push(
48 GreenNode::new_branch(kind, children.into_boxed_slice())
49 );
50 }
51
52 fn error(&mut self, message: String) {
53 self.errors.push(SyntaxError {
54 msg: message,
55 offset: self.pos,
56 })
57 }
58
59 fn finish(mut self) -> SyntaxNode {
60 assert_eq!(self.children.len(), 1);
61 let root = self.children.pop().unwrap();
62 let root = SyntaxRoot::new(root, self.errors);
63 SyntaxNode::new_owned(root)
64 }
65}
diff --git a/crates/libsyntax2/src/yellow/green.rs b/crates/libsyntax2/src/yellow/green.rs
new file mode 100644
index 000000000..f505b26d7
--- /dev/null
+++ b/crates/libsyntax2/src/yellow/green.rs
@@ -0,0 +1,95 @@
1use std::sync::Arc;
2use {
3 SyntaxKind, TextUnit,
4 smol_str::SmolStr,
5};
6
7#[derive(Clone, Debug)]
8pub(crate) enum GreenNode {
9 Leaf {
10 kind: SyntaxKind,
11 text: SmolStr,
12 },
13 Branch(Arc<GreenBranch>),
14}
15
16impl GreenNode {
17 pub(crate) fn new_leaf(kind: SyntaxKind, text: &str) -> GreenNode {
18 GreenNode::Leaf { kind, text: SmolStr::new(text) }
19 }
20
21 pub(crate) fn new_branch(kind: SyntaxKind, children: Box<[GreenNode]>) -> GreenNode {
22 GreenNode::Branch(Arc::new(GreenBranch::new(kind, children)))
23 }
24
25 pub fn kind(&self) -> SyntaxKind {
26 match self {
27 GreenNode::Leaf { kind, .. } => *kind,
28 GreenNode::Branch(b) => b.kind(),
29 }
30 }
31
32 pub fn text_len(&self) -> TextUnit {
33 match self {
34 GreenNode::Leaf { text, ..} => TextUnit::of_str(text.as_str()),
35 GreenNode::Branch(b) => b.text_len(),
36 }
37 }
38
39 pub fn children(&self) -> &[GreenNode] {
40 match self {
41 GreenNode::Leaf { .. } => &[],
42 GreenNode::Branch(b) => b.children(),
43 }
44 }
45
46 pub fn text(&self) -> String {
47 let mut buff = String::new();
48 go(self, &mut buff);
49 return buff;
50 fn go(node: &GreenNode, buff: &mut String) {
51 match node {
52 GreenNode::Leaf { text, .. } => buff.push_str(text.as_str()),
53 GreenNode::Branch(b) => b.children().iter().for_each(|child| go(child, buff)),
54 }
55 }
56 }
57}
58
59#[derive(Clone, Debug)]
60pub(crate) struct GreenBranch {
61 text_len: TextUnit,
62 kind: SyntaxKind,
63 children: Box<[GreenNode]>,
64}
65
66impl GreenBranch {
67 fn new(kind: SyntaxKind, children: Box<[GreenNode]>) -> GreenBranch {
68 let text_len = children.iter().map(|x| x.text_len()).sum::<TextUnit>();
69 GreenBranch {
70 text_len,
71 kind,
72 children,
73 }
74 }
75
76 pub fn kind(&self) -> SyntaxKind {
77 self.kind
78 }
79
80 pub fn text_len(&self) -> TextUnit {
81 self.text_len
82 }
83
84 pub fn children(&self) -> &[GreenNode] {
85 &*self.children
86 }
87}
88
89#[test]
90fn test_sizes() {
91 use std::mem::size_of;
92 println!("GreenBranch = {}", size_of::<GreenBranch>());
93 println!("GreenNode = {}", size_of::<GreenNode>());
94 println!("SmolStr = {}", size_of::<SmolStr>());
95}
diff --git a/crates/libsyntax2/src/yellow/mod.rs b/crates/libsyntax2/src/yellow/mod.rs
new file mode 100644
index 000000000..ff3bb221b
--- /dev/null
+++ b/crates/libsyntax2/src/yellow/mod.rs
@@ -0,0 +1,62 @@
1mod builder;
2mod green;
3mod red;
4mod syntax;
5
6use std::{
7 ops::Deref,
8 sync::Arc,
9 ptr,
10};
11pub use self::syntax::{SyntaxNode, SyntaxNodeRef, SyntaxError};
12pub(crate) use self::{
13 builder::GreenBuilder,
14 green::GreenNode,
15 red::RedNode,
16};
17
18pub trait TreeRoot: Deref<Target=SyntaxRoot> + Clone + Send + Sync {}
19
20#[derive(Debug)]
21pub struct SyntaxRoot {
22 red: RedNode,
23 pub(crate) errors: Vec<SyntaxError>,
24}
25
26impl TreeRoot for Arc<SyntaxRoot> {}
27
28impl<'a> TreeRoot for &'a SyntaxRoot {}
29
30impl SyntaxRoot {
31 pub(crate) fn new(green: GreenNode, errors: Vec<SyntaxError>) -> SyntaxRoot {
32 SyntaxRoot {
33 red: RedNode::new_root(green),
34 errors,
35 }
36 }
37}
38
39#[derive(Clone, Copy, PartialEq, Eq, Debug)]
40pub(crate) struct RedPtr(ptr::NonNull<RedNode>);
41
42unsafe impl Send for RedPtr {}
43
44unsafe impl Sync for RedPtr {}
45
46impl RedPtr {
47 fn new(red: &RedNode) -> RedPtr {
48 RedPtr(red.into())
49 }
50
51 unsafe fn get<'a>(self, _root: &'a impl TreeRoot) -> &'a RedNode {
52 &*self.0.as_ptr()
53 }
54}
55
56#[test]
57fn assert_send_sync() {
58 fn f<T: Send + Sync>() {}
59 f::<GreenNode>();
60 f::<RedNode>();
61 f::<SyntaxNode>();
62}
diff --git a/crates/libsyntax2/src/yellow/red.rs b/crates/libsyntax2/src/yellow/red.rs
new file mode 100644
index 000000000..13ad44c65
--- /dev/null
+++ b/crates/libsyntax2/src/yellow/red.rs
@@ -0,0 +1,94 @@
1use parking_lot::RwLock;
2use {yellow::{GreenNode, RedPtr}, TextUnit};
3
4#[derive(Debug)]
5pub(crate) struct RedNode {
6 green: GreenNode,
7 parent: Option<ParentData>,
8 children: RwLock<Box<[Option<RedNode>]>>,
9}
10
11#[derive(Debug)]
12struct ParentData {
13 parent: RedPtr,
14 start_offset: TextUnit,
15 index_in_parent: usize,
16}
17
18impl RedNode {
19 pub fn new_root(green: GreenNode) -> RedNode {
20 RedNode::new(green, None)
21 }
22
23 fn new_child(
24 green: GreenNode,
25 parent: RedPtr,
26 start_offset: TextUnit,
27 index_in_parent: usize,
28 ) -> RedNode {
29 let parent_data = ParentData {
30 parent,
31 start_offset,
32 index_in_parent,
33 };
34 RedNode::new(green, Some(parent_data))
35 }
36
37 fn new(green: GreenNode, parent: Option<ParentData>) -> RedNode {
38 let n_children = green.children().len();
39 let children = (0..n_children)
40 .map(|_| None)
41 .collect::<Vec<_>>()
42 .into_boxed_slice();
43 RedNode {
44 green,
45 parent,
46 children: RwLock::new(children),
47 }
48 }
49
50 pub(crate) fn green(&self) -> &GreenNode {
51 &self.green
52 }
53
54 pub(crate) fn start_offset(&self) -> TextUnit {
55 match &self.parent {
56 None => 0.into(),
57 Some(p) => p.start_offset,
58 }
59 }
60
61 pub(crate) fn n_children(&self) -> usize {
62 self.green.children().len()
63 }
64
65 pub(crate) fn get_child(&self, idx: usize) -> Option<RedPtr> {
66 if idx >= self.n_children() {
67 return None;
68 }
69 match &self.children.read()[idx] {
70 Some(child) => return Some(RedPtr::new(child)),
71 None => (),
72 };
73 let green_children = self.green.children();
74 let start_offset = self.start_offset()
75 + green_children[..idx]
76 .iter()
77 .map(|x| x.text_len())
78 .sum::<TextUnit>();
79 let child =
80 RedNode::new_child(green_children[idx].clone(), RedPtr::new(self), start_offset, idx);
81 let mut children = self.children.write();
82 if children[idx].is_none() {
83 children[idx] = Some(child)
84 }
85 Some(RedPtr::new(children[idx].as_ref().unwrap()))
86 }
87
88 pub(crate) fn parent(&self) -> Option<RedPtr> {
89 Some(self.parent.as_ref()?.parent)
90 }
91 pub(crate) fn index_in_parent(&self) -> Option<usize> {
92 Some(self.parent.as_ref()?.index_in_parent)
93 }
94}
diff --git a/crates/libsyntax2/src/yellow/syntax.rs b/crates/libsyntax2/src/yellow/syntax.rs
new file mode 100644
index 000000000..6e33310f1
--- /dev/null
+++ b/crates/libsyntax2/src/yellow/syntax.rs
@@ -0,0 +1,122 @@
1use std::{fmt, sync::Arc};
2
3use {
4 yellow::{RedNode, TreeRoot, SyntaxRoot, RedPtr},
5 SyntaxKind::{self, *},
6 TextRange, TextUnit,
7};
8
9
10#[derive(Clone, Copy)]
11pub struct SyntaxNode<R: TreeRoot = Arc<SyntaxRoot>> {
12 pub(crate) root: R,
13 // Guaranteed to not dangle, because `root` holds a
14 // strong reference to red's ancestor
15 red: RedPtr,
16}
17
18unsafe impl<R: TreeRoot> Send for SyntaxNode<R> {}
19unsafe impl<R: TreeRoot> Sync for SyntaxNode<R> {}
20
21impl<R1: TreeRoot, R2: TreeRoot> PartialEq<SyntaxNode<R1>> for SyntaxNode<R2> {
22 fn eq(&self, other: &SyntaxNode<R1>) -> bool {
23 self.red == other.red
24 }
25}
26
27impl<R: TreeRoot> Eq for SyntaxNode<R> {}
28
29pub type SyntaxNodeRef<'a> = SyntaxNode<&'a SyntaxRoot>;
30
31#[derive(Debug, Clone, PartialEq, Eq, Hash, Ord, PartialOrd)]
32pub struct SyntaxError {
33 pub msg: String,
34 pub offset: TextUnit,
35}
36
37impl SyntaxNode<Arc<SyntaxRoot>> {
38 pub(crate) fn new_owned(root: SyntaxRoot) -> Self {
39 let root = Arc::new(root);
40 let red = RedPtr::new(&root.red);
41 SyntaxNode { root, red }
42 }
43}
44
45impl<R: TreeRoot> SyntaxNode<R> {
46 pub fn as_ref<'a>(&'a self) -> SyntaxNode<&'a SyntaxRoot> {
47 SyntaxNode {
48 root: &*self.root,
49 red: self.red,
50 }
51 }
52
53 pub fn kind(&self) -> SyntaxKind {
54 self.red().green().kind()
55 }
56
57 pub fn range(&self) -> TextRange {
58 let red = self.red();
59 TextRange::offset_len(red.start_offset(), red.green().text_len())
60 }
61
62 pub fn text(&self) -> String {
63 self.red().green().text()
64 }
65
66 pub fn children<'a>(&'a self) -> impl Iterator<Item = SyntaxNode<R>> + 'a {
67 let red = self.red();
68 let n_children = red.n_children();
69 (0..n_children).map(move |i| SyntaxNode {
70 root: self.root.clone(),
71 red: red.get_child(i).unwrap(),
72 })
73 }
74
75 pub fn parent(&self) -> Option<SyntaxNode<R>> {
76 let parent = self.red().parent()?;
77 Some(SyntaxNode {
78 root: self.root.clone(),
79 red: parent,
80 })
81 }
82
83 pub fn first_child(&self) -> Option<SyntaxNode<R>> {
84 self.children().next()
85 }
86
87 pub fn next_sibling(&self) -> Option<SyntaxNode<R>> {
88 let red = self.red();
89 let parent = self.parent()?;
90 let next_sibling_idx = red.index_in_parent()? + 1;
91 let sibling_red = parent.red().get_child(next_sibling_idx)?;
92 Some(SyntaxNode {
93 root: self.root.clone(),
94 red: sibling_red,
95 })
96 }
97
98 pub fn is_leaf(&self) -> bool {
99 self.first_child().is_none()
100 }
101
102 fn red(&self) -> &RedNode {
103 unsafe { self.red.get(&self.root) }
104 }
105}
106
107impl<R: TreeRoot> fmt::Debug for SyntaxNode<R> {
108 fn fmt(&self, fmt: &mut fmt::Formatter) -> fmt::Result {
109 write!(fmt, "{:?}@{:?}", self.kind(), self.range())?;
110 if has_short_text(self.kind()) {
111 write!(fmt, " \"{}\"", self.text())?;
112 }
113 Ok(())
114 }
115}
116
117fn has_short_text(kind: SyntaxKind) -> bool {
118 match kind {
119 IDENT | LIFETIME | INT_NUMBER | FLOAT_NUMBER => true,
120 _ => false,
121 }
122}