treesitter-lang 1.0.1

Generate Tree-sitter grammars (grammar.js and grammar.json) and corpus tests from Rust.
Documentation
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
1001
1002
1003
1004
1005
1006
1007
1008
1009
1010
1011
1012
1013
1014
1015
1016
1017
1018
1019
1020
1021
1022
1023
1024
1025
1026
1027
1028
1029
1030
1031
1032
1033
1034
1035
1036
1037
1038
1039
1040
1041
1042
1043
1044
1045
1046
1047
1048
1049
1050
1051
1052
1053
1054
1055
1056
1057
1058
1059
1060
1061
1062
1063
1064
1065
1066
1067
1068
1069
1070
1071
1072
1073
1074
1075
1076
1077
1078
1079
1080
1081
1082
1083
1084
1085
1086
1087
1088
1089
1090
1091
1092
1093
1094
1095
1096
1097
1098
1099
1100
1101
1102
1103
1104
1105
1106
1107
1108
1109
1110
1111
1112
1113
1114
1115
1116
1117
1118
1119
1120
1121
1122
1123
1124
1125
1126
1127
1128
1129
1130
1131
1132
1133
1134
1135
1136
1137
1138
1139
1140
1141
1142
1143
1144
1145
1146
1147
1148
1149
1150
//! Grammar validation: the checks `tree-sitter generate` would otherwise fail
//! on (or, in two cases, crash or hang on), run before anything is emitted.
//!
//! Every check mirrors a rule of tree-sitter's own, probed against the CLI.
//! They come in two kinds, as in tree-sitter:
//!
//! - **Load-time checks** apply to every rule, because `grammar.js` evaluates
//!   every rule: names are identifiers, symbols resolve, tokens contain no
//!   symbols, patterns are not empty and are regular expressions JavaScript
//!   accepts (see [`crate::pattern`]).
//! - **Reachability checks** apply only to rules reachable from the start
//!   rule or the extras, because tree-sitter drops the rest before building
//!   the parser: strings are not empty, patterns are ones tree-sitter's own
//!   regular expression parser accepts, a rule other rules refer to cannot
//!   match nothing, nor can what a `repeat` repeats, no rules form a cycle
//!   of each being just the next, and supertypes produce one node per
//!   alternative.
//!
//! Tree-sitter merges identical tokens, so a rule whose whole body is a token
//! stays a token only if that token appears nowhere else among the reachable
//! rules; the word rule and any rule sharing an external's name must be such
//! a token. Some checks are stricter than tree-sitter, because what they
//! catch is always a mistake: an empty `choice` (accepted silently), an
//! `inline` entry naming nothing (only warned about), and empty patterns and
//! empty strings inside tokens (accepted in some places, but able to match
//! only nothing). Indirect recursion through
//! inlined rules, which makes tree-sitter loop forever, and a nullable extra
//! rule, which makes it crash, are reported as errors.
//!
//! Parse tables are not built here, so what tree-sitter finds while building
//! them — conflicts, and extras whose end it cannot tell — is left to it.
//! Differential fuzzing against the tree-sitter CLI, random grammars run
//! through both, found no other disagreement.
//!
//! Every walk is iterative, so a rule nested arbitrarily deep is checked
//! without recursion.

use alloc::{format, string::String, vec, vec::Vec};
use core::ptr;

use crate::{
    Error, Grammar, Rule,
    pattern::{Checker, Invalid},
    rule::{Expr, Prec, Text},
};

/// What a name refers to.
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub(crate) enum Def {
    /// The rule at this position in `Grammar::rules`.
    Rule(usize),
    /// An external token.
    External,
}

/// Every rule and external of a grammar, sorted by name for binary search.
///
/// A name that is both a rule and an external resolves to the rule; a name
/// defined as two rules resolves to the first, and is reported by
/// [`Index::duplicate`].
pub(crate) struct Index<'g> {
    entries: Vec<(&'g str, Def)>,
}

impl<'g> Index<'g> {
    pub(crate) fn new(grammar: &'g Grammar) -> Index<'g> {
        let mut entries = Vec::with_capacity(grammar.rules.len() + grammar.externals.len());
        entries.extend(
            grammar
                .rules
                .iter()
                .enumerate()
                .map(|(i, (name, _))| (&**name, Def::Rule(i))),
        );
        entries.extend(
            grammar
                .externals
                .iter()
                .map(|name| (&**name, Def::External)),
        );
        // Rules sort before externals of the same name, and same-named rules
        // in definition order, so the first entry for a name is the one it
        // resolves to.
        entries.sort_unstable_by(|a, b| a.0.cmp(b.0).then(rank(a.1).cmp(&rank(b.1))));
        Index { entries }
    }

    /// What `name` refers to, if anything.
    pub(crate) fn get(&self, name: &str) -> Option<Def> {
        let at = self.entries.partition_point(|(n, _)| *n < name);
        match self.entries.get(at) {
            Some(&(n, def)) if n == name => Some(def),
            _ => None,
        }
    }

    /// The rule name defined more than once whose second definition comes
    /// first, so the report follows definition order.
    fn duplicate(&self) -> Option<&'g str> {
        self.entries
            .windows(2)
            .filter_map(|pair| match (pair[0], pair[1]) {
                ((a, Def::Rule(_)), (b, Def::Rule(second))) if a == b => Some((second, a)),
                _ => None,
            })
            .min_by_key(|&(second, _)| second)
            .map(|(_, name)| name)
    }
}

