[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

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

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

721

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

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

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;

820

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

696

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

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

696

Will use correctSpelling

721

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

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

820

I'll use

for (auto it : enumerate(undefs))

[ruiu]

ELF/Relocations.cpp

721

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

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

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

820

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

820

(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

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

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

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!

ELF/Relocations.cpp

struct Loc {
     uint64_t offset;
   };
   std::vector<Loc> locs;
   bool isWarning;
 };
 
 static std::vector<UndefinedDiag> undefs;
 
 template <class ELFT>
-static void reportUndefinedSymbol(const UndefinedDiag &undef) {
+static void reportUndefinedSymbol(const UndefinedDiag &undef,
+                                  bool spellCorrector) {
   Symbol &sym = *undef.sym;
 
   auto visibility = [&]() -> std::string {
     switch (sym.visibility) {
     case STV_INTERNAL:
       return "internal ";
     case STV_HIDDEN:
       return "hidden ";
     case STV_PROTECTED:
       return "protected ";
     default:
       return "";
     }
   };
 
   std::string msg = maybeReportDiscarded<ELFT>(cast<Undefined>(sym));
   if (msg.empty())
     msg = "undefined " + visibility() + "symbol: " + toString(sym);
 
   const size_t maxUndefReferences = 10;
   size_t i = 0;
   for (UndefinedDiag::Loc l : undef.locs) {
     if (i >= maxUndefReferences)
       break;
     InputSectionBase &sec = *l.sec;
     uint64_t offset = l.offset;
 
     msg += "\n>>> referenced by ";
     std::string src = sec.getSrcMsg(sym, offset);
     if (!src.empty())
       msg += src + "\n>>>               ";
     msg += sec.getObjMsg(offset);
     i++;
   }
 
   if (i < undef.locs.size())
     msg += ("\n>>> referenced " + Twine(undef.locs.size() - i) + " more times")
                .str();
 
+  if (spellCorrector) {
+    // 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);
+
+    const Symbol *corrected = nullptr;
+    auto suggest = [&](StringRef newName) {
+      // Test if the name is defined locally.
+      const Symbol *s = map.lookup(newName);
+      if (s) {
+        corrected = s;
+        return true;
+      }
+
+      // Test if the name is in the symbol table.
+      s = symtab->find(newName);
+      if (s && !s->isUndefined()) {
+        corrected = s;
+        return true;
+      }
+      return false;
+    };
+
+    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 (suggest(newName))
+          break;
+      }
+      if (corrected || i == e)
+        break;
+
+      // Substitute name[i].
+      newName = name;
+      for (char c = '0'; c <= 'z'; ++c) {
+        newName[i] = c;
+        if (suggest(newName))
+          break;
+      }
+      if (corrected)
+        break;
+
+      // Delete name[i].
+      if (suggest((name.substr(0, i) + name.substr(i + 1)).str()))
+        break;
+    }
+
+    if (corrected) {
+      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);
+  size_t i = 0;
+  for (const UndefinedDiag &undef : undefs)
+    if (!undef.locs.empty()) {
+      // Enable spell corrector for the first 2 diagnostics.
+      reportUndefinedSymbol<ELFT>(undef, i < 2);
+      ++i;
     }
   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())

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
+
+# 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
+
+## 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: