{"thread":{"id":"50338","subject":"[PATCH v3 1/8] technical doc: add a design doc for the evolve command","startedAt":"2019-01-27T19:44:22Z","lastAt":"2019-01-29T18:09:57Z","messageCount":15,"participants":["sxenos@google.com","Junio C Hamano","Johannes Schindelin","Stefan Xenos"],"isPatch":true,"patchVersion":3,"patchTotal":8},"messages":[{"id":"367770","messageId":"20190127194415.171035-1-sxenos@google.com","threadId":"50338","inReplyTo":null,"subject":"[PATCH v3 1/8] technical doc: add a design doc for the evolve command","fromName":"","fromEmail":"sxenos@google.com","sentAt":"2019-01-27T19:44:08Z","receivedAt":"2019-01-27T19:44:22Z","isPatch":true,"sender":{"key":"sxenos@google.com","avatar":null},"body":"From: Stefan Xenos \n\nThis document describes what a change graph for\ngit would look like, the behavior of the evolve command,\nand the changes planned for other commands.\n\nSigned-off-by: Stefan Xenos \n---\n Documentation/technical/evolve.txt | 1034 ++++++++++++++++++++++++++++\n 1 file changed, 1034 insertions(+)\n create mode 100644 Documentation/technical/evolve.txt\n\ndiff --git a/Documentation/technical/evolve.txt b/Documentation/technical/evolve.txt\nnew file mode 100644\nindex 0000000000..7967c73e5d\n--- /dev/null\n+++ b/Documentation/technical/evolve.txt\n@@ -0,0 +1,1034 @@\n+Evolve\n+======\n+\n+Objective\n+=========\n+Create an \"evolve\" command to help users craft a high quality commit history.\n+Users can improve commits one at a time and in any order, then run git evolve to\n+rewrite their recent history to ensure everything is up-to-date. We track\n+amendments to a commit over time in a change graph. Users can share their\n+progress with others by exchanging their change graphs using the standard push,\n+fetch, and format-patch commands.\n+\n+Status\n+======\n+This proposal has not been implemented yet.\n+\n+Background\n+==========\n+Imagine you have three sequential changes up for review and you receive feedback\n+that requires editing all three changes. We'll define the word \"change\"\n+formally later, but for the moment let's say that a change is a work-in-progress\n+whose final version will be submitted as a commit in the future.\n+\n+While you're editing one change, more feedback arrives on one of the others.\n+What do you do?\n+\n+The evolve command is a convenient way to work with chains of commits that are\n+under review. Whenever you rebase or amend a commit, the repository remembers\n+that the old commit is obsolete and has been replaced by the new one. Then, at\n+some point in the future, you can run \"git evolve\" and the correct sequence of\n+rebases will occur in the correct order such that no commit has an obsolete\n+parent.\n+\n+Part of making the \"evolve\" command work involves tracking the edits to a commit\n+over time, which is why we need an change graph. However, the change\n+graph will also bring other benefits:\n+\n+- Users can view the history of a change directly (the sequence of amends and\n+ rebases it has undergone, orthogonal to the history of the branch it is on).\n+- It will be possible to quickly locate and list all the changes the user\n+ currently has in progress.\n+- It can be used as part of other high-level commands that combine or split\n+ changes.\n+- It can be used to decorate commits (in git log, gitk, etc) that are either\n+ obsolete or are the tip of a work in progress.\n+- By pushing and pulling the change graph, users can collaborate more\n+ easily on changes-in-progress. This is better than pushing and pulling the\n+ changes themselves since the change graph can be used to locate a more\n+ specific merge base, allowing for better merges between different versions of\n+ the same change. \n+- It could be used to correctly rebase local changes and other local branches\n+ after running git-filter-branch.\n+- It can replace the change-id footer used by gerrit.\n+\n+Goals\n+-----\n+Legend: Goals marked with P0 are required. Goals marked with Pn should be\n+attempted unless they interfere with goals marked with Pn-1.\n+\n+P0. All commands that modify commits (such as the normal commit --amend or\n+ rebase command) should mark the old commit as being obsolete and replaced by\n+ the new one. No additional commands should be required to keep the\n+ change graph up-to-date.\n+P0. Any commit that may be involved in a future evolve command should not be\n+ garbage collected. Specifically:\n+ - Commits that obsolete another should not be garbage collected until\n+ user-specified conditions have occurred and the change has expired from\n+ the reflog. User specified conditions for removing changes include:\n+ - The user explicitly deleted the change.\n+ - The change was merged into a specific branch.\n+ - Commits that have been obsoleted by another should not be garbage\n+ collected if any of their replacements are still being retained.\n+P0. A commit can be obsoleted by more than one replacement (called divergence).\n+P0. Must be able to resolve divergence (convergence).\n+P1. Users should be able to share chains of obsolete changes in order to\n+ collaborate on WIP changes.\n+P2. Such sharing should be at the user’s option. That is, it should be possible\n+ to directly share a change without also sharing the file states or commit\n+ comments from the obsolete changes that led up to it, and the choice not to\n+ share those commits should not require changing any commit hashes.\n+P2. It should be possible to discard part or all of the change graph\n+ without discarding the commits themselves that are already present in\n+ branches and the reflog.\n+P2. Provide sufficient information to replace gerrit's Change-Id footers.\n+\n+Similar technologies\n+--------------------\n+There are some other technologies that address the same end-user problem.\n+\n+Rebase -i can be used to solve the same problem, but users can't easily switch\n+tasks midway through an interactive rebase or have more than one interactive\n+rebase going on at the same time. It can't handle the case where you have\n+multiple changes sharing the same parent when that parent needs to be rebased\n+and won't let you collaborate with others on resolving a complicated interactive\n+rebase. You can think of rebase -i as a top-down approach and the evolve command\n+as the bottom-up approach to the same problem.\n+\n+Several patch queue managers have been built on top of git (such as topgit,\n+stgit, and quilt). They address the same user need. However they also rely on\n+state managed outside git that needs to be kept in sync. Such state can be\n+easily damaged when running a git native command that is unaware of the patch\n+queue. They also typically require an explicit initialization step to be done by\n+the user which creates workflow problems.\n+\n+Mercurial implements a very similar feature in its EvolveExtension. The behavior\n+of the evolve command itself is very similar, but the storage format for the\n+change graph differs. In the case of mercurial, each change set can have one or\n+more obsolescence markers that point to other changesets that they replace. This\n+is similar to the \"Commit Headers\" approach considered in the other options\n+appendix. The approach proposed here stores obsolescence information in a\n+separate metacommit graph, which makes exchanging of obsolescence information\n+optional.\n+\n+Mercurial's default behavior makes it easy to find and switch between\n+non-obsolete changesets that aren't currently on any branch. We introduce the\n+notion of a new ref namespace that enables a similar workflow via a different\n+mechanism. Mercurial has the notion of changeset phases which isn't present\n+in git and creates new ways for a changeset to diverge. Git doesn't need\n+to deal with these issues, but it has to deal with picking an upstream branch as\n+a target for rebases and protecting obsolescence information from GC. We also\n+introduce some additional transformations (see obsolescence-over-cherry-pick,\n+below) that aren't present in the mercurial implementation.\n+\n+Semi-related work\n+-----------------\n+There are other technologies that address different problems but have some\n+similarities with this proposal.\n+\n+Replacements (refs/replace) are superficially similar to obsolescences in that\n+they describe that one commit should be replaced by another. However, they\n+differ in both how they are created and how they are intended to be used.\n+Obsolescences are created automatically by the commands a user runs, and they\n+describe the user’s intent to perform a future rebase. Obsolete commits still\n+appear in branches, logs, etc like normal commits (possibly with an extra\n+decoration that marks them as obsolete). Replacements are typically created\n+explicitly by the user, they are meant to be kept around for a long time, and\n+they describe a replacement to be applied at read-time rather than as the input\n+to a future operation. When a replaced commit is queried, it is typically hidden\n+and swapped out with its replacement as though the replacement has already\n+occurred.\n+\n+Git-imerge is a project to help make complicated merges easier, particularly\n+when merging or rebasing long chains of patches. It is not an alternative to\n+the change graph, but its algorithm of applying smaller incremental merges\n+could be used as part of the evolve algorithm in the future.\n+\n+Overview\n+========\n+We introduce the notion of “meta-commits” which describe how one commit was\n+created from other commits. A branch of meta-commits is known as a change.\n+Changes are created and updated automatically whenever a user runs a command\n+that creates a commit. They are used for locating obsolete commits, providing a\n+list of a user’s unsubmitted work in progress, and providing a stable name for\n+each unsubmitted change.\n+\n+Users can exchange edit histories by pushing and fetching changes.\n+\n+New commands will be introduced for manipulating changes and resolving\n+divergence between them. Existing commands that create commits will be updated\n+to modify the meta-commit graph and create changes where necessary.\n+\n+Example usage\n+-------------\n+# First create three dependent changes\n+$ echo foo>bar.txt && git add .\n+$ git commit -m \"This is a test\"\n+created change metas/this_is_a_test\n+$ echo foo2>bar2.txt && git add .\n+$ git commit -m \"This is also a test\"\n+created change metas/this_is_also_a_test\n+$ echo foo3>bar3.txt && git add .\n+$ git commit -m \"More testing\"\n+created change metas/more_testing\n+\n+# List all our changes in progress\n+$ git change list\n+metas/this_is_a_test\n+metas/this_is_also_a_test\n+* metas/more_testing\n+metas/some_change_already_merged_upstream\n+\n+# Now modify the earliest change, using its stable name\n+$ git reset --hard metas/this_is_a_test\n+$ echo morefoo>>bar.txt && git add . && git commit --amend --no-edit\n+\n+# Use git-evolve to fix up any dependent changes\n+$ git evolve\n+rebasing metas/this_is_also_a_test onto metas/this_is_a_test\n+rebasing metas/more_testing onto metas/this_is_also_a_test\n+Done\n+\n+# Use git-obslog to view the history of the this_is_a_test change\n+$ git log --obslog\n+93f110 metas/this_is_a_test@{0} commit (amend): This is a test\n+930219 metas/this_is_a_test@{1} commit: This is a test\n+\n+# Now create an unrelated change\n+$ git reset --hard origin/master\n+$ echo newchange>unrelated.txt && git add .\n+$ git commit -m \"Unrelated change\"\n+created change metas/unrelated_change\n+\n+# Fetch the latest code from origin/master and use git-evolve\n+# to rebase all dependent changes.\n+$ git fetch origin master\n+$ git evolve origin/master\n+deleting metas/some_change_already_merged_upstream\n+rebasing metas/this_is_a_test onto origin/master\n+rebasing metas/this_is_also_a_test onto metas/this_is_a_test\n+rebasing metas/more_testing onto metas/this_is_also_a_test\n+rebasing metas/unrelated_change onto origin/master\n+Conflict detected! Resolve it and then use git evolve --continue to resume.\n+\n+# Sort out the conflict\n+$ git mergetool\n+$ git evolve --continue\n+Done\n+\n+# Share the full history of edits for the this_is_a_test change\n+# with a review server\n+$ git push origin metas/this_is_a_test:refs/for/master\n+# Share the lastest commit for “Unrelated change”, without history\n+$ git push origin HEAD:refs/for/master\n+\n+Detailed design\n+===============\n+Obsolescence information is stored as a graph of meta-commits. A meta-commit is\n+a specially-formatted merge commit that describes how one commit was created\n+from others.\n+\n+Meta-commits look like this:\n+\n+$ git cat-file -p \n+tree 4b825dc642cb6eb9a060e54bf8d69288fbee4904\n+parent aa7ce55545bf2c14bef48db91af1a74e2347539a\n+parent d64309ee51d0af12723b6cb027fc9f195b15a5e9\n+parent 7e1bbcd3a0fa854a7a9eac9bf1eea6465de98136\n+author Stefan Xenos 1540841596 -0700\n+committer Stefan Xenos 1540841596 -0700\n+parent-type c r o\n+\n+This says “commit aa7ce555 makes commit d64309ee obsolete. It was created by\n+cherry-picking commit 7e1bbcd3”.\n+\n+The tree for meta-commits is always the empty tree whose hash matches\n+4b825dc642cb6eb9a060e54bf8d69288fbee4904 exactly, but future versions of git may\n+attach other trees here. For forward-compatibility fsck should ignore such trees\n+if found on future repository versions. Similarly, current versions of git\n+should always fill in an empty commit comment and tools like fsck should ignore\n+the content of the commit comment if present in a future repository version.\n+This will allow future versions of git to add metadata to the meta-commit\n+comments or tree without breaking forwards compatibility.\n+\n+Parent-type\n+-----------\n+The “parent-type” field in the commit header identifies a commit as a\n+meta-commit and indicates the meaning for each of its parents. It is never\n+present for normal commits. It contains a space-deliminated list of enum values\n+whose order matches the order of the parents. Possible parent types are:\n+\n+- c: (content) the content parent identifies the commit that this meta-commit is\n+ describing.\n+- r: (replaced) indicates that this parent is made obsolete by the content\n+ parent.\n+- o: (origin) indicates that this parent was generated from the given commit.\n+- a: (abandoned) used in place of a content parent for abandoned changes. Points\n+ to the final content commit for the change at the time it was abandoned.\n+\n+There must be exactly one content or abandoned parent for each meta-commit and it is\n+always the first parent. The content commit will always be a normal commit and not a\n+meta-commit. However, future versions of git may create meta-commits for other\n+meta-commits and the fsck tool must be aware of this for forwards compatibility.\n+\n+A meta-commit can have zero or more replaced parents. An amend operation creates\n+a single replaced parent. A merge used to resolve divergence (see divergence,\n+below) will create multiple replaced parents. A meta-commit may have no\n+replaced parents if it describes a cherry-pick or squash merge that copies one\n+or more commits but does not replace them.\n+\n+A meta-commit can have zero or more origin parents. A cherry-pick creates a\n+single origin parent. Certain types of squash merge will create multiple origin\n+parents. Origin parents don't directly cause their origin to become obsolete,\n+but are used when computing blame or locating a merge base. The section\n+on obsolescence over cherry-picks describes how the evolve command uses\n+origin parents.\n+\n+A replaced parent or origin parent may be either a normal commit (indicating\n+the oldest-known version of a change) or another meta-commit (for a change that\n+has already been modified one or more times).\n+\n+The parent-type field needs to go after the committer field since git's rules\n+for forwards-compatibility require that new fields to be at the end of the\n+header. Putting a new field in the middle of the header would break fsck. \n+\n+The presence of an abandoned parent indicates that the change should be pruned\n+by the evolve command, and removed from the repository's history. The abandoned\n+parent points to the version of the change that should be restored if the user\n+attempts to restore the change.\n+\n+Changes\n+-------\n+A branch of meta-commits describes how a commit was produced and what previous\n+commits it is based on. It is also an identifier for a thing the user is\n+currently working on. We refer to such a meta-branch as a change.\n+\n+Local changes are stored in the new refs/metas namespace. Remote changes are\n+stored in the refs/remote//metas namespace.\n+\n+The list of changes in refs/metas is more than just a mechanism for the evolve\n+command to locate obsolete commits. It is also a convenient list of all of a\n+user’s work in progress and their current state - a list of things they’re\n+likely to want to come back to.\n+\n+Strictly speaking, it is the presence of the branch in the refs/metas namespace\n+that marks a branch as being a change, not the fact that it points to a\n+metacommit. Metacommits are only created when a commit is amended or rebased, so\n+in the case where a change points to a commit that has never been modified, the\n+change points to that initial commit rather than a metacommit.\n+\n+Changes are also stored in the refs/hiddenmetas namespace. Hiddenmetas holds\n+metadata for historical changes that are not currently in progress by the user.\n+Commands like filter-branch and other bulk import commands create metadata in\n+this namespace.\n+\n+Note that the changes in hiddenmetas get special treatment in several ways:\n+\n+- They are not cleaned up automatically once merged, since it is expected that\n+ they refer to historical changes.\n+- User commands that modify changes don't append to these changes as they would\n+ to a change in refs/metas.\n+- They are not displayed when the user lists their local changes.\n+\n+Obsolescence\n+------------\n+A commit is considered obsolete if it is reachable from the “replaces” edges\n+anywhere in the history of a change and it isn’t the head of that change.\n+Commits may be the content for 0 or more meta-commits. If the same commit\n+appears in multiple changes, it is not obsolete if it is the head of any of\n+those changes.\n+\n+Note that there is an exeption to this rule. The metas namespace takes\n+precedence over the hiddenmetas namespace for the purpose of obsolescence. That\n+is, if a change appears in a replaces edge of a change in the metas namespace,\n+it is obsolete even if it also appears as the head of a change in the\n+hiddenmetas namespace.\n+\n+This special case prevents the hiddenmetas namespace from creating divergence\n+with the user's work in progress, and allows the user to resolve historical\n+divergence by creating new changes in the metas namespace.\n+\n+Divergence\n+----------\n+From the user’s perspective, two changes are divergent if they both ask for\n+different replacements to the same commit. More precisely, a target commit is\n+considered divergent if there is more than one commit at the head of a change in\n+refs/metas that leads to the target commit via an unbroken chain of “obsolete”\n+parents.\n+\n+Much like a merge conflict, divergence is a situation that requires user\n+intervention to resolve. The evolve command will stop when it encounters\n+divergence and prompt the user to resolve the problem. Users can solve the\n+problem in several ways:\n+\n+- Discard one of the changes (by deleting its change branch).\n+- Merge the two changes (producing a single change branch).\n+- Copy one of the changes (keep both commits, but one of them gets a new\n+ metacommit appended to its history that is connected to its predecessor via an\n+ origin edge rather than an obsolete edge. That new change no longer obsoletes\n+ the original.)\n+\n+Obsolescence across cherry-picks\n+--------------------------------\n+By default the evolve command will treat cherry-picks and squash merges as being\n+completely separate from the original. Further amendments to the original commit\n+will have no effect on the cherry-picked copy. However, this behavior may not be\n+desirable in all circumstances.\n+\n+The evolve command may at some point support an option to look for cases where\n+the source of a cherry-pick or squash merge has itself been amended, and\n+automatically apply that same change to the cherry-picked copy. In such cases,\n+it would traverse origin edges rather than ignoring them, and would treat a\n+commit with origin edges as being obsolete if any of its origins were obsolete.\n+\n+Garbage collection\n+------------------\n+For GC purposes, meta-commits are normal commits. Just as a commit causes its\n+parents and tree to be retained, a meta-commit also causes its parents to be\n+retained.\n+\n+Change creation\n+---------------\n+Changes are created automatically whenever the user runs a command like “commit”\n+that has the semantics of creating a new change. They also move forward\n+automatically even if they’re not checked out. For example, whenever the user\n+runs a command like “commit --amend” that modifies a commit, all branches in\n+refs/metas that pointed to the old commit move forward to point to its\n+replacement instead. This also happens when the user is working from a detached\n+head.\n+\n+This does not mean that every commit has a corresponding change. By default,\n+changes only exist for recent locally-created commits. Users may explicitly pull\n+changes from other users or keep their changes around for a long time, but\n+either behavior requires a user to opt-in. Code review systems like gerrit may\n+also choose to keep changes around forever.\n+\n+Note that the changes in refs/metas serve a dual function as both a way to\n+identify obsolete changes and as a way for the user to keep track of their work\n+in progress. If we were only concerned with identifying obsolete changes, it\n+would be sufficient to create the change branch lazily the first time a commit\n+is obsoleted. Addressing the second use - of refs/metas as a mechanism for\n+keeping track of work in progress - is the reason for eagerly creating the\n+change on first commit.\n+\n+Change naming\n+-------------\n+When a change is first created, the only requirement for its name is that it\n+must be unique. Good names would also serve as useful mnemonics and be easy to\n+type. For example, a short word from the commit message containing no numbers or\n+special characters and that shows up with low frequency in other commit messages\n+would make a good choice.\n+\n+Different users may prefer different heuristics for their change names. For this\n+reason a new hook will be introduced to compute change names. Git will invoke\n+the hook for all newly-created changes and will append a numeric suffix if the\n+name isn’t unique. The default heuristics are not specified by this proposal and\n+may change during implementation.\n+\n+Change deletion\n+---------------\n+Changes are normally only interesting to a user while a commit is still in\n+development and under review. Once the commit has submitted wherever it is\n+going, its change can be discarded.\n+\n+The normal way of deleting changes makes this easy to do - changes are deleted\n+by the evolve command when it detects that the change is present in an upstream\n+branch. It does this in two ways: if the latest commit in a change either shows\n+up in the branch history or the change becomes empty after a rebase, it is\n+considered merged and the change is discarded. In this context, an “upstream\n+branch” is any branch passed in as the upstream argument of the evolve command.\n+\n+In case this sometimes deletes a useful change, such automatic deletions are\n+recorded in the reflog allowing them to be easily recovered.\n+\n+Sharing changes\n+---------------\n+Change histories are shared by pushing or fetching meta-commits and change\n+branches. This provides users with a lot of control of what to share and\n+repository implementations with control over what to retain.\n+\n+Users that only want to share the content of a commit can do so by pushing the\n+commit itself as they currently would. Users that want to share an edit history\n+for the commit can push its change, which would point to a meta-commit rather\n+than the commit itself if there is any history to share. Note that multiple\n+changes can refer to the same commits, so it’s possible to construct and push a\n+different history for the same commit in order to remove sensitive or irrelevant\n+intermediate states.\n+\n+Imagine the user is working on a change “mychange” that is currently the latest\n+commit on master, they have two ways to share it:\n+\n+# User shares just a commit without its history\n+> git push origin master\n+\n+# User shares the full history of the commit to a review system\n+> git push origin metas/mychange:refs/for/master\n+\n+# User fetches a collaborator’s modifications to their change\n+> git fetch remotename metas/mychange\n+# Which updates the ref remote/remotename/metas/mychange\n+\n+This will cause more intermediate states to be shared with the server than would\n+have been shared previously. A review system like gerrit would need to keep\n+track of which states had been explicitly pushed versus other intermediate\n+states in order to de-emphasize (or hide) the extra intermediate states from the\n+user interface.\n+\n+Merge-base\n+----------\n+Merge-base will be changed to search the meta-commit graph for common ancestors\n+as well as the commit graph, and will generally prefer results from the\n+meta-commit graph over the commit graph. Merge-base will consider meta-commits\n+from all changes, and will traverse both origin and obsolete edges.\n+\n+The reason for this is that - when merging two versions of the same commit\n+together - an earlier version of that same commit will usually be much more\n+similar than their common parent. This should make the workflow of collaborating\n+on unsubmitted patches as convenient as the workflow for collaborating in a\n+topic branch by eliminating repeated merges.\n+\n+Configuration\n+-------------\n+The core.enableChanges configuration variable enables the creation and update\n+of change branches. This is enabled by default.\n+\n+User interface\n+--------------\n+All git porcelain commands that create commits are classified as having one of\n+four behaviors: modify, create, copy, or import. These behaviors are discussed\n+in more detail below.\n+\n+Modify commands\n+---------------\n+Modification commands (commit --amend, rebase) will mark the old commit as\n+obsolete by creating a new meta-commit that references the old one as a\n+replaced parent. In the event that multiple changes point to the same commit,\n+this is done independently for every such change.\n+\n+More specifically, modifications work like this:\n+\n+1. Locate all existing changes for which the old commit is the content for the\n+ head of the change branch. If no such branch exists, create one that points\n+ to the old commit. Changes that include this commit in their history but not\n+ at their head are explicitly not included.\n+2. For every such change, create a new meta-commit that references the new\n+ commit as its content and references the old head of the change as a\n+ replaced parent.\n+3. Move the change branch forward to point to the new meta-commit.\n+\n+Copy commands\n+-------------\n+Copy commands (cherry-pick, merge --squash) create a new meta-commit that\n+references the old commits as origin parents. Besides the fact that the new\n+parents are tagged differently, copy commands work the same way as modify\n+commands.\n+\n+Create commands\n+---------------\n+Creation commands (commit, merge) create a new commit and a new change that\n+points to that commit. The do not create any meta-commits.\n+\n+Import commands\n+---------------\n+Import commands (fetch, pull) do not create any new meta-commits or changes\n+unless that is specifically what they are importing. For example, the fetch\n+command would update remote/origin/metas/change35 and fetch all referenced\n+meta-commits if asked to do so directly, but it wouldn’t create any changes or\n+meta-commits for commits discovered on the master branch when running “git fetch\n+origin master”.\n+\n+Other commands\n+--------------\n+Some commands don’t fit cleanly into one of the above categories.\n+\n+Semantically, filter-branch should be treated as a modify command, but doing so\n+is likely to create a lot of irrelevant clutter in the changes namespace and the\n+large number of extra change refs may introduce performance problems. We\n+recommend treating filter-branch as an import command initially, but making it\n+behave more like a modify command in future follow-up work. One possible\n+solution may be to treat commits that are part of existing changes as being\n+modified but to avoid creating changes for other rewritten changes.\n+\n+Once the evolve command can handle obsolescence across cherry-picks, such\n+cherry-picks will result in a hybrid move-and-copy operation. It will create\n+cherry-picks that replace other cherry-picks, which will have both origin edges\n+(pointing to the new source commit being picked) and obsolete edges (pointing to\n+the previous cherry-pick being replaced).\n+\n+Evolve\n+------\n+The evolve command performs the correct sequence of rebases such that no change\n+has an obsolete parent. The syntax looks like this:\n+\n+git evolve [--abort][--continue][--quit] [upstream…]\n+\n+It takes an optional list of upstream branches. All changes whose parent shows\n+up in the history of one of the upstream branches will be rebased onto the\n+upstream branch before resolving obsolete parents.\n+\n+Any change whose latest state is found in an upstream branch (or that ends up\n+empty after rebase) will be deleted. This is the normal mechanism for deleting\n+changes. Changes are created automatically on the first commit, and are deleted\n+automatically when evolve determines that they’ve been merged upstream.\n+\n+Orphan commits are commits with obsolete parents. The evolve command then\n+repeatedly rebases orphan commits with non-orphan parents until there are either\n+no orphan commits left, a merge conflict is discovered, or a divergent parent is\n+discovered.\n+\n+When evolve discovers divergence, it will first check if it can resolve the\n+divergence automatically using one of its enabled transformations. Supported\n+transformations are:\n+\n+- Check if the user has already merged the divergent changes in a follow-up\n+ change. That is, look for an existing merge in a follow-up change where all\n+ the parents are divergent versions of the same change. Squash that merge with\n+ its parents and use the result as the resolution for the divergence.\n+\n+- Attempt to auto-merge all the divergent changes (disabled by default).\n+\n+Each of the transformations can be enabled or disabled by command line options.\n+\n+The --abort option returns all changes to the state they were in prior to\n+invoking evolve, and the --quit option terminates the current evolution without\n+changing the current state.\n+\n+If the working tree is dirty, evolve will attempt to stash the user's changes\n+before applying the evolve and then reapply those changes afterward, in much\n+the same way as rebase --autostash does.\n+\n+Checkout\n+--------\n+Running checkout on a change by name has the same effect as checking out a\n+detached head pointing to the latest commit on that change-branch. There is no\n+need to ever have HEAD point to a change since changes always move forward when\n+necessary, no matter what branch the user has checked out\n+\n+Meta-commits themselves cannot be checked out by their hash.\n+\n+Reset\n+-----\n+Resetting a branch to a change by name is the same as resetting to the commit at\n+that change’s head.\n+\n+Commit\n+------\n+Commit --amend gets modify semantics and will move existing changes forward. The\n+normal form of commit gets create semantics and will create a new change.\n+\n+$ touch foo && git add . && git commit -m \"foo\" && git tag A\n+$ touch bar && git add . && git commit -m \"bar\" && git tag B\n+$ touch baz && git add . && git commit -m \"baz\" && git tag C\n+\n+This produces the following commits:\n+A(tree=[foo])\n+B(tree=[foo, bar], parent=A)\n+C(tree=[foo, bar, baz], parent=B)\n+\n+...along with three changes:\n+metas/foo = A\n+metas/bar = B\n+metas/baz = C\n+\n+Running commit --amend does the following:\n+$ git checkout B\n+$ touch zoom && git add . && git commit --amend -m \"baz and zoom\"\n+$ git tag D\n+\n+Commits:\n+A(tree=[foo])\n+B(tree=[foo, bar], parent=A)\n+C(tree=[foo, bar, baz], parent=B)\n+D(tree=[foo, bar, zoom], parent=A)\n+Dmeta(content=D, obsolete=B)\n+\n+Changes:\n+metas/foo = A\n+metas/bar = Dmeta\n+metas/baz = C\n+\n+Merge\n+-----\n+Merge gets create, modify, or copy semantics based on what is being merged and\n+the options being used.\n+\n+The --squash version of merge gets copy semantics (it produces a new change that\n+is marked as a copy of all the original changes that were squashed into it).\n+\n+The “modify” version of merge replaces both of the original commits with the\n+resulting merge commit. This is one of the standard mechanisms for resolving\n+divergence. The parents of the merge commit are the parents of the two commits\n+being merged. The resulting commit will not be a merge commit if both of the\n+original commits had the same parent or if one was the parent of the other.\n+\n+The “create” version of merge creates a new change pointing to a merge commit\n+that has both original commits as parents. The result is what merge produces now\n+- a new merge commit. However, this version of merge doesn’t directly resolve\n+divergence.\n+\n+To select between these two behaviors, merge gets new “--amend” and “--noamend”\n+options which select between the “create” and “modify” behaviors respectively,\n+with noamend being the default.\n+\n+For example, imagine we created two divergent changes like this:\n+\n+$ touch foo && git add . && git commit -m \"foo\" && git tag A\n+$ touch bar && git add . && git commit -m \"bar\" && git tag B\n+$ touch baz && git add . && git commit --amend -m \"bar and baz\"\n+$ git tag C\n+$ git checkout B\n+$ touch bam && git add . && git commit --amend -m \"bar and bam\"\n+$ git tag D\n+\n+At this point the commit graph looks like this:\n+\n+A(tree=[foo])\n+B(tree=[bar], parent=A)\n+C(tree=[bar, baz], parent=A)\n+D(tree=[bar, bam], parent=A)\n+Cmeta(content=C, obsoletes=B)\n+Dmeta(content=D, obsoletes=B)\n+\n+There would be three active changes with heads pointing as follows:\n+\n+metas/changeA=A\n+metas/changeB=Cmeta\n+metas/changeB2=Dmeta\n+\n+ChangeB and changeB2 are divergent at this point. Lets consider what happens if\n+perform each type of merge between changeB and changeB2.\n+\n+Merge example: Amend merge\n+One way to resolve divergent changes is to use an amend merge. Recall that HEAD\n+is currently pointing to D at this point.\n+\n+$ git merge --amend metas/changeB\n+\n+Here we’ve asked for an amend merge since we’re trying to resolve divergence\n+between two versions of the same change. There are no conflicts so we end up\n+with this:\n+\n+E(tree=[bar, baz, bam], parent=A)\n+Emeta(content=E, obsoletes=[Cmeta, Dmeta])\n+\n+With the following branches:\n+\n+metas/changeA=A\n+metas/changeB=Emeta\n+metas/changeB2=Emeta\n+\n+Notice that the result of the “amend merge” is a replacement for C and D rather\n+than a new commit with C and D as parents (as a normal merge would have\n+produced). The parents of the amend merge are the parents of C and D which - in\n+this case - is just A, so the result is not a merge commit. Also notice that\n+changeB and changeB2 are now aliases for the same change.\n+\n+Merge example: Noamend merge\n+Consider what would have happened if we’d used a noamend merge instead. Recall\n+that HEAD was at D and our branches looked like this:\n+\n+metas/changeA=A\n+metas/changeB=Cmeta\n+metas/changeB2=Dmeta\n+\n+$ git merge --noamend metas/changeB\n+\n+That would produce the sort of merge we’d normally expect today:\n+\n+F(tree=[bar, baz, bam], parent=[C, D])\n+\n+And our changes would look like this:\n+metas/changeA=A\n+metas/changeB=Cmeta\n+metas/changeB2=Dmeta\n+metas/changeF=F\n+\n+In this case, changeB and changeB2 are still divergent and we’ve created a new\n+change for our merge commit. However, this is just a temporary state. The next\n+time we run the “evolve” command, it will discover the divergence but also\n+discover the merge commit F that resolves it. Evolve will suggest converting F\n+into an amend merge in order to resolve the divergence and will display the\n+command for doing so.\n+\n+Rebase\n+------\n+In general the rebase command is treated as a modify command. When a change is\n+rebased, the new commit replaces the original.\n+\n+Rebase --abort is special. Its intent is to restore git to the state it had\n+prior to running rebase. It should move back any changes to point to the refs\n+they had prior to running rebase and delete any new changes that were created as\n+part of the rebase. To achieve this, rebase will save the state of all changes\n+in refs/metas prior to running rebase and will restore the entire namespace\n+after rebase completes (deleting any newly-created changes). Newly-created\n+metacommits are left in place, but will have no effect until garbage collected\n+since metacommits are only used if they are reachable from refs/metas.\n+\n+Change\n+------\n+The “change” command can be used to list, rename, reset or delete change. It has\n+a number of subcommands.\n+\n+The \"list\" subcommand lists local changes. If given the -r argument, it lists\n+remote changes.\n+\n+The \"rename\" subcommand renames a change, given its old and new name. If the old\n+name is omitted and there is exactly one change pointing to the current HEAD,\n+that change is renamed. If there are no changes pointing to the current HEAD,\n+one is created with the given name.\n+\n+The \"forget\" subcommand deletes a change by deleting its ref from the metas/\n+namespace. This is the normal way to delete extra aliases for a change if the\n+change has more than one name. By default, this will refuse to delete the last\n+alias for a change if there are any other changes that reference this change as\n+a parent.\n+\n+The \"update\" subcommand adds a new state to a change. It uses the default\n+algorithm for assigning change names. If the content commit is omitted, HEAD is\n+used. If given the optional --force argument, it will overwrite any existing\n+change of the same name. This latter form of \"update\" can be used to effectively\n+reset changes.\n+\n+The \"update\" command can accept any number of --origin and --replace arguments.\n+If any are present, the resulting change branch will point to a metacommit\n+containing the given origin and replacement edges.\n+\n+The \"replace\" command records a replacement in the obsolescence graph, given a\n+list of obsolete commits or metacommits followed by their replacement. This\n+behaves like a normal \"modify\" command, except that the replacement is an\n+existing commit. If an obsolete commit points to a metacommit, only a change\n+branch pointing to exactly that metacommit moves forward. If an obsolete commit\n+points to a normal commit, all change branches pointing to that commit move\n+forward. If no change branches moved forward, a new change branch is created\n+using the default name.\n+\n+The \"abandon\" command deletes a change using obsolescence markers. It marks the\n+change as being obsolete and having been replaced by its parent. If given no\n+arguments, it applies to the current commit. Running evolve will cause any\n+abandoned changes to be removed from the branch. Any child changes will be\n+reparented on top of the parent of the abandoned change. If the current change\n+is abandoned, HEAD will move to point to its parent.\n+\n+The \"restore\" command restores a previously-abandoned change.\n+\n+The \"prune\" command deletes all obsolete changes and all changes that are\n+present in the given branch. Note that such changes can be recovered from the\n+reflog.\n+\n+Combined with the GC protection that is offered, this is intended to facilitate\n+a workflow that relies on changes instead of branches. Users could choose to\n+work with no local branches and use changes instead - both for mailing list and\n+gerrit workflows.\n+\n+Log\n+---\n+When a commit is shown in git log that is part of a change, it is decorated with\n+extra change information. If it is the head of a change, the name of the change\n+is shown next to the list of branches. If it is obsolete, it is decorated with\n+the text “obsolete, commits behind ”.\n+\n+Log gets a new --obslog argument indicating that the obsolescence graph should\n+be followed instead of the commit graph. This also changes the default\n+formatting options to make them more appropriate for viewing different\n+iterations of the same commit.\n+\n+Pull\n+----\n+\n+Pull gets an --evolve argument that will automatically attempt to run \"evolve\"\n+on any affected branches after pulling.\n+\n+We also introduce an \"evolve\" enum value for the branch..rebase config\n+value. When set, the evolve behavior will happen automatically for that branch\n+after every pull even if the --evolve argument is not used.\n+\n+Next\n+----\n+\n+The \"next\" command will reset HEAD to a non-obsolete commit that refers to this\n+change as its parent. If there is more than one such change, the user will be\n+prompted. If given the --evolve argument, the next commit will be evolved if\n+necessary first.\n+\n+The \"next\" command can be thought of as the opposite of\n+\"git reset --hard HEAD^\" in that it navigates to a child commit rather than a\n+parent.\n+\n+Other options considered\n+========================\n+We considered several other options for storing the obsolescence graph. This\n+section describes the other options and why they were rejected.\n+\n+Commit header\n+-------------\n+Add an “obsoletes” field to the commit header that points backwards from a\n+commit to the previous commits it obsoletes.\n+\n+Pros:\n+- Very simple\n+- Easy to traverse from a commit to the previous commits it obsoletes.\n+Cons:\n+- Adds a cost to the storage format, even for commits where the change history\n+ is uninteresting.\n+- Unconditionally prevents the change history from being garbage collected.\n+- Always causes the change history to be shared when pushing or pulling changes.\n+\n+Git notes\n+---------\n+Instead of storing obsolescence information in metacommits, the metacommit\n+content could go in a new notes namespace - say refs/notes/metacommit. Each note\n+would contain the list of obsolete and origin parents, and an automerger could\n+be supplied to make it easy to merge the metacommit notes from different remotes.\n+\n+Pros:\n+- Easy to locate all commits obsoleted by a given commit (since there would only\n+ be one metacommit for any given commit).\n+Cons:\n+- Wrong GC behavior (obsolete commits wouldn’t automatically be retained by GC)\n+ unless we introduced a special case for these kinds of notes.\n+- No way to selectively share or pull the metacommits for one specific change.\n+ It would be all-or-nothing, which would be expensive. This could be addressed\n+ by changes to the protocol, but this would be invasive.\n+- Requires custom auto-merging behavior on fetch.\n+\n+Tags\n+----\n+Put the content of the metacommit in a message attached to tag on the\n+replacement commit. This is very similar to the git notes approach and has the\n+same pros and cons.\n+\n+Simple forward references\n+-------------------------\n+Record an edge from an obsolete commit to its replacement in this form:\n+\n+refs/obsoletes/\n+\n+pointing to commit as an indication that B is the replacement for the\n+obsolete commit A.\n+\n+Pros:\n+- Protects from being garbage collected.\n+- Fast lookup for the evolve operation, without additional search structures\n+ (“what is the replacement for ?” is very fast).\n+\n+Cons:\n+- Can’t represent divergence (which is a P0 requirement).\n+- Creates lots of refs (which can be inefficient)\n+- Doesn’t provide a way to fetch only refs for a specific change.\n+- The obslog command requires a search of all refs.\n+\n+Complex forward references\n+--------------------------\n+Record an edge from an obsolete commit to its replacement in this form:\n+\n+refs/obsoletes//obs_\n+\n+Pointing to commit as an indication that B is the replacement for obsolete\n+commit A.\n+\n+Pros:\n+- Permits sharing and fetching refs for only a specific change.\n+- Supports divergence\n+- Protects from being garbage collected.\n+\n+Cons:\n+- Creates lots of refs, which is inefficient.\n+- Doesn’t provide a good lookup structure for lookups in either direction.\n+\n+Backward references\n+-------------------\n+Record an edge from a replacement commit to the obsolete one in this form:\n+\n+refs/obsolescences/\n+\n+Cons:\n+- Doesn’t provide a way to resolve divergence (which is a P0 requirement).\n+- Doesn’t protect from being garbage collected (which could be fixed by\n+ combining this with a refs/metas namespace, as in the metacommit variant).\n+\n+Obsolescences file\n+------------------\n+Create a custom file (or files) in .git recording obsolescences.\n+\n+Pros:\n+- Can store exactly the information we want with exactly the performance we want\n+ for all operations. For example, there could be a disk-based hashtable\n+ permitting constant time lookups in either direction.\n+\n+Cons:\n+- Handling GC, pushing, and pulling would all require custom solutions. GC\n+ issues could be addressed with a repository format extension.\n+\n+Squash points\n+-------------\n+We create and update change branches in refs/metas them at the same time we\n+would in the metacommit proposal. However, rather than pointing to a metacommit\n+branch they point to normal commits and are treated as “squash points” - markers\n+for sequences of commits intended to be squashed together on submission.\n+\n+Amends and rebases work differently than they do now. Rather than actually\n+containing the desired state of a commit, they contain a delta from the previous\n+version along with a squash point indicating that the preceding changes are\n+intended to be squashed on submission. Specifically, amends would become new\n+changes and rebases would become merge commits with the old commit and new\n+parent as parents.\n+\n+When the changes are finally submitted, the squashes are executed, producing the\n+final version of the commit.\n+\n+In addition to the squash points, git would maintain a set of “nosquash” tags\n+for commits that were used as ancestors of a change that are not meant to be\n+included in the squash.\n+\n+For example, if we have this commit graph:\n+\n+A(...)\n+B(parent=A)\n+C(parent=B)\n+\n+...and we amend B to produce D, we’d get:\n+\n+A(...)\n+B(parent=A)\n+C(parent=B)\n+D(parent=B)\n+\n+...along with a new change branch indicating D should be squashed with its\n+parents when submitted:\n+\n+metas/changeB = D\n+metas/changeC = C\n+\n+We’d also create a nosquash tag for A indicating that A shouldn’t be included\n+when changeB is squashed.\n+\n+If a user amends the change again, they’d get:\n+\n+A(...)\n+B(parent=A)\n+C(parent=B)\n+D(parent=B)\n+E(parent=D)\n+\n+metas/changeB = E\n+metas/changeC = C\n+\n+Pros:\n+- Good GC behavior.\n+- Provides a natural way to share changes (they’re just normal branches).\n+- Merge-base works automatically without special cases.\n+- Rewriting the obslog would be easy using existing git commands.\n+- No new data types needed.\n+Cons:\n+- No way to connect the squashed version of a change to the original, so no way\n+ to automatically clean up old changes. This also means users lose all benefits\n+ of the evolve command if they prematurely squash their commits. This may occur\n+ if a user thinks a change is ready for submission, squashes it, and then later\n+ discovers an additional change to make.\n+- Histories would look very cluttered (users would see all previous edits to\n+ their commit in the commit log, and all previous rebases would show up as\n+ merges). Could be quite hard for users to tell what is going on. (Possible\n+ fix: also implement a new smart log feature that displays the log as though\n+ the squashes had occurred).\n+- Need to change the current behavior of current commands (like amend and\n+ rebase) in ways that will be unexpected to many users.\n-- \n2.20.1.495.gaa96b0ce6b-goog\n\n"},{"id":"367771","messageId":"20190127194415.171035-2-sxenos@google.com","threadId":"50338","inReplyTo":"20190127194415.171035-1-sxenos@google.com","subject":"[PATCH v3 2/8] sha1-array: Implement oid_array_readonly_contains","fromName":"","fromEmail":"sxenos@google.com","sentAt":"2019-01-27T19:44:09Z","receivedAt":"2019-01-27T19:44:23Z","isPatch":true,"sender":{"key":"sxenos@google.com","avatar":null},"body":"From: Stefan Xenos \n\nImplement a \"readonly_contains\" function for oid_array that won't\nsort the array if it is unsorted. This can be used to test containment in\nthe rare situations where the array order matters.\n\nThe function has intentionally been given a name that is more cumbersome\nthan the \"lookup\" function, which is what most callers will will want\nin most situations.\n\nSigned-off-by: Stefan Xenos \n---\n sha1-array.c | 15 +++++++++++++++\n sha1-array.h | 2 ++\n t/helper/test-sha1-array.c | 6 ++++++\n t/t0064-sha1-array.sh | 22 ++++++++++++++++++++++\n 4 files changed, 45 insertions(+)\n\ndiff --git a/sha1-array.c b/sha1-array.c\nindex b94e0ec0f5..071fce7e90 100644\n--- a/sha1-array.c\n+++ b/sha1-array.c\n@@ -26,6 +26,21 @@ static const unsigned char *sha1_access(size_t index, void *table)\n \treturn array[index].hash;\n }\n \n+int oid_array_readonly_contains(const struct oid_array* array,\n+\tconst struct object_id* oid)\n+{\n+\tint i;\n+\tif (array->sorted) {\n+\t\treturn sha1_pos(oid->hash, array->oid, array->nr, sha1_access) >= 0;\n+\t}\n+\tfor (i = 0; i < array->nr; i++) {\n+\t\tif (hashcmp(array->oid[i].hash, oid->hash) == 0) {\n+\t\t\treturn 1;\n+\t\t}\n+\t}\n+\treturn 0;\n+}\n+\n int oid_array_lookup(struct oid_array *array, const struct object_id *oid)\n {\n \tif (!array->sorted)\ndiff --git a/sha1-array.h b/sha1-array.h\nindex 232bf95017..7273bd5151 100644\n--- a/sha1-array.h\n+++ b/sha1-array.h\n@@ -13,6 +13,8 @@ struct oid_array {\n void oid_array_append(struct oid_array *array, const struct object_id *oid);\n int oid_array_lookup(struct oid_array *array, const struct object_id *oid);\n void oid_array_clear(struct oid_array *array);\n+int oid_array_readonly_contains(const struct oid_array* array,\n+\tconst struct object_id* oid);\n \n typedef int (*for_each_oid_fn)(const struct object_id *oid,\n \t\t\t void *data);\ndiff --git a/t/helper/test-sha1-array.c b/t/helper/test-sha1-array.c\nindex ad5e69f9d3..fefb1c984f 100644\n--- a/t/helper/test-sha1-array.c\n+++ b/t/helper/test-sha1-array.c\n@@ -25,10 +25,16 @@ int cmd__sha1_array(int argc, const char **argv)\n \t\t\tif (get_oid_hex(arg, &oid))\n \t\t\t\tdie(\"not a hexadecimal SHA1: %s\", arg);\n \t\t\tprintf(\"%d\\n\", oid_array_lookup(&array, &oid));\n+\t\t} else if (skip_prefix(line.buf, \"readonly_contains \", &arg)) {\n+\t\t\tif (get_oid_hex(arg, &oid))\n+\t\t\t\tdie(\"not a hexadecimal SHA1: %s\", arg);\n+\t\t\tprintf(\"%d\\n\", oid_array_readonly_contains(&array, &oid));\n \t\t} else if (!strcmp(line.buf, \"clear\"))\n \t\t\toid_array_clear(&array);\n \t\telse if (!strcmp(line.buf, \"for_each_unique\"))\n \t\t\toid_array_for_each_unique(&array, print_oid, NULL);\n+\t\telse if (!strcmp(line.buf, \"for_each\"))\n+\t\t\toid_array_for_each(&array, print_oid, NULL);\n \t\telse\n \t\t\tdie(\"unknown command: %s\", line.buf);\n \t}\ndiff --git a/t/t0064-sha1-array.sh b/t/t0064-sha1-array.sh\nindex 5dda570b9a..c1bac6fcdd 100755\n--- a/t/t0064-sha1-array.sh\n+++ b/t/t0064-sha1-array.sh\n@@ -32,6 +32,28 @@ test_expect_success 'ordered enumeration with duplicate suppression' '\n \ttest_cmp expect actual\n '\n \n+test_expect_success 'readonly_contains finds existing' '\n+\techo 1 > expect &&\n+\techoid \"\" 88 44 aa 55 >> expect &&\n+\t{\n+\t\techoid append 88 44 aa 55 &&\n+\t\techoid readonly_contains 55 &&\n+\t\techo for_each\n+\t} | test-tool sha1-array >actual &&\n+\ttest_cmp expect actual\n+'\n+\n+test_expect_success 'readonly_contains non-existing query' '\n+\techo 0 > expect &&\n+\techoid \"\" 88 44 aa 55 >> expect &&\n+\t{\n+\t\techoid append 88 44 aa 55 &&\n+\t\techoid readonly_contains 33 &&\n+\t\techo for_each\n+\t} | test-tool sha1-array >actual &&\n+\ttest_cmp expect actual\n+'\n+\n test_expect_success 'lookup' '\n \t{\n \t\techoid append 88 44 aa 55 &&\n-- \n2.20.1.495.gaa96b0ce6b-goog\n\n"},{"id":"367772","messageId":"20190127194415.171035-3-sxenos@google.com","threadId":"50338","inReplyTo":"20190127194415.171035-1-sxenos@google.com","subject":"[PATCH v3 3/8] ref-filter: Add the metas namespace to ref-filter","fromName":"","fromEmail":"sxenos@google.com","sentAt":"2019-01-27T19:44:10Z","receivedAt":"2019-01-27T19:44:26Z","isPatch":true,"sender":{"key":"sxenos@google.com","avatar":null},"body":"From: Stefan Xenos \n\nThe metas namespace will contain refs for changes in progress. Add\nsupport for searching this namespace.\n\nSigned-off-by: Stefan Xenos \n---\n ref-filter.c | 8 ++++++--\n ref-filter.h | 5 +++--\n 2 files changed, 9 insertions(+), 4 deletions(-)\n\ndiff --git a/ref-filter.c b/ref-filter.c\nindex 422a9c9ae3..4d7bd06880 100644\n--- a/ref-filter.c\n+++ b/ref-filter.c\n@@ -1925,7 +1925,8 @@ static int ref_kind_from_refname(const char *refname)\n \t} ref_kind[] = {\n \t\t{ \"refs/heads/\" , FILTER_REFS_BRANCHES },\n \t\t{ \"refs/remotes/\" , FILTER_REFS_REMOTES },\n-\t\t{ \"refs/tags/\", FILTER_REFS_TAGS}\n+\t\t{ \"refs/tags/\", FILTER_REFS_TAGS },\n+\t\t{ \"refs/metas/\", FILTER_REFS_CHANGES }\n \t};\n \n \tif (!strcmp(refname, \"HEAD\"))\n@@ -1943,7 +1944,8 @@ static int filter_ref_kind(struct ref_filter *filter, const char *refname)\n {\n \tif (filter->kind == FILTER_REFS_BRANCHES ||\n \t filter->kind == FILTER_REFS_REMOTES ||\n-\t filter->kind == FILTER_REFS_TAGS)\n+\t filter->kind == FILTER_REFS_TAGS ||\n+\t filter->kind == FILTER_REFS_CHANGES )\n \t\treturn filter->kind;\n \treturn ref_kind_from_refname(refname);\n }\n@@ -2128,6 +2130,8 @@ int filter_refs(struct ref_array *array, struct ref_filter *filter, unsigned int\n \t\t\tret = for_each_fullref_in(\"refs/remotes/\", ref_filter_handler, &ref_cbdata, broken);\n \t\telse if (filter->kind == FILTER_REFS_TAGS)\n \t\t\tret = for_each_fullref_in(\"refs/tags/\", ref_filter_handler, &ref_cbdata, broken);\n+\t\telse if (filter->kind == FILTER_REFS_CHANGES)\n+\t\t\tret = for_each_fullref_in(\"refs/metas/\", ref_filter_handler, &ref_cbdata, broken);\n \t\telse if (filter->kind & FILTER_REFS_ALL)\n \t\t\tret = for_each_fullref_in_pattern(filter, ref_filter_handler, &ref_cbdata, broken);\n \t\tif (!ret && (filter->kind & FILTER_REFS_DETACHED_HEAD))\ndiff --git a/ref-filter.h b/ref-filter.h\nindex 85c8ebc3b9..19a3e57845 100644\n--- a/ref-filter.h\n+++ b/ref-filter.h\n@@ -18,9 +18,10 @@\n #define FILTER_REFS_BRANCHES 0x0004\n #define FILTER_REFS_REMOTES 0x0008\n #define FILTER_REFS_OTHERS 0x0010\n-#define FILTER_REFS_ALL (FILTER_REFS_TAGS | FILTER_REFS_BRANCHES | \\\n-\t\t\t\t FILTER_REFS_REMOTES | FILTER_REFS_OTHERS)\n #define FILTER_REFS_DETACHED_HEAD 0x0020\n+#define FILTER_REFS_CHANGES 0X0040\n+#define FILTER_REFS_ALL (FILTER_REFS_TAGS | FILTER_REFS_BRANCHES | \\\n+\t\t\t\t FILTER_REFS_REMOTES | FILTER_REFS_CHANGES | FILTER_REFS_OTHERS)\n #define FILTER_REFS_KIND_MASK (FILTER_REFS_ALL | FILTER_REFS_DETACHED_HEAD)\n \n struct atom_value;\n-- \n2.20.1.495.gaa96b0ce6b-goog\n\n"},{"id":"367773","messageId":"20190127194415.171035-4-sxenos@google.com","threadId":"50338","inReplyTo":"20190127194415.171035-1-sxenos@google.com","subject":"[PATCH v3 4/8] evolve: Add support for parsing metacommits","fromName":"","fromEmail":"sxenos@google.com","sentAt":"2019-01-27T19:44:11Z","receivedAt":"2019-01-27T19:44:28Z","isPatch":true,"sender":{"key":"sxenos@google.com","avatar":null},"body":"From: Stefan Xenos \n\nThis patch adds the get_metacommit_content method, which can classify\ncommits as either metacommits or normal commits, determine whether they\nare abandoned, and extract the content commit's object id from the\nmetacommit.\n\nSigned-off-by: Stefan Xenos \n---\n Makefile | 1 +\n metacommit-parser.c | 87 +++++++++++++++++++++++++++++++++++++++++++++\n metacommit-parser.h | 16 +++++++++\n 3 files changed, 104 insertions(+)\n create mode 100644 metacommit-parser.c\n create mode 100644 metacommit-parser.h\n\ndiff --git a/Makefile b/Makefile\nindex 1a44c811aa..7ffc383f2b 100644\n--- a/Makefile\n+++ b/Makefile\n@@ -919,6 +919,7 @@ LIB_OBJS += merge.o\n LIB_OBJS += merge-blobs.o\n LIB_OBJS += merge-recursive.o\n LIB_OBJS += mergesort.o\n+LIB_OBJS += metacommit-parser.o\n LIB_OBJS += midx.o\n LIB_OBJS += name-hash.o\n LIB_OBJS += negotiator/default.o\ndiff --git a/metacommit-parser.c b/metacommit-parser.c\nnew file mode 100644\nindex 0000000000..5013a108a3\n--- /dev/null\n+++ b/metacommit-parser.c\n@@ -0,0 +1,87 @@\n+#include \"cache.h\"\n+#include \"metacommit-parser.h\"\n+#include \"commit.h\"\n+\n+/*\n+ * Search the commit buffer for a line starting with the given key. Unlike\n+ * find_commit_header, this also searches the commit message body.\n+ */\n+static const char *find_key(const char *msg, const char *key, size_t *out_len)\n+{\n+\tint key_len = strlen(key);\n+\tconst char *line = msg;\n+\n+\twhile (line) {\n+\t\tconst char *eol = strchrnul(line, '\\n');\n+\n+\t\tif (eol - line > key_len &&\n+\t\t\t\t!strncmp(line, key, key_len) &&\n+\t\t\t\tline[key_len] == ' ') {\n+\t\t\t*out_len = eol - line - key_len - 1;\n+\t\t\treturn line + key_len + 1;\n+\t\t}\n+\t\tline = *eol ? eol + 1 : NULL;\n+\t}\n+\treturn NULL;\n+}\n+\n+static struct commit *get_commit_by_index(struct commit_list *to_search, int index)\n+{\n+\twhile (to_search && index) {\n+\t\tto_search = to_search->next;\n+\t\t--index;\n+\t}\n+\n+\treturn to_search->item;\n+}\n+\n+/*\n+ * Writes the content parent's object id to \"content\".\n+ * Returns the metacommit type. See the METACOMMIT_TYPE_* constants.\n+ */\n+int get_metacommit_content(\n+\tstruct commit *commit, struct object_id *content)\n+{\n+\tconst char *buffer = get_commit_buffer(commit, NULL);\n+\tsize_t parent_types_size;\n+\tconst char *parent_types = find_key(buffer, \"parent-type\",\n+\t\t&parent_types_size);\n+\tconst char *end;\n+\tint index = 0;\n+\tint ret;\n+\tstruct commit *content_parent;\n+\n+\tif (!parent_types) {\n+\t\treturn METACOMMIT_TYPE_NONE;\n+\t}\n+\n+\tend = &(parent_types[parent_types_size]);\n+\n+\twhile (1) {\n+\t\tchar next = *parent_types;\n+\t\tif (next == ' ') {\n+\t\t\tindex++;\n+\t\t}\n+\t\tif (next == 'c') {\n+\t\t\tret = METACOMMIT_TYPE_NORMAL;\n+\t\t\tbreak;\n+\t\t}\n+\t\tif (next == 'a') {\n+\t\t\tret = METACOMMIT_TYPE_ABANDONED;\n+\t\t\tbreak;\n+\t\t}\n+\t\tparent_types++;\n+\t\tif (parent_types >= end) {\n+\t\t\treturn METACOMMIT_TYPE_NONE;\n+\t\t}\n+\t}\n+\n+\tcontent_parent = get_commit_by_index(commit->parents, index);\n+\n+\tif (!content_parent) {\n+\t\treturn METACOMMIT_TYPE_NONE;\n+\t}\n+\n+\toidcpy(content, &(content_parent->object.oid));\n+\treturn ret;\n+}\ndiff --git a/metacommit-parser.h b/metacommit-parser.h\nnew file mode 100644\nindex 0000000000..e546f5a7e7\n--- /dev/null\n+++ b/metacommit-parser.h\n@@ -0,0 +1,16 @@\n+#ifndef METACOMMIT_PARSER_H\n+#define METACOMMIT_PARSER_H\n+\n+// Indicates a normal commit (non-metacommit)\n+#define METACOMMIT_TYPE_NONE 0\n+// Indicates a metacommit with normal content (non-abandoned)\n+#define METACOMMIT_TYPE_NORMAL 1\n+// Indicates a metacommit with abandoned content\n+#define METACOMMIT_TYPE_ABANDONED 2\n+\n+struct commit;\n+\n+extern int get_metacommit_content(\n+\tstruct commit *commit, struct object_id *content);\n+\n+#endif\n-- \n2.20.1.495.gaa96b0ce6b-goog\n\n"},{"id":"367774","messageId":"20190127194415.171035-5-sxenos@google.com","threadId":"50338","inReplyTo":"20190127194415.171035-1-sxenos@google.com","subject":"[PATCH v3 5/8] evolve: Add the change-table structure","fromName":"","fromEmail":"sxenos@google.com","sentAt":"2019-01-27T19:44:12Z","receivedAt":"2019-01-27T19:44:31Z","isPatch":true,"sender":{"key":"sxenos@google.com","avatar":null},"body":"From: Stefan Xenos \n\nA change table stores a list of changes, and supports efficient lookup\nfrom a commit hash to the list of changes that reference that commit\ndirectly.\n\nIt can be used to look up content commits or metacommits at the head\nof a change, but does not support lookup of commits referenced as part\nof the commit history.\n\nSigned-off-by: Stefan Xenos \n---\n Makefile | 1 +\n change-table.c | 207 +++++++++++++++++++++++++++++++++++++++++++++++++\n change-table.h | 138 +++++++++++++++++++++++++++++++++\n 3 files changed, 346 insertions(+)\n create mode 100644 change-table.c\n create mode 100644 change-table.h\n\ndiff --git a/Makefile b/Makefile\nindex 7ffc383f2b..09cfd3ef1b 100644\n--- a/Makefile\n+++ b/Makefile\n@@ -844,6 +844,7 @@ LIB_OBJS += branch.o\n LIB_OBJS += bulk-checkin.o\n LIB_OBJS += bundle.o\n LIB_OBJS += cache-tree.o\n+LIB_OBJS += change-table.o\n LIB_OBJS += chdir-notify.o\n LIB_OBJS += checkout.o\n LIB_OBJS += color.o\ndiff --git a/change-table.c b/change-table.c\nnew file mode 100644\nindex 0000000000..6daff5f58c\n--- /dev/null\n+++ b/change-table.c\n@@ -0,0 +1,207 @@\n+#include \"cache.h\"\n+#include \"change-table.h\"\n+#include \"commit.h\"\n+#include \"ref-filter.h\"\n+#include \"metacommit-parser.h\"\n+\n+void change_table_init(struct change_table *to_initialize)\n+{\n+\tmemset(to_initialize, 0, sizeof(*to_initialize));\n+\tmem_pool_init(&(to_initialize->memory_pool), 0);\n+\tto_initialize->memory_pool->block_alloc = 4*1024 - sizeof(struct mp_block);\n+\toidmap_init(&(to_initialize->oid_to_metadata_index), 0);\n+\tstring_list_init(&(to_initialize->refname_to_change_head), 1);\n+}\n+\n+static void change_list_clear(struct change_list *to_clear) {\n+\tstring_list_clear(&to_clear->additional_refnames, 0);\n+}\n+\n+static void commit_change_list_entry_clear(\n+\tstruct commit_change_list_entry *to_clear) {\n+\tchange_list_clear(&(to_clear->changes));\n+}\n+\n+static void change_head_array_clear(struct change_head_array *to_clear)\n+{\n+\tFREE_AND_NULL(to_clear->array);\n+}\n+\n+void change_table_clear(struct change_table *to_clear)\n+{\n+\tstruct oidmap_iter iter;\n+\tstruct commit_change_list_entry *next;\n+\tfor (next = oidmap_iter_first(&to_clear->oid_to_metadata_index, &iter);\n+\t\tnext;\n+\t\tnext = oidmap_iter_next(&iter)) {\n+\n+\t\tcommit_change_list_entry_clear(next);\n+\t}\n+\n+\toidmap_free(&to_clear->oid_to_metadata_index, 0);\n+\tstring_list_clear(&(to_clear->refname_to_change_head), 0);\n+\tchange_head_array_clear(&to_clear->heads);\n+\tmem_pool_discard(to_clear->memory_pool, 0);\n+}\n+\n+/*\n+ * Appends a new, empty, change_head struct to the end of the given array.\n+ * Returns the index of the newly-added struct.\n+ */\n+static int change_head_array_append(struct change_head_array *to_add)\n+{\n+\tint index = to_add->nr++;\n+\tstruct change_head *new_head;\n+\tALLOC_GROW(to_add->array, to_add->nr, to_add->alloc);\n+\tnew_head = &(to_add->array[index]);\n+\tmemset(new_head, 0, sizeof(*new_head));\n+\treturn index;\n+}\n+\n+static void add_head_to_commit(struct change_table *to_modify,\n+\tconst struct object_id *to_add, const char *refname)\n+{\n+\tstruct commit_change_list_entry *entry;\n+\n+\t// Note: the indices in the map are 1-based. 0 is used to indicate a missing\n+\t// element.\n+\tentry = oidmap_get(&(to_modify->oid_to_metadata_index), to_add);\n+\tif (!entry) {\n+\t\tentry = mem_pool_calloc(to_modify->memory_pool, 1,\n+\t\t\tsizeof(*entry));\n+\t\toidcpy(&entry->entry.oid, to_add);\n+\t\toidmap_put(&(to_modify->oid_to_metadata_index), entry);\n+\t\tstring_list_init(&(entry->changes.additional_refnames), 0);\n+\t}\n+\n+\tif (entry->changes.first_refname == NULL) {\n+\t\tentry->changes.first_refname = refname;\n+\t} else {\n+\t\tstring_list_insert(&entry->changes.additional_refnames, refname);\n+\t}\n+}\n+\n+void change_table_add(struct change_table *to_modify, const char *refname,\n+\tstruct commit *to_add)\n+{\n+\tstruct change_head *new_head;\n+\tstruct string_list_item *new_item;\n+\tlong index;\n+\tint metacommit_type;\n+\n+\tindex = change_head_array_append(&to_modify->heads);\n+\tnew_head = &(to_modify->heads.array[index]);\n+\n+\toidcpy(&new_head->head, &(to_add->object.oid));\n+\n+\tmetacommit_type = get_metacommit_content(to_add, &new_head->content);\n+\tif (metacommit_type == METACOMMIT_TYPE_NONE) {\n+\t\toidcpy(&new_head->content, &(to_add->object.oid));\n+\t}\n+\tnew_head->abandoned = (metacommit_type == METACOMMIT_TYPE_ABANDONED);\n+\tnew_head->remote = starts_with(refname, \"refs/remote/\");\n+\tnew_head->hidden = starts_with(refname, \"refs/hiddenmetas/\");\n+\n+\tnew_item = string_list_insert(&to_modify->refname_to_change_head, refname);\n+\tnew_item->util = (void*)index;\n+\t// Use pointers to the copy of the string we're retaining locally\n+\trefname = new_item->string;\n+\n+\tif (!oideq(&new_head->content, &new_head->head)) {\n+\t\tadd_head_to_commit(to_modify, &(new_head->content), refname);\n+\t}\n+\tadd_head_to_commit(to_modify, &(new_head->head), refname);\n+}\n+\n+void change_table_add_all_visible(struct change_table *to_modify,\n+\tstruct repository* repo)\n+{\n+\tstruct ref_filter filter;\n+\tconst char *name_patterns[] = {NULL};\n+\tmemset(&filter, 0, sizeof(filter));\n+\tfilter.kind = FILTER_REFS_CHANGES;\n+\tfilter.name_patterns = name_patterns;\n+\n+\tchange_table_add_matching_filter(to_modify, repo, &filter);\n+}\n+\n+void change_table_add_matching_filter(struct change_table *to_modify,\n+\tstruct repository* repo, struct ref_filter *filter)\n+{\n+\tstruct ref_array matching_refs;\n+\tint i;\n+\n+\tmemset(&matching_refs, 0, sizeof(matching_refs));\n+\tfilter_refs(&matching_refs, filter, filter->kind);\n+\n+\t// Determine the object id for the latest content commit for each change.\n+\t// Fetch the commit at the head of each change ref. If it's a normal commit,\n+\t// that's the commit we want. If it's a metacommit, locate its content parent\n+\t// and use that.\n+\n+\tfor (i = 0; i < matching_refs.nr; i++) {\n+\t\tstruct ref_array_item *item = matching_refs.items[i];\n+\t\tstruct commit *commit = item->commit;\n+\n+\t\tcommit = lookup_commit_reference_gently(repo, &(item->objectname), 1);\n+\n+\t\tif (commit != NULL) {\n+\t\t\tchange_table_add(to_modify, item->refname, commit);\n+\t\t}\n+\t}\n+\n+\tref_array_clear(&matching_refs);\n+}\n+\n+static int return_true_callback(const char *refname, void *cb_data)\n+{\n+\treturn 1;\n+}\n+\n+int change_table_has_change_referencing(struct change_table *changes,\n+\tconst struct object_id *referenced_commit_id)\n+{\n+\treturn for_each_change_referencing(changes, referenced_commit_id,\n+\t\treturn_true_callback, NULL);\n+}\n+\n+int for_each_change_referencing(struct change_table *table,\n+\tconst struct object_id *referenced_commit_id, each_change_fn fn, void *cb_data)\n+{\n+\tconst struct change_list *changes;\n+\tint i;\n+\tint retvalue;\n+\tstruct commit_change_list_entry *entry;\n+\n+\tentry = oidmap_get(&table->oid_to_metadata_index,\n+\t\treferenced_commit_id);\n+\t// If this commit isn't referenced by any changes, it won't be in the map\n+\tif (!entry) {\n+\t\treturn 0;\n+\t}\n+\tchanges = &(entry->changes);\n+\tif (changes->first_refname == NULL) {\n+\t\treturn 0;\n+\t}\n+\tretvalue = fn(changes->first_refname, cb_data);\n+\tfor (i = 0; retvalue == 0 && i < changes->additional_refnames.nr; i++) {\n+\t\tretvalue = fn(changes->additional_refnames.items[i].string, cb_data);\n+\t}\n+\treturn retvalue;\n+}\n+\n+struct change_head* get_change_head(struct change_table *heads,\n+\tconst char* refname)\n+{\n+\tstruct string_list_item *item = string_list_lookup(\n+\t\t&heads->refname_to_change_head, refname);\n+\tlong index;\n+\n+\tif (!item) {\n+\t\treturn NULL;\n+\t}\n+\n+\tindex = (long)item->util;\n+\treturn &(heads->heads.array[index]);\n+}\n+\ndiff --git a/change-table.h b/change-table.h\nnew file mode 100644\nindex 0000000000..85bb19c3bf\n--- /dev/null\n+++ b/change-table.h\n@@ -0,0 +1,138 @@\n+#ifndef CHANGE_TABLE_H\n+#define CHANGE_TABLE_H\n+\n+#include \"oidmap.h\"\n+\n+struct commit;\n+struct ref_filter;\n+\n+/*\n+ * This struct holds a list of change refs. The first element is stored inline,\n+ * to optimize for small lists.\n+ */\n+struct change_list {\n+\t/* Ref name for the first change in the list, or null if none.\n+\t *\n+\t * This field is private. Use for_each_change_in to read.\n+\t */\n+\tconst char* first_refname;\n+\t/* List of additional change refs. Note that this is empty if the list\n+\t * contains 0 or 1 elements.\n+\t *\n+\t * This field is private. Use for_each_change_in to read.\n+\t */\n+\tstruct string_list additional_refnames;\n+};\n+\n+/*\n+ * Holds information about the head of a single change.\n+ */\n+struct change_head {\n+\t/*\n+\t * The location pointed to by the head of the change. May be a commit or a\n+\t * metacommit.\n+\t */\n+\tstruct object_id head;\n+\t/*\n+\t * The content commit for the latest commit in the change. Always points to a\n+\t * real commit, never a metacommit.\n+\t */\n+\tstruct object_id content;\n+\t/*\n+\t * Abandoned: indicates that the content commit should be removed from the\n+\t * history.\n+\t *\n+\t * Hidden: indicates that the change is an inactive change from the\n+\t * hiddenmetas namespace. Such changes will be hidden from the user by\n+\t * default.\n+\t *\n+\t * Deleted: indicates that the change has been removed from the repository.\n+\t * That is the ref was deleted since the time this struct was created. Such\n+\t * entries should be ignored.\n+\t */\n+\tint abandoned:1,\n+\t\thidden:1,\n+\t\tremote:1,\n+\t\tdeleted:1;\n+};\n+\n+/*\n+ * An array of change_head.\n+ */\n+struct change_head_array {\n+\tstruct change_head* array;\n+\tint nr;\n+\tint alloc;\n+};\n+\n+/*\n+ * Holds the list of change refs whose content points to a particular content\n+ * commit.\n+ */\n+struct commit_change_list_entry {\n+\tstruct oidmap_entry entry;\n+\tstruct change_list changes;\n+};\n+\n+/*\n+ * Holds information about the heads of each change, and permits effecient\n+ * lookup from a commit to the changes that reference it directly.\n+ *\n+ * All fields should be considered private. Use the change_table functions\n+ * to interact with this struct.\n+ */\n+struct change_table {\n+\t/**\n+\t * Memory pool for the objects allocated by the change table.\n+\t */\n+\tstruct mem_pool *memory_pool;\n+\t/* Map object_id to commit_change_list_entry structs. */\n+\tstruct oidmap oid_to_metadata_index;\n+\t/* List of ref names. The util value is an int index into change_metadata\n+\t * array.\n+\t */\n+\tstruct string_list refname_to_change_head;\n+\t/* change_head structures for each head */\n+\tstruct change_head_array heads;\n+};\n+\n+extern void change_table_init(struct change_table *to_initialize);\n+extern void change_table_clear(struct change_table *to_clear);\n+\n+/* Adds the given change head to the change_table struct */\n+extern void change_table_add(struct change_table *to_modify,\n+\tconst char *refname, struct commit *target);\n+\n+/* Adds the non-hidden local changes to the given change_table struct.\n+ */\n+extern void change_table_add_all_visible(struct change_table *to_modify,\n+\tstruct repository *repo);\n+\n+/*\n+ * Adds all changes matching the given ref filter to the given change_table\n+ * struct.\n+ */\n+extern void change_table_add_matching_filter(struct change_table *to_modify,\n+\tstruct repository* repo, struct ref_filter *filter);\n+\n+typedef int each_change_fn(const char *refname, void *cb_data);\n+\n+extern int change_table_has_change_referencing(struct change_table *changes,\n+\tconst struct object_id *referenced_commit_id);\n+\n+/* Iterates over all changes that reference the given commit. For metacommits,\n+ * this is the list of changes that point directly to that metacommit.\n+ * For normal commits, this is the list of changes that have this commit as\n+ * their latest content.\n+ */\n+extern int for_each_change_referencing(struct change_table *heads,\n+\tconst struct object_id *referenced_commit_id, each_change_fn fn, void *cb_data);\n+\n+/**\n+ * Returns the change head for the given refname. Returns NULL if no such change\n+ * exists.\n+ */\n+extern struct change_head* get_change_head(struct change_table *heads,\n+\tconst char* refname);\n+\n+#endif\n-- \n2.20.1.495.gaa96b0ce6b-goog\n\n"},{"id":"367775","messageId":"20190127194415.171035-6-sxenos@google.com","threadId":"50338","inReplyTo":"20190127194415.171035-1-sxenos@google.com","subject":"[PATCH v3 6/8] evolve: Add support for writing metacommits","fromName":"","fromEmail":"sxenos@google.com","sentAt":"2019-01-27T19:44:13Z","receivedAt":"2019-01-27T19:44:33Z","isPatch":true,"sender":{"key":"sxenos@google.com","avatar":null},"body":"From: Stefan Xenos \n\nmetacommit.c supports the creation of metacommits and\nadds the API needed to create and update changes.\n\nCreate the \"modify_change\" function that can be called from modification\ncommands like \"rebase\" and \"git amend\" to record obsolescences in the\nchange graph.\n\nCreate the \"record_metacommit\" function for recording more complicated\ncommit relationships in the commit graph.\n\nCreate the \"write_metacommit\" function for low-level creation of\nmetacommits.\n\nSigned-off-by: Stefan Xenos \n---\n Makefile | 1 +\n metacommit.c | 370 +++++++++++++++++++++++++++++++++++++++++++++++++++\n metacommit.h | 39 ++++++\n 3 files changed, 410 insertions(+)\n create mode 100644 metacommit.c\n create mode 100644 metacommit.h\n\ndiff --git a/Makefile b/Makefile\nindex 09cfd3ef1b..a6be1780c5 100644\n--- a/Makefile\n+++ b/Makefile\n@@ -920,6 +920,7 @@ LIB_OBJS += merge.o\n LIB_OBJS += merge-blobs.o\n LIB_OBJS += merge-recursive.o\n LIB_OBJS += mergesort.o\n+LIB_OBJS += metacommit.o\n LIB_OBJS += metacommit-parser.o\n LIB_OBJS += midx.o\n LIB_OBJS += name-hash.o\ndiff --git a/metacommit.c b/metacommit.c\nnew file mode 100644\nindex 0000000000..409c2fa03f\n--- /dev/null\n+++ b/metacommit.c\n@@ -0,0 +1,370 @@\n+#include \"cache.h\"\n+#include \"metacommit.h\"\n+#include \"commit.h\"\n+#include \"change-table.h\"\n+#include \"refs.h\"\n+\n+void init_metacommit_data(struct metacommit_data *state)\n+{\n+\tmemset(state, 0, sizeof(*state));\n+}\n+\n+void clear_metacommit_data(struct metacommit_data *state)\n+{\n+\toid_array_clear(&state->replace);\n+\toid_array_clear(&state->origin);\n+}\n+\n+static void compute_default_change_name(struct commit *initial_commit,\n+\tstruct strbuf* result)\n+{\n+\tconst char *buffer = get_commit_buffer(initial_commit, NULL);\n+\tconst char *subject;\n+\tconst char *eol;\n+\tint len;\n+\tfind_commit_subject(buffer, &subject);\n+\teol = strchrnul(subject, '\\n');\n+\tfor (len = 0;subject < eol && len < 10; ++subject, ++len) {\n+\t\tchar next = *subject;\n+\t\tif (isspace(next)) {\n+\t\t\tcontinue;\n+\t\t}\n+\n+\t\tstrbuf_addch(result, next);\n+\t}\n+}\n+\n+/*\n+ * Computes a change name for a change rooted at the given initial commit. Good\n+ * change names should be memorable, unique, and easy to type. They are not\n+ * required to match the commit comment.\n+ */\n+static void compute_change_name(struct commit *initial_commit, struct strbuf* result)\n+{\n+\tstruct strbuf default_name;\n+\tstruct object_id unused;\n+\n+\tstrbuf_init(&default_name, 0);\n+\tif (initial_commit) {\n+\t\tcompute_default_change_name(initial_commit, &default_name);\n+\t} else {\n+\t\tstrbuf_addstr(&default_name, \"change\");\n+\t}\n+\tstrbuf_addstr(result, \"refs/metas/\");\n+\tstrbuf_addstr(result, default_name.buf);\n+\n+\t// If there is already a change of this name, append a suffix\n+\tif (!read_ref(result->buf, &unused)) {\n+\t\tint suffix = 2;\n+\t\tint original_length = result->len;\n+\n+\t\twhile (1) {\n+\t\t\tstrbuf_addf(result, \"%d\", suffix);\n+\t\t\tif (read_ref(result->buf, &unused)) {\n+\t\t\t\tbreak;\n+\t\t\t}\n+\t\t\tstrbuf_remove(result, original_length, result->len - original_length);\n+\t\t\t++suffix;\n+\t\t}\n+\t}\n+\n+\tstrbuf_release(&default_name);\n+}\n+\n+struct resolve_metacommit_callback_data\n+{\n+\tstruct change_table* active_changes;\n+\tstruct string_list *changes;\n+\tstruct oid_array *heads;\n+};\n+\n+static int resolve_metacommit_callback(const char *refname, void *cb_data)\n+{\n+\tstruct resolve_metacommit_callback_data *data = (struct resolve_metacommit_callback_data *)cb_data;\n+\tstruct change_head *chhead;\n+\n+\tchhead = get_change_head(data->active_changes, refname);\n+\n+\tif (data->changes) {\n+\t\tstring_list_append(data->changes, refname)->util = &(chhead->head);\n+\t}\n+\tif (data->heads) {\n+\t\toid_array_append(data->heads, &(chhead->head));\n+\t}\n+\n+\treturn 0;\n+}\n+\n+/*\n+ * Produces the final form of a metacommit based on the current change refs.\n+ */\n+static void resolve_metacommit(\n+\tstruct repository* repo,\n+\tstruct change_table* active_changes,\n+\tconst struct metacommit_data *to_resolve,\n+\tstruct metacommit_data *resolved_output,\n+\tstruct string_list *to_advance,\n+\tint allow_append)\n+{\n+\tint i;\n+\tint len = to_resolve->replace.nr;\n+\tstruct resolve_metacommit_callback_data cbdata;\n+\tint old_change_list_length = to_advance->nr;\n+\tstruct commit* content;\n+\n+\toidcpy(&resolved_output->content, &to_resolve->content);\n+\n+\t// First look for changes that point to any of the replacement edges in the\n+\t// metacommit. These will be the changes that get advanced by this metacommit.\n+\tresolved_output->abandoned = to_resolve->abandoned;\n+\tcbdata.active_changes = active_changes;\n+\tcbdata.changes = to_advance;\n+\tcbdata.heads = &(resolved_output->replace);\n+\n+\tif (allow_append) {\n+\t\tfor (i = 0; i < len; i++) {\n+\t\t\tint old_number = resolved_output->replace.nr;\n+\t\t\tfor_each_change_referencing(active_changes, &(to_resolve->replace.oid[i]),\n+\t\t\t\tresolve_metacommit_callback, &cbdata);\n+\t\t\t// If no changes were found, use the unresolved value\n+\t\t\tif (old_number == resolved_output->replace.nr) {\n+\t\t\t\toid_array_append(&(resolved_output->replace), &(to_resolve->replace.oid[i]));\n+\t\t\t}\n+\t\t}\n+\t}\n+\n+\tcbdata.changes = NULL;\n+\tcbdata.heads = &(resolved_output->origin);\n+\n+\tlen = to_resolve->origin.nr;\n+\tfor (i = 0; i < len; i++) {\n+\t\tint old_number = resolved_output->origin.nr;\n+\t\tfor_each_change_referencing(active_changes, &(to_resolve->origin.oid[i]),\n+\t\t\tresolve_metacommit_callback, &cbdata);\n+\t\tif (old_number == resolved_output->origin.nr) {\n+\t\t\toid_array_append(&(resolved_output->origin), &(to_resolve->origin.oid[i]));\n+\t\t}\n+\t}\n+\n+\t// If no changes were advanced by this metacommit, we'll need to create a new\n+\t// one.\n+\tif (to_advance->nr == old_change_list_length) {\n+\t\tstruct strbuf change_name;\n+\n+\t\tstrbuf_init(&change_name, 80);\n+\t\tcontent = lookup_commit_reference_gently(repo, &(to_resolve->content), 1);\n+\n+\t\tcompute_change_name(content, &change_name);\n+\t\tstring_list_append(to_advance, change_name.buf);\n+\t\tstrbuf_release(&change_name);\n+\t}\n+}\n+\n+static void lookup_commits(\n+\tstruct repository *repo,\n+\tstruct oid_array *to_lookup,\n+\tstruct commit_list **result)\n+{\n+\tint i = to_lookup->nr;\n+\n+\twhile (--i >= 0) {\n+\t\tstruct object_id *next = &(to_lookup->oid[i]);\n+\t\tstruct commit *commit = lookup_commit_reference_gently(repo, next, 1);\n+\t\tcommit_list_insert(commit, result);\n+\t}\n+}\n+\n+#define PARENT_TYPE_PREFIX \"parent-type \"\n+\n+/*\n+ * Creates a new metacommit object with the given content. Writes the object\n+ * id of the newly-created commit to result.\n+ */\n+int write_metacommit(struct repository *repo, struct metacommit_data *state,\n+\tstruct object_id *result)\n+{\n+\tstruct commit_list *parents = NULL;\n+\tstruct strbuf comment;\n+\tint i;\n+\tstruct commit *content;\n+\n+\tstrbuf_init(&comment, strlen(PARENT_TYPE_PREFIX)\n+\t\t+ 1 + 2 * (state->origin.nr + state->replace.nr));\n+\tlookup_commits(repo, &state->origin, &parents);\n+\tlookup_commits(repo, &state->replace, &parents);\n+\tcontent = lookup_commit_reference_gently(repo, &state->content, 1);\n+\tif (!content) {\n+\t\tstrbuf_release(&comment);\n+\t\tfree_commit_list(parents);\n+\t\treturn -1;\n+\t}\n+\tcommit_list_insert(content, &parents);\n+\n+\tstrbuf_addstr(&comment, PARENT_TYPE_PREFIX);\n+\tstrbuf_addstr(&comment, state->abandoned ? \"a\" : \"c\");\n+\tfor (i = 0; i < state->replace.nr; i++) {\n+\t\tstrbuf_addstr(&comment, \" r\");\n+\t}\n+\n+\tfor (i = 0; i < state->origin.nr; i++) {\n+\t\tstrbuf_addstr(&comment, \" o\");\n+\t}\n+\n+\t// The parents list will be freed by this call\n+\tcommit_tree(comment.buf, comment.len, repo->hash_algo->empty_tree, parents,\n+\t\tresult, NULL, NULL);\n+\n+\tstrbuf_release(&comment);\n+\treturn 0;\n+}\n+\n+/*\n+ * Returns true iff the given metacommit is abandoned, has one or more origin\n+ * parents, or has one or more replacement parents.\n+ */\n+static int is_nontrivial_metacommit(struct metacommit_data *state)\n+{\n+\treturn state->replace.nr || state->origin.nr || state->abandoned;\n+}\n+\n+/*\n+ * Records the relationships described by the given metacommit in the\n+ * repository.\n+ *\n+ * If override_change is NULL (the default), an attempt will be made\n+ * to append to existing changes wherever possible instead of creating new ones.\n+ * If override_change is non-null, only the given change ref will be updated.\n+ *\n+ * options is a bitwise combination of the UPDATE_OPTION_* flags.\n+ */\n+int record_metacommit(struct repository *repo,\n+\tconst struct metacommit_data *metacommit,\n+\tconst char* override_change, int options, struct strbuf *err)\n+{\n+\tstatic const char *msg = \"updating change\";\n+\tstruct metacommit_data resolved_metacommit;\n+\tstruct string_list changes;\n+\tstruct object_id commit_target;\n+\tstruct ref_transaction *transaction = NULL;\n+\tstruct object_id old_head_working;\n+\tconst struct object_id *old_head;\n+\tstruct change_table chtable;\n+\tint i;\n+\tint ret = 0;\n+\tint force = (options & UPDATE_OPTION_FORCE);\n+\n+\tinit_metacommit_data(&resolved_metacommit);\n+\tstring_list_init(&changes, 1);\n+\n+\tchange_table_init(&chtable);\n+\n+\tchange_table_add_all_visible(&chtable, repo);\n+\n+\tresolve_metacommit(repo, &chtable, metacommit, &resolved_metacommit, &changes,\n+\t\t(options & UPDATE_OPTION_NOAPPEND) == 0);\n+\n+\tif (override_change) {\n+\t\told_head = &old_head_working;\n+\t\tstring_list_clear(&changes, 0);\n+\t\tif (get_oid_committish(override_change, &old_head_working)) {\n+\t\t\t// ...then this is a newly-created change\n+\t\t\told_head = &null_oid;\n+\t\t} else if (!force) {\n+\t\t\tif (!oid_array_readonly_contains(&(resolved_metacommit.replace),\n+\t\t\t\t&old_head_working)) {\n+\t\t\t\t// Attempted non-fast-forward change\n+\t\t\t\tstrbuf_addf(err, _(\"non-fast-forward update to '%s'\"),\n+\t\t\t\t\toverride_change);\n+\t\t\t\tret = -1;\n+\t\t\t\tgoto cleanup;\n+\t\t\t}\n+\t\t}\n+\t\t// The expected \"current\" head of the change is stored in the util pointer\n+\t\tstring_list_append(&changes, override_change)->util = (void*)old_head;\n+\t}\n+\n+\tif (is_nontrivial_metacommit(&resolved_metacommit)) {\n+\t\t// If there are any origin or replacement parents, create a new metacommit\n+\t\t// object.\n+\t\tif (write_metacommit(repo, &resolved_metacommit, &commit_target) < 0) {\n+\t\t\tret = -1;\n+\t\t\tgoto cleanup;\n+\t\t}\n+\t} else {\n+\t\t// If the metacommit would only contain a content commit, point to the\n+\t\t// commit itself rather than creating a trivial metacommit.\n+\t\toidcpy(&commit_target, &(resolved_metacommit.content));\n+\t}\n+\n+\t// If a change already exists with this target and we're not forcing an\n+\t// update to some specific override_change && change, there's nothing to do.\n+\tif (!override_change \n+\t\t&& change_table_has_change_referencing(&chtable, &commit_target)) {\n+\t\t// Not an error\n+\t\tgoto cleanup;\n+\t}\n+\n+\ttransaction = ref_transaction_begin(err);\n+\n+\t// Update the refs for each affected change\n+\tif (!transaction) {\n+\t\tret = -1;\n+\t} else {\n+\t\tfor (i = 0; i < changes.nr; i++) {\n+\t\t\tstruct string_list_item *it = &(changes.items[i]);\n+\n+\t\t\t// The expected current head of the change is stored in the util pointer.\n+\t\t\t// It is null if the change should be newly-created.\n+\t\t\tif (it->util) {\n+\t\t\t\tif (ref_transaction_update(transaction, it->string, &commit_target,\n+\t\t\t\t\tforce ? NULL : it->util, 0, msg, err)) {\n+\n+\t\t\t\t\tret = -1;\n+\t\t\t\t}\n+\t\t\t} else {\n+\t\t\t\tif (ref_transaction_create(transaction, it->string,\n+\t\t\t\t\t&commit_target, 0, msg, err)) {\n+\n+\t\t\t\t\tret = -1;\n+\t\t\t\t}\n+\t\t\t}\n+\t\t}\n+\n+\t\tif (!ret) {\n+\t\t\tif (ref_transaction_commit(transaction, err)) {\n+\t\t\t\tret = -1;\n+\t\t\t}\n+\t\t}\n+\t}\n+\n+cleanup:\n+\tref_transaction_free(transaction);\n+\tstring_list_clear(&changes, 0);\n+\tclear_metacommit_data(&resolved_metacommit);\n+\tchange_table_clear(&chtable);\n+\treturn ret;\n+}\n+\n+/*\n+ * Should be invoked after a command that has \"modify\" semantics - commands that\n+ * create a new commit based on an old commit and treat the new one as a\n+ * replacement for the old one. This method records the replacement in the\n+ * change graph, such that a future evolve operation will rebase children of\n+ * the old commit onto the new commit.\n+ */\n+void modify_change(\n+\tstruct repository *repo,\n+\tconst struct object_id *old_commit,\n+\tconst struct object_id *new_commit,\n+\tstruct strbuf *err)\n+{\n+\tstruct metacommit_data metacommit;\n+\n+\tinit_metacommit_data(&metacommit);\n+\toidcpy(&(metacommit.content), new_commit);\n+\toid_array_append(&(metacommit.replace), old_commit);\n+\n+\trecord_metacommit(repo, &metacommit, NULL, 0, err);\n+\n+\tclear_metacommit_data(&metacommit);\n+}\ndiff --git a/metacommit.h b/metacommit.h\nnew file mode 100644\nindex 0000000000..1d4be9cdfb\n--- /dev/null\n+++ b/metacommit.h\n@@ -0,0 +1,39 @@\n+#ifndef METACOMMIT_H\n+#define METACOMMIT_H\n+\n+// If specified, non-fast-forward changes are permitted.\n+#define UPDATE_OPTION_FORCE 0x0001\n+// If specified, no attempt will be made to append to existing changes.\n+// Normally, if a metacommit points to a commit in its replace or origin\n+// list and an existing change points to that same commit as its content, the\n+// new metacommit will attempt to append to that same change. This may replace\n+// the commit parent with one or more metacommits from the head of the appended\n+// changes. This option disables this behavior, and will always create a new\n+// change rather than reusing existing changes.\n+#define UPDATE_OPTION_NOAPPEND 0x0002\n+\n+// Metacommit Data\n+\n+struct metacommit_data {\n+\tstruct object_id content;\n+\tstruct oid_array replace;\n+\tstruct oid_array origin;\n+\tint abandoned;\n+};\n+\n+extern void init_metacommit_data(struct metacommit_data *state);\n+\n+extern void clear_metacommit_data(struct metacommit_data *state);\n+\n+extern int record_metacommit(struct repository *repo,\n+\tconst struct metacommit_data *metacommit,\n+\tconst char* override_change, int options, struct strbuf *err);\n+\n+extern void modify_change(struct repository *repo,\n+\tconst struct object_id *old_commit, const struct object_id *new_commit,\n+\tstruct strbuf *err);\n+\n+extern int write_metacommit(struct repository *repo, struct metacommit_data *state,\n+\tstruct object_id *result);\n+\n+#endif\n-- \n2.20.1.495.gaa96b0ce6b-goog\n\n"},{"id":"367776","messageId":"20190127194415.171035-7-sxenos@google.com","threadId":"50338","inReplyTo":"20190127194415.171035-1-sxenos@google.com","subject":"[PATCH v3 7/8] evolve: Implement the git change command","fromName":"","fromEmail":"sxenos@google.com","sentAt":"2019-01-27T19:44:14Z","receivedAt":"2019-01-27T19:44:37Z","isPatch":true,"sender":{"key":"sxenos@google.com","avatar":null},"body":"From: Stefan Xenos \n\nImplement the git change update command, which\nare sufficient for constructing change graphs.\n\nFor example, to create a new change (a stable name) that refers to HEAD:\n\ngit change update -c HEAD\n\nTo record a rebase or amend in the change graph:\n\ngit change update -c -r \n\nTo record a cherry-pick in the change graph:\n\ngit change update -c -o \n\nSigned-off-by: Stefan Xenos \n---\n .gitignore | 1 +\n Makefile | 1 +\n builtin.h | 1 +\n builtin/change.c | 175 +++++++++++++++++++++++++++++++++++++++++++++++\n git.c | 1 +\n 5 files changed, 179 insertions(+)\n create mode 100644 builtin/change.c\n\ndiff --git a/.gitignore b/.gitignore\nindex 0d77ea5894..8a084ac38b 100644\n--- a/.gitignore\n+++ b/.gitignore\n@@ -26,6 +26,7 @@\n /git-branch\n /git-bundle\n /git-cat-file\n+/git-change\n /git-check-attr\n /git-check-ignore\n /git-check-mailmap\ndiff --git a/Makefile b/Makefile\nindex a6be1780c5..d6fab30eca 100644\n--- a/Makefile\n+++ b/Makefile\n@@ -1035,6 +1035,7 @@ BUILTIN_OBJS += builtin/blame.o\n BUILTIN_OBJS += builtin/branch.o\n BUILTIN_OBJS += builtin/bundle.o\n BUILTIN_OBJS += builtin/cat-file.o\n+BUILTIN_OBJS += builtin/change.o\n BUILTIN_OBJS += builtin/check-attr.o\n BUILTIN_OBJS += builtin/check-ignore.o\n BUILTIN_OBJS += builtin/check-mailmap.o\ndiff --git a/builtin.h b/builtin.h\nindex 6538932e99..d2d39d9da8 100644\n--- a/builtin.h\n+++ b/builtin.h\n@@ -137,6 +137,7 @@ extern int cmd_blame(int argc, const char **argv, const char *prefix);\n extern int cmd_branch(int argc, const char **argv, const char *prefix);\n extern int cmd_bundle(int argc, const char **argv, const char *prefix);\n extern int cmd_cat_file(int argc, const char **argv, const char *prefix);\n+extern int cmd_change(int argc, const char **argv, const char *prefix);\n extern int cmd_checkout(int argc, const char **argv, const char *prefix);\n extern int cmd_checkout_index(int argc, const char **argv, const char *prefix);\n extern int cmd_check_attr(int argc, const char **argv, const char *prefix);\ndiff --git a/builtin/change.c b/builtin/change.c\nnew file mode 100644\nindex 0000000000..ff7eb3b113\n--- /dev/null\n+++ b/builtin/change.c\n@@ -0,0 +1,175 @@\n+#include \"builtin.h\"\n+#include \"ref-filter.h\"\n+#include \"parse-options.h\"\n+#include \"metacommit.h\"\n+#include \"config.h\"\n+\n+static const char * const builtin_change_usage[] = {\n+\tN_(\"git change update [--force] [--replace ...] [--origin ...] [--content ]\"),\n+\tNULL\n+};\n+\n+static const char * const builtin_update_usage[] = {\n+\tN_(\"git change update [--force] [--replace ...] [--origin ...] [--content ]\"),\n+\tNULL\n+};\n+\n+struct update_state {\n+\tint options;\n+\tconst char* change;\n+\tconst char* content;\n+\tstruct string_list replace;\n+\tstruct string_list origin;\n+};\n+\n+static void init_update_state(struct update_state *state)\n+{\n+\tmemset(state, 0, sizeof(*state));\n+\tstate->content = \"HEAD\";\n+\tstring_list_init(&state->replace, 0);\n+\tstring_list_init(&state->origin, 0);\n+}\n+\n+static void clear_update_state(struct update_state *state)\n+{\n+\tstring_list_clear(&state->replace, 0);\n+\tstring_list_clear(&state->origin, 0);\n+}\n+\n+static int update_option_parse_replace(const struct option *opt,\n+\t\t\t\t\t\t\tconst char *arg, int unset)\n+{\n+\tstruct update_state *state = opt->value;\n+\tstring_list_append(&state->replace, arg);\n+\treturn 0;\n+}\n+\n+static int update_option_parse_origin(const struct option *opt,\n+\t\t\t\t\t\t\tconst char *arg, int unset)\n+{\n+\tstruct update_state *state = opt->value;\n+\tstring_list_append(&state->origin, arg);\n+\treturn 0;\n+}\n+\n+static int resolve_commit(const char *committish, struct object_id *result)\n+{\n+\tstruct commit *commit;\n+\tif (get_oid_committish(committish, result))\n+\t\tdie(_(\"Failed to resolve '%s' as a valid revision.\"), committish);\n+\tcommit = lookup_commit_reference(the_repository, result);\n+\tif (!commit)\n+\t\tdie(_(\"Could not parse object '%s'.\"), committish);\n+\toidcpy(result, &commit->object.oid);\n+\treturn 0;\n+}\n+\n+static void resolve_commit_list(const struct string_list *commitsish_list,\n+\tstruct oid_array* result)\n+{\n+\tint i;\n+\tfor (i = 0; i < commitsish_list->nr; i++) {\n+\t\tstruct string_list_item *item = &commitsish_list->items[i];\n+\t\tstruct object_id next;\n+\t\tresolve_commit(item->string, &next);\n+\t\toid_array_append(result, &next);\n+\t}\n+}\n+\n+/*\n+ * Given the command-line options for the update command, fills in a\n+ * metacommit_data with the corresponding changes.\n+ */\n+static void get_metacommit_from_command_line(\n+\tconst struct update_state* commands, struct metacommit_data *result)\n+{\n+\tresolve_commit(commands->content, &(result->content));\n+\tresolve_commit_list(&(commands->replace), &(result->replace));\n+\tresolve_commit_list(&(commands->origin), &(result->origin));\n+}\n+\n+static int perform_update(\n+\tstruct repository *repo,\n+\tconst struct update_state *state,\n+\tstruct strbuf *err)\n+{\n+\tstruct metacommit_data metacommit;\n+\tint ret;\n+\n+\tinit_metacommit_data(&metacommit);\n+\n+\tget_metacommit_from_command_line(state, &metacommit);\n+\n+\tret = record_metacommit(repo, &metacommit, state->change, state->options, err);\n+\n+\tclear_metacommit_data(&metacommit);\n+\n+\treturn ret;\n+}\n+\n+static int change_update(int argc, const char **argv, const char* prefix)\n+{\n+\tint result;\n+\tint force = 0;\n+\tint newchange = 0;\n+\tstruct strbuf err = STRBUF_INIT;\n+\tstruct update_state state;\n+\tstruct option options[] = {\n+\t\t{ OPTION_CALLBACK, 'r', \"replace\", &state, N_(\"commit\"),\n+\t\t\tN_(\"marks the given commit as being obsolete\"),\n+\t\t\t0, update_option_parse_replace },\n+\t\t{ OPTION_CALLBACK, 'o', \"origin\", &state, N_(\"commit\"),\n+\t\t\tN_(\"marks the given commit as being the origin of this commit\"),\n+\t\t\t0, update_option_parse_origin },\n+\t\tOPT_BOOL('F', \"force\", &force,\n+\t\t\tN_(\"overwrite an existing change of the same name\")),\n+\t\tOPT_STRING('c', \"content\", &state.content, N_(\"commit\"),\n+\t\t\t\t N_(\"identifies the new content commit for the change\")),\n+\t\tOPT_STRING('g', \"change\", &state.change, N_(\"commit\"),\n+\t\t\t\t N_(\"name of the change to update\")),\n+\t\tOPT_BOOL('n', \"new\", &newchange,\n+\t\t\tN_(\"create a new change - do not append to any existing change\")),\n+\t\tOPT_END()\n+\t};\n+\n+\tinit_update_state(&state);\n+\n+\targc = parse_options(argc, argv, prefix, options, builtin_update_usage, 0);\n+\n+\tif (force) state.options |= UPDATE_OPTION_FORCE;\n+\tif (newchange) state.options |= UPDATE_OPTION_NOAPPEND;\n+\n+\tresult = perform_update(the_repository, &state, &err);\n+\n+\tif (result < 0) {\n+\t\terror(\"%s\", err.buf);\n+\t\tstrbuf_release(&err);\n+\t}\n+\n+\tclear_update_state(&state);\n+\n+\treturn result;\n+}\n+\n+int cmd_change(int argc, const char **argv, const char *prefix)\n+{\n+\t// No options permitted before subcommand currently\n+\tstruct option options[] = {\n+\t\tOPT_END()\n+\t};\n+\tint result = 1;\n+\n+\targc = parse_options(argc, argv, prefix, options, builtin_change_usage,\n+\t\tPARSE_OPT_STOP_AT_NON_OPTION);\n+\n+\tif (argc < 1)\n+\t\tusage_with_options(builtin_change_usage, options);\n+\telse if (!strcmp(argv[0], \"update\"))\n+\t\tresult = change_update(argc, argv, prefix);\n+\telse {\n+\t\terror(_(\"Unknown subcommand: %s\"), argv[0]);\n+\t\tusage_with_options(builtin_change_usage, options);\n+\t}\n+\n+\treturn result ? 1 : 0;\n+}\ndiff --git a/git.c b/git.c\nindex 0ce0e13f0f..f59f887238 100644\n--- a/git.c\n+++ b/git.c\n@@ -453,6 +453,7 @@ static struct cmd_struct commands[] = {\n \t{ \"branch\", cmd_branch, RUN_SETUP | DELAY_PAGER_CONFIG },\n \t{ \"bundle\", cmd_bundle, RUN_SETUP_GENTLY | NO_PARSEOPT },\n \t{ \"cat-file\", cmd_cat_file, RUN_SETUP },\n+\t{ \"change\", cmd_change, RUN_SETUP },\n \t{ \"check-attr\", cmd_check_attr, RUN_SETUP },\n \t{ \"check-ignore\", cmd_check_ignore, RUN_SETUP | NEED_WORK_TREE },\n \t{ \"check-mailmap\", cmd_check_mailmap, RUN_SETUP },\n-- \n2.20.1.495.gaa96b0ce6b-goog\n\n"},{"id":"367777","messageId":"20190127194415.171035-8-sxenos@google.com","threadId":"50338","inReplyTo":"20190127194415.171035-1-sxenos@google.com","subject":"[PATCH v3 8/8] evolve: Add the git change list command","fromName":"","fromEmail":"sxenos@google.com","sentAt":"2019-01-27T19:44:15Z","receivedAt":"2019-01-27T19:44:38Z","isPatch":true,"sender":{"key":"sxenos@google.com","avatar":null},"body":"From: Stefan Xenos \n\nThis command lists the ongoing changes from the refs/metas\nnamespace.\n\nSigned-off-by: Stefan Xenos \n---\n builtin/change.c | 53 ++++++++++++++++++++++++++++++++++++++++++++++++\n 1 file changed, 53 insertions(+)\n\ndiff --git a/builtin/change.c b/builtin/change.c\nindex ff7eb3b113..b63fe98665 100644\n--- a/builtin/change.c\n+++ b/builtin/change.c\n@@ -5,15 +5,66 @@\n #include \"config.h\"\n \n static const char * const builtin_change_usage[] = {\n+\tN_(\"git change list [...]\"),\n \tN_(\"git change update [--force] [--replace ...] [--origin ...] [--content ]\"),\n \tNULL\n };\n \n+static const char * const builtin_list_usage[] = {\n+\tN_(\"git change list [...]\"),\n+\tNULL\n+};\n+\n static const char * const builtin_update_usage[] = {\n \tN_(\"git change update [--force] [--replace ...] [--origin ...] [--content ]\"),\n \tNULL\n };\n \n+static int change_list(int argc, const char **argv, const char* prefix)\n+{\n+\tstruct option options[] = {\n+\t\tOPT_END()\n+\t};\n+\tstruct ref_filter filter;\n+\t// TODO: Sorting temporarily disabled. See comments, below.\n+\t//struct ref_sorting *sorting = ref_default_sorting();\n+\tstruct ref_format format = REF_FORMAT_INIT;\n+\tstruct ref_array array;\n+\tint i;\n+\n+\targc = parse_options(argc, argv, prefix, options, builtin_list_usage, 0);\n+\n+\tsetup_ref_filter_porcelain_msg();\n+\n+\tmemset(&filter, 0, sizeof(filter));\n+\tmemset(&array, 0, sizeof(array));\n+\n+\tfilter.kind = FILTER_REFS_CHANGES;\n+\tfilter.name_patterns = argv;\n+\n+\tfilter_refs(&array, &filter, FILTER_REFS_CHANGES);\n+\n+\t// TODO: This causes a crash. It sets one of the atom_value handlers to\n+\t// something invalid, which causes a crash later when we call\n+\t// show_ref_array_item. Figure out why this happens and put back the sorting.\n+\t//ref_array_sort(sorting, &array);\n+\n+\tif (!format.format) {\n+\t\tformat.format = \"%(refname:lstrip=1)\";\n+\t}\n+\n+\tif (verify_ref_format(&format))\n+\t\tdie(_(\"unable to parse format string\"));\n+\n+\tfor (i = 0; i < array.nr; i++) {\n+\t\tshow_ref_array_item(array.items[i], &format);\n+\t}\n+\n+\tref_array_clear(&array);\n+\n+\treturn 0;\n+}\n+\n struct update_state {\n \tint options;\n \tconst char* change;\n@@ -164,6 +215,8 @@ int cmd_change(int argc, const char **argv, const char *prefix)\n \n \tif (argc < 1)\n \t\tusage_with_options(builtin_change_usage, options);\n+\telse if (!strcmp(argv[0], \"list\"))\n+\t\tresult = change_list(argc, argv, prefix);\n \telse if (!strcmp(argv[0], \"update\"))\n \t\tresult = change_update(argc, argv, prefix);\n \telse {\n-- \n2.20.1.495.gaa96b0ce6b-goog\n\n"},{"id":"367809","messageId":"xmqqlg35czaf.fsf@gitster-ct.c.googlers.com","threadId":"50338","inReplyTo":"20190127194415.171035-2-sxenos@google.com","subject":"Re: [PATCH v3 2/8] sha1-array: Implement oid_array_readonly_contains","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2019-01-28T02:05:12Z","receivedAt":"2019-01-28T02:05:17Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"sxenos@google.com writes:\n\n> Subject: Re: [PATCH v3 2/8] sha1-array: Implement oid_array_readonly_contains\n\nStyle: s/: Implement/: implement/\n\n> From: Stefan Xenos \n\nThis line wants to say \"Stefan Xenos \" to match\nS-o-b below (I am assuming that you are following your employer's\nopen source recommendation to contribute under your corp address).\n\nPerhaps you would want user.email set to the corp address? I am\ntaking the above as an indication that the commits we are seeing\nhere have been made under your @gmail.com address and that is why\ngit-send-email is adding the in-body header.\n\n> diff --git a/sha1-array.c b/sha1-array.c\n> index b94e0ec0f5..071fce7e90 100644\n> --- a/sha1-array.c\n> +++ b/sha1-array.c\n> @@ -26,6 +26,21 @@ static const unsigned char *sha1_access(size_t index, void *table)\n> \treturn array[index].hash;\n> }\n> \n> +int oid_array_readonly_contains(const struct oid_array* array,\n> +\tconst struct object_id* oid)\n> +{\n> +\tint i;\n\nStyle: blank between decl and first stmt, perhaps?\n\n> +\tif (array->sorted) {\n> +\t\treturn sha1_pos(oid->hash, array->oid, array->nr, sha1_access) >= 0;\n\nNo need for {} around a single statement.\n\n> +\t}\n> +\tfor (i = 0; i < array->nr; i++) {\n> +\t\tif (hashcmp(array->oid[i].hash, oid->hash) == 0) {\n> +\t\t\treturn 1;\n\nLikewise.\n\n> +\t\t}\n> +\t}\n> +\treturn 0;\n> +}\n> ...\n> diff --git a/t/t0064-sha1-array.sh b/t/t0064-sha1-array.sh\n> index 5dda570b9a..c1bac6fcdd 100755\n> --- a/t/t0064-sha1-array.sh\n> +++ b/t/t0064-sha1-array.sh\n> @@ -32,6 +32,28 @@ test_expect_success 'ordered enumeration with duplicate suppression' '\n> \ttest_cmp expect actual\n> '\n> \n> +test_expect_success 'readonly_contains finds existing' '\n> +\techo 1 > expect &&\n\nStyle: no SP between redirection operator and its target, i.e.\n\n\techo 1 >expect &&\n\n> +\techoid \"\" 88 44 aa 55 >> expect &&\n\nLikewise.\n\n\techoid \"\" 88 44 aa 55 >>expect &&\n\n"},{"id":"367810","messageId":"xmqqef8xcza9.fsf@gitster-ct.c.googlers.com","threadId":"50338","inReplyTo":"20190127194415.171035-4-sxenos@google.com","subject":"Re: [PATCH v3 4/8] evolve: Add support for parsing metacommits","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2019-01-28T02:05:18Z","receivedAt":"2019-01-28T02:05:23Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"sxenos@google.com writes:\n\n> +/*\n> + * Search the commit buffer for a line starting with the given key. Unlike\n> + * find_commit_header, this also searches the commit message body.\n> + */\n> +static const char *find_key(const char *msg, const char *key, size_t *out_len)\n> +{\n> +\tint key_len = strlen(key);\n> +\tconst char *line = msg;\n> +\n> +\twhile (line) {\n> +\t\tconst char *eol = strchrnul(line, '\\n');\n> +\n> +\t\tif (eol - line > key_len &&\n> +\t\t\t\t!strncmp(line, key, key_len) &&\n\nUse of strncmp() here forces readers to wonder if and why we are\npreparing the code to allow NUL in key[0..key_len] (as line..eol\nwould not, because we just used strchrnul()). But because key_len\nwas computed using strlen(key), there is no valid reason to do so.\nIf the code used memcmp(), it won't waste readers' time.\n\n> +\t\t\t\tline[key_len] == ' ') {\n> +\t\t\t*out_len = eol - line - key_len - 1;\n> +\t\t\treturn line + key_len + 1;\n> +\t\t}\n> +\t\tline = *eol ? eol + 1 : NULL;\n> +\t}\n> +\treturn NULL;\n> +}\n> +\n> +static struct commit *get_commit_by_index(struct commit_list *to_search, int index)\n> +{\n> +\twhile (to_search && index) {\n> +\t\tto_search = to_search->next;\n> +\t\t--index;\n\nStyle: unlike some C++ shop, we tend to use post-increment/decrement\nwhen we do not use the value.\n\n> +\t}\n> +\n> +\treturn to_search->item;\n> +}\n\nIf a maliciously crafted parent-type field has excess ' ' to make\nindex larger than the number of \"parent\" field in the commit object,\nthe while() loop terminates upon noticing that to_search has become\nNULL. And then this return statement dereferences that NULL\npointer.\n\n> +/*\n> + * Writes the content parent's object id to \"content\".\n> + * Returns the metacommit type. See the METACOMMIT_TYPE_* constants.\n> + */\n> +int get_metacommit_content(\n> +\tstruct commit *commit, struct object_id *content)\n> +{\n> +\tconst char *buffer = get_commit_buffer(commit, NULL);\n> +\tsize_t parent_types_size;\n> +\tconst char *parent_types = find_key(buffer, \"parent-type\",\n> +\t\t&parent_types_size);\n> +\tconst char *end;\n> +\tint index = 0;\n> +\tint ret;\n> +\tstruct commit *content_parent;\n> +\n> +\tif (!parent_types) {\n> +\t\treturn METACOMMIT_TYPE_NONE;\n\nUnnecessary brace?\n\n> +\t}\n> +\n> +\tend = &(parent_types[parent_types_size]);\n\nUnnecessary parenthesis?\n\n> +\twhile (1) {\n> +\t\tchar next = *parent_types;\n> +\t\tif (next == ' ') {\n> +\t\t\tindex++;\n> +\t\t}\n> +\t\tif (next == 'c') {\n> +\t\t\tret = METACOMMIT_TYPE_NORMAL;\n> +\t\t\tbreak;\n> +\t\t}\n> +\t\tif (next == 'a') {\n> +\t\t\tret = METACOMMIT_TYPE_ABANDONED;\n> +\t\t\tbreak;\n> +\t\t}\n\nThe parsing of this seems somewhat loose. If there is 'x' on the\nline, this loop spins and consumes it without doing anything, which\nmeans that the same commit with a parent-type field can be encoded\nin different ways by adding arbitrary number of 'x' just after SP\nafter the \"parent-type\" keyword, no?\n\n> +\t\tparent_types++;\n> +\t\tif (parent_types >= end) {\n> +\t\t\treturn METACOMMIT_TYPE_NONE;\n> +\t\t}\n> +\t}\n> +\n> +\tcontent_parent = get_commit_by_index(commit->parents, index);\n> +\n> +\tif (!content_parent) {\n> +\t\treturn METACOMMIT_TYPE_NONE;\n> +\t}\n> +\n> +\toidcpy(content, &(content_parent->object.oid));\n> +\treturn ret;\n> +}\n> diff --git a/metacommit-parser.h b/metacommit-parser.h\n> new file mode 100644\n> index 0000000000..e546f5a7e7\n> --- /dev/null\n> +++ b/metacommit-parser.h\n> @@ -0,0 +1,16 @@\n> +#ifndef METACOMMIT_PARSER_H\n> +#define METACOMMIT_PARSER_H\n> +\n> +// Indicates a normal commit (non-metacommit)\n\nNo C99 // comments please. Not in the header, and not in the code.\n\n> +#define METACOMMIT_TYPE_NONE 0\n> +// Indicates a metacommit with normal content (non-abandoned)\n> +#define METACOMMIT_TYPE_NORMAL 1\n> +// Indicates a metacommit with abandoned content\n> +#define METACOMMIT_TYPE_ABANDONED 2\n> +\n> +struct commit;\n> +\n> +extern int get_metacommit_content(\n> +\tstruct commit *commit, struct object_id *content);\n> +\n> +#endif\n"},{"id":"367817","messageId":"nycvar.QRO.7.76.6.1901280858060.41@tvgsbejvaqbjf.bet","threadId":"50338","inReplyTo":"20190127194415.171035-5-sxenos@google.com","subject":"Re: [PATCH v3 5/8] evolve: Add the change-table structure","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2019-01-28T08:01:02Z","receivedAt":"2019-01-28T08:01:23Z","isPatch":true,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Hi Stefan,\n\nI did not yet have time to study your proposal in detail, but hope to do\nso before the Contributor Summit so that I can have an informed opinion.\n\nJust one thing:\n\nOn Sun, 27 Jan 2019, sxenos@google.com wrote:\n\n> From: Stefan Xenos \n> \n> A change table stores a list of changes, and supports efficient lookup\n> from a commit hash to the list of changes that reference that commit\n> directly.\n> \n> It can be used to look up content commits or metacommits at the head\n> of a change, but does not support lookup of commits referenced as part\n> of the commit history.\n> \n> Signed-off-by: Stefan Xenos \n> ---\n> Makefile | 1 +\n> change-table.c | 207 +++++++++++++++++++++++++++++++++++++++++++++++++\n> change-table.h | 138 +++++++++++++++++++++++++++++++++\n> 3 files changed, 346 insertions(+)\n> create mode 100644 change-table.c\n> create mode 100644 change-table.h\n> \n> diff --git a/Makefile b/Makefile\n> index 7ffc383f2b..09cfd3ef1b 100644\n> --- a/Makefile\n> +++ b/Makefile\n> @@ -844,6 +844,7 @@ LIB_OBJS += branch.o\n> LIB_OBJS += bulk-checkin.o\n> LIB_OBJS += bundle.o\n> LIB_OBJS += cache-tree.o\n> +LIB_OBJS += change-table.o\n> LIB_OBJS += chdir-notify.o\n> LIB_OBJS += checkout.o\n> LIB_OBJS += color.o\n> diff --git a/change-table.c b/change-table.c\n> new file mode 100644\n> index 0000000000..6daff5f58c\n> --- /dev/null\n> +++ b/change-table.c\n> @@ -0,0 +1,207 @@\n> +#include \"cache.h\"\n> +#include \"change-table.h\"\n> +#include \"commit.h\"\n> +#include \"ref-filter.h\"\n> +#include \"metacommit-parser.h\"\n> +\n> +void change_table_init(struct change_table *to_initialize)\n> +{\n> +\tmemset(to_initialize, 0, sizeof(*to_initialize));\n> +\tmem_pool_init(&(to_initialize->memory_pool), 0);\n> +\tto_initialize->memory_pool->block_alloc = 4*1024 - sizeof(struct mp_block);\n> +\toidmap_init(&(to_initialize->oid_to_metadata_index), 0);\n> +\tstring_list_init(&(to_initialize->refname_to_change_head), 1);\n> +}\n> +\n> +static void change_list_clear(struct change_list *to_clear) {\n> +\tstring_list_clear(&to_clear->additional_refnames, 0);\n> +}\n> +\n> +static void commit_change_list_entry_clear(\n> +\tstruct commit_change_list_entry *to_clear) {\n> +\tchange_list_clear(&(to_clear->changes));\n> +}\n> +\n> +static void change_head_array_clear(struct change_head_array *to_clear)\n> +{\n> +\tFREE_AND_NULL(to_clear->array);\n> +}\n> +\n> +void change_table_clear(struct change_table *to_clear)\n> +{\n> +\tstruct oidmap_iter iter;\n> +\tstruct commit_change_list_entry *next;\n> +\tfor (next = oidmap_iter_first(&to_clear->oid_to_metadata_index, &iter);\n> +\t\tnext;\n> +\t\tnext = oidmap_iter_next(&iter)) {\n> +\n> +\t\tcommit_change_list_entry_clear(next);\n> +\t}\n> +\n> +\toidmap_free(&to_clear->oid_to_metadata_index, 0);\n> +\tstring_list_clear(&(to_clear->refname_to_change_head), 0);\n> +\tchange_head_array_clear(&to_clear->heads);\n> +\tmem_pool_discard(to_clear->memory_pool, 0);\n> +}\n> +\n> +/*\n> + * Appends a new, empty, change_head struct to the end of the given array.\n> + * Returns the index of the newly-added struct.\n> + */\n> +static int change_head_array_append(struct change_head_array *to_add)\n> +{\n> +\tint index = to_add->nr++;\n> +\tstruct change_head *new_head;\n> +\tALLOC_GROW(to_add->array, to_add->nr, to_add->alloc);\n> +\tnew_head = &(to_add->array[index]);\n> +\tmemset(new_head, 0, sizeof(*new_head));\n> +\treturn index;\n> +}\n> +\n> +static void add_head_to_commit(struct change_table *to_modify,\n> +\tconst struct object_id *to_add, const char *refname)\n> +{\n> +\tstruct commit_change_list_entry *entry;\n> +\n> +\t// Note: the indices in the map are 1-based. 0 is used to indicate a missing\n> +\t// element.\n> +\tentry = oidmap_get(&(to_modify->oid_to_metadata_index), to_add);\n> +\tif (!entry) {\n> +\t\tentry = mem_pool_calloc(to_modify->memory_pool, 1,\n> +\t\t\tsizeof(*entry));\n> +\t\toidcpy(&entry->entry.oid, to_add);\n> +\t\toidmap_put(&(to_modify->oid_to_metadata_index), entry);\n> +\t\tstring_list_init(&(entry->changes.additional_refnames), 0);\n> +\t}\n> +\n> +\tif (entry->changes.first_refname == NULL) {\n> +\t\tentry->changes.first_refname = refname;\n> +\t} else {\n> +\t\tstring_list_insert(&entry->changes.additional_refnames, refname);\n> +\t}\n> +}\n> +\n> +void change_table_add(struct change_table *to_modify, const char *refname,\n> +\tstruct commit *to_add)\n> +{\n> +\tstruct change_head *new_head;\n> +\tstruct string_list_item *new_item;\n> +\tlong index;\n> +\tint metacommit_type;\n> +\n> +\tindex = change_head_array_append(&to_modify->heads);\n> +\tnew_head = &(to_modify->heads.array[index]);\n> +\n> +\toidcpy(&new_head->head, &(to_add->object.oid));\n> +\n> +\tmetacommit_type = get_metacommit_content(to_add, &new_head->content);\n> +\tif (metacommit_type == METACOMMIT_TYPE_NONE) {\n> +\t\toidcpy(&new_head->content, &(to_add->object.oid));\n> +\t}\n> +\tnew_head->abandoned = (metacommit_type == METACOMMIT_TYPE_ABANDONED);\n> +\tnew_head->remote = starts_with(refname, \"refs/remote/\");\n> +\tnew_head->hidden = starts_with(refname, \"refs/hiddenmetas/\");\n> +\n> +\tnew_item = string_list_insert(&to_modify->refname_to_change_head, refname);\n> +\tnew_item->util = (void*)index;\n\nThis is not good. You are using a `long` here. The 80s called and want\ntheir now-obsolete data types back.\n\nIf you want a data type that can take an integer but also a pointer, use\n`intptr_t` instead.\n\nBut even that is not good practice. What you really want here is to use a\nunion of the data types that you want to store in that `util` field.\n\nThis is not merely academic, your code causes compile errors on Windows:\n\nhttps://dev.azure.com/gitgitgadget/git/_build/results?buildId=400&view=logs&jobId=fd490c07-0b22-5182-fac9-6d67fe1e939b&taskId=ce91d5d6-0c55-50f5-8ab9-6695c03ab102&lineStart=430&lineEnd=440&colStart=1&colEnd=1\n\nCiao,\nJohannes\n\n> +\t// Use pointers to the copy of the string we're retaining locally\n> +\trefname = new_item->string;\n> +\n> +\tif (!oideq(&new_head->content, &new_head->head)) {\n> +\t\tadd_head_to_commit(to_modify, &(new_head->content), refname);\n> +\t}\n> +\tadd_head_to_commit(to_modify, &(new_head->head), refname);\n> +}\n> +\n> +void change_table_add_all_visible(struct change_table *to_modify,\n> +\tstruct repository* repo)\n> +{\n> +\tstruct ref_filter filter;\n> +\tconst char *name_patterns[] = {NULL};\n> +\tmemset(&filter, 0, sizeof(filter));\n> +\tfilter.kind = FILTER_REFS_CHANGES;\n> +\tfilter.name_patterns = name_patterns;\n> +\n> +\tchange_table_add_matching_filter(to_modify, repo, &filter);\n> +}\n> +\n> +void change_table_add_matching_filter(struct change_table *to_modify,\n> +\tstruct repository* repo, struct ref_filter *filter)\n> +{\n> +\tstruct ref_array matching_refs;\n> +\tint i;\n> +\n> +\tmemset(&matching_refs, 0, sizeof(matching_refs));\n> +\tfilter_refs(&matching_refs, filter, filter->kind);\n> +\n> +\t// Determine the object id for the latest content commit for each change.\n> +\t// Fetch the commit at the head of each change ref. If it's a normal commit,\n> +\t// that's the commit we want. If it's a metacommit, locate its content parent\n> +\t// and use that.\n> +\n> +\tfor (i = 0; i < matching_refs.nr; i++) {\n> +\t\tstruct ref_array_item *item = matching_refs.items[i];\n> +\t\tstruct commit *commit = item->commit;\n> +\n> +\t\tcommit = lookup_commit_reference_gently(repo, &(item->objectname), 1);\n> +\n> +\t\tif (commit != NULL) {\n> +\t\t\tchange_table_add(to_modify, item->refname, commit);\n> +\t\t}\n> +\t}\n> +\n> +\tref_array_clear(&matching_refs);\n> +}\n> +\n> +static int return_true_callback(const char *refname, void *cb_data)\n> +{\n> +\treturn 1;\n> +}\n> +\n> +int change_table_has_change_referencing(struct change_table *changes,\n> +\tconst struct object_id *referenced_commit_id)\n> +{\n> +\treturn for_each_change_referencing(changes, referenced_commit_id,\n> +\t\treturn_true_callback, NULL);\n> +}\n> +\n> +int for_each_change_referencing(struct change_table *table,\n> +\tconst struct object_id *referenced_commit_id, each_change_fn fn, void *cb_data)\n> +{\n> +\tconst struct change_list *changes;\n> +\tint i;\n> +\tint retvalue;\n> +\tstruct commit_change_list_entry *entry;\n> +\n> +\tentry = oidmap_get(&table->oid_to_metadata_index,\n> +\t\treferenced_commit_id);\n> +\t// If this commit isn't referenced by any changes, it won't be in the map\n> +\tif (!entry) {\n> +\t\treturn 0;\n> +\t}\n> +\tchanges = &(entry->changes);\n> +\tif (changes->first_refname == NULL) {\n> +\t\treturn 0;\n> +\t}\n> +\tretvalue = fn(changes->first_refname, cb_data);\n> +\tfor (i = 0; retvalue == 0 && i < changes->additional_refnames.nr; i++) {\n> +\t\tretvalue = fn(changes->additional_refnames.items[i].string, cb_data);\n> +\t}\n> +\treturn retvalue;\n> +}\n> +\n> +struct change_head* get_change_head(struct change_table *heads,\n> +\tconst char* refname)\n> +{\n> +\tstruct string_list_item *item = string_list_lookup(\n> +\t\t&heads->refname_to_change_head, refname);\n> +\tlong index;\n> +\n> +\tif (!item) {\n> +\t\treturn NULL;\n> +\t}\n> +\n> +\tindex = (long)item->util;\n> +\treturn &(heads->heads.array[index]);\n> +}\n> +\n> diff --git a/change-table.h b/change-table.h\n> new file mode 100644\n> index 0000000000..85bb19c3bf\n> --- /dev/null\n> +++ b/change-table.h\n> @@ -0,0 +1,138 @@\n> +#ifndef CHANGE_TABLE_H\n> +#define CHANGE_TABLE_H\n> +\n> +#include \"oidmap.h\"\n> +\n> +struct commit;\n> +struct ref_filter;\n> +\n> +/*\n> + * This struct holds a list of change refs. The first element is stored inline,\n> + * to optimize for small lists.\n> + */\n> +struct change_list {\n> +\t/* Ref name for the first change in the list, or null if none.\n> +\t *\n> +\t * This field is private. Use for_each_change_in to read.\n> +\t */\n> +\tconst char* first_refname;\n> +\t/* List of additional change refs. Note that this is empty if the list\n> +\t * contains 0 or 1 elements.\n> +\t *\n> +\t * This field is private. Use for_each_change_in to read.\n> +\t */\n> +\tstruct string_list additional_refnames;\n> +};\n> +\n> +/*\n> + * Holds information about the head of a single change.\n> + */\n> +struct change_head {\n> +\t/*\n> +\t * The location pointed to by the head of the change. May be a commit or a\n> +\t * metacommit.\n> +\t */\n> +\tstruct object_id head;\n> +\t/*\n> +\t * The content commit for the latest commit in the change. Always points to a\n> +\t * real commit, never a metacommit.\n> +\t */\n> +\tstruct object_id content;\n> +\t/*\n> +\t * Abandoned: indicates that the content commit should be removed from the\n> +\t * history.\n> +\t *\n> +\t * Hidden: indicates that the change is an inactive change from the\n> +\t * hiddenmetas namespace. Such changes will be hidden from the user by\n> +\t * default.\n> +\t *\n> +\t * Deleted: indicates that the change has been removed from the repository.\n> +\t * That is the ref was deleted since the time this struct was created. Such\n> +\t * entries should be ignored.\n> +\t */\n> +\tint abandoned:1,\n> +\t\thidden:1,\n> +\t\tremote:1,\n> +\t\tdeleted:1;\n> +};\n> +\n> +/*\n> + * An array of change_head.\n> + */\n> +struct change_head_array {\n> +\tstruct change_head* array;\n> +\tint nr;\n> +\tint alloc;\n> +};\n> +\n> +/*\n> + * Holds the list of change refs whose content points to a particular content\n> + * commit.\n> + */\n> +struct commit_change_list_entry {\n> +\tstruct oidmap_entry entry;\n> +\tstruct change_list changes;\n> +};\n> +\n> +/*\n> + * Holds information about the heads of each change, and permits effecient\n> + * lookup from a commit to the changes that reference it directly.\n> + *\n> + * All fields should be considered private. Use the change_table functions\n> + * to interact with this struct.\n> + */\n> +struct change_table {\n> +\t/**\n> +\t * Memory pool for the objects allocated by the change table.\n> +\t */\n> +\tstruct mem_pool *memory_pool;\n> +\t/* Map object_id to commit_change_list_entry structs. */\n> +\tstruct oidmap oid_to_metadata_index;\n> +\t/* List of ref names. The util value is an int index into change_metadata\n> +\t * array.\n> +\t */\n> +\tstruct string_list refname_to_change_head;\n> +\t/* change_head structures for each head */\n> +\tstruct change_head_array heads;\n> +};\n> +\n> +extern void change_table_init(struct change_table *to_initialize);\n> +extern void change_table_clear(struct change_table *to_clear);\n> +\n> +/* Adds the given change head to the change_table struct */\n> +extern void change_table_add(struct change_table *to_modify,\n> +\tconst char *refname, struct commit *target);\n> +\n> +/* Adds the non-hidden local changes to the given change_table struct.\n> + */\n> +extern void change_table_add_all_visible(struct change_table *to_modify,\n> +\tstruct repository *repo);\n> +\n> +/*\n> + * Adds all changes matching the given ref filter to the given change_table\n> + * struct.\n> + */\n> +extern void change_table_add_matching_filter(struct change_table *to_modify,\n> +\tstruct repository* repo, struct ref_filter *filter);\n> +\n> +typedef int each_change_fn(const char *refname, void *cb_data);\n> +\n> +extern int change_table_has_change_referencing(struct change_table *changes,\n> +\tconst struct object_id *referenced_commit_id);\n> +\n> +/* Iterates over all changes that reference the given commit. For metacommits,\n> + * this is the list of changes that point directly to that metacommit.\n> + * For normal commits, this is the list of changes that have this commit as\n> + * their latest content.\n> + */\n> +extern int for_each_change_referencing(struct change_table *heads,\n> +\tconst struct object_id *referenced_commit_id, each_change_fn fn, void *cb_data);\n> +\n> +/**\n> + * Returns the change head for the given refname. Returns NULL if no such change\n> + * exists.\n> + */\n> +extern struct change_head* get_change_head(struct change_table *heads,\n> +\tconst char* refname);\n> +\n> +#endif\n> -- \n> 2.20.1.495.gaa96b0ce6b-goog\n> \n> \n> \n"},{"id":"367902","messageId":"nycvar.QRO.7.76.6.1901290005390.41@tvgsbejvaqbjf.bet","threadId":"50338","inReplyTo":"nycvar.QRO.7.76.6.1901280858060.41@tvgsbejvaqbjf.bet","subject":"Re: [PATCH v3 5/8] evolve: Add the change-table structure","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2019-01-28T23:08:27Z","receivedAt":"2019-01-28T23:08:54Z","isPatch":true,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Hi Junio,\n\nOn Mon, 28 Jan 2019, Johannes Schindelin wrote:\n\n> On Sun, 27 Jan 2019, sxenos@google.com wrote:\n> \n> > +\tnew_item->util = (void*)index;\n> \n> This is not good. You are using a `long` here. The 80s called and want\n> their now-obsolete data types back.\n> \n> If you want a data type that can take an integer but also a pointer, use\n> `intptr_t` instead.\n> \n> But even that is not good practice. What you really want here is to use a\n> union of the data types that you want to store in that `util` field.\n> \n> This is not merely academic, your code causes compile errors on Windows:\n> \n> https://dev.azure.com/gitgitgadget/git/_build/results?buildId=400&view=logs&jobId=fd490c07-0b22-5182-fac9-6d67fe1e939b&taskId=ce91d5d6-0c55-50f5-8ab9-6695c03ab102&lineStart=430&lineEnd=440&colStart=1&colEnd=1\n\nSince Stefan did not grace us with an answer, Junio, could I ask you to\nsquash this in (which is by no means a satisfactory fix, but it is a\nstopgap to get `pu` building again)?\n\n-- snipsnap --\ndiff --git a/change-table.c b/change-table.c\nindex 2e0d935de846..197ce2783532 100644\n--- a/change-table.c\n+++ b/change-table.c\n@@ -103,7 +103,7 @@ void change_table_add(struct change_table *to_modify, const char *refname,\n \tnew_head->hidden = starts_with(refname, \"refs/hiddenmetas/\");\n \n \tnew_item = string_list_insert(&to_modify->refname_to_change_head, refname);\n-\tnew_item->util = (void*)index;\n+\tnew_item->util = (void *)(intptr_t)index;\n \t// Use pointers to the copy of the string we're retaining locally\n \trefname = new_item->string;\n \n@@ -201,6 +201,6 @@ struct change_head* get_change_head(struct change_table *heads,\n \t\treturn NULL;\n \t}\n \n-\tindex = (long)item->util;\n+\tindex = (long)(intptr_t)item->util;\n \treturn &(heads->heads.array[index]);\n }\n\n"},{"id":"367903","messageId":"CAPL8ZiuKnvQd1tpbsT+xn2Dt0rMs_ggQKOSz_vMda3i1V1YfHQ@mail.gmail.com","threadId":"50338","inReplyTo":"nycvar.QRO.7.76.6.1901290005390.41@tvgsbejvaqbjf.bet","subject":"Re: [PATCH v3 5/8] evolve: Add the change-table structure","fromName":"Stefan Xenos","fromEmail":"sxenos@google.com","sentAt":"2019-01-28T23:24:45Z","receivedAt":"2019-01-28T23:25:00Z","isPatch":true,"sender":{"key":"sxenos@google.com","avatar":null},"body":"Sorry, folks. I normally can't do any open source work on weekdays.\nThat also includes writing responses on the mailing list, so there\nwill normally be a week or two lag for me to iterate on this sort of\nthing.\n\nFeel free to either include this fix or revert my patch if there's a\nproblem with it - just let me know what you selected. I'll roll with\nit and either resubmit with the requested changes or submit the\nrequested changes as follow-ups.\n\n - Stefan\n\nOn Mon, Jan 28, 2019 at 3:08 PM Johannes Schindelin\n wrote:\n>\n> Hi Junio,\n>\n> On Mon, 28 Jan 2019, Johannes Schindelin wrote:\n>\n> > On Sun, 27 Jan 2019, sxenos@google.com wrote:\n> >\n> > > + new_item->util = (void*)index;\n> >\n> > This is not good. You are using a `long` here. The 80s called and want\n> > their now-obsolete data types back.\n> >\n> > If you want a data type that can take an integer but also a pointer, use\n> > `intptr_t` instead.\n> >\n> > But even that is not good practice. What you really want here is to use a\n> > union of the data types that you want to store in that `util` field.\n> >\n> > This is not merely academic, your code causes compile errors on Windows:\n> >\n> > https://dev.azure.com/gitgitgadget/git/_build/results?buildId=400&view=logs&jobId=fd490c07-0b22-5182-fac9-6d67fe1e939b&taskId=ce91d5d6-0c55-50f5-8ab9-6695c03ab102&lineStart=430&lineEnd=440&colStart=1&colEnd=1\n>\n> Since Stefan did not grace us with an answer, Junio, could I ask you to\n> squash this in (which is by no means a satisfactory fix, but it is a\n> stopgap to get `pu` building again)?\n>\n> -- snipsnap --\n> diff --git a/change-table.c b/change-table.c\n> index 2e0d935de846..197ce2783532 100644\n> --- a/change-table.c\n> +++ b/change-table.c\n> @@ -103,7 +103,7 @@ void change_table_add(struct change_table *to_modify, const char *refname,\n> new_head->hidden = starts_with(refname, \"refs/hiddenmetas/\");\n>\n> new_item = string_list_insert(&to_modify->refname_to_change_head, refname);\n> - new_item->util = (void*)index;\n> + new_item->util = (void *)(intptr_t)index;\n> // Use pointers to the copy of the string we're retaining locally\n> refname = new_item->string;\n>\n> @@ -201,6 +201,6 @@ struct change_head* get_change_head(struct change_table *heads,\n> return NULL;\n> }\n>\n> - index = (long)item->util;\n> + index = (long)(intptr_t)item->util;\n> return &(heads->heads.array[index]);\n> }\n>\n"},{"id":"368024","messageId":"xmqqef8v8hqp.fsf@gitster-ct.c.googlers.com","threadId":"50338","inReplyTo":"CAPL8ZiuKnvQd1tpbsT+xn2Dt0rMs_ggQKOSz_vMda3i1V1YfHQ@mail.gmail.com","subject":"Re: [PATCH v3 5/8] evolve: Add the change-table structure","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2019-01-29T18:02:22Z","receivedAt":"2019-01-29T18:02:28Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Stefan Xenos writes:\n\n> Sorry, folks. I normally can't do any open source work on weekdays.\n> That also includes writing responses on the mailing list, so there\n> will normally be a week or two lag for me to iterate on this sort of\n> thing.\n>\n> Feel free to either include this fix or revert my patch if there's a\n> problem with it - just let me know what you selected. I'll roll with\n> it and either resubmit with the requested changes or submit the\n> requested changes as follow-ups.\n\nI think double casting Dscho did was not his ideal \"fix\" but he did\nit as a mere workaround to force the 'pu' branch to compile. And I\nalso agree with him that the double casting workaround is too ugly\nto live, compared to a union he suggests. So I'd rather kick the\nbranch out of 'pu' for now.\n\nThanks, both.\n\n>\n> - Stefan\n>\n> On Mon, Jan 28, 2019 at 3:08 PM Johannes Schindelin\n> wrote:\n>>\n>> Hi Junio,\n>>\n>> On Mon, 28 Jan 2019, Johannes Schindelin wrote:\n>>\n>> > On Sun, 27 Jan 2019, sxenos@google.com wrote:\n>> >\n>> > > + new_item->util = (void*)index;\n>> >\n>> > This is not good. You are using a `long` here. The 80s called and want\n>> > their now-obsolete data types back.\n>> >\n>> > If you want a data type that can take an integer but also a pointer, use\n>> > `intptr_t` instead.\n>> >\n>> > But even that is not good practice. What you really want here is to use a\n>> > union of the data types that you want to store in that `util` field.\n>> >\n>> > This is not merely academic, your code causes compile errors on Windows:\n>> >\n>> > https://dev.azure.com/gitgitgadget/git/_build/results?buildId=400&view=logs&jobId=fd490c07-0b22-5182-fac9-6d67fe1e939b&taskId=ce91d5d6-0c55-50f5-8ab9-6695c03ab102&lineStart=430&lineEnd=440&colStart=1&colEnd=1\n>>\n>> Since Stefan did not grace us with an answer, Junio, could I ask you to\n>> squash this in (which is by no means a satisfactory fix, but it is a\n>> stopgap to get `pu` building again)?\n>>\n>> -- snipsnap --\n>> diff --git a/change-table.c b/change-table.c\n>> index 2e0d935de846..197ce2783532 100644\n>> --- a/change-table.c\n>> +++ b/change-table.c\n>> @@ -103,7 +103,7 @@ void change_table_add(struct change_table *to_modify, const char *refname,\n>> new_head->hidden = starts_with(refname, \"refs/hiddenmetas/\");\n>>\n>> new_item = string_list_insert(&to_modify->refname_to_change_head, refname);\n>> - new_item->util = (void*)index;\n>> + new_item->util = (void *)(intptr_t)index;\n>> // Use pointers to the copy of the string we're retaining locally\n>> refname = new_item->string;\n>>\n>> @@ -201,6 +201,6 @@ struct change_head* get_change_head(struct change_table *heads,\n>> return NULL;\n>> }\n>>\n>> - index = (long)item->util;\n>> + index = (long)(intptr_t)item->util;\n>> return &(heads->heads.array[index]);\n>> }\n>>\n"},{"id":"368025","messageId":"CAPL8ZiupbKuZMAymW8je9UJ61Tm5aoDcS1srQTf=y9iQEuPFoA@mail.gmail.com","threadId":"50338","inReplyTo":"xmqqef8v8hqp.fsf@gitster-ct.c.googlers.com","subject":"Re: [PATCH v3 5/8] evolve: Add the change-table structure","fromName":"Stefan Xenos","fromEmail":"sxenos@google.com","sentAt":"2019-01-29T18:09:42Z","receivedAt":"2019-01-29T18:09:57Z","isPatch":true,"sender":{"key":"sxenos@google.com","avatar":null},"body":"Works with me. I'll resubmit without the double casting next chance I\nhave to work on it. My long-term plan for that struct was to use the\nmemory pool for all allocations anyway. I think that should let me\nimplement it without moving objects around, which will make their\naddresses stable. That should let me use pointers for everything,\nwithout the ints - so I probably won't need the union.\n\nOn Tue, Jan 29, 2019 at 10:02 AM Junio C Hamano wrote:\n>\n> Stefan Xenos writes:\n>\n> > Sorry, folks. I normally can't do any open source work on weekdays.\n> > That also includes writing responses on the mailing list, so there\n> > will normally be a week or two lag for me to iterate on this sort of\n> > thing.\n> >\n> > Feel free to either include this fix or revert my patch if there's a\n> > problem with it - just let me know what you selected. I'll roll with\n> > it and either resubmit with the requested changes or submit the\n> > requested changes as follow-ups.\n>\n> I think double casting Dscho did was not his ideal \"fix\" but he did\n> it as a mere workaround to force the 'pu' branch to compile. And I\n> also agree with him that the double casting workaround is too ugly\n> to live, compared to a union he suggests. So I'd rather kick the\n> branch out of 'pu' for now.\n>\n> Thanks, both.\n>\n> >\n> > - Stefan\n> >\n> > On Mon, Jan 28, 2019 at 3:08 PM Johannes Schindelin\n> > wrote:\n> >>\n> >> Hi Junio,\n> >>\n> >> On Mon, 28 Jan 2019, Johannes Schindelin wrote:\n> >>\n> >> > On Sun, 27 Jan 2019, sxenos@google.com wrote:\n> >> >\n> >> > > + new_item->util = (void*)index;\n> >> >\n> >> > This is not good. You are using a `long` here. The 80s called and want\n> >> > their now-obsolete data types back.\n> >> >\n> >> > If you want a data type that can take an integer but also a pointer, use\n> >> > `intptr_t` instead.\n> >> >\n> >> > But even that is not good practice. What you really want here is to use a\n> >> > union of the data types that you want to store in that `util` field.\n> >> >\n> >> > This is not merely academic, your code causes compile errors on Windows:\n> >> >\n> >> > https://dev.azure.com/gitgitgadget/git/_build/results?buildId=400&view=logs&jobId=fd490c07-0b22-5182-fac9-6d67fe1e939b&taskId=ce91d5d6-0c55-50f5-8ab9-6695c03ab102&lineStart=430&lineEnd=440&colStart=1&colEnd=1\n> >>\n> >> Since Stefan did not grace us with an answer, Junio, could I ask you to\n> >> squash this in (which is by no means a satisfactory fix, but it is a\n> >> stopgap to get `pu` building again)?\n> >>\n> >> -- snipsnap --\n> >> diff --git a/change-table.c b/change-table.c\n> >> index 2e0d935de846..197ce2783532 100644\n> >> --- a/change-table.c\n> >> +++ b/change-table.c\n> >> @@ -103,7 +103,7 @@ void change_table_add(struct change_table *to_modify, const char *refname,\n> >> new_head->hidden = starts_with(refname, \"refs/hiddenmetas/\");\n> >>\n> >> new_item = string_list_insert(&to_modify->refname_to_change_head, refname);\n> >> - new_item->util = (void*)index;\n> >> + new_item->util = (void *)(intptr_t)index;\n> >> // Use pointers to the copy of the string we're retaining locally\n> >> refname = new_item->string;\n> >>\n> >> @@ -201,6 +201,6 @@ struct change_head* get_change_head(struct change_table *heads,\n> >> return NULL;\n> >> }\n> >>\n> >> - index = (long)item->util;\n> >> + index = (long)(intptr_t)item->util;\n> >> return &(heads->heads.array[index]);\n> >> }\n> >>\n"}]}