PDF.js 源码解读: struct_tree

  #readStructTreeRoot() {
    const rawObj = this.#catDict.getRaw("StructTreeRoot"),
      obj = this.xref.fetchIfRef(rawObj);
    return obj instanceof Dict
      ? new StructTreeRoot(this.xref, obj, rawObj)
      : null;
  }

class StructTreeRoot {
  kidRefToPosition = undefined;
 
  parentTree = null;
 
  roleMap = new Map();
 
  structParentIds = null;
 
  constructor(xref, rootDict, rootRef) {
    this.xref = xref;
    this.dict = rootDict;
    this.ref = rootRef instanceof Ref ? rootRef : null;
 
    const roleMap = rootDict.get("RoleMap");
    if (roleMap instanceof Dict) {
      for (const [key, value] of roleMap) {
        if (value instanceof Name) {
          this.roleMap.set(key, value.name);
        }
      }
    }
    const parentTree = rootDict.getRaw("ParentTree");
    if (parentTree) {
      this.parentTree = new NumberTree(parentTree, xref);
    }
  }

  get(key) {
    return this.xref.fetchIfRef(this.getRaw(key));
  }

  getKidPosition(kidRef) {
    if (this.kidRefToPosition === undefined) {
      const obj = this.dict.get("K");
      if (Array.isArray(obj)) {
        const map = (this.kidRefToPosition = new Map());
        for (let i = 0, ii = obj.length; i < ii; i++) {
          const ref = obj[i];
          if (ref) {
            map.set(ref.toString(), i);
          }
        }
      } else if (obj instanceof Dict) {
        this.kidRefToPosition = new Map([[obj.objId, 0]]);
      } else if (!obj) {
        this.kidRefToPosition = new Map();
      } else {
        this.kidRefToPosition = null;
      }
    }
    return this.kidRefToPosition
      ? (this.kidRefToPosition.get(kidRef) ?? NaN)
      : -1;
  }

  #addIdToPage(pageRef, id, type, objId) {
    if (!(pageRef instanceof Ref) || id < 0) {
      return;
    }
    (this.structParentIds ??= new RefMap())
      .getOrPutComputed(pageRef, makeArr)
      .push([id, type, objId]);
  }
 
  addAnnotationIdToPage(pageRef, id, ref) {
    this.#addIdToPage(
      pageRef,
      id,
      StructElementType.ANNOTATION,
      ref instanceof Ref ? ref.toString() : null
    );
  }

if (annotationGlobals.structTreeRoot) {
  let structParent = dict.get('StructParent');
  this.data.structParent = structParent =
    Number.isInteger(structParent) && structParent >= 0 ? structParent : -1;
 
  annotationGlobals.structTreeRoot.addAnnotationIdToPage(params.pageRef, structParent, this.ref);
}

  get role() {
    const nameObj = this.dict.get("S");
    const name = nameObj instanceof Name ? nameObj.name : "";
    const { root } = this.tree;
    return root.roleMap.get(name) ?? name;
  }

  #collectAttributes(value, attributes) {
    const pending = [value];
    const visited = new RefSet();
 
    while (pending.length > 0) {
      value = pending.pop();
      if (value instanceof Ref) {
        // Only indirect references can make a PDF attribute graph cyclic.
        if (visited.has(value)) {
          continue;
        }
        visited.put(value);
        value = this.xref.fetch(value);
      }
      if (value instanceof BaseStream) {
        value = value.dict;
      }
      if (value instanceof Dict) {
        attributes.push(value);
        continue;
      }
      if (!Array.isArray(value)) {
        continue;
      }
 
      // Process entries in source order. Attribute arrays may interleave
      // attribute objects and revision numbers.
      for (let i = value.length - 1; i >= 0; i--) {
        if (!Number.isInteger(value[i])) {
          pending.push(value[i]);
        }
      }
    }
  }

  get attributes() {
    const attributes = [];
 
    const classes = this.dict.getArray("C");
    if (classes !== undefined) {
      const classMap = this.tree.rootDict?.get("ClassMap");
      if (classMap instanceof Dict) {
        // Class names may be interleaved with revision numbers.
        for (const className of Array.isArray(classes) ? classes : [classes]) {
          if (className instanceof Name) {
            this.#collectAttributes(
              classMap.getRaw(className.name),
              attributes
            );
          }
        }
      }
    }
 
    // Explicit attributes take precedence over attributes from a class.
    this.#collectAttributes(this.dict.getRaw("A"), attributes);
 
    return shadow(this, "attributes", attributes);
  }

