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                     | "iterable"
 686                     | "condition"
 687             );
 688             if manually_implemented {
 689                 return;
 690             }
 691             lower_rule(acc, grammar, Some(l), rule);
 692         }
 693         Rule::Seq(rules) | Rule::Alt(rules) => {
 694             for rule in rules {
 695                 lower_rule(acc, grammar, label, rule)
 696             }
 697         }
 698         Rule::Opt(rule) => lower_rule(acc, grammar, label, rule),
 699     }
 700 }
 701
 702 // (T (',' T)* ','?)
 703 fn lower_comma_list(
 704     acc: &mut Vec<Field>,
 705     grammar: &Grammar,
 706     label: Option<&String>,
 707     rule: &Rule,
 708 ) -> bool {
 709     let rule = match rule {
 710         Rule::Seq(it) => it,
 711         _ => return false,
 712     };
 713     let (node, repeat, trailing_comma) = match rule.as_slice() {
 714         [Rule::Node(node), Rule::Rep(repeat), Rule::Opt(trailing_comma)] => {
 715             (node, repeat, trailing_comma)
 716         }
 717         _ => return false,
 718     };
 719     let repeat = match &**repeat {
 720         Rule::Seq(it) => it,
 721         _ => return false,
 722     };
 723     match repeat.as_slice() {
 724         [comma, Rule::Node(n)] if comma == &**trailing_comma && n == node => (),
 725         _ => return false,
 726     }
 727     let ty = grammar[*node].name.clone();
 728     let name = label.cloned().unwrap_or_else(|| pluralize(&to_lower_snake_case(&ty)));
 729     let field = Field::Node { name, ty, cardinality: Cardinality::Many };
 730     acc.push(field);
 731     true
 732 }
 733
 734 fn deduplicate_fields(ast: &mut AstSrc) {
 735     for node in &mut ast.nodes {
 736         let mut i = 0;
 737         'outer: while i < node.fields.len() {
 738             for j in 0..i {
 739                 let f1 = &node.fields[i];
 740                 let f2 = &node.fields[j];
 741                 if f1 == f2 {
 742                     node.fields.remove(i);
 743                     continue 'outer;
 744                 }
 745             }
 746             i += 1;
 747         }
 748     }
 749 }
 750
 751 fn extract_enums(ast: &mut AstSrc) {
 752     for node in &mut ast.nodes {
 753         for enm in &ast.enums {
 754             let mut to_remove = Vec::new();
 755             for (i, field) in node.fields.iter().enumerate() {
 756                 let ty = field.ty().to_string();
 757                 if enm.variants.iter().any(|it| it == &ty) {
 758                     to_remove.push(i);
 759                 }
 760             }
 761             if to_remove.len() == enm.variants.len() {
 762                 node.remove_field(to_remove);
 763                 let ty = enm.name.clone();
 764                 let name = to_lower_snake_case(&ty);
 765                 node.fields.push(Field::Node { name, ty, cardinality: Cardinality::Optional });
 766             }
 767         }
 768     }
 769 }
 770
 771 fn extract_struct_traits(ast: &mut AstSrc) {
 772     let traits: &[(&str, &[&str])] = &[
 773         ("HasAttrs", &["attrs"]),
 774         ("HasName", &["name"]),
 775         ("HasVisibility", &["visibility"]),
 776         ("HasGenericParams", &["generic_param_list", "where_clause"]),
 777         ("HasTypeBounds", &["type_bound_list", "colon_token"]),
 778         ("HasModuleItem", &["items"]),
 779         ("HasLoopBody", &["label", "loop_body"]),
 780         ("HasArgList", &["arg_list"]),
 781     ];
 782
 783     for node in &mut ast.nodes {
 784         for (name, methods) in traits {
 785             extract_struct_trait(node, name, methods);
 786         }
 787     }
 788
 789     let nodes_with_doc_comments = [
 790         "SourceFile",
 791         "Fn",
 792         "Struct",
 793         "Union",
 794         "RecordField",
 795         "TupleField",
 796         "Enum",
 797         "Variant",
 798         "Trait",
 799         "Module",
 800         "Static",
 801         "Const",
 802         "TypeAlias",
 803         "Impl",
 804         "ExternBlock",
 805         "ExternCrate",
 806         "MacroCall",
 807         "MacroRules",
 808         "MacroDef",
 809         "Use",
 810     ];
 811
 812     for node in &mut ast.nodes {
 813         if nodes_with_doc_comments.contains(&&*node.name) {
 814             node.traits.push("HasDocComments".into());
 815         }
 816     }
 817 }
 818
 819 fn extract_struct_trait(node: &mut AstNodeSrc, trait_name: &str, methods: &[&str]) {
 820     let mut to_remove = Vec::new();
 821     for (i, field) in node.fields.iter().enumerate() {
 822         let method_name = field.method_name().to_string();
 823         if methods.iter().any(|&it| it == method_name) {
 824             to_remove.push(i);
 825         }
 826     }
 827     if to_remove.len() == methods.len() {
 828         node.traits.push(trait_name.to_string());
 829         node.remove_field(to_remove);
 830     }
 831 }
 832
 833 fn extract_enum_traits(ast: &mut AstSrc) {
 834     for enm in &mut ast.enums {
 835         if enm.name == "Stmt" {
 836             continue;
 837         }
 838         let nodes = &ast.nodes;
 839         let mut variant_traits = enm
 840             .variants
 841             .iter()
 842             .map(|var| nodes.iter().find(|it| &it.name == var).unwrap())
 843             .map(|node| node.traits.iter().cloned().collect::<BTreeSet<_>>());
 844
 845         let mut enum_traits = match variant_traits.next() {
 846             Some(it) => it,
 847             None => continue,
 848         };
 849         for traits in variant_traits {
 850             enum_traits = enum_traits.intersection(&traits).cloned().collect();
 851         }
 852         enm.traits = enum_traits.into_iter().collect();
 853     }
 854 }
 855
 856 impl AstNodeSrc {
 857     fn remove_field(&mut self, to_remove: Vec<usize>) {
 858         to_remove.into_iter().rev().for_each(|idx| {
 859             self.fields.remove(idx);
 860         });
 861     }
 862 }