Move code for symbol resolution from SymbolTable.cpp to Symbols.cpp.

[ruiu]

Summary

My recent commits separated symbol resolution from the symbol table,
so the functions to resolve symbols are now in a somewhat wrong file.
This patch moves it to Symbols.cpp.

The functions are now member functions of the symbol.

This is code move change. I modified function names so that they are
appropriate as member functions, though. No functionality change
intended.

[grimar]

LGTM

ELF/Driver.cpp

static void handleUndefined(StringRef Name) {
   if (!Sym)
     return;
 
   // Since symbol S may not be used inside the program, LTO may
   // eliminate it. Mark the symbol as "used" to prevent it.
   Sym->IsUsedInRegularObj = true;
 
   if (Sym->isLazy())
-    Symtab->fetchLazy(Sym);
+    Sym->fetch();
 }
 
 static void handleLibcall(StringRef Name) {
   Symbol *Sym = Symtab->find(Name);
   if (!Sym || !Sym->isLazy())
     return;
 
   MemoryBufferRef MB;
   if (auto *LO = dyn_cast<LazyObject>(Sym))
     MB = LO->File->MB;
   else
     MB = cast<LazyArchive>(Sym)->getMemberBuffer();
 
   if (isBitcode(MB))
-    Symtab->fetchLazy(Sym);
+    Sym->fetch();
 }
 
 // Replaces common symbols with defined symbols reside in .bss sections.
 // This function is called after all symbol names are resolved. As a
 // result, the passes after the symbol resolution won't see any
 // symbols of type CommonSymbol.
 static void replaceCommonSymbols() {
   for (Symbol *Sym : Symtab->getSymbols()) {

ELF/InputFiles.cpp

if (Binding == STB_LOCAL) {
       else
         this->Symbols[I] =
             make<Defined>(this, Name, Binding, StOther, Type, Value, Size, Sec);
       continue;
     }
 
     // Handle global undefined symbols.
     if (ESym.st_shndx == SHN_UNDEF) {
-      resolveSymbol(this->Symbols[I],
-                    Undefined{this, Name, Binding, StOther, Type});
+      this->Symbols[I]->resolve(Undefined{this, Name, Binding, StOther, Type});
       continue;
     }
 
     // Handle global common symbols.
     if (ESym.st_shndx == SHN_COMMON) {
       if (Value == 0 || Value >= UINT32_MAX)
         fatal(toString(this) + ": common symbol '" + StringRef(Name.Data) +
               "' has invalid alignment: " + Twine(Value));
-      resolveSymbol(this->Symbols[I], CommonSymbol{this, Name, Binding, StOther,
-                                                   Type, Value, Size});
+      this->Symbols[I]->resolve(
+          CommonSymbol{this, Name, Binding, StOther, Type, Value, Size});
       continue;
     }
 
     // If a defined symbol is in a discarded section, handle it as if it
     // were an undefined symbol. Such symbol doesn't comply with the
     // standard, but in practice, a .eh_frame often directly refer
     // COMDAT member sections, and if a comdat group is discarded, some
     // defined symbol in a .eh_frame becomes dangling symbols.
     if (Sec == &InputSection::Discarded) {
-      resolveSymbol(this->Symbols[I],
-                    Undefined{this, Name, Binding, StOther, Type, SecIdx});
+      this->Symbols[I]->resolve(
       continue;
     }
 
     // Handle global defined symbols.
     if (Binding == STB_GLOBAL || Binding == STB_WEAK ||
         Binding == STB_GNU_UNIQUE) {
-      resolveSymbol(this->Symbols[I], Defined{this, Name, Binding, StOther,
-                                              Type, Value, Size, Sec});
+      this->Symbols[I]->resolve(
+          Defined{this, Name, Binding, StOther, Type, Value, Size, Sec});
       continue;
     }
 
     fatal(toString(this) + ": unexpected binding: " + Twine((int)Binding));
   }
 }
 
 ArchiveFile::ArchiveFile(std::unique_ptr<Archive> &&File)
for (const typename ELFT::Shdr &Sec : Sections) {
 
     // Get existing symbols or insert placeholder symbols.
     for (size_t I = FirstGlobal, End = ESyms.size(); I != End; ++I)
       if (ESyms[I].st_shndx != SHN_UNDEF)
         this->Symbols[I] = Symtab->insert(CHECK(ESyms[I].getName(Strtab), this));
 
     // Replace existing symbols with LazyObject symbols.
     //
-    // resolveSymbol() may trigger this->fetch() if an existing symbol
-    // is an undefined symbol. If that happens, this LazyObjFile has
-    // served its purpose, and we can exit from the loop early.
+    // resolve() may trigger this->fetch() if an existing symbol is an
+    // undefined symbol. If that happens, this LazyObjFile has served
+    // its purpose, and we can exit from the loop early.
     for (Symbol *Sym : this->Symbols) {
       if (!Sym)
         continue;
-      resolveSymbol(Sym, LazyObject{*this, Sym->getName()});
+      Sym->resolve(LazyObject{*this, Sym->getName()});
       if (AddedToLink)
         return;
     }
     return;
   }
 }
 
 std::string elf::replaceThinLTOSuffix(StringRef Path) {

ELF/LinkerScript.cpp

void LinkerScript::addSymbol(SymbolAssignment *Cmd) {
   // use symbols as variables in linker scripts. Doing so allows us to
   // write expressions like this: `alignment = 16; . = ALIGN(., alignment)`.
   uint64_t SymValue = Value.Sec ? 0 : Value.getValue();
 
   Defined New(nullptr, Cmd->Name, STB_GLOBAL, Visibility, STT_NOTYPE, SymValue,
               0, Sec);
 
   Symbol *Sym = Symtab->insert(Cmd->Name);
-  mergeSymbolProperties(Sym, New);
+  Sym->mergeProperties(New);
   Sym->replace(New);
   Cmd->Sym = cast<Defined>(Sym);
 }
 
 // This function is called from LinkerScript::declareSymbols.
 // It creates a placeholder symbol if needed.
 static void declareSymbol(SymbolAssignment *Cmd) {
   if (!shouldDefineSym(Cmd))
     return;
 
   uint8_t Visibility = Cmd->Hidden ? STV_HIDDEN : STV_DEFAULT;
   Defined New(nullptr, Cmd->Name, STB_GLOBAL, Visibility, STT_NOTYPE, 0, 0,
               nullptr);
 
   // We can't calculate final value right now.
   Symbol *Sym = Symtab->insert(Cmd->Name);
-  mergeSymbolProperties(Sym, New);
+  Sym->mergeProperties(New);
   Sym->replace(New);
 
   Cmd->Sym = cast<Defined>(Sym);
   Cmd->Provide = false;
   Sym->ScriptDefined = true;
 }
 
 // This method is used to handle INSERT AFTER statement. Here we rebuild

ELF/SymbolTable.h

public:
   void wrap(Symbol *Sym, Symbol *Real, Symbol *Wrap);
 
   ArrayRef<Symbol *> getSymbols() const { return SymVector; }
 
   Symbol *insert(StringRef Name);
 
   Symbol *addSymbol(const Symbol &New);
 
-  void fetchLazy(Symbol *Sym);
-
   void scanVersionScript();
 
   Symbol *find(StringRef Name);
 
   void trace(StringRef Name);
 
   void handleDynamicList();
 
private:
   // This mapping is 1:N because two symbols with different versions
   // can have the same name. We use this map to handle "extern C++ {}"
   // directive in version scripts.
   llvm::Optional<llvm::StringMap<std::vector<Symbol *>>> DemangledSyms;
 };
 
 extern SymbolTable *Symtab;
 
