From patchwork Mon Jan 21 22:32:09 2019 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Patchwork-Submitter: Stefan Xenos X-Patchwork-Id: 10774627 Return-Path: Received: from mail.wl.linuxfoundation.org (pdx-wl-mail.web.codeaurora.org [172.30.200.125]) by pdx-korg-patchwork-2.web.codeaurora.org (Postfix) with ESMTP id 460F513B5 for ; Mon, 21 Jan 2019 22:32:37 +0000 (UTC) Received: from mail.wl.linuxfoundation.org (localhost [127.0.0.1]) by mail.wl.linuxfoundation.org (Postfix) with ESMTP id 2AB8C2AECE for ; Mon, 21 Jan 2019 22:32:37 +0000 (UTC) Received: by mail.wl.linuxfoundation.org (Postfix, from userid 486) id 28DAE2AED5; Mon, 21 Jan 2019 22:32:37 +0000 (UTC) X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on pdx-wl-mail.web.codeaurora.org X-Spam-Level: X-Spam-Status: No, score=-15.5 required=2.0 tests=BAYES_00,DKIM_SIGNED, DKIM_VALID,DKIM_VALID_AU,MAILING_LIST_MULTI,RCVD_IN_DNSWL_HI, USER_IN_DEF_DKIM_WL autolearn=ham version=3.3.1 Received: from vger.kernel.org (vger.kernel.org [209.132.180.67]) by mail.wl.linuxfoundation.org (Postfix) with ESMTP id 30A652AED4 for ; Mon, 21 Jan 2019 22:32:34 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1727012AbfAUWc0 (ORCPT ); Mon, 21 Jan 2019 17:32:26 -0500 Received: from mail-qt1-f201.google.com ([209.85.160.201]:56935 "EHLO mail-qt1-f201.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1726152AbfAUWcZ (ORCPT ); Mon, 21 Jan 2019 17:32:25 -0500 Received: by mail-qt1-f201.google.com with SMTP id q33so21991066qte.23 for ; Mon, 21 Jan 2019 14:32:23 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=20161025; h=date:message-id:mime-version:subject:from:to:cc :content-transfer-encoding; bh=YvGeJS9h2VlrmJWVP9ObhFlL/BCfvP/mOrccQSM//vM=; b=J9hooXT3hb7e+85tmcUkX5R9QX4K7Ruect+nti8pwYCqKunFmwaHR99cENkHQ3SgAD RXnEk8HAooSQa8y5ShAQYySB1pwX0QpUbqz/OFVA1hPCJy6XJzNrMjcM/K4lk13nAXan Vpj25oA3Fr7hJJKT+X71DcNsWTEqf4hJEEthDre3gD8GAJkVrnJXjvYJTrSw58oDQNqz 73s6UGMHzsuTIGkJMK0EBkuc8XVVbqQptsn4UN7tguE2VdkfgxMnvpwJuHwDaHQzt7fn Zf0DazB6nibKkh3cnpXakol5PPKOaVo1towSc0bSk47ybiSo0JMqb7kb8gn1UgYimyaM 6NCA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:date:message-id:mime-version:subject:from:to:cc :content-transfer-encoding; bh=YvGeJS9h2VlrmJWVP9ObhFlL/BCfvP/mOrccQSM//vM=; b=HpvIBJzqXExaGuEItrPyTqmDMNfO6T5xz8iEFWdCuGYhn8YLpUKqD7TqdUaGXbSJqi ZqPZLiuvBdJcWiMgc7ecbjNMWgxBAdb9rsiRI759Pky+BCXawllVMEyVRWrMCuTY45G1 /boAZeZyGAfX3Ax75vGYZRnFLzu+mS9Ekuv7UwIXd3ZPC5wGMOUJ+k4XD/d//1S3Xpo/ rvV8m3vO28iOLPC0gg2jQ/vg+GJDy8b3jPjto1JbXJb/X4sicVNRTARjOlbquVNKgO6B W2VQ0pRk4fReSIir6n+pk10nhGIaXoJET8Tgv0bq9aa7XhBUKhRbN2bGNTuWfQsRguHV PeDw== X-Gm-Message-State: AJcUukefGzh4JoiOkD8pR4WMOPAZ2dOcUCfDSbUJOHw72v5P+W0VSDFZ RgA2tAHg6esrDjMvv+0B3UAb/AiW0+Hps4dnLH0UKr/nuNMhdAY8lsxlqO3GTVSLKRPWpbGSfWO j17J5ahx0GQNL10t/fdBKSl4mcNfGHAKlNwEQUTlFKVIgT8386ce67u8MeQ== X-Google-Smtp-Source: ALg8bN4PKdylqugO33qr8WqKbT5SKlxrZuDLHJWCPQJKaxaJGXjYcAJ7wVN1l7kTII+uZr8AuehMNptmhuU= X-Received: by 2002:a0c:9e19:: with SMTP id p25mr20759905qve.50.1548109943057; Mon, 21 Jan 2019 14:32:23 -0800 (PST) Date: Mon, 21 Jan 2019 14:32:09 -0800 Message-Id: <20190121223216.66659-1-sxenos@google.com> Mime-Version: 1.0 X-Mailer: git-send-email 2.20.1.321.g9e740568ce-goog Subject: [PATCH 1/8] technical doc: add a design doc for the evolve command From: sxenos@google.com To: git@vger.kernel.org Cc: Stefan Xenos Sender: git-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org X-Virus-Scanned: ClamAV using ClamSMTP From: Stefan Xenos This document describes what a change graph for git would look like, the behavior of the evolve command, and the changes planned for other commands. Signed-off-by: Stefan Xenos --- Documentation/technical/evolve.txt | 1034 ++++++++++++++++++++++++++++ 1 file changed, 1034 insertions(+) create mode 100644 Documentation/technical/evolve.txt diff --git a/Documentation/technical/evolve.txt b/Documentation/technical/evolve.txt new file mode 100644 index 0000000000..7967c73e5d --- /dev/null +++ b/Documentation/technical/evolve.txt @@ -0,0 +1,1034 @@ +Evolve +====== + +Objective +========= +Create an "evolve" command to help users craft a high quality commit history. +Users can improve commits one at a time and in any order, then run git evolve to +rewrite their recent history to ensure everything is up-to-date. We track +amendments to a commit over time in a change graph. Users can share their +progress with others by exchanging their change graphs using the standard push, +fetch, and format-patch commands. + +Status +====== +This proposal has not been implemented yet. + +Background +========== +Imagine you have three sequential changes up for review and you receive feedback +that requires editing all three changes. We'll define the word "change" +formally later, but for the moment let's say that a change is a work-in-progress +whose final version will be submitted as a commit in the future. + +While you're editing one change, more feedback arrives on one of the others. +What do you do? + +The evolve command is a convenient way to work with chains of commits that are +under review. Whenever you rebase or amend a commit, the repository remembers +that the old commit is obsolete and has been replaced by the new one. Then, at +some point in the future, you can run "git evolve" and the correct sequence of +rebases will occur in the correct order such that no commit has an obsolete +parent. + +Part of making the "evolve" command work involves tracking the edits to a commit +over time, which is why we need an change graph. However, the change +graph will also bring other benefits: + +- Users can view the history of a change directly (the sequence of amends and + rebases it has undergone, orthogonal to the history of the branch it is on). +- It will be possible to quickly locate and list all the changes the user + currently has in progress. +- It can be used as part of other high-level commands that combine or split + changes. +- It can be used to decorate commits (in git log, gitk, etc) that are either + obsolete or are the tip of a work in progress. +- By pushing and pulling the change graph, users can collaborate more + easily on changes-in-progress. This is better than pushing and pulling the + changes themselves since the change graph can be used to locate a more + specific merge base, allowing for better merges between different versions of + the same change. +- It could be used to correctly rebase local changes and other local branches + after running git-filter-branch. +- It can replace the change-id footer used by gerrit. + +Goals +----- +Legend: Goals marked with P0 are required. Goals marked with Pn should be +attempted unless they interfere with goals marked with Pn-1. + +P0. All commands that modify commits (such as the normal commit --amend or + rebase command) should mark the old commit as being obsolete and replaced by + the new one. No additional commands should be required to keep the + change graph up-to-date. +P0. Any commit that may be involved in a future evolve command should not be + garbage collected. Specifically: + - Commits that obsolete another should not be garbage collected until + user-specified conditions have occurred and the change has expired from + the reflog. User specified conditions for removing changes include: + - The user explicitly deleted the change. + - The change was merged into a specific branch. + - Commits that have been obsoleted by another should not be garbage + collected if any of their replacements are still being retained. +P0. A commit can be obsoleted by more than one replacement (called divergence). +P0. Must be able to resolve divergence (convergence). +P1. Users should be able to share chains of obsolete changes in order to + collaborate on WIP changes. +P2. Such sharing should be at the user’s option. That is, it should be possible + to directly share a change without also sharing the file states or commit + comments from the obsolete changes that led up to it, and the choice not to + share those commits should not require changing any commit hashes. +P2. It should be possible to discard part or all of the change graph + without discarding the commits themselves that are already present in + branches and the reflog. +P2. Provide sufficient information to replace gerrit's Change-Id footers. + +Similar technologies +-------------------- +There are some other technologies that address the same end-user problem. + +Rebase -i can be used to solve the same problem, but users can't easily switch +tasks midway through an interactive rebase or have more than one interactive +rebase going on at the same time. It can't handle the case where you have +multiple changes sharing the same parent when that parent needs to be rebased +and won't let you collaborate with others on resolving a complicated interactive +rebase. You can think of rebase -i as a top-down approach and the evolve command +as the bottom-up approach to the same problem. + +Several patch queue managers have been built on top of git (such as topgit, +stgit, and quilt). They address the same user need. However they also rely on +state managed outside git that needs to be kept in sync. Such state can be +easily damaged when running a git native command that is unaware of the patch +queue. They also typically require an explicit initialization step to be done by +the user which creates workflow problems. + +Mercurial implements a very similar feature in its EvolveExtension. The behavior +of the evolve command itself is very similar, but the storage format for the +change graph differs. In the case of mercurial, each change set can have one or +more obsolescence markers that point to other changesets that they replace. This +is similar to the "Commit Headers" approach considered in the other options +appendix. The approach proposed here stores obsolescence information in a +separate metacommit graph, which makes exchanging of obsolescence information +optional. + +Mercurial's default behavior makes it easy to find and switch between +non-obsolete changesets that aren't currently on any branch. We introduce the +notion of a new ref namespace that enables a similar workflow via a different +mechanism. Mercurial has the notion of changeset phases which isn't present +in git and creates new ways for a changeset to diverge. Git doesn't need +to deal with these issues, but it has to deal with picking an upstream branch as +a target for rebases and protecting obsolescence information from GC. We also +introduce some additional transformations (see obsolescence-over-cherry-pick, +below) that aren't present in the mercurial implementation. + +Semi-related work +----------------- +There are other technologies that address different problems but have some +similarities with this proposal. + +Replacements (refs/replace) are superficially similar to obsolescences in that +they describe that one commit should be replaced by another. However, they +differ in both how they are created and how they are intended to be used. +Obsolescences are created automatically by the commands a user runs, and they +describe the user’s intent to perform a future rebase. Obsolete commits still +appear in branches, logs, etc like normal commits (possibly with an extra +decoration that marks them as obsolete). Replacements are typically created +explicitly by the user, they are meant to be kept around for a long time, and +they describe a replacement to be applied at read-time rather than as the input +to a future operation. When a replaced commit is queried, it is typically hidden +and swapped out with its replacement as though the replacement has already +occurred. + +Git-imerge is a project to help make complicated merges easier, particularly +when merging or rebasing long chains of patches. It is not an alternative to +the change graph, but its algorithm of applying smaller incremental merges +could be used as part of the evolve algorithm in the future. + +Overview +======== +We introduce the notion of “meta-commits” which describe how one commit was +created from other commits. A branch of meta-commits is known as a change. +Changes are created and updated automatically whenever a user runs a command +that creates a commit. They are used for locating obsolete commits, providing a +list of a user’s unsubmitted work in progress, and providing a stable name for +each unsubmitted change. + +Users can exchange edit histories by pushing and fetching changes. + +New commands will be introduced for manipulating changes and resolving +divergence between them. Existing commands that create commits will be updated +to modify the meta-commit graph and create changes where necessary. + +Example usage +------------- +# First create three dependent changes +$ echo foo>bar.txt && git add . +$ git commit -m "This is a test" +created change metas/this_is_a_test +$ echo foo2>bar2.txt && git add . +$ git commit -m "This is also a test" +created change metas/this_is_also_a_test +$ echo foo3>bar3.txt && git add . +$ git commit -m "More testing" +created change metas/more_testing + +# List all our changes in progress +$ git change list +metas/this_is_a_test +metas/this_is_also_a_test +* metas/more_testing +metas/some_change_already_merged_upstream + +# Now modify the earliest change, using its stable name +$ git reset --hard metas/this_is_a_test +$ echo morefoo>>bar.txt && git add . && git commit --amend --no-edit + +# Use git-evolve to fix up any dependent changes +$ git evolve +rebasing metas/this_is_also_a_test onto metas/this_is_a_test +rebasing metas/more_testing onto metas/this_is_also_a_test +Done + +# Use git-obslog to view the history of the this_is_a_test change +$ git log --obslog +93f110 metas/this_is_a_test@{0} commit (amend): This is a test +930219 metas/this_is_a_test@{1} commit: This is a test + +# Now create an unrelated change +$ git reset --hard origin/master +$ echo newchange>unrelated.txt && git add . +$ git commit -m "Unrelated change" +created change metas/unrelated_change + +# Fetch the latest code from origin/master and use git-evolve +# to rebase all dependent changes. +$ git fetch origin master +$ git evolve origin/master +deleting metas/some_change_already_merged_upstream +rebasing metas/this_is_a_test onto origin/master +rebasing metas/this_is_also_a_test onto metas/this_is_a_test +rebasing metas/more_testing onto metas/this_is_also_a_test +rebasing metas/unrelated_change onto origin/master +Conflict detected! Resolve it and then use git evolve --continue to resume. + +# Sort out the conflict +$ git mergetool +$ git evolve --continue +Done + +# Share the full history of edits for the this_is_a_test change +# with a review server +$ git push origin metas/this_is_a_test:refs/for/master +# Share the lastest commit for “Unrelated change”, without history +$ git push origin HEAD:refs/for/master + +Detailed design +=============== +Obsolescence information is stored as a graph of meta-commits. A meta-commit is +a specially-formatted merge commit that describes how one commit was created +from others. + +Meta-commits look like this: + +$ git cat-file -p +tree 4b825dc642cb6eb9a060e54bf8d69288fbee4904 +parent aa7ce55545bf2c14bef48db91af1a74e2347539a +parent d64309ee51d0af12723b6cb027fc9f195b15a5e9 +parent 7e1bbcd3a0fa854a7a9eac9bf1eea6465de98136 +author Stefan Xenos 1540841596 -0700 +committer Stefan Xenos 1540841596 -0700 +parent-type c r o + +This says “commit aa7ce555 makes commit d64309ee obsolete. It was created by +cherry-picking commit 7e1bbcd3”. + +The tree for meta-commits is always the empty tree whose hash matches +4b825dc642cb6eb9a060e54bf8d69288fbee4904 exactly, but future versions of git may +attach other trees here. For forward-compatibility fsck should ignore such trees +if found on future repository versions. Similarly, current versions of git +should always fill in an empty commit comment and tools like fsck should ignore +the content of the commit comment if present in a future repository version. +This will allow future versions of git to add metadata to the meta-commit +comments or tree without breaking forwards compatibility. + +Parent-type +----------- +The “parent-type” field in the commit header identifies a commit as a +meta-commit and indicates the meaning for each of its parents. It is never +present for normal commits. It contains a space-deliminated list of enum values +whose order matches the order of the parents. Possible parent types are: + +- c: (content) the content parent identifies the commit that this meta-commit is + describing. +- r: (replaced) indicates that this parent is made obsolete by the content + parent. +- o: (origin) indicates that this parent was generated from the given commit. +- a: (abandoned) used in place of a content parent for abandoned changes. Points + to the final content commit for the change at the time it was abandoned. + +There must be exactly one content or abandoned parent for each meta-commit and it is +always the first parent. The content commit will always be a normal commit and not a +meta-commit. However, future versions of git may create meta-commits for other +meta-commits and the fsck tool must be aware of this for forwards compatibility. + +A meta-commit can have zero or more replaced parents. An amend operation creates +a single replaced parent. A merge used to resolve divergence (see divergence, +below) will create multiple replaced parents. A meta-commit may have no +replaced parents if it describes a cherry-pick or squash merge that copies one +or more commits but does not replace them. + +A meta-commit can have zero or more origin parents. A cherry-pick creates a +single origin parent. Certain types of squash merge will create multiple origin +parents. Origin parents don't directly cause their origin to become obsolete, +but are used when computing blame or locating a merge base. The section +on obsolescence over cherry-picks describes how the evolve command uses +origin parents. + +A replaced parent or origin parent may be either a normal commit (indicating +the oldest-known version of a change) or another meta-commit (for a change that +has already been modified one or more times). + +The parent-type field needs to go after the committer field since git's rules +for forwards-compatibility require that new fields to be at the end of the +header. Putting a new field in the middle of the header would break fsck. + +The presence of an abandoned parent indicates that the change should be pruned +by the evolve command, and removed from the repository's history. The abandoned +parent points to the version of the change that should be restored if the user +attempts to restore the change. + +Changes +------- +A branch of meta-commits describes how a commit was produced and what previous +commits it is based on. It is also an identifier for a thing the user is +currently working on. We refer to such a meta-branch as a change. + +Local changes are stored in the new refs/metas namespace. Remote changes are +stored in the refs/remote//metas namespace. + +The list of changes in refs/metas is more than just a mechanism for the evolve +command to locate obsolete commits. It is also a convenient list of all of a +user’s work in progress and their current state - a list of things they’re +likely to want to come back to. + +Strictly speaking, it is the presence of the branch in the refs/metas namespace +that marks a branch as being a change, not the fact that it points to a +metacommit. Metacommits are only created when a commit is amended or rebased, so +in the case where a change points to a commit that has never been modified, the +change points to that initial commit rather than a metacommit. + +Changes are also stored in the refs/hiddenmetas namespace. Hiddenmetas holds +metadata for historical changes that are not currently in progress by the user. +Commands like filter-branch and other bulk import commands create metadata in +this namespace. + +Note that the changes in hiddenmetas get special treatment in several ways: + +- They are not cleaned up automatically once merged, since it is expected that + they refer to historical changes. +- User commands that modify changes don't append to these changes as they would + to a change in refs/metas. +- They are not displayed when the user lists their local changes. + +Obsolescence +------------ +A commit is considered obsolete if it is reachable from the “replaces” edges +anywhere in the history of a change and it isn’t the head of that change. +Commits may be the content for 0 or more meta-commits. If the same commit +appears in multiple changes, it is not obsolete if it is the head of any of +those changes. + +Note that there is an exeption to this rule. The metas namespace takes +precedence over the hiddenmetas namespace for the purpose of obsolescence. That +is, if a change appears in a replaces edge of a change in the metas namespace, +it is obsolete even if it also appears as the head of a change in the +hiddenmetas namespace. + +This special case prevents the hiddenmetas namespace from creating divergence +with the user's work in progress, and allows the user to resolve historical +divergence by creating new changes in the metas namespace. + +Divergence +---------- +From the user’s perspective, two changes are divergent if they both ask for +different replacements to the same commit. More precisely, a target commit is +considered divergent if there is more than one commit at the head of a change in +refs/metas that leads to the target commit via an unbroken chain of “obsolete” +parents. + +Much like a merge conflict, divergence is a situation that requires user +intervention to resolve. The evolve command will stop when it encounters +divergence and prompt the user to resolve the problem. Users can solve the +problem in several ways: + +- Discard one of the changes (by deleting its change branch). +- Merge the two changes (producing a single change branch). +- Copy one of the changes (keep both commits, but one of them gets a new + metacommit appended to its history that is connected to its predecessor via an + origin edge rather than an obsolete edge. That new change no longer obsoletes + the original.) + +Obsolescence across cherry-picks +-------------------------------- +By default the evolve command will treat cherry-picks and squash merges as being +completely separate from the original. Further amendments to the original commit +will have no effect on the cherry-picked copy. However, this behavior may not be +desirable in all circumstances. + +The evolve command may at some point support an option to look for cases where +the source of a cherry-pick or squash merge has itself been amended, and +automatically apply that same change to the cherry-picked copy. In such cases, +it would traverse origin edges rather than ignoring them, and would treat a +commit with origin edges as being obsolete if any of its origins were obsolete. + +Garbage collection +------------------ +For GC purposes, meta-commits are normal commits. Just as a commit causes its +parents and tree to be retained, a meta-commit also causes its parents to be +retained. + +Change creation +--------------- +Changes are created automatically whenever the user runs a command like “commit” +that has the semantics of creating a new change. They also move forward +automatically even if they’re not checked out. For example, whenever the user +runs a command like “commit --amend” that modifies a commit, all branches in +refs/metas that pointed to the old commit move forward to point to its +replacement instead. This also happens when the user is working from a detached +head. + +This does not mean that every commit has a corresponding change. By default, +changes only exist for recent locally-created commits. Users may explicitly pull +changes from other users or keep their changes around for a long time, but +either behavior requires a user to opt-in. Code review systems like gerrit may +also choose to keep changes around forever. + +Note that the changes in refs/metas serve a dual function as both a way to +identify obsolete changes and as a way for the user to keep track of their work +in progress. If we were only concerned with identifying obsolete changes, it +would be sufficient to create the change branch lazily the first time a commit +is obsoleted. Addressing the second use - of refs/metas as a mechanism for +keeping track of work in progress - is the reason for eagerly creating the +change on first commit. + +Change naming +------------- +When a change is first created, the only requirement for its name is that it +must be unique. Good names would also serve as useful mnemonics and be easy to +type. For example, a short word from the commit message containing no numbers or +special characters and that shows up with low frequency in other commit messages +would make a good choice. + +Different users may prefer different heuristics for their change names. For this +reason a new hook will be introduced to compute change names. Git will invoke +the hook for all newly-created changes and will append a numeric suffix if the +name isn’t unique. The default heuristics are not specified by this proposal and +may change during implementation. + +Change deletion +--------------- +Changes are normally only interesting to a user while a commit is still in +development and under review. Once the commit has submitted wherever it is +going, its change can be discarded. + +The normal way of deleting changes makes this easy to do - changes are deleted +by the evolve command when it detects that the change is present in an upstream +branch. It does this in two ways: if the latest commit in a change either shows +up in the branch history or the change becomes empty after a rebase, it is +considered merged and the change is discarded. In this context, an “upstream +branch” is any branch passed in as the upstream argument of the evolve command. + +In case this sometimes deletes a useful change, such automatic deletions are +recorded in the reflog allowing them to be easily recovered. + +Sharing changes +--------------- +Change histories are shared by pushing or fetching meta-commits and change +branches. This provides users with a lot of control of what to share and +repository implementations with control over what to retain. + +Users that only want to share the content of a commit can do so by pushing the +commit itself as they currently would. Users that want to share an edit history +for the commit can push its change, which would point to a meta-commit rather +than the commit itself if there is any history to share. Note that multiple +changes can refer to the same commits, so it’s possible to construct and push a +different history for the same commit in order to remove sensitive or irrelevant +intermediate states. + +Imagine the user is working on a change “mychange” that is currently the latest +commit on master, they have two ways to share it: + +# User shares just a commit without its history +> git push origin master + +# User shares the full history of the commit to a review system +> git push origin metas/mychange:refs/for/master + +# User fetches a collaborator’s modifications to their change +> git fetch remotename metas/mychange +# Which updates the ref remote/remotename/metas/mychange + +This will cause more intermediate states to be shared with the server than would +have been shared previously. A review system like gerrit would need to keep +track of which states had been explicitly pushed versus other intermediate +states in order to de-emphasize (or hide) the extra intermediate states from the +user interface. + +Merge-base +---------- +Merge-base will be changed to search the meta-commit graph for common ancestors +as well as the commit graph, and will generally prefer results from the +meta-commit graph over the commit graph. Merge-base will consider meta-commits +from all changes, and will traverse both origin and obsolete edges. + +The reason for this is that - when merging two versions of the same commit +together - an earlier version of that same commit will usually be much more +similar than their common parent. This should make the workflow of collaborating +on unsubmitted patches as convenient as the workflow for collaborating in a +topic branch by eliminating repeated merges. + +Configuration +------------- +The core.enableChanges configuration variable enables the creation and update +of change branches. This is enabled by default. + +User interface +-------------- +All git porcelain commands that create commits are classified as having one of +four behaviors: modify, create, copy, or import. These behaviors are discussed +in more detail below. + +Modify commands +--------------- +Modification commands (commit --amend, rebase) will mark the old commit as +obsolete by creating a new meta-commit that references the old one as a +replaced parent. In the event that multiple changes point to the same commit, +this is done independently for every such change. + +More specifically, modifications work like this: + +1. Locate all existing changes for which the old commit is the content for the + head of the change branch. If no such branch exists, create one that points + to the old commit. Changes that include this commit in their history but not + at their head are explicitly not included. +2. For every such change, create a new meta-commit that references the new + commit as its content and references the old head of the change as a + replaced parent. +3. Move the change branch forward to point to the new meta-commit. + +Copy commands +------------- +Copy commands (cherry-pick, merge --squash) create a new meta-commit that +references the old commits as origin parents. Besides the fact that the new +parents are tagged differently, copy commands work the same way as modify +commands. + +Create commands +--------------- +Creation commands (commit, merge) create a new commit and a new change that +points to that commit. The do not create any meta-commits. + +Import commands +--------------- +Import commands (fetch, pull) do not create any new meta-commits or changes +unless that is specifically what they are importing. For example, the fetch +command would update remote/origin/metas/change35 and fetch all referenced +meta-commits if asked to do so directly, but it wouldn’t create any changes or +meta-commits for commits discovered on the master branch when running “git fetch +origin master”. + +Other commands +-------------- +Some commands don’t fit cleanly into one of the above categories. + +Semantically, filter-branch should be treated as a modify command, but doing so +is likely to create a lot of irrelevant clutter in the changes namespace and the +large number of extra change refs may introduce performance problems. We +recommend treating filter-branch as an import command initially, but making it +behave more like a modify command in future follow-up work. One possible +solution may be to treat commits that are part of existing changes as being +modified but to avoid creating changes for other rewritten changes. + +Once the evolve command can handle obsolescence across cherry-picks, such +cherry-picks will result in a hybrid move-and-copy operation. It will create +cherry-picks that replace other cherry-picks, which will have both origin edges +(pointing to the new source commit being picked) and obsolete edges (pointing to +the previous cherry-pick being replaced). + +Evolve +------ +The evolve command performs the correct sequence of rebases such that no change +has an obsolete parent. The syntax looks like this: + +git evolve [--abort][--continue][--quit] [upstream…] + +It takes an optional list of upstream branches. All changes whose parent shows +up in the history of one of the upstream branches will be rebased onto the +upstream branch before resolving obsolete parents. + +Any change whose latest state is found in an upstream branch (or that ends up +empty after rebase) will be deleted. This is the normal mechanism for deleting +changes. Changes are created automatically on the first commit, and are deleted +automatically when evolve determines that they’ve been merged upstream. + +Orphan commits are commits with obsolete parents. The evolve command then +repeatedly rebases orphan commits with non-orphan parents until there are either +no orphan commits left, a merge conflict is discovered, or a divergent parent is +discovered. + +When evolve discovers divergence, it will first check if it can resolve the +divergence automatically using one of its enabled transformations. Supported +transformations are: + +- Check if the user has already merged the divergent changes in a follow-up + change. That is, look for an existing merge in a follow-up change where all + the parents are divergent versions of the same change. Squash that merge with + its parents and use the result as the resolution for the divergence. + +- Attempt to auto-merge all the divergent changes (disabled by default). + +Each of the transformations can be enabled or disabled by command line options. + +The --abort option returns all changes to the state they were in prior to +invoking evolve, and the --quit option terminates the current evolution without +changing the current state. + +If the working tree is dirty, evolve will attempt to stash the user's changes +before applying the evolve and then reapply those changes afterward, in much +the same way as rebase --autostash does. + +Checkout +-------- +Running checkout on a change by name has the same effect as checking out a +detached head pointing to the latest commit on that change-branch. There is no +need to ever have HEAD point to a change since changes always move forward when +necessary, no matter what branch the user has checked out + +Meta-commits themselves cannot be checked out by their hash. + +Reset +----- +Resetting a branch to a change by name is the same as resetting to the commit at +that change’s head. + +Commit +------ +Commit --amend gets modify semantics and will move existing changes forward. The +normal form of commit gets create semantics and will create a new change. + +$ touch foo && git add . && git commit -m "foo" && git tag A +$ touch bar && git add . && git commit -m "bar" && git tag B +$ touch baz && git add . && git commit -m "baz" && git tag C + +This produces the following commits: +A(tree=[foo]) +B(tree=[foo, bar], parent=A) +C(tree=[foo, bar, baz], parent=B) + +...along with three changes: +metas/foo = A +metas/bar = B +metas/baz = C + +Running commit --amend does the following: +$ git checkout B +$ touch zoom && git add . && git commit --amend -m "baz and zoom" +$ git tag D + +Commits: +A(tree=[foo]) +B(tree=[foo, bar], parent=A) +C(tree=[foo, bar, baz], parent=B) +D(tree=[foo, bar, zoom], parent=A) +Dmeta(content=D, obsolete=B) + +Changes: +metas/foo = A +metas/bar = Dmeta +metas/baz = C + +Merge +----- +Merge gets create, modify, or copy semantics based on what is being merged and +the options being used. + +The --squash version of merge gets copy semantics (it produces a new change that +is marked as a copy of all the original changes that were squashed into it). + +The “modify” version of merge replaces both of the original commits with the +resulting merge commit. This is one of the standard mechanisms for resolving +divergence. The parents of the merge commit are the parents of the two commits +being merged. The resulting commit will not be a merge commit if both of the +original commits had the same parent or if one was the parent of the other. + +The “create” version of merge creates a new change pointing to a merge commit +that has both original commits as parents. The result is what merge produces now +- a new merge commit. However, this version of merge doesn’t directly resolve +divergence. + +To select between these two behaviors, merge gets new “--amend” and “--noamend” +options which select between the “create” and “modify” behaviors respectively, +with noamend being the default. + +For example, imagine we created two divergent changes like this: + +$ touch foo && git add . && git commit -m "foo" && git tag A +$ touch bar && git add . && git commit -m "bar" && git tag B +$ touch baz && git add . && git commit --amend -m "bar and baz" +$ git tag C +$ git checkout B +$ touch bam && git add . && git commit --amend -m "bar and bam" +$ git tag D + +At this point the commit graph looks like this: + +A(tree=[foo]) +B(tree=[bar], parent=A) +C(tree=[bar, baz], parent=A) +D(tree=[bar, bam], parent=A) +Cmeta(content=C, obsoletes=B) +Dmeta(content=D, obsoletes=B) + +There would be three active changes with heads pointing as follows: + +metas/changeA=A +metas/changeB=Cmeta +metas/changeB2=Dmeta + +ChangeB and changeB2 are divergent at this point. Lets consider what happens if +perform each type of merge between changeB and changeB2. + +Merge example: Amend merge +One way to resolve divergent changes is to use an amend merge. Recall that HEAD +is currently pointing to D at this point. + +$ git merge --amend metas/changeB + +Here we’ve asked for an amend merge since we’re trying to resolve divergence +between two versions of the same change. There are no conflicts so we end up +with this: + +E(tree=[bar, baz, bam], parent=A) +Emeta(content=E, obsoletes=[Cmeta, Dmeta]) + +With the following branches: + +metas/changeA=A +metas/changeB=Emeta +metas/changeB2=Emeta + +Notice that the result of the “amend merge” is a replacement for C and D rather +than a new commit with C and D as parents (as a normal merge would have +produced). The parents of the amend merge are the parents of C and D which - in +this case - is just A, so the result is not a merge commit. Also notice that +changeB and changeB2 are now aliases for the same change. + +Merge example: Noamend merge +Consider what would have happened if we’d used a noamend merge instead. Recall +that HEAD was at D and our branches looked like this: + +metas/changeA=A +metas/changeB=Cmeta +metas/changeB2=Dmeta + +$ git merge --noamend metas/changeB + +That would produce the sort of merge we’d normally expect today: + +F(tree=[bar, baz, bam], parent=[C, D]) + +And our changes would look like this: +metas/changeA=A +metas/changeB=Cmeta +metas/changeB2=Dmeta +metas/changeF=F + +In this case, changeB and changeB2 are still divergent and we’ve created a new +change for our merge commit. However, this is just a temporary state. The next +time we run the “evolve” command, it will discover the divergence but also +discover the merge commit F that resolves it. Evolve will suggest converting F +into an amend merge in order to resolve the divergence and will display the +command for doing so. + +Rebase +------ +In general the rebase command is treated as a modify command. When a change is +rebased, the new commit replaces the original. + +Rebase --abort is special. Its intent is to restore git to the state it had +prior to running rebase. It should move back any changes to point to the refs +they had prior to running rebase and delete any new changes that were created as +part of the rebase. To achieve this, rebase will save the state of all changes +in refs/metas prior to running rebase and will restore the entire namespace +after rebase completes (deleting any newly-created changes). Newly-created +metacommits are left in place, but will have no effect until garbage collected +since metacommits are only used if they are reachable from refs/metas. + +Change +------ +The “change” command can be used to list, rename, reset or delete change. It has +a number of subcommands. + +The "list" subcommand lists local changes. If given the -r argument, it lists +remote changes. + +The "rename" subcommand renames a change, given its old and new name. If the old +name is omitted and there is exactly one change pointing to the current HEAD, +that change is renamed. If there are no changes pointing to the current HEAD, +one is created with the given name. + +The "forget" subcommand deletes a change by deleting its ref from the metas/ +namespace. This is the normal way to delete extra aliases for a change if the +change has more than one name. By default, this will refuse to delete the last +alias for a change if there are any other changes that reference this change as +a parent. + +The "update" subcommand adds a new state to a change. It uses the default +algorithm for assigning change names. If the content commit is omitted, HEAD is +used. If given the optional --force argument, it will overwrite any existing +change of the same name. This latter form of "update" can be used to effectively +reset changes. + +The "update" command can accept any number of --origin and --replace arguments. +If any are present, the resulting change branch will point to a metacommit +containing the given origin and replacement edges. + +The "replace" command records a replacement in the obsolescence graph, given a +list of obsolete commits or metacommits followed by their replacement. This +behaves like a normal "modify" command, except that the replacement is an +existing commit. If an obsolete commit points to a metacommit, only a change +branch pointing to exactly that metacommit moves forward. If an obsolete commit +points to a normal commit, all change branches pointing to that commit move +forward. If no change branches moved forward, a new change branch is created +using the default name. + +The "abandon" command deletes a change using obsolescence markers. It marks the +change as being obsolete and having been replaced by its parent. If given no +arguments, it applies to the current commit. Running evolve will cause any +abandoned changes to be removed from the branch. Any child changes will be +reparented on top of the parent of the abandoned change. If the current change +is abandoned, HEAD will move to point to its parent. + +The "restore" command restores a previously-abandoned change. + +The "prune" command deletes all obsolete changes and all changes that are +present in the given branch. Note that such changes can be recovered from the +reflog. + +Combined with the GC protection that is offered, this is intended to facilitate +a workflow that relies on changes instead of branches. Users could choose to +work with no local branches and use changes instead - both for mailing list and +gerrit workflows. + +Log +--- +When a commit is shown in git log that is part of a change, it is decorated with +extra change information. If it is the head of a change, the name of the change +is shown next to the list of branches. If it is obsolete, it is decorated with +the text “obsolete, commits behind ”. + +Log gets a new --obslog argument indicating that the obsolescence graph should +be followed instead of the commit graph. This also changes the default +formatting options to make them more appropriate for viewing different +iterations of the same commit. + +Pull +---- + +Pull gets an --evolve argument that will automatically attempt to run "evolve" +on any affected branches after pulling. + +We also introduce an "evolve" enum value for the branch..rebase config +value. When set, the evolve behavior will happen automatically for that branch +after every pull even if the --evolve argument is not used. + +Next +---- + +The "next" command will reset HEAD to a non-obsolete commit that refers to this +change as its parent. If there is more than one such change, the user will be +prompted. If given the --evolve argument, the next commit will be evolved if +necessary first. + +The "next" command can be thought of as the opposite of +"git reset --hard HEAD^" in that it navigates to a child commit rather than a +parent. + +Other options considered +======================== +We considered several other options for storing the obsolescence graph. This +section describes the other options and why they were rejected. + +Commit header +------------- +Add an “obsoletes” field to the commit header that points backwards from a +commit to the previous commits it obsoletes. + +Pros: +- Very simple +- Easy to traverse from a commit to the previous commits it obsoletes. +Cons: +- Adds a cost to the storage format, even for commits where the change history + is uninteresting. +- Unconditionally prevents the change history from being garbage collected. +- Always causes the change history to be shared when pushing or pulling changes. + +Git notes +--------- +Instead of storing obsolescence information in metacommits, the metacommit +content could go in a new notes namespace - say refs/notes/metacommit. Each note +would contain the list of obsolete and origin parents, and an automerger could +be supplied to make it easy to merge the metacommit notes from different remotes. + +Pros: +- Easy to locate all commits obsoleted by a given commit (since there would only + be one metacommit for any given commit). +Cons: +- Wrong GC behavior (obsolete commits wouldn’t automatically be retained by GC) + unless we introduced a special case for these kinds of notes. +- No way to selectively share or pull the metacommits for one specific change. + It would be all-or-nothing, which would be expensive. This could be addressed + by changes to the protocol, but this would be invasive. +- Requires custom auto-merging behavior on fetch. + +Tags +---- +Put the content of the metacommit in a message attached to tag on the +replacement commit. This is very similar to the git notes approach and has the +same pros and cons. + +Simple forward references +------------------------- +Record an edge from an obsolete commit to its replacement in this form: + +refs/obsoletes/ + +pointing to commit as an indication that B is the replacement for the +obsolete commit A. + +Pros: +- Protects from being garbage collected. +- Fast lookup for the evolve operation, without additional search structures + (“what is the replacement for ?” is very fast). + +Cons: +- Can’t represent divergence (which is a P0 requirement). +- Creates lots of refs (which can be inefficient) +- Doesn’t provide a way to fetch only refs for a specific change. +- The obslog command requires a search of all refs. + +Complex forward references +-------------------------- +Record an edge from an obsolete commit to its replacement in this form: + +refs/obsoletes//obs_ + +Pointing to commit as an indication that B is the replacement for obsolete +commit A. + +Pros: +- Permits sharing and fetching refs for only a specific change. +- Supports divergence +- Protects from being garbage collected. + +Cons: +- Creates lots of refs, which is inefficient. +- Doesn’t provide a good lookup structure for lookups in either direction. + +Backward references +------------------- +Record an edge from a replacement commit to the obsolete one in this form: + +refs/obsolescences/ + +Cons: +- Doesn’t provide a way to resolve divergence (which is a P0 requirement). +- Doesn’t protect from being garbage collected (which could be fixed by + combining this with a refs/metas namespace, as in the metacommit variant). + +Obsolescences file +------------------ +Create a custom file (or files) in .git recording obsolescences. + +Pros: +- Can store exactly the information we want with exactly the performance we want + for all operations. For example, there could be a disk-based hashtable + permitting constant time lookups in either direction. + +Cons: +- Handling GC, pushing, and pulling would all require custom solutions. GC + issues could be addressed with a repository format extension. + +Squash points +------------- +We create and update change branches in refs/metas them at the same time we +would in the metacommit proposal. However, rather than pointing to a metacommit +branch they point to normal commits and are treated as “squash points” - markers +for sequences of commits intended to be squashed together on submission. + +Amends and rebases work differently than they do now. Rather than actually +containing the desired state of a commit, they contain a delta from the previous +version along with a squash point indicating that the preceding changes are +intended to be squashed on submission. Specifically, amends would become new +changes and rebases would become merge commits with the old commit and new +parent as parents. + +When the changes are finally submitted, the squashes are executed, producing the +final version of the commit. + +In addition to the squash points, git would maintain a set of “nosquash” tags +for commits that were used as ancestors of a change that are not meant to be +included in the squash. + +For example, if we have this commit graph: + +A(...) +B(parent=A) +C(parent=B) + +...and we amend B to produce D, we’d get: + +A(...) +B(parent=A) +C(parent=B) +D(parent=B) + +...along with a new change branch indicating D should be squashed with its +parents when submitted: + +metas/changeB = D +metas/changeC = C + +We’d also create a nosquash tag for A indicating that A shouldn’t be included +when changeB is squashed. + +If a user amends the change again, they’d get: + +A(...) +B(parent=A) +C(parent=B) +D(parent=B) +E(parent=D) + +metas/changeB = E +metas/changeC = C + +Pros: +- Good GC behavior. +- Provides a natural way to share changes (they’re just normal branches). +- Merge-base works automatically without special cases. +- Rewriting the obslog would be easy using existing git commands. +- No new data types needed. +Cons: +- No way to connect the squashed version of a change to the original, so no way + to automatically clean up old changes. This also means users lose all benefits + of the evolve command if they prematurely squash their commits. This may occur + if a user thinks a change is ready for submission, squashes it, and then later + discovers an additional change to make. +- Histories would look very cluttered (users would see all previous edits to + their commit in the commit log, and all previous rebases would show up as + merges). Could be quite hard for users to tell what is going on. (Possible + fix: also implement a new smart log feature that displays the log as though + the squashes had occurred). +- Need to change the current behavior of current commands (like amend and + rebase) in ways that will be unexpected to many users. From patchwork Mon Jan 21 22:32:11 2019 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Stefan Xenos X-Patchwork-Id: 10774621 Return-Path: Received: from mail.wl.linuxfoundation.org (pdx-wl-mail.web.codeaurora.org [172.30.200.125]) by pdx-korg-patchwork-2.web.codeaurora.org (Postfix) with ESMTP id 34F4113B5 for ; Mon, 21 Jan 2019 22:32:35 +0000 (UTC) Received: from mail.wl.linuxfoundation.org (localhost [127.0.0.1]) by mail.wl.linuxfoundation.org (Postfix) with ESMTP id 26E372AEA8 for ; Mon, 21 Jan 2019 22:32:35 +0000 (UTC) Received: by mail.wl.linuxfoundation.org (Postfix, from userid 486) id 256102AEC8; Mon, 21 Jan 2019 22:32:35 +0000 (UTC) X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on pdx-wl-mail.web.codeaurora.org X-Spam-Level: X-Spam-Status: No, score=-15.5 required=2.0 tests=BAYES_00,DKIM_SIGNED, DKIM_VALID,DKIM_VALID_AU,MAILING_LIST_MULTI,RCVD_IN_DNSWL_HI, USER_IN_DEF_DKIM_WL autolearn=ham version=3.3.1 Received: from vger.kernel.org (vger.kernel.org [209.132.180.67]) by mail.wl.linuxfoundation.org (Postfix) with ESMTP id 99EA12AEBF for ; Mon, 21 Jan 2019 22:32:34 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1727338AbfAUWca (ORCPT ); Mon, 21 Jan 2019 17:32:30 -0500 Received: from mail-qk1-f202.google.com ([209.85.222.202]:49407 "EHLO mail-qk1-f202.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1726541AbfAUWc2 (ORCPT ); Mon, 21 Jan 2019 17:32:28 -0500 Received: by mail-qk1-f202.google.com with SMTP id s14so20382626qkl.16 for ; Mon, 21 Jan 2019 14:32:28 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=20161025; h=date:in-reply-to:message-id:mime-version:references:subject:from:to :cc; bh=WqhtwsxwpDV2Ccj3BLiSJs3MJjNMvGGkbrGHBlaiXGc=; b=qi4ofmvyTU6V2TfDsu4XRb13SQpuVDe4oVZCpA5/3mZNY04pH49OUqoZafuZdvozjG YhVY3dPws32YfK+oMdSSR27SjO/0l/dDh/CrHa3SHd/zQPEyW2X7Z1ck5B8drj9Z0hy1 ybtLjjKQAt3JZXCOWqTt4FU+pnJGT/SD2o/2sF2xiMKIferq63mkesjmUM9eXFbh5tIU Jku7t7Cq1vGbL34CLjeVx/a3Ct0htDQL7Gqxt+roBPem3wJzj27iZPTDIko3lgWSJVfn 4iAoZgIy3aJEiv2v6ihuLq6mu2RCkr7eZQzkzV03fVhikQCg6wpiULC3Az1sjnyHCX7Q mhGQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:date:in-reply-to:message-id:mime-version :references:subject:from:to:cc; bh=WqhtwsxwpDV2Ccj3BLiSJs3MJjNMvGGkbrGHBlaiXGc=; b=RKS/m0tm4BPNybDdgsnJTiFS7XlkU+PLM9HIghtkd4oYuPynwmAKnXUHJ0a433/zYK vyYJ20aQiDrCpixLKOv+Y/CtfbgHWo1L9YmgCpoimebINNK0+vIiZJyRfasSVhakdKVq TvdFgCkqCTHcUr0Ipo9NG7nnikj74A9gtxiWiAPHorQJNveEtbZewX0xPCUiZEb92ve+ MWpVZfYOrSEtoxXUIZPR72STWcXsI8KvqjFQ2Lws77oUNxBeiAK0zrqpWF6uMgwYnGY2 /PioEfrPe7aDA0vu9C7YYURoS53whCd+OkUGmZ7+t4LYMBMSYNM+OwcO5Seole3dyNxJ t+pw== X-Gm-Message-State: AJcUukdVNzIZSsjq81spM4sQ2upd7TOYnYiwQXRAaWhS4Pbf8SFTEVd/ cUAlNp/NS+aGMPWtZLOVp8S271NDDkv1JUZhEex5v5+eeQ77MRw+eC3VExXc7wcojj2gJQJxgwe eb1GweDHqAUyLFr4s2GjWcmTrLmzorHK1dOqYO9FRTedkYG+bJrl9qBJRiw== X-Google-Smtp-Source: ALg8bN5gFROcQ2+kxqUD/Usw1ttANhBWKtup2LN04jSVMUtnx42V3YS6ETgyYtjes9rZell6SYXJ8E+2sgE= X-Received: by 2002:a0c:add8:: with SMTP id x24mr20655991qvc.16.1548109947805; Mon, 21 Jan 2019 14:32:27 -0800 (PST) Date: Mon, 21 Jan 2019 14:32:11 -0800 In-Reply-To: <20190121223216.66659-1-sxenos@google.com> Message-Id: <20190121223216.66659-3-sxenos@google.com> Mime-Version: 1.0 References: <20190121223216.66659-1-sxenos@google.com> X-Mailer: git-send-email 2.20.1.321.g9e740568ce-goog Subject: [PATCH 3/8] evlove: Add the metas namespace to ref-filter From: sxenos@google.com To: git@vger.kernel.org Cc: Stefan Xenos Sender: git-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org X-Virus-Scanned: ClamAV using ClamSMTP From: Stefan Xenos The metas namespace will contain refs for changes in progress. Add support for searching this namespace. --- ref-filter.c | 8 ++++++-- ref-filter.h | 5 +++-- 2 files changed, 9 insertions(+), 4 deletions(-) diff --git a/ref-filter.c b/ref-filter.c index 422a9c9ae3..4d7bd06880 100644 --- a/ref-filter.c +++ b/ref-filter.c @@ -1925,7 +1925,8 @@ static int ref_kind_from_refname(const char *refname) } ref_kind[] = { { "refs/heads/" , FILTER_REFS_BRANCHES }, { "refs/remotes/" , FILTER_REFS_REMOTES }, - { "refs/tags/", FILTER_REFS_TAGS} + { "refs/tags/", FILTER_REFS_TAGS }, + { "refs/metas/", FILTER_REFS_CHANGES } }; if (!strcmp(refname, "HEAD")) @@ -1943,7 +1944,8 @@ static int filter_ref_kind(struct ref_filter *filter, const char *refname) { if (filter->kind == FILTER_REFS_BRANCHES || filter->kind == FILTER_REFS_REMOTES || - filter->kind == FILTER_REFS_TAGS) + filter->kind == FILTER_REFS_TAGS || + filter->kind == FILTER_REFS_CHANGES ) return filter->kind; return ref_kind_from_refname(refname); } @@ -2128,6 +2130,8 @@ int filter_refs(struct ref_array *array, struct ref_filter *filter, unsigned int ret = for_each_fullref_in("refs/remotes/", ref_filter_handler, &ref_cbdata, broken); else if (filter->kind == FILTER_REFS_TAGS) ret = for_each_fullref_in("refs/tags/", ref_filter_handler, &ref_cbdata, broken); + else if (filter->kind == FILTER_REFS_CHANGES) + ret = for_each_fullref_in("refs/metas/", ref_filter_handler, &ref_cbdata, broken); else if (filter->kind & FILTER_REFS_ALL) ret = for_each_fullref_in_pattern(filter, ref_filter_handler, &ref_cbdata, broken); if (!ret && (filter->kind & FILTER_REFS_DETACHED_HEAD)) diff --git a/ref-filter.h b/ref-filter.h index 85c8ebc3b9..19a3e57845 100644 --- a/ref-filter.h +++ b/ref-filter.h @@ -18,9 +18,10 @@ #define FILTER_REFS_BRANCHES 0x0004 #define FILTER_REFS_REMOTES 0x0008 #define FILTER_REFS_OTHERS 0x0010 -#define FILTER_REFS_ALL (FILTER_REFS_TAGS | FILTER_REFS_BRANCHES | \ - FILTER_REFS_REMOTES | FILTER_REFS_OTHERS) #define FILTER_REFS_DETACHED_HEAD 0x0020 +#define FILTER_REFS_CHANGES 0X0040 +#define FILTER_REFS_ALL (FILTER_REFS_TAGS | FILTER_REFS_BRANCHES | \ + FILTER_REFS_REMOTES | FILTER_REFS_CHANGES | FILTER_REFS_OTHERS) #define FILTER_REFS_KIND_MASK (FILTER_REFS_ALL | FILTER_REFS_DETACHED_HEAD) struct atom_value; From patchwork Mon Jan 21 22:32:12 2019 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Stefan Xenos X-Patchwork-Id: 10774625 Return-Path: Received: from mail.wl.linuxfoundation.org (pdx-wl-mail.web.codeaurora.org [172.30.200.125]) by pdx-korg-patchwork-2.web.codeaurora.org (Postfix) with ESMTP id 3CEB713B5 for ; Mon, 21 Jan 2019 22:32:36 +0000 (UTC) Received: from mail.wl.linuxfoundation.org (localhost [127.0.0.1]) by mail.wl.linuxfoundation.org (Postfix) with ESMTP id 2FCDC2AEAA for ; Mon, 21 Jan 2019 22:32:36 +0000 (UTC) Received: by mail.wl.linuxfoundation.org (Postfix, from userid 486) id 2E6092AECB; Mon, 21 Jan 2019 22:32:36 +0000 (UTC) X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on pdx-wl-mail.web.codeaurora.org X-Spam-Level: X-Spam-Status: No, score=-15.5 required=2.0 tests=BAYES_00,DKIM_SIGNED, DKIM_VALID,DKIM_VALID_AU,MAILING_LIST_MULTI,RCVD_IN_DNSWL_HI, USER_IN_DEF_DKIM_WL autolearn=ham version=3.3.1 Received: from vger.kernel.org (vger.kernel.org [209.132.180.67]) by mail.wl.linuxfoundation.org (Postfix) with ESMTP id B9EF62AEAA for ; Mon, 21 Jan 2019 22:32:34 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1727496AbfAUWcc (ORCPT ); Mon, 21 Jan 2019 17:32:32 -0500 Received: from mail-yw1-f73.google.com ([209.85.161.73]:51199 "EHLO mail-yw1-f73.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1726541AbfAUWcb (ORCPT ); Mon, 21 Jan 2019 17:32:31 -0500 Received: by mail-yw1-f73.google.com with SMTP id b8so11823731ywb.17 for ; Mon, 21 Jan 2019 14:32:30 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=20161025; h=date:in-reply-to:message-id:mime-version:references:subject:from:to :cc; bh=nUQRE+j96MBpSIBvix+R5v5Qd59WfjWobTxdWQPLYlI=; b=DbpB1hm9EFh1qyOjMaCKC+HjKhv91n97En5FvFLJeN1o35Lf9PvdNZNY/91sVrb15i maedJ9KOTgUxmCwR78DTFMuNu3kulPdvMiwKGnD/cU0Wh3MYK3eLVziIBf0l5/7aYbvV mO7X6I8P0qtbdQaInQ5cGXSYYyUKRn6QDDgu7DqbOSIXL58WYd8LSQoDzRtaG3bhptd0 BkJSAadgmzJTx93/EwJbvZdbDG1yWUnJ5g46HiYCIagvkZsylaCE+hELZ8XltSiF2Z4a GxdBgazm2sNLP72VMqJfL12RqgWM9N8SXlWg1ZCgAY5L24XKth3uzxvZDG2ttDJ4zXCE /beA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:date:in-reply-to:message-id:mime-version :references:subject:from:to:cc; bh=nUQRE+j96MBpSIBvix+R5v5Qd59WfjWobTxdWQPLYlI=; b=b9msMH3/HeOzVwYkDkHqighhfEXAQPyB6NvHbGtcoXdfSXerg54XFsMRjYMKarUF93 ToOBznnBZK4ekMI9vS/j6+JQBxJTP57Vr1aWcGyxvDdI+LfWwCYM58nh0CFwR5HTOiTR tKPrFmrMAAC2w2/UMn1uBxrShUEqljWprZBGfaWjDwUOUSQkrU0UPAcwJnsXEpBn3eG5 gERf0r6q8aBOEUKjaAsykeY9XhraI4iZUaNWin6A9/N/4aWH6BSnutdw4O402voU7I2Y vSmfLNd8aOImyhommtsRbs/wckhFibYpT86xQF93a7DNoOWH/KvnjsWnQbb+DZyVrOcg Qu9A== X-Gm-Message-State: AJcUukfjSFE4T2IV4KXWA1upK2FnhlP/i0BVOGjnVeHz/I6tl6XaufFJ 5oCrN65kD1K70bWG/cVvIbCyCFJiJqAuaMmIWOQnuMUBSoMJYvIFbDZ0innH25TGHs+/7HTIQdL +hFN6TTP5PgTPsJgcMotmESlmtPUMUGHnElNYRzMhmCrLKoKj5Z7eG6zzpA== X-Google-Smtp-Source: ALg8bN7Hc/UKqYyaa240LTJ8Dd6QXEkfv83bDRqNE28fv5ncF7eHI7IXlBz0BjL2TDiYAQAx+ozl5jpdWSA= X-Received: by 2002:a25:245:: with SMTP id 66mr9379357ybc.39.1548109950356; Mon, 21 Jan 2019 14:32:30 -0800 (PST) Date: Mon, 21 Jan 2019 14:32:12 -0800 In-Reply-To: <20190121223216.66659-1-sxenos@google.com> Message-Id: <20190121223216.66659-4-sxenos@google.com> Mime-Version: 1.0 References: <20190121223216.66659-1-sxenos@google.com> X-Mailer: git-send-email 2.20.1.321.g9e740568ce-goog Subject: [PATCH 4/8] evolve: Add support for parsing metacommits From: sxenos@google.com To: git@vger.kernel.org Cc: Stefan Xenos Sender: git-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org X-Virus-Scanned: ClamAV using ClamSMTP From: Stefan Xenos This patch adds the get_metacommit_content method, which can classify commits as either metacommits or normal commits, determine whether they are abandoned, and extract the content commit's object id from the metacommit. --- Makefile | 1 + metacommit-parser.c | 87 +++++++++++++++++++++++++++++++++++++++++++++ metacommit-parser.h | 16 +++++++++ 3 files changed, 104 insertions(+) create mode 100644 metacommit-parser.c create mode 100644 metacommit-parser.h diff --git a/Makefile b/Makefile index 1a44c811aa..7ffc383f2b 100644 --- a/Makefile +++ b/Makefile @@ -919,6 +919,7 @@ LIB_OBJS += merge.o LIB_OBJS += merge-blobs.o LIB_OBJS += merge-recursive.o LIB_OBJS += mergesort.o +LIB_OBJS += metacommit-parser.o LIB_OBJS += midx.o LIB_OBJS += name-hash.o LIB_OBJS += negotiator/default.o diff --git a/metacommit-parser.c b/metacommit-parser.c new file mode 100644 index 0000000000..5013a108a3 --- /dev/null +++ b/metacommit-parser.c @@ -0,0 +1,87 @@ +#include "cache.h" +#include "metacommit-parser.h" +#include "commit.h" + +/* + * Search the commit buffer for a line starting with the given key. Unlike + * find_commit_header, this also searches the commit message body. + */ +static const char *find_key(const char *msg, const char *key, size_t *out_len) +{ + int key_len = strlen(key); + const char *line = msg; + + while (line) { + const char *eol = strchrnul(line, '\n'); + + if (eol - line > key_len && + !strncmp(line, key, key_len) && + line[key_len] == ' ') { + *out_len = eol - line - key_len - 1; + return line + key_len + 1; + } + line = *eol ? eol + 1 : NULL; + } + return NULL; +} + +static struct commit *get_commit_by_index(struct commit_list *to_search, int index) +{ + while (to_search && index) { + to_search = to_search->next; + --index; + } + + return to_search->item; +} + +/* + * Writes the content parent's object id to "content". + * Returns the metacommit type. See the METACOMMIT_TYPE_* constants. + */ +int get_metacommit_content( + struct commit *commit, struct object_id *content) +{ + const char *buffer = get_commit_buffer(commit, NULL); + size_t parent_types_size; + const char *parent_types = find_key(buffer, "parent-type", + &parent_types_size); + const char *end; + int index = 0; + int ret; + struct commit *content_parent; + + if (!parent_types) { + return METACOMMIT_TYPE_NONE; + } + + end = &(parent_types[parent_types_size]); + + while (1) { + char next = *parent_types; + if (next == ' ') { + index++; + } + if (next == 'c') { + ret = METACOMMIT_TYPE_NORMAL; + break; + } + if (next == 'a') { + ret = METACOMMIT_TYPE_ABANDONED; + break; + } + parent_types++; + if (parent_types >= end) { + return METACOMMIT_TYPE_NONE; + } + } + + content_parent = get_commit_by_index(commit->parents, index); + + if (!content_parent) { + return METACOMMIT_TYPE_NONE; + } + + oidcpy(content, &(content_parent->object.oid)); + return ret; +} diff --git a/metacommit-parser.h b/metacommit-parser.h new file mode 100644 index 0000000000..e546f5a7e7 --- /dev/null +++ b/metacommit-parser.h @@ -0,0 +1,16 @@ +#ifndef METACOMMIT_PARSER_H +#define METACOMMIT_PARSER_H + +// Indicates a normal commit (non-metacommit) +#define METACOMMIT_TYPE_NONE 0 +// Indicates a metacommit with normal content (non-abandoned) +#define METACOMMIT_TYPE_NORMAL 1 +// Indicates a metacommit with abandoned content +#define METACOMMIT_TYPE_ABANDONED 2 + +struct commit; + +extern int get_metacommit_content( + struct commit *commit, struct object_id *content); + +#endif From patchwork Mon Jan 21 22:32:13 2019 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Stefan Xenos X-Patchwork-Id: 10774629 Return-Path: Received: from mail.wl.linuxfoundation.org (pdx-wl-mail.web.codeaurora.org [172.30.200.125]) by pdx-korg-patchwork-2.web.codeaurora.org (Postfix) with ESMTP id 83AEA13B5 for ; Mon, 21 Jan 2019 22:32:39 +0000 (UTC) Received: from mail.wl.linuxfoundation.org (localhost [127.0.0.1]) by mail.wl.linuxfoundation.org (Postfix) with ESMTP id 750C62AECB for ; Mon, 21 Jan 2019 22:32:39 +0000 (UTC) Received: by mail.wl.linuxfoundation.org (Postfix, from userid 486) id 737682AED3; Mon, 21 Jan 2019 22:32:39 +0000 (UTC) X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on pdx-wl-mail.web.codeaurora.org X-Spam-Level: X-Spam-Status: No, score=-15.5 required=2.0 tests=BAYES_00,DKIM_SIGNED, DKIM_VALID,DKIM_VALID_AU,MAILING_LIST_MULTI,RCVD_IN_DNSWL_HI, USER_IN_DEF_DKIM_WL autolearn=ham version=3.3.1 Received: from vger.kernel.org (vger.kernel.org [209.132.180.67]) by mail.wl.linuxfoundation.org (Postfix) with ESMTP id 866D62AED7 for ; Mon, 21 Jan 2019 22:32:38 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1727599AbfAUWce (ORCPT ); Mon, 21 Jan 2019 17:32:34 -0500 Received: from mail-vs1-f73.google.com ([209.85.217.73]:40608 "EHLO mail-vs1-f73.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1726541AbfAUWce (ORCPT ); Mon, 21 Jan 2019 17:32:34 -0500 Received: by mail-vs1-f73.google.com with SMTP id e124so10815613vsc.7 for ; Mon, 21 Jan 2019 14:32:33 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=20161025; h=date:in-reply-to:message-id:mime-version:references:subject:from:to :cc; bh=CgNIfDsnmnto2migVa7Rq85pfLE5jKpjldBPkkul2o4=; b=q1XTeN7QpqHehOFL0G9liVGVQO9tJYMJiMewssPZQz0Flq0iopM+nKhJMHRbkV95XW J8WWV8RDsH5UGnQSlOrzp0cBJDYKPE6WdskATjBqxzOT7nILe7o13nbd3++lt7MaKspt 5yD7rJfNUPA8V7vDIW76KVtWkJSbm51ZAcZsuGkFlX2C3Yfi4u3Q0TfMSm/+QnH3ieUK J4zIAANTRsLyX805JBjAcyUUebycZ8La72Z/vEv9yrR+knSN6k7+yNHtg9AIGyRCPrw0 Z+Z8wEhNz5uRB+GwH4p6xGaIZc8kr/KOx/1+KPNCgtfomln6SP0jjMFhGCbl0Ye1k5Xw nlEw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:date:in-reply-to:message-id:mime-version :references:subject:from:to:cc; bh=CgNIfDsnmnto2migVa7Rq85pfLE5jKpjldBPkkul2o4=; b=c5DYLQSDFz7RMmg32M62EUIJ5JdMYzFFvYvtbhMP8ZrVP6CZmj+s0kuDV+BpVRf1N+ VUaZKSV27OE4mRHJBcQIR8jXhJAHf5ulKOYcgi/PzMGIIJoq5CgoHMHQ59y7/3/weeXx RYXTGaYXRb0ECmRTesjZivt1dgmiL/tvLWMA6D8stZU95q9iME8ETFbY3mkqXEARr7PK bekaOACz6Rt5/EmYliStZy8Gw4F16AKcJUIaXR8Cg4Cu5/xVFgIwzJdXatniy0mWMlG6 QSTIh4W9eCFe7BhoSd8mdVQVy6SybL/SBmD8q+YmguxnY9CDCzpGb7bw5rVopg2j+v3A vz/w== X-Gm-Message-State: AJcUukfVDESBMP4/oA9ICPueB2yMXJmgokSfa8KuIkOBdDYH6D6P6dLu OheSwoLDkzhwLXkCuUyBfPmu0iV3+PRcXyhhqJ077Ff+Z3k79KyA9v5LxUgFfgKewOhhsL/DWXE nOFdFkcQpn9Ujq6jV8MLnj0K115f1E6C59QKo8gPzlxGMx6PbDdD0nrvAMQ== X-Google-Smtp-Source: ALg8bN5moaA90Bi6gXSMGoSJeahj6wuMXmfv5i7WQ+z469GnykEZqCC9GuBBOnr+uu3agh9hgRPDUBeDVTY= X-Received: by 2002:a67:e99a:: with SMTP id b26mr24675214vso.10.1548109952969; Mon, 21 Jan 2019 14:32:32 -0800 (PST) Date: Mon, 21 Jan 2019 14:32:13 -0800 In-Reply-To: <20190121223216.66659-1-sxenos@google.com> Message-Id: <20190121223216.66659-5-sxenos@google.com> Mime-Version: 1.0 References: <20190121223216.66659-1-sxenos@google.com> X-Mailer: git-send-email 2.20.1.321.g9e740568ce-goog Subject: [PATCH 5/8] evolve: Add the change-table structure From: sxenos@google.com To: git@vger.kernel.org Cc: Stefan Xenos Sender: git-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org X-Virus-Scanned: ClamAV using ClamSMTP From: Stefan Xenos A change table stores a list of changes, and supports efficient lookup from a commit hash to the list of changes that reference that commit directly. It can be used to look up content commits or metacommits at the head of a change, but does not support lookup of commits referenced as part of the commit history. --- Makefile | 1 + change-table.c | 207 +++++++++++++++++++++++++++++++++++++++++++++++++ change-table.h | 138 +++++++++++++++++++++++++++++++++ 3 files changed, 346 insertions(+) create mode 100644 change-table.c create mode 100644 change-table.h diff --git a/Makefile b/Makefile index 7ffc383f2b..09cfd3ef1b 100644 --- a/Makefile +++ b/Makefile @@ -844,6 +844,7 @@ LIB_OBJS += branch.o LIB_OBJS += bulk-checkin.o LIB_OBJS += bundle.o LIB_OBJS += cache-tree.o +LIB_OBJS += change-table.o LIB_OBJS += chdir-notify.o LIB_OBJS += checkout.o LIB_OBJS += color.o diff --git a/change-table.c b/change-table.c new file mode 100644 index 0000000000..6daff5f58c --- /dev/null +++ b/change-table.c @@ -0,0 +1,207 @@ +#include "cache.h" +#include "change-table.h" +#include "commit.h" +#include "ref-filter.h" +#include "metacommit-parser.h" + +void change_table_init(struct change_table *to_initialize) +{ + memset(to_initialize, 0, sizeof(*to_initialize)); + mem_pool_init(&(to_initialize->memory_pool), 0); + to_initialize->memory_pool->block_alloc = 4*1024 - sizeof(struct mp_block); + oidmap_init(&(to_initialize->oid_to_metadata_index), 0); + string_list_init(&(to_initialize->refname_to_change_head), 1); +} + +static void change_list_clear(struct change_list *to_clear) { + string_list_clear(&to_clear->additional_refnames, 0); +} + +static void commit_change_list_entry_clear( + struct commit_change_list_entry *to_clear) { + change_list_clear(&(to_clear->changes)); +} + +static void change_head_array_clear(struct change_head_array *to_clear) +{ + FREE_AND_NULL(to_clear->array); +} + +void change_table_clear(struct change_table *to_clear) +{ + struct oidmap_iter iter; + struct commit_change_list_entry *next; + for (next = oidmap_iter_first(&to_clear->oid_to_metadata_index, &iter); + next; + next = oidmap_iter_next(&iter)) { + + commit_change_list_entry_clear(next); + } + + oidmap_free(&to_clear->oid_to_metadata_index, 0); + string_list_clear(&(to_clear->refname_to_change_head), 0); + change_head_array_clear(&to_clear->heads); + mem_pool_discard(to_clear->memory_pool, 0); +} + +/* + * Appends a new, empty, change_head struct to the end of the given array. + * Returns the index of the newly-added struct. + */ +static int change_head_array_append(struct change_head_array *to_add) +{ + int index = to_add->nr++; + struct change_head *new_head; + ALLOC_GROW(to_add->array, to_add->nr, to_add->alloc); + new_head = &(to_add->array[index]); + memset(new_head, 0, sizeof(*new_head)); + return index; +} + +static void add_head_to_commit(struct change_table *to_modify, + const struct object_id *to_add, const char *refname) +{ + struct commit_change_list_entry *entry; + + // Note: the indices in the map are 1-based. 0 is used to indicate a missing + // element. + entry = oidmap_get(&(to_modify->oid_to_metadata_index), to_add); + if (!entry) { + entry = mem_pool_calloc(to_modify->memory_pool, 1, + sizeof(*entry)); + oidcpy(&entry->entry.oid, to_add); + oidmap_put(&(to_modify->oid_to_metadata_index), entry); + string_list_init(&(entry->changes.additional_refnames), 0); + } + + if (entry->changes.first_refname == NULL) { + entry->changes.first_refname = refname; + } else { + string_list_insert(&entry->changes.additional_refnames, refname); + } +} + +void change_table_add(struct change_table *to_modify, const char *refname, + struct commit *to_add) +{ + struct change_head *new_head; + struct string_list_item *new_item; + long index; + int metacommit_type; + + index = change_head_array_append(&to_modify->heads); + new_head = &(to_modify->heads.array[index]); + + oidcpy(&new_head->head, &(to_add->object.oid)); + + metacommit_type = get_metacommit_content(to_add, &new_head->content); + if (metacommit_type == METACOMMIT_TYPE_NONE) { + oidcpy(&new_head->content, &(to_add->object.oid)); + } + new_head->abandoned = (metacommit_type == METACOMMIT_TYPE_ABANDONED); + new_head->remote = starts_with(refname, "refs/remote/"); + new_head->hidden = starts_with(refname, "refs/hiddenmetas/"); + + new_item = string_list_insert(&to_modify->refname_to_change_head, refname); + new_item->util = (void*)index; + // Use pointers to the copy of the string we're retaining locally + refname = new_item->string; + + if (!oideq(&new_head->content, &new_head->head)) { + add_head_to_commit(to_modify, &(new_head->content), refname); + } + add_head_to_commit(to_modify, &(new_head->head), refname); +} + +void change_table_add_all_visible(struct change_table *to_modify, + struct repository* repo) +{ + struct ref_filter filter; + const char *name_patterns[] = {NULL}; + memset(&filter, 0, sizeof(filter)); + filter.kind = FILTER_REFS_CHANGES; + filter.name_patterns = name_patterns; + + change_table_add_matching_filter(to_modify, repo, &filter); +} + +void change_table_add_matching_filter(struct change_table *to_modify, + struct repository* repo, struct ref_filter *filter) +{ + struct ref_array matching_refs; + int i; + + memset(&matching_refs, 0, sizeof(matching_refs)); + filter_refs(&matching_refs, filter, filter->kind); + + // Determine the object id for the latest content commit for each change. + // Fetch the commit at the head of each change ref. If it's a normal commit, + // that's the commit we want. If it's a metacommit, locate its content parent + // and use that. + + for (i = 0; i < matching_refs.nr; i++) { + struct ref_array_item *item = matching_refs.items[i]; + struct commit *commit = item->commit; + + commit = lookup_commit_reference_gently(repo, &(item->objectname), 1); + + if (commit != NULL) { + change_table_add(to_modify, item->refname, commit); + } + } + + ref_array_clear(&matching_refs); +} + +static int return_true_callback(const char *refname, void *cb_data) +{ + return 1; +} + +int change_table_has_change_referencing(struct change_table *changes, + const struct object_id *referenced_commit_id) +{ + return for_each_change_referencing(changes, referenced_commit_id, + return_true_callback, NULL); +} + +int for_each_change_referencing(struct change_table *table, + const struct object_id *referenced_commit_id, each_change_fn fn, void *cb_data) +{ + const struct change_list *changes; + int i; + int retvalue; + struct commit_change_list_entry *entry; + + entry = oidmap_get(&table->oid_to_metadata_index, + referenced_commit_id); + // If this commit isn't referenced by any changes, it won't be in the map + if (!entry) { + return 0; + } + changes = &(entry->changes); + if (changes->first_refname == NULL) { + return 0; + } + retvalue = fn(changes->first_refname, cb_data); + for (i = 0; retvalue == 0 && i < changes->additional_refnames.nr; i++) { + retvalue = fn(changes->additional_refnames.items[i].string, cb_data); + } + return retvalue; +} + +struct change_head* get_change_head(struct change_table *heads, + const char* refname) +{ + struct string_list_item *item = string_list_lookup( + &heads->refname_to_change_head, refname); + long index; + + if (!item) { + return NULL; + } + + index = (long)item->util; + return &(heads->heads.array[index]); +} + diff --git a/change-table.h b/change-table.h new file mode 100644 index 0000000000..7307ae86d0 --- /dev/null +++ b/change-table.h @@ -0,0 +1,138 @@ +#ifndef CHANGE_TABLE_H +#define CHANGE_TABLE_H + +#include "oidmap.h" + +struct commit; +struct ref_filter; + +/* + * This struct holds a list of change refs. The first element is stored inline, + * to optimize for small lists. + */ +struct change_list { + /* Ref name for the first change in the list, or null if none. + * + * This field is private. Use for_each_change_in to read. + */ + const char* first_refname; + /* List of additional change refs. Note that this is empty if the list + * contains 0 or 1 elements. + * + * This field is private. Use for_each_change_in to read. + */ + struct string_list additional_refnames; +}; + +/* + * Holds information about the head of a single change. + */ +struct change_head { + /* + * The location pointed to by the head of the change. May be a commit or a + * metacommit. + */ + struct object_id head; + /* + * The content commit for the latest commit in the change. Always points to a + * real commit, never a metacommit. + */ + struct object_id content; + /* + * Abandoned: indicates that the content commit should be removed from the + * history. + * + * Hidden: indicates that the change is an inactive change from the + * hiddenmetas namespace. Such changes will be hidden from the user by + * default. + * + * Deleted: indicates that the change has been removed from the repository. + * That is the ref was deleted since the time this struct was created. Such + * entries should be ignored. + */ + int abandoned:1, + hidden:1, + remote:1, + deleted:1; +}; + +/* + * An array of change_head. + */ +struct change_head_array { + struct change_head* array; + int nr; + int alloc; +}; + +/* + * Holds the list of change refs whose content points to a particular content + * commit. + */ +struct commit_change_list_entry { + struct oidmap_entry entry; + struct change_list changes; +}; + +/* + * Holds information about the heads of each change, and permits effecient + * lookup from a commit to the changes that reference it directly. + * + * All fields should be considered private. Use the change_table functions + * to interact with this struct. + */ +struct change_table { + /** + * Memory pool for the objects allocated by the change table. + */ + struct mem_pool *memory_pool; + /* Map object_id to commit_change_list_entry structs. */ + struct oidmap oid_to_metadata_index; + /* List of ref names. The util value is an int index into change_metadata + * array. + */ + struct string_list refname_to_change_head; + /* change_head structures for each head */ + struct change_head_array heads; +}; + +extern void change_table_init(struct change_table *to_initialize); +extern void change_table_clear(struct change_table *to_clear); + +/* Adds the given change head to the change_table struct */ +extern void change_table_add(struct change_table *to_modify, + const char *refname, struct commit *target); + +/* Adds the non-hidden local changes to the given change_table struct. + */ +extern void change_table_add_all_visible(struct change_table *to_modify, + struct repository *repo); + +/* + * Adds all changes matching the given ref filter to the given change_table + * struct. + */ +extern void change_table_add_matching_filter(struct change_table *to_modify, + struct repository* repo, struct ref_filter *filter); + +typedef int each_change_fn(const char *refname, void *cb_data); + +extern int change_table_has_change_referencing(struct change_table *changes, + const struct object_id *referenced_commit_id); + +/* Iterates over all changes that reference the given commit. For metacommits, + * this is the list of changes that point directly to that metacommit. + * For normal commits, this is the list of changes that have this commit as + * their latest content. + */ +extern int for_each_change_referencing(struct change_table *heads, + const struct object_id *referenced_commit_id, each_change_fn fn, void *cb_data); + +/** + * Returns the change head for the given refname. Returns NULL if no such change + * exists. + */ +extern struct change_head* get_change_head(struct change_table *heads, + const char* refname); + +#endif From patchwork Mon Jan 21 22:32:14 2019 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Stefan Xenos X-Patchwork-Id: 10774631 Return-Path: Received: from mail.wl.linuxfoundation.org (pdx-wl-mail.web.codeaurora.org [172.30.200.125]) by pdx-korg-patchwork-2.web.codeaurora.org (Postfix) with ESMTP id 6592F13BF for ; Mon, 21 Jan 2019 22:32:40 +0000 (UTC) Received: from mail.wl.linuxfoundation.org (localhost [127.0.0.1]) by mail.wl.linuxfoundation.org (Postfix) with ESMTP id 537AE2AEDB for ; Mon, 21 Jan 2019 22:32:40 +0000 (UTC) Received: by mail.wl.linuxfoundation.org (Postfix, from userid 486) id 47E102AED5; Mon, 21 Jan 2019 22:32:40 +0000 (UTC) X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on pdx-wl-mail.web.codeaurora.org X-Spam-Level: X-Spam-Status: No, score=-15.5 required=2.0 tests=BAYES_00,DKIM_SIGNED, DKIM_VALID,DKIM_VALID_AU,MAILING_LIST_MULTI,RCVD_IN_DNSWL_HI, USER_IN_DEF_DKIM_WL autolearn=ham version=3.3.1 Received: from vger.kernel.org (vger.kernel.org [209.132.180.67]) by mail.wl.linuxfoundation.org (Postfix) with ESMTP id BB4822AEB8 for ; Mon, 21 Jan 2019 22:32:38 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1727688AbfAUWch (ORCPT ); Mon, 21 Jan 2019 17:32:37 -0500 Received: from mail-pg1-f201.google.com ([209.85.215.201]:40642 "EHLO mail-pg1-f201.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1726541AbfAUWcg (ORCPT ); Mon, 21 Jan 2019 17:32:36 -0500 Received: by mail-pg1-f201.google.com with SMTP id r13so15006933pgb.7 for ; Mon, 21 Jan 2019 14:32:35 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=20161025; h=date:in-reply-to:message-id:mime-version:references:subject:from:to :cc; bh=mH0FxEYstzKqo5Z4qbFbpCwTsmU0QUpF5NRP8ax8y7k=; b=RvOol7aFm8qxouwFslbC05nxm0YitOlqgGWnTLTqqS1aSaIYLQ6LSqa3IbyXigXdhd ieslbOHl4rh61QgLsFeccsvuzpRiMNkGWZemZTUsXuCWBpdA2oC8PIpehz5qSc7mmTp/ npPA+y8Ju8F5bF9hpsh+mHcF/FTgTJ/zo0DIkirIAofskAfIXabXP/v9wy8+Mnx5WCvH 9bnuYhPLO9rishEzFFnT5mM/VYHrWkP2XUJJhY/33i1POFOMMnvEv7Wybqbt//caTnlP wMalRZt8sE4gkPvHWp5H6FNQxUPoXMrbnuZ/cEgalEIRFV7Mtwk8wJE10rZkxzoGTJYp 4EIw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:date:in-reply-to:message-id:mime-version :references:subject:from:to:cc; bh=mH0FxEYstzKqo5Z4qbFbpCwTsmU0QUpF5NRP8ax8y7k=; b=S7Cx6KprTmIQiAm6+p9p93h1i4fsisUEMiIHORhFxBGLb5SdOdI284H8tyRiSwRL+s bcuK6RGB+5zkVVHkIsJywb1XdV8KhiGp2L8OQJ9UlHKEo8RU18CaDpHJTUxui3WaIFkW MVXLILN5x95/lmKyks+iI/ftAGXRiSs7dhVWKpCHl6xvP4TxCxkUmzeQylnPPt7nQnI0 AbsEi2Ruinmo/VTioMBlnQEYmVuajYKqyNTQMTK3AXAxTsIElQ2MgXDHs2NeDFQcWBvk cnVQVrlvOKxObNDn0rUPMttESMsD2jb+EZZBcFe3YjveZchl6iZNhbM0/lHMBybKdseK 4hGA== X-Gm-Message-State: AJcUukfj/mmj8YzC7hHvKFam3MkBhsVRgZYnjyDOcEyr8Dk/sHUWBav7 vhesfZftfDy/CWOL3PiK8HxCeEfUmWtrKmWwulmzydHcArzUi4KPnk81IKkbO9qDZ/PI2VQkS5/ P1LXsbsiXLccwtyahhW1Zkdh9GZCw50XOt+iz2CB1kVRZOGaU2FwjbrTE+Q== X-Google-Smtp-Source: ALg8bN5dWM+wfiq6U7MoVJs0rI2ozU/g7H8XsgC3B/FLELvvaKOjs5aHI+Gutrl73A8awxbSJkLP5JJsAHI= X-Received: by 2002:a62:9f9c:: with SMTP id v28mr7580556pfk.72.1548109955114; Mon, 21 Jan 2019 14:32:35 -0800 (PST) Date: Mon, 21 Jan 2019 14:32:14 -0800 In-Reply-To: <20190121223216.66659-1-sxenos@google.com> Message-Id: <20190121223216.66659-6-sxenos@google.com> Mime-Version: 1.0 References: <20190121223216.66659-1-sxenos@google.com> X-Mailer: git-send-email 2.20.1.321.g9e740568ce-goog Subject: [PATCH 6/8] evolve: Add support for writing metacommits From: sxenos@google.com To: git@vger.kernel.org Cc: Stefan Xenos Sender: git-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org X-Virus-Scanned: ClamAV using ClamSMTP From: Stefan Xenos metacommit.c supports the creation of metacommits and adds the API needed to create and update changes. Create the "modify_change" function that can be called from modification commands like "rebase" and "git amend" to record obsolescences in the change graph. Create the "record_metacommit" function for recording more complicated commit relationships in the commit graph. Create the "write_metacommit" function for low-level creation of metacommits. --- Makefile | 1 + metacommit.c | 370 +++++++++++++++++++++++++++++++++++++++++++++++++++ metacommit.h | 39 ++++++ 3 files changed, 410 insertions(+) create mode 100644 metacommit.c create mode 100644 metacommit.h diff --git a/Makefile b/Makefile index 09cfd3ef1b..a6be1780c5 100644 --- a/Makefile +++ b/Makefile @@ -920,6 +920,7 @@ LIB_OBJS += merge.o LIB_OBJS += merge-blobs.o LIB_OBJS += merge-recursive.o LIB_OBJS += mergesort.o +LIB_OBJS += metacommit.o LIB_OBJS += metacommit-parser.o LIB_OBJS += midx.o LIB_OBJS += name-hash.o diff --git a/metacommit.c b/metacommit.c new file mode 100644 index 0000000000..705e54f3aa --- /dev/null +++ b/metacommit.c @@ -0,0 +1,370 @@ +#include "cache.h" +#include "metacommit.h" +#include "commit.h" +#include "change-table.h" +#include "refs.h" + +void init_metacommit_data(struct metacommit_data *state) +{ + memset(state, 0, sizeof(*state)); +} + +void clear_metacommit_data(struct metacommit_data *state) +{ + oid_array_clear(&state->replace); + oid_array_clear(&state->origin); +} + +static void compute_default_change_name(struct commit *initial_commit, + struct strbuf* result) +{ + const char *buffer = get_commit_buffer(initial_commit, NULL); + const char *subject; + const char *eol; + int len; + find_commit_subject(buffer, &subject); + eol = strchrnul(subject, '\n'); + for (len = 0;subject < eol && len < 10; ++subject, ++len) { + char next = *subject; + if (isspace(next)) { + continue; + } + + strbuf_addch(result, next); + } +} + +/* + * Computes a change name for a change rooted at the given initial commit. Good + * change names should be memorable, unique, and easy to type. They are not + * required to match the commit comment. + */ +static void compute_change_name(struct commit *initial_commit, struct strbuf* result) +{ + struct strbuf default_name; + struct object_id unused; + + strbuf_init(&default_name, 0); + if (initial_commit) { + compute_default_change_name(initial_commit, &default_name); + } else { + strbuf_addstr(&default_name, "change"); + } + strbuf_addstr(result, "refs/metas/"); + strbuf_addstr(result, default_name.buf); + + // If there is already a change of this name, append a suffix + if (!read_ref(result->buf, &unused)) { + int suffix = 2; + int original_length = result->len; + + while (1) { + strbuf_addf(result, "%d", suffix); + if (read_ref(result->buf, &unused)) { + break; + } + strbuf_remove(result, original_length, result->len - original_length); + ++suffix; + } + } + + strbuf_release(&default_name); +} + +struct resolve_metacommit_callback_data +{ + struct change_table* active_changes; + struct string_list *changes; + struct oid_array *heads; +}; + +static int resolve_metacommit_callback(const char *refname, void *cb_data) +{ + struct resolve_metacommit_callback_data *data = (struct resolve_metacommit_callback_data *)cb_data; + struct change_head *chhead; + + chhead = get_change_head(data->active_changes, refname); + + if (data->changes) { + string_list_append(data->changes, refname)->util = &(chhead->head); + } + if (data->heads) { + oid_array_append(data->heads, &(chhead->head)); + } + + return 0; +} + +/* + * Produces the final form of a metacommit based on the current change refs. + */ +static void resolve_metacommit( + struct repository* repo, + struct change_table* active_changes, + const struct metacommit_data *to_resolve, + struct metacommit_data *resolved_output, + struct string_list *to_advance, + int allow_append) +{ + int i; + int len = to_resolve->replace.nr; + struct resolve_metacommit_callback_data cbdata; + int old_change_list_length = to_advance->nr; + struct commit* content; + + oidcpy(&resolved_output->content, &to_resolve->content); + + // First look for changes that point to any of the replacement edges in the + // metacommit. These will be the changes that get advanced by this metacommit. + resolved_output->abandoned = to_resolve->abandoned; + cbdata.active_changes = active_changes; + cbdata.changes = to_advance; + cbdata.heads = &(resolved_output->replace); + + if (allow_append) { + for (i = 0; i < len; i++) { + int old_number = resolved_output->replace.nr; + for_each_change_referencing(active_changes, &(to_resolve->replace.oid[i]), + resolve_metacommit_callback, &cbdata); + // If no changes were found, use the unresolved value + if (old_number == resolved_output->replace.nr) { + oid_array_append(&(resolved_output->replace), &(to_resolve->replace.oid[i])); + } + } + } + + cbdata.changes = NULL; + cbdata.heads = &(resolved_output->origin); + + len = to_resolve->origin.nr; + for (i = 0; i < len; i++) { + int old_number = resolved_output->origin.nr; + for_each_change_referencing(active_changes, &(to_resolve->origin.oid[i]), + resolve_metacommit_callback, &cbdata); + if (old_number == resolved_output->origin.nr) { + oid_array_append(&(resolved_output->origin), &(to_resolve->origin.oid[i])); + } + } + + // If no changes were advanced by this metacommit, we'll need to create a new + // one. + if (to_advance->nr == old_change_list_length) { + struct strbuf change_name; + + strbuf_init(&change_name, 80); + content = lookup_commit_reference_gently(repo, &(to_resolve->content), 1); + + compute_change_name(content, &change_name); + string_list_append(to_advance, change_name.buf); + strbuf_release(&change_name); + } +} + +static void lookup_commits( + struct repository *repo, + struct oid_array *to_lookup, + struct commit_list **result) +{ + int i = to_lookup->nr; + + while (--i >= 0) { + struct object_id *next = &(to_lookup->oid[i]); + struct commit *commit = lookup_commit_reference_gently(repo, next, 1); + commit_list_insert(commit, result); + } +} + +#define PARENT_TYPE_PREFIX "parent-type " + +/* + * Creates a new metacommit object with the given content. Writes the object + * id of the newly-created commit to result. + */ +int write_metacommit(struct repository *repo, struct metacommit_data *state, + struct object_id *result) +{ + struct commit_list *parents = NULL; + struct strbuf comment; + int i; + struct commit *content; + + strbuf_init(&comment, strlen(PARENT_TYPE_PREFIX) + + 1 + 2 * (state->origin.nr + state->replace.nr)); + lookup_commits(repo, &state->origin, &parents); + lookup_commits(repo, &state->replace, &parents); + content = lookup_commit_reference_gently(repo, &state->content, 1); + if (!content) { + strbuf_release(&comment); + free_commit_list(parents); + return -1; + } + commit_list_insert(content, &parents); + + strbuf_addstr(&comment, PARENT_TYPE_PREFIX); + strbuf_addstr(&comment, state->abandoned ? "a" : "c"); + for (i = 0; i < state->replace.nr; i++) { + strbuf_addstr(&comment, " r"); + } + + for (i = 0; i < state->origin.nr; i++) { + strbuf_addstr(&comment, " o"); + } + + // The parents list will be freed by this call + commit_tree(comment.buf, comment.len, repo->hash_algo->empty_tree, parents, + result, NULL, NULL); + + strbuf_release(&comment); + return 0; +} + +/* + * Returns true iff the given metacommit is abandoned, has one or more origin + * parents, or has one or more replacement parents. + */ +static int is_nontrivial_metacommit(struct metacommit_data *state) +{ + return state->replace.nr || state->origin.nr || state->abandoned; +} + +/* + * Records the relationships described by the given metacommit in the + * repository. + * + * If override_change is NULL (the default), an attempt will be made + * to append to existing changes wherever possible instead of creating new ones. + * If override_change is non-null, only the given change ref will be updated. + * + * options is a bitwise combination of the UPDATE_OPTION_* flags. + */ +int record_metacommit(struct repository *repo, + const struct metacommit_data *metacommit, + const char* override_change, int options, struct strbuf *err) +{ + static const char *msg = "updating change"; + struct metacommit_data resolved_metacommit; + struct string_list changes; + struct object_id commit_target; + struct ref_transaction *transaction = NULL; + struct object_id old_head_working; + const struct object_id *old_head; + struct change_table chtable; + int i; + int ret = 0; + int force = (options & UPDATE_OPTION_FORCE); + + init_metacommit_data(&resolved_metacommit); + string_list_init(&changes, 1); + + change_table_init(&chtable); + + change_table_add_all_visible(&chtable, repo); + + resolve_metacommit(repo, &chtable, metacommit, &resolved_metacommit, &changes, + (options & UPDATE_OPTION_NOAPPEND) == 0); + + if (override_change) { + old_head = &old_head_working; + string_list_clear(&changes, 0); + if (get_oid_committish(override_change, &old_head_working)) { + // ...then this is a newly-created change + old_head = &null_oid; + } else if (!force) { + if (!oid_array_contains_nondestructive(&(resolved_metacommit.replace), + &old_head_working)) { + // Attempted non-fast-forward change + strbuf_addf(err, _("non-fast-forward update to '%s'"), + override_change); + ret = -1; + goto cleanup; + } + } + // The expected "current" head of the change is stored in the util pointer + string_list_append(&changes, override_change)->util = (void*)old_head; + } + + if (is_nontrivial_metacommit(&resolved_metacommit)) { + // If there are any origin or replacement parents, create a new metacommit + // object. + if (write_metacommit(repo, &resolved_metacommit, &commit_target) < 0) { + ret = -1; + goto cleanup; + } + } else { + // If the metacommit would only contain a content commit, point to the + // commit itself rather than creating a trivial metacommit. + oidcpy(&commit_target, &(resolved_metacommit.content)); + } + + // If a change already exists with this target and we're not forcing an + // update to some specific override_change && change, there's nothing to do. + if (!override_change + && change_table_has_change_referencing(&chtable, &commit_target)) { + // Not an error + goto cleanup; + } + + transaction = ref_transaction_begin(err); + + // Update the refs for each affected change + if (!transaction) { + ret = -1; + } else { + for (i = 0; i < changes.nr; i++) { + struct string_list_item *it = &(changes.items[i]); + + // The expected current head of the change is stored in the util pointer. + // It is null if the change should be newly-created. + if (it->util) { + if (ref_transaction_update(transaction, it->string, &commit_target, + force ? NULL : it->util, 0, msg, err)) { + + ret = -1; + } + } else { + if (ref_transaction_create(transaction, it->string, + &commit_target, 0, msg, err)) { + + ret = -1; + } + } + } + + if (!ret) { + if (ref_transaction_commit(transaction, err)) { + ret = -1; + } + } + } + +cleanup: + ref_transaction_free(transaction); + string_list_clear(&changes, 0); + clear_metacommit_data(&resolved_metacommit); + change_table_clear(&chtable); + return ret; +} + +/* + * Should be invoked after a command that has "modify" semantics - commands that + * create a new commit based on an old commit and treat the new one as a + * replacement for the old one. This method records the replacement in the + * change graph, such that a future evolve operation will rebase children of + * the old commit onto the new commit. + */ +void modify_change( + struct repository *repo, + const struct object_id *old_commit, + const struct object_id *new_commit, + struct strbuf *err) +{ + struct metacommit_data metacommit; + + init_metacommit_data(&metacommit); + oidcpy(&(metacommit.content), new_commit); + oid_array_append(&(metacommit.replace), old_commit); + + record_metacommit(repo, &metacommit, NULL, 0, err); + + clear_metacommit_data(&metacommit); +} diff --git a/metacommit.h b/metacommit.h new file mode 100644 index 0000000000..1d4be9cdfb --- /dev/null +++ b/metacommit.h @@ -0,0 +1,39 @@ +#ifndef METACOMMIT_H +#define METACOMMIT_H + +// If specified, non-fast-forward changes are permitted. +#define UPDATE_OPTION_FORCE 0x0001 +// If specified, no attempt will be made to append to existing changes. +// Normally, if a metacommit points to a commit in its replace or origin +// list and an existing change points to that same commit as its content, the +// new metacommit will attempt to append to that same change. This may replace +// the commit parent with one or more metacommits from the head of the appended +// changes. This option disables this behavior, and will always create a new +// change rather than reusing existing changes. +#define UPDATE_OPTION_NOAPPEND 0x0002 + +// Metacommit Data + +struct metacommit_data { + struct object_id content; + struct oid_array replace; + struct oid_array origin; + int abandoned; +}; + +extern void init_metacommit_data(struct metacommit_data *state); + +extern void clear_metacommit_data(struct metacommit_data *state); + +extern int record_metacommit(struct repository *repo, + const struct metacommit_data *metacommit, + const char* override_change, int options, struct strbuf *err); + +extern void modify_change(struct repository *repo, + const struct object_id *old_commit, const struct object_id *new_commit, + struct strbuf *err); + +extern int write_metacommit(struct repository *repo, struct metacommit_data *state, + struct object_id *result); + +#endif From patchwork Mon Jan 21 22:32:15 2019 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Stefan Xenos X-Patchwork-Id: 10774633 Return-Path: Received: from mail.wl.linuxfoundation.org (pdx-wl-mail.web.codeaurora.org [172.30.200.125]) by pdx-korg-patchwork-2.web.codeaurora.org (Postfix) with ESMTP id E392213BF for ; Mon, 21 Jan 2019 22:32:41 +0000 (UTC) Received: from mail.wl.linuxfoundation.org (localhost [127.0.0.1]) by mail.wl.linuxfoundation.org (Postfix) with ESMTP id D32202AED5 for ; Mon, 21 Jan 2019 22:32:41 +0000 (UTC) Received: by mail.wl.linuxfoundation.org (Postfix, from userid 486) id C74E92AEDA; Mon, 21 Jan 2019 22:32:41 +0000 (UTC) X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on pdx-wl-mail.web.codeaurora.org X-Spam-Level: X-Spam-Status: No, score=-15.5 required=2.0 tests=BAYES_00,DKIM_SIGNED, DKIM_VALID,DKIM_VALID_AU,MAILING_LIST_MULTI,RCVD_IN_DNSWL_HI, USER_IN_DEF_DKIM_WL autolearn=ham version=3.3.1 Received: from vger.kernel.org (vger.kernel.org [209.132.180.67]) by mail.wl.linuxfoundation.org (Postfix) with ESMTP id 251B42AEDD for ; Mon, 21 Jan 2019 22:32:41 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1727721AbfAUWcj (ORCPT ); Mon, 21 Jan 2019 17:32:39 -0500 Received: from mail-qk1-f201.google.com ([209.85.222.201]:50475 "EHLO mail-qk1-f201.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1727710AbfAUWcj (ORCPT ); Mon, 21 Jan 2019 17:32:39 -0500 Received: by mail-qk1-f201.google.com with SMTP id x125so20165315qka.17 for ; Mon, 21 Jan 2019 14:32:38 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=20161025; h=date:in-reply-to:message-id:mime-version:references:subject:from:to :cc; bh=QsBi1EbqBEhLSMwlcOMFqp+b+QJCQQLfD7+dRIa5TjI=; b=ZuvdTcUL3kJEmH+OY398NZX5wXwoD48SjAORNBdXYgMfa4LmrEItgfOX0bMNAj5XRg 3YA8OL5q8/yZAaZhw8s0HVHLWKbs7BEOl/T31Mg370BIIzpyPMG6sXMpbo8jJ3zxYd48 1UAPARhGGo/+3i4yrKye4rul5UFpF5q/4cNGRF1YUbf4+o8xfpTXxnpPCmhQ1VVR6vXu S7g+21X3I6y7lPqtTXIRUA2W8Xd1zfTjSf2ZsBooeTxPMR+xPUt8ink6dgdWeh6nSIV+ Rm5Y5/xQMO5fWWWjmybOUk9SZ3ageMXaPoERtxhqFs9my+DlNW1NYSfHHqJcw8Td0m7z RJXQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:date:in-reply-to:message-id:mime-version :references:subject:from:to:cc; bh=QsBi1EbqBEhLSMwlcOMFqp+b+QJCQQLfD7+dRIa5TjI=; b=oBQK007agtNqzCig5AETQCVgz0RKD8Ki2kl3NDJ0spca6ge6zFuDzyI1SiSTz41bpL hmei1umqtquCkEytCL0Nb2O1yw9vK8ipYblKc9/XVV1kXBmDKB/YiYtJPlUohhIS4JnO hB80ugMuhYjmsI62pIVaIe7AJ4Mk6m7eE0lGV+61P7ZAgbBxa5taU7RcTLjomYTmpzsR 1XWpWc73IsC1Mb0GNgxzUk2pp9g7aDJhV2pSolinTKxC4GIk9Psiwijh0n53TWcSiQ/6 0NiXRLj24zEpCZBk0dQhT49X/R5OCHrHB4xIyvreUaSkS3CAOuWlpXA9X1CCFULAhv2U ZKMw== X-Gm-Message-State: AJcUukdd3N8SsB1L2E1yS3zxupepYPQa2/Z3D5uG0/+heqgxv31WwsRb Rvsbhq3qimxH/yyyxO8IVpDdvVxQ0ehwMypnij83rQ4eoK5JzdyjPSrk54KfBNnoXMy+eBGxl7I Nt2o9YfjcxNbUuyVRu/rIfiz672MGf4EBWO/t6dJ5lRZNkvl10SvHMK0DJA== X-Google-Smtp-Source: ALg8bN7JsQ8vwQ+qvKs74eoUZjn6MEzNeE1nlmOBep9xOLpVEmoMG2BZgPqN6UOBxlJUkbvBem5w38JeI9U= X-Received: by 2002:ac8:17e6:: with SMTP id r35mr20891100qtk.45.1548109957725; Mon, 21 Jan 2019 14:32:37 -0800 (PST) Date: Mon, 21 Jan 2019 14:32:15 -0800 In-Reply-To: <20190121223216.66659-1-sxenos@google.com> Message-Id: <20190121223216.66659-7-sxenos@google.com> Mime-Version: 1.0 References: <20190121223216.66659-1-sxenos@google.com> X-Mailer: git-send-email 2.20.1.321.g9e740568ce-goog Subject: [PATCH 7/8] evolve: Implement the git change update command From: sxenos@google.com To: git@vger.kernel.org Cc: Stefan Xenos Sender: git-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org X-Virus-Scanned: ClamAV using ClamSMTP From: Stefan Xenos Implement the git change update command, which are sufficient for constructing change graphs. For example, to create a new change (a stable name) that refers to HEAD: git change update -c HEAD To record a rebase or amend in the change graph: git change update -c -r To record a cherry-pick in the change graph: git change update -c -o --- .gitignore | 1 + Makefile | 1 + builtin.h | 1 + builtin/change.c | 175 +++++++++++++++++++++++++++++++++++++++++++++++ git.c | 1 + 5 files changed, 179 insertions(+) create mode 100644 builtin/change.c diff --git a/.gitignore b/.gitignore index 0d77ea5894..8a084ac38b 100644 --- a/.gitignore +++ b/.gitignore @@ -26,6 +26,7 @@ /git-branch /git-bundle /git-cat-file +/git-change /git-check-attr /git-check-ignore /git-check-mailmap diff --git a/Makefile b/Makefile index a6be1780c5..d6fab30eca 100644 --- a/Makefile +++ b/Makefile @@ -1035,6 +1035,7 @@ BUILTIN_OBJS += builtin/blame.o BUILTIN_OBJS += builtin/branch.o BUILTIN_OBJS += builtin/bundle.o BUILTIN_OBJS += builtin/cat-file.o +BUILTIN_OBJS += builtin/change.o BUILTIN_OBJS += builtin/check-attr.o BUILTIN_OBJS += builtin/check-ignore.o BUILTIN_OBJS += builtin/check-mailmap.o diff --git a/builtin.h b/builtin.h index 6538932e99..d2d39d9da8 100644 --- a/builtin.h +++ b/builtin.h @@ -137,6 +137,7 @@ extern int cmd_blame(int argc, const char **argv, const char *prefix); extern int cmd_branch(int argc, const char **argv, const char *prefix); extern int cmd_bundle(int argc, const char **argv, const char *prefix); extern int cmd_cat_file(int argc, const char **argv, const char *prefix); +extern int cmd_change(int argc, const char **argv, const char *prefix); extern int cmd_checkout(int argc, const char **argv, const char *prefix); extern int cmd_checkout_index(int argc, const char **argv, const char *prefix); extern int cmd_check_attr(int argc, const char **argv, const char *prefix); diff --git a/builtin/change.c b/builtin/change.c new file mode 100644 index 0000000000..ff7eb3b113 --- /dev/null +++ b/builtin/change.c @@ -0,0 +1,175 @@ +#include "builtin.h" +#include "ref-filter.h" +#include "parse-options.h" +#include "metacommit.h" +#include "config.h" + +static const char * const builtin_change_usage[] = { + N_("git change update [--force] [--replace ...] [--origin ...] [--content ]"), + NULL +}; + +static const char * const builtin_update_usage[] = { + N_("git change update [--force] [--replace ...] [--origin ...] [--content ]"), + NULL +}; + +struct update_state { + int options; + const char* change; + const char* content; + struct string_list replace; + struct string_list origin; +}; + +static void init_update_state(struct update_state *state) +{ + memset(state, 0, sizeof(*state)); + state->content = "HEAD"; + string_list_init(&state->replace, 0); + string_list_init(&state->origin, 0); +} + +static void clear_update_state(struct update_state *state) +{ + string_list_clear(&state->replace, 0); + string_list_clear(&state->origin, 0); +} + +static int update_option_parse_replace(const struct option *opt, + const char *arg, int unset) +{ + struct update_state *state = opt->value; + string_list_append(&state->replace, arg); + return 0; +} + +static int update_option_parse_origin(const struct option *opt, + const char *arg, int unset) +{ + struct update_state *state = opt->value; + string_list_append(&state->origin, arg); + return 0; +} + +static int resolve_commit(const char *committish, struct object_id *result) +{ + struct commit *commit; + if (get_oid_committish(committish, result)) + die(_("Failed to resolve '%s' as a valid revision."), committish); + commit = lookup_commit_reference(the_repository, result); + if (!commit) + die(_("Could not parse object '%s'."), committish); + oidcpy(result, &commit->object.oid); + return 0; +} + +static void resolve_commit_list(const struct string_list *commitsish_list, + struct oid_array* result) +{ + int i; + for (i = 0; i < commitsish_list->nr; i++) { + struct string_list_item *item = &commitsish_list->items[i]; + struct object_id next; + resolve_commit(item->string, &next); + oid_array_append(result, &next); + } +} + +/* + * Given the command-line options for the update command, fills in a + * metacommit_data with the corresponding changes. + */ +static void get_metacommit_from_command_line( + const struct update_state* commands, struct metacommit_data *result) +{ + resolve_commit(commands->content, &(result->content)); + resolve_commit_list(&(commands->replace), &(result->replace)); + resolve_commit_list(&(commands->origin), &(result->origin)); +} + +static int perform_update( + struct repository *repo, + const struct update_state *state, + struct strbuf *err) +{ + struct metacommit_data metacommit; + int ret; + + init_metacommit_data(&metacommit); + + get_metacommit_from_command_line(state, &metacommit); + + ret = record_metacommit(repo, &metacommit, state->change, state->options, err); + + clear_metacommit_data(&metacommit); + + return ret; +} + +static int change_update(int argc, const char **argv, const char* prefix) +{ + int result; + int force = 0; + int newchange = 0; + struct strbuf err = STRBUF_INIT; + struct update_state state; + struct option options[] = { + { OPTION_CALLBACK, 'r', "replace", &state, N_("commit"), + N_("marks the given commit as being obsolete"), + 0, update_option_parse_replace }, + { OPTION_CALLBACK, 'o', "origin", &state, N_("commit"), + N_("marks the given commit as being the origin of this commit"), + 0, update_option_parse_origin }, + OPT_BOOL('F', "force", &force, + N_("overwrite an existing change of the same name")), + OPT_STRING('c', "content", &state.content, N_("commit"), + N_("identifies the new content commit for the change")), + OPT_STRING('g', "change", &state.change, N_("commit"), + N_("name of the change to update")), + OPT_BOOL('n', "new", &newchange, + N_("create a new change - do not append to any existing change")), + OPT_END() + }; + + init_update_state(&state); + + argc = parse_options(argc, argv, prefix, options, builtin_update_usage, 0); + + if (force) state.options |= UPDATE_OPTION_FORCE; + if (newchange) state.options |= UPDATE_OPTION_NOAPPEND; + + result = perform_update(the_repository, &state, &err); + + if (result < 0) { + error("%s", err.buf); + strbuf_release(&err); + } + + clear_update_state(&state); + + return result; +} + +int cmd_change(int argc, const char **argv, const char *prefix) +{ + // No options permitted before subcommand currently + struct option options[] = { + OPT_END() + }; + int result = 1; + + argc = parse_options(argc, argv, prefix, options, builtin_change_usage, + PARSE_OPT_STOP_AT_NON_OPTION); + + if (argc < 1) + usage_with_options(builtin_change_usage, options); + else if (!strcmp(argv[0], "update")) + result = change_update(argc, argv, prefix); + else { + error(_("Unknown subcommand: %s"), argv[0]); + usage_with_options(builtin_change_usage, options); + } + + return result ? 1 : 0; +} diff --git a/git.c b/git.c index 0ce0e13f0f..f59f887238 100644 --- a/git.c +++ b/git.c @@ -453,6 +453,7 @@ static struct cmd_struct commands[] = { { "branch", cmd_branch, RUN_SETUP | DELAY_PAGER_CONFIG }, { "bundle", cmd_bundle, RUN_SETUP_GENTLY | NO_PARSEOPT }, { "cat-file", cmd_cat_file, RUN_SETUP }, + { "change", cmd_change, RUN_SETUP }, { "check-attr", cmd_check_attr, RUN_SETUP }, { "check-ignore", cmd_check_ignore, RUN_SETUP | NEED_WORK_TREE }, { "check-mailmap", cmd_check_mailmap, RUN_SETUP }, From patchwork Mon Jan 21 22:32:16 2019 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Stefan Xenos X-Patchwork-Id: 10774635 Return-Path: Received: from mail.wl.linuxfoundation.org (pdx-wl-mail.web.codeaurora.org [172.30.200.125]) by pdx-korg-patchwork-2.web.codeaurora.org (Postfix) with ESMTP id B953913B5 for ; Mon, 21 Jan 2019 22:32:43 +0000 (UTC) Received: from mail.wl.linuxfoundation.org (localhost [127.0.0.1]) by mail.wl.linuxfoundation.org (Postfix) with ESMTP id AB07C2AECB for ; Mon, 21 Jan 2019 22:32:43 +0000 (UTC) Received: by mail.wl.linuxfoundation.org (Postfix, from userid 486) id A9B1D2AEE1; Mon, 21 Jan 2019 22:32:43 +0000 (UTC) X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on pdx-wl-mail.web.codeaurora.org X-Spam-Level: X-Spam-Status: No, score=-15.5 required=2.0 tests=BAYES_00,DKIM_SIGNED, DKIM_VALID,DKIM_VALID_AU,MAILING_LIST_MULTI,RCVD_IN_DNSWL_HI, USER_IN_DEF_DKIM_WL autolearn=ham version=3.3.1 Received: from vger.kernel.org (vger.kernel.org [209.132.180.67]) by mail.wl.linuxfoundation.org (Postfix) with ESMTP id 37DA52AED8 for ; Mon, 21 Jan 2019 22:32:43 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1727761AbfAUWcm (ORCPT ); Mon, 21 Jan 2019 17:32:42 -0500 Received: from mail-pf1-f202.google.com ([209.85.210.202]:36761 "EHLO mail-pf1-f202.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1727710AbfAUWcl (ORCPT ); Mon, 21 Jan 2019 17:32:41 -0500 Received: by mail-pf1-f202.google.com with SMTP id p9so16839895pfj.3 for ; Mon, 21 Jan 2019 14:32:40 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=20161025; h=date:in-reply-to:message-id:mime-version:references:subject:from:to :cc; bh=xABvFOVw5vsmWlpYKKg0Rj79uNZp/zFy7PE9X4wpDQw=; b=T50pYrgetNYTcJNXQL77+6hwzD0o1yXA4TPY8w8YDtXI1iKzW2Cq9se6VqoRyDYHMt 486uSVm+p0uHaw3r020QaWQg5jsSnSCOMDVCuVe4ooGxLSO8OinR+nmSVF2cJIYNYide Us/r83pqi6SeVMwxPN4Kb/7htCIcy3aaKrbFnDd5Ejw8ThZzYkMbXX00J+0d2osBX4qN PFzu5IFOAYdE0385mTSnx7iEbN3rFuoqoBtxGppOoYIlcVrJt+lMuWXHfS8AlMkLUxU9 uQZKED9vQ75OLwiWwV8B4+j9R92+v9v9Q7JoYqfJzxMNJy2q2q4mPtwyvCRNzyHyAoyw gGRw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:date:in-reply-to:message-id:mime-version :references:subject:from:to:cc; bh=xABvFOVw5vsmWlpYKKg0Rj79uNZp/zFy7PE9X4wpDQw=; b=CXOSaFqEbqFZCdCNVJYYEcLrQ0FD+SU6aFMFUfYyv9is3IykVNCsuIQ9Z1GQylMogO qfyl25qYPvx61ezJJsaffm1nfo7CzfaHFFEvY1UpY623Gm6PDYdZmrZ4RDUsqk101+QL BTI82TXW1z3c3h1Bq/u77VJtIuzrhTbxAA80tLhx621Fkbnpt0oxNfAOOrdj2wvKoMTW iEQIT5zMleH6mhOUYje3DZjVkq8kLBMmHZLFCZx+WXpJAAdf7kLkLzCJ1Ro1I0fFRX6+ HdXN32uUTKQC+3AD4FOg5HhNYiRZsEPHPRlUWHdY5d93xmVRZRpOfxrG131KfQ2fp6E6 60NQ== X-Gm-Message-State: AJcUukcCytmqQQRNa+an50YXRPKSo0SODg58Kr3fZvvDQbZcvv1mTRQp TmoEcOdVQE4N9nXuKk+GTxgioSdAJ4OeZXuOUZEYvdF7sXni4XnpzIlX2vVJyJPujD7tf3kGRm0 klhjpn6hw370DYy6uav0JmYU94IuOaB/3I6nkBhLWztPpJxeo50lIU9RB+g== X-Google-Smtp-Source: ALg8bN7umsvOZfNrNkk2EiGQHrUP7Mc/Jdarwn7BvAZCkcwgR/XM/9wwNuFc+4b2S0U6mIdvElhNAaDE76M= X-Received: by 2002:a65:46c9:: with SMTP id n9mr4318796pgr.45.1548109959910; Mon, 21 Jan 2019 14:32:39 -0800 (PST) Date: Mon, 21 Jan 2019 14:32:16 -0800 In-Reply-To: <20190121223216.66659-1-sxenos@google.com> Message-Id: <20190121223216.66659-8-sxenos@google.com> Mime-Version: 1.0 References: <20190121223216.66659-1-sxenos@google.com> X-Mailer: git-send-email 2.20.1.321.g9e740568ce-goog Subject: [PATCH 8/8] evolve: Add the git change list command From: sxenos@google.com To: git@vger.kernel.org Cc: Stefan Xenos Sender: git-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org X-Virus-Scanned: ClamAV using ClamSMTP From: Stefan Xenos This command lists the ongoing changes from the refs/metas namespace. --- builtin/change.c | 53 ++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 53 insertions(+) diff --git a/builtin/change.c b/builtin/change.c index ff7eb3b113..b63fe98665 100644 --- a/builtin/change.c +++ b/builtin/change.c @@ -5,15 +5,66 @@ #include "config.h" static const char * const builtin_change_usage[] = { + N_("git change list [...]"), N_("git change update [--force] [--replace ...] [--origin ...] [--content ]"), NULL }; +static const char * const builtin_list_usage[] = { + N_("git change list [...]"), + NULL +}; + static const char * const builtin_update_usage[] = { N_("git change update [--force] [--replace ...] [--origin ...] [--content ]"), NULL }; +static int change_list(int argc, const char **argv, const char* prefix) +{ + struct option options[] = { + OPT_END() + }; + struct ref_filter filter; + // TODO: Sorting temporarily disabled. See comments, below. + //struct ref_sorting *sorting = ref_default_sorting(); + struct ref_format format = REF_FORMAT_INIT; + struct ref_array array; + int i; + + argc = parse_options(argc, argv, prefix, options, builtin_list_usage, 0); + + setup_ref_filter_porcelain_msg(); + + memset(&filter, 0, sizeof(filter)); + memset(&array, 0, sizeof(array)); + + filter.kind = FILTER_REFS_CHANGES; + filter.name_patterns = argv; + + filter_refs(&array, &filter, FILTER_REFS_CHANGES); + + // TODO: This causes a crash. It sets one of the atom_value handlers to + // something invalid, which causes a crash later when we call + // show_ref_array_item. Figure out why this happens and put back the sorting. + //ref_array_sort(sorting, &array); + + if (!format.format) { + format.format = "%(refname:lstrip=1)"; + } + + if (verify_ref_format(&format)) + die(_("unable to parse format string")); + + for (i = 0; i < array.nr; i++) { + show_ref_array_item(array.items[i], &format); + } + + ref_array_clear(&array); + + return 0; +} + struct update_state { int options; const char* change; @@ -164,6 +215,8 @@ int cmd_change(int argc, const char **argv, const char *prefix) if (argc < 1) usage_with_options(builtin_change_usage, options); + else if (!strcmp(argv[0], "list")) + result = change_list(argc, argv, prefix); else if (!strcmp(argv[0], "update")) result = change_update(argc, argv, prefix); else {