Regression in plokhotnyuk/jsoniter-scala, recursive type leads to infinite loop

[WojciechMazur]

Regression found in Open CB build for plokhotnyuk/jsoniter-scala
Build logs: https://github.com/VirtusLab/community-build3/actions/runs/5557868276/jobs/10155545094

Compiler version

Works in 3.3.0
Works in 3.3.1-RC4
Fails in 3.3.2-RC1-bin-20230719-816bd5e-NIGHTLY
Bisect points to: 9726e1a

Minimized code

type JsonPrimitive = String 

type Rec[JA[_], A] = A match { 
  case JsonPrimitive => JsonPrimitive | JA[Rec[JA, JsonPrimitive]]
  case _ => A | JA[Rec[JA, A]]
}

type Json = Rec[[A] =>> List[A], JsonPrimitive]

Output

-- Error: /Users/wmazur/projects/sandbox/main.test.scala:8:5 -------------------
8 |type Json = Rec[[A] =>> List[A], JsonPrimitive]
  |     ^
  |Recursion limit exceeded.
  |Maybe there is an illegal cyclic reference?
  |If that's not the case, you could also try to increase the stacksize using the -Xss JVM option.
  |For the unprocessed stack trace, compile with -Yno-decode-stacktraces.
  |A recurring operation is (inner to outer):
  |
  |  variance check of ...
  |  variance check of List[...]
  |  variance check of JsonPrimitive | List[...]
  |  variance check of JsonPrimitive | List[...]
  |  variance check of List[JsonPrimitive | List[...]]
  |  variance check of JsonPrimitive | List[JsonPrimitive | List[...]]
  |  variance check of JsonPrimitive | List[JsonPrimitive | List[...]]
  |  variance check of List[JsonPrimitive | List[JsonPrimitive | List[...]]]
  |  variance check of JsonPrimitive | List[JsonPrimitive | List[JsonPrimitive | List[...]]]
  |  variance check of JsonPrimitive | List[JsonPrimitive | List[JsonPrimitive | List[...]]]
  |  ...
 
1 error found

