summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--.gitignore5
-rw-r--r--Makefile4
-rw-r--r--src/Makefile13
-rw-r--r--src/apk_package.h1
-rw-r--r--src/apk_solver.h33
-rw-r--r--src/solver.c563
-rw-r--r--src/test.c163
-rw-r--r--src/topology.c56
-rw-r--r--test/Makefile14
-rw-r--r--test/basic.installed13
-rw-r--r--test/basic.repo26
-rw-r--r--test/basic1.expect2
-rw-r--r--test/basic1.test1
-rw-r--r--test/basic2.expect0
-rw-r--r--test/basic2.test1
-rw-r--r--test/basic3.expect2
-rw-r--r--test/basic3.test1
-rw-r--r--test/basic4.expect1
-rw-r--r--test/basic4.test1
-rw-r--r--test/complicated1.expect4
-rw-r--r--test/complicated1.installed6
-rw-r--r--test/complicated1.repo46
-rw-r--r--test/complicated1.test1
-rw-r--r--test/complicated2.expect3
-rw-r--r--test/complicated2.test1
-rw-r--r--test/complicated3.expect2
-rw-r--r--test/complicated3.test1
-rw-r--r--test/complicated4.expect4
-rw-r--r--test/complicated4.test1
-rwxr-xr-xtest/solver.sh23
-rwxr-xr-xtest/version.sh6
31 files changed, 988 insertions, 10 deletions
diff --git a/.gitignore b/.gitignore
index 2b22f52..c0c96c7 100644
--- a/.gitignore
+++ b/.gitignore
@@ -1,5 +1,6 @@
-apk
-apk.static
+src/apk
+src/apk_test
+src/apk.static
*.o
*.d
*.cmd
diff --git a/Makefile b/Makefile
index 0af3b24..e1099cf 100644
--- a/Makefile
+++ b/Makefile
@@ -36,5 +36,9 @@ install:
$(INSTALLDIR) $(DESTDIR)$(DOCDIR)
$(INSTALL) README $(DESTDIR)$(DOCDIR)
+test: FORCE
+ $(Q)$(MAKE) TEST=y
+ $(Q)$(MAKE) -C test
+
static:
$(Q)$(MAKE) STATIC=y
diff --git a/src/Makefile b/src/Makefile
index deb6732..1f4e90e 100644
--- a/src/Makefile
+++ b/src/Makefile
@@ -23,7 +23,13 @@ apk-objs := apk.o add.o del.o fix.o update.o info.o \
audit.o verify.o dot.o
libapk.so-objs := common.o state.o database.o package.o archive.o \
- version.o io.o url.o gunzip.o blob.o hash.o print.o
+ version.o io.o url.o gunzip.o blob.o hash.o print.o \
+ solver.o topology.o
+
+ifeq ($(TEST),y)
+progs-y += apk_test
+apk_test-objs := apk.o test.o $(libapk.so-objs)
+endif
ifeq ($(SHARED_LIBAPK),)
apk-objs += $(libapk.so-objs)
@@ -47,15 +53,16 @@ progs-$(STATIC) += apk.static
apk.static-objs := $(filter-out apk.o,$(apk-objs)) apk-static.o
LDFLAGS_apk.static := -static
LDFLAGS_apk += -nopie -L$(obj)
+LDFLAGS_apk_test += -nopie -L$(obj)
CFLAGS_ALL += $(shell pkg-config --cflags $(PKGDEPS))
LIBS := -Wl,--as-needed \
$(shell pkg-config --libs $(PKGDEPS)) \
-Wl,--no-as-needed
-$(obj)/apk: $(LIBAPK-y)
+$(obj)/apk: $(LIBAPK-y)
-$(obj)/apk.so: $(obj)/libapk.so
+$(obj)/apk.so: $(obj)/libapk.so
install: $(obj)/apk $(LIBAPK-y) $(LUA_LIB-y)
$(INSTALLDIR) $(DESTDIR)$(SBINDIR)
diff --git a/src/apk_package.h b/src/apk_package.h
index 9802dfa..6c6c1bf 100644
--- a/src/apk_package.h
+++ b/src/apk_package.h
@@ -80,6 +80,7 @@ struct apk_installed_package {
struct apk_package {
apk_hash_node hash_node;
+ unsigned int topology_sort;
struct apk_name *name;
struct apk_installed_package *ipkg;
apk_blob_t *version, *arch, *license;
diff --git a/src/apk_solver.h b/src/apk_solver.h
new file mode 100644
index 0000000..27e3b93
--- /dev/null
+++ b/src/apk_solver.h
@@ -0,0 +1,33 @@
+/* apk_solver.h - Alpine Package Keeper (APK)
+ *
+ * Copyright (C) 2005-2008 Natanael Copa <n@tanael.org>
+ * Copyright (C) 2008 Timo Teräs <timo.teras@iki.fi>
+ * All rights reserved.
+ *
+ * This program is free software; you can redistribute it and/or modify it
+ * under the terms of the GNU General Public License version 2 as published
+ * by the Free Software Foundation. See http://www.gnu.org/ for details.
+ */
+
+#ifndef APK_SOLVER_H
+#define APK_SOLVER_H
+
+struct apk_change {
+ struct apk_package *oldpkg;
+ struct apk_package *newpkg;
+};
+APK_ARRAY(apk_change_array, struct apk_change);
+
+struct apk_changeset {
+ struct apk_change_array *changes;
+};
+
+void apk_solver_sort(struct apk_database *db);
+int apk_solver_solve(struct apk_database *db, struct apk_dependency_array *world,
+ struct apk_package_array **solution);
+int apk_solver_generate_changeset(struct apk_database *db,
+ struct apk_package_array *solution,
+ struct apk_changeset *changeset);
+
+#endif
+
diff --git a/src/solver.c b/src/solver.c
new file mode 100644
index 0000000..71cdccc
--- /dev/null
+++ b/src/solver.c
@@ -0,0 +1,563 @@
+/* solver.c - Alpine Package Keeper (APK)
+ * A backtracking, forward checking dependency graph solver.
+ *
+ * Copyright (C) 2011 Timo Teräs <timo.teras@iki.fi>
+ * All rights reserved.
+ *
+ * This program is free software; you can redistribute it and/or modify it
+ * under the terms of the GNU General Public License version 2 as published
+ * by the Free Software Foundation. See http://www.gnu.org/ for details.
+ */
+
+/* FIXME: install-if not supported yet */
+
+#include <stdlib.h>
+#include "apk_defines.h"
+#include "apk_database.h"
+#include "apk_package.h"
+#include "apk_solver.h"
+
+#if 0
+#include <stdio.h>
+#define dbg_printf(args...) fprintf(stderr, args)
+#else
+#define dbg_printf(args...)
+#endif
+
+#define APK_PKGSTF_NOINSTALL 0
+#define APK_PKGSTF_INSTALL 1
+#define APK_PKGSTF_BRANCH 2
+#define APK_PKGSTF_ALT_BRANCH 4
+
+struct apk_package_state {
+ struct apk_package *backtrack;
+ unsigned short flags;
+ unsigned short conflicts;
+};
+
+struct apk_name_state {
+ struct list_head unsolved_list;
+ struct apk_package *chosen;
+ struct apk_package *preferred;
+ unsigned short requirers;
+};
+
+struct apk_solver_state {
+ struct apk_database *db;
+ struct apk_package_state *pkg_state;
+ struct apk_name_state *name_state;
+ struct list_head unsolved_list_head;
+ struct apk_package *latest_decision;
+ unsigned int topology_position;
+ unsigned int assigned_names;
+
+ struct apk_package_array *best_solution;
+ unsigned int best_cost;
+};
+
+static int apply_constraint(struct apk_solver_state *ss, struct apk_dependency *dep);
+static int undo_constraint(struct apk_solver_state *ss, struct apk_dependency *dep);
+static int push_decision(struct apk_solver_state *ss, struct apk_package *pkg,
+ int flags);
+
+static inline int pkg_available(struct apk_database *db, struct apk_package *pkg)
+{
+ if (pkg->ipkg != NULL)
+ return TRUE;
+ if (pkg->installed_size == 0)
+ return TRUE;
+ if (pkg->filename != NULL)
+ return TRUE;
+ if (apk_db_select_repo(db, pkg) != NULL)
+ return TRUE;
+ return FALSE;
+}
+
+static int foreach_dependency(struct apk_solver_state *ss, struct apk_dependency_array *deps,
+ int (*func)(struct apk_solver_state *ss, struct apk_dependency *dep))
+{
+ int i, r = 0;
+ for (i = 0; i < deps->num; i++)
+ r += func(ss, &deps->item[i]);
+ return r;
+}
+
+static void calculate_preferred(struct apk_database *db,
+ struct apk_name *name,
+ struct apk_name_state *ns)
+{
+ struct apk_package *installed = NULL, *latest = NULL;
+ int i;
+
+ /* Get latest and installed packages */
+ for (i = 0; i < name->pkgs->num; i++) {
+ struct apk_package *pkg = name->pkgs->item[i];
+
+ if (pkg->ipkg != NULL)
+ installed = pkg;
+ else if (!pkg_available(db, pkg))
+ continue;
+ if (latest == NULL) {
+ latest = pkg;
+ continue;
+ }
+
+ if ((apk_flags & APK_PREFER_AVAILABLE) ||
+ (name->flags & APK_NAME_REINSTALL)) {
+ if (latest->repos != 0 && pkg->repos == 0)
+ continue;
+ if (latest->repos == 0 && pkg->repos != 0) {
+ latest = pkg;
+ continue;
+ }
+ /* Otherwise both are not available, or both are
+ * available and we just compare the versions then */
+ }
+ if (apk_pkg_version_compare(pkg, latest) == APK_VERSION_GREATER)
+ latest = pkg;
+ }
+
+ /* Choose the best looking candidate. */
+ if (apk_flags & APK_UPGRADE) {
+ ns->preferred = latest;
+ } else {
+ if (installed != NULL &&
+ (installed->repos != 0 ||
+ !(name->flags & APK_NAME_REINSTALL)))
+ ns->preferred = installed;
+ else
+ ns->preferred = latest;
+ }
+
+}
+
+static int update_name_state(struct apk_solver_state *ss,
+ struct apk_name *name, struct apk_name_state *ns)
+{
+ struct apk_package *pkg_best = NULL;
+ int i, options = 0;
+
+ for (i = 0; i < name->pkgs->num; i++) {
+ struct apk_package *pkg0 = name->pkgs->item[i];
+ struct apk_package_state *ps0 = &ss->pkg_state[pkg0->topology_sort];
+
+ if (pkg0->topology_sort >= ss->topology_position ||
+ ps0->conflicts != 0)
+ continue;
+
+ options++;
+ if (pkg_best == NULL ||
+ pkg0->topology_sort > pkg_best->topology_sort)
+ pkg_best = pkg0;
+ }
+ ns->chosen = pkg_best;
+ dbg_printf("%s: adjusted preference %d -> %d (options left %d)\n",
+ name->name, ss->topology_position, ns->chosen->topology_sort,
+ options);
+ return options;
+}
+
+static int apply_decision(struct apk_solver_state *ss,
+ struct apk_package *pkg,
+ struct apk_package_state *ps)
+{
+ struct apk_name_state *ns = &ss->name_state[pkg->name->id];
+
+ dbg_printf("apply_decision: " PKG_VER_FMT " %s\n", PKG_VER_PRINTF(pkg),
+ (ps->flags & APK_PKGSTF_INSTALL) ? "INSTALL" : "NO_INSTALL");
+
+ if (ps->flags & APK_PKGSTF_INSTALL) {
+ ss->assigned_names++;
+ ns->chosen = pkg;
+ if (list_hashed(&ns->unsolved_list)) {
+ list_del(&ns->unsolved_list);
+ list_init(&ns->unsolved_list);
+ dbg_printf("%s: deleting from unsolved list\n",
+ pkg->name->name);
+ }
+ return foreach_dependency(ss, pkg->depends, apply_constraint);
+ } else {
+ if (!list_hashed(&ns->unsolved_list)) {
+ ns->chosen = NULL;
+ return 0;
+ }
+ if (update_name_state(ss, pkg->name, ns) != 1)
+ return 0;
+ /* the name is required and we are left with only one candidate
+ * after deciding to not install pkg; autoselect the last option */
+ return push_decision(ss, ns->chosen, APK_PKGSTF_INSTALL);
+ }
+}
+
+static void undo_decision(struct apk_solver_state *ss,
+ struct apk_package *pkg,
+ struct apk_package_state *ps)
+{
+ struct apk_name_state *ns = &ss->name_state[pkg->name->id];
+
+ dbg_printf("undo_decision: " PKG_VER_FMT " %s\n", PKG_VER_PRINTF(pkg),
+ (ps->flags & APK_PKGSTF_INSTALL) ? "INSTALL" : "NO_INSTALL");
+
+ if (ps->flags & APK_PKGSTF_INSTALL) {
+ ss->assigned_names--;
+ foreach_dependency(ss, pkg->depends, undo_constraint);
+
+ if (ns->requirers) {
+ list_add(&ns->unsolved_list, &ss->unsolved_list_head);
+ dbg_printf("%s: adding back to unsolved list (requirers: %d)\n",
+ pkg->name->name, ns->requirers);
+ } else {
+ ns->chosen = NULL;
+ }
+ }
+}
+
+static int push_decision(struct apk_solver_state *ss, struct apk_package *pkg,
+ int flags)
+{
+ struct apk_package_state *ps = &ss->pkg_state[pkg->topology_sort];
+
+ ps->backtrack = ss->latest_decision;
+ ps->flags = flags;
+ ss->latest_decision = pkg;
+ if (flags & APK_PKGSTF_BRANCH) {
+ ss->topology_position = pkg->topology_sort;
+ dbg_printf("push_decision: adding new BRANCH at topology_position %d\n",
+ ss->topology_position);
+ } else
+ ps->flags |= APK_PKGSTF_ALT_BRANCH;
+
+ return apply_decision(ss, pkg, ps);
+}
+
+static int next_branch(struct apk_solver_state *ss)
+{
+ struct apk_package *pkg;
+ struct apk_package_state *ps;
+ int r;
+
+ while (1) {
+ pkg = ss->latest_decision;
+ ps = &ss->pkg_state[pkg->topology_sort];
+ undo_decision(ss, pkg, ps);
+
+ if (ps->flags & APK_PKGSTF_ALT_BRANCH) {
+ pkg = ps->backtrack;
+ ss->latest_decision = pkg;
+ if (pkg == NULL) /* at root, can't back track */
+ return 1;
+ ss->topology_position = pkg->topology_sort;
+ dbg_printf("next_branch: undo decision at topology_position %d\n",
+ ss->topology_position);
+ } else {
+ dbg_printf("next_branch: swapping BRANCH at topology_position %d\n",
+ ss->topology_position);
+
+ ps->flags |= APK_PKGSTF_ALT_BRANCH;
+ ps->flags ^= APK_PKGSTF_INSTALL;
+
+ r = apply_decision(ss, pkg, ps);
+ if (r == 0 /*|| report_errors */)
+ return r;
+ }
+ }
+}
+
+static int apply_constraint(struct apk_solver_state *ss, struct apk_dependency *dep)
+{
+ struct apk_name *name = dep->name;
+ struct apk_name_state *ns = &ss->name_state[name->id];
+ struct apk_package *pkg_best = NULL;
+ int i, options = 0;
+
+ for (i = 0; i < name->pkgs->num; i++) {
+ struct apk_package *pkg0 = name->pkgs->item[i];
+ struct apk_package_state *ps0 = &ss->pkg_state[pkg0->topology_sort];
+
+ if (pkg0->topology_sort >= ss->topology_position) {
+ dbg_printf(PKG_VER_FMT ": topology skip %d > %d\n",
+ PKG_VER_PRINTF(pkg0),
+ pkg0->topology_sort, ss->topology_position);
+ continue;
+ }
+
+ if (!apk_dep_is_satisfied(dep, pkg0)) {
+ ps0->conflicts++;
+ dbg_printf(PKG_VER_FMT ": conflicts++ -> %d\n",
+ PKG_VER_PRINTF(pkg0),
+ ps0->conflicts);
+ }
+ if (ps0->conflicts == 0) {
+ options++;
+ if (pkg_best == NULL ||
+ pkg0->topology_sort > pkg_best->topology_sort)
+ pkg_best = pkg0;
+ }
+ }
+
+ ns->requirers++;
+ if (!list_hashed(&ns->unsolved_list) && ns->chosen != NULL) {
+ dbg_printf(PKG_VER_FMT " selected already for %s\n", PKG_VER_PRINTF(ns->chosen),
+ dep->name->name);
+ return !apk_dep_is_satisfied(dep, ns->chosen);
+ }
+
+ ns->chosen = pkg_best;
+ if (options == 0) {
+ /* we conflicted with all possible options */
+ if (list_hashed(&ns->unsolved_list)) {
+ dbg_printf("%s: deleting unsolved (unable to satisfy)\n",
+ name->name);
+ list_del(&ns->unsolved_list);
+ list_init(&ns->unsolved_list);
+ }
+ return 1;
+ }
+ if (options == 1) {
+ /* we can short circuit to select the only option
+ * possible */
+ return push_decision(ss, pkg_best, APK_PKGSTF_INSTALL);
+ }
+ /* multiple ways to satisfy the requirement */
+ if (ns->requirers == 1) {
+ list_init(&ns->unsolved_list);
+ list_add(&ns->unsolved_list, &ss->unsolved_list_head);
+ dbg_printf("%s: adding to unsolved list (%d options)\n",
+ name->name, options);
+ }
+
+ return 0;
+}
+
+static int undo_constraint(struct apk_solver_state *ss, struct apk_dependency *dep)
+{
+ struct apk_name *name = dep->name;
+ struct apk_name_state *ns = &ss->name_state[name->id];
+ struct apk_package *pkg_best = NULL;
+ int i, had_options = 0, options = 0;
+
+ for (i = 0; i < name->pkgs->num; i++) {
+ struct apk_package *pkg0 = name->pkgs->item[i];
+ struct apk_package_state *ps0 = &ss->pkg_state[pkg0->topology_sort];
+
+ if (pkg0->topology_sort >= ss->topology_position)
+ continue;
+
+ if (ps0->conflicts == 0)
+ had_options++;
+ if (!apk_dep_is_satisfied(dep, pkg0)) {
+ ps0->conflicts--;
+ dbg_printf(PKG_VER_FMT ": conflicts-- -> %d\n",
+ PKG_VER_PRINTF(pkg0),
+ ps0->conflicts);
+ }
+ if (ps0->conflicts == 0) {
+ options++;
+ if (pkg_best == NULL ||
+ pkg0->topology_sort > pkg_best->topology_sort)
+ pkg_best = pkg0;
+ }
+ }
+
+ ns->requirers--;
+
+ if (ns->requirers == 0) {
+ if (list_hashed(&ns->unsolved_list)) {
+ list_del(&ns->unsolved_list);
+ list_init(&ns->unsolved_list);
+ ns->chosen = NULL;
+ }
+ } else {
+ ns->chosen = pkg_best;
+ if (had_options == 0 && options != 0) {
+ if (!list_hashed(&ns->unsolved_list)) {
+ list_add(&ns->unsolved_list, &ss->unsolved_list_head);
+ dbg_printf("%s: adding back to unsolved list (with %d options, %d requirers)\n",
+ name->name, options, ns->requirers);
+ } else {
+ ns->chosen = NULL;
+ }
+ return 0;
+ }
+ }
+ return 0;
+}
+
+static int expand_branch(struct apk_solver_state *ss)
+{
+ int r;
+
+ while (1) {
+ struct apk_name_state *ns;
+ struct apk_package *pkg0 = NULL;
+
+ /* FIXME: change unsolved_list to a priority queue */
+ list_for_each_entry(ns, &ss->unsolved_list_head, unsolved_list) {
+ if (pkg0 == NULL ||
+ ns->chosen->topology_sort > pkg0->topology_sort)
+ pkg0 = ns->chosen;
+ }
+ if (pkg0 == NULL) {
+ dbg_printf("expand_branch: list is empty\n");
+ return 0;
+ }
+
+ /* someone needs to provide this name -- find next eligible
+ * provider candidate */
+ ns = &ss->name_state[pkg0->name->id];
+ dbg_printf("expand_branch: %s %d\n", pkg0->name->name, pkg0->topology_sort);
+
+ /* Is there something we can still use? */
+ if (ns->preferred == NULL)
+ calculate_preferred(ss->db, pkg0->name, ns);
+
+ r = push_decision(ss, pkg0,
+ (pkg0 == ns->preferred) ?
+ (APK_PKGSTF_INSTALL | APK_PKGSTF_BRANCH) :
+ (APK_PKGSTF_NOINSTALL | APK_PKGSTF_BRANCH));
+
+ if (/*no_error_reporting &&*/ r)
+ return r;
+ }
+
+ return 0;
+}
+
+static void record_solution(struct apk_solver_state *ss)
+{
+ struct apk_package *pkg;
+ struct apk_package_state *ps;
+ int i;
+
+ apk_package_array_resize(&ss->best_solution, ss->assigned_names);
+
+ i = 0;
+ pkg = ss->latest_decision;
+ while (pkg != NULL) {
+ ps = &ss->pkg_state[pkg->topology_sort];
+ if (ps->flags & APK_PKGSTF_INSTALL)
+ ss->best_solution->item[i++] = pkg;
+
+ dbg_printf("record_solution: " PKG_VER_FMT ": %sINSTALL\n",
+ PKG_VER_PRINTF(pkg),
+ (ps->flags & APK_PKGSTF_INSTALL) ? "" : "NO_");
+
+ pkg = ps->backtrack;
+ }
+}
+
+int apk_solver_solve(struct apk_database *db, struct apk_dependency_array *world,
+ struct apk_package_array **solution)
+{
+ struct apk_solver_state *ss;
+ int r;
+
+ ss = calloc(1, sizeof(struct apk_solver_state));
+ ss->db = db;
+ ss->topology_position = -1;
+ list_init(&ss->unsolved_list_head);
+ ss->pkg_state = calloc(db->available.packages.num_items+1, sizeof(struct apk_package_state));
+ ss->name_state = calloc(db->available.names.num_items+1, sizeof(struct apk_name_state));
+
+ r = foreach_dependency(ss, world, apply_constraint);
+ while (r == 0) {
+ if (expand_branch(ss) == 0) {
+ /* found solution*/
+ /* FIXME: we should check other permutations if they
+ * have smaller cost to find optimal changeset */
+ break;
+ } else {
+ /* conflicting constraints -- backtrack */
+ r = next_branch(ss);
+ }
+ }
+
+ /* collect packages */
+ if (r == 0) {
+ record_solution(ss);
+ *solution = ss->best_solution;
+ }
+
+ free(ss->name_state);
+ free(ss->pkg_state);
+ free(ss);
+
+ return r;
+}
+
+static int compare_change(const void *p1, const void *p2)
+{
+ const struct apk_change *c1 = (const struct apk_change *) p1;
+ const struct apk_change *c2 = (const struct apk_change *) p2;
+
+ if (c1->newpkg == NULL) {
+ if (c2->newpkg == NULL)
+ /* both deleted - reverse topology order */
+ return c1->oldpkg->topology_sort - c2->oldpkg->topology_sort;
+
+ /* c1 deleted, c2 installed -> c2 first*/
+ return -1;
+ }
+ if (c2->newpkg == NULL)
+ /* c1 installed, c2 deleted -> c1 first*/
+ return 1;
+
+ return c2->newpkg->topology_sort - c1->newpkg->topology_sort;
+}
+
+int apk_solver_generate_changeset(struct apk_database *db,
+ struct apk_package_array *solution,
+ struct apk_changeset *changeset)
+{
+ struct apk_name *name;
+ struct apk_package *pkg, *pkg0;
+ struct apk_installed_package *ipkg;
+ int num_installs = 0, num_removed = 0, ci = 0;
+ int i, j;
+
+ /* calculate change set size */
+ for (i = 0; i < solution->num; i++) {
+ pkg = solution->item[i];
+ name = pkg->name;
+ if (pkg->ipkg == NULL || (name->flags & APK_NAME_REINSTALL))
+ num_installs++;
+ name->flags |= APK_NAME_VISITED;
+ }
+
+ list_for_each_entry(ipkg, &db->installed.packages, installed_pkgs_list) {
+ if (!(ipkg->pkg->name->flags & APK_NAME_VISITED))
+ num_removed++;
+ }
+
+ /* construct changeset */
+ apk_change_array_resize(&changeset->changes, num_installs + num_removed);
+ list_for_each_entry(ipkg, &db->installed.packages, installed_pkgs_list) {
+ if (ipkg->pkg->name->flags & APK_NAME_VISITED)
+ continue;
+ changeset->changes->item[ci].oldpkg = ipkg->pkg;
+ ci++;
+ }
+ for (i = 0; i < solution->num; i++) {
+ pkg = solution->item[i];
+ name = pkg->name;
+
+ if (pkg->ipkg == NULL || (name->flags & APK_NAME_REINSTALL)) {
+ for (j = 0; j < name->pkgs->num; j++) {
+ pkg0 = name->pkgs->item[j];
+ if (pkg0->ipkg == NULL)
+ continue;
+ changeset->changes->item[ci].oldpkg = pkg0;
+ break;
+ }
+ changeset->changes->item[ci].newpkg = pkg;
+ ci++;
+ }
+ name->flags &= ~APK_NAME_VISITED;
+ }
+
+ /* sort changeset to topology order */
+ qsort(changeset->changes->item, changeset->changes->num,
+ sizeof(struct apk_change), compare_change);
+
+ return 0;
+}
diff --git a/src/test.c b/src/test.c
new file mode 100644
index 0000000..b074de8
--- /dev/null
+++ b/src/test.c
@@ -0,0 +1,163 @@
+/* test.c - Alpine Package Keeper (APK)
+ *
+ * Copyright (C) 2011 Timo Teräs <timo.teras@iki.fi>
+ * All rights reserved.
+ *
+ * This program is free software; you can redistribute it and/or modify it
+ * under the terms of the GNU General Public License version 2 as published
+ * by the Free Software Foundation. See http://www.gnu.org/ for details.
+ */
+
+#include <errno.h>
+#include <fcntl.h>
+#include "apk_applet.h"
+#include "apk_database.h"
+#include "apk_solver.h"
+#include "apk_io.h"
+#include "apk_print.h"
+
+struct test_ctx {
+ const char *installed_db;
+ struct apk_string_array *repos;
+};
+
+static int test_parse(void *pctx, struct apk_db_options *dbopts,
+ int optch, int optindex, const char *optarg)
+{
+ struct test_ctx *ctx = (struct test_ctx *) pctx;
+
+ switch (optch) {
+ case 0x10000:
+ ctx->installed_db = optarg;
+ break;
+ case 0x10001:
+ if (ctx->repos == NULL)
+ apk_string_array_init(&ctx->repos);
+ *apk_string_array_add(&ctx->repos) = (char*) optarg;
+ break;
+ case 'u':
+ apk_flags |= APK_UPGRADE;
+ break;
+ case 'a':
+ apk_flags |= APK_PREFER_AVAILABLE;
+ break;
+ default:
+ return -1;
+ }
+ return 0;
+}
+
+static inline void print_change(struct apk_package *oldpkg,
+ struct apk_package *newpkg)
+{
+ const char *msg = NULL;
+ struct apk_name *name;
+ int r;
+
+ if (oldpkg != NULL)
+ name = oldpkg->name;
+ else
+ name = newpkg->name;
+
+ if (oldpkg == NULL) {
+ apk_message("Installing %s (" BLOB_FMT ")",
+ name->name,
+ BLOB_PRINTF(*newpkg->version));
+ } else if (newpkg == NULL) {
+ apk_message("Purging %s (" BLOB_FMT ")",
+ name->name,
+ BLOB_PRINTF(*oldpkg->version));
+ } else {
+ r = apk_pkg_version_compare(newpkg, oldpkg);
+ switch (r) {
+ case APK_VERSION_LESS:
+ msg = "Downgrading";
+ break;
+ case APK_VERSION_EQUAL:
+ if (newpkg == oldpkg)
+ msg = "Re-installing";
+ else
+ msg = "Replacing";
+ break;
+ case APK_VERSION_GREATER:
+ msg = "Upgrading";
+ break;
+ }
+ apk_message("%s %s (" BLOB_FMT " -> " BLOB_FMT ")",
+ msg, name->name,
+ BLOB_PRINTF(*oldpkg->version),
+ BLOB_PRINTF(*newpkg->version));
+ }
+}
+
+static int test_main(void *pctx, struct apk_database *db, int argc, char **argv)
+{
+ struct test_ctx *ctx = (struct test_ctx *) pctx;
+ struct apk_bstream *bs;
+ struct apk_package_array *solution = NULL;
+ struct apk_changeset changeset;
+ int i;
+
+ if (argc != 1)
+ return -EINVAL;
+
+ /* load installed db */
+ if (ctx->installed_db != NULL) {
+ bs = apk_bstream_from_file(AT_FDCWD, ctx->installed_db);
+ apk_db_index_read(db, bs, -1);
+ bs->close(bs, NULL);
+ }
+
+ /* load additional indexes */
+ if (ctx->repos) {
+ for (i = 0; i < ctx->repos->num; i++) {
+ bs = apk_bstream_from_file(AT_FDCWD, ctx->repos->item[i]);
+ apk_db_index_read(db, bs, i);
+ bs->close(bs, NULL);
+ }
+ }
+
+ /* construct new world */
+ apk_deps_parse(db, &db->world, APK_BLOB_STR(argv[0]));
+
+ /* run solver */
+ apk_solver_sort(db);
+ if (apk_solver_solve(db, db->world, &solution) != 0)
+ return 1;
+
+ memset(&changeset, 0, sizeof(changeset));
+ if (apk_solver_generate_changeset(db, solution, &changeset) == 0) {
+ /* dump changeset */
+ for (i = 0; i < changeset.changes->num; i++) {
+ struct apk_change *c = &changeset.changes->item[i];
+ print_change(c->oldpkg, c->newpkg);
+ }
+ }
+
+ return 0;
+}
+
+static struct apk_option test_options[] = {
+ { 0x10000, "installed", "Installed database",
+ required_argument, "DB" },
+ { 0x10001, "raw-repository", "Add unsigned test repository index",
+ required_argument, "INDEX" },
+ { 'u', "upgrade", "Prefer to upgrade package" },
+ { 'a', "available",
+ "Re-install or downgrade if currently installed package is not "
+ "currently available from any repository" },
+};
+
+static struct apk_applet test_applet = {
+ .name = "test",
+ .help = "Test dependency graph solver (uses simple repository and installed db)",
+ .arguments = "'WORLD'",
+ .open_flags = APK_OPENF_READ | APK_OPENF_NO_STATE | APK_OPENF_NO_REPOS,
+ .context_size = sizeof(struct test_ctx),
+ .num_options = ARRAY_SIZE(test_options),
+ .options = test_options,
+ .parse = test_parse,
+ .main = test_main,
+};
+
+APK_DEFINE_APPLET(test_applet);
diff --git a/src/topology.c b/src/topology.c
new file mode 100644
index 0000000..a60d20c
--- /dev/null
+++ b/src/topology.c
@@ -0,0 +1,56 @@
+/* topology.c - Alpine Package Keeper (APK)
+ * Topological sorting of database packages
+ *
+ * Copyright (C) 2011 Timo Teräs <timo.teras@iki.fi>
+ * All rights reserved.
+ *
+ * This program is free software; you can redistribute it and/or modify it
+ * under the terms of the GNU General Public License version 2 as published
+ * by the Free Software Foundation. See http://www.gnu.org/ for details.
+ */
+
+#include "apk_database.h"
+
+static int sort_pkg(apk_hash_item item, void *ctx)
+{
+ struct apk_package *pkg = (struct apk_package *) item;
+ unsigned int *sort_order = (unsigned int *) ctx;
+ int i, j;
+
+ /* Avoid recursion to same package */
+ if (pkg->topology_sort != 0) {
+ /* if pkg->topology_sort==-1 we have encountered a
+ * dependency loop. Just silently ignore it and pick a
+ * random topology sorting. */
+ return 0;
+ }
+ pkg->topology_sort = -1;
+
+ /* Sort all dependants before self */
+ for (i = 0; i < pkg->depends->num; i++) {
+ struct apk_dependency *dep = &pkg->depends->item[i];
+ struct apk_name *name0 = dep->name;
+
+ /* FIXME: sort names in order of ascending preference */
+ for (j = 0; j < name0->pkgs->num; j++) {
+ struct apk_package *pkg0 = name0->pkgs->item[j];
+ if (!apk_dep_is_satisfied(dep, pkg0))
+ continue;
+ sort_pkg(pkg0, ctx);
+ }
+ }
+
+ /* FIXME: install_if, provides, etc.*/
+
+ /* Finally assign a topology sorting order */
+ pkg->topology_sort = ++(*sort_order);
+
+ return 0;
+}
+
+void apk_solver_sort(struct apk_database *db)
+{
+ unsigned int sort_order = 0;
+
+ apk_hash_foreach(&db->available.packages, sort_pkg, &sort_order);
+}
diff --git a/test/Makefile b/test/Makefile
index 417ed1a..b59a456 100644
--- a/test/Makefile
+++ b/test/Makefile
@@ -13,7 +13,7 @@ SYSREPO ?= http://alpinelinux.org/cgi-bin/dl.cgi/edge/main
LD_LIBRARY_PATH = ../src
export LD_LIBRARY_PATH SYSREPO
-all: tests
+all: tests
$(repos):
@echo "Building $@"
@@ -50,11 +50,17 @@ repos.stamp: $(repos)
$(SUDO) rm -rf $(testroot); \
touch $@
-tests: repos.stamp
- @echo "== Testing `$(APK) --version` =="
+root-tests: repos.stamp
+ @echo "== Testing `$(APK) --version` (tests that require root permission) =="
@for i in test*.sh; do \
rm -f $${i%.sh}.ok ;\
$(SUDO) $(MAKE) --no-print-directory $${i%.sh}.ok SYSREPO=$(SYSREPO); \
done
-.PHONY: $(repos)
+tests:
+ @echo "== Testing `$(APK) --version` =="
+ @for i in $(sort $(filter-out test%.sh,$(wildcard *.sh))); do \
+ ./$$i || exit 1 ; \
+ done
+
+.PHONY: $(repos) tests
diff --git a/test/basic.installed b/test/basic.installed
new file mode 100644
index 0000000..16d66fb
--- /dev/null
+++ b/test/basic.installed
@@ -0,0 +1,13 @@
+C:Q1EyN5AdpAOBJWKMR89pp/C66o+OE=
+P:a
+V:1
+S:1
+I:1
+D:b
+
+C:Q1C4uoV7SdMdDhYg4OCVmI71D8HIA=
+P:b
+V:1
+S:1
+I:1
+
diff --git a/test/basic.repo b/test/basic.repo
new file mode 100644
index 0000000..4aace18
--- /dev/null
+++ b/test/basic.repo
@@ -0,0 +1,26 @@
+C:Q1EyN5AdpAOBJWKMR89pp/C66o+OE=
+P:a
+V:1
+S:1
+I:1
+D:b
+
+C:Q1eVpkasfqZAukAXFYbgwt4xAMZWU=
+P:a
+V:2
+S:1
+I:1
+D:b
+
+C:Q1C4uoV7SdMdDhYg4OCVmI71D8HIA=
+P:b
+V:1
+S:1
+I:1
+
+C:Q1hdUpqRv5mYgJEqW52UmVsvmyysE=
+P:b
+V:2
+S:1
+I:1
+
diff --git a/test/basic1.expect b/test/basic1.expect
new file mode 100644
index 0000000..a6cf8f2
--- /dev/null
+++ b/test/basic1.expect
@@ -0,0 +1,2 @@
+Installing a (2)
+Installing b (2)
diff --git a/test/basic1.test b/test/basic1.test
new file mode 100644
index 0000000..f0dffab
--- /dev/null
+++ b/test/basic1.test
@@ -0,0 +1 @@
+--raw-repository basic.repo a
diff --git a/test/basic2.expect b/test/basic2.expect
new file mode 100644
index 0000000..e69de29
--- /dev/null
+++ b/test/basic2.expect
diff --git a/test/basic2.test b/test/basic2.test
new file mode 100644
index 0000000..561380e
--- /dev/null
+++ b/test/basic2.test
@@ -0,0 +1 @@
+--raw-repository basic.repo --installed basic.installed a
diff --git a/test/basic3.expect b/test/basic3.expect
new file mode 100644
index 0000000..1764c4a
--- /dev/null
+++ b/test/basic3.expect
@@ -0,0 +1,2 @@
+Upgrading a (1 -> 2)
+Upgrading b (1 -> 2)
diff --git a/test/basic3.test b/test/basic3.test
new file mode 100644
index 0000000..7f4efa7
--- /dev/null
+++ b/test/basic3.test
@@ -0,0 +1 @@
+--raw-repository basic.repo --installed basic.installed -u a
diff --git a/test/basic4.expect b/test/basic4.expect
new file mode 100644
index 0000000..9dacff1
--- /dev/null
+++ b/test/basic4.expect
@@ -0,0 +1 @@
+Purging a (1)
diff --git a/test/basic4.test b/test/basic4.test
new file mode 100644
index 0000000..e2b897c
--- /dev/null
+++ b/test/basic4.test
@@ -0,0 +1 @@
+--raw-repository basic.repo --installed basic.installed b
diff --git a/test/complicated1.expect b/test/complicated1.expect
new file mode 100644
index 0000000..e3ad04d
--- /dev/null
+++ b/test/complicated1.expect
@@ -0,0 +1,4 @@
+Installing a (2)
+Installing b (1)
+Installing c (1)
+Installing d (1.5)
diff --git a/test/complicated1.installed b/test/complicated1.installed
new file mode 100644
index 0000000..20e6875
--- /dev/null
+++ b/test/complicated1.installed
@@ -0,0 +1,6 @@
+C:Q16m4HrGizBiH4lG6Mxd5EL239L2U=
+P:d
+V:1.0
+S:1
+I:1
+
diff --git a/test/complicated1.repo b/test/complicated1.repo
new file mode 100644
index 0000000..d4cf2ab
--- /dev/null
+++ b/test/complicated1.repo
@@ -0,0 +1,46 @@
+C:Q1EyN5AdpAOBJWKMR89pp/C66o+OE=
+P:a
+V:2
+S:1
+I:1
+D:b c
+
+C:Q1eVpkasfqZAukAXFYbgwt4xAMZWU=
+P:a
+V:3
+S:1
+I:1
+D:b c d>1.5
+
+C:Q1C4uoV7SdMdDhYg4OCVmI71D8HIA=
+P:b
+V:1
+S:1
+I:1
+D:c d<2.0
+
+C:Q1hdUpqRv5mYgJEqW52UmVsvmyysE=
+P:c
+V:1
+S:1
+I:1
+D:d>1.0
+
+C:Q16m4HrGizBiH4lG6Mxd5EL239L2U=
+P:d
+V:1.0
+S:1
+I:1
+
+C:Q1/hQ3eH2AguTwJVGOz+keypXhXKY=
+P:d
+V:1.5
+S:1
+I:1
+
+C:Q19uA/Cwc6UfrQs95TWVDETyAeEYM=
+P:d
+V:2.0
+S:1
+I:1
+
diff --git a/test/complicated1.test b/test/complicated1.test
new file mode 100644
index 0000000..8e98c78
--- /dev/null
+++ b/test/complicated1.test
@@ -0,0 +1 @@
+--raw-repository complicated1.repo a
diff --git a/test/complicated2.expect b/test/complicated2.expect
new file mode 100644
index 0000000..bfaa5ab
--- /dev/null
+++ b/test/complicated2.expect
@@ -0,0 +1,3 @@
+Installing b (1)
+Installing c (1)
+Installing d (1.5)
diff --git a/test/complicated2.test b/test/complicated2.test
new file mode 100644
index 0000000..d70cf8f
--- /dev/null
+++ b/test/complicated2.test
@@ -0,0 +1 @@
+--raw-repository complicated1.repo b
diff --git a/test/complicated3.expect b/test/complicated3.expect
new file mode 100644
index 0000000..81c21cb
--- /dev/null
+++ b/test/complicated3.expect
@@ -0,0 +1,2 @@
+Installing c (1)
+Installing d (2.0)
diff --git a/test/complicated3.test b/test/complicated3.test
new file mode 100644
index 0000000..fa75522
--- /dev/null
+++ b/test/complicated3.test
@@ -0,0 +1 @@
+--raw-repository complicated1.repo c
diff --git a/test/complicated4.expect b/test/complicated4.expect
new file mode 100644
index 0000000..dc96f6e
--- /dev/null
+++ b/test/complicated4.expect
@@ -0,0 +1,4 @@
+Installing a (2)
+Installing b (1)
+Installing c (1)
+Upgrading d (1.0 -> 1.5)
diff --git a/test/complicated4.test b/test/complicated4.test
new file mode 100644
index 0000000..2b636ec
--- /dev/null
+++ b/test/complicated4.test
@@ -0,0 +1 @@
+--raw-repository complicated1.repo --installed complicated1.installed a
diff --git a/test/solver.sh b/test/solver.sh
new file mode 100755
index 0000000..d819c70
--- /dev/null
+++ b/test/solver.sh
@@ -0,0 +1,23 @@
+#!/bin/sh
+
+APK_TEST=../src/apk_test
+
+fail=0
+for test in *.test; do
+ bn=$(basename $test .test)
+ $APK_TEST $(cat $test) &> $bn.got
+ if ! cmp $bn.expect $bn.got 2> /dev/null; then
+ fail=$((fail+1))
+ echo "FAIL: $test"
+ diff -ru $bn.expect $bn.got
+ else
+ echo "OK: $test"
+ fi
+done
+
+if [ "$fail" != "0" ]; then
+ echo "FAIL: $fail failed test cases"
+fi
+
+exit $fail
+
diff --git a/test/version.sh b/test/version.sh
index e01b674..18199a6 100755
--- a/test/version.sh
+++ b/test/version.sh
@@ -1,7 +1,7 @@
#!/bin/sh
fail=0
-while read a result b rest ; do
+cat version.data | while read a result b rest ; do
output="$(../src/apk version -t "$a" "$b")"
if [ "$output" != "$result" ] ; then
echo "$a $result $b, but got $output"
@@ -9,5 +9,9 @@ while read a result b rest ; do
fi
done
+if [ "$fail" == "0" ]; then
+ echo "OK: version checking works"
+fi
+
exit $fail