2021-02-24

Pythonのstrptime %zに関するバグ報告をした

Python

timefmt-goというGoライブラリを公開してメンテしているのですが、最近タイムゾーン周りの対応が弱いことに気がついて実装していました。タイムゾーンオフセットの表記は +0900 のようにコロンを入れないほうが一般的だと思いますが、RFC3339では +09:00 のようにコロンありの形もvalidです。strftime では %:z によりこの形を出力し、strptimeの %z はコロンありなし両方の形をparseする必要があります。GNU拡張のstrftimeでは %::z を使うと秒まで表記し、%:::z ではオフセットの精度によっていい感じに表記するようです (分精度なら分までなど)。

 $ date +%z
+0900
 $ date +%:z
+09:00
 $ date +%::z
+09:00:00
 $ date +%:::z
+09

strptimeの他の言語の挙動を確認しているときに、Python (3.9.2) で思わぬエラーが発生することに気が付きました。

>>> from datetime import datetime
>>> datetime.strptime('Z', '%z')
datetime.datetime(1900, 1, 1, 0, 0, tzinfo=datetime.timezone.utc)
>>> datetime.strptime('z', '%z')
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "/usr/local/lib/python3.9/_strptime.py", line 568, in _strptime_datetime
    tt, fraction, gmtoff_fraction = _strptime(data_string, format)
  File "/usr/local/lib/python3.9/_strptime.py", line 453, in _strptime
    if z[3] == ':':
IndexError: string index out of range

%z が大文字の Z を解釈するのは正しいのですが、それ以外のおかしな入力のときは ValueError となるべきです。

>>> datetime.strptime('x', '%z')
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "/usr/local/lib/python3.9/_strptime.py", line 568, in _strptime_datetime
    tt, fraction, gmtoff_fraction = _strptime(data_string, format)
  File "/usr/local/lib/python3.9/_strptime.py", line 349, in _strptime
    raise ValueError("time data %r does not match format %r" %
ValueError: time data 'x' does not match format '%z'

例外の型が違うということは except ValueError のようなキャッチをすり抜けてしまうということですね。ざんねんでした。

早速ソースコードを読んでいると、フォーマットを正規表現に変換するときに大文字小文字を無視するオプションを使っていて (%aがMonでもMONでもマッチするように)、UTCを表す Z が意図せず z にもマッチしているようでした。

            'z': r"(?P<z>[+-]\d\d:?[0-5]\d(:?[0-5]\d(\.\d{1,6})?)?|Z)",
# 略
    def compile(self, format):
        """Return a compiled re object for the format string."""
        return re_compile(self.pattern(format), IGNORECASE)
# 略
        elif group_key == 'z':
            z = found_dict['z']
            if z == 'Z':
                gmtoff = 0
            else:
                if z[3] == ':':
                    z = z[:3] + z[4:]

考慮漏れだとわかったので、既存のissueがないことを確かめて新たにチケットを切りました。 bugs.python.org GitHubではないので面倒かと思ったのですが、OpenIDですぐにログインできて、本名も要求されずとても簡単でした (Linux Foundationとかと比べると遥かに)。次の日には興味を持った人がパッチを投げてくれました。月や曜日のマッチングにはignore caseフラグが必要なのでどう修正するのかわからなかったのですが、 (?-i:PATTERN) で一時的に無視することができるのですね。知らなかった。 github.com 3.9.3では直るんじゃないでしょうか。世界から一つバグが消えてよかったですね。

Pythonのstrptimeは正規表現で実装されていて結構遅いと思いますが、あまり気にしない文化なのでしょうか。日時なんて大した長さの文字列ではないからこれで良いのかもしれません (しかも strptime('999', '%H%M%S') みたいなケースも対応している)。 timefmtは極力アロケーションを減らし、strconv.Atoiすら避けてカリカリにチューニングしているので、Pythonのライブラリはだいぶ富豪的だなと思いました。終わり。

itchyny.hatenablog.com

2021-01-20

Go言語のorderedmapパッケージを改善した

Go言語で書かれたorderedmapというサードパーティパッケージがあります。 github.com

Goのmapには順序がなく、JSONをデコードすると順序が失われ、それをエンコードするとオブジェクトのキーの順序にソートされます。これに困る人はそこそこいるようで、順序を保持するmapはいくつか実装されてきました。その中の一つが、orderedmapというパッケージです。シンプルなインターフェイスが気に入っています。

orderedmapパッケージの利用例

package main

import (
    "encoding/json"
    "fmt"
    "log"

    "github.com/iancoleman/orderedmap"
)

func main() {
    src := `{ "z": 1, "x": 2, "y": 3 }`

    fmt.Println("# map[string]interface{}")
    var v map[string]interface{}
    if err := json.Unmarshal([]byte(src), &v); err != nil {
        log.Fatal(err)
    }
    bs, err := json.MarshalIndent(v, "", "  ")
    if err != nil {
        log.Fatal(err)
    }
    fmt.Printf("%s\n\n", bs)

    fmt.Println("# OrderedMap")
    o := orderedmap.New()
    if err := json.Unmarshal([]byte(src), &o); err != nil {
        log.Fatal(err)
    }
    bs, err = json.MarshalIndent(o, "", "  ")
    if err != nil {
        log.Fatal(err)
    }
    fmt.Printf("%s\n\n", bs)
}

# map[string]interface{}
{
  "x": 2,
  "y": 3,
  "z": 1
}

# OrderedMap
{
  "z": 1,
  "x": 2,
  "y": 3
}

しかし、このパッケージのUnmarshal (JSON → OrderedMap の変換) の実装は、正直あまりきれいではありませんでした。 v0.1.0までの実装は以下のようになっていました。

map[string]interface{} に Unmarshal する
オブジェクトの各キーに対して、JSON文字列の中の出現位置を探す
- キーの " をエスケープして、 strings.LastIndex で探す
- JSON文字列を探したインデックスまでを切り取って } を付け加えたときにvalidなJSONかチェックする
  - validなJSONでなければ、ネストされたJSONのキーにヒットしまっているので、更に前にたどってキーのポジションを探す
