src/solver_util.c

   1 /*
   2  * Copyright (c) 2017, SUSE Inc.
   3  *
   4  * This program is licensed under the BSD license, read LICENSE.BSD
   5  * for further information
   6  */
   7
   8 /*
   9  * solver_util.c
  10  *
  11  * Dependency solver helper functions
  12  */
  13
  14 #include <stdio.h>
  15 #include <stdlib.h>
  16 #include <unistd.h>
  17 #include <string.h>
  18
  19 #include "solver.h"
  20 #include "solver_private.h"
  21 #include "bitmap.h"
  22 #include "pool.h"
  23 #include "poolarch.h"
  24 #include "util.h"
  25
  26
  27 /*-------------------------------------------------------------------
  28  * check if a installed package p is being updated
  29  */
  30 static int
  31 solver_is_updating(Solver *solv, Id p)
  32 {
  33   /* check if the update rule is true */
  34   Pool *pool = solv->pool;
  35   Rule *r;
  36   Id l, pp;
  37   if (solv->decisionmap[p] >= 0)
  38     return 0;   /* old package stayed */
  39   r = solv->rules + solv->updaterules + (p - solv->installed->start);
  40   FOR_RULELITERALS(l, pp, r)
  41     if (l > 0 && l != p && solv->decisionmap[l] > 0)
  42       return 1;
  43   return 0;
  44 }
  45
  46 /*-------------------------------------------------------------------
  47  * handle split provides
  48  *
  49  * a splitprovides dep looks like
  50  *     namespace:splitprovides(pkg REL_WITH path)
  51  * and is only true if pkg is installed and contains the specified path.
  52  * we also make sure that pkg is selected for an update, otherwise the
  53  * update would always be forced onto the user.
  54  * Map m is the map used when called from dep_possible.
  55  */
  56 int
  57 solver_splitprovides(Solver *solv, Id dep, Map *m)
  58 {
  59   Pool *pool = solv->pool;
  60   Id p, pp;
  61   Reldep *rd;
  62   Solvable *s;
  63
  64   if (!solv->dosplitprovides || !solv->installed)
  65     return 0;
  66   if (!ISRELDEP(dep))
  67     return 0;
  68   rd = GETRELDEP(pool, dep);
  69   if (rd->flags != REL_WITH)
  70     return 0;
  71   /*
  72    * things are a bit tricky here if pool->addedprovides == 1, because most split-provides are in
  73    * a non-standard location. If we simply call pool_whatprovides, we'll drag in the complete
  74    * file list. Instead we rely on pool_addfileprovides ignoring the addfileprovidesfiltered flag
  75    * for installed packages and check the lazywhatprovidesq (ignoring the REL_WITH part, but
  76    * we filter the package name further down anyway).
  77    */
  78   if (pool->addedfileprovides == 1 && !ISRELDEP(rd->evr) && !pool->whatprovides[rd->evr])
  79     pp = pool_searchlazywhatprovidesq(pool, rd->evr);
  80   else
  81     pp = pool_whatprovides(pool, dep);
  82   while ((p = pool->whatprovidesdata[pp++]) != 0)
  83     {
  84       /* here we have packages that provide the correct name and contain the path,
  85        * now do extra filtering */
  86       s = pool->solvables + p;
  87       if (s->repo != solv->installed || s->name != rd->name)
  88         continue;
  89       /* check if the package is updated. if m is set, we're called from dep_possible */
  90       if (m || solver_is_updating(solv, p))
  91         return 1;
  92     }
  93   return 0;
  94 }
  95
  96 int
  97 solver_dep_possible_slow(Solver *solv, Id dep, Map *m)
  98 {
  99   Pool *pool = solv->pool;
 100   Id p, pp;
 101
 102   if (ISRELDEP(dep))
 103     {
 104       Reldep *rd = GETRELDEP(pool, dep);
 105       if (rd->flags >= 8)
 106          {
 107           if (rd->flags == REL_COND || rd->flags == REL_UNLESS)
 108             return 1;
 109           if (rd->flags == REL_AND)
 110             {
 111               if (!solver_dep_possible_slow(solv, rd->name, m))
 112                 return 0;
 113               return solver_dep_possible_slow(solv, rd->evr, m);
 114             }
 115           if (rd->flags == REL_OR)
 116             {
 117               if (solver_dep_possible_slow(solv, rd->name, m))
 118                 return 1;
 119               return solver_dep_possible_slow(solv, rd->evr, m);
 120             }
 121           if (rd->flags == REL_NAMESPACE && rd->name == NAMESPACE_SPLITPROVIDES)
 122             return solver_splitprovides(solv, rd->evr, m);
 123         }
 124     }
 125   FOR_PROVIDES(p, pp, dep)
 126     {
 127       if (MAPTST(m, p))
 128         return 1;
 129     }
 130   return 0;
 131 }
 132
 133 int
 134 solver_dep_fulfilled_cplx(Solver *solv, Reldep *rd)
 135 {
 136   Pool *pool = solv->pool;
 137   if (rd->flags == REL_COND)
 138     {
 139       if (ISRELDEP(rd->evr))
 140         {
 141           Reldep *rd2 = GETRELDEP(pool, rd->evr);
 142           if (rd2->flags == REL_ELSE)
 143             {
 144               if (solver_dep_fulfilled(solv, rd2->name))
 145                 return solver_dep_fulfilled(solv, rd->name);
 146               return solver_dep_fulfilled(solv, rd2->evr);
 147             }
 148         }
 149       if (solver_dep_fulfilled(solv, rd->name))
 150         return 1;
 151       return !solver_dep_fulfilled(solv, rd->evr);
 152     }
 153   if (rd->flags == REL_UNLESS)
 154     {
 155       if (ISRELDEP(rd->evr))
 156         {
 157           Reldep *rd2 = GETRELDEP(pool, rd->evr);
 158           if (rd2->flags == REL_ELSE)
 159             {
 160               if (!solver_dep_fulfilled(solv, rd2->name))
 161                 return solver_dep_fulfilled(solv, rd->name);
 162               return solver_dep_fulfilled(solv, rd2->evr);
 163             }
 164         }
 165       if (!solver_dep_fulfilled(solv, rd->name))
 166         return 0;
 167       return !solver_dep_fulfilled(solv, rd->evr);
 168     }
 169   if (rd->flags == REL_AND)
 170     {
 171       if (!solver_dep_fulfilled(solv, rd->name))
 172         return 0;
 173       return solver_dep_fulfilled(solv, rd->evr);
 174     }
 175   if (rd->flags == REL_OR)
 176     {
 177       if (solver_dep_fulfilled(solv, rd->name))
 178         return 1;
 179       return solver_dep_fulfilled(solv, rd->evr);
 180     }
 181   return 0;
 182 }
 183
 184
 185 /* mirrors solver_dep_fulfilled, but returns 2 if a new package
 186  * was involved */
 187 static int
 188 solver_dep_fulfilled_alreadyinstalled(Solver *solv, Id dep)
 189 {
 190   Pool *pool = solv->pool;
 191   Id p, pp;
 192   int r;
 193
 194   if (ISRELDEP(dep))
 195     {
 196       Reldep *rd = GETRELDEP(pool, dep);
 197       if (rd->flags == REL_COND)
 198         {
 199           int r1, r2;
 200           if (ISRELDEP(rd->evr))
 201             {
 202               Reldep *rd2 = GETRELDEP(pool, rd->evr);
 203               if (rd2->flags == REL_ELSE)
 204                 {
 205                   r1 = solver_dep_fulfilled_alreadyinstalled(solv, rd2->name);
 206                   if (r1)
 207                     {
 208                       r2 = solver_dep_fulfilled_alreadyinstalled(solv, rd->name);
 209                       return r2 && r1 == 2 ? 2 : r2;
 210                     }
 211                   return solver_dep_fulfilled_alreadyinstalled(solv, rd2->evr);
 212                 }
 213             }
 214           r1 = solver_dep_fulfilled_alreadyinstalled(solv, rd->name);
 215           r2 = !solver_dep_fulfilled_alreadyinstalled(solv, rd->evr);
 216           if (!r1 && !r2)
 217             return 0;
 218           return r1 == 2 ? 2 : 1;
 219         }
 220       if (rd->flags == REL_UNLESS)
 221         {
 222           int r1, r2;
 223           if (ISRELDEP(rd->evr))
 224             {
 225               Reldep *rd2 = GETRELDEP(pool, rd->evr);
 226               if (rd2->flags == REL_ELSE)
 227                 {
 228                   r1 = solver_dep_fulfilled_alreadyinstalled(solv, rd2->name);
 229                   if (r1)
 230                     {
 231                       r2 = solver_dep_fulfilled_alreadyinstalled(solv, rd2->evr);
 232                       return r2 && r1 == 2 ? 2 : r2;
 233                     }
 234                   return solver_dep_fulfilled_alreadyinstalled(solv, rd->name);
 235                 }
 236             }
 237           /* A AND NOT(B) */
 238           r1 = solver_dep_fulfilled_alreadyinstalled(solv, rd->name);
 239           r2 = !solver_dep_fulfilled_alreadyinstalled(solv, rd->evr);
 240           if (!r1 || !r2)
 241             return 0;
 242           return r1 == 2 ? 2 : 1;
 243         }
 244       if (rd->flags == REL_AND)
 245         {
 246           int r2, r1 = solver_dep_fulfilled_alreadyinstalled(solv, rd->name);
 247           if (!r1)
 248             return 0;
 249           r2 = solver_dep_fulfilled_alreadyinstalled(solv, rd->evr);
 250           if (!r2)
 251             return 0;
 252           return r1 == 2 || r2 == 2 ? 2 : 1;
 253         }
 254       if (rd->flags == REL_OR)
 255         {
 256           int r2, r1 = solver_dep_fulfilled_alreadyinstalled(solv, rd->name);
 257           r2 = solver_dep_fulfilled_alreadyinstalled(solv, rd->evr);
 258           if (!r1 && !r2)
 259             return 0;
 260           return r1 == 2 || r2 == 2 ? 2 : 1;
 261         }
 262       if (rd->flags == REL_NAMESPACE && rd->name == NAMESPACE_SPLITPROVIDES)
 263         return solver_splitprovides(solv, rd->evr, 0) ? 2 : 0;
 264       if (rd->flags == REL_NAMESPACE && solv->installsuppdepq)
 265         {
 266           Queue *q = solv->installsuppdepq;
 267           int i;
 268           for (i = 0; i < q->count; i++)
 269             if (q->elements[i] == dep || q->elements[i] == rd->name)
 270               return 2;
 271         }
 272     }
 273   r = 0;
 274   FOR_PROVIDES(p, pp, dep)
 275     if (solv->decisionmap[p] > 0)
 276       {
 277         Solvable *s = pool->solvables + p;
 278         if (s->repo && s->repo != solv->installed)
 279           return 2;
 280         r = 1;
 281       }
 282   return r;
 283 }
 284
 285 int
 286 solver_is_supplementing_alreadyinstalled(Solver *solv, Solvable *s)
 287 {
 288   Id sup, *supp;
 289   supp = s->repo->idarraydata + s->supplements;
 290   while ((sup = *supp++) != 0)
 291     if (solver_dep_fulfilled_alreadyinstalled(solv, sup) == 2)
 292       return 1;
 293   return 0;
 294 }
 295 /*
 296  * add all installed packages that package p obsoletes to Queue q.
 297  * Package p is not installed. Also, we know that if
 298  * solv->keepexplicitobsoletes is not set, p is not in the multiversion map.
 299  * Entries may get added multiple times.
 300  */
 301 static void
 302 solver_add_obsoleted(Solver *solv, Id p, Queue *q)
 303 {
 304   Pool *pool = solv->pool;
 305   Repo *installed = solv->installed;
 306   Id p2, pp2;
 307   Solvable *s = pool->solvables + p;
 308   Id obs, *obsp;
 309   Id lastp2 = 0;
 310
 311   if (!solv->keepexplicitobsoletes || !(solv->multiversion.size && MAPTST(&solv->multiversion, p)))
 312     {
 313       FOR_PROVIDES(p2, pp2, s->name)
 314         {
 315           Solvable *ps = pool->solvables + p2;
 316           if (ps->repo != installed)
 317             continue;
 318           if (!pool->implicitobsoleteusesprovides && ps->name != s->name)
 319             continue;
 320           if (pool->implicitobsoleteusescolors && !pool_colormatch(pool, s, ps))
 321             continue;
 322           queue_push(q, p2);
 323           lastp2 = p2;
 324         }
 325     }
 326   if (!s->obsoletes)
 327     return;
 328   obsp = s->repo->idarraydata + s->obsoletes;
 329   while ((obs = *obsp++) != 0)
 330     FOR_PROVIDES(p2, pp2, obs)
 331       {
 332         Solvable *ps = pool->solvables + p2;
 333         if (ps->repo != installed)
 334           continue;
 335         if (!pool->obsoleteusesprovides && !pool_match_nevr(pool, ps, obs))
 336           continue;
 337         if (pool->obsoleteusescolors && !pool_colormatch(pool, s, ps))
 338           continue;
 339         if (p2 == lastp2)
 340           continue;
 341         queue_push(q, p2);
 342         lastp2 = p2;
 343       }
 344 }
 345
 346 /*
 347  * Call solver_add_obsoleted and intersect the result with the
 348  * elements in Queue q starting at qstart.
 349  * Assumes that it's the first call if qstart == q->count.
 350  * May use auxillary map m for the intersection process, all
 351  * elements of q starting at qstart must have their bit cleared.
 352  * (This is also true after the function returns.)
 353  * (See solver_add_obsoleted for limitations of the package p)
 354  */
 355 void
 356 solver_intersect_obsoleted(Solver *solv, Id p, Queue *q, int qstart, Map *m)
 357 {
 358   int i, j;
 359   int qcount = q->count;
 360
 361   solver_add_obsoleted(solv, p, q);
 362   if (qcount == qstart)
 363     return;     /* first call */
 364   if (qcount == q->count)
 365     j = qstart;
 366   else if (qcount == qstart + 1)
 367     {
 368       /* easy if there's just one element */
 369       j = qstart;
 370       for (i = qcount; i < q->count; i++)
 371         if (q->elements[i] == q->elements[qstart])
 372           {
 373             j++;        /* keep the element */
 374             break;
 375           }
 376     }
 377   else if (!m || (!m->size && q->count - qstart <= 8))
 378     {
 379       /* faster than a map most of the time */
 380       int k;
 381       for (i = j = qstart; i < qcount; i++)
 382         {
 383           Id ip = q->elements[i];
 384           for (k = qcount; k < q->count; k++)
 385             if (q->elements[k] == ip)
 386               {
 387                 q->elements[j++] = ip;
 388                 break;
 389               }
 390         }
 391     }
 392   else
 393     {
 394       /* for the really pathologic cases we use the map */
 395       Repo *installed = solv->installed;
 396       if (!m->size)
 397         map_init(m, installed->end - installed->start);
 398       for (i = qcount; i < q->count; i++)
 399         MAPSET(m, q->elements[i] - installed->start);
 400       for (i = j = qstart; i < qcount; i++)
 401         if (MAPTST(m, q->elements[i] - installed->start))
 402           {
 403             MAPCLR(m, q->elements[i] - installed->start);
 404             q->elements[j++] = q->elements[i];
 405           }
 406     }
 407   queue_truncate(q, j);
 408 }
 409