testing::internal::edit_distance Namespace Reference

Enumerations
enum	EditType { kMatch , kAdd , kRemove , kReplace }

Functions
GTEST_API_ std::vector< EditType >	CalculateOptimalEdits (const std::vector< size_t > &left, const std::vector< size_t > &right)
GTEST_API_ std::vector< EditType >	CalculateOptimalEdits (const std::vector< std::string > &left, const std::vector< std::string > &right)
GTEST_API_ std::string	CreateUnifiedDiff (const std::vector< std::string > &left, const std::vector< std::string > &right, size_t context=2)

Enumeration Type Documentation

EditType

enum testing::internal::edit_distance::EditType

Enumerator
kMatch
kAdd
kRemove
kReplace

Definition at line 168 of file gtest-internal.h.

{ kMatch, kAdd, kRemove, kReplace };

Function Documentation

CalculateOptimalEdits() [1/2]

std::vector< EditType > testing::internal::edit_distance::CalculateOptimalEdits	(	const std::vector< size_t > &	left,
		const std::vector< size_t > &	right
	)

Definition at line 1227 of file gtest.cc.

                                                                            {
  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;
}

CalculateOptimalEdits() [2/2]

std::vector< EditType > testing::internal::edit_distance::CalculateOptimalEdits	(	const std::vector< std::string > &	left,
		const std::vector< std::string > &	right
	)

Definition at line 1303 of file gtest.cc.

                                       {
  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);
}

CreateUnifiedDiff()

std::string testing::internal::edit_distance::CreateUnifiedDiff	(	const std::vector< std::string > &	left,
		const std::vector< std::string > &	right,
		size_t	context = 2
	)

Definition at line 1402 of file gtest.cc.

                                              {
  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.
        auto it = edits.begin() + static_cast<int>(edit_i);
        while (it != edits.end() && *it == kMatch) ++it;
        if (it == edits.end() ||
            static_cast<size_t>(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();
}