layout/flow/inline/

text_transform.rs

/* This Source Code Form is subject to the terms of the Mozilla Public
 * License, v. 2.0. If a copy of the MPL was not distributed with this
 * file, You can obtain one at https://mozilla.org/MPL/2.0/. */

//! # Logic for text transform in inline formatting contexts
//!
//! Inline formatting contexts do a variety of text transformations on their text content
//! including white space collapsing, application of the `text-transform` CSS property,
//! and application of the `-webkit-text-security` property. This module contains code to
//! handle this as well as code to map from offsets in the original DOM node to the final
//! IFC text and vice-versa.

use arrayvec::ArrayVec;
use icu_casemap::CaseMapper;
use icu_casemap::options::TitlecaseOptions;
use icu_locale_core::LanguageIdentifier;
use icu_properties::props::{EnumeratedProperty, GeneralCategory, GeneralCategoryGroup};
use icu_segmenter::WordSegmenter;
use icu_segmenter::options::WordBreakInvariantOptions;
use malloc_size_of_derive::MallocSizeOf;
#[cfg(test)]
use servo_base::text::AssumeUnder4GB;
use servo_base::text::Utf32CodeUnits;
use style::computed_values::_webkit_text_security::T as WebKitTextSecurity;
use style::computed_values::white_space_collapse::T as WhiteSpaceCollapse;
use style::properties::ComputedValues;
use style::values::specified::text::{TextTransform, TextTransformCase};
use writeable::Writeable;

use crate::flow::inline::construct::InlineFormattingContextBuilder;

/// <https://github.com/rust-lang/rust/blob/1.97.1/library/core/src/char/mod.rs#L523>
///
/// This is the maximum amount of characters that can be produced from case mapping,
/// and by consequence the maximum amount of characters that can be produced during
/// inline formatting context text transformation.
const MAX_CASE_MAPPING_LENGTH: usize = 3;

/// A single iteration in a pipeline of character iterators, that handle things like
/// whitespace collapse and `text-transform` processing for text in an
/// [`InlineFormattingContext`]. Each iteration can consume multiple characters and
/// produce zero or more characters (up to 3). Consumption of characters greater than the
/// characters produced by [`CharacterTransformIteration`] indicate that those characters
/// have been collapsed.
#[derive(Clone)]
pub struct CharacterTransformIteration {
    /// The number of characters consumed during this iteration of character transformation.
    consumed: Utf32CodeUnits,
    /// The characters that were produced during this iteration.
    characters: ArrayVec<char, MAX_CASE_MAPPING_LENGTH>,
}

impl CharacterTransformIteration {
    fn case_mapped(iterator: impl ExactSizeIterator<Item = char>) -> Self {
        debug_assert!(iterator.len() <= MAX_CASE_MAPPING_LENGTH);
        Self {
            consumed: Utf32CodeUnits(1),
            characters: iterator.collect(),
        }
    }

    fn one_to_one(character: char) -> Self {
        Self {
            consumed: Utf32CodeUnits(1),
            characters: std::iter::once(character).collect(),
        }
    }

    fn collapse(amount_collapsed: Utf32CodeUnits, character: Option<char>) -> Self {
        Self {
            consumed: amount_collapsed,
            characters: character.into_iter().collect(),
        }
    }

    fn is_one_to_one(&self) -> bool {
        self.characters.len() == 1 && self.consumed.0 == 1
    }

    pub fn characters(&self) -> &[char] {
        &self.characters
    }
}

pub struct WhitespaceCollapse<InputIterator> {
    input_iterator: InputIterator,
    white_space_collapse: WhiteSpaceCollapse,

    /// Whether or not we are in the process of collapse leading white space. This is true
    /// when the last character handled in our owning [`super::InlineFormattingContext`]
    /// was collapsible white space and we have not seen any non-whitespace characters
    /// during processing of this iterator's input.
    trimming_leading_white_space: bool,

    /// Whether or not the last character produced was newline. There is special behavior
    /// we do after each newline.
    following_newline: bool,

    /// When whitespace collapses before a non-whitespace character, the iterator returns
    /// the collapsed whitespace and in the next iteration the non-whitespace character
    /// must be returned. This value caches it until the next iteration.
    character_pending_to_return: Option<char>,
}

