GitCorner

Code

ossartcraftdeckcraft🌐
e4f86d11fe8a
//! PPTX import: package → [`Presentation`].

pub(crate) mod chart;
mod chartex;
pub(crate) mod dml;
mod shapes;
mod theme;
mod timing;

pub(crate) use chart::{chart_from as chart_from_el, read_chart_xml};
pub(crate) use chartex::{chartex_from, read_chartex_xml};

use std::cell::Cell;
use std::collections::{HashMap, HashSet};
use std::sync::Arc;

use deckcraft_geom::{Size, emu_to_pt};
use deckcraft_model::text::TextBody;
use deckcraft_model::{
    Background, Comment, CustomShow, EmbeddedFont, Geom, HeaderFooter, Layout, LayoutId, LayoutType, Master, MasterId, MediaId, MediaItem, PhType,
    Presentation, Properties, Section, ShowSettings, Slide, SlideId, defaults,
};

use crate::PptxError;
use crate::opc::{self, Package, Rels};
use crate::xml::{Doc, El, Node};

/// A snapshot of the import state a discarded read rolls back to.
pub struct Mark {
    diagram_xml_bytes: usize,
    media: usize,
    media_keys: usize,
    tag_bytes: usize,
    tags_capped: bool,
    kept_sidecar_bytes: usize,
    kept_chart_keys: usize,
}

/// Import state shared by all parts.
pub struct Imp<'a> {
    pub pkg: &'a Package,
    pub media: Vec<MediaItem>,
    pub media_by_part: HashMap<String, MediaId>,
    /// Keys added to `media_by_part`, in order, so a rollback removes only its own.
    pub media_keys: Vec<String>,
    pub next: u32,
    pub slide_by_part: HashMap<String, SlideId>,
    pub custom_show_names: HashMap<String, String>,
    /// GUIDs (upper case) of the table styles the file defines.
    pub table_style_ids: Vec<String>,
    /// Per legacy VML drawing part: shape id → preview picture part (see `shapes::vml_preview`).
    pub vml_previews: HashMap<String, HashMap<String, String>>,
    /// Aggregate byte count of retained chart sidecars across the presentation.
    pub kept_sidecar_bytes: usize,
    /// Data slots of the charts decoded so far (see `chart::MAX_PRESENTATION_CHART_POINTS`).
    pub chart_points: usize,
    /// Points the presentation may hold across modelled charts.
    pub chart_points_cap: usize,
    /// Cached kept sidecars by normalized chart part name.
    pub kept_charts: HashMap<String, deckcraft_model::chart::ChartKept>,
    /// Keys added to `kept_charts`, in order, for rollback.
    pub kept_chart_keys: Vec<String>,
    /// Chart parts whose sidecar capture was refused, with the retained-byte total it started from:
    /// the same start gives the same refusal, so the copy is not repeated.
    pub rejected_kept: HashMap<String, usize>,
    /// Bytes of chart parts decoded so far, rejected ones included (see `chart::MAX_CHART_DECODE_BYTES`).
    pub chart_decode_bytes: usize,
    /// Add-in tags parts, parsed once each, by normalized part name.
    pub tags_by_part: HashMap<String, Arc<[(String, String)]>>,
    /// Bytes of tags copied into the model so far (see [`MAX_TAG_BYTES`]).
    pub tag_bytes: usize,
    /// The tag budget ran out and the warning was given.
    pub tags_capped: bool,
    /// What the file lost that the reader kept going past (see [`MAX_IMPORT_WARNINGS`]).
    pub warnings: Vec<String>,
    /// Bytes of preserved theme XML kept by the masters read so far.
    pub theme_extra_bytes: usize,
    /// Shapes read from SmartArt drawings so far (see `shapes::MAX_SMARTART_SHAPES`).
    pub smartart_shapes: usize,
    /// Bytes of SmartArt layout, style and colour definitions copied into diagrams so far.
    pub diagram_xml_bytes: usize,
    /// Whether a part has relationships of its own, by normalized part name: looked up once
    /// however many embedded objects point at the part.
    pub has_rels: HashMap<String, bool>,
}

/// Import warnings kept; a hostile file with many oversized tables adds no more than this.
const MAX_IMPORT_WARNINGS: usize = 32;

impl Imp<'_> {
    /// Record something the file lost, and log it.
    pub fn warn(&mut self, msg: String) {
        log::warn!("pptx: {msg}");
        if self.warnings.len() < MAX_IMPORT_WARNINGS {
            self.warnings.push(msg);
        }
    }
    pub fn alloc(&mut self) -> u32 {
        self.next = self.next.saturating_add(1);
        self.next
    }
    /// Media item for an internal part, read once.
    pub fn media_for(&mut self, part: &str) -> Option<MediaId> {
        let key = opc::norm(part);
        if let Some(m) = self.media_by_part.get(&key) {
            return Some(*m);
        }
        let data = self.pkg.get(part)?.to_vec();
        let name = opc::file_of(self.pkg.original_name(part).unwrap_or(part)).to_string();
        let content_type = self.pkg.content_type(part).filter(|c| !c.is_empty()).unwrap_or_else(|| crate::mime_for(&name).to_string());
        let id = MediaId(self.alloc());
        self.media.push(MediaItem { id, name, content_type, data: Arc::new(data), link: None });
        self.media_keys.push(key.clone());
        self.media_by_part.insert(key, id);
        Some(id)
    }
    /// What a discarded read must give back: the budgets it charged and the media and kept-chart
    /// entries it added (see [`Imp::rollback`]).
    pub fn mark(&self) -> Mark {
        Mark {
            diagram_xml_bytes: self.diagram_xml_bytes,
            media: self.media.len(),
            media_keys: self.media_keys.len(),
            tag_bytes: self.tag_bytes,
            tags_capped: self.tags_capped,
            kept_sidecar_bytes: self.kept_sidecar_bytes,
            kept_chart_keys: self.kept_chart_keys.len(),
        }
    }
    /// Undo everything since `m`: only the entries added since are removed, so the cost follows
    /// what the discarded read added, not the size of the caches.
    pub fn rollback(&mut self, m: &Mark) {
        self.diagram_xml_bytes = m.diagram_xml_bytes;
        self.tag_bytes = m.tag_bytes;
        self.tags_capped = m.tags_capped;
        self.kept_sidecar_bytes = m.kept_sidecar_bytes;
        self.media.truncate(m.media);
        for k in self.media_keys.drain(m.media_keys..) {
            self.media_by_part.remove(&k);
        }
        for k in self.kept_chart_keys.drain(m.kept_chart_keys..) {
            self.kept_charts.remove(&k);
        }
        // Chart decode work (`chart_decode_bytes`, `chart_points`) stays charged: it was done, and
        // giving it back would let a discarded read repeat it. `rejected_kept` is keyed by the
        // retained total a refusal started from, so it stays valid after the rollback.
    }
    /// Media item for an external link.
    pub fn media_link(&mut self, url: &str) -> MediaId {
        if let Some(m) = self.media.iter().find(|m| m.link.as_deref() == Some(url)) {
            return m.id;
        }
        let id = MediaId(self.alloc());
        let name = url.rsplit('/').next().unwrap_or(url).to_string();
        let content_type = crate::mime_for(&name).to_string();
        self.media.push(MediaItem { id, name, content_type, data: Arc::new(vec![]), link: Some(url.to_string()) });
        id
    }
}

/// One part being read: its name, relationships and root namespace declarations.
pub struct Part {
    pub name: String,
    pub rels: Rels,
    pub ns: Vec<(String, String)>,
    /// Prefixes bound below the root only (on a wrapper such as `mc:Choice`), each to one namespace.
    pub inner_ns: Vec<(String, String)>,
    /// Bytes of namespace declarations this part may still copy onto kept fragments.
    ns_budget: Cell<usize>,
}

impl Part {
    pub fn new(pkg: &Package, name: &str, doc: &Doc) -> Self {
        let ns = doc.ns_decls();
        Part { name: name.to_string(), rels: pkg.rels(name), inner_ns: inner_decls(&doc.root, &ns), ns, ns_budget: Cell::new(MAX_COPIED_NS_BYTES) }
    }
    /// Serialize an element with the namespace declarations it needs from the part root.
    pub fn keep(&self, el: &El) -> String {
        keep_with(el, &[&self.ns], Some(&self.ns_budget))
    }
    /// Like [`Part::keep`], also declaring prefixes that only an enclosing wrapper binds.
    pub fn keep_inner(&self, el: &El) -> String {
        keep_with(el, &[&self.ns, &self.inner_ns], Some(&self.ns_budget))
    }
}

/// Prefixes declared below the root but not on it, skipping any bound to different namespaces.
fn inner_decls(root: &El, ns: &[(String, String)]) -> Vec<(String, String)> {
    fn rec(e: &El, out: &mut Vec<(String, String)>, out_map: &mut HashMap<String, String>, clash: &mut HashSet<String>, depth: usize) {
        if depth > crate::xml::MAX_DEPTH {
            return;
        }
        for (k, v) in e.attrs.iter().filter(|(k, _)| k.starts_with("xmlns:")) {
            if let Some(existing) = out_map.get(k) {
                if existing != v {
                    clash.insert(k.clone());
                }
            } else if out.len() < 1000 {
                out_map.insert(k.clone(), v.clone());
                out.push((k.clone(), v.clone()));
            }
        }
        for c in e.elements() {
            rec(c, out, out_map, clash, depth + 1);
        }
    }
    let mut out = vec![];
    let mut out_map = HashMap::new();
    let mut clash = HashSet::new();
    let root_ns: HashSet<&str> = ns.iter().map(|(r, _)| r.as_str()).collect();
    for c in root.elements() {
        rec(c, &mut out, &mut out_map, &mut clash, 1);
    }
    out.retain(|(k, _)| !clash.contains(k) && !root_ns.contains(k.as_str()));
    out
}

/// Longest namespace name copied onto a kept fragment or a resolved `mc` branch. Real ones are
/// URIs of well under 100 bytes; a longer one is not copied, so one declaration cannot be
/// multiplied by every fragment that uses its prefix.
const MAX_NS_VALUE: usize = 2048;