/// The sort rank of a definition among those sharing a name.
fn rank(def: Def) -> usize {
    match def {
        Def::Rule(i) => i,
        Def::External => usize::MAX,
    }
}

/// Which rules refer to which, outside tokens, in compressed form: the rules
/// rule `i` refers to are `edges[starts[i]..starts[i + 1]]`.
struct Graph {
    starts: Vec<usize>,
    edges: Vec<usize>,
    /// The same form for the rules each rule can be alone — referred to at
    /// an alternative position, through `choice`, `prec`, `field`, and
    /// `alias` — itself excluded.
    unit_starts: Vec<usize>,
    units: Vec<usize>,
    /// Rules named by extras that are a lone symbol, in extras order.
    extra_roots: Vec<usize>,
}

impl Graph {
    fn edges(&self, rule: usize) -> &[usize] {
        &self.edges[self.starts[rule]..self.starts[rule + 1]]
    }

    fn units(&self, rule: usize) -> &[usize] {
        &self.units[self.unit_starts[rule]..self.unit_starts[rule + 1]]
    }
}

/// Which rules tree-sitter keeps, and which of those other rules refer to.
struct Reach {
    reachable: Vec<bool>,
    used: Vec<bool>,
}

/// Validates a grammar, returning the first problem found.
pub(crate) fn validate(grammar: &Grammar) -> Result<(), Error> {
    names(grammar)?;
    let index = Index::new(grammar);
    if let Some(name) = index.duplicate() {
        return Err(Error::DuplicateRule {
            name: String::from(name),
        });
    }
    let mut patterns = Checker::default();
    let graph = load(grammar, &index, &mut patterns)?;
    references(grammar, &index)?;
    let reach = reach(grammar, &graph);
    unit_cycles(grammar, &graph, &reach)?;
    reachable_rules(grammar, &reach, &mut patterns)?;
    word(grammar, &index, &reach)?;
    externals(grammar, &index, &reach)?;
    inline(grammar, &index, &reach)?;
    supertypes(grammar, &index, &reach)
}

/// The grammar's, rules', and externals' names, and the start rule.
fn names(grammar: &Grammar) -> Result<(), Error> {
    identifier(&grammar.name)?;
    let Some((start, _)) = grammar.rules.first() else {
        return Err(Error::NoRules);
    };
    for name in grammar
        .rules
        .iter()
        .map(|(name, _)| name)
        .chain(&grammar.externals)
    {
        identifier(name)?;
        // `grammar.js` holds rules in an object literal and looks symbols up
        // as properties, where `__proto__` means the prototype, not a key.
        if name == "__proto__" {
            return Err(invalid_name(name));
        }
    }
    if is_hidden(start) {
        return Err(Error::HiddenStart {
            name: String::from(&**start),
        });
    }
    Ok(())
}

/// Whether a name is a valid tree-sitter identifier: an ASCII letter or `_`,
/// then ASCII letters, digits, and `_`.
fn identifier(name: &str) -> Result<(), Error> {
    let bytes = name.as_bytes();
    let valid = matches!(bytes.first(), Some(b) if b.is_ascii_alphabetic() || *b == b'_')
        && bytes[1..]
            .iter()
            .all(|b| b.is_ascii_alphanumeric() || *b == b'_');
    if valid {
        Ok(())
    } else {
        Err(invalid_name(name))
    }
}

fn invalid_name(name: &str) -> Error {
    Error::InvalidName {
        name: String::from(name),
    }
}

/// Whether a rule name makes the rule hidden.
#[inline]
pub(crate) fn is_hidden(name: &str) -> bool {
    name.starts_with('_')
}

fn undefined(symbol: &str, rule: &str) -> Error {
    Error::UndefinedSymbol {
        symbol: String::from(symbol),
        rule: String::from(rule),
    }
}

/// The load-time checks on every rule body and every extra, collecting the
/// references between rules on the way.
fn load(grammar: &Grammar, index: &Index<'_>, patterns: &mut Checker) -> Result<Graph, Error> {
    let count = grammar.rules.len();
    let mut graph = Graph {
        starts: Vec::with_capacity(count + 1),
        edges: Vec::new(),
        unit_starts: Vec::with_capacity(count + 1),
        units: Vec::new(),
        extra_roots: Vec::new(),
    };
    let mut stack = Vec::new();
    for (i, (name, body)) in grammar.rules.iter().enumerate() {
        graph.starts.push(graph.edges.len());
        graph.unit_starts.push(graph.units.len());
        let refs = Refs {
            edges: &mut graph.edges,
            units: &mut graph.units,
            rule: i,
        };
        load_rule(body, name, false, index, &mut stack, refs, patterns)?;
    }
    graph.starts.push(graph.edges.len());
    graph.unit_starts.push(graph.units.len());

    let (mut edges, mut units) = (Vec::new(), Vec::new());
    for extra in grammar.extras.iter().flatten() {
        match &extra.0 {
            // A lone symbol names a rule (or external) that may appear
            // anywhere; anything else is lexed as a token.
            Expr::Symbol(name) => match index.get(name) {
                None => return Err(undefined(name, "extras")),
                Some(Def::Rule(i)) => graph.extra_roots.push(i),
                Some(Def::External) => {}
            },
            _ => {
                // A token refers to no rules, so nothing is collected.
                let refs = Refs {
                    edges: &mut edges,
                    units: &mut units,
                    rule: usize::MAX,
                };
                load_rule(extra, "extras", true, index, &mut stack, refs, patterns)?;
            }
        }
    }
    Ok(graph)
}

