wave6 follow-up: gatsby-0001 — three filter-cache builders nodeTypeNames.includes -> Set

The Gatsby authors annotated each of the three call sites in
in-memory/indexing.ts with 'expensive at scale' comments. Their
diagnosis is correct: nodeTypeNames.includes(node.internal.type)
inside iterateNodes().forEach is O(N*T) per cache build.

For N=100k+ nodes typical of mature content sites and T=10-30
declared types per query, this fires on every type-filtered query.
gatsby develop in particular rebuilds caches per page render.

Fix: hoist Set<string> once at the top of each function. O(1) per
node lookup. Total cost O(N+T). Bench shows 8.4x at N=100k T=50;
2.7-4.7x at smaller scales.

Three call sites patched: ensureIndexByElemMatch (line 326),
ensureEmptyFilterCache (378), ensureIndexByElemMatchValue (504).
Author 'expensive at scale' comments updated to record the fix.

2026-04-25 10:15:32 -04:00

2.2 KiB

Raw Permalink Blame History

Gatsby — CWE-407 Disclosure Brief

Project: Gatsby (gatsbyjs/gatsby) Disclosure date: 2026-04-25 Severity: MEDIUM-HIGH Speedup: 8.4× measured at N=100,000 nodes × T=50 types Status: patch-ready, 1 patch + bench

Summary

Gatsby's in-memory datastore builds filter caches by walking every node and checking each node's type against a list of declared nodeTypeNames via Array#includes. Three call sites in packages/gatsby/src/datastore/in-memory/indexing.ts use this pattern. Two of them carry a Gatsby-author comment: // This loop is expensive at scale (!). The third notes // Expensive at scale.

The author's annotation is correct. For N nodes and T type-names, per-cache-build cost is O(N×T). Mature Gatsby sites carry 50K-500K nodes (every Markdown file, image, frontmatter object, GraphQL-introspected source becomes a node). Each query that filters by type rebuilds the cache; gatsby develop rebuilds caches per page. The fix is a single-line Set hoist per call site.

The Defects

gatsby-0001 (MOAD-0001 — MEDIUM-HIGH): packages/gatsby/src/datastore/in-memory/indexing.ts:326, 378, 504

// Three call sites with the same shape, e.g. line 326:
} else {
  // This loop is expensive at scale (!)
  getDataStore().iterateNodes().forEach(node => {
    if (!nodeTypeNames.includes(node.internal.type)) {  // O(T) per node
      return
    }
    addNodeToFilterCache({ node, ... })
  })
}

Fix: Hoist Set<string> once outside the loop; Set#has is O(1).

Benchmark (N nodes × T types)	defective	fixed	speedup
10,000 × 10	4.70ms	1.71ms	2.7×
50,000 × 20	45.70ms	9.67ms	4.7×
100,000 × 20	92.46ms	22.26ms	4.2×
100,000 × 50	198.74ms	23.57ms	8.4×

Scanner Evidence

unmoad flags all three call sites at HIGH severity via array-includes-in-loop. The patch hoists each nodeTypeNames array into a Set and replaces .includes with .has.

Patches

gatsby-0001-indexing-nodetypenames-includes-set.patch

2.2 KiB Raw Permalink Blame History Unescape Escape