goblint / goblint/analyzer

Handling of CIL variable renaming for witness invariant generation and parsing

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

Nobody has claimed this yet.

sv-comp
Dominant language
OCaml
Stars
252
Forks
90
Avg merge
4d 1m
Merged PRs (30d)
19

Description

Problem pointed out here: https://github.com/goblint/analyzer/pull/745#discussion_r883607234.

Good point, I didn't think about it here, but I think there's not much to do about it either. On the witness generation side, there's InvariantCil.exp_replace_original_name that maps things to original names. But here for parsing we'd somehow need to know, which of the variables with the same original name was in scope at a particular location inside the function after they've been all pulled up and renamed.

As I mentioned in goblint/cil#97, the normal Cabs2cil uses tons of global variables to keep track of things and these block scopes and alpha renaming tables (and undos in alpha renaming tables) are among those. But all those structures are mutated, so we cannot go back to a particular location and have the exact state of those internal globals that normally keep track of this. One way would be to keep the CABS of all functions around and redo Cabs2cil for the function where the invariant belongs to, so it reconstructs that state, such that we can convert the invariant expression exactly as it would have been at a particular location and abort Cabs2cil, but that seems super ugly.

But here's a maybe radical idea: we make CIL not do those renames at all and just continue with a single fundec containing multiple local varinfos with same vname. Since we identify variables by vid, not vname, this should have no effect on the semantics, only results presentation (which is nicer with less renaming anyway). And somehow also eliminate the pulling up of all locals from all block scopes, such that the scopes are also later observable.

Anyway, tackling that whole issue is probably too much to do right here, but for the time being, a variable name in the expression would just find the first varinfo that has it unrenamed. All the others would have names with suffixes, which won't be used unless you directly also use that name in the invariant, but that would violate the semantics of it being insertable as an assertion.

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 the discussion linked from PR #745 and inspect InvariantCil.exp_replace_original_name and Cabs2cil, which the issue identifies as relevant. Determine how variable scope and alpha-renaming state can be recovered for invariant parsing and generation; the issue does not define a concrete completion test or settled design.

Written by the indexing model from the issue text.

Assessment

Tech stack
c, ocaml
Domain
compilers, devtools
Issue type
Refactor
Difficulty
5/5
Estimated time
Over a week
Activity status
Stale
Clarity
Needs clarification
Newbie friendliness
20/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.