xml

const NS: {
  /** Bound to the `xml:` prefix implicitly; never declared. */
  readonly xml: "http://www.w3.org/XML/1998/namespace";
  /** The namespace of `xmlns` declarations themselves. */
  readonly xmlns: "http://www.w3.org/2000/xmlns/";
  /** Markup Compatibility and Extensibility (`mc:`). */
  readonly mc: "http://schemas.openxmlformats.org/markup-compatibility/2006";
  /** DrawingML main (`a:`). */
  readonly a: "http://schemas.openxmlformats.org/drawingml/2006/main";
  /** PresentationML main (`p:`). */
  readonly p: "http://schemas.openxmlformats.org/presentationml/2006/main";
  /** Relationship references inside part XML (`r:`). */
  readonly r: "http://schemas.openxmlformats.org/officeDocument/2006/relationships";
};

type NamespacePrefix = keyof typeof NS;

type NamespaceUri = (typeof NS)[NamespacePrefix];

const XML_SPACE_PRESERVE = "preserve";

const XML_ERROR_CODES: readonly ["ERR_DOCTYPE_FORBIDDEN", "ERR_MALFORMED_XML", "ERR_MISMATCHED_TAG", "ERR_UNCLOSED_TAG", "ERR_ROOT_ELEMENT", "ERR_DUPLICATE_ATTRIBUTE", "ERR_UNKNOWN_ENTITY", "ERR_INVALID_CHARACTER", "ERR_UNSUPPORTED_ENCODING", "ERR_LIMIT_EXCEEDED", "ERR_INVALID_MCE", "ERR_SCHEMA_ORDER", "ERR_INVALID_EDIT"];

type XmlErrorCode = (typeof XML_ERROR_CODES)[number];

interface XmlErrorDetail {
  /** Offset into the decoded source, in UTF-16 code units, when positional. */
  readonly offset?: number;
  /**
   * The element, attribute or entity name the failure is attributable to.
   *
   * Explicitly nullable rather than merely optional: under
   * `exactOptionalPropertyTypes` a caller that has a `string | undefined` in
   * hand cannot pass it to an optional-only field, and every caller here does.
   */
  readonly name?: string | undefined;
  /** The limit that was exceeded. */
  readonly limit?: number;
  /** The value that exceeded it. */
  readonly actual?: number;
  /** Whatever a dependency threw, preserved rather than swallowed. */
  readonly cause?: unknown;
}

class XmlError extends Error {
  readonly code: XmlErrorCode;
  readonly detail: XmlErrorDetail;
  constructor(code: XmlErrorCode, message: string, detail?: XmlErrorDetail);
}

function isXmlError(value: unknown): value is XmlError;

function positionOf(source: string, offset: number): {
  line: number;
  column: number;
};

function isXmlWhitespace(code: number): boolean;

function isNameStartChar(code: number): boolean;

function isNameChar(code: number): boolean;

function isXmlChar(code: number): boolean;

function isUnpairedSurrogate(source: string, index: number): boolean;

function isXmlCodePoint(code: number): boolean;

function normalizeLineEndings(text: string): string;

function isAllWhitespace(source: string, start: number, end: number): boolean;

type XmlEncoding = 'utf-8';

interface XmlSource {
  /**
   * The decoded document, **including a leading U+FEFF if the bytes carried a
   * byte order mark**. Every span in the tree indexes into this string.
   */
  readonly text: string;
  readonly encoding: XmlEncoding;
  /** True if `text` begins with U+FEFF because the bytes began with EF BB BF. */
  readonly bom: boolean;
  /** Length of the original byte sequence, for diagnostics and budgeting. */
  readonly byteLength: number;
}

function decodeXmlSource(bytes: Uint8Array): XmlSource;

function encodeXmlSource(text: string): Uint8Array;

function decodeReference(source: string, start: number, end?: number): {
  readonly text: string;
  readonly end: number;
};

function decodeCharacterData(source: string, start: number, end: number): string;

function normalizeAttributeValue(source: string, start: number, end: number): string;

function isLiteralRun(source: string, start: number, end: number, attribute: boolean): boolean;

function escapeText(value: string, at?: number): string;

