Expand equality failure messages with a by-line diff.
git-svn-id: http://googletest.googlecode.com/svn/trunk@691 861a406c-534a-0410-8894-cb66d6ee9925
diff --git a/include/gtest/internal/gtest-internal.h b/include/gtest/internal/gtest-internal.h
index ff8f629..21a0f56 100644
--- a/include/gtest/internal/gtest-internal.h
+++ b/include/gtest/internal/gtest-internal.h
@@ -56,6 +56,8 @@
#include <iomanip>
#include <limits>
#include <set>
+#include <string>
+#include <vector>
#include "gtest/gtest-message.h"
#include "gtest/internal/gtest-string.h"
@@ -171,6 +173,36 @@
// 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<EditType> CalculateOptimalEdits(
+ const std::vector<size_t>& left, const std::vector<size_t>& right);
+
+// Same as above, but the input is represented as strings.
+GTEST_API_ std::vector<EditType> CalculateOptimalEdits(
+ const std::vector<std::string>& left,
+ const std::vector<std::string>& right);
+
+// Create a diff of the input strings in Unified diff format.
+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
+// 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 ca3596e..e4f3df3 100644
--- a/src/gtest.cc
+++ b/src/gtest.cc
@@ -46,6 +46,8 @@
#include <algorithm>
#include <iomanip>
#include <limits>
+#include <list>
+#include <map>
#include <ostream> // NOLINT
#include <sstream>
#include <vector>
@@ -80,6 +82,7 @@
#elif GTEST_OS_WINDOWS_MOBILE // We are on Windows CE.
# include <windows.h> // 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 <windows.h> // NOLINT
+# undef min
#else
@@ -981,6 +985,276 @@
namespace internal {
+namespace edit_distance {
+std::vector<EditType> CalculateOptimalEdits(const std::vector<size_t>& left,
+ const std::vector<size_t>& right) {
+ std::vector<std::vector<double> > costs(
+ left.size() + 1, std::vector<double>(right.size() + 1));
+ std::vector<std::vector<EditType> > best_move(
+ left.size() + 1, std::vector<EditType>(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<double>(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<double>(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<EditType> 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<std::string, size_t> IdMap;
+ IdMap ids_;
+};
+
+} // namespace
+
+std::vector<EditType> CalculateOptimalEdits(
+ const std::vector<std::string>& left,
+ const std::vector<std::string>& right) {
+ std::vector<size_t> 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<std::pair<char, const char*> >::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
+ // "@@ -<left_start>,<left_length> +<right_start>,<right_length> @@"
+ // 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<std::pair<char, const char*> > 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<std::string>& left,
+ const std::vector<std::string>& right,
+ size_t context) {
+ const std::vector<EditType> 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<EditType>::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<std::string> SplitEscapedString(const std::string& str) {
+ std::vector<std::string> 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 @@
msg << "\nWhich is: " << expected_value;
}
+ if (!expected_value.empty() && !actual_value.empty()) {
+ const std::vector<std::string> expected_lines =
+ SplitEscapedString(expected_value);
+ const std::vector<std::string> 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 07ab633..5361d8d 100644
--- a/test/gtest_output_test_.cc
+++ b/test/gtest_output_test_.cc
@@ -113,6 +113,11 @@
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 960eedc..da54170 100644
--- a/test/gtest_output_test_golden_lin.txt
+++ b/test/gtest_output_test_golden_lin.txt
@@ -7,7 +7,7 @@
gtest_output_test_.cc:#: Failure
Value of: 3
Expected: 2
-[0;32m[==========] [mRunning 63 tests from 28 test cases.
+[0;32m[==========] [mRunning 64 tests from 28 test cases.
[0;32m[----------] [mGlobal test environment set-up.
FooEnvironment::SetUp() called.
BarEnvironment::SetUp() called.
@@ -31,7 +31,7 @@
[0;32m[ OK ] [mPassingTest.PassingTest1
[0;32m[ RUN ] [mPassingTest.PassingTest2
[0;32m[ OK ] [mPassingTest.PassingTest2
-[0;32m[----------] [m1 test from NonfatalFailureTest
+[0;32m[----------] [m2 tests from NonfatalFailureTest
[0;32m[ RUN ] [mNonfatalFailureTest.EscapesStringOperands
gtest_output_test_.cc:#: Failure
Value of: actual
@@ -44,6 +44,17 @@
Expected: golden
Which is: "\"Line"
[0;31m[ FAILED ] [mNonfatalFailureTest.EscapesStringOperands
+[0;32m[ RUN ] [mNonfatalFailureTest.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
+
+[0;31m[ FAILED ] [mNonfatalFailureTest.DiffForLongStrings
[0;32m[----------] [m3 tests from FatalFailureTest
[0;32m[ RUN ] [mFatalFailureTest.FatalFailureInSubroutine
(expecting a failure that x should be 1)
@@ -599,10 +610,11 @@
gtest_output_test_.cc:#: Failure
Failed
Expected fatal failure.
-[0;32m[==========] [m63 tests from 28 test cases ran.
+[0;32m[==========] [m64 tests from 28 test cases ran.
[0;32m[ PASSED ] [m21 tests.
-[0;31m[ FAILED ] [m42 tests, listed below:
+[0;31m[ FAILED ] [m43 tests, listed below:
[0;31m[ FAILED ] [mNonfatalFailureTest.EscapesStringOperands
+[0;31m[ FAILED ] [mNonfatalFailureTest.DiffForLongStrings
[0;31m[ FAILED ] [mFatalFailureTest.FatalFailureInSubroutine
[0;31m[ FAILED ] [mFatalFailureTest.FatalFailureInNestedSubroutine
[0;31m[ FAILED ] [mFatalFailureTest.NonfatalFailureInSubroutine
@@ -645,7 +657,7 @@
[0;31m[ FAILED ] [mScopedFakeTestPartResultReporterTest.InterceptOnlyCurrentThread
[0;31m[ FAILED ] [mPrintingFailingParams/FailingParamTest.Fails/0, where GetParam() = 2
-42 FAILED TESTS
+43 FAILED TESTS
[0;33m YOU HAVE 1 DISABLED TEST
[mNote: Google Test filter = FatalFailureTest.*:LoggingTest.*
diff --git a/test/gtest_unittest.cc b/test/gtest_unittest.cc
index 6cccd01..42638ce 100644
--- a/test/gtest_unittest.cc
+++ b/test/gtest_unittest.cc
@@ -282,6 +282,9 @@
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 @@
// Tests non-string assertions.
+std::string EditsToString(const std::vector<EditType>& 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<size_t> CharsToIndices(const std::string& str) {
+ std::vector<size_t> out;
+ for (size_t i = 0; i < str.size(); ++i) {
+ out.push_back(str[i]);
+ }
+ return out;
+}
+
+std::vector<std::string> CharsToLines(const std::string& str) {
+ std::vector<std::string> 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 @@
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");
