Repository: tweag/nickel (rust)

Issue:
NLS crashes on recursive definitions
**Describe the bug**
`nls` crashes with stack overflow error when parsing nickel source with recursive definition.

**To Reproduce**

Open file with following content in text editor with LSP support and running `nls`.
_I can reproduce it with [lunarvim](https://www.lunarvim.org/), but this should be easily reproduce with vanilla `neovim` or any other text editor._

```nickel
{
  applications = {
    apps | not_exported = applications,
    message = "message",
  }
} 
```

**Expected behavior**

Since this is a valid nickel source code, I would expect no `nls` crashes.

```
$ nickel export test.ncl
{
  "applications": {
    "message": "message"
  }
}
```

**Environment**
 - OS name + version:

```
NAME="Fedora Linux"
VERSION="39.20240327.0 (Sericea)"
```

 - Version of the code: From nixpkgs (unstable branch).

```
nickel-lang-cli nickel 1.5.0 (rev cargore)
```

**Additional logs**

```
[START][2024-03-28 10:20:49] LSP logging initiated
[INFO][2024-03-28 10:20:49] .../vim/lsp/rpc.lua:662	"Starting RPC client"	{  args = {},  cmd = "nls",  extra = {    cwd = "/tmp/nickel"  }}
[DEBUG][2024-03-28 10:20:49] .../vim/lsp/rpc.lua:284	"rpc.send"	{  id = 1,  jsonrpc = "2.0",  method = "initialize",  params = {    capabilities = {      textDocument = {        callHierarchy = {          dynamicRegistration = false        },        codeAction = {          codeActionLiteralSupport = {            codeActionKind = {              valueSet = { "", "quickfix", "refactor", "refactor.extract", "refactor.inline", "refactor.rewrite", "source", "source.organizeImports" }            }          },          dataSupport = true,          dynamicRegistration = false,          isPreferredSupport = true,          resolveSupport = {            properties = { "edit" }          }        },        completion = {          completionItem = {            commitCharactersSupport = true,            deprecatedSupport = true,            documentationFormat = { "markdown", "plaintext" },            insertReplaceSupport = true,            insertTextModeSupport = {              valueSet = { 1, 2 }            },            labelDetailsSupport = true,            preselectSupport = true,            resolveSupport = {              properties = { "documentation", "detail", "additionalTextEdits" }            },            snippetSupport = true,            tagSupport = {              valueSet = { 1 }            }          },          completionItemKind = {            valueSet = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25 }          },          completionList = {            itemDefaults = { "commitCharacters", "editRange", "insertTextFormat", "insertTextMode", "data" }          },          contextSupport = true,          dynamicRegistration = false,          insertTextMode = 1        },        declaration = {          linkSupport = true        },        definition = {          linkSupport = true        },        documentHighlight = {          dynamicRegistration = false        },        documentSymbol = {          dynamicRegistration = false,          hierarchicalDocumentSymbolSupport = true,          symbolKind = {            valueSet = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26 }          }        },        hover = {          contentFormat = { "markdown", "plaintext" },          dynamicRegistration = false        },        implementation = {          linkSupport = true        },        publishDiagnostics = {          relatedInformation = true,          tagSupport = {            valueSet = { 1, 2 }          }        },        references = {          dynamicRegistration = false        },        rename = {          dynamicRegistration = false,          prepareSupport = true        },        semanticTokens = {          augmentsSyntaxTokens = true,          dynamicRegistration = false,          formats = { "relative" },          multilineTokenSupport = false,          overlappingTokenSupport = true,          requests = {            full = {              delta = true            },            range = false          },          serverCancelSupport = false,          tokenModifiers = { "declaration", "definition", "readonly", "static", "deprecated", "abstract", "async", "modification", "documentation", "defaultLibrary" },          tokenTypes = { "namespace", "type", "class", "enum", "interface", "struct", "typeParameter", "parameter", "variable", "property", "enumMember", "event", "function", "method", "macro", "keyword", "modifier", "comment", "string", "number", "regexp", "operator", "decorator" }        },        signatureHelp = {          dynamicRegistration = false,          signatureInformation = {            activeParameterSupport = true,            documentationFormat = { "markdown", "plaintext" },            parameterInformation = {              labelOffsetSupport = true            }          }        },        synchronization = {          didSave = true,          dynamicRegistration = false,          willSave = true,          willSaveWaitUntil = true        },        typeDefinition = {          linkSupport = true        }      },      window = {        showDocument = {          support = true        },        showMessage = {          messageActionItem = {            additionalPropertiesSupport = false          }        },        workDoneProgress = true      },      workspace = {        applyEdit = true,        configuration = true,        didChangeWatchedFiles = {          dynamicRegistration = false,          relativePatternSupport = true        },        semanticTokens = {          refreshSupport = true        },        symbol = {          dynamicRegistration = false,          hierarchicalWorkspaceSymbolSupport = true,          symbolKind = {            valueSet = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26 }          }        },        workspaceEdit = {          resourceOperations = { "rename", "create", "delete" }        },        workspaceFolders = true      }    },    clientInfo = {      name = "Neovim",      version = "0.9.5"    },    initializationOptions = vim.empty_dict(),    processId = 2230809,    rootPath = "/tmp/nickel",    rootUri = "file:///tmp/nickel",    trace = "off",    workspaceFolders = { {        name = "/tmp/nickel",        uri = "file:///tmp/nickel"      } }  }}
[DEBUG][2024-03-28 10:20:49] .../vim/lsp/rpc.lua:387	"rpc.receive"	{  id = 1,  jsonrpc = "2.0",  result = {    capabilities = {      codeActionProvider = true,      completionProvider = {        triggerCharacters = { ".", '"', "/" }      },      definitionProvider = true,      documentFormattingProvider = true,      documentSymbolProvider = true,      executeCommandProvider = {        commands = { "eval" }      },      hoverProvider = {        workDoneProgress = false      },      referencesProvider = true,      renameProvider = true,      textDocumentSync = {        change = 1,        openClose = true      }    }  }}
[DEBUG][2024-03-28 10:20:49] .../vim/lsp/rpc.lua:284	"rpc.send"	{  jsonrpc = "2.0",  method = "initialized",  params = vim.empty_dict()}
[INFO][2024-03-28 10:20:49] .../lua/vim/lsp.lua:1344	"LSP[nickel_ls]"	"server_capabilities"	{  server_capabilities = {    codeActionProvider = true,    completionProvider = {      triggerCharacters = { ".", '"', "/" }    },    definitionProvider = true,    documentFormattingProvider = true,    documentSymbolProvider = true,    executeCommandProvider = {      commands = { "eval" }    },    hoverProvider = {      workDoneProgress = false    },    referencesProvider = true,    renameProvider = true,    textDocumentSync = {      change = 1,      openClose = true    }  }}
[DEBUG][2024-03-28 10:20:49] .../vim/lsp/rpc.lua:284	"rpc.send"	{  jsonrpc = "2.0",  method = "textDocument/didOpen",  params = {    textDocument = {      languageId = "nickel",      text = '{\n  applications = {\n    apps | not_exported = applications,\n    message = "message",\n  }\n} \n',      uri = "file:///tmp/nickel/test.ncl",      version = 0    }  }}
[DEBUG][2024-03-28 10:20:49] .../lua/vim/lsp.lua:1391	"LSP[nickel_ls]"	"client.request"	1	"textDocument/documentSymbol"	{  textDocument = {    uri = "file:///tmp/nickel/test.ncl"  }}	<function 1>	1
[DEBUG][2024-03-28 10:20:49] .../vim/lsp/rpc.lua:284	"rpc.send"	{  id = 2,  jsonrpc = "2.0",  method = "textDocument/documentSymbol",  params = {    textDocument = {      uri = "file:///tmp/nickel/test.ncl"    }  }}
[DEBUG][2024-03-28 10:20:49] .../vim/lsp/rpc.lua:387	"rpc.receive"	{  jsonrpc = "2.0",  method = "textDocument/publishDiagnostics",  params = {    diagnostics = {},    uri = "file:///tmp/nickel/test.ncl"  }}
[ERROR][2024-03-28 10:20:49] .../vim/lsp/rpc.lua:734	"rpc"	"nls"	"stderr"	"\nthread 'main' has overflowed its stack\nfatal runtime error: stack overflow\n"
[ERROR][2024-03-28 10:20:49] .../vim/lsp/rpc.lua:734	"rpc"	"nls"	"stderr"	"\nthread 'main' has overflowed its stack\nfatal runtime error: stack overflow\n"
[DEBUG][2024-03-28 10:20:49] .../lua/vim/lsp.lua:1391	"LSP[nickel_ls]"	"client.request"	1	"textDocument/documentSymbol"	{  textDocument = {    uri = "file:///tmp/nickel/test.ncl"  }}	<function 1>	1
[DEBUG][2024-03-28 10:20:49] .../vim/lsp/rpc.lua:284	"rpc.send"	{  id = 3,  jsonrpc = "2.0",  method = "textDocument/documentSymbol",  params = {    textDocument = {      uri = "file:///tmp/nickel/test.ncl"    }  }}
```

Pull request description:
Fix infinite recursion in doc symbols.
Fixes #1875, hopefully.

Patch:
diff --git a/core/src/program.rs b/core/src/program.rs
index 52e5ff9a..dd185ff8 100644
--- a/core/src/program.rs
+++ b/core/src/program.rs
@@ -895,10 +895,22 @@ mod doc {
             tight: true,
         })));
 
