Unstable layout and occasional segfault

[kdheepak]

I tested this on the following graph:

*---.   068e5b1 (HEAD -> main) 1-e
|\ \ \
| | | * 9fa1710 (tag: 4-b) 4-b
| | * | d3485ed (tag: 3-b) 3-b
| * | | 4b38ef0 (tag: 2-b) 2-b
| * | |   7664bed (tag: 2-a) 2-a
|/|\ \ \
| | |/ /
| |/| /
| | |/
| | * f55cb68 (tag: 4-a) 4-a
| * | f3786ec (tag: 3-a) 3-a
| |/
* | 8cc2ec3 (tag: 1-c) 1-c
* | c97b582 (tag: 1-b) 1-b
|/
* 00e0694 (tag: 1-a) 1-a

and was getting an unstable layout and an occasional segfault.

thread 'main' panicked at src/graph/calc.rs:228:5:
index out of bounds: the len is 0 but the index is 0
stack backtrace:
   0:        0x104fc744c - <std::sys_common::backtrace::_print::DisplayBacktrace as core::fmt::Display>::fmt::h1f3776e0b5c7517d
   1:        0x104fe5128 - core::fmt::write::heedef092c8c0962e
   2:        0x104fc471c - std::io::Write::write_fmt::h7178e8e2ea928914
   3:        0x104fc72a4 - std::sys_common::backtrace::print::h417292deb95532ed
   4:        0x104fc86a8 - std::panicking::default_hook::{{closure}}::h0cb68f1228c4613a
   5:        0x104fc839c - std::panicking::default_hook::h24535936bc1f51de
   6:        0x104fc8f60 - std::panicking::rust_panic_with_hook::h5db4d2345b297bed
   7:        0x104fc8990 - std::panicking::begin_panic_handler::{{closure}}::h3fd558f09a0d5492
   8:        0x104fc78d4 - std::sys_common::backtrace::__rust_end_short_backtrace::hfc76eebe1ce501b2
   9:        0x104fc8700 - _rust_begin_unwind
  10:        0x10500bf84 - core::panicking::panic_fmt::hc2b459a5bd3dce66
  11:        0x10500c0cc - core::panicking::panic_bounds_check::hd61643b086b4289f
  12:        0x104d68e34 - serie::graph::calc::calc_graph::h9e19fe0ce74cbc11
  13:        0x104da069c - serie::run::h946d0ce14d7749c3
  14:        0x104c555f8 - std::sys_common::backtrace::__rust_begin_short_backtrace::hc73c8b47148a5084
  15:        0x104c55618 - std::rt::lang_start::{{closure}}::hdaafe243cf43680d
  16:        0x104fbe318 - std::rt::lang_start_internal::hecc68fef83c8f44d
  17:        0x104c55804 - _main

Here's a video where I ran it multiple times:

serie-unstable.mov

Here's a python script to generate a number of git repos:

# -*- coding: utf-8 -*-
import argparse
import os
import shutil
import subprocess

TEST_DIR = os.path.realpath(os.path.dirname(__file__))
BASE_DIR = os.path.realpath(os.path.join(os.path.dirname(__file__), ".."))
DATA_DIR = os.path.realpath(os.path.join(os.path.dirname(__file__), "data"))
WORKTREE = None


def get_dir(name):
    """Return the path to the .test directory inside BASE_DIR"""
    return os.path.join(BASE_DIR, "tests", name)


def get_tmp_dir(name):
    """Return the path to the temporary directory inside .test directory"""
    return os.path.join(BASE_DIR, "tests", "tmp", name)


def create_abs_dir(path):
    """Create an absolute directory path"""
    os.makedirs(path, exist_ok=True)
    return path


def create_dir(name):
    """Create a directory inside the .test directory"""
    return create_abs_dir(get_dir(name))


def create_tmp_dir(name):
    """Create a temporary directory inside the .test directory"""
    remove_dir(os.path.join("tmp", name))
    return create_dir(os.path.join("tmp", name))


