From b54098a9abade957ab3c4e94ae5e5225ef0015a4 Mon Sep 17 00:00:00 2001 From: kosak Date: Mon, 28 Jul 2014 21:54:50 +0000 Subject: Expand equality failure messages with a by-line diff. --- include/gtest/internal/gtest-internal.h | 32 ++++ src/gtest.cc | 285 ++++++++++++++++++++++++++++++++ test/gtest_output_test_.cc | 5 + test/gtest_output_test_golden_lin.txt | 22 ++- test/gtest_unittest.cc | 94 +++++++++++ 5 files changed, 433 insertions(+), 5 deletions(-) diff --git a/include/gtest/internal/gtest-internal.h b/include/gtest/internal/gtest-internal.h index ff8f6298..21a0f567 100644 --- a/include/gtest/internal/gtest-internal.h +++ b/include/gtest/internal/gtest-internal.h @@ -56,6 +56,8 @@ #include #include #include +#include +#include #include "gtest/gtest-message.h" #include "gtest/internal/gtest-string.h" @@ -171,6 +173,36 @@ class GTEST_API_ ScopedTrace { // c'tor and d'tor. Therefore it doesn't // need to be used otherwise. +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 }; +GTEST_API_ std::vector CalculateOptimalEdits( + const std::vector& left, const std::vector& right); + +// Same as above, but the input is represented as strings. +GTEST_API_ std::vector CalculateOptimalEdits( + const std::vector& left, + const std::vector& right); + +// Create a diff of the input strings in Unified diff format. +GTEST_API_ std::string CreateUnifiedDiff(const std::vector& left, + const std::vector& 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 +// in left + right. +GTEST_API_ std::string DiffStrings(const std::string& left, + const std::string& right, + size_t* total_line_count); + // Constructs and returns the message for an equality assertion // (e.g. ASSERT_EQ, EXPECT_STREQ, etc) failure. // diff --git a/src/gtest.cc b/src/gtest.cc index ca3596eb..e4f3df3e 100644 --- a/src/gtest.cc +++ b/src/gtest.cc @@ -46,6 +46,8 @@ #include #include #include +#include +#include #include // NOLINT #include #include @@ -80,6 +82,7 @@ #elif GTEST_OS_WINDOWS_MOBILE // We are on Windows CE. # include // NOLINT +# undef min #elif GTEST_OS_WINDOWS // We are on Windows proper. @@ -102,6 +105,7 @@ // cpplint thinks that the header is already included, so we want to // silence it. # include // NOLINT +# undef min #else @@ -981,6 +985,276 @@ AssertionResult AssertionFailure(const Message& message) { namespace internal { +namespace edit_distance { +std::vector CalculateOptimalEdits(const std::vector& left, + const std::vector& right) { + std::vector > costs( + left.size() + 1, std::vector(right.size() + 1)); + std::vector > best_move( + left.size() + 1, std::vector(right.size() + 1)); + + // Populate for empty right. + for (size_t l_i = 0; l_i < costs.size(); ++l_i) { + costs[l_i][0] = static_cast(l_i); + best_move[l_i][0] = kRemove; + } + // Populate for empty left. + for (size_t r_i = 1; r_i < costs[0].size(); ++r_i) { + costs[0][r_i] = static_cast(r_i); + best_move[0][r_i] = kAdd; + } + + for (size_t l_i = 0; l_i < left.size(); ++l_i) { + for (size_t r_i = 0; r_i < right.size(); ++r_i) { + if (left[l_i] == right[r_i]) { + // Found a match. Consume it. + costs[l_i + 1][r_i + 1] = costs[l_i][r_i]; + best_move[l_i + 1][r_i + 1] = kMatch; + continue; + } + + const double add = costs[l_i + 1][r_i]; + const double remove = costs[l_i][r_i + 1]; + const double replace = costs[l_i][r_i]; + if (add < remove && add < replace) { + costs[l_i + 1][r_i + 1] = add + 1; + best_move[l_i + 1][r_i + 1] = kAdd; + } else if (remove < add && remove < replace) { + costs[l_i + 1][r_i + 1] = remove + 1; + best_move[l_i + 1][r_i + 1] = kRemove; + } else { + // We make replace a little more expensive than add/remove to lower + // their priority. + costs[l_i + 1][r_i + 1] = replace + 1.00001; + best_move[l_i + 1][r_i + 1] = kReplace; + } + } + } + + // Reconstruct the best path. We do it in reverse order. + std::vector best_path; + for (size_t l_i = left.size(), r_i = right.size(); l_i > 0 || r_i > 0;) { + EditType move = best_move[l_i][r_i]; + best_path.push_back(move); + l_i -= move != kAdd; + r_i -= move != kRemove; + } + std::reverse(best_path.begin(), best_path.end()); + return best_path; +} + +namespace { + +// Helper class to convert string into ids with deduplication. +class InternalStrings { + public: + size_t GetId(const std::string& str) { + IdMap::iterator it = ids_.find(str); + if (it != ids_.end()) return it->second; + size_t id = ids_.size(); + return ids_[str] = id; + } + + private: + typedef std::map IdMap; + IdMap ids_; +}; + +} // namespace + +std::vector CalculateOptimalEdits( + const std::vector& left, + const std::vector& right) { + std::vector left_ids, right_ids; + { + InternalStrings intern_table; + for (size_t i = 0; i < left.size(); ++i) { + left_ids.push_back(intern_table.GetId(left[i])); + } + for (size_t i = 0; i < right.size(); ++i) { + right_ids.push_back(intern_table.GetId(right[i])); + } + } + return CalculateOptimalEdits(left_ids, right_ids); +} + +namespace { + +// Helper class that holds the state for one hunk and prints it out to the +// stream. +// It reorders adds/removes when possible to group all removes before all +// adds. It also adds the hunk header before printint into the stream. +class Hunk { + public: + Hunk(size_t left_start, size_t right_start) + : left_start_(left_start), + right_start_(right_start), + adds_(), + removes_(), + common_() {} + + void PushLine(char edit, const char* line) { + switch (edit) { + case ' ': + ++common_; + FlushEdits(); + hunk_.push_back(std::make_pair(' ', line)); + break; + case '-': + ++removes_; + hunk_removes_.push_back(std::make_pair('-', line)); + break; + case '+': + ++adds_; + hunk_adds_.push_back(std::make_pair('+', line)); + break; + } + } + + void PrintTo(std::ostream* os) { + PrintHeader(os); + FlushEdits(); + for (std::list >::const_iterator it = + hunk_.begin(); + it != hunk_.end(); ++it) { + *os << it->first << it->second << "\n"; + } + } + + bool has_edits() const { return adds_ || removes_; } + + private: + void FlushEdits() { + hunk_.splice(hunk_.end(), hunk_removes_); + hunk_.splice(hunk_.end(), hunk_adds_); + } + + // Print a unified diff header for one hunk. + // The format is + // "@@ -, +, @@" + // where the left/right parts are ommitted if unnecessary. + void PrintHeader(std::ostream* ss) const { + *ss << "@@ "; + if (removes_) { + *ss << "-" << left_start_ << "," << (removes_ + common_); + } + if (removes_ && adds_) { + *ss << " "; + } + if (adds_) { + *ss << "+" << right_start_ << "," << (adds_ + common_); + } + *ss << " @@\n"; + } + + size_t left_start_, right_start_; + size_t adds_, removes_, common_; + std::list > hunk_, hunk_adds_, hunk_removes_; +}; + +} // namespace + +// Create a list of diff hunks in Unified diff format. +// Each hunk has a header generated by PrintHeader above plus a body with +// lines prefixed with ' ' for no change, '-' for deletion and '+' for +// addition. +// 'context' represents the desired unchanged prefix/suffix around the diff. +// If two hunks are close enough that their contexts overlap, then they are +// joined into one hunk. +std::string CreateUnifiedDiff(const std::vector& left, + const std::vector& right, + size_t context) { + const std::vector edits = CalculateOptimalEdits(left, right); + + size_t l_i = 0, r_i = 0, edit_i = 0; + std::stringstream ss; + while (edit_i < edits.size()) { + // Find first edit. + while (edit_i < edits.size() && edits[edit_i] == kMatch) { + ++l_i; + ++r_i; + ++edit_i; + } + + // Find the first line to include in the hunk. + const size_t prefix_context = std::min(l_i, context); + Hunk hunk(l_i - prefix_context + 1, r_i - prefix_context + 1); + for (size_t i = prefix_context; i > 0; --i) { + hunk.PushLine(' ', left[l_i - i].c_str()); + } + + // Iterate the edits until we found enough suffix for the hunk or the input + // is over. + size_t n_suffix = 0; + for (; edit_i < edits.size(); ++edit_i) { + if (n_suffix >= context) { + // Continue only if the next hunk is very close. + std::vector::const_iterator it = edits.begin() + edit_i; + while (it != edits.end() && *it == kMatch) ++it; + if (it == edits.end() || (it - edits.begin()) - edit_i >= context) { + // There is no next edit or it is too far away. + break; + } + } + + EditType edit = edits[edit_i]; + // Reset count when a non match is found. + n_suffix = edit == kMatch ? n_suffix + 1 : 0; + + if (edit == kMatch || edit == kRemove || edit == kReplace) { + hunk.PushLine(edit == kMatch ? ' ' : '-', left[l_i].c_str()); + } + if (edit == kAdd || edit == kReplace) { + hunk.PushLine('+', right[r_i].c_str()); + } + + // Advance indices, depending on edit type. + l_i += edit != kAdd; + r_i += edit != kRemove; + } + + if (!hunk.has_edits()) { + // We are done. We don't want this hunk. + break; + } + + hunk.PrintTo(&ss); + } + return ss.str(); +} + +} // namespace edit_distance + +namespace { + +// The string representation of the values received in EqFailure() are already +// escaped. Split them on escaped '\n' boundaries. Leave all other escaped +// characters the same. +std::vector SplitEscapedString(const std::string& str) { + std::vector lines; + size_t start = 0, end = str.size(); + if (end > 2 && str[0] == '"' && str[end - 1] == '"') { + ++start; + --end; + } + bool escaped = false; + for (size_t i = start; i + 1 < end; ++i) { + if (escaped) { + escaped = false; + if (str[i] == 'n') { + lines.push_back(str.substr(start, i - start - 1)); + start = i + 1; + } + } else { + escaped = str[i] == '\\'; + } + } + lines.push_back(str.substr(start, end - start)); + return lines; +} + +} // namespace + // Constructs and returns the message for an equality assertion // (e.g. ASSERT_EQ, EXPECT_STREQ, etc) failure. // @@ -1015,6 +1289,17 @@ AssertionResult EqFailure(const char* expected_expression, msg << "\nWhich is: " << expected_value; } + if (!expected_value.empty() && !actual_value.empty()) { + const std::vector expected_lines = + SplitEscapedString(expected_value); + const std::vector actual_lines = + SplitEscapedString(actual_value); + if (expected_lines.size() > 1 || actual_lines.size() > 1) { + msg << "\nWith diff:\n" + << edit_distance::CreateUnifiedDiff(expected_lines, actual_lines); + } + } + return AssertionFailure() << msg; } diff --git a/test/gtest_output_test_.cc b/test/gtest_output_test_.cc index 07ab633d..5361d8d8 100644 --- a/test/gtest_output_test_.cc +++ b/test/gtest_output_test_.cc @@ -113,6 +113,11 @@ TEST(NonfatalFailureTest, EscapesStringOperands) { EXPECT_EQ(golden, actual); } +TEST(NonfatalFailureTest, DiffForLongStrings) { + std::string golden_str(kGoldenString, sizeof(kGoldenString) - 1); + EXPECT_EQ(golden_str, "Line 2"); +} + // Tests catching a fatal failure in a subroutine. TEST(FatalFailureTest, FatalFailureInSubroutine) { printf("(expecting a failure that x should be 1)\n"); diff --git a/test/gtest_output_test_golden_lin.txt b/test/gtest_output_test_golden_lin.txt index 960eedce..da541700 100644 --- a/test/gtest_output_test_golden_lin.txt +++ b/test/gtest_output_test_golden_lin.txt @@ -7,7 +7,7 @@ Expected: true gtest_output_test_.cc:#: Failure Value of: 3 Expected: 2 -[==========] Running 63 tests from 28 test cases. +[==========] Running 64 tests from 28 test cases. [----------] Global test environment set-up. FooEnvironment::SetUp() called. BarEnvironment::SetUp() called. @@ -31,7 +31,7 @@ BarEnvironment::SetUp() called. [ OK ] PassingTest.PassingTest1 [ RUN ] PassingTest.PassingTest2 [ OK ] PassingTest.PassingTest2 -[----------] 1 test from NonfatalFailureTest +[----------] 2 tests from NonfatalFailureTest [ RUN ] NonfatalFailureTest.EscapesStringOperands gtest_output_test_.cc:#: Failure Value of: actual @@ -44,6 +44,17 @@ Value of: actual Expected: golden Which is: "\"Line" [ FAILED ] NonfatalFailureTest.EscapesStringOperands +[ RUN ] NonfatalFailureTest.DiffForLongStrings +gtest_output_test_.cc:#: Failure +Value of: "Line 2" +Expected: golden_str +Which is: "\"Line\0 1\"\nLine 2" +With diff: +@@ -1,2 @@ +-\"Line\0 1\" + Line 2 + +[ FAILED ] NonfatalFailureTest.DiffForLongStrings [----------] 3 tests from FatalFailureTest [ RUN ] FatalFailureTest.FatalFailureInSubroutine (expecting a failure that x should be 1) @@ -599,10 +610,11 @@ FooEnvironment::TearDown() called. gtest_output_test_.cc:#: Failure Failed Expected fatal failure. -[==========] 63 tests from 28 test cases ran. +[==========] 64 tests from 28 test cases ran. [ PASSED ] 21 tests. -[ FAILED ] 42 tests, listed below: +[ FAILED ] 43 tests, listed below: [ FAILED ] NonfatalFailureTest.EscapesStringOperands +[ FAILED ] NonfatalFailureTest.DiffForLongStrings [ FAILED ] FatalFailureTest.FatalFailureInSubroutine [ FAILED ] FatalFailureTest.FatalFailureInNestedSubroutine [ FAILED ] FatalFailureTest.NonfatalFailureInSubroutine @@ -645,7 +657,7 @@ Expected fatal failure. [ FAILED ] ScopedFakeTestPartResultReporterTest.InterceptOnlyCurrentThread [ FAILED ] PrintingFailingParams/FailingParamTest.Fails/0, where GetParam() = 2 -42 FAILED TESTS +43 FAILED TESTS  YOU HAVE 1 DISABLED TEST Note: Google Test filter = FatalFailureTest.*:LoggingTest.* diff --git a/test/gtest_unittest.cc b/test/gtest_unittest.cc index 6cccd018..42638ce2 100644 --- a/test/gtest_unittest.cc +++ b/test/gtest_unittest.cc @@ -282,6 +282,9 @@ using testing::internal::TestEventListenersAccessor; using testing::internal::TestResultAccessor; using testing::internal::UInt32; using testing::internal::WideStringToUtf8; +using testing::internal::edit_distance::CalculateOptimalEdits; +using testing::internal::edit_distance::CreateUnifiedDiff; +using testing::internal::edit_distance::EditType; using testing::internal::kMaxRandomSeed; using testing::internal::kTestTypeIdInGoogleTest; using testing::internal::scoped_ptr; @@ -3431,6 +3434,79 @@ TEST_F(NoFatalFailureTest, MessageIsStreamable) { // Tests non-string assertions. +std::string EditsToString(const std::vector& edits) { + std::string out; + for (size_t i = 0; i < edits.size(); ++i) { + static const char kEdits[] = " +-/"; + out.append(1, kEdits[edits[i]]); + } + return out; +} + +std::vector CharsToIndices(const std::string& str) { + std::vector out; + for (size_t i = 0; i < str.size(); ++i) { + out.push_back(str[i]); + } + return out; +} + +std::vector CharsToLines(const std::string& str) { + std::vector out; + for (size_t i = 0; i < str.size(); ++i) { + out.push_back(str.substr(i, 1)); + } + return out; +} + +TEST(EditDistance, TestCases) { + struct Case { + int line; + const char* left; + const char* right; + const char* expected_edits; + const char* expected_diff; + }; + static const Case kCases[] = { + // No change. + {__LINE__, "A", "A", " ", ""}, + {__LINE__, "ABCDE", "ABCDE", " ", ""}, + // Simple adds. + {__LINE__, "X", "XA", " +", "@@ +1,2 @@\n X\n+A\n"}, + {__LINE__, "X", "XABCD", " ++++", "@@ +1,5 @@\n X\n+A\n+B\n+C\n+D\n"}, + // Simple removes. + {__LINE__, "XA", "X", " -", "@@ -1,2 @@\n X\n-A\n"}, + {__LINE__, "XABCD", "X", " ----", "@@ -1,5 @@\n X\n-A\n-B\n-C\n-D\n"}, + // Simple replaces. + {__LINE__, "A", "a", "/", "@@ -1,1 +1,1 @@\n-A\n+a\n"}, + {__LINE__, "ABCD", "abcd", "////", + "@@ -1,4 +1,4 @@\n-A\n-B\n-C\n-D\n+a\n+b\n+c\n+d\n"}, + // Path finding. + {__LINE__, "ABCDEFGH", "ABXEGH1", " -/ - +", + "@@ -1,8 +1,7 @@\n A\n B\n-C\n-D\n+X\n E\n-F\n G\n H\n+1\n"}, + {__LINE__, "AAAABCCCC", "ABABCDCDC", "- / + / ", + "@@ -1,9 +1,9 @@\n-A\n A\n-A\n+B\n A\n B\n C\n+D\n C\n-C\n+D\n C\n"}, + {__LINE__, "ABCDE", "BCDCD", "- +/", + "@@ -1,5 +1,5 @@\n-A\n B\n C\n D\n-E\n+C\n+D\n"}, + {__LINE__, "ABCDEFGHIJKL", "BCDCDEFGJKLJK", "- ++ -- ++", + "@@ -1,4 +1,5 @@\n-A\n B\n+C\n+D\n C\n D\n" + "@@ -6,7 +7,7 @@\n F\n G\n-H\n-I\n J\n K\n L\n+J\n+K\n"}, + {}}; + for (const Case* c = kCases; c->left; ++c) { + EXPECT_TRUE(c->expected_edits == + EditsToString(CalculateOptimalEdits(CharsToIndices(c->left), + CharsToIndices(c->right)))) + << "Left <" << c->left << "> Right <" << c->right << "> Edits <" + << EditsToString(CalculateOptimalEdits( + CharsToIndices(c->left), CharsToIndices(c->right))) << ">"; + EXPECT_TRUE(c->expected_diff == CreateUnifiedDiff(CharsToLines(c->left), + CharsToLines(c->right))) + << "Left <" << c->left << "> Right <" << c->right << "> Diff <" + << CreateUnifiedDiff(CharsToLines(c->left), CharsToLines(c->right)) + << ">"; + } +} + // Tests EqFailure(), used for implementing *EQ* assertions. TEST(AssertionTest, EqFailure) { const std::string foo_val("5"), bar_val("6"); @@ -3481,6 +3557,24 @@ TEST(AssertionTest, EqFailure) { msg5.c_str()); } +TEST(AssertionTest, EqFailureWithDiff) { + const std::string left( + "1\\n2XXX\\n3\\n5\\n6\\n7\\n8\\n9\\n10\\n11\\n12XXX\\n13\\n14\\n15"); + const std::string right( + "1\\n2\\n3\\n4\\n5\\n6\\n7\\n8\\n9\\n11\\n12\\n13\\n14"); + const std::string msg1( + EqFailure("left", "right", left, right, false).failure_message()); + EXPECT_STREQ( + "Value of: right\n" + " Actual: 1\\n2\\n3\\n4\\n5\\n6\\n7\\n8\\n9\\n11\\n12\\n13\\n14\n" + "Expected: left\n" + "Which is: " + "1\\n2XXX\\n3\\n5\\n6\\n7\\n8\\n9\\n10\\n11\\n12XXX\\n13\\n14\\n15\n" + "With diff:\n@@ -1,5 +1,6 @@\n 1\n-2XXX\n+2\n 3\n+4\n 5\n 6\n" + "@@ -7,8 +8,6 @@\n 8\n 9\n-10\n 11\n-12XXX\n+12\n 13\n 14\n-15\n", + msg1.c_str()); +} + // Tests AppendUserMessage(), used for implementing the *EQ* macros. TEST(AssertionTest, AppendUserMessage) { const std::string foo("foo"); -- cgit v1.2.3