Skip to content

Commit 5ebb00f

Browse files
committed
fix: switch to better Myers algorithm implementation
See siderolabs/omni#2311 for the rationale. Signed-off-by: Andrey Smirnov <andrey.smirnov@siderolabs.com> (cherry picked from commit 35ad044)
1 parent 2b40379 commit 5ebb00f

File tree

10 files changed

+286
-114
lines changed

10 files changed

+286
-114
lines changed

go.mod

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -306,6 +306,7 @@ require (
306306
github.com/monochromegane/go-gitignore v0.0.0-20200626010858-205db1a8cc00 // indirect
307307
github.com/munnerz/goautoneg v0.0.0-20191010083416-a7dc8b61c822 // indirect
308308
github.com/mxk/go-flowrate v0.0.0-20140419014527-cca7078d478f // indirect
309+
github.com/neticdk/go-stdlib v1.0.0 // indirect
309310
github.com/nsf/termbox-go v0.0.0-20190121233118-02980233997d // indirect
310311
github.com/opencontainers/selinux v1.13.1 // indirect
311312
github.com/opentracing/opentracing-go v1.2.0 // indirect

go.sum

Lines changed: 2 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -528,6 +528,8 @@ github.com/mxk/go-flowrate v0.0.0-20140419014527-cca7078d478f h1:y5//uYreIhSUg3J
528528
github.com/mxk/go-flowrate v0.0.0-20140419014527-cca7078d478f/go.mod h1:ZdcZmHo+o7JKHSa8/e818NopupXU1YMK5fe1lsApnBw=
529529
github.com/nberlee/go-netstat v0.1.2 h1:wgPV1YOUo+kDFypqiKgfxMtnSs1Wb42c7ahI4qyEUJc=
530530
github.com/nberlee/go-netstat v0.1.2/go.mod h1:GvDCRLsUKMRN1wULkt7tpnDmjSIE6YGf5zeVq+mBO64=
531+
github.com/neticdk/go-stdlib v1.0.0 h1:9QCpoMpO5dBJGHJhumZrHzfJyvpVBd2Gc7ODJujfpXY=
532+
github.com/neticdk/go-stdlib v1.0.0/go.mod h1:rch+DEB6VtR972ZPTY6A5OyLmCrp2YlXP0WGjuDDdcw=
531533
github.com/nsf/termbox-go v0.0.0-20190121233118-02980233997d h1:x3S6kxmy49zXVVyhcnrFqxvNVCBPb2KZ9hV2RBdS840=
532534
github.com/nsf/termbox-go v0.0.0-20190121233118-02980233997d/go.mod h1:IuKpRQcYE1Tfu+oAQqaLisqDeXgjyyltCfsaoYN18NQ=
533535
github.com/onsi/ginkgo/v2 v2.27.2 h1:LzwLj0b89qtIy6SSASkzlNvX6WktqurSHwkk2ipF/Ns=

internal/app/machined/internal/server/v1alpha1/v1alpha1_server.go

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -318,7 +318,7 @@ func (s *Server) ApplyConfiguration(ctx context.Context, in *machine.ApplyConfig
318318
}
319319

320320
func generateDiff(r runtime.Runtime, provider config.Provider) (string, error) {
321-
documentsDiff, err := configdiff.DiffToString(r.ConfigContainer(), provider)
321+
documentsDiff, err := configdiff.DiffConfigs(r.ConfigContainer(), provider)
322322
if err != nil {
323323
return "", err
324324
}

internal/app/machined/pkg/runtime/v1alpha1/v1alpha1_runtime.go

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -194,7 +194,7 @@ func (r *Runtime) CanApplyImmediate(cfg config.Provider) error {
194194
}
195195

196196
if !reflect.DeepEqual(currentConfig, newConfig) {
197-
diff, err := configdiff.DiffToString(container.NewV1Alpha1(currentConfig), container.NewV1Alpha1(newConfig))
197+
diff, err := configdiff.DiffConfigs(container.NewV1Alpha1(currentConfig), container.NewV1Alpha1(newConfig))
198198
if err != nil {
199199
return fmt.Errorf("error calculating diff: %w", err)
200200
}

pkg/machinery/config/configdiff/configdiff.go

Lines changed: 6 additions & 97 deletions
Original file line numberDiff line numberDiff line change
@@ -6,23 +6,15 @@
66
package configdiff
77

88
import (
9-
"fmt"
10-
"io"
11-
"strings"
12-
13-
"github.com/fatih/color"
14-
"github.com/hexops/gotextdiff"
15-
"github.com/hexops/gotextdiff/myers"
16-
"github.com/hexops/gotextdiff/span"
17-
189
"github.com/siderolabs/talos/pkg/machinery/config"
1910
"github.com/siderolabs/talos/pkg/machinery/config/encoder"
11+
"github.com/siderolabs/talos/pkg/machinery/textdiff"
2012
)
2113

22-
// Diff outputs (optionally) colorized diff between two machine configurations.
14+
// DiffConfigs returns a string representation of the diff between two machine configurations.
2315
//
2416
// One of the resources might be nil.
25-
func Diff(w io.Writer, oldCfg, newCfg config.Encoder) error {
17+
func DiffConfigs(oldCfg, newCfg config.Encoder) (string, error) {
2618
var (
2719
oldYaml, newYaml []byte
2820
err error
@@ -31,99 +23,16 @@ func Diff(w io.Writer, oldCfg, newCfg config.Encoder) error {
3123
if oldCfg != nil {
3224
oldYaml, err = oldCfg.EncodeBytes(encoder.WithComments(encoder.CommentsDisabled))
3325
if err != nil {
34-
return err
26+
return "", err
3527
}
3628
}
3729

3830
if newCfg != nil {
3931
newYaml, err = newCfg.EncodeBytes(encoder.WithComments(encoder.CommentsDisabled))
4032
if err != nil {
41-
return err
33+
return "", err
4234
}
4335
}
4436

45-
edits := myers.ComputeEdits(span.URIFromPath("a"), string(oldYaml), string(newYaml))
46-
diff := gotextdiff.ToUnified("a", "b", string(oldYaml), edits)
47-
48-
outputDiff(w, diff, true)
49-
50-
return nil
51-
}
52-
53-
// DiffToString returns a string representation of the diff between two machine configurations.
54-
func DiffToString(oldCfg, newCfg config.Encoder) (string, error) {
55-
var sb strings.Builder
56-
57-
err := Diff(&sb, oldCfg, newCfg)
58-
59-
return sb.String(), err
60-
}
61-
62-
//nolint:gocyclo
63-
func outputDiff(w io.Writer, u gotextdiff.Unified, noColor bool) {
64-
if len(u.Hunks) == 0 {
65-
return
66-
}
67-
68-
bold := color.New(color.Bold)
69-
cyan := color.New(color.FgCyan)
70-
red := color.New(color.FgRed)
71-
green := color.New(color.FgGreen)
72-
73-
if noColor {
74-
bold.DisableColor()
75-
cyan.DisableColor()
76-
red.DisableColor()
77-
green.DisableColor()
78-
}
79-
80-
bold.Fprintf(w, "--- %s\n", u.From) //nolint:errcheck
81-
bold.Fprintf(w, "+++ %s\n", u.To) //nolint:errcheck
82-
83-
for _, hunk := range u.Hunks {
84-
fromCount, toCount := 0, 0
85-
86-
for _, l := range hunk.Lines {
87-
switch l.Kind { //nolint:exhaustive
88-
case gotextdiff.Delete:
89-
fromCount++
90-
case gotextdiff.Insert:
91-
toCount++
92-
default:
93-
fromCount++
94-
toCount++
95-
}
96-
}
97-
98-
cyan.Fprintf(w, "@@") //nolint:errcheck
99-
100-
if fromCount > 1 {
101-
cyan.Fprintf(w, " -%d,%d", hunk.FromLine, fromCount) //nolint:errcheck
102-
} else {
103-
cyan.Fprintf(w, " -%d", hunk.FromLine) //nolint:errcheck
104-
}
105-
106-
if toCount > 1 {
107-
cyan.Fprintf(w, " +%d,%d", hunk.ToLine, toCount) //nolint:errcheck
108-
} else {
109-
cyan.Fprintf(w, " +%d", hunk.ToLine) //nolint:errcheck
110-
}
111-
112-
cyan.Fprintf(w, " @@\n") //nolint:errcheck
113-
114-
for _, l := range hunk.Lines {
115-
switch l.Kind { //nolint:exhaustive
116-
case gotextdiff.Delete:
117-
red.Fprintf(w, "-%s", l.Content) //nolint:errcheck
118-
case gotextdiff.Insert:
119-
green.Fprintf(w, "+%s", l.Content) //nolint:errcheck
120-
default:
121-
fmt.Fprintf(w, " %s", l.Content)
122-
}
123-
124-
if !strings.HasSuffix(l.Content, "\n") {
125-
red.Fprintf(w, "\n\\ No newline at end of file\n") //nolint:errcheck
126-
}
127-
}
128-
}
37+
return textdiff.Diff(string(oldYaml), string(newYaml))
12938
}

pkg/machinery/config/configdiff/configdiff_test.go

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -75,7 +75,7 @@ func TestDiffString(t *testing.T) {
7575
oldCfg := must.Value(container.New(test.oldCfg...))(t)
7676
newCfg := must.Value(container.New(test.newCfg...))(t)
7777

78-
got, err := configdiff.DiffToString(oldCfg, newCfg)
78+
got, err := configdiff.DiffConfigs(oldCfg, newCfg)
7979
require.NoError(t, err)
8080

8181
require.Equal(t, test.want, got)

pkg/machinery/go.mod

Lines changed: 2 additions & 5 deletions
Original file line numberDiff line numberDiff line change
@@ -12,13 +12,12 @@ require (
1212
github.com/dustin/go-humanize v1.0.1
1313
github.com/emicklei/dot v1.9.2
1414
github.com/evanphx/json-patch v5.9.11+incompatible
15-
github.com/fatih/color v1.18.0
1615
github.com/ghodss/yaml v1.0.0
1716
github.com/google/cel-go v0.26.1
1817
github.com/hashicorp/go-multierror v1.1.1
19-
github.com/hexops/gotextdiff v1.0.3
2018
github.com/jsimonetti/rtnetlink/v2 v2.1.0
2119
github.com/mdlayher/ethtool v0.4.0
20+
github.com/neticdk/go-stdlib v1.0.0
2221
github.com/opencontainers/runtime-spec v1.2.1
2322
github.com/planetscale/vtprotobuf v0.6.1-0.20241121165744-79df5c4772f2
2423
github.com/ryanuber/go-glob v1.0.0
@@ -36,6 +35,7 @@ require (
3635
google.golang.org/genproto/googleapis/rpc v0.0.0-20251111163417-95abcf5c77ba
3736
google.golang.org/grpc v1.76.0
3837
google.golang.org/protobuf v1.36.10
38+
gopkg.in/yaml.v3 v3.0.1
3939
)
4040

4141
require (
@@ -54,8 +54,6 @@ require (
5454
github.com/grpc-ecosystem/grpc-gateway/v2 v2.27.3 // indirect
5555
github.com/hashicorp/errwrap v1.1.0 // indirect
5656
github.com/josharian/native v1.1.0 // indirect
57-
github.com/mattn/go-colorable v0.1.14 // indirect
58-
github.com/mattn/go-isatty v0.0.20 // indirect
5957
github.com/mdlayher/genetlink v1.3.2 // indirect
6058
github.com/mdlayher/netlink v1.8.0 // indirect
6159
github.com/mdlayher/socket v0.5.1 // indirect
@@ -74,5 +72,4 @@ require (
7472
golang.org/x/text v0.31.0 // indirect
7573
golang.org/x/time v0.14.0 // indirect
7674
gopkg.in/yaml.v2 v2.4.0 // indirect
77-
gopkg.in/yaml.v3 v3.0.1 // indirect
7875
)

pkg/machinery/go.sum

Lines changed: 2 additions & 9 deletions
Original file line numberDiff line numberDiff line change
@@ -36,8 +36,6 @@ github.com/emicklei/dot v1.9.2 h1:E/Wjz+BAH+JDhybEpISbo+QyDMNSiu/wqmIW9y922P8=
3636
github.com/emicklei/dot v1.9.2/go.mod h1:DeV7GvQtIw4h2u73RKBkkFdvVAz0D9fzeJrgPW6gy/s=
3737
github.com/evanphx/json-patch v5.9.11+incompatible h1:ixHHqfcGvxhWkniF1tWxBHA0yb4Z+d1UQi45df52xW8=
3838
github.com/evanphx/json-patch v5.9.11+incompatible/go.mod h1:50XU6AFN0ol/bzJsmQLiYLvXMP4fmwYFNcr97nuDLSk=
39-
github.com/fatih/color v1.18.0 h1:S8gINlzdQ840/4pfAwic/ZE0djQEH3wM94VfqLTZcOM=
40-
github.com/fatih/color v1.18.0/go.mod h1:4FelSpRwEGDpQ12mAdzqdOukCy4u8WUtOY6lkT/6HfU=
4139
github.com/gertd/go-pluralize v0.2.1 h1:M3uASbVjMnTsPb0PNqg+E/24Vwigyo/tvyMTtAlLgiA=
4240
github.com/gertd/go-pluralize v0.2.1/go.mod h1:rbYaKDbsXxmRfr8uygAEKhOWsjyrrqrkHVpZvoOp8zk=
4341
github.com/ghodss/yaml v1.0.0 h1:wQHKEahhL6wmXdzwWG11gIVCkOv05bNOh+Rxn0yngAk=
@@ -65,8 +63,6 @@ github.com/hashicorp/errwrap v1.1.0 h1:OxrOeh75EUXMY8TBjag2fzXGZ40LB6IKw45YeGUDY
6563
github.com/hashicorp/errwrap v1.1.0/go.mod h1:YH+1FKiLXxHSkmPseP+kNlulaMuP3n2brvKWEqk/Jc4=
6664
github.com/hashicorp/go-multierror v1.1.1 h1:H5DkEtf6CXdFp0N0Em5UCwQpXMWke8IA0+lD48awMYo=
6765
github.com/hashicorp/go-multierror v1.1.1/go.mod h1:iw975J/qwKPdAO1clOe2L8331t/9/fmwbPZ6JB6eMoM=
68-
github.com/hexops/gotextdiff v1.0.3 h1:gitA9+qJrrTCsiCl7+kh75nPqQt1cx4ZkudSTLoUqJM=
69-
github.com/hexops/gotextdiff v1.0.3/go.mod h1:pSWU5MAI3yDq+fZBTazCSJysOMbxWL1BSow5/V2vxeg=
7066
github.com/josharian/native v1.1.0 h1:uuaP0hAbW7Y4l0ZRQ6C9zfb7Mg1mbFKry/xzDAfmtLA=
7167
github.com/josharian/native v1.1.0/go.mod h1:7X/raswPFr05uY3HiLlYeyQntB6OO7E/d2Cu7qoaN2w=
7268
github.com/jsimonetti/rtnetlink/v2 v2.1.0 h1:3sSPD0k+Qvia3wbv6kZXCN0Dlz6Swv7RHjvvonuOcKE=
@@ -75,16 +71,14 @@ github.com/kr/pretty v0.3.1 h1:flRD4NNwYAUpkphVc1HcthR4KEIFJ65n8Mw5qdRn3LE=
7571
github.com/kr/pretty v0.3.1/go.mod h1:hoEshYVHaxMs3cyo3Yncou5ZscifuDolrwPKZanG3xk=
7672
github.com/kr/text v0.2.0 h1:5Nx0Ya0ZqY2ygV366QzturHI13Jq95ApcVaJBhpS+AY=
7773
github.com/kr/text v0.2.0/go.mod h1:eLer722TekiGuMkidMxC/pM04lWEeraHUUmBw8l2grE=
78-
github.com/mattn/go-colorable v0.1.14 h1:9A9LHSqF/7dyVVX6g0U9cwm9pG3kP9gSzcuIPHPsaIE=
79-
github.com/mattn/go-colorable v0.1.14/go.mod h1:6LmQG8QLFO4G5z1gPvYEzlUgJ2wF+stgPZH1UqBm1s8=
80-
github.com/mattn/go-isatty v0.0.20 h1:xfD0iDuEKnDkl03q4limB+vH+GxLEtL/jb4xVJSWWEY=
81-
github.com/mattn/go-isatty v0.0.20/go.mod h1:W+V8PltTTMOvKvAeJH7IuucS94S2C6jfK/D7dTCTo3Y=
8274
github.com/mdlayher/genetlink v1.3.2 h1:KdrNKe+CTu+IbZnm/GVUMXSqBBLqcGpRDa0xkQy56gw=
8375
github.com/mdlayher/genetlink v1.3.2/go.mod h1:tcC3pkCrPUGIKKsCsp0B3AdaaKuHtaxoJRz3cc+528o=
8476
github.com/mdlayher/netlink v1.8.0 h1:e7XNIYJKD7hUct3Px04RuIGJbBxy1/c4nX7D5YyvvlM=
8577
github.com/mdlayher/netlink v1.8.0/go.mod h1:UhgKXUlDQhzb09DrCl2GuRNEglHmhYoWAHid9HK3594=
8678
github.com/mdlayher/socket v0.5.1 h1:VZaqt6RkGkt2OE9l3GcC6nZkqD3xKeQLyfleW/uBcos=
8779
github.com/mdlayher/socket v0.5.1/go.mod h1:TjPLHI1UgwEv5J1B5q0zTZq12A/6H7nKmtTanQE37IQ=
80+
github.com/neticdk/go-stdlib v1.0.0 h1:9QCpoMpO5dBJGHJhumZrHzfJyvpVBd2Gc7ODJujfpXY=
81+
github.com/neticdk/go-stdlib v1.0.0/go.mod h1:rch+DEB6VtR972ZPTY6A5OyLmCrp2YlXP0WGjuDDdcw=
8882
github.com/onsi/ginkgo/v2 v2.20.1 h1:YlVIbqct+ZmnEph770q9Q7NVAz4wwIiVNahee6JyUzo=
8983
github.com/onsi/ginkgo/v2 v2.20.1/go.mod h1:lG9ey2Z29hR41WMVthyJBGUBcBhGOtoPF2VFMvBXFCI=
9084
github.com/onsi/gomega v1.34.1 h1:EUMJIKUjM8sKjYbtxQI9A4z2o+rruxnzNvpknOXie6k=
@@ -186,7 +180,6 @@ golang.org/x/sys v0.0.0-20220520151302-bc2c85ada10a/go.mod h1:oPkhp1MJrh7nUepCBc
186180
golang.org/x/sys v0.0.0-20220722155257-8c9f86f7a55f/go.mod h1:oPkhp1MJrh7nUepCBck5+mAzfO9JrbApNNgaTdGDITg=
187181
golang.org/x/sys v0.1.0/go.mod h1:oPkhp1MJrh7nUepCBck5+mAzfO9JrbApNNgaTdGDITg=
188182
golang.org/x/sys v0.5.0/go.mod h1:oPkhp1MJrh7nUepCBck5+mAzfO9JrbApNNgaTdGDITg=
189-
golang.org/x/sys v0.6.0/go.mod h1:oPkhp1MJrh7nUepCBck5+mAzfO9JrbApNNgaTdGDITg=
190183
golang.org/x/sys v0.38.0 h1:3yZWxaJjBmCWXqhN1qh02AkOnCQ1poK6oF+a7xWL6Gc=
191184
golang.org/x/sys v0.38.0/go.mod h1:OgkHotnGiDImocRcuBABYBEXf8A9a87e/uXjp9XT3ks=
192185
golang.org/x/term v0.0.0-20201126162022-7de9c90e9dd1/go.mod h1:bj7SfCRtBDWHUb9snDiAeCFNEtKQo2Wmx5Cou7ajbmo=

pkg/machinery/textdiff/textdiff.go

Lines changed: 77 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,77 @@
1+
// This Source Code Form is subject to the terms of the Mozilla Public
2+
// License, v. 2.0. If a copy of the MPL was not distributed with this
3+
// file, You can obtain one at http://mozilla.org/MPL/2.0/.
4+
5+
// Package textdiff provides a way to compare two text blobs.
6+
package textdiff
7+
8+
import (
9+
"fmt"
10+
"strings"
11+
12+
"github.com/neticdk/go-stdlib/diff/myers"
13+
)
14+
15+
// MaxLines is the maximum number of lines that the diff function will process before giving up and returning a message instead.
16+
const MaxLines = 75_000
17+
18+
// Diff is a function that computes unified diff between two strings.
19+
//
20+
// The diff is limited to MaxLines lines, and if the diff is larger than that, a message is returned instead of the actual diff.
21+
// This is to prevent the function from consuming too much memory or CPU time when comparing large text blobs.
22+
func Diff(a, b string) (string, error) {
23+
if a == b {
24+
return "", nil
25+
}
26+
27+
prevLines := strings.Count(a, "\n")
28+
newLines := strings.Count(b, "\n")
29+
30+
if prevLines+newLines > MaxLines {
31+
return fmt.Sprintf("@@ -%d,%d +%d,%d @@ diff too large to display\n", 1, prevLines, 1, newLines), nil
32+
}
33+
34+
differ := myers.NewCustomDiffer(
35+
myers.WithUnifiedFormatter(),
36+
myers.WithLinearSpace(true),
37+
// Disable the library's standard-Myers and LCS fallback paths:
38+
// - Standard Myers (< smallInputThreshold) is O((N+M)²) when inputs are asymmetric.
39+
// - LCS (> largeInputThreshold) is O(N*M) for the DP table.
40+
// By setting these to 0 and MaxLines respectively, only Hirschberg's
41+
// O(N+M) linear-space algorithm runs. Our MaxLines guard above ensures
42+
// inputs never exceed largeInputThreshold.
43+
myers.WithSmallInputThreshold(0),
44+
myers.WithLargeInputThreshold(MaxLines),
45+
)
46+
47+
return differ.Diff(a, b)
48+
}
49+
50+
// DiffWithCustomPaths is almost same as Diff, but allows to specify custom paths for the diff header.
51+
func DiffWithCustomPaths(a, b, aPath, bPath string) (string, error) {
52+
diff, err := Diff(a, b)
53+
if err != nil {
54+
return "", err
55+
}
56+
57+
if diff == "" {
58+
return "", nil
59+
}
60+
61+
// patch the diff header to include the manifest path
62+
diff, ok := strings.CutPrefix(diff, "--- a\n+++ b\n")
63+
if !ok {
64+
return "", fmt.Errorf("unexpected diff format")
65+
}
66+
67+
var sb strings.Builder
68+
69+
sb.WriteString("--- ")
70+
sb.WriteString(aPath)
71+
sb.WriteString("\n+++ ")
72+
sb.WriteString(bPath)
73+
sb.WriteString("\n")
74+
sb.WriteString(diff)
75+
76+
return sb.String(), nil
77+
}

0 commit comments

Comments
 (0)