use std::cmp::Ordering;
use std::collections::HashMap;
use std::sync::{Arc, Mutex, Weak};
use crate::document::BoundingRect;
use crate::{BaseDocument, NodeData, NodeId, NodeTree};
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub struct RangeBoundary {
pub node: NodeId,
pub offset: usize,
}
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub struct RangeBounds {
pub start: RangeBoundary,
pub end: RangeBoundary,
}
impl RangeBounds {
pub fn collapsed(self) -> bool {
self.start == self.end
}
}
#[derive(Clone, Debug)]
pub struct LiveRange(pub(crate) Arc<Mutex<RangeBounds>>);
impl LiveRange {
pub fn bounds(&self) -> RangeBounds {
*self.0.lock().unwrap()
}
pub fn set_bounds(&self, bounds: RangeBounds) {
*self.0.lock().unwrap() = bounds;
}
pub fn same_range(&self, other: &Self) -> bool {
Arc::ptr_eq(&self.0, &other.0)
}
}
#[derive(Clone, Debug)]
pub enum RangeContent {
Full(NodeId),
Partial(NodeId, Vec<RangeContent>),
Data(NodeId, usize, usize),
}
pub fn utf16_slice(value: &str, start: usize, end: usize) -> String {
let units: Vec<u16> = value
.encode_utf16()
.skip(start)
.take(end.saturating_sub(start))
.collect();
String::from_utf16_lossy(&units)
}
fn contains(nodes: &NodeTree, ancestor: NodeId, mut descendant: NodeId) -> bool {
loop {
if ancestor == descendant {
return true;
}
let Some(parent) = nodes.get(descendant).and_then(|node| node.parent) else {
return false;
};
descendant = parent;
}
}
impl BaseDocument {
pub fn create_live_range(&mut self, bounds: RangeBounds) -> LiveRange {
self.live_ranges.retain(|range| range.strong_count() != 0);
let range = LiveRange(Arc::new(Mutex::new(bounds)));
self.live_ranges.push(Arc::downgrade(&range.0));
range
}
pub fn range_character_data(&self, id: NodeId) -> Option<&str> {
match &self.get_node(id)?.data {
NodeData::Text(text) => Some(&text.content),
NodeData::Comment { contents } => Some(contents),
_ => None,
}
}
pub fn range_node_length(&self, id: NodeId) -> Option<usize> {
let node = self.get_node(id)?;
Some(match self.range_character_data(id) {
Some(text) => text.encode_utf16().count(),
None => node.children.len(),
})
}
pub fn range_contains(&self, ancestor: NodeId, descendant: NodeId) -> bool {
contains(&self.nodes, ancestor, descendant)
}
fn range_path(&self, mut id: NodeId) -> Vec<NodeId> {
let mut path = vec![id];
while let Some(parent) = self.get_node(id).and_then(|node| node.parent) {
path.push(parent);
id = parent;
}
path.reverse();
path
}
pub fn range_root(&self, id: NodeId) -> NodeId {
self.range_path(id)[0]
}
pub fn range_common_ancestor(&self, bounds: RangeBounds) -> Option<NodeId> {
self.range_path(bounds.start.node)
.iter()
.zip(self.range_path(bounds.end.node))
.take_while(|(left, right)| **left == *right)
.map(|(left, _)| *left)
.last()
}
pub fn compare_range_boundaries(
&self,
left: RangeBoundary,
right: RangeBoundary,
) -> Option<Ordering> {
if left.node == right.node {
return Some(left.offset.cmp(&right.offset));
}
let a = self.range_path(left.node);
let b = self.range_path(right.node);
if a.first() != b.first() {
return None;
}
let common = a.iter().zip(&b).take_while(|(a, b)| a == b).count();
let parent = self.get_node(a[common - 1])?;
if common == a.len() {
let index = parent.index_of_child(b[common])?;
return Some(if index < left.offset {
Ordering::Greater
} else {
Ordering::Less
});
}
if common == b.len() {
let index = parent.index_of_child(a[common])?;
return Some(if index < right.offset {
Ordering::Less
} else {
Ordering::Greater
});
}
Some(
parent
.index_of_child(a[common])?
.cmp(&parent.index_of_child(b[common])?),
)
}
fn update_live_ranges(&mut self, mut update: impl FnMut(&mut RangeBoundary)) {
self.live_ranges.retain(|weak| {
let Some(range) = weak.upgrade() else {
return false;
};
let mut bounds = range.lock().unwrap();
update(&mut bounds.start);
update(&mut bounds.end);
true
});
}
pub(crate) fn range_remove_node(&mut self, id: NodeId) {
if self.live_ranges.is_empty() {
return;
}
let Some(parent) = self.get_node(id).and_then(|node| node.parent) else {
return;
};
let Some(index) = self
.get_node(parent)
.and_then(|node| node.index_of_child(id))
else {
return;
};
let nodes = &self.nodes;
self.live_ranges.retain(|weak| {
let Some(range) = weak.upgrade() else {
return false;
};
let mut guard = range.lock().unwrap();
let bounds = &mut *guard;
for point in [&mut bounds.start, &mut bounds.end] {
if contains(nodes, id, point.node) {
*point = RangeBoundary {
node: parent,
offset: index,
};
} else if point.node == parent && point.offset > index {
point.offset -= 1;
}
}
true
});
}
pub(crate) fn range_insert_nodes(&mut self, parent: NodeId, index: usize, count: usize) {
if count == 0 || self.live_ranges.is_empty() {
return;
}
self.update_live_ranges(|point| {
if point.node == parent && point.offset > index {
point.offset += count;
}
});
}
pub(crate) fn range_replace_data(
&mut self,
id: NodeId,
offset: usize,
removed: usize,
added: usize,
) {
if self.live_ranges.is_empty() {
return;
}
self.update_live_ranges(|point| {
if point.node != id {
return;
}
if point.offset > offset && point.offset <= offset + removed {
point.offset = offset;
} else if point.offset > offset + removed {
point.offset = point.offset - removed + added;
}
});
}
pub(crate) fn range_split_text(
&mut self,
old: NodeId,
new: NodeId,
offset: usize,
parent_position: Option<(NodeId, usize)>,
) {
self.update_live_ranges(|point| {
if point.node == old && point.offset > offset {
point.node = new;
point.offset -= offset;
} else if let Some((parent, index)) = parent_position
&& point.node == parent
&& point.offset == index + 1
{
point.offset += 1;
}
});
}
pub fn range_merge_text(&mut self, keeper: NodeId, removed: NodeId, prefix: usize) {
let position = self.get_node(removed).and_then(|node| {
let parent = node.parent?;
Some((parent, self.get_node(parent)?.index_of_child(removed)?))
});
self.update_live_ranges(|point| {
if point.node == removed {
point.node = keeper;
point.offset += prefix;
} else if let Some((parent, index)) = position
&& point.node == parent
&& point.offset == index
{
*point = RangeBoundary {
node: keeper,
offset: prefix,
};
}
});
}
pub fn range_contents(&self, bounds: RangeBounds) -> Vec<RangeContent> {
if bounds.collapsed() {
return Vec::new();
}
let Some(common) = self.range_common_ancestor(bounds) else {
return Vec::new();
};
if self.range_character_data(common).is_some() {
return vec![RangeContent::Data(
common,
bounds.start.offset,
bounds.end.offset,
)];
}
self.get_node(common)
.into_iter()
.flat_map(|node| node.children.iter().copied())
.filter_map(|id| self.range_content(id, bounds))
.collect()
}
fn range_content(&self, id: NodeId, bounds: RangeBounds) -> Option<RangeContent> {
let node = self.get_node(id)?;
let parent = node.parent?;
let index = self.get_node(parent)?.index_of_child(id)?;
let before = RangeBoundary {
node: parent,
offset: index,
};
let after = RangeBoundary {
node: parent,
offset: index + 1,
};
if self.compare_range_boundaries(bounds.end, before)? != Ordering::Greater
|| self.compare_range_boundaries(bounds.start, after)? != Ordering::Less
{
return None;
}
if self.compare_range_boundaries(bounds.start, before)? != Ordering::Greater
&& self.compare_range_boundaries(bounds.end, after)? != Ordering::Less
{
return Some(RangeContent::Full(id));
}
if let Some(text) = self.range_character_data(id) {
let start = if bounds.start.node == id {
bounds.start.offset
} else {
0
};
let end = if bounds.end.node == id {
bounds.end.offset
} else {
text.encode_utf16().count()
};
return Some(RangeContent::Data(id, start, end));
}
Some(RangeContent::Partial(
id,
node.children
.iter()
.filter_map(|id| self.range_content(*id, bounds))
.collect(),
))
}
pub fn range_collapse_after_deletion(&self, bounds: RangeBounds) -> RangeBoundary {
if self.range_contains(bounds.start.node, bounds.end.node) {
return bounds.start;
}
let common = self
.range_common_ancestor(bounds)
.expect("range has one root");
let mut child = bounds.start.node;
while self.get_node(child).and_then(|node| node.parent) != Some(common) {
child = self
.get_node(child)
.and_then(|node| node.parent)
.expect("range ancestor");
}
RangeBoundary {
node: common,
offset: self
.get_node(common)
.unwrap()
.index_of_child(child)
.unwrap()
+ 1,
}
}
pub fn range_text_parts(&self, bounds: RangeBounds) -> Vec<(NodeId, usize, usize)> {
fn append(
doc: &BaseDocument,
content: &RangeContent,
result: &mut Vec<(NodeId, usize, usize)>,
) {
match content {
RangeContent::Data(id, start, end) => {
if doc.get_node(*id).is_some_and(|node| node.is_text_node()) {
result.push((*id, *start, *end));
}
}
RangeContent::Partial(_, children) => {
for child in children {
append(doc, child, result);
}
}
RangeContent::Full(id) => {
let mut stack = vec![*id];
while let Some(id) = stack.pop() {
let Some(node) = doc.get_node(id) else {
continue;
};
if let NodeData::Text(text) = &node.data {
result.push((id, 0, text.content.encode_utf16().count()));
} else {
stack.extend(node.children.iter().rev().copied());
}
}
}
}
}
let mut result = Vec::new();
for content in self.range_contents(bounds) {
append(self, &content, &mut result);
}
result
}
pub fn range_string(&self, bounds: RangeBounds) -> String {
let mut result = String::new();
for (id, start, end) in self.range_text_parts(bounds) {
if let Some(text) = self.range_character_data(id) {
result.push_str(&utf16_slice(text, start, end));
}
}
result
}
fn range_layout_extents(&self, root: NodeId) -> HashMap<NodeId, (usize, usize)> {
use parley::PositionedLayoutItem;
let mut result: HashMap<NodeId, (usize, usize)> = HashMap::new();
let Some(inline) = self
.get_node(root)
.and_then(|node| node.element_data())
.and_then(|element| element.inline_layout_data.as_ref())
else {
return result;
};
for line in inline.layout.lines() {
for item in line.items() {
if let PositionedLayoutItem::GlyphRun(run) = item
&& let Some(id) = run.style().brush.text_node
{
let range = run.run().text_range();
result
.entry(id)
.and_modify(|(start, end)| {
*start = (*start).min(range.start);
*end = (*end).max(range.end);
})
.or_insert((range.start, range.end));
}
}
}
result
}
pub fn range_layout_ranges(&self, bounds: RangeBounds) -> Vec<(NodeId, usize, usize)> {
let mut extents = HashMap::new();
let mut result: Vec<(NodeId, usize, usize)> = Vec::new();
for (id, start, end) in self.range_text_parts(bounds) {
let Some(root) = self
.get_node(id)
.filter(|node| node.flags.is_in_document())
.and_then(|node| node.inline_root_ancestor())
.map(|node| node.id)
else {
continue;
};
let map = extents
.entry(root)
.or_insert_with(|| self.range_layout_extents(root));
let Some(&(base, limit)) = map.get(&id) else {
continue;
};
let Some(text) = self.range_character_data(id) else {
continue;
};
let start = (base + utf16_slice(text, 0, start).len()).min(limit);
let end = (base + utf16_slice(text, 0, end).len()).min(limit);
if start == end {
continue;
}
if let Some((last_root, _, last_end)) = result.last_mut()
&& *last_root == root
&& *last_end == start
{
*last_end = end;
} else {
result.push((root, start, end));
}
}
result
}
pub fn range_boundary_from_layout(
&self,
root: NodeId,
offset: usize,
end_boundary: bool,
) -> Option<RangeBoundary> {
let extents = self.range_layout_extents(root);
let mut candidates: Vec<_> = extents.into_iter().collect();
candidates.sort_by_key(|(_, (start, _))| *start);
for (id, (start, end)) in candidates {
let matches = if end_boundary {
offset > start && offset <= end
} else {
offset >= start && offset < end
};
if matches {
let text = self.range_character_data(id)?;
let mut bytes = offset.saturating_sub(start).min(text.len());
while !text.is_char_boundary(bytes) {
bytes -= 1;
}
return Some(RangeBoundary {
node: id,
offset: text[..bytes].encode_utf16().count(),
});
}
}
None
}
pub fn range_client_rects(&self, bounds: RangeBounds) -> Vec<crate::kurbo::Rect> {
use parley::{Affinity, Cursor, Selection};
fn element_rects(
doc: &BaseDocument,
content: &RangeContent,
result: &mut Vec<crate::kurbo::Rect>,
) {
match content {
RangeContent::Full(id)
if doc.get_node(*id).is_some_and(|node| node.is_element()) =>
{
result.extend(doc.node_client_rects(*id).into_iter().map(|rect| {
crate::kurbo::Rect::new(
rect.x,
rect.y,
rect.x + rect.width,
rect.y + rect.height,
)
}));
}
RangeContent::Partial(_, children) => {
for child in children {
element_rects(doc, child, result);
}
}
_ => {}
}
}
let mut result = Vec::new();
for content in self.range_contents(bounds) {
element_rects(self, &content, &mut result);
}
for (root_id, start, end) in self.range_layout_ranges(bounds) {
let Some(root) = self.get_node(root_id) else {
continue;
};
let Some(inline) = root
.element_data()
.and_then(|element| element.inline_layout_data.as_ref())
else {
continue;
};
let layout = &inline.layout;
let scale = layout.scale() as f64;
let box_layout = root.final_layout();
let position = root.absolute_position(0.0, 0.0);
let x = position.x as f64 + (box_layout.padding.left + box_layout.border.left) as f64
- self.viewport_scroll.x;
let y = position.y as f64 + (box_layout.padding.top + box_layout.border.top) as f64
- self.viewport_scroll.y;
let selection = Selection::new(
Cursor::from_byte_index(layout, start, Affinity::Downstream),
Cursor::from_byte_index(layout, end, Affinity::Downstream),
);
selection.geometry_with(layout, |rect, _| {
let rect = self.transformed_client_rect(
root_id,
BoundingRect {
x: x + rect.x0 / scale,
y: y + rect.y0 / scale,
width: (rect.x1 - rect.x0) / scale,
height: (rect.y1 - rect.y0) / scale,
},
);
result.push(crate::kurbo::Rect::new(
rect.x,
rect.y,
rect.x + rect.width,
rect.y + rect.height,
));
});
}
result
}
}
pub(crate) type WeakRange = Weak<Mutex<RangeBounds>>;