pdfjs-dist/lib/core/name_number_tree.js

/**
 * @licstart The following is the entire license notice for the
 * Javascript code in this page
 *
 * Copyright 2022 Mozilla Foundation
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 *
 * @licend The above is the entire license notice for the
 * Javascript code in this page
 */
"use strict";

Object.defineProperty(exports, "__esModule", {
  value: true
});
exports.NumberTree = exports.NameTree = void 0;

var _primitives = require("./primitives.js");

var _util = require("../shared/util.js");

class NameOrNumberTree {
  constructor(root, xref, type) {
    if (this.constructor === NameOrNumberTree) {
      (0, _util.unreachable)("Cannot initialize NameOrNumberTree.");
    }

    this.root = root;
    this.xref = xref;
    this._type = type;
  }

  getAll() {
    const map = new Map();

    if (!this.root) {
      return map;
    }

    const xref = this.xref;
    const processed = new _primitives.RefSet();
    processed.put(this.root);
    const queue = [this.root];

    while (queue.length > 0) {
      const obj = xref.fetchIfRef(queue.shift());

      if (!(obj instanceof _primitives.Dict)) {
        continue;
      }

      if (obj.has("Kids")) {
        const kids = obj.get("Kids");

        for (let i = 0, ii = kids.length; i < ii; i++) {
          const kid = kids[i];

          if (processed.has(kid)) {
            throw new _util.FormatError(`Duplicate entry in "${this._type}" tree.`);
          }

          queue.push(kid);
          processed.put(kid);
        }

        continue;
      }

      const entries = obj.get(this._type);

      if (!Array.isArray(entries)) {
        continue;
      }

      for (let i = 0, ii = entries.length; i < ii; i += 2) {
        map.set(xref.fetchIfRef(entries[i]), xref.fetchIfRef(entries[i + 1]));
      }
    }

    return map;
  }

  get(key) {
    if (!this.root) {
      return null;
    }

    const xref = this.xref;
    let kidsOrEntries = xref.fetchIfRef(this.root);
    let loopCount = 0;
    const MAX_LEVELS = 10;

    while (kidsOrEntries.has("Kids")) {
      if (++loopCount > MAX_LEVELS) {
        (0, _util.warn)(`Search depth limit reached for "${this._type}" tree.`);
        return null;
      }

      const kids = kidsOrEntries.get("Kids");

      if (!Array.isArray(kids)) {
        return null;
      }

      let l = 0,
          r = kids.length - 1;

      while (l <= r) {
        const m = l + r >> 1;
        const kid = xref.fetchIfRef(kids[m]);
        const limits = kid.get("Limits");

        if (key < xref.fetchIfRef(limits[0])) {
          r = m - 1;
        } else if (key > xref.fetchIfRef(limits[1])) {
          l = m + 1;
        } else {
          kidsOrEntries = xref.fetchIfRef(kids[m]);
          break;
        }
      }

      if (l > r) {
        return null;
      }
    }

    const entries = kidsOrEntries.get(this._type);

    if (Array.isArray(entries)) {
      let l = 0,
          r = entries.length - 2;

      while (l <= r) {
        const tmp = l + r >> 1,
              m = tmp + (tmp & 1);
        const currentKey = xref.fetchIfRef(entries[m]);

        if (key < currentKey) {
          r = m - 2;
        } else if (key > currentKey) {
          l = m + 2;
        } else {
          return xref.fetchIfRef(entries[m + 1]);
        }
      }
    }

    return null;
  }

}

class NameTree extends NameOrNumberTree {
  constructor(root, xref) {
    super(root, xref, "Names");
  }

}

exports.NameTree = NameTree;

class NumberTree extends NameOrNumberTree {
  constructor(root, xref) {
    super(root, xref, "Nums");
  }

}

exports.NumberTree = NumberTree;