reduce-depends.awk: Reduce "pkg>1" and "pkg<2" into "pkg>1<2".

Enhance the reduce-depends.awk script to reduce a larger set of
dependencies into a single dependency.  The patterns representing
intervals of version numbers (can be open-ended) are of the form:

	pkg>lower
	pkg>=lower
	pkg<upper
	pkg<=upper
	pkg>lower<upper
	pkg>lower<=upper
	pkg>=lower<upper
	pkg>=lower<=upper

These patterns are now condensed into a single dependency of the
same form.  For example, given the following patterns:

	pkg>=1.0
	pkg>2.0
	pkg<3.0
	pkg<=4.0
	pkg>=2.5<3.5

the reduced pattern becomes:

	pkg>=2.5<3.0

Add the test script used to help with refactoring and adding the
new feature to the script.

This is a mostly complete rewrite of the script; change the
license to the standard 2-clause BSD license used by TNF.

3 files changed, 601 insertions, 63 deletions

diff --git a/mk/pkgformat/pkg/reduce-depends.awk b/mk/pkgformat/pkg/reduce-depends.awk
index add1e9d0c56..405f5db74fc 100755
--- a/mk/pkgformat/pkg/reduce-depends.awk
+++ b/mk/pkgformat/pkg/reduce-depends.awk
@@ -1,8 +1,8 @@
 #!/usr/bin/awk -f
 #
-# $NetBSD: reduce-depends.awk,v 1.4 2017/05/19 14:58:51 joerg Exp $
+# $NetBSD: reduce-depends.awk,v 1.5 2017/10/01 04:00:40 jlam Exp $
 #
-# Copyright (c) 2006 The NetBSD Foundation, Inc.
+# Copyright (c) 2006-2017 The NetBSD Foundation, Inc.
 # All rights reserved.
 #
 # This code is derived from software contributed to The NetBSD Foundation
@@ -16,13 +16,6 @@
 # 2. Redistributions in binary form must reproduce the above copyright
 #    notice, this list of conditions and the following disclaimer in the
 #    documentation and/or other materials provided with the distribution.
-# 3. All advertising materials mentioning features or use of this software
-#    must display the following acknowledgement:
-#        This product includes software developed by the NetBSD
-#        Foundation, Inc. and its contributors.
-# 4. Neither the name of The NetBSD Foundation nor the names of its
-#    contributors may be used to endorse or promote products derived
-#    from this software without specific prior written permission.
 #
 # THIS SOFTWARE IS PROVIDED BY THE NETBSD FOUNDATION, INC. AND CONTRIBUTORS
 # ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
@@ -43,22 +36,99 @@
 #	reduce-depends.awk -- reduce a list of dependencies
 #
 # SYNOPSIS
-#	reduce-depends.awk "depends_list"
+#	reduce-depends.awk depends-list
 #
 # DESCRIPTION
 #	reduce-depends.awk removes some extraneous dependencies from the
 #	dependency list.  The dependency list should be passed as a single
 #	argument, and the output will be a list of the reduced dependencies,
-#	echo one on a new line.
+#	each dependency separated by a new line.
+#
+#	depends-list	A whitespace-separated list of dependencies.
+#			This must be passed to the script as a single
+#			argument.
 #
 # ENVIRONMENT
-#	CAT
+#	CAT	The name or path to the cat(1) utility.
+#
 #	PKG_ADMIN
+#		The name or path to the pkg_admin(1) utility.
+#
 #	PWD_CMD
-#	TEST
+#		The command to get the physical path to the current
+#		working directory.  The default is "pwd -P".
+#
+#	TEST	The name or path to the test(1) utility.
 #
 ######################################################################
 
