CommunityToolkit / CommunityToolkit/ColorCode-Universal
Json.cs: Catastrophic regex backtracking in Regex_String causes extreme slowdown with JSON arrays
- Ngôn ngữ chính
- C#
- Star
- 265
- Fork
- 57
- Chỉ số merge pull request
- Không có pull request nào được merge trong 30 ngày
Mô tả
## 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
Hướng dẫn đóng góp
Chưa lập chỉ mục được hướng dẫn đóng góp cho kho mã nguồn này
Đánh giá
Issue này chưa được đánh giá.