Re: [PATCH v5 08/12] dir: replace exponential algorithm with a linear one

[Elijah Newren <newren@gmail.com>]

On Wed, Apr 1, 2020 at 6:57 AM Derrick Stolee <stolee@gmail.com> wrote:
>
> On 4/1/2020 12:17 AM, Elijah Newren via GitGitGadget wrote:
> > @@ -1659,7 +1659,13 @@ static enum path_treatment treat_directory(struct dir_struct *dir,
> >       const char *dirname, int len, int baselen, int excluded,
> >       const struct pathspec *pathspec)
> >  {
> > -     int nested_repo = 0;
> > +     /*
> > +      * WARNING: From this function, you can return path_recurse or you
> > +      *          can call read_directory_recursive() (or neither), but
> > +      *          you CAN'T DO BOTH.
> > +      */
> > +     enum path_treatment state;
> > +     int nested_repo = 0, old_ignored_nr, check_only, stop_early;
> >       /* The "len-1" is to strip the final '/' */
> >       enum exist_status status = directory_exists_in_index(istate, dirname, len-1);
> >
> > @@ -1711,18 +1717,135 @@ static enum path_treatment treat_directory(struct dir_struct *dir,
> >
> >       /* This is the "show_other_directories" case */
> >
> > -     if (!(dir->flags & DIR_HIDE_EMPTY_DIRECTORIES))
> > +     /*
> > +      * If we have a pathspec which could match something _below_ this
> > +      * directory (e.g. when checking 'subdir/' having a pathspec like
> > +      * 'subdir/some/deep/path/file' or 'subdir/widget-*.c'), then we
> > +      * need to recurse.
>
> I was extremely skeptical about this approach due to leading wildcards
> like "*.c" or "sub*/*.h" but found this comment inside math_pathspec_item():
>
>                 /*
>                  * Here is where we would perform a wildmatch to check if
>                  * "name" can be matched as a directory (or a prefix) against
>                  * the pathspec.  Since wildmatch doesn't have this capability
>                  * at the present we have to punt and say that it is a match,
>                  * potentially returning a false positive
>                  * The submodules themselves will be able to perform more
>                  * accurate matching to determine if the pathspec matches.
>                  */
>                 return MATCHED_RECURSIVELY_LEADING_PATHSPEC;
>
> So it looks like it will return MATCHED_RECURSIVELY_LEADING_PATHSPEC as
> expected by this block below:
>
> > +      */
> > +     if (pathspec) {
> > +             int ret = do_match_pathspec(istate, pathspec, dirname, len,
> > +                                         0 /* prefix */, NULL /* seen */,
> > +                                         DO_MATCH_LEADING_PATHSPEC);
> > +             if (ret == MATCHED_RECURSIVELY_LEADING_PATHSPEC)
> > +                     return path_recurse;
> > +     }
>
> I can't say that I fully understand the change to this patch yet, but at
> least my initial "THAT CAN'T POSSIBLY WORK!" reaction has been tempered.

I don't know if it helps you feel better about this block or not, but
it existed (in just slightly modified form) in dir.c before patch 7; I
just missed it when I was restructuring and thus didn't have it in my
first four rounds of this series.  (Funnily enough, I was the one who
added this LEADING_PATHSPEC logic to dir.c a while back, and you'd
think if I was going to overlook some code when I was restructuring,
that it surely couldn't be bits that I had added myself.)  So, that
basically means that dir.c has been relying on this logic for some
time, and I just needed to make sure to include it in this
restructuring.

Elijah