Class Sequence.RelativeNegativeIndex

Used internally (i.e. in package randoop.sequence) to represent inputs to a statement.

IMPLEMENTATION NOTE: Recall that a sequence is a sequence of statements where the inputs to a statement are values created by earlier statements. Instead of using a Variable to represent such inputs, we use a RelativeNegativeIndex, which is just a wrapper for an integer. The integer represents a negative offset from the statement index in which this RelativeNegativeIndex lives, and the offset points to the statement that created the values that is used as an input. In other words, a RelativeNegativeIndex says "I represent the value created by the N-th statement above me".

For example, the sequence

x = new Foo(); Bar b = x.m();

is internally represented as follows:

first element: Foo() applied to inputs [] second element: m() applied to inputs [-1]

Here is a brief history of why we use this particular representation.

The very first way we represented inputs to a statement was using a list of StatementWithInput objects, i.e. an input was just a reference to a previous statement that created the input value. For example, a sequence might be represented as follows:

StatementWithInputs@123: Foo() applied to inputs [] StatementWithInputs@124: m() applied to inputs [StatementWithInputs@123]

We discovered that a big slowdown in the input generator was that we were consuming lots of memory when creating sequences: for example, in memory, when extending the sequence x = new Foo(); Bar b = x.m(); we cloned each statement, created a new list, added the cloned statements, and finally appended the new statement to the new list.

Instead of cloning, we might imagine just using the original statements in the new sequence. This does not work. For example, let's say that we implement this scheme, so that everywhere we need "new Foo()" we use the same statement (more precisely, the same StatementWithInputs). Then, we cannot express Foo f1 = new Foo(); Foo f2 = new Foo(); f1.equals(f2); because its internal representation must be

StatementWithInputs@123: Foo() applied to inputs [] StatementWithInputs@123: Foo() applied to inputs [] StatementWithInputs@125: Object.equals(Object) applied to inputs [StatementWithInputs@123, StatementWithInputs@123]

It's clear that if we want to reuse statements, we cannot directly use the statements as inputs.

We can instead use indices: 0 represents the value created by the first statement, 1 the second, etc. Now we can express the above sequence:

Foo() applied to inputs [] Foo() applied to inputs [] Foo() applied to inputs [0, 1]

This scheme makes it relatively expensive to concatenate sequences (some generators do lots of concatenation, so concatenation is the hotspot). Because indexing is absolute, some statements will need to have their input indices updated. For example, let's say we wanted to concatenate two copies of the last sequence above. We cannot just concatenate the statements, because then we have

Foo() applied to inputs [] Foo() applied to inputs [] Foo() applied to inputs [0, 1] Foo() applied to inputs [] Foo() applied to inputs [] Foo() applied to inputs [0, 1]

While we really want

Foo() applied to inputs [] Foo() applied to inputs [] Foo() applied to inputs [0, 1] Foo() applied to inputs [] Foo() applied to inputs [] Foo() applied to inputs [3, 4]

This means that we need to (1) adjust indices, which takes time, and (2) create new statements that represent the adjusted indices, which breaks the "reuse statements" idea.

Relative indices are the current implementation. Instead of representing inputs as indices that start from the beginning of the sequence, a statement's indices are represented by a relative, negative offsets:

Foo() applied to inputs [] Foo() applied to inputs [] Foo() applied to inputs [-2, -1] Foo() applied to inputs [] Foo() applied to inputs [] Foo() applied to inputs [-2, -1]

Now concatenation is easier: to concatenate two sequences, concatenate their statements. Also, we do not need to create any new statements.