Skip to main content

lexical_ui/
structure.rs

1//! `LexicalStructure.ts` (`@experimental node-structure`): the structural
2//! facts a node class declares in its `$config()` (`inline`, `children`,
3//! `mergeAdjacent`, and the values it declares `derived`), read along its
4//! config chain, and the normalization that `NodeStructureExtension`
5//! (`@lexical/extension`) turns on with [`internal_register_node_structure`].
6//!
7//! JS reads the declarations off each class's `$config()` and walks the
8//! class's prototype chain (`iterStaticNodeConfigChain`). A Rust node
9//! declares them with [`LexicalNode::static_node_config_chain`]: its own
10//! class's [`StaticNodeConfig`] first, then those of the classes it extends
11//! (a class names another in a `children` list by [`NodeClassRef`], and
12//! "allows its subclasses" means a node whose chain names that class). A
13//! class's own hooks (`INTERNAL_$afterStructureMerge`,
14//! `INTERNAL_$afterStructureSplit`, `INTERNAL_$liftsFromStructure`), which
15//! JS finds by name, are [`LexicalNode`] hooks too.
16//!
17//! Where JS tells whether a class writes its own `isInline()` or
18//! `isShadowRoot()` (a trait method can't tell an override), the port does
19//! what Swift does: every class but the root counts as one whose rule may
20//! differ between its nodes (rust/PARITY.md).
21
22use crate::caret_tree::insert_sibling;
23use crate::editor::Editor;
24use crate::editor_state::EditorStateInner;
25use crate::lexical_selection::{PointType, Which, get_selection};
26use crate::lexical_utils::{copy_node, get_node_by_key, get_root, set_node_key};
27use crate::node::{LexicalNode, NodeKey, NodeRef, remove_node};
28use crate::node_state::AnyStateConfig;
29use crate::nodes::element::{self, is_root_or_shadow_root};
30use crate::nodes::line_break::{LineBreakNode, create_line_break_node};
31use crate::nodes::paragraph::ParagraphNode;
32use crate::ordered::{OrderedMap, OrderedSet};
33use crate::updates::get_active_editor;
34use crate::{LexicalError, Unregister};
35use std::any::TypeId;
36use std::cell::{Cell, RefCell};
37use std::collections::{HashMap, HashSet};
38use std::rc::{Rc, Weak};
39
40// MARK: Declarations
41
42/// A node class that a `children` list names: its type, and how to make a
43/// node of it (`$create(klass)`, for the wrapper a list of classes wraps a
44/// stray child in).
45#[derive(Clone, Copy)]
46pub struct NodeClassRef {
47    node_type: &'static str,
48    new_node: fn() -> Box<dyn LexicalNode>,
49}
50
51fn new_node<T: LexicalNode + Default>() -> Box<dyn LexicalNode> {
52    Box::new(T::default())
53}
54
55impl NodeClassRef {
56    /// The class of `T`.
57    pub fn of<T: LexicalNode + Default>() -> Self {
58        Self {
59            node_type: T::default().get_type(),
60            new_node: new_node::<T>,
61        }
62    }
63
64    /// The class's type.
65    pub fn node_type(&self) -> &'static str {
66        self.node_type
67    }
68
69    fn chain(&self) -> Vec<NodeConfigLink> {
70        iter_static_node_config_chain(&*(self.new_node)())
71    }
72}
73
74impl PartialEq for NodeClassRef {
75    fn eq(&self, other: &Self) -> bool {
76        self.node_type == other.node_type
77    }
78}
79
80impl std::fmt::Debug for NodeClassRef {
81    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
82        write!(f, "NodeClassRef({:?})", self.node_type)
83    }
84}
85
86/// One entry of a `children` list: `'inline'`, or a class (which allows its
87/// subclasses).
88#[derive(Clone, Copy, Debug, PartialEq)]
89pub enum NodeChildEntry {
90    Inline,
91    Class(NodeClassRef),
92}
93
94/// `NodeChildrenConfig` (`@experimental node-structure`): what an element
95/// may hold. `Inline` is a paragraph's content, `Block` a table cell's, and
96/// `List` only the listed entries.
97#[derive(Clone, Debug, PartialEq)]
98pub enum NodeChildrenConfig {
99    Inline,
100    Block,
101    List(Vec<NodeChildEntry>),
102}
103
104impl NodeChildrenConfig {
105    fn entries(&self) -> Option<&[NodeChildEntry]> {
106        match self {
107            NodeChildrenConfig::List(entries) => Some(entries),
108            _ => None,
109        }
110    }
111
112    /// Whether it is `'inline'` or a list that names `'inline'`.
113    fn holds_inline(&self) -> bool {
114        match self {
115            NodeChildrenConfig::Inline => true,
116            NodeChildrenConfig::Block => false,
117            NodeChildrenConfig::List(entries) => entries.contains(&NodeChildEntry::Inline),
118        }
119    }
120}
121
122/// One value `mergeAdjacent.by` names: a schema field of the class (a
123/// property of its JSON), or a NodeState.
124#[derive(Clone, Debug)]
125pub enum MergeAdjacentEntry {
126    Field(&'static str),
127    State(AnyStateConfig),
128}
129
130/// `MergeAdjacentConfig` (`@experimental node-structure`).
131#[derive(Clone, Debug)]
132pub struct MergeAdjacentConfig {
133    /// Schema field names of the class, or NodeState configs.
134    pub by: Vec<MergeAdjacentEntry>,
135}
136
137/// A class's own `mergeAdjacent` declaration: `Off` is JS's `false`, which
138/// turns off a declaration an ancestor made.
139#[derive(Clone, Debug)]
140pub enum MergeAdjacentDeclaration {
141    By(Vec<MergeAdjacentEntry>),
142    Off,
143}
144
145/// The node-structure keys of one class's own `$config()`
146/// (`StaticNodeConfigValue`'s `inline`, `children` and `mergeAdjacent`).
147/// What it declares `derived` comes from its schema
148/// ([`LexicalNode::json_schema_chain`]) and its NodeState
149/// ([`LexicalNode::state_configs`]).
150#[derive(Clone, Debug, Default)]
151pub struct StaticNodeConfig {
152    pub inline: Option<bool>,
153    pub children: Option<NodeChildrenConfig>,
154    pub merge_adjacent: Option<MergeAdjacentDeclaration>,
155}
156
157/// One class of a config chain (`iterStaticNodeConfigChain`'s
158/// `{klass, ownNodeType, ownNodeConfig}`).
159#[derive(Clone, Debug)]
160pub struct NodeConfigLink {
161    pub node_type: &'static str,
162    pub config: StaticNodeConfig,
163}
164
165impl NodeConfigLink {
166    pub fn new(node_type: &'static str, config: StaticNodeConfig) -> Self {
167        Self { node_type, config }
168    }
169}
170
171/// `iterStaticNodeConfigChain(klass)`: the node's class and the classes it
172/// extends, most derived first ([`LexicalNode::static_node_config_chain`]),
173/// or the node's class alone, declaring nothing, for a class that gives no
174/// chain.
175pub fn iter_static_node_config_chain(node: &dyn LexicalNode) -> Vec<NodeConfigLink> {
176    let chain = node.static_node_config_chain();
177    if chain.is_empty() {
178        vec![NodeConfigLink::new(
179            node.get_type(),
180            StaticNodeConfig::default(),
181        )]
182    } else {
183        chain
184    }
185}
186
187/// The chain of a class that declares only `children: 'inline'` (a
188/// paragraph, a heading, a quote, a code block).
189pub(crate) fn inline_holder_chain(node_type: &'static str) -> Vec<NodeConfigLink> {
190    vec![NodeConfigLink::new(
191        node_type,
192        StaticNodeConfig {
193            children: Some(NodeChildrenConfig::Inline),
194            ..StaticNodeConfig::default()
195        },
196    )]
197}
198
199/// The class each key of a [`DeclaredNodeStructure`] came from, by type.
200#[derive(Clone, Debug, Default, PartialEq)]
201pub struct DeclaredBy {
202    pub inline: Option<&'static str>,
203    pub children: Option<&'static str>,
204    pub merge_adjacent: Option<&'static str>,
205}
206
207/// `DeclaredNodeStructure` (`@experimental node-structure`): the structural
208/// facts a class declares, each from the nearest class in its config chain
209/// that declares it, and the values it declares derived. Keys no class
210/// declares are `None`; a `mergeAdjacent: false` declaration reads as `None`
211/// too.
212#[derive(Clone, Debug, Default)]
213pub struct DeclaredNodeStructure {
214    pub inline: Option<bool>,
215    pub children: Option<NodeChildrenConfig>,
216    pub merge_adjacent: Option<MergeAdjacentConfig>,
217    /// The schema fields and NodeState keys of the class declared
218    /// `derived`: the node's own code recomputes them.
219    pub derived: Vec<String>,
220    /// The class each key came from.
221    pub declared_by: DeclaredBy,
222}
223
224struct CachedNodeStructure {
225    declared: DeclaredNodeStructure,
226    /// The types of the class's config chain, its own first.
227    chain_types: Vec<&'static str>,
228    /// `isOverflowClass(klass)`.
229    is_overflow: bool,
230}
231
232impl CachedNodeStructure {
233    fn own_type(&self) -> &'static str {
234        self.chain_types[0]
235    }
236
237    /// Whether the class declares `mergeAdjacent` in its own `$config()`.
238    fn merges_itself(&self) -> bool {
239        self.declared.merge_adjacent.is_some()
240            && self.declared.declared_by.merge_adjacent == Some(self.own_type())
241    }
242}
243
244thread_local! {
245    /// The nearest `inline` declaration of each class, by its Rust type.
246    static DECLARED_INLINE: RefCell<HashMap<TypeId, Option<bool>>> = RefCell::new(HashMap::new());
247}
248
249/// The nearest `inline` declaration in the class's chain: what the
250/// `isInline()` JS synthesizes (`injectDeclaredIsInline`) returns. Read
251/// without the structure cache, which asks `isInline()`.
252pub(crate) fn declared_inline(node: &dyn LexicalNode) -> Option<bool> {
253    let id = node.as_any().type_id();
254    if let Some(cached) = DECLARED_INLINE.with(|c| c.borrow().get(&id).copied()) {
255        return cached;
256    }
257    let inline = node
258        .static_node_config_chain()
259        .iter()
260        .find_map(|link| link.config.inline);
261    DECLARED_INLINE.with(|c| c.borrow_mut().insert(id, inline));
262    inline
263}
264
265thread_local! {
266    /// `structureCache`, by the node's Rust type (one class).
267    static STRUCTURE_CACHE: RefCell<HashMap<TypeId, Rc<CachedNodeStructure>>> =
268        RefCell::new(HashMap::new());
269}
270
271/// Why `by` is invalid for the class, or `None` when it is valid
272/// (`invalidMergeBy`). A schema field is a property of the class's JSON.
273fn invalid_merge_by(
274    node: &dyn LexicalNode,
275    config: &MergeAdjacentConfig,
276    derived: &[String],
277) -> Option<(String, &'static str)> {
278    let fields = crate::schema::get_composed_schema_fields(node);
279    for entry in &config.by {
280        match entry {
281            MergeAdjacentEntry::Field(name) => {
282                if !fields.iter().any(|(key, _)| key == name) {
283                    return Some(((*name).to_owned(), "unknown"));
284                }
285                if derived.iter().any(|d| d == name) {
286                    return Some(((*name).to_owned(), "derived"));
287                }
288            }
289            MergeAdjacentEntry::State(state) => {
290                if state.derived() {
291                    return Some((state.key().to_owned(), "derived-state"));
292                }
293            }
294        }
295    }
296    None
297}
298
299/// `declaredChildren(klass)`: the nearest `children` declaration, read
300/// without the cache.
301fn declared_children(chain: &[NodeConfigLink]) -> Option<NodeChildrenConfig> {
302    chain.iter().find_map(|link| link.config.children.clone())
303}
304
305/// `mergingChildNotInline(klass, children)`: for a merging class that lists
306/// child classes (no `'inline'`), the first listed class that does not hold
307/// inline content (possibly with a nested instance of the class), or `None`.
308fn merging_child_not_inline(
309    chain_types: &[&'static str],
310    children: Option<&NodeChildrenConfig>,
311) -> Option<&'static str> {
312    let entries = children?.entries()?;
313    if entries.contains(&NodeChildEntry::Inline) {
314        return None;
315    }
316    for entry in entries {
317        let NodeChildEntry::Class(class) = entry else {
318            continue;
319        };
320        let item = declared_children(&class.chain());
321        let ok = match &item {
322            Some(NodeChildrenConfig::Inline) => true,
323            Some(NodeChildrenConfig::List(items)) => {
324                items.contains(&NodeChildEntry::Inline)
325                    && items.iter().all(|e| match e {
326                        NodeChildEntry::Inline => true,
327                        NodeChildEntry::Class(k) => chain_types.contains(&k.node_type),
328                    })
329            }
330            _ => false,
331        };
332        if !ok {
333            return Some(class.node_type);
334        }
335    }
336    None
337}
338
339/// `derivedNamesOf(klass)`: the names of the schema fields and NodeState
340/// keys the class declares derived.
341fn derived_names_of(node: &dyn LexicalNode) -> Vec<String> {
342    let mut derived: Vec<String> = crate::schema::get_composed_schema_fields(node)
343        .into_iter()
344        .filter(|(_, field)| field.is_derived())
345        .map(|(key, _)| key)
346        .collect();
347    for required in node.state_configs() {
348        let key = required.state_config.key();
349        if required.state_config.derived() && !derived.iter().any(|d| d == key) {
350            derived.push(key.to_owned());
351        }
352    }
353    derived
354}
355
356/// `cachedNodeStructure(klass)`, of the class of `node`.
357fn cached_node_structure(node: &dyn LexicalNode) -> Rc<CachedNodeStructure> {
358    let id = node.as_any().type_id();
359    if let Some(cached) = STRUCTURE_CACHE.with(|c| c.borrow().get(&id).cloned()) {
360        return cached;
361    }
362    let chain = iter_static_node_config_chain(node);
363    let own = chain[0].node_type;
364    let chain_types: Vec<&'static str> = chain.iter().map(|l| l.node_type).collect();
365    let mut out = DeclaredNodeStructure::default();
366    let mut merge_seen = false;
367    for link in &chain {
368        let config = &link.config;
369        if out.declared_by.inline.is_none()
370            && let Some(inline) = config.inline
371        {
372            out.inline = Some(inline);
373            out.declared_by.inline = Some(link.node_type);
374        }
375        if out.declared_by.children.is_none()
376            && let Some(children) = &config.children
377        {
378            out.children = Some(children.clone());
379            out.declared_by.children = Some(link.node_type);
380        }
381        if !merge_seen && let Some(merge) = &config.merge_adjacent {
382            merge_seen = true;
383            if let MergeAdjacentDeclaration::By(by) = merge {
384                out.merge_adjacent = Some(MergeAdjacentConfig { by: by.clone() });
385                out.declared_by.merge_adjacent = Some(link.node_type);
386            }
387        }
388    }
389    out.derived = derived_names_of(node);
390    // A declaration the class only inherits never makes it invalid: a key
391    // the class contradicts, or may contradict, reads as undeclared for it.
392    if out.declared_by.inline.is_some_and(|by| by != own) && Some(node.is_inline()) != out.inline {
393        out.inline = None;
394        out.declared_by.inline = None;
395    }
396    if out.declared_by.merge_adjacent.is_some_and(|by| by != own)
397        && (invalid_merge_by(node, out.merge_adjacent.as_ref().unwrap(), &out.derived).is_some()
398            || merging_child_not_inline(&chain_types, out.children.as_ref()).is_some())
399    {
400        out.merge_adjacent = None;
401        out.declared_by.merge_adjacent = None;
402    }
403    // `isOverflowClass`: a link of type `overflow` that extends `ElementNode`
404    // directly, the last of the chain (`ElementNode` itself is not in it).
405    let is_overflow = node.element().is_some() && chain_types.last() == Some(&"overflow");
406    let result = Rc::new(CachedNodeStructure {
407        declared: out,
408        chain_types,
409        is_overflow,
410    });
411    STRUCTURE_CACHE.with(|c| c.borrow_mut().insert(id, result.clone()));
412    result
413}
414
415fn cached_of(node: &NodeRef) -> Rc<CachedNodeStructure> {
416    cached_node_structure(&*node.get_latest())
417}
418
419/// `getDeclaredNodeStructure(klass)` (`@experimental node-structure`): the
420/// structural declarations of the class of `node`. Depends on the class
421/// only.
422pub fn get_declared_node_structure(node: &dyn LexicalNode) -> DeclaredNodeStructure {
423    cached_node_structure(node).declared.clone()
424}
425
426/// Whether `node` is of the class of type `node_type` or a subclass of it
427/// (`node instanceof klass`).
428fn is_instance_of(node: &NodeRef, node_type: &str) -> bool {
429    cached_of(node).chain_types.contains(&node_type)
430}
431
432/// `isOverflowNode(node)`: `OverflowNode` (`@lexical/overflow`) or a class
433/// that extends it, an element whose chain ends with the type `overflow`. It is
434/// inline content although its `isInline()` is false.
435fn is_overflow_node(node: &NodeRef) -> bool {
436    cached_of(node).is_overflow
437}
438
439fn is_line_break(node: &NodeRef) -> bool {
440    node.get_latest().is::<LineBreakNode>()
441}
442
443/// `$isParagraphNode(node)`: `ParagraphNode` or a class that extends it.
444fn is_paragraph(node: &NodeRef) -> bool {
445    node.get_latest().is::<ParagraphNode>() || is_instance_of(node, "paragraph")
446}
447
448fn is_inline_child(node: &NodeRef) -> bool {
449    node.is_text() || is_line_break(node) || is_overflow_node(node) || node.is_inline()
450}
451
452/// `INTERNAL_isInlineContent(node)`: whether the node structure
453/// normalization treats `node` as inline content: text, line breaks, inline
454/// elements and decorators, and the character limit's `OverflowNode`.
455pub fn internal_is_inline_content(node: &NodeRef) -> bool {
456    is_inline_child(node)
457}
458
459/// A leaf the normalization never removes and that sits in a line.
460fn is_inline_leaf(node: &NodeRef) -> bool {
461    node.is_text() || is_line_break(node) || (node.is_decorator() && is_inline_child(node))
462}
463
464fn allows(children: &NodeChildrenConfig, child: &NodeRef) -> bool {
465    if is_overflow_node(child) {
466        return true;
467    }
468    match children {
469        NodeChildrenConfig::Inline => is_inline_child(child),
470        NodeChildrenConfig::Block => !is_inline_child(child),
471        NodeChildrenConfig::List(entries) => {
472            if is_inline_child(child) {
473                return entries.contains(&NodeChildEntry::Inline);
474            }
475            entries.iter().any(|entry| match entry {
476                NodeChildEntry::Class(class) => is_instance_of(child, class.node_type),
477                NodeChildEntry::Inline => false,
478            })
479        }
480    }
481}
482
483/// `effectiveChildren(node)`: a root or shadow root holds blocks whatever
484/// its class declares, any other node what its class declares.
485fn effective_children(node: &NodeRef) -> Option<NodeChildrenConfig> {
486    if is_root_or_shadow_root(&*node.get_latest()) {
487        Some(NodeChildrenConfig::Block)
488    } else {
489        cached_of(node).declared.children.clone()
490    }
491}
492
493/// `isJoinableParagraph(holderChildren, node)`: a plain paragraph whose
494/// content `holder_children` allows.
495fn is_joinable_paragraph(holder_children: &NodeChildrenConfig, node: &NodeRef) -> bool {
496    is_paragraph(node)
497        && !node.get_latest().is_shadow_root()
498        && node
499            .get_children()
500            .iter()
501            .all(|c| allows(holder_children, c))
502}
503
504/// A selection point, as a position next to a node that survives repairs.
505#[derive(Clone, Debug)]
506enum Anchor {
507    Keys { keys: Vec<NodeKey>, after: bool },
508    Inside(NodeKey),
509    Text { key: NodeKey, offset: usize },
510}
511
512/// `descend(node, last)`: `node` and its last (or first) descendants down to
513/// a leaf.
514fn descend(node: &NodeRef, last: bool) -> Vec<NodeKey> {
515    let mut keys = Vec::new();
516    let mut n = Some(node.clone());
517    while let Some(current) = n {
518        keys.push(current.get_key().to_owned());
519        n = if current.is_element() {
520            if last {
521                current.get_last_child()
522            } else {
523                current.get_first_child()
524            }
525        } else {
526            None
527        };
528    }
529    keys
530}
531
532fn keys_after(node: &NodeRef) -> Anchor {
533    Anchor::Keys {
534        keys: descend(node, true),
535        after: true,
536    }
537}
538
539fn keys_before(node: &NodeRef) -> Anchor {
540    Anchor::Keys {
541        keys: descend(node, false),
542        after: false,
543    }
544}
545
546/// `$saveAnchor(point)`: an element point as the node next to it
547/// (preferably a leaf in the same line, which is never removed), so that it
548/// keeps its place among the content when its element is split, unwrapped
549/// or merged.
550fn save_anchor(point: &crate::Point) -> Result<Option<Anchor>, LexicalError> {
551    if point.point_type == PointType::Text {
552        // Text nodes are moved, never removed, but detaching one moves a
553        // point in it to its parent: it is put back afterwards.
554        return Ok(Some(Anchor::Text {
555            key: point.key.clone(),
556            offset: point.offset,
557        }));
558    }
559    let node = point.get_node()?;
560    if !node.is_element() {
561        return Ok(None);
562    }
563    // A point past the end is at the end.
564    let offset = point.offset.min(node.get_children_size());
565    let prev_node = if offset > 0 {
566        node.get_child_at_index(offset - 1)
567    } else {
568        None
569    };
570    let next_node = node.get_child_at_index(offset);
571    let leaf = |n: &Option<NodeRef>| n.as_ref().filter(|n| is_inline_leaf(n)).cloned();
572    if let Some(prev) = leaf(&prev_node) {
573        return Ok(Some(Anchor::Keys {
574            keys: vec![prev.get_key().to_owned()],
575            after: true,
576        }));
577    }
578    if let Some(next) = leaf(&next_node) {
579        return Ok(Some(Anchor::Keys {
580            keys: vec![next.get_key().to_owned()],
581            after: false,
582        }));
583    }
584    let mut prev = prev_node.clone();
585    let mut next = next_node.clone();
586    if effective_children(&node).is_some_and(|rule| rule.holds_inline()) {
587        // In a node that holds lines, a block with nothing in it (an empty
588        // list item) is passed over: a point on either side of it is at the
589        // same place in the content.
590        while let Some(p) = prev.clone().filter(is_passed_over) {
591            prev = p.get_previous_sibling();
592        }
593        while let Some(n) = next.clone().filter(is_passed_over) {
594            next = n.get_next_sibling();
595        }
596        if prev.is_none() && next.is_none() {
597            prev = prev_node;
598            next = next_node;
599        }
600    }
601    if let Some(prev) = leaf(&prev) {
602        return Ok(Some(Anchor::Keys {
603            keys: vec![prev.get_key().to_owned()],
604            after: true,
605        }));
606    }
607    if let Some(next) = leaf(&next) {
608        return Ok(Some(Anchor::Keys {
609            keys: vec![next.get_key().to_owned()],
610            after: false,
611        }));
612    }
613    if let Some(next) = &next {
614        return Ok(Some(keys_before(next)));
615    }
616    if let Some(prev) = &prev {
617        return Ok(Some(keys_after(prev)));
618    }
619    Ok(Some(Anchor::Inside(node.get_key().to_owned())))
620}
621
622/// `isPassedOver(node)`: an element that is not inline, not a paragraph
623/// and holds no leaf at any depth.
624fn is_passed_over(node: &NodeRef) -> bool {
625    if !node.is_element() || is_paragraph(node) || is_inline_child(node) {
626        return false;
627    }
628    fn holds_leaf(n: &NodeRef) -> bool {
629        n.get_children()
630            .iter()
631            .any(|c| !c.is_element() || holds_leaf(c))
632    }
633    !holds_leaf(node)
634}
635
636/// `Normalization`: what one pass of the normalization visits and changed.
637#[derive(Default)]
638struct Normalization {
639    /// The dirty nodes and all their ancestors, and what the repairs put in
640    /// a parent: the only nodes visited (unless `full`).
641    path: HashSet<NodeKey>,
642    /// The keys in `path` by the parent they were added under.
643    path_by_parent: OrderedMap<OrderedSet>,
644    /// Nodes the repairs put in a parent (lifted blocks, copies, wrappers).
645    touched: OrderedSet,
646    /// Where a removed childless element's caret goes.
647    substitutes: HashMap<NodeKey, Anchor>,
648    /// Elements whose children the repairs changed.
649    written: OrderedSet,
650    changed: bool,
651    /// Whether every descendant is visited, not only those in `path`.
652    full: bool,
653    /// Whether this is `INTERNAL_$normalizeNodeStructure`'s normalization.
654    explicit: bool,
655    /// The roots and shadow roots whose inline children are all wrapped.
656    wraps_all: HashSet<NodeKey>,
657    children_cache: HashMap<NodeKey, (usize, Vec<NodeRef>)>,
658}
659
660fn parent_key_of(node: &NodeRef) -> Option<NodeKey> {
661    node.get_latest().base().parent.clone()
662}
663
664impl Normalization {
665    /// `addPath(node)`: add `node`, under its current parent, to the nodes
666    /// visited.
667    fn add_path(&mut self, node: &NodeRef) {
668        let key = node.get_key().to_owned();
669        self.path.insert(key.clone());
670        if let Some(parent) = parent_key_of(node) {
671            if !self.path_by_parent.contains(&parent) {
672                self.path_by_parent.set(&parent, OrderedSet::new());
673            }
674            self.path_by_parent
675                .get_mut(&parent)
676                .expect("just set")
677                .add(&key);
678        }
679    }
680
681    /// `$children(parent)`: the children of `parent` to visit.
682    fn children(&mut self, parent: &NodeRef) -> Vec<NodeRef> {
683        if self.full {
684            return parent.get_children();
685        }
686        let parent_key = parent.get_key();
687        let Some(keys) = self.path_by_parent.get(parent_key) else {
688            return Vec::new();
689        };
690        // The keys of a parent only grow: the same count is the same keys.
691        if let Some((size, nodes)) = self.children_cache.get(parent_key)
692            && *size == keys.len()
693        {
694            return nodes.clone();
695        }
696        let nodes: Vec<NodeRef> = keys
697            .iter()
698            .filter_map(get_node_by_key)
699            .filter(|n| parent_key_of(n).as_deref() == Some(parent_key))
700            .collect();
701        self.children_cache
702            .insert(parent_key.to_owned(), (keys.len(), nodes.clone()));
703        nodes
704    }
705
706    /// `addPathChain(node)`: add `node`, and its ancestors up to one
707    /// already visited under its current parent, to the nodes visited.
708    fn add_path_chain(&mut self, node: &NodeRef) {
709        let mut n = Some(node.clone());
710        while let Some(current) = n {
711            if let Some(parent) = parent_key_of(&current)
712                && self
713                    .path_by_parent
714                    .get(&parent)
715                    .is_some_and(|keys| keys.contains(current.get_key()))
716            {
717                return;
718            }
719            self.add_path(&current);
720            n = current.get_parent();
721        }
722    }
723
724    /// `repath()`: after a class's own seam hook, the entries of every
725    /// removed parent go to where its children are now.
726    fn repath(&mut self) {
727        let entries: Vec<(NodeKey, Vec<NodeKey>)> = self
728            .path_by_parent
729            .iter()
730            .map(|(k, keys)| (k.to_owned(), keys.iter().map(str::to_owned).collect()))
731            .collect();
732        for (parent_key, keys) in entries {
733            if get_node_by_key(&parent_key).is_some_and(|p| p.is_attached()) {
734                continue;
735            }
736            self.path_by_parent.delete(&parent_key);
737            for key in keys {
738                if let Some(node) = get_node_by_key(&key).filter(NodeRef::is_attached) {
739                    self.add_path_chain(&node);
740                }
741            }
742        }
743    }
744
745    /// `movePath(from, to)`: `from`'s children were moved to `to` (a merge),
746    /// and so are their entries.
747    fn move_path(&mut self, from: &str, to: &NodeRef) {
748        if let Some(keys) = self.path_by_parent.delete(from) {
749            for key in keys.iter() {
750                if let Some(node) = get_node_by_key(key) {
751                    self.add_path(&node);
752                }
753            }
754        }
755        self.add_path(to);
756    }
757
758    /// `$resolve(anchor, depth)`.
759    fn resolve(&self, anchor: &Anchor, depth: usize) -> Option<(NodeKey, usize, PointType)> {
760        match anchor {
761            Anchor::Text { key, offset } => get_node_by_key(key)
762                .filter(NodeRef::is_attached)
763                .map(|_| (key.clone(), *offset, PointType::Text)),
764            Anchor::Inside(key) => {
765                if get_node_by_key(key).is_some_and(|n| n.is_attached()) {
766                    return Some((key.clone(), 0, PointType::Element));
767                }
768                let substitute = self.substitutes.get(key)?;
769                (depth < 16).then(|| self.resolve(substitute, depth + 1))?
770            }
771            Anchor::Keys { keys, after } => {
772                // From the innermost key out: the leaf the point was next to
773                // is moved, never removed.
774                for i in (0..keys.len()).rev() {
775                    let node = get_node_by_key(&keys[i])
776                        .filter(|n| n.is_attached() && n.get_parent().is_some());
777                    let Some(node) = node else {
778                        // A node the repairs removed says where its place
779                        // went.
780                        if let Some(substitute) = self.substitutes.get(&keys[i])
781                            && depth < 16
782                        {
783                            return self.resolve(substitute, depth + 1);
784                        }
785                        continue;
786                    };
787                    // Climb back out while the node is still the last child
788                    // (or first, for a point before it).
789                    let mut at = node;
790                    for _ in 0..i {
791                        let Some(parent) = at.get_parent() else {
792                            break;
793                        };
794                        let sibling = if *after {
795                            at.get_next_sibling()
796                        } else {
797                            at.get_previous_sibling()
798                        };
799                        if is_root_or_shadow_root(&*parent.get_latest()) || sibling.is_some() {
800                            break;
801                        }
802                        at = parent;
803                    }
804                    if at.is_text() {
805                        // Next to a text node in its own parent: a point in
806                        // it.
807                        let offset = if *after {
808                            at.get_text_content_size()
809                        } else {
810                            0
811                        };
812                        return Some((at.get_key().to_owned(), offset, PointType::Text));
813                    }
814                    let parent = at.get_parent()?;
815                    let index = at.get_index_within_parent()? + usize::from(*after);
816                    return Some((parent.get_key().to_owned(), index, PointType::Element));
817                }
818                None
819            }
820        }
821    }
822}
823
824/// `$append(parent, nodes)`: `ElementNode`'s own splice, so an override
825/// (`ListNode.splice` wraps every child in a list item) doesn't rewrite
826/// what the repair moves.
827fn append(parent: &NodeRef, nodes: &[NodeRef]) -> Result<(), LexicalError> {
828    if nodes.is_empty() {
829        return Ok(());
830    }
831    element::splice(parent, parent.get_children_size(), 0, nodes)
832}
833
834/// `$detach(node)`: never through an override, never removing a parent it
835/// empties, never moving the selection (the normalization restores it).
836fn detach(node: &NodeRef) -> Result<(), LexicalError> {
837    remove_node(node, false, true)
838}
839
840/// Two JSON values are `===` or `JSON.stringify` the same.
841fn json_equal(a: Option<&crate::json::Value>, b: Option<&crate::json::Value>) -> bool {
842    fn defined(v: Option<&crate::json::Value>) -> Option<&crate::json::Value> {
843        v.filter(|v| !v.is_undefined())
844    }
845    match (defined(a), defined(b)) {
846        (None, None) => true,
847        (Some(a), Some(b)) => a == b || a.to_string() == b.to_string(),
848        _ => false,
849    }
850}
851
852/// `$canMergeAdjacent(a, b)`: whether `a` and its next sibling `b` are the
853/// same thing under the `mergeAdjacent` of `a`'s class, which declares it
854/// itself.
855fn can_merge_adjacent(a: &NodeRef, b: &NodeRef) -> Result<bool, LexicalError> {
856    let (la, lb) = (a.get_latest(), b.get_latest());
857    if la.as_any().type_id() != lb.as_any().type_id() || !a.is_element() || !b.is_element() {
858        return Ok(false);
859    }
860    let cached = cached_node_structure(&*la);
861    if !cached.merges_itself() {
862        return Ok(false);
863    }
864    let config = cached.declared.merge_adjacent.as_ref().expect("merges");
865    let mut json: Option<(crate::json::Object, crate::json::Object)> = None;
866    for entry in &config.by {
867        match entry {
868            MergeAdjacentEntry::Field(name) => {
869                let (ja, jb) =
870                    json.get_or_insert_with(|| (la.export_json(false), lb.export_json(false)));
871                if !json_equal(ja.get(name), jb.get(name)) {
872                    return Ok(false);
873                }
874            }
875            MergeAdjacentEntry::State(state) => {
876                let va = crate::node_state::get_state_erased(&*la, state)?;
877                let vb = crate::node_state::get_state_erased(&*lb, state)?;
878                if !state.is_equal_erased(&*va, &*vb) {
879                    return Ok(false);
880                }
881            }
882        }
883    }
884    Ok(true)
885}
886
887/// `$mergeInto(a, b, ctx)`: append `b`'s children to `a` (its previous
888/// sibling) and remove `b`; `a`'s values win. Children that meet at the
889/// seam merge in turn.
890fn merge_into(a: &NodeRef, b: &NodeRef, ctx: &mut Normalization) -> Result<(), LexicalError> {
891    let a_last = a.get_last_child();
892    let b_first = b.get_first_child();
893    ctx.substitutes.insert(
894        b.get_key().to_owned(),
895        a_last
896            .as_ref()
897            .map_or_else(|| Anchor::Inside(a.get_key().to_owned()), keys_after),
898    );
899    append(a, &b.get_children())?;
900    detach(b)?;
901    ctx.move_path(b.get_key(), a);
902    ctx.changed = true;
903    ctx.written.add(a.get_key());
904    let (Some(a_last), Some(b_first)) = (a_last, b_first) else {
905        return Ok(());
906    };
907    if a_last.is_element() && can_merge_adjacent(&a_last, &b_first)? {
908        return merge_into(&a_last, &b_first, ctx);
909    }
910    // A class may join what meets at the seam itself (a list joins two
911    // items that only wrap nested lists).
912    if a.get_latest()
913        .internal_after_structure_merge(a, &a_last, &b_first)?
914        && !ctx.full
915    {
916        // The hook moves nodes the normalization may not have visited yet.
917        ctx.repath();
918    }
919    Ok(())
920}
921
922/// `$mergeRun(node, ctx)`: merge the run of mutually equal siblings around
923/// `node` into its first node, and return that node.
924fn merge_run(node: &NodeRef, ctx: &mut Normalization) -> Result<NodeRef, LexicalError> {
925    let mut first = node.clone();
926    while let Some(prev) = first.get_previous_sibling() {
927        if !can_merge_adjacent(&prev, &first)? {
928            break;
929        }
930        first = prev;
931    }
932    while let Some(next) = first.get_next_sibling() {
933        if !can_merge_adjacent(&first, &next)? {
934            break;
935        }
936        merge_into(&first, &next, ctx)?;
937    }
938    Ok(first)
939}
940
941/// `$mergeChildren(parent, ctx, all)`: merge the equal adjacent children of
942/// `parent`, every one when `all` (or the normalization is `full`),
943/// otherwise those around the children to visit.
944fn merge_children(
945    parent: &NodeRef,
946    ctx: &mut Normalization,
947    all: bool,
948) -> Result<(), LexicalError> {
949    if all || ctx.full {
950        let mut c = parent.get_first_child();
951        while let Some(current) = c {
952            c = merge_run(&current, ctx)?.get_next_sibling();
953        }
954        return Ok(());
955    }
956    for child in ctx.children(parent) {
957        // Only nodes of one class that declares mergeAdjacent itself merge.
958        if cached_of(&child).merges_itself()
959            && parent_key_of(&child).as_deref() == Some(parent.get_key())
960        {
961            merge_run(&child, ctx)?;
962        }
963    }
964    Ok(())
965}
966
967/// A run of a holder's content between two lifted blocks.
968#[derive(Default)]
969struct Segment {
970    content: Vec<NodeRef>,
971    had_children: bool,
972    /// The holder that received the segment, set by `rebuild`.
973    holder: Option<NodeRef>,
974}
975
976enum RebuildPiece {
977    /// An index into the segments.
978    Segment(usize),
979    Lifted(NodeRef),
980}
981
982/// `$rebuild(holder, pieces, ctx)`: split `holder` into its segments: the
983/// original keeps the first segment that had children, copies take the
984/// others, and the lifted blocks go between them, all in the holder's place
985/// in its parent. Returns the holders.
986fn rebuild(
987    holder: &NodeRef,
988    pieces: &[RebuildPiece],
989    segments: &mut [Segment],
990    ctx: &mut Normalization,
991) -> Result<Vec<NodeRef>, LexicalError> {
992    ctx.changed = true;
993    for child in holder.get_children() {
994        detach(&child)?;
995    }
996    let mut placed: Vec<NodeRef> = Vec::new();
997    let mut holders: Vec<NodeRef> = Vec::new();
998    let mut preceding: Vec<NodeRef> = Vec::new();
999    let mut holder_placed = false;
1000    for piece in pieces {
1001        let index = match piece {
1002            RebuildPiece::Lifted(node) => {
1003                placed.push(node.clone());
1004                continue;
1005            }
1006            RebuildPiece::Segment(index) => *index,
1007        };
1008        if !segments[index].had_children {
1009            continue;
1010        }
1011        let target = if !holder_placed {
1012            holder_placed = true;
1013            holder.clone()
1014        } else {
1015            let target = copy_node(holder);
1016            target
1017                .get_latest()
1018                .internal_after_structure_split(&target, holder, &preceding)?;
1019            target
1020        };
1021        append(&target, &segments[index].content)?;
1022        segments[index].holder = Some(target.clone());
1023        preceding.extend(segments[index].content.iter().cloned());
1024        placed.push(target.clone());
1025        holders.push(target);
1026    }
1027    let parent = holder.get_parent_or_throw()?;
1028    ctx.written.add(parent.get_key());
1029    let at = placed.iter().position(|n| n == holder);
1030    if let Some(at) = at {
1031        let mut anchor = holder.clone();
1032        for node in placed[..at].iter().rev() {
1033            insert_sibling(&anchor, false, node, false)?;
1034            anchor = node.clone();
1035        }
1036    }
1037    let mut anchor = holder.clone();
1038    for node in &placed[at.map_or(0, |at| at + 1)..] {
1039        insert_sibling(&anchor, true, node, false)?;
1040        anchor = node.clone();
1041    }
1042    for node in &placed {
1043        ctx.add_path(node);
1044        ctx.touched.add(node.get_key());
1045    }
1046    if at.is_none() {
1047        // Every child was lifted out: the emptied holder goes, and a point
1048        // in it goes before what was lifted out of it.
1049        if let Some(first) = placed.first() {
1050            ctx.substitutes
1051                .insert(holder.get_key().to_owned(), keys_before(first));
1052        }
1053        detach(holder)?;
1054    }
1055    Ok(holders)
1056}
1057
1058/// A holder's own hook for a child its declared `children` allow that must
1059/// still be lifted out (`INTERNAL_$liftsFromStructure`): the holder, the
1060/// child, and whether this is `INTERNAL_$normalizeNodeStructure`'s
1061/// normalization.
1062pub type LiftsFromStructure =
1063    fn(holder: &NodeRef, child: &NodeRef, explicit: bool) -> Result<bool, LexicalError>;
1064
1065/// `liftsFromStructure(holder)`.
1066fn lifts_from_structure(holder: &NodeRef) -> Option<LiftsFromStructure> {
1067    holder.get_latest().internal_lifts_from_structure()
1068}
1069
1070#[derive(Clone, Copy, PartialEq)]
1071enum InlineKind {
1072    Keep,
1073    Join,
1074    Lift,
1075}
1076
1077#[derive(Clone, Copy, PartialEq)]
1078enum ClassKind {
1079    Keep,
1080    Wrap,
1081    Flatten,
1082    Lift,
1083}
1084
1085/// `inlineRuleKinds(holder, rule, children, explicit)`: what a holder of
1086/// inline content does with each child.
1087fn inline_rule_kinds(
1088    holder: &NodeRef,
1089    rule: &NodeChildrenConfig,
1090    children: &[NodeRef],
1091    explicit: bool,
1092) -> Result<Vec<InlineKind>, LexicalError> {
1093    let inline_holder = holder.is_inline();
1094    let lifts = lifts_from_structure(holder);
1095    children
1096        .iter()
1097        .map(|c| {
1098            Ok(if allows(rule, c) {
1099                match lifts {
1100                    Some(lifts) if lifts(holder, c, explicit)? => InlineKind::Lift,
1101                    _ => InlineKind::Keep,
1102                }
1103            } else if !inline_holder && is_joinable_paragraph(rule, c) {
1104                InlineKind::Join
1105            } else if is_inline_child(c) {
1106                InlineKind::Keep
1107            } else {
1108                InlineKind::Lift
1109            })
1110        })
1111        .collect()
1112}
1113
1114/// `rule[0]` as a class: a list that names no `'inline'` lists classes.
1115fn first_listed_class(rule: &NodeChildrenConfig) -> Option<NodeClassRef> {
1116    match rule.entries()?.first()? {
1117        NodeChildEntry::Class(class) => Some(*class),
1118        NodeChildEntry::Inline => None,
1119    }
1120}
1121
1122/// `classRuleKinds(rule, children)`: what a holder that lists the classes
1123/// it allows (no `'inline'`) does with each child.
1124fn class_rule_kinds(rule: &NodeChildrenConfig, children: &[NodeRef]) -> Vec<ClassKind> {
1125    let wrapper = first_listed_class(rule);
1126    let wrapper_children = wrapper.and_then(|w| declared_children(&w.chain()));
1127    children
1128        .iter()
1129        .map(|c| {
1130            if allows(rule, c) {
1131                ClassKind::Keep
1132            } else if wrapper.is_some() && wrapper_children.as_ref().is_none_or(|w| allows(w, c)) {
1133                ClassKind::Wrap
1134            } else if wrapper.is_some()
1135                && wrapper_children
1136                    .as_ref()
1137                    .is_some_and(|w| is_joinable_paragraph(w, c))
1138            {
1139                ClassKind::Flatten
1140            } else if is_inline_child(c) {
1141                ClassKind::Keep
1142            } else {
1143                ClassKind::Lift
1144            }
1145        })
1146        .collect()
1147}
1148
1149/// `$wrapLiftedContent(block, holder, ctx)`: before `block` is lifted out
1150/// of the inline element `holder` (a link, a mark), wrap each run of inline
1151/// content in it, and in every block it holds at any depth, in a copy of
1152/// `holder`.
1153fn wrap_lifted_content(
1154    block: &NodeRef,
1155    holder: &NodeRef,
1156    ctx: &mut Normalization,
1157) -> Result<(), LexicalError> {
1158    let mut copies: Vec<NodeRef> = Vec::new();
1159    let mut run: Vec<NodeRef> = Vec::new();
1160    let flush = |run: &mut Vec<NodeRef>, copies: &mut Vec<NodeRef>| -> Result<(), LexicalError> {
1161        if !run.is_empty() {
1162            let copy = copy_node(holder);
1163            insert_sibling(&run[0], false, &copy, false)?;
1164            append(&copy, run)?;
1165            copies.push(copy);
1166            run.clear();
1167        }
1168        Ok(())
1169    };
1170    for child in block.get_children() {
1171        // An OverflowNode is not wrapped but wrapped inside.
1172        if is_inline_child(&child) && !is_overflow_node(&child) {
1173            run.push(child);
1174            continue;
1175        }
1176        flush(&mut run, &mut copies)?;
1177        if child.is_element() {
1178            wrap_lifted_content(&child, holder, ctx)?;
1179        }
1180    }
1181    flush(&mut run, &mut copies)?;
1182    if copies.is_empty() {
1183        return Ok(());
1184    }
1185    ctx.changed = true;
1186    ctx.written.add(block.get_key());
1187    if let Some(rule) = effective_children(block)
1188        && copies.iter().any(|copy| !allows(&rule, copy))
1189    {
1190        apply_rules(block, &rule, true, ctx)?;
1191    }
1192    Ok(())
1193}
1194
1195#[derive(Clone, Copy, PartialEq)]
1196enum Last {
1197    None,
1198    Inline,
1199    Line,
1200    Block,
1201}
1202
1203/// `$applyInlineRule(holder, rule, ctx)`: a holder of inline content: plain
1204/// paragraphs become lines of it, joined to the inline content next to them
1205/// with line breaks (an empty one keeps its line), and other blocks are
1206/// lifted out, the holder split around them.
1207fn apply_inline_rule(
1208    holder: &NodeRef,
1209    rule: &NodeChildrenConfig,
1210    ctx: &mut Normalization,
1211) -> Result<Vec<NodeRef>, LexicalError> {
1212    let inline_holder = holder.is_inline();
1213    let children = holder.get_children();
1214    let kinds = inline_rule_kinds(holder, rule, &children, ctx.explicit)?;
1215    if kinds.iter().all(|k| *k == InlineKind::Keep) {
1216        return Ok(vec![holder.clone()]);
1217    }
1218    let mut pieces: Vec<RebuildPiece> = Vec::new();
1219    let mut segments: Vec<Segment> = vec![Segment::default()];
1220    // (paragraph, segment, at)
1221    let mut empty_lines: Vec<(NodeRef, usize, usize)> = Vec::new();
1222    let mut last = Last::None;
1223    for (child, kind) in children.iter().zip(kinds) {
1224        let segment = segments.len() - 1;
1225        if kind == InlineKind::Lift {
1226            if inline_holder && child.is_element() {
1227                // Out of an inline element, the block's inline content is
1228                // wrapped in copies of it first.
1229                wrap_lifted_content(child, holder, ctx)?;
1230            }
1231            pieces.push(RebuildPiece::Segment(segment));
1232            pieces.push(RebuildPiece::Lifted(child.clone()));
1233            segments.push(Segment::default());
1234            last = Last::None;
1235            continue;
1236        }
1237        let s = &mut segments[segment];
1238        s.had_children = true;
1239        if kind == InlineKind::Join {
1240            if last == Last::Inline || last == Last::Line {
1241                s.content.push(create_line_break_node());
1242            }
1243            let content = child.get_children();
1244            if content.is_empty() {
1245                empty_lines.push((child.clone(), segment, s.content.len()));
1246            }
1247            s.content.extend(content);
1248            last = Last::Line;
1249            continue;
1250        }
1251        let unit = if is_inline_child(child) {
1252            Last::Inline
1253        } else {
1254            Last::Block
1255        };
1256        if unit == Last::Inline && last == Last::Line {
1257            s.content.push(create_line_break_node());
1258        }
1259        s.content.push(child.clone());
1260        last = unit;
1261    }
1262    pieces.push(RebuildPiece::Segment(segments.len() - 1));
1263    let holders = rebuild(holder, &pieces, &mut segments, ctx)?;
1264    for (paragraph, segment, at) in empty_lines {
1265        // An empty paragraph's line: after what precedes it in its segment,
1266        // or before what follows, or the holder of its segment.
1267        let s = &segments[segment];
1268        let anchor = if at > 0 {
1269            keys_after(&s.content[at - 1])
1270        } else if let Some(after) = s.content.get(at) {
1271            keys_before(after)
1272        } else {
1273            Anchor::Inside(s.holder.as_ref().unwrap_or(holder).get_key().to_owned())
1274        };
1275        ctx.substitutes
1276            .insert(paragraph.get_key().to_owned(), anchor);
1277    }
1278    Ok(holders)
1279}
1280
1281/// `$applyClassRule(holder, rule, ctx)`: a holder that lists the classes it
1282/// allows and not `'inline'` (a list): a child the first listed class can
1283/// hold is wrapped in one (a run of inline content in one), a plain
1284/// paragraph becomes one holding its content, and any other block is lifted
1285/// out and the holder split around it.
1286fn apply_class_rule(
1287    holder: &NodeRef,
1288    rule: &NodeChildrenConfig,
1289    ctx: &mut Normalization,
1290) -> Result<Vec<NodeRef>, LexicalError> {
1291    let wrapper = first_listed_class(rule);
1292    let children = holder.get_children();
1293    let kinds = class_rule_kinds(rule, &children);
1294    if kinds.iter().all(|k| *k == ClassKind::Keep) {
1295        return Ok(vec![holder.clone()]);
1296    }
1297    let create_wrapper = || set_node_key((wrapper.expect("a listed class").new_node)());
1298    let mut pieces: Vec<RebuildPiece> = Vec::new();
1299    let mut segments: Vec<Segment> = vec![Segment::default()];
1300    let mut i = 0;
1301    while i < children.len() {
1302        let child = &children[i];
1303        let kind = kinds[i];
1304        let segment = segments.len() - 1;
1305        if kind == ClassKind::Lift {
1306            pieces.push(RebuildPiece::Segment(segment));
1307            pieces.push(RebuildPiece::Lifted(child.clone()));
1308            segments.push(Segment::default());
1309            i += 1;
1310            continue;
1311        }
1312        segments[segment].had_children = true;
1313        match kind {
1314            ClassKind::Keep => segments[segment].content.push(child.clone()),
1315            ClassKind::Flatten => {
1316                let w = create_wrapper();
1317                append(&w, &child.get_children())?;
1318                ctx.substitutes.insert(
1319                    child.get_key().to_owned(),
1320                    Anchor::Inside(w.get_key().to_owned()),
1321                );
1322                segments[segment].content.push(w);
1323            }
1324            _ => {
1325                let mut run = vec![child.clone()];
1326                while is_inline_child(child)
1327                    && i + 1 < children.len()
1328                    && kinds[i + 1] == ClassKind::Wrap
1329                    && is_inline_child(&children[i + 1])
1330                {
1331                    i += 1;
1332                    run.push(children[i].clone());
1333                }
1334                let w = create_wrapper();
1335                append(&w, &run)?;
1336                segments[segment].content.push(w);
1337            }
1338        }
1339        i += 1;
1340    }
1341    pieces.push(RebuildPiece::Segment(segments.len() - 1));
1342    rebuild(holder, &pieces, &mut segments, ctx)
1343}
1344
1345/// `$wrapInlineRun(child, ctx)`: a holder of blocks: each run of inline
1346/// children is wrapped in the element its first node creates as a parent (a
1347/// paragraph), as core's shadow root transform does.
1348fn wrap_inline_run(child: &NodeRef, ctx: &mut Normalization) -> Result<(), LexicalError> {
1349    let blocked = |n: &NodeRef| !allows(&NodeChildrenConfig::Block, n);
1350    if !blocked(child) {
1351        return Ok(());
1352    }
1353    let mut first = child.clone();
1354    while let Some(p) = first.get_previous_sibling().filter(|p| blocked(p)) {
1355        first = p;
1356    }
1357    let mut run = vec![first.clone()];
1358    let mut n = first.get_next_sibling();
1359    while let Some(current) = n.filter(|n| blocked(n)) {
1360        n = current.get_next_sibling();
1361        run.push(current);
1362    }
1363    let w = first.create_parent_element_node();
1364    insert_sibling(&first, false, &w, false)?;
1365    append(&w, &run)?;
1366    ctx.changed = true;
1367    ctx.written.add(w.get_key());
1368    ctx.add_path(&w);
1369    ctx.touched.add(w.get_key());
1370    Ok(())
1371}
1372
1373/// `$checksAllChildren(holder, ctx)`: whether the children of `holder`
1374/// must all be checked against its rule. JS asks whether the class writes
1375/// its own `isShadowRoot()` or `isInline()` (`hasInstanceRuleInputs`); as in
1376/// Swift, every class but the root counts as one that does.
1377fn checks_all_children(holder: &NodeRef, ctx: &Normalization) -> bool {
1378    if lifts_from_structure(holder).is_some() {
1379        // Whether a child is allowed depends on its siblings too.
1380        return true;
1381    }
1382    if holder.is_root() {
1383        return ctx.full;
1384    }
1385    let latest = holder.get_latest();
1386    let inputs = u8::from(is_root_or_shadow_root(&*latest)) + 2 * u8::from(is_inline_child(holder));
1387    let mut before = latest.base().structure_rule_inputs.get();
1388    if before.is_none()
1389        && let Some(editor) = get_active_editor()
1390    {
1391        let committed = editor.get_editor_state();
1392        before = committed
1393            .0
1394            .node_map
1395            .borrow()
1396            .get(holder.get_key())
1397            .and_then(|n| n.base().structure_rule_inputs.get());
1398    }
1399    latest.base().structure_rule_inputs.set(Some(inputs));
1400    ctx.full || before != Some(inputs)
1401}
1402
1403/// `$applyRules(holder, rule, checksAll, ctx)`: apply `holder`'s rule.
1404/// Returns the holders it was split into, or `None` when it kept its
1405/// children as they were.
1406fn apply_rules(
1407    holder: &NodeRef,
1408    rule: &NodeChildrenConfig,
1409    checks_all: bool,
1410    ctx: &mut Normalization,
1411) -> Result<Option<Vec<NodeRef>>, LexicalError> {
1412    if *rule == NodeChildrenConfig::Block && checks_all && !holds_inline(holder) {
1413        // The common case (the root in every update).
1414        return Ok(None);
1415    }
1416    let holder_key = holder.get_key().to_owned();
1417    let children: Vec<NodeRef> = if checks_all {
1418        holder.get_children()
1419    } else {
1420        ctx.children(holder)
1421            .into_iter()
1422            .filter(|c| parent_key_of(c).as_deref() == Some(&holder_key))
1423            .collect()
1424    };
1425    if *rule == NodeChildrenConfig::Block {
1426        for c in &children {
1427            if parent_key_of(c).as_deref() == Some(&holder_key) {
1428                wrap_inline_run(c, ctx)?;
1429            }
1430        }
1431        return Ok(None);
1432    }
1433    if rule.holds_inline() {
1434        return Ok(
1435            if inline_rule_kinds(holder, rule, &children, ctx.explicit)?
1436                .iter()
1437                .all(|k| *k == InlineKind::Keep)
1438            {
1439                None
1440            } else {
1441                Some(apply_inline_rule(holder, rule, ctx)?)
1442            },
1443        );
1444    }
1445    Ok(
1446        if class_rule_kinds(rule, &children)
1447            .iter()
1448            .all(|k| *k == ClassKind::Keep)
1449        {
1450            None
1451        } else {
1452            Some(apply_class_rule(holder, rule, ctx)?)
1453        },
1454    )
1455}
1456
1457/// `$normalizeElement(node, ctx)`: normalize `node`'s subtree bottom-up.
1458/// Returns whether `node` was removed.
1459fn normalize_element(node: &NodeRef, ctx: &mut Normalization) -> Result<bool, LexicalError> {
1460    let rule = effective_children(node);
1461    // Decided once per visit: it records what the rule depends on.
1462    let checks_all = rule.as_ref().is_some_and(|rule| {
1463        checks_all_children(node, ctx)
1464            || (*rule == NodeChildrenConfig::Block && ctx.wraps_all.contains(node.get_key()))
1465    });
1466    let root_or_shadow = |n: &NodeRef| is_root_or_shadow_root(&*n.get_latest());
1467    if !ctx.full && !ctx.path_by_parent.contains(node.get_key()) {
1468        // Written, but none of its children was.
1469        if node.is_empty() && !root_or_shadow(node) && is_removed_when_empty(node) {
1470            remove_empty(node, ctx)?;
1471            return Ok(true);
1472        }
1473        if !checks_all {
1474            return Ok(false);
1475        }
1476    }
1477    merge_children(node, ctx, false)?;
1478    let mut removed_child = false;
1479    for c in ctx.children(node) {
1480        if c.is_element()
1481            && parent_key_of(&c).as_deref() == Some(node.get_key())
1482            && normalize_element(&c, ctx)?
1483        {
1484            removed_child = true;
1485        }
1486    }
1487    if node.is_empty()
1488        && !root_or_shadow(node)
1489        && (is_removed_when_empty(node) || (removed_child && !node.can_be_empty()))
1490    {
1491        remove_empty(node, ctx)?;
1492        return Ok(true);
1493    }
1494    let holders = match &rule {
1495        Some(rule) => apply_rules(node, rule, checks_all, ctx)?,
1496        None => None,
1497    };
1498    match holders {
1499        // A rebuilt holder's children were all moved: every pair is new.
1500        Some(holders) => {
1501            for holder in holders {
1502                merge_children(&holder, ctx, true)?;
1503            }
1504        }
1505        None => merge_children(node, ctx, false)?,
1506    }
1507    Ok(false)
1508}
1509
1510/// `isRemovedWhenEmpty(node)`: an inline element that cannot be empty (a
1511/// link, a mark), or the character limit's `OverflowNode`.
1512fn is_removed_when_empty(node: &NodeRef) -> bool {
1513    is_overflow_node(node) || (is_inline_child(node) && !node.can_be_empty())
1514}
1515
1516/// `$removeEmpty(node, ctx)`.
1517fn remove_empty(node: &NodeRef, ctx: &mut Normalization) -> Result<(), LexicalError> {
1518    let prev = node.get_previous_sibling();
1519    let next = node.get_next_sibling();
1520    let parent = node.get_parent_or_throw()?;
1521    let anchor = match (&prev, &next) {
1522        (Some(prev), _) => keys_after(prev),
1523        (None, Some(next)) => keys_before(next),
1524        (None, None) => Anchor::Inside(parent.get_key().to_owned()),
1525    };
1526    ctx.substitutes.insert(node.get_key().to_owned(), anchor);
1527    detach(node)?;
1528    // The siblings it separated are now adjacent: they may merge.
1529    for sibling in [prev, next].into_iter().flatten() {
1530        ctx.add_path(&sibling);
1531        ctx.touched.add(sibling.get_key());
1532    }
1533    ctx.changed = true;
1534    ctx.written.add(parent.get_key());
1535    Ok(())
1536}
1537
1538/// `isStructurallyUnchanged(node, committed)`. Only the root's class counts
1539/// as structurally static here (see [`checks_all_children`]).
1540fn is_structurally_unchanged(node: &NodeRef, committed: Option<&Rc<dyn LexicalNode>>) -> bool {
1541    let Some(committed) = committed else {
1542        return false;
1543    };
1544    if !node.is_root() || !committed.is::<crate::nodes::root::RootNode>() {
1545        return false;
1546    }
1547    let n = node.get_latest();
1548    let (nb, cb) = (n.base(), committed.base());
1549    let (ne, ce) = (
1550        n.element().expect("an element"),
1551        committed.element().expect("an element"),
1552    );
1553    cb.parent == nb.parent
1554        && cb.prev == nb.prev
1555        && cb.next == nb.next
1556        && ce.first == ne.first
1557        && ce.last == ne.last
1558        && ce.size == ne.size
1559}
1560
1561/// `$normalizeDirty(dirty, full, committedNormalized)`: repair the
1562/// structure around every node written since the last pass, from the root
1563/// down.
1564fn normalize_dirty(
1565    dirty: &mut Vec<NodeKey>,
1566    full: bool,
1567    committed_normalized: bool,
1568) -> Result<(), LexicalError> {
1569    let root = get_root();
1570    if dirty.is_empty() && !full && !holds_inline(&root) {
1571        return Ok(());
1572    }
1573    let mut ctx = Normalization {
1574        full,
1575        ..Normalization::default()
1576    };
1577    let root_key = root.get_key().to_owned();
1578    // Core's shadow root transform, which the extension turns off, wraps the
1579    // inline children of the root in every update and those of a shadow
1580    // root that was written: so does this.
1581    ctx.wraps_all.insert(root_key.clone());
1582    ctx.path.insert(root_key);
1583    let committed = committed_normalized
1584        .then(get_active_editor)
1585        .flatten()
1586        .map(|editor| editor.get_editor_state());
1587    let keys: Vec<NodeKey> = if full { Vec::new() } else { dirty.clone() };
1588    for key in keys {
1589        let node = get_node_by_key(&key);
1590        if let Some(node) = &node
1591            && node.is_element()
1592            && node.get_latest().is_shadow_root()
1593        {
1594            ctx.wraps_all.insert(key.clone());
1595        }
1596        if let (Some(committed), Some(node)) = (&committed, &node)
1597            && is_structurally_unchanged(node, committed.0.node_map.borrow().get(&key))
1598        {
1599            continue;
1600        }
1601        let mut chain: Vec<NodeRef> = Vec::new();
1602        let mut attached = false;
1603        let mut n = node;
1604        while let Some(current) = n {
1605            if ctx.path.contains(current.get_key()) {
1606                attached = true;
1607                break;
1608            }
1609            n = current.get_parent();
1610            chain.push(current);
1611        }
1612        if attached {
1613            for n in &chain {
1614                ctx.add_path(n);
1615            }
1616        }
1617    }
1618    dirty.clear();
1619    if ctx.path.len() > 1 || full || holds_inline(&root) {
1620        normalize(&mut ctx, |ctx| normalize_element(&root, ctx).map(|_| ()))?;
1621    }
1622    Ok(())
1623}
1624
1625/// `isBlockElement(node)`: an element whose `isInline()` returns false.
1626fn is_block_element(node: &NodeRef) -> bool {
1627    node.is_element() && !node.is_inline()
1628}
1629
1630/// `$holdsInline(node)`: whether `node` holds content that a holder of
1631/// blocks wraps.
1632fn holds_inline(node: &NodeRef) -> bool {
1633    let mut c = node.get_first_child();
1634    while let Some(current) = c {
1635        if !is_block_element(&current) && !allows(&NodeChildrenConfig::Block, &current) {
1636            return true;
1637        }
1638        c = current.get_next_sibling();
1639    }
1640    false
1641}
1642
1643/// `$normalize(ctx, repair)`: run `repair`, then make every ancestor of a
1644/// change dirty, so that its own transforms run again on the result, and
1645/// put the selection back among the content it was in.
1646fn normalize(
1647    ctx: &mut Normalization,
1648    repair: impl FnOnce(&mut Normalization) -> Result<(), LexicalError>,
1649) -> Result<(), LexicalError> {
1650    let selection = get_selection().filter(|s| s.is_range());
1651    let mut saved: Vec<(Which, Option<Anchor>)> = Vec::new();
1652    if let Some(selection) = &selection {
1653        for which in [Which::Anchor, Which::Focus] {
1654            let point = selection.point(which).expect("a range selection");
1655            saved.push((which, save_anchor(&point)?));
1656        }
1657    }
1658    repair(ctx)?;
1659    for key in ctx.written.iter() {
1660        if let Some(node) = get_node_by_key(key).filter(NodeRef::is_attached) {
1661            let mut n = Some(node);
1662            while let Some(current) = n.filter(|n| !n.is_root()) {
1663                current.mark_dirty();
1664                n = current.get_parent();
1665            }
1666        }
1667    }
1668    if ctx.changed
1669        && let Some(selection) = &selection
1670    {
1671        for (which, anchor) in saved {
1672            if let Some((key, offset, point_type)) =
1673                anchor.and_then(|anchor| ctx.resolve(&anchor, 0))
1674            {
1675                selection.point_set(which, &key, offset, point_type)?;
1676            }
1677        }
1678    }
1679    Ok(())
1680}
1681
1682/// `INTERNAL_$normalizeNodeStructure(node)` (internal): normalize the
1683/// subtree rooted at `node` now, as `NodeStructureExtension` does, bottom-up
1684/// (which may split `node` in its parent), then merge `node` (or what it was
1685/// split into) with its equal siblings. For code that applies an update with
1686/// `skip_transforms`, which the extension doesn't normalize.
1687pub fn internal_normalize_node_structure(node: &NodeRef) -> Result<(), LexicalError> {
1688    if !node.is_element() || !node.is_attached() {
1689        return Ok(());
1690    }
1691    let mut ctx = Normalization {
1692        full: true,
1693        explicit: true,
1694        ..Normalization::default()
1695    };
1696    let parent = node.get_parent();
1697    normalize(&mut ctx, |ctx| {
1698        let Some(parent) = parent.filter(|_| !is_root_or_shadow_root(&*node.get_latest())) else {
1699            // A root (or shadow root) is never split: normalize it in place.
1700            return normalize_element(node, ctx).map(|_| ());
1701        };
1702        let parent_key = parent.get_key().to_owned();
1703        ctx.touched.add(node.get_key());
1704        normalize_element(node, ctx)?;
1705        let touched: Vec<NodeKey> = ctx.touched.iter().map(str::to_owned).collect();
1706        for key in touched {
1707            if let Some(piece) = get_node_by_key(&key)
1708                && parent_key_of(&piece).as_deref() == Some(&parent_key)
1709            {
1710                merge_run(&piece, ctx)?;
1711            }
1712        }
1713        Ok(())
1714    })
1715}
1716
1717// MARK: Registration
1718
1719/// One editor's structure registration (`StructureRegistration`), counted.
1720pub(crate) struct NodeStructureRegistration {
1721    refs: Cell<usize>,
1722    dispose: RefCell<Option<Unregister>>,
1723    /// The nodes collected since the last pass, and since the last commit.
1724    dirty: RefCell<Vec<NodeKey>>,
1725    collected: RefCell<HashSet<NodeKey>>,
1726    /// Committed states that may not be normalized: the one before the
1727    /// registration, and any that an update applied without transforms
1728    /// changed (a JS `WeakSet`).
1729    unnormalized: RefCell<Vec<Weak<EditorStateInner>>>,
1730    /// The first pass after registering normalizes the whole document.
1731    full: Cell<bool>,
1732}
1733
1734impl NodeStructureRegistration {
1735    fn is_unnormalized(&self, state: &crate::EditorState) -> bool {
1736        let mut unnormalized = self.unnormalized.borrow_mut();
1737        unnormalized.retain(|w| w.strong_count() > 0);
1738        unnormalized
1739            .iter()
1740            .any(|w| std::ptr::eq(w.as_ptr(), Rc::as_ptr(&state.0)))
1741    }
1742}
1743
1744/// `INTERNAL_registerNodeStructure(editor)` (internal, for
1745/// `NodeStructureExtension` and `registerNodeStructure`): enforce the
1746/// structure node classes declare on `editor`, and mark every element and
1747/// decorator dirty so the current document is normalized too.
1748/// Registrations are counted: the normalization stops when the last one is
1749/// disposed.
1750///
1751/// Every class gets a transform that records the nodes written in the
1752/// update, and the root a transform, which runs last in each transform
1753/// pass, that normalizes from the root down along those nodes' ancestors.
1754pub fn internal_register_node_structure(editor: &Editor) -> Unregister {
1755    let existing = editor.0.node_structure.borrow().clone();
1756    let registration = match existing {
1757        Some(registration) => registration,
1758        None => {
1759            let registration = Rc::new(NodeStructureRegistration {
1760                refs: Cell::new(0),
1761                dispose: RefCell::new(None),
1762                dirty: RefCell::new(Vec::new()),
1763                collected: RefCell::new(HashSet::new()),
1764                unnormalized: RefCell::new(vec![Rc::downgrade(&editor.get_editor_state().0)]),
1765                full: Cell::new(true),
1766            });
1767            let mut cleanups: Vec<Unregister> = Vec::new();
1768            {
1769                let registration = Rc::downgrade(&registration);
1770                cleanups.push(editor.register_update_listener(move |payload| {
1771                    let Some(registration) = registration.upgrade() else {
1772                        return;
1773                    };
1774                    let node_map = payload.editor_state.0.node_map.borrow();
1775                    let skipped = |key: &str| {
1776                        !registration.collected.borrow().contains(key) && node_map.contains_key(key)
1777                    };
1778                    let complete =
1779                        !payload.dirty_elements.iter().any(|(key, intentional)| {
1780                            *intentional && key != "root" && skipped(key)
1781                        }) && !payload.dirty_leaves.iter().any(|key| skipped(key));
1782                    registration.collected.borrow_mut().clear();
1783                    if !complete {
1784                        registration
1785                            .unnormalized
1786                            .borrow_mut()
1787                            .push(Rc::downgrade(&payload.editor_state.0));
1788                    }
1789                }));
1790            }
1791            let mut types: Vec<&'static str> = Vec::new();
1792            for class in editor.registered_nodes_in_order() {
1793                let node_type = class.node_type();
1794                let registration = Rc::downgrade(&registration);
1795                cleanups.push(if node_type == "root" {
1796                    editor.add_node_transform(node_type, move |_| {
1797                        let Some(registration) = registration.upgrade() else {
1798                            return Ok(());
1799                        };
1800                        let all = registration.full.replace(false);
1801                        let committed_normalized = get_active_editor()
1802                            .is_some_and(|e| !registration.is_unnormalized(&e.get_editor_state()));
1803                        let mut dirty = std::mem::take(&mut *registration.dirty.borrow_mut());
1804                        let result = normalize_dirty(&mut dirty, all, committed_normalized);
1805                        // Keys collected while it ran stay for the next pass.
1806                        let mut pending = registration.dirty.borrow_mut();
1807                        dirty.append(&mut pending);
1808                        *pending = dirty;
1809                        result
1810                    })
1811                } else {
1812                    editor.add_node_transform(node_type, move |node| {
1813                        if let Some(registration) = registration.upgrade() {
1814                            let key = node.get_key().to_owned();
1815                            registration.collected.borrow_mut().insert(key.clone());
1816                            registration.dirty.borrow_mut().push(key);
1817                        }
1818                        Ok(())
1819                    })
1820                });
1821                if (class.is_element_or_decorator)() {
1822                    types.push(node_type);
1823                }
1824            }
1825            *registration.dispose.borrow_mut() = Some(crate::merge_register(cleanups));
1826            *editor.0.node_structure.borrow_mut() = Some(registration.clone());
1827            crate::editor::mark_nodes_with_types_as_dirty(editor, &types);
1828            registration
1829        }
1830    };
1831    registration.refs.set(registration.refs.get() + 1);
1832    let editor = editor.weak();
1833    // An `Unregister` is called at most once.
1834    Box::new(move || {
1835        registration.refs.set(registration.refs.get() - 1);
1836        if registration.refs.get() == 0 {
1837            if let Some(dispose) = registration.dispose.borrow_mut().take() {
1838                dispose();
1839            }
1840            if let Some(inner) = editor.upgrade() {
1841                let mut current = inner.node_structure.borrow_mut();
1842                if current
1843                    .as_ref()
1844                    .is_some_and(|r| Rc::ptr_eq(r, &registration))
1845                {
1846                    *current = None;
1847                }
1848            }
1849        }
1850    })
1851}
1852
1853/// `INTERNAL_isNodeStructureEnforced(editor)` (internal): whether `editor`
1854/// enforces declared node structure (`NodeStructureExtension` or
1855/// `registerNodeStructure` is registered on it).
1856pub fn internal_is_node_structure_enforced(editor: &Editor) -> bool {
1857    editor.0.node_structure.borrow().is_some()
1858}
1859
1860/// Whether there is an active editor and it enforces declared structure.
1861pub(crate) fn is_structure_enforced_on_active_editor() -> bool {
1862    get_active_editor().is_some_and(|e| internal_is_node_structure_enforced(&e))
1863}
1864
1865/// Whether the active editor enforces declared structure and `node`'s class
1866/// declares `mergeAdjacent` itself, so that the normalization merges it with
1867/// a next sibling of the same class (`$structureMerges` in `@lexical/link`
1868/// and `@lexical/list`).
1869#[cfg_attr(not(any(feature = "link", feature = "list")), allow(dead_code))]
1870pub(crate) fn structure_merges(node: &NodeRef, next: &NodeRef) -> bool {
1871    next.get_latest().as_any().type_id() == node.get_latest().as_any().type_id()
1872        && is_structure_enforced_on_active_editor()
1873        && cached_of(node).merges_itself()
1874}
1875
1876/// `$isBlockContainer(node)` (`@experimental node-structure`): whether
1877/// structural commands treat `node` as a container of blocks: the root, a
1878/// shadow root, or, in an editor that enforces declared node structure, a
1879/// block element whose class declares `children: 'block'`. With no active
1880/// editor, only the root and shadow roots are containers.
1881pub fn is_block_container(node: &NodeRef) -> bool {
1882    if !node.is_element() {
1883        return false;
1884    }
1885    is_root_or_shadow_root(&*node.get_latest())
1886        || (cached_of(node).declared.children == Some(NodeChildrenConfig::Block)
1887            && !node.is_inline()
1888            && is_structure_enforced_on_active_editor())
1889}
1890
1891/// `validateNodeStructure(klass)`: the development check of a class's
1892/// structural declarations, run when an editor is created. A bad
1893/// declaration is a bug in the node's implementation, so it panics with
1894/// JS's message.
1895pub(crate) fn validate_node_structure(node: &dyn LexicalNode) {
1896    let cached = cached_node_structure(node);
1897    let declared = &cached.declared;
1898    let name = cached.own_type();
1899    if cached.merges_itself() {
1900        let merge = declared.merge_adjacent.as_ref().expect("merges");
1901        match invalid_merge_by(node, merge, &declared.derived) {
1902            Some((entry, "unknown")) => panic!(
1903                "{name}: mergeAdjacent.by names {entry}, which is not a schema field of the class"
1904            ),
1905            Some((entry, "derived")) => {
1906                panic!("{name}: mergeAdjacent.by names {entry}, which is derived")
1907            }
1908            Some((entry, _)) => {
1909                panic!("{name}: mergeAdjacent.by names the derived NodeState {entry}")
1910            }
1911            None => {}
1912        }
1913        if let Some(item) =
1914            merging_child_not_inline(&cached.chain_types, declared.children.as_ref())
1915        {
1916            panic!(
1917                "{name}: a merging class that lists child classes must list classes that hold inline content ({item} does not)"
1918            );
1919        }
1920    }
1921    if let Some(inline) = declared.inline
1922        && declared.declared_by.inline == Some(name)
1923        && node.is_inline() != inline
1924    {
1925        panic!(
1926            "{name}: $config inline is {inline} but isInline() returns {}",
1927            node.is_inline()
1928        );
1929    }
1930}