qdepends: rewrite to better match forward/backward dependencies

- dep: extract dependency functions into separate files for later reuse
- by default, report all deps for all *DEPEND combined (duplicates
  removed)
- allow listing per *DEPEND using -v, pretty-print and highlight the
  atoms seleted or queried for (-Q)
- support reverse querying multiple atoms
- make -Q output match forward output, highlight the match, to just
  print the match, use -q

Bug: https://bugs.gentoo.org/682056
Signed-off-by: Fabian Groffen <grobian@gentoo.org>

16 files changed, 639 insertions, 610 deletions

diff --git a/TODO.md b/TODO.md
index 5ebd9ea..3841a8e 100644
--- a/TODO.md
+++ b/TODO.md
@@ -24,6 +24,9 @@
   we end up getting just:<br>
   `ACCEPT_LICENSE=" bar"`
 
+- q\_vdb\_foreach\_pkg should have variant that takes an atom (or just
+  cat?) to reduce search space
+
 # Atoms
 
 - only 32bit values are supported for revision (-r#)
diff --git a/libq/Makefile.am b/libq/Makefile.am
index 734a78f..765347f 100644
--- a/libq/Makefile.am
+++ b/libq/Makefile.am
@@ -7,6 +7,7 @@ QFILES = \
 	colors.c colors.h \
 	contents.c contents.h \
 	copy_file.c copy_file.h \
+	dep.c dep.h \
 	eat_file.c eat_file.h \
 	hash_fd.c hash_fd.h \
 	human_readable.c human_readable.h \
diff --git a/libq/Makefile.in b/libq/Makefile.in
index ab7012f..935747e 100644
--- a/libq/Makefile.in
+++ b/libq/Makefile.in
@@ -243,7 +243,7 @@ LTLIBRARIES = $(noinst_LTLIBRARIES)
 libq_la_LIBADD =
 am__objects_1 = libq_la-atom.lo libq_la-basename.lo libq_la-cache.lo \
 	libq_la-colors.lo libq_la-contents.lo libq_la-copy_file.lo \
-	libq_la-eat_file.lo libq_la-hash_fd.lo \
+	libq_la-dep.lo libq_la-eat_file.lo libq_la-hash_fd.lo \
 	libq_la-human_readable.lo libq_la-md5_sha1_sum.lo \
 	libq_la-prelink.lo libq_la-profile.lo libq_la-rmspace.lo \
 	libq_la-safe_io.lo libq_la-scandirat.lo libq_la-set.lo \
@@ -1450,6 +1450,7 @@ QFILES = \
 	colors.c colors.h \
 	contents.c contents.h \
 	copy_file.c copy_file.h \
+	dep.c dep.h \
 	eat_file.c eat_file.h \
 	hash_fd.c hash_fd.h \
 	human_readable.c human_readable.h \
@@ -1537,6 +1538,7 @@ distclean-compile:
 @AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/libq_la-colors.Plo@am__quote@
 @AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/libq_la-contents.Plo@am__quote@
 @AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/libq_la-copy_file.Plo@am__quote@
+@AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/libq_la-dep.Plo@am__quote@
 @AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/libq_la-eat_file.Plo@am__quote@
 @AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/libq_la-hash_fd.Plo@am__quote@
 @AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/libq_la-human_readable.Plo@am__quote@
@@ -1618,6 +1620,13 @@ libq_la-copy_file.lo: copy_file.c
 @AMDEP_TRUE@@am__fastdepCC_FALSE@	DEPDIR=$(DEPDIR) $(CCDEPMODE) $(depcomp) @AMDEPBACKSLASH@
 @am__fastdepCC_FALSE@	$(AM_V_CC@am__nodep@)$(LIBTOOL) $(AM_V_lt) --tag=CC $(AM_LIBTOOLFLAGS) $(LIBTOOLFLAGS) --mode=compile $(CC) $(DEFS) $(DEFAULT_INCLUDES) $(INCLUDES) $(libq_la_CPPFLAGS) $(CPPFLAGS) $(AM_CFLAGS) $(CFLAGS) -c -o libq_la-copy_file.lo `test -f 'copy_file.c' || echo '$(srcdir)/'`copy_file.c
 
+libq_la-dep.lo: dep.c
+@am__fastdepCC_TRUE@	$(AM_V_CC)$(LIBTOOL) $(AM_V_lt) --tag=CC $(AM_LIBTOOLFLAGS) $(LIBTOOLFLAGS) --mode=compile $(CC) $(DEFS) $(DEFAULT_INCLUDES) $(INCLUDES) $(libq_la_CPPFLAGS) $(CPPFLAGS) $(AM_CFLAGS) $(CFLAGS) -MT libq_la-dep.lo -MD -MP -MF $(DEPDIR)/libq_la-dep.Tpo -c -o libq_la-dep.lo `test -f 'dep.c' || echo '$(srcdir)/'`dep.c
+@am__fastdepCC_TRUE@	$(AM_V_at)$(am__mv) $(DEPDIR)/libq_la-dep.Tpo $(DEPDIR)/libq_la-dep.Plo
+@AMDEP_TRUE@@am__fastdepCC_FALSE@	$(AM_V_CC)source='dep.c' object='libq_la-dep.lo' libtool=yes @AMDEPBACKSLASH@
+@AMDEP_TRUE@@am__fastdepCC_FALSE@	DEPDIR=$(DEPDIR) $(CCDEPMODE) $(depcomp) @AMDEPBACKSLASH@
+@am__fastdepCC_FALSE@	$(AM_V_CC@am__nodep@)$(LIBTOOL) $(AM_V_lt) --tag=CC $(AM_LIBTOOLFLAGS) $(LIBTOOLFLAGS) --mode=compile $(CC) $(DEFS) $(DEFAULT_INCLUDES) $(INCLUDES) $(libq_la_CPPFLAGS) $(CPPFLAGS) $(AM_CFLAGS) $(CFLAGS) -c -o libq_la-dep.lo `test -f 'dep.c' || echo '$(srcdir)/'`dep.c
+
 libq_la-eat_file.lo: eat_file.c
 @am__fastdepCC_TRUE@	$(AM_V_CC)$(LIBTOOL) $(AM_V_lt) --tag=CC $(AM_LIBTOOLFLAGS) $(LIBTOOLFLAGS) --mode=compile $(CC) $(DEFS) $(DEFAULT_INCLUDES) $(INCLUDES) $(libq_la_CPPFLAGS) $(CPPFLAGS) $(AM_CFLAGS) $(CFLAGS) -MT libq_la-eat_file.lo -MD -MP -MF $(DEPDIR)/libq_la-eat_file.Tpo -c -o libq_la-eat_file.lo `test -f 'eat_file.c' || echo '$(srcdir)/'`eat_file.c
 @am__fastdepCC_TRUE@	$(AM_V_at)$(am__mv) $(DEPDIR)/libq_la-eat_file.Tpo $(DEPDIR)/libq_la-eat_file.Plo
diff --git a/libq/dep.c b/libq/dep.c
new file mode 100644
index 0000000..76d7b1e
--- /dev/null
+++ b/libq/dep.c
@@ -0,0 +1,334 @@
+/*
+ * Copyright 2005-2019 Gentoo Foundation
+ * Distributed under the terms of the GNU General Public License v2
+ *
+ * Copyright 2005-2010 Ned Ludd        - <solar@gentoo.org>
+ * Copyright 2005-2014 Mike Frysinger  - <vapier@gentoo.org>
+ * Copyright 2019-     Fabian Groffen  - <grobian@gentoo.org>
+ */
+
+#include "main.h"
+
+#include <stdio.h>
+#include <unistd.h>
+#include <stdlib.h>
+#include <string.h>
+#include <xalloc.h>
+#include <assert.h>
+#include <ctype.h>
+
+#include "atom.h"
+#include "dep.h"
+#include "set.h"
+#include "xarray.h"
+#include "xasprintf.h"
+
+static const dep_node null_node = {
+	.type = DEP_NULL,
+};
+
+static void _dep_attach(dep_node *root, dep_node *attach_me, int type);
+static void _dep_burn_node(dep_node *node);
+
+static dep_node *
+_dep_grow_node(dep_type type, const char *info, size_t info_len)
+{
+	dep_node *ret;
+	size_t len;
+
+	if (type == DEP_OR || type == DEP_GROUP)
+		info = NULL;
+
+	len = sizeof(*ret);
+	if (info) {
+		if (!info_len)
+			info_len = strlen(info);
+		len += info_len + 1;
+	}
+	ret = xzalloc(len);
+
+	ret->type = type;
+	if (info) {
+		ret->info = ((char*)ret) + sizeof(*ret);
+		memcpy(ret->info, info, info_len);
+		if (type == DEP_NORM)
+			ret->atom = atom_explode(ret->info);
+	}
+
+	return ret;
+}
+
+static void
+_dep_burn_node(dep_node *node)
+{
+	assert(node);
+	if (node->info_on_heap)
+		free(node->info);
+	if (node->atom)
+		atom_implode(node->atom);
+	free(node);
+}
+
+enum {
+	_DEP_NEIGH = 1,
+	_DEP_CHILD = 2
+};
+
+static void
+_dep_attach(dep_node *root, dep_node *attach_me, int type)
+{
+	if (type == _DEP_NEIGH) {
+		if (!root->neighbor) {
+			root->neighbor = attach_me;
+			attach_me->parent = root->parent;
+		} else
+			_dep_attach(root->neighbor, attach_me, _DEP_NEIGH);
+	} else {
+		if (!root->children) {
+			root->children = attach_me;
+			attach_me->parent = root;
+		} else
+			_dep_attach(root->children, attach_me, _DEP_NEIGH);
+	}
+}
+
+dep_node *
+dep_grow_tree(const char *depend)
+{
+	bool saw_whitespace;
+	signed long paren_balanced;
+	const char *ptr, *word;
+	int curr_attach;
+	dep_node *ret, *curr_node, *new_node;
+	dep_type prev_type;
+
+	ret = curr_node = new_node = NULL;
+	prev_type = DEP_NULL;
+	paren_balanced = 0;
+	curr_attach = _DEP_NEIGH;
+	word = NULL;
+
+#define _maybe_consume_word(t) \
+	do { \
+		if (!word) break; \
+		new_node = _dep_grow_node(t, word, ptr-word); \
+		if (!ret) \
+			ret = curr_node = new_node; \
+		else { \
+			_dep_attach(curr_node, new_node, curr_attach); \
+			curr_attach = _DEP_NEIGH; \
+			curr_node = new_node; \
+		} \
+		prev_type = t; \
+		word = NULL; \
+	} while (0)
+
+	saw_whitespace = true;
+	for (ptr = depend; *ptr; ++ptr) {
+		if (isspace(*ptr)) {
+			saw_whitespace = true;
+			_maybe_consume_word(DEP_NORM);
+			continue;
+		}
+
+		switch (*ptr) {
+		case '?': {
+			if (word == NULL) {
+				warnf("Found a ? but no USE flag");
+				goto error_out;
+			}
+			_maybe_consume_word(DEP_USE);
+			curr_attach = _DEP_CHILD;
+			continue;
+		}
+		case '|': {
+			if (!saw_whitespace)
+				break;
+			if (ptr[1] != '|') {
+				warnf("Found a | but not ||");
+				goto error_out;
+			}
+			word = ptr++;
+			_maybe_consume_word(DEP_OR);
+			curr_attach = _DEP_CHILD;
+			continue;
+		}
+		case '(': {
+			++paren_balanced;
+			if (!saw_whitespace)
+				break;
+			if (prev_type == DEP_OR || prev_type == DEP_USE) {
+				_maybe_consume_word(DEP_NORM);
+				prev_type = DEP_NULL;
+			} else {
+				if (word) {
+					warnf("New group has word in queue");
+					goto error_out;
+				}
+				word = ptr;
+				_maybe_consume_word(DEP_GROUP);
+				curr_attach = _DEP_CHILD;
+			}
+			break;
+		}
+		case ')': {
+			--paren_balanced;
+			if (!saw_whitespace)
+				break;
+			_maybe_consume_word(DEP_NORM);
+
+			if (curr_node->parent == NULL) {
+				warnf("Group lacks a parent");
+				goto error_out;
+			}
+			curr_node = curr_node->parent;
+			curr_attach = _DEP_NEIGH;
+			break;
+		}
+		default:
+			if (!word)
+				word = ptr;
+		}
+		saw_whitespace = false;
+
+		/* fall through to the paren failure below */
+		if (paren_balanced < 0)
+			break;
+	}
+
+	if (paren_balanced != 0) {
+		warnf("Parenthesis unbalanced");
+		goto error_out;
+	}
+
+	/* if the depend buffer wasnt terminated with a space,
+	 * we may have a word sitting in the buffer to consume */
+	_maybe_consume_word(DEP_NORM);
+
+#undef _maybe_consume_word
+
+	return ret ? : xmemdup(&null_node, sizeof(null_node));
+
+error_out:
+	warnf("DEPEND: %s", depend);
+	if (ret) {
+		dep_dump_tree(ret);
+		dep_burn_tree(ret);
+	}
+	return NULL;
+}
+
+void
+dep_print_tree(
+		FILE *fp,
+		const dep_node *root,
+		size_t space,
+		array_t *hlatoms,
+		const char *hlcolor,
+		int verbose)
+{
+	size_t s;
+	int indent = 4;  /* Gentoo 4-wide indent standard */
+	depend_atom *d = NULL;
+
+	assert(root);
+	if (root->type == DEP_NULL)
+		goto this_node_sucks;
+
+	for (s = space; s; --s)
+		fprintf(fp, "%*s", indent, "");
+
+	if (verbose > 0)
+		fprintf(fp, "Node [%s]: ", _dep_names[root->type]);
+	/*printf("Node %p [%s] %p %p %p: ", root, _dep_names[root->type], root->parent, root->neighbor, root->children);*/
+	if (root->type == DEP_OR)
+		fprintf(fp, "|| (");
+	if (root->info) {
+		if (hlatoms != NULL && root->type == DEP_NORM) {
+			size_t i;
+			depend_atom *m;
+			char *oslot;
+
+			d = root->atom;
+			d->pfx_op = d->sfx_op = ATOM_OP_NONE;
+
+			array_for_each(hlatoms, i, m) {
+				oslot = d->SLOT;
+				if (m->SLOT == NULL)
+					d->SLOT = NULL;
+
+				if (atom_compare(m, d) == EQUAL) {
+					m = NULL;
+					break;
+				}
+				d->SLOT = oslot;
+			}
+
+			if (m == NULL) { /* match found */
+				fprintf(fp, "%s%s%s", hlcolor, root->info, NORM);
+			} else {
+				fprintf(fp, "%s", root->info);
+			}
+		} else {
+			fprintf(fp, "%s", root->info);
+		}
+		/* If there is only one child, be nice to one-line: foo? ( pkg ) */
+		if (root->type == DEP_USE)
+			fprintf(fp, "? (");
+	}
+	fprintf(fp, "\n");
+
+	if (root->children)
+		dep_print_tree(fp, root->children, space+1, hlatoms, hlcolor, verbose);
+
+	if (root->type == DEP_OR || root->type == DEP_USE) {
+		for (s = space; s; --s)
+			fprintf(fp, "%*s", indent, "");
+		fprintf(fp, ")\n");
+	}
+ this_node_sucks:
+	if (root->neighbor)
+		dep_print_tree(fp, root->neighbor, space, hlatoms, hlcolor, verbose);
+}
+
+void
+dep_burn_tree(dep_node *root)
+{
+	assert(root);
+	if (root->children)
+		dep_burn_tree(root->children);
+	if (root->neighbor)
+		dep_burn_tree(root->neighbor);
+	_dep_burn_node(root);
+}
+
+void
+dep_prune_use(dep_node *root, set *use)
+{
+	if (root->neighbor)
+		dep_prune_use(root->neighbor, use);
+	if (root->type == DEP_USE) {
+		bool invert = (root->info[0] == '!' ? 1 : 0);
+		bool notfound = contains_set(root->info + (invert ? 1 : 0), use);
+
+		if (notfound ^ invert) {
+			root->type = DEP_NULL;
+			return;
+		}
+	}
+	if (root->children)
+		dep_prune_use(root->children, use);
+}
+
+void
+dep_flatten_tree(const dep_node *root, array_t *out)
+{
+	if (root->type != DEP_NULL) {
+		if (root->type == DEP_NORM)
+			xarraypush_ptr(out, root->atom);
+		if (root->children)
+			dep_flatten_tree(root->children, out);
+	}
+	if (root->neighbor)
+		dep_flatten_tree(root->neighbor, out);
+}
diff --git a/libq/dep.h b/libq/dep.h
new file mode 100644
index 0000000..1055d29
--- /dev/null
+++ b/libq/dep.h
@@ -0,0 +1,54 @@
+/*
+ * Copyright 2005-2019 Gentoo Foundation
+ * Distributed under the terms of the GNU General Public License v2
+ */
+
+#ifndef _DEP_H
+#define _DEP_H 1
+
+#include "atom.h"
+#include "colors.h"
+#include "set.h"
+#include "xarray.h"
+
+typedef enum {
+	DEP_NULL = 0,
+	DEP_NORM = 1,
+	DEP_USE = 2,
+	DEP_OR = 3,
+	DEP_GROUP = 4
+} dep_type;
+
+static const char * const _dep_names[] = {
+	"NULL",
+	"NORM",
+	"USE",
+	"OR",
+	"GROUP"
+};
+
+struct _dep_node {
+	dep_type type;
+	char *info;
+	char info_on_heap;
+	depend_atom *atom;
+	struct _dep_node *parent;
+	struct _dep_node *neighbor;
+	struct _dep_node *children;
+};
+typedef struct _dep_node dep_node;
+
+/* prototypes */
+#ifdef NDEBUG
+# define dep_dump_tree(r)
+#else
+# define dep_dump_tree(r) dep_print_tree(stdout, r, 0, NULL, NORM, 0)
+#endif
+
+dep_node *dep_grow_tree(const char *depend);
+void dep_print_tree(FILE *fp, const dep_node *root, size_t space, array_t *m, const char *c, int verbose);
+void dep_burn_tree(dep_node *root);
+void dep_prune_use(dep_node *root, set *use);
+void dep_flatten_tree(const dep_node *root, array_t *out);
+
+#endif
diff --git a/libq/set.c b/libq/set.c
index 7adbce7..de60410 100644
--- a/libq/set.c
+++ b/libq/set.c
@@ -72,6 +72,7 @@ add_set_unique(const char *name, set *q, bool *unique)
 	int pos;
 	elem *ll;
 	elem *w;
+	bool uniq = false;
 
 	if (q == NULL)
 		q = create_set();
@@ -85,13 +86,13 @@ add_set_unique(const char *name, set *q, bool *unique)
 		ll->next = NULL;
 		ll->name = mname;
 		ll->hash = hash;
-		*unique = true;
+		uniq = true;
 	} else {
 		ll = NULL;
 		for (w = q->buckets[pos]; w != NULL; ll = w, w = w->next) {
 			if (w->hash == hash && strcmp(w->name, mname) == 0) {
 				free(mname);
-				*unique = false;
+				uniq = false;
 				break;
 			}
 		}
@@ -100,12 +101,14 @@ add_set_unique(const char *name, set *q, bool *unique)
 			ll->next = NULL;
 			ll->name = mname;
 			ll->hash = hash;
-			*unique = true;
+			uniq = true;
 		}
 	}
 
