Repository: elm-tooling/elm-language-server
Pull request #431 (2020-12-30 17:11:02)

Recursion improvements
Part of #406. Adds recursion errors for let declarations and type aliases. Also improved all recursion error messages to show the cycles. I did a lot of A/B testing with the compiler to get the error locations and messages the same and added tests for all the different cases.


Patch:
diff --git a/CHANGELOG.md b/CHANGELOG.md
index 71d4856..23d69ac 100644
--- a/CHANGELOG.md
+++ b/CHANGELOG.md
@@ -1,36 +1,5 @@
 # Change Log
 
-## 2.0.0
-
-### Features
-
-- Enabled type checking diagnostics that update on document change. These include parsing errors, type mismatch errors, value not found errors, etc
-- Support file events APIs (Previously VSCode only)
-
-  - On file create, the module name will be inserted
-  - On file rename, the module name and all references will be updated
-
-- A new "extract function" code action. Select a complete expression and it can be extracted to a function in the top level or the enclosing let expression (if there is one)
-- Replaced elm-analyse with our own diagnostics, there might be missing rules for you due to this
-- Show inferred type information on hovers
-- Support linked editing ranges. When editing a function name, the type annotation name will auto rename, or vice versa (needs to be enabled in most clients)
-- Watch elm.json for changes. The server will restart when a change is detected
-- Run elm make on server init
-- Improve record completions
-
-### Bug Fixes
-
-- Greatly improve performance of diagnostics and type inference
-- Fix some type inference cases
-- Fix module resolution to be more like how the compiler resolves modules
-- Fix some incorrect unused value diagnostics
-- Fix how errors from third party binaries are shown
-
-### Other Changes
-
-- Update package rankings
-- Update our parser
-
 ## 1.13.2
 
 - Fix bug on file open
diff --git a/src/providers/diagnostics/elmMakeDiagnostics.ts b/src/providers/diagnostics/elmMakeDiagnostics.ts
index 0d821b6..da6f03f 100644
--- a/src/providers/diagnostics/elmMakeDiagnostics.ts
+++ b/src/providers/diagnostics/elmMakeDiagnostics.ts
@@ -134,10 +134,6 @@ export class ElmMakeDiagnostics {
     return this.convertDiagnosticsToCodeActions(elmMakeDiagnostics, uri);
   }
 
