Skip to content

Commit 42b881a

Browse files
Merge pull request #232 from bernardladenthin/fix/check-jar-path
tla: check.sh resolves a relative jar path; TODO: spurious wake-ups done
2 parents be3ff73 + 2ad7432 commit 42b881a

2 files changed

Lines changed: 16 additions & 87 deletions

File tree

‎TODO.md‎

Lines changed: 15 additions & 86 deletions
Original file line numberDiff line numberDiff line change
@@ -19,65 +19,28 @@ annotated, so everything below is genuinely still open.
1919
|---|---|---|---|---|
2020
| Prove that fairness per thread gives the fairness by role (`FairRole`, A13 follow-up; today argued and checked by TLC in bounded models) | 1–2 weeks | low, ~30 % | 2–3 weeks | tlapm cannot swap a quantifier over threads with a temporal operator (`\A q : P(q) ~> Q` to `(\E q : P(q)) ~> Q`), which is where it failed; another prover (e.g. Isabelle with a TLA embedding) would be the way out |
2121
| Liveness of the detailed model for any number of readers (A19) | 2–4 weeks | medium, ~50 % | 3–6 weeks | the pattern of `StreamBufferWaitForeverLiveProof.tla` carries over, but the detailed model is much larger (the FIFO as a sequence, more stages, the copy per entry), and the assumption of the row above stays |
22-
| A6: spurious wake-ups in the model (in progress, see below) | 1–2 weeks | ~75 % | 2–3 weeks | a small step (a parked thread may wake without a signal), but it is in four models and every proof above them (re-estimated 2026-11-13: the first estimate of 2–4 days missed that liveness needs the wake-ups bounded, a budget in `Pot` and in the forever measure) |
23-
| A6: several writers and closers in the detailed model | 1–2 weeks | ~70 % | 2–3 weeks | `StreamBuffer.tla` has one of each; `RefineWaitProof.tla` (2,656 obligations) must follow; the trace scenarios are easy afterwards |
22+
| A6: several writers and closers in the detailed model | 1–2 weeks | ~70 % | 2–3 weeks | `StreamBuffer.tla` has one of each; `RefineWaitProof.tla` (2,729 obligations) must follow; the trace scenarios are easy afterwards |
2423
| A6: trim in the model | 1–2 weeks | ~60 % | 2–4 weeks | the merge of the entries touches the FIFO invariant and the refinement; the geometric merge is hard to state compactly |
2524
| A8: `ReentrantLock` instead of `synchronized` | 3–5 days, if taken up | technically high, ~90 %; the gain unclear | 1–2 weeks | the measurements show a trade-off (faster for platform threads, slower for virtual threads); it needs a workload that decides which kind matters |
2625
| A9: functional proof of the instance methods | months | low, ~20–30 % | 3–6 months | OpenJML ESC returns "unknown" on instance methods, and the deque as a ghost sequence is large; extract a sequential core first |
2726
| Checker Framework Lock Checker | 1–2 days for a spike | ~40 % | ~1 week | blocked by inconsistent JDK stubs of `close()`; a way out via `-AskipDefs` or own stubs; A17 (the bytecode check) is an alternative that makes it mostly unnecessary |
2827
| `@VisibleForTesting` decision | ½ day | ~95 % | a few days | only the decision (an own marker annotation, or the convention does not apply here), then act |
2928
| Naming review | ~1 day | ~90 % | ~1 week | mechanical; renaming private methods is cheap, a public API rename is a breaking change for the CHANGELOG |
3029

31-
Best value for the risk: spurious wake-ups, the `@VisibleForTesting` decision and the naming
32-
review; then several writers in the detailed model, if that matters. The `FairRole` proof, A19
30+
Best value for the risk: the `@VisibleForTesting` decision and the naming review; then several
31+
writers in the detailed model, if that matters. The `FairRole` proof, A19
3332
and A9 are research with an open outcome. A17 is in the planned roadmap and covers most of what
3433
the Lock Checker would give.
3534

