TypeDescriptor with recursive generics triggers infinite recursion in ResolvableType.equals/hashCode

[juancarrey]

During SpEL evaluation, if the TypeDescriptor is recursive, the evaluation results in infinite recursion causing stack overflow.

This line:

spring-framework/spring-core/src/main/java/org/springframework/core/convert/TypeDescriptor.java

Line 509 in ba4105d

ObjectUtils.nullSafeEquals(getMapValueTypeDescriptor(), otherDesc.getMapValueTypeDescriptor()));

Evaluated object sample where we have this issue is a map:

public class MyClass implements Map<String, MyClass>

This causes the evaluation of equality to check the type, and recursively the inner types of the map.

[sbrannen]

Hi @juancarrey,

Congratulations on submitting your first issue for the Spring Framework! 👍

Unfortunately you have not provided enough information for us to reproduce the issue.

If you would like us to investigate this, please provide a minimal example that we can run -- for example, a stand-alone JUnit test class or a minimal sample application made available via a Git repository or a ZIP file attached to this issue.

Thanks

---

In any case, it appears that this may be an issue with TypeDescriptor in spring-core and therefore not specific to SpEL.

[sbrannen]

In any case, it appears that this may be an issue with TypeDescriptor in spring-core and therefore not specific to SpEL.

Indeed, the following results in a StackOverflowError.

class RecursiveTypeDescriptorTests {

	@Test
	void recursiveTypeDescriptor() {
		TypeDescriptor typeDescriptor1 =
				TypeDescriptor.map(Map.class,
						TypeDescriptor.valueOf(String.class),
						TypeDescriptor.valueOf(RecursiveMap.class));
		TypeDescriptor typeDescriptor2 =
				TypeDescriptor.map(Map.class,
						TypeDescriptor.valueOf(String.class),
						TypeDescriptor.valueOf(RecursiveMap.class));
		assertThat(typeDescriptor1).isEqualTo(typeDescriptor2);
	}


	static class RecursiveMap extends HashMap<String, RecursiveMap> {
	}

}

That results in a stack trace like this:

java.lang.StackOverflowError
	at org.springframework.util.ObjectUtils.nullSafeEquals(ObjectUtils.java:346)
	at org.springframework.core.ResolvableType.equals(ResolvableType.java:1023)
	at org.springframework.util.ObjectUtils.nullSafeEquals(ObjectUtils.java:342)
	at org.springframework.core.ResolvableType.equals(ResolvableType.java:1023)
	at org.springframework.util.ObjectUtils.nullSafeEquals(ObjectUtils.java:342)
	at org.springframework.core.ResolvableType.equals(ResolvableType.java:1023)
	at org.springframework.util.ObjectUtils.nullSafeEquals(ObjectUtils.java:342)
	at org.springframework.core.ResolvableType.equals(ResolvableType.java:1023)
	at org.springframework.util.ObjectUtils.nullSafeEquals(ObjectUtils.java:342)

But if we change the declaration of RecursiveMap to the following:

static class RecursiveMap extends HashMap<String, RecursiveMap>
	implements Map<String, RecursiveMap> {
}

... we then see a stack trace like this:

java.lang.StackOverflowError
	at org.springframework.util.ObjectUtils.nullSafeHashCode(ObjectUtils.java:452)
	at org.springframework.core.ResolvableType.calculateHashCode(ResolvableType.java:1056)
	at org.springframework.core.ResolvableType.hashCode(ResolvableType.java:1044)
	at org.springframework.util.ObjectUtils.nullSafeHashCode(ObjectUtils.java:452)
	at org.springframework.core.ResolvableType.calculateHashCode(ResolvableType.java:1056)
	at org.springframework.core.ResolvableType.hashCode(ResolvableType.java:1044)
	at org.springframework.util.ObjectUtils.nullSafeHashCode(ObjectUtils.java:452)
	at org.springframework.core.ResolvableType.calculateHashCode(ResolvableType.java:1056)
	at org.springframework.core.ResolvableType.hashCode(ResolvableType.java:1044)

Note the recursion in ResolvableType.equals vs. ResolvableType.hashCode.

[sbrannen]

We like to avoid infinite recursion in such scenarios, potentially by checking upfront if the generics are equal without recursing, or potentially by tracking which types have been visited and throwing an exception if a cycle is detected.

Tentatively assigned to 6.2.1, but may be backported to 6.1.x depending on the solution.

Note: there might be recursion issues in TypeDescriptor as well as in ResolvableType. So, we should write tests for recursive generics with both.

[sbrannen]

Potentially Related Issues

