Upgrade to 0.12

[github/fretlink/terraform-provider-statuscake.git] / vendor / github.com / google / go-cmp / cmp / internal / diff / diff.go

// Copyright 2017, The Go Authors. All rights reserved.
// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE.md file.

// Package diff implements an algorithm for producing edit-scripts.
// The edit-script is a sequence of operations needed to transform one list
// of symbols into another (or vice-versa). The edits allowed are insertions,
// deletions, and modifications. The summation of all edits is called the
// Levenshtein distance as this problem is well-known in computer science.
//
// This package prioritizes performance over accuracy. That is, the run time
// is more important than obtaining a minimal Levenshtein distance.
package diff

// EditType represents a single operation within an edit-script.
type EditType uint8

const (
        // Identity indicates that a symbol pair is identical in both list X and Y.
        Identity EditType = iota
        // UniqueX indicates that a symbol only exists in X and not Y.
        UniqueX
        // UniqueY indicates that a symbol only exists in Y and not X.
        UniqueY
        // Modified indicates that a symbol pair is a modification of each other.
        Modified
)

// EditScript represents the series of differences between two lists.
type EditScript []EditType

// String returns a human-readable string representing the edit-script where
// Identity, UniqueX, UniqueY, and Modified are represented by the
// '.', 'X', 'Y', and 'M' characters, respectively.
func (es EditScript) String() string {
        b := make([]byte, len(es))
        for i, e := range es {
                switch e {
                case Identity:
                        b[i] = '.'
                case UniqueX:
                        b[i] = 'X'
                case UniqueY:
                        b[i] = 'Y'
                case Modified:
                        b[i] = 'M'
                default:
                        panic("invalid edit-type")
                }
        }
        return string(b)
}

// stats returns a histogram of the number of each type of edit operation.
func (es EditScript) stats() (s struct{ NI, NX, NY, NM int }) {
        for _, e := range es {
                switch e {
                case Identity:
                        s.NI++
                case UniqueX:
                        s.NX++
                case UniqueY:
                        s.NY++
                case Modified:
                        s.NM++
                default:
                        panic("invalid edit-type")
                }
        }
        return
}

// Dist is the Levenshtein distance and is guaranteed to be 0 if and only if
// lists X and Y are equal.
func (es EditScript) Dist() int { return len(es) - es.stats().NI }

// LenX is the length of the X list.
func (es EditScript) LenX() int { return len(es) - es.stats().NY }

// LenY is the length of the Y list.
func (es EditScript) LenY() int { return len(es) - es.stats().NX }

// EqualFunc reports whether the symbols at indexes ix and iy are equal.
// When called by Difference, the index is guaranteed to be within nx and ny.
type EqualFunc func(ix int, iy int) Result

// Result is the result of comparison.
// NSame is the number of sub-elements that are equal.
// NDiff is the number of sub-elements that are not equal.
type Result struct{ NSame, NDiff int }

// Equal indicates whether the symbols are equal. Two symbols are equal
// if and only if NDiff == 0. If Equal, then they are also Similar.
func (r Result) Equal() bool { return r.NDiff == 0 }

// Similar indicates whether two symbols are similar and may be represented
// by using the Modified type. As a special case, we consider binary comparisons
// (i.e., those that return Result{1, 0} or Result{0, 1}) to be similar.
//
// The exact ratio of NSame to NDiff to determine similarity may change.
func (r Result) Similar() bool {
        // Use NSame+1 to offset NSame so that binary comparisons are similar.
        return r.NSame+1 >= r.NDiff
}

