Re: [PATCH v2 2/2] grep: use '/' delimiter for paths

From: Jeff King <peff@peff.net>
Date: Feb 9, 2017, 03:58 UTC
Message-ID: <20170209035839.wqsh6ibgnmxyjusi@sigill.intra.peff.net>
In-Reply-To: <xmqq8tphzr41.fsf@gitster.mtv.corp.google.com>

On Tue, Feb 07, 2017 at 12:24:30PM -0800, Junio C Hamano wrote:

Show 11 quoted lines

> Having said that, I actually think "make it more convenient" without
> making anything incorrect would be to teach the revision parser to
> understand
> 
>     <any-expression-to-name-a-tree-ish:<path>
> 
> as an extended SHA-1 expression to name the blob or the tree at that
> path in the tree-ish, e.g. if we can make the revision parser to
> take this
> 
>     master:Documentation:git.txt

So here I was wondering what happens when you have a filename with a colon in it, but then...

Show 7 quoted lines

> to be able to show the same thing as well.  You'd need to backtrack
> the parsing (e.g. attempt to find "Documentation:git.txt" in
> "master", fail to find any, then fall back to find "git.txt" in
> "master:Documentation", find one, and be happy, or something like
> that), and define how to resolve potential ambiguity (e.g. there may
> indeed be "Documentation:git.txt" and "Documentation/git.txt" in the
> tree-ish "master"), though.

...you obviously did think of that. Backtracking sounds pretty nasty, though. What's the time complexity of parsing:

  master:a:a:a:a:a:a:a:a:a:a:a

I think there are 2^(n-1) possible paths (each colon can be a real colon or a slash). Though I guess if you walk the trees as you go, you only have to examine at most "n" paths to find the first-level tree, and then at most "n-1" paths at the second level, and so on.

Unless you really do have ambiguous trees, in which case you have to walk down multiple paths.

It certainly would not be the first combinatoric explosion you can convince Git to perform. But it does seem like a lot of complication for something as simple as path lookups.

-Peff