Repository: VirtusLab/git-machete
Pull request #129 (2021-05-27 14:31:21)

Add detect-squash mode for traverse and status.
`machete` currently works very well for `merge`-based trunk-based and gitflow-based workflows, as the `status` and `traverse` commands will detected merged branches and slide-out the merged branch.

However, many trunk-based workflows rely on [`squash` merges](https://blog.dnsimple.com/2019/01/two-years-of-squash-merge/),  assuaging those of us with a fastidious obsession with linear commit histories.

As machete already supports a rebase-based development workflow "out of the box", it would make sense to detect and support upstream rebase and squash merges.

Of course, detecting an arbitrary rebase or squash merge is a non-trivial task.
Here, we implement a `git diff-tree` based heuristic, if any of the new commits on the upstream branch are "tree level" identical to a downstream branch head, we assume that the downstream branch has been merged via squash or rebase.
Though this involves a lot of `diff-tree` calls for detection, `diff-tree --quiet` makes this quite speedy as we aren't rendering full diffs for every comparison.

This detects squash and rebase merges when using the recommended github branch protection settings: "Require branches to be up to date before merging." and "Require linear history."

Override back to strict merge-based detection with using the `--merge` flag. Add `--merge` to `status` command to support strict overrides.

----------

- [x] Release notes.
- [x] Add test.

asford: @PawelLipski This should be ready for a final review.

I've update the feature to default to squash-merge detection, as you suggested, and added an opt-out via the existing `--merge` option. As mentioned, some quick benchmarks with a big-ish tree shows that `diff-tree --quiet` is quite speedy, so I don't anticipate this causing perf regressions.

Bumped version number to `3.2.0`.

Added basic functional test coverage for the feature.
asford: 🤔 It looks like I accidently discovered a version regression in the git support.
My test uses `git machete traverse -W`, which uses an `git branch --set-upstream-to`.

This feature flag was added in git `1.8.0`, in 2012.

https://github.com/git/git/blob/4e42405f00ecbbee412846f48cb0253efeebe726/Documentation/RelNotes/1.8.0.txt#L20-L22
PawelLipski: >  It looks like I accidently discovered a version regression in the git support.
> My test uses `git machete traverse -W`, which uses `git branch --set-upstream-to`.
> 
> This flag was added in git `1.8.0`, in 2012.
> 
> https://github.com/git/git/blob/4e42405f00ecbbee412846f48cb0253efeebe726/Documentation/RelNotes/1.8.0.txt#L20-L22

Whoops good spot!
PawelLipski: @asford hey, some time passed... would you like me to take this one over? Esp. the part about `git cherry`/performance optimizations

Patch:
diff --git a/.circleci/config.yml b/.circleci/config.yml
index 901474c..9467a01 100644
--- a/.circleci/config.yml
+++ b/.circleci/config.yml
@@ -26,7 +26,7 @@ jobs:
             sudo mv yq_linux_amd64 /usr/local/bin/yq
             sudo chmod +x /usr/local/bin/yq
 
-      - run: PYTHON_VERSION=3.6 GIT_VERSION=1.7.10 bash ci/tox/ci-run.sh  # Earliest versions of python/git supported by git-machete
+      - run: PYTHON_VERSION=3.6 GIT_VERSION=1.8.0 bash ci/tox/ci-run.sh  # Earliest versions of python/git supported by git-machete
       - run: PYTHON_VERSION=3.7 GIT_VERSION=2.7.6  bash ci/tox/ci-run.sh
       - run: PYTHON_VERSION=3.8 GIT_VERSION=2.25.0 bash ci/tox/ci-run.sh
       - run: PYTHON_VERSION=3.9 GIT_VERSION=2.30.1 bash ci/tox/ci-run.sh
diff --git a/README.md b/README.md
index c560139..a85cb50 100644
--- a/README.md
+++ b/README.md
@@ -172,7 +172,7 @@ The more advanced features like automated traversal, upstream inference and tree
 
 ## Git compatibility
 
-git-machete (since version 2.13.0) is compatible with git >= 1.7.10.
+git-machete (since version 2.13.0) is compatible with git >= 1.8.0
 
 
 ## Contributions
diff --git a/RELEASE_NOTES.md b/RELEASE_NOTES.md
index bdf62d9..8676250 100644
--- a/RELEASE_NOTES.md
+++ b/RELEASE_NOTES.md
@@ -1,10 +1,11 @@
 # Release notes
 
-## New in git-machete 3.1.2
+## New in git-machete 3.2.0
 
 - improved: slide-out can target branches with any number of downstream (child) branches
 - fixed: detection of no-op rebase cases in fork-point algorithm
 - fixed: if a branch is merged to its parent, `git machete status -l` now always displays an empty list of commits
+- improved: `traverse` and `status` can detect rebase and squash merges via diff-tree, use `--merge` to fallback to strict merge detection
 
 ## New in git-machete 3.1.1
 
diff --git a/completion/git-machete.completion.bash b/completion/git-machete.completion.bash
index 020ff75..3216cf8 100644
--- a/completion/git-machete.completion.bash
+++ b/completion/git-machete.completion.bash
@@ -21,7 +21,7 @@ _git_machete() {
     local reapply_opts="-f --fork-point="
     local slide_out_opts="-d --down-fork-point= -M --merge -n --no-edit-merge --no-interactive-rebase"
     local squash_opts="-f --fork-point="
-    local status_opts="--color= -L --list-commits-with-hashes -l --list-commits"
+    local status_opts="--color= -L --list-commits-with-hashes -l --list-commits -M --merge"
     local traverse_opts="-F --fetch -l --list-commits -M --merge -n --no-edit-merge --no-interactive-rebase --return-to= --start-from= -w --whole -W -y --yes"
     local update_opts="-f --fork-point= -M --merge -n --no-edit-merge --no-interactive-rebase"
 
diff --git a/completion/git-machete.completion.zsh b/completion/git-machete.completion.zsh
index 3b1f029..5954b83 100644
--- a/completion/git-machete.completion.zsh
+++ b/completion/git-machete.completion.zsh
@@ -102,6 +102,7 @@ _git-machete() {
                         '(--color)'--color='[Colorize the output; argument can be "always", "auto", or "never"]: :__git_machete_opt_color_args' \
                         '(-L --list-commits-with-hashes)'{-L,--list-commits-with-hashes}'[List the short hashes and messages of commits introduced on each branch]' \
                         '(-l --list-commits)'{-l,--list-commits}'[List the messages of commits introduced on each branch]' \
+                        '(-M --merge)'{-M,--merge}'[Strictly detect merge, rather than rebase]' \
                     && ret=0
                     ;;
                 (traverse)
diff --git a/git_machete/__init__.py b/git_machete/__init__.py
index f71b21a..573cf70 100644
--- a/git_machete/__init__.py
+++ b/git_machete/__init__.py
@@ -1,1 +1,1 @@
-__version__ = '3.1.2'
+__version__ = '3.2.0'
diff --git a/git_machete/cmd.py b/git_machete/cmd.py
index f078eee..82feb50 100644
--- a/git_machete/cmd.py
+++ b/git_machete/cmd.py
@@ -947,6 +947,14 @@ def is_full_sha(revision: str) -> Optional[Match[str]]:
     return re.match("^[0-9a-f]{40}$", revision)
 
 
+# Resolve a revision identifier to a full sha
+def full_sha(cli_ctxt: CommandLineContext, revision: str, prefix: str = "refs/heads/") -> Optional[str]:
+    if prefix == "" and is_full_sha(revision):
+        return revision
+    else:
+        return commit_sha_by_revision(cli_ctxt, revision, prefix)
+
+
 committer_unix_timestamp_by_revision_cached: Optional[Dict[str, int]] = None  # TODO (#110): default dict with 0
 
 
@@ -1094,20 +1102,68 @@ def merge_base(cli_ctxt: CommandLineContext, sha1: str, sha2: str) -> str:
 
 # Note: the 'git rev-parse --verify' validation is not performed in case for either of earlier/later
 # if the corresponding prefix is empty AND the revision is a 40 hex digit hash.
-def is_ancestor(cli_ctxt: CommandLineContext, earlier_revision: str, later_revision: str, earlier_prefix: str = "refs/heads/", later_prefix: str = "refs/heads/") -> bool:
-    if earlier_prefix == "" and is_full_sha(earlier_revision):
-        earlier_sha: Optional[str] = earlier_revision
-    else:
-        earlier_sha = commit_sha_by_revision(cli_ctxt, earlier_revision, earlier_prefix)
-    if later_prefix == "" and is_full_sha(later_revision):
-        later_sha: Optional[str] = later_revision
-    else:
-        later_sha = commit_sha_by_revision(cli_ctxt, later_revision, later_prefix)
+def is_ancestor(
+    cli_ctxt: CommandLineContext,
+    earlier_revision: str,
+    later_revision: str,
+    earlier_prefix: str = "refs/heads/",
+    later_prefix: str = "refs/heads/",
+) -> bool:
+    earlier_sha = full_sha(cli_ctxt, earlier_revision, earlier_prefix)
+    later_sha = full_sha(cli_ctxt, later_revision, later_prefix)
+
     if earlier_sha == later_sha:
         return True
     return merge_base(cli_ctxt, earlier_sha, later_sha) == earlier_sha
 
 
+# Determine if later_revision, or any ancestors of later_revision that are NOT ancestors of earlier_revision, contain a
+# tree with identical contents to earlier_revision, indicating that
+# later_revision contains a rebase or squash merge of earlier_revision.
+def contains_equivalent_tree(
+    cli_ctxt: CommandLineContext,
+    earlier_revision: str,
+    later_revision: str,
+    earlier_prefix: str = "refs/heads/",
+    later_prefix: str = "refs/heads/",
+) -> bool:
+    earlier_sha = full_sha(cli_ctxt, earlier_revision, earlier_prefix)
+    later_sha = full_sha(cli_ctxt, later_revision, later_prefix)
+
+    if earlier_sha == later_sha:
+        return True
+
+    debug(
+        cli_ctxt,
+        "contains_equivalent_tree",
+        f"earlier_revision={earlier_revision} later_revision={later_revision}",
+    )
+
+    # `git log later_sha ^earlier_sha`
+    # shows all commits reachable from later_sha but not from earlier_sha
+    #
+    # https://git-scm.com/docs/git-rev-list#_description
+    intermediate_tree_shas = non_empty_lines(
+        popen_git(
+            cli_ctxt,
+            "log",
+            "--format=%T",  # full commit's tree hash
+            later_sha,
+            "^" + earlier_sha,
+        )
+    )
+
+    earlier_tree_sha = popen_git(
+        cli_ctxt,
+        "log",
+        "--format=%T",
+        "-1",
+        earlier_sha
+    ).strip()
+
+    return earlier_tree_sha in intermediate_tree_shas
+
+
 def create_branch(cli_ctxt: CommandLineContext, b: str, out_of_revision: str) -> None:
     run_git(cli_ctxt, "checkout", "-b", b, out_of_revision)
     flush_caches()  # the repository state has changed b/c of a successful branch creation, let's defensively flush all the caches
@@ -1618,10 +1674,19 @@ def is_merged_to(cli_ctxt: CommandLineContext, b: str, target: str) -> bool:
         # (reflog stripped of trivial events like branch creation, reset etc.)
         # is non-empty.
         return bool(filtered_reflog(cli_ctxt, b, prefix="refs/heads/"))
-    else:
+    elif is_ancestor(cli_ctxt, b, target):
         # If a branch is NOT equal to the target (typically its parent),
-        # it's just enough to check if the target is reachable from the branch.
-        return is_ancestor(cli_ctxt, b, target)
+        # and target is reachable from the branch then it's merged
+        return True
+    elif not cli_ctxt.opt_merge:
+        # In the default, rebase/squash mode.
+        # If there is a commit in target with an identical tree state to b,
+        # then b may be squash or rebase merged into target.
+        return contains_equivalent_tree(cli_ctxt, b, target)
+    else:
+        # In strict merge mode.
+        # If merge isn't detected above
+        return False
 
 
 def is_merged_to_upstream(cli_ctxt: CommandLineContext, b: str) -> bool:
@@ -3117,7 +3182,7 @@ def usage(c: str = None) -> None:
               <b>-f, --fork-point=<fork-point-commit></b>    Specifies the alternative fork point commit after which the squashed part of history is meant to start.
         """,
         "status": """
-            <b>Usage: git machete s[tatus] [--color=WHEN] [-l|--list-commits] [-L|--list-commits-with-hashes]</b>
+            <b>Usage: git machete s[tatus] [--color=WHEN] [-l|--list-commits] [-L|--list-commits-with-hashes] [--merge]</b>
 
             Displays a tree-shaped status of the branches listed in the definition file.
 
@@ -3134,6 +3199,8 @@ def usage(c: str = None) -> None:
                 and the fork point of the downstream branch is <b>equal</b> to the upstream branch tip.
 
               - <b><dim>grey/dimmed edge</dim></b> means that the downstream branch has been <b>merged</b> to the upstream branch,
+                detected by commit equivalency via `diff-tree` (default), or by strict detection of merge commits (if `--merge` passed)
+
 
             * prints `(untracked/ahead of <remote>/behind <remote>/diverged from [& older than] <remote>)` message if the branch is not in sync with its remote counterpart;
 
@@ -3171,13 +3238,17 @@ def usage(c: str = None) -> None:
               <b>-l, --list-commits</b>                Additionally list the commits introduced on each branch.
 
               <b>-L, --list-commits-with-hashes</b>    Additionally list the short hashes and messages of commits introduced on each branch.
+
+              <b>-M, --merge</b>                       Only consider "strict" merges, rather than rebase/squash merges,
+                                                when detecting if a branch is merged into its upstream parent.
         """,
         "traverse": """
             <b>Usage: git machete traverse [-F|--fetch] [-l|--list-commits] [-M|--merge] [-n|--no-edit-merge|--no-interactive-rebase] [--return-to=WHERE] [--start-from=WHERE] [-w|--whole] [-W] [-y|--yes]</b>
 
             Traverses the branch dependency in pre-order (i.e. simply in the order as they occur in the definition file) and for each branch:
-            * if the branch is merged to its parent/upstream:
-              - asks the user whether to slide out the branch from the dependency tree (typically branches are longer needed after they're merged);
+            * detects if the branch is merged to its parent/upstream
+              - by commit equivalency via `diff-tree` (default), or by strict detection of merge commits (if `--merge` passed)
+              - if so, asks the user whether to slide out the branch from the dependency tree (typically branches are longer needed after they're merged);
             * otherwise, if the branch is not in "green" sync with its parent/upstream (see help for `status`):
               - asks the user whether to rebase (default) or merge (if `--merge` passed) the branch onto into its upstream branch - equivalent to `git machete update` with no `--fork-point` option passed;
 
@@ -3199,7 +3270,7 @@ def usage(c: str = None) -> None:
 
               <b>-l, --list-commits</b>           When printing the status, additionally list the messages of commits introduced on each branch.
 
-              <b>-M, --merge</b>                  Update by merge rather than by rebase.
+              <b>-M, --merge</b>                  Update, and detect updates, by merge rather than by rebase.
 
               <b>-n</b>                           If updating by rebase, equivalent to `--no-interactive-rebase`. If updating by merge, equivalent to `--no-edit-merge`.
 
@@ -3656,7 +3727,7 @@ def launch(orig_args: List[str]) -> None:
             cb = current_branch(cli_ctxt)
             squash(cli_ctxt, cb, cli_ctxt.opt_fork_point or fork_point(cli_ctxt, cb, use_overrides=True))
         elif cmd in ("s", "status"):
-            expect_no_param(parse_options(args, "Ll", ["color=", "list-commits-with-hashes", "list-commits"]))
+            expect_no_param(parse_options(args, "Ll", ["color=", "merge", "list-commits-with-hashes", "list-commits"]))
             read_definition_file(cli_ctxt)
             expect_at_least_one_managed_branch()
             status(cli_ctxt, warn_on_yellow_edges=True)


Test patch:
diff --git a/git_machete/tests/functional/test_machete.py b/git_machete/tests/functional/test_machete.py
index 9265c29..459b9aa 100644
--- a/git_machete/tests/functional/test_machete.py
+++ b/git_machete/tests/functional/test_machete.py
@@ -379,3 +379,147 @@ class MacheteTester(unittest.TestCase):
             o-child_b *
             """,
         )
+
+    def test_squash_merge(self) -> None:
+        self.maxDiff = None
+        repo = (
+            self.setup.new_branch("root")
+            .commit("root")
+            .push()
+            .new_branch("develop")
+            .commit("develop")
+            .push()
+            .new_branch("feature")
+            .commit("feature_1")
+            .commit("feature_2")
+            .push()
+            .new_branch("child")
+            .commit("child_1")
+            .commit("child_2")
+            .push()
+        )
+
+        self.launch_command("discover", "-y", "--roots=root")
+
+        self.assert_command(
+            ["status", "-l"],
+            """
+            root
+            |
+            | develop
+            o-develop
+              |
+              | feature_1
+              | feature_2
+              o-feature
+                |
+                | child_1
+                | child_2
+                o-child *
+            """,
+        )
+
+        # squash-merge feature onto develop
+        repo = (
+            repo.check_out("develop")
+            .execute("git merge --squash feature")
+            .execute("git commit -m squash_feature")
+            .check_out("child")
+        )
+
+        # in default mode, feature is detected as "m" (merged) into develop
+        self.assert_command(
+            ["status", "-l"],
+            """
+            root
+            |
+            | develop
+            | squash_feature
+            o-develop (ahead of origin)
+              |
+              m-feature
+                |
+                | child_1
+                | child_2
+                o-child *
+            """,
+        )
+
+        # but under --merge, feature is detected as "x" (behind) develop
+        self.assert_command(
+            ["status", "-l", "--merge"],
+            """
+            root
+            |
+            | develop
+            | squash_feature
+            o-develop (ahead of origin)
+              |
+              | feature_1
+              | feature_2
+              x-feature
+                |
+                | child_1
+                | child_2
+                o-child *
+            """,
+        )
+
+        # traverse then slides out the branch
+        self.launch_command("traverse", "-w", "-y")
+        self.assert_command(
+            ["status", "-l"],
+            """
+            root
+            |
+            | develop
+            | squash_feature
+            o-develop
+              |
+              | child_1
+              | child_2
+              o-child *
+            """,
+        )
+
+        # simulate an upstream squash-merge of the feature branch
+        repo = (
+            repo.check_out("develop")
+            .new_branch("upstream_squash")
+            .execute("git merge --squash child")
+            .execute("git commit -m squash_child")
+            .execute("git push origin upstream_squash:develop")
+            .check_out("child")
+            .execute("git branch -D upstream_squash")
+        )
+
+        # status before fetch will show develop as out of date
+        self.assert_command(
+            ["status", "-l"],
+            """
+            root
+            |
+            | develop
+            | squash_feature
+            o-develop (behind origin)
+              |
+              | child_1
+              | child_2
+              o-child *
+            """,
+        )
+
+        # fetch-traverse will fetch upstream squash, detect, and slide out the child branch
+        self.launch_command("traverse", "-W", "-y")
+
+        self.assert_command(
+            ["status", "-l"],
+            """
+            root
+            |
+            | develop
+            | squash_feature
+            | squash_child
+            o-develop *
+            """,
+        )