src/tools/unicode-table-generator/src/raw_emitter.rs

   1 use crate::fmt_list;
   2 use std::collections::{BTreeMap, BTreeSet, HashMap};
   3 use std::convert::TryFrom;
   4 use std::fmt::{self, Write};
   5 use std::ops::Range;
   6
   7 #[derive(Clone)]
   8 pub struct RawEmitter {
   9     pub file: String,
  10     pub desc: String,
  11     pub bytes_used: usize,
  12 }
  13
  14 impl RawEmitter {
  15     pub fn new() -> RawEmitter {
  16         RawEmitter { file: String::new(), bytes_used: 0, desc: String::new() }
  17     }
  18
  19     fn blank_line(&mut self) {
  20         if self.file.is_empty() || self.file.ends_with("\n\n") {
  21             return;
  22         }
  23         writeln!(&mut self.file).unwrap();
  24     }
  25
  26     fn emit_bitset(&mut self, ranges: &[Range<u32>]) -> Result<(), String> {
  27         let last_code_point = ranges.last().unwrap().end;
  28         // bitset for every bit in the codepoint range
  29         //
  30         // + 2 to ensure an all zero word to use for padding
  31         let mut buckets = vec![0u64; (last_code_point as usize / 64) + 2];
  32         for range in ranges {
  33             for codepoint in range.clone() {
  34                 let bucket = codepoint as usize / 64;
  35                 let bit = codepoint as u64 % 64;
  36                 buckets[bucket] |= 1 << bit;
  37             }
  38         }
  39
  40         let mut words = buckets;
  41         // Ensure that there's a zero word in the dataset, used for padding and
  42         // such.
  43         words.push(0);
  44         let unique_words =
  45             words.iter().cloned().collect::<BTreeSet<_>>().into_iter().collect::<Vec<_>>();
  46         if unique_words.len() > u8::MAX as usize {
  47             return Err(format!("cannot pack {} into 8 bits", unique_words.len()));
  48         }
  49         // needed for the chunk mapping to work
  50         assert_eq!(unique_words[0], 0, "has a zero word");
  51         let canonicalized = Canonicalized::canonicalize(&unique_words);
  52
  53         let word_indices = canonicalized.unique_mapping.clone();
  54         let compressed_words = words.iter().map(|w| word_indices[w]).collect::<Vec<u8>>();
  55
  56         let mut best = None;
  57         for length in 1..=64 {
  58             let mut temp = self.clone();
  59             temp.emit_chunk_map(word_indices[&0], &compressed_words, length);
  60             if let Some((_, size)) = best {
  61                 if temp.bytes_used < size {
  62                     best = Some((length, temp.bytes_used));
  63                 }
  64             } else {
  65                 best = Some((length, temp.bytes_used));
  66             }
  67         }
  68         self.emit_chunk_map(word_indices[&0], &compressed_words, best.unwrap().0);
  69
  70         struct Bits(u64);
  71         impl fmt::Debug for Bits {
  72             fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
  73                 write!(f, "0b{:064b}", self.0)
  74             }
  75         }
  76
  77         writeln!(
  78             &mut self.file,
  79             "static BITSET_CANONICAL: [u64; {}] = [{}];",
  80             canonicalized.canonical_words.len(),
  81             fmt_list(canonicalized.canonical_words.iter().map(|v| Bits(*v))),
  82         )
  83         .unwrap();
  84         self.bytes_used += 8 * canonicalized.canonical_words.len();
  85         writeln!(
  86             &mut self.file,
  87             "static BITSET_MAPPING: [(u8, u8); {}] = [{}];",
  88             canonicalized.canonicalized_words.len(),
  89             fmt_list(&canonicalized.canonicalized_words),
  90         )
  91         .unwrap();
  92         // 8 bit index into shifted words, 7 bits for shift + optional flip
  93         // We only need it for the words that we removed by applying a shift and
  94         // flip to them.
  95         self.bytes_used += 2 * canonicalized.canonicalized_words.len();
  96
  97         self.blank_line();
  98
  99         writeln!(&mut self.file, "pub fn lookup(c: char) -> bool {{").unwrap();
 100         writeln!(&mut self.file, "    super::bitset_search(",).unwrap();
 101         writeln!(&mut self.file, "        c as u32,").unwrap();
 102         writeln!(&mut self.file, "        &BITSET_CHUNKS_MAP,").unwrap();
 103         writeln!(&mut self.file, "        &BITSET_INDEX_CHUNKS,").unwrap();
 104         writeln!(&mut self.file, "        &BITSET_CANONICAL,").unwrap();
 105         writeln!(&mut self.file, "        &BITSET_MAPPING,").unwrap();
 106         writeln!(&mut self.file, "    )").unwrap();
 107         writeln!(&mut self.file, "}}").unwrap();
 108
 109         Ok(())
 110     }
 111
 112     fn emit_chunk_map(&mut self, zero_at: u8, compressed_words: &[u8], chunk_length: usize) {
 113         let mut compressed_words = compressed_words.to_vec();
 114         for _ in 0..(chunk_length - (compressed_words.len() % chunk_length)) {
 115             // pad out bitset index with zero words so we have all chunks of
 116             // chunkchunk_length
 117             compressed_words.push(zero_at);
 118         }
 119
 120         let mut chunks = BTreeSet::new();
 121         for chunk in compressed_words.chunks(chunk_length) {
 122             chunks.insert(chunk);
 123         }
 124         let chunk_map = chunks
 125             .clone()
 126             .into_iter()
 127             .enumerate()
 128             .map(|(idx, chunk)| (chunk, idx))
 129             .collect::<HashMap<_, _>>();
 130         let mut chunk_indices = Vec::new();
 131         for chunk in compressed_words.chunks(chunk_length) {
 132             chunk_indices.push(chunk_map[chunk]);
 133         }
 134
 135         writeln!(
 136             &mut self.file,
 137             "static BITSET_CHUNKS_MAP: [u8; {}] = [{}];",
 138             chunk_indices.len(),
 139             fmt_list(&chunk_indices),
 140         )
 141         .unwrap();
 142         self.bytes_used += chunk_indices.len();
 143         writeln!(
 144             &mut self.file,
 145             "static BITSET_INDEX_CHUNKS: [[u8; {}]; {}] = [{}];",
 146             chunk_length,
 147             chunks.len(),
 148             fmt_list(chunks.iter()),
 149         )
 150         .unwrap();
 151         self.bytes_used += chunk_length * chunks.len();
 152     }
 153 }
 154
 155 pub fn emit_codepoints(emitter: &mut RawEmitter, ranges: &[Range<u32>]) {
 156     emitter.blank_line();
 157
 158     let mut bitset = emitter.clone();
 159     let bitset_ok = bitset.emit_bitset(&ranges).is_ok();
 160
 161     let mut skiplist = emitter.clone();
 162     skiplist.emit_skiplist(&ranges);
 163
 164     if bitset_ok && bitset.bytes_used <= skiplist.bytes_used {
 165         *emitter = bitset;
 166         emitter.desc = String::from("bitset");
 167     } else {
 168         *emitter = skiplist;
 169         emitter.desc = String::from("skiplist");
 170     }
 171 }
 172
 173 struct Canonicalized {
 174     canonical_words: Vec<u64>,
 175     canonicalized_words: Vec<(u8, u8)>,
 176
 177     /// Maps an input unique word to the associated index (u8) which is into
 178     /// canonical_words or canonicalized_words (in order).
 179     unique_mapping: HashMap<u64, u8>,
 180 }
 181
 182 impl Canonicalized {
 183     fn canonicalize(unique_words: &[u64]) -> Self {
 184         #[derive(Copy, Clone, Debug)]
 185         enum Mapping {
 186             Rotate(u32),
 187             Invert,
 188             RotateAndInvert(u32),
 189             ShiftRight(u32),
 190         }
 191
 192         // key is the word being mapped to
 193         let mut mappings: BTreeMap<u64, Vec<(u64, Mapping)>> = BTreeMap::new();
 194         for &a in unique_words {
 195             'b: for &b in unique_words {
 196                 // skip self
 197                 if a == b {
 198                     continue;
 199                 }
 200
 201                 // All possible distinct rotations
 202                 for rotation in 1..64 {
 203                     if a.rotate_right(rotation) == b {
 204                         mappings.entry(b).or_default().push((a, Mapping::Rotate(rotation)));
 205                         // We're not interested in further mappings between a and b
 206                         continue 'b;
 207                     }
 208                 }
 209
 210                 if (!a) == b {
 211                     mappings.entry(b).or_default().push((a, Mapping::Invert));
 212                     // We're not interested in further mappings between a and b
 213                     continue 'b;
 214                 }
 215
 216                 // All possible distinct rotations, inverted
 217                 for rotation in 1..64 {
 218                     if (!a.rotate_right(rotation)) == b {
 219                         mappings
 220                             .entry(b)
 221                             .or_default()
 222                             .push((a, Mapping::RotateAndInvert(rotation)));
 223                         // We're not interested in further mappings between a and b
 224                         continue 'b;
 225                     }
 226                 }
 227
 228                 // All possible shifts
 229                 for shift_by in 1..64 {
 230                     if a == (b >> shift_by) {
 231                         mappings
 232                             .entry(b)
 233                             .or_default()
 234                             .push((a, Mapping::ShiftRight(shift_by as u32)));
 235                         // We're not interested in further mappings between a and b
 236                         continue 'b;
 237                     }
 238                 }
 239             }
 240         }
 241         // These are the bitset words which will be represented "raw" (as a u64)
 242         let mut canonical_words = Vec::new();
 243         // These are mapped words, which will be represented by an index into
 244         // the canonical_words and a Mapping; u16 when encoded.
 245         let mut canonicalized_words = Vec::new();
 246         let mut unique_mapping = HashMap::new();
 247
 248         #[derive(Debug, PartialEq, Eq)]
 249         enum UniqueMapping {
 250             Canonical(usize),
 251             Canonicalized(usize),
 252         }
 253
 254         // Map 0 first, so that it is the first canonical word.
 255         // This is realistically not inefficient because 0 is not mapped to by
 256         // anything else (a shift pattern could do it, but would be wasteful).
 257         //
 258         // However, 0s are quite common in the overall dataset, and it is quite
 259         // wasteful to have to go through a mapping function to determine that
 260         // we have a zero.
 261         //
 262         // FIXME: Experiment with choosing most common words in overall data set
 263         // for canonical when possible.
 264         while let Some((&to, _)) = mappings
 265             .iter()
 266             .find(|(&to, _)| to == 0)
 267             .or_else(|| mappings.iter().max_by_key(|m| m.1.len()))
 268         {
 269             // Get the mapping with the most entries. Currently, no mapping can
 270             // only exist transitively (i.e., there is no A, B, C such that A
 271             // does not map to C and but A maps to B maps to C), so this is
 272             // guaranteed to be acceptable.
 273             //
 274             // In the future, we may need a more sophisticated algorithm to
 275             // identify which keys to prefer as canonical.
 276             let mapped_from = mappings.remove(&to).unwrap();
 277             for (from, how) in &mapped_from {
 278                 // Remove the entries which mapped to this one.
 279                 // Noting that it should be associated with the Nth canonical word.
 280                 //
 281                 // We do not assert that this is present, because there may be
 282                 // no mappings to the `from` word; that's fine.
 283                 mappings.remove(from);
 284                 assert_eq!(
 285                     unique_mapping
 286                         .insert(*from, UniqueMapping::Canonicalized(canonicalized_words.len())),
 287                     None
 288                 );
 289                 canonicalized_words.push((canonical_words.len(), *how));
 290
 291                 // Remove the now-canonicalized word from other mappings,
 292                 // to ensure that we deprioritize them in the next iteration of
 293                 // the while loop.
 294                 for mapped in mappings.values_mut() {
 295                     let mut i = 0;
 296                     while i != mapped.len() {
 297                         if mapped[i].0 == *from {
 298                             mapped.remove(i);
 299                         } else {
 300                             i += 1;
 301                         }
 302                     }
 303                 }
 304             }
 305             assert!(
 306                 unique_mapping
 307                     .insert(to, UniqueMapping::Canonical(canonical_words.len()))
 308                     .is_none()
 309             );
 310             canonical_words.push(to);
 311
 312             // Remove the now-canonical word from other mappings, to ensure that
 313             // we deprioritize them in the next iteration of the while loop.
 314             for mapped in mappings.values_mut() {
 315                 let mut i = 0;
 316                 while i != mapped.len() {
 317                     if mapped[i].0 == to {
 318                         mapped.remove(i);
 319                     } else {
 320                         i += 1;
 321                     }
 322                 }
 323             }
 324         }
 325
 326         // Any words which we couldn't shrink, just stick into the canonical
 327         // words.
 328         //
 329         // FIXME: work harder -- there are more possibilities for mapping
 330         // functions (e.g., multiplication, shifting instead of rotation, etc.)
 331         // We'll probably always have some slack though so this loop will still
 332         // be needed.
 333         for &w in unique_words {
 334             if !unique_mapping.contains_key(&w) {
 335                 assert!(
 336                     unique_mapping
 337                         .insert(w, UniqueMapping::Canonical(canonical_words.len()))
 338                         .is_none()
 339                 );
 340                 canonical_words.push(w);
 341             }
 342         }
 343         assert_eq!(canonicalized_words.len() + canonical_words.len(), unique_words.len());
 344         assert_eq!(unique_mapping.len(), unique_words.len());
 345
 346         let unique_mapping = unique_mapping
 347             .into_iter()
 348             .map(|(key, value)| {
 349                 (
 350                     key,
 351                     match value {
 352                         UniqueMapping::Canonicalized(idx) => {
 353                             u8::try_from(canonical_words.len() + idx).unwrap()
 354                         }
 355                         UniqueMapping::Canonical(idx) => u8::try_from(idx).unwrap(),
 356                     },
 357                 )
 358             })
 359             .collect::<HashMap<_, _>>();
 360
 361         let mut distinct_indices = BTreeSet::new();
 362         for &w in unique_words {
 363             let idx = unique_mapping.get(&w).unwrap();
 364             assert!(distinct_indices.insert(idx));
 365         }
 366
 367         const LOWER_6: u32 = (1 << 6) - 1;
 368
 369         let canonicalized_words = canonicalized_words
 370             .into_iter()
 371             .map(|v| {
 372                 (
 373                     u8::try_from(v.0).unwrap(),
 374                     match v.1 {
 375                         Mapping::RotateAndInvert(amount) => {
 376                             assert_eq!(amount, amount & LOWER_6);
 377                             1 << 6 | (amount as u8)
 378                         }
 379                         Mapping::Rotate(amount) => {
 380                             assert_eq!(amount, amount & LOWER_6);
 381                             amount as u8
 382                         }
 383                         Mapping::Invert => 1 << 6,
 384                         Mapping::ShiftRight(shift_by) => {
 385                             assert_eq!(shift_by, shift_by & LOWER_6);
 386                             1 << 7 | (shift_by as u8)
 387                         }
 388                     },
 389                 )
 390             })
 391             .collect::<Vec<(u8, u8)>>();
 392         Canonicalized { unique_mapping, canonical_words, canonicalized_words }
 393     }
 394 }