test/suites/backtracking.sh

# suite: plan_resolution's own genuine, cross-request/cross-sibling
# backtracking -- resolve_dep/pick_provider's own %tag backtracking
# (covered by resolution.sh/graphs.sh) only ever looks at $db as it
# stands at the moment ONE specific %tag is decided, so it is blind to
# a conflict that only exists because of ANOTHER package in the SAME
# batch, discovered before or after that package is itself processed.
# every test here is a scenario the OLD (pre-plan_resolution) resolver
# could not solve even though a satisfying combination existed --
# either aborting the whole batch, or (worse) leaving some of it really
# installed on disk before discovering the unsatisfiable part. every
# test sets GLOBAL_DEPS=" " so the graph under test is exactly the graph
# declared.
 
# the flagship scenario: a %tag choice made resolving the FIRST
# requested package must be reconsidered once the SECOND requested
# package (processed afterward, in the same invocation) turns out to
# conflict with it -- the old resolver had already picked (and
# installed) the preferred provider by the time the conflict was even
# checked, and aborted with no way back.
test_cross_request_backtrack() {
	t_begin "cross_request_backtrack"
	reset_state
	printf 'GLOBAL_DEPS=" "\n' >> "$CONF"
	mkport btp1 <<'EOF'
pkg_name="btp1"
pkg_ver="1.0"
pkg_tags="bttag"
pkg_pref="10"
install:
	touch $MP_PREFIX/btp1-installed
remove:
	rm -f $MP_PREFIX/btp1-installed
EOF
	mkport btp2 <<'EOF'
pkg_name="btp2"
pkg_ver="1.0"
pkg_tags="bttag"
pkg_pref="20"
install:
	touch $MP_PREFIX/btp2-installed
remove:
	rm -f $MP_PREFIX/btp2-installed
EOF
	mkport btblocker <<'EOF'
pkg_name="btblocker"
pkg_ver="1.0"
pkg_conflicts="btp1"
install:
	touch $MP_PREFIX/btblocker-installed
remove:
	rm -f $MP_PREFIX/btblocker-installed
EOF
	mkport btconsumer <<'EOF'
pkg_name="btconsumer"
pkg_ver="1.0"
pkg_deps="%bttag"
install:
	touch $MP_PREFIX/btconsumer-installed
remove:
	rm -f $MP_PREFIX/btconsumer-installed
EOF
	# consumer requested FIRST: naive left-to-right resolution decides
	# %bttag (picking the lower-pref btp1) before ever seeing btblocker.
	out=$(mp install btconsumer btblocker 2>&1)
	rc=$?
	assert_exit0 "$rc" "$CUR_TEST" || return
	assert_file_exists "$MP_PREFIX/btp2-installed" "$CUR_TEST" || return
	assert_file_absent "$MP_PREFIX/btp1-installed" "$CUR_TEST" || return
	assert_file_exists "$MP_PREFIX/btblocker-installed" "$CUR_TEST" || return
	assert_file_exists "$MP_PREFIX/btconsumer-installed" "$CUR_TEST" || return
	t_pass
}
 
