LinkerScript: Add parsing of the EXTERN command

[meadori]

Summary

This patch implements parsing of the GNU ld EXTERN command [1].
Evaluation will be added at a later point in time.

[1] https://sourceware.org/binutils/docs-2.25/ld/Miscellaneous-Commands.html#Miscellaneous-Commands

[davide]

I see no problems with the patch as-is, but I'm more and more concerned about the direction LinkerScript is taking.
It seems like we keep adding support for parsing of different directives without implementing the corresponding semantic action, so this is almost-dead code.
In order to not have this gap growing I propose that at least for new directives we implement both semantic and parsing action at the same time, even in two different patches to facilitate review.

[meadori]

In D8271#139387, @davide wrote:

In order to not have this gap growing I propose that at least for new directives we implement both
semantic and parsing action at the same time, even in two different patches to facilitate review.

I did exactly that for this series. See D8272.

I did *not* do it with the MEMORY command because I believe that will take quite a bit of infrastructure to implement, but I plan to do it. For cases like MEMORY (where the eval piece is much more complicated) I think it is better to get the parsing bit out. For cases like EXTERN I think both sides should be submitted at the same time. I plan to always split the parse and eval portions into separate patches.

[davide]

Seems fine to me, but I would be happier if somebody else can take a look as well (also the semantic action).

[shankarke]

LGTM

include/lld/ReaderWriter/LinkerScript.h

enum Kind {
     libname,
     kw_align,
     kw_align_with_input,
     kw_as_needed,
     kw_at,
     kw_discard,
     kw_entry,
     kw_exclude_file,
+    kw_extern,
     kw_group,
     kw_hidden,
     kw_input,
     kw_keep,
     kw_length,
     kw_memory,
     kw_origin,
     kw_provide,

 ///              *(.interp)       /* An output-section-command */
 ///              }
 ///  }
 ///
 class Command {
 public:
   enum class Kind {
     Entry,
+    Extern,
     Group,
     Input,
     InputSectionsCmd,
     Memory,
     Output,
     OutputArch,
     OutputFormat,
     OutputSectionDescription,
public:
   }
 
   void dump(raw_ostream &os) const override;
 
 private:
   llvm::ArrayRef<const MemoryBlock *> _blocks;
 };
 
+/// Represents an extern command.
+class Extern : public Command {
+public:
+  Extern(Parser &ctx,
+         const SmallVectorImpl<StringRef> &symbols)
+      : Command(ctx, Kind::Extern) {
+    size_t numSymbols = symbols.size();
+    StringRef *symbolsStart =
+        getAllocator().Allocate<StringRef>(numSymbols);
+    std::copy(std::begin(symbols), std::end(symbols), symbolsStart);
+    _symbols = llvm::makeArrayRef(symbolsStart, numSymbols);
+  }
+
+  static bool classof(const Command *c) {
+    return c->getKind() == Kind::Extern;
+  }
+
+  void dump(raw_ostream &os) const override;
+
+private:
+  llvm::ArrayRef<StringRef> _symbols;
+};
+
 
