Re: [PATCH 1/6] path-walk: introduce an object walk by path

> "Derrick Stolee via GitGitGadget" <gitgitgadget@gmail.com> writes:
>
>> From: Derrick Stolee <stolee@gmail.com>
>>
>> In anticipation of a few planned applications, introduce the most basic form
>> of a path-walk API. It currently assumes that there are no UNINTERESTING
>> objects, and does not include any complicated filters. It calls a function
>> pointer on groups of tree and blob objects as grouped by path. This only
>> includes objects the first time they are discovered, so an object that
>> appears at multiple paths will not be included in two batches.
>>
>> These batches are collected in 'struct type_and_oid_list' objects, which
>> store an object type and an oid_array of objects.
>>
>> The data structures are documented in 'struct path_walk_context', but in
>> summary the most important are:
>>
>>   * 'paths_to_lists' is a strmap that connects a path to a
>>     type_and_oid_list for that path. To avoid conflicts in path names,
>>     we make sure that tree paths end in "/" (except the root path with
>>     is an empty string) and blob paths do not end in "/".
>>
>>   * 'path_stack' is a string list that is added to in an append-only
>>     way. This stores the stack of our depth-first search on the heap
>>     instead of using recursion.
>>
>>   * 'path_stack_pushed' is a strmap that stores path names that were
>>     already added to 'path_stack', to avoid repeating paths in the
>>     stack. Mostly, this saves us from quadratic lookups from doing
>>     unsorted checks into the string_list.
>>
>> The coupling of 'path_stack' and 'path_stack_pushed' is protected by the
>> push_to_stack() method. Call this instead of inserting into these
>> structures directly.
>>
>> The walk_objects_by_path() method initializes these structures and
>> starts walking commits from the given rev_info struct. The commits are
>> used to find the list of root trees which populate the start of our
>> depth-first search.
>
> Isn't this more of breadth-first search? Reading through the code, the
> algorithm seems something like:
>
> - For each commit in list of commits (from rev_info)
>   - Tackle each root tree, add root path to the stack.
> - For each path in stack left
>   - Call the callback provided by client.
>   - Find all its first level children, add each to the stack.
>
> So wouldn't this go through the tree in level by level basis? Making it
> a BFS?

>
> Apart from this, the patch itself looks solid. I ended up writing a
> small client to play with this API, and was very pleased how quickly I
> could get it running.
>
> [snip]