Graph rendering error

[bbolli]

There's a graph rendering error:

$ git log --pretty=raw --parents -8 d10dcd8 | ./test-graph
● Do not include merges in the announcement's change log
●━┑ Merge pull request #81 from esc/fix/reading_git_colors_256
●━┑ Merge pull request #80 from esc/fix/option_name_mismatch
● │ Reenable copy/rename detection in the status view
│ ● fix: the manpage says 'read-git-colors'
│ │ ● fix: reading git colors in rang 0 255
◎─┴─┘ Remove enforced diff move/copy detection
● Optionally show commit IDs for branches and tree entries

Compare to Git's output:

$ git log --oneline --graph -8 d10dcd8
* d10dcd8 Do not include merges in the announcement's change log
*   7cdab00 Merge pull request #81 from esc/fix/reading_git_colors_256
|\  
| * 54e8c4d fix: reading git colors in rang 0 255
* |   7368b5b Merge pull request #80 from esc/fix/option_name_mismatch
|\ \  
| * | 0431cd2 fix: the manpage says 'read-git-colors'
| |/  
* | 82458a4 Reenable copy/rename detection in the status view
|/  
* 6d276a6 Remove enforced diff move/copy detection
* c5aaa84 Optionally show commit IDs for branches and tree entries

[jonas]

Hey, I completely hear you. The graph rendering is pretty much broken for anything other than repositories with mostly linear history and an occasional branch.

[bbolli]

Any chance to reuse the graph code from Git? I realize that you'd have to get rid of the "one line per commit" scheme Tig currently uses (at least if the graph is displayed).

[jonas]

I didn't investigate git's text-mode graph code, but it would be an excellent candidate. As you note, it would require some changes to how commits are displayed and would need some adjustment to use the "square" UTF-8 inspired graph symbols, like "┐" in stead of "\".

[ThomasAdam]

I looked at this a few years ago---it's certainly possible, although in terms of reusing Git's graphing more closely, I wonder how receptive Git would be to allowing UTF8 characters for displaying the graph in cases where UTF8 was supported by the terminal? That way you could almost retain the output tig is using now.

[yasuoza]

Revision graph is still broken in version 1.2. I like tig, so I wish this will be solved in near future.

[majutsushi]

I agree, this makes more complex histories very hard to follow.

[BenBergman]

Is anyone actively working on this? I might take a stab at this, but would rather help someone out if they are already started.

[jonas]

Nobody is working on this as far as I know. I'm currently working mainly on splitting up the massive tig.c file. On Oct 24, 2013 6:09 PM, "Benjamin Bergman" notifications@github.com wrote:

Is anyone actively working on this? I might take a stab at this, but would rather help someone out if they are already started.

— Reply to this email directly or view it on GitHubhttps://github.com/jonas/tig/issues/144#issuecomment-27035993 .

[BenBergman]

I spent the evening fiddling with the graph printouts and I think it is at least better now. I won't bother with a PR until I've done some more testing, but if anyone else wants to try it out, my bugfix branch is here: https://github.com/BenBergman/tig/tree/fix-graph

I would appreciate getting some more sample repositories to use for testing edge cases. If you have a repository that still doesn't work quite right, please send me a printout of the git log --pretty=raw --parents command for the appropriate commits. The weirder the better (octopus merges, parallel histories, etc.). You can cut out most of the content and it will still work with test-graph, it just needs to have a commit line with parents and a message line for each commit. For example (using single character SHA-1s)

commit f e d
    Merge branch 'branch3'
commit e b c
    Merge branch 'branch2'
commit d a
    branch3
commit c a
    branch2
commit b a
    branch1
commit a
    init

produces

●─┐ Merge branch 'branch3'
│ ●─┐ Merge branch 'branch2'
● │ │ branch3
│ │ ● branch2
│ ● │ branch1
◎─┴─┘ init

Previously it was printing

●━┑ Merge branch 'branch3'
●━┑ Merge branch 'branch2'
│ │ ● branch3
│ ● │ branch2
● │ │ branch1
◎─┴─┘ init

If submitting broken graph examples, it might also be useful to see the output of git log --oneline --graph --decorate --color for comparison.

@jonas : if it is alright with you, I'm thinking I'll check in a bunch of these samples and their expected output as a sort of unit test. That way anyone else that comes along and wants to fiddle with the graph code can do so without fear of breaking the already tested edge cases. Perhaps they can go in a sub-directory in tools, along with a script to validate them all.

[BenBergman]

I pushed a few more updates over the weekend which work fine in the test-graph application, but I just noticed tig is now segfaulting, so I'll need to look into that a bit. Otherwise, the improvements are coming along nicely. :smile:

[jonas]

Cool, I'll take a look. On Oct 28, 2013 10:42 AM, "Benjamin Bergman" notifications@github.com wrote:

I pushed a few more updates over the weekend which work fine in the test-graph application, but I just noticed tig is now segfaulting, so I'll need to look into that a bit. Otherwise, the improvements are coming along nicely. [image: :smile:]

