XBPS Library API  0.19
The X Binary Package System
transaction_sortdeps.c
1 /*-
2  * Copyright (c) 2009-2012 Juan Romero Pardines.
3  * All rights reserved.
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  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
15  * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
16  * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
17  * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
18  * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
19  * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
20  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
21  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
22  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
23  * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
24  */
25 
26 #include <stdio.h>
27 #include <stdlib.h>
28 #include <string.h>
29 #include <errno.h>
30 
31 #include "xbps_api_impl.h"
32 
33 /*
34  * Sorting algorithm for packages in the transaction dictionary.
35  * The transaction dictionary contains all package dictionaries found from
36  * the repository plist index file in the "unsorted_deps" array.
37  *
38  * Any package in the unsorted_deps array is added into the tail and
39  * later if a package dependency has an index greater than current
40  * package, the package dependency is moved just before it.
41  *
42  * Once that all package dependencies for a package are in the correct
43  * index, the counter is increased. When all packages in the "unsorted_deps"
44  * array are processed the loop is stopped and the counter should have
45  * the same number than the "unsorted_deps" array... otherwise something
46  * went wrong.
47  */
48 
49 struct pkgdep {
50  TAILQ_ENTRY(pkgdep) pkgdep_entries;
51  prop_dictionary_t d;
52  char *name;
53 };
54 
55 static TAILQ_HEAD(pkgdep_head, pkgdep) pkgdep_list =
56  TAILQ_HEAD_INITIALIZER(pkgdep_list);
57 
58 static struct pkgdep *
59 pkgdep_find(const char *pkg)
60 {
61  struct pkgdep *pd = NULL, *pd_new = NULL;
62  const char *pkgver, *tract;
63 
64  TAILQ_FOREACH_SAFE(pd, &pkgdep_list, pkgdep_entries, pd_new) {
65  if (pd->d == NULL) {
66  /* ignore entries without dictionary */
67  continue;
68  }
69  prop_dictionary_get_cstring_nocopy(pd->d,
70  "transaction", &tract);
71  /* ignore pkgs to be removed */
72  if (strcmp(tract, "remove") == 0)
73  continue;
74  /* simple match */
75  prop_dictionary_get_cstring_nocopy(pd->d, "pkgver", &pkgver);
76  if (strcmp(pkgver, pkg) == 0)
77  return pd;
78  /* pkg expression match */
79  if (xbps_pkgpattern_match(pkgver, pkg))
80  return pd;
81  /* virtualpkg expression match */
82  if (xbps_match_virtual_pkg_in_dict(pd->d, pkg, true))
83  return pd;
84  }
85 
86  /* not found */
87  return NULL;
88 }
89 
90 static ssize_t
91 pkgdep_find_idx(const char *pkg)
92 {
93  struct pkgdep *pd, *pd_new;
94  ssize_t idx = 0;
95  const char *pkgver, *tract;
96 
97  TAILQ_FOREACH_SAFE(pd, &pkgdep_list, pkgdep_entries, pd_new) {
98  if (pd->d == NULL) {
99  /* ignore entries without dictionary */
100  idx++;
101  continue;
102  }
103  prop_dictionary_get_cstring_nocopy(pd->d,
104  "transaction", &tract);
105  /* ignore pkgs to be removed */
106  if (strcmp(tract, "remove") == 0) {
107  idx++;
108  continue;
109  }
110  /* simple match */
111  prop_dictionary_get_cstring_nocopy(pd->d, "pkgver", &pkgver);
112  if (strcmp(pkgver, pkg) == 0)
113  return idx;
114  /* pkg expression match */
115  if (xbps_pkgpattern_match(pkgver, pkg))
116  return idx;
117  /* virtualpkg expression match */
118  if (xbps_match_virtual_pkg_in_dict(pd->d, pkg, true))
119  return idx;
120 
121  idx++;
122  }
123  /* not found */
124  return -1;
125 }
126 
127 static void
128 pkgdep_release(struct pkgdep *pd)
129 {
130  free(pd->name);
131  free(pd);
132  pd = NULL;
133 }
134 
135 static struct pkgdep *
136 pkgdep_alloc(prop_dictionary_t d, const char *pkg)
137 {
138  struct pkgdep *pd;
139 
140  pd = malloc(sizeof(*pd));
141  assert(pd);
142  pd->d = d;
143  pd->name = strdup(pkg);
144 
145  return pd;
146 }
147 
148 static void
149 pkgdep_end(prop_array_t sorted)
150 {
151  struct pkgdep *pd;
152 
153  while ((pd = TAILQ_FIRST(&pkgdep_list)) != NULL) {
154  TAILQ_REMOVE(&pkgdep_list, pd, pkgdep_entries);
155  if (sorted != NULL && pd->d != NULL)
156  prop_array_add(sorted, pd->d);
157 
158  pkgdep_release(pd);
159  }
160 }
161 
162 static int
163 sort_pkg_rundeps(struct xbps_handle *xhp,
164  struct pkgdep *pd,
165  prop_array_t pkg_rundeps,
166  prop_array_t unsorted)
167 {
168  prop_dictionary_t curpkgd;
169  struct pkgdep *lpd, *pdn;
170  const char *str, *tract;
171  ssize_t pkgdepidx, curpkgidx;
172  size_t i, idx = 0;
173  int rv = 0;
174 
175  xbps_dbg_printf_append(xhp, "\n");
176  curpkgidx = pkgdep_find_idx(pd->name);
177 
178 again:
179  for (i = idx; i < prop_array_count(pkg_rundeps); i++) {
180  prop_array_get_cstring_nocopy(pkg_rundeps, i, &str);
181  xbps_dbg_printf(xhp, " Required dependency '%s': ", str);
182 
183  pdn = pkgdep_find(str);
184  if ((pdn == NULL) && xbps_pkg_is_installed(xhp, str)) {
185  /*
186  * Package dependency is installed, just add to
187  * the list but just mark it as "installed", to avoid
188  * calling xbps_check_is_installed_pkg_by_name(),
189  * which is expensive.
190  */
191  xbps_dbg_printf_append(xhp, "installed.\n");
192  lpd = pkgdep_alloc(NULL, str);
193  TAILQ_INSERT_TAIL(&pkgdep_list, lpd, pkgdep_entries);
194  continue;
195  } else if (pdn != NULL && pdn->d == NULL) {
196  /*
197  * Package was added previously into the list
198  * and is installed, skip.
199  */
200  xbps_dbg_printf_append(xhp, "installed.\n");
201  continue;
202  }
203  if (((curpkgd = xbps_find_pkg_in_array(unsorted, str)) == NULL) &&
204  ((curpkgd = xbps_find_virtualpkg_in_array(xhp, unsorted, str)) == NULL)) {
205  rv = EINVAL;
206  break;
207  }
208  prop_dictionary_get_cstring_nocopy(curpkgd,
209  "transaction", &tract);
210 
211  lpd = pkgdep_alloc(curpkgd, str);
212 
213  if (pdn == NULL) {
214  /*
215  * If package is not in the list, add to the tail
216  * and iterate at the same position.
217  */
218  TAILQ_INSERT_TAIL(&pkgdep_list, lpd, pkgdep_entries);
219  idx = i;
220  xbps_dbg_printf_append(xhp, "added into the tail, "
221  "checking again...\n");
222  goto again;
223  }
224  /*
225  * Find package dependency index.
226  */
227  pkgdepidx = pkgdep_find_idx(str);
228  /*
229  * If package dependency index is less than current
230  * package index, it's already sorted.
231  */
232  if (pkgdepidx < curpkgidx) {
233  xbps_dbg_printf_append(xhp, "already sorted.\n");
234  pkgdep_release(lpd);
235  } else {
236  /*
237  * Remove package dependency from list and move
238  * it before current package.
239  */
240  TAILQ_REMOVE(&pkgdep_list, pdn, pkgdep_entries);
241  pkgdep_release(pdn);
242  TAILQ_INSERT_BEFORE(pd, lpd, pkgdep_entries);
243  xbps_dbg_printf_append(xhp,
244  "added before `%s'.\n", pd->name);
245  }
246  }
247 
248  return rv;
249 }
250 
251 int HIDDEN
252 xbps_transaction_sort(struct xbps_handle *xhp)
253 {
254  prop_array_t provides, sorted, unsorted, rundeps;
255  prop_object_t obj;
256  struct pkgdep *pd;
257  size_t i, j, ndeps = 0, cnt = 0;
258  const char *pkgname, *pkgver, *tract, *vpkgdep;
259  int rv = 0;
260  bool vpkg_found;
261 
262  if ((sorted = prop_array_create()) == NULL)
263  return ENOMEM;
264  /*
265  * Add sorted packages array into transaction dictionary (empty).
266  */
267  if (!prop_dictionary_set(xhp->transd, "packages", sorted)) {
268  rv = EINVAL;
269  goto out;
270  }
271  /*
272  * All required deps are satisfied (already installed).
273  */
274  unsorted = prop_dictionary_get(xhp->transd, "unsorted_deps");
275  if (prop_array_count(unsorted) == 0) {
276  prop_dictionary_set(xhp->transd, "packages", sorted);
277  prop_object_release(sorted);
278  return 0;
279  }
280  /*
281  * The sorted array should have the same capacity than
282  * all objects in the unsorted array.
283  */
284  ndeps = prop_array_count(unsorted);
285  /*
286  * Iterate over the unsorted package dictionaries and sort all
287  * its package dependencies.
288  */
289  for (i = 0; i < ndeps; i++) {
290  vpkg_found = false;
291  obj = prop_array_get(unsorted, i);
292  prop_dictionary_get_cstring_nocopy(obj, "pkgname", &pkgname);
293  prop_dictionary_get_cstring_nocopy(obj, "pkgver", &pkgver);
294  prop_dictionary_get_cstring_nocopy(obj, "transaction", &tract);
295  provides = prop_dictionary_get(obj, "provides");
296  xbps_dbg_printf(xhp, "Sorting package '%s' (%s): ", pkgver, tract);
297 
298  if (provides) {
299  /*
300  * If current pkgdep provides any virtual pkg check
301  * if any of them was previously added. If true, don't
302  * add it into the list again, just order its deps.
303  */
304  for (j = 0; j < prop_array_count(provides); j++) {
305  prop_array_get_cstring_nocopy(provides,
306  j, &vpkgdep);
307  pd = pkgdep_find(vpkgdep);
308  if (pd != NULL) {
309  xbps_dbg_printf_append(xhp, "already "
310  "sorted via `%s' vpkg.", vpkgdep);
311  vpkg_found = true;
312  break;
313  }
314  }
315  }
316  if (!vpkg_found && (pd = pkgdep_find(pkgver)) == NULL) {
317  /*
318  * If package not in list, just add to the tail.
319  */
320  pd = pkgdep_alloc(obj, pkgver);
321  if (pd == NULL) {
322  pkgdep_end(NULL);
323  rv = ENOMEM;
324  goto out;
325  }
326  if (strcmp(tract, "remove") == 0) {
327  xbps_dbg_printf_append(xhp, "added into head.\n");
328  TAILQ_INSERT_HEAD(&pkgdep_list, pd,
329  pkgdep_entries);
330  cnt++;
331  continue;
332  } else {
333  xbps_dbg_printf_append(xhp, "added into tail.");
334  TAILQ_INSERT_TAIL(&pkgdep_list, pd,
335  pkgdep_entries);
336  }
337  }
338  /*
339  * Packages that don't have deps go at head, because
340  * it doesn't matter.
341  */
342  rundeps = prop_dictionary_get(obj, "run_depends");
343  if (rundeps == NULL || prop_array_count(rundeps) == 0) {
344  xbps_dbg_printf_append(xhp, "\n");
345  cnt++;
346  continue;
347  }
348  /*
349  * Sort package run-time dependencies for this package.
350  */
351  if ((rv = sort_pkg_rundeps(xhp, pd, rundeps, unsorted)) != 0) {
352  pkgdep_end(NULL);
353  goto out;
354  }
355  cnt++;
356  }
357  /*
358  * We are done, now we have to copy all pkg dictionaries
359  * from the sorted list into the "packages" array, and at
360  * the same time freeing memory used for temporary sorting.
361  */
362  pkgdep_end(sorted);
363  /*
364  * Sanity check that the array contains the same number of
365  * objects than the total number of required dependencies.
366  */
367  assert(cnt == prop_array_count(unsorted));
368  /*
369  * We are done, all packages were sorted... remove the
370  * temporary array with unsorted packages.
371  */
372  prop_dictionary_remove(xhp->transd, "unsorted_deps");
373 out:
374  if (rv != 0)
375  prop_dictionary_remove(xhp->transd, "packages");
376 
377  prop_object_release(sorted);
378 
379  return rv;
380 }
Generated on Wed Dec 19 2012 00:58:26 for XBPS Library API by   doxygen 1.8.2