Skip to content

Commit e9d55db

Browse files
shengyfuCopilot
andauthored
Fix Unicode case folding in indexed fixed-string searches (#174)
* Fix Unicode case folding in indexed fixed-string searches Co-authored-by: Copilot App <[email protected]> * Avoid panicking when literal query planning fails Co-authored-by: Copilot App <[email protected]> --------- Co-authored-by: Copilot App <[email protected]>
1 parent 2bb52ff commit e9d55db

3 files changed

Lines changed: 200 additions & 11 deletions

File tree

‎README.md‎

Lines changed: 4 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -620,7 +620,10 @@ exit code determined by the search alone. Suppress the message with
620620
2. **Querying** decomposes regex literals into trigram lookups, intersects or
621621
unions posting lists, and verifies candidates with the full regex engine.
622622
Inline case flags participate in planning; unsupported constructs use
623-
conservative plans rather than excluding possible matches.
623+
conservative plans rather than excluding possible matches. Case-insensitive
624+
fixed strings use the same Unicode-aware planning after escaping regex
625+
syntax. Both paths require only trigrams safe for the index's ASCII folding;
626+
if none remain, all indexed files are candidates.
624627
3. **Serving** combines a memory-mapped `IndexReader` with a mutable `LiveIndex`
625628
overlay in `HybridIndex`. Updates take precedence over disk entries.
626629
Clients use JSON-RPC 2.0 over newline-delimited TCP on loopback, with one

‎tgrep-cli/tests/ripgrep_compat.rs‎

Lines changed: 90 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -326,6 +326,96 @@ fn indexed_inline_case_flags_keep_candidates_selective() {
326326
});
327327
}
328328

329+
#[test]
330+
fn indexed_fixed_strings_preserve_unicode_case_folds() {
331+
let dir = TempDir::new().unwrap();
332+
let root = dir.path().join("testdata");
333+
fs::create_dir_all(&root).unwrap();
334+
for (name, content) in [
335+
("upper_accent.txt", "CAF\u{c9}\n"),
336+
("upper_fullwidth.txt", "\u{ff29}\u{ff24}\n"),
337+
("long_s_kelvin.txt", "\u{17f}hell\u{17f}hoc\u{212a}\n"),
338+
("short_fold.txt", "\u{17f}\u{212a}\u{17f}\n"),
339+
("lower.txt", "caf\u{e9} \u{ff49}\u{ff44} shellshock sks\n"),
340+
("literal.txt", "HELLO[.+](?i)\\END\n"),
341+
("decoy.txt", "unrelated content\n"),
342+
] {
343+
fs::write(root.join(name), content).unwrap();
344+
}
345+
let cases: &[(&[&str], &str, &[&str])] = &[
346+
(&["-i"], "caf\u{e9}", &["lower.txt", "upper_accent.txt"]),
347+
(&["-i"], "CAF\u{c9}", &["lower.txt", "upper_accent.txt"]),
348+
(
349+
&["-i"],
350+
"\u{ff49}\u{ff44}",
351+
&["lower.txt", "upper_fullwidth.txt"],
352+
),
353+
(
354+
&["-i"],
355+
"\u{ff29}\u{ff24}",
356+
&["lower.txt", "upper_fullwidth.txt"],
357+
),
358+
(&["-i"], "shellshock", &["long_s_kelvin.txt", "lower.txt"]),
359+
(&["-i"], "sks", &["lower.txt", "short_fold.txt"]),
360+
(&["-S"], "caf\u{e9}", &["lower.txt", "upper_accent.txt"]),
361+
(
362+
&["-S"],
363+
"\u{ff49}\u{ff44}",
364+
&["lower.txt", "upper_fullwidth.txt"],
365+
),
366+
(&["-S"], "shellshock", &["long_s_kelvin.txt", "lower.txt"]),
367+
(&["-S"], "CAF\u{c9}", &["upper_accent.txt"]),
368+
(&[], "CAF\u{c9}", &["upper_accent.txt"]),
369+
(&[], "\u{ff29}\u{ff24}", &["upper_fullwidth.txt"]),
370+
(&["-i", "--no-unicode"], "shellshock", &["lower.txt"]),
371+
(&["-i"], r"hello[.+](?i)\end", &["literal.txt"]),
372+
(
373+
&["-i", "-e", "caf\u{e9}"],
374+
"shellshock",
375+
&["long_s_kelvin.txt", "lower.txt", "upper_accent.txt"],
376+
),
377+
(
378+
&["-i", "-e", "\u{ff49}\u{ff44}"],
379+
"caf\u{e9}",
380+
&["lower.txt", "upper_accent.txt", "upper_fullwidth.txt"],
381+
),
382+
];
383+
let mut direct = Vec::new();
384+
with_stats_backends(&root, &dir.path().join("idx"), |backend, marker| {
385+
for (i, &(flags, pattern, files)) in cases.iter().enumerate() {
386+
let mut cmd = tgrep();
387+
cmd.args(backend)
388+
.args(flags)
389+
.args(["-F", "-l", "--stats", "--sort", "path", "--color", "never"]);
390+
if flags.contains(&"-e") {
391+
cmd.args(["-e", pattern, "--", root.to_str().unwrap()]);
392+
} else {
393+
cmd.args(["--", pattern, root.to_str().unwrap()]);
394+
}
395+
let output = cmd.assert().success().get_output().clone();
396+
let stderr = String::from_utf8(output.stderr).unwrap();
397+
assert!(stderr.contains(marker), "{flags:?} {pattern}: {stderr}");
398+
let stdout = String::from_utf8(output.stdout).unwrap();
399+
let names: Vec<_> = stdout
400+
.lines()
401+
.map(|line| {
402+
std::path::Path::new(line)
403+
.file_name()
404+
.unwrap()
405+
.to_str()
406+
.unwrap()
407+
})
408+
.collect();
409+
assert_eq!(names, files, "{backend:?} {flags:?} {pattern}");
410+
if backend == ["--no-index"] {
411+
direct.push(stdout);
412+
} else {
413+
assert_eq!(stdout, direct[i], "{backend:?} {flags:?} {pattern}");
414+
}
415+
}
416+
});
417+
}
418+
329419
#[test]
330420
fn indexed_stats_distinguish_full_corpus_candidates_from_server_transport() {
331421
let dir = TempDir::new().unwrap();

‎tgrep-core/src/query.rs‎

Lines changed: 106 additions & 10 deletions
Original file line numberDiff line numberDiff line change
@@ -50,13 +50,17 @@ pub fn build_query_plan(pattern: &str, case_insensitive: bool) -> Result<QueryPl
5050
}
5151

