Jove Constrained Random Solver

Copyright © 2005 Newisys, Inc. Licensed under the Open Software License version 2.0.

Product and company names mentioned herein may be trademarks of their respective owners.

Last updated 10/19/05

Introduction

Jove includes a BDD-based constrained random solver. The solver allows you to create directed random stimulus quickly and easily using the annotation (metadata) facility introduced in Java 5.0. It supports randomizing all Java primitive data types (boolean, int, etc) as well as their Object equivalents (Boolean, Integer, etc). Further, it supports Java 5.0 enumerations and the Jove Bit and BitVector types. Finally, it supports randomizing arbitrary types with the help of a type-specific, user-provided implementation of RandomMapper.

The solver randomizes object instances. When the user requests an instance be randomized, each member with the proper annotation is randomized according to the enabled constraint(s) associated with the instance. The randomized values are then stored to the instance via reflection. The random values stored to the members are uniformly distributed across all valid solutions.

Except where otherwise noted, the classes comprising the random solver are in com.newisys.randsolver.

Jove Random Solver Annotations

Annotations are used to indicate when and how to randomize variables. To describe a class as being randomizable, it should be annotated with the Randomizable annotation. The Randomizable annotation takes as an optional argument an array of Constraint annotations. A Constraint annotation consists of a String describing the constraint and an optional name. The syntax for constraints is described later in this document. If no Constraint argument is given, all members will be randomized across their natural range (e.g. -128 to 127 for a byte).

Class members may be annotated with either Rand or Randc. Annotating a member with Rand will cause that variable to be randomized, subject to the enabled constraints of the instance. Members annotated Randc (random cyclic) will randomly cycle through all valid values before any specific value repeats. For instance, if a 2-bit variable annotated with Randc were randomized 8 times, the following might result:

3, 2, 0, 1, 1, 2, 0, 3

In this example, the red values are those chosen in the first cycle and the blue values are those chosen in the second cycle. Note that no values repeat in a given cycle. Further, each cycle is randomized differently. For more information about cyclic variables, see Appendix B.

Users may need to execute arbitrary code either just prior to or just after randomization. This functionality can be achieved by having a Randomizable class implement the RandomHooks interface. Randomizable objects implementing the RandomHooks interface will have their preRandomize method called just prior to randomization and their postRandomize method called just after randomization. If multiple objects implementing RandomHooks are being randomized (e.g. randomization of an object with randomizable sub-objects), the order in which their preRandomize and postRandomize methods are called is undefined and should not be relied upon.

The following table summarizes the annotations used by the random solver:

All Jove random solver annotations are defined in the com.newisys.randsolver.annotation package.

A Simple Example

In the example below, we indicate that an instance of Foo can be randomized by annotating it with Randomizable. We've added a constraint (named "c1") that states i should be a value greater than 4 and should not be equal to j. Further, i should be less than or equal to 10.

We've indicated that the member i should be randomized by annotating it with Rand. This means whenever an instance of Foo is randomized, i will take on a value subject to "c1". There are no restrictions on the access permissions of i and j. They can be public, private, protected, or package-protected. However, members annotated with Rand or Randc cannot be marked as final.

In the main method, we create a new Foo, and print out its value of i. We then create a new PRNG (pseudo-random number generator) and randomize foo. Finally we print the value of i again and see that it has been randomized according to "c1".

package com.newisys.example;

import com.newisys.randsolver.Solver;
import com.newisys.randsolver.annotation.*;
import com.newisys.random.*;

@Randomizable(@Constraint(name="c1", expr="i > 4 && i != j; i <= 10;"))
class Foo
{
    @Rand
    int i = 2;

    final private int j = 5;

    public void print()
    {
        System.out.println("i = " + i);
    }

    public static void main(String[] args)
    {
        Foo foo = new Foo();
        foo.print();

        PRNG prng = PRNGFactoryFactory.getDefaultFactory().newInstance();
        Solver.randomize(foo, prng);

        foo.print();
    }
}

Enabling and Disabling Constraints