-void mergeSymbolProperties(Symbol *Old, const Symbol &New);
-void resolveSymbol(Symbol *Old, const Symbol &New);
-
 } // namespace elf
 } // namespace lld
 
 #endif

ELF/SymbolTable.cpp

void SymbolTable::wrap(Symbol *Sym, Symbol *Real, Symbol *Wrap) {
   // Now renaming is complete. No one refers Real symbol. We could leave
   // Real as-is, but if Real is written to the symbol table, that may
   // contain irrelevant values. So, we copy all values from Sym to Real.
   StringRef S = Real->getName();
   memcpy(Real, Sym, sizeof(SymbolUnion));
   Real->setName(S);
 }
 
-static uint8_t getMinVisibility(uint8_t VA, uint8_t VB) {
-  if (VA == STV_DEFAULT)
-    return VB;
-  if (VB == STV_DEFAULT)
-    return VA;
-  return std::min(VA, VB);
-}
-
 // Find an existing symbol or create a new one.
 Symbol *SymbolTable::insert(StringRef Name) {
   // <name>@@<version> means the symbol is the default version. In that
   // case <name>@@<version> will be used to resolve references to <name>.
   //
   // Since this is a hot path, the following string search code is
   // optimized for speed. StringRef::find(char) is much faster than
   // StringRef::find(StringRef).
Symbol *SymbolTable::insert(StringRef Name) {
   Sym->ExportDynamic = false;
   Sym->CanInline = true;
   Sym->Traced = Traced;
   Sym->ScriptDefined = false;
   return Sym;
 }
 
 Symbol *SymbolTable::addSymbol(const Symbol &New) {
-  Symbol *Old = Symtab->insert(New.getName());
-  resolveSymbol(Old, New);
-  return Old;
-}
-
-static void addUndefined(Symbol *Old, const Undefined &New) {
-  // An undefined symbol with non default visibility must be satisfied
-  // in the same DSO.
-  //
-  // If this is a non-weak defined symbol in a discarded section, override the
-  // existing undefined symbol for better error message later.
-  if ((Old->isShared() && New.Visibility != STV_DEFAULT) ||
-      (Old->isUndefined() && New.Binding != STB_WEAK && New.DiscardedSecIdx)) {
-    Old->replace(New);
-    return;
-  }
-
-  if (Old->isShared() || Old->isLazy() ||
-      (Old->isUndefined() && New.Binding != STB_WEAK))
-    Old->Binding = New.Binding;
-
-  if (Old->isLazy()) {
-    // An undefined weak will not fetch archive members. See comment on Lazy in
-    // Symbols.h for the details.
-    if (New.Binding == STB_WEAK) {
-      Old->Type = New.Type;
-      return;
-    }
-
-    // Do extra check for --warn-backrefs.
-    //
-    // --warn-backrefs is an option to prevent an undefined reference from
-    // fetching an archive member written earlier in the command line. It can be
-    // used to keep compatibility with GNU linkers to some degree.
-    // I'll explain the feature and why you may find it useful in this comment.
-    //
-    // lld's symbol resolution semantics is more relaxed than traditional Unix
-    // linkers. For example,
-    //
-    //   ld.lld foo.a bar.o
-    //
-    // succeeds even if bar.o contains an undefined symbol that has to be
-    // resolved by some object file in foo.a. Traditional Unix linkers don't
-    // allow this kind of backward reference, as they visit each file only once
-    // from left to right in the command line while resolving all undefined
-    // symbols at the moment of visiting.
-    //
-    // In the above case, since there's no undefined symbol when a linker visits
-    // foo.a, no files are pulled out from foo.a, and because the linker forgets
-    // about foo.a after visiting, it can't resolve undefined symbols in bar.o
-    // that could have been resolved otherwise.
-    //
-    // That lld accepts more relaxed form means that (besides it'd make more
-    // sense) you can accidentally write a command line or a build file that
-    // works only with lld, even if you have a plan to distribute it to wider
-    // users who may be using GNU linkers. With --warn-backrefs, you can detect
-    // a library order that doesn't work with other Unix linkers.
-    //
-    // The option is also useful to detect cyclic dependencies between static
-    // archives. Again, lld accepts
-    //
-    //   ld.lld foo.a bar.a
-    //
-    // even if foo.a and bar.a depend on each other. With --warn-backrefs, it is
-    // handled as an error.
-    //
-    // Here is how the option works. We assign a group ID to each file. A file
-    // with a smaller group ID can pull out object files from an archive file
-    // with an equal or greater group ID. Otherwise, it is a reverse dependency
-    // and an error.
-    //
-    // A file outside --{start,end}-group gets a fresh ID when instantiated. All
-    // files within the same --{start,end}-group get the same group ID. E.g.
-    //
-    //   ld.lld A B --start-group C D --end-group E
-    //
-    // A forms group 0. B form group 1. C and D (including their member object
-    // files) form group 2. E forms group 3. I think that you can see how this
-    // group assignment rule simulates the traditional linker's semantics.
-    bool Backref = Config->WarnBackrefs && New.File &&
-                   Old->File->GroupId < New.File->GroupId;
-    Symtab->fetchLazy(Old);
-
-    // We don't report backward references to weak symbols as they can be
-    // overridden later.
-    if (Backref && !Old->isWeak())
-      warn("backward reference detected: " + New.getName() + " in " +
-           toString(New.File) + " refers to " + toString(Old->File));
-  }
-}
-
-// Using .symver foo,foo@@VER unfortunately creates two symbols: foo and
-// foo@@VER. We want to effectively ignore foo, so give precedence to
-// foo@@VER.
-// FIXME: If users can transition to using
-// .symver foo,foo@@@VER
-// we can delete this hack.
-static int compareVersion(StringRef OldName, StringRef NewName) {
-  bool A = OldName.contains("@@");
-  bool B = NewName.contains("@@");
-  if (!A && B)
-    return 1;
-  if (A && !B)
-    return -1;
-  return 0;
-}
-
-// Compare two symbols. Return 1 if the new symbol should win, -1 if
-// the new symbol should lose, or 0 if there is a conflict.
-static int compare(const Symbol *Old, const Symbol *New) {
-  assert(New->isDefined() || New->isCommon());
-
-  if (!Old->isDefined() && !Old->isCommon())
-    return 1;
-
-  if (int Cmp = compareVersion(Old->getName(), New->getName()))
-    return Cmp;
-
-  if (New->isWeak())
-    return -1;
-
-  if (Old->isWeak())
-    return 1;
-
-  if (Old->isCommon() && New->isCommon()) {
-    if (Config->WarnCommon)
-      warn("multiple common of " + Old->getName());
-    return 0;
-  }
-
-  if (Old->isCommon()) {
-    if (Config->WarnCommon)
-      warn("common " + Old->getName() + " is overridden");
-    return 1;
-  }
-
-  if (New->isCommon()) {
-    if (Config->WarnCommon)
-      warn("common " + Old->getName() + " is overridden");
-    return -1;
-  }
-
-  auto *OldSym = cast<Defined>(Old);
-  auto *NewSym = cast<Defined>(New);
-
-  if (New->File && isa<BitcodeFile>(New->File))
-    return 0;
-
-  if (!OldSym->Section && !NewSym->Section && OldSym->Value == NewSym->Value &&
-      NewSym->Binding == STB_GLOBAL)
-    return -1;
-
-  return 0;
-}
-
-static void addCommon(Symbol *Old, const CommonSymbol &New) {
-  int Cmp = compare(Old, &New);
-  if (Cmp < 0)
-    return;
-
-  if (Cmp > 0) {
-    Old->replace(New);
-    return;
-  }
-
-  CommonSymbol *OldSym = cast<CommonSymbol>(Old);
-
-  OldSym->Alignment = std::max(OldSym->Alignment, New.Alignment);
-  if (OldSym->Size < New.Size) {
-    OldSym->File = New.File;
-    OldSym->Size = New.Size;
-  }
-}
-
-static void reportDuplicate(Symbol *Sym, InputFile *NewFile,
-                            InputSectionBase *ErrSec, uint64_t ErrOffset) {
-  if (Config->AllowMultipleDefinition)
-    return;
-
-  Defined *D = cast<Defined>(Sym);
-  if (!D->Section || !ErrSec) {
-    error("duplicate symbol: " + toString(*Sym) + "\n>>> defined in " +
-          toString(Sym->File) + "\n>>> defined in " + toString(NewFile));
-    return;
-  }
-
-  // Construct and print an error message in the form of:
-  //
-  //   ld.lld: error: duplicate symbol: foo
-  //   >>> defined at bar.c:30
-  //   >>>            bar.o (/home/alice/src/bar.o)
-  //   >>> defined at baz.c:563
-  //   >>>            baz.o in archive libbaz.a
-  auto *Sec1 = cast<InputSectionBase>(D->Section);
-  std::string Src1 = Sec1->getSrcMsg(*Sym, D->Value);
-  std::string Obj1 = Sec1->getObjMsg(D->Value);
-  std::string Src2 = ErrSec->getSrcMsg(*Sym, ErrOffset);
-  std::string Obj2 = ErrSec->getObjMsg(ErrOffset);
-
-  std::string Msg = "duplicate symbol: " + toString(*Sym) + "\n>>> defined at ";
-  if (!Src1.empty())
-    Msg += Src1 + "\n>>>            ";
-  Msg += Obj1 + "\n>>> defined at ";
-  if (!Src2.empty())
-    Msg += Src2 + "\n>>>            ";
-  Msg += Obj2;
-  error(Msg);
-}
-
-static void addDefined(Symbol *Old, const Defined &New) {
-  int Cmp = compare(Old, &New);
-  if (Cmp > 0)
-    Old->replace(New);
-  else if (Cmp == 0)
-    reportDuplicate(Old, New.File,
-                    dyn_cast_or_null<InputSectionBase>(New.Section), New.Value);
-}
-
-static void addShared(Symbol *Old, const SharedSymbol &New) {
-  if (Old->Visibility == STV_DEFAULT && (Old->isUndefined() || Old->isLazy())) {
-    // An undefined symbol with non default visibility must be satisfied
-    // in the same DSO.
-    uint8_t Binding = Old->Binding;
-    Old->replace(New);
-    Old->Binding = Binding;
-  }
+  Symbol *Sym = Symtab->insert(New.getName());
+  Sym->resolve(New);
+  return Sym;
 }
 
 Symbol *SymbolTable::find(StringRef Name) {
   auto It = SymMap.find(CachedHashStringRef(Name));
   if (It == SymMap.end())
     return nullptr;
   if (It->second == -1)
     return nullptr;
   return SymVector[It->second];
 }
 
-template <class LazyT> static void addLazy(Symbol *Old, const LazyT &New) {
-  if (!Old->isUndefined())
-    return;
-
-  // An undefined weak will not fetch archive members. See comment on Lazy in
-  // Symbols.h for the details.
-  if (Old->isWeak()) {
-    uint8_t Type = Old->Type;
-    Old->replace(New);
-    Old->Type = Type;
-    Old->Binding = STB_WEAK;
-    return;
-  }
-
-  if (InputFile *F = New.fetch())
-    parseFile(F);
-}
-
-static void addLazyArchive(Symbol *Old, const LazyArchive &New) {
-  addLazy(Old, New);
-}
-
-static void addLazyObject(Symbol *Old, const LazyObject &New) {
-  addLazy(Old, New);
-}
-
-void SymbolTable::fetchLazy(Symbol *Sym) {
-  if (auto *S = dyn_cast<LazyArchive>(Sym)) {
-    if (InputFile *File = S->fetch())
-      parseFile(File);
-    return;
-  }
-
-  auto *S = cast<LazyObject>(Sym);
-  if (InputFile *File = cast<LazyObjFile>(S->File)->fetch())
-    parseFile(File);
-}
-
 // Initialize DemangledSyms with a map from demangled symbols to symbol
 // objects. Used to handle "extern C++" directive in version scripts.
 //
 // The map will contain all demangled symbols. That can be very large,
 // and in LLD we generally want to avoid do anything for each symbol.
 // Then, why are we doing this? Here's why.
 //
 // Users can use "extern C++ {}" directive to match against demangled
for (SymbolVersion &Ver : V.Globals)
       assignWildcardVersion(Ver, V.Id);
 
   // Symbol themselves might know their versions because symbols
   // can contain versions in the form of <name>@<version>.
   // Let them parse and update their names to exclude version suffix.
   for (Symbol *Sym : SymVector)
     Sym->parseSymbolVersion();
 }