function escapeAttributeValue(value: string, quote: '"' | "'", at?: number): string;

type XmlTokenType = 'declaration' | 'processingInstruction' | 'comment' | 'startTag' | 'emptyElementTag' | 'endTag' | 'text' | 'cdata';

interface XAttribute {
  qname: string;
  /** Empty string when the name is unprefixed. */
  prefix: string;
  local: string;
  /**
   * Start of this attribute's **leading whitespace**, not of its name.
   *
   * Including the whitespace is what lets sub-phase 0.6 rewrite one attribute
   * of a tag and leave the spacing of the others alone. Office's own writer is
   * consistent, but 70 822 of the 98 777 self-closing tags in our corpus come
   * from a producer that writes `<a:off x="0" y="0" />` with a space before the
   * slash, so "the spacing is always the same" is false in practice.
   */
  readonly start: number;
  readonly nameStart: number;
  readonly nameEnd: number;
  /** First character inside the opening quote. */
  readonly valueStart: number;
  /** The closing quote. */
  readonly valueEnd: number;
  /** One past the closing quote. */
  readonly end: number;
  quote: '"' | "'";
  /**
   * Normalized per XML 1.0 §3.3.3.
   *
   * Deliberately not the same string as `source.slice(valueStart, valueEnd)`.
   * `name="a&#9;b"` and `name="a<TAB>b"` have the same normalized value only if
   * you get §3.3.3 wrong: a literal tab becomes a space, a character reference
   * to a tab stays a tab.
   */
  value: string;
  /**
   * Set by `markAttributeDirty` when the value no longer matches the source.
   *
   * While it is false the attribute re-emits by slicing `[start, end)`, which
   * keeps its original spacing and quote character. Setting it by hand without
   * marking the owning element is a silent no-op - the element would still be
   * clean and would re-emit the whole start tag as a slice.
   */
  dirty: boolean;
}

interface XmlDeclarationToken extends TokenBase {
  readonly type: 'declaration';
  readonly version: string;
  readonly encoding: string | undefined;
  readonly standalone: string | undefined;
}

interface XmlProcessingInstructionToken extends TokenBase {
  readonly type: 'processingInstruction';
  readonly target: string;
  /** Everything between the target and `?>`, verbatim. */
  readonly data: string;
}

interface XmlCommentToken extends TokenBase {
  readonly type: 'comment';
  /** The text between `<!--` and `-->`, with line endings normalized. */
  readonly value: string;
}

interface XmlElementToken extends TokenBase {
  readonly type: 'startTag' | 'emptyElementTag';
  readonly qname: string;
  readonly prefix: string;
  readonly local: string;
  readonly nameEnd: number;
  /**
   * Where the whitespace before `>` or `/>` begins.
   *
   * Equal to the last attribute's `end` (or to `nameEnd`) when there is none.
   */
  readonly trailingSpaceStart: number;
  readonly attributes: readonly XAttribute[];
  /**
   * True if any attribute is an `xmlns` or `xmlns:*` declaration.
   *
   * Computed here because the attribute loop has already looked at every name.
   * It turns `resolvePrefix`'s walk from "scan every ancestor's whole attribute
   * list" into "step over ancestors that declare nothing", which is the
   * difference between 37 seconds and milliseconds on a deep tree whose
   * elements carry many non-namespace attributes.
   */
  readonly hasNamespaceDeclarations: boolean;
}

interface XmlEndTagToken extends TokenBase {
  readonly type: 'endTag';
  readonly qname: string;
  readonly prefix: string;
  readonly local: string;
}

interface XmlTextToken extends TokenBase {
  readonly type: 'text';
  /** References expanded and line endings normalized. */
  readonly value: string;
  /** True if the run is `S` characters only - inter-element formatting. */
  readonly whitespaceOnly: boolean;
}

interface XmlCdataToken extends TokenBase {
  readonly type: 'cdata';
  /** The text between `<![CDATA[` and `]]>`, with line endings normalized. */
  readonly value: string;
}

type XmlToken = XmlDeclarationToken | XmlProcessingInstructionToken | XmlCommentToken | XmlElementToken | XmlEndTagToken | XmlTextToken | XmlCdataToken;

