GitCorner

Code

ossartcraftvectorcraft🌐
2bc41aeb8602
//! Pathfinder panel (`object.pathfinder.*`) and Object → Path commands backed by
//! `vectorcraft-pathops`: Offset Path, Outline Stroke, Simplify, Add Anchor Points, Split Into Grid,
//! Clean Up and Divide Objects Below.

use std::collections::BTreeSet;
use std::sync::Arc;

use serde_json::{Value, json};
use vectorcraft_color::BlendMode;
use vectorcraft_doc::appearance::{AppearanceItem, StrokeLayer};
use vectorcraft_doc::{AnchorRef, Appearance, Document, Node, NodeId, NodeKind, SegmentRef, TextObject};
use vectorcraft_geom::{FillRule, PathData, SubPath};
use vectorcraft_pathops as po;
use vectorcraft_pathops::{BoolOp, PathfinderOp};

use super::edit::selected_roots;
use super::expand::{fill_shape, reshaped, seeded};
use super::{
    CommandSpec, EngineError, Result, Session, always, bad, check_switches, checked_ids_or_selection, cmd, has_doc, has_selected_path, has_selection,
    number_or, switch_or, text_param,
};

pub fn specs() -> Vec<CommandSpec> {
    vec![
        cmd!(
            "object.pathfinder.unite",
            "Unite",
            ["Window", "Pathfinder"],
            None,
            "{ids?: [id…] (selected first; default: the selection), precision?: pt 0.001..10, removeRedundantPoints?: bool, removeUnpainted?: bool (default: the Pathfinder Options, see object.pathfinder.options; the values used join the journal entry)} operate on the selected objects (back → front) → {ids, warning?: when a selected object is or holds a line or another open path that encloses no area once closed, and so does not change the result's shape (when such a path leaves the result empty, as in Intersect, the error says so)}",
            has_selection,
            |s, p| run_pf(s, p, PathfinderOp::Unite)
        ),
        cmd!(
            "object.pathfinder.minusFront",
            "Minus Front",
            ["Window", "Pathfinder"],
            None,
            "{ids?: [id…] (selected first; default: the selection), precision?: pt 0.001..10, removeRedundantPoints?: bool, removeUnpainted?: bool (default: the Pathfinder Options, see object.pathfinder.options; the values used join the journal entry)} operate on the selected objects (back → front) → {ids, warning?: when a selected object is or holds a line or another open path that encloses no area once closed, and so does not change the result's shape (when such a path leaves the result empty, as in Intersect, the error says so)}",
            has_selection,
            |s, p| run_pf(s, p, PathfinderOp::MinusFront)
        ),
        cmd!(
            "object.pathfinder.intersect",
            "Intersect",
            ["Window", "Pathfinder"],
            None,
            "{ids?: [id…] (selected first; default: the selection), precision?: pt 0.001..10, removeRedundantPoints?: bool, removeUnpainted?: bool (default: the Pathfinder Options, see object.pathfinder.options; the values used join the journal entry)} operate on the selected objects (back → front) → {ids, warning?: when a selected object is or holds a line or another open path that encloses no area once closed, and so does not change the result's shape (when such a path leaves the result empty, as in Intersect, the error says so)}",
            has_selection,
            |s, p| run_pf(s, p, PathfinderOp::Intersect)
        ),
        cmd!(
            "object.pathfinder.exclude",
            "Exclude",
            ["Window", "Pathfinder"],
            None,
            "{ids?: [id…] (selected first; default: the selection), precision?: pt 0.001..10, removeRedundantPoints?: bool, removeUnpainted?: bool (default: the Pathfinder Options, see object.pathfinder.options; the values used join the journal entry)} operate on the selected objects (back → front) → {ids, warning?: when a selected object is or holds a line or another open path that encloses no area once closed, and so does not change the result's shape (when such a path leaves the result empty, as in Intersect, the error says so)}",
            has_selection,
            |s, p| run_pf(s, p, PathfinderOp::Exclude)
        ),
        cmd!(
            "object.pathfinder.divide",
            "Divide",
            ["Window", "Pathfinder"],
            None,
            "{ids?: [id…] (selected first; default: the selection), precision?: pt 0.001..10, removeRedundantPoints?: bool, removeUnpainted?: bool (default: the Pathfinder Options, see object.pathfinder.options; the values used join the journal entry)} operate on the selected objects (back → front) → {ids}",
            has_selection,
            |s, p| run_pf(s, p, PathfinderOp::Divide)
        ),
        cmd!(
            "object.pathfinder.trim",
            "Trim",
            ["Window", "Pathfinder"],
            None,
            "{ids?: [id…] (selected first; default: the selection), precision?: pt 0.001..10, removeRedundantPoints?: bool, removeUnpainted?: bool (default: the Pathfinder Options, see object.pathfinder.options; the values used join the journal entry)} operate on the selected objects (back → front) → {ids}",
            has_selection,
            |s, p| run_pf(s, p, PathfinderOp::Trim)
        ),
        cmd!(
            "object.pathfinder.merge",
            "Merge",
            ["Window", "Pathfinder"],
            None,
            "{ids?: [id…] (selected first; default: the selection), precision?: pt 0.001..10, removeRedundantPoints?: bool, removeUnpainted?: bool (default: the Pathfinder Options, see object.pathfinder.options; the values used join the journal entry)} operate on the selected objects (back → front) → {ids}",
            has_selection,
            |s, p| run_pf(s, p, PathfinderOp::Merge)
        ),
        cmd!(
            "object.pathfinder.crop",
            "Crop",
            ["Window", "Pathfinder"],
            None,
            "{ids?: [id…] (selected first; default: the selection), precision?: pt 0.001..10, removeRedundantPoints?: bool, removeUnpainted?: bool (default: the Pathfinder Options, see object.pathfinder.options; the values used join the journal entry)} operate on the selected objects (back → front) → {ids}",
            has_selection,
            |s, p| run_pf(s, p, PathfinderOp::Crop)
        ),
        cmd!(
            "object.pathfinder.outline",
            "Outline",
            ["Window", "Pathfinder"],
            None,
            "{ids?: [id…] (selected first; default: the selection), precision?: pt 0.001..10, removeRedundantPoints?: bool, removeUnpainted?: bool (default: the Pathfinder Options, see object.pathfinder.options; the values used join the journal entry)} operate on the selected objects (back → front) → {ids}",
            has_selection,
            |s, p| run_pf(s, p, PathfinderOp::Outline)
        ),
        cmd!(
            "object.pathfinder.minusBack",
            "Minus Back",
            ["Window", "Pathfinder"],
            None,
            "{ids?: [id…] (selected first; default: the selection), precision?: pt 0.001..10, removeRedundantPoints?: bool, removeUnpainted?: bool (default: the Pathfinder Options, see object.pathfinder.options; the values used join the journal entry)} operate on the selected objects (back → front) → {ids, warning?: when a selected object is or holds a line or another open path that encloses no area once closed, and so does not change the result's shape (when such a path leaves the result empty, as in Intersect, the error says so)}",
            has_selection,
            |s, p| run_pf(s, p, PathfinderOp::MinusBack)
        ),
        cmd!(
            "object.pathfinder.trap",
            "Trap…",
            ["Window", "Pathfinder"],
            None,
            "{ids?: [id…] (selected first; default: the selection), thickness?: pt 0.01..5000 (0.25; how far the lighter colour reaches into the darker one across vertical edges), heightWidth?: % 1..1000 (100; the reach across horizontal edges as a percentage of the vertical one), tintReduction?: % 0..100 (40; the trap paints the lighter colour at this percentage of its tint), trapsWithProcessColor?: bool (false; a swatch (spot) colour's trap is painted with its CMYK process equivalent), reverseTraps?: bool (false; the darker colour spreads into the lighter one, except a rich black)} adds overprinting traps where the selected objects' visible areas of different solid colours meet, grouped directly above the topmost selected object and selected; the objects stay as they are → {ids}",
            has_selection,
            trap
        ),
        cmd!(
            "object.pathfinder.options",
            "Pathfinder Options…",
            ["Window", "Pathfinder"],
            None,
            "{precision?: pt 0.001..10 (0.01; how closely the Pathfinder operations follow the paths: results are refit to within it and pieces thinner than it are dropped), removeRedundantPoints?: bool (false; the results lose the anchors that don't change their shape), removeUnpainted?: bool (false; Divide and Outline leave out the pieces of objects with no fill)} Pathfinder Options, kept in the preferences and used by every later Shape Mode and Pathfinder operation (not Trap); {} reads them → the options",
            always,
            pathfinder_options
        ),
        cmd!(
            "object.path.outlineStroke",
            "Outline Stroke",
            ["Object", "Path"],
            None,
            "{} replace stroked paths with filled outlines; a dimension whose lines are outlined becomes a plain group of its art, except one selected with art it measures, directly or in groups without fills, strokes or effects of their own: its lines stay as they are, and if the outlined art no longer fits its link it stays where it was, no longer linked → {ids}",
            has_selection,
            outline_stroke
        ),
        cmd!(
            "object.path.offsetPath",
            "Offset Path…",
            ["Object", "Path"],
            None,
            "{offset: pt (negative insets), joins?: \"miter\"|\"round\"|\"bevel\", miterLimit?: 4} → {ids} (new objects above the originals)",
            has_selection,
            offset_path
        ),
        cmd!(
            "object.path.simplify",
            "Simplify…",
            ["Object", "Path"],
            None,
            "{tolerance?: pt (1), level?: 0..100 (the Simplify slider, in place of tolerance: 0 fewest anchor points, 50 is 1 pt, every 10 levels halves or doubles it), auto?: bool (Auto-Simplify: the lowest level whose tolerance is at most 1/400 of the selection's longer side, or 100 when that side is under 12.5 pt), cornerAngle?: deg (30), straightLines?: bool, wholePaths?: bool (false: a path with segments direct-selected, or between direct-selected anchors, simplifies only each run of them between its end anchors, which stay as they are, and keeps the runs selected; true simplifies those paths whole)} → {ids, before, after} anchor counts, and the level used with level or auto",
            has_selected_path,
            simplify
        ),
        cmd!(
            "object.path.smooth",
            "Smooth…",
            ["Object", "Path"],
            None,
            "{level?: 0..100 (50; the Smooth slider: 0 minimum smoothing, the path staying within 0.1% of its longer side, 100 maximum: smoothed along its length by up to 5% of it and refitted with curves within up to 2.5% of it, corners kept only where the path turns back, never with more anchor points), auto?: bool (Auto-Smooth: level 50), ids?: [id…] (default: the selection)} smooth each path under the objects, compound path members included, as one undo step; without ids, a path with anchor points or segments direct-selected smooths only the sections between them, which stay selected → {ids, before, after} anchor counts, and the level used",
            has_selected_path,
            smooth
        ),
        cmd!("object.path.addAnchorPoints", "Add Anchor Points", ["Object", "Path"], None, "{} → {ids}", has_selected_path, add_anchor_points),
        cmd!(
            "object.path.divideObjectsBelow",
            "Divide Objects Below",
            ["Object", "Path"],
            None,
            "{} cut the objects below with the selected path (which is removed) → {ids}",
            has_selected_path,
            divide_objects_below
        ),
        cmd!(
            "object.path.splitIntoGrid",
            "Split Into Grid…",
            ["Object", "Path"],
            None,
            "{rows?: 2, columns?: 2, gutter?: pt (12; rowGutter?, columnGutter?: one of the two), totalHeight?, totalWidth?: pt (the grid's size; the selected paths' when left out), height?, width?: pt (each row's and column's size, which then sets the total), addGuides?: false (ruler guides along the row and column edges)} one grid of rectangles over the selected paths replaces them, painted as the topmost one → {ids, guides: count}",
            has_selected_path,
            split_into_grid
        ),
        cmd!(
            "object.path.cleanUp",
            "Clean Up…",
            ["Object", "Path"],
            None,
            "{strayPoints?: true, unpaintedObjects?: true, emptyTextPaths?: true} → {removed}",
            has_doc,
            clean_up
        ),
    ]
}

