public class OrienteeringSelection extends InputSequenceSelector
Biases input selection towards sequences that have lower execution cost. Execution cost is measured by the number of method calls in a sequence and the time it takes to execute.
Our implementation of Orienteering differs from that described in the GRT paper in that we do not measure the time of every execution of a sequence. Instead, we assume that a sequence's execution time is equal to the execution time of its first run. We believe this assumption is reasonable since a sequence does not take any inputs (it is self-contained), so its execution time probably does not differ greatly between separate runs.
The GRT paper also does not describe how to handle input sequences that have an execution time
of zero, such as one that only includes the assignment of a primitive type byte byte0 =
(byte)1;. We assign these input sequences an execution time of 1 nanosecond to prevent division
by zero when computing weights.
The GRT paper also does not describe how to handle input sequences that have not yet been selected. We start ecah input sequences with a selection count of 1 to prevent division by zero when computing weights.
| Modifier and Type | Class and Description |
|---|---|
private static class |
OrienteeringSelection.SequenceDetails
Information used by Orienteering to compute a weight for a sequence.
|
| Modifier and Type | Field and Description |
|---|---|
private java.util.Map<Sequence,OrienteeringSelection.SequenceDetails> |
sequenceDetailsMap
Map from a sequence to its details used for computing its weight.
|
private java.util.Map<Sequence,java.lang.Double> |
weightMap
Map from a sequence to its weight.
|
| Constructor and Description |
|---|
OrienteeringSelection(java.util.Set<Sequence> seedSequences)
Initialize
OrienteeringSelection and assign a weight to each Sequence within
the given set of seed sequences. |
| Modifier and Type | Method and Description |
|---|---|
private double |
computeTotalWeightForCandidates(SimpleList<Sequence> candidates)
Compute the total weight of the list of candidate
Sequences. |
void |
createdExecutableSequence(ExecutableSequence eSeq)
A hook that is called after a new sequence has been created and executed.
|
private void |
createSequenceDetailsWithExecutionTime(Sequence sequence,
long executionTimeNanos)
Creates and stores a
OrienteeringSelection.SequenceDetails for the given Sequence with the
corresponding execution time. |
private static double |
methodSizeSquareRoot(Sequence sequence)
Returns the the square root of the number of method call statements within the given sequence.
|
Sequence |
selectInputSequence(SimpleList<Sequence> candidates)
Bias input selection towards lower-cost sequences.
|
private final java.util.Map<Sequence,OrienteeringSelection.SequenceDetails> sequenceDetailsMap
private final java.util.Map<Sequence,java.lang.Double> weightMap
weightMap.get(s) ==
sequenceDetailsMap.get(s).getWeight(). This is needed because Randomneess#randomMemberWeighted takes a Map<T, Double> as an argument.public OrienteeringSelection(java.util.Set<Sequence> seedSequences)
OrienteeringSelection and assign a weight to each Sequence within
the given set of seed sequences. This ensures that later, Orienteering will always have a
corresponding OrienteeringSelection.SequenceDetails and therefore a corresponding weight for every Sequence within a list of candidates for selection.seedSequences - set of seed sequencespublic Sequence selectInputSequence(SimpleList<Sequence> candidates)
selectInputSequence in class InputSequenceSelectorcandidates - sequences to choose fromprivate double computeTotalWeightForCandidates(SimpleList<Sequence> candidates)
Sequences.candidates - list of candidate sequencespublic void createdExecutableSequence(ExecutableSequence eSeq)
The default implementation does nothing. Subclasses may override it to add behavior.
This implementation creates and stores a OrienteeringSelection.SequenceDetails for the underlying Sequence in the given ExecutableSequence.
createdExecutableSequence in class InputSequenceSelectoreSeq - the recently executed sequence which is new and unique, and has just been executed.
It contains its overall execution time for the underlying Sequence.private void createSequenceDetailsWithExecutionTime(Sequence sequence, long executionTimeNanos)
OrienteeringSelection.SequenceDetails for the given Sequence with the
corresponding execution time.sequence - the sequence to addexecutionTimeNanos - the execution time of the sequence, in nanosecondsprivate static double methodSizeSquareRoot(Sequence sequence)
To prevent division by zero, we use 1 for a sequence with no method calls.
sequence - a sequence