/// Namespace declaration bytes one part may copy onto all its kept fragments together; past it a
/// fragment keeps its markup but is not given further declarations.
const MAX_COPIED_NS_BYTES: usize = 8 << 20;

/// Prefixes `el` and its descendants use in element and attribute names, and those listed in
/// `mc:Ignorable` or `mc:MustUnderstand` (which must stay declared for the markup-compatibility rules to hold),
/// and those starting a QName-like attribute value.
fn used_prefixes(el: &El) -> HashSet<&str> {
    fn rec<'a>(e: &'a El, used: &mut HashSet<&'a str>, depth: usize) {
        if depth > crate::xml::MAX_DEPTH {
            return;
        }
        if let Some((p, _)) = e.name.split_once(':') {
            used.insert(p);
        }
        for (k, v) in &e.attrs {
            if let Some((p, local)) = k.split_once(':')
                && p != "xmlns"
                && p != "xml"
            {
                used.insert(p);
                if local == "Ignorable" || local == "MustUnderstand" {
                    used.extend(v.split_whitespace());
                }
            }
            // QName-valued attributes (`xsi:type="q:Item"`) need their prefix declared too.
            if k != "xmlns" && !k.starts_with("xmlns:") {
                for t in v.split_whitespace() {
                    if let Some((p, _)) = t.split_once(':')
                        && !p.is_empty()
                    {
                        used.insert(p);
                    }
                }
            }
        }
        for c in e.elements() {
            rec(c, used, depth + 1);
        }
    }
    let mut used = HashSet::new();
    rec(el, &mut used, 0);
    used
}

/// Serialize `el`, declaring every prefix it uses that the source root declared.
pub fn keep_xml(el: &El, ns: &[(String, String)]) -> String {
    keep_with(el, &[ns], None)
}

fn keep_with(el: &El, decls: &[&[(String, String)]], budget: Option<&Cell<usize>>) -> String {
    let used = used_prefixes(el);
    let mut have: HashSet<&str> = el.attrs.iter().map(|(a, _)| a.as_str()).collect();
    let mut extra = Vec::new();
    for (k, v) in decls.iter().flat_map(|d| d.iter()) {
        let p = k.strip_prefix("xmlns:").unwrap_or("");
        if !p.is_empty() && used.contains(p) && v.len() <= MAX_NS_VALUE && !have.contains(k.as_str()) {
            let cost = k.len() + v.len();
            if let Some(b) = budget {
                if b.get() < cost {
                    continue;
                }
                b.set(b.get() - cost);
            }
            have.insert(k);
            extra.push((k.clone(), v.clone()));
        }
    }
    let mut el = el.clone();
    el.attrs.extend(extra);
    el.to_xml()
}

/// Namespace prefixes whose `mc:Choice` content we understand.
const SUPPORTED_MC: [&str; 10] = ["p14", "p15", "p159", "a14", "a16", "p1510", "a15", "c14", "p188", "cx1"];

/// Office 2016 charts sit in a `cx1` choice; take it only for a layout DeckCraft reads (the
/// fallback is a picture or "this chart isn't available" text). The part is checked later, when
/// the frame is read, so here only the namespace counts.
fn chartex_readable(ch: &El) -> bool {
    let mut found = vec![];
    ch.find_all("graphicData", &mut found);
    found.iter().any(|g| g.attr("uri").is_some_and(|u| u.ends_with("/chartex")))
}

/// A relationship to an embedded 3-D model (`.glb`).
pub(crate) fn is_model3d(rel: &opc::Rel) -> bool {
    !rel.external && (rel.kind == "model3d" || rel.target.to_ascii_lowercase().ends_with(".glb"))
}

fn choice_has_model3d(el: &El, rels: &Rels) -> bool {
    fn rec(el: &El, rels: &Rels, depth: usize) -> bool {
        if depth > 16 {
            return false;
        }
        if el.is("contentPart")
            && let Some(id) = el.attr("r:id").filter(|s| !s.is_empty())
            && rels.get(id).is_some_and(is_model3d)
        {
            return true;
        }
        el.elements().any(|c| rec(c, rels, depth + 1))
    }
    rec(el, rels, 0)
}

/// Bytes of tags one import copies into the model, every tags part and reference together: a
/// small compressed tags part listed by many shapes, or many times by one, must not grow without
/// bound (#1164). The package budgets (`opc::MAX_XML_PART`, `MAX_TOTAL`, #1283) bound what is
/// parsed; this bounds what is copied from it.
pub const MAX_TAG_BYTES: usize = 64 << 20;
/// What each copied pair costs besides its text, so empty pairs count too.
const TAG_PAIR_COST: usize = std::mem::size_of::<(String, String)>();

/// Add-in tags named by `holder`'s `p:custDataLst`: the name/value pairs of each tags part.
/// Each part is parsed once per import and counted once per holder. Once [`MAX_TAG_BYTES`] is
/// reached, no further tag parts are parsed or cached (#1164).
pub fn tags(imp: &mut Imp, part: &Part, holder: &El) -> Vec<(String, String)> {
    if imp.tags_capped {
        return vec![];
    }
    let Some(list) = holder.child("custDataLst") else { return vec![] };
    let mut out = Vec::new();
    let mut seen = HashSet::new();
    for t in list.children_named("tags").take(100) {
        if imp.tags_capped {
            return out;
        }
        let Some(target) = t.attr("r:id").and_then(|id| part.rels.get(id)).map(|r| opc::norm(&r.target)) else { continue };
        if !seen.insert(target.clone()) {
            continue;
        }
        let parsed = match imp.tags_by_part.get(&target) {
            Some(p) => p.clone(),
            None => {
                if imp.tags_capped {
                    return out;
                }
                let p: Arc<[(String, String)]> = imp
                    .pkg
                    .xml(&target)
                    .map(|doc| {
                        doc.root
                            .children_named("tag")
                            .take(10_000)
                            .filter_map(|tag| Some((tag.attr("name")?.to_string(), tag.attr("val").unwrap_or("").to_string())))
                            .collect()
                    })
                    .unwrap_or_default();
                imp.tags_by_part.insert(target, p.clone());
                p
            }
        };
        for (name, val) in parsed.iter() {
            let n = imp.tag_bytes.saturating_add(TAG_PAIR_COST + name.len() + val.len());
            if n > MAX_TAG_BYTES {
                if !imp.tags_capped {
                    log::warn!("pptx: add-in tags over {MAX_TAG_BYTES} bytes; the rest are dropped");
                    imp.tags_capped = true;
                }
                return out;
            }
            imp.tag_bytes = n;
            out.push((name.clone(), val.clone()));
        }
    }
    out
}

/// Relationship types whose parts are kept verbatim, and whether they hang off the package root.
const KEPT_RELS: [(&str, bool); 3] = [
    ("http://schemas.openxmlformats.org/officeDocument/2006/relationships/customXml", false),
    ("http://schemas.microsoft.com/office/2020/02/relationships/classificationlabels", true),
    ("http://schemas.openxmlformats.org/officeDocument/2006/relationships/custom-properties", true),
];

/// A part we may keep: outside `ppt/` and the properties the writer makes itself.
fn keepable(name: &str) -> bool {
    let n = name.to_ascii_lowercase();
    !n.is_empty()
        && !n.contains("..")
        && !n.starts_with("ppt/")
        && n != "docprops/core.xml"
        && n != "docprops/app.xml"
        && !n.starts_with("[content_types]")
}

/// Custom XML data, sensitivity labels and custom properties, with the parts they relate to
/// (`itemProps`) and their relationships parts, as written.
fn kept_parts(pkg: &Package, pres_path: &str) -> Vec<deckcraft_model::KeptPart> {
    use deckcraft_model::KeptPart;
    let mut out: Vec<KeptPart> = Vec::new();
    let text = |name: &str| pkg.get(name).and_then(|b| std::str::from_utf8(b).ok()).map(str::to_string);
    for (holder, from_root) in [("", true), (pres_path, false)] {
        let Some(doc) = pkg.xml(&opc::rels_path(holder)) else { continue };
        let base = opc::dir_of(holder);
        for r in doc.root.children_named("Relationship") {
            let (Some(ty), Some(target)) = (r.attr("Type"), r.attr("Target")) else { continue };
            if r.attr("TargetMode").is_some_and(|m| m.eq_ignore_ascii_case("external"))
                || !KEPT_RELS.iter().any(|(t, root)| *t == ty && *root == from_root)
            {
                continue;
            }
            let name = opc::resolve(&base, target);
            if !keepable(&name) || out.iter().any(|k| k.name.eq_ignore_ascii_case(&name)) || out.len() >= 400 {
                continue;
            }
            let Some(xml) = text(&name) else { continue };
            out.push(KeptPart {
                content_type: pkg.content_type(&name).unwrap_or_default(),
                name: name.clone(),
                xml,
                rel_type: ty.to_string(),
                from_root,
            });
            // The part's own relationships (customXml item → itemProps) and their targets.
            let rp = opc::rels_path(&name);
            if let Some(rels_xml) = text(&rp) {
                let mut capped = false;
                for sub in pkg.rels(&name).items.iter().filter(|s| !s.external && keepable(&s.target)) {
                    // Checked before the part is read: repeated relationships to one large part
                    // must not copy it again each time.
                    if out.iter().any(|k| k.name.eq_ignore_ascii_case(&sub.target)) {
                        continue;
                    }
                    if out.len() >= 400 {
                        capped = true;
                        continue;
                    }
                    if let Some(x) = text(&sub.target) {
                        out.push(KeptPart {
                            content_type: pkg.content_type(&sub.target).unwrap_or_default(),
                            name: sub.target.clone(),
                            xml: x,
                            ..Default::default()
                        });
                    }
                }
                if !capped && out.len() < 400 {
                    out.push(KeptPart { name: rp, xml: rels_xml, ..Default::default() });
                }
            }
        }
    }
    out
}

/// Replace every `mc:AlternateContent` by the children of the branch we can read best.
/// A 3-D model choice is left in place (even when its `Requires` prefix is not one we otherwise
/// understand) so the shape reader can keep the model and its fallback picture. Ink content parts
/// still fall through to the fallback picture.
pub fn resolve_mc(el: &mut El, depth: usize) {
    resolve_mc_rels(el, depth, None);
}

