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->blackrules && p < solv->blackrules_end)
 132     POOL_DEBUG(type, "BLACK ");
 133   else if (p >= solv->strictrepopriorules && p < solv->strictrepopriorules_end)
 134     POOL_DEBUG(type, "REPOPRIO ");
 135   else if (p >= solv->recommendsrules && p < solv->recommendsrules_end)
 136     POOL_DEBUG(type, "RECOMMENDS ");
 137   solver_printrule(solv, type, r);
 138 }
 139
 140 void
 141 solver_printproblem(Solver *solv, Id v)
 142 {
 143   Pool *pool = solv->pool;
 144   int i;
 145   Rule *r;
 146   Id *jp;
 147
 148   if (v > 0)
 149     solver_printruleclass(solv, SOLV_DEBUG_SOLUTIONS, solv->rules + v);
 150   else
 151     {
 152       v = -(v + 1);
 153       POOL_DEBUG(SOLV_DEBUG_SOLUTIONS, "JOB %d\n", v);
 154       jp = solv->ruletojob.elements;
 155       for (i = solv->jobrules, r = solv->rules + i; i < solv->jobrules_end; i++, r++, jp++)
 156         if (*jp == v)
 157           {
 158             POOL_DEBUG(SOLV_DEBUG_SOLUTIONS, "- ");
 159             solver_printrule(solv, SOLV_DEBUG_SOLUTIONS, r);
 160           }
 161       POOL_DEBUG(SOLV_DEBUG_SOLUTIONS, "ENDJOB\n");
 162     }
 163 }
 164
 165 void
 166 solver_printwatches(Solver *solv, int type)
 167 {
 168   Pool *pool = solv->pool;
 169   int counter;
 170
 171   POOL_DEBUG(type, "Watches: \n");
 172   for (counter = -(pool->nsolvables - 1); counter < pool->nsolvables; counter++)
 173     POOL_DEBUG(type, "    solvable [%d] -- rule [%d]\n", counter, solv->watches[counter + pool->nsolvables]);
 174 }
 175
 176 void
 177 solver_printdecisionq(Solver *solv, int type)
 178 {
 179   Pool *pool = solv->pool;
 180   int i;
 181   Id p, why;
 182
 183   POOL_DEBUG(type, "Decisions:\n");
 184   for (i = 0; i < solv->decisionq.count; i++)
 185     {
 186       p = solv->decisionq.elements[i];
 187       if (p > 0)
 188         POOL_DEBUG(type, "%d %d install  %s, ", i, solv->decisionmap[p], pool_solvid2str(pool, p));
 189       else
 190         POOL_DEBUG(type, "%d %d conflict %s, ", i, -solv->decisionmap[-p], pool_solvid2str(pool, -p));
 191       why = solv->decisionq_why.elements[i];
 192       if (why > 0)
 193         {
 194           POOL_DEBUG(type, "forced by ");
 195           solver_printruleclass(solv, type, solv->rules + why);
 196         }
 197       else if (why < 0)
 198         {
 199           POOL_DEBUG(type, "chosen from ");
 200           solver_printruleclass(solv, type, solv->rules - why);
 201         }
 202       else
 203         POOL_DEBUG(type, "picked for some unknown reason.\n");
 204     }
 205 }
 206
 207 /*
 208  * printdecisions
 209  */
 210
 211 void
 212 solver_printdecisions(Solver *solv)
 213 {
 214   Pool *pool = solv->pool;
 215   Repo *installed = solv->installed;
 216   Transaction *trans = solver_create_transaction(solv);
 217   Id p, type;
 218   int i, j;
 219   Solvable *s;
 220   Queue iq;
 221   Queue recommendations;
 222   Queue suggestions;
 223   Queue orphaned;
 224
 225   POOL_DEBUG(SOLV_DEBUG_RESULT, "\n");
 226   POOL_DEBUG(SOLV_DEBUG_RESULT, "transaction:\n");
 227
 228   queue_init(&iq);
 229   for (i = 0; i < trans->steps.count; i++)
 230     {
 231       p = trans->steps.elements[i];
 232       s = pool->solvables + p;
 233       type = transaction_type(trans, p, SOLVER_TRANSACTION_SHOW_ACTIVE|SOLVER_TRANSACTION_SHOW_ALL|SOLVER_TRANSACTION_SHOW_OBSOLETES|SOLVER_TRANSACTION_SHOW_MULTIINSTALL);
 234       switch(type)
 235         {
 236         case SOLVER_TRANSACTION_MULTIINSTALL:
 237           POOL_DEBUG(SOLV_DEBUG_RESULT, "  multi install %s", pool_solvable2str(pool, s));
 238           break;
 239         case SOLVER_TRANSACTION_MULTIREINSTALL:
 240           POOL_DEBUG(SOLV_DEBUG_RESULT, "  multi reinstall %s", pool_solvable2str(pool, s));
 241           break;
 242         case SOLVER_TRANSACTION_INSTALL:
 243           POOL_DEBUG(SOLV_DEBUG_RESULT, "  install   %s", pool_solvable2str(pool, s));
 244           break;
 245         case SOLVER_TRANSACTION_REINSTALL:
 246           POOL_DEBUG(SOLV_DEBUG_RESULT, "  reinstall %s", pool_solvable2str(pool, s));
 247           break;
 248         case SOLVER_TRANSACTION_DOWNGRADE:
 249           POOL_DEBUG(SOLV_DEBUG_RESULT, "  downgrade %s", pool_solvable2str(pool, s));
 250           break;
 251         case SOLVER_TRANSACTION_CHANGE:
 252           POOL_DEBUG(SOLV_DEBUG_RESULT, "  change    %s", pool_solvable2str(pool, s));
 253           break;
 254         case SOLVER_TRANSACTION_UPGRADE:
 255         case SOLVER_TRANSACTION_OBSOLETES:
 256           POOL_DEBUG(SOLV_DEBUG_RESULT, "  upgrade   %s", pool_solvable2str(pool, s));
 257           break;
 258         case SOLVER_TRANSACTION_ERASE:
 259           POOL_DEBUG(SOLV_DEBUG_RESULT, "  erase     %s", pool_solvable2str(pool, s));
 260           break;
 261         default:
 262           break;
 263         }
 264       switch(type)
 265         {
 266         case SOLVER_TRANSACTION_INSTALL:
 267         case SOLVER_TRANSACTION_ERASE:
 268         case SOLVER_TRANSACTION_MULTIINSTALL:
 269         case SOLVER_TRANSACTION_MULTIREINSTALL:
 270           POOL_DEBUG(SOLV_DEBUG_RESULT, "\n");
 271           break;
 272         case SOLVER_TRANSACTION_REINSTALL:
 273         case SOLVER_TRANSACTION_DOWNGRADE:
 274         case SOLVER_TRANSACTION_CHANGE:
 275         case SOLVER_TRANSACTION_UPGRADE:
 276         case SOLVER_TRANSACTION_OBSOLETES:
 277           transaction_all_obs_pkgs(trans, p, &iq);
 278           if (iq.count)
 279             {
 280               POOL_DEBUG(SOLV_DEBUG_RESULT, "  (obsoletes");
 281               for (j = 0; j < iq.count; j++)
 282                 POOL_DEBUG(SOLV_DEBUG_RESULT, " %s", pool_solvid2str(pool, iq.elements[j]));
 283               POOL_DEBUG(SOLV_DEBUG_RESULT, ")");
 284             }
 285           POOL_DEBUG(SOLV_DEBUG_RESULT, "\n");
 286           break;
 287         default:
 288           break;
 289         }
 290     }
 291   queue_free(&iq);
 292
 293   POOL_DEBUG(SOLV_DEBUG_RESULT, "\n");
 294
 295   queue_init(&recommendations);
 296   queue_init(&suggestions);
 297   queue_init(&orphaned);
 298   solver_get_recommendations(solv, &recommendations, &suggestions, 0);
 299   solver_get_orphaned(solv, &orphaned);
 300   if (recommendations.count)
 301     {
 302       POOL_DEBUG(SOLV_DEBUG_RESULT, "recommended packages:\n");
 303       for (i = 0; i < recommendations.count; i++)
 304         {
 305           s = pool->solvables + recommendations.elements[i];
 306           if (solv->decisionmap[recommendations.elements[i]] > 0)
 307             {
 308               if (installed && s->repo == installed)
 309                 POOL_DEBUG(SOLV_DEBUG_RESULT, "  %s (installed)\n", pool_solvable2str(pool, s));
 310               else
 311                 POOL_DEBUG(SOLV_DEBUG_RESULT, "  %s (selected)\n", pool_solvable2str(pool, s));
 312             }
 313           else
 314             POOL_DEBUG(SOLV_DEBUG_RESULT, "  %s\n", pool_solvable2str(pool, s));
 315         }
 316       POOL_DEBUG(SOLV_DEBUG_RESULT, "\n");
 317     }
 318
 319   if (suggestions.count)
 320     {
 321       POOL_DEBUG(SOLV_DEBUG_RESULT, "suggested packages:\n");
 322       for (i = 0; i < suggestions.count; i++)
 323         {
 324           s = pool->solvables + suggestions.elements[i];
 325           if (solv->decisionmap[suggestions.elements[i]] > 0)
 326             {
 327               if (installed && s->repo == installed)
 328                 POOL_DEBUG(SOLV_DEBUG_RESULT, "  %s (installed)\n", pool_solvable2str(pool, s));
 329               else
 330                 POOL_DEBUG(SOLV_DEBUG_RESULT, "  %s (selected)\n", pool_solvable2str(pool, s));
 331             }
 332           else
 333             POOL_DEBUG(SOLV_DEBUG_RESULT, "  %s\n", pool_solvable2str(pool, s));
 334         }
 335       POOL_DEBUG(SOLV_DEBUG_RESULT, "\n");
 336     }
 337   if (orphaned.count)
 338     {
 339       POOL_DEBUG(SOLV_DEBUG_RESULT, "orphaned packages:\n");
 340       for (i = 0; i < orphaned.count; i++)
 341         {
 342           s = pool->solvables + orphaned.elements[i];
 343           if (solv->decisionmap[solv->orphaned.elements[i]] > 0)
 344             POOL_DEBUG(SOLV_DEBUG_RESULT, "  %s (kept)\n", pool_solvable2str(pool, s));
 345           else
 346             POOL_DEBUG(SOLV_DEBUG_RESULT, "  %s (erased)\n", pool_solvable2str(pool, s));
 347         }
 348       POOL_DEBUG(SOLV_DEBUG_RESULT, "\n");
 349     }
 350   queue_free(&recommendations);
 351   queue_free(&suggestions);
 352   queue_free(&orphaned);
 353   transaction_free(trans);
 354 }
 355
 356 static inline
 357 const char *id2strnone(Pool *pool, Id id)
 358 {
 359   return !id || id == 1 ? "(none)" : pool_id2str(pool, id);
 360 }
 361
 362 void
 363 transaction_print(Transaction *trans)
 364 {
 365   Pool *pool = trans->pool;
 366   Queue classes, pkgs;
 367   int i, j, mode, l, linel;
 368   char line[76];
 369   const char *n;
 370
 371   queue_init(&classes);
 372   queue_init(&pkgs);
 373   mode = SOLVER_TRANSACTION_SHOW_OBSOLETES | SOLVER_TRANSACTION_OBSOLETE_IS_UPGRADE;
 374   transaction_classify(trans, mode, &classes);
 375   for (i = 0; i < classes.count; i += 4)
 376     {
 377       Id class = classes.elements[i];
 378       Id cnt = classes.elements[i + 1];
 379       switch(class)
 380         {
 381         case SOLVER_TRANSACTION_ERASE:
 382           POOL_DEBUG(SOLV_DEBUG_RESULT, "%d erased packages:\n", cnt);
 383           break;
 384         case SOLVER_TRANSACTION_INSTALL:
 385           POOL_DEBUG(SOLV_DEBUG_RESULT, "%d installed packages:\n", cnt);
 386           break;
 387         case SOLVER_TRANSACTION_REINSTALLED:
 388           POOL_DEBUG(SOLV_DEBUG_RESULT, "%d reinstalled packages:\n", cnt);
 389           break;
 390         case SOLVER_TRANSACTION_DOWNGRADED:
 391           POOL_DEBUG(SOLV_DEBUG_RESULT, "%d downgraded packages:\n", cnt);
 392           break;
 393         case SOLVER_TRANSACTION_CHANGED:
 394           POOL_DEBUG(SOLV_DEBUG_RESULT, "%d changed packages:\n", cnt);
 395           break;
 396         case SOLVER_TRANSACTION_UPGRADED:
 397           POOL_DEBUG(SOLV_DEBUG_RESULT, "%d upgraded packages:\n", cnt);
 398           break;
 399         case SOLVER_TRANSACTION_VENDORCHANGE:
 400           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]));
 401           break;
 402         case SOLVER_TRANSACTION_ARCHCHANGE:
 403           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]));
 404           break;
 405         default:
 406           class = SOLVER_TRANSACTION_IGNORE;
 407           break;
 408         }
 409       if (class == SOLVER_TRANSACTION_IGNORE)
 410         continue;
 411       transaction_classify_pkgs(trans, mode, class, classes.elements[i + 2], classes.elements[i + 3], &pkgs);
 412       *line = 0;
 413       linel = 0;
 414       for (j = 0; j < pkgs.count; j++)
 415         {
 416           Id p = pkgs.elements[j];
 417           Solvable *s = pool->solvables + p;
 418           Solvable *s2;
 419
 420           switch(class)
 421             {
 422             case SOLVER_TRANSACTION_DOWNGRADED:
 423             case SOLVER_TRANSACTION_UPGRADED:
 424               s2 = pool->solvables + transaction_obs_pkg(trans, p);
 425               POOL_DEBUG(SOLV_DEBUG_RESULT, "  - %s -> %s\n", pool_solvable2str(pool, s), pool_solvable2str(pool, s2));
 426               break;
 427             case SOLVER_TRANSACTION_VENDORCHANGE:
 428             case SOLVER_TRANSACTION_ARCHCHANGE:
 429               n = pool_id2str(pool, s->name);
 430               l = strlen(n);
 431               if (l + linel > sizeof(line) - 3)
 432                 {
 433                   if (*line)
 434                     POOL_DEBUG(SOLV_DEBUG_RESULT, "    %s\n", line);
 435                   *line = 0;
 436                   linel = 0;
 437                 }
 438               if (l + linel > sizeof(line) - 3)
 439                 POOL_DEBUG(SOLV_DEBUG_RESULT, "    %s\n", n);
 440               else
 441                 {
 442                   if (*line)
 443                     {
 444                       strcpy(line + linel, ", ");
 445                       linel += 2;
 446                     }
 447                   strcpy(line + linel, n);
 448                   linel += l;
 449                 }
 450               break;
 451             default:
 452               POOL_DEBUG(SOLV_DEBUG_RESULT, "  - %s\n", pool_solvable2str(pool, s));
 453               break;
 454             }
 455         }
 456       if (*line)
 457         POOL_DEBUG(SOLV_DEBUG_RESULT, "    %s\n", line);
 458       POOL_DEBUG(SOLV_DEBUG_RESULT, "\n");
 459     }
 460   queue_free(&classes);
 461   queue_free(&pkgs);
 462 }
 463
 464 void
 465 solver_printproblemruleinfo(Solver *solv, Id probr)
 466 {
 467   Pool *pool = solv->pool;
 468   Id dep, source, target;
 469   SolverRuleinfo type = solver_ruleinfo(solv, probr, &source, &target, &dep);
 470
 471   POOL_DEBUG(SOLV_DEBUG_RESULT, "%s\n", solver_problemruleinfo2str(solv, type, source, target, dep));
 472 }
 473
 474 void
 475 solver_printprobleminfo(Solver *solv, Id problem)
 476 {
 477   solver_printproblemruleinfo(solv, solver_findproblemrule(solv, problem));
 478 }
 479
 480 void
 481 solver_printcompleteprobleminfo(Solver *solv, Id problem)
 482 {
 483   Queue q;
 484   Id probr;
 485   int i, nobad = 0;
 486
 487   queue_init(&q);
 488   solver_findallproblemrules(solv, problem, &q);
 489   for (i = 0; i < q.count; i++)
 490     {
 491       probr = q.elements[i];
 492       if (!(probr >= solv->updaterules && probr < solv->updaterules_end) && !(probr >= solv->jobrules && probr < solv->jobrules_end))
 493         {
 494           nobad = 1;
 495           break;
 496         }
 497     }
 498   for (i = 0; i < q.count; i++)
 499     {
 500       probr = q.elements[i];
 501       if (nobad && ((probr >= solv->updaterules && probr < solv->updaterules_end) || (probr >= solv->jobrules && probr < solv->jobrules_end)))
 502         continue;
 503       solver_printproblemruleinfo(solv, probr);
 504     }
 505   queue_free(&q);
 506 }
 507
 508 void
 509 solver_printsolution(Solver *solv, Id problem, Id solution)
 510 {
 511   Pool *pool = solv->pool;
 512   Queue q;
 513   int i;
 514   queue_init(&q);
 515   solver_all_solutionelements(solv, problem, solution, 1, &q);
 516   for (i = 0; i < q.count; i += 3)
 517     POOL_DEBUG(SOLV_DEBUG_RESULT, "  - %s\n", solver_solutionelementtype2str(solv, q.elements[i], q.elements[i + 1], q.elements[i + 2]));
 518   queue_free(&q);
 519 }
 520
 521 void
 522 solver_printallsolutions(Solver *solv)
 523 {
 524   Pool *pool = solv->pool;
 525   int pcnt;
 526   Id problem, solution;
 527
 528   POOL_DEBUG(SOLV_DEBUG_RESULT, "Encountered problems! Here are the solutions:\n\n");
 529   pcnt = 0;
 530   problem = 0;
 531   while ((problem = solver_next_problem(solv, problem)) != 0)
 532     {
 533       pcnt++;
 534       POOL_DEBUG(SOLV_DEBUG_RESULT, "Problem %d:\n", pcnt);
 535       POOL_DEBUG(SOLV_DEBUG_RESULT, "====================================\n");
 536 #if 1
 537       solver_printprobleminfo(solv, problem);
 538 #else
 539       solver_printcompleteprobleminfo(solv, problem);
 540 #endif
 541       POOL_DEBUG(SOLV_DEBUG_RESULT, "\n");
 542       solution = 0;
 543       while ((solution = solver_next_solution(solv, problem, solution)) != 0)
 544         {
 545           solver_printsolution(solv, problem, solution);
 546           POOL_DEBUG(SOLV_DEBUG_RESULT, "\n");
 547         }
 548     }
 549 }
 550