const TABLE_SPAN_ATTRIBUTES = [
  ['RowSpan', 'rowSpan'],
  ['ColSpan', 'colSpan'],
];

  get tableAttributes() {
    const { role } = this;
    if (role !== "Table" && role !== "TH" && role !== "TD") {
      return null;
    }
 
    const map = new Map();
    for (const attributes of this.attributes) {
      if (!isName(attributes.get("O"), "Table")) {
        continue;
      }
      // ...
    }
    return map.size ? map : null;
  }

const StructElementType = {
  PAGE_CONTENT: 1,
  STREAM_CONTENT: 2,
  OBJECT: 3,
  ANNOTATION: 4,
  ELEMENT: 5,
};

class StructElement {
  constructor({ type, dict = null, mcid = null, pageObjId = null, refObjId = null }) {
    this.type = type;
    this.dict = dict;
    this.mcid = mcid;
    this.pageObjId = pageObjId;
    this.refObjId = refObjId;
    this.parentNode = null;
  }
}

class StructElementNode {
  constructor(tree, dict) {
    this.tree = tree;
    this.xref = tree.xref;
    this.dict = dict;
    this.kids = [];
    this.parseKids();
  }

  parseKids() {
    let pageObjId = null;
    const objRef = this.dict.getRaw("Pg");
    if (objRef instanceof Ref) {
      pageObjId = objRef.toString();
    }
    const kids = this.dict.get("K");
    if (Array.isArray(kids)) {
      for (const kid of kids) {
        const element = this.parseKid(pageObjId, this.xref.fetchIfRef(kid));
        if (element) {
          this.kids.push(element);
        }
      }
    } else {
      const element = this.parseKid(pageObjId, kids);
      if (element) {
        this.kids.push(element);
      }
    }
  }

  parseKid(pageObjId, kid) {
    // A direct link to content, the integer is an mcid.
    if (Number.isInteger(kid)) {
      if (this.tree.pageDict.objId !== pageObjId) {
        return null;
      }
 
      return new StructElement({
        type: StructElementType.PAGE_CONTENT,
        mcid: kid,
        pageObjId,
      });
    }
 
    if (!(kid instanceof Dict)) {
      return null;
    }
 
    const pageRef = kid.getRaw("Pg");
    if (pageRef instanceof Ref) {
      pageObjId = pageRef.toString();
    }
 
    const type = kid.get("Type") instanceof Name ? kid.get("Type").name : null;
    if (type === "MCR") {
      if (this.tree.pageDict.objId !== pageObjId) {
        return null;
      }
      const kidRef = kid.getRaw("Stm");
      return new StructElement({
        type: StructElementType.STREAM_CONTENT,
        refObjId: kidRef instanceof Ref ? kidRef.toString() : null,
        pageObjId,
        mcid: kid.get("MCID"),
      });
    }
 
    if (type === "OBJR") {
      if (this.tree.pageDict.objId !== pageObjId) {
        return null;
      }
      const kidRef = kid.getRaw("Obj");
      return new StructElement({
        type: StructElementType.OBJECT,
        refObjId: kidRef instanceof Ref ? kidRef.toString() : null,
        pageObjId,
      });
    }
 
    return new StructElement({
      type: StructElementType.ELEMENT,
      dict: kid,
    });
  }

if (this.tree.pageDict.objId !== pageObjId) {
  return null;
}

/**
 * Instead of loading the whole tree we load just the page's relevant structure
 * elements, which means we need a wrapper structure to represent the tree.
 */

class StructTreePage {
  constructor(structTreeRoot, pageDict) {
    this.root = structTreeRoot;
    this.xref = structTreeRoot?.xref ?? null;
    this.rootDict = structTreeRoot?.dict ?? null;
    this.pageDict = pageDict;
    this.nodes = [];
  }

