path: root/third_party/rust/mapped_hyph/src/builder.rs

// Copyright 2019-2020 Mozilla Foundation. See the COPYRIGHT
// file at the top-level directory of this distribution.
//
// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
// https://www.apache.org/licenses/LICENSE-2.0> or the MIT license
// <LICENSE-MIT or https://opensource.org/licenses/MIT>, at your
// option. This file may not be copied, modified, or distributed
// except according to those terms.

/// Functions to compile human-readable patterns into a mapped_hyph
/// flattened representation of the hyphenation state machine.

use std::io::{Read,BufRead,BufReader,Write,Error,ErrorKind};
use std::collections::HashMap;
use std::convert::TryInto;
use std::hash::{Hash,Hasher};

// Wrap a HashMap so that we can implement the Hash trait.
#[derive(PartialEq, Eq, Clone)]
struct TransitionMap (HashMap<u8,i32>);

impl TransitionMap {
    fn new() -> TransitionMap {
        TransitionMap(HashMap::<u8,i32>::new())
    }
}

impl Hash for TransitionMap {
    fn hash<H: Hasher>(&self, state: &mut H) {
        // We only look at the values here; that's likely to be enough
        // for a reasonable hash.
        let mut transitions: Vec<&i32> = self.0.values().collect();
        transitions.sort();
        for t in transitions {
            t.hash(state);
        }
    }
}

#[derive(PartialEq, Eq, Hash, Clone)]
struct State {
    match_string: Option<Vec<u8>>,
    #[allow(dead_code)]
    repl_string: Option<Vec<u8>>,
    #[allow(dead_code)]
    repl_index: i32,
    #[allow(dead_code)]
    repl_cut: i32,
    fallback_state: i32,
    transitions: TransitionMap,
}

impl State {
    fn new() -> State {
        State {
            match_string: None,
            repl_string: None,
            repl_index: -1,
            repl_cut: -1,
            fallback_state: -1,
            transitions: TransitionMap::new(),
        }
    }
}

/// Structures returned by the read_dic_file() function;
/// array of these can then be passed to write_hyf_file()
/// to create the flattened output.
struct LevelBuilder {
    states: Vec<State>,
    str_to_state: HashMap<Vec<u8>,i32>,
    encoding: Option<String>,
    nohyphen: Option<String>,
    lh_min: u8,
    rh_min: u8,
    clh_min: u8,
    crh_min: u8,
}

impl LevelBuilder {
    fn new() -> LevelBuilder {
        let mut result = LevelBuilder {
            states: Vec::<State>::new(),
            str_to_state: HashMap::<Vec<u8>,i32>::new(),
            encoding: None,
            nohyphen: None,
            lh_min: 0,
            rh_min: 0,
            clh_min: 0,
            crh_min: 0,
        };
        // Initialize the builder with an empty start state.
        result.str_to_state.insert(vec![], 0);
        result.states.push(State::new());
        result
    }

    fn find_state_number_for(&mut self, text: &[u8]) -> i32 {
        let count = self.states.len() as i32;
        let index = *self.str_to_state.entry(text.to_vec()).or_insert(count);
        if index == count {
            self.states.push(State::new());
        }
        index
    }