// ---------- helpers ----------

/// Number param that also accepts strings like `"10 pt"`.
pub(crate) fn num_param(p: &Value, key: &str) -> Option<f64> {
    match p.get(key)? {
        Value::Number(n) => n.as_f64(),
        Value::String(s) => {
            let t: String = s.trim().chars().take_while(|c| c.is_ascii_digit() || matches!(c, '.' | '-' | '+' | 'e' | 'E')).collect();
            t.parse().ok()
        }
        _ => None,
    }
    .filter(|v: &f64| v.is_finite())
}

/// A distance param in points: a number, or a string with a unit (`"5 mm"`; bare numbers are
/// points).
pub(crate) fn len_param(p: &Value, key: &str) -> Option<f64> {
    match p.get(key)? {
        Value::String(s) => vectorcraft_doc::Unit::Points.parse(s).filter(|v| v.is_finite()).or_else(|| num_param(p, key)),
        _ => num_param(p, key),
    }
}

/// The number `p` gives `cmd` for `key`, or `None` when `p` leaves it out or gives null. A string
/// counts only when all of it is a number (`"20"`). Any other value, such as `true`, `"wide"` or
/// `"20abc"`, is an error: "`{key}` must be a number, not {v}".
pub(crate) fn number_given(p: &Value, key: &str, cmd: &str) -> Result<Option<f64>> {
    match p.get(key) {
        None | Some(Value::Null) => Ok(None),
        Some(v) => match v {
            Value::String(s) => whole_number(s),
            _ => num_param(p, key),
        }
        .map(Some)
        .ok_or_else(|| bad(cmd, format!("`{key}` must be a number, not {v}"))),
    }
}

/// The distance `p` gives `cmd` for `key`, or `None` when `p` leaves it out or gives null. A string
/// counts only when all of it is a length that [`vectorcraft_doc::Unit::parse`] reads (`"5 mm"`) or a
/// number. Any other value, such as `"20abc"`, is an error, as [`number_given`] gives it.
pub(crate) fn length_given(p: &Value, key: &str, cmd: &str) -> Result<Option<f64>> {
    match p.get(key) {
        None | Some(Value::Null) => Ok(None),
        Some(v) => match v {
            Value::String(s) => vectorcraft_doc::Unit::Points.parse(s).filter(|v| v.is_finite()).or_else(|| whole_number(s)),
            _ => num_param(p, key),
        }
        .map(Some)
        .ok_or_else(|| bad(cmd, format!("`{key}` must be a number, not {v}"))),
    }
}

/// `s` as a finite number when all of it, spaces around it aside, is one.
fn whole_number(s: &str) -> Option<f64> {
    s.trim().parse::<f64>().ok().filter(|v| v.is_finite())
}

fn ids_json(ids: &[NodeId]) -> Value {
    json!({ "ids": ids.iter().map(|i| i.0).collect::<Vec<_>>() })
}

/// Paint identity carried through a Pathfinder operation.
#[derive(Clone, Debug, PartialEq)]
pub(crate) struct Style {
    appearance: Appearance,
    opacity: f32,
    blend: BlendMode,
}

impl Style {
    fn of(n: &Node) -> Self {
        Style { appearance: (*n.appearance).clone(), opacity: n.opacity, blend: n.blend }
    }
    pub(crate) fn apply(&self, n: &mut Node) {
        n.appearance = self.appearance.clone().into();
        n.opacity = self.opacity;
        n.blend = self.blend;
    }
    /// The style of a shape drawn inside `n`: its opacity multiplied by `n`'s, and `n`'s blend
    /// mode when it is not Normal.
    pub(crate) fn within(self, n: &Node) -> Self {
        let blend = if n.blend == BlendMode::Normal { self.blend } else { n.blend };
        Style { opacity: self.opacity * n.opacity, blend, ..self }
    }
}

/// The Shape Mode commands' warning, which the status bar shows, when a selected object is or holds
/// a line or another open path that encloses no area once closed, and so does not change the result's
/// shape (the result still takes its paint from the frontmost object, as without the warning).
pub const SHAPE_MODE_OPEN_PATH_NO_AREA: &str = "a line or other open path that encloses no area does not change the result's shape; to include it, apply Object › Path › Outline Stroke to it first";

/// `path` has an open subpath that encloses no area once closed (a straight line, or an evenodd
/// contour traced twice), by the area its fill rule gives, so a self-crossing path whose signed
/// area is zero (a bow tie) still counts as enclosing area, as Divide measures it.
fn has_open_subpath_without_area(path: &PathData, rule: FillRule) -> bool {
    path.subpaths.iter().filter(|sp| !sp.closed).any(|sp| {
        // A point or a straight two-anchor line needs no area measurement.
        if sp.anchors.len() < 2 || (sp.anchors.len() == 2 && sp.anchors.iter().all(|a| a.h_in == a.p && a.h_out == a.p)) {
            return true;
        }
        let mut closed = sp.clone();
        closed.closed = true;
        // The signed-area test alone only holds for nonzero: evenodd can fill nothing where the
        // signed area is not zero (a contour traced twice).
        !(rule == FillRule::NonZero && po::encloses_area(sp)) && po::area(&PathData::single(closed), rule) <= 0.0
    })
}

/// The area `path` fills with its open subpaths closed, as the Shape Modes fill it.
fn closed_area(path: &PathData, rule: FillRule) -> f64 {
    let mut closed = path.clone();
    for sp in &mut closed.subpaths {
        sp.closed = true;
    }
    po::area(&closed, rule)
}

/// All subpaths of a path or compound path node, in document coordinates, with its fill rule.
pub(crate) fn node_path(n: &Node) -> Option<(PathData, FillRule)> {
    match &n.kind {
        NodeKind::Path { path, rule, .. } => Some((path.clone(), *rule)),
        NodeKind::Compound { children, rule } => {
            let mut subs = vec![];
            for c in children {
                if let Some((p, _)) = node_path(c) {
                    subs.extend(p.subpaths);
                }
            }
            Some((PathData::new(subs), *rule))
        }
        NodeKind::Text(t) => Some((text_outline(t), FillRule::NonZero)),
        _ => None,
    }
}

/// Glyph outlines of a text object in document coordinates.
pub(crate) fn text_outline(t: &TextObject) -> PathData {
    let lay = vectorcraft_text::layout(vectorcraft_text::FontDb::global(), t);
    PathData::from_bezpath(&lay.to_bezpath()).transformed(t.xf)
}

pub(crate) fn style_of(n: &Node) -> Style {
    match &n.kind {
        NodeKind::Text(t) => Style { appearance: t.first_style().appearance(), opacity: n.opacity, blend: n.blend },
        _ => Style::of(n),
    }
}

/// Leaf shapes (paths, compound paths, text) of a subtree in paint order; guides and clipping
/// paths are skipped.
pub(crate) fn leaves(n: &Node, out: &mut Vec<Node>) {
    each_leaf(n, &mut |l| out.push(l.clone()));
}

/// Calls `f` with each leaf shape of [`leaves`], in its order.
fn each_leaf(n: &Node, f: &mut impl FnMut(&Node)) {
    match &n.kind {
        NodeKind::Path { guide: true, .. } | NodeKind::Path { clipping: true, .. } => {}
        NodeKind::Path { .. } | NodeKind::Compound { .. } | NodeKind::Text(_) => f(n),
        NodeKind::Group { children, .. } | NodeKind::Layer { children, .. } => {
            for c in children {
                each_leaf(c, f);
            }
        }
        _ => {}
    }
}

/// [`leaves`] as a Pathfinder operation takes them: a compound shape is one shape, the area it
/// draws painted as it is, with the symbol instances among its members as their symbols' art from
/// `d` (its members as they are past a live Pathfinder's budget).
pub(crate) fn pf_leaves(d: &Document, n: &Node, out: &mut Vec<Node>) {
    match &n.kind {
        NodeKind::Group { children, .. } | NodeKind::Layer { children, .. } => {
            let hook = |c: &Node| vectorcraft_render::effects::outline_object(Some(d), c);
            match vectorcraft_render::effects::compound_shape_art(Some(d), n, Some(&hook)) {
                Some(art) => out.push(art),
                None => children.iter().for_each(|c| pf_leaves(d, c, out)),
            }
        }
        _ => leaves(n, out),
    }
}

/// The region a clip group's members show through: its clipping path's outline
/// ([`vectorcraft_render::effects::clip_outline`]), cut by the clip groups around it.
struct Clip {
    path: PathData,
    rule: FillRule,
}

/// Does `path` have an anchor or handle that isn't a finite number?
fn has_invalid_coordinates(path: &PathData) -> bool {
    path.subpaths.iter().flat_map(|sp| &sp.anchors).any(|a| [a.p, a.h_in, a.h_out].iter().any(|q| !(q.x.is_finite() && q.y.is_finite())))
}

/// A Pathfinder operation's leaf shape ([`pf_leaves`]) with the region its clip groups show it
/// through, `None` outside any clip group.
type ClippedLeaf = (Node, Option<Arc<Clip>>);