# the same shape of problem, but the conflicting dependency is a SIBLING
# in one package's OWN pkg_deps list rather than a separate top-level
# request -- the %tag is resolved as the FIRST dep, the conflict comes
# from the SECOND, both belonging to the one package "sdneed".
test_sibling_dep_backtrack() {
	t_begin "sibling_dep_backtrack"
	reset_state
	printf 'GLOBAL_DEPS=" "\n' >> "$CONF"
	mkport sdp1 <<'EOF'
pkg_name="sdp1"
pkg_ver="1.0"
pkg_tags="sdtag"
pkg_pref="10"
install:
	touch $MP_PREFIX/sdp1-installed
remove:
	rm -f $MP_PREFIX/sdp1-installed
EOF
	mkport sdp2 <<'EOF'
pkg_name="sdp2"
pkg_ver="1.0"
pkg_tags="sdtag"
pkg_pref="20"
install:
	touch $MP_PREFIX/sdp2-installed
remove:
	rm -f $MP_PREFIX/sdp2-installed
EOF
	mkport sdblocker <<'EOF'
pkg_name="sdblocker"
pkg_ver="1.0"
pkg_conflicts="sdp1"
install:
	touch $MP_PREFIX/sdblocker-installed
remove:
	rm -f $MP_PREFIX/sdblocker-installed
EOF
	mkport sdneed <<'EOF'
pkg_name="sdneed"
pkg_ver="1.0"
pkg_deps="%sdtag sdblocker"
install:
	touch $MP_PREFIX/sdneed-installed
remove:
	rm -f $MP_PREFIX/sdneed-installed
EOF
	out=$(mp install sdneed 2>&1)
	rc=$?
	assert_exit0 "$rc" "$CUR_TEST" || return
	assert_file_exists "$MP_PREFIX/sdp2-installed" "$CUR_TEST" || return
	assert_file_absent "$MP_PREFIX/sdp1-installed" "$CUR_TEST" || return
	assert_file_exists "$MP_PREFIX/sdblocker-installed" "$CUR_TEST" || return
	assert_file_exists "$MP_PREFIX/sdneed-installed" "$CUR_TEST" || return
	t_pass
}
 
# extreme cycles: among three %tag candidates, exactly one closes a
# hard dependency cycle back through the requesting package itself --
# that one candidate must be skipped (not treated as an unconditional
# failure of the whole tag), landing on the next-best conflict/cycle-
# free candidate instead.
test_cycle_routed_around_tag_choice() {
	t_begin "cycle_routed_around_tag_choice"
	reset_state
	printf 'GLOBAL_DEPS=" "\n' >> "$CONF"
	mkport cyneed <<'EOF'
pkg_name="cyneed"
pkg_ver="1.0"
pkg_deps="%cytag"
install:
	touch $MP_PREFIX/cyneed-installed
remove:
	rm -f $MP_PREFIX/cyneed-installed
EOF
	mkport cyp1 <<'EOF'
pkg_name="cyp1"
pkg_ver="1.0"
pkg_tags="cytag"
pkg_pref="10"
pkg_deps="cyneed"
install:
	touch $MP_PREFIX/cyp1-installed
remove:
	rm -f $MP_PREFIX/cyp1-installed
EOF
	mkport cyp2 <<'EOF'
pkg_name="cyp2"
pkg_ver="1.0"
pkg_tags="cytag"
pkg_pref="20"
install:
	touch $MP_PREFIX/cyp2-installed
remove:
	rm -f $MP_PREFIX/cyp2-installed
EOF
	mkport cyp3 <<'EOF'
pkg_name="cyp3"
pkg_ver="1.0"
pkg_tags="cytag"
pkg_pref="30"
install:
	touch $MP_PREFIX/cyp3-installed
remove:
	rm -f $MP_PREFIX/cyp3-installed
EOF
	out=$(mp install cyneed 2>&1)
	rc=$?
	assert_exit0 "$rc" "$CUR_TEST" || return
	assert_file_absent "$MP_PREFIX/cyp1-installed" "$CUR_TEST (cycle-closing candidate must be skipped)" || return
	assert_file_exists "$MP_PREFIX/cyp2-installed" "$CUR_TEST (next-best, cycle-free candidate)" || return
	assert_file_absent "$MP_PREFIX/cyp3-installed" "$CUR_TEST (never needed once cyp2 works)" || return
	assert_file_exists "$MP_PREFIX/cyneed-installed" "$CUR_TEST" || return
	t_pass
}
 
