extend-docx 0.1.1

use std::{
    cell::RefCell,
    collections::{HashMap, HashSet},
    marker::PhantomData,
};

use crate::xml::{TagRange, TaggedRange};

#[inline]
fn token_requires_edit_checks(token: &str) -> bool {
    let bytes = token.as_bytes();
    memchr::memchr_iter(b'x', bytes).any(|at| bytes[at..].starts_with(b"xmlns"))
        || memchr::memchr_iter(b'&', bytes).any(|at| bytes.get(at + 1) == Some(&b'#'))
}

struct Element {
    start: u32,
    open_end: u32,
    end: u32,
    parent: u32,
    next: u32,
    name_id: u32,
}

impl Element {
    fn name_range(&self, names: &[NamedElements], offset: usize) -> std::ops::Range<usize> {
        let start = self.start as usize + 1 - offset;
        start..start + names[self.name_id as usize].name_len as usize
    }
}

struct NamedElements {
    start: u32,
    end: u32,
    name_len: u32,
}

#[derive(Default)]
struct TagCache {
    start: usize,
    end: usize,
    first: Vec<u32>,
}

#[derive(Clone, Default)]
struct NameCacheEntry {
    name: [u8; 32],
    len: u8,
    id: Option<usize>,
}

pub(crate) struct IndexData {
    address: usize,
    len: usize,
    elements: Vec<Element>,
    names: HashMap<String, usize>,
    named_elements: Vec<NamedElements>,
    positions: Vec<u32>,
    canonical: bool,
    serialization_equivalent: bool,
    hoisted_validation: bool,
}

#[cfg(not(target_arch = "wasm32"))]
type IndexStorage = std::sync::Arc<IndexData>;
#[cfg(target_arch = "wasm32")]
type IndexStorage = IndexData;

pub(crate) struct Index {
    address: usize,
    len: usize,
    data: IndexStorage,
    tag_cache: RefCell<TagCache>,
    name_cache: RefCell<Vec<NameCacheEntry>>,
}

impl std::ops::Deref for Index {
    type Target = IndexData;
    fn deref(&self) -> &Self::Target {
        &self.data
    }
}

impl Index {
    fn from_data(data: IndexData) -> Self {
        let address = data.address;
        let len = data.len;
        #[cfg(not(target_arch = "wasm32"))]
        let data = std::sync::Arc::new(data);
        Self {
            address,
            len,
            data,
            tag_cache: RefCell::new(TagCache::default()),
            name_cache: RefCell::new(Vec::new()),
        }
    }

    pub(crate) fn build(xml: &str) -> Option<Self> {
        Self::build_impl::<false, false, false, false>(xml).map(|(index, _)| index)
    }

    pub(crate) fn canonical(xml: &str) -> Option<Self> {
        if memchr::memchr(b'\r', xml.as_bytes()).is_some() {
            return None;
        }
        Self::build_impl::<true, false, false, false>(xml).map(|(index, _)| index)
    }

    pub(crate) fn canonical_serialized(xml: &str) -> Option<Self> {
        if memchr::memchr(b'\r', xml.as_bytes()).is_some() {
            return None;
        }
        Self::build_impl::<true, true, false, false>(xml).map(|(index, _)| index)
    }

    pub(crate) fn canonical_normalized(xml: &str) -> Option<Self> {
        if memchr::memchr(b'\r', xml.as_bytes()).is_some() {
            return None;
        }
        Self::build_impl::<true, false, true, false>(xml).map(|(index, _)| index)
    }

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

    pub(crate) fn all_elements_qualified(&self) -> bool {
        self.names.keys().all(|name| name.contains(':'))
    }

    pub(crate) fn canonical_hoisted(xml: &str) -> Option<(String, Self)> {
        let (index, xml) = Self::build_impl::<true, true, true, true>(xml)?;
        Some((xml?, index))
    }

