[patch] Import "git-forest" into contrib/

[patch] Import "git-forest" into contrib/

[Jan Engelhardt]

commit b6612a2efe93660be7ecdb799625015efedadff1
Author: Jan Engelhardt <jengelh@computergmbh.de>
Date:   Tue Mar 18 19:24:33 2008 +0100

     Import "git-forest" into contrib/

diff --git a/contrib/git-forest/git-forest b/contrib/git-forest/git-forest
new file mode 100755
index 0000000..f5d6f81
--- /dev/null
+++ b/contrib/git-forest/git-forest
@@ -0,0 +1,391 @@
+#!/usr/bin/perl
+#
+#	git-森林
+#	text-based tree visualisation
+#	Copyright © Jan Engelhardt <jengelh [at] gmx de>, 2008
+#
+#	This program is free software; you can redistribute it and/or modify
+#	it under the terms of the GNU General Public License as published by
+#	the Free Software Foundation; either version 2 or 3 of the license.
+#
+use Getopt::Long;
+use Git;
+use strict;
+use encoding "utf8";
+my $Repo     = Git->repository($ENV{"GIT_DIR"} || ".");
+my $Style    = 2;
+my $With_sha = 0;
+my %Color    = (
+	"default" => "\e[0m",
+	"at"      => "\e[1;30m",
+	"head"    => "\e[1;32m",
+	"ref"     => "\e[1;34m",
+	"remote"  => "\e[1;35m",
+	"sha"     => "\e[0;31m",
+	"tag"     => "\e[1;33m",
+	"tree"    => "\e[0;33m",
+);
+
+&main();
+
+sub main ()
+{
+	&Getopt::Long::Configure(qw(bundling pass_through));
+	&GetOptions(
+		"no-color" => sub { %Color = (); },
+		"style=i"  => \$Style,
+		"sha"      => \$With_sha,
+	);
+	&process();
+}
+
+sub process ()
+{
+	my(@vine);
+	my $refs = &get_refs();
+	my($fh, $fhc) = $Repo->command_output_pipe("log", "--date-order",
+	                "--pretty=format:<%H><%h><%P>%s", @ARGV);
+
+	while (defined(my $line = <$fh>)) {
+		chomp $line;
+		my($sha, $mini_sha, $parents, $msg) =
+			($line =~ /^<(.*?)><(.*?)><(.*?)>(.*)/s);
+		my @parents = split(" ", $parents);
+
+		&vine_branch(\@vine, $sha);
+		my $ra = &vine_commit(\@vine, $sha, \@parents);
+
+		if (exists($refs->{$sha})) {
+			print &vis_post(&vis_commit($ra,
+			      $Color{at}."─".$Color{default}));
+			&ref_print($refs->{$sha});
+		} else {
+			print &vis_post(&vis_commit($ra, " "));
+		}
+		if ($With_sha) {
+			print $msg, $Color{at}, "──(", $Color{sha}, $mini_sha,
+			      $Color{at}, ")", $Color{default}, "\n";
+		} else {
+			print $msg, "\n";
+		}
+
+		&vine_merge(\@vine, $sha, \@parents);
+	}
+	$Repo->command_close_pipe($fh, $fhc);
+}
+
+sub get_refs ()
+{
+	my($fh, $c) = $Repo->command_output_pipe("show-ref");
+	my $ret = {};
+
+	while (defined(my $ln = <$fh>)) {
+		chomp $ln;
+		if (length($ln) == 0) {
+			next;
+		}
+
+		my($sha, $name) = ($ln =~ /^(\S+)\s+(.*)/s);
+		if (!exists($ret->{$sha})) {
+			$ret->{$sha} = [];
+		}
+		push(@{$ret->{$sha}}, $name);
+		if ($name =~ m{^refs/tags/}) {
+			my $sub_sha = $Repo->command("log", "-1",
+			              "--pretty=format:%H", $name);
+			chomp $sub_sha;
+			if ($sha ne $sub_sha) {
+				push(@{$ret->{$sub_sha}}, $name);
+			}
+		}
+	}
+
+	$Repo->command_close_pipe($fh, $c);
+	return $ret;
+}
+
+sub ref_print ($)
+{
+	foreach my $symbol (@{shift @_}) {
+		print $Color{at}, "[";
+		if ($symbol =~ m{^refs/(remotes/[^/]+)/(.*)}s) {
+			print $Color{remote}, $1, $Color{head}, "/$2";
+		} elsif ($symbol =~ m{^refs/heads/(.*)}s) {
+			print $Color{head}, $1;
+		} elsif ($symbol =~ m{^refs/tags/(.*)}s) {
+			print $Color{tag}, $1;
+		} elsif ($symbol =~ m{^refs/(.*)}s) {
+			print $Color{ref}, $1;
+		}
+		print $Color{at}, "]──", $Color{default};
+	}
+}
+
+sub vine_branch ($$)
+{
+	my($vine, $rev) = @_;
+	my $idx;
+
+	my $left = "╠";
+	my $matched = 0;
+	my $ret;
+
+	for ($idx = 0; $idx < scalar(@$vine); ++$idx) {
+		if (!defined($vine->[$idx])) {
+			$ret .= "═";
+			next;
+		} elsif ($vine->[$idx] ne $rev) {
+			$ret .= "╪";
+			next;
+		}
+		if ($matched == 0) {
+			$ret .= "╠";
+		} else {
+			$ret .= "╩";
+			$vine->[$idx] = undef;
+		}
+		++$matched;
+	}
+
+	if ($matched < 2) {
+		return;
+	}
+
+	while (!defined($vine->[$#$vine])) {
+		pop(@$vine);
+	}
+
+	print &vis_post(&vis_branch($ret)), "\n";
+}
+
+sub vine_commit ($$$)
+{
+	my($vine, $rev, $parents) = @_;
+	my $ret;
+
+	for (my $i = 0; $i <= $#$vine; ++$i) {
+		if (!defined($vine->[$i])) {
+			$ret .= " ";
+		} elsif ($vine->[$i] eq $rev) {
+			$ret .= "╟";
+		} else {
+			$ret .= "║";
+		}
+	}
+
+	if ($ret !~ /╟/) {
+		# Not having produced a ╟ before means this is a HEAD
+		$ret .= "╓";
+		push(@$vine, $rev);
+	}
+
+	while (scalar(@$vine) > 0 && !defined($vine->[$#$vine])) {
+		pop(@$vine);
+	}
+
+	if (scalar(@$parents) == 0) {
+		# tree root
+		$ret =~ s/╟/╙/g;
+	}
+
+	return $ret;
+}
+
+#
+#	Generate vine graphics for a merge
+#
+sub vine_merge ($$$)
+{
+	my($vine, $rev, $parents) = @_;
+	my $orig_vine = -1;
+	my @slot;
+	my($ret, $max);
+
+	for (my $i = 0; $i <= $#$vine; ++$i) {
+		if ($vine->[$i] eq $rev) {
+			$orig_vine = $i;
+			last;
+		}
+	}
+
+	if ($orig_vine == -1) {
+		die "vine_commit() did not add this vine.";
+	}
+
+	if (scalar(@$parents) <= 1) {
+		#
+		# A single parent does not need a visual. Update and return.
+		#
+		$vine->[$orig_vine] = $parents->[0];
+
+		while (scalar(@$vine) > 0 && !defined($vine->[$#$vine])) {
+			pop(@$vine);
+		}
+		return;
+	}
+
+	#
+	# Find some good spots to split out into.
+	#
+	push(@slot, $orig_vine);
+	my $parent = 0;
+
+	for (my $seeker = 2; $parent < $#$parents &&
+	    $seeker < 2 + 2 * $#$vine; ++$seeker)
+	{
+		my $idx = ($seeker % 2 == 0) ? -1 : 1;
+		$idx   *= int($seeker / 2);
+		$idx   += $orig_vine;
+
+		if ($idx >= 0 && $idx <= $#$vine && !defined($vine->[$idx])) {
+			push(@slot, $idx);
+			++$parent;
+		}
+	}
+	for (my $idx = $orig_vine + 1; $parent < $#$parents; ++$idx) {
+		if (!defined($vine->[$idx])) {
+			push(@slot, $idx);
+			++$parent;
+		}
+	}
+
+	if (scalar(@slot) != scalar(@$parents)) {
+		die "Serious internal problem";
+	}
+
+	@slot = sort { $a <=> $b } @slot;
+	$max  = scalar(@$vine) + scalar(@slot);
+
+	for (my $i = 0; $i < $max; ++$i) {
+		if ($#slot >= 0 && $i == $slot[0]) {
+			shift @slot;
+			$vine->[$i] = shift @$parents;
+			$ret .= ($i == $orig_vine) ? "S" : "s";
+		} elsif (defined($vine->[$i])) {
+			$ret .= "║";
+		} else {
+			$ret .= " ";
+		}
+
+	}
+
+	$ret =~ s/ +$//gs;
+	print &vis_post(&vis_merge($ret)), "\n";
+}
+
+sub vis_branch ($)
+{
+	# Sample input: ╬═╠╬╬╬╩╬═╬╬╬╬╬╬╩╬╩═╬╬
+	my $ra = shift @_;
+	my $i;
+
+	$ra =~ s{^(.+?)╠}{
+		$_ = $1;
+		$_ =~ tr/╪═/║ /;
+		$_ =~ s/(.)/$1 /gs;
+		$_ .= '╠';
+	}es;
+	$ra =~ s{(╠.*)╩}{
+		$_ = $1;
+		$_ =~ s/(.)/$1═/gs;
+		$_ .= '╝';
+	}es;
+	$ra =~ s{╝(.*)$}{
+		$_ = $1;
+		$_ =~ tr/╪═/║ /;
+		$_ =~ s/(.)/$1 /gs;
+		$_ = "╝ $_";
+	}es;
+	return $ra;
+}
+
+sub vis_commit ($$)
+{
+	my($ra, $sep) = @_;
+	my($l, $r) = ($ra =~ /^(.*?)([╟╓╙].*)/);
+	$l =~ s/(.)/$1 /gs;
+	$r =~ s/(.)/$1 /gs;
+	$r =~ s/ /$sep/gs;
+	return $l.$r;
+}
+
+sub vis_merge ($)
+{
+	my $s = shift @_;
+
+	if ($s =~ s/(s.*)S(.*s)/&vis_merge3($1, $2)/es) {
+		;
+	} elsif ($s =~ /(?:s.*)S/s) {
+		while ($s =~ s/(s.*)║(.*S)/$1╪$2/s) {
+			;
+		}
+		$s =~ s/(s.*)S/&vis_merge2L($1)."╣"/es;
+	} elsif ($s =~ /S(?:.*s)/s) {
+		while ($s =~ s/(S.*)║(.*s)/$1╪$2/s) {
+			;
+		}
+		$s =~ /S(.*s)/;
+		$s =~ s/S(.*s)/"╠".&vis_merge2R($1)/es;
+	} else {
+		# $s =~ s/S/║/s;
+		die "Should not come here";
+	}
+	$s =~ s{(.)}{&vis_merge1($1)}egs;
+	return $s;
+}
+
+sub vis_merge1 ($)
+{
+	if ($_[0] eq "╔" || $_[0] eq "╦" || $_[0] eq "╠" || $_[0] eq "╪") {
+		return $_[0]."═";
+	} else {
+		return $_[0]." ";
+	}
+}
+
+sub vis_merge2L ($)
+{
+	my $l = shift @_;
+	$l =~ s/^s/╔/;
+	$l =~ s/s/╦/g;
+	return $l;
+}
+
+sub vis_merge2R ($)
+{
+	my $r = shift @_;
+	$r =~ s/s$/╗/;
+	$r =~ s/s/╦/g;
+	return $r;
+}
+
+sub vis_merge3 ($$)
+{
+	my($l, $r) = shift @_;
+	$l =~ s/^s/╔/;
+	$l =~ s/s/╦/g;
+	$r =~ s/s$/╗/;
+	$r =~ s/s/╦/g;
+	return "$l╪$r";
+}
+
+#
+#	post-process vine graphic
+#
+sub vis_post ($)
+{
+	my $s = shift @_;
+
+	if ($Style == 1) {
+		$s =~ tr/╔╦╗╠╬╣╚╩╝║═╟╓╙╪/┌┬┐├┼┤└┴┘│─├┌└┼/;
+	} elsif ($Style == 2) {
+		$s =~ tr/╪/╬/;
+	} elsif ($Style == 3) {
+		$s =~ tr/╔╦╗╠╬╣╚╩╝║╟╓╙/╒╤╕╞╪╡╘╧╛│├┌└/;
+	}
+
+	if ($Color{default} ne "") {
+		$s =~ s{\Q$Color{default}\E}{$&$Color{tree}}g;
+	}
+	return $Color{tree}, $s, $Color{default};
+}
diff --git a/contrib/git-forest/git-forest.txt b/contrib/git-forest/git-forest.txt
new file mode 100644
index 0000000..0adfd6d
--- /dev/null
+++ b/contrib/git-forest/git-forest.txt
@@ -0,0 +1,34 @@
+
+Options:
+
+--style=1
+	Use single-line visuals
+--style=2
+	Use double-line visuals (default)
+--style=3
+	Use single-line visuals in vertical direction,
+	and double-line ones in horizontal direction.
+--sha
+	Display SHAs for each commit
+
+All other options and arguments are passed down to git-log.
+Commonly useful are --all and --topo-order; along with the
+tag name or commit range.
+
+This tool does not try to minimize the empty space between branches
+like gitk does. Take it as a feature.
+
+Notes on interpretation:
+
+'╬' (or variants thereof, like ╪) is meant to be a "path bridge", i.e.
+traversal is only "allowed" horizontal OR vertical direction.
+
+Branching:
+C D E F G
+╠═╬═╩═╩═╝  A->{C,E,F,G} and B->D.
+A B
+
+Merging:
+E F
+╠═╬═╦═╗    {A,C,D}->E, B->F.
+A B C D

Re: [patch] Import "git-forest" into contrib/

[Miklos Vajna]

[-- Attachment #1: Type: text/plain, Size: 307 bytes --]

On Tue, Mar 18, 2008 at 07:25:38PM +0100, Jan Engelhardt <jengelh@computergmbh.de> wrote:
> commit b6612a2efe93660be7ecdb799625015efedadff1
> Author: Jan Engelhardt <jengelh@computergmbh.de>
> Date:   Tue Mar 18 19:24:33 2008 +0100
> 
>     Import "git-forest" into contrib/

missing signed-off-by?

[-- Attachment #2: Type: application/pgp-signature, Size: 189 bytes --]

Re: [patch] Import "git-forest" into contrib/

[Jan Engelhardt]

On Mar 19 2008 22:11, Miklos Vajna wrote:

> On Tue, Mar 18, 2008 at 07:25:38PM +0100, Jan Engelhardt <jengelh@computergmbh.de> wrote:
>> commit b6612a2efe93660be7ecdb799625015efedadff1
>> Author: Jan Engelhardt <jengelh@computergmbh.de>
>> Date:   Tue Mar 18 19:24:33 2008 +0100
>>
>>     Import "git-forest" into contrib/
>
> missing signed-off-by?
>

Wasnot sure if it's used for git too;

Signed-off-by: Jan Engelhardt <jengelh@computergmbh.de>

Re: [patch] Import "git-forest" into contrib/

[Junio C Hamano]

Jan Engelhardt <jengelh@computergmbh.de> writes:

> On Mar 19 2008 22:11, Miklos Vajna wrote:
>
>> On Tue, Mar 18, 2008 at 07:25:38PM +0100, Jan Engelhardt <jengelh@computergmbh.de> wrote:
>>> commit b6612a2efe93660be7ecdb799625015efedadff1
>>> Author: Jan Engelhardt <jengelh@computergmbh.de>
>>> Date:   Tue Mar 18 19:24:33 2008 +0100
>>>
>>>     Import "git-forest" into contrib/
>>
>> missing signed-off-by?
>>
>
> Wasnot sure if it's used for git too;

Yes.

git also expects the kernel style e-mails, and it is _NOT_ "dump output
from 'git show' in the message, commit/Author:/Date: headers and message
indented by 4-spaces" format.

As to the contents, I did not understand this part.

+Notes on interpretation:
+
+'╬' (or variants thereof, like ╪) is meant to be a "path bridge", i.e.
+traversal is only "allowed" horizontal OR vertical direction.
+
+Branching:
+C D E F G
+╠═╬═╩═╩═╝  A->{C,E,F,G} and B->D.
+A B

So the horizontal line bridge goes over the vertical road between B and D
and these two will not get connection to anything else.  That part I
understand.

 (1) Why then is that horizontal bridge connected to E, F and G?  Do
     pluses and inverted Ts have different meaning?  What about the
     sideway T between A and C?

 (2) If you want to express D is merge between A and B, and C, E, F, G are
     independent children of A, how would you write it?

Did you mean "Connection with three legs (T, inverted T, sideways T) mean
all sides are connected, connection with four legs (+) mean horizontal and
vertical are independent and disconnected"?

Re: [patch] Import "git-forest" into contrib/

[Jan Engelhardt]

On Mar 19 2008 14:52, Junio C Hamano wrote:
>
> git also expects the kernel style e-mails, and it is _NOT_ "dump output
> from 'git show' in the message, commit/Author:/Date: headers and message
> indented by 4-spaces" format.

Actually, it's `git log -1 -p` that I used. PINE traditionally
trashes the direct mbox output of git, i.e. Message-ID is rewritten
by PINE again when using Continue Postponed, but apparently only on
non-PINE messages to begin with. I just recently switched to alpine,
maybe it's better there.

> As to the contents, I did not understand this part.
>
> +Notes on interpretation:
> +
> +'╬' (or variants thereof, like ╪) is meant to be a "path bridge", i.e.
> +traversal is only "allowed" horizontal OR vertical direction.
> +
> +Branching:
> +C D E F G
> +╠═╬═╩═╩═╝  A->{C,E,F,G} and B->D.
> +A B
>
> So the horizontal line bridge goes over the vertical road between B and D
> and these two will not get connection to anything else.  That part I
> understand.
>
> (1) Why then is that horizontal bridge connected to E, F and G?  Do
>     pluses and inverted Ts have different meaning?  What about the
>     sideway T between A and C?

> Did you mean "Connection with three legs (T, inverted T, sideways T) mean
> all sides are connected, connection with four legs (+) mean horizontal and
> vertical are independent and disconnected"?

Yes. Would

#       Connections with four "legs" ('╬' or variants thereof, like
#       '╪') are 
#       meant to be interpreted as being connected only in the
#       horizontal and 
#       vertical direction, NOT around-the-corner. 
# 
#       Connections with three or less "legs" ('╠', '╩', '╦', etc.)
#       imply 
#       a connection to all connected directions.

work as help text?

> (2) If you want to express D is merge between A and B, and C, E, F, G are
>     independent children of A, how would you write it?

A..G in the above are actually placeholders for more wood
instead of placeholders for commits.

So (one possible) answer to your question — since you can only
be referring to commits :-) — would be:


╓─[master]──[G]──sm7
║ ╓─[F]──sm6
║ ║ ╓─[E]──sm5
║ ║ ║ ╓─[C]──sm4
║ ║ ║ ║ ╓─[D]──something3
║ ║ ║ ║ ╠═╗ 
║ ║ ║ ║ ╟─║─[B]──something2
╠═╩═╩═╩═╬═╝ 
╟───────║─[A]──something1
╠═══════╝ 
╙ Initial

depending on the order you committed (or flags like
--date-order/--topo-order).

If one commit is added to D, the picture shifts a bit:

╓─[master]──c8
║ ╓─[G]──sm7
║ ║ ╓─[F]──sm6
║ ║ ║ ╓─[E]──sm5
║ ║ ║ ║ ╓─[C]──sm4
╟─║─║─║─║─[D]──something3
╠═╬═╬═╬═╬═╗ 
╟─║─║─║─║─║─[B]──something2
║ ╠═╩═╩═╩═╝ 
║ ╟─[A]──something1
╠═╝ 
╙ Initial

Re: [patch] Import "git-forest" into contrib/

[Miklos Vajna]

[-- Attachment #1: Type: text/plain, Size: 447 bytes --]

On Wed, Mar 19, 2008 at 11:23:55PM +0100, Jan Engelhardt <jengelh@computergmbh.de> wrote:
> Actually, it's `git log -1 -p` that I used. PINE traditionally
> trashes the direct mbox output of git, i.e. Message-ID is rewritten
> by PINE again when using Continue Postponed, but apparently only on
> non-PINE messages to begin with. I just recently switched to alpine,
> maybe it's better there.

or just use git-send-email if your mailer is broken.

[-- Attachment #2: Type: application/pgp-signature, Size: 189 bytes --]

Re: [patch] Import "git-forest" into contrib/

[Jakub Narebski]

Jan Engelhardt wrote:

> diff --git a/contrib/git-forest/git-forest b/contrib/git-forest/git-forest
> new file mode 100755
> index 0000000..f5d6f81
> --- /dev/null
> +++ b/contrib/git-forest/git-forest
> @@ -0,0 +1,391 @@
> +#!/usr/bin/perl
> +#
> +#      git-??

Eh?

-- 
Jakub Narebski
Warsaw, Poland
ShadeHawk on #git