--- a/src/imap/cmd-list.c	Thu Jun 28 22:34:59 2007 +0300
+++ b/src/imap/cmd-list.c	Fri Jun 29 03:39:27 2007 +0300
@@ -9,11 +9,6 @@
 #include "commands.h"
 #include "mail-namespace.h"
 
-enum {
-	_MAILBOX_LIST_ITER_HIDE_CHILDREN	= 0x1000000,
-	_MAILBOX_LIST_ITER_LISTEXT		= 0x0800000
-};
-
 struct cmd_list_context {
 	struct client_command_context *cmd;
 	const char *ref;
@@ -32,35 +27,44 @@
 	unsigned int cur_ns_match_inbox:1;
 	unsigned int cur_ns_send_prefix:1;
 	unsigned int cur_ns_skip_trailing_sep:1;
+	unsigned int used_listext:1;
 };
 
 static void
-mailbox_flags2str(string_t *str, enum mailbox_info_flags flags,
-		  enum mailbox_list_flags list_flags)
+mailbox_flags2str(struct cmd_list_context *ctx, string_t *str,
+		  enum mailbox_info_flags flags)
 {
 	unsigned int orig_len = str_len(str);
 
-	if ((flags & MAILBOX_NONEXISTENT) != 0 &&
-	    (list_flags & _MAILBOX_LIST_ITER_LISTEXT) == 0) {
+	if ((flags & MAILBOX_NONEXISTENT) != 0 && !ctx->used_listext) {
 		flags |= MAILBOX_NOSELECT;
 		flags &= ~MAILBOX_NONEXISTENT;
 	}
 
-	if ((list_flags & _MAILBOX_LIST_ITER_HIDE_CHILDREN) != 0)
+	if ((ctx->list_flags & MAILBOX_LIST_ITER_RETURN_CHILDREN) == 0)
 		flags &= ~(MAILBOX_CHILDREN|MAILBOX_NOCHILDREN);
 
+	if ((flags & MAILBOX_SUBSCRIBED) != 0 &&
+	    (ctx->list_flags & MAILBOX_LIST_ITER_RETURN_SUBSCRIBED) != 0)
+		str_append(str, "\\Subscribed ");
+
+	if ((flags & MAILBOX_CHILD_SUBSCRIBED) != 0 && !ctx->used_listext) {
+		/* LSUB uses \Noselect for this */
+		flags |= MAILBOX_NOSELECT;
+	}
+
 	if ((flags & MAILBOX_NOSELECT) != 0)
 		str_append(str, "\\Noselect ");
 	if ((flags & MAILBOX_NONEXISTENT) != 0)
 		str_append(str, "\\NonExistent ");
+
 	if ((flags & MAILBOX_CHILDREN) != 0)
 		str_append(str, "\\HasChildren ");
-	else {
-		if ((flags & MAILBOX_NOCHILDREN) != 0)
-			str_append(str, "\\HasNoChildren ");
-		if ((flags & MAILBOX_NOINFERIORS) != 0)
-			str_append(str, "\\NoInferiors ");
-	}
+	else if ((flags & MAILBOX_NOINFERIORS) != 0)
+		str_append(str, "\\NoInferiors ");
+	else if ((flags & MAILBOX_NOCHILDREN) != 0)
+		str_append(str, "\\HasNoChildren ");
+
 	if ((flags & MAILBOX_MARKED) != 0)
 		str_append(str, "\\Marked ");
 	if ((flags & MAILBOX_UNMARKED) != 0)
@@ -70,9 +74,52 @@
 		str_truncate(str, str_len(str)-1);
 }
 
+static void
+mailbox_childinfo2str(struct cmd_list_context *ctx, string_t *str,
+		      enum mailbox_info_flags flags)
+{
+	if (!ctx->used_listext)
+		return;
+
+	if ((flags & MAILBOX_CHILD_SUBSCRIBED) != 0)
+		str_append(str, " (\"CHILDINFO\" (\"SUBSCRIBED\"))");
+}
+
 static bool
-parse_list_flags(struct client_command_context *cmd, struct imap_arg *args,
-		 enum mailbox_list_flags *list_flags)
+parse_select_flags(struct client_command_context *cmd, struct imap_arg *args,
+		   enum mailbox_list_flags *list_flags)
+{
+	const char *atom;
+
+	while (args->type != IMAP_ARG_EOL) {
+		if (args->type != IMAP_ARG_ATOM) {
+			client_send_command_error(cmd,
+				"List options contains non-atoms.");
+			return FALSE;
+		}
+
+		atom = IMAP_ARG_STR(args);
+
+		if (strcasecmp(atom, "SUBSCRIBED") == 0) {
+			*list_flags |= MAILBOX_LIST_ITER_SELECT_SUBSCRIBED |
+				MAILBOX_LIST_ITER_RETURN_SUBSCRIBED;
+		} else if (strcasecmp(atom, "RECURSIVEMATCH") == 0)
+			*list_flags |= MAILBOX_LIST_ITER_SELECT_RECURSIVEMATCH;
+		args++;
+	}
+
+	if ((*list_flags & MAILBOX_LIST_ITER_SELECT_RECURSIVEMATCH) != 0 &&
+	    (*list_flags & MAILBOX_LIST_ITER_SELECT_SUBSCRIBED) == 0) {
+		client_send_command_error(cmd,
+			"RECURSIVEMATCH must not be the only selection.");
+		return FALSE;
+	}
+	return TRUE;
+}
+
+static bool
+parse_return_flags(struct client_command_context *cmd, struct imap_arg *args,
+		   enum mailbox_list_flags *list_flags)
 {
 	const char *atom;
 
@@ -86,14 +133,9 @@
 		atom = IMAP_ARG_STR(args);
 
 		if (strcasecmp(atom, "SUBSCRIBED") == 0)
-			*list_flags |= MAILBOX_LIST_ITER_SUBSCRIBED;
+			*list_flags |= MAILBOX_LIST_ITER_RETURN_SUBSCRIBED;
 		else if (strcasecmp(atom, "CHILDREN") == 0)
-			*list_flags |= MAILBOX_LIST_ITER_CHILDREN;
-		else {
-			client_send_tagline(cmd, t_strconcat(
-				"BAD Invalid list option ", atom, NULL));
-			return FALSE;
-		}
+			*list_flags |= MAILBOX_LIST_ITER_RETURN_CHILDREN;
 		args++;
 	}
 	return TRUE;
@@ -132,7 +174,7 @@
 	bool ret = FALSE;
 
 	list_iter = mailbox_list_iter_init(ctx->ns->list, "%",
-					   MAILBOX_LIST_ITER_FAST_FLAGS);
+					   MAILBOX_LIST_ITER_RETURN_NO_FLAGS);
 	info = mailbox_list_iter_next(list_iter);
 	if (info != NULL)
 		ret = TRUE;
