mdictlib 0.2.1

Library-first Rust parser for MDict .mdx and .mdd dictionaries
Documentation
use std::cmp::Ordering;
use std::mem::size_of;
use std::ops::Range;
use std::sync::Arc;

use super::{CachedFailure, CachedValue, MdictFile};
use crate::error::{Error, Result};
use crate::limits::{
    MemoryReservation, checked_usize, ensure_usize_limit, try_clone_string, try_reserve_vec,
};
use crate::types::KeyOrdinal;

#[derive(Debug)]
struct LocatorRow {
    raw: Box<str>,
    normalized: Box<str>,
}

#[derive(Debug)]
pub(crate) struct KeyLocator {
    rows: Box<[LocatorRow]>,
    by_raw: Box<[u32]>,
    by_normalized: Box<[u32]>,
    _memory: MemoryReservation,
}

#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub(crate) enum LocatorBasis {
    RawExact,
    HeaderNormalized,
}

#[derive(Debug, Clone)]
pub(crate) struct LocatedKeys {
    locator: Arc<KeyLocator>,
    basis: LocatorBasis,
    range: Range<usize>,
}

impl LocatedKeys {
    pub(crate) const fn basis(&self) -> LocatorBasis {
        self.basis
    }

    pub(crate) fn len(&self) -> usize {
        self.range.len()
    }

    pub(crate) fn is_empty(&self) -> bool {
        self.range.is_empty()
    }

    pub(crate) fn ordinal_at(&self, index: usize) -> Option<KeyOrdinal> {
        let position = self.range.start.checked_add(index)?;
        if position >= self.range.end {
            return None;
        }
        let ordinal = match self.basis {
            LocatorBasis::RawExact => *self.locator.by_raw.get(position)?,
            LocatorBasis::HeaderNormalized => *self.locator.by_normalized.get(position)?,
        };
        Some(KeyOrdinal::new(u64::from(ordinal)))
    }
}

impl MdictFile {
    pub(crate) fn locate_keys(&self, query: &str) -> Result<Option<LocatedKeys>> {
        let locator = self.key_locator()?;
        if let Some(range) = locator.equal_range(LocatorBasis::RawExact, query) {
            return Ok(Some(LocatedKeys {
                locator,
                basis: LocatorBasis::RawExact,
                range,
            }));
        }

        let normalized_len = self.normalizer.normalized_len(query)?;
        ensure_usize_limit(
            "normalized_query_bytes",
            normalized_len,
            self.limits.locator_bytes,
        )?;
        let _query_memory = self
            .memory
            .reserve(normalized_len, "normalized lookup query")?;
        let normalized = self.normalizer.normalize(query)?;
        Ok(locator
            .equal_range(LocatorBasis::HeaderNormalized, &normalized)
            .map(|range| LocatedKeys {
                locator,
                basis: LocatorBasis::HeaderNormalized,
                range,
            }))
    }

    fn key_locator(&self) -> Result<Arc<KeyLocator>> {
        if let Some(locator) = self.locator.get() {
            return cached_locator(locator);
        }

        let _build = self
            .locator_build
            .lock()
            .map_err(|_| Error::InvalidFormat("key locator build mutex poisoned"))?;
        if let Some(locator) = self.locator.get() {
            return cached_locator(locator);
        }

        match self.build_key_locator() {
            Ok(locator) => {
                let locator = Arc::new(locator);
                let _ = self.locator.set(CachedValue::Ready(Arc::clone(&locator)));
                Ok(locator)
            }
            Err(error) => {
                if let Some(cached) = CachedFailure::capture(&error, &self.memory) {
                    let _ = self.locator.set(CachedValue::Failed(cached));
                }
                Err(error)
            }
        }
    }

