CommunityToolkit / CommunityToolkit/ColorCode-Universal

Json.cs: Catastrophic regex backtracking in Regex_String causes extreme slowdown with JSON arrays

未关闭
#45 0 条评论 0 个 reaction 已指派 0 人 在 GitHub 查看
主要语言
C#
星标
265
派生
57
PR 合并指标
30 天内没有已合并 PR

描述

## Description

The JSON language definition in the underlying [ColorCode-Universal](https://github.com/CommunityToolkit/ColorCode-Universal) dependency (`ColorCode.Core/Compilation/Languages/Json.cs`) contains a **catastrophic backtracking** bug in its `Regex_String` pattern. This causes **exponential processing time (O(2^n))** when colorizing JSON that contains arrays with string values, making the application appear completely frozen.

The pattern is:

```
"[^"\\]*(?:\\[^\r\n]|[^"\\]*)*"
```

The repeating group `(?:\\[^\r\n]|[^"\\]*)` has two alternatives:
- `\\[^\r\n]` — backslash escape, always consumes 2 characters ✓
- `[^"\\]*` — **can match an empty string** ✗

The key-matching rule `[,{]\s*("...")\s*:` attempts to match JSON keys (string followed by `:`). For every `,` inside a JSON array, the engine tries this rule, matches the string value (e.g. `"John Doe"`), but fails when no `:` follows. On failure, the engine backtracks into the string subpattern and tries **all possible ways to partition** the `n` non-special characters between the outer `[^"\\]*` and the inner `(?:[^"\\]*)` repetition — resulting in **O(2^n) backtracking states**. For a 16-character string value this is ~65,000 states; for longer strings the number grows exponentially.

The fix is to replace the pattern with **Friedl's Unrolled Loop**:

```
"[^"\\]*(?:\\.[^"\\]*)*"
```

Each iteration of the group now **must** consume at least 2 characters via `\\.`, eliminating the empty alternative and all backtracking.

## Expected Behaviour

JSON arrays with string values are colorized in milliseconds, identical to simple JSON objects without arrays.

## Actual Behaviour

Colorizing JSON containing arrays with string values causes extreme slowdown. Processing time grows exponentially with the length of string values inside arrays. Simple JSON objects (no arrays) are not affected.

## Affected Version

3.0.1

## Steps to Reproduce

1. Set up a Markdig pipeline with `UseColorCode()`
2. Call `Markdig.Markdown.ToHtml()` on a Markdown document containing the following fenced code block:

````markdown
```json
{
"Project": "My Project",
"Tags": [
"first long string value",
"another long string value"
]
}
```
````

3. Observe that processing takes several seconds (or longer) instead of being near-instantaneous
4. Note that removing the array (keeping only simple key-value pairs) restores normal performance

**Workaround** (until the underlying bug is fixed in ColorCode-Universal): pass a corrected JSON language definition via `additionalLanguages`:

```csharp
var pipeline = new MarkdownPipelineBuilder()
.UseAdvancedExtensions()
.UseColorCode(additionalLanguages: new[] { new JsonLanguageFixed() })
.Build();
```

```csharp
// Friedl's Unrolled Loop – no backtracking, correct escape handling
private sealed class JsonLanguageFixed : ILanguage
{
private const string RegexString = @"""[^""\\]*(?:\\.[^""\\]*)*""";
private const string RegexNumber = @"-?(?:0|[1-9][0-9]*)(?:\.[0-9]*)?(?:[eE][-+]?[0-9]+)?";

public string Id => LanguageId.Json;
public string Name => "JSON";
public string CssClassName => "json";
public string FirstLinePattern => null;

public IList Rules => new List
{
new LanguageRule($@"[,\{{]\s*({RegexString})\s*:", new Dictionary { { 1, ScopeName.JsonKey } }),
new LanguageRule(RegexString, new Dictionary { { 0, ScopeName.JsonString } }),
new LanguageRule(RegexNumber, new Dictionary { { 0, ScopeName.JsonNumber } }),
new LanguageRule(@"\b(true|false|null)\b", new Dictionary { { 1, ScopeName.JsonConst } }),
};

public bool HasAlias(string lang) => false;
}
```

## Checklist

- [x] I have read the [contributing guidelines](https://github.com/wbaldoumas/markdown-colorcode/blob/main/CONTRIBUTING.md)
- [x] I have verified this does not duplicate an existing issue

贡献指南

这个仓库没有索引到贡献指南

评估

这个 Issue 还没有评估数据。

把新 issue 发到你的邮箱

精选适合新手参与的 GitHub issue 摘要。