/// [`pf_leaves`], each with the region the clip groups it is in show it through (#8093). A clip
/// group's clipping path is not a leaf, and the members of one whose clipping path clips by nothing
/// are hidden, as on the canvas: their region is empty.
fn clipped_pf_leaves(d: &Document, n: &Node, clip: Option<&Arc<Clip>>, precision: f64, out: &mut Vec<ClippedLeaf>) -> Result<()> {
    let (NodeKind::Group { children, clip: clips } | NodeKind::Layer { children, clip: clips, .. }) = &n.kind else {
        let mut lv = vec![];
        leaves(n, &mut lv);
        out.extend(lv.into_iter().map(|l| (l, clip.cloned())));
        return Ok(());
    };
    let hook = |c: &Node| vectorcraft_render::effects::outline_object(Some(d), c);
    if let Some(art) = vectorcraft_render::effects::compound_shape_art(Some(d), n, Some(&hook)) {
        out.push((art, clip.cloned()));
        return Ok(());
    }
    if !*clips {
        return children.iter().try_for_each(|c| clipped_pf_leaves(d, c, clip, precision, out));
    }
    let Some((first, rest)) = children.split_first() else { return Ok(()) };
    let mut region = match vectorcraft_render::effects::clip_outline(first) {
        Some((outline, rule)) => Clip { path: PathData::from_bezpath(&outline), rule },
        None => Clip { path: PathData::default(), rule: FillRule::NonZero },
    };
    if has_invalid_coordinates(&region.path) {
        return Err(EngineError::Other("paths contain invalid coordinates".into()));
    }
    if let Some(outer) = clip.filter(|_| !region.path.is_empty()) {
        let path = po::try_boolean(&region.path, region.rule, &outer.path, outer.rule, BoolOp::Intersect, precision)
            .map_err(|e| EngineError::Other(e.to_string()))?;
        region = Clip { path, rule: FillRule::NonZero };
    }
    let region = Arc::new(region);
    rest.iter().try_for_each(|c| clipped_pf_leaves(d, c, Some(&region), precision, out))
}

/// `path`, filled by `rule`, where `clip` shows it: its area intersected with the region, filled
/// non-zero, and with `lines` (Divide, whose open contours cut) its open contours' parts inside the
/// region, so their hidden parts cut nothing.
fn clipped(path: PathData, rule: FillRule, clip: &Clip, lines: bool, precision: f64) -> Result<(PathData, FillRule)> {
    if has_invalid_coordinates(&path) {
        // Left as it is for the operation to refuse ("paths contain invalid coordinates").
        return Ok((path, rule));
    }
    let (Some(within), Some(bounds)) = (clip.path.control_bounds(), path.control_bounds()) else { return Ok((PathData::default(), rule)) };
    if within.intersect(bounds).is_zero_area() && !bounds.is_zero_area() {
        // Wholly outside the region (a line's bounds may be flat, so only an area's are trusted).
        return Ok((PathData::default(), rule));
    }
    let (open, closed): (Vec<SubPath>, Vec<SubPath>) =
        if lines { path.subpaths.into_iter().partition(|sp| !sp.closed) } else { (vec![], path.subpaths) };
    let mut subs = vec![];
    if !closed.is_empty() {
        let area = po::try_boolean(&PathData::new(closed), rule, &clip.path, clip.rule, BoolOp::Intersect, precision)
            .map_err(|e| EngineError::Other(e.to_string()))?;
        subs.extend(area.subpaths);
    }
    if !open.is_empty() {
        let open = PathData::new(open);
        // Each segment is sampled at least every 1/16 of the region's shorter side (and 24 times),
        // and the crossings found are refined: a part of the region narrower than that, which a
        // line crosses between two samples, can be missed.
        let step = (within.width().min(within.height()) / 16.0).max(precision);
        let outline = clip.path.to_bezpath();
        let outside = |q| !vectorcraft_geom::hit::fill_contains(&outline, clip.rule, q);
        match super::draw2::erase_outline(&open, step, &outside) {
            Some(pieces) => subs.extend(pieces.into_iter().flat_map(|p| p.subpaths)),
            None => subs.extend(open.subpaths),
        }
    }
    Ok((PathData::new(subs), FillRule::NonZero))
}

/// How many shapes a Pathfinder operation takes from `n` selected alone: its leaf shapes, however
/// deep its groups nest (an expanded stroke is a group inside the group, #1635). Inside a compound
/// shape, a blend, an envelope or another live object and a symbol instance count as one shape
/// each, as its area takes the art they draw.
pub fn shape_count(n: &Node) -> usize {
    // Counted without copying the shapes: the panel asks every frame.
    fn count(n: &Node, in_shape: bool, total: &mut usize) {
        match &n.kind {
            NodeKind::Group { children, .. } | NodeKind::Layer { children, .. } => {
                let in_shape = in_shape || n.is_compound_shape();
                for c in children {
                    count(c, in_shape, total);
                }
            }
            NodeKind::SymbolInstance { .. } if in_shape => *total += 1,
            _ if in_shape && vectorcraft_doc::live::is_live(n) => *total += 1,
            _ => each_leaf(n, &mut |_| *total += 1),
        }
    }
    let mut total = 0;
    count(n, false, &mut total);
    total
}

/// A node for `path`: a plain path for one subpath, else a compound path.
pub(crate) fn shape_node(d: &mut Document, path: PathData, style_src: Option<&Node>) -> Node {
    let id = d.alloc_id();
    let mut n = if path.subpaths.len() <= 1 {
        Node::path(id, path, Appearance::default())
    } else {
        let children = path
            .subpaths
            .into_iter()
            .map(|sp| {
                let cid = d.alloc_id();
                Arc::new(Node::path(cid, PathData::single(sp), Appearance::default()))
            })
            .collect();
        Node::new(id, NodeKind::Compound { children, rule: FillRule::NonZero })
    };
    if let Some(src) = style_src {
        Style::of(src).apply(&mut n);
    }
    n
}

fn shape_node_styled(d: &mut Document, path: PathData, style: &Style) -> Node {
    let mut n = shape_node(d, path, None);
    style.apply(&mut n);
    n
}

/// Whether `ids` are separate objects, as [`Document::remove_many`] and [`Document::insert_beside`]
/// take them: each one is in the tree and listed once, and none lies inside another listed one.
pub(crate) fn separate(d: &Document, ids: &[NodeId]) -> bool {
    let paths = d.index_paths(ids.iter().copied());
    let mut found: Vec<_> = ids.iter().filter_map(|id| paths.get(id)).collect();
    found.sort_unstable();
    found.len() == ids.len() && found.windows(2).all(|w| !w[1].starts_with(w[0]))
}

/// Lists of nodes that go in place of objects, or directly above them; an empty list in place of
/// an object removes it. When the objects are [`separate`], [`Beside::put`] holds each list and
/// leaves the tree as it is, and [`Beside::finish`] inserts them all in one pass over the children
/// of each parent ([`Document::insert_beside`]). Otherwise [`Beside::put`] inserts each list at
/// once, where its object is at that moment.
pub(crate) struct Beside {
    replace: bool,
    waiting: Option<Vec<(NodeId, Vec<Node>)>>,
}

impl Beside {
    /// Lists that go in place of objects among `ids`.
    pub(crate) fn replacing(d: &Document, ids: &[NodeId]) -> Self {
        Beside { replace: true, waiting: separate(d, ids).then(Vec::new) }
    }

    /// Lists that go directly above objects among `ids`.
    pub(crate) fn above(d: &Document, ids: &[NodeId]) -> Self {
        Beside { replace: false, waiting: separate(d, ids).then(Vec::new) }
    }

    /// Put `nodes`, in their order, in place of object `id` or directly above it.
    pub(crate) fn put(&mut self, d: &mut Document, id: NodeId, nodes: Vec<Node>) -> Result<()> {
        if let Some(waiting) = &mut self.waiting {
            waiting.push((id, nodes));
            return Ok(());
        }
        let (parent, idx, _) = d.position(id).ok_or(EngineError::NoNode(id))?;
        let at = if self.replace {
            d.remove(id)?;
            idx
        } else {
            idx + 1
        };
        for (k, n) in nodes.into_iter().enumerate() {
            d.insert(parent, at + k, n)?;
        }
        Ok(())
    }

    /// Insert the lists that [`Beside::put`] held.
    pub(crate) fn finish(self, d: &mut Document) -> Result<()> {
        match self.waiting {
            Some(waiting) if !waiting.is_empty() => Ok(d.insert_beside(waiting, self.replace)?),
            _ => Ok(()),
        }
    }
}

/// Remove `ids` through a [`Beside`], which removes them in one pass when they are [`separate`].
pub(crate) fn remove_each(d: &mut Document, ids: &[NodeId]) -> Result<()> {
    let mut gone = Beside::replacing(d, ids);
    for id in ids {
        gone.put(d, *id, vec![])?;
    }
    gone.finish(d)
}

// ---------- Pathfinder ----------

/// Pathfinder panel › Pathfinder Options (`object.pathfinder.options`, the `pathfinder` preference
/// group), which every Shape Mode and Pathfinder operation of the panel uses. The defaults leave
/// the results as they were before the options existed.
#[derive(Clone, Copy, Debug, PartialEq, serde::Serialize, serde::Deserialize)]
#[serde(default, rename_all = "camelCase")]
pub struct PathfinderOptions {
    /// How closely results follow the paths (pt): they are refit to within it and pieces thinner
    /// than it are dropped ([`po::pathfinder_with`]).
    pub precision: f64,
    /// Results lose the anchors that don't change their shape (to within `precision`).
    pub remove_redundant_points: bool,
    /// Divide and Outline leave out the pieces of objects with no fill.
    pub remove_unpainted: bool,
}

impl Default for PathfinderOptions {
    fn default() -> Self {
        Self { precision: po::DEFAULT_PRECISION, remove_redundant_points: false, remove_unpainted: false }
    }
}

/// The range of Pathfinder Options › Precision (pt).
pub const PATHFINDER_PRECISION_RANGE: std::ops::RangeInclusive<f64> = 0.001..=10.0;

impl PathfinderOptions {
    /// These options with those `p` names (`precision` in pt or a string with a unit), or why `p`
    /// can't set them.
    pub(crate) fn merged(&self, p: &Value) -> std::result::Result<Self, String> {
        let given = match p {
            Value::Null => return Ok(*self),
            Value::Object(given) => given,
            _ => return Err("`pathfinder` must be an object".into()),
        };
        let mut o = *self;
        for (key, v) in given {
            let flag = || v.as_bool().ok_or_else(|| format!("`{key}` must be true or false"));
            match key.as_str() {
                "precision" => {
                    o.precision =
                        len_param(p, key).filter(|v| PATHFINDER_PRECISION_RANGE.contains(v)).ok_or("precision must be from 0.001 to 10 pt")?;
                }
                "removeRedundantPoints" => o.remove_redundant_points = flag()?,
                "removeUnpainted" => o.remove_unpainted = flag()?,
                k => {
                    let path = "pathfinder";
                    return Err(format!("unknown option `{path}.{k}`"));
                }
            }
        }
        Ok(o)
    }
}

