[ADT] Add edit_distance_insensitive to StringRef

[njames93]

Summary

In some instances its advantageous to calculate edit distances without worrying about casing.
Currently to achieve this both strings need to be converted to the same case first, then edit distance can be calculated.

[dblaikie]

Any chance of a template to avoid duplicating this code between case sensitive and case insensitive - looks like a long enough function with room for bugs/fixes/changes that it'd be worth avoiding duplication?

[njames93]

Remove code duplication by adding an extra Map parameter to llvm::ComputeEditDistance.

[dblaikie]

llvm/include/llvm/ADT/edit_distance.h

45–48

Do you need the default type argument here? The default (or explicit, in the other call) value below would allow template argument deduction, right?

49

I'm not sure this + is worthwhile - I'd say either make it a non-template entirely, and hardcode this parameter as a function pointer type (that'd work for the two callers here) or make the functor a template parameter and drop the + here (so that there's no call indirection overhead). (I guess a third option would be llvm::function_ref for functor-level generality without the template, but somewhat more runtime overhead, probably)

I don't have /super/ strong feelings either way.

[njames93]

llvm/include/llvm/ADT/edit_distance.h

45–48

The default value doesn't seem to deduce the template argument, however explicitly passing an argument would deduce the type correctly.

49

You're right, the + isn't necessary

[njames93]

Remove unnecessary '+'

[dblaikie]

llvm/include/llvm/ADT/edit_distance.h

45–48