+function shquote(s)
+{
+	# Escape single quotes (') by replacing them with '\''.
+	gsub(/'/, "'\\''", s)
+	# Surround with single quotes (').
+	return "'" s "'"
+}
+
+function version_cmp(v1, cmp, v2,	cmd, pattern, pkg)
+{
+	pkg = shquote("test-" v1)
+	test_pattern = shquote("test" cmp v2)
+	cmd = PKG_ADMIN " pmatch " test_pattern " " pkg
+	if (system(cmd) == 0) {
+		# v1 "cmp" v2
+		return 1
+	}
+	return 0
+}
+
+###
+# get_endpoint(cmp, patterns)
+#
+# Parameters:
+#	cmp (string)
+#		The relational operator ("<", "<=", ">", ">=").
+#
+#	patterns (array)
+#		The keys of the array form the set of dependency
+#		patterns that need to be reduced to a single pattern.
+#		The patterns all use the relational operator (cmp)
+#		and each expresses a ray of version strings.  The
+#		value associated with each key is the endpoint for
+#		that pattern.
+#
+# Return value:
+#	endpoint (string)
+#		The endpoint for the ray of version strings.
+#
+# Description:
+#	Returns a version string that is the endpoint of the ray of
+#	version strings formed from the intersection of the rays
+#	expressed by the patterns listed in the patterns array.
+#
+function get_endpoint(cmp, patterns, 	endpoint, key, match_all, pattern, pkg)
+{
+	endpoint = ""			# return value if patterns array is empty
+	for (key in patterns) {
+		endpoint = patterns[key]
+		pkg = shquote(gensub(cmp, "-", 1, key))
+		match_all = 1
+		for (pattern in patterns) {
+			if (key == pattern) continue
+			# Fix up the pattern to be closed if it is open.
+			if (cmp == "<")		sub("<", "<=", pattern)
+			else if (cmp == ">")	sub(">", ">=", pattern)
+			cmd = PKG_ADMIN " pmatch " shquote(pattern) " " pkg
+			if (system(cmd) != 0) {
+				match_all = 0
+				break
+			}
+		}
+		if (match_all == 1) break
+	}
+	return endpoint
+}
+
 BEGIN {
 	CAT = ENVIRON["CAT"] ? ENVIRON["CAT"] : "cat"
 	PKG_ADMIN = ENVIRON["PKG_ADMIN"] ? ENVIRON["PKG_ADMIN"] : "pkg_admin"
@@ -68,8 +138,12 @@ BEGIN {
 	PROGNAME = "reduce-depends.awk"
 	ERRCAT = CAT " 1>&2"
 
-	# Gather all dependencies into the depends array.  Index 0 of the
-	# depends[pkgpath] array is the number of patterns associated with
+	# Match version numbers with an ERE.
+	# XXX This matches more than it should.
+	VERSION_RE = "[0-9A-Za-z._+]+"
+
+	# Gather all dependencies into the patterns array.  Index 0 of the
+	# patterns[pkgpath] array is the number of patterns associated with
 	# that pkgpath.
 	#
 	args = ARGV[1]
@@ -81,19 +155,19 @@ BEGIN {
 			print "ERROR: [" PROGNAME "] invalid dependency pattern: " ARGV[i] | ERRCAT
 			exit 1
 		}
-		if (pattern_seen[pattern] == 1)
-			continue
+		if (pattern_seen[pattern] == 1) continue
 		pattern_seen[pattern] = 1
-		cmd = TEST " -d " dir
+		cmd = TEST " -d " shquote(dir)
 		if (system(cmd) == 0) {
-			cmd = "cd " dir " && " PWD_CMD
+			cmd = "cd " shquote(dir) " && " PWD_CMD
 			while ((cmd | getline pkgpath) > 0) {
 				if (!(pkgpath in pkgsrcdirs)) {
+					# Record package paths in the order they are seen.
 					pkgpaths[P++] = pkgpath
 					pkgsrcdirs[pkgpath] = dir
 				}
-				depends[pkgpath, 0]++;
-				depends[pkgpath, depends[pkgpath, 0]] = pattern
+				D = ++patterns[pkgpath, 0]
+				patterns[pkgpath, D] = pattern
 			}
 			close(cmd)
 		} else {
@@ -102,61 +176,103 @@ BEGIN {
 		}
 	}
 
-	# Reduce dependencies to the strictest set of dependencies it
-	# can derive from all of depends[...].  It only understands
-	# dependencies of the form foo>=1.0, and leaves the other
-	# dependencies undisturbed.
-	#
-	# The algorithm takes dependencies of the form foo>=1.0 and
-	# converts them to foo-1.0.  It then compares this pkg name against
-	# each dependency to see if it satisfies them all.  The key fact
-	# is the the strictest dependency, when converted to a pkg name,
-	# will satisfy every dependency.
-	#
+	# Reduce dependency patterns by package path.
 	for (p = 0; p < P; p++) {
 		pkgpath = pkgpaths[p]
-		D = depends[pkgpath, 0];
-		match_all = 1;
+		dir = pkgsrcdirs[pkgpath]
+		D = patterns[pkgpath, 0]
 		for (d = 1; d <= D; d++) {
-			dep = depends[pkgpath, d]
-			if (dep ~ /[{]/ || \
-			    dep ~ />=[0-9][0-9\.]*(nb[0-9]+)?<[0-9]+/ || \
-			    dep !~ />=[0-9]+/)
-			{
-				reduced[N++] = dep ":" pkgsrcdirs[pkgpath]
-				continue
+			# Repeatedly strip off possible boundary conditions to
+			# arrive at the PKGBASE.
+			pattern = patterns[pkgpath, d]
+			lt_bound = ""; le_bound = ""; ge_bound = ""; gt_bound = ""
+			if (match(pattern, "<" VERSION_RE "$")) {
+				lt_bound = substr(pattern, RSTART + 1, RLENGTH)
+				pattern = substr(pattern, 1, RSTART - 1)
+			}
+			if (match(pattern, "<=" VERSION_RE "$")) {
+				le_bound = substr(pattern, RSTART + 2, RLENGTH)
+				pattern = substr(pattern, 1, RSTART - 1)
+			}
+			if (match(pattern, ">" VERSION_RE "$")) {
+				gt_bound = substr(pattern, RSTART + 1, RLENGTH)
+				pattern = substr(pattern, 1, RSTART - 1)
+			}
+			if (match(pattern, ">=" VERSION_RE "$")) {
+				ge_bound = substr(pattern, RSTART + 2, RLENGTH)
+				pattern = substr(pattern, 1, RSTART - 1)
+			}
+			base = pattern
+			if (lt_bound) lt_patterns[base "<"  lt_bound] = lt_bound
+			if (le_bound) le_patterns[base "<=" le_bound] = le_bound
+			if (gt_bound) gt_patterns[base ">"  gt_bound] = gt_bound
+			if (ge_bound) ge_patterns[base ">=" ge_bound] = ge_bound
+			if (!(lt_bound || le_bound || gt_bound || ge_bound)) {
+				depend = pattern ":" dir
+				if (!(depend in reduced)) reduced[depend] = ++N
+			} else {
+				pkgbase[pkgpath] = base
 			}
-			ge_depends[dep] = dep
 		}
-		for (dep in ge_depends) {
-			dep2pkg = dep; sub(">=", "-", dep2pkg)
-			match_all = 1
-			for (pattern in ge_depends) {
-				cmd = PKG_ADMIN " pmatch \"" pattern "\" " dep2pkg
-				if (system(cmd) != 0) {
-					match_all = 0
-					break
-				}
+		lt_bound = get_endpoint("<",  lt_patterns)
+		le_bound = get_endpoint("<=", le_patterns)
+		gt_bound = get_endpoint(">",  gt_patterns)
+		ge_bound = get_endpoint(">=", ge_patterns)
+
+		# Lower bound and relational operator.
+		lower_bound = ""; gt = ""
+		if (gt_bound && ge_bound) {
+			if (version_cmp(gt_bound, ">=", ge_bound)) {
+				lower_bound = gt_bound; gt = ">"
+			} else {
+				lower_bound = ge_bound; gt = ">="
 			}
-			if (match_all == 0) continue
-			reduced[N++] = dep ":" pkgsrcdirs[pkgpath]
-			break
+		} else if (gt_bound) {
+			lower_bound = gt_bound; gt = ">"
+		} else if (ge_bound) {
+			lower_bound = ge_bound; gt = ">="
 		}
-		#
+
+		# Upper bound and relational operator.
+		upper_bound = ""; lt = ""
+		if (lt_bound && le_bound) {
+			if (version_cmp(lt_bound, "<=", le_bound)) {
+				upper_bound = lt_bound; lt = "<"
+			} else {
+				upper_bound = le_bound; lt = "<="
+			}
+		} else if (lt_bound) {
+			upper_bound = lt_bound; lt = "<"
+		} else if (le_bound) {
+			upper_bound = le_bound; lt = "<="
+		}
+
 		# If there are conflicting dependencies, then just pass them
 		# through and let the rest of the pkgsrc machinery handle it.
 		#
-		if (match_all == 0) {
+		# Othewise, build a new dependency based on the intersection
+		# of the rays determined by the various bounds.
+		#
+		if (lower_bound && upper_bound &&
+		    ((gt == ">" && version_cmp(lower_bound, ">=", upper_bound)) ||
+		     (gt == ">=" && version_cmp(lower_bound, ">", upper_bound)))) {
 			for (d = 1; d <= D; d++) {
-				dep = depends[pkgpath, d]
-				reduced[N++] = dep ":" pkgsrcdirs[pkgpath]
+				depend = patterns[pkgpath, d] ":" dir
+				if (!(depend in reduced)) reduced[depend] = ++N
 			}
+		} else if (lower_bound || upper_bound) {
+			pattern = pkgbase[pkgpath] gt lower_bound lt upper_bound
+			depend = pattern ":" dir
+			if (!(depend in reduced)) reduced[depend] = ++N
 		}
-		for (dep in ge_depends)
-			delete ge_depends[dep]
+
+		delete lt_patterns
+		delete le_patterns
+		delete gt_patterns
+		delete ge_patterns
 	}
 
 	# Output reduced dependencies.
-	for (n = 0; n < N; n++)
-		print reduced[n];
+	for (depend in reduced) output[reduced[depend]] = depend
+	for (i = 1; i <= N; i++) print(output[i])
 }
diff --git a/mk/pkgformat/pkg/tests/Kyuafile b/mk/pkgformat/pkg/tests/Kyuafile
index 14a0caf28e9..f8e2948d1d7 100644
--- a/mk/pkgformat/pkg/tests/Kyuafile
+++ b/mk/pkgformat/pkg/tests/Kyuafile
@@ -1,4 +1,4 @@
--- $NetBSD: Kyuafile,v 1.1 2017/06/01 02:09:43 jlam Exp $
+-- $NetBSD: Kyuafile,v 1.2 2017/10/01 04:00:40 jlam Exp $
 --[[-----------------------------------------------------------------------
 Copyright (c) 2017 The NetBSD Foundation, Inc.
 All rights reserved.
@@ -46,4 +46,5 @@ syntax( 2 )
 
 test_suite( "pkgsrc_pkgformat_pkg" )
 
+atf_test_program { name = "reduce-depends_test" }
 atf_test_program { name = "scripts_test" }
diff --git a/mk/pkgformat/pkg/tests/reduce-depends_test b/mk/pkgformat/pkg/tests/reduce-depends_test
new file mode 100755
index 00000000000..74b43479af1
--- /dev/null
+++ b/mk/pkgformat/pkg/tests/reduce-depends_test
@@ -0,0 +1,421 @@
+#!/usr/bin/env atf-sh
+#
+# Copyright (c) 2017 The NetBSD Foundation, Inc.
+# All rights reserved.
+#
+# This code is derived from software contributed to The NetBSD Foundation
+# by Johnny C. Lam.
+#
+# Redistribution and use in source and binary forms, with or without
+# modification, are permitted provided that the following conditions
+# are met:
+# 1. Redistributions of source code must retain the above copyright
+#    notice, this list of conditions and the following disclaimer.
+# 2. Redistributions in binary form must reproduce the above copyright
+#    notice, this list of conditions and the following disclaimer in the
+#    documentation and/or other materials provided with the distribution.
+#
+# THIS SOFTWARE IS PROVIDED BY THE NETBSD FOUNDATION, INC. AND CONTRIBUTORS
+# ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
+# TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
+# PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE FOUNDATION OR CONTRIBUTORS
+# BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
+# CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
+# SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
+# INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
+# CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
+# ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
+# POSSIBILITY OF SUCH DAMAGE.
+
+# ENVIRONMENT
+#	The following variables are used if they are set:
+#
+#	AWK
+#		The name or path to the awk(1) utility.
+#
+#	PKGSRCDIR
+#		The location of the pkgsrc source tree.  The default is
+#		"/usr/pkgsrc".
+
+write_contents()
+{
+	local file="$1"; shift
+	echo ">>> $file"
+	cat "$file"
+	echo "<<< $file"
+}
+
+check_reduce()
+{
+	: ${AWK:=awk}
+	: ${PKGSRCDIR:=/usr/pkgsrc}
+
+	local input="$1"; shift
+	local expected="$1"; shift
+
+	case $input in
+	/*)	;;
+	*)	input="${HOME}/$input" ;;
+	esac
+
+	( cd ${PKGSRCDIR}/pkgtools/pkg_install &&
+	  ${AWK} -f ${PKGSRCDIR}/mk/pkgformat/pkg/reduce-depends.awk \
+	  	"$(cat $input)"
+	) > value
+
+	if cmp expected value; then
+		: "success"
+	else
+		write_contents expected
+		write_contents value
+		atf_fail "output does not match expected"
+	fi
+}
+
+
+###
+### skip_irreducible_depends_test
+###
+
+atf_test_case skip_irreducible_depends_test
+
+skip_irreducible_depends_test_head()
+{
+	atf_set "descr" "skip irreducible dependencies"
+}
+
+skip_irreducible_depends_test_body()
+{
+	cat > input << EOF
+cwrappers-1{,nb1}:../../pkgtools/cwrappers
+pkg_install>=1:../../pkgtools/pkg_install
+pkg_install<2:../../pkgtools/pkg_install
+pkg_install-{0nb3,1nb2}:../../pkgtools/pkg_install
+EOF
+	cat > expected << EOF
+cwrappers-1{,nb1}:../../pkgtools/cwrappers
+pkg_install-{0nb3,1nb2}:../../pkgtools/pkg_install
+pkg_install>=1<2:../../pkgtools/pkg_install
+EOF
+	check_reduce input expected
+	atf_pass
+}
+
+###
+### less_or_equal_depends_test
+###
+
+atf_test_case less_or_equal_depends_test
+
+less_or_equal_depends_test_head()
+{
+	atf_set "descr" "reduce only <="
+}
+
+less_or_equal_depends_test_body()
+{
+	cat > input << EOF
+pkg_install<=1:../../pkgtools/pkg_install
+pkg_install<=2:../../pkgtools/pkg_install
+pkg_install<=3:../../pkgtools/pkg_install
+EOF
+	cat > expected << EOF
+pkg_install<=1:../../pkgtools/pkg_install
+EOF
+	check_reduce input expected
+	atf_pass
+}
+
+###
+### less_depends_test
+###
+
+atf_test_case less_depends_test
+
+less_depends_test_head()
+{
+	atf_set "descr" "reduce only <"
+}
+
+less_depends_test_body()
+{
+	cat > input << EOF
+pkg_install<1:../../pkgtools/pkg_install
+pkg_install<2:../../pkgtools/pkg_install
+pkg_install<3:../../pkgtools/pkg_install
+EOF
+	cat > expected << EOF
+pkg_install<1:../../pkgtools/pkg_install
+EOF
+	check_reduce input expected
+	atf_pass
+}
+
+###
+### greater_or_equal_depends_test
+###
+
+atf_test_case greater_or_equal_depends_test
+
+greater_or_equal_depends_test_head()
+{
+	atf_set "descr" "reduce only >="
+}
+
+greater_or_equal_depends_test_body()
+{
+	cat > input << EOF
+pkg_install>=1:../../pkgtools/pkg_install
+pkg_install>=2:../../pkgtools/pkg_install
+pkg_install>=3:../../pkgtools/pkg_install
+EOF
+	cat > expected << EOF
+pkg_install>=3:../../pkgtools/pkg_install
+EOF
+	check_reduce input expected
+	atf_pass
+}
+
+###
+### greater_depends_test
+###
+
+atf_test_case greater_depends_test
+
+greater_depends_test_head()
+{
+	atf_set "descr" "reduce only >"
+}
+
+greater_depends_test_body()
+{
+	cat > input << EOF
+pkg_install>1:../../pkgtools/pkg_install
+pkg_install>2:../../pkgtools/pkg_install
+pkg_install>3:../../pkgtools/pkg_install
+EOF
+	cat > expected << EOF
+pkg_install>3:../../pkgtools/pkg_install
+EOF
+	check_reduce input expected
+	atf_pass
+}
+
+###
+### less_and_less_equal_same_bound_test
+###
+
+atf_test_case less_and_less_equal_same_bound_test
+
+less_and_less_equal_same_bound_test_head()
+{
+	atf_set "descr" "reduce < and <=, same bound"
+}
+
+less_and_less_equal_same_bound_test_body()
+{
+	cat > input << EOF
+pkg_install<1:../../pkgtools/pkg_install
+pkg_install<=1:../../pkgtools/pkg_install
+EOF
+	cat > expected << EOF
+pkg_install<1:../../pkgtools/pkg_install
+EOF
+	check_reduce input expected
+	atf_pass
+}
+
+###
+### greater_and_greater_equal_same_bound_test
+###
+
+atf_test_case greater_and_greater_equal_same_bound_test
+
+greater_and_greater_equal_same_bound_test_head()
+{
+	atf_set "descr" "reduce > and >=, same bound"
+}
+
+greater_and_greater_equal_same_bound_test_body()
+{
+	cat > input << EOF
+pkg_install>1:../../pkgtools/pkg_install
+pkg_install>=1:../../pkgtools/pkg_install
+EOF
+	cat > expected << EOF
+pkg_install>1:../../pkgtools/pkg_install
+EOF
+	check_reduce input expected
+	atf_pass
+}
+
+###
+### lower_and_upper_bounds_test
+###
+
+atf_test_case lower_and_upper_bounds_test
+
+lower_and_upper_bounds_test_head()
+{
+	atf_set "descr" "reduce >, >=, <, and <= into one interval"
+}
+
+lower_and_upper_bounds_test_body()
+{
+	cat > input << EOF
+pkg_install>1:../../pkgtools/pkg_install
+pkg_install>=1:../../pkgtools/pkg_install
+pkg_install<2:../../pkgtools/pkg_install
+pkg_install<=2:../../pkgtools/pkg_install
+EOF
+	cat > expected << EOF
+pkg_install>1<2:../../pkgtools/pkg_install
+EOF
+	check_reduce input expected
+	atf_pass
+}
+
+###
+### overlapping_intervals_test
+###
+
+atf_test_case overlapping_intervals_test
+
+overlapping_intervals_test_head()
+{
+	atf_set "descr" "reduce overlapping intervals"
+}
+
+overlapping_intervals_test_body()
+{
+	cat > input << EOF
+pkg_install>1<3:../../pkgtools/pkg_install
+pkg_install>2<4:../../pkgtools/pkg_install
+EOF
+	cat > expected << EOF
+pkg_install>2<3:../../pkgtools/pkg_install
+EOF
+	check_reduce input expected
+	atf_pass
+}
+
+###
+### disjoint_test
+###
+
+atf_test_case disjoint_test
+
+disjoint_test_head()
+{
+	atf_set "descr" "can't reduce disjoint intervals"
+}
+
+disjoint_test_body()
+{
+	cat > input << EOF
+pkg_install<1:../../pkgtools/pkg_install
+pkg_install>1:../../pkgtools/pkg_install
+EOF
+	cat > expected << EOF
+pkg_install<1:../../pkgtools/pkg_install
+pkg_install>1:../../pkgtools/pkg_install
+EOF
+	check_reduce input expected
+	atf_pass
+}
+
+###
+### strings_in_versions_test
+###
+
+atf_test_case strings_in_versions_test
+
+strings_in_versions_test_head()
+{
+	atf_set "descr" "strings as separators in versions strings"
+}
+
+strings_in_versions_test_body()
+{
+	cat > input << EOF
+pkg_install>=1.0<2.0:../../pkgtools/pkg_install
+pkg_install>1.1beta3nb2:../../pkgtools/pkg_install
+pkg_install<1.2:../../pkgtools/pkg_install
+EOF
+	cat > expected << EOF
+pkg_install>1.1beta3nb2<1.2:../../pkgtools/pkg_install
+EOF
+	check_reduce input expected
+	atf_pass
+}
+
+###
+### underscores_in_versions_test
+###
+
+atf_test_case underscores_in_versions_test
+
+underscores_in_versions_test_head()
+{
+	atf_set "descr" "underscores in versions strings"
+}
+
+underscores_in_versions_test_body()
+{
+	cat > input << EOF
+pkg_install>=1.0_beta3:../../pkgtools/pkg_install
+pkg_install<1.2:../../pkgtools/pkg_install
+EOF
+	cat > expected << EOF
+pkg_install>=1.0_beta3<1.2:../../pkgtools/pkg_install
+EOF
+	check_reduce input expected
+	atf_pass
+}
+
+###
+### multiple_package_dependencies_test
+###
+
+atf_test_case multiple_package_dependencies_test
+
+multiple_package_dependencies_test_head()
+{
+	atf_set "descr" "multiple package dependencies"
+}
+
+multiple_package_dependencies_test_body()
+{
+	cat > input << EOF
+cwrappers>1:../../pkgtools/cwrappers
+cwrappers>=1:../../pkgtools/cwrappers
+cwrappers<2:../../pkgtools/cwrappers
+cwrappers<=2:../../pkgtools/cwrappers
+pkg_install>=1.0<2.0:../../pkgtools/pkg_install
+pkg_install>1.1beta3nb2:../../pkgtools/pkg_install
+pkg_install<1.2:../../pkgtools/pkg_install
+EOF
+	cat > expected << EOF
+cwrappers>1<2:../../pkgtools/cwrappers
+pkg_install>1.1beta3nb2<1.2:../../pkgtools/pkg_install
+EOF
+	check_reduce input expected
+	atf_pass
+}
+
+atf_init_test_cases()
+{
+	atf_add_test_case skip_irreducible_depends_test
+	atf_add_test_case less_or_equal_depends_test
+	atf_add_test_case less_depends_test
+	atf_add_test_case greater_or_equal_depends_test
+	atf_add_test_case greater_depends_test
+	atf_add_test_case less_and_less_equal_same_bound_test
+	atf_add_test_case greater_and_greater_equal_same_bound_test
+	atf_add_test_case lower_and_upper_bounds_test
+	atf_add_test_case overlapping_intervals_test
+	atf_add_test_case disjoint_test
+	atf_add_test_case strings_in_versions_test
+	atf_add_test_case underscores_in_versions_test
+	atf_add_test_case multiple_package_dependencies_test
+}