{"action":"created","issue":{"url":"https://api.github.com/repos/ingydotnet/git-subrepo/issues/130","repository_url":"https://api.github.com/repos/ingydotnet/git-subrepo","labels_url":"https://api.github.com/repos/ingydotnet/git-subrepo/issues/130/labels{/name}","comments_url":"https://api.github.com/repos/ingydotnet/git-subrepo/issues/130/comments","events_url":"https://api.github.com/repos/ingydotnet/git-subrepo/issues/130/events","html_url":"https://github.com/ingydotnet/git-subrepo/issues/130","id":129063210,"number":130,"title":"merge-base algorithm improvements ","user":{"login":"grimmySwe","id":6480514,"avatar_url":"https://avatars.githubusercontent.com/u/6480514?v=3","gravatar_id":"","url":"https://api.github.com/users/grimmySwe","html_url":"https://github.com/grimmySwe","followers_url":"https://api.github.com/users/grimmySwe/followers","following_url":"https://api.github.com/users/grimmySwe/following{/other_user}","gists_url":"https://api.github.com/users/grimmySwe/gists{/gist_id}","starred_url":"https://api.github.com/users/grimmySwe/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/grimmySwe/subscriptions","organizations_url":"https://api.github.com/users/grimmySwe/orgs","repos_url":"https://api.github.com/users/grimmySwe/repos","events_url":"https://api.github.com/users/grimmySwe/events{/privacy}","received_events_url":"https://api.github.com/users/grimmySwe/received_events","type":"User","site_admin":false},"labels":[{"url":"https://api.github.com/repos/ingydotnet/git-subrepo/labels/enhancement","name":"enhancement","color":"84b6eb"}],"state":"open","locked":false,"assignee":{"login":"grimmySwe","id":6480514,"avatar_url":"https://avatars.githubusercontent.com/u/6480514?v=3","gravatar_id":"","url":"https://api.github.com/users/grimmySwe","html_url":"https://github.com/grimmySwe","followers_url":"https://api.github.com/users/grimmySwe/followers","following_url":"https://api.github.com/users/grimmySwe/following{/other_user}","gists_url":"https://api.github.com/users/grimmySwe/gists{/gist_id}","starred_url":"https://api.github.com/users/grimmySwe/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/grimmySwe/subscriptions","organizations_url":"https://api.github.com/users/grimmySwe/orgs","repos_url":"https://api.github.com/users/grimmySwe/repos","events_url":"https://api.github.com/users/grimmySwe/events{/privacy}","received_events_url":"https://api.github.com/users/grimmySwe/received_events","type":"User","site_admin":false},"milestone":null,"comments":6,"created_at":"2016-01-27T07:50:01Z","updated_at":"2016-02-04T22:20:25Z","closed_at":null,"body":"Current implementation of the merge-base is a simple loop of loops. With a subrepo S and a local copy of that C:\r\nbest case: S+C (We always go through all commits at least once to detect duplicates)\r\nworst case: S*C + S+C (Find a match and also go through to find duplicates)\r\n\r\nAs C and S grows the time spent finding merge base will increase rapidly. You could though argue that the normal case should often be more like the best case because if you pull/push regularly you will find matches sooner.\r\n\r\nBut... worst case is having a common clone commit and then have a small change in you C that you never push.\r\n\r\nImplementation suggestion for the search:\r\nGo through C, store all commits in a set based on tree hash, in each entry store a list of C commits and a reference to the parent tree hash.\r\nGo through S, store all commits in the same set, in each entry store a list of S commits.\r\n\r\nFinal step is to start at the last tree hash and iterate through them by using the parent references to next tree hash:\r\nIf you find an entry with exactly one C commit and one S commit you have a unique spot that can be used as merge base.\r\nEntries with more then one C or S can't be used as they indicate that things have been reverted and we can't determine the actual order.\r\n\r\nNot sure how to do this in bash though :-)\r\n"},"comment":{"url":"https://api.github.com/repos/ingydotnet/git-subrepo/issues/comments/180076907","html_url":"https://github.com/ingydotnet/git-subrepo/issues/130#issuecomment-180076907","issue_url":"https://api.github.com/repos/ingydotnet/git-subrepo/issues/130","id":180076907,"user":{"login":"grimmySwe","id":6480514,"avatar_url":"https://avatars.githubusercontent.com/u/6480514?v=3","gravatar_id":"","url":"https://api.github.com/users/grimmySwe","html_url":"https://github.com/grimmySwe","followers_url":"https://api.github.com/users/grimmySwe/followers","following_url":"https://api.github.com/users/grimmySwe/following{/other_user}","gists_url":"https://api.github.com/users/grimmySwe/gists{/gist_id}","starred_url":"https://api.github.com/users/grimmySwe/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/grimmySwe/subscriptions","organizations_url":"https://api.github.com/users/grimmySwe/orgs","repos_url":"https://api.github.com/users/grimmySwe/repos","events_url":"https://api.github.com/users/grimmySwe/events{/privacy}","received_events_url":"https://api.github.com/users/grimmySwe/received_events","type":"User","site_admin":false},"created_at":"2016-02-04T22:20:25Z","updated_at":"2016-02-04T22:20:25Z","body":"I am testing a little hack variant:\r\n\r\n```\r\n#!/bin/bash\r\n\r\ngit:log-tree() {\r\n    git log --pretty=format:%H:%T \"$1\"\r\n}\r\n\r\nprepare() {\r\n    local prefix=\"$1\";\r\n    local data=$(git:log-tree \"$2\");\r\n\r\n    for entry in $data; do\r\n        local array=(${entry//:/ })\r\n        local commit=${array[0]}\r\n        local tree=${array[1]}\r\n\r\n        local key=\"${prefix}_$tree\";\r\n\r\n        if [ -z ${!key+x} ]; then\r\n            declare -g \"$key=$commit\";\r\n            #echo \"Declare $key\";\r\n        else\r\n            # Value is already set!\r\n            # we should do a reset\r\n            declare -g \"$key=${!key}_$commit\";\r\n            #echo \"$key is set to '${!key}'\";\r\n        fi\r\n        if $3; then\r\n            order+=(\"$tree\");\r\n        fi\r\n    done\r\n\r\n}\r\n\r\nmerge-base() {\r\n    local order=();\r\n\r\n    prepare \"left\" \"$1\" true;\r\n    prepare \"right\" \"$2\" false;\r\n\r\n    for entry in ${order[@]}; do\r\n        local left_key=\"left_$entry\";\r\n        local left_value=\"${!left_key}\";\r\n        if [[ ${#left_value} > 40 ]]; then\r\n            echo \"Duplicate_left: $left_value\";\r\n        else\r\n            local right_key=\"right_$entry\";\r\n            if [ -z ${!right_key+x} ]; then\r\n                echo \"Not found in right\";\r\n            else\r\n                local right_value=${!right_key};\r\n                if [[ ${#right_value} > 40 ]]; then\r\n                    echo \"Duplicate_right $right_value\";\r\n                else\r\n                    echo \"Found ancestor: ${!left_key},${!right_key}\";\r\n                fi\r\n            fi\r\n        fi\r\n    done\r\n}\r\n\r\nmerge-base \"$1\" \"$2\";\r\n```\r\n\r\nInstead of using a real hash/dict I use the built in variable mechanism. Hashes have the great benefit of being [0-9a-e]. So in the algorithm above you go through all commits on both side once to create the data and then you iterate through that data until you find the first candidate with equal tree hash and no duplicates.\r\n\r\nSo the best case is S+C and worst case 2S+C. No nested loops. There are some simplifications that can be done if you disregard debugging, You don't actually need to store the duplicate entires, you could simply mark it as duplicate.\r\n\r\nNote 1: I haven't tested this live yet, only on my small repo at home.\r\nNote 2: that the `declare -g`is probably a late bash as well, but it should be possible to work around with keeping everything in a single method or exporting or something else to make the data \"global\"\r\n"}}