Incorrect slice diff output

[dsnet]

Consider the following snippet:

got := "Forwarding service bread:foo-http-jean has a same-env shard undrained: aa:jean-shard000. The quick brown fox jumped over the lazy dog."
want := "Forwarding service bread:foo-api-scary has a same-env shard undrained: bb:scary-shard000. The quick brown fox jumped over the lazy dog."
fmt.Println(cmp.Diff(got, want))

Depending on the randomization involved, this sometimes prints:

  strings.Join({
  	"Fo",
- 	"rwar",
+ 	"rwar",
  	"ding service bread:foo-",
- 	"http-jean",
+ 	"api-scary",
  	" has a same-env shard undrained: ",
- 	"aa:jean",
+ 	"bb:scary",
  	"-shard000. The quick brown fox jumped over the lazy dog.",
  }, "")

when it should print:

  strings.Join({
  	"Forwarding service bread:foo-",
- 	"http-jean",
+ 	"api-scary",
  	" has a same-env shard undrained: ",
- 	"aa:jean",
+ 	"bb:scary",
  	"-shard000. The quick brown fox jumped over the lazy dog.",
  }, "")

Not that it incorrectly reports that "rwar" is different?

[Eun]

Having the same on uint8 slices:

func TestDiff(t *testing.T) {
	fmt.Println(cmp.Diff(
		// Hello Universe
		[]uint8{0x48, 0x65, 0x6c, 0x6c, 0x6f, 0x20, 0x55, 0x6e, 0x69, 0x76, 0x65, 0x72, 0x73, 0x65},
		// Hello World
		[]uint8{0x48, 0x65, 0x6c, 0x6c, 0x6f, 0x20, 0x57, 0x6f, 0x72, 0x6c, 0x64},
	))
}

sometimes reports

  []uint8{
  	... // 4 identical elements
  	0x6f,
  	0x20,
- 	0x55,
+ 	0x57,
- 	0x6e,
+ 	0x6f,
- 	0x69,
- 	0x76,
- 	0x65,
  	0x72,
- 	0x73,
+ 	0x6c,
- 	0x65,
+ 	0x64,
  }

sometimes

  bytes.Join({
  	"Hello ",
- 	"Universe",
+ 	"World",
  }, "")

[dsnet]

Hi @Eun, thanks for the report, but it's not the same issue. My original one is about the fact that the Diff is reporting a difference when there is none:

- 	"rwar",
+ 	"rwar",

This is incorrect.

The example you provided is one where the Diff is still correct, but sub-optimally shown. I'm fairly sure your specific case would be fixed by improving the optimality of the diffing algorithm (which is a different but valid concern). It currently uses a greedy search for differences, which may cause it to land in a local optimum, but is at least guaranteed to run in O(n). It just so happens that running the algorithm forwards produces a more optimal diff than running it backwards.

[Eun]

@dsnet Yeah I also realized that this might be a different issue than yours, I wasn't sure tho. I will create a new issue for that.

It appears that the problem may be related to the fact that when zigzagInit is assigned the value 1 in diff.Difference(), the first forward-searching match is determined to be (5, 2). Whereas when zigzagInit is assigned the value 0, the first forward match is correctly determined to be (0, 0). In the cases where the forward search is not allowed to begin at zero, it's as if it cannot discern matches that begin at the first element.

I notice the comments state:

// To ensure flexibility in changing the algorithm in the future,
// introduce some degree of deliberate instability.
// This is achieved by fiddling the zigzag iterator to start searching
// the graph starting from the bottom-right versus than the top-left.

Is this correct? Perhaps I'm misunderstanding, but it seems like zigZagInit does not drive whether the search begins from the top-left or bottom-right.

[dsnet]

This bug is definitely related to zigzagInit. It's not operate remotely like what is documented. I sent #247, which should fix it.

Coincidentally, this also fixes the case that @Eun reported. However, I'm going to keep #244 open since improving the optimality of the diffing algorithm is still something we want to do.

Nice. Here is a somewhat simpler solution that I had envisioned if you are interested.

[dsnet]

Thanks @C-DY for the PR! Mine may be a slightly more lines of change, but I was aiming to more clearly preserve the symmetry that exists between the forward and backward searches. They are identical except operating in different directions.