GitCorner

Code

ossartcraftgridcraft🌐
1687a9c05b0c
use super::*;

/// Largest package part read while validating a written package.
const MAX_XML_PART: u64 = 64 * 1024 * 1024;

/// Most zip entries looked at while validating a written package.
const MAX_ENTRIES: usize = 200_000;

/// Decompressed bytes that comparing one package's relationship kinds may read in total: the
/// relationship parts themselves and the targets whose content is checked.
const RELATIONSHIP_BUDGET: u64 = 512 * 1024 * 1024;

/// Relationship kinds (lower case) whose absence after a save isn't a loss: the calculation chain is
/// a cache Excel rebuilds, and GridCraft never writes it.
pub(super) const REBUILT_KINDS: [&str; 1] = ["calcchain"];

// ---------------------------------------------------------------- package validation

fn local_name(name: &[u8]) -> &[u8] {
    match name.iter().rposition(|&b| b == b':') {
        Some(i) => name.get(i + 1..).unwrap_or(name),
        None => name,
    }
}

/// `(element local name, attributes)` for every start/empty element of an XML part.
type XmlElement = (String, Vec<(String, String)>);

fn xml_elements(xml: &[u8]) -> Result<Vec<XmlElement>, String> {
    use quick_xml::events::Event;
    let mut reader = quick_xml::Reader::from_reader(xml);
    let mut buf = Vec::new();
    let mut out = Vec::new();
    loop {
        match reader.read_event_into(&mut buf) {
            Ok(Event::Start(e)) | Ok(Event::Empty(e)) => {
                let attrs = e
                    .attributes()
                    .with_checks(false)
                    .flatten()
                    .map(|a| {
                        let v = match a.normalized_value(quick_xml::XmlVersion::Explicit1_0) {
                            Ok(v) => v.into_owned(),
                            Err(_) => String::from_utf8_lossy(&a.value).into_owned(),
                        };
                        (String::from_utf8_lossy(local_name(a.key.as_ref())).into_owned(), v)
                    })
                    .collect();
                out.push((String::from_utf8_lossy(local_name(e.name().as_ref())).into_owned(), attrs));
            }
            Ok(Event::Eof) => break,
            Ok(_) => {}
            Err(e) => return Err(format!("invalid XML: {e}")),
        }
        buf.clear();
    }
    Ok(out)
}

fn attr<'a>(attrs: &'a [(String, String)], k: &str) -> Option<&'a str> {
    attrs.iter().find(|(n, _)| n == k).map(|(_, v)| v.as_str())
}

/// Lower-cased part name without a leading slash: OPC part names compare case-insensitively.
fn part_key(name: &str) -> String {
    name.trim_start_matches('/').to_ascii_lowercase()
}

/// `%XX` escapes in a relationship target.
fn percent_decode(s: &str) -> String {
    let b = s.as_bytes();
    let mut out = Vec::with_capacity(b.len());
    let mut i = 0;
    while let Some(&c) = b.get(i) {
        let hex = |j: usize| b.get(j).and_then(|h| (*h as char).to_digit(16));
        match (c, hex(i + 1), hex(i + 2)) {
            (b'%', Some(h), Some(l)) => {
                out.push((h * 16 + l) as u8);
                i += 3;
            }
            _ => {
                out.push(c);
                i += 1;
            }
        }
    }
    String::from_utf8_lossy(&out).into_owned()
}

/// Resolves a relationship target against the source part's directory.
fn resolve_target(source_dir: &str, target: &str) -> String {
    let target = percent_decode(target.split('#').next().unwrap_or(target));
    let joined = match target.strip_prefix('/') {
        Some(abs) => abs.to_string(),
        None if source_dir.is_empty() => target,
        None => format!("{source_dir}/{target}"),
    };
    let mut parts: Vec<&str> = Vec::new();
    for seg in joined.split('/') {
        match seg {
            "" | "." => {}
            ".." => {
                parts.pop();
            }
            s => parts.push(s),
        }
    }
    parts.join("/")
}

type Zip<'a> = zip::ZipArchive<Cursor<&'a [u8]>>;

fn zip_names(zip: &mut Zip<'_>) -> Vec<String> {
    (0..zip.len().min(MAX_ENTRIES)).filter_map(|i| zip.by_index_raw(i).ok().filter(|f| !f.is_dir()).map(|f| f.name().to_string())).collect()
}

fn read_zip_part(zip: &mut Zip<'_>, name: &str) -> Result<Vec<u8>, String> {
    let f = zip.by_name(name).map_err(|e| format!("{name}: {e}"))?;
    let mut buf = Vec::new();
    f.take(MAX_XML_PART).read_to_end(&mut buf).map_err(|e| format!("{name}: {e}"))?;
    Ok(buf)
}