I think this default templtae argument is unused? (argument deduction kicks in for both uses, doesn't it?) & wrong anyway - the functor type won't be a function pointer type, it'll be the specific type of each lambda, I think?

Could you remove this default template argument?

85–91

is there any concern about the number of times the map operation is used? Looks like the algorithm visits elements more than once, so might be worth some caching?

Like an easy one would probably be to compute Map(FromArray[y-1]) outside the for x loop at least? (but maybe other caching should be done too, I don't know - I guess toLower is cheap enough that it's not worth much more involved caching? - I guess Map(ToArray[x]) could be computed and cached for the next round's references to Map(ToArray[x-1]) for instance?)

[njames93]

Create a new functino ComputeMappedEditDistance to avoid template argument deduction issues.

[njames93]

llvm/include/llvm/ADT/edit_distance.h

85–91

Caching the outer loop value makes sense, but for the inner loop, probably not so much. If its expensive then it'd be better off to just create new arrays with the mapped values, then call ComputeEditDistance with no map functor.

[njames93]

Cache outer loop map item.

[dblaikie]

llvm/include/llvm/ADT/edit_distance.h

81

I'm not sure this amounts to anything different than using auto?

But if the intent was to allow reference types here - maybe this could rely on reference lifetime extension?

const auto &CurItem = ...

If the map function returns by value, this'll do reference lifetime extension, and if it returns by reference it'll be a reference.

[njames93]

llvm/include/llvm/ADT/edit_distance.h

81

Reference lifetime extension is exactly what I needed, just one of those cases I always forget about

[njames93]

Use reference lifetime extension.

[alexander-shaposhnikov]

llvm/include/llvm/ADT/edit_distance.h

46

as a side note, wouldn't it be a bit clearer / more flexible to pass a comparator instead ?

[dblaikie]

llvm/include/llvm/ADT/edit_distance.h

46

oh, fair - I'd be open to that, but wouldn't insist

llvm/include/llvm/ADT/StringRef.h

#endif
     /// \returns the minimum number of character insertions, removals,
     /// or (if \p AllowReplacements is \c true) replacements needed to
     /// transform one of the given strings into the other. If zero,
     /// the strings are identical.
     LLVM_NODISCARD
     unsigned edit_distance(StringRef Other, bool AllowReplacements = true,
                            unsigned MaxEditDistance = 0) const;
 
+    LLVM_NODISCARD unsigned
+    edit_distance_insensitive(StringRef Other, bool AllowReplacements = true,
+                              unsigned MaxEditDistance = 0) const;
+
     /// str - Get the contents as an std::string.
     LLVM_NODISCARD
     std::string str() const {
       if (!Data) return std::string();
       return std::string(Data, Length);
     }
 
     /// @}

llvm/include/llvm/ADT/edit_distance.h

 namespace llvm {
 
 /// Determine the edit distance between two sequences.
 ///
 /// \param FromArray the first sequence to compare.
 ///
 /// \param ToArray the second sequence to compare.
 ///
+/// \param Map A Functor to apply to each item of the sequences before
+/// comparison.
+///
 /// \param AllowReplacements whether to allow element replacements (change one
 /// element into another) as a single operation, rather than as two operations
 /// (an insertion and a removal).
 ///
 /// \param MaxEditDistance If non-zero, the maximum edit distance that this
 /// routine is allowed to compute. If the edit distance will exceed that
 /// maximum, returns \c MaxEditDistance+1.
 ///
 /// \returns the minimum number of element insertions, removals, or (if
 /// \p AllowReplacements is \c true) replacements needed to transform one of
 /// the given sequences into the other. If zero, the sequences are identical.
-template<typename T>
-unsigned ComputeEditDistance(ArrayRef<T> FromArray, ArrayRef<T> ToArray,
-                             bool AllowReplacements = true,
+template <typename T, typename Functor>
+unsigned ComputeMappedEditDistance(ArrayRef<T> FromArray, ArrayRef<T> ToArray,
+                                   Functor Map, bool AllowReplacements = true,
                                    unsigned MaxEditDistance = 0) {
   // The algorithm implemented below is the "classic"
   // dynamic-programming algorithm for computing the Levenshtein
   // distance, which is described here:
   //
   //   http://en.wikipedia.org/wiki/Levenshtein_distance
   //
   // Although the algorithm is typically described using an m x n
   // 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,
unsigned ComputeMappedEditDistance(ArrayRef<T> FromArray, ArrayRef<T> ToArray,
   for (unsigned i = 1; i <= n; ++i)
     Row[i] = i;
 
   for (typename ArrayRef<T>::size_type y = 1; y <= m; ++y) {
     Row[0] = y;
     unsigned BestThisRow = Row[0];
 
     unsigned Previous = y - 1;
+    const auto &CurItem = Map(FromArray[y - 1]);
     for (typename ArrayRef<T>::size_type x = 1; x <= n; ++x) {
       int OldRow = Row[x];
       if (AllowReplacements) {
-        Row[x] = std::min(
-            Previous + (FromArray[y-1] == ToArray[x-1] ? 0u : 1u),
-            std::min(Row[x-1], Row[x])+1);
+        Row[x] = std::min(Previous + (CurItem == Map(ToArray[x - 1]) ? 0u : 1u),
+                          std::min(Row[x - 1], Row[x]) + 1);
       }
       else {
-        if (FromArray[y-1] == ToArray[x-1]) Row[x] = Previous;
+        if (CurItem == Map(ToArray[x - 1]))
+          Row[x] = Previous;
         else Row[x] = std::min(Row[x-1], Row[x]) + 1;
       }
       Previous = OldRow;
       BestThisRow = std::min(BestThisRow, Row[x]);
     }
 
     if (MaxEditDistance && BestThisRow > MaxEditDistance)
       return MaxEditDistance + 1;
   }
 
   unsigned Result = Row[n];
   return Result;
 }
 
+template <typename T>
+unsigned ComputeEditDistance(ArrayRef<T> FromArray, ArrayRef<T> ToArray,
+                             bool AllowReplacements = true,
+                             unsigned MaxEditDistance = 0) {
+  return ComputeMappedEditDistance(
+      FromArray, ToArray, [](const T &X) -> const T & { return X; },
+      AllowReplacements, MaxEditDistance);
+}
+
 } // End llvm namespace
 
 #endif

llvm/lib/Support/StringRef.cpp

unsigned StringRef::edit_distance(llvm::StringRef Other,
                                   bool AllowReplacements,
                                   unsigned MaxEditDistance) const {
   return llvm::ComputeEditDistance(
       makeArrayRef(data(), size()),
       makeArrayRef(Other.data(), Other.size()),
       AllowReplacements, MaxEditDistance);
 }
 
+unsigned llvm::StringRef::edit_distance_insensitive(
+    StringRef Other, bool AllowReplacements, unsigned MaxEditDistance) const {
+  return llvm::ComputeMappedEditDistance(
+      makeArrayRef(data(), size()), makeArrayRef(Other.data(), Other.size()),
+      llvm::toLower, AllowReplacements, MaxEditDistance);
+}
+
 //===----------------------------------------------------------------------===//
 // String Operations
 //===----------------------------------------------------------------------===//
 
 std::string StringRef::lower() const {
   return std::string(map_iterator(begin(), toLower),
                      map_iterator(end(), toLower));
 }

llvm/unittests/ADT/StringRefTest.cpp

TEST(StringRefTest, EditDistance) {
   EXPECT_EQ(9U, Soylent.edit_distance("people soiled our green",
                                       /* allow replacements = */ true,
                                       /* max edit distance = */ 8));
   EXPECT_EQ(53U, Soylent.edit_distance("people soiled our green "
                                        "people soiled our green "
                                        "people soiled our green "));
 }
 
+TEST(StringRefTest, EditDistanceInsensitive) {
+  StringRef Hello("HELLO");
+  EXPECT_EQ(2U, Hello.edit_distance_insensitive("hill"));
+  EXPECT_EQ(0U, Hello.edit_distance_insensitive("hello"));
+
+  StringRef Industry("InDuStRy");
+  EXPECT_EQ(6U, Industry.edit_distance_insensitive("iNtErEsT"));
+}
+
 TEST(StringRefTest, Misc) {
   std::string Storage;
   raw_string_ostream OS(Storage);
   OS << StringRef("hello");
   EXPECT_EQ("hello", OS.str());
 }
 
 TEST(StringRefTest, Hashing) {