fn resolve_mc_rels(el: &mut El, depth: usize, rels: Option<&Rels>) {
    if depth > crate::xml::MAX_DEPTH {
        return;
    }
    if el.children.iter().any(|c| matches!(c, Node::El(e) if e.is("AlternateContent"))) {
        let mut out = Vec::with_capacity(el.children.len());
        for c in std::mem::take(&mut el.children) {
            match c {
                Node::El(ac) if ac.is("AlternateContent") => {
                    if rels.is_some_and(|rels| ac.children_named("Choice").any(|ch| choice_has_model3d(ch, rels))) {
                        out.push(Node::El(ac));
                        continue;
                    }
                    let choice = ac.children_named("Choice").find(|ch| {
                        let req_ok = ch.attr("Requires").unwrap_or("").split_whitespace().all(|r| SUPPORTED_MC.contains(&r));
                        // Ink content parts are not modelled; prefer their fallback picture.
                        let modelled = !ch.elements().any(|e| e.is("contentPart"))
                            && (!ch.attr("Requires").unwrap_or("").contains("cx1") || chartex_readable(ch));
                        req_ok && modelled
                    });
                    let branch = choice.or_else(|| ac.child("Fallback"));
                    if let Some(b) = branch {
                        // The branch's namespace declarations (the first usable one of each name,
                        // in order), indexed by prefix once: each child then looks up the prefixes
                        // it uses instead of scanning every declaration.
                        let mut decls: Vec<(&String, &String)> = Vec::new();
                        // An oversized declaration still shadows an outer one of its name: its
                        // content is left unbound rather than bound to the outer namespace.
                        let mut by_prefix: HashMap<&str, Option<usize>> = HashMap::new();
                        for (k, v) in b.attrs.iter().chain(ac.attrs.iter()) {
                            let prefix = if k == "xmlns" { Some("") } else { k.strip_prefix("xmlns:") };
                            if let Some(p) = prefix
                                && !by_prefix.contains_key(p)
                            {
                                by_prefix.insert(p, (v.len() <= MAX_NS_VALUE).then_some(decls.len()));
                                if v.len() <= MAX_NS_VALUE {
                                    decls.push((k, v));
                                }
                            }
                        }
                        for n in &b.children {
                            if let Node::El(e) = n {
                                // Carry the namespace declarations from the branch that its content
                                // uses (all of them per child made children x declarations copies).
                                let used = used_prefixes(e);
                                let have: HashSet<&str> = e.attrs.iter().map(|(a, _)| a.as_str()).collect();
                                let mut wanted: Vec<usize> = std::iter::once("")
                                    .chain(used.iter().copied())
                                    .filter_map(|p| by_prefix.get(p).copied().flatten())
                                    .filter(|&i| !have.contains(decls[i].0.as_str()))
                                    .collect();
                                wanted.sort_unstable();
                                wanted.dedup();
                                let mut e = e.clone();
                                e.attrs.extend(wanted.into_iter().map(|i| (decls[i].0.clone(), decls[i].1.clone())));
                                out.push(Node::El(e));
                            }
                        }
                    }
                }
                other => out.push(other),
            }
        }
        el.children = out;
    }
    for c in el.elements_mut() {
        resolve_mc_rels(c, depth + 1, rels);
    }
}

fn load(pkg: &Package, name: &str) -> Option<Doc> {
    let mut d = pkg.xml(name)?;
    let rels = pkg.rels(name);
    resolve_mc_rels(&mut d.root, 0, Some(&rels));
    Some(d)
}

fn max_cnvpr(el: &El, m: &mut u32) {
    let mut v = vec![];
    el.find_all("cNvPr", &mut v);
    for c in v {
        if let Some(id) = c.u32("id")
            && id < shapes::MAX_KEPT_ID
        {
            *m = (*m).max(id);
        }
    }
}

/// The theme of a `.thmx` theme file (its `officeDocument` is a theme part), or of the first
/// master of a `.pptx` / `.potx`, with the media its format scheme uses (ids from 1).
pub fn import_theme(bytes: &[u8]) -> Result<(deckcraft_model::theme::Theme, Vec<MediaItem>), PptxError> {
    let pkg = Package::open(bytes)?;
    let target = pkg.rels("").first_of("officeDocument").map(|r| r.target.clone());
    let theme_path = match &target {
        Some(t) if pkg.xml(t).is_some_and(|d| d.root.is("theme")) => t.clone(),
        _ => {
            // A presentation: its first master's theme.
            let pres = target.unwrap_or_else(|| "ppt/presentation.xml".into());
            let pres_doc = load(&pkg, &pres).ok_or_else(|| PptxError::NotPptx("neither a theme nor a presentation".into()))?;
            let pres_part = Part::new(&pkg, &pres, &pres_doc);
            let master = pres_doc
                .root
                .child("sldMasterIdLst")
                .and_then(|l| l.children_named("sldMasterId").next())
                .and_then(|m| pres_part.rels.target(m.attr("r:id").unwrap_or("")).map(String::from))
                .or_else(|| pres_part.rels.all_of("slideMaster").next().map(|r| r.target.clone()))
                .ok_or_else(|| PptxError::NotPptx("the presentation has no slide master".into()))?;
            pkg.rels(&master).first_of("theme").map(|r| r.target.clone()).ok_or_else(|| PptxError::NotPptx("the slide master has no theme".into()))?
        }
    };
    let doc = load(&pkg, &theme_path).ok_or_else(|| PptxError::NotPptx(format!("missing or unreadable {theme_path}")))?;
    if !doc.root.is("theme") {
        return Err(PptxError::NotPptx(format!("{theme_path} is not a theme part")));
    }
    let mut imp = Imp {
        pkg: &pkg,
        media: vec![],
        media_by_part: HashMap::new(),
        media_keys: vec![],
        next: 0,
        slide_by_part: HashMap::new(),
        custom_show_names: HashMap::new(),
        table_style_ids: Vec::new(),
        vml_previews: HashMap::new(),
        kept_sidecar_bytes: 0,
        chart_points: 0,
        chart_points_cap: chart::MAX_PRESENTATION_CHART_POINTS,
        kept_charts: HashMap::new(),
        kept_chart_keys: vec![],
        rejected_kept: HashMap::new(),
        chart_decode_bytes: 0,
        tags_by_part: HashMap::new(),
        tag_bytes: 0,
        tags_capped: false,
        warnings: vec![],
        theme_extra_bytes: 0,
        smartart_shapes: 0,
        diagram_xml_bytes: 0,
        has_rels: HashMap::new(),
    };
    let part = Part::new(&pkg, &theme_path, &doc);
    let theme = theme::read_theme(&mut imp, &part, &doc.root);
    Ok((theme, imp.media))
}

pub fn import(bytes: &[u8]) -> Result<Presentation, PptxError> {
    import_checked(bytes).map(|(p, _)| p)
}

/// [`import`], plus the slides the file's slide list names but that couldn't be read (a missing
/// or truncated slide part, or an entry whose relationship is missing): those slides are left
/// out, so a caller can say so (#203).
pub fn import_checked(bytes: &[u8]) -> Result<(Presentation, Vec<String>), PptxError> {
    import_report(bytes).map(|(p, lost, _)| (p, lost))
}

/// [`import_checked`], plus warnings for content the file had that was cut to fit a limit (a
/// table past the cell cap keeps its leading rows).
pub fn import_report(bytes: &[u8]) -> Result<(Presentation, Vec<String>, Vec<String>), PptxError> {
    import_report_with_chart_points(bytes, chart::MAX_PRESENTATION_CHART_POINTS)
}

const MAX_SLIDE_ENTRIES: usize = 10_000;

/// [`import_checked`] with the presentation's chart point budget set (tests lower it).
pub(crate) fn import_with_chart_points(bytes: &[u8], chart_points_cap: usize) -> Result<(Presentation, Vec<String>), PptxError> {
    import_report_with_chart_points(bytes, chart_points_cap).map(|(p, lost, _)| (p, lost))
}