/// Where [`load_rule`] records the rules a rule refers to.
struct Refs<'a> {
    /// Every rule referred to outside tokens.
    edges: &'a mut Vec<usize>,
    /// The rules referred to at an alternative position, other than itself.
    units: &'a mut Vec<usize>,
    /// The rule being loaded.
    rule: usize,
}

/// Checks one rule body in source order: symbols resolve and are not inside
/// a token, patterns are not empty and are regular expressions JavaScript
/// accepts, choices have alternatives, and field and alias names are
/// identifiers. Records the rules it refers to in `refs`.
fn load_rule<'g>(
    root: &'g Rule,
    rule: &str,
    lexical: bool,
    index: &Index<'_>,
    stack: &mut Vec<(&'g Rule, bool, bool)>,
    refs: Refs<'_>,
    patterns: &mut Checker,
) -> Result<(), Error> {
    stack.clear();
    stack.push((root, lexical, true));
    while let Some((node, in_token, unit)) = stack.pop() {
        match &node.0 {
            Expr::Symbol(name) => {
                let def = index.get(name).ok_or_else(|| undefined(name, rule))?;
                if in_token {
                    return Err(Error::SymbolInToken {
                        symbol: String::from(&**name),
                        rule: String::from(rule),
                    });
                }
                if let Def::Rule(i) = def {
                    refs.edges.push(i);
                    if unit && i != refs.rule {
                        refs.units.push(i);
                    }
                }
            }
            Expr::Pattern(text) if text.is_empty() => {
                return Err(Error::EmptyString {
                    rule: String::from(rule),
                });
            }
            // `grammar.js` evaluates every rule, so every pattern must be a
            // regular expression literal its JavaScript runtime accepts.
            Expr::Pattern(text) => patterns
                .javascript(text)
                .map_err(|problem| invalid_pattern(rule, text, problem))?,
            Expr::Choice(rules) if rules.is_empty() => {
                return Err(Error::EmptyChoice {
                    rule: String::from(rule),
                });
            }
            Expr::Field(name, _) | Expr::Alias(name, _) => identifier(name)?,
            _ => {}
        }
        let in_token = in_token || matches!(node.0, Expr::Token(_) | Expr::Immediate(_));
        let unit = unit
            && matches!(
                node.0,
                Expr::Choice(_) | Expr::Prec(..) | Expr::Field(..) | Expr::Alias(..)
            );
        stack.extend(
            node.children()
                .iter()
                .rev()
                .map(|child| (child, in_token, unit)),
        );
    }
    Ok(())
}

/// The names in `word`, `conflicts`, `inline`, and `supertypes` resolve.
fn references(grammar: &Grammar, index: &Index<'_>) -> Result<(), Error> {
    let defined = |name: &Text, place: &str| match index.get(name) {
        Some(_) => Ok(()),
        None => Err(undefined(name, place)),
    };
    if let Some(word) = &grammar.word {
        defined(word, "word")?;
    }
    for name in grammar.conflicts.iter().flatten() {
        defined(name, "conflicts")?;
    }
    for name in &grammar.inline {
        defined(name, "inline")?;
    }
    for name in &grammar.supertypes {
        defined(name, "supertypes")?;
    }
    Ok(())
}

/// The rules reachable from the start rule and the extras, and which of
/// them other reachable rules (or the extras) refer to.
fn reach(grammar: &Grammar, graph: &Graph) -> Reach {
    let count = grammar.rules.len();
    let mut reachable = vec![false; count];
    let mut used = vec![false; count];
    let mut queue = Vec::with_capacity(count);
    for &root in [0].iter().chain(&graph.extra_roots) {
        if !reachable[root] {
            reachable[root] = true;
            queue.push(root);
        }
    }
    for &root in &graph.extra_roots {
        used[root] = true;
    }
    while let Some(rule) = queue.pop() {
        for &next in graph.edges(rule) {
            used[next] = true;
            if !reachable[next] {
                reachable[next] = true;
                queue.push(next);
            }
        }
    }
    Reach { reachable, used }
}