def remove_dir(name):
    """Remove a directory inside the .test directory"""
    shutil.rmtree(get_dir(name), ignore_errors=True)


def remove_tmp_dirs():
    """Remove all temporary directories inside the .test directory"""
    remove_dir("tmp")


def git_init(name):
    """Initialize a new git repository in a temporary directory"""
    worktree = create_tmp_dir(f"repo/{name}")
    git_dir = os.path.join(worktree, ".git")
    run_git_command(["init", "-q", "-b", "main"], git_dir)
    run_git_command(["config", "user.email", "flog@test.com"], git_dir)
    run_git_command(["config", "user.name", "flog"], git_dir)
    os.chdir(worktree)
    global WORKTREE
    WORKTREE = worktree
    return worktree


def git_checkout(*args):
    """Checkout to a specific branch or commit"""
    run_git_command(["checkout", "-q"] + list(args))


def git_commit(*args):
    """Make an empty git commit"""
    run_git_command(["commit", "-q", "--allow-empty"] + list(args))


def git_merge(*args, fast_forward=False):
    """Merge branches or commits"""
    run_git_command(["merge", "-q", "--no-edit", "--ff" if fast_forward else "--no-ff"] + list(args))


def git_tag(*args):
    """Tag a commit"""
    run_git_command(["tag"] + list(args))


def git_commits(*commits, tag=True):
    """Create and tag multiple commits"""
    for commit in commits:
        git_commit("-m", commit)
        if tag:
            git_tag(commit)


def run_git_command(command, git_dir=None):
    """Helper function to execute a git command"""
    cmd = ["git"]
    if git_dir is None and WORKTREE is None:
        raise Exception("Cannot run git command without git-dir explicitly specified.")
    if git_dir is None:
        git_dir = os.path.join(str(WORKTREE), ".git")
    cmd.append(f"--git-dir={git_dir}")
    cmd.extend(command)
    subprocess.run(cmd, check=True)


def graph_simple():
    # Initialize the work tree
    print("Creating: ", git_init("graph_simple"))

    # Create and tag multiple commits
    git_commits("1-a", "1-b", "1-c", "1-d")

    git_checkout("-b", "new_branch")
    git_checkout("main")


def graph_merge():
    # Initialize the work tree
    print("Creating: ", git_init("graph_merge"))

    # Creating and tagging first set of commits
    git_commits("1-a", "1-b", "1-c")

    # Checkout to 1-b and create another set of commits
    git_checkout("1-b")
    git_commits("2-a", "2-b")

    # Checkout back to 1-c, merge branch from 2-b, and make new commits
    git_checkout("1-c")
    git_merge("-m", "1-d", "2-b")
    git_commits("1-e")
    git_checkout("main")
    git_merge("1-e", fast_forward=True)


def graph_tangle():
    # Initialize the work tree
    print("Creating: ", git_init("graph_merge_tangle"))

    # Creating initial set of commits
    git_commits("1-a", "1-b", "1-c", "1-d", "1-e")

    # Checkout to 1-b and create another commit
    git_checkout("1-b")
    git_commits("2-a")

    # Continue making commits on different branches
    git_checkout("1-c")
    git_commits("3-a")

    git_checkout("1-e")
    git_commits("1-f")

    git_checkout("2-a")
    git_merge("-m", "2-b", "1-e")
    git_tag("2-b")

    git_checkout("3-a")
    git_commits("3-b")

    git_checkout("1-f")
    git_commits("1-g")

    git_checkout("2-b")
    git_merge("-m", "2-c", "3-a")
    git_tag("2-c")

    git_checkout("1-g")
    git_merge("-m", "1-h", "3-b")
    git_merge("-m", "1-i", "2-c")
    git_tag("1-i")

    git_checkout("1-i")
    git_commits("4-a")

    git_checkout("1-i")
    git_commits("3-c")

    git_checkout("1-i")
    git_commits("1-j")

    git_checkout("1-i")
    git_commits("2-d")

    git_checkout("1-j")
    git_merge("-m", "1-k", "3-c", "4-a")
    git_merge("-m", "1-l", "2-d")


