After a change to code or configuration, a developer wants to know within seconds whether anything broke. Running the whole suite (cheap model-level cases, then integration runs, then runs on a real device) takes minutes or hours. Running a subset picked by guesswork is fast, but it can skip a case that now fails, and a missed failure is worse than a slow answer.
None of the parts used here is new. Recording what a computation reads, re-running only what a change can reach, and ordering checks from cheap to faithful are all known techniques, and each is credited below. The point of this article is the combination: I state the goal precisely, put the three parts together into one procedure, and prove that the procedure achieves the goal. Sometimes that is the useful piece of work.
All Lean below is core Lean 4 (checked with 4.16.0). The code blocks, joined in order, form one file that compiles with no errors, no warnings and no sorry, admit or added axiom. #print axioms on the theorems shows only the standard axioms that simp and omega use (propext, Quot.sound, Classical.choice).
The goal
A suite is a list of test cases. Each case produces a verdict, pass or fail, from the current state of everything it can see. A change moves that state from to . The procedure keeps a cache of past results and, after each change, updates it. I want four things from it.
Goal.
- Exactness. After a change, the cached verdicts equal the verdicts a full re-run of every case would give on the new state .
- Durability. Exactness holds after any number of changes in a row, with no periodic full re-run to restore it.
- Cost. The number of cases executed for one change is at most the number of cases whose recorded inputs the change touches. A smaller change never executes more cases, and an empty change executes none.
- Tiers. A pass from a cheap tier has a stated meaning, and the release gate is sound for the facts it checks. Every such claim names the hypothesis it rests on.
“In seconds” is not a theorem. Wall-clock time depends on how long each selected case takes, which no model of this size can know. What the theorems fix is how many cases run and which tier can answer first. If the cheapest tier’s cases are fast, the first answer is fast. That last step is an engineering property, and the limits section returns to it.
The components
Dynamic read sets. While a computation runs, record every location it reads. If a later state agrees with the earlier one on those locations, the computation would read the same things and return the same result, so it need not run again. This is the verifying-trace idea from “Build systems à la carte” (ICFP 2018), where build tasks with dynamic inputs are modelled as computations that request their inputs one at a time. “Shake before building: replacing make with Haskell” (ICFP 2012) records the inputs a build rule actually requests. Self-adjusting computation, from “Adaptive functional programming” (POPL 2002) and “Adapton: composable, demand-driven incremental computation” (PLDI 2014), records the same kind of information at a finer grain to re-execute only what a change reaches.
Safe regression test selection. After a change, re-run only the cases whose earlier execution touched a changed part, and argue that no other case can change its verdict. “Safe” means that no case whose verdict could change is left out. The formulation follows “A safe, efficient regression test selection technique” (ACM Transactions on Software Engineering and Methodology, 1997), which selects by the parts of a program that each case exercised.
Tiers related by refinement. Checks are ordered from cheap and abstract (a model of the system) to expensive and faithful (the system on a device). The link between a tier and the next is a refinement claim: what the abstract level establishes also holds at the concrete level. The idea goes back to “Proof of correctness of data representations” (Acta Informatica, 1972) and “Program development by stepwise refinement” (Communications of the ACM, 1971).
The combination
Procedure. Tiers are numbered , cheapest first. Tier is the device.
- Each tier has its own suite and its own cache. A cache entry holds, for one case, its last verdict and the read set recorded on the state the cache was built from.
- A change is given as a new state together with a changed set , a list of locations outside which agrees with the old state.
- In each tier, re-run exactly the cases whose cached read set meets , recording a fresh read set for each. Keep every other entry as it is.
- Report tier 0 first, then tier 1, and so on. The fast path reads the answer of one tier (usually tier 0). The release gate waits for every tier and requires every covered fact to pass.
The modelling choice that makes this checkable is that everything a case may depend on is a location in one store, and a case sees the store only by reading a location. Code lives in the store too: a source file’s content is the value at that file’s location, so editing code is writing to the store. Configuration, clocks, seeds and device state are locations in the same way. In a real system this is an obligation on the instrumentation, stated below as assumption A1.
Stores and computations
Store, computation, run. Locations and values are natural numbers, and a store is a function . A computation with results in is a tree built from two constructors: ends with result , and reads location and continues with applied to the value read. Running on gives a pair
where is the result and , the read set or footprint, lists the locations read, in the order the reads happen. Write for . A test case is a computation whose result is a Boolean verdict.
Agreement. Two stores agree on a list , written , if for every .
Which location a computation reads next can depend on values it has already read, because the continuation receives the value. The read set is therefore a property of one run on one store, not of the program text, and this is why it has to be recorded while the case runs.
namespace SoundFastTesting
/-! ## 1. Stores and computations that record what they read -/
abbrev Loc := Nat
abbrev Val := Nat
abbrev Store := Loc → Val
/-- A computation is a tree of reads ending in a result. -/
inductive Comp (α : Type) where
| ret : α → Comp α
| read : Loc → (Val → Comp α) → Comp α
/-- Run on a store; return the result and the read set, in read order. -/
def run {α : Type} : Comp α → Store → α × List Loc
| .ret a, _ => (a, [])
| .read l k, s => ((run (k (s l)) s).1, l :: (run (k (s l)) s).2)
/-- Two stores agree on a list of locations. -/
def Agree (s t : Store) (ls : List Loc) : Prop := ∀ l, l ∈ ls → s l = t l
Read-set soundness
Theorem 1 (read-set soundness). For every computation and stores : if , then .
Proof. Induction on . For both runs give . For , the read set on is followed by . Agreement on gives , so the run on continues with the same computation . Agreement on and the induction hypothesis give . Putting back in front of both read sets gives the claim. ∎
The equality is between pairs, so the run on has the same result and also the same read set. That second half matters below: a case that is not re-run keeps a footprint that is still correct for the new store.
/-- Theorem 1 (read-set soundness). -/
theorem read_set_sound {α : Type} (c : Comp α) :
∀ (s t : Store), Agree s t (run c s).2 → run c t = run c s := by
induction c with
| ret a => intro s t _; rfl
| read l k ih =>
intro s t h
have hl : s l = t l := h l (List.Mem.head _)
have rest : Agree s t (run (k (s l)) s).2 :=
fun x hx => h x (List.Mem.tail _ hx)
simp only [run]
rw [← hl, ih (s l) s t rest]
Selecting by intersection
Changed set, hit. For stores and a list , write when for every : the store differs from at most at locations in . A footprint hits when some location occurs in both.
Theorem 2 (selection soundness). If and does not hit , then . In particular, a test case whose footprint misses the changed set keeps its verdict.
Proof. Every in is outside , so . That is , and Theorem 1 applies. ∎
The Lean below defines membership and the hit test as Boolean functions, so that selection is something a program computes, and proves that a negative hit test means every footprint location lies outside the changed set.
/-! ## 2. Changed sets and selection -/
def memb (x : Loc) : List Loc → Bool
| [] => false
| y :: ys => x == y || memb x ys
/-- Does a footprint intersect a changed set? -/
def hits : List Loc → List Loc → Bool
| [], _ => false
| l :: ls, ch => memb l ch || hits ls ch
theorem hits_false {fp ch : List Loc} (h : hits fp ch = false) :
∀ l, l ∈ fp → memb l ch = false := by
induction fp with
| nil => intro l hl; cases hl
| cons x xs ih =>
intro l hl
simp only [hits, Bool.or_eq_false_iff] at h
cases hl with
| head => exact h.1
| tail _ hm => exact ih h.2 l hm
/-- `t` differs from `s` only at locations listed in `ch`. -/
def OffAgree (s t : Store) (ch : List Loc) : Prop :=
∀ l, memb l ch = false → s l = t l
/-- Theorem 2 (selection soundness, one case). -/
theorem selection_sound {α : Type} (c : Comp α) (s t : Store) (ch : List Loc)
(hst : OffAgree s t ch) (h : hits (run c s).2 ch = false) :
run c t = run c s :=
read_set_sound c s t (fun l hl => hst l (hits_false h l hl))
The selection step walks the suite and the cache together. For case with cached entry it produces
Theorem 2′ (selective re-run equals full re-run). If and the cache is the full run of the suite on , then refreshing it with and gives exactly the full run of the suite on .
Proof. Induction on the suite, one case at a time. If the cached footprint hits , the entry is replaced by by definition. Otherwise the entry stays , which equals by Theorem 2. ∎
/-- Re-run exactly the cases whose recorded footprint hits the change. -/
def refresh {α : Type} : List (Comp α) → List (α × List Loc) → List Loc → Store →
List (α × List Loc)
| c :: cs, e :: es, ch, t =>
(if hits e.2 ch then run c t else e) :: refresh cs es ch t
| _, _, _, _ => []
/-- Theorem 2' (selective re-run equals full re-run). -/
theorem refresh_exact {α : Type} (suite : List (Comp α)) (s t : Store) (ch : List Loc)
(hst : OffAgree s t ch) :
refresh suite (suite.map (fun c => run c s)) ch t = suite.map (fun c => run c t) := by
induction suite with
| nil => rfl
| cons c cs ih =>
simp only [List.map, refresh, ih]
cases hh : hits (run c s).2 ch with
| true => rfl
| false => simp only [selection_sound c s t ch hst hh]; rfl
A history is a list of steps . It is valid from when and for each . Replaying it applies the selection step once per change.
Theorem 2″ (the cache stays exact). If the history is valid from and the cache starts as the full run of the suite on , then after replaying the history the cache equals the full run of the suite on the final store .
Proof. Induction on the history. With no steps there is nothing to show. For a first step , Theorem 2′ turns the cache into the full run on , which is the starting condition for the rest of the history from , and the induction hypothesis finishes. ∎
The proof works only because each re-run case gets a fresh footprint, recorded on the store it ran on. A cache that kept old footprints for re-run cases could lose the starting condition after one step: if a re-run case now reads a different location, its stale footprint can miss a later change to that location. A case that is not re-run keeps its old footprint, which is still correct by the second half of Theorem 1.
/-- A history of changes, each with the store after it. -/
def Valid : Store → List (List Loc × Store) → Prop
| _, [] => True
| s, (ch, t) :: rest => OffAgree s t ch ∧ Valid t rest
def final : Store → List (List Loc × Store) → Store
| s, [] => s
| _, (_, t) :: rest => final t rest
def replay {α : Type} (suite : List (Comp α)) :
List (α × List Loc) → List (List Loc × Store) → List (α × List Loc)
| cache, [] => cache
| cache, (ch, t) :: rest => replay suite (refresh suite cache ch t) rest
/-- Theorem 2'' (the cache stays exact across any valid history). -/
theorem replay_exact {α : Type} (suite : List (Comp α)) :
∀ (hist : List (List Loc × Store)) (s : Store), Valid s hist →
replay suite (suite.map (fun c => run c s)) hist
= suite.map (fun c => run c (final s hist)) := by
intro hist
induction hist with
| nil => intro s _; rfl
| cons step rest ih =>
obtain ⟨ch, t⟩ := step
intro s hv
simp only [Valid] at hv
simp only [replay, final]
rw [refresh_exact suite s t ch hv.1]
exact ih t hv.2
Hit cases cannot be skipped in general. Take a case that reads location 0 and passes exactly when it sees 0. Let be the store that is 0 everywhere and the store that is 1 at location 0 and 0 elsewhere, so . The case gives true on and false on , and its footprint hits the change . So a rule that decides only from the recorded footprint and the changed set cannot skip a hit case in general: on this input it would report a stale verdict. This does not show that every hit case must be re-run (see the limits section). The block below also states Theorem 2 for Boolean verdicts alone, as kept_verdict, proves as bumped_off, and checks the rest of the example by decide.
/-- Corollary: verdicts of non-hit cases are unchanged. -/
theorem kept_verdict (c : Comp Bool) (s t : Store) (ch : List Loc)
(hst : OffAgree s t ch) (h : hits (run c s).2 ch = false) :
(run c t).1 = (run c s).1 := by
rw [selection_sound c s t ch hst h]
/-- A case that reads location 0 and passes exactly when it sees 0. -/
def probe : Comp Bool := .read 0 (fun v => .ret (v == 0))
/-- The store that is 1 at location 0 and 0 elsewhere. -/
def bumped : Store := fun l => if l == 0 then 1 else 0
/-- `bumped` differs from the all-zero store only inside the change `[0]`. -/
theorem bumped_off : OffAgree (fun _ => 0) bumped [0] := by
intro l h
simp [memb] at h
simp [bumped, h]
/-- Skipping this hit case under the valid change `[0]` would report a stale verdict. -/
example : (run probe (fun _ => 0)).1 = true ∧ (run probe bumped).1 = false ∧
hits (run probe (fun _ => 0)).2 [0] = true := by decide
The cost of selection
Let count the re-runs the selection step performs, and count the cache entries whose footprint hits . In Lean, is a separate recursive count, and an instrumented copy of the selection step, refreshC, returns the new cache together with the number of times it calls run. Two lemmas prove that its cache is the one refresh returns and that its count is , so is the number of executions by proof, not by reading the code.
Theorem 3 (cost).
- For every suite and cache, . When the suite and the cache have the same length, . Every cache the procedure produces has the suite’s length: the selection step returns a list of length , so starting from the full run of the suite, the length is kept through any history.
- is at most the size of the cache.
- If every location in is also in , then : a smaller change never executes more cases.
- : an empty change executes nothing.
Proof. Each is an induction on the cache (and the suite, for part 1), adding one per hitting entry. The length statements are inductions on the suite and on the history. For part 3, a footprint that hits also hits , by induction on the footprint. ∎
/-! ## 3. Cost of selection -/
def runs {α : Type} : List (Comp α) → List (α × List Loc) → List Loc → Nat
| _ :: cs, e :: es, ch => (if hits e.2 ch then 1 else 0) + runs cs es ch
| _, _, _ => 0
/-- The selection step, instrumented: also count the calls to `run`. -/
def refreshC {α : Type} : List (Comp α) → List (α × List Loc) → List Loc → Store →
List (α × List Loc) × Nat
| c :: cs, e :: es, ch, t =>
if hits e.2 ch then (run c t :: (refreshC cs es ch t).1, (refreshC cs es ch t).2 + 1)
else (e :: (refreshC cs es ch t).1, (refreshC cs es ch t).2)
| _, _, _, _ => ([], 0)
theorem refreshC_fst {α : Type} :
∀ (suite : List (Comp α)) (cache : List (α × List Loc)) (ch : List Loc) (t : Store),
(refreshC suite cache ch t).1 = refresh suite cache ch t := by
intro suite
induction suite with
| nil => intro cache ch t; cases cache <;> rfl
| cons c cs ih =>
intro cache ch t
cases cache with
| nil => rfl
| cons e es =>
simp only [refreshC, refresh]
split <;> simp [ih]
/-- `runs` is exactly the number of executions the selection step performs. -/
theorem refreshC_snd {α : Type} :
∀ (suite : List (Comp α)) (cache : List (α × List Loc)) (ch : List Loc) (t : Store),
(refreshC suite cache ch t).2 = runs suite cache ch := by
intro suite
induction suite with
| nil => intro cache ch t; cases cache <;> rfl
| cons c cs ih =>
intro cache ch t
cases cache with
| nil => rfl
| cons e es =>
simp only [refreshC, runs]
split <;> simp [ih] <;> omega
theorem refresh_length {α : Type} :
∀ (suite : List (Comp α)) (cache : List (α × List Loc)) (ch : List Loc) (t : Store),
(refresh suite cache ch t).length = min suite.length cache.length := by
intro suite
induction suite with
| nil => intro cache ch t; cases cache <;> rfl
| cons c cs ih =>
intro cache ch t
cases cache with
| nil => simp [refresh]
| cons e es =>
simp only [refresh, List.length_cons, ih]
omega
/-- Every cache the procedure produces has the suite's length. -/
theorem replay_length {α : Type} (suite : List (Comp α)) :
∀ (hist : List (List Loc × Store)) (cache : List (α × List Loc)),
cache.length = suite.length → (replay suite cache hist).length = suite.length := by
intro hist
induction hist with
| nil => intro cache h; exact h
| cons step rest ih =>
obtain ⟨ch, t⟩ := step
intro cache h
simp only [replay]
apply ih
rw [refresh_length, h]
omega
def hitCount {α : Type} : List (α × List Loc) → List Loc → Nat
| [], _ => 0
| e :: es, ch => (if hits e.2 ch then 1 else 0) + hitCount es ch
/-- Theorem 3, part 1: runs performed ≤ cached cases whose footprint hits the change. -/
theorem runs_le_hits {α : Type} :
∀ (suite : List (Comp α)) (cache : List (α × List Loc)) (ch : List Loc),
runs suite cache ch ≤ hitCount cache ch := by
intro suite
induction suite with
| nil => intro cache ch; cases cache <;> simp [runs, hitCount]
| cons c cs ih =>
intro cache ch
cases cache with
| nil => simp [runs]
| cons e es =>
have := ih es ch
simp only [runs, hitCount]; omega
/-- Theorem 3, part 1: equality when suite and cache have the same length. -/
theorem runs_eq_hits {α : Type} :
∀ (suite : List (Comp α)) (cache : List (α × List Loc)) (ch : List Loc),
suite.length = cache.length → runs suite cache ch = hitCount cache ch := by
intro suite
induction suite with
| nil => intro cache ch h; cases cache with
| nil => rfl
| cons _ _ => simp at h
| cons c cs ih =>
intro cache ch h
cases cache with
| nil => simp at h
| cons e es =>
simp only [List.length_cons, Nat.add_right_cancel_iff] at h
simp only [runs, hitCount, ih es ch h]
/-- Theorem 3, part 2. -/
theorem hitCount_le_length {α : Type} :
∀ (cache : List (α × List Loc)) (ch : List Loc), hitCount cache ch ≤ cache.length := by
intro cache ch
induction cache with
| nil => simp [hitCount]
| cons e es ih =>
simp only [hitCount, List.length_cons]
split <;> omega
theorem hits_mono {ch ch' : List Loc} (hsub : ∀ l, memb l ch = true → memb l ch' = true) :
∀ fp, hits fp ch = true → hits fp ch' = true := by
intro fp
induction fp with
| nil => simp [hits]
| cons x xs ih =>
intro h
simp only [hits, Bool.or_eq_true] at h ⊢
cases h with
| inl h => exact Or.inl (hsub x h)
| inr h => exact Or.inr (ih h)
/-- Theorem 3, part 3: a smaller change never runs more cases. -/
theorem hitCount_mono {α : Type} {ch ch' : List Loc}
(hsub : ∀ l, memb l ch = true → memb l ch' = true) :
∀ (cache : List (α × List Loc)), hitCount cache ch ≤ hitCount cache ch' := by
intro cache
induction cache with
| nil => simp [hitCount]
| cons e es ih =>
simp only [hitCount]
cases h : hits e.2 ch with
| false => simp only [Bool.false_eq_true, ↓reduceIte]; split <;> omega
| true =>
have h' := hits_mono hsub e.2 h
simp only [↓reduceIte, h']; omega
/-- Theorem 3, part 4: empty change, nothing runs. -/
theorem hitCount_nil {α : Type} (cache : List (α × List Loc)) : hitCount cache [] = 0 := by
have : ∀ fp : List Loc, hits fp [] = false := by
intro fp; induction fp with
| nil => rfl
| cons x xs ih => simp [hits, memb, ih]
induction cache with
| nil => rfl
| cons e es ih => simp [hitCount, this, ih]
Tiers
Tiers. A tier structure over a type of facts has a top index and two predicates, (tier checks fact ) and (tier ‘s check of passes). Let be a predicate on facts: what is actually the case on the real system.
- Faithful (hypothesis): if tier covers and passes it, then .
- Refines (hypothesis): for every , if tier covers and passes , then tier covers and passes .
- Gate passes: for every and every that tier covers, tier passes .
Faithful says the device tier is the real system for the facts it checks. Refines says a pass at one tier predicts a pass at the next, which in particular requires every higher tier to check every fact that a lower tier checks and passes. Neither is proved here. They are claims about how the tiers were built, and the theorems below show exactly where each one is used.
Theorem 4.
- (a) Gate soundness at the top. Faithful and gate passes imply for every that tier covers. Refines is not used.
- (b) Fast-path soundness. Faithful and Refines imply: for every , if tier covers and passes , then .
- (c) Gate soundness for all tiers. Faithful, Refines and gate passes imply for every that any tier covers.
- (d) Early refutation. Faithful and Refines imply: for every , if tier covers and is false, then tier does not pass .
Proof. (a) Gate passes at gives a top-tier pass, and Faithful turns it into truth. (b) Induction on lifts a pass at tier to a pass at tier , one Refines step at a time, and Faithful finishes. (c) Gate passes supplies the pass that (b) needs. (d) is the contrapositive of (b). ∎
/-! ## 4. Tiers -/
structure Tiers (Fact : Type) where
top : Nat
covers : Nat → Fact → Prop
pass : Nat → Fact → Prop
variable {Fact : Type}
/-- The top tier is the real system: its passes are true. (Hypothesis.) -/
def Faithful (T : Tiers Fact) (truth : Fact → Prop) : Prop :=
∀ f, T.covers T.top f → T.pass T.top f → truth f
/-- Each tier's pass on a fact it covers implies the next tier covers and passes it. -/
def Refines (T : Tiers Fact) : Prop :=
∀ i, i < T.top → ∀ f, T.covers i f → T.pass i f → T.covers (i+1) f ∧ T.pass (i+1) f
def GatePasses (T : Tiers Fact) : Prop :=
∀ i, i ≤ T.top → ∀ f, T.covers i f → T.pass i f
/-- Theorem 4a: the gate is sound for top-tier facts, with no refinement hypothesis. -/
theorem gate_sound_top (T : Tiers Fact) (truth : Fact → Prop)
(hF : Faithful T truth) (hG : GatePasses T) :
∀ f, T.covers T.top f → truth f :=
fun f hc => hF f hc (hG T.top (Nat.le_refl _) f hc)
theorem lift (T : Tiers Fact) (hR : Refines T) :
∀ d i f, i + d = T.top → T.covers i f → T.pass i f →
T.covers T.top f ∧ T.pass T.top f := by
intro d
induction d with
| zero => intro i f h hc hp; rw [← h]; exact ⟨hc, hp⟩
| succ d ih =>
intro i f h hc hp
have ⟨hc', hp'⟩ := hR i (by omega) f hc hp
exact ih (i+1) f (by omega) hc' hp'
/-- Theorem 4b: fast-path soundness: a pass at any tier certifies the facts it covers. -/
theorem fast_path_sound (T : Tiers Fact) (truth : Fact → Prop)
(hF : Faithful T truth) (hR : Refines T) :
∀ i, i ≤ T.top → ∀ f, T.covers i f → T.pass i f → truth f := by
intro i hi f hc hp
have ⟨hc', hp'⟩ := lift T hR (T.top - i) i f (by omega) hc hp
exact hF f hc' hp'
/-- Theorem 4c: the full gate is sound for every fact any tier covers. -/
theorem gate_sound_all (T : Tiers Fact) (truth : Fact → Prop)
(hF : Faithful T truth) (hR : Refines T) (hG : GatePasses T) :
∀ i, i ≤ T.top → ∀ f, T.covers i f → truth f :=
fun i hi f hc => fast_path_sound T truth hF hR i hi f hc (hG i hi f hc)
/-- Theorem 4d (contrapositive of 4b): under refinement, a false fact fails at the cheapest tier covering it. -/
theorem early_refutation (T : Tiers Fact) (truth : Fact → Prop)
(hF : Faithful T truth) (hR : Refines T) :
∀ i, i ≤ T.top → ∀ f, T.covers i f → ¬ truth f → ¬ T.pass i f :=
fun i hi f hc hn hp => hn (fast_path_sound T truth hF hR i hi f hc hp)
end SoundFastTesting
Theorem 4(d) runs in one direction only. A false fact fails at every tier that covers it, including the cheapest, so a bug is caught as early as the tiers allow. A failure at a cheap tier, however, does not show that the fact is false: a cheap tier may be stricter than the real system, and the hypotheses say nothing about that direction.
What the combination achieves
The two halves connect through the tier predicates. Fix a tier with suite of test cases, and let each fact that tier covers be checked by one case of . Read as “the verdict of that case on the current store is pass”. The procedure keeps one cache per tier and replays every change into each of them. By Theorem 2″, applied to each tier separately, every cached verdict equals the verdict a full re-run of that case would give on the current store. So the fast path and the release gate, read from the caches, evaluate the same predicates as a full re-run would, and Theorem 4 applies to them unchanged. Under this reading, Faithful and Refines are hypotheses about the current store and must hold for each store in the history. This step is an instance of Theorem 2″ argued in prose; the Lean file proves the two halves separately and does not state the instance as one theorem.
| goal | delivered by | rests on |
|---|---|---|
| exactness | Theorem 2′ | A1–A4 |
| durability | Theorem 2″ | A1–A4 |
| cost | Theorem 3 | A6 for what “cost” counts |
| fast path | Theorem 4(b), 4(d) | Faithful, Refines (A5) |
| release gate | Theorem 4(a) | Faithful only |
| release gate, all tiers | Theorem 4(c) | Faithful, Refines (A5) |
The release gate always includes the device tier because of the “release gate” row: Theorem 4(a) is the only tier result that does not depend on Refines, and Refines is an unproved claim about how faithful the cheaper tiers are. Requiring every tier to pass adds the guarantee of the last row, Theorem 4(c), which does depend on Refines. The fast path gives a quick answer whose soundness is conditional on Refines. The release gate gives an answer whose soundness for device-checked facts needs only Faithful. Selection keeps both cheap: in every tier, only the cases the change reaches are executed.
Limits and assumptions
The theorems hold in the model. These are the places where a real system has to meet the model.
- A1, complete instrumentation. Every input a case depends on is a store read that gets recorded: code, configuration, time, randomness, network and device state. In Lean this holds by construction, because a computation can only see the store through . In a real system it is an obligation on the implementation, and an unrecorded input takes the case outside the model, and Theorem 1 then no longer applies to it, with no visible sign.
- A2, changes are store writes. A code change is modelled as a write to the locations the computation reads, such as a file’s content. The changed set must contain every location that actually changed; this is the hypothesis .
- A3, determinism. A case is a function of the store. A flaky or nondeterministic case falls outside the model, unless its source of variation is itself a recorded location, such as a seed.
- A4, footprints from the cached store. Footprints are recorded on the store the cache holds, the previous store. Theorem 2″ shows this stays consistent over any history.
- A5, tier hypotheses. Faithful and Refines are hypotheses about the tiers and are not proved. Refines also asks every higher tier to cover the facts that a lower tier covers and passes.
- A6, what cost counts. The cost theorems count case executions, each with weight 1. The time of each case and the work of computing intersections are not modelled, so “seconds” depends on the selected cases being cheap.
- Granularity. Selection is only as precise as the locations. If a location is a whole file, a change to a comment in it re-runs every case that read the file. That is safe but costs extra runs.
- Minimality is not proved. A case whose footprint hits the change may still keep its verdict. The one-read example shows only that hit cases cannot be skipped in general.
- Types. Locations and values are natural numbers. Generalising them to any type with decidable equality would be routine but was not done.
- No cryptography. Nothing here involves a cryptographic property or a computational model.
Prior work
The read-set theorem is the soundness property behind verifying traces in “Build systems à la carte” (ICFP 2018), and the representation of a computation as a tree of reads is close to the monadic tasks of that paper. A generic form of such trees, with arbitrary requests in place of reads, appears in “Interaction trees: representing recursive and impure programs in Coq” (POPL 2020). Recording the inputs a computation actually requests, rather than declaring them in advance, is the approach of “Shake before building: replacing make with Haskell” (ICFP 2012). Self-adjusting computation, from “Adaptive functional programming” (POPL 2002) and “Adapton: composable, demand-driven incremental computation” (PLDI 2014), records reads to re-execute only what a change reaches.
Safe selection of regression tests from the parts of a program that each case exercised is the subject of “A safe, efficient regression test selection technique” (ACM Transactions on Software Engineering and Methodology, 1997). Theorem 2 is the same safety property stated for a store model with read sets recorded at run time.
Refinement between an abstract model and a concrete system is the subject of “Proof of correctness of data representations” (Acta Informatica, 1972) and “Program development by stepwise refinement” (Communications of the ACM, 1971). The tier hypothesis Refines is a one-step refinement claim between neighbouring tiers, restricted to the facts each tier checks.
What this article adds is the combination of the three, a statement of the goal it serves, and a single Lean file that proves the combination meets that goal under assumptions that are stated explicitly.