/// For every reachable rule, in definition order: no empty string, every
/// pattern one tree-sitter's regular expression parser accepts, and nothing
/// that can match nothing where tree-sitter needs something — the rule
/// itself if another rule refers to it, and anything a `repeat` or `repeat1`
/// repeats. Then the patterns in the extras, which tree-sitter always keeps.
fn reachable_rules(grammar: &Grammar, reach: &Reach, patterns: &mut Checker) -> Result<(), Error> {
    let mut walk = Vec::new();
    let mut frames = Vec::new();
    for (i, (name, body)) in grammar.rules.iter().enumerate() {
        if !reach.reachable[i] {
            continue;
        }
        // Tree-sitter refuses an empty string outside a token, and inside
        // one wherever it decides the token's value; elsewhere in a token it
        // can only match nothing. All are refused.
        walk.clear();
        walk.push(body);
        while let Some(node) = walk.pop() {
            match &node.0 {
                Expr::String(text) if text.is_empty() => {
                    return Err(Error::EmptyString {
                        rule: String::from(&**name),
                    });
                }
                Expr::Pattern(text) => patterns
                    .tree_sitter(text)
                    .map_err(|problem| invalid_pattern(name, text, problem))?,
                _ => walk.extend(node.children()),
            }
        }
        let (empty, empty_repeat) = nullability(body, &mut frames);
        if empty_repeat || (empty && reach.used[i]) {
            return Err(Error::MatchesEmpty {
                rule: String::from(&**name),
            });
        }
    }
    for extra in grammar.extras.iter().flatten() {
        walk.clear();
        walk.push(extra);
        while let Some(node) = walk.pop() {
            match &node.0 {
                Expr::Pattern(text) => patterns
                    .tree_sitter(text)
                    .map_err(|problem| invalid_pattern("extras", text, problem))?,
                _ => walk.extend(node.children()),
            }
        }
    }
    Ok(())
}

/// The error for a pattern that is not a regular expression tree-sitter can
/// use. [`Error`] is frozen, so this reuses [`Error::EmptyString`], the
/// variant for a pattern that cannot be written as a regular expression
/// literal: `rule` holds the rule's name, `: `, and what is wrong and where.
/// Rule names never contain `: `, which is how `Display` tells the two
/// apart.
fn invalid_pattern(rule: &str, pattern: &str, problem: Invalid) -> Error {
    const PREVIEW: usize = 40;
    let mut preview = String::new();
    for (n, c) in pattern.chars().enumerate() {
        if n == PREVIEW {
            preview.push('…');
            break;
        }
        if c.is_control() || c == '\u{2028}' || c == '\u{2029}' {
            preview.extend(c.escape_default());
        } else {
            preview.push(c);
        }
    }
    Error::EmptyString {
        rule: format!(
            "{rule}: {} at byte {} of `{preview}`",
            problem.reason, problem.at
        ),
    }
}

/// One frame of [`nullability`]: a rule whose parts are being evaluated.
struct Frame<'g> {
    rule: &'g Rule,
    next: usize,
    value: bool,
}

/// Whether tree-sitter would give this rule body an empty production — can
/// it match nothing without consuming any token or symbol? — and whether
/// anything it repeats (outside tokens) could.
///
/// Symbols and tokens consume something by definition; a symbol that can
/// itself match nothing is reported at its own rule. Evaluated bottom-up with
/// an explicit stack, visiting every part once.
fn nullability<'g>(root: &'g Rule, frames: &mut Vec<Frame<'g>>) -> (bool, bool) {
    frames.clear();
    let mut empty_repeat = false;
    let mut current = root;
    loop {
        // Descend until a part's value is known.
        let mut value = match &current.0 {
            Expr::Blank => true,
            Expr::String(_)
            | Expr::Pattern(_)
            | Expr::Symbol(_)
            | Expr::Token(_)
            | Expr::Immediate(_) => false,
            Expr::Seq(rules) | Expr::Choice(rules) => match rules.first() {
                // An empty choice never matches (and is reported separately).
                None => matches!(current.0, Expr::Seq(_)),
                Some(first) => {
                    let value = matches!(current.0, Expr::Seq(_));
                    frames.push(Frame {
                        rule: current,
                        next: 1,
                        value,
                    });
                    current = first;
                    continue;
                }
            },
            Expr::Repeat(inner)
            | Expr::Repeat1(inner)
            | Expr::Field(_, inner)
            | Expr::Alias(_, inner)
            | Expr::Prec(_, _, inner) => {
                frames.push(Frame {
                    rule: current,
                    next: 1,
                    value: false,
                });
                current = inner;
                continue;
            }
        };
        // Return values upward until a parent needs another part.
        loop {
            let Some(frame) = frames.last_mut() else {
                return (value, empty_repeat);
            };
            let parent: &'g Rule = frame.rule;
            match &parent.0 {
                Expr::Seq(rules) | Expr::Choice(rules) => {
                    frame.value = if matches!(parent.0, Expr::Seq(_)) {
                        frame.value && value
                    } else {
                        frame.value || value
                    };
                    if let Some(next) = rules.get(frame.next) {
                        frame.next += 1;
                        current = next;
                        break;
                    }
                    value = frame.value;
                }
                Expr::Repeat(_) => {
                    empty_repeat |= value;
                    value = true;
                }
                Expr::Repeat1(_) => empty_repeat |= value,
                _ => {}
            }
            let _finished = frames.pop();
        }
    }
}

