db, apps: sort packages by pkgname and pkgver

This will also fix "search" to display one match from each principal
pkgname group. "search -e vim" will now show both vim and gvim.

fixes #10864
fixes #10777

11 files changed, 191 insertions, 63 deletions

diff --git a/src/apk_database.h b/src/apk_database.h
index 194fe06..06b714a 100644
--- a/src/apk_database.h
+++ b/src/apk_database.h
@@ -102,6 +102,7 @@ struct apk_name {
 	unsigned auto_select_virtual: 1;
 	unsigned priority : 2;
 	unsigned solver_flags_set : 1;
+	unsigned providers_sorted : 1;
 	unsigned int foreach_genid;
 	union {
 		struct apk_solver_name_state ss;
@@ -203,6 +204,7 @@ typedef union apk_database_or_void {
 static inline int apk_name_cmp_display(const struct apk_name *a, const struct apk_name *b) {
 	return strcmp(a->name, b->name);
 }
+struct apk_provider_array *apk_name_sorted_providers(struct apk_name *);
 
 struct apk_name *apk_db_get_name(struct apk_database *db, apk_blob_t name);
 struct apk_name *apk_db_query_name(struct apk_database *db, apk_blob_t name);
@@ -283,4 +285,19 @@ int apk_db_foreach_matching_name(struct apk_database *db, struct apk_string_arra
 int apk_db_foreach_sorted_name(struct apk_database *db, struct apk_string_array *filter,
 			       apk_db_foreach_name_cb cb, void *ctx);
 
+typedef int (*apk_db_foreach_package_cb)(struct apk_database *db, const char *match, struct apk_package *pkg, void *ctx);
+
+int __apk_db_foreach_sorted_package(struct apk_database *db, struct apk_string_array *filter,
+				    apk_db_foreach_package_cb cb, void *cb_ctx, int provides);
+
+static inline int apk_db_foreach_sorted_package(struct apk_database *db, struct apk_string_array *filter,
+						apk_db_foreach_package_cb cb, void *cb_ctx) {
+	return __apk_db_foreach_sorted_package(db, filter, cb, cb_ctx, 0);
+}
+
+static inline int apk_db_foreach_sorted_providers(struct apk_database *db, struct apk_string_array *filter,
+						  apk_db_foreach_package_cb cb, void *cb_ctx) {
+	return __apk_db_foreach_sorted_package(db, filter, cb, cb_ctx, 1);
+}
+
 #endif
diff --git a/src/apk_package.h b/src/apk_package.h
index 6e428e4..10d3cf2 100644
--- a/src/apk_package.h
+++ b/src/apk_package.h
@@ -113,6 +113,7 @@ struct apk_package {
 	time_t build_time;
 	unsigned short provider_priority;
 	unsigned repos : APK_MAX_REPOS;
+	unsigned seen : 1;
 	unsigned marked : 1;
 	unsigned uninstallable : 1;
 	unsigned cached_non_repository : 1;
@@ -184,7 +185,8 @@ void apk_ipkg_run_script(struct apk_installed_package *ipkg, struct apk_database
 struct apk_package *apk_pkg_parse_index_entry(struct apk_database *db, apk_blob_t entry);
 int apk_pkg_write_index_entry(struct apk_package *pkg, struct apk_ostream *os);
 
-int apk_pkg_version_compare(struct apk_package *a, struct apk_package *b);
+int apk_pkg_version_compare(const struct apk_package *a, const struct apk_package *b);
+int apk_pkg_cmp_display(const struct apk_package *a, const struct apk_package *b);
 
 unsigned int apk_foreach_genid(void);
 int apk_pkg_match_genid(struct apk_package *pkg, unsigned int match);
diff --git a/src/app_dot.c b/src/app_dot.c
index 0a86e45..64c3f87 100644
--- a/src/app_dot.c
+++ b/src/app_dot.c
@@ -139,6 +139,7 @@ static int dump(struct apk_database *db, const char *match, struct apk_name *nam
 
 	if (!name) return 0;
 
+	apk_name_sorted_providers(name);
 	foreach_array_item(p, name->providers)
 		dump_pkg(ctx, p->pkg);
 	return 0;
diff --git a/src/app_fetch.c b/src/app_fetch.c
index ea2ca13..8a38047 100644
--- a/src/app_fetch.c
+++ b/src/app_fetch.c
@@ -123,11 +123,9 @@ static void progress_cb(void *pctx, size_t bytes_done)
 	apk_print_progress(ctx->done + bytes_done, ctx->total);
 }
 
-static int fetch_package(apk_hash_item item, void *pctx)
+static int fetch_package(struct apk_database *db, const char *match, struct apk_package *pkg, void *pctx)
 {
-	struct fetch_ctx *ctx = (struct fetch_ctx *) pctx;
-	struct apk_database *db = ctx->db;
-	struct apk_package *pkg = (struct apk_package *) item;
+	struct fetch_ctx *ctx = pctx;
 	struct apk_istream *is;
 	struct apk_repository *repo;
 	struct apk_file_info fi;
@@ -357,7 +355,7 @@ static int fetch_main(void *pctx, struct apk_database *db, struct apk_string_arr
 		apk_db_foreach_matching_name(db, args, mark_name, ctx);
 	}
 	if (!ctx->errors)
-		apk_hash_foreach(&db->available.packages, fetch_package, ctx);
+		apk_db_foreach_sorted_package(db, NULL, fetch_package, ctx);
 
 	/* Remove packages not matching download spec from the output directory */
 	if (!ctx->errors && (apk_flags & APK_PURGE) &&
diff --git a/src/app_info.c b/src/app_info.c
index 2cdbad6..1187dae 100644
--- a/src/app_info.c
+++ b/src/app_info.c
@@ -350,18 +350,16 @@ static void info_subaction(struct info_ctx *ctx, struct apk_package *pkg)
 	}
 }
 
-static int print_name_info(struct apk_database *db, const char *match, struct apk_name *name, void *pctx)
+static int print_name_info(struct apk_database *db, const char *match, struct apk_package *pkg, void *pctx)
 {
 	struct info_ctx *ctx = (struct info_ctx *) pctx;
-	struct apk_provider *p;
 
-	if (name == NULL) {
+	if (!pkg) {
 		ctx->errors++;
 		return 0;
 	}
 
-	foreach_array_item(p, name->providers)
-		info_subaction(ctx, p->pkg);
+	info_subaction(ctx, pkg);
 	return 0;
 }
 
@@ -454,8 +452,8 @@ static int info_main(void *ctx, struct apk_database *db, struct apk_string_array
 	if (ictx->action != NULL) {
 		ictx->action(ictx, db, args);
 	} else if (args->num > 0) {
-		/* Print info on given names */
-		apk_db_foreach_sorted_name(db, args, print_name_info, ctx);
+		/* Print info on given packages */
+		apk_db_foreach_sorted_providers(db, args, print_name_info, ctx);
 	} else {
 		/* Print all installed packages */
 		list_for_each_entry(ipkg, &db->installed.packages, installed_pkgs_list)
diff --git a/src/app_list.c b/src/app_list.c
index 13ab0a7..fed9aa9 100644
--- a/src/app_list.c
+++ b/src/app_list.c
@@ -164,6 +164,7 @@ static int print_result(struct apk_database *db, const char *match, struct apk_n
 
 	if (!name) return 0;
 
+	apk_name_sorted_providers(name);
 	if (ctx->match_depends) {
 		struct apk_name **pname;
 		foreach_array_item(pname, name->rdepends)
diff --git a/src/app_manifest.c b/src/app_manifest.c
index e476872..4c257e7 100644
--- a/src/app_manifest.c
+++ b/src/app_manifest.c
@@ -109,9 +109,11 @@ static int process_match(struct apk_database *db, const char *match, struct apk_
 		return 0;
 	}
 
-	foreach_array_item(p, name->providers)
+	apk_name_sorted_providers(name);
+	foreach_array_item(p, name->providers) {
+		if (p->pkg->name != name) continue;
 		process_package(db, p->pkg);
-
+	}
 	return 0;
 }
 
diff --git a/src/app_policy.c b/src/app_policy.c
index 519257a..8803008 100644
--- a/src/app_policy.c
+++ b/src/app_policy.c
@@ -37,13 +37,12 @@ zlib1g policy:
   1.1:
     http://nl.alpinelinux.org/alpine/v2.4/main
 */
+	apk_name_sorted_providers(name);
 	foreach_array_item(p, name->providers) {
-		if (p->pkg->name != name)
-			continue;
-		if (num++ == 0)
-			printf("%s policy:\n", name->name);
+		if (p->pkg->name != name) continue;
+		if (num++ == 0) printf("%s policy:\n", name->name);
 		printf("  " BLOB_FMT ":\n", BLOB_PRINTF(*p->version));
-		if (p->pkg->ipkg != NULL)
+		if (p->pkg->ipkg)
 			printf("    %s\n", apk_installed_file);
 		for (i = 0; i < db->num_repos; i++) {
 			repo = &db->repos[i];
diff --git a/src/app_search.c b/src/app_search.c
index fd9bd40..6b27620 100644
--- a/src/app_search.c
+++ b/src/app_search.c
@@ -25,18 +25,11 @@ struct search_ctx {
 
 	unsigned int matches;
 	struct apk_string_array *filter;
+	struct apk_package *prev_match;
 };
 
-static int unique_match(struct apk_package *pkg)
-{
-	if (pkg->state_int) return 0;
-	pkg->state_int = 1;
-	return 1;
-}
-
 static void print_package_name(struct search_ctx *ctx, struct apk_package *pkg)
 {
-	if (!unique_match(pkg)) return;
 	printf("%s", pkg->name->name);
 	if (apk_verbosity > 0)
 		printf("-" BLOB_FMT, BLOB_PRINTF(*pkg->version));
@@ -47,7 +40,6 @@ static void print_package_name(struct search_ctx *ctx, struct apk_package *pkg)
 
 static void print_origin_name(struct search_ctx *ctx, struct apk_package *pkg)
 {
-	if (!unique_match(pkg)) return;
 	if (pkg->origin != NULL)
 		printf(BLOB_FMT, BLOB_PRINTF(*pkg->origin));
 	else
@@ -143,26 +135,28 @@ match:
 	ctx->print_result(ctx, pkg);
 }
 
-static int print_result(struct apk_database *db, const char *match, struct apk_name *name, void *pctx)
+static int print_result(struct apk_database *db, const char *match, struct apk_package *pkg, void *pctx)
 {
 	struct search_ctx *ctx = pctx;
-	struct apk_provider *p;
-	struct apk_package *pkg = NULL;
 
-	if (!name) return 0;
+	if (!pkg) return 0;
 
 	if (ctx->show_all) {
-		foreach_array_item(p, name->providers)
-			print_result_pkg(ctx, p->pkg);
-	} else {
-		foreach_array_item(p, name->providers) {
-			if (pkg == NULL ||
-			    apk_version_compare_blob(*p->version, *pkg->version) == APK_VERSION_GREATER)
-				pkg = p->pkg;
-		}
-		if (pkg)
-			print_result_pkg(ctx, pkg);
+		print_result_pkg(ctx, pkg);
+		return 0;
 	}
+
+	if (!ctx->prev_match) {
+		ctx->prev_match = pkg;
+		return 0;
+	}
+	if (ctx->prev_match->name != pkg->name) {
+		print_result_pkg(ctx, ctx->prev_match);
+		ctx->prev_match = pkg;
+		return 0;
+	}
+	if (apk_pkg_version_compare(pkg, ctx->prev_match) == APK_VERSION_GREATER)
+		ctx->prev_match = pkg;
 	return 0;
 }
 
@@ -191,7 +185,9 @@ static int search_main(void *pctx, struct apk_database *db, struct apk_string_ar
 			*pmatch = tmp;
 		}
 	}
-	apk_db_foreach_sorted_name(db, args, print_result, ctx);
+	apk_db_foreach_sorted_providers(db, args, print_result, ctx);
+	if (ctx->prev_match) print_result_pkg(ctx, ctx->prev_match);
+
 	return 0;
 }
 
diff --git a/src/database.c b/src/database.c
index 3dc72f2..dd11973 100644
--- a/src/database.c
+++ b/src/database.c
@@ -226,6 +226,21 @@ struct apk_name *apk_db_get_name(struct apk_database *db, apk_blob_t name)
 	return pn;
 }
 
+static int cmp_provider(const void *a, const void *b)
+{
+	const struct apk_provider *pa = a, *pb = b;
+	return apk_pkg_cmp_display(pa->pkg, pb->pkg);
+}
+
+struct apk_provider_array *apk_name_sorted_providers(struct apk_name *name)
+{
+	if (!name->providers_sorted) {
+		qsort(name->providers->item,  name->providers->num, sizeof name->providers->item[0], cmp_provider);
+		name->providers_sorted = 0;
+	}
+	return name->providers;
+}
+
 static struct apk_db_acl *apk_db_acl_atomize(struct apk_database *db, mode_t mode, uid_t uid, gid_t gid, const struct apk_checksum *xattr_csum)
 {
 	struct apk_db_acl acl = { .mode = mode & 07777, .uid = uid, .gid = gid };
@@ -2993,24 +3008,48 @@ struct match_ctx {
 	void *cb_ctx;
 };
 
-static int match_names(apk_hash_item item, void *pctx)
+static int apk_string_match(const char *str, struct apk_string_array *filter, const char **res)
 {
-	struct match_ctx *ctx = (struct match_ctx *) pctx;
-	struct apk_name *name = (struct apk_name *) item;
 	char **pmatch;
 
-	if (!ctx->filter->num) {
-		ctx->cb(ctx->db, NULL, name, ctx->cb_ctx);
-		return 0;
+	foreach_array_item(pmatch, filter) {
+		if (fnmatch(*pmatch, str, 0) == 0) {
+			*res = *pmatch;
+			return 1;
+		}
 	}
+	return 0;
+}
 
-	foreach_array_item(pmatch, ctx->filter) {
-		if (fnmatch(*pmatch, name->name, 0) == 0) {
-			ctx->cb(ctx->db, *pmatch, name, ctx->cb_ctx);
-			break;
-		}
+static int apk_name_match(struct apk_name *name, struct apk_string_array *filter, const char **res)
+{
+	if (!filter) {
+		*res = NULL;
+		return 1;
+	}
+	return apk_string_match(name->name, filter, res);
+}
+
+static int apk_pkg_match(struct apk_package *pkg, struct apk_string_array *filter, const char **res, int provides)
+{
+	struct apk_dependency *d;
+
+	if (apk_name_match(pkg->name, filter, res)) return 1;
+	if (!provides) return 0;
+	foreach_array_item(d, pkg->provides) {
+		if (apk_string_match(d->name->name, filter, res)) return 1;
 	}
+	return 0;
+}
+
+static int match_names(apk_hash_item item, void *pctx)
+{
+	struct match_ctx *ctx = (struct match_ctx *) pctx;
+	struct apk_name *name = (struct apk_name *) item;
+	const char *match;
 
+	if (apk_name_match(name, ctx->filter, &match))
+		return ctx->cb(ctx->db, match, name, ctx->cb_ctx);
 	return 0;
 }
 
@@ -3050,6 +3089,12 @@ static int cmp_name(const void *a, const void *b)
 	return apk_name_cmp_display(*na, *nb);
 }
 
+static int cmp_package(const void *a, const void *b)
+{
+	const struct apk_package * const* pa = a, * const* pb = b;
+	return apk_pkg_cmp_display(*pa, *pb);
+}
+
 struct add_name_ctx {
 	struct apk_name_array *a;
 	size_t i;
@@ -3083,6 +3128,7 @@ int apk_db_foreach_sorted_name(struct apk_database *db, struct apk_string_array
 {
 	int walk_all = 0;
 	char **pmatch;
+	const char *match;
 	struct apk_name *name;
 	struct apk_name *results[128], **res;
 	size_t i, num_res = 0;
@@ -3122,17 +3168,71 @@ int apk_db_foreach_sorted_name(struct apk_database *db, struct apk_string_array
 
 	for (i = 0; i < num_res; i++) {
 		name = res[i];
-		if (!filter || !filter->num) {
-			cb(db, NULL, name, cb_ctx);
+		if (apk_name_match(name, filter, &match)) {
+			r = cb(db, match, name, cb_ctx);
+			if (r) return r;
+		}
+	}
+	return 0;
+}
+
+int __apk_db_foreach_sorted_package(struct apk_database *db, struct apk_string_array *filter,
+				    apk_db_foreach_package_cb cb, void *cb_ctx, int provides)
+{
+	char **pmatch;
+	const char *match;
+	struct apk_name *name;
+	struct apk_package *results[128];
+	struct apk_provider *p;
+	size_t i, num_res = 0;
+	int r;
+
+	if (!filter || !filter->num) {
+		filter = NULL;
+		goto walk_all;
+	}
+
+	foreach_array_item(pmatch, filter) {
+		name = (struct apk_name *) apk_hash_get(&db->available.names, APK_BLOB_STR(*pmatch));
+		if (strchr(*pmatch, '*')) goto walk_all;
+		if (!name) {
+			cb(db, *pmatch, NULL, cb_ctx);
 			continue;
 		}
-		foreach_array_item(pmatch, filter) {
-			if (fnmatch(*pmatch, name->name, 0) == 0) {
-				r = cb(db, *pmatch, name, cb_ctx);
-				break;
+
+		foreach_array_item(p, name->providers) {
+			if (!provides && p->pkg->name != name) continue;
+			if (p->pkg->seen) continue;
+			p->pkg->seen = 1;
+			if (num_res >= ARRAY_SIZE(results)) goto walk_all;
+			results[num_res++] = p->pkg;
+		}
+	}
+	for (i = 0; i < num_res; i++) results[i]->seen = 0;
+
+	qsort(results, num_res, sizeof results[0], cmp_package);
+	for (i = 0; i < num_res; i++) {
+		if (apk_pkg_match(results[i], filter, &match, provides)) {
+			r = cb(db, match, results[i], cb_ctx);
+			if (r) return r;
+		}
+	}
+	return 0;
+
+walk_all:
+	for (i = 0; i < num_res; i++) results[i]->seen = 0;
+
+	struct apk_name_array *a = apk_db_sorted_names(db);
+	for (i = 0; i < a->num; i++) {
+		name = a->item[i];
+		apk_name_sorted_providers(name);
+		foreach_array_item(p, name->providers) {
+			if (p->pkg->name != name) continue;
+			if (apk_pkg_match(p->pkg, filter, &match, provides)) {
+				r = cb(db, match, p->pkg, cb_ctx);
+				if (r) return r;
 			}
 		}
-		if (r) return r;
 	}
 	return 0;
 }
diff --git a/src/package.c b/src/package.c
index cd2329c..230c266 100644
--- a/src/package.c
+++ b/src/package.c
@@ -1178,7 +1178,7 @@ int apk_pkg_write_index_entry(struct apk_package *info,
 	return 0;
 }
 
-int apk_pkg_version_compare(struct apk_package *a, struct apk_package *b)
+int apk_pkg_version_compare(const struct apk_package *a, const struct apk_package *b)
 {
 	if (a->version == b->version)
 		return APK_VERSION_EQUAL;
@@ -1186,6 +1186,20 @@ int apk_pkg_version_compare(struct apk_package *a, struct apk_package *b)
 	return apk_version_compare_blob(*a->version, *b->version);
 }
 
+int apk_pkg_cmp_display(const struct apk_package *a, const struct apk_package *b)
+{
+	if (a->name != b->name)
+		return apk_name_cmp_display(a->name, b->name);
+	switch (apk_pkg_version_compare(a, b)) {
+	case APK_VERSION_LESS:
+		return -1;
+	case APK_VERSION_GREATER:
+		return 1;
+	default:
+		return 0;
+	}
+}
+
 unsigned int apk_foreach_genid(void)
 {
 	static unsigned int foreach_genid;