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
35struct port;
36
37typedef union {
38	char * name;
39	struct port * p;
40} DEP;
41
42typedef 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
64static void usage(void);
65static char * strdup2(const char *str);
66static DEP * makelist(char * str, size_t * n);
67static PORT * portify(char * line);
68static int portcompare(char * a, char * b);
69static void heapifyports(PORT **pp, size_t size, size_t pos);
70static PORT * findport(PORT ** pp, size_t st, size_t en, char * name, char * from);
71static void translateport(PORT ** pp, size_t pplen, PORT * p);
72static DEP * recurse_one(DEP * d, size_t * nd);
73static void recurse(PORT * p);
74static void heapifypkgs(DEP * d, size_t size, size_t pos);
75static void sortpkgs(DEP * d, size_t nd);
76static void printport(PORT * p);
77
78static void
79usage(void)
80{
81
82	fprintf(stderr, "usage: make_index file\n");
83	exit(1);
84	/* NOTREACHED */
85}
86
87static char *
88strdup2(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 *) */
99static DEP *
100makelist(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 */
133static PORT *
134portify(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 */
175static int
176portcompare(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] */
208static void
209heapifyports(PORT **pp, size_t size, size_t pos)
210{
211	size_t i = pos;
212	PORT * tmp;
213
214top:
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 */
234static PORT *
235findport(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 */
256static void
257translateport(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 */
274static DEP *
275recurse_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 */
305static void
306recurse(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 */
333static void
334heapifypkgs(DEP * d, size_t size, size_t pos)
335{
336	size_t i = pos;
337	PORT * tmp;
338
339top:
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 */
359static void
360sortpkgs(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. */
379static void
380printport(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
424int
425main(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}
514