-	if (*unique)
+	if (uniq)
 		q->len++;
+	if (unique)
+		*unique = uniq;
 	return q;
 }
 
@@ -199,7 +202,7 @@ list_set(set *q, char ***l)
 
 /* clear out a set */
 void
-free_set(set *q)
+clear_set(set *q)
 {
 	int i;
 	elem *w;
@@ -211,7 +214,16 @@ free_set(set *q)
 			free(w->name);
 			free(w);
 		}
+		q->buckets[i] = NULL;
 	}
+	q->len = 0;
+}
+
+/* clear and free a set */
+void
+free_set(set *q)
+{
+	clear_set(q);
 	free(q);
 }
 
diff --git a/libq/set.h b/libq/set.h
index 27e30ad..7ca5f65 100644
--- a/libq/set.h
+++ b/libq/set.h
@@ -32,5 +32,6 @@ bool contains_set(char *s, set *q);
 set *del_set(char *s, set *q, bool *removed);
 size_t list_set(set *q, char ***l);
 void free_set(set *q);
+void clear_set(set *q);
 
 #endif
diff --git a/qdepends.c b/qdepends.c
index ca82f08..df3434e 100644
--- a/qdepends.c
+++ b/qdepends.c
@@ -15,34 +15,31 @@
 #include <assert.h>
 
 #include "atom.h"
