add graph algorithm

6 files changed, 1083 insertions, 5 deletions

diff --git a/pkg/gui/filetree/file_manager_test.go b/pkg/gui/filetree/file_manager_test.go
index 36343bc13..83ba5b086 100644
--- a/pkg/gui/filetree/file_manager_test.go
+++ b/pkg/gui/filetree/file_manager_test.go
@@ -9,9 +9,11 @@ import (
 	"github.com/xo/terminfo"
 )
 
-func TestRender(t *testing.T) {
+func init() {
 	color.ForceSetColorLevel(terminfo.ColorLevelNone)
+}
 
+func TestRender(t *testing.T) {
 	scenarios := []struct {
 		name           string
 		root           *FileNode
diff --git a/pkg/gui/presentation/graph/cell.go b/pkg/gui/presentation/graph/cell.go
new file mode 100644
index 000000000..e4f57bf80
--- /dev/null
+++ b/pkg/gui/presentation/graph/cell.go
@@ -0,0 +1,141 @@
+package graph
+
+import (
+	"github.com/jesseduffield/lazygit/pkg/gui/style"
+)
+
+const mergeSymbol = '⏣'
+const commitSymbol = '⎔'
+
+type cellType int
+
+const (
+	CONNECTION cellType = iota
+	COMMIT
+	MERGE
+)
+
+type Cell struct {
+	up, down, left, right bool
+	cellType              cellType
+	rightStyle            *style.TextStyle
+	style                 style.TextStyle
+}
+
+func (cell *Cell) render() string {
+	up, down, left, right := cell.up, cell.down, cell.left, cell.right
+
+	first, second := getBoxDrawingChars(up, down, left, right)
+	var adjustedFirst rune
+	switch cell.cellType {
+	case CONNECTION:
+		adjustedFirst = first
+	case COMMIT:
+		adjustedFirst = commitSymbol
+	case MERGE:
+		adjustedFirst = mergeSymbol
+	}
+
+	var rightStyle *style.TextStyle
+	if cell.rightStyle == nil {
+		rightStyle = &cell.style
+	} else {
+		rightStyle = cell.rightStyle
+	}
+
+	// just doing this for the sake of easy testing, so that we don't need to
+	// assert on the style of a space given a space has no styling (assuming we
+	// stick to only using foreground styles)
+	var styledSecondChar string
+	if second == ' ' {
+		styledSecondChar = " "
+	} else {
+		styledSecondChar = rightStyle.Sprint(string(second))
+	}
+
+	return cell.style.Sprint(string(adjustedFirst)) + styledSecondChar
+}
+
+func (cell *Cell) reset() {
+	cell.up = false
+	cell.down = false
+	cell.left = false
+	cell.right = false
+}
+
+func (cell *Cell) setUp(style style.TextStyle) *Cell {
+	cell.up = true
+	cell.style = style
+	return cell
+}
+
+func (cell *Cell) setDown(style style.TextStyle) *Cell {
+	cell.down = true
+	cell.style = style
+	return cell
+}
+
+func (cell *Cell) setLeft(style style.TextStyle) *Cell {
+	cell.left = true
+	if !cell.up && !cell.down {
+		// vertical trumps left
+		cell.style = style
+	}
+	return cell
+}
+
+func (cell *Cell) setRight(style style.TextStyle, override bool) *Cell {
+	cell.right = true
+	if cell.rightStyle == nil || override {
+		cell.rightStyle = &style
+	}
+	return cell
+}
+
+func (cell *Cell) setStyle(style style.TextStyle) *Cell {
+	cell.style = style
+	return cell
+}
+
+func (cell *Cell) setType(cellType cellType) *Cell {
+	cell.cellType = cellType
+	return cell
+}
+
+func getBoxDrawingChars(up, down, left, right bool) (rune, rune) {
+	if up && down && left && right {
+		return '│', '─'
+	} else if up && down && left && !right {
+		return '│', ' '
+	} else if up && down && !left && right {
+		return '│', '─'
+	} else if up && down && !left && !right {
+		return '│', ' '
+	} else if up && !down && left && right {
+		return '┴', '─'
+	} else if up && !down && left && !right {
+		return '╯', ' '
+	} else if up && !down && !left && right {
+		return '╰', '─'
+	} else if up && !down && !left && !right {
+		return '╵', ' '
+	} else if !up && down && left && right {
+		return '┬', '─'
+	} else if !up && down && left && !right {
+		return '╮', ' '
+	} else if !up && down && !left && right {
+		return '╭', '─'
+	} else if !up && down && !left && !right {
+		return '╷', ' '
+	} else if !up && !down && left && right {
+		return '─', '─'
+	} else if !up && !down && left && !right {
+		return '─', ' '
+	} else if !up && !down && !left && right {
+		return '╶', '─'
+	} else if !up && !down && !left && !right {
+		return ' ', ' '
+	} else {
+		panic("should not be possible")
+	}
+}
diff --git a/pkg/gui/presentation/graph/graph.go b/pkg/gui/presentation/graph/graph.go
new file mode 100644
index 000000000..16d7a8ab1
--- /dev/null
+++ b/pkg/gui/presentation/graph/graph.go
@@ -0,0 +1,375 @@
+package graph
+
+import (
+	"sort"
+	"strings"
+	"sync"
+
+	"github.com/jesseduffield/lazygit/pkg/commands/models"
+	"github.com/jesseduffield/lazygit/pkg/gui/style"
+	"github.com/jesseduffield/lazygit/pkg/utils"
+)
+
+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 utils.Min(self.fromPos, self.toPos)
+}
+
+func (self Pipe) right() int {
+	return utils.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}}
+
+	pipeSets := [][]Pipe{}
+	for _, commit := range commits {
+		pipes = getNextPipes(pipes, commit, getStyle)
+		pipeSets = append(pipeSets, pipes)
+	}
+
+	return pipeSets
+}
+
+func RenderAux(pipeSets [][]Pipe, commits []*models.Commit, selectedCommitSha string) []string {
+	lines := make([]string, len(pipeSets))
+	wg := sync.WaitGroup{}
+	wg.Add(len(pipeSets))
+	for i, pipeSet := range pipeSets {
+		i := i
+		pipeSet := pipeSet
+		go func() {
+			defer wg.Done()
+			var prevCommit *models.Commit
+			if i > 0 {
+				prevCommit = commits[i-1]
+			}
+			line := renderPipeSet(pipeSet, selectedCommitSha, prevCommit)
+			lines[i] = line
+		}()
+	}
+	wg.Wait()
+	return lines
+}
+
+func getNextPipes(prevPipes []Pipe, commit *models.Commit, getStyle func(c *models.Commit) style.TextStyle) []Pipe {
+	currentPipes := make([]Pipe, 0, len(prevPipes))
+	maxPos := 0
+	for _, pipe := range prevPipes {
+		// a pipe that terminated in the previous line has no bearing on the current line
+		// so we'll filter those out
+		if pipe.kind != TERMINATES {
+			currentPipes = append(currentPipes, pipe)
+		}
+		maxPos = utils.Max(maxPos, pipe.toPos)
+	}
+
+	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 := make(map[int]bool)
+	// a traversed spot is one where a current pipe is starting on, ending on, or passing through
+	traversedSpots := make(map[int]bool)
+
+	if len(commit.Parents) > 0 {
+		newPipes = append(newPipes, Pipe{
+			fromPos: pos,
+			toPos:   pos,
+			fromSha: commit.Sha,
+			toSha:   commit.Parents[0],
+			kind:    STARTS,
+			style:   getStyle(commit),
+		})
+	}
+
+	traversedSpotsForContinuingPipes := make(map[int]bool)
+	for _, pipe := range currentPipes {
+		if !equalHashes(pipe.toSha, commit.Sha) {
+			traversedSpotsForContinuingPipes[pipe.toPos] = true
+		}
+	}
+
+	getNextAvailablePosForContinuingPipe := func() int {
+		i := 0
+		for {
+			if !traversedSpots[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[i] && !traversedSpotsForContinuingPipes[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[i] = true
+		}
+		takenSpots[to] = true
+	}
+
+	for _, pipe := range currentPipes {
+		if equalHashes(pipe.toSha, commit.Sha) {
+			// terminating here
+			newPipes = append(newPipes, Pipe{
+				fromPos: pipe.toPos,
+				toPos:   pos,
+				fromSha: pipe.fromSha,
+				toSha:   pipe.toSha,
+				kind:    TERMINATES,
+				style:   pipe.style,
+			})
+			traverse(pipe.toPos, pos)
+		} else if pipe.toPos < pos {
+			// continuing here
+			availablePos := getNextAvailablePosForContinuingPipe()
+			newPipes = append(newPipes, Pipe{
+				fromPos: pipe.toPos,
+				toPos:   availablePos,
+				fromSha: pipe.fromSha,
+				toSha:   pipe.toSha,
+				kind:    CONTINUES,
+				style:   pipe.style,
+			})
+			traverse(pipe.toPos, availablePos)
+		}
+	}
+
+	if commit.IsMerge() {
+		for _, parent := range commit.Parents[1:] {
+			availablePos := getNextAvailablePosForNewPipe()
+			// need to act as if continuing pipes are going to continue on the same line.
+			newPipes = append(newPipes, Pipe{
+				fromPos: pos,
+				toPos:   availablePos,
+				fromSha: commit.Sha,
+				toSha:   parent,
+				kind:    STARTS,
+				style:   getStyle(commit),
+			})
+
+			takenSpots[availablePos] = true
+		}
+	}
+
+	for _, pipe := range currentPipes {
+		if !equalHashes(pipe.toSha, commit.Sha) && pipe.toPos > pos {
+			// continuing on, potentially moving left to fill in a blank spot
+			last := pipe.toPos
+			for i := pipe.toPos; i > pos; i-- {
+				if takenSpots[i] || traversedSpots[i] {
+					break
+				} else {
+					last = i
+				}
+			}
+			newPipes = append(newPipes, Pipe{
+				fromPos: pipe.toPos,
+				toPos:   last,
+				fromSha: pipe.fromSha,
+				toSha:   pipe.toSha,
+				kind:    CONTINUES,
+				style:   pipe.style,
+			})
+			traverse(pipe.toPos, last)
+		}
+	}
+
+	// not efficient but doing it for now: sorting my pipes by toPos, then by kind
+	sort.Slice(newPipes, func(i, j int) bool {
+		if newPipes[i].toPos == newPipes[j].toPos {
+			return newPipes[i].kind < newPipes[j].kind
+		}
+		return newPipes[i].toPos < newPipes[j].toPos
+	})
+
+	return newPipes
+}
+
+func renderPipeSet(
+	pipes []Pipe,
+	selectedCommitSha string,
+	prevCommit *models.Commit,
+) string {
+	maxPos := 0
+	commitPos := 0
+	startCount := 0
+	for _, pipe := range pipes {
+		if pipe.kind == STARTS {
+			startCount++
+			commitPos = pipe.fromPos
+		} else if pipe.kind == TERMINATES {
+			commitPos = pipe.toPos
+		}
+
+		if pipe.right() > maxPos {
+			maxPos = pipe.right()
+		}
+	}
+	isMerge := startCount > 1
+
+	cells := make([]*Cell, maxPos+1)
+	for i := range cells {
+		cells[i] = &Cell{cellType: CONNECTION, style: style.FgDefault}
+	}
+
+	renderPipe := func(pipe Pipe, style style.TextStyle, overrideRightStyle bool) {
+		left := pipe.left()
+		right := pipe.right()
+
+		if left != right {
+			for i := left + 1; i < right; i++ {
+				cells[i].setLeft(style).setRight(style, overrideRightStyle)
+			}
+			cells[left].setRight(style, overrideRightStyle)
+			cells[right].setLeft(style)
+		}
+
+		if pipe.kind == STARTS || pipe.kind == CONTINUES {
+			cells[pipe.toPos].setDown(style)
+		}
+		if pipe.kind == TERMINATES || pipe.kind == CONTINUES {
+			cells[pipe.fromPos].setUp(style)
+		}
+	}
+
+	// we don't want to highlight two commits if they're contiguous. We only want
+	// to highlight multiple things if there's an actual visible pipe involved.
+	highlight := true
+	if prevCommit != nil && equalHashes(prevCommit.Sha, selectedCommitSha) {
+		highlight = false
+		for _, pipe := range pipes {
+			if equalHashes(pipe.fromSha, selectedCommitSha) && (pipe.kind != TERMINATES || pipe.fromPos != pipe.toPos) {
+				highlight = true
+			}
+		}
+	}
+
+	// so we have our commit pos again, now it's time to build the cells.
+	// we'll handle the one that's sourced from our selected commit last so that it can override the other cells.
+	selectedPipes := []Pipe{}
+	// pre-allocating this one because most of the time we'll only have non-selected pipes
+	nonSelectedPipes := make([]Pipe, 0, len(pipes))
+
+	for _, pipe := range pipes {
+		if highlight && equalHashes(pipe.fromSha, selectedCommitSha) {
+			selectedPipes = append(selectedPipes, pipe)
+		} else {
+			nonSelectedPipes = append(nonSelectedPipes, pipe)
+		}
+	}
+
+	for _, pipe := range nonSelectedPipes {
+		if pipe.kind == STARTS {
+			renderPipe(pipe, pipe.style, true)
+		}
+	}
+
+	for _, pipe := range nonSelectedPipes {
+		if pipe.kind != STARTS && !(pipe.kind == TERMINATES && pipe.fromPos == commitPos && pipe.toPos == commitPos) {
+			renderPipe(pipe, pipe.style, false)
+		}
+	}
+
+	for _, pipe := range selectedPipes {
+		for i := pipe.left(); i <= pipe.right(); i++ {
+			cells[i].reset()
+		}
+	}
+	for _, pipe := range selectedPipes {
+		renderPipe(pipe, highlightStyle, true)
+		if pipe.toPos == commitPos {
+			cells[pipe.toPos].setStyle(highlightStyle)
+		}
+	}
+
+	cType := COMMIT
+	if isMerge {
+		cType = MERGE
+	}
+
+	cells[commitPos].setType(cType)
+
+	renderedCells := make([]string, len(cells))
+	for i, cell := range cells {
+		renderedCells[i] = cell.render()
+	}
+	return strings.Join(renderedCells, "")
+}
+
+func equalHashes(a, b string) bool {
+	// if our selectedCommitSha is an empty string we treat that as meaning there is no selected commit sha
+	if a == "" || b == "" {
+		return false
+	}
+
+	length := utils.Min(len(a), len(b))
+	// parent hashes are only stored up to 20 characters for some reason so we'll truncate to that for comparison
+	return a[:length] == b[:length]
+}
diff --git a/pkg/gui/presentation/graph/graph_test.go b/pkg/gui/presentation/graph/graph_test.go
new file mode 100644
index 000000000..180f5f2b7
--- /dev/null
+++ b/pkg/gui/presentation/graph/graph_test.go
@@ -0,0 +1,553 @@
+package graph
+
+import (
+	"strings"
+	"testing"
+
+	"github.com/gookit/color"
+	"github.com/jesseduffield/lazygit/pkg/commands/models"
+	"github.com/jesseduffield/lazygit/pkg/gui/style"
+	"github.com/jesseduffield/lazygit/pkg/utils"
+	"github.com/stretchr/testify/assert"
+	"github.com/xo/terminfo"
+)
+
+func init() {
+	// on CI we've got no color capability so we're forcing it here
+	color.ForceSetColorLevel(terminfo.ColorLevelMillions)
+}
+
+func TestRenderCommitGraph(t *testing.T) {
+	tests := []struct {
+		name           string
+		commits        []*models.Commit
+		expectedOutput string
+	}{
+		{
+			name: "with some merges",
+			commits: []*models.Commit{
+				{Sha: "1", Parents: []string{"2"}},
+				{Sha: "2", Parents: []string{"3"}},
+				{Sha: "3", Parents: []string{"4"}},
+				{Sha: "4", Parents: []string{"5", "7"}},
+				{Sha: "7", Parents: []string{"5"}},
+				{Sha: "5", Parents: []string{"8"}},
+				{Sha: "8", Parents: []string{"9"}},
+				{Sha: "9", Parents: []string{"A", "B"}},
+				{Sha: "B", Parents: []string{"D"}},
+				{Sha: "D", Parents: []string{"D"}},
+				{Sha: "A", Parents: []string{"E"}},
+				{Sha: "E", Parents: []string{"F"}},
+				{Sha: "F", Parents: []string{"D"}},
+				{Sha: "D", Parents: []string{"G"}},
+			},
+			expectedOutput: `
+			1 ⎔
+			2 ⎔
+			3 ⎔
+			4 ⏣─╮
+			7 │ ⎔
+			5 ⎔─╯
+			8 ⎔
+			9 ⏣─╮
+			B │ ⎔
+			D │ ⎔
+			A ⎔ │
+			E ⎔ │
+			F ⎔ │
+			D ⎔─╯`,
+		},
+		{
+			name: "with a path that has room to move to the left",
+			commits: []*models.Commit{
+				{Sha: "1", Parents: []string{"2"}},
+				{Sha: "2", Parents: []string{"3", "4"}},
+				{Sha: "4", Parents: []string{"3", "5"}},
+				{Sha: "3", Parents: []string{"5"}},
+				{Sha: "5", Parents: []string{"6"}},
+				{Sha: "6", Parents: []string{"7"}},
+			},
+			expectedOutput: `
+			1 ⎔
+			2 ⏣─╮
+			4 │ ⏣─╮
+			3 ⎔─╯ │
+			5 ⎔───╯
+			6 ⎔`,
+		},
+		{
+			name: "with a new commit",
+			commits: []*models.Commit{
+				{Sha: "1", Parents: []string{"2"}},
+				{Sha: "2", Parents: []string{"3", "4"}},
+				{Sha: "4", Parents: []string{"3", "5"}},
+				{Sha: "Z", Parents: []string{"Z"}},
+				{Sha: "3", Parents: []string{"5"}},
+				{Sha: "5", Parents: []string{"6"}},
+				{Sha: "6", Parents: []string{"7"}},
+			},
+			expectedOutput: `
+			1 ⎔
+			2 ⏣─╮
+			4 │ ⏣─╮
+			Z │ │ │ ⎔
+			3 ⎔─╯ │ │
+			5 ⎔───╯ │
+			6 ⎔ ╭───╯`,
+		},
+		{
+			name: "with a path that has room to move to the left and continues",
+			commits: []*models.Commit{
+				{Sha: "1", Parents: []string{"2"}},
+				{Sha: "2", Parents: []string{"3", "4"}},
+				{Sha: "3", Parents: []string{"5", "4"}},
+				{Sha: "5", Parents: []string{"7", "8"}},
+				{Sha: "4", Parents: []string{"7"}},
+				{Sha: "7", Parents: []string{"11"}},
+			},
+			expectedOutput: `
+			1 ⎔
+			2 ⏣─╮
+			3 ⏣─│─╮
+			5 ⏣─│─│─╮
+			4 │ ⎔─╯ │
+			7 ⎔─╯ ╭─╯`,
+		},
+		{
+			name: "with a path that has room to move to the left and continues",
+			commits: []*models.Commit{
+				{Sha: "1", Parents: []string{"2"}},
+				{Sha: "2", Parents: []string{"3", "4"}},
+				{Sha: "3", Parents: []string{"5", "4"}},
+				{Sha: "5", Parents: []string{"7", "8"}},
+				{Sha: "7", Parents: []string{"4", "A"}},
+				{Sha: "4", Parents: []string{"B"}},
+				{Sha: "B", Parents: []string{"C"}},
+			},
+			expectedOutput: `
+			1 ⎔
+			2 ⏣─╮
+			3 ⏣─│─╮
+			5 ⏣─│─│─╮
+			7 ⏣─│─│─│─╮
+			4 ⎔─┴─╯ │ │
+			B ⎔ ╭───╯ │`,
+		},
+		{
+			name: "with a path that has room to move to the left and continues",
+			commits: []*models.Commit{
+				{Sha: "1", Parents: []string{"2", "3"}},
+				{Sha: "3", Parents: []string{"2"}},
+				{Sha: "2", Parents: []string{"4", "5"}},
+				{Sha: "4", Parents: []string{"6", "7"}},
+				{Sha: "6", Parents: []string{"8"}},
+			},
+			expectedOutput: `
+			1 ⏣─╮
+			3 │ ⎔
+			2 ⏣─│
+			4 ⏣─│─╮
+			6 ⎔ │ │`,
+		},
+		{
+			name: "new merge path fills gap before continuing path on right",
+			commits: []*models.Commit{
+				{Sha: "1", Parents: []string{"2", "3", "4", "5"}},
+				{Sha: "4", Parents: []string{"2"}},
+				{Sha: "2", Parents: []string{"A"}},
+				{Sha: "A", Parents: []string{"6", "B"}},
+				{Sha: "B", Parents: []string{"C"}},
+			},
+			expectedOutput: `
+			1 ⏣─┬─┬─╮
+			4 │ │ ⎔ │
+			2 ⎔─│─╯ │
+			A ⏣─│─╮ │
+			B │ │ ⎔ │`,
+		},
+		{
+			name: "with a path that has room to move to the left and continues",
+			commits: []*models.Commit{
+				{Sha: "1", Parents: []string{"2"}},
+				{Sha: "2", Parents: []string{"3", "4"}},
+				{Sha: "3", Parents: []string{"5", "4"}},
+				{Sha: "5", Parents: []string{"7", "8"}},
+				{Sha: "7", Parents: []string{"4", "A"}},
+				{Sha: "4", Parents: []string{"B"}},
+				{Sha: "B", Parents: []string{"C"}},
+				{Sha: "C", Parents: []string{"D"}},
+			},
+			expectedOutput: `
+			1 ⎔
+			2 ⏣─╮
+			3 ⏣─│─╮
+			5 ⏣─│─│─╮
+			7 ⏣─│─│─│─╮
+			4 ⎔─┴─╯ │ │
+			B ⎔ ╭───╯ │
+			C ⎔ │ ╭───╯`,
+		},
+		{
+			name: "with a path that has room to move to the left and continues",
+			commits: []*models.Commit{
+				{Sha: "1", Parents: []string{"2"}},
+				{Sha: "2", Parents: []string{"3", "4"}},
+				{Sha: "3", Parents: []string{"5", "4"}},
+				{Sha: "5", Parents: []string{"7", "G"}},
+				{Sha: "7", Parents: []string{"8", "A"}},
+				{Sha: "8", Parents: []string{"4", "E"}},
+				{Sha: "4", Parents: []string{"B"}},
+				{Sha: "B", Parents: []string{"C"}},
+				{Sha: "C", Parents: []string{"D"}},
+				{Sha: "D", Parents: []string{"F"}},
+			},
+			expectedOutput: `
+			1 ⎔
+			2 ⏣─╮
+			3 ⏣─│─╮
+			5 ⏣─│─│─╮
+			7 ⏣─│─│─│─╮
+			8 ⏣─│─│─│─│─╮
+			4 ⎔─┴─╯ │ │ │
+			B ⎔ ╭───╯ │ │
+			C ⎔ │ ╭───╯ │
+			D ⎔ │ │ ╭───╯`,
+		},
+	}
+
+	for _, test := range tests {
+		test := test
+		t.Run(test.name, func(t *testing.T) {
+			getStyle := func(c *models.Commit) style.TextStyle { return style.FgDefault }
+			lines := RenderCommitGraph(test.commits, "blah", getStyle)
+
+			trimmedExpectedOutput := ""
+			for _, line := range strings.Split(strings.TrimPrefix(test.expectedOutput, "\n"), "\n") {
+				trimmedExpectedOutput += strings.TrimSpace(line) + "\n"
+			}
+
+			t.Log("\nexpected: \n" + trimmedExpectedOutput)
+
+			output := ""
+			for i, line := range lines {
+				description := test.commits[i].Sha
+				output += strings.TrimSpace(description+" "+utils.Decolorise(line)) + "\n"
+			}
+			t.Log("\nactual: \n" + output)
+
+			assert.Equal(t,
+				trimmedExpectedOutput,
+				output)
+		})
+	}
+}
+
+func TestRenderPipeSet(t *testing.T) {
+	cyan := style.FgCyan
+	red := style.FgRed
+	green := style.FgGreen
+	// blue := style.FgBlue
+	yellow := style.FgYellow
+	magenta := style.FgMagenta
+	nothing := style.Nothing
+
+	tests := []struct {
+		name           string
+		pipes          []Pipe
+		commit         *models.Commit
+		prevCommit     *models.Commit
+		expectedStr    string
+		expectedStyles []style.TextStyle
+	}{
+		{
+			name: "single cell",
+			pipes: []Pipe{
+				{fromPos: 0, toPos: 0, fromSha: "a", toSha: "b", kind: TERMINATES, style: cyan},
+				{fromPos: 0, toPos: 0, fromSha: "b", toSha: "c", kind: STARTS, style: green},
+			},
+			prevCommit:     &models.Commit{Sha: "a"},
+			expectedStr:    "⎔",
+			expectedStyles: []style.TextStyle{green},
+		},
+		{
+			name: "single cell, selected",
+			pipes: []Pipe{
+				{fromPos: 0, toPos: 0, fromSha: "a", toSha: "selected", kind: TERMINATES, style: cyan},
+				{fromPos: 0, toPos: 0, fromSha: "selected", toSha: "c", kind: STARTS, style: green},
+			},
+			prevCommit:     &models.Commit{Sha: "a"},
+			expectedStr:    "⎔",
+			expectedStyles: []style.TextStyle{highlightStyle},
+		},
+		{
+			name: "terminating hook and starting hook, selected",
+			pipes: []Pipe{
+				{fromPos: 0, toPos: 0, fromSha: "a", toSha: "selected", kind: TERMINATES, style: cyan},
+				{fromPos: 1, toPos: 0, fromSha: "c", toSha: "selected", kind: TERMINATES, style: yellow},
+				{fromPos: 0, toPos: 0, fromSha: "selected", toSha: "d", kind: STARTS, style: green},
+				{fromPos: 0, toPos: 1, fromSha: "selected", toSha: "e", kind: STARTS, style: green},
+			},
+			prevCommit:  &models.Commit{Sha: "a"},
+			expectedStr: "⏣─╮",
+			expectedStyles: []style.TextStyle{
+				highlightStyle, highlightStyle, highlightStyle,
+			},
+		},
+		{
+			name: "terminating hook and starting hook, prioritise the starting one",
+			pipes: []Pipe{
+				{fromPos: 0, toPos: 0, fromSha: "a", toSha: "b", kind: TERMINATES, style: red},
+				{fromPos: 1, toPos: 0, fromSha: "c", toSha: "b", kind: TERMINATES, style: magenta},
+				{fromPos: 0, toPos: 0, fromSha: "b", toSha: "d", kind: STARTS, style: green},
+				{fromPos: 0, toPos: 1, fromSha: "b", toSha: "e", kind: STARTS, style: green},
+			},
+			prevCommit:  &models.Commit{Sha: "a"},
+			expectedStr: "⏣─│",
+			expectedStyles: []style.TextStyle{
+				green, green, magenta,
+			},
+		},
+		{
+			name: "starting and terminating pipe sharing some space",
+			pipes: []Pipe{
+				{fromPos: 0, toPos: 0, fromSha: "a1", toSha: "a2", kind: TERMINATES, style: red},
+				{fromPos: 0, toPos: 0, fromSha: "a2", toSha: "a3", kind: STARTS, style: yellow},
+				{fromPos: 1, toPos: 1, fromSha: "b1", toSha: "b2", kind: CONTINUES, style: magenta},
+				{fromPos: 3, toPos: 0, fromSha: "e1", toSha: "a2", kind: TERMINATES, style: green},
+				{fromPos: 0, toPos: 2, fromSha: "a2", toSha: "c3", kind: STARTS, style: yellow},
+			},
+			prevCommit:  &models.Commit{Sha: "a1"},
+			expectedStr: "⏣─│─┬─╯",
+			expectedStyles: []style.TextStyle{
+				yellow, yellow, magenta, yellow, yellow, green, green,
+			},
+		},
+		{
+			name: "starting and terminating pipe sharing some space, with selection",
+			pipes: []Pipe{
+				{fromPos: 0, toPos: 0, fromSha: "a1", toSha: "selected", kind: TERMINATES, style: red},
+				{fromPos: 0, toPos: 0, fromSha: "selected", toSha: "a3", kind: STARTS, style: yellow},
+				{fromPos: 1, toPos: 1, fromSha: "b1", toSha: "b2", kind: CONTINUES, style: magenta},
+				{fromPos: 3, toPos: 0, fromSha: "e1", toSha: "selected", kind: TERMINATES, style: green},
+				{fromPos: 0, toPos: 2, fromSha: "selected", toSha: "c3", kind: STARTS, style: yellow},
+			},
+			prevCommit:  &models.Commit{Sha: "a1"},
+			expectedStr: "⏣───╮ ╯",
+			expectedStyles: []style.TextStyle{
+				highlightStyle, highlightStyle, highlightStyle, highlightStyle, highlightStyle, nothing, green,
+			},
+		},
+		{
+			name: "many terminating pipes",
+			pipes: []Pipe{
+				{fromPos: 0, toPos: 0, fromSha: "a1", toSha: "a2", kind: TERMINATES, style: red},
+				{fromPos: 0, toPos: 0, fromSha: "a2", toSha: "a3", kind: STARTS, style: yellow},
+				{fromPos: 1, toPos: 0, fromSha: "b1", toSha: "a2", kind: TERMINATES, style: magenta},
+				{fromPos: 2, toPos: 0, fromSha: "c1", toSha: "a2", kind: TERMINATES, style: green},
+			},
+			prevCommit:  &models.Commit{Sha: "a1"},
+			expectedStr: "⎔─┴─╯",
+			expectedStyles: []style.TextStyle{
+				yellow, magenta, magenta, green, green,
+			},
+		},
+		{
+			name: "starting pipe passing through",
+			pipes: []Pipe{
+				{fromPos: 0, toPos: 0, fromSha: "a1", toSha: "a2", kind: TERMINATES, style: red},
+				{fromPos: 0, toPos: 0, fromSha: "a2", toSha: "a3", kind: STARTS, style: yellow},
+				{fromPos: 0, toPos: 3, fromSha: "a2", toSha: "d3", kind: STARTS, style: yellow},
+				{fromPos: 1, toPos: 1, fromSha: "b1", toSha: "b3", kind: CONTINUES, style: magenta},
+				{fromPos: 2, toPos: 2, fromSha: "c1", toSha: "c3", kind: CONTINUES, style: green},
+			},
+			prevCommit:  &models.Commit{Sha: "a1"},
+			expectedStr: "⏣─│─│─╮",
+			expectedStyles: []style.TextStyle{
+				yellow, yellow, magenta, yellow, green, yellow, yellow,
+			},
+		},
+		{
+			name: "starting and terminating path crossing continuing path",
+			pipes: []Pipe{
+				{fromPos: 0, toPos: 0, fromSha: "a1", toSha: "a2", kind: TERMINATES, style: red},
+				{fromPos: 0, toPos: 0, fromSha: "a2", toSha: "a3", kind: STARTS, style: yellow},
+				{fromPos: 0, toPos: 1, fromSha: "a2", toSha: "b3", kind: STARTS, style: yellow},
+				{fromPos: 1, toPos: 1, fromSha: "b1", toSha: "a2", kind: CONTINUES, style: green},
+				{fromPos: 2, toPos: 0, fromSha: "c1", toSha: "a2", kind: TERMINATES, style: magenta},
+			},
+			prevCommit:  &models.Commit{Sha: "a1"},
+			expectedStr: "⏣─│─╯",
+			expectedStyles: []style.TextStyle{
+				yellow, yellow, green, magenta, magenta,
+			},
+		},
+		{
+			name: "another clash of starting and terminating paths",
+			pipes: []Pipe{
+				{fromPos: 0, toPos: 0, fromSha: "a1", toSha: "a2", kind: TERMINATES, style: red},
+				{fromPos: 0, toPos: 0, fromSha: "a2", toSha: "a3", kind: STARTS, style: yellow},
+				{fromPos: 0, toPos: 1, fromSha: "a2", toSha: "b3", kind: STARTS, style: yellow},
+				{fromPos: 2, toPos: 2, fromSha: "c1", toSha: "c3", kind: CONTINUES, style: green},
+				{fromPos: 3, toPos: 0, fromSha: "d1", toSha: "a2", kind: TERMINATES, style: magenta},
+			},
+			prevCommit:  &models.Commit{Sha: "a1"},
+			expectedStr: "⏣─┬─│─╯",
+			expectedStyles: []style.TextStyle{
+				yellow, yellow, yellow, magenta, green, magenta, magenta,
+			},
+		},
+		{
+			name: "commit whose previous commit is selected",
+			pipes: []Pipe{
+				{fromPos: 0, toPos: 0, fromSha: "selected", toSha: "a2", kind: TERMINATES, style: red},
+				{fromPos: 0, toPos: 0, fromSha: "a2", toSha: "a3", kind: STARTS, style: yellow},
+			},
+			prevCommit:  &models.Commit{Sha: "selected"},
+			expectedStr: "⎔",
+			expectedStyles: []style.TextStyle{
+				yellow,
+			},
+		},
+		{
+			name: "commit whose previous commit is selected and is a merge commit",
+			pipes: []Pipe{
+				{fromPos: 0, toPos: 0, fromSha: "selected", toSha: "a2", kind: TERMINATES, style: red},
+				{fromPos: 1, toPos: 1, fromSha: "selected", toSha: "b3", kind: CONTINUES, style: red},
+			},
+			prevCommit:  &models.Commit{Sha: "selected"},
+			expectedStr: "⎔ │",
+			expectedStyles: []style.TextStyle{
+				highlightStyle, nothing, highlightStyle,
+			},
+		},
+		{
+			name: "commit whose previous commit is selected and is a merge commit, with continuing pipe inbetween",
+			pipes: []Pipe{
+				{fromPos: 0, toPos: 0, fromSha: "selected", toSha: "a2", kind: TERMINATES, style: red},
+				{fromPos: 1, toPos: 1, fromSha: "z1", toSha: "z3", kind: CONTINUES, style: green},
+				{fromPos: 2, toPos: 2, fromSha: "selected", toSha: "b3", kind: CONTINUES, style: red},
+			},
+			prevCommit:  &models.Commit{Sha: "selected"},
+			expectedStr: "⎔ │ │",
+			expectedStyles: []style.TextStyle{
+				highlightStyle, nothing, green, nothing, highlightStyle,
+			},
+		},
+		{
+			name: "when previous commit is selected, not a merge commit, and spawns a continuing pipe",
+			pipes: []Pipe{
+				{fromPos: 0, toPos: 0, fromSha: "a1", toSha: "a2", kind: TERMINATES, style: red},
+				{fromPos: 0, toPos: 0, fromSha: "a2", toSha: "a3", kind: STARTS, style: green},
+				{fromPos: 0, toPos: 1, fromSha: "a2", toSha: "b3", kind: STARTS, style: green},
+				{fromPos: 1, toPos: 0, fromSha: "selected", toSha: "a2", kind: TERMINATES, style: yellow},
+			},
+			prevCommit:  &models.Commit{Sha: "selected"},
+			expectedStr: "⏣─╯",