summaryrefslogtreecommitdiffstats
path: root/modules/gitgraph
diff options
context:
space:
mode:
authorzeripath <art27@cantab.net>2020-08-06 09:04:08 +0100
committerGitHub <noreply@github.com>2020-08-06 09:04:08 +0100
commit2c1ae6c82d0b3fa62dda7e6a30fb91e27aba6e04 (patch)
treebe14ac1376125be2482e6ca7de3eedc276203304 /modules/gitgraph
parentf1a42f5d5ee0279ddec7973a1ba9236c70bd5b5e (diff)
downloadgitea-2c1ae6c82d0b3fa62dda7e6a30fb91e27aba6e04.tar.gz
gitea-2c1ae6c82d0b3fa62dda7e6a30fb91e27aba6e04.zip
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>
Diffstat (limited to 'modules/gitgraph')
-rw-r--r--modules/gitgraph/graph.go108
-rw-r--r--modules/gitgraph/graph_models.go186
-rw-r--r--modules/gitgraph/graph_test.go666
-rw-r--r--modules/gitgraph/parser.go338
4 files changed, 1209 insertions, 89 deletions
diff --git a/modules/gitgraph/graph.go b/modules/gitgraph/graph.go
index 4ba110c706..257e4f3af0 100644
--- a/modules/gitgraph/graph.go
+++ b/modules/gitgraph/graph.go
@@ -16,26 +16,9 @@ import (
"code.gitea.io/gitea/modules/setting"
)
-// GraphItem represent one commit, or one relation in timeline
-type GraphItem struct {
- GraphAcii string
- Relation string
- Branch string
- Rev string
- Date string
- Author string
- AuthorEmail string
- ShortRev string
- Subject string
- OnlyRelation bool
-}
-
-// GraphItems is a list of commits from all branches
-type GraphItems []GraphItem
-
// GetCommitGraph return a list of commit (GraphItems) from all branches
-func GetCommitGraph(r *git.Repository, page int) (GraphItems, error) {
- format := "DATA:|%d|%H|%ad|%an|%ae|%h|%s"
+func GetCommitGraph(r *git.Repository, page int, maxAllowedColors int) (*Graph, error) {
+ format := "DATA:%d|%H|%ad|%an|%ae|%h|%s"
if page == 0 {
page = 1
@@ -51,7 +34,8 @@ func GetCommitGraph(r *git.Repository, page int) (GraphItems, error) {
"--date=iso",
fmt.Sprintf("--pretty=format:%s", format),
)
- commitGraph := make([]GraphItem, 0, 100)
+ graph := NewGraph()
+
stderr := new(strings.Builder)
stdoutReader, stdoutWriter, err := os.Pipe()
if err != nil {
@@ -64,86 +48,56 @@ func GetCommitGraph(r *git.Repository, page int) (GraphItems, error) {
if err := graphCmd.RunInDirTimeoutEnvFullPipelineFunc(nil, -1, r.Path, stdoutWriter, stderr, nil, 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() {
- if bytes.IndexByte(scanner.Bytes(), '*') >= 0 {
- line := scanner.Text()
- graphItem, err := graphItemFromString(line, r)
- if err != nil {
+ line := scanner.Bytes()
+ if bytes.IndexByte(line, '*') >= 0 {
+ if err := parser.AddLineToGraph(graph, row, line); err != nil {
cancel()
return err
}
- commitGraph = append(commitGraph, graphItem)
break
}
+ parser.ParseGlyphs(line)
}
for scanner.Scan() {
- line := scanner.Text()
- graphItem, err := graphItemFromString(line, r)
- if err != nil {
+ row++
+ line := scanner.Bytes()
+ if err := parser.AddLineToGraph(graph, row, line); err != nil {
cancel()
return err
}
- commitGraph = append(commitGraph, graphItem)
}
return scanner.Err()
}); err != nil {
- return commitGraph, err
- }
-
- return commitGraph, nil
-}
-
-func graphItemFromString(s string, r *git.Repository) (GraphItem, error) {
-
- var ascii string
- var data = "|||||||"
- lines := strings.SplitN(s, "DATA:", 2)
-
- switch len(lines) {
- case 1:
- ascii = lines[0]
- case 2:
- ascii = lines[0]
- data = lines[1]
- default:
- return GraphItem{}, fmt.Errorf("Failed parsing grap line:%s. Expect 1 or two fields", s)
- }
-
- rows := strings.SplitN(data, "|", 8)
- if len(rows) < 8 {
- return GraphItem{}, fmt.Errorf("Failed parsing grap line:%s - Should containt 8 datafields", s)
- }
-
- /* // see format in getCommitGraph()
- 0 Relation string
- 1 Branch string
- 2 Rev string
- 3 Date string
- 4 Author string
- 5 AuthorEmail string
- 6 ShortRev string
- 7 Subject string
- */
- gi := GraphItem{ascii,
- rows[0],
- rows[1],
- rows[2],
- rows[3],
- rows[4],
- rows[5],
- rows[6],
- rows[7],
- len(rows[2]) == 0, // no commits referred to, only relation in current line.
+ return graph, err
}
- return gi, nil
+ return graph, nil
}
diff --git a/modules/gitgraph/graph_models.go b/modules/gitgraph/graph_models.go
new file mode 100644
index 0000000000..ea6ba96084
--- /dev/null
+++ b/modules/gitgraph/graph_models.go
@@ -0,0 +1,186 @@
+// Copyright 2020 The Gitea Authors. All rights reserved.
+// Use of this source code is governed by a MIT-style
+// license that can be found in the LICENSE file.
+
+package gitgraph
+
+import (
+ "bytes"
+ "fmt"
+)
+
+// 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
+}
+
+// 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 co-ordinate 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("|"), 7)
+ if len(data) < 7 {
+ 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)
+ Branch: string(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:%an => author name
+ Author: string(data[3]),
+ // 4 matches git log --pretty=format:%ae => author email
+ AuthorEmail: string(data[4]),
+ // 5 matches git log --pretty=format:%h => abbreviated commit hash
+ ShortRev: string(data[5]),
+ // 6 matches git log --pretty=format:%s => subject
+ Subject: string(data[6]),
+ }, nil
+}
+
+// Commit represents a commit at co-ordinate X, Y with the data
+type Commit struct {
+ Flow int64
+ Row int
+ Column int
+ Branch string
+ Rev string
+ Date string
+ Author string
+ AuthorEmail 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
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 = `*
+*
+*
+*
+*
+*
+*
+*
+|\
+* |
+* |
+* |
+* |
+* |
+| *
+* |
+| *
+| |\
+* | |
+| | *
+| | |\
+* | | \
+|\ \ \ \
+| * | | |
+| |\| | |
+* | | | |
+|/ / / /
+| | | *
+| * | |
+| * | |
+| * | |
+* | | |
+* | | |
+* | | |
+* | | |
+* | | |
+|\ \ \ \
+| | * | |
+| | |\| |
+| | | * |
+| | | | *
+* | | | |
+* | | | |
+* | | | |
+* | | | |
+* | | | |
+|\ \ \ \ \
+| * | | | |
+|/| | | | |
+| | |/ / /
+| |/| | |
+| | | | *
+| * | | |
+|/| | | |
+| * | | |
+|/| | | |
+| | |/ /
+| |/| |
+| * | |
+| * | |
+| |\ \ \
+| | * | |
+| |/| | |
+| | | |/
+| | |/|
+| * | |
+| * | |
+| * | |
+| | * |
+| | |\ \
+| | | * |
+| | |/| |
+| | | * |
+| | | |\ \
+| | | | * |
+| | | |/| |
+| | * | | |
+| | * | | |
+| | |\ \ \ \
+| | | * | | |
+| | |/| | | |
+| | | | | * |
+| | | | |/ /
+* | | | / /
+|/ / / / /
+* | | | |
+|\ \ \ \ \
+| * | | | |
+|/| | | | |
+| * | | | |
+| * | | | |
+| |\ \ \ \ \
+| | | * \ \ \
+| | | |\ \ \ \
+| | | | * | | |
+| | | |/| | | |
+| | | | | |/ /
+| | | | |/| |
+* | | | | | |
+* | | | | | |
+* | | | | | |
+| | | | * | |
+* | | | | | |
+| | * | | | |
+| |/| | | | |
+* | | | | | |
+| |/ / / / /
+|/| | | | |
+| | | | * |
+| | | |/ /
+| | |/| |
+| * | | |
+| | | | *
+| | * | |
+| | |\ \ \
+| | | * | |
+| | |/| | |
+| | | |/ /
+| | | * |
+| | * | |
+| | |\ \ \
+| | | * | |
+| | |/| | |
+| | | |/ /
+| | | * |
+* | | | |
+|\ \ \ \ \
+| * \ \ \ \
+| |\ \ \ \ \
+| | | |/ / /
+| | |/| | |
+| | | | * |
+| | | | * |
+* | | | | |
+* | | | | |
+|/ / / / /
+| | | * |
+* | | | |
+* | | | |
+* | | | |
+* | | | |
+|\ \ \ \ \
+| * | | | |
+|/| | | | |
+| | * | | |
+| | |\ \ \ \
+| | | * | | |
+| | |/| | | |
+| |/| | |/ /
+| | | |/| |
+| | | | | *
+| |_|_|_|/
+|/| | | |
+| | * | |
+| |/ / /
+* | | |
+* | | |
+| | * |
+* | | |
+* | | |
+| * | |
+| | * |
+| * | |
+* | | |
+|\ \ \ \
+| * | | |
+|/| | | |
+| |/ / /
+| * | |
+| |\ \ \
+| | * | |
+| |/| | |
+| | |/ /
+| | * |
+| | |\ \
+| | | * |
+| | |/| |
+* | | | |
+* | | | |
+|\ \ \ \ \
+| * | | | |
+|/| | | | |
+| | * | | |
+| | * | | |
+| | * | | |
+| |/ / / /
+| * | | |
+| |\ \ \ \
+| | * | | |
+| |/| | | |
+* | | | | |
+* | | | | |
+* | | | | |
+* | | | | |
+* | | | | |
+| | | | * |
+* | | | | |
+|\ \ \ \ \ \
+| * | | | | |
+|/| | | | | |
+| | | | | * |
+| | | | |/ /
+* | | | | |
+|\ \ \ \ \ \
+* | | | | | |
+* | | | | | |
+| | | | * | |
+* | | | | | |
+* | | | | | |
+|\ \ \ \ \ \ \
+| | |_|_|/ / /
+| |/| | | | |
+| | | | * | |
+| | | | * | |
+| | | | * | |
+| | | | * | |
+| | | | * | |
+| | | | * | |
+| | | |/ / /
+| | | * | |
+| | | * | |
+| | | * | |
+| | |/| | |
+| | | * | |
+| | |/| | |
+| | | |/ /
+| | * | |
+| |/| | |
+| | | * |
+| | |/ /
+| | * |
+| * | |
+| |\ \ \
+| * | | |
+| | * | |
+| |/| | |
+| | |/ /
+| | * |
+| | |\ \
+| | * | |
+* | | | |
+|\| | | |
+| * | | |
+| * | | |
+| * | | |
+| | * | |
+| * | | |
+| |\| | |
+| * | | |
+| | * | |
+| | * | |
+| * | | |
+| * | | |
+| * | | |
+| * | | |
+| * | | |
+| * | | |
+| * | | |
+| * | | |
+| | * | |
+| * | | |
+| * | | |
+| * | | |
+| * | | |
+| | * | |
+* | | | |
+|\| | | |
+| | * | |
+| * | | |
+| |\| | |
+| | * | |
+| | * | |
+| | * | |
+| | | * |
+* | | | |
+|\| | | |
+| | * | |
+| | |/ /
+| * | |
+| * | |
+| |\| |
+* | | |
+|\| | |
+| | * |
+| | * |
+| | * |
+| * | |
+| | * |
+| * | |
+| | * |
+| | * |
+| | * |
+| * | |
+| * | |
+| * | |
+| * | |
+| * | |
+| * | |
+| * | |
+* | | |
+|\| | |
+| * | |
+| |\| |
+| | * |
+| | |\ \
+* | | | |
+|\| | | |
+| * | | |
+| |\| | |
+| | * | |
+| | | * |
+| | |/ /
+* | | |
+* | | |
+|\| | |
+| * | |
+| |\| |
+| | * |
+| | * |
+| | * |
+| | | *
+* | | |
+|\| | |
+| * | |
+| * | |
+| | | *
+| | | |\
+* | | | |
+| |_|_|/
+|/| | |
+| * | |
+| |\| |
+| | * |
+| | * |
+| | * |
+| | * |
+| | * |
+| * | |
+* | | |
+|\| | |
+| * | |
+|/| | |
+| |/ /
+| * |
+| |\ \
+| * | |
+| * | |
+* | | |
+|\| | |
+| | * |
+| * | |
+| * | |
+| * | |
+* | | |
+|\| | |
+| * | |
+| * | |
+| | * |
+| | |\ \
+| | |/ /
+| |/| |
+| * | |
+* | | |
+|\| | |
+| * | |
+* | | |
+|\| | |
+| * | |
+| |\ \ \
+| * | | |
+| * | | |
+| | | * |
+| * | | |
+| * | | |
+| | |/ /
+| |/| |
+| | * |
+* | | |
+|\| | |
+| * | |
+| * | |
+| * | |
+| * | |
+| * | |
+| |\ \ \
+* | | | |
+|\| | | |
+| * | | |
+| * | | |
+* | | | |
+* | | | |
+|\| | | |
+| | | | *
+| | | | |\
+| |_|_|_|/
+|/| | | |
+| * | | |
+* | | | |
+* | | | |
+|\| | | |
+| * | | |
+| |\ \ \ \
+| | | |/ /
+| | |/| |
+| * | | |
+| * | | |
+| * | | |
+| * | | |
+| | * | |
+| | | * |
+| | |/ /
+| |/| |
+* | | |
+|\| | |
+| * | |
+| * | |
+| * | |
+| * | |
+| * | |
+* | | |
+|\| | |
+| * | |
+| * | |
+* | | |
+| * | |
+| * | |
+| * | |
+* | | |
+* | | |
+* | | |
+|\| | |
+| * | |
+* | | |
+* | | |
+* | | |
+* | | |
+| | | *
+* | | |
+|\| | |
+| * | |
+| * | |
+| * | |
+`
diff --git a/modules/gitgraph/parser.go b/modules/gitgraph/parser.go
new file mode 100644
index 0000000000..62e0505652
--- /dev/null
+++ b/modules/gitgraph/parser.go
@@ -0,0 +1,338 @@
+// Copyright 2020 The Gitea Authors. All rights reserved.
+// Use of this source code is governed by a MIT-style
+// license that can be found in the LICENSE file.
+
+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)
+ }
+}