tree 3ac7d65d7a5d9eb4be3883cd3032d29cd93e1e21
parent 1bb76182caee8239b71b9d6d21f479014d37ad5b
author Abseil Team <absl-team@google.com> 1535396005 -0400
committer Gennadiy Civil <misterg@google.com> 1535489610 -0400

Googletest export

Fix Theta(N^2) memory usage of EXPECT_EQ(string) when the strings don't match.

The underlying CalculateOptimalEdits() implementation used a simple
dynamic-programming approach that always used N^2 memory and time. This meant
that tests for equality of large strings were ticking time bombs: They'd work
fine as long as the test passed, but as soon as the strings differed the test
would OOM, which is very hard to debug.
I switched it out for a Dijkstra search, which is still worst-case O(N^2), but
in the usual case of mostly-matching strings, it is much closer to linear.

PiperOrigin-RevId: 210405025