projax/internal/graph/layout.go

// Package graph computes layered top-down DAG layouts for the /graph view.
// It is intentionally minimal — pure Go, no external deps — and tuned for
// m's scale (≤ a few hundred items, single render per request).
//
// Algorithm: longest-path-from-root layering, then deterministic in-layer
// ordering by slug. Positions are assigned on a fixed grid with configurable
// node size and gaps. Multi-parent items resolve to the *maximum* layer
// of any of their parents + 1, so an item that surfaces under both `work`
// and `dev` sits below whichever lineage is longer.
package graph

import (
	"fmt"
	"sort"
)

// Node is the minimal item shape the layout needs. The web handler builds
// these from store.Item; this package never reaches into store/web so it
// stays independently testable.
type Node struct {
	ID       string
	Slug     string
	ParentIDs []string
}

// Pos is a node's computed position in the rendered SVG. Coordinates are in
// the SVG's user-units (pixels at 1:1 viewBox).
type Pos struct {
	X, Y float64
	Layer int
	Order int // 0-based position within the layer
}

// Edge is a parent→child edge with the four points needed for a smooth
// cubic Bézier: (Px,Py) source center-bottom, (Cx,Cy) target center-top,
// plus two control points laid out by the renderer.
type Edge struct {
	ParentID string
	ChildID  string
	SourceX, SourceY float64
	TargetX, TargetY float64
}

// Opts shapes the layout grid.
type Opts struct {
	NodeWidth  float64 // default 120
	NodeHeight float64 // default 40
	HGap       float64 // horizontal gap between sibling nodes (default 24)
	VGap       float64 // vertical gap between layers (default 80)
	MarginX    float64 // left/right canvas margin (default 24)
	MarginY    float64 // top/bottom canvas margin (default 24)
}

// applyDefaults fills zeroed Opts fields.
func (o *Opts) applyDefaults() {
	if o.NodeWidth == 0 {
		o.NodeWidth = 120
	}
	if o.NodeHeight == 0 {
		o.NodeHeight = 40
	}
	if o.HGap == 0 {
		o.HGap = 24
	}
	if o.VGap == 0 {
		o.VGap = 80
	}
	if o.MarginX == 0 {
		o.MarginX = 24
	}
	if o.MarginY == 0 {
		o.MarginY = 24
	}
}

// Layout is the rendered output: per-node positions + a flat list of edges
// + the total canvas size.
type Layout struct {
	Positions     map[string]Pos
	Edges         []Edge
	CanvasWidth   float64
	CanvasHeight  float64
	Layers        [][]string // node IDs per layer, top-down
}

// LayerByLongestPath assigns each node a layer index. Roots (no parents) sit
// at layer 0; every other node sits at `max(layer(parent) for parent in
// parents) + 1`. Cycle-safe by depth-cap (if a cycle exists the trigger
// guard already rejected it on write, but be paranoid in tests too).
func LayerByLongestPath(nodes []Node) (map[string]int, error) {
	byID := make(map[string]Node, len(nodes))
	for _, n := range nodes {
		byID[n.ID] = n
	}
	layer := make(map[string]int, len(nodes))
	const maxDepth = 64

	var visit func(id string, depth int) (int, error)
	visit = func(id string, depth int) (int, error) {
		if depth > maxDepth {
			return 0, fmt.Errorf("graph: depth exceeds %d at %s (cycle?)", maxDepth, id)
		}
		if v, ok := layer[id]; ok {
			return v, nil
		}
		n, ok := byID[id]
		if !ok {
			// Parent referenced but not in input — treat as a synthetic root.
			layer[id] = 0
			return 0, nil
		}
		if len(n.ParentIDs) == 0 {
			layer[id] = 0
			return 0, nil
		}
		best := -1
		for _, pid := range n.ParentIDs {
			pl, err := visit(pid, depth+1)
			if err != nil {
				return 0, err
			}
			if pl+1 > best {
				best = pl + 1
			}
		}
		layer[id] = best
		return best, nil
	}

	for _, n := range nodes {
		if _, err := visit(n.ID, 0); err != nil {
			return nil, err
		}
	}
	return layer, nil
}