• Resolve type variable recursively in GenericTypeResolver #30079
• Types with self-bounding generics cause infinite recursion in ResolvableType #32282

[zhanyan-Ader1y]

We like to avoid infinite recursion in such scenarios, potentially by checking upfront if the generics are equal without recursing, or potentially by tracking which types have been visited and throwing an exception if a cycle is detected.

Tentatively assigned to 6.2.1, but may be backported to 6.1.x depending on the solution.

Note: there might be recursion issues in TypeDescriptor as well as in ResolvableType. So, we should write tests for recursive generics with both.

Hi, I used the code in your comment to try to analyze the cause of this problem.
Hope it will be helpful for the next repair.

MyCode:

  /**
   * <pre>
   *  On this test case, stackoverflow start at {@link org.springframework.core.ResolvableType#equals}(ResolvableType.java:1023).
   *  <blockquote><pre>
   *  public boolean equals(@Nullable Object other) {
   *  ...
   *      if (...
   *        !ObjectUtils.nullSafeEquals(
   *            this.variableResolver.getSource(),
   *            otherType.variableResolver.getSource()
   *        ))) {
   * 		  return false;
   * 	  }
   *  }
   *  </pre></blockquote>
   *  The reason for infinite recursion is {@link ResolvableType.VariableResolver#getSource()} return cycle object likes:
   *  <blockquote><pre>
   *      class A extends HashMap<A, B>{}
   *  </pre></blockquote>
   *  or:
   *  <blockquote><pre>
   *      class C extends ArrayList<C>{}
   *  </pre></blockquote>
   * </pre>
   */
  @Test
  void test1() {
    TypeDescriptor typeDescriptor1 =
        TypeDescriptor.map(
            Map.class,
            TypeDescriptor.valueOf(String.class),
            TypeDescriptor.valueOf(RecursiveMap.class));
    TypeDescriptor typeDescriptor2 =
        TypeDescriptor.map(
            Map.class,
            TypeDescriptor.valueOf(String.class),
            TypeDescriptor.valueOf(RecursiveMap.class));
    ObjectUtils.nullSafeEquals(typeDescriptor1, typeDescriptor2);
  }

  /**
   * <pre>
   *  Why does this object implement the Map interface and throw diff stacktrace?
   *  I think this main reason same of test1, but some different in {@link ResolvableType#as(Class)}(call on {@link org.springframework.core.convert.TypeDescriptor#equals} ---> {@link TypeDescriptor#getMapKeyTypeDescriptor()}):
   *  <blockquote><pre>
   *  for (ResolvableType interfaceType : getInterfaces()) {
   * 	ResolvableType interfaceAsType = interfaceType.as(type);
   * 		if (interfaceAsType != NONE) {
   * 			return interfaceAsType;
   * 		}
   * 	}
   *  </pre></blockquote>
   *  focus on {@link ResolvableType#getInterfaces()}
   *  <blockquote><pre>
   *  	public ResolvableType[] getInterfaces() {
   * 		ResolvableType[] interfaces = this.interfaces;
   * 		if (interfaces == null) {
   * 			Type[] genericIfcs = resolved.getGenericInterfaces();
   * 			if (genericIfcs.length > 0) {
   * 				interfaces = new ResolvableType[genericIfcs.length];
   * 				for (int i = 0; i < genericIfcs.length; i++) {
   * 			        //  this forType function will use new ResolvableType(type, typeProvider, variableResolver)
   * 			        //  ResolvableType.calculateHashCode in this constructor
   * 					interfaces[i] = forType(genericIfcs[i], this);
   * 				}
   * 			}
   * 		......
   *  </pre></blockquote>
   *
   *  </pre>
   *
   *
   */
  @Test
  void test2() {
    TypeDescriptor typeDescriptor1 =
        TypeDescriptor.map(
            Map.class,
            TypeDescriptor.valueOf(String.class),
            TypeDescriptor.valueOf(RecursiveMap2.class));
    TypeDescriptor typeDescriptor2 =
        TypeDescriptor.map(
            Map.class,
            TypeDescriptor.valueOf(String.class),
            TypeDescriptor.valueOf(RecursiveMap2.class));
    ObjectUtils.nullSafeEquals(typeDescriptor1, typeDescriptor2);
  }

  static class RecursiveMap extends HashMap<String, RecursiveMap> {}

  static class RecursiveMap2 extends HashMap<RecursiveMap2, String>
      implements Map<RecursiveMap2, String> {}

  //  throw STOF
  static class RecursiveList extends ArrayList<RecursiveList>{

  }