src/pool.c

   1 /*
   2  * Copyright (c) 2007-2009, Novell Inc.
   3  *
   4  * This program is licensed under the BSD license, read LICENSE.BSD
   5  * for further information
   6  */
   7
   8 /*
   9  * pool.c
  10  *
  11  * The pool contains information about solvables
  12  * stored optimized for memory consumption and fast retrieval.
  13  */
  14
  15 #include <stdio.h>
  16 #include <stdlib.h>
  17 #include <stdarg.h>
  18 #include <unistd.h>
  19 #include <string.h>
  20
  21 #include "pool.h"
  22 #include "repo.h"
  23 #include "poolid.h"
  24 #include "poolid_private.h"
  25 #include "poolarch.h"
  26 #include "util.h"
  27 #include "bitmap.h"
  28 #include "evr.h"
  29
  30 #define SOLVABLE_BLOCK  255
  31
  32 #define KNOWNID_INITIALIZE
  33 #include "knownid.h"
  34 #undef KNOWNID_INITIALIZE
  35
  36 /* create pool */
  37 Pool *
  38 pool_create(void)
  39 {
  40   Pool *pool;
  41   Solvable *s;
  42
  43   pool = (Pool *)solv_calloc(1, sizeof(*pool));
  44
  45   stringpool_init (&pool->ss, initpool_data);
  46
  47   /* alloc space for RelDep 0 */
  48   pool->rels = solv_extend_resize(0, 1, sizeof(Reldep), REL_BLOCK);
  49   pool->nrels = 1;
  50   memset(pool->rels, 0, sizeof(Reldep));
  51
  52   /* alloc space for Solvable 0 and system solvable */
  53   pool->solvables = solv_extend_resize(0, 2, sizeof(Solvable), SOLVABLE_BLOCK);
  54   pool->nsolvables = 2;
  55   memset(pool->solvables, 0, 2 * sizeof(Solvable));
  56
  57   /* initialize the system solvable */
  58   s = pool->solvables + SYSTEMSOLVABLE;
  59   s->name = SYSTEM_SYSTEM;
  60   s->arch = ARCH_NOARCH;
  61   s->evr = ID_EMPTY;
  62
  63   queue_init(&pool->vendormap);
  64
  65   pool->debugmask = SOLV_DEBUG_RESULT;  /* FIXME */
  66 #ifdef FEDORA
  67   pool->obsoleteusescolors = 1;
  68 #endif
  69 #ifdef DEBIAN
  70   pool->allowselfconflicts = 1;
  71   pool->disttype = DISTTYPE_DEB;
  72 #endif
  73 #ifdef RPM5
  74   pool->obsoleteusesprovides = 1;
  75   pool->implicitobsoleteusesprovides = 1;
  76 #endif
  77   return pool;
  78 }
  79
  80
  81 /* free all the resources of our pool */
  82 void
  83 pool_free(Pool *pool)
  84 {
  85   int i;
  86
  87   pool_freewhatprovides(pool);
  88   pool_freeidhashes(pool);
  89   pool_freeallrepos(pool, 1);
  90   solv_free(pool->id2arch);
  91   solv_free(pool->solvables);
  92   stringpool_free(&pool->ss);
  93   solv_free(pool->rels);
  94   pool_setvendorclasses(pool, 0);
  95   queue_free(&pool->vendormap);
  96   for (i = 0; i < POOL_TMPSPACEBUF; i++)
  97     solv_free(pool->tmpspace.buf[i]);
  98   for (i = 0; i < pool->nlanguages; i++)
  99     free((char *)pool->languages[i]);
 100   solv_free(pool->languages);
 101   solv_free(pool->languagecache);
 102   solv_free(pool);
 103 }
 104
 105 void
 106 pool_freeallrepos(Pool *pool, int reuseids)
 107 {
 108   int i;
 109
 110   pool_freewhatprovides(pool);
 111   for (i = 1; i < pool->nrepos; i++)
 112     if (pool->repos[i])
 113       repo_freedata(pool->repos[i]);
 114   pool->repos = solv_free(pool->repos);
 115   pool->nrepos = 0;
 116   pool->urepos = 0;
 117   /* the first two solvables don't belong to a repo */
 118   pool_free_solvable_block(pool, 2, pool->nsolvables - 2, reuseids);
 119 }
 120
 121 #ifdef MULTI_SEMANTICS
 122 void
 123 pool_setdisttype(Pool *pool, int disttype)
 124 {
 125   pool->disttype = disttype;
 126 }
 127 #endif
 128
 129 Id
 130 pool_add_solvable(Pool *pool)
 131 {
 132   pool->solvables = solv_extend(pool->solvables, pool->nsolvables, 1, sizeof(Solvable), SOLVABLE_BLOCK);
 133   memset(pool->solvables + pool->nsolvables, 0, sizeof(Solvable));
 134   return pool->nsolvables++;
 135 }
 136
 137 Id
 138 pool_add_solvable_block(Pool *pool, int count)
 139 {
 140   Id nsolvables = pool->nsolvables;
 141   if (!count)
 142     return nsolvables;
 143   pool->solvables = solv_extend(pool->solvables, pool->nsolvables, count, sizeof(Solvable), SOLVABLE_BLOCK);
 144   memset(pool->solvables + nsolvables, 0, sizeof(Solvable) * count);
 145   pool->nsolvables += count;
 146   return nsolvables;
 147 }
 148
 149 void
 150 pool_free_solvable_block(Pool *pool, Id start, int count, int reuseids)
 151 {
 152   if (!count)
 153     return;
 154   if (reuseids && start + count == pool->nsolvables)
 155     {
 156       /* might want to shrink solvable array */
 157       pool->nsolvables = start;
 158       return;
 159     }
 160   memset(pool->solvables + start, 0, sizeof(Solvable) * count);
 161 }
 162
 163
 164 void
 165 pool_set_installed(Pool *pool, Repo *installed)
 166 {
 167   if (pool->installed == installed)
 168     return;
 169   pool->installed = installed;
 170   pool_freewhatprovides(pool);
 171 }
 172
 173 static int
 174 pool_shrink_whatprovides_sortcmp(const void *ap, const void *bp, void *dp)
 175 {
 176   int r;
 177   Pool *pool = dp;
 178   Id oa, ob, *da, *db;
 179   oa = pool->whatprovides[*(Id *)ap];
 180   ob = pool->whatprovides[*(Id *)bp];
 181   if (oa == ob)
 182     return *(Id *)ap - *(Id *)bp;
 183   if (!oa)
 184     return -1;
 185   if (!ob)
 186     return 1;
 187   da = pool->whatprovidesdata + oa;
 188   db = pool->whatprovidesdata + ob;
 189   while (*db)
 190     if ((r = (*da++ - *db++)) != 0)
 191       return r;
 192   if (*da)
 193     return *da;
 194   return *(Id *)ap - *(Id *)bp;
 195 }
 196
 197 /*
 198  * pool_shrink_whatprovides  - unify whatprovides data
 199  *
 200  * whatprovides_rel must be empty for this to work!
 201  *
 202  */
 203 static void
 204 pool_shrink_whatprovides(Pool *pool)
 205 {
 206   Id i, id;
 207   Id *sorted;
 208   Id lastid, *last, *dp, *lp;
 209   Offset o;
 210   int r;
 211
 212   if (pool->ss.nstrings < 3)
 213     return;
 214   sorted = solv_malloc2(pool->ss.nstrings, sizeof(Id));
 215   for (id = 0; id < pool->ss.nstrings; id++)
 216     sorted[id] = id;
 217   solv_sort(sorted + 1, pool->ss.nstrings - 1, sizeof(Id), pool_shrink_whatprovides_sortcmp, pool);
 218   last = 0;
 219   lastid = 0;
 220   for (i = 1; i < pool->ss.nstrings; i++)
 221     {
 222       id = sorted[i];
 223       o = pool->whatprovides[id];
 224       if (o == 0 || o == 1)
 225         continue;
 226       dp = pool->whatprovidesdata + o;
 227       if (last)
 228         {
 229           lp = last;
 230           while (*dp)
 231             if (*dp++ != *lp++)
 232               {
 233                 last = 0;
 234                 break;
 235               }
 236           if (last && *lp)
 237             last = 0;
 238           if (last)
 239             {
 240               pool->whatprovides[id] = -lastid;
 241               continue;
 242             }
 243         }
 244       last = pool->whatprovidesdata + o;
 245       lastid = id;
 246     }
 247   solv_free(sorted);
 248   dp = pool->whatprovidesdata + 2;
 249   for (id = 1; id < pool->ss.nstrings; id++)
 250     {
 251       o = pool->whatprovides[id];
 252       if (o == 0 || o == 1)
 253         continue;
 254       if ((Id)o < 0)
 255         {
 256           i = -(Id)o;
 257           if (i >= id)
 258             abort();
 259           pool->whatprovides[id] = pool->whatprovides[i];
 260           continue;
 261         }
 262       lp = pool->whatprovidesdata + o;
 263       if (lp < dp)
 264         abort();
 265       pool->whatprovides[id] = dp - pool->whatprovidesdata;
 266       while ((*dp++ = *lp++) != 0)
 267         ;
 268     }
 269   o = dp - pool->whatprovidesdata;
 270   POOL_DEBUG(SOLV_DEBUG_STATS, "shrunk whatprovidesdata from %d to %d\n", pool->whatprovidesdataoff, o);
 271   if (pool->whatprovidesdataoff == o)
 272     return;
 273   r = pool->whatprovidesdataoff - o;
 274   pool->whatprovidesdataoff = o;
 275   pool->whatprovidesdata = solv_realloc(pool->whatprovidesdata, (o + pool->whatprovidesdataleft) * sizeof(Id));
 276   if (r > pool->whatprovidesdataleft)
 277     r = pool->whatprovidesdataleft;
 278   memset(pool->whatprovidesdata + o, 0, r * sizeof(Id));
 279 }
 280
 281
 282 /*
 283  * pool_createwhatprovides()
 284  *
 285  * create hashes over pool of solvables to ease provide lookups
 286  *
 287  */
 288 void
 289 pool_createwhatprovides(Pool *pool)
 290 {
 291   int i, num, np, extra;
 292   Offset off;
 293   Solvable *s;
 294   Id id;
 295   Offset *idp, n;
 296   Offset *whatprovides;
 297   Id *whatprovidesdata, *d;
 298   Repo *installed = pool->installed;
 299   unsigned int now;
 300
 301   now = solv_timems(0);
 302   POOL_DEBUG(SOLV_DEBUG_STATS, "number of solvables: %d\n", pool->nsolvables);
 303   POOL_DEBUG(SOLV_DEBUG_STATS, "number of ids: %d + %d\n", pool->ss.nstrings, pool->nrels);
 304
 305   pool_freeidhashes(pool);      /* XXX: should not be here! */
 306   pool_freewhatprovides(pool);
 307   num = pool->ss.nstrings;
 308   pool->whatprovides = whatprovides = solv_calloc_block(num, sizeof(Offset), WHATPROVIDES_BLOCK);
 309   pool->whatprovides_rel = solv_calloc_block(pool->nrels, sizeof(Offset), WHATPROVIDES_BLOCK);
 310
 311   /* count providers for each name */
 312   for (i = pool->nsolvables - 1; i > 0; i--)
 313     {
 314       Id *pp;
 315       s = pool->solvables + i;
 316       if (!s->provides || !s->repo || s->repo->disabled)
 317         continue;
 318       /* we always need the installed solvable in the whatprovides data,
 319          otherwise obsoletes/conflicts on them won't work */
 320       if (s->repo != installed && !pool_installable(pool, s))
 321         continue;
 322       pp = s->repo->idarraydata + s->provides;
 323       while ((id = *pp++) != 0)
 324         {
 325           while (ISRELDEP(id))
 326             {
 327               Reldep *rd = GETRELDEP(pool, id);
 328               id = rd->name;
 329             }
 330           whatprovides[id]++;          /* inc count of providers */
 331         }
 332     }
 333
 334   off = 2;      /* first entry is undef, second is empty list */
 335   np = 0;                              /* number of names provided */
 336   for (i = 0, idp = whatprovides; i < num; i++, idp++)
 337     {
 338       n = *idp;
 339       if (!n)                          /* no providers */
 340         continue;
 341       off += n;                        /* make space for all providers */
 342       *idp = off++;                    /* now idp points to terminating zero */
 343       np++;                            /* inc # of provider 'slots' for stats */
 344     }
 345
 346   POOL_DEBUG(SOLV_DEBUG_STATS, "provide ids: %d\n", np);
 347
 348   /* reserve some space for relation data */
 349   extra = 2 * pool->nrels;
 350   if (extra < 256)
 351     extra = 256;
 352
 353   POOL_DEBUG(SOLV_DEBUG_STATS, "provide space needed: %d + %d\n", off, extra);
 354
 355   /* alloc space for all providers + extra */
 356   whatprovidesdata = solv_calloc(off + extra, sizeof(Id));
 357
 358   /* now fill data for all provides */
 359   for (i = pool->nsolvables - 1; i > 0; i--)
 360     {
 361       Id *pp;
 362       s = pool->solvables + i;
 363       if (!s->provides || !s->repo || s->repo->disabled)
 364         continue;
 365       if (s->repo != installed && !pool_installable(pool, s))
 366         continue;
 367
 368       /* for all provides of this solvable */
 369       pp = s->repo->idarraydata + s->provides;
 370       while ((id = *pp++) != 0)
 371         {
 372           while (ISRELDEP(id))
 373             {
 374               Reldep *rd = GETRELDEP(pool, id);
 375               id = rd->name;
 376             }
 377           d = whatprovidesdata + whatprovides[id];   /* offset into whatprovidesdata */
 378           if (*d != i)          /* don't add same solvable twice */
 379             {
 380               d[-1] = i;
 381               whatprovides[id]--;
 382             }
 383         }
 384     }
 385   pool->whatprovidesdata = whatprovidesdata;
 386   pool->whatprovidesdataoff = off;
 387   pool->whatprovidesdataleft = extra;
 388   pool_shrink_whatprovides(pool);
 389   POOL_DEBUG(SOLV_DEBUG_STATS, "whatprovides memory used: %d K id array, %d K data\n", (pool->ss.nstrings + pool->nrels + WHATPROVIDES_BLOCK) / (int)(1024/sizeof(Id)), (pool->whatprovidesdataoff + pool->whatprovidesdataleft) / (int)(1024/sizeof(Id)));
 390   POOL_DEBUG(SOLV_DEBUG_STATS, "createwhatprovides took %d ms\n", solv_timems(now));
 391 }
 392
 393 /*
 394  * free all of our whatprovides data
 395  * be careful, everything internalized with pool_queuetowhatprovides is
 396  * gone, too
 397  */
 398 void
 399 pool_freewhatprovides(Pool *pool)
 400 {
 401   pool->whatprovides = solv_free(pool->whatprovides);
 402   pool->whatprovides_rel = solv_free(pool->whatprovides_rel);
 403   pool->whatprovidesdata = solv_free(pool->whatprovidesdata);
 404   pool->whatprovidesdataoff = 0;
 405   pool->whatprovidesdataleft = 0;
 406 }
 407
 408
 409 /******************************************************************************/
 410
 411 /*
 412  * pool_queuetowhatprovides  - add queue contents to whatprovidesdata
 413  *
 414  * on-demand filling of provider information
 415  * move queue data into whatprovidesdata
 416  * q: queue of Ids
 417  * returns: Offset into whatprovides
 418  *
 419  */
 420 Id
 421 pool_queuetowhatprovides(Pool *pool, Queue *q)
 422 {
 423   Offset off;
 424   int count = q->count;
 425
 426   if (count == 0)                      /* queue empty -> 1 */
 427     return 1;
 428
 429   /* extend whatprovidesdata if needed, +1 for ID_NULL-termination */
 430   if (pool->whatprovidesdataleft < count + 1)
 431     {
 432       POOL_DEBUG(SOLV_DEBUG_STATS, "growing provides hash data...\n");
 433       pool->whatprovidesdata = solv_realloc(pool->whatprovidesdata, (pool->whatprovidesdataoff + count + 4096) * sizeof(Id));
 434       pool->whatprovidesdataleft = count + 4096;
 435     }
 436
 437   /* copy queue to next free slot */
 438   off = pool->whatprovidesdataoff;
 439   memcpy(pool->whatprovidesdata + pool->whatprovidesdataoff, q->elements, count * sizeof(Id));
 440
 441   /* adapt count and ID_NULL-terminate */
 442   pool->whatprovidesdataoff += count;
 443   pool->whatprovidesdata[pool->whatprovidesdataoff++] = ID_NULL;
 444   pool->whatprovidesdataleft -= count + 1;
 445
 446   return (Id)off;
 447 }
 448
 449
 450 /*************************************************************************/
 451
 452 #if defined(MULTI_SEMANTICS)
 453 # define EVRCMP_DEPCMP (pool->disttype == DISTTYPE_DEB ? EVRCMP_COMPARE : EVRCMP_MATCH_RELEASE)
 454 #elif defined(DEBIAN_SEMANTICS)
 455 # define EVRCMP_DEPCMP EVRCMP_COMPARE
 456 #else
 457 # define EVRCMP_DEPCMP EVRCMP_MATCH_RELEASE
 458 #endif
 459
 460 /* check if a package's nevr matches a dependency */
 461
 462 int
 463 pool_match_nevr_rel(Pool *pool, Solvable *s, Id d)
 464 {
 465   Reldep *rd = GETRELDEP(pool, d);
 466   Id name = rd->name;
 467   Id evr = rd->evr;
 468   int flags = rd->flags;
 469
 470   if (flags > 7)
 471     {
 472       switch (flags)
 473         {
 474         case REL_ARCH:
 475           if (s->arch != evr)
 476             return 0;
 477           return pool_match_nevr(pool, s, name);
 478         case REL_OR:
 479           if (pool_match_nevr(pool, s, name))
 480             return 1;
 481           return pool_match_nevr(pool, s, evr);
 482         case REL_AND:
 483         case REL_WITH:
 484           if (!pool_match_nevr(pool, s, name))
 485             return 0;
 486           return pool_match_nevr(pool, s, evr);
 487         default:
 488           return 0;
 489         }
 490     }
 491   if (!pool_match_nevr(pool, s, name))
 492     return 0;
 493   if (evr == s->evr)
 494     return flags & 2 ? 1 : 0;
 495   if (!flags)
 496     return 0;
 497   if (flags == 7)
 498     return 1;
 499   if (flags != 2 && flags != 5)
 500     flags ^= 5;
 501   if ((flags & (1 << (1 + pool_evrcmp(pool, s->evr, evr, EVRCMP_DEPCMP)))) != 0)
 502     return 1;
 503   return 0;
 504 }
 505
 506 /* match (flags, evr) against provider (pflags, pevr) */
 507 static inline int
 508 pool_match_flags_evr(Pool *pool, int pflags, Id pevr, int flags, int evr)
 509 {
 510   if (!pflags || !flags || pflags >= 8 || flags >= 8)
 511     return 0;
 512   if (flags == 7 || pflags == 7)
 513     return 1;           /* rel provides every version */
 514   if ((pflags & flags & 5) != 0)
 515     return 1;           /* both rels show in the same direction */
 516   if (pevr == evr)
 517     {
 518       if ((pflags & flags & 2) != 0)
 519         return 1;       /* both have '=', match */
 520     }
 521   else
 522     {
 523       int f = flags == 5 ? 5 : flags == 2 ? pflags : (flags ^ 5) & (pflags | 5);
 524       if ((f & (1 << (1 + pool_evrcmp(pool, pevr, evr, EVRCMP_DEPCMP)))) != 0)
 525         return 1;
 526     }
 527   return 0;
 528 }
 529
 530 /* match two dependencies (d1 = provider) */
 531
 532 int
 533 pool_match_dep(Pool *pool, Id d1, Id d2)
 534 {
 535   Reldep *rd1, *rd2;
 536
 537   if (d1 == d2)
 538     return 1;
 539   if (!ISRELDEP(d1))
 540     {
 541       if (!ISRELDEP(d2))
 542         return 0;
 543       rd2 = GETRELDEP(pool, d2);
 544       return pool_match_dep(pool, d1, rd2->name);
 545     }
 546   rd1 = GETRELDEP(pool, d1);
 547   if (!ISRELDEP(d2))
 548     {
 549       return pool_match_dep(pool, rd1->name, d2);
 550     }
 551   rd2 = GETRELDEP(pool, d2);
 552   /* first match name */
 553   if (!pool_match_dep(pool, rd1->name, rd2->name))
 554     return 0;
 555   /* name matches, check flags and evr */
 556   return pool_match_flags_evr(pool, rd1->flags, rd1->evr, rd2->flags, rd2->evr);
 557 }
 558
 559 /*
 560  * addrelproviders
 561  *
 562  * add packages fulfilling the relation to whatprovides array
 563  * no exact providers, do range match
 564  *
 565  */
 566
 567 Id
 568 pool_addrelproviders(Pool *pool, Id d)
 569 {
 570   Reldep *rd = GETRELDEP(pool, d);
 571   Reldep *prd;
 572   Queue plist;
 573   Id buf[16];
 574   Id name = rd->name;
 575   Id evr = rd->evr;
 576   int flags = rd->flags;
 577   Id pid, *pidp;
 578   Id p, *pp;
 579
 580   d = GETRELID(d);
 581   queue_init_buffer(&plist, buf, sizeof(buf)/sizeof(*buf));
 582
 583   if (flags >= 8)
 584     {
 585       /* special relation */
 586       Id wp = 0;
 587       Id *pp2, *pp3;
 588
 589       switch (flags)
 590         {
 591         case REL_AND:
 592         case REL_WITH:
 593           wp = pool_whatprovides(pool, name);
 594           pp2 = pool_whatprovides_ptr(pool, evr);
 595           pp = pool->whatprovidesdata + wp;
 596           while ((p = *pp++) != 0)
 597             {
 598               for (pp3 = pp2; *pp3; pp3++)
 599                 if (*pp3 == p)
 600                   break;
 601               if (*pp3)
 602                 queue_push(&plist, p);  /* found it */
 603               else
 604                 wp = 0;
 605             }
 606           break;
 607         case REL_OR:
 608           wp = pool_whatprovides(pool, name);
 609           pp = pool->whatprovidesdata + wp;
 610           if (!*pp)
 611             wp = pool_whatprovides(pool, evr);
 612           else
 613             {
 614               int cnt;
 615               while ((p = *pp++) != 0)
 616                 queue_push(&plist, p);
 617               cnt = plist.count;
 618               pp = pool_whatprovides_ptr(pool, evr);
 619               while ((p = *pp++) != 0)
 620                 queue_pushunique(&plist, p);
 621               if (plist.count != cnt)
 622                 wp = 0;
 623             }
 624           break;
 625         case REL_NAMESPACE:
 626           if (name == NAMESPACE_OTHERPROVIDERS)
 627             {
 628               wp = pool_whatprovides(pool, evr);
 629               break;
 630             }
 631           if (pool->nscallback)
 632             {
 633               /* ask callback which packages provide the dependency
 634                * 0:  none
 635                * 1:  the system (aka SYSTEMSOLVABLE)
 636                * >1: set of packages, stored as offset on whatprovidesdata
 637                */
 638               p = pool->nscallback(pool, pool->nscallbackdata, name, evr);
 639               if (p > 1)
 640                 wp = p;
 641               if (p == 1)
 642                 queue_push(&plist, SYSTEMSOLVABLE);
 643             }
 644           break;
 645         case REL_ARCH:
 646           /* small hack: make it possible to match <pkg>.src
 647            * we have to iterate over the solvables as src packages do not
 648            * provide anything, thus they are not indexed in our
 649            * whatprovides hash */
 650           if (evr == ARCH_SRC)
 651             {
 652               Solvable *s;
 653               for (p = 1, s = pool->solvables + p; p < pool->nsolvables; p++, s++)
 654                 {
 655                   if (s->arch != ARCH_SRC && s->arch != ARCH_NOSRC)
 656                     continue;
 657                   if (pool_match_nevr(pool, s, name))
 658                     queue_push(&plist, p);
 659                 }
 660               break;
 661             }
 662           wp = pool_whatprovides(pool, name);
 663           pp = pool->whatprovidesdata + wp;
 664           while ((p = *pp++) != 0)
 665             {
 666               Solvable *s = pool->solvables + p;
 667               if (s->arch == evr)
 668                 queue_push(&plist, p);
 669               else
 670                 wp = 0;
 671             }
 672           break;
 673         case REL_FILECONFLICT:
 674           pp = pool_whatprovides_ptr(pool, name);
 675           while ((p = *pp++) != 0)
 676             {
 677               Id origd = MAKERELDEP(d);
 678               Solvable *s = pool->solvables + p;
 679               if (!s->provides)
 680                 continue;
 681               pidp = s->repo->idarraydata + s->provides;
 682               while ((pid = *pidp++) != 0)
 683                 if (pid == origd)
 684                   break;
 685               if (pid)
 686                 queue_push(&plist, p);
 687             }
 688           break;
 689         default:
 690           break;
 691         }
 692       if (wp)
 693         {
 694           /* we can reuse an existing entry */
 695           queue_free(&plist);
 696           pool->whatprovides_rel[d] = wp;
 697           return wp;
 698         }
 699     }
 700   else if (flags)
 701     {
 702       /* simple version comparison relation */
 703 #if 0
 704       POOL_DEBUG(SOLV_DEBUG_STATS, "addrelproviders: what provides %s?\n", pool_dep2str(pool, name));
 705 #endif
 706       pp = pool_whatprovides_ptr(pool, name);
 707       while (ISRELDEP(name))
 708         {
 709           rd = GETRELDEP(pool, name);
 710           name = rd->name;
 711         }
 712       while ((p = *pp++) != 0)
 713         {
 714           Solvable *s = pool->solvables + p;
 715           if (!s->provides)
 716             {
 717               /* no provides - check nevr */
 718               if (pool_match_nevr_rel(pool, s, MAKERELDEP(d)))
 719                 queue_push(&plist, p);
 720               continue;
 721             }
 722           /* solvable p provides name in some rels */
 723           pidp = s->repo->idarraydata + s->provides;
 724           while ((pid = *pidp++) != 0)
 725             {
 726               if (pid == name)
 727                 {
 728                   if (pool->disttype == DISTTYPE_DEB)
 729                     continue;           /* unversioned provides can never match versioned deps */
 730                   break;
 731                 }
 732               if (!ISRELDEP(pid))
 733                 continue;               /* wrong provides name */
 734               prd = GETRELDEP(pool, pid);
 735               if (prd->name != name)
 736                 continue;               /* wrong provides name */
 737               /* right package, both deps are rels. check flags/evr */
 738               if (pool_match_flags_evr(pool, prd->flags, prd->evr, flags, evr))
 739                 break;  /* matches */
 740             }
 741           if (!pid)
 742             continue;   /* none of the providers matched */
 743           queue_push(&plist, p);
 744         }
 745       /* make our system solvable provide all unknown rpmlib() stuff */
 746       if (plist.count == 0 && !strncmp(pool_id2str(pool, name), "rpmlib(", 7))
 747         queue_push(&plist, SYSTEMSOLVABLE);
 748     }
 749   /* add providers to whatprovides */
 750 #if 0
 751   POOL_DEBUG(SOLV_DEBUG_STATS, "addrelproviders: adding %d packages to %d\n", plist.count, d);
 752 #endif
 753   pool->whatprovides_rel[d] = pool_queuetowhatprovides(pool, &plist);
 754   queue_free(&plist);
 755
 756   return pool->whatprovides_rel[d];
 757 }
 758
 759 /*************************************************************************/
 760
 761 void
 762 pool_debug(Pool *pool, int type, const char *format, ...)
 763 {
 764   va_list args;
 765   char buf[1024];
 766
 767   if ((type & (SOLV_FATAL|SOLV_ERROR)) == 0)
 768     {
 769       if ((pool->debugmask & type) == 0)
 770         return;
 771     }
 772   va_start(args, format);
 773   if (!pool->debugcallback)
 774     {
 775       if ((type & (SOLV_FATAL|SOLV_ERROR)) == 0 && !(pool->debugmask & SOLV_DEBUG_TO_STDERR))
 776         vprintf(format, args);
 777       else
 778         vfprintf(stderr, format, args);
 779       return;
 780     }
 781   vsnprintf(buf, sizeof(buf), format, args);
 782   pool->debugcallback(pool, pool->debugcallbackdata, type, buf);
 783 }
 784
 785 void
 786 pool_setdebuglevel(Pool *pool, int level)
 787 {
 788   int mask = SOLV_DEBUG_RESULT;
 789   if (level > 0)
 790     mask |= SOLV_DEBUG_STATS|SOLV_DEBUG_ANALYZE|SOLV_DEBUG_UNSOLVABLE|SOLV_DEBUG_SOLVER|SOLV_DEBUG_TRANSACTION;
 791   if (level > 1)
 792     mask |= SOLV_DEBUG_JOB|SOLV_DEBUG_SOLUTIONS|SOLV_DEBUG_POLICY;
 793   if (level > 2)
 794     mask |= SOLV_DEBUG_PROPAGATE;
 795   if (level > 3)
 796     mask |= SOLV_DEBUG_RULE_CREATION;
 797   mask |= pool->debugmask & SOLV_DEBUG_TO_STDERR;       /* keep bit */
 798   pool->debugmask = mask;
 799 }
 800
 801 void pool_setdebugcallback(Pool *pool, void (*debugcallback)(struct _Pool *, void *data, int type, const char *str), void *debugcallbackdata)
 802 {
 803   pool->debugcallback = debugcallback;
 804   pool->debugcallbackdata = debugcallbackdata;
 805 }
 806
 807 void pool_setdebugmask(Pool *pool, int mask)
 808 {
 809   pool->debugmask = mask;
 810 }
 811
 812 void pool_setloadcallback(Pool *pool, int (*cb)(struct _Pool *, struct _Repodata *, void *), void *loadcbdata)
 813 {
 814   pool->loadcallback = cb;
 815   pool->loadcallbackdata = loadcbdata;
 816 }
 817
 818 /*************************************************************************/
 819
 820 struct searchfiles {
 821   Id *ids;
 822   char **dirs;
 823   char **names;
 824   int nfiles;
 825   Map seen;
 826 };
 827
 828 #define SEARCHFILES_BLOCK 127
 829
 830 static void
 831 pool_addfileprovides_dep(Pool *pool, Id *ida, struct searchfiles *sf, struct searchfiles *isf)
 832 {
 833   Id dep, sid;
 834   const char *s, *sr;
 835   struct searchfiles *csf;
 836
 837   while ((dep = *ida++) != 0)
 838     {
 839       csf = sf;
 840       while (ISRELDEP(dep))
 841         {
 842           Reldep *rd;
 843           sid = pool->ss.nstrings + GETRELID(dep);
 844           if (MAPTST(&csf->seen, sid))
 845             {
 846               dep = 0;
 847               break;
 848             }
 849           MAPSET(&csf->seen, sid);
 850           rd = GETRELDEP(pool, dep);
 851           if (rd->flags < 8)
 852             dep = rd->name;
 853           else if (rd->flags == REL_NAMESPACE)
 854             {
 855               if (rd->name == NAMESPACE_INSTALLED || rd->name == NAMESPACE_SPLITPROVIDES)
 856                 {
 857                   csf = isf;
 858                   if (!csf || MAPTST(&csf->seen, sid))
 859                     {
 860                       dep = 0;
 861                       break;
 862                     }
 863                   MAPSET(&csf->seen, sid);
 864                 }
 865               dep = rd->evr;
 866             }
 867           else if (rd->flags == REL_FILECONFLICT)
 868             {
 869               dep = 0;
 870               break;
 871             }
 872           else
 873             {
 874               Id ids[2];
 875               ids[0] = rd->name;
 876               ids[1] = 0;
 877               pool_addfileprovides_dep(pool, ids, csf, isf);
 878               dep = rd->evr;
 879             }
 880         }
 881       if (!dep)
 882         continue;
 883       if (MAPTST(&csf->seen, dep))
 884         continue;
 885       MAPSET(&csf->seen, dep);
 886       s = pool_id2str(pool, dep);
 887       if (*s != '/')
 888         continue;
 889       csf->ids = solv_extend(csf->ids, csf->nfiles, 1, sizeof(Id), SEARCHFILES_BLOCK);
 890       csf->dirs = solv_extend(csf->dirs, csf->nfiles, 1, sizeof(const char *), SEARCHFILES_BLOCK);
 891       csf->names = solv_extend(csf->names, csf->nfiles, 1, sizeof(const char *), SEARCHFILES_BLOCK);
 892       csf->ids[csf->nfiles] = dep;
 893       sr = strrchr(s, '/');
 894       csf->names[csf->nfiles] = solv_strdup(sr + 1);
 895       csf->dirs[csf->nfiles] = solv_malloc(sr - s + 1);
 896       if (sr != s)
 897         strncpy(csf->dirs[csf->nfiles], s, sr - s);
 898       csf->dirs[csf->nfiles][sr - s] = 0;
 899       csf->nfiles++;
 900     }
 901 }
 902
 903 struct addfileprovides_cbdata {
 904   int nfiles;
 905   Id *ids;
 906   char **dirs;
 907   char **names;
 908
 909   Id *dids;
 910
 911   Map providedids;
 912
 913   Map useddirs;
 914 };
 915
 916 static int
 917 addfileprovides_cb(void *cbdata, Solvable *s, Repodata *data, Repokey *key, KeyValue *value)
 918 {
 919   struct addfileprovides_cbdata *cbd = cbdata;
 920   int i;
 921
 922   if (!cbd->useddirs.size)
 923     {
 924       map_init(&cbd->useddirs, data->dirpool.ndirs + 1);
 925       for (i = 0; i < cbd->nfiles; i++)
 926         {
 927           Id did;
 928           if (MAPTST(&cbd->providedids, cbd->ids[i]))
 929             {
 930               cbd->dids[i] = 0;
 931               continue;
 932             }
 933           did = repodata_str2dir(data, cbd->dirs[i], 0);
 934           cbd->dids[i] = did;
 935           if (did)
 936             MAPSET(&cbd->useddirs, did);
 937         }
 938     }
 939   if (value->id >= data->dirpool.ndirs || !MAPTST(&cbd->useddirs, value->id))
 940     return 0;
 941   for (i = 0; i < cbd->nfiles; i++)
 942     {
 943       if (cbd->dids[i] != value->id)
 944         continue;
 945       if (!strcmp(cbd->names[i], value->str))
 946         break;
 947     }
 948   if (i == cbd->nfiles)
 949     return 0;
 950   s->provides = repo_addid_dep(s->repo, s->provides, cbd->ids[i], SOLVABLE_FILEMARKER);
 951   return 0;
 952 }
 953
 954 static void
 955 pool_addfileprovides_search(Pool *pool, struct addfileprovides_cbdata *cbd, struct searchfiles *sf, Repo *repoonly)
 956 {
 957   Id p;
 958   Repodata *data;
 959   Repo *repo;
 960   Queue fileprovidesq;
 961   int i, j, repoid, repodataid;
 962   int provstart, provend;
 963   Map donemap;
 964   int ndone, incomplete;
 965
 966   if (!pool->urepos)
 967     return;
 968
 969   cbd->nfiles = sf->nfiles;
 970   cbd->ids = sf->ids;
 971   cbd->dirs = sf->dirs;
 972   cbd->names = sf->names;
 973   cbd->dids = solv_realloc2(cbd->dids, sf->nfiles, sizeof(Id));
 974   map_init(&cbd->providedids, pool->ss.nstrings);
 975
 976   repoid = 1;
 977   repo = repoonly ? repoonly : pool->repos[repoid];
 978   map_init(&donemap, pool->nsolvables);
 979   queue_init(&fileprovidesq);
 980   provstart = provend = 0;
 981   for (;;)
 982     {
 983       if (!repo || repo->disabled)
 984         {
 985           if (repoonly || ++repoid == pool->nrepos)
 986             break;
 987           repo = pool->repos[repoid];
 988           continue;
 989         }
 990       ndone = 0;
 991       FOR_REPODATAS(repo, repodataid, data)
 992         {
 993           if (ndone >= repo->nsolvables)
 994             break;
 995
 996           if (repodata_lookup_idarray(data, SOLVID_META, REPOSITORY_ADDEDFILEPROVIDES, &fileprovidesq))
 997             {
 998               map_empty(&cbd->providedids);
 999               for (i = 0; i < fileprovidesq.count; i++)
1000                 MAPSET(&cbd->providedids, fileprovidesq.elements[i]);
1001               provstart = data->start;
1002               provend = data->end;
1003               for (i = 0; i < cbd->nfiles; i++)
1004                 if (!MAPTST(&cbd->providedids, cbd->ids[i]))
1005                   break;
1006               if (i == cbd->nfiles)
1007                 {
1008                   /* great! no need to search files */
1009                   for (p = data->start; p < data->end; p++)
1010                     if (pool->solvables[p].repo == repo)
1011                       {
1012                         if (MAPTST(&donemap, p))
1013                           continue;
1014                         MAPSET(&donemap, p);
1015                         ndone++;
1016                       }
1017                   continue;
1018                 }
1019             }
1020
1021           if (!repodata_has_keyname(data, SOLVABLE_FILELIST))
1022             continue;
1023
1024           if (data->start < provstart || data->end > provend)
1025             {
1026               map_empty(&cbd->providedids);
1027               provstart = provend = 0;
1028             }
1029
1030           /* check if the data is incomplete */
1031           incomplete = 0;
1032           if (data->state == REPODATA_AVAILABLE)
1033             {
1034               for (j = 1; j < data->nkeys; j++)
1035                 if (data->keys[j].name != REPOSITORY_SOLVABLES && data->keys[j].name != SOLVABLE_FILELIST)
1036                   break;
1037               if (j < data->nkeys)
1038                 {
1039 #if 0
1040                   for (i = 0; i < cbd->nfiles; i++)
1041                     if (!MAPTST(&cbd->providedids, cbd->ids[i]) && !repodata_filelistfilter_matches(data, pool_id2str(pool, cbd->ids[i])))
1042                       printf("need complete filelist because of %s\n", pool_id2str(pool, cbd->ids[i]));
1043 #endif
1044                   for (i = 0; i < cbd->nfiles; i++)
1045                     if (!MAPTST(&cbd->providedids, cbd->ids[i]) && !repodata_filelistfilter_matches(data, pool_id2str(pool, cbd->ids[i])))
1046                       break;
1047                   if (i < cbd->nfiles)
1048                     incomplete = 1;
1049                 }
1050             }
1051
1052           /* do the search */
1053           map_init(&cbd->useddirs, 0);
1054           for (p = data->start; p < data->end; p++)
1055             if (pool->solvables[p].repo == repo)
1056               {
1057                 if (MAPTST(&donemap, p))
1058                   continue;
1059                 repodata_search(data, p, SOLVABLE_FILELIST, 0, addfileprovides_cb, cbd);
1060                 if (!incomplete)
1061                   {
1062                     MAPSET(&donemap, p);
1063                     ndone++;
1064                   }
1065               }
1066           map_free(&cbd->useddirs);
1067         }
1068
1069       if (repoonly || ++repoid == pool->nrepos)
1070         break;
1071       repo = pool->repos[repoid];
1072     }
1073   map_free(&donemap);
1074   queue_free(&fileprovidesq);
1075   map_free(&cbd->providedids);
1076 }
1077
1078 void
1079 pool_addfileprovides_queue(Pool *pool, Queue *idq)
1080 {
1081   Solvable *s;
1082   Repo *installed, *repo;
1083   struct searchfiles sf, isf, *isfp;
1084   struct addfileprovides_cbdata cbd;
1085   int i;
1086   unsigned int now;
1087
1088   installed = pool->installed;
1089   now = solv_timems(0);
1090   memset(&sf, 0, sizeof(sf));
1091   map_init(&sf.seen, pool->ss.nstrings + pool->nrels);
1092   memset(&isf, 0, sizeof(isf));
1093   map_init(&isf.seen, pool->ss.nstrings + pool->nrels);
1094
1095   if (idq)
1096     queue_empty(idq);
1097   isfp = installed ? &isf : 0;
1098   for (i = 1, s = pool->solvables + i; i < pool->nsolvables; i++, s++)
1099     {
1100       repo = s->repo;
1101       if (!repo)
1102         continue;
1103       if (s->obsoletes)
1104         pool_addfileprovides_dep(pool, repo->idarraydata + s->obsoletes, &sf, isfp);
1105       if (s->conflicts)
1106         pool_addfileprovides_dep(pool, repo->idarraydata + s->conflicts, &sf, isfp);
1107       if (s->requires)
1108         pool_addfileprovides_dep(pool, repo->idarraydata + s->requires, &sf, isfp);
1109       if (s->recommends)
1110         pool_addfileprovides_dep(pool, repo->idarraydata + s->recommends, &sf, isfp);
1111       if (s->suggests)
1112         pool_addfileprovides_dep(pool, repo->idarraydata + s->suggests, &sf, isfp);
1113       if (s->supplements)
1114         pool_addfileprovides_dep(pool, repo->idarraydata + s->supplements, &sf, isfp);
1115       if (s->enhances)
1116         pool_addfileprovides_dep(pool, repo->idarraydata + s->enhances, &sf, isfp);
1117     }
1118   map_free(&sf.seen);
1119   map_free(&isf.seen);
1120   POOL_DEBUG(SOLV_DEBUG_STATS, "found %d file dependencies, %d installed file dependencies\n", sf.nfiles, isf.nfiles);
1121   cbd.dids = 0;
1122   if (sf.nfiles)
1123     {
1124 #if 0
1125       for (i = 0; i < sf.nfiles; i++)
1126         POOL_DEBUG(SOLV_DEBUG_STATS, "looking up %s in filelist\n", pool_id2str(pool, sf.ids[i]));
1127 #endif
1128       pool_addfileprovides_search(pool, &cbd, &sf, 0);
1129       if (idq)
1130         for (i = 0; i < sf.nfiles; i++)
1131           queue_push(idq, sf.ids[i]);
1132       solv_free(sf.ids);
1133       for (i = 0; i < sf.nfiles; i++)
1134         {
1135           solv_free(sf.dirs[i]);
1136           solv_free(sf.names[i]);
1137         }
1138       solv_free(sf.dirs);
1139       solv_free(sf.names);
1140     }
1141   if (isf.nfiles)
1142     {
1143 #if 0
1144       for (i = 0; i < isf.nfiles; i++)
1145         POOL_DEBUG(SOLV_DEBUG_STATS, "looking up %s in installed filelist\n", pool_id2str(pool, isf.ids[i]));
1146 #endif
1147       if (installed)
1148         pool_addfileprovides_search(pool, &cbd, &isf, installed);
1149       solv_free(isf.ids);
1150       for (i = 0; i < isf.nfiles; i++)
1151         {
1152           solv_free(isf.dirs[i]);
1153           solv_free(isf.names[i]);
1154         }
1155       solv_free(isf.dirs);
1156       solv_free(isf.names);
1157     }
1158   solv_free(cbd.dids);
1159   pool_freewhatprovides(pool);  /* as we have added provides */
1160   POOL_DEBUG(SOLV_DEBUG_STATS, "addfileprovides took %d ms\n", solv_timems(now));
1161 }
1162
1163 void
1164 pool_addfileprovides(Pool *pool)
1165 {
1166   pool_addfileprovides_queue(pool, 0);
1167 }
1168
1169 void
1170 pool_search(Pool *pool, Id p, Id key, const char *match, int flags, int (*callback)(void *cbdata, Solvable *s, struct _Repodata *data, struct _Repokey *key, struct _KeyValue *kv), void *cbdata)
1171 {
1172   if (p)
1173     {
1174       if (pool->solvables[p].repo)
1175         repo_search(pool->solvables[p].repo, p, key, match, flags, callback, cbdata);
1176       return;
1177     }
1178   /* FIXME: obey callback return value! */
1179   for (p = 1; p < pool->nsolvables; p++)
1180     if (pool->solvables[p].repo)
1181       repo_search(pool->solvables[p].repo, p, key, match, flags, callback, cbdata);
1182 }
1183
1184 void
1185 pool_clear_pos(Pool *pool)
1186 {
1187   memset(&pool->pos, 0, sizeof(pool->pos));
1188 }
1189
1190
1191 void
1192 pool_set_languages(Pool *pool, const char **languages, int nlanguages)
1193 {
1194   int i;
1195
1196   pool->languagecache = solv_free(pool->languagecache);
1197   pool->languagecacheother = 0;
1198   if (pool->nlanguages)
1199     {
1200       for (i = 0; i < pool->nlanguages; i++)
1201         free((char *)pool->languages[i]);
1202       free(pool->languages);
1203     }
1204   pool->nlanguages = nlanguages;
1205   if (!nlanguages)
1206     return;
1207   pool->languages = solv_calloc(nlanguages, sizeof(const char **));
1208   for (i = 0; i < pool->nlanguages; i++)
1209     pool->languages[i] = solv_strdup(languages[i]);
1210 }
1211
1212 Id
1213 pool_id2langid(Pool *pool, Id id, const char *lang, int create)
1214 {
1215   const char *n;
1216   char buf[256], *p;
1217   int l;
1218
1219   if (!lang || !*lang)
1220     return id;
1221   n = pool_id2str(pool, id);
1222   l = strlen(n) + strlen(lang) + 2;
1223   if (l > sizeof(buf))
1224     p = solv_malloc(strlen(n) + strlen(lang) + 2);
1225   else
1226     p = buf;
1227   sprintf(p, "%s:%s", n, lang);
1228   id = pool_str2id(pool, p, create);
1229   if (p != buf)
1230     free(p);
1231   return id;
1232 }
1233
1234 char *
1235 pool_alloctmpspace(Pool *pool, int len)
1236 {
1237   int n = pool->tmpspace.n;
1238   if (!len)
1239     return 0;
1240   if (len > pool->tmpspace.len[n])
1241     {
1242       pool->tmpspace.buf[n] = solv_realloc(pool->tmpspace.buf[n], len + 32);
1243       pool->tmpspace.len[n] = len + 32;
1244     }
1245   pool->tmpspace.n = (n + 1) % POOL_TMPSPACEBUF;
1246   return pool->tmpspace.buf[n];
1247 }
1248
1249 static char *
1250 pool_alloctmpspace_free(Pool *pool, const char *space, int len)
1251 {
1252   if (space)
1253     {
1254       int n, oldn;
1255       n = oldn = pool->tmpspace.n;
1256       for (;;)
1257         {
1258           if (!n--)
1259             n = POOL_TMPSPACEBUF - 1;
1260           if (n == oldn)
1261             break;
1262           if (pool->tmpspace.buf[n] != space)
1263             continue;
1264           if (len > pool->tmpspace.len[n])
1265             {
1266               pool->tmpspace.buf[n] = solv_realloc(pool->tmpspace.buf[n], len + 32);
1267               pool->tmpspace.len[n] = len + 32;
1268             }
1269           return pool->tmpspace.buf[n];
1270         }
1271     }
1272   return 0;
1273 }
1274
1275 void
1276 pool_freetmpspace(Pool *pool, const char *space)
1277 {
1278   int n = pool->tmpspace.n;
1279   if (!space)
1280     return;
1281   n = (n + (POOL_TMPSPACEBUF - 1)) % POOL_TMPSPACEBUF;
1282   if (pool->tmpspace.buf[n] == space)
1283     pool->tmpspace.n = n;
1284 }
1285
1286 char *
1287 pool_tmpjoin(Pool *pool, const char *str1, const char *str2, const char *str3)
1288 {
1289   int l1, l2, l3;
1290   char *s, *str;
1291   l1 = str1 ? strlen(str1) : 0;
1292   l2 = str2 ? strlen(str2) : 0;
1293   l3 = str3 ? strlen(str3) : 0;
1294   s = str = pool_alloctmpspace(pool, l1 + l2 + l3 + 1);
1295   if (l1)
1296     {
1297       strcpy(s, str1);
1298       s += l1;
1299     }
1300   if (l2)
1301     {
1302       strcpy(s, str2);
1303       s += l2;
1304     }
1305   if (l3)
1306     {
1307       strcpy(s, str3);
1308       s += l3;
1309     }
1310   *s = 0;
1311   return str;
1312 }
1313
1314 char *
1315 pool_tmpappend(Pool *pool, const char *str1, const char *str2, const char *str3)
1316 {
1317   int l1, l2, l3;
1318   char *s, *str;
1319
1320   l1 = str1 ? strlen(str1) : 0;
1321   l2 = str2 ? strlen(str2) : 0;
1322   l3 = str3 ? strlen(str3) : 0;
1323   str = pool_alloctmpspace_free(pool, str1, l1 + l2 + l3 + 1);
1324   if (str)
1325     str1 = str;
1326   else
1327     str = pool_alloctmpspace(pool, l1 + l2 + l3 + 1);
1328   s = str;
1329   if (l1)
1330     {
1331       if (s != str1)
1332         strcpy(s, str1);
1333       s += l1;
1334     }
1335   if (l2)
1336     {
1337       strcpy(s, str2);
1338       s += l2;
1339     }
1340   if (l3)
1341     {
1342       strcpy(s, str3);
1343       s += l3;
1344     }
1345   *s = 0;
1346   return str;
1347 }
1348
1349 const char *
1350 pool_bin2hex(Pool *pool, const unsigned char *buf, int len)
1351 {
1352   char *s;
1353   if (!len)
1354     return "";
1355   s = pool_alloctmpspace(pool, 2 * len + 1);
1356   solv_bin2hex(buf, len, s);
1357   return s;
1358 }
1359
1360 /*******************************************************************/
1361
1362 struct mptree {
1363   Id sibling;
1364   Id child;
1365   const char *comp;
1366   int compl;
1367   Id mountpoint;
1368 };
1369
1370 struct ducbdata {
1371   DUChanges *mps;
1372   struct mptree *mptree;
1373   int addsub;
1374   int hasdu;
1375
1376   Id *dirmap;
1377   int nmap;
1378   Repodata *olddata;
1379 };
1380
1381
1382 static int
1383 solver_fill_DU_cb(void *cbdata, Solvable *s, Repodata *data, Repokey *key, KeyValue *value)
1384 {
1385   struct ducbdata *cbd = cbdata;
1386   Id mp;
1387
1388   if (data != cbd->olddata)
1389     {
1390       Id dn, mp, comp, *dirmap, *dirs;
1391       int i, compl;
1392       const char *compstr;
1393       struct mptree *mptree;
1394
1395       /* create map from dir to mptree */
1396       cbd->dirmap = solv_free(cbd->dirmap);
1397       cbd->nmap = 0;
1398       dirmap = solv_calloc(data->dirpool.ndirs, sizeof(Id));
1399       mptree = cbd->mptree;
1400       mp = 0;
1401       for (dn = 2, dirs = data->dirpool.dirs + dn; dn < data->dirpool.ndirs; dn++)
1402         {
1403           comp = *dirs++;
1404           if (comp <= 0)
1405             {
1406               mp = dirmap[-comp];
1407               continue;
1408             }
1409           if (mp < 0)
1410             {
1411               /* unconnected */
1412               dirmap[dn] = mp;
1413               continue;
1414             }
1415           if (!mptree[mp].child)
1416             {
1417               dirmap[dn] = -mp;
1418               continue;
1419             }
1420           if (data->localpool)
1421             compstr = stringpool_id2str(&data->spool, comp);
1422           else
1423             compstr = pool_id2str(data->repo->pool, comp);
1424           compl = strlen(compstr);
1425           for (i = mptree[mp].child; i; i = mptree[i].sibling)
1426             if (mptree[i].compl == compl && !strncmp(mptree[i].comp, compstr, compl))
1427               break;
1428           dirmap[dn] = i ? i : -mp;
1429         }
1430       /* change dirmap to point to mountpoint instead of mptree */
1431       for (dn = 0; dn < data->dirpool.ndirs; dn++)
1432         {
1433           mp = dirmap[dn];
1434           dirmap[dn] = mptree[mp > 0 ? mp : -mp].mountpoint;
1435         }
1436       cbd->dirmap = dirmap;
1437       cbd->nmap = data->dirpool.ndirs;
1438       cbd->olddata = data;
1439     }
1440   cbd->hasdu = 1;
1441   if (value->id < 0 || value->id >= cbd->nmap)
1442     return 0;
1443   mp = cbd->dirmap[value->id];
1444   if (mp < 0)
1445     return 0;
1446   if (cbd->addsub > 0)
1447     {
1448       cbd->mps[mp].kbytes += value->num;
1449       cbd->mps[mp].files += value->num2;
1450     }
1451   else
1452     {
1453       cbd->mps[mp].kbytes -= value->num;
1454       cbd->mps[mp].files -= value->num2;
1455     }
1456   return 0;
1457 }
1458
1459 static void
1460 propagate_mountpoints(struct mptree *mptree, int pos, Id mountpoint)
1461 {
1462   int i;
1463   if (mptree[pos].mountpoint == -1)
1464     mptree[pos].mountpoint = mountpoint;
1465   else
1466     mountpoint = mptree[pos].mountpoint;
1467   for (i = mptree[pos].child; i; i = mptree[i].sibling)
1468     propagate_mountpoints(mptree, i, mountpoint);
1469 }
1470
1471 #define MPTREE_BLOCK 15
1472
1473 void
1474 pool_calc_duchanges(Pool *pool, Map *installedmap, DUChanges *mps, int nmps)
1475 {
1476   char *p;
1477   const char *path, *compstr;
1478   struct mptree *mptree;
1479   int i, nmptree;
1480   int pos, compl;
1481   int mp;
1482   struct ducbdata cbd;
1483   Solvable *s;
1484   Id sp;
1485   Map ignoredu;
1486   Repo *oldinstalled = pool->installed;
1487
1488   memset(&ignoredu, 0, sizeof(ignoredu));
1489   cbd.mps = mps;
1490   cbd.addsub = 0;
1491   cbd.dirmap = 0;
1492   cbd.nmap = 0;
1493   cbd.olddata = 0;
1494
1495   mptree = solv_extend_resize(0, 1, sizeof(struct mptree), MPTREE_BLOCK);
1496
1497   /* our root node */
1498   mptree[0].sibling = 0;
1499   mptree[0].child = 0;
1500   mptree[0].comp = 0;
1501   mptree[0].compl = 0;
1502   mptree[0].mountpoint = -1;
1503   nmptree = 1;
1504
1505   /* create component tree */
1506   for (mp = 0; mp < nmps; mp++)
1507     {
1508       mps[mp].kbytes = 0;
1509       mps[mp].files = 0;
1510       pos = 0;
1511       path = mps[mp].path;
1512       while(*path == '/')
1513         path++;
1514       while (*path)
1515         {
1516           if ((p = strchr(path, '/')) == 0)
1517             {
1518               compstr = path;
1519               compl = strlen(compstr);
1520               path += compl;
1521             }
1522           else
1523             {
1524               compstr = path;
1525               compl = p - path;
1526               path = p + 1;
1527               while(*path == '/')
1528                 path++;
1529             }
1530           for (i = mptree[pos].child; i; i = mptree[i].sibling)
1531             if (mptree[i].compl == compl && !strncmp(mptree[i].comp, compstr, compl))
1532               break;
1533           if (!i)
1534             {
1535               /* create new node */
1536               mptree = solv_extend(mptree, nmptree, 1, sizeof(struct mptree), MPTREE_BLOCK);
1537               i = nmptree++;
1538               mptree[i].sibling = mptree[pos].child;
1539               mptree[i].child = 0;
1540               mptree[i].comp = compstr;
1541               mptree[i].compl = compl;
1542               mptree[i].mountpoint = -1;
1543               mptree[pos].child = i;
1544             }
1545           pos = i;
1546         }
1547       mptree[pos].mountpoint = mp;
1548     }
1549
1550   propagate_mountpoints(mptree, 0, mptree[0].mountpoint);
1551
1552 #if 0
1553   for (i = 0; i < nmptree; i++)
1554     {
1555       printf("#%d sibling: %d\n", i, mptree[i].sibling);
1556       printf("#%d child: %d\n", i, mptree[i].child);
1557       printf("#%d comp: %s\n", i, mptree[i].comp);
1558       printf("#%d compl: %d\n", i, mptree[i].compl);
1559       printf("#%d mountpont: %d\n", i, mptree[i].mountpoint);
1560     }
1561 #endif
1562
1563   cbd.mptree = mptree;
1564   cbd.addsub = 1;
1565   for (sp = 1, s = pool->solvables + sp; sp < pool->nsolvables; sp++, s++)
1566     {
1567       if (!s->repo || (oldinstalled && s->repo == oldinstalled))
1568         continue;
1569       if (!MAPTST(installedmap, sp))
1570         continue;
1571       cbd.hasdu = 0;
1572       repo_search(s->repo, sp, SOLVABLE_DISKUSAGE, 0, 0, solver_fill_DU_cb, &cbd);
1573       if (!cbd.hasdu && oldinstalled)
1574         {
1575           Id op, opp;
1576           /* no du data available, ignore data of all installed solvables we obsolete */
1577           if (!ignoredu.map)
1578             map_init(&ignoredu, oldinstalled->end - oldinstalled->start);
1579           if (s->obsoletes)
1580             {
1581               Id obs, *obsp = s->repo->idarraydata + s->obsoletes;
1582               while ((obs = *obsp++) != 0)
1583                 FOR_PROVIDES(op, opp, obs)
1584                   if (op >= oldinstalled->start && op < oldinstalled->end)
1585                     MAPSET(&ignoredu, op - oldinstalled->start);
1586             }
1587           FOR_PROVIDES(op, opp, s->name)
1588             if (pool->solvables[op].name == s->name)
1589               if (op >= oldinstalled->start && op < oldinstalled->end)
1590                 MAPSET(&ignoredu, op - oldinstalled->start);
1591         }
1592     }
1593   cbd.addsub = -1;
1594   if (oldinstalled)
1595     {
1596       /* assumes we allways have du data for installed solvables */
1597       FOR_REPO_SOLVABLES(oldinstalled, sp, s)
1598         {
1599           if (MAPTST(installedmap, sp))
1600             continue;
1601           if (ignoredu.map && MAPTST(&ignoredu, sp - oldinstalled->start))
1602             continue;
1603           repo_search(oldinstalled, sp, SOLVABLE_DISKUSAGE, 0, 0, solver_fill_DU_cb, &cbd);
1604         }
1605     }
1606   if (ignoredu.map)
1607     map_free(&ignoredu);
1608   solv_free(cbd.dirmap);
1609   solv_free(mptree);
1610 }
1611
1612 int
1613 pool_calc_installsizechange(Pool *pool, Map *installedmap)
1614 {
1615   Id sp;
1616   Solvable *s;
1617   int change = 0;
1618   Repo *oldinstalled = pool->installed;
1619
1620   for (sp = 1, s = pool->solvables + sp; sp < pool->nsolvables; sp++, s++)
1621     {
1622       if (!s->repo || (oldinstalled && s->repo == oldinstalled))
1623         continue;
1624       if (!MAPTST(installedmap, sp))
1625         continue;
1626       change += solvable_lookup_num(s, SOLVABLE_INSTALLSIZE, 0);
1627     }
1628   if (oldinstalled)
1629     {
1630       FOR_REPO_SOLVABLES(oldinstalled, sp, s)
1631         {
1632           if (MAPTST(installedmap, sp))
1633             continue;
1634           change -= solvable_lookup_num(s, SOLVABLE_INSTALLSIZE, 0);
1635         }
1636     }
1637   return change;
1638 }
1639
1640 /* map:
1641  *  1: installed
1642  *  2: conflicts with installed
1643  *  8: interesting (only true if installed)
1644  * 16: undecided
1645  */
1646
1647 static inline Id dep2name(Pool *pool, Id dep)
1648 {
1649   while (ISRELDEP(dep))
1650     {
1651       Reldep *rd = rd = GETRELDEP(pool, dep);
1652       dep = rd->name;
1653     }
1654   return dep;
1655 }
1656
1657 static int providedbyinstalled_multiversion(Pool *pool, unsigned char *map, Id n, Id con)
1658 {
1659   Id p, pp;
1660   Solvable *sn = pool->solvables + n;
1661
1662   FOR_PROVIDES(p, pp, sn->name)
1663     {
1664       Solvable *s = pool->solvables + p;
1665       if (s->name != sn->name || s->arch != sn->arch)
1666         continue;
1667       if ((map[p] & 9) != 9)
1668         continue;
1669       if (pool_match_nevr(pool, pool->solvables + p, con))
1670         continue;
1671       return 1;         /* found installed package that doesn't conflict */
1672     }
1673   return 0;
1674 }
1675
1676 static inline int providedbyinstalled(Pool *pool, unsigned char *map, Id dep, int ispatch, Map *noobsoletesmap)
1677 {
1678   Id p, pp;
1679   int r = 0;
1680   FOR_PROVIDES(p, pp, dep)
1681     {
1682       if (p == SYSTEMSOLVABLE)
1683         return 1;       /* always boring, as never constraining */
1684       if (ispatch && !pool_match_nevr(pool, pool->solvables + p, dep))
1685         continue;
1686       if (ispatch && noobsoletesmap && noobsoletesmap->size && MAPTST(noobsoletesmap, p) && ISRELDEP(dep))
1687         if (providedbyinstalled_multiversion(pool, map, p, dep))
1688           continue;
1689       if ((map[p] & 9) == 9)
1690         return 9;
1691       r |= map[p] & 17;
1692     }
1693   return r;
1694 }
1695
1696 /*
1697  * pool_trivial_installable - calculate if a set of solvables is
1698  * trivial installable without any other installs/deinstalls of
1699  * packages not belonging to the set.
1700  *
1701  * the state is returned in the result queue:
1702  * 1:  solvable is installable without any other package changes
1703  * 0:  solvable is not installable
1704  * -1: solvable is installable, but doesn't constrain any installed packages
1705  */
1706
1707 void
1708 pool_trivial_installable_noobsoletesmap(Pool *pool, Map *installedmap, Queue *pkgs, Queue *res, Map *noobsoletesmap)
1709 {
1710   int i, r, m, did;
1711   Id p, *dp, con, *conp, req, *reqp;
1712   unsigned char *map;
1713   Solvable *s;
1714
1715   map = solv_calloc(pool->nsolvables, 1);
1716   for (p = 1; p < pool->nsolvables; p++)
1717     {
1718       if (!MAPTST(installedmap, p))
1719         continue;
1720       map[p] |= 9;
1721       s = pool->solvables + p;
1722       if (!s->conflicts)
1723         continue;
1724       conp = s->repo->idarraydata + s->conflicts;
1725       while ((con = *conp++) != 0)
1726         {
1727           dp = pool_whatprovides_ptr(pool, con);
1728           for (; *dp; dp++)
1729             map[p] |= 2;        /* XXX: self conflict ? */
1730         }
1731     }
1732   for (i = 0; i < pkgs->count; i++)
1733     map[pkgs->elements[i]] = 16;
1734
1735   for (i = 0, did = 0; did < pkgs->count; i++, did++)
1736     {
1737       if (i == pkgs->count)
1738         i = 0;
1739       p = pkgs->elements[i];
1740       if ((map[p] & 16) == 0)
1741         continue;
1742       if ((map[p] & 2) != 0)
1743         {
1744           map[p] = 2;
1745           continue;
1746         }
1747       s = pool->solvables + p;
1748       m = 1;
1749       if (s->requires)
1750         {
1751           reqp = s->repo->idarraydata + s->requires;
1752           while ((req = *reqp++) != 0)
1753             {
1754               if (req == SOLVABLE_PREREQMARKER)
1755                 continue;
1756               r = providedbyinstalled(pool, map, req, 0, 0);
1757               if (!r)
1758                 {
1759                   /* decided and miss */
1760                   map[p] = 2;
1761                   break;
1762                 }
1763               m |= r;   /* 1 | 9 | 16 | 17 */
1764             }
1765           if (req)
1766             continue;
1767           if ((m & 9) == 9)
1768             m = 9;
1769         }
1770       if (s->conflicts)
1771         {
1772           int ispatch = 0;      /* see solver.c patch handling */
1773
1774           if (!strncmp("patch:", pool_id2str(pool, s->name), 6))
1775             ispatch = 1;
1776           conp = s->repo->idarraydata + s->conflicts;
1777           while ((con = *conp++) != 0)
1778             {
1779               if ((providedbyinstalled(pool, map, con, ispatch, noobsoletesmap) & 1) != 0)
1780                 {
1781                   map[p] = 2;
1782                   break;
1783                 }
1784               if ((m == 1 || m == 17) && ISRELDEP(con))
1785                 {
1786                   con = dep2name(pool, con);
1787                   if ((providedbyinstalled(pool, map, con, ispatch, noobsoletesmap) & 1) != 0)
1788                     m = 9;
1789                 }
1790             }
1791           if (con)
1792             continue;   /* found a conflict */
1793         }
1794 #if 0
1795       if (s->repo && s->repo != oldinstalled)
1796         {
1797           Id p2, obs, *obsp, *pp;
1798           Solvable *s2;
1799           if (s->obsoletes)
1800             {
1801               obsp = s->repo->idarraydata + s->obsoletes;
1802               while ((obs = *obsp++) != 0)
1803                 {
1804                   if ((providedbyinstalled(pool, map, obs, 0, 0) & 1) != 0)
1805                     {
1806                       map[p] = 2;
1807                       break;
1808                     }
1809                 }
1810               if (obs)
1811                 continue;
1812             }
1813           FOR_PROVIDES(p2, pp, s->name)
1814             {
1815               s2 = pool->solvables + p2;
1816               if (s2->name == s->name && (map[p2] & 1) != 0)
1817                 {
1818                   map[p] = 2;
1819                   break;
1820                 }
1821             }
1822           if (p2)
1823             continue;
1824         }
1825 #endif
1826       if (m != map[p])
1827         {
1828           map[p] = m;
1829           did = 0;
1830         }
1831     }
1832   queue_free(res);
1833   queue_init_clone(res, pkgs);
1834   for (i = 0; i < pkgs->count; i++)
1835     {
1836       m = map[pkgs->elements[i]];
1837       if ((m & 9) == 9)
1838         r = 1;
1839       else if (m & 1)
1840         r = -1;
1841       else
1842         r = 0;
1843       res->elements[i] = r;
1844     }
1845   free(map);
1846 }
1847
1848 void
1849 pool_trivial_installable(Pool *pool, Map *installedmap, Queue *pkgs, Queue *res)
1850 {
1851   pool_trivial_installable_noobsoletesmap(pool, installedmap, pkgs, res, 0);
1852 }
1853
1854 const char *
1855 pool_lookup_str(Pool *pool, Id entry, Id keyname)
1856 {
1857   if (entry == SOLVID_POS && pool->pos.repo)
1858     return repodata_lookup_str(pool->pos.repo->repodata + pool->pos.repodataid, SOLVID_POS, keyname);
1859   if (entry <= 0)
1860     return 0;
1861   return solvable_lookup_str(pool->solvables + entry, keyname);
1862 }
1863
1864 Id
1865 pool_lookup_id(Pool *pool, Id entry, Id keyname)
1866 {
1867   if (entry == SOLVID_POS && pool->pos.repo)
1868     {
1869       Repodata *data = pool->pos.repo->repodata + pool->pos.repodataid;
1870       Id id = repodata_lookup_id(data, SOLVID_POS, keyname);
1871       return data->localpool ? repodata_globalize_id(data, id, 1) : id;
1872     }
1873   if (entry <= 0)
1874     return 0;
1875   return solvable_lookup_id(pool->solvables + entry, keyname);
1876 }
1877
1878 unsigned int
1879 pool_lookup_num(Pool *pool, Id entry, Id keyname, unsigned int notfound)
1880 {
1881   if (entry == SOLVID_POS && pool->pos.repo)
1882     {
1883       unsigned int value;
1884       if (repodata_lookup_num(pool->pos.repo->repodata + pool->pos.repodataid, SOLVID_POS, keyname, &value))
1885         return value;
1886       return notfound;
1887     }
1888   if (entry <= 0)
1889     return notfound;
1890   return solvable_lookup_num(pool->solvables + entry, keyname, notfound);
1891 }
1892
1893 int
1894 pool_lookup_void(Pool *pool, Id entry, Id keyname)
1895 {
1896   if (entry == SOLVID_POS && pool->pos.repo)
1897     return repodata_lookup_void(pool->pos.repo->repodata + pool->pos.repodataid, SOLVID_POS, keyname);
1898   if (entry <= 0)
1899     return 0;
1900   return solvable_lookup_void(pool->solvables + entry, keyname);
1901 }
1902
1903 const unsigned char *
1904 pool_lookup_bin_checksum(Pool *pool, Id entry, Id keyname, Id *typep)
1905 {
1906   if (entry == SOLVID_POS && pool->pos.repo)
1907     return repodata_lookup_bin_checksum(pool->pos.repo->repodata + pool->pos.repodataid, SOLVID_POS, keyname, typep);
1908   if (entry <= 0)
1909     return 0;
1910   return solvable_lookup_bin_checksum(pool->solvables + entry, keyname, typep);
1911 }
1912
1913 const char *
1914 pool_lookup_checksum(Pool *pool, Id entry, Id keyname, Id *typep)
1915 {
1916   if (entry == SOLVID_POS && pool->pos.repo)
1917     {
1918       const unsigned char *chk = repodata_lookup_bin_checksum(pool->pos.repo->repodata + pool->pos.repodataid, SOLVID_POS, keyname, typep);
1919       return chk ? repodata_chk2str(pool->pos.repo->repodata + pool->pos.repodataid, *typep, chk) : 0;
1920     }
1921   if (entry <= 0)
1922     return 0;
1923   return solvable_lookup_checksum(pool->solvables + entry, keyname, typep);
1924 }
1925
1926 void
1927 pool_add_fileconflicts_deps(Pool *pool, Queue *conflicts)
1928 {
1929   int hadhashes = pool->relhashtbl ? 1 : 0;
1930   Solvable *s;
1931   Id fn, p, q, md5;
1932   Id id;
1933   int i;
1934
1935   if (!conflicts->count)
1936     return;
1937   pool_freewhatprovides(pool);
1938   for (i = 0; i < conflicts->count; i += 5)
1939     {
1940       fn = conflicts->elements[i];
1941       p = conflicts->elements[i + 1];
1942       md5 = conflicts->elements[i + 2];
1943       q = conflicts->elements[i + 3];
1944       id = pool_rel2id(pool, fn, md5, REL_FILECONFLICT, 1);
1945       s = pool->solvables + p;
1946       if (!s->repo)
1947         continue;
1948       s->provides = repo_addid_dep(s->repo, s->provides, id, SOLVABLE_FILEMARKER);
1949       s = pool->solvables + q;
1950       if (!s->repo)
1951         continue;
1952       s->conflicts = repo_addid_dep(s->repo, s->conflicts, id, 0);
1953     }
1954   if (!hadhashes)
1955     pool_freeidhashes(pool);
1956 }
1957
1958 /* EOF */