/// [`import_report`] with the presentation's chart point budget set.
fn import_report_with_chart_points(bytes: &[u8], chart_points_cap: usize) -> Result<(Presentation, Vec<String>, Vec<String>), PptxError> {
    let mut lost_slides: Vec<String> = vec![];
    let pkg = Package::open(bytes)?;
    let root_rels = pkg.rels("");
    let pres_path = root_rels.first_of("officeDocument").map(|r| r.target.clone()).unwrap_or_else(|| "ppt/presentation.xml".into());
    let pres_doc = load(&pkg, &pres_path).ok_or_else(|| PptxError::NotPptx(format!("missing or unreadable {pres_path}")))?;
    let pres_el = &pres_doc.root;
    if !pres_el.is("presentation") {
        return Err(PptxError::NotPptx(format!("{pres_path} is not a presentation part")));
    }
    // Refuse an oversized list before reading slide parts: truncating it would look like a
    // complete import and allow a later save to overwrite the omitted slides (#1910).
    // Looking only for the first entry past the cap keeps this check bounded.
    if pres_el.child("sldIdLst").is_some_and(|list| list.children_named("sldId").nth(MAX_SLIDE_ENTRIES).is_some()) {
        return Err(PptxError::Unsupported(format!("PPTX slide list exceeds the {MAX_SLIDE_ENTRIES}-entry import limit")));
    }
    let pres_part = Part::new(&pkg, &pres_path, &pres_doc);

    let (master_paths, slide_entries) = master_and_slide_paths(pres_el, &pres_part, &mut lost_slides);
    let (docs, max_id) = load_part_docs(&pkg, &master_paths, &slide_entries);

    let mut imp = Imp {
        pkg: &pkg,
        media: vec![],
        media_by_part: HashMap::new(),
        media_keys: vec![],
        next: max_id.max(1),
        slide_by_part: HashMap::new(),
        custom_show_names: HashMap::new(),
        table_style_ids: Vec::new(),
        vml_previews: HashMap::new(),
        kept_sidecar_bytes: 0,
        chart_points: 0,
        chart_points_cap,
        kept_charts: HashMap::new(),
        kept_chart_keys: vec![],
        rejected_kept: HashMap::new(),
        chart_decode_bytes: 0,
        tags_by_part: HashMap::new(),
        tag_bytes: 0,
        tags_capped: false,
        warnings: vec![],
        theme_extra_bytes: 0,
        smartart_shapes: 0,
        diagram_xml_bytes: 0,
        has_rels: HashMap::new(),
    };
    // Slide ids first so hyperlinks anywhere can point at slides.
    let slide_ids = register_slides(&mut imp, &docs, &slide_entries, &mut lost_slides);
    read_custom_show_names(&mut imp, pres_el);

    let mut p = defaults::blank_presentation(defaults::WIDE, Default::default(), false);
    p.masters.clear();
    p.media.clear();
    p.default_text_style = Default::default();

    read_presentation_settings(&mut imp, &mut p, &pres_part, pres_el);
    let layout_by_part = read_masters(&mut imp, &mut p, &master_paths, &docs);
    let file_slide_ids = read_slides(&mut imp, &mut p, &pres_part, &docs, &slide_ids, &layout_by_part);
    read_sections(&mut p, &pres_part, pres_el, &file_slide_ids);
    p.tags = tags(&mut imp, &pres_part, pres_el);
    read_custom_shows(&mut p, &imp, &pres_part, pres_el);
    read_guides_and_show(&mut p, &imp, &pres_part);
    read_notes_master(&mut imp, &mut p, &pres_part);
    read_handout_master(&mut imp, &mut p, &pres_part);
    read_document_properties(&mut p, &pkg, &root_rels);

    p.kept_parts = kept_parts(&pkg, &pres_path);

    inherit_placeholder_geometry(&mut p);
    default_text_anchor(&mut p);
    p.header_footer = header_footer(&p);
    p.embedded_fonts = read_embedded_fonts(&mut imp, &pres_part, pres_el);
    p.media = std::mem::take(&mut imp.media);
    p.next_id = imp.next;
    p.fix_next_id();
    Ok((p, lost_slides, std::mem::take(&mut imp.warnings)))
}

/// Masters, layouts and slides to read, in file order and without duplicates: (master paths,
/// (file slide id, slide path)).
fn master_and_slide_paths(pres_el: &El, pres_part: &Part, lost_slides: &mut Vec<String>) -> (Vec<String>, Vec<(u32, String)>) {
    let master_paths: Vec<String> = pres_el
        .child("sldMasterIdLst")
        .map(|l| l.children_named("sldMasterId").filter_map(|m| pres_part.rels.target(m.attr("r:id").unwrap_or(""))).map(String::from).collect())
        .unwrap_or_default();
    let mut master_paths: Vec<String> =
        if master_paths.is_empty() { pres_part.rels.all_of("slideMaster").map(|r| r.target.clone()).collect() } else { master_paths };
    let mut slide_entries: Vec<(u32, String)> = pres_el
        .child("sldIdLst")
        .map(|l| {
            l.children_named("sldId")
                .take(MAX_SLIDE_ENTRIES)
                .filter_map(|s| {
                    let rid = s.attr("r:id").unwrap_or("");
                    let Some(path) = pres_part.rels.target(rid) else {
                        // A missing relationship still represents a lost slide. Report it so
                        // the engine opens a repaired copy instead of overwriting the original.
                        lost_slides.push(format!("slide {} (missing relationship {rid})", s.u32("id").unwrap_or(0)));
                        return None;
                    };
                    Some((s.u32("id").unwrap_or(0), path.to_string()))
                })
                .collect()
        })
        .unwrap_or_default();
    let mut seen_masters = HashSet::new();
    master_paths.retain(|m| seen_masters.insert(opc::norm(m)));
    let mut seen_slides = HashSet::new();
    slide_entries.retain(|(_, p)| seen_slides.insert(opc::norm(p)));
    (master_paths, slide_entries)
}

/// Loads every master, layout and slide part once. Returns them by normalized path and the
/// largest shape id found in them.
fn load_part_docs(pkg: &Package, master_paths: &[String], slide_entries: &[(u32, String)]) -> (HashMap<String, Doc>, u32) {
    let mut all_parts: Vec<String> = master_paths.to_vec();
    let mut seen_layouts = HashSet::new();
    for m in master_paths {
        for r in pkg.rels(m).all_of("slideLayout") {
            let key = opc::norm(&r.target);
            if seen_layouts.insert(key) {
                all_parts.push(r.target.clone());
            }
        }
    }
    all_parts.extend(slide_entries.iter().map(|(_, p)| p.clone()));
    let mut docs: HashMap<String, Doc> = HashMap::new();
    let mut max_id = 0u32;
    for p in &all_parts {
        let key = opc::norm(p);
        if docs.contains_key(&key) {
            continue;
        }
        if let Some(d) = load(pkg, p) {
            max_cnvpr(&d.root, &mut max_id);
            docs.insert(key, d);
        }
    }
    (docs, max_id)
}

/// Allocates an id for every readable slide; slides that are missing or unreadable are recorded in
/// `lost_slides` and left out.
fn register_slides(
    imp: &mut Imp,
    docs: &HashMap<String, Doc>,
    slide_entries: &[(u32, String)],
    lost_slides: &mut Vec<String>,
) -> Vec<(u32, String, SlideId)> {
    let mut slide_ids: Vec<(u32, String, SlideId)> = vec![];
    for (file_id, path) in slide_entries {
        if !docs.contains_key(&opc::norm(path)) {
            log::warn!("pptx: slide {path} is missing or unreadable; skipped");
            lost_slides.push(path.clone());
            continue;
        }
        let id = SlideId(imp.alloc());
        imp.slide_by_part.insert(opc::norm(path), id);
        slide_ids.push((*file_id, path.clone(), id));
    }
    slide_ids
}

fn read_custom_show_names(imp: &mut Imp, pres_el: &El) {
    if let Some(l) = pres_el.child("custShowLst") {
        for cs in l.children_named("custShow") {
            if let (Some(id), Some(name)) = (cs.attr("id"), cs.attr("name")) {
                imp.custom_show_names.insert(id.to_string(), name.to_string());
            }
        }
    }
}

/// Slide and notes size, first slide number, default text style and table styles.
fn read_presentation_settings(imp: &mut Imp, p: &mut Presentation, pres_part: &Part, pres_el: &El) {
    if let Some(sz) = pres_el.child("sldSz") {
        let w = sz.i64("cx").map(emu_to_pt).unwrap_or(960.0);
        let h = sz.i64("cy").map(emu_to_pt).unwrap_or(540.0);
        p.slide_size = Size::new(sane_len(w, 960.0), sane_len(h, 540.0));
    }
    if let Some(sz) = pres_el.child("notesSz") {
        let w = sz.i64("cx").map(emu_to_pt).unwrap_or(540.0);
        let h = sz.i64("cy").map(emu_to_pt).unwrap_or(720.0);
        p.notes_size = Size::new(sane_len(w, 540.0), sane_len(h, 720.0));
    }
    p.first_slide_number = pres_el.u32("firstSlideNum").unwrap_or(1).min(9999);
    if let Some(dts) = pres_el.child("defaultTextStyle") {
        p.default_text_style = dml::list_style(imp, pres_part, dts);
    }
    if let Some(r) = pres_part.rels.first_of("tableStyles")
        && let Some(d) = load(imp.pkg, &r.target)
    {
        let part = Part::new(imp.pkg, &r.target, &d);
        p.table_styles = table_styles(imp, &part, &d.root);
        imp.table_style_ids = p.table_styles.iter().map(|s| s.id.clone()).collect();
    }
}

/// Reads the slide masters and their layouts; a file without a readable master gets a default one.
fn read_masters(imp: &mut Imp, p: &mut Presentation, master_paths: &[String], docs: &HashMap<String, Doc>) -> HashMap<String, LayoutId> {
    let mut layout_by_part: HashMap<String, LayoutId> = HashMap::new();
    for mp in master_paths {
        let Some(doc) = docs.get(&opc::norm(mp)) else {
            log::warn!("pptx: master {mp} missing; skipped");
            continue;
        };
        let master = read_master(imp, mp, doc, docs, &mut layout_by_part);
        p.masters.push(Arc::new(master));
    }
    if p.masters.is_empty() {
        log::warn!("pptx: no readable slide master; using a default one");
        let (m, _) = defaults::build_master(p.slide_size, Default::default(), imp.next);
        imp.next = imp.next.saturating_add(200);
        p.masters.push(Arc::new(m));
    }
    layout_by_part
}

/// Reads every registered slide with its notes and comments. Returns the slide ids by file id.
fn read_slides(
    imp: &mut Imp,
    p: &mut Presentation,
    pres_part: &Part,
    docs: &HashMap<String, Doc>,
    slide_ids: &[(u32, String, SlideId)],
    layout_by_part: &HashMap<String, LayoutId>,
) -> HashMap<u32, SlideId> {
    let pkg = imp.pkg;
    let fallback_layout = p.masters.first().and_then(|m| m.layouts.first()).map(|l| l.id).unwrap_or_default();
    let mut file_slide_ids: HashMap<u32, SlideId> = HashMap::new();
    // A notes or comments part belongs to one slide; one shared by many must not be read (and
    // copied) once per slide that names it.
    let mut owned_parts: HashSet<String> = HashSet::new();
    for (file_id, path, id) in slide_ids {
        let Some(doc) = docs.get(&opc::norm(path)) else { continue };
        let part = Part::new(pkg, path, doc);
        let layout = part.rels.first_of("slideLayout").and_then(|r| layout_by_part.get(&opc::norm(&r.target)).copied()).unwrap_or(fallback_layout);
        let mut slide = read_slide(imp, &part, doc, *id, layout);
        if let Some(notes) = slide_notes(imp, &part, &mut owned_parts) {
            slide.notes = notes;
            slide.has_notes_slide = true;
        }
        read_slide_comments(pkg, pres_part, &part, &mut slide, &mut owned_parts);
        file_slide_ids.insert(*file_id, *id);
        p.slides.push(Arc::new(slide));
    }
    file_slide_ids
}

