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