package web
import (
"sort"
"strings"
)
// treeMaxColumns is the most columns the tree axis draws: about two
// pixels each across the plot. Past it a column is narrower than a
// pixel, so the reader sees nothing more and the browser builds tens of
// thousands of marks for it (netbsd-src drew 19,549 columns, 8 MB).
const treeMaxColumns = 450
// foldColumns fits a window's paths to limit columns. It starts from
// the top-level directories and splits the busiest column into its
// children while the split still fits, so the detail goes where the
// work was: a directory nobody touched stays one column, a hot one
// opens down to its files. A folded directory is named with a trailing
// slash, as the index names the rows it folds itself. Each touch moves
// to its column; touches that land on the same (day, column, person)
// become one. A tree too wide even at its top level is drawn in runs of
// neighbouring columns. It reports whether anything was folded.
func foldColumns(act activityOut, limit int) (activityOut, bool) {
if len(act.Paths) <= limit || limit < 1 {
return act, false
}
parts := make([][]string, len(act.Paths))
for i, p := range act.Paths {
parts[i] = strings.Split(strings.TrimSuffix(p, "/"), "/")
}
weight := make([]int, len(act.Paths))
for _, t := range act.Touches {
if t.Path >= 0 && t.Path < len(weight) && t.Inherited == 0 {
weight[t.Path]++
}
}
// A column is a prefix of depth components and the paths under it;
// a path no deeper than its column's depth is the column itself.
type column struct {
depth int
members []int
weight int
}
group := func(members []int, depth int) []column {
var out []column
at := map[string]int{}
for _, i := range members {
k := colKey(act.Paths[i], parts[i], depth)
c, ok := at[k]
if !ok {
c = len(out)
at[k] = c
out = append(out, column{depth: depth})
}
out[c].members = append(out[c].members, i)
out[c].weight += weight[i]
}
return out
}
all := make([]int, len(act.Paths))
for i := range all {
all[i] = i
}
cols := group(all, 1)
if len(cols) <= limit {
for {
// The busiest column that still opens and whose children fit.
best, bestKids := -1, []column(nil)
for c, col := range cols {
if len(col.members) < 2 || (best >= 0 && col.weight <= cols[best].weight) {
continue
}
kids := group(col.members, col.depth+1)
for len(kids) == 1 && kids[0].depth < maxDepth(parts, kids[0].members) {
kids = group(kids[0].members, kids[0].depth+1)
}
if len(kids) < 2 || len(cols)-1+len(kids) > limit {
continue
}
best, bestKids = c, kids
}
if best < 0 {
break
}
cols = append(cols[:best], append(bestKids, cols[best+1:]...)...)
}
}
colOf := make([]int, len(act.Paths))
var names []string
if len(cols) <= limit {
// Order the columns as the index orders paths: by the first
// path in each, which keeps a directory's columns together.
sort.SliceStable(cols, func(a, b int) bool { return cols[a].members[0] < cols[b].members[0] })
for c, col := range cols {
first := col.members[0]
names = append(names, colKey(act.Paths[first], parts[first], col.depth))
for _, i := range col.members {
colOf[i] = c
}
}
} else {
run := (len(act.Paths) + limit - 1) / limit
for i := range act.Paths {
if i%run == 0 {
names = append(names, act.Paths[i])
}
colOf[i] = i / run
}
}
type mark struct{ day, col, author, inherited int }
seen := map[mark]struct{}{}
touches := make([]activityTouch, 0, len(act.Touches))
for _, t := range act.Touches {
if t.Path < 0 || t.Path >= len(colOf) {
continue
}
m := mark{t.Day, colOf[t.Path], t.Author, t.Inherited}
if _, dup := seen[m]; dup {
continue
}
seen[m] = struct{}{}
t.Path = m.col
touches = append(touches, t)
}
act.Paths, act.Touches = names, touches
return act, true
}
// colKey names path i's column at depth: the path itself when it is no
// deeper, else its first depth components as a directory.
func colKey(path string, parts []string, depth int) string {
if len(parts) <= depth {
return path
}
return strings.Join(parts[:depth], "/") + "/"
}
func maxDepth(parts [][]string, members []int) int {
d := 0
for _, i := range members {
d = max(d, len(parts[i]))
}
return d
}
// colDir is the directory a column belongs to, for the bands: a folded
// directory column belongs to its parent, as a file does.
func colDir(col string) string { return dirOf(strings.TrimSuffix(col, "/")) }