db/Interface: CollectUniqueTags() allows multiple "groups"

Instead of passing tag and group, pass an array of tags.  To support a
nested return value, return a nested std::map of std::maps.  Each key
specifies the tag value, and each value may be another nesting level.

Closes https://github.com/MusicPlayerDaemon/MPD/issues/408

11 files changed, 163 insertions, 122 deletions

diff --git a/src/command/DatabaseCommands.cxx b/src/command/DatabaseCommands.cxx
index 6fc9fa8ac..ca0bd1ea9 100644
--- a/src/command/DatabaseCommands.cxx
+++ b/src/command/DatabaseCommands.cxx
@@ -266,7 +266,7 @@ handle_list(Client &client, Request args, Response &r)
 	}
 
 	std::unique_ptr<SongFilter> filter;
-	TagType group = TAG_NUM_OF_ITEM_TYPES;
+	std::vector<TagType> tag_types;
 
 	if (args.size == 1 &&
 	    /* parantheses are the syntax for filter expressions: no
@@ -284,20 +284,31 @@ handle_list(Client &client, Request args, Response &r)
 					    args.shift()));
 	}
 
-	if  (args.size >= 2 &&
-	     StringIsEqual(args[args.size - 2], "group")) {
+	while (args.size >= 2 &&
+	       StringIsEqual(args[args.size - 2], "group")) {
 		const char *s = args[args.size - 1];
-		group = tag_name_parse_i(s);
+		const auto group = tag_name_parse_i(s);
 		if (group == TAG_NUM_OF_ITEM_TYPES) {
 			r.FormatError(ACK_ERROR_ARG,
 				      "Unknown tag type: %s", s);
 			return CommandResult::ERROR;
 		}
 
+		if (group == tagType ||
+		    std::find(tag_types.begin(), tag_types.end(),
+			      group) != tag_types.end()) {
+			r.Error(ACK_ERROR_ARG, "Conflicting group");
+			return CommandResult::ERROR;
+		}
+
+		tag_types.emplace_back(group);
+
 		args.pop_back();
 		args.pop_back();
 	}
 
+	tag_types.emplace_back(tagType);
+
 	if (!args.empty()) {
 		filter.reset(new SongFilter());
 		try {
@@ -310,13 +321,9 @@ handle_list(Client &client, Request args, Response &r)
 		filter->Optimize();
 	}
 
-	if (tagType < TAG_NUM_OF_ITEM_TYPES && tagType == group) {
-		r.Error(ACK_ERROR_ARG, "Conflicting group");
-		return CommandResult::ERROR;
-	}
-
 	PrintUniqueTags(r, client.GetPartition(),
-			tagType, group, filter.get());
+			{&tag_types.front(), tag_types.size()},
+			filter.get());
 	return CommandResult::OK;
 }
 
diff --git a/src/db/DatabasePrint.cxx b/src/db/DatabasePrint.cxx
index ceafb5a93..deb430b1a 100644
--- a/src/db/DatabasePrint.cxx
+++ b/src/db/DatabasePrint.cxx
@@ -1,5 +1,5 @@
 /*
- * Copyright 2003-2018 The Music Player Daemon Project
+ * Copyright 2003-2019 The Music Player Daemon Project
  * http://www.musicpd.org
  *
  * This program is free software; you can redistribute it and/or modify
@@ -35,6 +35,7 @@
 #include "Interface.hxx"
 #include "fs/Traits.hxx"
 #include "util/ChronoUtil.hxx"
+#include "util/RecursiveMap.hxx"
 
 #include <functional>
 
@@ -186,42 +187,29 @@ PrintSongUris(Response &r, Partition &partition,
 }
 
 static void
-PrintUniqueTags(Response &r, TagType tag_type,
-		const std::set<std::string> &values)
+PrintUniqueTags(Response &r, ConstBuffer<TagType> tag_types,
+		const RecursiveMap<std::string> &map) noexcept
 {
-	const char *const name = tag_item_names[tag_type];
-	for (const auto &i : values)
-		r.Format("%s: %s\n", name, i.c_str());
-}
+	const char *const name = tag_item_names[tag_types.front()];
+	tag_types.pop_front();
 
-static void
-PrintGroupedUniqueTags(Response &r, TagType tag_type, TagType group,
-		       const std::map<std::string, std::set<std::string>> &groups)
-{
-	if (group == TAG_NUM_OF_ITEM_TYPES) {
-		for (const auto &i : groups)
-			PrintUniqueTags(r, tag_type, i.second);
-		return;
-	}
+	for (const auto &i : map) {
+		r.Format("%s: %s\n", name, i.first.c_str());
 
-	const char *const group_name = tag_item_names[group];
-	for (const auto &i : groups) {
-		r.Format("%s: %s\n", group_name, i.first.c_str());
-		PrintUniqueTags(r, tag_type, i.second);
+		if (!tag_types.empty())
+			PrintUniqueTags(r, tag_types, i.second);
 	}
 }
 
 void
 PrintUniqueTags(Response &r, Partition &partition,
-		TagType type, TagType group,
+		ConstBuffer<TagType> tag_types,
 		const SongFilter *filter)
 {
-	assert(type < TAG_NUM_OF_ITEM_TYPES);
-
 	const Database &db = partition.GetDatabaseOrThrow();
 
 	const DatabaseSelection selection("", true, filter);
 
-	PrintGroupedUniqueTags(r, type, group,
-			       db.CollectUniqueTags(selection, type, group));
+	PrintUniqueTags(r, tag_types,
+			db.CollectUniqueTags(selection, tag_types));
 }
diff --git a/src/db/DatabasePrint.hxx b/src/db/DatabasePrint.hxx
index b485ad787..dbfb2a8d9 100644
--- a/src/db/DatabasePrint.hxx
+++ b/src/db/DatabasePrint.hxx
@@ -1,5 +1,5 @@
 /*
- * Copyright 2003-2018 The Music Player Daemon Project
+ * Copyright 2003-2019 The Music Player Daemon Project
  * http://www.musicpd.org
  *
  * This program is free software; you can redistribute it and/or modify
@@ -22,6 +22,7 @@
 
 #include <stdint.h>
 
+template<typename T> struct ConstBuffer;
 enum TagType : uint8_t;
 class TagMask;
 class SongFilter;
@@ -45,7 +46,7 @@ PrintSongUris(Response &r, Partition &partition,
 
 void
 PrintUniqueTags(Response &r, Partition &partition,
-		TagType type, TagType group,
+		ConstBuffer<TagType> tag_types,
 		const SongFilter *filter);
 
 #endif
diff --git a/src/db/Interface.hxx b/src/db/Interface.hxx
index 2bfdd0a44..7ba6e38b5 100644
--- a/src/db/Interface.hxx
+++ b/src/db/Interface.hxx
@@ -1,5 +1,5 @@
 /*
- * Copyright 2003-2018 The Music Player Daemon Project
+ * Copyright 2003-2019 The Music Player Daemon Project
  * http://www.musicpd.org
  *
  * This program is free software; you can redistribute it and/or modify
@@ -25,15 +25,14 @@
 #include "util/Compiler.h"
 
 #include <chrono>
-#include <map>
-#include <set>
 #include <string>
 
 struct DatabasePlugin;
 struct DatabaseStats;
 struct DatabaseSelection;
 struct LightSong;
-class TagMask;
+template<typename Key> class RecursiveMap;
+template<typename T> struct ConstBuffer;
 
 class Database {
 	const DatabasePlugin &plugin;
@@ -106,13 +105,14 @@ public:
 	}
 
 	/**
-	 * Collect unique values of the given tag type.
+	 * Collect unique values of the given tag types.  Each item in
+	 * the #tag_types parameter results in one nesting level in
+	 * the return value.
 	 *
 	 * Throws on error.
 	 */
-	virtual std::map<std::string, std::set<std::string>> CollectUniqueTags(const DatabaseSelection &selection,
-									       TagType tag_type,
-									       TagType group=TAG_NUM_OF_ITEM_TYPES) const = 0;
+	virtual RecursiveMap<std::string> CollectUniqueTags(const DatabaseSelection &selection,
+							    ConstBuffer<TagType> tag_types) const = 0;
 
 	/**
 	 * Throws on error.
diff --git a/src/db/UniqueTags.cxx b/src/db/UniqueTags.cxx
index b9fe41899..1f38d7cea 100644
--- a/src/db/UniqueTags.cxx
+++ b/src/db/UniqueTags.cxx
@@ -1,5 +1,5 @@
 /*
- * Copyright 2003-2018 The Music Player Daemon Project
+ * Copyright 2003-2019 The Music Player Daemon Project
  * http://www.musicpd.org
  *
  * This program is free software; you can redistribute it and/or modify
@@ -21,36 +21,32 @@
 #include "Interface.hxx"
 #include "song/LightSong.hxx"
 #include "tag/VisitFallback.hxx"
+#include "util/ConstBuffer.hxx"
+#include "util/RecursiveMap.hxx"
 
 static void
-CollectTags(std::set<std::string> &result,
-	    const Tag &tag,
-	    TagType tag_type) noexcept
+CollectUniqueTags(RecursiveMap<std::string> &result,
+		  const Tag &tag,
+		  ConstBuffer<TagType> tag_types) noexcept
 {
-	VisitTagWithFallbackOrEmpty(tag, tag_type, [&result](const char *value){
-			result.emplace(value);
-		});
-}
+	if (tag_types.empty())
+		return;
 
-static void
-CollectGroupTags(std::map<std::string, std::set<std::string>> &result,
-		 const Tag &tag,
-		 TagType tag_type,
-		 TagType group) noexcept
-{
-	VisitTagWithFallbackOrEmpty(tag, group, [&](const char *group_name){
-			CollectTags(result[group_name], tag, tag_type);
+	const auto tag_type = tag_types.shift();
+
+	VisitTagWithFallbackOrEmpty(tag, tag_type, [&result, &tag, tag_types](const char *value){
+			CollectUniqueTags(result[value], tag, tag_types);
 		});
 }
 
-std::map<std::string, std::set<std::string>>
+RecursiveMap<std::string>
 CollectUniqueTags(const Database &db, const DatabaseSelection &selection,
-		  TagType tag_type, TagType group)
+		  ConstBuffer<TagType> tag_types)
 {
-	std::map<std::string, std::set<std::string>> result;
+	RecursiveMap<std::string> result;
 
-	db.Visit(selection, [&result, tag_type, group](const LightSong &song){
-			CollectGroupTags(result, song.tag, tag_type, group);
+	db.Visit(selection, [&result, tag_types](const LightSong &song){
+			CollectUniqueTags(result, song.tag, tag_types);
 		});
 
 	return result;
diff --git a/src/db/UniqueTags.hxx b/src/db/UniqueTags.hxx
index dfcd1457d..fb368e206 100644
--- a/src/db/UniqueTags.hxx
+++ b/src/db/UniqueTags.hxx
@@ -1,5 +1,5 @@
 /*
- * Copyright 2003-2018 The Music Player Daemon Project
+ * Copyright 2003-2019 The Music Player Daemon Project
  * http://www.musicpd.org
  *
  * This program is free software; you can redistribute it and/or modify
@@ -29,9 +29,11 @@
 class TagMask;
 class Database;
 struct DatabaseSelection;
+template<typename Key> class RecursiveMap;
+template<typename T> struct ConstBuffer;
 
-std::map<std::string, std::set<std::string>>
+RecursiveMap<std::string>
 CollectUniqueTags(const Database &db, const DatabaseSelection &selection,
-		  TagType tag_type, TagType group);
+		  ConstBuffer<TagType> tag_types);
 
 #endif
diff --git a/src/db/plugins/ProxyDatabasePlugin.cxx b/src/db/plugins/ProxyDatabasePlugin.cxx
index f80ffd277..42edd23d0 100644
--- a/src/db/plugins/ProxyDatabasePlugin.cxx
+++ b/src/db/plugins/ProxyDatabasePlugin.cxx
@@ -38,6 +38,8 @@
 #include "tag/Tag.hxx"
 #include "tag/Mask.hxx"
 #include "tag/ParseName.hxx"
+#include "util/ConstBuffer.hxx"
+#include "util/RecursiveMap.hxx"
 #include "util/ScopeExit.hxx"
 #include "util/RuntimeError.hxx"
 #include "protocol/Ack.hxx"
@@ -127,9 +129,8 @@ public:
 		   VisitSong visit_song,
 		   VisitPlaylist visit_playlist) const override;
 
-	std::map<std::string, std::set<std::string>> CollectUniqueTags(const DatabaseSelection &selection,
-								       TagType tag_type,
-								       TagType group) const override;
+	RecursiveMap<std::string> CollectUniqueTags(const DatabaseSelection &selection,
+						    ConstBuffer<TagType> tag_types) const override;
 
 	DatabaseStats GetStats(const DatabaseSelection &selection) const override;
 
@@ -412,8 +413,7 @@ SendConstraints(mpd_connection *connection, const DatabaseSelection &selection)
 static bool
 SendGroup(mpd_connection *connection, TagType group)
 {
-	if (group == TAG_NUM_OF_ITEM_TYPES)
-		return true;
+	assert(group != TAG_NUM_OF_ITEM_TYPES);
 
 #if LIBMPDCLIENT_CHECK_VERSION(2,12,0)
 	const auto tag = Convert(group);
@@ -428,6 +428,19 @@ SendGroup(mpd_connection *connection, TagType group)
 #endif
 }
 
+static bool
+SendGroup(mpd_connection *connection, ConstBuffer<TagType> group)
+{
+	while (!group.empty()) {
+		if (!SendGroup(connection, group.back()))
+		    return false;
+
+		group.pop_back();
+	}
+
+	return true;
+}
+
 ProxyDatabase::ProxyDatabase(EventLoop &_loop, DatabaseListener &_listener,
 			     const ConfigBlock &block)
 	:Database(proxy_db_plugin),
@@ -983,17 +996,20 @@ ProxyDatabase::Visit(const DatabaseSelection &selection,
 	helper.Commit();
 }
 
-std::map<std::string, std::set<std::string>>
+RecursiveMap<std::string>
 ProxyDatabase::CollectUniqueTags(const DatabaseSelection &selection,
-				 TagType tag_type, TagType group) const
+				 ConstBuffer<TagType> tag_types) const
 try {
 	// TODO: eliminate the const_cast
 	const_cast<ProxyDatabase *>(this)->EnsureConnected();
 
-	enum mpd_tag_type tag_type2 = Convert(tag_type);
+	enum mpd_tag_type tag_type2 = Convert(tag_types.back());
 	if (tag_type2 == MPD_TAG_COUNT)
 		throw std::runtime_error("Unsupported tag");
 
+	auto group = tag_types;
+	group.pop_back();
+
 	if (!mpd_search_db_tags(connection, tag_type2) ||
 	    !SendConstraints(connection, selection) ||
 	    !SendGroup(connection, group))
@@ -1002,44 +1018,33 @@ try {
 	if (!mpd_search_commit(connection))
 		ThrowError(connection);
 
-	std::map<std::string, std::set<std::string>> result;
-
-	if (group == TAG_NUM_OF_ITEM_TYPES) {
-		auto &values = result[std::string()];
-
-		while (auto *pair = mpd_recv_pair(connection)) {
-			AtScopeExit(this, pair) {
-				mpd_return_pair(connection, pair);
-			};
+	RecursiveMap<std::string> result;
+	std::vector<RecursiveMap<std::string> *> position;
+	position.emplace_back(&result);
 
-			const auto current_type = tag_name_parse_i(pair->name);
-			if (current_type == TAG_NUM_OF_ITEM_TYPES)
-				continue;
+	while (auto *pair = mpd_recv_pair(connection)) {
+		AtScopeExit(this, pair) {
+			mpd_return_pair(connection, pair);
+		};
 
-			if (current_type == tag_type)
-				values.emplace(pair->value);
-		}
-	} else {
-		std::set<std::string> *current_group = nullptr;
+		const auto current_type = tag_name_parse_i(pair->name);
+		if (current_type == TAG_NUM_OF_ITEM_TYPES)
+			continue;
 
-		while (auto *pair = mpd_recv_pair(connection)) {
-			AtScopeExit(this, pair) {
-				mpd_return_pair(connection, pair);
-			};
+		auto it = std::find(tag_types.begin(), tag_types.end(),
+				    current_type);
+		if (it == tag_types.end())
+			continue;
 
-			const auto current_type = tag_name_parse_i(pair->name);
-			if (current_type == TAG_NUM_OF_ITEM_TYPES)
-				continue;
+		size_t i = std::distance(tag_types.begin(), it);
+		if (i > position.size())
+			continue;
 
-			if (current_type == tag_type) {
-				if (current_group == nullptr)
-					current_group = &result[std::string()];
+		if (i + 1 < position.size())
+			position.resize(i + 1);
 
-				current_group->emplace(pair->value);
-			} else if (current_type == group) {
-				current_group = &result[pair->value];
-			}
-		}
+		auto &parent = *position[i];
+		position.emplace_back(&parent[pair->value]);
 	}
 
 	if (!mpd_response_finish(connection))
diff --git a/src/db/plugins/simple/SimpleDatabasePlugin.cxx b/src/db/plugins/simple/SimpleDatabasePlugin.cxx
index 1daa4bf57..ebb34ee14 100644
--- a/src/db/plugins/simple/SimpleDatabasePlugin.cxx
+++ b/src/db/plugins/simple/SimpleDatabasePlugin.cxx
@@ -42,6 +42,8 @@
 #include "fs/FileSystem.hxx"
 #include "util/CharUtil.hxx"
 #include "util/Domain.hxx"
+#include "util/ConstBuffer.hxx"
+#include "util/RecursiveMap.hxx"
 #include "Log.hxx"
 
 #ifdef ENABLE_ZLIB
@@ -329,11 +331,11 @@ SimpleDatabase::Visit(const DatabaseSelection &selection,
 			    "No such directory");
 }
 
-std::map<std::string, std::set<std::string>>
+RecursiveMap<std::string>
 SimpleDatabase::CollectUniqueTags(const DatabaseSelection &selection,
-				  TagType tag_type, TagType group) const
+				  ConstBuffer<TagType> tag_types) const
 {
-	return ::CollectUniqueTags(*this, selection, tag_type, group);
+	return ::CollectUniqueTags(*this, selection, tag_types);
 }
 
 DatabaseStats
diff --git a/src/db/plugins/simple/SimpleDatabasePlugin.hxx b/src/db/plugins/simple/SimpleDatabasePlugin.hxx
index d3dac514f..bdc90f6c1 100644
--- a/src/db/plugins/simple/SimpleDatabasePlugin.hxx
+++ b/src/db/plugins/simple/SimpleDatabasePlugin.hxx
@@ -122,9 +122,8 @@ public:
 		   VisitSong visit_song,
 		   VisitPlaylist visit_playlist) const override;
 
-	std::map<std::string, std::set<std::string>> CollectUniqueTags(const DatabaseSelection &selection,
-								       TagType tag_type,
-								       TagType group) const override;
+	RecursiveMap<std::string> CollectUniqueTags(const DatabaseSelection &selection,
+						    ConstBuffer<TagType> tag_types) const override;
 
 	DatabaseStats GetStats(const DatabaseSelection &selection) const override;
 
diff --git a/src/db/plugins/upnp/UpnpDatabasePlugin.cxx b/src/db/plugins/upnp/UpnpDatabasePlugin.cxx
index 4263773a4..c3fc32e27 100644
--- a/src/db/plugins/upnp/UpnpDatabasePlugin.cxx
+++ b/src/db/plugins/upnp/UpnpDatabasePlugin.cxx
@@ -40,10 +40,11 @@
 #include "tag/Mask.hxx"
 #include "fs/Traits.hxx"
 #include "Log.hxx"
+#include "util/ConstBuffer.hxx"
+#include "util/RecursiveMap.hxx"
 #include "util/SplitString.hxx"
 
 #include <string>
-#include <set>
 
 #include <assert.h>
 #include <string.h>
@@ -97,9 +98,8 @@ public:
 		   VisitSong visit_song,
 		   VisitPlaylist visit_playlist) const override;
 
-	std::map<std::string, std::set<std::string>> CollectUniqueTags(const DatabaseSelection &selection,
-								       TagType tag_type,
-								       TagType group) const override;
+	RecursiveMap<std::string> CollectUniqueTags(const DatabaseSelection &selection,
+						    ConstBuffer<TagType> tag_types) const override;
 
 	DatabaseStats GetStats(const DatabaseSelection &selection) const override;
 
@@ -624,11 +624,11 @@ UpnpDatabase::Visit(const DatabaseSelection &selection,
 	helper.Commit();
 }
 
-std::map<std::string, std::set<std::string>>
+RecursiveMap<std::string>
 UpnpDatabase::CollectUniqueTags(const DatabaseSelection &selection,
-				TagType tag, TagType group) const
+				ConstBuffer<TagType> tag_types) const
 {
-	return ::CollectUniqueTags(*this, selection, tag, group);
+	return ::CollectUniqueTags(*this, selection, tag_types);
 }
 
 DatabaseStats
diff --git a/src/util/RecursiveMap.hxx b/src/util/RecursiveMap.hxx
new file mode 100644
index 000000000..4811c73a8
--- /dev/null
+++ b/src/util/RecursiveMap.hxx
@@ -0,0 +1,41 @@
+/*
+ * Copyright 2019 Max Kellermann <max.kellermann@gmail.com>
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ *
+ * - Redistributions of source code must retain the above copyright
+ * notice, this list of conditions and the following disclaimer.
+ *
+ * - 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 COPYRIGHT HOLDERS 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.
+ */
+
+#ifndef RECURSIVE_MAP_HXX
+#define RECURSIVE_MAP_HXX
+
+#include <map>
+
+/**
+ * A #std::map which contains instances of itself.
+ */
+template<typename Key>
+class RecursiveMap : public std::map<Key, RecursiveMap<Key>> {};
+
+#endif