def graph_merge_octopus():
    # Initialize the work tree
    print("Creating: ", git_init("graph_merge_octopus"))

    # Creating initial set of commits
    git_commits("1-a", "1-b")

    # Checkout to 1-a and create another sets of commits
    git_checkout("1-a")
    git_commits("2-a")

    git_checkout("1-a")
    git_commits("3-a")

    git_checkout("1-a")
    git_commits("4-a")

    # Checkout to 1-b and merge multiple branches in an octopus merge
    git_checkout("1-b")
    git_merge("-m", "1-c", "2-a", "3-a", "4-a")


def graph_branch_end():
    # Initialize the work tree
    print("Creating: ", git_init("graph_branch_end"))

    # Creating initial set of commits
    git_commits("1-a", "1-b")

    # Create more commits on different branches
    git_checkout("1-a")
    git_commits("3-a")

    git_checkout("1-a")
    git_commits("4-a")

    git_checkout("1-b")
    git_commits("1-c")
    git_merge("-m", "2-a", "3-a", "4-a")
    git_tag("2-a")

    git_checkout("4-a")
    git_commits("4-b")

    git_checkout("3-a")
    git_commits("3-b")

    git_checkout("2-a")
    git_commits("2-b")

    git_checkout("1-c")
    git_merge("-m", "1-e", "2-b", "3-b", "4-b")


def graph_merge_cross():
    # Initialize the work tree
    print("Creating: ", git_init("graph_merge_cross"))

    # Creating initial set of commits
    git_commits("1-a", "1-b")

    # Create more commits and merges on different branches
    git_checkout("1-a")
    git_commits("3-a")

    git_checkout("1-b")
    git_commits("2-a")

    git_checkout("1-b")
    git_commits("1-c")

    git_checkout("2-a")
    git_merge("-m", "2-b", "1-c", "3-a")
    git_tag("2-b")

    git_checkout("3-a")
    git_commits("3-b")

    git_checkout("2-b")
    git_commits("2-c")

    git_checkout("1-c")
    git_commits("1-d")
    git_merge("-m", "1-e", "2-c", "3-b")


def graph_merge_octopus_left():
    # Initialize the work tree
    print("Creating: ", git_init("graph_merge_octopus_left"))

    # Creating initial set of commits
    git_commits("1-a", "1-b")

    # Create more commits on different branches
    git_checkout("1-a")
    git_commits("2-a")

    git_checkout("1-a")
    git_commits("3-a")

    git_checkout("1-a")
    git_commits("4-a")

    git_checkout("1-b")
    git_merge("-m", "2-b", "2-a", "3-a", "4-a")
    git_tag("2-b")

    git_checkout("1-b")
    git_commits("1-c")


def graph_merge_complex():
    # Initialize the work tree
    print("Creating: ", git_init("graph_merge_complex"))

    # Create and tag initial commits
    git_commits("1-a", "1-b")

    # Create more commits on different branches
    git_checkout("1-a")
    git_commits("3-a", "3-b")

    git_checkout("1-b")
    git_commits("2-a", "2-b")

    git_checkout("1-b")
    git_merge("-m", "1-c", "2-a", "3-a")
    git_merge("-m", "1-d", "2-b", "3-b")


def graph_merge_multiline():
    # Initialize the work tree
    print("Creating: ", git_init("graph_merge_multiline"))

    # Create and tag initial commits
    git_commits("1-a", "1-b", "1-c")

    # Create more commits on different branches
    git_checkout("1-b")
    git_commits("2-a", "2-b")

    git_checkout("1-c")
    git_merge("-m", "1-d", "2-b")
    git_commits("1-e")