  parse(pageRef) {
    if (!this.root || !this.rootDict || !(pageRef instanceof Ref)) {
      return;
    }
 
    const { parentTree } = this.root;
    if (!parentTree) {
      return;
    }
    const id = this.pageDict.get("StructParents");
    const ids = this.root.structParentIds?.get(pageRef);
    if (!Number.isInteger(id) && !ids) {
      return;
    }
 
    const map = new Map();
 
    if (Number.isInteger(id)) {
      const parentArray = parentTree.get(id);
      if (Array.isArray(parentArray)) {
        for (const ref of parentArray) {
          if (ref instanceof Ref) {
            this.addNode(this.xref.fetch(ref), map);
          }
        }
      }
    }
 
    if (!ids) {
      return;
    }
    for (const [elemId, type, objId] of ids) {
      const obj = parentTree.get(elemId);
      if (!obj) {
        continue;
      }
      const elem = this.addNode(this.xref.fetchIfRef(obj), map);
      if (!elem || !objId) {
        continue;
      }
      // Match the annotation by object reference because its structure
      // element may have other children.
      for (const kid of elem.kids) {
        if (kid.type === StructElementType.OBJECT && kid.refObjId === objId) {
          kid.type = type;
        }
      }
    }
  }

  collectObjects(pageRef) {
    if (!this.root || !this.rootDict || !(pageRef instanceof Ref)) {
      return null;
    }
 
    const parentTree = this.rootDict.get("ParentTree");
    if (!parentTree) {
      return null;
    }
    const ids = this.root.structParentIds?.get(pageRef);
    if (!ids) {
      return null;
    }
    const map = new Map();
    const numberTree = new NumberTree(parentTree, this.xref);
 
    for (const [elemId] of ids) {
      const obj = numberTree.getRaw(elemId);
      if (obj instanceof Ref) {
        map.set(elemId, obj);
      }
    }
    return map;
  }

  addNode(dict, map, level = 0) {
    if (level > MAX_DEPTH) {
      warn("StructTree MAX_DEPTH reached.");
      return null;
    }
    if (!(dict instanceof Dict)) {
      return null;
    }
 
    if (map.has(dict)) {
      return map.get(dict);
    }
 
    const element = new StructElementNode(this, dict);
    map.set(dict, element);
    switch (element.role) {
      case "L":
      case "LBody":
      case "LI":
      case "Table":
      case "THead":
      case "TBody":
      case "TFoot":
      case "TR": {
        // Always collect all child nodes of lists and tables, even empty ones
        for (const kid of element.kids) {
          if (kid.type === StructElementType.ELEMENT) {
            this.addNode(kid.dict, map, level - 1);
          }
        }
      }
    }
 
    const parent = dict.get("P");
 
    if (
      !(parent instanceof Dict) ||
      isName(parent.get("Type"), "StructTreeRoot")
    ) {
      if (!this.addTopLevelNode(dict, element)) {
        map.delete(dict);
      }
      return element;
    }
 
    const parentNode = this.addNode(parent, map, level + 1);
    if (!parentNode) {
      return element;
    }
    let save = false;
    for (const kid of parentNode.kids) {
      if (kid.type === StructElementType.ELEMENT && kid.dict === dict) {
        kid.parentNode = element;
        save = true;
      }
    }
    if (!save) {
      map.delete(dict);
    }
    return element;
  }

  addTopLevelNode(dict, element) {
    const index = this.root.getKidPosition(dict.objId);
    if (isNaN(index)) {
      return false;
    }
    if (index !== -1) {
      this.nodes[index] = element;
    }
    return true;
  }

