From 1fb1afc5c25830c6914789d7b427c9ffdf88a24e Mon Sep 17 00:00:00 2001
From: Timo Teräs <timo.teras@iki.fi>
Date: Wed, 17 Aug 2011 16:55:35 +0300
Subject: solver: reintroduce install_if support

 * each package name has two sorting positions, one which causes
   install_if triggers to be run, and other for bulk dependencies
 * fix also inverted ordering of package installations
---
 src/solver.c             | 231 +++++++++++++++++++++++++++++++++++++----------
 test/basic1.expect       |   2 +-
 test/basic3.expect       |   2 +-
 test/basic5.expect       |   2 +-
 test/complicated1.expect |   6 +-
 test/complicated2.expect |   4 +-
 test/complicated3.expect |   2 +-
 test/complicated4.expect |   6 +-
 test/installif1.expect   |   4 +
 test/installif1.repo     |  48 ++++++++++
 test/installif1.test     |   2 +
 test/installif2.expect   |   6 ++
 test/installif2.test     |   2 +
 test/installif3.expect   |   4 +
 test/installif3.test     |   2 +
 15 files changed, 265 insertions(+), 58 deletions(-)
 create mode 100644 test/installif1.expect
 create mode 100644 test/installif1.repo
 create mode 100644 test/installif1.test
 create mode 100644 test/installif2.expect
 create mode 100644 test/installif2.test
 create mode 100644 test/installif3.expect
 create mode 100644 test/installif3.test

diff --git a/src/solver.c b/src/solver.c
index e257cad..96ca172 100644
--- a/src/solver.c
+++ b/src/solver.c
@@ -26,10 +26,11 @@
 #define APK_PKGSTF_INSTALL		1
 #define APK_PKGSTF_BRANCH		2
 #define APK_PKGSTF_ALT_BRANCH		4
