CommonContextExtraction

Common Context Extraction (CCE) for UPLC terms.

Generalizes CSE by extracting common contexts (subtrees differing in exactly one position) into shared lambda-abstractions. While CSE handles identical subexpressions, CCE handles cases where repeated structures differ in a single "hole" at '''any''' child position:

// Right-spine (original):
headList(tailList(sndPair(unConstrData(x)))) + headList(tailList(sndPair(unConstrData(y))))
→ let f = \a -> headList(tailList(sndPair(unConstrData(a)))) in f(x) + f(y)

// Left-spine (new): f(x, z) + f(y, z)
→ let g = \a -> f(a, z) in g(x) + g(y)

// Case scrutinee (new): case x of [...] and case y of [...]
→ let h = \a -> case a of [...] in h(x) + h(y)

This reduces on-chain script code size (CBOR bytes), which directly affects transaction fees.

==Algorithm==

1. '''Collect pass''': Traverse the term. For each non-leaf node, generate all single-hole decompositions via CommonContextExtraction.decompose. Record templates with termSize >= 6 (see CommonContextExtraction.MinTemplateSize) along with their paths. Track path IDs at evaluation boundaries (LamAbs, Delay, Case) — same as CSE.
2. '''Group & filter pass''': Group by TemplateKey. For each group:
   • Require >= 2 distinct leaves (identical leaves are handled by CSE)
   • Profitability check: (N-1) * templateSize > N + 3
   • Compute bind path as longest common prefix of occurrence paths
   • Scope safety: free vars of template (excluding HOLE) in scope at bind path
   • Shadowing safety: no re-binding between bind and occurrence paths
   • Conditional boundary safety: no hoisting shape-partial builtins across Case/Delay
3. '''Substitute pass''': For each candidate (largest template first):
   • Re-count in (possibly modified) term via CommonContextExtraction.matchTemplate
   • Create fresh name __cce_<HeadBuiltin>[_N] (e.g. __cce_HeadList, __cce_SndPair_1)
   • Replace each matching occurrence with Apply(Var(lambdaName), leaf)
   • Insert at bind path: Apply(LamAbs(lambdaName, body), LamAbs(param, templateBody))