interface XmlTokenizerLimits {
  /** Attributes on one element. The most any element in our corpus carries is 15. */
  readonly maxAttributes: number;
  /** Tokens in one part. Our largest part yields 2303 elements. */
  readonly maxTokens: number;
  /**
   * Length of the source, in UTF-16 code units.
   *
   * The only ceiling here denominated in the quantity that actually governs
   * allocation. Counting tokens, nodes or attributes-per-element each bounds
   * one dimension and misses the product: 20 000 elements carrying 256
   * attributes apiece is 41.9 MiB of source, 20 001 nodes - half a percent of
   * `maxNodes` - and 817 MB of heap. Under a constrained heap that is a
   * `FATAL ERROR: Ineffective mark-compacts` process abort, which no
   * `try`/`catch` can see.
   *
   * The largest XML part in our 37-package corpus is 69 KB; the largest seen
   * anywhere in the wild is under a megabyte. 16 MiB is far past both.
   */
  readonly maxSourceLength: number;
}

const DEFAULT_TOKENIZER_LIMITS: XmlTokenizerLimits;

class XmlTokenizer {
  #private;
  readonly source: string;
  constructor(source: string, limits?: XmlTokenizerLimits);
  /** Index of the first token. Non-zero exactly when the source carries a BOM. */
  get contentStart(): number;
  get position(): number;
  next(): XmlToken | undefined;
  /** Every remaining token, in order. */
  [Symbol.iterator](): IterableIterator<XmlToken>;
}

function tokenize(source: string, limits?: XmlTokenizerLimits): XmlToken[];

interface SpanGap {
  readonly kind: 'gap' | 'overlap' | 'prologue' | 'epilogue';
  readonly at: number;
  readonly text: string;
}

function checkSpanCoverage(source: string, tokens: readonly XmlToken[]): SpanGap[];

function splitQName(qname: string): {
  prefix: string;
  local: string;
};

interface XElement extends NodeBase {
  readonly type: 'element';
  qname: string;
  prefix: string;
  local: string;
  attributes: XAttribute[];
  children: XNode[];
  /**
   * `<x/>` rather than `<x></x>`.
   *
   * Both are legal and both survive PowerPoint's reader, so the distinction is
   * ours to preserve: 33 elements in the corpus - all in `docProps` - use the
   * long form, and PowerPoint's own writer collapses them on resave.
   */
  selfClosing: boolean;
  /** One past the `>` of the start tag. Children begin here. */
  openTagEnd: number;
  /** The `<` of the end tag. Equal to {@link NodeBase.end} when self-closing. */
  closeTagStart: number;
  /** One past the element name inside the start tag. */
  nameEnd: number;
  /**
   * Where the whitespace before `>` or `/>` begins.
   *
   * Not cosmetic: 70 822 of the 98 777 self-closing tags in the corpus are
   * written `<a:off x="0" y="0" />`, so a serializer that assumes `/>` follows
   * the last attribute directly loses a character on most of the corpus.
   */
  trailingSpaceStart: number;
  /**
   * True if this element carries any `xmlns` or `xmlns:*` attribute.
   *
   * Computed by the tokenizer, which has already read every attribute name.
   * {@link resolvePrefix} walks ancestors, and without this it also rescanned
   * each ancestor's whole attribute list: a 1.7 MB document 1000 deep with 200
   * attributes per element took 37 seconds in `undeclaredPrefixes`. Both
   * numbers are legal - depth 1001 is under `maxDepth`, 200 attributes under
   * `maxAttributes` - and nothing counted the product.
   */
  hasNamespaceDeclarations: boolean;
}

interface XText extends NodeBase {
  readonly type: 'text';
  /** References expanded, line endings normalized. Not the source text. */
  value: string;
  /**
   * True if the run is `S` characters only - inter-element formatting.
   *
   * Derived from `value`, and therefore not `readonly`: sub-phase 0.6's
   * `setValue` maintains it. A derived field that an edit can leave stale is a
   * bug that shows up somewhere far away from the edit.
   */
  whitespaceOnly: boolean;
}

interface XCData extends NodeBase {
  readonly type: 'cdata';
  value: string;
}

interface XComment extends NodeBase {
  readonly type: 'comment';
  value: string;
}