All constraints are enabled when an new Randomizable instance is created. It is sometimes useful to disable a certain constraint and re-enable it at a later time. If this functionality is needed, the name argument must be present in the Constraint annotation. The Solver class contains static methods for enabling and disabling a named constraint for a specific instance:

public static void enableConstraint(Randomizable r, String constraintName);
public static void disableConstraint(Randomizable r, String constraintName);

The Solver class also provides methods to enable and disable all constraints for a given instance:

public static void enableAllConstraints(Randomizable r);
public static void disableAllConstraints(Randomizable r);

Finally, the Solver class provides a way to query whether or not a constraint is enabled:

public static boolean isConstraintEnabled(Randomizable r, String constraintName);

It is an error if constraintName does not correspond to any named constraint in r.

Enabling and Disabling Member Randomization

All member variables annotated with either Rand or Randc are enabled when an new Randomizable is created. It is sometimes useful to disable randomization of a certain member and re-enable it at a later time. The Solver class contains static methods for enabling and disabling the randomization of a member for a specific instance:

public static void enableRand(Randomizable r, String varName);
public static void disableRand(Randomizable r, String varName);

The Solver class also provides methods to enable and disable randomization of all Rand/Randc members for a given instance:

public static void enableAllRand(Randomizable r);
public static void disableAllRand(Randomizable r);

Finally, the Solver class provides a way to query whether or not the randomization of a member is enabled:

public static boolean isConstraintEnabled(Randomizable r, String varName);

It is an error if varName does not correspond to any member in r or if the member is not annotated with either Rand or Randc.

Constraining Variables that are Randomizable

Randomizable classes often contain member variables that are themselves Randomizable. If these members are annotated with Rand (Randc is illegal in this case), they will be randomized when the object containing them is randomized, according to their own constraints. It is also possible to further constrain their members in the top-level object's constraints. An example of this is shown below:

@Randomizable(@Constraint(name="subobj_constraint", expr="i > 4 && i < 10;"))
class SubObject
{
    private int i = 2;
}

@Randomizable(@Constraint(name="top_constraint", expr="subObject.i != 6;"))
class TopObject
{
    @Rand
    SubObject subObject = new SubObject();
}

When an instance of type TopObject is randomized, its subObject member will also be randomized. The SubObject constraint will limit values of i to be between 5 and 9 (inclusive). The TopObject constraint further constraints subObject.i such that it cannot take on a value of 6. Finally, note that even though i is private, it is still legal to access it in "top_constraint" (though needing to access private variables generally indicates a bad design decision).

Randomization and Inheritance

The Randomizable annotation is inherited when a type is subclassed. That is, if class Bar is derived from class Foo, and Foo is Randomizable, Bar is also Randomizable. Further, Foo's constraints will be applied to the randomization of any Bar instance (unless they have been disabled for the instance). The constraint declaration of Bar can contain constraints with the same name as those defined in Foo. In this case, the constraint declared in Bar will override the constraint in Foo.

