17065179658

Committed 19 Aug 2025 09:17AM UTC coverage: 42.059% (-3.4%) from 45.498%

Build # 17065179658

Build Type

Pull #2945

github

Committed by

web-flow

Commit Message

Merge 453498b26 into 51135b07d

Pull Request Pull Request #2945: upgrade Go from 1.23/1.24 to 1.25

Run Details

5 of 9 new or added lines in 7 files covered. (55.56%)

531 existing lines in 13 files now uncovered.

6493 of 15438 relevant lines covered (42.06%)

15.22 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

0.0

/pkg/util/nicediff/diff.go

// Copyright 2013 Google Inc.  All rights reserved.
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
//     http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.

// Package diff implements a linewise diff algorithm.
package nicediff

import (
        "fmt"
        "strings"
)

// Chunk represents a piece of the diff.  A chunk will not have both added and
// deleted lines.  Equal lines are always after any added or deleted lines.
// A Chunk may or may not have any lines in it, especially for the first or last
// chunk in a computation.
type Chunk struct {
        Added   []string
        Deleted []string
        Equal   []string
}

func (c *Chunk) empty() bool {
        return len(c.Added) == 0 && len(c.Deleted) == 0 && len(c.Equal) == 0
}

// Diff returns a string containing a line-by-line unified diff of the linewise
// changes required to make A into B.  Each line is prefixed with '+', '-', or
// ' ' to indicate if it should be added, removed, or is correct respectively.
func Diff(A, B string, skipEqual bool) string {
        aLines := strings.Split(A, "\n")
        bLines := strings.Split(B, "\n")
        return Render(DiffChunks(aLines, bLines), skipEqual)
}

// Render renders the slice of chunks into a representation that prefixes
// the lines with '+', '-', or ' ' depending on whether the line was added,
// removed, or equal (respectively).
func Render(chunks []Chunk, skipEqual bool) string {
        buf := new(strings.Builder)
        for _, c := range chunks {
                for _, line := range c.Added {
                        fmt.Fprintf(buf, "+%s\n", line)
                }
                for _, line := range c.Deleted {
                        fmt.Fprintf(buf, "-%s\n", line)
                }
                if !skipEqual {
                        for _, line := range c.Equal {
                                fmt.Fprintf(buf, " %s\n", line)
                        }
                }
        }
        return strings.TrimRight(buf.String(), "\n")
}

