#![forbid(
missing_debug_implementations,
unconditional_recursion,
future_incompatible,
missing_docs
)]
#![deny(unsafe_code)]
extern crate colosseum;
extern crate parking_lot;
extern crate smol_str;
extern crate text_unit;
mod green;
#[allow(unsafe_code)]
mod imp;
#[allow(unsafe_code)]
mod swap_cell;
use std::{
fmt,
hash::{Hash, Hasher},
ops::Range,
ptr,
};
pub use crate::{
green::{GreenNode, GreenNodeBuilder},
smol_str::SmolStr,
text_unit::{TextRange, TextUnit},
};
pub trait Types: Send + Sync + 'static {
type Kind: fmt::Debug + Copy + Eq + Send + Sync;
type RootData: fmt::Debug + Send + Sync;
}
pub use crate::imp::{TransparentNewType, TreeArc};
impl<T, N> Clone for TreeArc<T, N>
where
T: Types,
N: TransparentNewType<Repr = SyntaxNode<T>>,
{
fn clone(&self) -> TreeArc<T, N> {
let n: &N = &*self;
TreeArc::new(n)
}
}
impl<T, N> PartialEq<TreeArc<T, N>> for TreeArc<T, N>
where
T: Types,
N: TransparentNewType<Repr = SyntaxNode<T>>,
{
fn eq(&self, other: &TreeArc<T, N>) -> bool {
ptr::eq(self.inner, other.inner)
}
}
impl<T, N> Eq for TreeArc<T, N>
where
T: Types,
N: TransparentNewType<Repr = SyntaxNode<T>>,
{
}
impl<T, N> Hash for TreeArc<T, N>
where
T: Types,
N: TransparentNewType<Repr = SyntaxNode<T>>,
{
fn hash<H: Hasher>(&self, state: &mut H) {
self.inner.hash(state)
}
}
impl<T, N> std::borrow::Borrow<N> for TreeArc<T, N>
where
T: Types,
N: TransparentNewType<Repr = SyntaxNode<T>>,
{
fn borrow(&self) -> &N {
&*self
}
}
pub use crate::imp::SyntaxNode;
impl<T: Types> fmt::Debug for SyntaxNode<T> {
fn fmt(&self, fmt: &mut fmt::Formatter) -> fmt::Result {
write!(fmt, "{:?}@{:?}", self.kind(), self.range())
}
}
impl<T: Types> fmt::Display for SyntaxNode<T> {
fn fmt(&self, fmt: &mut fmt::Formatter) -> fmt::Result {
self.preorder()
.filter_map(|event| match event {
WalkEvent::Enter(node) => Some(node),
_ => None,
})
.filter_map(|it| it.leaf_text())
.try_for_each(|it| write!(fmt, "{}", it))
}
}
impl<T: Types> PartialEq<SyntaxNode<T>> for SyntaxNode<T> {
fn eq(&self, other: &SyntaxNode<T>) -> bool {
ptr::eq(self, other)
}
}
impl<T: Types> Eq for SyntaxNode<T> {}
impl<T: Types> Hash for SyntaxNode<T> {
fn hash<H: Hasher>(&self, state: &mut H) {
(self as *const SyntaxNode<T>).hash(state)
}
}
impl<T, N> fmt::Debug for TreeArc<T, N>
where
T: Types,
N: TransparentNewType<Repr = SyntaxNode<T>> + fmt::Debug,
{
fn fmt(&self, fmt: &mut fmt::Formatter) -> fmt::Result {
let inner: &N = &*self;
fmt::Debug::fmt(inner, fmt)
}
}
#[derive(Debug, Copy, Clone)]
pub enum WalkEvent<T> {
Enter(T),
Leave(T),
}
#[derive(Clone, Debug)]
pub enum LeafAtOffset<T> {
None,
Single(T),
Between(T, T),
}
impl<T> LeafAtOffset<T> {
pub fn right_biased(self) -> Option<T> {
match self {
LeafAtOffset::None => None,
LeafAtOffset::Single(node) => Some(node),
LeafAtOffset::Between(_, right) => Some(right),
}
}
pub fn left_biased(self) -> Option<T> {
match self {
LeafAtOffset::None => None,
LeafAtOffset::Single(node) => Some(node),
LeafAtOffset::Between(left, _) => Some(left),
}
}
}
impl<T> Iterator for LeafAtOffset<T> {
type Item = T;
fn next(&mut self) -> Option<T> {
match std::mem::replace(self, LeafAtOffset::None) {
LeafAtOffset::None => None,
LeafAtOffset::Single(node) => {
*self = LeafAtOffset::None;
Some(node)
}
LeafAtOffset::Between(left, right) => {
*self = LeafAtOffset::Single(right);
Some(left)
}
}
}
}
impl<T: Types> ToOwned for SyntaxNode<T> {
type Owned = TreeArc<T, SyntaxNode<T>>;
fn to_owned(&self) -> TreeArc<T, SyntaxNode<T>> {
TreeArc::new(self)
}
}
impl<T: Types> SyntaxNode<T> {
pub fn new(green: GreenNode<T>, data: T::RootData) -> TreeArc<T, SyntaxNode<T>> {
Self::new_root(green, data)
}
pub fn green(&self) -> &GreenNode<T> {
&self.green
}
pub fn replace_children(&self, children: Box<[GreenNode<T>]>) -> GreenNode<T> {
self.replace_self(GreenNode::new_branch(self.kind(), children))
}
pub fn replace_self(&self, green: GreenNode<T>) -> GreenNode<T> {
assert_eq!(self.kind(), green.kind());
match self.parent() {
None => green,
Some(parent) => {
let children: Vec<_> = parent
.children()
.map(|child| {
if child == self {
green.clone()
} else {
child.green.clone()
}
})
.collect();
let new_parent = GreenNode::new_branch(parent.kind(), children.into_boxed_slice());
parent.replace_self(new_parent)
}
}
}
pub fn is_leaf(&self) -> bool {
self.green.leaf_text().is_some()
}
pub fn leaf_text<'a>(&'a self) -> Option<&'a SmolStr> {
self.green.leaf_text()
}
pub fn root_data(&self) -> &T::RootData {
&self.root().data
}
pub fn kind(&self) -> T::Kind {
self.green.kind()
}
pub fn range(&self) -> TextRange {
TextRange::offset_len(self.start_offset(), self.green.text_len())
}
pub fn parent(&self) -> Option<&SyntaxNode<T>> {
self.parent_impl()
}
pub fn first_child(&self) -> Option<&SyntaxNode<T>> {
self.get_child(0)
}
pub fn last_child(&self) -> Option<&SyntaxNode<T>> {
let n = self.n_children();
let n = n.checked_sub(1)?;
self.get_child(n)
}
pub fn next_sibling(&self) -> Option<&SyntaxNode<T>> {
let parent = self.parent()?;
let next_sibling_idx = self.index_in_parent()? + 1;
parent.get_child(next_sibling_idx)
}
pub fn prev_sibling(&self) -> Option<&SyntaxNode<T>> {
let parent = self.parent()?;
let prev_sibling_idx = self.index_in_parent()?.checked_sub(1)?;
parent.get_child(prev_sibling_idx)
}
pub fn children(&self) -> SyntaxNodeChildren<T> {
SyntaxNodeChildren {
parent: self,
iter: (0..self.n_children()),
}
}
pub fn ancestors(&self) -> impl Iterator<Item = &SyntaxNode<T>> {
generate(Some(self), |node| node.parent())
}
pub fn preorder(&self) -> impl Iterator<Item = WalkEvent<&SyntaxNode<T>>> {
generate(Some(WalkEvent::Enter(self)), move |pos| {
let next = match *pos {
WalkEvent::Enter(node) => match node.first_child() {
Some(child) => WalkEvent::Enter(child),
None => WalkEvent::Leave(node),
},
WalkEvent::Leave(node) => {
if node == self {
return None;
}
match node.next_sibling() {
Some(sibling) => WalkEvent::Enter(sibling),
None => WalkEvent::Leave(node.parent().unwrap()),
}
}
};
Some(next)
})
}
pub fn common_ancestor<'a>(&'a self, other: &'a SyntaxNode<T>) -> &'a SyntaxNode<T> {
for p in self.ancestors() {
if other.ancestors().any(|a| a == p) {
return p;
}
}
panic!("No common ancestor for {:?} and {:?}", self, other)
}
pub fn leaf_at_offset(&self, offset: TextUnit) -> LeafAtOffset<&SyntaxNode<T>> {
let range = self.range();
assert!(
range.start() <= offset && offset <= range.end(),
"Bad offset: range {:?} offset {:?}",
range,
offset
);
if range.is_empty() {
return LeafAtOffset::None;
}
if self.is_leaf() {
return LeafAtOffset::Single(self);
}
let mut children = self.children().filter(|child| {
let child_range = child.range();
!child_range.is_empty()
&& (child_range.start() <= offset && offset <= child_range.end())
});
let left = children.next().unwrap();
let right = children.next();
assert!(children.next().is_none());
if let Some(right) = right {
match (left.leaf_at_offset(offset), right.leaf_at_offset(offset)) {
(LeafAtOffset::Single(left), LeafAtOffset::Single(right)) => {
LeafAtOffset::Between(left, right)
}
_ => unreachable!(),
}
} else {
left.leaf_at_offset(offset)
}
}
pub fn covering_node(&self, range: TextRange) -> &SyntaxNode<T> {
let mut res = self;
loop {
assert!(
range.is_subrange(&res.range()),
"Bad range: node range {:?}, range {:?}",
res.range(),
range,
);
res = match res
.children()
.find(|child| range.is_subrange(&child.range()))
{
Some(child) => child,
None => return res,
}
}
}
pub fn memory_size_of_subtree(&self) -> usize {
std::mem::size_of::<Self>()
+ self.green().memory_size_of_subtree()
+ self.memory_size_of_red_children()
}
pub(crate) fn start_offset(&self) -> TextUnit {
match &self.parent {
None => 0.into(),
Some(p) => p.start_offset,
}
}
pub(crate) fn n_children(&self) -> usize {
self.green.children().len()
}
pub(crate) fn index_in_parent(&self) -> Option<usize> {
Some(self.parent.as_ref()?.index_in_parent as usize)
}
}
#[derive(Debug)]
pub struct SyntaxNodeChildren<'a, T: Types> {
parent: &'a SyntaxNode<T>,
iter: Range<usize>,
}
impl<'a, T: Types> Iterator for SyntaxNodeChildren<'a, T> {
type Item = &'a SyntaxNode<T>;
fn next(&mut self) -> Option<&'a SyntaxNode<T>> {
self.iter.next().map(|i| self.parent.get_child(i).unwrap())
}
}
fn generate<'a, T: 'a, F: Fn(&T) -> Option<T> + 'a>(
seed: Option<T>,
step: F,
) -> impl Iterator<Item = T> + 'a {
std::iter::repeat(()).scan(seed, move |state, ()| {
state.take().map(|curr| {
*state = step(&curr);
curr
})
})
}
#[cfg(test)]
mod tests {
use super::*;
#[derive(Clone, Copy)]
enum SillyTypes {}
impl Types for SillyTypes {
type Kind = u8;
type RootData = ();
}
#[test]
fn assert_send_sync() {
fn f<T: Send + Sync>() {}
f::<GreenNode<SillyTypes>>();
f::<SyntaxNode<SillyTypes>>();
f::<TreeArc<SillyTypes, SyntaxNode<SillyTypes>>>();
}
}