impl<InputIterator: Iterator<Item = char>> WhitespaceCollapse<InputIterator> {
    pub fn new(
        input_iterator: InputIterator,
        white_space_collapse: WhiteSpaceCollapse,
        should_trim_leading_white_space: bool,
    ) -> Self {
        Self {
            input_iterator,
            white_space_collapse,
            following_newline: false,
            trimming_leading_white_space: should_trim_leading_white_space,
            character_pending_to_return: None,
        }
    }

    /// In some cases, white space is replaced by a single character (when not
    /// following a newline and when leading whitespace is not being trimmed). In all
    /// other cases, the white space is simply removed. This method handles that.
    fn iteration_for_collapsed_whitespace(
        &self,
        collapsed_whitespace: Utf32CodeUnits,
    ) -> CharacterTransformIteration {
        if !self.following_newline && !self.trimming_leading_white_space {
            CharacterTransformIteration::collapse(collapsed_whitespace, Some(' '))
        } else {
            CharacterTransformIteration::collapse(collapsed_whitespace, None)
        }
    }

    fn iteration_for_collected_white_space(
        &self,
        collected_whitespace: Utf32CodeUnits,
    ) -> Option<CharacterTransformIteration> {
        (collected_whitespace.0 != 0)
            .then(|| self.iteration_for_collapsed_whitespace(collected_whitespace))
    }
}

impl<InputIterator: Iterator<Item = char>> Iterator for WhitespaceCollapse<InputIterator> {
    type Item = CharacterTransformIteration;

    fn next(&mut self) -> Option<Self::Item> {
        // Point 4.1.1 first bullet:
        // > If white-space is set to normal, nowrap, or pre-line, whitespace
        // > characters are considered collapsible
        // If whitespace is not considered collapsible, it is preserved entirely, which
        // means that we can simply return the input string exactly.
        if self.white_space_collapse == WhiteSpaceCollapse::Preserve ||
            self.white_space_collapse == WhiteSpaceCollapse::BreakSpaces
        {
            // From <https://drafts.csswg.org/css-text-3/#white-space-processing>:
            // > Carriage returns (U+000D) are treated identically to spaces (U+0020) in all respects.
            //
            // In the non-preserved case these are converted to space below.
            return match self.input_iterator.next() {
                Some('\r') => Some(CharacterTransformIteration::one_to_one(' ')),
                next => next.map(CharacterTransformIteration::one_to_one),
            };
        }

        if let Some(character) = self.character_pending_to_return.take() {
            // Once we produce a non-whitespace character, we are no longer trimming leading whitespace.
            self.trimming_leading_white_space = false;
            self.following_newline = false;
            return Some(CharacterTransformIteration::one_to_one(character));
        }

        // When we enter a collapsible white space region, we may need to wait to produce
        // a single white space character as soon as we encounter a non-white space
        // character. When that happens we queue up the non-white space character for the
        // next iterator call.
        let mut collected_whitespace = Utf32CodeUnits(0);

        while let Some(character) = self.input_iterator.next() {
            // Don't push non-newline whitespace immediately. Instead wait to push it until we
            // know that it isn't followed by a newline. See `push_pending_whitespace_if_needed`
            // above.
            if InlineFormattingContextBuilder::is_document_white_space(character) &&
                character != '\n'
            {
                collected_whitespace += Utf32CodeUnits(1);
                continue;
            }

            // Point 4.1.1:
            // > 2. Collapsible segment breaks are transformed for rendering according to the
            // >    segment break transformation rules.
            if character == '\n' {
                // From <https://drafts.csswg.org/css-text-3/#line-break-transform>
                // (4.1.3 -- the segment break transformation rules):
                //
                // > When white-space is pre, pre-wrap, or pre-line, segment breaks are not
                // > collapsible and are instead transformed into a preserved line feed"
                //
                // > 1. First, any collapsible segment break immediately following another
                // >    collapsible segment break is removed.
                // > 2. Then any remaining segment break is either transformed into a space (U+0020)
                // >    or removed depending on the context before and after the break.
                let iteration = if self.white_space_collapse != WhiteSpaceCollapse::Collapse {
                    CharacterTransformIteration::collapse(
                        collected_whitespace + Utf32CodeUnits(1),
                        Some('\n'),
                    )
                } else {
                    self.iteration_for_collapsed_whitespace(
                        collected_whitespace + Utf32CodeUnits(1),
                    )
                };

                self.following_newline = true;
                return Some(iteration);
            }

            // Non-whitespace character

            // Point 4.1.1:
            // > 2. Any sequence of collapsible spaces and tabs immediately preceding or
            // >    following a segment break is removed.
            // > 3. Every collapsible tab is converted to a collapsible space (U+0020).
            // > 4. Any collapsible space immediately following another collapsible space—even
            // >    one outside the boundary of the inline containing that space, provided both
            // >    spaces are within the same inline formatting context—is collapsed to have zero
            // >    advance width.
            if let Some(iteration) = self.iteration_for_collected_white_space(collected_whitespace)
            {
                self.character_pending_to_return = Some(character);
                return Some(iteration);
            }

            // Once we produce a non-whitespace character, we are no longer trimming leading whitespace.
            self.trimming_leading_white_space = false;
            self.following_newline = false;
            return Some(CharacterTransformIteration::one_to_one(character));
        }

        self.iteration_for_collected_white_space(collected_whitespace)
    }
}

