java-topology/docs/tickets/go-0001-isparameterized-tparams-slices-index-linear-scan.md

go-0001 — CWE-407: isParameterized tparams slices.Index linear scan

Target: golang/go — src/cmd/compile/internal/types2/infer.go Severity: MEDIUM Complexity: O(n²) → O(n)

Defect

tpWalker.isParameterized walks the type graph recursively. At each *TypeParam node (line 630) it calls slices.Index(w.tparams, t) to check membership:

case *TypeParam:
    return slices.Index(w.tparams, t) >= 0

w.tparams is a []*TypeParam slice. slices.Index is O(n) linear scan.

isParameterized is called in the inner body of type-inference loops (lines 173, 290, 420–443, 451). For a generic function with N type parameters, each call walks up to N TypeParam nodes, each doing an O(N) scan → O(N²) total per inference invocation. With deeply nested generic types or long type parameter lists, this compounds across every call site in the outer dirty loop.

Fix

Replace the tparams []*TypeParam slice with a tset map[*TypeParam]bool pre-built before walking. Then membership is O(1) per node.

func isParameterized(tparams []*TypeParam, typ Type) bool {
    tset := make(map[*TypeParam]bool, len(tparams))
    for _, tp := range tparams {
        tset[tp] = true
    }
    w := tpWalker{
        tparams: tset,
        seen:    make(map[Type]bool),
    }
    return w.isParameterized(typ)
}

type tpWalker struct {
    tparams map[*TypeParam]bool   // was []*TypeParam
    seen    map[Type]bool
}

// In isParameterized switch:
case *TypeParam:
    return w.tparams[t]

Impact

• Triggered during type inference for every generic function call
• Scales with number of type parameters × depth of type graph
• Projects with many generic functions (e.g. large generics-heavy codebases) see O(n²) degradation in compile time

Files

• Patch: defects/go/patch/go-0001.patch
• Unit: defects/go/unit/GoInferTest.java