    fn build_key_locator(&self) -> Result<KeyLocator> {
        let maximum_entries = self.limits.locator_entries.min(u64::from(u32::MAX));
        if self.len() > maximum_entries {
            return Err(Error::LimitExceeded {
                limit: "locator_entries",
                value: self.len(),
                max: maximum_entries,
            });
        }
        let entry_count = checked_usize(self.len(), "locator entry count")?;

        let fixed_bytes = entry_count
            .checked_mul(size_of::<LocatorRow>() + 2 * size_of::<u32>())
            .ok_or(Error::InvalidFormat("key locator size overflow"))?;
        enforce_locator_size(fixed_bytes, self.limits.locator_bytes)?;
        let mut retained_memory = self.memory.reserve(fixed_bytes, "key locator")?;

        let mut rows = Vec::new();
        try_reserve_vec(&mut rows, entry_count, "key locator rows")?;
        let mut estimated_bytes = fixed_bytes;
        let mut previous_record_start = None;

        for block_index in 0..self.key_block_count() {
            let block = self
                .layout
                .key_blocks
                .get(block_index)
                .ok_or(Error::InvalidFormat("key block index out of range"))?;
            let entries = self.decode_key_block(block_index)?;
            for entry in entries.iter() {
                if entry.record_start > self.layout.total_decoded_record_len {
                    return Err(Error::InvalidData(format!(
                        "record start {} exceeds total record bytes {}",
                        entry.record_start, self.layout.total_decoded_record_len
                    )));
                }
                if let Some(previous) = previous_record_start
                    && previous > entry.record_start
                {
                    return Err(Error::InvalidData(format!(
                        "record starts decrease from {previous} to {}",
                        entry.record_start
                    )));
                }
                previous_record_start = Some(entry.record_start);
                let normalized_len = self.normalizer.normalized_len(&entry.key)?;
                estimated_bytes = estimated_bytes
                    .checked_add(entry.key.len())
                    .and_then(|value| value.checked_add(normalized_len))
                    .ok_or(Error::InvalidFormat("key locator size overflow"))?;
                enforce_locator_size(estimated_bytes, self.limits.locator_bytes)?;
                retained_memory.grow(
                    entry
                        .key
                        .len()
                        .checked_add(normalized_len)
                        .ok_or(Error::InvalidFormat("key locator size overflow"))?,
                )?;
                let normalized = self.normalizer.normalize(&entry.key)?;
                rows.push(LocatorRow {
                    raw: try_clone_string(&entry.key, "key locator raw key")?.into_boxed_str(),
                    normalized: normalized.into_boxed_str(),
                });
            }

            let expected_end = usize::try_from(
                block
                    .entry_start_index
                    .checked_add(block.entry_count)
                    .ok_or(Error::InvalidFormat("keyword entry count overflow"))?,
            )
            .map_err(|_| Error::InvalidFormat("keyword entry count exceeds usize"))?;
            if rows.len() != expected_end {
                return Err(Error::InvalidData(format!(
                    "locator row count mismatch after block {block_index}: expected {expected_end}, decoded {}",
                    rows.len()
                )));
            }
            drop(entries);
        }

        if rows.len() != entry_count {
            return Err(Error::InvalidData(format!(
                "locator row count mismatch: expected {entry_count}, decoded {}",
                rows.len()
            )));
        }

        let mut by_raw = Vec::new();
        let mut by_normalized = Vec::new();
        try_reserve_vec(&mut by_raw, entry_count, "raw locator index")?;
        try_reserve_vec(&mut by_normalized, entry_count, "normalized locator index")?;
        for index in 0..entry_count {
            let index = u32::try_from(index)
                .map_err(|_| Error::InvalidFormat("locator row index exceeds u32"))?;
            by_raw.push(index);
            by_normalized.push(index);
        }

        by_raw.sort_unstable_by(|left, right| compare_rows(&rows, *left, *right, false));
        by_normalized.sort_unstable_by(|left, right| compare_rows(&rows, *left, *right, true));

        Ok(KeyLocator {
            rows: rows.into_boxed_slice(),
            by_raw: by_raw.into_boxed_slice(),
            by_normalized: by_normalized.into_boxed_slice(),
            _memory: retained_memory,
        })
    }
}

fn cached_locator(locator: &CachedValue<KeyLocator>) -> Result<Arc<KeyLocator>> {
    match locator {
        CachedValue::Ready(locator) => Ok(Arc::clone(locator)),
        CachedValue::Failed(error) => Err(error.replay()),
    }
}

impl KeyLocator {
    pub(super) const fn memory_bytes(&self) -> usize {
        self._memory.bytes()
    }

    fn equal_range(&self, basis: LocatorBasis, query: &str) -> Option<Range<usize>> {
        let index = match basis {
            LocatorBasis::RawExact => &self.by_raw,
            LocatorBasis::HeaderNormalized => &self.by_normalized,
        };
        let key = |ordinal: &u32| {
            let row_index = usize::try_from(*ordinal)
                .expect("locator ordinal was created from an in-range usize");
            let row = &self.rows[row_index];
            match basis {
                LocatorBasis::RawExact => row.raw.as_ref(),
                LocatorBasis::HeaderNormalized => row.normalized.as_ref(),
            }
        };
        let start = index.partition_point(|ordinal| key(ordinal) < query);
        let end = index.partition_point(|ordinal| key(ordinal) <= query);
        (start < end).then_some(start..end)
    }
}

fn compare_rows(rows: &[LocatorRow], left: u32, right: u32, normalized: bool) -> Ordering {
    let left = usize::try_from(left).expect("locator ordinal originated as usize");
    let right = usize::try_from(right).expect("locator ordinal originated as usize");
    let left_row = &rows[left];
    let right_row = &rows[right];
    let key_order = if normalized {
        left_row.normalized.cmp(&right_row.normalized)
    } else {
        left_row.raw.cmp(&right_row.raw)
    };
    key_order.then_with(|| left.cmp(&right))
}

fn enforce_locator_size(bytes: usize, maximum: usize) -> Result<()> {
    if bytes > maximum {
        let value = u64::try_from(bytes).unwrap_or(u64::MAX);
        let max = u64::try_from(maximum).unwrap_or(u64::MAX);
        return Err(Error::LimitExceeded {
            limit: "locator_bytes",
            value,
            max,
        });
    }
    Ok(())
}