Control flow graph-based incremental testing

[KOLANICH]

Project description

Some unit tests are long to run. So it may be beneficial to run unit tests only for the changed parts of code. How can we achive that?

0. Run statc code analysis. Build a CFG. Identify recursions and loops.
1. Compute a diff of CFGs of old and new versions
2. identify the functions influenced and not influenced by the diff. Identify pure functions.
3. find the changed tests. Add them to the schedule.
4. find the tests actually (from the recorded traces, if there is no traces for that functions - from tests CFG) calling the functions influenced by the diff. Add them to the schedule.
5. Run the scheduled tests. When running tests, trace and record their execution paths and memoize functions arguments and return values, if they are not in a loop or a recursion. If a pure function is not influenced by the diff, if memoized value is present, return it immediately without actual invocation, otherwise invoke and memoize.

Relevant Technology

Coverage-guided fuzzing

Complexity and required time

Complexity

• [x] Advanced - The project requires the user to have a good understanding of all components of the project to contribute

Required time (ETA)

• [x] Much work - The project will take more than a couple of weeks and serious planning is required

[remram44]

Why use static code analysis, rather than a coverage report? A lot of languages have code coverage tools, and they are usually integrated with unit test frameworks, so you could just use that.

[KOLANICH]

@remram44, because coverage reports are specific to version of the software under test and to generate it one has to run test. We need the stuff ahead of time, to know which tests to run in order to test everything not tested it is possible to test using available tests, but to minimize overlap to already tested.

For example I have a lib for wrapping hyperparams optimizers. We definitely need to test all of them, but some optimizers are damn slow, other ones not as slow, but are still slow. When I test on my machine, I know what I want to test. But I have set up a CI, and I want the CI to be as fast as possible - not to test any backends which have not been changed and which are already tested. So when I add a backend, only that backend is tested.

[remram44]

Yes but you only need to run all the tests once, then you have the info needed to not re-run all of them next time. You can then update the information for the changed tests and keep going.

[KOLANICH]

Yes but you only need to run all the tests once, then you have the info needed to not re-run all of them next time.

It is raw data. In order to extract the info about which tests should be run, static code analysis is required.

[remram44]

What do you mean? What's wrong with the approach I outlined, and what is "raw data"?

[KOLANICH]

and what is "raw data"?

count of executions of each statement of code

What's wrong with the approach I outlined

When we add a piece of code into a covered branch, that piece is not covered. In order to understand that that piece belongs to that branch, static code analysis is necessary.

But usually coverage data is not by branches, but by statements.

[remram44]

If you add code after a covered line, it is going to be covered. This can be determined from the dynamic coverage info just fine.

If you add a brand new function, you are going to have to change covered code to add a call to that function for it to be used. That change will be seen.

Code coverage is usually aware of branches (Python's coverage, GCC's -fprofile, ...)

[KOLANICH]

If you add code after a covered line, it is going to be covered. This can be determined from the dynamic coverage info just fine.

Not necessarily. For example you can add dead code, and it will be not covered. Or you can just to add a method and not call it in any of tests.

Code coverage is usually aware of branches

We need coverage ahead of time, before we have run any tests. coverage tools usually detect coverage of already executed instrumented code, not the one which is not executed.

[remram44]

Precisely. If you add dead code, no test needs to be re-run. This will be detected correctly.

I don't know what you mean by coverage of not executed code.

[KOLANICH]

I don't know what you mean by coverage of not executed code.

def a(): # we know this function is covered
    ....
    b() #inserted chunk, will be covered because folpows the covered code
    ....

def b(): # a newly added function
    ... # will be covered to
    if very_complex_condition(): # we cannot know if it is covered, but it is a pure function, so we can use the cached value to determine if the branch is covered
        .... # no returns and exceptions here
    .... # also covered

To understand what is covered and what is not, static code analysis and symbolic execution is needed.

[remram44]

You keep saying "static code analysis is needed" but fail to provide concrete arguments as to why dynamic code coverage tools are not enough. Repeating it does not make it so.