From 698f8c2f01ea549d77d7dc3338a12e04c11057b9 Mon Sep 17 00:00:00 2001 From: Daniel Baumann Date: Wed, 17 Apr 2024 14:02:58 +0200 Subject: Adding upstream version 1.64.0+dfsg1. Signed-off-by: Daniel Baumann --- src/tools/rust-analyzer/crates/tt/Cargo.toml | 15 ++ src/tools/rust-analyzer/crates/tt/src/buffer.rs | 231 +++++++++++++++++ src/tools/rust-analyzer/crates/tt/src/lib.rs | 322 ++++++++++++++++++++++++ 3 files changed, 568 insertions(+) create mode 100644 src/tools/rust-analyzer/crates/tt/Cargo.toml create mode 100644 src/tools/rust-analyzer/crates/tt/src/buffer.rs create mode 100644 src/tools/rust-analyzer/crates/tt/src/lib.rs (limited to 'src/tools/rust-analyzer/crates/tt') diff --git a/src/tools/rust-analyzer/crates/tt/Cargo.toml b/src/tools/rust-analyzer/crates/tt/Cargo.toml new file mode 100644 index 000000000..52dfb8608 --- /dev/null +++ b/src/tools/rust-analyzer/crates/tt/Cargo.toml @@ -0,0 +1,15 @@ +[package] +name = "tt" +version = "0.0.0" +description = "TBD" +license = "MIT OR Apache-2.0" +edition = "2021" +rust-version = "1.57" + +[lib] +doctest = false + +[dependencies] +smol_str = "0.1.23" + +stdx = { path = "../stdx", version = "0.0.0" } diff --git a/src/tools/rust-analyzer/crates/tt/src/buffer.rs b/src/tools/rust-analyzer/crates/tt/src/buffer.rs new file mode 100644 index 000000000..69226bd4c --- /dev/null +++ b/src/tools/rust-analyzer/crates/tt/src/buffer.rs @@ -0,0 +1,231 @@ +//! Stateful iteration over token trees. +//! +//! We use this as the source of tokens for parser. +use crate::{Leaf, Subtree, TokenTree}; + +#[derive(Copy, Clone, Debug, Eq, PartialEq)] +struct EntryId(usize); + +#[derive(Copy, Clone, Debug, Eq, PartialEq)] +struct EntryPtr(EntryId, usize); + +/// Internal type which is used instead of `TokenTree` to represent a token tree +/// within a `TokenBuffer`. +#[derive(Debug)] +enum Entry<'t> { + // Mimicking types from proc-macro. + Subtree(Option<&'t TokenTree>, &'t Subtree, EntryId), + Leaf(&'t TokenTree), + // End entries contain a pointer to the entry from the containing + // token tree, or None if this is the outermost level. + End(Option), +} + +/// A token tree buffer +/// The safe version of `syn` [`TokenBuffer`](https://github.com/dtolnay/syn/blob/6533607f91686545cb034d2838beea338d9d0742/src/buffer.rs#L41) +#[derive(Debug)] +pub struct TokenBuffer<'t> { + buffers: Vec]>>, +} + +trait TokenList<'a> { + fn entries(&self) -> (Vec<(usize, (&'a Subtree, Option<&'a TokenTree>))>, Vec>); +} + +impl<'a> TokenList<'a> for &'a [TokenTree] { + fn entries(&self) -> (Vec<(usize, (&'a Subtree, Option<&'a TokenTree>))>, Vec>) { + // Must contain everything in tokens and then the Entry::End + let start_capacity = self.len() + 1; + let mut entries = Vec::with_capacity(start_capacity); + let mut children = vec![]; + for (idx, tt) in self.iter().enumerate() { + match tt { + TokenTree::Leaf(_) => { + entries.push(Entry::Leaf(tt)); + } + TokenTree::Subtree(subtree) => { + entries.push(Entry::End(None)); + children.push((idx, (subtree, Some(tt)))); + } + } + } + (children, entries) + } +} + +impl<'a> TokenList<'a> for &'a Subtree { + fn entries(&self) -> (Vec<(usize, (&'a Subtree, Option<&'a TokenTree>))>, Vec>) { + // Must contain everything in tokens and then the Entry::End + let mut entries = vec![]; + let mut children = vec![]; + entries.push(Entry::End(None)); + children.push((0usize, (*self, None))); + (children, entries) + } +} + +impl<'t> TokenBuffer<'t> { + pub fn from_tokens(tokens: &'t [TokenTree]) -> TokenBuffer<'t> { + Self::new(tokens) + } + + pub fn from_subtree(subtree: &'t Subtree) -> TokenBuffer<'t> { + Self::new(subtree) + } + + fn new>(tokens: T) -> TokenBuffer<'t> { + let mut buffers = vec![]; + let idx = TokenBuffer::new_inner(tokens, &mut buffers, None); + assert_eq!(idx, 0); + TokenBuffer { buffers } + } + + fn new_inner>( + tokens: T, + buffers: &mut Vec]>>, + next: Option, + ) -> usize { + let (children, mut entries) = tokens.entries(); + + entries.push(Entry::End(next)); + let res = buffers.len(); + buffers.push(entries.into_boxed_slice()); + + for (child_idx, (subtree, tt)) in children { + let idx = TokenBuffer::new_inner( + subtree.token_trees.as_slice(), + buffers, + Some(EntryPtr(EntryId(res), child_idx + 1)), + ); + buffers[res].as_mut()[child_idx] = Entry::Subtree(tt, subtree, EntryId(idx)); + } + + res + } + + /// Creates a cursor referencing the first token in the buffer and able to + /// traverse until the end of the buffer. + pub fn begin(&self) -> Cursor<'_> { + Cursor::create(self, EntryPtr(EntryId(0), 0)) + } + + fn entry(&self, ptr: &EntryPtr) -> Option<&Entry<'_>> { + let id = ptr.0; + self.buffers[id.0].get(ptr.1) + } +} + +#[derive(Debug)] +pub enum TokenTreeRef<'a> { + Subtree(&'a Subtree, Option<&'a TokenTree>), + Leaf(&'a Leaf, &'a TokenTree), +} + +impl<'a> TokenTreeRef<'a> { + pub fn cloned(&self) -> TokenTree { + match &self { + TokenTreeRef::Subtree(subtree, tt) => match tt { + Some(it) => (*it).clone(), + None => (*subtree).clone().into(), + }, + TokenTreeRef::Leaf(_, tt) => (*tt).clone(), + } + } +} + +/// A safe version of `Cursor` from `syn` crate +#[derive(Copy, Clone, Debug)] +pub struct Cursor<'a> { + buffer: &'a TokenBuffer<'a>, + ptr: EntryPtr, +} + +impl<'a> PartialEq for Cursor<'a> { + fn eq(&self, other: &Cursor<'_>) -> bool { + self.ptr == other.ptr && std::ptr::eq(self.buffer, other.buffer) + } +} + +impl<'a> Eq for Cursor<'a> {} + +impl<'a> Cursor<'a> { + /// Check whether it is eof + pub fn eof(self) -> bool { + matches!(self.buffer.entry(&self.ptr), None | Some(Entry::End(None))) + } + + /// If the cursor is pointing at the end of a subtree, returns + /// the parent subtree + pub fn end(self) -> Option<&'a Subtree> { + match self.entry() { + Some(Entry::End(Some(ptr))) => { + let idx = ptr.1; + if let Some(Entry::Subtree(_, subtree, _)) = + self.buffer.entry(&EntryPtr(ptr.0, idx - 1)) + { + return Some(subtree); + } + None + } + _ => None, + } + } + + fn entry(self) -> Option<&'a Entry<'a>> { + self.buffer.entry(&self.ptr) + } + + /// If the cursor is pointing at a `Subtree`, returns + /// a cursor into that subtree + pub fn subtree(self) -> Option> { + match self.entry() { + Some(Entry::Subtree(_, _, entry_id)) => { + Some(Cursor::create(self.buffer, EntryPtr(*entry_id, 0))) + } + _ => None, + } + } + + /// If the cursor is pointing at a `TokenTree`, returns it + pub fn token_tree(self) -> Option> { + match self.entry() { + Some(Entry::Leaf(tt)) => match tt { + TokenTree::Leaf(leaf) => Some(TokenTreeRef::Leaf(leaf, *tt)), + TokenTree::Subtree(subtree) => Some(TokenTreeRef::Subtree(subtree, Some(tt))), + }, + Some(Entry::Subtree(tt, subtree, _)) => Some(TokenTreeRef::Subtree(subtree, *tt)), + Some(Entry::End(_)) | None => None, + } + } + + fn create(buffer: &'a TokenBuffer<'_>, ptr: EntryPtr) -> Cursor<'a> { + Cursor { buffer, ptr } + } + + /// Bump the cursor + pub fn bump(self) -> Cursor<'a> { + if let Some(Entry::End(exit)) = self.buffer.entry(&self.ptr) { + match exit { + Some(exit) => Cursor::create(self.buffer, *exit), + None => self, + } + } else { + Cursor::create(self.buffer, EntryPtr(self.ptr.0, self.ptr.1 + 1)) + } + } + + /// Bump the cursor, if it is a subtree, returns + /// a cursor into that subtree + pub fn bump_subtree(self) -> Cursor<'a> { + match self.entry() { + Some(Entry::Subtree(_, _, _)) => self.subtree().unwrap(), + _ => self.bump(), + } + } + + /// Check whether it is a top level + pub fn is_root(&self) -> bool { + let entry_id = self.ptr.0; + entry_id.0 == 0 + } +} diff --git a/src/tools/rust-analyzer/crates/tt/src/lib.rs b/src/tools/rust-analyzer/crates/tt/src/lib.rs new file mode 100644 index 000000000..a54861de9 --- /dev/null +++ b/src/tools/rust-analyzer/crates/tt/src/lib.rs @@ -0,0 +1,322 @@ +//! `tt` crate defines a `TokenTree` data structure: this is the interface (both +//! input and output) of macros. It closely mirrors `proc_macro` crate's +//! `TokenTree`. + +#![warn(rust_2018_idioms, unused_lifetimes, semicolon_in_expressions_from_macros)] + +use std::fmt; + +use stdx::impl_from; + +pub use smol_str::SmolStr; + +/// Represents identity of the token. +/// +/// For hygiene purposes, we need to track which expanded tokens originated from +/// which source tokens. We do it by assigning an distinct identity to each +/// source token and making sure that identities are preserved during macro +/// expansion. +#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)] +pub struct TokenId(pub u32); + +impl TokenId { + pub const fn unspecified() -> TokenId { + TokenId(!0) + } +} + +#[derive(Debug, Clone, PartialEq, Eq, Hash)] +pub enum TokenTree { + Leaf(Leaf), + Subtree(Subtree), +} +impl_from!(Leaf, Subtree for TokenTree); + +impl TokenTree { + pub fn empty() -> Self { + TokenTree::Subtree(Subtree::default()) + } +} + +#[derive(Debug, Clone, PartialEq, Eq, Hash)] +pub enum Leaf { + Literal(Literal), + Punct(Punct), + Ident(Ident), +} +impl_from!(Literal, Punct, Ident for Leaf); + +#[derive(Clone, PartialEq, Eq, Hash, Default)] +pub struct Subtree { + pub delimiter: Option, + pub token_trees: Vec, +} + +#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)] +pub struct Delimiter { + pub id: TokenId, + pub kind: DelimiterKind, +} + +#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)] +pub enum DelimiterKind { + Parenthesis, + Brace, + Bracket, +} + +#[derive(Debug, Clone, PartialEq, Eq, Hash)] +pub struct Literal { + pub text: SmolStr, + pub id: TokenId, +} + +#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)] +pub struct Punct { + pub char: char, + pub spacing: Spacing, + pub id: TokenId, +} + +#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)] +pub enum Spacing { + Alone, + Joint, +} + +#[derive(Debug, Clone, PartialEq, Eq, Hash)] +pub struct Ident { + pub text: SmolStr, + pub id: TokenId, +} + +impl Leaf { + pub fn id(&self) -> TokenId { + match self { + Leaf::Literal(l) => l.id, + Leaf::Punct(p) => p.id, + Leaf::Ident(i) => i.id, + } + } +} + +fn print_debug_subtree(f: &mut fmt::Formatter<'_>, subtree: &Subtree, level: usize) -> fmt::Result { + let align = " ".repeat(level); + + let aux = match subtree.delimiter.map(|it| (it.kind, it.id.0)) { + None => "$".to_string(), + Some((DelimiterKind::Parenthesis, id)) => format!("() {}", id), + Some((DelimiterKind::Brace, id)) => format!("{{}} {}", id), + Some((DelimiterKind::Bracket, id)) => format!("[] {}", id), + }; + + if subtree.token_trees.is_empty() { + write!(f, "{}SUBTREE {}", align, aux)?; + } else { + writeln!(f, "{}SUBTREE {}", align, aux)?; + for (idx, child) in subtree.token_trees.iter().enumerate() { + print_debug_token(f, child, level + 1)?; + if idx != subtree.token_trees.len() - 1 { + writeln!(f)?; + } + } + } + + Ok(()) +} + +fn print_debug_token(f: &mut fmt::Formatter<'_>, tkn: &TokenTree, level: usize) -> fmt::Result { + let align = " ".repeat(level); + + match tkn { + TokenTree::Leaf(leaf) => match leaf { + Leaf::Literal(lit) => write!(f, "{}LITERAL {} {}", align, lit.text, lit.id.0)?, + Leaf::Punct(punct) => write!( + f, + "{}PUNCH {} [{}] {}", + align, + punct.char, + if punct.spacing == Spacing::Alone { "alone" } else { "joint" }, + punct.id.0 + )?, + Leaf::Ident(ident) => write!(f, "{}IDENT {} {}", align, ident.text, ident.id.0)?, + }, + TokenTree::Subtree(subtree) => { + print_debug_subtree(f, subtree, level)?; + } + } + + Ok(()) +} + +impl fmt::Debug for Subtree { + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + print_debug_subtree(f, self, 0) + } +} + +impl fmt::Display for TokenTree { + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + match self { + TokenTree::Leaf(it) => fmt::Display::fmt(it, f), + TokenTree::Subtree(it) => fmt::Display::fmt(it, f), + } + } +} + +impl fmt::Display for Subtree { + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + let (l, r) = match self.delimiter_kind() { + Some(DelimiterKind::Parenthesis) => ("(", ")"), + Some(DelimiterKind::Brace) => ("{", "}"), + Some(DelimiterKind::Bracket) => ("[", "]"), + None => ("", ""), + }; + f.write_str(l)?; + let mut needs_space = false; + for tt in &self.token_trees { + if needs_space { + f.write_str(" ")?; + } + needs_space = true; + match tt { + TokenTree::Leaf(Leaf::Punct(p)) => { + needs_space = p.spacing == Spacing::Alone; + fmt::Display::fmt(p, f)?; + } + tt => fmt::Display::fmt(tt, f)?, + } + } + f.write_str(r)?; + Ok(()) + } +} + +impl fmt::Display for Leaf { + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + match self { + Leaf::Ident(it) => fmt::Display::fmt(it, f), + Leaf::Literal(it) => fmt::Display::fmt(it, f), + Leaf::Punct(it) => fmt::Display::fmt(it, f), + } + } +} + +impl fmt::Display for Ident { + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + fmt::Display::fmt(&self.text, f) + } +} + +impl fmt::Display for Literal { + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + fmt::Display::fmt(&self.text, f) + } +} + +impl fmt::Display for Punct { + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + fmt::Display::fmt(&self.char, f) + } +} + +impl Subtree { + /// Count the number of tokens recursively + pub fn count(&self) -> usize { + let children_count = self + .token_trees + .iter() + .map(|c| match c { + TokenTree::Subtree(c) => c.count(), + TokenTree::Leaf(_) => 0, + }) + .sum::(); + + self.token_trees.len() + children_count + } + + pub fn delimiter_kind(&self) -> Option { + self.delimiter.map(|it| it.kind) + } +} + +impl Subtree { + /// A simple line string used for debugging + pub fn as_debug_string(&self) -> String { + let delim = match self.delimiter_kind() { + Some(DelimiterKind::Brace) => ("{", "}"), + Some(DelimiterKind::Bracket) => ("[", "]"), + Some(DelimiterKind::Parenthesis) => ("(", ")"), + None => (" ", " "), + }; + + let mut res = String::new(); + res.push_str(delim.0); + let mut last = None; + for child in &self.token_trees { + let s = match child { + TokenTree::Leaf(it) => { + let s = match it { + Leaf::Literal(it) => it.text.to_string(), + Leaf::Punct(it) => it.char.to_string(), + Leaf::Ident(it) => it.text.to_string(), + }; + match (it, last) { + (Leaf::Ident(_), Some(&TokenTree::Leaf(Leaf::Ident(_)))) => { + " ".to_string() + &s + } + (Leaf::Punct(_), Some(&TokenTree::Leaf(Leaf::Punct(punct)))) => { + if punct.spacing == Spacing::Alone { + " ".to_string() + &s + } else { + s + } + } + _ => s, + } + } + TokenTree::Subtree(it) => it.as_debug_string(), + }; + res.push_str(&s); + last = Some(child); + } + + res.push_str(delim.1); + res + } +} + +pub mod buffer; + +pub fn pretty(tkns: &[TokenTree]) -> String { + fn tokentree_to_text(tkn: &TokenTree) -> String { + match tkn { + TokenTree::Leaf(Leaf::Ident(ident)) => ident.text.clone().into(), + TokenTree::Leaf(Leaf::Literal(literal)) => literal.text.clone().into(), + TokenTree::Leaf(Leaf::Punct(punct)) => format!("{}", punct.char), + TokenTree::Subtree(subtree) => { + let content = pretty(&subtree.token_trees); + let (open, close) = match subtree.delimiter.map(|it| it.kind) { + None => ("", ""), + Some(DelimiterKind::Brace) => ("{", "}"), + Some(DelimiterKind::Parenthesis) => ("(", ")"), + Some(DelimiterKind::Bracket) => ("[", "]"), + }; + format!("{}{}{}", open, content, close) + } + } + } + + tkns.iter() + .fold((String::new(), true), |(last, last_to_joint), tkn| { + let s = [last, tokentree_to_text(tkn)].join(if last_to_joint { "" } else { " " }); + let mut is_joint = false; + if let TokenTree::Leaf(Leaf::Punct(punct)) = tkn { + if punct.spacing == Spacing::Joint { + is_joint = true; + } + } + (s, is_joint) + }) + .0 +} -- cgit v1.2.3