/// The slide's notes text. A notes part is the notes of the first slide that names it.
fn slide_notes(imp: &mut Imp, part: &Part, owned: &mut HashSet<String>) -> Option<TextBody> {
    let n = part.rels.first_of("notesSlide")?;
    if !owned.insert(opc::norm(&n.target)) {
        log::warn!("pptx: notes part {} is named by more than one slide; kept on the first", n.target);
        return None;
    }
    let pkg = imp.pkg;
    let nd = load(pkg, &n.target)?;
    let np = Part::new(pkg, &n.target, &nd);
    Some(read_notes(imp, &np, &nd.root))
}

/// Comments. A modern part and the legacy part can describe the same threads (PowerPoint
/// writes both): the modern one wins, its flattened legacy copy is skipped.
/// Each comments part is read once, for the first slide that names it.
fn read_slide_comments(pkg: &Package, pres_part: &Part, part: &Part, slide: &mut Slide, owned: &mut HashSet<String>) {
    let mut parts: Vec<(Doc, bool, bool)> = vec![];
    for c in part.rels.all_of("comments") {
        // An already-owned part is not re-read, but its kind still decides modern precedence.
        let fresh = owned.insert(opc::norm(&c.target));
        if let Some(cd) = pkg.xml(&c.target) {
            // The content type names the modern part; a package that types it only through a
            // Default entry instead of an Override is still modern when its root is p188.
            let modern = pkg.content_type(&c.target).as_deref() == Some(crate::write::CT_COMMENTS_MODERN) || cd.root.prefix() == "p188";
            parts.push((cd, modern, fresh));
        }
    }
    let has_modern = parts.iter().any(|(_, m, _)| *m);
    for (cd, modern, fresh) in parts {
        if !fresh || (has_modern && !modern) {
            continue;
        }
        slide.comments.extend(read_comments(pkg, pres_part, &cd.root, modern));
    }
}

/// Sections, and the extension elements the model does not understand (kept verbatim).
fn read_sections(p: &mut Presentation, pres_part: &Part, pres_el: &El, file_slide_ids: &HashMap<u32, SlideId>) {
    let Some(ext) = pres_el.child("extLst") else { return };
    if let Some(sl) = ext.find("sectionLst") {
        for s in sl.children_named("section").take(10_000) {
            let slides = s
                .child("sldIdLst")
                .map(|l| l.children_named("sldId").filter_map(|x| x.u32("id").and_then(|i| file_slide_ids.get(&i).copied())).collect())
                .unwrap_or_default();
            p.sections.push(Section { name: s.attr("name").unwrap_or("").to_string(), slides });
        }
    }
    let kept: String =
        ext.children_named("ext").filter(|e| e.attr("uri") != Some(crate::SECTION_EXT_URI) && !has_rel_refs(e)).map(|e| pres_part.keep(e)).collect();
    if !kept.is_empty() {
        p.raw_ext = Some(kept);
    }
}

fn read_custom_shows(p: &mut Presentation, imp: &Imp, pres_part: &Part, pres_el: &El) {
    let Some(l) = pres_el.child("custShowLst") else { return };
    for cs in l.children_named("custShow") {
        let slides = cs
            .child("sldLst")
            .map(|l| {
                l.children_named("sld")
                    .filter_map(|s| pres_part.rels.target(s.attr("r:id").unwrap_or("")))
                    .filter_map(|t| imp.slide_by_part.get(&opc::norm(t)).copied())
                    .collect()
            })
            .unwrap_or_default();
        p.custom_shows.push(CustomShow { name: cs.attr("name").unwrap_or("").to_string(), slides });
    }
}

/// Drawing guides (eighths of a point) and slide show settings.
fn read_guides_and_show(p: &mut Presentation, imp: &Imp, pres_part: &Part) {
    let pkg = imp.pkg;
    if let Some(r) = pres_part.rels.first_of("viewProps")
        && let Some(d) = pkg.xml(&r.target)
        && let Some(lst) = d.root.find("slideViewPr").and_then(|v| v.find("guideLst"))
    {
        p.guides = lst
            .children_named("guide")
            .filter_map(|g| {
                let pos = g.attr("pos").and_then(|v| v.parse::<f64>().ok()).unwrap_or(0.0) / 8.0;
                pos.is_finite().then_some(deckcraft_model::DrawGuide { vertical: g.attr("orient") != Some("horz"), pos })
            })
            .take(1000)
            .collect();
    }
    if let Some(r) = pres_part.rels.first_of("presProps")
        && let Some(d) = pkg.xml(&r.target)
        && let Some(sp) = d.root.child("showPr")
    {
        p.show = read_show(sp, &imp.custom_show_names);
    }
}

/// Theme, background, shapes and colour map shared by the notes and handout masters.
fn read_aux_master(imp: &mut Imp, part: &Part, doc: &Doc, m: &mut Master) {
    let mut ctx = shapes::IdCtx::default();
    if let Some(csld) = doc.root.child("cSld") {
        m.background = background(imp, part, csld);
        if let Some(tree) = csld.child("spTree") {
            m.shapes = shapes::sp_tree(imp, part, &mut ctx, tree, 0);
        }
    }
    if let Some(cm) = doc.root.child("clrMap") {
        m.color_map = color_map(cm);
    }
}

/// Reads the part's own theme into the master, if it has one.
fn read_master_theme(imp: &mut Imp, part: &Part, m: &mut Master) -> bool {
    let pkg = imp.pkg;
    if let Some(t) = part.rels.first_of("theme")
        && let Some(td) = pkg.xml(&t.target)
    {
        let tp = Part::new(pkg, &t.target, &td);
        m.theme = theme::read_theme(imp, &tp, &td.root);
        return true;
    }
    false
}

fn read_notes_master(imp: &mut Imp, p: &mut Presentation, pres_part: &Part) {
    let pkg = imp.pkg;
    let Some(r) = pres_part.rels.first_of("notesMaster") else { return };
    let Some(d) = load(pkg, &r.target) else { return };
    let part = Part::new(pkg, &r.target, &d);
    let mut m = Master { id: MasterId(imp.alloc()), name: "Notes Master".into(), ..Default::default() };
    read_master_theme(imp, &part, &mut m);
    read_aux_master(imp, &part, &d, &mut m);
    // Notes text styles are the body's list style; slide masters use title/body/other instead.
    if let Some(ns) = d.root.child("notesStyle") {
        m.body_style = dml::list_style(imp, &part, ns);
    }
    p.notes_master = Some(Arc::new(m));
}

/// Handout master (header, footer, date and slide number for printed handouts).
fn read_handout_master(imp: &mut Imp, p: &mut Presentation, pres_part: &Part) {
    let pkg = imp.pkg;
    let Some(r) = pres_part.rels.first_of("handoutMaster") else { return };
    let Some(d) = load(pkg, &r.target) else { return };
    let part = Part::new(pkg, &r.target, &d);
    let mut m = Master { id: MasterId(imp.alloc()), name: "Handout Master".into(), ..Default::default() };
    if !read_master_theme(imp, &part, &mut m)
        && let Some(first) = p.masters.first()
    {
        m.theme = first.theme.clone();
    }
    if let Some(n) = d.root.child("cSld").and_then(|c| c.attr("name")).filter(|s| !s.is_empty()) {
        m.name = n.to_string();
    }
    read_aux_master(imp, &part, &d, &mut m);
    p.handout_master = Some(Arc::new(m));
}

fn read_document_properties(p: &mut Presentation, pkg: &Package, root_rels: &Rels) {
    if let Some(r) = root_rels.first_of("core-properties")
        && let Some(d) = pkg.xml(&r.target)
    {
        read_core(&d.root, &mut p.props);
    }
    if let Some(r) = root_rels.first_of("extended-properties")
        && let Some(d) = pkg.xml(&r.target)
    {
        p.props.company = d.root.child("Company").map(|c| c.text()).unwrap_or_default();
    }
}

/// Embedded font faces in one file. Past this, further typefaces are dropped.
const MAX_EMBEDDED_FONTS: usize = 64;
/// One font part. A larger part is skipped; the rest of the file is still read.
const MAX_FONT_BYTES: usize = 32 * 1024 * 1024;

/// `p:embeddedFontLst`: each typeface and the font parts its four face slots point at.
fn read_embedded_fonts(imp: &mut Imp, pres: &Part, root: &El) -> Vec<EmbeddedFont> {
    let Some(list) = root.child("embeddedFontLst") else { return Vec::new() };
    let mut out = Vec::new();
    for e in list.children_named("embeddedFont").take(MAX_EMBEDDED_FONTS) {
        let Some(font) = e.child("font") else { continue };
        let Some(typeface) = font.attr("typeface").map(str::trim).filter(|t| !t.is_empty()) else { continue };
        let typeface: String = typeface.chars().take(255).collect();
        let slot = |imp: &mut Imp, name: &str| -> Option<MediaId> {
            let id = e.child(name)?.attr("r:id")?;
            let part = pres.rels.target(id)?;
            let data = imp.pkg.get(part)?;
            if data.is_empty() || data.len() > MAX_FONT_BYTES {
                log::warn!("pptx: embedded font {part} skipped ({} bytes)", data.len());
                return None;
            }
            imp.media_for(part)
        };
        let regular = slot(imp, "regular");
        let bold = slot(imp, "bold");
        let italic = slot(imp, "italic");
        let bold_italic = slot(imp, "boldItalic");
        if regular.is_none() && bold.is_none() && italic.is_none() && bold_italic.is_none() {
            continue;
        }
        out.push(EmbeddedFont {
            typeface,
            panose: panose_attr(font),
            pitch_family: byte_attr(font, "pitchFamily"),
            charset: byte_attr(font, "charset"),
            regular,
            bold,
            italic,
            bold_italic,
        });
    }
    out
}

fn byte_attr(el: &El, name: &str) -> Option<u8> {
    u8::try_from(el.u32(name)?).ok()
}