+#include "dep.h"
 #include "set.h"
 #include "vdb.h"
 #include "xarray.h"
 #include "xasprintf.h"
 #include "xregex.h"
 
-#define QDEPENDS_FLAGS "drpbafNk:Q:" COMMON_FLAGS
+#define QDEPENDS_FLAGS "drpbfNQu" COMMON_FLAGS
 static struct option const qdepends_long_opts[] = {
 	{"depend",    no_argument, NULL, 'd'},
 	{"rdepend",   no_argument, NULL, 'r'},
 	{"pdepend",   no_argument, NULL, 'p'},
 	{"bdepend",   no_argument, NULL, 'b'},
-	{"key",        a_argument, NULL, 'k'},
-	{"query",      a_argument, NULL, 'Q'},
+	{"query",     no_argument, NULL, 'Q'},
 	{"name-only", no_argument, NULL, 'N'},
-	{"all",       no_argument, NULL, 'a'},
 	{"format",    no_argument, NULL, 'f'},
 	COMMON_LONG_OPTS
 };
 static const char * const qdepends_opts_help[] = {
-	"Show DEPEND info (default)",
+	"Show DEPEND info",
 	"Show RDEPEND info",
 	"Show PDEPEND info",
 	"Show BDEPEND info",
-	"User defined vdb key",
 	"Query reverse deps",
 	"Only show package name",
-	"Show all DEPEND info",
 	"Pretty format specified depend strings",
 	COMMON_OPTS_HELP
 };