  get serializable() {
    function nodeToSerializable(node, parent, level = 0) {
      if (level > MAX_DEPTH) {
        warn("StructTree too deep to be fully serialized.");
        return;
      }
      const obj = Object.create(null);
      obj.role = node.role;
      obj.children = [];
      parent.children.push(obj);
      let alt = node.dict.get("Alt");
      if (typeof alt !== "string") {
        alt = node.dict.get("ActualText");
      }
      if (typeof alt === "string") {
        obj.alt = stringToPDFString(alt);
      }
      // ...
    }

const root = Object.create(null);
root.children = [];
root.role = 'Root';
for (const child of this.nodes) {
  if (!child) {
    continue;
  }
  nodeToSerializable(child, root);
}
return root;

// Note that this must not be called `id`, since that name is already
// used, with a different meaning, on the content/object/annotation
// children below.
const structId = node.dict.get('ID');
if (obj.role === 'TH' && typeof structId === 'string' && structId) {
  obj.structId = stringToPDFString(structId);
}

for (const kid of node.kids) {
  const kidElement = kid.type === StructElementType.ELEMENT ? kid.parentNode : null;
  if (kidElement) {
    nodeToSerializable(kidElement, obj, level + 1);
    continue;
  } else if (
    kid.type === StructElementType.PAGE_CONTENT ||
    kid.type === StructElementType.STREAM_CONTENT
  ) {
    obj.children.push({
      type: 'content',
      id: `p${kid.pageObjId}_mc${kid.mcid}`,
    });
  } else if (kid.type === StructElementType.OBJECT) {
    obj.children.push({
      type: 'object',
      id: kid.refObjId,
    });
  } else if (kid.type === StructElementType.ANNOTATION) {
    obj.children.push({
      type: 'annotation',
      id: `${AnnotationPrefix}${kid.refObjId}`,
    });
  }
}

const mcid = args[1] instanceof Dict ? args[1].get('MCID') : null;
textContent.items.push({
  type: 'beginMarkedContentProps',
  id: Number.isInteger(mcid) ? `${self.idFactory.getPageObjId()}_mc${mcid}` : null,
  tag: args[0] instanceof Name ? args[0].name : null,
});

      static getPageObjId() {
        return `p${ref.toString()}`;
      }

let alt = node.dict.get('Alt');
if (typeof alt !== 'string') {
  alt = node.dict.get('ActualText');
}
if (typeof alt === 'string') {
  obj.alt = stringToPDFString(alt);
}

let bbox = null,
  size = null;
for (const a of node.attributes) {
  bbox = lookupNormalRect(a.getArray('BBox'), bbox);
  const width = a.get('Width');
  const height = a.get('Height');
  if (typeof width === 'number' && width > 0 && typeof height === 'number' && height > 0) {
    size = [0, 0, width, height];
  }
}
// Prefer BBox because Width and Height cannot recover its position.
if (bbox || size) {
  obj.bbox = bbox ?? size;
}

if (obj.role === 'Formula') {
  try {
    const { mathML } = node;
    if (mathML) {
      obj.mathML = mathML;
    }
  } catch (ex) {
    if (ex instanceof MissingDataException) {
      throw ex;
    }
    warn(`Ignoring mathML: "${ex}".`);
  }
}

      const fileStream = FileSpec.pickPlatformItem(af.get("EF"));
      if (
        !(fileStream instanceof BaseStream) ||
        !isDict(fileStream.dict, "EmbeddedFile") ||
        !isName(fileStream.dict.get("Subtype"), "application/mathml+xml")
      ) {
        continue;
      }
      // The default encoding for xml files is UTF-8.
      return stringToUTF8String(fileStream.getString());

const lang = node.dict.get('Lang');
if (typeof lang === 'string') {
  obj.lang = stringToPDFString(lang);
}

let nextKey = 0;
let hasNothingToUpdate = true;
 
for (const [pageIndex, elements] of newAnnotationsByPage) {
  const { ref: pageRef } = await pdfManager.getPage(pageIndex);
  if (!(pageRef instanceof Ref)) {
    warn(`Cannot save the struct tree: page ${pageIndex} has no ref.`);
    hasNothingToUpdate = true;
    break;
  }
  for (const element of elements) {
    if (element.accessibilityData?.type) {
      // Each tag must have a structure type.
      element.parentTreeId = nextKey++;
      hasNothingToUpdate = false;
    }
  }
}
// ...

  static async createStructureTree({
    newAnnotationsByPage,
    xref,
    catalogRef,
    pdfManager,
    changes,
  }) {
    const root = await pdfManager.ensureCatalog("cloneDict");
    const cache = new RefMap();
    cache.put(catalogRef, root);
 
    const structTreeRootRef = xref.getNewTemporaryRef();
    root.set("StructTreeRoot", structTreeRootRef);
 
    const structTreeRoot = new Dict(xref);
    structTreeRoot.set("Type", Name.get("StructTreeRoot"));
    const parentTreeRef = xref.getNewTemporaryRef();
    structTreeRoot.set("ParentTree", parentTreeRef);
    const kids = [];
    structTreeRoot.set("K", kids);
    cache.put(structTreeRootRef, structTreeRoot);
 
    const parentTree = new Dict(xref);
    const nums = [];
    parentTree.set("Nums", nums);
 
    const nextKey = await this.#writeKids({
      newAnnotationsByPage,
      structTreeRootRef,
      structTreeRoot: null,
      kids,
      nums,
      xref,
      pdfManager,
      changes,
      cache,
    });
    structTreeRoot.set("ParentTreeNextKey", nextKey);
 