/// `panose` is 20 hex digits (ST_Panose). Anything else is dropped.
fn panose_attr(el: &El) -> Option<String> {
    let v = el.attr("panose")?.trim();
    (v.len() == 20 && v.chars().all(|c| c.is_ascii_hexdigit())).then(|| v.to_string())
}

fn sane_len(v: f64, dflt: f64) -> f64 {
    if v.is_finite() && (1.0..=20_000.0).contains(&v) { v } else { dflt }
}

/// Does the element (or a descendant) reference a relationship?
pub fn has_rel_refs(el: &El) -> bool {
    !rel_refs(el).is_empty()
}

/// Is this attribute a relationship id (`r:id`, `r:embed`, `r:dm`…)?
pub fn is_rel_attr(k: &str, v: &str) -> bool {
    !k.starts_with("xmlns")
        && k.contains(':')
        && matches!(k.rsplit(':').next(), Some("id" | "embed" | "link" | "dm" | "lo" | "qs" | "cs" | "pict" | "href"))
        && !v.is_empty()
}

/// Every relationship id `el` and its descendants use, sorted and without repeats.
pub fn rel_refs(el: &El) -> Vec<String> {
    fn rec(e: &El, out: &mut Vec<String>, depth: usize) {
        if depth > crate::xml::MAX_DEPTH {
            return;
        }
        out.extend(e.attrs.iter().filter(|(k, v)| is_rel_attr(k, v)).map(|(_, v)| v.clone()));
        for c in e.elements() {
            rec(c, out, depth + 1);
        }
    }
    let mut out = vec![];
    rec(el, &mut out, 0);
    out.sort();
    out.dedup();
    out
}

pub fn color_map(cm: &El) -> Vec<(String, String)> {
    cm.attrs.iter().filter(|(k, _)| !k.starts_with("xmlns")).map(|(k, v)| (k.clone(), v.clone())).collect()
}

/// A shape's text without an anchor of its own sits at the top, as the standard has it and as
/// PowerPoint draws it. The theme's shape defaults (`a:objectDefaults/a:spDef/a:bodyPr`, centred in
/// Office's themes) are for shapes inserted later, not for the file's own shapes: PowerPoint for
/// Mac draws `<a:bodyPr/>` at the top under an `spDef` with `anchor="ctr"`. The model's own default
/// for shapes is the middle, so a top or bottom anchor is made explicit here and a middle one left
/// unset (placeholders and text boxes keep inheriting).
fn default_text_anchor(p: &mut Presentation) {
    fn fix(shapes: &mut [deckcraft_model::Shape]) {
        walk_shapes_mut(shapes, &mut |s| {
            if s.ph.is_none()
                && !s.text_box
                && !matches!(s.kind, deckcraft_model::ShapeKind::Table(_))
                && let Some(t) = &mut s.text
            {
                // Middle is the model's own default for shapes, so it is kept as unset.
                let got = t.body.anchor.unwrap_or(deckcraft_model::text::Anchor::Top);
                t.body.anchor = (got != deckcraft_model::text::Anchor::Middle).then_some(got);
            }
        });
    }
    for m in &mut p.masters {
        let m = Arc::make_mut(m);
        fix(&mut m.shapes);
        for l in &mut m.layouts {
            fix(&mut l.shapes);
        }
    }
    for s in &mut p.slides {
        fix(&mut Arc::make_mut(s).shapes);
    }
}

/// Placeholders read without a geometry (an empty custom geometry, see `shapes::sp`) take the
/// geometry of the layout or master placeholder they inherit from, as PowerPoint draws them: a
/// layout's picture placeholder cut into a shape keeps that shape on the slide. Anything left
/// is a rectangle.
fn inherit_placeholder_geometry(p: &mut Presentation) {
    let unset = |g: &Geom| matches!(g, Geom::Custom { paths } if paths.is_empty());
    // Masters first, then layouts (from their masters), then slides (from layouts and masters).
    for m in &mut p.masters {
        let m = Arc::make_mut(m);
        walk_shapes_mut(&mut m.shapes, &mut |s| {
            if unset(&s.geom) {
                s.geom = Geom::default();
            }
        });
    }
    let mut layout_geoms: Vec<(LayoutId, usize, Geom)> = vec![];
    for m in &p.masters {
        for l in &m.layouts {
            let ctx = deckcraft_model::resolve::Ctx::for_layout(p, m, l);
            for (i, s) in l.shapes.iter().enumerate() {
                if unset(&s.geom) {
                    let (_, mp) = deckcraft_model::resolve::parents(&ctx, s);
                    layout_geoms.push((l.id, i, mp.map(|m| m.geom.clone()).filter(|g| !unset(g)).unwrap_or_default()));
                }
            }
        }
    }
    for m in &mut p.masters {
        let m = Arc::make_mut(m);
        for l in &mut m.layouts {
            for (id, i, g) in layout_geoms.iter().filter(|(id, _, _)| *id == l.id) {
                let _ = id;
                if let Some(s) = l.shapes.get_mut(*i) {
                    s.geom = g.clone();
                }
            }
        }
    }
    let mut slide_geoms: Vec<(usize, usize, Geom)> = vec![];
    for (si, sl) in p.slides.iter().enumerate() {
        let Some(ctx) = deckcraft_model::resolve::Ctx::for_slide(p, sl) else { continue };
        for (i, s) in sl.shapes.iter().enumerate() {
            if unset(&s.geom) {
                let (lp, mp) = deckcraft_model::resolve::parents(&ctx, s);
                let g = lp.map(|l| l.geom.clone()).filter(|g| !unset(g)).or_else(|| mp.map(|m| m.geom.clone()).filter(|g| !unset(g)));
                slide_geoms.push((si, i, g.unwrap_or_default()));
            }
        }
    }
    for (si, i, g) in slide_geoms {
        if let Some(sl) = p.slides.get_mut(si)
            && let Some(s) = Arc::make_mut(sl).shapes.get_mut(i)
        {
            s.geom = g;
        }
    }
    // Placeholders inside groups (rare) and anything still unset: rectangles.
    for sl in &mut p.slides {
        walk_shapes_mut(&mut Arc::make_mut(sl).shapes, &mut |s| {
            if unset(&s.geom) {
                s.geom = Geom::default();
            }
        });
    }
    for m in &mut p.masters {
        for l in &mut Arc::make_mut(m).layouts {
            walk_shapes_mut(&mut l.shapes, &mut |s| {
                if unset(&s.geom) {
                    s.geom = Geom::default();
                }
            });
        }
    }
}

/// Every shape, groups included.
fn walk_shapes_mut(shapes: &mut [deckcraft_model::Shape], f: &mut dyn FnMut(&mut deckcraft_model::Shape)) {
    for s in shapes {
        f(s);
        if let deckcraft_model::ShapeKind::Group { children, .. } = &mut s.kind {
            walk_shapes_mut(children, f);
        }
    }
}

/// `a:tblStyleLst`: the table styles the file defines.
fn table_styles(imp: &mut Imp, part: &Part, root: &El) -> Vec<deckcraft_model::table::TableStyleDef> {
    use deckcraft_model::table::{TableBorder, TablePart, TablePartStyle, TableStyleDef};
    root.children_named("tblStyle")
        .take(256)
        .filter_map(|st| {
            let id = st.attr("styleId")?.to_ascii_uppercase();
            let mut def = TableStyleDef { id, name: st.attr("styleName").unwrap_or("").to_string(), raw: part.keep(st), ..Default::default() };
            if let Some(bg) = st.child("tblBg") {
                let mut ps = TablePartStyle::default();
                if let Some(f) = bg.elements().find(|e| e.local().ends_with("Fill")) {
                    ps.fill = dml::fill_el(imp, part, f);
                }
                if let Some(fr) = bg.child("fillRef") {
                    ps.fill_ref = Some((
                        fr.u32("idx").unwrap_or(0),
                        dml::color(fr).unwrap_or(deckcraft_model::ColorRef::scheme(deckcraft_color::SchemeSlot::Accent1)),
                    ));
                }
                def.background = Some(ps);
            }
            for el in st.elements() {
                let Some(kind) = TablePart::from_xml(el.local()) else { continue };
                let mut ps = TablePartStyle::default();
                if let Some(tx) = el.child("tcTxStyle") {
                    ps.text_color = dml::color(tx);
                    ps.bold = tx.attr("b").map(|v| v == "on");
                    ps.italic = tx.attr("i").map(|v| v == "on");
                }
                if let Some(tc) = el.child("tcStyle") {
                    if let Some(f) = tc.child("fill").and_then(|f| f.elements().next()) {
                        ps.fill = dml::fill_el(imp, part, f);
                    }
                    if let Some(fr) = tc.child("fillRef") {
                        ps.fill_ref = Some((
                            fr.u32("idx").unwrap_or(0),
                            dml::color(fr).unwrap_or(deckcraft_model::ColorRef::scheme(deckcraft_color::SchemeSlot::Accent1)),
                        ));
                    }
                    if let Some(bd) = tc.child("tcBdr") {
                        for (i, side) in ["left", "right", "top", "bottom", "insideH", "insideV"].iter().enumerate() {
                            let Some(b) = bd.child(side) else { continue };
                            let border = if let Some(ln) = b.child("ln") {
                                Some(TableBorder::Line { line: dml::line(imp, part, ln) })
                            } else {
                                b.child("lnRef").map(|r| TableBorder::Ref {
                                    idx: r.u32("idx").unwrap_or(0),
                                    color: dml::color(r).unwrap_or(deckcraft_model::ColorRef::scheme(deckcraft_color::SchemeSlot::Accent1)),
                                })
                            };
                            if let Some(slot) = ps.borders.get_mut(i) {
                                *slot = border;
                            }
                        }
                    }
                }
                def.parts.push((kind, ps));
            }
            Some(def)
        })
        .collect()
}

fn background(imp: &mut Imp, part: &Part, csld: &El) -> Option<Background> {
    let bg = csld.child("bg")?;
    if let Some(pr) = bg.child("bgPr") {
        return Some(Background::Fill { fill: dml::fill_of(imp, part, pr).unwrap_or(deckcraft_model::Fill::None) });
    }
    let r = bg.child("bgRef")?;
    Some(Background::Ref {
        idx: r.u32("idx").unwrap_or(1001),
        color: dml::color(r).unwrap_or(deckcraft_model::ColorRef::scheme(deckcraft_color::SchemeSlot::Bg1)),
    })
}

