PDFMinerコードリーディングメモ ① Indirect Object ReferenceのTokenize処理

しばらくこちらのブログを更新していなかったのですが、2023年からはもう少しGitHub以外のアウトプットも増やしてみようかなということで、試しに今回はコードリーディング時のメモとかも残していってみます。

ここ数日PDFの仕様書を読み進めているのですが、仕様書からは読み取りきれないところとかパーサーを書く際に設計で悩みそうなところがいくつかあったので、Shimizukawaさんも挙げられているPDFMinerのコードを読んでみました。

PDFParser クラスと PDFDocument クラス

PDFMinerでは次のように PDFParserクラスとPDFDocumentクラスを使ってまずCross-Reference TableやTrailer Dictionaryをパースしています。 まずはそれぞれの役割抑えてみます。

from pdfminer.pdfdocument import PDFDocument
from pdfminer.pdfparser import PDFParser


with open("simple.pdf", 'rb') as f:
    parser = PDFParser(f)
    doc = PDFDocument(parser, password="")

PDFParser はファイルオブジェクトを受け取ってファイルから必要な情報を抜き出します。例えばPDFファイルをopenしたら最初にやるのは末尾から1行ずつ読みこんでCross-Reference Tableのファイル内オフセットを取得します。Pythonのファイルライクオブジェクトに後ろから1行ずつ読み込む方法は存在しませんが、 PDFParser().revreadlines() のようにPDFParserクラス (厳密にはこのようなファイルオブジェクトのちょっとしたラッパー程度の処理はPDFParserの親クラスであるPSBaseParserクラスに実装されています) が提供します。

# https://github.com/pdfminer/pdfminer.six/blob/5114acdda61205009221ce4ebf2c68c144fc4ee5/pdfminer/psparser.py#L272-L295
    def revreadlines(self) -> Iterator[bytes]:
        """Fetches a next line backword.
        This is used to locate the trailers at the end of a file.
        """
        self.fp.seek(0, 2)
        pos = self.fp.tell()
        buf = b""
        while 0 < pos:
            prevpos = pos
            pos = max(0, pos - self.BUFSIZ)
            self.fp.seek(pos)
            s = self.fp.read(prevpos - pos)
            if not s:
                break
            while 1:
                n = max(s.rfind(b"\r"), s.rfind(b"\n"))
                if n == -1:
                    buf = s + buf
                    break
                yield s[n:] + buf
                s = s[:n]
                buf = b""
        return

その一方、PDFを開いたあとに startxref やCross-Reference Tableの中身の解析を担当するのは PDFDocument クラスのようです。このクラスの初期化時に、 PDFDocument.find_xref(parser) でCross-Reference Tableのファイル内オフセット(int)を取得し、 xrefs: list[PDFBaseXRef] = []; PDFDocument.read_xref_from(parser, startxref, xrefs) を実行すると xrefs にCross Reference Tableのエントリー一覧をappendします。

# https://github.com/pdfminer/pdfminer.six/blob/5114acdda61205009221ce4ebf2c68c144fc4ee5/pdfminer/pdfdocument.py#L965-L1016
    # find_xref
    def find_xref(self, parser: PDFParser) -> int:
        """Internal function used to locate the first XRef."""
        # search the last xref table by scanning the file backwards.
        prev = None
        for line in parser.revreadlines():
            line = line.strip()
            log.debug("find_xref: %r", line)
            if line == b"startxref":
                break
            if line:
                prev = line
        else:
            raise PDFNoValidXRef("Unexpected EOF")
        log.debug("xref found: pos=%r", prev)
        assert prev is not None
        return int(prev)

    # read xref table
    def read_xref_from(
        self, parser: PDFParser, start: int, xrefs: List[PDFBaseXRef]
    ) -> None:
        """Reads XRefs from the given location."""
        parser.seek(start)
        parser.reset()
        try:
            (pos, token) = parser.nexttoken()
        except PSEOF:
            raise PDFNoValidXRef("Unexpected EOF")
        log.debug("read_xref_from: start=%d, token=%r", start, token)
        if isinstance(token, int):
            # XRefStream: PDF-1.5
            parser.seek(pos)
            parser.reset()
            xref: PDFBaseXRef = PDFXRefStream()
            xref.load(parser)
        else:
            if token is parser.KEYWORD_XREF:
                parser.nextline()
            xref = PDFXRef()
            xref.load(parser)
        xrefs.append(xref)
        trailer = xref.get_trailer()
        log.debug("trailer: %r", trailer)
        if "XRefStm" in trailer:
            pos = int_value(trailer["XRefStm"])
            self.read_xref_from(parser, pos, xrefs)
        if "Prev" in trailer:
            # find previous xref
            pos = int_value(trailer["Prev"])
            self.read_xref_from(parser, pos, xrefs)
        return