    fn build_impl<
        const CANONICAL: bool,
        const SERIALIZED: bool,
        const NORMALIZED: bool,
        const HOIST: bool,
    >(
        xml: &str,
    ) -> Option<(Self, Option<String>)> {
        if xml.len() > u32::MAX as usize {
            return None;
        }
        let name_capacity = (xml.len() / 256).clamp(4, 128);
        let mut index = IndexData {
            address: xml.as_ptr() as usize,
            len: xml.len(),
            elements: Vec::new(),
            names: HashMap::with_capacity(name_capacity),
            named_elements: Vec::with_capacity(name_capacity),
            positions: Vec::new(),
            canonical: CANONICAL,
            serialization_equivalent: false,
            hoisted_validation: HOIST,
        };
        let mut interned = HashMap::<&str, usize>::with_capacity(name_capacity);
        let mut name_cache = [("", 0usize); 128];
        let mut open_cache = [("", 0usize); 128];
        let mut stack = Vec::<usize>::new();
        let mut canonical = Canonical {
            serialized: true,
            ..Canonical::default()
        };
        let mut roots = 0;
        let mut root_name_end = 0;
        let mut cursor = 0;
        while let Some(offset) = next_markup_start(&xml.as_bytes()[cursor..]) {
            let start = cursor + offset;
            if CANONICAL
                && cursor != start
                && !canonical.text::<SERIALIZED>(&xml[cursor..start], stack.is_empty())
            {
                return None;
            }
            let end = if CANONICAL {
                start + canonical_token_end(&xml.as_bytes()[start..])? + 1
            } else {
                crate::xml::tag_token_end(xml, start)?
            };
            cursor = end;
            let token = &xml[start..end];
            if !CANONICAL && memchr::memchr(b'<', &token.as_bytes()[1..]).is_some() {
                return None;
            }
            if token.starts_with("<?") {
                if HOIST {
                    return None;
                }
                if CANONICAL
                    && !matches!(
                        quick_xml::Reader::from_str(token).read_event(),
                        Ok(quick_xml::events::Event::Decl(_))
                    )
                {
                    return None;
                }
                continue;
            }
            if token.starts_with("<!") {
                return None;
            }
            if token.starts_with("</") {
                if HOIST {
                    canonical.close_scope(stack.len().checked_sub(1)?);
                }
                let id = stack.pop()?;
                let next = index.elements.len();
                let element = &mut index.elements[id];
                if xml.as_bytes()[element.name_range(&index.named_elements, 0)]
                    != xml.as_bytes()[start + 2..end - 1]
                {
                    return None;
                }
                if SERIALIZED && element.open_end as usize == start {
                    if HOIST {
                        canonical.edits.push((start - 1, start, "/>".to_owned()));
                        canonical.edits.push((start, end, String::new()));
                    } else {
                        canonical.serialized = false;
                    }
                }
                element.end = end as u32;
                element.next = next as u32;
            } else {
                let root = stack.is_empty();
                let cache_slot = if CANONICAL {
                    let bytes = token.as_bytes();
                    (bytes.len().wrapping_mul(31)
                        ^ ((bytes[1] as usize) << 3)
                        ^ ((bytes[bytes.len() / 2] as usize) << 1)
                        ^ bytes[bytes.len() - 2] as usize)
                        & (open_cache.len() - 1)
                } else {
                    0
                };
                let scope_cacheable = CANONICAL && (!HOIST
                    || canonical.activations.last().is_none_or(|(depth, _)| *depth == 0));
                let cached = !root && scope_cacheable && open_cache[cache_slot].0 == token;
                let name_id = if cached {
                    // Exact validated tokens retain their interned name in the same index.
                    open_cache[cache_slot].1
                } else {
                    let name_start = start + 1;
                    let mut name_end = name_start;
                    loop {
                        let byte = *xml.as_bytes().get(name_end)?;
                        if byte.is_ascii_alphanumeric() || matches!(byte, b'_' | b':') {
                            name_end += 1;
                        } else if byte.is_ascii_whitespace() || matches!(byte, b'/' | b'>') {
                            break;
                        } else {
                            return None;
                        }
                    }
                    if name_end == name_start {
                        return None;
                    }
                    let name = &xml[name_start..name_end];
                    let cacheable = scope_cacheable
                        && (!HOIST || !token_requires_edit_checks(token));
                    if CANONICAL {
                        if root {
                            roots += 1;
                            root_name_end = name_end;
                        }
                        if !canonical.open::<SERIALIZED, NORMALIZED, HOIST>(
                            name,
                            &xml[name_end..end],
                            root,
                            stack.len(),
                            xml.as_ptr() as usize,
                        ) {
                            return None;
                        }
                    }
                    let bytes = name.as_bytes();
                    let slot = (bytes.len().wrapping_mul(31)
                        ^ ((bytes[0] as usize) << 3)
                        ^ ((bytes[bytes.len() / 2] as usize) << 1)
                        ^ bytes[bytes.len() - 1] as usize)
                        & (name_cache.len() - 1);
                    let name_id = if name_cache[slot].0 == name {
                        name_cache[slot].1
                    } else {
                        if SERIALIZED && !canonical_name(name) {
                            return None;
                        }
                        let name_id = *interned.entry(name).or_insert_with(|| {
                            let lower = name.to_ascii_lowercase();
                            let name_id = if let Some(name_id) = index.names.get(&lower) {
                                *name_id
                            } else {
                                let name_id = index.named_elements.len();
                                // ASCII case folding preserves the QName byte length.
                                index.named_elements.push(NamedElements {
                                    start: 0,
                                    end: 0,
                                    name_len: name.len() as u32,
                                });
                                index.names.insert(lower, name_id);
                                name_id
                            };
                            if name.bytes().any(|b| b.is_ascii_uppercase()) {
                                index.names.insert(name.to_owned(), name_id);
                            }
                            name_id
                        });
                        name_cache[slot] = (name, name_id);
                        name_id
                    };
                    if !root && cacheable && token.len() <= 256 {
                        open_cache[cache_slot] = (token, name_id);
                    }
                    name_id
                };
                let id = index.elements.len();
                if id == 0 {
                    index.elements.reserve((xml.len() / 48).min(65536));
                }
                let empty = token.ends_with("/>");
                index.elements.push(Element {
                    start: start as u32,
                    open_end: end as u32,
                    end: if empty { end as u32 } else { 0 },
                    parent: stack.last().map(|id| *id as u32).unwrap_or(u32::MAX),
                    next: (id + 1) as u32,
                    name_id: name_id as u32,
                });
                // Each element consumes XML bytes, so the input size bound also bounds IDs.
                index.named_elements[name_id].end += 1;
                if !empty {
                    stack.push(id);
                } else if HOIST {
                    canonical.close_scope(stack.len());
                }
            }
        }
        if CANONICAL
            && (roots != 1 || !canonical.text::<SERIALIZED>(&xml[cursor..], stack.is_empty()))
        {
            return None;
        }
        index.serialization_equivalent = SERIALIZED && canonical.serialized;
        if !stack.is_empty() {
            return None;
        }
        let mut offset = 0;
        for named in &mut index.named_elements {
            let count = named.end;
            named.start = offset;
            named.end = offset;
            offset += count;
        }
        index.positions.resize(index.elements.len(), 0);
        for (id, element) in index.elements.iter().enumerate() {
            let named = &mut index.named_elements[element.name_id as usize];
            index.positions[named.end as usize] = id as u32;
            named.end += 1;
        }
        if HOIST {
            if !canonical.serialized {
                return None;
            }
            let mut bindings: Vec<_> = canonical.bindings.iter().collect();
            bindings.sort_unstable_by_key(|(name, _)| **name);
            let mut declarations = String::new();
            for (name, uri) in bindings {
                if *name == "xml" {
                    continue;
                }
                declarations.push_str(" xmlns");
                if !name.is_empty() {
                    declarations.push(':');
                    declarations.push_str(name);
                }
                declarations.push_str("=\"");
                declarations.push_str(uri);
                declarations.push('"');
            }
            canonical
                .edits
                .push((root_name_end, root_name_end, declarations));
            canonical
                .edits
                .sort_unstable_by_key(|(start, end, _)| (*start, *end));
            let mut out = String::with_capacity(xml.len());
            let mut offsets = Vec::with_capacity(canonical.edits.len());
            let mut cursor = 0;
            let mut delta = 0i64;
            for (start, end, replacement) in canonical.edits {
                if start < cursor || end > xml.len() {
                    return None;
                }
                out.push_str(&xml[cursor..start]);
                out.push_str(&replacement);
                delta += replacement.len() as i64 - (end - start) as i64;
                offsets.push((end, delta));
                cursor = end;
            }
            out.push_str(&xml[cursor..]);
            if out.len() > u32::MAX as usize {
                return None;
            }
            let mut edit = 0;
            let mut delta = 0i64;
            let mut translate = |offset: u32| {
                while edit < offsets.len() && offsets[edit].0 <= offset as usize {
                    delta = offsets[edit].1;
                    edit += 1;
                }
                (offset as i64 + delta) as u32
            };
            let mut parent = u32::MAX;
            for id in 0..index.elements.len() {
                let start = index.elements[id].start;
                while parent != u32::MAX && index.elements[parent as usize].end <= start {
                    let element = &mut index.elements[parent as usize];
                    element.end = translate(element.end);
                    parent = element.parent;
                }
                let element = &mut index.elements[id];
                let empty = element.open_end == element.end;
                element.start = translate(element.start);
                element.open_end = translate(element.open_end);
                if empty {
                    element.end = element.open_end;
                } else {
                    parent = id as u32;
                }
            }
            while parent != u32::MAX {
                let element = &mut index.elements[parent as usize];
                element.end = translate(element.end);
                parent = element.parent;
            }
            index.address = out.as_ptr() as usize;
            index.len = out.len();
            return Some((Self::from_data(index), Some(out)));
        }
        Some((Self::from_data(index), None))
    }

