src/problems.c

   1 /*
   2  * Copyright (c) 2007-2009, Novell Inc.
   3  *
   4  * This program is licensed under the BSD license, read LICENSE.BSD
   5  * for further information
   6  */
   7
   8 /*
   9  * problems.c
  10  *
  11  */
  12
  13 #include <stdio.h>
  14 #include <stdlib.h>
  15 #include <unistd.h>
  16 #include <string.h>
  17 #include <assert.h>
  18
  19 #include "solver.h"
  20 #include "solver_private.h"
  21 #include "bitmap.h"
  22 #include "pool.h"
  23 #include "util.h"
  24 #include "evr.h"
  25 #include "solverdebug.h"
  26
  27
  28 /**********************************************************************************/
  29
  30 /* a problem is an item on the solver's problem list. It can either be >0, in that
  31  * case it is a update/infarch/dup rule, or it can be <0, which makes it refer to a job
  32  * consisting of multiple job rules.
  33  */
  34
  35 void
  36 solver_disableproblem(Solver *solv, Id v)
  37 {
  38   Rule *r;
  39   int i;
  40   Id *jp;
  41
  42   if (v > 0)
  43     {
  44       if (v >= solv->infarchrules && v < solv->infarchrules_end)
  45         {
  46           Pool *pool = solv->pool;
  47           Id name = pool->solvables[-solv->rules[v].p].name;
  48           while (v > solv->infarchrules && pool->solvables[-solv->rules[v - 1].p].name == name)
  49             v--;
  50           for (; v < solv->infarchrules_end && pool->solvables[-solv->rules[v].p].name == name; v++)
  51             solver_disablerule(solv, solv->rules + v);
  52           return;
  53         }
  54       if (v >= solv->duprules && v < solv->duprules_end)
  55         {
  56           Pool *pool = solv->pool;
  57           Id name = pool->solvables[-solv->rules[v].p].name;
  58           while (v > solv->duprules && pool->solvables[-solv->rules[v - 1].p].name == name)
  59             v--;
  60           for (; v < solv->duprules_end && pool->solvables[-solv->rules[v].p].name == name; v++)
  61             solver_disablerule(solv, solv->rules + v);
  62           return;
  63         }
  64       solver_disablerule(solv, solv->rules + v);
  65 #if 0
  66       /* XXX: doesn't work */
  67       if (v >= solv->updaterules && v < solv->updaterules_end)
  68         {
  69           /* enable feature rule if we disabled the update rule */
  70           r = solv->rules + (v - solv->updaterules + solv->featurerules);
  71           if (r->p)
  72             solver_enablerule(solv, r);
  73         }
  74 #endif
  75       return;
  76     }
  77   v = -(v + 1);
  78   jp = solv->ruletojob.elements;
  79   for (i = solv->jobrules, r = solv->rules + i; i < solv->jobrules_end; i++, r++, jp++)
  80     if (*jp == v)
  81       solver_disablerule(solv, r);
  82 }
  83
  84 /*-------------------------------------------------------------------
  85  * enableproblem
  86  */
  87
  88 void
  89 solver_enableproblem(Solver *solv, Id v)
  90 {
  91   Rule *r;
  92   int i;
  93   Id *jp;
  94
  95   if (v > 0)
  96     {
  97       if (v >= solv->infarchrules && v < solv->infarchrules_end)
  98         {
  99           Pool *pool = solv->pool;
 100           Id name = pool->solvables[-solv->rules[v].p].name;
 101           while (v > solv->infarchrules && pool->solvables[-solv->rules[v - 1].p].name == name)
 102             v--;
 103           for (; v < solv->infarchrules_end && pool->solvables[-solv->rules[v].p].name == name; v++)
 104             solver_enablerule(solv, solv->rules + v);
 105           return;
 106         }
 107       if (v >= solv->duprules && v < solv->duprules_end)
 108         {
 109           Pool *pool = solv->pool;
 110           Id name = pool->solvables[-solv->rules[v].p].name;
 111           while (v > solv->duprules && pool->solvables[-solv->rules[v - 1].p].name == name)
 112             v--;
 113           for (; v < solv->duprules_end && pool->solvables[-solv->rules[v].p].name == name; v++)
 114             solver_enablerule(solv, solv->rules + v);
 115           return;
 116         }
 117       if (v >= solv->featurerules && v < solv->featurerules_end)
 118         {
 119           /* do not enable feature rule if update rule is enabled */
 120           r = solv->rules + (v - solv->featurerules + solv->updaterules);
 121           if (r->d >= 0)
 122             return;
 123         }
 124       solver_enablerule(solv, solv->rules + v);
 125       if (v >= solv->updaterules && v < solv->updaterules_end)
 126         {
 127           /* disable feature rule when enabling update rule */
 128           r = solv->rules + (v - solv->updaterules + solv->featurerules);
 129           if (r->p)
 130             solver_disablerule(solv, r);
 131         }
 132       return;
 133     }
 134   v = -(v + 1);
 135   jp = solv->ruletojob.elements;
 136   for (i = solv->jobrules, r = solv->rules + i; i < solv->jobrules_end; i++, r++, jp++)
 137     if (*jp == v)
 138       solver_enablerule(solv, r);
 139 }
 140
 141
 142 /*-------------------------------------------------------------------
 143  * enable weak rules
 144  *
 145  * Reenable all disabled weak rules (marked in weakrulemap)
 146  *
 147  */
 148
 149 static void
 150 enableweakrules(Solver *solv)
 151 {
 152   int i;
 153   Rule *r;
 154
 155   for (i = 1, r = solv->rules + i; i < solv->learntrules; i++, r++)
 156     {
 157       if (r->d >= 0) /* already enabled? */
 158         continue;
 159       if (!MAPTST(&solv->weakrulemap, i))
 160         continue;
 161       solver_enablerule(solv, r);
 162     }
 163 }
 164
 165
 166 /*-------------------------------------------------------------------
 167  *
 168  * refine_suggestion
 169  *
 170  * at this point, all rules that led to conflicts are disabled.
 171  * we re-enable all rules of a problem set but rule "sug", then
 172  * continue to disable more rules until there as again a solution.
 173  */
 174
 175 /* FIXME: think about conflicting assertions */
 176
 177 static void
 178 refine_suggestion(Solver *solv, Id *problem, Id sug, Queue *refined, int essentialok)
 179 {
 180   Pool *pool = solv->pool;
 181   int i, j;
 182   Id v;
 183   Queue disabled;
 184   int disabledcnt;
 185
 186   IF_POOLDEBUG (SAT_DEBUG_SOLUTIONS)
 187     {
 188       POOL_DEBUG(SAT_DEBUG_SOLUTIONS, "refine_suggestion start\n");
 189       for (i = 0; problem[i]; i++)
 190         {
 191           if (problem[i] == sug)
 192             POOL_DEBUG(SAT_DEBUG_SOLUTIONS, "=> ");
 193           solver_printproblem(solv, problem[i]);
 194         }
 195     }
 196   queue_empty(refined);
 197   if (!essentialok && sug < 0 && (solv->job.elements[-sug - 1] & SOLVER_ESSENTIAL) != 0)
 198     return;
 199   queue_init(&disabled);
 200   queue_push(refined, sug);
 201
 202   /* re-enable all problem rules with the exception of "sug"(gestion) */
 203   solver_reset(solv);
 204
 205   for (i = 0; problem[i]; i++)
 206     if (problem[i] != sug)
 207       solver_enableproblem(solv, problem[i]);
 208
 209   if (sug < 0)
 210     solver_reenablepolicyrules(solv, -(sug + 1));
 211   else if (sug >= solv->updaterules && sug < solv->updaterules_end)
 212     {
 213       /* enable feature rule */
 214       Rule *r = solv->rules + solv->featurerules + (sug - solv->updaterules);
 215       if (r->p)
 216         solver_enablerule(solv, r);
 217     }
 218
 219   enableweakrules(solv);
 220
 221   for (;;)
 222     {
 223       int njob, nfeature, nupdate;
 224       queue_empty(&solv->problems);
 225       solver_reset(solv);
 226
 227       if (!solv->problems.count)
 228         solver_run_sat(solv, 0, 0);
 229
 230       if (!solv->problems.count)
 231         {
 232           POOL_DEBUG(SAT_DEBUG_SOLUTIONS, "no more problems!\n");
 233           break;                /* great, no more problems */
 234         }
 235       disabledcnt = disabled.count;
 236       /* start with 1 to skip over proof index */
 237       njob = nfeature = nupdate = 0;
 238       for (i = 1; i < solv->problems.count - 1; i++)
 239         {
 240           /* ignore solutions in refined */
 241           v = solv->problems.elements[i];
 242           if (v == 0)
 243             break;      /* end of problem reached */
 244           for (j = 0; problem[j]; j++)
 245             if (problem[j] != sug && problem[j] == v)
 246               break;
 247           if (problem[j])
 248             continue;
 249           if (v >= solv->featurerules && v < solv->featurerules_end)
 250             nfeature++;
 251           else if (v > 0)
 252             nupdate++;
 253           else
 254             {
 255               if (!essentialok && (solv->job.elements[-v -1] & SOLVER_ESSENTIAL) != 0)
 256                 continue;       /* not that one! */
 257               njob++;
 258             }
 259           queue_push(&disabled, v);
 260         }
 261       if (disabled.count == disabledcnt)
 262         {
 263           /* no solution found, this was an invalid suggestion! */
 264           POOL_DEBUG(SAT_DEBUG_SOLUTIONS, "no solution found!\n");
 265           refined->count = 0;
 266           break;
 267         }
 268       if (!njob && nupdate && nfeature)
 269         {
 270           /* got only update rules, filter out feature rules */
 271           POOL_DEBUG(SAT_DEBUG_SOLUTIONS, "throwing away feature rules\n");
 272           for (i = j = disabledcnt; i < disabled.count; i++)
 273             {
 274               v = disabled.elements[i];
 275               if (v < solv->featurerules || v >= solv->featurerules_end)
 276                 disabled.elements[j++] = v;
 277             }
 278           disabled.count = j;
 279           nfeature = 0;
 280         }
 281       if (disabled.count == disabledcnt + 1)
 282         {
 283           /* just one suggestion, add it to refined list */
 284           v = disabled.elements[disabledcnt];
 285           if (!nfeature)
 286             queue_push(refined, v);     /* do not record feature rules */
 287           solver_disableproblem(solv, v);
 288           if (v >= solv->updaterules && v < solv->updaterules_end)
 289             {
 290               Rule *r = solv->rules + (v - solv->updaterules + solv->featurerules);
 291               if (r->p)
 292                 solver_enablerule(solv, r);     /* enable corresponding feature rule */
 293             }
 294           if (v < 0)
 295             solver_reenablepolicyrules(solv, -(v + 1));
 296         }
 297       else
 298         {
 299           /* more than one solution, disable all */
 300           /* do not push anything on refine list, as we do not know which solution to choose */
 301           /* thus, the user will get another problem if he selects this solution, where he
 302            * can choose the right one */
 303           IF_POOLDEBUG (SAT_DEBUG_SOLUTIONS)
 304             {
 305               POOL_DEBUG(SAT_DEBUG_SOLUTIONS, "more than one solution found:\n");
 306               for (i = disabledcnt; i < disabled.count; i++)
 307                 solver_printproblem(solv, disabled.elements[i]);
 308             }
 309           for (i = disabledcnt; i < disabled.count; i++)
 310             {
 311               v = disabled.elements[i];
 312               solver_disableproblem(solv, v);
 313               if (v >= solv->updaterules && v < solv->updaterules_end)
 314                 {
 315                   Rule *r = solv->rules + (v - solv->updaterules + solv->featurerules);
 316                   if (r->p)
 317                     solver_enablerule(solv, r);
 318                 }
 319             }
 320         }
 321     }
 322   /* all done, get us back into the same state as before */
 323   /* enable refined rules again */
 324   for (i = 0; i < disabled.count; i++)
 325     solver_enableproblem(solv, disabled.elements[i]);
 326   queue_free(&disabled);
 327   /* reset policy rules */
 328   for (i = 0; problem[i]; i++)
 329     solver_enableproblem(solv, problem[i]);
 330   solver_disablepolicyrules(solv);
 331   /* disable problem rules again */
 332   for (i = 0; problem[i]; i++)
 333     solver_disableproblem(solv, problem[i]);
 334   POOL_DEBUG(SAT_DEBUG_SOLUTIONS, "refine_suggestion end\n");
 335 }
 336
 337
 338 /*-------------------------------------------------------------------
 339  * sorting helper for problems
 340  *
 341  * bring update rules before job rules
 342  * make essential job rules last
 343  */
 344
 345 static int
 346 problems_sortcmp(const void *ap, const void *bp, void *dp)
 347 {
 348   Queue *job = dp;
 349   Id a = *(Id *)ap, b = *(Id *)bp;
 350   if (a < 0 && b > 0)
 351     return 1;
 352   if (a > 0 && b < 0)
 353     return -1;
 354   if (a < 0 && b < 0)
 355     {
 356       int af = job->elements[-a - 1] & SOLVER_ESSENTIAL;
 357       int bf = job->elements[-b - 1] & SOLVER_ESSENTIAL;
 358       int x = af - bf;
 359       if (x)
 360         return x;
 361     }
 362   return a - b;
 363 }
 364
 365 /*
 366  * convert a solution rule into a job modifier
 367  */
 368 static void
 369 convertsolution(Solver *solv, Id why, Queue *solutionq)
 370 {
 371   Pool *pool = solv->pool;
 372   if (why < 0)
 373     {
 374       queue_push(solutionq, 0);
 375       queue_push(solutionq, -why);
 376       return;
 377     }
 378   if (why >= solv->infarchrules && why < solv->infarchrules_end)
 379     {
 380       Id p, name;
 381       /* infarch rule, find replacement */
 382       assert(solv->rules[why].p < 0);
 383       name = pool->solvables[-solv->rules[why].p].name;
 384       while (why > solv->infarchrules && pool->solvables[-solv->rules[why - 1].p].name == name)
 385         why--;
 386       p = 0;
 387       for (; why < solv->infarchrules_end && pool->solvables[-solv->rules[why].p].name == name; why++)
 388         if (solv->decisionmap[-solv->rules[why].p] > 0)
 389           {
 390             p = -solv->rules[why].p;
 391             break;
 392           }
 393       if (!p)
 394         return;         /* false alarm */
 395       queue_push(solutionq, SOLVER_SOLUTION_INFARCH);
 396       queue_push(solutionq, p);
 397       return;
 398     }
 399   if (why >= solv->duprules && why < solv->duprules_end)
 400     {
 401       Id p, name;
 402       /* dist upgrade rule, find replacement */
 403       assert(solv->rules[why].p < 0);
 404       name = pool->solvables[-solv->rules[why].p].name;
 405       while (why > solv->duprules && pool->solvables[-solv->rules[why - 1].p].name == name)
 406         why--;
 407       p = 0;
 408       for (; why < solv->duprules_end && pool->solvables[-solv->rules[why].p].name == name; why++)
 409         if (solv->decisionmap[-solv->rules[why].p] > 0)
 410           {
 411             p = -solv->rules[why].p;
 412             break;
 413           }
 414       if (!p)
 415         return;         /* false alarm */
 416       queue_push(solutionq, SOLVER_SOLUTION_DISTUPGRADE);
 417       queue_push(solutionq, p);
 418       return;
 419     }
 420   if (why >= solv->updaterules && why < solv->updaterules_end)
 421     {
 422       /* update rule, find replacement package */
 423       Id p, *dp, rp = 0;
 424       Rule *rr;
 425
 426       assert(why >= solv->updaterules && why < solv->updaterules_end);
 427       /* check if this is a false positive, i.e. the update rule is fulfilled */
 428       rr = solv->rules + why;
 429       FOR_RULELITERALS(p, dp, rr)
 430         if (p > 0 && solv->decisionmap[p] > 0)
 431           break;
 432       if (p)
 433         return;         /* false alarm */
 434
 435       p = solv->installed->start + (why - solv->updaterules);
 436       rr = solv->rules + solv->featurerules + (why - solv->updaterules);
 437       if (!rr->p)
 438         rr = solv->rules + why;
 439       if (solv->dupmap_all && solv->rules[why].p != p && solv->decisionmap[p] > 0)
 440         {
 441           /* distupgrade case, allow to keep old package */
 442           queue_push(solutionq, SOLVER_SOLUTION_DISTUPGRADE);
 443           queue_push(solutionq, p);
 444           return;
 445         }
 446       if (solv->decisionmap[p] > 0)
 447         return;         /* false alarm, turned out we can keep the package */
 448       if (rr->w2)
 449         {
 450           int mvrp = 0;         /* multi-version replacement */
 451           FOR_RULELITERALS(rp, dp, rr)
 452             {
 453               if (rp > 0 && solv->decisionmap[rp] > 0 && pool->solvables[rp].repo != solv->installed)
 454                 {
 455                   mvrp = rp;
 456                   if (!(solv->noobsoletes.size && MAPTST(&solv->noobsoletes, rp)))
 457                     break;
 458                 }
 459             }
 460           if (!rp && mvrp)
 461             {
 462               /* found only multi-version replacements */
 463               /* have to split solution into two parts */
 464               queue_push(solutionq, p);
 465               queue_push(solutionq, mvrp);
 466             }
 467         }
 468       queue_push(solutionq, p);
 469       queue_push(solutionq, rp);
 470       return;
 471     }
 472 }
 473
 474 /*
 475  * convert problem data into a form usable for refining.
 476  * Returns the number of problems.
 477  */
 478 int
 479 solver_prepare_solutions(Solver *solv)
 480 {
 481   int i, j = 1, idx = 1;
 482
 483   if (!solv->problems.count)
 484     return 0;
 485   queue_push(&solv->solutions, 0);
 486   queue_push(&solv->solutions, -1); /* unrefined */
 487   for (i = 1; i < solv->problems.count; i++)
 488     {
 489       Id p = solv->problems.elements[i];
 490       queue_push(&solv->solutions, p);
 491       if (p)
 492         continue;
 493       solv->problems.elements[j++] = idx;
 494       if (i + 1 >= solv->problems.count)
 495         break;
 496       solv->problems.elements[j++] = solv->problems.elements[++i];  /* copy proofidx */
 497       idx = solv->solutions.count;
 498       queue_push(&solv->solutions, -1);
 499     }
 500   solv->problems.count = j;
 501   return j / 2;
 502 }
 503
 504 /*
 505  * refine the simple solution rule list provided by
 506  * the solver into multiple lists of job modifiers.
 507  */
 508 static void
 509 create_solutions(Solver *solv, int probnr, int solidx)
 510 {
 511   Pool *pool = solv->pool;
 512   Queue redoq;
 513   Queue problem, solution, problems_save;
 514   int i, j, nsol;
 515   int essentialok;
 516   int recocount;
 517   unsigned int now;
 518
 519   now = sat_timems(0);
 520   recocount = solv->recommendations.count;
 521   solv->recommendations.count = 0;      /* so that revert() doesn't mess with it later */
 522   queue_init(&redoq);
 523   /* save decisionq, decisionq_why, decisionmap */
 524   for (i = 0; i < solv->decisionq.count; i++)
 525     {
 526       Id p = solv->decisionq.elements[i];
 527       queue_push(&redoq, p);
 528       queue_push(&redoq, solv->decisionq_why.elements[i]);
 529       queue_push(&redoq, solv->decisionmap[p > 0 ? p : -p]);
 530     }
 531   /* save problems queue */
 532   problems_save = solv->problems;
 533   memset(&solv->problems, 0, sizeof(solv->problems));
 534
 535   /* extract problem from queue */
 536   queue_init(&problem);
 537   for (i = solidx + 1; i < solv->solutions.count; i++)
 538     {
 539       Id v = solv->solutions.elements[i];
 540       if (!v)
 541         break;
 542       queue_push(&problem, v);
 543     }
 544   if (problem.count > 1)
 545     sat_sort(problem.elements, problem.count, sizeof(Id), problems_sortcmp, &solv->job);
 546   queue_push(&problem, 0);      /* mark end for refine_suggestion */
 547   problem.count--;
 548 #if 0
 549   for (i = 0; i < problem.count; i++)
 550     printf("PP %d %d\n", i, problem.elements[i]);
 551 #endif
 552
 553   /* refine each solution element */
 554   nsol = 0;
 555   essentialok = 0;
 556   queue_init(&solution);
 557   for (i = 0; i < problem.count; i++)
 558     {
 559       int solstart = solv->solutions.count;
 560       refine_suggestion(solv, problem.elements, problem.elements[i], &solution, essentialok);
 561       queue_push(&solv->solutions, 0);  /* reserve room for number of elements */
 562       for (j = 0; j < solution.count; j++)
 563         convertsolution(solv, solution.elements[j], &solv->solutions);
 564       if (solv->solutions.count == solstart + 1)
 565         {
 566           solv->solutions.count--;      /* this one did not work out */
 567           if (nsol || i + 1 < problem.count)
 568             continue;                   /* got one or still hope */
 569           if (!essentialok)
 570             {
 571               /* nothing found, start over */
 572               POOL_DEBUG(SAT_DEBUG_SOLUTIONS, "nothing found, re-run with essentialok = 1\n");
 573               essentialok = 1;
 574               i = -1;
 575               continue;
 576             }
 577           /* this is bad, we found no solution */
 578           /* for now just offer a rule */
 579           POOL_DEBUG(SAT_DEBUG_SOLUTIONS, "nothing found, already did essentialok, fake it\n");
 580           queue_push(&solv->solutions, 0);
 581           for (j = 0; j < problem.count; j++)
 582             {
 583               queue_empty(&solution);
 584               queue_push(&solution, problem.elements[j]);
 585               convertsolution(solv, solution.elements[j], &solv->solutions);
 586               if (solv->solutions.count > solstart + 1)
 587                 break;
 588             }
 589           if (solv->solutions.count == solstart + 1)
 590             {
 591               solv->solutions.count--;
 592               continue;         /* sorry */
 593             }
 594         }
 595       /* patch in number of solution elements */
 596       solv->solutions.elements[solstart] = (solv->solutions.count - (solstart + 1)) / 2;
 597       queue_push(&solv->solutions, 0);  /* add end marker */
 598       queue_push(&solv->solutions, 0);  /* add end marker */
 599       solv->solutions.elements[solidx + 1 + nsol++] = solstart;
 600     }
 601   solv->solutions.elements[solidx + 1 + nsol] = 0;      /* end marker */
 602   solv->solutions.elements[solidx] = nsol;
 603   queue_free(&problem);
 604   queue_free(&solution);
 605
 606   /* restore decisions */
 607   memset(solv->decisionmap, 0, pool->nsolvables * sizeof(Id));
 608   queue_empty(&solv->decisionq);
 609   queue_empty(&solv->decisionq_why);
 610   for (i = 0; i < redoq.count; i += 3)
 611     {
 612       Id p = redoq.elements[i];
 613       queue_push(&solv->decisionq, p);
 614       queue_push(&solv->decisionq_why, redoq.elements[i + 1]);
 615       solv->decisionmap[p > 0 ? p : -p] = redoq.elements[i + 2];
 616     }
 617   solv->recommendations.count = recocount;
 618   queue_free(&redoq);
 619   /* restore problems */
 620   queue_free(&solv->problems);
 621   solv->problems = problems_save;
 622   POOL_DEBUG(SAT_DEBUG_STATS, "create_solutions for problem #%d took %d ms\n", probnr, sat_timems(now));
 623 }
 624
 625
 626 /**************************************************************************/
 627
 628 unsigned int
 629 solver_problem_count(Solver *solv)
 630 {
 631   return solv->problems.count / 2;
 632 }
 633
 634 Id
 635 solver_next_problem(Solver *solv, Id problem)
 636 {
 637   if (!problem)
 638     return solv->problems.count ? 1 : 0;
 639   return (problem + 1) * 2 - 1 < solv->problems.count ? problem + 1 : 0;
 640 }
 641
 642 unsigned int
 643 solver_solution_count(Solver *solv, Id problem)
 644 {
 645   Id solidx = solv->problems.elements[problem * 2 - 1];
 646   if (solv->solutions.elements[solidx] < 0)
 647     create_solutions(solv, problem, solidx);
 648   return solv->solutions.elements[solidx];
 649 }
 650
 651 Id
 652 solver_next_solution(Solver *solv, Id problem, Id solution)
 653 {
 654   Id solidx = solv->problems.elements[problem * 2 - 1];
 655   if (solv->solutions.elements[solidx] < 0)
 656     create_solutions(solv, problem, solidx);
 657   return solv->solutions.elements[solidx + solution + 1] ? solution + 1 : 0;
 658 }
 659
 660 unsigned int
 661 solver_solutionelement_count(Solver *solv, Id problem, Id solution)
 662 {
 663   Id solidx = solv->problems.elements[problem * 2 - 1];
 664   solidx = solv->solutions.elements[solidx + solution];
 665   return solv->solutions.elements[solidx];
 666 }
 667
 668
 669 /*
 670  *  return the next item of the proposed solution
 671  *  here are the possibilities for p / rp and what
 672  *  the solver expects the application to do:
 673  *    p                             rp
 674  *  -------------------------------------------------------
 675  *    SOLVER_SOLUTION_INFARCH       pkgid
 676  *    -> add (SOLVER_INSTALL|SOLVER_SOLVABLE, rp) to the job
 677  *    SOLVER_SOLUTION_DISTUPGRADE   pkgid
 678  *    -> add (SOLVER_INSTALL|SOLVER_SOLVABLE, rp) to the job
 679  *    SOLVER_SOLUTION_JOB           jobidx
 680  *    -> remove job (jobidx - 1, jobidx) from job queue
 681  *    pkgid (> 0)                   0
 682  *    -> add (SOLVER_ERASE|SOLVER_SOLVABLE, p) to the job
 683  *    pkgid (> 0)                   pkgid (> 0)
 684  *    -> add (SOLVER_INSTALL|SOLVER_SOLVABLE, rp) to the job
 685  *       (this will replace package p)
 686  *
 687  * Thus, the solver will either ask the application to remove
 688  * a specific job from the job queue, or ask to add an install/erase
 689  * job to it.
 690  *
 691  */
 692
 693 Id
 694 solver_next_solutionelement(Solver *solv, Id problem, Id solution, Id element, Id *p, Id *rp)
 695 {
 696   Id solidx = solv->problems.elements[problem * 2 - 1];
 697   solidx = solv->solutions.elements[solidx + solution];
 698   if (!solidx)
 699     return 0;
 700   solidx += 1 + element * 2;
 701   if (!solv->solutions.elements[solidx] && !solv->solutions.elements[solidx + 1])
 702     return 0;
 703   *p = solv->solutions.elements[solidx];
 704   *rp = solv->solutions.elements[solidx + 1];
 705   return element + 1;
 706 }
 707
 708 void
 709 solver_take_solutionelement(Solver *solv, Id p, Id rp, Queue *job)
 710 {
 711   int i;
 712
 713   if (p == SOLVER_SOLUTION_JOB)
 714     {
 715       job->elements[rp - 1] = SOLVER_NOOP;
 716       job->elements[rp] = 0;
 717       return;
 718     }
 719   if (rp <= 0 && p <= 0)
 720     return;     /* just in case */
 721   if (rp > 0)
 722     p = SOLVER_INSTALL|SOLVER_SOLVABLE;
 723   else
 724     {
 725       rp = p;
 726       p = SOLVER_ERASE|SOLVER_SOLVABLE;
 727     }
 728   for (i = 0; i < job->count; i += 2)
 729     if (job->elements[i] == p && job->elements[i + 1] == rp)
 730       return;
 731   queue_push2(job, p, rp);
 732 }
 733
 734 void
 735 solver_take_solution(Solver *solv, Id problem, Id solution, Queue *job)
 736 {
 737   Id p, rp, element = 0;
 738   while ((element = solver_next_solutionelement(solv, problem, solution, element, &p, &rp)) != 0)
 739     solver_take_solutionelement(solv, p, rp, job);
 740 }
 741
 742
 743 /*-------------------------------------------------------------------
 744  *
 745  * find problem rule
 746  */
 747
 748 static void
 749 findproblemrule_internal(Solver *solv, Id idx, Id *reqrp, Id *conrp, Id *sysrp, Id *jobrp)
 750 {
 751   Id rid, d;
 752   Id lreqr, lconr, lsysr, ljobr;
 753   Rule *r;
 754   Id jobassert = 0;
 755   int i, reqset = 0;    /* 0: unset, 1: installed, 2: jobassert, 3: assert */
 756
 757   /* find us a jobassert rule */
 758   for (i = idx; (rid = solv->learnt_pool.elements[i]) != 0; i++)
 759     {
 760       if (rid < solv->jobrules || rid >= solv->jobrules_end)
 761         continue;
 762       r = solv->rules + rid;
 763       d = r->d < 0 ? -r->d - 1 : r->d;
 764       if (!d && r->w2 == 0 && r->p > 0)
 765         {
 766           jobassert = r->p;
 767           break;
 768         }
 769     }
 770
 771   /* the problem rules are somewhat ordered from "near to the problem" to
 772    * "near to the job" */
 773   lreqr = lconr = lsysr = ljobr = 0;
 774   while ((rid = solv->learnt_pool.elements[idx++]) != 0)
 775     {
 776       assert(rid > 0);
 777       if (rid >= solv->learntrules)
 778         findproblemrule_internal(solv, solv->learnt_why.elements[rid - solv->learntrules], &lreqr, &lconr, &lsysr, &ljobr);
 779       else if ((rid >= solv->jobrules && rid < solv->jobrules_end) || (rid >= solv->infarchrules && rid < solv->infarchrules_end) || (rid >= solv->duprules && rid < solv->duprules_end))
 780         {
 781           if (!*jobrp)
 782             *jobrp = rid;
 783         }
 784       else if (rid >= solv->updaterules && rid < solv->updaterules_end)
 785         {
 786           if (!*sysrp)
 787             *sysrp = rid;
 788         }
 789       else
 790         {
 791           assert(rid < solv->rpmrules_end);
 792           r = solv->rules + rid;
 793           d = r->d < 0 ? -r->d - 1 : r->d;
 794           if (!d && r->w2 < 0)
 795             {
 796               if (!*conrp)
 797                 *conrp = rid;
 798             }
 799           else
 800             {
 801               if (!d && r->w2 == 0 && reqset < 3)
 802                 {
 803                   if (*reqrp > 0 && r->p < -1)
 804                     {
 805                       Id op = -solv->rules[*reqrp].p;
 806                       if (op > 1 && solv->pool->solvables[op].arch != solv->pool->solvables[-r->p].arch)
 807                         continue;       /* different arch, skip */
 808                     }
 809                   /* prefer assertions */
 810                   *reqrp = rid;
 811                   reqset = 3;
 812                 }
 813               else if (jobassert && r->p == -jobassert)
 814                 {
 815                   /* prefer rules of job assertions */
 816                   *reqrp = rid;
 817                   reqset = 2;
 818                 }
 819               else if (solv->installed && r->p < 0 && solv->pool->solvables[-r->p].repo == solv->installed && reqset <= 1)
 820                 {
 821                   /* prefer rules of job installed package so that the user doesn't get confused by strange packages */
 822                   *reqrp = rid;
 823                   reqset = 1;
 824                 }
 825               else if (!*reqrp)
 826                 *reqrp = rid;
 827             }
 828         }
 829     }
 830   if (!*reqrp && lreqr)
 831     *reqrp = lreqr;
 832   if (!*conrp && lconr)
 833     *conrp = lconr;
 834   if (!*jobrp && ljobr)
 835     *jobrp = ljobr;
 836   if (!*sysrp && lsysr)
 837     *sysrp = lsysr;
 838 }
 839
 840 /*
 841  * find problem rule
 842  *
 843  * search for a rule that describes the problem to the
 844  * user. Actually a pretty hopeless task that may leave the user
 845  * puzzled. To get all of the needed information use
 846  * solver_findallproblemrules() instead.
 847  */
 848
 849 Id
 850 solver_findproblemrule(Solver *solv, Id problem)
 851 {
 852   Id reqr, conr, sysr, jobr;
 853   Id idx = solv->problems.elements[2 * problem - 2];
 854   reqr = conr = sysr = jobr = 0;
 855   findproblemrule_internal(solv, idx, &reqr, &conr, &sysr, &jobr);
 856   if (reqr)
 857     return reqr;        /* some requires */
 858   if (conr)
 859     return conr;        /* some conflict */
 860   if (sysr)
 861     return sysr;        /* an update rule */
 862   if (jobr)
 863     return jobr;        /* a user request */
 864   assert(0);
 865 }
 866
 867 /*-------------------------------------------------------------------*/
 868
 869 static void
 870 findallproblemrules_internal(Solver *solv, Id idx, Queue *rules)
 871 {
 872   Id rid;
 873   while ((rid = solv->learnt_pool.elements[idx++]) != 0)
 874     {
 875       if (rid >= solv->learntrules)
 876         {
 877           findallproblemrules_internal(solv, solv->learnt_why.elements[rid - solv->learntrules], rules);
 878           continue;
 879         }
 880       queue_pushunique(rules, rid);
 881     }
 882 }
 883
 884 /*
 885  * find all problem rule
 886  *
 887  * return all rules that lead to the problem. This gives the user
 888  * all of the information to understand the problem, but the result
 889  * can be a large number of rules.
 890  */
 891
 892 void
 893 solver_findallproblemrules(Solver *solv, Id problem, Queue *rules)
 894 {
 895   queue_empty(rules);
 896   findallproblemrules_internal(solv, solv->problems.elements[2 * problem - 2], rules);
 897 }
 898
 899 /* EOF */