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パーサー書いてる間は何度もコードを読んで見ることになりそうなので、また疑問点出てきたらメモ残していこうと思います。

著書『実践Django Pythonによる本格Webアプリケーション開発』が本日から発売されます。

Twitterでは以前から告知を行っていましたが、著書『実践Django Pythonによる本格Webアプリケーション開発』が本日から発売になります。 購入を検討している方は、Amazonもしくはお近くの書店で探してみてください(エキスパートPythonプログラミング 改訂3版も今月末発売予定です)。

f:id:nwpct1:20210717141541j:plain

初の著書であり単著ということもあり大変なこともありましたが、満足の行く一冊が出来上がってホッとしています。

追記: 単行本派データベースカテゴリでベストセラー1位、Kindle版もNPONGOカテゴリでベストセラー1位になっていました。購入してくださった方、Twitterで拡散してくださった方ありがとうございました!

本書の対象読者

本書の対象読者やおすすめの読み方については、レビューをお手伝いいただいた中川さんが素晴らしい記事を書いてくださいました。 本書がアピールしたいことや、どういうふうに読んでほしいかをまさに汲み取ってまとめていただいているのでぜひこちらを先に読んでみてください。

shinyorke.hatenablog.com

"Djangoをやる方はもちろん, Djangoを抜きにしてもWebアプリケーション開発をされる方にめちゃくちゃオススメしたい!" と思いました, レビューさせてもらったときからすごく良かったんですよ, それぐらい興奮しました ※1

※1: レビューしながら, 「そうだよ!そこが大事なのよ!!」とか家で一人声を出しながら食い気味に読ませていただきました苦笑. 発売前に原稿が読めて幸せでした(感謝)

中川さんもこうおっしゃってくださっていて嬉しいです。

例えばデータベースのインデックスチューニングやHTTPまわりの基礎知識、ユニットテストを書くときの考え方、認証認可まわりの注意点などは、Djangoに限らず必要な知識だと思います。こういったフレームワークに依存しない知識は、Django公式ドキュメントで扱っていないことも多く、初学者の方は勉強のきっかけを掴めないことも多いと思います。

でも、むしろそういったところにWeb開発者として長く役に立つ知識が詰まっているとも思っています。 他のPython Web関連の書籍に比べて高度な内容も多く扱っていると思いますが、詳しく解説しすぎるとどんどん難しくなる話もちょうどよいボリュームでまとめるよう心がけて執筆したので、ぜひ多くの方の手にとっていただきたいです。

サンプルコードや目次

サンプルコードや目次はこちらのGitHubリポジトリで公開しています。

github.com

Amazonレビューのお願い

すでに本書を読んでくださったという方もいらっしゃると思いますが、もしよければAmazonでレビューをつけていただけると嬉しいです。

(素晴らしい書籍であるにも関わらず、残念なレビューがついてしまう悲しい話 も見たことがあるので、どんな評価であれできるだけ多くの方がAmazonレビューをつけていただけると嬉しいです...!)

最後に

Djangoを触り始めてもう7年くらい経ちますが、今見てもこれだけ多くの機能を見通しよく設計し使いやすく提供できていることに驚きます。 たまにパッチを書いてコア開発者の方々からレビューをもらったときには、彼らの設計能力の高さやデータベースまわりの知識の深さに圧倒されます。 Djangoに限らないとは思いますが、世界中のWebシステムの開発に使われるフレームワークを開発している人たちのさまざまなドメインに対する知識の深さは頭がいくつも抜けていて、自分はいまだに全然届かないなと思いました。 彼らがDjangoの開発を続けてくれていることにとても感謝しています。

GitHub SponsorsこちらのページDjango Software Foundationへ寄付ができます (自分はGitHub Sponsors経由にしています)。 本書をきっかけに少しでもDjangoの採用事例が増え、寄付をする人が増えたら嬉しいなと思っています。ぜひ検討してみてください。

最近の登壇資料と出版予定の書籍、インタビュー記事

最近は勉強会での登壇や書籍の出版などアウトプットが色々重なりました (昨年は一度もプロポーザルを書かず登壇依頼もなかったので随分増えました)。 そのたびにツイートもしてきましたが、ほとんど流れてしまって少しもったいない気がしたのでブログにまとめておこうと思います。

登壇資料

PyData.Tokyo Meetup #23「サイバーエージェントにおけるMLOpsに関する取り組み」

運営の方からお声がけいただき、MLOpsについてお話させていただきました。あまりMLのコミュニティで登壇してこなかったのと、参加者が500人以上いて緊張していたので、資料も気合を入れて準備しました。

登壇資料の中では過去一番拡散され、Twitterでの反応もよく久しぶりに満足のいく発表ができたかなと思います。動画も公開されているのでよければ見てみてください。


www.youtube.com