-
-// Merge symbol properties.
-//
-// When we have many symbols of the same name, we choose one of them,
-// and that's the result of symbol resolution. However, symbols that
-// were not chosen still affect some symbol properties.
-void elf::mergeSymbolProperties(Symbol *Old, const Symbol &New) {
-  // Merge symbol properties.
-  Old->ExportDynamic = Old->ExportDynamic || New.ExportDynamic;
-  Old->IsUsedInRegularObj = Old->IsUsedInRegularObj || New.IsUsedInRegularObj;
-
-  // DSO symbols do not affect visibility in the output.
-  if (!New.isShared())
-    Old->Visibility = getMinVisibility(Old->Visibility, New.Visibility);
-}
-
-void elf::resolveSymbol(Symbol *Old, const Symbol &New) {
-  mergeSymbolProperties(Old, New);
-
-  if (Old->isPlaceholder()) {
-    Old->replace(New);
-    return;
-  }
-
-  switch (New.kind()) {
-  case Symbol::UndefinedKind:
-    addUndefined(Old, cast<Undefined>(New));
-    break;
-  case Symbol::CommonKind:
-    addCommon(Old, cast<CommonSymbol>(New));
-    break;
-  case Symbol::DefinedKind:
-    addDefined(Old, cast<Defined>(New));
-    break;
-  case Symbol::LazyArchiveKind:
-    addLazyArchive(Old, cast<LazyArchive>(New));
-    break;
-  case Symbol::LazyObjectKind:
-    addLazyObject(Old, cast<LazyObject>(New));
-    break;
-  case Symbol::SharedKind:
-    addShared(Old, cast<SharedSymbol>(New));
-    break;
-  case Symbol::PlaceholderKind:
-    llvm_unreachable("bad symbol kind");
-  }
-}

