// The span-addressed formatting planner (F2a). Selection reuses find's
// own enumeration in text mode, so what formatting acts on is EXACTLY
// what find reported — but NOT find's verdict: `actionable` is the
// identity-REPLACEMENT judgment, and a hyperlink-boundary span that
// cannot be replaced is still perfectly formattable. Formatting's
// verdict is the formatting planner's own refusal, raised while
// planning.
///|
/// One selected span, as the receipt reports it.
pub struct DocxFormatSpan {
path : String
para_id : String?
anchor_status : String
start : Int
end : Int
text : String
source_runs : Array[String]
}
///|
/// The paragraph the span belongs to, body-relative.
pub fn DocxFormatSpan::path(self : DocxFormatSpan) -> String {
self.path
}
///|
/// The paragraph's canonical anchor paraId, when it carries one.
pub fn DocxFormatSpan::para_id(self : DocxFormatSpan) -> String? {
self.para_id
}
///|
/// The paragraph's anchor status (`unique`, `missing`, `invalid`,
/// `duplicate`).
pub fn DocxFormatSpan::anchor_status(self : DocxFormatSpan) -> String {
self.anchor_status
}
///|
/// The span's paragraph-local UTF-16 start offset.
pub fn DocxFormatSpan::start(self : DocxFormatSpan) -> Int {
self.start
}
///|
/// The span's paragraph-local UTF-16 end offset, exclusive.
pub fn DocxFormatSpan::end(self : DocxFormatSpan) -> Int {
self.end
}
///|
/// The projected text the span selects.
pub fn DocxFormatSpan::text(self : DocxFormatSpan) -> String {
self.text
}
///|
/// The runs the span drew from BEFORE the edit — a snapshot, because a
/// split changes what runs exist.
pub fn DocxFormatSpan::source_runs(self : DocxFormatSpan) -> Array[String] {
self.source_runs.copy()
}
///|
/// One affected paragraph: its identity, the projection it must STILL
/// read afterwards (formatting never moves text), and what the plan did
/// to its runs.
pub struct DocxFormatAffected {
path : String
expected : String
para_id : String?
anchor_status : String
runs_changed : Int
runs_already_satisfied : Int
splits : Int
}
///|
/// The paragraph's body-relative path.
pub fn DocxFormatAffected::path(self : DocxFormatAffected) -> String {
self.path
}
///|
/// The projection the paragraph must still read after the edit.
pub fn DocxFormatAffected::expected(self : DocxFormatAffected) -> String {
self.expected
}
///|
/// The paragraph's canonical anchor paraId, when it carries one.
pub fn DocxFormatAffected::para_id(self : DocxFormatAffected) -> String? {
self.para_id
}
///|
/// The paragraph's anchor status.
pub fn DocxFormatAffected::anchor_status(self : DocxFormatAffected) -> String {
self.anchor_status
}
///|
/// How many of the paragraph's runs the plan rewrites.
pub fn DocxFormatAffected::runs_changed(self : DocxFormatAffected) -> Int {
self.runs_changed
}
///|
/// How many of the paragraph's touched runs already held the request.
pub fn DocxFormatAffected::runs_already_satisfied(
self : DocxFormatAffected,
) -> Int {
self.runs_already_satisfied
}
///|
/// How many of the paragraph's runs the plan clone-splits.
pub fn DocxFormatAffected::splits(self : DocxFormatAffected) -> Int {
self.splits
}
///|
/// What a planned formatting batch will do.
pub struct DocxFormatReceipt {
mode : String
requested_text : String?
requested_within : String?
requested_nth : Int?
requested_range : (Int, Int)?
selected : Array[Int]
spans : Array[DocxFormatSpan]
affected : Array[DocxFormatAffected]
runs_changed : Int
runs_already_satisfied : Int
splits : Int
byte_edits : Int
}
///|
/// `text` or `range` — which selector produced the spans.
pub fn DocxFormatReceipt::mode(self : DocxFormatReceipt) -> String {
self.mode
}
///|
/// The needle the caller asked for, in text mode.
pub fn DocxFormatReceipt::requested_text(self : DocxFormatReceipt) -> String? {
self.requested_text
}
///|
/// The subtree the caller restricted to, if any — and in range mode,
/// the paragraph it addressed.
pub fn DocxFormatReceipt::requested_within(self : DocxFormatReceipt) -> String? {
self.requested_within
}
///|
/// The ordinal the caller selected, if any. `None` with one span means
/// "all candidates, and there was one" — a distinction a count alone
/// cannot make.
pub fn DocxFormatReceipt::requested_nth(self : DocxFormatReceipt) -> Int? {
self.requested_nth
}
///|
/// The explicit range the caller addressed, in range mode.
pub fn DocxFormatReceipt::requested_range(
self : DocxFormatReceipt,
) -> (Int, Int)? {
self.requested_range
}
///|
/// The candidate ordinals this plan formats, in document order. Empty
/// in range mode, which addresses coordinates rather than candidates.
pub fn DocxFormatReceipt::selected(self : DocxFormatReceipt) -> Array[Int] {
self.selected.copy()
}
///|
/// The selected spans.
pub fn DocxFormatReceipt::spans(
self : DocxFormatReceipt,
) -> Array[DocxFormatSpan] {
// A span carries an array of its own, so copying only the outer array
// would hand the caller a handle back into the receipt.
self.spans.map(DocxFormatSpan::copy)
}
///|
/// A span that shares nothing with this one, so a caller handed it
/// cannot reach back into the receipt it came from.
pub fn DocxFormatSpan::copy(self : DocxFormatSpan) -> DocxFormatSpan {
{ ..self, source_runs: self.source_runs.copy(), }
}
///|
/// The affected paragraphs with their unchanged projections.
pub fn DocxFormatReceipt::affected(
self : DocxFormatReceipt,
) -> Array[DocxFormatAffected] {
self.affected.copy()
}
///|
/// How many runs the plan rewrites.
pub fn DocxFormatReceipt::runs_changed(self : DocxFormatReceipt) -> Int {
self.runs_changed
}
///|
/// How many touched runs already held every requested property — the
/// no-op accounting a `changed=false` report rests on.
pub fn DocxFormatReceipt::runs_already_satisfied(
self : DocxFormatReceipt,
) -> Int {
self.runs_already_satisfied
}
///|
/// How many runs the plan clone-splits.
pub fn DocxFormatReceipt::splits(self : DocxFormatReceipt) -> Int {
self.splits
}
///|
/// How many byte edits the plan carries. Zero means the document
/// already held the request everywhere it was asked.
pub fn DocxFormatReceipt::byte_edits(self : DocxFormatReceipt) -> Int {
self.byte_edits
}
///|
/// Plan absolute direct formatting over spans of the body story.
///
/// Exactly one selector: `text` (find's literal enumeration, with
/// `within` restricting the subtree and `nth` selecting one candidate
/// by ordinal) or `range` (paragraph-local UTF-16 coordinates inside
/// the single paragraph `within` names). Selection happens BEFORE
/// formatting actionability, and any refusal aborts the whole batch —
/// formatting never silently skips what it selected.
///
/// `DocxMatch::actionable` is deliberately NOT consulted: it is the
/// identity-replacement verdict, and a span crossing a hyperlink
/// boundary is unreplaceable yet formattable. The formatting planner
/// raises its own refusals instead.
///
/// Zero candidates plans nothing and returns an empty receipt; whether
/// that is an error is the caller's policy, not this engine's fact.
///
/// The returned plan is pinned to the annotated read's retained bytes,
/// so applying it to any other snapshot refuses as stale.
pub fn plan_docx_format(
annotated : DocxAnnotatedResult,
story : DocxStoryPartSource,
format~ : DocxDirectFormat,
text? : String,
within? : String,
nth? : Int,
range? : (Int, Int),
) -> (@splice.SplicePlan, DocxFormatReceipt) raise DocxError {
let part = story.part()
// v1 is BODY-ONLY in both selector modes. Text mode inherits find's
// own check, but range mode reaches the projection directly, and a
// header or footnote formatted through it would carry body
// addressing metadata that is false.
guard part == annotated.main_story_source().part() else {
raise Unsupported(
message="format edits the body story only in v1; '\{part}' is not the main document part",
)
}
guard !(text is Some(_) && range is Some(_)) else {
raise Unsupported(
message="format takes exactly one selector: a text needle or an explicit range",
)
}
guard text is Some(_) || range is Some(_) else {
raise Unsupported(
message="format takes exactly one selector: a text needle or an explicit range",
)
}
guard !(range is Some(_) && nth is Some(_)) else {
raise Unsupported(
message="nth selects among text candidates; an explicit range addresses one span already",
)
}
guard annotated.reader_projections.get(part) is Some(projection) else {
raise Unsupported(
message="format requires a mutation-safe read with a retained projection for '\{part}'",
)
}
guard annotated.reader_projection_sources.get(part) is Some(bytes) else {
raise Unsupported(
message="the mutation-safe read retained no source bytes for '\{part}'",
)
}
let paragraph_paths = find_path_map(projection.scan, "p")
let elements = projection.scan.elements()
// Paths are NOT unique: a tolerated nested paragraph makes two
// logical paragraphs share one physical head, hence one path. A
// last-wins map would format one paragraph while the receipt
// described the other, so collided paths are counted and refused
// rather than answered for.
let index_by_path : Map[String, Int] = Map([])
let claimants : Map[String, Int] = Map([])
for paragraph_index, paragraph in projection.paragraphs {
guard paragraph.sources.length() > 0 else { continue }
let SourceElementId(head) = paragraph.sources[0].source
if paragraph_paths.get(elements[head].byte_start) is Some(path) {
claimants[path] = match claimants.get(path) {
Some(seen) => seen + 1
None => 1
}
if claimants.get(path) == Some(1) {
index_by_path[path] = paragraph_index
}
}
}
fn resolve_paragraph(path : String) -> Int raise DocxError {
guard claimants.get(path) is Some(count) else {
raise Unsupported(
message="the paragraph '\{path}' did not resolve to a projection paragraph",
)
}
guard count == 1 else {
raise Unsupported(
message="the path '\{path}' names \{count} logical paragraphs (a tolerated nested paragraph shares its head); formatting refuses an ambiguous address",
)
}
guard index_by_path.get(path) is Some(paragraph_index) else {
raise Unsupported(
message="the paragraph '\{path}' did not resolve to a projection paragraph",
)
}
paragraph_index
}
// Selection.
let mode = if range is Some(_) { "range" } else { "text" }
let ordinals : Array[Int] = []
let spans : Array[DocxFormatSpan] = []
match range {
Some((start, end)) => {
guard within is Some(scope) else {
raise Unsupported(
message="an explicit range needs the paragraph it addresses (--in)",
)
}
guard claimants.get(scope) is Some(_) else {
raise Unsupported(
message="the scope '\{scope}' does not name a paragraph of this story",
)
}
let paragraph_index = resolve_paragraph(scope)
let paragraph = projection.paragraphs[paragraph_index]
let projected = find_paragraph_projection(paragraph)
guard start >= 0 && start < end && end <= projected.length() else {
raise Unsupported(
message="the range \{start}:\{end} is outside the paragraph's \{projected.length()} unit(s)",
)
}
let anchors = docx_paragraph_anchor_index(annotated, story)
let judgment = anchors.anchor_of_paragraph(paragraph_index)
spans.push({
path: scope,
para_id: match judgment {
Some(found) => found.para_id()
None => None
},
anchor_status: match judgment {
Some(found) => found.status()
None => "missing"
},
start,
end,
text: find_slice(projected, start, end),
source_runs: docx_format_source_runs(
projection, paragraph_index, start, end, scope,
),
})
}
None => {
guard text is Some(needle) else {
raise Unsupported(message="format needs a text needle")
}
let found = find_docx_matches(
annotated,
story,
needle~,
within?,
limit=1000,
)
if found.truncated() {
raise Unsupported(
message="\{found.total()} candidates for the needle exceed the 1000-candidate ceiling; narrow the scope with a subtree restriction or a longer needle",
)
}
let matches = found.matches()
let selected : Array[DocxMatch] = []
match nth {
Some(ordinal) => {
guard ordinal >= 1 && ordinal <= matches.length() else {
raise Unsupported(
message="nth selects candidate \{ordinal}, but the document has \{matches.length()} candidate(s)",
)
}
selected.push(matches[ordinal - 1])
}
None =>
for hit in matches {
selected.push(hit)
}
}
for hit in selected {
ordinals.push(hit.ordinal())
spans.push({
path: hit.path(),
para_id: hit.para_id(),
anchor_status: hit.anchor_status(),
start: hit.start(),
end: hit.end(),
text: hit.text(),
source_runs: hit.runs(),
})
}
}
}
// One batch per paragraph, in document order: the formatting planner
// validates the batch as a whole — ordering, overlap, and every
// structural gate — which is the point of batching.
let plan = @splice.SplicePlan::new()
plan.pin_part(part, bytes)
let affected : Array[DocxFormatAffected] = []
let mut runs_changed = 0
let mut runs_already_satisfied = 0
let mut splits = 0
let mut byte_edits = 0
let mut cursor = 0
while cursor < spans.length() {
let path = spans[cursor].path
let mut stop = cursor
while stop < spans.length() && spans[stop].path == path {
stop = stop + 1
}
let paragraph_index = resolve_paragraph(path)
let requested : Array[ParagraphFormatSpan] = []
for at in cursor.. Array[String] {
let run_paths = find_path_map(projection.scan, "r")
let elements = projection.scan.elements()
let paragraph = projection.paragraphs[paragraph_index]
let base = paragraph.projection_start
let out : Array[String] = []
let seen : Map[String, Bool] = Map([])
for contribution in paragraph.contributions {
guard contribution.kind is ProjectedText(_) else { continue }
let local_start = contribution.projection_start - base
let local_end = contribution.projection_end - base
guard local_start < end && local_end > start else { continue }
guard contribution.run_source is Some(SourceElementId(run_identity)) else {
continue
}
let path = match run_paths.get(elements[run_identity].byte_start) {
Some(found) => found
None => paragraph_path
}
if seen.get(path) is None {
seen[path] = true
out.push(path)
}
}
out
}
///|
/// What every question about one story needs to know about it, built
/// ONCE: which paragraph carries each path and how many claim it, and
/// which source elements the reader registered as paragraphs.
///
/// Both are story-wide facts, and deriving either costs a pass over the
/// whole document. The readback asks about many paragraphs of the same
/// story, so deriving them per question would cost the document again
/// for each one — a thousand formatted paragraphs in a large document
/// turn a bounded read into a quadratic one.
priv struct DocxStoryIndex {
by_path : Map[String, (Int, Int)]
registered : Map[Int, Bool]
}
///|
fn docx_story_index(projection : ReaderProjection) -> DocxStoryIndex {
let by_path : Map[String, (Int, Int)] = Map([])
let registered : Map[Int, Bool] = Map([])
let paragraph_paths = find_path_map(projection.scan, "p")
let elements = projection.scan.elements()
for paragraph_index, paragraph in projection.paragraphs {
for source in paragraph.sources {
let SourceElementId(head) = source.source
registered[head] = true
}
guard paragraph.sources.length() > 0 else { continue }
let SourceElementId(head) = paragraph.sources[0].source
guard paragraph_paths.get(elements[head].byte_start) is Some(path) else {
continue
}
match by_path.get(path) {
Some((first, count)) => by_path[path] = (first, count + 1)
None => by_path[path] = (paragraph_index, 1)
}
}
{ by_path, registered, }
}
///|
/// The paragraph a path names, and how many paragraphs name it.
fn DocxStoryIndex::locate(self : DocxStoryIndex, path : String) -> (Int, Int) {
match self.by_path.get(path) {
Some(entry) => entry
None => (-1, 0)
}
}
///|
///|
/// The readback's direct-format judgment: does every run whose
/// projected text lies inside `[start, end)` of paragraph `path` carry
/// every requested property EXPLICITLY?
///
/// This is the check the projection cannot make — the projection is
/// unchanged by formatting, so only the runs themselves can say whether
/// the edit landed. Returns None when satisfied, or the first
/// discrepancy's description. `None` for a missing paragraph is not
/// possible: an unresolvable path is itself a discrepancy.
pub fn docx_paragraph_direct_format_spans(
annotated : DocxAnnotatedResult,
story : DocxStoryPartSource,
path~ : String,
spans~ : Array[(Int, Int)],
format~ : DocxDirectFormat,
) -> String? raise DocxError {
docx_paragraphs_direct_format(
annotated,
story,
requests=[(path, spans)],
format~,
)[0]
}
///|
/// The same judgment for many paragraphs of one story, with the path
/// lookup built once for the whole batch. Answers are returned in the
/// order asked.
pub fn docx_paragraphs_direct_format(
annotated : DocxAnnotatedResult,
story : DocxStoryPartSource,
requests~ : Array[(String, Array[(Int, Int)])],
format~ : DocxDirectFormat,
) -> Array[String?] raise DocxError {
// An empty batch asks nothing, and building the lookup for it would
// charge a pass over the story for no question.
guard !requests.is_empty() else { return [] }
let part = story.part()
guard annotated.reader_projections.get(part) is Some(projection) else {
return requests.map(_ => {
Some("the re-read retained no projection for '\{part}'")
})
}
guard annotated.reader_projection_sources.get(part) is Some(bytes) else {
return requests.map(_ => {
Some("the re-read retained no source bytes for '\{part}'")
})
}
let index = docx_story_index(projection)
let answers : Array[String?] = []
for request in requests {
let (path, spans) = request
answers.push(
docx_paragraph_direct_format_at(
projection, bytes, index, path, spans, format,
),
)
}
answers
}
///|
/// One paragraph's positive check, against a lookup already built.
fn docx_paragraph_direct_format_at(
projection : ReaderProjection,
bytes : BytesView,
index : DocxStoryIndex,
path : String,
spans : Array[(Int, Int)],
format : DocxDirectFormat,
) -> String? raise DocxError {
let elements = projection.scan.elements()
let (target, found) = index.locate(path)
guard target >= 0 else {
return Some("the path '\{path}' names no paragraph after the edit")
}
// A collided path cannot be answered for: the planner refuses these,
// so seeing one at readback means the document changed shape under
// the edit.
guard found == 1 else {
return Some(
"the path '\{path}' names \{found} logical paragraphs after the edit",
)
}
let paragraph = projection.paragraphs[target]
let base = paragraph.projection_start
// EVERY selected unit must belong to a run: text the tolerant reader
// admits directly under the paragraph has no run to carry direct
// formatting, so a range covering it can never be satisfied — and
// judging only the runs that happen to exist would call that a pass.
// Index the units a run carries ONCE: scanning every contribution
// per unit is quadratic, and a paragraph of many small runs is legal.
let width = paragraph.projection_end - base
// Ownership as ordered INTERVALS: a paragraph is allowed to be one
// enormous run, and a table sized by its units would be sized by the
// text.
let owned : Array[(Int, Int, Int)] = []
for contribution in paragraph.contributions {
guard contribution.kind is ProjectedText(_) else { continue }
guard contribution.run_source is Some(SourceElementId(run_identity)) else {
continue
}
let from = contribution.projection_start - base
let to = contribution.projection_end - base
if to > from && from >= 0 && to <= width {
owned.push((from, to, run_identity))
}
}
owned.sort_by(fn(left, right) { left.0.compare(right.0) })
// The selection, sorted and coalesced ONCE: the sweep below then
// costs the contributions and the spans, not the characters.
let selection : Array[(Int, Int)] = []
for span in spans {
let (start, end) = span
guard start >= 0 && start < end && end <= width else {
return Some(
"the range \{start}:\{end} is outside the \{width} unit(s) of '\{path}'",
)
}
selection.push(span)
}
selection.sort_by(fn(left, right) { left.0.compare(right.0) })
// EVERY selected unit must belong to a run: text the tolerant reader
// admits directly under the paragraph has no run to carry direct
// formatting, so a range covering it can never be satisfied — and
// judging only the runs that happen to exist would call that a pass.
// Every run holding selected text must carry the properties; a run
// whose text lies only OUTSIDE the span is none of this check's
// business.
let judged : Map[Int, Bool] = Map([])
let judged_runs : Array[Int] = []
let mut owned_at = 0
for span in selection {
let (start, end) = span
let mut cursor = start
while owned_at < owned.length() && owned[owned_at].1 <= cursor {
owned_at += 1
}
let mut probe = owned_at
while cursor < end {
guard probe < owned.length() && owned[probe].0 <= cursor else {
return Some(
"unit \{cursor} of '\{path}' is not carried by any run, so it cannot hold direct formatting",
)
}
let (_, owned_end, run_identity) = owned[probe]
if judged.get(run_identity) is None {
judged[run_identity] = true
judged_runs.push(run_identity)
}
cursor = owned_end
probe += 1
}
}
let judged_count = judged_runs.length()
for run_identity in judged_runs {
let run_element = elements[run_identity]
let binding = format_surgery_run_binding(
bytes,
elements,
run_element,
"readback of '\{path}'",
) catch {
Unsupported(message~) => return Some(message)
error => raise error
}
let (prefix, extension_prefixes) = binding
let slice = bytes[run_element.byte_start:run_element.byte_end]
// A refusal during readback is itself a discrepancy: the run can no
// longer be judged, which is exactly what a readback must catch.
let verdict = verify_run_format(
slice,
prefix~,
extension_prefixes~,
format~,
) catch {
Unsupported(message~) => Some(message)
error => raise error
}
if verdict is Some(discrepancy) {
return Some(discrepancy)
}
}
if judged_count == 0 {
return Some("the requested spans of '\{path}' hold no run after the edit")
}
None
}
///|
/// The readback's PRESERVATION judgment: did formatting stay inside the
/// spans it was asked for?
///
/// The positive check cannot answer this. A run outside the union may
/// have carried the property all along, so presence proves nothing —
/// provenance does. The comparison is made PER PROJECTION UNIT rather
/// than per run: splitting changes which runs exist and how their
/// contributions are grouped, but it must never change which properties
/// apply to a given character. Every unit outside the requested spans
/// must therefore carry exactly the run properties it carried before,
/// and the runs that project no text at all (a note reference alone in
/// its run) must keep theirs too, compared in document order.
///
/// SCOPE: this judges the PARAGRAPH's own formatting — its runs, its
/// carriers, its mark. Formatting that lives outside the paragraph (a
/// table cell's `w:tcPr`, a style definition) is not compared here,
/// and does not need to be: a plan's declared byte edits bound what it
/// can touch, so anything outside them is preserved by the splice
/// itself rather than by this check.
///
/// `spans` are the paragraph-local ranges the plan was asked to format.
/// Returns None when preserved, or the first discrepancy.
pub fn docx_paragraph_format_preserved(
before : DocxAnnotatedResult,
before_story : DocxStoryPartSource,
after : DocxAnnotatedResult,
after_story : DocxStoryPartSource,
path~ : String,
spans~ : Array[(Int, Int)],
format~ : DocxDirectFormat,
) -> String? raise DocxError {
docx_paragraphs_format_preserved(
before,
before_story,
after,
after_story,
requests=[(path, spans)],
format~,
)[0]
}
///|
/// The same judgment for many paragraphs of one story, with each
/// document's path lookup built once for the whole batch. Answers are
/// returned in the order asked.
pub fn docx_paragraphs_format_preserved(
before : DocxAnnotatedResult,
before_story : DocxStoryPartSource,
after : DocxAnnotatedResult,
after_story : DocxStoryPartSource,
requests~ : Array[(String, Array[(Int, Int)])],
format~ : DocxDirectFormat,
) -> Array[String?] raise DocxError {
guard !requests.is_empty() else { return [] }
let before_part = before_story.part()
let after_part = after_story.part()
guard before.reader_projections.get(before_part) is Some(before_projection) &&
before.reader_projection_sources.get(before_part) is Some(before_bytes) else {
return requests.map(_ => {
Some("the source retained no projection for '\{before_part}'")
})
}
guard after.reader_projections.get(after_part) is Some(after_projection) &&
after.reader_projection_sources.get(after_part) is Some(after_bytes) else {
return requests.map(_ => {
Some("the re-read retained no projection for '\{after_part}'")
})
}
let before_index = docx_story_index(before_projection)
let after_index = docx_story_index(after_projection)
// ONE identity table for the whole batch: ids from the two documents
// are compared against each other, so they must be minted together.
let interner = DocxFormatInterner::new()
let answers : Array[String?] = []
for request in requests {
answers.push(
docx_paragraph_format_preserved_at(
before_projection,
before_bytes,
before_index,
after_projection,
after_bytes,
after_index,
request.0,
request.1,
format,
interner,
),
)
}
answers
}
///|
/// One paragraph's preservation check, against lookups already built.
fn docx_paragraph_format_preserved_at(
before_projection : ReaderProjection,
before_bytes : BytesView,
before_index : DocxStoryIndex,
after_projection : ReaderProjection,
after_bytes : BytesView,
after_index : DocxStoryIndex,
path : String,
spans : Array[(Int, Int)],
format : DocxDirectFormat,
interner : DocxFormatInterner,
) -> String? raise DocxError {
// Inside a span only the REQUESTED properties may differ: an
// omitted property means untouched, so a plan that dropped an
// unrelated one while setting bold must be caught even though the
// positive check passes and the projection is unchanged.
let touched = docx_format_touched_properties(format)
let filtered : Map[String, String] = Map([])
guard docx_format_paragraph_provenance(
before_projection,
before_bytes,
before_index,
path,
interner~,
)
is Some((original_units, original_width, original_silent, original_mark)) else {
return Some("the path '\{path}' names no single paragraph before the edit")
}
guard docx_format_paragraph_provenance(
after_projection,
after_bytes,
after_index,
path,
interner~,
)
is Some((result_units, result_width, result_silent, result_mark)) else {
return Some("the path '\{path}' names no single paragraph after the edit")
}
guard original_mark == result_mark else {
return Some(
"the paragraph mark of '\{path}' changed its formatting, though no span selected it",
)
}
guard original_width == result_width else {
return Some(
"'\{path}' projected \{original_width} unit(s) before the edit and \{result_width} after",
)
}
// The selection as sorted, coalesced INTERVALS, like the ownership:
// the comparison sweeps segment boundaries, so a paragraph allowed to
// be one enormous run costs its contributions, not its characters.
let selection : Array[(Int, Int)] = []
for span in spans {
let (from, to) = span
let start = if from < 0 { 0 } else { from }
let end = if to > original_width { original_width } else { to }
if end > start {
selection.push((start, end))
}
}
selection.sort_by(fn(left, right) { left.0.compare(right.0) })
let merged_selection : Array[(Int, Int)] = []
for span in selection {
match merged_selection.last() {
Some(last) if span.0 <= last.1 =>
if span.1 > last.1 {
merged_selection[merged_selection.length() - 1] = (last.0, span.1)
}
_ => merged_selection.push(span)
}
}
// The piecewise comparison: at every maximal segment on which the
// before-owner, after-owner, and selection are all constant, apply
// the same three judgments the per-unit loop made.
let mut cursor = 0
let mut before_at = 0
let mut after_at = 0
let mut selected_at = 0
let unowned : (String, String, String) = ("", "0", "0")
while cursor < original_width {
while before_at < original_units.length() &&
original_units[before_at].end <= cursor {
before_at += 1
}
while after_at < result_units.length() &&
result_units[after_at].end <= cursor {
after_at += 1
}
while selected_at < merged_selection.length() &&
merged_selection[selected_at].1 <= cursor {
selected_at += 1
}
let mut segment_end = original_width
let (original_properties, original_key, original_digest) = if before_at <
original_units.length() {
let owned = original_units[before_at]
if owned.start > cursor {
if owned.start < segment_end {
segment_end = owned.start
}
unowned
} else {
if owned.end < segment_end {
segment_end = owned.end
}
(owned.properties, owned.key, owned.digest)
}
} else {
unowned
}
let (result_properties, result_key, result_digest) = if after_at <
result_units.length() {
let owned = result_units[after_at]
if owned.start > cursor {
if owned.start < segment_end {
segment_end = owned.start
}
unowned
} else {
if owned.end < segment_end {
segment_end = owned.end
}
(owned.properties, owned.key, owned.digest)
}
} else {
unowned
}
let selected = if selected_at < merged_selection.length() {
let span = merged_selection[selected_at]
if span.0 > cursor {
if span.0 < segment_end {
segment_end = span.0
}
false
} else {
if span.1 < segment_end {
segment_end = span.1
}
true
}
} else {
false
}
let unit = cursor
// A unit's properties only mean what its namespace bindings say
// they mean: the same spelling under a rebound prefix is different
// formatting, and a faithful edit never disturbs it.
guard original_digest == result_digest else {
return Some(
"unit \{unit} of '\{path}' had its namespace bindings changed, so its properties may no longer mean what they did",
)
}
if selected {
// The properties the request does NOT name must survive. Filtered
// results are cached by their text: segments of one run share
// properties, and re-filtering them per segment would cost text
// times property bytes.
guard docx_format_filtered(
original_properties,
original_key,
touched,
filtered~,
interner~,
) ==
docx_format_filtered(
result_properties,
result_key,
touched,
filtered~,
interner~,
) else {
return Some(
"unit \{unit} of '\{path}' lost or gained a run property the request never named",
)
}
} else {
guard original_key == result_key else {
return Some(
"unit \{unit} of '\{path}' lies outside every requested span but its run properties changed",
)
}
}
cursor = segment_end
}
guard original_silent.length() == result_silent.length() else {
return Some(
"'\{path}' carried \{original_silent.length()} text-less run(s) before the edit and \{result_silent.length()} after",
)
}
for index in 0.. (Array[DocxFormatOwnedSpan], Int, Array[String], String)? raise DocxError {
let elements = projection.scan.elements()
let (target, found) = index.locate(path)
guard target >= 0 && found == 1 else { return None }
let paragraph = projection.paragraphs[target]
let SourceElementId(paragraph_head_identity) = paragraph.sources[0].source
let base = paragraph.projection_start
let width = paragraph.projection_end - base
// Ownership as INTERVALS, one per text contribution, in projection
// order: a paragraph is allowed to be one enormous run, and a table
// sized by its units would be sized by the text. A unit inside no
// interval — text the tolerant reader admits directly under the
// paragraph — has no properties to preserve, and the comparison
// treats the gap as saying so.
let units : Array[DocxFormatOwnedSpan] = []
// Namespace scopes and declaration tables, memoized per element: an
// ancestor's declarations are read once, and an element that
// declares nothing shares its parent's scope outright.
// Every element's subtree binding digest, computed in ONE pass.
let namespace_tokens : Map[Int, UInt] = Map([])
let binding_digests = docx_format_binding_digests(
bytes,
elements,
paragraph_head_identity,
tokens=namespace_tokens,
interner~,
)
// A run's properties, read ONCE per run: recomputing them for every
// contribution walks its children again and again, and a run of many
// small text elements is legal.
let properties_by_run : Map[Int, String] = Map([])
let digests_by_run : Map[Int, String] = Map([])
let keys_by_run : Map[Int, String] = Map([])
for contribution in paragraph.contributions {
guard contribution.kind is ProjectedText(_) else { continue }
guard contribution.run_source is Some(run_source) else { continue }
let SourceElementId(run_identity) = run_source
let properties = match properties_by_run.get(run_identity) {
Some(known) => known
None => {
let read = docx_format_run_properties(
bytes,
elements,
elements[run_identity],
)
properties_by_run[run_identity] = read
read
}
}
// The bindings this run's own properties depend on: two runs may
// each bind the same prefix to a different vocabulary, so the
// digest belongs to the unit, not to the paragraph.
// A small key for these properties, computed ONCE per run: the
// comparisons below are made per UNIT, and hashing the whole
// property text apiece would cost the run's length times its size.
let properties_key = match keys_by_run.get(run_identity) {
Some(known) => known
None => {
let read = interner.id(properties)
keys_by_run[run_identity] = read
read
}
}
// Rooted at the PROPERTIES, not the whole run: splitting
// legitimately adds `xml:space` to a text element, and a digest
// that reached the text would call that a change of meaning.
let digest = match digests_by_run.get(run_identity) {
Some(known) => known
None => {
let mut properties_identity = -1
let mut child = elements[run_identity].first_child_index
while child >= 0 {
let entry = elements[child]
if is_wml_uri(entry.uri) && entry.local_name == "rPr" {
properties_identity = entry.identity
}
child = entry.next_sibling_index
}
// Absent properties and properties that depend on no
// extension binding say the same thing, so both read as the
// empty digest.
let read = if properties_identity >= 0 {
"\{binding_digests.get(properties_identity).unwrap_or(0)}"
} else {
"0"
}
digests_by_run[run_identity] = read
read
}
}
let from = contribution.projection_start - base
let to = contribution.projection_end - base
if to > from && from >= 0 && to <= width {
units.push({
start: from,
end: to,
properties,
key: properties_key,
digest,
})
}
}
units.sort_by(fn(left, right) { left.start.compare(right.start) })
// Which runs project text, indexed once: scanning every contribution
// per run is quadratic, and a paragraph of many small runs is legal.
let projecting : Map[Int, Bool] = Map([])
for contribution in paragraph.contributions {
guard contribution.kind is ProjectedText(_) else { continue }
guard contribution.projection_end > contribution.projection_start else {
continue
}
guard contribution.run_source is Some(SourceElementId(identity)) else {
continue
}
projecting[identity] = true
}
// Where each run sits, in projection units — including the zero-width
// contributions a text-less run makes, so every run has a position.
// Run signatures are BOUNDED and computed once each: a run may
// contain a large subtree, and every carrier inside it would
// otherwise re-read and re-store that whole text.
let signatures : Map[Int, String] = Map([])
let keys : Map[Int, String] = Map([])
let run_offsets : Map[Int, Int] = Map([])
for contribution in paragraph.contributions {
guard contribution.run_source is Some(SourceElementId(owner)) else {
continue
}
let offset = contribution.projection_start - base
match run_offsets.get(owner) {
Some(known) => if offset < known { run_offsets[owner] = offset }
None => run_offsets[owner] = offset
}
}
// The paragraphs the reader registered — only these answer for their
// own carriers — come from the story index, because deriving them
// here would cost a pass over every paragraph in the document for
// every paragraph judged.
let registered = index.registered
// What formatting survives outside the per-unit comparison, bound to
// WHAT IT FORMATS rather than to its position in a list. A carrier's
// properties alone cannot tell that italic MOVED from a footnote
// marker to an endnote marker — the ordered strings would match —
// so every entry pairs an owner signature with its properties, and a
// run with no properties still occupies a slot.
//
// Formatting carriers are not only runs: `w:pPr`, `w:sdtPr` and
// `w:sdtEndPr` hold run properties too, and enumerating the carrier
// ELEMENT rather than a list of known container kinds is what keeps
// this closed against a container nobody has heard of.
let silent : Array[String] = []
let physical_runs : Array[Int] = []
docx_format_collect_named(
elements,
paragraph_head_identity,
"r",
physical_runs,
registered~,
)
let run_carriers : Map[Int, Bool] = Map([])
for run_identity in physical_runs {
// A run carrying projected units is compared per unit, with the
// request's authorization; a WEIGHTLESS run (properties and empty
// text only) is the shell a split legitimately re-homes.
let mut child = elements[run_identity].first_child_index
while child >= 0 {
let entry = elements[child]
if is_wml_uri(entry.uri) && entry.local_name == "rPr" {
run_carriers[entry.identity] = true
}
child = entry.next_sibling_index
}
if projecting.get(run_identity) == Some(true) {
continue
}
if !docx_format_run_carries_content(elements, run_identity) {
continue
}
let signature = docx_format_run_signature_key(
bytes,
elements,
run_identity,
signatures~,
interner~,
)
let properties = docx_format_run_properties(
bytes,
elements,
elements[run_identity],
)
silent.push(
"\{signature}\u{1}\{properties}\u{1}\{binding_digests.get(run_identity).unwrap_or(0)}",
)
}
// Carriers that belong to no run at all: `w:pPr`, `w:sdtPr`,
// `w:sdtEndPr`, or any container this planner has never seen.
let carriers : Array[Int] = []
docx_format_collect_named(
elements,
paragraph_head_identity,
"rPr",
carriers,
registered~,
)
for carrier_identity in carriers {
guard run_carriers.get(carrier_identity) is None else { continue }
let entry = elements[carrier_identity]
// A STRUCTURAL path, not just the container's name: two content
// controls both own an `sdtEndPr`, and end-character formatting
// moving from one to the other must not look like no change at
// all. Splitting never renumbers these ancestors — only runs — so
// the path is stable across a faithful edit.
let owner_path = docx_format_carrier_key(
bytes,
elements,
entry.parent_index,
paragraph_head_identity,
run_offsets~,
signatures~,
keys~,
namespace_tokens~,
interner~,
)
silent.push(
"\{owner_path}\u{1}\{interner.id(format_surgery_decode(bytes[entry.byte_start:entry.byte_end]))}\u{1}\{binding_digests.get(carrier_identity).unwrap_or(0)}",
)
}
// Every pPr in the paragraph's physical subtree, in document order:
// the reader PROMOTES an `mc:AlternateContent` branch's children
// into the logical paragraph, so properties can sit a level down
// and still be the paragraph's own. The WHOLE element is compared —
// alignment, spacing, numbering, and the mark's own rPr alike —
// because no v1 request touches any of it.
let marks : Array[Int] = []
docx_format_collect_named(
elements,
paragraph_head_identity,
"pPr",
marks,
registered~,
)
let mark_builder = StringBuilder()
for mark_identity in marks {
let entry = elements[mark_identity]
// Bound to WHERE it sits: an identical `pPr` moved from an
// mc:Choice into the Fallback changes which one applies, and a
// bare concatenation could not tell.
mark_builder.write_string("|")
mark_builder.write_string(
docx_format_carrier_key(
bytes,
elements,
mark_identity,
paragraph_head_identity,
run_offsets~,
signatures~,
keys~,
namespace_tokens~,
interner~,
),
)
mark_builder.write_string("=")
mark_builder.write_string(
interner.id(format_surgery_decode(bytes[entry.byte_start:entry.byte_end])),
)
mark_builder.write_string("~")
mark_builder.write_string(
"\{binding_digests.get(mark_identity).unwrap_or(0)}",
)
}
let mark = mark_builder.to_string()
Some((units, width, silent, mark))
}
///|
/// A run's properties as spelled: EVERY direct `rPr` child's bytes,
/// joined. Duplicates are a refusal at planning time, but a readback
/// must still see a change in any one of them rather than the last.
fn docx_format_run_properties(
bytes : BytesView,
elements : Array[ScannedElement],
run_element : ScannedElement,
) -> String raise DocxError {
let builder = StringBuilder()
let mut child = run_element.first_child_index
while child >= 0 {
let entry = elements[child]
if is_wml_uri(entry.uri) && entry.local_name == "rPr" {
builder.write_string(
format_surgery_decode(bytes[entry.byte_start:entry.byte_end]),
)
}
child = entry.next_sibling_index
}
builder.to_string()
}
///|
/// The rPr child names a request touches — the ONLY ones that may
/// differ inside a selected span.
fn docx_format_touched_properties(format : DocxDirectFormat) -> Array[String] {
let touched : Array[String] = []
if format.bold() is Some(_) {
touched.push("b")
touched.push("bCs")
}
if format.italic() is Some(_) {
touched.push("i")
touched.push("iCs")
}
if format.underline() is Some(_) {
touched.push("u")
}
if format.color() is Some(_) {
touched.push("color")
}
touched
}
///|
/// One run's properties with the touched ones removed, as a comparable
/// string: the `rPr` shell and every child the request does NOT name
/// survive verbatim, so a difference anywhere else is still a
/// difference.
fn docx_format_without(
properties : String,
touched : Array[String],
) -> String raise DocxError {
guard properties != "" else { return "" }
let bytes = @utf8.encode(properties)
docx_format_filter_region(bytes, 0, bytes.length(), touched)
}
///|
/// Filter one region: text survives, an `rPr` shell is descended into,
/// and any other element is dropped exactly when the request names it.
fn docx_format_filter_region(
bytes : BytesView,
from : Int,
to : Int,
touched : Array[String],
) -> String raise DocxError {
let builder = StringBuilder()
let mut at = from
while at < to {
if bytes[at] != b'<' {
builder.write_string(format_surgery_decode(bytes[at:at + 1]))
at += 1
continue
}
let name_start = at + 1
let mut name_end = name_start
while name_end < to &&
bytes[name_end] != b'>' &&
bytes[name_end] != b'/' &&
!is_xml_ws(bytes[name_end]) {
name_end += 1
}
let qname = format_surgery_decode(bytes[name_start:name_end])
let (_, property_name) = split_qname(qname)
// The open tag ends at the first '>' outside a quoted value.
let mut cursor = name_end
let mut quote = b'\x00'
while cursor < to {
let byte = bytes[cursor]
if quote != b'\x00' {
if byte == quote {
quote = b'\x00'
}
} else if byte == b'"' || byte == b'\'' {
quote = byte
} else if byte == b'>' {
break
}
cursor += 1
}
guard cursor < to else {
// Unparseable: keep the remainder verbatim rather than lose it.
builder.write_string(format_surgery_decode(bytes[at:to]))
return builder.to_string()
}
let open_end = cursor + 1
let self_closing = bytes[cursor - 1] == b'/'
if self_closing {
if property_name == "rPr" {
// `` and an rPr the filter empties say the same thing;
// only its ATTRIBUTES distinguish it from no rPr at all.
builder.write_string(docx_format_shell(bytes, name_end, cursor - 1, ""))
} else if touched.contains(property_name) {
builder.write_string(
docx_format_touched_residue(
bytes,
qname,
property_name,
name_end,
cursor - 1,
),
)
} else {
builder.write_string(format_surgery_decode(bytes[at:open_end]))
}
at = open_end
continue
}
// Paired element: find its matching close tag by depth over its own
// qualified name.
let close_marker = "', and a
// LONGER name that merely starts with this one is a different
// element.
if docx_format_matches_at(bytes, probe, close_marker) &&
docx_format_name_ends_at(bytes, probe + close_marker.length(), to) {
depth -= 1
if depth == 0 {
content_end = probe
break
}
} else if docx_format_matches_at(bytes, probe, open_marker) &&
docx_format_name_ends_at(bytes, probe + open_marker.length(), to) {
depth += 1
}
}
probe += 1
}
guard content_end >= 0 else {
builder.write_string(format_surgery_decode(bytes[at:to]))
return builder.to_string()
}
// The close tag runs to its own '>', whitespace included.
let mut close_cursor = content_end + close_marker.length()
while close_cursor < to && bytes[close_cursor] != b'>' {
close_cursor += 1
}
let element_end = close_cursor + 1
if property_name == "rPr" {
// An rPr holding nothing but touched properties says the same as
// no rPr at all — otherwise a run that GAINED its first property
// would read as a change to properties nobody named. Its
// ATTRIBUTES are not part of that equivalence: they survive, so
// an unrelated change to them is still a change.
let remaining = docx_format_filter_region(
bytes, open_end, content_end, touched,
)
builder.write_string(
docx_format_shell(
bytes,
name_end,
open_end - 1,
remaining.trim(chars=" \t\n\r").to_owned(),
),
)
} else if touched.contains(property_name) {
// A property the request names may change the attributes the
// request AUTHORIZES and nothing else; its other attributes and
// any content are compared exactly.
builder.write_string(
docx_format_touched_residue(
bytes,
qname,
property_name,
name_end,
open_end - 1,
),
)
builder.write_string(
docx_format_filter_region(bytes, open_end, content_end, touched),
)
} else {
builder.write_string(format_surgery_decode(bytes[at:element_end]))
}
at = element_end
}
builder.to_string()
}
///|
fn docx_format_matches_at(bytes : BytesView, at : Int, needle : String) -> Bool {
let units = needle.code_units()
if at + units.length() > bytes.length() {
return false
}
for index in 0.. String raise DocxError {
let attributes = if attributes_to > attributes_from {
format_surgery_decode(bytes[attributes_from:attributes_to])
.trim(chars=" \t\n\r")
.to_owned()
} else {
""
}
if attributes == "" && children == "" {
return ""
}
"\{children}"
}
///|
/// Whether a name ends at this offset — the next byte may not continue
/// an XML name, so ` Bool {
if at >= to {
return true
}
let byte = bytes[at]
!((byte >= b'a' && byte <= b'z') ||
(byte >= b'A' && byte <= b'Z') ||
(byte >= b'0' && byte <= b'9') ||
byte == b'_' ||
byte == b'-' ||
byte == b'.' ||
byte == b':')
}
///|
/// What survives of a property the request NAMES: its attributes other
/// than the ones the request authorizes it to change. An element left
/// with none says the same as an absent one, so adding a property is
/// not mistaken for changing something nobody named — while a `w:u`
/// keeping its colour, or a `w:color` keeping an unrelated attribute,
/// still compares exactly.
fn docx_format_touched_residue(
bytes : BytesView,
qname : String,
property_name : String,
from : Int,
to : Int,
) -> String raise DocxError {
// The attributes a request may rewrite: an on/off or underline
// property owns its `val`; an absolute colour additionally drops the
// theme linkage that would contradict it.
let authorized = if property_name == "color" {
["val", "themeColor", "themeTint", "themeShade"]
} else {
["val"]
}
let kept = StringBuilder()
let mut at = from
while at < to {
if is_xml_ws(bytes[at]) {
at += 1
continue
}
if bytes[at] == b'/' {
at += 1
continue
}
let name_start = at
while at < to && bytes[at] != b'=' && !is_xml_ws(bytes[at]) {
at += 1
}
let attribute = format_surgery_decode(bytes[name_start:at])
while at < to && bytes[at] != b'"' && bytes[at] != b'\'' {
at += 1
}
guard at < to else { break }
let quote = bytes[at]
at += 1
let value_start = at
while at < to && bytes[at] != quote {
at += 1
}
let value = format_surgery_decode(bytes[value_start:at])
at += 1
let (_, attribute_local) = split_qname(attribute)
if !authorized.contains(attribute_local) {
kept.write_string(" \{attribute}=\"\{value}\"")
}
}
let residue = kept.to_string()
if residue == "" {
""
} else {
"<\{qname}\{residue}>"
}
}
///|
/// Every WML element with this local name in a paragraph's physical
/// subtree, in document order, without descending into a nested `w:p`
/// — that paragraph answers for its own.
fn docx_format_collect_named(
elements : Array[ScannedElement],
element_identity : Int,
local_name : String,
out : Array[Int],
registered~ : Map[Int, Bool],
) -> Unit {
let mut child = elements[element_identity].first_child_index
while child >= 0 {
let entry = elements[child]
// A nested paragraph answers for its own carriers only if the
// reader REGISTERED it. One inside a suppressed container never
// becomes a logical paragraph, so nobody else would look.
if is_wml_uri(entry.uri) &&
entry.local_name == "p" &&
registered.get(entry.identity) == Some(true) {
child = entry.next_sibling_index
continue
}
if is_wml_uri(entry.uri) && entry.local_name == local_name {
out.push(entry.identity)
}
docx_format_collect_named(
elements,
entry.identity,
local_name,
out,
registered~,
)
child = entry.next_sibling_index
}
}
///|
/// The positive check over ONE span — the batched judgment applied to
/// a single range.
pub fn docx_paragraph_direct_format(
annotated : DocxAnnotatedResult,
story : DocxStoryPartSource,
path~ : String,
start~ : Int,
end~ : Int,
format~ : DocxDirectFormat,
) -> String? raise DocxError {
docx_paragraph_direct_format_spans(
annotated,
story,
path~,
spans=[(start, end)],
format~,
)
}
///|
/// Whether a run carries anything at all: a run holding only properties
/// and EMPTY text elements is the weightless shell a split legitimately
/// re-homes, and nothing about it is worth comparing.
fn docx_format_run_carries_content(
elements : Array[ScannedElement],
run_identity : Int,
) -> Bool {
let mut child = elements[run_identity].first_child_index
while child >= 0 {
let entry = elements[child]
let is_properties = is_wml_uri(entry.uri) && entry.local_name == "rPr"
let is_empty_text = is_wml_uri(entry.uri) &&
entry.local_name == "t" &&
entry.content_end <= entry.content_start
if !is_properties && !is_empty_text {
return true
}
child = entry.next_sibling_index
}
false
}
///|
/// What a run FORMATS, as a signature: its content with its properties
/// removed. Two text-less runs holding different markers have
/// different signatures, so formatting cannot move between them
/// unnoticed.
fn docx_format_run_signature(
bytes : BytesView,
elements : Array[ScannedElement],
run_identity : Int,
) -> String raise DocxError {
let builder = StringBuilder()
let mut child = elements[run_identity].first_child_index
while child >= 0 {
let entry = elements[child]
if !(is_wml_uri(entry.uri) && entry.local_name == "rPr") {
builder.write_string(
format_surgery_decode(bytes[entry.byte_start:entry.byte_end]),
)
}
child = entry.next_sibling_index
}
builder.to_string()
}
///|
/// A carrier's key within the paragraph, derived INCREMENTALLY from
/// its parent's key and its own step, and memoized per element. Each
/// step is namespace-QUALIFIED (a foreign `sdtEndPr` is not the WML
/// one), and a RUN step is keyed by where it sits and what it holds
/// rather than by its ordinal — splitting renumbers runs, and a
/// carrier nested inside one must survive that unchanged.
///
/// No ancestor path is ever materialized: a paragraph may hold many
/// carriers under a deep chain, each with a different immediate owner,
/// and building a path apiece would put the depth back into the cost.
fn docx_format_carrier_key(
bytes : BytesView,
elements : Array[ScannedElement],
element_identity : Int,
stop_identity : Int,
run_offsets~ : Map[Int, Int],
signatures~ : Map[Int, String],
keys~ : Map[Int, String],
namespace_tokens~ : Map[Int, UInt],
interner~ : DocxFormatInterner,
) -> String raise DocxError {
if element_identity < 0 ||
element_identity >= elements.length() ||
element_identity == stop_identity {
return ""
}
match keys.get(element_identity) {
Some(known) => known
None => {
let entry = elements[element_identity]
let step = if is_wml_uri(entry.uri) && entry.local_name == "r" {
let offset = run_offsets.get(element_identity).unwrap_or(-1)
let signature = docx_format_run_signature_key(
bytes,
elements,
element_identity,
signatures~,
interner~,
)
"r@\{offset}#{\{signature}}"
} else {
"\{namespace_tokens.get(element_identity).unwrap_or(0)}:\{entry.local_name}[\{entry.same_name_ordinal}]"
}
let parent = docx_format_carrier_key(
bytes,
elements,
entry.parent_index,
stop_identity,
run_offsets~,
signatures~,
keys~,
namespace_tokens~,
interner~,
)
let key = interner.id("\{parent}/\{step}")
keys[element_identity] = key
key
}
}
}
///|
/// Dense identities for texts, EXACT by construction.
///
/// The comparisons this file makes are equality comparisons, and a
/// digest answers them only up to its collisions — a 32-bit one is
/// searchable, and two twelve-character font names that collide are a
/// candidate whose unrequested change the preservation check would call
/// preserved. Interning costs the same pass over the text a digest
/// would, and two ids are equal exactly when the texts are.
///
/// The entries themselves stay small, which is what the digest was for:
/// a unit's entry holds an id rather than the property text, so an
/// array of them grows with the units and not with their product.
priv struct DocxFormatInterner {
ids : Map[String, Int]
}
///|
fn DocxFormatInterner::new() -> DocxFormatInterner {
{ ids: Map([]), }
}
///|
fn DocxFormatInterner::uid(self : DocxFormatInterner, text : String) -> UInt {
match self.ids.get(text) {
Some(known) => known.reinterpret_as_uint()
None => {
let id = self.ids.length() + 1
self.ids[text] = id
id.reinterpret_as_uint()
}
}
}
///|
fn DocxFormatInterner::id(self : DocxFormatInterner, text : String) -> String {
match self.ids.get(text) {
Some(known) => "\{known}"
None => {
// Ids start at 1: "0" is the SENTINEL for a unit no run claims,
// and the first real property text must not compare equal to it.
let id = self.ids.length() + 1
self.ids[text] = id
"\{id}"
}
}
}
///|
/// A BOUNDED key for a run's content signature: its length and a
/// fingerprint, computed once per run. The signature itself can be the
/// whole of a large subtree, and a paragraph may hold many carriers
/// inside one such run — storing the text in every entry would grow
/// with their product rather than with the document.
fn docx_format_run_signature_key(
bytes : BytesView,
elements : Array[ScannedElement],
run_identity : Int,
signatures~ : Map[Int, String],
interner~ : DocxFormatInterner,
) -> String raise DocxError {
match signatures.get(run_identity) {
Some(known) => known
None => {
let signature = docx_format_run_signature(bytes, elements, run_identity)
let key = interner.id(signature)
signatures[run_identity] = key
key
}
}
}
///|
/// `docx_format_without`, memoized by the properties text: a run's
/// units all carry the same properties, and filtering them once per
/// unit would cost the text's length times the property bytes.
fn docx_format_filtered(
properties : String,
properties_key : String,
touched : Array[String],
filtered~ : Map[String, String],
interner~ : DocxFormatInterner,
) -> String raise DocxError {
// Keyed by the properties' own small fingerprint: keying by the text
// would hash every byte of it on each lookup.
match filtered.get(properties_key) {
Some(known) => known
None => {
let result = interner.id(docx_format_without(properties, touched))
filtered[properties_key] = result
result
}
}
}
///|
/// Every element's SUBTREE binding digest, computed in one pass.
///
/// A property's meaning depends on the namespace bindings in scope
/// where it sits, and a carrier must be compared together with them.
/// Resolving prefixes per carrier — or materializing a scope map per
/// element, or a prefix set per subtree — costs depth times breadth on
/// documents the reader accepts. So the scope is carried down a single
/// depth-first walk with an undo log, each element's own
/// prefix-to-URI pairs are folded into an order-independent sum, and a
/// subtree's digest is its own pairs plus its children's. Every
/// carrier then reads its digest in one lookup.
///
/// Prefixes resolving to WML are left out: the request writes WML and
/// the rPr engine vouches for that binding, so recording it would make
/// a run that GAINED its first property look like a change of meaning.
fn docx_format_binding_digests(
bytes : BytesView,
elements : Array[ScannedElement],
root_identity : Int,
tokens~ : Map[Int, UInt],
interner~ : DocxFormatInterner,
) -> Map[Int, UInt] raise DocxError {
let digests : Map[Int, UInt] = Map([])
let scope : Map[String, String] = Map([])
// Each binding's identity, interned ONCE when it is declared: a long
// URI used by many descendants would otherwise be re-read per use.
// These are EXACT — equal ids mean equal prefix=uri pairs — where the
// folded hash they replace answered equality only up to collisions,
// and a 32-bit collision between two bindings is searchable.
let scope_hash : Map[String, UInt] = Map([])
fn binding_hash(prefix : String, uri : String) -> UInt {
interner.uid("b|\{prefix}=\{uri}")
}
fn walk(identity : Int) -> UInt raise DocxError {
let element = elements[identity]
// Declarations on this element, parsed in ONE pass over its tag,
// applied to the scope with an undo record.
let undo : Array[(String, String?, UInt?)] = []
let used : Array[String] = []
// Attributes whose VALUES may carry prefixes: markup-compatibility
// directives name namespaces and elements by QName, so a prefix can
// be load-bearing without appearing in any element or attribute
// NAME. They are resolved after the whole tag is read, because a
// declaration may follow the directive within the same tag.
let directives : Array[(String, String, String)] = []
let stop = run_surgery_open_tag_end(element)
let mut at = element.byte_start + 1
let name_start = at
while at < stop &&
bytes[at] != b'>' &&
bytes[at] != b'/' &&
!is_xml_ws(bytes[at]) {
at += 1
}
let (element_prefix, _) = split_qname(
format_surgery_decode(bytes[name_start:at]),
)
used.push(element_prefix)
while at < stop {
if is_xml_ws(bytes[at]) || bytes[at] == b'/' {
at += 1
continue
}
if bytes[at] == b'>' {
break
}
let attribute_start = at
while at < stop && bytes[at] != b'=' && !is_xml_ws(bytes[at]) {
at += 1
}
let attribute = format_surgery_decode(bytes[attribute_start:at])
while at < stop && bytes[at] != b'"' && bytes[at] != b'\'' {
at += 1
}
if at >= stop {
break
}
let quote = bytes[at]
at += 1
let value_start = at
while at < stop && bytes[at] != quote {
at += 1
}
// Entity-spelled bindings and directives mean what they decode to.
let value = decode_entities(format_surgery_decode(bytes[value_start:at]))
at += 1
if attribute == "xmlns" {
undo.push(("", scope.get(""), scope_hash.get("")))
scope[""] = value
scope_hash[""] = if is_wml_uri(value) {
0
} else {
binding_hash("", value)
}
} else if attribute.has_prefix("xmlns:") {
let declared = attribute[6:].to_owned()
undo.push((declared, scope.get(declared), scope_hash.get(declared)))
scope[declared] = value
scope_hash[declared] = if is_wml_uri(value) {
0
} else {
binding_hash(declared, value)
}
} else {
let (attribute_prefix, attribute_local) = split_qname(attribute)
used.push(attribute_prefix)
if attribute_local
is ("Requires"
| "Ignorable"
| "MustUnderstand"
| "ProcessContent"
| "PreserveElements"
| "PreserveAttributes") {
directives.push((attribute_prefix, attribute_local, value))
}
}
}
// A directive counts when its own name is in the MC namespace, or —
// the spelling the spec gives `Requires` — when it sits unprefixed
// on an MC element.
for directive in directives {
let (attribute_prefix, attribute_local, value) = directive
let is_mc = scope.get(attribute_prefix) == Some(MC_URI) ||
(attribute_prefix == "" && element.uri == MC_URI)
guard is_mc else { continue }
let listed_prefixes = attribute_local
is ("Requires" | "Ignorable" | "MustUnderstand")
let mut token_start = -1
for offset in 0..<=value.length() {
let boundary = offset == value.length() ||
value[offset] is (' ' | '\t' | '\n' | '\r')
if boundary {
if token_start >= 0 {
let token = value[token_start:offset]
if listed_prefixes {
used.push(token.to_owned())
} else {
match token.find(":") {
Some(colon) => used.push(token[:colon].to_owned())
None => used.push("")
}
}
token_start = -1
}
} else if token_start < 0 {
token_start = offset
}
}
}
// This element's own contribution: the ids of the NON-WML bindings
// its own names depend on, in document order. WML uses are omitted
// rather than recorded as zeros, so that a surgery which adds a
// pure-WML property to a subtree — the one thing a faithful format
// edit inserts — leaves the digest of that subtree what it was.
let own_builder = StringBuilder()
for prefix in used {
// Declared bindings answer from their interned id; only the
// element's own fallback is interned here, once per element.
let contribution = match scope_hash.get(prefix) {
Some(known) => known
None =>
if prefix == "xml" {
0
} else {
let uri = if prefix == element_prefix { element.uri } else { "?" }
if is_wml_uri(uri) {
0
} else {
binding_hash(prefix, uri)
}
}
}
if contribution != 0 {
own_builder.write_string("\{contribution},")
}
}
// The element's own namespace, as a BOUNDED token: a structural
// key that embedded the URI would record it once per element that
// uses it.
tokens[identity] = scope_hash.get(element_prefix).unwrap_or(0)
// The subtree's digest is an interned token over the element's own
// contribution and its children's tokens IN ORDER, with the
// all-WML token 0 omitted on both sides so a pure-WML subtree — and
// an absent one — read as 0 exactly. Equal tokens mean equal
// sequences of foreign-binding uses; the sum this replaces could
// cancel.
let children_builder = StringBuilder()
let mut child = element.first_child_index
while child >= 0 {
let token = walk(child)
if token != 0 {
children_builder.write_string("\{token},")
}
child = elements[child].next_sibling_index
}
let own_part = own_builder.to_string()
let children_part = children_builder.to_string()
let total : UInt = if own_part == "" && children_part == "" {
0
} else {
interner.uid("s|\{own_part}/\{children_part}")
}
digests[identity] = total
for entry in undo {
// The shadowed binding's HASH is restored with it: recomputing it
// would hash a long ancestor URI once per child that shadowed it.
match entry.1 {
Some(previous) => {
scope[entry.0] = previous
match entry.2 {
Some(previous_hash) => scope_hash[entry.0] = previous_hash
None => scope_hash.remove(entry.0)
}
}
None => {
scope.remove(entry.0)
scope_hash.remove(entry.0)
}
}
}
total
}
// The scope above the paragraph matters too, so the walk starts at
// the story root and records digests for everything beneath it.
let mut ancestor = root_identity
let chain : Array[Int] = []
while ancestor >= 0 && ancestor < elements.length() {
chain.push(ancestor)
ancestor = elements[ancestor].parent_index
}
let mut index = chain.length() - 1
while index > 0 {
let element = elements[chain[index]]
let stop = run_surgery_open_tag_end(element)
let mut at = element.byte_start + 1
while at < stop &&
bytes[at] != b'>' &&
bytes[at] != b'/' &&
!is_xml_ws(bytes[at]) {
at += 1
}
while at < stop {
if is_xml_ws(bytes[at]) || bytes[at] == b'/' {
at += 1
continue
}
if bytes[at] == b'>' {
break
}
let attribute_start = at
while at < stop && bytes[at] != b'=' && !is_xml_ws(bytes[at]) {
at += 1
}
let attribute = format_surgery_decode(bytes[attribute_start:at])
while at < stop && bytes[at] != b'"' && bytes[at] != b'\'' {
at += 1
}
if at >= stop {
break
}
let quote = bytes[at]
at += 1
let value_start = at
while at < stop && bytes[at] != quote {
at += 1
}
// Entity-spelled bindings and directives mean what they decode to.
let value = decode_entities(format_surgery_decode(bytes[value_start:at]))
at += 1
if attribute == "xmlns" {
scope[""] = value
scope_hash[""] = if is_wml_uri(value) {
0
} else {
binding_hash("", value)
}
} else if attribute.has_prefix("xmlns:") {
let declared = attribute[6:].to_owned()
scope[declared] = value
scope_hash[declared] = if is_wml_uri(value) {
0
} else {
binding_hash(declared, value)
}
}
}
index -= 1
}
walk(root_identity) |> ignore
digests
}