fn pathfinder_options(s: &mut Session, p: &Value) -> Result<Value> {
    s.prefs.pathfinder = s.prefs.pathfinder.merged(p).map_err(|e| bad("object.pathfinder.options", e))?;
    Ok(json!(s.prefs.pathfinder))
}

/// The last part of the id of `op`'s command (`object.pathfinder.…`).
fn pf_id(op: PathfinderOp) -> &'static str {
    match op {
        PathfinderOp::Unite => "unite",
        PathfinderOp::MinusFront => "minusFront",
        PathfinderOp::Intersect => "intersect",
        PathfinderOp::Exclude => "exclude",
        PathfinderOp::Divide => "divide",
        PathfinderOp::Trim => "trim",
        PathfinderOp::Merge => "merge",
        PathfinderOp::Crop => "crop",
        PathfinderOp::Outline => "outline",
        PathfinderOp::MinusBack => "minusBack",
        PathfinderOp::HardMix => "hardMix",
        PathfinderOp::SoftMix => "softMix",
    }
}

fn pf_label(op: PathfinderOp) -> &'static str {
    match op {
        PathfinderOp::Unite => "Unite",
        PathfinderOp::MinusFront => "Minus Front",
        PathfinderOp::Intersect => "Intersect",
        PathfinderOp::Exclude => "Exclude",
        PathfinderOp::Divide => "Divide",
        PathfinderOp::Trim => "Trim",
        PathfinderOp::Merge => "Merge",
        PathfinderOp::Crop => "Crop",
        PathfinderOp::Outline => "Outline",
        PathfinderOp::MinusBack => "Minus Back",
        PathfinderOp::HardMix => "Hard Mix",
        PathfinderOp::SoftMix => "Soft Mix",
    }
}

/// The Pathfinder Options an operation uses: those `p` gives, else the preferences'. They join the
/// command's journal entry, so replaying it gives the same result whatever the preferences are then.
fn pf_options(s: &mut Session, p: &Value, id: &str) -> Result<PathfinderOptions> {
    let mut stored = s.prefs.pathfinder;
    if !PATHFINDER_PRECISION_RANGE.contains(&stored.precision) {
        // A preferences file edited by hand: the default, rather than refitting everything away.
        stored.precision = po::DEFAULT_PRECISION;
    }
    let keys = ["precision", "removeRedundantPoints", "removeUnpainted"];
    let given: serde_json::Map<String, Value> =
        p.as_object().into_iter().flatten().filter(|(k, _)| keys.contains(&k.as_str())).map(|(k, v)| (k.clone(), v.clone())).collect();
    let options = stored.merged(&Value::Object(given)).map_err(|e| bad(id, e))?;
    s.note_journal("precision", json!(options.precision));
    s.note_journal("removeRedundantPoints", json!(options.remove_redundant_points));
    s.note_journal("removeUnpainted", json!(options.remove_unpainted));
    Ok(options)
}

fn run_pf(s: &mut Session, p: &Value, op: PathfinderOp) -> Result<Value> {
    let roots = selected_roots(s)?;
    if roots.is_empty() {
        return Err(EngineError::Other("nothing selected".into()));
    }
    let shape_mode =
        matches!(op, PathfinderOp::Unite | PathfinderOp::MinusFront | PathfinderOp::Intersect | PathfinderOp::Exclude | PathfinderOp::MinusBack);
    // An operand its clipping masks hide altogether is an empty shape for the operations whose
    // result it changes (Intersect gives nothing, Minus Front loses its back object, Minus Back its
    // front one, Crop its cropping shape); the others leave it out, which gives the same art.
    let keeps_hidden = matches!(op, PathfinderOp::Intersect | PathfinderOp::MinusFront | PathfinderOp::MinusBack | PathfinderOp::Crop);
    let label = pf_label(op);
    let options = pf_options(s, p, &format!("object.pathfinder.{}", pf_id(op)))?;
    let (ids, no_area) = s.edit(label, |d, sel| {
        // Build the stack (back → front); names are separate from paint/style identity.
        let mut no_area = false;
        let mut styles: Vec<Style> = vec![];
        let mut shapes: Vec<po::Shape> = vec![];
        let mut names: Vec<Option<String>> = vec![];
        // `hidden`: the masks hide the operand altogether, and its empty path stands for it.
        let mut push =
            |mut path: PathData, mut rule: FillRule, mut st: Style, name: Option<String>, clip: Option<&Clip>, hidden: bool| -> Result<()> {
                if path.is_empty() && !(hidden && keeps_hidden) {
                    return Ok(());
                }
                // Trim, Merge and Crop remove any strokes (and Merge then merges by fill alone), as the
                // public Pathfinder documentation describes.
                if matches!(op, PathfinderOp::Trim | PathfinderOp::Merge | PathfinderOp::Crop) {
                    st.appearance.items.retain(|i| !matches!(i, AppearanceItem::Stroke(_)));
                }
                if op == PathfinderOp::Divide && st.appearance.items.iter().any(|i| matches!(i, AppearanceItem::Fill(f) if !f.paint.is_none())) {
                    // Filled open contours keep their implicit closing edge. A zero-area line
                    // stays a cutter; normalised area also catches zero-signed-area self crossings.
                    for sub in path.subpaths.iter_mut().filter(|sp| !sp.closed) {
                        sub.closed = po::encloses_area(sub) || po::area(&PathData::single(sub.clone()), rule) > 0.0;
                    }
                }
                if let Some(clip) = clip {
                    (path, rule) = clipped(path, rule, clip, op == PathfinderOp::Divide, options.precision)?;
                    if path.is_empty() && !keeps_hidden {
                        return Ok(());
                    }
                }
                let key = match styles.iter().position(|x| *x == st) {
                    Some(k) => k,
                    None => {
                        styles.push(st);
                        styles.len() - 1
                    }
                };
                shapes.push(po::Shape::new(path, rule, key as u64));
                names.push(name);
                Ok(())
            };
        // Whether a clip group was among the selection, for the error when its mask hides it all.
        let mut masked = false;
        for id in &roots {
            let n = d.node(*id).ok_or(EngineError::NoNode(*id))?;
            let mut lv = vec![];
            clipped_pf_leaves(d, n, None, options.precision, &mut lv)?;
            masked |= lv.iter().any(|(_, clip)| clip.is_some());
            if lv.is_empty() {
                continue;
            }
            if shape_mode && roots.len() > 1 && lv.len() > 1 {
                // Among other objects, a group acts as one shape (the union of its leaves, each
                // where its clip groups show it) with the style of its top leaf that shows.
                // Selected alone, its members are the shapes (#1450).
                let mut parts: Vec<(&Node, PathData, FillRule)> = vec![];
                for (l, clip) in &lv {
                    let Some((p, r)) = node_path(l) else { continue };
                    let (p, r) = match clip {
                        Some(clip) => clipped(p, r, clip, false, options.precision)?,
                        None => (p, r),
                    };
                    if !p.is_empty() {
                        parts.push((l, p, r));
                    }
                }
                let name = n.name.clone().or_else(|| parts.iter().find_map(|(l, ..)| l.name.clone()));
                let Some((top, ..)) = parts.last() else {
                    // The masks hide the whole group.
                    if let Some((top, _)) = lv.last() {
                        push(PathData::default(), FillRule::NonZero, style_of(top), name, None, true)?;
                    }
                    continue;
                };
                let top = *top;
                no_area = no_area || parts.iter().any(|(_, p, r)| has_open_subpath_without_area(p, *r));
                let refs: Vec<(&PathData, FillRule)> = parts.iter().map(|(_, p, r)| (p, *r)).collect();
                push(
                    po::try_unite_all_with(&refs, options.precision).map_err(|e| EngineError::Other(e.to_string()))?,
                    FillRule::NonZero,
                    style_of(top),
                    name,
                    None,
                    false,
                )?;
            } else {
                for (l, clip) in &lv {
                    if let Some((p, r)) = node_path(l) {
                        no_area = no_area || (shape_mode && has_open_subpath_without_area(&p, r));
                        push(p, r, style_of(l), n.name.clone().or_else(|| l.name.clone()), clip.as_deref(), clip.is_some())?;
                    }
                }
            }
        }
        if shapes.is_empty() && masked {
            return Err(EngineError::Other(format!("{label}: the clipping masks hide the selected art")));
        }
        if shapes.is_empty() {
            return Err(EngineError::Other(format!("{label}: select paths, compound paths, groups or text")));
        }
        if shapes.iter().any(|s| s.path.subpaths.iter().any(|sp| sp.anchors.iter().any(|a| !(a.p.x.is_finite() && a.p.y.is_finite())))) {
            return Err(EngineError::Other("paths contain invalid coordinates".into()));
        }
        let mut results = po::pathfinder_with(op, &shapes, options.precision);
        if options.remove_unpainted && matches!(op, PathfinderOp::Divide | PathfinderOp::Outline) {
            // Pathfinder Options › Divide and Outline Will Remove Unpainted Artwork: the pieces
            // of objects with no fill (or only hidden ones) go.
            let filled = |st: &Style| st.appearance.items.iter().any(|i| matches!(i, AppearanceItem::Fill(f) if f.visible && !f.paint.is_none()));
            results.retain(|r| styles.get(r.key as usize).is_some_and(filled));
        }
        if options.remove_redundant_points {
            for r in &mut results {
                r.path = po::remove_redundant_points(&r.path, options.precision);
            }
        }
        if results.iter().all(|r| r.path.is_empty()) {
            // The lines left the result empty when the other shapes give a result without them, or
            // when nothing else is selected. A closed shape without area stays among the others.
            let lines_emptied = no_area && {
                let kept: Vec<po::Shape> = shapes
                    .iter()
                    .filter(|s| closed_area(&s.path, s.rule) > 0.0 || !has_open_subpath_without_area(&s.path, s.rule))
                    .cloned()
                    .collect();
                kept.is_empty() || po::pathfinder_with(op, &kept, options.precision).iter().any(|r| !r.path.is_empty())
            };
            if lines_emptied {
                return Err(EngineError::Other(format!(
                    "{label} produced an empty result: a line or other open path encloses no area; to include it, apply Object › Path › Outline Stroke to it first"
                )));
            }
            return Err(EngineError::Other(format!("{label} produced an empty result")));
        }
        let new_node = if shape_mode {
            let r =
                results.into_iter().find(|r| !r.path.is_empty()).ok_or_else(|| EngineError::Other(format!("{label} produced an empty result")))?;
            let style = styles.get(r.key as usize).ok_or_else(|| EngineError::Other(format!("{label}: lost track of a shape's style")))?;
            let mut n = shape_node_styled(d, r.path, style);
            n.name = match op {
                // A subtraction keeps its surviving source's identity, even when unnamed.
                PathfinderOp::MinusFront => names.first().cloned().flatten(),
                PathfinderOp::MinusBack => names.last().cloned().flatten(),
                _ => names.into_iter().flatten().next(),
            };
            n
        } else {
            let mut children = vec![];
            for r in results {
                if r.path.is_empty() {
                    continue;
                }
                let st = &styles[r.key as usize];
                let mut n = shape_node_styled(d, r.path, st);
                if op == PathfinderOp::Outline {
                    // Outline: open edges stroked with the face's former fill.
                    let fill = st.appearance.fill_paint();
                    let paint = if fill.is_none() { st.appearance.stroke_paint() } else { fill };
                    n.appearance = Appearance { items: vec![AppearanceItem::Stroke(StrokeLayer::new(paint, 1.0))], ..Default::default() }.into();
                }
                children.push(Arc::new(n));
            }
            let gid = d.alloc_id();
            Node::group(gid, children)
        };
        let nid = d.wrap(&roots, |_| new_node)?;
        sel.set([nid]);
        Ok((vec![nid], no_area))
    })?;
    let mut out = ids_json(&ids);
    if no_area {
        out["warning"] = json!(SHAPE_MODE_OPEN_PATH_NO_AREA);
    }
    Ok(out)
}