 /// Stores the parse tree of a linker script.
 class LinkerScript {
 public:
   void dump(raw_ostream &os) const {
     for (const Command *c : _commands) {
       c->dump(os);
       if (isa<SymbolAssignment>(c))
private:
   ///   MEMORY {
   ///   ^~~~ parseMemory()
   ///     ram (rwx) : ORIGIN = 0x20000000, LENGTH = 96K
   ///     rom (rx)  : ORIGIN = 0x0,        LENGTH = 256K
   ///   }
   ///
   Memory *parseMemory();
 
+  Extern *parseExtern();
 private:
   // Owns the entire linker script AST nodes
   llvm::BumpPtrAllocator _alloc;
 
   // The top-level/entry-point linker script AST node
   LinkerScript _script;
 
   Lexer _lex;

lib/ReaderWriter/LinkerScript.cpp

case Token::name:                                                            \
     CASE(libname)
     CASE(kw_align)
     CASE(kw_align_with_input)
     CASE(kw_as_needed)
     CASE(kw_at)
     CASE(kw_discard)
     CASE(kw_entry)
     CASE(kw_exclude_file)
+    CASE(kw_extern)
     CASE(kw_group)
     CASE(kw_hidden)
     CASE(kw_input)
     CASE(kw_keep)
     CASE(kw_length)
     CASE(kw_memory)
     CASE(kw_origin)
     CASE(kw_provide)
default:
     Token::Kind kind =
         llvm::StringSwitch<Token::Kind>(word)
             .Case("ALIGN", Token::kw_align)
             .Case("ALIGN_WITH_INPUT", Token::kw_align_with_input)
             .Case("AS_NEEDED", Token::kw_as_needed)
             .Case("AT", Token::kw_at)
             .Case("ENTRY", Token::kw_entry)
             .Case("EXCLUDE_FILE", Token::kw_exclude_file)
+            .Case("EXTERN", Token::kw_extern)
             .Case("GROUP", Token::kw_group)
             .Case("HIDDEN", Token::kw_hidden)
             .Case("INPUT", Token::kw_input)
             .Case("KEEP", Token::kw_keep)
             .Case("LENGTH", Token::kw_length)
             .Case("l", Token::kw_length)
             .Case("len", Token::kw_length)
             .Case("MEMORY", Token::kw_memory)
void Memory::dump(raw_ostream &os) const {
   os << "MEMORY\n{\n";
   for (auto &block : _blocks) {
     block->dump(os);
     os << "\n";
   }
   os << "}\n";
 }
 
+// Extern functions
+void Extern::dump(raw_ostream &os) const {
+  os << "EXTERN(";
+  for (unsigned i = 0, e = _symbols.size(); i != e; ++i) {
+    if (i)
+      os << " ";
+    os << _symbols[i];
+  }
+  os << ")\n";
+}
+
+
 // Parser functions
 std::error_code Parser::parse() {
   // Get the first token.
   _lex.lex(_tok);
   // Parse top level commands.
   while (true) {
     switch (_tok._kind) {
     case Token::eof:
while (true) {
     }
     case Token::kw_memory: {
       const Command *cmd = parseMemory();
       if (!cmd)
         return LinkerScriptReaderError::parse_error;
       _script._commands.push_back(cmd);
       break;
     }
+    case Token::kw_extern: {
+      const Command *cmd = parseExtern();
+      if (!cmd)
+        return LinkerScriptReaderError::parse_error;
+      _script._commands.push_back(cmd);
+      break;
+    }
     default:
       // Unexpected.
       error(_tok, "expected linker script command");
       return LinkerScriptReaderError::parse_error;
     }
   }
   return LinkerScriptReaderError::parse_error;
 }
Memory *Parser::parseMemory() {
   if (!expectAndConsume(
           Token::r_brace,
           "expected memory block definition."))
     return nullptr;
 
   return new (_alloc) Memory(*this, blocks);
 }
 
+Extern *Parser::parseExtern() {
+  assert(_tok._kind == Token::kw_extern && "Expected EXTERN!");
+  consumeToken();
+  if (!expectAndConsume(Token::l_paren, "expected ("))
+    return nullptr;
+
+  // Parse one or more symbols.
+  SmallVector<StringRef, 8> symbols;
+  if (_tok._kind != Token::identifier) {
+    error(_tok, "expected one or more symbols in EXTERN.");
+    return nullptr;
+  }
+  symbols.push_back(_tok._range);
+  consumeToken();
+  while (_tok._kind == Token::identifier) {
+    symbols.push_back(_tok._range);
+    consumeToken();
+  }
+
+  if (!expectAndConsume(Token::r_paren, "expected symbol in EXTERN."))
+    return nullptr;
+
+  return new (_alloc) Extern(*this, symbols);
+}
+
 } // end namespace script
 } // end namespace lld

test/LinkerScript/extern-bad-symbol.test

+/*
+  RUN: linker-script-test %s 2> %t | FileCheck %s
+  RUN: FileCheck -input-file %t -check-prefix=CHECK-ERR %s
+*/
+
+
+EXTERN(a b 3)
+/*
+CHECK-ERR: [[@LINE-2]]:12: error: expected symbol in EXTERN.
+CHECK-ERR-NEXT: {{^EXTERN\(a b 3\)}}
+CHECK-ERR-NEXT: {{^          \^}}
+*/
+
+/*
+CHECK: kw_extern: EXTERN
+CHECK: l_paren: (
+CHECK: identifier: a
+CHECK: identifier: b
+CHECK: number: 3
+CHECK: r_paren: )
+CHECK: eof:
+*/

test/LinkerScript/extern-empty.test

+/*
+  RUN: linker-script-test %s 2> %t | FileCheck %s
+  RUN: FileCheck -input-file %t -check-prefix=CHECK-ERR %s
+*/
+
+
+EXTERN()
+/*
+CHECK-ERR: [[@LINE-2]]:8: error: expected one or more symbols in EXTERN.
+CHECK-ERR-NEXT: {{^EXTERN()}}
+CHECK-ERR-NEXT: {{^     \^}}
+*/
+
+/*
+CHECK: kw_extern: EXTERN
+CHECK: l_paren: (
+CHECK: r_paren: )
+CHECK: eof:
+*/

test/LinkerScript/extern-valid.test

+/*
+  RUN: linker-script-test %s | FileCheck %s
+*/
+
+EXTERN(a)
+EXTERN(a b)
+EXTERN(_foo _bar _baz)
+
+/*
+CHECK: kw_extern: EXTERN
+CHECK: l_paren: (
+CHECK: identifier: a
+CHECK: r_paren: )
+CHECK: kw_extern: EXTERN
+CHECK: l_paren: (
+CHECK: identifier: a
+CHECK: identifier: b
+CHECK: r_paren: )
+CHECK: kw_extern: EXTERN
+CHECK: l_paren: (
+CHECK: identifier: _foo
+CHECK: identifier: _bar
+CHECK: identifier: _baz
+CHECK: r_paren: )
+CHECK: eof:
+CHECK: EXTERN(a)
+CHECK: EXTERN(a b)
+CHECK: EXTERN(_foo _bar _baz)
+*/