Rewrite depsolver to use a series of passes over all packages.
The big change is that we follow one step of the depedency chain for
each package to resolve in each iteration, and repeat until there are
no more possible moves. In contrast the old depsolver would try to
follow the dependency chain completely for one package at a time.
This new approach is simpler and faster, and at the same time more
roboust. Instead of knowing how one newly installed package may
affect other packages (obsoleting, pulling in new packages etc), the
new algorithm just looks at the total list of requires, provides,
obsoletes and conflicts after installing new packages.
1.1 --- a/main.c Wed Jun 04 21:28:26 2008 -0400
1.2 +++ b/main.c Mon Jun 09 12:47:37 2008 -0400
1.3 @@ -77,6 +77,7 @@
1.4 list_properties(const char *package_name,
1.5 enum razor_property_type required_type)
1.6 {
1.7 + static const char *relation_string[] = { "<", "<=", "=", ">=", ">" };
1.8 struct razor_set *set;
1.9 struct razor_property *property;
1.10 struct razor_package *package;
1.11 @@ -101,7 +102,7 @@
1.12 printf("%s\n", name);
1.13 else
1.14 printf("%s %s %s\n", name,
1.15 - razor_version_relations[relation], version);
1.16 + relation_string[relation], version);
1.17 }
1.18 razor_property_iterator_destroy(pi);
1.19
1.20 @@ -361,20 +362,6 @@
1.21 }
1.22
1.23 static int
1.24 -command_validate(int argc, const char *argv[])
1.25 -{
1.26 - struct razor_set *set;
1.27 -
1.28 - set = razor_set_open(repo_filename);
1.29 - if (set == NULL)
1.30 - return 1;
1.31 - razor_set_list_unsatisfied(set);
1.32 - razor_set_destroy(set);
1.33 -
1.34 - return 0;
1.35 -}
1.36 -
1.37 -static int
1.38 mark_packages_for_update(struct razor_transaction *trans,
1.39 struct razor_set *set, const char *pattern)
1.40 {
1.41 @@ -387,7 +374,7 @@
1.42 while (razor_package_iterator_next(pi, &package,
1.43 &name, &version, &arch)) {
1.44 if (pattern && fnmatch(pattern, name, 0) == 0) {
1.45 - razor_transaction_install_package(trans, package);
1.46 + razor_transaction_update_package(trans, package);
1.47 matches++;
1.48 }
1.49 }
1.50 @@ -434,7 +421,7 @@
1.51 if (argc == 0)
1.52 razor_transaction_update_all(trans);
1.53 for (i = 0; i < argc; i++) {
1.54 - if (mark_packages_for_update(trans, upstream, argv[i]) == 0) {
1.55 + if (mark_packages_for_update(trans, set, argv[i]) == 0) {
1.56 fprintf(stderr, "no match for %s\n", argv[i]);
1.57 return 1;
1.58 }
1.59 @@ -828,7 +815,6 @@
1.60 { "import-yum", "import yum metadata files", command_import_yum },
1.61 { "import-rpmdb", "import the system rpm database", command_import_rpmdb },
1.62 { "import-rpms", "import rpms from the given directory", command_import_rpms },
1.63 - { "validate", "validate a package set", command_validate },
1.64 { "update", "update all or specified packages", command_update },
1.65 { "remove", "remove specified packages", command_remove },
1.66 { "diff", "show diff between two package sets", command_diff },
2.1 --- a/razor.c Wed Jun 04 21:28:26 2008 -0400
2.2 +++ b/razor.c Mon Jun 09 12:47:37 2008 -0400
2.3 @@ -839,6 +839,16 @@
2.4 return pi;
2.5 }
2.6
2.7 +static void
2.8 +razor_package_iterator_init_for_property(struct razor_package_iterator *pi,
2.9 + struct razor_set *set,
2.10 + struct razor_property *property)
2.11 +{
2.12 + memset(pi, 0, sizeof *pi);
2.13 + pi->set = set;
2.14 + pi->index = list_first(&property->packages, &set->package_pool);
2.15 +}
2.16 +
2.17 struct razor_package_iterator *
2.18 razor_package_iterator_create_for_property(struct razor_set *set,
2.19 struct razor_property *property)
2.20 @@ -1140,82 +1150,6 @@
2.21 list_package_files(set, r, set->files.data, end, buffer);
2.22 }
2.23
2.24 -static void
2.25 -razor_set_validate(struct razor_set *set, struct array *unsatisfied)
2.26 -{
2.27 - struct razor_property *r, *p, *end;
2.28 - uint32_t *u;
2.29 - char *pool;
2.30 -
2.31 - end = set->properties.data + set->properties.size;
2.32 - pool = set->string_pool.data;
2.33 -
2.34 - for (r = set->properties.data, p = r; r < end; r++) {
2.35 - if (r->type != RAZOR_PROPERTY_REQUIRES)
2.36 - continue;
2.37 -
2.38 - p = r;
2.39 - while (p < end && p->name == r->name &&
2.40 - p->type == r->type)
2.41 - p++;
2.42 -
2.43 - /* If there is more than one version of a provides,
2.44 - * seek to the end for the highest version. */
2.45 - /* FIXME: This doesn't work if we have a series of
2.46 - * requires a = 1, provides a = 1, requires a = 2,
2.47 - * provides a = 2, as the kernel and kernel-devel
2.48 - * does.*/
2.49 - while (p + 1 < end && p->name == (p + 1)->name &&
2.50 - p->type == (p + 1)->type)
2.51 - p++;
2.52 -
2.53 - /* FIXME: We need to track property flags (<, <=, =
2.54 - * etc) to properly determine if a requires is
2.55 - * satisfied. The current code doesn't track that the
2.56 - * requires a = 1 isn't satisfied by a = 2 provides. */
2.57 -
2.58 - if (p == end ||
2.59 - p->type != RAZOR_PROPERTY_PROVIDES ||
2.60 - r->name != p->name ||
2.61 - versioncmp(&pool[r->version], &pool[p->version]) > 0) {
2.62 - /* FIXME: We ignore file requires for now. */
2.63 - if (pool[r->name] == '/')
2.64 - continue;
2.65 - u = array_add(unsatisfied, sizeof *u);
2.66 - *u = r - (struct razor_property *) set->properties.data;
2.67 - }
2.68 - }
2.69 -}
2.70 -
2.71 -void
2.72 -razor_set_list_unsatisfied(struct razor_set *set)
2.73 -{
2.74 - struct array unsatisfied;
2.75 - struct razor_property *properties, *r;
2.76 - uint32_t *u, *end;
2.77 - char *pool;
2.78 -
2.79 - array_init(&unsatisfied);
2.80 - razor_set_validate(set, &unsatisfied);
2.81 -
2.82 - end = unsatisfied.data + unsatisfied.size;
2.83 - properties = set->properties.data;
2.84 - pool = set->string_pool.data;
2.85 -
2.86 - for (u = unsatisfied.data; u < end; u++) {
2.87 - r = properties + *u;
2.88 - if (pool[r->version] == '\0')
2.89 - printf("%s not satisfied\n",
2.90 - &pool[r->name]);
2.91 - else
2.92 - printf("%s-%s not satisfied\n",
2.93 - &pool[r->name],
2.94 - &pool[r->version]);
2.95 - }
2.96 -
2.97 - array_release(&unsatisfied);
2.98 -}
2.99 -
2.100 #define UPSTREAM_SOURCE 0x80
2.101
2.102 struct source {
2.103 @@ -1262,13 +1196,25 @@
2.104 }
2.105
2.106 static void
2.107 -add_package(struct razor_merger *merger,
2.108 - struct razor_package *package, struct source *source,
2.109 - uint32_t flags)
2.110 +razor_merger_add_package(struct razor_merger *merger,
2.111 + struct razor_package *package)
2.112 {
2.113 char *pool;
2.114 struct list *r;
2.115 struct razor_package *p;
2.116 + struct razor_set *set1;
2.117 + struct source *source;
2.118 + uint32_t flags;
2.119 +
2.120 + set1 = merger->source1.set;
2.121 + if (set1->packages.data <= (void *) package &&
2.122 + (void *) package < set1->packages.data + set1->packages.size) {
2.123 + source = &merger->source1;
2.124 + flags = 0;
2.125 + } else {
2.126 + source = &merger->source2;
2.127 + flags = UPSTREAM_SOURCE;
2.128 + }
2.129
2.130 pool = source->set->string_pool.data;
2.131 p = array_add(&merger->set->packages, sizeof *p);
2.132 @@ -1723,8 +1669,8 @@
2.133 razor_set_diff(struct razor_set *set, struct razor_set *upstream,
2.134 razor_package_callback_t callback, void *data)
2.135 {
2.136 - struct razor_package_iterator *pi1, *pi2;
2.137 - struct razor_package *p1, *p2;
2.138 + struct razor_package_iterator *pi1, *pi2;
2.139 + struct razor_package *p1, *p2;
2.140 const char *name1, *name2, *version1, *version2, *arch1, *arch2;
2.141 int res;
2.142
2.143 @@ -1760,232 +1706,19 @@
2.144 razor_package_iterator_destroy(pi2);
2.145 }
2.146
2.147 -struct razor_transaction;
2.148 -struct razor_transaction_package;
2.149 -struct razor_transaction_resolver;
2.150 -
2.151 -struct razor_transaction {
2.152 - int package_count, errors;
2.153 - struct razor_set *system, *upstream;
2.154 -
2.155 - struct bitarray syspkgs, uppkgs;
2.156 - struct array packages;
2.157 -};
2.158 -
2.159 -struct razor_transaction_package {
2.160 - const char *name, *old_version, *new_version;
2.161 - struct razor_package *old_package, *new_package;
2.162 - enum razor_transaction_package_state state;
2.163 -
2.164 - /* dep_package is the name of the package that resulted in
2.165 - * this entry being created (or NULL if the user requested the
2.166 - * install/remove), with the other dep_ fields providing
2.167 - * additional information.
2.168 - *
2.169 - * For INSTALL, if dep_type is REQUIRES, then dep_package
2.170 - * required something that this package provides. If dep_type
2.171 - * is CONFLICTS, then dep_package is a package that conflicted
2.172 - * with an older version of this package, forcing an upgrade.
2.173 - *
2.174 - * For REMOVE, if dep_type is REQUIRES, then dep_package is a
2.175 - * package that is being removed. If dep_type is OBSOLETES,
2.176 - * then dep_package is a package that obsoletes this one.
2.177 - *
2.178 - * For OLD_CONFLICT or NEW_CONFLICT, dep_package is an
2.179 - * existing package that conflicts with this one. The
2.180 - * conflicting property comes from the already-installed
2.181 - * package for OLD_CONFLICT, or the to-be-installed package
2.182 - * for NEW_CONFLICT.
2.183 - *
2.184 - * For UNSATISFIABLE, the dep_ fields are as for an INSTALL,
2.185 - * but the name field will be NULL.
2.186 - */
2.187 - const char *dep_package;
2.188 - enum razor_property_type dep_type;
2.189 - const char *dep_property;
2.190 - enum razor_version_relation dep_relation;
2.191 - const char *dep_version;
2.192 -};
2.193 -
2.194 -static int
2.195 -package_in_set(void *package, struct razor_set *set)
2.196 -{
2.197 - return package >= set->packages.data &&
2.198 - package < set->packages.data + set->packages.size;
2.199 -}
2.200 -
2.201 -static int
2.202 -property_in_set(void *property, struct razor_set *set)
2.203 -{
2.204 - return property >= set->properties.data &&
2.205 - property < set->properties.data + set->properties.size;
2.206 -}
2.207 -
2.208 -static struct razor_package *
2.209 -property_provider_package(struct razor_transaction *trans,
2.210 - struct razor_property *prop,
2.211 - int installed)
2.212 -{
2.213 - struct razor_set *set;
2.214 - struct bitarray *pkgbits;
2.215 - struct razor_package *pkgs;
2.216 - struct list *p;
2.217 -
2.218 - if (installed && prop->type != RAZOR_PROPERTY_PROVIDES)
2.219 - return NULL;
2.220 - else if (!installed &&
2.221 - prop->type != RAZOR_PROPERTY_PROVIDES &&
2.222 - prop->type != RAZOR_PROPERTY_OBSOLETES)
2.223 - return NULL;
2.224 -
2.225 - if (property_in_set(prop, trans->system)) {
2.226 - set = trans->system;
2.227 - pkgbits = &trans->syspkgs;
2.228 - } else {
2.229 - set = trans->upstream;
2.230 - pkgbits = &trans->uppkgs;
2.231 - }
2.232 - pkgs = set->packages.data;
2.233 -
2.234 - for (p = list_first(&prop->packages, &set->package_pool); p; p = list_next(p)) {
2.235 - if (bitarray_get(pkgbits, p->data) != installed)
2.236 - continue;
2.237 - if (prop->type == RAZOR_PROPERTY_OBSOLETES ||
2.238 - pkgs[p->data].name == prop->name)
2.239 - return &pkgs[p->data];
2.240 - }
2.241 - return NULL;
2.242 -}
2.243 -
2.244 -static int
2.245 -compare_transaction_packages(const void *one, const void *two)
2.246 -{
2.247 - struct razor_transaction_package **tp1 = (void *)one;
2.248 - struct razor_transaction_package **tp2 = (void *)two;
2.249 -
2.250 - if (!(*tp1)->name)
2.251 - return 1;
2.252 - else if (!(*tp2)->name)
2.253 - return -1;
2.254 - else
2.255 - return strcmp((*tp1)->name, (*tp2)->name);
2.256 -}
2.257 -
2.258 -/* FIXME: merge this into the other property loop in razor_transaction_satisfy */
2.259 -static void
2.260 -resolve_new_packages(struct razor_transaction *trans,
2.261 - int start, int end)
2.262 -{
2.263 - struct razor_property *sp, *up, *sp_end, *up_end;
2.264 - struct razor_package *spkg, *spkgs, *upkg, *upkgs;
2.265 - struct razor_transaction_package **packages;
2.266 - const char *spool, *upool;
2.267 - int i;
2.268 -
2.269 - sp_end = trans->system->properties.data + trans->system->properties.size;
2.270 - spool = trans->system->string_pool.data;
2.271 - spkgs = trans->system->packages.data;
2.272 - up_end = trans->upstream->properties.data + trans->upstream->properties.size;
2.273 - upool = trans->upstream->string_pool.data;
2.274 - upkgs = trans->upstream->packages.data;
2.275 -
2.276 - /* FIXME, check if sorting the packages directly (rather than
2.277 - * sorting pointers-to-packages) still results in confusing
2.278 - * descriptions.
2.279 - */
2.280 - packages = calloc(end - start, sizeof *packages);
2.281 - for (i = start; i < end; i++)
2.282 - packages[i - start] = ((struct razor_transaction_package *)trans->packages.data) + i;
2.283 - qsort(packages, end - start, sizeof *packages,
2.284 - compare_transaction_packages);
2.285 -
2.286 - sp = trans->system->properties.data;
2.287 - up = trans->upstream->properties.data;
2.288 - for (i = 0; i < end - start; i++) {
2.289 - if (!packages[i]->name ||
2.290 - packages[i]->state >= RAZOR_PACKAGE_FIRST_ERROR_STATE)
2.291 - continue;
2.292 -
2.293 - spkg = NULL;
2.294 - while (sp < sp_end &&
2.295 - strcmp(&spool[sp->name], packages[i]->name) < 0)
2.296 - sp++;
2.297 - while (sp < sp_end &&
2.298 - strcmp(&spool[sp->name], packages[i]->name) == 0 &&
2.299 - !(spkg = property_provider_package(trans, sp, 1)))
2.300 - sp++;
2.301 -
2.302 - upkg = NULL;
2.303 - while (up < up_end &&
2.304 - strcmp(&upool[up->name], packages[i]->name) < 0)
2.305 - up++;
2.306 - while (up < up_end &&
2.307 - strcmp(&upool[up->name], packages[i]->name) == 0 &&
2.308 - !(upkg = property_provider_package(trans, up, 0)))
2.309 - up++;
2.310 -
2.311 - if (packages[i]->state == RAZOR_PACKAGE_REMOVE ||
2.312 - packages[i]->state == RAZOR_PACKAGE_OBSOLETED) {
2.313 - if (spkg) {
2.314 - packages[i]->old_package = spkg;
2.315 - packages[i]->name = &spool[spkg->name];
2.316 - packages[i]->old_version = &spool[spkg->version];
2.317 - bitarray_set(&trans->syspkgs, spkg - spkgs, 0);
2.318 - }
2.319 - if (!packages[i]->old_package) {
2.320 - packages[i]->name = strdup(packages[i]->name);
2.321 - packages[i]->state |= RAZOR_PACKAGE_UNAVAILABLE_FLAG;
2.322 - trans->errors++;
2.323 - }
2.324 - } else {
2.325 - if (upkg) {
2.326 - packages[i]->new_package = upkg;
2.327 - packages[i]->name = &upool[upkg->name];
2.328 - packages[i]->new_version = &upool[upkg->version];
2.329 -
2.330 - if (up->name != upkg->name) {
2.331 - packages[i]->dep_package = &upool[upkg->name];
2.332 - packages[i]->dep_type = up->type;
2.333 - packages[i]->dep_property = &upool[up->name];
2.334 - packages[i]->dep_relation = up->relation;
2.335 - packages[i]->dep_version = &upool[up->version];
2.336 - }
2.337 -
2.338 - if (spkg) {
2.339 - packages[i]->old_package = spkg;
2.340 - packages[i]->old_version = &spool[spkg->version];
2.341 - if (versioncmp(&spool[spkg->version], &upool[up->version]) >= 0) {
2.342 - packages[i]->state = RAZOR_PACKAGE_UP_TO_DATE;
2.343 - trans->errors++;
2.344 - continue;
2.345 - }
2.346 - bitarray_set(&trans->syspkgs, spkg - spkgs, 0);
2.347 - }
2.348 - bitarray_set(&trans->uppkgs, upkg - upkgs, 1);
2.349 - }
2.350 - if (!packages[i]->new_package) {
2.351 - packages[i]->name = strdup(packages[i]->name);
2.352 - packages[i]->state |= RAZOR_PACKAGE_UNAVAILABLE_FLAG;
2.353 - trans->errors++;
2.354 - }
2.355 - }
2.356 - }
2.357 -}
2.358 -
2.359 static int
2.360 provider_satisfies_requirement(struct razor_property *provider,
2.361 const char *provider_strings,
2.362 - struct razor_property *requirement,
2.363 - const char *requirement_strings)
2.364 + enum razor_version_relation relation,
2.365 + const char *required)
2.366 {
2.367 int cmp, len;
2.368 const char *provided = &provider_strings[provider->version];
2.369 - const char *required = &requirement_strings[requirement->version];
2.370
2.371 if (!*required)
2.372 return 1;
2.373 if (!*provided) {
2.374 - if (requirement->relation >= RAZOR_VERSION_EQUAL)
2.375 + if (relation >= RAZOR_VERSION_EQUAL)
2.376 return 1;
2.377 else
2.378 return 0;
2.379 @@ -1993,7 +1726,7 @@
2.380
2.381 cmp = versioncmp(provided, required);
2.382
2.383 - switch (requirement->relation) {
2.384 + switch (relation) {
2.385 case RAZOR_VERSION_LESS:
2.386 return cmp < 0;
2.387
2.388 @@ -2023,614 +1756,82 @@
2.389 return 0;
2.390 }
2.391
2.392 -static struct razor_package *
2.393 -find_package_for_file(struct razor_set *set, struct bitarray *pkgbits,
2.394 - const char *filename, int installed)
2.395 +#define TRANS_PACKAGE_PRESENT 1
2.396 +#define TRANS_PACKAGE_UPDATE 2
2.397 +#define TRANS_PROPERTY_SATISFIED 0x80000000
2.398 +
2.399 +struct transaction_set {
2.400 + struct razor_set *set;
2.401 + uint32_t *packages;
2.402 + uint32_t *properties;
2.403 +};
2.404 +
2.405 +struct razor_transaction {
2.406 + int package_count, errors;
2.407 + struct transaction_set system, upstream;
2.408 + int changes;
2.409 +};
2.410 +
2.411 +static void
2.412 +transaction_set_init(struct transaction_set *ts, struct razor_set *set)
2.413 {
2.414 - struct razor_package *pkgs = set->packages.data;
2.415 - struct razor_entry *entry;
2.416 - struct list *p;
2.417 + int count;
2.418
2.419 - if (filename[0] != '/')
2.420 - return 0;
2.421 -
2.422 - entry = find_entry(set, set->files.data, filename);
2.423 - if (!entry)
2.424 - return 0;
2.425 -
2.426 - for (p = list_first(&entry->packages, &set->package_pool); p; p = list_next(p)) {
2.427 - if (bitarray_get(pkgbits, p->data) == installed)
2.428 - return &pkgs[p->data];
2.429 - }
2.430 - return NULL;
2.431 -}
2.432 -
2.433 -static struct razor_package *
2.434 -find_installed_package_for_file(struct razor_transaction *trans,
2.435 - const char *filename)
2.436 -{
2.437 - struct razor_package *pkg;
2.438 -
2.439 - pkg = find_package_for_file(trans->system, &trans->syspkgs,
2.440 - filename, 1);
2.441 - if (!pkg)
2.442 - pkg = find_package_for_file(trans->upstream, &trans->uppkgs,
2.443 - filename, 1);
2.444 - return pkg;
2.445 -}
2.446 -
2.447 -static struct razor_package *
2.448 -find_uninstalled_package_for_file(struct razor_transaction *trans,
2.449 - const char *filename)
2.450 -{
2.451 - struct razor_package *pkg;
2.452 -
2.453 - pkg = find_package_for_file(trans->upstream, &trans->uppkgs,
2.454 - filename, 0);
2.455 - if (!pkg)
2.456 - pkg = find_package_for_file(trans->system, &trans->syspkgs,
2.457 - filename, 0);
2.458 - return pkg;
2.459 -}
2.460 -
2.461 -static struct razor_property *
2.462 -skip_to_matching_property(struct razor_transaction *trans,
2.463 - struct razor_property *match,
2.464 - struct razor_property *prop)
2.465 -{
2.466 - struct razor_set *mset, *pset;
2.467 - const char *ppool, *mpool;
2.468 - struct razor_property *prop_end;
2.469 -
2.470 - if (property_in_set(match, trans->system))
2.471 - mset = trans->system;
2.472 - else
2.473 - mset = trans->upstream;
2.474 -
2.475 - if (property_in_set(prop, trans->system))
2.476 - pset = trans->system;
2.477 - else if (property_in_set(prop, trans->upstream))
2.478 - pset = trans->upstream;
2.479 - else
2.480 - return prop;
2.481 -
2.482 - prop_end = pset->properties.data + pset->properties.size;
2.483 - ppool = pset->string_pool.data;
2.484 - mpool = mset->string_pool.data;
2.485 -
2.486 - while (prop < prop_end &&
2.487 - strcmp(&ppool[prop->name], &mpool[match->name]) < 0)
2.488 - prop++;
2.489 - return prop;
2.490 -}
2.491 -
2.492 -static struct razor_package *
2.493 -find_package_matching(struct razor_transaction *trans, int installed,
2.494 - struct razor_property *prop,
2.495 - struct razor_property *req,
2.496 - struct razor_set *req_set)
2.497 -{
2.498 - struct razor_set *set;
2.499 - struct bitarray *pkgbits;
2.500 - struct razor_package *pkgs;
2.501 - struct razor_property *props, *prop_end;
2.502 - enum razor_property_type match_type;
2.503 - const char *pool;
2.504 - const char *rpool;
2.505 - int match_name = (req->type == RAZOR_PROPERTY_OBSOLETES);
2.506 - int match;
2.507 -
2.508 - if (property_in_set(prop, trans->system)) {
2.509 - set = trans->system;
2.510 - pkgbits = &trans->syspkgs;
2.511 - } else if (property_in_set(prop, trans->upstream)) {
2.512 - set = trans->upstream;
2.513 - pkgbits = &trans->uppkgs;
2.514 - } else
2.515 - return NULL;
2.516 -
2.517 - if (!req_set) {
2.518 - if (property_in_set(req, trans->system))
2.519 - req_set = trans->system;
2.520 - else
2.521 - req_set = trans->upstream;
2.522 - }
2.523 - rpool = req_set->string_pool.data;
2.524 -
2.525 - if (req->type == RAZOR_PROPERTY_PROVIDES)
2.526 - match_type = RAZOR_PROPERTY_CONFLICTS;
2.527 - else
2.528 - match_type = RAZOR_PROPERTY_PROVIDES;
2.529 -
2.530 - pkgs = set->packages.data;
2.531 - props = set->properties.data;
2.532 - prop_end = set->properties.data + set->properties.size;
2.533 - pool = set->string_pool.data;
2.534 -
2.535 - /* Find first matching property */
2.536 - while (prop < prop_end &&
2.537 - strcmp(&pool[prop->name], &rpool[req->name]) < 0)
2.538 - prop++;
2.539 - if (prop == prop_end ||
2.540 - strcmp(&pool[prop->name], &rpool[req->name]) > 0)
2.541 - return NULL;
2.542 -
2.543 - if (prop->type < match_type) {
2.544 - while (prop < prop_end && prop->type != match_type)
2.545 - prop++;
2.546 - } else {
2.547 - while (prop >= props && prop->type != match_type)
2.548 - prop--;
2.549 - while (prop > props + 1 && (prop - 1)->name == prop->name &&
2.550 - (prop - 1)->type == match_type)
2.551 - prop--;
2.552 - }
2.553 -
2.554 - /* Scan matching properties */
2.555 - while (prop < prop_end && prop->type == match_type &&
2.556 - strcmp(&pool[prop->name], &rpool[req->name]) == 0) {
2.557 - if (match_type == RAZOR_PROPERTY_PROVIDES)
2.558 - match = provider_satisfies_requirement(prop, pool, req, rpool);
2.559 - else
2.560 - match = provider_satisfies_requirement(req, rpool, prop, pool);
2.561 - if (match) {
2.562 - struct list *pkg;
2.563 -
2.564 - for (pkg = list_first(&prop->packages, &set->package_pool); pkg; pkg = list_next(pkg)) {
2.565 - if (bitarray_get(pkgbits, pkg->data) != installed)
2.566 - continue;
2.567 - if (!match_name ||
2.568 - strcmp(&pool[pkgs[pkg->data].name],
2.569 - &rpool[req->name]) == 0)
2.570 - return &pkgs[pkg->data];
2.571 - }
2.572 - }
2.573 - prop++;
2.574 - }
2.575 -
2.576 - return NULL;
2.577 -}
2.578 -
2.579 -static struct razor_package *
2.580 -find_installed_package_for_property(struct razor_transaction *trans,
2.581 - struct razor_property *sys_start,
2.582 - struct razor_property *up_start,
2.583 - struct razor_property *req)
2.584 -{
2.585 - struct razor_package *pkg;
2.586 -
2.587 - pkg = find_package_matching(trans, 1, sys_start, req, NULL);
2.588 - if (!pkg)
2.589 - pkg = find_package_matching(trans, 1, up_start, req, NULL);
2.590 - return pkg;
2.591 -}
2.592 -
2.593 -static struct razor_package *
2.594 -find_uninstalled_package_for_property(struct razor_transaction *trans,
2.595 - struct razor_property *sys_start,
2.596 - struct razor_property *up_start,
2.597 - struct razor_property *req)
2.598 -{
2.599 - struct razor_package *pkg;
2.600 -
2.601 - pkg = find_package_matching(trans, 0, up_start, req, NULL);
2.602 - if (!pkg)
2.603 - pkg = find_package_matching(trans, 0, sys_start, req, NULL);
2.604 - return pkg;
2.605 -}
2.606 -
2.607 -static struct razor_transaction_package *
2.608 -find_transaction_package(struct razor_transaction *trans, const char *name)
2.609 -{
2.610 - struct razor_transaction_package *packages;
2.611 - int count, i;
2.612 -
2.613 - packages = trans->packages.data;
2.614 - count = trans->packages.size / sizeof *packages;
2.615 - for (i = 0; i < count; i++) {
2.616 - if (packages[i].name && !strcmp(packages[i].name, name))
2.617 - return &packages[i];
2.618 - }
2.619 - return NULL;
2.620 -}
2.621 -
2.622 -/* FIXME? */
2.623 -static int
2.624 -prop_is_being_installed(struct razor_transaction *trans,
2.625 - struct razor_property *prop)
2.626 -{
2.627 - struct list *pkg;
2.628 -
2.629 - for (pkg = list_first(&prop->packages, &trans->upstream->package_pool); pkg; pkg = list_next(pkg)) {
2.630 - if (bitarray_get(&trans->uppkgs, pkg->data))
2.631 - return 1;
2.632 - }
2.633 - return 0;
2.634 -}
2.635 -
2.636 -static int
2.637 -prop_is_being_removed(struct razor_transaction *trans,
2.638 - struct razor_property *prop)
2.639 -{
2.640 - struct list *pkg;
2.641 -
2.642 - for (pkg = list_first(&prop->packages, &trans->system->package_pool); pkg; pkg = list_next(pkg)) {
2.643 - if (bitarray_get(&trans->syspkgs, pkg->data))
2.644 - return 0;
2.645 - }
2.646 - return 1;
2.647 -}
2.648 -
2.649 -static int
2.650 -prop_is_being_updated(struct razor_transaction *trans,
2.651 - struct razor_property *prop)
2.652 -{
2.653 - struct razor_package *packages = trans->system->packages.data;
2.654 - const char *pool = trans->system->string_pool.data;
2.655 - struct razor_transaction_package *tp;
2.656 - struct list *pkg;
2.657 -
2.658 - /* Assumes prop_is_being_removed returns true */
2.659 -
2.660 - for (pkg = list_first(&prop->packages, &trans->system->package_pool); pkg; pkg = list_next(pkg)) {
2.661 - tp = find_transaction_package(trans, &pool[packages[pkg->data].name]);
2.662 - if (tp && tp->state == RAZOR_PACKAGE_REMOVE)
2.663 - return 0;
2.664 - }
2.665 - return 1;
2.666 + ts->set = set;
2.667 + count = set->packages.size / sizeof (struct razor_package);
2.668 + ts->packages = zalloc(count * sizeof *ts->packages);
2.669 + count = set->properties.size / sizeof (struct razor_property);
2.670 + ts->properties = zalloc(count * sizeof *ts->properties);
2.671 }
2.672
2.673 static void
2.674 -add_transaction_package(struct razor_transaction *trans,
2.675 - struct razor_package *new_package,
2.676 - struct razor_package *old_package,
2.677 - enum razor_transaction_package_state state,
2.678 - const char *req_package,
2.679 - struct razor_property *req_prop)
2.680 +transaction_set_release(struct transaction_set *ts)
2.681 {
2.682 - struct razor_set *new_package_set, *old_package_set, *req_set;
2.683 - struct bitarray *reqpkgbits;
2.684 - struct razor_transaction_package *tp, *already;
2.685 - const char *pool;
2.686 - struct razor_package *pkgs;
2.687 - struct list *pkg;
2.688 - int contradiction = 0;
2.689 -
2.690 - if (package_in_set(new_package, trans->system))
2.691 - new_package_set = trans->system;
2.692 - else
2.693 - new_package_set = trans->upstream;
2.694 - if (package_in_set(old_package, trans->system))
2.695 - old_package_set = trans->system;
2.696 - else
2.697 - old_package_set = trans->upstream;
2.698 - if (property_in_set(req_prop, trans->system)) {
2.699 - req_set = trans->system;
2.700 - reqpkgbits = &trans->syspkgs;
2.701 - } else {
2.702 - req_set = trans->upstream;
2.703 - reqpkgbits = &trans->uppkgs;
2.704 - }
2.705 -
2.706 - if (new_package) {
2.707 - pool = new_package_set->string_pool.data;
2.708 - already = find_transaction_package(trans, &pool[new_package->name]);
2.709 - if (already) {
2.710 - if (already->new_package == new_package) {
2.711 - /* Already taken care of */
2.712 - return;
2.713 - } else if (new_package_set == trans->upstream &&
2.714 - already->state == RAZOR_PACKAGE_FORCED_UPDATE) {
2.715 - already->new_package = new_package;
2.716 - return;
2.717 - } else if (new_package_set == trans->upstream) {
2.718 - return;
2.719 - }
2.720 -
2.721 - /* Oops. We lose */
2.722 - if (state != RAZOR_PACKAGE_CONTRADICTION)
2.723 - contradiction = 1;
2.724 - }
2.725 - } else if (old_package) {
2.726 - pool = old_package_set->string_pool.data;
2.727 - already = find_transaction_package(trans, &pool[old_package->name]);
2.728 - if (already) {
2.729 - if (already->old_package == old_package) {
2.730 - /* Already taken care of */
2.731 - return;
2.732 - } else if (old_package_set == trans->system) {
2.733 - already->old_package = old_package;
2.734 - return;
2.735 - }
2.736 -
2.737 - /* Oops. We lose */
2.738 - if (state != RAZOR_PACKAGE_CONTRADICTION)
2.739 - contradiction = 1;
2.740 - }
2.741 - } else
2.742 - state = RAZOR_PACKAGE_UNSATISFIABLE;
2.743 -
2.744 - tp = array_add(&trans->packages, sizeof *tp);
2.745 - memset(tp, 0, sizeof *tp);
2.746 -
2.747 - if (new_package) {
2.748 - pool = new_package_set->string_pool.data;
2.749 - tp->new_package = new_package;
2.750 - tp->name = &pool[new_package->name];
2.751 - tp->new_version = &pool[new_package->version];
2.752 -
2.753 - pkgs = new_package_set->packages.data;
2.754 - }
2.755 - if (old_package) {
2.756 - pool = old_package_set->string_pool.data;
2.757 - tp->old_package = old_package;
2.758 - tp->name = &pool[old_package->name];
2.759 - tp->old_version = &pool[old_package->version];
2.760 -
2.761 - pkgs = old_package_set->packages.data;
2.762 - }
2.763 -
2.764 - tp->state = state;
2.765 - if (state != RAZOR_PACKAGE_INSTALL &&
2.766 - state != RAZOR_PACKAGE_FORCED_UPDATE &&
2.767 - state != RAZOR_PACKAGE_REMOVE &&
2.768 - state != RAZOR_PACKAGE_OBSOLETED)
2.769 - trans->errors++;
2.770 -
2.771 - if (contradiction) {
2.772 - /* Do this now, after adding tp, so that it ends up
2.773 - * after both the INSTALL and the REMOVE in the array.
2.774 - */
2.775 - add_transaction_package(trans, new_package, old_package,
2.776 - RAZOR_PACKAGE_CONTRADICTION,
2.777 - NULL, NULL);
2.778 - }
2.779 -
2.780 - if (req_package)
2.781 - tp->dep_package = req_package;
2.782 - if (!req_prop)
2.783 - return;
2.784 -
2.785 - pool = req_set->string_pool.data;
2.786 - pkgs = req_set->packages.data;
2.787 - if (!req_package) {
2.788 - for (pkg = list_first(&req_prop->packages, &req_set->package_pool); pkg; pkg = list_next(pkg)) {
2.789 - if (bitarray_get(reqpkgbits, pkg->data))
2.790 - break;
2.791 - }
2.792 - if (pkg)
2.793 - tp->dep_package = &pool[pkgs[pkg->data].name];
2.794 - }
2.795 -
2.796 - tp->dep_type = req_prop->type;
2.797 - tp->dep_property = &pool[req_prop->name];
2.798 - tp->dep_relation = req_prop->relation;
2.799 - tp->dep_version = &pool[req_prop->version];
2.800 + free(ts->packages);
2.801 + free(ts->properties);
2.802 }
2.803
2.804 static void
2.805 -razor_transaction_satisfy(struct razor_transaction *trans)
2.806 +transaction_set_install_package(struct transaction_set *ts,
2.807 + struct razor_package *package)
2.808 {
2.809 - struct razor_package *spkgs, *upkgs, *pkg;
2.810 - struct razor_property *sp, *sprops, *sprop_end;
2.811 - struct razor_property *up, *uprops, *uprop_end;
2.812 - struct razor_property *sr, *ur, *first_up;
2.813 - const char *spool, *upool, *removed_package;
2.814 - struct list *reqpkg;
2.815 + struct razor_package *pkgs;
2.816 + struct list *prop;
2.817 + int i;
2.818
2.819 - spkgs = trans->system->packages.data;
2.820 - sprops = trans->system->properties.data;
2.821 - sprop_end = trans->system->properties.data + trans->system->properties.size;
2.822 - spool = trans->system->string_pool.data;
2.823 - upkgs = trans->upstream->packages.data;
2.824 - uprops = trans->upstream->properties.data;
2.825 - uprop_end = trans->upstream->properties.data + trans->upstream->properties.size;
2.826 - upool = trans->upstream->string_pool.data;
2.827 + pkgs = ts->set->packages.data;
2.828 + i = package - pkgs;
2.829 + if (ts->packages[i] == TRANS_PACKAGE_PRESENT)
2.830 + return;
2.831
2.832 - sp = sprops;
2.833 - for (up = uprops; up < uprop_end; up++) {
2.834 - /* Skip 'up' ahead to a property of a package which is
2.835 - * to-be-installed.
2.836 - */
2.837 - while (up < uprop_end &&
2.838 - !prop_is_being_installed(trans, up))
2.839 - up++;
2.840 - if (up == uprop_end)
2.841 - break;
2.842 - sp = skip_to_matching_property(trans, up, sp);
2.843 + ts->packages[i] = TRANS_PACKAGE_PRESENT;
2.844
2.845 - switch (up->type) {
2.846 - case RAZOR_PROPERTY_REQUIRES:
2.847 - if (!strncmp(&upool[up->name], "rpmlib(", 7))
2.848 - break;
2.849 -
2.850 - if (find_installed_package_for_property(trans, sp, up, up) ||
2.851 - find_installed_package_for_file(trans, &upool[up->name])) {
2.852 - /* Requires something that is either installed
2.853 - * or to-be-installed.
2.854 - */
2.855 - break;
2.856 - }
2.857 -
2.858 - /* See if we can install a new upstream provider */
2.859 - pkg = find_uninstalled_package_for_property(trans, sp, up, up);
2.860 - if (!pkg)
2.861 - pkg = find_uninstalled_package_for_file(trans, &upool[up->name]);
2.862 - add_transaction_package(trans, pkg, NULL,
2.863 - RAZOR_PACKAGE_INSTALL,
2.864 - NULL, up);
2.865 - break;
2.866 -
2.867 - case RAZOR_PROPERTY_PROVIDES:
2.868 - /* find_installed_package_for_property works backwards
2.869 - * here, finding a *conflicting* installed package.
2.870 - */
2.871 - pkg = find_installed_package_for_property(trans, sp, up, up);
2.872 - if (!pkg)
2.873 - break;
2.874 -
2.875 - if (package_in_set(pkg, trans->system)) {
2.876 - /* pkg CONFLICTS with what 'up' PROVIDES. Try
2.877 - * finding an upgrade
2.878 - */
2.879 - add_transaction_package(trans, NULL, pkg,
2.880 - RAZOR_PACKAGE_FORCED_UPDATE,
2.881 - &upool[up->name], sp);
2.882 - } else {
2.883 - add_transaction_package(trans, NULL, pkg,
2.884 - RAZOR_PACKAGE_CONTRADICTION,
2.885 - NULL, up);
2.886 - }
2.887 - break;
2.888 -
2.889 - case RAZOR_PROPERTY_CONFLICTS:
2.890 - pkg = find_installed_package_for_property(trans, sp, up, up);
2.891 - if (!pkg)
2.892 - break;
2.893 -
2.894 - if (package_in_set(pkg, trans->system)) {
2.895 - /* Conflicts with something already installed.
2.896 - * Try to upgrade out.
2.897 - */
2.898 - add_transaction_package(trans, NULL, pkg,
2.899 - RAZOR_PACKAGE_FORCED_UPDATE,
2.900 - NULL, up);
2.901 - } else {
2.902 - add_transaction_package(trans, pkg, NULL,
2.903 - RAZOR_PACKAGE_CONTRADICTION,
2.904 - NULL, up);
2.905 - }
2.906 - break;
2.907 -
2.908 - case RAZOR_PROPERTY_OBSOLETES:
2.909 - pkg = find_installed_package_for_property(trans, sp, up, up);
2.910 - if (pkg) {
2.911 - /* If pkg is to-be-installed, this
2.912 - * will add a CONTRADICTION error as well.
2.913 - */
2.914 - add_transaction_package(trans, NULL, pkg,
2.915 - RAZOR_PACKAGE_OBSOLETED,
2.916 - NULL, up);
2.917 - }
2.918 - break;
2.919 -
2.920 - default:
2.921 - /* can't happen */
2.922 - break;
2.923 - }
2.924 - }
2.925 -
2.926 - up = uprops;
2.927 - for (sp = sprops; sp < sprop_end; sp++) {
2.928 - /* Skip 'sp' ahead to a PROVIDES of a package which is
2.929 - * to-be-removed.
2.930 - */
2.931 - while (sp < sprop_end &&
2.932 - (sp->type != RAZOR_PROPERTY_PROVIDES ||
2.933 - !prop_is_being_removed(trans, sp)))
2.934 - sp++;
2.935 - if (sp == sprop_end)
2.936 - break;
2.937 -
2.938 - removed_package = &spool[spkgs[list_first(&sp->packages, &trans->system->package_pool)->data].name];
2.939 -
2.940 - /* Skip 'up' to match */
2.941 - up = skip_to_matching_property(trans, sp, up);
2.942 - ur = first_up = up;
2.943 -
2.944 - /* If the package is just being upgraded, we may
2.945 - * already be installing an identical PROVIDES, so
2.946 - * check for that.
2.947 - */
2.948 - while (up < uprop_end &&
2.949 - strcmp(&spool[sp->name], &upool[up->name]) == 0 &&
2.950 - (up->type != RAZOR_PROPERTY_PROVIDES ||
2.951 - sp->relation != up->relation ||
2.952 - strcmp(&spool[sp->name], &upool[up->name]) != 0))
2.953 - up++;
2.954 - if (up < uprop_end &&
2.955 - up->type == RAZOR_PROPERTY_PROVIDES &&
2.956 - strcmp(&spool[sp->name], &upool[up->name]) == 0 &&
2.957 - sp->relation == up->relation &&
2.958 - strcmp(&spool[sp->version], &upool[up->version]) == 0 &&
2.959 - prop_is_being_installed(trans, up)) {
2.960 - up = first_up;
2.961 - continue;
2.962 - }
2.963 - up = first_up;
2.964 -
2.965 - /* For all still-installed packages that require
2.966 - * sp->name, see if they are satisfied by any other
2.967 - * still-installed or to-be-installed property. If
2.968 - * not, either remove or attempt to update the
2.969 - * package, depending on why the required property has
2.970 - * disappeared
2.971 - */
2.972 - sr = sp;
2.973 - while (sr > sprops + 1 && (sr - 1)->name == sr->name)
2.974 - sr--;
2.975 - for (; sr->type == RAZOR_PROPERTY_REQUIRES; sr++) {
2.976 - if (prop_is_being_removed(trans, sr))
2.977 - continue;
2.978 - if (find_installed_package_for_property(trans, sp, up, sr))
2.979 - continue;
2.980 -
2.981 - for (reqpkg = list_first(&sr->packages, &trans->system->package_pool); reqpkg; reqpkg = list_next(reqpkg)) {
2.982 - if (!bitarray_get(&trans->syspkgs, reqpkg->data))
2.983 - continue;
2.984 - pkg = &spkgs[reqpkg->data];
2.985 - if (prop_is_being_updated(trans, sp)) {
2.986 - add_transaction_package(trans, NULL, pkg,
2.987 - RAZOR_PACKAGE_FORCED_UPDATE,
2.988 - removed_package, NULL);
2.989 - } else {
2.990 - add_transaction_package(trans, NULL, pkg,
2.991 - RAZOR_PACKAGE_REMOVE,
2.992 - removed_package, sr);
2.993 - }
2.994 - }
2.995 - }
2.996 + prop = list_first(&package->properties, &ts->set->property_pool);
2.997 + while (prop) {
2.998 + ts->properties[prop->data]++;
2.999 + prop = list_next(prop);
2.1000 }
2.1001 }
2.1002
2.1003 -void
2.1004 -razor_transaction_install_package(struct razor_transaction *transaction,
2.1005 - struct razor_package *package)
2.1006 +static void
2.1007 +transaction_set_remove_package(struct transaction_set *ts,
2.1008 + struct razor_package *package)
2.1009 {
2.1010 - add_transaction_package(transaction, package, NULL,
2.1011 - RAZOR_PACKAGE_INSTALL, NULL, NULL);
2.1012 -}
2.1013 + struct razor_package *pkgs;
2.1014 + struct list *prop;
2.1015 + int i;
2.1016
2.1017 -void
2.1018 -razor_transaction_remove_package(struct razor_transaction *transaction,
2.1019 - struct razor_package *package)
2.1020 -{
2.1021 - add_transaction_package(transaction, NULL, package,
2.1022 - RAZOR_PACKAGE_REMOVE, NULL, NULL);
2.1023 -}
2.1024 + pkgs = ts->set->packages.data;
2.1025 + i = package - pkgs;
2.1026 + if (ts->packages[i] == 0)
2.1027 + return;
2.1028
2.1029 -void
2.1030 -razor_transaction_update_all(struct razor_transaction *trans)
2.1031 -{
2.1032 - struct razor_package *sp, *spkgs, *send, *up, *upkgs, *uend;
2.1033 - const char *spool, *upool;
2.1034 + ts->packages[i] = 0;
2.1035
2.1036 - spkgs = trans->system->packages.data;
2.1037 - send = trans->system->packages.data + trans->system->packages.size;
2.1038 - spool = trans->system->string_pool.data;
2.1039 - up = upkgs = trans->upstream->packages.data;
2.1040 - uend = trans->upstream->packages.data + trans->upstream->packages.size;
2.1041 - upool = trans->upstream->string_pool.data;
2.1042 -
2.1043 - for (sp = spkgs; sp < send; sp++) {
2.1044 - while (up < uend && strcmp(&spool[sp->name], &upool[up->name]) > 0)
2.1045 - up++;
2.1046 - if (strcmp(&spool[sp->name], &upool[up->name]) == 0 &&
2.1047 - versioncmp(&spool[sp->version], &upool[up->version]) < 0) {
2.1048 - add_transaction_package(trans, up, sp,
2.1049 - RAZOR_PACKAGE_INSTALL,
2.1050 - NULL, NULL);
2.1051 - }
2.1052 + prop = list_first(&package->properties, &ts->set->property_pool);
2.1053 + while (prop) {
2.1054 + ts->properties[prop->data]--;
2.1055 + prop = list_next(prop);
2.1056 }
2.1057 }
2.1058
2.1059 @@ -2638,242 +1839,618 @@
2.1060 razor_transaction_create(struct razor_set *system, struct razor_set *upstream)
2.1061 {
2.1062 struct razor_transaction *trans;
2.1063 - int count;
2.1064 + struct razor_package *p, *spkgs, *pend;
2.1065
2.1066 trans = zalloc(sizeof *trans);
2.1067 + transaction_set_init(&trans->system, system);
2.1068 + transaction_set_init(&trans->upstream, upstream);
2.1069
2.1070 - trans->system = system;
2.1071 - trans->upstream = upstream ? upstream : razor_set_create();
2.1072 - array_init(&trans->packages);
2.1073 - count = trans->system->packages.size / sizeof (struct razor_package);
2.1074 - bitarray_init(&trans->syspkgs, count, 1);
2.1075 - count = trans->upstream->packages.size / sizeof (struct razor_package);
2.1076 - bitarray_init(&trans->uppkgs, count, 0);
2.1077 + spkgs = trans->system.set->packages.data;
2.1078 + pend = trans->system.set->packages.data +
2.1079 + trans->system.set->packages.size;
2.1080 + for (p = spkgs; p < pend; p++)
2.1081 + transaction_set_install_package(&trans->system, p);
2.1082
2.1083 return trans;
2.1084 }
2.1085
2.1086 -static void
2.1087 -resolve_transaction(struct razor_transaction *trans)
2.1088 +void
2.1089 +razor_transaction_install_package(struct razor_transaction *trans,
2.1090 + struct razor_package *package)
2.1091 {
2.1092 - int start, end;
2.1093 -
2.1094 - if (trans->package_count > 0)
2.1095 - /* Already did this, return. */
2.1096 - return;
2.1097 -
2.1098 - start = 0;
2.1099 - end = trans->packages.size / sizeof (struct razor_transaction_package);
2.1100 -
2.1101 - while (start != end) {
2.1102 - resolve_new_packages(trans, start, end);
2.1103 - if (trans->errors)
2.1104 - break;
2.1105 -
2.1106 - razor_transaction_satisfy(trans);
2.1107 -
2.1108 - start = end;
2.1109 - end = trans->packages.size / sizeof (struct razor_transaction_package);
2.1110 - }
2.1111 -
2.1112 - trans->package_count = end;
2.1113 + transaction_set_install_package(&trans->upstream, package);
2.1114 + trans->changes++;
2.1115 }
2.1116
2.1117 -const char * const razor_version_relations[] = {
2.1118 - /* same order as enum razor_version_relation */
2.1119 - "<", "<=", "=", ">=", ">"
2.1120 -};
2.1121 +void
2.1122 +razor_transaction_remove_package(struct razor_transaction *trans,
2.1123 + struct razor_package *package)
2.1124 +{
2.1125 + transaction_set_remove_package(&trans->system, package);
2.1126 + trans->changes++;
2.1127 +}
2.1128
2.1129 -const char * const razor_property_types[] = {
2.1130 - /* same order as enum razor_property_type */
2.1131 - "requires", "provides", "conflicts with", "obsoletes"
2.1132 +void
2.1133 +razor_transaction_update_package(struct razor_transaction *trans,
2.1134 + struct razor_package *package)
2.1135 +{
2.1136 + struct razor_package *spkgs;
2.1137 +
2.1138 + spkgs = trans->system.set->packages.data;
2.1139 + trans->system.packages[package - spkgs] |= TRANS_PACKAGE_UPDATE;
2.1140 +}
2.1141 +
2.1142 +struct prop_iter {
2.1143 + struct razor_property *p, *start, *end;
2.1144 + const char *pool;
2.1145 + uint32_t *present;
2.1146 };
2.1147
2.1148 static void
2.1149 -print_requirement(struct razor_transaction_package *p)
2.1150 +prop_iter_init(struct prop_iter *pi, struct transaction_set *ts)
2.1151 {
2.1152 - if (p->dep_type == RAZOR_PROPERTY_CONFLICTS &&
2.1153 - !strcmp(p->dep_package, p->name)) {
2.1154 - printf(" because %s %s conflicts with %s",
2.1155 - p->name, p->old_version, p->dep_property);
2.1156 - if (*p->dep_version) {
2.1157 - printf(" %s %s",
2.1158 - razor_version_relations[p->dep_relation],
2.1159 - p->dep_version);
2.1160 + pi->p = ts->set->properties.data;
2.1161 + pi->start = ts->set->properties.data;
2.1162 + pi->end = ts->set->properties.data + ts->set->properties.size;
2.1163 + pi->pool = ts->set->string_pool.data;
2.1164 + pi->present = ts->properties;
2.1165 +}
2.1166 +
2.1167 +static int
2.1168 +prop_iter_next(struct prop_iter *pi,
2.1169 + enum razor_property_type type, struct razor_property **p)
2.1170 +{
2.1171 + while (pi->p < pi->end) {
2.1172 + if ((pi->present[pi->p - pi->start] & ~TRANS_PROPERTY_SATISFIED) &&
2.1173 + pi->p->type == type) {
2.1174 + *p = pi->p++;
2.1175 + return 1;
2.1176 }
2.1177 + pi->p++;
2.1178 + }
2.1179 +
2.1180 + return 0;
2.1181 +}
2.1182 +
2.1183 +static struct razor_property *
2.1184 +prop_iter_seek_to(struct prop_iter *pi,
2.1185 + enum razor_property_type type, const char *match)
2.1186 +{
2.1187 + uint32_t name;
2.1188 +
2.1189 + while (pi->p < pi->end && strcmp(&pi->pool[pi->p->name], match) < 0)
2.1190 + pi->p++;
2.1191 +
2.1192 + if (pi->p == pi->end || strcmp(&pi->pool[pi->p->name], match) > 0)
2.1193 + return NULL;
2.1194 +
2.1195 + name = pi->p->name;
2.1196 + while (pi->p < pi->end &&
2.1197 + pi->p->name == name &&
2.1198 + pi->p->type != type)
2.1199 + pi->p++;
2.1200 +
2.1201 + if (pi->p == pi->end || pi->p->name != name)
2.1202 + return NULL;
2.1203 +
2.1204 + return pi->p;
2.1205 +}
2.1206 +
2.1207 +/* Remove packages from set that provide any of the matching (same
2.1208 + * name and type) providers from ppi onwards that match the
2.1209 + * requirement that rpi points to. */
2.1210 +static void
2.1211 +remove_matching_providers(struct razor_transaction *trans,
2.1212 + struct prop_iter *ppi,
2.1213 + enum razor_version_relation relation,
2.1214 + const char *version)
2.1215 +{
2.1216 + struct razor_property *p;
2.1217 + struct razor_package *pkg, *pkgs;
2.1218 + struct razor_package_iterator pkg_iter;
2.1219 + struct razor_set *set;
2.1220 + const char *n, *v, *a;
2.1221 +
2.1222 + if (ppi->present == trans->system.properties)
2.1223 + set = trans->system.set;
2.1224 + else
2.1225 + set = trans->upstream.set;
2.1226 +
2.1227 + pkgs = (struct razor_package *) set->packages.data;
2.1228 + for (p = ppi->p;
2.1229 + p < ppi->end &&
2.1230 + p->name == ppi->p->name &&
2.1231 + p->type == ppi->p->type;
2.1232 + p++) {
2.1233 + if (!ppi->present[p - ppi->start])
2.1234 + continue;
2.1235 + if (!provider_satisfies_requirement(p, ppi->pool,
2.1236 + relation, version))
2.1237 + continue;
2.1238 +
2.1239 + razor_package_iterator_init_for_property(&pkg_iter, set, p);
2.1240 + while (razor_package_iterator_next(&pkg_iter,
2.1241 + &pkg, &n, &v, &a)) {
2.1242 + fprintf(stderr, "removing %s-%s\n", n, v);
2.1243 + razor_transaction_remove_package(trans, pkg);
2.1244 + }
2.1245 + }
2.1246 +}
2.1247 +
2.1248 +static void
2.1249 +flag_matching_providers(struct razor_transaction *trans,
2.1250 + struct prop_iter *ppi,
2.1251 + struct razor_property *r,
2.1252 + struct prop_iter *rpi,
2.1253 + unsigned int flag)
2.1254 +{
2.1255 + struct razor_property *p;
2.1256 + struct razor_package *pkg, *pkgs;
2.1257 + struct razor_package_iterator pkg_iter;
2.1258 + struct razor_set *set;
2.1259 + const char *name, *version, *arch;
2.1260 + uint32_t *flags;
2.1261 +
2.1262 + if (ppi->present == trans->system.properties) {
2.1263 + set = trans->system.set;
2.1264 + flags = trans->system.packages;
2.1265 } else {
2.1266 - if (strcmp(p->name, p->dep_package) != 0)
2.1267 - printf(" for %s", p->dep_package);
2.1268 - if (*p->dep_version) {
2.1269 - printf(", which %s %s %s %s",
2.1270 - razor_property_types[p->dep_type],
2.1271 - p->dep_property,
2.1272 - razor_version_relations[p->dep_relation],
2.1273 - p->dep_version);
2.1274 - } else if (strcmp(p->dep_property, p->name) != 0) {
2.1275 - printf(", which %s %s",
2.1276 - razor_property_types[p->dep_type],
2.1277 - p->dep_property);
2.1278 + set = trans->upstream.set;
2.1279 + flags = trans->upstream.packages;
2.1280 + }
2.1281 +
2.1282 + pkgs = (struct razor_package *) set->packages.data;
2.1283 + for (p = ppi->p;
2.1284 + p < ppi->end &&
2.1285 + p->name == ppi->p->name &&
2.1286 + p->type == ppi->p->type;
2.1287 + p++) {
2.1288 + if (!ppi->present[p - ppi->start])
2.1289 + continue;
2.1290 + if (!provider_satisfies_requirement(p, ppi->pool,
2.1291 + r->relation,
2.1292 + &rpi->pool[r->version]))
2.1293 + continue;
2.1294 +
2.1295 + razor_package_iterator_init_for_property(&pkg_iter, set, p);
2.1296 + while (razor_package_iterator_next(&pkg_iter, &pkg,
2.1297 + &name, &version, &arch)) {
2.1298 +
2.1299 + fprintf(stderr, "flagging %s-%s for providing %s matching %s %s\n",
2.1300 + name, version,
2.1301 + ppi->pool + p->name,
2.1302 + rpi->pool + r->name,
2.1303 + rpi->pool + r->version);
2.1304 + flags[pkg - pkgs] |= flag;
2.1305 }
2.1306 }
2.1307 }
2.1308
2.1309 +static struct razor_package *
2.1310 +pick_matching_provider(struct razor_set *set,
2.1311 + struct prop_iter *ppi,
2.1312 + enum razor_version_relation relation,
2.1313 + const char *version)
2.1314 +{
2.1315 + struct razor_property *p;
2.1316 + struct razor_package *pkgs;
2.1317 + struct list *i;
2.1318 +
2.1319 + /* This is where we decide which pkgs to pull in to satisfy a
2.1320 + * requirement. There may be several different providers
2.1321 + * (different versions) and each version of a provider may
2.1322 + * come from a number of packages. We pick the first package
2.1323 + * from the first provider that matches. */
2.1324 +
2.1325 + pkgs = set->packages.data;
2.1326 + for (p = ppi->p;
2.1327 + p < ppi->end &&
2.1328 + p->name == ppi->p->name &&
2.1329 + p->type == ppi->p->type &&
2.1330 + ppi->present[p - ppi->start] == 0;
2.1331 + p++) {
2.1332 + if (!provider_satisfies_requirement(p, ppi->pool,
2.1333 + relation, version))
2.1334 + continue;
2.1335 +
2.1336 + i = list_first(&p->packages, &set->package_pool);
2.1337 +
2.1338 + return &pkgs[i->data];
2.1339 + }
2.1340 +
2.1341 + return NULL;
2.1342 +}
2.1343 +
2.1344 +static void
2.1345 +remove_obsoleted_packages(struct razor_transaction *trans)
2.1346 +{
2.1347 + struct razor_property *up;
2.1348 + struct razor_package *spkgs;
2.1349 + struct prop_iter spi, upi;
2.1350 +
2.1351 + spkgs = trans->system.set->packages.data;
2.1352 + prop_iter_init(&spi, &trans->system);
2.1353 + prop_iter_init(&upi, &trans->upstream);
2.1354 +
2.1355 + while (prop_iter_next(&upi, RAZOR_PROPERTY_OBSOLETES, &up)) {
2.1356 + if (!prop_iter_seek_to(&spi, RAZOR_PROPERTY_PROVIDES,
2.1357 + &upi.pool[up->name]))
2.1358 + continue;
2.1359 + remove_matching_providers(trans, &spi, up->relation,
2.1360 + &upi.pool[up->version]);
2.1361 + }
2.1362 +}
2.1363 +
2.1364 +static int
2.1365 +any_provider_satisfies_requirement(struct prop_iter *ppi,
2.1366 + enum razor_version_relation relation,
2.1367 + const char *version)
2.1368 +{
2.1369 + struct razor_property *p;
2.1370 +
2.1371 + for (p = ppi->p;
2.1372 + p < ppi->end &&
2.1373 + p->name == ppi->p->name &&
2.1374 + p->type == ppi->p->type;
2.1375 + p++) {
2.1376 + if (ppi->present[p - ppi->start] > 0 &&
2.1377 + provider_satisfies_requirement(p, ppi->pool,
2.1378 + relation, version))
2.1379 + return 1;
2.1380 + }
2.1381 +
2.1382 + return 0;
2.1383 +}
2.1384 +
2.1385 +static void
2.1386 +clear_requires_flags(struct transaction_set *ts)
2.1387 +{
2.1388 + struct razor_property *p;
2.1389 + const char *pool;
2.1390 + int i, count;
2.1391 +
2.1392 + count = ts->set->properties.size / sizeof *p;
2.1393 + p = ts->set->properties.data;
2.1394 + pool = ts->set->string_pool.data;
2.1395 + for (i = 0; i < count; i++) {
2.1396 + ts->properties[i] &= ~TRANS_PROPERTY_SATISFIED;
2.1397 + if (strncmp(&pool[p[i].name], "rpmlib(", 7) == 0)
2.1398 + ts->properties[i] |= TRANS_PROPERTY_SATISFIED;
2.1399 + }
2.1400 +}
2.1401 +
2.1402 +static void
2.1403 +mark_satisfied_requires(struct razor_transaction *trans,
2.1404 + struct transaction_set *rts,
2.1405 + struct transaction_set *pts)
2.1406 +{
2.1407 + struct prop_iter rpi, ppi;
2.1408 + struct razor_property *rp;
2.1409 +
2.1410 + prop_iter_init(&rpi, rts);
2.1411 + prop_iter_init(&ppi, pts);
2.1412 +
2.1413 + while (prop_iter_next(&rpi, RAZOR_PROPERTY_REQUIRES, &rp)) {
2.1414 + if (!prop_iter_seek_to(&ppi, RAZOR_PROPERTY_PROVIDES,
2.1415 + &rpi.pool[rp->name]))
2.1416 + continue;
2.1417 +
2.1418 + if (any_provider_satisfies_requirement(&ppi, rp->relation,
2.1419 + &rpi.pool[rp->version]))
2.1420 + rpi.present[rp - rpi.start] |= TRANS_PROPERTY_SATISFIED;
2.1421 + }
2.1422 +}
2.1423 +
2.1424 +static const char *relation_string[] = { "<", "<=", "=", ">=", ">" };
2.1425 +
2.1426 +static void
2.1427 +mark_all_satisfied_requires(struct razor_transaction *trans)
2.1428 +{
2.1429 + struct razor_property *sp;
2.1430 + struct prop_iter spi;
2.1431 +
2.1432 + clear_requires_flags(&trans->system);
2.1433 + clear_requires_flags(&trans->upstream);
2.1434 + mark_satisfied_requires(trans, &trans->system, &trans->system);
2.1435 + mark_satisfied_requires(trans, &trans->system, &trans->upstream);
2.1436 + mark_satisfied_requires(trans, &trans->upstream, &trans->system);
2.1437 + mark_satisfied_requires(trans, &trans->upstream, &trans->upstream);
2.1438 +
2.1439 + prop_iter_init(&spi, &trans->system);
2.1440 + while (prop_iter_next(&spi, RAZOR_PROPERTY_REQUIRES, &sp)) {
2.1441 + if (spi.present[sp - spi.start] & TRANS_PROPERTY_SATISFIED)
2.1442 + continue;
2.1443 + fprintf(stderr, "unsatisfied system requires: %s %s %s\n",
2.1444 + spi.pool + sp->name,
2.1445 + relation_string[sp->relation],
2.1446 + spi.pool + sp->version);
2.1447 + }
2.1448 +
2.1449 + prop_iter_init(&spi, &trans->upstream);
2.1450 + while (prop_iter_next(&spi, RAZOR_PROPERTY_REQUIRES, &sp)) {
2.1451 + if (spi.present[sp - spi.start] & TRANS_PROPERTY_SATISFIED)
2.1452 + continue;
2.1453 + fprintf(stderr, "unsatisfied upstream requires: %s %s %s\n",
2.1454 + spi.pool + sp->name,
2.1455 + relation_string[sp->relation],
2.1456 + spi.pool + sp->version);
2.1457 + }
2.1458 +}
2.1459 +
2.1460 +static void
2.1461 +update_unsatisfied_packages(struct razor_transaction *trans)
2.1462 +{
2.1463 + struct razor_package *spkgs, *pkg;
2.1464 + struct razor_property *sp;
2.1465 + struct prop_iter spi;
2.1466 + struct razor_package_iterator pkg_iter;
2.1467 + const char *name, *version, *arch;
2.1468 +
2.1469 + spkgs = trans->system.set->packages.data;
2.1470 + prop_iter_init(&spi, &trans->system);
2.1471 +
2.1472 + while (prop_iter_next(&spi, RAZOR_PROPERTY_REQUIRES, &sp)) {
2.1473 + if (spi.present[sp - spi.start] & TRANS_PROPERTY_SATISFIED)
2.1474 + continue;
2.1475 +
2.1476 + razor_package_iterator_init_for_property(&pkg_iter,
2.1477 + trans->system.set,
2.1478 + sp);
2.1479 + while (razor_package_iterator_next(&pkg_iter, &pkg,
2.1480 + &name, &version, &arch)) {
2.1481 + fprintf(stderr, "updating %s because %s %s %s "
2.1482 + "isn't satisfied\n",
2.1483 + name, spi.pool + sp->name,
2.1484 + relation_string[sp->relation],
2.1485 + spi.pool + sp->version);
2.1486 + trans->system.packages[pkg - spkgs] |=
2.1487 + TRANS_PACKAGE_UPDATE;
2.1488 + }
2.1489 + }
2.1490 +}
2.1491 +
2.1492 +void
2.1493 +razor_transaction_update_all(struct razor_transaction *trans)
2.1494 +{
2.1495 + struct razor_package *p;
2.1496 + int i, count;
2.1497 +
2.1498 + count = trans->system.set->packages.size / sizeof *p;
2.1499 + for (i = 0; i < count; i++)
2.1500 + trans->system.packages[i] |= TRANS_PACKAGE_UPDATE;
2.1501 +}
2.1502 +
2.1503 +static void
2.1504 +update_conflicted_packages(struct razor_transaction *trans)
2.1505 +{
2.1506 + struct razor_package *pkg, *spkgs;
2.1507 + struct razor_property *up, *sp;
2.1508 + struct prop_iter spi, upi;
2.1509 + struct razor_package_iterator pkg_iter;
2.1510 + const char *name, *version, *arch;
2.1511 +
2.1512 + spkgs = trans->system.set->packages.data;
2.1513 + prop_iter_init(&spi, &trans->system);
2.1514 + prop_iter_init(&upi, &trans->upstream);
2.1515 +
2.1516 + while (prop_iter_next(&spi, RAZOR_PROPERTY_CONFLICTS, &sp)) {
2.1517 + if (!prop_iter_seek_to(&upi, RAZOR_PROPERTY_PROVIDES,
2.1518 + &spi.pool[sp->name]))
2.1519 + continue;
2.1520 +
2.1521 + if (!any_provider_satisfies_requirement(&upi, sp->relation,
2.1522 + &spi.pool[sp->version]))
2.1523 + continue;
2.1524 +
2.1525 + razor_package_iterator_init_for_property(&pkg_iter,
2.1526 + trans->system.set,
2.1527 + sp);
2.1528 + while (razor_package_iterator_next(&pkg_iter, &pkg,
2.1529 + &name, &version, &arch)) {
2.1530 + fprintf(stderr, "updating %s %s because it conflicts with %s",
2.1531 + name, version, spi.pool + sp->name);
2.1532 + trans->system.packages[pkg - spkgs] |=
2.1533 + TRANS_PACKAGE_UPDATE;
2.1534 + }
2.1535 + }
2.1536 +
2.1537 + prop_iter_init(&spi, &trans->system);
2.1538 + prop_iter_init(&upi, &trans->upstream);
2.1539 +
2.1540 + while (prop_iter_next(&upi, RAZOR_PROPERTY_CONFLICTS, &up)) {
2.1541 + sp = prop_iter_seek_to(&spi, RAZOR_PROPERTY_PROVIDES,
2.1542 + &upi.pool[upi.p->name]);
2.1543 +
2.1544 + if (sp)
2.1545 + flag_matching_providers(trans, &spi, up, &upi,
2.1546 + TRANS_PACKAGE_UPDATE);
2.1547 + }
2.1548 +}
2.1549 +
2.1550 +static void
2.1551 +pull_in_requirements(struct razor_transaction *trans,
2.1552 + struct prop_iter *rpi, struct prop_iter *ppi)
2.1553 +{
2.1554 + struct razor_property *rp, *pp;
2.1555 + struct razor_package *pkg, *upkgs;
2.1556 +
2.1557 + upkgs = trans->upstream.set->packages.data;
2.1558 + while (prop_iter_next(rpi, RAZOR_PROPERTY_REQUIRES, &rp)) {
2.1559 + if (rpi->present[rp - rpi->start] & TRANS_PROPERTY_SATISFIED)
2.1560 + continue;
2.1561 +
2.1562 + pp = prop_iter_seek_to(ppi, RAZOR_PROPERTY_PROVIDES,
2.1563 + &rpi->pool[rp->name]);
2.1564 + if (pp == NULL)
2.1565 + continue;
2.1566 + pkg = pick_matching_provider(trans->upstream.set,
2.1567 + ppi, rp->relation,
2.1568 + &rpi->pool[rp->version]);
2.1569 + if (pkg == NULL)
2.1570 + continue;
2.1571 +
2.1572 + rpi->present[rp - rpi->start] |= TRANS_PROPERTY_SATISFIED;
2.1573 +
2.1574 + fprintf(stderr, "pulling in %s which provides %s %s %s "
2.1575 + "to satisfy %s %s %s\n",
2.1576 + ppi->pool + pkg->name,
2.1577 + ppi->pool + pp->name,
2.1578 + relation_string[pp->relation],
2.1579 + ppi->pool + pp->version,
2.1580 + &rpi->pool[rp->name],
2.1581 + relation_string[rp->relation],
2.1582 + &rpi->pool[rp->version]);
2.1583 +
2.1584 + trans->upstream.packages[pkg - upkgs] |= TRANS_PACKAGE_UPDATE;
2.1585 + }
2.1586 +}
2.1587 +
2.1588 +static void
2.1589 +pull_in_all_requirements(struct razor_transaction *trans)
2.1590 +{
2.1591 + struct prop_iter rpi, ppi;
2.1592 + struct razor_property *rp;
2.1593 +
2.1594 + prop_iter_init(&rpi, &trans->system);
2.1595 + prop_iter_init(&ppi, &trans->upstream);
2.1596 + pull_in_requirements(trans, &rpi, &ppi);
2.1597 +
2.1598 + prop_iter_init(&rpi, &trans->upstream);
2.1599 + prop_iter_init(&ppi, &trans->upstream);
2.1600 + pull_in_requirements(trans, &rpi, &ppi);
2.1601 +
2.1602 + prop_iter_init(&rpi, &trans->system);
2.1603 + while (prop_iter_next(&rpi, RAZOR_PROPERTY_REQUIRES, &rp)) {
2.1604 + if (!(rpi.present[rp - rpi.start] & TRANS_PROPERTY_SATISFIED))
2.1605 + fprintf(stderr, "could not satisfy req %s %s %s\n",
2.1606 + &rpi.pool[rp->name],
2.1607 + relation_string[rp->relation],
2.1608 + &rpi.pool[rp->version]);
2.1609 + }
2.1610 +
2.1611 + prop_iter_init(&rpi, &trans->upstream);
2.1612 + while (prop_iter_next(&rpi, RAZOR_PROPERTY_REQUIRES, &rp)) {
2.1613 + if (!(rpi.present[rp - rpi.start] & TRANS_PROPERTY_SATISFIED))
2.1614 + fprintf(stderr, "could not satisfy req %s %s %s\n",
2.1615 + &rpi.pool[rp->name],
2.1616 + relation_string[rp->relation],
2.1617 + &rpi.pool[rp->version]);
2.1618 + }
2.1619 +}
2.1620 +
2.1621 +static void
2.1622 +flush_scheduled_system_updates(struct razor_transaction *trans)
2.1623 +{
2.1624 + struct razor_package_iterator *pi;
2.1625 + struct razor_package *p, *pkg, *spkgs;
2.1626 + struct prop_iter ppi;
2.1627 + const char *name, *version, *arch;
2.1628 +
2.1629 + spkgs = trans->system.set->packages.data;
2.1630 + pi = razor_package_iterator_create(trans->system.set);
2.1631 + prop_iter_init(&ppi, &trans->upstream);
2.1632 +
2.1633 + while (razor_package_iterator_next(pi, &p, &name, &version, &arch)) {
2.1634 + if (!(trans->system.packages[p - spkgs] & TRANS_PACKAGE_UPDATE))
2.1635 + continue;
2.1636 +
2.1637 + if (!prop_iter_seek_to(&ppi, RAZOR_PROPERTY_PROVIDES, name)) {
2.1638 + fprintf(stderr, "nothing provides %s\n", name);
2.1639 + continue;
2.1640 + }
2.1641 +
2.1642 + pkg = pick_matching_provider(trans->upstream.set, &ppi,
2.1643 + RAZOR_VERSION_GREATER, version);
2.1644 + if (pkg == NULL) {
2.1645 + fprintf(stderr,
2.1646 + "no newer version of %s available\n", name);
2.1647 + continue;
2.1648 + }
2.1649 +
2.1650 + fprintf(stderr, "updating %s from %s to %s\n",
2.1651 + name, version, &ppi.pool[pkg->version]);
2.1652 +
2.1653 + razor_transaction_remove_package(trans, p);
2.1654 + razor_transaction_install_package(trans, pkg);
2.1655 + }
2.1656 +
2.1657 + razor_package_iterator_destroy(pi);
2.1658 +}
2.1659 +
2.1660 +static void
2.1661 +flush_scheduled_upstream_updates(struct razor_transaction *trans)
2.1662 +{
2.1663 + struct razor_package_iterator *pi;
2.1664 + struct razor_package *p, *upkgs;
2.1665 + struct prop_iter spi;
2.1666 + const char *name, *version, *arch;
2.1667 +
2.1668 + upkgs = trans->upstream.set->packages.data;
2.1669 + pi = razor_package_iterator_create(trans->upstream.set);
2.1670 + prop_iter_init(&spi, &trans->system);
2.1671 +
2.1672 + while (razor_package_iterator_next(pi, &p, &name, &version, &arch)) {
2.1673 + if (!(trans->upstream.packages[p - upkgs] & TRANS_PACKAGE_UPDATE))
2.1674 + continue;
2.1675 +
2.1676 + if (!prop_iter_seek_to(&spi, RAZOR_PROPERTY_PROVIDES, name))
2.1677 + continue;
2.1678 + remove_matching_providers(trans, &spi,
2.1679 + RAZOR_VERSION_LESS, version);
2.1680 + razor_transaction_install_package(trans, p);
2.1681 + fprintf(stderr, "installing %s-%s\n", name, version);
2.1682 + }
2.1683 +}
2.1684 +
2.1685 int
2.1686 razor_transaction_resolve(struct razor_transaction *trans)
2.1687 {
2.1688 - struct razor_transaction_package *p, *pend, *tps;
2.1689 - int errors_only = 0;
2.1690 + int last = 0;
2.1691
2.1692 - resolve_transaction(trans);
2.1693 + flush_scheduled_system_updates(trans);
2.1694
2.1695 - tps = trans->packages.data;
2.1696 - pend = trans->packages.data + trans->packages.size;
2.1697 - for (p = trans->packages.data; p < pend; p++) {
2.1698 - switch (p->state) {
2.1699 - case RAZOR_PACKAGE_INSTALL:
2.1700 - if (errors_only)
2.1701 - break;
2.1702 -
2.1703 - printf("Installing %s %s", p->name, p->new_version);
2.1704 - if (p->dep_package)
2.1705 - print_requirement(p);
2.1706 - printf("\n");
2.1707 - break;
2.1708 -
2.1709 - case RAZOR_PACKAGE_FORCED_UPDATE:
2.1710 - if (errors_only)
2.1711 - break;
2.1712 -
2.1713 - printf("Updating %s to %s due to update of %s\n",
2.1714 - p->name, p->new_version, p->dep_package);
2.1715 - break;
2.1716 -
2.1717 - case RAZOR_PACKAGE_REMOVE:
2.1718 - if (errors_only)
2.1719 - break;
2.1720 - printf("Removing %s %s", p->name, p->old_version);
2.1721 - if (p->dep_package) {
2.1722 - printf(" which required %s",
2.1723 - p->dep_package);
2.1724 - if (strcmp(p->dep_property, p->dep_package) != 0)
2.1725 - printf(" for %s", p->dep_property);
2.1726 - }
2.1727 - printf("\n");
2.1728 - break;
2.1729 -
2.1730 - case RAZOR_PACKAGE_OBSOLETED:
2.1731 - if (errors_only)
2.1732 - break;
2.1733 - printf("Removing %s %s", p->name, p->old_version);
2.1734 - if (p->dep_package) {
2.1735 - printf(" which is obsoleted by %s",
2.1736 - p->dep_package);
2.1737 - }
2.1738 - printf("\n");
2.1739 - break;
2.1740 -
2.1741 - case RAZOR_PACKAGE_INSTALL_UNAVAILABLE:
2.1742 - printf("Error: can't find %s", p->name);
2.1743 - if (p->dep_package) {
2.1744 - printf(" (which is required");
2.1745 - print_requirement(p);
2.1746 - printf(")");
2.1747 - }
2.1748 - printf("\n");
2.1749 - errors_only = 1;
2.1750 - break;
2.1751 -
2.1752 - case RAZOR_PACKAGE_UPDATE_UNAVAILABLE:
2.1753 - printf("Error: can't find an updated version of %s (which must be updated due to update of %s)\n",
2.1754 - p->name, p->dep_package);
2.1755 - errors_only = 1;
2.1756 - break;
2.1757 -
2.1758 - case RAZOR_PACKAGE_REMOVE_NOT_INSTALLED:
2.1759 - printf("Error: can't remove %s: not installed\n", p->name);
2.1760 - errors_only = 1;
2.1761 - break;
2.1762 -
2.1763 - case RAZOR_PACKAGE_UP_TO_DATE:
2.1764 - printf("Error: can't update %s", p->name);
2.1765 - if (p->dep_package)
2.1766 - printf(" (which must be updated due to update of %s)", p->dep_package);
2.1767 - printf(": %s is most recent version\n", p->old_version);
2.1768 - errors_only = 1;
2.1769 - break;
2.1770 -
2.1771 - case RAZOR_PACKAGE_CONTRADICTION:
2.1772 - printf("Error: package %s is marked for both installation and removal\n", p->name);
2.1773 - errors_only = 1;
2.1774 - break;
2.1775 -
2.1776 - case RAZOR_PACKAGE_OLD_CONFLICT:
2.1777 - printf("Error: can't install %s, because installed package %s conflicts with ",
2.1778 - p->name, p->dep_package);
2.1779 - if (*p->dep_version) {
2.1780 - printf("%s %s %s",
2.1781 - p->dep_property,
2.1782 - razor_version_relations[p->dep_relation],
2.1783 - p->dep_version);
2.1784 - } else
2.1785 - printf("it");
2.1786 - printf("\n");
2.1787 -
2.1788 - errors_only = 1;
2.1789 - break;
2.1790 -
2.1791 - case RAZOR_PACKAGE_NEW_CONFLICT:
2.1792 - printf("Error: can't install %s, because it conflicts with %s",
2.1793 - p->name, p->dep_package);
2.1794 - if (*p->dep_version) {
2.1795 - printf(" %s %s",
2.1796 - razor_version_relations[p->dep_relation],
2.1797 - p->dep_version);
2.1798 - }
2.1799 - printf("\n");
2.1800 -
2.1801 - errors_only = 1;
2.1802 - break;
2.1803 -
2.1804 - case RAZOR_PACKAGE_UNSATISFIABLE:
2.1805 - printf("Error: can't find package for %s", p->dep_property);
2.1806 - if (*p->dep_version) {
2.1807 - printf(" %s %s",
2.1808 - razor_version_relations[p->dep_relation],
2.1809 - p->dep_version);
2.1810 - }
2.1811 - printf(" which is required by %s\n",
2.1812 - p->dep_package);
2.1813 - errors_only = 1;
2.1814 - break;
2.1815 -
2.1816 - default:
2.1817 - /* Shouldn't actually happen */
2.1818 - break;
2.1819 - }
2.1820 + while (last < trans->changes) {
2.1821 + last = trans->changes;
2.1822 + remove_obsoleted_packages(trans);
2.1823 + mark_all_satisfied_requires(trans);
2.1824 + update_unsatisfied_packages(trans);
2.1825 + update_conflicted_packages(trans);
2.1826 + pull_in_all_requirements(trans);
2.1827 + flush_scheduled_system_updates(trans);
2.1828 + flush_scheduled_upstream_updates(trans);
2.1829 }
2.1830
2.1831 - return trans->errors;
2.1832 + return trans->changes;
2.1833 }
2.1834
2.1835 int
2.1836 razor_transaction_unsatisfied_property(struct razor_transaction *trans,
2.1837 const char *name,
2.1838 enum razor_version_relation rel,
2.1839 - const char *version)
2.1840 + const char *version,
2.1841 + enum razor_property_type type)
2.1842 {
2.1843 - struct razor_transaction_package *p, *end;
2.1844 + struct prop_iter pi;
2.1845 + struct razor_property *p;
2.1846
2.1847 - end = trans->packages.data + trans->packages.size;
2.1848 - for (p = trans->packages.data; p < end; p++) {
2.1849 - if (p->state != RAZOR_PACKAGE_UNSATISFIABLE)
2.1850 - continue;
2.1851 - if (strcmp(name, p->dep_property) != 0 ||
2.1852 - rel != p->dep_relation ||
2.1853 - strcmp(version, p->dep_version) != 0)
2.1854 - continue;
2.1855 + prop_iter_init(&pi, &trans->system);
2.1856 + while (prop_iter_next(&pi, type, &p)) {
2.1857 + if (!(trans->system.properties[p - pi.start] & TRANS_PROPERTY_SATISFIED) &&
2.1858 + p->relation == rel &&
2.1859 + strcmp(&pi.pool[p->name], name) == 0 &&
2.1860 + strcmp(&pi.pool[p->version], version) == 0)
2.1861 +
2.1862 + return 1;
2.1863 + }
2.1864
2.1865 - return 1;
2.1866 + prop_iter_init(&pi, &trans->upstream);
2.1867 + while (prop_iter_next(&pi, type, &p)) {
2.1868 + if (!(trans->upstream.properties[p - pi.start] & TRANS_PROPERTY_SATISFIED) &&
2.1869 + p->relation == rel &&
2.1870 + strcmp(&pi.pool[p->name], name) == 0 &&
2.1871 + strcmp(&pi.pool[p->version], version) == 0)
2.1872 +
2.1873 + return 1;
2.1874 }
2.1875
2.1876 return 0;
2.1877 @@ -2882,117 +2459,61 @@
2.1878 struct razor_set *
2.1879 razor_transaction_finish(struct razor_transaction *trans)
2.1880 {
2.1881 - struct array install_packages, remove_packages;
2.1882 struct razor_merger *merger;
2.1883 - struct razor_package *pkg, *i, *iend, *r, *rend, *s, *send;
2.1884 - struct razor_set *set;
2.1885 - struct source *source1, *source2;
2.1886 - char *spool, *ipool, *rpool;
2.1887 - uint32_t *map;
2.1888 - struct razor_transaction_package *p, *end;
2.1889 + struct razor_package *u, *uend, *upkgs, *s, *send, *spkgs;
2.1890 + char *upool, *spool;
2.1891 int cmp;
2.1892
2.1893 - /* FIXME */
2.1894 - if (trans->errors)
2.1895 - return NULL;
2.1896 + s = trans->system.set->packages.data;
2.1897 + spkgs = trans->system.set->packages.data;
2.1898 + send = trans->system.set->packages.data +
2.1899 + trans->system.set->packages.size;
2.1900 + spool = trans->system.set->string_pool.data;
2.1901
2.1902 - /* Sort the transaction packages into two arrays */
2.1903 - array_init(&install_packages);
2.1904 - array_init(&remove_packages);
2.1905 + u = trans->upstream.set->packages.data;
2.1906 + upkgs = trans->upstream.set->packages.data;
2.1907 + uend = trans->upstream.set->packages.data +
2.1908 + trans->upstream.set->packages.size;
2.1909 + upool = trans->upstream.set->string_pool.data;
2.1910
2.1911 - end = trans->packages.data + trans->packages.size;
2.1912 - for (p = trans->packages.data; p < end; p++) {
2.1913 - if (p->new_package) {
2.1914 - pkg = array_add(&install_packages, sizeof *pkg);
2.1915 - *pkg = *p->new_package;
2.1916 - } else {
2.1917 - pkg = array_add(&remove_packages, sizeof *pkg);
2.1918 - *pkg = *p->old_package;
2.1919 - }
2.1920 - }
2.1921 - map = razor_qsort_with_data(install_packages.data,
2.1922 - install_packages.size / sizeof *pkg,
2.1923 - sizeof *pkg,
2.1924 - compare_packages,
2.1925 - trans->upstream);
2.1926 - free(map);
2.1927 - map = razor_qsort_with_data(remove_packages.data,
2.1928 - remove_packages.size / sizeof *pkg,
2.1929 - sizeof *pkg,
2.1930 - compare_packages,
2.1931 - trans->system);
2.1932 - free(map);
2.1933 -
2.1934 - merger = razor_merger_create(trans->system, trans->upstream);
2.1935 -
2.1936 - source1 = &merger->source1;
2.1937 - source2 = &merger->source2;
2.1938 -
2.1939 - i = install_packages.data;
2.1940 - iend = install_packages.data + install_packages.size;
2.1941 - ipool = trans->upstream->string_pool.data;
2.1942 -
2.1943 - r = remove_packages.data;
2.1944 - rend = remove_packages.data + remove_packages.size;
2.1945 - rpool = trans->system->string_pool.data;
2.1946 -
2.1947 - s = trans->system->packages.data;
2.1948 - send = trans->system->packages.data + trans->system->packages.size;
2.1949 - spool = trans->system->string_pool.data;
2.1950 -
2.1951 - while (s < send || i < iend) {
2.1952 - /* Check if s is being removed */
2.1953 - if (s < send && r < rend &&
2.1954 - s->name == r->name && s->version && r->version) {
2.1955 - s++;
2.1956 - r++;
2.1957 - continue;
2.1958 - }
2.1959 -
2.1960 - if (s < send && i < iend)
2.1961 - cmp = strcmp(&spool[s->name], &ipool[i->name]);
2.1962 + merger = razor_merger_create(trans->system.set, trans->upstream.set);
2.1963 + while (s < send || u < uend) {
2.1964 + if (s < send && u < uend)
2.1965 + cmp = strcmp(&spool[s->name], &upool[u->name]);
2.1966 else if (s < send)
2.1967 cmp = -1;
2.1968 else
2.1969 cmp = 1;
2.1970 +
2.1971 if (cmp < 0) {
2.1972 - add_package(merger, s, source1, 0);
2.1973 + if (trans->system.packages[s - spkgs] & TRANS_PACKAGE_PRESENT)
2.1974 + razor_merger_add_package(merger, s);
2.1975 s++;
2.1976 } else if (cmp == 0) {
2.1977 - add_package(merger, i, source2, UPSTREAM_SOURCE);
2.1978 + if (trans->system.packages[s - spkgs] & TRANS_PACKAGE_PRESENT)
2.1979 + razor_merger_add_package(merger, s);
2.1980 + if (trans->upstream.packages[u - upkgs] & TRANS_PACKAGE_PRESENT)
2.1981 + razor_merger_add_package(merger, u);
2.1982 +
2.1983 s++;
2.1984 - i++;
2.1985 + u++;
2.1986 } else {
2.1987 - add_package(merger, i, source2, UPSTREAM_SOURCE);
2.1988 - i++;
2.1989 + if (trans->upstream.packages[u - upkgs] & TRANS_PACKAGE_PRESENT)
2.1990 + razor_merger_add_package(merger, u);
2.1991 + u++;
2.1992 }
2.1993 }
2.1994
2.1995 - array_release(&install_packages);
2.1996 - array_release(&remove_packages);
2.1997 -
2.1998 - set = razor_merger_finish(merger);
2.1999 razor_transaction_destroy(trans);
2.2000
2.2001 - return set;
2.2002 + return razor_merger_finish(merger);
2.2003 }
2.2004
2.2005 void
2.2006 razor_transaction_destroy(struct razor_transaction *trans)
2.2007 {
2.2008 - struct razor_transaction_package *p, *end;
2.2009 -
2.2010 - end = trans->packages.data + trans->packages.size;
2.2011 - for (p = trans->packages.data; p < end; p++) {
2.2012 - if (!p->dep_package &&
2.2013 - (p->state == RAZOR_PACKAGE_INSTALL_UNAVAILABLE ||
2.2014 - p->state == RAZOR_PACKAGE_REMOVE_NOT_INSTALLED))
2.2015 - free((char *)p->name);
2.2016 - }
2.2017 -
2.2018 - array_release(&trans->packages);
2.2019 - bitarray_release(&trans->syspkgs);
2.2020 - bitarray_release(&trans->uppkgs);
2.2021 + transaction_set_release(&trans->system);
2.2022 + transaction_set_release(&trans->upstream);
2.2023 free(trans);
2.2024
2.2025 /* FIXME: free upstream if it was created as an empty set */
3.1 --- a/razor.h Wed Jun 04 21:28:26 2008 -0400
3.2 +++ b/razor.h Mon Jun 09 12:47:37 2008 -0400
3.3 @@ -108,45 +108,14 @@
3.4
3.5 /* Package transactions */
3.6
3.7 -enum razor_transaction_package_state {
3.8 - /* Basic states */
3.9 - RAZOR_PACKAGE_INSTALL,
3.10 - RAZOR_PACKAGE_FORCED_UPDATE,
3.11 - RAZOR_PACKAGE_REMOVE,
3.12 - RAZOR_PACKAGE_OBSOLETED,
3.13 -
3.14 - /* Error states */
3.15 -
3.16 - RAZOR_PACKAGE_FIRST_ERROR_STATE = 0x4,
3.17 - RAZOR_PACKAGE_UNAVAILABLE_FLAG = 0x4,
3.18 -
3.19 - /* Package requested for install does not exist */
3.20 - RAZOR_PACKAGE_INSTALL_UNAVAILABLE = RAZOR_PACKAGE_INSTALL | RAZOR_PACKAGE_UNAVAILABLE_FLAG,
3.21 - /* Package requiring update does not have any update */
3.22 - RAZOR_PACKAGE_UPDATE_UNAVAILABLE = RAZOR_PACKAGE_FORCED_UPDATE | RAZOR_PACKAGE_UNAVAILABLE_FLAG,
3.23 - /* Package requested for removal does not exist */
3.24 - RAZOR_PACKAGE_REMOVE_NOT_INSTALLED = RAZOR_PACKAGE_REMOVE | RAZOR_PACKAGE_UNAVAILABLE_FLAG,
3.25 - /* (not used) */
3.26 - RAZOR_PACKAGE_OBSOLETE_UNAVAILABLE = RAZOR_PACKAGE_OBSOLETED | RAZOR_PACKAGE_UNAVAILABLE_FLAG,
3.27 -
3.28 - /* No newer version of package is available */
3.29 - RAZOR_PACKAGE_UP_TO_DATE,
3.30 - /* Package marked for both install and remove */
3.31 - RAZOR_PACKAGE_CONTRADICTION,
3.32 - /* Package would add a conflict with an already-installed package */
3.33 - RAZOR_PACKAGE_NEW_CONFLICT,
3.34 - /* Already-installed package has a conflict against this package */
3.35 - RAZOR_PACKAGE_OLD_CONFLICT,
3.36 - /* Requirement of to-be-installed package can't be satisfied */
3.37 - RAZOR_PACKAGE_UNSATISFIABLE,
3.38 -};
3.39 -
3.40 struct razor_transaction *
3.41 razor_transaction_create(struct razor_set *system, struct razor_set *upstream);
3.42 void razor_transaction_install_package(struct razor_transaction *transaction,
3.43 struct razor_package *package);
3.44 void razor_transaction_remove_package(struct razor_transaction *transaction,
3.45 struct razor_package *package);
3.46 +void razor_transaction_update_package(struct razor_transaction *trans,
3.47 + struct razor_package *package);
3.48 void razor_transaction_update_all(struct razor_transaction *transaction);
3.49 int razor_transaction_resolve(struct razor_transaction *trans);
3.50 struct razor_set *razor_transaction_finish(struct razor_transaction *trans);
3.51 @@ -156,7 +125,8 @@
3.52 int razor_transaction_unsatisfied_property(struct razor_transaction *trans,
3.53 const char *name,
3.54 enum razor_version_relation rel,
3.55 - const char *version);
3.56 + const char *version,
3.57 + enum razor_property_type type);
3.58
3.59 /* Importer interface; for building a razor set from external sources,
3.60 * like yum, rpmdb or razor package files. */
4.1 --- a/rpm-razor.c Wed Jun 04 21:28:26 2008 -0400
4.2 +++ b/rpm-razor.c Mon Jun 09 12:47:37 2008 -0400
4.3 @@ -350,6 +350,8 @@
4.4 return razor_package_query_finish(query);
4.5 }
4.6
4.7 +static const char *relation_string[] = { "<", "<=", "=", ">=", ">" };
4.8 +
4.9 static void
4.10 print_package_properties(struct razor_set *set,
4.11 struct razor_package *package,
4.12 @@ -371,7 +373,7 @@
4.13 printf("%s\n", name);
4.14 else
4.15 printf("%s %s %s\n", name,
4.16 - razor_version_relations[relation], version);
4.17 + relation_string[relation], version);
4.18 }
4.19 razor_property_iterator_destroy(pi);
4.20 }
4.21 @@ -518,7 +520,6 @@
4.22 next = razor_transaction_finish(trans);
4.23 razor_set_destroy(set);
4.24
4.25 - razor_set_list_unsatisfied(next);
4.26 razor_set_destroy(next);
4.27 }
4.28
4.29 @@ -551,8 +552,6 @@
4.30 razor_set_destroy(set);
4.31 razor_set_destroy(upstream);
4.32
4.33 - razor_set_list_unsatisfied(next);
4.34 -
4.35 razor_set_destroy(next);
4.36 }
4.37
5.1 --- a/test-driver.c Wed Jun 04 21:28:26 2008 -0400
5.2 +++ b/test-driver.c Mon Jun 09 12:47:37 2008 -0400
5.3 @@ -204,15 +204,17 @@
5.4 enum razor_version_relation rel,
5.5 const char *version)
5.6 {
5.7 + static const char *relation_string[] = { "<", "<=", "=", ">=", ">" };
5.8 +
5.9 if (!version)
5.10 version = "";
5.11
5.12 if (razor_transaction_unsatisfied_property(ctx->trans,
5.13 - name, rel, version))
5.14 + name, rel, version, type))
5.15 return;
5.16
5.17 fprintf(stderr, " didn't get unsatisfiable '%s %s %s'\n",
5.18 - name, razor_version_relations[rel], version);
5.19 + name, relation_string[rel], version);
5.20 ctx->errors++;
5.21 }
5.22
6.1 --- a/types.c Wed Jun 04 21:28:26 2008 -0400
6.2 +++ b/types.c Mon Jun 09 12:47:37 2008 -0400
6.3 @@ -244,34 +244,3 @@
6.4
6.5 return hashtable_insert(table, string);
6.6 }
6.7 -
6.8 -
6.9 -void
6.10 -bitarray_init(struct bitarray *bitarray, int size, int initial_value)
6.11 -{
6.12 - int bytes = ((size + 31) / 32) * 4;
6.13 -
6.14 - bitarray->bits = malloc(bytes);
6.15 - memset(bitarray->bits, initial_value ? 0xff : 0x00, bytes);
6.16 -}
6.17 -
6.18 -void
6.19 -bitarray_release(struct bitarray *bitarray)
6.20 -{
6.21 - free(bitarray->bits);
6.22 -}
6.23 -
6.24 -void
6.25 -bitarray_set(struct bitarray *bitarray, int bit, int value)
6.26 -{
6.27 - if (value)
6.28 - bitarray->bits[bit >> 5] |= 1 << (bit & 31);
6.29 - else
6.30 - bitarray->bits[bit >> 5] &= ~(1 << (bit & 31));
6.31 -}
6.32 -
6.33 -int
6.34 -bitarray_get(struct bitarray *bitarray, int bit)
6.35 -{
6.36 - return (bitarray->bits[bit >> 5] & (1 << (bit & 31))) != 0;
6.37 -}