Render the git graph on the server (#12333)

Rendering the git graph on the server means that we can properly track flows and switch from the Canvas implementation to a SVG implementation.

* This implementation provides a 16 limited color selection
* The uniqued color numbers are also provided
* And there is also a monochrome version
*In addition is a hover highlight that allows users to highlight commits on the same flow.

Closes #12209

Signed-off-by: Andrew Thornton art27@cantab.net
Co-authored-by: silverwind <me@silverwind.io>

1 files changed, 654 insertions, 12 deletions

diff --git a/modules/gitgraph/graph_test.go b/modules/gitgraph/graph_test.go
index a2c7f447b6..ca9d653cee 100644
--- a/modules/gitgraph/graph_test.go
+++ b/modules/gitgraph/graph_test.go
@@ -5,7 +5,9 @@
 package gitgraph
 
 import (
+	"bytes"
 	"fmt"
+	"strings"
 	"testing"
 
 	"code.gitea.io/gitea/modules/git"
@@ -14,40 +16,235 @@ import (
 func BenchmarkGetCommitGraph(b *testing.B) {
 
 	currentRepo, err := git.OpenRepository(".")
-	if err != nil {
+	if err != nil || currentRepo == nil {
 		b.Error("Could not open repository")
 	}
 	defer currentRepo.Close()
 
 	for i := 0; i < b.N; i++ {
-		graph, err := GetCommitGraph(currentRepo, 1)
+		graph, err := GetCommitGraph(currentRepo, 1, 0)
 		if err != nil {
 			b.Error("Could get commit graph")
 		}
 
-		if len(graph) < 100 {
+		if len(graph.Commits) < 100 {
 			b.Error("Should get 100 log lines.")
 		}
 	}
 }
 
 func BenchmarkParseCommitString(b *testing.B) {
-	testString := "* DATA:||4e61bacab44e9b4730e44a6615d04098dd3a8eaf|2016-12-20 21:10:41 +0100|Kjell Kvinge|kjell@kvinge.biz|4e61bac|Add route for graph"
+	testString := "* DATA:|4e61bacab44e9b4730e44a6615d04098dd3a8eaf|2016-12-20 21:10:41 +0100|Kjell Kvinge|kjell@kvinge.biz|4e61bac|Add route for graph"
 
+	parser := &Parser{}
+	parser.Reset()
 	for i := 0; i < b.N; i++ {
-		graphItem, err := graphItemFromString(testString, nil)
-		if err != nil {
+		parser.Reset()
+		graph := NewGraph()
+		if err := parser.AddLineToGraph(graph, 0, []byte(testString)); err != nil {
 			b.Error("could not parse teststring")
 		}
-
-		if graphItem.Author != "Kjell Kvinge" {
+		if graph.Flows[1].Commits[0].Author != "Kjell Kvinge" {
 			b.Error("Did not get expected data")
 		}
 	}
 }
 
+func BenchmarkParseGlyphs(b *testing.B) {
+	parser := &Parser{}
+	parser.Reset()
+	tgBytes := []byte(testglyphs)
+	tg := tgBytes
+	idx := bytes.Index(tg, []byte("\n"))
+	for i := 0; i < b.N; i++ {
+		parser.Reset()
+		tg = tgBytes
+		idx = bytes.Index(tg, []byte("\n"))
+		for idx > 0 {
+			parser.ParseGlyphs(tg[:idx])
+			tg = tg[idx+1:]
+			idx = bytes.Index(tg, []byte("\n"))
+		}
+	}
+}
+
+func TestReleaseUnusedColors(t *testing.T) {
+	testcases := []struct {
+		availableColors []int
+		oldColors       []int
+		firstInUse      int // these values have to be either be correct or suggest less is
+		firstAvailable  int // available than possibly is - i.e. you cannot say 10 is available when it
+	}{
+		{
+			availableColors: []int{1, 2, 3, 4, 5, 6, 7, 8, 9, 10},
+			oldColors:       []int{1, 1, 1, 1, 1},
+			firstAvailable:  -1,
+			firstInUse:      1,
+		},
+		{
+			availableColors: []int{1, 2, 3, 4, 5, 6, 7, 8, 9, 10},
+			oldColors:       []int{1, 2, 3, 4},
+			firstAvailable:  6,
+			firstInUse:      0,
+		},
+		{
+			availableColors: []int{1, 2, 3, 4, 5, 6, 7, 8, 9, 10},
+			oldColors:       []int{6, 0, 3, 5, 3, 4, 0, 0},
+			firstAvailable:  6,
+			firstInUse:      0,
+		},
+		{
+			availableColors: []int{1, 2, 3, 4, 5, 6, 7},
+			oldColors:       []int{6, 1, 3, 5, 3, 4, 2, 7},
+			firstAvailable:  -1,
+			firstInUse:      0,
+		},
+		{
+			availableColors: []int{1, 2, 3, 4, 5, 6, 7},
+			oldColors:       []int{6, 0, 3, 5, 3, 4, 2, 7},
+			firstAvailable:  -1,
+			firstInUse:      0,
+		},
+	}
+	for _, testcase := range testcases {
+		parser := &Parser{}
+		parser.Reset()
+		parser.availableColors = append([]int{}, testcase.availableColors...)
+		parser.oldColors = append(parser.oldColors, testcase.oldColors...)
+		parser.firstAvailable = testcase.firstAvailable
+		parser.firstInUse = testcase.firstInUse
+		parser.releaseUnusedColors()
+
+		if parser.firstAvailable == -1 {
+			// All in use
+			for _, color := range parser.availableColors {
+				found := false
+				for _, oldColor := range parser.oldColors {
+					if oldColor == color {
+						found = true
+						break
+					}
+				}
+				if !found {
+					t.Errorf("In testcase:\n%d\t%d\t%d %d =>\n%d\t%d\t%d %d: %d should be available but is not",
+						testcase.availableColors,
+						testcase.oldColors,
+						testcase.firstAvailable,
+						testcase.firstInUse,
+						parser.availableColors,
+						parser.oldColors,
+						parser.firstAvailable,
+						parser.firstInUse,
+						color)
+				}
+			}
+		} else if parser.firstInUse != -1 {
+			// Some in use
+			for i := parser.firstInUse; i != parser.firstAvailable; i = (i + 1) % len(parser.availableColors) {
+				color := parser.availableColors[i]
+				found := false
+				for _, oldColor := range parser.oldColors {
+					if oldColor == color {
+						found = true
+						break
+					}
+				}
+				if !found {
+					t.Errorf("In testcase:\n%d\t%d\t%d %d =>\n%d\t%d\t%d %d: %d should be available but is not",
+						testcase.availableColors,
+						testcase.oldColors,
+						testcase.firstAvailable,
+						testcase.firstInUse,
+						parser.availableColors,
+						parser.oldColors,
+						parser.firstAvailable,
+						parser.firstInUse,
+						color)
+				}
+			}
+			for i := parser.firstAvailable; i != parser.firstInUse; i = (i + 1) % len(parser.availableColors) {
+				color := parser.availableColors[i]
+				found := false
+				for _, oldColor := range parser.oldColors {
+					if oldColor == color {
+						found = true
+						break
+					}
+				}
+				if found {
+					t.Errorf("In testcase:\n%d\t%d\t%d %d =>\n%d\t%d\t%d %d: %d should not be available but is",
+						testcase.availableColors,
+						testcase.oldColors,
+						testcase.firstAvailable,
+						testcase.firstInUse,
+						parser.availableColors,
+						parser.oldColors,
+						parser.firstAvailable,
+						parser.firstInUse,
+						color)
+				}
+			}
+		} else {
+			// None in use
+			for _, color := range parser.oldColors {
+				if color != 0 {
+					t.Errorf("In testcase:\n%d\t%d\t%d %d =>\n%d\t%d\t%d %d: %d should not be available but is",
+						testcase.availableColors,
+						testcase.oldColors,
+						testcase.firstAvailable,
+						testcase.firstInUse,
+						parser.availableColors,
+						parser.oldColors,
+						parser.firstAvailable,
+						parser.firstInUse,
+						color)
+				}
+			}
+		}
+	}
+}
+
+func TestParseGlyphs(t *testing.T) {
+	parser := &Parser{}
+	parser.Reset()
+	tgBytes := []byte(testglyphs)
+	tg := tgBytes
+	idx := bytes.Index(tg, []byte("\n"))
+	row := 0
+	for idx > 0 {
+		parser.ParseGlyphs(tg[:idx])
+		tg = tg[idx+1:]
+		idx = bytes.Index(tg, []byte("\n"))
+		if parser.flows[0] != 1 {
+			t.Errorf("First column flow should be 1 but was %d", parser.flows[0])
+		}
+		colorToFlow := map[int]int64{}
+		flowToColor := map[int64]int{}
+
+		for i, flow := range parser.flows {
+			if flow == 0 {
+				continue
+			}
+			color := parser.colors[i]
+
+			if fColor, in := flowToColor[flow]; in && fColor != color {
+				t.Errorf("Row %d column %d flow %d has color %d but should be %d", row, i, flow, color, fColor)
+			}
+			flowToColor[flow] = color
+			if cFlow, in := colorToFlow[color]; in && cFlow != flow {
+				t.Errorf("Row %d column %d flow %d has color %d but conflicts with flow %d", row, i, flow, color, cFlow)
+			}
+			colorToFlow[color] = flow
+		}
+		row++
+	}
+	if len(parser.availableColors) != 9 {
+		t.Errorf("Expected 9 colors but have %d", len(parser.availableColors))
+	}
+}
+
 func TestCommitStringParsing(t *testing.T) {
-	dataFirstPart := "* DATA:||4e61bacab44e9b4730e44a6615d04098dd3a8eaf|2016-12-20 21:10:41 +0100|Author|user@mail.something|4e61bac|"
+	dataFirstPart := "* DATA:|4e61bacab44e9b4730e44a6615d04098dd3a8eaf|2016-12-20 21:10:41 +0100|Author|user@mail.something|4e61bac|"
 	tests := []struct {
 		shouldPass    bool
 		testName      string
@@ -62,15 +259,460 @@ func TestCommitStringParsing(t *testing.T) {
 
 		t.Run(test.testName, func(t *testing.T) {
 			testString := fmt.Sprintf("%s%s", dataFirstPart, test.commitMessage)
-			graphItem, err := graphItemFromString(testString, nil)
+			idx := strings.Index(testString, "DATA:")
+			commit, err := NewCommit(0, 0, []byte(testString[idx+5:]))
 			if err != nil && test.shouldPass {
 				t.Errorf("Could not parse %s", testString)
 				return
 			}
 
-			if test.commitMessage != graphItem.Subject {
-				t.Errorf("%s does not match %s", test.commitMessage, graphItem.Subject)
+			if test.commitMessage != commit.Subject {
+				t.Errorf("%s does not match %s", test.commitMessage, commit.Subject)
 			}
 		})
 	}
 }
+
+var testglyphs = `* 
+* 
+* 
+* 
+* 
+* 
+* 
+*   
+|\  
+* | 
+* | 
+* | 
+* | 
+* | 
+| * 
+* | 
+| *   
+| |\  
+* | | 
+| | *   
+| | |\  
+* | | \   
+|\ \ \ \  
+| * | | | 
+| |\| | | 
+* | | | | 
+|/ / / /  
+| | | * 
+| * | | 
+| * | | 
+| * | | 
+* | | | 
+* | | | 
+* | | | 
+* | | | 
+* | | |   
+|\ \ \ \  
+| | * | | 
+| | |\| | 
+| | | * | 
+| | | | * 
+* | | | | 
+* | | | | 
+* | | | | 
+* | | | | 
+* | | | |   
+|\ \ \ \ \  
+| * | | | | 
+|/| | | | | 
+| | |/ / /  
+| |/| | |   
+| | | | * 
+| * | | | 
+|/| | | | 
+| * | | | 
+|/| | | | 
+| | |/ /  
+| |/| |   
+| * | | 
+| * | |   
+| |\ \ \  
+| | * | | 
+| |/| | | 
+| | | |/  
+| | |/|   
+| * | | 
+| * | | 
+| * | | 
+| | * |   
+| | |\ \  
+| | | * | 
+| | |/| | 
+| | | * |   
+| | | |\ \  
+| | | | * | 
+| | | |/| | 
+| | * | | | 
+| | * | | |   
+| | |\ \ \ \  
+| | | * | | | 
+| | |/| | | | 
+| | | | | * | 
+| | | | |/ /  
+* | | | / / 
+|/ / / / /  
+* | | | |   
+|\ \ \ \ \  
+| * | | | | 
+|/| | | | | 
+| * | | | | 
+| * | | | |   
+| |\ \ \ \ \  
+| | | * \ \ \   
+| | | |\ \ \ \  
+| | | | * | | | 
+| | | |/| | | | 
+| | | | | |/ /  
+| | | | |/| |   
+* | | | | | | 
+* | | | | | | 
+* | | | | | | 
+| | | | * | | 
+* | | | | | | 
+| | * | | | | 
+| |/| | | | | 
+* | | | | | | 
+| |/ / / / /  
+|/| | | | |   
+| | | | * | 
+| | | |/ /  
+| | |/| |   
+| * | | | 
+| | | | * 
+| | * | |   
+| | |\ \ \  
+| | | * | | 
+| | |/| | | 
+| | | |/ /  
+| | | * | 
+| | * | |   
+| | |\ \ \  
+| | | * | | 
+| | |/| | | 
+| | | |/ /  
+| | | * | 
+* | | | |   
+|\ \ \ \ \  
+| * \ \ \ \   
+| |\ \ \ \ \  
+| | | |/ / /  
+| | |/| | |   
+| | | | * | 
+| | | | * | 
+* | | | | | 
+* | | | | | 
+|/ / / / /  
+| | | * | 
+* | | | | 
+* | | | | 
+* | | | | 
+* | | | |   
+|\ \ \ \ \  
+| * | | | | 
+|/| | | | | 
+| | * | | |   
+| | |\ \ \ \  
+| | | * | | | 
+| | |/| | | | 
+| |/| | |/ /  
+| | | |/| |   
+| | | | | * 
+| |_|_|_|/  
+|/| | | |   
+| | * | | 
+| |/ / /  
+* | | | 
+* | | | 
+| | * | 
+* | | | 
+* | | | 
+| * | | 
+| | * | 
+| * | | 
+* | | |   
+|\ \ \ \  
+| * | | | 
+|/| | | | 
+| |/ / /  
+| * | |   
+| |\ \ \  
+| | * | | 
+| |/| | | 
+| | |/ /  
+| | * |   
+| | |\ \  
+| | | * | 
+| | |/| | 
+* | | | | 
+* | | | |   
+|\ \ \ \ \  
+| * | | | | 
+|/| | | | | 
+| | * | | | 
+| | * | | | 
+| | * | | | 
+| |/ / / /  
+| * | | |   
+| |\ \ \ \  
+| | * | | | 
+| |/| | | | 
+* | | | | | 
+* | | | | | 
+* | | | | | 
+* | | | | | 
+* | | | | | 
+| | | | * | 
+* | | | | |   
+|\ \ \ \ \ \  
+| * | | | | | 
+|/| | | | | | 
+| | | | | * | 
+| | | | |/ /  
+* | | | | |   
+|\ \ \ \ \ \  
+* | | | | | | 
+* | | | | | | 
+| | | | * | | 
+* | | | | | | 
+* | | | | | |   
+|\ \ \ \ \ \ \  
+| | |_|_|/ / /  
+| |/| | | | |   
+| | | | * | | 
+| | | | * | | 
+| | | | * | | 
+| | | | * | | 
+| | | | * | | 
+| | | | * | | 
+| | | |/ / /  
+| | | * | | 
+| | | * | | 
+| | | * | | 
+| | |/| | | 
+| | | * | | 
+| | |/| | | 
+| | | |/ /  
+| | * | | 
+| |/| | | 
+| | | * | 
+| | |/ /  
+| | * | 
+| * | |   
+| |\ \ \  
+| * | | | 
+| | * | | 
+| |/| | | 
+| | |/ /  
+| | * |   
+| | |\ \  
+| | * | | 
+* | | | | 
+|\| | | | 
+| * | | | 
+| * | | | 
+| * | | | 
+| | * | | 
+| * | | | 
+| |\| | | 
+| * | | | 
+| | * | | 
+| | * | | 
+| * | | | 
+| * | | | 
+| * | | | 
+| * | | | 
+| * | | | 
+| * | | | 
+| * | | | 
+| * | | | 
+| | * | | 
+| * | | | 
+| * | | | 
+| * | | | 
+| * | | | 
+| | * | | 
+* | | | | 
+|\| | | | 
+| | * | | 
+| * | | | 
+| |\| | | 
+| | * | | 
+| | * | | 
+| | * | | 
+| | | * | 
+* | | | | 
+|\| | | | 
+| | * | | 
+| | |/ /  
+| * | | 
+| * | | 
+| |\| | 
+* | | | 
+|\| | | 
+| | * | 
+| | * | 
+| | * | 
+| * | | 
+| | * | 
+| * | | 
+| | * | 
+| | * | 
+| | * | 
+| * | | 
+| * | | 
+| * | | 
+| * | | 
+| * | | 
+| * | | 
+| * | | 
+* | | | 
+|\| | | 
+| * | | 
+| |\| | 
+| | * |   
+| | |\ \  
+* | | | | 
+|\| | | | 
+| * | | | 
+| |\| | | 
+| | * | | 
+| | | * | 
+| | |/ /  
+* | | | 
+* | | | 
+|\| | | 
+| * | | 
+| |\| | 
+| | * | 
+| | * | 
+| | * | 
+| | | * 
+* | | | 
+|\| | | 
+| * | | 
+| * | | 
+| | | *   
+| | | |\  
+* | | | | 
+| |_|_|/  
+|/| | |   
+| * | | 
+| |\| | 
+| | * | 
+| | * | 
+| | * | 
+| | * | 
+| | * | 
+| * | | 
+* | | | 
+|\| | | 
+| * | | 
+|/| | | 
+| |/ /  
+| * |   
+| |\ \  
+| * | | 
+| * | | 
+* | | | 
+|\| | | 
+| | * | 
+| * | | 
+| * | | 
+| * | | 
+* | | | 
+|\| | | 
+| * | | 
+| * | | 
+| | * |   
+| | |\ \  
+| | |/ /  
+| |/| |   
+| * | | 
+* | | | 
+|\| | | 
+| * | | 
+* | | | 
+|\| | | 
+| * | |   
+| |\ \ \  
+| * | | | 
+| * | | | 
+| | | * | 
+| * | | | 
+| * | | | 
+| | |/ /  
+| |/| |   
+| | * | 
+* | | | 
+|\| | | 
+| * | | 
+| * | | 
+| * | | 
+| * | | 
+| * | |   
+| |\ \ \  
+* | | | | 
+|\| | | | 
+| * | | | 
+| * | | | 
+* | | | | 
+* | | | | 
+|\| | | | 
+| | | | *   
+| | | | |\  
+| |_|_|_|/  
+|/| | | |   
+| * | | | 
+* | | | | 
+* | | | | 
+|\| | | | 
+| * | | |   
+| |\ \ \ \  
+| | | |/ /  
+| | |/| |   
+| * | | | 
+| * | | | 
+| * | | | 
+| * | | | 
+| | * | | 
+| | | * | 
+| | |/ /  
+| |/| |   
+* | | | 
+|\| | | 
+| * | | 
+| * | | 
+| * | | 
+| * | | 
+| * | | 
+* | | | 
+|\| | | 
+| * | | 
+| * | | 
+* | | | 
+| * | | 
+| * | | 
+| * | | 
+* | | | 
+* | | | 
+* | | | 
+|\| | | 
+| * | | 
+* | | | 
+* | | | 
+* | | | 
+* | | | 
+| | | * 
+* | | | 
+|\| | | 
+| * | | 
+| * | | 
+| * | | 
+`