    #[cfg(not(target_arch = "wasm32"))]
    pub(crate) fn shared_source(&self) -> IndexedSource {
        IndexedSource {
            address: self.address,
            len: self.len,
            data: std::sync::Arc::clone(&self.data),
        }
    }

    fn name_id(&self, name: &str) -> Option<usize> {
        if name.is_empty() || name.len() > 32 {
            return self.find_name_id(name);
        }
        let bytes = name.as_bytes();
        let slot = (bytes.len().wrapping_mul(31)
            ^ ((bytes[0] as usize) << 3)
            ^ ((bytes[bytes.len() / 2] as usize) << 1)
            ^ bytes[bytes.len() - 1] as usize)
            & 127;
        let mut cache = self.name_cache.borrow_mut();
        if cache.is_empty() {
            cache.resize(128, NameCacheEntry::default());
        }
        let entry = &mut cache[slot];
        if entry.len as usize == bytes.len() && &entry.name[..bytes.len()] == bytes {
            return entry.id;
        }
        let id = self.find_name_id(name);
        entry.name[..bytes.len()].copy_from_slice(bytes);
        entry.len = bytes.len() as u8;
        entry.id = id;
        id
    }

    fn find_name_id(&self, name: &str) -> Option<usize> {
        if let Some(id) = self.names.get(name) {
            return Some(*id);
        }
        if !name.bytes().any(|b| b.is_ascii_uppercase()) {
            return None;
        }
        let mut folded = [0u8; 128];
        let id = if name.len() <= folded.len() {
            for (out, byte) in folded.iter_mut().zip(name.bytes()) {
                *out = byte.to_ascii_lowercase();
            }
            self.names
                .get(std::str::from_utf8(&folded[..name.len()]).ok()?)?
        } else {
            self.names.get(&name.to_ascii_lowercase())?
        };
        Some(*id)
    }

    fn positions_for(&self, name_id: usize) -> &[u32] {
        let named = &self.named_elements[name_id];
        &self.positions[named.start as usize..named.end as usize]
    }

    fn named(&self, name: &str) -> Option<&[u32]> {
        Some(self.positions_for(self.name_id(name)?))
    }
}

#[inline]
fn next_markup_start(bytes: &[u8]) -> Option<usize> {
    if bytes.first() == Some(&b'<') {
        Some(0)
    } else {
        memchr::memchr(b'<', bytes)
    }
}

#[inline]
fn canonical_token_end(bytes: &[u8]) -> Option<usize> {
    if let Some(prefix) = bytes.first_chunk::<8>() {
        let value = u64::from_le_bytes(*prefix) ^ u64::from_le_bytes([b'>'; 8]);
        let matches = value.wrapping_sub(0x0101010101010101) & !value & 0x8080808080808080;
        if matches != 0 {
            // Borrow propagation can mark later bytes, but the first match is exact.
            return Some(matches.trailing_zeros() as usize / 8);
        }
        return memchr::memchr(b'>', &bytes[8..]).map(|offset| offset + 8);
    }
    memchr::memchr(b'>', bytes)
}