// Difference reports whether two lists of lengths nx and ny are equal
// given the definition of equality provided as f.
//
// This function returns an edit-script, which is a sequence of operations
// needed to convert one list into the other. The following invariants for
// the edit-script are maintained:
//      • eq == (es.Dist()==0)
//      • nx == es.LenX()
//      • ny == es.LenY()
//
// This algorithm is not guaranteed to be an optimal solution (i.e., one that
// produces an edit-script with a minimal Levenshtein distance). This algorithm
// favors performance over optimality. The exact output is not guaranteed to
// be stable and may change over time.
func Difference(nx, ny int, f EqualFunc) (es EditScript) {
        // This algorithm is based on traversing what is known as an "edit-graph".
        // See Figure 1 from "An O(ND) Difference Algorithm and Its Variations"
        // by Eugene W. Myers. Since D can be as large as N itself, this is
        // effectively O(N^2). Unlike the algorithm from that paper, we are not
        // interested in the optimal path, but at least some "decent" path.
        //
        // For example, let X and Y be lists of symbols:
        //      X = [A B C A B B A]
        //      Y = [C B A B A C]
        //
        // The edit-graph can be drawn as the following:
        //         A B C A B B A
        //        ┌─────────────┐
        //      C │_|_|\|_|_|_|_│ 0
        //      B │_|\|_|_|\|\|_│ 1
        //      A │\|_|_|\|_|_|\│ 2
        //      B │_|\|_|_|\|\|_│ 3
        //      A │\|_|_|\|_|_|\│ 4
        //      C │ | |\| | | | │ 5
        //        └─────────────┘ 6
        //         0 1 2 3 4 5 6 7
        //
        // List X is written along the horizontal axis, while list Y is written
        // along the vertical axis. At any point on this grid, if the symbol in
        // list X matches the corresponding symbol in list Y, then a '\' is drawn.
        // The goal of any minimal edit-script algorithm is to find a path from the
        // top-left corner to the bottom-right corner, while traveling through the
        // fewest horizontal or vertical edges.
        // A horizontal edge is equivalent to inserting a symbol from list X.
        // A vertical edge is equivalent to inserting a symbol from list Y.
        // A diagonal edge is equivalent to a matching symbol between both X and Y.

        // Invariants:
        //      • 0 ≤ fwdPath.X ≤ (fwdFrontier.X, revFrontier.X) ≤ revPath.X ≤ nx
        //      • 0 ≤ fwdPath.Y ≤ (fwdFrontier.Y, revFrontier.Y) ≤ revPath.Y ≤ ny
        //
        // In general:
        //      • fwdFrontier.X < revFrontier.X
        //      • fwdFrontier.Y < revFrontier.Y
        // Unless, it is time for the algorithm to terminate.
        fwdPath := path{+1, point{0, 0}, make(EditScript, 0, (nx+ny)/2)}
        revPath := path{-1, point{nx, ny}, make(EditScript, 0)}
        fwdFrontier := fwdPath.point // Forward search frontier
        revFrontier := revPath.point // Reverse search frontier

        // Search budget bounds the cost of searching for better paths.
        // The longest sequence of non-matching symbols that can be tolerated is
        // approximately the square-root of the search budget.
        searchBudget := 4 * (nx + ny) // O(n)

        // The algorithm below is a greedy, meet-in-the-middle algorithm for
        // computing sub-optimal edit-scripts between two lists.
        //
        // The algorithm is approximately as follows:
        //      • Searching for differences switches back-and-forth between
        //      a search that starts at the beginning (the top-left corner), and
        //      a search that starts at the end (the bottom-right corner). The goal of
        //      the search is connect with the search from the opposite corner.
        //      • As we search, we build a path in a greedy manner, where the first
        //      match seen is added to the path (this is sub-optimal, but provides a
        //      decent result in practice). When matches are found, we try the next pair
        //      of symbols in the lists and follow all matches as far as possible.
        //      • When searching for matches, we search along a diagonal going through
        //      through the "frontier" point. If no matches are found, we advance the
        //      frontier towards the opposite corner.
        //      • This algorithm terminates when either the X coordinates or the
        //      Y coordinates of the forward and reverse frontier points ever intersect.
        //
        // This algorithm is correct even if searching only in the forward direction
        // or in the reverse direction. We do both because it is commonly observed
        // that two lists commonly differ because elements were added to the front
        // or end of the other list.
        //
        // Running the tests with the "debug" build tag prints a visualization of
        // the algorithm running in real-time. This is educational for understanding
        // how the algorithm works. See debug_enable.go.
        f = debug.Begin(nx, ny, f, &fwdPath.es, &revPath.es)
        for {
                // Forward search from the beginning.
                if fwdFrontier.X >= revFrontier.X || fwdFrontier.Y >= revFrontier.Y || searchBudget == 0 {
                        break
                }
                for stop1, stop2, i := false, false, 0; !(stop1 && stop2) && searchBudget > 0; i++ {
                        // Search in a diagonal pattern for a match.
                        z := zigzag(i)
                        p := point{fwdFrontier.X + z, fwdFrontier.Y - z}
                        switch {
                        case p.X >= revPath.X || p.Y < fwdPath.Y:
                                stop1 = true // Hit top-right corner
                        case p.Y >= revPath.Y || p.X < fwdPath.X:
                                stop2 = true // Hit bottom-left corner
                        case f(p.X, p.Y).Equal():
                                // Match found, so connect the path to this point.
                                fwdPath.connect(p, f)
                                fwdPath.append(Identity)
                                // Follow sequence of matches as far as possible.
                                for fwdPath.X < revPath.X && fwdPath.Y < revPath.Y {
                                        if !f(fwdPath.X, fwdPath.Y).Equal() {
                                                break
                                        }
                                        fwdPath.append(Identity)
                                }
                                fwdFrontier = fwdPath.point
                                stop1, stop2 = true, true
                        default:
                                searchBudget-- // Match not found
                        }
                        debug.Update()
                }
                // Advance the frontier towards reverse point.
                if revPath.X-fwdFrontier.X >= revPath.Y-fwdFrontier.Y {
                        fwdFrontier.X++
                } else {
                        fwdFrontier.Y++
                }

                // Reverse search from the end.
                if fwdFrontier.X >= revFrontier.X || fwdFrontier.Y >= revFrontier.Y || searchBudget == 0 {
                        break
                }
                for stop1, stop2, i := false, false, 0; !(stop1 && stop2) && searchBudget > 0; i++ {
                        // Search in a diagonal pattern for a match.
                        z := zigzag(i)
                        p := point{revFrontier.X - z, revFrontier.Y + z}
                        switch {
                        case fwdPath.X >= p.X || revPath.Y < p.Y:
                                stop1 = true // Hit bottom-left corner
                        case fwdPath.Y >= p.Y || revPath.X < p.X:
                                stop2 = true // Hit top-right corner
                        case f(p.X-1, p.Y-1).Equal():
                                // Match found, so connect the path to this point.
                                revPath.connect(p, f)
                                revPath.append(Identity)
                                // Follow sequence of matches as far as possible.
                                for fwdPath.X < revPath.X && fwdPath.Y < revPath.Y {
                                        if !f(revPath.X-1, revPath.Y-1).Equal() {
                                                break
                                        }
                                        revPath.append(Identity)
                                }
                                revFrontier = revPath.point
                                stop1, stop2 = true, true
                        default:
                                searchBudget-- // Match not found
                        }
                        debug.Update()
                }
                // Advance the frontier towards forward point.
                if revFrontier.X-fwdPath.X >= revFrontier.Y-fwdPath.Y {
                        revFrontier.X--
                } else {
                        revFrontier.Y--
                }
        }

        // Join the forward and reverse paths and then append the reverse path.
        fwdPath.connect(revPath.point, f)
        for i := len(revPath.es) - 1; i >= 0; i-- {
                t := revPath.es[i]
                revPath.es = revPath.es[:i]
                fwdPath.append(t)
        }
        debug.Finish()
        return fwdPath.es
}

