omnist/ops/
isomorphic.rs

1//! Schema isomorphism -- ported from `~/dev/omnist/omnist/ops/isomorphic.py`.
2//!
3//! Two schemas are equivalent iff their minimized (normalized) forms are
4//! isomorphic. That gives a second, algorithm-independent decision procedure
5//! for `equivalent`, structurally unrelated to bidirectional
6//! `subschema::compatible_with`, so the two can be cross-checked against
7//! each other in tests (the "dual-algorithm oracle" -- see `tests.rs`, the
8//! `minimize`/`isomorphic` triple-check strategy from the issue).
9//!
10//! [`is_isomorphic`] is deliberately not part of the crate's public surface
11//! commitment the way `subschema::equivalent` is -- it exists purely as an
12//! independent oracle for tests, matching the Python reference's choice to
13//! keep `_isomorphic` private.
14//!
15//! Algorithm: parallel traversal from both roots, building a bijection
16//! `name_a -> name_b` (and its inverse) between env record names as the
17//! traversal discovers pairs. At each visited record pair, `local_signature`
18//! must match; since it sorts fields by label and ref/scalar shape is part
19//! of the key, fields on the two sides line up one-to-one by label once the
20//! signatures agree. For each ref-typed field, the two targets are
21//! recursively required to be isomorphic, with the bijection enforced
22//! consistently in both directions.
23//!
24//! Both inputs are assumed already normalized (pruned + minimized) by the
25//! caller -- this module does not call `normalize` itself.
26
27use indexmap::IndexMap;
28
29use crate::schema::{FieldType, Schema};
30
31use super::prune::is_empty;
32use super::signature::local_signature;
33
34/// True iff normalized schemas `a` and `b` are isomorphic: there is a
35/// bijection between their env record names under which the two root
36/// records (and everything reachable from them) match exactly.
37///
38/// **Empty-schema convention.** If both `a` and `b` are unsatisfiable, they
39/// are treated as isomorphic (both accept the empty language). If exactly
40/// one is empty, they are *not* isomorphic.
41pub fn is_isomorphic(a: &Schema, b: &Schema) -> bool {
42    let (empty_a, empty_b) = (is_empty(a), is_empty(b));
43    if empty_a || empty_b {
44        return empty_a && empty_b;
45    }
46
47    let mut map_ab: IndexMap<String, String> = IndexMap::new();
48    let mut map_ba: IndexMap<String, String> = IndexMap::new();
49    walk(
50        a,
51        a.root().name.clone(),
52        b,
53        b.root().name.clone(),
54        &mut map_ab,
55        &mut map_ba,
56    )
57}
58
59fn walk(
60    a: &Schema,
61    na: String,
62    b: &Schema,
63    nb: String,
64    map_ab: &mut IndexMap<String, String>,
65    map_ba: &mut IndexMap<String, String>,
66) -> bool {
67    if map_ab.contains_key(&na) || map_ba.contains_key(&nb) {
68        // Already visited on at least one side: the bijection must agree
69        // both ways, or the schemas aren't isomorphic.
70        return map_ab.get(&na) == Some(&nb) && map_ba.get(&nb) == Some(&na);
71    }
72
73    map_ab.insert(na.clone(), nb.clone());
74    map_ba.insert(nb.clone(), na.clone());
75
76    let ra = a
77        .env()
78        .get(&na)
79        .expect("caller only walks names taken from a Schema's own root/Ref graph");
80    let rb = b
81        .env()
82        .get(&nb)
83        .expect("caller only walks names taken from a Schema's own root/Ref graph");
84    if local_signature(ra) != local_signature(rb) {
85        return false;
86    }
87
88    // local_signature sorts fields by label and includes the label in its
89    // key, so two records with equal signatures declare exactly the same
90    // set of labels -- fields on the two sides line up one-to-one by label.
91    for fa in ra.fields() {
92        let fb = rb
93            .field(&fa.label)
94            .expect("equal local_signature guarantees the same label set on both sides");
95        if let (FieldType::Ref(ra_ref), FieldType::Ref(rb_ref)) = (&fa.ty, &fb.ty)
96            && !walk(
97                a,
98                ra_ref.name.clone(),
99                b,
100                rb_ref.name.clone(),
101                map_ab,
102                map_ba,
103            )
104        {
105            return false;
106        }
107    }
108    true
109}
omnist/ops/isomorphic.rs

omnist/ops/
isomorphic.rs
