Skip to main content

lexical_ui/
reconciler.rs

1//! `LexicalReconciler.ts`, its model half: the walk `$reconcileRoot` makes
2//! over the previous and next trees once the editor has a root element, for
3//! what it gives back to the model: the nodes it creates, updates and
4//! destroys, for mutation listeners (`setMutatedNode`, in
5//! `LexicalUtils.ts`), slot values included (`$mountSlotChildren`,
6//! `$reconcileSlotChildren`, `$destroyNode`'s of a host's slots); what each
7//! decorator it renders decorates to (`reconcileDecorator`, for
8//! `editor._decorators`); and the `textFormat` and `textStyle` a reconciled
9//! element takes from its first text descendant (`reconcileTextFormat`,
10//! `reconcileTextStyle`). Each node's keyed DOM is a [`ReconciledNode`],
11//! which keeps what JS caches on that DOM between commits for the model: an
12//! element's first text descendant (`__lexicalFirstTextKey`) and the slot
13//! container a slot value is mounted in. Nothing is rendered, so the text
14//! and direction caches aren't kept, except for what the root's text cache
15//! (`__cachedText`) does to the commit: a stale one marks the root dirty
16//! (`commit_pending_updates`).
17//!
18//! The children fast paths of `$reconcileChildren` (a dirty suffix of four
19//! or more children) only save DOM work: they reach the same nodes in the
20//! same order as the general walk and recover the same first text
21//! (`$resolveSuffixPathFormat`), so this ports the general walk, as Swift
22//! does.
23
24use crate::Editor;
25use crate::editor::{DirtyType, NodeMutation};
26use crate::editor_state::{EditorState, NodeMap};
27use crate::json::array_index;
28use crate::node::{LexicalNode, NodeKey, NodeRef};
29use crate::nodes::element::is_root_or_shadow_root;
30use crate::ordered::{OrderedMap, OrderedSet};
31use crate::slot::{SlotMap, slot_host_key_field, slots_field};
32use std::any::Any;
33use std::cell::{Cell, RefCell};
34use std::collections::{HashMap, HashSet};
35use std::fmt;
36use std::rc::Rc;
37
38pub(crate) use crate::editor::MutatedNodes;
39
40/// `editor._decorators` (`Record<NodeKey, unknown>`): what each decorator
41/// the reconciler rendered returned from
42/// [`decorate`](LexicalNode::decorate), by key, in the order JS's object
43/// lists its keys (`Object.entries`): array-index keys ascending, which
44/// every generated key is, then the others in insertion order. A value is
45/// the app's `Rc<dyn Any>`, compared by identity (`Rc::ptr_eq`) as JS
46/// compares the object a `decorate` returns (`===`).
47#[derive(Clone, Default)]
48pub struct Decorators {
49    entries: Vec<(NodeKey, Rc<dyn Any>)>,
50}
51
52impl Decorators {
53    /// `decorators[key]`.
54    pub fn get(&self, key: &str) -> Option<&Rc<dyn Any>> {
55        self.entries.iter().find(|(k, _)| k == key).map(|(_, v)| v)
56    }
57
58    /// `Object.entries(decorators)`.
59    pub fn iter(&self) -> impl Iterator<Item = (&str, &Rc<dyn Any>)> {
60        self.entries.iter().map(|(k, v)| (k.as_str(), v))
61    }
62
63    /// `Object.keys(decorators)`.
64    pub fn keys(&self) -> impl Iterator<Item = &str> {
65        self.entries.iter().map(|(k, _)| k.as_str())
66    }
67
68    pub fn len(&self) -> usize {
69        self.entries.len()
70    }
71
72    pub fn is_empty(&self) -> bool {
73        self.entries.is_empty()
74    }
75
76    /// `decorators[key] = value`, in JS's property order.
77    fn insert(&mut self, key: &str, value: Rc<dyn Any>) {
78        if let Some(entry) = self.entries.iter_mut().find(|(k, _)| k == key) {
79            entry.1 = value;
80            return;
81        }
82        let at = match array_index(key) {
83            Some(index) => self
84                .entries
85                .iter()
86                .position(|(k, _)| array_index(k).is_none_or(|i| i > index))
87                .unwrap_or(self.entries.len()),
88            None => self.entries.len(),
89        };
90        self.entries.insert(at, (key.to_owned(), value));
91    }
92
93    /// `delete decorators[key]`.
94    fn remove(&mut self, key: &str) {
95        self.entries.retain(|(k, _)| k != key);
96    }
97}
98
99impl fmt::Debug for Decorators {
100    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
101        f.debug_list().entries(self.keys()).finish()
102    }
103}
104
105/// `$garbageCollectDetachedDecorators(editor, pendingEditorState)`
106/// (`LexicalGC.ts`): the decorators of nodes the pending state no longer
107/// has are dropped, in `_pendingDecorators` (made from `_decorators` when
108/// there is none, as `cloneDecorators` does).
109pub(crate) fn garbage_collect_detached_decorators(
110    editor: &Editor,
111    pending_editor_state: &EditorState,
112) {
113    let detached: Vec<NodeKey> = {
114        let node_map = pending_editor_state.0.node_map.borrow();
115        let pending = editor.0.pending_decorators.borrow();
116        let current = editor.0.decorators.borrow();
117        pending
118            .as_ref()
119            .unwrap_or(&current)
120            .keys()
121            .filter(|key| !node_map.contains_key(*key))
122            .map(str::to_owned)
123            .collect()
124    };
125    if detached.is_empty() {
126        return;
127    }
128    let pending = editor.0.pending_decorators.borrow_mut().take();
129    let mut decorators = pending.unwrap_or_else(|| editor.0.decorators.borrow().clone());
130    for key in &detached {
131        decorators.remove(key);
132    }
133    *editor.0.pending_decorators.borrow_mut() = Some(decorators);
134}
135
136/// The stand-in for a node's keyed DOM (a value of `editor._keyToDOMMap`):
137/// what the reconciler keeps on it between commits.
138#[derive(Default)]
139pub(crate) struct ReconciledNode {
140    /// `__lexicalFirstTextKey` (elements only): `Some(None)` when there is
141    /// no text descendant, `None` while unset.
142    first_text_key: RefCell<Option<Option<NodeKey>>>,
143    /// The slot container the DOM is mounted in (a slot value's
144    /// `parentElement`), by its id; `None` in a parent's children.
145    container: Cell<Option<u64>>,
146}
147
148#[cfg(all(test, feature = "extension", feature = "rich-text", feature = "link"))]
149impl ReconciledNode {
150    /// `dom.__lexicalFirstTextKey`, for the ported reconciler tests.
151    pub(crate) fn first_text_key(&self) -> Option<Option<NodeKey>> {
152        self.first_text_key.borrow().clone()
153    }
154}
155
156/// `editor._keyToDOMMap`.
157pub(crate) type KeyToDomMap = HashMap<NodeKey, Rc<ReconciledNode>>;
158
159/// The `DOMSlot` `$createNode` inserts a node into: a slot container, by
160/// id, or (`None`) its parent's children.
161#[derive(Clone, Copy)]
162struct Slot {
163    container: Option<u64>,
164}
165
166/// `CaptureGuard`: the first text captured before a walk that may reset it.
167struct CaptureGuard {
168    first_text_key: Option<NodeKey>,
169    format: Option<f64>,
170    style: Option<String>,
171}
172
173/// What `reconcileTextFormat` and `reconcileTextStyle` set on an element.
174struct TextFieldsWrite {
175    key: NodeKey,
176    format: Option<f64>,
177    style: Option<String>,
178}
179
180struct Reconciler<'a> {
181    editor: &'a Editor,
182    /// `treatAllNodesAsDirty`.
183    treat_all_nodes_as_dirty: bool,
184    /// `activeEditorStateReadOnly`.
185    editor_state_read_only: bool,
186    dirty_elements: &'a OrderedMap<bool>,
187    dirty_leaves: &'a OrderedSet,
188    prev_node_map: &'a NodeMap,
189    next_node_map: &'a NodeMap,
190    /// Whether any mutation listener is registered (`mutationListeners.size`).
191    listening: bool,
192    mutated_nodes: MutatedNodes,
193    /// `activeEditor._keyToDOMMap`, taken from the editor for the walk.
194    key_to_dom_map: KeyToDomMap,
195    /// `activePrevKeyToDOMMap` (the map as the walk started), as the entries
196    /// the walk has changed since: a key's value before its first change.
197    prev_key_to_dom_map: HashMap<NodeKey, Option<Rc<ReconciledNode>>>,
198    /// `subTreeTextFormat`.
199    sub_tree_text_format: Option<f64>,
200    /// `subTreeTextStyle`.
201    sub_tree_text_style: Option<String>,
202    /// `subTreeFirstTextKey`.
203    sub_tree_first_text_key: Option<NodeKey>,
204    /// The `setTextFormat` and `setTextStyle` calls of `reconcileTextFormat`
205    /// and `reconcileTextStyle`, in the walk's order. JS makes them during
206    /// the walk; nothing the walk reads later reads them, so they are made
207    /// once it ends, when the node maps are no longer borrowed.
208    text_fields_writes: Vec<TextFieldsWrite>,
209}
210
211impl Reconciler<'_> {
212    /// `setMutatedNode(mutatedNodes, registeredNodes, mutationListeners,
213    /// node, mutation)`.
214    fn set_mutated_node(&mut self, node: &dyn LexicalNode, mutation: NodeMutation) {
215        if !self.listening {
216            return;
217        }
218        let node_type = node.get_type();
219        let index = match self.mutated_nodes.iter().position(|(t, _)| *t == node_type) {
220            Some(index) => index,
221            None => {
222                self.mutated_nodes.push((node_type, Vec::new()));
223                self.mutated_nodes.len() - 1
224            }
225        };
226        let by_type = &mut self.mutated_nodes[index].1;
227        let key = node.get_key();
228        match by_type.iter_mut().find(|(k, _)| k == key) {
229            // A node destroyed, then made again: a move, so an update.
230            Some((_, prev)) => {
231                if *prev == NodeMutation::Destroyed && mutation == NodeMutation::Created {
232                    *prev = NodeMutation::Updated;
233                }
234            }
235            None => by_type.push((key.to_owned(), mutation)),
236        }
237    }
238
239    /// `$beginCaptureGuard()`.
240    fn begin_capture_guard(&self) -> CaptureGuard {
241        CaptureGuard {
242            first_text_key: self.sub_tree_first_text_key.clone(),
243            format: self.sub_tree_text_format,
244            style: self.sub_tree_text_style.clone(),
245        }
246    }
247
248    /// `$endCaptureGuard(saved)`: an earlier capture wins.
249    fn end_capture_guard(&mut self, saved: CaptureGuard) {
250        if saved.first_text_key.is_some() {
251            self.sub_tree_text_format = saved.format;
252            self.sub_tree_text_style = saved.style;
253            self.sub_tree_first_text_key = saved.first_text_key;
254        }
255    }
256
257    /// The first text of the walk, when none is captured yet: what
258    /// `$createChildren` and `$reconcileNodeChildren` do after a child.
259    fn capture_first_text(&mut self, key: &str) {
260        if self.sub_tree_text_format.is_some() {
261            return;
262        }
263        if let Some(text) = self.next_node_map.get(key).and_then(|n| n.text()) {
264            self.sub_tree_text_format = Some(text.get_format());
265            self.sub_tree_text_style = Some(text.get_style().to_owned());
266            self.sub_tree_first_text_key = Some(key.to_owned());
267        }
268    }
269
270    /// `$bubbleChildFirstText(childKeyedDom)`: a clean element's cached
271    /// first text, unless one is captured already.
272    fn bubble_child_first_text(&mut self, child_keyed_dom: &ReconciledNode) {
273        if self.sub_tree_first_text_key.is_some() {
274            return;
275        }
276        let child_first_key =
277            child_keyed_dom.first_text_key.borrow().clone().expect(
278                "$bubbleChildFirstText: missing __lexicalFirstTextKey on element keyed DOM",
279            );
280        let Some(child_first_key) = child_first_key else {
281            return;
282        };
283        if let Some(text) = self
284            .next_node_map
285            .get(&child_first_key)
286            .and_then(|n| n.text())
287        {
288            self.sub_tree_text_format = Some(text.get_format());
289            self.sub_tree_text_style = Some(text.get_style().to_owned());
290            self.sub_tree_first_text_key = Some(child_first_key);
291        }
292    }
293
294    /// `getElementByKeyOrThrow(activeEditor, key)`.
295    fn get_element_by_key_or_throw(&self, key: &str) -> Rc<ReconciledNode> {
296        self.key_to_dom_map.get(key).cloned().unwrap_or_else(|| {
297            panic!("Reconciliation: could not find DOM element for node key {key}")
298        })
299    }
300
301    /// `activePrevKeyToDOMMap.get(key)`.
302    fn prev_element_by_key(&self, key: &str) -> Option<Rc<ReconciledNode>> {
303        match self.prev_key_to_dom_map.get(key) {
304            Some(prev) => prev.clone(),
305            None => self.key_to_dom_map.get(key).cloned(),
306        }
307    }
308
309    /// `getPrevElementByKeyOrThrow(key)`.
310    fn get_prev_element_by_key_or_throw(&self, key: &str) -> Rc<ReconciledNode> {
311        self.prev_element_by_key(key).unwrap_or_else(|| {
312            panic!("Reconciliation: could not find DOM element for node key {key}")
313        })
314    }
315
316    /// Keeps a key's value in the previous map before the walk first changes
317    /// it.
318    fn save_prev_element(&mut self, key: &str) {
319        if !self.prev_key_to_dom_map.contains_key(key) {
320            let prev = self.key_to_dom_map.get(key).cloned();
321            self.prev_key_to_dom_map.insert(key.to_owned(), prev);
322        }
323    }
324
325    /// `storeDOMWithKey(key, dom, editor)`.
326    fn store_dom_with_key(&mut self, key: &str, dom: Rc<ReconciledNode>) {
327        self.save_prev_element(key);
328        self.key_to_dom_map.insert(key.to_owned(), dom);
329    }
330
331    /// A new slot container (`$createSlotDOM(name)`).
332    fn create_slot_dom(&self) -> u64 {
333        self.editor.next_id()
334    }
335
336    /// `$createChildrenArray(element, nodeMap)`.
337    fn children(node: &dyn LexicalNode, node_map: &NodeMap) -> Vec<NodeKey> {
338        let mut children = Vec::new();
339        let mut key = node.element().and_then(|e| e.first.clone());
340        while let Some(k) = key {
341            key = node_map.get(&k).and_then(|n| n.base().next.clone());
342            children.push(k);
343        }
344        children
345    }
346
347    /// `$readSlots(node)`.
348    fn read_slots(node: &dyn LexicalNode) -> SlotMap {
349        slots_field(node).cloned().unwrap_or_default()
350    }
351
352    /// `$destroyNode(key, parentDOM)`.
353    fn destroy_node(&mut self, key: &str) {
354        let node = self.prev_node_map.get(key).cloned();
355        // A node moved across parents in the same update still exists in
356        // the next map: its new parent reconciles it.
357        if self.next_node_map.contains_key(key) {
358            return;
359        }
360        self.save_prev_element(key);
361        self.key_to_dom_map.remove(key);
362        let Some(node) = node else {
363            return;
364        };
365        if node.element().is_some() {
366            let children = Self::children(&*node, self.prev_node_map);
367            self.destroy_children(&children);
368        }
369        // Slots are a separate channel from the children, so destroy each
370        // slot subtree too.
371        for slot_key in Self::read_slots(&*node).values() {
372            self.destroy_node(slot_key);
373        }
374        self.set_mutated_node(&*node, NodeMutation::Destroyed);
375    }
376
377    /// `$destroyChildren(children, startIndex, endIndex, dom)`.
378    fn destroy_children(&mut self, children: &[NodeKey]) {
379        for child in children {
380            self.destroy_node(child);
381        }
382    }
383
384    /// `$createNode(key, slot)`. With a slot (`slot !== null`), a node the
385    /// previous tree had in another parent or slot host, or in a slot
386    /// container that is gone, keeps its DOM and is reconciled instead.
387    fn create_node(&mut self, key: &str, slot: Option<Slot>) -> Rc<ReconciledNode> {
388        let node = self
389            .next_node_map
390            .get(key)
391            .cloned()
392            .expect("createNode: node does not exist in nodeMap");
393        if let Some(slot) = slot
394            && let Some(prev_node) = self.prev_node_map.get(key)
395            && let Some(existing_dom) = self.prev_element_by_key(key)
396        {
397            let prev_slot_host = slot_host_key_field(&**prev_node);
398            let next_slot_host = slot_host_key_field(&*node);
399            let model_moved =
400                prev_node.base().parent != node.base().parent || prev_slot_host != next_slot_host;
401            let slot_child_dom_detached =
402                next_slot_host.is_some() && existing_dom.container.get() != slot.container;
403            if model_moved || slot_child_dom_detached {
404                // `slot.insertChild(existingDOM)`.
405                existing_dom.container.set(slot.container);
406                return self.reconcile_node(key);
407            }
408        }
409        let dom = Rc::new(ReconciledNode::default());
410        dom.container.set(slot.and_then(|s| s.container));
411        self.store_dom_with_key(key, dom.clone());
412        if let Some(element) = node.element() {
413            // Slots mount first, ahead of the children.
414            let slots = Self::read_slots(&*node);
415            if slots.len() > 0 {
416                self.mount_slot_children(&slots);
417            }
418            if element.size == 0 {
419                *dom.first_text_key.borrow_mut() = Some(None);
420            } else {
421                let children = Self::children(&*node, self.next_node_map);
422                self.create_children(&children, key);
423            }
424        } else if node.is_decorator() {
425            if let Some(decorator) = node.decorate(self.editor) {
426                self.reconcile_decorator(key, decorator);
427            }
428            let slots = Self::read_slots(&*node);
429            if slots.len() > 0 {
430                self.mount_slot_children(&slots);
431            }
432        }
433        self.set_mutated_node(&*node, NodeMutation::Created);
434        dom
435    }
436
437    /// `$createChildren(children, element, startIndex, endIndex, slot)`,
438    /// for the keys of `element_key`'s children in `children`.
439    fn create_children(&mut self, children: &[NodeKey], element_key: &str) {
440        let outer_saved = self.begin_capture_guard();
441        self.sub_tree_text_format = None;
442        self.sub_tree_text_style = None;
443        self.sub_tree_first_text_key = None;
444        for child in children {
445            let saved = self.begin_capture_guard();
446            self.create_node(child, Some(Slot { container: None }));
447            self.capture_first_text(child);
448            self.end_capture_guard(saved);
449        }
450        let cache_dom = self.key_to_dom_map.get(element_key).unwrap_or_else(|| {
451            panic!("$createChildren: Element with key {element_key} missing from keyToDOMMap")
452        });
453        *cache_dom.first_text_key.borrow_mut() = Some(self.sub_tree_first_text_key.clone());
454        self.end_capture_guard(outer_saved);
455    }
456
457    /// `$mountSlotChildren(node, hostDom, slots)`: each slot value is
458    /// created in a new slot container.
459    fn mount_slot_children(&mut self, slots: &SlotMap) {
460        let outer_saved = self.begin_capture_guard();
461        for slot_key in slots.values() {
462            let container = self.create_slot_dom();
463            let saved = self.begin_capture_guard();
464            self.create_node(
465                slot_key,
466                Some(Slot {
467                    container: Some(container),
468                }),
469            );
470            self.end_capture_guard(saved);
471        }
472        self.end_capture_guard(outer_saved);
473    }
474
475    /// `$reconcileSlotChildren(prevNode, nextNode, hostDom)`: a removed slot's
476    /// value is destroyed; a kept one is reconciled in its container, or
477    /// replaced there; a new one is created in a new container.
478    fn reconcile_slot_children(
479        &mut self,
480        prev_node: &dyn LexicalNode,
481        next_node: &dyn LexicalNode,
482    ) {
483        let prev_slots = Self::read_slots(prev_node);
484        let next_slots = Self::read_slots(next_node);
485        for (name, prev_slot_key) in prev_slots.iter() {
486            if next_slots.get(name).is_none() {
487                self.destroy_node(prev_slot_key);
488            }
489        }
490        let outer_saved = self.begin_capture_guard();
491        for (name, next_slot_key) in next_slots.iter() {
492            let prev_slot_key = prev_slots.get(name);
493            // `$slotContainerForKey(prevSlotKey)`.
494            let container = prev_slot_key
495                .and_then(|k| self.prev_element_by_key(k))
496                .and_then(|dom| dom.container.get());
497            let saved = self.begin_capture_guard();
498            match (container, prev_slot_key) {
499                (Some(_), Some(prev_slot_key)) if prev_slot_key == next_slot_key => {
500                    self.reconcile_node(next_slot_key);
501                }
502                (Some(container), prev_slot_key) => {
503                    if let Some(prev_slot_key) = prev_slot_key {
504                        self.destroy_node(prev_slot_key);
505                    }
506                    self.create_node(
507                        next_slot_key,
508                        Some(Slot {
509                            container: Some(container),
510                        }),
511                    );
512                }
513                (None, _) => {
514                    let container = self.create_slot_dom();
515                    self.create_node(
516                        next_slot_key,
517                        Some(Slot {
518                            container: Some(container),
519                        }),
520                    );
521                }
522            }
523            self.end_capture_guard(saved);
524        }
525        self.end_capture_guard(outer_saved);
526    }
527
528    /// `reconcileDecorator(key, decorator)`: a decorator that changed is
529    /// written to `_pendingDecorators`, made from `_decorators` at the first.
530    fn reconcile_decorator(&mut self, key: &str, decorator: Rc<dyn Any>) {
531        let editor = self.editor;
532        let pending = editor.0.pending_decorators.borrow_mut().take();
533        let mut pending = match pending {
534            Some(pending) => pending,
535            None => {
536                let unchanged = editor
537                    .0
538                    .decorators
539                    .borrow()
540                    .get(key)
541                    .is_some_and(|current| Rc::ptr_eq(current, &decorator));
542                if unchanged {
543                    return;
544                }
545                // `cloneDecorators(activeEditor)`.
546                editor.0.decorators.borrow().clone()
547            }
548        };
549        pending.insert(key, decorator);
550        *editor.0.pending_decorators.borrow_mut() = Some(pending);
551    }
552
553    /// `reconcileTextFormat(element)` and `reconcileTextStyle(element)`.
554    fn reconcile_text_fields(&mut self, element: &dyn LexicalNode) {
555        if self.editor_state_read_only {
556            return;
557        }
558        let data = element.element().expect("an element");
559        let format = self
560            .sub_tree_text_format
561            .filter(|&format| format != data.get_text_format());
562        let style = self
563            .sub_tree_text_style
564            .clone()
565            .filter(|style| style != data.get_text_style());
566        if format.is_some() || style.is_some() {
567            self.text_fields_writes.push(TextFieldsWrite {
568                key: element.get_key().to_owned(),
569                format,
570                style,
571            });
572        }
573    }
574
575    /// `$reconcileChildrenWithDirection(prevElement, nextElement, dom,
576    /// derivesTextFields)`.
577    fn reconcile_children_with_direction(
578        &mut self,
579        prev_element: &dyn LexicalNode,
580        next_element: &dyn LexicalNode,
581        derives_text_fields: bool,
582    ) {
583        self.sub_tree_text_format = None;
584        self.sub_tree_text_style = None;
585        self.sub_tree_first_text_key = None;
586        self.reconcile_children(prev_element, next_element);
587        // The root and shadow roots never expose their text fields.
588        if !is_root_or_shadow_root(next_element) && derives_text_fields {
589            self.reconcile_text_fields(next_element);
590        }
591    }
592
593    /// `$reconcileChildren(prevElement, nextElement, slot)`.
594    fn reconcile_children(&mut self, prev: &dyn LexicalNode, next: &dyn LexicalNode) {
595        let next_key = next.get_key();
596        let cache_dom = self
597            .key_to_dom_map
598            .get(next_key)
599            .cloned()
600            .unwrap_or_else(|| {
601                panic!("$reconcileChildren: Element with key {next_key} missing from keyToDOMMap")
602            });
603        let prev_children = Self::children(prev, self.prev_node_map);
604        let next_children = Self::children(next, self.next_node_map);
605        if prev_children.len() == 1 && next_children.len() == 1 {
606            let (prev_first, next_first) = (&prev_children[0], &next_children[0]);
607            if prev_first == next_first {
608                self.reconcile_node(prev_first);
609            } else {
610                self.get_prev_element_by_key_or_throw(prev_first);
611                self.create_node(next_first, None);
612                self.destroy_node(prev_first);
613            }
614            self.capture_first_text(next_first);
615        } else if prev_children.is_empty() {
616            if !next_children.is_empty() {
617                self.create_children(&next_children, next_key);
618            }
619        } else if next_children.is_empty() {
620            self.destroy_children(&prev_children);
621        } else {
622            self.reconcile_node_children(next_key, &prev_children, &next_children);
623        }
624        *cache_dom.first_text_key.borrow_mut() = Some(self.sub_tree_first_text_key.clone());
625    }
626
627    /// `$reconcileNodeChildren(nextElement, prevChildren, nextChildren,
628    /// prevChildrenLength, nextChildrenLength, slot)`.
629    fn reconcile_node_children(
630        &mut self,
631        next_element_key: &str,
632        prev_children: &[NodeKey],
633        next_children: &[NodeKey],
634    ) {
635        let mut prev_children_set: Option<HashSet<&str>> = None;
636        let mut next_children_set: Option<HashSet<&str>> = None;
637        let (mut prev_index, mut next_index) = (0, 0);
638        while prev_index < prev_children.len() && next_index < next_children.len() {
639            let prev_key = &prev_children[prev_index];
640            let next_key = &next_children[next_index];
641            let saved = self.begin_capture_guard();
642            if prev_key == next_key {
643                self.reconcile_node(next_key);
644                prev_index += 1;
645                next_index += 1;
646            } else {
647                let next_set = next_children_set.get_or_insert_with(|| {
648                    next_children[next_index..]
649                        .iter()
650                        .map(String::as_str)
651                        .collect()
652                });
653                let prev_set = match &mut prev_children_set {
654                    None => prev_children_set.insert(
655                        prev_children[prev_index..]
656                            .iter()
657                            .map(String::as_str)
658                            .collect(),
659                    ),
660                    Some(set) => {
661                        if !set.contains(prev_key.as_str()) {
662                            // Already moved.
663                            prev_index += 1;
664                            self.end_capture_guard(saved);
665                            continue;
666                        }
667                        set
668                    }
669                };
670                if !next_set.contains(prev_key.as_str()) {
671                    // Remove prev.
672                    prev_set.remove(prev_key.as_str());
673                    prev_index += 1;
674                    self.get_prev_element_by_key_or_throw(prev_key);
675                    self.destroy_node(prev_key);
676                    self.end_capture_guard(saved);
677                    continue;
678                }
679                if !prev_set.contains(next_key.as_str()) {
680                    // Create next.
681                    next_index += 1;
682                    self.create_node(next_key, Some(Slot { container: None }));
683                } else {
684                    // Move next.
685                    prev_index += 1;
686                    next_index += 1;
687                    self.get_element_by_key_or_throw(next_key);
688                    self.reconcile_node(next_key);
689                }
690            }
691            self.capture_first_text(next_key);
692            self.end_capture_guard(saved);
693        }
694        let append_new_children = prev_index >= prev_children.len();
695        let remove_old_children = next_index >= next_children.len();
696        if append_new_children && !remove_old_children {
697            self.create_children(&next_children[next_index..], next_element_key);
698        } else if remove_old_children && !append_new_children {
699            self.destroy_children(&prev_children[prev_index..]);
700        }
701    }
702
703    /// `$reconcileNode(key, parentDOM)`.
704    fn reconcile_node(&mut self, key: &str) -> Rc<ReconciledNode> {
705        let (Some(prev_node), Some(next_node)) = (
706            self.prev_node_map.get(key).cloned(),
707            self.next_node_map.get(key).cloned(),
708        ) else {
709            panic!("reconcileNode: prevNode or nextNode does not exist in nodeMap");
710        };
711        let is_dirty = self.treat_all_nodes_as_dirty
712            || self.dirty_leaves.contains(key)
713            || self.dirty_elements.contains(key);
714        let dom = self.get_element_by_key_or_throw(key);
715        // The same version in both states, and clean.
716        let same = Rc::ptr_eq(&prev_node, &next_node);
717        if same && !is_dirty {
718            if prev_node.element().is_some() {
719                self.bubble_child_first_text(&dom);
720            }
721            return dom;
722        }
723        // A cloned node that is dirty was mutated.
724        if !same && is_dirty {
725            self.set_mutated_node(&*next_node, NodeMutation::Updated);
726        }
727        if next_node.update_dom(&*prev_node) {
728            let replacement_dom = self.create_node(key, None);
729            // `parentDOM.replaceChild(replacementDOM, dom)`.
730            replacement_dom.container.set(dom.container.get());
731            self.destroy_node(key);
732            return replacement_dom;
733        }
734        let has_slots =
735            Self::read_slots(&*next_node).len() > 0 || Self::read_slots(&*prev_node).len() > 0;
736        if prev_node.element().is_some() {
737            // Slot edits dirty the host, so a clean host's slots are
738            // unchanged.
739            if is_dirty && has_slots {
740                self.reconcile_slot_children(&*prev_node, &*next_node);
741            }
742            if is_dirty {
743                // A full reconcile treats every node as dirty, but an
744                // element the update did not change, or change inside,
745                // keeps its text fields.
746                let derives_text_fields = !same || self.dirty_elements.contains(key);
747                self.reconcile_children_with_direction(
748                    &*prev_node,
749                    &*next_node,
750                    derives_text_fields,
751                );
752            } else {
753                self.bubble_child_first_text(&dom);
754            }
755        } else if next_node.is_decorator() {
756            if let Some(decorator) = next_node.decorate(self.editor) {
757                self.reconcile_decorator(key, decorator);
758            }
759            if is_dirty && has_slots {
760                self.reconcile_slot_children(&*prev_node, &*next_node);
761            }
762        }
763        dom
764    }
765}
766
767/// `$reconcileRoot(prevEditorState, nextEditorState, editor, dirtyType,
768/// dirtyElements, dirtyLeaves)`: the mutated nodes of the commit. Runs in
769/// the pending state, where the text fields the walk derives are set.
770pub(crate) fn reconcile_root(
771    prev_editor_state: &EditorState,
772    next_editor_state: &EditorState,
773    editor: &Editor,
774) -> MutatedNodes {
775    let key_to_dom_map = std::mem::take(&mut *editor.0.key_to_dom_map.borrow_mut());
776    let (mutated_nodes, key_to_dom_map, writes) = {
777        let dirty = editor.0.dirty.borrow();
778        let prev_node_map = prev_editor_state.0.node_map.borrow();
779        let next_node_map = next_editor_state.0.node_map.borrow();
780        let mut reconciler = Reconciler {
781            editor,
782            treat_all_nodes_as_dirty: dirty.dirty_type == DirtyType::FullReconcile,
783            editor_state_read_only: next_editor_state.0.read_only.get(),
784            dirty_elements: &dirty.elements,
785            dirty_leaves: &dirty.leaves,
786            prev_node_map: &prev_node_map,
787            next_node_map: &next_node_map,
788            listening: editor.has_mutation_listeners(),
789            mutated_nodes: Vec::new(),
790            key_to_dom_map,
791            prev_key_to_dom_map: HashMap::new(),
792            sub_tree_text_format: None,
793            sub_tree_text_style: None,
794            sub_tree_first_text_key: None,
795            text_fields_writes: Vec::new(),
796        };
797        reconciler.reconcile_node("root");
798        (
799            reconciler.mutated_nodes,
800            reconciler.key_to_dom_map,
801            reconciler.text_fields_writes,
802        )
803    };
804    *editor.0.key_to_dom_map.borrow_mut() = key_to_dom_map;
805    // `element.setTextFormat(subTreeTextFormat)` and
806    // `element.setTextStyle(subTreeTextStyle)`, through `getWritable()`.
807    for write in writes {
808        let element = NodeRef::new(write.key);
809        if let Some(format) = write.format {
810            element.set_text_format(format);
811        }
812        if let Some(style) = write.style {
813            element.set_text_style(&style);
814        }
815    }
816    mutated_nodes
817}
818
819/// `resetEditor`'s `keyNodeMap.clear()` and, with a root element,
820/// `setRootElement`'s `this._keyToDOMMap.set('root', nextRootElement)`.
821pub(crate) fn reset_key_to_dom_map(editor: &Editor, has_root_element: bool) {
822    let mut map = editor.0.key_to_dom_map.borrow_mut();
823    map.clear();
824    if has_root_element {
825        map.insert("root".to_owned(), Rc::new(ReconciledNode::default()));
826    }
827}