viperproject / viperproject/silver

Termination plugin incompleteness with let-expressions

Open
#797 0 comments 1 reaction 0 assignees View on GitHub

Nobody has claimed this yet.

termination plugin
Dominant language
Scala
Stars
100
Forks
53
Avg merge
8h 10m
Merged PRs (30d)
2

Description

For the following program, both backends report that len might not terminate:

field elem: Int
field nxt: Ref
predicate ll(r: Ref) {
    acc(r.elem) && acc(r.nxt) && (r.nxt != null ==> let rn == (r.nxt) in ll(rn))
}
function len(r: Ref): Int
    requires ll(r)
    decreases ll(r)
{
    unfolding ll(r) in (r.nxt == null ? 0 : 1 + len(r.nxt))
}

The program verifies if the let expression is removed and ll(rn) is replaced by ll(r.nxt).

Reported by @Aurel300, found by a PV student.

Contributor guide

No contributing guide indexed for this repository

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.

Research direction

Start by running the provided program through both backends and compare it with the version where the let-expression is removed and ll(rn) uses ll(r.nxt). Trace the termination plugin's handling of let-expressions and identify why the decrease cannot be established. Done means both backends verify len without reporting possible nontermination.

Written by the indexing model from the issue text.

Assessment

Tech stack
scala
Domain
compilers
Issue type
Bug
Difficulty
4/5
Estimated time
3-5 days
Activity status
Stale
Clarity
Mostly clear
Newbie friendliness
38/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.