[lld/mac] Port typo correction for undefined symbols from ELF port

[thakis]

Summary

Ports:

• core feature: https://reviews.llvm.org/D67039
• case mismatch: https://reviews.llvm.org/D70506
• extern "C" suggestions: https://reviews.llvm.org/D69592, https://reviews.llvm.org/D69650

Does not port https://reviews.llvm.org/D71735 since I believe that that doesn't
apply to lld/Mach-O.

I was a bit skeptical of the feature when it was initially added, but I think it's
proved itself in the ELF port.

[thakis]

make extern "C" suggestions actually work

need to account for the additional leading _ that darwin mangling inserts

[thakis]

rebase to try and make presubmit happy

[thakis]

reupload same diff without parent rev set in an attempt to unconfuse the precommit bot

[oontvoo]

Nice! LGTM
(it seems patch-application still failed - probably need sync'ing again?)

lld/MachO/SymbolTable.cpp

413

This function does some intensive works - is it worth caching the results?

(OTOTH, maybe performance isn't important in case of failures, anyways 🤔 )

[thakis]

Thanks!

Presubmit looks happier now that I removed the committed parent rev. Yesterday, when the parent wasn't committed yet, it was green too. Maybe a presubmit bug with landed parent revs.

lld/MachO/SymbolTable.cpp

413

We only call it once per undefined symbol, so a cache would have a very low hit rate i think (?). We only call this for the first 2 undefined symbols for perf reasons too. So even for fairly long symbol names, this should add less than 100k symbol lookups (which is not nothing! But it only happens on failing links, and it's still small compared to total number of lookups during a link)

[int3]

I was wondering if we could have more code sharing with the ELF port, or if it's too messy to be worth the effort of refactoring

[thakis]

In D135038#3832164, @int3 wrote:

I was wondering if we could have more code sharing with the ELF port, or if it's too messy to be worth the effort of refactoring

Some things could be shared if we wanted, but there's also a bunch of differences (some silly, like it being sym.file in ELF vs sym.getFile() in MachO and file->getSymbols() in ELF vs file->symbols in MachO, or there not being an isUndefined() in MachO; some more structural, such as MachO having to deal with the extra _ prefix). The code that generates all the candidates is pretty similar, but if we share it we make it harder to change the symtab impl of each port. I thought duplicating it is nicer, but *shrug*. Happy to change concrete things if you have something concrete that you feel would be better.

[int3]

Nah that's fair enough

[MaskRay]

I agree that code duplication is better engineering if consider object file format differences and updating convenience.

[hans]

Developers are reporting crashes/asserts from this change: http://crbug.com/1372389
I'll back it out for now until it can be fixed.

[dblaikie]

(FWIW, my 2c & this dates back to the founding of the 'new' (now not-so-new) lld - that the code duplication between ports is pretty unfortunate & while it does give some agility to the ports to work differently because they are different - it also means code diverges, bugfixes get made in one port and not shared by others - all the usual reasons code duplication is problematic & that LLVM as a whole has been founded on reusable library abstractions that have been quite effective/beneficial overall - I'd love to see even small parts of lld start to be abstracted into common helpers even with some trait adapters to handle the trivial differences in naming and/or some pressure to make the naming consistent and keep it that way at least in subsets of the API (eg: enough to make this work as a template) - but you folks can take this for whatever it's worth/weigh it against all your other goals/needs)

[thakis]

In D135038#3848082, @dblaikie wrote:

(FWIW, my 2c & this dates back to the founding of the 'new' (now not-so-new) lld - that the code duplication between ports is pretty unfortunate & while it does give some agility

Not sure if this is the right forum to re-litigate this :) I'm sure you're aware of the history: The original lld used a design like this and didn't go anywhere. The new lld uses this somewhat uncommon approach, and it's led to lld becoming the fastest production quality linker that can target COFF, ELF, and MachO. Abstractly I kind of agree with you, but you also can't argue too much with the impact the current approach had.

[thakis]

Unrelatedly, I relanded the patch, and I made D135889 that has a test for the crash. (It depends on D135888, so I didn't include it in the reland directly, to make the reland almost identical to the original commit.)

[tschuett]

In D135038#3855955, @thakis wrote:

In D135038#3848082, @dblaikie wrote:

(FWIW, my 2c & this dates back to the founding of the 'new' (now not-so-new) lld - that the code duplication between ports is pretty unfortunate & while it does give some agility

Not sure if this is the right forum to re-litigate this :) I'm sure you're aware of the history: The original lld used a design like this and didn't go anywhere. The new lld uses this somewhat uncommon approach, and it's led to lld becoming the fastest production quality linker that can target COFF, ELF, and MachO. Abstractly I kind of agree with you, but you also can't argue too much with the impact the current approach had.

mold might disagree about speed.

[thakis]

mold might disagree about speed.

mold is great, but it doesn't have a COFF port yet and I think it's seen little production use for its MachO port so far. (mold uses the same internal design as lld – distinct code for ELF and MachO, so I think bringing it up doesn't add anything to the discussion here – but as I said I also think it's not terribly useful to have this discussion again on this random review.)

[dblaikie]

In D135038#3855955, @thakis wrote:

In D135038#3848082, @dblaikie wrote:

(FWIW, my 2c & this dates back to the founding of the 'new' (now not-so-new) lld - that the code duplication between ports is pretty unfortunate & while it does give some agility

Not sure if this is the right forum to re-litigate this :) I'm sure you're aware of the history: The original lld used a design like this and didn't go anywhere. The new lld uses this somewhat uncommon approach, and it's led to lld becoming the fastest production quality linker that can target COFF, ELF, and MachO. Abstractly I kind of agree with you, but you also can't argue too much with the impact the current approach had.

One of the arguments made early on was that unlibrary-ification would be necessary for early velocity (not one I agree with, but that's how it went) & that library-ification could occur once development was over that hump/had got concrete results. Given that lld's been proved out and is a production linker, I think now's a good time to start considering looking for commonality and migrating towards more common infrastructure and library-like design.

[thakis]

One of the arguments made early on was that unlibrary-ification would be necessary for early velocity (not one I agree with, but that's how it went) & that library-ification could occur once development was over that hump/had got concrete results. Given that lld's been proved out and is a production linker, I think now's a good time to start considering looking for commonality and migrating towards more common infrastructure and library-like design.

I'm somewhat familiar with three of the ports, and I think there isn't a lot of commonality really.

[dblaikie]

In D135038#3858367, @thakis wrote:

One of the arguments made early on was that unlibrary-ification would be necessary for early velocity (not one I agree with, but that's how it went) & that library-ification could occur once development was over that hump/had got concrete results. Given that lld's been proved out and is a production linker, I think now's a good time to start considering looking for commonality and migrating towards more common infrastructure and library-like design.

I'm somewhat familiar with three of the ports, and I think there isn't a lot of commonality really.

Fair enough - this seemed like a place that was relatively close enough to consider, judging by the description/purpose of the code, etc. Ah well.

lld/MachO/SymbolTable.cpp

if (!config->deadStripDuplicates || duplicate.sym->isLive()) {
       message += duplicate.src1.second + "\n>>> defined in ";
       if (!duplicate.src2.first.empty())
         message += duplicate.src2.first + "\n>>>            ";
       error(message + duplicate.src2.second);
     }
   }
 }
 
+// Check whether the definition name def is a mangled function name that matches
+// the reference name ref.
+static bool canSuggestExternCForCXX(StringRef ref, StringRef def) {
+  llvm::ItaniumPartialDemangler d;
+  std::string name = def.str();
+  if (d.partialDemangle(name.c_str()))
+    return false;
+  char *buf = d.getFunctionName(nullptr, nullptr);
+  if (!buf)
+    return false;
+  bool ret = ref == buf;
+  free(buf);
+  return ret;
+}
+
+// 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,
+                                            std::string &pre_hint,
+                                            std::string &post_hint) {
+  DenseMap<StringRef, const Symbol *> map;
+  if (sym.getFile() && sym.getFile()->kind() == InputFile::ObjKind) {
+    // Build a map of local defined symbols.
+    for (const Symbol *s : sym.getFile()->symbols)
+      if (auto *defined = dyn_cast<Defined>(s))
+        if (!defined->isExternal())
+          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 (dyn_cast<Undefined>(s) == nullptr)
+        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 = std::string(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;
+  }
+
+  // Case mismatch, e.g. Foo vs FOO.
+  for (auto &it : map)
+    if (name.equals_insensitive(it.first))
+      return it.second;
+  for (Symbol *sym : symtab->getSymbols())
+    if (dyn_cast<Undefined>(sym) == nullptr &&
+        name.equals_insensitive(sym->getName()))
+      return sym;
+
+  // The reference may be a mangled name while the definition is not. Suggest a
+  // missing extern "C".
+  if (name.startswith("__Z")) {
+    std::string buf = name.str();
+    llvm::ItaniumPartialDemangler d;
+    if (!d.partialDemangle(buf.c_str()))
+      if (char *buf = d.getFunctionName(nullptr, nullptr)) {
+        const Symbol *s = suggest((Twine("_") + buf).str());
+        free(buf);
+        if (s) {
+          pre_hint = ": extern \"C\" ";
+          return s;
+        }
+      }
+  } else {
+    StringRef name_without_underscore = name;
+    name_without_underscore.consume_front("_");
+    const Symbol *s = nullptr;
+    for (auto &it : map)
+      if (canSuggestExternCForCXX(name_without_underscore, it.first)) {
+        s = it.second;
+        break;
+      }
+    if (!s)
+      for (Symbol *sym : symtab->getSymbols())
+        if (canSuggestExternCForCXX(name_without_underscore, sym->getName())) {
+          s = sym;
+          break;
+        }
+    if (s) {
+      pre_hint = " to declare ";
+      post_hint = " as extern \"C\"?";
+      return s;
+    }
+  }
+
+  return nullptr;
+}
+
 static void reportUndefinedSymbol(const Undefined &sym,
-                                  const UndefinedDiag &locations) {
+                                  const UndefinedDiag &locations,
+                                  bool correctSpelling) {
   std::string message = "undefined symbol";
   if (config->archMultiple)
     message += (" for arch " + getArchitectureName(config->arch())).str();
   message += ": " + toString(sym);
 
   const size_t maxUndefinedReferences = 3;
   size_t i = 0;
   for (const std::string &loc : locations.otherReferences) {
static void reportUndefinedSymbol(const Undefined &sym,
 
   size_t totalReferences =
       locations.otherReferences.size() + locations.codeReferences.size();
   if (totalReferences > i)
     message +=
         ("\n>>> referenced " + Twine(totalReferences - i) + " more times")
             .str();
 
+  if (correctSpelling) {
+    std::string pre_hint = ": ", post_hint;
+    if (const Symbol *corrected =
+            getAlternativeSpelling(sym, pre_hint, post_hint)) {
+      message +=
+          "\n>>> did you mean" + pre_hint + toString(*corrected) + post_hint;
+      if (corrected->getFile())
+        message += "\n>>> defined in: " + toString(corrected->getFile());
+    }
+  }
+
   if (config->undefinedSymbolTreatment == UndefinedSymbolTreatment::error)
     error(message);
   else if (config->undefinedSymbolTreatment ==
            UndefinedSymbolTreatment::warning)
     warn(message);
   else
     assert(false && "diagnostics make sense for -undefined error|warning only");
 }
 
 void macho::reportPendingUndefinedSymbols() {
-  for (const auto &undef : undefs)
-    reportUndefinedSymbol(*undef.first, undef.second);
+  // Enable spell corrector for the first 2 diagnostics.
+  for (const auto &[i, undef] : llvm::enumerate(undefs))
+    reportUndefinedSymbol(*undef.first, undef.second, i < 2);
 
   // This function is called multiple times during execution. Clear the printed
   // diagnostics to avoid printing the same things again the next time.
   undefs.clear();
 }
 
 void macho::treatUndefinedSymbol(const Undefined &sym, StringRef source) {
   if (recoverFromUndefinedSymbol(sym))

lld/test/MachO/undef-spell-corrector.s

+# REQUIRES: x86
+# RUN: llvm-mc -filetype=obj -triple=x86_64-apple-macos %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-apple-macos - -o %t1.o
+# RUN: not %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: %lld %t.o -dylib -o %t.dylib
+# RUN: not %lld %t.dylib %t1.o -o /dev/null 2>&1 | FileCheck --check-prefix=INSERT %s -DFILE=%t.dylib
+
+# INSERT:      error: undefined symbol: abde
+# 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: bcde
+# INSERT-NEXT: >>> referenced by {{.*}}
+# INSERT-NOT:  >>>
+
+## Substitute a character.
+# RUN: echo 'call bbcde; call abcdd' | llvm-mc -filetype=obj -triple=x86_64-apple-macos - -o %t1.o
+# RUN: not %lld %t.o %t1.o -o /dev/null 2>&1 | FileCheck --check-prefix=SUBST %s
+
+# SUBST:      error: undefined symbol: abcdd
+# SUBST-NEXT: >>> referenced by {{.*}}
+# SUBST-NEXT: >>> did you mean: abcde
+# SUBST:      error: undefined symbol: bbcde
+# 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-apple-macos - -o %t1.o
+# RUN: not %lld %t.o %t1.o -o /dev/null 2>&1 | FileCheck --check-prefix=DELETE %s
+
+# DELETE:      error: undefined symbol: abcdee
+# DELETE-NEXT: >>> referenced by {{.*}}
+# DELETE-NEXT: >>> did you mean: abcde
+# DELETE:      error: undefined symbol: aabcde
+# DELETE-NEXT: >>> referenced by {{.*}}
+# DELETE-NEXT: >>> did you mean: abcde
+
+## Transpose.
+# RUN: echo 'call bacde' | llvm-mc -filetype=obj -triple=x86_64-apple-macos - -o %t1.o
+# RUN: not %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-apple-macos - -o %t1.o
+# RUN: not %lld %t.o %t1.o -demangle -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-apple-macos - -o %t1.o
+# RUN: not %lld %t1.o -demangle -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*)
+
+## Case mismatch.
+# RUN: echo 'call __Z3FOOPKi' | llvm-mc -filetype=obj -triple=x86_64-apple-macos - -o %t1.o
+# RUN: not %lld %t.o %t1.o -demangle -o /dev/null 2>&1 | FileCheck --check-prefix=CASE %s
+# RUN: echo '__Z3fooPKi: call __Z3FOOPKi' | llvm-mc -filetype=obj -triple=x86_64-apple-macos - -o %t1.o
+# RUN: not %lld %t1.o -demangle -o /dev/null 2>&1 | FileCheck --check-prefix=CASE %s
+
+# CASE:      error: undefined symbol: FOO(int const*)
+# CASE-NEXT: >>> referenced by {{.*}}
+# CASE-NEXT: >>> did you mean: foo(int const*)
+
+.globl _main, abcde, __Z3fooPKi
+_main:
+abcde:
+__Z3fooPKi:

lld/test/MachO/undef-suggest-extern-c.s

+# REQUIRES: x86
+# RUN: llvm-mc -filetype=obj -triple=x86_64-apple-macos %s -o %t.o
+
+## The reference is mangled while the definition is not, suggest a missing
+## extern "C".
+# RUN: echo 'call __Z3fooi' | llvm-mc -filetype=obj -triple=x86_64-apple-macos - -o %t1.o
+# RUN: not %lld %t.o %t1.o -demangle -o /dev/null 2>&1 | FileCheck %s
+
+# CHECK:      error: undefined symbol: foo(int)
+# CHECK-NEXT: >>> referenced by {{.*}}
+# CHECK-NEXT: >>> did you mean: extern "C" _foo
+
+## Don't suggest for nested names like F::foo() and foo::foo().
+# RUN: echo 'call __ZN1F3fooEv; call __ZN3fooC1Ev' | llvm-mc -filetype=obj -triple=x86_64-apple-macos - -o %t2.o
+# RUN: not ld.lld %t.o %t2.o -o /dev/null 2>&1 | FileCheck /dev/null --implicit-check-not='did you mean'
+
+.globl _start, _foo
+_start:
+_foo:

lld/test/MachO/undef-suggest-extern-c2.s

+# REQUIRES: x86
+# RUN: llvm-mc -filetype=obj -triple=x86_64-apple-macos %s -o %t.o
+
+## The definition is mangled while the reference is not, suggest an arbitrary
+## C++ overload.
+# RUN: echo '.globl __Z3fooi; __Z3fooi:' | llvm-mc -filetype=obj -triple=x86_64-apple-macos - -o %t1.o
+# RUN: not %lld %t.o %t1.o -demangle -o /dev/null 2>&1 | FileCheck %s
+
+## Check that we can suggest a local definition.
+# RUN: echo '__Z3fooi: call _foo' | llvm-mc -filetype=obj -triple=x86_64-apple-macos - -o %t2.o
+# RUN: not %lld %t2.o -demangle -o /dev/null 2>&1 | FileCheck %s
+
+# CHECK:      error: undefined symbol: _foo
+# CHECK-NEXT: >>> referenced by {{.*}}
+# CHECK-NEXT: >>> did you mean to declare foo(int) as extern "C"?
+
+## Don't suggest nested names whose base name is "foo", e.g. F::foo().
+# RUN: echo '.globl __ZN1F3fooEv; __ZN1F3fooEv:' | llvm-mc -filetype=obj -triple=x86_64-apple-macos - -o %t3.o
+# RUN: not %lld %t.o %t3.o -o /dev/null 2>&1 | FileCheck /dev/null --implicit-check-not='did you mean'
+
+call _foo