src/tools/rust-analyzer/crates/tt/src/lib.rs

   1 //! `tt` crate defines a `TokenTree` data structure: this is the interface (both
   2 //! input and output) of macros. It closely mirrors `proc_macro` crate's
   3 //! `TokenTree`.
   4
   5 #![warn(rust_2018_idioms, unused_lifetimes)]
   6
   7 use std::fmt;
   8
   9 use stdx::impl_from;
  10
  11 pub use smol_str::SmolStr;
  12 pub use text_size::{TextRange, TextSize};
  13
  14 #[derive(Clone, Copy, PartialEq, Eq, Hash, Debug)]
  15 pub struct SpanData<Anchor, Ctx> {
  16     /// The text range of this span, relative to the anchor.
  17     /// We need the anchor for incrementality, as storing absolute ranges will require
  18     /// recomputation on every change in a file at all times.
  19     pub range: TextRange,
  20     pub anchor: Anchor,
  21     /// The syntax context of the span.
  22     pub ctx: Ctx,
  23 }
  24
  25 impl<Anchor: SpanAnchor, Ctx: SyntaxContext> Span for SpanData<Anchor, Ctx> {
  26     #[allow(deprecated)]
  27     const DUMMY: Self = SpanData {
  28         range: TextRange::empty(TextSize::new(0)),
  29         anchor: Anchor::DUMMY,
  30         ctx: Ctx::DUMMY,
  31     };
  32 }
  33
  34 pub trait Span: std::fmt::Debug + Copy + Sized + Eq {
  35     // FIXME: Should not exist. Dummy spans will always be wrong if they leak somewhere. Instead,
  36     // the call site or def site spans should be used in relevant places, its just that we don't
  37     // expose those everywhere in the yet.
  38     const DUMMY: Self;
  39 }
  40
  41 // FIXME: Should not exist
  42 pub trait SpanAnchor:
  43     std::fmt::Debug + Copy + Sized + Eq + Copy + fmt::Debug + std::hash::Hash
  44 {
  45     #[deprecated(note = "this should not exist")]
  46     const DUMMY: Self;
  47 }
  48
  49 // FIXME: Should not exist
  50 pub trait SyntaxContext: std::fmt::Debug + Copy + Sized + Eq {
  51     #[deprecated(note = "this should not exist")]
  52     const DUMMY: Self;
  53 }
  54
  55 #[derive(Debug, Clone, PartialEq, Eq, Hash)]
  56 pub enum TokenTree<S> {
  57     Leaf(Leaf<S>),
  58     Subtree(Subtree<S>),
  59 }
  60 impl_from!(Leaf<S>, Subtree<S> for TokenTree);
  61 impl<S: Span> TokenTree<S> {
  62     pub const fn empty(span: S) -> Self {
  63         Self::Subtree(Subtree {
  64             delimiter: Delimiter::invisible_spanned(span),
  65             token_trees: vec![],
  66         })
  67     }
  68
  69     pub fn subtree_or_wrap(self) -> Subtree<S> {
  70         match self {
  71             TokenTree::Leaf(_) => {
  72                 Subtree { delimiter: Delimiter::DUMMY_INVISIBLE, token_trees: vec![self] }
  73             }
  74             TokenTree::Subtree(s) => s,
  75         }
  76     }
  77     pub fn subtree_or_wrap2(self, span: DelimSpan<S>) -> Subtree<S> {
  78         match self {
  79             TokenTree::Leaf(_) => Subtree {
  80                 delimiter: Delimiter::invisible_delim_spanned(span),
  81                 token_trees: vec![self],
  82             },
  83             TokenTree::Subtree(s) => s,
  84         }
  85     }
  86 }
  87
  88 #[derive(Debug, Clone, PartialEq, Eq, Hash)]
  89 pub enum Leaf<S> {
  90     Literal(Literal<S>),
  91     Punct(Punct<S>),
  92     Ident(Ident<S>),
  93 }
  94
  95 impl<S> Leaf<S> {
  96     pub fn span(&self) -> &S {
  97         match self {
  98             Leaf::Literal(it) => &it.span,
  99             Leaf::Punct(it) => &it.span,
 100             Leaf::Ident(it) => &it.span,
 101         }
 102     }
 103 }
 104 impl_from!(Literal<S>, Punct<S>, Ident<S> for Leaf);
 105
 106 #[derive(Clone, PartialEq, Eq, Hash)]
 107 pub struct Subtree<S> {
 108     pub delimiter: Delimiter<S>,
 109     pub token_trees: Vec<TokenTree<S>>,
 110 }
 111
 112 impl<S: Span> Subtree<S> {
 113     pub const fn empty(span: DelimSpan<S>) -> Self {
 114         Subtree { delimiter: Delimiter::invisible_delim_spanned(span), token_trees: vec![] }
 115     }
 116
 117     pub fn visit_ids(&mut self, f: &mut impl FnMut(S) -> S) {
 118         self.delimiter.open = f(self.delimiter.open);
 119         self.delimiter.close = f(self.delimiter.close);
 120         self.token_trees.iter_mut().for_each(|tt| match tt {
 121             crate::TokenTree::Leaf(leaf) => match leaf {
 122                 crate::Leaf::Literal(it) => it.span = f(it.span),
 123                 crate::Leaf::Punct(it) => it.span = f(it.span),
 124                 crate::Leaf::Ident(it) => it.span = f(it.span),
 125             },
 126             crate::TokenTree::Subtree(s) => s.visit_ids(f),
 127         })
 128     }
 129 }
 130
 131 #[derive(Debug, Copy, Clone, PartialEq)]
 132 pub struct DelimSpan<S> {
 133     pub open: S,
 134     pub close: S,
 135 }
 136
 137 impl<S: Span> DelimSpan<S> {
 138     // FIXME should not exist
 139     pub const DUMMY: Self = Self { open: S::DUMMY, close: S::DUMMY };
 140 }
 141
 142 #[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
 143 pub struct Delimiter<S> {
 144     pub open: S,
 145     pub close: S,
 146     pub kind: DelimiterKind,
 147 }
 148
 149 impl<S: Span> Delimiter<S> {
 150     // FIXME should not exist
 151     pub const DUMMY_INVISIBLE: Self =
 152         Self { open: S::DUMMY, close: S::DUMMY, kind: DelimiterKind::Invisible };
 153
 154     // FIXME should not exist
 155     pub const fn dummy_invisible() -> Self {
 156         Self::DUMMY_INVISIBLE
 157     }
 158
 159     pub const fn invisible_spanned(span: S) -> Self {
 160         Delimiter { open: span, close: span, kind: DelimiterKind::Invisible }
 161     }
 162
 163     pub const fn invisible_delim_spanned(span: DelimSpan<S>) -> Self {
 164         Delimiter { open: span.open, close: span.close, kind: DelimiterKind::Invisible }
 165     }
 166
 167     pub fn delim_span(&self) -> DelimSpan<S> {
 168         DelimSpan { open: self.open, close: self.close }
 169     }
 170 }
 171
 172 #[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
 173 pub enum DelimiterKind {
 174     Parenthesis,
 175     Brace,
 176     Bracket,
 177     Invisible,
 178 }
 179
 180 #[derive(Debug, Clone, PartialEq, Eq, Hash)]
 181 pub struct Literal<S> {
 182     pub text: SmolStr,
 183     pub span: S,
 184 }
 185
 186 #[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
 187 pub struct Punct<S> {
 188     pub char: char,
 189     pub spacing: Spacing,
 190     pub span: S,
 191 }
 192
 193 #[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
 194 pub enum Spacing {
 195     Alone,
 196     Joint,
 197 }
 198
 199 #[derive(Debug, Clone, PartialEq, Eq, Hash)]
 200 /// Identifier or keyword. Unlike rustc, we keep "r#" prefix when it represents a raw identifier.
 201 pub struct Ident<S> {
 202     pub text: SmolStr,
 203     pub span: S,
 204 }
 205
 206 impl<S> Ident<S> {
 207     pub fn new(text: impl Into<SmolStr>, span: S) -> Self {
 208         Ident { text: text.into(), span }
 209     }
 210 }
 211
 212 fn print_debug_subtree<S: fmt::Debug>(
 213     f: &mut fmt::Formatter<'_>,
 214     subtree: &Subtree<S>,
 215     level: usize,
 216 ) -> fmt::Result {
 217     let align = "  ".repeat(level);
 218
 219     let Delimiter { kind, open, close } = &subtree.delimiter;
 220     let aux = match kind {
 221         DelimiterKind::Invisible => format!("$$ {:?} {:?}", open, close),
 222         DelimiterKind::Parenthesis => format!("() {:?} {:?}", open, close),
 223         DelimiterKind::Brace => format!("{{}} {:?} {:?}", open, close),
 224         DelimiterKind::Bracket => format!("[] {:?} {:?}", open, close),
 225     };
 226
 227     if subtree.token_trees.is_empty() {
 228         write!(f, "{align}SUBTREE {aux}")?;
 229     } else {
 230         writeln!(f, "{align}SUBTREE {aux}")?;
 231         for (idx, child) in subtree.token_trees.iter().enumerate() {
 232             print_debug_token(f, child, level + 1)?;
 233             if idx != subtree.token_trees.len() - 1 {
 234                 writeln!(f)?;
 235             }
 236         }
 237     }
 238
 239     Ok(())
 240 }
 241
 242 fn print_debug_token<S: fmt::Debug>(
 243     f: &mut fmt::Formatter<'_>,
 244     tkn: &TokenTree<S>,
 245     level: usize,
 246 ) -> fmt::Result {
 247     let align = "  ".repeat(level);
 248
 249     match tkn {
 250         TokenTree::Leaf(leaf) => match leaf {
 251             Leaf::Literal(lit) => write!(f, "{}LITERAL {} {:?}", align, lit.text, lit.span)?,
 252             Leaf::Punct(punct) => write!(
 253                 f,
 254                 "{}PUNCH   {} [{}] {:?}",
 255                 align,
 256                 punct.char,
 257                 if punct.spacing == Spacing::Alone { "alone" } else { "joint" },
 258                 punct.span
 259             )?,
 260             Leaf::Ident(ident) => write!(f, "{}IDENT   {} {:?}", align, ident.text, ident.span)?,
 261         },
 262         TokenTree::Subtree(subtree) => {
 263             print_debug_subtree(f, subtree, level)?;
 264         }
 265     }
 266
 267     Ok(())
 268 }
 269
 270 impl<S: fmt::Debug> fmt::Debug for Subtree<S> {
 271     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
 272         print_debug_subtree(f, self, 0)
 273     }
 274 }
 275
 276 impl<S> fmt::Display for TokenTree<S> {
 277     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
 278         match self {
 279             TokenTree::Leaf(it) => fmt::Display::fmt(it, f),
 280             TokenTree::Subtree(it) => fmt::Display::fmt(it, f),
 281         }
 282     }
 283 }
 284
 285 impl<S> fmt::Display for Subtree<S> {
 286     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
 287         let (l, r) = match self.delimiter.kind {
 288             DelimiterKind::Parenthesis => ("(", ")"),
 289             DelimiterKind::Brace => ("{", "}"),
 290             DelimiterKind::Bracket => ("[", "]"),
 291             DelimiterKind::Invisible => ("", ""),
 292         };
 293         f.write_str(l)?;
 294         let mut needs_space = false;
 295         for tt in &self.token_trees {
 296             if needs_space {
 297                 f.write_str(" ")?;
 298             }
 299             needs_space = true;
 300             match tt {
 301                 TokenTree::Leaf(Leaf::Punct(p)) => {
 302                     needs_space = p.spacing == Spacing::Alone;
 303                     fmt::Display::fmt(p, f)?;
 304                 }
 305                 tt => fmt::Display::fmt(tt, f)?,
 306             }
 307         }
 308         f.write_str(r)?;
 309         Ok(())
 310     }
 311 }
 312
 313 impl<S> fmt::Display for Leaf<S> {
 314     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
 315         match self {
 316             Leaf::Ident(it) => fmt::Display::fmt(it, f),
 317             Leaf::Literal(it) => fmt::Display::fmt(it, f),
 318             Leaf::Punct(it) => fmt::Display::fmt(it, f),
 319         }
 320     }
 321 }
 322
 323 impl<S> fmt::Display for Ident<S> {
 324     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
 325         fmt::Display::fmt(&self.text, f)
 326     }
 327 }
 328
 329 impl<S> fmt::Display for Literal<S> {
 330     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
 331         fmt::Display::fmt(&self.text, f)
 332     }
 333 }
 334
 335 impl<S> fmt::Display for Punct<S> {
 336     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
 337         fmt::Display::fmt(&self.char, f)
 338     }
 339 }
 340
 341 impl<S> Subtree<S> {
 342     /// Count the number of tokens recursively
 343     pub fn count(&self) -> usize {
 344         let children_count = self
 345             .token_trees
 346             .iter()
 347             .map(|c| match c {
 348                 TokenTree::Subtree(c) => c.count(),
 349                 TokenTree::Leaf(_) => 0,
 350             })
 351             .sum::<usize>();
 352
 353         self.token_trees.len() + children_count
 354     }
 355 }
 356
 357 impl<S> Subtree<S> {
 358     /// A simple line string used for debugging
 359     pub fn as_debug_string(&self) -> String {
 360         let delim = match self.delimiter.kind {
 361             DelimiterKind::Brace => ("{", "}"),
 362             DelimiterKind::Bracket => ("[", "]"),
 363             DelimiterKind::Parenthesis => ("(", ")"),
 364             DelimiterKind::Invisible => ("$", "$"),
 365         };
 366
 367         let mut res = String::new();
 368         res.push_str(delim.0);
 369         let mut last = None;
 370         for child in &self.token_trees {
 371             let s = match child {
 372                 TokenTree::Leaf(it) => {
 373                     let s = match it {
 374                         Leaf::Literal(it) => it.text.to_string(),
 375                         Leaf::Punct(it) => it.char.to_string(),
 376                         Leaf::Ident(it) => it.text.to_string(),
 377                     };
 378                     match (it, last) {
 379                         (Leaf::Ident(_), Some(&TokenTree::Leaf(Leaf::Ident(_)))) => {
 380                             " ".to_string() + &s
 381                         }
 382                         (Leaf::Punct(_), Some(TokenTree::Leaf(Leaf::Punct(punct)))) => {
 383                             if punct.spacing == Spacing::Alone {
 384                                 " ".to_string() + &s
 385                             } else {
 386                                 s
 387                             }
 388                         }
 389                         _ => s,
 390                     }
 391                 }
 392                 TokenTree::Subtree(it) => it.as_debug_string(),
 393             };
 394             res.push_str(&s);
 395             last = Some(child);
 396         }
 397
 398         res.push_str(delim.1);
 399         res
 400     }
 401 }
 402
 403 pub mod buffer;
 404
 405 pub fn pretty<S>(tkns: &[TokenTree<S>]) -> String {
 406     fn tokentree_to_text<S>(tkn: &TokenTree<S>) -> String {
 407         match tkn {
 408             TokenTree::Leaf(Leaf::Ident(ident)) => ident.text.clone().into(),
 409             TokenTree::Leaf(Leaf::Literal(literal)) => literal.text.clone().into(),
 410             TokenTree::Leaf(Leaf::Punct(punct)) => format!("{}", punct.char),
 411             TokenTree::Subtree(subtree) => {
 412                 let content = pretty(&subtree.token_trees);
 413                 let (open, close) = match subtree.delimiter.kind {
 414                     DelimiterKind::Brace => ("{", "}"),
 415                     DelimiterKind::Bracket => ("[", "]"),
 416                     DelimiterKind::Parenthesis => ("(", ")"),
 417                     DelimiterKind::Invisible => ("", ""),
 418                 };
 419                 format!("{open}{content}{close}")
 420             }
 421         }
 422     }
 423
 424     tkns.iter()
 425         .fold((String::new(), true), |(last, last_to_joint), tkn| {
 426             let s = [last, tokentree_to_text(tkn)].join(if last_to_joint { "" } else { " " });
 427             let mut is_joint = false;
 428             if let TokenTree::Leaf(Leaf::Punct(punct)) = tkn {
 429                 if punct.spacing == Spacing::Joint {
 430                     is_joint = true;
 431                 }
 432             }
 433             (s, is_joint)
 434         })
 435         .0
 436 }