Basics

Basic Lifting Strategy

Every value in the computation is replaced by variational values (type V[T] instead of T). All computations are performed over all alternative values of a variational value using vmap and vflatMap operations. Every computation has a context, that may be restricted at control-flow decisions.

Instead of lifting the interpreter, we will attempt to modify the bytecode to achieve the same effect.

Not all code may be lifted to variational bytecode, but we will attempt to lift as much as possible, including code of the standard library. We lift code by using a special classloader that transforms the code while loading. Nonetheless, we will have to deal with interacting with nonvariational code, at the minimum when interacting with the environment.

Basic lifting

Every value of a local variable is transformed to use type edu.cmu.cs.varex.V. Primitive types are boxed on creation. All instructions that work on basic values, such as IADD are lifted to function calls that work on (boxed) variational values. Method invocations are wrapped into vflatMap calls.

Every method receives an extra parameter (the last one) for the current's execution context, of type de.fosd.typechef.featureexpr.FeatureExpr.

Lifting method calls

When lifting method calls in existing bytecode, there are three possible cases:

• The target method has been lifted, such that we can simply pass variational parameters and context. (It may be worth considering whether the this variable should be variational or whether we should map the call over all values of the receiver.)
• The target method is not lifted, but it's side-effect free. We may need some annotation mechanism or external database to identify such methods. In this case, we can explode all possible parameter values and merely call the method multiple times. The explosion should be delegated to a library function, which just receives a lambda object with the original function.
• For methods that we cannot lift (e.g., in java.lang.*), we can provide model classes and rewrite the call to call a separate variational implementation. This might be worth for frequently used IO functions such as println and for performance reasons as in StringBuffer. As lifting happens at compile-time, there is no runtime reflection necessary.
• In calls to unknown unlifted methods or unlifted methods with side effects (i.e., all other cases), we hope that each variational parameter has only a single value. We extract that single value and call the method once, terminating the execution with an exception if there are actually multiple values.

Hint: For lifting method calls, Java 8's closures may come in handy. Here is an example of how to lift this with java/lang/invoke/LambdaMetafactory in branch feature_invokedynamic. This avoids creating many additional classes.

Control-flow lifting

Lifting control-flow is more challenging, since jumps within the method may have multiple targets. Instead, every block within a method has an own execution context that is updated during execution. Details are described separately. Exception handling requires additional attention, sketched here.

Technical challenges

• Interacting with the environment, as usual.
• Lifting of long and double values needs to be done carefully, because it affects the stack size.
• Is concurrency an issue? We'll most likely need model classes for the basic abstractions there. I fear we will be able to create deadlocks that only occur due to multiple configurations, when config A waits for a lock that config !A holds. Since we only execute a single method at once, this might be hard to avoid.