usr.sbin/portsnap/make_index/make_index.c

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