aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorAvatar Ciaran McCreesh <ciaran.mccreesh@googlemail.com> 2010-06-14 14:57:32 +0100
committerAvatar Ciaran McCreesh <ciaran.mccreesh@googlemail.com> 2010-06-14 14:57:32 +0100
commitbbf7f70804bedc675f8c1725842af2055fa21eee (patch)
tree5f5e8a6864438b275599be5909cfd17e2a050013
parent0bb25e053b1ef2e7943340ff0bb684fae40ad13b (diff)
downloadpaludis-bbf7f70804bedc675f8c1725842af2055fa21eee.tar.gz
paludis-bbf7f70804bedc675f8c1725842af2055fa21eee.tar.xz
More cycle resolution cleverness
-rw-r--r--paludis/resolver/lineariser.cc108
-rw-r--r--paludis/resolver/lineariser.hh7
-rw-r--r--paludis/resolver/nag.hh4
-rw-r--r--paludis/resolver/resolver_TEST_cycles.cc64
-rwxr-xr-xpaludis/resolver/resolver_TEST_cycles_setup.sh35
5 files changed, 188 insertions, 30 deletions
diff --git a/paludis/resolver/lineariser.cc b/paludis/resolver/lineariser.cc
index c41156c..b9ae68b 100644
--- a/paludis/resolver/lineariser.cc
+++ b/paludis/resolver/lineariser.cc
@@ -41,6 +41,8 @@
using namespace paludis;
using namespace paludis::resolver;
+typedef std::tr1::unordered_map<Resolvent, std::tr1::shared_ptr<const ChangeOrRemoveDecision>, Hash<Resolvent> > ChangeOrRemoveResolvents;
+
namespace paludis
{
template <>
@@ -49,6 +51,7 @@ namespace paludis
const Environment * const env;
const std::tr1::shared_ptr<Resolved> resolved;
const std::tr1::shared_ptr<NAG> nag;
+ ChangeOrRemoveResolvents change_or_remove_resolvents;
Implementation(
const Environment * const e,
@@ -75,7 +78,6 @@ Lineariser::~Lineariser()
namespace
{
typedef std::tr1::unordered_set<Resolvent, Hash<Resolvent> > ResolventsSet;
- typedef std::tr1::unordered_map<Resolvent, std::tr1::shared_ptr<const ChangeOrRemoveDecision>, Hash<Resolvent> > ChangeOrRemoveResolvents;
struct DecisionDispatcher
{
@@ -248,7 +250,9 @@ namespace
if (classifier.build || classifier.run)
nag->add_edge(r.from_resolvent(), resolvent, make_named_values<NAGEdgeProperties>(
n::build() = classifier.build,
- n::run() = classifier.run
+ n::build_all_met() = r.already_met() || ! classifier.build,
+ n::run() = classifier.run,
+ n::run_all_met() = r.already_met() || ! classifier.run
));
else if (classifier.post)
{
@@ -278,6 +282,20 @@ namespace
{
}
};
+
+ bool no_build_dependencies(
+ const Set<Resolvent> & resolvents,
+ const NAG & nag)
+ {
+ for (Set<Resolvent>::ConstIterator r(resolvents.begin()), r_end(resolvents.end()) ;
+ r != r_end ; ++r)
+ for (NAG::EdgesFromConstIterator e(nag.begin_edges_from(*r)), e_end(nag.end_edges_from(*r)) ;
+ e != e_end ; ++e)
+ if (e->second.build())
+ return false;
+
+ return true;
+ }
}
void
@@ -286,7 +304,6 @@ Lineariser::resolve()
_imp->env->trigger_notifier_callback(NotifierCallbackResolverStageEvent("Nodifying Decisions"));
ResolventsSet ignore_dependencies_from_resolvents, ignore_edges_from_resolvents;
- ChangeOrRemoveResolvents change_or_remove_resolvents;
for (Resolutions::ConstIterator r(_imp->resolved->resolutions()->begin()),
r_end(_imp->resolved->resolutions()->end()) ;
r != r_end ; ++r)
@@ -295,7 +312,7 @@ Lineariser::resolve()
_imp->resolved,
_imp->nag,
ignore_dependencies_from_resolvents,
- change_or_remove_resolvents,
+ _imp->change_or_remove_resolvents,
(*r)->resolvent(),
(*r)->decision());
if (! (*r)->decision()->accept_returning<bool>(decision_dispatcher))
@@ -336,7 +353,7 @@ Lineariser::resolve()
for (Set<Resolvent>::ConstIterator r(scc->nodes()->begin()), r_end(scc->nodes()->end()) ;
r != r_end ; ++r)
- if (change_or_remove_resolvents.end() != change_or_remove_resolvents.find(*r))
+ if (_imp->change_or_remove_resolvents.end() != _imp->change_or_remove_resolvents.find(*r))
changes_in_scc.insert(*r);
if (changes_in_scc.empty())
@@ -348,7 +365,7 @@ Lineariser::resolve()
{
/* there's only one real package in the component, so there's no
* need to try anything clever */
- schedule(change_or_remove_resolvents.find(*changes_in_scc.begin())->second);
+ schedule(_imp->change_or_remove_resolvents.find(*changes_in_scc.begin())->second);
}
else
{
@@ -371,28 +388,67 @@ Lineariser::resolve()
/* now we try again, hopefully with lots of small SCCs now */
const std::tr1::shared_ptr<const SortedStronglyConnectedComponents> sub_ssccs(scc_nag.sorted_strongly_connected_components());
- for (SortedStronglyConnectedComponents::ConstIterator sub_scc(sub_ssccs->begin()), sub_scc_end(sub_ssccs->end()) ;
- sub_scc != sub_scc_end ; ++sub_scc)
+ linearise_sub_ssccs(scc_nag, sub_ssccs, true);
+ }
+ }
+}
+
+void
+Lineariser::linearise_sub_ssccs(
+ const NAG & scc_nag,
+ const std::tr1::shared_ptr<const SortedStronglyConnectedComponents> & sub_ssccs,
+ const bool can_recurse)
+{
+ for (SortedStronglyConnectedComponents::ConstIterator sub_scc(sub_ssccs->begin()), sub_scc_end(sub_ssccs->end()) ;
+ sub_scc != sub_scc_end ; ++sub_scc)
+ {
+ if (sub_scc->nodes()->size() == 1)
+ {
+ /* yay. it's all on its own. */
+ schedule(_imp->change_or_remove_resolvents.find(*sub_scc->nodes()->begin())->second);
+ }
+ else if (no_build_dependencies(*sub_scc->nodes(), scc_nag))
+ {
+ /* what's that, timmy? we have directly codependent nodes?
+ * well i'm jolly glad that's because they're run
+ * dependency cycles which we can order however we like! */
+ for (Set<Resolvent>::ConstIterator r(sub_scc->nodes()->begin()), r_end(sub_scc->nodes()->end()) ;
+ r != r_end ; ++r)
+ schedule(_imp->change_or_remove_resolvents.find(*r)->second);
+ }
+ else if (can_recurse)
+ {
+ /* no, at least one of the deps is a build dep. let's try
+ * this whole mess again, except without any edges for
+ * dependencies that're already met */
+ NAG scc_nag_without_met_deps;
+ for (Set<Resolvent>::ConstIterator r(sub_scc->nodes()->begin()), r_end(sub_scc->nodes()->end()) ;
+ r != r_end ; ++r)
{
- if (sub_scc->nodes()->size() == 1)
- {
- /* yay. it's all on its own. */
- schedule(change_or_remove_resolvents.find(*sub_scc->nodes()->begin())->second);
- }
- else
- {
- /* what's that, timmy? we have directly codependent nodes? well i
- * sure do hope that's because they're run dependency cycles! */
-
- /* no, at least one of the deps is a build dep. do we have something
- * installed? */
-
- /* all that effort was wasted. there's incest and there's nothing we
- * can do to fix it. */
- throw InternalError(PALUDIS_HERE, "circular dependencies we're not smart enough to solve yet: { "
- + join(sub_scc->nodes()->begin(), sub_scc->nodes()->end(), ", ") + " }");
- }
+ scc_nag_without_met_deps.add_node(*r);
+ for (NAG::EdgesFromConstIterator e(scc_nag.begin_edges_from(*r)), e_end(scc_nag.end_edges_from(*r)) ;
+ e != e_end ; ++e)
+ if ((! e->second.build_all_met()) || (! e->second.run_all_met()))
+ scc_nag_without_met_deps.add_edge(*r, e->first, make_named_values<NAGEdgeProperties>(
+ n::build() = e->second.build() && ! e->second.build_all_met(),
+ n::build_all_met() = e->second.build_all_met(),
+ n::run() = e->second.run() && ! e->second.run_all_met(),
+ n::run_all_met() = e->second.run_all_met()
+ ));
}
+
+ scc_nag_without_met_deps.verify_edges();
+
+ const std::tr1::shared_ptr<const SortedStronglyConnectedComponents> sub_ssccs_without_met_deps(
+ scc_nag_without_met_deps.sorted_strongly_connected_components());
+ linearise_sub_ssccs(scc_nag_without_met_deps, sub_ssccs_without_met_deps, false);
+ }
+ else
+ {
+ /* all that effort was wasted. there's incest and there's nothing we
+ * can do to fix it. */
+ throw InternalError(PALUDIS_HERE, "circular dependencies we're not smart enough to solve yet: { "
+ + join(sub_scc->nodes()->begin(), sub_scc->nodes()->end(), ", ") + " }");
}
}
}
diff --git a/paludis/resolver/lineariser.hh b/paludis/resolver/lineariser.hh
index e93729f..ac69c50 100644
--- a/paludis/resolver/lineariser.hh
+++ b/paludis/resolver/lineariser.hh
@@ -23,6 +23,8 @@
#include <paludis/resolver/lineariser-fwd.hh>
#include <paludis/resolver/resolved-fwd.hh>
#include <paludis/resolver/decision-fwd.hh>
+#include <paludis/resolver/strongly_connected_component-fwd.hh>
+#include <paludis/resolver/nag-fwd.hh>
#include <paludis/util/private_implementation_pattern.hh>
#include <paludis/environment-fwd.hh>
@@ -36,6 +38,11 @@ namespace paludis
private:
void schedule(const std::tr1::shared_ptr<const ChangeOrRemoveDecision> &);
+ void linearise_sub_ssccs(
+ const NAG &,
+ const std::tr1::shared_ptr<const SortedStronglyConnectedComponents> & sub_ssccs,
+ const bool can_recurse);
+
public:
Lineariser(
const Environment * const,
diff --git a/paludis/resolver/nag.hh b/paludis/resolver/nag.hh
index 5b85e3f..3fec99c 100644
--- a/paludis/resolver/nag.hh
+++ b/paludis/resolver/nag.hh
@@ -33,7 +33,9 @@ namespace paludis
namespace n
{
typedef Name<struct build_name> build;
+ typedef Name<struct build_all_met_name> build_all_met;
typedef Name<struct run_name> run;
+ typedef Name<struct run_all_met_name> run_all_met;
}
namespace resolver
@@ -41,7 +43,9 @@ namespace paludis
struct NAGEdgeProperties
{
NamedValue<n::build, bool> build;
+ NamedValue<n::build_all_met, bool> build_all_met;
NamedValue<n::run, bool> run;
+ NamedValue<n::run_all_met, bool> run_all_met;
NAGEdgeProperties & operator|= (const NAGEdgeProperties &);
};
diff --git a/paludis/resolver/resolver_TEST_cycles.cc b/paludis/resolver/resolver_TEST_cycles.cc
index 792c320..74614e8 100644
--- a/paludis/resolver/resolver_TEST_cycles.cc
+++ b/paludis/resolver/resolver_TEST_cycles.cc
@@ -111,8 +111,6 @@ namespace test_cases
}
} test_no_changes;
-#if 0
-
struct TestExistingUsable : ResolverCyclesTestCase
{
TestExistingUsable() :
@@ -165,8 +163,6 @@ namespace test_cases
}
} test_mutual_run_deps;
-#endif
-
struct TestMutualBuildDeps : ResolverCyclesTestCase
{
TestMutualBuildDeps() : ResolverCyclesTestCase("mutual-build-deps") { }
@@ -176,5 +172,65 @@ namespace test_cases
TEST_CHECK_THROWS(get_resolved("mutual-build-deps/target"), Exception);
}
} test_mutual_build_deps;
+
+ struct TestTriangle : ResolverCyclesTestCase
+ {
+ const bool b_installed;
+ const bool c_installed;
+
+ TestTriangle(bool b, bool c) :
+ ResolverCyclesTestCase("triangle " + stringify(b) + " " + stringify(c)),
+ b_installed(b),
+ c_installed(c)
+ {
+ if (b_installed)
+ install("triangle", "dep-b", "1");
+ if (c_installed)
+ install("triangle", "dep-c", "1");
+ }
+
+ void run()
+ {
+ if ((! b_installed) && (! c_installed))
+ {
+ TEST_CHECK_THROWS(get_resolved("triangle/target"), Exception);
+ return;
+ }
+
+ std::tr1::shared_ptr<const Resolved> resolved(get_resolved("triangle/target"));
+ std::tr1::shared_ptr<DecisionChecks> checks;
+
+ if (b_installed)
+ {
+ checks = make_shared_copy(DecisionChecks()
+ .change(QualifiedPackageName("triangle/dep-c"))
+ .change(QualifiedPackageName("triangle/dep-a"))
+ .change(QualifiedPackageName("triangle/dep-b"))
+ .change(QualifiedPackageName("triangle/target"))
+ .finished());
+ }
+ else if (c_installed)
+ {
+ checks = make_shared_copy(DecisionChecks()
+ .change(QualifiedPackageName("triangle/dep-a"))
+ .change(QualifiedPackageName("triangle/dep-b"))
+ .change(QualifiedPackageName("triangle/dep-c"))
+ .change(QualifiedPackageName("triangle/target"))
+ .finished());
+ }
+ else
+ TEST_CHECK(false);
+
+ check_resolved(resolved,
+ n::display_change_or_remove_decisions() = checks,
+ n::taken_unable_to_make_decisions() = make_shared_copy(DecisionChecks()
+ .finished()),
+ n::untaken_change_or_remove_decisions() = make_shared_copy(DecisionChecks()
+ .finished()),
+ n::untaken_unable_to_make_decisions() = make_shared_copy(DecisionChecks()
+ .finished())
+ );
+ }
+ } test_triangle_none(false, false), test_triangle_b(true, false), test_triangle_c(false, true);
}
diff --git a/paludis/resolver/resolver_TEST_cycles_setup.sh b/paludis/resolver/resolver_TEST_cycles_setup.sh
index 762cad0..a3ca2b3 100755
--- a/paludis/resolver/resolver_TEST_cycles_setup.sh
+++ b/paludis/resolver/resolver_TEST_cycles_setup.sh
@@ -130,5 +130,40 @@ SLOT="0"
DEPENDENCIES="build: mutual-build-deps/dep-b"
END
+# triangle
+echo 'triangle' >> metadata/categories.conf
+
+mkdir -p 'packages/triangle/target'
+cat <<END > packages/triangle/target/target-1.exheres-0
+SUMMARY="target"
+PLATFORMS="test"
+SLOT="0"
+DEPENDENCIES="triangle/dep-c"
+END
+
+mkdir -p 'packages/triangle/dep-a'
+cat <<END > packages/triangle/dep-a/dep-a-1.exheres-0
+SUMMARY="target"
+PLATFORMS="test"
+SLOT="0"
+DEPENDENCIES="run: triangle/dep-b build: triangle/dep-c"
+END
+
+mkdir -p 'packages/triangle/dep-b'
+cat <<END > packages/triangle/dep-b/dep-b-1.exheres-0
+SUMMARY="target"
+PLATFORMS="test"
+SLOT="0"
+DEPENDENCIES="run: triangle/dep-a build: triangle/dep-c"
+END
+
+mkdir -p 'packages/triangle/dep-c'
+cat <<END > packages/triangle/dep-c/dep-c-1.exheres-0
+SUMMARY="target"
+PLATFORMS="test"
+SLOT="0"
+DEPENDENCIES="run: triangle/dep-b"
+END
+
cd ..