Rewrite InputGraph's Group

[ruiu]

Summary

The aim of this patch is to reduce the excessive abstraction from
the InputGraph. We found that even a simple thing, such as sorting
input files (Mach-O) or adding a new file to the input file list
(PE/COFF), is nearly impossible with the InputGraph abstraction,
because it hides too much information behind it. As a result,
we invented complex interactions between components (e.g.
notifyProgress() mechanism) and tricky code to work around that
limitation. There were many occasions that we needed to write
awkward code.

This patch is the first step to make it cleaner. As the first step,
this removes Group class from the InputGraph. The grouping feature,
is now directly handled by the Resolver. notifyProgress is removed
since we no longer need it. I could have cleaned it up even more,
but in order to keep the patch minimum, I focused on Group.

SimpleFileNode class, a container of File objects (confusing!), is
now limited to have only one File. We shold have done this earlier.
We used to allow putting multiple File objects to FileNode.
Although SimpleFileNode usually has only one file, the Driver class
actually used that capability. I modified the Driver class a bit,
so that one FileNode is created for each input File.

We should now probably remove SimpleFileNode and directly store
File objects to the InputGraph in some way, because a container
that can contain only one object is useless. This is a TODO.

Mach-O input files are now sorted before they are passe to the
Resolver. DarwinInputGraph class is no longer needed, so removed.

PECOFF still has hacky code to add a new file to the input file list.
This will be cleaned up in another patch.

[kledzik]

The big problem I still see is that this does not fix the issue of multiple different file kinds in one InputElement.

Resolver::resolveUndefines() is still convoluted.

It would be nice if there was some way to flatten the InputElement vector into a File vector (preserving groups). And maybe a parallel set of index ranges into the File vector for where the groups are.

include/lld/Core/Resolver.h

117–119

A little weird to have this method in the middle of the data members

lib/Core/Resolver.cpp

82

undefAdded = undefAdded || handleFile(*member);

lib/ReaderWriter/MachO/MachOLinkingContext.cpp

934–937

Does isa<File> work? File is the base class for SharedLibraryFile and ArchiveLibraryFile, so I would think that isa<File> would return true for libraries? Maybe this is a case of how dynamic_cast<> and isa<> differ?

939–942

This really only works if there is one file in each input element. That is not the case for yaml input.

957

Is that expression right? Or is it only right because this is a stable_sort(). That is, if both a and b are the same type, the comparator always returns false, no matter the order of a and b.

[ruiu]

I made a change to FileNode so that a FileNode containing multiple Files in it is expanded to multiple FileNode before it's passed to the Resolver. It's not a complete fix (because FileNode is now supposed to contain strictly one file, which makes FileNode useless as a container), but it should mitigate the situation. I'll try to remove that indirection of the container in a followup patch.

I totally agree that it's nice to have a way to get a list of files in the InputGraph. This patch removes Group nesting from the Graph, so this is one step towards that.

include/lld/Core/Resolver.h

117–119

Done.

lib/Core/Resolver.cpp

82

Done.

lib/ReaderWriter/MachO/MachOLinkingContext.cpp

934–937

I initially didn't notice that, but isa<File>(file) always returned true. Thank you for pointing that out. Because of that, the lambda function passed to stable_sort returned inconsistent results, but it happened to work in my environment.

What really matters is whether a file is library or not. So I removed this function and use !isLibrary instead.

939–942

Now the YAML file containing multiple files are expanded to multiple InputElements by getReplacements.

957

The lambda function passed to stable_sort is supposed to return true only if the first argument is less (in the sense of < operator) than the second. It's totally okay that both a < b and b < a are satisfied. That means a is equivalent to b in sort order, and their original order is preserved.

[atanasyan]

include/lld/Core/LinkingContext.h

323

Maybe rename this method to something like beforeResolving() or preResolving()? A derived class can override this method for something different from sorting.

[ruiu]

include/lld/Core/LinkingContext.h

323

Currently only Mach-O uses this hook so it's named accordingly. I kind of prefer this naming over beforeResolving because it's clear what it is (currently) doing. We could change the name when we want to use it for other archs. If you want me to rename it, I can do that now, though.

[atanasyan]

include/lld/Core/LinkingContext.h

323

OK. Let's use the current name.

[ruiu]

Pre-thanksgiving ping.

[ruiu]

Ping.

[kledzik]

This still seems too complicated. But it is a step in the right direction, so LGTM.

include/lld/Core/InputGraph.h

public:
 
   /// getNextFile returns the next file that needs to be processed by
   /// the resolver. When there are no more files to be processed, an
   /// appropriate InputGraphError is returned. Ordinals are assigned
   /// to files returned by getNextFile, which means ordinals would be
   /// assigned in the way files are resolved.
   virtual ErrorOr<File &> getNextFile();
 
-  /// Notifies the current input element of Resolver made some progress on
-  /// resolving undefined symbols using the current file. Group (representing
-  /// --start-group and --end-group) uses that notification to make a decision
-  /// whether it should iterate over again or terminate or not.
-  virtual void notifyProgress();
-
   /// Adds an observer of getNextFile(). Each time a new file is about to be
   /// returned from getNextFile(), registered observers are called with the file
   /// being returned.
   void registerObserver(std::function<void(File *)>);
 
   /// \brief Adds a node into the InputGraph
   void addInputElement(std::unique_ptr<InputElement>);
 
   /// \brief Adds a node at the beginning of the InputGraph
   void addInputElementFront(std::unique_ptr<InputElement>);
 
-  /// Normalize the InputGraph. It calls expand() on each node and then replace
-  /// it with getReplacements() results.
+  /// Normalize the InputGraph. It calls getReplacements() on each element.
   void normalize();
 
-  range<InputElementIterT> inputElements() {
-    return make_range(_inputArgs.begin(), _inputArgs.end());
+  InputElementVectorT &inputElements() {
+    return _inputArgs;
   }
 
+  // Returns the current group size if we are at an --end-group.
+  // Otherwise returns 0.
+  int getGroupSize();
+  void skipGroup();
+
   // \brief Returns the number of input files.
   size_t size() const { return _inputArgs.size(); }
 
   /// \brief Dump the input Graph
   bool dump(raw_ostream &diagnostics = llvm::errs());
 
 protected:
   // Input arguments
   InputElementVectorT _inputArgs;
   // Index of the next element to be processed
   uint32_t _nextElementIndex;
   InputElement *_currentInputElement;
   std::vector<std::function<void(File *)>> _observers;
 
 private:
   ErrorOr<InputElement *> getNextInputElement();
 };
 
 /// \brief This describes each element in the InputGraph. The Kind
 /// determines what the current node contains.
 class InputElement {
 public:
   /// Each input element in the graph can be a File or a control
   enum class Kind : uint8_t {
-    Group,      // Represents a type associated with Group
-    File        // Represents a type associated with File Nodes
+    File,       // Represents a type associated with File Nodes
+    GroupEnd,
   };
 
   InputElement(Kind type) : _kind(type) {}
   virtual ~InputElement() {}
 
   /// Return the Element Type for an Input Element
   virtual Kind kind() const { return _kind; }
 
   /// \brief Dump the Input Element
   virtual bool dump(raw_ostream &diagnostics) { return true; }
 
   /// \brief parse the input element
   virtual std::error_code parse(const LinkingContext &, raw_ostream &) = 0;
 
   /// \brief functions for the resolver to use
 
   /// Get the next file to be processed by the resolver
   virtual ErrorOr<File &> getNextFile() = 0;
 
-  /// Refer InputGraph::notifyProgress(). By default, it does nothing. Only
-  /// Group is interested in this message.
-  virtual void notifyProgress() {};
-
   /// \brief Reset the next index
   virtual void resetNextIndex() = 0;
 
-  /// Returns true if we want to replace this node with children.
-  virtual void expand() {}
-
   /// Get the elements that we want to expand with.
   virtual bool getReplacements(InputGraph::InputElementVectorT &) {
     return false;
   }
 
 protected:
   Kind _kind; // The type of the Element
 };
 