    cache.put(parentTreeRef, parentTree);
 
    for (const [ref, obj] of cache.items()) {
      changes.put(ref, {
        data: obj,
      });
    }
  }

  async canUpdateStructTree({ pdfManager, newAnnotationsByPage }) {
    if (!this.ref) {
      warn("Cannot update the struct tree: no root reference.");
      return false;
    }
 
    let nextKey = this.dict.get("ParentTreeNextKey");
    if (!Number.isInteger(nextKey) || nextKey < 0) {
      warn("Cannot update the struct tree: invalid next key.");
      return false;
    }
 
    const parentTree = this.dict.get("ParentTree");
    if (!(parentTree instanceof Dict)) {
      warn("Cannot update the struct tree: ParentTree isn't a dict.");
      return false;
    }
    const nums = parentTree.get("Nums");
    if (!Array.isArray(nums)) {
      warn("Cannot update the struct tree: nums isn't an array.");
      return false;
    }
    const numberTree = new NumberTree(parentTree, this.xref);
 
    for (const pageIndex of newAnnotationsByPage.keys()) {
      const { pageDict } = await pdfManager.getPage(pageIndex);
      if (!pageDict.has("StructParents")) {
        // StructParents is required when the content stream has some tagged
        // contents but a page can just have tagged annotations.
        continue;
      }
      const id = pageDict.get("StructParents");
      if (!Number.isInteger(id) || !Array.isArray(numberTree.get(id))) {
        warn(`Cannot save the struct tree: page ${pageIndex} has a wrong id.`);
        return false;
      }
    }
    // ...
    return true;
  }

StructTreeRoot.#collectParents({
  elements,
  xref: this.xref,
  pageDict,
  numberTree,
});
 
for (const element of elements) {
  if (element.accessibilityData?.type) {
    // structParent can be undefined and in this case the positivity check
    // will fail (it's why the expression isn't equivalent to a `.<.`).
    if (!(element.accessibilityData.structParent >= 0)) {
      // Each tag must have a structure type.
      element.parentTreeId = nextKey++;
    }
    hasNothingToUpdate = false;
  }
}