// OrderInLayer groups nodes by layer index and sorts each layer
// alphabetically by slug for stable rendering.
func OrderInLayer(nodes []Node, layers map[string]int) [][]string {
	if len(layers) == 0 {
		return nil
	}
	max := 0
	for _, l := range layers {
		if l > max {
			max = l
		}
	}
	byID := make(map[string]Node, len(nodes))
	for _, n := range nodes {
		byID[n.ID] = n
	}
	out := make([][]string, max+1)
	for id, l := range layers {
		out[l] = append(out[l], id)
	}
	for i := range out {
		sort.Slice(out[i], func(a, b int) bool {
			return byID[out[i][a]].Slug < byID[out[i][b]].Slug
		})
	}
	return out
}

// Compute produces a full Layout from raw nodes. Pure function — callers can
// reuse it from handler tests or scripts without HTTP plumbing.
func Compute(nodes []Node, opts Opts) (*Layout, error) {
	opts.applyDefaults()
	if len(nodes) == 0 {
		return &Layout{
			Positions:    map[string]Pos{},
			CanvasWidth:  opts.NodeWidth + 2*opts.MarginX,
			CanvasHeight: opts.NodeHeight + 2*opts.MarginY,
		}, nil
	}

	layers, err := LayerByLongestPath(nodes)
	if err != nil {
		return nil, err
	}
	ordered := OrderInLayer(nodes, layers)

	widest := 0
	for _, layer := range ordered {
		if len(layer) > widest {
			widest = len(layer)
		}
	}
	canvasW := opts.MarginX*2 + float64(widest)*opts.NodeWidth + float64(widest-1)*opts.HGap
	if widest <= 1 {
		canvasW = opts.MarginX*2 + opts.NodeWidth
	}

	positions := make(map[string]Pos, len(nodes))
	byID := make(map[string]Node, len(nodes))
	for _, n := range nodes {
		byID[n.ID] = n
	}
	for li, layer := range ordered {
		rowW := float64(len(layer))*opts.NodeWidth + float64(len(layer)-1)*opts.HGap
		if len(layer) <= 1 {
			rowW = opts.NodeWidth
		}
		startX := (canvasW - rowW) / 2
		for i, id := range layer {
			x := startX + float64(i)*(opts.NodeWidth+opts.HGap)
			y := opts.MarginY + float64(li)*(opts.NodeHeight+opts.VGap)
			positions[id] = Pos{X: x, Y: y, Layer: li, Order: i}
		}
	}
	canvasH := opts.MarginY*2 + float64(len(ordered))*opts.NodeHeight + float64(len(ordered)-1)*opts.VGap
	if len(ordered) <= 1 {
		canvasH = opts.MarginY*2 + opts.NodeHeight
	}

	// Edges: one per (parent, child) pair, source = parent center-bottom,
	// target = child center-top. Multi-parent items emit one edge per parent.
	var edges []Edge
	for _, n := range nodes {
		cp, ok := positions[n.ID]
		if !ok {
			continue
		}
		for _, pid := range n.ParentIDs {
			pp, ok := positions[pid]
			if !ok {
				continue
			}
			edges = append(edges, Edge{
				ParentID: pid,
				ChildID:  n.ID,
				SourceX:  pp.X + opts.NodeWidth/2,
				SourceY:  pp.Y + opts.NodeHeight,
				TargetX:  cp.X + opts.NodeWidth/2,
				TargetY:  cp.Y,
			})
		}
	}
	// Stable edge order for deterministic rendering.
	sort.Slice(edges, func(i, j int) bool {
		if edges[i].ParentID != edges[j].ParentID {
			return edges[i].ParentID < edges[j].ParentID
		}
		return edges[i].ChildID < edges[j].ChildID
	})

	return &Layout{
		Positions:    positions,
		Edges:        edges,
		CanvasWidth:  canvasW,
		CanvasHeight: canvasH,
		Layers:       ordered,
	}, nil
}