#[derive(Default)]
struct Canonical<'a> {
    bindings: HashMap<&'a str, &'a str>,
    attributes: Vec<&'a str>,
    attribute_names: [(&'a str, bool); 32],
    bound_prefixes: u32,
    serialized: bool,
    active_unknown: HashSet<&'a str>,
    activations: Vec<(usize, &'a str)>,
    edits: Vec<(usize, usize, String)>,
}

fn is_prefix_list_attribute(key: &str) -> bool {
    matches!(key, "Requires" | "Ignorable")
        || key.ends_with(":Requires")
        || key.ends_with(":Ignorable")
}

fn canonical_name(name: &str) -> bool {
    let mut count = 0;
    name.split(':').all(|part| {
        count += 1;
        count <= 2
            && part
                .as_bytes()
                .first()
                .is_some_and(|byte| byte.is_ascii_alphabetic() || *byte == b'_')
    })
}

impl<'a> Canonical<'a> {
    fn prefix_bit(prefix: &str) -> u32 {
        match prefix {
            "w" => 1,
            "r" => 2,
            "a" => 4,
            "m" => 8,
            "c" => 16,
            "wp" => 32,
            "pic" => 64,
            "wps" => 128,
            "wpg" => 256,
            "mc" => 512,
            "w14" => 1024,
            "w15" => 2048,
            "v" => 4096,
            "o" => 8192,
            "wp14" => 16384,
            "w10" => 32768,
            _ => 0,
        }
    }

    fn is_bound<const HOIST: bool>(&self, prefix: &str) -> bool {
        let bit = Self::prefix_bit(prefix);
        if bit != 0 {
            return self.bound_prefixes & bit != 0;
        }
        prefix == "xml"
            || if HOIST {
                self.active_unknown.contains(prefix)
            } else {
                self.bindings.contains_key(prefix)
            }
    }

    fn close_scope(&mut self, depth: usize) {
        while self
            .activations
            .last()
            .is_some_and(|(level, _)| *level == depth)
        {
            let (_, prefix) = self.activations.pop().unwrap();
            self.bound_prefixes &= !Self::prefix_bit(prefix);
            self.active_unknown.remove(prefix);
        }
    }

    fn text<const SERIALIZED: bool>(&mut self, text: &str, outside: bool) -> bool {
        if outside {
            return text.bytes().all(|b| b.is_ascii_whitespace());
        }
        if SERIALIZED && memchr::memchr(b'>', text.as_bytes()).is_some() {
            self.serialized = false;
        }
        let mut remaining = text;
        while let Some(start) = memchr::memchr(b'&', remaining.as_bytes()) {
            let tail = &remaining[start + 1..];
            let Some(end) = memchr::memchr(b';', tail.as_bytes()) else {
                return false;
            };
            let (name, rest) = (&tail[..end], &tail[end + 1..]);
            if SERIALIZED && !matches!(name, "amp" | "lt" | "gt") {
                self.serialized = false;
            }
            if !matches!(name, "amp" | "lt" | "gt" | "quot" | "apos") {
                let code = name
                    .strip_prefix("#x")
                    .or_else(|| name.strip_prefix("#X"))
                    .and_then(|digits| u32::from_str_radix(digits, 16).ok())
                    .or_else(|| {
                        name.strip_prefix('#')
                            .and_then(|digits| digits.parse::<u32>().ok())
                    });
                if !code.is_some_and(|code| {
                    code >= 0x20
                        && !matches!(code, 0xfffe | 0xffff)
                        && char::from_u32(code).is_some()
                }) {
                    return false;
                }
            }
            remaining = rest;
        }
        true
    }

    fn open<const SERIALIZED: bool, const NORMALIZED: bool, const HOIST: bool>(
        &mut self,
        name: &'a str,
        mut tail: &'a str,
        root: bool,
        depth: usize,
        base: usize,
    ) -> bool {
        self.attributes.clear();
        loop {
            let whitespace = tail
                .as_bytes()
                .iter()
                .position(|byte| !byte.is_ascii_whitespace())
                .unwrap_or(tail.len());
            let trimmed = &tail[whitespace..];
            if matches!(trimmed, ">" | "/>") {
                if SERIALIZED && whitespace != 0 {
                    self.serialized = false;
                }
                break;
            }
            if trimmed.len() == tail.len() {
                return false;
            }
            if SERIALIZED && (whitespace != 1 || tail.as_bytes()[0] != b' ') {
                self.serialized = false;
            }
            let Some(key_end) = memchr::memchr(b'=', trimmed.as_bytes()) else {
                return false;
            };
            let key = &trimmed[..key_end];
            if key.is_empty() || self.attributes.contains(&key) {
                return false;
            }
            let bytes = key.as_bytes();
            let slot = (bytes.len().wrapping_mul(31)
                ^ ((bytes[0] as usize) << 3)
                ^ ((bytes[bytes.len() / 2] as usize) << 1)
                ^ bytes[bytes.len() - 1] as usize) & (self.attribute_names.len() - 1);
            let canonical = if self.attribute_names[slot].0 == key {
                self.attribute_names[slot].1
            } else {
                if !bytes.iter().all(|&b| b.is_ascii_alphanumeric() || matches!(b, b'_' | b':' | b'-' | b'.')) {
                    return false;
                }
                let canonical = !SERIALIZED || canonical_name(key);
                self.attribute_names[slot] = (key, canonical);
                canonical
            };
            if SERIALIZED && !canonical {
                self.serialized = false;
            }
            if HOIST && key.ends_with(":xmlns") {
                return false;
            }
            let Some(value_tail) = trimmed[key_end + 1..].strip_prefix('"') else {
                return false;
            };
            let Some(value_end) = memchr::memchr(b'"', value_tail.as_bytes()) else {
                return false;
            };
            let (value, rest) = (&value_tail[..value_end], &value_tail[value_end + 1..]);
            if value
                .bytes()
                .any(|b| matches!(b, b'\n' | b'\t' | b'<' | b'>'))
            {
                return false;
            }
            for position in memchr::memchr_iter(b'&', value.as_bytes()) {
                let reference = &value[position + 1..];
                if ["amp;", "lt;", "gt;", "quot;"]
                    .iter()
                    .any(|entity| reference.starts_with(entity))
                    || (NORMALIZED
                        && ["#9;", "#10;", "#13;"]
                            .iter()
                            .any(|entity| reference.starts_with(entity)))
                {
                    continue;
                }
                let replacement = if HOIST {
                    [
                        ("#xA;", "&#10;"),
                        ("#xa;", "&#10;"),
                        ("#xD;", "&#13;"),
                        ("#xd;", "&#13;"),
                        ("#x9;", "&#9;"),
                    ]
                    .into_iter()
                    .find(|(entity, _)| reference.starts_with(entity))
                } else {
                    None
                };
                let Some((source, replacement)) = replacement else {
                    return false;
                };
                let start = value.as_ptr() as usize - base + position;
                self.edits
                    .push((start, start + source.len() + 1, replacement.to_owned()));
            }
            if HOIST && is_prefix_list_attribute(key) && value.contains("&#") {
                return false;
            }
            self.attributes.push(key);
            if SERIALIZED
                && is_prefix_list_attribute(key)
                && !value.split_whitespace().eq(value.split(' '))
            {
                self.serialized = false;
            }
            if key == "xmlns" || key.starts_with("xmlns:") {
                if SERIALIZED && !root && !HOIST {
                    self.serialized = false;
                }
                let declared = key.strip_prefix("xmlns:").unwrap_or("");
                if HOIST
                    && (value.is_empty()
                        || declared == "xmlns"
                        || value == "http://www.w3.org/2000/xmlns/")
                {
                    return false;
                }
                if (!HOIST && !root && !self.bindings.contains_key(declared))
                    || memchr::memchr(b'&', value.as_bytes()).is_some()
                {
                    return false;
                }
                if let Some(expected) = crate::parse::canonical_namespace_prefix(value) {
                    if declared != expected {
                        return false;
                    }
                } else if declared.is_empty()
                    || [
                        "w", "r", "a", "m", "c", "wp", "pic", "wps", "wpg", "mc", "w14", "w15",
                        "v", "o", "xml", "wp14", "w10",
                    ]
                    .contains(&declared)
                {
                    return false;
                }
                if self.bindings.get(declared).is_some_and(|old| *old != value)
                    || self
                        .bindings
                        .iter()
                        .any(|(key, old)| *old == value && *key != declared)
                {
                    return false;
                }
                if HOIST {
                    if !self.is_bound::<HOIST>(declared) {
                        self.activations.push((depth, declared));
                        if Self::prefix_bit(declared) == 0 {
                            self.active_unknown.insert(declared);
                        }
                    }
                    self.edits.push((
                        tail.as_ptr() as usize - base,
                        rest.as_ptr() as usize - base,
                        String::new(),
                    ));
                }
                self.bindings.entry(declared).or_insert(value);
                self.bound_prefixes |= Self::prefix_bit(declared);
            }
            tail = rest;
        }
        if memchr::memchr(b':', name.as_bytes())
            .is_some_and(|position| !self.is_bound::<HOIST>(&name[..position]))
        {
            return false;
        }
        !self.attributes.iter().any(|key| {
            memchr::memchr(b':', key.as_bytes()).is_some_and(|position| {
                let prefix = &key[..position];
                prefix != "xmlns" && !self.is_bound::<HOIST>(prefix)
            })
        })
    }
}

thread_local! {
    static INDEXES: RefCell<Vec<Index>> = const { RefCell::new(Vec::new()) };
}

#[cfg(not(target_arch = "wasm32"))]
pub(crate) struct IndexedSource {
    address: usize,
    len: usize,
    data: std::sync::Arc<IndexData>,
}

#[cfg(not(target_arch = "wasm32"))]
impl IndexedSource {
    pub(crate) fn local_index(&self) -> Index {
        Index {
            address: self.address,
            len: self.len,
            data: std::sync::Arc::clone(&self.data),
            tag_cache: RefCell::new(TagCache::default()),
            name_cache: RefCell::new(Vec::new()),
        }
    }
}

// Source borrows and thread affinity keep address-based lookups valid for the scope.
pub(crate) struct Scope<'a> {
    previous: Vec<Index>,
    #[cfg(not(target_arch = "wasm32"))]
    shared: std::sync::Arc<[IndexedSource]>,
    source: PhantomData<std::rc::Rc<&'a str>>,
}

pub(crate) fn scope<'a>(
    parts: impl Iterator<Item = (&'a str, &'a str)>,
    mut prepared: HashMap<String, Index>,
) -> Scope<'a> {
    let mut indexes: Vec<_> = parts
        .filter_map(|(name, xml)| {
            let mut index = prepared.remove(name).or_else(|| Index::build(xml))?;
            index.address = xml.as_ptr() as usize;
            #[cfg(target_arch = "wasm32")]
            {
                index.data.address = xml.as_ptr() as usize;
            }
            Some(index)
        })
        .collect();
    indexes.sort_unstable_by_key(|index| index.address);
    #[cfg(not(target_arch = "wasm32"))]
    let shared = indexes
        .iter()
        .map(|index| IndexedSource {
            address: index.address,
            len: index.len,
            data: std::sync::Arc::clone(&index.data),
        })
        .collect::<Vec<_>>()
        .into();
    Scope {
        previous: INDEXES.with(|current| current.replace(indexes)),
        #[cfg(not(target_arch = "wasm32"))]
        shared,
        source: PhantomData,
    }
}

