thodg/got

diff --git a/got/Makefile b/got/Makefile
index a0db6ed..59cca6f 100644
--- a/got/Makefile
+++ b/got/Makefile
@@ -3,8 +3,9 @@
 PROG=		got
 SRCS=		got.c blame.c commit_graph.c delta.c diff.c diffoffset.c \
 		diffreg.c error.c fileindex.c object.c object_cache.c \
-		object_idset.c object_parse.c opentemp.c path.c pack.c \
-		privsep.c reference.c repository.c sha1.c worktree.c inflate.c
+		object_idset.c object_parse.c opentemp.c path.c pathset.c \
+		pack.c privsep.c reference.c repository.c sha1.c worktree.c \
+		inflate.c
 
 CPPFLAGS = -I${.CURDIR}/../include -I${.CURDIR}/../lib \
 	-DGOT_LIBEXECDIR=${GOT_LIBEXECDIR}
diff --git a/lib/worktree.c b/lib/worktree.c
index e43e15f..a728112 100644
--- a/lib/worktree.c
+++ b/lib/worktree.c
@@ -39,6 +39,7 @@
 
 #include "got_lib_worktree.h"
 #include "got_lib_path.h"
+#include "got_lib_pathset.h"
 #include "got_lib_sha1.h"
 #include "got_lib_fileindex.h"
 #include "got_lib_inflate.h"
@@ -740,13 +741,14 @@ done:
 struct collect_missing_entry_args {
 	struct got_fileindex *fileindex;
 	const struct got_tree_entries *entries;
-	struct got_fileindex missing_entries;
+	struct got_pathset *missing_entries;
 	const char *current_subdir;
 };
 
 static const struct got_error *
 collect_missing_file(void *args, struct got_fileindex_entry *entry)
 {
+	const struct got_error *err = NULL;
 	struct collect_missing_entry_args *a = args;
 	char *start, *end;
 	ptrdiff_t len;
@@ -781,7 +783,51 @@ collect_missing_file(void *args, struct got_fileindex_entry *entry)
 		return NULL;
 
 	got_fileindex_entry_remove(a->fileindex, entry);
-	return got_fileindex_entry_add(&a->missing_entries, entry);
+	err = got_pathset_add(a->missing_entries, entry->path, NULL);
+	got_fileindex_entry_free(entry);
+	return err;
+}
+
+struct remove_missing_file_args {
+    const char *root_path;
+    got_worktree_checkout_cb progress_cb;
+    void *progress_arg;
+    got_worktree_cancel_cb cancel_cb;
+    void *cancel_arg;
+};
+
+static const struct got_error *
+remove_missing_file(const char *path, void *data, void *arg)
+{
+	const struct got_error *err = NULL;
+	char *ondisk_path = NULL;
+	struct remove_missing_file_args *a = arg;
+
+	if (a->cancel_cb) {
+		err = (*a->cancel_cb)(a->cancel_arg);
+		if (err)
+			return err;
+	}
+
+	(*a->progress_cb)(a->progress_arg, GOT_STATUS_DELETE, path);
+
+	if (asprintf(&ondisk_path, "%s/%s", a->root_path, path) == -1)
+		return got_error_from_errno();
+
+	if (unlink(ondisk_path) == -1)
+		err = got_error_from_errno();
+	else {
+		char *parent = dirname(ondisk_path);
+		while (parent && strcmp(parent, a->root_path) != 0) {
+			if (rmdir(parent) == -1 && errno != ENOTEMPTY) {
+				err = got_error_from_errno();
+				break;
+			}
+			parent = dirname(parent);
+		}
+	}
+	free(ondisk_path);
+	return err;
 }
 
 /* Remove files which exist in the file index but not in the tree. */
