-
Notifications
You must be signed in to change notification settings - Fork 322
New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
Group (topological) branches in log output #242
Comments
Here's a description of how Git does it: https://github.blog/2022-08-30-gits-database-internals-ii-commit-history-queries/#topological-sorting |
Sorry, haven't read through that Github blog in detail so maybe I have this wrong but it seems to me like a simple DFS like approach would work well (enough) here? I personally find this much easier to read --
I originally did not differentiate between children vs descendants but then later shoehorned it with Also, I'm not really sure how jj handles those relations in code but in the DFS, we could just prefer to render most recently touched subtrees towards the end (or the beginning, if you don't reverse the output), with the working copy getting special preference to be considered most recently touched (and hence get rendered at the last for better visibility). Thoughts? |
Just to make the above log more compact (like jj log now),
|
The code is in revset_graph_iterator.rs. What makes it complicated is the laziness - we shouldn't walk the whole graph before we start displaying output. That would be fine to do in small repos, but it would make |
Segmented changelog (or similar) might help the scalability issue? Just for reference. I don't know if it applies here, but it contains some readable graph examples saying "use depth-first search" to assign numbers. |
Hmm, I think that's a good point whether or not we use segmented changelog. Unlike Git 1, we could quite efficiently find common ancestors using the commit index. Maybe that would perform well enough and be simpler, but I haven't thought much about it. Footnotes
|
It sounds like this function might be useful. It's used by smartlog rendering (via the It's a bit more aggressive than the old |
…WIP) May be buggy. Not yet ready for production use. I'm just dogfooding to see if I like this more than Sapling's beautify_graph(), which reorders commits more aggressively. martinvonz#242
…WIP) May be buggy. Not yet ready for production use. I'm just dogfooding to see if I like this more than Sapling's beautify_graph(), which reorders commits more aggressively. martinvonz#242
This is similar to Mercurial's "topo" sorting, but merge handling seems different. Mercurial's dagop.toposort() tracks [(roots, descendants)], and merge parents are combined into a single tracking record. OTOH, ours tracks {root: descendants}, and merge ancestors are split to separate tracking records. I don't know which would produce a better result, but I think the latter is easier to implement. Compared to Sapling's beautify_graph(), this is lazy, and can roughly preserve the index (or chronological) order. I tried beautify_graph() with prioritizing the @ commit, but the result seemed too aggressively reordered. Perhaps, for merge-heavy history (or branchy history in reverse order), beautify_graph() will produce significantly better result. Closes martinvonz#242
This is similar to Mercurial's "topo" sorting, but merge handling seems different. Mercurial's dagop.toposort() tracks [(roots, descendants)], and merged ancestors are combined into a single tracking record. OTOH, ours tracks {root: descendants}, and merged ancestors are split into separate tracking records. I don't know which one will produce a better result, but I think the latter is easier to implement. Compared to Sapling's beautify_graph(), this is lazy, and can roughly preserve the index (or chronological) order. I tried beautify_graph() with prioritizing the @ commit, but the result seemed too aggressively reordered. Perhaps, for merge-heavy history (or branchy history in reverse order), beautify_graph() will produce significantly better result. For my wip branches (~30 branches, a couple of commits per branch), this works pretty well. Closes martinvonz#242
This is similar to Mercurial's "topo" sorting, but merge handling seems different. Mercurial's dagop.toposort() tracks [(roots, descendants)], and merged ancestors are combined into a single tracking record. OTOH, ours tracks {root: descendants}, and merged ancestors are split into separate tracking records. I don't know which one will produce a better result, but I think the latter is easier to implement. Compared to Sapling's beautify_graph(), this is lazy, and can roughly preserve the index (or chronological) order. I tried beautify_graph() with prioritizing the @ commit, but the result seemed too aggressively reordered. Perhaps, for merge-heavy history (or branchy history in reverse order), beautify_graph() will produce significantly better result. For my wip branches (~30 branches, a couple of commits per branch), this works pretty well. Closes martinvonz#242
The original idea was similar to Mercurial's "topo" sorting, but it couldn't reorder merge-heavy history. In order to render merges of topic branches nicely, we need to roughly reorder branches at merge point, not at fork point. To achieve that, we build a graph of linear segments, and walk them from the head towards the root of the second branch. While walking, descendant segments of the current segment will also be visited. Compared to Sapling's beautify_graph(), this is lazy, and can roughly preserve the index (or chronological) order. I tried beautify_graph() with prioritizing the @ commit, but the result seemed too aggressively reordered. Perhaps, for merge-heavy history, beautify_graph() will produce a better result. For my wip branches (~30 branches, a couple of commits per branch), this works pretty well. Closes martinvonz#242
The original idea was similar to Mercurial's "topo" sorting, but it was bad at handling merge-heavy history. In order to render merges of topic branches nicely, we need to prioritize branches at merge point, not at fork point. To achieve that, we build a graph of linear segments, and walk them from the head towards the root of the second branch. While walking, descendant segments of the current segment are also visited. Compared to Sapling's beautify_graph(), this is lazy, and can roughly preserve the index (or chronological) order. I tried beautify_graph() with prioritizing the @ commit, but the result seemed too aggressively reordered. Perhaps, for merge-heavy history, beautify_graph() would produce a better result. For my wip branches (~30 branches, a couple of commits per branch), this works pretty well. Closes martinvonz#242
The original idea was similar to Mercurial's "topo" sorting, but it was bad at handling merge-heavy history. In order to render merges of topic branches nicely, we need to prioritize branches at merge point, not at fork point. OTOH, we do also want to place unmerged branches as close to the fork point as possible. This commit implements the former requirement, and the latter will be addressed by the next commit. I think this is similar to Git's sorting logic described in the following blog post. In our case, the in-degree walk can be dumb since topological order is guaranteed by the index. We keep HashSet<CommitId> instead of an in-degree integer value, which will be used in the next commit to resolve new heads as late as possible. https://github.blog/2022-08-30-gits-database-internals-ii-commit-history-queries/#topological-sorting Compared to Sapling's beautify_graph(), this is lazy, and can roughly preserve the index (or chronological) order. I tried beautify_graph() with prioritizing the @ commit, but the result seemed too aggressively reordered. Perhaps, for more complex history, beautify_graph() would produce a better result. For my wip branches (~30 branches, a couple of commits per branch), this works pretty well. martinvonz#242
The idea is simple. New heads are ignored until the node dependency resolution stuck. Then, only heads that will unblock the visit will be queued. Closes martinvonz#242
The original idea was similar to Mercurial's "topo" sorting, but it was bad at handling merge-heavy history. In order to render merges of topic branches nicely, we need to prioritize branches at merge point, not at fork point. OTOH, we do also want to place unmerged branches as close to the fork point as possible. This commit implements the former requirement, and the latter will be addressed by the next commit. I think this is similar to Git's sorting logic described in the following blog post. In our case, the in-degree walk can be dumb since topological order is guaranteed by the index. We keep HashSet<CommitId> instead of an in-degree integer value, which will be used in the next commit to resolve new heads as late as possible. https://github.blog/2022-08-30-gits-database-internals-ii-commit-history-queries/#topological-sorting Compared to Sapling's beautify_graph(), this is lazy, and can roughly preserve the index (or chronological) order. I tried beautify_graph() with prioritizing the @ commit, but the result seemed too aggressively reordered. Perhaps, for more complex history, beautify_graph() would produce a better result. For my wip branches (~30 branches, a couple of commits per branch), this works pretty well. martinvonz#242
The idea is simple. New heads are ignored until the node dependency resolution stuck. Then, only heads that will unblock the visit will be queued. Closes martinvonz#242
The original idea was similar to Mercurial's "topo" sorting, but it was bad at handling merge-heavy history. In order to render merges of topic branches nicely, we need to prioritize branches at merge point, not at fork point. OTOH, we do also want to place unmerged branches as close to the fork point as possible. This commit implements the former requirement, and the latter will be addressed by the next commit. I think this is similar to Git's sorting logic described in the following blog post. In our case, the in-degree walk can be dumb since topological order is guaranteed by the index. We keep HashSet<CommitId> instead of an in-degree integer value, which will be used in the next commit to resolve new heads as late as possible. https://github.blog/2022-08-30-gits-database-internals-ii-commit-history-queries/#topological-sorting Compared to Sapling's beautify_graph(), this is lazy, and can roughly preserve the index (or chronological) order. I tried beautify_graph() with prioritizing the @ commit, but the result seemed too aggressively reordered. Perhaps, for more complex history, beautify_graph() would produce a better result. For my wip branches (~30 branches, a couple of commits per branch), this works pretty well. martinvonz#242
The idea is simple. New heads are ignored until the node dependency resolution stuck. Then, only heads that will unblock the visit will be queued. Closes martinvonz#242
The original idea was similar to Mercurial's "topo" sorting, but it was bad at handling merge-heavy history. In order to render merges of topic branches nicely, we need to prioritize branches at merge point, not at fork point. OTOH, we do also want to place unmerged branches as close to the fork point as possible. This commit implements the former requirement, and the latter will be addressed by the next commit. I think this is similar to Git's sorting logic described in the following blog post. In our case, the in-degree walk can be dumb since topological order is guaranteed by the index. We keep HashSet<CommitId> instead of an in-degree integer value, which will be used in the next commit to resolve new heads as late as possible. https://github.blog/2022-08-30-gits-database-internals-ii-commit-history-queries/#topological-sorting Compared to Sapling's beautify_graph(), this is lazy, and can roughly preserve the index (or chronological) order. I tried beautify_graph() with prioritizing the @ commit, but the result seemed too aggressively reordered. Perhaps, for more complex history, beautify_graph() would produce a better result. For my wip branches (~30 branches, a couple of commits per branch), this works pretty well. martinvonz#242
The idea is simple. New heads are ignored until the node dependency resolution stuck. Then, only heads that will unblock the visit will be queued. Closes martinvonz#242
The original idea was similar to Mercurial's "topo" sorting, but it was bad at handling merge-heavy history. In order to render merges of topic branches nicely, we need to prioritize branches at merge point, not at fork point. OTOH, we do also want to place unmerged branches as close to the fork point as possible. This commit implements the former requirement, and the latter will be addressed by the next commit. I think this is similar to Git's sorting logic described in the following blog post. In our case, the in-degree walk can be dumb since topological order is guaranteed by the index. We keep HashSet<CommitId> instead of an in-degree integer value, which will be used in the next commit to resolve new heads as late as possible. https://github.blog/2022-08-30-gits-database-internals-ii-commit-history-queries/#topological-sorting Compared to Sapling's beautify_graph(), this is lazy, and can roughly preserve the index (or chronological) order. I tried beautify_graph() with prioritizing the @ commit, but the result seemed too aggressively reordered. Perhaps, for more complex history, beautify_graph() would produce a better result. For my wip branches (~30 branches, a couple of commits per branch), this works pretty well. martinvonz#242
The idea is simple. New heads are ignored until the node dependency resolution stuck. Then, only the first head that will unblock the visit will be queued. Closes martinvonz#242
The original idea was similar to Mercurial's "topo" sorting, but it was bad at handling merge-heavy history. In order to render merges of topic branches nicely, we need to prioritize branches at merge point, not at fork point. OTOH, we do also want to place unmerged branches as close to the fork point as possible. This commit implements the former requirement, and the latter will be addressed by the next commit. I think this is similar to Git's sorting logic described in the following blog post. In our case, the in-degree walk can be dumb since topological order is guaranteed by the index. We keep HashSet<CommitId> instead of an in-degree integer value, which will be used in the next commit to resolve new heads as late as possible. https://github.blog/2022-08-30-gits-database-internals-ii-commit-history-queries/#topological-sorting Compared to Sapling's beautify_graph(), this is lazy, and can roughly preserve the index (or chronological) order. I tried beautify_graph() with prioritizing the @ commit, but the result seemed too aggressively reordered. Perhaps, for more complex history, beautify_graph() would produce a better result. For my wip branches (~30 branches, a couple of commits per branch), this works pretty well. martinvonz#242
The idea is simple. New heads are ignored until the node dependency resolution stuck. Then, only the first head that will unblock the visit will be queued. Closes martinvonz#242
The original idea was similar to Mercurial's "topo" sorting, but it was bad at handling merge-heavy history. In order to render merges of topic branches nicely, we need to prioritize branches at merge point, not at fork point. OTOH, we do also want to place unmerged branches as close to the fork point as possible. This commit implements the former requirement, and the latter will be addressed by the next commit. I think this is similar to Git's sorting logic described in the following blog post. In our case, the in-degree walk can be dumb since topological order is guaranteed by the index. We keep HashSet<CommitId> instead of an in-degree integer value, which will be used in the next commit to resolve new heads as late as possible. https://github.blog/2022-08-30-gits-database-internals-ii-commit-history-queries/#topological-sorting Compared to Sapling's beautify_graph(), this is lazy, and can roughly preserve the index (or chronological) order. I tried beautify_graph() with prioritizing the @ commit, but the result seemed too aggressively reordered. Perhaps, for more complex history, beautify_graph() would produce a better result. For my wip branches (~30 branches, a couple of commits per branch), this works pretty well. #242
[0.10.0] - 2023-10-04 ### Breaking changes * A default revset-alias function `trunk()` now exists. If you previously defined your own `trunk()` alias it will continue to overwrite the built-in one. Check [revsets.toml](cli/src/config/revsets.toml) and [revsets.md](docs/revsets.md) to understand how the function can be adapted. ### New features * The `ancestors()` revset function now takes an optional `depth` argument to limit the depth of the ancestor set. For example, use `jj log -r 'ancestors(@, 5)` to view the last 5 commits. * Support for the Watchman filesystem monitor is now bundled by default. Set `core.fsmonitor = "watchman"` in your repo to enable. * You can now configure the set of immutable commits via `revset-aliases.immutable_heads()`. For example, set it to `"remote_branches() | tags()"` to prevent rewriting those those. Their ancestors are implicitly also immutable. * `jj op log` now supports `--no-graph`. * Templates now support an additional escape: `\0`. This will output a literal null byte. This may be useful for e.g. `jj log -T 'description ++ "\0"' --no-graph` to output descriptions only, but be able to tell where the boundaries are * jj now bundles a TUI tool to use as the default diff and merge editors. (The previous default was `meld`.) * `jj split` supports the `--interactive` flag. (This is already the default if no paths are provided.) * `jj commit` accepts an optional list of paths indicating a subset of files to include in the first commit * `jj commit` accepts the `--interactive` flag. ### Fixed bugs ### Contributors Thanks to the people who made this release happen! * Austin Seipp (@thoughtpolice) * Emily Kyle Fox (@emilykfox) * glencbz (@glencbz) * Hong Shin (@honglooker) * Ilya Grigoriev (@ilyagr) * James Sully (@sullyj3) * Martin von Zweigbergk (@martinvonz) * Philip Metzger (@PhilipMetzger) * Ruben Slabbert (@rslabbert) * Vamsi Avula (@avamsi) * Waleed Khan (@arxanas) * Willian Mori (@wmrmrx)) * Yuya Nishihara (@yuja) * Zachary Dremann (@Dr-Emann) [0.9.0] - 2023-09-06 ### Breaking changes * The minimum supported Rust version (MSRV) is now 1.71.0. * The storage format of branches, tags, and git refs has changed. Newly-stored repository data will no longer be loadable by older binaries. * The `:` revset operator is deprecated. Use `::` instead. We plan to delete the `:` form in jj 0.15+. * The `--allow-large-revsets` flag for `jj rebase` and `jj new` was replaced by a `all:` before the revset. For example, use `jj rebase -d 'all:foo-'` instead of `jj rebase --allow-large-revsets -d 'foo-'`. * The `--allow-large-revsets` flag for `jj rebase` and `jj new` can no longer be used for allowing duplicate destinations. Include the potential duplicates in a single expression instead (e.g. `jj new 'all:x|y'`). * The `push.branch-prefix` option was renamed to `git.push-branch-prefix`. * The default editor on Windows is now `Notepad` instead of `pico`. * `jj` will fail attempts to snapshot new files larger than 1MiB by default. This behavior can be customized with the `snapshot.max-new-file-size` config option. * Author and committer signatures now use empty strings to represent unset names and email addresses. The `author`/`committer` template keywords and methods also return empty strings. Older binaries may not warn user when attempting to `git push` commits with such signatures. * In revsets, the working-copy or remote symbols (such as `@`, `workspace_id@`, and `branch@remote`) can no longer be quoted as a unit. If a workspace or branch name contains whitespace, quote the name like `"branch name"@remote`. Also, these symbols will not be resolved as revset aliases or function parameters. For example, `author(foo@)` is now an error, and the revset alias `'revset-aliases.foo@' = '@'` will be failed to parse. * The `root` revset symbol has been converted to function `root()`. * The `..x` revset is now evaluated to `root()..x`, which means the root commit is no longer included. * `jj git push` will now push all branches in the range `remote_branches()..@` instead of only branches pointing to `@` or `@-`. * It's no longer allowed to create a Git remote named "git". Use `jj git remote rename` to rename the existing remote. [#1690](martinvonz/jj#1690) * Revset expression like `origin/main` will no longer resolve to a remote-tracking branch. Use `main@origin` instead. ### New features * Default template for `jj log` now does not show irrelevant information (timestamp, empty, message placeholder etc.) about the root commit. * Commit templates now support the `root` keyword, which is `true` for the root commit and `false` for every other commit. * `jj init --git-repo` now works with bare repositories. * `jj config edit --user` and `jj config set --user` will now pick a default config location if no existing file is found, potentially creating parent directories. * `jj log` output is now topologically grouped. [#242](martinvonz/jj#242) * `jj git clone` now supports the `--colocate` flag to create the git repo in the same directory as the jj repo. * `jj restore` gained a new option `--changes-in` to restore files from a merge revision's parents. This undoes the changes that `jj diff -r` would show. * `jj diff`/`log` now supports `--tool <name>` option to generate diffs by external program. For configuration, see [the documentation](docs/config.md). [#1886](martinvonz/jj#1886) * A new experimental diff editor `meld-3` is introduced that sets up Meld to allow you to see both sides of the original diff while editing. This can be used with `jj split`, `jj move -i`, etc. * `jj log`/`obslog`/`op log` now supports `--limit N` option to show the first `N` entries. * Added the `ui.paginate` option to enable/disable pager usage in commands * `jj checkout`/`jj describe`/`jj commit`/`jj new`/`jj squash` can take repeated `-m/--message` arguments. Each passed message will be combined into paragraphs (separated by a blank line) * It is now possible to set a default description using the new `ui.default-description` option, to use when describing changes with an empty description. * `jj split` will now leave the description empty on the second part if the description was empty on the input commit. * `branches()`/`remote_branches()`/`author()`/`committer()`/`description()` revsets now support exact matching. For example, `branch(exact:main)` selects the branch named "main", but not "maint". `description(exact:"")` selects commits whose description is empty. * Revsets gained a new function `mine()` that aliases `author(exact:"your_email")`. * Added support for `::` and `..` revset operators with both left and right operands omitted. These expressions are equivalent to `all()` and `~root()` respectively. * `jj log` timestamp format now accepts `.utc()` to convert a timestamp to UTC. * templates now support additional string methods `.starts_with(x)`, `.ends_with(x)` `.remove_prefix(x)`, `.remove_suffix(x)`, and `.substr(start, end)`. * `jj next` and `jj prev` are added, these allow you to traverse the history in a linear style. For people coming from Sapling and `git-branchles` see [#2126](martinvonz/jj#2126) for further pending improvements. * `jj diff --stat` has been implemented. It shows a histogram of the changes, same as `git diff --stat`. Fixes [#2066](martinvonz/jj#2066) * `jj git fetch --all-remotes` has been implemented. It fetches all remotes instead of just the default remote ### Fixed bugs * Fix issues related to .gitignore handling of untracked directories [#2051](martinvonz/jj#2051). * `jj config set --user` and `jj config edit --user` can now be used outside of any repository. * SSH authentication could hang when ssh-agent couldn't be reached [#1970](martinvonz/jj#1970) * SSH authentication can now use ed25519 and ed25519-sk keys. They still need to be password-less. * Git repository managed by the repo tool can now be detected as a "colocated" repository. [#2011](martinvonz/jj#2011) ### Contributors Thanks to the people who made this release happen! * Alexander Potashev (@aspotashev) * Anton Bulakh (@necauqua) * Austin Seipp (@thoughtpolice) * Benjamin Brittain (@benbrittain) * Benjamin Saunders (@Ralith) * Christophe Poucet (@poucet) * Emily Kyle Fox (@emilykfox) * Glen Choo (@chooglen) * Ilya Grigoriev (@ilyagr) * Kevin Liao (@kevincliao) * Linus Arver (@listx) * Martin Clausen (@maacl) * Martin von Zweigbergk (@martinvonz) * Matt Freitas-Stavola (@mbStavola) * Oscar Bonilla (@ob) * Philip Metzger (@PhilipMetzger) * Piotr Kufel (@qfel) * Preston Van Loon (@prestonvanloon) * Tal Pressman (@talpr) * Vamsi Avula (@avamsi) * Vincent Breitmoser (@Valodim) * Vladimir (@0xdeafbeef) * Waleed Khan (@arxanas) * Yuya Nishihara (@yuja) * Zachary Dremann (@Dr-Emann)
Description
Parallel branches are interleaved in the (ASCII-)graphical log output, making it hard to read.
Actual Behavior
Expected Behavior
It's much easier to read like this:
I think the idea is to print all commits on one side of a fork point before the other side(s) of the fork point. The fork points in this graph are
ca796b49f06f
andc0a26f76426e
, although only the latter matters in this case (because there's only one commit on each side beforeca796b49f06f
)Specifications
The text was updated successfully, but these errors were encountered: