git-ents.gitmain
⌘K
foforge

crates/kernel/ents-query/tests/monotone.rs

monotone.rs378 lines · 14.7 KB · rusthistorycomment on this file
1//! Property test for monotone, entry-only semantics (`query.monotone`)
2//! and incremental-equals-full evaluation (`query.incremental`): random
3//! synthetic ref histories — advances, force-pushes, deletions, result
4//! recordings — checked after every transition against an independent
5//! naive oracle. The evaluator's incremental entry set must equal the
6//! oracle's `full(after) − full(before)` for every query whose static
7//! footprint the transitioned ref touches, and the empty set otherwise
8//! (`query.footprint`, `query.results`): a `results()` atom's entry set
9//! cannot be moved by an unrelated ref's reachability, only by its own
10//! results refs. The work set must equal the entry set minus recorded
11//! prefixes.
12
13#![expect(
14 clippy::expect_used,
15 clippy::indexing_slicing,
16 clippy::arithmetic_side_effects,
17 clippy::unreachable,
18 reason = "test code: fixture indexing panics are test failures"
19)]
20
21use std::collections::{HashMap, HashSet};
22
23use ents_model::{Member, Provenance, Status};
24use ents_query::{Evaluator, Query, Transition};
25use ents_testutil::{MemRefStore, ObjectStore, advance_ref, record_result, write_member};
26use gix_hash::ObjectId;
27use gix_object::{CommitRef, Find as _};
28use gix_ref_store::RefStoreRead as _;
29use proptest::prelude::*;
30
31const BRANCHES: [&str; 3] = ["refs/heads/main", "refs/heads/dev", "refs/heads/wip/x"];
32const EFFECTS: [&str; 2] = ["unit", "integ"];
33const STATUSES: [Status; 3] = [Status::Pass, Status::Fail, Status::Error];
34const MEMBERS: [&str; 2] = ["alice", "bob"];
35
36/// One randomized history operation.
37#[derive(Debug, Clone)]
38enum Op {
39 Advance {
40 branch: usize,
41 count: usize,
42 },
43 ForceTo {
44 branch: usize,
45 commit: usize,
46 },
47 Delete {
48 branch: usize,
49 },
50 Record {
51 effect: usize,
52 commit: usize,
53 status: usize,
54 short_len: usize,
55 },
56 Member {
57 who: usize,
58 },
59}
60
61fn op_strategy() -> impl Strategy<Value = Op> {
62 prop_oneof![
63 (0..3usize, 1..3usize).prop_map(|(branch, count)| Op::Advance { branch, count }),
64 (0..3usize, 0..64usize).prop_map(|(branch, commit)| Op::ForceTo { branch, commit }),
65 (0..3usize).prop_map(|branch| Op::Delete { branch }),
66 (0..2usize, 0..64usize, 0..3usize, 7..12usize).prop_map(
67 |(effect, commit, status, short_len)| Op::Record {
68 effect,
69 commit,
70 status,
71 short_len
72 }
73 ),
74 (0..2usize).prop_map(|who| Op::Member { who }),
75 ]
76}
77
78// ---------------------------------------------------------------------
79// The naive oracle: full evaluation from first principles.
80// ---------------------------------------------------------------------
81
82type Refs = HashMap<String, ObjectId>;
83
84fn snapshot(refs: &MemRefStore) -> Refs {
85 refs.iter_prefix("refs/")
86 .expect("iterable")
87 .map(|entry| {
88 let (name, oid) = entry.expect("readable");
89 (name.as_bstr().to_string(), oid)
90 })
91 .collect()
92}
93
94fn parents(objects: &ObjectStore, oid: ObjectId) -> Vec<ObjectId> {
95 let mut buf = Vec::new();
96 let data = objects
97 .try_find(&oid, &mut buf)
98 .expect("readable")
99 .expect("present");
100 CommitRef::from_bytes(data.data, oid.kind())
101 .expect("a commit")
102 .parents()
103 .collect()
104}
105
106fn reach(objects: &ObjectStore, tips: impl IntoIterator<Item = ObjectId>) -> HashSet<ObjectId> {
107 let mut seen = HashSet::new();
108 let mut queue: Vec<ObjectId> = tips.into_iter().collect();
109 while let Some(oid) = queue.pop() {
110 if seen.insert(oid) {
111 queue.extend(parents(objects, oid));
112 }
113 }
114 seen
115}
116
117fn reach_glob(objects: &ObjectStore, refs: &Refs, prefix: &str) -> HashSet<ObjectId> {
118 reach(
119 objects,
120 refs.iter()
121 .filter(|(name, _)| name.starts_with(prefix) && !name.starts_with("refs/meta/"))
122 .map(|(_, oid)| *oid),
123 )
124}
125
126/// Recorded shorts for one effect whose status satisfies `want`
127/// (`None` = any), read back through facet like the evaluator does.
128fn recorded(objects: &ObjectStore, refs: &Refs, effect: &str, want: Option<Status>) -> Vec<String> {
129 let prefix = format!("refs/meta/results/{effect}/");
130 refs.iter()
131 .filter_map(|(name, tip)| {
132 let short = name.strip_prefix(&prefix)?;
133 let mut buf = Vec::new();
134 let data = objects.try_find(tip, &mut buf).expect("readable")?;
135 let tree = CommitRef::from_bytes(data.data, tip.kind())
136 .expect("commit")
137 .tree();
138 let record: ents_model::ResultRecord =
139 facet_git_tree::deserialize(&tree, objects).expect("result tree");
140 (want.is_none() || want == Some(record.status)).then(|| short.to_owned())
141 })
142 .collect()
143}
144
145fn universe(objects: &ObjectStore, refs: &Refs) -> HashSet<ObjectId> {
146 reach(objects, refs.values().copied())
147}
148
149fn by_prefix(universe: &HashSet<ObjectId>, shorts: &[String]) -> HashSet<ObjectId> {
150 universe
151 .iter()
152 .copied()
153 .filter(|oid| {
154 let hex = oid.to_string();
155 shorts.iter().any(|s| hex.starts_with(s.as_str()))
156 })
157 .collect()
158}
159
160/// The six checked queries and their independent full evaluations.
161fn oracle(objects: &ObjectStore, refs: &Refs, query_index: usize) -> HashSet<ObjectId> {
162 let main = reach(objects, refs.get("refs/heads/main").copied());
163 match query_index {
164 0 => main,
165 1 => {
166 let heads = reach_glob(objects, refs, "refs/heads/");
167 let wip = reach_glob(objects, refs, "refs/heads/wip/");
168 heads.difference(&wip).copied().collect()
169 }
170 2 => {
171 let u = universe(objects, refs);
172 let pass = by_prefix(&u, &recorded(objects, refs, "unit", Some(Status::Pass)));
173 main.intersection(&pass).copied().collect()
174 }
175 3 => {
176 let u = universe(objects, refs);
177 let unit = by_prefix(&u, &recorded(objects, refs, "unit", Some(Status::Pass)));
178 let integ = by_prefix(&u, &recorded(objects, refs, "integ", Some(Status::Pass)));
179 unit.intersection(&integ).copied().collect()
180 }
181 4 => {
182 let dev = reach(objects, refs.get("refs/heads/dev").copied());
183 main.union(&dev).copied().collect()
184 }
185 // `meta(refs/meta/member/*)` (`query.meta`): the tip commits of
186 // matching author-written meta-refs directly, never a
187 // reachability closure — computed independently of both
188 // `Query::footprint` and the evaluator's `meta_tips`.
189 5 => refs
190 .iter()
191 .filter(|(name, _)| name.starts_with("refs/meta/member/"))
192 .map(|(_, oid)| *oid)
193 .collect(),
194 _ => unreachable!("six queries"),
195 }
196}
197
198const QUERIES: [&str; 6] = [
199 "rev(refs/heads/main)",
200 "rev(refs/heads/*) - rev(refs/heads/wip/*)",
201 "rev(refs/heads/main) & results(unit, pass)",
202 "results(unit, pass) & results(integ, pass)",
203 "rev(refs/heads/main) | rev(refs/heads/dev)",
204 "meta(refs/meta/member/*)",
205];
206
207/// Each of the six queries' static ref-footprint (`query.footprint`),
208/// hand-written independently of `Query::footprint` — this is what the
209/// oracle checks against, not a call into the thing under test.
210///
211/// A `results()` atom's footprint is its own results namespace, nothing
212/// else (`query.results`): a transition outside a query's footprint,
213/// such as deleting and recreating an unrelated branch, is a non-event
214/// for that query's entry set, even though it can change which commits
215/// `oracle`'s shared reachable-universe helper currently sees (a
216/// reconciliation-grade concern the diff below must not leak into
217/// incremental entry).
218fn footprint_touches(query_index: usize, moved: &str) -> bool {
219 let results_of = |effect: &str| moved.starts_with(&format!("refs/meta/results/{effect}/"));
220 match query_index {
221 0 => moved == "refs/heads/main",
222 1 => moved.starts_with("refs/heads/"),
223 2 => moved == "refs/heads/main" || results_of("unit"),
224 3 => results_of("unit") || results_of("integ"),
225 4 => moved == "refs/heads/main" || moved == "refs/heads/dev",
226 5 => moved.starts_with("refs/meta/member/"),
227 _ => unreachable!("six queries"),
228 }
229}
230
231// ---------------------------------------------------------------------
232// The property.
233// ---------------------------------------------------------------------
234
235proptest! {
236 #![proptest_config(ProptestConfig::with_cases(48))]
237
238 // @relation(query.monotone, query.incremental, query.set-ops, query.workset, query.footprint, query.results, scope=function, role=Verifies)
239 #[test]
240 fn entry_sets_equal_the_oracle_diff_over_random_histories(
241 ops in proptest::collection::vec(op_strategy(), 1..14)
242 ) {
243 let refs = MemRefStore::default();
244 let objects = ObjectStore::default();
245 let queries: Vec<Query> =
246 QUERIES.iter().map(|q| q.parse().expect("valid")).collect();
247 let evaluator = Evaluator::new(&refs, &objects);
248
249 let mut commits: Vec<ObjectId> = Vec::new();
250 let mut seconds = 1_000i64;
251
252 for op in ops {
253 let before = snapshot(&refs);
254
255 // Apply the operation; `moved` is the transitioned refname.
256 let moved: Option<String> = match op {
257 Op::Advance { branch, count } => {
258 let name = BRANCHES[branch];
259 seconds += 100;
260 commits.extend(advance_ref(&refs, &objects, name, count, seconds));
261 Some(name.to_owned())
262 }
263 Op::ForceTo { branch, commit } => {
264 if commits.is_empty() {
265 continue;
266 }
267 let name = BRANCHES[branch];
268 let target = commits[commit % commits.len()];
269 refs.set_str(name, target);
270 Some(name.to_owned())
271 }
272 Op::Delete { branch } => {
273 let name = BRANCHES[branch];
274 let full: gix::refs::FullName = name.try_into().expect("valid");
275 refs.remove(full.as_ref());
276 Some(name.to_owned())
277 }
278 Op::Record { effect, commit, status, short_len } => {
279 if commits.is_empty() {
280 continue;
281 }
282 let tested = commits[commit % commits.len()];
283 let short = tested.to_string()
284 .get(..short_len)
285 .expect("40 hex chars")
286 .to_owned();
287 seconds += 100;
288 record_result(
289 &refs, &objects, EFFECTS[effect], &short,
290 STATUSES[status], None, seconds,
291 );
292 Some(format!("refs/meta/results/{}/{short}", EFFECTS[effect]))
293 }
294 Op::Member { who } => {
295 let id = MEMBERS[who];
296 seconds += 100;
297 let member = Member::new(id, format!("key-{id}"), Provenance::AdminRegistered);
298 write_member(&refs, &objects, id, &member, None, seconds);
299 Some(format!("refs/meta/member/{id}"))
300 }
301 };
302
303 let after = snapshot(&refs);
304 let Some(moved) = moved else { continue };
305 let (old, new) = (before.get(&moved).copied(), after.get(&moved).copied());
306 if old == new {
307 continue; // a no-op transition denotes no frontier
308 }
309 let transition = Transition {
310 name: moved.as_str().try_into().expect("valid"),
311 old,
312 new,
313 };
314
315 for (index, query) in queries.iter().enumerate() {
316 // The hand-written mirror must agree with the real
317 // `Query::footprint()` on every generated transition —
318 // any silent divergence between the mirror's theory and
319 // the implementation's derivation is a loud failure
320 // here, not a false pass downstream.
321 let touches = footprint_touches(index, &moved);
322 prop_assert_eq!(
323 touches,
324 query.footprint().matches(transition.name.as_ref()),
325 "footprint mirror disagreement for {} on {:?}", QUERIES[index], moved
326 );
327
328 let full_before = oracle(&objects, &before, index);
329 let full_after = oracle(&objects, &after, index);
330
331 // Incremental entry == full(after) − full(before), but
332 // only within the query's own footprint; a transition
333 // outside it is a non-event no matter what the raw diff
334 // of two full evaluations would suggest.
335 let expected: std::collections::BTreeSet<ObjectId> =
336 if touches {
337 full_after.difference(&full_before).copied().collect()
338 } else {
339 std::collections::BTreeSet::new()
340 };
341 let entered = evaluator
342 .entry_set(query, &transition)
343 .expect("evaluates");
344 prop_assert_eq!(
345 &entered, &expected,
346 "entry mismatch for {} under {:?}", QUERIES[index], transition
347 );
348
349 // Full evaluation agrees with the oracle outright.
350 let full = evaluator.eval(query).expect("evaluates");
351 let oracle_after: std::collections::BTreeSet<ObjectId> =
352 full_after.iter().copied().collect();
353 prop_assert_eq!(
354 &full, &oracle_after,
355 "full-eval mismatch for {}", QUERIES[index]
356 );
357 }
358
359 // The work set: trigger − results(self, any), on the plain
360 // rev trigger.
361 let trigger = &queries[0];
362 let entered = evaluator.entry_set(trigger, &transition).expect("evaluates");
363 let unit_any = recorded(&objects, &after, "unit", None);
364 let expected_work: std::collections::BTreeSet<ObjectId> = entered
365 .iter()
366 .copied()
367 .filter(|oid| {
368 let hex = oid.to_string();
369 !unit_any.iter().any(|s| hex.starts_with(s.as_str()))
370 })
371 .collect();
372 let work = evaluator
373 .work_set("unit", trigger, &transition)
374 .expect("evaluates");
375 prop_assert_eq!(&work, &expected_work, "work-set mismatch");
376 }
377 }
378}