    fn add_pattern(&mut self, pattern: &str) {
        let mut bytes = pattern.as_bytes();
        let mut text = Vec::<u8>::with_capacity(bytes.len());
        let mut digits = Vec::<u8>::with_capacity(bytes.len() + 1);
        let mut repl_str = None;
        let mut repl_index = 0;
        let mut repl_cut = 0;

        // Check for replacement rule (non-standard hyphenation spelling change).
        if let Some(slash) = bytes.iter().position(|x| *x == b'/') {
            let parts = bytes.split_at(slash);
            bytes = parts.0;
            let mut it = parts.1[1 ..].split(|x| *x == b',');
            if let Some(repl) = it.next() {
                repl_str = Some(repl.to_vec());
            }
            if let Some(num) = it.next() {
                repl_index = std::str::from_utf8(num).unwrap().parse::<i32>().unwrap() - 1;
            }
            if let Some(num) = it.next() {
                repl_cut = std::str::from_utf8(num).unwrap().parse::<i32>().unwrap();
            }
        }

        // Separate the input pattern into parallel arrays of text (bytes) and digits.
        let mut got_digit = false;
        for byte in bytes {
            if *byte <= b'9' && *byte >= b'0' {
                if got_digit {
                    warn!("invalid pattern \"{}\": consecutive digits", pattern);
                    return;
                }
                digits.push(*byte);
                got_digit = true;
            } else {
                text.push(*byte);
                if got_digit {
                    got_digit = false;
                } else {
                    digits.push(b'0');
                }
            }
        }
        if !got_digit {
            digits.push(b'0');
        }

        if repl_str.is_none() {
            // Optimize away leading zeroes from the digits array.
            while !digits.is_empty() && digits[0] == b'0' {
                digits.remove(0);
            }
        } else {
            // Convert repl_index and repl_cut from Unicode char to byte indexing.
            let start = if text[0] == b'.' { 1 } else { 0 };
            if start == 1 {
                if digits[0] != b'0' {
                    warn!("invalid pattern \"{}\": unexpected digit before start of word", pattern);
                    return;
                }
                digits.remove(0);
            }
            let word = std::str::from_utf8(&text[start..]).unwrap();
            let mut chars: Vec<_> = word.char_indices().collect();
            chars.push((word.len(), '.'));
            repl_cut = chars[(repl_index + repl_cut) as usize].0 as i32 - chars[repl_index as usize].0 as i32;
            repl_index = chars[repl_index as usize].0 as i32;
        }

        // Create the new state, or add pattern into an existing state
        // (which should not already have a match_string).
        let mut state_num = self.find_state_number_for(&text);
        let mut state = &mut self.states[state_num as usize];
        if state.match_string.is_some() {
            warn!("duplicate pattern \"{}\" discarded", pattern);
            return;
        }
        if !digits.is_empty() {
            state.match_string = Some(digits);
        }
        if repl_str.is_some() {
            state.repl_string = repl_str;
            state.repl_index = repl_index;
            state.repl_cut = repl_cut;
        }

        // Set up prefix transitions, inserting additional states as needed.
        while !text.is_empty() {
            let last_state = state_num;
            let ch = *text.last().unwrap();
            text.truncate(text.len() - 1);
            state_num = self.find_state_number_for(&text);
            if let Some(exists) = self.states[state_num as usize].transitions.0.insert(ch, last_state) {
                assert_eq!(exists, last_state, "overwriting existing transition at pattern \"{}\"", pattern);
                break;
            }
        }
    }

    fn merge_duplicate_states(&mut self) {
        // We loop here because when we eliminate a duplicate, and update the transitons
        // that referenced it, we may thereby create new duplicates that another pass
        // will find and compress further.
        loop {
            let orig_len = self.states.len();
            // Used to map State records to the (first) index at which they occur.
            let mut state_to_index = HashMap::<&State,i32>::new();
            // Mapping of old->new state indexes, and whether each old state is
            // a duplicate that should be dropped.
            let mut mappings = Vec::<(i32,bool)>::with_capacity(orig_len);
            let mut next_new_index: i32 = 0;
            for index in 0 .. self.states.len() {
                // Find existing index for this state, or allocate the next new index to it.
                let new_index = *state_to_index.entry(&self.states[index]).or_insert(next_new_index);
                // Record the mapping, and whether the state was a duplicate.
                mappings.push((new_index, new_index != next_new_index));
                // If we used next_new_index for this state, increment it.
                if new_index == next_new_index {
                    next_new_index += 1;
                }
            }
            // If we didn't find any duplicates, next_new_index will have kept pace with
            // index, so we know we're finished.
            if next_new_index as usize == self.states.len() {
                break;
            }
            // Iterate over all the states, either deleting them or updating indexes
            // according to the mapping we created; then repeat the search.
            for index in (0 .. self.states.len()).rev() {
                if mappings[index].1 {
                    self.states.remove(index);
                } else {
                    let state = &mut self.states[index];
                    if state.fallback_state != -1 {
                        state.fallback_state = mappings[state.fallback_state as usize].0;
                    }
                    for t in state.transitions.0.iter_mut() {
                        *t.1 = mappings[*t.1 as usize].0;
                    }
                }
            }
        }
    }

