Repository: gcanti/io-ts (ts)

Issue:
RangeError: Maximum call stack size exceeded
## 🐛 Bug report

### Current Behavior

`RangeError: Maximum call stack size exceeded`

### Expected behavior

No error

### Reproducible example

https://stackblitz.com/edit/typescript-3kmxjd

### Suggested solution(s)

Memoisation, Tail Call Optimisation, Trampolining
https://blog.logrocket.com/using-trampolines-to-manage-large-recursive-loops-in-javascript-d8c9db095ae3/

### Additional context

The code in this example is generated using io-ts-codegen.
This code is used to decode forms that are shown to the user to be filled using angular components.

### Your environment

Which versions of io-ts are affected by this issue?

io-ts@2.0.0

Did this work in previous versions of io-ts?

Not as far as I know.

<!-- PLEASE FILL THIS OUT -->

| Software   | Version(s) |
| ---------- | ---------- |
| io-ts      |      2.0.0      |
| fp-ts      |      2.0.3      |
| TypeScript |  3.4.5+          |


Pull request description:
fix `getTags` algorithm for mutually recursive codecs, closes #354

Patch:
diff --git a/CHANGELOG.md b/CHANGELOG.md
index a6074fe..905243e 100644
--- a/CHANGELOG.md
+++ b/CHANGELOG.md
@@ -14,6 +14,11 @@
 **Note**: Gaps between patch versions are faulty/broken releases. **Note**: A feature tagged as Experimental is in a
 high state of flux, you're at risk of it changing without notice.
 
+# 2.0.1
+
+- **Bug Fix**
+  - fix `getTags` algorithm for mutually recursive codecs, closes #354 (@gcanti)
+
 # 2.0.0
 
 - **Breaking Change**
diff --git a/package.json b/package.json
index 9126cac..c7dc2e6 100644
--- a/package.json
+++ b/package.json
@@ -1,6 +1,6 @@
 {
   "name": "io-ts",
-  "version": "2.0.0",
+  "version": "2.0.1",
   "description": "TypeScript compatible runtime type system for IO validation",
   "files": [
     "lib",
diff --git a/src/index.ts b/src/index.ts
index 998762c..b1ecfeb 100644
--- a/src/index.ts
+++ b/src/index.ts
@@ -1985,10 +1985,6 @@ export function alias<A, O, I>(
   return () => codec as any
 }
 
-//
-// backporting
-//
-
 interface NonEmptyArray<A> extends Array<A> {
   0: A
 }
@@ -2089,13 +2085,13 @@ function isRecursiveC(codec: Any): codec is RecursiveType<Any> {
   return (codec as any)._tag === 'RecursiveType'
 }
 
-let lazyCodec: Any | null = null
+const lazyCodecs: Array<Any> = []
 
 /**
  * @internal
  */
 export function getTags(codec: Any): Tags {
-  if (codec === lazyCodec) {
+  if (lazyCodecs.indexOf(codec) !== -1) {
     return emptyTags
   }
   if (isTypeC(codec) || isStrictC(codec)) {
@@ -2118,9 +2114,9 @@ export function getTags(codec: Any): Tags {
   } else if (isUnionC(codec)) {
     return codec.types.slice(1).reduce((tags, codec) => intersectTags(tags, getTags(codec)), getTags(codec.types[0]))
   } else if (isRecursiveC(codec)) {
-    lazyCodec = codec
+    lazyCodecs.push(codec)
     const tags = getTags(codec.type)
-    lazyCodec = null
+    lazyCodecs.pop()
     return tags
   }
   return emptyTags


Test patch:
diff --git a/test/recursion.ts b/test/recursion.ts
index ce30f18..db17c31 100644
--- a/test/recursion.ts
+++ b/test/recursion.ts
@@ -126,9 +126,9 @@ describe('recursion', () => {
     type B = {
       a: A | null
     }
-    const A: t.Type<A> = t.recursion('A', self =>
+    const A: t.Type<A> = t.recursion('A', () =>
       t.type({
-        b: t.union([self, B, t.null])
+        b: t.union([A, B, t.null])
       })
     )
     const B: t.Type<B> = t.recursion('B', () =>
@@ -138,5 +138,21 @@ describe('recursion', () => {
     )
     assert.strictEqual(A.is({ b: { b: null } }), true)
     assert.strictEqual(A.is({ b: { a: { b: { a: null } } } }), true)
+
+    // #354
+    interface C1A {
+      a: C1A | string
+    }
+    const C1: t.Type<C1A> = t.recursion('C1', () =>
+      t.type({
+        a: t.union([C2, t.string])
+      })
+    )
+    const C2: t.Type<C1A> = t.recursion('C2', () => C1)
+    const C3 = t.union([C1, t.string])
+
+    assert.strictEqual(C3.is({ a: 'a' }), true)
+    assert.strictEqual(C3.is('a'), true)
+    assert.strictEqual(C3.is({ a: { a: 'a' } }), true)
   })
 })