Skip to main content

lexical_ui/
caret.rs

1//! `caret/LexicalCaret.ts`: carets, caret ranges, text slices and the
2//! document order of carets.
3//!
4//! JS has one class per caret type and direction (`SiblingCaretNext`,
5//! `ChildCaretLast`, `TextPointCaretPrevious`, ...). Here one [`PointCaret`]
6//! value carries its [`CaretKind`], the JS `type` (with the offset of a text
7//! point caret), and its [`CaretDirection`]; [`SiblingCaret`],
8//! [`ChildCaret`], [`TextPointCaret`] and [`NodeCaret`] are aliases of it
9//! that say which kinds a function takes or returns, as the JS types do.
10//!
11//! A caret's origin is a [`NodeRef`], which always resolves the latest
12//! version of the node, so `getLatest()` returns the same caret.
13//! `$filterByMode` stops at roots and at slotted nodes, whose up-link is
14//! their host rather than a parent.
15
16use crate::LexicalError;
17use crate::error::invariant;
18use crate::lexical_utils::get_root;
19use crate::node::{NodeKey, NodeRef};
20use crate::nodes::element::is_root_or_shadow_root;
21use crate::utf16;
22use std::cmp::Ordering;
23use std::collections::HashMap;
24
25/// `CaretDirection`: `'next'` points towards the end of the document,
26/// `'previous'` towards the beginning.
27#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
28pub enum CaretDirection {
29    Next,
30    Previous,
31}
32
33impl CaretDirection {
34    /// The JS name: `"next"` or `"previous"`.
35    pub fn as_str(self) -> &'static str {
36        match self {
37            CaretDirection::Next => "next",
38            CaretDirection::Previous => "previous",
39        }
40    }
41}
42
43/// `flipDirection(direction)`.
44pub fn flip_direction(direction: CaretDirection) -> CaretDirection {
45    match direction {
46        CaretDirection::Next => CaretDirection::Previous,
47        CaretDirection::Previous => CaretDirection::Next,
48    }
49}
50
51/// `RootMode`: whether a traversal up the tree stops at the root only
52/// (`'root'`), or at the root and any shadow root (`'shadowRoot'`).
53#[derive(Clone, Copy, Debug, Default, PartialEq, Eq)]
54pub enum RootMode {
55    #[default]
56    Root,
57    ShadowRoot,
58}
59
60/// A caret's JS `type`, with the offset a text point caret carries.
61#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
62pub enum CaretKind {
63    /// `'sibling'`: from the origin towards its next or previous sibling.
64    Sibling,
65    /// `'child'`: from an element origin towards its first (`next`) or
66    /// last (`previous`) child.
67    Child,
68    /// `'text'`: at `offset` (UTF-16 code units) in a text node origin.
69    Text { offset: usize },
70}
71
72/// `PointCaret`: a [`NodeCaret`] or a [`TextPointCaret`].
73///
74/// Two carets are `==` when JS's `isSamePointCaret` holds: same kind,
75/// direction, origin (by key) and offset.
76#[derive(Clone, Debug, PartialEq, Eq, Hash)]
77pub struct PointCaret {
78    origin: NodeRef,
79    direction: CaretDirection,
80    kind: CaretKind,
81}
82
83/// `SiblingCaret`: a [`PointCaret`] whose kind is [`CaretKind::Sibling`].
84pub type SiblingCaret = PointCaret;
85/// `ChildCaret`: a [`PointCaret`] whose kind is [`CaretKind::Child`].
86pub type ChildCaret = PointCaret;
87/// `TextPointCaret`: a [`PointCaret`] whose kind is [`CaretKind::Text`].
88pub type TextPointCaret = PointCaret;
89/// `NodeCaret`: a sibling or child caret.
90pub type NodeCaret = PointCaret;
91
92/// `$filterByMode(node, mode)`: `None` at a root according to `mode`.
93fn filter_by_mode(node: Option<NodeRef>, mode: RootMode) -> Option<NodeRef> {
94    let node = node?;
95    let is_boundary = match mode {
96        RootMode::Root => node.is_root(),
97        RootMode::ShadowRoot => is_root_or_shadow_root(&*node.get_latest()),
98    };
99    // A slotted node has no parent: it is an upward boundary in every mode.
100    (!is_boundary && crate::slot::get_slot_host_key(&node).is_none()).then_some(node)
101}
102
103impl PointCaret {
104    /// `caret.origin`.
105    pub fn origin(&self) -> &NodeRef {
106        &self.origin
107    }
108
109    /// `caret.direction`.
110    pub fn direction(&self) -> CaretDirection {
111        self.direction
112    }
113
114    pub fn kind(&self) -> CaretKind {
115        self.kind
116    }
117
118    /// `caret.type`: `"sibling"`, `"child"` or `"text"`.
119    pub fn caret_type(&self) -> &'static str {
120        match self.kind {
121            CaretKind::Sibling => "sibling",
122            CaretKind::Child => "child",
123            CaretKind::Text { .. } => "text",
124        }
125    }
126
127    /// `caret.offset` of a text point caret.
128    pub fn offset(&self) -> Option<usize> {
129        match self.kind {
130            CaretKind::Text { offset } => Some(offset),
131            _ => None,
132        }
133    }
134
135    /// `$isTextPointCaret(caret)`.
136    pub fn is_text_point_caret(&self) -> bool {
137        matches!(self.kind, CaretKind::Text { .. })
138    }
139
140    /// `$isSiblingCaret(caret)`: a sibling caret, not a text point caret.
141    pub fn is_sibling_caret(&self) -> bool {
142        self.kind == CaretKind::Sibling
143    }
144
145    /// `$isChildCaret(caret)`.
146    pub fn is_child_caret(&self) -> bool {
147        self.kind == CaretKind::Child
148    }
149
150    /// `getLatest()`: the origin always resolves its latest version, so
151    /// this is the same caret.
152    pub fn get_latest(&self) -> PointCaret {
153        self.clone()
154    }
155
156    /// `getNodeAtCaret()`: the node next to the origin in the caret's
157    /// direction (the first or last child for a child caret).
158    pub fn get_node_at_caret(&self) -> Option<NodeRef> {
159        match (self.kind, self.direction) {
160            (CaretKind::Child, CaretDirection::Next) => self.origin.get_first_child(),
161            (CaretKind::Child, CaretDirection::Previous) => self.origin.get_last_child(),
162            (_, CaretDirection::Next) => self.origin.get_next_sibling(),
163            (_, CaretDirection::Previous) => self.origin.get_previous_sibling(),
164        }
165    }
166
167    /// `getParentAtCaret()`: the origin for a child caret, the origin's
168    /// parent otherwise.
169    pub fn get_parent_at_caret(&self) -> Option<NodeRef> {
170        match self.kind {
171            CaretKind::Child => Some(self.origin.clone()),
172            _ => self.origin.get_parent(),
173        }
174    }
175
176    /// `getAdjacentCaret()`: the sibling caret of the node at the caret.
177    pub fn get_adjacent_caret(&self) -> Option<SiblingCaret> {
178        self.get_node_at_caret()
179            .map(|node| get_sibling_caret(&node, self.direction))
180    }
181
182    /// `getSiblingCaret()`: a sibling caret with the same origin and
183    /// direction.
184    pub fn get_sibling_caret(&self) -> SiblingCaret {
185        match self.kind {
186            CaretKind::Sibling => self.clone(),
187            _ => get_sibling_caret(&self.origin, self.direction),
188        }
189    }
190
191    /// `getChildCaret()`: this caret for a child caret, the child caret of
192    /// an element origin for a sibling caret, `None` otherwise.
193    pub fn get_child_caret(&self) -> Option<ChildCaret> {
194        match self.kind {
195            CaretKind::Child => Some(self.clone()),
196            CaretKind::Sibling => get_child_caret(&self.origin, self.direction),
197            CaretKind::Text { .. } => None,
198        }
199    }
200
201    /// `getParentCaret(mode)`: the sibling caret of the parent at the caret
202    /// in the same direction, `None` at a root according to `mode`.
203    pub fn get_parent_caret(&self, mode: RootMode) -> Option<SiblingCaret> {
204        filter_by_mode(self.get_parent_at_caret(), mode)
205            .map(|parent| get_sibling_caret(&parent, self.direction))
206    }
207
208    /// `getFlipped()`: the same position facing the other way, so that
209    /// flipping twice is the identity.
210    pub fn get_flipped(&self) -> Result<PointCaret, LexicalError> {
211        let dir = flip_direction(self.direction);
212        Ok(match self.kind {
213            CaretKind::Text { offset } => PointCaret {
214                origin: self.origin.clone(),
215                direction: dir,
216                kind: CaretKind::Text { offset },
217            },
218            CaretKind::Child => match self.get_node_at_caret() {
219                Some(node) => get_sibling_caret(&node, dir),
220                None => new_child_caret(&self.origin, dir),
221            },
222            CaretKind::Sibling => match self.get_node_at_caret() {
223                Some(node) => get_sibling_caret(&node, dir),
224                None => new_child_caret(&self.origin.get_parent_or_throw()?, dir),
225            },
226        })
227    }
228
229    /// `isSameNodeCaret(other)`: same direction and origin, where a sibling
230    /// caret and a text point caret count as the same.
231    pub fn is_same_node_caret(&self, other: &PointCaret) -> bool {
232        let same_kind = match self.kind {
233            CaretKind::Child => other.is_child_caret(),
234            _ => !other.is_child_caret(),
235        };
236        same_kind && self.direction == other.direction && self.origin == other.origin
237    }
238
239    /// `isSamePointCaret(other)`: the same caret (also `==`).
240    pub fn is_same_point_caret(&self, other: &PointCaret) -> bool {
241        self == other
242    }
243
244    /// `[Symbol.iterator]()`: the sibling carets of the nodes after the
245    /// caret, in its direction.
246    pub fn iter(&self) -> impl Iterator<Item = SiblingCaret> + use<> {
247        make_stepwise_iterator(
248            self.get_adjacent_caret(),
249            |caret: &Option<SiblingCaret>| caret.as_ref().is_some_and(PointCaret::is_sibling_caret),
250            |caret| caret.and_then(|c| c.get_adjacent_caret()),
251            |caret| caret.clone().expect("checked by has_next"),
252        )
253    }
254
255    /// `remove()`: removes the node at the caret, if any.
256    pub fn remove(&self) -> Result<(), LexicalError> {
257        if let Some(node) = self.get_node_at_caret() {
258            node.remove(false)?;
259        }
260        Ok(())
261    }
262
263    /// `insert(node)`: inserts `node` next to the origin in the caret's
264    /// direction (before the node at the caret).
265    pub fn insert(&self, node: &NodeRef) -> Result<(), LexicalError> {
266        match (self.kind, self.direction) {
267            (CaretKind::Child, CaretDirection::Next) => {
268                self.origin.splice(0, 0, std::slice::from_ref(node))
269            }
270            (CaretKind::Child, CaretDirection::Previous) => self.origin.splice(
271                self.origin.get_children_size(),
272                0,
273                std::slice::from_ref(node),
274            ),
275            (_, CaretDirection::Next) => self.origin.insert_after(node, true).map(drop),
276            (_, CaretDirection::Previous) => self.origin.insert_before(node, true).map(drop),
277        }
278    }
279
280    /// `replaceOrInsert(node, includeChildren)`: replaces the node at the
281    /// caret with `node`, or inserts it if there is none.
282    pub fn replace_or_insert(
283        &self,
284        node: &NodeRef,
285        include_children: bool,
286    ) -> Result<(), LexicalError> {
287        let target = self.get_node_at_caret();
288        if node == &self.origin || Some(node) == target.as_ref() {
289            // do nothing
290        } else if let Some(target) = target {
291            target.replace(node, include_children)?;
292        } else {
293            self.insert(node)?;
294        }
295        Ok(())
296    }
297
298    /// `splice(deleteCount, nodes, nodesDirection)`: replaces the
299    /// `delete_count` nodes after the caret with `nodes`, which are in
300    /// `nodes_direction` order (JS's default is `next`).
301    pub fn splice(
302        &self,
303        delete_count: usize,
304        nodes: &[NodeRef],
305        nodes_direction: CaretDirection,
306    ) -> Result<(), LexicalError> {
307        let mut node_iter = nodes.to_vec();
308        if nodes_direction != self.direction {
309            node_iter.reverse();
310        }
311        let mut caret = self.clone();
312        let parent = self.get_parent_at_caret();
313        // Insertion-ordered, like JS's Map.
314        let mut nodes_to_remove: Vec<NodeRef> = Vec::new();
315        // Find all of the nodes we expect to remove first, so we don't have
316        // to worry about the cases where there is overlap between the nodes
317        // to insert and the nodes to remove
318        let mut remove_caret = caret.get_adjacent_caret();
319        while let Some(rc) = remove_caret.filter(|_| nodes_to_remove.len() < delete_count) {
320            crate::lexical_utils::get_writable(rc.origin.get_key());
321            if !nodes_to_remove.contains(&rc.origin) {
322                nodes_to_remove.push(rc.origin.clone());
323            }
324            remove_caret = rc.get_adjacent_caret();
325        }
326        for node in &node_iter {
327            if !nodes_to_remove.is_empty() {
328                let Some(target) = caret.get_node_at_caret() else {
329                    let keys: Vec<&str> = nodes_to_remove.iter().map(NodeRef::get_key).collect();
330                    return Err(LexicalError::new(format!(
331                        "NodeCaret.splice: Underflow of expected nodesToRemove during splice (keys: {})",
332                        keys.join(" ")
333                    )));
334                };
335                nodes_to_remove.retain(|n| n != &target && n != node);
336                if &target == node || &caret.origin == node {
337                    // do nothing, it's already in the right place
338                } else {
339                    if node
340                        .get_parent()
341                        .is_some_and(|p| Some(&p) == parent.as_ref())
342                    {
343                        // It's a sibling somewhere else in this node, so
344                        // unparent it first
345                        node.remove(false)?;
346                    }
347                    target.replace(node, false)?;
348                }
349            } else {
350                caret.insert(node)?;
351            }
352            caret = get_sibling_caret(node, self.direction);
353        }
354        for node in &nodes_to_remove {
355            node.remove(false)?;
356        }
357        Ok(())
358    }
359}
360
361fn new_child_caret(origin: &NodeRef, direction: CaretDirection) -> ChildCaret {
362    PointCaret {
363        origin: origin.clone(),
364        direction,
365        kind: CaretKind::Child,
366    }
367}
368
369/// `$getSiblingCaret(origin, direction)`: a caret pointing from `origin` to
370/// its next or previous sibling. JS returns `null` for a `null` origin;
371/// here that is `Option::map`.
372pub fn get_sibling_caret(origin: &NodeRef, direction: CaretDirection) -> SiblingCaret {
373    PointCaret {
374        origin: origin.clone(),
375        direction,
376        kind: CaretKind::Sibling,
377    }
378}
379
380/// An offset into a text node: a number of UTF-16 code units, or the end
381/// in a direction (`'next'` is the end, `'previous'` the start), as JS's
382/// `number | CaretDirection`.
383#[derive(Clone, Copy, Debug, PartialEq, Eq)]
384pub enum TextOffset {
385    Offset(usize),
386    End(CaretDirection),
387}
388
389impl From<usize> for TextOffset {
390    fn from(offset: usize) -> Self {
391        TextOffset::Offset(offset)
392    }
393}
394
395impl From<CaretDirection> for TextOffset {
396    fn from(direction: CaretDirection) -> Self {
397        TextOffset::End(direction)
398    }
399}
400
401/// `$getTextPointCaret(origin, direction, offset)`: a caret at `offset` in
402/// the text node `origin`. An offset past the end is an error, as in JS's
403/// development build.
404pub fn get_text_point_caret(
405    origin: &NodeRef,
406    direction: CaretDirection,
407    offset: impl Into<TextOffset>,
408) -> Result<TextPointCaret, LexicalError> {
409    Ok(PointCaret {
410        origin: origin.clone(),
411        direction,
412        kind: CaretKind::Text {
413            offset: get_text_node_offset(origin, offset.into(), false)?,
414        },
415    })
416}
417
418/// [`get_text_point_caret`] at an end of the text, which can't fail.
419pub(crate) fn get_text_point_caret_at_end(
420    origin: &NodeRef,
421    direction: CaretDirection,
422    end: CaretDirection,
423) -> TextPointCaret {
424    get_text_point_caret(origin, direction, end).expect("an end is always a valid offset")
425}
426
427/// `$getTextNodeOffset(origin, offset, mode)`: the numeric offset of
428/// `offset` in `origin`. Out of bounds it is an error (JS's development
429/// build), or clamped when `clamp` (`mode` `'clamp'`).
430pub fn get_text_node_offset(
431    origin: &NodeRef,
432    offset: TextOffset,
433    clamp: bool,
434) -> Result<usize, LexicalError> {
435    let size = origin.get_text_content_size();
436    let numeric_offset = match offset {
437        TextOffset::End(CaretDirection::Next) => size,
438        TextOffset::End(CaretDirection::Previous) => 0,
439        TextOffset::Offset(offset) => offset,
440    };
441    if numeric_offset > size {
442        invariant!(
443            clamp,
444            "$getTextNodeOffset: invalid offset {numeric_offset} for size {size} at key {}",
445            origin.get_key()
446        );
447        return Ok(size);
448    }
449    Ok(numeric_offset)
450}
451
452/// `TextPointCaretSlice`: a text point caret and a signed distance from its
453/// offset. A negative distance selects the text before the offset, a
454/// positive one the text after it, whatever the caret's direction.
455#[derive(Clone, Debug, PartialEq, Eq)]
456pub struct TextPointCaretSlice {
457    pub caret: TextPointCaret,
458    pub distance: isize,
459}
460
461impl TextPointCaretSlice {
462    fn offset(&self) -> usize {
463        self.caret.offset().expect("a text point caret")
464    }
465
466    /// `getSliceIndices()`: the start and end of the slice in the text.
467    pub fn get_slice_indices(&self) -> (usize, usize) {
468        let offset = self.offset();
469        let offset_b = offset.saturating_add_signed(self.distance);
470        if offset_b < offset {
471            (offset_b, offset)
472        } else {
473            (offset, offset_b)
474        }
475    }
476
477    /// `getTextContent()`: the text of the slice.
478    pub fn get_text_content(&self) -> String {
479        let (start, end) = self.get_slice_indices();
480        utf16::slice(&self.caret.origin.get_text_content(), start, end)
481    }
482
483    /// `getTextContentSize()`.
484    pub fn get_text_content_size(&self) -> usize {
485        self.distance.unsigned_abs()
486    }
487
488    /// `removeTextSlice()`: removes the slice's text, and returns the caret
489    /// at its start, in the same direction.
490    pub fn remove_text_slice(&self) -> Result<TextPointCaret, LexicalError> {
491        let origin = &self.caret.origin;
492        let (start, end) = self.get_slice_indices();
493        // `$setTextContentSpliced`: text edits aren't recorded in this port.
494        let content = origin.get_text_content();
495        let next = utf16::slice(&content, 0, start) + &utf16::slice_from(&content, end);
496        origin.set_text_content(&next);
497        get_text_point_caret(origin, self.caret.direction, start)
498    }
499}
500
501/// `$getTextPointCaretSlice(caret, distance)`.
502pub fn get_text_point_caret_slice(caret: TextPointCaret, distance: isize) -> TextPointCaretSlice {
503    debug_assert!(caret.is_text_point_caret());
504    TextPointCaretSlice { caret, distance }
505}
506
507/// `$getChildCaret(origin, direction)`: a caret pointing to the first
508/// (`next`) or last (`previous`) child of `origin`, or `None` if it isn't
509/// an element.
510pub fn get_child_caret(origin: &NodeRef, direction: CaretDirection) -> Option<ChildCaret> {
511    origin
512        .is_element()
513        .then(|| new_child_caret(origin, direction))
514}
515
516/// `$getChildCaretOrSelf(caret)`: the caret's child caret if it has one,
517/// otherwise the caret.
518pub fn get_child_caret_or_self(caret: Option<PointCaret>) -> Option<PointCaret> {
519    caret.map(|c| c.get_child_caret().unwrap_or(c))
520}
521
522/// `$getAdjacentChildCaret(caret)`: the adjacent caret, or its child caret
523/// when its origin is an element. With `getParentCaret` this walks the
524/// whole tree depth first.
525pub fn get_adjacent_child_caret(caret: Option<&NodeCaret>) -> Option<NodeCaret> {
526    get_child_caret_or_self(caret?.get_adjacent_caret())
527}
528
529/// `CaretRange`: a range selection as a pair of carets in one direction.
530#[derive(Clone, Debug, PartialEq, Eq)]
531pub struct CaretRange {
532    pub anchor: PointCaret,
533    pub focus: PointCaret,
534    direction: CaretDirection,
535}
536
537impl CaretRange {
538    /// `range.direction`.
539    pub fn direction(&self) -> CaretDirection {
540        self.direction
541    }
542
543    /// `getLatest()`: the same range, as carets always resolve the latest
544    /// nodes.
545    pub fn get_latest(&self) -> CaretRange {
546        self.clone()
547    }
548
549    /// `isCollapsed()`: whether anchor and focus are the same caret.
550    pub fn is_collapsed(&self) -> bool {
551        self.anchor.is_same_point_caret(&self.focus)
552    }
553
554    /// `getTextSlices()`: the slices of the text point carets at the anchor
555    /// and the focus. When both are on one text node, the first holds the
556    /// whole slice and the second is `None`.
557    pub fn get_text_slices(&self) -> [Option<TextPointCaretSlice>; 2] {
558        let anchor = self.anchor.get_latest();
559        let focus = self.focus.get_latest();
560        if let (Some(anchor_offset), Some(focus_offset)) = (anchor.offset(), focus.offset())
561            && anchor.is_same_node_caret(&focus)
562        {
563            let distance = focus_offset as isize - anchor_offset as isize;
564            return [Some(get_text_point_caret_slice(anchor, distance)), None];
565        }
566        [
567            anchor
568                .is_text_point_caret()
569                .then(|| get_slice_from_text_point_caret(anchor, false)),
570            focus
571                .is_text_point_caret()
572                .then(|| get_slice_from_text_point_caret(focus, true)),
573        ]
574    }
575
576    /// `iterNodeCarets(rootMode)`: the carets between anchor and focus, in
577    /// pre-order, without the text slices at either end. An element is
578    /// yielded as a child caret on enter and a sibling caret on leave.
579    pub fn iter_node_carets(&self, root_mode: RootMode) -> impl Iterator<Item = NodeCaret> + use<> {
580        let anchor = if self.anchor.is_text_point_caret() {
581            self.anchor.get_sibling_caret()
582        } else {
583            self.anchor.get_latest()
584        };
585        let focus = self.focus.get_latest();
586        let is_text_focus = focus.is_text_point_caret();
587        let step = {
588            let focus = focus.clone();
589            move |state: &NodeCaret| -> Option<NodeCaret> {
590                if state.is_same_node_caret(&focus) {
591                    None
592                } else {
593                    get_adjacent_child_caret(Some(state))
594                        .or_else(|| state.get_parent_caret(root_mode))
595                }
596            }
597        };
598        let initial = if anchor.is_same_node_caret(&focus) {
599            None
600        } else {
601            step(&anchor)
602        };
603        make_stepwise_iterator(
604            initial,
605            move |state: &Option<NodeCaret>| {
606                state
607                    .as_ref()
608                    .is_some_and(|s| !(is_text_focus && focus.is_same_node_caret(s)))
609            },
610            move |state| state.and_then(|s| step(&s)),
611            |state| state.clone().expect("checked by has_next"),
612        )
613    }
614
615    /// `[Symbol.iterator]()`: `iterNodeCarets('root')`.
616    pub fn iter(&self) -> impl Iterator<Item = NodeCaret> + use<> {
617        self.iter_node_carets(RootMode::Root)
618    }
619}
620
621/// `$getSliceFromTextPointCaret(caret, anchorOrFocus)`: the slice from the
622/// caret to the end of its text the range covers.
623fn get_slice_from_text_point_caret(caret: TextPointCaret, is_focus: bool) -> TextPointCaretSlice {
624    let direction = caret.direction;
625    let end = if is_focus {
626        flip_direction(direction)
627    } else {
628        direction
629    };
630    let offset_b = get_text_node_offset(&caret.origin, end.into(), false)
631        .expect("an end is always a valid offset");
632    let offset = caret.offset().expect("a text point caret");
633    get_text_point_caret_slice(caret, offset_b as isize - offset as isize)
634}
635
636/// `$getCaretInDirection(caret, direction)`: the caret if it is in
637/// `direction`, otherwise `caret.getFlipped()`.
638pub fn get_caret_in_direction(
639    caret: &PointCaret,
640    direction: CaretDirection,
641) -> Result<PointCaret, LexicalError> {
642    if caret.direction == direction {
643        Ok(caret.clone())
644    } else {
645        caret.get_flipped()
646    }
647}
648
649/// `$extendCaretToRange(anchor)`: a range from `anchor` to the end of the
650/// document in its direction.
651pub fn extend_caret_to_range(anchor: &PointCaret) -> Result<CaretRange, LexicalError> {
652    let root_caret = new_child_caret(&get_root(), flip_direction(anchor.direction));
653    get_caret_range(
654        anchor.clone(),
655        get_caret_in_direction(&root_caret, anchor.direction)?,
656    )
657}
658
659/// `$getCollapsedCaretRange(anchor)`.
660pub fn get_collapsed_caret_range(anchor: PointCaret) -> CaretRange {
661    CaretRange {
662        anchor: anchor.clone(),
663        focus: anchor.clone(),
664        direction: anchor.direction,
665    }
666}
667
668/// `$getCaretRange(anchor, focus)`: a range between carets in the same
669/// direction, where the anchor points towards the focus.
670pub fn get_caret_range(anchor: PointCaret, focus: PointCaret) -> Result<CaretRange, LexicalError> {
671    invariant!(
672        anchor.direction == focus.direction,
673        "$getCaretRange: anchor and focus must be in the same direction"
674    );
675    let direction = anchor.direction;
676    Ok(CaretRange {
677        anchor,
678        focus,
679        direction,
680    })
681}
682
683/// `makeStepwiseIterator({initial, hasNext, step, map})`: yields
684/// `map(state)` while `has_next(state)`, stepping the state after each.
685pub fn make_stepwise_iterator<State, Value>(
686    initial: State,
687    has_next: impl FnMut(&State) -> bool,
688    step: impl FnMut(State) -> State,
689    map: impl FnMut(&State) -> Value,
690) -> impl Iterator<Item = Value> {
691    StepwiseIterator {
692        state: Some(initial),
693        has_next,
694        step,
695        map,
696    }
697}
698
699struct StepwiseIterator<State, H, S, M> {
700    // Only `None` while stepping.
701    state: Option<State>,
702    has_next: H,
703    step: S,
704    map: M,
705}
706
707impl<State, Value, H, S, M> Iterator for StepwiseIterator<State, H, S, M>
708where
709    H: FnMut(&State) -> bool,
710    S: FnMut(State) -> State,
711    M: FnMut(&State) -> Value,
712{
713    type Item = Value;
714
715    fn next(&mut self) -> Option<Value> {
716        let state = self.state.as_ref()?;
717        if !(self.has_next)(state) {
718            return None;
719        }
720        let value = (self.map)(state);
721        let state = self.state.take().expect("checked above");
722        self.state = Some((self.step)(state));
723        Some(value)
724    }
725}
726
727/// `$comparePointCaretNext(a, b)`: the total order of `next` carets in
728/// which a [`CaretRange`] iterates them. For one origin, a child caret and
729/// a text point caret come before the sibling caret. Carets whose origins
730/// have no common ancestor are an error.
731pub fn compare_point_caret_next(a: &PointCaret, b: &PointCaret) -> Result<Ordering, LexicalError> {
732    let compare = get_common_ancestor(&a.origin, &b.origin);
733    let Some(compare) = compare else {
734        return Err(LexicalError::new(format!(
735            "$comparePointCaretNext: a (key {}) and b (key {}) do not have a common ancestor",
736            a.origin.get_key(),
737            b.origin.get_key()
738        )));
739    };
740    Ok(match compare {
741        CommonAncestorResult::Same { .. } => compare_same_origin_carets(a, b),
742        CommonAncestorResult::Ancestor { .. } => {
743            if a.is_child_caret() {
744                Ordering::Less
745            } else {
746                Ordering::Greater
747            }
748        }
749        CommonAncestorResult::Descendant { .. } => {
750            if b.is_child_caret() {
751                Ordering::Greater
752            } else {
753                Ordering::Less
754            }
755        }
756        CommonAncestorResult::Branch { a, b, .. } => {
757            get_common_ancestor_result_branch_order(&a, &b)
758        }
759    })
760}
761
762/// `$compareSameOriginCarets(a, b)`.
763fn compare_same_origin_carets(a: &PointCaret, b: &PointCaret) -> Ordering {
764    match (a.kind, b.kind) {
765        (CaretKind::Text { offset: x }, CaretKind::Text { offset: y }) => x.cmp(&y),
766        (x, y) if x == y => Ordering::Equal,
767        (CaretKind::Text { .. }, _) => Ordering::Less,
768        (_, CaretKind::Text { .. }) => Ordering::Greater,
769        (CaretKind::Child, _) => Ordering::Less,
770        _ => Ordering::Greater,
771    }
772}
773
774/// `$getCommonAncestorResultBranchOrder(compare)`: `Less` if `a` (a sibling
775/// of `b`) comes first, `Greater` otherwise.
776pub fn get_common_ancestor_result_branch_order(a: &NodeRef, b: &NodeRef) -> Ordering {
777    let mut na = Some(a.clone());
778    let mut nb = Some(b.clone());
779    while let (Some(x), Some(y)) = (&na, &nb) {
780        if x == b {
781            return Ordering::Less;
782        } else if y == a {
783            return Ordering::Greater;
784        }
785        na = x.get_next_sibling();
786        nb = y.get_next_sibling();
787    }
788    if na.is_none() {
789        Ordering::Greater
790    } else {
791        Ordering::Less
792    }
793}
794
795/// `CommonAncestorResult`: how two nodes relate through their common
796/// ancestor.
797#[derive(Clone, Debug, PartialEq, Eq)]
798pub enum CommonAncestorResult {
799    /// The two nodes are the same.
800    Same { common_ancestor: NodeRef },
801    /// `a` is an ancestor of `b`.
802    Ancestor { common_ancestor: NodeRef },
803    /// `a` is a descendant of `b`.
804    Descendant { common_ancestor: NodeRef },
805    /// `a` and `b` are on different branches; `a` and `b` here are their
806    /// ancestors (or themselves) that are children of `common_ancestor`.
807    Branch {
808        common_ancestor: NodeRef,
809        a: NodeRef,
810        b: NodeRef,
811    },
812}
813
814impl CommonAncestorResult {
815    /// `result.commonAncestor`.
816    pub fn common_ancestor(&self) -> &NodeRef {
817        match self {
818            CommonAncestorResult::Same { common_ancestor }
819            | CommonAncestorResult::Ancestor { common_ancestor }
820            | CommonAncestorResult::Descendant { common_ancestor }
821            | CommonAncestorResult::Branch {
822                common_ancestor, ..
823            } => common_ancestor,
824        }
825    }
826}
827
828/// `$initialElementTuple(node)`: the node and no child for an element, its
829/// parent and itself otherwise.
830fn initial_element_tuple(node: &NodeRef) -> (Option<NodeRef>, Option<NodeRef>) {
831    if node.is_element() {
832        (Some(node.clone()), None)
833    } else {
834        (node.get_parent(), Some(node.clone()))
835    }
836}
837
838/// `$getCommonAncestor(a, b)`: how `a` and `b` relate, or `None` if they
839/// have no common ancestor.
840pub fn get_common_ancestor(a: &NodeRef, b: &NodeRef) -> Option<CommonAncestorResult> {
841    if a == b {
842        return Some(CommonAncestorResult::Same {
843            common_ancestor: a.clone(),
844        });
845    }
846    // Map of parent -> child entries based on a and its ancestors
847    let mut a_map: HashMap<NodeKey, Option<NodeRef>> = HashMap::new();
848    let (mut parent, mut child) = initial_element_tuple(a);
849    while let Some(p) = parent {
850        parent = p.get_parent();
851        a_map.insert(p.get_key().to_owned(), child);
852        child = Some(p);
853    }
854    let (mut parent, mut child) = initial_element_tuple(b);
855    while let Some(p) = parent {
856        if let Some(a_child) = a_map.get(p.get_key()) {
857            return Some(match (a_child, child) {
858                (None, _) => {
859                    // a is the ancestor
860                    assert!(&p == a, "$originComparison: ancestor logic error");
861                    CommonAncestorResult::Ancestor { common_ancestor: p }
862                }
863                (Some(_), None) => {
864                    // b is the ancestor
865                    assert!(&p == b, "$originComparison: descendant logic error");
866                    CommonAncestorResult::Descendant { common_ancestor: p }
867                }
868                (Some(a_child), Some(child)) => {
869                    assert!(
870                        (a_child.is_element() || a_child == a)
871                            && (child.is_element() || &child == b)
872                            && a_child.get_parent().as_ref() == Some(&p)
873                            && child.get_parent().as_ref() == Some(&p),
874                        "$originComparison: branch logic error"
875                    );
876                    CommonAncestorResult::Branch {
877                        common_ancestor: p,
878                        a: a_child.clone(),
879                        b: child,
880                    }
881                }
882            });
883        }
884        parent = p.get_parent();
885        child = Some(p);
886    }
887    None
888}
889
890/// `CommonAncestorAcrossSlotsResult` (`@experimental`): like
891/// [`CommonAncestorResult`], except that the common ancestor may be a
892/// decorator slot host, and the node on either side below it may be one of
893/// its slot values rather than a child.
894#[derive(Clone, Debug, PartialEq, Eq)]
895pub enum CommonAncestorAcrossSlotsResult {
896    Same {
897        common_ancestor: NodeRef,
898    },
899    Ancestor {
900        common_ancestor: NodeRef,
901        b: NodeRef,
902    },
903    Descendant {
904        common_ancestor: NodeRef,
905        a: NodeRef,
906    },
907    Branch {
908        common_ancestor: NodeRef,
909        a: NodeRef,
910        b: NodeRef,
911    },
912}
913
914/// `$getParentAcrossSlots(node)`.
915fn get_parent_across_slots(node: &NodeRef) -> Option<NodeRef> {
916    node.get_parent()
917        .or_else(|| crate::slot::get_slot_host(node))
918}
919
920/// `$getCommonAncestorAcrossSlots(a, b)` (`@experimental`): like
921/// [`get_common_ancestor`], but a slot value's parent is its host.
922pub fn get_common_ancestor_across_slots(
923    a: &NodeRef,
924    b: &NodeRef,
925) -> Option<CommonAncestorAcrossSlotsResult> {
926    let mut a_path: HashMap<NodeKey, Option<NodeRef>> = HashMap::new();
927    let mut child: Option<NodeRef> = None;
928    let mut node = Some(a.clone());
929    while let Some(n) = node {
930        a_path.insert(n.get_key().to_owned(), child);
931        node = get_parent_across_slots(&n);
932        child = Some(n);
933    }
934    let mut child: Option<NodeRef> = None;
935    let mut node = Some(b.clone());
936    while let Some(n) = node {
937        if let Some(a_child) = a_path.get(n.get_key()) {
938            let common_ancestor = n.clone();
939            return Some(match (a_child.clone(), child) {
940                (None, None) => CommonAncestorAcrossSlotsResult::Same { common_ancestor },
941                (None, Some(b)) => CommonAncestorAcrossSlotsResult::Ancestor { common_ancestor, b },
942                (Some(a), None) => {
943                    CommonAncestorAcrossSlotsResult::Descendant { common_ancestor, a }
944                }
945                (Some(a), Some(b)) => CommonAncestorAcrossSlotsResult::Branch {
946                    common_ancestor,
947                    a,
948                    b,
949                },
950            });
951        }
952        node = get_parent_across_slots(&n);
953        child = Some(n);
954    }
955    None
956}
957
958/// `$comparePointCaretNextAcrossSlots(a, b)` (`@experimental`): like
959/// [`compare_point_caret_next`], with a host's slot values, in slot order,
960/// after the points before the host and before its children. `None` when
961/// the carets have no common ancestor.
962pub fn compare_point_caret_next_across_slots(a: &PointCaret, b: &PointCaret) -> Option<Ordering> {
963    use crate::slot::get_slot_host_key;
964    Some(
965        match get_common_ancestor_across_slots(&a.origin, &b.origin)? {
966            CommonAncestorAcrossSlotsResult::Same { .. } => compare_same_origin_carets(a, b),
967            CommonAncestorAcrossSlotsResult::Ancestor { b: node_b, .. } => {
968                if a.is_child_caret() && get_slot_host_key(&node_b).is_none() {
969                    Ordering::Less
970                } else {
971                    Ordering::Greater
972                }
973            }
974            CommonAncestorAcrossSlotsResult::Descendant { a: node_a, .. } => {
975                if b.is_child_caret() && get_slot_host_key(&node_a).is_none() {
976                    Ordering::Greater
977                } else {
978                    Ordering::Less
979                }
980            }
981            CommonAncestorAcrossSlotsResult::Branch {
982                common_ancestor,
983                a: node_a,
984                b: node_b,
985            } => {
986                let a_slot = get_slot_host_key(&node_a).is_some();
987                let b_slot = get_slot_host_key(&node_b).is_some();
988                if a_slot && b_slot {
989                    // Two slot values of one host: slot order.
990                    for key in crate::slot::get_slot_map(&common_ancestor).values() {
991                        if key == node_a.get_key() || key == node_b.get_key() {
992                            return Some(if key == node_a.get_key() {
993                                Ordering::Less
994                            } else {
995                                Ordering::Greater
996                            });
997                        }
998                    }
999                }
1000                if a_slot {
1001                    Ordering::Less
1002                } else if b_slot {
1003                    Ordering::Greater
1004                } else if node_a.is_before(&node_b) {
1005                    Ordering::Less
1006                } else {
1007                    Ordering::Greater
1008                }
1009            }
1010        },
1011    )
1012}