Fix managing weak symbols.

Weak symbols where not being managed correctly. The symbols table
is now a class with externals and weaks as separate symtabs so
the externals can be searched first then the weaks and if not
found an unresolved error is raised. This was found creating
a libbsdport RAP file where the drivers in the all driver table
resolved to the weak symbols and so linking in nothing.

Fixing the weak symbols as found in the libbsdport library
triggered a new resolver bug. The object files now contain the
resolver state and this is used to determine if an object file
has been resolved or is currently being resolved avoiding
rescursive loops with dependent object files.

The resolver trace output is a little easier to read.

9 files changed, 372 insertions, 70 deletions

diff --git a/rld-elf.cpp b/rld-elf.cpp
index 5cfcc8f..c8e7aa1 100644
--- a/rld-elf.cpp
+++ b/rld-elf.cpp
@@ -853,14 +853,14 @@ namespace rld
           if (unresolved)
             add = true;
         }
-        else if (!unresolved)
+        else
         {
           if (((stype == STT_NOTYPE) ||
                (stype == STT_OBJECT) ||
                (stype == STT_FUNC)) &&
-              ((local && (sbind == STB_LOCAL)) ||
-                  (weak && (sbind == STB_WEAK)) ||
-               (global && (sbind == STB_GLOBAL))))
+              ((weak && (sbind == STB_WEAK)) ||
+               (!unresolved && ((local && (sbind == STB_LOCAL)) ||
+                                (global && (sbind == STB_GLOBAL))))))
             add = true;
         }
 
diff --git a/rld-files.cpp b/rld-files.cpp
index 75860ba..9887e48 100644
--- a/rld-files.cpp
+++ b/rld-files.cpp
@@ -979,7 +979,9 @@ namespace rld
     object::object (archive& archive_, file& name_)
       : image (name_),
         archive_ (&archive_),
-        valid_ (false)
+        valid_ (false),
+        resolving_ (false),
+        resolved_ (false)
     {
       if (!name ().is_valid ())
         throw rld_error_at ("name is empty");
@@ -988,7 +990,9 @@ namespace rld
     object::object (const std::string& path)
       : image (path),
         archive_ (0),
-        valid_ (false)
+        valid_ (false),
+        resolving_ (false),
+        resolved_ (false)
     {
       if (!name ().is_valid ())
         throw rld_error_at ("name is empty");
@@ -996,7 +1000,9 @@ namespace rld
 
     object::object ()
       : archive_ (0),
-        valid_ (false)
+        valid_ (false),
+        resolving_ (false),
+        resolved_ (false)
     {
     }
 
@@ -1116,7 +1122,7 @@ namespace rld
 
       rld::symbols::pointers syms;
 
-      elf ().get_symbols (syms, false, local);
+      elf ().get_symbols (syms, false, local, false, true);
 
       if (rld::verbose () >= RLD_VERBOSE_TRACE_SYMS)
         std::cout << "object:load-sym: exported: total "
@@ -1132,11 +1138,31 @@ namespace rld
           std::cout << "object:load-sym: exported: " << sym << std::endl;
 
         sym.set_object (*this);
-        symbols[sym.name ()] = &sym;
+        symbols.add_external (sym);
         externals.push_back (&sym);
       }
 
-      elf ().get_symbols (syms, true);
+      elf ().get_symbols (syms, false, false, true, false);
+
+      if (rld::verbose () >= RLD_VERBOSE_TRACE_SYMS)
+        std::cout << "object:load-sym: weak: total "
+                  << syms.size () << std::endl;
+
+      for (symbols::pointers::iterator si = syms.begin ();
+           si != syms.end ();
+           ++si)
+      {
+        symbols::symbol& sym = *(*si);
+
+        if (rld::verbose () >= RLD_VERBOSE_TRACE_SYMS)
+          std::cout << "object:load-sym: weak: " << sym << std::endl;
+
+        sym.set_object (*this);
+        symbols.add_weak (sym);
+        externals.push_back (&sym);
+      }
+
+      elf ().get_symbols (syms, true, false, true, true);
 
       if (rld::verbose () >= RLD_VERBOSE_TRACE_SYMS)
         std::cout << "object:load-sym: unresolved: total "
@@ -1215,7 +1241,7 @@ namespace rld
       return archive_;
     }
 