— Reply to this email directly or view it on GitHubhttps://github.com/jonas/tig/issues/144#issuecomment-27216971 .

[BenBergman]

I had to take a break from my graph fix for a little while, but I have now fixed the segfault and improved the graph drawing even further. You can try it out in my branch (https://github.com/BenBergman/tig/tree/fix-graph). I still have a couple more things to fix up, plus I should rebase onto the new master, but I'd be happy to have some feedback. If anything looks wonky, I'd happily accept some git log --pretty=raw --parents to work from and what output you expected.

[jonas]

I am still trying to catch up with my Tig backlog. Looking at your test cases it looks awesome. Hope to see this merged soon.

[BenBergman]

I've made some good progress, but I've got an edge case I'm having a hard time working around. See this gist for reference: https://gist.github.com/BenBergman/8605367 (github shows unicode line drawings a little oddly, so you might want to copy into your faVourIte terMinal editor.)

The situation is that there is a commit that is both a merge commit and a branching point, thus it has multiple lines extending upwards and multiple lines extending downwards. This is commit C in the above example. The first, longer sample output is how it is currently being displayed. At first glance, it looks like B might be the parent of F, but in fact C is the actual parent.

Below that is roughly what git log --graph --oneline might spit out. As you can see, it relies an multiple non-commit rows in order to draw something unambiguous, which we do not have space for in tig.

Option 1 is kind of ugly, but I think it does an okay job of conveying meaning.

Options 2-6 are basically the same solution with different symbol options. For the UTF8 display mode, I would like to stick with the line drawing characters as any other character I found either didn't look very good there (which is the whole point of the UTF8 display, in my opinion) or it did not render on at least one of my machines. Options 2 and 5 do this, but the symbol for 2 doesn't always have a break in the vertical line, and the symbol for 5 makes it almost as ambiguous as the original.

Options 7-10 are a different approach which will complicate the logic a bit (ie. having lines out the left of commits and, in the case of 7, having a special curling down symbol next to the left line), but should be doable.

I'm not totally sure which approach makes the most sense or if there is any other option that I'm missing. As far as I can tell, either the vertical or horizontal line must be shared between the merge and the branch. I personally like something from options 1-6 as it more or less indicates directly on the Commit C line that it is both a branch and a merge, whereas 7-10 require you following the shared vertical line up to the branch point to discover that Commit C was a branch point.

So, anyone have an opinion on the best option? Can anyone suggest a better option that will be obvious in meaning and nice looking in UTF8 and ASCII mode?

[jonas]

Taking a look now.

BTW, let me find my guitar and play these crazy tabs your drew. Maybe knowing how they sounds will help decide the best option. ;-)

[jonas]

First, let me say that the graph rendering in your fix-graph branch looks really great.

Regarding your proposals, I personally like 1, 2, 5 and 6. And in any case, I think that given the limitations of Unicode box-drawing characters the only way we could potentially render this type of situation would be to add 'non-commit' lines like git log --graph does. For example:

│ │ ● │ Commit F after C
│ ● │ │ Commit E after D
├─│─┘ │
●─│─┐ │ Commit C - Merge B into A
│ ● │ │ Commit D after Q
│ │ ● │ Commit B after R

I never actually checked how hard it would be to do such a thing.

[BenBergman]

I think your example does look the cleanest and least ambiguous, which would be especially useful if we end up with an octopus merge that is the base for many different branches, but I'm not sure how difficult it would be to insert non-commit lines with the current structure. Specifically, the current logic is only aware of what the previous line was, what the previous line expects the current line to look like, and what the current line expects the next line to look like. Under these constraints, I'm not sure how difficult it would be decide on a time to inject a non-commit row. One possible way to decide is if we have multiple columns that need to connect to the current commit and the current commit is a merge commit, inject a non-commit line. This logic is relatively straight forward, but I have no idea how I might implement the non-commit rows as I've been solely poking around the graph code.

Perhaps I'll leave this particular edge case for later and try to poke around at the possibility of adding a non-commit row once I get there.

[BenBergman]

Ok, I think I'm more or less done with updating the main logic. If you run my "unit tests" (https://github.com/BenBergman/tig/tree/fix-graph) you can see there are still a few error cases, but I think they are all related to the merge + branch commit thing. I haven't looked into how a non-commit line might be done yet, and likely won't for a while. I just have a few more items on my list and then I think I'll be ready for a pull request.

• [x] Reimplement colouring
• [ ] Ideally get crossover colours working as well
• [x] Get ASCII output working
• [x] Remove dead code
• [x] Organize new logic
• [x] Improve speed
• [ ] Implement option 2 from my above Gist as a 'temporary' fix for the merge-branch issue...?
• [ ] Fix a few small remaining bugs

Am I missing anything you think should be present in the pull request?

Do you have a preferred way to have the pull request formatted? I know some projects like a single feature/bugfix as a single commit, rebased on top of current master. Others like the full set of commits just as they were. I know at least some of my commit messages are poorly written as I used them basically as a save-state and just kept working.

[BenBergman]