enum PartError {
    /// Reading the part would spend more than the remaining budget.
    OverBudget,
    Unreadable,
}

/// Reads a part like [`read_zip_part`], charging the decompressed bytes to `budget`.
fn read_zip_part_within(zip: &mut Zip<'_>, name: &str, budget: &mut u64) -> Result<Vec<u8>, PartError> {
    let f = zip.by_name(name).map_err(|_| PartError::Unreadable)?;
    // One byte past what is left shows that the part doesn't fit.
    let limit = MAX_XML_PART.min(budget.saturating_add(1));
    let mut buf = Vec::new();
    // Bytes read before a decompression error still count against the budget.
    let res = f.take(limit).read_to_end(&mut buf);
    let read = buf.len() as u64;
    if read > *budget {
        *budget = 0;
        return Err(PartError::OverBudget);
    }
    *budget -= read;
    res.map_err(|_| PartError::Unreadable)?;
    Ok(buf)
}

/// Whether the producer flagged its cached results as stale with `<calcPr fullCalcOnLoad="1">`:
/// libraries that don't calculate write it, and store 0 or nothing as every formula's value.
pub(super) fn full_calc_on_load(bytes: &[u8]) -> bool {
    let Ok(mut zip) = zip::ZipArchive::new(Cursor::new(bytes)) else { return false };
    let names = zip_names(&mut zip);
    let find = |key: &str| names.iter().find(|n| part_key(n) == key).cloned();
    let mut workbook = "xl/workbook.xml".to_string();
    if let Some(rels) = find("_rels/.rels")
        && let Ok(xml) = read_zip_part(&mut zip, &rels)
        && let Ok(els) = xml_elements(&xml)
        && let Some(target) = els
            .iter()
            .find(|(e, a)| e == "Relationship" && attr(a, "Type").is_some_and(|t| t.ends_with("/officeDocument")))
            .and_then(|(_, a)| attr(a, "Target"))
    {
        workbook = resolve_target("", target);
    }
    let Some(name) = find(&part_key(&workbook)) else { return false };
    let Ok(xml) = read_zip_part(&mut zip, &name) else { return false };
    xml_elements(&xml)
        .ok()
        .into_iter()
        .flatten()
        .any(|(e, a)| e == "calcPr" && attr(&a, "fullCalcOnLoad").is_some_and(|v| v == "1" || v.eq_ignore_ascii_case("true")))
}

/// Problems Excel would repair in a written package: parts without a content type, content-type
/// overrides for missing parts, relationship files for missing parts, duplicate relationship ids
/// and internal relationships pointing at missing parts. `Err` when the package can't be read.
pub fn validate_package(bytes: &[u8]) -> Result<Vec<String>, String> {
    let mut zip = zip::ZipArchive::new(Cursor::new(bytes)).map_err(|e| format!("not a zip package: {e}"))?;
    let names = zip_names(&mut zip);
    let parts: HashSet<String> = names.iter().map(|n| part_key(n)).collect();
    let mut read_part = |name: &str| read_zip_part(&mut zip, name);
    let mut issues = Vec::new();
    let ct_name = names.iter().find(|n| part_key(n) == "[content_types].xml").cloned();
    let (mut defaults, mut overrides) = (HashSet::new(), HashSet::new());
    match ct_name {
        None => issues.push("no [Content_Types].xml".to_string()),
        Some(n) => {
            for (el, attrs) in xml_elements(&read_part(&n)?).map_err(|e| format!("[Content_Types].xml: {e}"))? {
                match el.as_str() {
                    "Default" => {
                        if let Some(x) = attr(&attrs, "Extension") {
                            defaults.insert(x.to_ascii_lowercase());
                        }
                    }
                    "Override" => {
                        if let Some(p) = attr(&attrs, "PartName") {
                            overrides.insert(part_key(p));
                        }
                    }
                    _ => {}
                }
            }
        }
    }
    let mut sorted: Vec<&String> = names.iter().collect();
    sorted.sort();
    for n in &sorted {
        let key = part_key(n);
        if key == "[content_types].xml" {
            continue;
        }
        let ext = key.rsplit('/').next().and_then(|f| f.rsplit_once('.')).map(|(_, e)| e.to_string());
        if !overrides.contains(&key) && !ext.is_some_and(|e| defaults.contains(&e)) {
            issues.push(format!("part {n} has no content type"));
        }
    }
    let mut missing_overrides: Vec<&String> = overrides.iter().filter(|p| !parts.contains(*p)).collect();
    missing_overrides.sort();
    for p in missing_overrides {
        issues.push(format!("content type override for missing part /{p}"));
    }
    for n in sorted {
        let key = part_key(n);
        let Some(rels_file) = key.strip_suffix(".rels") else { continue };
        // `dir/_rels/name.rels` describes `dir/name`; `_rels/.rels` the package itself.
        let (dir, file) = match rels_file.rsplit_once('/') {
            Some((d, f)) => (d, f),
            None => continue,
        };
        let Some(src_dir) = dir.strip_suffix("_rels").map(|d| d.trim_end_matches('/')) else { continue };
        let source = if src_dir.is_empty() { file.to_string() } else { format!("{src_dir}/{file}") };
        if !source.is_empty() && !parts.contains(&source) {
            issues.push(format!("{n} describes missing part {source}"));
        }
        let mut ids = HashSet::new();
        for (el, attrs) in xml_elements(&read_part(n)?).map_err(|e| format!("{n}: {e}"))? {
            if el != "Relationship" {
                continue;
            }
            let id = attr(&attrs, "Id").unwrap_or("");
            if !ids.insert(id.to_string()) {
                issues.push(format!("{n}: duplicate relationship id {id}"));
            }
            if attr(&attrs, "TargetMode").is_some_and(|m| m.eq_ignore_ascii_case("External")) {
                continue;
            }
            let target = attr(&attrs, "Target").unwrap_or("");
            let resolved = resolve_target(src_dir, target);
            if !parts.contains(&resolved.to_ascii_lowercase()) {
                let kind = attr(&attrs, "Type").and_then(|t| t.rsplit('/').next()).unwrap_or("?");
                issues.push(format!("{n}: {id} ({kind}) targets missing part {resolved}"));
            }
        }
    }
    Ok(issues)
}

