NAME

examples/generalized-multisection.t

SYNOPSIS

    prove -v examples/generalized-multisection.t

DESCRIPTION

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.

• 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.

FUNCTIONS

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.

  1. 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.

     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",
         ],

  2. 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, 219, 109, 108, 54, 81, 80, 67, 66, 60, 59, 57, 56, 55,
           137, 136, 96, 95, 75, 74, 65, 64, 58 ],

prepare_report()

• Purpose

  Generate a lookup table in which we can quickly see the indexes in the sequence where the action result changed.

• Arguments

      $rep = prepare_report($values);

  Single array reference: the first array ref returned by multisect_list().

• Return Value

  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.