# huge diamond: many independently-requested consumers all sharing one
# %tag must converge on exactly one physical provider, in a single
# invocation.
test_huge_diamond_many_consumers() {
	t_begin "huge_diamond_many_consumers"
	reset_state
	printf 'GLOBAL_DEPS=" "\n' >> "$CONF"
	mkport hdprov <<'EOF'
pkg_name="hdprov"
pkg_ver="1.0"
pkg_tags="hdtag"
install:
	touch $MP_PREFIX/hdprov-installed
remove:
	rm -f $MP_PREFIX/hdprov-installed
EOF
	names=""
	i=1
	while [ "$i" -le 15 ]; do
		mkport "hdc$i" <<EOF
pkg_name="hdc$i"
pkg_ver="1.0"
pkg_deps="%hdtag"
install:
	touch \$MP_PREFIX/hdc$i-installed
remove:
	rm -f \$MP_PREFIX/hdc$i-installed
EOF
		names="$names hdc$i"
		i=$((i + 1))
	done
	out=$(mp install $names 2>&1)
	rc=$?
	assert_exit0 "$rc" "$CUR_TEST" || return
	count=$(grep -c '^hdprov' "$WD/db")
	if [ "$count" -ne 1 ]; then t_fail "$CUR_TEST (expected exactly 1 hdprov db entry, got $count)"; return; fi
	i=1
	while [ "$i" -le 15 ]; do
		assert_file_exists "$MP_PREFIX/hdc$i-installed" "$CUR_TEST" || return
		i=$((i + 1))
	done
	t_pass
}
 
# combinations: one %tag, three candidates, three DIFFERENT reasons two
# of them are unusable (a static conflict, and a dependency cycle) --
# only the third, clean candidate must be picked.
test_combined_cycle_and_conflict_backtrack() {
	t_begin "combined_cycle_and_conflict_backtrack"
	reset_state
	printf 'GLOBAL_DEPS=" "\n' >> "$CONF"
	mkport ccx <<'EOF'
pkg_name="ccx"
pkg_ver="1.0"
install:
	touch $MP_PREFIX/ccx-installed
remove:
	rm -f $MP_PREFIX/ccx-installed
EOF
	mkport ccneed <<'EOF'
pkg_name="ccneed"
pkg_ver="1.0"
pkg_deps="%cctag"
install:
	touch $MP_PREFIX/ccneed-installed
remove:
	rm -f $MP_PREFIX/ccneed-installed
EOF
	mkport ccp1 <<'EOF'
pkg_name="ccp1"
pkg_ver="1.0"
pkg_tags="cctag"
pkg_pref="10"
pkg_conflicts="ccx"
install:
	touch $MP_PREFIX/ccp1-installed
remove:
	rm -f $MP_PREFIX/ccp1-installed
EOF
	mkport ccp2 <<'EOF'
pkg_name="ccp2"
pkg_ver="1.0"
pkg_tags="cctag"
pkg_pref="20"
pkg_deps="ccneed"
install:
	touch $MP_PREFIX/ccp2-installed
remove:
	rm -f $MP_PREFIX/ccp2-installed
EOF
	mkport ccp3 <<'EOF'
pkg_name="ccp3"
pkg_ver="1.0"
pkg_tags="cctag"
pkg_pref="30"
install:
	touch $MP_PREFIX/ccp3-installed
remove:
	rm -f $MP_PREFIX/ccp3-installed
EOF
	mp install ccx >/tmp/cc.out 2>&1
	out=$(mp install ccneed 2>&1)
	rc=$?
	assert_exit0 "$rc" "$CUR_TEST" || return
	assert_file_absent "$MP_PREFIX/ccp1-installed" "$CUR_TEST (conflicts with ccx)" || return
	assert_file_absent "$MP_PREFIX/ccp2-installed" "$CUR_TEST (cycles back through ccneed)" || return
	assert_file_exists "$MP_PREFIX/ccp3-installed" "$CUR_TEST (only clean candidate)" || return
	assert_file_exists "$MP_PREFIX/ccneed-installed" "$CUR_TEST" || return
	t_pass
}
 
