path: root/pkg/gui/presentation/graph/graph.go

package graph

import (
	"runtime"
	"strings"
	"sync"

	"github.com/jesseduffield/generics/set"
	"github.com/jesseduffield/lazygit/pkg/commands/models"
	"github.com/jesseduffield/lazygit/pkg/gui/style"
	"github.com/jesseduffield/lazygit/pkg/utils"
	"github.com/samber/lo"
	"golang.org/x/exp/slices"
)

type PipeKind uint8

const (
	TERMINATES PipeKind = iota
	STARTS
	CONTINUES
)

type Pipe struct {
	fromPos int
	toPos   int
	fromSha string
	toSha   string
	kind    PipeKind
	style   style.TextStyle
}

var highlightStyle = style.FgLightWhite.SetBold()

func ContainsCommitSha(pipes []*Pipe, sha string) bool {
	for _, pipe := range pipes {
		if equalHashes(pipe.fromSha, sha) {
			return true
		}
	}
	return false
}

func (self Pipe) left() int {
	return min(self.fromPos, self.toPos)
}

func (self Pipe) right() int {
	return max(self.fromPos, self.toPos)
}

func RenderCommitGraph(commits []*models.Commit, selectedCommitSha string, getStyle func(c *models.Commit) style.TextStyle) []string {
	pipeSets := GetPipeSets(commits, getStyle)
	if len(pipeSets) == 0 {
		return nil
	}

	lines := RenderAux(pipeSets, commits, selectedCommitSha)

	return lines
}

func GetPipeSets(commits []*models.Commit, getStyle func(c *models.Commit) style.TextStyle) [][]*Pipe {
	if len(commits) == 0 {
		return nil
	}

	pipes := []*Pipe{{fromPos: 0, toPos: 0, fromSha: "START", toSha: commits[0].Sha, kind: STARTS, style: style.FgDefault}}

	return lo.Map(commits, func(commit *models.Commit, _ int) []*Pipe {
		pipes = getNextPipes(pipes, commit, getStyle)
		return pipes
	})
}

func RenderAux(pipeSets [][]*Pipe, commits []*models.Commit, selectedCommitSha string) []string {
	maxProcs := runtime.GOMAXPROCS(0)

	// splitting up the rendering of the graph into multiple goroutines allows us to render the graph in parallel
	chunks := make([][]string, maxProcs)
	perProc := len(pipeSets) / maxProcs

	wg := sync.WaitGroup{}
	wg.Add(maxProcs)

	for i := 0; i < maxProcs; i++ {
		i := i
		go func() {
			from := i * perProc
			to := (i + 1) * perProc
			if i == maxProcs-1 {
				to = len(pipeSets)
			}
			innerLines := make([]string, 0, to-from)
			for j, pipeSet := range pipeSets[from:to] {
				k := from + j
				var prevCommit *models.Commit
				if k > 0 {
					prevCommit = commits[k-1]
				}
				line := renderPipeSet(pipeSet, selectedCommitSha, prevCommit)
				innerLines = append(innerLines, line)
			}
			chunks[i] = innerLines
			wg.Done()
		}()
	}

	wg.Wait()

	return lo.Flatten(chunks)
}

func getNextPipes(prevPipes []*Pipe, commit *models.Commit, getStyle func(c *models.Commit) style.TextStyle) []*Pipe {
	maxPos := 0
	for _, pipe := range prevPipes {
		if pipe.toPos > maxPos {
			maxPos = pipe.toPos
		}
	}

	// a pipe that terminated in the previous line has no bearing on the current line
	// so we'll filter those out
	currentPipes := lo.Filter(prevPipes, func(pipe *Pipe, _ int) bool {
		return pipe.kind != TERMINATES
	})

	newPipes := make([]*Pipe, 0, len(currentPipes)+len(commit.Parents))
	// start by assuming that we've got a brand new commit not related to any preceding commit.
	// (this only happens when we're doing `git log --all`). These will be tacked onto the far end.
	pos := maxPos + 1
	for _, pipe := range currentPipes {
		if equalHashes(pipe.toSha, commit.Sha) {
			// turns out this commit does have a descendant so we'll place it right under the first instance
			pos = pipe.toPos
			break
		}
	}

	// a taken spot is one where a current pipe is ending on
	takenSpots := set.New[int]()
	// a traversed spot is one where a current pipe is starting on, ending on, or passing through
	traversedSpots := set.New[int]()

	if len(commit.Parents) > 0 { // merge commit
		newPipes = append(newPipes, &Pipe{
			fromPos: pos,
			toPos:   pos,
			fromSha: commit.Sha,
			toSha:   commit.Parents[0],
			kind:    STARTS,
			style:   getStyle(commit),
		})
	} else if len(commit.Parents) == 0 { // root commit
		newPipes = append(newPipes, &Pipe{
			fromPos: pos,
			toPos:   pos,
			fromSha: commit.Sha,
			toSha:   models.EmptyTreeCommitHash,
			kind:    STARTS,
			style:   getStyle(commit),
		})
	}

	traversedSpotsForContinuingPipes := set.New[int]()
	for _, pipe := range currentPipes {
		if !equalHashes(pipe.toSha, commit.Sha) {
			traversedSpotsForContinuingPipes.Add(pipe.toPos)
		}
	}

	getNextAvailablePosForContinuingPipe := func() int {
		i := 0
		for {
			if !traversedSpots.Includes(i) {
				return i
			}
			i++
		}
	}

	getNextAvailablePosForNewPipe := func() int {
		i := 0
		for {
			// a newly created pipe is not allowed to end on a spot that's already taken,
			// nor on a spot that's been traversed by a continuing pipe.
			if !takenSpots.Includes(i) && !traversedSpotsForContinuingPipes.Includes(i) {
				return i
			}
			i++
		}
	}

	traverse := func(from, to int) {
		left, right := from, to
		if left > right {
			left, right = right, left
		}
		for i := left; i <= right; i++ {
			traversedSpots.Add(i)
		}
		takenSpots.Add(to)
	}

	for _, pipe := range currentPipes {
		if equalHashes(pipe.toSha, commit.Sha) {
			// terminating here
			newPipes = append(newPipes, &Pipe{
				fromPos: pipe.toPos,
				toPos:   pos,
				fromSha: pipe.fromSha,