-    rld::symbols::table&
+    rld::symbols::symtab&
     object::unresolved_symbols ()
     {
       return unresolved;
@@ -1281,6 +1307,36 @@ namespace rld
                         "' not found: " + name ().full (), "object::get-section");
     }
 
+    void
+    object::resolve_set ()
+    {
+      resolving_ = true;
+    }
+
+    void
+    object::resolve_clear ()
+    {
+      resolving_ = false;
+    }
+
+    bool
+    object::resolving () const
+    {
+      return resolving_;
+    }
+
+    void
+    object::resolved_set ()
+    {
+      resolved_ = true;
+    }
+
+    bool
+    object::resolved () const
+    {
+      return resolved_;
+    }
+
     cache::cache ()
       : opened (false)
     {
diff --git a/rld-files.h b/rld-files.h
index f579626..4b5362e 100644
--- a/rld-files.h
+++ b/rld-files.h
@@ -56,12 +56,12 @@ namespace rld
     /**
      * Container of archive files.
      */
-    typedef std::map < std::string, archive* > archives;
+    typedef std::map < const std::string, archive* > archives;
 
     /**
      * Container of object files.
      */
-    typedef std::map < std::string, object* > objects;
+    typedef std::map < const std::string, object* > objects;
 
     /**
      * Container list of object files.
@@ -700,7 +700,7 @@ namespace rld
       /**
        * Return the unresolved symbol table for this object file.
        */
-      symbols::table& unresolved_symbols ();
+      symbols::symtab& unresolved_symbols ();
 
       /**
        * Return the list external symbols.
@@ -741,13 +741,40 @@ namespace rld
        */
       const section& get_section (int index) const;
 
+      /**
+       * Set the object file's resolving flag.
+       */
+      void resolve_set ();
+
+      /**
+       * Clear the object file's resolving flag.
+       */
+      void resolve_clear ();
+
+      /**
+       * The resolving state.
+       */
+      bool resolving () const;
+
+      /**
+       * Set the object file resolved flag.
+       */
+      void resolved_set ();
+
+      /**
+       * The resolved state.
+       */
+      bool resolved () const;
+
     private:
       archive*          archive_;   //< Points to the archive if part of an
                                     //  archive.
       bool              valid_;     //< If true begin has run and finished.
-      symbols::table    unresolved; //< This object's unresolved symbols.
+      symbols::symtab   unresolved; //< This object's unresolved symbols.
       symbols::pointers externals;  //< This object's external symbols.
       sections          secs;       //< The sections.
+      bool              resolving_; //< The object is being resolved.
+      bool              resolved_;  //< The object has been resolved.
 
       /**
        * Cannot copy via a copy constructor.
diff --git a/rld-outputter.cpp b/rld-outputter.cpp
index 7925743..8c6c37c 100644
--- a/rld-outputter.cpp
+++ b/rld-outputter.cpp
@@ -88,10 +88,10 @@ namespace rld
 
         out << "o:" << name << std::endl;
 
-        symbols::table& unresolved = obj.unresolved_symbols ();
+        symbols::symtab& unresolved = obj.unresolved_symbols ();
 
         int count = 0;
-        for (symbols::table::iterator ursi = unresolved.begin ();
+        for (symbols::symtab::iterator ursi = unresolved.begin ();
              ursi != unresolved.begin ();
              ++ursi)
         {
diff --git a/rld-resolver.cpp b/rld-resolver.cpp
index 93bc9da..31a6779 100644
--- a/rld-resolver.cpp
+++ b/rld-resolver.cpp
@@ -38,14 +38,27 @@ namespace rld
 {
   namespace resolver
   {
+    static files::object*
+    get_object (files::cache&      cache,
+                const std::string& fullname)
+    {
+      files::objects&          objects = cache.get_objects ();
+      files::objects::iterator oi = objects.find (fullname);
+      if (oi == objects.end ())
+        return 0;
+      return (*oi).second;
+    }
+
     static void
-    resolve_symbols (rld::files::object_list& dependents,
-                     rld::files::cache&       cache,
-                     rld::symbols::table&     base_symbols,
-                     rld::symbols::table&     symbols,
-                     rld::symbols::table&     unresolved,
-                     const std::string&       name)
+    resolve_symbols (files::object_list& dependents,
+                     files::cache&       cache,
+                     symbols::table&     base_symbols,
+                     symbols::table&     symbols,
+                     symbols::symtab&    unresolved,
+                     const std::string&  fullname)
     {
+      const std::string name = files::basename (fullname);
+
       static int nesting = 0;
 
       ++nesting;
@@ -59,6 +72,23 @@ namespace rld
        * 'es' is the exported symbol.
        */
 
+      files::object* object = get_object (cache, fullname);
+
+      if (object)
+      {
+        if (object->resolved () || object->resolving ())
+        {
+          if (rld::verbose () >= RLD_VERBOSE_INFO)
+            std::cout << "resolver:resolving: "
+                      << std::setw (nesting - 1) << ' '
+                      << name
+                      << " is resolved or resolving"
+                      << std::endl;
+          return;
+        }
+        object->resolve_set ();
+      }
+
       if (rld::verbose () >= RLD_VERBOSE_INFO)
         std::cout << "resolver:resolving: "
                   << std::setw (nesting - 1) << ' '
@@ -67,41 +97,58 @@ namespace rld
                   << unresolved.size ()
                   << std::endl;
 
-      rld::files::object_list objects;
+      files::object_list objects;
 
-      for (rld::symbols::table::iterator ursi = unresolved.begin ();
-           (ursi != unresolved.end ()) && !((*ursi).second)->object ();
+      for (symbols::symtab::iterator ursi = unresolved.begin ();
+           ursi != unresolved.end ();
            ++ursi)
       {
-        rld::symbols::symbol&         urs = *((*ursi).second);
-        rld::symbols::table::iterator esi = base_symbols.find (urs.name ());
-        bool                          base = true;
+        symbols::symbol& urs = *((*ursi).second);
+
+        if ((urs.binding () != STB_WEAK) && urs.object ())
+          continue;
+
+        symbols::symbol* es = base_symbols.find_external (urs.name ());
+        bool             base = true;
 
         if (rld::verbose () >= RLD_VERBOSE_INFO)
         {
           std::cout << "resolver:resolve  : "
                     << std::setw (nesting + 1) << ' '
-                    << urs.name () << std::endl;
+                    << " |- " << urs.name () << std::endl;
         }
 
-        if (esi == base_symbols.end ())
+        if (!es)
         {
-          esi = symbols.find (urs.name ());
-          if (esi == symbols.end ())
-            throw rld::error ("symbol not found: " + urs.name (), name);
+          es = symbols.find_external (urs.name ());
+          if (!es)
+          {
+            es = symbols.find_weak (urs.name ());
+            if (!es)
+              throw rld::error ("symbol not found: " + urs.name (), name);
+          }
           base = false;
         }
 
-        rld::symbols::symbol& es = *((*esi).second);
+        symbols::symbol& esym = *es;
 
         if (rld::verbose () >= RLD_VERBOSE_INFO)
         {
           std::cout << "resolver:resolved : "
                     << std::setw (nesting + 1) << ' '
-                    << urs.name ()
-                    << " -> ";
-          if (es.object())
-            std::cout << es.object()->name ().basename ();
+                    << " |   `--> ";
+          if (esym.object())
+          {
+            std::cout << esym.object()->name ().basename ();
+            if (esym.object()->resolving ())
+              std::cout << " (resolving)";
+            else if (esym.object()->resolved ())
+              std::cout << " (resolved)";
+            else if (base)
+              std::cout << " (base)";
+            else
+              std::cout << " (unresolved: " << objects.size () + 1 << ')';
+          }
           else
             std::cout << "null";
           std::cout << std::endl;
@@ -109,30 +156,47 @@ namespace rld
 
         if (!base)
         {
-          urs.set_object (*es.object ());
-          objects.push_back (es.object ());
+          files::object& eobj = *esym.object ();
+          urs.set_object (eobj);
+          if (!eobj.resolved () && !eobj.resolving ())
+          {
+            objects.push_back (&eobj);
+            objects.unique ();
+          }
         }
 
-        es.referenced ();
+        esym.referenced ();
+      }
+
+      if (object)
+      {
+        object->resolve_clear ();
+        object->resolved_set ();
       }
 
       /*
-       * Recurse into any references object files. First remove any duplicate
-       * entries.
+       * Recurse into any references object files.
        */
-      objects.unique ();
 
-      for (rld::files::object_list::iterator oli = objects.begin ();
+      if (rld::verbose () >= RLD_VERBOSE_INFO)
+        std::cout << "resolver:resolved : "
+                  << std::setw (nesting + 1) << ' '
+                  << " +-- referenced objects: " << objects.size ()
+                  << std::endl;
+
+      for (files::object_list::iterator oli = objects.begin ();
            oli != objects.end ();
            ++oli)
       {
-        rld::files::object& object = *(*oli);
+        files::object& obj = *(*oli);
         if (rld::verbose () >= RLD_VERBOSE_INFO)
-          std::cout << "resolver:resolving:    : "
-                    << object.name ().basename () << std::endl;
+          std::cout << "resolver:resolving: "
+                    << std::setw (nesting) << ' '
+                    << "] " << name << " ==> "
+                    << obj.name ().basename () << std::endl;
         resolve_symbols (dependents, cache, base_symbols, symbols,
-                         object.unresolved_symbols (),
-                         object.name ().basename ());
+                         obj.unresolved_symbols (),
+                         obj.name ().full ());
       }
 
       --nesting;
@@ -142,13 +206,13 @@ namespace rld
     }
 
     void
-    resolve (rld::files::object_list& dependents,
-             rld::files::cache&       cache,
-             rld::symbols::table&     base_symbols,
-             rld::symbols::table&     symbols,
-             rld::symbols::table&     undefined)
+    resolve (files::object_list& dependents,
+             files::cache&       cache,
+             symbols::table&     base_symbols,
+             symbols::table&     symbols,
+             symbols::symtab&    undefined)
     {
-      rld::files::object_list objects;
+      files::object_list objects;
       cache.get_objects (objects);
 
       /*
@@ -161,17 +225,17 @@ namespace rld
       /*
        * Resolve the symbols in the object files.
        */
-      for (rld::files::object_list::iterator oi = objects.begin ();
+      for (files::object_list::iterator oi = objects.begin ();
            oi != objects.end ();
            ++oi)
       {
-        rld::files::object& object = *(*oi);
+        files::object& object = *(*oi);
         if (rld::verbose () >= RLD_VERBOSE_INFO)
           std::cout << "resolver:resolving: top: "
                     << object.name ().basename () << std::endl;
         resolver::resolve_symbols (dependents, cache, base_symbols, symbols,
                                    object.unresolved_symbols (),
-                                   object.name ().basename ());
+                                   object.name ().full ());
       }
     }
   }
diff --git a/rld-resolver.h b/rld-resolver.h
index 0385bda..3771f18 100644
--- a/rld-resolver.h
+++ b/rld-resolver.h
@@ -1,10 +1,10 @@
 /*
- * Copyright (c) 2011, Chris Johns <chrisj@rtems.org> 
+ * Copyright (c) 2011, Chris Johns <chrisj@rtems.org>
  *
  * Permission to use, copy, modify, and/or distribute this software for any
  * purpose with or without fee is hereby granted, provided that the above
  * copyright notice and this permission notice appear in all copies.
- * 
+ *
  * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
  * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
  * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
@@ -43,11 +43,11 @@ namespace rld
      * @param undefined Extra undefined symbols dependent object files are
      *                  added for.
      */
-    void resolve (rld::files::object_list& dependents, 
-                  rld::files::cache&       cache,
-                  rld::symbols::table&     base_symbols,
-                  rld::symbols::table&     symbols,
-                  rld::symbols::table&     undefined);
+    void resolve (files::object_list& dependents,
+                  files::cache&       cache,
+                  symbols::table&     base_symbols,
+                  symbols::table&     symbols,
+                  symbols::symtab&    undefined);
   }
 }
 