-- Error: /Users/wmazur/projects/sandbox/main.test.scala:8:5 -------------------
8 |type Json = Rec[[A] =>> List[A], JsonPrimitive]
  |     ^
  |Recursion limit exceeded.
  |Maybe there is an illegal cyclic reference?
  |If that's not the case, you could also try to increase the stacksize using the -Xss JVM option.
  |For the unprocessed stack trace, compile with -Yno-decode-stacktraces.
  |A recurring operation is (inner to outer):
  |
  |  variance check of ...
  |  variance check of List[...]
  |  variance check of JsonPrimitive | List[...]
  |  variance check of JsonPrimitive | List[...]
  |  variance check of List[JsonPrimitive | List[...]]
  |  variance check of JsonPrimitive | List[JsonPrimitive | List[...]]
  |  variance check of JsonPrimitive | List[JsonPrimitive | List[...]]
  |  variance check of List[JsonPrimitive | List[JsonPrimitive | List[...]]]
  |  variance check of JsonPrimitive | List[JsonPrimitive | List[JsonPrimitive | List[...]]]
  |  variance check of JsonPrimitive | List[JsonPrimitive | List[JsonPrimitive | List[...]]]
  |  ...
  |
  |  variance check of JsonPrimitive |
  |  List[JsonPrimitive |
  |    List[JsonPrimitive |
  |      List[JsonPrimitive |
  |        List[JsonPrimitive |
  |          List[JsonPrimitive |
  |            List[JsonPrimitive |
  |              List[JsonPrimitive |
  |                List[JsonPrimitive |
  |                  List[JsonPrimitive |
  |                    List[JsonPrimitive |
  |                      List[JsonPrimitive |
  |                        List[JsonPrimitive |
  |                          List[JsonPrimitive |
  |                            List[JsonPrimitive |
  |                              List[JsonPrimitive |
  |                                List[JsonPrimitive |
  |                                  List[JsonPrimitive |
  |                                    List[JsonPrimitive |
  |                                      List[JsonPrimitive |
  |                                        List[JsonPrimitive |
  |                                          List[JsonPrimitive |
  |                                            List[JsonPrimitive |
  |                                              List[JsonPrimitive |
  |                                                List[...JsonPrimitive | ...[...]
  |                                                  ]
  |                                              ]
  |                                            ]
  |                                          ]
  |                                        ]
  |                                      ]
  |                                    ]
  |                                  ]
  |                                ]
  |                              ]
  |                            ]
  |                          ]
  |                        ]
  |                      ]
  |                    ]
  |                  ]
  |                ]
  |              ]
  |            ]
  |          ]
  |        ]
  |      ]
  |    ]
  |  ]
  |  variance check of List[JsonPrimitive |
  |  List[JsonPrimitive |
  |    List[JsonPrimitive |
  |      List[JsonPrimitive |
  |        List[JsonPrimitive |
  |          List[JsonPrimitive |
  |            List[JsonPrimitive |
  |              List[JsonPrimitive |
  |                List[JsonPrimitive |
  |                  List[JsonPrimitive |
  |                    List[JsonPrimitive |
  |                      List[JsonPrimitive |
  |                        List[JsonPrimitive |
  |                          List[JsonPrimitive |
  |                            List[JsonPrimitive |
  |                              List[JsonPrimitive |
  |                                List[JsonPrimitive |
  |                                  List[JsonPrimitive |
  |                                    List[JsonPrimitive |
  |                                      List[JsonPrimitive |
  |                                        List[JsonPrimitive |
  |                                          List[JsonPrimitive |
  |                                            List[JsonPrimitive |
  |                                              List[JsonPrimitive |
  |                                                List[... | ...]]
  |                                            ]
  |                                          ]
  |                                        ]
  |                                      ]
  |                                    ]
  |                                  ]
  |                                ]
  |                              ]
  |                            ]
  |                          ]
  |                        ]
  |                      ]
  |                    ]
  |                  ]
  |                ]
  |              ]
  |            ]
  |          ]
  |        ]
  |      ]
  |    ]
  |  ]
  |]
  |  variance check of JsonPrimitive |
  |  List[JsonPrimitive |
  |    List[JsonPrimitive |
  |      List[JsonPrimitive |
  |        List[JsonPrimitive |
  |          List[JsonPrimitive |
  |            List[JsonPrimitive |
  |              List[JsonPrimitive |
  |                List[JsonPrimitive |
  |                  List[JsonPrimitive |
  |                    List[JsonPrimitive |
  |                      List[JsonPrimitive |
  |                        List[JsonPrimitive |
  |                          List[JsonPrimitive |
  |                            List[JsonPrimitive |
  |                              List[JsonPrimitive |
  |                                List[JsonPrimitive |
  |                                  List[JsonPrimitive |
  |                                    List[JsonPrimitive |
  |                                      List[JsonPrimitive |
  |                                        List[JsonPrimitive |
  |                                          List[JsonPrimitive |
  |                                            List[JsonPrimitive |
  |                                              List[JsonPrimitive |
  |                                                List[...JsonPrimitive | ...[...]
  |                                                  ]
  |                                              ]
  |                                            ]
  |                                          ]
  |                                        ]
  |                                      ]
  |                                    ]
  |                                  ]
  |                                ]
  |                              ]
  |                            ]
  |                          ]
  |                        ]
  |                      ]
  |                    ]
  |                  ]
  |                ]
  |              ]
  |            ]
  |          ]
  |        ]
  |      ]
  |    ]
  |  ]
  |  variance check of JsonPrimitive |
  |  List[JsonPrimitive |
  |    List[JsonPrimitive |
  |      List[JsonPrimitive |
  |        List[JsonPrimitive |
  |          List[JsonPrimitive |
  |            List[JsonPrimitive |
  |              List[JsonPrimitive |
  |                List[JsonPrimitive |
  |                  List[JsonPrimitive |
  |                    List[JsonPrimitive |
  |                      List[JsonPrimitive |
  |                        List[JsonPrimitive |
  |                          List[JsonPrimitive |
  |                            List[JsonPrimitive |
  |                              List[JsonPrimitive |
  |                                List[JsonPrimitive |
  |                                  List[JsonPrimitive |
  |                                    List[JsonPrimitive |
  |                                      List[JsonPrimitive |
  |                                        List[JsonPrimitive |
  |                                          List[JsonPrimitive |
  |                                            List[JsonPrimitive |
  |                                              List[JsonPrimitive |
  |                                                List[...JsonPrimitive | ...[...]
  |                                                  ]
  |                                              ]
  |                                            ]
  |                                          ]
  |                                        ]
  |                                      ]
  |                                    ]
  |                                  ]
  |                                ]
  |                              ]
  |                            ]
  |                          ]
  |                        ]
  |                      ]
  |                    ]
  |                  ]
  |                ]
  |              ]
  |            ]
  |          ]
  |        ]
  |      ]
  |    ]
  |  ]
  |  variance check of List[JsonPrimitive |
  |  List[JsonPrimitive |
  |    List[JsonPrimitive |
  |      List[JsonPrimitive |
  |        List[JsonPrimitive |
  |          List[JsonPrimitive |
  |            List[JsonPrimitive |
  |              List[JsonPrimitive |
  |                List[JsonPrimitive |
  |                  List[JsonPrimitive |
  |                    List[JsonPrimitive |
  |                      List[JsonPrimitive |
  |                        List[JsonPrimitive |
  |                          List[JsonPrimitive |
  |                            List[JsonPrimitive |
  |                              List[JsonPrimitive |
  |                                List[JsonPrimitive |
  |                                  List[JsonPrimitive |
  |                                    List[JsonPrimitive |
  |                                      List[JsonPrimitive |
  |                                        List[JsonPrimitive |
  |                                          List[JsonPrimitive |
  |                                            List[JsonPrimitive |
  |                                              List[JsonPrimitive |
  |                                                List[... | ...]]
  |                                            ]
  |                                          ]
  |                                        ]
  |                                      ]
  |                                    ]
  |                                  ]
  |                                ]
  |                              ]
  |                            ]
  |                          ]
  |                        ]
  |                      ]
  |                    ]
  |                  ]
  |                ]
  |              ]
  |            ]
  |          ]
  |        ]
  |      ]
  |    ]
  |  ]
  |]
  |  variance check of JsonPrimitive |
  |  List[JsonPrimitive |
  |    List[JsonPrimitive |
  |      List[JsonPrimitive |
  |        List[JsonPrimitive |
  |          List[JsonPrimitive |
  |            List[JsonPrimitive |
  |              List[JsonPrimitive |
  |                List[JsonPrimitive |
  |                  List[JsonPrimitive |
  |                    List[JsonPrimitive |
  |                      List[JsonPrimitive |
  |                        List[JsonPrimitive |
  |                          List[JsonPrimitive |
  |                            List[JsonPrimitive |
  |                              List[JsonPrimitive |
  |                                List[JsonPrimitive |
  |                                  List[JsonPrimitive |
  |                                    List[JsonPrimitive |
  |                                      List[JsonPrimitive |
  |                                        List[JsonPrimitive |
  |                                          List[JsonPrimitive |
  |                                            List[JsonPrimitive |
  |                                              List[JsonPrimitive |
  |                                                List[...JsonPrimitive | ...[...]
  |                                                  ]
  |                                              ]
  |                                            ]
  |                                          ]
  |                                        ]
  |                                      ]
  |                                    ]
  |                                  ]
  |                                ]
  |                              ]
  |                            ]
  |                          ]
  |                        ]
  |                      ]
  |                    ]
  |                  ]
  |                ]
  |              ]
  |            ]
  |          ]
  |        ]
  |      ]
  |    ]
  |  ]
  |  variance check of JsonPrimitive |
  |  List[JsonPrimitive |
  |    List[JsonPrimitive |
  |      List[JsonPrimitive |
  |        List[JsonPrimitive |
  |          List[JsonPrimitive |
  |            List[JsonPrimitive |
  |              List[JsonPrimitive |
  |                List[JsonPrimitive |
  |                  List[JsonPrimitive |
  |                    List[JsonPrimitive |
  |                      List[JsonPrimitive |
  |                        List[JsonPrimitive |
  |                          List[JsonPrimitive |
  |                            List[JsonPrimitive |
  |                              List[JsonPrimitive |
  |                                List[JsonPrimitive |
  |                                  List[JsonPrimitive |
  |                                    List[JsonPrimitive |
  |                                      List[JsonPrimitive |
  |                                        List[JsonPrimitive |
  |                                          List[JsonPrimitive |
  |                                            List[JsonPrimitive |
  |                                              List[JsonPrimitive |
  |                                                List[...JsonPrimitive | ...[...]
  |                                                  ]
  |                                              ]
  |                                            ]
  |                                          ]
  |                                        ]
  |                                      ]
  |                                    ]
  |                                  ]
  |                                ]
  |                              ]
  |                            ]
  |                          ]
  |                        ]
  |                      ]
  |                    ]
  |                  ]
  |                ]
  |              ]
  |            ]
  |          ]
  |        ]
  |      ]
  |    ]
  |  ]
  |  variance check of List[JsonPrimitive |
  |  List[JsonPrimitive |
  |    List[JsonPrimitive |
  |      List[JsonPrimitive |
  |        List[JsonPrimitive |
  |          List[JsonPrimitive |
  |            List[JsonPrimitive |
  |              List[JsonPrimitive |
  |                List[JsonPrimitive |
  |                  List[JsonPrimitive |
  |                    List[JsonPrimitive |
  |                      List[JsonPrimitive |
  |                        List[JsonPrimitive |
  |                          List[JsonPrimitive |
  |                            List[JsonPrimitive |
  |                              List[JsonPrimitive |
  |                                List[JsonPrimitive |
  |                                  List[JsonPrimitive |
  |                                    List[JsonPrimitive |
  |                                      List[JsonPrimitive |
  |                                        List[JsonPrimitive |
  |                                          List[JsonPrimitive |
  |                                            List[JsonPrimitive |
  |                                              List[JsonPrimitive |
  |                                                List[... | ...]]
  |                                            ]
  |                                          ]
  |                                        ]
  |                                      ]
  |                                    ]
  |                                  ]
  |                                ]
  |                              ]
  |                            ]
  |                          ]
  |                        ]
  |                      ]
  |                    ]
  |                  ]
  |                ]
  |              ]
  |            ]
  |          ]
  |        ]
  |      ]
  |    ]
  |  ]
  |]
  |  variance check of JsonPrimitive |
  |  List[JsonPrimitive |
  |    List[JsonPrimitive |
  |      List[JsonPrimitive |
  |        List[JsonPrimitive |
  |          List[JsonPrimitive |
  |            List[JsonPrimitive |
  |              List[JsonPrimitive |
  |                List[JsonPrimitive |
  |                  List[JsonPrimitive |
  |                    List[JsonPrimitive |
  |                      List[JsonPrimitive |
  |                        List[JsonPrimitive |
  |                          List[JsonPrimitive |
  |                            List[JsonPrimitive |
  |                              List[JsonPrimitive |
  |                                List[JsonPrimitive |
  |                                  List[JsonPrimitive |
  |                                    List[JsonPrimitive |
  |                                      List[JsonPrimitive |
  |                                        List[JsonPrimitive |
  |                                          List[JsonPrimitive |
  |                                            List[JsonPrimitive |
  |                                              List[JsonPrimitive |
  |                                                List[...JsonPrimitive | ...[...]
  |                                                  ]
  |                                              ]
  |                                            ]
  |                                          ]
  |                                        ]
  |                                      ]
  |                                    ]
  |                                  ]
  |                                ]
  |                              ]
  |                            ]
  |                          ]
  |                        ]
  |                      ]
  |                    ]
  |                  ]
  |                ]
  |              ]
  |            ]
  |          ]
  |        ]
  |      ]
  |    ]
  |  ]
  |  variance check of  = JsonPrimitive |
  |  List[JsonPrimitive |
  |    List[JsonPrimitive |
  |      List[JsonPrimitive |
  |        List[JsonPrimitive |
  |          List[JsonPrimitive |
  |            List[JsonPrimitive |
  |              List[JsonPrimitive |
  |                List[JsonPrimitive |
  |                  List[JsonPrimitive |
  |                    List[JsonPrimitive |
  |                      List[JsonPrimitive |
  |                        List[JsonPrimitive |
  |                          List[JsonPrimitive |
  |                            List[JsonPrimitive |
  |                              List[JsonPrimitive |
  |                                List[JsonPrimitive |
  |                                  List[JsonPrimitive |
  |                                    List[JsonPrimitive |
  |                                      List[JsonPrimitive |
  |                                        List[JsonPrimitive |
  |                                          List[JsonPrimitive |
  |                                            List[JsonPrimitive |
  |                                              List[JsonPrimitive |
  |                                                List[... | ...]]
  |                                            ]
  |                                          ]
  |                                        ]
  |                                      ]
  |                                    ]
  |                                  ]
  |                                ]
  |                              ]
  |                            ]
  |                          ]
  |                        ]
  |                      ]
  |                    ]
  |                  ]
  |                ]
  |              ]
  |            ]
  |          ]
  |        ]
  |      ]
  |    ]
  |  ]