interface XProcessingInstruction extends NodeBase {
  readonly type: 'processingInstruction';
  target: string;
  data: string;
}

interface XDeclaration extends NodeBase {
  readonly type: 'declaration';
  readonly version: string;
  readonly encoding: string | undefined;
  readonly standalone: string | undefined;
}

type XNode = XElement | XText | XCData | XComment | XProcessingInstruction | XDeclaration;

interface XDocument {
  readonly source: string;
  readonly encoding: XmlEncoding;
  readonly bom: boolean;
  readonly children: XNode[];
  readonly root: XElement;
  readonly declaration: XDeclaration | undefined;
}

interface XmlParseLimits extends XmlTokenizerLimits {
  /**
   * Element nesting depth.
   *
   * The deepest part in our corpus reaches 23, inside a `p:timing` tree.
   * PowerPoint has no useful limit of its own - it opens a part nested 5000
   * deep - so this number protects us rather than matching it. The builder uses
   * an explicit stack and never recurses, so the limit bounds what a hostile
   * document can allocate; it is not standing between us and a stack overflow.
   */
  readonly maxDepth: number;
  /** Nodes in one document. */
  readonly maxNodes: number;
}

const DEFAULT_PARSE_LIMITS: XmlParseLimits;

function parseXmlString(source: string, limits?: XmlParseLimits): XDocument;

function parseXml(bytes: Uint8Array, limits?: XmlParseLimits): XDocument;

function sourceOf(document: XDocument, node: XNode): string;

function startTagOf(document: XDocument, element: XElement): string;

function childElements(element: XElement): XElement[];

function firstChild(element: XElement, qname: string): XElement | undefined;

function attribute(element: XElement, qname: string): XAttribute | undefined;

function attributeValue(element: XElement, qname: string): string | undefined;

function descendantElements(element: XElement): IterableIterator<XElement>;

function textContent(element: XElement): string;

function markDirty(node: XNode, journal?: XNode[]): void;

function markAttributeDirty(element: XElement, attribute: XAttribute, journal?: {
  nodes: XNode[];
  attributes: XAttribute[];
}): void;

function checkDirtyInvariant(document: XDocument): CoverageGap[];

function declaredNamespaces(element: XElement): Map<string, string>;

function resolvePrefix(element: XElement, prefix: string): string | undefined;

function namespaceOf(element: XElement): string | undefined;

function attributeNamespaceOf(owner: XElement, attr: XAttribute): string | undefined;

function namespaceScope(element: XElement): Map<string, string>;

function prefixFor(element: XElement, namespace: string): string | undefined;

function prefixMap(document: XDocument): Map<string, Set<string>>;

function undeclaredPrefixes(document: XDocument): {
  prefix: string;
  at: number;
}[];

function xmlSpace(element: XElement): 'default' | 'preserve';

interface CoverageGap {
  readonly kind: 'gap' | 'overlap' | 'malformed';
  readonly at: number;
  readonly detail: string;
}

function checkTreeCoverage(document: XDocument): CoverageGap[];

function serializeXmlString(document: XDocument): string;

function serializeXml(document: XDocument): Uint8Array;

function serializeNode(document: XDocument, node: XNode): string;

interface RoundTripDifference {
  /**
   * `parse` - the output is not well-formed, which is the worst case and the
   * only one that makes the rest of the comparison impossible.
   * `structure` - the trees differ at some node.
   * `prefix` - a prefix is bound to a different set of URIs.
   * `bom` - the byte order mark was gained or lost.
   */
  readonly kind: 'parse' | 'structure' | 'prefix' | 'bom';
  /** Offset in the **input** document, where one is attributable. */
  readonly at: number;
  readonly detail: string;
}

function checkRoundTrip(document: XDocument, limits?: XmlParseLimits): RoundTripDifference[];

interface CanonicalXmlOptions {
  /**
   * Rewrite an attribute value before it is written.
   *
   * The one caller is the round-trip comparator, which relabels relationship
   * ids: `r:embed="rId3"` and `r:embed="rId7"` are the same reference if the
   * two `.rels` agree about where rId3 and rId7 point. Passing the mapping in
   * rather than building it here keeps this module ignorant of relationships,
   * which are a package concept and not an XML one.
   *
   * `namespaceUri` is the attribute's namespace - the empty string for an
   * unprefixed attribute, which is in no namespace rather than in the element's
   * default one.
   */
  readonly rewriteAttributeValue?: (value: string, namespaceUri: string, localName: string) => string;
}

