[ADT] edit_distance: don't return random values for empty strings (PR28780)

[BK1603]

Summary

Fixes the edit_distance bug where if both the strings are
empty the algorithm returns a random integer.

Edited the already existing test and added a test for the case
when both strings are empty.

Bug link: [https://bugs.llvm.org/show_bug.cgi?id=28780]

[lebedev.ri]

Please use more meaningful patch subjects, that make sense and convey the problem the patch solves.

[BK1603]

1. Updating D67000: Fixes bug 28780 #
2. Enter a brief description of the changes included in this update.
3. The first line is used as subject, next lines as comment. #
4. If you intended to create a new revision, use:
5. $ arc diff --create

Added comment to the the code

[BK1603]

@lebedev.ri Sure! I hope it's better now :)

[BK1603]

@lebedev.ri Thanks a lot! Will remember this for further patches :)

llvm/include/llvm/ADT/edit_distance.h

unsigned ComputeEditDistance(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 either of the strings are empty, return the length of the other string.
+  if(m == 0) return n;
+  if(n == 0) return m;
+
   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);
   }

llvm/unittests/ADT/StringRefTest.cpp

TEST(StringRefTest, Count) {
   EXPECT_EQ(0U, Str.count('z'));
   EXPECT_EQ(0U, Str.count("helloworld"));
   EXPECT_EQ(1U, Str.count("hello"));
   EXPECT_EQ(1U, Str.count("ello"));
   EXPECT_EQ(0U, Str.count("zz"));
 }
 
 TEST(StringRefTest, EditDistance) {
+  StringRef StrNull;
+  StringRef StrEmpty("");
+
+  EXPECT_EQ(0U, StrNull.edit_distance(""));
+  EXPECT_EQ(0U, StrEmpty.edit_distance(""));
   StringRef Hello("hello");
   EXPECT_EQ(2U, Hello.edit_distance("hill"));
 
   StringRef Industry("industry");
   EXPECT_EQ(6U, Industry.edit_distance("interest"));
 
   StringRef Soylent("soylent green is people");
   EXPECT_EQ(19U, Soylent.edit_distance("people soiled our green"));