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: stable/12/usr.sbin/portsnap/make_index/make_index.c 326276 2017-11-27 15:37:16Z pfg $");
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
usage(void)81 usage(void)
82 {
83
84 fprintf(stderr, "usage: make_index file\n");
85 exit(1);
86 /* NOTREACHED */
87 }
88
89 static char *
strdup2(const char * str)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 *
makelist(char * str,size_t * n)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 *
portify(char * line)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
portcompare(char * a,char * b)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
heapifyports(PORT ** pp,size_t size,size_t pos)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 *
findport(PORT ** pp,size_t st,size_t en,char * name,char * from)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
translateport(PORT ** pp,size_t pplen,PORT * p)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 *
recurse_one(DEP * d,size_t * nd)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
recurse(PORT * p)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
heapifypkgs(DEP * d,size_t size,size_t pos)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
sortpkgs(DEP * d,size_t nd)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
printport(PORT * p)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
main(int argc,char * argv[])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 }
516