runtimeverification / runtimeverification/kontrol

Usability improvements to `foundry-merge-node`

Open
#23 7 comments 0 reactions 0 assignees View on GitHub

Nobody has claimed this yet.

enhancement
Dominant language
Python
Stars
122
Forks
16
PR merge metrics
No merged PRs in 30d

Description

With this PR, we can now use the foundry-merge-nodes command to merge two nodes in different branches into a single node that subsumes both. This lets us merge branches back after a split, for example after an if statement or a loop, continuing the execution as a single branch, which has the potential of greatly improving the scalability of the tool in code with many loops or if statements.

However, this command has a few limitations in terms of usability:

  1. The corresponding nodes in each branch (same PC) need to be present in the KCFG in order to be merged. This is not necessarily easy to ensure.
  2. Because it requires manual intervention, the result of the verification becomes harder to reproduce.

We should think about ways to address these limitations to make this functionality easier to use. For example, suppose there was a cheatcode kevm.mergePoint() that denotes the point where we want to merge branches:

if (condition) {
    // if branch
} else {
    // else branch
}

kevm.mergePoint();

If we could implement this cheatcode such that the point where it's called is always added as a node to the KCFG, this would take care of (1). Going one step further, if we had an option to automatically merge such nodes if they have the same PC, this would take care of (2) (but this heuristic might not always work, for example if the merge point itself is inside a loop or a function that is called multiple times). But I don't know if something like that could actually be implemented, because it is a cheatcode that would not be handled solely from inside kevm, instead needing to somehow communicate with pyk.

I'd like to hear people's thoughts on this and brainstorm possible options.

Contributor guide

Open the 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.

Research direction

Start by reading PR 1934 and the existing foundry-merge-nodes command, then trace how KCFG nodes are created and how kevm.mergePoint() would need to communicate with pyK. A completed effort would define and implement a reproducible merge-point workflow, including its behavior for same-PC nodes and loop or function-call edge cases.

Written by the indexing model from the issue text.

Assessment

Tech stack
python
Domain
devtools
Issue type
Feature
Difficulty
5/5
Estimated time
Over a week
Activity status
Stale
Clarity
Needs clarification
Newbie friendliness
25/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.