Re: [PATCH 01/10] list_lookup: create case and length search

Junio C Hamano <gitster@pobox.com> writes:

In the above, I mixed up which string is a prefix of which, but the overall comment still stands, I think.

Your mailmap string list has "Ee@eee" (email part only) stored, while the record from author/committer line has "NNNN <EE@EEE> TTTTTT sZZZZ", to hold name, timestamp and zone. You have a pointer email pointing at the first "E" in that record, with maillen set to 6, and see if the mailmap contains a string that match "EE@EEE". So I mixed up the prefix-ness of these strings.

Let's address the case sensitivety first. The string_list_lookup() and your string_list_lookup_extended() functions both work on a string list that is built by add_mapping() function that asks string_list_find_insert_index() to find an insertion point in the sorted string list. If this is not done using the same case insensitive manner for a string list that is meant to be queried case insensitively, the resulting list is still sorted case sensitively, and look-up functions that work by binary search won't find what you are looking for when they try to find the string using case-insensitive comparison. The change to implement it would probably look like the attached patch.

Assuming that we can leave the case sensitivity behind us that way, we still would need a new helper function

    string_list_lookup_prefix(struct string_list *, const char*, size_t)

so that you can find an existing "Ee@eee" entry in the string list by email that points at "EE@EEE> TTTTTT sZZZZ" with maillen of 6.

I am wondering if we can do that without adding the length-limited sort in the low-level get_entry_index() to do so, though.

You could first ask string_list_find_insert_index() to locate the insertion point for "EE@EEE> TTTTTT sZZZZ". That has to come after "Ee@eee" if it exists (or it could be "De@eee" in which case you know there is no match).

 1. Ask string_list_find_insert_index() to locate "EE@EEE> TTTTTT..."

    a. If it says there is an exact match, then that did not match
       "EE@EEE" list (you found "EE@EEE> TTTTTT sZZZZ").  You might
       still find "EE@EEE" before that record, though.  Also your
       key may have been "EE@EEE" exactly, in which case you already
       found what you were looking for.

    b. If it says there is not an exact match, the returned value is
       pointing at a record that comes after "EE@EEE> TTTTTT sZZZZ" if
       you were to insert it, which definitely is after "EE@EEE".

    So in either case, you know what you are looking for must come
    before string_list_find_insert_index() gave you.  Let's call
    that position "i".

    You still need to be careful that there could be an existing
    entry whose key is "EE@EEE" followed by a byte that sorts before
    ">" or " " (we do not want to limit this new generic string-list
    function to operate only on e-mail addresses), though.  So the
    above "must come before" is not "must come immediately before".

 2. Then compare map->items[i].string and email using strncasecmp()
    for maillen bytes, and make sure map->items[].string is exactly
    maillen bytes long.  If it matches, you found what you were
    looking for.  Otherwise, decrement "i" (e.g. the overlong key
    string you had was "EE@EEE> TTTTTT..." and the record at one
    before the insertion point was "EE@EEE\t" which sorts before it,
    but the string-list may have "EE@EEE" before that entry), see if
    the first maillen bytes still match, and continue.  Once you
    decrement i enough, the first maillen bytes won't match
    (e.g. you hit "De@EEE"), or "i" goes negative, and you can stop.

or something like that. I'll cook up a patch and see how ugly it ends up with.

-- >8 --
Subject: [PATCH] string-list: allow case-insensitive string list

Signed-off-by: Junio C Hamano <gitster@pobox.com>
---

 * At the very beginning of mailmap.c::read_mailmap(), you would say
   something like:

	int read_mailmap(struct string_list *map, char **repo_ident)
        {
        	map->strdup_strings = 1;
       +        map->cmp = strcasecmp;
                /* each failure returns 1, so >1 means both calls ...

   to make the mailmap string list a case insensitive one.

 string-list.c | 17 +++++++++++++----
 string-list.h |  4 ++++
 2 files changed, 17 insertions(+), 4 deletions(-)