// ---------- Trap ----------

/// Pathfinder panel › Trap ([`vectorcraft_render::effects::trap`]): the traps between the selected
/// objects' leaf shapes, as one group of overprinting paths above the topmost selected object.
fn trap(s: &mut Session, p: &Value) -> Result<Value> {
    use vectorcraft_render::effects::trap::{TRAP_LABEL, TrapOptions, TrapSource, trap_appearance, try_traps};
    const ID: &str = "object.pathfinder.trap";
    let mut q = p.clone();
    if let Some(t) = length_given(p, "thickness", ID)? {
        if !(po::TRAP_MIN_WIDTH..=po::TRAP_MAX_WIDTH).contains(&t) {
            return Err(bad(ID, "thickness must be from 0.01 to 5000 pt"));
        }
        q["thickness"] = json!(t);
    }
    if number_given(p, "heightWidth", ID)?.is_some_and(|v| !(1.0..=1000.0).contains(&v)) {
        return Err(bad(ID, "heightWidth must be from 1 to 1000 %"));
    }
    if number_given(p, "tintReduction", ID)?.is_some_and(|v| !(0.0..=100.0).contains(&v)) {
        return Err(bad(ID, "tintReduction must be from 0 to 100 %"));
    }
    check_switches(p, &["trapsWithProcessColor", "reverseTraps"], ID)?;
    // The effect-only settings stay at their defaults.
    if let Some(o) = q.as_object_mut() {
        o.remove("precision");
        o.remove("removeRedundantPoints");
    }
    let options = TrapOptions::from_params(&q);
    let roots = selected_roots(s)?;
    if roots.is_empty() {
        return Err(EngineError::Other("nothing selected".into()));
    }
    let ids = s.edit(TRAP_LABEL, |d, sel| {
        let mut sources = vec![];
        for id in &roots {
            let n = d.node(*id).ok_or(EngineError::NoNode(*id))?;
            each_leaf(n, &mut |l| {
                if let Some((path, rule)) = node_path(l) {
                    sources.push(TrapSource { path, rule, fill: style_of(l).appearance.fill_paint() });
                }
            });
        }
        if sources.iter().filter(|s| s.fill.color().is_some()).count() < 2 {
            return Err(EngineError::Other("Trap: select two or more objects filled with solid colours".into()));
        }
        let Some(made) = try_traps(&sources, &options) else {
            return Err(EngineError::Other(format!(
                "Trap: more than {} pairs of objects lie close enough to trap, or too many objects share a horizontal range; trap fewer objects at a time",
                vectorcraft_render::effects::trap::MAX_NEAR_PAIRS
            )));
        };
        if made.is_empty() {
            return Err(EngineError::Other("Trap: no edges of different colours meet among the selected objects".into()));
        }
        let mut children = Vec::with_capacity(made.len());
        for piece in made {
            let mut n = shape_node(d, piece.path, None);
            n.appearance = trap_appearance(piece.paint).into();
            children.push(Arc::new(n));
        }
        let gid = d.alloc_id();
        let top = *roots.last().ok_or_else(|| EngineError::Other("nothing selected".into()))?;
        d.insert_beside(vec![(top, vec![Node::group(gid, children)])], false)?;
        sel.set([gid]);
        Ok(vec![gid])
    })?;
    Ok(ids_json(&ids))
}

// ---------- Offset Path ----------

fn join_param(p: &Value, key: &str, cmd: &str) -> Result<po::Join> {
    match text_param(p, key, cmd)?.map(str::to_ascii_lowercase).as_deref() {
        None | Some("miter") => Ok(po::Join::Miter),
        Some("round") => Ok(po::Join::Round),
        Some("bevel") => Ok(po::Join::Bevel),
        Some(_) => Err(bad(cmd, format!("`{key}` must be one of miter, round, bevel"))),
    }
}

fn offset_path(s: &mut Session, p: &Value) -> Result<Value> {
    const C: &str = "object.path.offsetPath";
    let delta = length_given(p, "offset", C)?.unwrap_or(10.0);
    if delta.abs() > 1e5 {
        return Err(bad(C, "offset out of range"));
    }
    let join = join_param(p, "joins", C)?;
    let miter = number_given(p, "miterLimit", C)?.unwrap_or(4.0).clamp(1.0, 500.0);
    let roots = selected_roots(s)?;
    let ids = s.edit("Offset Path", |d, sel| {
        // Each selected root, whether it is a group, and the style of each of its leaf paths; the
        // paths themselves go to `sources` in the same order.
        let (mut roots_found, mut sources) = (vec![], vec![]);
        for id in &roots {
            let Some(n) = d.node(*id) else { continue };
            let mut styles = vec![];
            each_leaf(n, &mut |l| {
                if !matches!(l.kind, NodeKind::Text(_))
                    && let Some((path, rule)) = node_path(l)
                {
                    styles.push(Style::of(l));
                    sources.push((path, rule, matches!(l.kind, NodeKind::Compound { .. })));
                }
            });
            roots_found.push((*id, matches!(n.kind, NodeKind::Group { .. }), styles));
        }
        let paths = !sources.is_empty();
        let offset = |(path, rule, compound): &(PathData, FillRule, bool)| {
            let normalized;
            let base = if *compound && path.is_closed() {
                normalized = po::normalize(path, *rule);
                &normalized
            } else {
                path
            };
            match po::try_offset_path(base, delta, join, miter) {
                Ok(p) => Ok(Some(p)),
                Err(po::PathOpsError::NonFinite) => Ok(None),
                Err(e) => Err(e),
            }
        };
        // The offsets are worked out together; the nodes are made here, in selection order, so
        // the ids, the stacking and the first error are those of one path after another.
        let (offsets, _) = ordered_map(&sources, offset_threads(), offset, std::result::Result::is_err);
        let mut offsets = offsets.into_iter();
        let (mut out, mut above) = (vec![], vec![]);
        for (id, group, styles) in roots_found {
            let mut made = vec![];
            for style in &styles {
                match offsets.next().flatten() {
                    Some(Ok(Some(off))) if !off.is_empty() => made.push(shape_node_styled(d, off, style)),
                    Some(Err(po::PathOpsError::TooComplex)) => {
                        return Err(EngineError::Other("Offset Path: the path is too complex to offset".into()));
                    }
                    Some(Err(e)) => return Err(EngineError::Other(format!("Offset Path: {e}"))),
                    _ => {}
                }
            }
            if made.is_empty() {
                continue;
            }
            let new = if made.len() == 1
                && !group
                && let Some(one) = made.pop()
            {
                one
            } else {
                let gid = d.alloc_id();
                Node::group(gid, made.into_iter().map(Arc::new).collect())
            };
            out.push(new.id);
            above.push((id, vec![new]));
        }
        if out.is_empty() && paths {
            return Err(EngineError::Other("Offset Path: the offset leaves nothing of the selected paths (an inset larger than the shapes)".into()));
        }
        if out.is_empty() {
            return Err(EngineError::Other("Offset Path: select paths".into()));
        }
        d.insert_beside(above, false)?;
        sel.set(out.iter().copied());
        Ok(out)
    })?;
    Ok(ids_json(&ids))
}

/// The threads [`offset_path`] works on: the logical CPUs, or one on the web.
fn offset_threads() -> usize {
    #[cfg(target_arch = "wasm32")]
    {
        1
    }
    #[cfg(not(target_arch = "wasm32"))]
    {
        std::thread::available_parallelism().map_or(1, std::num::NonZero::get)
    }
}

/// `f` of each of `items`, in their order. The items are split into runs whose sizes differ by
/// at most one, as many as `threads` or the items allow and at least one. This thread works
/// on the first run, and a thread of its own works on each other run (this thread does when that
/// one can't start). Once `stop` accepts a result, the items after it are left out (`None`); every
/// item before the first such result has its result. Returns the results and the number of
/// threads that worked on them.
pub(crate) fn ordered_map<T: Sync, R: Send>(
    items: &[T],
    threads: usize,
    f: impl Fn(&T) -> R + Sync,
    stop: impl Fn(&R) -> bool + Sync,
) -> (Vec<Option<R>>, usize) {
    use std::sync::atomic::{AtomicUsize, Ordering};
    let mut out: Vec<Option<R>> = std::iter::repeat_with(|| None).take(items.len()).collect();
    let stopped = AtomicUsize::new(usize::MAX);
    let run = |from: usize, its: &[T], out: &mut [Option<R>]| {
        for (i, (item, slot)) in its.iter().zip(out).enumerate() {
            let at = from + i;
            if at > stopped.load(Ordering::Relaxed) {
                return;
            }
            let r = f(item);
            if stop(&r) {
                stopped.fetch_min(at, Ordering::Relaxed);
            }
            *slot = Some(r);
        }
    };
    let runs = threads.clamp(1, items.len().max(1));
    if runs == 1 {
        run(0, items, &mut out);
        return (out, 1);
    }
    // Run `k` holds the items from `start(k)` up to `start(k + 1)`.
    let start = |k: usize| k * items.len() / runs;
    let mut unstarted = vec![];
    let used = std::thread::scope(|s| {
        let mut rest = out.as_mut_slice();
        let mut first = None;
        let mut used = 1;
        for k in 0..runs {
            let (from, to) = (start(k), start(k + 1));
            let Some((o, tail)) = std::mem::take(&mut rest).split_at_mut_checked(to - from) else { break };
            rest = tail;
            let its = items.get(from..to).unwrap_or_default();
            if k == 0 {
                first = Some((o, its));
                continue;
            }
            let run = &run;
            match std::thread::Builder::new().spawn_scoped(s, move || run(from, its, o)) {
                Ok(_) => used += 1,
                Err(_) => unstarted.push(k),
            }
        }
        if let Some((o, its)) = first {
            run(0, its, o);
        }
        used
    });
    for (from, to) in unstarted.into_iter().map(|k| (start(k), start(k + 1))) {
        if let (Some(o), Some(its)) = (out.get_mut(from..to), items.get(from..to)) {
            run(from, its, o);
        }
    }
    (out, used)
}

