src/selection.c

   1 /*
   2  * Copyright (c) 2012, 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 #include "evr.h"
  24
  25
  26 static int
  27 str2archid(Pool *pool, const char *arch)
  28 {
  29   Id id;
  30   if (!*arch)
  31     return 0;
  32   id = pool_str2id(pool, arch, 0);
  33   if (!id || id == ARCH_SRC || id == ARCH_NOSRC || id == ARCH_NOARCH)
  34     return id;
  35   if (pool->id2arch && pool_arch2score(pool, id) == 0)
  36     return 0;
  37   return id;
  38 }
  39
  40 /* remove empty jobs from the selection */
  41 static void
  42 selection_prune(Pool *pool, Queue *selection)
  43 {
  44   int i, j;
  45   Id p, pp;
  46   for (i = j = 0; i < selection->count; i += 2)
  47     {
  48       Id select = selection->elements[i] & SOLVER_SELECTMASK;
  49       p = 0;
  50       if (select == SOLVER_SOLVABLE_ALL)
  51         p = 1;
  52       else if (select == SOLVER_SOLVABLE_REPO)
  53         {
  54           Solvable *s;
  55           Repo *repo = pool_id2repo(pool, selection->elements[i + 1]);
  56           if (repo)
  57             {
  58               FOR_REPO_SOLVABLES(repo, p, s)
  59                 break;
  60             }
  61         }
  62       else
  63         {
  64           FOR_JOB_SELECT(p, pp, select, selection->elements[i + 1])
  65             break;
  66         }
  67       if (!p)
  68         continue;
  69       selection->elements[j] = selection->elements[i];
  70       selection->elements[j + 1] = selection->elements[i + 1];
  71       j += 2;
  72     }
  73   queue_truncate(selection, j);
  74 }
  75
  76
  77 static int
  78 selection_solvables_sortcmp(const void *ap, const void *bp, void *dp)
  79 {
  80   return *(const Id *)ap - *(const Id *)bp;
  81 }
  82
  83 void
  84 selection_solvables(Pool *pool, Queue *selection, Queue *pkgs)
  85 {
  86   int i, j;
  87   Id p, pp, lastid;
  88   queue_empty(pkgs);
  89   for (i = 0; i < selection->count; i += 2)
  90     {
  91       Id select = selection->elements[i] & SOLVER_SELECTMASK;
  92       if (select == SOLVER_SOLVABLE_ALL)
  93         {
  94           FOR_POOL_SOLVABLES(p)
  95             queue_push(pkgs, p);
  96         }
  97       if (select == SOLVER_SOLVABLE_REPO)
  98         {
  99           Solvable *s;
 100           Repo *repo = pool_id2repo(pool, selection->elements[i + 1]);
 101           if (repo)
 102             {
 103               FOR_REPO_SOLVABLES(repo, p, s)
 104                 queue_push(pkgs, p);
 105             }
 106         }
 107       else
 108         {
 109           FOR_JOB_SELECT(p, pp, select, selection->elements[i + 1])
 110             queue_push(pkgs, p);
 111         }
 112     }
 113   if (pkgs->count < 2)
 114     return;
 115   /* sort and unify */
 116   solv_sort(pkgs->elements, pkgs->count, sizeof(Id), selection_solvables_sortcmp, NULL);
 117   lastid = pkgs->elements[0];
 118   for (i = j = 1; i < pkgs->count; i++)
 119     if (pkgs->elements[i] != lastid)
 120       pkgs->elements[j++] = lastid = pkgs->elements[i];
 121   queue_truncate(pkgs, j);
 122 }
 123
 124 static void
 125 selection_flatten(Pool *pool, Queue *selection)
 126 {
 127   Queue q;
 128   int i;
 129   if (selection->count <= 2)
 130     return;
 131   for (i = 0; i < selection->count; i += 2)
 132     if ((selection->elements[i] & SOLVER_SELECTMASK) == SOLVER_SOLVABLE_ALL)
 133       {
 134         selection->elements[0] = selection->elements[i];
 135         selection->elements[1] = selection->elements[i + 1];
 136         queue_truncate(selection, 2);
 137         return;
 138       }
 139   queue_init(&q);
 140   selection_solvables(pool, selection, &q);
 141   if (!q.count)
 142     {
 143       queue_empty(selection);
 144       return;
 145     }
 146   queue_truncate(selection, 2);
 147   if (q.count > 1)
 148     {
 149       selection->elements[0] = SOLVER_SOLVABLE_ONE_OF;
 150       selection->elements[1] = pool_queuetowhatprovides(pool, &q);
 151     }
 152   else
 153     {
 154       selection->elements[0] = SOLVER_SOLVABLE | SOLVER_NOAUTOSET;
 155       selection->elements[1] = q.elements[0];
 156     }
 157 }
 158
 159 /* only supports simple rels plus REL_ARCH */
 160 static int
 161 match_nevr_rel(Pool *pool, Solvable *s, Id rflags, Id revr)
 162 {
 163   if (rflags == REL_ARCH)
 164     {
 165       if (s->arch != revr)
 166         {
 167           if (revr != ARCH_SRC || s->arch != ARCH_NOSRC)
 168             return 0;
 169         }
 170       return 1;
 171     }
 172   if (rflags > 7)
 173     return 0;
 174   return pool_intersect_evrs(pool, REL_EQ, s->evr, rflags, revr);
 175 }
 176
 177 /* only supports simple rels plus REL_ARCH */
 178 static void
 179 selection_filter_rel_noprune(Pool *pool, Queue *selection, Id relflags, Id relevr)
 180 {
 181   int i;
 182
 183   if (!selection->count)
 184     return;
 185
 186   for (i = 0; i < selection->count; i += 2)
 187     {
 188       Id select = selection->elements[i] & SOLVER_SELECTMASK;
 189       Id id = selection->elements[i + 1];
 190       if (select == SOLVER_SOLVABLE || select == SOLVER_SOLVABLE_ONE_OF)
 191         {
 192           /* done by selection_addextra, currently implies SELECTION_NAME */
 193           Queue q;
 194           Id p, pp;
 195           int miss = 0;
 196
 197           queue_init(&q);
 198           FOR_JOB_SELECT(p, pp, select, id)
 199             {
 200               Solvable *s = pool->solvables + p;
 201               if (match_nevr_rel(pool, s, relflags, relevr))
 202                 queue_push(&q, p);
 203               else
 204                 miss = 1;
 205             }
 206           if (miss)
 207             {
 208               if (q.count == 1)
 209                 {
 210                   selection->elements[i] = SOLVER_SOLVABLE | SOLVER_NOAUTOSET;
 211                   selection->elements[i + 1] = q.elements[0];
 212                 }
 213               else
 214                 {
 215                   selection->elements[i] = SOLVER_SOLVABLE_ONE_OF;
 216                   selection->elements[i + 1] = pool_queuetowhatprovides(pool, &q);
 217                 }
 218             }
 219           queue_free(&q);
 220         }
 221       else if (select == SOLVER_SOLVABLE_NAME || select == SOLVER_SOLVABLE_PROVIDES)
 222         {
 223           /* don't stack src reldeps */
 224           if (relflags == REL_ARCH && (relevr == ARCH_SRC || relevr == ARCH_NOSRC) && ISRELDEP(id))
 225             {
 226               Reldep *rd = GETRELDEP(pool, id);
 227               if (rd->flags == REL_ARCH && rd->evr == ARCH_SRC)
 228                 id = rd->name;
 229             }
 230           selection->elements[i + 1] = pool_rel2id(pool, id, relevr, relflags, 1);
 231         }
 232       else
 233         continue;       /* actually cannot happen */
 234
 235       /* now add the setflags we gained */
 236       if (relflags == REL_ARCH)
 237         selection->elements[i] |= SOLVER_SETARCH;
 238       if (relflags == REL_EQ && select != SOLVER_SOLVABLE_PROVIDES)
 239         {
 240           if (pool->disttype == DISTTYPE_DEB)
 241             selection->elements[i] |= SOLVER_SETEVR;    /* debian can't match version only like rpm */
 242           else
 243             {
 244               const char *rel =  strrchr(pool_id2str(pool, relevr), '-');
 245               selection->elements[i] |= rel ? SOLVER_SETEVR : SOLVER_SETEV;
 246             }
 247         }
 248     }
 249 }
 250
 251 /* only supports simple rels plus REL_ARCH */
 252 /* prunes empty jobs */
 253 static void
 254 selection_filter_rel(Pool *pool, Queue *selection, Id relflags, Id relevr)
 255 {
 256   selection_filter_rel_noprune(pool, selection, relflags, relevr);
 257   selection_prune(pool, selection);
 258 }
 259
 260 /* limit a selection to to repository */
 261 /* prunes empty jobs */
 262 static void
 263 selection_filter_repo(Pool *pool, Queue *selection, Repo *repo)
 264 {
 265   Queue q;
 266   int i, j;
 267
 268   if (!selection->count)
 269     return;
 270   if (!repo)
 271     {
 272       queue_empty(selection);
 273       return;
 274     }
 275   queue_init(&q);
 276   for (i = j = 0; i < selection->count; i += 2)
 277     {
 278       Id select = selection->elements[i] & SOLVER_SELECTMASK;
 279       Id id = selection->elements[i + 1];
 280       if (select == SOLVER_SOLVABLE_ALL)
 281         {
 282           select = SOLVER_SOLVABLE_REPO;
 283           id = repo->repoid;
 284         }
 285       else if (select == SOLVER_SOLVABLE_REPO)
 286         {
 287           if (id != repo->repoid)
 288             select = 0;
 289         }
 290       else
 291         {
 292           int bad = 0;
 293           Id p, pp;
 294           queue_empty(&q);
 295           FOR_JOB_SELECT(p, pp, select, id)
 296             {
 297               if (pool->solvables[p].repo != repo)
 298                 bad = 1;
 299               else
 300                 queue_push(&q, p);
 301             }
 302           if (bad || !q.count)
 303             {
 304               if (!q.count)
 305                 select = 0;             /* prune empty jobs */
 306               else if (q.count == 1)
 307                 {
 308                   select = SOLVER_SOLVABLE | SOLVER_NOAUTOSET;
 309                   id = q.elements[0];
 310                 }
 311               else
 312                 {
 313                   select = SOLVER_SOLVABLE_ONE_OF;
 314                   id = pool_queuetowhatprovides(pool, &q);
 315                 }
 316             }
 317         }
 318       if (!select)
 319         continue;       /* job is now empty */
 320       if (select == SOLVER_SOLVABLE_REPO)
 321         {
 322           Id p;
 323           Solvable *s;
 324           FOR_REPO_SOLVABLES(repo, p, s)
 325             break;
 326           if (!p)
 327             continue;   /* repo is empty */
 328         }
 329       selection->elements[j++] = select | (selection->elements[i] & ~SOLVER_SELECTMASK) | SOLVER_SETREPO;
 330       selection->elements[j++] = id;
 331     }
 332   queue_truncate(selection, j);
 333   queue_free(&q);
 334 }
 335
 336
 337 static int
 338 matchprovides(Pool *pool, Solvable *s, Id dep)
 339 {
 340   Id id, *idp;
 341   idp = s->repo->idarraydata + s->provides;
 342   while ((id = *idp++) != 0)
 343     if (pool_match_dep(pool, id, dep))
 344       return 1;
 345   return 0;
 346 }
 347
 348 /* change a SOLVER_SOLVABLE_NAME/PROVIDES selection to something that also includes
 349  * extra packages.
 350  * extra packages are: src, badarch, disabled
 351  */
 352 static void
 353 selection_addextra(Pool *pool, Queue *selection, int flags)
 354 {
 355   Queue q;
 356   Id p, pp, dep;
 357   int i, isextra, haveextra, doprovides;
 358
 359   if ((flags & SELECTION_INSTALLED_ONLY) != 0)
 360     flags &= ~SELECTION_WITH_SOURCE;
 361
 362   if (!(flags & (SELECTION_WITH_SOURCE | SELECTION_WITH_DISABLED | SELECTION_WITH_BADARCH)))
 363     return;     /* nothing to add */
 364
 365   queue_init(&q);
 366   for (i = 0; i < selection->count; i += 2)
 367     {
 368       if (selection->elements[i] == SOLVER_SOLVABLE_NAME)
 369         doprovides = 0;
 370       else if (selection->elements[i] == SOLVER_SOLVABLE_PROVIDES)
 371         doprovides = 1;
 372       else
 373         continue;
 374       dep = selection->elements[i + 1];
 375       haveextra = 0;
 376       queue_empty(&q);
 377       if (doprovides)
 378         {
 379           /* first put all non-extra packages on the queue */
 380           FOR_PROVIDES(p, pp, dep)
 381             {
 382               if ((flags & SELECTION_INSTALLED_ONLY) != 0 && pool->solvables[p].repo != pool->installed)
 383                 continue;
 384               queue_push(&q, p);
 385             }
 386         }
 387       FOR_POOL_SOLVABLES(p)
 388         {
 389           Solvable *s = pool->solvables + p;
 390           if (!doprovides && !pool_match_nevr(pool, s, dep))
 391             continue;
 392           if ((flags & SELECTION_INSTALLED_ONLY) != 0 && s->repo != pool->installed)
 393             continue;
 394           isextra = 0;
 395           if (s->arch == ARCH_SRC || s->arch == ARCH_NOSRC)
 396             {
 397               if (!(flags & SELECTION_WITH_SOURCE) && !(flags & SELECTION_SOURCE_ONLY))
 398                 continue;
 399               if (!(flags & SELECTION_SOURCE_ONLY))
 400                 isextra = 1;
 401               if (pool_disabled_solvable(pool, s))
 402                 {
 403                   if (!(flags & SELECTION_WITH_DISABLED))
 404                     continue;
 405                   isextra = 1;
 406                 }
 407             }
 408           else
 409             {
 410               if ((flags & SELECTION_SOURCE_ONLY) != 0)
 411                 continue;
 412               if (s->repo != pool->installed)
 413                 {
 414                   if (pool_disabled_solvable(pool, s))
 415                     {
 416                       if (!(flags & SELECTION_WITH_DISABLED))
 417                         continue;
 418                       isextra = 1;
 419                     }
 420                   if (pool_badarch_solvable(pool, s))
 421                     {
 422                       if (!(flags & SELECTION_WITH_BADARCH))
 423                         continue;
 424                       isextra = 1;
 425                     }
 426                 }
 427             }
 428           if (doprovides)
 429             {
 430               if (!isextra)
 431                 continue;       /* already done above in FOR_PROVIDES */
 432               if (!s->provides || !matchprovides(pool, s, dep))
 433                 continue;
 434             }
 435           haveextra |= isextra;
 436           queue_push(&q, p);
 437         }
 438       if (!haveextra || !q.count)
 439         continue;
 440       if (q.count == 1)
 441         {
 442           selection->elements[i] = (selection->elements[i] & ~SOLVER_SELECTMASK) | SOLVER_SOLVABLE | SOLVER_NOAUTOSET;
 443           selection->elements[i + 1] = q.elements[0];
 444         }
 445       else
 446         {
 447           if (doprovides)
 448             solv_sort(q.elements, q.count, sizeof(Id), selection_solvables_sortcmp, NULL);
 449           selection->elements[i] = (selection->elements[i] & ~SOLVER_SELECTMASK) | SOLVER_SOLVABLE_ONE_OF;
 450           selection->elements[i + 1] = pool_queuetowhatprovides(pool, &q);
 451         }
 452     }
 453   queue_free(&q);
 454 }
 455
 456 static inline const char *
 457 skipkind(const char *n)
 458 {
 459   const char *s;
 460   for (s = n; *s >= 'a' && *s <= 'z'; s++)
 461     ;
 462   if (*s == ':' && s != n)
 463      return s + 1;
 464   return n;
 465 }
 466
 467 static inline void
 468 queue_pushunique2(Queue *q, Id id1, Id id2)
 469 {
 470   int i;
 471   for (i = 0; i < q->count; i += 2)
 472     if (q->elements[i] == id1 && q->elements[i + 1] == id2)
 473       return;
 474   queue_push2(q, id1, id2);
 475 }
 476
 477
 478 /*****  provides matching  *****/
 479
 480 static int
 481 selection_addextra_provides(Pool *pool, Queue *selection, const char *name, int flags)
 482 {
 483   Id p, id, *idp;
 484   int match = 0;
 485   int doglob, nocase, globflags;
 486
 487   if ((flags & SELECTION_INSTALLED_ONLY) != 0)
 488     return 0;   /* neither disabled nor badarch nor src */
 489
 490   nocase = flags & SELECTION_NOCASE;
 491   doglob = (flags & SELECTION_GLOB) != 0 && strpbrk(name, "[*?") != 0;
 492   globflags = doglob && nocase ? FNM_CASEFOLD : 0;
 493
 494   FOR_POOL_SOLVABLES(p)
 495     {
 496       const char *n;
 497       Solvable *s = pool->solvables + p;
 498       if (!s->provides)
 499         continue;
 500       if (s->arch == ARCH_SRC || s->arch == ARCH_NOSRC) /* no provides */
 501         continue;
 502       if (s->repo == pool->installed)
 503         continue;
 504       if (pool_disabled_solvable(pool, s))
 505         {
 506           if (!(flags & SELECTION_WITH_DISABLED))
 507             continue;
 508           if (!(flags & SELECTION_WITH_BADARCH) && pool_badarch_solvable(pool, s))
 509             continue;
 510         }
 511       else if (pool_badarch_solvable(pool, s))
 512         {
 513           if (!(flags & SELECTION_WITH_BADARCH))
 514             continue;
 515         }
 516       else
 517         continue;
 518       /* here is an extra solvable we need to consider */
 519       idp = s->repo->idarraydata + s->provides;
 520       while ((id = *idp++) != 0)
 521         {
 522           while (ISRELDEP(id))
 523             {
 524               Reldep *rd = GETRELDEP(pool, id);
 525               id = rd->name;
 526             }
 527           if (pool->whatprovides[id] > 1)
 528             continue;   /* we already did that one in the normal code path */
 529           n = pool_id2str(pool, id);
 530           if ((doglob ? fnmatch(name, n, globflags) : nocase ? strcasecmp(name, n) : strcmp(name, n)) == 0)
 531             {
 532               queue_pushunique2(selection, SOLVER_SOLVABLE_PROVIDES, id);
 533               match = 1;
 534             }
 535         }
 536     }
 537   return match;
 538 }
 539
 540 /* this is the fast path of selection_provides: the id for the name
 541  * is known and thus we can quickly check the existance of a
 542  * package with that provides */
 543 static int
 544 selection_provides_id(Pool *pool, Queue *selection, Id id, int flags)
 545 {
 546   Id p, pp;
 547
 548   FOR_PROVIDES(p, pp, id)
 549     {
 550       Solvable *s = pool->solvables + p;
 551       if ((flags & SELECTION_INSTALLED_ONLY) != 0 && s->repo != pool->installed)
 552         continue;
 553       break;
 554     }
 555   if (p)
 556     {
 557       queue_push2(selection, SOLVER_SOLVABLE_PROVIDES, id);
 558       return SELECTION_PROVIDES;
 559     }
 560
 561   if ((flags & (SELECTION_WITH_BADARCH | SELECTION_WITH_DISABLED)) != 0)
 562     {
 563       queue_push2(selection, SOLVER_SOLVABLE_PROVIDES, id);
 564       selection_addextra(pool, selection, flags);
 565       if (selection->elements[0] == SOLVER_SOLVABLE_PROVIDES)
 566         queue_empty(selection);
 567       else
 568         {
 569           selection->elements[0] = SOLVER_SOLVABLE_PROVIDES;
 570           selection->elements[1] = id;
 571         }
 572       return selection->count ? SELECTION_PROVIDES : 0;
 573     }
 574
 575   return 0;
 576 }
 577
 578 /* add missing provides matchers to the selection */
 579 /* match the provides of a package */
 580 /* note that we only return raw SOLVER_SOLVABLE_PROVIDES jobs
 581  * so that the selection can be modified later. */
 582 static int
 583 selection_provides(Pool *pool, Queue *selection, const char *name, int flags)
 584 {
 585   Id id, p, pp;
 586   int match;
 587   int doglob;
 588   int nocase;
 589   int globflags;
 590   const char *n;
 591
 592   if ((flags & SELECTION_SOURCE_ONLY) != 0)
 593     return 0;   /* sources do not have provides */
 594
 595   nocase = flags & SELECTION_NOCASE;
 596   if (!nocase)
 597     {
 598       /* try the fast path first */
 599       id = pool_str2id(pool, name, 0);
 600       if (id)
 601         {
 602           /* the id is known, do the fast id matching */
 603           int ret = selection_provides_id(pool, selection, id, flags);
 604           if (ret)
 605             return ret;
 606         }
 607     }
 608
 609   doglob = (flags & SELECTION_GLOB) != 0 && strpbrk(name, "[*?") != 0;
 610   if (!nocase && !doglob)
 611     {
 612       /* all done above in selection_provides_id */
 613       return 0;
 614     }
 615
 616   /* looks like a glob or nocase match. really hard work. */
 617   match = 0;
 618   globflags = doglob && nocase ? FNM_CASEFOLD : 0;
 619   for (id = 1; id < pool->ss.nstrings; id++)
 620     {
 621       /* do we habe packages providing this id? */
 622       if (!pool->whatprovides[id] || pool->whatprovides[id] == 1)
 623         continue;
 624       n = pool_id2str(pool, id);
 625       if ((doglob ? fnmatch(name, n, globflags) : nocase ? strcasecmp(name, n) : strcmp(name, n)) == 0)
 626         {
 627           if ((flags & SELECTION_INSTALLED_ONLY) != 0)
 628             {
 629               FOR_PROVIDES(p, pp, id)
 630                 if (pool->solvables[p].repo == pool->installed)
 631                   break;
 632               if (!p)
 633                 continue;
 634             }
 635           queue_push2(selection, SOLVER_SOLVABLE_PROVIDES, id);
 636           match = 1;
 637         }
 638     }
 639
 640   if (flags & (SELECTION_WITH_BADARCH | SELECTION_WITH_DISABLED))
 641     match |= selection_addextra_provides(pool, selection, name, flags);
 642
 643   return match ? SELECTION_PROVIDES : 0;
 644 }
 645
 646 /*****  name matching  *****/
 647
 648 /* this is the fast path of selection_name: the id for the name
 649  * is known and thus we can quickly check the existance of a
 650  * package with that name */
 651 static int
 652 selection_name_id(Pool *pool, Queue *selection, Id id, int flags)
 653 {
 654   Id p, pp, matchid;
 655
 656   matchid = id;
 657   if ((flags & SELECTION_SOURCE_ONLY) != 0)
 658     {
 659       /* sources cannot be installed */
 660       if ((flags & SELECTION_INSTALLED_ONLY) != 0)
 661         return 0;
 662       /* add ARCH_SRC to match only sources */
 663       matchid = pool_rel2id(pool, id, ARCH_SRC, REL_ARCH, 1);
 664       flags &= ~SELECTION_WITH_SOURCE;
 665     }
 666
 667   FOR_PROVIDES(p, pp, matchid)
 668     {
 669       Solvable *s = pool->solvables + p;
 670       if (s->name != id)
 671         continue;
 672       if ((flags & SELECTION_INSTALLED_ONLY) != 0 && s->repo != pool->installed)
 673         continue;
 674       /* one match is all we need */
 675       queue_push2(selection, SOLVER_SOLVABLE_NAME, matchid);
 676       /* add the requested extra packages */
 677       if ((flags & (SELECTION_WITH_SOURCE | SELECTION_WITH_BADARCH | SELECTION_WITH_DISABLED)) != 0)
 678         selection_addextra(pool, selection, flags);
 679       return SELECTION_NAME;
 680     }
 681
 682   if ((flags & (SELECTION_WITH_BADARCH | SELECTION_WITH_DISABLED)) != 0)
 683     {
 684       queue_push2(selection, SOLVER_SOLVABLE_NAME, matchid);
 685       selection_addextra(pool, selection, flags);
 686       if (selection->elements[0] == SOLVER_SOLVABLE_NAME)
 687         queue_empty(selection);
 688       return selection->count ? SELECTION_NAME : 0;
 689     }
 690
 691   if ((flags & SELECTION_WITH_SOURCE) != 0 && (flags & SELECTION_INSTALLED_ONLY) == 0)
 692     {
 693       /* WITH_SOURCE case, but we had no match. try SOURCE_ONLY instead */
 694       matchid = pool_rel2id(pool, id, ARCH_SRC, REL_ARCH, 1);
 695       FOR_PROVIDES(p, pp, matchid)
 696         {
 697           Solvable *s = pool->solvables + p;
 698           if (s->name != id)
 699             continue;
 700           queue_push2(selection, SOLVER_SOLVABLE_NAME, matchid);
 701           return SELECTION_NAME;
 702         }
 703     }
 704   return 0;
 705 }
 706
 707 /* match the name of a package */
 708 /* note that for SELECTION_INSTALLED_ONLY the result is not trimmed */
 709 static int
 710 selection_name(Pool *pool, Queue *selection, const char *name, int flags)
 711 {
 712   Id id, p;
 713   int match;
 714   int doglob, nocase;
 715   int globflags;
 716   const char *n;
 717
 718   if ((flags & SELECTION_SOURCE_ONLY) != 0)
 719     flags &= ~SELECTION_WITH_SOURCE;
 720
 721   nocase = flags & SELECTION_NOCASE;
 722   if (!nocase && !(flags & SELECTION_SKIP_KIND))
 723     {
 724       /* try the fast path first */
 725       id = pool_str2id(pool, name, 0);
 726       if (id)
 727         {
 728           int ret = selection_name_id(pool, selection, id, flags);
 729           if (ret)
 730             return ret;
 731         }
 732     }
 733
 734   doglob = (flags & SELECTION_GLOB) != 0 && strpbrk(name, "[*?") != 0;
 735   if (!nocase && !(flags & SELECTION_SKIP_KIND) && !doglob)
 736     return 0;   /* all done above in selection_name_id */
 737
 738   /* do a name match over all packages. hard work. */
 739   match = 0;
 740   globflags = doglob && nocase ? FNM_CASEFOLD : 0;
 741   FOR_POOL_SOLVABLES(p)
 742     {
 743       Solvable *s = pool->solvables + p;
 744       if ((flags & SELECTION_INSTALLED_ONLY) != 0 && s->repo != pool->installed)
 745         continue;
 746       if (s->arch == ARCH_SRC || s->arch == ARCH_NOSRC)
 747         {
 748           if (!(flags & SELECTION_SOURCE_ONLY) && !(flags & SELECTION_WITH_SOURCE))
 749             continue;
 750           if (!(flags & SELECTION_WITH_DISABLED) && pool_disabled_solvable(pool, s))
 751             continue;
 752         }
 753       else if (s->repo != pool->installed)
 754         {
 755           if (!(flags & SELECTION_WITH_DISABLED) && pool_disabled_solvable(pool, s))
 756             continue;
 757           if (!(flags & SELECTION_WITH_BADARCH) && pool_badarch_solvable(pool, s))
 758             continue;
 759         }
 760       id = s->name;
 761       n = pool_id2str(pool, id);
 762       if (flags & SELECTION_SKIP_KIND)
 763         n = skipkind(n);
 764       if ((doglob ? fnmatch(name, n, globflags) : nocase ? strcasecmp(name, n) : strcmp(name, n)) == 0)
 765         {
 766           if ((flags & SELECTION_SOURCE_ONLY) != 0)
 767             {
 768               if (s->arch != ARCH_SRC && s->arch != ARCH_NOSRC)
 769                 continue;
 770               id = pool_rel2id(pool, id, ARCH_SRC, REL_ARCH, 1);
 771             }
 772           queue_pushunique2(selection, SOLVER_SOLVABLE_NAME, id);
 773           match = 1;
 774         }
 775     }
 776   if (match)
 777     {
 778       /* if there was a match widen the selector to include all extra packages */
 779       if ((flags & (SELECTION_WITH_SOURCE | SELECTION_WITH_BADARCH | SELECTION_WITH_DISABLED)) != 0)
 780         selection_addextra(pool, selection, flags);
 781       return SELECTION_NAME;
 782     }
 783   return 0;
 784 }
 785
 786
 787 /*****  SELECTION_DOTARCH and SELECTION_REL handling *****/
 788
 789 /* like selection_name, but check for a .arch suffix if the match did
 790    not work and SELECTION_DOTARCH is used */
 791 static int
 792 selection_name_arch(Pool *pool, Queue *selection, const char *name, int flags, int doprovides, int noprune)
 793 {
 794   int ret;
 795   const char *r;
 796   Id archid;
 797
 798   if (doprovides)
 799     ret = selection_provides(pool, selection, name, flags);
 800   else
 801     ret = selection_name(pool, selection, name, flags);
 802   if (ret)
 803     return ret;
 804   if (!(flags & SELECTION_DOTARCH))
 805     return 0;
 806   /* check if there is an .arch suffix */
 807   if ((r = strrchr(name, '.')) != 0 && r[1] && (archid = str2archid(pool, r + 1)) != 0)
 808     {
 809       char *rname = solv_strdup(name);
 810       rname[r - name] = 0;
 811       if (archid == ARCH_SRC || archid == ARCH_NOSRC)
 812         flags |= SELECTION_SOURCE_ONLY;
 813       if (doprovides)
 814         ret = selection_provides(pool, selection, rname, flags);
 815       else
 816         ret = selection_name(pool, selection, rname, flags);
 817       if (ret)
 818         {
 819           selection_filter_rel_noprune(pool, selection, REL_ARCH, archid);
 820           if (!noprune)
 821             selection_prune(pool, selection);
 822         }
 823       solv_free(rname);
 824       return ret && selection->count ? ret | SELECTION_DOTARCH : 0;
 825     }
 826   return 0;
 827 }
 828
 829 static char *
 830 splitrel(char *rname, char *r, int *rflagsp)
 831 {
 832   int nend = r - rname;
 833   int rflags = 0;
 834   if (nend && *r == '=' && r[-1] == '!')
 835     {
 836       nend--;
 837       r++;
 838       rflags = REL_LT|REL_GT;
 839     }
 840   for (; *r; r++)
 841     {
 842       if (*r == '<')
 843         rflags |= REL_LT;
 844       else if (*r == '=')
 845         rflags |= REL_EQ;
 846       else if (*r == '>')
 847         rflags |= REL_GT;
 848       else
 849         break;
 850     }
 851   while (*r && (*r == ' ' || *r == '\t'))
 852     r++;
 853   while (nend && (rname[nend - 1] == ' ' || rname[nend - 1] == '\t'))
 854     nend--;
 855   if (nend <= 0 || !*r || !rflags)
 856     return 0;
 857   *rflagsp = rflags;
 858   rname[nend] = 0;
 859   return r;
 860 }
 861
 862 /* match name/provides, support DOTARCH and REL modifiers
 863  */
 864 static int
 865 selection_name_arch_rel(Pool *pool, Queue *selection, const char *name, int flags, int doprovides)
 866 {
 867   int ret, rflags = 0, noprune;
 868   char *r = 0, *rname = 0;
 869
 870   /* try to split off an relation part */
 871   if ((flags & SELECTION_REL) != 0)
 872     {
 873       if ((r = strpbrk(name, "<=>")) != 0)
 874         {
 875           rname = solv_strdup(name);
 876           r = rname + (r - name);
 877           if ((r = splitrel(rname, r, &rflags)) == 0)
 878             rname = solv_free(rname);
 879         }
 880     }
 881
 882   /* check if we need to call selection_addextra */
 883   noprune = doprovides && (flags & (SELECTION_WITH_DISABLED | SELECTION_WITH_BADARCH));
 884
 885   if (!r)
 886     {
 887       /* could not split off relation */
 888       ret = selection_name_arch(pool, selection, name, flags, doprovides, noprune);
 889       if (ret && noprune)
 890         {
 891           selection_addextra(pool, selection, flags);
 892           selection_prune(pool, selection);
 893         }
 894       return ret && selection->count ? ret : 0;
 895     }
 896
 897   /* we could split of a relation. prune name and then filter rel */
 898   ret = selection_name_arch(pool, selection, rname, flags, doprovides, noprune);
 899   if (ret)
 900     {
 901       selection_filter_rel_noprune(pool, selection, rflags, pool_str2id(pool, r, 1));
 902       if (noprune)
 903         selection_addextra(pool, selection, flags);
 904       selection_prune(pool, selection);
 905     }
 906   solv_free(rname);
 907   return ret && selection->count ? ret | SELECTION_REL : 0;
 908 }
 909
 910 /*****  filelist matching  *****/
 911
 912 static int
 913 selection_filelist_sortcmp(const void *ap, const void *bp, void *dp)
 914 {
 915   Pool *pool = dp;
 916   const Id *a = ap, *b = bp;
 917   if (a[0] != b[0])
 918     return strcmp(pool_id2str(pool, a[0]), pool_id2str(pool, b[0]));
 919   return a[1] - b[1];
 920 }
 921
 922 static int
 923 selection_filelist(Pool *pool, Queue *selection, const char *name, int flags)
 924 {
 925   Dataiterator di;
 926   Queue q;
 927   Id id;
 928   int type;
 929   int i, j, lastid;
 930
 931   /* all files in the file list start with a '/' */
 932   if (*name != '/')
 933     {
 934       if (!(flags & SELECTION_GLOB))
 935         return 0;
 936       if (*name != '*' && *name != '[' && *name != '?')
 937         return 0;
 938     }
 939   type = !(flags & SELECTION_GLOB) || strpbrk(name, "[*?") == 0 ? SEARCH_STRING : SEARCH_GLOB;
 940   if ((flags & SELECTION_NOCASE) != 0)
 941     type |= SEARCH_NOCASE;
 942   queue_init(&q);
 943   dataiterator_init(&di, pool, flags & SELECTION_INSTALLED_ONLY ? pool->installed : 0, 0, SOLVABLE_FILELIST, name, type|SEARCH_FILES|SEARCH_COMPLETE_FILELIST);
 944   while (dataiterator_step(&di))
 945     {
 946       Solvable *s = pool->solvables + di.solvid;
 947       if (!s->repo)
 948         continue;
 949       if (s->arch == ARCH_SRC || s->arch == ARCH_NOSRC)
 950         {
 951           if (!(flags & SELECTION_SOURCE_ONLY) && !(flags & SELECTION_WITH_SOURCE))
 952             continue;
 953           if (!(flags & SELECTION_WITH_DISABLED) && pool_disabled_solvable(pool, s))
 954             continue;
 955         }
 956       else
 957         {
 958           if ((flags & SELECTION_SOURCE_ONLY) != 0)
 959             continue;
 960           if (s->repo != pool->installed)
 961             {
 962               if (!(flags & SELECTION_WITH_DISABLED) && pool_disabled_solvable(pool, s))
 963                 continue;
 964               if (!(flags & SELECTION_WITH_BADARCH) && pool_badarch_solvable(pool, s))
 965                 continue;
 966             }
 967         }
 968       if ((flags & SELECTION_FLAT) != 0)
 969         {
 970           /* don't bother with the complex stuff */
 971           queue_push2(selection, SOLVER_SOLVABLE | SOLVER_NOAUTOSET, di.solvid);
 972           dataiterator_skip_solvable(&di);
 973           continue;
 974         }
 975       id = pool_str2id(pool, di.kv.str, 1);
 976       queue_push2(&q, id, di.solvid);
 977     }
 978   dataiterator_free(&di);
 979   if ((flags & SELECTION_FLAT) != 0)
 980     {
 981       queue_free(&q);
 982       return selection->count ? SELECTION_FILELIST : 0;
 983     }
 984   if (!q.count)
 985     {
 986       queue_free(&q);
 987       return 0;
 988     }
 989   solv_sort(q.elements, q.count / 2, 2 * sizeof(Id), selection_filelist_sortcmp, pool);
 990   lastid = 0;
 991   queue_push2(&q, 0, 0);
 992   for (i = j = 0; i < q.count; i += 2)
 993     {
 994       if (q.elements[i] != lastid)
 995         {
 996           if (j == 1)
 997             queue_pushunique2(selection, SOLVER_SOLVABLE | SOLVER_NOAUTOSET, q.elements[0]);
 998           else if (j > 1)
 999             {
1000               int k;
1001               Id *idp;
1002               /* check if we already have it */
1003               for (k = 0; k < selection->count; k += 2)
1004                 {
1005                   if (selection->elements[k] != SOLVER_SOLVABLE_ONE_OF)
1006                     continue;
1007                   idp = pool->whatprovidesdata + selection->elements[k + 1];
1008                   if (!memcmp(idp, q.elements, j * sizeof(Id)) && !idp[j])
1009                     break;
1010                 }
1011               if (k == selection->count)
1012                 queue_push2(selection, SOLVER_SOLVABLE_ONE_OF, pool_ids2whatprovides(pool, q.elements, j));
1013             }
1014           lastid = q.elements[i];
1015           j = 0;
1016         }
1017       if (!j || q.elements[j - 1] != q.elements[i])
1018         q.elements[j++] = q.elements[i + 1];
1019     }
1020   queue_free(&q);
1021   return SELECTION_FILELIST;
1022 }
1023
1024
1025 /*****  canon name matching  *****/
1026
1027 #if defined(MULTI_SEMANTICS)
1028 # define EVRCMP_DEPCMP (pool->disttype == DISTTYPE_DEB ? EVRCMP_COMPARE : EVRCMP_MATCH_RELEASE)
1029 #elif defined(DEBIAN)
1030 # define EVRCMP_DEPCMP EVRCMP_COMPARE
1031 #else
1032 # define EVRCMP_DEPCMP EVRCMP_MATCH_RELEASE
1033 #endif
1034
1035 /* magic epoch promotion code, works only for SELECTION_NAME selections */
1036 static void
1037 selection_filter_evr(Pool *pool, Queue *selection, const char *evr)
1038 {
1039   int i, j;
1040   Queue q;
1041   Id qbuf[10];
1042   const char *sp;
1043
1044   /* do we already have an epoch? */
1045   for (sp = evr; *sp >= '0' && *sp <= '9'; sp++)
1046     ;
1047   if (*sp == ':' && sp != evr)
1048     {
1049       /* yes, just add the rel filter */
1050       selection_filter_rel(pool, selection, REL_EQ, pool_str2id(pool, evr, 1));
1051       return;
1052     }
1053
1054   queue_init(&q);
1055   queue_init_buffer(&q, qbuf, sizeof(qbuf)/sizeof(*qbuf));
1056   for (i = j = 0; i < selection->count; i += 2)
1057     {
1058       Id select = selection->elements[i] & SOLVER_SELECTMASK;
1059       Id id = selection->elements[i + 1];
1060       Id p, pp;
1061       const char *lastepoch = 0;
1062       int lastepochlen = 0;
1063
1064       queue_empty(&q);
1065       FOR_JOB_SELECT(p, pp, select, id)
1066         {
1067           Solvable *s = pool->solvables + p;
1068           const char *sevr = pool_id2str(pool, s->evr);
1069           for (sp = sevr; *sp >= '0' && *sp <= '9'; sp++)
1070             ;
1071           if (*sp != ':')
1072             sp = sevr;
1073           /* compare vr part */
1074           if (strcmp(evr, sp != sevr ? sp + 1 : sevr) != 0)
1075             {
1076               int r = pool_evrcmp_str(pool, sp != sevr ? sp + 1 : sevr, evr, EVRCMP_DEPCMP);
1077               if (r == -1 || r == 1)
1078                 continue;       /* solvable does not match vr */
1079             }
1080           queue_push(&q, p);
1081           if (sp > sevr)
1082             {
1083               while (sevr < sp && *sevr == '0') /* normalize epoch */
1084                 sevr++;
1085             }
1086           if (!lastepoch)
1087             {
1088               lastepoch = sevr;
1089               lastepochlen = sp - sevr;
1090             }
1091           else if (lastepochlen != sp - sevr || strncmp(lastepoch, sevr, lastepochlen) != 0)
1092             lastepochlen = -1;  /* multiple different epochs */
1093         }
1094       if (!lastepoch || lastepochlen == 0)
1095         id = pool_str2id(pool, evr, 1);         /* no match at all or zero epoch */
1096       else if (lastepochlen >= 0)
1097         {
1098           /* found exactly one epoch, simply prepend */
1099           char *evrx = solv_malloc(strlen(evr) + lastepochlen + 2);
1100           strncpy(evrx, lastepoch, lastepochlen + 1);
1101           strcpy(evrx + lastepochlen + 1, evr);
1102           id = pool_str2id(pool, evrx, 1);
1103           solv_free(evrx);
1104         }
1105       else
1106         {
1107           /* multiple epochs in multiple solvables, convert to list of solvables */
1108           selection->elements[j] = (selection->elements[i] & ~SOLVER_SELECTMASK) | SOLVER_SOLVABLE_ONE_OF;
1109           selection->elements[j + 1] = pool_queuetowhatprovides(pool, &q);
1110           j += 2;
1111           continue;
1112         }
1113       queue_empty(&q);
1114       queue_push2(&q, selection->elements[i], selection->elements[i + 1]);
1115       selection_filter_rel(pool, &q, REL_EQ, id);
1116       if (!q.count)
1117         continue;               /* oops, no match */
1118       selection->elements[j] = q.elements[0];
1119       selection->elements[j + 1] = q.elements[1];
1120       j += 2;
1121     }
1122   queue_truncate(selection, j);
1123   queue_free(&q);
1124 }
1125
1126 /* match the "canonical" name of the package */
1127 static int
1128 selection_canon(Pool *pool, Queue *selection, const char *name, int flags)
1129 {
1130   char *rname, *r, *r2;
1131   Id archid = 0;
1132   int ret;
1133
1134   /*
1135    * nameglob-version
1136    * nameglob-version.arch
1137    * nameglob-version-release
1138    * nameglob-version-release.arch
1139    */
1140   flags |= SELECTION_NAME;
1141   flags &= ~SELECTION_PROVIDES;
1142
1143   if (pool->disttype == DISTTYPE_DEB)
1144     {
1145       if ((r = strchr(name, '_')) == 0)
1146         return 0;
1147       rname = solv_strdup(name);        /* so we can modify it */
1148       r = rname + (r - name);
1149       *r++ = 0;
1150       if ((ret = selection_name(pool, selection, rname, flags)) == 0)
1151         {
1152           solv_free(rname);
1153           return 0;
1154         }
1155       /* is there a vaild arch? */
1156       if ((r2 = strrchr(r, '_')) != 0 && r[1] && (archid = str2archid(pool, r + 1)) != 0)
1157         {
1158           *r2 = 0;      /* split off */
1159           selection_filter_rel(pool, selection, REL_ARCH, archid);
1160         }
1161       selection_filter_rel(pool, selection, REL_EQ, pool_str2id(pool, r, 1));
1162       solv_free(rname);
1163       return selection->count ? ret | SELECTION_CANON : 0;
1164     }
1165
1166   if (pool->disttype == DISTTYPE_HAIKU)
1167     {
1168       if ((r = strchr(name, '-')) == 0)
1169         return 0;
1170       rname = solv_strdup(name);        /* so we can modify it */
1171       r = rname + (r - name);
1172       *r++ = 0;
1173       if ((ret = selection_name(pool, selection, rname, flags)) == 0)
1174         {
1175           solv_free(rname);
1176           return 0;
1177         }
1178       /* is there a vaild arch? */
1179       if ((r2 = strrchr(r, '-')) != 0 && r[1] && (archid = str2archid(pool, r + 1)) != 0)
1180         {
1181           *r2 = 0;      /* split off */
1182           selection_filter_rel(pool, selection, REL_ARCH, archid);
1183         }
1184       selection_filter_rel(pool, selection, REL_EQ, pool_str2id(pool, r, 1));
1185       solv_free(rname);
1186       return selection->count ? ret | SELECTION_CANON : 0;
1187     }
1188
1189   if ((r = strrchr(name, '-')) == 0)
1190     return 0;
1191   rname = solv_strdup(name);    /* so we can modify it */
1192   r = rname + (r - name);
1193   *r = 0;
1194
1195   /* split off potential arch part from version */
1196   if ((r2 = strrchr(r + 1, '.')) != 0 && r2[1] && (archid = str2archid(pool, r2 + 1)) != 0)
1197     *r2 = 0;    /* found valid arch, split it off */
1198   if (archid == ARCH_SRC || archid == ARCH_NOSRC)
1199     flags |= SELECTION_SOURCE_ONLY;
1200
1201   /* try with just the version */
1202   if ((ret = selection_name(pool, selection, rname, flags)) == 0)
1203     {
1204       /* no luck, try with version-release */
1205       if ((r2 = strrchr(rname, '-')) == 0)
1206         {
1207           solv_free(rname);
1208           return 0;
1209         }
1210       *r = '-';
1211       *r2 = 0;
1212       r = r2;
1213       if ((ret = selection_name(pool, selection, rname, flags)) == 0)
1214         {
1215           solv_free(rname);
1216           return 0;
1217         }
1218     }
1219   if (archid)
1220     selection_filter_rel(pool, selection, REL_ARCH, archid);
1221   selection_filter_evr(pool, selection, r + 1); /* magic epoch promotion */
1222   solv_free(rname);
1223   return selection->count ? ret | SELECTION_CANON : 0;
1224 }
1225
1226 /* return the needed withbits to match the provided selection */
1227 static int
1228 selection_extrabits(Pool *pool, Queue *selection, int flags)
1229 {
1230   int i, needflags, isextra;
1231   int allflags;
1232   Id p;
1233   Solvable *s;
1234   Queue qlimit;
1235
1236   allflags = flags & (SELECTION_WITH_SOURCE | SELECTION_WITH_DISABLED | SELECTION_WITH_BADARCH);
1237   if (!selection->count)
1238     return allflags;
1239   if (selection->count == 2 && selection->elements[0] == SOLVER_SOLVABLE_ALL)
1240     return allflags;    /* don't bother */
1241   queue_init(&qlimit);
1242   selection_solvables(pool, selection, &qlimit);
1243   needflags = 0;
1244   for (i = 0; i < qlimit.count; i++)
1245     {
1246       p = qlimit.elements[i];
1247       s = pool->solvables + p;
1248       if ((flags & SELECTION_INSTALLED_ONLY) != 0 && s->repo != pool->installed)
1249         continue;
1250       isextra = 0;
1251       if (s->arch == ARCH_SRC || s->arch == ARCH_NOSRC)
1252         {
1253           if (!(flags & SELECTION_WITH_SOURCE))
1254             continue;
1255           isextra |= SELECTION_WITH_SOURCE;
1256           if (pool_disabled_solvable(pool, s))
1257             {
1258               if (!(flags & SELECTION_WITH_DISABLED))
1259                 continue;
1260               isextra |= SELECTION_WITH_DISABLED;
1261             }
1262         }
1263       else
1264         {
1265           if ((flags & SELECTION_SOURCE_ONLY) != 0)
1266             continue;
1267           if (s->repo != pool->installed)
1268             {
1269               if (pool_disabled_solvable(pool, s))
1270                 {
1271                   if (!(flags & SELECTION_WITH_DISABLED))
1272                     continue;
1273                   isextra |= SELECTION_WITH_DISABLED;
1274                 }
1275               if (pool_badarch_solvable(pool, s))
1276                 {
1277                   if (!(flags & SELECTION_WITH_BADARCH))
1278                     continue;
1279                   isextra |= SELECTION_WITH_BADARCH;
1280                 }
1281             }
1282         }
1283       if (isextra)
1284         {
1285           needflags |= isextra;
1286           if (needflags == allflags)
1287             break;
1288         }
1289     }
1290   queue_free(&qlimit);
1291   return needflags;
1292 }
1293
1294 int
1295 selection_make(Pool *pool, Queue *selection, const char *name, int flags)
1296 {
1297   int ret = 0;
1298   if ((flags & SELECTION_MODEBITS) != 0)
1299     {
1300       Queue q;
1301
1302       queue_init(&q);
1303       if ((flags & SELECTION_MODEBITS) == SELECTION_SUBTRACT || (flags & SELECTION_MODEBITS) == SELECTION_FILTER)
1304         {
1305           if (!selection->count)
1306             {
1307               queue_free(&q);
1308               return 0;
1309             }
1310           if ((flags & (SELECTION_WITH_DISABLED | SELECTION_WITH_BADARCH | SELECTION_WITH_SOURCE)) != 0)
1311             {
1312               /* try to drop expensive extra bits */
1313               flags = (flags & ~(SELECTION_WITH_DISABLED | SELECTION_WITH_BADARCH | SELECTION_WITH_SOURCE)) | selection_extrabits(pool, selection, flags);
1314             }
1315         }
1316       ret = selection_make(pool, &q, name, flags & ~SELECTION_MODEBITS);
1317       if ((flags & SELECTION_MODEBITS) == SELECTION_ADD)
1318         selection_add(pool, selection, &q);
1319       else if ((flags & SELECTION_MODEBITS) == SELECTION_SUBTRACT)
1320         selection_subtract(pool, selection, &q);
1321       else if (ret || !(flags & SELECTION_FILTER_KEEP_IFEMPTY))
1322         {
1323           if ((flags & SELECTION_FILTER_SWAPPED) != 0)
1324             {
1325               selection_filter(pool, &q, selection);
1326               queue_free(selection);
1327               queue_init_clone(selection, &q);
1328             }
1329           else
1330             selection_filter(pool, selection, &q);
1331         }
1332       queue_free(&q);
1333       return ret;
1334     }
1335   queue_empty(selection);
1336   if ((flags & SELECTION_INSTALLED_ONLY) != 0 && !pool->installed)
1337     return 0;
1338
1339   /* here come our four selection modes */
1340   if ((flags & SELECTION_FILELIST) != 0)
1341     ret = selection_filelist(pool, selection, name, flags);
1342   if (!ret && (flags & SELECTION_NAME) != 0)
1343     ret = selection_name_arch_rel(pool, selection, name, flags, 0);
1344   if (!ret && (flags & SELECTION_PROVIDES) != 0)
1345     ret = selection_name_arch_rel(pool, selection, name, flags, 1);
1346   if (!ret && (flags & SELECTION_CANON) != 0)
1347     ret = selection_canon(pool, selection, name, flags);
1348
1349   /* now do result filtering */
1350   if (ret && (flags & SELECTION_INSTALLED_ONLY) != 0)
1351     selection_filter_repo(pool, selection, pool->installed);
1352
1353   /* flatten if requested */
1354   if (ret && (flags & SELECTION_FLAT) != 0)
1355     selection_flatten(pool, selection);
1356   return selection->count ? ret : 0;
1357 }
1358
1359 struct limiter {
1360   int start;    /* either 2 or repofilter->start */
1361   int end;      /* either nsolvables or repofilter->end */
1362   Id *mapper;
1363   Repo *repofilter;
1364 };
1365
1366 /* add matching src packages to simple SOLVABLE_NAME selections */
1367 static void
1368 setup_limiter(Pool *pool, int flags, struct limiter *limiter)
1369 {
1370   limiter->start = 2;
1371   limiter->end = pool->nsolvables;
1372   limiter->mapper = 0;
1373   limiter->repofilter = 0;
1374   if ((flags & SELECTION_INSTALLED_ONLY) != 0)
1375     {
1376       Repo *repo = pool->installed;
1377       limiter->repofilter = repo;
1378       limiter->start = repo ? repo->start : 0;
1379       limiter->end = repo ? repo->end : 0;
1380     }
1381 }
1382
1383 static int
1384 matchdep_str(const char *pattern, const char *string, int flags)
1385 {
1386   if (!pattern || !string)
1387     return 0;
1388   if (flags & SELECTION_GLOB)
1389     {
1390       int globflags = (flags & SELECTION_NOCASE) != 0 ? FNM_CASEFOLD : 0;
1391       return fnmatch(pattern, string, globflags) == 0 ? 1 : 0;
1392     }
1393   if (flags & SELECTION_NOCASE)
1394     return strcasecmp(pattern, string) == 0 ? 1 : 0;
1395   return strcmp(pattern, string) == 0 ? 1 : 0;
1396 }
1397
1398 /* like pool_match_dep but uses matchdep_str to match the name for glob and nocase matching */
1399 static int
1400 matchdep(Pool *pool, Id id, char *rname, int rflags, Id revr, int flags)
1401 {
1402   if (ISRELDEP(id))
1403     {
1404       Reldep *rd = GETRELDEP(pool, id);
1405       if (rd->flags > 7)
1406         {
1407           if (rd->flags == REL_AND || rd->flags == REL_OR || rd->flags == REL_WITH || rd->flags == REL_WITHOUT || rd->flags == REL_COND || rd->flags == REL_UNLESS)
1408             {
1409               if (matchdep(pool, rd->name, rname, rflags, revr, flags))
1410                 return 1;
1411               if ((rd->flags == REL_COND || rd->flags == REL_UNLESS) && ISRELDEP(rd->evr))
1412                 {
1413                   rd = GETRELDEP(pool, rd->evr);
1414                   if (rd->flags != REL_ELSE)
1415                     return 0;
1416                 }
1417               if (rd->flags != REL_COND && rd->flags != REL_UNLESS && rd->flags != REL_WITHOUT && matchdep(pool, rd->evr, rname, rflags, revr, flags))
1418                 return 1;
1419               return 0;
1420             }
1421           if (rd->flags == REL_ARCH)
1422             return matchdep(pool, rd->name, rname, rflags, revr, flags);
1423         }
1424       if (!matchdep(pool, rd->name, rname, rflags, revr, flags))
1425         return 0;
1426       if (rflags && !pool_intersect_evrs(pool, rd->flags, rd->evr, rflags, revr))
1427         return 0;
1428       return 1;
1429     }
1430   return matchdep_str(rname, pool_id2str(pool, id), flags);
1431 }
1432
1433 static int
1434 selection_make_matchdeps_common_limited(Pool *pool, Queue *selection, const char *name, Id dep, int flags, int keyname, int marker, struct limiter *limiter)
1435 {
1436   int li, i, j;
1437   int ret = 0;
1438   char *rname = 0, *r = 0;
1439   int rflags = 0;
1440   Id revr = 0;
1441   Id p;
1442   Queue q;
1443
1444   queue_empty(selection);
1445   if (!limiter->end)
1446     return 0;
1447   if (!name && !dep)
1448     return 0;
1449   if (name && dep)
1450     return 0;
1451
1452   if ((flags & SELECTION_MATCH_DEPSTR) != 0)
1453     flags &= ~SELECTION_REL;
1454
1455   if (name)
1456     {
1457       rname = solv_strdup(name);
1458       if ((flags & SELECTION_REL) != 0)
1459         {
1460           if ((r = strpbrk(rname, "<=>")) != 0)
1461             {
1462               if ((r = splitrel(rname, r, &rflags)) == 0)
1463                 {
1464                   solv_free(rname);
1465                   return 0;
1466                 }
1467             }
1468           revr = pool_str2id(pool, r, 1);
1469           ret |= SELECTION_REL;
1470         }
1471       if ((flags & SELECTION_GLOB) != 0 && !strpbrk(rname, "[*?") != 0)
1472         flags &= ~SELECTION_GLOB;
1473
1474       if ((flags & SELECTION_GLOB) == 0 && (flags & SELECTION_NOCASE) == 0 && (flags & SELECTION_MATCH_DEPSTR) == 0)
1475         {
1476           /* we can use the faster selection_make_matchdepid */
1477           dep = pool_str2id(pool, rname, 1);
1478           if (rflags)
1479             dep = pool_rel2id(pool, dep, revr, rflags, 1);
1480           rname = solv_free(rname);
1481           name = 0;
1482         }
1483     }
1484   if (dep)
1485     {
1486       if (keyname == SOLVABLE_NAME && (flags & SELECTION_MATCH_DEPSTR) != 0)
1487         {
1488           Reldep *rd;
1489           if (!ISRELDEP(dep))
1490             return 0;
1491           rd = GETRELDEP(pool, dep);
1492           if (!rd->name || rd->flags != REL_EQ)
1493             return 0;
1494           dep = rd->name;
1495           rflags = rd->flags;
1496           revr = rd->evr;
1497         }
1498     }
1499
1500   queue_init(&q);
1501   for (li = limiter->start; li < limiter->end; li++)
1502     {
1503       Solvable *s;
1504       p = limiter->mapper ? limiter->mapper[li] : li;
1505       s = pool->solvables + p;
1506       if (!s->repo || (limiter->repofilter && s->repo != limiter->repofilter))
1507         continue;
1508       if (s->arch == ARCH_SRC || s->arch == ARCH_NOSRC)
1509         {
1510           if (!(flags & SELECTION_SOURCE_ONLY) && !(flags & SELECTION_WITH_SOURCE))
1511             continue;
1512           if (!(flags & SELECTION_WITH_DISABLED) && pool_disabled_solvable(pool, s))
1513             continue;
1514         }
1515       else
1516         {
1517           if ((flags & SELECTION_SOURCE_ONLY) != 0)
1518             continue;
1519           if (s->repo != pool->installed)
1520             {
1521               if (!(flags & SELECTION_WITH_DISABLED) && pool_disabled_solvable(pool, s))
1522                 continue;
1523               if (!(flags & SELECTION_WITH_BADARCH) && pool_badarch_solvable(pool, s))
1524                 continue;
1525             }
1526         }
1527       if (keyname == SOLVABLE_NAME)                     /* nevr match hack */
1528         {
1529           if (dep)
1530             {
1531               if ((flags & SELECTION_MATCH_DEPSTR) != 0)
1532                 {
1533                   if (s->name != dep || s->evr != revr)
1534                     continue;
1535                 }
1536               else
1537                 {
1538                   if (!pool_match_nevr(pool, s, dep))
1539                     continue;
1540                 }
1541             }
1542           else
1543             {
1544               if ((flags & SELECTION_MATCH_DEPSTR) != 0)        /* mis-use */
1545                 {
1546                   char *tmp = pool_tmpjoin(pool, pool_id2str(pool, s->name), " = ", pool_id2str(pool, s->evr));
1547                   if (!matchdep_str(rname, tmp, flags))
1548                     continue;
1549                 }
1550               else
1551                 {
1552                   if (!matchdep(pool, s->name, rname, rflags, revr, flags))
1553                     continue;
1554                   if (rflags && !pool_intersect_evrs(pool, rflags, revr, REL_EQ, s->evr))
1555                     continue;
1556                 }
1557             }
1558           queue_push(selection, p);
1559           continue;
1560         }
1561       queue_empty(&q);
1562       repo_lookup_deparray(s->repo, p, keyname, &q, marker);
1563       if (!q.count)
1564         continue;
1565       if (dep)
1566         {
1567           if ((flags & SELECTION_MATCH_DEPSTR) != 0)    /* mis-use */
1568             {
1569               for (i = 0; i < q.count; i++)
1570                 if (q.elements[i] == dep)
1571                   break;
1572             }
1573           else
1574             {
1575               for (i = 0; i < q.count; i++)
1576                 if (pool_match_dep(pool, q.elements[i], dep))
1577                   break;
1578             }
1579         }
1580       else
1581         {
1582           if ((flags & SELECTION_MATCH_DEPSTR) != 0)
1583             {
1584               for (i = 0; i < q.count; i++)
1585                 if (matchdep_str(rname, pool_dep2str(pool, q.elements[i]), flags))
1586                   break;
1587             }
1588           else
1589             {
1590               for (i = 0; i < q.count; i++)
1591                 if (matchdep(pool, q.elements[i], rname, rflags, revr, flags))
1592                   break;
1593             }
1594         }
1595       if (i < q.count)
1596         queue_push(selection, p);
1597     }
1598   queue_free(&q);
1599   solv_free(rname);
1600   if (!selection->count)
1601     return 0;
1602
1603   /* convert package list to selection */
1604   j = selection->count;
1605   queue_insertn(selection, 0, selection->count, 0);
1606   for (i = 0; i < selection->count; )
1607     {
1608       selection->elements[i++] = SOLVER_SOLVABLE | SOLVER_NOAUTOSET;
1609       selection->elements[i++] = selection->elements[j++];
1610     }
1611
1612   if ((flags & SELECTION_FLAT) != 0)
1613     selection_flatten(pool, selection);
1614   return ret | (keyname == SOLVABLE_NAME ? SELECTION_NAME : SELECTION_PROVIDES);
1615 }
1616
1617 static int
1618 selection_make_matchdeps_common(Pool *pool, Queue *selection, const char *name, Id dep, int flags, int keyname, int marker)
1619 {
1620   struct limiter limiter;
1621
1622   setup_limiter(pool, flags, &limiter);
1623   if ((flags & SELECTION_MODEBITS) != SELECTION_REPLACE)
1624     {
1625       int ret;
1626       Queue q, qlimit;
1627       queue_init(&q);
1628       queue_init(&qlimit);
1629       /* deal with special filter cases */
1630       if ((flags & SELECTION_MODEBITS) == SELECTION_FILTER && selection->count == 2 && limiter.end)
1631         {
1632           if ((selection->elements[0] & SOLVER_SELECTMASK) == SOLVER_SOLVABLE_ALL)
1633             flags = (flags & ~SELECTION_MODEBITS) | SELECTION_REPLACE;
1634           else if ((selection->elements[0] & SOLVER_SELECTMASK) == SOLVER_SOLVABLE_REPO)
1635             {
1636               Repo *repo = pool_id2repo(pool, selection->elements[1]);
1637               if (limiter.repofilter && repo != limiter.repofilter)
1638                 repo = 0;
1639               limiter.repofilter = repo;
1640               limiter.start = repo ? repo->start : 0;
1641               limiter.end = repo ? repo->end : 0;
1642               flags = (flags & ~SELECTION_MODEBITS) | SELECTION_REPLACE;
1643             }
1644         }
1645       if (limiter.end && ((flags & SELECTION_MODEBITS) == SELECTION_SUBTRACT || (flags & SELECTION_MODEBITS) == SELECTION_FILTER))
1646         {
1647           selection_solvables(pool, selection, &qlimit);
1648           limiter.start = 0;
1649           limiter.end = qlimit.count;
1650           limiter.mapper = qlimit.elements;
1651         }
1652       ret = selection_make_matchdeps_common_limited(pool, &q, name, dep, flags & ~SELECTION_MODEBITS, keyname, marker, &limiter);
1653       queue_free(&qlimit);
1654       if ((flags & SELECTION_MODEBITS) == SELECTION_ADD)
1655         selection_add(pool, selection, &q);
1656       else if ((flags & SELECTION_MODEBITS) == SELECTION_SUBTRACT)
1657         selection_subtract(pool, selection, &q);
1658       else if ((flags & SELECTION_MODEBITS) == SELECTION_FILTER)
1659         {
1660           if (ret || !(flags & SELECTION_FILTER_KEEP_IFEMPTY))
1661             {
1662               if ((flags & SELECTION_FILTER_SWAPPED) != 0)
1663                 {
1664                   selection_filter(pool, &q, selection);
1665                   queue_free(selection);
1666                   queue_init_clone(selection, &q);
1667                 }
1668               else
1669                 selection_filter(pool, selection, &q);
1670             }
1671         }
1672       else if (ret || !(flags & SELECTION_FILTER_KEEP_IFEMPTY))
1673         {
1674           /* special filter case from above */
1675           int i;
1676           Id f = selection->elements[0] & ~(SOLVER_SELECTMASK|SOLVER_NOAUTOSET);        /* job, jobflags, setflags */
1677           queue_free(selection);
1678           queue_init_clone(selection, &q);
1679           for (i = 0; i < selection->count; i += 2)
1680             selection->elements[i] = (selection->elements[i] & (SOLVER_SELECTMASK | SOLVER_SETMASK)) | f;
1681         }
1682       queue_free(&q);
1683       return ret;
1684     }
1685   return selection_make_matchdeps_common_limited(pool, selection, name, dep, flags, keyname, marker, &limiter);
1686 }
1687
1688 /*
1689  *  select against the dependencies in keyname
1690  *  like SELECTION_PROVIDES, but with the deps in keyname instead of provides.
1691  *  supported match modifiers:
1692  *    SELECTION_REL
1693  *    SELECTION_GLOB
1694  *    SELECTION_NOCASE
1695  */
1696 int
1697 selection_make_matchdeps(Pool *pool, Queue *selection, const char *name, int flags, int keyname, int marker)
1698 {
1699   return selection_make_matchdeps_common(pool, selection, name, 0, flags, keyname, marker);
1700 }
1701
1702 /*
1703  *  select against the dependency id in keyname
1704  */
1705 int
1706 selection_make_matchdepid(Pool *pool, Queue *selection, Id dep, int flags, int keyname, int marker)
1707 {
1708   return selection_make_matchdeps_common(pool, selection, 0, dep, flags, keyname, marker);
1709 }
1710
1711 static inline int
1712 pool_is_kind(Pool *pool, Id name, Id kind)
1713 {
1714   const char *n;
1715   if (!kind)
1716     return 1;
1717   n = pool_id2str(pool, name);
1718   if (kind != 1)
1719     {
1720       const char *kn = pool_id2str(pool, kind);
1721       int knl = strlen(kn);
1722       return !strncmp(n, kn, knl) && n[knl] == ':' ? 1 : 0;
1723     }
1724   else
1725     {
1726       if (*n == ':')
1727         return 1;
1728       while(*n >= 'a' && *n <= 'z')
1729         n++;
1730       return *n == ':' ? 0 : 1;
1731     }
1732 }
1733
1734 static void
1735 selection_filter_map(Pool *pool, Queue *sel, Map *m, int setflags)
1736 {
1737   int i, j, miss;
1738   Queue q;
1739   Id p, pp;
1740
1741   queue_init(&q);
1742   for (i = j = 0; i < sel->count; i += 2)
1743     {
1744       Id select = sel->elements[i] & SOLVER_SELECTMASK;
1745       queue_empty(&q);
1746       miss = 0;
1747       if (select == SOLVER_SOLVABLE_ALL)
1748         {
1749           FOR_POOL_SOLVABLES(p)
1750             {
1751               if (map_tst(m, p))
1752                 queue_push(&q, p);
1753               else
1754                 miss = 1;
1755             }
1756         }
1757       else if (select == SOLVER_SOLVABLE_REPO)
1758         {
1759           Solvable *s;
1760           Repo *repo = pool_id2repo(pool, sel->elements[i + 1]);
1761           if (repo)
1762             {
1763               FOR_REPO_SOLVABLES(repo, p, s)
1764                 {
1765                   if (map_tst(m, p))
1766                     queue_push(&q, p);
1767                   else
1768                     miss = 1;
1769                 }
1770             }
1771         }
1772       else
1773         {
1774           FOR_JOB_SELECT(p, pp, select, sel->elements[i + 1])
1775             {
1776               if (map_tst(m, p))
1777                 queue_pushunique(&q, p);
1778               else
1779                 miss = 1;
1780             }
1781         }
1782       if (!q.count)
1783         continue;
1784       if (!miss)
1785         {
1786           sel->elements[j] = sel->elements[i] | setflags;
1787           sel->elements[j + 1] = sel->elements[i + 1];
1788         }
1789       else if (q.count > 1)
1790         {
1791           sel->elements[j] = (sel->elements[i] & ~SOLVER_SELECTMASK) | SOLVER_SOLVABLE_ONE_OF | setflags;
1792           sel->elements[j + 1] = pool_queuetowhatprovides(pool, &q);
1793         }
1794       else
1795         {
1796           sel->elements[j] = (sel->elements[i] & ~SOLVER_SELECTMASK) | SOLVER_SOLVABLE | SOLVER_NOAUTOSET | setflags;
1797           sel->elements[j + 1] = q.elements[0];
1798         }
1799       j += 2;
1800     }
1801   queue_truncate(sel, j);
1802   queue_free(&q);
1803 }
1804
1805 static void
1806 selection_filter_int(Pool *pool, Queue *sel1, Queue *sel2, int invert)
1807 {
1808   int i, j;
1809   Id p, pp, q1filled = 0;
1810   Queue q1;
1811   Map m2;
1812   Id setflags = 0;
1813
1814   if (!sel1->count || !sel2->count)
1815     {
1816       if (invert && !sel2->count)
1817         return;
1818       queue_empty(sel1);
1819       return;
1820     }
1821   if (sel1->count == 2 && (sel1->elements[0] & SOLVER_SELECTMASK) == SOLVER_SOLVABLE_ALL && !invert)
1822     {
1823       /* XXX: not 100% correct, but very useful */
1824       p = sel1->elements[0] & ~(SOLVER_SELECTMASK | SOLVER_SETMASK);    /* job & jobflags */
1825       queue_free(sel1);
1826       queue_init_clone(sel1, sel2);
1827       for (i = 0; i < sel1->count; i += 2)
1828         sel1->elements[i] = (sel1->elements[i] & (SOLVER_SELECTMASK | SOLVER_SETMASK)) | p ;
1829       return;
1830     }
1831
1832   /* convert sel2 into a map */
1833   queue_init(&q1);
1834   map_init(&m2, pool->nsolvables);
1835   for (i = 0; i < sel2->count; i += 2)
1836     {
1837       Id select = sel2->elements[i] & SOLVER_SELECTMASK;
1838       if (select == SOLVER_SOLVABLE_ALL)
1839         {
1840           queue_free(&q1);
1841           map_free(&m2);
1842           if (invert)
1843             queue_empty(sel1);
1844           return;
1845         }
1846       if (select == SOLVER_SOLVABLE_REPO)
1847         {
1848           Solvable *s;
1849           Repo *repo = pool_id2repo(pool, sel2->elements[i + 1]);
1850           if (repo)
1851             {
1852               FOR_REPO_SOLVABLES(repo, p, s)
1853                 map_set(&m2, p);
1854             }
1855         }
1856       else
1857         {
1858           if ((select == SOLVER_SOLVABLE_NAME || select == SOLVER_SOLVABLE_PROVIDES) && ISRELDEP(sel2->elements[i + 1]))
1859             {
1860               Reldep *rd = GETRELDEP(pool, sel2->elements[i + 1]);
1861               if (rd->flags == REL_ARCH && rd->name == 0)
1862                 {
1863                   /* special arch filter */
1864                   if (!q1filled++)
1865                     selection_solvables(pool, sel1, &q1);
1866                   for (j = 0; j < q1.count; j++)
1867                     {
1868                       Id p = q1.elements[j];
1869                       Solvable *s = pool->solvables + p;
1870                       if (s->arch == rd->evr || (rd->evr == ARCH_SRC && s->arch == ARCH_NOSRC))
1871                         map_set(&m2, p);
1872                     }
1873                   continue;
1874                 }
1875               else if (rd->flags == REL_KIND && rd->name == 0)
1876                 {
1877                   /* special kind filter */
1878                   if (!q1filled++)
1879                     selection_solvables(pool, sel1, &q1);
1880                   for (j = 0; j < q1.count; j++)
1881                     {
1882                       Id p = q1.elements[j];
1883                       Solvable *s = pool->solvables + p;
1884                       if (pool_is_kind(pool, s->name, rd->evr))
1885                         map_set(&m2, p);
1886                     }
1887                   continue;
1888                 }
1889             }
1890           FOR_JOB_SELECT(p, pp, select, sel2->elements[i + 1])
1891             map_set(&m2, p);
1892         }
1893     }
1894   queue_free(&q1);
1895
1896   /* now filter sel1 with the map */
1897   if (invert)
1898     map_invertall(&m2);
1899   if (sel2->count == 2)
1900     setflags = sel2->elements[0] & SOLVER_SETMASK & ~SOLVER_NOAUTOSET;
1901   selection_filter_map(pool, sel1, &m2, setflags);
1902   map_free(&m2);
1903 }
1904
1905 void
1906 selection_filter(Pool *pool, Queue *sel1, Queue *sel2)
1907 {
1908   selection_filter_int(pool, sel1, sel2, 0);
1909 }
1910
1911 void
1912 selection_add(Pool *pool, Queue *sel1, Queue *sel2)
1913 {
1914   if (sel2->count)
1915     queue_insertn(sel1, sel1->count, sel2->count, sel2->elements);
1916 }
1917
1918 void
1919 selection_subtract(Pool *pool, Queue *sel1, Queue *sel2)
1920 {
1921   selection_filter_int(pool, sel1, sel2, 1);
1922 }
1923
1924 const char *
1925 pool_selection2str(Pool *pool, Queue *selection, Id flagmask)
1926 {
1927   char *s;
1928   const char *s2;
1929   int i;
1930   s = pool_tmpjoin(pool, 0, 0, 0);
1931   for (i = 0; i < selection->count; i += 2)
1932     {
1933       Id how = selection->elements[i];
1934       if (*s)
1935         s = pool_tmpappend(pool, s, " + ", 0);
1936       s2 = solver_select2str(pool, how & SOLVER_SELECTMASK, selection->elements[i + 1]);
1937       s = pool_tmpappend(pool, s, s2, 0);
1938       pool_freetmpspace(pool, s2);
1939       how &= flagmask & SOLVER_SETMASK;
1940       if (how)
1941         {
1942           int o = strlen(s);
1943           s = pool_tmpappend(pool, s, " ", 0);
1944           if (how & SOLVER_SETEV)
1945             s = pool_tmpappend(pool, s, ",setev", 0);
1946           if (how & SOLVER_SETEVR)
1947             s = pool_tmpappend(pool, s, ",setevr", 0);
1948           if (how & SOLVER_SETARCH)
1949             s = pool_tmpappend(pool, s, ",setarch", 0);
1950           if (how & SOLVER_SETVENDOR)
1951             s = pool_tmpappend(pool, s, ",setvendor", 0);
1952           if (how & SOLVER_SETREPO)
1953             s = pool_tmpappend(pool, s, ",setrepo", 0);
1954           if (how & SOLVER_NOAUTOSET)
1955             s = pool_tmpappend(pool, s, ",noautoset", 0);
1956           if (s[o + 1] != ',')
1957             s = pool_tmpappend(pool, s, ",?", 0);
1958           s[o + 1] = '[';
1959           s = pool_tmpappend(pool, s, "]", 0);
1960         }
1961     }
1962   return s;
1963 }
1964