    fn flatten(&self) -> Vec<u8> {
        // Calculate total space needed for state data, and build the state_to_offset table.
        let mut state_data_size = 0;
        let mut state_to_offset = Vec::<usize>::with_capacity(self.states.len());
        for state in &self.states {
            state_to_offset.push(state_data_size);
            state_data_size += if state.repl_string.is_some() { 12 } else { 8 };
            state_data_size += state.transitions.0.len() * 4;
        }

        // Helper to map a state index to its offset in the final data block.
        let get_state_offset_for = |state_index: i32| -> u32 {
            if state_index < 0 {
                return super::INVALID_STATE_OFFSET;
            }
            state_to_offset[state_index as usize] as u32
        };

        // Helper to map a byte string to its offset in the final data block, and
        // store the bytes into string_data unless using an already-existing string.
        let mut string_to_offset = HashMap::<Vec<u8>,usize>::new();
        let mut string_data = Vec::<u8>::new();
        let mut get_string_offset_for = |bytes: &Option<Vec<u8>>| -> u16 {
            if bytes.is_none() {
                return super::INVALID_STRING_OFFSET;
            }
            assert!(bytes.as_ref().unwrap().len() < 256);
            let new_offset = string_data.len();
            let offset = *string_to_offset.entry(bytes.as_ref().unwrap().clone()).or_insert(new_offset);
            if offset == new_offset {
                string_data.push(bytes.as_ref().unwrap().len() as u8);
                string_data.extend_from_slice(bytes.as_ref().unwrap().as_ref());
            }
            offset.try_into().unwrap()
        };

        // Handle nohyphen string list if present, converting comma separators to NULs
        // and trimming any surplus whitespace.
        let mut nohyphen_string_offset: u16 = super::INVALID_STRING_OFFSET;
        let mut nohyphen_count: u16 = 0;
        if self.nohyphen.is_some() {
            let nohyphen_strings: Vec<_> = self.nohyphen.as_ref().unwrap().split(',').map(|x| x.trim()).collect();
            nohyphen_count = nohyphen_strings.len().try_into().unwrap();
            nohyphen_string_offset = get_string_offset_for(&Some(nohyphen_strings.join("\0").as_bytes().to_vec()));
        }

        let mut state_data = Vec::<u8>::with_capacity(state_data_size);
        for state in &self.states {
            state_data.extend(&get_state_offset_for(state.fallback_state).to_le_bytes());
            state_data.extend(&get_string_offset_for(&state.match_string).to_le_bytes());
            state_data.push(state.transitions.0.len() as u8);
            // Determine whether to use an extended state record, and if so add the
            // replacement string and index fields.
            if state.repl_string.is_none() {
                state_data.push(0);
            } else {
                state_data.push(1);
                state_data.extend(&get_string_offset_for(&state.repl_string).to_le_bytes());
                state_data.push(state.repl_index as u8);
                state_data.push(state.repl_cut as u8);
            }
            // Collect transitions into an array so we can sort them.
            let mut transitions = vec![];
            for (key, value) in state.transitions.0.iter() {
                transitions.push((*key, get_state_offset_for(*value)))
            }
            transitions.sort();
            for t in transitions {
                // New state offset is stored as a 24-bit value, so we do this manually.
                state_data.push((t.1 & 0xff) as u8);
                state_data.push(((t.1 >> 8) & 0xff) as u8);
                state_data.push(((t.1 >> 16) & 0xff) as u8);
                state_data.push(t.0);
            }
        }
        assert_eq!(state_data.len(), state_data_size);

        // Pad string data to a 4-byte boundary
        while string_data.len() & 3 != 0 {
            string_data.push(0);
        }

        let total_size = super::LEVEL_HEADER_SIZE as usize + state_data_size + string_data.len();
        let mut result = Vec::<u8>::with_capacity(total_size);

        let state_data_base: u32 = super::LEVEL_HEADER_SIZE as u32;
        let string_data_base: u32 = state_data_base + state_data_size as u32;

        result.extend(&state_data_base.to_le_bytes());
        result.extend(&string_data_base.to_le_bytes());
        result.extend(&nohyphen_string_offset.to_le_bytes());
        result.extend(&nohyphen_count.to_le_bytes());
        result.push(self.lh_min);
        result.push(self.rh_min);
        result.push(self.clh_min);
        result.push(self.crh_min);

        result.extend(state_data.iter());
        result.extend(string_data.iter());

        assert_eq!(result.len(), total_size);

        result
    }
}

