fathom/internal/insights/crystallize.go

package insights

import (
	"context"
	"fmt"
	"sort"
	"strings"
	"time"
)

// Crystallize finds work that has become routine.
//
// Two signals, because they catch different things. Sequence mining finds
// repeated *mechanics* — the same ordered run of tool calls, whatever it was
// asked for. Prompt clustering finds repeated *requests* — the same thing asked
// several times, however it was carried out. A habit worth capturing usually
// shows up in one or the other; the ones that show up in both are the strongest
// candidates.
type Crystallize struct {
	// MinRuns is how many times a sequence must recur before it is worth
	// mentioning. Two is a coincidence.
	MinRuns int

	// MinLen is the shortest sequence considered. A single repeated tool call
	// is not a workflow, it is just a tool.
	MinLen int

	// MaxLen bounds the window scanned. Long sequences are rarely repeated
	// exactly and the short ones inside them are the reusable part anyway.
	MaxLen int

	// PromptSimilarity is the Jaccard threshold for calling two prompts near
	// duplicates, used when no embedding model is available.
	PromptSimilarity float64

	lastMethod ClusterMethod

	// Embedder, when set, clusters prompts by meaning rather than by shared
	// vocabulary. Nil is the ordinary case and uses MinHash.
	Embedder Embedder
}

// lastMethod is set by the most recent run, for reporting.
func NewCrystallize() *Crystallize {
	return &Crystallize{
		MinRuns:          3,
		MinLen:           3,
		MaxLen:           6,
		PromptSimilarity: 0.55,
	}
}

func (c *Crystallize) Name() string { return "crystallize" }

func (c *Crystallize) Detect(traces []TraceFacts) []Insight {
	var out []Insight
	out = append(out, c.detectSequences(traces)...)
	out = append(out, c.detectRepeatedAsks(traces)...)
	return out
}

// LastMethod reports how the most recent prompt clustering was done, so the UI
// can say whether a finding came from shared wording or shared meaning.
func (c *Crystallize) LastMethod() ClusterMethod {
	if c.lastMethod == "" {
		return MethodMinHash
	}
	return c.lastMethod
}

// occurrence is one appearance of a sequence.
type occurrence struct {
	traceIdx int
	at       int
	cost     float64
	wall     int64
}

// detectSequences mines frequent contiguous runs of tool calls.
//
// Contiguous n-grams rather than the general subsequence mining PrefixSpan
// does. The distinction matters for what is being recommended: a script has to
// perform steps in order with nothing interesting between them, so a gapped
// subsequence — grep, then forty other things, then test — is not something you
// can wrap. Restricting to contiguous windows also bounds the work to
// O(calls × MaxLen) with no candidate generation, which at these sizes is
// immediate.
func (c *Crystallize) detectSequences(traces []TraceFacts) []Insight {
	occurrences := map[string][]occurrence{}

	for ti := range traces {
		t := &traces[ti]
		if len(t.Calls) < c.MinLen {
			continue
		}
		// A trace is credited at most once per distinct sequence, so a loop
		// that repeats the same three steps ten times within one run counts as
		// one trace, not ten. Without this, a single pathological trace
		// manufactures a "pattern".
		seenHere := map[string]bool{}

		perCall := t.CostUSD / float64(max(1, len(t.Calls)))
		for n := c.MinLen; n <= c.MaxLen; n++ {
			for i := 0; i+n <= len(t.Calls); i++ {
				win := t.Calls[i : i+n]
				if !worthCapturing(win) {
					continue
				}
				key := sequenceKey(win)
				if seenHere[key] {
					continue
				}
				seenHere[key] = true

				var wall int64
				for _, cl := range win {
					wall += cl.DurMicros
				}
				occurrences[key] = append(occurrences[key], occurrence{
					traceIdx: ti, at: i,
					cost: perCall * float64(n),
					wall: wall,
				})
			}
		}
	}

	var cands []candidate
	for key, occs := range occurrences {
		if distinctTraces(occs) < c.MinRuns {
			continue
		}
		cands = append(cands, candidate{key, occs})
	}

	// Rank by how often the pattern recurs, then by length.
	//
	// Length-first was wrong and produced exactly the wrong answer: a five-step
	// variant seen three times outranked the four-step core seen nine times, so
	// the core was suppressed as an overlap of its own variant. How often
	// something recurs is what makes it a habit; how long it is only breaks
	// ties.
	sort.SliceStable(cands, func(i, j int) bool {
		ri, rj := distinctTraces(cands[i].occs), distinctTraces(cands[j].occs)
		if ri != rj {
			return ri > rj
		}
		li, lj := len(strings.Split(cands[i].key, " → ")), len(strings.Split(cands[j].key, " → "))
		return li > lj
	})

	var kept []candidate
	for _, cand := range cands {
		if restates(cand, kept, c.MinLen) {
			continue
		}
		kept = append(kept, cand)
	}

	var out []Insight
	for _, cand := range kept {
		steps := strings.Split(cand.key, " → ")
		runs := distinctTraces(cand.occs)

		var cost float64
		var wall int64
		for _, o := range cand.occs {
			cost += o.cost
			wall += o.wall
		}

		ins := Insight{
			ID:       "crystallize/seq/" + slug(cand.key),
			Theme:    ThemeCrystallize,
			Severity: severityFor(cost, runs),
			Title: fmt.Sprintf("%s — the same %d steps in %d runs",
				strings.Join(toolNames(steps), " → "), len(steps), runs),
			Occurrences: runs,
			CostUSD:     cost,
			WallMicros:  wall,
			Steps:       steps,
		}
		ins.Body = fmt.Sprintf(
			"This exact run of %d steps appeared in %d separate %s, costing about %s and %s of wall time in total. "+
				"The arguments changed each time; the shape did not.",
			len(steps), runs, plural(runs, "trace", "traces"), money(cost), shortDur(wall))
		ins.Suggestion = "A short script or a throwaway skill covering these steps would collapse them into one call. " +
			"It does not need to be durable — patterns like this usually belong to whatever you are working on this fortnight, " +
			"so it is worth writing cheaply and deleting when the work moves on."

		ins.Evidence, ins.FirstSeen, ins.LastSeen = evidenceFor(traces, cand.occs, steps)
		out = append(out, ins)
	}
	return out
}

