solver: new package selection logic (which is not yet used)

 * basic code for a backtracking, forward checking dependency satisfier
 * works better when there are tricky dependencies to solve
   (when can't just upgrade everything to most preferred versions)
 * the new code always evaluates all of 'world' constraints
   (old code just does incremental updates based on heuristics)
 * is probably somewhat slower than old code (probably unnoticeable
   difference in most cases)
 * makes easier to write support for provides and repository pinning
 * test applet and a bunch of test cases added which uses the new code
 * from the old feature set install_if is not yet implemented

23 files changed, 155 insertions, 5 deletions

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