// Package gitgraph legt een commitgrafiek over branches en tags en // bewaart die in een begrensde geheugencache. package gitgraph import ( "crypto/sha256" "encoding/hex" "fmt" "sort" "strings" ) // DefaultLimit is het aantal recente commits dat in de grafiek past. const DefaultLimit = 40 // PaletteSize is het aantal kleuren voor niet-hoofdbranches. const PaletteSize = 8 // RowH, LaneW en DotR zijn de tekenmaten in pixels. // LaneW en RowH moeten ruim genoeg zijn voor de avatar-knoop (2*DotR). // Corner is de straal van een afgeronde 90-graden bocht. // TextPad is de ruimte tussen de rechterkant van de laatste lane en de tekst. // MsgW is de minimale breedte van de tekstkolom in het paneel. const ( RowH = 28 LaneW = 28 DotR = 9.0 RefW = 78 Corner = 5.0 TextPad = 8 MsgW = 180 ) // Commit is één commit voor de grafiek, met ouders. type Commit struct { SHA, Short, Author, Email, Subject string Unix int64 Parents []string } // Ref is een branch of tag die naar een commit wijst. type Ref struct { Name string SHA string Kind string // "branch" of "tag" } // Label is een verkorte branch- of tagnaam bij een commit. // Ref is de volledige naam (voor de dropdown en de gloed). type Label struct { Name, Ref, Kind, Color, Class string Default bool } // Row is één regel in de gelegde grafiek. type Row struct { Commit Lane int Color string Class string Branch string // branch die deze commit in de grafiek "bezit" Labels []Label Avatar string Initial string UserURL string } // Edge is een lijn van een kind naar een ouder (of het einde van het venster). type Edge struct { FromRow, FromLane, ToRow, ToLane int Color, Branch string } // Graph is een gelegde commitgrafiek, klaar om te tekenen. type Graph struct { Rows []Row Edges []Edge Lanes int Width int // breedte van het SVG-lanedeel Height int TextX int // x waarop de tekstkolom begint, rechts van de laatste lane PanelWidth int // refs + lanes + tekst, in pixels } // Color is de CSS-kleur van een branch. De hoofdbranch is altijd --blue. func Color(branch, defaultBranch string) string { if strings.TrimSpace(branch) != "" && branch == defaultBranch { return "var(--blue)" } return fmt.Sprintf("var(--graph-%d)", hashName(branch)%PaletteSize) } // ColorClass is een CSS-klasse voor dezelfde kleur, veilig in templates // (html/template weigert var(--…) in een style-attribuut). func ColorClass(color string) string { if color == "var(--blue)" { return "is-main" } if strings.HasPrefix(color, "var(--graph-") && strings.HasSuffix(color, ")") { mid := color[len("var(--graph-") : len(color)-1] if len(mid) == 1 && mid[0] >= '0' && mid[0] < '0'+byte(PaletteSize) { return "c" + mid } } return "" } func hashName(name string) int { n := 0 for _, r := range strings.ToLower(strings.TrimSpace(name)) { n = n*33 + int(r) } if n < 0 { n = -n } return n } // Key is de cachesleutel: repo plus de stand van alle branch- en tag-tips. func Key(repoID int64, tips map[string]string, defaultBranch string, limit int) string { if limit < 1 { limit = DefaultLimit } names := make([]string, 0, len(tips)) for n := range tips { names = append(names, n) } sort.Strings(names) var b strings.Builder fmt.Fprintf(&b, "%d\n%d\n%s\n", repoID, limit, defaultBranch) for _, n := range names { b.WriteString(n) b.WriteByte('=') b.WriteString(tips[n]) b.WriteByte('\n') } sum := sha256.Sum256([]byte(b.String())) return fmt.Sprintf("%d:%s", repoID, hex.EncodeToString(sum[:16])) } type laneState struct { sha, color, branch string } // Layout wijst lanes toe en legt lijnen voor merges en forks. // commits staat nieuwste eerst. Ontbrekende ouders lopen tot de onderkant. func Layout(commits []Commit, refs []Ref, defaultBranch string) *Graph { g := &Graph{} if len(commits) == 0 { return g } bySHA := make(map[string]int, len(commits)) for i, c := range commits { bySHA[c.SHA] = i if c.Short == "" && len(c.SHA) >= 10 { commits[i].Short = c.SHA[:10] } } labels := labelsBySHA(refs, defaultBranch) mainline := mainlineSHAs(commits, refs, defaultBranch) var lanes []laneState // Lane 0 is gereserveerd voor de hoofdbranch, zodat een nieuwere // zijtak die kleur en kolom niet inpikt. if def := defaultTip(refs, defaultBranch); def != "" { lanes = []laneState{{sha: def, color: "var(--blue)", branch: defaultBranch}} } g.Rows = make([]Row, len(commits)) occupancy := make([][]laneState, len(commits)+1) for i, c := range commits { incoming := findSHA(lanes, c.SHA) if len(incoming) == 0 { col := colorForCommit(c.SHA, labels, defaultBranch, "") if mainline[c.SHA] { col = "var(--blue)" } incoming = []int{allocLane(&lanes, c.SHA, col, branchForCommit(c.SHA, labels, defaultBranch, mainline, ""))} } primary := pickPrimary(incoming, lanes, c.SHA, labels, defaultBranch) if mainline[c.SHA] { // blijf op lane 0 als die op deze commit wacht for _, li := range incoming { if li == 0 { primary = 0 break } } } row := Row{Commit: commits[i], Lane: primary, Labels: labels[c.SHA]} row.Branch = branchForCommit(c.SHA, labels, defaultBranch, mainline, lanes[primary].branch) if mainline[c.SHA] { row.Color = "var(--blue)" } else { inherit := lanes[primary].color if inherit == "var(--blue)" { inherit = "" } col := colorForCommit(c.SHA, labels, defaultBranch, inherit) if col == "" || col == "var(--blue)" { col = Color(c.SHA, defaultBranch) } row.Color = col } if row.Color == "" { row.Color = "var(--graph-0)" } row.Class = ColorClass(row.Color) lanes[primary].color = row.Color lanes[primary].branch = row.Branch g.Rows[i] = row for _, li := range incoming { if li != primary { lanes[li].sha = "" } } if len(c.Parents) == 0 { lanes[primary].sha = "" } else { first := c.Parents[0] if idx := firstLane(lanes, first); idx >= 0 && idx != primary && !mainline[c.SHA] && !mainline[first] { // zijtak: eerste ouder zit al in een andere lane, daarheen mergen lanes[primary].sha = "" } else { lanes[primary].sha = first } for _, p := range c.Parents[1:] { if firstLane(lanes, p) >= 0 { continue } col := colorForCommit(p, labels, defaultBranch, "") if col == "" || col == "var(--blue)" && !mainline[p] { col = Color(p, defaultBranch) } br := branchForCommit(p, labels, defaultBranch, mainline, "") allocLane(&lanes, p, col, br) } if lanes[primary].sha == "" { if firstLane(lanes, first) < 0 && first != "" { allocLane(&lanes, first, row.Color, row.Branch) } } } occupancy[i+1] = copyLanes(lanes) trimTrailing(&lanes) } occupancy[0] = make([]laneState, len(occupancy[1])) if len(occupancy[0]) > 0 && len(g.Rows) > 0 { // bovenaan: de lane van de nieuwste commit is bezet if g.Rows[0].Lane < len(occupancy[0]) { occupancy[0][g.Rows[0].Lane] = laneState{sha: g.Rows[0].SHA, color: g.Rows[0].Color, branch: g.Rows[0].Branch} } } g.Edges = buildEdges(g.Rows, bySHA, occupancy) g.Lanes = 1 for _, r := range g.Rows { if r.Lane+1 > g.Lanes { g.Lanes = r.Lane + 1 } } for _, e := range g.Edges { if e.FromLane+1 > g.Lanes { g.Lanes = e.FromLane + 1 } if e.ToLane+1 > g.Lanes { g.Lanes = e.ToLane + 1 } } g.Width = g.Lanes * LaneW g.Height = len(g.Rows) * RowH g.TextX = g.Lanes*LaneW + TextPad g.PanelWidth = RefW + g.TextX + MsgW return g } func labelsBySHA(refs []Ref, defaultBranch string) map[string][]Label { out := map[string][]Label{} for _, r := range refs { if r.SHA == "" || r.Name == "" { continue } lb := Label{Name: shortName(r.Name), Ref: r.Name, Kind: r.Kind, Color: Color(r.Name, defaultBranch), Default: r.Kind == "branch" && r.Name == defaultBranch} if r.Kind == "tag" { lb.Color = "var(--muted)" lb.Class = "is-tag" } else { lb.Class = ColorClass(lb.Color) } out[r.SHA] = append(out[r.SHA], lb) } for sha, list := range out { sort.Slice(list, func(i, j int) bool { if list[i].Default != list[j].Default { return list[i].Default } if list[i].Kind != list[j].Kind { return list[i].Kind == "branch" } return list[i].Name < list[j].Name }) out[sha] = list } return out } func shortName(name string) string { const max = 18 if strings.HasPrefix(name, "refs/heads/") { name = strings.TrimPrefix(name, "refs/heads/") } if strings.HasPrefix(name, "refs/tags/") { name = strings.TrimPrefix(name, "refs/tags/") } runes := []rune(name) if len(runes) <= max { return name } return string(runes[:max-1]) + "…" } func colorForCommit(sha string, labels map[string][]Label, defaultBranch, fallback string) string { for _, lb := range labels[sha] { if lb.Default { return "var(--blue)" } } for _, lb := range labels[sha] { if lb.Kind == "branch" { return lb.Color } } if fallback != "" { return fallback } if defaultBranch != "" { return Color(sha, defaultBranch) // stabiel, maar niet --blue } return "var(--graph-0)" } func findSHA(lanes []laneState, sha string) []int { var out []int for i, l := range lanes { if l.sha == sha { out = append(out, i) } } return out } func firstLane(lanes []laneState, sha string) int { for i, l := range lanes { if l.sha == sha { return i } } return -1 } func pickPrimary(incoming []int, lanes []laneState, sha string, labels map[string][]Label, defaultBranch string) int { want := colorForCommit(sha, labels, defaultBranch, "") for _, i := range incoming { if lanes[i].color == want || (want == "var(--blue)" && lanes[i].color == "var(--blue)") { return i } } return incoming[0] } func allocLane(lanes *[]laneState, sha, color, branch string) int { for i, l := range *lanes { if l.sha == "" { (*lanes)[i] = laneState{sha: sha, color: color, branch: branch} return i } } *lanes = append(*lanes, laneState{sha: sha, color: color, branch: branch}) return len(*lanes) - 1 } func branchForCommit(sha string, labels map[string][]Label, defaultBranch string, mainline map[string]bool, fallback string) string { for _, lb := range labels[sha] { if lb.Default && lb.Ref != "" { return lb.Ref } if lb.Default && defaultBranch != "" { return defaultBranch } } for _, lb := range labels[sha] { if lb.Kind == "branch" && lb.Ref != "" { return lb.Ref } if lb.Kind == "branch" && lb.Name != "" { return lb.Name } } if mainline[sha] && defaultBranch != "" { return defaultBranch } return fallback } func copyLanes(lanes []laneState) []laneState { out := make([]laneState, len(lanes)) copy(out, lanes) return out } func trimTrailing(lanes *[]laneState) { n := len(*lanes) for n > 0 && (*lanes)[n-1].sha == "" { n-- } *lanes = (*lanes)[:n] } func buildEdges(rows []Row, bySHA map[string]int, occ [][]laneState) []Edge { var edges []Edge seen := map[[4]int]bool{} add := func(e Edge) { if e.FromRow < 0 || e.ToRow < e.FromRow { return } k := [4]int{e.FromRow, e.FromLane, e.ToRow, e.ToLane} if seen[k] { return } seen[k] = true edges = append(edges, e) } // Van elke commit naar zijn ouders in het venster, of naar de onderkant. for i, r := range rows { if len(r.Parents) == 0 { continue } for pi, p := range r.Parents { toRow, toLane := len(rows)-1, r.Lane if j, ok := bySHA[p]; ok { toRow = j toLane = rows[j].Lane } else { // ouder buiten het venster: zoek de lane waarin we die sha bewaren toLane = r.Lane if i+1 < len(occ) { if idx := firstLane(occ[i+1], p); idx >= 0 { toLane = idx } } toRow = len(rows) - 1 } col, branch := r.Color, r.Branch if pi > 0 { if j, ok := bySHA[p]; ok { if rows[j].Color != "" { col = rows[j].Color } if rows[j].Branch != "" { branch = rows[j].Branch } } } // Tussenliggende verticale stukken volgen de gereserveerde lane. fromLane := r.Lane if pi > 0 && i+1 < len(occ) { if idx := firstLane(occ[i+1], p); idx >= 0 { fromLane = idx // boog vanaf de merge-commit naar de ouder-lane op de volgende rij add(Edge{FromRow: i, FromLane: r.Lane, ToRow: i + 1, ToLane: fromLane, Color: col, Branch: branch}) if toRow > i+1 { add(Edge{FromRow: i + 1, FromLane: fromLane, ToRow: toRow, ToLane: toLane, Color: col, Branch: branch}) } continue } } add(Edge{FromRow: i, FromLane: fromLane, ToRow: toRow, ToLane: toLane, Color: col, Branch: branch}) } } return edges } func defaultTip(refs []Ref, defaultBranch string) string { for _, r := range refs { if r.Kind == "branch" && r.Name == defaultBranch { return r.SHA } } return "" } func mainlineSHAs(commits []Commit, refs []Ref, defaultBranch string) map[string]bool { out := map[string]bool{} tip := defaultTip(refs, defaultBranch) if tip == "" { return out } parents := map[string][]string{} for _, c := range commits { parents[c.SHA] = c.Parents } seen := map[string]bool{} for sha := tip; sha != "" && !seen[sha]; { seen[sha] = true out[sha] = true ps := parents[sha] if len(ps) == 0 { break } sha = ps[0] } return out }