From 9f885c3eec8f065b7dc400acfb9dd67158284fcf Mon Sep 17 00:00:00 2001 From: Mikko Rasa Date: Wed, 21 Dec 2022 00:38:59 +0200 Subject: [PATCH] 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. --- source/binary.cpp | 85 ++++++++++++++++++++++--------------------- source/binary.h | 2 + source/component.cpp | 24 +++++++----- source/objectfile.cpp | 53 +++++++++++++-------------- source/objectfile.h | 2 +- 5 files changed, 88 insertions(+), 78 deletions(-) diff --git a/source/binary.cpp b/source/binary.cpp index c8011d7..7b5bac8 100644 --- a/source/binary.cpp +++ b/source/binary.cpp @@ -1,4 +1,4 @@ -#include +#include #include #include #include @@ -46,52 +46,55 @@ void Binary::find_dependencies() if(!component) return; - list queue; - list dep_libs; - set missing_libs; - queue.push_back(this); - for(auto j=queue.begin(); j!=queue.end(); ++j) + vector static_libs; + vector shared_libs; + vector 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 &static_libs, vector &shared_libs, vector &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(real)) { - Target *real = lib->get_real_target(); - if(StaticLibrary *stlib = dynamic_cast(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 a8d10f0..a9e8de1 100644 --- 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 &, std::vector &, std::vector &); }; #endif diff --git a/source/component.cpp b/source/component.cpp index 98b6ff7..6545b28 100644 --- a/source/component.cpp +++ b/source/component.cpp @@ -1,3 +1,4 @@ +#include #include #include #include @@ -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 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 256807c..a2f8072 100644 --- 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 headers; + find_dependencies(source, headers); + for(FileTarget *h: headers) { - d->prepare(); - find_dependencies(dynamic_cast(d)); + add_dependency(*h); + if(h->get_real_target()->is_buildable()) + h->signal_modified.connect(sigc::mem_fun(this, static_cast(&ObjectFile::find_dependencies))); } } -void ObjectFile::find_dependencies(FileTarget *tgt) +void ObjectFile::find_dependencies(FileTarget &tgt, vector &headers) { - FileTarget *rtgt = dynamic_cast(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(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(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(d)) { - add_dependency(*d); - if(d->get_real_target()->is_buildable()) - d->signal_modified.connect(sigc::mem_fun(this, static_cast(&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 fc844d9..4f116e9 100644 --- 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 &); }; #endif -- 2.43.0