bug: a oneof branch that writes nothing after an earlier write in the same action is never explored (always assertion passes unsoundly)

Open
#441 1 comment 0 reactions 0 assignees View on GitHub

Maintainers usually reply within 1 day

Nobody has claimed this yet.

Assessment

Difficulty
4/5
Estimated time
3-5 days
Newbie friendliness
55/100
Issue type
Bug
Clarity
Clearly specified
Activity status
Active
Tech stack
go

Research direction

Start by running the supplied lost-branch.fizz reproduction and compare its explored states with the version that moves oneof before the write. Trace how the model checker represents fork nodes and completed action states; the report points to issue #387 as related context. Done means every oneof branch's completed state is explored and the NeverBad assertion fails for this reproduction.

Written by the indexing model from the issue text.

Description

fizzbee 0.5.4, macOS arm64 (Homebrew). Also with --experimental_no_graph.

In an action that has already assigned a state variable, a later oneof branch that assigns nothing more is lost: its end state is never visited as a completed state, so its successors are never explored. An always assertion that a reachable state violates then passes.

Repro (lost-branch.fizz)

---
deadlock_detection: false
---

action Init:
    done = False
    flag = False
    bad = False

atomic action Go:
    require not done
    done = True
    c = oneof [False, True]
    if c:
        flag = True

atomic action Next:
    if done and not flag:
        bad = True

always assertion NeverBad:
    return not bad
$ fizz lost-branch.fizz
Valid Nodes: 3 Unique states: 2
PASSED: Model checker completed successfully

{done: True, flag: False} is reachable (Go with c = False), and Next then sets bad = True, so NeverBad should fail. Only 2 unique states are explored: Init and {done: True, flag: True}.

Moving the oneof before the write makes it fail as expected

atomic action Go:
    require not done
    c = oneof [False, True]
    done = True
    if c:
        flag = True
$ fizz lost-branch-oneof-first.fizz
FAILED: Model checker failed. Invariant:  NeverBad

What makes the difference (exists-assertion probes, same shape)

action body after done = True c = False end state reached?
c = oneof [False, True]; if c: flag = True no
same with oneof ["no", "yes"] / if c == "yes" no
same with the list order swapped no
...; if c: flag = True then seen = 1 (a write after the oneof) yes
...; if c: flag = True else: flag = False (the branch re-assigns, same value) yes
oneof drawn before done = True yes
two oneofs, or a oneof inside an if on the first one's value, both after the write but with every branch writing yes

It looks like the branch whose end state equals the state at the oneof fork node is merged into that intermediate node, which is not treated as the end of the action. #387 reports the intermediate fork node being seen by transition assertions; this may be the same root cause, with the opposite effect: here a completed state is missed rather than an intermediate one being checked.

Expected

Every branch of a oneof ends the action in its own completed state, explored and checked like any other, whether or not it writes anything after the fork.

Workaround

Draw every oneof before the action writes any state variable, or make every branch assign something.

Dominant language
Go
Stars
361
Forks
24
Avg merge
1d 3h
Merged PRs (30d)
62

Getting set up

  • Ships a Dockerfile or Docker Compose file
  • No pull request template
  • No contributing guide

First steps

  1. Read the whole issue, then the project's contributing guide.
  2. Comment on the issue to say you are picking it up — it saves two people doing the same work.
  3. Fork the repository and make your change on a branch.
  4. Open a pull request that references the issue number.

More from fizzbee-io/fizzbee

All issues in fizzbee-io/fizzbee

Similar issues

More Go issues

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.