/// Every relationship kind (last segment of the type, the same in the transitional and strict
/// namespaces) in the package's relationship parts, keyed in lower case. Relationships that carry
/// nothing are left out, as a save may rightly drop them: a link to a place in the workbook
/// (`#Sheet1!A1`, written as a cell's `location`) and a target part with nothing in it.
pub(super) fn relationship_kinds(bytes: &[u8]) -> Result<BTreeMap<String, String>, String> {
    relationship_kinds_within(bytes, RELATIONSHIP_BUDGET)
}

/// [`relationship_kinds`] reading at most `budget` decompressed bytes. `Err` once the relationship
/// parts alone need more: their kinds can't be listed completely.
fn relationship_kinds_within(bytes: &[u8], mut budget: u64) -> Result<BTreeMap<String, String>, String> {
    let mut zip = zip::ZipArchive::new(Cursor::new(bytes)).map_err(|e| format!("not a zip package: {e}"))?;
    let names = zip_names(&mut zip);
    let by_key: HashMap<String, &String> = names.iter().map(|n| (part_key(n), n)).collect();
    // Several relationships name the same part; each fresh check decompressed it again, so
    // repeated references to one highly compressible part multiplied the work. The verdict is
    // remembered per (part, named content) and the decompression the package can cause is
    // budgeted as a whole, the relationship parts included: many large, unreferenced rels parts
    // would otherwise each spend a full per-part allowance.
    let mut verdicts: HashMap<(String, &'static str), bool> = HashMap::new();
    let mut kinds = BTreeMap::new();
    for n in names.iter().filter(|n| part_key(n).ends_with(".rels")) {
        let Some(src_dir) = rels_source_dir(&part_key(n)) else { continue };
        let xml = match read_zip_part_within(&mut zip, n, &mut budget) {
            Ok(xml) => xml,
            Err(PartError::OverBudget) => return Err(format!("{n}: relationship check stopped at its decompression limit")),
            Err(PartError::Unreadable) => continue,
        };
        let Ok(els) = xml_elements(&xml) else { continue };
        for (_, attrs) in els.iter().filter(|(el, _)| el == "Relationship") {
            let Some(kind) = attr(attrs, "Type").and_then(|t| t.rsplit('/').next()) else { continue };
            let target = attr(attrs, "Target").unwrap_or("");
            if kind.eq_ignore_ascii_case("hyperlink") && target.starts_with('#') {
                continue;
            }
            let external = attr(attrs, "TargetMode").is_some_and(|m| m.eq_ignore_ascii_case("External"));
            if !external
                && let Some(part) = by_key.get(&resolve_target(&src_dir, target).to_ascii_lowercase())
                && !holds_something(&mut zip, part, kind, &mut verdicts, &mut budget)
            {
                continue;
            }
            kinds.entry(kind.to_ascii_lowercase()).or_insert_with(|| kind.to_string());
        }
    }
    Ok(kinds)
}

/// The directory of the part a rels part describes: `xl` for `xl/_rels/workbook.xml.rels`, the
/// empty string for the package's `_rels/.rels`.
fn rels_source_dir(key: &str) -> Option<String> {
    let (dir, _) = key.strip_suffix(".rels")?.rsplit_once('/')?;
    Some(dir.strip_suffix("_rels")?.trim_end_matches('/').to_string())
}

/// Whether a part has content: an element under its root, or for comments (whose authors list
/// comes first) a comment, for VML a shape. Read only as far as needed; an unreadable part counts.
/// `verdicts` remembers the answer per (part, named content); `budget` is the decompression this
/// package's remaining checks may cause, and once it is spent the part counts as having content.
fn holds_something(zip: &mut Zip<'_>, name: &str, kind: &str, verdicts: &mut HashMap<(String, &'static str), bool>, budget: &mut u64) -> bool {
    let wanted: Option<&'static [u8]> = match kind.to_ascii_lowercase().as_str() {
        "comments" => Some(b"comment"),
        "vmldrawing" => Some(b"shape"),
        _ => None,
    };
    let marker = match wanted {
        Some(b"comment") => "comment",
        Some(_) => "shape",
        None => "any",
    };
    if let Some(v) = verdicts.get(&(name.to_ascii_lowercase(), marker)) {
        return *v;
    }
    let v = holds_something_uncached(zip, name, marker, budget);
    verdicts.insert((name.to_ascii_lowercase(), marker), v);
    v
}