オブジェクトの各値に対して
- オブジェクトであれば、OrderedMapへの変換を再帰的に行う
- 配列であれば、各要素の変換を再帰的に行う
オブジェクトのキー一覧を、出現位置でソートする

オブジェクトのキーの順序を保持したい → キーの文字列の出現位置を探索してソートすれば良い、という素朴な発想でこういう実装になっているのだと思いますが、この処理には様々な問題があります。

オブジェクトのキーを文字列から探すときに " しかエスケープしておらず、{ "\n": 1 } のようなものはうまくUnmarshalできない
- { "A\u0041A\u0041A": 0 } のようなキーもありうるので、strings.LastIndex でポジションを探す方針には限界がある (指数関数的な個数のエスケープを試す必要がある)
パフォーマンスが良くない (#2)
- validなJSONかかどうかをチェックするという処理でいちいち json.Unmarshal している (orderedmap.go#L178-L192)。
- 探索範囲を絞ったりスペースをスキップしたりするために、文字列のアロケーションが多い
ネストしたJSONに対処するために実装が複雑で、一見してバグっていない自信がない (主観)
- 重複キーに対しては結構怪しい気がする

個人的には好きなパッケージですが、Unmarshalの実装が複雑であまり使いたくないという気持ちがありました。しかし作者も課題感を持っているようでしたし、解決策も思いついたので、実装し直すことにしました。

標準パッケージのencoding/jsonの*DecoderにはToken() (Token, error)という関数があります。 JSONのトークンを一つずつデコードする関数です。 *DecoderはJSONのステートを持っているので、単なるlexerではなくてvalidなJSONのトークン列を返してくれます。これを使います。

map[string]interface{} に Unmarshal する
JSONから *Decoder を作り、dec.Token() を使ってトークンをたどっていく
- キーはスライスに追加する
  - 重複キーは後ろに移動する
- 値の最初のトークンによって、オブジェクトか配列かその他の場合に分かれる
  - 値がオブジェクトの場合
    - map[string]interface{}またはOrderedMap (重複キー) の場合はOrderedMapに変換する処理を行う
    - それ以外の場合 (型が違う) は重複キーなので、OrderedMapへのデコードを行うが得られた値は捨てる
  - 値が配列の場合
    - 配列の各要素に対してオブジェクトか配列の場合は再帰的にデコードを行う
    - それ以外の場合 (型が違う、配列のインデックスを超えているなど) は重複キーなので、デコードを行うが得られた値は捨てる

この実装によって様々な点が改善されました。

オブジェクトのキーがエスケープされていても問題なく動く
- { "A\u0041A\u0041A": 0 } のようなものでもOK
以前の実装では何度も文字列上を走査する必要があったが、この実装では二回スキャンすればよい
- 実装を突き詰めてJSONパースを自前で持てば一回で済むが、そこはencoding/jsonに任せて小さく実装している
オブジェクトのキー一覧をソートする必要がない
- ただし重複キーが大量にある場合のパフォーマンスは良くない
文字列のアロケーションが大幅に減少し、パフォーマンスも改善される
実装が比較的読みやすい

ベンチマークは以下のように改善されています。アロケーションは半分以下に抑えられ、パフォーマンスも三倍近く改善しています。

benchmark                     old ns/op     new ns/op     delta
BenchmarkUnmarshalJSON-16     125485        37536         -70.09%

benchmark                     old allocs    new allocs    delta
BenchmarkUnmarshalJSON-16     964           389           -59.65%

benchmark                     old bytes     new bytes     delta
BenchmarkUnmarshalJSON-16     49885         13174         -73.59%

一方、Marshal (OrderedMap → JSONへの変換) にも改善を入れました。 Unmarshal ほどの問題はありませんでしたが、オブジェクトのキーのエスケープが足りていない ({ "\n": 1 } 相当を出力すると改行が入りvalidなJSONにならない) とか、文字列のアロケーションが多いといった問題を解決しています。文字列の結合をbytes.Bufferに置き換える単純なお仕事です。

ベンチマークは以下のようになっています。アロケーションはかなり減りましたが、パフォーマンスとしては7%程度の改善にとどまっています。

benchmark                   old ns/op     new ns/op     delta
BenchmarkMarshalJSON-16     15687         14535         -7.34%

benchmark                   old allocs    new allocs    delta
BenchmarkMarshalJSON-16     94            33            -64.89%

benchmark                   old bytes     new bytes     delta
BenchmarkMarshalJSON-16     9309          2195          -76.42%

以上の改善は、v0.2.0としてリリースされています。個人的には実装がかなりクリアになり (まあ自分で書いたし)、パフォーマンスも良くなったので、安心してこのパッケージを使えるようになりました。また一つ世界が良くなりましたね。おしまい！

2021-01-18

gojq が homebrew/core に入りました、他近況

gojqはGoで実装されたjqコマンドおよびライブラリです。2019年の4月から開発を始めて、現在も様々な改善を行っています。

これまでgojqのHomebrew formulaはitchyny/tapより配信していましたが、このたび公式のhomebrew/coreに入りました。これにより、次のコマンドでインストールできるようになりました。

brew install gojq

tapの考え方についてはTapsを参照してください。

実は、私への連絡もなしにいきなりhomebrew/coreに入れられていて、formulaの品質が悪かったのですが、色々と指摘したらすぐに直してくれました。自分のコントロールできない部分に置くのが正直嫌だったのですが、すでに入ってしまったのを怒ってもしょうがないし、bottleによるメリットも大きいので良いかなと思います。ただ、連絡はしてほしかったですね… (というかメイン開発者の意向を無視して勝手にformula追加できるのどうなの…)

formulaの配布元tapを移動するときは、tap_migrations.json を使います。 tapのリポジトリのトップにこの名前のJSONを作っておけば、既存のtapを使っているユーザーもスムーズにtapの移行が行われます。今回はhomebrew/coreに移動したので、以下のようなJSONファイルを配置しました。

{
  "gojq": "homebrew/core"
}

gojqは様々なフィードバックを受けて完成度があがっています。最近あったものとしては、$HOMEが空のときにうまく動かないというものです (#58)。デフォルトのモジュールパスの~/.jqを展開するためにos.UserHomeDirを使っていたのですが、値を取れないときにエラーとして終了していました。 $HOMEが取れないケースというのは想定したことなかったのです。 AWS Lambdaで動かすとこれが空になるそうですね。

Fuzzingによるコーナーケースの修正も行っています。例えば ""[:{}] とか infinite * "x" のようなクエリのクラッシュが発見されています。また先日は全探索によるバグの探索も行いました。コマンド引数に渡すクエリ文字列を生成して、コマンドの実行結果を比較するという感じです。

jqとgojqの終了ステータスの差異をチェックするコード

package main

import (
    "fmt"
    "os/exec"
    "syscall"
)

func main() {
    source := []byte(" ")
    for {
        check(string(source))
        for i := len(source) - 1; i >= 0; i-- {
            if source[i] != '~' {
                source[i]++
                if i == 0 && (source[i] == '-' || source[i] == '+') ||
                    source[i] == '#' {
                    source[i]++
                }
                if source[i] == '1' {
                    source[i] = ':'
                }
                break
            }
            source[i] = ' '
            if i == 0 {
                source[0] = '!'
                source = append(source, '!')
            } else if i == len(source)-1 {
                source[i]++
            }
        }
    }
}

var sem = make(chan struct{}, 10)

func check(src string) {
    sem <- struct{}{}
    go func() {
        defer func() { <-sem }()
        if x, y := run("jq", "-n", src), run("gojq", "-n", src); x != y {
            fmt.Printf("ng: %q %d %d\n", src, x, y)
        } else if x == 0 {
            fmt.Printf("ok: %q %d %d\n", src, x, y)
        }
    }()
}

func run(command string, args ...string) int {
    cmd := exec.Command(command, args...)
    if err := cmd.Start(); err != nil {
        return -1
    }
    if err := cmd.Wait(); err != nil {
        if exiterr, ok := err.(*exec.ExitError); ok {
            if status, ok := exiterr.Sys().(syscall.WaitStatus); ok {
                return status.ExitStatus()
            }
        }
    }
    return 0
}

この調査では 1?/1 (lexerのバグで、?//という演算子をチェックして失敗した後のoffsetのバグ)、0.._ (これもlexerのバグで、クエリのエラーとすべきものを受け付けてしまっていた) や @a? (compilerのバグで、定義されていないformatをcompile errorとしてはいけない) といったクエリの挙動が異なることが発見されました。実装に相当自信があっても、Fuzzingや探索を行ってみると、何かしらのバグは見つかるものですね。

gojq v0.12.0からはJSONに色を付けるライブラリを自前で持ち、パフォーマンスが三倍以上改善しました。以前はgo-prettyprintにお世話になっていましたが、オブジェクトのキーのエスケープがバグっていたのと (#15にて修正済)、NaNや無限大の正規化が (これらはnullと出力するというjqの仕様を実装する必要がある) オーバーヘッドになっていたこと、またこのライブラリのパフォーマンスがあまり良くないことが問題でした。色付けを行う部分を自前にすることで、jq仕様の正規化も組み込むことができ、またメモリーアロケーションも大幅に減少することができました。 go-prettyjsonのパフォーマンスの改善に関しては#17にてフィードバックしています (二倍近くは速くなりそうです)。

gojqは言語処理系です。作り始めて二年近くになり、処理系もパーサーもそれぞれ完全なリライトをしています。コミット数も1000を超え、様々なことを学ぶことができました。 Goのツールにライブラリとしてgojqを埋め込む利用例も増えています。ソフトウェアは完成することはありません。これからもgojqを楽しんでいきたいと思います。

gojqは作り始めて一年半経った今でもコードを書く楽しさを教え続けてくれて嬉しい。大体これくらいやってると飽きが来るのだけど、gojqは飽きた頃に新しい話題を持ってきてくれる。
— (っ=﹏=c) .｡o○ (@itchyny) 2020年12月21日

2021-01-11

一括リネームツール mmv でディレクトリツリーを扱えるようにした

一年前、ファイルをエディターで一括リネームするmmvコマンドを作りました。

itchyny.hatenablog.com

github.com

mmvはリネームの依存関係を解析して順番を決定します。例えば

a => b
b => c

というリネームを愚直に上から実行すると、ファイルbが消えてしまいます。 mmvはリネーム先がリネームの対象となっている場合は、そちらのリネーム (上の例では b => c) を先に実行します。もし

a => b
b => c
c => a

のようにリネームが循環している場合は、一時的なパスに一旦退避してからリネームします。

a   => tmp
c   => a
b   => c
tmp => b

このツールを作ったときはこれで機能的には十分だと思っていましたが、去年の12月に面白いissueが立ちました (#11)。 mmv $(find .) のようにディレクトリツリーを対象にするとうまく動かないというのです。

a   => b
a/x => b/x
a/y => b/z
a/z => c/z

mmvはリネームの対象の中でパスが他のパスのディレクトリとなっているケースは想定していませんでした。リネームを実行すると以下のような問題が起きてしまいます。

a/x => b/x を a => b より先に実行してしまうと、最初のリネームが先に b/ を作成してしまうので a => b が失敗し、a/ 以下の他のファイルは移動されない
a => b を a/z => c/z より先に実行してしまうと、 a/z はすでに b/z に移動しているので対象ファイルが見つからない

この問題を1か月ほど悩んだ末に、先日ようやく実装することができました。

移動先の浅いパスのリネームから順番に行う。これでリネーム先のディレクトリが先に作られてしまう問題を修正。
親ディレクトリがリネームされる場合は、一時的なパスに先に退避する。
- ただし、直近の親ディレクトリと同じ場所にリネームされる場合は、ディレクトリの移動に任せる

例えば以下のようなリネームを行う場合は

a   => b
a/x => b/x
a/y => b/z
a/z => c/z

mmvは以下の順番でリネームを行います。

a/y  => tmp1
a/z  => tmp2
a    => b
tmp1 => b/z
tmp2 => c/z

ディレクトリ a のリネームが行われるので、その中のファイルを一旦退避しています。ただし a/x => b/x は a => b のリネームに任せることで、リネームの数を抑えています。

このように書いてしまえばシンプルな処理に見えますね。しかし、mmvは親ディレクトリの解析と、先述の依存関係の解析を同時に行います。また、愚直に実装してしまうと O(n²) になってしまうので、先にディレクトリの深さでパスをグルーピングする実装を行いました。色々なケースを想像していると重い腰が上がらず、1か月もかかってしまいました。

このツールを作ったときは機能を増やさない信念と称してツールの機能が膨れ上がらないようにと思っていました。実際、git mv したいとか -dry-run したいとか言う要望は、mmv の信念にはそぐわないので却下しています *1。しかし親ディレクトリの解析はmmvの中で実装するのに適切な機能であり、また面白そうなチャレンジだったので実装しました。

昨日リリースしたv0.1.3よりこの機能をお使いいただけます。是非お使いください。現場からは以上です。

*1:git mvは外部コマンドを開く必要があり、mmvは複数のrename(2) に過ぎないという考え方と合わない。-dry-run はmmvのインタラクティブ性と合わない。

2020-12-31

2020年を振り返って

雑記

今年はコロナ禍でリモートワークになり、生活リズムが大きく変わりました。年末も帰省を控えているため、人生で初めて実家で過ごさない正月となります。年末年始を京都で過ごすのは初めてで少しわくわくしています。仕事は担当サービスのコンテナ化やAWS化などを手伝いながら、インターン講師をやったり、プロジェクトのタスクマネジメント的なことをやってました。むずかしいですね。

OSS活動としてはmmvを作ったり、HomebrewのインストーラーをBashに書き直したり、gojqのパーサーを書き直したり、timefmt-goやrassemble-goを作ったりしていました。gojqはJSONを出力する処理を自前で書くことでjqコマンドの3倍以上のパフォーマンスを出せるようになりました。他には、jqのリポジトリをwatchしてissueの打ち返しをしたり、Vim 9 scriptの仕様に関するフィードバックを行ったりしていました。

秋頃に競技プログラミングにハマり、AtCoderをRustで解いていました。昔やっていた頃よりもツールやライブラリが揃っていて参加しやすくなったと感じました。しかしgojqでやることが増えたら自然と競技プログラミングをやる時間も減ってしまいました。なかなか続かないですね… Rustをもっと書きたいんですがどうしても時間がかかってしまってGoを選んでしまいます。

9月に家族で天橋立に行きました。200kmほど運転を担当し、天気が良くて気持ちよかったです。しかし連休に行ったのもありとても混雑していて大変でした。12月には京都水族館に行きました。クラゲが可愛かったです。

将棋が強くなりたくて対局を観たりアプリをやったりしていたのですが、最近は時間がなくてやれてません。将棋鑑賞、なかなか大変な趣味です。夏頃には筋トレグッズを買ってしばらくやっていましたが、これも続きませんでした。来年こそは続けるんだ。YouTubeをPremiumにしてから結構見るようになりました。しみさん夫婦・るかちゃんねる・はるまきちゃんねるあたりが好きです。

今年の良かったアニメは『アサルトリリィ BOUQUET』『安達としまむら』『かぐや様は告らせたい？～天才たちの恋愛頭脳戦～』『魔女の旅々』『ストライクウィッチーズ ROAD to BERLIN』あたりですね。アサルトリリィはOP・EDもWEBラジオも赤尾ひかるさんも良かったです。舞台をやっているからなのか、声優さんたちが仲がいいですね。『魔女の旅々』の本渡楓さんもよかったです。ドラマもかなり見ていて『危険なビーナス』『七人の秘書』『テセウスの船』『監察医朝顔』『アリバイ崩し承ります』あたりがよかったです。映画は『TENET』が最高でした。クリストファー・ノーランは常に最高を届けてくれます。

来年はいい一年になりますように。

伊東閑「責任感と罪悪感はきちんと分けないと、身を滅ぼすわよ」
アサルトリリィ BOUQUET 第11話