1 error found

Input 2

More complex input (original source) leads to compiler crash due to StackOverflowError

type JsonPrimitive = String | Int | Double | Boolean | None.type

type Rec[JA[_], JO[_], A] = A match {
  case JsonPrimitive => JsonPrimitive | JA[Rec[JA, JO, JsonPrimitive]] | JO[Rec[JA, JO, JsonPrimitive]]
  case _ => A | JA[Rec[JA, JO, A]] | JO[Rec[JA, JO, A]]
}

type Json = Rec[[A] =>> List[A], [A] =>> Map[String, A], JsonPrimitive]

Expectation

Should allow to compile the recursive type

[dwijnand]

No, as it says in the PR, we're disallowing infinite match types.

[dwijnand]

tests/pos/i15158.scala → tests/neg/i15158.scala is the test we have internally where we decided to disallow this.

[WojciechMazur]

@plokhotnyuk You might be interested in this change.

[WojciechMazur]

I wonder if we're capable of detecting recursive types early and introduce some circuit-break mechanism. The following snippet would be compiling infinitely long on current nightly. This might later lead to issues with tooling, eg. bloop might not be able to cancel ongoing compilation.
The issue might be present only when having a big, recursive union types and might be only present when upgrading from 3.3 LTS which allowed for the compilation.

import scala.collection.mutable

type JsonPrimitive = String | Int | Double | Boolean | None.type
type Rec[JA[_], JO[_], A] = A match { 
  case JsonPrimitive => JsonPrimitive | JA[Rec[JA, JO, JsonPrimitive]] | JO[Rec[JA, JO, JsonPrimitive]]
  case _ => A | JA[Rec[JA, JO, A]] | JO[Rec[JA, JO, A]]
}
type Json = Rec[[A] =>> mutable.Buffer[A], [A] =>> mutable.Map[String, A], JsonPrimitive]

trait JsonValueCodec[A]

def jsonCodec: JsonValueCodec[Json] = ???