#[cfg(not(target_arch = "wasm32"))]
pub(crate) struct ScopeSnapshot<'a> {
    shared: std::sync::Arc<[IndexedSource]>,
    source: PhantomData<&'a str>,
}

#[cfg(not(target_arch = "wasm32"))]
impl Scope<'_> {
    pub(crate) fn snapshot(&self) -> ScopeSnapshot<'_> {
        ScopeSnapshot {
            shared: std::sync::Arc::clone(&self.shared),
            source: PhantomData,
        }
    }
}

#[cfg(not(target_arch = "wasm32"))]
impl<'a> ScopeSnapshot<'a> {
    pub(crate) fn enter(self) -> Scope<'a> {
        let indexes = self
            .shared
            .iter()
            .map(|source| Index {
                address: source.address,
                len: source.len,
                data: std::sync::Arc::clone(&source.data),
                tag_cache: RefCell::new(TagCache::default()),
                name_cache: RefCell::new(Vec::new()),
            })
            .collect();
        Scope {
            previous: INDEXES.with(|current| current.replace(indexes)),
            shared: self.shared,
            source: PhantomData,
        }
    }
}

impl Drop for Scope<'_> {
    fn drop(&mut self) {
        INDEXES.with(|current| current.replace(std::mem::take(&mut self.previous)));
    }
}

fn lookup<T>(xml: &str, visit: impl FnOnce(&Index, usize, usize) -> T) -> Option<T> {
    if xml.is_empty() {
        return None;
    }
    INDEXES.with(|indexes| {
        let indexes = indexes.borrow();
        let address = xml.as_ptr() as usize;
        let position = indexes
            .partition_point(|index| index.address <= address)
            .checked_sub(1)?;
        let index = &indexes[position];
        let start = address - index.address;
        let end = start.checked_add(xml.len())?;
        (end <= index.len).then(|| visit(index, start, end))
    })
}

pub(crate) fn tag<'a>(xml: &'a str, name: &str) -> Option<Option<&'a str>> {
    lookup(xml, |index, start, end| {
        let name_id = index.name_id(name)?;
        let element_id = if xml.len() <= 2048 {
            let mut cache = index.tag_cache.borrow_mut();
            if cache.start != start || cache.end != end || cache.first.is_empty() {
                cache.start = start;
                cache.end = end;
                cache.first.resize(index.named_elements.len(), u32::MAX);
                cache.first.fill(u32::MAX);
                let first = index
                    .elements
                    .partition_point(|element| (element.start as usize) < start);
                for (id, element) in index.elements.iter().enumerate().skip(first) {
                    if element.open_end as usize > end {
                        break;
                    }
                    let target = &mut cache.first[element.name_id as usize];
                    if *target == u32::MAX {
                        *target = id as u32;
                    }
                }
            }
            let id = cache.first[name_id];
            if id == u32::MAX {
                return None;
            }
            id as usize
        } else {
            let names = index.positions_for(name_id);
            let pos =
                names.partition_point(|id| (index.elements[*id as usize].start as usize) < start);
            *names.get(pos)? as usize
        };
        let element = &index.elements[element_id];
        ((element.open_end as usize) <= end)
            .then(|| &xml[element.start as usize - start..element.open_end as usize - start])
    })
}

pub(crate) fn unique_inner_xml<'a>(xml: &'a str, name: &str) -> Option<&'a str> {
    lookup(xml, |index, start, end| {
        if !index.canonical || index.names.keys().any(|candidate| {
            candidate.len() > name.len()
                && candidate.as_bytes()[..name.len()].eq_ignore_ascii_case(name.as_bytes())
        }) {
            return None;
        }
        let positions = index.named(name)?;
        let first = positions.partition_point(|id| (index.elements[*id as usize].start as usize) < start);
        let id = *positions.get(first)? as usize;
        let element = &index.elements[id];
        if element.end <= element.open_end || element.end as usize > end
            || positions.get(first + 1).is_some_and(|id| (index.elements[*id as usize].start as usize) < end)
        {
            return None;
        }
        // Canonical closing tokens contain only the matching QName and delimiters.
        let close_start = (element.end as usize).checked_sub(name.len() + 3)?;
        xml.get(element.open_end as usize - start..close_start.checked_sub(start)?)
    }).flatten()
}

pub(crate) fn opening_tags<'a>(xml: &'a str, name: &str) -> Option<Vec<&'a str>> {
    lookup(xml, |index, start, end| {
        if !index.canonical || index.names.keys().any(|candidate| {
            candidate.len() > name.len()
                && candidate.as_bytes()[name.len()] == b':'
                && candidate.as_bytes()[..name.len()].eq_ignore_ascii_case(name.as_bytes())
        }) {
            return None;
        }
        let Some(name_id) = index.name_id(name) else {
            return Some(Vec::new());
        };
        let positions = index.positions_for(name_id);
        let first = positions.partition_point(|id| (index.elements[*id as usize].start as usize) < start);
        let mut tags = Vec::new();
        for id in &positions[first..] {
            let element = &index.elements[*id as usize];
            if element.open_end as usize > end {
                break;
            }
            tags.push(&xml[element.start as usize - start..element.open_end as usize - start]);
        }
        Some(tags)
    }).flatten()
}

fn valid_xml_characters(xml: &str) -> bool {
    let bytes = xml.as_bytes();
    let invalid = bytes.iter().fold(0u8, |invalid, &byte| {
        invalid | u8::from(byte < 0x20 && !matches!(byte, b'\t' | b'\n' | b'\r'))
    });
    invalid == 0 && !memchr::memchr_iter(0xef, bytes).any(|at| {
        bytes.get(at + 1) == Some(&0xbf) && matches!(bytes.get(at + 2), Some(0xbe | 0xbf))
    })
}