+#define APK_PKGSTF_INSTALLIF		8
 
 struct apk_package_state {
 	struct apk_package *backtrack;
-	unsigned int topology_depends;
+	unsigned int topology_hard, topology_soft;
 	unsigned short flags;
 	unsigned short conflicts;
 	unsigned short cur_unsatisfiable;
@@ -43,6 +44,7 @@ struct apk_name_state {
 	struct apk_package *chosen;
 	unsigned short flags;
 	unsigned short requirers;
+	unsigned short install_ifs;
 };
 
 struct apk_solver_state {
@@ -82,37 +84,100 @@ static inline int pkg_available(struct apk_database *db, struct apk_package *pkg
 	return FALSE;
 }
 
-static void sort_pkg(struct apk_solver_state *ss, struct apk_package *pkg)
+static void foreach_dependency_pkg(
+	struct apk_solver_state *ss, struct apk_dependency_array *depends,
+	void (*cb)(struct apk_solver_state *ss, struct apk_package *dependency))
 {
-	struct apk_package_state *ps;
 	int i, j;
 
-	/* Avoid recursion to same package */
-	if (pkg->state_ptr != NULL)
-		return;
-
-	pkg->state_ptr = calloc(1, sizeof(struct apk_package_state));
-	ps = pkg_to_ps(pkg);
-
-	/* Sort all dependants before self */
-	for (i = 0; i < pkg->depends->num; i++) {
-		struct apk_dependency *dep = &pkg->depends->item[i];
+	/* And sort the main dependencies */
+	for (i = 0; i < depends->num; i++) {
+		struct apk_dependency *dep = &depends->item[i];
 		struct apk_name *name0 = dep->name;
 
 		for (j = 0; j < name0->pkgs->num; j++) {
 			struct apk_package *pkg0 = name0->pkgs->item[j];
+
 			/* conflict depends on all to be not installed */
 			if (dep->result_mask != APK_DEPMASK_CONFLICT &&
 			    !apk_dep_is_satisfied(dep, pkg0))
 				continue;
-			sort_pkg(ss, pkg0);
+
+			cb(ss, pkg0);
 		}
 	}
+}
 
-	/* Assign a topology sorting order */
-	ps->topology_depends = ++ss->num_topology_positions;
+static void foreach_rinstall_if_pkg(
+	struct apk_solver_state *ss, struct apk_package *pkg,
+	void (*cb)(struct apk_solver_state *ss, struct apk_package *rinstall_if))
+{
+	struct apk_name *name = pkg->name;
+	int i, j, k;
+
+	for (i = 0; i < pkg->name->rinstall_if->num; i++) {
+		struct apk_name *name0 = pkg->name->rinstall_if->item[i];
+
+		dbg_printf(PKG_VER_FMT ": rinstall_if %s\n",
+			   PKG_VER_PRINTF(pkg), name0->name);
 
-	/* FIXME: install_if */
+		for (j = 0; j < name0->pkgs->num; j++) {
+			struct apk_package *pkg0 = name0->pkgs->item[j];
+
+			for (k = 0; k < pkg0->install_if->num; k++) {
+				struct apk_dependency *dep = &pkg0->install_if->item[k];
+				if (dep->name == name &&
+				    (dep->result_mask == APK_DEPMASK_CONFLICT ||
+				     apk_dep_is_satisfied(dep, pkg)))
+					break;
+			}
+			if (k >= pkg0->install_if->num)
+				continue;
+
+			/* pkg depends (via install_if) on pkg0 */
+			cb(ss, pkg0);
+		}
+	}
+}
+
+static void sort_hard_dependencies(struct apk_solver_state *ss, struct apk_package *pkg)
+{
+	struct apk_package_state *ps;
+
+	if (pkg->state_ptr == NULL)
+		pkg->state_ptr = calloc(1, sizeof(struct apk_package_state));
+
+	ps = pkg_to_ps(pkg);
+	if (ps->topology_hard)
+		return;
+
+	/* Consider hard dependencies only */
+	foreach_dependency_pkg(ss, pkg->depends, sort_hard_dependencies);
+	foreach_dependency_pkg(ss, pkg->install_if, sort_hard_dependencies);
+
+	ps->topology_soft = ps->topology_hard = ++ss->num_topology_positions;
+	dbg_printf(PKG_VER_FMT ": topology_hard=%d\n",
+		   PKG_VER_PRINTF(pkg), ps->topology_hard);
+}
+
+static void sort_soft_dependencies(struct apk_solver_state *ss, struct apk_package *pkg)
+{
+	struct apk_package_state *ps;
+
+	sort_hard_dependencies(ss, pkg);
+
+	ps = pkg_to_ps(pkg);
+	if (ps->topology_soft != ps->topology_hard)
+		return;
+
+	/* Soft reverse dependencies aka. install_if */
+	foreach_rinstall_if_pkg(ss, pkg, sort_hard_dependencies);
+	foreach_dependency_pkg(ss, pkg->depends, sort_soft_dependencies);
+
+	/* Assign a topology sorting order */
+	ps->topology_soft = ++ss->num_topology_positions;
+	dbg_printf(PKG_VER_FMT ": topology_soft=%d\n",
+		   PKG_VER_PRINTF(pkg), ps->topology_soft);
 }
 
 static void sort_name(struct apk_solver_state *ss, struct apk_name *name)
@@ -120,7 +185,7 @@ static void sort_name(struct apk_solver_state *ss, struct apk_name *name)
 	int i;
 
 	for (i = 0; i < name->pkgs->num; i++)
-		sort_pkg(ss, name->pkgs->item[i]);
+		sort_soft_dependencies(ss, name->pkgs->item[i]);
 }
 
 static void prepare_name(struct apk_solver_state *ss, struct apk_name *name,
@@ -158,7 +223,7 @@ static int inline can_consider_package(struct apk_solver_state *ss, struct apk_p
 {
 	if (ps == NULL)
 		return FALSE;
-	if (ps->topology_depends > ss->topology_position)
+	if (ps->topology_hard > ss->topology_position)
 		return FALSE;
 	if (ps->conflicts)
 		return FALSE;
@@ -209,13 +274,30 @@ static int get_pkg_expansion_flags(struct apk_solver_state *ss, struct apk_packa
 	return APK_PKGSTF_INSTALL;
 }
 
+static int install_if_missing(struct apk_solver_state *ss, struct apk_package *pkg)
+{
+	struct apk_name_state *ns = &ss->name_state[pkg->name->id];
+	int i, missing = 0;
+
+	for (i = 0; i < pkg->install_if->num; i++) {
+		struct apk_dependency *dep = &pkg->install_if->item[i];
+
+		ns = &ss->name_state[dep->name->id];
+		if (!(ns->flags & APK_NAMESTF_LOCKED) ||
+		    !apk_dep_is_satisfied(dep, ns->chosen))
+			missing++;
+	}
+
+	return missing;
+}
+
 static int update_name_state(struct apk_solver_state *ss,
 			     struct apk_name *name, struct apk_name_state *ns,
 			     int requirers_adjustment)
 {
 	struct apk_package *best_pkg = NULL;
 	unsigned int best_topology = 0;
-	int i, options = 0;
+	int i, options = 0, skipped_options = 0;
 
 	ns->requirers += requirers_adjustment;
 
@@ -226,15 +308,25 @@ static int update_name_state(struct apk_solver_state *ss,
 		if (!can_consider_package(ss, ps0))
 			continue;
 
+		if (ns->requirers == 0 && ns->install_ifs != 0 &&
+		    install_if_missing(ss, pkg0)) {
+			skipped_options++;
+			continue;
+		}
+
 		options++;
-		if (best_pkg == NULL ||
-		    ps0->topology_depends > best_topology)
-			best_pkg = pkg0, best_topology = ps0->topology_depends;
+		if (ps0->topology_soft < ss->topology_position &&
+		    ps0->topology_soft > best_topology)
+			best_pkg = pkg0, best_topology = ps0->topology_soft;
+		else if (ps0->topology_hard > best_topology)
+			best_pkg = pkg0, best_topology = ps0->topology_hard;
 	}
 
-	if (options == 0) {
+	if (options == 0 && skipped_options == 0) {
 		if (!(ns->flags & APK_NAMESTF_NO_OPTIONS)) {
 			ss->cur_unsatisfiable += ns->requirers;
+			if (ns->install_ifs)
+				ss->cur_unsatisfiable++;
 			ns->flags |= APK_NAMESTF_NO_OPTIONS;
 		} else if (requirers_adjustment > 0) {
 			ss->cur_unsatisfiable += requirers_adjustment;
@@ -242,17 +334,18 @@ static int update_name_state(struct apk_solver_state *ss,
 	} else
 		ns->flags &= ~APK_NAMESTF_NO_OPTIONS;
 
-	if (options == 0 || ns->requirers == 0) {
+	if (options == 0 || (ns->requirers == 0 && ns->install_ifs == 0)) {
 		if (list_hashed(&ns->unsolved_list)) {
 			list_del(&ns->unsolved_list);
 			list_init(&ns->unsolved_list);
 			ns->chosen = NULL;
 		}
-		dbg_printf("%s: deleted from unsolved: %d requirers, %d options\n",
-			   name->name, ns->requirers, options);
+		dbg_printf("%s: deleted from unsolved: %d requirers, %d install_ifs, %d options\n",
+			   name->name, ns->requirers, ns->install_ifs, options);
 	} else {
-		dbg_printf("%s: added to unsolved: %d requirers, %d options (next topology %d)\n",
-			   name->name, ns->requirers, options, best_topology);
+		dbg_printf("%s: added to unsolved: %d requirers, %d install_ifs, %d options (next topology %d)\n",
+			   name->name, ns->requirers, ns->install_ifs, options,
+			   best_topology);
 		if (!list_hashed(&ns->unsolved_list))
 			list_add(&ns->unsolved_list, &ss->unsolved_list_head);
 		ns->chosen = best_pkg;
@@ -261,6 +354,32 @@ static int update_name_state(struct apk_solver_state *ss,
 	return options;
 }
 
+static void trigger_install_if(struct apk_solver_state *ss,
+			       struct apk_package *pkg)
+{
+	if (install_if_missing(ss, pkg) == 0) {
+		struct apk_name_state *ns = ns = &ss->name_state[pkg->name->id];
+
+		dbg_printf("trigger_install_if: " PKG_VER_FMT " triggered\n",
+			   PKG_VER_PRINTF(pkg));
+		ns->install_ifs++;
+		update_name_state(ss, pkg->name, ns, 0);
+	}
+}
+
+static void untrigger_install_if(struct apk_solver_state *ss,
+			       struct apk_package *pkg)
+{
+	if (install_if_missing(ss, pkg) != 1) {
+		struct apk_name_state *ns = ns = &ss->name_state[pkg->name->id];
+
+		dbg_printf("untrigger_install_if: " PKG_VER_FMT " no longer triggered\n",
+			   PKG_VER_PRINTF(pkg));
+		ns->install_ifs--;
+		update_name_state(ss, pkg->name, ns, 0);
+	}
+}
+
 static void apply_decision(struct apk_solver_state *ss,
 			   struct apk_package *pkg,
 			   struct apk_package_state *ps)
@@ -281,6 +400,7 @@ static void apply_decision(struct apk_solver_state *ss,
 			   pkg->name->name);
 
 		foreach_dependency(ss, pkg->depends, apply_constraint);
+		foreach_rinstall_if_pkg(ss, pkg, trigger_install_if);
 	} else {
 		ps->conflicts++;
 		update_name_state(ss, pkg->name, ns, 0);
@@ -297,11 +417,15 @@ static void undo_decision(struct apk_solver_state *ss,
 		   (ps->flags & APK_PKGSTF_INSTALL) ? "INSTALL" : "NO_INSTALL");
 
 	ss->cur_unsatisfiable = ps->cur_unsatisfiable;
-	if (ps->flags & APK_PKGSTF_BRANCH)
-		ss->topology_position = ps->topology_depends;
+	if (ps->flags & APK_PKGSTF_INSTALLIF)
+		ss->topology_position = ps->topology_soft;
+	else
+		ss->topology_position = ps->topology_hard;
 
 	if (ps->flags & APK_PKGSTF_INSTALL) {
 		ss->assigned_names--;
+
+		foreach_rinstall_if_pkg(ss, pkg, untrigger_install_if);
 		foreach_dependency(ss, pkg->depends, undo_constraint);
 
 		ns->flags &= ~APK_NAMESTF_LOCKED;
@@ -321,15 +445,27 @@ static void push_decision(struct apk_solver_state *ss, struct apk_package *pkg,
 	ps->backtrack = ss->latest_decision;
 	ps->flags = flags;
 	ps->cur_unsatisfiable = ss->cur_unsatisfiable;
+
+	if (ps->topology_soft < ss->topology_position) {
+		if (flags & APK_PKGSTF_INSTALL)
+			ps->flags |= APK_PKGSTF_INSTALLIF;
+		ss->topology_position = ps->topology_soft;
+	} else {
+		ps->flags &= ~APK_PKGSTF_INSTALLIF;
+		ss->topology_position = ps->topology_hard;
+	}
 	ss->latest_decision = pkg;
 
 	if (flags & APK_PKGSTF_BRANCH) {
-		ss->topology_position = ps->topology_depends;
 		dbg_printf("push_decision: adding new BRANCH at topology_position %d\n",
 			   ss->topology_position);
 	} else
 		ps->flags |= APK_PKGSTF_ALT_BRANCH;
 
+	if (ps->flags & APK_PKGSTF_INSTALLIF)
+		dbg_printf("triggers due to " PKG_VER_FMT "\n",
+			   PKG_VER_PRINTF(pkg));
+
 	apply_decision(ss, pkg, ps);
 }
 
@@ -385,7 +521,7 @@ static void apply_constraint(struct apk_solver_state *ss, struct apk_dependency
 		struct apk_package_state *ps0 = pkg_to_ps(pkg0);
 
 		if (ps0 == NULL ||
-		    ps0->topology_depends >= ss->topology_position)
+		    ps0->topology_hard >= ss->topology_position)
 			continue;
 
 		if (!apk_dep_is_satisfied(dep, pkg0)) {
@@ -416,7 +552,7 @@ static void undo_constraint(struct apk_solver_state *ss, struct apk_dependency *
 		struct apk_package *pkg0 = name->pkgs->item[i];
 		struct apk_package_state *ps0 = pkg_to_ps(pkg0);
 
-		if (ps0->topology_depends >= ss->topology_position)
+		if (ps0->topology_hard >= ss->topology_position)
 			continue;
 
 		if (!apk_dep_is_satisfied(dep, pkg0)) {
@@ -439,9 +575,17 @@ static int expand_branch(struct apk_solver_state *ss)
 
 	/* FIXME: change unsolved_list to a priority queue */
 	list_for_each_entry(ns, &ss->unsolved_list_head, unsolved_list) {
-		if (pkg0 == NULL ||
-		    pkg_to_ps(ns->chosen)->topology_depends > topology0)
-			pkg0 = ns->chosen, topology0 = pkg_to_ps(pkg0)->topology_depends;
+		/* ns->chosen can be NULL if the name has only install_if
+		 * requirers that got later conflicted, but it still has
+		 * other options that can get activated later due to more
+		 * complicated install_if rules in some other package. */
+		if (ns->chosen == NULL)
+			continue;
+		if (pkg_to_ps(ns->chosen)->topology_soft < ss->topology_position &&
+		    pkg_to_ps(ns->chosen)->topology_soft > topology0)
+			pkg0 = ns->chosen, topology0 = pkg_to_ps(pkg0)->topology_soft;
+		else if (pkg_to_ps(ns->chosen)->topology_hard > topology0)
+			pkg0 = ns->chosen, topology0 = pkg_to_ps(pkg0)->topology_hard;
 	}
 	if (pkg0 == NULL) {
 		dbg_printf("expand_branch: list is empty (%d unsatisfied)\n",
@@ -455,11 +599,6 @@ static int expand_branch(struct apk_solver_state *ss)
 	dbg_printf("expand_branch: %s\n", pkg0->name->name);
 
 	push_decision(ss, pkg0, get_pkg_expansion_flags(ss, pkg0));
-	#if 0
-		      is_pkg_preferred(ss, pkg0) ?
-			(APK_PKGSTF_INSTALL | APK_PKGSTF_BRANCH) :
-			(APK_PKGSTF_NOINSTALL | APK_PKGSTF_BRANCH));
-			#endif
 
 	return 0;
 }
@@ -563,8 +702,8 @@ static int compare_change(const void *p1, const void *p2)
 	if (c1->newpkg == NULL) {
 		if (c2->newpkg == NULL)
 			/* both deleted - reverse topology order */
-			return  pkg_to_ps(c1->oldpkg)->topology_depends -
-				pkg_to_ps(c2->oldpkg)->topology_depends;
+			return  pkg_to_ps(c2->oldpkg)->topology_hard -
+				pkg_to_ps(c1->oldpkg)->topology_hard;
 
 		/* c1 deleted, c2 installed -> c2 first*/
 		return -1;
@@ -573,8 +712,8 @@ static int compare_change(const void *p1, const void *p2)
 		/* c1 installed, c2 deleted -> c1 first*/
 		return 1;
 
-	return  pkg_to_ps(c2->newpkg)->topology_depends -
-		pkg_to_ps(c1->newpkg)->topology_depends;
+	return  pkg_to_ps(c1->newpkg)->topology_hard -
+		pkg_to_ps(c2->newpkg)->topology_hard;
 }
 
 int apk_solver_generate_changeset(struct apk_database *db,
diff --git a/test/basic1.expect b/test/basic1.expect
index a6cf8f2..81756fe 100644
--- a/test/basic1.expect
+++ b/test/basic1.expect
@@ -1,2 +1,2 @@
-Installing a (2)
 Installing b (2)
+Installing a (2)
diff --git a/test/basic3.expect b/test/basic3.expect
index 1764c4a..73bef16 100644
--- a/test/basic3.expect
+++ b/test/basic3.expect
@@ -1,2 +1,2 @@
-Upgrading a (1 -> 2)
 Upgrading b (1 -> 2)
+Upgrading a (1 -> 2)
diff --git a/test/basic5.expect b/test/basic5.expect
index 269ff0c..b29db17 100644
--- a/test/basic5.expect
+++ b/test/basic5.expect
@@ -1,2 +1,2 @@
-Replacing a (2 -> 2)
 Replacing b (2 -> 2)
+Replacing a (2 -> 2)
diff --git a/test/complicated1.expect b/test/complicated1.expect
index e3ad04d..1387f53 100644
--- a/test/complicated1.expect
+++ b/test/complicated1.expect
@@ -1,4 +1,4 @@
-Installing a (2)
-Installing b (1)
-Installing c (1)
 Installing d (1.5)
+Installing c (1)
+Installing b (1)
+Installing a (2)
diff --git a/test/complicated2.expect b/test/complicated2.expect
index bfaa5ab..5261d10 100644
--- a/test/complicated2.expect
+++ b/test/complicated2.expect
@@ -1,3 +1,3 @@
-Installing b (1)
-Installing c (1)
 Installing d (1.5)
+Installing c (1)
+Installing b (1)
diff --git a/test/complicated3.expect b/test/complicated3.expect
index 81c21cb..e9b2733 100644
--- a/test/complicated3.expect
+++ b/test/complicated3.expect
@@ -1,2 +1,2 @@
-Installing c (1)
 Installing d (2.0)
+Installing c (1)
diff --git a/test/complicated4.expect b/test/complicated4.expect
index dc96f6e..44964e3 100644
--- a/test/complicated4.expect
+++ b/test/complicated4.expect
@@ -1,4 +1,4 @@
-Installing a (2)
-Installing b (1)
-Installing c (1)
 Upgrading d (1.0 -> 1.5)
+Installing c (1)
+Installing b (1)
+Installing a (2)
diff --git a/test/installif1.expect b/test/installif1.expect
new file mode 100644
index 0000000..d9ee058
--- /dev/null
+++ b/test/installif1.expect
@@ -0,0 +1,4 @@
+Installing foo (1)
+Installing lib (1)
+Installing app (1)
+Installing appiif1 (1)
diff --git a/test/installif1.repo b/test/installif1.repo
new file mode 100644
index 0000000..09b6760
--- /dev/null
+++ b/test/installif1.repo
@@ -0,0 +1,48 @@
+C:Q1EyN5AdpAOBJWKMR89pp/C66o+OE=
+P:app
+V:1
+S:1
+I:1
+D:lib
+
+C:Q1eVpkasfqZAukAXFYbgwt4xAMZWU=
+P:lib
+V:1
+S:1
+I:1
+
+C:Q1C4uoV7SdMdDhYg4OCVmI71D8HIA=
+P:foo
+V:1
+S:1
+I:1
+
+C:Q1hdUpqRv5mYgJEqW52UmVsvmyysF=
+P:bar
+V:1
+S:1
+I:1
+
+C:Q1hdUpqRv5mYgJEqW52UmVsvmyysE=
+P:libiif
+V:1
+S:1
+I:1
+i:lib foo
+
+C:Q16m4HrGizBiH4lG6Mxd5EL239L2U=
+P:appiif1
+V:1
+S:1
+I:1
+D:app
+i:app foo
+
+C:Q1/hQ3eH2AguTwJVGOz+keypXhXKY=
+P:appiif2
+V:1
+S:1
+I:1
+D:app
+i:app bar
+
diff --git a/test/installif1.test b/test/installif1.test
new file mode 100644
index 0000000..99e139a
--- /dev/null
+++ b/test/installif1.test
@@ -0,0 +1,2 @@
+--raw-repository installif1.repo
+foo app
diff --git a/test/installif2.expect b/test/installif2.expect
new file mode 100644
index 0000000..0cd5d31
--- /dev/null
+++ b/test/installif2.expect
@@ -0,0 +1,6 @@
+Installing foo (1)
+Installing lib (1)
+Installing app (1)
+Installing appiif1 (1)
+Installing bar (1)
+Installing appiif2 (1)
diff --git a/test/installif2.test b/test/installif2.test
new file mode 100644
index 0000000..f4f68f5
--- /dev/null
+++ b/test/installif2.test
@@ -0,0 +1,2 @@
+--raw-repository installif1.repo
+foo app bar
diff --git a/test/installif3.expect b/test/installif3.expect
new file mode 100644
index 0000000..d9ee058
--- /dev/null
+++ b/test/installif3.expect
@@ -0,0 +1,4 @@
+Installing foo (1)
+Installing lib (1)
+Installing app (1)
+Installing appiif1 (1)
diff --git a/test/installif3.test b/test/installif3.test
new file mode 100644
index 0000000..881b664
--- /dev/null
+++ b/test/installif3.test
@@ -0,0 +1,2 @@
+--raw-repository installif1.repo --raw-repository installif2.repo
+foo app
-- 
cgit v1.2.3-60-g2f50