36-
- **Spurious wake-ups in the model (started 2026-11-13, branch `feat/spurious-wakeups`).**
37-
`Condition.await()` may return without a signal (JDK); the code tests again in its loop, but no
38-
model has the step, and A6 rejects a trace with one. Run with `/loop` and the prompt in "Run
39-
prompts" below.
40-
41-
Decisions (with reasons):
42-
- **A budget, not unbounded:** a ghost counter `spurious` starting at the constant `Spurious`
43-
(any natural number); a spurious wake-up of a parked thread uses one. Safety for every
44-
`Spurious` covers every run, since a finite prefix has finitely many; liveness assumes
45-
finitely many, the usual assumption (infinitely many with no progress is not a defect of the
46-
code).
47-
- **Not under fairness:** the step is not part of `ReaderStep`/`ThreadStep`, so the fairness
48-
per thread never forces it; forced wake-ups would hide a lost wake-up in the liveness checks
49-
(`StreamBufferWaitLive.tla`'s weak fairness of all of `Next` could, but its proof shows a
50-
protocol step enabled until all are done).
51-
- **Existing configurations get `Spurious = 0`:** their behaviour and state counts stay; new
52-
models check `Spurious = 2`.
53-
- **In `StreamBuffer.tla` and `StreamBufferWait.tla`** (the abstraction with the TLAPS
54-
refinement and the liveness proofs), not in `StreamBufferCounters.tla` and
55-
`StreamBufferRecords.tla`: `StreamBufferWait.tla` covers their slices, and their TLC
56-
refinement checks run with `Spurious = 0`, so they stay valid.
57-
58-
- [x] (61e4cec, f285661) Detailed model: `Spurious`, `spurious`, `SpuriousWake(r)` (parked to woken, one of the
59-
budget) in `Next`, not in `Fairness`; every existing `.cfg` with `Spurious = 0`; new models
60-
(2 and 3 readers, records, `waitForAtLeast`) with `Spurious = 2`; a negative control (the
61-
woken thread skips the test of its loop: must fail once a spurious wake-up is possible);
62-
`check.sh`. The control runs next to a lone `waitForAtLeast(2)` (`WaitAlone1`): next to a
63-
`read()` reader the mutant fails without spurious wake-ups too, so it would not separate.
64-
- [x] (61e4cec, f285661) A6: `TraceStreamBuffer.tla` lets a parked thread wake spuriously; `TraceGenerator` writes
65-
a budget; a hand-written trace with a wake-up without `signalAll` is accepted with a budget and
66-
rejected with `Spurious = 0`; README limits. The trace is written by `trace-controls.sh`
67-
(one more round of the wait loop right after a park); removing the signal lines of a recorded
68-
trace does not work, the model places the writer's signal silently before its exit line.
69-
- [x] (61e4cec, bae7484) `StreamBufferWait.tla`: the same step and budget; `inductive.sh` (Apalache, any budget);
70-
TLAPS: `StreamBufferWaitProof.tla` (`SafeInv`), `StreamBufferWaitLiveProof.tla` (the budget in
71-
`Pot`), `StreamBufferWaitEnabled.tla` if needed, the forever proof (the budget in `FIP`),
72-
`RefineWaitProof.tla` (map `spurious` to `spurious`). Every action keeps the budget, so the
73-
fairness and the witness actions need nothing new; `Pot` weighs it 10, the forever `FIP` 1.
74-
Run on Vultr (the local machine ran out of memory): proof.sh 8,036 obligations, inductive.sh
75-
61 OK, check.sh 45 models and the mutant.
76-
- [x] README (model, properties, limits), CHANGELOG, CLAUDE.md, CI times.
77-
- Known limits (review 2026-11-13, not blocking): `FairRole` is TLC-checked only without spurious
78-
wake-ups (`WaitForeverMeasure2`); the probe `SpuriousReached2` covers one configuration; the
79-
4-core CI time of `check.sh` is an estimate until the first scheduled run.
80-
- [ ] Review, one push, PR, CI green.
35+
- **Spurious wake-ups in the model: done (PR #231, 2026-11-13).** `Condition.await()` may return
36+
without a signal. `StreamBuffer.tla` and `StreamBufferWait.tla` have the step `SpuriousWake(r)`
37+
within a ghost budget (the constant `Spurious`, not under fairness), with TLC models and a mutant
38+
control in `check.sh`, the TLAPS proofs for any budget (safety, liveness, forever liveness,
39+
refinement), Apalache, and a control in `trace-controls.sh`; details in
40+
`src/test/tla/README.md`, "Spurious wake-ups". Known limits (review 2026-11-13): `FairRole` is
41+
TLC-checked only without spurious wake-ups (`WaitForeverMeasure2`); the probe
42+
`SpuriousReached2` covers one configuration; the 4-core CI time of `check.sh` is an estimate
43+
until the first scheduled run.
8144

8245
- **Verification roadmap 2026-11 — packages A6–A14.** Each package is closed on its own, ends in a
8346
machine-checked result and is listed with its acceptance criterion. The contract every package
@@ -105,9 +68,6 @@ annotated, so everything below is genuinely still open.
10568
one of each; the A13 abstractions have several, but no trace check against them), trim (not
10669
modeled; the scenarios set `maxBufferElements` above the number of writes), and
10770
`waitForAtLeast` with a timeout (`awaitNanos` is not rewritten, not in the model).
108-
- [ ] A spurious wake-up of `await()` is not in the model and would reject a trace (none
109-
occurred in 990 runs). If one shows up in CI: model it (a parked waiter may wake without a
110-
signal), not a retry.
11171
- [ ] The trace lines name a method and its n-th access (`waitForAtLeast.getAvail#0`): a
11272
change of the wait or read paths needs the mapping in `TraceStreamBuffer.tla` changed with
11373
it (`TraceRecorderTest` fails first).
@@ -300,9 +260,9 @@ annotated, so everything below is genuinely still open.
300260
the trusted base (JVM and JIT, javac, the JDK classes `ReentrantLock`/`Condition`/AQS,
301261
`Semaphore`, `ArrayDeque`, `CopyOnWriteArrayList`, the atomics), the caller contracts (a
302262
written array without `safeWrite`, the semaphore limits of F280, `release()` overrides, trim
303-
signals), what no model covers (timeouts, interrupts, spurious wake-ups, trim in the TLA+
304-
model). And a table: property → tool → scope (bounded or unbounded; abstraction, detailed
305-
model or code) → assumptions → CI job. Every scheduled formal run writes a manifest (commit SHA,
263+
signals), what no model covers (timeouts, interrupts, trim in the TLA+ model) and what the
264+
models assume (finitely many spurious wake-ups). And a table: property → tool → scope
265+
(bounded or unbounded; abstraction, detailed model or code) → assumptions → CI job. Every scheduled formal run writes a manifest (commit SHA,
306266
tool versions and SHA-256, obligations, states) as an artifact. Done when every verification
307267
claim in the READMEs points to a row of that table, and every row has a run with a SHA.
308268
- **A15 — Proofs as a release gate (1–2 days).** `formal-verification.yml` gets a `workflow_call`
@@ -432,37 +392,6 @@ Prompts for long `/loop` runs. The loop is started with a one-line reference to
432392
so the prompt can be changed in this file without restarting the loop; the next iteration reads
433393
the current text.
434394
435-
### Spurious wake-ups
436-
437-
Start: `/loop Work on the spurious wake-ups as described in TODO.md, section "Run prompts" / "Spurious wake-ups", re-read on every iteration.`
438-
439-
````text
440-
Add spurious wake-ups to the TLA+ models of streambuffer (TODO.md, "Spurious wake-ups in the
441-
model": the decisions and the checkbox plan) fully automatically and as independently as
442-
possible. It may take longer than one session; there is no deadline. Work locally (TLC 1.7.4 as
443-
pinned in formal-verification.yml, Apalache as in src/test/tla/README.md, tlapm ff40755 in WSL;
444-
Maven with JAVA_HOME=/c/Users/berna/AppData/Local/Programs/jdk-25.0.4.1+1).
445-
446-
Procedure:
447-
1. Every iteration: on the branch feat/spurious-wakeups in the real clone, do the next open step,
448-
test it, tick it with its commit, add steps found on the way, with the reason for every
449-
decision.
450-
2. No change to production code. Do not bend the models to make a property hold: a property that
451-
fails is a finding (document it with its counterexample). Negative controls are mandatory.
452-
3. Every proof module that changes runs through tlapm with all obligations proved; inductive.sh
453-
and check.sh pass; the A6 trace validation and its controls pass. Numbers in the READMEs;
454-
CHANGELOG.md, CLAUDE.md, TODO.md updated. CI: only the existing workflow files.
455-
4. At the end: review of the branch by an agent with the stop criterion (only regressions,
456-
moderate or high bugs of the branch, wrong statements in the docs block; the rest one line in
457-
TODO.md; at most one more round). Then one push, open the PR (do not merge, no dispatch runs),
458-
watch CI, work off CodeRabbit's still-valid findings; on a CI error of my own: cancel the run,
459-
commit the fix, push.
460-
5. Rules: no questions (ask only for something that is the owner's to decide). No force-push, no
461-
pkill -f, delete only with Remove-Item, no private data to external services. When the PR is
462-
green, remove the done steps from TODO.md (only the result stays) before the push, a summary in
463-
German, then end the loop.
464-
````
465-
466395
### Verification roadmap A15–A18
467396
468397
Start: `/loop Work on the verification roadmap A15-A18 as described in TODO.md, section "Run prompts" / "Verification roadmap A15–A18", re-read on every iteration.`

‎src/test/tla/check.sh‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -12,7 +12,7 @@
1212
#
1313
# Usage: src/test/tla/check.sh <path to tla2tools.jar> (run from anywhere; needs java on PATH)
1414
set -euo pipefail
15-
jar="$1"
15+
jar="$(cd "$(dirname "$1")" && pwd)/$(basename "$1")"
1616
cd "$(dirname "$0")"
1717
work="$(mktemp -d)"
1818
trap 'rm -rf "$work"' EXIT

0 commit comments

Comments
 (0)