pub(crate) struct TextTransformationIterator<'a> {
    case_map_iterator: Box<dyn Iterator<Item = CharacterTransformIteration> + 'a>,
    full_width: bool,
    full_size_kana: bool,
}

impl<'a> TextTransformationIterator<'a> {
    pub(crate) fn new(
        mut text: &'a str,
        style: &'a ComputedValues,
        trim_leading_white_space: bool,
        on_word_boundary: bool,
    ) -> Self {
        let text_security = style.get__webkit_text_security();

        // <https://drafts.csswg.org/css-text-4/#text-transform-property>
        let text_transform = style.get_text_transform();

        if text_transform.intersects(TextTransform::MATH_AUTO) {
            // `math-auto` only does anything “on text nodes containing a single character” per
            // https://w3c.github.io/mathml-core/#math-auto-transform
            //
            // TODO: should this be single character after whitespace collapsing?
            // TODO: does `::first-letter` mess with this check?
            let mut char_iter = text.chars();
            if let Some(first_char) = char_iter.next() &&
                let None = char_iter.next() &&
                let Some(&mapping) = super::mathml_italics::ITALICS_MAPPINGS.get(&first_char)
            {
                text = mapping
            }
        }

        let chars = text
            .chars()
            .map(move |character| map_character_for_webkit_text_security(text_security, character));
        let white_space_collapse = style.slow_clone_white_space_collapse();
        let iterator =
            WhitespaceCollapse::new(chars, white_space_collapse, trim_leading_white_space);

        // https://drafts.csswg.org/css-text-4/#text-transform-order
        // > When multiple transformations need to be applied,
        // > they are applied in the following order:
        // >
        // > * `word-space-transform`
        // > * `capitalize`, `uppercase`, and `lowercase`
        // > * `full-width`
        // > * `full-size-kana`
        // >
        // > Word space transformation and text transformation happen after
        // > § 4.3.1 Phase I: Collapsing and Transformation but before
        // > § 4.3.2 Phase II: Trimming and Positioning. This means for instance that full-width
        // > only transforms spaces (U+0020) to U+3000 IDEOGRAPHIC SPACE within
        // > preserved white space.

        let case_map_iterator = match text_transform.case() {
            TextTransformCase::None | TextTransformCase::MathAuto => {
                Box::new(iterator) as Box<dyn Iterator<Item = CharacterTransformIteration>>
            },
            TextTransformCase::Lowercase => {
                Box::new(simple_case_transform_iterator(iterator, |character| {
                    CharacterTransformIteration::case_mapped(character.to_lowercase())
                }))
            },
            TextTransformCase::Uppercase => {
                Box::new(simple_case_transform_iterator(iterator, |character| {
                    CharacterTransformIteration::case_mapped(character.to_uppercase())
                }))
            },
            TextTransformCase::Capitalize => Box::new(capitalization_iterator(
                iterator,
                text.len(),
                on_word_boundary,
                style
                    .get__x_lang()
                    .0
                    .parse()
                    .unwrap_or(LanguageIdentifier::UNKNOWN),
            )),
        };

        Self {
            case_map_iterator,
            full_width: text_transform.intersects(TextTransform::FULL_WIDTH),
            full_size_kana: text_transform.intersects(TextTransform::FULL_SIZE_KANA),
        }
    }
}