@@ -793,58 +839,27 @@ remove_missing_files(struct got_worktree *worktree, const char *path,
 {
 	const struct got_error *err = NULL;
 	struct collect_missing_entry_args a;
-	struct got_fileindex_entry *entry, *tmp;
+	struct remove_missing_file_args a2;
 
 	a.fileindex = fileindex;
 	a.entries = entries;
-	a.missing_entries.nentries = 0;
+	a.missing_entries = got_pathset_alloc();
+	if (a.missing_entries == NULL)
+		return got_error_from_errno();
 	a.current_subdir = apply_path_prefix(worktree, path);
-	TAILQ_INIT(&a.missing_entries.entries);
 	err = got_fileindex_for_each_entry_safe(fileindex,
 	    collect_missing_file, &a);
 	if (err)
 		return err;
 
-	TAILQ_FOREACH_SAFE(entry, &a.missing_entries.entries, entry, tmp) {
-		char *ondisk_path = NULL;
-
-		if (cancel_cb) {
-			err = (*cancel_cb)(cancel_arg);
-			if (err)
-				break;
-		}
-
-		(*progress_cb)(progress_arg, GOT_STATUS_DELETE, entry->path);
-
-		if (asprintf(&ondisk_path, "%s/%s", worktree->root_path,
-		    entry->path) == -1) {
-			err = got_error_from_errno();
-			break;
-		}
-
-		if (unlink(ondisk_path) == -1)
-			err = got_error_from_errno();
-		else {
-			char *parent = dirname(ondisk_path);
-			if (rmdir(parent) == -1 && errno != ENOTEMPTY)
-				err = got_error_from_errno();
-		}
-		free(ondisk_path);
-		if (err)
-			break;
-
-		TAILQ_REMOVE(&a.missing_entries.entries, entry, entry);
-		got_fileindex_entry_free(entry);
-	}
-
-	if (err) {
-		while (!TAILQ_EMPTY(&a.missing_entries.entries)) {
-			entry = TAILQ_FIRST(&a.missing_entries.entries);
-			TAILQ_REMOVE(&a.missing_entries.entries, entry, entry);
-			got_fileindex_entry_free(entry);
-		}
-	}
+	a2.root_path = worktree->root_path;
+	a2.cancel_cb = cancel_cb;
+	a2.cancel_arg = cancel_arg;
+	a2.progress_cb = progress_cb;
+	a2.progress_arg = progress_arg;
 
+	err = got_pathset_for_each(a.missing_entries, remove_missing_file, &a2);
+	got_pathset_free(a.missing_entries);
 	return err;
 }
 
diff --git a/regress/cmdline/update.sh b/regress/cmdline/update.sh
index 5c505f1..eb351e5 100755
--- a/regress/cmdline/update.sh
+++ b/regress/cmdline/update.sh
@@ -199,8 +199,50 @@ function test_update_deletes_dir_with_path_prefix {
 	test_done "$testroot" "0"
 }
 
+function test_update_deletes_dir_recursively {
+	local testroot=`test_init update_deletes_dir_recursively`
+	local first_rev=`git_show_head $testroot/repo`
+
+	mkdir $testroot/repo/epsilon/psi
+	echo mu > $testroot/repo/epsilon/psi/mu
+	mkdir $testroot/repo/epsilon/psi/chi
+	echo tau > $testroot/repo/epsilon/psi/chi/tau
+	(cd $testroot/repo && git add .)
+	git_commit $testroot/repo -m "adding a sub-directory beneath epsilon"
+
+	# check out the epsilon/ sub-tree
+	got checkout -p epsilon $testroot/repo $testroot/wt > /dev/null
+	if [ "$?" != "0" ]; then
+		test_done "$testroot" "$?"
+		return 1
+	fi
+
+	# update back to first commit and expect psi/mu to be deleted
+	echo "D  psi/chi/tau" > $testroot/stdout.expected
+	echo "D  psi/mu" >> $testroot/stdout.expected
+	echo "Updated to commit $first_rev" >> $testroot/stdout.expected
+
+	(cd $testroot/wt && got update -c $first_rev > $testroot/stdout)
+
+	cmp $testroot/stdout.expected $testroot/stdout
+	if [ "$?" != "0" ]; then
+		diff -u $testroot/stdout.expected $testroot/stdout
+		test_done "$testroot" "$?"
+		return 1
+	fi
+
+	if [ -e $testroot/wt/psi ]; then
+		echo "removed dir psi still exists on disk" >&2
+		test_done "$testroot" "1"
+		return 1
+	fi
+
+	test_done "$testroot" "0"
+}
+
 run_test test_update_basic
 run_test test_update_adds_file
 run_test test_update_deletes_file
 run_test test_update_deletes_dir
 run_test test_update_deletes_dir_with_path_prefix
+run_test test_update_deletes_dir_recursively
diff --git a/regress/idset/Makefile b/regress/idset/Makefile
index 622918d..7046be7 100644
--- a/regress/idset/Makefile
+++ b/regress/idset/Makefile
@@ -1,9 +1,9 @@
 .PATH:${.CURDIR}/../../lib
 
 PROG = idset_test
-SRCS = error.c object.c privsep.c sha1.c pack.c inflate.c path.c opentemp.c \
-	delta.c repository.c reference.c worktree.c fileindex.c object_cache.c \
-	object_idset.c object_parse.c idset_test.c
+SRCS = error.c object.c privsep.c sha1.c pack.c inflate.c path.c pathset.c \
+	opentemp.c delta.c repository.c reference.c worktree.c fileindex.c \
+	object_cache.c object_idset.c object_parse.c idset_test.c
 
 CPPFLAGS = -I${.CURDIR}/../../include -I${.CURDIR}/../../lib
 LDADD = -lutil -lz
diff --git a/regress/repository/Makefile b/regress/repository/Makefile
index 5da0a61..7eba96e 100644
--- a/regress/repository/Makefile
+++ b/regress/repository/Makefile
@@ -4,7 +4,7 @@ PROG = repository_test
 SRCS = path.c repository.c error.c reference.c object.c object_cache.c \
 	object_idset.c object_parse.c opentemp.c sha1.c diff.c diffreg.c \
 	pack.c privsep.c delta.c fileindex.c worktree.c inflate.c \
-	repository_test.c
+	pathset.c repository_test.c
 
 CPPFLAGS = -I${.CURDIR}/../../include -I${.CURDIR}/../../lib \
 	-DGOT_LIBEXECDIR=${GOT_LIBEXECDIR}
diff --git a/regress/worktree/Makefile b/regress/worktree/Makefile
index 967be5e..c7e2786 100644
--- a/regress/worktree/Makefile
+++ b/regress/worktree/Makefile
@@ -2,7 +2,7 @@
 
 PROG = worktree_test
 SRCS = worktree.c repository.c object.c object_cache.c object_idset.c \
-	object_parse.c opentemp.c path.c error.c reference.c sha1.c \
+	object_parse.c opentemp.c path.c pathset.c error.c reference.c sha1.c \
 	pack.c privsep.c delta.c inflate.c fileindex.c worktree_test.c
 
 CPPFLAGS = -I${.CURDIR}/../../include -I${.CURDIR}/../../lib \
diff --git a/tog/Makefile b/tog/Makefile
index 72f8d6d..fb52772 100644
--- a/tog/Makefile
+++ b/tog/Makefile
@@ -3,8 +3,8 @@
 PROG=		tog
 SRCS=		tog.c blame.c commit_graph.c delta.c diff.c diffoffset.c \
 		diffreg.c error.c fileindex.c object.c object_cache.c \
-		object_idset.c object_parse.c opentemp.c path.c pack.c \
-		privsep.c reference.c repository.c sha1.c worktree.c \
+		object_idset.c object_parse.c opentemp.c path.c pathset.c \
+		pack.c privsep.c reference.c repository.c sha1.c worktree.c \
 		utf8.c inflate.c
 
 CPPFLAGS = -I${.CURDIR}/../include -I${.CURDIR}/../lib \