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
37struct port;
38
39typedef union {
40	char * name;
41	struct port * p;
42} DEP;
43
44typedef 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
66static void usage(void);
67static char * strdup2(const char *str);
68static DEP * makelist(char * str, size_t * n);
69static PORT * portify(char * line);
70static int portcompare(char * a, char * b);
71static void heapifyports(PORT **pp, size_t size, size_t pos);
72static PORT * findport(PORT ** pp, size_t st, size_t en, char * name, char * from);
73static void translateport(PORT ** pp, size_t pplen, PORT * p);
74static DEP * recurse_one(DEP * d, size_t * nd);
75static void recurse(PORT * p);
76static void heapifypkgs(DEP * d, size_t size, size_t pos);
77static void sortpkgs(DEP * d, size_t nd);
78static void printport(PORT * p);
79
80static void
81usage(void)
82{
83
84	fprintf(stderr, "usage: make_index file\n");
85	exit(1);
86	/* NOTREACHED */
87}
88
89static char *
90strdup2(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 *) */
101static DEP *
102makelist(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 */
135static PORT *
136portify(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 */
177static int
178portcompare(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] */
210static void
211heapifyports(PORT **pp, size_t size, size_t pos)
212{
213	size_t i = pos;
214	PORT * tmp;
215
216top:
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 */
236static PORT *
237findport(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 */
258static void
259translateport(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 */
276static DEP *
277recurse_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 */
307static void
308recurse(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 */
335static void
336heapifypkgs(DEP * d, size_t size, size_t pos)
337{
338	size_t i = pos;
339	PORT * tmp;
340
341top:
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 */
361static void
362sortpkgs(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. */
381static void
382printport(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
426int
427main(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