Skip to main content

tabnas/
merge.rs

1// Copyright (c) 2013-2026 Richard Rodger, MIT License
2
3//! Commutative composition of two configured parser instances.
4//!
5//! Token numbers belong to one `Tabnas` instance.  Merge therefore moves
6//! grammar slots and token sets through token *names*, allocates a fresh
7//! deterministic token space, and only then materializes the combined rules.
8
9use crate::options::{
10    CommentDef, ConfigModifier, FixedToken, LexCheck, LexMatcher, MatchToken, MatchTokenMatcher,
11    MatchValue, TextModifier, ValueDef,
12};
13use crate::{
14    Action, ActionBinding, AltActionBinding, AltSpec, ContextAction, LexSubscriber, Options,
15    Plugin, PluginError, RuleDoneSubscriber, RuleSpec, RuleSubscriber, Tabnas, TokenSubscriber,
16    Value,
17};
18use indexmap::IndexMap;
19use std::collections::{BTreeSet, HashMap};
20use std::fmt;
21use std::sync::Arc;
22
23#[derive(Debug, Clone, PartialEq, Eq)]
24pub struct MergeError(pub String);
25
26impl fmt::Display for MergeError {
27    fn fmt(&self, formatter: &mut fmt::Formatter<'_>) -> fmt::Result {
28        formatter.write_str(&self.0)
29    }
30}
31
32impl std::error::Error for MergeError {}
33
34fn conflict(path: &str) -> MergeError {
35    MergeError(format!("merge: conflicting option values at {path}"))
36}
37
38fn pick<T: Clone>(
39    left: &T,
40    right: &T,
41    default: &T,
42    path: &str,
43    equal: &dyn Fn(&T, &T) -> bool,
44) -> Result<T, MergeError> {
45    if equal(left, right) {
46        Ok(left.clone())
47    } else if equal(left, default) {
48        Ok(right.clone())
49    } else if equal(right, default) {
50        Ok(left.clone())
51    } else {
52        Err(conflict(path))
53    }
54}
55
56fn pick_without_default<T: Clone>(
57    left: &T,
58    right: &T,
59    path: &str,
60    equal: &dyn Fn(&T, &T) -> bool,
61) -> Result<T, MergeError> {
62    equal(left, right)
63        .then(|| left.clone())
64        .ok_or_else(|| conflict(path))
65}
66
67fn eq_value(left: &Value, right: &Value) -> bool {
68    left.deep_equal(right)
69}
70
71fn eq_f64(left: &f64, right: &f64) -> bool {
72    (left.is_nan() && right.is_nan()) || left.to_bits() == right.to_bits()
73}
74
75fn eq_option_arc<T: ?Sized>(left: &Option<Arc<T>>, right: &Option<Arc<T>>) -> bool {
76    match (left, right) {
77        (None, None) => true,
78        (Some(left), Some(right)) => Arc::ptr_eq(left, right),
79        _ => false,
80    }
81}
82
83fn eq_arc_vec<T: ?Sized>(left: &[Arc<T>], right: &[Arc<T>]) -> bool {
84    left.len() == right.len()
85        && left
86            .iter()
87            .zip(right)
88            .all(|(left, right)| Arc::ptr_eq(left, right))
89}
90
91fn eq_text_modifier_vec(left: &[TextModifier], right: &[TextModifier]) -> bool {
92    left.len() == right.len()
93        && left
94            .iter()
95            .zip(right)
96            .all(|(left, right)| left.same_callback(right))
97}
98
99fn eq_prepare_vec(left: &[crate::ParsePrepare], right: &[crate::ParsePrepare]) -> bool {
100    left.len() == right.len()
101        && left
102            .iter()
103            .zip(right)
104            .all(|(left, right)| left.same_callback(right))
105}
106
107fn eq_option_check(left: &Option<LexCheck>, right: &Option<LexCheck>) -> bool {
108    match (left, right) {
109        (None, None) => true,
110        (Some(left), Some(right)) => left.same_callback(right),
111        _ => false,
112    }
113}
114
115fn ordered_keys<T>(left: &IndexMap<String, T>, right: &IndexMap<String, T>) -> Vec<String> {
116    let mut keys = left.keys().cloned().collect::<Vec<_>>();
117    keys.extend(right.keys().filter(|key| !left.contains_key(*key)).cloned());
118    keys
119}
120
121fn sorted_hash_keys<T>(left: &HashMap<String, T>, right: &HashMap<String, T>) -> Vec<String> {
122    let mut keys = left
123        .keys()
124        .chain(right.keys())
125        .cloned()
126        .collect::<BTreeSet<_>>()
127        .into_iter()
128        .collect::<Vec<_>>();
129    keys.shrink_to_fit();
130    keys
131}
132
133fn merge_index_map<T: Clone>(
134    left: &IndexMap<String, T>,
135    right: &IndexMap<String, T>,
136    default: &IndexMap<String, T>,
137    prefix: &str,
138    equal: &dyn Fn(&T, &T) -> bool,
139) -> Result<IndexMap<String, T>, MergeError> {
140    let mut out = IndexMap::new();
141    for key in ordered_keys(left, right) {
142        let value = match (left.get(&key), right.get(&key), default.get(&key)) {
143            (Some(left), Some(right), Some(default)) => Some(pick(
144                left,
145                right,
146                default,
147                &format!("{prefix}.{key}"),
148                equal,
149            )?),
150            (Some(left), Some(right), None) => Some(pick_without_default(
151                left,
152                right,
153                &format!("{prefix}.{key}"),
154                equal,
155            )?),
156            // A missing resolved default entry represents an explicit
157            // deletion. It wins against the unchanged default, while a
158            // deletion and a different replacement are both non-default.
159            (Some(value), None, Some(default)) | (None, Some(value), Some(default)) => {
160                if equal(value, default) {
161                    None
162                } else {
163                    return Err(conflict(&format!("{prefix}.{key}")));
164                }
165            }
166            (Some(value), None, None) | (None, Some(value), None) => Some(value.clone()),
167            (None, None, _) => unreachable!(),
168        };
169        if let Some(value) = value {
170            out.insert(key, value);
171        }
172    }
173    Ok(out)
174}
175
176fn merge_hash_map<T: Clone>(
177    left: &HashMap<String, T>,
178    right: &HashMap<String, T>,
179    default: &HashMap<String, T>,
180    prefix: &str,
181    equal: &dyn Fn(&T, &T) -> bool,
182) -> Result<HashMap<String, T>, MergeError> {
183    let mut out = HashMap::new();
184    for key in sorted_hash_keys(left, right) {
185        let value = match (left.get(&key), right.get(&key), default.get(&key)) {
186            (Some(left), Some(right), Some(default)) => Some(pick(
187                left,
188                right,
189                default,
190                &format!("{prefix}.{key}"),
191                equal,
192            )?),
193            (Some(left), Some(right), None) => Some(pick_without_default(
194                left,
195                right,
196                &format!("{prefix}.{key}"),
197                equal,
198            )?),
199            (Some(value), None, Some(default)) | (None, Some(value), Some(default)) => {
200                if equal(value, default) {
201                    None
202                } else {
203                    return Err(conflict(&format!("{prefix}.{key}")));
204                }
205            }
206            (Some(value), None, None) | (None, Some(value), None) => Some(value.clone()),
207            (None, None, _) => unreachable!(),
208        };
209        if let Some(value) = value {
210            out.insert(key, value);
211        }
212    }
213    Ok(out)
214}
215
216fn merge_char_map(
217    left: &HashMap<char, String>,
218    right: &HashMap<char, String>,
219    default: &HashMap<char, String>,
220    prefix: &str,
221) -> Result<HashMap<char, String>, MergeError> {
222    let keys = left
223        .keys()
224        .chain(right.keys())
225        .copied()
226        .collect::<BTreeSet<_>>();
227    let mut out = HashMap::new();
228    for key in keys {
229        let path = format!("{prefix}.{key}");
230        let value = match (left.get(&key), right.get(&key), default.get(&key)) {
231            (Some(left), Some(right), Some(default)) => {
232                Some(pick(left, right, default, &path, &PartialEq::eq)?)
233            }
234            (Some(left), Some(right), None) => {
235                Some(pick_without_default(left, right, &path, &PartialEq::eq)?)
236            }
237            (Some(value), None, Some(default)) | (None, Some(value), Some(default)) => {
238                if value == default {
239                    None
240                } else {
241                    return Err(conflict(&path));
242                }
243            }
244            (Some(value), None, None) | (None, Some(value), None) => Some(value.clone()),
245            (None, None, _) => unreachable!(),
246        };
247        if let Some(value) = value {
248            out.insert(key, value);
249        }
250    }
251    Ok(out)
252}
253
254fn eq_matcher(left: &MatchTokenMatcher, right: &MatchTokenMatcher) -> bool {
255    match (left, right) {
256        (MatchTokenMatcher::Regex(left), MatchTokenMatcher::Regex(right)) => {
257            left.as_str() == right.as_str()
258        }
259        (MatchTokenMatcher::Callback(left), MatchTokenMatcher::Callback(right)) => {
260            Arc::ptr_eq(left, right)
261        }
262        _ => false,
263    }
264}
265
266fn eq_fixed_token(left: &FixedToken, right: &FixedToken) -> bool {
267    left.name == right.name && left.source == right.source
268}
269
270fn eq_match_token(left: &MatchToken, right: &MatchToken) -> bool {
271    left.name == right.name
272        && left.eager == right.eager
273        && eq_matcher(&left.matcher, &right.matcher)
274}
275
276fn eq_match_value(left: &MatchValue, right: &MatchValue) -> bool {
277    left.name == right.name
278        && eq_matcher(&left.matcher, &right.matcher)
279        && match (&left.val, &right.val) {
280            (None, None) => true,
281            (Some(left), Some(right)) => left.deep_equal(right),
282            _ => false,
283        }
284        && eq_option_arc(&left.transform, &right.transform)
285}
286
287fn eq_value_def(left: &ValueDef, right: &ValueDef) -> bool {
288    match (&left.val, &right.val) {
289        (None, None) => {}
290        (Some(left), Some(right)) if left.deep_equal(right) => {}
291        _ => return false,
292    }
293    match (&left.matcher, &right.matcher) {
294        (None, None) => {}
295        (Some(left), Some(right)) if left.as_str() == right.as_str() => {}
296        _ => return false,
297    }
298    left.consume == right.consume && eq_option_arc(&left.transform, &right.transform)
299}
300
301fn eq_comment_def(left: &CommentDef, right: &CommentDef) -> bool {
302    left.line == right.line
303        && left.start == right.start
304        && left.end == right.end
305        && left.lex == right.lex
306        && left.suffixes == right.suffixes
307        && left.eat_line == right.eat_line
308        && match (&left.suffix_matcher, &right.suffix_matcher) {
309            (None, None) => true,
310            (Some(left), Some(right)) => left.same_callback(right),
311            _ => false,
312        }
313}
314
315fn eq_lex_matcher(left: &LexMatcher, right: &LexMatcher) -> bool {
316    left.name == right.name
317        && eq_f64(&left.order, &right.order)
318        && eq_option_arc(&left.matcher, &right.matcher)
319        && eq_option_arc(&left.imperative, &right.imperative)
320        && eq_option_arc(&left.factory, &right.factory)
321}
322
323fn merge_options(left: &Options, right: &Options) -> Result<Options, MergeError> {
324    let default = Options::default();
325    let mut out = default.clone();
326
327    out.safe.key = pick(
328        &left.safe.key,
329        &right.safe.key,
330        &default.safe.key,
331        "safe.key",
332        &PartialEq::eq,
333    )?;
334
335    out.fixed.lex = pick(
336        &left.fixed.lex,
337        &right.fixed.lex,
338        &default.fixed.lex,
339        "fixed.lex",
340        &PartialEq::eq,
341    )?;
342    out.fixed.check = pick(
343        &left.fixed.check,
344        &right.fixed.check,
345        &default.fixed.check,
346        "fixed.check",
347        &eq_option_check,
348    )?;
349    out.fixed.tokens = merge_index_map(
350        &left.fixed.tokens,
351        &right.fixed.tokens,
352        &default.fixed.tokens,
353        "fixed.token",
354        &eq_fixed_token,
355    )?;
356
357    out.space.lex = pick(
358        &left.space.lex,
359        &right.space.lex,
360        &default.space.lex,
361        "space.lex",
362        &PartialEq::eq,
363    )?;
364    out.space.chars = pick(
365        &left.space.chars,
366        &right.space.chars,
367        &default.space.chars,
368        "space.chars",
369        &PartialEq::eq,
370    )?;
371    out.space.check = pick(
372        &left.space.check,
373        &right.space.check,
374        &default.space.check,
375        "space.check",
376        &eq_option_check,
377    )?;
378
379    out.text.lex = pick(
380        &left.text.lex,
381        &right.text.lex,
382        &default.text.lex,
383        "text.lex",
384        &PartialEq::eq,
385    )?;
386    out.text.modify = pick(
387        &left.text.modify,
388        &right.text.modify,
389        &default.text.modify,
390        "text.modify",
391        &|left, right| eq_text_modifier_vec(left, right),
392    )?;
393    out.text.check = pick(
394        &left.text.check,
395        &right.text.check,
396        &default.text.check,
397        "text.check",
398        &eq_option_check,
399    )?;
400
401    out.number.lex = pick(
402        &left.number.lex,
403        &right.number.lex,
404        &default.number.lex,
405        "number.lex",
406        &PartialEq::eq,
407    )?;
408    out.number.hex = pick(
409        &left.number.hex,
410        &right.number.hex,
411        &default.number.hex,
412        "number.hex",
413        &PartialEq::eq,
414    )?;
415    out.number.oct = pick(
416        &left.number.oct,
417        &right.number.oct,
418        &default.number.oct,
419        "number.oct",
420        &PartialEq::eq,
421    )?;
422    out.number.bin = pick(
423        &left.number.bin,
424        &right.number.bin,
425        &default.number.bin,
426        "number.bin",
427        &PartialEq::eq,
428    )?;
429    out.number.sep = pick(
430        &left.number.sep,
431        &right.number.sep,
432        &default.number.sep,
433        "number.sep",
434        &PartialEq::eq,
435    )?;
436    out.number.exclude = pick(
437        &left.number.exclude,
438        &right.number.exclude,
439        &default.number.exclude,
440        "number.exclude",
441        &PartialEq::eq,
442    )?;
443    out.number.check = pick(
444        &left.number.check,
445        &right.number.check,
446        &default.number.check,
447        "number.check",
448        &eq_option_check,
449    )?;
450
451    out.string.lex = pick(
452        &left.string.lex,
453        &right.string.lex,
454        &default.string.lex,
455        "string.lex",
456        &PartialEq::eq,
457    )?;
458    out.string.chars = pick(
459        &left.string.chars,
460        &right.string.chars,
461        &default.string.chars,
462        "string.chars",
463        &PartialEq::eq,
464    )?;
465    out.string.multi_chars = pick(
466        &left.string.multi_chars,
467        &right.string.multi_chars,
468        &default.string.multi_chars,
469        "string.multiChars",
470        &PartialEq::eq,
471    )?;
472    out.string.escape_char = pick(
473        &left.string.escape_char,
474        &right.string.escape_char,
475        &default.string.escape_char,
476        "string.escapeChar",
477        &PartialEq::eq,
478    )?;
479    out.string.escape = merge_char_map(
480        &left.string.escape,
481        &right.string.escape,
482        &default.string.escape,
483        "string.escape",
484    )?;
485    out.string.replace = merge_char_map(
486        &left.string.replace,
487        &right.string.replace,
488        &default.string.replace,
489        "string.replace",
490    )?;
491    out.string.allow_unknown = pick(
492        &left.string.allow_unknown,
493        &right.string.allow_unknown,
494        &default.string.allow_unknown,
495        "string.allowUnknown",
496        &PartialEq::eq,
497    )?;
498    out.string.escape_strict = pick(
499        &left.string.escape_strict,
500        &right.string.escape_strict,
501        &default.string.escape_strict,
502        "string.escapeStrict",
503        &PartialEq::eq,
504    )?;
505    out.string.allow_control = pick(
506        &left.string.allow_control,
507        &right.string.allow_control,
508        &default.string.allow_control,
509        "string.allowControl",
510        &PartialEq::eq,
511    )?;
512    out.string.abandon = pick(
513        &left.string.abandon,
514        &right.string.abandon,
515        &default.string.abandon,
516        "string.abandon",
517        &PartialEq::eq,
518    )?;
519    out.string.check = pick(
520        &left.string.check,
521        &right.string.check,
522        &default.string.check,
523        "string.check",
524        &eq_option_check,
525    )?;
526
527    out.line.lex = pick(
528        &left.line.lex,
529        &right.line.lex,
530        &default.line.lex,
531        "line.lex",
532        &PartialEq::eq,
533    )?;
534    out.line.chars = pick(
535        &left.line.chars,
536        &right.line.chars,
537        &default.line.chars,
538        "line.chars",
539        &PartialEq::eq,
540    )?;
541    out.line.row_chars = pick(
542        &left.line.row_chars,
543        &right.line.row_chars,
544        &default.line.row_chars,
545        "line.rowChars",
546        &PartialEq::eq,
547    )?;
548    out.line.single = pick(
549        &left.line.single,
550        &right.line.single,
551        &default.line.single,
552        "line.single",
553        &PartialEq::eq,
554    )?;
555    out.line.fixed = pick(
556        &left.line.fixed,
557        &right.line.fixed,
558        &default.line.fixed,
559        "line.fixed",
560        &PartialEq::eq,
561    )?;
562    out.line.check = pick(
563        &left.line.check,
564        &right.line.check,
565        &default.line.check,
566        "line.check",
567        &eq_option_check,
568    )?;
569
570    out.comment.lex = pick(
571        &left.comment.lex,
572        &right.comment.lex,
573        &default.comment.lex,
574        "comment.lex",
575        &PartialEq::eq,
576    )?;
577    out.comment.check = pick(
578        &left.comment.check,
579        &right.comment.check,
580        &default.comment.check,
581        "comment.check",
582        &eq_option_check,
583    )?;
584    out.comment.definitions = merge_index_map(
585        &left.comment.definitions,
586        &right.comment.definitions,
587        &default.comment.definitions,
588        "comment.def",
589        &eq_comment_def,
590    )?;
591
592    out.value.lex = pick(
593        &left.value.lex,
594        &right.value.lex,
595        &default.value.lex,
596        "value.lex",
597        &PartialEq::eq,
598    )?;
599    out.value.definitions = merge_index_map(
600        &left.value.definitions,
601        &right.value.definitions,
602        &default.value.definitions,
603        "value.def",
604        &eq_value_def,
605    )?;
606    out.ender = pick(
607        &left.ender,
608        &right.ender,
609        &default.ender,
610        "ender",
611        &PartialEq::eq,
612    )?;
613
614    out.map.extend = pick(
615        &left.map.extend,
616        &right.map.extend,
617        &default.map.extend,
618        "map.extend",
619        &PartialEq::eq,
620    )?;
621    out.map.merge = pick(
622        &left.map.merge,
623        &right.map.merge,
624        &default.map.merge,
625        "map.merge",
626        &eq_option_arc,
627    )?;
628    out.map.child = pick(
629        &left.map.child,
630        &right.map.child,
631        &default.map.child,
632        "map.child",
633        &PartialEq::eq,
634    )?;
635    out.map.ordered = pick(
636        &left.map.ordered,
637        &right.map.ordered,
638        &default.map.ordered,
639        "map.ordered",
640        &PartialEq::eq,
641    )?;
642
643    out.list.property = pick(
644        &left.list.property,
645        &right.list.property,
646        &default.list.property,
647        "list.property",
648        &PartialEq::eq,
649    )?;
650    out.list.pair = pick(
651        &left.list.pair,
652        &right.list.pair,
653        &default.list.pair,
654        "list.pair",
655        &PartialEq::eq,
656    )?;
657    out.list.child = pick(
658        &left.list.child,
659        &right.list.child,
660        &default.list.child,
661        "list.child",
662        &PartialEq::eq,
663    )?;
664
665    out.info.map = pick(
666        &left.info.map,
667        &right.info.map,
668        &default.info.map,
669        "info.map",
670        &PartialEq::eq,
671    )?;
672    out.info.list = pick(
673        &left.info.list,
674        &right.info.list,
675        &default.info.list,
676        "info.list",
677        &PartialEq::eq,
678    )?;
679    out.info.text = pick(
680        &left.info.text,
681        &right.info.text,
682        &default.info.text,
683        "info.text",
684        &PartialEq::eq,
685    )?;
686    out.info.marker = pick(
687        &left.info.marker,
688        &right.info.marker,
689        &default.info.marker,
690        "info.marker",
691        &PartialEq::eq,
692    )?;
693
694    out.lex.empty = pick(
695        &left.lex.empty,
696        &right.lex.empty,
697        &default.lex.empty,
698        "lex.empty",
699        &PartialEq::eq,
700    )?;
701    out.lex.empty_result = pick(
702        &left.lex.empty_result,
703        &right.lex.empty_result,
704        &default.lex.empty_result,
705        "lex.emptyResult",
706        &eq_value,
707    )?;
708    out.lex.relex = pick(
709        &left.lex.relex,
710        &right.lex.relex,
711        &default.lex.relex,
712        "lex.relex",
713        &PartialEq::eq,
714    )?;
715    out.lex.window = pick(
716        &left.lex.window,
717        &right.lex.window,
718        &default.lex.window,
719        "lex.window",
720        &PartialEq::eq,
721    )?;
722    out.lex.matchers = merge_index_map(
723        &left.lex.matchers,
724        &right.lex.matchers,
725        &default.lex.matchers,
726        "lex.match",
727        &eq_lex_matcher,
728    )?;
729    out.lex.matchers.sort_by(|name_a, left, name_b, right| {
730        left.order
731            .total_cmp(&right.order)
732            .then_with(|| name_a.cmp(name_b))
733    });
734
735    out.rewind.history = pick(
736        &left.rewind.history,
737        &right.rewind.history,
738        &default.rewind.history,
739        "rewind.history",
740        &PartialEq::eq,
741    )?;
742    out.rule.finish = pick(
743        &left.rule.finish,
744        &right.rule.finish,
745        &default.rule.finish,
746        "rule.finish",
747        &PartialEq::eq,
748    )?;
749    // Each bound as the links read it (`effective_rule_history`): two
750    // values that parse alike, `Some(0)` and `Some(1)` or one past the
751    // cap and the cap, are no conflict.
752    out.rule.history = pick(
753        &crate::options::effective_rule_history(left.rule.history),
754        &crate::options::effective_rule_history(right.rule.history),
755        &default.rule.history,
756        "rule.history",
757        &PartialEq::eq,
758    )?;
759    out.rule.maxmul = pick(
760        &left.rule.maxmul,
761        &right.rule.maxmul,
762        &default.rule.maxmul,
763        "rule.maxmul",
764        &PartialEq::eq,
765    )?;
766    out.rule.include = pick(
767        &left.rule.include,
768        &right.rule.include,
769        &default.rule.include,
770        "rule.include",
771        &PartialEq::eq,
772    )?;
773    out.rule.exclude = pick(
774        &left.rule.exclude,
775        &right.rule.exclude,
776        &default.rule.exclude,
777        "rule.exclude",
778        &PartialEq::eq,
779    )?;
780    out.rule.start = pick(
781        &left.rule.start,
782        &right.rule.start,
783        &default.rule.start,
784        "rule.start",
785        &PartialEq::eq,
786    )?;
787    out.result.fail = pick(
788        &left.result.fail,
789        &right.result.fail,
790        &default.result.fail,
791        "result.fail",
792        &|left, right| {
793            left.len() == right.len()
794                && left
795                    .iter()
796                    .zip(right)
797                    .all(|(left, right)| left.deep_equal(right))
798        },
799    )?;
800    out.plugin = merge_index_map(
801        &left.plugin,
802        &right.plugin,
803        &default.plugin,
804        "plugin",
805        &Value::deep_equal,
806    )?;
807
808    out.parse.prepare = pick(
809        &left.parse.prepare,
810        &right.parse.prepare,
811        &default.parse.prepare,
812        "parse.prepare",
813        &|left, right| eq_prepare_vec(left, right),
814    )?;
815    out.parse.named_prepare = merge_index_map(
816        &left.parse.named_prepare,
817        &right.parse.named_prepare,
818        &default.parse.named_prepare,
819        "parse.prepare",
820        &crate::ParsePrepare::same_callback,
821    )?;
822    out.parse.budget.check_every_n = pick(
823        &left.parse.budget.check_every_n,
824        &right.parse.budget.check_every_n,
825        &default.parse.budget.check_every_n,
826        "parse.budget.checkEveryN",
827        &PartialEq::eq,
828    )?;
829    out.parse.budget.on_check = pick(
830        &left.parse.budget.on_check,
831        &right.parse.budget.on_check,
832        &default.parse.budget.on_check,
833        "parse.budget.onCheck",
834        &eq_option_arc,
835    )?;
836    out.parse.recover.enabled = pick(
837        &left.parse.recover.enabled,
838        &right.parse.recover.enabled,
839        &default.parse.recover.enabled,
840        "parse.recover.enabled",
841        &PartialEq::eq,
842    )?;
843    out.parse.recover.sync_groups = pick(
844        &left.parse.recover.sync_groups,
845        &right.parse.recover.sync_groups,
846        &default.parse.recover.sync_groups,
847        "parse.recover.syncGroups",
848        &PartialEq::eq,
849    )?;
850    out.parse.recover.sync_tokens = pick(
851        &left.parse.recover.sync_tokens,
852        &right.parse.recover.sync_tokens,
853        &default.parse.recover.sync_tokens,
854        "parse.recover.syncTokens",
855        &PartialEq::eq,
856    )?;
857    out.parse.recover.pop_until_valid = pick(
858        &left.parse.recover.pop_until_valid,
859        &right.parse.recover.pop_until_valid,
860        &default.parse.recover.pop_until_valid,
861        "parse.recover.popUntilValid",
862        &PartialEq::eq,
863    )?;
864    out.parse.recover.max_skip = pick(
865        &left.parse.recover.max_skip,
866        &right.parse.recover.max_skip,
867        &default.parse.recover.max_skip,
868        "parse.recover.maxSkip",
869        &PartialEq::eq,
870    )?;
871    out.parse.recover.max_recoveries = pick(
872        &left.parse.recover.max_recoveries,
873        &right.parse.recover.max_recoveries,
874        &default.parse.recover.max_recoveries,
875        "parse.recover.maxRecoveries",
876        &PartialEq::eq,
877    )?;
878    out.parse.recover.suppress = pick(
879        &left.parse.recover.suppress,
880        &right.parse.recover.suppress,
881        &default.parse.recover.suppress,
882        "parse.recover.suppress",
883        &PartialEq::eq,
884    )?;
885    out.parser.start = pick(
886        &left.parser.start,
887        &right.parser.start,
888        &default.parser.start,
889        "parser.start",
890        &eq_option_arc,
891    )?;
892    out.parser.start_with_instance = pick(
893        &left.parser.start_with_instance,
894        &right.parser.start_with_instance,
895        &default.parser.start_with_instance,
896        "parser.start",
897        &eq_option_arc,
898    )?;
899    out.parser.start_with_context = pick(
900        &left.parser.start_with_context,
901        &right.parser.start_with_context,
902        &default.parser.start_with_context,
903        "parser.start",
904        &eq_option_arc,
905    )?;
906    out.debug.maxlen = pick(
907        &left.debug.maxlen,
908        &right.debug.maxlen,
909        &default.debug.maxlen,
910        "debug.maxlen",
911        &PartialEq::eq,
912    )?;
913    out.debug.print.config = pick(
914        &left.debug.print.config,
915        &right.debug.print.config,
916        &default.debug.print.config,
917        "debug.print.config",
918        &PartialEq::eq,
919    )?;
920    out.debug.print.source = pick(
921        &left.debug.print.source,
922        &right.debug.print.source,
923        &default.debug.print.source,
924        "debug.print.src",
925        &eq_option_arc,
926    )?;
927    out.debug.output = pick(
928        &left.debug.output,
929        &right.debug.output,
930        &default.debug.output,
931        "debug.get_console",
932        &eq_option_arc,
933    )?;
934
935    out.match_lex = pick(
936        &left.match_lex,
937        &right.match_lex,
938        &default.match_lex,
939        "match.lex",
940        &PartialEq::eq,
941    )?;
942    out.match_check = pick(
943        &left.match_check,
944        &right.match_check,
945        &default.match_check,
946        "match.check",
947        &eq_option_check,
948    )?;
949    out.match_tokens = merge_index_map(
950        &left.match_tokens,
951        &right.match_tokens,
952        &default.match_tokens,
953        "match.token",
954        &eq_match_token,
955    )?;
956    out.match_values = merge_index_map(
957        &left.match_values,
958        &right.match_values,
959        &default.match_values,
960        "match.value",
961        &eq_match_value,
962    )?;
963    out.error = merge_hash_map(
964        &left.error,
965        &right.error,
966        &default.error,
967        "error",
968        &PartialEq::eq,
969    )?;
970    out.hint = merge_hash_map(
971        &left.hint,
972        &right.hint,
973        &default.hint,
974        "hint",
975        &PartialEq::eq,
976    )?;
977
978    out.errmsg.name = pick(
979        &left.errmsg.name,
980        &right.errmsg.name,
981        &default.errmsg.name,
982        "errmsg.name",
983        &PartialEq::eq,
984    )?;
985    out.errmsg.suffix = pick(
986        &left.errmsg.suffix,
987        &right.errmsg.suffix,
988        &default.errmsg.suffix,
989        "errmsg.suffix",
990        &PartialEq::eq,
991    )?;
992    out.errmsg.link = pick(
993        &left.errmsg.link,
994        &right.errmsg.link,
995        &default.errmsg.link,
996        "errmsg.link",
997        &PartialEq::eq,
998    )?;
999    out.color.active = pick(
1000        &left.color.active,
1001        &right.color.active,
1002        &default.color.active,
1003        "color.active",
1004        &PartialEq::eq,
1005    )?;
1006    out.color.reset = pick(
1007        &left.color.reset,
1008        &right.color.reset,
1009        &default.color.reset,
1010        "color.reset",
1011        &PartialEq::eq,
1012    )?;
1013    out.color.hi = pick(
1014        &left.color.hi,
1015        &right.color.hi,
1016        &default.color.hi,
1017        "color.hi",
1018        &PartialEq::eq,
1019    )?;
1020    out.color.lo = pick(
1021        &left.color.lo,
1022        &right.color.lo,
1023        &default.color.lo,
1024        "color.lo",
1025        &PartialEq::eq,
1026    )?;
1027    out.color.line = pick(
1028        &left.color.line,
1029        &right.color.line,
1030        &default.color.line,
1031        "color.line",
1032        &PartialEq::eq,
1033    )?;
1034    out.config_modify = merge_index_map(
1035        &left.config_modify,
1036        &right.config_modify,
1037        &default.config_modify,
1038        "config.modify",
1039        &ConfigModifier::same_callback,
1040    )?;
1041
1042    merge_token_space(left, right, &default, &mut out)?;
1043    Ok(out)
1044}
1045
1046fn token_set_names(options: &Options) -> HashMap<String, Vec<String>> {
1047    options
1048        .token_set
1049        .iter()
1050        .map(|(name, members)| {
1051            (
1052                name.clone(),
1053                members.iter().map(|tin| options.token_name(*tin)).collect(),
1054            )
1055        })
1056        .collect()
1057}
1058
1059fn merge_token_space(
1060    left: &Options,
1061    right: &Options,
1062    default: &Options,
1063    out: &mut Options,
1064) -> Result<(), MergeError> {
1065    let left_sets = token_set_names(left);
1066    let right_sets = token_set_names(right);
1067    let default_sets = token_set_names(default);
1068    let sets = merge_hash_map(
1069        &left_sets,
1070        &right_sets,
1071        &default_sets,
1072        "tokenSet",
1073        &PartialEq::eq,
1074    )?;
1075
1076    let mut plain_names = left
1077        .tokens
1078        .keys()
1079        .chain(right.tokens.keys())
1080        .cloned()
1081        .collect::<BTreeSet<_>>();
1082    for name in out.fixed.tokens.keys().chain(out.match_tokens.keys()) {
1083        plain_names.insert(name.clone());
1084    }
1085    for members in sets.values() {
1086        plain_names.extend(members.iter().cloned());
1087    }
1088
1089    let mut next_tin = crate::token::TIN_MAX;
1090    let mut tins = HashMap::new();
1091    for name in &plain_names {
1092        let tin = crate::token::name_to_tin(name).unwrap_or_else(|| {
1093            let allocated = next_tin;
1094            next_tin += 1;
1095            allocated
1096        });
1097        tins.insert(name.clone(), tin);
1098    }
1099
1100    for (name, token) in &mut out.fixed.tokens {
1101        token.tin = *tins.get(name).expect("fixed token was allocated");
1102    }
1103    for (name, token) in &mut out.match_tokens {
1104        token.tin = *tins.get(name).expect("match token was allocated");
1105    }
1106    out.tokens = plain_names
1107        .iter()
1108        .map(|name| (name.clone(), tins[name]))
1109        .collect();
1110    out.token_set = sets
1111        .into_iter()
1112        .map(|(name, members)| {
1113            let members = members.into_iter().map(|member| tins[&member]).collect();
1114            (name, members)
1115        })
1116        .collect();
1117
1118    let mut by_source: HashMap<&str, &str> = HashMap::new();
1119    for (name, token) in &out.fixed.tokens {
1120        if let Some(existing) = by_source.insert(&token.source, name) {
1121            if existing != name {
1122                return Err(MergeError(format!(
1123                    "merge: fixed tokens {existing} and {name} both claim source {:?}",
1124                    token.source
1125                )));
1126            }
1127        }
1128    }
1129    Ok(())
1130}
1131
1132#[derive(Clone, Debug, PartialEq, Eq)]
1133enum ActionIdentity {
1134    Simple(usize),
1135    Context(usize),
1136    Matched(usize),
1137    State(usize),
1138    Builtin(String),
1139    Missing(String),
1140}
1141
1142fn erased_ptr<T: ?Sized>(value: &Arc<T>) -> usize {
1143    Arc::as_ptr(value) as *const () as usize
1144}
1145
1146fn action_identity(tabnas: &Tabnas, name: &str) -> ActionIdentity {
1147    if name.contains('$') {
1148        ActionIdentity::Builtin(name.to_string())
1149    } else if let Some(action) = tabnas.actions.get(name) {
1150        ActionIdentity::Simple(erased_ptr(action))
1151    } else if let Some(action) = tabnas.context_actions.get(name) {
1152        ActionIdentity::Context(erased_ptr(action))
1153    } else if let Some(action) = tabnas.matched_actions.get(name) {
1154        ActionIdentity::Matched(erased_ptr(action))
1155    } else if let Some(action) = tabnas.state_actions.get(name) {
1156        ActionIdentity::State(erased_ptr(action))
1157    } else {
1158        ActionIdentity::Missing(name.to_string())
1159    }
1160}
1161
1162fn rename_ref(name: &str, tag: &str) -> String {
1163    if name.contains('$') {
1164        name.to_string()
1165    } else if let Some(name) = name.strip_prefix('@') {
1166        format!("@{tag}:{name}")
1167    } else {
1168        format!("{tag}:{name}")
1169    }
1170}
1171
1172#[derive(Clone)]
1173struct PortableAlt {
1174    alt: AltSpec,
1175    slots: Vec<Vec<String>>,
1176    keys: Vec<String>,
1177    /// Per slot, the sorted names the slot re-resolves from on the merged
1178    /// instance, or its key when it has none. Two slots declared alike
1179    /// resolve alike under every later token-set override; two that only
1180    /// resolve alike now may not.
1181    declared: Vec<String>,
1182    complexity: [usize; 10],
1183    group: String,
1184    tag: String,
1185    action_identity: Vec<ActionIdentity>,
1186}
1187
1188fn portable_alt(tabnas: &Tabnas, alt: &AltSpec, tag: &str) -> PortableAlt {
1189    // A slot declared by name is what its names resolve to on the source
1190    // instance now, which is how that instance's parser reads it: the spec
1191    // keeps what they resolved to when the alternate was installed, and a
1192    // token set overridden since would otherwise key, order and carry the
1193    // old members.
1194    let slots = (0..alt.s.len())
1195        .map(|slot| {
1196            crate::parser::resolved_slot(alt, slot, &tabnas.options)
1197                .unwrap_or_else(|| alt.s[slot].clone())
1198                .iter()
1199                .map(|tin| tabnas.options.token_name(*tin))
1200                .collect::<Vec<_>>()
1201        })
1202        .collect::<Vec<_>>();
1203    let keys: Vec<String> = slots
1204        .iter()
1205        .map(|slot| {
1206            let mut names = slot.clone();
1207            names.sort();
1208            names.join(" ")
1209        })
1210        .collect();
1211    let mut cloned = alt.clone();
1212    let ordered_actions = crate::rule::resolved_alt_action_order(
1213        &alt.a,
1214        &alt.action_fns,
1215        &alt.matched_action_fns,
1216        &alt.action_order,
1217    );
1218    let action_identity = ordered_actions
1219        .iter()
1220        .map(|binding| match binding {
1221            AltActionBinding::Named(name) => action_identity(tabnas, name),
1222            AltActionBinding::Context(callback) => ActionIdentity::Context(erased_ptr(callback)),
1223            AltActionBinding::Matched(callback) => ActionIdentity::Matched(erased_ptr(callback)),
1224        })
1225        .collect();
1226    cloned.a = alt.a.iter().map(|name| rename_ref(name, tag)).collect();
1227    cloned.action_configs = alt
1228        .action_configs
1229        .iter()
1230        .map(|(name, value)| (rename_ref(name, tag), value.clone()))
1231        .collect();
1232    cloned.c_ref = alt.c_ref.as_ref().map(|name| rename_ref(name, tag));
1233    cloned.action_order = ordered_actions
1234        .into_iter()
1235        .map(|binding| match binding {
1236            AltActionBinding::Named(name) => AltActionBinding::Named(rename_ref(&name, tag)),
1237            AltActionBinding::Context(callback) => AltActionBinding::Context(callback),
1238            AltActionBinding::Matched(callback) => AltActionBinding::Matched(callback),
1239        })
1240        .collect();
1241    // A slot set by hand since its names last resolved (its `s` is no
1242    // longer `s_bound`) keeps its tins: its names are dropped here, so no
1243    // rebuild on the merged instance resolves them over the edit.
1244    for (slot, names) in cloned.s_names.iter_mut().enumerate() {
1245        if alt.s.get(slot) != alt.s_bound.get(slot) {
1246            names.clear();
1247        }
1248    }
1249    let declared = keys
1250        .iter()
1251        .enumerate()
1252        .map(|(slot, key)| match cloned.s_names.get(slot) {
1253            Some(names) if !names.is_empty() => {
1254                let mut names = names.clone();
1255                names.sort();
1256                names.join(" ")
1257            }
1258            _ => key.clone(),
1259        })
1260        .collect();
1261    cloned.s.clear();
1262    PortableAlt {
1263        alt: cloned,
1264        slots,
1265        keys,
1266        declared,
1267        complexity: [
1268            usize::from(
1269                !alt.c.is_empty()
1270                    || alt.c_fn.is_some()
1271                    || alt.c_match.is_some()
1272                    || alt.c_lex.is_some()
1273                    || alt.c_lex_match.is_some(),
1274            ),
1275            usize::from(alt.e.is_some() || alt.e_match.is_some()),
1276            usize::from(alt.h.is_some() || alt.h_match.is_some()),
1277            usize::from(alt.b != 0 || alt.b_fn.is_some() || alt.b_match.is_some()),
1278            alt.n.len(),
1279            usize::from(
1280                !alt.a.is_empty()
1281                    || !alt.action_fns.is_empty()
1282                    || !alt.matched_action_fns.is_empty(),
1283            ),
1284            usize::from(!alt.u.is_empty()),
1285            usize::from(!alt.k.is_empty()),
1286            usize::from(alt.p.is_some() || alt.p_fn.is_some() || alt.p_match.is_some()),
1287            usize::from(alt.r.is_some() || alt.r_fn.is_some() || alt.r_match.is_some()),
1288        ],
1289        group: alt.g.clone(),
1290        tag: tag.to_string(),
1291        action_identity,
1292    }
1293}
1294
1295fn compare_alts(left: &PortableAlt, right: &PortableAlt) -> std::cmp::Ordering {
1296    for (left, right) in left.keys.iter().zip(&right.keys) {
1297        let ordering = left.cmp(right);
1298        if !ordering.is_eq() {
1299            return ordering;
1300        }
1301    }
1302    if left.keys.len() != right.keys.len() {
1303        return right.keys.len().cmp(&left.keys.len());
1304    }
1305    for (left, right) in left.complexity.iter().zip(right.complexity) {
1306        let ordering = right.cmp(left);
1307        if !ordering.is_eq() {
1308            return ordering;
1309        }
1310    }
1311    left.group
1312        .cmp(&right.group)
1313        .then_with(|| left.tag.cmp(&right.tag))
1314}
1315
1316fn eq_value_hash(left: &HashMap<String, Value>, right: &HashMap<String, Value>) -> bool {
1317    left.len() == right.len()
1318        && left
1319            .iter()
1320            .all(|(key, value)| right.get(key).is_some_and(|other| value.deep_equal(other)))
1321}
1322
1323fn eq_conditions(left: &[crate::Condition], right: &[crate::Condition]) -> bool {
1324    left.len() == right.len()
1325        && left.iter().zip(right).all(|(left, right)| {
1326            left.path == right.path && left.op == right.op && left.value.deep_equal(&right.value)
1327        })
1328}
1329
1330fn identical_alts(left: &PortableAlt, right: &PortableAlt) -> bool {
1331    let left_alt = &left.alt;
1332    let right_alt = &right.alt;
1333    left.keys == right.keys
1334        && left.declared == right.declared
1335        && left.group == right.group
1336        && left.action_identity == right.action_identity
1337        && eq_arc_vec(&left_alt.action_fns, &right_alt.action_fns)
1338        && eq_arc_vec(&left_alt.matched_action_fns, &right_alt.matched_action_fns)
1339        && eq_conditions(&left_alt.c, &right_alt.c)
1340        && eq_option_arc(&left_alt.c_fn, &right_alt.c_fn)
1341        && eq_option_arc(&left_alt.c_match, &right_alt.c_match)
1342        && eq_option_arc(&left_alt.c_lex, &right_alt.c_lex)
1343        && eq_option_arc(&left_alt.c_lex_match, &right_alt.c_lex_match)
1344        && eq_option_arc(&left_alt.h, &right_alt.h)
1345        && eq_option_arc(&left_alt.h_match, &right_alt.h_match)
1346        && eq_option_arc(&left_alt.e, &right_alt.e)
1347        && eq_option_arc(&left_alt.e_match, &right_alt.e_match)
1348        && left_alt.b == right_alt.b
1349        && eq_option_arc(&left_alt.b_fn, &right_alt.b_fn)
1350        && eq_option_arc(&left_alt.b_match, &right_alt.b_match)
1351        && left_alt.p == right_alt.p
1352        && eq_option_arc(&left_alt.p_fn, &right_alt.p_fn)
1353        && eq_option_arc(&left_alt.p_match, &right_alt.p_match)
1354        && left_alt.r == right_alt.r
1355        && eq_option_arc(&left_alt.r_fn, &right_alt.r_fn)
1356        && eq_option_arc(&left_alt.r_match, &right_alt.r_match)
1357        && left_alt.n == right_alt.n
1358        && eq_value_hash(&left_alt.u, &right_alt.u)
1359        && eq_value_hash(&left_alt.k, &right_alt.k)
1360        && eq_value_hash(&left_alt.action_configs, &right_alt.action_configs)
1361}
1362
1363fn interleave(left: Vec<PortableAlt>, right: Vec<PortableAlt>) -> Vec<PortableAlt> {
1364    let right = right
1365        .into_iter()
1366        .filter(|candidate| {
1367            !left
1368                .iter()
1369                .any(|existing| identical_alts(existing, candidate))
1370        })
1371        .collect::<Vec<_>>();
1372    let mut out = Vec::with_capacity(left.len() + right.len());
1373    let (mut left_i, mut right_i) = (0, 0);
1374    while left_i < left.len() && right_i < right.len() {
1375        if compare_alts(&left[left_i], &right[right_i]).is_le() {
1376            out.push(left[left_i].clone());
1377            left_i += 1;
1378        } else {
1379            out.push(right[right_i].clone());
1380            right_i += 1;
1381        }
1382    }
1383    out.extend(left[left_i..].iter().cloned());
1384    out.extend(right[right_i..].iter().cloned());
1385    out
1386}
1387
1388fn append_callbacks<T: ?Sized>(left: &[Arc<T>], right: &[Arc<T>]) -> Vec<Arc<T>> {
1389    left.iter().chain(right).cloned().collect()
1390}
1391
1392#[derive(Clone)]
1393struct MergedRule {
1394    name: String,
1395    open: Vec<PortableAlt>,
1396    close: Vec<PortableAlt>,
1397    bo: Vec<String>,
1398    ao: Vec<String>,
1399    bc: Vec<String>,
1400    ac: Vec<String>,
1401    bo_fns: Vec<ContextAction>,
1402    ao_fns: Vec<ContextAction>,
1403    bc_fns: Vec<ContextAction>,
1404    ac_fns: Vec<ContextAction>,
1405    bo_state_fns: Vec<crate::StateAction>,
1406    ao_state_fns: Vec<crate::StateAction>,
1407    bc_state_fns: Vec<crate::StateAction>,
1408    ac_state_fns: Vec<crate::StateAction>,
1409    bo_order: Vec<ActionBinding>,
1410    ao_order: Vec<ActionBinding>,
1411    bc_order: Vec<ActionBinding>,
1412    ac_order: Vec<ActionBinding>,
1413}
1414
1415impl MergedRule {
1416    fn materialize(&self, options: &mut Options) -> RuleSpec {
1417        fn alts(alts: &[PortableAlt], options: &mut Options) -> Vec<AltSpec> {
1418            alts.iter()
1419                .map(|portable| {
1420                    let mut alt = portable.alt.clone();
1421                    alt.s = portable
1422                        .slots
1423                        .iter()
1424                        .map(|slot| {
1425                            slot.iter()
1426                                .map(|name| options.register_token(name))
1427                                .collect()
1428                        })
1429                        .collect();
1430                    // The tins are this instance's now, so what the names
1431                    // are compared with has to be too: left at the
1432                    // source's tins, every slot would read as set by hand
1433                    // and a set overridden here would never reach it.
1434                    alt.s_bound = alt.s.clone();
1435                    alt
1436                })
1437                .collect()
1438        }
1439        RuleSpec {
1440            name: self.name.clone(),
1441            open: alts(&self.open, options),
1442            close: alts(&self.close, options),
1443            bo: self.bo.clone(),
1444            ao: self.ao.clone(),
1445            bc: self.bc.clone(),
1446            ac: self.ac.clone(),
1447            bo_fns: self.bo_fns.clone(),
1448            ao_fns: self.ao_fns.clone(),
1449            bc_fns: self.bc_fns.clone(),
1450            ac_fns: self.ac_fns.clone(),
1451            bo_state_fns: self.bo_state_fns.clone(),
1452            ao_state_fns: self.ao_state_fns.clone(),
1453            bc_state_fns: self.bc_state_fns.clone(),
1454            ac_state_fns: self.ac_state_fns.clone(),
1455            bo_order: self.bo_order.clone(),
1456            ao_order: self.ao_order.clone(),
1457            bc_order: self.bc_order.clone(),
1458            ac_order: self.ac_order.clone(),
1459        }
1460    }
1461}
1462
1463struct PhaseSource<'a> {
1464    tabnas: &'a Tabnas,
1465    named: &'a [String],
1466    callbacks: &'a [ContextAction],
1467    states: &'a [crate::StateAction],
1468    order: &'a [ActionBinding],
1469    tag: &'a str,
1470}
1471
1472fn merge_phase(
1473    left: PhaseSource<'_>,
1474    right: PhaseSource<'_>,
1475) -> (
1476    Vec<String>,
1477    Vec<ContextAction>,
1478    Vec<crate::StateAction>,
1479    Vec<ActionBinding>,
1480) {
1481    fn portable(
1482        tabnas: &Tabnas,
1483        named: &[String],
1484        callbacks: &[ContextAction],
1485        states: &[crate::StateAction],
1486        order: &[ActionBinding],
1487        tag: &str,
1488    ) -> Vec<(ActionBinding, ActionIdentity)> {
1489        crate::rule::resolved_action_order(named, callbacks, states, order)
1490            .into_iter()
1491            .map(|binding| match binding {
1492                ActionBinding::Named(name) => (
1493                    ActionBinding::Named(rename_ref(&name, tag)),
1494                    action_identity(tabnas, &name),
1495                ),
1496                ActionBinding::Callback(callback) => {
1497                    let identity = ActionIdentity::Context(erased_ptr(&callback));
1498                    (ActionBinding::Callback(callback), identity)
1499                }
1500                ActionBinding::State(callback) => {
1501                    let identity = ActionIdentity::State(erased_ptr(&callback));
1502                    (ActionBinding::State(callback), identity)
1503                }
1504            })
1505            .collect()
1506    }
1507
1508    let mut order = portable(
1509        left.tabnas,
1510        left.named,
1511        left.callbacks,
1512        left.states,
1513        left.order,
1514        left.tag,
1515    );
1516    for candidate in portable(
1517        right.tabnas,
1518        right.named,
1519        right.callbacks,
1520        right.states,
1521        right.order,
1522        right.tag,
1523    ) {
1524        if !order.iter().any(|(_, identity)| *identity == candidate.1) {
1525            order.push(candidate);
1526        }
1527    }
1528    let order = order
1529        .into_iter()
1530        .map(|(binding, _)| binding)
1531        .collect::<Vec<_>>();
1532    let named = order
1533        .iter()
1534        .filter_map(|binding| match binding {
1535            ActionBinding::Named(name) => Some(name.clone()),
1536            ActionBinding::Callback(_) => None,
1537            ActionBinding::State(_) => None,
1538        })
1539        .collect();
1540    let callbacks = order
1541        .iter()
1542        .filter_map(|binding| match binding {
1543            ActionBinding::Named(_) => None,
1544            ActionBinding::Callback(callback) => Some(callback.clone()),
1545            ActionBinding::State(_) => None,
1546        })
1547        .collect();
1548    let states = order
1549        .iter()
1550        .filter_map(|binding| match binding {
1551            ActionBinding::State(callback) => Some(callback.clone()),
1552            ActionBinding::Named(_) | ActionBinding::Callback(_) => None,
1553        })
1554        .collect();
1555    (named, callbacks, states, order)
1556}
1557
1558fn merged_rules(left: &Tabnas, left_tag: &str, right: &Tabnas, right_tag: &str) -> Vec<MergedRule> {
1559    let names = left
1560        .rules
1561        .keys()
1562        .chain(right.rules.keys())
1563        .cloned()
1564        .collect::<BTreeSet<_>>();
1565    names
1566        .into_iter()
1567        .map(|name| {
1568            let left_rule = left.rules.get(&name);
1569            let right_rule = right.rules.get(&name);
1570            let empty_named = Vec::new();
1571            let empty_callbacks = Vec::new();
1572            let empty_states = Vec::new();
1573            let empty_order = Vec::new();
1574            let left_open = left_rule
1575                .map(|rule| {
1576                    rule.open
1577                        .iter()
1578                        .map(|alt| portable_alt(left, alt, left_tag))
1579                        .collect()
1580                })
1581                .unwrap_or_default();
1582            let right_open = right_rule
1583                .map(|rule| {
1584                    rule.open
1585                        .iter()
1586                        .map(|alt| portable_alt(right, alt, right_tag))
1587                        .collect()
1588                })
1589                .unwrap_or_default();
1590            let left_close = left_rule
1591                .map(|rule| {
1592                    rule.close
1593                        .iter()
1594                        .map(|alt| portable_alt(left, alt, left_tag))
1595                        .collect()
1596                })
1597                .unwrap_or_default();
1598            let right_close = right_rule
1599                .map(|rule| {
1600                    rule.close
1601                        .iter()
1602                        .map(|alt| portable_alt(right, alt, right_tag))
1603                        .collect()
1604                })
1605                .unwrap_or_default();
1606            let phase =
1607                |select_named: fn(&RuleSpec) -> &Vec<String>,
1608                 select_callbacks: fn(&RuleSpec) -> &Vec<ContextAction>,
1609                 select_states: fn(&RuleSpec) -> &Vec<crate::StateAction>,
1610                 select_order: fn(&RuleSpec) -> &Vec<ActionBinding>| {
1611                    merge_phase(
1612                        PhaseSource {
1613                            tabnas: left,
1614                            named: left_rule.map(select_named).unwrap_or(&empty_named),
1615                            callbacks: left_rule.map(select_callbacks).unwrap_or(&empty_callbacks),
1616                            states: left_rule.map(select_states).unwrap_or(&empty_states),
1617                            order: left_rule.map(select_order).unwrap_or(&empty_order),
1618                            tag: left_tag,
1619                        },
1620                        PhaseSource {
1621                            tabnas: right,
1622                            named: right_rule.map(select_named).unwrap_or(&empty_named),
1623                            callbacks: right_rule.map(select_callbacks).unwrap_or(&empty_callbacks),
1624                            states: right_rule.map(select_states).unwrap_or(&empty_states),
1625                            order: right_rule.map(select_order).unwrap_or(&empty_order),
1626                            tag: right_tag,
1627                        },
1628                    )
1629                };
1630            let (bo, bo_fns, bo_state_fns, bo_order) = phase(
1631                |rule| &rule.bo,
1632                |rule| &rule.bo_fns,
1633                |rule| &rule.bo_state_fns,
1634                |rule| &rule.bo_order,
1635            );
1636            let (ao, ao_fns, ao_state_fns, ao_order) = phase(
1637                |rule| &rule.ao,
1638                |rule| &rule.ao_fns,
1639                |rule| &rule.ao_state_fns,
1640                |rule| &rule.ao_order,
1641            );
1642            let (bc, bc_fns, bc_state_fns, bc_order) = phase(
1643                |rule| &rule.bc,
1644                |rule| &rule.bc_fns,
1645                |rule| &rule.bc_state_fns,
1646                |rule| &rule.bc_order,
1647            );
1648            let (ac, ac_fns, ac_state_fns, ac_order) = phase(
1649                |rule| &rule.ac,
1650                |rule| &rule.ac_fns,
1651                |rule| &rule.ac_state_fns,
1652                |rule| &rule.ac_order,
1653            );
1654            MergedRule {
1655                name,
1656                open: interleave(left_open, right_open),
1657                close: interleave(left_close, right_close),
1658                bo,
1659                ao,
1660                bc,
1661                ac,
1662                bo_fns,
1663                ao_fns,
1664                bc_fns,
1665                ac_fns,
1666                bo_state_fns,
1667                ao_state_fns,
1668                bc_state_fns,
1669                ac_state_fns,
1670                bo_order,
1671                ao_order,
1672                bc_order,
1673                ac_order,
1674            }
1675        })
1676        .collect()
1677}
1678
1679fn prefix_hash_map<T: Clone>(source: &HashMap<String, T>, tag: &str) -> HashMap<String, T> {
1680    source
1681        .iter()
1682        .map(|(name, value)| (rename_ref(name, tag), value.clone()))
1683        .collect()
1684}
1685
1686/// Both sides' guards, each under its side's tag, so that two grammars
1687/// that name a guard alike each keep theirs: a merged parser holds to the
1688/// bounds of both. Every name is prefixed, whatever it contains: a guard
1689/// name is an identity, not a reference, so `rename_ref`'s exemption for
1690/// builtin action names (anything with a `$`) must not apply, or two such
1691/// names would collide and one side's bound would be dropped.
1692fn combine_guards(
1693    left: &IndexMap<String, crate::ParseGuard>,
1694    left_tag: &str,
1695    right: &IndexMap<String, crate::ParseGuard>,
1696    right_tag: &str,
1697) -> IndexMap<String, crate::ParseGuard> {
1698    let side = |guards: &IndexMap<String, crate::ParseGuard>, tag: &str| {
1699        guards
1700            .iter()
1701            .map(|(name, guard)| (format!("{tag}:{name}"), guard.clone()))
1702            .collect::<Vec<_>>()
1703    };
1704    side(left, left_tag)
1705        .into_iter()
1706        .chain(side(right, right_tag))
1707        .collect()
1708}
1709
1710fn combine_prefixed<T: Clone>(
1711    left: &HashMap<String, T>,
1712    left_tag: &str,
1713    right: &HashMap<String, T>,
1714    right_tag: &str,
1715) -> HashMap<String, T> {
1716    let mut out = prefix_hash_map(left, left_tag);
1717    out.extend(prefix_hash_map(right, right_tag));
1718    out
1719}
1720
1721#[derive(Clone)]
1722struct MergedInstall {
1723    rules: Vec<MergedRule>,
1724    actions: HashMap<String, Action>,
1725    context_actions: HashMap<String, ContextAction>,
1726    matched_actions: HashMap<String, crate::AltAction>,
1727    state_actions: HashMap<String, crate::StateAction>,
1728    token_subscribers: Vec<TokenSubscriber>,
1729    lex_subscribers: Vec<LexSubscriber>,
1730    rule_subscribers: Vec<RuleSubscriber>,
1731    rule_done_subscribers: Vec<RuleDoneSubscriber>,
1732    parse_guards: IndexMap<String, crate::ParseGuard>,
1733    alt_conditions: HashMap<String, crate::AltCondition>,
1734    alt_match_conditions: HashMap<String, crate::AltConditionWithMatch>,
1735    alt_lexer_conditions: HashMap<String, crate::AltConditionWithLexer>,
1736    alt_lexer_match_conditions: HashMap<String, crate::AltConditionWithLexerAndMatch>,
1737    alt_modifiers: HashMap<String, crate::AltModifier>,
1738    alt_match_modifiers: HashMap<String, crate::AltModifierWithMatch>,
1739    alt_errors: HashMap<String, crate::AltError>,
1740    alt_match_errors: HashMap<String, crate::AltErrorWithMatch>,
1741    alt_pushes: HashMap<String, crate::AltNext>,
1742    alt_match_pushes: HashMap<String, crate::AltNextWithMatch>,
1743    alt_replaces: HashMap<String, crate::AltNext>,
1744    alt_match_replaces: HashMap<String, crate::AltNextWithMatch>,
1745    alt_backtracks: HashMap<String, crate::AltBack>,
1746    alt_match_backtracks: HashMap<String, crate::AltBackWithMatch>,
1747    match_token_refs: HashMap<String, (crate::MatchTokenCallback, bool)>,
1748    value_transform_refs: HashMap<String, crate::ValueTransform>,
1749    text_modifier_refs: HashMap<String, crate::TextModifier>,
1750    lex_check_refs: HashMap<String, crate::LexCheck>,
1751    comment_suffix_refs: HashMap<String, crate::CommentSuffixMatcher>,
1752    match_value_refs: HashMap<String, crate::MatchTokenCallback>,
1753    parse_prepare_refs: HashMap<String, crate::ParsePrepare>,
1754    budget_check_refs: HashMap<String, crate::BudgetCheck>,
1755    lex_match_refs: HashMap<String, crate::LexMatcherCallback>,
1756    imperative_lex_match_refs: HashMap<String, crate::ImperativeLexMatcher>,
1757    lex_match_factory_refs: HashMap<String, crate::LexMatcherFactory>,
1758    error_suffix_refs: HashMap<String, crate::ErrorSuffixCallback>,
1759    config_modifier_refs: HashMap<String, crate::ConfigModifier>,
1760    parser_start_refs: HashMap<String, crate::ParserStart>,
1761    parser_start_instance_refs: HashMap<String, crate::ParserStartWithInstance>,
1762    parser_start_context_refs: HashMap<String, crate::ParserStartWithContext>,
1763    map_merge_refs: HashMap<String, crate::MapMerge>,
1764}
1765
1766impl MergedInstall {
1767    fn install(&self, tabnas: &mut Tabnas) {
1768        tabnas.rules = self
1769            .rules
1770            .iter()
1771            .map(|rule| {
1772                let rule = rule.materialize(&mut tabnas.options);
1773                (rule.name.clone(), rule)
1774            })
1775            .collect::<indexmap::IndexMap<_, _>>()
1776            .into();
1777        tabnas.actions = self.actions.clone().into();
1778        tabnas.context_actions = (self.context_actions.clone()).into();
1779        tabnas.matched_actions = (self.matched_actions.clone()).into();
1780        tabnas.state_actions = (self.state_actions.clone()).into();
1781        tabnas.token_subscribers = (self.token_subscribers.clone()).into();
1782        tabnas.lex_subscribers = (self.lex_subscribers.clone()).into();
1783        tabnas.rule_subscribers = (self.rule_subscribers.clone()).into();
1784        tabnas.rule_done_subscribers = (self.rule_done_subscribers.clone()).into();
1785        // Added, not assigned: `derive` re-runs this install on a copy of
1786        // the merged parent's guards, and a guard installed on that parent
1787        // after the merge has to survive it.
1788        for (name, guard) in &self.parse_guards {
1789            tabnas.parse_guards.insert(name.clone(), guard.clone());
1790        }
1791        tabnas.alt_conditions = self.alt_conditions.clone();
1792        tabnas.alt_match_conditions = self.alt_match_conditions.clone();
1793        tabnas.alt_lexer_conditions = self.alt_lexer_conditions.clone();
1794        tabnas.alt_lexer_match_conditions = self.alt_lexer_match_conditions.clone();
1795        tabnas.alt_modifiers = self.alt_modifiers.clone();
1796        tabnas.alt_match_modifiers = self.alt_match_modifiers.clone();
1797        tabnas.alt_errors = self.alt_errors.clone();
1798        tabnas.alt_match_errors = self.alt_match_errors.clone();
1799        tabnas.alt_pushes = self.alt_pushes.clone();
1800        tabnas.alt_match_pushes = self.alt_match_pushes.clone();
1801        tabnas.alt_replaces = self.alt_replaces.clone();
1802        tabnas.alt_match_replaces = self.alt_match_replaces.clone();
1803        tabnas.alt_backtracks = self.alt_backtracks.clone();
1804        tabnas.alt_match_backtracks = self.alt_match_backtracks.clone();
1805        tabnas.match_token_refs = self.match_token_refs.clone();
1806        tabnas.value_transform_refs = self.value_transform_refs.clone();
1807        tabnas.text_modifier_refs = self.text_modifier_refs.clone();
1808        tabnas.lex_check_refs = self.lex_check_refs.clone();
1809        tabnas.comment_suffix_refs = self.comment_suffix_refs.clone();
1810        tabnas.match_value_refs = self.match_value_refs.clone();
1811        tabnas.parse_prepare_refs = self.parse_prepare_refs.clone();
1812        tabnas.budget_check_refs = self.budget_check_refs.clone();
1813        tabnas.lex_match_refs = self.lex_match_refs.clone();
1814        tabnas.imperative_lex_match_refs = self.imperative_lex_match_refs.clone();
1815        tabnas.lex_match_factory_refs = self.lex_match_factory_refs.clone();
1816        tabnas.error_suffix_refs = self.error_suffix_refs.clone();
1817        tabnas.config_modifier_refs = self.config_modifier_refs.clone();
1818        tabnas.parser_start_refs = self.parser_start_refs.clone();
1819        tabnas.parser_start_instance_refs = self.parser_start_instance_refs.clone();
1820        tabnas.parser_start_context_refs = self.parser_start_context_refs.clone();
1821        tabnas.map_merge_refs = self.map_merge_refs.clone();
1822    }
1823}
1824
1825fn merge_plugin_value(left: &Value, right: &Value, path: &str) -> Result<Value, MergeError> {
1826    match (left, right) {
1827        (Value::Undefined, value) | (value, Value::Undefined) => Ok(value.clone()),
1828        (Value::Object(left), Value::Object(right)) => {
1829            let mut out = IndexMap::new();
1830            for key in ordered_keys(left, right) {
1831                let value = match (left.get(&key), right.get(&key)) {
1832                    (Some(left), Some(right)) => {
1833                        merge_plugin_value(left, right, &format!("{path}.{key}"))?
1834                    }
1835                    (Some(value), None) | (None, Some(value)) => value.clone(),
1836                    (None, None) => unreachable!(),
1837                };
1838                out.insert(key, value);
1839            }
1840            Ok(Value::object(out))
1841        }
1842        _ if left.deep_equal(right) => Ok(left.clone()),
1843        _ => Err(conflict(path)),
1844    }
1845}
1846
1847fn merge_decorations(
1848    left: &IndexMap<String, crate::Decoration>,
1849    right: &IndexMap<String, crate::Decoration>,
1850) -> Result<IndexMap<String, crate::Decoration>, MergeError> {
1851    let mut out = left.clone();
1852    for (name, value) in right {
1853        if let Some(previous) = out.get(name) {
1854            if !previous.equivalent(value) {
1855                return Err(conflict(&format!("decoration.{name}")));
1856            }
1857        } else {
1858            out.insert(name.clone(), value.clone());
1859        }
1860    }
1861    Ok(out)
1862}
1863
1864pub(crate) fn merge(left: &Tabnas, right: &Tabnas) -> Result<Tabnas, MergeError> {
1865    fn tag<'a>(tabnas: &'a Tabnas, which: &str) -> Result<&'a str, MergeError> {
1866        let tag = tabnas.options.tag.as_str();
1867        if tag.is_empty() || tag == "-" {
1868            Err(MergeError(format!(
1869                "merge: the {which} instance needs a tag option (used to prefix its named actions)"
1870            )))
1871        } else {
1872            Ok(tag)
1873        }
1874    }
1875
1876    let left_tag = tag(left, "first")?;
1877    let right_tag = tag(right, "second")?;
1878    if left_tag == right_tag {
1879        return Err(MergeError(format!(
1880            "merge: instance tags must differ, both are {left_tag:?}"
1881        )));
1882    }
1883    let (left, left_tag, right, right_tag) = if left_tag < right_tag {
1884        (left, left_tag, right, right_tag)
1885    } else {
1886        (right, right_tag, left, left_tag)
1887    };
1888
1889    let mut options = merge_options(&left.options, &right.options)?;
1890    options.tag = format!("{left_tag}~{right_tag}");
1891    let plugin_options = merge_plugin_value(
1892        &Value::object(left.plugin_options.clone()),
1893        &Value::object(right.plugin_options.clone()),
1894        "plugin",
1895    )?;
1896    let Value::Object(plugin_options) = plugin_options else {
1897        unreachable!()
1898    };
1899    let decorations = merge_decorations(&left.decorations, &right.decorations)?;
1900
1901    let install = MergedInstall {
1902        rules: merged_rules(left, left_tag, right, right_tag),
1903        actions: combine_prefixed(&left.actions, left_tag, &right.actions, right_tag),
1904        context_actions: combine_prefixed(
1905            &left.context_actions,
1906            left_tag,
1907            &right.context_actions,
1908            right_tag,
1909        ),
1910        matched_actions: combine_prefixed(
1911            &left.matched_actions,
1912            left_tag,
1913            &right.matched_actions,
1914            right_tag,
1915        ),
1916        state_actions: combine_prefixed(
1917            &left.state_actions,
1918            left_tag,
1919            &right.state_actions,
1920            right_tag,
1921        ),
1922        token_subscribers: append_callbacks(&left.token_subscribers, &right.token_subscribers),
1923        lex_subscribers: append_callbacks(&left.lex_subscribers, &right.lex_subscribers),
1924        rule_subscribers: append_callbacks(&left.rule_subscribers, &right.rule_subscribers),
1925        rule_done_subscribers: append_callbacks(
1926            &left.rule_done_subscribers,
1927            &right.rule_done_subscribers,
1928        ),
1929        parse_guards: combine_guards(&left.parse_guards, left_tag, &right.parse_guards, right_tag),
1930        alt_conditions: combine_prefixed(
1931            &left.alt_conditions,
1932            left_tag,
1933            &right.alt_conditions,
1934            right_tag,
1935        ),
1936        alt_match_conditions: combine_prefixed(
1937            &left.alt_match_conditions,
1938            left_tag,
1939            &right.alt_match_conditions,
1940            right_tag,
1941        ),
1942        alt_lexer_conditions: combine_prefixed(
1943            &left.alt_lexer_conditions,
1944            left_tag,
1945            &right.alt_lexer_conditions,
1946            right_tag,
1947        ),
1948        alt_lexer_match_conditions: combine_prefixed(
1949            &left.alt_lexer_match_conditions,
1950            left_tag,
1951            &right.alt_lexer_match_conditions,
1952            right_tag,
1953        ),
1954        alt_modifiers: combine_prefixed(
1955            &left.alt_modifiers,
1956            left_tag,
1957            &right.alt_modifiers,
1958            right_tag,
1959        ),
1960        alt_match_modifiers: combine_prefixed(
1961            &left.alt_match_modifiers,
1962            left_tag,
1963            &right.alt_match_modifiers,
1964            right_tag,
1965        ),
1966        alt_errors: combine_prefixed(&left.alt_errors, left_tag, &right.alt_errors, right_tag),
1967        alt_match_errors: combine_prefixed(
1968            &left.alt_match_errors,
1969            left_tag,
1970            &right.alt_match_errors,
1971            right_tag,
1972        ),
1973        alt_pushes: combine_prefixed(&left.alt_pushes, left_tag, &right.alt_pushes, right_tag),
1974        alt_match_pushes: combine_prefixed(
1975            &left.alt_match_pushes,
1976            left_tag,
1977            &right.alt_match_pushes,
1978            right_tag,
1979        ),
1980        alt_replaces: combine_prefixed(
1981            &left.alt_replaces,
1982            left_tag,
1983            &right.alt_replaces,
1984            right_tag,
1985        ),
1986        alt_match_replaces: combine_prefixed(
1987            &left.alt_match_replaces,
1988            left_tag,
1989            &right.alt_match_replaces,
1990            right_tag,
1991        ),
1992        alt_backtracks: combine_prefixed(
1993            &left.alt_backtracks,
1994            left_tag,
1995            &right.alt_backtracks,
1996            right_tag,
1997        ),
1998        alt_match_backtracks: combine_prefixed(
1999            &left.alt_match_backtracks,
2000            left_tag,
2001            &right.alt_match_backtracks,
2002            right_tag,
2003        ),
2004        match_token_refs: combine_prefixed(
2005            &left.match_token_refs,
2006            left_tag,
2007            &right.match_token_refs,
2008            right_tag,
2009        ),
2010        value_transform_refs: combine_prefixed(
2011            &left.value_transform_refs,
2012            left_tag,
2013            &right.value_transform_refs,
2014            right_tag,
2015        ),
2016        text_modifier_refs: combine_prefixed(
2017            &left.text_modifier_refs,
2018            left_tag,
2019            &right.text_modifier_refs,
2020            right_tag,
2021        ),
2022        lex_check_refs: combine_prefixed(
2023            &left.lex_check_refs,
2024            left_tag,
2025            &right.lex_check_refs,
2026            right_tag,
2027        ),
2028        comment_suffix_refs: combine_prefixed(
2029            &left.comment_suffix_refs,
2030            left_tag,
2031            &right.comment_suffix_refs,
2032            right_tag,
2033        ),
2034        match_value_refs: combine_prefixed(
2035            &left.match_value_refs,
2036            left_tag,
2037            &right.match_value_refs,
2038            right_tag,
2039        ),
2040        parse_prepare_refs: combine_prefixed(
2041            &left.parse_prepare_refs,
2042            left_tag,
2043            &right.parse_prepare_refs,
2044            right_tag,
2045        ),
2046        budget_check_refs: combine_prefixed(
2047            &left.budget_check_refs,
2048            left_tag,
2049            &right.budget_check_refs,
2050            right_tag,
2051        ),
2052        lex_match_refs: combine_prefixed(
2053            &left.lex_match_refs,
2054            left_tag,
2055            &right.lex_match_refs,
2056            right_tag,
2057        ),
2058        imperative_lex_match_refs: combine_prefixed(
2059            &left.imperative_lex_match_refs,
2060            left_tag,
2061            &right.imperative_lex_match_refs,
2062            right_tag,
2063        ),
2064        lex_match_factory_refs: combine_prefixed(
2065            &left.lex_match_factory_refs,
2066            left_tag,
2067            &right.lex_match_factory_refs,
2068            right_tag,
2069        ),
2070        error_suffix_refs: combine_prefixed(
2071            &left.error_suffix_refs,
2072            left_tag,
2073            &right.error_suffix_refs,
2074            right_tag,
2075        ),
2076        config_modifier_refs: combine_prefixed(
2077            &left.config_modifier_refs,
2078            left_tag,
2079            &right.config_modifier_refs,
2080            right_tag,
2081        ),
2082        parser_start_refs: combine_prefixed(
2083            &left.parser_start_refs,
2084            left_tag,
2085            &right.parser_start_refs,
2086            right_tag,
2087        ),
2088        parser_start_instance_refs: combine_prefixed(
2089            &left.parser_start_instance_refs,
2090            left_tag,
2091            &right.parser_start_instance_refs,
2092            right_tag,
2093        ),
2094        parser_start_context_refs: combine_prefixed(
2095            &left.parser_start_context_refs,
2096            left_tag,
2097            &right.parser_start_context_refs,
2098            right_tag,
2099        ),
2100        map_merge_refs: combine_prefixed(
2101            &left.map_merge_refs,
2102            left_tag,
2103            &right.map_merge_refs,
2104            right_tag,
2105        ),
2106    };
2107
2108    let mut out = Tabnas::with_options(options);
2109    out.plugin_options = crate::value::unwrap_arc(plugin_options);
2110    out.decorations = decorations;
2111    let install_callback = install.clone();
2112    out.use_plugin(
2113        Plugin::new("merged", move |tabnas, _| {
2114            install_callback.install(tabnas);
2115            Ok(())
2116        }),
2117        None,
2118    )
2119    .map_err(|PluginError(message)| MergeError(format!("merge: {message}")))?;
2120    Ok(out)
2121}