regedit: add search feature.

Open up a search input with '/'. 'x' key gets the next
result.

This patch also ensures that keys are always sorted, so
that the search order matches the order the keys appear
on screen.

TODO:
	+ flesh out search interface
	+ find previous
	+ search values

Signed-off-by: Chris Davis <cd.rattan@gmail.com>
Reviewed-by: Andreas Schneider <asn@samba.org>
Reviewed-by: Michael Adam <obnox@samba.org>

6 files changed, 280 insertions, 39 deletions

diff --git a/source3/utils/regedit.c b/source3/utils/regedit.c
index a69fa6b65f..77c254bfd0 100644
--- a/source3/utils/regedit.c
+++ b/source3/utils/regedit.c
@@ -60,6 +60,7 @@ struct regedit {
 	struct value_list *vl;
 	struct tree_view *keys;
 	bool tree_input;
+	struct regedit_search_opts active_search;
 };
 
 static struct regedit *regedit_main = NULL;
@@ -141,8 +142,9 @@ static void print_help(struct regedit *regedit)
 			    "[b] Edit binary";
 	const char *msg = "KEYS";
 	const char *help = khelp;
-	const char *genhelp = "[TAB] Switch sections [q] Quit regedit "
-			      "[UP] List up [DOWN] List down";
+	const char *genhelp = "[TAB] Switch sections [q] Quit "
+			      "[UP] List up [DOWN] List down "
+			      "[/] Search [x] Next";
 	int i, pad;
 
 	if (!regedit->tree_input) {
@@ -185,7 +187,7 @@ static void load_values(struct regedit *regedit)
 {
 	struct tree_node *node;
 
-	node = item_userptr(current_item(regedit->keys->menu));
+	node = tree_view_get_current_node(regedit->keys);
 	value_list_load(regedit->vl, node->key);
 }
 
@@ -229,7 +231,7 @@ static void add_reg_key(struct regedit *regedit, struct tree_node *node,
 				new_node = tree_node_new(parent, parent,
 							 name, new_key);
 				SMB_ASSERT(new_node);
-				tree_node_append_last(list, new_node);
+				tree_node_insert_sorted(list, new_node);
 			}
 
 			list = tree_node_first(node);
@@ -243,6 +245,106 @@ static void add_reg_key(struct regedit *regedit, struct tree_node *node,
 	}
 }
 
+static WERROR next_depth_first(struct tree_node **node)
+{
+	WERROR rv = WERR_OK;
+
+	SMB_ASSERT(node != NULL && *node != NULL);
+
+	if (tree_node_has_children(*node)) {
+		/* 1. If the node has children, go to the first one. */
+		rv = tree_node_load_children(*node);
+		if (W_ERROR_IS_OK(rv)) {
+			SMB_ASSERT((*node)->child_head != NULL);
+			*node = (*node)->child_head;
+		}
+	} else if ((*node)->next) {
+		/* 2. If there's a node directly after this one, go there */
+		*node = (*node)->next;
+	} else {
+		/* 3. Otherwise, go up the hierarchy to find the next one */
+		do {
+			*node = (*node)->parent;
+			if (*node && (*node)->next) {
+				*node = (*node)->next;
+				break;
+			}
+		} while (*node);
+	}
+
+	return rv;
+}
+
+static WERROR regedit_search_next(struct regedit *regedit)
+{
+	WERROR rv;
+	struct regedit_search_opts *opts = &regedit->active_search;
+
+	if (opts->search_recursive) {
+		rv = next_depth_first(&opts->node);
+		if (!W_ERROR_IS_OK(rv)) {
+			return rv;
+		}
+	} else {
+		opts->node = opts->node->next;
+	}
+
+	return WERR_OK;
+}
+
+static WERROR regedit_search(struct regedit *regedit)
+{
+	struct regedit_search_opts *opts;
+	struct tree_node *found;
+	WERROR rv;
+
+	opts = &regedit->active_search;
+
+	if (!opts->query || !opts->match) {
+		return WERR_OK;
+	}
+
+	SMB_ASSERT(opts->search_key || opts->search_value);
+
+	for (found = NULL; opts->node && !found; ) {
+		if (opts->search_key &&
+		    opts->match(opts->node->name, opts->query)) {
+			found = opts->node;
+		}
+		if (opts->search_value) {
+			/* TODO
+			rv = regedit_search_value(regedit);
+			if (W_ERROR_IS_OK(rv)) {
+				found = opts->node;
+			} else if (!W_ERROR_EQUAL(rv, WERR_NO_MORE_ITEMS)) {
+				return rv;
+			}
+			*/
+		}
+		rv = regedit_search_next(regedit);
+		if (!W_ERROR_IS_OK(rv)) {
+			return rv;
+		}
+	}
+
+	if (found) {
+		/* Put the cursor on the node that was found */
+		if (!tree_view_is_node_visible(regedit->keys, found)) {
+			tree_view_update(regedit->keys,
+					 tree_node_first(found));
+			print_path(regedit, found);
+		}
+		tree_view_set_current_node(regedit->keys, found);
+		load_values(regedit);
+		tree_view_show(regedit->keys);
+		value_list_show(regedit->vl);
+	} else {
+		beep();
+	}
+
+	return WERR_OK;
+}
+
 static void handle_tree_input(struct regedit *regedit, int c)
 {
 	struct tree_node *node;
@@ -394,9 +496,49 @@ static void handle_value_input(struct regedit *regedit, int c)
 	value_list_show(regedit->vl);
 }
 
