Skip to content

[java] Fix StackOverflowError in TypeOps projection of cyclic captured type vars#6553

Merged
adangel merged 3 commits into
pmd:mainfrom
slovdahl:StackOverflowError-fix
May 7, 2026
Merged

[java] Fix StackOverflowError in TypeOps projection of cyclic captured type vars#6553
adangel merged 3 commits into
pmd:mainfrom
slovdahl:StackOverflowError-fix

Conversation

@slovdahl
Copy link
Copy Markdown
Contributor

Full disclosure

The issue in question, the fix and the test was to 100% analzyzed and written by Claude Code and Sonnet 4.6. I have verified locally that this change fixes the issue reported in #5721. That said, I have no idea if the fix makes sense. It took a few iterations, but the analysis sounds plausible. OTOH, it might equally well be hallucination. 🙈

Describe the PR

Root cause

TypeOps.projectUpwards() / projectDownwards() use UPWARDS_PROJECTOR /
DOWNWARDS_PROJECTOR, which are JTypeVisitor implementations that recursively
walk a type and substitute captured type variables with their bounds.

For a captured var α whose upper bound is a parameterized type that contains
α again as a wildcard bound (e.g. Container<T extends Container<? extends T>>
produces α with upper bound Container<? extends α>), the projection entered
infinite mutual recursion:

visitTypeVar(α) → follows bound Container<? extends α>
→ visitClass → recurseIfNotDone(? extends α) [wildcard: no cycle guard]
→ visitWildcard(? extends α) → follows bound α
→ visitTypeVar(α) → follows bound Container<? extends α> [cycle!]

RecursionStop.recurseIfNotDone only guarded against JTypeVar type args
(direct type-arg position in visitClass). Wildcards bypassed that guard,
so the wildcard → captured-var → bound → wildcard cycle was undetected.

Two distinct cycle paths require two distinct guards

visitTypeVar for a captured var α can be reached via two paths:

  1. Via recurseIfNotDone body (direct type-arg in visitClass):
    recurseIfNotDone adds α to its set and calls body = visitTypeVar(α).
    Detected by contains(α) == true. The cycle guard for DIRECT type args
    is already handled by recurseIfNotDone itself (second encounter of α
    as a direct type arg returns α unchanged → isCvar → replaced with ?).
    However, α's bound may still lead back to α via a WILDCARD (not a
    direct type arg), escaping recurseIfNotDone's guard. This path needs
    its own cycle detection: containsCallStack.

  2. Via a fresh call (top level) or via visitWildcard (wildcard-bound path):
    α is NOT yet in recurseIfNotDone's set. This is the original SOE path.
    Detected by contains(α) == false. This path needs freshCallStack.

The two stacks cannot be merged: the Scratch<T extends Scratch> case
requires the recurseIfNotDone body call to proceed (even though an outer
fresh call may have already entered the same var in freshCallStack), because
the legitimate first-level unrolling (Scratch → Scratch>)
depends on the body following the bound before recurseIfNotDone catches the
second direct occurrence. Using a single shared stack would confuse the two
paths and prevent the correct projection.

RecursionStop now carries:

  • contains(tvar): read-only check of the recurseIfNotDone set.
  • enterFreshVar / leaveFreshVar: for fresh/wildcard-path cycle detection.
  • enterContainsVar / leaveContainsVar: for contains-path cycle detection.

Related issues

Ready?

  • Added unit tests for fixed bug/feature
  • Passing all unit tests
  • Complete build ./mvnw clean verify passes (checked automatically by github actions)
  • Added (in-code) documentation (if needed)

slovdahl and others added 2 commits March 27, 2026 15:10
…d type vars

Root cause
----------
TypeOps.projectUpwards() / projectDownwards() use UPWARDS_PROJECTOR /
DOWNWARDS_PROJECTOR, which are JTypeVisitor implementations that recursively
walk a type and substitute captured type variables with their bounds.

For a captured var α whose upper bound is a parameterized type that contains
α again as a wildcard bound (e.g. Container<T extends Container<? extends T>>
produces α with upper bound Container<? extends α>), the projection entered
infinite mutual recursion:

  visitTypeVar(α) → follows bound Container<? extends α>
    → visitClass → recurseIfNotDone(? extends α)  [wildcard: no cycle guard]
      → visitWildcard(? extends α) → follows bound α
        → visitTypeVar(α) → follows bound Container<? extends α>  [cycle!]