impl Iterator for TextTransformationIterator<'_> {
    type Item = CharacterTransformIteration;

    fn next(&mut self) -> Option<Self::Item> {
        // https://drafts.csswg.org/css-text-4/#text-transform-order
        // > When multiple transformations need to be applied,
        // > they are applied in the following order:
        // >
        // > * `word-space-transform`
        // > * `capitalize`, `uppercase`, and `lowercase`
        // > * `full-width`
        // > * `full-size-kana`
        let mut iteration = self.case_map_iterator.next()?;
        map_characters_with_phf(
            self.full_width,
            &mut iteration.characters,
            &super::full_width::FULL_WIDTH_MAPPINGS,
        );
        map_characters_with_phf(
            self.full_size_kana,
            &mut iteration.characters,
            &super::small_kana::SMALL_KANA_MAPPINGS,
        );
        Some(iteration)
    }
}

fn simple_case_transform_iterator(
    input_iterator: impl Iterator<Item = CharacterTransformIteration>,
    mapping: impl Fn(char) -> CharacterTransformIteration,
) -> impl Iterator<Item = CharacterTransformIteration> {
    input_iterator.map(move |iteration| {
        if iteration.is_one_to_one() {
            mapping(iteration.characters[0])
        } else {
            iteration
        }
    })
}

/// From <https://drafts.csswg.org/css-text-4/#typographic-letter-unit>:
/// > A typographic letter unit (or letter for the purpose of this specification) is a
/// > typographic character unit belonging to one of the Letter or Number general categories. See
/// > Appendix E: Characters and Properties for how to determine the Unicode properties of a
/// > typographic character unit.
fn is_typographic_letter_unit(character: char) -> bool {
    let category = GeneralCategory::for_char(character);
    GeneralCategoryGroup::Letter.contains(category) ||
        GeneralCategoryGroup::Number.contains(category)
}

#[derive(Default)]
struct CaseMappingSink(ArrayVec<char, MAX_CASE_MAPPING_LENGTH>);

impl std::fmt::Write for CaseMappingSink {
    fn write_str(&mut self, string: &str) -> std::fmt::Result {
        string
            .chars()
            .try_for_each(|character| self.write_char(character))
    }

    fn write_char(&mut self, character: char) -> std::fmt::Result {
        self.0.try_push(character).map_err(|_| std::fmt::Error)
    }
}

fn title_case(character: char, language: &LanguageIdentifier) -> CharacterTransformIteration {
    let mut buffer = [0; 4];
    let mut titlecase = CaseMappingSink::default();
    let result = CaseMapper::new()
        .titlecase_segment_with_only_case_data(
            character.encode_utf8(&mut buffer),
            language,
            TitlecaseOptions::default(),
        )
        .write_to(&mut titlecase);
    debug_assert!(
        result.is_ok(),
        "CaseMapping of {character} for language {language:?} required more than \
        MAX_CASE_MAPPING_LENGTH ({MAX_CASE_MAPPING_LENGTH}) characters."
    );
    CharacterTransformIteration::case_mapped(titlecase.0.into_iter())
}

