Repository: fabien0102/ts-to-zod
Pull request #114 (2023-02-01 02:58:37)

Support circular dependencies with loops of length > 1
# Why

This PR add support for any circular dependencies with loops of length > 1 (unless there are missing dependencies)

Before this PR, This repo already supported types depending on itself with `z.lazy()` like:
```ts
interface Person {
  friend: Person
}
```

With `z.lazy()` actually circular dependencies with loops of length > 1 can also be supported, for example:
```ts
      export interface EvilPlan {
        description: string;
        details: EvilPlanDetails;
      }

      export interface EvilPlanDetails {
        parent: EvilPlan;
        steps: string[];
      }
```

With this PR will generate:
```ts
        export const evilPlanSchema: z.ZodSchema<EvilPlan> = z.lazy(() => z.object({
            description: z.string(),
            details: evilPlanDetailsSchema
        }));

        export const evilPlanDetailsSchema: z.ZodSchema<EvilPlanDetails> = z.lazy(() => z.object({
            parent: evilPlanSchema,
            steps: z.array(z.string())
        }));
```

codecov-commenter: # [Codecov](https://codecov.io/gh/fabien0102/ts-to-zod/pull/114?src=pr&el=h1&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=Fabien+BERNARD) Report
> Merging [#114](https://codecov.io/gh/fabien0102/ts-to-zod/pull/114?src=pr&el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=Fabien+BERNARD) (865b912) into [main](https://codecov.io/gh/fabien0102/ts-to-zod/commit/e5e49615d832129cae8a23cbf5fa0b35024e15e2?el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=Fabien+BERNARD) (e5e4961) will **decrease** coverage by `2.95%`.
> The diff coverage is `93.46%`.

:mega: This organization is not using Codecov’s [GitHub App Integration](https://github.com/apps/codecov). We recommend you install it so Codecov can continue to function properly for your repositories. [Learn more](https://about.codecov.io/blog/codecov-is-updating-its-github-integration/?utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=Fabien+BERNARD)

```diff
@@            Coverage Diff             @@
##             main     #114      +/-   ##
==========================================
- Coverage   98.49%   95.55%   -2.95%     
==========================================
  Files           8       13       +5     
  Lines         332      517     +185     
  Branches      102      172      +70     
==========================================
+ Hits          327      494     +167     
- Misses          5       20      +15     
- Partials        0        3       +3     
```


| [Impacted Files](https://codecov.io/gh/fabien0102/ts-to-zod/pull/114?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=Fabien+BERNARD) | Coverage Δ | |
|---|---|---|
| [src/utils/traverseTypes.ts](https://codecov.io/gh/fabien0102/ts-to-zod/pull/114?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=Fabien+BERNARD#diff-c3JjL3V0aWxzL3RyYXZlcnNlVHlwZXMudHM=) | `68.96% <68.96%> (ø)` | |
| [src/core/generateZodSchema.ts](https://codecov.io/gh/fabien0102/ts-to-zod/pull/114?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=Fabien+BERNARD#diff-c3JjL2NvcmUvZ2VuZXJhdGVab2RTY2hlbWEudHM=) | `95.19% <93.02%> (-2.02%)` | :arrow_down: |
| [src/utils/resolveModules.ts](https://codecov.io/gh/fabien0102/ts-to-zod/pull/114?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=Fabien+BERNARD#diff-c3JjL3V0aWxzL3Jlc29sdmVNb2R1bGVzLnRz) | `95.91% <95.91%> (ø)` | |
| [src/core/generate.ts](https://codecov.io/gh/fabien0102/ts-to-zod/pull/114?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=Fabien+BERNARD#diff-c3JjL2NvcmUvZ2VuZXJhdGUudHM=) | `100.00% <100.00%> (ø)` | |
| [src/core/jsDocTags.ts](https://codecov.io/gh/fabien0102/ts-to-zod/pull/114?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=Fabien+BERNARD#diff-c3JjL2NvcmUvanNEb2NUYWdzLnRz) | `98.57% <100.00%> (-1.43%)` | :arrow_down: |
| [src/core/validateGeneratedTypes.ts](https://codecov.io/gh/fabien0102/ts-to-zod/pull/114?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=Fabien+BERNARD#diff-c3JjL2NvcmUvdmFsaWRhdGVHZW5lcmF0ZWRUeXBlcy50cw==) | `97.05% <100.00%> (-0.31%)` | :arrow_down: |
| [src/utils/getSimplifiedJsDocTags.ts](https://codecov.io/gh/fabien0102/ts-to-zod/pull/114?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=Fabien+BERNARD#diff-c3JjL3V0aWxzL2dldFNpbXBsaWZpZWRKc0RvY1RhZ3MudHM=) | `100.00% <100.00%> (ø)` | |
| [src/utils/isNotNull.ts](https://codecov.io/gh/fabien0102/ts-to-zod/pull/114?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=Fabien+BERNARD#diff-c3JjL3V0aWxzL2lzTm90TnVsbC50cw==) | `100.00% <100.00%> (ø)` | |
| [src/utils/resolveDefaultProperties.ts](https://codecov.io/gh/fabien0102/ts-to-zod/pull/114?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=Fabien+BERNARD#diff-c3JjL3V0aWxzL3Jlc29sdmVEZWZhdWx0UHJvcGVydGllcy50cw==) | `100.00% <100.00%> (ø)` | |
| ... and [7 more](https://codecov.io/gh/fabien0102/ts-to-zod/pull/114?src=pr&el=tree-more&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=Fabien+BERNARD) | |

Help us with your feedback. Take ten seconds to tell us [how you rate us](https://about.codecov.io/nps?utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=Fabien+BERNARD). Have a feature suggestion? [Share it here.](https://app.codecov.io/gh/feedback/?utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=Fabien+BERNARD)

NexZhu: This PR addionally improve the generation process:

1. Every progressive iteration will at least find a direct or indirect missing dependency (1st iteration will find all direct missing dependencies, 2nd iteration will find all indirect missing dependencies depending on any direct missing dependencies, etc.), or at least one new type that can be generated (all its dependencies become able to be generated by this time).
2. If an iteration did not find any direct or indirect missing dependencies nor any new types that can be generated, the whole process can immediately end since no further iterations can possibly find them again.
3. To sum up, we can use a `done` flag to track if each iteration is still making progress and end the process as soon as there's no more progress being made, this way there won't be wasted iterations and dead loops won't happen.
4. Max iteration number flag is removed since it's not needed any more.
NexZhu: @fabien0102 Please check this out soon when you have time, so I can open further improvement PRs after this get merged, thanks! 😄

Patch:
diff --git a/README.md b/README.md
index d601e46..0d766a4 100644
--- a/README.md
+++ b/README.md
@@ -179,14 +179,13 @@ export interface Superman {
 }
 ```
 
-/!\ Please note: if your exported interface/type have a reference to a non-exported interface/type, ts-to-zod will not be able to generate anything (a circular dependency will be report due to the missing reference).
+/!\ Please note: if your exported interface/type have a reference to a non-exported interface/type, ts-to-zod will not be able to generate anything (missing dependencies will be reported).
 
 ## Limitation
 
 Since we are generating Zod schemas, we are limited by what Zod actually supports:
 
 - No type generics
-- No complex circular dependencies (you will be warn if you have some in your types)
 - No `Record<number, …>`
 - …
 
diff --git a/example/heros.zod.ts b/example/heros.zod.ts
index 076b4ac..a5ac122 100644
--- a/example/heros.zod.ts
+++ b/example/heros.zod.ts
@@ -1,6 +1,6 @@
 // Generated by ts-to-zod
 import { z } from "zod";
-import { EnemyPower, Villain } from "./heros";
+import { EnemyPower, Villain, EvilPlan, EvilPlanDetails } from "./heros";
 
 export const enemyPowerSchema = z.nativeEnum(EnemyPower);
 
@@ -89,3 +89,18 @@ export const supermanNameSchema = supermanSchema.shape.name;
 
 export const supermanInvinciblePowerSchema =
   supermanSchema.shape.powers.items[2];
+
+export const evilPlanSchema: z.ZodSchema<EvilPlan> = z.lazy(() =>
+  z.object({
+    owner: villainSchema,
+    description: z.string(),
+    details: evilPlanDetailsSchema,
+  })
+);
+
+export const evilPlanDetailsSchema: z.ZodSchema<EvilPlanDetails> = z.lazy(() =>
+  z.object({
+    parent: evilPlanSchema,
+    steps: z.array(z.string()),
+  })
+);
diff --git a/package.json b/package.json
index 140a9d3..8e8d7f9 100644
--- a/package.json
+++ b/package.json
@@ -39,6 +39,7 @@
   "dependencies": {
     "@oclif/command": "^1.8.6",
     "@oclif/config": "^1.17.1",
+    "@oclif/errors": "^1.3",
     "@oclif/plugin-help": "^3.2.7",
     "@typescript/vfs": "^1.3.5",
     "async": "^3.2.0",
diff --git a/src/cli.ts b/src/cli.ts
index 95fcdd1..6870388 100644
--- a/src/cli.ts
+++ b/src/cli.ts
@@ -67,11 +67,6 @@ class TsToZod extends Command {
   static flags = {
     version: flags.version({ char: "v" }),
     help: flags.help({ char: "h" }),
-    maxRun: flags.integer({
-      hidden: true,
-      default: 10,
-      description: "max iteration number to resolve the declaration order",
-    }),
     keepComments: flags.boolean({
       char: "k",
       description: "Keep parameters comments",
@@ -238,9 +233,6 @@ See more help with --help`,
       sourceText,
       ...fileConfig,
     };
-    if (typeof flags.maxRun === "number") {
-      generateOptions.maxRun = flags.maxRun;
-    }
     if (typeof flags.keepComments === "boolean") {
       generateOptions.keepComments = flags.keepComments;
     }
diff --git a/src/config.ts b/src/config.ts
index 7d53b34..9f34892 100644
--- a/src/config.ts
+++ b/src/config.ts
@@ -34,11 +34,6 @@ export type Config = {
    */
   skipValidation?: boolean;
 
-  /**
-   * Max iteration number to resolve the declaration order.
-   */
-  maxRun?: number;
-
   /**
    * Filter on type/interface name.
    */
diff --git a/src/config.zod.ts b/src/config.zod.ts
index 5c4e090..ec93181 100644
--- a/src/config.zod.ts
+++ b/src/config.zod.ts
@@ -25,7 +25,6 @@ export const configSchema = z.object({
   input: z.string(),
   output: z.string(),
   skipValidation: z.boolean().optional(),
-  maxRun: z.number().optional(),
   nameFilter: nameFilterSchema.optional(),
   jsDocTagFilter: jSDocTagFilterSchema.optional(),
   getSchemaName: getSchemaNameSchema.optional(),
diff --git a/src/core/generate.ts b/src/core/generate.ts
index b9da45d..4d62136 100644
--- a/src/core/generate.ts
+++ b/src/core/generate.ts
@@ -20,11 +20,6 @@ export interface GenerateProps {
    */
   sourceText: string;
 
-  /**
-   * Max iteration number to resolve the declaration order.
-   */
-  maxRun?: number;
-
   /**
    * Filter on type/interface name.
    */
@@ -61,7 +56,6 @@ export interface GenerateProps {
  */
 export function generate({
   sourceText,
-  maxRun = 10,
   nameFilter = () => true,
   jsDocTagFilter = () => true,
   getSchemaName = (id) => camel(id) + "Schema",
@@ -130,6 +124,7 @@ export function generate({
 
     return { typeName, varName, ...zodSchema };
   });
+  const zodSchemaNames = zodSchemas.map(({ varName }) => varName);
 
   // Resolves statements order
   // A schema can't be declared if all the referenced schemas used inside this one are not previously declared.
@@ -139,17 +134,31 @@ export function generate({
   >();
   const typeImports: Set<string> = new Set();
 
-  let n = 0;
-  while (statements.size !== zodSchemas.length && n < maxRun) {
+  // Zod schemas with direct or indirect dependencies that are not in `zodSchemas`, won't be generated
+  const zodSchemasWithMissingDependencies = new Set<string>();
+
+  let done = false;
+  // Loop until no more schemas can be generated and no more schemas with direct or indirect missing dependencies are found
+  while (
+    !done &&
+    statements.size + zodSchemasWithMissingDependencies.size !==
+      zodSchemas.length
+  ) {
+    done = true;
     zodSchemas
-      .filter(({ varName }) => !statements.has(varName))
+      .filter(
+        ({ varName }) =>
+          !statements.has(varName) &&
+          !zodSchemasWithMissingDependencies.has(varName)
+      )
       .forEach(
         ({ varName, dependencies, statement, typeName, requiresImport }) => {
           const isCircular = dependencies.includes(varName);
-          const missingDependencies = dependencies
+          const notGeneratedDependencies = dependencies
             .filter((dep) => dep !== varName)
             .filter((dep) => !statements.has(dep));
-          if (missingDependencies.length === 0) {
+          if (notGeneratedDependencies.length === 0) {
+            done = false;
             if (isCircular) {
               typeImports.add(typeName);
               statements.set(varName, {
@@ -162,24 +171,45 @@ export function generate({
               }
               statements.set(varName, { value: statement, typeName });
             }
+          } else if (
+            // Check if every dependency is (in `zodSchemas` and not in `zodSchemasWithMissingDependencies`)
+            !notGeneratedDependencies.every(
+              (dep) =>
+                zodSchemaNames.includes(dep) &&
+                !zodSchemasWithMissingDependencies.has(dep)
+            )
+          ) {
+            done = false;
+            zodSchemasWithMissingDependencies.add(varName);
           }
         }
       );
-
-    n++; // Just a safety net to avoid infinity loops
   }
 
-  // Warn the user of possible not resolvable loops
-  const missingStatements = zodSchemas.filter(
-    ({ varName }) => !statements.has(varName)
-  );
+  // Generate remaining schemas, which have circular dependencies with loop of length > 1 like: A->B—>C->A
+  zodSchemas
+    .filter(
+      ({ varName }) =>
+        !statements.has(varName) &&
+        !zodSchemasWithMissingDependencies.has(varName)
+    )
+    .forEach(
+      ({ varName, dependencies, statement, typeName, requiresImport }) => {
+        typeImports.add(typeName);
+        statements.set(varName, {
+          value: transformRecursiveSchema("z", statement, typeName),
+          typeName,
+        });
+      }
+    );
 
+  // Warn the user of possible not resolvable loops
   const errors: string[] = [];
 
-  if (missingStatements.length) {
+  if (zodSchemasWithMissingDependencies.size > 0) {
     errors.push(
-      `Some schemas can't be generated due to circular dependencies:
-${missingStatements.map(({ varName }) => `${varName}`).join("\n")}`
+      `Some schemas can't be generated due to direct or indirect missing dependencies:
+${Array.from(zodSchemasWithMissingDependencies).join("\n")}`
     );
   }
 
@@ -249,6 +279,7 @@ ${Array.from(statements.values())
     return print(zodInferredSchema);
   })
   .join("\n\n")}
+
 ${testCases.map(print).join("\n")}
 `;
 
diff --git a/yarn.lock b/yarn.lock
index b2b61af..b28e2ea 100644
--- a/yarn.lock
+++ b/yarn.lock
@@ -1675,6 +1675,17 @@
     strip-ansi "^6.0.0"
     wrap-ansi "^7.0.0"
 
+"@oclif/errors@^1.3":
+  version "1.3.6"
+  resolved "https://registry.yarnpkg.com/@oclif/errors/-/errors-1.3.6.tgz#e8fe1fc12346cb77c4f274e26891964f5175f75d"
+  integrity sha512-fYaU4aDceETd89KXP+3cLyg9EHZsLD3RxF2IU9yxahhBpspWjkWi3Dy3bTgcwZ3V47BgxQaGapzJWDM33XIVDQ==
+  dependencies:
+    clean-stack "^3.0.0"
+    fs-extra "^8.1"
+    indent-string "^4.0.0"
+    strip-ansi "^6.0.1"
+    wrap-ansi "^7.0.0"
+
 "@oclif/errors@^1.3.5":
   version "1.3.5"
   resolved "https://registry.yarnpkg.com/@oclif/errors/-/errors-1.3.5.tgz#a1e9694dbeccab10fe2fe15acb7113991bed636c"
@@ -4953,6 +4964,13 @@ strip-ansi@^6.0.0:
   dependencies:
     ansi-regex "^5.0.0"
 
+strip-ansi@^6.0.1:
+  version "6.0.1"
+  resolved "https://registry.yarnpkg.com/strip-ansi/-/strip-ansi-6.0.1.tgz#9e26c63d30f53443e9489495b2105d37b67a85d9"
+  integrity sha512-Y38VPSHcqkFrCpFnQ9vuSXmquuv5oXOKpGeT6aGrr3o3Gc9AlVa6JBfUSOCnbxGGZF+/0ooI7KrPuUSztUdU5A==
+  dependencies:
+    ansi-regex "^5.0.1"
+
 strip-bom@^4.0.0:
   version "4.0.0"
   resolved "https://registry.yarnpkg.com/strip-bom/-/strip-bom-4.0.0.tgz#9c3505c1db45bcedca3d9cf7a16f5c5aa3901878"


Test patch:
diff --git a/src/core/generate.test.ts b/src/core/generate.test.ts
index 4043c01..5a810a3 100644
--- a/src/core/generate.test.ts
+++ b/src/core/generate.test.ts
@@ -63,6 +63,7 @@ describe("generate", () => {
         export type supermanSchemaInferredType = z.infer<typeof generated.supermanSchema>;
 
         export type badassSupermanSchemaInferredType = z.infer<typeof generated.badassSupermanSchema>;
+
         expectType<spec.Name>({} as nameSchemaInferredType)
         expectType<nameSchemaInferredType>({} as spec.Name)
         expectType<spec.Superman>({} as supermanSchemaInferredType)
@@ -125,6 +126,7 @@ describe("generate", () => {
         export type superheroSchemaInferredType = z.infer<typeof generated.superheroSchema>;
 
         export type favoriteSuperheroSchemaInferredType = z.infer<typeof generated.favoriteSuperheroSchema>;
+
         expectType<spec.Superhero>({} as superheroSchemaInferredType)
         expectType<superheroSchemaInferredType>({} as spec.Superhero)
         expectType<spec.FavoriteSuperhero>({} as favoriteSuperheroSchemaInferredType)
@@ -153,27 +155,41 @@ describe("generate", () => {
       }
 
       export interface EvilPlanDetails {
-        parent: EvilPlan; // <- Unsolvable circular reference
+        parent: EvilPlan;
         steps: string[];
       }
+
+      export interface IHaveUnknownDependency {
+        dep: UnknwonDependency; // <- Missing dependency
+      }
       `;
 
     const { getZodSchemasFile, getIntegrationTestFile, errors } = generate({
       sourceText,
-      maxRun: 3,
     });
 
     it("should generate the zod schemas", () => {
       expect(getZodSchemasFile("./villain")).toMatchInlineSnapshot(`
         "// Generated by ts-to-zod
         import { z } from \\"zod\\";
-        import { Villain } from \\"./villain\\";
+        import { Villain, EvilPlan, EvilPlanDetails } from \\"./villain\\";
 
         export const villainSchema: z.ZodSchema<Villain> = z.lazy(() => z.object({
             name: z.string(),
             powers: z.array(z.string()),
             friends: z.array(villainSchema)
         }));
+
+        export const evilPlanSchema: z.ZodSchema<EvilPlan> = z.lazy(() => z.object({
+            owner: villainSchema,
+            description: z.string(),
+            details: evilPlanDetailsSchema
+        }));
+
+        export const evilPlanDetailsSchema: z.ZodSchema<EvilPlanDetails> = z.lazy(() => z.object({
+            parent: evilPlanSchema,
+            steps: z.array(z.string())
+        }));
         "
       `);
     });
@@ -193,8 +209,17 @@ describe("generate", () => {
         }
 
         export type villainSchemaInferredType = z.infer<typeof generated.villainSchema>;
+
+        export type evilPlanSchemaInferredType = z.infer<typeof generated.evilPlanSchema>;
+
+        export type evilPlanDetailsSchemaInferredType = z.infer<typeof generated.evilPlanDetailsSchema>;
+
         expectType<spec.Villain>({} as villainSchemaInferredType)
         expectType<villainSchemaInferredType>({} as spec.Villain)
+        expectType<spec.EvilPlan>({} as evilPlanSchemaInferredType)
+        expectType<evilPlanSchemaInferredType>({} as spec.EvilPlan)
+        expectType<spec.EvilPlanDetails>({} as evilPlanDetailsSchemaInferredType)
+        expectType<evilPlanDetailsSchemaInferredType>({} as spec.EvilPlanDetails)
         "
       `);
     });
@@ -202,9 +227,8 @@ describe("generate", () => {
     it("should have some errors", () => {
       expect(errors).toMatchInlineSnapshot(`
         Array [
-          "Some schemas can't be generated due to circular dependencies:
-        evilPlanSchema
-        evilPlanDetailsSchema",
+          "Some schemas can't be generated due to direct or indirect missing dependencies:
+        iHaveUnknownDependencySchema",
         ]
       `);
     });
@@ -366,6 +390,7 @@ describe("generate", () => {
         export type nameSchemaInferredType = z.infer<typeof generated.nameSchema>;
 
         export type badassSupermanSchemaInferredType = z.infer<typeof generated.badassSupermanSchema>;
+
         expectType<spec.Name>({} as nameSchemaInferredType)
         expectType<nameSchemaInferredType>({} as spec.Name)
         expectType<spec.BadassSuperman>({} as badassSupermanSchemaInferredType)
@@ -439,6 +464,7 @@ describe("generate", () => {
         export type metropolisSupermanSchemaInferredType = z.infer<typeof generated.metropolisSupermanSchema>;
 
         export type metropolisBadassSupermanSchemaInferredType = z.infer<typeof generated.metropolisBadassSupermanSchema>;
+
         expectType<spec.MetropolisName>({} as metropolisNameSchemaInferredType)
         expectType<metropolisNameSchemaInferredType>({} as spec.MetropolisName)
         expectType<spec.MetropolisSuperman>({} as metropolisSupermanSchemaInferredType)