| 1 | // Package gitgraph legt een commitgrafiek over branches en tags en |
| 2 | // bewaart die in een begrensde geheugencache. |
| 3 | package gitgraph |
| 4 | |
| 5 | import ( |
| 6 | "crypto/sha256" |
| 7 | "encoding/hex" |
| 8 | "fmt" |
| 9 | "sort" |
| 10 | "strings" |
| 11 | ) |
| 12 | |
| 13 | // DefaultLimit is het aantal recente commits dat in de grafiek past. |
| 14 | const DefaultLimit = 40 |
| 15 | |
| 16 | // PaletteSize is het aantal kleuren voor niet-hoofdbranches. |
| 17 | const PaletteSize = 8 |
| 18 | |
| 19 | // RowH, LaneW en DotR zijn de tekenmaten in pixels. |
| 20 | const ( |
| 21 | RowH = 22 |
| 22 | LaneW = 12 |
| 23 | DotR = 4.0 |
| 24 | RefW = 78 |
| 25 | ) |
| 26 | |
| 27 | // Commit is één commit voor de grafiek, met ouders. |
| 28 | type Commit struct { |
| 29 | SHA, Short, Author, Email, Subject string |
| 30 | Unix int64 |
| 31 | Parents []string |
| 32 | } |
| 33 | |
| 34 | // Ref is een branch of tag die naar een commit wijst. |
| 35 | type Ref struct { |
| 36 | Name string |
| 37 | SHA string |
| 38 | Kind string // "branch" of "tag" |
| 39 | } |
| 40 | |
| 41 | // Label is een verkorte branch- of tagnaam bij een commit. |
| 42 | type Label struct { |
| 43 | Name, Kind, Color, Class string |
| 44 | Default bool |
| 45 | } |
| 46 | |
| 47 | // Row is één regel in de gelegde grafiek. |
| 48 | type Row struct { |
| 49 | Commit |
| 50 | Lane int |
| 51 | Color string |
| 52 | Class string |
| 53 | Labels []Label |
| 54 | Avatar string |
| 55 | Initial string |
| 56 | UserURL string |
| 57 | } |
| 58 | |
| 59 | // Edge is een lijn van een kind naar een ouder (of het einde van het venster). |
| 60 | type Edge struct { |
| 61 | FromRow, FromLane, ToRow, ToLane int |
| 62 | Color string |
| 63 | } |
| 64 | |
| 65 | // Graph is een gelegde commitgrafiek, klaar om te tekenen. |
| 66 | type Graph struct { |
| 67 | Rows []Row |
| 68 | Edges []Edge |
| 69 | Lanes int |
| 70 | Width int |
| 71 | Height int |
| 72 | } |
| 73 | |
| 74 | // Color is de CSS-kleur van een branch. De hoofdbranch is altijd --blue. |
| 75 | func Color(branch, defaultBranch string) string { |
| 76 | if strings.TrimSpace(branch) != "" && branch == defaultBranch { |
| 77 | return "var(--blue)" |
| 78 | } |
| 79 | return fmt.Sprintf("var(--graph-%d)", hashName(branch)%PaletteSize) |
| 80 | } |
| 81 | |
| 82 | // ColorClass is een CSS-klasse voor dezelfde kleur, veilig in templates |
| 83 | // (html/template weigert var(--…) in een style-attribuut). |
| 84 | func ColorClass(color string) string { |
| 85 | if color == "var(--blue)" { |
| 86 | return "is-main" |
| 87 | } |
| 88 | if strings.HasPrefix(color, "var(--graph-") && strings.HasSuffix(color, ")") { |
| 89 | mid := color[len("var(--graph-") : len(color)-1] |
| 90 | if len(mid) == 1 && mid[0] >= '0' && mid[0] < '0'+byte(PaletteSize) { |
| 91 | return "c" + mid |
| 92 | } |
| 93 | } |
| 94 | return "" |
| 95 | } |
| 96 | |
| 97 | func hashName(name string) int { |
| 98 | n := 0 |
| 99 | for _, r := range strings.ToLower(strings.TrimSpace(name)) { |
| 100 | n = n*33 + int(r) |
| 101 | } |
| 102 | if n < 0 { |
| 103 | n = -n |
| 104 | } |
| 105 | return n |
| 106 | } |
| 107 | |
| 108 | // Key is de cachesleutel: repo plus de stand van alle branch- en tag-tips. |
| 109 | func Key(repoID int64, tips map[string]string, defaultBranch string, limit int) string { |
| 110 | if limit < 1 { |
| 111 | limit = DefaultLimit |
| 112 | } |
| 113 | names := make([]string, 0, len(tips)) |
| 114 | for n := range tips { |
| 115 | names = append(names, n) |
| 116 | } |
| 117 | sort.Strings(names) |
| 118 | var b strings.Builder |
| 119 | fmt.Fprintf(&b, "%d\n%d\n%s\n", repoID, limit, defaultBranch) |
| 120 | for _, n := range names { |
| 121 | b.WriteString(n) |
| 122 | b.WriteByte('=') |
| 123 | b.WriteString(tips[n]) |
| 124 | b.WriteByte('\n') |
| 125 | } |
| 126 | sum := sha256.Sum256([]byte(b.String())) |
| 127 | return fmt.Sprintf("%d:%s", repoID, hex.EncodeToString(sum[:16])) |
| 128 | } |
| 129 | |
| 130 | type laneState struct { |
| 131 | sha string |
| 132 | color string |
| 133 | } |
| 134 | |
| 135 | // Layout wijst lanes toe en legt lijnen voor merges en forks. |
| 136 | // commits staat nieuwste eerst. Ontbrekende ouders lopen tot de onderkant. |
| 137 | func Layout(commits []Commit, refs []Ref, defaultBranch string) *Graph { |
| 138 | g := &Graph{} |
| 139 | if len(commits) == 0 { |
| 140 | return g |
| 141 | } |
| 142 | bySHA := make(map[string]int, len(commits)) |
| 143 | for i, c := range commits { |
| 144 | bySHA[c.SHA] = i |
| 145 | if c.Short == "" && len(c.SHA) >= 10 { |
| 146 | commits[i].Short = c.SHA[:10] |
| 147 | } |
| 148 | } |
| 149 | labels := labelsBySHA(refs, defaultBranch) |
| 150 | mainline := mainlineSHAs(commits, refs, defaultBranch) |
| 151 | |
| 152 | var lanes []laneState |
| 153 | // Lane 0 is gereserveerd voor de hoofdbranch, zodat een nieuwere |
| 154 | // zijtak die kleur en kolom niet inpikt. |
| 155 | if def := defaultTip(refs, defaultBranch); def != "" { |
| 156 | lanes = []laneState{{sha: def, color: "var(--blue)"}} |
| 157 | } |
| 158 | g.Rows = make([]Row, len(commits)) |
| 159 | occupancy := make([][]laneState, len(commits)+1) |
| 160 | |
| 161 | for i, c := range commits { |
| 162 | incoming := findSHA(lanes, c.SHA) |
| 163 | if len(incoming) == 0 { |
| 164 | col := colorForCommit(c.SHA, labels, defaultBranch, "") |
| 165 | if mainline[c.SHA] { |
| 166 | col = "var(--blue)" |
| 167 | } |
| 168 | incoming = []int{allocLane(&lanes, c.SHA, col)} |
| 169 | } |
| 170 | primary := pickPrimary(incoming, lanes, c.SHA, labels, defaultBranch) |
| 171 | if mainline[c.SHA] { |
| 172 | // blijf op lane 0 als die op deze commit wacht |
| 173 | for _, li := range incoming { |
| 174 | if li == 0 { |
| 175 | primary = 0 |
| 176 | break |
| 177 | } |
| 178 | } |
| 179 | } |
| 180 | row := Row{Commit: commits[i], Lane: primary, Labels: labels[c.SHA]} |
| 181 | if mainline[c.SHA] { |
| 182 | row.Color = "var(--blue)" |
| 183 | } else { |
| 184 | inherit := lanes[primary].color |
| 185 | if inherit == "var(--blue)" { |
| 186 | inherit = "" |
| 187 | } |
| 188 | col := colorForCommit(c.SHA, labels, defaultBranch, inherit) |
| 189 | if col == "" || col == "var(--blue)" { |
| 190 | col = Color(c.SHA, defaultBranch) |
| 191 | } |
| 192 | row.Color = col |
| 193 | } |
| 194 | if row.Color == "" { |
| 195 | row.Color = "var(--graph-0)" |
| 196 | } |
| 197 | row.Class = ColorClass(row.Color) |
| 198 | lanes[primary].color = row.Color |
| 199 | g.Rows[i] = row |
| 200 | |
| 201 | for _, li := range incoming { |
| 202 | if li != primary { |
| 203 | lanes[li].sha = "" |
| 204 | } |
| 205 | } |
| 206 | if len(c.Parents) == 0 { |
| 207 | lanes[primary].sha = "" |
| 208 | } else { |
| 209 | first := c.Parents[0] |
| 210 | if idx := firstLane(lanes, first); idx >= 0 && idx != primary && !mainline[c.SHA] && !mainline[first] { |
| 211 | // zijtak: eerste ouder zit al in een andere lane, daarheen mergen |
| 212 | lanes[primary].sha = "" |
| 213 | } else { |
| 214 | lanes[primary].sha = first |
| 215 | } |
| 216 | for _, p := range c.Parents[1:] { |
| 217 | if firstLane(lanes, p) >= 0 { |
| 218 | continue |
| 219 | } |
| 220 | col := colorForCommit(p, labels, defaultBranch, "") |
| 221 | if col == "" || col == "var(--blue)" && !mainline[p] { |
| 222 | col = Color(p, defaultBranch) |
| 223 | } |
| 224 | allocLane(&lanes, p, col) |
| 225 | } |
| 226 | if lanes[primary].sha == "" { |
| 227 | if firstLane(lanes, first) < 0 && first != "" { |
| 228 | allocLane(&lanes, first, row.Color) |
| 229 | } |
| 230 | } |
| 231 | } |
| 232 | occupancy[i+1] = copyLanes(lanes) |
| 233 | trimTrailing(&lanes) |
| 234 | } |
| 235 | occupancy[0] = make([]laneState, len(occupancy[1])) |
| 236 | if len(occupancy[0]) > 0 && len(g.Rows) > 0 { |
| 237 | // bovenaan: de lane van de nieuwste commit is bezet |
| 238 | if g.Rows[0].Lane < len(occupancy[0]) { |
| 239 | occupancy[0][g.Rows[0].Lane] = laneState{sha: g.Rows[0].SHA, color: g.Rows[0].Color} |
| 240 | } |
| 241 | } |
| 242 | g.Edges = buildEdges(g.Rows, bySHA, occupancy) |
| 243 | g.Lanes = 1 |
| 244 | for _, r := range g.Rows { |
| 245 | if r.Lane+1 > g.Lanes { |
| 246 | g.Lanes = r.Lane + 1 |
| 247 | } |
| 248 | } |
| 249 | for _, e := range g.Edges { |
| 250 | if e.FromLane+1 > g.Lanes { |
| 251 | g.Lanes = e.FromLane + 1 |
| 252 | } |
| 253 | if e.ToLane+1 > g.Lanes { |
| 254 | g.Lanes = e.ToLane + 1 |
| 255 | } |
| 256 | } |
| 257 | g.Width = g.Lanes * LaneW |
| 258 | g.Height = len(g.Rows) * RowH |
| 259 | return g |
| 260 | } |
| 261 | |
| 262 | func labelsBySHA(refs []Ref, defaultBranch string) map[string][]Label { |
| 263 | out := map[string][]Label{} |
| 264 | for _, r := range refs { |
| 265 | if r.SHA == "" || r.Name == "" { |
| 266 | continue |
| 267 | } |
| 268 | lb := Label{Name: shortName(r.Name), Kind: r.Kind, Color: Color(r.Name, defaultBranch), Default: r.Kind == "branch" && r.Name == defaultBranch} |
| 269 | if r.Kind == "tag" { |
| 270 | lb.Color = "var(--muted)" |
| 271 | lb.Class = "is-tag" |
| 272 | } else { |
| 273 | lb.Class = ColorClass(lb.Color) |
| 274 | } |
| 275 | out[r.SHA] = append(out[r.SHA], lb) |
| 276 | } |
| 277 | for sha, list := range out { |
| 278 | sort.Slice(list, func(i, j int) bool { |
| 279 | if list[i].Default != list[j].Default { |
| 280 | return list[i].Default |
| 281 | } |
| 282 | if list[i].Kind != list[j].Kind { |
| 283 | return list[i].Kind == "branch" |
| 284 | } |
| 285 | return list[i].Name < list[j].Name |
| 286 | }) |
| 287 | out[sha] = list |
| 288 | } |
| 289 | return out |
| 290 | } |
| 291 | |
| 292 | func shortName(name string) string { |
| 293 | const max = 18 |
| 294 | if strings.HasPrefix(name, "refs/heads/") { |
| 295 | name = strings.TrimPrefix(name, "refs/heads/") |
| 296 | } |
| 297 | if strings.HasPrefix(name, "refs/tags/") { |
| 298 | name = strings.TrimPrefix(name, "refs/tags/") |
| 299 | } |
| 300 | runes := []rune(name) |
| 301 | if len(runes) <= max { |
| 302 | return name |
| 303 | } |
| 304 | return string(runes[:max-1]) + "…" |
| 305 | } |
| 306 | |
| 307 | func colorForCommit(sha string, labels map[string][]Label, defaultBranch, fallback string) string { |
| 308 | for _, lb := range labels[sha] { |
| 309 | if lb.Default { |
| 310 | return "var(--blue)" |
| 311 | } |
| 312 | } |
| 313 | for _, lb := range labels[sha] { |
| 314 | if lb.Kind == "branch" { |
| 315 | return lb.Color |
| 316 | } |
| 317 | } |
| 318 | if fallback != "" { |
| 319 | return fallback |
| 320 | } |
| 321 | if defaultBranch != "" { |
| 322 | return Color(sha, defaultBranch) // stabiel, maar niet --blue |
| 323 | } |
| 324 | return "var(--graph-0)" |
| 325 | } |
| 326 | |
| 327 | func findSHA(lanes []laneState, sha string) []int { |
| 328 | var out []int |
| 329 | for i, l := range lanes { |
| 330 | if l.sha == sha { |
| 331 | out = append(out, i) |
| 332 | } |
| 333 | } |
| 334 | return out |
| 335 | } |
| 336 | |
| 337 | func firstLane(lanes []laneState, sha string) int { |
| 338 | for i, l := range lanes { |
| 339 | if l.sha == sha { |
| 340 | return i |
| 341 | } |
| 342 | } |
| 343 | return -1 |
| 344 | } |
| 345 | |
| 346 | func pickPrimary(incoming []int, lanes []laneState, sha string, labels map[string][]Label, defaultBranch string) int { |
| 347 | want := colorForCommit(sha, labels, defaultBranch, "") |
| 348 | for _, i := range incoming { |
| 349 | if lanes[i].color == want || (want == "var(--blue)" && lanes[i].color == "var(--blue)") { |
| 350 | return i |
| 351 | } |
| 352 | } |
| 353 | return incoming[0] |
| 354 | } |
| 355 | |
| 356 | func allocLane(lanes *[]laneState, sha, color string) int { |
| 357 | for i, l := range *lanes { |
| 358 | if l.sha == "" { |
| 359 | (*lanes)[i] = laneState{sha: sha, color: color} |
| 360 | return i |
| 361 | } |
| 362 | } |
| 363 | *lanes = append(*lanes, laneState{sha: sha, color: color}) |
| 364 | return len(*lanes) - 1 |
| 365 | } |
| 366 | |
| 367 | func copyLanes(lanes []laneState) []laneState { |
| 368 | out := make([]laneState, len(lanes)) |
| 369 | copy(out, lanes) |
| 370 | return out |
| 371 | } |
| 372 | |
| 373 | func trimTrailing(lanes *[]laneState) { |
| 374 | n := len(*lanes) |
| 375 | for n > 0 && (*lanes)[n-1].sha == "" { |
| 376 | n-- |
| 377 | } |
| 378 | *lanes = (*lanes)[:n] |
| 379 | } |
| 380 | |
| 381 | func buildEdges(rows []Row, bySHA map[string]int, occ [][]laneState) []Edge { |
| 382 | var edges []Edge |
| 383 | seen := map[[4]int]bool{} |
| 384 | add := func(e Edge) { |
| 385 | if e.FromRow < 0 || e.ToRow < e.FromRow { |
| 386 | return |
| 387 | } |
| 388 | k := [4]int{e.FromRow, e.FromLane, e.ToRow, e.ToLane} |
| 389 | if seen[k] { |
| 390 | return |
| 391 | } |
| 392 | seen[k] = true |
| 393 | edges = append(edges, e) |
| 394 | } |
| 395 | // Van elke commit naar zijn ouders in het venster, of naar de onderkant. |
| 396 | for i, r := range rows { |
| 397 | if len(r.Parents) == 0 { |
| 398 | continue |
| 399 | } |
| 400 | for pi, p := range r.Parents { |
| 401 | toRow, toLane := len(rows)-1, r.Lane |
| 402 | if j, ok := bySHA[p]; ok { |
| 403 | toRow = j |
| 404 | toLane = rows[j].Lane |
| 405 | } else { |
| 406 | // ouder buiten het venster: zoek de lane waarin we die sha bewaren |
| 407 | toLane = r.Lane |
| 408 | if i+1 < len(occ) { |
| 409 | if idx := firstLane(occ[i+1], p); idx >= 0 { |
| 410 | toLane = idx |
| 411 | } |
| 412 | } |
| 413 | toRow = len(rows) - 1 |
| 414 | } |
| 415 | col := r.Color |
| 416 | if pi == 0 && r.Color != "" { |
| 417 | col = r.Color |
| 418 | } |
| 419 | // Tussenliggende verticale stukken volgen de gereserveerde lane. |
| 420 | fromLane := r.Lane |
| 421 | if pi > 0 && i+1 < len(occ) { |
| 422 | if idx := firstLane(occ[i+1], p); idx >= 0 { |
| 423 | fromLane = idx |
| 424 | // boog vanaf de merge-commit naar de ouder-lane op de volgende rij |
| 425 | add(Edge{FromRow: i, FromLane: r.Lane, ToRow: i + 1, ToLane: fromLane, Color: col}) |
| 426 | if toRow > i+1 { |
| 427 | add(Edge{FromRow: i + 1, FromLane: fromLane, ToRow: toRow, ToLane: toLane, Color: col}) |
| 428 | } |
| 429 | continue |
| 430 | } |
| 431 | } |
| 432 | add(Edge{FromRow: i, FromLane: fromLane, ToRow: toRow, ToLane: toLane, Color: col}) |
| 433 | } |
| 434 | } |
| 435 | return edges |
| 436 | } |
| 437 | |
| 438 | func defaultTip(refs []Ref, defaultBranch string) string { |
| 439 | for _, r := range refs { |
| 440 | if r.Kind == "branch" && r.Name == defaultBranch { |
| 441 | return r.SHA |
| 442 | } |
| 443 | } |
| 444 | return "" |
| 445 | } |
| 446 | |
| 447 | func mainlineSHAs(commits []Commit, refs []Ref, defaultBranch string) map[string]bool { |
| 448 | out := map[string]bool{} |
| 449 | tip := defaultTip(refs, defaultBranch) |
| 450 | if tip == "" { |
| 451 | return out |
| 452 | } |
| 453 | parents := map[string][]string{} |
| 454 | for _, c := range commits { |
| 455 | parents[c.SHA] = c.Parents |
| 456 | } |
| 457 | seen := map[string]bool{} |
| 458 | for sha := tip; sha != "" && !seen[sha]; { |
| 459 | seen[sha] = true |
| 460 | out[sha] = true |
| 461 | ps := parents[sha] |
| 462 | if len(ps) == 0 { |
| 463 | break |
| 464 | } |
| 465 | sha = ps[0] |
| 466 | } |
| 467 | return out |
| 468 | } |