diff options
| -rw-r--r-- | src/generic/problemresolver/problemresolver.h | 282 | ||||
| -rw-r--r-- | src/generic/problemresolver/search_graph.h | 77 | ||||
| -rw-r--r-- | tests/test_resolver.cc | 25 |
3 files changed, 250 insertions, 134 deletions
diff --git a/src/generic/problemresolver/problemresolver.h b/src/generic/problemresolver/problemresolver.h index cd1f427c..a708b0f6 100644 --- a/src/generic/problemresolver/problemresolver.h +++ b/src/generic/problemresolver/problemresolver.h @@ -978,6 +978,7 @@ private: deferred_choice.get_dep()); else { + LOG_TRACE(resolver.logger, deferred_choice << " is now deferred; marking it as such in all active steps."); // Note that this is not quite right in logical terms. // Technically, the promotion we generate should contain the // choice that led to the deferral. However, that's not @@ -1231,61 +1232,49 @@ private: graph.schedule_promotion_propagation(step_num, p); } - /** \brief Utility structure used to find incipient promotions. - * - * While searching for incipient promotions, we allocate one of - * these for each step hit by a promotion. A promotion is - * incipient in a given step if each of its choices is mapped to - * the step in the global choice index, and if exactly one of those - * choices is a solver. - */ - struct incipient_promotion_search_info - { - /** \brief Counts the number of times the promotion hits the - * action set. - */ - int action_hits; - - /** \brief Counts the number of times the promotion hits the - * solver set. - */ - int solver_hits; - - /** \brief Set to the first choice in the promotion that was - * mapped to a solver. - * - * We only need to store one because there will only be a single - * choice stored as a solver in steps that contain all but one - * choice as an action. We can count on that because actions and - * solvers are not allowed to overlap. - */ - choice solver; - - incipient_promotion_search_info() - : action_hits(0), solver_hits(0) - { - } - }; - // Helper function for find_steps_containing_incipient_promotion. - // Processes mapping information and updates the counters. + // Processes mapping information and updates the counters; when a + // hit is found, inserts it into an output set. // - // Note that the same choice could show up as a solver for several - // different dependencies, so we need to remember which steps we - // already incremented the solver-hits counter for. + // We don't immediately invoke a callback, because that might + // actually lead to doing the wrong thing. If several different + // solvers (say, different from-source-dep solvers that install the + // same version) hit the same promotion, then applying the promotion + // immediately when we see the first solver might remove the other + // ones. When the caller finishes tracing the tree for the first + // solver, it'll notice that the root step lacks the other solver + // and not visit anything. class update_incipient_promotion_information { - std::map<int, incipient_promotion_search_info> &output; - std::set<int> &visited_solver_steps; + generic_problem_resolver &resolver; + const unsigned int promotion_search_index; + const unsigned int promotion_size; const choice &promotion_c; + std::set<int> &active_hits; // Steps that contain the promotion in + // their action set. + std::set<int> &incipient_hits; // Steps that contain the promotion + // as an incipient promotion. + + void too_many_choices(int choices) const + { + LOG_ERROR(resolver.logger, "Internal error: the choice " << promotion_c + << " is match number " << choices + << " against a promotion of size " << promotion_size); + } public: - update_incipient_promotion_information(std::map<int, incipient_promotion_search_info> &_output, - std::set<int> &_visited_solver_steps, - const choice &_promotion_c) - : output(_output), - visited_solver_steps(_visited_solver_steps), - promotion_c(_promotion_c) + update_incipient_promotion_information(generic_problem_resolver &_resolver, + unsigned int _promotion_search_index, + unsigned int _promotion_size, + const choice &_promotion_c, + std::set<int> &_active_hits, + std::set<int> &_incipient_hits) + : resolver(_resolver), + promotion_search_index(_promotion_search_index), + promotion_size(_promotion_size), + promotion_c(_promotion_c), + active_hits(_active_hits), + incipient_hits(_incipient_hits) { } @@ -1293,58 +1282,124 @@ private: const typename search_graph::choice_mapping_type how, int step_num) const { - incipient_promotion_search_info &output_inf(output[step_num]); + step &s(resolver.graph.get_step(step_num)); + LOG_TRACE(resolver.logger, "update_incipient_promotion_information: visiting step " << step_num << " for " << c); + + if(s.last_promotion_search != promotion_search_index) + { + s.last_promotion_search = promotion_search_index; + s.choice_set_hit_count = 0; + s.solver_set_hit_count = 0; + } + // Short-circuit if we can't possibly match. + else if(s.solver_set_hit_count > 1) + return true; switch(how) { case search_graph::choice_mapping_action: - ++output_inf.action_hits; + LOG_TRACE(resolver.logger, "Hit step " << step_num << " as an action with " << c); + ++s.choice_set_hit_count; + if(s.choice_set_hit_count > promotion_size) + { + too_many_choices(s.choice_set_hit_count); + return true; + } break; case search_graph::choice_mapping_solver: - { - bool already_visited = - !visited_solver_steps.insert(step_num).second; - - if(already_visited) + LOG_TRACE(resolver.logger, "Hit step " << step_num << " as a solver with " << c); + if(s.solver_set_hit_count == 0) + { + s.solver_set_hit_count = 1; + s.first_solver_hit = promotion_c; + } + else if(s.first_solver_hit.contains(promotion_c)) + // This is the same choice we already stored, so do + // nothing. + return true; + else if(promotion_c.contains(s.first_solver_hit)) + // This is a more general version of the choice we already + // stored. + { + s.first_solver_hit = promotion_c; return true; - } + } + else + // If we see a new solver, increment the solver hit count + // (thus marking this solver as invalid). + ++s.solver_set_hit_count; - ++output_inf.solver_hits; - output_inf.solver = promotion_c; break; } + if(s.solver_set_hit_count <= 1 && + s.choice_set_hit_count + s.solver_set_hit_count == promotion_size) + { + if(s.solver_set_hit_count == 0) + active_hits.insert(step_num); + else + incipient_hits.insert(step_num); + } + return true; } }; + template<typename Callbacks> class find_steps_containing_incipient_promotion { - // Note: would it be more efficient to use an array? Usually - // there aren't that many steps anyway. I could even store this - // information in the global step array; that would more or less - // eliminate the cost of maintaining this structure, and it would - // be safe since this isn't reentrant (same trick I use for - // promotions). - std::map<int, incipient_promotion_search_info> &output; - const search_graph &graph; + generic_problem_resolver &resolver; + unsigned int promotion_search_index; + const promotion &p; + Callbacks callbacks; public: - find_steps_containing_incipient_promotion(std::map<int, incipient_promotion_search_info> &_output, - const search_graph &_graph) - : output(_output), - graph(_graph) + find_steps_containing_incipient_promotion(generic_problem_resolver &_resolver, + unsigned int _promotion_search_index, + const promotion &_p, + Callbacks _callbacks) + : resolver(_resolver), + promotion_search_index(_promotion_search_index), + p(_p), + callbacks(_callbacks) { } bool operator()(const choice &c) const { - std::set<int> steps_containing_c_as_a_solver; + std::set<int> active_hits; + std::set<int> incipient_hits; + update_incipient_promotion_information - update_f(output, steps_containing_c_as_a_solver, c); + update_f(resolver, + promotion_search_index, + p.get_choices().size(), + c, + active_hits, + incipient_hits); + + resolver.graph.for_each_step_related_to_choice(c, update_f); + + for(std::set<int>::const_iterator it = active_hits.begin(); + it != active_hits.end(); ++it) + { + int step_num(*it); + + LOG_DEBUG(resolver.logger, "Step " << step_num + << " contains " << p + << " as an active promotion."); + callbacks.active(step_num); + } + + for(std::set<int>::const_iterator it = incipient_hits.begin(); + it != incipient_hits.end(); ++it) + { + int step_num(*it); + step &s(resolver.graph.get_step(step_num)); - graph.for_each_step_related_to_choice(c, update_f); + callbacks.incipient(step_num, s.first_solver_hit); + } return true; } @@ -1356,62 +1411,14 @@ private: * callbacks.active(step_num) if it's contained in the action set. */ template<typename Callbacks> - void for_each_promotion_hit(const promotion &p, Callbacks callbacks) const + void for_each_promotion_hit(const promotion &p, Callbacks callbacks) { - std::map<int, incipient_promotion_search_info> search_result; - { - find_steps_containing_incipient_promotion - find_promotion_f(search_result, graph); - p.get_choices().for_each(find_promotion_f); - } - - int num_promotion_choices = p.get_choices().size(); - for(typename std::map<int, incipient_promotion_search_info>::const_iterator - it = search_result.begin(); it != search_result.end(); ++it) - { - const int step_num(it->first); - const incipient_promotion_search_info &inf(it->second); - - if(inf.action_hits == num_promotion_choices) - { - const step &s(graph.get_step(step_num)); - if(s.step_tier < p.get_tier()) - { - LOG_TRACE(logger, "Step " << step_num - << " contains " << p - << " as an active promotion."); - - callbacks.active(step_num); - } - } - else if(inf.action_hits + 1 != num_promotion_choices) - { - LOG_TRACE(logger, "Step " << step_num - << " does not contain " << p - << " as an incipient promotion; it includes " - << inf.action_hits - << " choices from the promotion (needed " - << (num_promotion_choices - 1) - << ")"); - } - else if(inf.solver_hits != 1) - { - LOG_TRACE(logger, "Step " << step_num - << " does not contain " << p - << " as an incipient promotion: " - << inf.solver_hits - << " of its solvers are contained in the promotion (needed 1)."); - } - else - { - LOG_DEBUG(logger, "Step " << step_num - << " contains " << p - << " as an incipient promotion for the solver " - << inf.solver); - - callbacks.incipient(step_num, inf.solver); - } - } + find_steps_containing_incipient_promotion<Callbacks> + find_promotion_f(*this, + graph.get_and_increment_promotion_search_index(), + p, + callbacks); + p.get_choices().for_each(find_promotion_f); } /** \brief For each promotion hit, increase its tier in a solver set @@ -2577,6 +2584,9 @@ private: void increase_solver_tier_everywhere(const choice &solver, const promotion &p) { + LOG_TRACE(logger, "Increasing the tier of " << solver + << " according to the promotion " << p + << " in all active steps."); do_increase_solver_tier_everywhere increase_solver_tier_everywhere_f(*this, solver, p); @@ -3305,6 +3315,8 @@ public: if(!inf.get_rejected()->get_value()) { + LOG_TRACE(logger, "Rejecting " << ver); + if(undo != NULL) undo->add_item(new undo_resolver_manipulation<PackageUniverse, version>(this, ver, &generic_problem_resolver<PackageUniverse>::unreject_version)); @@ -3322,6 +3334,8 @@ public: if(inf.get_rejected()->get_value()) { + LOG_TRACE(logger, "Canceling the rejection of " << ver); + if(undo != NULL) undo->add_item(new undo_resolver_manipulation<PackageUniverse, version>(this, ver, &generic_problem_resolver<PackageUniverse>::reject_version)); @@ -3335,6 +3349,8 @@ public: if(!inf.get_approved()->get_value()) { + LOG_TRACE(logger, "Mandating " << ver); + if(undo != NULL) undo->add_item(new undo_resolver_manipulation<PackageUniverse, version>(this, ver, &generic_problem_resolver<PackageUniverse>::unmandate_version)); @@ -3349,6 +3365,8 @@ public: if(inf.get_approved()->get_value()) { + LOG_TRACE(logger, "Un-mandating " << ver); + if(undo != NULL) undo->add_item(new undo_resolver_manipulation<PackageUniverse, version>(this, ver, &generic_problem_resolver<PackageUniverse>::mandate_version)); @@ -3398,6 +3416,8 @@ public: if(!inf.get_rejected()->get_value()) { + LOG_TRACE(logger, "Hardening " << d); + if(undo != NULL) undo->add_item(new undo_resolver_manipulation<PackageUniverse, dep>(this, d, &generic_problem_resolver<PackageUniverse>::unharden)); @@ -3413,6 +3433,8 @@ public: if(inf.get_rejected()->get_value()) { + LOG_TRACE(logger, "Un-hardening " << d); + if(undo != NULL) undo->add_item(new undo_resolver_manipulation<PackageUniverse, dep>(this, d, &generic_problem_resolver<PackageUniverse>::harden)); @@ -3440,6 +3462,8 @@ public: if(!inf.get_approved()->get_value()) { + LOG_TRACE(logger, "Approving breaking " << d); + if(undo != NULL) undo->add_item(new undo_resolver_manipulation<PackageUniverse, dep>(this, d, &generic_problem_resolver<PackageUniverse>::unapprove_break)); @@ -3455,6 +3479,8 @@ public: if(inf.get_approved()->get_value()) { + LOG_TRACE(logger, "Un-approving breaking " << d); + if(undo != NULL) undo->add_item(new undo_resolver_manipulation<PackageUniverse, dep>(this, d, &generic_problem_resolver<PackageUniverse>::approve_break)); diff --git a/src/generic/problemresolver/search_graph.h b/src/generic/problemresolver/search_graph.h index d8c1bf3b..c03e09be 100644 --- a/src/generic/problemresolver/search_graph.h +++ b/src/generic/problemresolver/search_graph.h @@ -314,6 +314,41 @@ public: // successors are generated. int first_child; + /** \brief Members used while searching promotions in existing + * steps. + */ + + // @{ + + /** \brief The index of the last promotion search. + * + * Initially zero; the promotion searcher uses this to determine + * whether the hit counts need to be reset to zero. + */ + unsigned int last_promotion_search; + + /** \brief The number of times that the choice set was hit by a + * promotion. + * + * Initially zero. + */ + unsigned int choice_set_hit_count; + + /** \brief The number of times that the solver set was hit by a + * promotion. + * + * Initially zero. + */ + unsigned int solver_set_hit_count; + + /** \brief The first solver that was found to hit a promotion. + * + * Only meaningful if solver_set_hit_count > 0. + */ + choice first_solver_hit; + + // @} + /** \brief Members related to generating a step's * successor. */ @@ -451,6 +486,10 @@ public: : is_last_child(true), is_blessed_solution(false), parent(-1), first_child(-1), + last_promotion_search(0), + choice_set_hit_count(0), + solver_set_hit_count(0), + first_solver_hit(), is_deferred_listener(), canonical_clone(-1), reason(), @@ -470,7 +509,12 @@ public: int _action_score) : is_last_child(true), is_blessed_solution(false), - parent(-1), first_child(-1), canonical_clone(-1), + parent(-1), first_child(-1), + last_promotion_search(0), + choice_set_hit_count(0), + solver_set_hit_count(0), + first_solver_hit(), + canonical_clone(-1), actions(_actions), score(_score), action_score(_action_score), @@ -492,7 +536,12 @@ public: : is_last_child(_is_last_child), is_blessed_solution(false), parent(_parent), - first_child(-1), canonical_clone(-1), + first_child(-1), + last_promotion_search(0), + choice_set_hit_count(0), + solver_set_hit_count(0), + first_solver_hit(), + canonical_clone(-1), actions(_actions), score(_score), action_score(_action_score), @@ -585,6 +634,17 @@ private: */ generic_choice_indexed_map<PackageUniverse, choice_mapping_info> steps_related_to_choices; + /** \brief The index of the next promotion search. + * + * This is used as an alternative to maintaining costly structures + * to determine which steps we hit and/or to clear hit counts. Hit + * counts in a step are only valid if the step's + * last_promotion_search member is equal to the index of the + * current promotion search. Otherwise, they are presumed to be + * zero. + */ + int next_promotion_search_index; + public: /** \brief Add an entry to the choice->step reverse index. * @@ -893,7 +953,8 @@ public: */ generic_search_graph(promotion_set &_promotions) : logger(aptitude::Loggers::getAptitudeResolverSearchGraph()), - promotions(_promotions) + promotions(_promotions), + next_promotion_search_index(0) { } @@ -931,6 +992,16 @@ public: return steps.size(); } + /** \brief Retrieve the next promotion search index, incrementing it + * in the process. + */ + int get_and_increment_promotion_search_index() + { + const int rval = next_promotion_search_index; + ++next_promotion_search_index; + return rval; + } + public: step &add_step() { diff --git a/tests/test_resolver.cc b/tests/test_resolver.cc index d320c7a1..c58b35cb 100644 --- a/tests/test_resolver.cc +++ b/tests/test_resolver.cc @@ -320,7 +320,8 @@ private: void testTiers() { - LOG_TRACE(log4cxx::Logger::getLogger("test.resolver.testTiers"), "Entering testTiers"); + log4cxx::LoggerPtr logger(log4cxx::Logger::getLogger("test.resolver.testTiers")); + LOG_TRACE(logger, "Entering testTiers"); dummy_universe_ref u = parseUniverse(dummy_universe_2); @@ -341,6 +342,8 @@ private: choice_set av2_choices; av2_choices.insert_or_narrow(choice::make_install_version(av2, 0)); + LOG_TRACE(logger, "Verifying that without a tier the shortest solution is produced first and there are two solutions."); + // Verify that without a tier we get the shorter solution first. // Without this we aren't testing anything! { @@ -361,6 +364,8 @@ private: CPPUNIT_FAIL("Expected two solutions, got none."); } + LOG_TRACE(logger, "Got first solution: " << sol); + assertSameEffect(av2_choices, sol.get_choices()); try @@ -372,21 +377,28 @@ private: CPPUNIT_FAIL("Expected two solutions, got only one."); } + LOG_TRACE(logger, "Got second solution: " << sol); + assertSameEffect(av1_choices, sol.get_choices()); bool done = false; try { - r.find_next_solution(1000000, NULL); + sol = r.find_next_solution(1000000, NULL); } catch(NoMoreSolutions) { done = true; } + if(!done) + LOG_ERROR(logger, "Got unexpected third solution: " << sol); + CPPUNIT_ASSERT_MESSAGE("Expected two solutions, got more.", done); } + LOG_TRACE(logger, "Checking that adjusting tiers changes the output."); + // Now check that adjusting tiers changes the output. { dummy_resolver r(10, -300, -100, 100000, 50000, 50, @@ -407,6 +419,8 @@ private: CPPUNIT_FAIL("Expected two solutions, got none."); } + LOG_TRACE(logger, "Got first solution: " << sol); + assertSameEffect(av1_choices, sol.get_choices()); try @@ -418,18 +432,23 @@ private: CPPUNIT_FAIL("Expected two solutions, got only one."); } + LOG_TRACE(logger, "Got second solution: " << sol); + assertSameEffect(av2_choices, sol.get_choices()); bool done = false; try { - r.find_next_solution(1000000, NULL); + sol = r.find_next_solution(1000000, NULL); } catch(NoMoreSolutions) { done = true; } + if(!done) + LOG_ERROR(logger, "Got an unexpected third solution: " << sol); + CPPUNIT_ASSERT_MESSAGE("Expected two solutions, got more.", done); } } |