Skip to content

Commit bb8741c

Browse files
joshuamegnauth54joshuamegnauth54
committed
unicodedata: Fix Bidirectional, improve parser
We can save space by calculating the diffs between modern Unicode and 3.2.0 and storing membership information where valid. This avoids storing entire tables for 3.2.0, and is also more correct in the long run since it handles absence from 3.2.0 correctly. I switched over Bidi to this new method which partially fixed the test. Unfortunately, our Unicode data is more up to date than Python 3.14 so the test fails for modern Unicode. It should pass with 3.15's tests.
1 parent dd2cc4d commit bb8741c

3 files changed

Lines changed: 14000 additions & 59 deletions

File tree

‎crates/unicode/build.rs‎

Lines changed: 85 additions & 31 deletions
Original file line numberDiff line numberDiff line change
@@ -14,7 +14,9 @@ use std::{
1414
thread,
1515
};
1616

17-
use icu_properties::props::{EnumeratedProperty, GeneralCategory, NumericType};
17+
use icu_properties::props::{
18+
BidiClass, EnumeratedProperty, GeneralCategory, NamedEnumeratedProperty, NumericType,
19+
};
1820

1921
fn generate_unicode_3_2() {
2022
let path = PathBuf::from(env::var("OUT_DIR").unwrap())
@@ -80,17 +82,23 @@ fn generate_unicode_3_2() {
8082
write_derived(
8183
&base,
8284
"DerivedBidiClass-3.2.0.txt",
83-
"BIDI_CLASS",
85+
"BIDI_CLASS_DIFF",
8486
"(u32, u32, BidiClass)",
8587
NonZeroUsize::new(1).unwrap(),
8688
&mut writer,
8789
|start, end, id, _| {
8890
let id = parse_bidi(id);
89-
if id != "BidiClass::LeftToRight" {
90-
Some((start, end, id))
91-
} else {
92-
None
91+
for i in start..=end {
92+
let legacy = BidiClass::try_from_str(id.rsplit_once("::").unwrap().1)
93+
.expect("Unicode data contains valid variants");
94+
let modern = char::from_u32(i).map(BidiClass::for_char);
95+
96+
if Some(legacy) != modern {
97+
return Some((start, end, id));
98+
}
9399
}
100+
101+
None
94102
},
95103
|writer, mut values| {
96104
values.sort_unstable_by_key(|(start, _, _)| *start);
@@ -197,21 +205,86 @@ fn generate_numeric_type() {
197205
);
198206
}
199207

208+
/// Generate a compressed array of Unicode 3.2 membership.
209+
///
210+
/// Membership + diff checks is more efficient than storing the full table for 3.2. The logic is to
211+
/// default to the latest Unicode if a character exists in 3.2 but isn't different. Membership
212+
/// is needed because diffs aren't enough - a character may be absent in 3.2 which is different
213+
/// than returning a default.
214+
fn generate_membership_3_2() {
215+
let path = Path::new(env!("CARGO_MANIFEST_DIR"))
216+
.join("unicode")
217+
.join("ucd32")
218+
.join("UnicodeData-3.2.0.txt");
219+
let reader = BufReader::new(File::open(path).unwrap());
220+
221+
// Parse membership from the first data. Unfortunately, this is largely uncompressed.
222+
let mut membership_set = BTreeSet::new();
223+
// TODO: Oh my, is this hacky and ugly...
224+
let mut range_membership = Vec::new();
225+
parse_unicode_3_2(
226+
reader,
227+
NonZeroUsize::new(1).unwrap(),
228+
&mut io::empty(),
229+
|start, end, value, _| {
230+
if value.ends_with("First>") | value.ends_with("Last>") {
231+
// Some lines (literally 20) are compressed ranges, so we have to handle those separately
232+
range_membership.push(start);
233+
} else {
234+
membership_set.insert((start, end));
235+
}
236+
237+
Option::<()>::None
238+
},
239+
|_writer, _values| {},
240+
);
241+
242+
// Second pass. Compress the ranges.
243+
let mut iter = membership_set.iter();
244+
let &(mut start_prev, mut end_prev) = iter.next().unwrap();
245+
let mut membership = Vec::new();
246+
247+
for &(start, end) in iter {
248+
if start <= end_prev + 1 {
249+
end_prev = end_prev.max(end);
250+
} else {
251+
membership.push((start_prev, end_prev));
252+
start_prev = start;
253+
end_prev = end;
254+
}
255+
}
256+
membership.push((start_prev, end_prev));
257+
258+
let (chunks, &[]) = range_membership.as_chunks::<2>() else {
259+
panic!("Range membership is always in pairs")
260+
};
261+
for &chunk in chunks {
262+
membership.push(chunk.into());
263+
}
264+
265+
membership.sort_unstable_by_key(|&(start, _)| start);
266+
267+
let path = PathBuf::from(env::var("OUT_DIR").unwrap())
268+
.join("generated")
269+
.join("membership_3_2.rs");
270+
fs::create_dir_all(path.parent().unwrap()).unwrap();
271+
let mut writer = BufWriter::new(File::create(&path).unwrap());
272+
273+
writeln!(writer, "static MEMBERSHIP_3_2: &[(u32, u32)] = &").unwrap();
274+
write!(writer, "{membership:?};").unwrap();
275+
}
276+
200277
fn generate_numeric_value() {
201278
let path = PathBuf::from(env::var("OUT_DIR").unwrap())
202279
.join("generated")
203280
.join("unicode_numeric_value.rs");
204281
fs::create_dir_all(path.parent().unwrap()).unwrap();
205282
let mut writer = BufWriter::new(File::create(&path).unwrap());
206283

207-
// Ideally, this would store the diffs between the two tables. However, we need 3.2.0
208-
// membership as well as different chars. The final tables are both smaller than storing the
209-
// full 3.2.0 value table.
210284
let ucd32 = Path::new(env!("CARGO_MANIFEST_DIR"))
211285
.join("unicode")
212286
.join("ucd32");
213287
let mut ucd32_diffs = BTreeMap::new();
214-
let mut ucd32_member = BTreeSet::new();
215288
let numeric_32 =
216289
BufReader::new(File::open(ucd32.join("DerivedNumericValues-3.2.0.txt")).unwrap());
217290
parse_unicode_3_2(
@@ -223,7 +296,6 @@ fn generate_numeric_value() {
223296
.parse()
224297
.expect("Unicode data contains valid properties");
225298
ucd32_diffs.insert((start, end), value);
226-
ucd32_member.insert((start, end));
227299
Option::<()>::None
228300
},
229301
|_writer, _values| {},
@@ -270,26 +342,6 @@ fn generate_numeric_value() {
270342
write!(writer, "({start}, {end}, {value:?}),").unwrap();
271343
}
272344
writeln!(writer, "];").unwrap();
273-
274-
// Compress membership table
275-
let mut iter = ucd32_member.iter();
276-
let &(mut start_prev, mut end_prev) = iter.next().unwrap();
277-
let mut membership = Vec::new();
278-
279-
for &(start, end) in iter {
280-
if start <= end_prev + 1 {
281-
end_prev = end_prev.max(end);
282-
} else {
283-
membership.push((start_prev, end_prev));
284-
start_prev = start;
285-
end_prev = end;
286-
}
287-
}
288-
membership.push((start_prev, end_prev));
289-
membership.sort_unstable_by_key(|&(start, _)| start);
290-
291-
writeln!(writer, "static NUMERIC_VAL_EXISTS_32: &[(u32, u32)] = &").unwrap();
292-
write!(writer, "{membership:?};").unwrap();
293345
}
294346

295347
fn generate_unicode_latest() {
@@ -602,10 +654,12 @@ fn main() {
602654
println!("cargo:rerun-if-changed=unicode/latest");
603655

604656
let t_32 = thread::spawn(generate_unicode_3_2);
657+
let t_32_membership = thread::spawn(generate_membership_3_2);
605658
let t_numeric_type = thread::spawn(generate_numeric_type);
606659
let t_numeric_value = thread::spawn(generate_numeric_value);
607660
let t_latest = thread::spawn(generate_unicode_latest);
608661
t_32.join().unwrap();
662+
t_32_membership.join().unwrap();
609663
t_numeric_type.join().unwrap();
610664
t_numeric_value.join().unwrap();
611665
t_latest.join().unwrap();

‎crates/unicode/src/data.rs‎

Lines changed: 41 additions & 28 deletions
Original file line numberDiff line numberDiff line change
@@ -19,6 +19,7 @@ use icu_properties::props::{
1919
};
2020
use rustpython_wtf8::CodePoint;
2121

22+
include!(concat!(env!("OUT_DIR"), "/generated/membership_3_2.rs"));
2223
include!(concat!(env!("OUT_DIR"), "/generated/unicode_3_2.rs"));
2324
include!(concat!(env!("OUT_DIR"), "/generated/unicode_latest.rs"));
2425
include!(concat!(env!("OUT_DIR"), "/generated/unicode_num_type.rs"));
@@ -70,7 +71,7 @@ impl DecompositionType {
7071
}
7172
}
7273

73-
fn lookup_property<T: Copy>(table: &[(u32, u32, T)], ch: char) -> Option<T> {
74+
fn lookup_table<T: Copy>(table: &[(u32, u32, T)], ch: char) -> Option<T> {
7475
let ch = ch as u32;
7576
table
7677
.binary_search_by(|&(start, end, _)| {
@@ -86,25 +87,34 @@ fn lookup_property<T: Copy>(table: &[(u32, u32, T)], ch: char) -> Option<T> {
8687
.map(|i| table[i].2)
8788
}
8889

89-
fn lookup_numeric_val(ch: char, modern: bool) -> Option<f64> {
90+
fn membership_3_2(ch: u32) -> bool {
91+
MEMBERSHIP_3_2
92+
.binary_search_by(|&(start, end)| {
93+
if ch > end {
94+
Ordering::Less
95+
} else if ch < start {
96+
Ordering::Greater
97+
} else {
98+
Ordering::Equal
99+
}
100+
})
101+
.is_ok()
102+
}
103+
104+
fn lookup_property_diff<T: Copy>(
105+
table: &[(u32, u32, T)],
106+
diff: &[(u32, u32, T)],
107+
ch: char,
108+
modern: bool,
109+
) -> Option<T> {
90110
if modern {
91-
lookup_property(NUMERIC_VALUES, ch)
111+
lookup_table(table, ch)
92112
} else {
93113
cold_path();
94-
lookup_property(NUMERIC_VALUES_DIFF, ch).or_else(|| {
95-
NUMERIC_VAL_EXISTS_32
96-
.binary_search_by(|&(start, end)| {
97-
let ch = ch as u32;
98-
if ch > end {
99-
Ordering::Less
100-
} else if ch < start {
101-
Ordering::Greater
102-
} else {
103-
Ordering::Equal
104-
}
105-
})
106-
.ok()
107-
.and_then(|_| lookup_property(NUMERIC_VALUES, ch))
114+
lookup_table(diff, ch).or_else(|| {
115+
membership_3_2(ch as u32)
116+
.then(|| lookup_table(table, ch))
117+
.flatten()
108118
})
109119
}
110120
}
@@ -154,7 +164,7 @@ impl Ucd {
154164
Some(GeneralCategory::for_char(c))
155165
} else {
156166
cold_path();
157-
lookup_property(GENERAL_CATEGORY, c)
167+
lookup_table(GENERAL_CATEGORY, c)
158168
}
159169
.unwrap_or(GeneralCategory::Unassigned)
160170
.short_name()
@@ -168,11 +178,13 @@ impl Ucd {
168178
Some(BidiClass::for_char(c))
169179
} else {
170180
cold_path();
171-
lookup_property(BIDI_CLASS, c)
181+
lookup_table(BIDI_CLASS_DIFF, c)
182+
.or_else(|| membership_3_2(c as u32).then(|| BidiClass::for_char(c)))
172183
}
173184
})
174-
.unwrap_or(BidiClass::LeftToRight)
175-
.short_name()
185+
.as_ref()
186+
.map(BidiClass::short_name)
187+
.unwrap_or_default()
176188
}
177189

178190
#[must_use]
@@ -192,7 +204,7 @@ impl Ucd {
192204
//
193205
// Currently, this implementation is incomplete because I can't figure
194206
// out what CPython is doing.
195-
lookup_property(EAST_ASIAN_WIDTH, c)
207+
lookup_table(EAST_ASIAN_WIDTH, c)
196208
}
197209
})
198210
.unwrap_or(EastAsianWidth::Neutral)
@@ -230,7 +242,7 @@ impl Ucd {
230242
Some(CanonicalCombiningClass::for_char(c))
231243
} else {
232244
cold_path();
233-
lookup_property(COMBINING_CLASS, c)
245+
lookup_table(COMBINING_CLASS, c)
234246
}
235247
})
236248
.unwrap_or(CanonicalCombiningClass::NotReordered)
@@ -296,7 +308,7 @@ impl Ucd {
296308
NumericType::for_char(ch)
297309
} else {
298310
cold_path();
299-
lookup_property(NUMERIC_TYPE_DIFF, ch).unwrap_or_else(|| NumericType::for_char(ch))
311+
lookup_table(NUMERIC_TYPE_DIFF, ch).unwrap_or_else(|| NumericType::for_char(ch))
300312
};
301313

302314
expected.contains(&actual).then_some(ch)
@@ -307,7 +319,7 @@ impl Ucd {
307319
pub fn digit(&self, c: CodePoint) -> Option<u64> {
308320
let expected = [NumericType::Decimal, NumericType::Digit];
309321
self.numeric_type_matches(c, &expected).and_then(|ch| {
310-
let value = lookup_numeric_val(ch, true)?;
322+
let value = lookup_property_diff(NUMERIC_VALUES, &[], ch, true)?;
311323
let int = value as u64;
312324
(int as f64 == value).then_some(int)
313325
})
@@ -318,7 +330,7 @@ impl Ucd {
318330
pub fn decimal(&self, c: CodePoint) -> Option<u64> {
319331
let expected = [NumericType::Decimal];
320332
self.numeric_type_matches(c, &expected).and_then(|ch| {
321-
let value = lookup_numeric_val(ch, self.modern)?;
333+
let value = lookup_property_diff(NUMERIC_VALUES, NUMERIC_VALUES_DIFF, ch, self.modern)?;
322334
let int = value as u64;
323335
(int as f64 == value).then_some(int)
324336
})
@@ -328,8 +340,9 @@ impl Ucd {
328340
#[must_use]
329341
pub fn numeric(&self, c: CodePoint) -> Option<f64> {
330342
let expected = &NumericType::ALL_VALUES[1..];
331-
self.numeric_type_matches(c, expected)
332-
.and_then(|ch| lookup_numeric_val(ch, self.modern))
343+
self.numeric_type_matches(c, expected).and_then(|ch| {
344+
lookup_property_diff(NUMERIC_VALUES, NUMERIC_VALUES_DIFF, ch, self.modern)
345+
})
333346
}
334347

335348
#[must_use]

0 commit comments

Comments
 (0)