src/fileprovides.c

   1 /*
   2  * Copyright (c) 2007-2016, SUSE LLC
   3  *
   4  * This program is licensed under the BSD license, read LICENSE.BSD
   5  * for further information
   6  */
   7
   8 /*
   9  * fileprovides.c
  10  *
  11  * Add missing file dependencies to the package provides
  12  */
  13
  14 #include <stdio.h>
  15 #include <stdlib.h>
  16 #include <stdarg.h>
  17 #include <unistd.h>
  18 #include <string.h>
  19
  20 #include "pool.h"
  21 #include "repo.h"
  22 #include "util.h"
  23 #include "bitmap.h"
  24
  25
  26 struct searchfiles {
  27   Id *ids;
  28   int nfiles;
  29   Map seen;
  30 };
  31
  32 #define SEARCHFILES_BLOCK 127
  33
  34 static void
  35 pool_addfileprovides_dep(Pool *pool, Id *ida, struct searchfiles *sf, struct searchfiles *isf)
  36 {
  37   Id dep, sid;
  38   const char *s;
  39   struct searchfiles *csf;
  40
  41   while ((dep = *ida++) != 0)
  42     {
  43       csf = sf;
  44       while (ISRELDEP(dep))
  45         {
  46           Reldep *rd;
  47           sid = pool->ss.nstrings + GETRELID(dep);
  48           if (MAPTST(&csf->seen, sid))
  49             {
  50               dep = 0;
  51               break;
  52             }
  53           MAPSET(&csf->seen, sid);
  54           rd = GETRELDEP(pool, dep);
  55           if (rd->flags < 8)
  56             dep = rd->name;
  57           else if (rd->flags == REL_NAMESPACE)
  58             {
  59               if (rd->name == NAMESPACE_SPLITPROVIDES)
  60                 {
  61                   csf = isf;
  62                   if (!csf || MAPTST(&csf->seen, sid))
  63                     {
  64                       dep = 0;
  65                       break;
  66                     }
  67                   MAPSET(&csf->seen, sid);
  68                 }
  69               dep = rd->evr;
  70             }
  71           else if (rd->flags == REL_FILECONFLICT)
  72             {
  73               dep = 0;
  74               break;
  75             }
  76           else
  77             {
  78               Id ids[2];
  79               ids[0] = rd->name;
  80               ids[1] = 0;
  81               pool_addfileprovides_dep(pool, ids, csf, isf);
  82               dep = rd->evr;
  83             }
  84         }
  85       if (!dep)
  86         continue;
  87       if (MAPTST(&csf->seen, dep))
  88         continue;
  89       MAPSET(&csf->seen, dep);
  90       s = pool_id2str(pool, dep);
  91       if (*s != '/')
  92         continue;
  93       if (csf != isf && pool->addedfileprovides == 1 && !repodata_filelistfilter_matches(0, s))
  94         continue;       /* skip non-standard locations csf == isf: installed case */
  95       csf->ids = solv_extend(csf->ids, csf->nfiles, 1, sizeof(Id), SEARCHFILES_BLOCK);
  96       csf->ids[csf->nfiles++] = dep;
  97     }
  98 }
  99
 100 struct addfileprovides_cbdata {
 101   int nfiles;
 102   Id *ids;
 103   char **dirs;
 104   char **names;
 105   Id *dids;
 106
 107   Map *providedids;
 108   int provstart;
 109   int provend;
 110
 111   Map *todo;
 112   int todo_start;
 113   int todo_end;
 114 };
 115
 116 /* split filelist dep into basename and dirname */
 117 static void
 118 create_dirs_names_array(struct addfileprovides_cbdata *cbd, Pool *pool)
 119 {
 120   int i;
 121   cbd->dirs = solv_malloc2(cbd->nfiles, sizeof(char *));
 122   cbd->names = solv_malloc2(cbd->nfiles, sizeof(char *));
 123   for (i = 0; i < cbd->nfiles; i++)
 124     {
 125       char *s = solv_strdup(pool_id2str(pool, cbd->ids[i]));
 126       cbd->dirs[i] = s;
 127       s = strrchr(s, '/');
 128       *s = 0;
 129       cbd->names[i] = s + 1;
 130     }
 131 }
 132
 133 static void
 134 free_dirs_names_array(struct addfileprovides_cbdata *cbd)
 135 {
 136   int i;
 137   if (cbd->dirs)
 138     {
 139       for (i = 0; i < cbd->nfiles; i++)
 140         solv_free(cbd->dirs[i]);
 141       cbd->dirs = solv_free(cbd->dirs);
 142       cbd->names = solv_free(cbd->names);
 143     }
 144 }
 145
 146 static void
 147 prune_todo_range(Repo *repo, struct addfileprovides_cbdata *cbd)
 148 {
 149   int start = cbd->todo_start, end = cbd->todo_end;
 150   while (start < end && !MAPTST(cbd->todo, start - repo->start))
 151     start++;
 152   while (end > start && !MAPTST(cbd->todo, end - 1 - repo->start))
 153     end--;
 154   cbd->todo_start = start;
 155   cbd->todo_end = end;
 156 }
 157
 158 static int
 159 repodata_intersects_todo(Repodata *data, struct addfileprovides_cbdata *cbd)
 160 {
 161   Repo *repo;
 162   int p, start = data->start, end = data->end;
 163   if (start >= cbd->todo_end || end <= cbd->todo_start)
 164     return 0;
 165   repo = data->repo;
 166   if (start < cbd->todo_start)
 167     start = cbd->todo_start;
 168   if (end > cbd->todo_end)
 169     end = cbd->todo_end;
 170   for (p = start; p < end; p++)
 171     if (MAPTST(cbd->todo, p - repo->start))
 172       return 1;
 173   return 0;
 174 }
 175
 176 /* forward declaration */
 177 static void repodata_addfileprovides_search(Repodata *data, struct addfileprovides_cbdata *cbd);
 178
 179 /* search a subset of the todo range */
 180 static void
 181 repodata_addfileprovides_search_limited(Repodata *data, struct addfileprovides_cbdata *cbd, int start, int end)
 182 {
 183
 184   int old_todo_start = cbd->todo_start;
 185   int old_todo_end = cbd->todo_end;
 186   if (start < cbd->todo_start)
 187     start = cbd->todo_start;
 188   if (end > cbd->todo_end)
 189     end = cbd->todo_end;
 190   if (start >= end)
 191     return;
 192   cbd->todo_start = start;
 193   cbd->todo_end = end;
 194   repodata_addfileprovides_search(data, cbd);
 195   cbd->todo_start = old_todo_start;
 196   cbd->todo_end = old_todo_end;
 197   prune_todo_range(data->repo, cbd);
 198 }
 199
 200 static void
 201 repodata_addfileprovides_search(Repodata *data, struct addfileprovides_cbdata *cbd)
 202 {
 203   Repo *repo = data->repo;
 204   int i, p, start, end;
 205   Map useddirs;
 206   Map *providedids = 0;
 207
 208   /* make it available */
 209   if (data->state == REPODATA_STUB)
 210     repodata_load(data);
 211   if (data->state != REPODATA_AVAILABLE)
 212     return;
 213   if (!data->incoredata || !data->dirpool.ndirs)
 214     return;
 215
 216   start = cbd->todo_start > data->start ? cbd->todo_start : data->start;
 217   end = cbd->todo_end > data->end ? data->end : cbd->todo_end;
 218
 219   if (start >= end)
 220     return;
 221
 222   /* deal with provideids overlap */
 223   if (cbd->providedids)
 224     {
 225       if (start >= cbd->provstart && end <= cbd->provend)
 226         providedids = cbd->providedids; /* complete overlap */
 227       else if (start < cbd->provend && end > cbd->provstart)
 228         {
 229           /* partial overlap, need to split search */
 230           if (start < cbd->provstart)
 231             {
 232               repodata_addfileprovides_search_limited(data, cbd, start, cbd->provstart);
 233               start = cbd->provstart;
 234             }
 235           if (end > cbd->provend)
 236             {
 237               repodata_addfileprovides_search_limited(data, cbd, cbd->provend, end);
 238               end = cbd->provend;
 239             }
 240           if (start < end)
 241             repodata_addfileprovides_search_limited(data, cbd, start, end);
 242           return;
 243         }
 244     }
 245
 246   /* set up dirs and names array if not already done */
 247   if (!cbd->dirs)
 248     create_dirs_names_array(cbd, repo->pool);
 249
 250   /* set up useddirs map and the cbd->dids array */
 251   map_init(&useddirs, data->dirpool.ndirs);
 252   for (i = 0; i < cbd->nfiles; i++)
 253     {
 254       Id did;
 255       if (providedids && MAPTST(providedids, cbd->ids[i]))
 256         {
 257           cbd->dids[i] = 0;     /* already included, do not add again */
 258           continue;
 259         }
 260       cbd->dids[i] = did = repodata_str2dir(data, cbd->dirs[i], 0);
 261       if (did)
 262         MAPSET(&useddirs, did);
 263     }
 264   repodata_free_dircache(data);         /* repodata_str2dir created it */
 265
 266   for (p = start; p < end; p++)
 267     {
 268       const unsigned char *dp;
 269       Solvable *s;
 270       if (!MAPTST(cbd->todo, p - repo->start))
 271         continue;
 272       dp = repodata_lookup_packed_dirstrarray(data, p, SOLVABLE_FILELIST);
 273       if (!dp)
 274         continue;
 275       /* now iterate through the packed array */
 276       s = repo->pool->solvables + p;
 277       MAPCLR(cbd->todo, p - repo->start);       /* this entry is done */
 278       for (;;)
 279         {
 280           Id did = 0;
 281           int c;
 282           while ((c = *dp++) & 0x80)
 283             did = (did << 7) ^ c ^ 0x80;
 284           did = (did << 6) | (c & 0x3f);
 285           if ((unsigned int)did < (unsigned int)data->dirpool.ndirs && MAPTST(&useddirs, did))
 286             {
 287               /* there is at least one entry with that did */
 288               for (i = 0; i < cbd->nfiles; i++)
 289                 if (cbd->dids[i] == did && !strcmp(cbd->names[i], (const char *)dp))
 290                   s->provides = repo_addid_dep(s->repo, s->provides, cbd->ids[i], SOLVABLE_FILEMARKER);
 291             }
 292           if (!(c & 0x40))
 293             break;
 294           dp += strlen((const char *)dp) + 1;
 295         }
 296     }
 297   map_free(&useddirs);
 298   prune_todo_range(repo, cbd);
 299 }
 300
 301 static void
 302 repo_addfileprovides_search_filtered(Repo *repo, struct addfileprovides_cbdata *cbd, int filteredid, Map *postpone)
 303 {
 304   Repodata *data = repo->repodata + filteredid;
 305   Map *providedids = cbd->providedids;
 306   int rdid;
 307   int start, end, p, i;
 308   Map old_todo;
 309   int old_todo_start, old_todo_end;
 310
 311   start = cbd->todo_start > data->start ? cbd->todo_start : data->start;
 312   end = cbd->todo_end > data->end ? data->end : cbd->todo_end;
 313
 314   if (providedids)
 315     {
 316       /* check if all solvables are in the provide range */
 317       if (start < cbd->provstart || end > cbd->provend)
 318         {
 319           /* unclear, check each solvable */
 320           for (p = start; p < end; p++)
 321             {
 322               if (p >= cbd->provstart && p < cbd->provend)
 323                 continue;
 324               if (data->incoreoffset[p - data->start] && MAPTST(cbd->todo, p - repo->start))
 325                 {
 326                   providedids = 0;      /* nope, cannot prune with providedids */
 327                   break;
 328                 }
 329             }
 330         }
 331     }
 332
 333   /* check if the filtered files are enough */
 334   for (i = 0; i < cbd->nfiles; i++)
 335     {
 336       if (providedids && MAPTST(providedids, cbd->ids[i]))      /* this one is already provided */
 337         continue;
 338       if (!repodata_filelistfilter_matches(data, pool_id2str(repo->pool, cbd->ids[i])))
 339         break;
 340     }
 341   if (i < cbd->nfiles)
 342     {
 343       /* nope, need to search the extensions as well. postpone. */
 344       for (p = start; p < end; p++)
 345         {
 346           if (data->incoreoffset[p - data->start] && MAPTST(cbd->todo, p - repo->start))
 347             {
 348               if (!postpone->size)
 349                 map_grow(postpone, repo->nsolvables);
 350               MAPSET(postpone, p - repo->start);
 351               MAPCLR(cbd->todo, p - repo->start);
 352             }
 353         }
 354       prune_todo_range(repo, cbd);
 355       return;
 356     }
 357
 358   /* now check if there is no data marked withour EXTENSION */
 359   /* limit todo to the solvables in this repodata */
 360   old_todo_start = cbd->todo_start;
 361   old_todo_end = cbd->todo_end;
 362   old_todo = *cbd->todo;
 363   map_init(cbd->todo, repo->nsolvables);
 364   for (p = start; p < end; p++)
 365     if (data->incoreoffset[p - data->start] && MAPTST(&old_todo, p - repo->start))
 366       {
 367         MAPCLR(&old_todo, p - repo->start);
 368         MAPSET(cbd->todo, p - repo->start);
 369       }
 370   prune_todo_range(repo, cbd);
 371
 372   /* do the check */
 373   for (rdid = repo->nrepodata - 1, data = repo->repodata + rdid; rdid > filteredid ; rdid--, data--)
 374     {
 375       if (data->filelisttype == REPODATA_FILELIST_EXTENSION)
 376         continue;
 377       if (data->start >= cbd->todo_end || data->end <= cbd->todo_start)
 378         continue;
 379       if (!repodata_has_keyname(data, SOLVABLE_FILELIST))
 380         continue;
 381       if (!repodata_intersects_todo(data, cbd))
 382         continue;
 383       /* oh no, this filelist data is not tagged with REPODATA_FILELIST_EXTENSION! */
 384       /* postpone entries that have filelist data */
 385       start = cbd->todo_start > data->start ? cbd->todo_start : data->start;
 386       end = cbd->todo_end > data->end ? data->end : cbd->todo_end;
 387       for (p = start; p < end; p++)
 388         if (MAPTST(cbd->todo, p - repo->start))
 389           if (repodata_lookup_type(data, p, SOLVABLE_FILELIST))
 390             {
 391               if (!postpone->size)
 392                 map_grow(postpone, repo->nsolvables);
 393               MAPSET(postpone, p - repo->start);
 394               MAPCLR(cbd->todo, p - repo->start);
 395             }
 396       prune_todo_range(repo, cbd);
 397       if (cbd->todo_start >= cbd->todo_end)
 398         break;
 399     }
 400
 401   /* do the search over the filtered file list with the remaining entries*/
 402   if (cbd->todo_start < cbd->todo_end)
 403     repodata_addfileprovides_search(repo->repodata + filteredid, cbd);
 404
 405   /* restore todo map */
 406   map_free(cbd->todo);
 407   *cbd->todo = old_todo;
 408   cbd->todo_start = old_todo_start;
 409   cbd->todo_end = old_todo_end;
 410   prune_todo_range(repo, cbd);
 411 }
 412
 413 static void
 414 repo_addfileprovides_search(Repo *repo, struct addfileprovides_cbdata *cbd, struct searchfiles *sf)
 415 {
 416   Repodata *data;
 417   int rdid, p, i;
 418   int provstart, provend;
 419   Map todo;
 420   Map providedids;
 421
 422   if (repo->end <= repo->start || !repo->nsolvables || !sf->nfiles)
 423     return;
 424
 425   /* update search data if changed */
 426   if (cbd->nfiles != sf->nfiles || cbd->ids != sf->ids)
 427     {
 428       free_dirs_names_array(cbd);
 429       cbd->nfiles = sf->nfiles;
 430       cbd->ids = sf->ids;
 431       cbd->dids = solv_realloc2(cbd->dids, sf->nfiles, sizeof(Id));
 432     }
 433
 434   /* create todo map and range */
 435   map_init(&todo, repo->end - repo->start);
 436   for (p = repo->start; p < repo->end; p++)
 437     if (repo->pool->solvables[p].repo == repo)
 438       MAPSET(&todo, p - repo->start);
 439   cbd->todo = &todo;
 440   cbd->todo_start = repo->start;
 441   cbd->todo_end = repo->end;
 442   prune_todo_range(repo, cbd);
 443
 444   provstart = provend = 0;
 445   map_init(&providedids, 0);
 446   data = repo_lookup_repodata(repo, SOLVID_META, REPOSITORY_ADDEDFILEPROVIDES);
 447   if (data)
 448     {
 449       Queue fileprovidesq;
 450       queue_init(&fileprovidesq);
 451       if (repodata_lookup_idarray(data, SOLVID_META, REPOSITORY_ADDEDFILEPROVIDES, &fileprovidesq))
 452         {
 453           map_grow(&providedids, repo->pool->ss.nstrings);
 454           cbd->providedids = &providedids;
 455           provstart = data->start;
 456           provend = data->end;
 457           for (i = 0; i < fileprovidesq.count; i++)
 458             MAPSET(&providedids, fileprovidesq.elements[i]);
 459           for (i = 0; i < cbd->nfiles; i++)
 460             if (!MAPTST(&providedids, cbd->ids[i]))
 461               break;
 462           if (i == cbd->nfiles)
 463             {
 464               /* all included, clear entries from todo list */
 465               if (provstart <= cbd->todo_start && provend >= cbd->todo_end)
 466                 cbd->todo_end = cbd->todo_start;        /* clear complete range */
 467               else
 468                 {
 469                   for (p = provstart; p < provend; p++)
 470                     MAPCLR(&todo, p - repo->start);
 471                   prune_todo_range(repo, cbd);
 472                 }
 473             }
 474         }
 475       queue_free(&fileprovidesq);
 476     }
 477
 478   if (cbd->todo_start >= cbd->todo_end)
 479     {
 480       map_free(&todo);
 481       cbd->todo = 0;
 482       map_free(&providedids);
 483       cbd->providedids = 0;
 484       return;
 485     }
 486
 487   /* this is similar to repo_lookup_filelist_repodata in repo.c */
 488
 489   for (rdid = 1, data = repo->repodata + rdid; rdid < repo->nrepodata; rdid++, data++)
 490     if (data->filelisttype == REPODATA_FILELIST_FILTERED)
 491       break;
 492   for (; rdid < repo->nrepodata; rdid++, data++)
 493     if (data->filelisttype == REPODATA_FILELIST_EXTENSION)
 494       break;
 495
 496   if (rdid < repo->nrepodata)
 497     {
 498       /* have at least one repodata with REPODATA_FILELIST_FILTERED followed by REPODATA_FILELIST_EXTENSION */
 499       Map postpone;
 500       map_init(&postpone, 0);
 501       for (rdid = repo->nrepodata - 1, data = repo->repodata + rdid; rdid > 0; rdid--, data--)
 502         {
 503           if (data->filelisttype != REPODATA_FILELIST_FILTERED)
 504             continue;
 505           if (!repodata_intersects_todo(data, cbd))
 506             continue;
 507           if (data->state != REPODATA_AVAILABLE)
 508             {
 509               if (data->state != REPODATA_STUB)
 510                 continue;
 511               repodata_load(data);
 512               if (data->state != REPODATA_AVAILABLE || data->filelisttype != REPODATA_FILELIST_FILTERED)
 513                 continue;
 514             }
 515           repo_addfileprovides_search_filtered(repo, cbd, rdid, &postpone);
 516         }
 517       if (postpone.size)
 518         {
 519           /* add postponed entries back to todo */
 520           map_or(&todo, &postpone);
 521           cbd->todo_start = repo->start;
 522           cbd->todo_end = repo->end;
 523           prune_todo_range(repo, cbd);
 524         }
 525       map_free(&postpone);
 526     }
 527
 528   /* search remaining entries in the standard way */
 529   if (cbd->todo_start < cbd->todo_end)
 530     {
 531       for (rdid = repo->nrepodata - 1, data = repo->repodata + rdid; rdid > 0; rdid--, data--)
 532         {
 533           if (data->start >= cbd->todo_end || data->end <= cbd->todo_start)
 534             continue;
 535           if (!repodata_has_keyname(data, SOLVABLE_FILELIST))
 536             continue;
 537           if (!repodata_intersects_todo(data, cbd))
 538             continue;
 539           repodata_addfileprovides_search(data, cbd);
 540           if (cbd->todo_start >= cbd->todo_end)
 541             break;
 542         }
 543     }
 544
 545   map_free(&todo);
 546   cbd->todo = 0;
 547   map_free(&providedids);
 548   cbd->providedids = 0;
 549 }
 550
 551 void
 552 pool_addfileprovides_queue(Pool *pool, Queue *idq, Queue *idqinst)
 553 {
 554   Solvable *s;
 555   Repo *installed, *repo;
 556   struct searchfiles sf, isf, *isfp;
 557   struct addfileprovides_cbdata cbd;
 558   int i;
 559   unsigned int now;
 560
 561   installed = pool->installed;
 562   now = solv_timems(0);
 563   memset(&cbd, 0, sizeof(cbd));
 564   memset(&sf, 0, sizeof(sf));
 565   map_init(&sf.seen, pool->ss.nstrings + pool->nrels);
 566   memset(&isf, 0, sizeof(isf));
 567   map_init(&isf.seen, pool->ss.nstrings + pool->nrels);
 568   pool->addedfileprovides = pool->addfileprovidesfiltered ? 1 : 2;
 569
 570   if (idq)
 571     queue_empty(idq);
 572   if (idqinst)
 573     queue_empty(idqinst);
 574   isfp = installed ? &isf : 0;
 575   for (i = 1, s = pool->solvables + i; i < pool->nsolvables; i++, s++)
 576     {
 577       repo = s->repo;
 578       if (!repo)
 579         continue;
 580       if (s->obsoletes)
 581         pool_addfileprovides_dep(pool, repo->idarraydata + s->obsoletes, &sf, isfp);
 582       if (s->conflicts)
 583         pool_addfileprovides_dep(pool, repo->idarraydata + s->conflicts, &sf, isfp);
 584       if (s->requires)
 585         pool_addfileprovides_dep(pool, repo->idarraydata + s->requires, &sf, isfp);
 586       if (s->recommends)
 587         pool_addfileprovides_dep(pool, repo->idarraydata + s->recommends, &sf, isfp);
 588       if (s->suggests)
 589         pool_addfileprovides_dep(pool, repo->idarraydata + s->suggests, &sf, isfp);
 590       if (s->supplements)
 591         pool_addfileprovides_dep(pool, repo->idarraydata + s->supplements, &sf, isfp);
 592       if (s->enhances)
 593         pool_addfileprovides_dep(pool, repo->idarraydata + s->enhances, &sf, isfp);
 594     }
 595
 596   map_free(&sf.seen);
 597   map_free(&isf.seen);
 598   POOL_DEBUG(SOLV_DEBUG_STATS, "found %d file dependencies, %d installed file dependencies\n", sf.nfiles, isf.nfiles);
 599   if (sf.nfiles)
 600     {
 601 #if 0
 602       for (i = 0; i < sf.nfiles; i++)
 603         POOL_DEBUG(SOLV_DEBUG_STATS, "looking up %s in filelist\n", pool_id2str(pool, sf.ids[i]));
 604 #endif
 605       FOR_REPOS(i, repo)
 606         repo_addfileprovides_search(repo, &cbd, &sf);
 607       if (idq)
 608         queue_insertn(idq, idq->count, sf.nfiles, sf.ids);
 609       if (idqinst)
 610         queue_insertn(idqinst, idqinst->count, sf.nfiles, sf.ids);
 611       solv_free(sf.ids);
 612     }
 613   if (isf.nfiles)
 614     {
 615 #if 0
 616       for (i = 0; i < isf.nfiles; i++)
 617         POOL_DEBUG(SOLV_DEBUG_STATS, "looking up %s in installed filelist\n", pool_id2str(pool, isf.ids[i]));
 618 #endif
 619       if (installed)
 620         repo_addfileprovides_search(installed, &cbd, &isf);
 621       if (installed && idqinst)
 622         for (i = 0; i < isf.nfiles; i++)
 623           queue_pushunique(idqinst, isf.ids[i]);
 624       solv_free(isf.ids);
 625     }
 626   free_dirs_names_array(&cbd);
 627   solv_free(cbd.dids);
 628   pool_freewhatprovides(pool);  /* as we have added provides */
 629   POOL_DEBUG(SOLV_DEBUG_STATS, "addfileprovides took %d ms\n", solv_timems(now));
 630 }
 631
 632 void
 633 pool_addfileprovides(Pool *pool)
 634 {
 635   pool_addfileprovides_queue(pool, 0, 0);
 636 }
 637