+static bool find_substring(const char *haystack, const char *needle)
+{
+	return strstr(haystack, needle) != NULL;
+}
+
+static bool find_substring_nocase(const char *haystack, const char *needle)
+{
+	return strcasestr(haystack, needle) != NULL;
+}
+
 static void handle_main_input(struct regedit *regedit, int c)
 {
 	switch (c) {
+	case 'f':
+	case 'F':
+	case '/': {
+		int rv;
+		struct regedit_search_opts *opts;
+
+		opts = &regedit->active_search;
+		if (opts->query) {
+			talloc_free(discard_const(opts->query));
+		}
+		rv = dialog_search_input(regedit, opts);
+		if (rv == DIALOG_OK) {
+			SMB_ASSERT(opts->query != NULL);
+			opts->match = find_substring;
+			opts->node = regedit->keys->root;
+			if (opts->search_nocase) {
+				opts->match = find_substring_nocase;
+			}
+			if (opts->search_relative) {
+				opts->node =
+				     tree_view_get_current_node(regedit->keys);
+			}
+			regedit_search(regedit);
+		}
+		break;
+	}
+	case 'x':
+	case 'X':
+		regedit_search(regedit);
+		break;
 	case '\t':
 		regedit->tree_input = !regedit->tree_input;
 		print_heading(regedit);
diff --git a/source3/utils/regedit.h b/source3/utils/regedit.h
index 2ab40f9d69..113f226ec6 100644
--- a/source3/utils/regedit.h
+++ b/source3/utils/regedit.h
@@ -59,4 +59,17 @@ WERROR reg_open_samba3(TALLOC_CTX *mem_ctx, struct registry_context **ctx);
 
 int regedit_getch(void);
 
+typedef bool (*regedit_search_match_fn_t)(const char *, const char *);
+
+struct regedit_search_opts {
+	const char *query;
+	regedit_search_match_fn_t match;
+	struct tree_node *node;
+	unsigned int search_key:1;
+	unsigned int search_value:1;
+	unsigned int search_recursive:1;
+	unsigned int search_relative:1;
+	unsigned int search_nocase:1;
+};
+
 #endif
diff --git a/source3/utils/regedit_dialog.c b/source3/utils/regedit_dialog.c
index c3dd19899b..944fcc8aea 100644
--- a/source3/utils/regedit_dialog.c
+++ b/source3/utils/regedit_dialog.c
@@ -1207,3 +1207,17 @@ finish:
 
 	return sel;
 }
+
+int dialog_search_input(TALLOC_CTX *ctx, struct regedit_search_opts *opts)
+{
+	int rv;
+	// TODO
+
+	opts->search_key = 1;
+	opts->search_recursive = 1;
+	opts->search_nocase = 1;
+
+	rv = dialog_input(ctx, &opts->query, "Search", "Query");
+
+	return rv;
+}
diff --git a/source3/utils/regedit_dialog.h b/source3/utils/regedit_dialog.h
index 0a0aec87b8..f57bcd1a6f 100644
--- a/source3/utils/regedit_dialog.h
+++ b/source3/utils/regedit_dialog.h
@@ -73,4 +73,8 @@ WERROR dialog_edit_value(TALLOC_CTX *ctx, struct registry_key *key,
 
 int dialog_select_type(TALLOC_CTX *ctx, int *type);
 
+struct regedit_search_opts;
+
+int dialog_search_input(TALLOC_CTX *ctx, struct regedit_search_opts *opts);
+
 #endif
diff --git a/source3/utils/regedit_treeview.c b/source3/utils/regedit_treeview.c
index cfcf5f2500..ef8575414d 100644
--- a/source3/utils/regedit_treeview.c
+++ b/source3/utils/regedit_treeview.c
@@ -117,7 +117,7 @@ struct tree_node *tree_node_last(struct tree_node *list)
 	return list;
 }
 
-bool tree_node_has_children(struct tree_node *node)
+static uint32_t get_num_subkeys(struct tree_node *node)
 {
 	const char *classname;
 	uint32_t num_subkeys;
@@ -128,20 +128,49 @@ bool tree_node_has_children(struct tree_node *node)
 	uint32_t max_valbufsize;
 	WERROR rv;
 
-	if (node->child_head) {
-		return true;
-	}
-
 	rv = reg_key_get_info(node, node->key, &classname, &num_subkeys,
 			      &num_values, &last_change_time,
 			      &max_subkeynamelen, &max_valnamelen,
 			      &max_valbufsize);
 
 	if (W_ERROR_IS_OK(rv)) {
-		return num_subkeys != 0;
+		return num_subkeys;
+	}
+
+	return 0;
+}
+
+bool tree_node_has_children(struct tree_node *node)
+{
+	if (node->child_head) {
+		return true;
 	}
 
-	return false;
+	return get_num_subkeys(node) > 0;
+}
+
+static int node_cmp(struct tree_node **a, struct tree_node **b)
+{
+	return strcmp((*a)->name, (*b)->name);
+}
+
+void tree_node_insert_sorted(struct tree_node *list, struct tree_node *node)
+{
+	list = tree_node_first(list);
+
+	if (node_cmp(&list, &node) >= 0) {
+		tree_node_append(node, list);
+		if (list->parent) {
+			list->parent->child_head = node;
+		}
+		return;
+	}
+
+	while (list->next && node_cmp(&list->next, &node) < 0) {
+		list = list->next;
+	}
+
+	tree_node_append(list, node);
 }
 
 WERROR tree_node_load_children(struct tree_node *node)
@@ -149,43 +178,63 @@ WERROR tree_node_load_children(struct tree_node *node)
 	struct registry_key *key;
 	const char *key_name, *klass;
 	NTTIME modified;
-	uint32_t i;
+	uint32_t i, nsubkeys;
 	WERROR rv;
-	struct tree_node *new_node, *prev;
+	struct tree_node *prev, **array;
 
 	/* does this node already have it's children loaded? */
 	if (node->child_head)
 		return WERR_OK;
 
-	for (prev = NULL, i = 0; ; ++i) {
+	nsubkeys = get_num_subkeys(node);
+	if (nsubkeys == 0)
+		return WERR_OK;
+
+	array = talloc_zero_array(node, struct tree_node *, nsubkeys);
+	if (array == NULL) {
+		return WERR_NOMEM;
+	}
+
+	for (i = 0; i < nsubkeys; ++i) {
 		rv = reg_key_get_subkey_by_index(node, node->key, i,
 						 &key_name, &klass,
 						 &modified);
 		if (!W_ERROR_IS_OK(rv)) {
-			if (W_ERROR_EQUAL(rv, WERR_NO_MORE_ITEMS)) {
-				break;
-			}
-
-			return rv;
+			goto finish;
 		}
 
 		rv = reg_open_key(node, node->key, key_name, &key);
 		if (!W_ERROR_IS_OK(rv)) {
-			return rv;
+			goto finish;
 		}
 
-		new_node = tree_node_new(node, node, key_name, key);
-		if (new_node == NULL) {
-			return WERR_NOMEM;
+		array[i] = tree_node_new(node, node, key_name, key);
+		if (array[i] == NULL) {
+			rv = WERR_NOMEM;
+			goto finish;
 		}
+	}
+
+	TYPESAFE_QSORT(array, nsubkeys, node_cmp);
+
+	for (i = 1, prev = array[0]; i < nsubkeys; ++i) {
+		tree_node_append(prev, array[i]);
+		prev = array[i];
+	}
+	node->child_head = array[0];
+
+	rv = WERR_OK;
 
-		if (prev) {
-			tree_node_append(prev, new_node);
+finish:
+	if (!W_ERROR_IS_OK(rv)) {
+		for (i = 0; i < nsubkeys; ++i) {
+			talloc_free(array[i]);
 		}
-		prev = new_node;
+		node->child_head = NULL;
 	}
+	talloc_free(array);
 
-	return WERR_OK;
+	return rv;
 }
 
 void tree_node_free_recursive(struct tree_node *list)
@@ -236,16 +285,6 @@ void tree_view_clear(struct tree_view *view)
 	view->current_items = NULL;
 }
 
-static int item_comp(ITEM **a, ITEM **b)
-{
-	struct tree_node *nodea, *nodeb;
-
-	nodea = item_userptr(*a);
-	nodeb = item_userptr(*b);
-
-	return strcmp(nodea->name, nodeb->name);
-}
-
 WERROR tree_view_update(struct tree_view *view, struct tree_node *list)
 {
 	ITEM **items;
@@ -283,8 +322,6 @@ WERROR tree_view_update(struct tree_view *view, struct tree_node *list)
 		set_item_userptr(items[i], node);
 	}
 
-	TYPESAFE_QSORT(items, n_items, item_comp);
-
 	unpost_menu(view->menu);
 	set_menu_items(view->menu, items);
 	tree_view_free_current_items(view->current_items);
@@ -298,6 +335,33 @@ fail:
 	return WERR_NOMEM;
 }
 
+/* is this node in the current level? */
+bool tree_view_is_node_visible(struct tree_view *view, struct tree_node *node)
+{
+	struct tree_node *first;
+
+	first = item_userptr(view->current_items[0]);
+
+	return first->parent == node->parent;
+}
+
+void tree_view_set_current_node(struct tree_view *view, struct tree_node *node)
+{
+	ITEM **it;
+
+	for (it = view->current_items; *it; ++it) {
+		if (item_userptr(*it) == node) {
+			set_current_item(view->menu, *it);
+			return;
+		}
+	}
+}
+
+struct tree_node *tree_view_get_current_node(struct tree_view *view)
+{
+	return item_userptr(current_item(view->menu));
+}
+
 void tree_view_set_selected(struct tree_view *view, bool select)
 {
 	attr_t attr = A_NORMAL;
diff --git a/source3/utils/regedit_treeview.h b/source3/utils/regedit_treeview.h
index 66e692eb0f..152ba3c3b6 100644
--- a/source3/utils/regedit_treeview.h
+++ b/source3/utils/regedit_treeview.h
@@ -70,5 +70,9 @@ void tree_view_clear(struct tree_view *view);
 WERROR tree_view_update(struct tree_view *view, struct tree_node *list);
 bool tree_node_has_children(struct tree_node *node);
 WERROR tree_node_load_children(struct tree_node *node);
+void tree_node_insert_sorted(struct tree_node *list, struct tree_node *node);
+bool tree_view_is_node_visible(struct tree_view *view, struct tree_node *node);
+void tree_view_set_current_node(struct tree_view *view, struct tree_node *node);
+struct tree_node *tree_view_get_current_node(struct tree_view *view);
 
 #endif