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を楽しんでいきたいと思います。

一括リネームツール 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/xa => b より先に実行してしまうと、最初のリネームが先に b/ を作成してしまうので a => b が失敗し、a/ 以下の他のファイルは移動されない
  • a => ba/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/xa => 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年を振り返って

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

OSS活動としてはmmvを作ったりHomebrewのインストーラーをBashに書き直したりgojqのパーサーを書き直したりtimefmt-gorassemble-goを作ったりしていました。gojqJSONを出力する処理を自前で書くことで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話

Vimの古いバージョンをコンパイルし高速にbisectする (macOS編)

Vimプラグインを作っていると、特定の機能がどのバージョンで実装されたか調べるのが難しいことがあります。 ヘルプ (:h vim7, :h vim8) や git log のコミットメッセージから探せば多くのケースでは見つかるのですが、うまく検索できなくて見つからないこともあります。 また、急にテストが古いVimで落ちるようになったときに、どの機能が原因で落ちているのかつかめないこともあります。

確実な方法は git bisect すれば良いのですが、これには2つの問題があります。

後は純粋な興味もあって、古いバージョンのビルド済みバイナリーを作っておこうと思い立ちました。 しかし1パッチごとにビルドするのはあまりに大変です。 そもそも当時のコンパイルでもビルドできず、その後のパッチで直ったりするバージョンがあるので、どうしてもビルドできないバージョンは存在します。 後はディスク容量の問題もあります。

まずは以下のようなスクリプトで100パッチごとにビルドしてみることにしました。 macOS・clang 12.0.0 (clang-1200.0.32.27) で v7.3.000 から v8.2.2000 までの103バージョンをビルドすることができました。

vim-backcompile.sh

#!/bin/bash
set -euxo pipefail

if [[ ! -d /tmp/vim ]]; then
  git clone https://github.com/vim/vim.git /tmp/vim
fi
cd /tmp/vim

BACKUP_DIR=/tmp/vim-backup
mkdir -p "$BACKUP_DIR"

while true; do
  git restore .
  while ! git describe --tags | grep -E '^v\d[.]\d(?:[.]\d(?:\d*00)?)?$'; do
    git reset --hard HEAD^
  done
  gsed -i '/sizeof(uint32_t) != 4/,+1s/exit/return/' src/auto/configure # v8.2.1119
  gsed -i '/if (\(p\|res\|e1.*\) [!=]= NUL)/s/NUL/NULL/g' src/*.c # v8.0.0046
  gsed -i '/#define VV_NAME/s/, {0}$//' src/eval.c # v7.4.1648
  gsed -i '/static struct vimvar/,+4s/dictitem_T/dictitem16_T/;/char\s*vv_filler.*/d' src/eval.c # v7.4.1648
  if ! git grep 'struct dictitem16_S' src/structs.h >/dev/null; then
    gsed -i '/typedef struct dictitem_S dictitem_T;/a struct dictitem16_S {\n  typval_T di_tv;\n  char_u di_flags;\n  char_u di_key[17];\n};\ntypedef struct dictitem16_S dictitem16_T;' src/structs.h # v7.4.1648
  fi
  gsed -i 's/__ARGS(\(.*\))/\1/' src/proto/os_mac_conv.pro # v7.4.1202
  gsed -i 's/!builtin_first == i/(!builtin_first) == i/' src/term.c # v7.4.914
  gsed -i '/extern int sigaltstack/s/^/\/\//' src/os_unix.c # v8.0.1236
  gsed -i '/+multi_byte/,+6s/FEAT_BIG/FEAT_NORMAL/' src/feature.h # v7.3.968
  if ! ./configure; then
    make distclean || :
    rm -f auto/config.cache
    ./configure
  fi
  make -j8
  src/vim --version
  MAJOR=$(./src/vim --version | head -n 1 | awk '{ print $5 }' | tr -d '\n')
  MINOR=$(./src/vim --version | grep patch | awk '{ print $3 }' | sed -e 's/^[0-9]*-//g' | tr -d '\n' || :)
  cp src/vim "$BACKUP_DIR/vim-$MAJOR.$(printf "%04d" "$MINOR")"
  git reset --hard HEAD^
done
  • ビルドが通っても起動できない事があったので、 src/vim --version で起動チェックを行う
  • 変わっていくソースコードにパッチファイルは使いにくいので、今のコンパイラコンパイルできない箇所は sed で雑にパッチを当てる。

実行ファイルのサイズが少しずつ増える様子が分かりました。

今は上のスクリプトを少し変えて、25パッチごとにビルドして実行ファイルを保存しています。 ビルドできなかったのは 8.0.0750 (8.0.0751で修正), 7.4.1625 (7.4.1626で修正) のみでした。