ELF/Symbols.h

 #include "InputSection.h"
 #include "lld/Common/LLVM.h"
 #include "lld/Common/Strings.h"
 #include "llvm/Object/Archive.h"
 #include "llvm/Object/ELF.h"
 
 namespace lld {
 namespace elf {
-class Symbol;
+class CommonSymbol;
+class Defined;
 class InputFile;
+class LazyArchive;
+class LazyObject;
+class SharedSymbol;
+class Symbol;
+class Undefined;
 } // namespace elf
 
 std::string toString(const elf::Symbol &);
 std::string toString(const elf::InputFile *);
 
 namespace elf {
 
 // This is a StringRef-like container that doesn't run strlen().
public:
   uint64_t getGotPltOffset() const;
   uint64_t getGotPltVA() const;
   uint64_t getPltVA() const;
   uint64_t getPPC64LongBranchTableVA() const;
   uint64_t getPPC64LongBranchOffset() const;
   uint64_t getSize() const;
   OutputSection *getOutputSection() const;
 
+  // The following two functions are used for symbol resolution.
+  //
+  // You are expected to call mergeProperties for all symbols in input
+  // files so that attributes that are attached to names rather than
+  // indivisual symbol (such as visibility) are merged together.
+  //
+  // Every time you read a new symbol from an input, you are supposed
+  // to call resolve() with the new symbol. That function replaces
+  // "this" object as a result of name resolution if the new symbol is
+  // more appropriate to be included in the output.
+  //
+  // For example, if "this" is an undefined symbol and a new symbol is
+  // a defined symbol, "this" is replaced with the new symbol.
+  void mergeProperties(const Symbol &Other);
+  void resolve(const Symbol &Other);
+
+  // If this is a lazy symbol, fetch an input file and add the symbol
+  // in the file to the symbol table. Calling this function on
+  // non-lazy object causes a runtime error.
+  void fetch() const;
+
 private:
   static bool isExportDynamic(Kind K, uint8_t Visibility) {
     if (K == SharedKind)
       return Visibility == llvm::ELF::STV_DEFAULT;
     return Config->Shared || Config->ExportDynamic;
   }
 
+  void resolveUndefined(const Undefined &Other);
+  void resolveCommon(const CommonSymbol &Other);
+  void resolveDefined(const Defined &Other);
+  template <class LazyT> void resolveLazy(const LazyT &Other);
+  void resolveShared(const SharedSymbol &Other);
+
+  int compare(const Symbol *Other) const;
+
   inline size_t getSymbolSize() const;
 
 protected:
   Symbol(Kind K, InputFile *File, StringRefZ Name, uint8_t Binding,
          uint8_t StOther, uint8_t Type)
       : File(File), NameData(Name.Data), NameSize(Name.Size), Binding(Binding),
         Type(Type), StOther(StOther), SymbolKind(K), Visibility(StOther & 3),
         IsUsedInRegularObj(!File || File->kind() == InputFile::ObjKind),

 public:
   LazyArchive(InputFile &File, const llvm::object::Archive::Symbol S)
       : Symbol(LazyArchiveKind, &File, S.getName(), llvm::ELF::STB_GLOBAL,
                llvm::ELF::STV_DEFAULT, llvm::ELF::STT_NOTYPE),
         Sym(S) {}
 
   static bool classof(const Symbol *S) { return S->kind() == LazyArchiveKind; }
 
-  InputFile *fetch() const;
   MemoryBufferRef getMemberBuffer();
 
-private:
   const llvm::object::Archive::Symbol Sym;
 };
 
 // LazyObject symbols represents symbols in object files between
 // --start-lib and --end-lib options.
 class LazyObject : public Symbol {
 public:
   LazyObject(InputFile &File, StringRef Name)
       : Symbol(LazyObjectKind, &File, Name, llvm::ELF::STB_GLOBAL,
                llvm::ELF::STV_DEFAULT, llvm::ELF::STT_NOTYPE) {}
 
   static bool classof(const Symbol *S) { return S->kind() == LazyObjectKind; }
-
-  InputFile *fetch() const;
 };
 
 // Some linker-generated symbols need to be created as
 // Defined symbols.
 struct ElfSym {
   // __bss_start
   static Defined *Bss;
 

ELF/Symbols.cpp

void Symbol::parseSymbolVersion() {
   // so we do not report error in this case. We also do not error
   // if the symbol has a local version as it won't be in the dynamic
   // symbol table.
   if (Config->Shared && VersionId != VER_NDX_LOCAL)
     error(toString(File) + ": symbol " + S + " has undefined version " +
           Verstr);
 }
 
-InputFile *LazyArchive::fetch() const {
-  return cast<ArchiveFile>(File)->fetch(Sym);
+void Symbol::fetch() const {
+  if (auto *Sym = dyn_cast<LazyArchive>(this)) {
+    if (auto *F = cast<ArchiveFile>(Sym->File)->fetch(Sym->Sym))
+      parseFile(F);
+    return;
+  }
+
+  if (auto *Sym = dyn_cast<LazyObject>(this)) {
+    if (auto *F = dyn_cast<LazyObjFile>(Sym->File)->fetch())
+      parseFile(F);
+    return;
+  }
+
+  llvm_unreachable("Symbol::fetch() is called on a non-lazy symbol");
 }
 
 MemoryBufferRef LazyArchive::getMemberBuffer() {
   Archive::Child C = CHECK(
       Sym.getMember(), "could not get the member for symbol " + Sym.getName());
 
   return CHECK(C.getMemoryBufferRef(),
                "could not get the buffer for the member defining symbol " +
                    Sym.getName());
 }
 
-InputFile *LazyObject::fetch() const {
-  return cast<LazyObjFile>(File)->fetch();
-}
-
 uint8_t Symbol::computeBinding() const {
   if (Config->Relocatable)
     return Binding;
   if (Visibility != STV_DEFAULT && Visibility != STV_PROTECTED)
     return STB_LOCAL;
   if (VersionId == VER_NDX_LOCAL && isDefined() && !IsPreemptible)
     return STB_LOCAL;
   if (!Config->GnuUnique && Binding == STB_GNU_UNIQUE)

 
 // Returns a symbol for an error message.
 std::string lld::toString(const Symbol &B) {
   if (Config->Demangle)
     if (Optional<std::string> S = demangleItanium(B.getName()))
       return *S;
   return B.getName();
 }
+
+static uint8_t getMinVisibility(uint8_t VA, uint8_t VB) {
+  if (VA == STV_DEFAULT)
+    return VB;
+  if (VB == STV_DEFAULT)
+    return VA;
+  return std::min(VA, VB);
+}
+
+// Merge symbol properties.
+//
+// When we have many symbols of the same name, we choose one of them,
+// and that's the result of symbol resolution. However, symbols that
+// were not chosen still affect some symbol properties.
+void Symbol::mergeProperties(const Symbol &Other) {
+  if (Other.ExportDynamic)
+    ExportDynamic = true;
+  if (Other.IsUsedInRegularObj)
+    IsUsedInRegularObj = true;
+
+  // DSO symbols do not affect visibility in the output.
+  if (!Other.isShared())
+    Visibility = getMinVisibility(Visibility, Other.Visibility);
+}
+
+void Symbol::resolve(const Symbol &Other) {
+  mergeProperties(Other);
+
+  if (isPlaceholder()) {
+    replace(Other);
+    return;
+  }
+
+  switch (Other.kind()) {
+  case Symbol::UndefinedKind:
+    resolveUndefined(cast<Undefined>(Other));
+    break;
+  case Symbol::CommonKind:
+    resolveCommon(cast<CommonSymbol>(Other));
+    break;
+  case Symbol::DefinedKind:
+    resolveDefined(cast<Defined>(Other));
+    break;
+  case Symbol::LazyArchiveKind:
+    resolveLazy(cast<LazyArchive>(Other));
+    break;
+  case Symbol::LazyObjectKind:
+    resolveLazy(cast<LazyObject>(Other));
+    break;
+  case Symbol::SharedKind:
+    resolveShared(cast<SharedSymbol>(Other));
+    break;
+  case Symbol::PlaceholderKind:
+    llvm_unreachable("bad symbol kind");
+  }
+}
+
+void Symbol::resolveUndefined(const Undefined &Other) {
+  // An undefined symbol with non default visibility must be satisfied
+  // in the same DSO.
+  //
+  // If this is a non-weak defined symbol in a discarded section, override the
+  // existing undefined symbol for better error message later.
+  if ((isShared() && Other.Visibility != STV_DEFAULT) ||
+      (isUndefined() && Other.Binding != STB_WEAK && Other.DiscardedSecIdx)) {
+    replace(Other);
+    return;
+  }
+
+  if (isShared() || isLazy() || (isUndefined() && Other.Binding != STB_WEAK))
+    Binding = Other.Binding;
+
+  if (isLazy()) {
+    // An undefined weak will not fetch archive members. See comment on Lazy in
+    // Symbols.h for the details.
+    if (Other.Binding == STB_WEAK) {
+      Type = Other.Type;
+      return;
+    }
+
+    // Do extra check for --warn-backrefs.
+    //
+    // --warn-backrefs is an option to prevent an undefined reference from
+    // fetching an archive member written earlier in the command line. It can be
+    // used to keep compatibility with GNU linkers to some degree.
+    // I'll explain the feature and why you may find it useful in this comment.
+    //
+    // lld's symbol resolution semantics is more relaxed than traditional Unix
+    // linkers. For example,
+    //
+    //   ld.lld foo.a bar.o
+    //
+    // succeeds even if bar.o contains an undefined symbol that has to be
+    // resolved by some object file in foo.a. Traditional Unix linkers don't
+    // allow this kind of backward reference, as they visit each file only once
+    // from left to right in the command line while resolving all undefined
+    // symbols at the moment of visiting.
+    //
+    // In the above case, since there's no undefined symbol when a linker visits
+    // foo.a, no files are pulled out from foo.a, and because the linker forgets
+    // about foo.a after visiting, it can't resolve undefined symbols in bar.o
+    // that could have been resolved otherwise.
+    //
+    // That lld accepts more relaxed form means that (besides it'd make more
+    // sense) you can accidentally write a command line or a build file that
+    // works only with lld, even if you have a plan to distribute it to wider
+    // users who may be using GNU linkers. With --warn-backrefs, you can detect
+    // a library order that doesn't work with other Unix linkers.
+    //
+    // The option is also useful to detect cyclic dependencies between static
+    // archives. Again, lld accepts
+    //
+    //   ld.lld foo.a bar.a
+    //
+    // even if foo.a and bar.a depend on each other. With --warn-backrefs, it is
+    // handled as an error.
+    //
+    // Here is how the option works. We assign a group ID to each file. A file
+    // with a smaller group ID can pull out object files from an archive file
+    // with an equal or greater group ID. Otherwise, it is a reverse dependency
+    // and an error.
+    //
+    // A file outside --{start,end}-group gets a fresh ID when instantiated. All
+    // files within the same --{start,end}-group get the same group ID. E.g.
+    //
+    //   ld.lld A B --start-group C D --end-group E
+    //
+    // A forms group 0. B form group 1. C and D (including their member object
+    // files) form group 2. E forms group 3. I think that you can see how this
+    // group assignment rule simulates the traditional linker's semantics.
+    bool Backref = Config->WarnBackrefs && Other.File &&
+                   File->GroupId < Other.File->GroupId;
+    fetch();
+
+    // We don't report backward references to weak symbols as they can be
+    // overridden later.
+    if (Backref && !isWeak())
+      warn("backward reference detected: " + Other.getName() + " in " +
+           toString(Other.File) + " refers to " + toString(File));
+  }
+}
+
+// Using .symver foo,foo@@VER unfortunately creates two symbols: foo and
+// foo@@VER. We want to effectively ignore foo, so give precedence to
+// foo@@VER.
+// FIXME: If users can transition to using
+// .symver foo,foo@@@VER
+// we can delete this hack.
+static int compareVersion(StringRef A, StringRef B) {
+  bool X = A.contains("@@");
+  bool Y = B.contains("@@");
+  if (!X && Y)
+    return 1;
+  if (X && !Y)
+    return -1;
+  return 0;
+}
+
+// Compare two symbols. Return 1 if the new symbol should win, -1 if
+// the new symbol should lose, or 0 if there is a conflict.
+int Symbol::compare(const Symbol *Other) const {
+  assert(Other->isDefined() || Other->isCommon());
+
+  if (!isDefined() && !isCommon())
+    return 1;
+
+  if (int Cmp = compareVersion(getName(), Other->getName()))
+    return Cmp;
+
+  if (Other->isWeak())
+    return -1;
+
+  if (isWeak())
+    return 1;
+
+  if (isCommon() && Other->isCommon()) {
+    if (Config->WarnCommon)
+      warn("multiple common of " + getName());
+    return 0;
+  }
+
+  if (isCommon()) {
+    if (Config->WarnCommon)
+      warn("common " + getName() + " is overridden");
+    return 1;
+  }
+
+  if (Other->isCommon()) {
+    if (Config->WarnCommon)
+      warn("common " + getName() + " is overridden");
+    return -1;
+  }
+
+  auto *OldSym = cast<Defined>(this);
+  auto *NewSym = cast<Defined>(Other);
+
+  if (Other->File && isa<BitcodeFile>(Other->File))
+    return 0;
+
+  if (!OldSym->Section && !NewSym->Section && OldSym->Value == NewSym->Value &&
+      NewSym->Binding == STB_GLOBAL)
+    return -1;
+
+  return 0;
+}
+
+static void reportDuplicate(Symbol *Sym, InputFile *NewFile,
+                            InputSectionBase *ErrSec, uint64_t ErrOffset) {
+  if (Config->AllowMultipleDefinition)
+    return;
+
+  Defined *D = cast<Defined>(Sym);
+  if (!D->Section || !ErrSec) {
+    error("duplicate symbol: " + toString(*Sym) + "\n>>> defined in " +
+          toString(Sym->File) + "\n>>> defined in " + toString(NewFile));
+    return;
+  }
+
+  // Construct and print an error message in the form of:
+  //
+  //   ld.lld: error: duplicate symbol: foo
+  //   >>> defined at bar.c:30
+  //   >>>            bar.o (/home/alice/src/bar.o)
+  //   >>> defined at baz.c:563
+  //   >>>            baz.o in archive libbaz.a
+  auto *Sec1 = cast<InputSectionBase>(D->Section);
+  std::string Src1 = Sec1->getSrcMsg(*Sym, D->Value);
+  std::string Obj1 = Sec1->getObjMsg(D->Value);
+  std::string Src2 = ErrSec->getSrcMsg(*Sym, ErrOffset);
+  std::string Obj2 = ErrSec->getObjMsg(ErrOffset);
+
+  std::string Msg = "duplicate symbol: " + toString(*Sym) + "\n>>> defined at ";
+  if (!Src1.empty())
+    Msg += Src1 + "\n>>>            ";
+  Msg += Obj1 + "\n>>> defined at ";
+  if (!Src2.empty())
+    Msg += Src2 + "\n>>>            ";
+  Msg += Obj2;
+  error(Msg);
+}
+
+void Symbol::resolveCommon(const CommonSymbol &Other) {
+  int Cmp = compare(&Other);
+  if (Cmp < 0)
+    return;
+
+  if (Cmp > 0) {
+    replace(Other);
+    return;
+  }
+
+  CommonSymbol *OldSym = cast<CommonSymbol>(this);
+
+  OldSym->Alignment = std::max(OldSym->Alignment, Other.Alignment);
+  if (OldSym->Size < Other.Size) {
+    OldSym->File = Other.File;
+    OldSym->Size = Other.Size;
+  }
+}
+
+void Symbol::resolveDefined(const Defined &Other) {
+  int Cmp = compare(&Other);
+  if (Cmp > 0)
+    replace(Other);
+  else if (Cmp == 0)
+    reportDuplicate(this, Other.File,
+                    dyn_cast_or_null<InputSectionBase>(Other.Section),
+                    Other.Value);
+}
+
+template <class LazyT> void Symbol::resolveLazy(const LazyT &Other) {
+  if (!isUndefined())
+    return;
+
+  // An undefined weak will not fetch archive members. See comment on Lazy in
+  // Symbols.h for the details.
+  if (isWeak()) {
+    uint8_t Ty = Type;
+    replace(Other);
+    Type = Ty;
+    Binding = STB_WEAK;
+    return;
+  }
+
+  Other.fetch();
+}
+
+void Symbol::resolveShared(const SharedSymbol &Other) {
+  if (Visibility == STV_DEFAULT && (isUndefined() || isLazy())) {
+    // An undefined symbol with non default visibility must be satisfied
+    // in the same DSO.
+    uint8_t Bind = Binding;
+    replace(Other);
+    Binding = Bind;
+  }
+}