private function getMoves()

in src/Diff.php [129:244]

• 42 lines of code
• 11 McCabe index (conditional complexity)

  private function getMoves(): vec<this::TMove> {
    /* If you're comparing this to the paper:
     * `$max_x` is N
     * `$max_y` is M
     * `$max_cost` is MAX
     * `$cost` is D
     * `$diagonal` is k
     * `$best_points` is V
     * `$best_points_at_cost` is Vd
     *
     * 'cost' isn't quite the same as 'depth': taking a diagonal path through
     * the space is an increase in depth, but not cost.
     */

    $a = $this->a;
    $b = $this->b;
    $max_x = C\count($a);
    $max_y = C\count($b);
    // Absolute worst case: delete everything from a + insert everything from b
    $max_cost = $max_x + $max_y;

    /* Find the shortest path.
     *
     * $x: offset into a: deletions
     * $y: offset into b: insertions
     * $diagonal: an identifier representing the line where $y = $x - $diagonal
     *
     * From the paper:
     * 1. For any path of cost $cost: -$cost <= $diagonal <= $cost
     * 2. The furthest-reaching 0-cost path ends at (x,x), where x =
     *    min(x) where $a[x] !== $b[x] or $x >= $max_x or $x >= $max_y
     * 3. The furthest-reaching ($cost)-cost path is composed of either:
     *    1. 1. a furthest-reaching ($cost-1)-path on diagonal ($diagonal - 1)
     *       2. a horizontal edge (deletion)
     *       3. any number (including 0) of diagonal edges (keeps)
     *    2. 1. a furthest-reaching ($cost-1)-path on diagonal ($diagonal + 1)
     *       2. a vertical edge (insertion)
     *       3. any number (including 0) of diagonal edges (keeps)
     *
     * So, for each cost, find the furthest-reaching point on each diagonal.
     * Stop when we leave the search space, or reach the endpoint.
     */

    // A map from $diagonal to $x. This is effectively a map from $diagonal to
    // points, as $y = $x - $diagonal.
    //
    // To handle $cost = 0, we take advantage of the fact that:
    // - we will only be looking at $diagonal === 0
    // - the implementation takes the ($diagonal + 1) path if $cost ===
    //   $diagonal
    // So, we set the best-$x for ($diagonal + 1) to 0, as that gets us
    // $y = $x + $diagonal = 0 + 0 = 0, so ($x = 0, $y = 0)
    $best_points = dict[1 => 0];
    $best_points_at_cost = vec[];

    for ($cost = 0; $cost <= $max_cost; $cost++) {
      $best_points_at_cost[] = $best_points;
      // Add 2 each time: any point with cost 0 is on diagonal 0; any point
      // with cost 1 is either on diagonal 1 or -1, any point with cost 2
      // is on diagonal -2, 0, or 2. This can be generalized to 3.x.1 above:
      // - Any even cost point is on an even diagonal
      // - Any odd cost point is on an odd diagonal
      // ... so if we have an even cost, skip the odd diagonals, and if we have
      // an odd cost, skip the even diagonals
      for ($diagonal = -$cost; $diagonal <= $cost; $diagonal += 2) { // Use 1.
        // Use 3: The furthest-reaching path on this diagonal is a continuation
        // of a ($cost-1) path on either ($diagonal-1) or ($diagonal+1).
        //
        // Decide which option we're taking for this diagonal
        if (
          // if ===, can't be -1 as $diagonal >= -$cost
          $diagonal === -$cost ||
          (
            // if ===, must be -1 as $diagonal <= $cost
            $diagonal !== $cost
            // Okay, we can choose.
            // prefer to keep the ($cost-1) path with higher $x - i.e. prefer to
            // delete. Not needed for correctness or efficiency, but:
            //     -foo
            //     +foof
            // is generally expected, and considered more readable than:
            //     +foof
            //     -foo
            &&
            $best_points[$diagonal - 1] < $best_points[$diagonal + 1]
          )
        ) {
          // keep x, increase $y (add a insertion)
          $x = $best_points[$diagonal + 1];
        } else {
          // increase x, keep y (add a deletion)
          $x = $best_points[$diagonal - 1] + 1;
        }
        $y = $x - $diagonal;

        // Use 2: Can we move along the diagonal (keep/unchanged elem)?
        while (
          $x < $max_x &&
          $y < $max_y &&
          $this->areSame($a[$x]['content'], $b[$y]['content'])
        ) {
          $x++;
          $y++;
        }

        $best_points[$diagonal] = $x;

        if ($x >= $max_x && $y >= $max_y) {
          return $this->backtrackPath($best_points_at_cost);
        }
      }
    }
    invariant_violation(
      'Shortest path is greater than the maximum possible length',
    );
  }