[ELF] - Use std::regex instead of hand written logic in elf::globMatch()

[grimar]

Summary

As was suggested in review comments for D23803,
we can use std::regex instead of hand written matcher.

Patch based on code and ideas of Rui Ueyama (D23827).

[ruiu]

ELF/Config.h

47–49 ↗

(On Diff #69090)

I wouldn't think that this class is designed well. Name and Wildcard are mutually exclusive, and if hasWildcard(Sym.Name) is false, you need to use Sym.Wildcard. That's not easy to understand.

49 ↗

(On Diff #69090)

This should be named Re.

ELF/LinkerScript.cpp

130–132 ↗

(On Diff #69090)

Isn't this slow?

ELF/Strings.cpp

33 ↗

(On Diff #69090)

This converts "[*]" to "[.*]" which is wrong.

46 ↗

(On Diff #69090)

You need to remove this function. This is not even a "glob" match anymore.

[grimar]

ELF/Config.h

47–49 ↗

(On Diff #69090)

That is because I am trying not to use regex matching when it is unnessecary, like in next case:
SymbolTable.cpp(linke 646)

SymbolBody *B = Sym.IsExternCpp ? Demangled[Sym.Name] : find(Sym.Name);

I can probably introduce some helper method hiding this logic.

ELF/Strings.cpp

33 ↗

(On Diff #69090)

Before this patch we did not have support of "[" or "]". This patch does not add any testcases as well as does not add support for them.
I am assuming that testcases and support for new wildcard characters should be added separately.

[grimar]

ELF/Strings.cpp

33 ↗

(On Diff #69090)

The real problem here is that is converts ".foo" to ".foo" (unchanged), what is incorrect. I`ll add testcase and fix that.

[grimar]

ELF/LinkerScript.cpp

130–132 ↗

(On Diff #69090)

I think this should not be slow. Even FreeBSD script
which I think is from largest group there are ~150 input sections pattern in total.
That is not huge amount itself.
I think 99% of them starts from "." (a dot, not a any character, like ".data" will have pattern "\.data")
And matching should end on first symbol comparsion for most of them ('C' vs '.').
Am I missing something here ?

[grimar]

• Fixed bug (".data" expression was generated from ".data" instead of "\.data"), added testcase.
• Addressed review comments.

ELF/Config.h

47–49 ↗

(On Diff #69090)

I think we do not need that new field at all. It can be created on demand since only used in scanVersionScript(). I removed it.

ELF/Strings.cpp

46 ↗

(On Diff #69090)

Done.

[ruiu]

ELF/LinkerScript.cpp

836–841 ↗

(On Diff #69095)

This function can return a std::regex instead of a vector of std::regexs by concatenating regexs using |.

ELF/Strings.cpp

29–30 ↗

(On Diff #69095)

This is not a state machine.

ELF/SymbolTable.cpp

486 ↗

(On Diff #69095)

clang-format

ELF/SymbolTable.h

94 ↗

(On Diff #69095)

clang-format

[majnemer]

Our software requirements include that GCC should be >= 4.7.0: http://llvm.org/docs/GettingStarted.html#software

However, std::regex wasn't implemented until GCC 4.9.0

Could you use llvm::Regex instead?

[grimar]

• Addressed review comments.
• Switched to llvm::Regex

[grimar]

ELF/LinkerScript.cpp

836–841 ↗

(On Diff #69095)

"|" does not work with std::regex::basic, because not a part of basic regular expressions syntax (http://pubs.opengroup.org/onlinepubs/9699919799/basedefs/V1_chap09.html#tag_09_03_05).

I guess removing std::regex::basic should be slower while there is no real profit.

105 ↗

(On Diff #69675)

I dont like this and other const casts I had to use,
D24027 should help to fix that.

ELF/Strings.cpp

29–30 ↗

(On Diff #69095)

Hmm technically it can be I think.

Like from initial state basing on input it do a transition to state N,
and each state N returns the machine to initial state after doing its job.

I changed comment anyways :)

[ruiu]

ELF/LinkerScript.cpp

95 ↗

(On Diff #69675)

Nit: we probably should use Re as a local variable name throughout this patch instead of Pat, Pattern nor Patterns because it is no longer a glob pattern (which Pat was named after) but a regular expression.

847–852 ↗

(On Diff #69675)

It shouldn't be slow. I did not actually take a look at the implementation, but at least in theory, any regular expression that we use can be compiled to a DFA because we do not use anything that requires NFA such as capturing. If you can't use | because you are using the basic re, you shouldn't use the basic re but instead extended one.

ELF/LinkerScript.h

97 ↗

(On Diff #69675)

Why unique_ptr?

132 ↗

(On Diff #69675)

Why pointers?

ELF/Strings.h

19 ↗

(On Diff #69675)

Let's name this compileGlobPattern because it complies a glob pattern to a re.

[grimar]

• Addressed review comments.

[grimar]

ELF/LinkerScript.cpp

95 ↗

(On Diff #69675)

Done.

847–852 ↗

(On Diff #69675)

Ok, I see.
Found one more problem with that unfortunatelly:

I can't just switch current:

std::vector<llvm::Regex> ExcludedFiles;
std::vector<llvm::Regex> SectionPatterns;

to

llvm::Regex ExcludedFiles;
llvm::Regex SectionPatterns;

Because as I mantioned above, llvm::Regex does not have constructor with no arguments.
Not sure we what we should do (I guess anyways we will switch to use of std::regex one day probably), so possible solutions are
either not to use "|" or to make them unique_ptr.
What do you think ?

ELF/LinkerScript.h

97 ↗

(On Diff #69675)

In compare with std::regex, llvm::Regex does not have constructor with no arguments.
Removed unique_ptr, added argument for InputSectionDescription instead.

132 ↗

(On Diff #69675)

Restriction of API. llvm::Regex is non-copyable.
That looks to be intended:
r198334 "Make llvm::Regex non-copyable but movable."

So I cant just copy kept patterns into KeptSections.

106 ↗

(On Diff #69826)

Not sure, do we want to rename SectionPatterns and FilePattern to something then ?

[ruiu]

ELF/LinkerScript.cpp

907–912 ↗

(On Diff #69826)

Why don't you add a constructor with no arguments to llvm::Regex?

[grimar]

ELF/LinkerScript.cpp

907–912 ↗

(On Diff #69826)

OK, I can do that. What do you think about const_casts this patch introduces ?
We can either avoid using const llvm::Regex references to be able to use non-const match or reimplement llvm::Regex to be able to make match() const.

[grimar]

ELF/LinkerScript.cpp

907–912 ↗

(On Diff #69826)

One more variant is to leave const_casts as is for now.

[ruiu]

llvm::Regex is not used in that many places, so it seems you can make Match const and update all places where that member function is called.

[grimar]

In D23829#530459, @ruiu wrote:

llvm::Regex is not used in that many places, so it seems you can make Match const and update all places where that member function is called.

Actually it is. Just search "Regex" in llvm. I wanted to do it const here: D24027. It requires making error field to be mutable.

David Blaikie was against this change:

"Sounds like the error handling is part of the identity of the object - I'm not sure it'd be a good idea to make that mutable & make the object logically const when it's actually changing that error field. (it seems it'd be easy to introduce misuse there - where one user does something to the Regex, then passes a const ref somewhere, then examines the error field and finds it changed - let alone multithreading)"

His suggestion was:

"(or remove the side-channel error handling, and have the APIs return errors explicitly instead - the side channel's likely to be accidentally unchecked by many callers, which is probably a mistake)"

Reworking llvm::Regex API is not a little change and I am not sure it is worth that as std::regex is a part of c++ 11 and I hope soon all compilers will have a support.

[ruiu]

How about defining a copy constructor to llvm::Regex and create mutable copies from const Regexs? Regex seems to be just two-pointer-sized object so copying it should be cheap.

[grimar]

In D23829#530626, @ruiu wrote:

How about defining a copy constructor to llvm::Regex and create mutable copies from const Regexs? Regex seems to be just two-pointer-sized object so copying it should be cheap.

And wrap llvm_regex *preg into something like std::shared_ptr with custom deleter ?

[grimar]

In D23829#530634, @grimar wrote:

In D23829#530626, @ruiu wrote:

How about defining a copy constructor to llvm::Regex and create mutable copies from const Regexs? Regex seems to be just two-pointer-sized object so copying it should be cheap.

And wrap llvm_regex *preg into something like std::shared_ptr with custom deleter ?

I did not mean we should really do that, only that it is not that simple just to copy it properly.
Probably we can remove the set of error field from match() at all.

It has next code:

if (rc != 0) {
  // regexec can fail due to invalid pattern or running out of memory.
  error = rc;
  return false;
}

I do not think that set a srror in case of invalid pattern is fine. As we might want to call it second time with valid one.
Out of memory probably is the error we can ignore.
Method anyways return bool result, that should be enough.

[grimar]

Closing this as r280284 was committed instead.

[grimar]

Closed by mistake, sorry.

[grimar]

• Updated to use "|" for regex concatenations.

[ruiu]

ELF/LinkerScript.cpp

96–97 ↗

(On Diff #69983)

if (Re->match(S->getSectionName()))

ELF/LinkerScript.h

101 ↗

(On Diff #69983)

Please do not use the implicit conversion from an object of type T to ArrayRef<T>. That confused me. Add {} around FilePattern. You also want to rename compileGlobPatterns since now it takes not a single glob pattern but many patterns.

107 ↗

(On Diff #69983)

I'd rename SectionRe and FileRe.

ELF/Strings.cpp

31 ↗

(On Diff #69983)

There's a room to simplify this function. First , define a function that compiles single glob pattern.

static std::string toRegex(StringRef S);

and then use it as

Regex elf::compileGlobPatterns(ArrayRef<StringRef> V) {
  std::string T = "^(" + toRegex(V[0]);
  for (StringRef S : V.slice(1))
    T += "|" + toRegex(S);
  return Regex(T + ")$");
}

43 ↗

(On Diff #69983)

. is not the only one metacharacter we want to quote. For example, if it contains \, it needs to be converted to \\. Did you do that?

[grimar]

ELF/LinkerScript.h

101 ↗

(On Diff #69983)

Ok, I just was unsure what is the best way to avoid that. Was thinking about separate method for single pattern compilation, unfortunately it needs to be exported so rejected that way.
Approach with {} should work and looks evident enough, will use it.

[grimar]

• Addressed review comments.
• Returned const_casts for Regex.

ELF/LinkerScript.cpp

96–97 ↗

(On Diff #69983)

Done.

ELF/LinkerScript.h

107 ↗

(On Diff #69983)

Done.

ELF/Strings.cpp

31 ↗

(On Diff #69983)

Done.

43 ↗

(On Diff #69983)

Nope. Looking on the list of metacharacters I dont think I ever saw them in globs. We also do not have testcases with them yet. Do you think this can be done in separate patch ?

[ruiu]

ELF/Strings.cpp

42 ↗

(On Diff #70167)

Are you sure? What will happen if you have this?

SECTIONS { .text : { "foo(bar*).o"( .text ); } }

where "foo(bar*).o" is an actual file name.

[grimar]

ELF/Strings.cpp

42 ↗

(On Diff #70167)

I did not say it is not possible. I meant it is so unusual that we even do not have testcases covering that. And sutuation is unlikely to happen, that is why I suggested to prepare testcases and separate patch for that.
From your comments it seems you would like to see it in this patch. Ok, I'll do that.

[grimar]

• Addressed review comments.

[grimar]

ELF/Strings.cpp

32 ↗

(On Diff #70210)

Not supported because there is D23803 for that.

[grimar]

test/ELF/wildcards2.s

18 ↗

(On Diff #70210)

It is not possible to create file with "|" "/" or "\" in name, so this is not tested here.

[ruiu]

ELF/Strings.cpp

35–36 ↗

(On Diff #70210)

for (char F : S)

By the way, why F?

41 ↗

(On Diff #70210)

StringRef(".+^${}()|/\\[]").find_first_of(F) is probably more conventional.

42 ↗

(On Diff #70210)

What is this std::string() for?

test/ELF/wildcards2.s

18 ↗

(On Diff #70210)

You don't need to test this this vigorously. It is too easy to break on minor filesystems. Add a test just for ..

[grimar]

ELF/Strings.cpp

35–36 ↗

(On Diff #70210)

Front. Do you prefer other name ?

42 ↗

(On Diff #70210)

"\\" is a pointer to char.
+ F just moves that pointer, but I need concatenation of string.

[grimar]

ELF/Strings.cpp

42 ↗

(On Diff #70210)

I mean if I would just write

T += "\\" + F;

test/ELF/wildcards2.s

18 ↗

(On Diff #70210)

Done.

[grimar]

test/ELF/wildcards2.s

18 ↗

(On Diff #70210)

Posted this comment too early. Will be done in updated diff I mean.

[grimar]

• Addressed review comments.

test/ELF/wildcards2.s

18 ↗

(On Diff #70210)

So, removed the last added testcase because first one already do check for dot.

[ruiu]

Please ping me after all depending patches are submitted.

[grimar]

In D23829#533376, @ruiu wrote:

Please ping me after all depending patches are submitted.

They are already. D24102 looks will not be accepted and the latest diffs of current patch does not require it (that is why it has const_casts for Regex).

[ruiu]

ELF/LinkerScript.cpp

103–105 ↗

(On Diff #70223)

This is the same as

return const_cast<Regex &>(Desc->FileRe).match(Filename) &&
       !const_cast<Regex &>(Desc->ExcludedFiles).match(Filename);

ELF/LinkerScript.h

101 ↗

(On Diff #70223)

compileGlobPatterns (notice the last s.)

106 ↗

(On Diff #70223)

Maybe this should be ExcludedFileRe.

ELF/Strings.cpp

35–36 ↗

(On Diff #70223)

I think we usually use C for a character.

50 ↗

(On Diff #70223)

This is not a method but just a function. It doesn't convert into a regex form, but converts into a regex object. It always takes multiple glob patterns (it's just that the array could contain just one element).

ELF/Strings.h

19 ↗

(On Diff #70223)

S doesn't match with the actual parameter name.

[grimar]

• Addressed review comments.

ELF/LinkerScript.cpp

103–105 ↗

(On Diff #70223)

Done.

ELF/LinkerScript.h

101 ↗

(On Diff #70223)

Forget about "s", sorry. Fixed.

106 ↗

(On Diff #70223)

Done.

ELF/Strings.cpp

35–36 ↗

(On Diff #70223)

Done.

50 ↗

(On Diff #70223)

Done.

ELF/Strings.h

19 ↗

(On Diff #70223)

Done.

[ruiu]

LGTM with all these changes.

ELF/Strings.cpp

51 ↗

(On Diff #70230)

Why P? I believe we usually use V or Arr for an ArrayRef.

ELF/SymbolTable.cpp

486 ↗

(On Diff #70230)

given regex.

ELF/SymbolTable.h

95 ↗

(On Diff #70230)

Pattern -> Re (Please be consistent with naming.)

[grimar]

Thanks for review !

ELF/Strings.cpp

51 ↗

(On Diff #70230)

Because Patterns. Actually choosed between V and P. Will switch to P then.

[ruiu]

ELF/Strings.cpp

51 ↗

(On Diff #70230)

Actually I found that it is easy to read if you name variables of a small scope according to it's type rather than what the variable has, so please stick with V or Arr.

[ruiu]

ELF/Strings.cpp

51 ↗

(On Diff #70230)

We know that the argument is an array of glob patterns. Because the function name and the comment says so. But if you name it P, it'd make everybody wonder what P is. At least, it doesn't make much sense to me.

lld/trunk/ELF/LinkerScript.h

 //===- LinkerScript.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_LINKER_SCRIPT_H
 #define LLD_ELF_LINKER_SCRIPT_H
 
+#include "Strings.h"
 #include "Writer.h"
 #include "lld/Core/LLVM.h"
 #include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/MapVector.h"
 #include "llvm/Support/Allocator.h"
 #include "llvm/Support/MemoryBuffer.h"
+#include "llvm/Support/Regex.h"
 #include <functional>
 
 namespace lld {
 namespace elf {
 class DefinedCommon;
 class ScriptParser;
 class SymbolBody;
 template <class ELFT> class InputSectionBase;
struct OutputSectionCommand : BaseCommand {
   std::vector<StringRef> Phdrs;
   std::vector<uint8_t> Filler;
   ConstraintKind Constraint = ConstraintKind::NoConstraint;
 };
 
 enum SortKind { SortNone, SortByName, SortByAlignment };
 
 struct InputSectionDescription : BaseCommand {
-  InputSectionDescription() : BaseCommand(InputSectionKind) {}
+  InputSectionDescription(StringRef FilePattern)
+      : BaseCommand(InputSectionKind),
+        FileRe(compileGlobPatterns({FilePattern})) {}
   static bool classof(const BaseCommand *C);
-  StringRef FilePattern;
+  llvm::Regex FileRe;
   SortKind SortOuter = SortNone;
   SortKind SortInner = SortNone;
-  std::vector<StringRef> ExcludedFiles;
-  std::vector<StringRef> SectionPatterns;
+  llvm::Regex ExcludedFileRe;
+  llvm::Regex SectionRe;
 };
 
 struct AssertCommand : BaseCommand {
   AssertCommand(Expr E) : BaseCommand(AssertKind), Expression(E) {}
   static bool classof(const BaseCommand *C);
   Expr Expression;
 };
 
struct ScriptConfiguration {
   std::vector<PhdrsCommand> PhdrsCommands;
 
   bool HasContents = false;
 
   llvm::BumpPtrAllocator Alloc;
 
   // List of section patterns specified with KEEP commands. They will
   // be kept even if they are unused and --gc-sections is specified.
-  std::vector<StringRef> KeptSections;
+  std::vector<llvm::Regex *> KeptSections;
 };
 
 extern ScriptConfiguration *ScriptConfig;
 
 // This is a runner of the linker script.
 template <class ELFT> class LinkerScript {
   typedef typename ELFT::uint uintX_t;
 

lld/trunk/ELF/LinkerScript.cpp

template <class ELFT> static bool isDiscarded(InputSectionBase<ELFT> *S) {
   return !S || !S->Live;
 }
 
 template <class ELFT> LinkerScript<ELFT>::LinkerScript() {}
 template <class ELFT> LinkerScript<ELFT>::~LinkerScript() {}
 
 template <class ELFT>
 bool LinkerScript<ELFT>::shouldKeep(InputSectionBase<ELFT> *S) {
-  for (StringRef Pat : Opt.KeptSections)
-    if (globMatch(Pat, S->getSectionName()))
-      return true;
-  return false;
-}
-
-static bool match(ArrayRef<StringRef> Patterns, StringRef S) {
-  for (StringRef Pat : Patterns)
-    if (globMatch(Pat, S))
+  for (Regex *Re : Opt.KeptSections)
+    if (Re->match(S->getSectionName()))
       return true;
   return false;
 }
 
 static bool fileMatches(const InputSectionDescription *Desc,
                         StringRef Filename) {
-  if (!globMatch(Desc->FilePattern, Filename))
-    return false;
-  return Desc->ExcludedFiles.empty() || !match(Desc->ExcludedFiles, Filename);
+  return const_cast<Regex &>(Desc->FileRe).match(Filename) &&
+         !const_cast<Regex &>(Desc->ExcludedFileRe).match(Filename);
 }
 
 // Returns input sections filtered by given glob patterns.
 template <class ELFT>
 std::vector<InputSectionBase<ELFT> *>
 LinkerScript<ELFT>::getInputSections(const InputSectionDescription *I) {
-  ArrayRef<StringRef> Patterns = I->SectionPatterns;
+  const Regex &Re = I->SectionRe;
   std::vector<InputSectionBase<ELFT> *> Ret;
   for (const std::unique_ptr<ObjectFile<ELFT>> &F :
        Symtab<ELFT>::X->getObjectFiles()) {
     if (fileMatches(I, sys::path::filename(F->getName())))
       for (InputSectionBase<ELFT> *S : F->getSections())
         if (!isDiscarded(S) && !S->OutSec &&
-            match(Patterns, S->getSectionName()))
+            const_cast<Regex &>(Re).match(S->getSectionName()))
           Ret.push_back(S);
   }
 
-  if (llvm::find(Patterns, "COMMON") != Patterns.end())
+  if (const_cast<Regex &>(Re).match("COMMON"))
     Ret.push_back(CommonInputSection<ELFT>::X);
-
   return Ret;
 }
 
 template <class ELFT>
 static bool compareName(InputSectionBase<ELFT> *A, InputSectionBase<ELFT> *B) {
   return A->getSectionName() < B->getSectionName();
 }
 
private:
   void readVersion();
   void readVersionScriptCommand();
 
   SymbolAssignment *readAssignment(StringRef Name);
   OutputSectionCommand *readOutputSectionDescription(StringRef OutSec);
   std::vector<uint8_t> readOutputSectionFiller();
   std::vector<StringRef> readOutputSectionPhdrs();
   InputSectionDescription *readInputSectionDescription(StringRef Tok);
-  std::vector<StringRef> readInputFilePatterns();
+  Regex readFilePatterns();
   InputSectionDescription *readInputSectionRules(StringRef FilePattern);
   unsigned readPhdrType();
   SortKind readSortKind();
   SymbolAssignment *readProvideHidden(bool Provide, bool Hidden);
   SymbolAssignment *readProvideOrAssignment(StringRef Tok);
   void readSort();
   Expr readAssert();
 
return StringSwitch<int>(Op)
       .Case("<=", 2)
       .Case("==", 2)
       .Case("!=", 2)
       .Case("&", 1)
       .Case("|", 1)
       .Default(-1);
 }
 
-std::vector<StringRef> ScriptParser::readInputFilePatterns() {
+Regex ScriptParser::readFilePatterns() {
   std::vector<StringRef> V;
   while (!Error && !skip(")"))
     V.push_back(next());
-  return V;
+  return compileGlobPatterns(V);
 }
 
 SortKind ScriptParser::readSortKind() {
   if (skip("SORT") || skip("SORT_BY_NAME"))
     return SortByName;
   if (skip("SORT_BY_ALIGNMENT"))
     return SortByAlignment;
   return SortNone;
 }
 
 InputSectionDescription *
 ScriptParser::readInputSectionRules(StringRef FilePattern) {
-  auto *Cmd = new InputSectionDescription;
-  Cmd->FilePattern = FilePattern;
+  auto *Cmd = new InputSectionDescription(FilePattern);
   expect("(");
 
   // Read EXCLUDE_FILE().
   if (skip("EXCLUDE_FILE")) {
     expect("(");
-    while (!Error && !skip(")"))
-      Cmd->ExcludedFiles.push_back(next());
+    Cmd->ExcludedFileRe = readFilePatterns();
   }
 
   // Read SORT().
   if (SortKind K1 = readSortKind()) {
     Cmd->SortOuter = K1;
     expect("(");
     if (SortKind K2 = readSortKind()) {
       Cmd->SortInner = K2;
       expect("(");
-      Cmd->SectionPatterns = readInputFilePatterns();
+      Cmd->SectionRe = readFilePatterns();
       expect(")");
     } else {
-      Cmd->SectionPatterns = readInputFilePatterns();
+      Cmd->SectionRe = readFilePatterns();
     }
     expect(")");
     return Cmd;
   }
 
-  Cmd->SectionPatterns = readInputFilePatterns();
+  Cmd->SectionRe = readFilePatterns();
   return Cmd;
 }
 
 InputSectionDescription *
 ScriptParser::readInputSectionDescription(StringRef Tok) {
   // Input section wildcard can be surrounded by KEEP.
   // https://sourceware.org/binutils/docs/ld/Input-Section-Keep.html#Input-Section-Keep
   if (Tok == "KEEP") {
     expect("(");
     StringRef FilePattern = next();
     InputSectionDescription *Cmd = readInputSectionRules(FilePattern);
     expect(")");
-    Opt.KeptSections.insert(Opt.KeptSections.end(),
-                            Cmd->SectionPatterns.begin(),
-                            Cmd->SectionPatterns.end());
+    Opt.KeptSections.push_back(&Cmd->SectionRe);
     return Cmd;
   }
   return readInputSectionRules(Tok);
 }
 
 void ScriptParser::readSort() {
   expect("(");
   expect("CONSTRUCTORS");

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_COFF_STRINGS_H
 #define LLD_COFF_STRINGS_H
 
 #include "lld/Core/LLVM.h"
+#include "llvm/Support/Regex.h"
 #include <vector>
 
 namespace lld {
 namespace elf {
-bool globMatch(StringRef S, StringRef T);
+llvm::Regex compileGlobPatterns(ArrayRef<StringRef> V);
+bool hasWildcard(StringRef S);
 std::vector<uint8_t> parseHex(StringRef S);
 bool isValidCIdentifier(StringRef S);
 
 // 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);
 }
 }
 
 #endif

lld/trunk/ELF/Strings.cpp

 //===- Strings.cpp -------------------------------------------------------===//
 //
 //                             The LLVM Linker
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 
 #include "Strings.h"
 #include "Error.h"
+#include "llvm/ADT/ArrayRef.h"
 #include "llvm/ADT/StringRef.h"
 #include "llvm/ADT/Twine.h"
 #include "llvm/Config/config.h"
 #include <algorithm>
 
 #ifdef HAVE_CXXABI_H
 #include <cxxabi.h>
 #endif
 
 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.
-bool elf::globMatch(StringRef S, StringRef T) {
-  for (;;) {
-    if (S.empty())
-      return T.empty();
-    if (S[0] == '*') {
-      S = S.substr(1);
-      if (S.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)))
-          return true;
-      return false;
-    }
-    if (T.empty() || (S[0] != T[0] && S[0] != '?'))
-      return false;
+bool elf::hasWildcard(StringRef S) {
+  return S.find_first_of("?*") != StringRef::npos;
+
+static std::string toRegex(StringRef S) {
+  if (S.find_first_of("[]") != StringRef::npos)
+    warning("unsupported wildcard: " + S);
+
+  std::string T;
+  while (!S.empty()) {
+    char C = S.front();
+    if (C == '*')
+      T += ".*";
+    else if (C == '?')
+      T += '.';
+    else if (StringRef(".+^${}()|/\\[]").find_first_of(C) != StringRef::npos)
+      T += std::string("\\") + C;
+    else
+      T += C;
     S = S.substr(1);
-    T = T.substr(1);
   }
+  return T;
+}
+
+// Takes multiple glob patterns and converts them into regex object.
+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);

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 "llvm/ADT/DenseMap.h"
+#include "llvm/Support/Regex.h"
 
 namespace lld {
 namespace elf {
 class Lazy;
 template <class ELFT> class OutputSectionBase;
 struct Symbol;
 
 typedef llvm::CachedHash<StringRef> SymName;
public:
   void scanVersionScript();
 
   SymbolBody *find(StringRef Name);
 
   void trace(StringRef Name);
   void wrap(StringRef Name);
 
 private:
-  std::vector<SymbolBody *> findAll(StringRef Pattern);
+  std::vector<SymbolBody *> findAll(const llvm::Regex &Re);
   std::pair<Symbol *, bool> insert(StringRef &Name);
   std::pair<Symbol *, bool> insert(StringRef &Name, uint8_t Type,
                                    uint8_t Visibility, bool CanOmitFromDynSym,
                                    bool HasUnnamedAddr, InputFile *File);
 
   std::string conflictMsg(SymbolBody *Existing, InputFile *NewFile);
   void reportDuplicate(SymbolBody *Existing, InputFile *NewFile);
 

lld/trunk/ELF/SymbolTable.cpp

template <class ELFT> SymbolBody *SymbolTable<ELFT>::find(StringRef Name) {
   if (It == Symtab.end())
     return nullptr;
   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 glob pattern.
+// Returns a list of defined symbols that match with a given regex.
 template <class ELFT>
-std::vector<SymbolBody *> SymbolTable<ELFT>::findAll(StringRef Pattern) {
+std::vector<SymbolBody *> SymbolTable<ELFT>::findAll(const Regex &Re) {
   std::vector<SymbolBody *> Res;
   for (Symbol *Sym : SymVector) {
     SymbolBody *B = Sym->body();
-    if (!B->isUndefined() && globMatch(Pattern, B->getName()))
+    StringRef Name = B->getName();
+    if (!B->isUndefined() && const_cast<Regex &>(Re).match(Name))
       Res.push_back(B);
   }
   return Res;
 }
 
 template <class ELFT>
 void SymbolTable<ELFT>::addLazyArchive(ArchiveFile *F,
                                        const object::Archive::Symbol Sym) {

 // This function process the dynamic list option by marking all the symbols
 // to be exported in the dynamic table.
 template <class ELFT> void SymbolTable<ELFT>::scanDynamicList() {
   for (StringRef S : Config->DynamicList)
     if (SymbolBody *B = find(S))
       B->symbol()->ExportDynamic = true;
 }
 
-static bool hasWildcard(StringRef S) {
-  return S.find_first_of("?*") != StringRef::npos;
-}
-
 static void setVersionId(SymbolBody *Body, StringRef VersionName,
                          StringRef Name, uint16_t Version) {
   if (!Body || Body->isUndefined()) {
     if (Config->NoUndefinedVersion)
       error("version script assignment of " + VersionName + " to symbol " +
             Name + " failed: symbol not defined");
     return;
   }
static SymbolBody *findDemangled(const std::map<std::string, SymbolBody *> &D,
   auto I = D.find(Name);
   if (I != D.end())
     return I->second;
   return nullptr;
 }
 
 static std::vector<SymbolBody *>
 findAllDemangled(const std::map<std::string, SymbolBody *> &D,
-                 StringRef Pattern) {
+                 const Regex &Re) {
   std::vector<SymbolBody *> Res;
   for (auto &P : D) {
     SymbolBody *Body = P.second;
-    if (!Body->isUndefined() && globMatch(Pattern, P.first))
+    if (!Body->isUndefined() && const_cast<Regex &>(Re).match(P.first))
       Res.push_back(Body);
   }
   return Res;
 }
 
 // This function processes the --version-script option by marking all global
 // symbols with the VersionScriptGlobal flag, which acts as a filter on the
 // dynamic symbol table.
template <class ELFT> void SymbolTable<ELFT>::scanVersionScript() {
 
   // Handle wildcards.
   for (size_t I = Config->VersionDefinitions.size() - 1; I != (size_t)-1; --I) {
     VersionDefinition &V = Config->VersionDefinitions[I];
     for (SymbolVersion &Sym : V.Globals) {
       if (!hasWildcard(Sym.Name))
         continue;
       std::vector<SymbolBody *> All =
-          Sym.IsExternCpp ? findAllDemangled(Demangled, Sym.Name)
-                          : findAll(Sym.Name);
+          Sym.IsExternCpp
+              ? findAllDemangled(Demangled, compileGlobPatterns({Sym.Name}))
+              : findAll(compileGlobPatterns({Sym.Name}));
 
       for (SymbolBody *B : All)
         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>;

lld/trunk/test/ELF/wildcards2.s

+# REQUIRES: x86
+
+# RUN: llvm-mc -filetype=obj -triple=x86_64-unknown-linux %s -o %t
+## Check that aabc is not included in text.
+# RUN: echo "SECTIONS { \
+# RUN:      .text : { *(.abc) } }" > %t.script
+# RUN: ld.lld -o %t.out --script %t.script %t
+# RUN: llvm-objdump -section-headers %t.out | \
+# RUN:   FileCheck %s
+# CHECK:      Sections:
+# CHECK-NEXT:  Idx Name          Size      Address          Type
+# CHECK-NEXT:    0               00000000 0000000000000000
+# CHECK-NEXT:    1 .text         00000004 0000000000000120 TEXT DATA
+# CHECK-NEXT:    2 aabc          00000004 0000000000000124 TEXT DATA
+
+.text
+.section .abc,"ax",@progbits
+.long 0
+
+.text
+.section aabc,"ax",@progbits
+.long 0
+
+.globl _start
+_start: