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