In the example below, when instances of Foo are randomized, i will be set to 4 and j to 6. However, when instances of Bar are randomized, both i and j will be set to 6 (since constraint "c1" was overridden in Bar's declaration). Finally, the results of randomizing an instance of Baz are identical to that of Bar, as the declaration of Baz inherits the constraints from Bar and does not override any of them.

@Randomizable({
    @Constraint(name="c1", expr="i == 4;"),
    @Constraint(name="c2", expr="j == 6;")
})
class Foo
{
    @Rand
    protected int i = 0;

    @Rand
    protected int j = 0;
}

@Randomizable(@Constraint(name="c1", expr="i == j;"))
class Bar extends Foo
{
}

class Baz extends Bar
{
}

Note that it is legal for constraints in subclasses to access private members of superclasses as though they were members of the subclass (though needing to access private variables generally indicates a bad design decision).

Creating Your Own Randomizable Type

While the solver supports randomizing a number of types by default, it is possible to add a type by implementing a RandomMapper or RandomMapperFactory. A RandomMapper maps integer values to objects and vice versa. It also defines any constraints required by the type. This might be useful for randomizing pre-Java 5.0 enumerations that use the typesafe enumeration pattern or any other situation where Java 5.0 enumerations cannot be used. A RandomMapper must have exactly 1 member marked as Rand or Randc.

A RandomMapperFactory is useful when randomizing across a type hierarchy. In this case, a different RandomMapper can be returned based on the type passed to the factory method.

RandomMapper and RandomMapperFactory objects should be registered statically at initialization via the methods in RandomMapperRegistry.

Examples of RandomMapper implementations are available in the com.newisys.randsolver.mappers package.

Arithmetic Results

All arithmetic operators supported by the solver take integer arguments and return integer results. "Integer" in this context refers to a mathematical integer, not a 32-bit quantity.

Constraint Syntax

A constraint consists of one or more expressions, each ending in a semicolon. There is an implicit "and" operation across multiple expressions (e.g. "i > 4; i < 10;" is equivalent to "i > 4 && i < 10;"). Constraints may include boolean literals, numeric literals, class member access, sub-object member access and constraint operators.

Boolean literals consist of true and false.

For numeric literals, Java and Verilog notation are allowed with the exception of Verilog signed bit vectors. Examples of numeric literals include: 19, 0x100000000L, 0x3F, 8'o377, and 4'b1011.

The following table describes the legal constraint operators, going from highest to lowest precedence:

The in and !in operators

The in operator states that the expression to the left of the operator must be contained in the set of ranges to the right of the operator. Ranges are declared as:

{ <range> [, <range>, ... ]}

where a <range> is decalred as:

<expr> .. <expr>

Thus, the following expression would state that (foo + 2) must be either 3, 4, 5, 6, 7 or in the range of bar to (baz - 1). Any of the variables foo, bar or baz may be declared as Rand or Randc.

(foo + 2) in {3..7, bar..(baz - 1)};

The !in operator is simply the negation of the in operator. That is, the expression to the left of the operator must not be in any of the ranges to the right of the operator.

Implication

For the conditions that cause implication operator, =>, to evaluate to true, refer to the following truth table:

In essense, the implication operator states that if the expression to the left of the operator is true, the expression to the right of the operator must be true. Else, the expression to the right of the operator may be true or false. Both the left and right hand sides of an implication expression may contain random variables. Implication is generally useful for writing conditional constraints.

Appendix A

A few tips on increasing performance of your randomization:

• Use a power of 2 in ranges where possible
• Avoid mixing multiplication/addition on the same variables when possible
• If not possible, keep the number of operations to a minimum
• Make state variables (i.e. variables that are not randomized) static and final when possible
• Create constraints only if there is a good reason to do so. That is, use com.newisys.random when possible.

Appendix B

The current implementation of the random solver associates a secondary, "cyclic constraint" with each cyclic random variable. Whenever that variable is randomized to say, 5, the expression "var != 5;" is added to this cyclic constraint, which is in turn added to the primary constraint each time a solution is generated. When the cyclic constraint contains no solutions, the period of the cyclic variable is complete, and it is reset to allow any value in that variables range.

In the current implementation of the random solver, it is possible, if a constraint includes more than one cyclic random variable, that one of those variables might be reset before it has exhausted its state space. Specifically, this can occur in the following situation:

• More than one cyclic random variable exists in a constraint
• The cyclic constraint of the first cyclic variable is added to the primary contraint
• Adding the cyclic constraint of the second cyclic variable to the primary constraint would cause no solutions to exist

In this case, the second cyclic variable is "reset", meaning its cyclic constraint is empty. However, it might have been the case that the second variable's state space had not been exhausted.

An example:

    @Randomizable(@Contraint(expr="v1 + v2 > 4;"))
    class CyclicExample implements
    {
    @Randc
    @Length(3)
    BitVector v1 = new BitVector(3);
 
    @Randc
    @Length(3)
    BitVector v2 = new BitVector(3);
    }

Here's the output of 10 randomizations. It can be seen that v2 cycles before its state space is exhausted.