/// Given an input iterator, a size hint for the number items in the iterator,
/// a boolean determining whether the start of the input represents a word
/// boundary and the language, return an iterator that capitalizes one-to-one mapped characters
/// from the input iterator.
pub(crate) fn capitalization_iterator(
    input_iterator: impl Iterator<Item = CharacterTransformIteration>,
    size_hint: usize,
    allow_word_at_start: bool,
    language: LanguageIdentifier,
) -> impl Iterator<Item = CharacterTransformIteration> {
    let mut iterations: Vec<_> = input_iterator.collect();
    let mut string = String::with_capacity(size_hint);
    for iteration in &iterations {
        string.extend(iteration.characters());
    }

    // For the purpose of capitalization, the additional segmentation rules of the complex scripts
    // are not needed, since none of these scripts have uppercase / lowercase.
    let word_segmenter =
        WordSegmenter::new_for_non_complex_scripts(WordBreakInvariantOptions::default());
    let mut bounds = word_segmenter.segment_str(&string).peekable();
    let mut current_byte_index = 0;
    let mut pending_word_start = false;
    for iteration in iterations.iter_mut() {
        let bytes_to_advance: usize = iteration
            .characters()
            .iter()
            .map(|character| character.len_utf8())
            .sum();
        if bytes_to_advance == 0 {
            continue;
        }

        if bounds.peek() == Some(&current_byte_index) {
            pending_word_start = current_byte_index != 0 || allow_word_at_start;
            bounds.next();
        }

        // From <https://drafts.csswg.org/css-text-4/#text-transform-property>:
        // > Puts the first typographic letter unit of each word, if lowercase, in titlecase;
        // > other characters are unaffected.
        if iteration.is_one_to_one() &&
            pending_word_start &&
            is_typographic_letter_unit(iteration.characters[0])
        {
            // TODO: text-transform-capitalize-007.html disagrees with the is_lowercase condition.
            if iteration.characters[0].is_lowercase() {
                *iteration = title_case(iteration.characters[0], &language);
            }

            pending_word_start = false;
        }

        current_byte_index += bytes_to_advance;
    }

    iterations.into_iter()
}

/// Map a character according to the rules of the `-webkit-text-security` CSS property.
///
/// Note: The behavior of `-webkit-text-security` isn't specified, so we have some
/// flexibility in the implementation. We just need to maintain a rough compatibility with
/// other browsers.
fn map_character_for_webkit_text_security(mode: &WebKitTextSecurity, character: char) -> char {
    if let WebKitTextSecurity::None = mode {
        return character;
    }

    // TODO: When MSRV is 1.95+ use std::hint::cold_path().
    match character {
        // Newlines are preserved, so that `<br>` keeps working as expected.
        '\n' => '\n',
        _ => match mode {
            WebKitTextSecurity::None => character, // unreachable
            WebKitTextSecurity::Circle => '○',
            WebKitTextSecurity::Disc => '●',
            WebKitTextSecurity::Square => '■',
        },
    }
}

fn map_characters_with_phf(enabled: bool, characters: &mut [char], map: &phf::Map<char, char>) {
    if enabled {
        // TODO: When MSRV is 1.95+ use std::hint::cold_path().

        for character in characters {
            if let Some(mapping) = map.get(character) {
                *character = *mapping
            }
        }
    }
}

#[derive(MallocSizeOf, Clone, Copy)]
struct OffsetMapKnownPosition {
    original_offset: Utf32CodeUnits,
    final_offset: Utf32CodeUnits,
}

#[derive(Default, MallocSizeOf)]
pub struct OffsetMap {
    /// Not including `IMPLICIT_KNOWN_POSITION_AT_START`
    known_positions: Vec<OffsetMapKnownPosition>,
    /// `Default` initializes to `false`
    last_range_maps_one_to_one: bool,
}

impl std::fmt::Debug for OffsetMap {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        f.debug_struct("OffsetMap")
            .field("total_original_size", &self.total_original_size())
            .field("total_final_size", &self.total_final_size())
            .finish()
    }
}

static IMPLICIT_KNOWN_POSITION_AT_START: OffsetMapKnownPosition = OffsetMapKnownPosition {
    original_offset: Utf32CodeUnits(0),
    final_offset: Utf32CodeUnits(0),
};

impl OffsetMap {
    fn last_known_position(&self) -> &OffsetMapKnownPosition {
        self.known_positions
            .last()
            .unwrap_or(&IMPLICIT_KNOWN_POSITION_AT_START)
    }

    pub fn total_original_size(&self) -> Utf32CodeUnits {
        self.last_known_position().original_offset
    }

    pub fn total_final_size(&self) -> Utf32CodeUnits {
        self.last_known_position().final_offset
    }