// ---------- Outline Stroke ----------

/// Can Outline Stroke turn `st` into filled art?
pub(crate) fn outlinable(st: &StrokeLayer) -> bool {
    st.visible && !st.paint.is_none() && st.width > 0.0
}

/// `n` with `opacity` and `blend` applied: set on it when it has none of its own, else on a
/// group around it.
pub(crate) fn with_transparency(d: &mut Document, mut n: Node, opacity: f32, blend: BlendMode) -> Node {
    if opacity >= 1.0 && blend == BlendMode::Normal {
        return n;
    }
    if n.opacity < 1.0 || n.blend != BlendMode::Normal {
        n = Node::group(d.alloc_id(), vec![Arc::new(n)]);
    }
    n.opacity = opacity;
    n.blend = blend;
    n
}

/// The art stroke `st` of a path (`path`, `rule`) paints, as fills: its brush art (with the
/// stroke's opacity, blend mode and raster effects), or the outline of the stroke (as on the canvas)
/// filled with the stroke's paint, opacity, blend mode and effects (a gradient along or across the stroke: gradient meshes in a clip group shaped
/// like the outline). `None` when it paints nothing.
pub(crate) fn outlined_stroke(
    d: &mut Document,
    brushes: &[vectorcraft_brush::Brush],
    path: &PathData,
    rule: FillRule,
    st: &StrokeLayer,
) -> Option<Node> {
    if let Some(b) = st.brush.as_deref().and_then(|name| brushes.iter().find(|b| b.name == name)) {
        let mut pieces = vectorcraft_brush::stroke_pieces(d, b, &path.to_bezpath(), st);
        let art = match pieces.len() {
            0 => return None,
            1 => pieces.remove(0),
            _ => Node::group(NodeId(0), pieces.into_iter().map(Arc::new).collect()),
        };
        let art = d.reid(&art);
        let mut art = with_transparency(d, art, st.opacity, st.blend);
        let raster = vectorcraft_render::effects::without_geometry(&st.effects);
        if !raster.is_empty() {
            if !art.appearance.effects.is_empty() {
                art = Node::group(d.alloc_id(), vec![Arc::new(art)]);
            }
            art.appearance.effects = raster;
        }
        return Some(art);
    }
    let outline = vectorcraft_render::effects::stroke::outline_region(path, rule, st);
    if outline.is_empty() {
        return None;
    }
    if let Some(g) = st.path_gradient() {
        // A gradient along or across the stroke: gradient meshes clipped to its outline.
        let meshes = vectorcraft_render::effects::stroke::gradient_meshes(&path.to_bezpath(), rule, st, &g.gradient);
        let mut clip = shape_node(d, outline, None);
        super::object::as_clipping_path(&mut clip).ok()?;
        let meshes: Vec<Node> = meshes.into_iter().map(|m| Node::new(d.alloc_id(), NodeKind::Mesh(m))).collect();
        let children = std::iter::once(clip).chain(meshes).map(Arc::new).collect();
        let group = Node::new(d.alloc_id(), NodeKind::Group { children, clip: true });
        let mut art = with_transparency(d, group, st.opacity, st.blend);
        art.appearance.effects = st.effects.clone();
        return Some(art);
    }
    let mut n = shape_node(d, outline, None);
    let fill = vectorcraft_doc::appearance::FillLayer {
        opacity: st.opacity,
        blend: st.blend,
        effects: st.effects.clone(),
        overprint: st.overprint,
        ..vectorcraft_doc::appearance::FillLayer::new(st.paint.stroke_as_fill())
    };
    n.appearance = Appearance { items: vec![AppearanceItem::Fill(fill)], ..Default::default() }.into();
    Some(n)
}

/// Path `l` with every stroke outlined, in appearance order: runs of fills stay on copies of
/// the path, each stroke becomes its outline (or brush art), grouped when there are several.
/// As on the canvas, the path's geometry effects ([`reshaped`]) shape the path first, and each
/// stroke's own geometry effects then shape the path that stroke outlines; [`outlined_stroke`]
/// gets the stroke without them. A fill with a random Transform effect paints the outline its
/// geometry effects make of the path, on a copy of its own. A path whose Transform effect copies
/// it with a gradient, or has Scale Strokes & Effects or Transform Patterns on, becomes the art the
/// canvas draws for it, each copy with its own gradient, stroke width and pattern, and its strokes
/// outlined before the art gets new ids. Random in a Transform effect takes its seed
/// from the object's id, so these effects give the outline the values the canvas drew. When the
/// geometry effects leave nothing to paint, an empty group takes the path's place.
/// `None` when `l` has no stroke to outline.
pub(crate) fn outline_strokes(d: &mut Document, brushes: &[vectorcraft_brush::Brush], l: &Node) -> Option<Node> {
    use vectorcraft_render::effects::{GeomContext, apply_geometry_carrying, has_geometry, has_transform_art, reshape, without_geometry};
    if !l.appearance.items.iter().any(|i| matches!(i, AppearanceItem::Stroke(st) if outlinable(st))) {
        return None;
    }
    if has_transform_art(l) {
        let mut art = reshape(Some(&*d), l, None)?;
        outline_member_strokes(d, brushes, &mut art);
        return Some(d.reid(&art));
    }
    let reshaped = reshaped(d, l);
    let l = reshaped.as_ref().unwrap_or(l);
    let (path, rule) = node_path(l)?;
    let ctx = GeomContext::of(l);
    // A fill belongs to the source path, whether open or closed. Converting its stroke
    // preserves that fill on a separate copy (including compound member geometry).
    let mut parts: Vec<Node> = vec![];
    let mut fills: Vec<AppearanceItem> = vec![];
    for item in &l.appearance.items {
        match item {
            AppearanceItem::Fill(f) if f.visible && !f.paint.is_none() => {
                let shaped = f.effects.iter().any(seeded).then(|| path.bounds().and_then(|b| fill_shape(d, l, item, &path, b))).flatten();
                let Some((shape, _, _, moved)) = shaped else {
                    fills.push(item.clone());
                    continue;
                };
                if !fills.is_empty() {
                    parts.push(styled_copy(d, l, std::mem::take(&mut fills)));
                }
                let mut plain = moved;
                *plain.effects_mut() = without_geometry(plain.effects());
                parts.push(styled_copy(d, &shape, vec![plain]));
            }
            AppearanceItem::Stroke(st) if outlinable(st) => {
                if !fills.is_empty() {
                    parts.push(styled_copy(d, l, std::mem::take(&mut fills)));
                }
                let mut plain = st.clone();
                let stroked = match path.bounds() {
                    Some(b) if has_geometry(&st.effects) => {
                        let (stroked, carry) = apply_geometry_carrying(&st.effects, &path, b, &ctx.item(item));
                        // Its raster effects follow only the Transform effects that moved it.
                        carry.hide_skipped(&mut plain.effects);
                        stroked
                    }
                    _ => path.clone(),
                };
                plain.effects = without_geometry(&plain.effects);
                parts.extend(outlined_stroke(d, brushes, &stroked, rule, &plain));
            }
            _ => {}
        }
    }
    if !fills.is_empty() {
        parts.push(styled_copy(d, l, fills));
    }
    let reshapes = reshaped.is_some()
        || l.appearance.items.iter().any(|i| matches!(i, AppearanceItem::Stroke(st) if outlinable(st) && has_geometry(&st.effects)));
    if parts.is_empty() && reshapes {
        // The geometry effects leave nothing to paint, as on the canvas: an empty group takes the path's place.
        parts.push(Node::group(d.alloc_id(), vec![]));
    }
    assemble(d, l, parts)
}

/// Outline the strokes of every member of group `n`, however deep ([`outline_strokes`]).
fn outline_member_strokes(d: &mut Document, brushes: &[vectorcraft_brush::Brush], n: &mut Node) {
    let Some(children) = n.children_mut() else { return };
    for c in children.iter_mut() {
        if let Some(o) = outline_strokes(d, brushes, c) {
            *c = Arc::new(o);
        } else if c.children().is_some() {
            outline_member_strokes(d, brushes, Arc::make_mut(c));
        }
    }
}

/// A plain copy of path `l` (new ids, no transparency, name or mask) painted with `items`.
/// The copy is shown and unlocked.
pub(crate) fn styled_copy(d: &mut Document, l: &Node, items: Vec<AppearanceItem>) -> Node {
    let mut f = d.reid(l);
    f.appearance = Appearance { items, ..Default::default() }.into();
    f.opacity = 1.0;
    f.blend = BlendMode::Normal;
    (f.visible, f.locked, f.knockout_shape) = (true, false, false);
    f.name = None;
    f.extras_mut().mask = None;
    if let NodeKind::Path { live, .. } = &mut f.kind {
        *live = None;
    }
    f
}

/// What stands for object `l` once its appearance became `parts` (paint order): the one part (in a
/// group when it has effects of its own) or a group of them, with `l`'s transparency, name, opacity
/// mask, effects, and hidden, locked and knockout-shape states. `None` without parts.
pub(crate) fn assemble(d: &mut Document, l: &Node, mut parts: Vec<Node>) -> Option<Node> {
    let root = match parts.len() {
        0 => return None,
        1 if parts[0].appearance.effects.is_empty() => parts.remove(0),
        _ => Node::group(d.alloc_id(), parts.into_iter().map(Arc::new).collect()),
    };
    let mut root = with_transparency(d, root, l.opacity, l.blend);
    (root.visible, root.locked, root.knockout_shape) = (l.visible, l.locked, l.knockout_shape);
    root.name = l.name.clone();
    root.extras_mut().mask = l.extras().mask.clone();
    root.appearance.effects = l.appearance.effects.clone();
    Some(root)
}

