aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorAvatar Ciaran McCreesh <ciaran.mccreesh@googlemail.com> 2009-12-06 16:59:03 +0000
committerAvatar Ciaran McCreesh <ciaran.mccreesh@googlemail.com> 2009-12-06 20:43:07 +0000
commit1d7d3717751952e8468b5b95927094924a83da58 (patch)
tree9c63fbc4ddbabf4467315312ce741186b47ba1a4
parentd7ce8b54b2e6b0acda640ba528f5153450a2c5ce (diff)
downloadpaludis-1d7d3717751952e8468b5b95927094924a83da58.tar.gz
paludis-1d7d3717751952e8468b5b95927094924a83da58.tar.xz
New, improved ordering
-rw-r--r--paludis/resolver/orderer.cc263
-rw-r--r--paludis/resolver/orderer.hh7
2 files changed, 170 insertions, 100 deletions
diff --git a/paludis/resolver/orderer.cc b/paludis/resolver/orderer.cc
index 7fb9489..4aea541 100644
--- a/paludis/resolver/orderer.cc
+++ b/paludis/resolver/orderer.cc
@@ -547,139 +547,213 @@ Orderer::_resolve_jobs_dep_arrows()
void
Orderer::_resolve_order()
{
- bool remaining(true);
- int pass(1);
- while (remaining)
+ while (true)
{
- remaining = false;
- bool any(false);
+ _imp->env->trigger_notifier_callback(NotifierCallbackResolverStageEvent("Ordering"));
- _imp->env->trigger_notifier_callback(NotifierCallbackResolverStepEvent());
+ /* anything left? */
+ if (! _anything_left_to_order())
+ break;
- for (JobIDSequence::ConstIterator i(_imp->lists->unordered_job_ids()->begin()),
- i_end(_imp->lists->unordered_job_ids()->end()) ;
- i != i_end ; ++i)
- {
- if (_already_ordered(*i))
- continue;
+ /* first attempt: nothing fancy */
+ if (_order_some(false, false))
+ continue;
- remaining = true;
+ _imp->env->trigger_notifier_callback(NotifierCallbackResolverStageEvent("Ordering Usable Cycles"));
- if (! _can_order(*i, pass))
- continue;
+ /* second attempt: remove cycles containing only usable jobs */
+ if (_remove_usable_cycles())
+ continue;
- _imp->lists->ordered_job_ids()->push_back(*i);
- any = true;
- _mark_already_ordered(*i);
+ _imp->env->trigger_notifier_callback(NotifierCallbackResolverStageEvent("Ordering Using Existing"));
- if (pass >= 2)
- {
- std::stringstream s;
- const std::tr1::shared_ptr<const Job> job(_imp->lists->jobs()->fetch(*i));
- for (ArrowSequence::ConstIterator a(job->arrows()->begin()), a_end(job->arrows()->end()) ;
- a != a_end ; ++a)
- if (! _already_ordered(a->comes_after()))
- s << " " << a->comes_after().string_id();
-
- Log::get_instance()->message("resolver.orderer.job.broke_cycle", ll_warning, lc_context)
- << "Had to use cycle breaking to order " << i->string_id() << " (pass " << pass
- << ", remaining arrows are" << s.str() << ")";
-
- pass = 1;
- continue;
- }
- }
+ /* third attempt: remove an install job whose deps are already met */
+ if (_order_some(true, true))
+ continue;
- if (remaining && ! any)
- {
- if (++pass < 3)
- continue;
+ _imp->env->trigger_notifier_callback(NotifierCallbackResolverStageEvent("Ordering Using Any Existing"));
- std::stringstream s;
- for (JobIDSequence::ConstIterator i(_imp->lists->unordered_job_ids()->begin()),
- i_end(_imp->lists->unordered_job_ids()->end()) ;
- i != i_end ; ++i)
- {
- if (_already_ordered(*i))
- continue;
-
- s << " {{{" << i->string_id() << " missing";
- const std::tr1::shared_ptr<const Job> job(_imp->lists->jobs()->fetch(*i));
- for (ArrowSequence::ConstIterator a(job->arrows()->begin()), a_end(job->arrows()->end()) ;
- a != a_end ; ++a)
- if (! _already_ordered(a->comes_after()))
- s << " [" << a->comes_after().string_id() << "]";
- s << " }}}";
- }
+ if (_order_some(true, false))
+ continue;
- throw InternalError(PALUDIS_HERE, "unbreakable cycle, remaining" + s.str());
- }
+ _cycle_error();
}
}
-namespace
+bool
+Orderer::_anything_left_to_order() const
{
- typedef std::tr1::function<bool (const PackageOrBlockDepSpec &)> AlreadyMetFn;
+ for (JobIDSequence::ConstIterator i(_imp->lists->unordered_job_ids()->begin()),
+ i_end(_imp->lists->unordered_job_ids()->end()) ;
+ i != i_end ; ++i)
+ {
+ if (_already_ordered(*i))
+ continue;
- struct AlreadyMetDep
+ return true;
+ }
+
+ return false;
+}
+
+bool
+Orderer::_order_some(const bool desperate, const bool installs_only)
+{
+ bool result(false);
+
+ for (JobIDSequence::ConstIterator i(_imp->lists->unordered_job_ids()->begin()),
+ i_end(_imp->lists->unordered_job_ids()->end()) ;
+ i != i_end ; ++i)
{
- bool visit(const PresetReason &) const
- {
- return false;
- }
+ if (_already_ordered(*i))
+ continue;
- bool visit(const TargetReason &) const
+ if (installs_only)
{
- return false;
+ const std::tr1::shared_ptr<const Job> job(_imp->lists->jobs()->fetch(*i));
+ if (! simple_visitor_cast<const SimpleInstallJob>(*job))
+ continue;
}
- bool visit(const SetReason & r) const
- {
- return r.reason_for_set()->accept_returning<bool>(*this);
- }
+ if (! _can_order(*i, desperate))
+ continue;
- bool visit(const DependencyReason & r) const
+ if (desperate)
{
- return r.already_met();
+ const std::tr1::shared_ptr<const Job> job(_imp->lists->jobs()->fetch(*i));
+ std::stringstream s;
+ for (ArrowSequence::ConstIterator a(job->arrows()->begin()), a_end(job->arrows()->end()) ;
+ a != a_end ; ++a)
+ if (! _already_ordered(a->comes_after()))
+ {
+ if (! s.str().empty())
+ s << ", ";
+ s << a->comes_after().string_id();
+ }
+
+ Log::get_instance()->message("resolver.orderer.cycle_breaking.already_met", ll_warning, lc_context)
+ << "Had to use existing packages to order " << i->string_id() << " (unmet deps are " << s.str() << ")";
}
- };
- struct Pass1Ignorable
+ _imp->lists->ordered_job_ids()->push_back(*i);
+ _mark_already_ordered(*i);
+ result = true;
+ }
+
+ return result;
+}
+
+bool
+Orderer::_remove_usable_cycles()
+{
+ /* we only want to remove usable jobs... */
+ std::tr1::unordered_set<JobID, Hash<JobID> > removable;
+ for (JobIDSequence::ConstIterator i(_imp->lists->unordered_job_ids()->begin()),
+ i_end(_imp->lists->unordered_job_ids()->end()) ;
+ i != i_end ; ++i)
{
- bool visit(const UsableJob &) const
- {
- return true;
- }
+ if (_already_ordered(*i))
+ continue;
+
+ const std::tr1::shared_ptr<const Job> job(_imp->lists->jobs()->fetch(*i));
+ if (simple_visitor_cast<const UsableJob>(*job))
+ removable.insert(job->id());
+ }
- bool visit(const PretendJob &) const
+ /* but we don't want to remove any job unless it only requires other jobs that
+ * we're going to remove. */
+ while (true)
+ {
+ bool need_another_pass(false);
+ /* hashes have annoying invalidation rules */
+ std::list<JobID> removable_copy(removable.begin(), removable.end());
+ for (std::list<JobID>::iterator i(removable_copy.begin()), i_end(removable_copy.end()) ;
+ i != i_end ; ++i)
{
- return false;
+ bool ok(true);
+ const std::tr1::shared_ptr<const Job> job(_imp->lists->jobs()->fetch(*i));
+ for (ArrowSequence::ConstIterator a(job->arrows()->begin()), a_end(job->arrows()->end()) ;
+ a != a_end ; ++a)
+ if (! _already_ordered(a->comes_after()))
+ if (removable.end() == removable.find(a->comes_after()))
+ {
+ need_another_pass = true;
+ ok = false;
+ break;
+ }
+
+ if (! ok)
+ removable.erase(*i);
}
- bool visit(const SyncPointJob &) const
+ if (! need_another_pass)
+ break;
+ }
+
+ for (std::tr1::unordered_set<JobID, Hash<JobID> >::iterator i(removable.begin()),
+ i_end(removable.end()) ;
+ i != i_end ; ++i)
+ {
+ _imp->lists->ordered_job_ids()->push_back(*i);
+ _mark_already_ordered(*i);
+ }
+
+ return ! removable.empty();
+}
+
+void
+Orderer::_cycle_error()
+{
+ std::stringstream s;
+ for (JobIDSequence::ConstIterator i(_imp->lists->unordered_job_ids()->begin()),
+ i_end(_imp->lists->unordered_job_ids()->end()) ;
+ i != i_end ; ++i)
+ {
+ if (_already_ordered(*i))
+ continue;
+
+ s << " {{{" << i->string_id() << " missing";
+ const std::tr1::shared_ptr<const Job> job(_imp->lists->jobs()->fetch(*i));
+ for (ArrowSequence::ConstIterator a(job->arrows()->begin()), a_end(job->arrows()->end()) ;
+ a != a_end ; ++a)
+ if (! _already_ordered(a->comes_after()))
+ s << " [" << a->comes_after().string_id() << "]";
+ s << " }}}";
+ }
+
+ throw InternalError(PALUDIS_HERE, "can't order any of " + s.str());
+}
+
+namespace
+{
+ typedef std::tr1::function<bool (const PackageOrBlockDepSpec &)> AlreadyMetFn;
+
+ struct AlreadyMetDep
+ {
+ bool visit(const PresetReason &) const
{
return false;
}
- bool visit(const FetchJob &) const
+ bool visit(const TargetReason &) const
{
return false;
}
- bool visit(const UntakenInstallJob &) const
+ bool visit(const SetReason & r) const
{
- return false;
+ return r.reason_for_set()->accept_returning<bool>(*this);
}
- bool visit(const SimpleInstallJob &) const
+ bool visit(const DependencyReason & r) const
{
- return false;
+ return r.already_met();
}
};
}
bool
-Orderer::_can_order(const JobID & i, const int pass) const
+Orderer::_can_order(const JobID & i, const bool desperate) const
{
const std::tr1::shared_ptr<const Job> job(_imp->lists->jobs()->fetch(i));
for (ArrowSequence::ConstIterator a(job->arrows()->begin()), a_end(job->arrows()->end()) ;
@@ -689,18 +763,7 @@ Orderer::_can_order(const JobID & i, const int pass) const
{
bool skippable(false);
- if ((! skippable) && (pass >= 1))
- {
- /* if our job is a NoChangeJob or a UsableJob, and we're
- * supposed to come after a NoChangeJob or a UsableJob, ignore
- * the arrow. */
- const std::tr1::shared_ptr<const Job> other_job(_imp->lists->jobs()->fetch(a->comes_after()));
- if (job->accept_returning<bool>(Pass1Ignorable()) &&
- other_job->accept_returning<bool>(Pass1Ignorable()))
- skippable = true;
- }
-
- if ((! skippable) && (pass >= 2))
+ if ((! skippable) && desperate)
{
/* we can also ignore any arrows that are already met (e.g a
* dep b, b dep a, a is already installed */
@@ -727,5 +790,7 @@ Orderer::_mark_already_ordered(const JobID & i)
{
if (! _imp->already_ordered.insert(i).second)
throw InternalError(PALUDIS_HERE, "already already ordered");
+
+ _imp->env->trigger_notifier_callback(NotifierCallbackResolverStepEvent());
}
diff --git a/paludis/resolver/orderer.hh b/paludis/resolver/orderer.hh
index 2c10677..313d19d 100644
--- a/paludis/resolver/orderer.hh
+++ b/paludis/resolver/orderer.hh
@@ -49,9 +49,14 @@ namespace paludis
void _resolve_order();
bool _already_ordered(const JobID &) const PALUDIS_ATTRIBUTE((warn_unused_result));
- bool _can_order(const JobID &, const int pass) const PALUDIS_ATTRIBUTE((warn_unused_result));
+ bool _can_order(const JobID &, const bool desperate) const PALUDIS_ATTRIBUTE((warn_unused_result));
void _mark_already_ordered(const JobID &);
+ bool _anything_left_to_order() const PALUDIS_ATTRIBUTE((warn_unused_result));
+ bool _order_some(const bool desperate, const bool installs_only) PALUDIS_ATTRIBUTE((warn_unused_result));
+ bool _remove_usable_cycles() PALUDIS_ATTRIBUTE((warn_unused_result));
+ void _cycle_error() PALUDIS_ATTRIBUTE((noreturn));
+
public:
Orderer(
const Environment * const,