Add observers to Input Graph

[ruiu]

Summary

Make it possible to add observers to an Input Graph, so that files
returned from an Input Graph can be examined before they are
passed to Resolver.

To implement some PE/COFF features we need to know all the symbols
that *can* be solved, including ones in archive files that are not
yet to be read.

Currently, Resolver only maintains a set of symbols that are
already read. It has no knowledge on symbols in skipped files in
an archive file.

There are many ways to implement that. I chose to apply the
observer pattern here because it seems most non-intrusive. We don't
want to mess up Resolver with architecture specific features.
Even in PE/COFF, the feature that needs this mechanism is minor.
So I chose not to modify Resolver, but add a hook to Input Graph.

[Bigcheese]

lgtm.

[atanasyan]

LGTM

include/lld/Core/InputGraph.h

74 ↗

(On Diff #9331)

Maybe it is better to use the llvm::function_ref class to be consistent with main LLVM code.

http://llvm.org/docs/ProgrammersManual.html#passing-functions-and-other-callable-objects

[Bigcheese]

include/lld/Core/InputGraph.h

74 ↗

(On Diff #9331)

This is news to me. I would much prefer we use std::function.

So after doing some research, it seems that advanced uses of std::function can fail on VC11 (VS 2012). We're not doing that here, and the buildbots have the final say in what is supported.

[shankarke]

Can you also add a test ? Possibly two tests ? One with InputGraphTest and one with YAML ?

include/lld/Core/InputGraph.h

74 ↗

(On Diff #9331)

You might want to change the observer function to return an ErrorOr,

lib/ReaderWriter/FileArchive.cpp

100–108 ↗

(On Diff #9331)

This may be put in one line using std::transform.

std::transform(_symbolMemberMap.begin(),_symbolMemberMap.end(), std::back_inserter(ret), [](const auto &pair){return pair.first;});

[dexonsmith]

+richard, who added the current guidance in r208067.

[ruiu]

• Added a test

[ruiu]

include/lld/Core/InputGraph.h

74 ↗

(On Diff #9331)

I'd prefer std::function too.

74 ↗

(On Diff #9331)

Return type of void is intentional. Observers should never fail, and should not do anything other than observing.

lib/ReaderWriter/FileArchive.cpp

100–108 ↗

(On Diff #9331)

It looks more cryptic than the plain for loop. I think it's better to keep the for loop. It might make sense to write it in four lines like this.

std::set<StringRef> ret;
for (const auto &e : _symbolMemberMap)
  ret.insert(e.first)
return ret;

[ruiu]

• Replaced std::function with function_ref

[atanasyan]

LGTM

[ruiu]

Closed by commit rL208753 (authored by @ruiu).

lld/trunk/include/lld/Core/ArchiveLibraryFile.h

 //===- Core/ArchiveLibraryFile.h - Models static library ------------------===//
 //
 //                             The LLVM Linker
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLD_CORE_ARCHIVE_LIBRARY_FILE_H
 #define LLD_CORE_ARCHIVE_LIBRARY_FILE_H
 
 #include "lld/Core/File.h"
 
+#include <set>
+
 namespace lld {
 
 ///
 /// The ArchiveLibraryFile subclass of File is used to represent unix
 /// static library archives.  These libraries provide no atoms to the
 /// initial set of atoms linked.  Instead, when the Resolver will query
 /// ArchiveLibraryFile instances for specific symbols names using the
 /// find() method.  If the archive contains an object file which has a
 /// DefinedAtom whose scope is not translationUnit, then that entire
 /// object file File is returned.
 ///
 class ArchiveLibraryFile : public File {
 public:
   static inline bool classof(const File *f) {
     return f->kind() == kindArchiveLibrary;
   }
 
   /// Check if any member of the archive contains an Atom with the
   /// specified name and return the File object for that member, or nullptr.
   virtual const File *find(StringRef name, bool dataSymbolOnly) const = 0;
 
   virtual error_code
   parseAllMembers(std::vector<std::unique_ptr<File>> &result) const = 0;
 
+  /// Returns a set of all defined symbols in the archive, i.e. all
+  /// resolvable symbol using this file.
+  virtual std::set<StringRef> getDefinedSymbols() const {
+    return std::set<StringRef>();
+  }
+
 protected:
   /// only subclasses of ArchiveLibraryFile can be instantiated
   ArchiveLibraryFile(StringRef path) : File(path, kindArchiveLibrary) {}
 };
 
 } // namespace lld
 
 #endif // LLD_CORE_ARCHIVE_LIBRARY_FILE_H

lld/trunk/include/lld/Core/InputGraph.h

 //===----------------------------------------------------------------------===//
 
 #ifndef LLD_CORE_INPUT_GRAPH_H
 #define LLD_CORE_INPUT_GRAPH_H
 
 #include "lld/Core/File.h"
 #include "llvm/Option/ArgList.h"
 
+#include "llvm/ADT/STLExtras.h"
 #include "llvm/Support/ErrorOr.h"
 #include "llvm/Support/MemoryBuffer.h"
 #include "llvm/Support/raw_ostream.h"
 
 #include <memory>
 #include <stack>
 #include <vector>
 
public:
   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.
   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(llvm::function_ref<void(File *)> fn);
+
   /// \brief Adds a node into the InputGraph
   void addInputElement(std::unique_ptr<InputElement>);
 
   /// Normalize the InputGraph. It calls expand() on each node and then replace
   /// it with getReplacements() results.
   void normalize();
 
   range<InputElementIterT> inputElements() {
public:
   void insertElementAt(std::unique_ptr<InputElement>, Position position);
 
 protected:
   // Input arguments
   InputElementVectorT _inputArgs;
   // Index of the next element to be processed
   uint32_t _nextElementIndex;
   InputElement *_currentInputElement;
+  std::vector<llvm::function_ref<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 {

lld/trunk/lib/Core/InputGraph.cpp

 using namespace lld;
 
 ErrorOr<File &> InputGraph::getNextFile() {
   // Try to get the next file of _currentInputElement. If the current input
   // element points to an archive file, and there's a file left in the archive,
   // it will succeed. If not, try to get the next file in the input graph.
   for (;;) {
     if (_currentInputElement) {
-      ErrorOr<File &> nextFile = _currentInputElement->getNextFile();
-      if (nextFile.getError() != InputGraphError::no_more_files)
-        return std::move(nextFile);
+      ErrorOr<File &> next = _currentInputElement->getNextFile();
+      if (next.getError() != InputGraphError::no_more_files) {
+        for (llvm::function_ref<void(File *)> observer : _observers)
+          observer(&next.get());
+        return std::move(next);
+      }
     }
 
     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(llvm::function_ref<void(File *)> fn) {
+  _observers.push_back(fn);
+}
+
 void InputGraph::addInputElement(std::unique_ptr<InputElement> ie) {
   _inputArgs.push_back(std::move(ie));
 }
 
 bool InputGraph::dump(raw_ostream &diagnostics) {
   for (std::unique_ptr<InputElement> &ie : _inputArgs)
     if (!ie->dump(diagnostics))
       return false;

lld/trunk/lib/ReaderWriter/FileArchive.cpp

public:
   const atom_collection<SharedLibraryAtom> &sharedLibrary() const override {
     return _sharedLibraryAtoms;
   }
 
   const atom_collection<AbsoluteAtom> &absolute() const override {
     return _absoluteAtoms;
   }
 
+  /// Returns a set of all defined symbols in the archive.
+  std::set<StringRef> getDefinedSymbols() const override {
+    std::set<StringRef> ret;
+    for (const auto &e : _symbolMemberMap)
+      ret.insert(e.first);
+    return ret;
+  }
+
 protected:
   error_code
   instantiateMember(Archive::child_iterator member,
                     std::vector<std::unique_ptr<File>> &result) const {
     std::unique_ptr<MemoryBuffer> mb;
     if (error_code ec = member->getMemoryBuffer(mb, true))
       return ec;
     if (_logLoading)

lld/trunk/unittests/DriverTests/InputGraphTest.cpp

TEST_F(InputGraphTest, 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"));
+  EXPECT_EQ("file1", getNext());
+  EXPECT_EQ("file2", getNext());
+  expectEnd();
+
+  EXPECT_EQ(2U, files.size());
+  EXPECT_EQ("file1", files[0]);
+  EXPECT_EQ("file2", files[1]);
+}