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 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 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 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 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 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 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 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 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 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 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 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 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