pub(crate) fn feature_names(
    xml: &str,
    names: &[&str],
    mut visit: impl FnMut(&str, &str),
) -> Option<()> {
    lookup(xml, |index, start, end| {
        if !index.canonical || start != 0 || end != index.len
            || !valid_xml_characters(xml)
        {
            return None;
        }
        let root = index.elements.first()?;
        let mut depths = Vec::<u8>::with_capacity(index.elements.len());
        for element in &index.elements {
            let depth = if element.parent == u32::MAX {
                0
            } else {
                depths.get(element.parent as usize)?.checked_add(1)?
            };
            if depth >= 64 {
                return None;
            }
            depths.push(depth);
        }
        if !index.hoisted_validation {
            if memchr::memmem::find_iter(xml.as_bytes(), b"&#").any(|offset| {
                !["&#9;", "&#10;", "&#13;"].iter().any(|reference| xml[offset..].starts_with(reference))
            }) || xml.contains("]]>")
                || index.names.keys().any(|name| !canonical_name(name))
                || xml[root.open_end as usize..].contains("<?")
            {
                return None;
            }
            let mut checked = [""; 128];
            for element in &index.elements {
                let open_end = element.open_end as usize;
                let trim = if xml.as_bytes()[open_end - 2] == b'/' { 2 } else { 1 };
                let content = &xml[element.start as usize + 1..open_end - trim];
                let bytes = content.as_bytes();
                let slot = (bytes.len().wrapping_mul(31)
                    ^ ((bytes[0] as usize) << 3)
                    ^ ((bytes[bytes.len() / 2] as usize) << 1)
                    ^ bytes[bytes.len() - 1] as usize) & (checked.len() - 1);
                if checked[slot] == content {
                    continue;
                }
                let name_len = index.named_elements[element.name_id as usize].name_len as usize;
                let tag = quick_xml::events::BytesStart::from_content(content, name_len);
                for attribute in tag.attributes().with_checks(false) {
                    let attribute = attribute.ok()?;
                    let name: &str = attribute.key.as_ref();
                    if !canonical_name(name) || name.ends_with(":xmlns")
                        || (name.starts_with("xmlns:") && attribute.value.is_empty())
                    {
                        return None;
                    }
                }
                if content.len() <= 256 {
                    checked[slot] = content;
                }
            }
        }
        let mut root_xml = xml[..root.open_end as usize - 1].to_owned();
        if !root_xml.ends_with('/') {
            root_xml.push('/');
        }
        root_xml.push('>');
        let declaration = roxmltree::Document::parse(&root_xml).ok()?;
        let root_node = declaration.root_element();
        for name_id in 0..index.named_elements.len() {
            let positions = index.positions_for(name_id);
            let Some(first) = positions.first() else { continue; };
            let first = &index.elements[*first as usize];
            let name = &xml[first.name_range(&index.named_elements, 0)];
            let local = name.rsplit(':').next().unwrap_or(name);
            if !names.iter().any(|candidate| local.eq_ignore_ascii_case(candidate)) {
                continue;
            }
            for position in positions {
                let element = &index.elements[*position as usize];
                let qualified = &xml[element.name_range(&index.named_elements, 0)];
                let (prefix, local) = qualified.split_once(':')
                    .map_or((None, qualified), |(prefix, local)| (Some(prefix), local));
                visit(root_node.lookup_namespace_uri(prefix).unwrap_or(""), local);
            }
        }
        Some(())
    }).flatten()
}

pub(crate) fn contains_local_names(xml: &str, names: &[&str]) -> Option<bool> {
    lookup(xml, |index, _, _| {
        index.names.keys().any(|name| {
            let local = name.rsplit(':').next().unwrap_or(name);
            names.iter().any(|name| local.eq_ignore_ascii_case(name))
        })
    })
}

pub(crate) fn alternate_choices(xml: &str) -> Option<Vec<(TagRange, TagRange)>> {
    lookup(xml, |index, start, end| {
        if !index.canonical {
            return None;
        }
        let Some(alternates) = index.named("mc:AlternateContent") else {
            return None;
        };
        let choices = index.named("mc:Choice").unwrap_or(&[]);
        let first =
            alternates.partition_point(|id| (index.elements[*id as usize].start as usize) < start);
        let mut result = Vec::new();
        for (position, id) in alternates.iter().enumerate().skip(first) {
            let alternate = &index.elements[*id as usize];
            let a_start = alternate.start as usize;
            let a_end = alternate.end as usize;
            if a_start >= end {
                break;
            }
            if a_end > end
                || alternates
                    .get(position + 1)
                    .is_some_and(|id| (index.elements[*id as usize].start as usize) < a_end)
            {
                return None;
            }
            let alternate_xml = &xml[a_start - start..a_end - start];
            if !alternate_xml.starts_with("<mc:AlternateContent")
                || !alternate_xml.ends_with("</mc:AlternateContent>")
            {
                return None;
            }
            let choice_pos = choices
                .partition_point(|id| (index.elements[*id as usize].start as usize) < a_start);
            let Some(choice_id) = choices.get(choice_pos) else {
                continue;
            };
            let choice = &index.elements[*choice_id as usize];
            if choice.start as usize >= a_end {
                continue;
            }
            if choice.end as usize > a_end
                || choices
                    .get(choice_pos + 1)
                    .is_some_and(|id| index.elements[*id as usize].start < choice.end)
            {
                return None;
            }
            let choice_xml = &xml[choice.start as usize - start..choice.end as usize - start];
            if !choice_xml.starts_with("<mc:Choice")
                || !choice_xml.ends_with("</mc:Choice>")
                || choice_xml.find('>') != Some((choice.open_end - choice.start) as usize - 1)
            {
                return None;
            }
            result.push((
                TagRange {
                    start: a_start - start,
                    end: a_end - start,
                },
                TagRange {
                    start: choice.open_end as usize - start,
                    end: choice.end as usize - start - "</mc:Choice>".len(),
                },
            ));
        }
        Some(result)
    })
    .flatten()
}

pub(crate) fn ranges(xml: &str, name: &str) -> Option<Vec<TagRange>> {
    lookup(xml, |index, start, end| {
        let mut result = Vec::new();
        let Some(names) = index.named(name) else {
            return result;
        };
        let pos = names.partition_point(|id| (index.elements[*id as usize].start as usize) < start);
        let mut covered = start;
        for id in &names[pos..] {
            let element = &index.elements[*id as usize];
            if (element.start as usize) >= end {
                break;
            }
            if (element.start as usize) < covered {
                continue;
            }
            covered = element.end as usize;
            if (element.end as usize) <= end {
                result.push(TagRange {
                    start: (element.start as usize) - start,
                    end: (element.end as usize) - start,
                });
            }
        }
        result
    })
}

pub(crate) fn children(xml: &str) -> Option<Vec<TaggedRange>> {
    lookup(xml, |index, start, end| {
        let root = index
            .elements
            .partition_point(|element| (element.start as usize) < start);
        let element = index.elements.get(root)?;
        if (element.start as usize) != start || (element.end as usize) > end {
            return None;
        }
        let mut result = Vec::new();
        let mut child = root + 1;
        while child < (element.next as usize) {
            let node = &index.elements[child];
            if node.parent != root as u32 {
                return None;
            }
            result.push(TaggedRange {
                start: (node.start as usize) - start,
                end: (node.end as usize) - start,
                tag_name: xml[node.name_range(&index.named_elements, start)].to_owned(),
            });
            child = node.next as usize;
        }
        Some(result)
    })
    .flatten()
}