-/// \brief A Control node which contains a group of InputElements
-/// This affects the resolver so that it resolves undefined symbols
-/// in the group completely before looking at other input files that
-/// follow the group
-class Group : public InputElement {
+// This is a marker for --end-group. getSize() returns the number of
+// files between the corresponding --start-group and this marker.
+class GroupEnd : public InputElement {
 public:
-  Group()
-      : InputElement(InputElement::Kind::Group), _currentElementIndex(0),
-        _nextElementIndex(0), _madeProgress(false) {}
-
-  static inline bool classof(const InputElement *a) {
-    return a->kind() == InputElement::Kind::Group;
-  }
+  GroupEnd(int size) : InputElement(Kind::GroupEnd), _size(size) {}
 
-  /// \brief Process input element and add it to the group
-  bool addFile(std::unique_ptr<InputElement> element) {
-    _elements.push_back(std::move(element));
-    return true;
-  }
-
-  range<InputGraph::InputElementIterT> elements() {
-    return make_range(_elements.begin(), _elements.end());
-  }
+  int getSize() const { return _size; }
 
-  void resetNextIndex() override {
-    _madeProgress = false;
-    _currentElementIndex = 0;
-    _nextElementIndex = 0;
-    for (std::unique_ptr<InputElement> &elem : _elements)
-      elem->resetNextIndex();
+  static inline bool classof(const InputElement *a) {
+    return a->kind() == Kind::GroupEnd;
   }
 
   /// \brief Parse the group members.
   std::error_code parse(const LinkingContext &ctx, raw_ostream &diag) override {
-    for (std::unique_ptr<InputElement> &ei : _elements)
-      if (std::error_code ec = ei->parse(ctx, diag))
-        return ec;
     return std::error_code();
   }
 
-  /// If Resolver made a progress using the current file, it's ok to revisit
-  /// files in this group in future.
-  void notifyProgress() override {
-    for (std::unique_ptr<InputElement> &elem : _elements)
-      elem->notifyProgress();
-    _madeProgress = true;
-  }
-
-  ErrorOr<File &> getNextFile() override;
-
-  void expand() override {
-    for (std::unique_ptr<InputElement> &elt : _elements)
-      elt->expand();
-    std::vector<std::unique_ptr<InputElement>> result;
-    for (std::unique_ptr<InputElement> &elt : _elements) {
-      if (elt->getReplacements(result))
-        continue;
-      result.push_back(std::move(elt));
-    }
-    _elements.swap(result);
+  ErrorOr<File &> getNextFile() override {
+    llvm_unreachable("shouldn't be here.");
   }
 
-protected:
-  InputGraph::InputElementVectorT _elements;
-  uint32_t _currentElementIndex;
-  uint32_t _nextElementIndex;
-  bool _madeProgress;
+  void resetNextIndex() override {}
+
+private:
+  int _size;
 };
 
 /// \brief Represents an Input file in the graph
 ///
 /// This class represents an input to the linker. It create the MemoryBuffer
 /// lazily when needed based on the file path. It can also take a MemoryBuffer
 /// directly.
 class FileNode : public InputElement {
public:
 
   /// \brief Get the list of files
   range<InputGraph::FileIterT> files() {
     return make_range(_files.begin(), _files.end());
   }
 
   /// \brief add a file to the list of files
   virtual void addFiles(InputGraph::FileVectorT files) {
+    assert(files.size() == 1);
+    assert(_files.empty());
     for (std::unique_ptr<File> &ai : files)
       _files.push_back(std::move(ai));
   }
 
   /// \brief Reset the file index if the resolver needs to process
   /// the node again.
   void resetNextIndex() override { _nextFileIndex = 0; }
 
+  bool getReplacements(InputGraph::InputElementVectorT &result) override;
+
 protected:
   /// \brief Read the file into _buffer.
   std::error_code getBuffer(StringRef filePath);
 
   StringRef _path;                       // The path of the Input file
   InputGraph::FileVectorT _files;        // A vector of lld File objects
   std::unique_ptr<MemoryBuffer> _buffer; // Memory buffer to actual contents
 
   // The next file that would be processed by the resolver
   uint32_t _nextFileIndex;
 };
 
 /// \brief Represents Internal Input files
 class SimpleFileNode : public FileNode {
 public:
   SimpleFileNode(StringRef path) : FileNode(path) {}
+  SimpleFileNode(StringRef path, std::unique_ptr<File> f)
+      : FileNode(path) {
+    _files.push_back(std::move(f));
+  }
 
   virtual ~SimpleFileNode() {}
 
   /// \brief add a file to the list of files
   virtual void appendInputFile(std::unique_ptr<File> f) {
     _files.push_back(std::move(f));
   }
 

include/lld/Core/LinkingContext.h

public:
   /// Calls through to the writeFile() method on the specified Writer.
   ///
   /// \param linkedFile This is the merged/linked graph of all input file Atoms.
   virtual std::error_code writeFile(const File &linkedFile) const;
 
   /// Return the next ordinal and Increment it.
   virtual uint64_t getNextOrdinalAndIncrement() const { return _nextOrdinal++; }
 
+  // This function is called just before the Resolver kicks in.
+  // Derived classes may use that chance to rearrange the input files.
+  virtual void maybeSortInputFiles() {}
+
   /// @}
 
 protected:
   LinkingContext(); // Must be subclassed
 
   /// Abstract method to lazily instantiate the Writer.
   virtual Writer &writer() const = 0;
 

include/lld/Core/Resolver.h

 class Atom;
 class LinkingContext;
 
 /// \brief The Resolver is responsible for merging all input object files
 /// and producing a merged graph.
 class Resolver {
 public:
   Resolver(LinkingContext &context)
-      : _context(context), _symbolTable(context), _result(new MergedFile()) {}
+      : _context(context), _symbolTable(context), _result(new MergedFile()),
+        _fileIndex(0) {}
 
   // InputFiles::Handler methods
   void doDefinedAtom(const DefinedAtom&);
   bool doUndefinedAtom(const UndefinedAtom &);
   void doSharedLibraryAtom(const SharedLibraryAtom &);
   void doAbsoluteAtom(const AbsoluteAtom &);
 
   // Handle files, this adds atoms from the current file thats
   // being processed by the resolver
-  void handleFile(const File &);
+  bool handleFile(const File &);
 
   // Handle an archive library file.
-  void handleArchiveFile(const File &);
+  bool handleArchiveFile(const File &);
 
   // Handle a shared library file.
   void handleSharedLibrary(const File &);
 
   /// @brief do work of merging and resolving and return list
   bool resolve();
 
   std::unique_ptr<MutableFile> resultFile() { return std::move(_result); }
 
 private:
   typedef std::function<void(StringRef, bool)> UndefCallback;
 
+  bool undefinesAdded(int count);
+  ErrorOr<File &> nextFile(bool &inGroup);
+
   /// \brief Add section group/.gnu.linkonce if it does not exist previously.
   void maybeAddSectionGroupOrGnuLinkOnce(const DefinedAtom &atom);
 
   /// \brief The main function that iterates over the files to resolve
   bool resolveUndefines();
   void updateReferences();
   void deadStripOptimize();
   bool checkUndefines();
private:
   LinkingContext &_context;
   SymbolTable _symbolTable;
   std::vector<const Atom *>     _atoms;
   std::set<const Atom *>        _deadStripRoots;
   llvm::DenseSet<const Atom *>  _liveAtoms;
   llvm::DenseSet<const Atom *>  _deadAtoms;
   std::unique_ptr<MergedFile>   _result;
   llvm::DenseMap<const Atom *, llvm::DenseSet<const Atom *>> _reverseRef;
+
+  // --start-group and --end-group
+  std::vector<File *> _files;
+  std::map<File *, bool> _newUndefinesAdded;
+  size_t _fileIndex;
 };
 
 } // namespace lld
 
 #endif // LLD_CORE_RESOLVER_H

include/lld/Driver/DarwinInputGraph.h

 #define LLD_DRIVER_DARWIN_INPUT_GRAPH_H
 
 #include "lld/Core/ArchiveLibraryFile.h"
 #include "lld/Core/InputGraph.h"
 #include "lld/ReaderWriter/MachOLinkingContext.h"
 
 namespace lld {
 
-
-class DarwinInputGraph : public InputGraph {
-public:
-  DarwinInputGraph() : _librariesPhase(false), _repeatLibraries(false) { }
-  ErrorOr<File &> getNextFile() override;
-  void notifyProgress() override;
-private:
-  bool _librariesPhase;
-  bool _repeatLibraries;
-};
-
-
 /// \brief Represents a MachO File
 class MachOFileNode : public FileNode {
 public:
   MachOFileNode(StringRef path, MachOLinkingContext &ctx)
       : FileNode(path), _context(ctx), _isWholeArchive(false),
         _upwardDylib(false) {}
 
   /// \brief Parse the input file to lld::File.

include/lld/Driver/WinLinkInputGraph.h

 class PECOFFLibraryNode : public PECOFFFileNode {
 public:
   PECOFFLibraryNode(PECOFFLinkingContext &ctx, StringRef path)
       : PECOFFFileNode(ctx, path) {}
 
   ErrorOr<StringRef> getPath(const LinkingContext &ctx) const override;
 };
 
-/// \brief Represents a ELF control node
-class PECOFFGroup : public Group {
-public:
-  PECOFFGroup(PECOFFLinkingContext &ctx) : Group(), _ctx(ctx) {}
-
-  /// \brief Parse the group members.
-  std::error_code parse(const LinkingContext &ctx, raw_ostream &diag) override {
-    std::lock_guard<std::recursive_mutex> lock(_ctx.getMutex());
-    return Group::parse(ctx, diag);
-  }
-
-private:
-  PECOFFLinkingContext &_ctx;
-};
-
 } // namespace lld
 
 #endif

include/lld/ReaderWriter/MachOLinkingContext.h

public:
   static bool is64Bit(Arch arch);
   static bool isHostEndian(Arch arch);
   static bool isBigEndian(Arch arch);
 
   /// Construct 32-bit value from string "X.Y.Z" where
   /// bits are xxxx.yy.zz.  Largest number is 65535.255.255
   static bool parsePackedVersion(StringRef str, uint32_t &result);
 
+  void maybeSortInputFiles() override;
+
 private:
   Writer &writer() const override;
   mach_o::MachODylibFile* loadIndirectDylib(StringRef path);
   void checkExportWhiteList(const DefinedAtom *atom) const;
   void checkExportBlackList(const DefinedAtom *atom) const;
   bool customAtomOrderer(const DefinedAtom *left, const DefinedAtom *right,
                          bool &leftBeforeRight);
   struct ArchInfo {

include/lld/ReaderWriter/PECOFFLinkingContext.h

 #include <vector>
 
 using llvm::COFF::MachineTypes;
 using llvm::COFF::WindowsSubsystem;
 
 static const uint8_t DEFAULT_DOS_STUB[128] = {'M', 'Z'};
 
 namespace lld {
-class Group;
 
 class PECOFFLinkingContext : public LinkingContext {
 public:
   PECOFFLinkingContext()
       : _mutex(), _allocMutex(), _hasEntry(true),
         _baseAddress(invalidBaseAddress), _stackReserve(1024 * 1024),
         _stackCommit(4096), _heapReserve(1024 * 1024), _heapCommit(4096),
         _noDefaultLibAll(false), _sectionDefaultAlignment(4096),
template <typename T> T &allocateCopy(const T &x) const {
     return *r;
   }
 
   virtual bool hasInputGraph() { return !!_inputGraph; }
 
   void setEntryNode(SimpleFileNode *node) { _entryNode = node; }
   SimpleFileNode *getEntryNode() const { return _entryNode; }
 
-  void setLibraryGroup(Group *group) { _libraryGroup = group; }
-  Group *getLibraryGroup() const { return _libraryGroup; }
+  void addLibraryFile(std::unique_ptr<FileNode> file);
 
   void setModuleDefinitionFile(const std::string val) {
     _moduleDefinitionFile = val;
   }
   std::string getModuleDefinitionFile() const {
     return _moduleDefinitionFile;
   }
 
private:
   // Windows loader do not really care about DOS stub contents, but it's usually
   // a small DOS program that prints out a message "This program requires
   // Microsoft Windows." This feature was somewhat useful before Windows 95.
   ArrayRef<uint8_t> _dosStub;
 
   // The node containing the entry point file.
   SimpleFileNode *_entryNode;
 
-  // The PECOFFGroup that contains all the .lib files.
-  Group *_libraryGroup;
-
   // Name of the temporary file for lib.exe subcommand. For debugging
   // only.
   std::string _moduleDefinitionFile;
 };
 
 } // end namespace lld
 
 #endif

lib/Core/InputGraph.cpp

for (;;) {
 
     ErrorOr<InputElement *> elt = getNextInputElement();
     if (elt.getError() == InputGraphError::no_more_elements || *elt == nullptr)
       return make_error_code(InputGraphError::no_more_files);
     _currentInputElement = *elt;
   }
 }
 
-void InputGraph::notifyProgress() { _currentInputElement->notifyProgress(); }
-
 void InputGraph::registerObserver(std::function<void(File *)> fn) {
   _observers.push_back(fn);
 }
 
 void InputGraph::addInputElement(std::unique_ptr<InputElement> ie) {
   _inputArgs.push_back(std::move(ie));
 }
 
 void InputGraph::addInputElementFront(std::unique_ptr<InputElement> ie) {
   _inputArgs.insert(_inputArgs.begin(), std::move(ie));
 }
 
 bool InputGraph::dump(raw_ostream &diagnostics) {
   for (std::unique_ptr<InputElement> &ie : _inputArgs)
     if (!ie->dump(diagnostics))
       return false;
   return true;
 }
 
 /// \brief Helper functions for the resolver
 ErrorOr<InputElement *> InputGraph::getNextInputElement() {
   if (_nextElementIndex >= _inputArgs.size())
     return make_error_code(InputGraphError::no_more_elements);
-  return _inputArgs[_nextElementIndex++].get();
+  InputElement *elem = _inputArgs[_nextElementIndex++].get();
+  if (isa<GroupEnd>(elem))
+    return getNextInputElement();
+  return elem;
 }
 
 void InputGraph::normalize() {
-  for (std::unique_ptr<InputElement> &elt : _inputArgs)
-    elt->expand();
   std::vector<std::unique_ptr<InputElement>> vec;
   for (std::unique_ptr<InputElement> &elt : _inputArgs) {
     if (elt->getReplacements(vec))
       continue;
     vec.push_back(std::move(elt));
   }
   _inputArgs = std::move(vec);
 }
 
+// If we are at the end of a group, return its size (which indicates
+// how many files we need to go back in the command line).
+// Returns 0 if we are not at the end of a group.
+int InputGraph::getGroupSize() {
+  if (_nextElementIndex >= _inputArgs.size())
+    return 0;
+  InputElement *elem = _inputArgs[_nextElementIndex].get();
+  if (const GroupEnd *group = dyn_cast<GroupEnd>(elem))
+    return group->getSize();
+  return 0;
+}
+
+void InputGraph::skipGroup() {
+  if (_nextElementIndex >= _inputArgs.size())
+    return;
+  if (isa<GroupEnd>(_inputArgs[_nextElementIndex].get()))
+    _nextElementIndex++;
+}
+
 /// \brief Read the file into _buffer.
 std::error_code FileNode::getBuffer(StringRef filePath) {
   // Create a memory buffer
   ErrorOr<std::unique_ptr<MemoryBuffer>> mb =
       MemoryBuffer::getFileOrSTDIN(filePath);
   if (std::error_code ec = mb.getError())
     return ec;
   _buffer = std::move(mb.get());
   return std::error_code();
 }
 
-/// \brief Return the next file that need to be processed by the resolver.
-/// This also processes input elements depending on the resolve status
-/// of the input elements contained in the group.
-ErrorOr<File &> Group::getNextFile() {
-  // If there are no elements, move on to the next input element
-  if (_elements.empty())
-    return make_error_code(InputGraphError::no_more_files);
-
-  for (;;) {
-    // If we have processed all the elements, and have made no progress on
-    // linking, we cannot resolve any symbol from this group. Continue to the
-    // next one by returning no_more_files.
-    if (_nextElementIndex == _elements.size()) {
-      if (!_madeProgress)
-        return make_error_code(InputGraphError::no_more_files);
-      resetNextIndex();
-    }
-
-    _currentElementIndex = _nextElementIndex;
-    auto file = _elements[_nextElementIndex]->getNextFile();
-    // Move on to the next element if we have finished processing all
-    // the files in the input element
-    if (file.getError() == InputGraphError::no_more_files) {
-      _nextElementIndex++;
-      continue;
-    }
-    return *file;
-  }
+bool FileNode::getReplacements(InputGraph::InputElementVectorT &result) {
+  if (_files.size() < 2)
+    return false;
+  for (std::unique_ptr<File> &file : _files)
+    result.push_back(llvm::make_unique<SimpleFileNode>(_path, std::move(file)));
+  return true;
 }

lib/Core/Resolver.cpp

 #include "llvm/Support/Format.h"
 #include "llvm/Support/raw_ostream.h"
 #include <algorithm>
 #include <cassert>
 #include <vector>
 
 namespace lld {
 
-void Resolver::handleFile(const File &file) {
+bool Resolver::handleFile(const File &file) {
   bool undefAdded = false;
   for (const DefinedAtom *atom : file.defined())
     doDefinedAtom(*atom);
   for (const UndefinedAtom *atom : file.undefined())
     if (doUndefinedAtom(*atom))
       undefAdded = true;
   for (const SharedLibraryAtom *atom : file.sharedLibrary())
     doSharedLibraryAtom(*atom);
   for (const AbsoluteAtom *atom : file.absolute())
     doAbsoluteAtom(*atom);
-
-  // Notify the input file manager of the fact that we have made some progress
-  // on linking using the current input file. It may want to know the fact for
-  // --start-group/--end-group.
-  if (undefAdded) {
-    _context.getInputGraph().notifyProgress();
-  }
+  return undefAdded;
 }
 
 void Resolver::forEachUndefines(bool searchForOverrides,
                                 UndefCallback callback) {
   // Handle normal archives
   unsigned undefineGenCount = 0;
   do {
     undefineGenCount = _symbolTable.size();
if (searchForOverrides) {
           if (curDefAtom->merge() == DefinedAtom::mergeAsTentative)
             callback(tentDefName, true);
         }
       }
     }
   } while (undefineGenCount != _symbolTable.size());
 }
 
-void Resolver::handleArchiveFile(const File &file) {
+bool Resolver::handleArchiveFile(const File &file) {
   const ArchiveLibraryFile *archiveFile = cast<ArchiveLibraryFile>(&file);
   bool searchForOverrides =
       _context.searchArchivesToOverrideTentativeDefinitions();
+  bool undefAdded = false;
   forEachUndefines(searchForOverrides,
                    [&](StringRef undefName, bool dataSymbolOnly) {
     if (const File *member = archiveFile->find(undefName, dataSymbolOnly)) {
       member->setOrdinal(_context.getNextOrdinalAndIncrement());
-      handleFile(*member);
+      undefAdded = undefAdded || handleFile(*member);
     }
   });
+  return undefAdded;
 }
 
 void Resolver::handleSharedLibrary(const File &file) {
   // Add all the atoms from the shared library
   const SharedLibraryFile *sharedLibrary = cast<SharedLibraryFile>(&file);
   handleFile(*sharedLibrary);
   bool searchForOverrides =
       _context.searchSharedLibrariesToOverrideTentativeDefinitions();

 }
 
 // utility to add a vector of atoms
 void Resolver::addAtoms(const std::vector<const DefinedAtom *> &newAtoms) {
   for (const DefinedAtom *newAtom : newAtoms)
     doDefinedAtom(*newAtom);
 }
 
+// Returns true if at least one of N previous files has created an
+// undefined symbol.
+bool Resolver::undefinesAdded(int n) {
+  for (size_t i = _fileIndex - n; i < _fileIndex; ++i)
+    if (_newUndefinesAdded[_files[i]])
+      return true;
+  return false;
+}
+
+ErrorOr<File &> Resolver::nextFile(bool &inGroup) {
+  if (size_t groupSize = _context.getInputGraph().getGroupSize()) {
+    // We are at the end of the current group. If one or more new
+    // undefined atom has been added in the last groupSize files, we
+    // reiterate over the files.
+    if (undefinesAdded(groupSize))
+      _fileIndex -= groupSize;
+    _context.getInputGraph().skipGroup();
+    return nextFile(inGroup);
+  }
+  if (_fileIndex < _files.size()) {
+    // We are still in the current group.
+    inGroup = true;
+    return *_files[_fileIndex++];
+  }
+  // We are not in a group. Get a new file.
+  ErrorOr<File &> file = _context.getInputGraph().getNextFile();
+  if (std::error_code ec = file.getError()) {
+    if (ec != InputGraphError::no_more_files)
+      llvm::errs() << "Error occurred in getNextFile: " << ec.message() << "\n";
+    return ec;
+  }
+  _files.push_back(&*file);
+  ++_fileIndex;
+  inGroup = false;
+  return *file;
+}
+
 // Keep adding atoms until _context.getNextFile() returns an error. This
 // function is where undefined atoms are resolved.
 bool Resolver::resolveUndefines() {
   ScopedTask task(getDefaultDomain(), "resolveUndefines");
 
   for (;;) {
-    ErrorOr<File &> file = _context.getInputGraph().getNextFile();
-    std::error_code ec = file.getError();
-    if (ec == InputGraphError::no_more_files)
-      return true;
-    if (!file) {
-      llvm::errs() << "Error occurred in getNextFile: " << ec.message() << "\n";
-      return false;
-    }
-
+    bool inGroup = false;
+    bool undefAdded = false;
+    ErrorOr<File &> file = nextFile(inGroup);
+    if (std::error_code ec = file.getError())
+      return ec == InputGraphError::no_more_files;
     switch (file->kind()) {
     case File::kindObject:
+      if (inGroup)
+        break;
       assert(!file->hasOrdinal());
       file->setOrdinal(_context.getNextOrdinalAndIncrement());
-      handleFile(*file);
+      undefAdded = handleFile(*file);
       break;
     case File::kindArchiveLibrary:
       if (!file->hasOrdinal())
         file->setOrdinal(_context.getNextOrdinalAndIncrement());
-      handleArchiveFile(*file);
+      undefAdded = handleArchiveFile(*file);
       break;
     case File::kindSharedLibrary:
       if (!file->hasOrdinal())
         file->setOrdinal(_context.getNextOrdinalAndIncrement());
       handleSharedLibrary(*file);
       break;
     }
+    _newUndefinesAdded[&*file] = undefAdded;
   }
 }
 
 // switch all references to undefined or coalesced away atoms
 // to the new defined atom
 void Resolver::updateReferences() {
   ScopedTask task(getDefaultDomain(), "updateReferences");
   for (const Atom *atom : _atoms) {

lib/Driver/DarwinInputGraph.cpp

 #include "lld/Core/File.h"
 #include "lld/Core/LLVM.h"
 #include "lld/Core/Reference.h"
 #include "lld/Core/SharedLibraryFile.h"
 
 namespace lld {
 
 
-ErrorOr<File &> DarwinInputGraph::getNextFile() {
-  // The darwin linker processes input files in two phases.  The first phase
-  // links in all object (.o) files in command line order. The second phase
-  // links in libraries in command line order. If there are still UndefinedAtoms
-  // the second phase is repeated until notifyProgress() is not called by
-  // resolver.
-  for (;;) {
-    if (_currentInputElement) {
-      for(;;) {
-        ErrorOr<File &> next = _currentInputElement->getNextFile();
-        if (next.getError())
-          break;
-        File *file = &next.get();
-        bool fileIsLibrary = isa<SharedLibraryFile>(file) ||
-                             isa<ArchiveLibraryFile>(file);
-        if (fileIsLibrary == _librariesPhase) {
-          // Return library in library phase and object files in non-lib mode.
-          return *file;
-        }
-      }
-    }
-
-    if (_nextElementIndex >= _inputArgs.size()) {
-      // If no more elements, done unless we need to repeat library scan.
-      if (_librariesPhase && !_repeatLibraries)
-        return make_error_code(InputGraphError::no_more_files);
-      // Clear iterations and only look for libraries.
-      _librariesPhase = true;
-      _repeatLibraries = false;
-      _nextElementIndex = 0;
-      for (auto &ie : _inputArgs) {
-        ie->resetNextIndex();
-      }
-    }
-    _currentInputElement = _inputArgs[_nextElementIndex++].get();
-  }
-}
-
-void DarwinInputGraph::notifyProgress() {
-  _repeatLibraries = true;
-}
-
 /// \brief Parse the input file to lld::File.
 std::error_code MachOFileNode::parse(const LinkingContext &ctx,
                                      raw_ostream &diagnostics)  {
   ErrorOr<StringRef> filePath = getPath(ctx);
   if (std::error_code ec = filePath.getError())
     return ec;
 
   if (std::error_code ec = getBuffer(*filePath))

lib/Driver/DarwinLdDriver.cpp

if (sep != '/') {
     std::string fixedPath = path;
     std::replace(fixedPath.begin(), fixedPath.end(), sep, '/');
     return fixedPath;
   } else {
     return path;
   }
 }
 
-static void addFile(StringRef path, std::unique_ptr<DarwinInputGraph> &inputGraph,
+static void addFile(StringRef path, std::unique_ptr<InputGraph> &inputGraph,
                     MachOLinkingContext &ctx, bool loadWholeArchive,
                     bool upwardDylib) {
   auto node = llvm::make_unique<MachOFileNode>(path, ctx);
   if (loadWholeArchive)
     node->setLoadWholeArchive();
   if (upwardDylib)
     node->setUpwardDylib();
   inputGraph->addInputElement(std::move(node));

 // In this variant, the path is to a text file which contains one file path
 // per line.  There are no comments or trimming of whitespace.
 //
 //   -fileList <path>,<dir>
 // In this variant, the path is to a text file which contains a partial path
 // per line. The <dir> prefix is prepended to each partial path.
 //
 static std::error_code parseFileList(StringRef fileListPath,
-                                     std::unique_ptr<DarwinInputGraph> &inputGraph,
+                                     std::unique_ptr<InputGraph> &inputGraph,
                                      MachOLinkingContext &ctx, bool forceLoad,
                                      raw_ostream &diagnostics) {
   // If there is a comma, split off <dir>.
   std::pair<StringRef, StringRef> opt = fileListPath.split(',');
   StringRef filePath = opt.first;
   StringRef dirName = opt.second;
   ctx.addInputFileDependency(filePath);
   // Map in file list file.
if (parsedArgs->getLastArg(OPT_test_file_usage)) {
     ctx.setDoNothing(true);
 
     // Only bother looking for an existence override if we're going to use it.
     for (auto existingPath : parsedArgs->filtered(OPT_path_exists)) {
       ctx.addExistingPathForDebug(existingPath->getValue());
     }
   }
 
-  std::unique_ptr<DarwinInputGraph> inputGraph(new DarwinInputGraph());
+  std::unique_ptr<InputGraph> inputGraph(new InputGraph());
 
   // Now construct the set of library search directories, following ld64's
   // baroque set of accumulated hacks. Mostly, the algorithm constructs
   //     { syslibroots } x { libpaths }
   //
   // Unfortunately, there are numerous exceptions:
   //   1. Only absolute paths get modified by syslibroot options.
   //   2. If there is just 1 -syslibroot, system paths not found in it are

lib/Driver/Driver.cpp

tg.spawn([&] {
       // We buffer the diagnostics output to a separate string-backed output
       // stream, acquire the lock, and then print it out.
       std::string buf;
       llvm::raw_string_ostream stream(buf);
 
       if (std::error_code ec = ie->parse(context, stream)) {
         if (FileNode *fileNode = dyn_cast<FileNode>(ie.get()))
           stream << fileNode->errStr(ec) << "\n";
-        else if (dyn_cast<Group>(ie.get()))
-          // FIXME: We need a better diagnostics here
-          stream << "Cannot parse group input element\n";
         else
           llvm_unreachable("Unknown type of input element");
         fail = true;
       }
 
       stream.flush();
       if (!buf.empty()) {
         std::lock_guard<std::mutex> lock(diagnosticsMutex);
         diagnostics << buf;
       }
     });
   }
   tg.sync();
   readTask.end();
 
   if (fail)
     return false;
 
-  std::unique_ptr<SimpleFileNode> fileNode(
-      new SimpleFileNode("Internal Files"));
-
   InputGraph::FileVectorT internalFiles;
   context.createInternalFiles(internalFiles);
-
-  if (internalFiles.size())
-    fileNode->addFiles(std::move(internalFiles));
+  for (auto i = internalFiles.rbegin(), e = internalFiles.rend(); i != e; ++i) {
+    context.getInputGraph().addInputElementFront(
+        llvm::make_unique<SimpleFileNode>("internal", std::move(*i)));
+  }
 
   // Give target a chance to add files.
   InputGraph::FileVectorT implicitFiles;
   context.createImplicitFiles(implicitFiles);
-  if (implicitFiles.size())
-    fileNode->addFiles(std::move(implicitFiles));
-  context.getInputGraph().addInputElementFront(std::move(fileNode));
+  for (auto i = implicitFiles.rbegin(), e = implicitFiles.rend(); i != e; ++i) {
+    context.getInputGraph().addInputElementFront(
+        llvm::make_unique<SimpleFileNode>("implicit", std::move(*i)));
+  }
+
+  // Give target a chance to sort the input files.
+  // Mach-O uses this chance to move all object files before library files.
+  context.maybeSortInputFiles();
 
   // Do core linking.
   ScopedTask resolveTask(getDefaultDomain(), "Resolve");
   Resolver resolver(context);
   if (!resolver.resolve())
     return false;
   std::unique_ptr<MutableFile> merged = resolver.resultFile();
   resolveTask.end();

lib/Driver/GnuLdDriver.cpp

bool GnuLdDriver::parse(int argc, const char *argv[],
   std::unique_ptr<ELFLinkingContext> ctx(ELFLinkingContext::create(triple));
 
   if (!ctx) {
     diagnostics << "unknown target triple\n";
     return false;
   }
 
   std::unique_ptr<InputGraph> inputGraph(new InputGraph());
-  std::stack<Group *> groupStack;
+  std::stack<int> groupStack;
+  int numfiles = 0;
 
   ELFFileNode::Attributes attributes;
 
   bool _outputOptionSet = false;
 
   // Ignore unknown arguments.
   for (auto unknownArg : parsedArgs->filtered(OPT_UNKNOWN))
     diagnostics << "warning: ignoring unknown argument: "
case OPT_defsym: {
         ctx->addAlias(sym, target);
       } else {
         diagnostics << "invalid --defsym: " << inputArg->getValue() << "\n";
         return false;
       }
       break;
     }
 
-    case OPT_start_group: {
-      std::unique_ptr<Group> group(new Group());
-      groupStack.push(group.get());
-      inputGraph->addInputElement(std::move(group));
+    case OPT_start_group:
+      groupStack.push(numfiles);
       break;
-    }
 
-    case OPT_end_group:
+    case OPT_end_group: {
+      if (groupStack.empty()) {
+        diagnostics << "stray --end-group\n";
+        return false;
+      }
+      int startGroupPos = groupStack.top();
+      inputGraph->addInputElement(
+          llvm::make_unique<GroupEnd>(numfiles - startGroupPos));
       groupStack.pop();
       break;
+    }
 
     case OPT_z: {
       StringRef extOpt = inputArg->getValue();
       if (extOpt == "muldefs")
         ctx->setAllowDuplicates(true);
       else if (extOpt.startswith("max-page-size")) {
         // Parse -z max-page-size option.
         // The default page size is considered the minimum page size the user
case OPT_l: {
         inputNode = new ELFGNULdScript(*ctx, resolvedInputPath);
         ec = inputNode->parse(*ctx, diagnostics);
         if (ec) {
           diagnostics << userPath << ": Error parsing linker script\n";
           return false;
         }
       }
       std::unique_ptr<InputElement> inputFile(inputNode);
-      if (groupStack.empty()) {
-        inputGraph->addInputElement(std::move(inputFile));
-      } else {
-        groupStack.top()->addFile(std::move(inputFile));
-      }
+      ++numfiles;
       break;
     }
 
     case OPT_rpath: {
       SmallVector<StringRef, 2> rpaths;
       StringRef(inputArg->getValue()).split(rpaths, ":");
       for (auto path : rpaths)
         ctx->addRpath(path);

lib/Driver/GnuLdInputGraph.cpp

if (std::error_code ec = GNULdScript::parse(ctx, diagnostics))
     return ec;
   StringRef sysRoot = _elfLinkingContext.getSysroot();
   if (!sysRoot.empty() && isPathUnderSysroot(sysRoot, *getPath(ctx)))
     attributes.setSysRooted(true);
   for (const script::Command *c : _linkerScript->_commands) {
     auto *group = dyn_cast<script::Group>(c);
     if (!group)
       continue;
-    std::unique_ptr<Group> groupStart(new Group());
+    size_t numfiles = 0;
     for (const script::Path &path : group->getPaths()) {
       // TODO : Propagate Set WholeArchive/dashlPrefix
       attributes.setAsNeeded(path._asNeeded);
       attributes.setDashlPrefix(path._isDashlPrefix);
       auto inputNode = new ELFFileNode(
           _elfLinkingContext, _elfLinkingContext.allocateString(path._path),
           attributes);
       std::unique_ptr<InputElement> inputFile(inputNode);
-      groupStart.get()->addFile(std::move(inputFile));
+      _expandElements.push_back(std::move(inputFile));
+      ++numfiles;
     }
-    _expandElements.push_back(std::move(groupStart));
+    _expandElements.push_back(llvm::make_unique<GroupEnd>(numfiles));
   }
   return std::error_code();
 }

lib/Driver/WinLinkDriver.cpp

 }
 
 // Returns true if the given file node has already been added to the input
 // graph.
 static bool hasLibrary(const PECOFFLinkingContext &ctx, FileNode *fileNode) {
   ErrorOr<StringRef> path = fileNode->getPath(ctx);
   if (!path)
     return false;
-  for (std::unique_ptr<InputElement> &p : ctx.getLibraryGroup()->elements())
+  for (std::unique_ptr<InputElement> &p : ctx.getInputGraph().inputElements())
     if (auto *f = dyn_cast<FileNode>(p.get()))
       if (*path == *f->getPath(ctx))
         return true;
   return false;
 }
 
 // If the first command line argument is "/lib", link.exe acts as if it's
 // "lib.exe" command. This feature is not documented and looks weird, or at
#undef DEFINE_BOOLEAN_FLAG
 
   // Add the library group to the input graph.
   if (!isReadingDirectiveSection) {
     // The container for the entry point file.
     std::unique_ptr<SimpleFileNode> entry(new SimpleFileNode("<entry>"));
     ctx.setEntryNode(entry.get());
     ctx.getInputGraph().addInputElement(std::move(entry));
 
-    // The container for all library files.
-    std::unique_ptr<Group> group(new PECOFFGroup(ctx));
-    ctx.setLibraryGroup(group.get());
-    ctx.getInputGraph().addInputElement(std::move(group));
+    // Add a group-end marker.
+    ctx.getInputGraph().addInputElement(llvm::make_unique<GroupEnd>(0));
   }
 
   // Add the library files to the library group.
   for (std::unique_ptr<FileNode> &lib : libraries) {
     if (!hasLibrary(ctx, lib.get())) {
       if (isReadingDirectiveSection)
         if (lib->parse(ctx, diag))
           return false;
-      ctx.getLibraryGroup()->addFile(std::move(lib));
+      ctx.addLibraryFile(std::move(lib));
     }
   }
 
   // Validate the combination of options used.
   return ctx.validate(diag);
 }
 
 } // namespace lld

lib/ReaderWriter/MachO/MachOLinkingContext.cpp

 #include "lld/Passes/LayoutPass.h"
 #include "lld/Passes/RoundTripYAMLPass.h"
 #include "lld/ReaderWriter/Reader.h"
 #include "lld/ReaderWriter/Writer.h"
 #include "llvm/ADT/StringExtras.h"
 #include "llvm/ADT/Triple.h"
 #include "llvm/Config/config.h"
 #include "llvm/Support/Errc.h"
+#include "llvm/Support/Debug.h"
 #include "llvm/Support/Host.h"
 #include "llvm/Support/MachO.h"
 #include "llvm/Support/Path.h"
 #include <algorithm>
 
 #if defined(HAVE_CXXABI_H)
 #include <cxxabi.h>
 #endif
bool MachOLinkingContext::customAtomOrderer(const DefinedAtom *left,
   if (foundLeft != foundRight)
     leftBeforeRight = foundLeft;
   else
     leftBeforeRight = (leftOrder < rightOrder);
 
   return true;
 }
 
+static File *getFirstFile(const std::unique_ptr<InputElement> &elem) {
+  FileNode *e = dyn_cast<FileNode>(const_cast<InputElement *>(elem.get()));
+  if (!e || e->files().empty())
+    return nullptr;
+  return e->files()[0].get();
+}
+
+static bool isLibrary(const std::unique_ptr<InputElement> &elem) {
+  File *f = getFirstFile(elem);
+  return f && (isa<SharedLibraryFile>(f) || isa<ArchiveLibraryFile>(f));
+}
+
+// The darwin linker processes input files in two phases.  The first phase
+// links in all object (.o) files in command line order. The second phase
+// links in libraries in command line order.
+// In this function we reorder the input files so that all the object files
+// comes before any library file. We also make a group for the library files
+// so that the Resolver will reiterate over the libraries as long as we find
+// new undefines from libraries.
+void MachOLinkingContext::maybeSortInputFiles() {
+  std::vector<std::unique_ptr<InputElement>> &elements
+      = getInputGraph().inputElements();
+  std::stable_sort(elements.begin(), elements.end(),
+                   [](const std::unique_ptr<InputElement> &a,
+                      const std::unique_ptr<InputElement> &b) {
+                     return !isLibrary(a) && isLibrary(b);
+                   });
+  size_t numLibs = std::count_if(elements.begin(), elements.end(), isLibrary);
+  elements.push_back(llvm::make_unique<GroupEnd>(numLibs));
+}
+
 } // end namespace lld

lib/ReaderWriter/PECOFF/PECOFFLinkingContext.cpp

std::unique_ptr<File> PECOFFLinkingContext::createEntrySymbolFile() const {
   return LinkingContext::createEntrySymbolFile("<command line option /entry>");
 }
 
 std::unique_ptr<File> PECOFFLinkingContext::createUndefinedSymbolFile() const {
   return LinkingContext::createUndefinedSymbolFile(
       "<command line option /include>");
 }
 
+void PECOFFLinkingContext::addLibraryFile(std::unique_ptr<FileNode> file) {
+  GroupEnd *currentGroupEnd;
+  int pos = -1;
+  std::vector<std::unique_ptr<InputElement>> &elements
+      = getInputGraph().inputElements();
+  for (int i = 0, e = elements.size(); i < e; ++i) {
+    if ((currentGroupEnd = dyn_cast<GroupEnd>(elements[i].get()))) {
+      pos = i;
+      break;
+    }
+  }
+  assert(pos >= 0);
+  elements.insert(elements.begin() + pos, std::move(file));
+  elements[pos + 1] = llvm::make_unique<GroupEnd>(
+      currentGroupEnd->getSize() + 1);
+}
+
 bool PECOFFLinkingContext::createImplicitFiles(
     std::vector<std::unique_ptr<File>> &) {
   // Create a file for __ImageBase.
   auto fileNode = llvm::make_unique<SimpleFileNode>("Implicit Files");
   fileNode->appendInputFile(
       llvm::make_unique<pecoff::LinkerGeneratedSymbolFile>(*this));
   getInputGraph().addInputElement(std::move(fileNode));
 
   // Create a file for _imp_ symbols.
   auto impFileNode = llvm::make_unique<SimpleFileNode>("imp");
   impFileNode->appendInputFile(
       llvm::make_unique<pecoff::LocallyImportedSymbolFile>(*this));
   getInputGraph().addInputElement(std::move(impFileNode));
 
   std::shared_ptr<pecoff::ResolvableSymbols> syms(
       new pecoff::ResolvableSymbols());
   getInputGraph().registerObserver([=](File *file) { syms->add(file); });
 
   // Create a file for dllexported symbols.
   auto exportNode = llvm::make_unique<SimpleFileNode>("<export>");
   exportNode->appendInputFile(
       llvm::make_unique<pecoff::ExportedSymbolRenameFile>(*this, syms));
-  getLibraryGroup()->addFile(std::move(exportNode));
+  addLibraryFile(std::move(exportNode));
 
   // Create a file for the entry point function.
   getEntryNode()->appendInputFile(
       llvm::make_unique<pecoff::EntryPointFile>(*this, syms));
   return true;
 }
 
 /// Returns the section name in the resulting executable.

unittests/DriverTests/DriverTest.h

protected:
   std::string inputFile(int index) {
     const InputElement &inputElement =
         *linkingContext()->getInputGraph().inputElements()[index];
     if (inputElement.kind() == InputElement::Kind::File)
       return *cast<FileNode>(&inputElement)->getPath(*linkingContext());
     llvm_unreachable("not handling other types of input files");
   }
 
-  // Convenience method for getting i'th input files name.
-  std::string inputFile(int index1, int index2) {
-    Group *group = dyn_cast<Group>(
-        linkingContext()->getInputGraph().inputElements()[index1].get());
-    if (!group)
-      llvm_unreachable("not handling other types of input files");
-    FileNode *file = dyn_cast<FileNode>(group->elements()[index2].get());
-    if (!file)
-      llvm_unreachable("not handling other types of input files");
-    return *file->getPath(*linkingContext());
-  }
-
   // For unit tests to call driver with various command lines.
   bool parse(const char *args, ...) {
     // Construct command line options from varargs.
     std::vector<const char *> vec;
     vec.push_back(args);
     va_list ap;
     va_start(ap, args);
     while (const char *arg = va_arg(ap, const char *))

unittests/DriverTests/InputGraphTest.cpp

 
 protected:
   TestLinkingContext _ctx;
   InputGraph *_graph;
 };
 
 } // end anonymous namespace
 
-static std::unique_ptr<TestFileNode> createFile1(StringRef name) {
+static std::unique_ptr<TestFileNode> createFile(StringRef name) {
   std::vector<std::unique_ptr<File>> files;
   files.push_back(std::unique_ptr<SimpleFile>(new SimpleFile(name)));
   std::unique_ptr<TestFileNode> file(new TestFileNode("filenode"));
   file->addFiles(std::move(files));
   return file;
 }
 
-static std::unique_ptr<TestFileNode> createFile2(StringRef name1,
-                                                 StringRef name2) {
-  std::vector<std::unique_ptr<File>> files;
-  files.push_back(std::unique_ptr<SimpleFile>(new SimpleFile(name1)));
-  files.push_back(std::unique_ptr<SimpleFile>(new SimpleFile(name2)));
-  std::unique_ptr<TestFileNode> file(new TestFileNode("filenode"));
-  file->addFiles(std::move(files));
-  return file;
-}
-
 TEST_F(InputGraphTest, Empty) {
   expectEnd();
 }
 
 TEST_F(InputGraphTest, File) {
-  _graph->addInputElement(createFile1("file1"));
-  EXPECT_EQ("file1", getNext());
-  expectEnd();
-}
-
-TEST_F(InputGraphTest, Files) {
-  _graph->addInputElement(createFile2("file1", "file2"));
-  EXPECT_EQ("file1", getNext());
-  EXPECT_EQ("file2", getNext());
-  expectEnd();
-}
-
-TEST_F(InputGraphTest, Group) {
-  _graph->addInputElement(createFile2("file1", "file2"));
-
-  std::unique_ptr<Group> group(new Group());
-  group->addFile(createFile2("file3", "file4"));
-  group->addFile(createFile1("file5"));
-  group->addFile(createFile1("file6"));
-  _graph->addInputElement(std::move(group));
-
+  _graph->addInputElement(createFile("file1"));
   EXPECT_EQ("file1", getNext());
-  EXPECT_EQ("file2", getNext());
-  EXPECT_EQ("file3", getNext());
-  EXPECT_EQ("file4", getNext());
-  EXPECT_EQ("file5", getNext());
-  EXPECT_EQ("file6", getNext());
-  expectEnd();
-}
-
-// Iterate through the group
-TEST_F(InputGraphTest, GroupIteration) {
-  _graph->addInputElement(createFile2("file1", "file2"));
-
-  std::unique_ptr<Group> group(new Group());
-  group->addFile(createFile2("file3", "file4"));
-  group->addFile(createFile1("file5"));
-  group->addFile(createFile1("file6"));
-  _graph->addInputElement(std::move(group));
-
-  EXPECT_EQ("file1", getNext());
-  EXPECT_EQ("file2", getNext());
-
-  EXPECT_EQ("file3", getNext());
-  EXPECT_EQ("file4", getNext());
-  EXPECT_EQ("file5", getNext());
-  EXPECT_EQ("file6", getNext());
-  _graph->notifyProgress();
-
-  EXPECT_EQ("file3", getNext());
-  EXPECT_EQ("file4", getNext());
-  _graph->notifyProgress();
-  EXPECT_EQ("file5", getNext());
-  EXPECT_EQ("file6", getNext());
-
-  EXPECT_EQ("file3", getNext());
-  EXPECT_EQ("file4", getNext());
-  EXPECT_EQ("file5", getNext());
-  EXPECT_EQ("file6", getNext());
   expectEnd();
 }
 
 // Node expansion tests
 TEST_F(InputGraphTest, Normalize) {
-  _graph->addInputElement(createFile2("file1", "file2"));
+  _graph->addInputElement(createFile("file1"));
 
   std::unique_ptr<TestExpandFileNode> expandFile(
       new TestExpandFileNode("node"));
-  expandFile->addElement(createFile1("file3"));
-  expandFile->addElement(createFile1("file4"));
+  expandFile->addElement(createFile("file2"));
+  expandFile->addElement(createFile("file3"));
   _graph->addInputElement(std::move(expandFile));
-
-  std::unique_ptr<Group> group(new Group());
-  std::unique_ptr<TestExpandFileNode> expandFile2(
-      new TestExpandFileNode("node"));
-  expandFile2->addElement(createFile1("file5"));
-  group->addFile(std::move(expandFile2));
-  _graph->addInputElement(std::move(group));
-
-  _graph->addInputElement(createFile1("file6"));
   _graph->normalize();
 
   EXPECT_EQ("file1", getNext());
   EXPECT_EQ("file2", getNext());
   EXPECT_EQ("file3", getNext());
-  EXPECT_EQ("file4", getNext());
-  EXPECT_EQ("file5", getNext());
-  EXPECT_EQ("file6", getNext());
   expectEnd();
 }
 
 TEST_F(InputGraphTest, Observer) {
   std::vector<std::string> files;
   _graph->registerObserver([&](File *file) { files.push_back(file->path()); });
 
-  _graph->addInputElement(createFile1("file1"));
-  _graph->addInputElement(createFile1("file2"));
+  _graph->addInputElement(createFile("file1"));
+  _graph->addInputElement(createFile("file2"));
   EXPECT_EQ("file1", getNext());
   EXPECT_EQ("file2", getNext());
   expectEnd();
 
   EXPECT_EQ(2U, files.size());
   EXPECT_EQ("file1", files[0]);
   EXPECT_EQ("file2", files[1]);
 }

unittests/DriverTests/WinLinkDriverTest.cpp

 
 //
 // Tests for input file order
 //
 
 TEST_F(WinLinkParserTest, InputOrder) {
   EXPECT_TRUE(parse("link.exe", "a.lib", "b.obj", "c.obj", "a.lib", "d.obj",
                     nullptr));
-  EXPECT_EQ(5, inputFileCount());
+  EXPECT_EQ(6, inputFileCount());
   EXPECT_EQ("b.obj", inputFile(0));
   EXPECT_EQ("c.obj", inputFile(1));
   EXPECT_EQ("d.obj", inputFile(2));
-  EXPECT_EQ("a.lib", inputFile(4, 0));
+  EXPECT_EQ("a.lib", inputFile(4));
 }
 
 //
 // Tests for command line options that take values.
 //
 
 TEST_F(WinLinkParserTest, AlternateName) {
   EXPECT_TRUE(parse("link.exe", "/alternatename:sym1=sym2", "a.out", nullptr));

 
 //
 // Tests for /defaultlib and /nodefaultlib.
 //
 
 TEST_F(WinLinkParserTest, DefaultLib) {
   EXPECT_TRUE(parse("link.exe", "/defaultlib:user32.lib",
                     "/defaultlib:kernel32", "a.obj", nullptr));
-  EXPECT_EQ(3, inputFileCount());
+  EXPECT_EQ(5, inputFileCount());
   EXPECT_EQ("a.obj", inputFile(0));
-  EXPECT_EQ("user32.lib", inputFile(2, 0));
-  EXPECT_EQ("kernel32.lib", inputFile(2, 1));
+  EXPECT_EQ("user32.lib", inputFile(2));
+  EXPECT_EQ("kernel32.lib", inputFile(3));
 }
 
 TEST_F(WinLinkParserTest, DefaultLibDuplicates) {
   EXPECT_TRUE(parse("link.exe", "/defaultlib:user32.lib",
                     "/defaultlib:user32.lib", "a.obj", nullptr));
-  EXPECT_EQ(3, inputFileCount());
+  EXPECT_EQ(4, inputFileCount());
   EXPECT_EQ("a.obj", inputFile(0));
-  EXPECT_EQ("user32.lib", inputFile(2, 0));
+  EXPECT_EQ("user32.lib", inputFile(2));
 }
 
 TEST_F(WinLinkParserTest, NoDefaultLib) {
   EXPECT_TRUE(parse("link.exe", "/defaultlib:user32.lib",
                     "/defaultlib:kernel32", "/nodefaultlib:user32.lib", "a.obj",
                     nullptr));
-  EXPECT_EQ(3, inputFileCount());
+  EXPECT_EQ(4, inputFileCount());
   EXPECT_EQ("a.obj", inputFile(0));
-  EXPECT_EQ("kernel32.lib", inputFile(2, 0));
+  EXPECT_EQ("kernel32.lib", inputFile(2));
 }
 
 TEST_F(WinLinkParserTest, NoDefaultLibCase) {
   EXPECT_TRUE(parse("link.exe", "/defaultlib:user32",
                     "/defaultlib:kernel32", "/nodefaultlib:USER32.LIB", "a.obj",
                     nullptr));
-  EXPECT_EQ(3, inputFileCount());
+  EXPECT_EQ(4, inputFileCount());
   EXPECT_EQ("a.obj", inputFile(0));
-  EXPECT_EQ("kernel32.lib", inputFile(2, 0));
+  EXPECT_EQ("kernel32.lib", inputFile(2));
 }
 
 TEST_F(WinLinkParserTest, NoDefaultLibAll) {
   EXPECT_TRUE(parse("link.exe", "/defaultlib:user32.lib",
                     "/defaultlib:kernel32", "/nodefaultlib", "a.obj", nullptr));
   EXPECT_EQ(3, inputFileCount());
   EXPECT_EQ("a.obj", inputFile(0));
 }
 
 TEST_F(WinLinkParserTest, DisallowLib) {
   EXPECT_TRUE(parse("link.exe", "/defaultlib:user32.lib",
                     "/defaultlib:kernel32", "/disallowlib:user32.lib", "a.obj",
                     nullptr));
-  EXPECT_EQ(3, inputFileCount());
+  EXPECT_EQ(4, inputFileCount());
   EXPECT_EQ("a.obj", inputFile(0));
-  EXPECT_EQ("kernel32.lib", inputFile(2, 0));
+  EXPECT_EQ("kernel32.lib", inputFile(2));
 }
 
 //
 // Tests for DLL.
 //
 
 TEST_F(WinLinkParserTest, NoEntry) {
   EXPECT_TRUE(parse("link.exe", "/noentry", "/dll", "a.obj", nullptr));