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

From: Derrick Stolee <stolee@gmail.com>
Date: Apr 1, 2020, 13:57 UTC
Message-ID: <977213ee-3d5f-150a-2982-e1083557bce3@gmail.com>
In-Reply-To: <b2caa426790a2cd6a510e5ebf2d182b018f12185.1585714667.git.gitgitgadget@gmail.com>

On 4/1/2020 12:17 AM, Elijah Newren via GitGitGadget wrote:

Show 25 quoted lines

> @@ -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:

Show 8 quoted lines

> +	 */
> +	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.

Thanks, -Stolee