    pub fn push_range(
        &mut self,
        additional_original_length: Utf32CodeUnits,
        additional_final_length: Utf32CodeUnits,
    ) {
        let this_range_maps_one_to_one = additional_original_length == additional_final_length;
        if this_range_maps_one_to_one &&
            self.last_range_maps_one_to_one &&
            let Some(last) = self.known_positions.last_mut()
        {
            last.original_offset += additional_original_length;
            last.final_offset += additional_final_length;
        } else {
            let last = self.last_known_position();
            self.known_positions.push(OffsetMapKnownPosition {
                original_offset: last.original_offset + additional_original_length,
                final_offset: last.final_offset + additional_final_length,
            });
        }
        self.last_range_maps_one_to_one = this_range_maps_one_to_one;
    }

    pub(crate) fn push_iteration(&mut self, iteration: &CharacterTransformIteration) {
        self.push_range(
            iteration.consumed,
            Utf32CodeUnits(iteration.characters.len() as u32),
        );
    }

    pub fn map(&self, target_original_offset: Utf32CodeUnits) -> Utf32CodeUnits {
        self.map_common(
            target_original_offset,
            |position| position.original_offset,
            |position| position.final_offset,
        )
    }

    pub fn reverse_map(&self, target_final_offset: Utf32CodeUnits) -> Utf32CodeUnits {
        self.map_common(
            target_final_offset,
            |position| position.final_offset,
            |position| position.original_offset,
        )
    }

    fn map_common(
        &self,
        target_offset: Utf32CodeUnits,
        get_input_offset: impl Copy + Fn(&OffsetMapKnownPosition) -> Utf32CodeUnits,
        get_output_offset: impl Fn(&OffsetMapKnownPosition) -> Utf32CodeUnits,
    ) -> Utf32CodeUnits {
        if target_offset.0 == 0 {
            // Implict known position
            return Utf32CodeUnits(0);
        }
        match self
            .known_positions
            .binary_search_by_key(&target_offset, get_input_offset)
        {
            Ok(index) => {
                // Exact known position
                get_output_offset(&self.known_positions[index])
            },
            Err(index) => {
                // `index` is where inserting a new position would keep the `Vec` sorted
                if let Some(position_after) = self.known_positions.get(index) {
                    let position_before = if index > 0 {
                        &self.known_positions[index - 1]
                    } else {
                        &IMPLICIT_KNOWN_POSITION_AT_START
                    };
                    debug_assert!(target_offset > get_input_offset(position_before));
                    debug_assert!(target_offset < get_input_offset(position_after));
                    let offset_within_range = target_offset - get_input_offset(position_before);
                    let candidate = get_output_offset(position_before) + offset_within_range;
                    // If the output range is shorter, to go beyond it
                    let upper_bound = get_output_offset(position_after);
                    upper_bound.min(candidate)
                } else {
                    // `target_offset` at or past the end of the text covered by this map
                    get_output_offset(self.last_known_position())
                }
            },
        }
    }
}

#[test]
fn test_offsetmap_basic_expansion() {
    let original_string = "aßΰb";
    let final_string = "ASS\u{3a5}\u{308}\u{301}B";
    assert_eq!(original_string.to_uppercase(), final_string);

    let mut offset_map = OffsetMap::default();
    offset_map.push_iteration(&CharacterTransformIteration::case_mapped(
        'a'.to_uppercase(),
    ));
    offset_map.push_iteration(&CharacterTransformIteration::case_mapped(
        'ß'.to_uppercase(),
    ));
    offset_map.push_iteration(&CharacterTransformIteration::case_mapped(
        'ΰ'.to_uppercase(),
    ));
    offset_map.push_iteration(&CharacterTransformIteration::case_mapped(
        'b'.to_uppercase(),
    ));

    assert_eq!(offset_map.map(Utf32CodeUnits(0)).0, 0);
    assert_eq!(offset_map.map(Utf32CodeUnits(1)).0, 1);
    assert_eq!(offset_map.map(Utf32CodeUnits(2)).0, 3);
    assert_eq!(offset_map.map(Utf32CodeUnits(3)).0, 6);
    assert_eq!(offset_map.map(Utf32CodeUnits(4)).0, 7);

    // Beyond the last index should always map to the index after the last character
    // (for handling selections).
    assert_eq!(offset_map.map(Utf32CodeUnits(5)).0, 7);
    assert_eq!(offset_map.map(Utf32CodeUnits(100)).0, 7);

    let map_substring = |offset: u32, length: u32| {
        let start = usize::from(
            offset_map
                .map(Utf32CodeUnits(offset))
                .to_utf8_code_units_in(AssumeUnder4GB, final_string),
        );
        let end = usize::from(
            offset_map
                .map(Utf32CodeUnits(offset + length))
                .to_utf8_code_units_in(AssumeUnder4GB, final_string),
        );
        &final_string[start..end]
    };
    assert_eq!(map_substring(0, 1), "A");
    assert_eq!(map_substring(0, 2), "ASS");
    assert_eq!(map_substring(0, 3), "ASS\u{3a5}\u{308}\u{301}");
    assert_eq!(map_substring(0, 4), "ASS\u{3a5}\u{308}\u{301}B");
    assert_eq!(map_substring(1, 1), "SS");
}

