Optimize RevWalk.getMergedInto()
Transitive Relation Definition:
On the DAG of commit history, if A can reach B, C can reach A, then C
can reach B.
Example:
As is shown in the graph below:
1 - 2 - 3 - 4 (side)
\
5 - 6^ (master) - 7 (topic)
Find out which branches is 2 merged into:
After we calculated that master contains 2, we can mark 6 as TEMP_MARK
to avoid unwanted walks.
When we want to figure out if 2 is merge into the topic, the traversal
path would be [7, 6] instead of [7, 6, 5, 3, 2].
Test:
This change can significantly improve performance for tags.
On a copy of the Linux repository, the command 'git tag --contains
<commit>' had the following performance improvement:
commit | Before | After | Rel %
47a44d27ca | 29251ms | 6687ms | -77%
90327e7dff | 21388ms | 6256ms | -70%
f85fac0efa | 11150ms | 7338ms | -34%
The current version ignores tags, even though the tag is a type of
the ref.
Follow-up commits I'll fix it.
Change-Id: Ie6295ca4d16070499912af462239e679a97cce47
Signed-off-by: kylezhao <kylezhao@tencent.com>
Reviewed-by: Christian Halstrick <christian.halstrick@sap.com>
Reviewed-by: Martin Fick <mfick@codeaurora.org>