PDFParserにはもう一つ役割があり、むしろこちらがメインの役割だと思うのですが、PDFオブジェクトのTokenizeを担当します。 今回はTokenizeで不明点があったのでそこを調べてみました。

PDF Dictionary ObjectとIndirect Reference

今回調べたかったのはDictionary Object(辞書オブジェクト)のパースです。PDFを開いて最初にパースする辞書オブジェクトは基本的にはPDFの末尾に配置されているTrailer辞書オブジェクトというものになるかと思いますがそれは次のような形式です。

<<
  /Size 6
  /Root 1 0 R
>>

辞書オブジェクトはKey-value形式で、Keyは名前オブジェクト(/ から始まる文字列のような型)であることが仕様上定められています。このTrailer辞書オブジェクトは /Size/Root という2つのKeyとそれに対するValueが存在しているようです。次にもう一つ別の例を見てみます。

 << /Type /Example
      /Subtype /DictionaryExample
      /Version 0.01
      /IntegerItem 12
      /StringItem (a string)
      /Subdictionary << /Item1 0.4
          /Item2 true
          /LastItem (not!)
          /VeryLastItem (OK)
     >>
     /Foo [1 2 3]
>>

この例では /Type というKeyに対して、 /Example という名前オブジェクトをValueとして指定されています。 ここでの疑問はパースの方法です。2つめの例を見るに、1つのKeyに対して1つのValueを持つという前提がなければ /Type /Example /SubType /DictionaryExample というバイト列はどれがKeyでどれがValueかを特定できません。そこでナイーブにKeyとValueが1:1であることを前提にパーサーを実装すると1つめの辞書の /Root に対するValue1 (整数型) のみとなるはずです。

仕様書を読み返すと先程の /Root 1 0 R1 0 R はIndirect ReferenceというIndirect Objectへの参照を表すようです。

The object may be referred to from elsewhere in the file by an indirect reference. Such indirect references shall consist of the object number, the generation number, and the keyword R (with white space separating each part): 12 0 R

整数オブジェクト2つとキーワードRを並べているのですが、特別なシンボルでまとめられていたりはしないため、うまくパースする方法が思いつかなかったので処理をもう少し追ってみます。

PDFMinerでの実装

このようなTrailer辞書オブジェクトのパースを担当するのは PDFParser.nextobject() メソッドです。