/// Outline the strokes of every path under `root` in place: → (the id now standing for `root`,
/// how many paths changed).
pub(crate) fn outline_strokes_under(d: &mut Document, brushes: &[vectorcraft_brush::Brush], root: NodeId) -> Result<(NodeId, usize)> {
    replace_leaves(d, root, |d, l| if matches!(l.kind, NodeKind::Text(_)) { None } else { outline_strokes(d, brushes, l) })
}

/// Replace each leaf shape under `root` ([`leaves`]) by what `f` makes of it (`None` keeps it):
/// → (the id now standing for `root`, how many leaves changed).
pub(crate) fn replace_leaves(d: &mut Document, root: NodeId, mut f: impl FnMut(&mut Document, &Node) -> Option<Node>) -> Result<(NodeId, usize)> {
    let Some(n) = d.node(root).cloned() else { return Ok((root, 0)) };
    let mut lv = vec![];
    leaves(&n, &mut lv);
    let (mut replacement, mut changed) = (root, 0);
    for l in lv {
        let Some(new) = f(d, &l) else { continue };
        let nid = new.id;
        *d.node_mut(l.id).ok_or(EngineError::NoNode(l.id))? = new;
        changed += 1;
        if l.id == root {
            replacement = nid;
        }
    }
    Ok((replacement, changed))
}

fn outline_stroke(s: &mut Session, _: &Value) -> Result<Value> {
    let roots = selected_roots(s)?;
    let ids = s.edit("Outline Stroke", |d, sel| {
        let before = d.clone();
        // Outlining the strokes in a graph does not move or scale its plot at the next redraw.
        let graphs = super::graph::graphs_holding(d, &roots);
        // A dimension selected with the art it measures keeps its own lines: it is out of the
        // document while the art is outlined.
        let lifted = super::dimension::lift(d, &roots);
        let kept = !lifted.is_empty();
        let ended = super::dimension::end_links(d, &roots);
        let brushes = vectorcraft_brush::library(d);
        let mut new_sel = vec![];
        let mut changed = 0;
        for root in &roots {
            let (id, n) = outline_strokes_under(d, &brushes, *root)?;
            new_sel.push(id);
            changed += n;
        }
        super::dimension::put_back(d, lifted);
        // A dimension whose source was outlined stays where it was, no longer linked.
        super::dimension::restore_unchanged(&before, d, ended);
        if changed == 0 || (kept && d.layers == before.layers) {
            return Err(EngineError::Other("Outline Stroke: no stroked paths selected".into()));
        }
        super::graph::keep_placed(d, &graphs);
        sel.set(new_sel.iter().copied());
        Ok(new_sel)
    })?;
    Ok(ids_json(&ids))
}

// ---------- Simplify / Add Anchor Points ----------

/// Ids of every plain path node under the selected roots (compound children included).
fn path_ids(d: &Document, roots: &[NodeId]) -> Vec<NodeId> {
    let mut out = vec![];
    for r in roots {
        if let Some(n) = d.node(*r) {
            n.walk(&mut |c| {
                if matches!(c.kind, NodeKind::Path { guide: false, .. }) {
                    out.push(c.id)
                }
            });
        }
    }
    out
}

/// The direct selection a path keeps after an edit of part of it: (its selected anchors, and its
/// selected segments when they were picked as segments). `None` selects the path whole.
type PartSelection = Option<(BTreeSet<AnchorRef>, Option<BTreeSet<SegmentRef>>)>;

/// Replace each path under `roots` ([`path_ids`]) by what `f` makes of it, given its
/// direct-selected anchors and picked segments (none when it is selected whole): → (their ids, how
/// many anchors they have before and after). A path that `f` would empty or returns unchanged is
/// left as it is, with its live shape and its direct selection; a replaced path loses its live
/// shape and has the direct selection `f` gives it.
fn edit_paths(
    s: &mut Session,
    roots: &[NodeId],
    label: &str,
    f: impl Fn(&PathData, Option<&BTreeSet<AnchorRef>>, Option<&BTreeSet<SegmentRef>>) -> (PathData, PartSelection),
) -> Result<(Vec<NodeId>, usize, usize)> {
    let st = s.doc()?;
    let (d, sel) = (&st.doc, &st.selection);
    let ids = path_ids(d, roots);
    if ids.is_empty() {
        return Err(EngineError::Other(format!("{label}: select paths")));
    }
    let (mut before, mut after, mut changed) = (0, 0, vec![]);
    for id in &ids {
        let Some(NodeKind::Path { path, .. }) = d.node(*id).map(|n| &n.kind) else { continue };
        before += path.anchor_count();
        let (np, part) = f(path, sel.anchors.get(id), sel.segments.get(id));
        if (np.is_empty() && !path.is_empty()) || np == *path {
            after += path.anchor_count();
            continue;
        }
        after += np.anchor_count();
        changed.push((*id, np, part));
    }
    // When no path changes, the document and its undo history stay as they are.
    if !changed.is_empty() {
        s.edit(label, |d, sel| {
            for (id, np, part) in changed {
                if let Some(NodeKind::Path { path, live, .. }) = d.node_mut(id).map(|n| &mut n.kind) {
                    // Refit and subdivision change what the old component indexes refer to: the
                    // path is selected whole, or with the part `f` says.
                    sel.anchors.remove(&id);
                    sel.segments.remove(&id);
                    if let Some((anchors, segments)) = part.filter(|(a, _)| a.len() < np.anchor_count()) {
                        sel.anchors.insert(id, anchors);
                        if let Some(segments) = segments {
                            sel.segments.insert(id, segments);
                        }
                    }
                    *path = np;
                    *live = None;
                }
            }
            Ok(())
        })?;
    }
    Ok((ids, before, after))
}

/// The segments of `path` a direct selection picks: the `segments` picked as such, or else every
/// segment with both its anchors among `anchors`. `None` when the path is selected whole, or when
/// no segment of it is selected.
fn selected_segments(
    path: &PathData,
    anchors: Option<&BTreeSet<AnchorRef>>,
    segments: Option<&BTreeSet<SegmentRef>>,
) -> Option<BTreeSet<SegmentRef>> {
    let anchors = anchors?;
    let picked: BTreeSet<SegmentRef> = match segments {
        Some(segs) => segs.iter().copied().filter(|&(si, i)| path.subpaths.get(si).is_some_and(|sp| i < sp.segment_count())).collect(),
        None => path
            .subpaths
            .iter()
            .enumerate()
            .flat_map(|(si, sp)| {
                (0..sp.segment_count())
                    .filter(move |&i| anchors.contains(&(si, i)) && anchors.contains(&(si, (i + 1) % sp.anchors.len())))
                    .map(move |i| (si, i))
            })
            .collect(),
    };
    (!picked.is_empty()).then_some(picked)
}

/// Auto-Simplify's level for the selection: [`po::auto_simplify_level`] for the longer side of the
/// selected objects' bounds. Object › Path › Simplify's slider opens at it, and
/// `object.path.simplify {auto: true}` simplifies at it.
pub fn auto_simplify_level(s: &Session) -> Result<f64> {
    let roots = selected_roots(s)?;
    let size = s.doc()?.doc.bounds_of(&roots, false).map_or(0.0, |b| b.width().max(b.height()));
    Ok(po::auto_simplify_level(size))
}

fn simplify(s: &mut Session, p: &Value) -> Result<Value> {
    const C: &str = "object.path.simplify";
    let (auto, given_level, given_tolerance) = (switch_or(p, "auto", false, C)?, number_given(p, "level", C)?, length_given(p, "tolerance", C)?);
    let corner_angle = number_given(p, "cornerAngle", C)?.unwrap_or(30.0).clamp(0.0, 180.0);
    let (straight_lines, whole) = (switch_or(p, "straightLines", false, C)?, switch_or(p, "wholePaths", false, C)?);
    // With auto, the slider's level is Auto-Simplify's for the selection's size; otherwise it is the level given.
    let level = if auto {
        Some(auto_simplify_level(s)?)
    } else {
        given_level.map(|l| if l.is_finite() { l.round().clamp(0.0, 100.0) } else { po::SIMPLIFY_LEVEL })
    };
    let tolerance = match level {
        Some(l) => po::simplify_level_tolerance(l),
        None => given_tolerance.unwrap_or(1.0),
    };
    let opts = po::SimplifyOptions { tolerance: tolerance.clamp(1e-4, 1e4), corner_angle_deg: corner_angle, straight_lines, ..Default::default() };
    // A path with segments direct-selected simplifies only their runs, and keeps those runs (and the
    // other anchors it had selected) direct-selected.
    let roots = selected_roots(s)?;
    let (ids, before, after) = edit_paths(s, &roots, "Simplify", |path, anchors, segments| {
        let Some(picked) = selected_segments(path, anchors, segments).filter(|_| !whole) else {
            return (po::simplify_with(path, &opts), None);
        };
        let part = po::simplify_part(path, &picked, &opts);
        refitted_part(part, anchors, segments)
    })?;
    let mut out = json!({ "ids": ids.iter().map(|i| i.0).collect::<Vec<_>>(), "before": before, "after": after });
    if let Some(l) = level {
        out["level"] = json!(l);
    }
    Ok(out)
}

/// A path with only the runs of `part` refitted, and what stays direct-selected: the anchors it had
/// selected that are still there, and the refitted runs (their anchors, and their segments when
/// segments were selected).
fn refitted_part(
    part: po::SimplifiedPart,
    anchors: Option<&BTreeSet<AnchorRef>>,
    segments: Option<&BTreeSet<SegmentRef>>,
) -> (PathData, PartSelection) {
    let mut kept: BTreeSet<AnchorRef> = anchors.into_iter().flatten().filter_map(|a| part.anchors.get(a).copied()).collect();
    for &(si, i) in &part.segments {
        let m = part.path.subpaths.get(si).map_or(1, |sp| sp.anchors.len().max(1));
        kept.extend([(si, i), (si, (i + 1) % m)]);
    }
    let segs = segments.map(|_| part.segments.clone());
    (part.path, Some((kept, segs)))
}

/// Object › Path › Smooth (`object.path.smooth`): [`po::smooth_level`] on each path under the
/// objects given or selected, as one undo step; Auto-Smooth (`auto`) uses [`po::SMOOTH_AUTO_LEVEL`].
/// A path with anchor points or segments direct-selected (and no `ids` given) smooths only the runs
/// between them, which stay selected, as Simplify does.
fn smooth(s: &mut Session, p: &Value) -> Result<Value> {
    const C: &str = "object.path.smooth";
    let level = number_or(p, "level", po::SMOOTH_AUTO_LEVEL, C)?.round().clamp(0.0, 100.0);
    let level = if switch_or(p, "auto", false, C)? { po::SMOOTH_AUTO_LEVEL } else { level };
    let given = p.get("ids").is_some_and(|v| !v.is_null());
    let roots = checked_ids_or_selection(s, p, C)?;
    let (ids, before, after) = edit_paths(s, &roots, "Smooth", |path, anchors, segments| {
        let Some(picked) = selected_segments(path, anchors, segments).filter(|_| !given) else {
            return (po::smooth_level(path, level), None);
        };
        refitted_part(po::simplify_part(path, &picked, &po::smooth_options(path, level)), anchors, segments)
    })?;
    Ok(json!({ "ids": ids.iter().map(|i| i.0).collect::<Vec<_>>(), "before": before, "after": after, "level": level }))
}

