usr.sbin/portsnap/make_index/make_index.c

   1 /*-
   2  * Copyright 2005 Colin Percival
   3  * All rights reserved
   4  *
   5  * Redistribution and use in source and binary forms, with or without
   6  * modification, are permitted providing that the following conditions
   7  * are met:
   8  * 1. Redistributions of source code must retain the above copyright
   9  *    notice, this list of conditions and the following disclaimer.
  10  * 2. Redistributions in binary form must reproduce the above copyright
  11  *    notice, this list of conditions and the following disclaimer in the
  12  *    documentation and/or other materials provided with the distribution.
  13  *
  14  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
  15  * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
  16  * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  17  * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY
  18  * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  19  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  20  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  21  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
  22  * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING
  23  * IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
  24  * POSSIBILITY OF SUCH DAMAGE.
  25  */
  26
  27 #include <sys/cdefs.h>
  28 __FBSDID("$FreeBSD$");
  29
  30 #include <err.h>
  31 #include <stdio.h>
  32 #include <stdlib.h>
  33 #include <string.h>
  34
  35 struct port;
  36
  37 typedef union {
  38         char * name;
  39         struct port * p;
  40 } DEP;
  41
  42 typedef struct port {
  43         char * pkgname;
  44         char * portdir;
  45         char * prefix;
  46         char * comment;
  47         char * pkgdescr;
  48         char * maintainer;
  49         char * categories;
  50         size_t n_edep;
  51         DEP * edep;
  52         size_t n_pdep;
  53         DEP * pdep;
  54         size_t n_fdep;
  55         DEP * fdep;
  56         size_t n_bdep;
  57         DEP * bdep;
  58         size_t n_rdep;
  59         DEP * rdep;
  60         char * www;
  61         int recursed;
  62 } PORT;
  63
  64 static void usage(void);
  65 static char * strdup2(const char *str);
  66 static DEP * makelist(char * str, size_t * n);
  67 static PORT * portify(char * line);
  68 static int portcompare(char * a, char * b);
  69 static void heapifyports(PORT **pp, size_t size, size_t pos);
  70 static PORT * findport(PORT ** pp, size_t st, size_t en, char * name, char * from);
  71 static void translateport(PORT ** pp, size_t pplen, PORT * p);
  72 static DEP * recurse_one(DEP * d, size_t * nd);
  73 static void recurse(PORT * p);
  74 static void heapifypkgs(DEP * d, size_t size, size_t pos);
  75 static void sortpkgs(DEP * d, size_t nd);
  76 static void printport(PORT * p);
  77
  78 static void
  79 usage(void)
  80 {
  81
  82         fprintf(stderr, "usage: make_index file\n");
  83         exit(1);
  84         /* NOTREACHED */
  85 }
  86
  87 static char *
  88 strdup2(const char *str)
  89 {
  90         char * r;
  91
  92         r = strdup(str);
  93         if (r == NULL)
  94                 err(1, "strdup");
  95         return r;
  96 }
  97
  98 /* Take a space-separated list and return an array of (char *) */
  99 static DEP *
 100 makelist(char * str, size_t * n)
 101 {
 102         DEP * d;
 103         size_t i;
 104
 105         /* No depends at all? */
 106         if (str[0] == 0) {
 107                 *n = 0;
 108                 return NULL;
 109         }
 110
 111         /* Count the number of fields */
 112         *n = 1;
 113         for (i = 0; str[i] != 0; i++)
 114                 if (str[i] == ' ')
 115                         (*n)++;
 116
 117         /* Allocate and fill an array */
 118         d = malloc(*n * sizeof(DEP));
 119         if (d == NULL)
 120                 err(1, "malloc(DEP)");
 121         for (i = 0; i < *n; i++) {
 122                 d[i].name = strdup2(strsep(&str, " "));
 123
 124                 /* Strip trailing slashes */
 125                 if (d[i].name[strlen(d[i].name) - 1] == '/')
 126                         d[i].name[strlen(d[i].name) - 1] = 0;
 127         }
 128
 129         return d;
 130 }
 131
 132 /* Take a port's describe line and split it into fields */
 133 static PORT *
 134 portify(char * line)
 135 {
 136         PORT * p;
 137         size_t i, n;
 138
 139         /* Verify that line has the right number of fields */
 140         for (n = i = 0; line[i] != 0; i++)
 141                 if (line[i] == '|')
 142                         n++;
 143         if (n != 12)
 144                 errx(1, "Port describe line is corrupt:\n%s\n", line);
 145
 146         p = malloc(sizeof(PORT));
 147         if (p == NULL)
 148                 err(1, "malloc(PORT)");
 149
 150         p->pkgname = strdup2(strsep(&line, "|"));
 151         p->portdir = strdup2(strsep(&line, "|"));
 152         p->prefix = strdup2(strsep(&line, "|"));
 153         p->comment = strdup2(strsep(&line, "|"));
 154         p->pkgdescr = strdup2(strsep(&line, "|"));
 155         p->maintainer = strdup2(strsep(&line, "|"));
 156         p->categories = strdup2(strsep(&line, "|"));
 157         p->edep = makelist(strsep(&line, "|"), &p->n_edep);
 158         p->pdep = makelist(strsep(&line, "|"), &p->n_pdep);
 159         p->fdep = makelist(strsep(&line, "|"), &p->n_fdep);
 160         p->bdep = makelist(strsep(&line, "|"), &p->n_bdep);
 161         p->rdep = makelist(strsep(&line, "|"), &p->n_rdep);
 162         p->www = strdup2(strsep(&line, "|"));
 163
 164         p->recursed = 0;
 165
 166         /*
 167          * line will now be equal to NULL -- we counted the field
 168          * separators at the top of the function.
 169          */
 170
 171         return p;
 172 }
 173
 174 /* Returns -1, 0, or 1 based on a comparison of the portdir strings */
 175 static int
 176 portcompare(char * a, char * b)
 177 {
 178         size_t i;
 179
 180         /* Find first non-matching position */
 181         for (i = 0; ; i++) {
 182                 if (a[i] != b[i])
 183                         break;
 184                 if (a[i] == 0)                  /* End of strings */
 185                         return 0;
 186         }
 187
 188         /* One string is a prefix of the other */
 189         if (a[i] == 0)
 190                 return -1;
 191         if (b[i] == 0)
 192                 return 1;
 193
 194         /* One string has a category which is a prefix of the other */
 195         if (a[i] == '/')
 196                 return -1;
 197         if (b[i] == '/')
 198                 return 1;
 199
 200         /* The two strings are simply different */
 201         if (a[i] < b[i])
 202                 return -1;
 203         else
 204                 return 1;
 205 }
 206
 207 /* Heapify (PORT *) number pos in a pseudo-heap pp[0]..pp[size - 1] */
 208 static void
 209 heapifyports(PORT **pp, size_t size, size_t pos)
 210 {
 211         size_t i = pos;
 212         PORT * tmp;
 213
 214 top:
 215         /* Find the largest value out of {pos, 2*pos+1, 2*pos+2} */
 216         if ((2 * pos + 1 < size) &&
 217             (portcompare(pp[i]->portdir, pp[2 * pos + 1]->portdir) < 0))
 218                 i = 2 * pos + 1;
 219         if ((2 * pos + 2 < size) &&
 220             (portcompare(pp[i]->portdir, pp[2 * pos + 2]->portdir) < 0))
 221                 i = 2 * pos + 2;
 222
 223         /* If necessary, swap elements and iterate down the tree. */
 224         if (i != pos) {
 225                 tmp = pp[pos];
 226                 pp[pos] = pp[i];
 227                 pp[i] = tmp;
 228                 pos = i;
 229                 goto top;
 230         }
 231 }
 232
 233 /* Translate a port directory name into a (PORT *), and free the name */
 234 static PORT *
 235 findport(PORT ** pp, size_t st, size_t en, char * name, char * from)
 236 {
 237         size_t mid;
 238         int r;
 239
 240         if (st == en)
 241                 errx(1, "%s: no entry for %s", from, name);
 242
 243         mid = (st + en) / 2;
 244         r = portcompare(pp[mid]->portdir, name);
 245
 246         if (r == 0) {
 247                 free(name);
 248                 return pp[mid];
 249         } else if (r < 0)
 250                 return findport(pp, mid + 1, en, name, from);
 251         else
 252                 return findport(pp, st, mid, name, from);
 253 }
 254
 255 /* Translate all depends from names into PORT *s */
 256 static void
 257 translateport(PORT ** pp, size_t pplen, PORT * p)
 258 {
 259         size_t i;
 260
 261         for (i = 0; i < p->n_edep; i++)
 262                 p->edep[i].p = findport(pp, 0, pplen, p->edep[i].name, p->portdir);
 263         for (i = 0; i < p->n_pdep; i++)
 264                 p->pdep[i].p = findport(pp, 0, pplen, p->pdep[i].name, p->portdir);
 265         for (i = 0; i < p->n_fdep; i++)
 266                 p->fdep[i].p = findport(pp, 0, pplen, p->fdep[i].name, p->portdir);
 267         for (i = 0; i < p->n_bdep; i++)
 268                 p->bdep[i].p = findport(pp, 0, pplen, p->bdep[i].name, p->portdir);
 269         for (i = 0; i < p->n_rdep; i++)
 270                 p->rdep[i].p = findport(pp, 0, pplen, p->rdep[i].name, p->portdir);
 271 }
 272
 273 /* Recurse on one specific depends list */
 274 static DEP *
 275 recurse_one(DEP * d, size_t * nd)
 276 {
 277         size_t i, j, k, n, N;
 278
 279         N = n = *nd;
 280         for (i = 0; i < n; i++) {
 281                 recurse(d[i].p);
 282                 for (j = 0; j < d[i].p->n_rdep; j++) {
 283                         for (k = 0; k < N; k++) {
 284                                 if (d[i].p->rdep[j].p == d[k].p)
 285                                         break;
 286                         }
 287                         if (k == N) {
 288                                 N++;
 289                                 if (N >= *nd) {
 290                                         *nd += *nd;
 291                                         d = realloc(d, *nd * sizeof(DEP));
 292                                         if (d == NULL)
 293                                                 err(1, "realloc(d)");
 294                                 }
 295                                 d[k].p = d[i].p->rdep[j].p;
 296                         }
 297                 }
 298         }
 299         *nd = N;
 300
 301         return d;
 302 }
 303
 304 /* Recurse on the depends lists */
 305 static void
 306 recurse(PORT * p)
 307 {
 308         switch (p->recursed) {
 309         case 0:
 310                 /* First time we've seen this port */
 311                 p->recursed = 1;
 312                 break;
 313         case 1:
 314                 /* We're in the middle of recursing this port */
 315                 errx(1, "Circular dependency loop found: %s"
 316                     " depends upon itself.\n", p->pkgname);
 317         case 2:
 318                 /* This port has already been recursed */
 319                 return;
 320         }
 321
 322         p->edep = recurse_one(p->edep, &p->n_edep);
 323         p->pdep = recurse_one(p->pdep, &p->n_pdep);
 324         p->fdep = recurse_one(p->fdep, &p->n_fdep);
 325         p->bdep = recurse_one(p->bdep, &p->n_bdep);
 326         p->rdep = recurse_one(p->rdep, &p->n_rdep);
 327
 328         /* Finished recursing on this port */
 329         p->recursed = 2;
 330 }
 331
 332 /* Heapify an element in a package list */
 333 static void
 334 heapifypkgs(DEP * d, size_t size, size_t pos)
 335 {
 336         size_t i = pos;
 337         PORT * tmp;
 338
 339 top:
 340         /* Find the largest value out of {pos, 2*pos+1, 2*pos+2} */
 341         if ((2 * pos + 1 < size) &&
 342             (strcmp(d[i].p->pkgname, d[2 * pos + 1].p->pkgname) < 0))
 343                 i = 2 * pos + 1;
 344         if ((2 * pos + 2 < size) &&
 345             (strcmp(d[i].p->pkgname, d[2 * pos + 2].p->pkgname) < 0))
 346                 i = 2 * pos + 2;
 347
 348         /* If necessary, swap elements and iterate down the tree. */
 349         if (i != pos) {
 350                 tmp = d[pos].p;
 351                 d[pos].p = d[i].p;
 352                 d[i].p = tmp;
 353                 pos = i;
 354                 goto top;
 355         }
 356 }
 357
 358 /* Sort a list of dependent packages in alphabetical order */
 359 static void
 360 sortpkgs(DEP * d, size_t nd)
 361 {
 362         size_t i;
 363         PORT * tmp;
 364
 365         if (nd == 0)
 366                 return;
 367
 368         for (i = nd; i > 0; i--)
 369                 heapifypkgs(d, nd, i - 1);      /* Build a heap */
 370         for (i = nd - 1; i > 0; i--) {
 371                 tmp = d[0].p;                   /* Extract elements */
 372                 d[0].p = d[i].p;
 373                 d[i].p = tmp;
 374                 heapifypkgs(d, i, 0);           /* And re-heapify */
 375         }
 376 }
 377
 378 /* Output an index line for the given port. */
 379 static void
 380 printport(PORT * p)
 381 {
 382         size_t i;
 383
 384         sortpkgs(p->edep, p->n_edep);
 385         sortpkgs(p->pdep, p->n_pdep);
 386         sortpkgs(p->fdep, p->n_fdep);
 387         sortpkgs(p->bdep, p->n_bdep);
 388         sortpkgs(p->rdep, p->n_rdep);
 389
 390         printf("%s|%s|%s|%s|%s|%s|%s|",
 391             p->pkgname, p->portdir, p->prefix, p->comment, p->pkgdescr,
 392             p->maintainer, p->categories);
 393         for (i = 0; i < p->n_bdep; i++)
 394                 printf("%s%s", i ? " " : "", p->bdep[i].p->pkgname);
 395         printf("|");
 396         for (i = 0; i < p->n_rdep; i++)
 397                 printf("%s%s", i ? " " : "", p->rdep[i].p->pkgname);
 398         printf("|");
 399         printf("%s|", p->www);
 400         for (i = 0; i < p->n_edep; i++)
 401                 printf("%s%s", i ? " " : "", p->edep[i].p->pkgname);
 402         printf("|");
 403         for (i = 0; i < p->n_pdep; i++)
 404                 printf("%s%s", i ? " " : "", p->pdep[i].p->pkgname);
 405         printf("|");
 406         for (i = 0; i < p->n_fdep; i++)
 407                 printf("%s%s", i ? " " : "", p->fdep[i].p->pkgname);
 408         printf("\n");
 409 }
 410
 411 /*
 412  * Algorithm:
 413  * 1. Suck in all the data, splitting into fields.
 414  * 1a. If there are no ports, there is no INDEX.
 415  * 2. Sort the ports according to port directory.
 416  * 3. Using a binary search, translate each dependency from a
 417  * port directory name into a pointer to a port.
 418  * 4. Recursively follow dependencies, expanding the lists of
 419  * pointers as needed (using realloc).
 420  * 5. Iterate through the ports, printing them out (remembering
 421  * to list the dependent ports in alphabetical order).
 422  */
 423
 424 int
 425 main(int argc, char *argv[])
 426 {
 427         FILE * f;
 428         char * line;
 429         size_t linelen;
 430         PORT ** pp;     /* Array of pointers to PORTs */
 431         PORT * tmp;
 432         size_t pplen;   /* Allocated size of array */
 433         size_t i;
 434
 435         if (argc != 2)
 436                 usage();
 437         if ((f = fopen(argv[1], "r")) == NULL)
 438                 err(1, "fopen(%s)", argv[1]);
 439
 440         pplen = 1024;
 441         if ((pp = malloc(pplen * sizeof(PORT *))) == NULL)
 442                 err(1, "malloc(pp)");
 443
 444         /*
 445          * 1. Suck in all the data, splitting into fields.
 446          */
 447         for(i = 0; (line = fgetln(f, &linelen)) != NULL; i++) {
 448                 if (line[linelen - 1] != '\n')
 449                         errx(1, "Unterminated line encountered");
 450                 line[linelen - 1] = 0;
 451
 452                 /* Enlarge array if needed */
 453                 if (i >= pplen) {
 454                         pplen *= 2;
 455                         if ((pp = realloc(pp, pplen * sizeof(PORT *))) == NULL)
 456                                 err(1, "realloc(pp)");
 457                 }
 458
 459                 pp[i] = portify(line);
 460         }
 461         /* Reallocate to the correct size */
 462         pplen = i;
 463         if ((pp = realloc(pp, pplen * sizeof(PORT *))) == NULL)
 464                 err(1, "realloc(pp)");
 465
 466         /* Make sure we actually reached the EOF */
 467         if (!feof(f))
 468                 err(1, "fgetln(%s)", argv[1]);
 469         /* Close the describes file */
 470         if (fclose(f) != 0)
 471                 err(1, "fclose(%s)", argv[1]);
 472
 473         /*
 474          * 1a. If there are no ports, there is no INDEX.
 475          */
 476         if (pplen == 0)
 477                 return 0;
 478
 479         /*
 480          * 2. Sort the ports according to port directory.
 481          */
 482         for (i = pplen; i > 0; i--)
 483                 heapifyports(pp, pplen, i - 1); /* Build a heap */
 484         for (i = pplen - 1; i > 0; i--) {
 485                 tmp = pp[0];                    /* Extract elements */
 486                 pp[0] = pp[i];
 487                 pp[i] = tmp;
 488                 heapifyports(pp, i, 0);         /* And re-heapify */
 489         }
 490
 491         /*
 492          * 3. Using a binary search, translate each dependency from a
 493          * port directory name into a pointer to a port.
 494          */
 495         for (i = 0; i < pplen; i++)
 496                 translateport(pp, pplen, pp[i]);
 497
 498         /*
 499          * 4. Recursively follow dependencies, expanding the lists of
 500          * pointers as needed (using realloc).
 501          */
 502         for (i = 0; i < pplen; i++)
 503                 recurse(pp[i]);
 504
 505         /*
 506          * 5. Iterate through the ports, printing them out (remembering
 507          * to list the dependent ports in alphabetical order).
 508          */
 509         for (i = 0; i < pplen; i++)
 510                 printport(pp[i]);
 511
 512         return 0;
 513 }