fn read_master(imp: &mut Imp, path: &str, doc: &Doc, docs: &HashMap<String, Doc>, layout_by_part: &mut HashMap<String, LayoutId>) -> Master {
    let pkg = imp.pkg;
    let part = Part::new(pkg, path, doc);
    let root = &doc.root;
    let mut m = Master { id: MasterId(0), preserve: root.bool("preserve").unwrap_or(false), ..Default::default() };
    if let Some(t) = part.rels.first_of("theme")
        && let Some(td) = pkg.xml(&t.target)
    {
        let tp = Part::new(pkg, &t.target, &td);
        m.theme = theme::read_theme(imp, &tp, &td.root);
    }
    m.id = MasterId(imp.alloc());
    if let Some(cm) = root.child("clrMap") {
        m.color_map = color_map(cm);
    }
    if let Some(csld) = root.child("cSld") {
        m.name = csld.attr("name").unwrap_or("").to_string();
        m.background = background(imp, &part, csld);
        if let Some(tree) = csld.child("spTree") {
            let mut ctx = shapes::IdCtx::default();
            m.shapes = shapes::sp_tree(imp, &part, &mut ctx, tree, 0);
        }
    }
    if m.name.is_empty() {
        m.name = m.theme.name.clone();
    }
    if let Some(ts) = root.child("txStyles") {
        if let Some(s) = ts.child("titleStyle") {
            m.title_style = dml::list_style(imp, &part, s);
        }
        if let Some(s) = ts.child("bodyStyle") {
            m.body_style = dml::list_style(imp, &part, s);
        }
        if let Some(s) = ts.child("otherStyle") {
            m.other_style = dml::list_style(imp, &part, s);
        }
    }
    // Layouts in list order, then any other related layouts.
    let mut lpaths: Vec<String> = root
        .child("sldLayoutIdLst")
        .map(|l| l.children_named("sldLayoutId").filter_map(|x| part.rels.target(x.attr("r:id").unwrap_or(""))).map(String::from).collect())
        .unwrap_or_default();
    for r in part.rels.all_of("slideLayout") {
        if !lpaths.iter().any(|x| opc::norm(x) == opc::norm(&r.target)) {
            lpaths.push(r.target.clone());
        }
    }
    for lp in lpaths.iter().take(1000) {
        let key = opc::norm(lp);
        if layout_by_part.contains_key(&key) {
            continue;
        }
        let Some(ld) = docs.get(&key) else { continue };
        let lpart = Part::new(pkg, lp, ld);
        let l = read_layout(imp, &lpart, ld);
        layout_by_part.insert(key, l.id);
        m.layouts.push(l);
    }
    if m.layouts.is_empty() {
        // A master must have a layout for slides to use.
        imp.next = imp.next.saturating_add(1);
        m.layouts.push(Layout {
            id: LayoutId(imp.next),
            name: "Blank".into(),
            kind: LayoutType::Blank,
            show_master_shapes: true,
            ..Default::default()
        });
    }
    if let Some(ext) = root.child("extLst").filter(|e| !has_rel_refs(e)) {
        m.raw_ext = Some(ext.elements().map(|e| part.keep(e)).collect());
    }
    m
}

fn read_layout(imp: &mut Imp, part: &Part, doc: &Doc) -> Layout {
    let root = &doc.root;
    let mut l = Layout {
        id: LayoutId(imp.alloc()),
        kind: LayoutType::from_xml(root.attr("type").unwrap_or("cust")),
        show_master_shapes: root.bool("showMasterSp").unwrap_or(true),
        preserve: root.bool("preserve").unwrap_or(false),
        ..Default::default()
    };
    if let Some(csld) = root.child("cSld") {
        l.name = csld.attr("name").unwrap_or("").to_string();
        l.background = background(imp, part, csld);
        if let Some(tree) = csld.child("spTree") {
            let mut ctx = shapes::IdCtx::default();
            l.shapes = shapes::sp_tree(imp, part, &mut ctx, tree, 0);
        }
    }
    l.color_map = color_map_override(root);
    if let Some(ext) = root.child("extLst").filter(|e| !has_rel_refs(e)) {
        l.raw_ext = Some(ext.elements().map(|e| part.keep(e)).collect());
    }
    l
}

/// A layout's or slide's `clrMapOvr/overrideClrMapping` (None for `masterClrMapping` or none).
fn color_map_override(root: &El) -> Option<Vec<(String, String)>> {
    root.child("clrMapOvr")?.child("overrideClrMapping").map(color_map)
}

fn read_slide(imp: &mut Imp, part: &Part, doc: &Doc, id: SlideId, layout: LayoutId) -> Slide {
    let root = &doc.root;
    let mut s = Slide {
        id,
        layout,
        hidden: root.bool("show") == Some(false),
        show_master_shapes: root.bool("showMasterSp").unwrap_or(true),
        color_map: color_map_override(root),
        ..Default::default()
    };
    let mut ctx = shapes::IdCtx::default();
    if let Some(csld) = root.child("cSld") {
        s.name = csld.attr("name").unwrap_or("").to_string();
        s.tags = tags(imp, part, csld);
        s.background = background(imp, part, csld);
        if let Some(tree) = csld.child("spTree") {
            s.shapes = shapes::sp_tree(imp, part, &mut ctx, tree, 0);
        }
        if let Some(c) = csld.child("controls") {
            let pics = shapes::controls(imp, part, &mut ctx, c);
            s.shapes.extend(pics);
        }
    }
    if let Some(t) = root.child("transition") {
        s.transition = timing::transition(imp, part, t);
    }
    if let Some(t) = root.child("timing") {
        s.animations = timing::animations(imp, part, &ctx, t, &s.shapes);
        timing::media_settings(t, &ctx, &mut s.shapes);
    }
    if let Some(ext) = root.child("extLst").filter(|e| !has_rel_refs(e)) {
        s.raw_ext = Some(ext.elements().map(|e| part.keep(e)).collect());
    }
    s
}

fn read_notes(imp: &mut Imp, part: &Part, root: &El) -> TextBody {
    let Some(tree) = root.path(&["cSld", "spTree"]) else { return TextBody::default() };
    for sp in tree.children_named("sp") {
        let ph = sp.path(&["nvSpPr", "nvPr", "ph"]);
        let is_body = ph.is_some_and(|ph| matches!(ph.attr("type"), Some("body") | None) && ph.attr("type") != Some("sldImg"));
        if is_body && let Some(tx) = sp.child("txBody") {
            let mut t = dml::text_body(imp, part, tx);
            // Notes keep only content: drop body formatting from the notes master placeholder.
            t.list_style = Default::default();
            if t.is_empty() {
                return TextBody::default();
            }
            return t;
        }
    }
    TextBody::default()
}

fn read_comments(pkg: &Package, pres: &Part, root: &El, modern: bool) -> Vec<Comment> {
    // Authors: legacy commentAuthors.xml (numeric ids) and modern authors.xml (GUIDs).
    let mut authors: HashMap<String, (String, String)> = HashMap::new();
    for kind in ["commentAuthors", "authors"] {
        if let Some(r) = pres.rels.first_of(kind)
            && let Some(d) = pkg.xml(&r.target)
        {
            for a in d.root.elements() {
                if let Some(id) = a.attr("id") {
                    authors.insert(id.to_string(), (a.attr("name").unwrap_or("").to_string(), a.attr("initials").unwrap_or("").to_string()));
                }
            }
        }
    }
    // Legacy positions are 1/8 pt; the modern part's p188:pos is an a:CT_Point2D in EMU.
    let scale = if modern { 12_700.0 } else { 8.0 };
    fn one(e: &El, authors: &HashMap<String, (String, String)>, depth: usize, scale: f64) -> Comment {
        let (author, initials) = e.attr("authorId").and_then(|a| authors.get(a).cloned()).unwrap_or_default();
        let text = if let Some(t) = e.child("text") {
            t.text()
        } else if let Some(tb) = e.child("txBody") {
            tb.children_named("p").map(|p| p.text()).collect::<Vec<_>>().join("\n")
        } else {
            String::new()
        };
        let pos = e.child("pos");
        let replies = if depth < 4 {
            e.child("replyLst").map(|l| l.children_named("reply").take(1000).map(|r| one(r, authors, depth + 1, scale)).collect()).unwrap_or_default()
        } else {
            vec![]
        };
        Comment {
            author,
            initials,
            text,
            date: e.attr("dt").or(e.attr("created")).unwrap_or("").to_string(),
            x: pos.and_then(|p| p.f64("x")).unwrap_or(0.0) / scale,
            y: pos.and_then(|p| p.f64("y")).unwrap_or(0.0) / scale,
            resolved: e.attr("status") == Some("resolved"),
            replies,
            shape: None,
        }
    }
    root.children_named("cm").take(10_000).map(|c| one(c, &authors, 0, scale)).collect()
}

fn read_show(sp: &El, shows: &HashMap<String, String>) -> ShowSettings {
    let mut s = ShowSettings {
        loop_until_esc: sp.bool("loop").unwrap_or(false),
        without_narration: sp.bool("showNarration") == Some(false),
        without_animation: sp.bool("showAnimation") == Some(false),
        use_timings: sp.bool("useTimings").unwrap_or(true),
        show_media_controls: sp.find("showMediaCtrls").and_then(|e| e.bool("val")).unwrap_or(true),
        ..Default::default()
    };
    if sp.child("browse").is_some() {
        s.show_type = "browsed".into();
    } else if sp.child("kiosk").is_some() {
        s.show_type = "kiosk".into();
    }
    if let Some(r) = sp.child("sldRg") {
        s.range = Some((r.u32("st").unwrap_or(1).max(1), r.u32("end").unwrap_or(1).max(1)));
    }
    if let Some(c) = sp.child("custShow") {
        let id = c.attr("id").unwrap_or("");
        s.custom_show = Some(shows.get(id).cloned().unwrap_or_else(|| id.to_string()));
    }
    if let Some(c) = sp.child("penClr").and_then(dml::color)
        && let deckcraft_model::ColorBase::Rgb { rgb } = c.base
    {
        s.pen_color = rgb;
    }
    s
}