/// Read a libhyphen-style pattern file and create the corresponding state
/// machine transitions, etc.
/// The returned Vec can be passed to write_hyf_file() to generate a flattened
/// representation of the state machine in mapped_hyph's binary format.
fn read_dic_file<T: Read>(dic_file: T, compress: bool) -> Result<Vec<LevelBuilder>, &'static str> {
    let reader = BufReader::new(dic_file);

    let mut builders = Vec::<LevelBuilder>::new();
    builders.push(LevelBuilder::new());
    let mut builder = &mut builders[0];

    for (index, line) in reader.lines().enumerate() {
        let mut trimmed = line.unwrap().trim().to_string();
        // Strip comments.
        if let Some(i) = trimmed.find('%') {
            trimmed = trimmed[..i].trim().to_string();
        }
        // Ignore empty lines.
        if trimmed.is_empty() {
            continue;
        }
        // Uppercase indicates keyword rather than pattern.
        if trimmed.as_bytes()[0] >= b'A' && trimmed.as_bytes()[0] <= b'Z' {
            // First line is encoding; we only support UTF-8.
            if builder.encoding.is_none() {
                if trimmed != "UTF-8" {
                    return Err("Only UTF-8 patterns are accepted!");
                };
                builder.encoding = Some(trimmed);
                continue;
            }
            // Check for valid keyword-value pairs.
            if trimmed.contains(' ') {
                let parts: Vec<&str> = trimmed.split(' ').collect();
                if parts.len() != 2 {
                    warn!("unrecognized keyword/values: {}", trimmed);
                    continue;
                }
                let keyword = parts[0];
                let value = parts[1];
                match keyword {
                    "LEFTHYPHENMIN" => builder.lh_min = value.parse::<u8>().unwrap(),
                    "RIGHTHYPHENMIN" => builder.rh_min = value.parse::<u8>().unwrap(),
                    "COMPOUNDLEFTHYPHENMIN" => builder.clh_min = value.parse::<u8>().unwrap(),
                    "COMPOUNDRIGHTHYPHENMIN" => builder.crh_min = value.parse::<u8>().unwrap(),
                    "NOHYPHEN" => builder.nohyphen = Some(trimmed),
                    _ => warn!("unknown keyword: {}", trimmed),
                }
                continue;
            }
            // Start a new hyphenation level?
            if trimmed == "NEXTLEVEL" {
                builders.push(LevelBuilder::new());
                builder = builders.last_mut().unwrap();
                continue;
            }
            warn!("unknown keyword: {}", trimmed);
            continue;
        }
        // Patterns should always be provided in lowercase; complain if not, and discard
        // the bad pattern.
        if trimmed != trimmed.to_lowercase() {
            warn!("pattern \"{}\" not lowercased at line {}", trimmed, index);
            continue;
        }
        builder.add_pattern(&trimmed);
    }

    // Create default first (compound-word) level if only one level was provided.
    // (Maybe this should be optional? Currently just copying libhyphen behavior.)
    if builders.len() == 1 {
        let (lh_min, rh_min, clh_min, crh_min) =
            (builders[0].lh_min, builders[0].rh_min, builders[0].clh_min, builders[0].crh_min);
        builders.insert(0, LevelBuilder::new());
        builder = builders.first_mut().unwrap();
        builder.add_pattern("1-1");
        builder.add_pattern("1'1");
        builder.add_pattern("1\u{2013}1"); // en-dash
        builder.add_pattern("1\u{2019}1"); // curly apostrophe
        builder.nohyphen = Some("',\u{2013},\u{2019},-".to_string());
        builder.lh_min = lh_min;
        builder.rh_min = rh_min;
        builder.clh_min = if clh_min > 0 { clh_min } else if lh_min > 0 { lh_min } else { 3 };
        builder.crh_min = if crh_min > 0 { crh_min } else if rh_min > 0 { rh_min } else { 3 };
    }

    // Put in fallback states in each builder.
    for builder in &mut builders {
        for (key, state_index) in builder.str_to_state.iter() {
            if key.is_empty() {
                continue;
            }
            let mut fallback_key = key.clone();
            while !fallback_key.is_empty() {
                fallback_key.remove(0);
                if builder.str_to_state.contains_key(&fallback_key) {
                    break;
                }
            }
            builder.states[*state_index as usize].fallback_state = builder.str_to_state[&fallback_key];
        }
    }

    if compress {
        // Merge duplicate states to reduce size.
        for builder in &mut builders {
            builder.merge_duplicate_states();
        }
    }

    Ok(builders)
}

/// Write out the state machines representing a set of hyphenation rules
/// to the given output stream.
fn write_hyf_file<T: Write>(hyf_file: &mut T, levels: Vec<LevelBuilder>) -> std::io::Result<()> {
    if levels.is_empty() {
        return Err(Error::from(ErrorKind::InvalidData));
    }
    let mut flattened = vec![];
    for level in levels {
        flattened.push(level.flatten());
    }
    // Write file header: magic number, count of levels.
    hyf_file.write_all(&[b'H', b'y', b'f', b'0'])?;
    let level_count: u32 = flattened.len() as u32;
    hyf_file.write_all(&level_count.to_le_bytes())?;
    // Write array of offsets to each level. First level will begin immediately
    // after the array of offsets.
    let mut offset: u32 = super::FILE_HEADER_SIZE as u32 + 4 * level_count;
    for flat in &flattened {
        hyf_file.write_all(&offset.to_le_bytes())?;
        offset += flat.len() as u32;
    }
    // Write the flattened data for each level.
    for flat in &flattened {
        hyf_file.write_all(&flat)?;
    }
    Ok(())
}

/// The public API to the compilation process: reads `dic_file` and writes compiled tables
/// to `hyf_file`. The `compress` param determines whether extra processing to reduce the
/// size of the output is performed.
pub fn compile<T1: Read, T2: Write>(dic_file: T1, hyf_file: &mut T2, compress: bool) -> std::io::Result<()> {
    match read_dic_file(dic_file, compress) {
        Ok(dic) => write_hyf_file(hyf_file, dic),
        Err(e) => {
            warn!("parse error: {}", e);
            return Err(Error::from(ErrorKind::InvalidData))
        }
    }
}