5252
/// Build a query plan for a literal (fixed-string) pattern.
53+
///
54+
/// If regex planning fails, scan all candidates rather than reject a valid
55+
/// literal. This only disables index narrowing; the matcher still verifies it.
5356
pub fn build_literal_plan(literal: &str, case_insensitive: bool) -> QueryPlan {
54-
let text = if case_insensitive {
55-
literal.to_lowercase()
56-
} else {
57-
literal.to_string()
58-
};
59-
literals_to_query_plan(text.as_bytes())
57+
if case_insensitive {
58+
// The index only folds ASCII. Let the regex planner break literal runs
59+
// at Unicode case classes that cannot safely use those folded trigrams.
60+
return build_query_plan(&regex_syntax::escape(literal), true)
61+
.unwrap_or(QueryPlan::MatchAll);
62+
}
63+
literals_to_query_plan(literal.as_bytes())
6064
}
6165

6266
/// Build one plan covering every pattern the user supplied.
@@ -1102,14 +1106,12 @@ mod tests {
11021106

11031107
#[test]
11041108
fn test_case_insensitive_literal_plan() {
1105-
// "class AlertSchema" with case-insensitive should produce trigrams
1106-
// from "class alertschema"
1107-
let plan = build_literal_plan("class AlertSchema", true);
1109+
let plan = build_literal_plan("HeLLo", true);
11081110
match &plan {
11091111
QueryPlan::And(queries) => {
11101112
assert!(!queries.is_empty(), "should have trigrams");
11111113
// Verify these are lowercase trigrams
1112-
let expected = trigram::extract_from_literal("class alertschema");
1114+
let expected = trigram::extract_from_literal("hello");
11131115
let hashes: Vec<TrigramHash> = queries.iter().map(|q| q.hash).collect();
11141116
for tri in &expected {
11151117
assert!(hashes.contains(tri), "missing trigram {tri:#010x}");
@@ -1119,6 +1121,100 @@ mod tests {
11191121
}
11201122
}
11211123

1124+
#[test]
1125+
fn case_insensitive_literal_plan_handles_long_literals() {
1126+
let literal = "[(HeLLo.+)\u{e9}]".repeat(4096);
1127+
let content = "[(HELLO.+)\u{c9}]".repeat(4096);
1128+
let plan = build_literal_plan(&literal, true);
1129+
if plan.is_match_all() {
1130+
return;
1131+
}
1132+
1133+
let masks = trigram::extract_merged_masks(content.as_bytes());
1134+
let candidates = execute_plan_with_masks(&plan, &|tri| {
1135+
masks
1136+
.get(&tri)
1137+
.map(|mask| PostingEntry {
1138+
file_id: 0,
1139+
loc_mask: mask.loc_mask,
1140+
next_mask: mask.next_mask,
1141+
})
1142+
.into_iter()
1143+
.collect()
1144+
});
1145+
assert_eq!(candidates, vec![0], "{plan:?}");
1146+
}
1147+
1148+
#[test]
1149+
fn case_insensitive_literals_preserve_unicode_candidates() {
1150+
let cases: &[(&str, &[&str], bool)] = &[
1151+
("caf\u{e9}", &["CAF\u{c9}", "caf\u{e9}"], true),
1152+
("CAF\u{c9}", &["CAF\u{c9}", "caf\u{e9}"], true),
1153+
(
1154+
"\u{ff49}\u{ff44}",
1155+
&["\u{ff29}\u{ff24}", "\u{ff49}\u{ff44}"],
1156+
false,
1157+
),
1158+
(
1159+
"\u{ff29}\u{ff24}",
1160+
&["\u{ff29}\u{ff24}", "\u{ff49}\u{ff44}"],
1161+
false,
1162+
),
1163+
(
1164+
"shellshock",
1165+
&["SHELLSHOCK", "\u{17f}hell\u{17f}hoc\u{212a}"],
1166+
true,
1167+
),
1168+
("sks", &["SKS", "\u{17f}\u{212a}\u{17f}"], false),
1169+
(
1170+
"prefix\u{e9}suffix",
1171+
&["PREFIX\u{c9}SUFFIX", "prefix\u{e9}suffix"],
1172+
true,
1173+
),
1174+
("a\u{130}bc", &["A\u{130}BC"], true),
1175+
(r"hello[.+](?i)\end", &[r"HELLO[.+](?i)\END"], true),
1176+
("", &[""], false),
1177+
("ab", &["AB"], false),
1178+
];
1179+
for &(literal, matches, narrows) in cases {
1180+
let mut inverted = std::collections::HashMap::<u32, Vec<PostingEntry>>::new();
1181+
for (id, content) in matches.iter().chain([&"unrelated decoy"]).enumerate() {
1182+
for (tri, masks) in trigram::extract_merged_masks(content.as_bytes()) {
1183+
inverted.entry(tri).or_default().push(PostingEntry {
1184+
file_id: id as u32,
1185+
loc_mask: masks.loc_mask,
1186+
next_mask: masks.next_mask,
1187+
});
1188+
}
1189+
}
1190+
let plan = build_literal_plan(literal, true);
1191+
assert_eq!(!plan.is_match_all(), narrows, "{literal:?}: {plan:?}");
1192+
let matcher = regex::RegexBuilder::new(&regex_syntax::escape(literal))
1193+
.case_insensitive(true)
1194+
.build()
1195+
.unwrap();
1196+
for content in matches {
1197+
assert!(matcher.is_match(content), "{literal:?}: {content:?}");
1198+
}
1199+
if plan.is_match_all() {
1200+
continue;
1201+
}
1202+
let lookup = |tri| inverted.get(&tri).cloned().unwrap_or_default();
1203+
for candidates in [
1204+
execute_plan(&plan, &|tri| {
1205+
lookup(tri).iter().map(|entry| entry.file_id).collect()
1206+
}),
1207+
execute_plan_with_masks(&plan, &lookup),
1208+
] {
1209+
assert_eq!(
1210+
candidates,
1211+
(0..matches.len() as u32).collect::<Vec<_>>(),
1212+
"{literal:?}: {plan:?}"
1213+
);
1214+
}
1215+
}
1216+
}
1217+
11221218
#[test]
11231219
fn test_case_insensitive_regex_plan() {
11241220
// Unicode case folds of S include non-ASCII bytes, so only the

0 commit comments

Comments
 (0)