// worthCapturing rejects windows that would produce a useless recommendation.
func worthCapturing(win []ToolCall) bool {
	// A run of one repeated tool is not a workflow. Reading four files in a row
	// is reading, not a procedure worth scripting.
	distinct := map[string]bool{}
	for _, c := range win {
		distinct[c.Name] = true
	}
	if len(distinct) < 2 {
		return false
	}
	// A sequence containing an unresolvable step cannot be described usefully.
	for _, c := range win {
		if strings.HasSuffix(c.Signature, ":?") || c.Signature == "" {
			return false
		}
	}
	return true
}

func sequenceKey(win []ToolCall) string {
	parts := make([]string, len(win))
	for i, c := range win {
		parts[i] = c.Signature
	}
	return strings.Join(parts, " → ")
}

func distinctTraces(occs []occurrence) int {
	seen := map[int]bool{}
	for _, o := range occs {
		seen[o.traceIdx] = true
	}
	return len(seen)
}

// candidate is a sequence and every place it appeared.
type candidate struct {
	key  string
	occs []occurrence
}

// restates reports whether a candidate is another view of a habit already kept.
//
// Substring containment alone is not enough. Variants of one habit differ at
// the edges — what happened just before the routine started — so
// "WebFetch → Grep → Read → Edit → Bash" and "Bash → Grep → Read → Edit → Bash"
// contain neither one another yet describe the same core. Reporting all of them
// fills the theme with one finding wearing different hats.
//
// Two tests, either of which is sufficient:
//
//   - a shared run of minLen consecutive steps, which is the same routine with
//     different edges; or
//   - a shorter shared run *and* a trace set entirely contained in the kept
//     pattern's. If every run exhibiting this pattern also exhibits a stronger
//     one, this is a facet of that, not a habit in its own right.
func restates(cand candidate, kept []candidate, minLen int) bool {
	steps := strings.Split(cand.key, " → ")
	mine := traceSet(cand.occs)

	for _, k := range kept {
		run := sharedRun(steps, strings.Split(k.key, " → "))
		if run >= minLen {
			return true
		}
		if run >= 2 && isSubsetOf(mine, traceSet(k.occs)) {
			return true
		}
	}
	return false
}

func traceSet(occs []occurrence) map[int]bool {
	out := make(map[int]bool, len(occs))
	for _, o := range occs {
		out[o.traceIdx] = true
	}
	return out
}

func isSubsetOf(a, b map[int]bool) bool {
	if len(a) > len(b) {
		return false
	}
	for k := range a {
		if !b[k] {
			return false
		}
	}
	return true
}

// sharedRun is the length of the longest run of consecutive steps common to
// both sequences.
func sharedRun(a, b []string) int {
	best := 0
	// Sequences here are at most MaxLen long, so the quadratic form is a few
	// dozen comparisons and needs no table.
	for i := range a {
		for j := range b {
			n := 0
			for i+n < len(a) && j+n < len(b) && a[i+n] == b[j+n] {
				n++
			}
			if n > best {
				best = n
			}
		}
	}
	return best
}

// toolNames strips the argument shape from each step, for a title that reads as
// a sentence. The full signatures stay on the insight for the detail view.
func toolNames(steps []string) []string {
	out := make([]string, len(steps))
	for i, st := range steps {
		if c := strings.Index(st, ":"); c > 0 {
			out[i] = st[:c]
			continue
		}
		out[i] = st
	}
	return out
}