-  private hasType(error: any): error is IElmError | IElmCompilerError {
-    return "type" in error;
-  }
-
   private convertDiagnosticsToCodeActions(
     diagnostics: IDiagnostic[],
     uri: string,
@@ -460,7 +456,7 @@ export class ElmMakeDiagnostics {
         const execaError = error as execa.ExecaReturnValue<string>;
         const lines: IElmIssue[] = [];
         execaError.stderr.split("\n").forEach((line: string) => {
-          let errorObject: unknown;
+          let errorObject: any;
           try {
             errorObject = JSON.parse(line);
           } catch (error) {
@@ -469,13 +465,8 @@ export class ElmMakeDiagnostics {
             );
           }
 
-          if (
-            errorObject &&
-            this.hasType(errorObject) &&
-            errorObject.type === "compile-errors"
-          ) {
-            const compilerError = errorObject as IElmCompilerError;
-            compilerError.errors.forEach((error: IError) => {
+          if (errorObject && errorObject.type === "compile-errors") {
+            errorObject.errors.forEach((error: IError) => {
               const problems: IElmIssue[] = error.problems.map(
                 (problem: IProblem) => ({
                   details: problem.message
@@ -500,25 +491,18 @@ export class ElmMakeDiagnostics {
 
               lines.push(...problems);
             });
-          } else if (
-            errorObject &&
-            this.hasType(errorObject) &&
-            errorObject.type === "error"
-          ) {
-            const error = errorObject as IElmError;
-            this.checkIfVersionMismatchesAndCreateMessage(error);
-
+          } else if (errorObject && errorObject.type === "error") {
             const problem: IElmIssue = {
-              details: error.message
+              details: errorObject.message
                 .map((message: string | IStyledString) =>
                   typeof message === "string" ? message : message.string,
                 )
                 .join(""),
               // elm-test might supply absolute paths to files
-              file: error.path
-                ? path.relative(workspaceRootPath, error.path)
+              file: errorObject.path
+                ? path.relative(workspaceRootPath, errorObject.path)
                 : relativePathsToFiles[0],
-              overview: error.title,
+              overview: errorObject.title,
               region: {
                 end: {
                   column: 1,
@@ -541,17 +525,4 @@ export class ElmMakeDiagnostics {
       }
     }
   }
-  private checkIfVersionMismatchesAndCreateMessage(
-    errorObject: IElmError,
-  ): void {
-    if (errorObject.title === "ELM VERSION MISMATCH") {
-      this.connection.window.showErrorMessage(
-        errorObject.message
-          .map((message: string | IStyledString) =>
-            typeof message === "string" ? message : message.string,
-          )
-          .join(""),
-      );
-    }
-  }
 }
diff --git a/src/util/types/diagnostics.ts b/src/util/types/diagnostics.ts
index fd25654..6d507fc 100644
--- a/src/util/types/diagnostics.ts
+++ b/src/util/types/diagnostics.ts
@@ -82,11 +82,6 @@ export const Diagnostics = {
     "Could not find a module to import named `{0}` in `dependencies` or `source-directories`.",
     DiagnosticSeverity.Error,
   ),
-  InfiniteRecursion: diag(
-    "infinite_recursion",
-    "Infinite recursion.",
-    DiagnosticSeverity.Error,
-  ),
   InvalidPattern: diag(
     "invalid_pattern",
     "Invalid pattern error.\nExpected: `{0}`\nFound: `{1}`",
@@ -128,6 +123,42 @@ export const Diagnostics = {
     "The record does not have a `{0}` field.",
     DiagnosticSeverity.Error,
   ),
+  RecursiveAlias: (n: number): IDiagnosticMessage =>
+    diag(
+      "recursive_alias",
+      n < 2
+        ? "Alias problem. This type alias is recursive, forming an infinite type."
+        : `Alias problem. This type alias is part of a mutually recursive set of type aliases:\n${Array.from(
+            Array(n).keys(),
+          )
+            .map((i) => `{${i}}`)
+            .join(" -> ")}`,
+      DiagnosticSeverity.Error,
+    ),
+  RecursiveDeclaration: (n: number): IDiagnosticMessage =>
+    diag(
+      "recursive_declaration",
+      n < 2
+        ? "Cyclic definition. The value `{0}` is defined directly in terms of itself, causing an infinite loop."
+        : `Cyclic definition. The value \`{0}\`  depends on itself through the following chain of definitions:\n${Array.from(
+            Array(n).keys(),
+          )
+            .map((i) => `{${i}}`)
+            .join(" -> ")}`,
+      DiagnosticSeverity.Error,
+    ),
+  RecursiveLet: (n: number): IDiagnosticMessage =>
+    diag(
+      "recursive_let",
+      n < 2
+        ? "Cyclic value. The value `{0}` is defined directly in terms of itself, causing an infinite loop."
+        : `Cyclic value. The value \`{0}\` depends on itself through the following chain of definitions:\n${Array.from(
+            Array(n).keys(),
+          )
+            .map((i) => `{${i}}`)
+            .join(" -> ")}`,
+      DiagnosticSeverity.Error,
+    ),
   Redefinition: diag(
     "redefinition",
     "A value named `{0}` is already defined.",
diff --git a/src/util/types/typeChecker.ts b/src/util/types/typeChecker.ts
index b35bb6b..8cd92a2 100644
--- a/src/util/types/typeChecker.ts
+++ b/src/util/types/typeChecker.ts
@@ -890,6 +890,7 @@ export function createTypeChecker(workspace: IElmWorkspace): TypeChecker {
       valueDeclaration.tree.uri,
       workspace,
       new Set(),
+      /* recursionAllowed */ false,
       cancellationToken,
     );
     result.diagnostics.forEach((diagnostic) => diagnostics.add(diagnostic));
diff --git a/src/util/types/typeExpression.ts b/src/util/types/typeExpression.ts
index 379c7d5..f046ffa 100644
--- a/src/util/types/typeExpression.ts
+++ b/src/util/types/typeExpression.ts
@@ -231,11 +231,6 @@ export class TypeExpression {
   private inferTypeAliasDeclaration(
     declaration: ETypeAliasDeclaration,
   ): InferenceResult {
-    if (this.activeAliases.has(declaration)) {
-      this.diagnostics.push(error(declaration, Diagnostics.InfiniteRecursion));
-      return this.toResult(TUnknown);
-    }
-
     this.activeAliases.add(declaration);
 
     const type = declaration.typeExpression
@@ -427,11 +422,38 @@ export class TypeExpression {
           ).type;
           break;
         case "TypeAliasDeclaration":
-          declaredType = TypeExpression.typeAliasDeclarationInference(
-            definition.expr,
-            this.workspace,
-            new Set(this.activeAliases.values()),
-          ).type;
+          {
+            // Check for recursion
+            const aliases = Array.from(this.activeAliases);
+            const recursiveAlias = aliases.find(
+              (decl) => decl.id === definition.expr.id,
+            );
+            if (recursiveAlias) {
+              const name = definition.expr.childForFieldName("name");
+              const index = aliases.findIndex(
+                (alias) => alias.id === recursiveAlias.id,
+              );
+              if (name) {
+                const slicedAliases = aliases.slice(index);
+                this.diagnostics.push(
+                  error(
+                    name,
+                    Diagnostics.RecursiveAlias(slicedAliases.length),
+                    ...slicedAliases.map(
+                      (alias) => alias.childForFieldName("name")?.text ?? "",
+                    ),
+                  ),
+                );
+              }
+              declaredType = TUnknown;
+            } else {
+              declaredType = TypeExpression.typeAliasDeclarationInference(
+                definition.expr,
+                this.workspace,
+                new Set(this.activeAliases.values()),
+              ).type;
+            }
+          }
           break;
         default:
           throw new Error("Unexpected type reference");
diff --git a/src/util/types/typeInference.ts b/src/util/types/typeInference.ts
index f18630f..4890d7c 100644
--- a/src/util/types/typeInference.ts
+++ b/src/util/types/typeInference.ts
@@ -555,6 +555,7 @@ export class InferenceScope {
     uri: string,
     program: IElmWorkspace,
     activeScopes: Set<EValueDeclaration>,
+    recursionAllowed = false,
     cancellationToken?: ICancellationToken,
   ): InferenceResult {
     const nonShadowableNames =
@@ -567,7 +568,7 @@ export class InferenceScope {
         program,
         nonShadowableNames,
         new Set(activeScopes.values()),
-        /* recursionAllowed */ false,
+        recursionAllowed,
         cancellationToken,
       ).inferDeclaration(declaration, true);
 
@@ -640,20 +641,67 @@ export class InferenceScope {
   }
 
   private checkRecursion(declaration: EValueDeclaration): boolean {
-    const isRecursive = !!Array.from(this.activeScopes.values()).find(
-      (d) => d.id === declaration.id,
-    );
+    let scopes = Array.from(this.activeScopes.values());
+    const index = scopes.findIndex((decl) => decl.id === declaration.id);
 
-    const functionDeclaration = mapSyntaxNodeToExpression(
-      declaration.childForFieldName("functionDeclarationLeft"),
-    );
+    const isRecursive = index >= 0;
+
+    if (isRecursive) {
+      // We only want scopes in the recursion loop
+      scopes = scopes.slice(index);
+    }
+
+    // Handle top level declaration recursion
     if (
       isRecursive &&
       !this.recursionAllowed &&
-      (functionDeclaration?.nodeType !== "FunctionDeclarationLeft" ||
-        !functionDeclaration.params[0])
+      declaration.parent?.type === "file"
     ) {
-      this.diagnostics.push(error(declaration, Diagnostics.InfiniteRecursion));
+      const callChain = scopes.filter(
+        (decl) => decl.parent?.id === declaration.parent?.id,
+      );
+
+      if (callChain.every((decl) => decl.params.length === 0)) {
+        const mapped = callChain.map(
+          (decl) => decl.firstNamedChild?.firstNamedChild?.text ?? "",
+        );
+
+        this.diagnostics.push(
+          error(
+            declaration.firstNamedChild!,
+            Diagnostics.RecursiveDeclaration(mapped.length),
+            ...mapped,
+          ),
+        );
+      }
+    }
+
+    // Handle let recursion
+    if (isRecursive && declaration.parent?.type === "let_in_expr") {
+      const callChain = scopes
+        .filter((decl) => decl.parent?.id === declaration.parent?.id)
+        .reverse();
+
+      const recursiveLet = callChain.find((decl) => decl.params.length === 0);
+
+      if (recursiveLet?.firstNamedChild) {
+        const reversed = callChain
+          .reverse()
+          .map((decl) => decl.firstNamedChild?.firstNamedChild?.text ?? "");
+
+        const rotated = Utils.rotateArray(
+          reversed,
+          reversed.indexOf(recursiveLet.firstNamedChild.text),
+        );
+
+        this.diagnostics.push(
+          error(
+            recursiveLet.firstNamedChild,
+            Diagnostics.RecursiveLet(callChain.length),
+            ...rotated,
+          ),
+        );
+      }
     }
 
     return isRecursive;
@@ -1068,6 +1116,7 @@ export class InferenceScope {
             declaration.tree.uri,
             this.elmWorkspace,
             this.activeScopes,
+            this.recursionAllowed,
             this.cancellationToken,
           ).type
         : parentScope.inferChildDeclaration(declaration, this.activeScopes)
diff --git a/src/util/utils.ts b/src/util/utils.ts
index 4b9b628..540a30c 100644
--- a/src/util/utils.ts
+++ b/src/util/utils.ts
@@ -73,4 +73,13 @@ export class Utils {
 
     return [startIndex, endIndex];
   }
+
+  public static rotateArray<T>(array: T[], newStartIndex: number): T[] {
+    const newArray = [];
+    for (let i = 0; i < array.length; i++) {
+      newArray.push(array[newStartIndex]);
+      newStartIndex = (newStartIndex + 1) % array.length;
+    }
+    return newArray;
+  }
 }


Test patch:
diff --git a/test/diagnosticTests/elmDiagnostics.test.ts b/test/diagnosticTests/elmDiagnostics.test.ts
index 57c8664..fbdb436 100644
--- a/test/diagnosticTests/elmDiagnostics.test.ts
+++ b/test/diagnosticTests/elmDiagnostics.test.ts
@@ -320,11 +320,11 @@ func2 =
     await testTypeInference(basicsSources + source, [], true);
 
     const source2 = `
-    --@ Test.elm
+--@ Test.elm
 module Test exposing (..)
 
 func =
-     --^
+--^
     let
         go =
             if False then
@@ -337,7 +337,437 @@ func =
       `;
     await testTypeInference(
       basicsSources + source2,
-      [{ message: Diagnostics.InfiniteRecursion, args: [] }],
+      [{ message: Diagnostics.RecursiveDeclaration(1), args: ["func"] }],
+      true,
+    );
+  });
+
+  test("mutual let recursion", async () => {
+    const source = `
+--@ Test.elm
+module Test exposing (..)
+
+func =
+    let
+        go n =
+            if n == 1 then
+                "text"
+
+            else
+                to n
+
+        to =
+      --^
+            go
+    in
+    go
+  `;
+    await testTypeInference(
+      basicsSources + source,
+      [{ message: Diagnostics.RecursiveLet(2), args: ["to", "go"] }],
+      true,
+    );
+
+    const source2 = `
+--@ Test.elm
+module Test exposing (..)
+
+func =
+    let
+        go n =
+            if n == 1 then
+                "text"
+
+            else
+                to n
+
+        to n =
+            go n
+    in
+    go
+  `;
+    await testTypeInference(basicsSources + source2, [], true);
+
+    // Recusion through 3 let declarations
+    const source3 = `
+--@ Test.elm
+module Test exposing (..)
+
+func =
+    let
+        go n =
+            if n == 1 then
+                "text"
+
+            else
+                to n
+ 
+        to =
+            another
+
+        another =
+        --^
+            go
+    in
+    go
+  `;
+    await testTypeInference(
+      basicsSources + source3,
+      [
+        {
+          message: Diagnostics.RecursiveLet(3),
+          args: ["another", "go", "to"],
+        },
+      ],
+      true,
+    );
+
+    const source4 = `
+--@ Test.elm
+module Test exposing (..)
+
+func =
+    let
+        go n =
+            if n == 1 then
+                "text"
+
+            else
+                to n
+
+        another =
+        --^
+            go
+
+        to =
+            another
+    in
+    go
+  `;
+    await testTypeInference(
+      basicsSources + source4,
+      [{ message: Diagnostics.RecursiveLet(3), args: ["another", "go", "to"] }],
+      true,
+    );
+
+    const source5 = `
+--@ Test.elm
+module Test exposing (..)
+
+func =
+    let
+        go n =
+            if n == 1 then
+                "text"
+
+            else
+                to n
+
+        another n =
+            go
+
+        to =
+      --^
+            another
+    in
+    go
+  `;
+    await testTypeInference(
+      basicsSources + source5,
+      [{ message: Diagnostics.RecursiveLet(3), args: ["to", "another", "go"] }],
+      true,
+    );
+
+    const source6 = `
+--@ Test.elm
+module Test exposing (..)
+
+func =
+    let
+        go =
+      --^
+            to
+
+        to =
+            go
+    in
+    go
+  `;
+    // FAILING - but not a big deal, since the error is just on `to` instead. Didn't see an easy way to solve this one
+    // await testTypeInference(
+    //   basicsSources + source6,
+    //   [{ message: Diagnostics.RecursiveLet(2), args: ["go", "to"] }],
+    //   true,
+    // );
+
+    const source7 = `
+--@ Test.elm
+module Test exposing (..)
+
+func =
+    let
+        go =
+            to
+
+        to =
+            another
+
+        another =
+        --^
+            to
+    in
+    go
+  `;
+    await testTypeInference(
+      basicsSources + source7,
+      [{ message: Diagnostics.RecursiveLet(2), args: ["another", "to"] }],
+      true,
+    );
+  });
+
+  test("recursion between declarations and let declarations", async () => {
+    const source = `
+--@ Test.elm
+module Test exposing (..)
+
+func =
+    let
+        go n =
+            if n == 1 then
+                "text"
+
+            else
+                to n
+
+        to n =
+            func2
+    in
+    go
+
+
+func2 =
+    func
+  `;
+    await testTypeInference(basicsSources + source, [], true);
+  });
+
+  test("recursion between declarations", async () => {
+    const source = `
+    --@ Test.elm
+func =
+--^
+    func2
+
+
+func2 =
+    func3
+
+
+func3 =
+    func
+      `;
+    await testTypeInference(
+      basicsSources + source,
+      [
+        {
+          message: Diagnostics.RecursiveDeclaration(3),
+          args: ["func", "func2", "func3"],
+        },
+      ],
+      true,
+    );
+
+    const source2 = `
+    --@ Test.elm
+func =
+--^
+    func
+      `;
+    await testTypeInference(
+      basicsSources + source2,
+      [
+        {
+          message: Diagnostics.RecursiveDeclaration(1),
+          args: ["func"],
+        },
+      ],
+      true,
+    );
+
+    const source3 = `
+    --@ Test.elm
+func =
+    func2 
+
+
+func2 =
+    func3
+
+
+func3 a =
+    func
+      `;
+    await testTypeInference(basicsSources + source3, [], true);
+
+    const source4 = `
+    --@ Test.elm
+func =
+    func2
+
+func2 =
+--^
+    func3
+
+func3 =
+    func2
+      `;
+    await testTypeInference(
+      basicsSources + source4,
+      [
+        {
+          message: Diagnostics.RecursiveDeclaration(2),
+          args: ["func2", "func3"],
+        },
+      ],
+      true,
+    );
+  });
+
+  xtest("infinite type error", async () => {
+    const source = `
+--@ Test.elm
+module Test exposing (..)
+
+func =
+    \\_ -> func
+  `;
+    await testTypeInference(
+      basicsSources + source,
+      [
+        // Infinte type error
+      ],
+      true,
+    );
+
+    const source2 = `
+--@ Test.elm
+module Test exposing (..)
+
+func =
+    let
+        go n =
+            go
+    in
+    go
+  `;
+    await testTypeInference(
+      basicsSources + source2,
+      [
+        // Infinte type error
+      ],
+      true,
+    );
+
+    const source3 = `
+--@ Test.elm
+module Test exposing (..)
+
+func =
+    let
+        go n =
+            func
+    in
+    go
+  `;
+    await testTypeInference(
+      basicsSources + source3,
+      [
+        // Infinte type error
+      ],
+      true,
+    );
+  });
+
+  test("type alias recursion", async () => {
+    const source = `
+--@ Test.elm
+module Test exposing (..)
+
+type alias Test =
+          --^
+    { field : Test
+    }
+  `;
+    await testTypeInference(
+      basicsSources + source,
+      [{ message: Diagnostics.RecursiveAlias(0), args: [] }],
+      true,
+    );
+
+    const source2 = `
+--@ Test.elm
+module Test exposing (..)
+
+type alias Test =
+          --^
+    { field : Test2
+    }
+
+
+type alias Test2 =
+    Test
+  `;
+    await testTypeInference(
+      basicsSources + source2,
+      [{ message: Diagnostics.RecursiveAlias(2), args: ["Test", "Test2"] }],
+      true,
+    );
+
+    const source3 = `
+--@ Test.elm
+module Test exposing (..)
+
+type alias Test =
+    { field : Test2
+    }
+
+type alias Test2 =
+          --^
+    Test3 
+
+type alias Test3 =
+    Test2
+  `;
+    await testTypeInference(
+      basicsSources + source3,
+      [{ message: Diagnostics.RecursiveAlias(2), args: ["Test2", "Test3"] }],
+      true,
+    );
+
+    const source4 = `
+--@ Test.elm
+module Test exposing (..)
+
+type alias Test =
+          --^
+    { field : Test2
+    }
+
+type alias Test2 =
+    Test3 
+
+type alias Test3 =
+    { field : Test
+    }
+  `;
+    await testTypeInference(
+      basicsSources + source4,
+      [
+        {
+          message: Diagnostics.RecursiveAlias(3),
+          args: ["Test", "Test2", "Test3"],
+        },
+      ],
       true,
     );
   });