function canonicalXml(document: XDocument, options?: CanonicalXmlOptions): string;

function firstDifference(a: string, b: string): number;

function excerpt(text: string, at: number, radius?: number): string;

const SCHEMA_SOURCES: readonly {
  readonly file: string;
  readonly sha256: string;
}[];

const SCHEMA_NAMESPACES: readonly string[];

function isSchemaNamespace(namespace: string | undefined): boolean;

function qualifiedKey(namespace: string, local: string): string;

function elementKey(element: XElement): string | undefined;

function childRanks(parent: XElement): ReadonlyMap<string, number> | undefined;

function childRank(parent: XElement, childKey: string): number | undefined;

function insertionIndex(parent: XElement, childKey: string): number | undefined;

function outOfOrderChildren(parent: XElement): {
  at: number;
  detail: string;
}[];

const MC_ALTERNATE_CONTENT = "AlternateContent";

const MC_CHOICE = "Choice";

const MC_FALLBACK = "Fallback";

function isAlternateContent(element: XElement): boolean;

function ignorableNamespaces(element: XElement): Set<string>;

function mustUnderstandNamespaces(element: XElement): Set<string>;

function processContentNames(element: XElement): Set<string>;

function selectAlternateContent(alternateContent: XElement, supported: ReadonlySet<string>): XElement | undefined;

function effectiveChildren(element: XElement, supported: ReadonlySet<string>): IterableIterator<XNode>;

function effectiveAttributes(element: XElement, supported: ReadonlySet<string>): IterableIterator<XAttribute>;

interface McProblem {
  readonly at: number;
  readonly detail: string;
}

function checkMarkupCompatibility(root: XElement, supported: ReadonlySet<string>): McProblem[];

function boundNamespaces(root: XElement): Set<string>;

function newAttribute(qname: string, value: string, quote?: '"' | "'"): XAttribute;

function newElement(qname: string, attributes?: readonly XAttribute[], children?: readonly XNode[]): XElement;

function newText(value: string): XText;

interface DirtyRestore {
  readonly nodes: readonly XNode[];
  readonly attributes: readonly XAttribute[];
}

interface SetAttributeEdit extends EditBase {
  readonly kind: 'setAttribute';
  readonly element: XElement;
  readonly qname: string;
  readonly value: string;
}

interface AddAttributeEdit extends EditBase {
  readonly kind: 'addAttribute';
  readonly element: XElement;
  readonly index: number;
  readonly attribute: XAttribute;
}

interface RemoveAttributeEdit extends EditBase {
  readonly kind: 'removeAttribute';
  readonly element: XElement;
  readonly qname: string;
}

interface InsertChildEdit extends EditBase {
  readonly kind: 'insertChild';
  readonly parent: XElement;
  readonly index: number;
  readonly node: XNode;
}

interface RemoveChildEdit extends EditBase {
  readonly kind: 'removeChild';
  readonly parent: XElement;
  readonly node: XNode;
}

interface SetValueEdit extends EditBase {
  readonly kind: 'setValue';
  readonly node: XText | XCData | XComment;
  readonly value: string;
}

type XmlEdit = SetAttributeEdit | AddAttributeEdit | RemoveAttributeEdit | InsertChildEdit | RemoveChildEdit | SetValueEdit;

function applyEdit(edit: XmlEdit): XmlEdit;

function applyEdits(edits: readonly XmlEdit[]): XmlEdit[];

function insertInOrder(parent: XElement, child: XElement): InsertChildEdit;

function extensionList(parent: XElement): XElement | undefined;

function extensions(parent: XElement): XElement[];

function findExtension(parent: XElement, uri: string): XElement | undefined;

function planAddExtension(parent: XElement, uri: string): {
  edits: XmlEdit[];
  ext: XElement;
};

function planRemoveExtension(parent: XElement, uri: string): XmlEdit[];