Rewrite dependency finding algorithms in a few classes

They no longer depend on iterators to the dependencies list staying valid
when elements are added, allowing conversion to std::vector.

diff --git a/source/binary.cpp b/source/binary.cpp
index c8011d7c2a24c0cec015d751fca615fc8df23de4..7b5bac8e1b0dae70d977cc68326b94aba438bdcd 100644 (file)
--- a/source/binary.cpp
+++ b/source/binary.cpp
@@ -1,4 +1,4 @@
-#include <algorithm>
+#include <msp/core/algorithm.h>
 #include <msp/fs/utils.h>
 #include <msp/strings/format.h>
 #include <msp/strings/utils.h>
@@ -46,52 +46,55 @@ void Binary::find_dependencies()
        if(!component)
                return;
 
-       list<Target *> queue;
-       list<Target *> dep_libs;
-       set<string> missing_libs;
-       queue.push_back(this);
-       for(auto j=queue.begin(); j!=queue.end(); ++j)
+       vector<Target *> static_libs;
+       vector<Target *> shared_libs;
+       vector<string> missing_libs;
+       find_dependencies(this, static_libs, shared_libs, missing_libs);
+
+       for(Target *t: static_libs)
+               add_dependency(*t);
+       for(Target *t: shared_libs)
+               add_dependency(*t);
+       for(const string &m: missing_libs)
+               problems.push_back(format("Required library %s not found", m));
+}
+
+void Binary::find_dependencies(Target *tgt, vector<Target *> &static_libs, vector<Target *> &shared_libs, vector<string> &missing_libs)
+{
+       BuildInfo binfo;
+       tgt->collect_build_info(binfo);
+       if(tgt!=this)
        {
-               Target *tgt = *j;
+               static_binfo.libpath.insert(static_binfo.libpath.end(), binfo.libpath.begin(), binfo.libpath.end());
+               static_binfo.keep_symbols.insert(static_binfo.keep_symbols.end(), binfo.keep_symbols.begin(), binfo.keep_symbols.end());
+               if(binfo.threads)
+                       static_binfo.threads = true;
+       }
 
-               BuildInfo binfo;
-               tgt->collect_build_info(binfo);
-               if(tgt!=this)
-               {
-                       static_binfo.libpath.insert(static_binfo.libpath.end(), binfo.libpath.begin(), binfo.libpath.end());
-                       static_binfo.keep_symbols.insert(static_binfo.keep_symbols.end(), binfo.keep_symbols.begin(), binfo.keep_symbols.end());
-                       if(binfo.threads)
-                               static_binfo.threads = true;
-               }
+       for(const string &l: binfo.libs)
+       {
+               if(l.size()>10 && !l.compare(l.size()-10, 10, ".framework"))
+                       continue;
 
-               auto insert_pos = j;
-               ++insert_pos;
-               for(const string &l: binfo.libs)
+               BuildInfo::LibraryMode libmode = component->get_build_info().get_libmode_for(l);
+               Target *lib = builder.get_vfs().find_library(l, binfo.libpath, libmode);
+               if(lib)
                {
-                       if(l.size()>10 && !l.compare(l.size()-10, 10, ".framework"))
-                               continue;
-
-                       BuildInfo::LibraryMode libmode = component->get_build_info().get_libmode_for(l);
-                       Target *lib = builder.get_vfs().find_library(l, binfo.libpath, libmode);
-                       if(lib)
+                       Target *real = lib->get_real_target();
+                       if(StaticLibrary *stlib = dynamic_cast<StaticLibrary *>(real))
                        {
-                               Target *real = lib->get_real_target();
-                               if(StaticLibrary *stlib = dynamic_cast<StaticLibrary *>(real))
-                                       queue.insert(insert_pos, stlib);
-                               else
-                                       dep_libs.push_back(lib);
+                               /* Keep only the last occurrence of each static library.  This
+                               ensures the order is correct for linking. */
+                               auto i = find(static_libs, stlib);
+                               if(i!=static_libs.end())
+                                       static_libs.erase(i);
+                               static_libs.push_back(stlib);
+                               find_dependencies(stlib, static_libs, shared_libs, missing_libs);
                        }
-                       else if(missing_libs.insert(l).second)
-                               problems.push_back(format("Required library %s not found", l));
+                       else if(!any_equals(shared_libs, lib))
+                               shared_libs.push_back(lib);
                }
+               else if(!any_equals(missing_libs, l))
+                       missing_libs.push_back(l);
        }
-
-       queue.pop_front();
-       dep_libs.splice(dep_libs.begin(), queue);
-
-       /* Add only the last occurrence of each library to the actual dependencies.
-       This ensures that static library ordering is correct. */
-       for(auto i=dep_libs.begin(); i!=dep_libs.end(); ++i)
-               if(!any_of(next(i), dep_libs.end(), [i](Target *d){ return d==*i; }))
-                       add_dependency(**i);
 }