diff --git a/rld-symbols.cpp b/rld-symbols.cpp
index 0ea7425..3464017 100644
--- a/rld-symbols.cpp
+++ b/rld-symbols.cpp
@@ -266,6 +266,62 @@ namespace rld
         out << "   (" << object ()->name ().basename () << ')';
     }
 
+    table::table ()
+    {
+    }
+
+    table::~table ()
+    {
+    }
+
+    void
+    table::add_external (symbol& sym)
+    {
+      _externals[sym.name ()] = &sym;
+    }
+
+    void
+    table::add_weak (symbol& sym)
+    {
+      _weaks[sym.name ()] = &sym;
+    }
+
+    symbol*
+    table::find_external (const std::string& name)
+    {
+      symtab::iterator sti = _externals.find (name);
+      if (sti == _externals.end ())
+        return 0;
+      return (*sti).second;
+    }
+
+    symbol*
+    table::find_weak (const std::string& name)
+    {
+      symtab::iterator sti = _weaks.find (name);
+      if (sti == _weaks.end ())
+        return 0;
+      return (*sti).second;
+    }
+
+    size_t
+    table::size () const
+    {
+      return _externals.size () + _weaks.size ();
+    }
+
+    const symtab&
+    table::externals () const
+    {
+      return _externals;
+    }
+
+    const symtab&
+    table::weaks () const
+    {
+      return _weaks;
+    }
+
     void
     load (bucket& bucket_, table& table_)
     {
@@ -273,6 +329,17 @@ namespace rld
            sbi != bucket_.end ();
            ++sbi)
       {
+        table_.add_external (*sbi);
+      }
+    }
+
+    void
+    load (bucket& bucket_, symtab& table_)
+    {
+      for (bucket::iterator sbi = bucket_.begin ();
+           sbi != bucket_.end ();
+           ++sbi)
+      {
         symbol& sym = *sbi;
         table_[sym.name ()] = &sym;
       }
@@ -297,9 +364,18 @@ namespace rld
     void
     output (std::ostream& out, const table& symbols)
     {
+      out << "Externals:" << std::endl;
+      output (out, symbols.externals ());
+      out << "Weaks:" << std::endl;
+      output (out, symbols.weaks ());
+    }
+
+    void
+    output (std::ostream& out, const symtab& symbols)
+    {
       std::cout << " No.  Scope      Type        Address    Size    Name" << std::endl;
       int index = 0;
-      for (table::const_iterator si = symbols.begin ();
+      for (symtab::const_iterator si = symbols.begin ();
            si != symbols.end ();
            ++si)
       {
diff --git a/rld-symbols.h b/rld-symbols.h
index e602e36..5405d2f 100644
--- a/rld-symbols.h
+++ b/rld-symbols.h
@@ -187,7 +187,76 @@ namespace rld
      * A symbols table is a map container of symbols. Should always point to
      * symbols held in a bucket.
      */
-    typedef std::map < std::string, symbol* > table;
+    typedef std::map < std::string, symbol* > symtab;
+
+    /**
+     * A symbols contains a symbol table of externals and weak symbols.
+     */
+    class table
+    {
+    public:
+      /**
+       * Construct a table.
+       */
+      table ();
+
+      /**
+       * Destruct a table.
+       */
+      ~table ();
+
+      /**
+       * Add an external symbol.
+       */
+      void add_external (symbol& sym);
+
+      /**
+       * Add a weak symbol.
+       */
+      void add_weak (symbol& sym);
+
+      /**
+       * Find an external symbol.
+       */
+      symbol* find_external (const std::string& name);
+
+      /**
+       * Find an weak symbol.
+       */
+      symbol* find_weak (const std::string& name);
+
+      /**
+       * Return the size of the symbols loaded.
+       */
+      size_t size () const;
+
+      /**
+       * Return the externals symbol table.
+       */
+      const symtab& externals () const;
+
+      /**
+       * Return the weaks symbol table.
+       */
+      const symtab& weaks () const;
+
+    private:
+
+      /**
+       * Cannot copy a table.
+       */
+      table (const table& orig);
+
+      /**
+       * A table of external symbols.
+       */
+      symtab _externals;
+
+      /**
+       * A table of weak symbols.
+       */
+      symtab _weaks;
+    };
 
     /**
      * Load a table from a buckey.
@@ -195,6 +264,11 @@ namespace rld
     void load (bucket& bucket_, table& table_);
 
     /**
+     * Load a table from a buckey.
+     */
+    void load (bucket& bucket_, symtab& table_);
+
+    /**
      * Given a container of symbols return how many are referenced.
      */
     size_t referenced (pointers& symbols);
@@ -203,6 +277,11 @@ namespace rld
      * Output the symbol table.
      */
     void output (std::ostream& out, const table& symbols);
+
+    /**
+     * Output the symbol table.
+     */
+    void output (std::ostream& out, const symtab& symbols);
   }
 }
 
diff --git a/rtems-ld.cpp b/rtems-ld.cpp
index d051b4b..cef40f9 100644
--- a/rtems-ld.cpp
+++ b/rtems-ld.cpp
@@ -170,7 +170,7 @@ main (int argc, char* argv[])
     rld::symbols::bucket undefines;
     rld::symbols::table  base_symbols;
     rld::symbols::table  symbols;
-    rld::symbols::table  undefined;
+    rld::symbols::symtab undefined;
     std::string          entry = "rtems";
     std::string          exit;
     std::string          output = "a.out";