rules: validate merged nodes against the grammar
The arity/category backstop, the last of the five v1 conflict rules:
every merged node whose child list changed relative to its origin must
still satisfy node-types.json — required fields filled exactly as
often as allowed, every child kind admitted by its slot, supertypes
expanded through their subtypes. Individually clean branch edits can
combine into a structurally invalid tree no pairwise rule names; this
catches those as arity conflicts before the merge is declared clean.
Unchanged nodes are skipped so grammar corners the node-types model is
too strict about cannot flag untouched code.
Assisted-by: Claude Fable 5 via Claude Code
diff --git a/src/lang.rs b/src/lang.rs
index 29a6b95..3847c6f 100644
--- a/src/lang.rs
+++ b/src/lang.rs
@@ -125,6 +125,33 @@ impl NodeTypes {
self.by_kind.get(kind)
}
+ /// Whether `allowed` admits a child of `kind`, expanding supertype
+ /// entries (like rust's `_expression`) through their subtypes.
+ pub fn admits(&self, allowed: &[TypeRef], kind: &str) -> bool {
+ let mut seen: Vec<&str> = Vec::new();
+ self.admits_inner(allowed, kind, &mut seen)
+ }
+
+ fn admits_inner<'s>(
+ &'s self,
+ allowed: &'s [TypeRef],
+ kind: &str,
+ seen: &mut Vec<&'s str>,
+ ) -> bool {
+ allowed.iter().any(|type_ref| {
+ if type_ref.kind == kind {
+ return true;
+ }
+ if seen.iter().any(|&visited| visited == type_ref.kind) {
+ return false;
+ }
+ seen.push(&type_ref.kind);
+ self.by_kind
+ .get(&type_ref.kind)
+ .is_some_and(|node_type| self.admits_inner(&node_type.subtypes, kind, seen))
+ })
+ }
+
fn parse(json: &str) -> Result<Self, serde_json::Error> {
let entries: Vec<Entry> = serde_json::from_str(json)?;
// Keep only named entries: a kind name can appear twice — once
diff --git a/src/merge.rs b/src/merge.rs
index c40355d..f73aa6d 100644
--- a/src/merge.rs
+++ b/src/merge.rs
@@ -135,10 +135,19 @@ pub fn merge(o: &Tree, a: &Tree, b: &Tree) -> Result<MergeOutcome, Error> {
consumed: HashSet::new(),
};
let root = builder.build_survivor(o.root());
- Ok(MergeOutcome::Merged(MergedTree {
+ let merged = MergedTree {
nodes: builder.nodes,
root,
- }))
+ };
+
+ // The grammar backstop: individually clean edits can still combine
+ // into a structurally invalid tree.
+ let arity_conflicts = rules::arity(o, a, b, &merged);
+ if !arity_conflicts.is_empty() {
+ return Ok(MergeOutcome::Conflicts(arity_conflicts));
+ }
+
+ Ok(MergeOutcome::Merged(merged))
}
/// Which branch a graft comes from, with its diff to O and to-M pull
@@ -524,6 +533,74 @@ mod tests {
)
}
+ /// Clones O into a candidate MergedTree, skipping one node (and
+ /// its subtree).
+ fn clone_skipping(o: &Tree, skip: Option<crate::tree::NodeId>) -> MergedTree {
+ fn walk(
+ o: &Tree,
+ node: crate::tree::NodeId,
+ skip: Option<crate::tree::NodeId>,
+ nodes: &mut Vec<MergedNode>,
+ ) -> MergedId {
+ let children = o
+ .children(node)
+ .iter()
+ .filter(|&&c| Some(c) != skip)
+ .map(|&c| walk(o, c, skip, nodes))
+ .collect();
+ let id = MergedId(nodes.len());
+ nodes.push(MergedNode {
+ origin: Origin::O(node),
+ children,
+ });
+ id
+ }
+ let mut nodes = Vec::new();
+ let root = walk(o, o.root(), skip, &mut nodes);
+ MergedTree { nodes, root }
+ }
+
+ #[test]
+ fn an_emptied_required_field_fires_the_arity_rule() -> Result<(), Error> {
+ // Branch edits that are individually fine can combine into a
+ // grammar-invalid tree. The pairwise rules usually fire first
+ // in real merges, so drive the backstop directly: a candidate
+ // M that is O minus a required field (the if-condition).
+ let o = parse("fn f() { if c { } }", "rust")?;
+ let lang = Lang::by_name("rust").ok_or(Error::UnknownLanguage {
+ path: "rust".into(),
+ })?;
+ let condition_field = lang.language().field_id_for_name("condition");
+ let condition = o
+ .nodes()
+ .find(|&n| o.field_id(n).is_some() && o.field_id(n) == condition_field);
+ assert!(condition.is_some());
+
+ let broken = clone_skipping(&o, condition);
+ let conflicts = crate::rules::arity(&o, &o, &o, &broken);
+ assert!(!conflicts.is_empty());
+ assert!(conflicts.iter().all(|c| c.rule == "arity"));
+
+ // The intact clone passes.
+ let intact = clone_skipping(&o, None);
+ assert_eq!(crate::rules::arity(&o, &o, &o, &intact), Vec::new());
+ Ok(())
+ }
+
+ #[test]
+ fn variable_arity_growth_does_not_fire_the_arity_rule() -> Result<(), Error> {
+ // Two statements inserted into one block is legal growth; the
+ // full merge pipeline (now ending in the arity check) stays
+ // clean.
+ assert_merges(
+ "rust",
+ "fn f() { x(); }",
+ "fn f() { x(); y(); }",
+ "fn f() { w(); x(); }",
+ "fn f() { w(); x(); y(); }",
+ )
+ }
+
#[test]
fn a_wrap_pulls_the_survivor_into_the_graft() -> Result<(), Error> {
// A wraps the array one level deeper; B leaves it alone.
diff --git a/src/rules.rs b/src/rules.rs
index f32a763..f794092 100644
--- a/src/rules.rs
+++ b/src/rules.rs
@@ -6,7 +6,7 @@
use std::collections::{HashMap, HashSet};
use crate::diff::{Edit, Matching};
-use crate::merge::Conflict;
+use crate::merge::{Conflict, MergedId, MergedTree, Origin};
use crate::tree::{NodeId, Tree};
/// Everything a rule may consult: the three trees and the two diffs.
@@ -161,6 +161,148 @@ fn deletion_components(o: &Tree, script: &[Edit]) -> Vec<HashSet<NodeId>> {
components
}
+/// The arity/category backstop: every merged node whose child list
+/// changed relative to its origin must still satisfy the grammar's
+/// node-types.json — required fields present exactly as often as
+/// allowed, every child's kind admitted by its slot. This is the
+/// grammar-driven stand-in for per-language syntactic-consistency
+/// rules and catches structurally invalid combinations no pairwise
+/// rule names.
+pub(crate) fn arity(o: &Tree, a: &Tree, b: &Tree, merged: &MergedTree) -> Vec<Conflict> {
+ let mut conflicts = Vec::new();
+ let mut stack = vec![merged.root()];
+ while let Some(id) = stack.pop() {
+ stack.extend(merged.children(id).iter().copied());
+ let (tree, node) = resolve(o, a, b, merged.origin(id));
+ if !children_changed(o, a, b, merged, id) {
+ continue;
+ }
+ if let Some(node_type) = tree.lang().node_types().get(tree.kind(node))
+ && !node_satisfies(o, a, b, merged, id, tree, node_type)
+ {
+ let span = tree.span(node);
+ let conflict = match merged.origin(id) {
+ Origin::O(_) => Conflict {
+ span_o: Some(span),
+ span_a: None,
+ span_b: None,
+ rule: "arity",
+ },
+ Origin::A(_) => Conflict {
+ span_o: None,
+ span_a: Some(span),
+ span_b: None,
+ rule: "arity",
+ },
+ Origin::B(_) => Conflict {
+ span_o: None,
+ span_a: None,
+ span_b: Some(span),
+ rule: "arity",
+ },
+ };
+ if !conflicts.contains(&conflict) {
+ conflicts.push(conflict);
+ }
+ }
+ }
+ conflicts
+}
+
+/// Resolves an origin tag to the tree and node it points at.
+fn resolve<'t>(o: &'t Tree, a: &'t Tree, b: &'t Tree, origin: Origin) -> (&'t Tree, NodeId) {
+ match origin {
+ Origin::O(n) => (o, n),
+ Origin::A(n) => (a, n),
+ Origin::B(n) => (b, n),
+ }
+}
+
+/// Whether a merged node's child list differs from its origin node's —
+/// only changed nodes are validated, so grammar corners our
+/// node-types model is too strict about cannot flag untouched code.
+fn children_changed(o: &Tree, a: &Tree, b: &Tree, merged: &MergedTree, id: MergedId) -> bool {
+ let (tree, node) = resolve(o, a, b, merged.origin(id));
+ let expected = tree.children(node);
+ let actual = merged.children(id);
+ if actual.len() != expected.len() {
+ return true;
+ }
+ actual.iter().zip(expected).any(|(&mc, &ec)| {
+ let same_tree = match (merged.origin(id), merged.origin(mc)) {
+ (Origin::O(_), Origin::O(n))
+ | (Origin::A(_), Origin::A(n))
+ | (Origin::B(_), Origin::B(n)) => Some(n),
+ _ => None,
+ };
+ same_tree != Some(ec)
+ })
+}
+
+/// Whether a merged node's children satisfy its node-types entry.
+fn node_satisfies(
+ o: &Tree,
+ a: &Tree,
+ b: &Tree,
+ merged: &MergedTree,
+ id: MergedId,
+ parent_tree: &Tree,
+ node_type: &crate::lang::NodeType,
+) -> bool {
+ let node_types = parent_tree.lang().node_types();
+ let language = parent_tree.lang().language();
+
+ // Each merged child resolved to (field name, kind, named).
+ let members: Vec<(Option<&str>, &str, bool)> = merged
+ .children(id)
+ .iter()
+ .map(|&child| {
+ let (tree, node) = resolve(o, a, b, merged.origin(child));
+ let field = tree
+ .field_id(node)
+ .and_then(|fid| language.field_name_for_id(fid.get()));
+ (field, tree.kind(node), tree.is_named(node))
+ })
+ .collect();
+
+ for (name, slot) in &node_type.fields {
+ let filled: Vec<_> = members
+ .iter()
+ .filter(|(field, _, _)| field.is_some_and(|f| f == name))
+ .collect();
+ if slot.required && filled.is_empty() {
+ return false;
+ }
+ if !slot.multiple && filled.len() > 1 {
+ return false;
+ }
+ if filled
+ .iter()
+ .any(|(_, kind, _)| !node_types.admits(&slot.types, kind))
+ {
+ return false;
+ }
+ }
+
+ let loose: Vec<_> = members
+ .iter()
+ .filter(|(field, _, named)| field.is_none() && *named)
+ .collect();
+ if let Some(slot) = &node_type.children {
+ if slot.required && loose.is_empty() {
+ return false;
+ }
+ if loose
+ .iter()
+ .any(|(_, kind, _)| !node_types.admits(&slot.types, kind))
+ {
+ return false;
+ }
+ }
+
+ true
+}
+
/// insert-insert: both branches inserted at the same slot — same
/// parent image, same nearest preceding matched sibling — but the
/// inserted subtree sequences differ. Equal sequences at the same
diff --git a/src/tree.rs b/src/tree.rs
index 30794a5..0b5dd19 100644
--- a/src/tree.rs
+++ b/src/tree.rs
@@ -36,6 +36,7 @@ impl NodeId {
/// structural merge requires syntactically valid inputs.
#[derive(Debug)]
pub struct Tree {
+ lang: &'static Lang,
source: String,
nodes: Vec<NodeData>,
hashes: Vec<u64>,
@@ -86,6 +87,7 @@ impl Tree {
let nodes = lift(root);
let mut tree = Self {
+ lang,
source: source.into(),
nodes,
hashes: Vec::new(),
@@ -94,11 +96,22 @@ impl Tree {
Ok(tree)
}
+ /// The language this tree was parsed with.
+ pub fn lang(&self) -> &'static Lang {
+ self.lang
+ }
+
/// The root node (arena index 0).
pub fn root(&self) -> NodeId {
NodeId(0)
}
+ /// Whether the node is named (a grammar rule) as opposed to an
+ /// anonymous token like `+`.
+ pub fn is_named(&self, id: NodeId) -> bool {
+ self.node(id).named
+ }
+
/// All nodes in pre-order.
pub fn nodes(&self) -> impl Iterator<Item = NodeId> + '_ {
(0..self.nodes.len()).map(NodeId)