pub(crate) fn for_each_child<'a>(
    xml: &'a str,
    mut visit: impl FnMut(&'a str, &'a str) -> bool,
) -> Option<bool> {
    lookup(xml, |index, start, end| {
        let root = index
            .elements
            .partition_point(|element| (element.start as usize) < start);
        let element = index.elements.get(root)?;
        if element.start as usize != start || element.end as usize > end {
            return None;
        }
        let mut child = root + 1;
        while child < element.next as usize {
            let node = &index.elements[child];
            if node.parent != root as u32 {
                return None;
            }
            if !visit(
                &xml[node.name_range(&index.named_elements, start)],
                &xml[node.start as usize - start..node.end as usize - start],
            ) {
                return Some(false);
            }
            child = node.next as usize;
        }
        Some(true)
    })
    .flatten()
}

pub(crate) struct ElementRef<'a> {
    pub(crate) name: &'a str,
    pub(crate) xml: &'a str,
    pub(crate) source_start: usize,
    open_end: usize,
}

impl<'a> ElementRef<'a> {
    pub(crate) fn content(&self) -> Option<&'a str> {
        (self.open_end != self.xml.len())
            .then(|| &self.xml[self.open_end..self.xml.len() - self.name.len() - 3])
    }
}

pub(crate) fn for_each_element<'a>(
    xml: &'a str,
    mut visit: impl FnMut(ElementRef<'a>) -> bool,
) -> Option<bool> {
    lookup(xml, |index, start, end| {
        if !index.canonical {
            return None;
        }
        let root = index
            .elements
            .partition_point(|element| (element.start as usize) < start);
        let element = index.elements.get(root)?;
        if element.start as usize != start || element.end as usize != end {
            return None;
        }
        for node in &index.elements[root..element.next as usize] {
            let name_range = node.name_range(&index.named_elements, start);
            let boundary = xml.as_bytes()[name_range.end];
            if matches!(boundary, b'\x0b' | b'\x0c') {
                return None;
            }
            if !visit(ElementRef {
                name: &xml[name_range],
                xml: &xml[node.start as usize - start..node.end as usize - start],
                source_start: node.start as usize - start,
                open_end: node.open_end as usize - node.start as usize,
            }) {
                return Some(false);
            }
        }
        Some(true)
    })
    .flatten()
}

pub(crate) fn child<'a>(xml: &'a str, name: &str) -> Option<Option<&'a str>> {
    lookup(xml, |index, start, end| {
        let root = index
            .elements
            .partition_point(|element| (element.start as usize) < start);
        let element = index.elements.get(root)?;
        if (element.start as usize) != start || (element.end as usize) > end {
            return None;
        }
        let mut child = root + 1;
        while child < (element.next as usize) {
            let node = &index.elements[child];
            if node.parent != root as u32 {
                return None;
            }
            if xml[node.name_range(&index.named_elements, start)].eq_ignore_ascii_case(name) {
                return Some(Some(
                    &xml[(node.start as usize) - start..(node.end as usize) - start],
                ));
            }
            child = node.next as usize;
        }
        Some(None)
    })
    .flatten()
}

#[cfg(test)]
mod position_tests {
    #[test]
    fn positions_remain_ordered_across_interleaved_and_case_variant_names() {
        let xml = "<w:root><w:a/><w:b><w:a/></w:b><w:A/><w:a/></w:root>";
        let index = super::Index::build(xml).unwrap();
        assert_eq!(index.named("w:a"), Some([1, 3, 4, 5].as_slice()));
        assert_eq!(index.named("w:A"), Some([1, 3, 4, 5].as_slice()));
        assert_eq!(index.named("w:b"), Some([2].as_slice()));
        let _scope = super::scope([("part", xml)].into_iter(), Default::default());
        let nested = &xml[xml.find("<w:b>").unwrap()..xml.find("</w:b>").unwrap() + 6];
        assert_eq!(super::tag(nested, "w:a"), Some(Some("<w:a/>")));
        assert_eq!(super::children(nested).unwrap().len(), 1);
    }
}

#[cfg(all(test, not(target_arch = "wasm32")))]
mod shared_scope_tests {
    #[test]
    fn snapshot_retains_its_source_across_nested_scopes_and_threads() {
        let outer = "<w:root><w:a/></w:root>";
        let inner = "<w:root><w:b/></w:root>";
        let scope = super::scope([("outer", outer)].into_iter(), Default::default());
        let _nested = super::scope([("inner", inner)].into_iter(), Default::default());
        let snapshot = scope.snapshot();
        std::thread::scope(|threads| {
            threads
                .spawn(move || {
                    let _installed = snapshot.enter();
                    assert_eq!(super::tag(outer, "w:a"), Some(Some("<w:a/>")));
                    assert_eq!(super::tag(inner, "w:b"), None);
                })
                .join()
                .unwrap();
        });
        assert_eq!(super::tag(inner, "w:b"), Some(Some("<w:b/>")));
    }
}

#[cfg(all(test, not(target_arch = "wasm32")))]
mod shared_index_tests {
    use super::*;

    #[test]
    fn shared_offsets_rebase_for_independent_buffers_and_workers() {
        let original = String::from("<root><item value=\"one\"/><item value=\"two\"/></root>");
        let index = Index::build(&original).unwrap();
        for _ in 0..4 {
            let copied = original.clone();
            assert_ne!(original.as_ptr(), copied.as_ptr());
            let scope = scope([("part", copied.as_str())].into_iter(), HashMap::from([("part".to_owned(), index.shared_source().local_index())]));
            let token = tag(&copied, "item").flatten().unwrap();
            assert_eq!(token, "<item value=\"one\"/>");
            assert_eq!(token.as_ptr(), copied[6..].as_ptr());
            let snapshot = scope.snapshot();
            std::thread::scope(|threads| {
                threads.spawn(|| {
                    let _entered = snapshot.enter();
                    let token = tag(&copied, "item").flatten().unwrap();
                    assert_eq!(token.as_ptr(), copied[6..].as_ptr());
                }).join().unwrap();
            });
        }
    }
}

#[cfg(test)]
mod cached_attribute_proof_tests {
    use super::Index;

    fn wrapped(body: &str) -> String {
        format!("<w:root xmlns:w=\"http://schemas.openxmlformats.org/wordprocessingml/2006/main\">{body}</w:root>")
    }

    #[test]
    fn repeated_names_keep_duplicate_and_namespace_checks() {
        for tail in [
            "<w:item w:key=\"a\" w:key=\"b\"/>",
            "<w:item xmlns:w=\"urn:changed\" w:key=\"b\"/>",
            "<w:item q:key=\"b\"/>",
            "<w:item w:ke?y=\"b\"/>",
        ] {
            let xml = wrapped(&format!("<w:item w:key=\"a\"/>{tail}"));
            assert!(Index::canonical(&xml).is_none());
        }
    }