@@ -185,15 +227,17 @@
 			flags |= MAILBOX_NOCHILDREN;
 		}
 	}
-	
-	str = t_str_new(128);
-	str_append(str, "* LIST (");
-	mailbox_flags2str(str, flags, ctx->list_flags);
-	str_printfa(str, ") \"%s\" ", ctx->ns->sep_str);
 
 	name = ctx->cur_ns_skip_trailing_sep ?
 		t_strndup(ctx->ns->prefix, len-1) : ctx->ns->prefix;
+
+	str = t_str_new(128);
+	str_append(str, "* LIST (");
+	mailbox_flags2str(ctx, str, flags);
+	str_printfa(str, ") \"%s\" ", ctx->ns->sep_str);
 	imap_quote_append_string(str, name, FALSE);
+	mailbox_childinfo2str(ctx, str, flags);
+
 	client_send_line(ctx->cmd->client, str_c(str));
 }
 
@@ -285,9 +329,11 @@
 
 		str_truncate(str, 0);
 		str_printfa(str, "* %s (", ctx->lsub ? "LSUB" : "LIST");
-		mailbox_flags2str(str, flags, ctx->list_flags);
+		mailbox_flags2str(ctx, str, flags);
 		str_printfa(str, ") \"%s\" ", ctx->ns->sep_str);
 		imap_quote_append_string(str, name, FALSE);
+		mailbox_childinfo2str(ctx, str, flags);
+
 		if (client_send_line(ctx->cmd->client, str_c(str)) == 0) {
 			/* buffer is full, continue later */
 			t_pop();
@@ -461,7 +507,7 @@
 	cur_mask = ctx->mask;
 
 	if ((ctx->ns->flags & NAMESPACE_FLAG_HIDDEN) != 0 &&
-	    (ctx->list_flags & MAILBOX_LIST_ITER_SUBSCRIBED) != 0) {
+	    (ctx->list_flags & MAILBOX_LIST_ITER_SELECT_SUBSCRIBED) != 0) {
 		/* ignore hidden namespaces */
 		return;
 	}
@@ -509,7 +555,8 @@
 
 		if (match == IMAP_MATCH_YES &&
 		    (ns->flags & NAMESPACE_FLAG_LIST) != 0 &&
-		    (ctx->list_flags & MAILBOX_LIST_ITER_SUBSCRIBED) == 0)
+		    (ctx->list_flags &
+		     MAILBOX_LIST_ITER_SELECT_SUBSCRIBED) == 0)
 			ctx->cur_ns_send_prefix = TRUE;
 	}
 
