ingydotnet/git-subrepo — pull request #25 by AndrewSmart (2014-11-04 00:15:21+00:00)
Title: Fixes the ./test/failing/test.sh failing test case I gave you [improved].

I solve this problem by finding a better common ancestor before merging. This common-ancestor search is necessary as otherwise the *git merge* command with the $subrepo_parent obtained from the .gitrepo file would fail. I believe this is because the merge command internally calls `git-merge-base`, which isn't sophisticated enough to find the best common-ancestor in this context (due to one branch having the .gitrepo file and the other not). We must do this search manually by comparing the trees without the presence of the .gitrepo file.

Previously I had solved the problem by ***caching*** when the latest *git subrepo push* command was, and used that point as the common-ancestor during the merge (in the *git subrepo pull* command).
* But that solution wasn't acceptable as the cache only stayed in the local repo- causing problems for other developers as they wouldn't recieve this cache.

Now I have solved the problem by ***searching*** for where the lastest *git subrepo push* command was done, and using that point as the common-ancestor during the merge (in the *git subrepo pull* command).
* In doing the search it was necessary to checkout the subrepo/$subdir branch in the subrepo pull command.
* This search has **M*N** complexity (two loops).
* **M** (outer loop) is # of commits since last subrepo clone/pull in ***subrepo branch***.
* Essentially iterates over the output of `git rev-list subrepo/$subdir --format="format:%T"`, and stopping once the tree pertaining to the last subrepo clone/pull command is reached.
* **N** (inner loop) is # of commits since last subrepo clone/pull in ***original branch***.
* Iterates over `git rev-list "$subrepo_parent".."$original_head_branch" -- "$subdir"`, which is the list of commits which modified the subrepo since the last subrepo clone/pull.
* A further optimization within this loop can be made by caching the output of `git mktree < <(git ls-tree "$i:$subdir" | sed -r '/^.*\.gitrepo.*$/d')`.
* This logic was placed into the get-best-common-ancestor-for-merge() function.