src/solverdebug.c

   1 /*
   2  * Copyright (c) 2008, Novell Inc.
   3  *
   4  * This program is licensed under the BSD license, read LICENSE.BSD
   5  * for further information
   6  */
   7
   8 /*
   9  * solverdebug.c
  10  *
  11  * debug functions for the SAT solver
  12  */
  13
  14 #include <stdio.h>
  15 #include <stdlib.h>
  16 #include <unistd.h>
  17 #include <string.h>
  18 #include <assert.h>
  19
  20 #include "solver.h"
  21 #include "solver_private.h"
  22 #include "solverdebug.h"
  23 #include "bitmap.h"
  24 #include "pool.h"
  25 #include "poolarch.h"
  26 #include "util.h"
  27 #include "evr.h"
  28 #include "policy.h"
  29
  30
  31 void
  32 solver_printruleelement(Solver *solv, int type, Rule *r, Id v)
  33 {
  34   Pool *pool = solv->pool;
  35   Solvable *s;
  36   if (v < 0)
  37     {
  38       s = pool->solvables + -v;
  39       POOL_DEBUG(type, "    !%s [%d]", pool_solvable2str(pool, s), -v);
  40     }
  41   else
  42     {
  43       s = pool->solvables + v;
  44       POOL_DEBUG(type, "    %s [%d]", pool_solvable2str(pool, s), v);
  45     }
  46   if (pool->installed && s->repo == pool->installed)
  47     POOL_DEBUG(type, "I");
  48   if (r)
  49     {
  50       if (r->w1 == v)
  51         POOL_DEBUG(type, " (w1)");
  52       if (r->w2 == v)
  53         POOL_DEBUG(type, " (w2)");
  54     }
  55   if (solv->decisionmap[s - pool->solvables] > 0)
  56     POOL_DEBUG(type, " Install.level%d", solv->decisionmap[s - pool->solvables]);
  57   if (solv->decisionmap[s - pool->solvables] < 0)
  58     POOL_DEBUG(type, " Conflict.level%d", -solv->decisionmap[s - pool->solvables]);
  59   POOL_DEBUG(type, "\n");
  60 }
  61
  62
  63 /*
  64  * print rule
  65  */
  66
  67 void
  68 solver_printrule(Solver *solv, int type, Rule *r)
  69 {
  70   Pool *pool = solv->pool;
  71   int i;
  72   Id d, v;
  73
  74   if (r >= solv->rules && r < solv->rules + solv->nrules)   /* r is a solver rule */
  75     POOL_DEBUG(type, "Rule #%d:", (int)(r - solv->rules));
  76   else
  77     POOL_DEBUG(type, "Rule:");                 /* r is any rule */
  78   if (r->d < 0)
  79     POOL_DEBUG(type, " (disabled)");
  80   POOL_DEBUG(type, "\n");
  81   d = r->d < 0 ? -r->d - 1 : r->d;
  82   for (i = 0; ; i++)
  83     {
  84       if (i == 0)
  85           /* print direct literal */
  86         v = r->p;
  87       else if (!d)
  88         {
  89           if (i == 2)
  90             break;
  91           /* binary rule --> print w2 as second literal */
  92           v = r->w2;
  93         }
  94       else
  95           /* every other which is in d */
  96         v = solv->pool->whatprovidesdata[d + i - 1];
  97       if (v == ID_NULL)
  98         break;
  99       solver_printruleelement(solv, type, r, v);
 100     }
 101   POOL_DEBUG(type, "    next rules: %d %d\n", r->n1, r->n2);
 102 }
 103
 104 void
 105 solver_printruleclass(Solver *solv, int type, Rule *r)
 106 {
 107   Pool *pool = solv->pool;
 108   Id p = r - solv->rules;
 109   assert(p >= 0);
 110   if (p < solv->learntrules)
 111     if (solv->weakrulemap.size && MAPTST(&solv->weakrulemap, p))
 112       POOL_DEBUG(type, "WEAK ");
 113   if (solv->learntrules && p >= solv->learntrules)
 114     POOL_DEBUG(type, "LEARNT ");
 115   else if (p >= solv->bestrules && p < solv->bestrules_end)
 116     POOL_DEBUG(type, "BEST ");
 117   else if (p >= solv->choicerules && p < solv->choicerules_end)
 118     POOL_DEBUG(type, "CHOICE ");
 119   else if (p >= solv->infarchrules && p < solv->infarchrules_end)
 120     POOL_DEBUG(type, "INFARCH ");
 121   else if (p >= solv->duprules && p < solv->duprules_end)
 122     POOL_DEBUG(type, "DUP ");
 123   else if (p >= solv->jobrules && p < solv->jobrules_end)
 124     POOL_DEBUG(type, "JOB ");
 125   else if (p >= solv->updaterules && p < solv->updaterules_end)
 126     POOL_DEBUG(type, "UPDATE ");
 127   else if (p >= solv->featurerules && p < solv->featurerules_end)
 128     POOL_DEBUG(type, "FEATURE ");
 129   else if (p >= solv->yumobsrules && p < solv->yumobsrules_end)
 130     POOL_DEBUG(type, "YUMOBS ");
 131   else if (p >= solv->recommendsrules && p < solv->recommendsrules_end)
 132     POOL_DEBUG(type, "RECOMMENDS ");
 133   solver_printrule(solv, type, r);
 134 }
 135
 136 void
 137 solver_printproblem(Solver *solv, Id v)
 138 {
 139   Pool *pool = solv->pool;
 140   int i;
 141   Rule *r;
 142   Id *jp;
 143
 144   if (v > 0)
 145     solver_printruleclass(solv, SOLV_DEBUG_SOLUTIONS, solv->rules + v);
 146   else
 147     {
 148       v = -(v + 1);
 149       POOL_DEBUG(SOLV_DEBUG_SOLUTIONS, "JOB %d\n", v);
 150       jp = solv->ruletojob.elements;
 151       for (i = solv->jobrules, r = solv->rules + i; i < solv->jobrules_end; i++, r++, jp++)
 152         if (*jp == v)
 153           {
 154             POOL_DEBUG(SOLV_DEBUG_SOLUTIONS, "- ");
 155             solver_printrule(solv, SOLV_DEBUG_SOLUTIONS, r);
 156           }
 157       POOL_DEBUG(SOLV_DEBUG_SOLUTIONS, "ENDJOB\n");
 158     }
 159 }
 160
 161 void
 162 solver_printwatches(Solver *solv, int type)
 163 {
 164   Pool *pool = solv->pool;
 165   int counter;
 166
 167   POOL_DEBUG(type, "Watches: \n");
 168   for (counter = -(pool->nsolvables - 1); counter < pool->nsolvables; counter++)
 169     POOL_DEBUG(type, "    solvable [%d] -- rule [%d]\n", counter, solv->watches[counter + pool->nsolvables]);
 170 }
 171
 172 void
 173 solver_printdecisionq(Solver *solv, int type)
 174 {
 175   Pool *pool = solv->pool;
 176   int i;
 177   Id p, why;
 178
 179   POOL_DEBUG(type, "Decisions:\n");
 180   for (i = 0; i < solv->decisionq.count; i++)
 181     {
 182       p = solv->decisionq.elements[i];
 183       if (p > 0)
 184         POOL_DEBUG(type, "%d %d install  %s, ", i, solv->decisionmap[p], pool_solvid2str(pool, p));
 185       else
 186         POOL_DEBUG(type, "%d %d conflict %s, ", i, -solv->decisionmap[-p], pool_solvid2str(pool, -p));
 187       why = solv->decisionq_why.elements[i];
 188       if (why > 0)
 189         {
 190           POOL_DEBUG(type, "forced by ");
 191           solver_printruleclass(solv, type, solv->rules + why);
 192         }
 193       else if (why < 0)
 194         {
 195           POOL_DEBUG(type, "chosen from ");
 196           solver_printruleclass(solv, type, solv->rules - why);
 197         }
 198       else
 199         POOL_DEBUG(type, "picked for some unknown reason.\n");
 200     }
 201 }
 202
 203 /*
 204  * printdecisions
 205  */
 206
 207 void
 208 solver_printdecisions(Solver *solv)
 209 {
 210   Pool *pool = solv->pool;
 211   Repo *installed = solv->installed;
 212   Transaction *trans = solver_create_transaction(solv);
 213   Id p, type;
 214   int i, j;
 215   Solvable *s;
 216   Queue iq;
 217   Queue recommendations;
 218   Queue suggestions;
 219   Queue orphaned;
 220
 221   POOL_DEBUG(SOLV_DEBUG_RESULT, "\n");
 222   POOL_DEBUG(SOLV_DEBUG_RESULT, "transaction:\n");
 223
 224   queue_init(&iq);
 225   for (i = 0; i < trans->steps.count; i++)
 226     {
 227       p = trans->steps.elements[i];
 228       s = pool->solvables + p;
 229       type = transaction_type(trans, p, SOLVER_TRANSACTION_SHOW_ACTIVE|SOLVER_TRANSACTION_SHOW_ALL|SOLVER_TRANSACTION_SHOW_OBSOLETES|SOLVER_TRANSACTION_SHOW_MULTIINSTALL);
 230       switch(type)
 231         {
 232         case SOLVER_TRANSACTION_MULTIINSTALL:
 233           POOL_DEBUG(SOLV_DEBUG_RESULT, "  multi install %s", pool_solvable2str(pool, s));
 234           break;
 235         case SOLVER_TRANSACTION_MULTIREINSTALL:
 236           POOL_DEBUG(SOLV_DEBUG_RESULT, "  multi reinstall %s", pool_solvable2str(pool, s));
 237           break;
 238         case SOLVER_TRANSACTION_INSTALL:
 239           POOL_DEBUG(SOLV_DEBUG_RESULT, "  install   %s", pool_solvable2str(pool, s));
 240           break;
 241         case SOLVER_TRANSACTION_REINSTALL:
 242           POOL_DEBUG(SOLV_DEBUG_RESULT, "  reinstall %s", pool_solvable2str(pool, s));
 243           break;
 244         case SOLVER_TRANSACTION_DOWNGRADE:
 245           POOL_DEBUG(SOLV_DEBUG_RESULT, "  downgrade %s", pool_solvable2str(pool, s));
 246           break;
 247         case SOLVER_TRANSACTION_CHANGE:
 248           POOL_DEBUG(SOLV_DEBUG_RESULT, "  change    %s", pool_solvable2str(pool, s));
 249           break;
 250         case SOLVER_TRANSACTION_UPGRADE:
 251         case SOLVER_TRANSACTION_OBSOLETES:
 252           POOL_DEBUG(SOLV_DEBUG_RESULT, "  upgrade   %s", pool_solvable2str(pool, s));
 253           break;
 254         case SOLVER_TRANSACTION_ERASE:
 255           POOL_DEBUG(SOLV_DEBUG_RESULT, "  erase     %s", pool_solvable2str(pool, s));
 256           break;
 257         default:
 258           break;
 259         }
 260       switch(type)
 261         {
 262         case SOLVER_TRANSACTION_INSTALL:
 263         case SOLVER_TRANSACTION_ERASE:
 264         case SOLVER_TRANSACTION_MULTIINSTALL:
 265         case SOLVER_TRANSACTION_MULTIREINSTALL:
 266           POOL_DEBUG(SOLV_DEBUG_RESULT, "\n");
 267           break;
 268         case SOLVER_TRANSACTION_REINSTALL:
 269         case SOLVER_TRANSACTION_DOWNGRADE:
 270         case SOLVER_TRANSACTION_CHANGE:
 271         case SOLVER_TRANSACTION_UPGRADE:
 272         case SOLVER_TRANSACTION_OBSOLETES:
 273           transaction_all_obs_pkgs(trans, p, &iq);
 274           if (iq.count)
 275             {
 276               POOL_DEBUG(SOLV_DEBUG_RESULT, "  (obsoletes");
 277               for (j = 0; j < iq.count; j++)
 278                 POOL_DEBUG(SOLV_DEBUG_RESULT, " %s", pool_solvid2str(pool, iq.elements[j]));
 279               POOL_DEBUG(SOLV_DEBUG_RESULT, ")");
 280             }
 281           POOL_DEBUG(SOLV_DEBUG_RESULT, "\n");
 282           break;
 283         default:
 284           break;
 285         }
 286     }
 287   queue_free(&iq);
 288
 289   POOL_DEBUG(SOLV_DEBUG_RESULT, "\n");
 290
 291   queue_init(&recommendations);
 292   queue_init(&suggestions);
 293   queue_init(&orphaned);
 294   solver_get_recommendations(solv, &recommendations, &suggestions, 0);
 295   solver_get_orphaned(solv, &orphaned);
 296   if (recommendations.count)
 297     {
 298       POOL_DEBUG(SOLV_DEBUG_RESULT, "recommended packages:\n");
 299       for (i = 0; i < recommendations.count; i++)
 300         {
 301           s = pool->solvables + recommendations.elements[i];
 302           if (solv->decisionmap[recommendations.elements[i]] > 0)
 303             {
 304               if (installed && s->repo == installed)
 305                 POOL_DEBUG(SOLV_DEBUG_RESULT, "  %s (installed)\n", pool_solvable2str(pool, s));
 306               else
 307                 POOL_DEBUG(SOLV_DEBUG_RESULT, "  %s (selected)\n", pool_solvable2str(pool, s));
 308             }
 309           else
 310             POOL_DEBUG(SOLV_DEBUG_RESULT, "  %s\n", pool_solvable2str(pool, s));
 311         }
 312       POOL_DEBUG(SOLV_DEBUG_RESULT, "\n");
 313     }
 314
 315   if (suggestions.count)
 316     {
 317       POOL_DEBUG(SOLV_DEBUG_RESULT, "suggested packages:\n");
 318       for (i = 0; i < suggestions.count; i++)
 319         {
 320           s = pool->solvables + suggestions.elements[i];
 321           if (solv->decisionmap[suggestions.elements[i]] > 0)
 322             {
 323               if (installed && s->repo == installed)
 324                 POOL_DEBUG(SOLV_DEBUG_RESULT, "  %s (installed)\n", pool_solvable2str(pool, s));
 325               else
 326                 POOL_DEBUG(SOLV_DEBUG_RESULT, "  %s (selected)\n", pool_solvable2str(pool, s));
 327             }
 328           else
 329             POOL_DEBUG(SOLV_DEBUG_RESULT, "  %s\n", pool_solvable2str(pool, s));
 330         }
 331       POOL_DEBUG(SOLV_DEBUG_RESULT, "\n");
 332     }
 333   if (orphaned.count)
 334     {
 335       POOL_DEBUG(SOLV_DEBUG_RESULT, "orphaned packages:\n");
 336       for (i = 0; i < orphaned.count; i++)
 337         {
 338           s = pool->solvables + orphaned.elements[i];
 339           if (solv->decisionmap[solv->orphaned.elements[i]] > 0)
 340             POOL_DEBUG(SOLV_DEBUG_RESULT, "  %s (kept)\n", pool_solvable2str(pool, s));
 341           else
 342             POOL_DEBUG(SOLV_DEBUG_RESULT, "  %s (erased)\n", pool_solvable2str(pool, s));
 343         }
 344       POOL_DEBUG(SOLV_DEBUG_RESULT, "\n");
 345     }
 346   queue_free(&recommendations);
 347   queue_free(&suggestions);
 348   queue_free(&orphaned);
 349   transaction_free(trans);
 350 }
 351
 352 static inline
 353 const char *id2strnone(Pool *pool, Id id)
 354 {
 355   return !id || id == 1 ? "(none)" : pool_id2str(pool, id);
 356 }
 357
 358 void
 359 transaction_print(Transaction *trans)
 360 {
 361   Pool *pool = trans->pool;
 362   Queue classes, pkgs;
 363   int i, j, mode, l, linel;
 364   char line[76];
 365   const char *n;
 366
 367   queue_init(&classes);
 368   queue_init(&pkgs);
 369   mode = SOLVER_TRANSACTION_SHOW_OBSOLETES | SOLVER_TRANSACTION_OBSOLETE_IS_UPGRADE;
 370   transaction_classify(trans, mode, &classes);
 371   for (i = 0; i < classes.count; i += 4)
 372     {
 373       Id class = classes.elements[i];
 374       Id cnt = classes.elements[i + 1];
 375       switch(class)
 376         {
 377         case SOLVER_TRANSACTION_ERASE:
 378           POOL_DEBUG(SOLV_DEBUG_RESULT, "%d erased packages:\n", cnt);
 379           break;
 380         case SOLVER_TRANSACTION_INSTALL:
 381           POOL_DEBUG(SOLV_DEBUG_RESULT, "%d installed packages:\n", cnt);
 382           break;
 383         case SOLVER_TRANSACTION_REINSTALLED:
 384           POOL_DEBUG(SOLV_DEBUG_RESULT, "%d reinstalled packages:\n", cnt);
 385           break;
 386         case SOLVER_TRANSACTION_DOWNGRADED:
 387           POOL_DEBUG(SOLV_DEBUG_RESULT, "%d downgraded packages:\n", cnt);
 388           break;
 389         case SOLVER_TRANSACTION_CHANGED:
 390           POOL_DEBUG(SOLV_DEBUG_RESULT, "%d changed packages:\n", cnt);
 391           break;
 392         case SOLVER_TRANSACTION_UPGRADED:
 393           POOL_DEBUG(SOLV_DEBUG_RESULT, "%d upgraded packages:\n", cnt);
 394           break;
 395         case SOLVER_TRANSACTION_VENDORCHANGE:
 396           POOL_DEBUG(SOLV_DEBUG_RESULT, "%d vendor changes from '%s' to '%s':\n", cnt, id2strnone(pool, classes.elements[i + 2]), id2strnone(pool, classes.elements[i + 3]));
 397           break;
 398         case SOLVER_TRANSACTION_ARCHCHANGE:
 399           POOL_DEBUG(SOLV_DEBUG_RESULT, "%d arch changes from %s to %s:\n", cnt, pool_id2str(pool, classes.elements[i + 2]), pool_id2str(pool, classes.elements[i + 3]));
 400           break;
 401         default:
 402           class = SOLVER_TRANSACTION_IGNORE;
 403           break;
 404         }
 405       if (class == SOLVER_TRANSACTION_IGNORE)
 406         continue;
 407       transaction_classify_pkgs(trans, mode, class, classes.elements[i + 2], classes.elements[i + 3], &pkgs);
 408       *line = 0;
 409       linel = 0;
 410       for (j = 0; j < pkgs.count; j++)
 411         {
 412           Id p = pkgs.elements[j];
 413           Solvable *s = pool->solvables + p;
 414           Solvable *s2;
 415
 416           switch(class)
 417             {
 418             case SOLVER_TRANSACTION_DOWNGRADED:
 419             case SOLVER_TRANSACTION_UPGRADED:
 420               s2 = pool->solvables + transaction_obs_pkg(trans, p);
 421               POOL_DEBUG(SOLV_DEBUG_RESULT, "  - %s -> %s\n", pool_solvable2str(pool, s), pool_solvable2str(pool, s2));
 422               break;
 423             case SOLVER_TRANSACTION_VENDORCHANGE:
 424             case SOLVER_TRANSACTION_ARCHCHANGE:
 425               n = pool_id2str(pool, s->name);
 426               l = strlen(n);
 427               if (l + linel > sizeof(line) - 3)
 428                 {
 429                   if (*line)
 430                     POOL_DEBUG(SOLV_DEBUG_RESULT, "    %s\n", line);
 431                   *line = 0;
 432                   linel = 0;
 433                 }
 434               if (l + linel > sizeof(line) - 3)
 435                 POOL_DEBUG(SOLV_DEBUG_RESULT, "    %s\n", n);
 436               else
 437                 {
 438                   if (*line)
 439                     {
 440                       strcpy(line + linel, ", ");
 441                       linel += 2;
 442                     }
 443                   strcpy(line + linel, n);
 444                   linel += l;
 445                 }
 446               break;
 447             default:
 448               POOL_DEBUG(SOLV_DEBUG_RESULT, "  - %s\n", pool_solvable2str(pool, s));
 449               break;
 450             }
 451         }
 452       if (*line)
 453         POOL_DEBUG(SOLV_DEBUG_RESULT, "    %s\n", line);
 454       POOL_DEBUG(SOLV_DEBUG_RESULT, "\n");
 455     }
 456   queue_free(&classes);
 457   queue_free(&pkgs);
 458 }
 459
 460 void
 461 solver_printproblemruleinfo(Solver *solv, Id probr)
 462 {
 463   Pool *pool = solv->pool;
 464   Id dep, source, target;
 465   SolverRuleinfo type = solver_ruleinfo(solv, probr, &source, &target, &dep);
 466
 467   POOL_DEBUG(SOLV_DEBUG_RESULT, "%s\n", solver_problemruleinfo2str(solv, type, source, target, dep));
 468 }
 469
 470 void
 471 solver_printprobleminfo(Solver *solv, Id problem)
 472 {
 473   solver_printproblemruleinfo(solv, solver_findproblemrule(solv, problem));
 474 }
 475
 476 void
 477 solver_printcompleteprobleminfo(Solver *solv, Id problem)
 478 {
 479   Queue q;
 480   Id probr;
 481   int i, nobad = 0;
 482
 483   queue_init(&q);
 484   solver_findallproblemrules(solv, problem, &q);
 485   for (i = 0; i < q.count; i++)
 486     {
 487       probr = q.elements[i];
 488       if (!(probr >= solv->updaterules && probr < solv->updaterules_end) && !(probr >= solv->jobrules && probr < solv->jobrules_end))
 489         {
 490           nobad = 1;
 491           break;
 492         }
 493     }
 494   for (i = 0; i < q.count; i++)
 495     {
 496       probr = q.elements[i];
 497       if (nobad && ((probr >= solv->updaterules && probr < solv->updaterules_end) || (probr >= solv->jobrules && probr < solv->jobrules_end)))
 498         continue;
 499       solver_printproblemruleinfo(solv, probr);
 500     }
 501   queue_free(&q);
 502 }
 503
 504 static int illegals[] = {
 505   POLICY_ILLEGAL_DOWNGRADE,
 506   POLICY_ILLEGAL_NAMECHANGE,
 507   POLICY_ILLEGAL_ARCHCHANGE,
 508   POLICY_ILLEGAL_VENDORCHANGE,
 509   0
 510 };
 511
 512 void
 513 solver_printsolution(Solver *solv, Id problem, Id solution)
 514 {
 515   Pool *pool = solv->pool;
 516   Id p, rp, element;
 517
 518   element = 0;
 519   while ((element = solver_next_solutionelement(solv, problem, solution, element, &p, &rp)) != 0)
 520     {
 521       if (p > 0 && rp > 0)
 522         {
 523           /* for replacements we want to know why it was illegal */
 524           Solvable *s = pool->solvables + p, *rs = pool->solvables + rp;
 525           int illegal = policy_is_illegal(solv, s, rs, 0);
 526           if (illegal)
 527             {
 528               int i;
 529               for (i = 0; illegals[i]; i++)
 530                 if ((illegal & illegals[i]) != 0)
 531                   {
 532                     POOL_DEBUG(SOLV_DEBUG_RESULT, "  - allow %s\n", policy_illegal2str(solv, illegals[i], s, rs));
 533                     illegal ^= illegals[i];
 534                   }
 535               if (!illegal)
 536                 continue;
 537             }
 538         }
 539       POOL_DEBUG(SOLV_DEBUG_RESULT, "  - %s\n", solver_solutionelement2str(solv, p, rp));
 540     }
 541 }
 542
 543 void
 544 solver_printallsolutions(Solver *solv)
 545 {
 546   Pool *pool = solv->pool;
 547   int pcnt;
 548   Id problem, solution;
 549
 550   POOL_DEBUG(SOLV_DEBUG_RESULT, "Encountered problems! Here are the solutions:\n\n");
 551   pcnt = 0;
 552   problem = 0;
 553   while ((problem = solver_next_problem(solv, problem)) != 0)
 554     {
 555       pcnt++;
 556       POOL_DEBUG(SOLV_DEBUG_RESULT, "Problem %d:\n", pcnt);
 557       POOL_DEBUG(SOLV_DEBUG_RESULT, "====================================\n");
 558 #if 1
 559       solver_printprobleminfo(solv, problem);
 560 #else
 561       solver_printcompleteprobleminfo(solv, problem);
 562 #endif
 563       POOL_DEBUG(SOLV_DEBUG_RESULT, "\n");
 564       solution = 0;
 565       while ((solution = solver_next_solution(solv, problem, solution)) != 0)
 566         {
 567           solver_printsolution(solv, problem, solution);
 568           POOL_DEBUG(SOLV_DEBUG_RESULT, "\n");
 569         }
 570     }
 571 }
 572