/// No cycle of two or more reachable rules in which each rule can be just the
/// next one — `a` can be `b` alone and `b` can be `a` alone — which
/// tree-sitter refuses as an "indirectly recursive rule". A rule can be
/// another alone when that rule is one of its alternatives, through
/// `choice`, `optional`, and the `prec`, `field`, and `alias` wrappers (not
/// through `seq` or a repetition). A rule that is itself directly is left to
/// tree-sitter, which reports it as a conflict — except a hidden rule that is
/// itself under a precedence, on which tree-sitter hangs.
fn unit_cycles(grammar: &Grammar, graph: &Graph, reach: &Reach) -> Result<(), Error> {
    const WHITE: u8 = 0;
    const GRAY: u8 = 1;
    const BLACK: u8 = 2;
    let count = grammar.rules.len();

    // A hidden rule that can be itself under a precedence makes tree-sitter
    // loop forever.
    let mut walk = Vec::new();
    for (i, (name, body)) in grammar.rules.iter().enumerate() {
        if reach.reachable[i] && is_hidden(name) && itself_under_precedence(body, name, &mut walk) {
            return Err(Error::IndirectRecursion {
                rule: String::from(&**name),
            });
        }
    }

    let mut color = vec![WHITE; count];
    let mut stack: Vec<(usize, usize)> = Vec::new();
    for start in 0..count {
        if color[start] != WHITE || !reach.reachable[start] {
            continue;
        }
        color[start] = GRAY;
        stack.push((start, 0));
        while let Some(top) = stack.last_mut() {
            let (rule, at) = *top;
            let Some(&next) = graph.units(rule).get(at) else {
                color[rule] = BLACK;
                let _finished = stack.pop();
                continue;
            };
            top.1 += 1;
            if color[next] == GRAY {
                return Err(Error::IndirectRecursion {
                    rule: String::from(&*grammar.rules[next].0),
                });
            }
            if color[next] == WHITE {
                color[next] = GRAY;
                stack.push((next, 0));
            }
        }
    }
    Ok(())
}

/// Whether one alternative of a rule body is the rule itself under a
/// non-zero `prec`, `prec.left`, or `prec.right` — seen through `choice` and
/// sequences whose other parts are blank, but not through `field` or `alias`.
/// Tree-sitter never finishes generating a parser for a hidden rule like
/// that; a visible one, precedence zero, or `prec.dynamic` it handles.
fn itself_under_precedence<'g>(
    body: &'g Rule,
    name: &str,
    walk: &mut Vec<(&'g Rule, bool)>,
) -> bool {
    walk.clear();
    walk.push((body, false));
    while let Some((node, ranked)) = walk.pop() {
        match &node.0 {
            Expr::Symbol(symbol) if ranked && symbol == name => return true,
            Expr::Choice(alternatives) => {
                walk.extend(alternatives.iter().map(|a| (a, ranked)));
            }
            Expr::Prec(kind, level, inner) => {
                let ranked = ranked || (*kind != Prec::Dynamic && *level != 0);
                walk.push((inner, ranked));
            }
            Expr::Seq(parts) => {
                let mut solid = parts.iter().filter(|p| !matches!(p.0, Expr::Blank));
                if let (Some(part), None) = (solid.next(), solid.next()) {
                    walk.push((part, ranked));
                }
            }
            _ => {}
        }
    }
    false
}

/// Whether tree-sitter turns rule `i` into a token of its own: it is not the
/// start rule, its whole body is a token, and no reachable rule uses an
/// identical token anywhere else (tree-sitter would merge the two, making
/// the rule a non-terminal wrapper around the shared token). A hidden rule
/// whose token is just a string literal is never one: tree-sitter treats it
/// as that anonymous string. Supertypes count as hidden — tree-sitter hides
/// them before it looks for tokens — except when it decides what may be
/// inlined, which it does by the rule's own name (`supertypes_hidden`).
fn is_token_rule(grammar: &Grammar, reach: &Reach, i: usize, supertypes_hidden: bool) -> bool {
    let (name, target) = &grammar.rules[i];
    let hidden = is_hidden(name) || (supertypes_hidden && grammar.supertypes.contains(name));
    if i == 0 || !target.is_terminal() || (hidden && is_literal(target)) {
        return false;
    }
    let key = token_key(target);
    let mut walk = Vec::new();
    for (j, (_, body)) in grammar.rules.iter().enumerate() {
        if !reach.reachable[j] {
            continue;
        }
        walk.clear();
        walk.push(body);
        while let Some(node) = walk.pop() {
            if node.is_terminal() {
                if !ptr::eq(node, target) && token_key(node).same(key) {
                    return false;
                }
            } else {
                walk.extend(node.children());
            }
        }
    }
    true
}

/// A token as tree-sitter compares it with others: `token` around a single
/// string or pattern is that string or pattern.
fn token_key(rule: &Rule) -> &Rule {
    match &rule.0 {
        Expr::Token(inner) if matches!(inner.0, Expr::String(_) | Expr::Pattern(_)) => inner,
        _ => rule,
    }
}

/// Whether a token is just a string literal: a string, possibly inside one
/// `token` or `token.immediate`, and within that any number of `prec`,
/// `field`, and `alias`, which do not change what is lexed.
fn is_literal(rule: &Rule) -> bool {
    let mut rule = match &rule.0 {
        Expr::Token(inner) | Expr::Immediate(inner) => inner,
        _ => rule,
    };
    loop {
        match &rule.0 {
            Expr::Prec(_, _, inner) | Expr::Field(_, inner) | Expr::Alias(_, inner) => rule = inner,
            Expr::String(_) => return true,
            _ => return false,
        }
    }
}

