use crate::LexicalError;
use crate::error::invariant;
use crate::lexical_utils::get_root;
use crate::node::{NodeKey, NodeRef};
use crate::nodes::element::is_root_or_shadow_root;
use crate::utf16;
use std::cmp::Ordering;
use std::collections::HashMap;
#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
pub enum CaretDirection {
Next,
Previous,
}
impl CaretDirection {
pub fn as_str(self) -> &'static str {
match self {
CaretDirection::Next => "next",
CaretDirection::Previous => "previous",
}
}
}
pub fn flip_direction(direction: CaretDirection) -> CaretDirection {
match direction {
CaretDirection::Next => CaretDirection::Previous,
CaretDirection::Previous => CaretDirection::Next,
}
}
#[derive(Clone, Copy, Debug, Default, PartialEq, Eq)]
pub enum RootMode {
#[default]
Root,
ShadowRoot,
}
#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
pub enum CaretKind {
Sibling,
Child,
Text { offset: usize },
}
#[derive(Clone, Debug, PartialEq, Eq, Hash)]
pub struct PointCaret {
origin: NodeRef,
direction: CaretDirection,
kind: CaretKind,
}
pub type SiblingCaret = PointCaret;
pub type ChildCaret = PointCaret;
pub type TextPointCaret = PointCaret;
pub type NodeCaret = PointCaret;
fn filter_by_mode(node: Option<NodeRef>, mode: RootMode) -> Option<NodeRef> {
let node = node?;
let is_boundary = match mode {
RootMode::Root => node.is_root(),
RootMode::ShadowRoot => is_root_or_shadow_root(&*node.get_latest()),
};
(!is_boundary && crate::slot::get_slot_host_key(&node).is_none()).then_some(node)
}
impl PointCaret {
pub fn origin(&self) -> &NodeRef {
&self.origin
}
pub fn direction(&self) -> CaretDirection {
self.direction
}
pub fn kind(&self) -> CaretKind {
self.kind
}
pub fn caret_type(&self) -> &'static str {
match self.kind {
CaretKind::Sibling => "sibling",
CaretKind::Child => "child",
CaretKind::Text { .. } => "text",
}
}
pub fn offset(&self) -> Option<usize> {
match self.kind {
CaretKind::Text { offset } => Some(offset),
_ => None,
}
}
pub fn is_text_point_caret(&self) -> bool {
matches!(self.kind, CaretKind::Text { .. })
}
pub fn is_sibling_caret(&self) -> bool {
self.kind == CaretKind::Sibling
}
pub fn is_child_caret(&self) -> bool {
self.kind == CaretKind::Child
}
pub fn get_latest(&self) -> PointCaret {
self.clone()
}
pub fn get_node_at_caret(&self) -> Option<NodeRef> {
match (self.kind, self.direction) {
(CaretKind::Child, CaretDirection::Next) => self.origin.get_first_child(),
(CaretKind::Child, CaretDirection::Previous) => self.origin.get_last_child(),
(_, CaretDirection::Next) => self.origin.get_next_sibling(),
(_, CaretDirection::Previous) => self.origin.get_previous_sibling(),
}
}
pub fn get_parent_at_caret(&self) -> Option<NodeRef> {
match self.kind {
CaretKind::Child => Some(self.origin.clone()),
_ => self.origin.get_parent(),
}
}
pub fn get_adjacent_caret(&self) -> Option<SiblingCaret> {
self.get_node_at_caret()
.map(|node| get_sibling_caret(&node, self.direction))
}
pub fn get_sibling_caret(&self) -> SiblingCaret {
match self.kind {
CaretKind::Sibling => self.clone(),
_ => get_sibling_caret(&self.origin, self.direction),
}
}
pub fn get_child_caret(&self) -> Option<ChildCaret> {
match self.kind {
CaretKind::Child => Some(self.clone()),
CaretKind::Sibling => get_child_caret(&self.origin, self.direction),
CaretKind::Text { .. } => None,
}
}
pub fn get_parent_caret(&self, mode: RootMode) -> Option<SiblingCaret> {
filter_by_mode(self.get_parent_at_caret(), mode)
.map(|parent| get_sibling_caret(&parent, self.direction))
}
pub fn get_flipped(&self) -> Result<PointCaret, LexicalError> {
let dir = flip_direction(self.direction);
Ok(match self.kind {
CaretKind::Text { offset } => PointCaret {
origin: self.origin.clone(),
direction: dir,
kind: CaretKind::Text { offset },
},
CaretKind::Child => match self.get_node_at_caret() {
Some(node) => get_sibling_caret(&node, dir),
None => new_child_caret(&self.origin, dir),
},
CaretKind::Sibling => match self.get_node_at_caret() {
Some(node) => get_sibling_caret(&node, dir),
None => new_child_caret(&self.origin.get_parent_or_throw()?, dir),
},
})
}
pub fn is_same_node_caret(&self, other: &PointCaret) -> bool {
let same_kind = match self.kind {
CaretKind::Child => other.is_child_caret(),
_ => !other.is_child_caret(),
};
same_kind && self.direction == other.direction && self.origin == other.origin
}
pub fn is_same_point_caret(&self, other: &PointCaret) -> bool {
self == other
}
pub fn iter(&self) -> impl Iterator<Item = SiblingCaret> + use<> {
make_stepwise_iterator(
self.get_adjacent_caret(),
|caret: &Option<SiblingCaret>| caret.as_ref().is_some_and(PointCaret::is_sibling_caret),
|caret| caret.and_then(|c| c.get_adjacent_caret()),
|caret| caret.clone().expect("checked by has_next"),
)
}
pub fn remove(&self) -> Result<(), LexicalError> {
if let Some(node) = self.get_node_at_caret() {
node.remove(false)?;
}
Ok(())
}
pub fn insert(&self, node: &NodeRef) -> Result<(), LexicalError> {
match (self.kind, self.direction) {
(CaretKind::Child, CaretDirection::Next) => {
self.origin.splice(0, 0, std::slice::from_ref(node))
}
(CaretKind::Child, CaretDirection::Previous) => self.origin.splice(
self.origin.get_children_size(),
0,
std::slice::from_ref(node),
),
(_, CaretDirection::Next) => self.origin.insert_after(node, true).map(drop),
(_, CaretDirection::Previous) => self.origin.insert_before(node, true).map(drop),
}
}
pub fn replace_or_insert(
&self,
node: &NodeRef,
include_children: bool,
) -> Result<(), LexicalError> {
let target = self.get_node_at_caret();
if node == &self.origin || Some(node) == target.as_ref() {
} else if let Some(target) = target {
target.replace(node, include_children)?;
} else {
self.insert(node)?;
}
Ok(())
}
pub fn splice(
&self,
delete_count: usize,
nodes: &[NodeRef],
nodes_direction: CaretDirection,
) -> Result<(), LexicalError> {
let mut node_iter = nodes.to_vec();
if nodes_direction != self.direction {
node_iter.reverse();
}
let mut caret = self.clone();
let parent = self.get_parent_at_caret();
let mut nodes_to_remove: Vec<NodeRef> = Vec::new();
let mut remove_caret = caret.get_adjacent_caret();
while let Some(rc) = remove_caret.filter(|_| nodes_to_remove.len() < delete_count) {
crate::lexical_utils::get_writable(rc.origin.get_key());
if !nodes_to_remove.contains(&rc.origin) {
nodes_to_remove.push(rc.origin.clone());
}
remove_caret = rc.get_adjacent_caret();
}
for node in &node_iter {
if !nodes_to_remove.is_empty() {
let Some(target) = caret.get_node_at_caret() else {
let keys: Vec<&str> = nodes_to_remove.iter().map(NodeRef::get_key).collect();
return Err(LexicalError::new(format!(
"NodeCaret.splice: Underflow of expected nodesToRemove during splice (keys: {})",
keys.join(" ")
)));
};
nodes_to_remove.retain(|n| n != &target && n != node);
if &target == node || &caret.origin == node {
} else {
if node
.get_parent()
.is_some_and(|p| Some(&p) == parent.as_ref())
{
node.remove(false)?;
}
target.replace(node, false)?;
}
} else {
caret.insert(node)?;
}
caret = get_sibling_caret(node, self.direction);
}
for node in &nodes_to_remove {
node.remove(false)?;
}
Ok(())
}
}
fn new_child_caret(origin: &NodeRef, direction: CaretDirection) -> ChildCaret {
PointCaret {
origin: origin.clone(),
direction,
kind: CaretKind::Child,
}
}
pub fn get_sibling_caret(origin: &NodeRef, direction: CaretDirection) -> SiblingCaret {
PointCaret {
origin: origin.clone(),
direction,
kind: CaretKind::Sibling,
}
}
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub enum TextOffset {
Offset(usize),
End(CaretDirection),
}
impl From<usize> for TextOffset {
fn from(offset: usize) -> Self {
TextOffset::Offset(offset)
}
}
impl From<CaretDirection> for TextOffset {
fn from(direction: CaretDirection) -> Self {
TextOffset::End(direction)
}
}
pub fn get_text_point_caret(
origin: &NodeRef,
direction: CaretDirection,
offset: impl Into<TextOffset>,
) -> Result<TextPointCaret, LexicalError> {
Ok(PointCaret {
origin: origin.clone(),
direction,
kind: CaretKind::Text {
offset: get_text_node_offset(origin, offset.into(), false)?,
},
})
}
pub(crate) fn get_text_point_caret_at_end(
origin: &NodeRef,
direction: CaretDirection,
end: CaretDirection,
) -> TextPointCaret {
get_text_point_caret(origin, direction, end).expect("an end is always a valid offset")
}
pub fn get_text_node_offset(
origin: &NodeRef,
offset: TextOffset,
clamp: bool,
) -> Result<usize, LexicalError> {
let size = origin.get_text_content_size();
let numeric_offset = match offset {
TextOffset::End(CaretDirection::Next) => size,
TextOffset::End(CaretDirection::Previous) => 0,
TextOffset::Offset(offset) => offset,
};
if numeric_offset > size {
invariant!(
clamp,
"$getTextNodeOffset: invalid offset {numeric_offset} for size {size} at key {}",
origin.get_key()
);
return Ok(size);
}
Ok(numeric_offset)
}
#[derive(Clone, Debug, PartialEq, Eq)]
pub struct TextPointCaretSlice {
pub caret: TextPointCaret,
pub distance: isize,
}
impl TextPointCaretSlice {
fn offset(&self) -> usize {
self.caret.offset().expect("a text point caret")
}
pub fn get_slice_indices(&self) -> (usize, usize) {
let offset = self.offset();
let offset_b = offset.saturating_add_signed(self.distance);
if offset_b < offset {
(offset_b, offset)
} else {
(offset, offset_b)
}
}
pub fn get_text_content(&self) -> String {
let (start, end) = self.get_slice_indices();
utf16::slice(&self.caret.origin.get_text_content(), start, end)
}
pub fn get_text_content_size(&self) -> usize {
self.distance.unsigned_abs()
}
pub fn remove_text_slice(&self) -> Result<TextPointCaret, LexicalError> {
let origin = &self.caret.origin;
let (start, end) = self.get_slice_indices();
let content = origin.get_text_content();
let next = utf16::slice(&content, 0, start) + &utf16::slice_from(&content, end);
origin.set_text_content(&next);
get_text_point_caret(origin, self.caret.direction, start)
}
}
pub fn get_text_point_caret_slice(caret: TextPointCaret, distance: isize) -> TextPointCaretSlice {
debug_assert!(caret.is_text_point_caret());
TextPointCaretSlice { caret, distance }
}
pub fn get_child_caret(origin: &NodeRef, direction: CaretDirection) -> Option<ChildCaret> {
origin
.is_element()
.then(|| new_child_caret(origin, direction))
}
pub fn get_child_caret_or_self(caret: Option<PointCaret>) -> Option<PointCaret> {
caret.map(|c| c.get_child_caret().unwrap_or(c))
}
pub fn get_adjacent_child_caret(caret: Option<&NodeCaret>) -> Option<NodeCaret> {
get_child_caret_or_self(caret?.get_adjacent_caret())
}
#[derive(Clone, Debug, PartialEq, Eq)]
pub struct CaretRange {
pub anchor: PointCaret,
pub focus: PointCaret,
direction: CaretDirection,
}
impl CaretRange {
pub fn direction(&self) -> CaretDirection {
self.direction
}
pub fn get_latest(&self) -> CaretRange {
self.clone()
}
pub fn is_collapsed(&self) -> bool {
self.anchor.is_same_point_caret(&self.focus)
}
pub fn get_text_slices(&self) -> [Option<TextPointCaretSlice>; 2] {
let anchor = self.anchor.get_latest();
let focus = self.focus.get_latest();
if let (Some(anchor_offset), Some(focus_offset)) = (anchor.offset(), focus.offset())
&& anchor.is_same_node_caret(&focus)
{
let distance = focus_offset as isize - anchor_offset as isize;
return [Some(get_text_point_caret_slice(anchor, distance)), None];
}
[
anchor
.is_text_point_caret()
.then(|| get_slice_from_text_point_caret(anchor, false)),
focus
.is_text_point_caret()
.then(|| get_slice_from_text_point_caret(focus, true)),
]
}
pub fn iter_node_carets(&self, root_mode: RootMode) -> impl Iterator<Item = NodeCaret> + use<> {
let anchor = if self.anchor.is_text_point_caret() {
self.anchor.get_sibling_caret()
} else {
self.anchor.get_latest()
};
let focus = self.focus.get_latest();
let is_text_focus = focus.is_text_point_caret();
let step = {
let focus = focus.clone();
move |state: &NodeCaret| -> Option<NodeCaret> {
if state.is_same_node_caret(&focus) {
None
} else {
get_adjacent_child_caret(Some(state))
.or_else(|| state.get_parent_caret(root_mode))
}
}
};
let initial = if anchor.is_same_node_caret(&focus) {
None
} else {
step(&anchor)
};
make_stepwise_iterator(
initial,
move |state: &Option<NodeCaret>| {
state
.as_ref()
.is_some_and(|s| !(is_text_focus && focus.is_same_node_caret(s)))
},
move |state| state.and_then(|s| step(&s)),
|state| state.clone().expect("checked by has_next"),
)
}
pub fn iter(&self) -> impl Iterator<Item = NodeCaret> + use<> {
self.iter_node_carets(RootMode::Root)
}
}
fn get_slice_from_text_point_caret(caret: TextPointCaret, is_focus: bool) -> TextPointCaretSlice {
let direction = caret.direction;
let end = if is_focus {
flip_direction(direction)
} else {
direction
};
let offset_b = get_text_node_offset(&caret.origin, end.into(), false)
.expect("an end is always a valid offset");
let offset = caret.offset().expect("a text point caret");
get_text_point_caret_slice(caret, offset_b as isize - offset as isize)
}
pub fn get_caret_in_direction(
caret: &PointCaret,
direction: CaretDirection,
) -> Result<PointCaret, LexicalError> {
if caret.direction == direction {
Ok(caret.clone())
} else {
caret.get_flipped()
}
}
pub fn extend_caret_to_range(anchor: &PointCaret) -> Result<CaretRange, LexicalError> {
let root_caret = new_child_caret(&get_root(), flip_direction(anchor.direction));
get_caret_range(
anchor.clone(),
get_caret_in_direction(&root_caret, anchor.direction)?,
)
}
pub fn get_collapsed_caret_range(anchor: PointCaret) -> CaretRange {
CaretRange {
anchor: anchor.clone(),
focus: anchor.clone(),
direction: anchor.direction,
}
}
pub fn get_caret_range(anchor: PointCaret, focus: PointCaret) -> Result<CaretRange, LexicalError> {
invariant!(
anchor.direction == focus.direction,
"$getCaretRange: anchor and focus must be in the same direction"
);
let direction = anchor.direction;
Ok(CaretRange {
anchor,
focus,
direction,
})
}
pub fn make_stepwise_iterator<State, Value>(
initial: State,
has_next: impl FnMut(&State) -> bool,
step: impl FnMut(State) -> State,
map: impl FnMut(&State) -> Value,
) -> impl Iterator<Item = Value> {
StepwiseIterator {
state: Some(initial),
has_next,
step,
map,
}
}
struct StepwiseIterator<State, H, S, M> {
state: Option<State>,
has_next: H,
step: S,
map: M,
}
impl<State, Value, H, S, M> Iterator for StepwiseIterator<State, H, S, M>
where
H: FnMut(&State) -> bool,
S: FnMut(State) -> State,
M: FnMut(&State) -> Value,
{
type Item = Value;
fn next(&mut self) -> Option<Value> {
let state = self.state.as_ref()?;
if !(self.has_next)(state) {
return None;
}
let value = (self.map)(state);
let state = self.state.take().expect("checked above");
self.state = Some((self.step)(state));
Some(value)
}
}
pub fn compare_point_caret_next(a: &PointCaret, b: &PointCaret) -> Result<Ordering, LexicalError> {
let compare = get_common_ancestor(&a.origin, &b.origin);
let Some(compare) = compare else {
return Err(LexicalError::new(format!(
"$comparePointCaretNext: a (key {}) and b (key {}) do not have a common ancestor",
a.origin.get_key(),
b.origin.get_key()
)));
};
Ok(match compare {
CommonAncestorResult::Same { .. } => compare_same_origin_carets(a, b),
CommonAncestorResult::Ancestor { .. } => {
if a.is_child_caret() {
Ordering::Less
} else {
Ordering::Greater
}
}
CommonAncestorResult::Descendant { .. } => {
if b.is_child_caret() {
Ordering::Greater
} else {
Ordering::Less
}
}
CommonAncestorResult::Branch { a, b, .. } => {
get_common_ancestor_result_branch_order(&a, &b)
}
})
}
fn compare_same_origin_carets(a: &PointCaret, b: &PointCaret) -> Ordering {
match (a.kind, b.kind) {
(CaretKind::Text { offset: x }, CaretKind::Text { offset: y }) => x.cmp(&y),
(x, y) if x == y => Ordering::Equal,
(CaretKind::Text { .. }, _) => Ordering::Less,
(_, CaretKind::Text { .. }) => Ordering::Greater,
(CaretKind::Child, _) => Ordering::Less,
_ => Ordering::Greater,
}
}
pub fn get_common_ancestor_result_branch_order(a: &NodeRef, b: &NodeRef) -> Ordering {
let mut na = Some(a.clone());
let mut nb = Some(b.clone());
while let (Some(x), Some(y)) = (&na, &nb) {
if x == b {
return Ordering::Less;
} else if y == a {
return Ordering::Greater;
}
na = x.get_next_sibling();
nb = y.get_next_sibling();
}
if na.is_none() {
Ordering::Greater
} else {
Ordering::Less
}
}
#[derive(Clone, Debug, PartialEq, Eq)]
pub enum CommonAncestorResult {
Same { common_ancestor: NodeRef },
Ancestor { common_ancestor: NodeRef },
Descendant { common_ancestor: NodeRef },
Branch {
common_ancestor: NodeRef,
a: NodeRef,
b: NodeRef,
},
}
impl CommonAncestorResult {
pub fn common_ancestor(&self) -> &NodeRef {
match self {
CommonAncestorResult::Same { common_ancestor }
| CommonAncestorResult::Ancestor { common_ancestor }
| CommonAncestorResult::Descendant { common_ancestor }
| CommonAncestorResult::Branch {
common_ancestor, ..
} => common_ancestor,
}
}
}
fn initial_element_tuple(node: &NodeRef) -> (Option<NodeRef>, Option<NodeRef>) {
if node.is_element() {
(Some(node.clone()), None)
} else {
(node.get_parent(), Some(node.clone()))
}
}
pub fn get_common_ancestor(a: &NodeRef, b: &NodeRef) -> Option<CommonAncestorResult> {
if a == b {
return Some(CommonAncestorResult::Same {
common_ancestor: a.clone(),
});
}
let mut a_map: HashMap<NodeKey, Option<NodeRef>> = HashMap::new();
let (mut parent, mut child) = initial_element_tuple(a);
while let Some(p) = parent {
parent = p.get_parent();
a_map.insert(p.get_key().to_owned(), child);
child = Some(p);
}
let (mut parent, mut child) = initial_element_tuple(b);
while let Some(p) = parent {
if let Some(a_child) = a_map.get(p.get_key()) {
return Some(match (a_child, child) {
(None, _) => {
assert!(&p == a, "$originComparison: ancestor logic error");
CommonAncestorResult::Ancestor { common_ancestor: p }
}
(Some(_), None) => {
assert!(&p == b, "$originComparison: descendant logic error");
CommonAncestorResult::Descendant { common_ancestor: p }
}
(Some(a_child), Some(child)) => {
assert!(
(a_child.is_element() || a_child == a)
&& (child.is_element() || &child == b)
&& a_child.get_parent().as_ref() == Some(&p)
&& child.get_parent().as_ref() == Some(&p),
"$originComparison: branch logic error"
);
CommonAncestorResult::Branch {
common_ancestor: p,
a: a_child.clone(),
b: child,
}
}
});
}
parent = p.get_parent();
child = Some(p);
}
None
}
#[derive(Clone, Debug, PartialEq, Eq)]
pub enum CommonAncestorAcrossSlotsResult {
Same {
common_ancestor: NodeRef,
},
Ancestor {
common_ancestor: NodeRef,
b: NodeRef,
},
Descendant {
common_ancestor: NodeRef,
a: NodeRef,
},
Branch {
common_ancestor: NodeRef,
a: NodeRef,
b: NodeRef,
},
}
fn get_parent_across_slots(node: &NodeRef) -> Option<NodeRef> {
node.get_parent()
.or_else(|| crate::slot::get_slot_host(node))
}
pub fn get_common_ancestor_across_slots(
a: &NodeRef,
b: &NodeRef,
) -> Option<CommonAncestorAcrossSlotsResult> {
let mut a_path: HashMap<NodeKey, Option<NodeRef>> = HashMap::new();
let mut child: Option<NodeRef> = None;
let mut node = Some(a.clone());
while let Some(n) = node {
a_path.insert(n.get_key().to_owned(), child);
node = get_parent_across_slots(&n);
child = Some(n);
}
let mut child: Option<NodeRef> = None;
let mut node = Some(b.clone());
while let Some(n) = node {
if let Some(a_child) = a_path.get(n.get_key()) {
let common_ancestor = n.clone();
return Some(match (a_child.clone(), child) {
(None, None) => CommonAncestorAcrossSlotsResult::Same { common_ancestor },
(None, Some(b)) => CommonAncestorAcrossSlotsResult::Ancestor { common_ancestor, b },
(Some(a), None) => {
CommonAncestorAcrossSlotsResult::Descendant { common_ancestor, a }
}
(Some(a), Some(b)) => CommonAncestorAcrossSlotsResult::Branch {
common_ancestor,
a,
b,
},
});
}
node = get_parent_across_slots(&n);
child = Some(n);
}
None
}
pub fn compare_point_caret_next_across_slots(a: &PointCaret, b: &PointCaret) -> Option<Ordering> {
use crate::slot::get_slot_host_key;
Some(
match get_common_ancestor_across_slots(&a.origin, &b.origin)? {
CommonAncestorAcrossSlotsResult::Same { .. } => compare_same_origin_carets(a, b),
CommonAncestorAcrossSlotsResult::Ancestor { b: node_b, .. } => {
if a.is_child_caret() && get_slot_host_key(&node_b).is_none() {
Ordering::Less
} else {
Ordering::Greater
}
}
CommonAncestorAcrossSlotsResult::Descendant { a: node_a, .. } => {
if b.is_child_caret() && get_slot_host_key(&node_a).is_none() {
Ordering::Greater
} else {
Ordering::Less
}
}
CommonAncestorAcrossSlotsResult::Branch {
common_ancestor,
a: node_a,
b: node_b,
} => {
let a_slot = get_slot_host_key(&node_a).is_some();
let b_slot = get_slot_host_key(&node_b).is_some();
if a_slot && b_slot {
for key in crate::slot::get_slot_map(&common_ancestor).values() {
if key == node_a.get_key() || key == node_b.get_key() {
return Some(if key == node_a.get_key() {
Ordering::Less
} else {
Ordering::Greater
});
}
}
}
if a_slot {
Ordering::Less
} else if b_slot {
Ordering::Greater
} else if node_a.is_before(&node_b) {
Ordering::Less
} else {
Ordering::Greater
}
}
},
)
}