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