Skip to content

Long virtual document URI causes quadratic path normalization #3501

Open

Description

@net-sky

How are you using the lua-language-server?

Visual Studio Code Extension (sumneko.lua)

Which OS are you using?

Windows

What is the issue affecting?

Diagnostics/Syntax Checking

Expected Behaviour

A textDocument/didOpen for a virtual document should not block the server, regardless of the URI length. The server should keep answering queued requests.

Actual Behaviour

A didOpen whose URI embeds a long payload (a virtual diff document; the URI carries the whole file as URL-encoded base64) makes the server spin at 100% of one core for minutes and stops answering every queued request until it finishes.

  • lua-language-server 3.19.2, Windows 10 x64, 16 logical cores
  • Memory stays flat (145–173 MB), so this is not GC/allocation related
  • didOpen itself took 376.349 s in my session; the queued documentColor / inlayHint / codeAction / codeLens / semanticTokens / documentSymbol / foldingRange / $/cancelRequest requests all returned afterwards, each taking 216 s
  • The code is unchanged on master (script/files.lua:964, script/workspace/workspace.lua:272), so upgrading does not help

Reproduction steps

Any LSP client, after initialize:

  1. textDocument/didOpen a short, normal file: document, so the workspace becomes ready.

  2. textDocument/didOpen a virtual document whose URI has a long payload with no path separators:

    uri  = "genie-diff:x.lua?" .. string.rep("a", 100000)
    text = "local a = 1"
    
  3. Send any request afterwards (e.g. textDocument/hover).

The second document is never acknowledged within 25 s in my harness, and the server burns 100% of one CPU core. Only URI length and the absence of /, \, . matter:

URI payload Time until the server responds again
26,000 chars, no separator ~18 s
104,000 chars, no separator > 300 s
104,000 chars, one / every 64 chars 46 ms

A long document text with a short URI, or a short URI without a query, is fast. The real-world URI is 104,129 chars long; its payload is URL-encoded base64 with zero /, \ and . (+ and / are escaped as %2B / %2F).

Additional Notes

Root cause

files.open() dispatches the open watchers synchronously, and the diagnostics watcher reaches ws.isIgnored() from inside the didOpen handler:

provider/provider.lua → files.open(uri) → provider/diagnostic.lua doDiagnostic → isValid → workspace.isIgnored(uri) → workspace.getRelativePath(uri).

getRelativePath treats any string that does not start with file: as a filesystem path, so the whole 100 KB URI is passed to files.normalize(path). There, this loop:

path, count = path:gsub('[^/\\]+[/\\]+%.%.[/\\]', '/', 1)

requires a / or \ after a run of non-separator characters. In a URL-encoded base64 payload there is no separator at all, so the match fails at every start position: Lua's pattern engine greedily matches to the end of the string and then backtracks over it — O(n²), roughly 5.4×10⁹ steps for 104 k characters.

Note that the default Lua.diagnostics.enableScheme (["file"]) does not prevent this, because it is checked after ws.isIgnored().

Suggested fix

  1. In files.normalize, only run the ..-folding loop when the string can contain .. and is short enough to be a real path:
if #path <= 4096 and path:find('..', 1, true) then
    for _ = 1, 1000 do
        ...
    end
end

This cannot change the result: the gsub can never match without a literal .., and the guard is a plain (linear) search.

  1. In workspace.isIgnored, return false for non-file: schemes before any path work, since ignore patterns are filesystem paths:
local scheme = uri:match('^(%a[%w+.-]*):')
if scheme and #scheme > 1 and scheme ~= 'file' then
    return false
end

With both changes the same 104 k-character didOpen returns within ~3 s in my harness (client-side delays included) and the follow-up request is answered. I have a PR with the two changes plus a regression test (test/basic/uri-normalize.lua) ready.

Workaround

Restart the language server (Lua: Stop Server / Lua: Start Server); avoid virtual diff views that embed a whole file in the document URI.

Log File

Redacted excerpt (the URI contains the whole source file, so it is trimmed here):

[17:13:06.609][warn] [#0:script\proto\proto.lua:189]: Method [textDocument/didOpen] takes [142.577]sec. {
    params = { textDocument = { uri = "genie-diff:promptbasic.lua?<104129 chars, redacted>", ... } } }
[17:19:22.963][warn] [#0:script\proto\proto.lua:189]: Method [textDocument/didOpen] takes [376.349]sec. { ... }
[17:22:59.389][warn] [#0:script\proto\proto.lua:189]: Method [$/cancelRequest] takes [216.426]sec. { ... }
[17:22:59.389][warn] [#0:script\proto\proto.lua:189]: Method [textDocument/documentColor] takes [216.427]sec. { ... }
[17:22:59.535][warn] [#0:script\proto\proto.lua:189]: Method [textDocument/foldingRange] takes [216.569]sec. { ... }

The full log can be provided privately if needed.

Activity

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Type

    No type

    Projects

    No projects

      Milestone

      No milestone

      Relationships

      None yet

      Development

      No branches or pull requests

      Issue actions