# a conflict discovered several hops BELOW the tag decision (not an
# immediate sibling dependency) must still trigger backtracking all the
# way back up to the tag choice.
test_deep_downstream_conflict_backtrack() {
	t_begin "deep_downstream_conflict_backtrack"
	reset_state
	printf 'GLOBAL_DEPS=" "\n' >> "$CONF"
	mkport ddp1 <<'EOF'
pkg_name="ddp1"
pkg_ver="1.0"
pkg_tags="ddtag"
pkg_pref="10"
install:
	touch $MP_PREFIX/ddp1-installed
remove:
	rm -f $MP_PREFIX/ddp1-installed
EOF
	mkport ddp2 <<'EOF'
pkg_name="ddp2"
pkg_ver="1.0"
pkg_tags="ddtag"
pkg_pref="20"
install:
	touch $MP_PREFIX/ddp2-installed
remove:
	rm -f $MP_PREFIX/ddp2-installed
EOF
	mkport ddleaf <<'EOF'
pkg_name="ddleaf"
pkg_ver="1.0"
pkg_conflicts="ddp1"
install:
	touch $MP_PREFIX/ddleaf-installed
remove:
	rm -f $MP_PREFIX/ddleaf-installed
EOF
	mkport ddmid <<'EOF'
pkg_name="ddmid"
pkg_ver="1.0"
pkg_deps="ddleaf"
install:
	touch $MP_PREFIX/ddmid-installed
remove:
	rm -f $MP_PREFIX/ddmid-installed
EOF
	mkport ddneed <<'EOF'
pkg_name="ddneed"
pkg_ver="1.0"
pkg_deps="%ddtag ddmid"
install:
	touch $MP_PREFIX/ddneed-installed
remove:
	rm -f $MP_PREFIX/ddneed-installed
EOF
	out=$(mp install ddneed 2>&1)
	rc=$?
	assert_exit0 "$rc" "$CUR_TEST" || return
	assert_file_absent "$MP_PREFIX/ddp1-installed" "$CUR_TEST" || return
	assert_file_exists "$MP_PREFIX/ddp2-installed" "$CUR_TEST" || return
	assert_file_exists "$MP_PREFIX/ddleaf-installed" "$CUR_TEST" || return
	assert_file_exists "$MP_PREFIX/ddmid-installed" "$CUR_TEST" || return
	assert_file_exists "$MP_PREFIX/ddneed-installed" "$CUR_TEST" || return
	t_pass
}
 
# a genuinely unsatisfiable request must leave NOTHING installed,
# including a perfectly fine, unrelated package requested in the SAME
# batch that would have installed successfully first under naive
# left-to-right processing.
test_unsatisfiable_leaves_nothing_installed() {
	t_begin "unsatisfiable_leaves_nothing_installed"
	reset_state
	printf 'GLOBAL_DEPS=" "\n' >> "$CONF"
	mkport unsx <<'EOF'
pkg_name="unsx"
pkg_ver="1.0"
install:
	touch $MP_PREFIX/unsx-installed
remove:
	rm -f $MP_PREFIX/unsx-installed
EOF
	mkport unsp1 <<'EOF'
pkg_name="unsp1"
pkg_ver="1.0"
pkg_tags="unstag"
pkg_conflicts="unsx"
install:
	touch $MP_PREFIX/unsp1-installed
remove:
	rm -f $MP_PREFIX/unsp1-installed
EOF
	mkport unsleadin <<'EOF'
pkg_name="unsleadin"
pkg_ver="1.0"
install:
	touch $MP_PREFIX/unsleadin-installed
remove:
	rm -f $MP_PREFIX/unsleadin-installed
EOF
	mkport unsneed <<'EOF'
pkg_name="unsneed"
pkg_ver="1.0"
pkg_deps="%unstag"
install:
	touch $MP_PREFIX/unsneed-installed
remove:
	rm -f $MP_PREFIX/unsneed-installed
EOF
	mp install unsx >/tmp/uns.out 2>&1
	out=$(mp install unsleadin unsneed 2>&1)
	rc=$?
	assert_exit_nonzero "$rc" "$CUR_TEST" || return
	assert_file_absent "$MP_PREFIX/unsleadin-installed" "$CUR_TEST (unrelated package in the same failed batch)" || return
	assert_file_absent "$MP_PREFIX/unsp1-installed" "$CUR_TEST" || return
	assert_file_absent "$MP_PREFIX/unsneed-installed" "$CUR_TEST" || return
	t_pass
}
 
run_backtracking_suite() {
	test_cross_request_backtrack
	test_sibling_dep_backtrack
	test_cycle_routed_around_tag_choice
	test_huge_diamond_many_consumers
	test_combined_cycle_and_conflict_backtrack
	test_deep_downstream_conflict_backtrack
	test_unsatisfiable_leaves_nothing_installed
}