sudachi/input_text/
buffer.rs

1/*
2 *  Copyright (c) 2021-2026 Works Applications Co., Ltd.
3 *
4 *  Licensed under the Apache License, Version 2.0 (the "License");
5 *  you may not use this file except in compliance with the License.
6 *  You may obtain a copy of the License at
7 *
8 *      http://www.apache.org/licenses/LICENSE-2.0
9 *
10 *   Unless required by applicable law or agreed to in writing, software
11 *  distributed under the License is distributed on an "AS IS" BASIS,
12 *  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 *  See the License for the specific language governing permissions and
14 *  limitations under the License.
15 */
16
17mod edit;
18#[cfg(test)]
19mod test_basic;
20#[cfg(test)]
21mod test_ported;
22
23pub use self::edit::InputEditor;
24use crate::dic::category_type::CategoryType;
25use crate::dic::grammar::Grammar;
26use std::ops::Range;
27
28use crate::error::{SudachiError, SudachiResult};
29use crate::input_text::InputTextIndex;
30
31/// limit on the maximum length of the input types, in bytes, 3/4 of u16::MAX
32const MAX_LENGTH: usize = u16::MAX as usize / 4 * 3;
33
34/// if the limit of the rewritten sentence is more than this number, then all bets are off
35const REALLY_MAX_LENGTH: usize = u16::MAX as usize;
36
37#[derive(Eq, PartialEq, Debug, Clone, Default)]
38enum BufferState {
39    #[default]
40    Clean,
41    RW,
42    RO,
43}
44
45/// InputBuffer - prepares the input data for the analysis
46///
47/// By saying char we actually mean Unicode codepoint here.
48/// In the context of this struct these terms are synonyms.
49#[derive(Default, Clone)]
50pub struct InputBuffer {
51    /// Original input data, output is done on this
52    original: String,
53    /// Normalized input data, analysis is done on this. Byte-based indexing.
54    modified: String,
55    /// Buffer for normalization, reusing allocations
56    modified_2: String,
57    /// Byte mapping from normalized data to originals.
58    /// Only values lying on codepoint boundaries are correct. Byte-based indexing.
59    m2o: Vec<usize>,
60    /// Buffer for normalization.
61    /// After building it is used as byte-to-char mapping for original data.
62    m2o_2: Vec<usize>,
63    /// Characters of the modified string. Char-based indexing.
64    mod_chars: Vec<char>,
65    /// Char-to-byte mapping for the modified string. Char-based indexing.
66    mod_c2b: Vec<usize>,
67    /// Byte-to-char mapping for the modified string. Byte-based indexing.
68    mod_b2c: Vec<usize>,
69    /// Markers whether the byte can start new word or not
70    mod_bow: Vec<bool>,
71    /// Character categories. Char-based indexing.
72    mod_cat: Vec<CategoryType>,
73    /// Number of codepoints with the same category. Char-based indexing.
74    mod_cat_continuity: Vec<usize>,
75    /// This very temporarily keeps the replacement data.
76    /// 'static lifetime is a lie and it is **incorrect** to use
77    /// it outside `with_replacer` function or its callees.
78    replaces: Vec<edit::ReplaceOp<'static>>,
79    /// Current state of the buffer
80    state: BufferState,
81}
82
83impl InputBuffer {
84    /// Creates new InputBuffer
85    pub fn new() -> InputBuffer {
86        InputBuffer::default()
87    }
88
89    /// Resets the input buffer, so it could be used to process new input.
90    /// New input should be written to the returned mutable reference.
91    pub fn reset(&mut self) -> &mut String {
92        // extended buffers can be ignored during cleaning,
93        // they will be cleaned before usage automatically
94        self.original.clear();
95        self.modified.clear();
96        self.m2o.clear();
97        self.mod_chars.clear();
98        self.mod_c2b.clear();
99        self.mod_b2c.clear();
100        self.mod_bow.clear();
101        self.mod_cat.clear();
102        self.mod_cat_continuity.clear();
103        self.state = BufferState::Clean;
104        &mut self.original
105    }
106
107    /// Creates input from the passed string. Should be used mostly for tests.
108    ///
109    /// Panics if the input string is too long.
110    pub fn from<T: AsRef<str>>(data: T) -> InputBuffer {
111        let mut buf = Self::new();
112        buf.reset().push_str(data.as_ref());
113        buf.start_build().expect("");
114        buf
115    }
116
117    /// Moves InputBuffer into RW state, making it possible to perform edits on it
118    pub fn start_build(&mut self) -> SudachiResult<()> {
119        if self.original.len() > MAX_LENGTH {
120            return Err(SudachiError::InputTooLong(self.original.len(), MAX_LENGTH));
121        }
122        debug_assert_eq!(self.state, BufferState::Clean);
123        self.state = BufferState::RW;
124        self.modified.push_str(&self.original);
125        self.m2o.extend(0..self.modified.len() + 1);
126        Ok(())
127    }
128
129    /// Finalizes InputBuffer state, making it RO
130    pub fn build(&mut self, grammar: &Grammar) -> SudachiResult<()> {
131        debug_assert_eq!(self.state, BufferState::RW);
132        self.state = BufferState::RO;
133        self.mod_chars.clear();
134        let cats = &grammar.character_category;
135        let mut last_offset = 0;
136        let mut last_chidx = 0;
137
138        // Match the Java implementation: only continuation bytes and
139        // same-script alphabetic runs suppress BOW.
140        let non_starting = CategoryType::ALPHA | CategoryType::GREEK | CategoryType::CYRILLIC;
141        let mut prev_cat = CategoryType::empty();
142        self.mod_bow.resize(self.modified.len(), false);
143
144        for (chidx, (bidx, ch)) in self.modified.char_indices().enumerate() {
145            self.mod_chars.push(ch);
146            let cat = cats.get_category_types(ch);
147            self.mod_cat.push(cat);
148            self.mod_c2b.push(bidx);
149            self.mod_b2c
150                .extend(std::iter::repeat(last_chidx).take(bidx - last_offset));
151            last_offset = bidx;
152            last_chidx = chidx;
153
154            let can_bow = if cat.intersects(non_starting) {
155                // the previous char is compatible
156                !cat.intersects(prev_cat)
157            } else {
158                true
159            };
160
161            self.mod_bow[bidx] = can_bow;
162            prev_cat = cat;
163        }
164        // trailing indices for the last codepoint
165        self.mod_b2c
166            .extend(std::iter::repeat(last_chidx).take(self.modified.len() - last_offset));
167        // sentinel values for range translations
168        self.mod_c2b.push(self.mod_b2c.len());
169        self.mod_b2c.push(last_chidx + 1);
170
171        self.fill_cat_continuity();
172        self.fill_orig_b2c();
173
174        Ok(())
175    }
176
177    fn fill_cat_continuity(&mut self) {
178        if self.mod_chars.is_empty() {
179            return;
180        }
181        self.mod_cat_continuity.clear();
182        self.mod_cat_continuity.reserve(self.mod_cat.len());
183
184        let mut length = 1;
185        for start in 0..self.mod_cat.len() {
186            // skip intermediate to align with Java implementation
187            if length > 1 {
188                length -= 1;
189                self.mod_cat_continuity.push(length);
190                continue;
191            }
192
193            let mut common = self.mod_cat[start];
194            length = 1;
195            while start + length < self.mod_cat.len() {
196                common &= self.mod_cat[start + length];
197                if common.is_empty() {
198                    break;
199                }
200                length += 1;
201            }
202            self.mod_cat_continuity.push(length);
203        }
204    }
205
206    fn fill_orig_b2c(&mut self) {
207        self.m2o_2.clear();
208        self.m2o_2.resize(self.original.len() + 1, usize::MAX);
209        let mut max = 0;
210        for (ch_idx, (b_idx, _)) in self.original.char_indices().enumerate() {
211            self.m2o_2[b_idx] = ch_idx;
212            max = ch_idx
213        }
214        self.m2o_2[self.original.len()] = max + 1;
215    }
216
217    fn commit(&mut self) -> SudachiResult<()> {
218        if self.replaces.is_empty() {
219            return Ok(());
220        }
221
222        self.mod_chars.clear();
223        self.modified_2.clear();
224        self.m2o_2.clear();
225
226        let sz = edit::resolve_edits(
227            &self.modified,
228            &self.m2o,
229            &mut self.modified_2,
230            &mut self.m2o_2,
231            &mut self.replaces,
232        );
233        if sz > REALLY_MAX_LENGTH {
234            // super improbable, but still
235            return Err(SudachiError::InputTooLong(sz, REALLY_MAX_LENGTH));
236        }
237        std::mem::swap(&mut self.modified, &mut self.modified_2);
238        std::mem::swap(&mut self.m2o, &mut self.m2o_2);
239        Ok(())
240    }
241
242    fn rollback(&mut self) {
243        self.replaces.clear()
244    }
245
246    fn make_editor<'a>(&mut self) -> InputEditor<'a> {
247        // SAFETY: while it is possible to write into borrowed replaces
248        // the buffer object itself will be accessible as RO
249        let replaces: &'a mut Vec<edit::ReplaceOp<'a>> =
250            unsafe { std::mem::transmute(&mut self.replaces) };
251        InputEditor::new(replaces)
252    }
253
254    /// Execute a function which can modify the contents of the current buffer
255    ///
256    /// Edit can borrow &str from the context with the borrow checker working correctly     
257    pub fn with_editor<'a, F>(&mut self, func: F) -> SudachiResult<()>
258    where
259        F: FnOnce(&InputBuffer, InputEditor<'a>) -> SudachiResult<InputEditor<'a>>,
260        F: 'a,
261    {
262        debug_assert_eq!(self.state, BufferState::RW);
263        // InputBufferReplacer should have 'a lifetime parameter for API safety
264        // It is impossible to create it outside of this function
265        // And the API forces user to return it by value
266        let editor: InputEditor<'a> = self.make_editor();
267        match func(self, editor) {
268            Ok(_) => self.commit(),
269            Err(e) => {
270                self.rollback();
271                Err(e)
272            }
273        }
274    }
275
276    /// Recompute chars from modified string (useful if the processing will use chars)
277    pub fn refresh_chars(&mut self) {
278        debug_assert_eq!(self.state, BufferState::RW);
279        if self.mod_chars.is_empty() {
280            self.mod_chars.extend(self.modified.chars());
281        }
282    }
283}
284
285// RO Accessors
286impl InputBuffer {
287    /// Borrow original data
288    pub fn original(&self) -> &str {
289        debug_assert_ne!(self.state, BufferState::Clean);
290        &self.original
291    }
292
293    /// Borrow modified data
294    pub fn current(&self) -> &str {
295        debug_assert_ne!(self.state, BufferState::Clean);
296        &self.modified
297    }
298
299    /// Borrow array of current characters
300    pub fn current_chars(&self) -> &[char] {
301        debug_assert_ne!(self.state, BufferState::Clean);
302        debug_assert_eq!(self.modified.is_empty(), self.mod_chars.is_empty());
303        &self.mod_chars
304    }
305
306    /// Returns byte offsets of current chars
307    pub fn curr_byte_offsets(&self) -> &[usize] {
308        debug_assert_eq!(self.state, BufferState::RO);
309        let len = self.mod_c2b.len();
310        &self.mod_c2b[0..len - 1]
311    }
312
313    /// Get index of the current byte in original sentence
314    /// Bytes not on character boundaries are not supported
315    pub fn get_original_index(&self, index: usize) -> usize {
316        debug_assert!(self.modified.is_char_boundary(index));
317        self.m2o[index]
318    }
319
320    /// Mod Char Idx -> Orig Byte Idx
321    pub fn to_orig_byte_idx(&self, index: usize) -> usize {
322        debug_assert_ne!(self.state, BufferState::Clean);
323        let byte_idx = self.mod_c2b[index];
324        self.m2o[byte_idx]
325    }
326
327    /// Mod Char Idx -> Orig Char Idx
328    pub fn to_orig_char_idx(&self, index: usize) -> usize {
329        let b_idx = self.to_orig_byte_idx(index);
330        let res = self.m2o_2[b_idx];
331        debug_assert_ne!(res, usize::MAX);
332        res
333    }
334
335    /// Mod Char Idx -> Mod Byte Idx
336    pub fn to_curr_byte_idx(&self, index: usize) -> usize {
337        debug_assert_eq!(self.state, BufferState::RO);
338        self.mod_c2b[index]
339    }
340
341    /// Input: Mod Char Idx
342    pub fn curr_slice_c(&self, data: Range<usize>) -> &str {
343        debug_assert_eq!(self.state, BufferState::RO);
344        let start = self.mod_c2b[data.start];
345        let end = self.mod_c2b[data.end];
346        &self.modified[start..end]
347    }
348
349    /// Input: Mod Char Idx
350    pub fn orig_slice_c(&self, data: Range<usize>) -> &str {
351        debug_assert_eq!(self.state, BufferState::RO);
352        let start = self.to_orig_byte_idx(data.start);
353        let end = self.to_orig_byte_idx(data.end);
354        &self.original[start..end]
355    }
356
357    pub fn ch_idx(&self, idx: usize) -> usize {
358        debug_assert_eq!(self.state, BufferState::RO);
359        self.mod_b2c[idx]
360    }
361
362    /// Swaps original data with the passed location
363    pub fn swap_original(&mut self, target: &mut String) {
364        std::mem::swap(&mut self.original, target);
365        self.state = BufferState::Clean;
366    }
367
368    /// Return original data as owned, consuming itself    
369    pub fn into_original(self) -> String {
370        self.original
371    }
372
373    /// Whether the byte can start a new word.
374    /// Supports bytes not on character boundaries.
375    #[inline]
376    pub fn can_bow(&self, offset: usize) -> bool {
377        debug_assert_eq!(self.state, BufferState::RO);
378        self.mod_bow[offset]
379    }
380
381    /// Whether the character can start a new OOV word.
382    #[inline]
383    pub fn can_oov_bow(&self, offset: usize) -> bool {
384        debug_assert_eq!(self.state, BufferState::RO);
385        let cat = self.mod_cat[offset];
386        !cat.contains(CategoryType::NOOOVBOW)
387            && (offset == 0 || !self.mod_cat[offset - 1].contains(CategoryType::NOOOVEOW))
388    }
389
390    /// Returns char length to the next can_bow point
391    ///
392    /// Used by SimpleOOV plugin
393    pub fn get_word_candidate_length(&self, char_idx: usize) -> usize {
394        debug_assert_eq!(self.state, BufferState::RO);
395        let char_len = self.mod_chars.len();
396
397        for i in (char_idx + 1)..char_len {
398            let byte_idx = self.mod_c2b[i];
399            if self.can_bow(byte_idx) {
400                return i - char_idx;
401            }
402        }
403        char_len - char_idx
404    }
405}
406
407impl InputTextIndex for InputBuffer {
408    #[inline]
409    fn cat_of_range(&self, range: Range<usize>) -> CategoryType {
410        debug_assert_eq!(self.state, BufferState::RO);
411        if range.is_empty() {
412            return CategoryType::empty();
413        }
414
415        self.mod_cat[range]
416            .iter()
417            .fold(CategoryType::all(), |a, b| a & *b)
418    }
419
420    #[inline]
421    fn cat_at_char(&self, offset: usize) -> CategoryType {
422        debug_assert_eq!(self.state, BufferState::RO);
423        self.mod_cat[offset]
424    }
425
426    #[inline]
427    fn cat_continuous_len(&self, offset: usize) -> usize {
428        debug_assert_eq!(self.state, BufferState::RO);
429        self.mod_cat_continuity[offset]
430    }
431
432    fn char_distance(&self, cpt: usize, offset: usize) -> usize {
433        debug_assert_eq!(self.state, BufferState::RO);
434        let end = (cpt + offset).min(self.mod_chars.len());
435        end - cpt
436    }
437
438    #[inline]
439    fn orig_slice(&self, range: Range<usize>) -> &str {
440        debug_assert_ne!(self.state, BufferState::Clean);
441        debug_assert!(
442            self.modified.is_char_boundary(range.start),
443            "start is off char boundary"
444        );
445        debug_assert!(
446            self.modified.is_char_boundary(range.end),
447            "end is off char boundary"
448        );
449        &self.original[self.to_orig(range)]
450    }
451
452    #[inline]
453    fn curr_slice(&self, range: Range<usize>) -> &str {
454        debug_assert_ne!(self.state, BufferState::Clean);
455        &self.modified[range]
456    }
457
458    #[inline]
459    fn to_orig(&self, range: Range<usize>) -> Range<usize> {
460        debug_assert_ne!(self.state, BufferState::Clean);
461        self.m2o[range.start]..self.m2o[range.end]
462    }
463}
sudachi/input_text/buffer.rs

sudachi/input_text/
buffer.rs