type path struct {
        dir   int // +1 if forward, -1 if reverse
        point     // Leading point of the EditScript path
        es    EditScript
}

// connect appends any necessary Identity, Modified, UniqueX, or UniqueY types
// to the edit-script to connect p.point to dst.
func (p *path) connect(dst point, f EqualFunc) {
        if p.dir > 0 {
                // Connect in forward direction.
                for dst.X > p.X && dst.Y > p.Y {
                        switch r := f(p.X, p.Y); {
                        case r.Equal():
                                p.append(Identity)
                        case r.Similar():
                                p.append(Modified)
                        case dst.X-p.X >= dst.Y-p.Y:
                                p.append(UniqueX)
                        default:
                                p.append(UniqueY)
                        }
                }
                for dst.X > p.X {
                        p.append(UniqueX)
                }
                for dst.Y > p.Y {
                        p.append(UniqueY)
                }
        } else {
                // Connect in reverse direction.
                for p.X > dst.X && p.Y > dst.Y {
                        switch r := f(p.X-1, p.Y-1); {
                        case r.Equal():
                                p.append(Identity)
                        case r.Similar():
                                p.append(Modified)
                        case p.Y-dst.Y >= p.X-dst.X:
                                p.append(UniqueY)
                        default:
                                p.append(UniqueX)
                        }
                }
                for p.X > dst.X {
                        p.append(UniqueX)
                }
                for p.Y > dst.Y {
                        p.append(UniqueY)
                }
        }
}

func (p *path) append(t EditType) {
        p.es = append(p.es, t)
        switch t {
        case Identity, Modified:
                p.add(p.dir, p.dir)
        case UniqueX:
                p.add(p.dir, 0)
        case UniqueY:
                p.add(0, p.dir)
        }
        debug.Update()
}

type point struct{ X, Y int }

func (p *point) add(dx, dy int) { p.X += dx; p.Y += dy }

// zigzag maps a consecutive sequence of integers to a zig-zag sequence.
//      [0 1 2 3 4 5 ...] => [0 -1 +1 -2 +2 ...]
func zigzag(x int) int {
        if x&1 != 0 {
                x = ^x
        }
        return x >> 1
}