fn holds_something_uncached(zip: &mut Zip<'_>, name: &str, marker: &'static str, budget: &mut u64) -> bool {
    use quick_xml::events::Event;
    let Ok(f) = zip.by_name(name) else { return true };
    if *budget == 0 {
        return true;
    }
    let take = f.size().min(MAX_XML_PART).min(*budget);
    *budget -= take;
    let mut reader = quick_xml::Reader::from_reader(std::io::BufReader::new(f.take(take)));
    let wanted: Option<&'static [u8]> = match marker {
        "comment" => Some(b"comment"),
        "shape" => Some(b"shape"),
        _ => None,
    };
    let mut buf = Vec::new();
    let mut in_root = false;
    loop {
        match reader.read_event_into(&mut buf) {
            Ok(Event::Start(e)) | Ok(Event::Empty(e)) => {
                let found = match wanted {
                    Some(w) => local_name(e.name().as_ref()) == w,
                    None => in_root,
                };
                if found {
                    return true;
                }
                in_root = true;
            }
            Ok(Event::Eof) => return false,
            Ok(_) => {}
            Err(_) => return true,
        }
        buf.clear();
    }
}

#[cfg(test)]
mod tests {
    use std::io::Write as _;

    use super::*;

    /// A package with `count` relationship parts of `size` bytes each, none of them describing an
    /// existing part.
    fn many_rels(count: usize, size: usize) -> Vec<u8> {
        let mut z = zip::ZipWriter::new(Cursor::new(Vec::new()));
        let opts = zip::write::SimpleFileOptions::default().compression_method(zip::CompressionMethod::Deflated);
        let head = r#"<?xml version="1.0"?><Relationships xmlns="http://schemas.openxmlformats.org/package/2006/relationships"><Relationship Id="rId1" Type="http://schemas.openxmlformats.org/officeDocument/2006/relationships/custom" Target="https://example.com" TargetMode="External"/>"#;
        let tail = "</Relationships>";
        let filler = " ".repeat(size.saturating_sub(head.len() + tail.len()));
        for i in 0..count {
            z.start_file(format!("xl/_rels/part{i}.xml.rels"), opts).unwrap();
            z.write_all(head.as_bytes()).unwrap();
            z.write_all(filler.as_bytes()).unwrap();
            z.write_all(tail.as_bytes()).unwrap();
        }
        z.finish().unwrap().into_inner()
    }

    #[test]
    fn relationship_parts_count_against_the_decompression_budget() {
        // Each part fits the per-part allowance, but together they need more than the budget.
        let bytes = many_rels(8, 64 * 1024);
        assert!(relationship_kinds_within(&bytes, 256 * 1024).is_err());
        let kinds = relationship_kinds_within(&bytes, 1024 * 1024).unwrap();
        assert_eq!(kinds.get("custom").map(String::as_str), Some("custom"));
    }
}