-
Notifications
You must be signed in to change notification settings - Fork 3
Terminology
Based on the explanations in the original master's thesis, this page collects the definitions for terms which are of interest in the context of flowR.
For more information on different slicing variants, refer to Section 2.1.3 of the original master's thesis.
Overview of the classification used within the thesis
A slicing criterion describes the location of a single variable or several variables of interest to slice for. Weiser originally defined it as a combination of a line number and a set of variables of the program (Weiser, 1984). flowR allows for three different formats:
format | example | description |
---|---|---|
line@variable |
12@product |
the classical format but only for a single variable. The example 12@product slices for the first occurrence of a variable with the name product in line 12. |
line:column |
12:5 |
a single variable or point in the program that starts at the given point. |
$id |
$42 |
this criteria is probably best used internally and refers to the unique id assigned by flowR |
Furthermore, slicing criteria can be joined by the use of a ;
-semicolon. 10@sum;12@product
refers to the first occurrence of sum
in line 10 and the first occurrence of product
in line 12 as two variables to be used for slicing.
Based on a slicing criterion and a program, a program slice is a subset of the program that either
- might influence the values of the variables specified by the slicing criterion backward slice, or
- might be influenced by the values of the variables specified by the slicing criterion forward slice.
There are many ways to slice a program. In other words, a slice is not unique - the complete program is always valid. However, as this is rarely useful, we are interested in minimal slices, i.e., slices that are as small as possible.<1>
To exemplify the term, let's look at a concrete example with the following code:
z <- 3
if(x > 4) {
y <- x
} else {
y <- -x
}
x <- y
print(x + z)
Let's slice for the last definition of x
in line 9 (x <- y
).
-
the smallest backward slice is:
if(x > 4) { y <- x } else { y <- -x } x <- y
It does not contain
z <- 3
as it is not necessary to definex
in the last line, however it includes the if's condition, as it decides the active branch and hence the active definition fory
in the definition. Ifx <- y
itself is to be included in the slice depends on the program slicer. flowR includes it. -
the smallest forward slice is:
print(x + z)
It contains all statements affected by the definition of
x
. flowR does not support forward slicing in its current form.
Based on a slicing criterion and a program, a backward slice is a subset of the program that might influence the values of the variables of the slicing criterion. See the explanation of program slices for an example.
Based on a slicing criterion and a program, a forward slice is a subset of the program that might be influenced by the slicing criterion. See the explanation of program slices for an example.
In contrast to a dynamic slicer, the static slicer only relies on the source code of the input program, as well as other statically extractable information like the control-flow graph and the dataflow graph to calculate the program slice. flowR uses static information.
In contrast to a static slicer, the dynamic slicer retrieves the execution trace of a program for a given input and uses it to calculate the program slice.
flowR is currently not using dynamic information.
<1>: Finding statement minimal slices has been stated to be impossible by Weiser with a simple reduction to the halting problem (Weiser, 1984).