@@ -555,7 +602,7 @@
 	/* INBOX always exists */
 	if (!ctx->inbox_found && ctx->cur_ns_match_inbox &&
 	    (ctx->ns->flags & NAMESPACE_FLAG_INBOX) != 0 &&
-	    (ctx->list_flags & MAILBOX_LIST_ITER_SUBSCRIBED) == 0) {
+	    (ctx->list_flags & MAILBOX_LIST_ITER_SELECT_SUBSCRIBED) == 0) {
 		str = t_strdup_printf("* LIST (\\Unmarked) \"%s\" \"INBOX\"",
 				      ctx->ns->sep_str);
 		client_send_line(ctx->cmd->client, str);
@@ -651,49 +698,70 @@
 	enum mailbox_list_flags list_flags;
         struct cmd_list_context *ctx;
 	const char *ref, *mask;
+	bool used_listext = FALSE;
 
-	/* [(<options>)] <reference> <mailbox wildcards> */
+	/* [(<selection options>)] <reference> <pattern>|(<pattern list>)
+	   [RETURN (<return options>)] */
 	if (!client_read_args(cmd, 0, 0, &args))
 		return FALSE;
 
 	if (lsub) {
 		/* LSUB - we don't care about flags */
-		list_flags = MAILBOX_LIST_ITER_SUBSCRIBED |
-			MAILBOX_LIST_ITER_FAST_FLAGS |
-			_MAILBOX_LIST_ITER_HIDE_CHILDREN;
+		list_flags = MAILBOX_LIST_ITER_SELECT_SUBSCRIBED |
+			MAILBOX_LIST_ITER_SELECT_RECURSIVEMATCH |
+			MAILBOX_LIST_ITER_RETURN_NO_FLAGS;
 	} else if (args[0].type != IMAP_ARG_LIST) {
 		/* LIST - allow children flags, but don't require them */
-		list_flags = 0;
+		list_flags = MAILBOX_LIST_ITER_RETURN_CHILDREN;
 	} else {
-		list_flags =
-			(enum mailbox_list_flags)_MAILBOX_LIST_ITER_LISTEXT;
-		if (!parse_list_flags(cmd, IMAP_ARG_LIST(&args[0])->args,
-				      &list_flags))
+		/* LIST-EXTENDED extension */
+		used_listext = TRUE;
+
+		if (!parse_select_flags(cmd, IMAP_ARG_LIST(&args[0])->args,
+					&list_flags))
 			return TRUE;
 		args++;
 
-		/* don't show children flags unless explicitly specified */
-		if ((list_flags & MAILBOX_LIST_ITER_CHILDREN) == 0)
-			list_flags |= _MAILBOX_LIST_ITER_HIDE_CHILDREN;
+		if (args[0].type == IMAP_ARG_EOL ||
+		    args[1].type == IMAP_ARG_EOL) {
+			client_send_command_error(cmd, "Invalid arguments.");
+			return TRUE;
+		}
+
+		if (args[2].type == IMAP_ARG_ATOM &&
+		    strcasecmp(imap_arg_string(&args[2]), "RETURN") == 0 &&
+		    args[3].type == IMAP_ARG_LIST &&
+		    args[4].type == IMAP_ARG_EOL) {
+			if (!parse_return_flags(cmd,
+						IMAP_ARG_LIST(&args[3])->args,
+						&list_flags))
+				return TRUE;
+		} else if (args[2].type != IMAP_ARG_EOL) {
+			client_send_command_error(cmd, "Invalid arguments.");
+			return TRUE;
+		}
 	}
 
 	ref = imap_arg_string(&args[0]);
-	mask = imap_arg_string(&args[1]);
+	mask = ref == NULL ? NULL : imap_arg_string(&args[1]);
 
-	if (ref == NULL || mask == NULL) {
+	if (ref == NULL || (mask == NULL && args[1].type != IMAP_ARG_LIST)) {
 		client_send_command_error(cmd, "Invalid arguments.");
 		return TRUE;
 	}
 
-	if (*mask == '\0' && !lsub) {
+	if (mask != NULL && *mask == '\0' && !lsub) {
+		/* only with mask string, not with list */
 		cmd_list_ref_root(client, ref);
 		client_send_tagline(cmd, "OK List completed.");
 	} else {
+		/* FIXME: handle mask lists */
 		ctx = p_new(cmd->pool, struct cmd_list_context, 1);
 		ctx->cmd = cmd;
 		ctx->ref = ref;
 		ctx->mask = mask;
 		ctx->list_flags = list_flags;
+		ctx->used_listext = used_listext;
 		ctx->lsub = lsub;
 		ctx->ns = client->namespaces;
 		p_array_init(&ctx->ns_prefixes_listed, cmd->pool, 8);

--- a/src/lib-storage/index/cydir/cydir-storage.c	Thu Jun 28 22:34:59 2007 +0300
+++ b/src/lib-storage/index/cydir/cydir-storage.c	Fri Jun 29 03:39:27 2007 +0300
@@ -359,7 +359,7 @@
 	if (type != MAILBOX_LIST_FILE_TYPE_DIR &&
 	    type != MAILBOX_LIST_FILE_TYPE_SYMLINK &&
 	    type != MAILBOX_LIST_FILE_TYPE_UNKNOWN &&
-	    (ctx->flags & MAILBOX_LIST_ITER_FAST_FLAGS) != 0) {
+	    (ctx->flags & MAILBOX_LIST_ITER_RETURN_NO_FLAGS) != 0) {
 		/* it's a file */
 		*flags |= MAILBOX_NOSELECT | MAILBOX_NOINFERIORS;
 		return 0;

--- a/src/lib-storage/index/dbox/dbox-storage.c	Thu Jun 28 22:34:59 2007 +0300
+++ b/src/lib-storage/index/dbox/dbox-storage.c	Fri Jun 29 03:39:27 2007 +0300
@@ -500,7 +500,7 @@
 	if (type != MAILBOX_LIST_FILE_TYPE_DIR &&
 	    type != MAILBOX_LIST_FILE_TYPE_SYMLINK &&
 	    type != MAILBOX_LIST_FILE_TYPE_UNKNOWN &&
-	    (ctx->flags & MAILBOX_LIST_ITER_FAST_FLAGS) != 0) {
+	    (ctx->flags & MAILBOX_LIST_ITER_RETURN_NO_FLAGS) != 0) {
 		/* it's a file */
 		*flags |= MAILBOX_NOSELECT | MAILBOX_NOINFERIORS;
 		return 0;

--- a/src/lib-storage/index/mbox/mbox-storage.c	Thu Jun 28 22:34:59 2007 +0300
+++ b/src/lib-storage/index/mbox/mbox-storage.c	Fri Jun 29 03:39:27 2007 +0300
@@ -804,7 +804,7 @@
 	}
 	if (type != MAILBOX_LIST_FILE_TYPE_SYMLINK &&
 	    type != MAILBOX_LIST_FILE_TYPE_UNKNOWN &&
-	    (ctx->flags & MAILBOX_LIST_ITER_FAST_FLAGS) != 0) {
+	    (ctx->flags & MAILBOX_LIST_ITER_RETURN_NO_FLAGS) != 0) {
 		*flags_r = MAILBOX_NOINFERIORS;
 		return 1;
 	}
@@ -827,9 +827,10 @@
 		}
 	} else if (errno == EACCES || errno == ELOOP)
 		*flags_r = MAILBOX_NOSELECT;
-	else if (ENOTFOUND(errno))
+	else if (ENOTFOUND(errno)) {
+		*flags_r = MAILBOX_NONEXISTENT;
 		ret = 0;
-	else {
+	} else {
 		mail_storage_set_critical(storage, "stat(%s) failed: %m", path);
 		ret = -1;
 	}

--- a/src/lib-storage/list/Makefile.am	Thu Jun 28 22:34:59 2007 +0300
+++ b/src/lib-storage/list/Makefile.am	Fri Jun 29 03:39:27 2007 +0300
@@ -15,6 +15,7 @@
 	mailbox-list-fs-iter.c \
 	mailbox-list-maildir.c \
 	mailbox-list-maildir-iter.c \
+	mailbox-list-subscriptions.c \
 	subscription-file.c
 
 headers = \

--- a/src/lib-storage/list/mailbox-list-fs-iter.c	Thu Jun 28 22:34:59 2007 +0300
+++ b/src/lib-storage/list/mailbox-list-fs-iter.c	Fri Jun 29 03:39:27 2007 +0300
@@ -4,7 +4,8 @@
 #include "home-expand.h"
 #include "unlink-directory.h"
 #include "imap-match.h"
-#include "subscription-file.h"
+#include "mailbox-tree.h"
+#include "mailbox-list-subscriptions.h"
 #include "mailbox-list-fs.h"
 
 #include <dirent.h>
@@ -20,7 +21,8 @@
 	struct mailbox_list_iterate_context ctx;
 
 	struct imap_match_glob *glob;
-	struct subsfile_list_context *subsfile_ctx;
+	struct mailbox_tree_context *subs_tree;
+	struct mailbox_tree_iterate_context *tree_iter;
 
 	bool inbox_found, inbox_listed;
 	enum mailbox_info_flags inbox_flags;
@@ -93,28 +95,29 @@
 	ctx->ctx.flags = flags;
 	ctx->info_pool = pool_alloconly_create("fs list", 1024);
         ctx->next = fs_list_next;
+	ctx->glob = imap_match_init(default_pool, mask, TRUE, '/');
 
 	/* check that we're not trying to do any "../../" lists */
-	if (!mailbox_list_is_valid_mask(_list, mask)) {
-		mailbox_list_set_error(_list, MAIL_ERROR_PARAMS,
-				       "Invalid mask");
-		ctx->ctx.failed = TRUE;
+	if (!mailbox_list_is_valid_mask(_list, mask))
 		return &ctx->ctx;
-	}
 
-	if ((flags & MAILBOX_LIST_ITER_SUBSCRIBED) != 0) {
-		ctx->next = fs_list_subs;
-
-		path = t_strconcat(_list->set.control_dir != NULL ?
-				   _list->set.control_dir : _list->set.root_dir,
-				   "/", _list->set.subscription_fname, NULL);
-		ctx->subsfile_ctx = subsfile_list_init(_list, path);
-		if (ctx->subsfile_ctx == NULL) {
-			ctx->next = fs_list_next;
+	if ((flags & (MAILBOX_LIST_ITER_SELECT_SUBSCRIBED |
+		      MAILBOX_LIST_ITER_RETURN_SUBSCRIBED)) != 0) {
+		/* we want to return MAILBOX_SUBSCRIBED flags, possibly for all
+		   mailboxes. Build a mailbox tree of all the subscriptions. */
+		ctx->subs_tree = mailbox_tree_init('/');
+		if (mailbox_list_subscriptions_fill(&ctx->ctx,
+						    ctx->subs_tree,
+						    ctx->glob, FALSE) < 0) {
 			ctx->ctx.failed = TRUE;
 			return &ctx->ctx;
 		}
-		ctx->glob = imap_match_init(default_pool, mask, TRUE, '/');
+	}
+
+	if ((flags & MAILBOX_LIST_ITER_SELECT_SUBSCRIBED) != 0) {
+		ctx->next = fs_list_subs;
+		ctx->tree_iter = mailbox_tree_iterate_init(ctx->subs_tree, NULL,
+							   MAILBOX_MATCHED);
 		return &ctx->ctx;
 	}
 
@@ -128,9 +131,6 @@
 		return &ctx->ctx;
 	/* if user gave invalid directory, we just don't show any results. */
 
-	ctx->ctx.flags = flags;
-	ctx->glob = imap_match_init(default_pool, mask, TRUE, '/');
-
 	if (virtual_path != NULL && dirp != NULL)
 		ctx->next = fs_list_path;
 
@@ -158,11 +158,6 @@
 
 	int ret = ctx->ctx.failed ? -1 : 0;
 
-	if (ctx->subsfile_ctx != NULL) {
-		if (subsfile_list_deinit(ctx->subsfile_ctx) < 0)
-			ret = -1;
-	}
-
 	while (ctx->dir != NULL) {
 		struct list_dir_context *dir = ctx->dir;
 
@@ -170,6 +165,10 @@
                 list_dir_context_free(dir);
 	}
 
+	if (ctx->tree_iter != NULL)
+		mailbox_tree_iterate_deinit(&ctx->tree_iter);
+	if (ctx->subs_tree != NULL)
+		mailbox_tree_deinit(&ctx->subs_tree);
 	if (ctx->info_pool != NULL)
 		pool_unref(ctx->info_pool);
 	if (ctx->glob != NULL)
@@ -206,6 +205,19 @@
 	}
 }
 
+static enum mailbox_info_flags
+fs_list_get_subscription_flags(struct fs_list_iterate_context *ctx,
+			       const char *mailbox)
+{
+	struct mailbox_node *node;
+
+	node = mailbox_tree_lookup(ctx->subs_tree, mailbox);
+	if (node == NULL)
+		return 0;
+
+	return node->flags & (MAILBOX_SUBSCRIBED | MAILBOX_CHILD_SUBSCRIBED);
+}
+
 static struct mailbox_info *fs_list_inbox(struct fs_list_iterate_context *ctx)
 {
 	const char *inbox_path, *dir, *fname;
@@ -223,6 +235,7 @@
 		ctx->ctx.failed = TRUE;
 	t_pop();
 
+	ctx->info.flags |= fs_list_get_subscription_flags(ctx, "INBOX");
 	return &ctx->info;
 }
 
@@ -262,6 +275,11 @@
 	if (ret <= 0)
 		return ret;
 
+	if ((ctx->ctx.flags & MAILBOX_LIST_ITER_RETURN_SUBSCRIBED) != 0) {
+		ctx->info.flags |=
+			fs_list_get_subscription_flags(ctx, list_path);
+	}
+
 	/* make sure we give only one correct INBOX */
 	real_path = t_strconcat(ctx->dir->real_path, "/", fname, NULL);
 	if ((ctx->ctx.list->ns->flags & NAMESPACE_FLAG_INBOX) != 0 &&
@@ -337,38 +355,23 @@
 static const struct mailbox_info *
 fs_list_subs(struct fs_list_iterate_context *ctx)
 {
-	const char *name, *path, *p, *dir, *fname;
-	enum imap_match_result match = IMAP_MATCH_NO;
+	struct mailbox_node *node;
+	enum mailbox_info_flags flags;
+	const char *path, *dir, *fname;
 
-	while ((name = subsfile_list_next(ctx->subsfile_ctx)) != NULL) {
-		match = imap_match(ctx->glob, name);
-		if (match == IMAP_MATCH_YES || match == IMAP_MATCH_PARENT)
-			break;
-	}
-
-	if (name == NULL)
+	node = mailbox_tree_iterate_next(ctx->tree_iter, &ctx->info.name);
+	if (node == NULL)
 		return NULL;
 
-	ctx->info.flags = 0;
-	ctx->info.name = name;
+	/* subscription list has real knowledge of only subscription flags */
+	flags = node->flags & (MAILBOX_SUBSCRIBED | MAILBOX_CHILD_SUBSCRIBED);
 
-	if (match == IMAP_MATCH_PARENT) {
-		/* placeholder */
-		ctx->info.flags = MAILBOX_NONEXISTENT | MAILBOX_CHILDREN;
-		while ((p = strrchr(name, '/')) != NULL) {
-			name = t_strdup_until(name, p);
-			if (imap_match(ctx->glob, name) > 0) {
-				p_clear(ctx->info_pool);
-				ctx->info.name = p_strdup(ctx->info_pool, name);
-				return &ctx->info;
-			}
-		}
-		i_unreached();
+	if ((ctx->ctx.flags & MAILBOX_LIST_ITER_RETURN_NO_FLAGS) != 0 &&
+	    (ctx->ctx.flags & MAILBOX_LIST_ITER_RETURN_CHILDREN) == 0) {
+		ctx->info.flags = flags;
+		return &ctx->info;
 	}
 
-	if ((ctx->ctx.flags & MAILBOX_LIST_ITER_FAST_FLAGS) != 0)
-		return &ctx->info;
-
 	t_push();
 	path = mailbox_list_get_path(ctx->ctx.list, ctx->info.name,
 				     MAILBOX_LIST_PATH_TYPE_DIR);
@@ -378,6 +381,8 @@
 					     &ctx->info.flags) < 0)
 		ctx->ctx.failed = TRUE;
 	t_pop();
+
+	ctx->info.flags |= flags;
 	return &ctx->info;
 }
 
@@ -428,12 +433,14 @@
 	if (!ctx->inbox_found &&
 	    (ctx->ctx.list->ns->flags & NAMESPACE_FLAG_INBOX) != 0 &&
 	    ctx->glob != NULL && imap_match(ctx->glob, "INBOX") > 0) {
-		/* show inbox */
+		/* INBOX wasn't seen while listing other mailboxes. It might
+		   be located elsewhere. */
 		ctx->inbox_listed = TRUE;
 		ctx->inbox_found = TRUE;
 		return fs_list_inbox(ctx);
 	}
 	if (!ctx->inbox_listed && ctx->inbox_found) {
+		/* INBOX was found, but we delayed listing it. Show it now. */
 		ctx->inbox_listed = TRUE;
 		ctx->info.flags = ctx->inbox_flags;
 		ctx->info.name = "INBOX";

--- a/src/lib-storage/list/mailbox-list-maildir-iter.c	Thu Jun 28 22:34:59 2007 +0300
+++ b/src/lib-storage/list/mailbox-list-maildir-iter.c	Fri Jun 29 03:39:27 2007 +0300
@@ -4,14 +4,12 @@
 #include "str.h"
 #include "home-expand.h"
 #include "imap-match.h"
-#include "subscription-file.h"
 #include "mailbox-tree.h"
+#include "mailbox-list-subscriptions.h"
 #include "mailbox-list-maildir.h"
 
 #include <dirent.h>
 
-#define MAILBOX_FLAG_MATCHED 0x40000000
-
 struct maildir_list_iterate_context {
 	struct mailbox_list_iterate_context ctx;
 	pool_t pool;
@@ -24,24 +22,6 @@
 	struct mailbox_info info;
 };
 
-static void maildir_nodes_fix(struct mailbox_node *node, bool is_subs)
-{
-	while (node != NULL) {
-		if (node->children != NULL) {
-			node->flags |= MAILBOX_CHILDREN;
-			node->flags &= ~MAILBOX_NOCHILDREN;
-			maildir_nodes_fix(node->children, is_subs);
-		} else if ((node->flags & MAILBOX_NONEXISTENT) != 0) {
-			if (!is_subs) {
-				node->flags &= ~MAILBOX_NONEXISTENT;
-				node->flags |= MAILBOX_NOSELECT;
-			}
-			node->flags |= MAILBOX_CHILDREN;
-		}
-		node = node->next;
-	}
-}
-
 static int
 maildir_fill_readdir(struct maildir_list_iterate_context *ctx,
 		     struct imap_match_glob *glob, bool update_only)
@@ -107,6 +87,7 @@
 			continue;
 
 		if (match == IMAP_MATCH_PARENT) {
+			/* get the name of the parent mailbox that matches */
 			t_push();
 			while ((p = strrchr(mailbox_c,
 					    hierarchy_sep)) != NULL) {
@@ -119,15 +100,18 @@
 
 			created = FALSE;
 			node = update_only ?
-				mailbox_tree_update(ctx->tree_ctx, mailbox_c) :
+				mailbox_tree_lookup(ctx->tree_ctx, mailbox_c) :
 				mailbox_tree_get(ctx->tree_ctx,
 						 mailbox_c, &created);
 			if (node != NULL) {
-				if (created)
+				if (created) {
+					/* we haven't yet seen this mailbox,
+					   but we might see it later */
 					node->flags = MAILBOX_NONEXISTENT;
-
-				node->flags |= MAILBOX_CHILDREN |
-					MAILBOX_FLAG_MATCHED;
+				}
+				if (!update_only)
+					node->flags |= MAILBOX_MATCHED;
+				node->flags |= MAILBOX_CHILDREN;
 				node->flags &= ~MAILBOX_NOCHILDREN;
 			}
 
@@ -135,21 +119,37 @@
 		} else {
 			created = FALSE;
 			node = update_only ?
-				mailbox_tree_update(ctx->tree_ctx, mailbox_c) :
+				mailbox_tree_lookup(ctx->tree_ctx, mailbox_c) :
 				mailbox_tree_get(ctx->tree_ctx,
 						 mailbox_c, &created);
 
 			if (node != NULL) {
 				if (created)
 					node->flags = MAILBOX_NOCHILDREN;
-				node->flags &= ~MAILBOX_NONEXISTENT;
-				node->flags |= MAILBOX_FLAG_MATCHED;
+				else
+					node->flags &= ~MAILBOX_NONEXISTENT;
+				if (!update_only)
+					node->flags |= MAILBOX_MATCHED;
 			}
 		}
 		if (node != NULL) {
+			/* apply flags given by storage. we know the children
+			   flags ourself, so ignore if any of them were set. */
 			node->flags |= flags & ~(MAILBOX_NOINFERIORS |
 						 MAILBOX_CHILDREN |
 						 MAILBOX_NOCHILDREN);
+
+			/* Fix parent nodes' children states. also if we
+			   happened to create any of the parents, we need to
+			   mark them nonexistent. */
+			node = node->parent;
+			for (; node != NULL; node = node->parent) {
+				if ((node->flags & MAILBOX_MATCHED) == 0)
+					node->flags |= MAILBOX_NONEXISTENT;
+
+				node->flags |= MAILBOX_CHILDREN;
+				node->flags &= ~MAILBOX_NOCHILDREN;
+			}
 		}
 	}
 	t_pop();
@@ -160,10 +160,12 @@
 		return -1;
 	}
 
-	if ((ctx->ctx.list->ns->flags & NAMESPACE_FLAG_INBOX) != 0 &&
-	    (ctx->ctx.flags & MAILBOX_LIST_ITER_SUBSCRIBED) == 0) {
+	if ((ctx->ctx.list->ns->flags & NAMESPACE_FLAG_INBOX) != 0) {
 		/* make sure INBOX is there */
-		node = mailbox_tree_get(ctx->tree_ctx, "INBOX", &created);
+		created = FALSE;
+		node = update_only ?
+			mailbox_tree_lookup(ctx->tree_ctx, "INBOX") :
+			mailbox_tree_get(ctx->tree_ctx, "INBOX", &created);
 		if (created)
 			node->flags = MAILBOX_NOCHILDREN;
 		else
@@ -172,66 +174,16 @@
 		switch (imap_match(glob, "INBOX")) {
 		case IMAP_MATCH_YES:
 		case IMAP_MATCH_PARENT:
-			node->flags |= MAILBOX_FLAG_MATCHED;
+			if (!update_only)
+				node->flags |= MAILBOX_MATCHED;
 			break;
 		default:
 			break;
 		}
 	}
-	maildir_nodes_fix(mailbox_tree_get(ctx->tree_ctx, NULL, NULL),
-			  (ctx->ctx.flags & MAILBOX_LIST_ITER_SUBSCRIBED) != 0);
 	return 0;
 }
 
-static int maildir_fill_subscribed(struct maildir_list_iterate_context *ctx,
-				   struct imap_match_glob *glob)
-{
-	struct subsfile_list_context *subsfile_ctx;
-	const char *path, *name, *p;
-	struct mailbox_node *node;
-	char hierarchy_sep;
-	bool created;
-
-	path = t_strconcat(ctx->ctx.list->set.control_dir != NULL ?
-			   ctx->ctx.list->set.control_dir :
-			   ctx->ctx.list->set.root_dir,
-			   "/", ctx->ctx.list->set.subscription_fname, NULL);
-	subsfile_ctx = subsfile_list_init(ctx->ctx.list, path);
-
-	hierarchy_sep = ctx->ctx.list->hierarchy_sep;
-	while ((name = subsfile_list_next(subsfile_ctx)) != NULL) {
-		switch (imap_match(glob, name)) {
-		case IMAP_MATCH_YES:
-			node = mailbox_tree_get(ctx->tree_ctx, name, NULL);
-			node->flags = MAILBOX_FLAG_MATCHED;
-			if ((ctx->ctx.flags &
-			     MAILBOX_LIST_ITER_FAST_FLAGS) == 0) {
-				node->flags |= MAILBOX_NONEXISTENT |
-					MAILBOX_NOCHILDREN;
-			}
-			break;
-		case IMAP_MATCH_PARENT:
-			/* placeholder */
-			while ((p = strrchr(name, hierarchy_sep)) != NULL) {
-				name = t_strdup_until(name, p);
-				if (imap_match(glob, name) > 0)
-					break;
-			}
-			i_assert(p != NULL);
-
-			node = mailbox_tree_get(ctx->tree_ctx, name, &created);
-			if (created) node->flags = MAILBOX_NONEXISTENT;
-			node->flags |= MAILBOX_FLAG_MATCHED | MAILBOX_CHILDREN;
-			node->flags &= ~MAILBOX_NOCHILDREN;
-			break;
-		default:
-			break;
-		}
-	}
-
-	return subsfile_list_deinit(subsfile_ctx);
-}
-
 struct mailbox_list_iterate_context *
 maildir_list_iter_init(struct mailbox_list *_list, const char *mask,
 		       enum mailbox_list_iter_flags flags)
@@ -253,13 +205,17 @@
 	ctx->dir = _list->set.root_dir;
 	ctx->prefix = "";
 
-	if ((flags & MAILBOX_LIST_ITER_SUBSCRIBED) != 0) {
-		if (maildir_fill_subscribed(ctx, glob) < 0) {
+	if ((flags & MAILBOX_LIST_ITER_SELECT_SUBSCRIBED) != 0) {
+		/* Listing only subscribed mailboxes.
+		   Flags are set later if needed. */
+		if (mailbox_list_subscriptions_fill(&ctx->ctx, ctx->tree_ctx,
+						    glob, FALSE) < 0) {
 			ctx->ctx.failed = TRUE;
 			return &ctx->ctx;
 		}
 	} else if ((_list->flags & MAILBOX_LIST_FLAG_FULL_FS_ACCESS) != 0 &&
 		   (p = strrchr(mask, '/')) != NULL) {
+		/* Listing non-default maildir */
 		dir = t_strdup_until(mask, p);
 		ctx->prefix = p_strdup_until(pool, mask, p+1);
 
@@ -268,17 +224,31 @@
 		ctx->dir = p_strdup(pool, home_expand(dir));
 	}
 
-	if ((flags & MAILBOX_LIST_ITER_SUBSCRIBED) == 0 ||
-	    (ctx->ctx.flags & MAILBOX_LIST_ITER_FAST_FLAGS) == 0) {
-		bool update_only = (flags & MAILBOX_LIST_ITER_SUBSCRIBED) != 0;
+	if ((flags & MAILBOX_LIST_ITER_SELECT_SUBSCRIBED) == 0 ||
+	    (flags & MAILBOX_LIST_ITER_RETURN_NO_FLAGS) == 0) {
+		/* Add/update mailbox list with flags */
+		bool update_only =
+			(flags & MAILBOX_LIST_ITER_SELECT_SUBSCRIBED) != 0;
+
 		if (maildir_fill_readdir(ctx, glob, update_only) < 0) {
 			ctx->ctx.failed = TRUE;
 			return &ctx->ctx;
 		}
 	}
 
+	if ((flags & MAILBOX_LIST_ITER_RETURN_SUBSCRIBED) != 0 &&
+	    (flags & MAILBOX_LIST_ITER_SELECT_SUBSCRIBED) == 0) {
+		/* we're listing all mailboxes but we want to know
+		   \Subscribed flags */
+		if (mailbox_list_subscriptions_fill(&ctx->ctx, ctx->tree_ctx,
+						    glob, TRUE) < 0) {
+			ctx->ctx.failed = TRUE;
+			return &ctx->ctx;
+		}
+	}
+
 	ctx->tree_iter = mailbox_tree_iterate_init(ctx->tree_ctx, NULL,
-						   MAILBOX_FLAG_MATCHED);
+						   MAILBOX_MATCHED);
 	return &ctx->ctx;
 }
 

--- a/src/lib-storage/list/mailbox-list-maildir.c	Thu Jun 28 22:34:59 2007 +0300
+++ b/src/lib-storage/list/mailbox-list-maildir.c	Fri Jun 29 03:39:27 2007 +0300
@@ -294,7 +294,8 @@
 
 	mask = t_strdup_printf("%s%c*", oldname,
 			       mailbox_list_get_hierarchy_sep(list));
-	iter = mailbox_list_iter_init(list, mask, MAILBOX_LIST_ITER_FAST_FLAGS);
+	iter = mailbox_list_iter_init(list, mask,
+				      MAILBOX_LIST_ITER_RETURN_NO_FLAGS);
 	while ((info = mailbox_list_iter_next(iter)) != NULL) {
 		const char *name;
 

--- a/src/lib-storage/mailbox-list.h	Thu Jun 28 22:34:59 2007 +0300
+++ b/src/lib-storage/mailbox-list.h	Fri Jun 29 03:39:27 2007 +0300
@@ -17,13 +17,18 @@
 };
 
 enum mailbox_info_flags {
-	MAILBOX_NOSELECT	= 0x001,
-	MAILBOX_NONEXISTENT	= 0x002,
-	MAILBOX_CHILDREN	= 0x004,
-	MAILBOX_NOCHILDREN	= 0x008,
-	MAILBOX_NOINFERIORS	= 0x010,
-	MAILBOX_MARKED		= 0x020,
-	MAILBOX_UNMARKED	= 0x040
+	MAILBOX_NOSELECT		= 0x001,
+	MAILBOX_NONEXISTENT		= 0x002,
+	MAILBOX_CHILDREN		= 0x004,
+	MAILBOX_NOCHILDREN		= 0x008,
+	MAILBOX_NOINFERIORS		= 0x010,
+	MAILBOX_MARKED			= 0x020,
+	MAILBOX_UNMARKED		= 0x040,
+	MAILBOX_SUBSCRIBED		= 0x080,
+	MAILBOX_CHILD_SUBSCRIBED	= 0x100,
+
+	/* Internally used by lib-storage */
+	MAILBOX_MATCHED			= 0x40000000
 };
 
 enum mailbox_name_status {
@@ -34,14 +39,21 @@
 };
 
 enum mailbox_list_iter_flags {
+	/* Ignore index file and ACLs (used by ACL plugin internally) */
+	MAILBOX_LIST_ITER_RAW_LIST		= 0x000001,
+
 	/* List only subscribed mailboxes */
-	MAILBOX_LIST_ITER_SUBSCRIBED	= 0x01,
+	MAILBOX_LIST_ITER_SELECT_SUBSCRIBED	= 0x000010,
+	/* Return MAILBOX_CHILD_* if mailbox's children match selection
+	   criteria, even if the mailbox itself wouldn't match. */
+	MAILBOX_LIST_ITER_SELECT_RECURSIVEMATCH	= 0x000020,
+
 	/* Don't return any flags unless it can be done without cost */
-	MAILBOX_LIST_ITER_FAST_FLAGS	= 0x02,
+	MAILBOX_LIST_ITER_RETURN_NO_FLAGS	= 0x001000,
+	/* Return MAILBOX_SUBSCRIBED flag */
+	MAILBOX_LIST_ITER_RETURN_SUBSCRIBED	= 0x002000,
 	/* Return children flags */
-	MAILBOX_LIST_ITER_CHILDREN	= 0x04,
-	/* Ignore index file and ACLs (used by ACL plugin internally) */
-	MAILBOX_LIST_ITER_RAW_LIST	= 0x08
+	MAILBOX_LIST_ITER_RETURN_CHILDREN	= 0x004000
 };
 
 enum mailbox_list_path_type {

--- a/src/lib-storage/mailbox-tree.c	Thu Jun 28 22:34:59 2007 +0300
+++ b/src/lib-storage/mailbox-tree.c	Fri Jun 29 03:39:27 2007 +0300
@@ -49,7 +49,7 @@
 mailbox_tree_traverse(struct mailbox_tree_context *tree, const char *path,
 		      bool create, bool *created)
 {
-	struct mailbox_node **node;
+	struct mailbox_node **node, *parent;
 	const char *name;
 	string_t *str;
 
@@ -65,6 +65,7 @@
 	    (path[5] == '\0' || path[5] == tree->separator))
 		path = t_strdup_printf("INBOX%s", path+5);
 
+	parent = NULL;
 	node = &tree->nodes;
 
 	str = t_str_new(strlen(path)+1);
@@ -90,6 +91,7 @@
 				break;
 
 			*node = p_new(tree->pool, struct mailbox_node, 1);
+			(*node)->parent = parent;
 			(*node)->name = p_strdup(tree->pool, name);
 
 			if (*path != '\0') {
@@ -106,6 +108,8 @@
 		(*node)->flags |= MAILBOX_CHILDREN;
 		(*node)->flags &= ~(MAILBOX_NOCHILDREN | MAILBOX_NOINFERIORS);
 		name = path+1;
+
+		parent = *node;
 		node = &(*node)->children;
 	}
 	t_pop();
@@ -121,7 +125,7 @@
 }
 
 struct mailbox_node *
-mailbox_tree_update(struct mailbox_tree_context *tree, const char *path)
+mailbox_tree_lookup(struct mailbox_tree_context *tree, const char *path)
 {
 	return mailbox_tree_traverse(tree, path, FALSE, NULL);
 }

--- a/src/lib-storage/mailbox-tree.h	Thu Jun 28 22:34:59 2007 +0300
+++ b/src/lib-storage/mailbox-tree.h	Fri Jun 29 03:39:27 2007 +0300
@@ -4,6 +4,7 @@
 #include "mailbox-list.h"
 
 struct mailbox_node {
+	struct mailbox_node *parent;
 	struct mailbox_node *next;
 	struct mailbox_node *children;
 
@@ -19,7 +20,7 @@
 		 bool *created);
 
 struct mailbox_node *
-mailbox_tree_update(struct mailbox_tree_context *tree, const char *path);
+mailbox_tree_lookup(struct mailbox_tree_context *tree, const char *path);
 
 struct mailbox_tree_iterate_context *
 mailbox_tree_iterate_init(struct mailbox_tree_context *tree,

--- a/src/plugins/acl/acl-backend-vfile-acllist.c	Thu Jun 28 22:34:59 2007 +0300
+++ b/src/plugins/acl/acl-backend-vfile-acllist.c	Fri Jun 29 03:39:27 2007 +0300
@@ -214,8 +214,8 @@
 	ns = mailbox_list_get_namespace(list);
 
 	backend->rebuilding_acllist = TRUE;
-	iter = mailbox_list_iter_init(list, "*", MAILBOX_LIST_ITER_FAST_FLAGS |
-				      MAILBOX_LIST_ITER_RAW_LIST);
+	iter = mailbox_list_iter_init(list, "*", MAILBOX_LIST_ITER_RAW_LIST |
+				      MAILBOX_LIST_ITER_RETURN_NO_FLAGS);
 	while ((info = mailbox_list_iter_next(iter)) != NULL) {
 		if (acllist_append(backend, output, ns->storage,
 				   info->name) < 0) {

--- a/src/plugins/acl/acl-mailbox-list.c	Thu Jun 28 22:34:59 2007 +0300
+++ b/src/plugins/acl/acl-mailbox-list.c	Fri Jun 29 03:39:27 2007 +0300
@@ -195,16 +195,14 @@
 		}
 
 		/* no permission to see this mailbox */
-		if ((ctx->ctx.flags & MAILBOX_LIST_ITER_SUBSCRIBED) != 0) {
+		if ((ctx->info.flags & MAILBOX_SUBSCRIBED) != 0) {
 			/* it's subscribed, show it as non-existent */
-			if ((ctx->ctx.flags &
-			     MAILBOX_LIST_ITER_FAST_FLAGS) == 0) {
-				if (info != &ctx->info) {
-					ctx->info = *info;
-					info = &ctx->info;
-				}
-				ctx->info.flags = MAILBOX_NONEXISTENT;
+			if (info != &ctx->info) {
+				ctx->info = *info;
+				info = &ctx->info;
 			}
+			ctx->info.flags = MAILBOX_NONEXISTENT |
+				MAILBOX_SUBSCRIBED;
 			return info;
 		}
 

--- a/src/plugins/convert/convert-storage.c	Thu Jun 28 22:34:59 2007 +0300
+++ b/src/plugins/convert/convert-storage.c	Fri Jun 29 03:39:27 2007 +0300
@@ -213,7 +213,7 @@
 	int ret = 0;
 
 	iter = mailbox_list_iter_init(mail_storage_get_list(source_storage),
-				      "*", MAILBOX_LIST_ITER_FAST_FLAGS);
+				      "*", MAILBOX_LIST_ITER_RETURN_NO_FLAGS);
 	while ((info = mailbox_list_iter_next(iter)) != NULL) {
 		if (mailbox_convert_list_item(source_storage, dest_storage,
 					      info, dotlock, set) < 0) {
@@ -242,8 +242,8 @@
 
 	dest_list = mail_storage_get_list(dest_storage);
 	iter = mailbox_list_iter_init(mail_storage_get_list(source_storage),
-				      "*", MAILBOX_LIST_ITER_SUBSCRIBED |
-				      MAILBOX_LIST_ITER_FAST_FLAGS);
+				      "*", MAILBOX_LIST_ITER_SELECT_SUBSCRIBED |
+				      MAILBOX_LIST_ITER_RETURN_NO_FLAGS);
 	while ((info = mailbox_list_iter_next(iter)) != NULL) {
 		dest_name = mailbox_name_convert(dest_storage, source_storage,
 						 set, info->name);

--- a/src/plugins/quota/quota-count.c	Thu Jun 28 22:34:59 2007 +0300
+++ b/src/plugins/quota/quota-count.c	Fri Jun 29 03:39:27 2007 +0300
@@ -55,7 +55,7 @@
 	int ret = 0;
 
 	ctx = mailbox_list_iter_init(storage->list, "*",
-				     MAILBOX_LIST_ITER_FAST_FLAGS);
+				     MAILBOX_LIST_ITER_RETURN_NO_FLAGS);
 	while ((info = mailbox_list_iter_next(ctx)) != NULL) {
 		if ((info->flags & (MAILBOX_NONEXISTENT |
 				    MAILBOX_NOSELECT)) == 0) {

--- a/src/plugins/quota/quota-maildir.c	Thu Jun 28 22:34:59 2007 +0300
+++ b/src/plugins/quota/quota-maildir.c	Fri Jun 29 03:39:27 2007 +0300
@@ -136,7 +136,7 @@
 	ctx->storage = storage;
 	ctx->path = str_new(default_pool, 512);
 	ctx->iter = mailbox_list_iter_init(mail_storage_get_list(storage), "*",
-					   MAILBOX_LIST_ITER_FAST_FLAGS);
+					   MAILBOX_LIST_ITER_RETURN_NO_FLAGS);
 	return ctx;
 }