#[test]
fn test_offsetmap_basic_collapse() {
    let _original_string = "  aaa  b \nc";
    let final_string = "aaa b\nc";

    let mut offset_map = OffsetMap::default();
    offset_map.push_iteration(&CharacterTransformIteration::collapse(
        Utf32CodeUnits(2),
        None,
    ));
    offset_map.push_iteration(&CharacterTransformIteration::one_to_one('a'));
    offset_map.push_iteration(&CharacterTransformIteration::one_to_one('a'));
    offset_map.push_iteration(&CharacterTransformIteration::one_to_one('a'));
    assert_eq!(
        offset_map.known_positions.len(),
        2,
        "Consecutive one-to-one mappings are merged"
    );

    offset_map.push_iteration(&CharacterTransformIteration::collapse(
        Utf32CodeUnits(2),
        Some(' '),
    ));
    offset_map.push_iteration(&CharacterTransformIteration::one_to_one('b'));
    offset_map.push_iteration(&CharacterTransformIteration::collapse(
        Utf32CodeUnits(2),
        Some('\n'),
    ));
    offset_map.push_iteration(&CharacterTransformIteration::one_to_one('c'));

    assert_eq!(offset_map.map(Utf32CodeUnits(0)).0, 0);
    assert_eq!(offset_map.map(Utf32CodeUnits(1)).0, 0);
    assert_eq!(offset_map.map(Utf32CodeUnits(2)).0, 0);
    assert_eq!(offset_map.map(Utf32CodeUnits(3)).0, 1);
    assert_eq!(offset_map.map(Utf32CodeUnits(4)).0, 2);
    assert_eq!(offset_map.map(Utf32CodeUnits(5)).0, 3);
    // Mapping from the middle of the collapsed sequence should map to after the replacement.
    assert_eq!(offset_map.map(Utf32CodeUnits(6)).0, 4);
    assert_eq!(offset_map.map(Utf32CodeUnits(7)).0, 4);
    assert_eq!(offset_map.map(Utf32CodeUnits(8)).0, 5);
    // Mapping from the middle of the collapsed sequence should map to after the replacement.
    assert_eq!(offset_map.map(Utf32CodeUnits(9)).0, 6);
    assert_eq!(offset_map.map(Utf32CodeUnits(10)).0, 6);
    assert_eq!(offset_map.map(Utf32CodeUnits(11)).0, 7);

    // Beyond the last index should always map to the index after the last character
    // (for handling selections).
    assert_eq!(offset_map.map(Utf32CodeUnits(12)).0, 7);
    assert_eq!(offset_map.map(Utf32CodeUnits(100)).0, 7);

    let map_substring = |offset: u32, length: u32| {
        let start = usize::from(offset_map.map(Utf32CodeUnits(offset)));
        let end = usize::from(offset_map.map(Utf32CodeUnits(offset + length)));
        &final_string[start..end]
    };
    assert_eq!(map_substring(0, 1), "");
    assert_eq!(map_substring(0, 3), "a");
    assert_eq!(map_substring(0, 5), "aaa");
    assert_eq!(map_substring(0, 6), "aaa ");
    assert_eq!(map_substring(0, 7), "aaa ");
    assert_eq!(map_substring(0, 8), "aaa b");
    assert_eq!(map_substring(0, 11), "aaa b\nc");
}