ビルド済み実行ファイルが揃ったので、次はこれを使ってbisectします。

vim-bisect.sh

#!/bin/bash
set -euo pipefail

script_dir="$(cd "$(dirname "${BASH_SOURCE[0]}")" >/dev/null 2>&1 && pwd)"

VERSIONS=($(cd "$script_dir" && ls vim-[0-9]* | sort --version-sort --field-separator=.))

find_index() {
  for i in "${!VERSIONS[@]}"; do
    if [[ "${VERSIONS[$i]}" = "$1" ]]; then
      echo "$i"
    fi
  done
}

exec_command="${1:?specify bisecting command}"
low_version="${2:-${VERSIONS[0]}}"
high_version="${3:-${VERSIONS[${#VERSIONS[@]}-1]}}"
if [[ ! "$low_version" =~ ^vim- ]]; then
  low_version="vim-$low_version"
fi
if [[ ! "$high_version" =~ ^vim- ]]; then
  high_version="vim-$high_version"
fi
low_index="$(find_index "$low_version")"
high_index="$(find_index "$high_version")"

test_version() {
  env VIM="$script_dir/$1" bash -c "$exec_command"
}

if test_version "$high_version"; then
  echo "$high_version is good"
  exit 1
fi
if ! test_version "$low_version"; then
  echo "$low_version is bad"
  exit 1
fi

bad_version="$high_version"
while [[ "$low_index" -lt "$high_index" ]]; do
  mid_index="$(((low_index + high_index) / 2))"
  version="${VERSIONS[$mid_index]}"
  if test_version "$version"; then
    echo "$version: good"
    low_index="$((mid_index + 1))"
  else
    echo "$version: bad"
    high_index="$((mid_index))"
    bad_version="$version"
  fi
done

echo "$bad_version is the bad version"

$VIM という環境変数に実行ファイルのパスを入れるので、 vim-bisect.sh '! env THEMIS_VIM=$VIM /tmp/vim-themis/bin/themis --reporter spec >/dev/null' のようなコマンドで vim-themis を使ったテストを回すことができます。

すべてのパッチバージョンに対する実行ファイルを用意できるわけではないので、git bisect みたいにこのパッチがbad commitというところまではいけませんが、50パッチや25パッチの範囲くらいならコミットログに全部目を通すことはできます。 ビルド済みbisectはめちゃくちゃ便利なので、ぜひ試してみてください。

おしまい

Vimのパッチ存在確認処理を速くした

昨日Apple Eventを待機しながらVimのコードを眺めていたら、なんだか香ばしい匂いのするコードを見つけてしまいました。

/*
 * Return TRUE if patch "n" has been included.
 */
    int
has_patch(int n)
{
    int        i;

    for (i = 0; included_patches[i] != 0; ++i)
        if (included_patches[i] == n)
            return TRUE;
    return FALSE;
}

ペロッ… こ、これは、線形探索!

Vimは、メインのブランチのすべてのコミットでパッチバージョンが上がっていく方式をとっています。 プラグインが新しい機能を使いたい時に、ユーザーが使っているVimに特定のパッチが入っているかをチェックする必要があります (関数やイベントなど機能が入っているかを直接チェックすることができる場合もありますが、機能が入ってもバグっていることがありますし、直接チェックできない機能もあります。その時はパッチバージョンでチェックする必要があります)。 こういうプラグイン実装者のために、 has('patch-8.2.1200') のように関数 has() でパッチバージョンが含まれているかをチェックすることができます (詳しくは :h has-patch)。

含まれているパッチバージョンは included_patches という配列にすべて羅列されており、これを線形に探索しているコードです。 しかし included_patches は必ず大きい番号順にソートされており、二分探索したほうがほとんどのケースでお得なはずです。 ということで昨日シュッとコードを書いて、出してみました。

github.com 素朴な二分探索です。

/*
 * Return TRUE if patch "n" has been included.
 */
    int
has_patch(int n)
{
    int        h, m, l;

    // Perform a binary search.
    l = 0;
    h = (int)(sizeof(included_patches) / sizeof(included_patches[0])) - 1;
    while (l < h)
    {
        m = (l + h) / 2;
        if (included_patches[m] == n)
            return TRUE;
        if (included_patches[m] < n)
            h = m;
        else
            l = m + 1;
    }
    return FALSE;
}

朝起きたら、無事 v8.2.1973 として取り込まれていました。修正なしで入っていると嬉しいですね。 github.com

ここの処理は大昔から変わっておらず (少なくとも2004年からずっと同じコードでした。もっと遡れるかもしれません) で、今まで見過ごされていたのが不思議なくらいです。 Vimがまた少し速くなってよかったですね。