Stack overflow on multi maps (and other non-trivial generic classes)

[xRodney]

Describe the bug

Hi,

while I was testing my other work (#4354) against Keycloak operator schema, I noticed another issue. The schema generation fails with StackOverflowError.

Upon closer inspection, it looks that the problematic part is their usage of concrete multi maps like so:

private MultivaluedHashMap<String, ComponentExportRepresentation> components;

public class MultivaluedHashMap<K, V> extends HashMap<K, List<V>> { /* ...  */ }

Fabric8 Kubernetes Client version

6.0.0

Steps to reproduce

Here's a minimal failing example:

@Group("map.fabric8.io")
@Version("v1alpha1")
public class ContainingMaps extends  CustomResource<ContainingMapsSpec, Void> {}

public class ContainingMapsSpec {
  private MyMultiMap<String, String> test3;
}

public class MyMultiMap<K, V> extends HashMap<K, List<V>> {}

Unfortunately, this cannot be avoided by using @SchemaFrom or @SchemaSwap annotations, because the Stack Overflow happens an a code path that does not process these annotations, namely in AnnotatedPropertyPathDetector

And it is not even necessary to run the full schema generation.

All that is needed to trigger the Stack Overflow (i.e. from a unit test) is:

Types.typeDefFrom(MyMultiMap.class);

Expected behavior

The problem is in the unschallow logic, implemented in Types class.

For generic types, the methods projectSuperClasses, projectDefinition, mapClassRefArguments and mapGenericProperties replace type parameters on superclasses with their concrete instantiations from usage site.

For simple types, like class IntStringMap extends HashMap<Integer,String>, this works by first creating a mapping {K -> Integer, V -> String} and thein recursively replacing all usages of K and V according to the mapping.

However, in our case, the mapping contains V -> List<V>. This gets expanded infinitely to List<List<List<...>>>, until memory is exhausted.

Obviously, expected behavior is for this to not happen, the V should only be expanded once.

Runtime

other (please specify in additional context)

Kubernetes API Server version

other (please specify in additional context)

Environment

other (please specify in additional context)

Fabric8 Kubernetes Client Logs

No response

Additional context

I think I may have a fix for the StackOverflowError, we can discuss that further, just please confirm that somebody else is not working on it already.

As a side note, even with that fixed, multimaps are still generated wrong. I may have a cure for that, too, but I'd create a separate issue.

[xRodney]

I forgot to mention, this only happens on 6.x version, for 5.x it does not fail

[xRodney]

Here's PoC fix: d62cba1

[andreaTP]

Hi @xRodney ! thanks a lot for looking into this!
Just in case you don't know about it, currently, the Keycloak operator is generating the CRD using this crd-generator and those are the necessary substitutions:
https://github.com/keycloak/keycloak/blob/bf1382728284c95a283c2850f34a428bcb2e7f22/operator/patch-sources.sh#L23

Regarding this issue:

This gets expanded infinitely

This sounds like a regression in sundrio that should be reported and fixed there if possible. Would you mind opening an issue here: https://github.com/sundrio/sundrio/issues ?

cc. @iocanel

[xRodney]

Hi @andreaTP,
yes I know about substitutions the Keycloak team needed to implement to fix their model.
The problem is that when they upgrade to 6.0.0, their model will not compile, with or without substitutions.

At the moment, I don't see a bug in sundrio (regarding this issue). The faulty logic is implemented in this project.

It is possible that there was a change of behavior between versions, perhaps regarding how Visitors handle changes they themselves caused. I'm not that familiar with a history of this project and/or sundrio. But with my limited understanding of the code, I don't see an obvious reason why sundrio's current behavior would be wrong.

[andreaTP]

From what you said, it sounds like an issue with sundrio which should not continue to expand the value type. But I might be wrong, I'll look into this better in the next days , let me know if you have any progress on this investigation.

[iocanel]

@xRodney @andreaTP: It does seem like a sundrio issue. Can you please raise an issue there? Meanwhile, you may be able to work around the issue by moving the spec to its own class.

[iocanel]

It seems that for some reason, sundrio has a hard time dealing with:

public class MyMultiMap<K, V> extends HashMap<K, List<V>> {}

Still investigating.

[xRodney]

There really is a bug in sundrio. It took me a while to simulate it, but I was successful in the end.
Interestingly, kubernetes-client does not directly use the code that causes the error. Instead, it copy/pastes the relevant parts (including the bug).
Of course, we'll see what the sundrio maintainers have to say about it, but right now I think the best course of action would be to fix it in sundrio, remove the copied code from this project and use the library version.

[andreaTP]

@xRodney can you please test everything out on top of this PR: #4403 ?

[andreaTP]

Closed by accident, but everything is in the master branch.

[manusa]

I'm confused, does #4403 fix this one (as the PR description says), or are there some pending tasks to complete the fix?

[andreaTP]

@manusa it "should" fix the issue, but it has not been tested against a complex scenario like the Keycloak RealmRepresentation, let's wait a few days if @xRodney is available to provide feedback on the current status.

[manusa]

👍 We'll wait for his feedback then. Tonight's SNAPSHOT should contain the new dependency.

[xRodney]

No, it's not fixed.

The fix in sundrio only applies to their TypeArguments util. It is not used in crd-generator, I wrote that it is a duplicate of code from this repo.
So either crd-generator should migrate to TypeArguments, or apply the fix to its own code.

To complicate thigs ever further, I am not fully convinced that the fix sundrio/sundrio#334 is, in fact, correct. What they did was to replace mapping V -> List<V> with V -> List<?>. While this indeed stops the looping, I think it it may give incorrect results.

I am not sure how much that would matter if we indeed wanted to migrate crd-code to TypeArguments. It most likely will matter once we will want to generate correct schema for multimaps (but that's a different issue)

I'll look into this further and I'll put some more comments to sundrio/sundrio#333 if I find something.

[andreaTP]

Thanks a lot, @xRodney for getting back to this!
Let me know your findings and, next week, I will try to better assess myself what's going on here.

Meanwhile cc. @iocanel for some additional help 🙏

[xRodney]

Update: I have made a PR to sundrio, fixing the issue (sundrio/sundrio#340). I have also made a PR here, which however relies on the changed code, so it won't compile for you. But locally it seems to be working.

[manusa]

I guess we need to wait on Sundrio release to complete this fix

[andreaTP]

ping @iocanel would you have the time to cut a release of sundrio 🙏 ?

[xRodney]

ping @andreaTP, sundrio has been released and the linked PR is ready for review