fn add_anchor_points(s: &mut Session, _: &Value) -> Result<Value> {
    let roots = selected_roots(s)?;
    let (ids, before, after) = edit_paths(s, &roots, "Add Anchor Points", |path, _, _| (po::add_anchor_points(path), None))?;
    Ok(json!({ "ids": ids.iter().map(|i| i.0).collect::<Vec<_>>(), "before": before, "after": after }))
}

// ---------- Split Into Grid ----------

/// One direction of the grid: the (gutter, total size) of `n` rows or columns. A `size` for each
/// makes the total; otherwise it is `total`, or `extent` (the selection's) when neither is given.
fn grid_axis(p: &Value, n: f64, [size, gutter, total]: [&str; 3], extent: f64) -> (f64, f64) {
    let gutter = len_param(p, gutter).or_else(|| len_param(p, "gutter")).unwrap_or(12.0).max(0.0);
    let total = match len_param(p, size) {
        Some(size) => n * size + (n - 1.0) * gutter,
        None => len_param(p, total).unwrap_or(extent),
    };
    (gutter, total)
}

fn split_into_grid(s: &mut Session, p: &Value) -> Result<Value> {
    const C: &str = "object.path.splitIntoGrid";
    let rows = number_given(p, "rows", C)?.unwrap_or(2.0).round();
    let cols = number_given(p, "columns", C)?.unwrap_or(2.0).round();
    if !(1.0..=500.0).contains(&rows) || !(1.0..=500.0).contains(&cols) {
        return Err(bad(C, "rows and columns must be 1..500"));
    }
    let add_guides = switch_or(p, "addGuides", false, C)?;
    // Each distance [`grid_axis`] reads is a number, a string with a unit or null, checked before the
    // selection, so a bad one is an error whatever is selected.
    for key in ["height", "rowGutter", "totalHeight", "width", "columnGutter", "totalWidth", "gutter"] {
        length_given(p, key, C)?;
    }
    let too_small = || EngineError::Other("Split Into Grid: select paths large enough for the grid".into());
    // The selected paths, back to front: one grid over them all replaces them, where the topmost
    // one was and painted as it is.
    let d = &s.doc()?.doc;
    let roots = selected_roots(s)?;
    let paths: Vec<&Node> =
        roots.iter().filter_map(|id| d.node(*id)).filter(|n| matches!(n.kind, NodeKind::Path { .. } | NodeKind::Compound { .. })).collect();
    let Some((top, below)) = paths.split_last().map(|(top, below)| (Node::clone(top), below.iter().map(|n| n.id).collect::<Vec<_>>())) else {
        return Err(too_small());
    };
    let Some(b) = paths.iter().filter_map(|n| n.geometric_bounds()).reduce(|a, b| a.union(b)) else { return Err(too_small()) };
    let (row_gutter, height) = grid_axis(p, rows, ["height", "rowGutter", "totalHeight"], b.height());
    let (col_gutter, width) = grid_axis(p, cols, ["width", "columnGutter", "totalWidth"], b.width());
    let (rows, cols) = (rows as usize, cols as usize);
    let cells = po::split_into_grid(vectorcraft_geom::Rect::new(b.x0, b.y0, b.x0 + width, b.y0 + height), rows, cols, (row_gutter, col_gutter));
    if cells.is_empty() {
        return Err(too_small());
    }
    let mut edges: Vec<(bool, f64)> = Vec::new();
    if add_guides {
        // Row-major cells: the first row has the column edges, each row's first cell the row edges.
        let bounds = cells.iter().filter_map(PathData::bounds);
        edges.extend(bounds.clone().take(cols).flat_map(|c| [(true, c.x0), (true, c.x1)]));
        edges.extend(bounds.step_by(cols).flat_map(|c| [(false, c.y0), (false, c.y1)]));
        // Without a gutter, neighbours share an edge.
        edges.dedup_by(|a, b| a.0 == b.0 && (a.1 - b.1).abs() < 1e-9);
    }
    let ids = s.edit("Split Into Grid", |d, sel| {
        d.remove_many(&below)?;
        let (par, idx, _) = d.position(top.id).ok_or(EngineError::NoNode(top.id))?;
        let layer = d.layer_containing(top.id);
        d.remove(top.id)?;
        let mut out = Vec::with_capacity(cells.len());
        for (k, c) in cells.into_iter().enumerate() {
            let node = shape_node(d, c, Some(&top));
            out.push(d.insert(par, idx + k, node)?);
        }
        for &(vertical, pos) in &edges {
            d.add_ruler_guide(&vectorcraft_doc::Guide { layer, ..vectorcraft_doc::Guide::new(vertical, pos) });
        }
        sel.set(out.iter().copied());
        Ok(out)
    })?;
    Ok(json!({ "ids": ids.iter().map(|i| i.0).collect::<Vec<_>>(), "guides": edges.len() }))
}

// ---------- Clean Up ----------

fn is_painted(a: &Appearance) -> bool {
    a.items.iter().any(|i| match i {
        AppearanceItem::Fill(f) => f.visible && !f.paint.is_none(),
        AppearanceItem::Stroke(s) => s.visible && !s.paint.is_none() && s.width > 0.0,
    })
}

fn clean_up(s: &mut Session, p: &Value) -> Result<Value> {
    const C: &str = "object.path.cleanUp";
    let stray = switch_or(p, "strayPoints", true, C)?;
    let unpainted = switch_or(p, "unpaintedObjects", true, C)?;
    let empty_text = switch_or(p, "emptyTextPaths", true, C)?;
    let found = {
        let d = &s.doc()?.doc;
        let mut v = vec![];
        fn visit(n: &Node, parent_compound: bool, parent_clip: bool, first: bool, v: &mut Vec<NodeId>, opts: (bool, bool, bool)) {
            let (stray, unpainted, empty_text) = opts;
            match &n.kind {
                NodeKind::Path { path, clipping, guide, .. } => {
                    if *guide || *clipping || (parent_clip && first) {
                        return;
                    }
                    if (stray && path.anchor_count() <= 1) || (unpainted && !parent_compound && !is_painted(&n.appearance)) {
                        v.push(n.id);
                    }
                }
                NodeKind::Compound { children, .. } => {
                    if unpainted && !(parent_clip && first) && !is_painted(&n.appearance) {
                        v.push(n.id);
                        return;
                    }
                    for c in children {
                        visit(c, true, false, false, v, opts);
                    }
                }
                NodeKind::Text(t) if empty_text && t.plain_text().trim().is_empty() => v.push(n.id),
                NodeKind::Layer { children, .. } => {
                    for c in children {
                        visit(c, false, false, false, v, opts);
                    }
                }
                NodeKind::Group { children, clip } => {
                    for (i, c) in children.iter().enumerate() {
                        visit(c, false, *clip, i == 0, v, opts);
                    }
                }
                _ => {}
            }
        }
        for l in &d.layers {
            visit(l, false, false, false, &mut v, (stray, unpainted, empty_text));
        }
        let editable = d.editable();
        v.retain(|id| editable(*id));
        v
    };
    if found.is_empty() {
        return Ok(json!({ "removed": 0 }));
    }
    s.edit("Clean Up", |d, _| {
        let mut gone = Beside::replacing(d, &found);
        for id in &found {
            if d.node(*id).is_some() {
                gone.put(d, *id, vec![])?;
            }
        }
        gone.finish(d)
    })?;
    Ok(json!({ "removed": found.len() }))
}

// ---------- Divide Objects Below ----------

fn divide_objects_below(s: &mut Session, _: &Value) -> Result<Value> {
    let roots = selected_roots(s)?;
    let [cutter_id] = roots[..] else { return Err(EngineError::Other("Divide Objects Below: select exactly one path".into())) };
    let ids = s.edit("Divide Objects Below", |d, sel| {
        let cutter = d.node(cutter_id).cloned().ok_or(EngineError::NoNode(cutter_id))?;
        let Some((cpath, crule)) = node_path(&cutter).filter(|_| !matches!(cutter.kind, NodeKind::Text(_))) else {
            return Err(EngineError::Other("Divide Objects Below: select a path".into()));
        };
        let Some(cb) = cpath.bounds() else { return Err(EngineError::Other("empty cutter".into())) };
        let cutter_pos = d.index_path(cutter_id).unwrap_or_default();
        let mut targets = vec![];
        for l in &d.layers {
            l.walk(&mut |n| {
                if let NodeKind::Path { path, guide: false, clipping: false, .. } = &n.kind
                    && path.is_closed()
                {
                    targets.push(n.id);
                }
                if matches!(n.kind, NodeKind::Compound { .. }) {
                    targets.push(n.id);
                }
            });
        }
        // Compound children are handled via their compound.
        targets.retain(|id| !matches!(d.parent_of(*id).and_then(|p| d.node(p)).map(|p| &p.kind), Some(NodeKind::Compound { .. })));
        let editable = d.editable();
        targets.retain(|id| {
            *id != cutter_id
                && editable(*id)
                && d.is_visible(*id)
                && d.index_path(*id).is_some_and(|ip| ip < cutter_pos)
                && d.node(*id).and_then(Node::geometric_bounds).is_some_and(|b| b.intersect(cb).area() > 0.0)
        });
        drop(editable);
        let mut out = vec![];
        let mut cut = Beside::replacing(d, &[targets.as_slice(), &[cutter_id]].concat());
        for t in targets {
            let Some(n) = d.node(t).cloned() else { continue };
            let Some((tp, tr)) = node_path(&n) else { continue };
            let inside = po::boolean(&tp, tr, &cpath, crule, BoolOp::Intersect);
            let outside = po::boolean(&tp, tr, &cpath, crule, BoolOp::Difference);
            if inside.is_empty() || outside.is_empty() {
                continue;
            }
            let pieces: Vec<Node> = [outside, inside].into_iter().map(|piece| shape_node(d, piece, Some(&n))).collect();
            out.extend(pieces.iter().map(|p| p.id));
            cut.put(d, t, pieces)?;
        }
        cut.put(d, cutter_id, vec![])?;
        cut.finish(d)?;
        sel.set(out.iter().copied());
        Ok(out)
    })?;
    Ok(ids_json(&ids))
}