def graph_merge_octopus_crossover():
    # Initialize the work tree
    print("Creating: ", git_init("graph_merge_octopus_crossover"))

    # Create and tag initial commits
    git_commits("1-a")

    # Create more commits on different branches
    git_checkout("1-a")
    git_commits("2-a")

    git_checkout("1-a")
    git_commits("3-a")

    git_checkout("1-a")
    git_commits("4-a")

    git_checkout("1-a")
    git_commits("5-a")

    git_checkout("2-a")
    git_merge("-m", "2-b", "3-a", "4-a", "5-a")
    git_tag("2-b")

    git_checkout("1-a")
    git_commits("1-b")


def graph_merge_octopus_crossover_left():
    # Initialize the work tree
    print("Creating: ", git_init("graph_merge_octopus_crossover_left"))

    # Create and tag initial commits
    git_commits("1-a")

    # Create more commits on different branches
    git_checkout("1-a")
    git_commits("2-a")

    git_checkout("1-a")
    git_commits("3-a")

    git_checkout("1-a")
    git_commits("4-a")

    git_checkout("1-a")
    git_commits("1-b", "1-c")

    git_checkout("2-a")
    git_merge("-m", "2-b", "3-a", "4-a", "1-b")
    git_tag("2-b")


def main():
    # Create a list of all 'graph_' functions
    graph_functions = [f for f in globals().keys() if callable(globals()[f]) and f.startswith("graph_")]

    # Create an argument parser
    parser = argparse.ArgumentParser(description="Run one of the test graph functions.")
    parser.add_argument("function", type=str, nargs="?", help="The name of the function to run")

    # Parse command-line arguments
    args = parser.parse_args()
    func_name = args.function

    if func_name == "all":
        for func_name in graph_functions:
            globals()[func_name]()
    elif func_name in globals() and callable(globals()[func_name]):
        globals()[func_name]()
    else:
        if func_name:
            print(f"The function '{func_name}' is not defined.")
        # Print the list of available graph functions
        print("Available functions:")
        for i, func in enumerate(sorted(graph_functions)):
            print(f" {i+1}. {func}")


if __name__ == "__main__":

    main()

This script is adapted from the test cases in this repo: https://github.com/rbong/vim-flog/tree/master/t

If I had to guess, there might be an issue because commits in these test cases are created in quick succession.

I also noticed in other repos the graph didn't quite match what I was seeing with tig, lazygit log and git log --oneline --all --graph. But I figured I'd report this first, since it seemed more pertinent.

[lusingander]

Thank you for your report.

The resolution of the commit date handled by git is 1 second, and the list of commits is sorted by sort_by_key, but since it is managed by a HashMap, the order seems to be unstable. This seems to be causing the problem.

serie/src/graph/calc.rs

Lines 61 to 62 in 779bd6e

	let mut commits = repository.all_commits();
	commits.sort_by_key(|commit| commit.committer_date_sort_key());

Also, although there was no crash, there is something a bit strange at 19 seconds in the graph (commit 2-b) and 22 seconds (commit 2-a).

[kdheepak]

fwiw, I tried modifying your code to not sort manually and rely on the order returned by git ( I added a Vec<Commit> and passed that instead ) and it was still segfaulting.

[lusingander]

Thanks for checking.

The process determines the y-position of the commit in the following steps:

serie/src/graph/calc.rs

Lines 61 to 67 in 779bd6e

	let mut commits = repository.all_commits();
	commits.sort_by_key(|commit| commit.committer_date_sort_key());
	commits = match options.sort {
	SortCommit::Chronological => bfs_topological_sort(commits, repository),
	SortCommit::Topological => dfs_topological_sort(commits, repository),
	};

And if the commits are not topologically ordered, further calculations will fail.

In the case of --order=chrono, since the date is referenced during topological sorting, it seems that the data cannot be sorted topologically correctly.
With --order=topo, it seems like it won't crash or produce strange graph. (The order is not stable, but this is for the reasons mentioned above.)

