1 /*
2 * queue.c
3 * compilation of a list of packages into a world dependency set
4 *
5 * SPDX-License-Identifier: pkgconf
6 *
7 * Copyright (c) 2012 pkgconf authors (see AUTHORS).
8 *
9 * Permission to use, copy, modify, and/or distribute this software for any
10 * purpose with or without fee is hereby granted, provided that the above
11 * copyright notice and this permission notice appear in all copies.
12 *
13 * This software is provided 'as is' and without any warranty, express or
14 * implied. In no event shall the authors be liable for any damages arising
15 * from the use of this software.
16 */
17
18 #include <libpkgconf/stdinc.h>
19 #include <libpkgconf/libpkgconf.h>
20
21 /*
22 * !doc
23 *
24 * libpkgconf `queue` module
25 * =========================
26 *
27 * The `queue` module provides an interface that allows easily building a dependency graph from an
28 * arbitrary set of dependencies. It also provides support for doing "preflight" checks on the entire
29 * dependency graph prior to working with it.
30 *
31 * Using the `queue` module functions is the recommended way of working with dependency graphs.
32 */
33
34 /*
35 * !doc
36 *
37 * .. c:function:: void pkgconf_queue_push_dependency(pkgconf_list_t *list, const pkgconf_dependency_t *dep)
38 *
39 * Pushes a requested dependency onto the dependency resolver's queue which is described by
40 * a pkgconf_dependency_t node.
41 *
42 * :param pkgconf_list_t* list: the dependency resolution queue to add the package request to.
43 * :param pkgconf_dependency_t* dep: the dependency requested
44 * :return: nothing
45 */
46 void
pkgconf_queue_push_dependency(pkgconf_list_t * list,const pkgconf_dependency_t * dep)47 pkgconf_queue_push_dependency(pkgconf_list_t *list, const pkgconf_dependency_t *dep)
48 {
49 pkgconf_buffer_t depbuf = PKGCONF_BUFFER_INITIALIZER;
50 pkgconf_queue_t *pkgq = calloc(1, sizeof(pkgconf_queue_t));
51
52 if (pkgq == NULL)
53 return;
54
55 pkgconf_buffer_append(&depbuf, dep->package);
56 if (dep->version != NULL)
57 pkgconf_buffer_append_fmt(&depbuf, " %s %s", pkgconf_pkg_get_comparator(dep), dep->version);
58
59 pkgq->package = pkgconf_buffer_freeze(&depbuf);
60 pkgconf_node_insert_tail(&pkgq->iter, pkgq, list);
61 }
62
63 /*
64 * !doc
65 *
66 * .. c:function:: void pkgconf_queue_push(pkgconf_list_t *list, const char *package)
67 *
68 * Pushes a requested dependency onto the dependency resolver's queue.
69 *
70 * :param pkgconf_list_t* list: the dependency resolution queue to add the package request to.
71 * :param char* package: the dependency atom requested
72 * :return: nothing
73 */
74 void
pkgconf_queue_push(pkgconf_list_t * list,const char * package)75 pkgconf_queue_push(pkgconf_list_t *list, const char *package)
76 {
77 pkgconf_queue_t *pkgq = calloc(1, sizeof(pkgconf_queue_t));
78
79 if (pkgq == NULL)
80 return;
81
82 pkgq->package = strdup(package);
83 pkgconf_node_insert_tail(&pkgq->iter, pkgq, list);
84 }
85
86 /*
87 * !doc
88 *
89 * .. c:function:: bool pkgconf_queue_compile(pkgconf_client_t *client, pkgconf_pkg_t *world, pkgconf_list_t *list)
90 *
91 * Compile a dependency resolution queue into a dependency resolution problem if possible, otherwise report an error.
92 *
93 * :param pkgconf_client_t* client: The pkgconf client object to use for dependency resolution.
94 * :param pkgconf_pkg_t* world: The designated root of the dependency graph.
95 * :param pkgconf_list_t* list: The list of dependency requests to consider.
96 * :return: true if the built dependency resolution problem is consistent, else false
97 * :rtype: bool
98 */
99 bool
pkgconf_queue_compile(pkgconf_client_t * client,pkgconf_pkg_t * world,pkgconf_list_t * list)100 pkgconf_queue_compile(pkgconf_client_t *client, pkgconf_pkg_t *world, pkgconf_list_t *list)
101 {
102 pkgconf_node_t *iter;
103
104 PKGCONF_FOREACH_LIST_ENTRY(list->head, iter)
105 {
106 pkgconf_queue_t *pkgq;
107
108 pkgq = iter->data;
109 pkgconf_dependency_parse(client, world, &world->required, pkgq->package, PKGCONF_PKG_DEPF_QUERY);
110 }
111
112 return (world->required.head != NULL);
113 }
114
115 /*
116 * !doc
117 *
118 * .. c:function:: void pkgconf_queue_free(pkgconf_list_t *list)
119 *
120 * Release any memory related to a dependency resolution queue.
121 *
122 * :param pkgconf_list_t* list: The dependency resolution queue to release.
123 * :return: nothing
124 */
125 void
pkgconf_queue_free(pkgconf_list_t * list)126 pkgconf_queue_free(pkgconf_list_t *list)
127 {
128 pkgconf_node_t *node, *tnode;
129
130 PKGCONF_FOREACH_LIST_ENTRY_SAFE(list->head, tnode, node)
131 {
132 pkgconf_queue_t *pkgq = node->data;
133
134 free(pkgq->package);
135 free(pkgq);
136 }
137 }
138
139 static void
pkgconf_queue_mark_public(pkgconf_client_t * client,pkgconf_pkg_t * pkg,void * data)140 pkgconf_queue_mark_public(pkgconf_client_t *client, pkgconf_pkg_t *pkg, void *data)
141 {
142 if (pkg->flags & PKGCONF_PKG_PROPF_VISITED_PRIVATE)
143 {
144 pkgconf_list_t *list = data;
145 pkgconf_node_t *node;
146
147 PKGCONF_FOREACH_LIST_ENTRY(list->head, node)
148 {
149 pkgconf_dependency_t *dep = node->data;
150 if (dep->match == pkg)
151 dep->flags &= ~PKGCONF_PKG_DEPF_PRIVATE;
152 }
153
154 pkg->flags &= ~PKGCONF_PKG_PROPF_VISITED_PRIVATE;
155
156 PKGCONF_TRACE(client, "%s: updated, public", pkg->id);
157 }
158 }
159
160 static unsigned int
161 pkgconf_queue_collect_dependencies_main(pkgconf_client_t *client,
162 pkgconf_pkg_t *root,
163 void *data,
164 int maxdepth);
165
166 static inline unsigned int
pkgconf_queue_collect_dependencies_walk(pkgconf_client_t * client,pkgconf_list_t * deplist,void * data,int depth)167 pkgconf_queue_collect_dependencies_walk(pkgconf_client_t *client,
168 pkgconf_list_t *deplist,
169 void *data,
170 int depth)
171 {
172 unsigned int eflags = PKGCONF_PKG_ERRF_OK;
173 pkgconf_node_t *node;
174 pkgconf_pkg_t *world = data;
175
176 PKGCONF_FOREACH_LIST_ENTRY_REVERSE(deplist->tail, node)
177 {
178 pkgconf_dependency_t *dep = node->data;
179 pkgconf_dependency_t *flattened_dep;
180 pkgconf_pkg_t *pkg = dep->match;
181
182 if (*dep->package == '\0')
183 continue;
184
185 if (pkg == NULL)
186 {
187 PKGCONF_TRACE(client, "WTF: unmatched dependency %p <%s>", dep, dep->package);
188 continue;
189 }
190
191 if (pkg->serial == client->serial)
192 continue;
193
194 if (client->flags & PKGCONF_PKG_PKGF_ITER_PKG_IS_PRIVATE)
195 pkg->flags |= PKGCONF_PKG_PROPF_VISITED_PRIVATE;
196 else
197 pkg->flags &= ~PKGCONF_PKG_PROPF_VISITED_PRIVATE;
198
199 eflags |= pkgconf_queue_collect_dependencies_main(client, pkg, data, depth - 1);
200
201 flattened_dep = pkgconf_dependency_copy(client, dep);
202 if (flattened_dep == NULL)
203 {
204 eflags |= PKGCONF_PKG_ERRF_DEPGRAPH_BREAK;
205 continue;
206 }
207
208 pkgconf_node_insert(&flattened_dep->iter, flattened_dep, &world->required);
209 }
210
211 return eflags;
212 }
213
214 static unsigned int
pkgconf_queue_collect_dependencies_main(pkgconf_client_t * client,pkgconf_pkg_t * root,void * data,int maxdepth)215 pkgconf_queue_collect_dependencies_main(pkgconf_client_t *client,
216 pkgconf_pkg_t *root,
217 void *data,
218 int maxdepth)
219 {
220 unsigned int eflags = PKGCONF_PKG_ERRF_OK;
221
222 if (maxdepth == 0)
223 return eflags;
224
225 /* Short-circuit if we have already visited this node.
226 */
227 if (root->serial == client->serial)
228 return eflags;
229
230 root->serial = client->serial;
231
232 if (!(client->flags & PKGCONF_PKG_PKGF_MERGE_PRIVATE_FRAGMENTS))
233 {
234 PKGCONF_TRACE(client, "%s: collecting shared dependencies, level %d", root->id, maxdepth);
235
236 eflags = pkgconf_queue_collect_dependencies_walk(client, &root->requires_shared, data, maxdepth);
237 if (eflags != PKGCONF_PKG_ERRF_OK)
238 return eflags;
239 }
240
241 PKGCONF_TRACE(client, "%s: collecting private dependencies, level %d", root->id, maxdepth);
242
243 /* XXX: ugly */
244 const unsigned int saved_flags = client->flags;
245 client->flags |= PKGCONF_PKG_PKGF_ITER_PKG_IS_PRIVATE;
246 eflags = pkgconf_queue_collect_dependencies_walk(client, &root->requires_private, data, maxdepth);
247 client->flags = saved_flags;
248 if (eflags != PKGCONF_PKG_ERRF_OK)
249 return eflags;
250
251 PKGCONF_TRACE(client, "%s: collecting public dependencies, level %d", root->id, maxdepth);
252
253 eflags = pkgconf_queue_collect_dependencies_walk(client, &root->required, data, maxdepth);
254 if (eflags != PKGCONF_PKG_ERRF_OK)
255 return eflags;
256
257 PKGCONF_TRACE(client, "%s: finished, %s", root->id, (root->flags & PKGCONF_PKG_PROPF_VISITED_PRIVATE) ? "private" : "public");
258
259 return eflags;
260 }
261
262 static inline unsigned int
pkgconf_queue_collect_dependencies(pkgconf_client_t * client,pkgconf_pkg_t * root,void * data,int maxdepth)263 pkgconf_queue_collect_dependencies(pkgconf_client_t *client,
264 pkgconf_pkg_t *root,
265 void *data,
266 int maxdepth)
267 {
268 ++client->serial;
269 return pkgconf_queue_collect_dependencies_main(client, root, data, maxdepth);
270 }
271
272 static inline unsigned int
pkgconf_queue_collect_conflicts(pkgconf_client_t * client,pkgconf_pkg_t * root,pkgconf_pkg_t * world,int maxdepth)273 pkgconf_queue_collect_conflicts(pkgconf_client_t *client,
274 pkgconf_pkg_t *root,
275 pkgconf_pkg_t *world,
276 int maxdepth)
277 {
278 unsigned int eflags = PKGCONF_PKG_ERRF_OK;
279 pkgconf_node_t *node;
280
281 PKGCONF_TRACE(client, "%s: collecting conflicts, level %d", root->id, maxdepth);
282
283 PKGCONF_FOREACH_LIST_ENTRY(root->required.head, node)
284 {
285 pkgconf_dependency_t *dep = node->data;
286 pkgconf_pkg_t *pkg = dep->match;
287 pkgconf_node_t *cnode;
288
289 if (*dep->package == '\0')
290 continue;
291
292 if (pkg == NULL)
293 {
294 PKGCONF_TRACE(client, "WTF: unmatched dependency %p <%s>", dep, dep->package);
295 continue;
296 }
297
298 PKGCONF_FOREACH_LIST_ENTRY(pkg->conflicts.head, cnode)
299 {
300 pkgconf_dependency_t *conflict = cnode->data;
301 pkgconf_dependency_t *flattened_conflict = pkgconf_dependency_copy(client, conflict);
302 if (flattened_conflict == NULL)
303 {
304 eflags |= PKGCONF_PKG_ERRF_DEPGRAPH_BREAK;
305 continue;
306 }
307
308 flattened_conflict->why = strdup(pkg->id);
309 pkgconf_node_insert(&flattened_conflict->iter, flattened_conflict, &world->conflicts);
310 }
311 }
312
313 return eflags;
314 }
315
316 static inline unsigned int
pkgconf_queue_verify(pkgconf_client_t * client,pkgconf_pkg_t * world,pkgconf_list_t * list,int maxdepth)317 pkgconf_queue_verify(pkgconf_client_t *client, pkgconf_pkg_t *world, pkgconf_list_t *list, int maxdepth)
318 {
319 unsigned int result;
320 const unsigned int saved_flags = client->flags;
321 pkgconf_pkg_t initial_world = {
322 .id = "user:request",
323 .realname = "virtual world package",
324 .flags = PKGCONF_PKG_PROPF_STATIC | PKGCONF_PKG_PROPF_VIRTUAL,
325 };
326
327 if (!pkgconf_queue_compile(client, &initial_world, list))
328 {
329 pkgconf_solution_free(client, &initial_world);
330 return PKGCONF_PKG_ERRF_DEPGRAPH_BREAK;
331 }
332
333 PKGCONF_TRACE(client, "solving");
334 result = pkgconf_pkg_traverse(client, &initial_world, NULL, NULL, maxdepth, 0);
335 if (result != PKGCONF_PKG_ERRF_OK)
336 {
337 pkgconf_solution_free(client, &initial_world);
338 return result;
339 }
340
341 PKGCONF_TRACE(client, "flattening");
342 result = pkgconf_queue_collect_dependencies(client, &initial_world, world, maxdepth);
343 if (result != PKGCONF_PKG_ERRF_OK)
344 {
345 pkgconf_solution_free(client, &initial_world);
346 return result;
347 }
348
349 result = pkgconf_queue_collect_conflicts(client, world, world, maxdepth);
350 if (result != PKGCONF_PKG_ERRF_OK)
351 {
352 pkgconf_solution_free(client, &initial_world);
353 return result;
354 }
355
356 if (client->flags & PKGCONF_PKG_PKGF_SEARCH_PRIVATE)
357 {
358 PKGCONF_TRACE(client, "marking public deps");
359 client->flags &= ~PKGCONF_PKG_PKGF_SEARCH_PRIVATE;
360 client->flags |= PKGCONF_PKG_PKGF_SKIP_CONFLICTS;
361 result = pkgconf_pkg_traverse(client, &initial_world, pkgconf_queue_mark_public, &world->required, maxdepth, 0);
362 client->flags = saved_flags;
363 if (result != PKGCONF_PKG_ERRF_OK)
364 {
365 pkgconf_solution_free(client, &initial_world);
366 return result;
367 }
368 }
369
370 if (!(client->flags & PKGCONF_PKG_PKGF_SKIP_CONFLICTS))
371 {
372 PKGCONF_TRACE(client, "checking for conflicts");
373
374 result = pkgconf_pkg_walk_conflicts_list(client, world, &world->conflicts);
375 if (result != PKGCONF_PKG_ERRF_OK)
376 {
377 pkgconf_solution_free(client, &initial_world);
378 return result;
379 }
380 }
381
382 /* free the initial solution */
383 pkgconf_solution_free(client, &initial_world);
384
385 return PKGCONF_PKG_ERRF_OK;
386 }
387
388 /*
389 * !doc
390 *
391 * .. c:function:: void pkgconf_solution_free(pkgconf_client_t *client, pkgconf_pkg_t *world, int maxdepth)
392 *
393 * Removes references to package nodes contained in a solution.
394 *
395 * :param pkgconf_client_t* client: The pkgconf client object to use for dependency resolution.
396 * :param pkgconf_pkg_t* world: The root for the generated dependency graph. Should have PKGCONF_PKG_PROPF_VIRTUAL flag.
397 * :returns: nothing
398 */
399 void
pkgconf_solution_free(pkgconf_client_t * client,pkgconf_pkg_t * world)400 pkgconf_solution_free(pkgconf_client_t *client, pkgconf_pkg_t *world)
401 {
402 (void) client;
403
404 if (world->flags & PKGCONF_PKG_PROPF_VIRTUAL)
405 {
406 pkgconf_dependency_free(&world->required);
407 pkgconf_dependency_free(&world->requires_private);
408 pkgconf_dependency_free(&world->conflicts);
409 }
410 }
411
412 /*
413 * !doc
414 *
415 * .. c:function:: bool pkgconf_queue_solve(pkgconf_client_t *client, pkgconf_list_t *list, pkgconf_pkg_t *world, int maxdepth)
416 *
417 * Solves and flattens the dependency graph for the supplied dependency list.
418 *
419 * :param pkgconf_client_t* client: The pkgconf client object to use for dependency resolution.
420 * :param pkgconf_list_t* list: The list of dependency requests to consider.
421 * :param pkgconf_pkg_t* world: The root for the generated dependency graph, provided by the caller. Should have PKGCONF_PKG_PROPF_VIRTUAL flag.
422 * :param int maxdepth: The maximum allowed depth for the dependency resolver. A depth of -1 means unlimited.
423 * :returns: true if the dependency resolver found a solution, otherwise false.
424 * :rtype: bool
425 */
426 bool
pkgconf_queue_solve(pkgconf_client_t * client,pkgconf_list_t * list,pkgconf_pkg_t * world,int maxdepth)427 pkgconf_queue_solve(pkgconf_client_t *client, pkgconf_list_t *list, pkgconf_pkg_t *world, int maxdepth)
428 {
429 /* if maxdepth is one, then we will not traverse deeper than our virtual package. */
430 if (!maxdepth)
431 maxdepth = -1;
432
433 unsigned int flags = client->flags;
434 client->flags |= PKGCONF_PKG_PKGF_SEARCH_PRIVATE;
435
436 unsigned int ret = pkgconf_queue_verify(client, world, list, maxdepth);
437 client->flags = flags;
438
439 return ret == PKGCONF_PKG_ERRF_OK;
440 }
441
442 /*
443 * !doc
444 *
445 * .. c:function:: void pkgconf_queue_apply(pkgconf_client_t *client, pkgconf_list_t *list, pkgconf_queue_apply_func_t func, int maxdepth, void *data)
446 *
447 * Attempt to compile a dependency resolution queue into a dependency resolution problem, then attempt to solve the problem and
448 * feed the solution to a callback function if a complete dependency graph is found.
449 *
450 * This function should not be used in new code. Use pkgconf_queue_solve instead.
451 *
452 * :param pkgconf_client_t* client: The pkgconf client object to use for dependency resolution.
453 * :param pkgconf_list_t* list: The list of dependency requests to consider.
454 * :param pkgconf_queue_apply_func_t func: The callback function to call if a solution is found by the dependency resolver.
455 * :param int maxdepth: The maximum allowed depth for the dependency resolver. A depth of -1 means unlimited.
456 * :param void* data: An opaque pointer which is passed to the callback function.
457 * :returns: true if the dependency resolver found a solution, otherwise false.
458 * :rtype: bool
459 */
460 bool
pkgconf_queue_apply(pkgconf_client_t * client,pkgconf_list_t * list,pkgconf_queue_apply_func_t func,int maxdepth,void * data)461 pkgconf_queue_apply(pkgconf_client_t *client, pkgconf_list_t *list, pkgconf_queue_apply_func_t func, int maxdepth, void *data)
462 {
463 bool ret = false;
464 pkgconf_pkg_t world = {
465 .id = "virtual:world",
466 .realname = "virtual world package",
467 .flags = PKGCONF_PKG_PROPF_STATIC | PKGCONF_PKG_PROPF_VIRTUAL,
468 };
469
470 /* if maxdepth is one, then we will not traverse deeper than our virtual package. */
471 if (!maxdepth)
472 maxdepth = -1;
473
474 if (!pkgconf_queue_solve(client, list, &world, maxdepth))
475 goto cleanup;
476
477 /* the world dependency set is flattened after it is returned from pkgconf_queue_verify */
478 if (!func(client, &world, data, maxdepth))
479 goto cleanup;
480
481 ret = true;
482
483 cleanup:
484 pkgconf_pkg_free(client, &world);
485 return ret;
486 }
487
488 /*
489 * !doc
490 *
491 * .. c:function:: void pkgconf_queue_validate(pkgconf_client_t *client, pkgconf_list_t *list, pkgconf_queue_apply_func_t func, int maxdepth, void *data)
492 *
493 * Attempt to compile a dependency resolution queue into a dependency resolution problem, then attempt to solve the problem.
494 *
495 * :param pkgconf_client_t* client: The pkgconf client object to use for dependency resolution.
496 * :param pkgconf_list_t* list: The list of dependency requests to consider.
497 * :param int maxdepth: The maximum allowed depth for the dependency resolver. A depth of -1 means unlimited.
498 * :returns: true if the dependency resolver found a solution, otherwise false.
499 * :rtype: bool
500 */
501 bool
pkgconf_queue_validate(pkgconf_client_t * client,pkgconf_list_t * list,int maxdepth)502 pkgconf_queue_validate(pkgconf_client_t *client, pkgconf_list_t *list, int maxdepth)
503 {
504 bool retval = true;
505 pkgconf_pkg_t world = {
506 .id = "virtual:world",
507 .realname = "virtual world package",
508 .flags = PKGCONF_PKG_PROPF_STATIC | PKGCONF_PKG_PROPF_VIRTUAL,
509 };
510
511 /* if maxdepth is one, then we will not traverse deeper than our virtual package. */
512 if (!maxdepth)
513 maxdepth = -1;
514
515 if (pkgconf_queue_verify(client, &world, list, maxdepth) != PKGCONF_PKG_ERRF_OK)
516 retval = false;
517
518 pkgconf_pkg_free(client, &world);
519
520 return retval;
521 }
522