src/tools/rust-analyzer/crates/syntax/src/tests/sourcegen_ast.rs

   1 //! This module generates AST datatype used by rust-analyzer.
   2 //!
   3 //! Specifically, it generates the `SyntaxKind` enum and a number of newtype
   4 //! wrappers around `SyntaxNode` which implement `syntax::AstNode`.
   5
   6 use std::{
   7     collections::{BTreeSet, HashSet},
   8     fmt::Write,
   9 };
  10
  11 use itertools::Itertools;
  12 use proc_macro2::{Punct, Spacing};
  13 use quote::{format_ident, quote};
  14 use ungrammar::{Grammar, Rule};
  15
  16 use crate::tests::ast_src::{
  17     AstEnumSrc, AstNodeSrc, AstSrc, Cardinality, Field, KindsSrc, KINDS_SRC,
  18 };
  19
  20 #[test]
  21 fn sourcegen_ast() {
  22     let syntax_kinds = generate_syntax_kinds(KINDS_SRC);
  23     let syntax_kinds_file =
  24         sourcegen::project_root().join("crates/parser/src/syntax_kind/generated.rs");
  25     sourcegen::ensure_file_contents(syntax_kinds_file.as_path(), &syntax_kinds);
  26
  27     let grammar =
  28         include_str!(concat!(env!("CARGO_MANIFEST_DIR"), "/rust.ungram")).parse().unwrap();
  29     let ast = lower(&grammar);
  30
  31     let ast_tokens = generate_tokens(&ast);
  32     let ast_tokens_file =
  33         sourcegen::project_root().join("crates/syntax/src/ast/generated/tokens.rs");
  34     sourcegen::ensure_file_contents(ast_tokens_file.as_path(), &ast_tokens);
  35
  36     let ast_nodes = generate_nodes(KINDS_SRC, &ast);
  37     let ast_nodes_file = sourcegen::project_root().join("crates/syntax/src/ast/generated/nodes.rs");
  38     sourcegen::ensure_file_contents(ast_nodes_file.as_path(), &ast_nodes);
  39 }
  40
  41 fn generate_tokens(grammar: &AstSrc) -> String {
  42     let tokens = grammar.tokens.iter().map(|token| {
  43         let name = format_ident!("{}", token);
  44         let kind = format_ident!("{}", to_upper_snake_case(token));
  45         quote! {
  46             #[derive(Debug, Clone, PartialEq, Eq, Hash)]
  47             pub struct #name {
  48                 pub(crate) syntax: SyntaxToken,
  49             }
  50             impl std::fmt::Display for #name {
  51                 fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
  52                     std::fmt::Display::fmt(&self.syntax, f)
  53                 }
  54             }
  55             impl AstToken for #name {
  56                 fn can_cast(kind: SyntaxKind) -> bool { kind == #kind }
  57                 fn cast(syntax: SyntaxToken) -> Option<Self> {
  58                     if Self::can_cast(syntax.kind()) { Some(Self { syntax }) } else { None }
  59                 }
  60                 fn syntax(&self) -> &SyntaxToken { &self.syntax }
  61             }
  62         }
  63     });
  64
  65     sourcegen::add_preamble(
  66         "sourcegen_ast",
  67         sourcegen::reformat(
  68             quote! {
  69                 use crate::{SyntaxKind::{self, *}, SyntaxToken, ast::AstToken};
  70                 #(#tokens)*
  71             }
  72             .to_string(),
  73         ),
  74     )
  75     .replace("#[derive", "\n#[derive")
  76 }
  77
  78 fn generate_nodes(kinds: KindsSrc<'_>, grammar: &AstSrc) -> String {
  79     let (node_defs, node_boilerplate_impls): (Vec<_>, Vec<_>) = grammar
  80         .nodes
  81         .iter()
  82         .map(|node| {
  83             let name = format_ident!("{}", node.name);
  84             let kind = format_ident!("{}", to_upper_snake_case(&node.name));
  85             let traits = node
  86                 .traits
  87                 .iter()
  88                 .filter(|trait_name| {
  89                     // Loops have two expressions so this might collide, therefor manual impl it
  90                     node.name != "ForExpr" && node.name != "WhileExpr"
  91                         || trait_name.as_str() != "HasLoopBody"
  92                 })
  93                 .map(|trait_name| {
  94                     let trait_name = format_ident!("{}", trait_name);
  95                     quote!(impl ast::#trait_name for #name {})
  96                 });
  97
  98             let methods = node.fields.iter().map(|field| {
  99                 let method_name = field.method_name();
 100                 let ty = field.ty();
 101
 102                 if field.is_many() {
 103                     quote! {
 104                         pub fn #method_name(&self) -> AstChildren<#ty> {
 105                             support::children(&self.syntax)
 106                         }
 107                     }
 108                 } else if let Some(token_kind) = field.token_kind() {
 109                     quote! {
 110                         pub fn #method_name(&self) -> Option<#ty> {
 111                             support::token(&self.syntax, #token_kind)
 112                         }
 113                     }
 114                 } else {
 115                     quote! {
 116                         pub fn #method_name(&self) -> Option<#ty> {
 117                             support::child(&self.syntax)
 118                         }
 119                     }
 120                 }
 121             });
 122             (
 123                 quote! {
 124                     #[pretty_doc_comment_placeholder_workaround]
 125                     #[derive(Debug, Clone, PartialEq, Eq, Hash)]
 126                     pub struct #name {
 127                         pub(crate) syntax: SyntaxNode,
 128                     }
 129
 130                     #(#traits)*
 131
 132                     impl #name {
 133                         #(#methods)*
 134                     }
 135                 },
 136                 quote! {
 137                     impl AstNode for #name {
 138                         fn can_cast(kind: SyntaxKind) -> bool {
 139                             kind == #kind
 140                         }
 141                         fn cast(syntax: SyntaxNode) -> Option<Self> {
 142                             if Self::can_cast(syntax.kind()) { Some(Self { syntax }) } else { None }
 143                         }
 144                         fn syntax(&self) -> &SyntaxNode { &self.syntax }
 145                     }
 146                 },
 147             )
 148         })
 149         .unzip();
 150
 151     let (enum_defs, enum_boilerplate_impls): (Vec<_>, Vec<_>) = grammar
 152         .enums
 153         .iter()
 154         .map(|en| {
 155             let variants: Vec<_> = en.variants.iter().map(|var| format_ident!("{}", var)).collect();
 156             let name = format_ident!("{}", en.name);
 157             let kinds: Vec<_> = variants
 158                 .iter()
 159                 .map(|name| format_ident!("{}", to_upper_snake_case(&name.to_string())))
 160                 .collect();
 161             let traits = en.traits.iter().map(|trait_name| {
 162                 let trait_name = format_ident!("{}", trait_name);
 163                 quote!(impl ast::#trait_name for #name {})
 164             });
 165
 166             let ast_node = if en.name == "Stmt" {
 167                 quote! {}
 168             } else {
 169                 quote! {
 170                     impl AstNode for #name {
 171                         fn can_cast(kind: SyntaxKind) -> bool {
 172                             match kind {
 173                                 #(#kinds)|* => true,
 174                                 _ => false,
 175                             }
 176                         }
 177                         fn cast(syntax: SyntaxNode) -> Option<Self> {
 178                             let res = match syntax.kind() {
 179                                 #(
 180                                 #kinds => #name::#variants(#variants { syntax }),
 181                                 )*
 182                                 _ => return None,
 183                             };
 184                             Some(res)
 185                         }
 186                         fn syntax(&self) -> &SyntaxNode {
 187                             match self {
 188                                 #(
 189                                 #name::#variants(it) => &it.syntax,
 190                                 )*
 191                             }
 192                         }
 193                     }
 194                 }
 195             };
 196
 197             (
 198                 quote! {
 199                     #[pretty_doc_comment_placeholder_workaround]
 200                     #[derive(Debug, Clone, PartialEq, Eq, Hash)]
 201                     pub enum #name {
 202                         #(#variants(#variants),)*
 203                     }
 204
 205                     #(#traits)*
 206                 },
 207                 quote! {
 208                     #(
 209                         impl From<#variants> for #name {
 210                             fn from(node: #variants) -> #name {
 211                                 #name::#variants(node)
 212                             }
 213                         }
 214                     )*
 215                     #ast_node
 216                 },
 217             )
 218         })
 219         .unzip();
 220
 221     let (any_node_defs, any_node_boilerplate_impls): (Vec<_>, Vec<_>) = grammar
 222         .nodes
 223         .iter()
 224         .flat_map(|node| node.traits.iter().map(move |t| (t, node)))
 225         .into_group_map()
 226         .into_iter()
 227         .sorted_by_key(|(k, _)| *k)
 228         .map(|(trait_name, nodes)| {
 229             let name = format_ident!("Any{}", trait_name);
 230             let trait_name = format_ident!("{}", trait_name);
 231             let kinds: Vec<_> = nodes
 232                 .iter()
 233                 .map(|name| format_ident!("{}", to_upper_snake_case(&name.name.to_string())))
 234                 .collect();
 235
 236             (
 237                 quote! {
 238                     #[pretty_doc_comment_placeholder_workaround]
 239                     #[derive(Debug, Clone, PartialEq, Eq, Hash)]
 240                     pub struct #name {
 241                         pub(crate) syntax: SyntaxNode,
 242                     }
 243                     impl ast::#trait_name for #name {}
 244                 },
 245                 quote! {
 246                     impl #name {
 247                         #[inline]
 248                         pub fn new<T: ast::#trait_name>(node: T) -> #name {
 249                             #name {
 250                                 syntax: node.syntax().clone()
 251                             }
 252                         }
 253                     }
 254                     impl AstNode for #name {
 255                         fn can_cast(kind: SyntaxKind) -> bool {
 256                             match kind {
 257                                 #(#kinds)|* => true,
 258                                 _ => false,
 259                             }
 260                         }
 261                         fn cast(syntax: SyntaxNode) -> Option<Self> {
 262                             Self::can_cast(syntax.kind()).then(|| #name { syntax })
 263                         }
 264                         fn syntax(&self) -> &SyntaxNode {
 265                             &self.syntax
 266                         }
 267                     }
 268                 },
 269             )
 270         })
 271         .unzip();
 272
 273     let enum_names = grammar.enums.iter().map(|it| &it.name);
 274     let node_names = grammar.nodes.iter().map(|it| &it.name);
 275
 276     let display_impls =
 277         enum_names.chain(node_names.clone()).map(|it| format_ident!("{}", it)).map(|name| {
 278             quote! {
 279                 impl std::fmt::Display for #name {
 280                     fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
 281                         std::fmt::Display::fmt(self.syntax(), f)
 282                     }
 283                 }
 284             }
 285         });
 286
 287     let defined_nodes: HashSet<_> = node_names.collect();
 288
 289     for node in kinds
 290         .nodes
 291         .iter()
 292         .map(|kind| to_pascal_case(kind))
 293         .filter(|name| !defined_nodes.iter().any(|&it| it == name))
 294     {
 295         drop(node)
 296         // FIXME: restore this
 297         // eprintln!("Warning: node {} not defined in ast source", node);
 298     }
 299
 300     let ast = quote! {
 301         #![allow(non_snake_case)]
 302         use crate::{
 303             SyntaxNode, SyntaxToken, SyntaxKind::{self, *},
 304             ast::{self, AstNode, AstChildren, support},
 305             T,
 306         };
 307
 308         #(#node_defs)*
 309         #(#enum_defs)*
 310         #(#any_node_defs)*
 311         #(#node_boilerplate_impls)*
 312         #(#enum_boilerplate_impls)*
 313         #(#any_node_boilerplate_impls)*
 314         #(#display_impls)*
 315     };
 316
 317     let ast = ast.to_string().replace("T ! [", "T![");
 318
 319     let mut res = String::with_capacity(ast.len() * 2);
 320
 321     let mut docs =
 322         grammar.nodes.iter().map(|it| &it.doc).chain(grammar.enums.iter().map(|it| &it.doc));
 323
 324     for chunk in ast.split("# [pretty_doc_comment_placeholder_workaround] ") {
 325         res.push_str(chunk);
 326         if let Some(doc) = docs.next() {
 327             write_doc_comment(doc, &mut res);
 328         }
 329     }
 330
 331     let res = sourcegen::add_preamble("sourcegen_ast", sourcegen::reformat(res));
 332     res.replace("#[derive", "\n#[derive")
 333 }
 334
 335 fn write_doc_comment(contents: &[String], dest: &mut String) {
 336     for line in contents {
 337         writeln!(dest, "///{}", line).unwrap();
 338     }
 339 }
 340
 341 fn generate_syntax_kinds(grammar: KindsSrc<'_>) -> String {
 342     let (single_byte_tokens_values, single_byte_tokens): (Vec<_>, Vec<_>) = grammar
 343         .punct
 344         .iter()
 345         .filter(|(token, _name)| token.len() == 1)
 346         .map(|(token, name)| (token.chars().next().unwrap(), format_ident!("{}", name)))
 347         .unzip();
 348
 349     let punctuation_values = grammar.punct.iter().map(|(token, _name)| {
 350         if "{}[]()".contains(token) {
 351             let c = token.chars().next().unwrap();
 352             quote! { #c }
 353         } else {
 354             let cs = token.chars().map(|c| Punct::new(c, Spacing::Joint));
 355             quote! { #(#cs)* }
 356         }
 357     });
 358     let punctuation =
 359         grammar.punct.iter().map(|(_token, name)| format_ident!("{}", name)).collect::<Vec<_>>();
 360
 361     let x = |&name| match name {
 362         "Self" => format_ident!("SELF_TYPE_KW"),
 363         name => format_ident!("{}_KW", to_upper_snake_case(name)),
 364     };
 365     let full_keywords_values = grammar.keywords;
 366     let full_keywords = full_keywords_values.iter().map(x);
 367
 368     let contextual_keywords_values = &grammar.contextual_keywords;
 369     let contextual_keywords = contextual_keywords_values.iter().map(x);
 370
 371     let all_keywords_values = grammar
 372         .keywords
 373         .iter()
 374         .chain(grammar.contextual_keywords.iter())
 375         .copied()
 376         .collect::<Vec<_>>();
 377     let all_keywords_idents = all_keywords_values.iter().map(|kw| format_ident!("{}", kw));
 378     let all_keywords = all_keywords_values.iter().map(x).collect::<Vec<_>>();
 379
 380     let literals =
 381         grammar.literals.iter().map(|name| format_ident!("{}", name)).collect::<Vec<_>>();
 382
 383     let tokens = grammar.tokens.iter().map(|name| format_ident!("{}", name)).collect::<Vec<_>>();
 384
 385     let nodes = grammar.nodes.iter().map(|name| format_ident!("{}", name)).collect::<Vec<_>>();
 386
 387     let ast = quote! {
 388         #![allow(bad_style, missing_docs, unreachable_pub)]
 389         /// The kind of syntax node, e.g. `IDENT`, `USE_KW`, or `STRUCT`.
 390         #[derive(Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash, Debug)]
 391         #[repr(u16)]
 392         pub enum SyntaxKind {
 393             // Technical SyntaxKinds: they appear temporally during parsing,
 394             // but never end up in the final tree
 395             #[doc(hidden)]
 396             TOMBSTONE,
 397             #[doc(hidden)]
 398             EOF,
 399             #(#punctuation,)*
 400             #(#all_keywords,)*
 401             #(#literals,)*
 402             #(#tokens,)*
 403             #(#nodes,)*
 404
 405             // Technical kind so that we can cast from u16 safely
 406             #[doc(hidden)]
 407             __LAST,
 408         }
 409         use self::SyntaxKind::*;
 410
 411         impl SyntaxKind {
 412             pub fn is_keyword(self) -> bool {
 413                 match self {
 414                     #(#all_keywords)|* => true,
 415                     _ => false,
 416                 }
 417             }
 418
 419             pub fn is_punct(self) -> bool {
 420                 match self {
 421                     #(#punctuation)|* => true,
 422                     _ => false,
 423                 }
 424             }
 425
 426             pub fn is_literal(self) -> bool {
 427                 match self {
 428                     #(#literals)|* => true,
 429                     _ => false,
 430                 }
 431             }
 432
 433             pub fn from_keyword(ident: &str) -> Option<SyntaxKind> {
 434                 let kw = match ident {
 435                     #(#full_keywords_values => #full_keywords,)*
 436                     _ => return None,
 437                 };
 438                 Some(kw)
 439             }
 440
 441             pub fn from_contextual_keyword(ident: &str) -> Option<SyntaxKind> {
 442                 let kw = match ident {
 443                     #(#contextual_keywords_values => #contextual_keywords,)*
 444                     _ => return None,
 445                 };
 446                 Some(kw)
 447             }
 448
 449             pub fn from_char(c: char) -> Option<SyntaxKind> {
 450                 let tok = match c {
 451                     #(#single_byte_tokens_values => #single_byte_tokens,)*
 452                     _ => return None,
 453                 };
 454                 Some(tok)
 455             }
 456         }
 457
 458         #[macro_export]
 459         macro_rules! T {
 460             #([#punctuation_values] => { $crate::SyntaxKind::#punctuation };)*
 461             #([#all_keywords_idents] => { $crate::SyntaxKind::#all_keywords };)*
 462             [lifetime_ident] => { $crate::SyntaxKind::LIFETIME_IDENT };
 463             [ident] => { $crate::SyntaxKind::IDENT };
 464             [shebang] => { $crate::SyntaxKind::SHEBANG };
 465         }
 466         pub use T;
 467     };
 468
 469     sourcegen::add_preamble("sourcegen_ast", sourcegen::reformat(ast.to_string()))
 470 }
 471
 472 fn to_upper_snake_case(s: &str) -> String {
 473     let mut buf = String::with_capacity(s.len());
 474     let mut prev = false;
 475     for c in s.chars() {
 476         if c.is_ascii_uppercase() && prev {
 477             buf.push('_')
 478         }
 479         prev = true;
 480
 481         buf.push(c.to_ascii_uppercase());
 482     }
 483     buf
 484 }
 485
 486 fn to_lower_snake_case(s: &str) -> String {
 487     let mut buf = String::with_capacity(s.len());
 488     let mut prev = false;
 489     for c in s.chars() {
 490         if c.is_ascii_uppercase() && prev {
 491             buf.push('_')
 492         }
 493         prev = true;
 494
 495         buf.push(c.to_ascii_lowercase());
 496     }
 497     buf
 498 }
 499
 500 fn to_pascal_case(s: &str) -> String {
 501     let mut buf = String::with_capacity(s.len());
 502     let mut prev_is_underscore = true;
 503     for c in s.chars() {
 504         if c == '_' {
 505             prev_is_underscore = true;
 506         } else if prev_is_underscore {
 507             buf.push(c.to_ascii_uppercase());
 508             prev_is_underscore = false;
 509         } else {
 510             buf.push(c.to_ascii_lowercase());
 511         }
 512     }
 513     buf
 514 }
 515
 516 fn pluralize(s: &str) -> String {
 517     format!("{}s", s)
 518 }
 519
 520 impl Field {
 521     fn is_many(&self) -> bool {
 522         matches!(self, Field::Node { cardinality: Cardinality::Many, .. })
 523     }
 524     fn token_kind(&self) -> Option<proc_macro2::TokenStream> {
 525         match self {
 526             Field::Token(token) => {
 527                 let token: proc_macro2::TokenStream = token.parse().unwrap();
 528                 Some(quote! { T![#token] })
 529             }
 530             _ => None,
 531         }
 532     }
 533     fn method_name(&self) -> proc_macro2::Ident {
 534         match self {
 535             Field::Token(name) => {
 536                 let name = match name.as_str() {
 537                     ";" => "semicolon",
 538                     "->" => "thin_arrow",
 539                     "'{'" => "l_curly",
 540                     "'}'" => "r_curly",
 541                     "'('" => "l_paren",
 542                     "')'" => "r_paren",
 543                     "'['" => "l_brack",
 544                     "']'" => "r_brack",
 545                     "<" => "l_angle",
 546                     ">" => "r_angle",
 547                     "=" => "eq",
 548                     "!" => "excl",
 549                     "*" => "star",
 550                     "&" => "amp",
 551                     "_" => "underscore",
 552                     "." => "dot",
 553                     ".." => "dotdot",
 554                     "..." => "dotdotdot",
 555                     "..=" => "dotdoteq",
 556                     "=>" => "fat_arrow",
 557                     "@" => "at",
 558                     ":" => "colon",
 559                     "::" => "coloncolon",
 560                     "#" => "pound",
 561                     "?" => "question_mark",
 562                     "," => "comma",
 563                     "|" => "pipe",
 564                     "~" => "tilde",
 565                     _ => name,
 566                 };
 567                 format_ident!("{}_token", name)
 568             }
 569             Field::Node { name, .. } => {
 570                 if name == "type" {
 571                     format_ident!("ty")
 572                 } else {
 573                     format_ident!("{}", name)
 574                 }
 575             }
 576         }
 577     }
 578     fn ty(&self) -> proc_macro2::Ident {
 579         match self {
 580             Field::Token(_) => format_ident!("SyntaxToken"),
 581             Field::Node { ty, .. } => format_ident!("{}", ty),
 582         }
 583     }
 584 }
 585
 586 fn lower(grammar: &Grammar) -> AstSrc {
 587     let mut res = AstSrc {
 588         tokens: "Whitespace Comment String ByteString IntNumber FloatNumber Char Byte Ident"
 589             .split_ascii_whitespace()
 590             .map(|it| it.to_string())
 591             .collect::<Vec<_>>(),
 592         ..Default::default()
 593     };
 594
 595     let nodes = grammar.iter().collect::<Vec<_>>();
 596
 597     for &node in &nodes {
 598         let name = grammar[node].name.clone();
 599         let rule = &grammar[node].rule;
 600         match lower_enum(grammar, rule) {
 601             Some(variants) => {
 602                 let enum_src = AstEnumSrc { doc: Vec::new(), name, traits: Vec::new(), variants };
 603                 res.enums.push(enum_src);
 604             }
 605             None => {
 606                 let mut fields = Vec::new();
 607                 lower_rule(&mut fields, grammar, None, rule);
 608                 res.nodes.push(AstNodeSrc { doc: Vec::new(), name, traits: Vec::new(), fields });
 609             }
 610         }
 611     }
 612
 613     deduplicate_fields(&mut res);
 614     extract_enums(&mut res);
 615     extract_struct_traits(&mut res);
 616     extract_enum_traits(&mut res);
 617     res
 618 }
 619
 620 fn lower_enum(grammar: &Grammar, rule: &Rule) -> Option<Vec<String>> {
 621     let alternatives = match rule {
 622         Rule::Alt(it) => it,
 623         _ => return None,
 624     };
 625     let mut variants = Vec::new();
 626     for alternative in alternatives {
 627         match alternative {
 628             Rule::Node(it) => variants.push(grammar[*it].name.clone()),
 629             Rule::Token(it) if grammar[*it].name == ";" => (),
 630             _ => return None,
 631         }
 632     }
 633     Some(variants)
 634 }
 635
 636 fn lower_rule(acc: &mut Vec<Field>, grammar: &Grammar, label: Option<&String>, rule: &Rule) {
 637     if lower_comma_list(acc, grammar, label, rule) {
 638         return;
 639     }
 640
 641     match rule {
 642         Rule::Node(node) => {
 643             let ty = grammar[*node].name.clone();
 644             let name = label.cloned().unwrap_or_else(|| to_lower_snake_case(&ty));
 645             let field = Field::Node { name, ty, cardinality: Cardinality::Optional };
 646             acc.push(field);
 647         }
 648         Rule::Token(token) => {
 649             assert!(label.is_none());
 650             let mut name = grammar[*token].name.clone();
 651             if name != "int_number" && name != "string" {
 652                 if "[]{}()".contains(&name) {
 653                     name = format!("'{}'", name);
 654                 }
 655                 let field = Field::Token(name);
 656                 acc.push(field);
 657             }
 658         }
 659         Rule::Rep(inner) => {
 660             if let Rule::Node(node) = &**inner {
 661                 let ty = grammar[*node].name.clone();
 662                 let name = label.cloned().unwrap_or_else(|| pluralize(&to_lower_snake_case(&ty)));
 663                 let field = Field::Node { name, ty, cardinality: Cardinality::Many };
 664                 acc.push(field);
 665                 return;
 666             }
 667             panic!("unhandled rule: {:?}", rule)
 668         }
 669         Rule::Labeled { label: l, rule } => {
 670             assert!(label.is_none());
 671             let manually_implemented = matches!(
 672                 l.as_str(),
 673                 "lhs"
 674                     | "rhs"
 675                     | "then_branch"
 676                     | "else_branch"
 677                     | "start"
 678                     | "end"
 679                     | "op"
 680                     | "index"
 681                     | "base"
 682                     | "value"
 683                     | "trait"
 684                     | "self_ty"
 685             );
 686             if manually_implemented {
 687                 return;
 688             }
 689             lower_rule(acc, grammar, Some(l), rule);
 690         }
 691         Rule::Seq(rules) | Rule::Alt(rules) => {
 692             for rule in rules {
 693                 lower_rule(acc, grammar, label, rule)
 694             }
 695         }
 696         Rule::Opt(rule) => lower_rule(acc, grammar, label, rule),
 697     }
 698 }
 699
 700 // (T (',' T)* ','?)
 701 fn lower_comma_list(
 702     acc: &mut Vec<Field>,
 703     grammar: &Grammar,
 704     label: Option<&String>,
 705     rule: &Rule,
 706 ) -> bool {
 707     let rule = match rule {
 708         Rule::Seq(it) => it,
 709         _ => return false,
 710     };
 711     let (node, repeat, trailing_comma) = match rule.as_slice() {
 712         [Rule::Node(node), Rule::Rep(repeat), Rule::Opt(trailing_comma)] => {
 713             (node, repeat, trailing_comma)
 714         }
 715         _ => return false,
 716     };
 717     let repeat = match &**repeat {
 718         Rule::Seq(it) => it,
 719         _ => return false,
 720     };
 721     match repeat.as_slice() {
 722         [comma, Rule::Node(n)] if comma == &**trailing_comma && n == node => (),
 723         _ => return false,
 724     }
 725     let ty = grammar[*node].name.clone();
 726     let name = label.cloned().unwrap_or_else(|| pluralize(&to_lower_snake_case(&ty)));
 727     let field = Field::Node { name, ty, cardinality: Cardinality::Many };
 728     acc.push(field);
 729     true
 730 }
 731
 732 fn deduplicate_fields(ast: &mut AstSrc) {
 733     for node in &mut ast.nodes {
 734         let mut i = 0;
 735         'outer: while i < node.fields.len() {
 736             for j in 0..i {
 737                 let f1 = &node.fields[i];
 738                 let f2 = &node.fields[j];
 739                 if f1 == f2 {
 740                     node.fields.remove(i);
 741                     continue 'outer;
 742                 }
 743             }
 744             i += 1;
 745         }
 746     }
 747 }
 748
 749 fn extract_enums(ast: &mut AstSrc) {
 750     for node in &mut ast.nodes {
 751         for enm in &ast.enums {
 752             let mut to_remove = Vec::new();
 753             for (i, field) in node.fields.iter().enumerate() {
 754                 let ty = field.ty().to_string();
 755                 if enm.variants.iter().any(|it| it == &ty) {
 756                     to_remove.push(i);
 757                 }
 758             }
 759             if to_remove.len() == enm.variants.len() {
 760                 node.remove_field(to_remove);
 761                 let ty = enm.name.clone();
 762                 let name = to_lower_snake_case(&ty);
 763                 node.fields.push(Field::Node { name, ty, cardinality: Cardinality::Optional });
 764             }
 765         }
 766     }
 767 }
 768
 769 fn extract_struct_traits(ast: &mut AstSrc) {
 770     let traits: &[(&str, &[&str])] = &[
 771         ("HasAttrs", &["attrs"]),
 772         ("HasName", &["name"]),
 773         ("HasVisibility", &["visibility"]),
 774         ("HasGenericParams", &["generic_param_list", "where_clause"]),
 775         ("HasTypeBounds", &["type_bound_list", "colon_token"]),
 776         ("HasModuleItem", &["items"]),
 777         ("HasLoopBody", &["label", "loop_body"]),
 778         ("HasArgList", &["arg_list"]),
 779     ];
 780
 781     for node in &mut ast.nodes {
 782         for (name, methods) in traits {
 783             extract_struct_trait(node, name, methods);
 784         }
 785     }
 786
 787     let nodes_with_doc_comments = [
 788         "SourceFile",
 789         "Fn",
 790         "Struct",
 791         "Union",
 792         "RecordField",
 793         "TupleField",
 794         "Enum",
 795         "Variant",
 796         "Trait",
 797         "Module",
 798         "Static",
 799         "Const",
 800         "TypeAlias",
 801         "Impl",
 802         "ExternBlock",
 803         "ExternCrate",
 804         "MacroCall",
 805         "MacroRules",
 806         "MacroDef",
 807         "Use",
 808     ];
 809
 810     for node in &mut ast.nodes {
 811         if nodes_with_doc_comments.contains(&&*node.name) {
 812             node.traits.push("HasDocComments".into());
 813         }
 814     }
 815 }
 816
 817 fn extract_struct_trait(node: &mut AstNodeSrc, trait_name: &str, methods: &[&str]) {
 818     let mut to_remove = Vec::new();
 819     for (i, field) in node.fields.iter().enumerate() {
 820         let method_name = field.method_name().to_string();
 821         if methods.iter().any(|&it| it == method_name) {
 822             to_remove.push(i);
 823         }
 824     }
 825     if to_remove.len() == methods.len() {
 826         node.traits.push(trait_name.to_string());
 827         node.remove_field(to_remove);
 828     }
 829 }
 830
 831 fn extract_enum_traits(ast: &mut AstSrc) {
 832     for enm in &mut ast.enums {
 833         if enm.name == "Stmt" {
 834             continue;
 835         }
 836         let nodes = &ast.nodes;
 837         let mut variant_traits = enm
 838             .variants
 839             .iter()
 840             .map(|var| nodes.iter().find(|it| &it.name == var).unwrap())
 841             .map(|node| node.traits.iter().cloned().collect::<BTreeSet<_>>());
 842
 843         let mut enum_traits = match variant_traits.next() {
 844             Some(it) => it,
 845             None => continue,
 846         };
 847         for traits in variant_traits {
 848             enum_traits = enum_traits.intersection(&traits).cloned().collect();
 849         }
 850         enm.traits = enum_traits.into_iter().collect();
 851     }
 852 }
 853
 854 impl AstNodeSrc {
 855     fn remove_field(&mut self, to_remove: Vec<usize>) {
 856         to_remove.into_iter().rev().for_each(|idx| {
 857             self.fields.remove(idx);
 858         });
 859     }
 860 }