[ELF] Add a spell corrector for "undefined symbol" diagnostics

[MaskRay]

Summary

Non-undefined symbols with Levenshtein distance 1 or a transposition are
suggestion candidates. This is probably good enough and it can suggest
some missing/superfluous qualifiers: const, restrict, volatile, & and &&
ref-qualifier, e.g.

 error: undefined symbol: foo(int*)
 >>> referenced by b.o:(.text+0x1)
+>>> did you mean: foo(int const*)
+>>> defined in: a.o

 error: undefined symbol: foo(int*&)
 >>> referenced by b.o:(.text+0x1)
+>>> did you mean: foo(int*)
+>>> defined in: b.o

[MaskRay]

Fix a RUN line

[ruiu]

ELF/Relocations.cpp

736 ↗

(On Diff #218226)

Can you factor out the new code into a new function and then add a function comment as to what this is?

[MaskRay]

Add a new function correctSpelling

(I was thinking if the code can be shared with COFF and wasm. We can define it in lld/Common,
but the common part is just ~25 lines, and a non-inline function will harm performance)

[ruiu]

ELF/Relocations.cpp

694 ↗

(On Diff #218286)

Please add a file comment saying that this function is for "did you mean?" feature.

721 ↗

(On Diff #218286)

IIUC, this function costs (N+1)*74 where N is the length of a symbol name. Symbol names can be very long. Doesn't this too slow?

[grimar]

ELF/Relocations.cpp

721 ↗

(On Diff #218286)

It's enabled for the first two undefined symbols. Even with large N, like 100 it shouldn't probably be too slow for the error reporting case?

727 ↗

(On Diff #218286)

Seems it would be simpler to make suggest return const Symbol * (on success) or nullptr (on fail)?
You should be able to early return nicely then:

if (const Symbol *S = suggest(newName))
  return S;

and avoid doing things like

if (corrected)
  break;

823 ↗

(On Diff #218286)

It feels for would look a bit better?

for (size_t I = 0; I<undefs.size(); ++I)
  if (!undefs[I].locs.empty())
    reportUndefinedSymbol<ELFT>(undefs[I], i < 2);

[peter.smith]

Interesting idea. I suspect we'll need to modify it over time in response to feedback. For example, what if there are several candidates, should we report them all, give one stronger weighting etc. One thing I don't think it will catch, which is my most common and least favourite typo, is a transposition which is usually a distance of 2. I'm less concerned about the algorithm speed at the moment as it should only trigger in an error case, and if it aids debugging then it is time well spent.

ELF/Relocations.cpp

752 ↗

(On Diff #218286)

I think you mean to use spellCorrector as a verb (do spelling correction), but it reads like a noun (spellCorrector is some object that does spelling correction). I suggest doSpellingCorrection or correctSpelling.

[peter.smith]

ELF/Relocations.cpp

694 ↗

(On Diff #218286)

I suggest getAlternativeSpelling as there could be many symbols within the same distance, particularly sym1, sym2, sym9 for correctSpelling(sym)

[MaskRay]

Interesting idea. I suspect we'll need to modify it over time in response to feedback. For example, what if there are several candidates, should we report them all, give one stronger weighting etc.

Agree. We can wait for user feedback.

One thing I don't think it will catch, which is my most common and least favourite typo, is a transposition which is usually a distance of 2.

Added transposition.

I'm less concerned about the algorithm speed at the moment as it should only trigger in an error case, and if it aids debugging then it is time well spent.

[MaskRay]

ELF/Relocations.cpp

721 ↗

(On Diff #218286)

I think the complexity is fine. I avoid making the size of symtab a factor in the time complexity. Doing mutation in the input is probably fine.

In a large executable, I get a long mangled name of N=4398 bytes.
O(74*N) is not too bad.

727 ↗

(On Diff #218286)

Thanks. This simplification is available since this is now a new function.

752 ↗

(On Diff #218286)

Will use correctSpelling

823 ↗

(On Diff #218286)

I'll use

for (auto it : enumerate(undefs))

[ruiu]

ELF/Relocations.cpp

721 ↗

(On Diff #218286)

Maybe you are right. A symbol that is 4398 bytes long is perhaps an outlier, but even for a 1000 byte long symbol, it is 74,000 hash table lookup, which may not too bad. Did you run this code against a long symbol name? If it doesn't feel sluggish, I'm fine.

[MaskRay]

ELF/Relocations.cpp

721 ↗

(On Diff #218286)

I tested linking a large executable. It took 19.8s in total.

For the long symbol (sym.getName().size() = 4379), if I patched getAlternativeSpelling to attempt all suggestions before returning, suggest was called 665682 times, and it took about 0.76s, a small portion of the whole link time.

(As a comparison, symVector.size() = 4195114.)

[thakis]

This is a cool idea, but I'm struggling to come up with a scenario where it's actually useful :)

For this to fire and be a true positive, you'd have to have an incorrect declaration but a correct definition of a function. I can't remember ever running into this – and the compiler seems to be in a better place to print a diagnostic for this case in almost all cases (except for if the TU with the correct definition doesn't happen to see the incorrect declaration).

[MaskRay]

In D67039#1655055, @thakis wrote:

This is a cool idea, but I'm struggling to come up with a scenario where it's actually useful :)

For this to fire and be a true positive, you'd have to have an incorrect declaration but a correct definition of a function. I can't remember ever running into this – and the compiler seems to be in a better place to print a diagnostic for this case in almost all cases (except for if the TU with the correct definition doesn't happen to see the incorrect declaration).

The file that provides the definition may have a mismatch of the declaration and the definition, e.g.

// a.h
void foo(int &a);

// a.cc
#include "a.h"
void foo(int a) {}

// b.cc
#include "a.h"
void bar(int a) { foo(a); }

% ld.lld a.o b.o            
ld.lld: error: undefined symbol: foo(int&)
>>> referenced by b.cc
>>>               b.o:(bar(int))
>>> did you mean: foo(int)
>>> defined in: a.o

[grimar]

It looks fine to me I think. I probably have no more comments except 2 nits below.

ELF/Relocations.cpp

700 ↗

(On Diff #218328)

I think LLD coding style requires curly bracers here, since you have more than one line under if.

823 ↗

(On Diff #218286)

I am not sure enumerate is better (it is not consistent and this approach uses auto), I'll leave it to others.

[grimar]

ELF/Relocations.cpp

823 ↗

(On Diff #218286)

(not consistent with the LLD code I meant. Which doesn't use it anywhere, preferring 'for')

[thakis]

For this to fire and be a true positive, you'd have to have an incorrect declaration but a correct definition of a function. I can't remember ever running into this – and the compiler seems to be in a better place to print a diagnostic for this case in almost all cases (except for if the TU with the correct definition doesn't happen to see the incorrect declaration).

The file that provides the definition may have a mismatch of the declaration and the definition, e.g.

Well, I guess we'll see how useful it turns out to be in practice :)

[ruiu]

LGTM

ELF/Relocations.cpp

718 ↗

(On Diff #218328)

I'd add a comment here to describe this loop. This loop creates all possible strings of edit distance 1 as typo correction candidates and see whether they exist or not.

721 ↗

(On Diff #218286)

I still have a little concern about the speed because 0.76s is not a negligible delay. When you get an undefined error, you are likely to be in a edit-compile-link cycle, and in the cycle you are likely to get an error message as soon as possible. That being said, 0.76s is probably a worst-case number, and if it becomes a problem, we may be able to improve this code, so I'm fine for now.

[MaskRay]

Add a comment associated with the loop

ELF/Relocations.cpp

721 ↗

(On Diff #218286)

The pessimistic case has a symbol of 4379 bytes long. I think the length of a typical mangled name is much smaller than 1000.

This is a failed attempt and it tries all suggestions. A successful attempt may take just half of the time.

This is an extremely large executable with 4195114 symbols. A typical application has much less.

The pessimistic 0.76s case assumes the worse case in every factor. For a typical application, I'd be surprised if the typo correction takes even 5% of the pessimistic 0.76s case, i.e 0.038s.

[RKSimon]

@MaskRay This is breaking buildbots: http://lab.llvm.org:8011/builders/llvm-clang-lld-x86_64-scei-ps4-ubuntu-fast/builds/54307/steps/test/logs/stdio

[MaskRay]

In D67039#1657122, @RKSimon wrote:

@MaskRay This is breaking buildbots: http://lab.llvm.org:8011/builders/llvm-clang-lld-x86_64-scei-ps4-ubuntu-fast/builds/54307/steps/test/logs/stdio

Fixed by rL370875

[RKSimon]

In D67039#1657156, @MaskRay wrote:

In D67039#1657122, @RKSimon wrote:

@MaskRay This is breaking buildbots: http://lab.llvm.org:8011/builders/llvm-clang-lld-x86_64-scei-ps4-ubuntu-fast/builds/54307/steps/test/logs/stdio

Fixed by rL370875

Thanks for the quick fix!

lld/trunk/ELF/Relocations.cpp

struct Loc {
     uint64_t offset;
   };
   std::vector<Loc> locs;
   bool isWarning;
 };
 
 static std::vector<UndefinedDiag> undefs;
 
+// Suggest an alternative spelling of an "undefined symbol" diagnostic. Returns
+// the suggested symbol, which is either in the symbol table, or in the same
+// file of sym.
+static const Symbol *getAlternativeSpelling(const Undefined &sym) {
+  // Build a map of local defined symbols.
+  DenseMap<StringRef, const Symbol *> map;
+  if (sym.file) {
+    for (const Symbol *s : sym.file->getSymbols())
+      if (s->isLocal() && s->isDefined())
+        map.try_emplace(s->getName(), s);
+  }
+
+  auto suggest = [&](StringRef newName) -> const Symbol * {
+    // If defined locally.
+    if (const Symbol *s = map.lookup(newName))
+      return s;
+
+    // If in the symbol table and not undefined.
+    if (const Symbol *s = symtab->find(newName))
+      if (!s->isUndefined())
+        return s;
+
+    return nullptr;
+  };
+
+  // This loop enumerates all strings of Levenshtein distance 1 as typo
+  // correction candidates and suggests the one that exists as a non-undefined
+  // symbol.
+  StringRef name = sym.getName();
+  for (size_t i = 0, e = name.size(); i != e + 1; ++i) {
+    // Insert a character before name[i].
+    std::string newName = (name.substr(0, i) + "0" + name.substr(i)).str();
+    for (char c = '0'; c <= 'z'; ++c) {
+      newName[i] = c;
+      if (const Symbol *s = suggest(newName))
+        return s;
+    }
+    if (i == e)
+      break;
+
+    // Substitute name[i].
+    newName = name;
+    for (char c = '0'; c <= 'z'; ++c) {
+      newName[i] = c;
+      if (const Symbol *s = suggest(newName))
+        return s;
+    }
+
+    // Transpose name[i] and name[i+1]. This is of edit distance 2 but it is
+    // common.
+    if (i + 1 < e) {
+      newName[i] = name[i + 1];
+      newName[i + 1] = name[i];
+      if (const Symbol *s = suggest(newName))
+        return s;
+    }
+
+    // Delete name[i].
+    newName = (name.substr(0, i) + name.substr(i + 1)).str();
+    if (const Symbol *s = suggest(newName))
+      return s;
+  }
+
+  return nullptr;
+}
+
 template <class ELFT>
-static void reportUndefinedSymbol(const UndefinedDiag &undef) {
+static void reportUndefinedSymbol(const UndefinedDiag &undef,
+                                  bool correctSpelling) {
   Symbol &sym = *undef.sym;
 
   auto visibility = [&]() -> std::string {
     switch (sym.visibility) {
     case STV_INTERNAL:
       return "internal ";
     case STV_HIDDEN:
       return "hidden ";
for (UndefinedDiag::Loc l : undef.locs) {
     msg += sec.getObjMsg(offset);
     i++;
   }
 
   if (i < undef.locs.size())
     msg += ("\n>>> referenced " + Twine(undef.locs.size() - i) + " more times")
                .str();
 
+  if (correctSpelling)
+    if (const Symbol *corrected =
+            getAlternativeSpelling(cast<Undefined>(sym))) {
+      msg += "\n>>> did you mean: " + toString(*corrected);
+      if (corrected->file)
+        msg += "\n>>> defined in: " + toString(corrected->file);
+    }
+
   if (sym.getName().startswith("_ZTV"))
     msg += "\nthe vtable symbol may be undefined because the class is missing "
            "its key function (see https://lld.llvm.org/missingkeyfunction)";
 
   if (undef.isWarning)
     warn(msg);
   else
     error(msg);
 }
 
 template <class ELFT> void elf::reportUndefinedSymbols() {
   // Find the first "undefined symbol" diagnostic for each diagnostic, and
   // collect all "referenced from" lines at the first diagnostic.
   DenseMap<Symbol *, UndefinedDiag *> firstRef;
   for (UndefinedDiag &undef : undefs) {
     assert(undef.locs.size() == 1);
     if (UndefinedDiag *canon = firstRef.lookup(undef.sym)) {
       canon->locs.push_back(undef.locs[0]);
       undef.locs.clear();
     } else
       firstRef[undef.sym] = &undef;
   }
 
-  for (const UndefinedDiag &undef : undefs) {
-    if (!undef.locs.empty())
-      reportUndefinedSymbol<ELFT>(undef);
-  }
+  // Enable spell corrector for the first 2 diagnostics.
+  for (auto it : enumerate(undefs))
+    if (!it.value().locs.empty())
+      reportUndefinedSymbol<ELFT>(it.value(), it.index() < 2);
   undefs.clear();
 }
 
 // Report an undefined symbol if necessary.
 // Returns true if the undefined symbol will produce an error message.
 static bool maybeReportUndefined(Symbol &sym, InputSectionBase &sec,
                                  uint64_t offset) {
   if (!sym.isUndefined() || sym.isWeak())

lld/trunk/test/ELF/undef-spell-corrector.s

+# REQUIRES: x86
+# RUN: llvm-mc -filetype=obj -triple=x86_64 %s -o %t.o
+
+## Insert a character.
+## The spell corrector is enabled for the first two "undefined symbol" diagnostics.
+# RUN: echo 'call bcde; call abcd; call abde' | llvm-mc -filetype=obj -triple=x86_64 - -o %t1.o
+# RUN: not ld.lld %t.o %t1.o -o /dev/null 2>&1 | FileCheck --check-prefix=INSERT %s -DFILE=%t.o
+
+## Symbols defined in DSO can be suggested.
+# RUN: ld.lld %t.o -shared -o %t.so
+# RUN: not ld.lld %t.so %t1.o -o /dev/null 2>&1 | FileCheck --check-prefix=INSERT %s -DFILE=%t.so
+
+# INSERT:      error: undefined symbol: bcde
+# INSERT-NEXT: >>> referenced by {{.*}}
+# INSERT-NEXT: >>> did you mean: abcde
+# INSERT-NEXT: >>> defined in: [[FILE]]
+# INSERT:      error: undefined symbol: abcd
+# INSERT-NEXT: >>> referenced by {{.*}}
+# INSERT-NEXT: >>> did you mean: abcde
+# INSERT-NEXT: >>> defined in: [[FILE]]
+# INSERT:      error: undefined symbol: abde
+# INSERT-NEXT: >>> referenced by {{.*}}
+# INSERT-NOT:  >>>
+
+## Substitute a character.
+# RUN: echo 'call bbcde; call abcdd' | llvm-mc -filetype=obj -triple=x86_64 - -o %t1.o
+# RUN: not ld.lld %t.o %t1.o -o /dev/null 2>&1 | FileCheck --check-prefix=SUBST %s
+
+# SUBST:      error: undefined symbol: bbcde
+# SUBST-NEXT: >>> referenced by {{.*}}
+# SUBST-NEXT: >>> did you mean: abcde
+# SUBST:      error: undefined symbol: abcdd
+# SUBST-NEXT: >>> referenced by {{.*}}
+# SUBST-NEXT: >>> did you mean: abcde
+
+## Delete a character.
+# RUN: echo 'call aabcde; call abcdee' | llvm-mc -filetype=obj -triple=x86_64 - -o %t1.o
+# RUN: not ld.lld %t.o %t1.o -o /dev/null 2>&1 | FileCheck --check-prefix=DELETE %s
+
+# DELETE:      error: undefined symbol: aabcde
+# DELETE-NEXT: >>> referenced by {{.*}}
+# DELETE-NEXT: >>> did you mean: abcde
+# DELETE:      error: undefined symbol: abcdee
+# DELETE-NEXT: >>> referenced by {{.*}}
+# DELETE-NEXT: >>> did you mean: abcde
+
+## Transpose.
+# RUN: echo 'call bacde' | llvm-mc -filetype=obj -triple=x86_64 - -o %t1.o
+# RUN: not ld.lld %t.o %t1.o -o /dev/null 2>&1 | FileCheck --check-prefix=TRANSPOSE %s
+
+# TRANSPOSE:      error: undefined symbol: bacde
+# TRANSPOSE-NEXT: >>> referenced by {{.*}}
+# TRANSPOSE-NEXT: >>> did you mean: abcde
+
+## Missing const qualifier.
+# RUN: echo 'call _Z3fooPi' | llvm-mc -filetype=obj -triple=x86_64 - -o %t1.o
+# RUN: not ld.lld %t.o %t1.o -o /dev/null 2>&1 | FileCheck --check-prefix=CONST %s
+## Local defined symbols.
+# RUN: echo '_Z3fooPKi: call _Z3fooPi' | llvm-mc -filetype=obj -triple=x86_64 - -o %t1.o
+# RUN: not ld.lld %t1.o -o /dev/null 2>&1 | FileCheck --check-prefix=CONST %s
+
+# CONST:      error: undefined symbol: foo(int*)
+# CONST-NEXT: >>> referenced by {{.*}}
+# CONST-NEXT: >>> did you mean: foo(int const*)
+
+.globl _start, abcde, _Z3fooPKi
+_start:
+abcde:
+_Z3fooPKi: