Adding upstream version 1.64.0+dfsg1.upstream/1.64.0+dfsg1

Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>

3 files changed, 568 insertions, 0 deletions

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<EntryPtr>),
+}
+
+/// 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<Box<[Entry<'t>]>>,
+}
+
+trait TokenList<'a> {
+    fn entries(&self) -> (Vec<(usize, (&'a Subtree, Option<&'a TokenTree>))>, Vec<Entry<'a>>);
+}
+
+impl<'a> TokenList<'a> for &'a [TokenTree] {
+    fn entries(&self) -> (Vec<(usize, (&'a Subtree, Option<&'a TokenTree>))>, Vec<Entry<'a>>) {
+        // 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<Entry<'a>>) {
+        // 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<T: TokenList<'t>>(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<T: TokenList<'t>>(
+        tokens: T,
+        buffers: &mut Vec<Box<[Entry<'t>]>>,
+        next: Option<EntryPtr>,
+    ) -> 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 <https://github.com/dtolnay/syn/blob/6533607f91686545cb034d2838beea338d9d0742/src/buffer.rs#L125>
+#[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<Cursor<'a>> {
+        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<TokenTreeRef<'a>> {
+        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<Delimiter>,
+    pub token_trees: Vec<TokenTree>,
+}
+
+#[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::<usize>();
+
+        self.token_trees.len() + children_count
+    }
+
+    pub fn delimiter_kind(&self) -> Option<DelimiterKind> {
+        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
+}