Add [<chars>] to the glob matcher to eliminate use of llvm::Regex.

[ruiu]

Summary

Previously, it didn't support the character class, so we couldn't
eliminate the use fo llvm::Regex. Now that it is supported, we
can remove compileGlobPattern, which converts a glob pattern to
a regex.

This patch contains optimization for exact/prefix/suffix matches.

[evgeny777]

LGTM with nits

ELF/LinkerScript.cpp

1250 ↗

(On Diff #76870)

std::move should be removed here or used on line 1214 as well

ELF/LinkerScript.h

117 ↗

(On Diff #76870)

I would use "StringMatcher &&" to avoid copying of member vector

ELF/Strings.cpp

148 ↗

(On Diff #76870)

I would pass Pat by const reference to avoid copying.

lld/trunk/ELF/LinkerScript.h

struct OutputSectionCommand : BaseCommand {
   std::vector<uint8_t> Filler;
   ConstraintKind Constraint = ConstraintKind::NoConstraint;
 };
 
 // This struct represents one section match pattern in SECTIONS() command.
 // It can optionally have negative match pattern for EXCLUDED_FILE command.
 // Also it may be surrounded with SORT() command, so contains sorting rules.
 struct SectionPattern {
-  SectionPattern(StringMatcher &&Re1, StringMatcher &&Re2)
-      : ExcludedFileRe(std::forward<StringMatcher>(Re1)),
-        SectionRe(std::forward<StringMatcher>(Re2)) {}
-
-  SectionPattern(SectionPattern &&Other) {
-    std::swap(ExcludedFileRe, Other.ExcludedFileRe);
-    std::swap(SectionRe, Other.SectionRe);
-    std::swap(SortOuter, Other.SortOuter);
-    std::swap(SortInner, Other.SortInner);
-  }
+  SectionPattern(StringMatcher &&Pat1, StringMatcher &&Pat2)
+      : ExcludedFilePat(Pat1), SectionPat(Pat2) {}
 
-  StringMatcher ExcludedFileRe;
-  StringMatcher SectionRe;
+  StringMatcher ExcludedFilePat;
+  StringMatcher SectionPat;
   SortSectionPolicy SortOuter;
   SortSectionPolicy SortInner;
 };
 
 struct InputSectionDescription : BaseCommand {
   InputSectionDescription(StringRef FilePattern)
-      : BaseCommand(InputSectionKind), FileRe(FilePattern) {}
+      : BaseCommand(InputSectionKind), FilePat({FilePattern}) {}
   static bool classof(const BaseCommand *C);
-  StringMatcher FileRe;
+  StringMatcher FilePat;
 
   // Input sections that matches at least one of SectionPatterns
   // will be associated with this InputSectionDescription.
   std::vector<SectionPattern> SectionPatterns;
 
   std::vector<InputSectionData *> Sections;
 };
 

lld/trunk/ELF/LinkerScript.cpp

 
 template <class ELFT> LinkerScript<ELFT>::LinkerScript() {}
 template <class ELFT> LinkerScript<ELFT>::~LinkerScript() {}
 
 template <class ELFT>
 bool LinkerScript<ELFT>::shouldKeep(InputSectionBase<ELFT> *S) {
   for (InputSectionDescription *ID : Opt.KeptSections) {
     StringRef Filename = S->getFile()->getName();
-    if (!ID->FileRe.match(sys::path::filename(Filename)))
+    if (!ID->FilePat.match(sys::path::filename(Filename)))
       continue;
 
     for (SectionPattern &P : ID->SectionPatterns)
-      if (P.SectionRe.match(S->Name))
+      if (P.SectionPat.match(S->Name))
         return true;
   }
   return false;
 }
 
 static bool comparePriority(InputSectionData *A, InputSectionData *B) {
   return getPriority(A->Name) < getPriority(B->Name);
 }

 template <class ELFT>
 void LinkerScript<ELFT>::computeInputSections(InputSectionDescription *I) {
   // Collects all sections that satisfy constraints of I
   // and attach them to I.
   for (SectionPattern &Pat : I->SectionPatterns) {
     size_t SizeBefore = I->Sections.size();
     for (ObjectFile<ELFT> *F : Symtab<ELFT>::X->getObjectFiles()) {
       StringRef Filename = sys::path::filename(F->getName());
-      if (!I->FileRe.match(Filename) || Pat.ExcludedFileRe.match(Filename))
+      if (!I->FilePat.match(Filename) || Pat.ExcludedFilePat.match(Filename))
         continue;
 
       for (InputSectionBase<ELFT> *S : F->getSections())
-        if (!isDiscarded(S) && !S->OutSec && Pat.SectionRe.match(S->Name))
+        if (!isDiscarded(S) && !S->OutSec && Pat.SectionPat.match(S->Name))
           I->Sections.push_back(S);
-      if (Pat.SectionRe.match("COMMON"))
+      if (Pat.SectionPat.match("COMMON"))
         I->Sections.push_back(InputSection<ELFT>::CommonInputSection);
     }
 
     // Sort sections as instructed by SORT-family commands and --sort-section
     // option. Because SORT-family commands can be nested at most two depth
     // (e.g. SORT_BY_NAME(SORT_BY_ALIGNMENT(.text.*))) and because the command
     // line option is respected even if a SORT command is given, the exact
     // behavior we have here is a bit complicated. Here are the rules.
return StringSwitch<int>(Op)
       .Cases("&", "|", 1)
       .Default(-1);
 }
 
 StringMatcher ScriptParser::readFilePatterns() {
   std::vector<StringRef> V;
   while (!Error && !consume(")"))
     V.push_back(next());
-  return StringMatcher(std::move(V));
+  return StringMatcher(V);
 }
 
 SortSectionPolicy ScriptParser::readSortKind() {
   if (consume("SORT") || consume("SORT_BY_NAME"))
     return SortSectionPolicy::Name;
   if (consume("SORT_BY_ALIGNMENT"))
     return SortSectionPolicy::Alignment;
   if (consume("SORT_BY_INIT_PRIORITY"))
     return SortSectionPolicy::Priority;
   if (consume("SORT_NONE"))
     return SortSectionPolicy::None;
   return SortSectionPolicy::Default;
 }
 
 // Method reads a list of sequence of excluded files and section globs given in
 // a following form: ((EXCLUDE_FILE(file_pattern+))? section_pattern+)+
 // Example: *(.foo.1 EXCLUDE_FILE (*a.o) .foo.2 EXCLUDE_FILE (*b.o) .foo.3)
 // The semantics of that is next:
 // * Include .foo.1 from every file.
 // * Include .foo.2 from every file but a.o
 // * Include .foo.3 from every file but b.o
 std::vector<SectionPattern> ScriptParser::readInputSectionsList() {
   std::vector<SectionPattern> Ret;
   while (!Error && peek() != ")") {
-    StringMatcher ExcludeFileRe;
+    StringMatcher ExcludeFilePat;
     if (consume("EXCLUDE_FILE")) {
       expect("(");
-      ExcludeFileRe = readFilePatterns();
+      ExcludeFilePat = readFilePatterns();
     }
 
     std::vector<StringRef> V;
     while (!Error && peek() != ")" && peek() != "EXCLUDE_FILE")
       V.push_back(next());
 
     if (!V.empty())
-      Ret.push_back({std::move(ExcludeFileRe), StringMatcher(std::move(V))});
+      Ret.push_back({std::move(ExcludeFilePat), StringMatcher(V)});
     else
       setError("section pattern is expected");
   }
   return Ret;
 }
 
 // Section pattern grammar can have complex expressions, for example:
 // *(SORT(.foo.* EXCLUDE_FILE (*file1.o) .bar.*) .bar.* SORT(.zed.*))

lld/trunk/ELF/Strings.h

 //===- Strings.h ------------------------------------------------*- C++ -*-===//
 //
 //                             The LLVM Linker
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLD_ELF_STRINGS_H
 #define LLD_ELF_STRINGS_H
 
 #include "lld/Core/LLVM.h"
 #include "llvm/ADT/ArrayRef.h"
+#include "llvm/ADT/BitVector.h"
+#include "llvm/ADT/Optional.h"
 #include "llvm/ADT/StringRef.h"
-#include "llvm/Support/Regex.h"
 #include <vector>
 
 namespace lld {
 namespace elf {
-llvm::Regex compileGlobPatterns(ArrayRef<StringRef> V);
+
 int getPriority(StringRef S);
 bool hasWildcard(StringRef S);
 std::vector<uint8_t> parseHex(StringRef S);
 bool isValidCIdentifier(StringRef S);
 StringRef unquote(StringRef S);
 
+// This class represents a glob pattern. Supported metacharacters
+// are "*", "?", "[<chars>]" and "[^<chars>]".
+class GlobPattern {
+public:
+  explicit GlobPattern(StringRef Pat);
+  bool match(StringRef S) const;
+
+private:
+  bool matchOne(ArrayRef<llvm::BitVector> Pat, StringRef S) const;
+  llvm::BitVector scan(StringRef &S);
+  llvm::BitVector expand(StringRef S);
+
+  // Parsed glob pattern.
+  std::vector<llvm::BitVector> Tokens;
+
+  // A glob pattern given to this class. This is for error reporting.
+  StringRef Original;
+
+  // The following members are for optimization.
+  llvm::Optional<StringRef> Exact;
+  llvm::Optional<StringRef> Prefix;
+  llvm::Optional<StringRef> Suffix;
+};
+
+// This class represents multiple glob patterns.
 class StringMatcher {
 public:
   StringMatcher() = default;
-  explicit StringMatcher(StringRef P) : Patterns({P}) {}
-  explicit StringMatcher(std::vector<StringRef> &&Pat)
-      : Patterns(std::move(Pat)) {}
+  explicit StringMatcher(const std::vector<StringRef> &Pat);
+
+  bool match(StringRef S) const;
 
-  bool match(StringRef S);
 private:
-  std::vector<StringRef> Patterns;
+  std::vector<GlobPattern> Patterns;
 };
 
 // Returns a demangled C++ symbol name. If Name is not a mangled
 // name or the system does not provide __cxa_demangle function,
 // it returns an unmodified string.
 std::string demangle(StringRef Name);
 
 // Demangle if Config->Demangle is true.

lld/trunk/ELF/Strings.cpp

 #include "llvm/Config/config.h"
 #include "llvm/Demangle/Demangle.h"
 #include <algorithm>
 
 using namespace llvm;
 using namespace lld;
 using namespace lld::elf;
 
-// Returns true if S matches T. S can contain glob meta-characters.
-// The asterisk ('*') matches zero or more characters, and the question
-// mark ('?') matches one character.
-static bool globMatch(StringRef S, StringRef T) {
+// This is a scanner for the glob pattern.
+// A glob pattern token is one of "*", "?", "[<chars>]", "[^<chars>]"
+// (which is a negative form of "[<chars>]"), or a non-meta character.
+// This function returns the first token in S.
+BitVector GlobPattern::scan(StringRef &S) {
+  switch (S[0]) {
+  case '*':
+    S = S.substr(1);
+    // '*' is represented by an empty bitvector.
+    // All other bitvectors are 256-bit long.
+    return BitVector();
+  case '?':
+    S = S.substr(1);
+    return BitVector(256, true);
+  case '[': {
+    size_t End = S.find(']', 1);
+    if (End == StringRef::npos) {
+      error("invalid glob pattern: " + Original);
+      return BitVector(256, false);
+    }
+    StringRef Chars = S.substr(1, End - 1);
+    S = S.substr(End + 1);
+    if (Chars.startswith("^"))
+      return expand(Chars.substr(1)).flip();
+    return expand(Chars);
+  }
+  default:
+    BitVector BV(256, false);
+    BV[S[0]] = true;
+    S = S.substr(1);
+    return BV;
+  }
+}
+
+// Expands character ranges and returns a bitmap.
+// For example, "a-cf-hz" is expanded to "abcfghz".
+BitVector GlobPattern::expand(StringRef S) {
+  BitVector BV(256, false);
+
+  // Expand "x-y".
   for (;;) {
-    if (S.empty())
-      return T.empty();
-    if (S[0] == '*') {
+    if (S.size() < 3)
+      break;
+
+    // If it doesn't start with something like "x-y",
+    // consume the first character and proceed.
+    if (S[1] != '-') {
+      BV[S[0]] = true;
       S = S.substr(1);
-      if (S.empty())
+      continue;
+    }
+
+    // It must be in the form of "x-y".
+    // Validate it and then interpret the range.
+    if (S[0] > S[2]) {
+      error("invalid glob pattern: " + Original);
+      return BV;
+    }
+    for (int C = S[0]; C <= S[2]; ++C)
+      BV[C] = true;
+    S = S.substr(3);
+  }
+
+  for (char C : S)
+    BV[C] = true;
+  return BV;
+}
+
+GlobPattern::GlobPattern(StringRef S) : Original(S) {
+  if (!hasWildcard(S)) {
+    // S doesn't contain any metacharacter,
+    // so the regular string comparison should work.
+    Exact = S;
+  } else if (S.endswith("*") && !hasWildcard(S.drop_back())) {
+    // S is something like "foo*". We can use startswith().
+    Prefix = S.drop_back();
+  } else if (S.startswith("*") && !hasWildcard(S.drop_front())) {
+    // S is something like "*foo". We can use endswith().
+    Suffix = S.drop_front();
+  } else {
+    // Otherwise, we need to do real glob pattern matching.
+    // Parse the pattern now.
+    while (!S.empty())
+      Tokens.push_back(scan(S));
+  }
+}
+
+bool GlobPattern::match(StringRef S) const {
+  if (Exact)
+    return S == *Exact;
+  if (Prefix)
+    return S.startswith(*Prefix);
+  if (Suffix)
+    return S.endswith(*Suffix);
+  return matchOne(Tokens, S);
+}
+
+// Runs glob pattern Pats against string S.
+bool GlobPattern::matchOne(ArrayRef<BitVector> Pats, StringRef S) const {
+  for (;;) {
+    if (Pats.empty())
+      return S.empty();
+
+    // If Pats[0] is '*', try to match Pats[1..] against all possible
+    // substrings of S to see at least one pattern succeeds.
+    if (Pats[0].size() == 0) {
+      Pats = Pats.slice(1);
+      if (Pats.empty())
         // Fast path. If a pattern is '*', it matches anything.
         return true;
-      for (size_t I = 0, E = T.size(); I < E; ++I)
-        if (globMatch(S, T.substr(I)))
+      for (size_t I = 0, E = S.size(); I < E; ++I)
+        if (matchOne(Pats, S.substr(I)))
           return true;
       return false;
     }
-    if (T.empty() || (S[0] != T[0] && S[0] != '?'))
+
+    // If Pats[0] is not '*', it must consume one character.
+    if (S.empty() || !Pats[0][S[0]])
       return false;
+    Pats = Pats.slice(1);
     S = S.substr(1);
-    T = T.substr(1);
   }
 }
 
-bool StringMatcher::match(StringRef S) {
-  for (StringRef P : Patterns)
-    if (globMatch(P, S))
+StringMatcher::StringMatcher(const std::vector<StringRef> &Pat) {
+  for (StringRef S : Pat)
+    Patterns.push_back(GlobPattern(S));
+}
+
+bool StringMatcher::match(StringRef S) const {
+  for (const GlobPattern &Pat : Patterns)
+    if (Pat.match(S))
       return true;
   return false;
 }
+
 // If an input string is in the form of "foo.N" where N is a number,
 // return N. Otherwise, returns 65536, which is one greater than the
 // lowest priority.
 int elf::getPriority(StringRef S) {
   size_t Pos = S.rfind('.');
   if (Pos == StringRef::npos)
     return 65536;
   int V;
   if (S.substr(Pos + 1).getAsInteger(10, V))
     return 65536;
   return V;
 }
 
 bool elf::hasWildcard(StringRef S) {
   return S.find_first_of("?*[") != StringRef::npos;
 }
 
 StringRef elf::unquote(StringRef S) {
   if (!S.startswith("\""))
     return S;
   return S.substr(1, S.size() - 2);
 }
 
-// Converts a glob pattern to a regular expression.
-static std::string toRegex(StringRef S) {
-  std::string T;
-  bool InBracket = false;
-  while (!S.empty()) {
-    char C = S.front();
-    if (InBracket) {
-      InBracket = C != ']';
-      T += C;
-      S = S.drop_front();
-      continue;
-    }
-
-    if (C == '*')
-      T += ".*";
-    else if (C == '?')
-      T += '.';
-    else if (StringRef(".+^${}()|/\\").find_first_of(C) != StringRef::npos)
-      T += std::string("\\") + C;
-    else
-      T += C;
-
-    InBracket = C == '[';
-    S = S.substr(1);
-  }
-  return T;
-}
-
-// Converts multiple glob patterns to a regular expression.
-Regex elf::compileGlobPatterns(ArrayRef<StringRef> V) {
-  std::string T = "^(" + toRegex(V[0]);
-  for (StringRef S : V.slice(1))
-    T += "|" + toRegex(S);
-  return Regex(T + ")$");
-}
-
 // Converts a hex string (e.g. "deadbeef") to a vector.
 std::vector<uint8_t> elf::parseHex(StringRef S) {
   std::vector<uint8_t> Hex;
   while (!S.empty()) {
     StringRef B = S.substr(0, 2);
     S = S.substr(2);
     uint8_t H;
     if (B.getAsInteger(16, H)) {

lld/trunk/ELF/SymbolTable.h

 //===- SymbolTable.h --------------------------------------------*- C++ -*-===//
 //
 //                             The LLVM Linker
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLD_ELF_SYMBOL_TABLE_H
 #define LLD_ELF_SYMBOL_TABLE_H
 
 #include "InputFiles.h"
 #include "LTO.h"
+#include "Strings.h"
 #include "llvm/ADT/CachedHashString.h"
 #include "llvm/ADT/DenseMap.h"
-#include "llvm/Support/Regex.h"
 
 namespace lld {
 namespace elf {
 class Lazy;
 template <class ELFT> class OutputSectionBase;
 struct Symbol;
 
 typedef llvm::CachedHashStringRef SymName;
public:
   void scanVersionScript();
 
   SymbolBody *find(StringRef Name);
 
   void trace(StringRef Name);
   void wrap(StringRef Name);
 
 private:
-  std::vector<SymbolBody *> findAll(const llvm::Regex &Re);
+  std::vector<SymbolBody *> findAll(const StringMatcher &M);
   std::pair<Symbol *, bool> insert(StringRef &Name);
   std::pair<Symbol *, bool> insert(StringRef &Name, uint8_t Type,
                                    uint8_t Visibility, bool CanOmitFromDynSym,
                                    InputFile *File);
 
   void reportDuplicate(SymbolBody *Existing, InputFile *NewFile);
 
   std::map<std::string, std::vector<SymbolBody *>> getDemangledSyms();

lld/trunk/ELF/SymbolTable.cpp

template <class ELFT> SymbolBody *SymbolTable<ELFT>::find(StringRef Name) {
   SymIndex V = It->second;
   if (V.Idx == -1)
     return nullptr;
   return SymVector[V.Idx]->body();
 }
 
 // Returns a list of defined symbols that match with a given regex.
 template <class ELFT>
-std::vector<SymbolBody *> SymbolTable<ELFT>::findAll(const Regex &Re) {
+std::vector<SymbolBody *> SymbolTable<ELFT>::findAll(const StringMatcher &M) {
   std::vector<SymbolBody *> Res;
   for (Symbol *Sym : SymVector) {
     SymbolBody *B = Sym->body();
     StringRef Name = B->getName();
-    if (!B->isUndefined() && const_cast<Regex &>(Re).match(Name))
+    if (!B->isUndefined() && M.match(Name))
       Res.push_back(B);
   }
   return Res;
 }
 
 template <class ELFT>
 void SymbolTable<ELFT>::addLazyArchive(ArchiveFile *F,
                                        const object::Archive::Symbol Sym) {
findDemangled(std::map<std::string, std::vector<SymbolBody *>> &D,
   auto I = D.find(Name);
   if (I != D.end())
     return I->second;
   return {};
 }
 
 static std::vector<SymbolBody *>
 findAllDemangled(const std::map<std::string, std::vector<SymbolBody *>> &D,
-                 const Regex &Re) {
+                 StringMatcher &M) {
   std::vector<SymbolBody *> Res;
   for (auto &P : D) {
-    if (const_cast<Regex &>(Re).match(P.first))
+    if (M.match(P.first))
       for (SymbolBody *Body : P.second)
         if (!Body->isUndefined())
           Res.push_back(Body);
   }
   return Res;
 }
 
 // If there's only one anonymous version definition in a version
 // script file, the script does not actullay define any symbol version,
 // but just specifies symbols visibilities. We assume that the script was
 // in the form of { global: foo; bar; local *; }. So, local is default.
 // In this function, we make specified symbols global.
 template <class ELFT> void SymbolTable<ELFT>::handleAnonymousVersion() {
   std::vector<StringRef> Patterns;
   for (SymbolVersion &Sym : Config->VersionScriptGlobals) {
     if (hasWildcard(Sym.Name)) {
       Patterns.push_back(Sym.Name);
       continue;
     }
     if (SymbolBody *B = find(Sym.Name))
       B->symbol()->VersionId = VER_NDX_GLOBAL;
   }
   if (Patterns.empty())
     return;
-  Regex Re = compileGlobPatterns(Patterns);
-  std::vector<SymbolBody *> Syms = findAll(Re);
+  StringMatcher M(Patterns);
+  std::vector<SymbolBody *> Syms = findAll(M);
   for (SymbolBody *B : Syms)
     B->symbol()->VersionId = VER_NDX_GLOBAL;
 }
 
 // This function processes version scripts by updating VersionId
 // member of symbols.
 template <class ELFT> void SymbolTable<ELFT>::scanVersionScript() {
   // Handle edge cases first.
template <class ELFT> void SymbolTable<ELFT>::scanVersionScript() {
   // i.e. version definitions containing glob meta-characters.
   // Note that because the last match takes precedence over previous matches,
   // we iterate over the definitions in the reverse order.
   for (size_t I = Config->VersionDefinitions.size() - 1; I != (size_t)-1; --I) {
     VersionDefinition &V = Config->VersionDefinitions[I];
     for (SymbolVersion &Sym : V.Globals) {
       if (!Sym.HasWildcards)
         continue;
-      Regex Re = compileGlobPatterns({Sym.Name});
+      StringMatcher M({Sym.Name});
       std::vector<SymbolBody *> Syms =
-          Sym.IsExternCpp ? findAllDemangled(Demangled, Re) : findAll(Re);
+          Sym.IsExternCpp ? findAllDemangled(Demangled, M) : findAll(M);
 
       // Exact matching takes precendence over fuzzy matching,
       // so we set a version to a symbol only if no version has been assigned
       // to the symbol. This behavior is compatible with GNU.
       for (SymbolBody *B : Syms)
         if (B->symbol()->VersionId == Config->DefaultSymbolVersion)
           B->symbol()->VersionId = V.Id;
     }
   }
 }
 
 template class elf::SymbolTable<ELF32LE>;
 template class elf::SymbolTable<ELF32BE>;
 template class elf::SymbolTable<ELF64LE>;
 template class elf::SymbolTable<ELF64BE>;