1 //! This implements the core logic of the compression scheme used to compactly
2 //! encode Unicode properties.
4 //! We have two primary goals with the encoding: we want to be compact, because
5 //! these tables often end up in ~every Rust program (especially the
6 //! grapheme_extend table, used for str debugging), including those for embedded
7 //! targets (where space is important). We also want to be relatively fast,
8 //! though this is more of a nice to have rather than a key design constraint.
9 //! It is expected that libraries/applications which are performance-sensitive
10 //! to Unicode property lookups are extremely rare, and those that care may find
11 //! the tradeoff of the raw bitsets worth it. For most applications, a
12 //! relatively fast but much smaller (and as such less cache-impacting, etc.)
13 //! data set is likely preferable.
15 //! We have two separate encoding schemes: a skiplist-like approach, and a
16 //! compressed bitset. The datasets we consider mostly use the skiplist (it's
17 //! smaller) but the lowercase and uppercase sets are sufficiently sparse for
18 //! the bitset to be worthwhile -- for those sets the bitset is a 2x size win.
19 //! Since the bitset is also faster, this seems an obvious choice. (As a
20 //! historical note, the bitset was also the prior implementation, so its
21 //! relative complexity had already been paid).
25 //! The primary idea is that we 'flatten' the Unicode ranges into an enormous
26 //! bitset. To represent any arbitrary codepoint in a raw bitset, we would need
27 //! over 17 kilobytes of data per character set -- way too much for our
30 //! First, the raw bitset (one bit for every valid `char`, from 0 to 0x10FFFF,
31 //! not skipping the small 'gap') is associated into words (u64) and
32 //! deduplicated. On random data, this would be useless; on our data, this is
33 //! incredibly beneficial -- our data sets have (far) less than 256 unique
36 //! This gives us an array that maps `u8 -> word`; the current algorithm does
37 //! not handle the case of more than 256 unique words, but we are relatively far
38 //! from coming that close.
40 //! With that scheme, we now have a single byte for every 64 codepoints.
42 //! We further chunk these by some constant N (between 1 and 64 per group,
43 //! dynamically chosen for smallest size), and again deduplicate and store in an
44 //! array (u8 -> [u8; N]).
46 //! The bytes of this array map into the words from the bitset above, but we
47 //! apply another trick here: some of these words are similar enough that they
48 //! can be represented by some function of another word. The particular
49 //! functions chosen are rotation, inversion, and shifting (right).
53 //! The skip list arose out of the desire for an even smaller encoding than the
54 //! bitset -- and was the answer to the question "what is the smallest
55 //! representation we can imagine?". However, it is not necessarily the
56 //! smallest, and if you have a better proposal, please do suggest it!
58 //! This is a relatively straightforward encoding. First, we break up all the
59 //! ranges in the input data into offsets from each other, essentially a gap
60 //! encoding. In practice, most gaps are small -- less than u8::MAX -- so we
61 //! store those directly. We make use of the larger gaps (which are nicely
62 //! interspersed already) throughout the dataset to index this data set.
64 //! In particular, each run of small gaps (terminating in a large gap) is
65 //! indexed in a separate dataset. That data set stores an index into the
66 //! primary offset list and a prefix sum of that offset list. These are packed
67 //! into a single u32 (11 bits for the offset, 21 bits for the prefix sum).
69 //! Lookup proceeds via a binary search in the index and then a straightforward
70 //! linear scan (adding up the offsets) until we reach the needle, and then the
71 //! index of that offset is utilized as the answer to whether we're in the set
74 use std::collections::{BTreeMap, HashMap};
76 use ucd_parse::Codepoints;
83 use raw_emitter::{emit_codepoints, RawEmitter};
85 static PROPERTIES: &[&str] = &[
98 ranges: Vec<(&'static str, Vec<Range<u32>>)>,
99 to_upper: BTreeMap<u32, (u32, u32, u32)>,
100 to_lower: BTreeMap<u32, (u32, u32, u32)>,
103 fn to_mapping(origin: u32, codepoints: Vec<ucd_parse::Codepoint>) -> Option<(u32, u32, u32)> {
108 for codepoint in codepoints {
109 if origin == codepoint.value() {
114 a = Some(codepoint.value());
115 } else if b.is_none() {
116 b = Some(codepoint.value());
117 } else if c.is_none() {
118 c = Some(codepoint.value());
120 panic!("more than 3 mapped codepoints")
124 Some((a.unwrap(), b.unwrap_or(0), c.unwrap_or(0)))
127 static UNICODE_DIRECTORY: &str = "unicode-downloads";
129 fn load_data() -> UnicodeData {
130 unicode_download::fetch_latest();
132 let mut properties = HashMap::new();
133 for row in ucd_parse::parse::<_, ucd_parse::CoreProperty>(&UNICODE_DIRECTORY).unwrap() {
134 if let Some(name) = PROPERTIES.iter().find(|prop| **prop == row.property.as_str()) {
135 properties.entry(*name).or_insert_with(Vec::new).push(row.codepoints);
138 for row in ucd_parse::parse::<_, ucd_parse::Property>(&UNICODE_DIRECTORY).unwrap() {
139 if let Some(name) = PROPERTIES.iter().find(|prop| **prop == row.property.as_str()) {
140 properties.entry(*name).or_insert_with(Vec::new).push(row.codepoints);
144 let mut to_lower = BTreeMap::new();
145 let mut to_upper = BTreeMap::new();
146 for row in ucd_parse::UnicodeDataExpander::new(
147 ucd_parse::parse::<_, ucd_parse::UnicodeData>(&UNICODE_DIRECTORY).unwrap(),
149 let general_category = if ["Nd", "Nl", "No"].contains(&row.general_category.as_str()) {
152 row.general_category.as_str()
154 if let Some(name) = PROPERTIES.iter().find(|prop| **prop == general_category) {
157 .or_insert_with(Vec::new)
158 .push(Codepoints::Single(row.codepoint));
161 if let Some(mapped) = row.simple_lowercase_mapping {
162 if mapped != row.codepoint {
163 to_lower.insert(row.codepoint.value(), (mapped.value(), 0, 0));
166 if let Some(mapped) = row.simple_uppercase_mapping {
167 if mapped != row.codepoint {
168 to_upper.insert(row.codepoint.value(), (mapped.value(), 0, 0));
173 for row in ucd_parse::parse::<_, ucd_parse::SpecialCaseMapping>(&UNICODE_DIRECTORY).unwrap() {
174 if !row.conditions.is_empty() {
175 // Skip conditional case mappings
179 let key = row.codepoint.value();
180 if let Some(lower) = to_mapping(key, row.lowercase) {
181 to_lower.insert(key, lower);
183 if let Some(upper) = to_mapping(key, row.uppercase) {
184 to_upper.insert(key, upper);
188 let mut properties: HashMap<&'static str, Vec<Range<u32>>> = properties
194 .flat_map(|codepoints| match codepoints {
195 Codepoints::Single(c) => c
197 .map(|ch| (ch as u32..ch as u32 + 1))
199 .collect::<Vec<_>>(),
200 Codepoints::Range(c) => c
202 .flat_map(|c| c.scalar().map(|ch| (ch as u32..ch as u32 + 1)))
203 .collect::<Vec<_>>(),
205 .collect::<Vec<Range<u32>>>(),
210 for ranges in properties.values_mut() {
211 merge_ranges(ranges);
214 let mut properties = properties.into_iter().collect::<Vec<_>>();
215 properties.sort_by_key(|p| p.0);
216 UnicodeData { ranges: properties, to_lower, to_upper }
220 let write_location = std::env::args().nth(1).unwrap_or_else(|| {
221 eprintln!("Must provide path to write unicode tables to");
223 "e.g. {} library/core/unicode/unicode_data.rs",
224 std::env::args().next().unwrap_or_default()
226 std::process::exit(1);
229 // Optional test path, which is a Rust source file testing that the unicode
230 // property lookups are correct.
231 let test_path = std::env::args().nth(2);
233 let unicode_data = load_data();
234 let ranges_by_property = &unicode_data.ranges;
236 if let Some(path) = test_path {
237 std::fs::write(&path, generate_tests(&write_location, &ranges_by_property)).unwrap();
240 let mut total_bytes = 0;
241 let mut modules = Vec::new();
242 for (property, ranges) in ranges_by_property {
243 let datapoints = ranges.iter().map(|r| r.end - r.start).sum::<u32>();
244 let mut emitter = RawEmitter::new();
245 emit_codepoints(&mut emitter, &ranges);
247 modules.push((property.to_lowercase().to_string(), emitter.file));
249 "{:15}: {} bytes, {} codepoints in {} ranges ({} - {}) using {}",
254 ranges.first().unwrap().start,
255 ranges.last().unwrap().end,
258 total_bytes += emitter.bytes_used;
261 let mut table_file = String::new();
264 "///! This file is generated by src/tools/unicode-table-generator; do not edit manually!\n",
267 // Include the range search function
268 table_file.push('\n');
269 table_file.push_str(include_str!("range_search.rs"));
270 table_file.push('\n');
272 table_file.push_str(&version());
274 table_file.push('\n');
276 modules.push((String::from("conversions"), case_mapping::generate_case_mapping(&unicode_data)));
278 for (name, contents) in modules {
279 table_file.push_str("#[rustfmt::skip]\n");
280 table_file.push_str(&format!("pub mod {} {{\n", name));
281 for line in contents.lines() {
282 if !line.trim().is_empty() {
283 table_file.push_str(" ");
284 table_file.push_str(&line);
286 table_file.push('\n');
288 table_file.push_str("}\n\n");
291 std::fs::write(&write_location, format!("{}\n", table_file.trim_end())).unwrap();
293 println!("Total table sizes: {} bytes", total_bytes);
296 fn version() -> String {
297 let mut out = String::new();
298 out.push_str("pub const UNICODE_VERSION: (u8, u8, u8) = ");
301 std::fs::read_to_string(std::path::Path::new(UNICODE_DIRECTORY).join("ReadMe.txt"))
304 let prefix = "for Version ";
305 let start = readme.find(prefix).unwrap() + prefix.len();
306 let end = readme.find(" of the Unicode Standard.").unwrap();
308 readme[start..end].split('.').map(|v| v.parse::<u32>().expect(&v)).collect::<Vec<_>>();
309 let [major, minor, micro] = [version[0], version[1], version[2]];
311 out.push_str(&format!("({}, {}, {});\n", major, minor, micro));
315 fn fmt_list<V: std::fmt::Debug>(values: impl IntoIterator<Item = V>) -> String {
316 let pieces = values.into_iter().map(|b| format!("{:?}, ", b)).collect::<Vec<_>>();
317 let mut out = String::new();
318 let mut line = format!("\n ");
319 for piece in pieces {
320 if line.len() + piece.len() < 98 {
321 line.push_str(&piece);
323 out.push_str(line.trim_end());
325 line = format!(" {}", piece);
328 out.push_str(line.trim_end());
333 fn generate_tests(data_path: &str, ranges: &[(&str, Vec<Range<u32>>)]) -> String {
334 let mut s = String::new();
335 s.push_str("#![allow(incomplete_features, unused)]\n");
336 s.push_str("#![feature(const_generics)]\n\n");
337 s.push_str("\n#[allow(unused)]\nuse std::hint;\n");
338 s.push_str(&format!("#[path = \"{}\"]\n", data_path));
339 s.push_str("mod unicode_data;\n\n");
341 s.push_str("\nfn main() {\n");
343 for (property, ranges) in ranges {
344 s.push_str(&format!(r#" println!("Testing {}");"#, property));
346 s.push_str(&format!(" {}_true();\n", property.to_lowercase()));
347 s.push_str(&format!(" {}_false();\n", property.to_lowercase()));
348 let mut is_true = Vec::new();
349 let mut is_false = Vec::new();
350 for ch_num in 0..(std::char::MAX as u32) {
351 if std::char::from_u32(ch_num).is_none() {
354 if ranges.iter().any(|r| r.contains(&ch_num)) {
355 is_true.push(ch_num);
357 is_false.push(ch_num);
361 s.push_str(&format!(" fn {}_true() {{\n", property.to_lowercase()));
362 generate_asserts(&mut s, property, &is_true, true);
363 s.push_str(" }\n\n");
364 s.push_str(&format!(" fn {}_false() {{\n", property.to_lowercase()));
365 generate_asserts(&mut s, property, &is_false, false);
366 s.push_str(" }\n\n");
373 fn generate_asserts(s: &mut String, property: &str, points: &[u32], truthy: bool) {
374 for range in ranges_from_set(points) {
375 if range.end == range.start + 1 {
377 " assert!({}unicode_data::{}::lookup({:?}), \"{}\");\n",
378 if truthy { "" } else { "!" },
379 property.to_lowercase(),
380 std::char::from_u32(range.start).unwrap(),
384 s.push_str(&format!(" for chn in {:?}u32 {{\n", range));
386 " assert!({}unicode_data::{}::lookup(std::char::from_u32(chn).unwrap()), \"{{:?}}\", chn);\n",
387 if truthy { "" } else { "!" },
388 property.to_lowercase(),
395 fn ranges_from_set(set: &[u32]) -> Vec<Range<u32>> {
396 let mut ranges = set.iter().map(|e| (*e)..(*e + 1)).collect::<Vec<Range<u32>>>();
397 merge_ranges(&mut ranges);
401 fn merge_ranges(ranges: &mut Vec<Range<u32>>) {
403 let mut new_ranges = Vec::new();
404 let mut idx_iter = 0..(ranges.len() - 1);
405 let mut should_insert_last = true;
406 while let Some(idx) = idx_iter.next() {
407 let cur = ranges[idx].clone();
408 let next = ranges[idx + 1].clone();
409 if cur.end == next.start {
410 if idx_iter.next().is_none() {
411 // We're merging the last element
412 should_insert_last = false;
414 new_ranges.push(cur.start..next.end);
416 // We're *not* merging the last element
417 should_insert_last = true;
418 new_ranges.push(cur);
421 if should_insert_last {
422 new_ranges.push(ranges.last().unwrap().clone());
424 if new_ranges.len() == ranges.len() {
425 *ranges = new_ranges;
428 *ranges = new_ranges;
432 let mut last_end = None;
433 for range in ranges {
434 if let Some(last) = last_end {
435 assert!(range.start > last, "{:?}", range);
437 last_end = Some(range.end);