diff --git a/source/binary.h b/source/binary.h
index a8d10f0384008a9599a8a001b5a6c87294e63ca2..a9e8de1c8e89bb883ee24f1e6032c42836833c8a 100644 (file)
--- a/source/binary.h
+++ b/source/binary.h
@@ -27,6 +27,8 @@ public:
 
 protected:
        void find_dependencies() override;
+private:
+       void find_dependencies(Target *, std::vector<Target *> &, std::vector<Target *> &, std::vector<std::string> &);
 };
 
 #endif

diff --git a/source/component.cpp b/source/component.cpp
index 98b6ff76590e1067709895ed1277d6535ed61e58..6545b28b95c460ed9b1f34b8ca679cd8aa77e677 100644 (file)
--- a/source/component.cpp
+++ b/source/component.cpp
@@ -1,3 +1,4 @@
+#include <deque>
 #include <msp/core/algorithm.h>
 #include <msp/fs/dir.h>
 #include <msp/fs/stat.h>
@@ -30,18 +31,23 @@ void Component::create_build_info()
        const Package::Requirements &pkg_reqs = package.get_required_packages();
        Package::Requirements direct_reqs = requires;
        direct_reqs.insert(direct_reqs.end(), pkg_reqs.begin(), pkg_reqs.end());
+       for(Package *r: direct_reqs)
+               final_build_info.update_from(r->get_exported_build_info(), BuildInfo::DEPENDENCY);
 
        Package::Requirements all_reqs = direct_reqs;
-       for(Package *r: all_reqs)
+       deque<Package *> queue(direct_reqs.begin(), direct_reqs.end());
+       while(!queue.empty())
        {
-               BuildInfo::UpdateLevel level = BuildInfo::CHAINED;
-               if(any_equals(direct_reqs, r))
-                       level = BuildInfo::DEPENDENCY;
-               final_build_info.update_from(r->get_exported_build_info(), level);
-
-               for(Package *q: r->get_required_packages())
-                       if(!any_equals(all_reqs, q))
-                               all_reqs.push_back(q);
+               Package *req = queue.front();
+               queue.pop_front();
+
+               for(Package *r: req->get_required_packages())
+                       if(!any_equals(all_reqs, r))
+                       {
+                               final_build_info.update_from(r->get_exported_build_info(), BuildInfo::CHAINED);
+                               all_reqs.push_back(r);
+                               queue.push_back(r);
+                       }
        }
 
        final_build_info.update_from(package.get_build_info());

diff --git a/source/objectfile.cpp b/source/objectfile.cpp
index 256807c1d7930d7db3e1c6e6360d5d6ceb1f26f7..a2f80729878630a2e081caca19a818b8e88e8d4b 100644 (file)
--- a/source/objectfile.cpp
+++ b/source/objectfile.cpp
@@ -52,61 +52,60 @@ void ObjectFile::collect_build_info(BuildInfo &binfo) const
 
 void ObjectFile::find_dependencies()
 {
-       for(Target *d: depends)
+       vector<FileTarget *> headers;
+       find_dependencies(source, headers);
+       for(FileTarget *h: headers)
        {
-               d->prepare();
-               find_dependencies(dynamic_cast<FileTarget *>(d));
+               add_dependency(*h);
+               if(h->get_real_target()->is_buildable())
+                       h->signal_modified.connect(sigc::mem_fun(this, static_cast<void (ObjectFile::*)()>(&ObjectFile::find_dependencies)));
        }
 }
 