fwiw, I tried modifying your code to not sort manually and rely on the order returned by git ( I added a Vec and passed that instead ) and it was still segfaulting.

Have you also modified the git command you run? If you don't specify the order like #3, the output of git log doesn't seem to be topologically correct.

[kdheepak]

Have you also modified the git command you run? If you don't specify the order like #3, the output of git log doesn't seem to be topologically correct.

Yes, I changed the code to what I pasted in #3, and commented out the code for calculating stashes.

$ ~/gitrepos/serie/target/debug/serie
The application panicked (crashed).
Message:  index out of bounds: the len is 1 but the index is 1
Location: src/graph/calc.rs:227

  ━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━ BACKTRACE ━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
                                ⋮ 13 frames hidden ⋮
  14: core::panicking::panic_bounds_check::he46a1c3b225e5b31
      at /rustc/faefc618cf48bd794cbc808448df1bf3f59f36af/library/core/src/panicking.rs:274
  15: serie::graph::calc::update_commit_line::h2a9fbab474c3a2a1
      at /Users/USER/gitrepos/serie/src/graph/calc.rs:227
       225 │         }
       226 │     }
       227 >     commit_line_state[min_pos_x] = Some(&commit.commit_hash);
       228 │     min_pos_x as u8
       229 │ }
  16: serie::graph::calc::calc_commit_positions::h5d870706dbb28452
      at /Users/USER/gitrepos/serie/src/graph/calc.rs:167
       165 │             commit_pos_map.insert(&commit.commit_hash, (pos_x, pos_y));
       166 │         } else {
       167 >             let pos_x = update_commit_line(commit, &mut commit_line_state, &filtered_children_hash);
       168 │             commit_pos_map.insert(&commit.commit_hash, (pos_x, pos_y));
       169 │         }
  17: serie::graph::calc::calc_graph::ha079a42ab9210d63
      at /Users/USER/gitrepos/serie/src/graph/calc.rs:68
        66 │     // };
        67 │
        68 >     let commit_pos_map = calc_commit_positions(&commits, repository);
        69 │     let (graph_edges, max_pos_x) = calc_edges(&commit_pos_map, &commits, repository);
        70 │
  18: serie::run::h01d589a161ff4c43
      at /Users/USER/gitrepos/serie/src/lib.rs:112
       110 │         sort: args.order.into(),
       111 │     };
       112 >     let graph = graph::calc_graph(&repository, graph_options);
       113 │
       114 │     let graph_image_options = graph::GraphImageOptions::new(color_set.clone(), args.no_cache);
  19: serie::main::hdfc6600888b789b8
      at /Users/USER/gitrepos/serie/src/main.rs:2
         1 │ fn main() -> std::io::Result<()> {
         2 >     serie::run()
         3 │ }
  20: core::ops::function::FnOnce::call_once::h3751d4ecbc4b8f83
      at /rustc/faefc618cf48bd794cbc808448df1bf3f59f36af/library/core/src/ops/function.rs:250
                                ⋮ 13 frames hidden ⋮

Run with COLORBT_SHOW_HIDDEN=1 environment variable to disable frame filtering.

[kdheepak]

Here's specifically the segfault fault issue.

These are the 3 arguments to update_commit_line:

