AtCoder Beginner Contest 040

A - 赤赤赤赤青

n個の中の特定の一つのブロックを隣り合うブロックの入れ替えによって両端のいずれかに移動する最小の回数。

main :: IO ()
main = getContents >>= print . (\[n, x] -> min (x - 1) (n - x)) . map read . words

B - □□□□□

n個のタイルをどれだけたくさん使ってできる限り正方形に並べられるか。指標は二辺の差と使い切れなかったタイルの数の和が最小のもの。

main :: IO ()
main = readLn >>= print . solve

solve :: Int -> Int
solve n = minimum [ abs (l - k) + n - k * l | k <- [1..round (sqrt (fromIntegral n))], let l = n `div` k ]

C - 柱柱柱柱柱

柱を端から端まで飛び移っていく。一本飛ばしでも飛べるのだが、柱を飛び移るときに高さが違うだけ疲れるので疲れを最小にしたい。

import Data.List (foldl')

main :: IO ()
main = print . solve . tail . map read . words =<< getContents

solve :: [Int] -> Int
solve (a0:as) = fst $ fst $ foldl' f ((0, a0), (0, maxBound)) as
  where f ((x, ax), (y, ay)) az = (min (x + abs (ax - az), az) ((y + abs (ay - az)), az), (x, ax))

Array使ってDPしてもいいけど、せいぜい最後の二本の情報を持っていればよいのでそこまでする必要はないかな。一本飛ばしまでしかできないからそうだけど、何本飛ばしでもできて、過去の全てを使って新しいところの値が決まるという問題ならDPしたほうがよさそう。

D - 道路の老朽化対策について

重み付き無向グラフ上で、ある重み以上の道しか通れない時にどれだけの数のノードに辿り着けるか。

import Control.Monad (replicateM)
import Data.Graph (buildG, reachable)

main :: IO ()
main = do
  [n, m] <- getInts
  abys <- replicateM m (toTriple <$> getInts)
  q <- readLn
  vws <- replicateM q (toTuple <$> getInts)
  mapM_ print $ solve n abys vws

getInts :: IO [Int]
getInts = map read . words <$> getLine

solve :: Int -> [(Int, Int, Int)] -> [(Int, Int)] -> [Int]
solve n abys vws = [ length $ reachable gr v | (v, w) <- vws, let gr = buildGraph w ]
  where buildGraph w = buildG (1, n) $ concat [[(a, b), (b, a)] | (a, b, y) <- abys, y > w]

toTuple :: [a] -> (a, a)
toTuple xs = (head xs, xs !! 1)

toTriple :: [a] -> (a, a, a)
toTriple xs = (head xs, xs !! 1, xs !! 2)

すみません、Largeは通らないです。50点は取れた。本当は、最初に各ノード間の最小の重みを計算しないといけなさそうだけど、元気がなかった…

HHKBを買いました・他近況報告

4月頃から仕事中に両手の小指に痛みを感じるようになり、コードを書いては少し手を休めないとつらくなっていました。意図的に小指を使わないように打鍵したり、比較的指を使わないレビュー作業を合間に挟んだりしていたのですが、痛みは出てきたり引いたりという状況が続いていました。特に家に帰ってから再度キーボードの上に手を置くと、また痛みを感じたり、痛くなくてもあまりコードを書くのがはかどらない状況が続いていました。

MacBook Airは六年前から使い続けています。大学の時に買ったMacBook Airが今でも現役で動いています。手に馴染んだキーボードとキー配列とキーストロークを六年も使ってきたので、ここに来てMacのキーボードがつらくなるとは思っていませんでした。

どのキーボードを使うかかなり悩んだのですが、やはり定評のあるHHKBがいいのだろうなぁと思い、特に店舗で試したりすることもなく思い切って購入しました。広く評価されていることは知っていたので、手に馴染まなくて後悔するかもしれないという気持ちはあまりありませんでした。

家で二週間ほど使い、会社に持って行って一週間ほど使ったところ、かなり手に馴染むようになってきました。おかげさまで手の痛みも引いていき、かなり楽にタイピングできるようになりました。それでも使い始めて一週間は、深いストロークに苦しめられました。ずっとMacのキーボードに慣れてきてましたから。最近では柔らかいキータッチにも慣れて、快適に過ごしています。

ここ二か月ほどは、Vimソースコードに没頭していました。これまで自らの道具は自ら磨くという信念の元、様々なVimプラグインプラグインマネージャーを作ってきました。そして、私の関心は次第にVimというエディターそのものに向けられ始めていました。3月からVimソースコードを読み始め、独自のコマンドを作ったりして感覚を掴み、4月に入ってからはVim scriptの実行系のリファクタリングにとりかかっていました。実行系から構文解析処理を分離して構文木をキャッシュするという作業を進めていたのですが、あまりにも進捗が悪く、だんだんモチベーションも下がってきたため、途中で投げ出してしまいました。evalNの関数を構文解析と評価器に分けるだけなのですが、それらの関数が再帰していることや、handle_subscriptあたりの処理が複雑すぎて挫折しました。しばらくして興味が戻ってきたら再開したいと思います。

Vimの複雑なコードを前に立ち止まってしまった後はしばらくコードを書いていなかったのですが、また別のことに興味が向き始めました。最近は画像処理を始めました。各ファイルフォーマットの構造や、圧縮、類似画像検索など、興味深いテーマがたくさんあります。まだ素人同然なのですが、まとまってきたらエントリー書きたいなと思っています。

最近どんどん暑くなってきていますね。以前住んでいたところはマンションの最上階の南向きで、夏は陽射しが強く、また屋上からの熱も加わって、すぐに温度が上がって嫌な朝を過ごしていました。今は最上階でもなく、また西向きなので朝は快適です。その代わり昼を過ぎると日光が差し込んで、ぐんぐん室温が上がります。実家は夏でも扇風機で過ごす環境だったので、クーラーはかなり苦手です。かつて体調を崩したこともあるので、腕から汗が出始めてから付けるようにしています。今日は曇っていて、快適な室温です。

しまなみ海道を走ってきました

大学時代の友人に誘われて、しまなみ海道を自転車で走ってきました。

ゴールデンウィークということもあり、福山で乗り換えるとちらほら自転車乗りたちが見え始め、尾道ではたくさんの人たちが自転車を組み立てていました。9:30ごろ尾道からフェリーに乗り向島に渡り、サイクリングを始めました。 天気はとても良く、気持ちの良い潮風を感じながらひたすら走りました。特に島々をつなぐ橋は美しく、一生懸命写真を撮りました。 f:id:itchyny:20160504125313j:plain 道は海岸に沿って通っているのですが、橋がかかっているのは少し高いところなので、橋を渡るたびに坂道を登らなければなりません。その坂道に徐々に体力を奪われていきました。 f:id:itchyny:20160501135220j:plain 大三島に渡ったところにサイクリストの聖地という石碑がありました。2つの丸は自転車を表しているのでしょうか。 f:id:itchyny:20160501162844j:plain 来島海峡を渡ることにはヘトヘトになっていましたが、連なる美しい吊り橋を支える巨大なボルトに心躍らせながら、最後の力を振り絞って走りました。 f:id:itchyny:20160504131245j:plain 今治駅に着いたのは17:15でした。途中のお食事処でまったりしていたので、かなり遅くなってしまいました。Stravaのタイムは4時間半でした。

登り坂に体力を奪われ、途中でかなり疲れてしまったので、もっと体力と持久力をつけて長く速く走れるようになりたいと思いました。 f:id:itchyny:20160501215405j:plain 夜は道後温泉でゆっくり疲れをとりました。 おしまい。

端末の上で動かして遊べる!迷路コマンドをGo言語で書きました!

迷路で遊びたくなったので作りました。Goで書いています。

github.com

maze

Homebrewをお使いの方は、次のコマンドでインストールしてください。

brew install itchyny/tap/maze

そうでない方は、次のコマンドでビルドしてインストールするか、

go get github.com/itchyny/maze/cmd/maze

あるいは https://github.com/itchyny/maze/releases よりバイナリーを落としてご利用ください。

mazeコマンドは、ランダムな迷路を出力します。

maze

maze

--interactive引数を渡すと、カーソルを動かして迷路を遊ぶことができます。

maze --interactive

maze

--format colorを渡すと迷路が綺麗に表示されます。--width--heightなどで迷路のサイズを制御することができます。

maze --width 20 --height 10 --format color

maze

sキーを押すと、解答 (solution) の表示をトグルすることができます。 maze

端末の文字サイズを小さくすると、複雑な迷路を楽しむことができます。 maze

ぜひお楽しみください!

これからは少し実装の話をしようと思います。

迷路の表現

迷路の構造体の定義は次のように書きました。

const (
    Up = 1 << iota
    Down
    Left
    Right
)

type Maze struct {
    Directions [][]int
    Height     int
    Width      int
    Start      *Point
    Goal       *Point
}

type Point struct {
    X, Y int
}

Maze構造体のDirectionsフィールドには、迷路の道の情報が入っています。それぞれのセルには、道が空いている方向の情報がバイナリー表現で格納されています。例えば Down は2進数で 10 で、Right1000 なので、下と右が空いているセルは2進数で 1010、つまり int10 と表現されます。バイナリー表現だとフラグを立てるのは|= (bitwise or)、道があるかチェックするのは& (bitwise and)、道をトグルするのは^ (bitwise xor)で書くことができます。それにしてもGoのiotaは便利ですね。

Directionsには、迷路の道に加えて、正解の道順も格納されています。下から1ビット目から4ビット目が迷路の道に利用され、5ビット目から8ビット目が正解の道に利用されています。さらに、9ビット目から12ビット目が、ユーザーのカーソルが辿った道に利用されています。

迷路の生成と解答

迷路の生成には、深さ優先探索を使いました。

  1. 隣の点をランダムに選び、道を作り点を進めてスタックに積む。前に進めるまでこれを繰り返す。
  2. 前に進めなくなったら、スタックからランダムに点を選び、スタックから落して1を繰り返す。

実際のコードは次のようになっています。

func (maze *Maze) Next(point *Point) *Point {
    neighbors := maze.Neighbors(point)
    if len(neighbors) == 0 {
        return nil
    }
    direction := neighbors[rand.Int()%len(neighbors)]
    maze.Directions[point.X][point.Y] |= direction
    next := point.Advance(direction)
    maze.Directions[next.X][next.Y] |= Opposite[direction]
    return next
}

func (maze *Maze) Generate() {
    point := maze.Start
    stack := []*Point{point}
    for len(stack) > 0 {
        for {
            point = maze.Next(point)
            if point == nil {
                break
            }
            stack = append(stack, point)
        }
        i := rand.Int() % ((len(stack) + 1) / 2)
        point = stack[i]
        stack = append(stack[:i], stack[i+1:]...)
    }
}

単純ですね。スタックと書きましたが、端から取り出す必要はありません。経験的に前の方から取ると迷路がいい感じになるような気がするので、上のようなコードになっています。

迷路を解くときは二本のスタックを使いました。

  1. スタート地点から開始する。スタックと解答スタックにスタート地点を入れておく。
  2. 迷路の道があり移動できる隣接点をすべてスタックに積む。
  3. スタックをpopして次の点とする。
  4. その点が解答スタックの最後と繋がっていなければ、その点まで解答スタックをpopする。
  5. 解答スタックに次の点をpushして2に戻る。ゴールに着いたら修了。

具体的なコードはリポジトリを参照してください。最初は再帰で書いていましたが、なんとなく再帰よりもスタックを使って書いたほうが、手続きが分かって良いなぁと思ったのでそういう実装になっています。

ターミナルUI

最初は標準出力にprintfするだけで、遊ぶときは迷路を目で追うしかありませんでした。しかしそれでは面白くないので、キー入力を受け付けて遊べるようにしたい。Go言語でターミナル上のUIを作ろうと思ったのは初めてでしたが、termbox-goを使ってみると簡単でした。

github.com

mazeコマンドは引数がないと標準出力に表示してすぐに終了し、--interactiveをつけると矢印キーで遊べるようになっています。これはtermbox.Close()deferをつけるかつけないかという違いがあります。以下は実際のソースコードの一部を簡略化したものです。

func action(ctx *cli.Context) {
    termbox.Init()
    config := makeConfig(ctx)
    maze := createMaze(config)
    if config.Interactive {
        defer termbox.Close()
        interactive(maze, config.Format)
    } else {
        termbox.Close()
        maze.Print(config.Output, config.Format)
    }
}

インタラクティブモードではないときは、termbox.Close()を直接呼び、迷路を出力して終わりです。

出力先が二種類あると、ライブラリー側がどういう関数を提供すればいいか、少し頭を捻る必要があります。termboxを用いて端末に表示する場合、termbox.SetCellという関数を用いて一文字ずつ場所と色を指定しなければなりません。迷路の出力は (解答の描画も含め)、わりと複雑なタスクなので、迷路ライブラリーが提供するべき機能です。ユーザー (これもわたしなんですが) は迷路を標準出力にもtermboxにも表示したいと考えています。コマンドを実装する場所ではtermboxを利用しますが、迷路ライブラリー (maze.go) ではtermboxに依存したくありません。

今回わたしは、出力channelをもらってそこに流しこむことにしました。迷路を書き込む関数はchan stringをもらってそこに迷路を出力します。

func (maze *Maze) Write(writer chan string, format *Format) {

    // fmt.Print(str) するかわりに
    writer <- str

    // 例えば壁なら
    writer <- "##"

    // 例えば道なら
    writer <- "  "

    // 最後を知らせる
    writer <- "\u0000"
}

この関数を使って、標準出力、あるいはファイル出力に流すのはとても簡単です。

func (maze *Maze) Print(writer io.Writer, format *Format) {
    // 出力を待ち受けるchannelを作る
    strwriter := make(chan string)
    go maze.Write(strwriter, format)
    for {
        str := <-strwriter
        switch str {
        // この文字が来たら修了
        case "\u0000":
            return
        // 流れてくる文字列を単純にFprintするだけ
        default:
            fmt.Fprint(writer, str)
        }
    }
}

上記の関数は迷路ライブラリー (maze.go) が提供してくれます。

さて、迷路ライブラリーはchannelに出力を流すWrite関数を提供してくれています。termboxに迷路を表示したいと思ったライブラリー利用者 (これもわたし) は、このWrite関数をtermboxをうまく繋いでやる必要があります。mazeコマンドの実装は、だいたい次のようなコードになっています。

func interactive(maze *maze.Maze, format *maze.Format) {
    // 略
    strwriter := make(chan string)
    go printTermbox(maze, strwriter)
    maze.Write(strwriter, format)
    // 略
}

func printTermbox(maze *maze.Maze, strwriter chan string) {
    // 表示位置
    x, y := 1, 0
    for {
        str := <-strwriter
        switch str {
        // 終了したらFlushする・位置をリセット
        case "\u0000":
            termbox.Flush()
            x, y = 1, 0
        // そうでなければ、一文字ずつSetCellする
        default:
            for _, c := range str {
                if c == '\n' {
                    x, y = x+1, 0
                } else {
                    termbox.SetCell(y, x, c, termbox.ColorDefault, termbox.ColorDefault)
                    y = y + 1
                }
            }
        }
    }
}

改行の時の処理とかがミソですね。色付けとかに対応するため、実際の実装はもっと複雑になっています。

言われてみればそりゃそれで動くでしょうねと思われるかもしれませんが、実際にこの方法で、それまでずっと標準出力に出力して終わっていたコマンドが、termboxを使って表示できるようになった瞬間は、とても嬉しく思いました。ライブラリーとしての責務は守り (例えば迷路ライブラリーをtermboxに依存させるなんてことはせず)、やっていることは単純 (chan stringに流すだけ) で過度な抽象化にも走っていない、バランスのよい解決法だと思います。

テスト

迷路を出力するだけのコマンドですので、単体テストみたいな大げさなテストコードは書いていません。そのかわりに、mazeコマンドにいくつか引数を渡したものが書いたshell scriptと、それを実行した時に期待される出力を用意し、scriptの実行結果と比較するテストをしています。テストの一例は次のようになっています。以下のようなテストが20程度あります。TravisCIでテストしています。

~/.go/src/github.com/itchyny/maze cat test/default.sh test/default.txt
maze --seed 0 --width 10 --height 10

  ##########################################
  S       ##      ##                      ##
  ######  ##  ##  ##  ##  ##############  ##
  ##      ##  ##      ##  ##  ##      ##  ##
  ##  ######  ##########  ##  ##  ######  ##
  ##  ##      ##          ##  ##          ##
  ##  ##  ######  ##########  ##  ######  ##
  ##      ##      ##              ##      ##
  ##########  ######  ##############  ##  ##
  ##      ##  ##  ##  ##  ##          ##  ##
  ##  ##  ##  ##  ##  ##  ##  ##########  ##
  ##  ##      ##  ##      ##          ##  ##
  ##  ##########  ##########  ######  ######
  ##  ##      ##                  ##      ##
  ######  ##  ##  ######################  ##
  ##      ##          ##      ##          ##
  ##  ##############  ##  ##  ##  ##########
  ##      ##      ##      ##  ##          ##
  ######  ##  ##  ######################  ##
  ##      ##  ##                           G
  ##########################################

デフォルトではランダムな迷路が生成されてしまい、テストしようがありません。テストでは上記のように、--seed 0のようにしてrandom seedを固定しています。この引数の値が同じであれば、mazeコマンドは常に同じ迷路を生成して出力します。--seed引数が与えられなければ、時刻から適当に初期化します。

裏話

実を言うと、迷路コマンドを書くのはこれが初めてではありません。かつてC言語で実装してブログを書いたことがありました。

itchyny.hatenablog.com

このとき書いたコマンドは迷路を解く事ができず、またカーソルを動かして遊ぶこともできないものでした。なぜか「迷路の圧縮」という謎の課題に夢中になり、二次元の迷路を一次元文字列で圧縮・解凍するコードを一所懸命書いていました。autotoolsの勉強にはなりましたが、使いみちのない謎機能にのめり込んでしまったがためにコードもめちゃくちゃになってしまい、手がつけられなくなっていました。

Go言語はcliツールを簡単に書くことができ、またターミナル上で動くゲームもいくつか実装されていることから、インタラクティブに遊べる迷路コマンドが欲しいと思うようになりました。3月の半ばくらいに迷路の生成・解答コードを書き、標準出力に吐き出せた時点で一時期興味が薄れてしまっていました。しかし、前の土曜日でtermboxを触り始めて、上記のchan string使う方法を思いついて実装し、日曜日にテストを用意しコマンドのフラグを整え、昨日READMEやスクリーンショット、TravisCIとの連携とこの記事を用意し、本日リリースしました。

まとめ

Go言語で迷路コマンドを作りました。迷路の実装やchannelを用いた出力の切り替え、random seedを外から注入できるようにしておいてテストする方法などを説明しました。

github.com

息抜きに迷路で遊びたくなったらお使いください。

はてなでは、自分が興味を持った課題には全力でコードを書く、意欲あるエンジニアを募集しています。

hatenacorp.jp

Vimの標準プラグインmatchparenが遅かったので8倍くらい速いプラグインを作りました

コードを書いているとき、対応する括弧はとても大事です。エディターの中でカーソル下の括弧がどこと対応しているかが一目でわかると便利です。Vimの標準のプラグインにmatchparenというプラグインがあります (:h matchparen)。

私もずっとmatchparenのハイライトに依存してコードを書いてきました。しかし、だんだんこのプラグインのパフォーマンスが気になるようになってきました。標準プラグインなのですがわりと重い処理をやっていると思います。対応括弧をハイライトするプラグインによって余計な処理が行われて、コーディングの妨げになってはあまりよくありません。

最初はパッチを送ることも考えましたが、プロファイルを取った結果、どうしてもある機能を実現するために必要な処理が重くて時間がかかっていることに気が付きました (3日くらい前のことです)。その機能を落とすのは標準プラグインには受け入れられないので、大体同じような機能を持つ新たなプラグインを書き、それに乗り換えることにしました。

github.com

f:id:itchyny:20160330222736g:plain あまりいい名前が思いつかなかったので、デフォルトプラグインのmatchparenをひっくり返してparenmatchにしました (雑…)。

インストールするときは、例えばNeoBundleのお使いの方は次のようにしてください。

let g:loaded_matchparen = 1

NeoBundle 'itchyny/vim-parenmatch'

一行目はこのプラグインの設定ではなくて、標準のmatchparenを使うのをやめる設定です。そうしないとパフォーマンス上の魅力はないです。

プロファイルと取った結果、parenmatchは標準のmatchparenプラグインと比べると8倍以上速いということが分かっています。 gist.github.com 適当なVim scriptのコードの上でカーソルを移動して回るスクリプトを動かした時のプロファイル結果です。このプロファイル結果から、matchparenのどこが重いのかが見えてきます。

シンタックスを取得して文字列などをきちんとスキップする

まず、次の三行が重そうです。

  535              0.006009   let s_skip = '!empty(filter(map(synstack(line("."), col(".")), ''synIDattr(v:val, "name")''), ' . '''v:val =~? "string\\|character\\|singlequote\\|escape\\|comment"''))'
  535              1.424980   execute 'if' s_skip '| let s_skip = 0 | endif'
  535              1.590589     let [m_lnum, m_col] = searchpairpos(c, '', c2, s_flags, s_skip, stopline, timeout)

これは何をやっているのでしょうか。例えば次のようなコードを考えてみましょう。

var x = [ [ "[  ]  [" ], [ "]  [  ]" ] ]

正確に括弧の対応を調べるには、文字列の中かどうか判定しなければなりません。文字列の外側の括弧は外側の括弧と対応するでしょうし、文字列の中の括弧は中同士で対応することが期待されます。それを正確に調べるには、synIDattrという関数を使ってシンタックスを調べて、文字列っぽいシンタックスならスキップしないといけません。

ところが、synIDattrシンタックスを取得したり、その結果を正規表現にマッチさせたりするのは比較的重い処理です。しかも、現実のコードで上記のようなコードがそう頻繁にあるわけではありません。決してないわけではありませんが、多くのコードでは問題ありません。そんな少ないケースのために、常に処理が重くなっていては良くないですよね。

私の作ったparenmatchプラグインでは、上のように文字列の中かどうかを判定しないと正確に対応括弧が取れないケースには対応していません。バッサリ切り捨てました。その代わり、このチェックをしないことによってかなり速くなっています。特殊ケース (というほど特殊とはいえませんが、コード上ではそんなにない) のために全体のパフォーマンスを下げるような処理は気に入らなかったのです。それでももし、やっぱり正確に文字列の中かちゃんと判定して欲しいという場合は、標準のmatchparenプラグインをお使い下さい。

カーソル下の文字を取得するのに正規表現を使っている

次に気になるのは以下の行です。

10001              0.484219   let matches = matchlist(text, '\(.\)\=\%'.c_col.'c\(.\=\)')

\%c という指定行にマッチする正規表現を使いつつ、カーソルの下と一つ左の文字を取得しています。それだけで、と思われるかもしれませんが、正規表現を作り、キャプチャーを作りながらマッチさせるという処理はやはり重いようです。

parenmatchでは普通に文字列のインデックスアクセスで取得しています。

matchpairsの分割を毎回行っている

三番目に気になったのは、この行です。

10001              0.391124   let plist = split(&matchpairs, '.\zs[:,]')

基本的に、matchpairsの値はそう頻繁に変わるものではありません。カーソルをちょっと動かしただけでコロコロ変わるものじゃないですよね。そういう値を、しかも正規表現で毎度分割するのは効率のよい処理ではありません。このオプションがよくセットされる場所としては、vimrcの中でグローバルな値がセットされているか、あるいは何らかのファイルタイプでローカルに変更されるケースでしょう。

parenmatchでは、予めmatchpairsの値を分割し、更に頻繁に呼ばれる関数の中で使いやすい形に整形してキャッシュしています。

parenmatchの実装

matchparenの重い場所は分かったので、次に私が今回作ってみたparenmatchのコードを見てみましょう。

括弧をカーソルが動く度にハイライトさせようと思ったら、どうしてもカーソルが動く度に呼ばれる関数が必要になります。

augroup parenmatch
  autocmd!
  autocmd CursorMoved,CursorMovedI * call parenmatch#update()
augroup END

この関数はとても頻繁に呼ばれるので、プロファイルを取りながら限界まで小さく実装します。この記事を書いてる時点でのコードは次のようになっています (今後変更される可能性はあります)。

let s:paren = {}
function! parenmatch#update() abort
  let i = mode() ==# 'i' || mode() ==# 'R'
  let c = getline('.')[col('.') - i - 1]
  silent! call matchdelete(w:parenmatch)
  if !has_key(s:paren, c) | return | endif
  let [open, closed, flags, stop] = s:paren[c]
  let q = [line('.'), col('.') - i]
  if i | let p = getcurpos() | call cursor(q) | endif
  let r = searchpairpos(open, '', closed, flags, '', line(stop), 10)
  if i | call setpos('.', p) | endif
  if r[0] > 0 | let w:parenmatch = matchaddpos('ParenMatch', [q, r]) | endif
endfunction

スクリプトローカルな変数 s:paren は次のようにして準備されます。

let s:matchpairs = ''
function! parenmatch#setup() abort
  if s:matchpairs ==# &l:matchpairs
    return
  endif
  let s:matchpairs = &l:matchpairs
  let s:paren = {}
  for [open, closed] in map(split(&l:matchpairs, ','), 'split(v:val, ":")')
    let s:paren[open] = [ escape(open, '[]'), escape(closed, '[]'), 'nW', 'w$' ]
    let s:paren[closed] = [ escape(open, '[]'), escape(closed, '[]'), 'bnW', 'w0' ]
  endfor
endfunction

例えば matchpairs=(:),{:},[:] の時、 s:paren は次のようになります。

{
  '(': ['(', ')', 'nW', 'w$'],
  ')': ['(', ')', 'bnW', 'w0'],
  '{': ['{', '}', 'nW', 'w$'],
  '}': ['{', '}', 'bnW', 'w0'],
  '[': ['\[', '\]', 'nW', 'w$'],
  ']': ['\[', '\]', 'bnW', 'w0']
}

parenmatch#update の処理を追ってみましょう。まず、挿入モードや置換モードかどうかチェックします。そして、カーソル下の文字、挿入モードならばカーソルの一つ左の文字を取得します。文字列のアクセスでインデックスがないときは空文字になります (そういう挙動をヘルプで確認しながらコードを削っていきます)。

  let i = mode() ==# 'i' || mode() ==# 'R'
  let c = getline('.')[col('.') - i - 1]

なぜ挿入モードで一つずらすかというと、閉じ括弧を打った時にその対応括弧がハイライトされてほしいからですね。 f:id:itchyny:20160330222750g:plain 次のコードは、前回のハイライトを消す処理です。この変数がないかもしれないのでお行儀はよくありませんが、コードを短くするために変数チェックもせずにmatchdeleteを呼び、silent!で握りつぶしています。

  silent! call matchdelete(w:parenmatch)

そして、さっきのキャッシュのキーかどうか判定しています。括弧文字でなければこの関数の処理は終わりです。

  if !has_key(s:paren, c) | return | endif

実際、コードを書いていてカーソル下の文字が括弧文字ではない場合は括弧文字である場合よりも多いので、この行までと後で呼ばれる回数はかなり差があります。プロファイルの結果をもう一度貼り付けておきます。

FUNCTION  parenmatch#update()
Called 10000 times
Total time:   0.660151
 Self time:   0.660151

count  total (s)   self (s)
10000              0.110140   let i = mode() ==# 'i' || mode() ==# 'R'
10000              0.149091   let c = getline('.')[col('.') - i - 1]
10000              0.151401   silent! call matchdelete(w:parenmatch)
10000              0.106627   if !has_key(s:paren, c) | return | endif
  535              0.005828   let [open, closed, flags, stop] = s:paren[c]
  535              0.006679   let q = [line('.'), col('.') - i]
  535              0.006086   if i | let p = getcurpos() | call cursor(q) | endif
  535              0.046504   let r = searchpairpos(open, '', closed, flags, '', line(stop), 10)
  535              0.005393   if i | call setpos('.', p) | endif
  535              0.037070   if r[0] > 0 | let w:parenmatch = matchaddpos('ParenMatch', [q, r]) | endif

もちろんコードの言語に依存しますが、90%以上の確率で4行目で終わるでしょう。 もし括弧文字の上にカーソルがある場合は、セットアップしたs:parenから情報を取り、

  let [open, closed, flags, stop] = s:paren[c]

対応括弧を探して、

  let r = searchpairpos(open, '', closed, flags, '', line(stop), 10)

もし見つかれば、ParenMatchというシンタックスで登録します。

  if r[0] > 0 | let w:parenmatch = matchaddpos('ParenMatch', [q, r]) | endif

以上がメインの処理です。途中三行ほど飛ばしました。挿入モードなら、カーソルの一つ左の括弧から検索 (searchpairpos) を開始する必要があります。getcurposでカーソル位置を覚えておき、一つずらし、対応括弧を探した後にカーソルを戻すという処理が入っています。

  let q = [line('.'), col('.') - i]
  if i | let p = getcurpos() | call cursor(q) | endif
  let r = searchpairpos(...
  if i | call setpos('.', p) | endif

以上です。

おわりに

括弧の対応をハイライトする標準プラグインのパフォーマンスが気に入らなかったので、新しくプラグイン作りました。厳密なシンタックスのチェックはスキップしていますが、それなりに快適なはずです。

github.com

ここで、私が昔作ったプラグインをもう一つ紹介しておきます。今回作ったparenmatchと姉妹プラグインと言ってもよいかもしれません。 github.com これはカーソルの下の単語に下線をひくプラグインです。 https://raw.githubusercontent.com/wiki/itchyny/vim-cursorword/image/image.gif

コードを書いている時、カーソルの下の変数が気になるのはどの言語でも同じです。このcursorwordプラグインを入れると、カーソルの下の変数がどこで代入されたり使用されているかがすぐに分かります。しかも、下線なのでそこまで目立ちすぎず、コーディングの邪魔にもなりません。

let g:loaded_matchparen = 1
NeoBundle 'itchyny/vim-parenmatch'
NeoBundle 'itchyny/vim-cursorword'

私はcursorwordのさりげない下線ハイライトに本当に助けられています。

parenmatchとcursorwordを入れて、快適なコーディングライフをお過ごしください。おしまい。