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