    #[test]
    fn attribute_proofs_preserve_serialization_and_index_positions() {
        let body: String = (0..96).map(|index| format!("<w:item key{index}=\"value\" w:key=\"{index}\"/>")).collect();
        let xml = wrapped(&body);
        let index = Index::canonical_serialized(&xml).unwrap();
        assert!(index.serialization_equivalent());
        assert_eq!(index.elements.len(), 97);
        let invalid = wrapped("<w:item 1key=\"a\"/><w:item 1key=\"b\"/>");
        assert!(!Index::canonical_serialized(&invalid).unwrap().serialization_equivalent());
    }
}


#[cfg(test)]
mod linear_offset_remap_tests {
    use super::Index;

    #[test]
    fn translated_boundaries_equal_a_fresh_index() {
        for repetitions in [1, 7, 129] {
            let fragment = "<w:p><w:r w:val=\"&#xA;&#x9;\"><w:t>λ😀&amp;text</w:t></w:r><w:p/><w:r></w:r><q:item xmlns:q=\"urn:shared\"><q:leaf/><q:item></q:item></q:item></w:p>";
            let xml = format!("<w:root xmlns:w=\"http://schemas.openxmlformats.org/wordprocessingml/2006/main\">{}</w:root>", fragment.repeat(repetitions));
            let (normalized, actual) = Index::canonical_hoisted(&xml).unwrap();
            let expected = Index::canonical_normalized(&normalized).unwrap();
            assert_eq!(actual.elements.len(), expected.elements.len());
            for (actual, expected) in actual.elements.iter().zip(&expected.elements) {
                assert_eq!((actual.start, actual.open_end, actual.end, actual.parent, actual.next),
                           (expected.start, expected.open_end, expected.end, expected.parent, expected.next));
            }
            assert_eq!(actual.positions, expected.positions);
        }
    }
}

#[cfg(test)]
mod hoist_token_search_tests {
    #[test]
    fn byte_prefilters_preserve_edit_detection() {
        let fragments = ["", "x", "xml", "xmlns", "xmlns:", "xxmlns", "&", "&#", "&amp;", "x&", "α中😀", "\0", "#", "x#m"];
        for prefix in fragments {
            for middle in fragments {
                for suffix in fragments {
                    let token = format!("{prefix}{middle}{suffix}");
                    assert_eq!(super::token_requires_edit_checks(&token), token.contains("xmlns") || token.contains("&#"));
                }
            }
        }
        for padding in 0..=129 {
            for middle in fragments {
                let token = format!("{}{}{}", " ".repeat(padding), middle, " ".repeat(131 - padding));
                assert_eq!(super::token_requires_edit_checks(&token), token.contains("xmlns") || token.contains("&#"));
            }
        }
    }
}

#[cfg(test)]
mod hoist_cache_prefilter_tests {
    #[test]
    fn cached_tokens_do_not_hide_scoped_bindings_or_repeated_edits() {
        let binding = "http://schemas.openxmlformats.org/wordprocessingml/2006/main";
        let xml = format!("<w:root xmlns:w=\"{binding}\"><w:p/><w:p/><w:p w:val=\"&#xA;\"/><w:p w:val=\"&#xA;\"/><w:group xmlns:q=\"urn:qualified\"><q:item/><w:p/><q:item/></w:group><w:p/></w:root>");
        let (normalized, _) = super::Index::canonical_hoisted(&xml).unwrap();
        assert_eq!(normalized.matches("&#10;").count(), 2);
        let original = roxmltree::Document::parse(&xml).unwrap();
        let actual = roxmltree::Document::parse(&normalized).unwrap();
        let signature = |doc: &roxmltree::Document<'_>| doc.descendants().filter(|node| node.is_element()).map(|node| {
            (node.tag_name().namespace().map(str::to_owned), node.tag_name().name().to_owned(),
             node.attributes().map(|attr| (attr.namespace().map(str::to_owned), attr.name().to_owned(), attr.value().to_owned())).collect::<Vec<_>>())
        }).collect::<Vec<_>>();
        assert_eq!(signature(&original), signature(&actual));
        let unbound = xml.replace("</w:root>", "<q:item/></w:root>");
        assert!(super::Index::canonical_hoisted(&unbound).is_none());
    }
}

#[cfg(test)]
mod feature_character_tests {
    #[test]
    fn byte_validation_matches_every_unicode_scalar() {
        for scalar in (0..=0x10ffff).filter_map(char::from_u32) {
            let valid = matches!(scalar, '\t' | '\n' | '\r')
                || (scalar >= '\u{20}' && !matches!(scalar, '\u{fffe}' | '\u{ffff}'));
            for padding in [0, 15, 31] {
                let text = format!("{}{scalar}{}", "a".repeat(padding), "z".repeat(32));
                assert_eq!(super::valid_xml_characters(&text), valid);
            }
        }
    }
}

#[cfg(test)]
mod token_metadata_tests {
    use super::Index;

    #[test]
    fn repeated_token_metadata_matches_uncached_index_positions() {
        let mut body = String::new();
        for index in 0..256 {
            body.push_str(&format!("<w:outer><w:item/><w:item/><w:Item/><w:other a=\"{index}\"/></w:outer>"));
        }
        let xml = format!("<w:root xmlns:w=\"http://schemas.openxmlformats.org/wordprocessingml/2006/main\">{body}</w:root>");
        let actual = Index::canonical(&xml).unwrap();
        let expected = Index::build(&xml).unwrap();
        assert_eq!(actual.elements.len(), expected.elements.len());
        assert_eq!(actual.positions, expected.positions);
        assert_eq!(actual.names, expected.names);
        for (actual, expected) in actual.elements.iter().zip(&expected.elements) {
            assert_eq!((actual.start, actual.open_end, actual.end, actual.parent, actual.next, actual.name_id),
                       (expected.start, expected.open_end, expected.end, expected.parent, expected.next, expected.name_id));
        }
    }

    #[test]
    fn cached_tokens_cannot_supply_a_second_root() {
        assert!(Index::canonical("<root><item/></root><item/>").is_none());
        assert!(Index::canonical_serialized("<root><item/></root><item/>").is_none());
    }
}

#[cfg(test)]
mod short_token_scan_tests {
    #[test]
    fn delimiter_offsets_match_byte_search_across_all_pairs_and_boundaries() {
        for left in 0..=255 {
            for right in 0..=255 {
                for padding in 0..=17 {
                    let mut bytes = vec![b'z'; padding];
                    bytes.extend([left, right]);
                    bytes.extend([b'z'; 17]);
                    assert_eq!(super::canonical_token_end(&bytes), memchr::memchr(b'>', &bytes));
                    assert_eq!(super::next_markup_start(&bytes), memchr::memchr(b'<', &bytes));
                }
            }
        }
        for length in 0..=17 {
            for position in 0..=length {
                let mut bytes = vec![b'z'; length];
                if position < length { bytes[position] = b'>'; }
                assert_eq!(super::canonical_token_end(&bytes), memchr::memchr(b'>', &bytes));
            }
        }
    }
}