summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorTimo Teräs <timo.teras@iki.fi>2012-02-27 16:35:04 +0200
committerTimo Teräs <timo.teras@iki.fi>2012-02-27 16:35:04 +0200
commitb7a22e555f7d287edec0ae7c816de16ca74d2941 (patch)
tree88efaea460abd666ec1ecbbf54ad50c854919dea
parent1074c4d32680e2a80dc2e2266f8499bbba6acbc0 (diff)
downloadapk-tools-b7a22e555f7d287edec0ae7c816de16ca74d2941.tar.gz
apk-tools-b7a22e555f7d287edec0ae7c816de16ca74d2941.tar.bz2
apk-tools-b7a22e555f7d287edec0ae7c816de16ca74d2941.tar.xz
apk-tools-b7a22e555f7d287edec0ae7c816de16ca74d2941.zip
solver, test: implements more provides things, add tests
ref #574
-rw-r--r--src/apk_blob.h1
-rw-r--r--src/blob.c7
-rw-r--r--src/solver.c122
-rw-r--r--test/provides.repo44
-rw-r--r--test/provides1.test7
-rw-r--r--test/provides2.test9
-rw-r--r--test/provides3.test6
-rw-r--r--test/provides4.test5
8 files changed, 168 insertions, 33 deletions
diff --git a/src/apk_blob.h b/src/apk_blob.h
index 23bff3f..e22a2f4 100644
--- a/src/apk_blob.h
+++ b/src/apk_blob.h
@@ -27,6 +27,7 @@ struct apk_blob {
};
typedef struct apk_blob apk_blob_t;
typedef int (*apk_blob_cb)(void *ctx, apk_blob_t blob);
+extern apk_blob_t apk_null_blob;
#define BLOB_FMT "%.*s"
#define BLOB_PRINTF(b) (int)(b).len, (b).ptr
diff --git a/src/blob.c b/src/blob.c
index 0a7643d..a03c66a 100644
--- a/src/blob.c
+++ b/src/blob.c
@@ -609,7 +609,8 @@ static struct apk_hash_ops atom_ops = {
.compare = apk_blob_compare,
.delete_item = (apk_hash_delete_f) free,
};
-static apk_blob_t null_blob = {0,0};
+
+apk_blob_t apk_null_blob = {0,0};
void apk_atom_init(void)
{
@@ -622,7 +623,7 @@ apk_blob_t *apk_blob_atomize(apk_blob_t blob)
unsigned long hash = apk_hash_from_key(&atom_hash, blob);
if (blob.len < 0 || blob.ptr == NULL)
- return &null_blob;
+ return &apk_null_blob;
atom = (struct apk_blob_atom *) apk_hash_get_hashed(&atom_hash, blob, hash);
if (atom != NULL)
@@ -642,7 +643,7 @@ apk_blob_t *apk_blob_atomize_dup(apk_blob_t blob)
char *ptr;
if (blob.len < 0 || blob.ptr == NULL)
- return &null_blob;
+ return &apk_null_blob;
atom = (struct apk_blob_atom *) apk_hash_get_hashed(&atom_hash, blob, hash);
if (atom != NULL)
return &atom->blob;
diff --git a/src/solver.c b/src/solver.c
index 11c1862..50bea4c 100644
--- a/src/solver.c
+++ b/src/solver.c
@@ -29,7 +29,7 @@
#if defined(DEBUG_PRINT) || defined(DEBUG_CHECKS)
#define ASSERT(cond, fmt...) \
- if (!(cond)) { fprintf(stderr, fmt); *(char*)NULL = 0; }
+ if (!(cond)) { apk_error(fmt); *(char*)NULL = 0; }
#else
#define ASSERT(cond, fmt...)
#endif
@@ -567,8 +567,6 @@ static void sort_name(struct apk_solver_state *ss, struct apk_name *name)
struct apk_name_state *ns = name_to_ns_alloc(name);
int i, j;
- count_name(ss, name);
-
for (i = 0; i < name->providers->num; i++) {
struct apk_package *pkg = name->providers->item[i].pkg;
struct apk_package_state *ps = pkg_to_ps_alloc(pkg);
@@ -802,6 +800,9 @@ static solver_result_t apply_decision(struct apk_solver_state *ss,
PKG_VER_PRINTF(pkg),
(d->type == DECISION_ASSIGN) ? "ASSIGN" : "EXCLUDE");
+ for (i = 0; i < pkg->provides->num; i++)
+ name_to_ns(pkg->provides->item[i].name)->name_touched = 1;
+
ps->locked = 1;
ps->handle_install_if = 0;
@@ -930,7 +931,7 @@ static solver_result_t push_decision(struct apk_solver_state *ss,
struct apk_decision *d;
ASSERT(ss->num_decisions <= ss->max_decisions,
- "Decision tree overflow.\n");
+ "Decision tree overflow.");
ss->num_decisions++;
d = &ss->decisions[ss->num_decisions];
@@ -967,11 +968,11 @@ static int next_branch(struct apk_solver_state *ss)
#ifdef DEBUG_CHECKS
ASSERT(cmpscore(&d->saved_score, &ss->score) == 0,
- "ERROR! saved_score "SCORE_FMT" != score "SCORE_FMT"\n",
+ "ERROR! saved_score "SCORE_FMT" != score "SCORE_FMT,
SCORE_PRINTF(&d->saved_score),
SCORE_PRINTF(&ss->score));
ASSERT(d->saved_requirers == ns->requirers,
- "ERROR! requirers not restored between decisions\n");
+ "ERROR! requirers not restored between decisions");
#endif
if (backup_until >= ss->num_decisions &&
@@ -1043,8 +1044,9 @@ static void apply_constraint(struct apk_solver_state *ss, struct apk_dependency
ps0->conflicts);
changed |= 1;
} else if (requirer_pkg != NULL) {
- dbg_printf("%s: inheriting flags and pinning from %s\n",
- name->name, name0->name);
+ dbg_printf(PKG_VER_FMT ": inheriting flags and pinning from"PKG_VER_FMT"\n",
+ PKG_VER_PRINTF(pkg0),
+ PKG_VER_PRINTF(requirer_pkg));
changed |= inherit_package_state(ss->db, pkg0, requirer_pkg);
}
}
@@ -1107,8 +1109,9 @@ static void undo_constraint(struct apk_solver_state *ss, struct apk_dependency *
PKG_VER_PRINTF(pkg0),
ps0->conflicts);
} else if (requirer_pkg != NULL) {
- dbg_printf("%s: uninheriting flags and pinning from %s\n",
- name->name, name0->name);
+ dbg_printf(PKG_VER_FMT ": uninheriting flags and pinning from "PKG_VER_FMT"\n",
+ PKG_VER_PRINTF(pkg0),
+ PKG_VER_PRINTF(requirer_pkg));
uninherit_package_state(ss->db, pkg0, requirer_pkg);
}
}
@@ -1139,7 +1142,7 @@ static int reconsider_name(struct apk_solver_state *ss, struct apk_name *name)
if (cmpscore2(&ss->score, &minscore, &ss->best_score) >= 0) {
dbg_printf("%s: pruning none, score too high "SCORE_FMT"+"SCORE_FMT">="SCORE_FMT"\n",
name->name,
- SCORE_PRINTF(&score),
+ SCORE_PRINTF(&ss->score),
SCORE_PRINTF(&minscore),
SCORE_PRINTF(&ss->best_score));
return push_decision(ss, name, NULL, DECISION_EXCLUDE, BRANCH_NO, FALSE);
@@ -1180,7 +1183,7 @@ static int reconsider_name(struct apk_solver_state *ss, struct apk_name *name)
if (ns->none_excluded)
return SOLVERR_PRUNED;
return push_decision(ss, name, NULL, DECISION_ASSIGN, BRANCH_NO, FALSE);
- } else if (options == 1 && score_locked && ns->none_excluded) {
+ } else if (options == 1 && score_locked && ns->none_excluded && name == next_p->pkg->name) {
dbg_printf("reconsider_name: %s: only one choice left with known score, locking.\n",
name->name);
return push_decision(ss, name, next_p->pkg, DECISION_ASSIGN, BRANCH_NO, FALSE);
@@ -1188,15 +1191,15 @@ static int reconsider_name(struct apk_solver_state *ss, struct apk_name *name)
ns->chosen = *next_p;
- dbg_printf("reconsider_name: %s: min penalty " SCORE_FMT ", next_pkg=%p\n",
- name->name, SCORE_PRINTF(&minscore), next_p->pkg);
+ dbg_printf("reconsider_name: %s: next_pkg=%p [ version="BLOB_FMT" ]\n",
+ name->name, next_p->pkg, BLOB_PRINTF(*ns->chosen.version));
return SOLVERR_SOLUTION;
}
static int expand_branch(struct apk_solver_state *ss)
{
- struct apk_name *name;
+ struct apk_name *name0, *name;
struct apk_name_state *ns;
struct apk_package *pkg0 = NULL;
struct apk_package_state *ps0;
@@ -1204,6 +1207,7 @@ static int expand_branch(struct apk_solver_state *ss)
unsigned short allowed_pinning, preferred_pinning;
unsigned int allowed_repos;
int primary_decision, branching_point;
+ int can_install = FALSE;
list_for_each_entry(ns, &ss->unsolved_list_head, unsolved_list) {
name = ns->name;
@@ -1216,10 +1220,22 @@ static int expand_branch(struct apk_solver_state *ss)
ns->name_touched = 0;
}
if (pkg_to_ps(ns->chosen.pkg)->topology_soft < ss->topology_position &&
- pkg_to_ps(ns->chosen.pkg)->topology_soft > topology0)
- pkg0 = ns->chosen.pkg, topology0 = pkg_to_ps(pkg0)->topology_soft;
- else if (ns->chosen.pkg->topology_hard > topology0)
- pkg0 = ns->chosen.pkg, topology0 = pkg0->topology_hard;
+ pkg_to_ps(ns->chosen.pkg)->topology_soft >= topology0) {
+ topology0 = pkg_to_ps(ns->chosen.pkg)->topology_soft;
+ } else if (ns->chosen.pkg->topology_hard >= topology0) {
+ topology0 = ns->chosen.pkg->topology_hard;
+ } else {
+ continue;
+ }
+ if (pkg0 != ns->chosen.pkg) {
+ can_install = FALSE;
+ name0 = name;
+ }
+ pkg0 = ns->chosen.pkg;
+ if (ns->chosen.version != &apk_null_blob) {
+ can_install |= TRUE;
+ name0 = name;
+ }
}
if (pkg0 == NULL) {
dbg_printf("expand_branch: solution with score "SCORE_FMT"\n",
@@ -1230,7 +1246,7 @@ static int expand_branch(struct apk_solver_state *ss)
/* someone needs to provide this name -- find next eligible
* provider candidate */
ps0 = pkg_to_ps(pkg0);
- name = pkg0->name;
+ name = name0;
ns = name_to_ns(name);
if (!ns->none_excluded) {
@@ -1242,10 +1258,14 @@ static int expand_branch(struct apk_solver_state *ss)
return push_decision(ss, name, NULL, primary_decision, BRANCH_YES, FALSE);
}
- dbg_printf("expand_branch: "PKG_VER_FMT" score: "SCORE_FMT"\tminpenalty: "SCORE_FMT"\tbest: "SCORE_FMT"\n",
+ if (!can_install) {
+ /* provides with no version; not eglible to auto install */
+ return push_decision(ss, pkg0->name, pkg0, DECISION_EXCLUDE, BRANCH_NO, TRUE);
+ }
+
+ dbg_printf("expand_branch: "PKG_VER_FMT" score: "SCORE_FMT"\tbest: "SCORE_FMT"\n",
PKG_VER_PRINTF(pkg0),
SCORE_PRINTF(&ss->score),
- SCORE_PRINTF(&ss->minimum_penalty),
SCORE_PRINTF(&ss->best_score));
preferred_pinning = ns->preferred_pinning ?: APK_DEFAULT_PINNING_MASK;
@@ -1327,7 +1347,7 @@ static void record_solution(struct apk_solver_state *ss)
pinning = ps->allowed_pinning | ns->preferred_pinning | APK_DEFAULT_PINNING_MASK;
repos = pkg->repos | (pkg->ipkg ? db->repo_tags[pkg->ipkg->repository_tag].allowed_repos : 0);
- ASSERT(n < ss->assigned_names, "Name assignment overflow\n");
+ ASSERT(n < ss->assigned_names, "Name assignment overflow");
ss->best_solution->item[n++] = (struct apk_solution_entry){
.pkg = pkg,
.reinstall = ps->inherited_reinstall ||
@@ -1438,7 +1458,7 @@ static int free_state(apk_hash_item item, void *ctx)
if (ns != NULL) {
#ifdef DEBUG_CHECKS
- ASSERT(ns->requirers == 0, "Requirers is not zero after cleanup\n");
+ ASSERT(ns->requirers == 0, "Requirers is not zero after cleanup");
#endif
free(ns);
name->state_ptr = NULL;
@@ -1518,7 +1538,7 @@ int apk_solver_solve(struct apk_database *db,
if (r == SOLVERR_SOLUTION) {
if (cmpscore(&ss->score, &ss->best_score) < 0) {
dbg_printf("updating best score "SCORE_FMT" (was: "SCORE_FMT")\n",
- SCORE_PRINTF(&score),
+ SCORE_PRINTF(&ss->score),
SCORE_PRINTF(&ss->best_score));
record_solution(ss);
@@ -1888,7 +1908,27 @@ all_done:
return r;
}
-static void print_dep_errors(struct apk_database *db, char *label, struct apk_dependency_array *deps)
+static void add_name_if_virtual(struct apk_name_array **names, struct apk_name *name)
+{
+ int i;
+
+ if (name->state_int == 1)
+ return;
+ name->state_int = 1;
+
+ if (name->providers->num == 0)
+ return;
+
+ for (i = 0; i < name->providers->num; i++)
+ if (name->providers->item[i].pkg->name == name)
+ return;
+
+ *apk_name_array_add(names) = name;
+}
+
+static void print_dep_errors(struct apk_database *db, char *label,
+ struct apk_dependency_array *deps,
+ struct apk_name_array **names)
{
int i, print_label = 1;
char buf[256];
@@ -1902,6 +1942,9 @@ static void print_dep_errors(struct apk_database *db, char *label, struct apk_de
if (apk_dep_is_materialized_or_provided(dep, pkg))
continue;
+ if (pkg == NULL)
+ add_name_if_virtual(names, dep->name);
+
if (print_label) {
print_label = 0;
indent.x = printf(" %s:", label);
@@ -1921,8 +1964,11 @@ void apk_solver_print_errors(struct apk_database *db,
struct apk_dependency_array *world,
int unsatisfiable)
{
- int i;
+ struct apk_name_array *names;
+ char pkgtext[256];
+ int i, j;
+ apk_name_array_init(&names);
apk_error("%d unsatisfiable dependencies:", unsatisfiable);
for (i = 0; i < solution->num; i++) {
@@ -1930,13 +1976,29 @@ void apk_solver_print_errors(struct apk_database *db,
pkg->name->state_ptr = pkg;
}
- print_dep_errors(db, "world", world);
+ print_dep_errors(db, "world", world, &names);
for (i = 0; i < solution->num; i++) {
struct apk_package *pkg = solution->item[i].pkg;
- char pkgtext[256];
snprintf(pkgtext, sizeof(pkgtext), PKG_VER_FMT, PKG_VER_PRINTF(pkg));
- print_dep_errors(db, pkgtext, pkg->depends);
+ print_dep_errors(db, pkgtext, pkg->depends, &names);
+ }
+
+ for (i = 0; i < names->num; i++) {
+ struct apk_indent indent;
+ struct apk_name *name = names->item[i];
+
+ printf("\n %s is a virtual package provided by:\n ", name->name);
+ indent.x = 4;
+ indent.indent = 4;
+
+ for (j = 0; j < name->providers->num; j++) {
+ struct apk_package *pkg = name->providers->item[j].pkg;
+ snprintf(pkgtext, sizeof(pkgtext), PKG_VER_FMT, PKG_VER_PRINTF(pkg));
+ apk_print_indented(&indent, APK_BLOB_STR(pkgtext));
+ }
+ printf("\n");
}
+ apk_name_array_free(&names);
}
int apk_solver_commit(struct apk_database *db,
diff --git a/test/provides.repo b/test/provides.repo
new file mode 100644
index 0000000..73875f4
--- /dev/null
+++ b/test/provides.repo
@@ -0,0 +1,44 @@
+C:Q1EyN5AdpAOBJWKMR89pp/C66o+OE=
+P:libfoo
+V:1
+S:1
+I:1
+p:so:foo.so.1=1.0
+
+C:Q1eVpkasfqZAukAXFYbgwt4xAMZWU=
+P:app
+V:2
+S:1
+I:1
+D:so:foo.so.1
+
+C:Q1EyN5AdpAOBJWKMR89pp/C66FFFF=
+P:mymailreader
+V:1
+S:1
+I:1
+p:mail-reader
+
+C:Q1eVpkasfqZAukAXFYbgwt4xAEEEe=
+P:mailreadplus
+V:1
+S:1
+I:1
+p:mail-reader
+
+C:Q1EyN5AdpAOBJWKMR89pp/C77FFFF=
+P:server-a
+V:1
+S:1
+I:1
+p:theservice
+D:!theservice
+
+C:Q1eVpkasfqZAukAXFYbgwt444EEEe=
+P:server-b
+V:1
+S:1
+I:1
+p:theservice
+D:!theservice
+
diff --git a/test/provides1.test b/test/provides1.test
new file mode 100644
index 0000000..22b111a
--- /dev/null
+++ b/test/provides1.test
@@ -0,0 +1,7 @@
+@ARGS
+--test-repo provides.repo
+add app
+@EXPECT
+(1/2) Installing libfoo (1)
+(2/2) Installing app (2)
+OK: 0 MiB in 0 packages
diff --git a/test/provides2.test b/test/provides2.test
new file mode 100644
index 0000000..36a0637
--- /dev/null
+++ b/test/provides2.test
@@ -0,0 +1,9 @@
+@ARGS
+--test-repo provides.repo
+add mail-reader
+@EXPECT
+ERROR: 1 unsatisfiable dependencies:
+ world: mail-reader
+
+ mail-reader is a virtual package provided by:
+ mymailreader-1 mailreadplus-1
diff --git a/test/provides3.test b/test/provides3.test
new file mode 100644
index 0000000..8ab8af7
--- /dev/null
+++ b/test/provides3.test
@@ -0,0 +1,6 @@
+@ARGS
+--test-repo provides.repo
+add mail-reader mymailreader
+@EXPECT
+(1/1) Installing mymailreader (1)
+OK: 0 MiB in 0 packages
diff --git a/test/provides4.test b/test/provides4.test
new file mode 100644
index 0000000..daf6386
--- /dev/null
+++ b/test/provides4.test
@@ -0,0 +1,5 @@
+@ARGS
+--test-repo provides.repo
+add mymailreader mailreadplus
+@EXPECT
+