examples/generalized-multisection.t
prove -v examples/generalized-multisection.t
This program holds tests for the accuracy and efficiency of an implementation of multiple bisection.
In this program we abstract away many of the considerations found in the rest of CPAN distribution Devel-Git-MultiBisect. These include:
The specific application domains: the Perl 5 core distribution and CPAN librairies.
git as a source control mechanism.
We make the following assumptions:
We have a given body of source code which changes step-by-step (e.g., commits) over time.
We can perform an action over the source code at each step which generates a single, defined, non-empty string as a result.
If, from one step to another, there is no relevant change in the source code and if we make no changes in the way we call the action (e.g., different command-line options, different testing data), then the action will generate the same result every time.
If the action has been producing string A and we then make source code or testing changes which generate string B, no further changes will ever generate A, B, etc., ever again.
A
B
We already know the total number of steps over which we can or will perform the action.
We have already performed the action at the first and last steps in the sequence, so we know the strings generated at those points.
multisect_list()
Purpose
Identify all steps in the sequence where performing the action generates a new result.
Arguments
($values, $indices_visited) = multisect_list( { action => $action, list_count => scalar(@{$list}), first_value => $list->[0], last_value => $list->[-1], } );
Reference to a hash with the following elements:
action
Reference to a subroutine.
list_count
The number of steps in the sequence.
first_value
String holding the result from performing the action on the first step in the sequence.
last_value
String holding the result from performing the action on the last step in the sequence.
Return Value
List of two references to arrays.
Array with one element for each step in the original sequence. If, for the purpose of identifying a transition from one action result to another, we had to perform the action at a given step, then the corresponding element in the array is defined. If, however, bisection meant we did not need to perform the action at a given step, then the corresponding element in the array is undef.
undef
Example (trimmed):
[ "09431b9e74d329ef9ae0940eb0d279fb", undef, undef, ... undef, undef, "09431b9e74d329ef9ae0940eb0d279fb", "01ec704681e4680f683eaaaa6f83f79c", "01ec704681e4680f683eaaaa6f83f79c", "01ec704681e4680f683eaaaa6f83f79c", "01ec704681e4680f683eaaaa6f83f79c", "b29d11b703576a350d91e1506674fd80", "b29d11b703576a350d91e1506674fd80", undef, undef, ... undef, "b29d11b703576a350d91e1506674fd80", "481032a28823c8409a610e058b34a047", "481032a28823c8409a610e058b34a047", "481032a28823c8409a610e058b34a047", undef, undef, ... undef, "481032a28823c8409a610e058b34a047", ],
Array holding the index numbers of the steps in the sequence in the order in which they were visited during bisection. By definition, the first two elements in this array will be 0 and the total number of steps in the sequence minus 1.
0
1
[ 0, 219, 109, 108, 54, 81, 80, 67, 66, 60, 59, 57, 56, 55, 137, 136, 96, 95, 75, 74, 65, 64, 58 ],
prepare_report()
Generate a lookup table in which we can quickly see the indexes in the sequence where the action result changed.
$rep = prepare_report($values);
Single array reference: the first array ref returned by multisect_list().
Reference to a hash whose elements are keyed on the indices of the transitional steps, i.e., the first and last steps and the "before" and "after" steps at every transitional point. The values are the corresponding strings returned by performing the action at each such step.
Example: If there were 220 steps in the sequence, the return value would look something like this:
{ "0" => "09431b9e74d329ef9ae0940eb0d279fb", "54" => "09431b9e74d329ef9ae0940eb0d279fb", "55" => "01ec704681e4680f683eaaaa6f83f79c", "58" => "01ec704681e4680f683eaaaa6f83f79c", "59" => "b29d11b703576a350d91e1506674fd80", "64" => "b29d11b703576a350d91e1506674fd80", "65" => "481032a28823c8409a610e058b34a047", "219" => "481032a28823c8409a610e058b34a047", }
This hashref can then be compared to a hashref with the indices and values we expected.
To install Devel::Git::MultiBisect, copy and paste the appropriate command in to your terminal.
cpanm
cpanm Devel::Git::MultiBisect
CPAN shell
perl -MCPAN -e shell install Devel::Git::MultiBisect
For more information on module installation, please visit the detailed CPAN module installation guide.