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