lindera_dictionary/dictionary/
character_definition.rs

1use rkyv::{Archive, Deserialize as RkyvDeserialize, Serialize as RkyvSerialize};
2use serde::{Deserialize, Serialize};
3
4use crate::LinderaResult;
5use crate::error::LinderaErrorKind;
6
7#[derive(Serialize, Deserialize, Debug, Copy, Clone, Archive, RkyvSerialize, RkyvDeserialize)]
8
9pub struct CategoryData {
10    pub invoke: bool,
11    pub group: bool,
12    pub length: u32,
13}
14
15#[derive(
16    Serialize,
17    Deserialize,
18    Clone,
19    Debug,
20    Hash,
21    Copy,
22    PartialOrd,
23    Ord,
24    Eq,
25    PartialEq,
26    Archive,
27    RkyvSerialize,
28    RkyvDeserialize,
29)]
30
31pub struct CategoryId(pub usize);
32
33#[derive(Serialize, Deserialize, Clone, Archive, RkyvSerialize, RkyvDeserialize)]
34
35pub struct LookupTable<T: Copy + Clone> {
36    boundaries: Vec<u32>,
37    values: Vec<Vec<T>>,
38}
39
40impl<T: Copy + Clone> LookupTable<T> {
41    pub fn from_fn(mut boundaries: Vec<u32>, funct: &dyn Fn(u32, &mut Vec<T>)) -> LookupTable<T> {
42        if !boundaries.contains(&0) {
43            boundaries.push(0);
44        }
45        boundaries.sort_unstable();
46        let mut values = Vec::new();
47        for &boundary in &boundaries {
48            let mut output = Vec::default();
49            funct(boundary, &mut output);
50            values.push(output);
51        }
52        LookupTable { boundaries, values }
53    }
54
55    pub fn eval(&self, target: u32) -> &[T] {
56        let idx = self
57            .boundaries
58            .binary_search(&target)
59            .unwrap_or_else(|val| val - 1);
60        &self.values[idx][..]
61    }
62}
63
64/// Number of codepoints covered by the flat category table (the Basic
65/// Multilingual Plane).
66const FLAT_TABLE_LEN: usize = 0x10000;
67
68/// Maximum categories per codepoint representable in a packed `flat_index`
69/// entry (8 bits of length).
70const FLAT_MAX_ROW_LEN: usize = 0xFF;
71
72/// Maximum pool offset representable in a packed `flat_index` entry (24 bits).
73const FLAT_MAX_OFFSET: usize = (1 << 24) - 1;
74
75#[derive(Clone, Serialize, Deserialize, Archive, RkyvSerialize, RkyvDeserialize)]
76
77pub struct CharacterDefinition {
78    pub category_definitions: Vec<CategoryData>,
79    pub category_names: Vec<String>,
80    pub mapping: LookupTable<CategoryId>,
81    /// Concatenation of the `mapping` rows in row order; the backing pool
82    /// sliced by `flat_index`. Runtime-only: skipped by serde and rkyv (a
83    /// trailing zero-sized member in the archived layout), rebuilt at load.
84    #[serde(skip)]
85    #[rkyv(with = ::rkyv::with::Skip)]
86    flat_categories: Vec<CategoryId>,
87    /// Per-BMP-codepoint packed `offset << 8 | len` into `flat_categories`,
88    /// `FLAT_TABLE_LEN` entries; empty when the table is not built, in which
89    /// case lookups fall back to the `mapping` binary search. Runtime-only:
90    /// skipped by serde and rkyv, rebuilt at load.
91    #[serde(skip)]
92    #[rkyv(with = ::rkyv::with::Skip)]
93    flat_index: Vec<u32>,
94}
95
96impl CharacterDefinition {
97    /// Creates a definition from its parsed parts and builds the flat
98    /// BMP category table.
99    ///
100    /// # Arguments
101    ///
102    /// * `category_definitions` - Per-category invoke/group/length flags.
103    /// * `category_names` - Category names in `CategoryId` order.
104    /// * `mapping` - Codepoint-range to category-set lookup table.
105    ///
106    /// # Returns
107    ///
108    /// A `CharacterDefinition` ready for O(1) BMP category lookups.
109    pub fn new(
110        category_definitions: Vec<CategoryData>,
111        category_names: Vec<String>,
112        mapping: LookupTable<CategoryId>,
113    ) -> Self {
114        let mut definition = CharacterDefinition {
115            category_definitions,
116            category_names,
117            mapping,
118            flat_categories: Vec::new(),
119            flat_index: Vec::new(),
120        };
121        definition.build_flat_table();
122        definition
123    }
124
125    /// Builds the flat BMP category table from `mapping`.
126    ///
127    /// Leaves the table empty (falling back to the binary search) if a row
128    /// exceeds the packed-entry limits, which no real char.def can reach.
129    fn build_flat_table(&mut self) {
130        let mut pool: Vec<CategoryId> = Vec::new();
131        // One packed (offset, len) per mapping row, in row order.
132        let mut packed_rows: Vec<u32> = Vec::with_capacity(self.mapping.values.len());
133        for row in &self.mapping.values {
134            let offset = pool.len();
135            if row.len() > FLAT_MAX_ROW_LEN || offset > FLAT_MAX_OFFSET {
136                return;
137            }
138            pool.extend_from_slice(row);
139            packed_rows.push(((offset as u32) << 8) | row.len() as u32);
140        }
141
142        let mut index = Vec::with_capacity(FLAT_TABLE_LEN);
143        for cp in 0..FLAT_TABLE_LEN as u32 {
144            let row_idx = self
145                .mapping
146                .boundaries
147                .binary_search(&cp)
148                .unwrap_or_else(|val| val - 1);
149            index.push(packed_rows[row_idx]);
150        }
151
152        self.flat_categories = pool;
153        self.flat_index = index;
154    }
155
156    pub fn categories(&self) -> &[String] {
157        &self.category_names[..]
158    }
159
160    pub fn load(char_def_data: &[u8]) -> LinderaResult<CharacterDefinition> {
161        let mut aligned = rkyv::util::AlignedVec::<16>::new();
162        aligned.extend_from_slice(char_def_data);
163        let mut definition = rkyv::from_bytes::<CharacterDefinition, rkyv::rancor::Error>(&aligned)
164            .map_err(|err| {
165                LinderaErrorKind::Deserialize.with_error(anyhow::anyhow!(err.to_string()))
166            })?;
167        // The flat table is not serialized; rebuild it after deserialization.
168        definition.build_flat_table();
169        Ok(definition)
170    }
171
172    pub fn lookup_definition(&self, category_id: CategoryId) -> &CategoryData {
173        &self.category_definitions[category_id.0]
174    }
175
176    pub fn category_name(&self, category_id: CategoryId) -> &str {
177        &self.category_names[category_id.0]
178    }
179
180    pub fn category_id_by_name(&self, name: &str) -> Option<CategoryId> {
181        self.category_names
182            .iter()
183            .position(|n| n == name)
184            .map(CategoryId)
185    }
186
187    pub fn lookup_categories(&self, c: char) -> &[CategoryId] {
188        let cp = c as u32;
189        if (cp as usize) < FLAT_TABLE_LEN && !self.flat_index.is_empty() {
190            // O(1) fast path: one indexed load plus a slice into the pool,
191            // returning exactly the slice the binary search would.
192            let packed = self.flat_index[cp as usize];
193            let offset = (packed >> 8) as usize;
194            let len = (packed & 0xFF) as usize;
195            &self.flat_categories[offset..offset + len]
196        } else {
197            self.mapping.eval(cp)
198        }
199    }
200}
201
202#[cfg(test)]
203mod tests {
204    use crate::dictionary::character_definition::{
205        CategoryData, CategoryId, CharacterDefinition, LookupTable,
206    };
207
208    #[test]
209    fn test_lookup_table() {
210        let funct = |c: u32, output: &mut Vec<u32>| {
211            if c >= 10u32 {
212                output.push(1u32);
213            } else {
214                output.push(0u32);
215            }
216        };
217        let lookup_table = LookupTable::from_fn(vec![0u32, 10u32], &funct);
218        for i in 0..100 {
219            let mut v = Vec::default();
220            funct(i, &mut v);
221            assert_eq!(lookup_table.eval(i), &v[..]);
222        }
223    }
224
225    /// Builds a small multi-category definition whose ranges cross the
226    /// codepoint space, including a multi-category row and a boundary
227    /// beyond the BMP.
228    fn test_definition() -> CharacterDefinition {
229        let mapping = LookupTable::from_fn(
230            vec![0u32, 0x80, 0x3040, 0x4E00, 0x20000],
231            &|c, buff: &mut Vec<CategoryId>| {
232                if c >= 0x20000 {
233                    buff.push(CategoryId(3));
234                } else if c >= 0x4E00 {
235                    // Multi-category row: order must be preserved.
236                    buff.push(CategoryId(2));
237                    buff.push(CategoryId(1));
238                } else if c >= 0x3040 {
239                    buff.push(CategoryId(1));
240                } else if c >= 0x80 {
241                    buff.push(CategoryId(3));
242                } else {
243                    buff.push(CategoryId(0));
244                }
245            },
246        );
247        let categories = vec![
248            CategoryData {
249                invoke: false,
250                group: true,
251                length: 0,
252            };
253            4
254        ];
255        let names = vec!["A".into(), "B".into(), "C".into(), "D".into()];
256        CharacterDefinition::new(categories, names, mapping)
257    }
258
259    /// Regression test for #878 stage 2: the flat BMP table must return
260    /// exactly the slice (contents and order) the binary search returns,
261    /// for every codepoint including the astral fallback.
262    #[test]
263    fn test_flat_table_matches_binary_search_for_all_chars() {
264        let definition = test_definition();
265        assert!(
266            !definition.flat_index.is_empty(),
267            "flat table should be built"
268        );
269        for cp in 0..=0x10FFFFu32 {
270            let Some(c) = char::from_u32(cp) else {
271                continue; // surrogate range
272            };
273            assert_eq!(
274                definition.lookup_categories(c),
275                definition.mapping.eval(cp),
276                "mismatch at U+{cp:04X}"
277            );
278        }
279    }
280
281    /// Regression test for #878 stage 2: the flat table is skipped during
282    /// serialization and rebuilt by `load()`, and lookups survive the
283    /// round-trip unchanged.
284    #[test]
285    fn test_flat_table_rebuilt_after_rkyv_round_trip() {
286        let definition = test_definition();
287        let bytes = rkyv::to_bytes::<rkyv::rancor::Error>(&definition).unwrap();
288        let reloaded = CharacterDefinition::load(&bytes).unwrap();
289        assert!(!reloaded.flat_index.is_empty(), "load() must rebuild");
290        for cp in [0u32, 0x41, 0x80, 0x3042, 0x4E8C, 0xFFFF, 0x20B9F] {
291            let c = char::from_u32(cp).unwrap();
292            assert_eq!(
293                reloaded.lookup_categories(c),
294                definition.lookup_categories(c)
295            );
296        }
297    }
298}
lindera_dictionary/dictionary/character_definition.rs

lindera_dictionary/dictionary/
character_definition.rs
