diff options
author | Abseil Team <absl-team@google.com> | 2018-08-27 18:53:25 (GMT) |
---|---|---|
committer | Gennadiy Civil <misterg@google.com> | 2018-08-28 20:53:30 (GMT) |
commit | 167c5e8188beb5dae002ac7571457e3c26eb6a3f (patch) | |
tree | 3ac7d65d7a5d9eb4be3883cd3032d29cd93e1e21 /googletest/include/gtest | |
parent | 1bb76182caee8239b71b9d6d21f479014d37ad5b (diff) | |
download | googletest-167c5e8188beb5dae002ac7571457e3c26eb6a3f.zip googletest-167c5e8188beb5dae002ac7571457e3c26eb6a3f.tar.gz googletest-167c5e8188beb5dae002ac7571457e3c26eb6a3f.tar.bz2 |
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
Diffstat (limited to 'googletest/include/gtest')
-rw-r--r-- | googletest/include/gtest/internal/gtest-internal.h | 14 |
1 files changed, 6 insertions, 8 deletions
diff --git a/googletest/include/gtest/internal/gtest-internal.h b/googletest/include/gtest/internal/gtest-internal.h index 9593a45..1c2824d 100644 --- a/googletest/include/gtest/internal/gtest-internal.h +++ b/googletest/include/gtest/internal/gtest-internal.h @@ -159,15 +159,15 @@ GTEST_DISABLE_MSC_WARNINGS_POP_() // 4275 #endif // GTEST_HAS_EXCEPTIONS -namespace edit_distance { // Returns the optimal edits to go from 'left' to 'right'. // All edits cost the same, with replace having lower priority than -// add/remove. -// Simple implementation of the Wagner-Fischer algorithm. -// See http://en.wikipedia.org/wiki/Wagner-Fischer_algorithm -enum EditType { kMatch, kAdd, kRemove, kReplace }; +// add/remove. Returns an approximation of the maximum memory used in +// 'memory_usage' if non-null. +// Uses a Dijkstra search, with a couple of simple bells and whistles added on. +enum EditType { kEditMatch, kEditAdd, kEditRemove, kEditReplace }; GTEST_API_ std::vector<EditType> CalculateOptimalEdits( - const std::vector<size_t>& left, const std::vector<size_t>& right); + const std::vector<size_t>& left, const std::vector<size_t>& right, + size_t* memory_usage = NULL); // Same as above, but the input is represented as strings. GTEST_API_ std::vector<EditType> CalculateOptimalEdits( @@ -179,8 +179,6 @@ GTEST_API_ std::string CreateUnifiedDiff(const std::vector<std::string>& left, const std::vector<std::string>& right, size_t context = 2); -} // namespace edit_distance - // Calculate the diff between 'left' and 'right' and return it in unified diff // format. // If not null, stores in 'total_line_count' the total number of lines found |