viperproject / viperproject/silver

Termination Plugin: undefined error locations prevent caching

Open
#451 0 comments 0 reactions 0 assignees View on GitHub

Nobody has claimed this yet.

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

Description

The termination plugin implicitly creates methods that perform termination checks for functions, e.g., in the following scenario:

import <decreases/int.vpr>
function bar(x: Int): Bool
    decreases x
{
    bar(x)
}

Since these auxiliary method's do not correspond to any source code, the positions for them (and the verification errors that might occur inside) are set to NoPosition. This prevents us from being able to soundly cache anything in the current file. The reason is that caching must associate each error with one method, and this happens based on the position of the error. It would be unsound to cache any method that verified successfully if some errors are potentially not cacheable. Therefore, the only sound solution right now seems to be to discard all verification results if at least one of them is lacking position info.

@marcoeilers and I are proposing a lightweight solution: we can add the following field to class AbstractError:

val scope: Option[Node] = None

This would give the plugin the opportunity to associate an error with an internal method and would enable caching. In future, Silicon and Carbon could also be adapted to set the scope of errors that they generate, avoiding the need to recompute this relation in the caching mechanism, which is fragile.

Conceptually, I think that such a field would make sense, as it is often important to see the associativity of errors to AST nodes even, e.g., in a scenario where the verifiers are invoked from the command line.

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 with AbstractError in src/main/scala/viper/silver/verifier/VerificationResult.scala and trace how the termination plugin creates auxiliary methods and how caching associates errors with methods. Done means verification errors can carry an optional Node scope, allowing termination-plugin errors without source positions to be associated with an internal method and cached soundly.

Written by the indexing model from the issue text.

Assessment

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

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.