fn read_core(root: &El, p: &mut Properties) {
    for e in root.elements() {
        let t = e.text();
        match e.local() {
            "title" => p.title = t,
            "subject" => p.subject = t,
            "creator" => p.author = t,
            "keywords" => p.keywords = t,
            "description" => p.comments = t,
            "category" => p.category = t,
            "lastModifiedBy" => p.last_modified_by = t,
            "revision" => p.revision = t.trim().parse().unwrap_or(0),
            "created" => p.created = t,
            "modified" => p.modified = t,
            _ => {}
        }
    }
}

/// Which footer placeholders the slides show.
fn header_footer(p: &Presentation) -> HeaderFooter {
    let mut hf = HeaderFooter::default();
    for s in &p.slides {
        for sh in &s.shapes {
            match sh.ph_type() {
                Some(PhType::SlideNum) => hf.slide_number = true,
                Some(PhType::Date) => {
                    hf.date = true;
                    let field = sh.text.iter().flat_map(|t| t.paragraphs.iter()).flat_map(|p| p.runs.iter()).find_map(|r| match &r.kind {
                        deckcraft_model::text::RunKind::Field { field } if deckcraft_text::datetime::is_date_field(field) => Some(field.as_str()),
                        _ => None,
                    });
                    match field {
                        // An automatic date: remember which of the thirteen formats it is, so the
                        // Header and Footer dialog opens on the deck's own choice instead of the
                        // default. An unknown spelling (`datetime`, `datetimeFigureOut`) is left
                        // as no choice rather than guessed at.
                        Some(kind) => {
                            if hf.date_format.is_empty() && deckcraft_text::datetime::DATE_KINDS.contains(&kind) {
                                hf.date_format = kind.to_string();
                            }
                        }
                        // A fixed date: its text, as before.
                        None => {
                            if hf.date_text.is_empty()
                                && let Some(t) = &sh.text
                            {
                                hf.date_text = t.text();
                            }
                        }
                    }
                }
                Some(PhType::Footer) => {
                    hf.footer = true;
                    if hf.footer_text.is_empty()
                        && let Some(t) = &sh.text
                    {
                        hf.footer_text = t.text();
                    }
                }
                _ => {}
            }
        }
    }
    hf
}

#[cfg(test)]
mod rollback_tests {
    use super::*;

    /// A rolled-back read gives back its budgets and removes only the media and kept-chart entries it added.
    #[test]
    fn rollback_restores_budgets_and_removes_only_what_was_added() {
        let bytes = crate::export(&deckcraft_model::Presentation::default()).expect("export");
        let pkg = Package::open(&bytes).expect("package");
        let mut imp = Imp {
            pkg: &pkg,
            media: vec![],
            media_by_part: HashMap::new(),
            media_keys: vec![],
            next: 0,
            slide_by_part: HashMap::new(),
            custom_show_names: HashMap::new(),
            table_style_ids: Vec::new(),
            vml_previews: HashMap::new(),
            kept_sidecar_bytes: 0,
            chart_points: 0,
            chart_points_cap: chart::MAX_PRESENTATION_CHART_POINTS,
            kept_charts: HashMap::new(),
            kept_chart_keys: vec![],
            rejected_kept: HashMap::new(),
            chart_decode_bytes: 0,
            tags_by_part: HashMap::new(),
            tag_bytes: 0,
            tags_capped: false,
            warnings: vec![],
            theme_extra_bytes: 0,
            smartart_shapes: 0,
            diagram_xml_bytes: 0,
            has_rels: HashMap::new(),
        };
        let kept_before = imp.media_for("ppt/presentation.xml").expect("media");
        let (m, items) = (imp.mark(), imp.media.len());
        assert!(imp.media_for("ppt/presProps.xml").is_some());
        imp.kept_chart_keys.push("ppt/charts/chart1.xml".into());
        imp.kept_charts.insert("ppt/charts/chart1.xml".into(), Default::default());
        (imp.diagram_xml_bytes, imp.tag_bytes, imp.tags_capped, imp.kept_sidecar_bytes) = (7, 5, true, 9);
        imp.rollback(&m);
        assert_eq!(imp.media.len(), items);
        assert_eq!(imp.media_by_part.get("ppt/presentation.xml"), Some(&kept_before));
        assert!(!imp.media_by_part.contains_key("ppt/presprops.xml") && imp.kept_charts.is_empty() && imp.kept_chart_keys.is_empty());
        assert_eq!((imp.diagram_xml_bytes, imp.tag_bytes, imp.tags_capped, imp.kept_sidecar_bytes), (0, 0, false, 0));
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn mc_branches_carry_only_the_declarations_their_content_uses() {
        // 2,000 declarations on the branch and 2,000 children: each child gets the one it uses
        // (and the default), not all 2,000.
        let decls: String = (0..2000).map(|i| format!(r#" xmlns:n{i}="urn:n{i}""#)).collect();
        let kids: String = (0..2000).map(|i| format!("<n{i}:x/>")).collect();
        let x = format!(
            r#"<r xmlns:mc="http://schemas.openxmlformats.org/markup-compatibility/2006"><mc:AlternateContent><mc:Fallback xmlns="urn:d"{decls}>{kids}</mc:Fallback></mc:AlternateContent></r>"#
        );
        let mut d = crate::xml::parse(x.as_bytes()).unwrap();
        resolve_mc(&mut d.root, 0);
        let kids: Vec<&El> = d.root.elements().collect();
        assert_eq!(kids.len(), 2000);
        assert_eq!(kids[7].attrs, vec![("xmlns".to_string(), "urn:d".to_string()), ("xmlns:n7".to_string(), "urn:n7".to_string())]);
    }

    /// The branch's own declaration of a prefix wins over the `AlternateContent`'s; an oversized
    /// one still shadows it (its content stays unbound); a child's own declaration is left alone.
    #[test]
    fn mc_branch_declarations_keep_their_precedence() {
        let long = "u".repeat(MAX_NS_VALUE + 1);
        let x = format!(
            r#"<r xmlns:mc="http://schemas.openxmlformats.org/markup-compatibility/2006"><mc:AlternateContent xmlns:p="urn:ac" xmlns:q="urn:q-short"><mc:Fallback xmlns:p="urn:b" xmlns:q="{long}"><p:x/><q:y/><p:z xmlns:p="urn:own"/></mc:Fallback></mc:AlternateContent></r>"#
        );
        let mut d = crate::xml::parse(x.as_bytes()).unwrap();
        resolve_mc(&mut d.root, 0);
        let kids: Vec<&El> = d.root.elements().collect();
        let attrs = |i: usize| kids[i].attrs.iter().map(|(k, v)| format!("{k}={v}")).collect::<Vec<_>>();
        assert_eq!(attrs(0), ["xmlns:p=urn:b"]);
        assert!(attrs(1).is_empty(), "{:?}", attrs(1));
        assert_eq!(attrs(2), ["xmlns:p=urn:own"]);
    }

    #[test]
    fn mc_branches_keep_prefixes_named_by_must_understand() {
        let x = r#"<r xmlns:mc="http://schemas.openxmlformats.org/markup-compatibility/2006"><mc:AlternateContent><mc:Fallback xmlns:q="urn:q"><a mc:MustUnderstand="q"/></mc:Fallback></mc:AlternateContent></r>"#;
        let mut d = crate::xml::parse(x.as_bytes()).unwrap();
        resolve_mc(&mut d.root, 0);
        let kid = d.root.elements().next().unwrap();
        assert!(kid.attrs.iter().any(|(k, v)| k == "xmlns:q" && v == "urn:q"), "{:?}", kid.attrs);
    }

    #[test]
    fn mc_branches_keep_prefixes_used_in_qname_values() {
        let x = r#"<r xmlns:mc="http://schemas.openxmlformats.org/markup-compatibility/2006"><mc:AlternateContent><mc:Fallback xmlns:q="urn:q" xmlns:z="urn:z"><n xmlns:xsi="urn:xsi" xsi:type="q:Item"/></mc:Fallback></mc:AlternateContent></r>"#;
        let mut d = crate::xml::parse(x.as_bytes()).unwrap();
        resolve_mc(&mut d.root, 0);
        let kid = d.root.elements().next().unwrap();
        assert!(kid.attrs.iter().any(|(k, v)| k == "xmlns:q" && v == "urn:q"), "{:?}", kid.attrs);
        assert!(!kid.attrs.iter().any(|(k, _)| k == "xmlns:z"), "unused declarations stay out: {:?}", kid.attrs);
    }

    #[test]
    fn kept_fragments_skip_oversized_namespace_names() {
        let big = "u".repeat(MAX_NS_VALUE + 1);
        let ns = vec![("xmlns:a".to_string(), "urn:a".to_string()), ("xmlns:b".to_string(), big)];
        let d = crate::xml::parse(br#"<a:x xmlns:a="urn:a" xmlns:b="urn:b"><b:y/></a:x>"#).unwrap();
        let mut el = d.root.clone();
        el.attrs.clear();
        let out = keep_xml(&el, &ns);
        assert!(out.contains(r#"xmlns:a="urn:a""#), "{out}");
        assert!(!out.contains("uuuu"), "the oversized declaration is not copied");
    }

    #[test]
    fn copied_namespace_bytes_are_budgeted_per_part() {
        let d = crate::xml::parse(br#"<a:x xmlns:a="urn:a"><a:y/></a:x>"#).unwrap();
        let mut el = d.root.clone();
        el.attrs.clear();
        let part = Part {
            name: String::new(),
            rels: Default::default(),
            ns: vec![("xmlns:a".to_string(), "urn:a".to_string())],
            inner_ns: vec![],
            ns_budget: Cell::new(15),
        };
        assert!(part.keep(&el).contains(r#"xmlns:a="urn:a""#), "within budget");
        assert!(part.ns_budget.get() < 15);
        let again = part.keep(&el);
        assert!(!again.contains("xmlns:a"), "budget spent, no further declarations: {again}");
    }
}