// DiffChunks uses an O(D(N+M)) shortest-edit-script algorithm
// to compute the edits required from A to B and returns the
// edit chunks.
func DiffChunks(a, b []string) []Chunk {
        // algorithm: http://www.xmailserver.org/diff2.pdf

        // We'll need these quantities a lot.
        alen, blen := len(a), len(b) // M, N

        // At most, it will require len(a) deletions and len(b) additions
        // to transform a into b.
        maxPath := alen + blen // MAX
        if maxPath == 0 {
                // degenerate case: two empty lists are the same
                return nil
        }

        // Store the endpoint of the path for diagonals.
        // We store only the a index, because the b index on any diagonal
        // (which we know during the loop below) is aidx-diag.
        // endpoint[maxPath] represents the 0 diagonal.
        //
        // Stated differently:
        // endpoint[d] contains the aidx of a furthest reaching path in diagonal d
        endpoint := make([]int, 2*maxPath+1) // V

        saved := make([][]int, 0, 8) // Vs
        save := func() {
                dup := make([]int, len(endpoint))
                copy(dup, endpoint)
                saved = append(saved, dup)
        }

        var editDistance int // D
dLoop:
        for editDistance = 0; editDistance <= maxPath; editDistance++ {
                // The 0 diag(onal) represents equality of a and b.  Each diagonal to
                // the left is numbered one lower, to the right is one higher, from
                // -alen to +blen.  Negative diagonals favor differences from a,
                // positive diagonals favor differences from b.  The edit distance to a
                // diagonal d cannot be shorter than d itself.
                //
                // The iterations of this loop cover either odds or evens, but not both,
                // If odd indices are inputs, even indices are outputs and vice versa.
                for diag := -editDistance; diag <= editDistance; diag += 2 { // k
                        var aidx int // x
                        switch {
                        case diag == -editDistance:
                                // This is a new diagonal; copy from previous iter
                                aidx = endpoint[maxPath-editDistance+1] + 0
                        case diag == editDistance:
                                // This is a new diagonal; copy from previous iter
                                aidx = endpoint[maxPath+editDistance-1] + 1
                        case endpoint[maxPath+diag+1] > endpoint[maxPath+diag-1]:
                                // diagonal d+1 was farther along, so use that
                                aidx = endpoint[maxPath+diag+1] + 0
                        default:
                                // diagonal d-1 was farther (or the same), so use that
                                aidx = endpoint[maxPath+diag-1] + 1
                        }
                        // On diagonal d, we can compute bidx from aidx.
                        bidx := aidx - diag // y
                        // See how far we can go on this diagonal before we find a difference.
                        for aidx < alen && bidx < blen && a[aidx] == b[bidx] {
                                aidx++
                                bidx++
                        }
                        // Store the end of the current edit chain.
                        endpoint[maxPath+diag] = aidx
                        // If we've found the end of both inputs, we're done!
                        if aidx >= alen && bidx >= blen {
                                save() // save the final path
                                break dLoop
                        }
                }
                save() // save the current path
        }
        if editDistance == 0 {
                return nil
        }
        chunks := make([]Chunk, editDistance+1)

        x, y := alen, blen
        for d := editDistance; d > 0; d-- {
                endpoint := saved[d]
                diag := x - y
                insert := diag == -d || (diag != d && endpoint[maxPath+diag-1] < endpoint[maxPath+diag+1])

                x1 := endpoint[maxPath+diag]
                var x0, xM, kk int
                if insert {
                        kk = diag + 1
                        x0 = endpoint[maxPath+kk]
                        xM = x0
                } else {
                        kk = diag - 1
                        x0 = endpoint[maxPath+kk]
                        xM = x0 + 1
                }
                y0 := x0 - kk

                var c Chunk
                if insert {
                        c.Added = b[y0:][:1]
                } else {
                        c.Deleted = a[x0:][:1]
                }
                if xM < x1 {
                        c.Equal = a[xM:][:x1-xM]
                }

                x, y = x0, y0
                chunks[d] = c
        }
        if x > 0 {
                chunks[0].Equal = a[:x]
        }
        if chunks[0].empty() {
                chunks = chunks[1:]
        }
        if len(chunks) == 0 {
                return nil
        }
        return chunks
}

