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 "bitmap.h"
  22 #include "pool.h"
  23 #include "util.h"
  24 #include "evr.h"
  25 #include "policy.h"
  26
  27
  28 /*
  29  * create obsoletesmap from solver decisions
  30  *
  31  * for solvables in installed repo:
  32  *   0 - not obsoleted
  33  *   p - one of the packages that obsolete us
  34  * for all others:
  35  *   n - number of packages this package obsoletes
  36  *
  37  */
  38
  39 Id *
  40 solver_create_decisions_obsoletesmap(Solver *solv)
  41 {
  42   Pool *pool = solv->pool;
  43   Repo *installed = solv->installed;
  44   Id p, *obsoletesmap = NULL;
  45   int i;
  46   Solvable *s;
  47
  48   obsoletesmap = (Id *)sat_calloc(pool->nsolvables, sizeof(Id));
  49   if (installed)
  50     {
  51       for (i = 0; i < solv->decisionq.count; i++)
  52         {
  53           Id *pp, n;
  54
  55           n = solv->decisionq.elements[i];
  56           if (n < 0)
  57             continue;
  58           if (n == SYSTEMSOLVABLE)
  59             continue;
  60           s = pool->solvables + n;
  61           if (s->repo == installed)             /* obsoletes don't count for already installed packages */
  62             continue;
  63           FOR_PROVIDES(p, pp, s->name)
  64             {
  65               if (!solv->implicitobsoleteusesprovides && s->name != pool->solvables[p].name)
  66                 continue;
  67               if (pool->solvables[p].repo == installed && !obsoletesmap[p])
  68                 {
  69                   obsoletesmap[p] = n;
  70                   obsoletesmap[n]++;
  71                 }
  72             }
  73         }
  74       for (i = 0; i < solv->decisionq.count; i++)
  75         {
  76           Id obs, *obsp;
  77           Id *pp, n;
  78
  79           n = solv->decisionq.elements[i];
  80           if (n < 0)
  81             continue;
  82           if (n == SYSTEMSOLVABLE)
  83             continue;
  84           s = pool->solvables + n;
  85           if (s->repo == installed)             /* obsoletes don't count for already installed packages */
  86             continue;
  87           if (!s->obsoletes)
  88             continue;
  89           obsp = s->repo->idarraydata + s->obsoletes;
  90           while ((obs = *obsp++) != 0)
  91             FOR_PROVIDES(p, pp, obs)
  92               {
  93                 if (!solv->obsoleteusesprovides && s->name != pool->solvables[p].name)
  94                   continue;
  95                 if (pool->solvables[p].repo == installed && !obsoletesmap[p])
  96                   {
  97                     obsoletesmap[p] = n;
  98                     obsoletesmap[n]++;
  99                   }
 100               }
 101         }
 102     }
 103   return obsoletesmap;
 104 }
 105
 106 void
 107 solver_printruleelement(Solver *solv, int type, Rule *r, Id v)
 108 {
 109   Pool *pool = solv->pool;
 110   Solvable *s;
 111   if (v < 0)
 112     {
 113       s = pool->solvables + -v;
 114       POOL_DEBUG(type, "    !%s [%d]", solvable2str(pool, s), -v);
 115     }
 116   else
 117     {
 118       s = pool->solvables + v;
 119       POOL_DEBUG(type, "    %s [%d]", solvable2str(pool, s), v);
 120     }
 121   if (r)
 122     {
 123       if (r->w1 == v)
 124         POOL_DEBUG(type, " (w1)");
 125       if (r->w2 == v)
 126         POOL_DEBUG(type, " (w2)");
 127     }
 128   if (solv->decisionmap[s - pool->solvables] > 0)
 129     POOL_DEBUG(type, " Install.level%d", solv->decisionmap[s - pool->solvables]);
 130   if (solv->decisionmap[s - pool->solvables] < 0)
 131     POOL_DEBUG(type, " Conflict.level%d", -solv->decisionmap[s - pool->solvables]);
 132   POOL_DEBUG(type, "\n");
 133 }
 134
 135
 136 /*
 137  * print rule
 138  */
 139
 140 void
 141 solver_printrule(Solver *solv, int type, Rule *r)
 142 {
 143   Pool *pool = solv->pool;
 144   int i;
 145   Id d, v;
 146
 147   if (r >= solv->rules && r < solv->rules + solv->nrules)   /* r is a solver rule */
 148     POOL_DEBUG(type, "Rule #%d:", (int)(r - solv->rules));
 149   else
 150     POOL_DEBUG(type, "Rule:");                 /* r is any rule */
 151   if (r && r->d < 0)
 152     POOL_DEBUG(type, " (disabled)");
 153   POOL_DEBUG(type, "\n");
 154   d = r->d < 0 ? -r->d - 1 : r->d;
 155   for (i = 0; ; i++)
 156     {
 157       if (i == 0)
 158           /* print direct literal */
 159         v = r->p;
 160       else if (!d)
 161         {
 162           if (i == 2)
 163             break;
 164           /* binary rule --> print w2 as second literal */
 165           v = r->w2;
 166         }
 167       else
 168           /* every other which is in d */
 169         v = solv->pool->whatprovidesdata[d + i - 1];
 170       if (v == ID_NULL)
 171         break;
 172       solver_printruleelement(solv, type, r, v);
 173     }
 174   POOL_DEBUG(type, "    next rules: %d %d\n", r->n1, r->n2);
 175 }
 176
 177 void
 178 solver_printruleclass(Solver *solv, int type, Rule *r)
 179 {
 180   Pool *pool = solv->pool;
 181   Id p = r - solv->rules;
 182   assert(p >= 0);
 183   if (p < solv->learntrules)
 184     if (MAPTST(&solv->weakrulemap, p))
 185       POOL_DEBUG(type, "WEAK ");
 186   if (p >= solv->learntrules)
 187     POOL_DEBUG(type, "LEARNT ");
 188   else if (p >= solv->featurerules)
 189     POOL_DEBUG(type, "FEATURE ");
 190   else if (p >= solv->updaterules)
 191     POOL_DEBUG(type, "UPDATE ");
 192   else if (p >= solv->jobrules)
 193     POOL_DEBUG(type, "JOB ");
 194   solver_printrule(solv, type, r);
 195 }
 196
 197 void
 198 solver_printproblem(Solver *solv, Id v)
 199 {
 200   Pool *pool = solv->pool;
 201   int i;
 202   Rule *r;
 203   Id *jp;
 204
 205   if (v > 0)
 206     solver_printruleclass(solv, SAT_DEBUG_SOLUTIONS, solv->rules + v);
 207   else
 208     {
 209       v = -(v + 1);
 210       POOL_DEBUG(SAT_DEBUG_SOLUTIONS, "JOB %d\n", v);
 211       jp = solv->ruletojob.elements;
 212       for (i = solv->jobrules, r = solv->rules + i; i < solv->updaterules; i++, r++, jp++)
 213         if (*jp == v)
 214           {
 215             POOL_DEBUG(SAT_DEBUG_SOLUTIONS, "- ");
 216             solver_printrule(solv, SAT_DEBUG_SOLUTIONS, r);
 217           }
 218       POOL_DEBUG(SAT_DEBUG_SOLUTIONS, "ENDJOB\n");
 219     }
 220 }
 221
 222 void
 223 solver_printwatches(Solver *solv, int type)
 224 {
 225   Pool *pool = solv->pool;
 226   int counter;
 227
 228   POOL_DEBUG(type, "Watches: \n");
 229   for (counter = -(pool->nsolvables - 1); counter < pool->nsolvables; counter++)
 230     POOL_DEBUG(type, "    solvable [%d] -- rule [%d]\n", counter, solv->watches[counter + pool->nsolvables]);
 231 }
 232
 233 /*
 234  * printdecisions
 235  */
 236
 237 void
 238 solver_printdecisions(Solver *solv)
 239 {
 240   Pool *pool = solv->pool;
 241   Repo *installed = solv->installed;
 242   Id p, *obsoletesmap = solver_create_decisions_obsoletesmap(solv);
 243   int i;
 244   Solvable *s;
 245
 246   IF_POOLDEBUG (SAT_DEBUG_SCHUBI)
 247     {
 248       POOL_DEBUG(SAT_DEBUG_SCHUBI, "----- Decisions -----\n");
 249       for (i = 0; i < solv->decisionq.count; i++)
 250         {
 251           p = solv->decisionq.elements[i];
 252           solver_printruleelement(solv, SAT_DEBUG_SCHUBI, 0, p);
 253         }
 254       POOL_DEBUG(SAT_DEBUG_SCHUBI, "----- Decisions end -----\n");
 255     }
 256
 257   /* print solvables to be erased */
 258
 259   if (installed)
 260     {
 261       FOR_REPO_SOLVABLES(installed, p, s)
 262         {
 263           if (solv->decisionmap[p] >= 0)
 264             continue;
 265           if (obsoletesmap[p])
 266             continue;
 267           POOL_DEBUG(SAT_DEBUG_RESULT, "erase   %s\n", solvable2str(pool, s));
 268         }
 269     }
 270
 271   /* print solvables to be installed */
 272
 273   for (i = 0; i < solv->decisionq.count; i++)
 274     {
 275       int j;
 276       p = solv->decisionq.elements[i];
 277       if (p < 0)
 278         continue;
 279       if (p == SYSTEMSOLVABLE)
 280         continue;
 281       s = pool->solvables + p;
 282       if (installed && s->repo == installed)
 283         continue;
 284
 285       if (!obsoletesmap[p])
 286         {
 287           POOL_DEBUG(SAT_DEBUG_RESULT, "install   %s", solvable2str(pool, s));
 288         }
 289       else
 290         {
 291           Id xp, *xpp;
 292           FOR_PROVIDES(xp, xpp, s->name)
 293             {
 294               Solvable *s2 = pool->solvables + xp;
 295               if (s2->name != s->name)
 296                 continue;
 297               if (evrcmp(pool, s->evr, s2->evr, EVRCMP_MATCH_RELEASE) < 0)
 298                 break;
 299             }
 300           if (xp)
 301             POOL_DEBUG(SAT_DEBUG_RESULT, "downgrade %s", solvable2str(pool, s));
 302           else
 303             POOL_DEBUG(SAT_DEBUG_RESULT, "upgrade   %s", solvable2str(pool, s));
 304           POOL_DEBUG(SAT_DEBUG_RESULT, "  (obsoletes");
 305           for (j = installed->start; j < installed->end; j++)
 306             if (obsoletesmap[j] == p)
 307               POOL_DEBUG(SAT_DEBUG_RESULT, " %s", solvable2str(pool, pool->solvables + j));
 308           POOL_DEBUG(SAT_DEBUG_RESULT, ")");
 309         }
 310       POOL_DEBUG(SAT_DEBUG_RESULT, "\n");
 311     }
 312
 313   sat_free(obsoletesmap);
 314
 315   if (solv->recommendations.count)
 316     {
 317       POOL_DEBUG(SAT_DEBUG_RESULT, "\nrecommended packages:\n");
 318       for (i = 0; i < solv->recommendations.count; i++)
 319         {
 320           s = pool->solvables + solv->recommendations.elements[i];
 321           if (solv->decisionmap[solv->recommendations.elements[i]] > 0)
 322             {
 323               if (installed && s->repo == installed)
 324                 POOL_DEBUG(SAT_DEBUG_RESULT, "- %s (installed)\n", solvable2str(pool, s));
 325               else
 326                 POOL_DEBUG(SAT_DEBUG_RESULT, "- %s (selected)\n", solvable2str(pool, s));
 327             }
 328           else
 329             POOL_DEBUG(SAT_DEBUG_RESULT, "- %s\n", solvable2str(pool, s));
 330         }
 331     }
 332
 333   if (solv->suggestions.count)
 334     {
 335       POOL_DEBUG(SAT_DEBUG_RESULT, "\nsuggested packages:\n");
 336       for (i = 0; i < solv->suggestions.count; i++)
 337         {
 338           s = pool->solvables + solv->suggestions.elements[i];
 339           if (solv->decisionmap[solv->suggestions.elements[i]] > 0)
 340             {
 341               if (installed && s->repo == installed)
 342                 POOL_DEBUG(SAT_DEBUG_RESULT, "- %s (installed)\n", solvable2str(pool, s));
 343               else
 344                 POOL_DEBUG(SAT_DEBUG_RESULT, "- %s (selected)\n", solvable2str(pool, s));
 345             }
 346           else
 347             POOL_DEBUG(SAT_DEBUG_RESULT, "- %s\n", solvable2str(pool, s));
 348         }
 349     }
 350 }
 351
 352 void
 353 solver_printprobleminfo(Solver *solv, Queue *job, Id problem)
 354 {
 355   Pool *pool = solv->pool;
 356   Id probr;
 357   Id dep, source, target;
 358   Solvable *s, *s2;
 359
 360   probr = solver_findproblemrule(solv, problem);
 361   switch (solver_problemruleinfo(solv, job, probr, &dep, &source, &target))
 362     {
 363     case SOLVER_PROBLEM_UPDATE_RULE:
 364       s = pool_id2solvable(pool, source);
 365       POOL_DEBUG(SAT_DEBUG_RESULT, "problem with installed package %s\n", solvable2str(pool, s));
 366       return;
 367     case SOLVER_PROBLEM_JOB_RULE:
 368       POOL_DEBUG(SAT_DEBUG_RESULT, "conflicting requests\n");
 369       return;
 370     case SOLVER_PROBLEM_JOB_NOTHING_PROVIDES_DEP:
 371       POOL_DEBUG(SAT_DEBUG_RESULT, "nothing provides requested %s\n", dep2str(pool, dep));
 372       return;
 373     case SOLVER_PROBLEM_NOT_INSTALLABLE:
 374       s = pool_id2solvable(pool, source);
 375       POOL_DEBUG(SAT_DEBUG_RESULT, "package %s is not installable\n", solvable2str(pool, s));
 376       return;
 377     case SOLVER_PROBLEM_NOTHING_PROVIDES_DEP:
 378       s = pool_id2solvable(pool, source);
 379       POOL_DEBUG(SAT_DEBUG_RESULT, "nothing provides %s needed by %s\n", dep2str(pool, dep), solvable2str(pool, s));
 380       return;
 381     case SOLVER_PROBLEM_SAME_NAME:
 382       s = pool_id2solvable(pool, source);
 383       s2 = pool_id2solvable(pool, target);
 384       POOL_DEBUG(SAT_DEBUG_RESULT, "cannot install both %s and %s\n", solvable2str(pool, s), solvable2str(pool, s2));
 385       return;
 386     case SOLVER_PROBLEM_PACKAGE_CONFLICT:
 387       s = pool_id2solvable(pool, source);
 388       s2 = pool_id2solvable(pool, target);
 389       POOL_DEBUG(SAT_DEBUG_RESULT, "package %s conflicts with %s provided by %s\n", solvable2str(pool, s), dep2str(pool, dep), solvable2str(pool, s2));
 390       return;
 391     case SOLVER_PROBLEM_PACKAGE_OBSOLETES:
 392       s = pool_id2solvable(pool, source);
 393       s2 = pool_id2solvable(pool, target);
 394       POOL_DEBUG(SAT_DEBUG_RESULT, "package %s obsoletes %s provided by %s\n", solvable2str(pool, s), dep2str(pool, dep), solvable2str(pool, s2));
 395       return;
 396     case SOLVER_PROBLEM_DEP_PROVIDERS_NOT_INSTALLABLE:
 397       s = pool_id2solvable(pool, source);
 398       POOL_DEBUG(SAT_DEBUG_RESULT, "package %s requires %s, but none of the providers can be installed\n", solvable2str(pool, s), dep2str(pool, dep));
 399       return;
 400     case SOLVER_PROBLEM_SELF_CONFLICT:
 401       s = pool_id2solvable(pool, source);
 402       POOL_DEBUG(SAT_DEBUG_RESULT, "package %s conflicts with %s provided by itself\n", solvable2str(pool, s), dep2str(pool, dep));
 403       return;
 404     }
 405 }
 406
 407 void
 408 solver_printsolutions(Solver *solv, Queue *job)
 409 {
 410   Pool *pool = solv->pool;
 411   int pcnt;
 412   Id p, rp, how, what;
 413   Id problem, solution, element;
 414   Solvable *s, *sd;
 415
 416   POOL_DEBUG(SAT_DEBUG_RESULT, "Encountered problems! Here are the solutions:\n\n");
 417   pcnt = 1;
 418   problem = 0;
 419   while ((problem = solver_next_problem(solv, problem)) != 0)
 420     {
 421       POOL_DEBUG(SAT_DEBUG_RESULT, "Problem %d:\n", pcnt++);
 422       POOL_DEBUG(SAT_DEBUG_RESULT, "====================================\n");
 423       solver_printprobleminfo(solv, job, problem);
 424       POOL_DEBUG(SAT_DEBUG_RESULT, "\n");
 425       solution = 0;
 426       while ((solution = solver_next_solution(solv, problem, solution)) != 0)
 427         {
 428           element = 0;
 429           while ((element = solver_next_solutionelement(solv, problem, solution, element, &p, &rp)) != 0)
 430             {
 431               if (p == 0)
 432                 {
 433                   /* job, rp is index into job queue */
 434                   how = job->elements[rp - 1] & ~SOLVER_WEAK;
 435                   what = job->elements[rp];
 436                   switch (how)
 437                     {
 438                     case SOLVER_INSTALL_SOLVABLE:
 439                       s = pool->solvables + what;
 440                       if (solv->installed && s->repo == solv->installed)
 441                         POOL_DEBUG(SAT_DEBUG_RESULT, "- do not keep %s installed\n", solvable2str(pool, s));
 442                       else
 443                         POOL_DEBUG(SAT_DEBUG_RESULT, "- do not install %s\n", solvable2str(pool, s));
 444                       break;
 445                     case SOLVER_ERASE_SOLVABLE:
 446                       s = pool->solvables + what;
 447                       if (solv->installed && s->repo == solv->installed)
 448                         POOL_DEBUG(SAT_DEBUG_RESULT, "- do not deinstall %s\n", solvable2str(pool, s));
 449                       else
 450                         POOL_DEBUG(SAT_DEBUG_RESULT, "- do not forbid installation of %s\n", solvable2str(pool, s));
 451                       break;
 452                     case SOLVER_INSTALL_SOLVABLE_NAME:
 453                       POOL_DEBUG(SAT_DEBUG_RESULT, "- do not install %s\n", dep2str(pool, what));
 454                       break;
 455                     case SOLVER_ERASE_SOLVABLE_NAME:
 456                       POOL_DEBUG(SAT_DEBUG_RESULT, "- do not deinstall %s\n", dep2str(pool, what));
 457                       break;
 458                     case SOLVER_INSTALL_SOLVABLE_PROVIDES:
 459                       POOL_DEBUG(SAT_DEBUG_RESULT, "- do not install a solvable providing %s\n", dep2str(pool, what));
 460                       break;
 461                     case SOLVER_ERASE_SOLVABLE_PROVIDES:
 462                       POOL_DEBUG(SAT_DEBUG_RESULT, "- do not deinstall all solvables providing %s\n", dep2str(pool, what));
 463                       break;
 464                     case SOLVER_INSTALL_SOLVABLE_UPDATE:
 465                       s = pool->solvables + what;
 466                       POOL_DEBUG(SAT_DEBUG_RESULT, "- do not install most recent version of %s\n", solvable2str(pool, s));
 467                       break;
 468                     default:
 469                       POOL_DEBUG(SAT_DEBUG_RESULT, "- do something different\n");
 470                       break;
 471                     }
 472                 }
 473               else
 474                 {
 475                   /* policy, replace p with rp */
 476                   s = pool->solvables + p;
 477                   sd = rp ? pool->solvables + rp : 0;
 478                   if (sd)
 479                     {
 480                       int gotone = 0;
 481                       if (!solv->allowdowngrade && evrcmp(pool, s->evr, sd->evr, EVRCMP_MATCH_RELEASE) > 0)
 482                         {
 483                           POOL_DEBUG(SAT_DEBUG_RESULT, "- allow downgrade of %s to %s\n", solvable2str(pool, s), solvable2str(pool, sd));
 484                           gotone = 1;
 485                         }
 486                       if (!solv->allowarchchange && s->name == sd->name && s->arch != sd->arch && policy_illegal_archchange(solv, s, sd))
 487                         {
 488                           POOL_DEBUG(SAT_DEBUG_RESULT, "- allow architecture change of %s to %s\n", solvable2str(pool, s), solvable2str(pool, sd));
 489                           gotone = 1;
 490                         }
 491                       if (!solv->allowvendorchange && s->name == sd->name && s->vendor != sd->vendor && policy_illegal_vendorchange(solv, s, sd))
 492                         {
 493                           if (sd->vendor)
 494                             POOL_DEBUG(SAT_DEBUG_RESULT, "- allow vendor change from '%s' (%s) to '%s' (%s)\n", id2str(pool, s->vendor), solvable2str(pool, s), id2str(pool, sd->vendor), solvable2str(pool, sd));
 495                           else
 496                             POOL_DEBUG(SAT_DEBUG_RESULT, "- allow vendor change from '%s' (%s) to no vendor (%s)\n", id2str(pool, s->vendor), solvable2str(pool, s), solvable2str(pool, sd));
 497                           gotone = 1;
 498                         }
 499                       if (!gotone)
 500                         POOL_DEBUG(SAT_DEBUG_RESULT, "- allow replacement of %s with %s\n", solvable2str(pool, s), solvable2str(pool, sd));
 501                     }
 502                   else
 503                     {
 504                       POOL_DEBUG(SAT_DEBUG_RESULT, "- allow deinstallation of %s\n", solvable2str(pool, s));
 505                     }
 506
 507                 }
 508             }
 509           POOL_DEBUG(SAT_DEBUG_RESULT, "\n");
 510         }
 511     }
 512 }
 513