RecursionStop.recurseIfNotDone only guarded against JTypeVar type args
(direct type-arg position in visitClass). Wildcards bypassed that guard,
so the wildcard → captured-var → bound → wildcard cycle was undetected.

Two distinct cycle paths require two distinct guards
----------------------------------------------------
visitTypeVar for a captured var α can be reached via two paths:

1. Via recurseIfNotDone body (direct type-arg in visitClass):
   recurseIfNotDone adds α to its set and calls body = visitTypeVar(α).
   Detected by contains(α) == true. The cycle guard for DIRECT type args
   is already handled by recurseIfNotDone itself (second encounter of α
   as a direct type arg returns α unchanged → isCvar → replaced with ?).
   However, α's bound may still lead back to α via a WILDCARD (not a
   direct type arg), escaping recurseIfNotDone's guard. This path needs
   its own cycle detection: containsCallStack.

2. Via a fresh call (top level) or via visitWildcard (wildcard-bound path):
   α is NOT yet in recurseIfNotDone's set. This is the original SOE path.
   Detected by contains(α) == false. This path needs freshCallStack.

The two stacks cannot be merged: the Scratch<T extends Scratch<T>> case
requires the recurseIfNotDone body call to proceed (even though an outer
fresh call may have already entered the same var in freshCallStack), because
the legitimate first-level unrolling (Scratch<T> → Scratch<? extends Scratch<?>>)
depends on the body following the bound before recurseIfNotDone catches the
second direct occurrence. Using a single shared stack would confuse the two
paths and prevent the correct projection.

RecursionStop now carries:
- contains(tvar): read-only check of the recurseIfNotDone set.
- enterFreshVar / leaveFreshVar: for fresh/wildcard-path cycle detection.
- enterContainsVar / leaveContainsVar: for contains-path cycle detection.

Co-Authored-By: Claude Sonnet 4.6 <[email protected]>
…with cyclic captured vars

Tests two distinct cycle paths that caused SOEs:

1. Fresh/wildcard path: captured var α whose upper bound directly contains
   a wildcard self-reference (Container<T extends Container<? extends T>>).
   Calling getValue() on Container<?> returns α; projecting α upwards visits
   Container<? extends α>, then the wildcard bound re-enters visitTypeVar(α).

2. Direct type-arg / contains path: captured var α appearing as a direct type
   argument in a class type (e.g. via wrap() returning Container<T>), where
   α's bound also contains a wildcard self-reference. visitClass calls
   recurseIfNotDone(α, body); body follows α's bound which leads back to α
   via a wildcard, re-entering visitTypeVar(α) through the contains path.

Co-Authored-By: Claude Sonnet 4.6 <[email protected]>
@adangel adangel requested a review from oowekyala May 7, 2026 08:51
@pmd-actions-helper
Copy link
Copy Markdown
Contributor

Documentation Preview

Compared to main:
This changeset changes 0 violations,
introduces 0 new violations, 0 new errors and 0 new configuration errors,
removes 0 violations, 0 errors and 0 configuration errors.
There are 0 changed duplications, 0 new duplications and 0 removed duplications.
There are 0 changed CPD errors, 0 new CPD errors and 0 removed CPD errors.

Regression Tester Report

(comment created at 2026-05-07 09:25:39+00:00 for d1969b2)

Copy link
Copy Markdown
Member

@adangel adangel left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

I'm merging this. All existing tests pass, regression tester is unsuspicious.

Thanks for the fix!

adangel added a commit that referenced this pull request May 7, 2026
adangel added a commit that referenced this pull request May 7, 2026
@adangel adangel merged commit d1969b2 into pmd:main May 7, 2026
13 checks passed
@adangel adangel added this to the 7.25.0 milestone May 7, 2026
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Labels

None yet

Projects

None yet

Development

Successfully merging this pull request may close these issues.

[java] StackOverflowError in 7.17.0 with nested wildcard generics

2 participants