let parentTreeRef = structTreeRoot.getRaw('ParentTree');
let parentTree;
if (parentTreeRef instanceof Ref) {
  parentTree = xref.fetch(parentTreeRef);
} else {
  parentTree = parentTreeRef;
  parentTreeRef = xref.getNewTemporaryRef();
  structTreeRoot.set('ParentTree', parentTreeRef);
}
parentTree = parentTree.clone();
cache.put(parentTreeRef, parentTree);
// ...

        const { structParent } = accessibilityData;
 
        if (
          structTreeRoot &&
          Number.isInteger(structParent) &&
          structParent >= 0
        ) {
          let objs = (structTreePageObjs ||= new Map()).get(pageIndex);
          if (objs === undefined) {
            // We need to collect the objects for the page.
            const structTreePage = new StructTreePage(
              structTreeRoot,
              page.pageDict
            );
            objs = structTreePage.collectObjects(pageRef);
            structTreePageObjs.set(pageIndex, objs);
          }
          const objRef = objs?.get(structParent);
          if (objRef) {
            // We update the existing tag.
            const tagDict = xref.fetch(objRef).clone();
            StructTreeRoot.#writeProperties(tagDict, accessibilityData);
            changes.put(objRef, {
              data: tagDict,
            });
            continue;
          }
        }
        nextKey = Math.max(nextKey, parentTreeId);
 
        const tagRef = xref.getNewTemporaryRef();
        const tagDict = new Dict(xref);
 
        StructTreeRoot.#writeProperties(tagDict, accessibilityData);
        // ...
        cache.put(tagRef, tagDict);
        nums.push(parentTreeId, tagRef);

const objDict = new Dict(xref);
tagDict.set('K', objDict);
objDict.set('Type', objr);
if (isPageRef) {
  // Pg is optional.
  objDict.set('Pg', pageRef);
}
objDict.set('Obj', ref);

  static #writeProperties(
    tagDict,
    { type, title, lang, alt, expanded, actualText }
  ) {
    // The structure type is required.
    tagDict.set("S", Name.get(type));
 
    if (title) {
      tagDict.set("T", stringToAsciiOrUTF16BE(title));
    }
    if (lang) {
      tagDict.set("Lang", stringToAsciiOrUTF16BE(lang));
    }
    if (alt) {
      tagDict.set("Alt", stringToAsciiOrUTF16BE(alt));
    }
    if (expanded) {
      tagDict.set("E", stringToAsciiOrUTF16BE(expanded));
    }
    if (actualText) {
      tagDict.set("ActualText", stringToAsciiOrUTF16BE(actualText));
    }
  }

const updateElement = (kid, pageKid, kidRef) => {
  const elems = idToElements.get(kid);
  if (elems) {
    const parentRef = pageKid.getRaw('P');
    const parentDict = xref.fetchIfRef(parentRef);
    if (parentRef instanceof Ref && parentDict instanceof Dict) {
      // It should always the case, but we check just in case.
      const params = { ref: kidRef, dict: pageKid };
      for (const element of elems) {
        element.structTreeParent = params;
      }
    }
    return true;
  }
  return false;
};

if (element.structTreeParentId) {
  const id = parseInt(element.structTreeParentId.split('_mc')[1], 10);
  idToElements.getOrInsertComputed(id, makeArr).push(element);
}

let ref = null;
let parentRef;
if (structTreeParent) {
  ({ ref } = structTreeParent);
 
  // We get the parent of the tag.
  parentRef = structTreeParent.dict.getRaw('P') || structTreeRootRef;
} else {
  parentRef = structTreeRootRef;
}
 
tagDict.set('P', parentRef);
 
// We get the kids in order to insert a new tag at the right position.
const parentDict = xref.fetchIfRef(parentRef);
if (!parentDict) {
  fallbackKids.push(newTagRef);
  return;
}
// ...
const index = cachedParentKids.indexOf(ref);
cachedParentKids.splice(index >= 0 ? index + 1 : cachedParentKids.length, 0, newTagRef);

const MAX_DEPTH = 40;

try {
  const structTree = await this.pdfManager.ensure(this, '_parseStructTree', [structTreeRoot]);
  return await this.pdfManager.ensure(structTree, 'serializable');
} catch (ex) {
  warn(`getStructTree: "${ex}".`);
  return null;
}