@jonas: I'm thinking it would be nice to use a hash-table/map in the colour selection code. I could try to implement something myself, but there would be more robustness if we used something off the shelf. Would you mind using a third party library?

I found this StackOverflow answer that lists several different options: http://stackoverflow.com/questions/1138742/looking-for-a-good-hash-table-implementation-in-c/8470745#8470745

[jonas]

Regarding the pull request, I left that they are rebased on top of master with commits squashed to make them easier to review.

And yes, let's reuse an existing hash table library. Did you have a closer look on some of the listed implementations? On Jan 29, 2014 1:28 AM, "Benjamin Bergman" notifications@github.com wrote:

@jonas https://github.com/jonas: I'm thinking it would be nice to use a hash-table/map in the colour selection code. I could try to implement something myself, but there would be more robustness if we used something off the shelf. Would you mind using a third party library?

I found this StackOverflow answer that lists several different options: http://stackoverflow.com/questions/1138742/looking-for-a-good-hash-table-implementation-in-c/8470745#8470745

— Reply to this email directly or view it on GitHubhttps://github.com/jonas/tig/issues/144#issuecomment-33559893 .

[jonas]

Another candidate is hashtab from libiberty, since Tig is already using stuff from there. On Jan 29, 2014 7:38 AM, "Jonas Fonseca" jonas.fonseca@gmail.com wrote:

Regarding the pull request, I left that they are rebased on top of master with commits squashed to make them easier to review.

And yes, let's reuse an existing hash table library. Did you have a closer look on some of the listed implementations? On Jan 29, 2014 1:28 AM, "Benjamin Bergman" notifications@github.com wrote:

@jonas https://github.com/jonas: I'm thinking it would be nice to use a hash-table/map in the colour selection code. I could try to implement something myself, but there would be more robustness if we used something off the shelf. Would you mind using a third party library?

I found this StackOverflow answer that lists several different options: http://stackoverflow.com/questions/1138742/looking-for-a-good-hash-table-implementation-in-c/8470745#8470745

— Reply to this email directly or view it on GitHubhttps://github.com/jonas/tig/issues/144#issuecomment-33559893 .

[BenBergman]

Thanks for the hashtab recommendation. It did the trick (see my branch for it in use).

[BenBergman]

I'm considering changing the UTF8 corner characters from the sharp angles to the nice rounded ones. Thoughts? The sharp ones would still be used for the default (chtype) graphics mode.

old: ┌┐┘└
new: ╭╮╯╰

OLD:

NEW:

[MattWoelk]

Those curved lines look excellent. They definitely lead the eye better than the right angles.

[bbolli]

I have found a regression in the new graph code: when loading the official Git repo at commit 614c158afed5077691c76d341b6888596b24b9fd (currently the tip of branch "next"), I get a realloc() error:

I can't open an issue on @BenBergman's tig clone, so I'm appending this here.

[jonas]

Wow, @BenBergman the rounded corners and graph colouring look amazing.

[BenBergman]

@bbolli Thanks for pointing that out. I'll take a look.

@jonas Thanks. :) I'll commit the rounded corners now.

[jonas]

I wonder also if you could rebase on top of current master. I had an issue with building on a Mac and that is fixed in master. On Jan 31, 2014 9:41 PM, "Benjamin Bergman" notifications@github.com wrote:

@bbolli https://github.com/bbolli Thanks for pointing that out. I'll take a look.

@jonas https://github.com/jonas Thanks. :) I'll commit the rounded corners now.

— Reply to this email directly or view it on GitHubhttps://github.com/jonas/tig/issues/144#issuecomment-33861166 .

[BenBergman]

@jonas I have rebased onto the latest master. Let me know how that works for you. There was one conflict with the changes introduced by #217. I think I merged it well, but I have not really done anything with boundary commits thus far so I'm a little unsure.

[BenBergman]

@bbolli I pushed a fix for the realloc error you were seeing (BenBergman/tig@deeb725). I feel like it isn't a very proper fix, but the allocator macro code seems like it should be solid enough to do the right thing.

[BenBergman]

Last night I more or less fixed the speed issue I was having and I got my code somewhat organized. I noticed a couple more edge cases where there was the wrong symbol being displayed, so once I fix that up, I think I'll be ready to submit a PR.

Because of the scope of the changes required, I will leave the cross-over line colouring and the non-commit lines as related but separate features that I can hopefully make time for in the future. The non-commit line feature could also come in handy for line wrapping as mentioned in issue #2. My only concern is that the graph will not wrap well, if at all, when it has too many columns.

[BenBergman]

@bbolli - FYI, in the pull request I managed to implement a much better fix for the realloc error you were seeing.

[rofrol]

Doesn't work for me when using tig. Graph lines are displayed incorrectly as x. Though this characters are display correctly in command line using Dejavu Sans Mono: ╭╮╯╰

I've set font according to this http://superuser.com/questions/393834/how-to-configure-putty-to-display-these-characters

[bbolli]

@rofrol Try hitting ~ (tilde) a few times. This changes the set of characters used to display the graph.