# https://github.com/pdfminer/pdfminer.six/blob/5114acdda61205009221ce4ebf2c68c144fc4ee5/pdfminer/psparser.py#L600-L675

    def nextobject(self) -> PSStackEntry[ExtraT]:
        """Yields a list of objects.
        Arrays and dictionaries are represented as Python lists and
        dictionaries.
        :return: keywords, literals, strings, numbers, arrays and dictionaries.
        """
        while not self.results:
            (pos, token) = self.nexttoken()
            if isinstance(token, (int, float, bool, str, bytes, PSLiteral)):
                # normal token
                self.push((pos, token))
            elif token == KEYWORD_ARRAY_BEGIN:
                # begin array
                self.start_type(pos, "a")
            elif token == KEYWORD_ARRAY_END:
                # end array
                try:
                    self.push(self.end_type("a"))
                except PSTypeError:
                    if settings.STRICT:
                        raise
            elif token == KEYWORD_DICT_BEGIN:
                # begin dictionary
                self.start_type(pos, "d")
            elif token == KEYWORD_DICT_END:
                # end dictionary
                try:
                    (pos, objs) = self.end_type("d")
                    if len(objs) % 2 != 0:
                        error_msg = "Invalid dictionary construct: %r" % objs
                        raise PSSyntaxError(error_msg)
                    d = {
                        literal_name(k): v
                        for (k, v) in choplist(2, objs)
                        if v is not None
                    }
                    self.push((pos, d))
                except PSTypeError:
                    if settings.STRICT:
                        raise
            elif token == KEYWORD_PROC_BEGIN:
                # begin proc
                self.start_type(pos, "p")
            elif token == KEYWORD_PROC_END:
                # end proc
                try:
                    self.push(self.end_type("p"))
                except PSTypeError:
                    if settings.STRICT:
                        raise
            elif isinstance(token, PSKeyword):
                log.debug(
                    "do_keyword: pos=%r, token=%r, stack=%r", pos, token, self.curstack
                )
                self.do_keyword(pos, token)
            else:
                log.error(
                    "unknown token: pos=%r, token=%r, stack=%r",
                    pos,
                    token,
                    self.curstack,
                )
                self.do_keyword(pos, token)
                raise
            if self.context:
                continue
            else:
                self.flush()
        obj = self.results.pop(0)
        try:
            log.debug("nextobject: %r", obj)
        except Exception:
            log.debug("nextobject: (unprintable object)")
        return obj

このメソッドは PDFParser.nexttoken() メソッドを呼び出してtokenを取得しながら辞書オブジェクトを構築していきます。Indirect Object Referenceを含む << /Size 6 /Root 1 0 R >> のような辞書を入力に対して PDFParser.nexttoken() を何度も呼び出していくとやはり次のようなToken列に分割されます。

  1. << トーク
  2. /Size 名前トーク
  3. 6 整数トーク
  4. /Root 名前トーク
  5. 1 整数トーク
  6. 0 整数トーク
  7. R キーワードトーク

ここでは 1 0 R とやはりまとめられてはおらず困るように思えましたが、Tokenize時にキーワードトークンを受け取った際は次のような処理を入れて対応しているようです。

# https://github.com/pdfminer/pdfminer.six/blob/master/pdfminer/pdfparser.py#L74-L84
class PDFParser(PSStackParser[Union[PSKeyword, PDFStream, PDFObjRef, None]]):
    ...
    KEYWORD_R = KWD(b"R")
    KEYWORD_NULL = KWD(b"null")
    KEYWORD_ENDOBJ = KWD(b"endobj")
    KEYWORD_STREAM = KWD(b"stream")
    KEYWORD_XREF = KWD(b"xref")
    KEYWORD_STARTXREF = KWD(b"startxref")

    def do_keyword(self, pos: int, token: PSKeyword) -> None:
        """Handles PDF-related keywords."""

        if token in (self.KEYWORD_XREF, self.KEYWORD_STARTXREF):
            self.add_results(*self.pop(1))

        elif token is self.KEYWORD_ENDOBJ:
            self.add_results(*self.pop(4))

        elif token is self.KEYWORD_NULL:
            # null object
            self.push((pos, None))

        elif token is self.KEYWORD_R:
            # reference to indirect object
            if len(self.curstack) >= 2:
                try:
                    ((_, objid), (_, genno)) = self.pop(2)
                    (objid, genno) = (int(objid), int(genno))  # type: ignore[arg-type]
                    assert self.doc is not None
                    obj = PDFObjRef(self.doc, objid, genno)
                    self.push((pos, obj))
                except PSSyntaxError:
                    pass

Rキーワードが来たらトークン一覧から2つpopしてPDFObjRefトークンを詰め直すということをやっています。 Tokenを一度に読み出す必要はありますが、辞書オブジェクトの中でしかでてこないならひとまずこれが一番シンプルで合理的に思えます。 先読みも一応可能ですが、整数オブジェクトが見つかった際に常にそれがIndirect Referenceかをチェックするのは、整数オブジェクトのほうが数が多いのでパフォーマンス上もデメリットがありそうです。

まだPDFのオブジェクトとドキュメントのパース処理しか読めてないのでほんの一部ですが、設計の意図が読み取りやすいライブラリでした。 PDFパーサー書いてる間は何度もコードを読んで見ることになりそうなので、また疑問点出てきたらメモ残していこうと思います。