1/*
2 * FreeBSD install - a package for the installation and maintenance
3 * of non-core utilities.
4 *
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided 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 * Maxim Sobolev
15 * 14 March 2001
16 *
17 * Routines used to do various operations with dependencies
18 * among installed packages.
19 *
20 */
21
22#include <sys/cdefs.h>
23__FBSDID("$FreeBSD$");
24
25#include "lib.h"
26#include <err.h>
27#include <stdio.h>
28
29void list_deps(const char *pkgname, char **pkgs, char *listed,
30               char *check_loop, char **newpkgs, int *nrnewpkgs,
31               int *err_cnt);
32
33/*
34 * Sort given NULL-terminated list of installed packages (pkgs) in
35 * such a way that if package A depends on package B then after
36 * sorting A will be listed before B no matter how they were
37 * originally positioned in the list.
38 *
39 * Works by performing a recursive depth-first search on the
40 * required-by lists.
41 */
42
43int
44sortdeps(char **pkgs)
45{
46    int i, err_cnt=0;
47    int nrpkgs, nrnewpkgs;
48    char *listed, *check_loop, **newpkgs;
49    char *cp;
50
51    if (pkgs[0] == NULL || pkgs[1] == NULL)
52	return (0);
53
54    nrpkgs = 0;
55    while (pkgs[nrpkgs]) nrpkgs++;
56    listed = alloca(nrpkgs);
57    if (listed == NULL) {
58	warnx("%s(): alloca() failed", __func__);
59	return 1;
60    }
61    bzero(listed,nrpkgs);
62    check_loop = alloca(nrpkgs);
63    if (check_loop == NULL) {
64	warnx("%s(): alloca() failed", __func__);
65	return 1;
66    }
67    bzero(check_loop,nrpkgs);
68    newpkgs = alloca(nrpkgs*sizeof(char*));
69    if (newpkgs == NULL) {
70	warnx("%s(): alloca() failed", __func__);
71	return 1;
72    }
73    nrnewpkgs = 0;
74
75    for (i = 0; pkgs[i]; i++) if (!listed[i]) {
76	check_loop[i] = 1;
77	cp = strchr(pkgs[i], ':');
78	if (cp != NULL)
79	    *cp = '\0';
80	list_deps(pkgs[i],pkgs,listed,check_loop,newpkgs,&nrnewpkgs,&err_cnt);
81	if (cp != NULL)
82	    *cp = ':';
83	listed[i] = 1;
84	newpkgs[nrnewpkgs] = pkgs[i];
85	nrnewpkgs++;
86    }
87
88    if (nrnewpkgs != nrpkgs) {
89	fprintf(stderr,"This shouldn't happen, and indicates a huge error in the code.\n");
90	exit(1);
91    }
92    for (i = 0; i < nrnewpkgs; i++) pkgs[i] = newpkgs[i];
93
94    return err_cnt;
95}
96
97/*
98 * This recursive function lists the dependencies (that is, the
99 * "required-by"s) for pkgname, putting them into newpkgs.
100 */
101
102void list_deps(const char *pkgname, char **pkgs, char *listed,
103               char *check_loop, char **newpkgs, int *nrnewpkgs,
104               int *err_cnt) {
105    char **rb, **rbtmp;
106    char *cp;
107    int errcode, i, j;
108    struct reqr_by_entry *rb_entry;
109    struct reqr_by_head *rb_list;
110
111    if (isinstalledpkg(pkgname) <= 0)
112	return;
113
114    errcode = requiredby(pkgname, &rb_list, FALSE, TRUE);
115    if (errcode < 0)
116	return;
117    /*
118     * We put rb_list into an argv style NULL terminated list,
119     * because requiredby uses some static storage, and list_deps
120     * is a recursive function.
121     */
122
123    rbtmp = rb = alloca((errcode + 1) * sizeof(*rb));
124    if (rb == NULL) {
125	warnx("%s(): alloca() failed", __func__);
126	(*err_cnt)++;
127	return;
128    }
129    STAILQ_FOREACH(rb_entry, rb_list, link) {
130	*rbtmp = alloca(strlen(rb_entry->pkgname) + 1);
131	if (*rbtmp == NULL) {
132	    warnx("%s(): alloca() failed", __func__);
133	    (*err_cnt)++;
134	    return;
135	}
136	strcpy(*rbtmp, rb_entry->pkgname);
137	rbtmp++;
138    }
139    *rbtmp = NULL;
140
141    for (i = 0; rb[i]; i++)
142	for (j = 0; pkgs[j]; j++) if (!listed[j]) {
143	    cp = strchr(pkgs[j], ':');
144	    if (cp != NULL)
145		*cp = '\0';
146	    if (strcmp(rb[i], pkgs[j]) == 0) { /*match */
147		/*
148		 * Try to avoid deadlock if package A depends on B which in
149		 * turn depends on C and C due to an error depends on A.
150		 * It Should Never Happen[tm] in real life.
151		 */
152		if (check_loop[j]) {
153		    warnx("dependency loop detected for package %s", pkgs[j]);
154		    (*err_cnt)++;
155		}
156		else {
157		    check_loop[j] = 1;
158		    list_deps(pkgs[j],pkgs,listed,check_loop,newpkgs,nrnewpkgs,err_cnt);
159		    listed[j] = 1;
160		    newpkgs[*nrnewpkgs] = pkgs[j];
161		    (*nrnewpkgs)++;
162		}
163	    }
164	    if (cp != NULL)
165		*cp = ':';
166	}
167}
168
169/*
170 * Load +REQUIRED_BY file and return a list with names of
171 * packages that require package referred to by `pkgname'.
172 *
173 * Optionally check that packages listed there are actually
174 * installed and filter out those that don't (filter == TRUE).
175 *
176 * strict argument controls whether the caller want warnings
177 * to be emitted when there are some non-fatal conditions,
178 * i.e. package doesn't have +REQUIRED_BY file or some packages
179 * listed in +REQUIRED_BY don't exist.
180 *
181 * Result returned in the **list, while return value is equal
182 * to the number of entries in the resulting list. Print error
183 * message and return -1 on error.
184 */
185int
186requiredby(const char *pkgname, struct reqr_by_head **list, Boolean strict, Boolean filter)
187{
188    FILE *fp;
189    char fbuf[FILENAME_MAX], fname[FILENAME_MAX];
190    int retval;
191    struct reqr_by_entry *rb_entry;
192    static struct reqr_by_head rb_list = STAILQ_HEAD_INITIALIZER(rb_list);
193
194    *list = &rb_list;
195    /* Deallocate any previously allocated space */
196    while (!STAILQ_EMPTY(&rb_list)) {
197	rb_entry = STAILQ_FIRST(&rb_list);
198	STAILQ_REMOVE_HEAD(&rb_list, link);
199	free(rb_entry);
200    }
201
202    if (isinstalledpkg(pkgname) <= 0) {
203	if (strict == TRUE)
204	    warnx("no such package '%s' installed", pkgname);
205	return -1;
206    }
207
208    snprintf(fname, sizeof(fname), "%s/%s/%s", LOG_DIR, pkgname,
209	     REQUIRED_BY_FNAME);
210    fp = fopen(fname, "r");
211    if (fp == NULL) {
212	/* Probably pkgname doesn't have any packages that depend on it */
213	if (strict == TRUE)
214	    warnx("couldn't open dependency file '%s'", fname);
215	return 0;
216    }
217
218    retval = 0;
219    while (fgets(fbuf, sizeof(fbuf), fp) != NULL) {
220	if (fbuf[strlen(fbuf) - 1] == '\n')
221	    fbuf[strlen(fbuf) - 1] = '\0';
222	if (filter == TRUE && isinstalledpkg(fbuf) <= 0) {
223	    if (strict == TRUE)
224		warnx("package '%s' is recorded in the '%s' but isn't "
225		      "actually installed", fbuf, fname);
226	    continue;
227	}
228	retval++;
229	rb_entry = malloc(sizeof(*rb_entry));
230	if (rb_entry == NULL) {
231	    warnx("%s(): malloc() failed", __func__);
232	    retval = -1;
233	    break;
234	}
235	strlcpy(rb_entry->pkgname, fbuf, sizeof(rb_entry->pkgname));
236	STAILQ_INSERT_TAIL(&rb_list, rb_entry, link);
237    }
238    fclose(fp);
239
240    return retval;
241}
242