[2/5] path.c: clarify trie_find()'s in-code comment

Commit Message

SZEDER Gábor Oct. 21, 2019, 4 p.m. UTC

A fairly long comment describes trie_find()'s behavior and shows
examples, but it's slightly incomplete/inaccurate.  Update this
comment to specify how trie_find() handles a negative return value
from the given match function.

Furthermore, update the list of examples to include not only two but
three levels of path components.  This makes the examples slightly
more complicated, but it can illustrate the behavior in more corner
cases.

Finally, basically everything refers to the data stored for a key as
"value", with two confusing exceptions:

  - The type definition of the match function calls its corresponding
    parameter 'data'.
    Rename that parameter to 'value'.  (check_common(), the only
    function of this type already calls it 'value').

  - The table of examples above trie_find() has a "val from node"
    column, which has nothing to do with the value stored in the trie:
    it's a "prefix of the key for which the trie contains a value"
    that led to that node.
    Rename that column header to "prefix to node".

Note that neither the original nor the updated description and
examples correspond 100% to the current implementation, because the
implementation is a bit buggy, but the comment describes the desired
behavior.  The bug will be fixed in the last patch of this series.

Signed-off-by: SZEDER Gábor <[e-mail]>
---
 path.c | 45 ++++++++++++++++++++++++++++-----------------
 1 file changed, 28 insertions(+), 17 deletions(-)

Patch

diff --git a/path.c b/path.c
index e3da1f3c4e..4ac9a101f5 100644
--- a/path.c
+++ b/path.c
@@ -236,30 +236,41 @@  static void *add_to_trie(struct trie *root, const char *key, void *value)
 	return old;
 }
 
-typedef int (*match_fn)(const char *unmatched, void *data, void *baton);
+typedef int (*match_fn)(const char *unmatched, void *value, void *baton);
 
 /*
  * Search a trie for some key.  Find the longest /-or-\0-terminated
- * prefix of the key for which the trie contains a value.  Call fn
- * with the unmatched portion of the key and the found value, and
- * return its return value.  If there is no such prefix, return -1.
+ * prefix of the key for which the trie contains a value.  If there is
+ * no such prefix, return -1.  Otherwise call fn with the unmatched
+ * portion of the key and the found value.  If fn returns 0 or
+ * positive, then return its return value.  If fn returns negative,
+ * then call fn with the next-longest /-terminated prefix of the key
+ * (i.e. a parent directory) for which the trie contains a value, and
+ * handle its return value the same way.  If there is no shorter
+ * /-terminated prefix with a value left, then return the negative
+ * return value of the most recent fn invocation.
  *
  * The key is partially normalized: consecutive slashes are skipped.
  *
- * For example, consider the trie containing only [refs,
- * refs/worktree] (both with values).
- *
- * | key             | unmatched  | val from node | return value |
- * |-----------------|------------|---------------|--------------|
- * | a               | not called | n/a           | -1           |
- * | refs            | \0         | refs          | as per fn    |
- * | refs/           | /          | refs          | as per fn    |
- * | refs/w          | /w         | refs          | as per fn    |
- * | refs/worktree   | \0         | refs/worktree | as per fn    |
- * | refs/worktree/  | /          | refs/worktree | as per fn    |
- * | refs/worktree/a | /a         | refs/worktree | as per fn    |
- * |-----------------|------------|---------------|--------------|
+ * For example, consider the trie containing only [logs,
+ * logs/refs/bisect], both with values, but not logs/refs.
  *
+ * | key                | unmatched      | prefix to node   | return value |
+ * |--------------------|----------------|------------------|--------------|
+ * | a                  | not called     | n/a              | -1           |
+ * | logstore           | not called     | n/a              | -1           |
+ * | logs               | \0             | logs             | as per fn    |
+ * | logs/              | /              | logs             | as per fn    |
+ * | logs/refs          | /refs          | logs             | as per fn    |
+ * | logs/refs/         | /refs/         | logs             | as per fn    |
+ * | logs/refs/b        | /refs/b        | logs             | as per fn    |
+ * | logs/refs/bisected | /refs/bisected | logs             | as per fn    |
+ * | logs/refs/bisect   | \0             | logs/refs/bisect | as per fn    |
+ * | logs/refs/bisect/  | /              | logs/refs/bisect | as per fn    |
+ * | logs/refs/bisect/a | /a             | logs/refs/bisect | as per fn    |
+ * | (If fn in the previous line returns -1, then fn is called once more:) |
+ * | logs/refs/bisect/a | /refs/bisect/a | logs             | as per fn    |
+ * |--------------------|----------------|------------------|--------------|
  */
 static int trie_find(struct trie *root, const char *key, match_fn fn,
 		     void *baton)