Moving fb extensions to core.

[Durham Goode]

On 7/6/17 8:10 AM, Yuya Nishihara wrote:
> On Wed, 5 Jul 2017 11:24:59 -0700, Durham Goode wrote:
>> On 7/5/17 11:13 AM, Pulkit Goyal wrote:
>>> copytrace: This patch speeds up the copy tracing by a file based
>>> heuristics. I am not sure about the way to go with this.
>>
>> I'd put this in core and behind a config flag.  Just like we have
>> aggressive merge deltas behind a config flag, this is an optimization
>> that is useful for some, is awkward to do via an extension, and could
>> end up replacing the current copy tracing logic in the future if we
>> iterate on it enough.
>
> Sounds good, though I don't know the implementation details. Given how
> expensive the current copy tracing is, fast-but-inaccurate one should be
> a good option for large repos.

To give a quick overview of the implementation:

Normal copy tracing looks at all files in the destination that don't 
exist in the source, and traces their history back to the common 
ancestor to see if they match up with a file changed in the source. This 
is expensive because it is O(files changed between common ancestor and 
destination).

The heuristic limits the search to just files that are either A) in the 
same directory as a file in the source (i.e. a rename), or B) have the 
same name as a file in the source (i.e. a move to a different 
directory). This limits the search space dramatically. Credit to Ryan 
and Stas for the idea.