/// The word rule is a token, or an external.
fn word(grammar: &Grammar, index: &Index<'_>, reach: &Reach) -> Result<(), Error> {
    let Some(word) = &grammar.word else {
        return Ok(());
    };
    match index.get(word) {
        Some(Def::Rule(i)) if !is_token_rule(grammar, reach, i, true) => Err(Error::WordNotToken {
            name: String::from(&**word),
        }),
        _ => Ok(()),
    }
}

/// An external may share its name with a rule only if that rule is a token,
/// which serves as the fallback when the external scanner declines.
fn externals(grammar: &Grammar, index: &Index<'_>, reach: &Reach) -> Result<(), Error> {
    for name in &grammar.externals {
        if let Some(Def::Rule(i)) = index.get(name) {
            if !is_token_rule(grammar, reach, i, true) {
                return Err(Error::InvalidExternal {
                    name: String::from(&**name),
                });
            }
        }
    }
    Ok(())
}

/// Inlined rules: not the start rule, not a token, not an external, and not
/// recursive through inlined rules alone.
fn inline(grammar: &Grammar, index: &Index<'_>, reach: &Reach) -> Result<(), Error> {
    const WHITE: u8 = 0;
    const GRAY: u8 = 1;
    const BLACK: u8 = 2;

    if grammar.inline.is_empty() {
        return Ok(());
    }
    let count = grammar.rules.len();
    let mut inlined = vec![false; count];
    for name in &grammar.inline {
        let invalid = || Error::InvalidInline {
            name: String::from(&**name),
        };
        let Some(Def::Rule(i)) = index.get(name) else {
            return Err(invalid());
        };
        // Tree-sitter refuses to inline the rules it lexes as tokens.
        if i == 0 || is_token_rule(grammar, reach, i, false) {
            return Err(invalid());
        }
        inlined[i] = true;
    }

    // A cycle through inlined rules alone would expand forever: depth-first
    // search over the references between inlined rules, in inline order. A
    // reference inside a repetition does not count: tree-sitter moves it
    // into a helper rule of its own, which is not inlined.
    let mut edges: Vec<Vec<usize>> = vec![Vec::new(); count];
    let mut walk = Vec::new();
    for (i, (_, body)) in grammar.rules.iter().enumerate() {
        if !inlined[i] {
            continue;
        }
        walk.clear();
        walk.push(body);
        while let Some(node) = walk.pop() {
            match &node.0 {
                Expr::Symbol(name) => {
                    if let Some(Def::Rule(j)) = index.get(name) {
                        if inlined[j] {
                            edges[i].push(j);
                        }
                    }
                }
                Expr::Repeat(_) | Expr::Repeat1(_) | Expr::Token(_) | Expr::Immediate(_) => {}
                _ => walk.extend(node.children()),
            }
        }
    }
    let mut color = vec![WHITE; count];
    let mut stack: Vec<(usize, usize)> = Vec::new();
    for name in &grammar.inline {
        let Some(Def::Rule(start)) = index.get(name) else {
            continue;
        };
        if color[start] != WHITE {
            continue;
        }
        color[start] = GRAY;
        stack.push((start, 0));
        while let Some(top) = stack.last_mut() {
            let (rule, at) = *top;
            let Some(&next) = edges[rule].get(at) else {
                color[rule] = BLACK;
                let _finished = stack.pop();
                continue;
            };
            top.1 += 1;
            if color[next] == GRAY {
                return Err(Error::InvalidInline {
                    name: String::from(&*grammar.rules[next].0),
                });
            }
            if color[next] == WHITE {
                color[next] = GRAY;
                stack.push((next, 0));
            }
        }
    }
    Ok(())
}

/// Supertypes: rules, and — when reachable — not a token with a pattern in
/// it, never themselves, and producing a single node in every alternative.
fn supertypes(grammar: &Grammar, index: &Index<'_>, reach: &Reach) -> Result<(), Error> {
    if grammar.supertypes.is_empty() {
        return Ok(());
    }
    let nodes = NodeCounts::new(grammar, index);
    let mut walk = Vec::new();
    let mut expanded = Vec::new();
    for name in &grammar.supertypes {
        let invalid = || Error::InvalidSupertype {
            name: String::from(&**name),
        };
        let Some(Def::Rule(i)) = index.get(name) else {
            return Err(invalid());
        };
        // An inlined supertype is expanded away before supertypes are
        // looked at, and an unreachable one is dropped.
        if !reach.reachable[i] || grammar.inline.contains(name) {
            continue;
        }
        let body = &grammar.rules[i].1;
        // A supertype is hidden, so a literal is not a token here; one that
        // tree-sitter lexes as a token of its own is refused.
        if is_token_rule(grammar, reach, i, true) || nodes.most(body) > 1 {
            return Err(invalid());
        }
        // A supertype that can be itself — directly, or through the hidden
        // and inlined rules tree-sitter expands in place — would make its node
        // types depend on themselves. An alias names something else.
        walk.clear();
        walk.push(body);
        expanded.clear();
        expanded.resize(grammar.rules.len(), false);
        while let Some(node) = walk.pop() {
            match &node.0 {
                Expr::Symbol(symbol) if symbol == name => return Err(invalid()),
                Expr::Symbol(symbol) => {
                    if let Some(Def::Rule(j)) = index.get(symbol) {
                        if nodes.expands[j] && !expanded[j] {
                            expanded[j] = true;
                            walk.push(&grammar.rules[j].1);
                        }
                    }
                }
                Expr::Alias(..) | Expr::Token(_) | Expr::Immediate(_) => {}
                _ => walk.extend(node.children()),
            }
        }
    }
    Ok(())
}