-void ObjectFile::find_dependencies(FileTarget *tgt)
+void ObjectFile::find_dependencies(FileTarget &tgt, vector<FileTarget *> &headers)
 {
-       FileTarget *rtgt = dynamic_cast<FileTarget *>(tgt->get_real_target());
-       const Dependencies &tdeps = rtgt->get_transitive_dependencies();
-       Dependencies deps_to_add;
-       if(rtgt==tgt)
-       {
-               /* We are using the target from its original location, so dependencies
-               apply directly */
-               deps_to_add = tdeps;
-       }
-       else
+       tgt.prepare();
+
+       FileTarget *rtgt = dynamic_cast<FileTarget *>(tgt.get_real_target());
+       Dependencies deps_to_add = rtgt->get_transitive_dependencies();
+       if(rtgt!=&tgt)
        {
                FS::Path inst_dir = rtgt->get_component()->get_install_map().get_install_location(*rtgt);
                /* The target has been displaced by installing it.  Displace any
                dependencies that come from the same package as well. */
                const SourcePackage *tpkg = rtgt->get_package();
-               for(Target *d: tdeps)
+               for(Target *&d: deps_to_add)
                {
                        FileTarget *file = dynamic_cast<FileTarget *>(d);
                        if(file && file->get_package()==tpkg && FS::descendant_depth(file->get_path(), tpkg->get_source_directory())>=0)
                        {
                                const Component *tcomp = file->get_component();
                                FS::Path dep_inst = tcomp->get_install_map().get_install_location(*file);
-                               FS::Path displaced = FS::dirname(tgt->get_path())/FS::relative(dep_inst, inst_dir)/FS::basename(file->get_path());
-                               if(Target *ddep = builder.get_vfs().get_target(displaced))
-                                       deps_to_add.push_back(ddep);
-                               else
+                               FS::Path displaced = FS::dirname(tgt.get_path())/FS::relative(dep_inst, inst_dir)/FS::basename(file->get_path());
+                               d = builder.get_vfs().get_target(displaced);
+                               if(!d)
                                {
+                                       /* If the target was in an overlay directory and the displaced
+                                       dependency is not found, try removing the overlay from the path. */
                                        string last_dir = FS::basename(FS::dirname(displaced));
                                        if(any_equals(tcomp->get_overlays(), last_dir))
                                        {
                                                displaced = displaced.subpath(0, displaced.size()-2)/FS::basename(file->get_path());
-                                               if((ddep = builder.get_vfs().get_target(displaced)))
-                                                       deps_to_add.push_back(ddep);
+                                               d = builder.get_vfs().get_target(displaced);
                                        }
                                }
                        }
-                       else
-                               deps_to_add.push_back(d);
                }
        }
 
        for(Target *d: deps_to_add)
-               if(!any_equals(depends, d))
+               if(FileTarget *file = dynamic_cast<FileTarget *>(d))
                {
-                       add_dependency(*d);
-                       if(d->get_real_target()->is_buildable())
-                               d->signal_modified.connect(sigc::mem_fun(this, static_cast<void (ObjectFile::*)()>(&ObjectFile::find_dependencies)));
+                       auto i = lower_bound(headers, file);
+                       if(i==headers.end() || *i!=file)
+                       {
+                               headers.insert(i, file);
+                               find_dependencies(*file, headers);
+                       }
                }
 }

diff --git a/source/objectfile.h b/source/objectfile.h
index fc844d9a04dff28786af13607351720dd404c1c6..4f116e9f2d99e50e044b259bce2656fa3b214beb 100644 (file)
--- a/source/objectfile.h
+++ b/source/objectfile.h
@@ -31,7 +31,7 @@ public:
 private:
        void find_dependencies() override;
 
-       void find_dependencies(FileTarget *);
+       void find_dependencies(FileTarget &, std::vector<FileTarget *> &);
 };
 
 #endif