1use std::collections::HashSet;
7
8const MAX_FORMAT_CHARS: usize = 8192;
9const MAX_FORMAT_DEPTH: usize = 32;
10
11#[derive(Debug, Clone, PartialEq, Eq)]
12pub struct BraceField {
13 pub selector: BraceSelector,
14 pub source_char: usize,
15}
16
17#[derive(Debug, Clone, PartialEq, Eq, Hash)]
18pub enum BraceSelector {
19 Automatic(usize),
20 Positional(usize),
21 Named(String),
22}
23
24#[derive(Debug, Clone, PartialEq, Eq)]
25pub struct BraceFormat {
26 pub fields: Vec<BraceField>,
27 pub named_fields: HashSet<String>,
28 pub max_positional_count: usize,
29 pub has_automatic_fields: bool,
30 pub has_explicit_fields: bool,
31 pub complete: bool,
32}
33
34#[derive(Debug, Clone, PartialEq, Eq)]
35pub struct PercentItem {
36 pub conversion: char,
37 pub mapping_key: Option<String>,
38 pub width_stars: usize,
39 pub precision_stars: usize,
40 pub source_char: usize,
41}
42
43#[derive(Debug, Clone, PartialEq, Eq)]
44pub struct PercentFormat {
45 pub items: Vec<PercentItem>,
46 pub named_fields: HashSet<String>,
47 pub positional_slots: usize,
48 pub has_named_items: bool,
49 pub has_positional_items: bool,
50 pub unsupported_conversions: Vec<(char, usize)>,
51 pub complete: bool,
52}
53
54pub fn parse_brace_format(value: &str) -> BraceFormat {
55 let chars = value.chars().collect::<Vec<_>>();
56 if chars.len() > MAX_FORMAT_CHARS {
57 return BraceFormat::incomplete();
58 }
59 let mut parser = BraceParser {
60 chars: &chars,
61 fields: Vec::new(),
62 named_fields: HashSet::new(),
63 next_automatic: 0,
64 max_positional_count: 0,
65 has_automatic_fields: false,
66 has_explicit_fields: false,
67 complete: true,
68 };
69 parser.scan(0, chars.len(), 0);
70 BraceFormat {
71 fields: parser.fields,
72 named_fields: parser.named_fields,
73 max_positional_count: parser.max_positional_count,
74 has_automatic_fields: parser.has_automatic_fields,
75 has_explicit_fields: parser.has_explicit_fields,
76 complete: parser.complete,
77 }
78}
79
80impl BraceFormat {
81 fn incomplete() -> Self {
82 Self {
83 fields: Vec::new(),
84 named_fields: HashSet::new(),
85 max_positional_count: 0,
86 has_automatic_fields: false,
87 has_explicit_fields: false,
88 complete: false,
89 }
90 }
91
92 pub fn mixes_numbering(&self) -> bool {
93 self.has_automatic_fields && self.has_explicit_fields
94 }
95}
96
97struct BraceParser<'a> {
98 chars: &'a [char],
99 fields: Vec<BraceField>,
100 named_fields: HashSet<String>,
101 next_automatic: usize,
102 max_positional_count: usize,
103 has_automatic_fields: bool,
104 has_explicit_fields: bool,
105 complete: bool,
106}
107
108impl BraceParser<'_> {
109 fn scan(&mut self, start: usize, end: usize, depth: usize) {
110 if depth > MAX_FORMAT_DEPTH {
111 self.complete = false;
112 return;
113 }
114 let mut cursor = start;
115 while cursor < end {
116 match self.chars[cursor] {
117 '{' if self.chars.get(cursor + 1) == Some(&'{') => cursor += 2,
118 '}' if self.chars.get(cursor + 1) == Some(&'}') => cursor += 2,
119 '{' => {
120 let Some(close) = self.field_close(cursor, end) else {
121 self.complete = false;
122 return;
123 };
124 let (header_end, spec_start) = self.field_header(cursor + 1, close);
125 self.field_selector(cursor + 1, header_end, cursor);
126 if let Some(spec_start) = spec_start {
127 self.scan(spec_start, close, depth + 1);
128 }
129 cursor = close + 1;
130 }
131 '}' => {
132 self.complete = false;
133 return;
134 }
135 _ => cursor += 1,
136 }
137 }
138 }
139
140 fn field_close(&self, open: usize, end: usize) -> Option<usize> {
141 let mut depth = 1usize;
142 let mut cursor = open + 1;
143 while cursor < end {
144 match self.chars[cursor] {
145 '{' if self.chars.get(cursor + 1) == Some(&'{') => cursor += 2,
146 '{' => {
147 depth = depth.checked_add(1)?;
148 cursor += 1;
149 }
150 '}' if depth == 1 => return Some(cursor),
151 '}' => {
152 depth -= 1;
153 cursor += 1;
154 }
155 _ => cursor += 1,
156 }
157 }
158 None
159 }
160
161 fn field_header(&mut self, start: usize, close: usize) -> (usize, Option<usize>) {
162 let mut cursor = start;
163 let mut bracket_depth = 0usize;
164 while cursor < close {
165 match self.chars[cursor] {
166 '[' => bracket_depth += 1,
167 ']' => {
168 if bracket_depth == 0 {
169 self.complete = false;
170 } else {
171 bracket_depth -= 1;
172 }
173 }
174 '!' if bracket_depth == 0 => {
175 let conversion = self.chars.get(cursor + 1).copied();
176 if !matches!(conversion, Some('s' | 'r' | 'a'))
177 || !matches!(self.chars.get(cursor + 2), Some(':' | '}'))
178 {
179 self.complete = false;
180 return (close, None);
181 }
182 if self.chars.get(cursor + 2) == Some(&':') {
183 return (cursor, Some(cursor + 3));
184 }
185 return (cursor, None);
186 }
187 ':' if bracket_depth == 0 => return (cursor, Some(cursor + 1)),
188 _ => {}
189 }
190 cursor += 1;
191 }
192 if bracket_depth != 0 {
193 self.complete = false;
194 }
195 (close, None)
196 }
197
198 fn field_selector(&mut self, start: usize, header_end: usize, source_char: usize) {
199 let mut cursor = start;
200 while cursor < header_end && !matches!(self.chars[cursor], '.' | '[') {
201 cursor += 1;
202 }
203 let root = self.chars[start..cursor].iter().collect::<String>();
204 if root.is_empty() {
205 let index = self.next_automatic;
206 let Some(next) = index.checked_add(1) else {
207 self.complete = false;
208 return;
209 };
210 self.next_automatic = next;
211 self.max_positional_count = self.max_positional_count.max(next);
212 self.has_automatic_fields = true;
213 self.fields.push(BraceField {
214 selector: BraceSelector::Automatic(index),
215 source_char,
216 });
217 } else if root.bytes().all(|byte| byte.is_ascii_digit()) {
218 let Ok(index) = root.parse::<usize>() else {
219 self.complete = false;
220 return;
221 };
222 let Some(count) = index.checked_add(1) else {
223 self.complete = false;
224 return;
225 };
226 self.max_positional_count = self.max_positional_count.max(count);
227 self.has_explicit_fields = true;
228 self.fields.push(BraceField {
229 selector: BraceSelector::Positional(index),
230 source_char,
231 });
232 } else {
233 self.named_fields.insert(root.clone());
234 self.fields.push(BraceField {
235 selector: BraceSelector::Named(root),
236 source_char,
237 });
238 }
239 }
240}
241
242pub fn parse_percent_format(value: &str) -> PercentFormat {
243 let chars = value.chars().collect::<Vec<_>>();
244 if chars.len() > MAX_FORMAT_CHARS {
245 return PercentFormat::incomplete();
246 }
247 let mut result = PercentFormat {
248 items: Vec::new(),
249 named_fields: HashSet::new(),
250 positional_slots: 0,
251 has_named_items: false,
252 has_positional_items: false,
253 unsupported_conversions: Vec::new(),
254 complete: true,
255 };
256 let mut cursor = 0usize;
257 while cursor < chars.len() {
258 if chars[cursor] != '%' {
259 cursor += 1;
260 continue;
261 }
262 let source_char = cursor;
263 cursor += 1;
264 if cursor == chars.len() {
265 result.complete = false;
266 break;
267 }
268 if chars[cursor] == '%' {
269 cursor += 1;
270 continue;
271 }
272
273 let mapping_key = if chars[cursor] == '(' {
274 cursor += 1;
275 let start = cursor;
276 while cursor < chars.len() && chars[cursor] != ')' {
277 cursor += 1;
278 }
279 if cursor == chars.len() {
280 result.complete = false;
281 break;
282 }
283 let key = chars[start..cursor].iter().collect::<String>();
284 cursor += 1;
285 result.named_fields.insert(key.clone());
286 result.has_named_items = true;
287 Some(key)
288 } else {
289 result.has_positional_items = true;
290 None
291 };
292
293 while cursor < chars.len() && matches!(chars[cursor], '#' | '0' | '-' | ' ' | '+') {
294 cursor += 1;
295 }
296
297 let mut width_stars = 0usize;
298 if cursor < chars.len() && chars[cursor] == '*' {
299 width_stars = 1;
300 cursor += 1;
301 } else {
302 while cursor < chars.len() && chars[cursor].is_ascii_digit() {
303 cursor += 1;
304 }
305 }
306
307 let mut precision_stars = 0usize;
308 if cursor < chars.len() && chars[cursor] == '.' {
309 cursor += 1;
310 if cursor < chars.len() && chars[cursor] == '*' {
311 precision_stars = 1;
312 cursor += 1;
313 } else {
314 while cursor < chars.len() && chars[cursor].is_ascii_digit() {
315 cursor += 1;
316 }
317 }
318 }
319
320 if cursor < chars.len() && matches!(chars[cursor], 'h' | 'l' | 'L') {
321 cursor += 1;
322 }
323 let Some(&conversion) = chars.get(cursor) else {
324 result.complete = false;
325 break;
326 };
327 cursor += 1;
328 if !matches!(
329 conversion,
330 'b' | 'd'
331 | 'i'
332 | 'o'
333 | 'u'
334 | 'x'
335 | 'X'
336 | 'e'
337 | 'E'
338 | 'f'
339 | 'F'
340 | 'g'
341 | 'G'
342 | 'c'
343 | 'r'
344 | 's'
345 | 'a'
346 ) {
347 result
348 .unsupported_conversions
349 .push((conversion, cursor - 1));
350 }
351 if mapping_key.is_some() && (width_stars != 0 || precision_stars != 0) {
352 result.complete = false;
353 }
354 result.positional_slots = result
355 .positional_slots
356 .saturating_add(width_stars)
357 .saturating_add(precision_stars)
358 .saturating_add(usize::from(mapping_key.is_none()));
359 result.items.push(PercentItem {
360 conversion,
361 mapping_key,
362 width_stars,
363 precision_stars,
364 source_char,
365 });
366 }
367 result
368}
369
370impl PercentFormat {
371 fn incomplete() -> Self {
372 Self {
373 items: Vec::new(),
374 named_fields: HashSet::new(),
375 positional_slots: 0,
376 has_named_items: false,
377 has_positional_items: false,
378 unsupported_conversions: Vec::new(),
379 complete: false,
380 }
381 }
382}
383
384#[cfg(test)]
385mod tests {
386 use super::*;
387
388 #[test]
390 #[brokk_bifrost_test_macros::hardwon(
391 "6b123df7cc68: quicksilver round 6 on brokk-bifrost-python: empty percent mapping keys are valid"
392 )]
393 fn qs6_empty_percent_mapping_key() {
394 let parsed = parse_percent_format("%()s");
395 assert!(parsed.complete, "{parsed:?}");
396 assert_eq!(parsed.named_fields, HashSet::from([String::new()]));
397 assert_eq!(parsed.items[0].mapping_key.as_deref(), Some(""));
398 assert_eq!(parsed.positional_slots, 0);
399 }
400
401 #[test]
403 fn qs6_format_conversion_corpus() {
404 for conversion in ['s', 'r', 'a'] {
405 let parsed = parse_brace_format(&format!("{{name!{conversion}}}"));
406 assert!(parsed.complete, "{parsed:?}");
407 assert_eq!(parsed.named_fields, HashSet::from(["name".into()]));
408 }
409 assert!(!parse_brace_format("{name!q}").complete);
410 assert!(!parse_percent_format("%(unclosed").complete);
411 }
412
413 #[test]
414 fn brace_fields_decode_numbering_names_and_escapes() {
415 let parsed = parse_brace_format("{{literal}} {} {2[name]} {user.name!r:>{width}}");
416
417 assert!(parsed.complete);
418 assert_eq!(parsed.max_positional_count, 3);
419 assert!(parsed.mixes_numbering());
420 assert_eq!(
421 parsed.named_fields,
422 HashSet::from(["user".to_owned(), "width".to_owned()])
423 );
424 assert_eq!(parsed.fields.len(), 4);
425 assert_eq!(parsed.fields[0].selector, BraceSelector::Automatic(0));
426 assert_eq!(parsed.fields[1].selector, BraceSelector::Positional(2));
427 assert_eq!(
428 parsed.fields[2].selector,
429 BraceSelector::Named("user".to_owned())
430 );
431 assert_eq!(
432 parsed.fields[3].selector,
433 BraceSelector::Named("width".to_owned())
434 );
435 }
436
437 #[test]
438 fn brace_argument_count_does_not_count_duplicate_explicit_fields() {
439 let parsed = parse_brace_format("{0} {0}");
440
441 assert!(parsed.complete);
442 assert_eq!(parsed.max_positional_count, 1);
443 assert!(!parsed.mixes_numbering());
444 }
445
446 #[test]
447 fn malformed_brace_values_are_incomplete() {
448 for value in ["{", "}", "{name!q}", "{name[broken}"] {
449 assert!(
450 !parse_brace_format(value).complete,
451 "{value:?} must be incomplete"
452 );
453 }
454 }
455
456 #[test]
457 fn percent_parser_counts_conversion_and_star_slots() {
458 let parsed = parse_percent_format("%% %(name)08.2f %*.*s %Z");
459
460 assert!(parsed.complete);
461 assert!(parsed.has_named_items);
462 assert!(parsed.has_positional_items);
463 assert_eq!(parsed.named_fields, HashSet::from(["name".to_owned()]));
464 assert_eq!(parsed.positional_slots, 4);
465 assert_eq!(parsed.unsupported_conversions, vec![('Z', 23)]);
466 assert_eq!(parsed.items.len(), 3);
467 assert_eq!(parsed.items[1].width_stars, 1);
468 assert_eq!(parsed.items[1].precision_stars, 1);
469 }
470
471 #[test]
472 fn percent_parser_skips_escaped_percent_and_marks_dangling_percent_incomplete() {
473 let parsed = parse_percent_format("100%% complete");
474 assert!(parsed.complete);
475 assert!(parsed.items.is_empty());
476 assert_eq!(parsed.positional_slots, 0);
477
478 assert!(!parse_percent_format("value %").complete);
479 }
480
481 #[test]
482 fn percent_parser_keeps_conversion_source_positions() {
483 let parsed = parse_percent_format("%s %Z");
484 assert_eq!(parsed.items[0].source_char, 0);
485 assert_eq!(parsed.items[1].source_char, 3);
486 assert_eq!(parsed.unsupported_conversions, vec![('Z', 4)]);
487 }
488}
489
490#[cfg(test)]
491mod budget_tests {
492 use super::*;
493
494 #[test]
495 fn qs6_format_caps_count_characters_not_utf8_bytes() {
496 for length in [8191, 8192, 8193] {
497 let brace_suffix = "{{}}{name}";
498 let percent_suffix = "%%%(name)s";
499 let padding = length - 10;
500 let brace = parse_brace_format(&format!("{}{brace_suffix}", "\u{e9}".repeat(padding)));
501 let percent =
502 parse_percent_format(&format!("{}{percent_suffix}", "\u{e9}".repeat(padding)));
503 assert_eq!(brace.complete, length <= 8192);
504 assert_eq!(percent.complete, length <= 8192);
505 if length <= 8192 {
506 assert_eq!(
507 brace.fields,
508 vec![BraceField {
509 selector: BraceSelector::Named("name".into()),
510 source_char: padding + 4
511 }]
512 );
513 assert_eq!(percent.items.len(), 1);
514 assert_eq!(percent.items[0].source_char, padding + 2);
515 assert_eq!(percent.items[0].mapping_key.as_deref(), Some("name"));
516 assert_eq!(percent.items[0].conversion, 's');
517 } else {
518 assert!(brace.fields.is_empty());
519 assert!(percent.items.is_empty());
520 assert!(brace.named_fields.is_empty());
521 assert!(percent.named_fields.is_empty());
522 }
523 }
524 }
525}