1	// Copyright 2013 Google Inc. All rights reserved.
2	//
3	// Licensed under the Apache License, Version 2.0 (the "License");
4	// you may not use this file except in compliance with the License.
5	// You may obtain a copy of the License at
6	//
7	// http://www.apache.org/licenses/LICENSE-2.0
8	//
9	// Unless required by applicable law or agreed to in writing, software
10	// distributed under the License is distributed on an "AS IS" BASIS,
11	// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12	// See the License for the specific language governing permissions and
13	// limitations under the License.
14
15	// Package diff implements a linewise diff algorithm.
16	package nicediff
17
18	import (
19	"fmt"
20	"strings"
21	)
22
23	// Chunk represents a piece of the diff. A chunk will not have both added and
24	// deleted lines. Equal lines are always after any added or deleted lines.
25	// A Chunk may or may not have any lines in it, especially for the first or last
26	// chunk in a computation.
27	type Chunk struct {
28	Added []string
29	Deleted []string
30	Equal []string
31	}
32
UNCOV 33	func (c *Chunk) empty() bool {	×
UNCOV 34	return len(c.Added) == 0 && len(c.Deleted) == 0 && len(c.Equal) == 0	×
UNCOV 35	}	×
36
37	// Diff returns a string containing a line-by-line unified diff of the linewise
38	// changes required to make A into B. Each line is prefixed with '+', '-', or
39	// ' ' to indicate if it should be added, removed, or is correct respectively.
UNCOV 40	func Diff(A, B string, skipEqual bool) string {	×
UNCOV 41	aLines := strings.Split(A, "\n")	×
UNCOV 42	bLines := strings.Split(B, "\n")	×
UNCOV 43	return Render(DiffChunks(aLines, bLines), skipEqual)	×
UNCOV 44	}	×
45
46	// Render renders the slice of chunks into a representation that prefixes
47	// the lines with '+', '-', or ' ' depending on whether the line was added,
48	// removed, or equal (respectively).
UNCOV 49	func Render(chunks []Chunk, skipEqual bool) string {	×
UNCOV 50	buf := new(strings.Builder)	×
UNCOV 51	for _, c := range chunks {	×
UNCOV 52	for _, line := range c.Added {	×
UNCOV 53	fmt.Fprintf(buf, "+%s\n", line)	×
UNCOV 54	}	×
UNCOV 55	for _, line := range c.Deleted {	×
UNCOV 56	fmt.Fprintf(buf, "-%s\n", line)	×
UNCOV 57	}	×
UNCOV 58	if !skipEqual {	×
59	for _, line := range c.Equal {	×
60	fmt.Fprintf(buf, " %s\n", line)	×
61	}	×
62	}
63	}
UNCOV 64	return strings.TrimRight(buf.String(), "\n")	×
65	}
66
67	// DiffChunks uses an O(D(N+M)) shortest-edit-script algorithm
68	// to compute the edits required from A to B and returns the
69	// edit chunks.
UNCOV 70	func DiffChunks(a, b []string) []Chunk {	×
UNCOV 71	// algorithm: http://www.xmailserver.org/diff2.pdf	×
UNCOV 72		×
UNCOV 73	// We'll need these quantities a lot.	×
UNCOV 74	alen, blen := len(a), len(b) // M, N	×
UNCOV 75		×
UNCOV 76	// At most, it will require len(a) deletions and len(b) additions	×
UNCOV 77	// to transform a into b.	×
UNCOV 78	maxPath := alen + blen // MAX	×
UNCOV 79	if maxPath == 0 {	×
80	// degenerate case: two empty lists are the same	×
81	return nil	×
82	}	×
83
84	// Store the endpoint of the path for diagonals.
85	// We store only the a index, because the b index on any diagonal
86	// (which we know during the loop below) is aidx-diag.
87	// endpoint[maxPath] represents the 0 diagonal.
88	//
89	// Stated differently:
90	// endpoint[d] contains the aidx of a furthest reaching path in diagonal d
UNCOV 91	endpoint := make([]int, 2*maxPath+1) // V	×
UNCOV 92		×
UNCOV 93	saved := make([][]int, 0, 8) // Vs	×
UNCOV 94	save := func() {	×
UNCOV 95	dup := make([]int, len(endpoint))	×
UNCOV 96	copy(dup, endpoint)	×
UNCOV 97	saved = append(saved, dup)	×
UNCOV 98	}	×
99
UNCOV 100	var editDistance int // D	×
UNCOV 101	dLoop:	×
UNCOV 102	for editDistance = 0; editDistance <= maxPath; editDistance++ {	×
UNCOV 103	// The 0 diag(onal) represents equality of a and b. Each diagonal to	×
UNCOV 104	// the left is numbered one lower, to the right is one higher, from	×
UNCOV 105	// -alen to +blen. Negative diagonals favor differences from a,	×
UNCOV 106	// positive diagonals favor differences from b. The edit distance to a	×
UNCOV 107	// diagonal d cannot be shorter than d itself.	×
UNCOV 108	//	×
UNCOV 109	// The iterations of this loop cover either odds or evens, but not both,	×
UNCOV 110	// If odd indices are inputs, even indices are outputs and vice versa.	×
UNCOV 111	for diag := -editDistance; diag <= editDistance; diag += 2 { // k	×
UNCOV 112	var aidx int // x	×
UNCOV 113	switch {	×
UNCOV 114	case diag == -editDistance:	×
UNCOV 115	// This is a new diagonal; copy from previous iter	×
UNCOV 116	aidx = endpoint[maxPath-editDistance+1] + 0	×
UNCOV 117	case diag == editDistance:	×
UNCOV 118	// This is a new diagonal; copy from previous iter	×
UNCOV 119	aidx = endpoint[maxPath+editDistance-1] + 1	×
UNCOV 120	case endpoint[maxPath+diag+1] > endpoint[maxPath+diag-1]:	×
UNCOV 121	// diagonal d+1 was farther along, so use that	×
UNCOV 122	aidx = endpoint[maxPath+diag+1] + 0	×
UNCOV 123	default:	×
UNCOV 124	// diagonal d-1 was farther (or the same), so use that	×
UNCOV 125	aidx = endpoint[maxPath+diag-1] + 1	×
126	}
127	// On diagonal d, we can compute bidx from aidx.
UNCOV 128	bidx := aidx - diag // y	×
UNCOV 129	// See how far we can go on this diagonal before we find a difference.	×
UNCOV 130	for aidx < alen && bidx < blen && a[aidx] == b[bidx] {	×
UNCOV 131	aidx++	×
UNCOV 132	bidx++	×
UNCOV 133	}	×
134	// Store the end of the current edit chain.
UNCOV 135	endpoint[maxPath+diag] = aidx	×
UNCOV 136	// If we've found the end of both inputs, we're done!	×
UNCOV 137	if aidx >= alen && bidx >= blen {	×
UNCOV 138	save() // save the final path	×
UNCOV 139	break dLoop	×
140	}
141	}
UNCOV 142	save() // save the current path	×
143	}
UNCOV 144	if editDistance == 0 {	×
UNCOV 145	return nil	×
UNCOV 146	}	×
UNCOV 147	chunks := make([]Chunk, editDistance+1)	×
UNCOV 148		×
UNCOV 149	x, y := alen, blen	×
UNCOV 150	for d := editDistance; d > 0; d-- {	×
UNCOV 151	endpoint := saved[d]	×
UNCOV 152	diag := x - y	×
UNCOV 153	insert := diag == -d \|\| (diag != d && endpoint[maxPath+diag-1] < endpoint[maxPath+diag+1])	×
UNCOV 154		×
UNCOV 155	x1 := endpoint[maxPath+diag]	×
UNCOV 156	var x0, xM, kk int	×
UNCOV 157	if insert {	×
UNCOV 158	kk = diag + 1	×
UNCOV 159	x0 = endpoint[maxPath+kk]	×
UNCOV 160	xM = x0	×
UNCOV 161	} else {	×
UNCOV 162	kk = diag - 1	×
UNCOV 163	x0 = endpoint[maxPath+kk]	×
UNCOV 164	xM = x0 + 1	×
UNCOV 165	}	×
UNCOV 166	y0 := x0 - kk	×
UNCOV 167		×
UNCOV 168	var c Chunk	×
UNCOV 169	if insert {	×
UNCOV 170	c.Added = b[y0:][:1]	×
UNCOV 171	} else {	×
UNCOV 172	c.Deleted = a[x0:][:1]	×
UNCOV 173	}	×
UNCOV 174	if xM < x1 {	×
UNCOV 175	c.Equal = a[xM:][:x1-xM]	×
UNCOV 176	}	×
177
UNCOV 178	x, y = x0, y0	×
UNCOV 179	chunks[d] = c	×
180	}
UNCOV 181	if x > 0 {	×
UNCOV 182	chunks[0].Equal = a[:x]	×
UNCOV 183	}	×
UNCOV 184	if chunks[0].empty() {	×
UNCOV 185	chunks = chunks[1:]	×
UNCOV 186	}	×
UNCOV 187	if len(chunks) == 0 {	×
188	return nil	×
189	}	×
UNCOV 190	return chunks	×
191	}

zalando / postgres-operator / 17065179658

Source File Press 'n' to go to next uncovered line, 'b' for previous

Source File
Press 'n' to go to next uncovered line, 'b' for previous