omnist/ops/prune.rs
1//! Satisfiability analysis and schema pruning. Ported from
2//! `~/dev/omnist/omnist/ops/prune.py`.
3//!
4//! A record is *satisfiable* iff it admits at least one finite document, and
5//! [`prune`] returns an equivalent schema with everything that can never
6//! match removed. Satisfiability is a least fixpoint over the env's records:
7//! a record is satisfiable iff every field with `min >= 1` is either a
8//! `Scalar` or a `Ref` to a satisfiable record (fields with `min == 0` never
9//! block satisfiability -- they simply need not be emitted).
10
11use indexmap::{IndexMap, IndexSet};
12
13use crate::schema::{Field, FieldType, Record, Ref, Schema};
14
15/// The set of env record names that admit at least one finite document.
16///
17/// Least fixpoint: start with nothing known-satisfiable and repeatedly add
18/// any record all of whose mandatory (`min >= 1`) fields are already
19/// satisfiable. Monotonic on a finite env, so this always terminates. Only
20/// ever queried by membership (never iterated for its own order), so an
21/// `IndexSet` is used purely for the "no `HashMap`/`HashSet`" house style,
22/// not because iteration order matters here.
23pub fn satisfiable_set(s: &Schema) -> IndexSet<String> {
24 let mut sat: IndexSet<String> = IndexSet::new();
25 let mut changed = true;
26 while changed {
27 changed = false;
28 for (name, rec) in s.env() {
29 if sat.contains(name) {
30 continue;
31 }
32 if record_satisfiable(rec, &sat) {
33 sat.insert(name.clone());
34 changed = true;
35 }
36 }
37 }
38 sat
39}
40
41fn record_satisfiable(rec: &Record, sat: &IndexSet<String>) -> bool {
42 for f in rec.fields() {
43 if f.min < 1 {
44 continue;
45 }
46 if let FieldType::Ref(r) = &f.ty
47 && !sat.contains(&r.name)
48 {
49 return false;
50 }
51 }
52 true
53}
54
55/// True iff `s`'s root record is unsatisfiable -- the schema's language (the
56/// set of documents it accepts) is empty.
57pub fn is_empty(s: &Schema) -> bool {
58 !satisfiable_set(s).contains(&s.root().name)
59}
60
61/// An equivalent schema with everything that can never match removed:
62/// records unreachable from root are dropped; fields with `max == 0` are
63/// dropped; optional (`min == 0`) fields whose type is an unsatisfiable
64/// record are dropped; records left unreachable/unsatisfiable after the
65/// above are dropped from the environment too.
66///
67/// **Root-unsatisfiable case.** If the root record itself is unsatisfiable
68/// (`is_empty` is true), field pruning is *not* applied to the root: its
69/// mandatory fields are exactly what make it unsatisfiable, and stripping
70/// them would silently produce a *different*, satisfiable schema. Instead
71/// the root record is kept as-is and only the rest of the environment is
72/// reduced to what's reachable from it.
73///
74/// **Environment order (omnist-ts#56).** The returned environment iterates
75/// `s.env()` in its own declaration order, filtered to `reachable` -- not
76/// the other way round. `IndexSet::contains` is a membership check only;
77/// iterating the *set* itself instead of the schema's own `IndexMap` is
78/// exactly the bug TS's port had (traversal order leaking into the output
79/// instead of preserving the input's authored order).
80pub fn prune(s: &Schema) -> Schema {
81 let sat = satisfiable_set(s);
82 let root_ok = sat.contains(&s.root().name);
83 let reachable = reachable_from_root(s, &sat, root_ok);
84
85 let mut new_env: IndexMap<String, Record> = IndexMap::new();
86 for (name, rec) in s.env() {
87 if !reachable.contains(name) {
88 continue;
89 }
90 if !root_ok && *name == s.root().name {
91 new_env.insert(name.clone(), rec.clone());
92 } else {
93 new_env.insert(name.clone(), prune_record(rec, &sat));
94 }
95 }
96 Schema::new(Ref::new(s.root().name.clone()), new_env).expect(
97 "prune only drops unreachable records and never-emittable/unsatisfiable-optional \
98 fields; every surviving Ref still resolves within the surviving env",
99 )
100}
101
102fn reachable_from_root(s: &Schema, sat: &IndexSet<String>, root_ok: bool) -> IndexSet<String> {
103 let mut seen: IndexSet<String> = IndexSet::new();
104 let mut stack = vec![s.root().name.clone()];
105 while let Some(name) = stack.pop() {
106 if seen.contains(&name) {
107 continue;
108 }
109 // Every name here is either the root or a Ref target found on an
110 // already-visited record -- `Schema::new`'s `check_refs` guarantees
111 // both always resolve, so a fallible lookup is dead code (see
112 // `lint::reachable`'s identical note).
113 let rec = s
114 .env()
115 .get(&name)
116 .expect("Schema's own invariant: every Ref target resolves within its env");
117 seen.insert(name.clone());
118 let is_unpruned_root = name == s.root().name && !root_ok;
119 for f in rec.fields() {
120 if !is_unpruned_root {
121 if f.max == Some(0) {
122 continue;
123 }
124 if f.min == 0
125 && let FieldType::Ref(r) = &f.ty
126 && !sat.contains(&r.name)
127 {
128 continue;
129 }
130 }
131 if let FieldType::Ref(r) = &f.ty {
132 stack.push(r.name.clone());
133 }
134 }
135 }
136 seen
137}
138
139fn prune_record(rec: &Record, sat: &IndexSet<String>) -> Record {
140 let kept: Vec<Field> = rec
141 .fields()
142 .iter()
143 .filter(|f| {
144 if f.max == Some(0) {
145 return false;
146 }
147 if f.min == 0
148 && let FieldType::Ref(r) = &f.ty
149 && !sat.contains(&r.name)
150 {
151 return false;
152 }
153 true
154 })
155 .cloned()
156 .collect();
157 Record::new(kept).expect(
158 "filtering fields out of an already-valid Record cannot introduce a duplicate label",
159 )
160}