[src/graph/calc.rs:167:13] &commit = Commit {
    commit_hash: CommitHash(
        "7664bed7fe2fb9a6a414d2ab74eba8935893683f",
    ),
    author_name: "flog",
    author_email: "flog@test.com",
    author_date: 2024-07-04T23:41:23-04:00,
    committer_name: "flog",
    committer_email: "flog@test.com",
    committer_date: 2024-07-04T23:41:23-04:00,
    subject: "2-a",
    body: "* tag '3-a':\n  3-a\n\n* tag '4-a':\n  4-a\n",
    parent_commit_hashes: [
        CommitHash(
            "8cc2ec35e8c3955c49cc517441c8622e111553f6",
        ),
        CommitHash(
            "f3786ec7635c8a92095c7a4db14528e32f17e376",
        ),
        CommitHash(
            "f55cb6830703434d4ced3a52ab35113efd975dcf",
        ),
    ],
    commit_type: Commit,
}
[src/graph/calc.rs:167:13] &commit_line_state = [
    Some(
        CommitHash(
            "9fa17109a645444d93e92aec2516d2b226aac793",
        ),
    ),
]
[src/graph/calc.rs:167:13] &filtered_children_hash = [
    CommitHash(
        "4b38ef0e5cc46e7e8538b8d8b12a1bb74ee6f049",
    ),
]
The application panicked (crashed).
Message:  index out of bounds: the len is 1 but the index is 1
Location: src/graph/calc.rs:228

commit_line_state is length 1, and there's no matches in the for loop.

I made some changes that appear to resolve it now. I'll submit a PR.

[lusingander]

Yes, I changed the code to what I pasted in #3, and commented out the code for calculating stashes.

Would the changes be as follows?

diff --git forkSrcPrefix/src/git.rs forkDstPrefix/src/git.rs
index bf6222345f2d43cf0a4ae91f46da1d32e0167b3a..fea0cf862b25fab97100777e9c59f580dbf0c66c 100644
--- /src/git.rs
+++ /src/git.rs
@@ -122,6 +122,7 @@ type RefMap = HashMap<CommitHash, Vec<Ref>>;
 #[derive(Debug)]
 pub struct Repository {
     path: PathBuf,
+    commits: Vec<Commit>,
     commit_map: CommitMap,
 
     parents_map: CommitsMap,
@@ -135,10 +136,8 @@ impl Repository {
     pub fn load(path: &Path) -> Self {
         check_git_repository(path);
 
-        let mut commits = load_all_commits(path);
-        let stashes = load_all_stashes(path, to_commit_ref_map(&commits));
-
-        commits.extend(stashes);
+        let commits = load_all_commits(path);
+        let commits_cloned = commits.clone();
 
         let (parents_map, children_map) = build_commits_maps(&commits);
         let commit_map = to_commit_map(commits);
@@ -149,6 +148,7 @@ impl Repository {
 
         Self::new(
             path.to_path_buf(),
+            commits_cloned,
             commit_map,
             parents_map,
             children_map,
@@ -159,6 +159,7 @@ impl Repository {
 
     pub fn new(
         path: PathBuf,
+        commits: Vec<Commit>,
         commit_map: CommitMap,
         parents_map: CommitsMap,
         children_map: CommitsMap,
@@ -167,6 +168,7 @@ impl Repository {
     ) -> Self {
         Self {
             path,
+            commits,
             commit_map,
             parents_map,
             children_map,
@@ -180,7 +182,7 @@ impl Repository {
     }
 
     pub fn all_commits(&self) -> Vec<&Commit> {
-        self.commit_map.values().collect()
+        self.commits.iter().collect()
     }
 
     pub fn parents_hash(&self, commit_hash: &CommitHash) -> Vec<&CommitHash> {
@@ -244,6 +246,7 @@ fn load_all_commits(path: &Path) -> Vec<Commit> {
         .arg("--tags")
         .arg(format!("--pretty={}", load_commits_format()))
         .arg("--date=iso-strict")
+        .arg("--date-order")
         .arg("-z") // use NUL as a delimiter
         .current_dir(path)
         .stdout(Stdio::piped())

It seems to work in my environment 🤔

serie.mp4

[kdheepak]

I think when I tested it previously I forgot to make this change:

     pub fn all_commits(&self) -> Vec<&Commit> {
-        self.commit_map.values().collect()
+        self.commits.iter().collect()
     }

Or I made it but forgot to save and build again?

With your patch (identical to my PR) it seems to be working fine.