src/selection.c

   1 /*
   2  * Copyright (c) 2007, Novell Inc.
   3  *
   4  * This program is licensed under the BSD license, read LICENSE.BSD
   5  * for further information
   6  */
   7
   8 /*
   9  * selection.c
  10  *
  11  */
  12
  13 #define _GNU_SOURCE
  14 #include <string.h>
  15 #include <fnmatch.h>
  16
  17 #include <stdio.h>
  18 #include <stdlib.h>
  19 #include <unistd.h>
  20
  21 #include "selection.h"
  22 #include "solver.h"
  23
  24
  25 static int
  26 str2archid(Pool *pool, const char *arch)
  27 {
  28   Id id;
  29   if (!*arch)
  30     return 0;
  31   id = pool_str2id(pool, arch, 0);
  32   if (!id || id == ARCH_SRC || id == ARCH_NOSRC || id == ARCH_NOARCH)
  33     return id;
  34   if (pool->id2arch && (id > pool->lastarch || !pool->id2arch[id]))
  35     return 0;
  36   return id;
  37 }
  38
  39 static void
  40 selection_prune(Pool *pool, Queue *selection)
  41 {
  42   int i, j;
  43   Id p, pp;
  44   for (i = j = 0; i < selection->count; i += 2)
  45     {
  46       Id select = selection->elements[i] & SOLVER_SELECTMASK;
  47       p = 0;
  48       if (select == SOLVER_SOLVABLE_ALL)
  49         p = 1;
  50       else if (select == SOLVER_SOLVABLE_REPO)
  51         {
  52           Solvable *s;
  53           Repo *repo = pool_id2repo(pool, selection->elements[i + 1]);
  54           if (repo)
  55             FOR_REPO_SOLVABLES(repo, p, s)
  56               break;
  57         }
  58       else
  59         {
  60           FOR_JOB_SELECT(p, pp, select, selection->elements[i + 1])
  61             break;
  62         }
  63       if (!p)
  64         continue;
  65       selection->elements[j] = selection->elements[i];
  66       selection->elements[j + 1] = selection->elements[i + 1];
  67       j += 2;
  68     }
  69   queue_truncate(selection, j);
  70 }
  71
  72
  73 static int
  74 selection_solvables_sortcmp(const void *ap, const void *bp, void *dp)
  75 {
  76   return *(const Id *)ap - *(const Id *)bp;
  77 }
  78
  79 void
  80 selection_solvables(Pool *pool, Queue *selection, Queue *pkgs)
  81 {
  82   int i, j;
  83   Id p, pp, lastid;
  84   queue_empty(pkgs);
  85   for (i = 0; i < selection->count; i += 2)
  86     {
  87       Id select = selection->elements[i] & SOLVER_SELECTMASK;
  88       if (select == SOLVER_SOLVABLE_ALL)
  89         {
  90           FOR_POOL_SOLVABLES(p)
  91             queue_push(pkgs, p);
  92         }
  93       if (select == SOLVER_SOLVABLE_REPO)
  94         {
  95           Solvable *s;
  96           Repo *repo = pool_id2repo(pool, selection->elements[i + 1]);
  97           if (repo)
  98             FOR_REPO_SOLVABLES(repo, p, s)
  99               queue_push(pkgs, p);
 100         }
 101       else
 102         {
 103           FOR_JOB_SELECT(p, pp, select, selection->elements[i + 1])
 104             queue_push(pkgs, p);
 105         }
 106     }
 107   if (pkgs->count < 2)
 108     return;
 109   /* sort and unify */
 110   solv_sort(pkgs->elements, pkgs->count, sizeof(Id), selection_solvables_sortcmp, NULL);
 111   lastid = pkgs->elements[0];
 112   for (i = j = 1; i < pkgs->count; i++)
 113     if (pkgs->elements[i] != lastid)
 114       pkgs->elements[j++] = lastid = pkgs->elements[i];
 115   queue_truncate(pkgs, j);
 116 }
 117
 118 static void
 119 selection_flatten(Pool *pool, Queue *selection)
 120 {
 121   Queue q;
 122   int i;
 123   if (selection->count <= 1)
 124     return;
 125   for (i = 0; i < selection->count; i += 2)
 126     if ((selection->elements[i] & SOLVER_SELECTMASK) == SOLVER_SOLVABLE_ALL)
 127       {
 128         selection->elements[0] = selection->elements[i];
 129         selection->elements[1] = selection->elements[i + 1];
 130         queue_truncate(selection, 2);
 131         return;
 132       }
 133   queue_init(&q);
 134   selection_solvables(pool, selection, &q);
 135   if (!q.count)
 136     {
 137       queue_empty(selection);
 138       return;
 139     }
 140   queue_truncate(selection, 2);
 141   if (q.count > 1)
 142     {
 143       selection->elements[0] = SOLVER_SOLVABLE_ONE_OF;
 144       selection->elements[1] = pool_queuetowhatprovides(pool, &q);
 145     }
 146   else
 147     {
 148       selection->elements[0] = SOLVER_SOLVABLE | SOLVER_NOAUTOSET;
 149       selection->elements[1] = q.elements[0];
 150     }
 151 }
 152
 153 static void
 154 selection_limit_rel(Pool *pool, Queue *selection, Id flags, Id evr)
 155 {
 156   int i, j;
 157   for (i = j = 0; i < selection->count; i += 2)
 158     {
 159       Id select = selection->elements[i] & SOLVER_SELECTMASK;
 160       if (select != SOLVER_SOLVABLE_NAME && select != SOLVER_SOLVABLE_PROVIDES)
 161         continue;       /* actually internal error */
 162       selection->elements[i + 1] = pool_rel2id(pool, selection->elements[i + 1], evr, flags, 1);
 163       if (flags == REL_ARCH)
 164         selection->elements[i] |= SOLVER_SETARCH;
 165       if (flags == REL_EQ && select == SOLVER_SOLVABLE_NAME && selection->elements[i])
 166         {
 167           if (pool->disttype == DISTTYPE_DEB)
 168             selection->elements[i] |= SOLVER_SETEVR;    /* debian can't match version only like rpm */
 169           else
 170             selection->elements[i] |= strchr(pool_id2str(pool, evr), '-') != 0 ? SOLVER_SETEVR : SOLVER_SETEV;
 171         }
 172     }
 173   selection_prune(pool, selection);
 174 }
 175
 176 static int
 177 selection_depglob(Pool *pool, Queue *selection, const char *name, int flags)
 178 {
 179   Id id, p, pp;
 180   int i, match = 0;
 181   int doglob = 0;
 182   int globflags = 0;
 183
 184   if (!(flags & (SELECTION_NAME|SELECTION_PROVIDES)))
 185     return 0;
 186
 187   if ((flags & SELECTION_INSTALLED_ONLY) != 0 && !pool->installed)
 188     return 0;
 189
 190   if (!(flags & SELECTION_NOCASE))
 191     {
 192       id = pool_str2id(pool, name, 0);
 193       if (id)
 194         {
 195           FOR_PROVIDES(p, pp, id)
 196             {
 197               Solvable *s = pool->solvables + p;
 198               if ((flags & SELECTION_INSTALLED_ONLY) != 0 && s->repo != pool->installed)
 199                 continue;
 200               match = 1;
 201               if (s->name == id && (flags & SELECTION_NAME) != 0)
 202                 {
 203                   queue_push2(selection, SOLVER_SOLVABLE_NAME, id);
 204                   return SELECTION_NAME;
 205                 }
 206             }
 207           if (match && (flags & SELECTION_PROVIDES) != 0)
 208             {
 209               queue_push2(selection, SOLVER_SOLVABLE_PROVIDES, id);
 210               return SELECTION_PROVIDES;
 211             }
 212         }
 213     }
 214
 215   if ((flags & SELECTION_GLOB) != 0 && strpbrk(name, "[*?") != 0)
 216     doglob = 1;
 217
 218   if (!doglob && !(flags & SELECTION_NOCASE))
 219     return 0;
 220
 221   if (doglob && (flags & SELECTION_NOCASE) != 0)
 222     globflags = FNM_CASEFOLD;
 223
 224 #if 0   /* doesn't work with selection_limit_rel yet */
 225   if (doglob && !strcmp(name, "*") && (flags & SELECTION_FLAT) != 0)
 226     {
 227       /* can't do this for SELECTION_PROVIDES, as src rpms don't provide anything */
 228       if ((flags & SELECTION_NAME) != 0)
 229         {
 230           queue_push2(selection, SOLVER_SOLVABLE_ALL, 0);
 231           return SELECTION_NAME;
 232         }
 233     }
 234 #endif
 235
 236   if ((flags & SELECTION_NAME) != 0)
 237     {
 238       /* looks like a name glob. hard work. */
 239       for (p = 1; p < pool->nsolvables; p++)
 240         {
 241           Solvable *s = pool->solvables + p;
 242           if (!s->repo || !pool_installable(pool, s))
 243             continue;
 244           if ((flags & SELECTION_INSTALLED_ONLY) != 0 && s->repo != pool->installed)
 245             continue;
 246           id = s->name;
 247           if ((doglob ? fnmatch(name, pool_id2str(pool, id), globflags) : strcasecmp(name, pool_id2str(pool, id))) == 0)
 248             {
 249               for (i = 0; i < selection->count; i += 2)
 250                 if (selection->elements[i] == SOLVER_SOLVABLE_NAME && selection->elements[i + 1] == id)
 251                   break;
 252               if (i == selection->count)
 253                 queue_push2(selection, SOLVER_SOLVABLE_NAME, id);
 254               match = 1;
 255             }
 256         }
 257       if (match)
 258         return SELECTION_NAME;
 259     }
 260   if ((flags & SELECTION_PROVIDES))
 261     {
 262       /* looks like a dep glob. really hard work. */
 263       for (id = 1; id < pool->ss.nstrings; id++)
 264         {
 265           if (!pool->whatprovides[id])
 266             continue;
 267           if ((doglob ? fnmatch(name, pool_id2str(pool, id), globflags) : strcasecmp(name, pool_id2str(pool, id))) == 0)
 268             {
 269               if ((flags & SELECTION_INSTALLED_ONLY) != 0)
 270                 {
 271                   FOR_PROVIDES(p, pp, id)
 272                     if (pool->solvables[p].repo == pool->installed)
 273                       break;
 274                   if (!p)
 275                     continue;
 276                 }
 277               queue_push2(selection, SOLVER_SOLVABLE_PROVIDES, id);
 278               match = 1;
 279             }
 280         }
 281       if (match)
 282         return SELECTION_PROVIDES;
 283     }
 284   return 0;
 285 }
 286
 287 static int
 288 selection_depglob_arch(Pool *pool, Queue *selection, const char *name, int flags)
 289 {
 290   int ret;
 291   const char *r;
 292   Id archid;
 293
 294   if ((ret = selection_depglob(pool, selection, name, flags)) != 0)
 295     return ret;
 296   /* check if theres an .arch suffix */
 297   if ((r = strrchr(name, '.')) != 0 && r[1] && (archid = str2archid(pool, r + 1)) != 0)
 298     {
 299       char *rname = solv_strdup(name);
 300       rname[r - name] = 0;
 301       if ((ret = selection_depglob(pool, selection, rname, flags)) != 0)
 302         {
 303           selection_limit_rel(pool, selection, REL_ARCH, archid);
 304           solv_free(rname);
 305           return ret;
 306         }
 307       solv_free(rname);
 308     }
 309   return 0;
 310 }
 311
 312 static int
 313 selection_filelist(Pool *pool, Queue *selection, const char *name, int flags)
 314 {
 315   Dataiterator di;
 316   Queue q;
 317   int type;
 318
 319   type = !(flags & SELECTION_GLOB) || strpbrk(name, "[*?") == 0 ? SEARCH_STRING : SEARCH_GLOB;
 320   if ((flags & SELECTION_NOCASE) != 0)
 321     type |= SEARCH_NOCASE;
 322   queue_init(&q);
 323   dataiterator_init(&di, pool, flags & SELECTION_INSTALLED_ONLY ? pool->installed : 0, 0, SOLVABLE_FILELIST, name, type|SEARCH_FILES|SEARCH_COMPLETE_FILELIST);
 324   while (dataiterator_step(&di))
 325     {
 326       Solvable *s = pool->solvables + di.solvid;
 327       if (!s->repo || !pool_installable(pool, s))
 328         continue;
 329       queue_push(&q, di.solvid);
 330       dataiterator_skip_solvable(&di);
 331     }
 332   dataiterator_free(&di);
 333   if (!q.count)
 334     return 0;
 335   if (q.count > 1)
 336     queue_push2(selection, SOLVER_SOLVABLE_ONE_OF, pool_queuetowhatprovides(pool, &q));
 337   else
 338     queue_push2(selection, SOLVER_SOLVABLE | SOLVER_NOAUTOSET, q.elements[0]);
 339   queue_free(&q);
 340   return SELECTION_FILELIST;
 341 }
 342
 343 static int
 344 selection_rel(Pool *pool, Queue *selection, const char *name, int flags)
 345 {
 346   int ret, rflags = 0;
 347   char *r, *rname;
 348
 349   /* relation case, support:
 350    * depglob rel
 351    * depglob.arch rel
 352    */
 353   rname = solv_strdup(name);
 354   if ((r = strpbrk(rname, "<=>")) != 0)
 355     {
 356       int nend = r - rname;
 357       for (; *r; r++)
 358         {
 359           if (*r == '<')
 360             rflags |= REL_LT;
 361           else if (*r == '=')
 362             rflags |= REL_EQ;
 363           else if (*r == '>')
 364             rflags |= REL_GT;
 365           else
 366             break;
 367         }
 368       while (*r && *r == ' ' && *r == '\t')
 369         r++;
 370       while (nend && (rname[nend - 1] == ' ' || rname[nend -1 ] == '\t'))
 371         nend--;
 372       if (!*rname || !*r)
 373         {
 374           solv_free(rname);
 375           return 0;
 376         }
 377       rname[nend] = 0;
 378     }
 379   if ((ret = selection_depglob_arch(pool, selection, rname, flags)) != 0)
 380     {
 381       if (rflags)
 382         selection_limit_rel(pool, selection, rflags, pool_str2id(pool, r, 1));
 383       solv_free(rname);
 384       return ret;
 385     }
 386   solv_free(rname);
 387   return 0;
 388 }
 389
 390 static int
 391 selection_nevra(Pool *pool, Queue *selection, const char *name, int flags)
 392 {
 393   char *rname, *r, *r2;
 394   Id archid = 0;
 395   int ret;
 396
 397   /*
 398    * nameglob-version
 399    * nameglob-version.arch
 400    * nameglob-version-release
 401    * nameglob-version-release.arch
 402    */
 403   flags |= SELECTION_NAME;
 404   flags &= ~SELECTION_PROVIDES;
 405
 406   if (pool->disttype == DISTTYPE_DEB)
 407     {
 408       if ((r = strchr(name, '_')) == 0)
 409         return 0;
 410       rname = solv_strdup(name);        /* so we can modify it */
 411       r = rname + (r - name);
 412       *r++ = 0;
 413       if ((ret = selection_depglob(pool, selection, rname, flags)) == 0)
 414         {
 415           solv_free(rname);
 416           return 0;
 417         }
 418       /* is there a vaild arch? */
 419       if ((r2 = strchr(r, '_')) != 0 && r[1] && (archid = str2archid(pool, r + 1)) != 0)
 420         {
 421           *r2 = 0;      /* split off */
 422           selection_limit_rel(pool, selection, REL_ARCH, archid);
 423         }
 424       selection_limit_rel(pool, selection, flags, pool_str2id(pool, r, 1));
 425       solv_free(rname);
 426       return ret;
 427     }
 428
 429   if ((r = strrchr(name, '-')) == 0)
 430     return 0;
 431   rname = solv_strdup(name);    /* so we can modify it */
 432   r = rname + (r - name);
 433   *r = 0;
 434   /* try with just the version */
 435   if ((ret = selection_depglob(pool, selection, rname, flags)) == 0)
 436     {
 437       /* no luck, try with version-release */
 438       if ((r2 = strrchr(rname, '-')) == 0)
 439         {
 440           solv_free(rname);
 441           return 0;
 442         }
 443       *r = '-';
 444       *r2 = 0;
 445       r = r2;
 446       if ((ret = selection_depglob(pool, selection, rname, flags)) == 0)
 447         {
 448           solv_free(rname);
 449           return 0;
 450         }
 451     }
 452   /* we now know the name, check if we need to split of the arch */
 453   r++;
 454   if ((r2 = strrchr(r, '.')) != 0 && r2[1] && (archid = str2archid(pool, r2 + 1)) != 0)
 455     {
 456       /* found valid arch, split it off */
 457       *r2 = 0;
 458       selection_limit_rel(pool, selection, REL_ARCH, archid);
 459     }
 460   selection_limit_rel(pool, selection, REL_EQ, pool_str2id(pool, r, 1));
 461   solv_free(rname);
 462   return ret;
 463 }
 464
 465 int
 466 selection_make(Pool *pool, Queue *selection, const char *name, int flags)
 467 {
 468   int ret = 0;
 469   const char *r;
 470
 471   queue_empty(selection);
 472   if (*name == '/' && (flags & SELECTION_FILELIST))
 473     ret = selection_filelist(pool, selection, name, flags);
 474   if (!ret && (r = strpbrk(name, "<=>")) != 0)
 475     ret = selection_rel(pool, selection, name, flags);
 476   if (!ret)
 477     ret = selection_depglob_arch(pool, selection, name, flags);
 478   if (!ret && (flags & SELECTION_NAME) != 0)
 479     ret = selection_nevra(pool, selection, name, flags);
 480   if (ret && (flags & SELECTION_FLAT) != 0)
 481     selection_flatten(pool, selection);
 482   return ret;
 483 }
 484
 485 void
 486 selection_limit(Pool *pool, Queue *sel1, Queue *sel2)
 487 {
 488   int i, j, miss;
 489   Id p, pp;
 490   Queue q1;
 491   Map m2;
 492   Id setflags = 0;
 493
 494   if (!sel1->count || !sel2->count)
 495     {
 496       queue_empty(sel1);
 497       return;
 498     }
 499   if (sel1->count == 2 && (sel1->elements[0] & SOLVER_SELECTMASK) == SOLVER_SOLVABLE_ALL)
 500     {
 501       /* XXX: not 100% correct, but very useful */
 502       queue_free(sel1);
 503       queue_init_clone(sel1, sel2);
 504       return;
 505     }
 506   queue_init(&q1);
 507   map_init(&m2, pool->nsolvables);
 508   for (i = 0; i < sel2->count; i += 2)
 509     {
 510       Id select = sel2->elements[i] & SOLVER_SELECTMASK;
 511       if (select == SOLVER_SOLVABLE_ALL)
 512         return;
 513       if (select == SOLVER_SOLVABLE_REPO)
 514         {
 515           Solvable *s;
 516           Repo *repo = pool_id2repo(pool, sel2->elements[i + 1]);
 517           if (repo)
 518             FOR_REPO_SOLVABLES(repo, p, s)
 519               map_set(&m2, p);
 520         }
 521       else
 522         {
 523           FOR_JOB_SELECT(p, pp, select, sel2->elements[i + 1])
 524             map_set(&m2, p);
 525         }
 526     }
 527   if (sel2->count == 2)         /* XXX: AND all setmasks instead? */
 528     setflags = sel2->elements[0] & SOLVER_SETMASK & ~SOLVER_NOAUTOSET;
 529   for (i = j = 0; i < sel1->count; i += 2)
 530     {
 531       Id select = sel1->elements[i] & SOLVER_SELECTMASK;
 532       queue_empty(&q1);
 533       miss = 0;
 534       if (select == SOLVER_SOLVABLE_ALL)
 535         {
 536           FOR_POOL_SOLVABLES(p)
 537             {
 538               if (map_tst(&m2, p))
 539                 queue_push(&q1, p);
 540               else
 541                 miss = 1;
 542             }
 543         }
 544       else if (select == SOLVER_SOLVABLE_REPO)
 545         {
 546           Solvable *s;
 547           Repo *repo = pool_id2repo(pool, sel1->elements[i + 1]);
 548           if (repo)
 549             FOR_REPO_SOLVABLES(repo, p, s)
 550               {
 551                 if (map_tst(&m2, p))
 552                   queue_push(&q1, p);
 553                 else
 554                   miss = 1;
 555               }
 556         }
 557       else
 558         {
 559           FOR_JOB_SELECT(p, pp, select, sel1->elements[i + 1])
 560             {
 561               if (map_tst(&m2, p))
 562                 queue_pushunique(&q1, p);
 563               else
 564                 miss = 1;
 565             }
 566         }
 567       if (!q1.count)
 568         continue;
 569       if (!miss)
 570         {
 571           sel1->elements[j] = sel1->elements[i] | setflags;
 572           sel1->elements[j + 1] = sel1->elements[i + 1];
 573         }
 574       else if (q1.count > 1)
 575         {
 576           sel1->elements[j] = (sel1->elements[i] & ~SOLVER_SELECTMASK) | SOLVER_SOLVABLE_ONE_OF | setflags;
 577           sel1->elements[j + 1] = pool_queuetowhatprovides(pool, &q1);
 578         }
 579       else
 580         {
 581           sel1->elements[j] = (sel1->elements[i] & ~SOLVER_SELECTMASK) | SOLVER_SOLVABLE | SOLVER_NOAUTOSET | setflags;
 582           sel1->elements[j + 1] = q1.elements[0];
 583         }
 584       j += 2;
 585     }
 586   queue_truncate(sel1, j);
 587 }
 588
 589 void
 590 selection_add(Pool *pool, Queue *sel1, Queue *sel2)
 591 {
 592   int i;
 593   for (i = 0; i < sel2->count; i++)
 594     queue_push(sel1, sel2->elements[i]);
 595 }
 596