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