[ADT][NFC] Early bail out for ComputeEditDistance

[njames93]

Summary

The minimun bound for number of edits is the size difference between the 2 arrays.
If MaxEditDistance is smaller than this, we can bail out early without needing to traverse any of the arrays.

[dblaikie]

Could be unit tested with a counting map functor? Though I'm not sure that's strictly necessary/worthwhile, up to you.

[njames93]

Add tests to verify bailing out.

[dblaikie]

Looks good, thanks!

llvm/unittests/ADT/EditDistanceTest.cpp

35–36 ↗

(On Diff #434755)

Generally prefer implicit construction over explicit where they're both valid - since implicit is strictly less powerful.

llvm/include/llvm/ADT/edit_distance.h

unsigned ComputeMappedEditDistance(ArrayRef<T> FromArray, ArrayRef<T> ToArray,
   // array, only one row plus one element are used at a time, so this
   // implementation just keeps one vector for the row.  To update one entry,
   // only the entries to the left, top, and top-left are needed.  The left
   // entry is in Row[x-1], the top entry is what's in Row[x] from the last
   // iteration, and the top-left entry is stored in Previous.
   typename ArrayRef<T>::size_type m = FromArray.size();
   typename ArrayRef<T>::size_type n = ToArray.size();
 
+  if (MaxEditDistance) {
+    // If the difference in size between the 2 arrays is larger than the max
+    // distance allowed, we can bail out as we will always need at least
+    // MaxEditDistance insertions or removals.
+    typename ArrayRef<T>::size_type AbsDiff = m > n ? m - n : n - m;
+    if (AbsDiff > MaxEditDistance)
+      return MaxEditDistance + 1;
+  }
+
   const unsigned SmallBufferSize = 64;
   unsigned SmallBuffer[SmallBufferSize];
   std::unique_ptr<unsigned[]> Allocated;
   unsigned *Row = SmallBuffer;
   if (n + 1 > SmallBufferSize) {
     Row = new unsigned[n + 1];
     Allocated.reset(Row);
   }