PDFMinerコードリーディングメモ ① Indirect Object ReferenceのTokenize処理
しばらくこちらのブログを更新していなかったのですが、2023年からはもう少しGitHub以外のアウトプットも増やしてみようかなということで、試しに今回はコードリーディング時のメモとかも残していってみます。
2023年に新しく学ぶ技術はRustとPDFにします。
— c-bata (@c_bata_) 2023年1月16日
なるほどー。PDFはデータ構造が表示に特化しているのでなかなか大変そう。でも読んで表示するならなんとかなるのかな。
— Takayuki Shimizukawa (@shimizukawa) 2023年1月17日
Python使うか分からないけど、某書籍のPDFからテキスト生成するのに使ったコードがあるので参考にどうぞー
pdfminerを使ってPDFからreSTを生成 https://t.co/oe4YQOr1Lv
ここ数日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
に対するValueは 1
(整数型) のみとなるはずです。
仕様書を読み返すと先程の /Root 1 0 R
の 1 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 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パーサー書いてる間は何度もコードを読んで見ることになりそうなので、また疑問点出てきたらメモ残していこうと思います。