use crate::tags::Tag;
pub type NodeId = u32;
pub(crate) const NONE: NodeId = NodeId::MAX;
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum Ns {
Html,
Svg,
MathMl,
Xml,
}
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum AttrNs {
None,
XLink,
Xml,
Xmlns,
Host(u32),
}
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum Quirks {
No,
Limited,
Quirks,
}
const IN_SOURCE: u32 = 1 << 31;
const IN_EXTRA: u32 = 1 << 30;
pub const MAX_INPUT: usize = 1 << 29;
#[derive(Debug, Clone, Copy)]
pub(crate) struct Span {
pub start: u32,
pub end: u32,
}
#[derive(Debug, Clone, Copy)]
pub(crate) enum Name {
Tag,
Svg(u8),
Span(Span),
}
#[derive(Debug, Clone, Copy)]
pub(crate) struct Attr {
pub ns: AttrNs,
pub name: Span,
pub value: Span,
}
#[derive(Debug, Clone, Copy)]
pub(crate) struct Element {
pub ns: Ns,
pub tag: Tag,
pub name: Name,
pub attrs: Span,
pub contents: NodeId,
pub html_integration: bool,
}
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum ShadowRootMode {
Open,
Closed,
}
#[derive(Debug, Clone, Copy, PartialEq, Eq, Default)]
pub enum SlotAssignment {
#[default]
Named,
Manual,
}
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub struct ShadowRoot {
pub mode: ShadowRootMode,
pub delegates_focus: bool,
pub clonable: bool,
pub serializable: bool,
pub slot_assignment: SlotAssignment,
pub declarative: bool,
}
impl ShadowRoot {
pub fn open() -> ShadowRoot {
ShadowRoot {
mode: ShadowRootMode::Open,
delegates_focus: false,
clonable: false,
serializable: false,
slot_assignment: SlotAssignment::Named,
declarative: false,
}
}
pub fn closed() -> ShadowRoot {
ShadowRoot {
mode: ShadowRootMode::Closed,
..ShadowRoot::open()
}
}
}
#[derive(Debug, Clone, Copy)]
pub(crate) enum Data {
Document,
Fragment,
ShadowRoot {
host: NodeId,
init: ShadowRoot,
},
Doctype {
name: Span,
public_id: Span,
system_id: Span,
},
Element(Element),
Text(Span),
Comment(Span),
ProcessingInstruction {
target: Span,
data: Span,
},
Cdata(Span),
}
#[derive(Debug, Clone, Copy)]
pub(crate) struct Node {
pub parent: NodeId,
pub first_child: NodeId,
pub last_child: NodeId,
pub prev: NodeId,
pub next: NodeId,
pub data: Data,
}
pub struct Document {
pub(crate) nodes: Vec<Node>,
pub(crate) src: String,
pub(crate) buf: String,
pub(crate) extras: Vec<String>,
pub(crate) attrs: Vec<Attr>,
pub(crate) quirks: Quirks,
pub(crate) scripting: bool,
pub(crate) positions: Option<Box<Positions>>,
pub(crate) hosts: Option<std::collections::HashMap<NodeId, NodeId>>,
pub(crate) shadow_roots: std::collections::HashMap<NodeId, NodeId>,
pub(crate) manual_slots: std::collections::HashMap<NodeId, Vec<NodeId>>,
pub(crate) errors: Vec<crate::SyntaxError>,
pub(crate) dead: Vec<u64>,
lines: std::sync::OnceLock<Lines>,
}
struct Lines {
starts: Vec<u32>,
chars: Vec<u32>,
}
impl Lines {
const BLOCK: usize = 4096;
fn new(src: &[u8]) -> Lines {
let mut starts = vec![0];
starts.extend(memchr::memchr_iter(b'\n', src).map(|i| i as u32 + 1));
let mut chars = Vec::with_capacity(src.len() / Lines::BLOCK + 1);
let mut before = 0;
for block in src.chunks(Lines::BLOCK) {
chars.push(before);
before += count_chars(block) as u32;
}
chars.push(before);
Lines { starts, chars }
}
fn chars_before(&self, src: &[u8], at: usize) -> usize {
let block = at / Lines::BLOCK;
self.chars[block] as usize + count_chars(&src[block * Lines::BLOCK..at])
}
}
fn count_chars(bytes: &[u8]) -> usize {
bytes.iter().filter(|&&b| (b as i8) >= -0x40).count()
}
const UNKNOWN: [u32; 2] = [u32::MAX; 2];
#[derive(Debug, Default)]
pub(crate) struct Positions {
pub nodes: Vec<[u32; 2]>,
pub ends: Vec<[u32; 2]>,
pub attrs: Vec<[u32; 2]>,
pub crlf: Vec<u32>,
pub skipped: u32,
}
impl Positions {
pub(crate) fn set(list: &mut Vec<[u32; 2]>, i: usize, at: [u32; 2]) {
if list.len() <= i {
list.resize(i + 1, UNKNOWN);
}
list[i] = at;
}
fn get(list: &[[u32; 2]], i: usize) -> Option<[u32; 2]> {
list.get(i).copied().filter(|&a| a != UNKNOWN)
}
pub(crate) fn original(&self, at: u32) -> usize {
let dropped = self.crlf.partition_point(|&lf| lf < at);
self.skipped as usize + at as usize + dropped
}
fn range(&self, at: [u32; 2]) -> std::ops::Range<usize> {
self.original(at[0])..self.original(at[1])
}
}
#[derive(Debug, PartialEq, Eq)]
pub enum Kind<'a> {
Document,
Fragment,
ShadowRoot(ShadowRoot),
Doctype {
name: &'a str,
public_id: &'a str,
system_id: &'a str,
},
Element {
ns: Ns,
name: &'a str,
},
Text(&'a str),
Comment(&'a str),
ProcessingInstruction {
target: &'a str,
data: &'a str,
},
Cdata(&'a str),
}
impl Document {
pub(crate) fn new(root: Data, capacity: usize) -> Document {
let mut nodes = Vec::with_capacity(capacity / 10 + 16);
nodes.push(Node {
parent: NONE,
first_child: NONE,
last_child: NONE,
prev: NONE,
next: NONE,
data: root,
});
Document {
nodes,
src: String::new(),
buf: String::with_capacity(capacity / 8),
extras: Vec::new(),
attrs: Vec::with_capacity(capacity / 32 + 16),
quirks: Quirks::No,
scripting: false,
positions: None,
hosts: None,
shadow_roots: std::collections::HashMap::new(),
manual_slots: std::collections::HashMap::new(),
errors: Vec::new(),
dead: Vec::new(),
lines: std::sync::OnceLock::new(),
}
}
pub fn empty() -> Document {
Document::new(Data::Document, 0)
}
pub fn root(&self) -> NodeId {
0
}
pub fn quirks(&self) -> Quirks {
self.quirks
}
pub fn len(&self) -> usize {
self.nodes.len()
}
pub fn is_empty(&self) -> bool {
self.nodes.len() <= 1
}
pub(crate) fn str(&self, s: Span) -> &str {
if s.start & IN_SOURCE != 0 {
&self.src[(s.start & !IN_SOURCE) as usize..(s.end & !IN_SOURCE) as usize]
} else if s.start & IN_EXTRA != 0 {
&self.extras[(s.start & !IN_EXTRA) as usize]
} else {
&self.buf[s.start as usize..s.end as usize]
}
}
pub(crate) fn push_stable(&mut self, s: &str) -> Span {
let at = self.extras.len() as u32 | IN_EXTRA;
self.extras.push(s.to_owned());
Span { start: at, end: at }
}
pub(crate) fn source_offset(&self, s: &str) -> Option<usize> {
let base = self.src.as_ptr() as usize;
let at = s.as_ptr() as usize;
(at >= base && at + s.len() <= base + self.src.len()).then(|| at - base)
}
pub(crate) fn intern(&mut self, s: &str) -> Span {
match self.source_offset(s) {
Some(at) => Span {
start: at as u32 | IN_SOURCE,
end: (at + s.len()) as u32 | IN_SOURCE,
},
None => self.push_str(s),
}
}
pub(crate) fn push_str(&mut self, s: &str) -> Span {
if self.buf.len() + s.len() >= IN_EXTRA as usize {
return self.push_stable(s);
}
let start = self.buf.len() as u32;
self.buf.push_str(s);
Span {
start,
end: self.buf.len() as u32,
}
}
pub(crate) fn add(&mut self, data: Data) -> NodeId {
let id = self.nodes.len() as NodeId;
self.nodes.push(Node {
parent: NONE,
first_child: NONE,
last_child: NONE,
prev: NONE,
next: NONE,
data,
});
id
}
pub fn span(&self, id: NodeId) -> Option<std::ops::Range<usize>> {
if self.is_removed(id) {
return None;
}
let p = self.positions.as_deref()?;
Positions::get(&p.nodes, id as usize).map(|at| p.range(at))
}
pub fn end_span(&self, id: NodeId) -> Option<std::ops::Range<usize>> {
if self.is_removed(id) {
return None;
}
let p = self.positions.as_deref()?;
Positions::get(&p.ends, id as usize).map(|at| p.range(at))
}
pub fn attr_span(&self, id: NodeId, i: usize) -> Option<std::ops::Range<usize>> {
if self.is_removed(id) {
return None;
}
let p = self.positions.as_deref()?;
let e = self.element(id)?;
let at = e.attrs.start as usize + i;
if at >= e.attrs.end as usize {
return None;
}
Positions::get(&p.attrs, at).map(|at| p.range(at))
}
pub fn line_col(&self, offset: usize) -> (usize, usize) {
let (skipped, crlf) = self
.positions
.as_deref()
.map_or((0, &[][..]), |p| (p.skipped as usize, &p.crlf[..]));
let o = offset.saturating_sub(skipped);
let (mut lo, mut hi) = (0, crlf.len());
while lo < hi {
let mid = (lo + hi) / 2;
if crlf[mid] as usize + mid + 1 < o {
lo = mid + 1;
} else {
hi = mid;
}
}
let at = (o - lo.min(o)).min(self.src.len());
let src = self.src.as_bytes();
let lines = self.lines.get_or_init(|| Lines::new(src));
let line = lines.starts.partition_point(|&s| s as usize <= at);
let start = lines.starts[line - 1] as usize;
let column = 1 + lines.chars_before(src, at) - lines.chars_before(src, start);
(line, column)
}
pub fn errors(&self) -> &[crate::SyntaxError] {
&self.errors
}
pub(crate) fn element(&self, id: NodeId) -> Option<&Element> {
match &self.nodes[id as usize].data {
Data::Element(e) => Some(e),
_ => None,
}
}
pub(crate) fn element_name(&self, e: &Element) -> &str {
match e.name {
Name::Tag => e.tag.name(),
Name::Svg(i) => crate::tree::SVG_TAG_NAMES[i as usize].1,
Name::Span(s) => self.str(s),
}
}
pub(crate) fn insert(&mut self, parent: NodeId, child: NodeId, before: NodeId) {
debug_assert!(
matches!(
self.nodes[parent as usize].data,
Data::Element(_) | Data::Document | Data::Fragment | Data::ShadowRoot { .. }
),
"node {parent} can't have children"
);
debug_assert!(
!matches!(
self.nodes[child as usize].data,
Data::Document | Data::Fragment | Data::ShadowRoot { .. }
),
"node {child} is a document, fragment or shadow root, never a child"
);
debug_assert!(
self.nodes[child as usize].parent == NONE
&& self.nodes[child as usize].prev == NONE
&& self.nodes[child as usize].next == NONE,
"node {child} is inserted while still linked"
);
debug_assert!(parent != child, "node {child} inserted into itself");
debug_assert!(
before == NONE || self.nodes[before as usize].parent == parent,
"node {before} isn't a child of {parent}"
);
let prev = if before == NONE {
self.nodes[parent as usize].last_child
} else {
self.nodes[before as usize].prev
};
{
let c = &mut self.nodes[child as usize];
c.parent = parent;
c.prev = prev;
c.next = before;
}
if prev == NONE {
self.nodes[parent as usize].first_child = child;
} else {
self.nodes[prev as usize].next = child;
}
if before == NONE {
self.nodes[parent as usize].last_child = child;
} else {
self.nodes[before as usize].prev = child;
}
debug_assert!(self.links_agree(child), "links around node {child}");
}
pub fn detach(&mut self, child: NodeId) {
let Node {
parent, prev, next, ..
} = self.nodes[child as usize];
if parent == NONE {
debug_assert!(
prev == NONE && next == NONE,
"node {child} has siblings, no parent"
);
return;
}
debug_assert!(self.links_agree(child), "links around node {child}");
if prev == NONE {
self.nodes[parent as usize].first_child = next;
} else {
self.nodes[prev as usize].next = next;
}
if next == NONE {
self.nodes[parent as usize].last_child = prev;
} else {
self.nodes[next as usize].prev = prev;
}
let c = &mut self.nodes[child as usize];
c.parent = NONE;
c.prev = NONE;
c.next = NONE;
debug_assert!(
(prev == NONE || self.links_agree(prev)) && (next == NONE || self.links_agree(next)),
"links where node {child} was"
);
}
pub(crate) fn links_agree(&self, id: NodeId) -> bool {
let n = &self.nodes[id as usize];
if n.parent == NONE {
return n.prev == NONE && n.next == NONE;
}
let p = &self.nodes[n.parent as usize];
let prev_ok = if n.prev == NONE {
p.first_child == id
} else {
let s = &self.nodes[n.prev as usize];
s.next == id && s.parent == n.parent && p.first_child != id
};
let next_ok = if n.next == NONE {
p.last_child == id
} else {
let s = &self.nodes[n.next as usize];
s.prev == id && s.parent == n.parent && p.last_child != id
};
prev_ok && next_ok
}
pub(crate) fn append_text(&mut self, id: NodeId, text: &str) {
let Data::Text(span) = self.nodes[id as usize].data else {
unreachable!("not a text node")
};
let in_source = span.start & IN_SOURCE != 0;
let in_buf = span.start & (IN_SOURCE | IN_EXTRA) == 0;
let span =
if in_source && self.source_offset(text) == Some((span.end & !IN_SOURCE) as usize) {
debug_assert!((span.end & !IN_SOURCE) as usize + text.len() <= self.src.len());
Span {
start: span.start,
end: span.end + text.len() as u32,
}
} else if in_buf
&& span.end as usize == self.buf.len()
&& self.buf.len() + text.len() < IN_EXTRA as usize
{
self.buf.push_str(text);
Span {
start: span.start,
end: self.buf.len() as u32,
}
} else if span.start & IN_EXTRA != 0 {
self.extras[(span.start & !IN_EXTRA) as usize].push_str(text);
span
} else {
let mut own = self.str(span).to_owned();
own.push_str(text);
let at = self.extras.len() as u32 | IN_EXTRA;
self.extras.push(own);
Span { start: at, end: at }
};
self.nodes[id as usize].data = Data::Text(span);
}
#[cfg(debug_assertions)]
pub fn check_tree(&self) {
let len = self.nodes.len();
let span_ok = |s: Span| {
if s.start & IN_SOURCE != 0 {
let (a, b) = (s.start & !IN_SOURCE, s.end & !IN_SOURCE);
s.end & IN_SOURCE != 0
&& a <= b
&& self.src.is_char_boundary(a as usize)
&& self.src.is_char_boundary(b as usize)
} else if s.start & IN_EXTRA != 0 {
s.start == s.end && ((s.start & !IN_EXTRA) as usize) < self.extras.len()
} else {
s.start <= s.end
&& self.buf.is_char_boundary(s.start as usize)
&& self.buf.is_char_boundary(s.end as usize)
}
};
let mut contents_of = vec![NONE; len];
for (id, n) in self.nodes.iter().enumerate() {
let id = id as NodeId;
for link in [n.parent, n.first_child, n.last_child, n.prev, n.next] {
assert!(
link == NONE || (link as usize) < len,
"node {id} links past the end"
);
}
assert!(self.links_agree(id), "links around node {id}");
assert!(
!self.is_removed(id) || n.parent == NONE || self.is_removed(n.parent),
"removed node {id} is under {}, which isn't",
n.parent
);
assert_eq!(
n.first_child == NONE,
n.last_child == NONE,
"node {id} has a first child or a last, not both"
);
if n.first_child != NONE {
let first = &self.nodes[n.first_child as usize];
let last = &self.nodes[n.last_child as usize];
assert!(
first.parent == id && first.prev == NONE,
"node {id}'s first child"
);
assert!(
last.parent == id && last.next == NONE,
"node {id}'s last child"
);
assert!(
matches!(
n.data,
Data::Element(_)
| Data::Document
| Data::Fragment
| Data::ShadowRoot { .. }
),
"node {id} can't have children"
);
}
match n.data {
Data::Document | Data::Fragment => {
assert!(
n.parent == NONE,
"node {id}, a document or fragment, has a parent"
)
}
Data::ShadowRoot { host, .. } => {
assert!(n.parent == NONE, "shadow root {id} has a parent");
assert!(
self.element(host).is_some(),
"shadow root {id}'s host isn't an element"
);
assert_eq!(
self.shadow_roots.get(&host),
Some(&id),
"shadow root {id} isn't its host's"
);
}
Data::Element(e) => {
let name_ok = match e.name {
Name::Tag => true,
Name::Svg(i) => (i as usize) < crate::tree::SVG_TAG_NAMES.len(),
Name::Span(s) => span_ok(s),
};
assert!(name_ok, "node {id}'s name");
assert!(
e.attrs.start <= e.attrs.end && e.attrs.end as usize <= self.attrs.len(),
"node {id}'s attributes"
);
if e.contents != NONE {
let c = e.contents as usize;
assert!(
e.ns == Ns::Html && e.tag == Tag::Template,
"node {id} has contents but isn't a template"
);
assert!(
c < len && matches!(self.nodes[c].data, Data::Fragment),
"node {id}'s contents aren't a fragment"
);
assert!(contents_of[c] == NONE, "two templates have contents {c}");
contents_of[c] = id;
}
}
Data::Doctype {
name,
public_id,
system_id,
} => assert!(
span_ok(name) && span_ok(public_id) && span_ok(system_id),
"node {id}'s strings"
),
Data::Text(s) | Data::Comment(s) | Data::Cdata(s) => {
assert!(span_ok(s), "node {id}'s text")
}
Data::ProcessingInstruction { target, data } => {
assert!(span_ok(target) && span_ok(data), "node {id}'s strings")
}
}
}
for (i, a) in self.attrs.iter().enumerate() {
assert!(
span_ok(a.name) && span_ok(a.value),
"attribute {i}'s strings"
);
}
for (&host, &root) in &self.shadow_roots {
assert!(
matches!(self.nodes.get(root as usize).map(|n| n.data), Some(Data::ShadowRoot { host: h, .. }) if h == host),
"host {host}'s shadow root {root} doesn't name it"
);
}
for (&slot, nodes) in &self.manual_slots {
assert!(
self.element(slot).is_some(),
"manual slot {slot} isn't an element"
);
assert!(
nodes.iter().all(|&n| (n as usize) < len),
"manual slot {slot}'s nodes"
);
}
if let Some(hosts) = &self.hosts {
for (&contents, &host) in hosts {
assert_eq!(
contents_of.get(contents as usize),
Some(&host),
"the hosts map at {contents}"
);
}
let templates = contents_of.iter().filter(|&&h| h != NONE).count();
assert_eq!(hosts.len(), templates, "the hosts map misses a template");
}
let mut seen = vec![false; len];
let mut stack = vec![self.root()];
while let Some(id) = stack.pop() {
assert!(!seen[id as usize], "node {id} reached twice");
seen[id as usize] = true;
let n = &self.nodes[id as usize];
let mut child = n.first_child;
while child != NONE {
assert!(!seen[child as usize], "a loop among node {id}'s children");
assert_eq!(
self.nodes[child as usize].parent, id,
"node {child}'s parent"
);
stack.push(child);
child = self.nodes[child as usize].next;
if stack.len() > len {
panic!("a loop among node {id}'s children");
}
}
if let Data::Element(e) = n.data
&& e.contents != NONE
{
stack.push(e.contents);
}
if let Some(&root) = self.shadow_roots.get(&id) {
stack.push(root);
}
}
if let Some(p) = self.positions.as_deref() {
let src = self.src.len() as u32;
let in_src = |at: &[u32; 2]| *at == UNKNOWN || (at[0] <= at[1] && at[1] <= src);
assert!(
p.nodes.len() <= len && p.ends.len() <= len,
"positions past the nodes"
);
assert!(
p.attrs.len() <= self.attrs.len(),
"positions past the attributes"
);
for (i, at) in p.nodes.iter().chain(&p.ends).chain(&p.attrs).enumerate() {
assert!(
in_src(at),
"position {i}, {at:?}, outside {src} bytes of source"
);
}
assert!(p.crlf.windows(2).all(|w| w[0] < w[1]), "CRLFs out of order");
assert!(
p.crlf.last().is_none_or(|&lf| lf < src),
"a CRLF past the source"
);
let original = p.original(src);
for e in &self.errors {
assert!(
e.offset <= original,
"{e:?} past the input's {original} bytes"
);
}
}
}
pub fn parent(&self, id: NodeId) -> Option<NodeId> {
if self.is_removed(id) {
return None;
}
Some(self.nodes[id as usize].parent).filter(|&p| p != NONE)
}
pub fn first_child(&self, id: NodeId) -> Option<NodeId> {
if self.is_removed(id) {
return None;
}
Some(self.nodes[id as usize].first_child).filter(|&c| c != NONE)
}
pub fn prev_sibling(&self, id: NodeId) -> Option<NodeId> {
if self.is_removed(id) {
return None;
}
Some(self.nodes[id as usize].prev).filter(|&c| c != NONE)
}
pub fn last_child(&self, id: NodeId) -> Option<NodeId> {
if self.is_removed(id) {
return None;
}
Some(self.nodes[id as usize].last_child).filter(|&c| c != NONE)
}
pub fn next_sibling(&self, id: NodeId) -> Option<NodeId> {
if self.is_removed(id) {
return None;
}
Some(self.nodes[id as usize].next).filter(|&c| c != NONE)
}
pub fn children(&self, id: NodeId) -> impl Iterator<Item = NodeId> + '_ {
std::iter::successors(self.first_child(id), move |&c| self.next_sibling(c))
}
pub fn template_contents(&self, id: NodeId) -> Option<NodeId> {
if self.is_removed(id) {
return None;
}
self.element(id).map(|e| e.contents).filter(|&c| c != NONE)
}
pub fn is_removed(&self, id: NodeId) -> bool {
self.dead
.get(id as usize / 64)
.is_some_and(|w| w >> (id % 64) & 1 == 1)
}
pub(crate) fn mark_removed(&mut self, id: NodeId) {
let word = id as usize / 64;
if self.dead.len() <= word {
self.dead.resize(word + 1, 0);
}
self.dead[word] |= 1 << (id % 64);
}
pub fn kind(&self, id: NodeId) -> Kind<'_> {
let kind = self.kind_of(id);
if !self.is_removed(id) {
return kind;
}
match kind {
Kind::Text(_) => Kind::Text(""),
Kind::Comment(_) => Kind::Comment(""),
Kind::Cdata(_) => Kind::Cdata(""),
Kind::ProcessingInstruction { target, .. } => {
Kind::ProcessingInstruction { target, data: "" }
}
other => other,
}
}
fn kind_of(&self, id: NodeId) -> Kind<'_> {
match &self.nodes[id as usize].data {
Data::Document => Kind::Document,
Data::Fragment => Kind::Fragment,
Data::ShadowRoot { init, .. } => Kind::ShadowRoot(*init),
Data::Doctype {
name,
public_id,
system_id,
} => Kind::Doctype {
name: self.str(*name),
public_id: self.str(*public_id),
system_id: self.str(*system_id),
},
Data::Element(e) => Kind::Element {
ns: e.ns,
name: self.element_name(e),
},
Data::Text(s) => Kind::Text(self.str(*s)),
Data::Comment(s) => Kind::Comment(self.str(*s)),
Data::Cdata(s) => Kind::Cdata(self.str(*s)),
Data::ProcessingInstruction { target, data } => Kind::ProcessingInstruction {
target: self.str(*target),
data: self.str(*data),
},
}
}
pub fn attrs(&self, id: NodeId) -> impl Iterator<Item = (AttrNs, &str, &str)> + '_ {
let attrs = if self.is_removed(id) {
&[][..]
} else {
self.attrs_of(id)
};
attrs.iter().map(|a| {
let name = self.str(a.name);
let name = match a.ns {
AttrNs::XLink | AttrNs::Xml | AttrNs::Xmlns => {
name.split_once(':').map_or(name, |(_, local)| local)
}
_ => name,
};
(a.ns, name, self.str(a.value))
})
}
pub fn attrs_written(&self, id: NodeId) -> impl Iterator<Item = (AttrNs, &str, &str)> + '_ {
let ns = self.element(id).map_or(Ns::Html, |e| e.ns);
let attrs = if self.is_removed(id) {
&[][..]
} else {
self.attrs_of(id)
};
attrs
.iter()
.map(move |a| (a.ns, self.written_name(ns, a), self.str(a.value)))
}
pub(crate) fn attrs_of(&self, id: NodeId) -> &[Attr] {
let range = self
.element(id)
.map_or(0..0, |e| e.attrs.start as usize..e.attrs.end as usize);
&self.attrs[range]
}
pub(crate) fn written_name(&self, ns: Ns, a: &Attr) -> &str {
let name = self.str(a.name);
match (ns, a.ns) {
(Ns::Svg, AttrNs::None) => crate::tree::svg_attr_name(name).unwrap_or(name),
(Ns::MathMl, AttrNs::None) if name == "definitionurl" => "definitionURL",
_ => name,
}
}
pub fn lower_name(&self, id: NodeId) -> Option<&str> {
if self.is_removed(id) {
return None;
}
let e = self.element(id)?;
Some(match e.name {
Name::Tag => e.tag.name(),
Name::Svg(i) => crate::tree::SVG_TAG_NAMES[i as usize].0,
Name::Span(s) => self.str(s),
})
}
pub fn known_tag(&self, id: NodeId) -> Option<u8> {
if self.is_removed(id) {
return None;
}
self.element(id)
.filter(|e| e.tag != Tag::Other && e.ns != Ns::Xml)
.map(|e| e.tag as u8)
}
}
#[cfg(test)]
mod tests {
use super::{Data, Document, IN_EXTRA, Kind, count_chars};
use crate::{AttrNs, parse};
#[test]
fn foreign_attributes_have_a_lowercase_name_and_a_written_one() {
let doc = parse(
"<svg viewBox=0 xmlns:xlink=x><use xlink:href=#i></use></svg>\
<math definitionURL=d></math>",
false,
);
let svg = (0..doc.len() as u32)
.find(|&n| doc.lower_name(n) == Some("svg"))
.unwrap();
let use_ = doc.first_child(svg).unwrap();
let math = doc.next_sibling(svg).unwrap();
let names = |n, written: bool| -> Vec<String> {
if written {
doc.attrs_written(n)
.map(|(_, a, _)| a.to_string())
.collect()
} else {
doc.attrs(n).map(|(_, a, _)| a.to_string()).collect()
}
};
assert_eq!(names(svg, false), ["viewbox", "xlink"]);
assert_eq!(names(svg, true), ["viewBox", "xmlns:xlink"]);
assert_eq!(names(use_, false), ["href"]);
assert_eq!(doc.attrs(use_).next().unwrap().0, AttrNs::XLink);
assert_eq!(names(use_, true), ["xlink:href"]);
assert_eq!(names(math, false), ["definitionurl"]);
assert_eq!(names(math, true), ["definitionURL"]);
assert!(doc.outer_html(svg).starts_with(r#"<svg viewBox="0""#));
assert!(doc.outer_html(math).contains("definitionURL"));
}
#[test]
fn line_col_agrees_with_counting_and_costs_little_a_call() {
let input = "\u{FEFF}<p>a\r\nb\rc\n\u{e9}\u{20ac}\u{1F600}</p>".repeat(300)
+ &"\u{e9}".repeat(5_000)
+ "\n"
+ &"x".repeat(4_096 * 2 - 1);
let doc = crate::parse_with(
&input,
crate::Options {
spans: true,
..crate::Options::default()
},
)
.unwrap();
let slow = |offset: usize| {
let p = doc.positions.as_deref().unwrap();
let o = offset.saturating_sub(p.skipped as usize);
let lo = (0..p.crlf.len())
.take_while(|&k| p.crlf[k] as usize + k + 1 < o)
.count();
let bytes = &doc.src.as_bytes()[..(o - lo.min(o)).min(doc.src.len())];
let start = memchr::memrchr(b'\n', bytes).map_or(0, |i| i + 1);
(
1 + memchr::memchr_iter(b'\n', bytes).count(),
1 + count_chars(&bytes[start..]),
)
};
for at in 0..=input.len() + 2 {
assert_eq!(doc.line_col(at), slow(at), "at {at}");
}
let calls = |lines: usize| {
let page = parse(&"x\n".repeat(lines), false);
let start = std::time::Instant::now();
for i in lines - 10_000..lines {
assert_eq!(page.line_col(i * 2), (i + 1, 1));
}
start.elapsed()
};
let rounds: Vec<_> = (0..5).map(|_| (calls(250_000), calls(2_000_000))).collect();
assert!(
rounds
.iter()
.any(|&(a, b)| b < a * 3 + std::time::Duration::from_millis(20)),
"{rounds:?}"
);
}
#[test]
fn an_edit_finds_a_foreign_attribute_by_its_written_name() {
let mut doc = parse("<svg viewBox=0></svg>", false);
let svg = (0..doc.len() as u32)
.find(|&n| doc.lower_name(n) == Some("svg"))
.unwrap();
doc.set_attr(svg, "viewBox", "1").unwrap();
assert_eq!(doc.outer_html(svg), r#"<svg viewBox="1"></svg>"#);
assert!(doc.remove_attr(svg, "viewBox"));
assert_eq!(doc.outer_html(svg), "<svg></svg>");
}
#[test]
fn strings_past_two_to_the_thirty_bytes_of_buffer_read_back() {
let mut doc = Document::empty();
doc.buf = "x".repeat(IN_EXTRA as usize - 4);
let near = doc.push_str("abcdefgh");
let past = doc.push_str("ijkl");
assert_eq!(doc.str(near), "abcdefgh");
assert_eq!(doc.str(past), "ijkl");
assert!(doc.buf.len() < IN_EXTRA as usize);
doc.buf.truncate(IN_EXTRA as usize - 4);
let at = doc.push_str("ab");
let text = doc.add(Data::Text(at));
doc.append_text(text, "cdef");
assert!(matches!(doc.kind(text), Kind::Text("abcdef")));
assert!(doc.buf.len() < IN_EXTRA as usize);
}
}