Optuna Meetup #1「CMA-ESサンプラーによるハイパーパラメータ最適化」

自分もコミッターを務めているハイパーパラメータ最適化フレームワーク「Optuna」の勉強会で、CMA-ESという最適化アルゴリズムの話をしてきました。 こちらも450人程度参加者が集まっていて、Optunaの人気の高さに驚きました。動画は公開されていません。スライド資料だけ読んでもよくわからないかもしれませんが、以前Optunaのブログで記事も書いているので興味のある方はこちら読んでみてください。

World Plone Day「Web パネルディスカッション(Python Webと非同期)」

PythonCMSPlone」の国際カンファレンスであるWorld Plone Dayのパネルディスカッションで、寺田(@terapyon)さんにお声がけいただきパネラーをやってきました。 といってもPloneを使ったことがないので普通にPython Webフレームワークの非同期対応について話してきました。

一緒にパネルで話した @hirokiky さんや @aodagさんも含め全員がWSGIフレームワークを書いたりしたことがあるぐらいには、Webフレームワークの設計や実装を理解しているメンバーなのでやや踏み込んだ話が多かったと思います。 自分自身色々キャッチアップできてとても勉強になりました。個人的に印象に残った話だけメモしておくと:

  • SQLAlchemyの非同期対応が最近入った。
    • メソッド呼び出しだけでなくプロパティアクセスで暗黙的にSQLを発行したりするので簡単ではない。
    • DjangoよりSQLAlchemyのほうがそういう暗黙的な挙動が多いらしく、大変そうという話がでました (今思うとDjangoもjoin忘れると普通に起きるので同じぐらいかも?という気もします)
  • DBドライバーの非同期対応がなかなかまだ厳しいという話
    • DB-APIの非同期インターフェイスがまだ存在せず、各種DBドライバーは独自でインターフェイスを決めて実装している。
    • asyncpgとaiopgは微妙にシグネチャが違っていて、同じコードでは動かない。
    • 現状まともに使えそうな非同期のDBドライバーはasyncpgぐらい。
    • SQLite3とかはPythonの標準ライブラリに追加されるといいね(ついでに非同期版DB-API決まるといいね)と思った。


www.youtube.com

動画はちょっと長いのですが、前半45分がPythonと非同期に関する話になります。

CA BASE NEXT「サイバーエージェントにおけるMLOpsに関する取り組み」

サイバーエージェントの若手世代による社外向け技術カンファレンスである『CA BASE NEXT』でも話してきました。内容はPyData Tokyoで話したものと同じですが、時間がこちらは30分しかなかったため、GeventやWebSocketまわりの話を削ってお話しています。

ca-base-next.cyberagent.co.jp

書籍

実践Django Pythonによる本格Webアプリケーション開発(翔泳社:7月19日発売)

PythonのWebフレームワーク「Django」の書籍です。今月19日発売になります。初の単著書ということもあり出版にあたって色々想いもあるのでこちらについてはまた発売日にブログを書こうと思います。

エキスパートPythonプログラミング改訂3版(KADOKAWA:7月30日発売)

エキスパートPythonプログラミングの改訂3版です。今月30日発売になります。内容がアップデートされただけでなく新しく追加された章もあるので改訂2版をお持ちの方もぜひ手にとってみてください。

インタビュー記事

今年3月に会社のFEATUReSというメディアから、2本のインタビュー記事が出ました。 昨年も個人インタビュー記事を書いていただけたのですが、こんなに何度も取り上げていただけることはあまりないので嬉しいです。

PythonOSS開発とフレームワーク解析の日々はやがて世界5位の研究成果につながる FEATUReS

サイバーエージェント社内にはDeveloper Expertsという肩書きを持つエンジニアが8名在籍しています。自分は昨年からPython領域のDeveloper Expertsに任命されていて、そのときの就任インタビュー記事が今年3月に公開されました。

www.cyberagent.co.jp

生み出したのは、世界レベルの実績。研究/OSS開発で切り開くハイパーパラメータ最適化の未来 - FEATUReS

現在所属しているハイパーパラメータ最適化チームのインタビュー記事です。現在は同期のリサーチャーである野村と2人で活動しているのですが、ここ1年は色々とまとまった成果が出てきました。研究者も開発者もいい人がいたらぜひ手伝っていただきたいなと思っているので、もしこの辺興味がある方いたらお声がけいただけると嬉しいです。

www.cyberagent.co.jp

おわりに

ここ2-3ヶ月は、登壇資料ばかり書いていてメインタスクがおろそかになってしまった気がします。昨年いろいろ頑張って成果がでた貯金のおかげで、昨年末・今年の4月と全社表彰でベストエンジニア賞をいただけたりもしましたが、もう貯金も切れてしまったと思うのでここから挽回したいなと思います。