summaryrefslogtreecommitdiffstats
path: root/modules/gitgraph
diff options
context:
space:
mode:
Diffstat (limited to 'modules/gitgraph')
-rw-r--r--modules/gitgraph/graph.go116
-rw-r--r--modules/gitgraph/graph_models.go256
-rw-r--r--modules/gitgraph/graph_test.go714
-rw-r--r--modules/gitgraph/parser.go336
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)
+ }
+}
generated by cgit v1.2.3 (git 2.39.1) at 2024-12-26 17:05:30 +0100