Vakyartha documentation

1//! L1 editing: locate elements by byte span and splice replacements into
2//! the original bytes (O1). Everything outside an edited span stays
3//! byte-identical, so markup Vak does not model survives an edit.
4
5use std::ops::Range;
6
7use quick_xml::events::Event;
8
9use crate::xml::{Element, local_name};
10use crate::{Error, Limits};
11
12/// One element with the byte spans of its tags.
13#[derive(Debug, Clone, PartialEq, Eq)]
14pub struct Node {
15 pub element: Element,
16 /// From `<` of the start tag to after `>` of the end tag.
17 pub span: Range<usize>,
18 /// Between the start tag and the end tag; empty for `<x/>`.
19 pub inner: Range<usize>,
20 pub parent: Option<usize>,
21 pub children: Vec<usize>,
22 /// Inside an `mc:AlternateContent` branch a reader skips (a later
23 /// `Choice`, or the `Fallback` after a taken one). Anchors never count
24 /// skipped nodes, matching [`crate::xml::walk`].
25 pub skipped: bool,
26}
27
28impl Node {
29 pub fn local(&self) -> &str {
30 self.element.local()
31 }
32
33 pub fn is_empty_element(&self) -> bool {
34 self.inner.is_empty() && self.inner.start == self.span.end
35 }
36}
37
38/// Every element of a part in document order, with the same `DOCTYPE`,
39/// depth and attribute bounds as a read.
40#[derive(Debug, Clone)]
41pub struct Tree {
42 pub nodes: Vec<Node>,
43}
44
45impl Tree {
46 pub fn parse(bytes: &[u8], part: &str, limits: &Limits) -> Result<Self, Error> {
47 if bytes.starts_with(&[0xFF, 0xFE]) || bytes.starts_with(&[0xFE, 0xFF]) {
48 return Err(xml_error(part, "UTF-16 parts are not supported"));
49 }
50 let mut reader = quick_xml::Reader::from_reader(bytes);
51 reader.config_mut().check_end_names = true;
52 let mut buffer = Vec::new();
53 let mut nodes: Vec<Node> = Vec::new();
54 let mut open: Vec<usize> = Vec::new();
55 let mut alternates: Vec<bool> = Vec::new();
56 let mut skipping: Option<usize> = None;
57 loop {
58 let before = position(&reader);
59 let event = reader
60 .read_event_into(&mut buffer)
61 .map_err(|error| xml_error(part, &error.to_string()))?;
62 let after = position(&reader);
63 match event {
64 Event::Start(start) | Event::Empty(start) => {
65 let empty = matches!(
66 bytes
67 .get(before..after)
68 .and_then(|tag| tag.get(tag.len().saturating_sub(2)..)),
69 Some(b"/>")
70 );
71 if open.len() + 1 > limits.max_xml_depth {
72 return Err(Error::TooDeep(part.to_string()));
73 }
74 let element = crate::xml::element_of(&start, part, limits)?;
75 let parent = open.last().copied();
76 let skipped = skipping.is_some() || {
77 let skip = skip_alternate(&element, &mut alternates);
78 if skip {
79 skipping = Some(open.len() + 1);
80 }
81 skip
82 };
83 if !skipped && element.local() == "AlternateContent" && !empty {
84 alternates.push(false);
85 }
86 let index = nodes.len();
87 nodes.push(Node {
88 element,
89 span: before..after,
90 inner: after..after,
91 parent,
92 children: Vec::new(),
93 skipped,
94 });
95 if let Some(parent) = parent {
96 nodes[parent].children.push(index);
97 }
98 if empty {
99 if skipping == Some(open.len() + 1) {
100 skipping = None;
101 }
102 } else {
103 open.push(index);
104 }
105 }
106 Event::End(_) => {
107 let Some(index) = open.pop() else {
108 return Err(xml_error(part, "unbalanced end tag"));
109 };
110 let node = &mut nodes[index];
111 node.inner = node.inner.start..before;
112 node.span = node.span.start..after;
113 if skipping == Some(open.len() + 1) {
114 skipping = None;
115 } else if !node.skipped && node.element.local() == "AlternateContent" {
116 alternates.pop();
117 }
118 }
119 Event::DocType(_) => return Err(Error::DocType(part.to_string())),
120 Event::Eof => {
121 if nodes.is_empty() {
122 return Err(xml_error(part, "no root element"));
123 }
124 if !open.is_empty() {
125 return Err(xml_error(part, "unexpected end of document"));
126 }
127 return Ok(Self { nodes });
128 }
129 _ => {}
130 }
131 buffer.clear();
132 }
133 }
134
135 pub fn root(&self) -> &Node {
136 &self.nodes[0]
137 }
138
139 /// Visible (not skipped) descendants of `index` with local name
140 /// `local`, in document order.
141 pub fn descendants<'a>(
142 &'a self,
143 index: usize,
144 local: &'a str,
145 ) -> impl Iterator<Item = usize> + 'a {
146 let span = self.nodes[index].span.clone();
147 (index + 1..self.nodes.len())
148 .take_while(move |candidate| self.nodes[*candidate].span.start < span.end)
149 .filter(move |candidate| {
150 let node = &self.nodes[*candidate];
151 !node.skipped && node.local() == local
152 })
153 }
154
155 /// Visible direct children of `index` with local name `local`.
156 pub fn children<'a>(
157 &'a self,
158 index: usize,
159 local: &'a str,
160 ) -> impl Iterator<Item = usize> + 'a {
161 self.nodes[index]
162 .children
163 .iter()
164 .copied()
165 .filter(move |child| {
166 let node = &self.nodes[*child];
167 !node.skipped && node.local() == local
168 })
169 }
170
171 /// Prefix (with its colon, or empty for a default namespace) the root
172 /// binds to `namespace`, if any.
173 pub fn prefix_for(&self, namespace: &str) -> Option<String> {
174 self.root()
175 .element
176 .attributes
177 .iter()
178 .find_map(|(key, value)| {
179 if value != namespace {
180 return None;
181 }
182 if key == "xmlns" {
183 Some(String::new())
184 } else {
185 key.strip_prefix("xmlns:")
186 .map(|prefix| format!("{prefix}:"))
187 }
188 })
189 }
190}
191
192fn position(reader: &quick_xml::Reader<&[u8]>) -> usize {
193 usize::try_from(reader.buffer_position()).unwrap_or(usize::MAX)
194}
195
196fn skip_alternate(element: &Element, alternates: &mut [bool]) -> bool {
197 let Some(taken) = alternates.last_mut() else {
198 return false;
199 };
200 match element.local() {
201 "Choice" if *taken => true,
202 "Choice" => {
203 *taken = true;
204 false
205 }
206 "Fallback" => *taken,
207 _ => false,
208 }
209}
210
211/// Byte-range replacements over one part. Ranges must not overlap; an
212/// insertion is an empty range.
213#[derive(Debug, Default, Clone)]
214pub struct Splice {
215 edits: Vec<(Range<usize>, Vec<u8>)>,
216}
217
218impl Splice {
219 pub fn replace(&mut self, range: Range<usize>, bytes: impl Into<Vec<u8>>) {
220 self.edits.push((range, bytes.into()));
221 }
222
223 pub fn insert(&mut self, at: usize, bytes: impl Into<Vec<u8>>) {
224 self.edits.push((at..at, bytes.into()));
225 }
226
227 pub fn is_empty(&self) -> bool {
228 self.edits.is_empty()
229 }
230
231 pub fn apply(mut self, source: &[u8], part: &str) -> Result<Vec<u8>, Error> {
232 self.edits
233 .sort_by_key(|(range, _)| (range.start, range.end));
234 let mut out = Vec::with_capacity(source.len());
235 let mut cursor = 0;
236 for (range, bytes) in &self.edits {
237 if range.start < cursor || range.end > source.len() || range.start > range.end {
238 return Err(xml_error(part, "overlapping or out-of-range edits"));
239 }
240 out.extend_from_slice(&source[cursor..range.start]);
241 out.extend_from_slice(bytes);
242 cursor = range.end;
243 }
244 out.extend_from_slice(&source[cursor..]);
245 Ok(out)
246 }
247}
248
249/// Escapes text content.
250pub fn escape_text(text: &str) -> String {
251 text.replace('&', "&")
252 .replace('<', "<")
253 .replace('>', ">")
254}
255
256/// Escapes an attribute value written in double quotes.
257pub fn escape_attr(text: &str) -> String {
258 escape_text(text).replace('"', """)
259}
260
261/// Rebuilds a start tag from an element, with `attributes` replacing the
262/// element's own. Used only for tags Vak changes; untouched tags are never
263/// rewritten.
264pub fn start_tag(name: &str, attributes: &[(String, String)], empty: bool) -> String {
265 let mut tag = format!("<{name}");
266 for (key, value) in attributes {
267 tag.push_str(&format!(" {key}=\"{}\"", escape_attr(value)));
268 }
269 tag.push_str(if empty { "/>" } else { ">" });
270 tag
271}
272
273pub fn has_local(node: &Node, local: &str) -> bool {
274 local_name(&node.element.name) == local
275}
276
277fn xml_error(part: &str, message: &str) -> Error {
278 Error::Xml {
279 part: part.to_string(),
280 message: message.to_string(),
281 }
282}
283
284#[cfg(test)]
285#[allow(clippy::unwrap_used, clippy::expect_used)]
286mod tests {
287 use super::*;
288
289 #[test]
290 fn spans_cover_tags_exactly() {
291 let xml = br#"<?xml version="1.0"?><a x="1">hi<c/></a>"#;
292 let tree = Tree::parse(xml, "t", &Limits::default()).unwrap();
293 let text = std::str::from_utf8(xml).unwrap();
294 assert_eq!(
295 &text[tree.nodes[0].span.clone()],
296 r#"<a x="1">hi<c/></a>"#
297 );
298 assert_eq!(&text[tree.nodes[1].span.clone()], "hi");
299 assert_eq!(&text[tree.nodes[1].inner.clone()], "hi");
300 assert_eq!(&text[tree.nodes[2].span.clone()], "<c/>");
301 assert!(tree.nodes[2].is_empty_element());
302 assert_eq!(tree.nodes[0].children, vec![1, 2]);
303 }
304
305 #[test]
306 fn splice_keeps_everything_else_byte_identical() {
307 let xml = b"<a> old\n<c/></a>";
308 let tree = Tree::parse(xml, "t", &Limits::default()).unwrap();
309 let mut splice = Splice::default();
310 splice.replace(tree.nodes[1].inner.clone(), "new");
311 splice.insert(tree.nodes[2].span.end, "<d/>");
312 let out = splice.apply(xml, "t").unwrap();
313 assert_eq!(out, b"<a> new\n<c/><d/></a>");
314 let mut overlapping = Splice::default();
315 overlapping.replace(0..5, "x");
316 overlapping.replace(3..6, "y");
317 assert!(overlapping.apply(xml, "t").is_err());
318 }
319
320 #[test]
321 fn skipped_alternate_branches_are_marked() {
322 let xml = br#"<r xmlns:mc="m"><mc:AlternateContent><mc:Choice></mc:Choice><mc:Fallback></mc:Fallback></mc:AlternateContent></r>"#;
323 let tree = Tree::parse(xml, "t", &Limits::default()).unwrap();
324 let visible: Vec<usize> = tree.descendants(0, "p").collect();
325 assert_eq!(visible.len(), 2, "the fallback copy is not counted");
326 }
327
328 #[test]
329 fn prefixes_are_read_from_the_root() {
330 let xml = br#"<x:doc xmlns:x="urn:w" xmlns="urn:d"/>"#;
331 let tree = Tree::parse(xml, "t", &Limits::default()).unwrap();
332 assert_eq!(tree.prefix_for("urn:w").as_deref(), Some("x:"));
333 assert_eq!(tree.prefix_for("urn:d").as_deref(), Some(""));
334 assert_eq!(tree.prefix_for("urn:none"), None);
335 }
336}
337

1//! L1 editing: locate elements by byte span and splice replacements into
2//! the original bytes (O1). Everything outside an edited span stays
3//! byte-identical, so markup Vak does not model survives an edit.
4
5use std::ops::Range;
6
7use quick_xml::events::Event;
8
9use crate::xml::{Element, local_name};
10use crate::{Error, Limits};
11
12/// One element with the byte spans of its tags.
13#[derive(Debug, Clone, PartialEq, Eq)]
14pub struct Node {
15 pub element: Element,
16 /// From `<` of the start tag to after `>` of the end tag.
17 pub span: Range<usize>,
18 /// Between the start tag and the end tag; empty for `<x/>`.
19 pub inner: Range<usize>,
20 pub parent: Option<usize>,
21 pub children: Vec<usize>,
22 /// Inside an `mc:AlternateContent` branch a reader skips (a later
23 /// `Choice`, or the `Fallback` after a taken one). Anchors never count
24 /// skipped nodes, matching [`crate::xml::walk`].
25 pub skipped: bool,
26}
27
28impl Node {
29 pub fn local(&self) -> &str {
30 self.element.local()
31 }
32
33 pub fn is_empty_element(&self) -> bool {
34 self.inner.is_empty() && self.inner.start == self.span.end
35 }
36}
37
38/// Every element of a part in document order, with the same `DOCTYPE`,
39/// depth and attribute bounds as a read.
40#[derive(Debug, Clone)]
41pub struct Tree {
42 pub nodes: Vec<Node>,
43}
44
45impl Tree {
46 pub fn parse(bytes: &[u8], part: &str, limits: &Limits) -> Result<Self, Error> {
47 if bytes.starts_with(&[0xFF, 0xFE]) || bytes.starts_with(&[0xFE, 0xFF]) {
48 return Err(xml_error(part, "UTF-16 parts are not supported"));
49 }
50 let mut reader = quick_xml::Reader::from_reader(bytes);
51 reader.config_mut().check_end_names = true;
52 let mut buffer = Vec::new();
53 let mut nodes: Vec<Node> = Vec::new();
54 let mut open: Vec<usize> = Vec::new();
55 let mut alternates: Vec<bool> = Vec::new();
56 let mut skipping: Option<usize> = None;
57 loop {
58 let before = position(&reader);
59 let event = reader
60 .read_event_into(&mut buffer)
61 .map_err(|error| xml_error(part, &error.to_string()))?;
62 let after = position(&reader);
63 match event {
64 Event::Start(start) | Event::Empty(start) => {
65 let empty = matches!(
66 bytes
67 .get(before..after)
68 .and_then(|tag| tag.get(tag.len().saturating_sub(2)..)),
69 Some(b"/>")
70 );
71 if open.len() + 1 > limits.max_xml_depth {
72 return Err(Error::TooDeep(part.to_string()));
73 }
74 let element = crate::xml::element_of(&start, part, limits)?;
75 let parent = open.last().copied();
76 let skipped = skipping.is_some() || {
77 let skip = skip_alternate(&element, &mut alternates);
78 if skip {
79 skipping = Some(open.len() + 1);
80 }
81 skip
82 };
83 if !skipped && element.local() == "AlternateContent" && !empty {
84 alternates.push(false);
85 }
86 let index = nodes.len();
87 nodes.push(Node {
88 element,
89 span: before..after,
90 inner: after..after,
91 parent,
92 children: Vec::new(),
93 skipped,
94 });
95 if let Some(parent) = parent {
96 nodes[parent].children.push(index);
97 }
98 if empty {
99 if skipping == Some(open.len() + 1) {
100 skipping = None;
101 }
102 } else {
103 open.push(index);
104 }
105 }
106 Event::End(_) => {
107 let Some(index) = open.pop() else {
108 return Err(xml_error(part, "unbalanced end tag"));
109 };
110 let node = &mut nodes[index];
111 node.inner = node.inner.start..before;
112 node.span = node.span.start..after;
113 if skipping == Some(open.len() + 1) {
114 skipping = None;
115 } else if !node.skipped && node.element.local() == "AlternateContent" {
116 alternates.pop();
117 }
118 }
119 Event::DocType(_) => return Err(Error::DocType(part.to_string())),
120 Event::Eof => {
121 if nodes.is_empty() {
122 return Err(xml_error(part, "no root element"));
123 }
124 if !open.is_empty() {
125 return Err(xml_error(part, "unexpected end of document"));
126 }
127 return Ok(Self { nodes });
128 }
129 _ => {}
130 }
131 buffer.clear();
132 }
133 }
134
135 pub fn root(&self) -> &Node {
136 &self.nodes[0]
137 }
138
139 /// Visible (not skipped) descendants of `index` with local name
140 /// `local`, in document order.
141 pub fn descendants<'a>(
142 &'a self,
143 index: usize,
144 local: &'a str,
145 ) -> impl Iterator<Item = usize> + 'a {
146 let span = self.nodes[index].span.clone();
147 (index + 1..self.nodes.len())
148 .take_while(move |candidate| self.nodes[*candidate].span.start < span.end)
149 .filter(move |candidate| {
150 let node = &self.nodes[*candidate];
151 !node.skipped && node.local() == local
152 })
153 }
154
155 /// Visible direct children of `index` with local name `local`.
156 pub fn children<'a>(
157 &'a self,
158 index: usize,
159 local: &'a str,
160 ) -> impl Iterator<Item = usize> + 'a {
161 self.nodes[index]
162 .children
163 .iter()
164 .copied()
165 .filter(move |child| {
166 let node = &self.nodes[*child];
167 !node.skipped && node.local() == local
168 })
169 }
170
171 /// Prefix (with its colon, or empty for a default namespace) the root
172 /// binds to `namespace`, if any.
173 pub fn prefix_for(&self, namespace: &str) -> Option<String> {
174 self.root()
175 .element
176 .attributes
177 .iter()
178 .find_map(|(key, value)| {
179 if value != namespace {
180 return None;
181 }
182 if key == "xmlns" {
183 Some(String::new())
184 } else {
185 key.strip_prefix("xmlns:")
186 .map(|prefix| format!("{prefix}:"))
187 }
188 })
189 }
190}
191
192fn position(reader: &quick_xml::Reader<&[u8]>) -> usize {
193 usize::try_from(reader.buffer_position()).unwrap_or(usize::MAX)
194}
195
196fn skip_alternate(element: &Element, alternates: &mut [bool]) -> bool {
197 let Some(taken) = alternates.last_mut() else {
198 return false;
199 };
200 match element.local() {
201 "Choice" if *taken => true,
202 "Choice" => {
203 *taken = true;
204 false
205 }
206 "Fallback" => *taken,
207 _ => false,
208 }
209}
210
211/// Byte-range replacements over one part. Ranges must not overlap; an
212/// insertion is an empty range.
213#[derive(Debug, Default, Clone)]
214pub struct Splice {
215 edits: Vec<(Range<usize>, Vec<u8>)>,
216}
217
218impl Splice {
219 pub fn replace(&mut self, range: Range<usize>, bytes: impl Into<Vec<u8>>) {
220 self.edits.push((range, bytes.into()));
221 }
222
223 pub fn insert(&mut self, at: usize, bytes: impl Into<Vec<u8>>) {
224 self.edits.push((at..at, bytes.into()));
225 }
226
227 pub fn is_empty(&self) -> bool {
228 self.edits.is_empty()
229 }
230
231 pub fn apply(mut self, source: &[u8], part: &str) -> Result<Vec<u8>, Error> {
232 self.edits
233 .sort_by_key(|(range, _)| (range.start, range.end));
234 let mut out = Vec::with_capacity(source.len());
235 let mut cursor = 0;
236 for (range, bytes) in &self.edits {
237 if range.start < cursor || range.end > source.len() || range.start > range.end {
238 return Err(xml_error(part, "overlapping or out-of-range edits"));
239 }
240 out.extend_from_slice(&source[cursor..range.start]);
241 out.extend_from_slice(bytes);
242 cursor = range.end;
243 }
244 out.extend_from_slice(&source[cursor..]);
245 Ok(out)
246 }
247}
248
249/// Escapes text content.
250pub fn escape_text(text: &str) -> String {
251 text.replace('&', "&")
252 .replace('<', "<")
253 .replace('>', ">")
254}
255
256/// Escapes an attribute value written in double quotes.
257pub fn escape_attr(text: &str) -> String {
258 escape_text(text).replace('"', """)
259}
260
261/// Rebuilds a start tag from an element, with `attributes` replacing the
262/// element's own. Used only for tags Vak changes; untouched tags are never
263/// rewritten.
264pub fn start_tag(name: &str, attributes: &[(String, String)], empty: bool) -> String {
265 let mut tag = format!("<{name}");
266 for (key, value) in attributes {
267 tag.push_str(&format!(" {key}=\"{}\"", escape_attr(value)));
268 }
269 tag.push_str(if empty { "/>" } else { ">" });
270 tag
271}
272
273pub fn has_local(node: &Node, local: &str) -> bool {
274 local_name(&node.element.name) == local
275}
276
277fn xml_error(part: &str, message: &str) -> Error {
278 Error::Xml {
279 part: part.to_string(),
280 message: message.to_string(),
281 }
282}
283
284#[cfg(test)]
285#[allow(clippy::unwrap_used, clippy::expect_used)]
286mod tests {
287 use super::*;
288
289 #[test]
290 fn spans_cover_tags_exactly() {
291 let xml = br#"<?xml version="1.0"?><a x="1">hi<c/></a>"#;
292 let tree = Tree::parse(xml, "t", &Limits::default()).unwrap();
293 let text = std::str::from_utf8(xml).unwrap();
294 assert_eq!(
295 &text[tree.nodes[0].span.clone()],
296 r#"<a x="1">hi<c/></a>"#
297 );
298 assert_eq!(&text[tree.nodes[1].span.clone()], "hi");
299 assert_eq!(&text[tree.nodes[1].inner.clone()], "hi");
300 assert_eq!(&text[tree.nodes[2].span.clone()], "<c/>");
301 assert!(tree.nodes[2].is_empty_element());
302 assert_eq!(tree.nodes[0].children, vec![1, 2]);
303 }
304
305 #[test]
306 fn splice_keeps_everything_else_byte_identical() {
307 let xml = b"<a> old\n<c/></a>";
308 let tree = Tree::parse(xml, "t", &Limits::default()).unwrap();
309 let mut splice = Splice::default();
310 splice.replace(tree.nodes[1].inner.clone(), "new");
311 splice.insert(tree.nodes[2].span.end, "<d/>");
312 let out = splice.apply(xml, "t").unwrap();
313 assert_eq!(out, b"<a> new\n<c/><d/></a>");
314 let mut overlapping = Splice::default();
315 overlapping.replace(0..5, "x");
316 overlapping.replace(3..6, "y");
317 assert!(overlapping.apply(xml, "t").is_err());
318 }
319
320 #[test]
321 fn skipped_alternate_branches_are_marked() {
322 let xml = br#"<r xmlns:mc="m"><mc:AlternateContent><mc:Choice></mc:Choice><mc:Fallback></mc:Fallback></mc:AlternateContent></r>"#;
323 let tree = Tree::parse(xml, "t", &Limits::default()).unwrap();
324 let visible: Vec<usize> = tree.descendants(0, "p").collect();
325 assert_eq!(visible.len(), 2, "the fallback copy is not counted");
326 }
327
328 #[test]
329 fn prefixes_are_read_from_the_root() {
330 let xml = br#"<x:doc xmlns:x="urn:w" xmlns="urn:d"/>"#;
331 let tree = Tree::parse(xml, "t", &Limits::default()).unwrap();
332 assert_eq!(tree.prefix_for("urn:w").as_deref(), Some("x:"));
333 assert_eq!(tree.prefix_for("urn:d").as_deref(), Some(""));
334 assert_eq!(tree.prefix_for("urn:none"), None);
335 }
336}
337

Indexing the workspace…