/// The most nodes one alternative of a rule can put in the tree, capped at
/// two ("more than one"), with hidden and inlined rules expanded in place as
/// tree-sitter expands them.
struct NodeCounts<'g, 'i> {
    index: &'i Index<'g>,
    /// Per rule: whether references to it expand, and the count it expands
    /// to.
    expands: Vec<bool>,
    counts: Vec<u8>,
}

impl<'g, 'i> NodeCounts<'g, 'i> {
    fn new(grammar: &'g Grammar, index: &'i Index<'g>) -> Self {
        let expands: Vec<bool> = grammar
            .rules
            .iter()
            .map(|(name, body)| {
                (is_hidden(name) || grammar.inline.contains(name)) && !body.is_terminal()
            })
            .collect();
        let mut counts = NodeCounts {
            index,
            counts: vec![0; expands.len()],
            expands,
        };
        // Counts only grow and are capped, so this settles, including
        // through recursive hidden rules.
        let mut changed = true;
        while changed {
            changed = false;
            for (i, (_, body)) in grammar.rules.iter().enumerate() {
                if counts.expands[i] {
                    let count = counts.most(body);
                    if count > counts.counts[i] {
                        counts.counts[i] = count;
                        changed = true;
                    }
                }
            }
        }
        counts
    }

    /// The most nodes one alternative of `root` produces, capped at two.
    ///
    /// An alias renames each element of what it wraps, so beneath one a
    /// hidden rule is a single (renamed) node rather than expanded.
    fn most(&self, root: &Rule) -> u8 {
        // Each frame: a rule whose parts are being combined, the next part,
        // the value so far, and whether an alias encloses the rule.
        let mut frames: Vec<(&Rule, usize, u8, bool)> = Vec::new();
        let mut current = root;
        let mut aliased = false;
        loop {
            let mut value = match &current.0 {
                Expr::Blank => 0,
                Expr::String(_) | Expr::Pattern(_) | Expr::Token(_) | Expr::Immediate(_) => 1,
                Expr::Symbol(name) => match self.index.get(name) {
                    Some(Def::Rule(j)) if self.expands[j] && !aliased => self.counts[j],
                    _ => 1,
                },
                Expr::Choice(rules) if rules.is_empty() => 0,
                // Tree-sitter turns a repetition into a helper rule that
                // refers to itself twice: several nodes, whatever it repeats.
                Expr::Repeat(_) | Expr::Repeat1(_) => 2,
                _ => {
                    // Sequences, choices, fields, precedences, aliases:
                    // combine their parts. A sequence is never empty (an
                    // empty one is a blank).
                    frames.push((current, 1, 0, aliased));
                    aliased = aliased || matches!(current.0, Expr::Alias(..));
                    current = &current.children()[0];
                    continue;
                }
            };
            loop {
                let Some(frame) = frames.last_mut() else {
                    return value;
                };
                let parent = frame.0;
                frame.2 = match parent.0 {
                    Expr::Seq(_) => frame.2.saturating_add(value).min(2),
                    Expr::Choice(_) => frame.2.max(value),
                    _ => value,
                };
                if let Some(next) = parent.children().get(frame.1) {
                    frame.1 += 1;
                    aliased = frame.3 || matches!(parent.0, Expr::Alias(..));
                    current = next;
                    break;
                }
                value = frame.2;
                let _finished = frames.pop();
            }
        }
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    fn empty(rule: &Rule) -> bool {
        nullability(rule, &mut Vec::new()).0
    }

    fn empty_repeat(rule: &Rule) -> bool {
        nullability(rule, &mut Vec::new()).1
    }

    #[test]
    fn test_nullability_leaves() {
        assert!(empty(&Rule::blank()));
        assert!(!empty(&Rule::string("a")));
        assert!(!empty(&Rule::pattern("a*")));
        assert!(!empty(&Rule::symbol("a")));
        assert!(!empty(&Rule::token(Rule::blank())));
    }

    #[test]
    fn test_nullability_combinators() {
        assert!(empty(&Rule::seq([])));
        assert!(!empty(&Rule::choice([])));
        assert!(empty(&Rule::repeat(Rule::string("a"))));
        assert!(!empty(&Rule::repeat1(Rule::string("a"))));
        assert!(empty(&Rule::repeat1(Rule::blank())));
        assert!(empty(&Rule::optional(Rule::string("a"))));
        assert!(empty(&Rule::seq([
            Rule::blank(),
            Rule::optional(Rule::string("a"))
        ])));
        assert!(!empty(&Rule::seq([Rule::blank(), Rule::string("a")])));
        assert!(!empty(&Rule::seq([Rule::string("a"), Rule::blank()])));
        assert!(empty(&Rule::choice([Rule::string("a"), Rule::blank()])));
        assert!(!empty(&Rule::choice([
            Rule::string("a"),
            Rule::symbol("b")
        ])));
        assert!(empty(&Rule::field(
            "f",
            Rule::prec(1, Rule::repeat(Rule::string("a")))
        )));
        assert!(!empty(&Rule::alias(Rule::string("a"), "b")));
    }

    #[test]
    fn test_nullability_finds_empty_repeats_anywhere_outside_tokens() {
        assert!(!empty_repeat(&Rule::repeat(Rule::string("a"))));
        assert!(empty_repeat(&Rule::repeat(Rule::optional(Rule::string(
            "a"
        )))));
        assert!(empty_repeat(&Rule::repeat1(Rule::blank())));
        assert!(empty_repeat(&Rule::repeat1(Rule::repeat(Rule::string(
            "a"
        )))));
        let nested = Rule::seq([
            Rule::string("x"),
            Rule::choice([
                Rule::symbol("y"),
                Rule::repeat(Rule::optional(Rule::symbol("z"))),
            ]),
        ]);
        assert!(!empty(&nested));
        assert!(empty_repeat(&nested));
        // Inside a token, repetition is lexical and may match nothing.
        assert!(!empty_repeat(&Rule::token(Rule::repeat(Rule::optional(
            Rule::string("a")
        )))));
    }

    #[test]
    fn test_nullability_deep_chain_is_iterative() {
        let mut rule = Rule::blank();
        for _ in 0..100_000 {
            rule = Rule::seq([Rule::field("f", rule)]);
        }
        assert!(empty(&rule));
    }

    #[test]
    fn test_identifier_rules() {
        for ok in ["a", "_", "_a1", "Snake_Case9", "class"] {
            assert_eq!(identifier(ok), Ok(()), "{ok}");
        }
        for bad in ["", "1a", "a-b", "a b", "é", "a.b", "$a"] {
            assert!(identifier(bad).is_err(), "{bad}");
        }
    }

    #[test]
    fn test_index_resolves_rules_before_externals() {
        let g = Grammar::new("g")
            .rule("b", Rule::string("b"))
            .rule("a", Rule::string("a"))
            .external("a")
            .external("z");
        let index = Index::new(&g);
        assert_eq!(index.get("a"), Some(Def::Rule(1)));
        assert_eq!(index.get("b"), Some(Def::Rule(0)));
        assert_eq!(index.get("z"), Some(Def::External));
        assert_eq!(index.get("c"), None);
        assert_eq!(index.duplicate(), None);
    }

    #[test]
    fn test_duplicate_reports_earliest_second_definition() {
        let g = Grammar::new("g")
            .rule("s", Rule::string("s"))
            .rule("z", Rule::string("1"))
            .rule("a", Rule::string("1"))
            .rule("z", Rule::string("2"))
            .rule("a", Rule::string("2"));
        assert_eq!(Index::new(&g).duplicate(), Some("z"));
    }

    #[test]
    fn test_reach_follows_references_and_extras() {
        let g = Grammar::new("g")
            .extra(Rule::symbol("note"))
            .rule("s", Rule::repeat(Rule::symbol("a")))
            .rule("a", Rule::string("a"))
            .rule("orphan", Rule::symbol("a"))
            .rule("note", Rule::seq([Rule::string("#"), Rule::symbol("text")]))
            .rule("text", Rule::pattern("[a-z]+"));
        let index = Index::new(&g);
        let graph = load(&g, &index, &mut Checker::default());
        assert!(graph.is_ok());
        let Ok(graph) = graph else { return };
        let reach = reach(&g, &graph);
        assert_eq!(reach.reachable, [true, true, false, true, true]);
        assert_eq!(reach.used, [false, true, false, true, true]);
    }

    #[test]
    fn test_node_counts_expand_hidden_rules() {
        let g = Grammar::new("g")
            .rule("s", Rule::blank())
            .rule(
                "_one",
                Rule::choice([Rule::symbol("a"), Rule::symbol("_nested")]),
            )
            .rule("_nested", Rule::symbol("a"))
            .rule("_two", Rule::seq([Rule::symbol("a"), Rule::string(";")]))
            .rule(
                "_list",
                Rule::seq([Rule::symbol("a"), Rule::optional(Rule::symbol("_list"))]),
            )
            .rule("a", Rule::string("a"));
        let index = Index::new(&g);
        let counts = NodeCounts::new(&g, &index);
        let most = |name: &str| match index.get(name) {
            Some(Def::Rule(i)) => counts.most(&g.rules[i].1),
            _ => u8::MAX,
        };
        assert_eq!(most("s"), 0);
        assert_eq!(most("_one"), 1);
        assert_eq!(most("_two"), 2);
        assert_eq!(most("_list"), 2);
        assert_eq!(counts.most(&Rule::repeat(Rule::symbol("a"))), 2);
        assert_eq!(counts.most(&Rule::repeat(Rule::blank())), 2);
        assert_eq!(counts.most(&Rule::alias(Rule::symbol("_two"), "x")), 1);
    }
}