// detectRepeatedAsks finds near-duplicate prompts.
//
// This is the "have I asked this before" signal. A cluster here means the same
// request was paid for several times over — which is either a habit worth
// capturing, or a sign the first answer did not stick.
func (c *Crystallize) detectRepeatedAsks(traces []TraceFacts) []Insight {
	prompts := make([]string, len(traces))
	for i, t := range traces {
		prompts[i] = t.Prompt
	}

	// The analysis runs in the background, so a local model is allowed a few
	// seconds. It is still bounded: a hung model server must not wedge the
	// analyzer, and the fallback costs only clustering quality.
	ctx, cancel := context.WithTimeout(context.Background(), 20*time.Second)
	defer cancel()

	clusters, method := clusterPrompts(ctx, c.Embedder, prompts, c.PromptSimilarity)
	c.lastMethod = method

	var out []Insight
	for _, members := range clusters {
		if len(members) < c.MinRuns {
			continue
		}
		var cost float64
		var tokens int64
		var ev []Evidence
		first, last := int64(0), int64(0)
		for _, m := range members {
			t := traces[m]
			cost += t.CostUSD
			tokens += t.Tokens
			if first == 0 || t.StartTS < first {
				first = t.StartTS
			}
			if t.StartTS > last {
				last = t.StartTS
			}
			ev = append(ev, Evidence{
				TraceID: t.TraceID, When: t.StartTS, Prompt: t.Prompt,
				CostUSD: t.CostUSD,
				Detail:  fmt.Sprintf("%d tool %s", len(t.Calls), plural(len(t.Calls), "call", "calls")),
			})
		}
		sort.SliceStable(ev, func(i, j int) bool { return ev[i].When > ev[j].When })

		ins := Insight{
			ID:          "crystallize/ask/" + slug(traces[members[0]].Prompt),
			Theme:       ThemeCrystallize,
			Severity:    severityFor(cost, len(members)),
			Title:       fmt.Sprintf("You asked for much the same thing %d times", len(members)),
			Occurrences: len(members),
			CostUSD:     cost,
			Tokens:      tokens,
			FirstSeen:   first,
			LastSeen:    last,
			Evidence:    ev,
		}
		basis := "share most of their wording"
		if method == MethodEmbedding {
			basis = "are asking for much the same thing"
		}
		ins.Method = method
		ins.Body = fmt.Sprintf(
			"%d runs "+basis+" and cost %s between them. "+
				"Each one started from scratch: the context was rebuilt, the files were re-read, and the same ground was covered again.",
			len(members), money(cost))
		ins.Suggestion = "If this is a recurring task rather than a one-off, the steps behind it are a good candidate " +
			"for a small skill. If it is the same question asked repeatedly because the answer did not stick, " +
			"writing the answer down somewhere the agent reads is cheaper than asking again."
		out = append(out, ins)
	}
	return out
}

// evidenceFor builds per-trace evidence for a sequence, capped so the UI shows
// a readable sample rather than every occurrence.
func evidenceFor(traces []TraceFacts, occs []occurrence, steps []string) ([]Evidence, int64, int64) {
	const maxEvidence = 8

	byTrace := map[int]occurrence{}
	for _, o := range occs {
		if _, ok := byTrace[o.traceIdx]; !ok {
			byTrace[o.traceIdx] = o
		}
	}

	var first, last int64
	var ev []Evidence
	for ti, o := range byTrace {
		t := traces[ti]
		if first == 0 || t.StartTS < first {
			first = t.StartTS
		}
		if t.StartTS > last {
			last = t.StartTS
		}
		ev = append(ev, Evidence{
			TraceID: t.TraceID,
			When:    t.StartTS,
			Prompt:  t.Prompt,
			CostUSD: t.CostUSD,
			Detail:  concreteSteps(t, o.at, len(steps)),
		})
	}
	sort.SliceStable(ev, func(i, j int) bool { return ev[i].When > ev[j].When })
	if len(ev) > maxEvidence {
		ev = ev[:maxEvidence]
	}
	return ev, first, last
}

// concreteSteps shows what the pattern actually did in one trace, which is what
// makes the abstract signature believable.
func concreteSteps(t TraceFacts, at, n int) string {
	var parts []string
	for i := at; i < at+n && i < len(t.Calls); i++ {
		c := t.Calls[i]
		label := c.Name
		if c.Target != "" {
			label += " " + trimMiddle(c.Target, 44)
		}
		parts = append(parts, label)
	}
	return strings.Join(parts, " → ")
}

func trimMiddle(s string, n int) string {
	r := []rune(s)
	if len(r) <= n {
		return s
	}
	keep := (n - 1) / 2
	return string(r[:keep]) + "…" + string(r[len(r)-keep:])
}

func shortDur(micros int64) string {
	s := float64(micros) / 1e6
	switch {
	case s < 1:
		return fmt.Sprintf("%.0fms", s*1000)
	case s < 60:
		return fmt.Sprintf("%.1fs", s)
	case s < 3600:
		return fmt.Sprintf("%.0fm", s/60)
	}
	return fmt.Sprintf("%.1fh", s/3600)
}

func slug(s string) string {
	var b strings.Builder
	for _, r := range strings.ToLower(s) {
		switch {
		case r >= 'a' && r <= 'z', r >= '0' && r <= '9':
			b.WriteRune(r)
		case b.Len() > 0 && b.String()[b.Len()-1] != '-':
			b.WriteByte('-')
		}
		if b.Len() > 60 {
			break
		}
	}
	return strings.Trim(b.String(), "-")
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}