Repository navigation
Expand file tree
/
Copy pathstring.rs
More file actions
507 lines (447 loc) · 15.4 KB
/
Copy pathstring.rs
File metadata and controls
507 lines (447 loc) · 15.4 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
use rustpython_wtf8::Wtf8;
/// A position in the subject, paired with the byte pointer it resolves to.
///
/// `position` is a **character index**, never a byte offset. The engine does
/// arithmetic on it directly — it subtracts two positions to get a character
/// count, adds a repeat count to get a bound, and compares one against a
/// lookbehind width — so the unit is part of the [`StrDrive`] contract rather
/// than a detail each implementation may pick.
#[derive(Debug, Clone, Copy)]
pub struct StringCursor {
pub(crate) ptr: *const u8,
pub position: usize,
}
impl Default for StringCursor {
fn default() -> Self {
Self {
ptr: core::ptr::null(),
position: 0,
}
}
}
/// Random access over the subject being matched.
///
/// An implementation chooses how a character is spelled in memory — one byte
/// for `&[u8]`, one code point for `&str` and `&Wtf8` — but **not** how
/// positions are counted. Every position this trait produces or consumes is a
/// character index: `count` is the subject's length in characters, and
/// `skip(n)` advances a cursor's `position` by exactly `n`.
///
/// That is load-bearing, not incidental. The engine reads position arithmetic
/// as character arithmetic in several places — `_count` bounds a repeat with
/// `position + max_count` and reports the repeat's length as a difference of
/// positions, `ASSERT` tests `position < back` against a lookbehind width, and
/// `search_info` recovers a match start as `position - (len - 1)`. A drive
/// that stored byte offsets here would leave all of those type-correct and
/// silently wrong, and would index a lookbehind out of bounds.
///
/// So a drive over a variable-width encoding pays for the mapping: `count`
/// and `create_cursor` have to resolve character indices, and cannot simply
/// hand back byte lengths and byte offsets.
pub trait StrDrive: Copy {
/// The subject's length, in characters.
fn count(&self) -> usize;
/// A cursor at character index `n`.
fn create_cursor(&self, n: usize) -> StringCursor;
/// Move `cursor` to character index `n`, from wherever it is now.
fn adjust_cursor(&self, cursor: &mut StringCursor, n: usize);
/// Consume one character, returning it; `position` grows by one.
fn advance(cursor: &mut StringCursor) -> u32;
/// The character at `cursor`, without moving it.
fn peek(cursor: &StringCursor) -> u32;
/// Skip `n` characters, so `position` grows by exactly `n`.
fn skip(cursor: &mut StringCursor, n: usize);
/// Step back over one character, returning it; `position` shrinks by one.
fn back_advance(cursor: &mut StringCursor) -> u32;
/// The character before `cursor`, without moving it.
fn back_peek(cursor: &StringCursor) -> u32;
/// Step back `n` characters, so `position` shrinks by exactly `n`.
fn back_skip(cursor: &mut StringCursor, n: usize);
}
impl StrDrive for &[u8] {
#[inline]
fn count(&self) -> usize {
self.len()
}
#[inline]
fn create_cursor(&self, n: usize) -> StringCursor {
StringCursor {
ptr: self[n..].as_ptr(),
position: n,
}
}
#[inline]
fn adjust_cursor(&self, cursor: &mut StringCursor, n: usize) {
cursor.position = n;
cursor.ptr = self[n..].as_ptr();
}
#[inline]
fn advance(cursor: &mut StringCursor) -> u32 {
cursor.position += 1;
unsafe { cursor.ptr = cursor.ptr.add(1) };
unsafe { *cursor.ptr as u32 }
}
#[inline]
fn peek(cursor: &StringCursor) -> u32 {
unsafe { *cursor.ptr as u32 }
}
#[inline]
fn skip(cursor: &mut StringCursor, n: usize) {
cursor.position += n;
unsafe { cursor.ptr = cursor.ptr.add(n) };
}
#[inline]
fn back_advance(cursor: &mut StringCursor) -> u32 {
cursor.position -= 1;
unsafe { cursor.ptr = cursor.ptr.sub(1) };
unsafe { *cursor.ptr as u32 }
}
#[inline]
fn back_peek(cursor: &StringCursor) -> u32 {
unsafe { *cursor.ptr.sub(1) as u32 }
}
#[inline]
fn back_skip(cursor: &mut StringCursor, n: usize) {
cursor.position -= n;
unsafe { cursor.ptr = cursor.ptr.sub(n) };
}
}
impl StrDrive for &str {
#[inline]
fn count(&self) -> usize {
self.chars().count()
}
#[inline]
fn create_cursor(&self, n: usize) -> StringCursor {
let mut cursor = StringCursor {
ptr: self.as_ptr(),
position: 0,
};
Self::skip(&mut cursor, n);
cursor
}
#[inline]
fn adjust_cursor(&self, cursor: &mut StringCursor, n: usize) {
if cursor.ptr.is_null() || cursor.position > n {
*cursor = Self::create_cursor(self, n);
} else if cursor.position < n {
Self::skip(cursor, n - cursor.position);
}
}
#[inline]
fn advance(cursor: &mut StringCursor) -> u32 {
cursor.position += 1;
unsafe { next_code_point(&mut cursor.ptr) }
}
#[inline]
fn peek(cursor: &StringCursor) -> u32 {
let mut ptr = cursor.ptr;
unsafe { next_code_point(&mut ptr) }
}
#[inline]
fn skip(cursor: &mut StringCursor, n: usize) {
cursor.position += n;
for _ in 0..n {
unsafe { next_code_point(&mut cursor.ptr) };
}
}
#[inline]
fn back_advance(cursor: &mut StringCursor) -> u32 {
cursor.position -= 1;
unsafe { next_code_point_reverse(&mut cursor.ptr) }
}
#[inline]
fn back_peek(cursor: &StringCursor) -> u32 {
let mut ptr = cursor.ptr;
unsafe { next_code_point_reverse(&mut ptr) }
}
#[inline]
fn back_skip(cursor: &mut StringCursor, n: usize) {
cursor.position -= n;
for _ in 0..n {
unsafe { next_code_point_reverse(&mut cursor.ptr) };
}
}
}
impl StrDrive for &Wtf8 {
#[inline]
fn count(&self) -> usize {
self.code_points().count()
}
#[inline]
fn create_cursor(&self, n: usize) -> StringCursor {
let mut cursor = StringCursor {
ptr: self.as_bytes().as_ptr(),
position: 0,
};
Self::skip(&mut cursor, n);
cursor
}
#[inline]
fn adjust_cursor(&self, cursor: &mut StringCursor, n: usize) {
if cursor.ptr.is_null() || cursor.position > n {
*cursor = Self::create_cursor(self, n);
} else if cursor.position < n {
Self::skip(cursor, n - cursor.position);
}
}
#[inline]
fn advance(cursor: &mut StringCursor) -> u32 {
cursor.position += 1;
unsafe { next_code_point(&mut cursor.ptr) }
}
#[inline]
fn peek(cursor: &StringCursor) -> u32 {
let mut ptr = cursor.ptr;
unsafe { next_code_point(&mut ptr) }
}
#[inline]
fn skip(cursor: &mut StringCursor, n: usize) {
cursor.position += n;
for _ in 0..n {
unsafe { next_code_point(&mut cursor.ptr) };
}
}
#[inline]
fn back_advance(cursor: &mut StringCursor) -> u32 {
cursor.position -= 1;
unsafe { next_code_point_reverse(&mut cursor.ptr) }
}
#[inline]
fn back_peek(cursor: &StringCursor) -> u32 {
let mut ptr = cursor.ptr;
unsafe { next_code_point_reverse(&mut ptr) }
}
#[inline]
fn back_skip(cursor: &mut StringCursor, n: usize) {
cursor.position -= n;
for _ in 0..n {
unsafe { next_code_point_reverse(&mut cursor.ptr) };
}
}
}
/// Reads the next code point out of a byte iterator (assuming a
/// UTF-8-like encoding).
///
/// # Safety
///
/// `bytes` must produce a valid UTF-8-like (UTF-8 or WTF-8) string
#[inline]
const unsafe fn next_code_point(ptr: &mut *const u8) -> u32 {
// Decode UTF-8
let x = unsafe { **ptr };
*ptr = unsafe { ptr.add(1) };
if x < 128 {
return x as u32;
}
// Multibyte case follows
// Decode from a byte combination out of: [[[x y] z] w]
// NOTE: Performance is sensitive to the exact formulation here
let init = utf8_first_byte(x, 2);
// SAFETY: `bytes` produces an UTF-8-like string,
// so the iterator must produce a value here.
let y = unsafe { **ptr };
*ptr = unsafe { ptr.add(1) };
let mut ch = utf8_acc_cont_byte(init, y);
if x >= 0xE0 {
// [[x y z] w] case
// 5th bit in 0xE0 .. 0xEF is always clear, so `init` is still valid
// SAFETY: `bytes` produces an UTF-8-like string,
// so the iterator must produce a value here.
let z = unsafe { **ptr };
*ptr = unsafe { ptr.add(1) };
let y_z = utf8_acc_cont_byte((y & CONT_MASK) as u32, z);
ch = (init << 12) | y_z;
if x >= 0xF0 {
// [x y z w] case
// use only the lower 3 bits of `init`
// SAFETY: `bytes` produces an UTF-8-like string,
// so the iterator must produce a value here.
let w = unsafe { **ptr };
*ptr = unsafe { ptr.add(1) };
ch = ((init & 7) << 18) | utf8_acc_cont_byte(y_z, w);
}
}
ch
}
/// Reads the last code point out of a byte iterator (assuming a
/// UTF-8-like encoding).
///
/// # Safety
///
/// `bytes` must produce a valid UTF-8-like (UTF-8 or WTF-8) string
#[inline]
const unsafe fn next_code_point_reverse(ptr: &mut *const u8) -> u32 {
// Decode UTF-8
*ptr = unsafe { ptr.sub(1) };
let w = match unsafe { **ptr } {
next_byte if next_byte < 128 => return next_byte as u32,
back_byte => back_byte,
};
// Multibyte case follows
// Decode from a byte combination out of: [x [y [z w]]]
let mut ch;
// SAFETY: `bytes` produces an UTF-8-like string,
// so the iterator must produce a value here.
*ptr = unsafe { ptr.sub(1) };
let z = unsafe { **ptr };
ch = utf8_first_byte(z, 2);
if utf8_is_cont_byte(z) {
// SAFETY: `bytes` produces an UTF-8-like string,
// so the iterator must produce a value here.
*ptr = unsafe { ptr.sub(1) };
let y = unsafe { **ptr };
ch = utf8_first_byte(y, 3);
if utf8_is_cont_byte(y) {
// SAFETY: `bytes` produces an UTF-8-like string,
// so the iterator must produce a value here.
*ptr = unsafe { ptr.sub(1) };
let x = unsafe { **ptr };
ch = utf8_first_byte(x, 4);
ch = utf8_acc_cont_byte(ch, y);
}
ch = utf8_acc_cont_byte(ch, z);
}
ch = utf8_acc_cont_byte(ch, w);
ch
}
/// Returns the initial codepoint accumulator for the first byte.
/// The first byte is special, only want bottom 5 bits for width 2, 4 bits
/// for width 3, and 3 bits for width 4.
#[inline]
const fn utf8_first_byte(byte: u8, width: u32) -> u32 {
(byte & (0x7F >> width)) as u32
}
/// Returns the value of `ch` updated with continuation byte `byte`.
#[inline]
const fn utf8_acc_cont_byte(ch: u32, byte: u8) -> u32 {
(ch << 6) | (byte & CONT_MASK) as u32
}
/// Checks whether the byte is a UTF-8 continuation byte (i.e., starts with the
/// bits `10`).
#[inline]
const fn utf8_is_cont_byte(byte: u8) -> bool {
(byte as i8) < -64
}
/// Mask of the value bits of a continuation byte.
const CONT_MASK: u8 = 0b0011_1111;
// Character-class and case predicates for the SRE engine.
//
// Every predicate takes a raw `u32` code point (SRE decodes strings into `u32`s,
// including lone surrogates) and returns whether it belongs to the class.
// ASCII-mode predicates only ever consider byte values; Unicode-mode predicates
// consult the shared property tables in `rustpython_unicode::classify`.
const UNDERSCORE: u32 = '_' as u32;
#[inline]
pub(crate) fn is_word(ch: u32) -> bool {
ch == UNDERSCORE || u8::try_from(ch).is_ok_and(|x| x.is_ascii_alphanumeric())
}
#[inline]
pub(crate) fn is_space(ch: u32) -> bool {
u8::try_from(ch).is_ok_and(rustpython_wtf8::is_py_ascii_whitespace)
}
#[inline]
pub(crate) fn is_digit(ch: u32) -> bool {
u8::try_from(ch).is_ok_and(|x| x.is_ascii_digit())
}
/// Byte classification and case conversion in the current locale.
///
/// Callbacks keep host APIs outside this `no_std` engine. They are called while
/// matching, rather than cached in a compiled pattern, so a locale change also
/// affects existing patterns and scanners. Without host callbacks, matching uses
/// the ASCII rules of the C locale.
#[derive(Debug, Clone, Copy)]
pub struct Locale {
pub is_alnum: fn(u8) -> bool,
pub to_lower: fn(u8) -> u32,
pub to_upper: fn(u8) -> u32,
}
impl Default for Locale {
fn default() -> Self {
Self {
is_alnum: |ch| ch.is_ascii_alphanumeric(),
to_lower: |ch| ch.to_ascii_lowercase() as u32,
to_upper: |ch| ch.to_ascii_uppercase() as u32,
}
}
}
impl Locale {
#[inline]
pub(crate) fn is_word(self, ch: u32) -> bool {
ch == UNDERSCORE || u8::try_from(ch).is_ok_and(self.is_alnum)
}
#[inline]
pub(crate) fn lower(self, ch: u32) -> u32 {
u8::try_from(ch).map_or(ch, self.to_lower)
}
#[inline]
pub(crate) fn upper(self, ch: u32) -> u32 {
u8::try_from(ch).map_or(ch, self.to_upper)
}
}
#[inline]
pub(crate) const fn is_linebreak(ch: u32) -> bool {
ch == '\n' as u32
}
#[inline]
#[must_use]
pub fn lower_ascii(ch: u32) -> u32 {
u8::try_from(ch).map_or(ch, |x| x.to_ascii_lowercase() as u32)
}
#[inline]
pub(crate) fn is_uni_digit(ch: u32) -> bool {
// SRE_UNI_IS_DIGIT matches Unicode decimal digits (Py_UNICODE_ISDECIMAL),
// not just ASCII 0-9. Fast-path true ASCII (< 0x80) to skip the
// general-category table lookup for the overwhelmingly common case;
// u8 covers the whole Latin-1 range, so gate on 0x80 rather than
// `u8::try_from` succeeding.
if ch < 0x80 {
return (ch as u8).is_ascii_digit();
}
char::try_from(ch).is_ok_and(rustpython_unicode::classify::is_decimal)
}
#[inline]
pub(crate) fn is_uni_space(ch: u32) -> bool {
// SRE_UNI_IS_SPACE is Py_UNICODE_ISSPACE. Fast-path ASCII: besides the
// usual whitespace bytes, Py_UNICODE_ISSPACE also covers the 0x1C..=0x1F
// separators (bidirectional class B/S/WS).
if ch < 0x80 {
return matches!(ch, 0x09..=0x0D | 0x1C..=0x20);
}
char::try_from(ch).is_ok_and(rustpython_unicode::classify::is_space)
}
#[inline]
pub(crate) const fn is_uni_linebreak(ch: u32) -> bool {
matches!(
ch,
0x000A | 0x000B | 0x000C | 0x000D | 0x001C | 0x001D | 0x001E | 0x0085 | 0x2028 | 0x2029
)
}
#[inline]
pub(crate) fn is_uni_alnum(ch: u32) -> bool {
// TODO: check with cpython
// Fast-path true ASCII (< 0x80) to skip the general-category table
// lookup, which dominates \w matching over otherwise-ASCII text (the
// common case). Latin-1 supplement characters (0x80..=0xFF) still need
// the full table (e.g. 'Ä' is alphanumeric but not ASCII).
if ch < 0x80 {
return (ch as u8).is_ascii_alphanumeric();
}
char::try_from(ch).is_ok_and(rustpython_unicode::classify::is_alnum)
}
#[inline]
pub(crate) fn is_uni_word(ch: u32) -> bool {
ch == UNDERSCORE || is_uni_alnum(ch)
}
#[inline]
#[must_use]
pub fn lower_unicode(ch: u32) -> u32 {
// SRE_UNI_LOWER is Py_UNICODE_TOLOWER, the simple one-to-one mapping.
char::try_from(ch).map_or(ch, |x| rustpython_unicode::case::simple_lowercase(x) as u32)
}
#[inline]
#[must_use]
pub fn upper_unicode(ch: u32) -> u32 {
// SRE_UNI_UPPER is Py_UNICODE_TOUPPER, the simple one-to-one mapping.
char::try_from(ch).map_or(ch, |x| rustpython_unicode::case::simple_uppercase(x) as u32)
}