Adding upstream version 9.0.3.

Signed-off-by: Daniel Baumann <daniel@debian.org>

4 files changed, 1422 insertions, 0 deletions

diff --git a/modules/gitgraph/graph.go b/modules/gitgraph/graph.go
new file mode 100644
index 0000000..331ad6b
--- /dev/null
+++ b/modules/gitgraph/graph.go
@@ -0,0 +1,116 @@
+// Copyright 2016 The Gitea Authors. All rights reserved.
+// SPDX-License-Identifier: MIT
+
+package gitgraph
+
+import (
+	"bufio"
+	"bytes"
+	"context"
+	"os"
+	"strings"
+
+	"code.gitea.io/gitea/modules/git"
+	"code.gitea.io/gitea/modules/setting"
+)
+
+// GetCommitGraph return a list of commit (GraphItems) from all branches
+func GetCommitGraph(r *git.Repository, page, maxAllowedColors int, hidePRRefs bool, branches, files []string) (*Graph, error) {
+	format := "DATA:%D|%H|%ad|%h|%s"
+
+	if page == 0 {
+		page = 1
+	}
+
+	graphCmd := git.NewCommand(r.Ctx, "log", "--graph", "--date-order", "--decorate=full")
+
+	if hidePRRefs {
+		graphCmd.AddArguments("--exclude=" + git.PullPrefix + "*")
+	}
+
+	if len(branches) == 0 {
+		graphCmd.AddArguments("--all")
+	}
+
+	graphCmd.AddArguments("-C", "-M", "--date=iso").
+		AddOptionFormat("-n %d", setting.UI.GraphMaxCommitNum*page).
+		AddOptionFormat("--pretty=format:%s", format)
+
+	if len(branches) > 0 {
+		graphCmd.AddDynamicArguments(branches...)
+	}
+	if len(files) > 0 {
+		graphCmd.AddDashesAndList(files...)
+	}
+	graph := NewGraph()
+
+	stderr := new(strings.Builder)
+	stdoutReader, stdoutWriter, err := os.Pipe()
+	if err != nil {
+		return nil, err
+	}
+	commitsToSkip := setting.UI.GraphMaxCommitNum * (page - 1)
+
+	scanner := bufio.NewScanner(stdoutReader)
+
+	if err := graphCmd.Run(&git.RunOpts{
+		Dir:    r.Path,
+		Stdout: stdoutWriter,
+		Stderr: stderr,
+		PipelineFunc: func(ctx context.Context, cancel context.CancelFunc) error {
+			_ = stdoutWriter.Close()
+			defer stdoutReader.Close()
+			parser := &Parser{}
+			parser.firstInUse = -1
+			parser.maxAllowedColors = maxAllowedColors
+			if maxAllowedColors > 0 {
+				parser.availableColors = make([]int, maxAllowedColors)
+				for i := range parser.availableColors {
+					parser.availableColors[i] = i + 1
+				}
+			} else {
+				parser.availableColors = []int{1, 2}
+			}
+			for commitsToSkip > 0 && scanner.Scan() {
+				line := scanner.Bytes()
+				dataIdx := bytes.Index(line, []byte("DATA:"))
+				if dataIdx < 0 {
+					dataIdx = len(line)
+				}
+				starIdx := bytes.IndexByte(line, '*')
+				if starIdx >= 0 && starIdx < dataIdx {
+					commitsToSkip--
+				}
+				parser.ParseGlyphs(line[:dataIdx])
+			}
+
+			row := 0
+
+			// Skip initial non-commit lines
+			for scanner.Scan() {
+				line := scanner.Bytes()
+				if bytes.IndexByte(line, '*') >= 0 {
+					if err := parser.AddLineToGraph(graph, row, line); err != nil {
+						cancel()
+						return err
+					}
+					break
+				}
+				parser.ParseGlyphs(line)
+			}
+
+			for scanner.Scan() {
+				row++
+				line := scanner.Bytes()
+				if err := parser.AddLineToGraph(graph, row, line); err != nil {
+					cancel()
+					return err
+				}
+			}
+			return scanner.Err()
+		},
+	}); err != nil {
+		return graph, err
+	}
+	return graph, nil
+}
diff --git a/modules/gitgraph/graph_models.go b/modules/gitgraph/graph_models.go
new file mode 100644
index 0000000..82f460e
--- /dev/null
+++ b/modules/gitgraph/graph_models.go
@@ -0,0 +1,256 @@
+// Copyright 2020 The Gitea Authors. All rights reserved.
+// SPDX-License-Identifier: MIT
+
+package gitgraph
+
+import (
+	"bytes"
+	"context"
+	"fmt"
+	"strings"
+
+	asymkey_model "code.gitea.io/gitea/models/asymkey"
+	"code.gitea.io/gitea/models/db"
+	git_model "code.gitea.io/gitea/models/git"
+	repo_model "code.gitea.io/gitea/models/repo"
+	user_model "code.gitea.io/gitea/models/user"
+	"code.gitea.io/gitea/modules/git"
+	"code.gitea.io/gitea/modules/log"
+)
+
+// NewGraph creates a basic graph
+func NewGraph() *Graph {
+	graph := &Graph{}
+	graph.relationCommit = &Commit{
+		Row:    -1,
+		Column: -1,
+	}
+	graph.Flows = map[int64]*Flow{}
+	return graph
+}
+
+// Graph represents a collection of flows
+type Graph struct {
+	Flows          map[int64]*Flow
+	Commits        []*Commit
+	MinRow         int
+	MinColumn      int
+	MaxRow         int
+	MaxColumn      int
+	relationCommit *Commit
+}
+
+// Width returns the width of the graph
+func (graph *Graph) Width() int {
+	return graph.MaxColumn - graph.MinColumn + 1
+}
+
+// Height returns the height of the graph
+func (graph *Graph) Height() int {
+	return graph.MaxRow - graph.MinRow + 1
+}
+
+// AddGlyph adds glyph to flows
+func (graph *Graph) AddGlyph(row, column int, flowID int64, color int, glyph byte) {
+	flow, ok := graph.Flows[flowID]
+	if !ok {
+		flow = NewFlow(flowID, color, row, column)
+		graph.Flows[flowID] = flow
+	}
+	flow.AddGlyph(row, column, glyph)
+
+	if row < graph.MinRow {
+		graph.MinRow = row
+	}
+	if row > graph.MaxRow {
+		graph.MaxRow = row
+	}
+	if column < graph.MinColumn {
+		graph.MinColumn = column
+	}
+	if column > graph.MaxColumn {
+		graph.MaxColumn = column
+	}
+}
+
+// AddCommit adds a commit at row, column on flowID with the provided data
+func (graph *Graph) AddCommit(row, column int, flowID int64, data []byte) error {
+	commit, err := NewCommit(row, column, data)
+	if err != nil {
+		return err
+	}
+	commit.Flow = flowID
+	graph.Commits = append(graph.Commits, commit)
+
+	graph.Flows[flowID].Commits = append(graph.Flows[flowID].Commits, commit)
+	return nil
+}
+
+// LoadAndProcessCommits will load the git.Commits for each commit in the graph,
+// the associate the commit with the user author, and check the commit verification
+// before finally retrieving the latest status
+func (graph *Graph) LoadAndProcessCommits(ctx context.Context, repository *repo_model.Repository, gitRepo *git.Repository) error {
+	var err error
+	var ok bool
+
+	emails := map[string]*user_model.User{}
+	keyMap := map[string]bool{}
+
+	for _, c := range graph.Commits {
+		if len(c.Rev) == 0 {
+			continue
+		}
+		c.Commit, err = gitRepo.GetCommit(c.Rev)
+		if err != nil {
+			return fmt.Errorf("GetCommit: %s Error: %w", c.Rev, err)
+		}
+
+		if c.Commit.Author != nil {
+			email := c.Commit.Author.Email
+			if c.User, ok = emails[email]; !ok {
+				c.User, _ = user_model.GetUserByEmail(ctx, email)
+				emails[email] = c.User
+			}
+		}
+
+		c.Verification = asymkey_model.ParseCommitWithSignature(ctx, c.Commit)
+
+		_ = asymkey_model.CalculateTrustStatus(c.Verification, repository.GetTrustModel(), func(user *user_model.User) (bool, error) {
+			return repo_model.IsOwnerMemberCollaborator(ctx, repository, user.ID)
+		}, &keyMap)
+
+		statuses, _, err := git_model.GetLatestCommitStatus(ctx, repository.ID, c.Commit.ID.String(), db.ListOptions{})
+		if err != nil {
+			log.Error("GetLatestCommitStatus: %v", err)
+		} else {
+			c.Status = git_model.CalcCommitStatus(statuses)
+		}
+	}
+	return nil
+}
+
+// NewFlow creates a new flow
+func NewFlow(flowID int64, color, row, column int) *Flow {
+	return &Flow{
+		ID:          flowID,
+		ColorNumber: color,
+		MinRow:      row,
+		MinColumn:   column,
+		MaxRow:      row,
+		MaxColumn:   column,
+	}
+}
+
+// Flow represents a series of glyphs
+type Flow struct {
+	ID          int64
+	ColorNumber int
+	Glyphs      []Glyph
+	Commits     []*Commit
+	MinRow      int
+	MinColumn   int
+	MaxRow      int
+	MaxColumn   int
+}
+
+// Color16 wraps the color numbers around mod 16
+func (flow *Flow) Color16() int {
+	return flow.ColorNumber % 16
+}
+
+// AddGlyph adds glyph at row and column
+func (flow *Flow) AddGlyph(row, column int, glyph byte) {
+	if row < flow.MinRow {
+		flow.MinRow = row
+	}
+	if row > flow.MaxRow {
+		flow.MaxRow = row
+	}
+	if column < flow.MinColumn {
+		flow.MinColumn = column
+	}
+	if column > flow.MaxColumn {
+		flow.MaxColumn = column
+	}
+
+	flow.Glyphs = append(flow.Glyphs, Glyph{
+		row,
+		column,
+		glyph,
+	})
+}
+
+// Glyph represents a coordinate and glyph
+type Glyph struct {
+	Row    int
+	Column int
+	Glyph  byte
+}
+
+// RelationCommit represents an empty relation commit
+var RelationCommit = &Commit{
+	Row: -1,
+}
+
+// NewCommit creates a new commit from a provided line
+func NewCommit(row, column int, line []byte) (*Commit, error) {
+	data := bytes.SplitN(line, []byte("|"), 5)
+	if len(data) < 5 {
+		return nil, fmt.Errorf("malformed data section on line %d with commit: %s", row, string(line))
+	}
+	return &Commit{
+		Row:    row,
+		Column: column,
+		// 0 matches git log --pretty=format:%d => ref names, like the --decorate option of git-log(1)
+		Refs: newRefsFromRefNames(data[0]),
+		// 1 matches git log --pretty=format:%H => commit hash
+		Rev: string(data[1]),
+		// 2 matches git log --pretty=format:%ad => author date (format respects --date= option)
+		Date: string(data[2]),
+		// 3 matches git log --pretty=format:%h => abbreviated commit hash
+		ShortRev: string(data[3]),
+		// 4 matches git log --pretty=format:%s => subject
+		Subject: string(data[4]),
+	}, nil
+}
+
+func newRefsFromRefNames(refNames []byte) []git.Reference {
+	refBytes := bytes.Split(refNames, []byte{',', ' '})
+	refs := make([]git.Reference, 0, len(refBytes))
+	for _, refNameBytes := range refBytes {
+		if len(refNameBytes) == 0 {
+			continue
+		}
+		refName := string(refNameBytes)
+		if strings.HasPrefix(refName, "tag: ") {
+			refName = strings.TrimPrefix(refName, "tag: ")
+		} else {
+			refName = strings.TrimPrefix(refName, "HEAD -> ")
+		}
+		refs = append(refs, git.Reference{
+			Name: refName,
+		})
+	}
+	return refs
+}
+
+// Commit represents a commit at coordinate X, Y with the data
+type Commit struct {
+	Commit       *git.Commit
+	User         *user_model.User
+	Verification *asymkey_model.ObjectVerification
+	Status       *git_model.CommitStatus
+	Flow         int64
+	Row          int
+	Column       int
+	Refs         []git.Reference
+	Rev          string
+	Date         string
+	ShortRev     string
+	Subject      string
+}
+
+// OnlyRelation returns whether this a relation only commit
+func (c *Commit) OnlyRelation() bool {
+	return c.Row == -1
+}
diff --git a/modules/gitgraph/graph_test.go b/modules/gitgraph/graph_test.go
new file mode 100644
index 0000000..18d427a
--- /dev/null
+++ b/modules/gitgraph/graph_test.go
@@ -0,0 +1,714 @@
+// Copyright 2016 The Gitea Authors. All rights reserved.
+// SPDX-License-Identifier: MIT
+
+package gitgraph
+
+import (
+	"bytes"
+	"fmt"
+	"strings"
+	"testing"
+
+	"code.gitea.io/gitea/modules/git"
+)
+
+func BenchmarkGetCommitGraph(b *testing.B) {
+	currentRepo, err := git.OpenRepository(git.DefaultContext, ".")
+	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, 0, false, nil, nil)
+		if err != nil {
+			b.Error("Could get commit graph")
+		}
+
+		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|4e61bac|Add route for graph"
+
+	parser := &Parser{}
+	parser.Reset()
+	for i := 0; i < b.N; i++ {
+		parser.Reset()
+		graph := NewGraph()
+		if err := parser.AddLineToGraph(graph, 0, []byte(testString)); err != nil {
+			b.Error("could not parse teststring")
+		}
+		if graph.Flows[1].Commits[0].Rev != "4e61bacab44e9b4730e44a6615d04098dd3a8eaf" {
+			b.Error("Did not get expected data")
+		}
+	}
+}
+
+func BenchmarkParseGlyphs(b *testing.B) {
+	parser := &Parser{}
+	parser.Reset()
+	tgBytes := []byte(testglyphs)
+	var tg []byte
+	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|4e61bac|"
+	tests := []struct {
+		shouldPass    bool
+		testName      string
+		commitMessage string
+	}{
+		{true, "normal", "not a fancy message"},
+		{true, "extra pipe", "An extra pipe: |"},
+		{true, "extra 'Data:'", "DATA: might be trouble"},
+	}
+
+	for _, test := range tests {
+		t.Run(test.testName, func(t *testing.T) {
+			testString := fmt.Sprintf("%s%s", dataFirstPart, test.commitMessage)
+			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 != commit.Subject {
+				t.Errorf("%s does not match %s", test.commitMessage, commit.Subject)
+			}
+		})
+	}
+}
+
+var testglyphs = `* 
+* 
+* 
+* 
+* 
+* 
+* 
+*   
+|\  
+* | 
+* | 
+* | 
+* | 
+* | 
+| * 
+* | 
+| *   
+| |\  
+* | | 
+| | *   
+| | |\  
+* | | \   
+|\ \ \ \  
+| * | | | 
+| |\| | | 
+* | | | | 
+|/ / / /  
+| | | * 
+| * | | 
+| * | | 
+| * | | 
+* | | | 
+* | | | 
+* | | | 
+* | | | 
+* | | |   
+|\ \ \ \  
+| | * | | 
+| | |\| | 
+| | | * | 
+| | | | * 
+* | | | | 
+* | | | | 
+* | | | | 
+* | | | | 
+* | | | |   
+|\ \ \ \ \  
+| * | | | | 
+|/| | | | | 
+| | |/ / /  
+| |/| | |   
+| | | | * 
+| * | | | 
+|/| | | | 
+| * | | | 
+|/| | | | 
+| | |/ /  
+| |/| |   
+| * | | 
+| * | |   
+| |\ \ \  
+| | * | | 
+| |/| | | 
+| | | |/  
+| | |/|   
+| * | | 
+| * | | 
+| * | | 
+| | * |   
+| | |\ \  
+| | | * | 
+| | |/| | 
+| | | * |   
+| | | |\ \  
+| | | | * | 
+| | | |/| | 
+| | * | | | 
+| | * | | |   
+| | |\ \ \ \  
+| | | * | | | 
+| | |/| | | | 
+| | | | | * | 
+| | | | |/ /  
+* | | | / / 
+|/ / / / /  
+* | | | |   
+|\ \ \ \ \  
+| * | | | | 
+|/| | | | | 
+| * | | | | 
+| * | | | |   
+| |\ \ \ \ \  
+| | | * \ \ \   
+| | | |\ \ \ \  
+| | | | * | | | 
+| | | |/| | | | 
+| | | | | |/ /  
+| | | | |/| |   
+* | | | | | | 
+* | | | | | | 
+* | | | | | | 
+| | | | * | | 
+* | | | | | | 
+| | * | | | | 
+| |/| | | | | 
+* | | | | | | 
+| |/ / / / /  
+|/| | | | |   
+| | | | * | 
+| | | |/ /  
+| | |/| |   
+| * | | | 
+| | | | * 
+| | * | |   
+| | |\ \ \  
+| | | * | | 
+| | |/| | | 
+| | | |/ /  
+| | | * | 
+| | * | |   
+| | |\ \ \  
+| | | * | | 
+| | |/| | | 
+| | | |/ /  
+| | | * | 
+* | | | |   
+|\ \ \ \ \  
+| * \ \ \ \   
+| |\ \ \ \ \  
+| | | |/ / /  
+| | |/| | |   
+| | | | * | 
+| | | | * | 
+* | | | | | 
+* | | | | | 
+|/ / / / /  
+| | | * | 
+* | | | | 
+* | | | | 
+* | | | | 
+* | | | |   
+|\ \ \ \ \  
+| * | | | | 
+|/| | | | | 
+| | * | | |   
+| | |\ \ \ \  
+| | | * | | | 
+| | |/| | | | 
+| |/| | |/ /  
+| | | |/| |   
+| | | | | * 
+| |_|_|_|/  
+|/| | | |   
+| | * | | 
+| |/ / /  
+* | | | 
+* | | | 
+| | * | 
+* | | | 
+* | | | 
+| * | | 
+| | * | 
+| * | | 
+* | | |   
+|\ \ \ \  
+| * | | | 
+|/| | | | 
+| |/ / /  
+| * | |   
+| |\ \ \  
+| | * | | 
+| |/| | | 
+| | |/ /  
+| | * |   
+| | |\ \  
+| | | * | 
+| | |/| | 
+* | | | | 
+* | | | |   
+|\ \ \ \ \  
+| * | | | | 
+|/| | | | | 
+| | * | | | 
+| | * | | | 
+| | * | | | 
+| |/ / / /  
+| * | | |   
+| |\ \ \ \  
+| | * | | | 
+| |/| | | | 
+* | | | | | 
+* | | | | | 
+* | | | | | 
+* | | | | | 
+* | | | | | 
+| | | | * | 
+* | | | | |   
+|\ \ \ \ \ \  
+| * | | | | | 
+|/| | | | | | 
+| | | | | * | 
+| | | | |/ /  
+* | | | | |   
+|\ \ \ \ \ \  
+* | | | | | | 
+* | | | | | | 
+| | | | * | | 
+* | | | | | | 
+* | | | | | |   
+|\ \ \ \ \ \ \  
+| | |_|_|/ / /  
+| |/| | | | |   
+| | | | * | | 
+| | | | * | | 
+| | | | * | | 
+| | | | * | | 
+| | | | * | | 
+| | | | * | | 
+| | | |/ / /  
+| | | * | | 
+| | | * | | 
+| | | * | | 
+| | |/| | | 
+| | | * | | 
+| | |/| | | 
+| | | |/ /  
+| | * | | 
+| |/| | | 
+| | | * | 
+| | |/ /  
+| | * | 
+| * | |   
+| |\ \ \  
+| * | | | 
+| | * | | 
+| |/| | | 
+| | |/ /  
+| | * |   
+| | |\ \  
+| | * | | 
+* | | | | 
+|\| | | | 
+| * | | | 
+| * | | | 
+| * | | | 
+| | * | | 
+| * | | | 
+| |\| | | 
+| * | | | 
+| | * | | 
+| | * | | 
+| * | | | 
+| * | | | 
+| * | | | 
+| * | | | 
+| * | | | 
+| * | | | 
+| * | | | 
+| * | | | 
+| | * | | 
+| * | | | 
+| * | | | 
+| * | | | 
+| * | | | 
+| | * | | 
+* | | | | 
+|\| | | | 
+| | * | | 
+| * | | | 
+| |\| | | 
+| | * | | 
+| | * | | 
+| | * | | 
+| | | * | 
+* | | | | 
+|\| | | | 
+| | * | | 
+| | |/ /  
+| * | | 
+| * | | 
+| |\| | 
+* | | | 
+|\| | | 
+| | * | 
+| | * | 
+| | * | 
+| * | | 
+| | * | 
+| * | | 
+| | * | 
+| | * | 
+| | * | 
+| * | | 
+| * | | 
+| * | | 
+| * | | 
+| * | | 
+| * | | 
+| * | | 
+* | | | 
+|\| | | 
+| * | | 
+| |\| | 
+| | * |   
+| | |\ \  
+* | | | | 
+|\| | | | 
+| * | | | 
+| |\| | | 
+| | * | | 
+| | | * | 
+| | |/ /  
+* | | | 
+* | | | 
+|\| | | 
+| * | | 
+| |\| | 
+| | * | 
+| | * | 
+| | * | 
+| | | * 
+* | | | 
+|\| | | 
+| * | | 
+| * | | 
+| | | *   
+| | | |\  
+* | | | | 
+| |_|_|/  
+|/| | |   
+| * | | 
+| |\| | 
+| | * | 
+| | * | 
+| | * | 
+| | * | 
+| | * | 
+| * | | 
+* | | | 
+|\| | | 
+| * | | 
+|/| | | 
+| |/ /  
+| * |   
+| |\ \  
+| * | | 
+| * | | 
+* | | | 
+|\| | | 
+| | * | 
+| * | | 
+| * | | 
+| * | | 
+* | | | 
+|\| | | 
+| * | | 
+| * | | 
+| | * |   
+| | |\ \  
+| | |/ /  
+| |/| |   
+| * | | 
+* | | | 
+|\| | | 
+| * | | 
+* | | | 
+|\| | | 
+| * | |   
+| |\ \ \  
+| * | | | 
+| * | | | 
+| | | * | 
+| * | | | 
+| * | | | 
+| | |/ /  
+| |/| |   
+| | * | 
+* | | | 
+|\| | | 
+| * | | 
+| * | | 
+| * | | 
+| * | | 
+| * | |   
+| |\ \ \  
+* | | | | 
+|\| | | | 
+| * | | | 
+| * | | | 
+* | | | | 
+* | | | | 
+|\| | | | 
+| | | | *   
+| | | | |\  
+| |_|_|_|/  
+|/| | | |   
+| * | | | 
+* | | | | 
+* | | | | 
+|\| | | | 
+| * | | |   
+| |\ \ \ \  
+| | | |/ /  
+| | |/| |   
+| * | | | 
+| * | | | 
+| * | | | 
+| * | | | 
+| | * | | 
+| | | * | 
+| | |/ /  
+| |/| |   
+* | | | 
+|\| | | 
+| * | | 
+| * | | 
+| * | | 
+| * | | 
+| * | | 
+* | | | 
+|\| | | 
+| * | | 
+| * | | 
+* | | | 
+| * | | 
+| * | | 
+| * | | 
+* | | | 
+* | | | 
+* | | | 
+|\| | | 
+| * | | 
+* | | | 
+* | | | 
+* | | | 
+* | | | 
+| | | * 
+* | | | 
+|\| | | 
+| * | | 
+| * | | 
+| * | | 
+`
diff --git a/modules/gitgraph/parser.go b/modules/gitgraph/parser.go
new file mode 100644
index 0000000..f6bf9b0
--- /dev/null
+++ b/modules/gitgraph/parser.go
@@ -0,0 +1,336 @@
+// Copyright 2020 The Gitea Authors. All rights reserved.
+// SPDX-License-Identifier: MIT
+
+package gitgraph
+
+import (
+	"bytes"
+	"fmt"
+)
+
+// Parser represents a git graph parser. It is stateful containing the previous
+// glyphs, detected flows and color assignments.
+type Parser struct {
+	glyphs           []byte
+	oldGlyphs        []byte
+	flows            []int64
+	oldFlows         []int64
+	maxFlow          int64
+	colors           []int
+	oldColors        []int
+	availableColors  []int
+	nextAvailable    int
+	firstInUse       int
+	firstAvailable   int
+	maxAllowedColors int
+}
+
+// Reset resets the internal parser state.
+func (parser *Parser) Reset() {
+	parser.glyphs = parser.glyphs[0:0]
+	parser.oldGlyphs = parser.oldGlyphs[0:0]
+	parser.flows = parser.flows[0:0]
+	parser.oldFlows = parser.oldFlows[0:0]
+	parser.maxFlow = 0
+	parser.colors = parser.colors[0:0]
+	parser.oldColors = parser.oldColors[0:0]
+	parser.availableColors = parser.availableColors[0:0]
+	parser.availableColors = append(parser.availableColors, 1, 2)
+	parser.nextAvailable = 0
+	parser.firstInUse = -1
+	parser.firstAvailable = 0
+	parser.maxAllowedColors = 0
+}
+
+// AddLineToGraph adds the line as a row to the graph
+func (parser *Parser) AddLineToGraph(graph *Graph, row int, line []byte) error {
+	idx := bytes.Index(line, []byte("DATA:"))
+	if idx < 0 {
+		parser.ParseGlyphs(line)
+	} else {
+		parser.ParseGlyphs(line[:idx])
+	}
+
+	var err error
+	commitDone := false
+
+	for column, glyph := range parser.glyphs {
+		if glyph == ' ' {
+			continue
+		}
+
+		flowID := parser.flows[column]
+
+		graph.AddGlyph(row, column, flowID, parser.colors[column], glyph)
+
+		if glyph == '*' {
+			if commitDone {
+				if err != nil {
+					err = fmt.Errorf("double commit on line %d: %s. %w", row, string(line), err)
+				} else {
+					err = fmt.Errorf("double commit on line %d: %s", row, string(line))
+				}
+			}
+			commitDone = true
+			if idx < 0 {
+				if err != nil {
+					err = fmt.Errorf("missing data section on line %d with commit: %s. %w", row, string(line), err)
+				} else {
+					err = fmt.Errorf("missing data section on line %d with commit: %s", row, string(line))
+				}
+				continue
+			}
+			err2 := graph.AddCommit(row, column, flowID, line[idx+5:])
+			if err != nil && err2 != nil {
+				err = fmt.Errorf("%v %w", err2, err)
+				continue
+			} else if err2 != nil {
+				err = err2
+				continue
+			}
+		}
+	}
+	if !commitDone {
+		graph.Commits = append(graph.Commits, RelationCommit)
+	}
+	return err
+}
+
+func (parser *Parser) releaseUnusedColors() {
+	if parser.firstInUse > -1 {
+		// Here we step through the old colors, searching for them in the
+		// "in-use" section of availableColors (that is, the colors between
+		// firstInUse and firstAvailable)
+		// Ensure that the benchmarks are not worsened with proposed changes
+		stepstaken := 0
+		position := parser.firstInUse
+		for _, color := range parser.oldColors {
+			if color == 0 {
+				continue
+			}
+			found := false
+			i := position
+			for j := stepstaken; i != parser.firstAvailable && j < len(parser.availableColors); j++ {
+				colorToCheck := parser.availableColors[i]
+				if colorToCheck == color {
+					found = true
+					break
+				}
+				i = (i + 1) % len(parser.availableColors)
+			}
+			if !found {
+				// Duplicate color
+				continue
+			}
+			// Swap them around
+			parser.availableColors[position], parser.availableColors[i] = parser.availableColors[i], parser.availableColors[position]
+			stepstaken++
+			position = (parser.firstInUse + stepstaken) % len(parser.availableColors)
+			if position == parser.firstAvailable || stepstaken == len(parser.availableColors) {
+				break
+			}
+		}
+		if stepstaken == len(parser.availableColors) {
+			parser.firstAvailable = -1
+		} else {
+			parser.firstAvailable = position
+			if parser.nextAvailable == -1 {
+				parser.nextAvailable = parser.firstAvailable
+			}
+		}
+	}
+}
+
+// ParseGlyphs parses the provided glyphs and sets the internal state
+func (parser *Parser) ParseGlyphs(glyphs []byte) {
+	// Clean state for parsing this row
+	parser.glyphs, parser.oldGlyphs = parser.oldGlyphs, parser.glyphs
+	parser.glyphs = parser.glyphs[0:0]
+	parser.flows, parser.oldFlows = parser.oldFlows, parser.flows
+	parser.flows = parser.flows[0:0]
+	parser.colors, parser.oldColors = parser.oldColors, parser.colors
+
+	// Ensure we have enough flows and colors
+	parser.colors = parser.colors[0:0]
+	for range glyphs {
+		parser.flows = append(parser.flows, 0)
+		parser.colors = append(parser.colors, 0)
+	}
+
+	// Copy the provided glyphs in to state.glyphs for safekeeping
+	parser.glyphs = append(parser.glyphs, glyphs...)
+
+	// release unused colors
+	parser.releaseUnusedColors()
+
+	for i := len(glyphs) - 1; i >= 0; i-- {
+		glyph := glyphs[i]
+		switch glyph {
+		case '|':
+			fallthrough
+		case '*':
+			parser.setUpFlow(i)
+		case '/':
+			parser.setOutFlow(i)
+		case '\\':
+			parser.setInFlow(i)
+		case '_':
+			parser.setRightFlow(i)
+		case '.':
+			fallthrough
+		case '-':
+			parser.setLeftFlow(i)
+		case ' ':
+			// no-op
+		default:
+			parser.newFlow(i)
+		}
+	}
+}
+
+func (parser *Parser) takePreviousFlow(i, j int) {
+	if j < len(parser.oldFlows) && parser.oldFlows[j] > 0 {
+		parser.flows[i] = parser.oldFlows[j]
+		parser.oldFlows[j] = 0
+		parser.colors[i] = parser.oldColors[j]
+		parser.oldColors[j] = 0
+	} else {
+		parser.newFlow(i)
+	}
+}
+
+func (parser *Parser) takeCurrentFlow(i, j int) {
+	if j < len(parser.flows) && parser.flows[j] > 0 {
+		parser.flows[i] = parser.flows[j]
+		parser.colors[i] = parser.colors[j]
+	} else {
+		parser.newFlow(i)
+	}
+}
+
+func (parser *Parser) newFlow(i int) {
+	parser.maxFlow++
+	parser.flows[i] = parser.maxFlow
+
+	// Now give this flow a color
+	if parser.nextAvailable == -1 {
+		next := len(parser.availableColors)
+		if parser.maxAllowedColors < 1 || next < parser.maxAllowedColors {
+			parser.nextAvailable = next
+			parser.firstAvailable = next
+			parser.availableColors = append(parser.availableColors, next+1)
+		}
+	}
+	parser.colors[i] = parser.availableColors[parser.nextAvailable]
+	if parser.firstInUse == -1 {
+		parser.firstInUse = parser.nextAvailable
+	}
+	parser.availableColors[parser.firstAvailable], parser.availableColors[parser.nextAvailable] = parser.availableColors[parser.nextAvailable], parser.availableColors[parser.firstAvailable]
+
+	parser.nextAvailable = (parser.nextAvailable + 1) % len(parser.availableColors)
+	parser.firstAvailable = (parser.firstAvailable + 1) % len(parser.availableColors)
+
+	if parser.nextAvailable == parser.firstInUse {
+		parser.nextAvailable = parser.firstAvailable
+	}
+	if parser.nextAvailable == parser.firstInUse {
+		parser.nextAvailable = -1
+		parser.firstAvailable = -1
+	}
+}
+
+// setUpFlow handles '|' or '*'
+func (parser *Parser) setUpFlow(i int) {
+	// In preference order:
+	//
+	// Previous Row: '\? ' ' |' '  /'
+	// Current Row:  ' | ' ' |' ' | '
+	if i > 0 && i-1 < len(parser.oldGlyphs) && parser.oldGlyphs[i-1] == '\\' {
+		parser.takePreviousFlow(i, i-1)
+	} else if i < len(parser.oldGlyphs) && (parser.oldGlyphs[i] == '|' || parser.oldGlyphs[i] == '*') {
+		parser.takePreviousFlow(i, i)
+	} else if i+1 < len(parser.oldGlyphs) && parser.oldGlyphs[i+1] == '/' {
+		parser.takePreviousFlow(i, i+1)
+	} else {
+		parser.newFlow(i)
+	}
+}
+
+// setOutFlow handles '/'
+func (parser *Parser) setOutFlow(i int) {
+	// In preference order:
+	//
+	// Previous Row: ' |/' ' |_' ' |' ' /' ' _' '\'
+	// Current Row:  '/| ' '/| ' '/ ' '/ ' '/ ' '/'
+	if i+2 < len(parser.oldGlyphs) &&
+		(parser.oldGlyphs[i+1] == '|' || parser.oldGlyphs[i+1] == '*') &&
+		(parser.oldGlyphs[i+2] == '/' || parser.oldGlyphs[i+2] == '_') &&
+		i+1 < len(parser.glyphs) &&
+		(parser.glyphs[i+1] == '|' || parser.glyphs[i+1] == '*') {
+		parser.takePreviousFlow(i, i+2)
+	} else if i+1 < len(parser.oldGlyphs) &&
+		(parser.oldGlyphs[i+1] == '|' || parser.oldGlyphs[i+1] == '*' ||
+			parser.oldGlyphs[i+1] == '/' || parser.oldGlyphs[i+1] == '_') {
+		parser.takePreviousFlow(i, i+1)
+		if parser.oldGlyphs[i+1] == '/' {
+			parser.glyphs[i] = '|'
+		}
+	} else if i < len(parser.oldGlyphs) && parser.oldGlyphs[i] == '\\' {
+		parser.takePreviousFlow(i, i)
+	} else {
+		parser.newFlow(i)
+	}
+}
+
+// setInFlow handles '\'
+func (parser *Parser) setInFlow(i int) {
+	// In preference order:
+	//
+	// Previous Row: '| ' '-. ' '| ' '\ ' '/' '---'
+	// Current Row:  '|\' '  \' ' \' ' \' '\' ' \ '
+	if i > 0 && i-1 < len(parser.oldGlyphs) &&
+		(parser.oldGlyphs[i-1] == '|' || parser.oldGlyphs[i-1] == '*') &&
+		(parser.glyphs[i-1] == '|' || parser.glyphs[i-1] == '*') {
+		parser.newFlow(i)
+	} else if i > 0 && i-1 < len(parser.oldGlyphs) &&
+		(parser.oldGlyphs[i-1] == '|' || parser.oldGlyphs[i-1] == '*' ||
+			parser.oldGlyphs[i-1] == '.' || parser.oldGlyphs[i-1] == '\\') {
+		parser.takePreviousFlow(i, i-1)
+		if parser.oldGlyphs[i-1] == '\\' {
+			parser.glyphs[i] = '|'
+		}
+	} else if i < len(parser.oldGlyphs) && parser.oldGlyphs[i] == '/' {
+		parser.takePreviousFlow(i, i)
+	} else {
+		parser.newFlow(i)
+	}
+}
+
+// setRightFlow handles '_'
+func (parser *Parser) setRightFlow(i int) {
+	// In preference order:
+	//
+	// Current Row:  '__' '_/' '_|_' '_|/'
+	if i+1 < len(parser.glyphs) &&
+		(parser.glyphs[i+1] == '_' || parser.glyphs[i+1] == '/') {
+		parser.takeCurrentFlow(i, i+1)
+	} else if i+2 < len(parser.glyphs) &&
+		(parser.glyphs[i+1] == '|' || parser.glyphs[i+1] == '*') &&
+		(parser.glyphs[i+2] == '_' || parser.glyphs[i+2] == '/') {
+		parser.takeCurrentFlow(i, i+2)
+	} else {
+		parser.newFlow(i)
+	}
+}
+
+// setLeftFlow handles '----.'
+func (parser *Parser) setLeftFlow(i int) {
+	if parser.glyphs[i] == '.' {
+		parser.newFlow(i)
+	} else if i+1 < len(parser.glyphs) &&
+		(parser.glyphs[i+1] == '-' || parser.glyphs[i+1] == '.') {
+		parser.takeCurrentFlow(i, i+1)
+	} else {
+		parser.newFlow(i)
+	}
+}