lib/rpmal.c

   1 /** \ingroup rpmdep
   2  * \file lib/rpmal.c
   3  */
   4
   5 #include "system.h"
   6
   7
   8 #include <rpm/rpmte.h>
   9 #include <rpm/rpmfi.h>
  10 #include <rpm/rpmstrpool.h>
  11
  12 #include "lib/rpmal.h"
  13 #include "lib/misc.h"
  14 #include "lib/rpmte_internal.h"
  15 #include "lib/rpmds_internal.h"
  16 #include "lib/rpmfi_internal.h"
  17
  18 #include "debug.h"
  19
  20 typedef struct availablePackage_s * availablePackage;
  21 typedef int rpmalNum;
  22
  23 /** \ingroup rpmdep
  24  * Info about a single package to be installed.
  25  */
  26 struct availablePackage_s {
  27     rpmte p;                    /*!< transaction member */
  28     rpmds provides;             /*!< Provides: dependencies. */
  29     rpmds obsoletes;            /*!< Obsoletes: dependencies. */
  30     rpmfiles fi;                /*!< File info set. */
  31 };
  32
  33 /** \ingroup rpmdep
  34  * A single available item (e.g. a Provides: dependency).
  35  */
  36 typedef struct availableIndexEntry_s {
  37     rpmalNum pkgNum;            /*!< Containing package index. */
  38     unsigned int entryIx;       /*!< Dependency index. */
  39 } * availableIndexEntry;
  40
  41 #undef HASHTYPE
  42 #undef HTKEYTYPE
  43 #undef HTDATATYPE
  44 #define HASHTYPE rpmalDepHash
  45 #define HTKEYTYPE rpmsid
  46 #define HTDATATYPE struct availableIndexEntry_s
  47 #include "lib/rpmhash.H"
  48 #include "lib/rpmhash.C"
  49
  50 typedef struct availableIndexFileEntry_s {
  51     rpmsid dirName;
  52     rpmalNum pkgNum;            /*!< Containing package index. */
  53     unsigned int entryIx;       /*!< Dependency index. */
  54 } * availableIndexFileEntry;
  55
  56 #undef HASHTYPE
  57 #undef HTKEYTYPE
  58 #undef HTDATATYPE
  59 #define HASHTYPE rpmalFileHash
  60 #define HTKEYTYPE rpmsid
  61 #define HTDATATYPE struct availableIndexFileEntry_s
  62 #include "lib/rpmhash.H"
  63 #include "lib/rpmhash.C"
  64
  65 /** \ingroup rpmdep
  66  * Set of available packages, items, and directories.
  67  */
  68 struct rpmal_s {
  69     rpmstrPool pool;            /*!< String pool */
  70     availablePackage list;      /*!< Set of packages. */
  71     rpmalDepHash providesHash;
  72     rpmalDepHash obsoletesHash;
  73     rpmalFileHash fileHash;
  74     int delta;                  /*!< Delta for pkg list reallocation. */
  75     int size;                   /*!< No. of pkgs in list. */
  76     int alloced;                /*!< No. of pkgs allocated for list. */
  77     rpmtransFlags tsflags;      /*!< Transaction control flags. */
  78     rpm_color_t tscolor;        /*!< Transaction color. */
  79     rpm_color_t prefcolor;      /*!< Transaction preferred color. */
  80     fingerPrintCache fpc;
  81 };
  82
  83 /**
  84  * Destroy available item index.
  85  * @param al            available list
  86  */
  87 static void rpmalFreeIndex(rpmal al)
  88 {
  89     al->providesHash = rpmalDepHashFree(al->providesHash);
  90     al->obsoletesHash = rpmalDepHashFree(al->obsoletesHash);
  91     al->fileHash = rpmalFileHashFree(al->fileHash);
  92     al->fpc = fpCacheFree(al->fpc);
  93 }
  94
  95 rpmal rpmalCreate(rpmstrPool pool, int delta, rpmtransFlags tsflags,
  96                   rpm_color_t tscolor, rpm_color_t prefcolor)
  97 {
  98     rpmal al = xcalloc(1, sizeof(*al));
  99
 100     /* transition time safe-guard */
 101     assert(pool != NULL);
 102
 103     al->pool = rpmstrPoolLink(pool);
 104     al->delta = delta;
 105     al->size = 0;
 106     al->alloced = al->delta;
 107     al->list = xmalloc(sizeof(*al->list) * al->alloced);;
 108
 109     al->providesHash = NULL;
 110     al->obsoletesHash = NULL;
 111     al->fileHash = NULL;
 112     al->tsflags = tsflags;
 113     al->tscolor = tscolor;
 114     al->prefcolor = prefcolor;
 115
 116     return al;
 117 }
 118
 119 rpmal rpmalFree(rpmal al)
 120 {
 121     availablePackage alp;
 122     int i;
 123
 124     if (al == NULL)
 125         return NULL;
 126
 127     if ((alp = al->list) != NULL)
 128     for (i = 0; i < al->size; i++, alp++) {
 129         alp->obsoletes = rpmdsFree(alp->obsoletes);
 130         alp->provides = rpmdsFree(alp->provides);
 131         alp->fi = rpmfilesFree(alp->fi);
 132     }
 133     al->pool = rpmstrPoolFree(al->pool);
 134     al->list = _free(al->list);
 135     al->alloced = 0;
 136
 137     rpmalFreeIndex(al);
 138     al = _free(al);
 139     return NULL;
 140 }
 141
 142 static unsigned int sidHash(rpmsid sid)
 143 {
 144     return sid;
 145 }
 146
 147 static int sidCmp(rpmsid a, rpmsid b)
 148 {
 149     return (a != b);
 150 }
 151
 152 void rpmalDel(rpmal al, rpmte p)
 153 {
 154     availablePackage alp;
 155     rpmalNum pkgNum;
 156
 157     if (al == NULL || al->list == NULL)
 158         return;         /* XXX can't happen */
 159
 160     // XXX use a search for self provide
 161     for (pkgNum=0; pkgNum<al->size; pkgNum++) {
 162         if (al->list[pkgNum].p == p) {
 163             break;
 164         }
 165     }
 166     if (pkgNum == al->size ) return; // Not found!
 167
 168     alp = al->list + pkgNum;
 169     // do not actually delete, just set p to NULL
 170     // and later filter that out of the results
 171     alp->p = NULL;
 172 }
 173
 174 static void rpmalAddFiles(rpmal al, rpmalNum pkgNum, rpmfiles fi)
 175 {
 176     struct availableIndexFileEntry_s fileEntry;
 177     int fc = rpmfilesFC(fi);
 178     rpm_color_t ficolor;
 179     int skipdoc = (al->tsflags & RPMTRANS_FLAG_NODOCS);
 180     int skipconf = (al->tsflags & RPMTRANS_FLAG_NOCONFIGS);
 181
 182     fileEntry.pkgNum = pkgNum;
 183
 184     for (int i = 0; i < fc; i++) {
 185         /* Ignore colored provides not in our rainbow. */
 186         ficolor = rpmfilesFColor(fi, i);
 187         if (al->tscolor && ficolor && !(al->tscolor & ficolor))
 188             continue;
 189
 190         /* Ignore files that wont be installed */
 191         if (skipdoc && (rpmfilesFFlags(fi, i) & RPMFILE_DOC))
 192             continue;
 193         if (skipconf && (rpmfilesFFlags(fi, i) & RPMFILE_CONFIG))
 194             continue;
 195
 196         fileEntry.dirName = rpmfilesDNId(fi, rpmfilesDI(fi, i));
 197         fileEntry.entryIx = i;
 198
 199         rpmalFileHashAddEntry(al->fileHash, rpmfilesBNId(fi, i), fileEntry);
 200     }
 201 }
 202
 203 static void rpmalAddProvides(rpmal al, rpmalNum pkgNum, rpmds provides)
 204 {
 205     struct availableIndexEntry_s indexEntry;
 206     rpm_color_t dscolor;
 207     int skipconf = (al->tsflags & RPMTRANS_FLAG_NOCONFIGS);
 208     int dc = rpmdsCount(provides);
 209
 210     indexEntry.pkgNum = pkgNum;
 211
 212     for (int i = 0; i < dc; i++) {
 213         /* Ignore colored provides not in our rainbow. */
 214         dscolor = rpmdsColorIndex(provides, i);
 215         if (al->tscolor && dscolor && !(al->tscolor & dscolor))
 216             continue;
 217
 218         /* Ignore config() provides if the files wont be installed */
 219         if (skipconf & (rpmdsFlagsIndex(provides, i) & RPMSENSE_CONFIG))
 220             continue;
 221
 222         indexEntry.entryIx = i;;
 223         rpmalDepHashAddEntry(al->providesHash,
 224                                   rpmdsNIdIndex(provides, i), indexEntry);
 225     }
 226 }
 227
 228 static void rpmalAddObsoletes(rpmal al, rpmalNum pkgNum, rpmds obsoletes)
 229 {
 230     struct availableIndexEntry_s indexEntry;
 231     rpm_color_t dscolor;
 232     int dc = rpmdsCount(obsoletes);
 233
 234     indexEntry.pkgNum = pkgNum;
 235
 236     for (int i = 0; i < dc; i++) {
 237         /* Obsoletes shouldn't be colored but just in case... */
 238         dscolor = rpmdsColorIndex(obsoletes, i);
 239         if (al->tscolor && dscolor && !(al->tscolor & dscolor))
 240             continue;
 241
 242         indexEntry.entryIx = i;;
 243         rpmalDepHashAddEntry(al->obsoletesHash,
 244                                   rpmdsNIdIndex(obsoletes, i), indexEntry);
 245     }
 246 }
 247
 248 void rpmalAdd(rpmal al, rpmte p)
 249 {
 250     rpmalNum pkgNum;
 251     availablePackage alp;
 252
 253     if (al->size == al->alloced) {
 254         al->alloced += al->delta;
 255         al->list = xrealloc(al->list, sizeof(*al->list) * al->alloced);
 256     }
 257     pkgNum = al->size++;
 258
 259     alp = al->list + pkgNum;
 260
 261     alp->p = p;
 262
 263     alp->provides = rpmdsLink(rpmteDS(p, RPMTAG_PROVIDENAME));
 264     alp->obsoletes = rpmdsLink(rpmteDS(p, RPMTAG_OBSOLETENAME));
 265     alp->fi = rpmteFiles(p);
 266
 267     /*
 268      * Transition-time safe-guard to catch private-pool uses.
 269      * File sets with no files have NULL pool, that's fine. But WTF is up
 270      * with the provides: every single package should have at least its
 271      * own name as a provide, and thus never NULL, and normal use matches
 272      * this expectation. However the test-suite is tripping up on NULL
 273      * NULL pool from NULL alp->provides in numerous cases?
 274      */
 275     {
 276         rpmstrPool fipool = rpmfilesPool(alp->fi);
 277         rpmstrPool dspool = rpmdsPool(alp->provides);
 278
 279         assert(fipool == NULL || fipool == al->pool);
 280         assert(dspool == NULL || dspool == al->pool);
 281     }
 282
 283     /* Try to be lazy as delayed hash creation is cheaper */
 284     if (al->providesHash != NULL)
 285         rpmalAddProvides(al, pkgNum, alp->provides);
 286     if (al->obsoletesHash != NULL)
 287         rpmalAddObsoletes(al, pkgNum, alp->obsoletes);
 288     if (al->fileHash != NULL)
 289         rpmalAddFiles(al, pkgNum, alp->fi);
 290
 291     assert(((rpmalNum)(alp - al->list)) == pkgNum);
 292 }
 293
 294 static void rpmalMakeFileIndex(rpmal al)
 295 {
 296     availablePackage alp;
 297     int i, fileCnt = 0;
 298
 299     for (i = 0; i < al->size; i++) {
 300         alp = al->list + i;
 301         if (alp->fi != NULL)
 302             fileCnt += rpmfilesFC(alp->fi);
 303     }
 304     al->fileHash = rpmalFileHashCreate(fileCnt/4+128,
 305                                        sidHash, sidCmp, NULL, NULL);
 306     for (i = 0; i < al->size; i++) {
 307         alp = al->list + i;
 308         rpmalAddFiles(al, i, alp->fi);
 309     }
 310 }
 311
 312 static void rpmalMakeProvidesIndex(rpmal al)
 313 {
 314     availablePackage alp;
 315     int i, providesCnt = 0;
 316
 317     for (i = 0; i < al->size; i++) {
 318         alp = al->list + i;
 319         providesCnt += rpmdsCount(alp->provides);
 320     }
 321
 322     al->providesHash = rpmalDepHashCreate(providesCnt/4+128,
 323                                                sidHash, sidCmp, NULL, NULL);
 324     for (i = 0; i < al->size; i++) {
 325         alp = al->list + i;
 326         rpmalAddProvides(al, i, alp->provides);
 327     }
 328 }
 329
 330 static void rpmalMakeObsoletesIndex(rpmal al)
 331 {
 332     availablePackage alp;
 333     int i, obsoletesCnt = 0;
 334
 335     for (i = 0; i < al->size; i++) {
 336         alp = al->list + i;
 337         obsoletesCnt += rpmdsCount(alp->obsoletes);
 338     }
 339
 340     al->obsoletesHash = rpmalDepHashCreate(obsoletesCnt/4+128,
 341                                                sidHash, sidCmp, NULL, NULL);
 342     for (i = 0; i < al->size; i++) {
 343         alp = al->list + i;
 344         rpmalAddObsoletes(al, i, alp->obsoletes);
 345     }
 346 }
 347
 348 rpmte * rpmalAllObsoletes(rpmal al, rpmds ds)
 349 {
 350     rpmte * ret = NULL;
 351     rpmsid nameId;
 352     availableIndexEntry result;
 353     int resultCnt;
 354
 355     if (al == NULL || ds == NULL || (nameId = rpmdsNId(ds)) == 0)
 356         return ret;
 357
 358     if (al->obsoletesHash == NULL)
 359         rpmalMakeObsoletesIndex(al);
 360
 361     rpmalDepHashGetEntry(al->obsoletesHash, nameId, &result, &resultCnt, NULL);
 362
 363     if (resultCnt > 0) {
 364         availablePackage alp;
 365         int rc, found = 0;
 366
 367         ret = xmalloc((resultCnt+1) * sizeof(*ret));
 368
 369         for (int i = 0; i < resultCnt; i++) {
 370             alp = al->list + result[i].pkgNum;
 371             if (alp->p == NULL) // deleted
 372                 continue;
 373
 374             rc = rpmdsCompareIndex(alp->obsoletes, result[i].entryIx,
 375                                    ds, rpmdsIx(ds));
 376
 377             if (rc) {
 378                 rpmdsNotify(ds, "(added obsolete)", 0);
 379                 ret[found] = alp->p;
 380                 found++;
 381             }
 382         }
 383
 384         if (found)
 385             ret[found] = NULL;
 386         else
 387             ret = _free(ret);
 388     }
 389
 390     return ret;
 391 }
 392
 393 static rpmte * rpmalAllFileSatisfiesDepend(const rpmal al, const char *fileName, const rpmds filterds)
 394 {
 395     const char *slash;
 396     rpmte * ret = NULL;
 397
 398     if (al == NULL || fileName == NULL || *fileName != '/')
 399         return NULL;
 400
 401     /* Split path into dirname and basename components for lookup */
 402     if ((slash = strrchr(fileName, '/')) != NULL) {
 403         availableIndexFileEntry result;
 404         int resultCnt = 0;
 405         size_t bnStart = (slash - fileName) + 1;
 406         rpmsid baseName;
 407
 408         if (al->fileHash == NULL)
 409             rpmalMakeFileIndex(al);
 410
 411         baseName = rpmstrPoolId(al->pool, fileName + bnStart, 0);
 412         if (!baseName)
 413             return NULL;        /* no match possible */
 414
 415         rpmalFileHashGetEntry(al->fileHash, baseName, &result, &resultCnt, NULL);
 416
 417         if (resultCnt > 0) {
 418             int i, found;
 419             ret = xmalloc((resultCnt+1) * sizeof(*ret));
 420             fingerPrint * fp = NULL;
 421             rpmsid dirName = rpmstrPoolIdn(al->pool, fileName, bnStart, 1);
 422
 423             if (!al->fpc)
 424                 al->fpc = fpCacheCreate(1001, NULL);
 425             fpLookup(al->fpc, rpmstrPoolStr(al->pool, dirName), fileName + bnStart, &fp);
 426
 427             for (found = i = 0; i < resultCnt; i++) {
 428                 availablePackage alp = al->list + result[i].pkgNum;
 429                 if (alp->p == NULL) /* deleted */
 430                     continue;
 431                 /* ignore self-conflicts/obsoletes */
 432                 if (filterds && rpmteDS(alp->p, rpmdsTagN(filterds)) == filterds)
 433                     continue;
 434                 if (result[i].dirName != dirName &&
 435                     !fpLookupEquals(al->fpc, fp, rpmstrPoolStr(al->pool, result[i].dirName), fileName + bnStart))
 436                     continue;
 437
 438                 ret[found] = alp->p;
 439                 found++;
 440             }
 441             _free(fp);
 442             ret[found] = NULL;
 443         }
 444     }
 445
 446     return ret;
 447 }
 448
 449 rpmte * rpmalAllSatisfiesDepend(const rpmal al, const rpmds ds)
 450 {
 451     rpmte * ret = NULL;
 452     int i, ix, found;
 453     rpmsid nameId;
 454     const char *name;
 455     availableIndexEntry result;
 456     int resultCnt;
 457     int obsolete;
 458     rpmTagVal dtag;
 459     rpmds filterds = NULL;
 460
 461     availablePackage alp;
 462     int rc;
 463
 464     if (al == NULL || ds == NULL || (nameId = rpmdsNId(ds)) == 0)
 465         return ret;
 466
 467     dtag = rpmdsTagN(ds);
 468     obsolete = (dtag == RPMTAG_OBSOLETENAME);
 469     if (dtag == RPMTAG_OBSOLETENAME || dtag == RPMTAG_CONFLICTNAME)
 470         filterds = ds;
 471     name = rpmstrPoolStr(al->pool, nameId);
 472     if (!obsolete && *name == '/') {
 473         /* First, look for files "contained" in package ... */
 474         ret = rpmalAllFileSatisfiesDepend(al, name, filterds);
 475         if (ret != NULL && *ret != NULL) {
 476             rpmdsNotify(ds, "(added files)", 0);
 477             return ret;
 478         }
 479         /* ... then, look for files "provided" by package. */
 480         ret = _free(ret);
 481     }
 482
 483     if (al->providesHash == NULL)
 484         rpmalMakeProvidesIndex(al);
 485
 486     rpmalDepHashGetEntry(al->providesHash, nameId, &result,
 487                               &resultCnt, NULL);
 488
 489     if (resultCnt==0) return NULL;
 490
 491     ret = xmalloc((resultCnt+1) * sizeof(*ret));
 492
 493     for (found=i=0; i<resultCnt; i++) {
 494         alp = al->list + result[i].pkgNum;
 495         if (alp->p == NULL) /* deleted */
 496             continue;
 497         /* ignore self-conflicts/obsoletes */
 498         if (filterds && rpmteDS(alp->p, rpmdsTagN(filterds)) == filterds)
 499             continue;
 500         ix = result[i].entryIx;
 501
 502         if (obsolete) {
 503             /* Obsoletes are on package NEVR only */
 504             rpmds thisds;
 505             if (!rstreq(rpmdsNIndex(alp->provides, ix), rpmteN(alp->p)))
 506                 continue;
 507             thisds = rpmteDS(alp->p, RPMTAG_NAME);
 508             rc = rpmdsCompareIndex(thisds, rpmdsIx(thisds), ds, rpmdsIx(ds));
 509         } else {
 510             rc = rpmdsCompareIndex(alp->provides, ix, ds, rpmdsIx(ds));
 511         }
 512
 513         if (rc)
 514             ret[found++] = alp->p;
 515     }
 516
 517     if (found) {
 518         rpmdsNotify(ds, "(added provide)", 0);
 519         ret[found] = NULL;
 520     } else {
 521         ret = _free(ret);
 522     }
 523
 524     return ret;
 525 }
 526
 527 rpmte
 528 rpmalSatisfiesDepend(const rpmal al, const rpmte te, const rpmds ds)
 529 {
 530     rpmte *providers = rpmalAllSatisfiesDepend(al, ds);
 531     rpmte best = NULL;
 532     int bestscore = 0;
 533
 534     if (providers) {
 535         rpm_color_t dscolor = rpmdsColor(ds);
 536         for (rpmte *p = providers; *p; p++) {
 537             int score = 0;
 538
 539             /*
 540              * For colored dependencies, prefer a matching colored provider.
 541              * Otherwise prefer provider of ts preferred color.
 542              */
 543             if (al->tscolor) {
 544                 rpm_color_t tecolor = rpmteColor(*p);
 545                 if (dscolor) {
 546                     if (dscolor == tecolor) score += 2;
 547                 } else if (al->prefcolor) {
 548                     if (al->prefcolor == tecolor) score += 2;
 549                 }
 550             }
 551
 552             /* Being self-provided is a bonus */
 553             if (*p == te)
 554                 score += 1;
 555
 556             if (score > bestscore) {
 557                 bestscore = score;
 558                 best = *p;
 559             }
 560         }
 561         /* if not decided by now, just pick first match */
 562         if (!best) best = providers[0];
 563         free(providers);
 564     }
 565     return best;
 566 }
 567
 568 unsigned int
 569 rpmalLookupTE(const rpmal al, const rpmte te)
 570 {
 571     rpmalNum pkgNum;
 572     for (pkgNum=0; pkgNum < al->size; pkgNum++)
 573         if (al->list[pkgNum].p == te)
 574             break;
 575     return pkgNum < al->size ? pkgNum : (unsigned int)-1;
 576 }
 577