-        list_item.append(arena.alloc(AstNode::from(NodeValue::Code(NodeCode {
+        // We have to wrap the content of the list item into a paragraph, otherwise the list won't
+        // be properly separated from the next block coming after it, producing invalid output (for
+        // example, the beginning of the documenantation of the current field might be merged with
+        // the last type or contract item).
+        //
+        // We probably shouldn't have to, but afer diving into comrak's rendering engine, it seems
+        // that some subtle interactions make things work correctly for parsed markdown (as opposed to
+        // this one being programmatically generated) just because list items are always parsed as
+        // paragraphs. We thus mimic this unspoken invariant here.
+        let paragraph = arena.alloc(AstNode::from(NodeValue::Paragraph));
+
+        paragraph.append(arena.alloc(AstNode::from(NodeValue::Code(NodeCode {
             literal: format!("{ident} {separator} {typ}"),
             num_backticks: 1,
         }))));
+        list_item.append(paragraph);
 
         list_item
     }
diff --git a/lsp/nls/src/requests/symbols.rs b/lsp/nls/src/requests/symbols.rs
index 770e7f9f..320e6d56 100644
--- a/lsp/nls/src/requests/symbols.rs
+++ b/lsp/nls/src/requests/symbols.rs
@@ -10,6 +10,10 @@ use crate::server::Server;
 use crate::term::RawSpanExt;
 use crate::world::World;
 
+// How deeply are we willing to recurse into records when resolving symbols?
+// This needs to be bounded to avoid the stack overflowing for infinitely nested records.
+const MAX_SYMBOL_DEPTH: usize = 32;
+
 // Returns a hierarchy of "publicly accessible" symbols in a term.
 //
 // Basically, if the term "evaluates" (in the sense of FieldResolver's heuristics) to a record,
@@ -19,6 +23,7 @@ fn symbols(
     world: &World,
     type_lookups: &CollectedTypes<Type>,
     rt: &RichTerm,
+    max_depth: usize,
 ) -> Vec<DocumentSymbol> {
     let resolver = FieldResolver::new(world);
     let root_records = resolver.resolve_path(rt, [].into_iter());
@@ -36,7 +41,9 @@ fn symbols(
                     crate::codespan_lsp::byte_span_to_range(world.cache.files(), file_id, span)
                         .ok()?;
 
-                let children = field.value.map(|v| symbols(world, type_lookups, &v));
+                let children = max_depth
+                    .checked_sub(1)
+                    .and_then(|depth| field.value.map(|v| symbols(world, type_lookups, &v, depth)));
 
                 #[allow(deprecated)]
                 // because the `deprecated` field is... wait for it... deprecated.
@@ -70,7 +77,7 @@ pub fn handle_document_symbols(
     let term = server.world.cache.get_ref(file_id);
 
     let mut symbols = term
-        .map(|t| symbols(&server.world, type_lookups, t))
+        .map(|t| symbols(&server.world, type_lookups, t, MAX_SYMBOL_DEPTH))
         .unwrap_or_default();
     // Sort so the response is deterministic.
     symbols.sort_by_key(|s| s.range.start);


Test patch:
diff --git a/cli/tests/snapshot/snapshots/snapshot__doc_stdout_types.ncl.snap b/cli/tests/snapshot/snapshots/snapshot__doc_stdout_types.ncl.snap
index ecb7563c..dae212a8 100644
--- a/cli/tests/snapshot/snapshots/snapshot__doc_stdout_types.ncl.snap
+++ b/cli/tests/snapshot/snapshots/snapshot__doc_stdout_types.ncl.snap
@@ -6,4 +6,5 @@ expression: out
 
 - `Hello : Number`
 - `Hello | std.string.Stringable`
+
 World\!
diff --git a/lsp/nls/tests/inputs/symbols-recursion.ncl b/lsp/nls/tests/inputs/symbols-recursion.ncl
new file mode 100644
index 00000000..54b8cad0
--- /dev/null
+++ b/lsp/nls/tests/inputs/symbols-recursion.ncl
@@ -0,0 +1,7 @@
+### /syms.ncl
+let rec foo = { bar = foo } in foo
+### # In principle there are infinitely many symbols, but we bound the recursion instead
+### # of crashing.
+### [[request]]
+### type = "Symbols"
+### textDocument.uri = "file:///syms.ncl"
diff --git a/lsp/nls/tests/snapshots/main__lsp__nls__tests__inputs__symbols-recursion.ncl.snap b/lsp/nls/tests/snapshots/main__lsp__nls__tests__inputs__symbols-recursion.ncl.snap
new file mode 100644
index 00000000..b8263f82
--- /dev/null
+++ b/lsp/nls/tests/snapshots/main__lsp__nls__tests__inputs__symbols-recursion.ncl.snap
@@ -0,0 +1,5 @@
+---
+source: lsp/nls/tests/main.rs
+expression: output
+---
+[bar (Variable / "Dyn")@0:16-0:19 in 0:16-0:19: [bar (Variable / "Dyn")@0:16-0:19 in 0:16-0:19: [bar (Variable / "Dyn")@0:16-0:19 in 0:16-0:19: [bar (Variable / "Dyn")@0:16-0:19 in 0:16-0:19: [bar (Variable / "Dyn")@0:16-0:19 in 0:16-0:19: [bar (Variable / "Dyn")@0:16-0:19 in 0:16-0:19: [bar (Variable / "Dyn")@0:16-0:19 in 0:16-0:19: [bar (Variable / "Dyn")@0:16-0:19 in 0:16-0:19: [bar (Variable / "Dyn")@0:16-0:19 in 0:16-0:19: [bar (Variable / "Dyn")@0:16-0:19 in 0:16-0:19: [bar (Variable / "Dyn")@0:16-0:19 in 0:16-0:19: [bar (Variable / "Dyn")@0:16-0:19 in 0:16-0:19: [bar (Variable / "Dyn")@0:16-0:19 in 0:16-0:19: [bar (Variable / "Dyn")@0:16-0:19 in 0:16-0:19: [bar (Variable / "Dyn")@0:16-0:19 in 0:16-0:19: [bar (Variable / "Dyn")@0:16-0:19 in 0:16-0:19: [bar (Variable / "Dyn")@0:16-0:19 in 0:16-0:19: [bar (Variable / "Dyn")@0:16-0:19 in 0:16-0:19: [bar (Variable / "Dyn")@0:16-0:19 in 0:16-0:19: [bar (Variable / "Dyn")@0:16-0:19 in 0:16-0:19: [bar (Variable / "Dyn")@0:16-0:19 in 0:16-0:19: [bar (Variable / "Dyn")@0:16-0:19 in 0:16-0:19: [bar (Variable / "Dyn")@0:16-0:19 in 0:16-0:19: [bar (Variable / "Dyn")@0:16-0:19 in 0:16-0:19: [bar (Variable / "Dyn")@0:16-0:19 in 0:16-0:19: [bar (Variable / "Dyn")@0:16-0:19 in 0:16-0:19: [bar (Variable / "Dyn")@0:16-0:19 in 0:16-0:19: [bar (Variable / "Dyn")@0:16-0:19 in 0:16-0:19: [bar (Variable / "Dyn")@0:16-0:19 in 0:16-0:19: [bar (Variable / "Dyn")@0:16-0:19 in 0:16-0:19: [bar (Variable / "Dyn")@0:16-0:19 in 0:16-0:19: [bar (Variable / "Dyn")@0:16-0:19 in 0:16-0:19: [bar (Variable / "Dyn")@0:16-0:19 in 0:16-0:19: []]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]