@@ -51,278 +48,31 @@ static const char * const qdepends_opts_help[] = {
 static char qdep_name_only = 0;
 
 /* structures / types / etc ... */
-typedef enum {
-	DEP_NULL = 0,
-	DEP_NORM = 1,
-	DEP_USE = 2,
-	DEP_OR = 3,
-	DEP_GROUP = 4
-} dep_type;
-static const char * const _dep_names[] = { "NULL", "NORM", "USE", "OR", "GROUP" };
-
-struct _dep_node {
-	dep_type type;
-	char *info;
-	char info_on_heap;
-	depend_atom *atom;
-	struct _dep_node *parent;
-	struct _dep_node *neighbor;
-	struct _dep_node *children;
-};
-typedef struct _dep_node dep_node;
-
-static const dep_node null_node = {
-	.type = DEP_NULL,
+struct qdepends_opt_state {
+	unsigned char qmode;
+	array_t *atoms;
+	array_t *deps;
+	set *udeps;
+	char *depend;
+	size_t depend_len;
 };
 
-/* prototypes */
-#ifdef NDEBUG
-# define dep_dump_tree(r)
-#else
-# define dep_dump_tree(r) _dep_print_tree(stdout, r, 0)
-#endif
-static void _dep_print_tree(FILE *fp, const dep_node *root, size_t space);
-static void dep_burn_tree(dep_node *root);
-static char *dep_flatten_tree(const dep_node *root);
-static void _dep_attach(dep_node *root, dep_node *attach_me, int type);
-static void _dep_burn_node(dep_node *node);
-
-#ifdef EBUG
-static void
-print_word(const char *ptr, size_t num)
-{
-	while (num--)
-		printf("%c", *ptr++);
-	printf("\n");
-}
-#endif
-
-static dep_node *
-_dep_grow_node(dep_type type, const char *info, size_t info_len)
-{
-	dep_node *ret;
-	size_t len;
-
-	if (type == DEP_OR || type == DEP_GROUP)
-		info = NULL;
-
-	len = sizeof(*ret);
-	if (info) {
-		if (!info_len)
-			info_len = strlen(info);
-		len += info_len + 1;
-	}
-	ret = xzalloc(len);
-
-	ret->type = type;
-	if (info) {
-		ret->info = ((char*)ret) + sizeof(*ret);
-		memcpy(ret->info, info, info_len);
-		if (type == DEP_NORM)
-			ret->atom = atom_explode(info);
-	}
-
-	return ret;
-}
-
-static void
-_dep_burn_node(dep_node *node)
-{
-	assert(node);
-	if (node->info_on_heap) free(node->info);
-	if (node->atom) atom_implode(node->atom);
-	free(node);
-}
-
-enum {
-	_DEP_NEIGH = 1,
-	_DEP_CHILD = 2
+#define QMODE_DEPEND     (1<<0)
+#define QMODE_RDEPEND    (1<<1)
+#define QMODE_PDEPEND    (1<<2)
+#define QMODE_BDEPEND    (1<<3)
+#define QMODE_REVERSE    (1<<7)
+
+const char *depend_files[] = {  /* keep *DEPEND aligned with above defines */
+	/* 0 */ "DEPEND",
+	/* 1 */ "RDEPEND",
+	/* 2 */ "PDEPEND",
+	/* 3 */ "BDEPEND",
+	/* 4 */ NULL
 };
 
-static void
-_dep_attach(dep_node *root, dep_node *attach_me, int type)
-{
-	if (type == _DEP_NEIGH) {
-		if (!root->neighbor) {
-			root->neighbor = attach_me;
-			attach_me->parent = root->parent;
-		} else
-			_dep_attach(root->neighbor, attach_me, _DEP_NEIGH);
-	} else {
-		if (!root->children) {
-			root->children = attach_me;
-			attach_me->parent = root;
-		} else
-			_dep_attach(root->children, attach_me, _DEP_NEIGH);
-	}
-}
-
-static dep_node *
-dep_grow_tree(const char *depend)
-{
-	bool saw_whitespace;
-	signed long paren_balanced;
-	const char *ptr, *word;
-	int curr_attach;
-	dep_node *ret, *curr_node, *new_node;
-	dep_type prev_type;
-
-	ret = curr_node = new_node = NULL;
-	prev_type = DEP_NULL;
-	paren_balanced = 0;
-	curr_attach = _DEP_NEIGH;
-	word = NULL;
-
-#define _maybe_consume_word(t) \
-	do { \
-	if (!word) break; \
-	new_node = _dep_grow_node(t, word, ptr-word); \
-	if (!ret) \
-		ret = curr_node = new_node; \
-	else { \
-		_dep_attach(curr_node, new_node, curr_attach); \
-		curr_attach = _DEP_NEIGH; \
-		curr_node = new_node; \
-	} \
-	prev_type = t; \
-	word = NULL; \
-	} while (0)
-
-	saw_whitespace = true;
-	for (ptr = depend; *ptr; ++ptr) {
-		if (isspace(*ptr)) {
-			saw_whitespace = true;
-			_maybe_consume_word(DEP_NORM);
-			continue;
-		}
-
-		switch (*ptr) {
-		case '?': {
-			if (word == NULL) {
-				warnf("Found a ? but no USE flag");
-				goto error_out;
-			}
-			_maybe_consume_word(DEP_USE);
-			curr_attach = _DEP_CHILD;
-			continue;
-		}
-		case '|': {
-			if (!saw_whitespace)
-				break;
-			if (ptr[1] != '|') {
-				warnf("Found a | but not ||");
-				goto error_out;
-			}
-			word = ptr++;
-			_maybe_consume_word(DEP_OR);
-			curr_attach = _DEP_CHILD;
-			continue;
-		}
-		case '(': {
-			++paren_balanced;
-			if (!saw_whitespace)
-				break;
-			if (prev_type == DEP_OR || prev_type == DEP_USE) {
-				_maybe_consume_word(DEP_NORM);
-				prev_type = DEP_NULL;
-			} else {
-				if (word) {
-					warnf("New group has word in queue");
-					goto error_out;
-				}
-				word = ptr;
-				_maybe_consume_word(DEP_GROUP);
-				curr_attach = _DEP_CHILD;
-			}
-			break;
-		}
-		case ')': {
-			--paren_balanced;
-			if (!saw_whitespace)
-				break;
-			_maybe_consume_word(DEP_NORM);
-
-			if (curr_node->parent == NULL) {
-				warnf("Group lacks a parent");
-				goto error_out;
-			}
-			curr_node = curr_node->parent;
-			curr_attach = _DEP_NEIGH;
-			break;
-		}
-		default:
-			if (!word)
-				word = ptr;
-		}
-		saw_whitespace = false;
-
-		/* fall through to the paren failure below */
-		if (paren_balanced < 0)
-			break;
-	}
-
-	if (paren_balanced != 0) {
-		warnf("Parenthesis unbalanced");
-		goto error_out;
-	}
-
-	/* if the depend buffer wasnt terminated with a space,
-	 * we may have a word sitting in the buffer to consume */
-	_maybe_consume_word(DEP_NORM);
-
-#undef _maybe_consume_word
-
-	return ret ? : xmemdup(&null_node, sizeof(null_node));
-
-error_out:
-	warnf("DEPEND: %s", depend);
-	if (ret) {
-		dep_dump_tree(ret);
-		dep_burn_tree(ret);
-	}
-	return NULL;
-}
-
-static void
-_dep_print_tree(FILE *fp, const dep_node *root, size_t space)
-{
-	size_t s;
-
-	assert(root);
-	if (root->type == DEP_NULL)
-		goto this_node_sucks;
-
-	for (s = space; s; --s)
-		fprintf(fp, "\t");
-
-	if (verbose > 1)
-		fprintf(fp, "Node [%s]: ", _dep_names[root->type]);
-	/*printf("Node %p [%s] %p %p %p: ", root, _dep_names[root->type], root->parent, root->neighbor, root->children);*/
-	if (root->type == DEP_OR)
-		fprintf(fp, "|| (");
-	if (root->info) {
-		fprintf(fp, "%s", root->info);
-		/* If there is only one child, be nice to one-line: foo? ( pkg ) */
-		if (root->type == DEP_USE)
-			fprintf(fp, "? (");
-	}
-	fprintf(fp, "\n");
-
-	if (root->children)
-		_dep_print_tree(fp, root->children, space+1);
-
-	if (root->type == DEP_OR || root->type == DEP_USE) {
-		for (s = space; s; --s)
-			fprintf(fp, "\t");
-		fprintf(fp, ")\n");
-	}
- this_node_sucks:
-	if (root->neighbor)
-		_dep_print_tree(fp, root->neighbor, space);
-}
-
 static bool
-dep_print_depend(FILE *fp, const char *depend)
+qdepends_print_depend(FILE *fp, const char *depend)
 {
 	dep_node *dep_tree;
 
@@ -333,7 +83,7 @@ dep_print_depend(FILE *fp, const char *depend)
 	if (!quiet)
 		fprintf(fp, "DEPEND=\"\n");
 
-	_dep_print_tree(fp, dep_tree, 1);
+	dep_print_tree(fp, dep_tree, 1, NULL, NORM, verbose > 1);
 
 	dep_burn_tree(dep_tree);
 	if (!quiet)
@@ -342,346 +92,210 @@ dep_print_depend(FILE *fp, const char *depend)
 	return true;
 }
 
-static void
-dep_burn_tree(dep_node *root)
-{
-	assert(root);
-	if (root->children) dep_burn_tree(root->children);
-	if (root->neighbor) dep_burn_tree(root->neighbor);
-	_dep_burn_node(root);
-}
-
-static void
-dep_prune_use(dep_node *root, const char *use)
-{
-	if (root->neighbor) dep_prune_use(root->neighbor, use);
-	if (root->type == DEP_USE) {
-		char *useflag = NULL;
-		int notfound, invert = (root->info[0] == '!' ? 1 : 0);
-		xasprintf(&useflag, " %s ", root->info+invert);
-		notfound = (strstr(use, useflag) == NULL ? 1 : 0);
-		free(useflag);
-		if (notfound ^ invert) {
-			root->type = DEP_NULL;
-			return;
-		}
-	}
-	if (root->children) dep_prune_use(root->children, use);
-}
-
-static char *
-_dep_flatten_tree(const dep_node *root, char *buf)
-{
-	if (root->type != DEP_NULL) {
-		if (root->type == DEP_NORM)
-			buf += sprintf(buf, " %s", root->info);
-		if (root->children)
-			buf = _dep_flatten_tree(root->children, buf);
-	}
-	if (root->neighbor)
-		buf = _dep_flatten_tree(root->neighbor, buf);
-	return buf;
-}
-
-static char *
-dep_flatten_tree(const dep_node *root)
-{
-	static char flat[1024 * 1024];
-	char *buf = _dep_flatten_tree(root, flat);
-	if (buf == flat) {
-		/* all the nodes were squashed ... for example:
-		 * USE=-selinux RDEPEND="selinux? ( sys-libs/libselinux )"
-		 */
-		return NULL;
-	}
-	return flat + 1;
-}
-
-struct qdepends_opt_state {
-	array_t *atoms;
-	const char *depend_file;
-	const char *query;
-};
-
 static int
-qdepends_main_vdb_cb(q_vdb_pkg_ctx *pkg_ctx, void *priv)
+qdepends_results_cb(q_vdb_pkg_ctx *pkg_ctx, void *priv)
 {
 	struct qdepends_opt_state *state = priv;
 	const char *catname = pkg_ctx->cat_ctx->name;
 	const char *pkgname = pkg_ctx->name;
-	size_t i, len;
-	int ret;
-	char *ptr;
+	depend_atom *atom;
+	depend_atom *datom;
+	depend_atom *fatom;
+	bool firstmatch = false;
 	char buf[_Q_PATH_MAX];
-	static char *depend, *use;
-	static size_t depend_len, use_len;
-	depend_atom *atom, *datom;
+	const char **dfile;
+	size_t i;
+	size_t n;
+	size_t m;
+	int ret = 0;
 	dep_node *dep_tree;
-
-	datom = NULL;
-	ret = 0;
-
-	/* see if this cat/pkg is requested */
-	array_for_each(state->atoms, i, atom) {
-		bool matched = false;
-		snprintf(buf, sizeof(buf), "%s/%s", catname, pkgname);
-		datom = atom_explode(buf);
-		if (datom) {
-			matched = (atom_compare(atom, datom) == EQUAL);
-			if (matched)
-				goto matched;
+	char **d;
+
+	/* matrix consists of:
+	 * - QMODE_*DEPEND
+	 * - QMODE_REVERSE or not
+	 *
+	 * REVERSE vs forward mode requires a different search strategy,
+	 * *DEPEND alters the search somewhat and affects results printing.
+	 */
+
+	snprintf(buf, sizeof(buf), "%s/%s", catname, pkgname);
+	datom = atom_explode(buf);
+	if (datom == NULL)
+		return ret;
+
+	if ((state->qmode & QMODE_REVERSE) == 0) {
+		/* see if this cat/pkg is requested */
+		array_for_each(state->atoms, i, atom) {
+			if (atom_compare(atom, datom) == EQUAL) {
+				atom = NULL;
+				break;
+			}
 		}
-		atom_implode(datom);
-	}
-	return ret;
- matched:
 
-	if (!q_vdb_pkg_eat(pkg_ctx, state->depend_file, &depend, &depend_len))
-		goto done;
-
-	dep_tree = dep_grow_tree(depend);
-	if (dep_tree == NULL)
-		goto done;
-
-	if (qdep_name_only)
-		printf("%s%s/%s%s%s: ", BOLD, catname, BLUE, atom->PN, NORM);
-	else
-		printf("%s%s/%s%s%s: ", BOLD, catname, BLUE, pkgname, NORM);
-
-	if (!q_vdb_pkg_eat(pkg_ctx, "USE", &use, &use_len)) {
-		warn("Could not eat_file(%s), you'll prob have incorrect output", buf);
-	} else {
-		for (ptr = use; *ptr; ++ptr)
-			if (*ptr == '\n' || *ptr == '\t')
-				*ptr = ' ';
-		len = ptr - use;
-		if (len + 1 >= use_len) {
-			use_len += BUFSIZE;
-			use = xrealloc(use, use_len);
+		/* nothing matched */
+		if (atom != NULL) {
+			atom_implode(datom);
+			return ret;
 		}
-		use[len] = ' ';
-		use[len+1] = '\0';
-		memmove(use+1, use, len);
-		use[0] = ' ';
-
-		dep_prune_use(dep_tree, use);
-	}
-
-	/*dep_dump_tree(dep_tree);*/
-	ptr = dep_flatten_tree(dep_tree);
-	printf("%s\n", (ptr == NULL ? "" : ptr));
-
-	dep_burn_tree(dep_tree);
-
-	ret = 1;
 
- done:
-	atom_implode(datom);
-	return ret;
-}
+		ret = 1;
 
-static int
-qdepends_vdb_deep_cb(q_vdb_pkg_ctx *pkg_ctx, void *priv)
-{
-	struct qdepends_opt_state *state = priv;
-	const char *catname = pkg_ctx->cat_ctx->name;
-	const char *pkgname = pkg_ctx->name;
-	size_t len;
-	char *ptr;
-	char qbuf[_Q_PATH_MAX];
-	static char *depend, *use;
-	static size_t depend_len, use_len;
-	dep_node *dep_tree;
-	int ret;
-	regex_t preg;
-	regmatch_t match;
-	depend_atom *aq;
-	depend_atom *as;
-	depend_atom *ac;
-	char firstmatch = 0;
-	char *sslot;
-
-	if (!q_vdb_pkg_eat(pkg_ctx, state->depend_file, &depend, &depend_len))
-		return 0;
-
-	dep_tree = dep_grow_tree(depend);
-	if (dep_tree == NULL)
-		return 0;
-
-	if (q_vdb_pkg_eat(pkg_ctx, "USE", &use, &use_len))
-		use[0] = '\0';
-
-	for (ptr = use; *ptr; ++ptr)
-		if (*ptr == '\n' || *ptr == '\t')
-			*ptr = ' ';
-	len = ptr - use;
-	if (len + 1 >= use_len) {
-		use_len += BUFSIZE;
-		use = xrealloc(use, use_len);
+		printf("%s%s/%s%s%s:", BOLD, catname, BLUE,
+				qdep_name_only ? datom->PN : pkgname, NORM);
 	}
-	use[len] = ' ';
-	use[len+1] = '\0';
-	memmove(use+1, use, len);
-	use[0] = ' ';
 
-	dep_prune_use(dep_tree, use);
+	xarrayfree_int(state->deps);
+	clear_set(state->udeps);
 
-	if ((ptr = dep_flatten_tree(dep_tree)) == NULL) {
-		dep_burn_tree(dep_tree);
-		return 1;
-	}
-
-	snprintf(qbuf, sizeof(qbuf), "%s/%s", catname, pkgname);
-	as = atom_explode(qbuf);
-	if (!as) {
-		dep_burn_tree(dep_tree);
-		return 1;
-	}
-
-	aq = atom_explode(state->query);
-	if (!aq) {
-		/* "fall" back to old behaviour of just performing an extended
-		 * regular expression match */
-		if (wregcomp(&preg, state->query, REG_EXTENDED) != 0) {
-			dep_burn_tree(dep_tree);
-			return 1;
-		}
-	}
+	dfile = depend_files;
+	for (i = QMODE_DEPEND; i <= QMODE_BDEPEND; i <<= 1, dfile++) {
+		if (!(state->qmode & i))
+			continue;
+		if (!q_vdb_pkg_eat(pkg_ctx, *dfile,
+					&state->depend, &state->depend_len))
+			continue;
 
-	match.rm_eo = 0;
-	firstmatch = 1;
-	do {  /* find all matches */
-		if (!aq) {
-			ret = regexec(&preg, ptr + match.rm_eo, 1, &match, 0);
-		} else {
-			char *loc;
-			ret = -1;
-			snprintf(qbuf, sizeof(qbuf), "%s%s%s",
-					aq->CATEGORY ? aq->CATEGORY : "",
-					aq->CATEGORY ? "/" : "",
-					aq->PN);
-			if ((loc = strstr(ptr + match.rm_eo, qbuf)) != NULL) {
-				ret = 0;
-				match.rm_so = loc - ptr;
-				match.rm_eo = match.rm_so + strlen(qbuf);
-			}
-		}
-		if (ret != 0)
-			break;
-
-		/* find the boundaries for matched atom, dep specifications can
-		 * include built-with-use deps using [xxx] notation, so ensure
-		 * we exclude that as part of the atom */
-		while (match.rm_so > 0 && !isspace(ptr[match.rm_so - 1]))
-			match.rm_so--;
-		while (ptr[match.rm_eo] != '\0' && ptr[match.rm_eo] != '[' &&
-				!isspace(ptr[match.rm_eo]))
-			match.rm_eo++;
-
-		snprintf(qbuf, sizeof(qbuf), "%.*s",
-					(int)(match.rm_eo - match.rm_so),
-					ptr + match.rm_so);
-		ac = atom_explode(qbuf);
-
-		/* drop SLOT when not present in aq so we can match atoms
-		 * regardless */
-		sslot = ac->SLOT;
-		if (aq->SLOT == NULL && ac->SLOT != NULL)
-			ac->SLOT = NULL;
-		ret = atom_compare(ac, aq);
-		ac->SLOT = sslot;
-		if (ret != EQUAL) {
-			atom_implode(ac);
-			break;
-		}
+		dep_tree = dep_grow_tree(state->depend);
+		if (dep_tree == NULL)
+			continue;
 
-		if (firstmatch == 1) {
-			firstmatch = 0;
-			printf("%s%s/%s%s%s%c", BOLD, catname, BLUE,
-					qdep_name_only ? as->PN : pkgname, NORM,
-					verbose ? ':' : '\n');
-		}
+		dep_flatten_tree(dep_tree, state->deps);
 
 		if (verbose) {
-			printf(" ");
-			if (ac) {
-				printf("%s", atom_op_str[ac->pfx_op]);
-				if (ac->CATEGORY)
-					printf("%s/", ac->CATEGORY);
-				printf("%s", ac->P);
-				if (ac->PR_int)
-					printf("-r%i", ac->PR_int);
-				printf("%s", atom_op_str[ac->sfx_op]);
-				if (ac->SLOT)
-					printf(":%s", ac->SLOT);
-				atom_implode(ac);
+			if (state->qmode & QMODE_REVERSE) {
+				array_for_each(state->atoms, m, atom) {
+					array_for_each(state->deps, n, fatom) {
+						if (atom_compare(atom, fatom) == EQUAL) {
+							fatom = NULL;
+							break;
+						}
+					}
+					if (fatom == NULL) {
+						atom = NULL;
+						break;
+					}
+				}
+				if (atom == NULL) {
+					ret = 1;
+
+					if (!firstmatch) {
+						printf("%s%s/%s%s%s:",
+								BOLD, catname, BLUE,
+								qdep_name_only ? datom->PN : pkgname, NORM);
+					}
+					firstmatch = true;
+
+					printf("\n%s=\"\n", *dfile);
+					dep_print_tree(stdout, dep_tree, 1, state->atoms,
+							RED, verbose > 1);
+					printf("\"");
+				}
 			} else {
-				printf("%s", qbuf);
+				printf("\n%s=\"\n", *dfile);
+				dep_print_tree(stdout, dep_tree, 1, state->deps,
+						GREEN, verbose > 1);
+				printf("\"");
 			}
 		} else {
-			/* if not verbose, we don't care about any extra matches */
-			atom_implode(ac);
-			break;
+			if (state->qmode & QMODE_REVERSE) {
+				array_for_each(state->deps, m, atom) {
+					array_for_each(state->atoms, n, fatom) {
+						if (atom_compare(atom, fatom) == EQUAL) {
+							fatom = NULL;
+							break;
+						}
+					}
+					if (fatom == NULL) {
+						ret = 1;
+
+						if (!firstmatch) {
+							printf("%s%s/%s%s%s%s",
+									BOLD, catname, BLUE,
+									qdep_name_only ? datom->PN : pkgname, NORM,
+									quiet ? "" : ":");
+						}
+						firstmatch = true;
+
+						snprintf(buf, sizeof(buf), "%s%s%s",
+								RED, atom_to_string(atom), NORM);
+						add_set_unique(buf, state->udeps, NULL);
+					} else if (!quiet) {
+						add_set_unique(atom_to_string(atom),
+								state->udeps, NULL);
+					}
+				}
+			} else {
+				array_for_each(state->deps, m, atom)
+					add_set_unique(atom_to_string(atom), state->udeps, NULL);
+			}
 		}
-	} while (1);
-	if (verbose && firstmatch == 0)
+
+		xarrayfree_int(state->deps);
+		dep_burn_tree(dep_tree);
+	}
+	if (verbose && ret == 1)
 		printf("\n");
 
-	if (!aq) {
-		regfree(&preg);
-	} else {
-		atom_implode(aq);
+	if (!verbose) {
+		if ((state->qmode & QMODE_REVERSE) == 0 || ret == 1) {
+			for (n = list_set(state->udeps, &d); n > 0; n--)
+				printf(" %s", d[n -1]);
+			free(d);
+			printf("\n");
+		}
 	}
-	atom_implode(as);
-	dep_burn_tree(dep_tree);
 
-	return 1;
+	atom_implode(datom);
+
+	return ret;
 }
 
 int qdepends_main(int argc, char **argv)
 {
 	depend_atom *atom;
 	DECLARE_ARRAY(atoms);
+	DECLARE_ARRAY(deps);
 	struct qdepends_opt_state state = {
 		.atoms = atoms,
+		.deps = deps,
+		.udeps = create_set(),
+		.qmode = 0,
+		.depend = NULL,
+		.depend_len = 0,
 	};
-	q_vdb_pkg_cb *cb;
 	size_t i;
 	int ret;
 	bool do_format = false;
-	const char *query = NULL;
-	const char *depend_file;
-	const char *depend_files[] = {
-		/* 0 */ "DEPEND",
-		/* 1 */ "RDEPEND",
-		/* 2 */ "PDEPEND",
-		/* 3 */ "BDEPEND",
-		/* 4 */ NULL
-	};
-
-	depend_file = depend_files[0];
 
 	while ((ret = GETOPT_LONG(QDEPENDS, qdepends, "")) != -1) {
 		switch (ret) {
 		COMMON_GETOPTS_CASES(qdepends)
 
-		case 'd': depend_file = depend_files[0]; break;
-		case 'r': depend_file = depend_files[1]; break;
-		case 'p': depend_file = depend_files[2]; break;
-		case 'b': depend_file = depend_files[3]; break;
-		case 'k': depend_file = optarg; break;
-		case 'a': depend_file = NULL; break;
-		case 'Q': query = optarg; break;
+		case 'd': state.qmode |= QMODE_DEPEND;  break;
+		case 'r': state.qmode |= QMODE_RDEPEND; break;
+		case 'p': state.qmode |= QMODE_PDEPEND; break;
+		case 'b': state.qmode |= QMODE_BDEPEND; break;
+		case 'Q': state.qmode |= QMODE_REVERSE; break;
 		case 'N': qdep_name_only = 1; break;
 		case 'f': do_format = true; break;
 		}
 	}
-	if ((argc == optind) && (query == NULL) && !do_format)
+
+	if ((state.qmode & ~QMODE_REVERSE) == 0) {
+		/* default mode of operation: -qau (also for just -Q) */
+		state.qmode |= QMODE_DEPEND  |
+					   QMODE_RDEPEND |
+					   QMODE_PDEPEND |
+					   QMODE_BDEPEND;
+	}
+
+	if ((argc == optind) && !do_format)
 		qdepends_usage(EXIT_FAILURE);
 
 	if (do_format) {
 		while (optind < argc) {
-			if (!dep_print_depend(stdout, argv[optind++]))
+			if (!qdepends_print_depend(stdout, argv[optind++]))
 				return EXIT_FAILURE;
 			if (optind < argc)
 				fprintf(stdout, "\n");
@@ -692,35 +306,25 @@ int qdepends_main(int argc, char **argv)
 	argc -= optind;
 	argv += optind;
 
-	state.depend_file = depend_file;
-	state.query = query;
-	if (query)
-		cb = qdepends_vdb_deep_cb;
-	else {
-		cb = qdepends_main_vdb_cb;
-
-		for (i = 0; i < (size_t)argc; ++i) {
-			atom = atom_explode(argv[i]);
-			if (!atom)
-				warn("invalid atom: %s", argv[i]);
-			else
-				xarraypush_ptr(atoms, atom);
-		}
+	for (i = 0; i < (size_t)argc; ++i) {
+		atom = atom_explode(argv[i]);
+		if (!atom)
+			warn("invalid atom: %s", argv[i]);
+		else
+			xarraypush_ptr(atoms, atom);
 	}
 
-	if (!depend_file) {
-		ret = 0;
-		for (i = 0; depend_files[i]; ++i) {
-			printf(" %s*%s %s\n", GREEN, NORM, depend_files[i]);
-			state.depend_file = depend_files[i];
-			ret |= q_vdb_foreach_pkg(portroot, portvdb, cb, &state, NULL);
-		}
-	} else
-		ret = q_vdb_foreach_pkg(portroot, portvdb, cb, &state, NULL);
+	ret = q_vdb_foreach_pkg(portroot, portvdb,
+			qdepends_results_cb, &state, NULL);
+
+	if (state.depend != NULL)
+		free(state.depend);
 
 	array_for_each(atoms, i, atom)
 		atom_implode(atom);
 	xarrayfree_int(atoms);
+	xarrayfree_int(state.deps);
+	free_set(state.udeps);
 
 	if (!ret)
 		warn("no matches found for your query");
diff --git a/tests/qdepends/dotest b/tests/qdepends/dotest
index 672fb15..41a4edd 100755
--- a/tests/qdepends/dotest
+++ b/tests/qdepends/dotest
@@ -21,6 +21,17 @@ test() {
 		return
 	fi
 
+	# qdepends output is based on a hash, which may differ based on
+	# endiannes, so sort the output so we get a deterministic set
+	while IFS= read -r line ; do
+		if [[ ${line} == *:* ]] ; then
+			pkg=${line%%:*}
+			echo "${pkg}: $(echo ${line#*:} | xargs -n1 | sort | xargs)"
+		else
+			echo "${line}"
+		fi
+	done < list | diff list - | patch -s list
+
 	local good="${as}/list${num}.good"
 	if [[ ! -e ${good} ]] ; then
 		cp list "${good}"
diff --git a/tests/qdepends/list02.good b/tests/qdepends/list02.good
index 14d0134..7d2631b 100644
--- a/tests/qdepends/list02.good
+++ b/tests/qdepends/list02.good
@@ -1,3 +1,3 @@
 DEPEND="
-	a/b
+    a/b
 "
diff --git a/tests/qdepends/list03.good b/tests/qdepends/list03.good
index 017c839..f66b636 100644
--- a/tests/qdepends/list03.good
+++ b/tests/qdepends/list03.good
@@ -1,5 +1,5 @@
 DEPEND="
-	foo? (
-		a/b
-	)
+    foo? (
+        a/b
+    )
 "
diff --git a/tests/qdepends/list04.good b/tests/qdepends/list04.good
index 6d9f24e..2457caf 100644
--- a/tests/qdepends/list04.good
+++ b/tests/qdepends/list04.good
@@ -1,5 +1,5 @@
 DEPEND="
-	|| (
-		a/b
-	)
+    || (
+        a/b
+    )
 "
diff --git a/tests/qdepends/list05.good b/tests/qdepends/list05.good
index 1d38431..0b7d420 100644
--- a/tests/qdepends/list05.good
+++ b/tests/qdepends/list05.good
@@ -1,10 +1,10 @@
 DEPEND="
-	|| (
-		|| (
-			|| (
-				x
-			)
-			a
-		)
-	)
+    || (
+        || (
+            || (
+                x
+            )
+            a
+        )
+    )
 "
diff --git a/tests/qdepends/list06.good b/tests/qdepends/list06.good
index 6bcf3af..34cc4c9 100644
--- a/tests/qdepends/list06.good
+++ b/tests/qdepends/list06.good
@@ -1,3 +1,3 @@
 DEPEND="
-	a[foo(+)]
+    a[foo(+)]
 "
diff --git a/tests/qdepends/list07.good b/tests/qdepends/list07.good
index 4aaea04..9aaf42d 100644
--- a/tests/qdepends/list07.good
+++ b/tests/qdepends/list07.good
@@ -1 +1 @@
-x11-apps/xdm-1.1.11-r3
+x11-apps/xdm-1.1.11-r3: !<sys-apps/systemd-187 >=media-fonts/font-util-1.2.0 >=sys-devel/autoconf-2.68 >=sys-devel/automake-1.12:1.12 >=sys-devel/automake-1.13:1.13 >=sys-devel/libtool-2.2.6a >=x11-apps/xinit-1.0.2-r3 >=x11-misc/util-macros-1.17 sys-devel/libtool sys-devel/m4 virtual/pkgconfig x11-apps/sessreg x11-apps/xconsole x11-apps/xrdb x11-libs/libX11 x11-libs/libXaw x11-libs/libXdmcp x11-libs/libXinerama x11-libs/libXmu x11-libs/libXt x11-proto/xineramaproto x11-proto/xproto
diff --git a/tests/qdepends/list08.good b/tests/qdepends/list08.good
index bad1799..9aaf42d 100644
--- a/tests/qdepends/list08.good
+++ b/tests/qdepends/list08.good
@@ -1 +1 @@
-x11-apps/xdm-1.1.11-r3: x11-apps/xrdb x11-libs/libXdmcp x11-libs/libXaw >=x11-apps/xinit-1.0.2-r3 x11-libs/libXinerama x11-libs/libXmu x11-libs/libX11 x11-libs/libXt x11-apps/sessreg x11-apps/xconsole !<sys-apps/systemd-187 x11-proto/xineramaproto x11-proto/xproto >=sys-devel/automake-1.12:1.12 >=sys-devel/automake-1.13:1.13 >=sys-devel/autoconf-2.68 sys-devel/libtool >=sys-devel/libtool-2.2.6a sys-devel/m4 >=x11-misc/util-macros-1.17 >=media-fonts/font-util-1.2.0 virtual/pkgconfig virtual/pkgconfig
+x11-apps/xdm-1.1.11-r3: !<sys-apps/systemd-187 >=media-fonts/font-util-1.2.0 >=sys-devel/autoconf-2.68 >=sys-devel/automake-1.12:1.12 >=sys-devel/automake-1.13:1.13 >=sys-devel/libtool-2.2.6a >=x11-apps/xinit-1.0.2-r3 >=x11-misc/util-macros-1.17 sys-devel/libtool sys-devel/m4 virtual/pkgconfig x11-apps/sessreg x11-apps/xconsole x11-apps/xrdb x11-libs/libX11 x11-libs/libXaw x11-libs/libXdmcp x11-libs/libXinerama x11-libs/libXmu x11-libs/libXt x11-proto/xineramaproto x11-proto/xproto