2018/12/25


先日、Go Advent Calendar の記事の中で Language Server について書きました。

Big Sky :: gocode やめます(そして Language Server へ)

はじめに まず始めに言っておかなければなりません。 gocode 今まで本当にありがとう この記事は、Go 言語歴10年になる僕がこれまで愛用してきた Go 言語のコード補完ソフトウェア gocode...

https://mattn.kaoriya.net/software/lang/go/20181217000056.htm

僕は Vim を使っていて、幾らかの言語の開発環境は vim-lsp に移行できたのですが C/C++ を扱うケースだけ vim-lsp に移行できず vim-clang を使ってきました。C/C++ は clangd という Language Server を使うのだけど何故か clangd サーバがうまく補完候補を出してくれませんでした。調べてみると clangd は vim-clang の様に .clang ファイルを読み取ってくれず、compile_commands.json というファイルを読み取っているらしいのです。フォーマットは以下の様になっています。

[
 {
  "directory": "C:/dev/foo",
  "arguments": [
   "gcc",
   "-c",
   "-I.",
   "-DWIN32",
   "-s",
   "foo.c",
   "-o",
   "foo.o"
  ],
  "file": "foo.c"
 }
]

一つ二つなら自分で書く事も出来るのですが、ソースファイルが沢山ある場合にこんなの作ってられません。cmake を使っているプロジェクトであればこれを自動で生成してくれる方法があるらしいのですが、Makefile からは作ってくれません。これを自動で作る方法無いかなと調べていたら compiledb というコマンドがある事に気付きました。

GitHub - nickdiego/compiledb: Tool for generating Clang's JSON Compilation Database files for make-based build systems.

Compilation Database Generator Tool for generating Clang's JSON Compilation Database file for GNU ma...

https://github.com/nickdiego/compiledb

このコマンドを以下の様にインストールします。

pip3 install compiledb

インストールしたらいつもの make の手順に compiledb を付けて以下の様に実行します。

compiledb make

すると全てのビルドが終わったタイミングで compile_commands.json が生成されます。後は vim-lsp から補完を行えば vim-clang よりも高速に入力補完が行える様になります。

快適~


2018/12/17


はじめに

まず始めに言っておかなければなりません。

gocode 今まで本当にありがとう

この記事は、Go 言語歴10年になる僕がこれまで愛用してきた Go 言語のコード補完ソフトウェア gocode の歴史と功績、そして今、gocode 自らがその役割を終えようとしている姿をぜひ皆さんに知って頂きたいという思いから Go Advent Calendar 2018 の記事として起こしました。この記事では gocode が歩んできた歴史と苦悩を少しでも皆さんに分かる様に解説させて頂きつつ、そして次にやってくる Go 言語のコード補完の未来についてご紹介したいと思います。Vim について多めに書かれていますが、Visual Studio Code での Go 開発にも影響する話です。

gocode とは

gocode は nsf 氏が開発した Go 言語のコード補完サーバです。

GitHub - nsf/gocode: An autocompletion daemon for the Go programming language

An autocompletion daemon for the Go programming language VERY IMPORTANT: this project is not maintai...

https://github.com/nsf/gocode

GitHub スターの数を見て貰えると分かる通り、gocode は多くのユーザに使われてきました。Go 言語はコンパイル型言語にも拘わらずスクリプト言語並みのコンパイルの速さでユーザを魅了してきたのですが、多くのユーザが gocode により助けられ開発速度を保てていたという事実はもはや説明するまでもありません。Visual Studio Code を使っておられる方であれば、その . をタイプして Go のコード補完候補を出していたのは gocode なのです。(最近は go-langserver が使われていますが、あれも最近まで中身が gocode でした)

gocode は開発初期こそ Vim と Emacs のみをサポートして来ましたが、最終的にはあらゆるテキストエディタや IDE で使われました。

  • Vim/NeoVim (vim-go)
  • Emacs (go-autocomplete.el)
  • goclipse
  • SublimeText 2 (GoSublime)
  • godev
  • godit
  • Wide
  • Visual Studio Code (vscode-go)

僕と gocode

gocode は僕の Go 言語プログラミングの右腕でした。趣味でも仕事でも常に使ってきました。一部の方であればご存じかもしれませんが、僕は Vim というテキストエディタを愛用しています。10年前となるともちろん Go 言語のコード補完はどの環境向けにも作られておらず、Go 言語のユーザ達は全てのコードを自分でタイプしていました。僕もその一人でしたし、それが普通だと思っていました。

2010年7月に gocode が誕生し、Go 言語ユーザから知られる様になって来た頃に僕もその存在に気付きました。はじめて Go 言語のコード補完を見た時には小躍りしそうなほど興奮したのを覚えています。Go のユーザが増えると共に gocode も人気となり開発もさかんになりました。僕も gocode には幾つかコントリビュートさせて貰いました。

そして gocode の本体に含まれていた Vim プラグインが vim-go に移り、今や Vim を使う Go ユーザの多くが vim-go ユーザでもあります。僕も今では vim-go が無いと Go が開発出来ないという程に vim-go のヘビーユーザです。そんな事もあり僕は Go の環境をセットアップする時はいつもまず gocode をインストールして来ました。

今思えば僕が Go のコードをこれほどまで量産してこれたのも、gocode が助けてくれていたからかも知れません。

gocode の仕組み

gocode はコード補完サーバ兼クライアントです。テキストエディタは Go のソースコードを開くと同時にその拡張やプラグインがバックグラウンドで gocode を起動します。そしてコード補完を行うタイミングで編集中のソースコードがテンポラリファイルに一旦書き込まれ、gocode のクライアントを経由してサーバに対してリクエストが送り込まれます。gocode サーバはソースを解析し、補完の候補を作ると各テキストエディタ向けのフォーマットで応答を返します。例えば Vim であれば Vim script のリスト形式を返しました。Emacs であればS式を返しました。その後、ユーザ数の拡大に合わせ各種フォーマットに対応しました。

  • vim
  • emacs
  • nice
  • csv
  • csv-with-package
  • json
  • godit

一見、json だけあれば十分ですし無駄な努力であった様にも見えますが Vim がまだ JSON を扱う事が出来なかった頃の話なので、これはあって当然の実装だったのです。

gocode が取り組んだ事

さまざまなテキストエディタや IDE から使われ、gocode は Go でのコード補完機能のデファクトスタンダードとしてのポジションに君臨して来ました。

gocode は Go 本体のコードの一部をベースとして作られており、ソースの一部からも取り込み当初の Go のコードが残る物になっています。元々は gocode も Go のソースをパースしソースコードから補完候補を作る仕組みでした。Go のユーザ数が増え、開発される規模も大きくなり、状況も変わってきました。そこで nsf 氏はバイナリをサポートし始めます。Go は go install するとパッケージをバイナリとして保持します。そして gocode はそのバイナリをパースしコード補完を高速化する事に成功しました。この時のコード補完の速度はとても速く素晴らしい物でした。そしてそれを gocode 標準の機能としたのです。

この方法には大きなメリットがありました。それは GOPATH 上にないソースコードでも補完が行えるのです。書き捨てのコードを GOPATH 外で編集していてもコード補完が効くのでとても便利でした。

しかしながら全ての Go ユーザが常に最新の Go を使っている訳ではありません。2018年12月現在 Go の最新バージョンは 1.11 ですが、未だ Go 1.8 を使っているユーザもいます。

gocode はその全てのバージョンのユーザをサポートしようとしました。Go コンパイラが出力するバイナリにはバイナリのバージョン番号が含まれるのですが、gocode のソースコードにはそのバージョンに対応するコードが散りばめられています。

gocode/package_bin.go at f1f547fc1cd78d02c3343f6acca144b79d411f02 - nsf/gocode - GitHub

v.20170907 v.20150303 go.weekly.2012-03-13 go.weekly.2012-03-04 go.weekly.2012-02-22 go.weekly.2012-...

https://github.com/nsf/gocode/blob/f1f547fc1cd78d02c3343f6acca144b79d411f02/package_bin.go#L167-L174

gocode の苦悩

しかしながら多くのバージョンに対応するという事は色々な問題を抱える事にもなります。複数のバイナリをサポートするという事だけでも大変な作業なのです。さらに Go コンパイラが新しいバイナリを生成する様になると、gocode は途端にクラッシュしてしまいます。僕の様に常に最新の Go を使っているユーザだと、Go コンパイラが新しいバイナリのバージョンをサポートし始めると gocode がそのバージョンをサポートするまではコード補完が使えない状態となるのです。

そして gocode の issues は常にこういったユーザからの「動かない」という報告で溢れていました。

gocode の限界

この様な苦悩はありながらも今後も gocode がコード補完の標準であり続けるであろうと思っていた中、それは突然やってきました。Go 1.10 のビルドキャッシュです。

Go 1.10 Release Notes - The Go Programming Language

Introduction to Go 1.10 The latest Go release, version 1.10, arrives six months after Go 1.9 . Most ...

https://tip.golang.org/doc/go1.10#build

Go 1.10 に追加されたビルドキャッシュは、Go コンパイラがビルドした結果をキャッシュし保持する仕組みです。そのキャッシュは Go の pkg ディレクトリにはインストールされません。Go のコードを一旦コンパイルし、バイナリ解析してコード補完を行っていた gocode は、そのキャッシュの場所を把握出来ません。そして pkg ディレクトリとキャッシュとの間で起きるコードの差異により、正しいコード補完結果を作る事が出来なくなりました。

Go1.10 and the pkg cache - Issue #500 - nsf/gocode - GitHub

The go build command now maintains a cache of recently built packages, separate from the installed p...

https://github.com/nsf/gocode/issues/500

一方その頃、Visual Studio Code は Language Server をサポートし始めました。Language Server は言語に依存しないコード解析仕様で、コード補完や定義位置ジャンプ等を提供します。各 Language Server は Language Server Protocol (LSP) に従って各言語版の実装する事で、Language Server Client からは透過的に各言語を扱えるという物です。これにより、一旦テキストエディタが Language Server Client を実装さえしてしまえばそれ以降は各言語が Language Server を実装すればテキストエディタは無改造(もしくは少量の変更のみ)で対応する事が出来るのです。Go 言語にもその実装 go-langserver が誕生しました。

ただし残念な事にその頃の go-langserver の内部実装は gocode を使う物でした。ビルドキャッシュの問題が go-langserver にものしかかります。

gocode の fork

nsf 氏はこのビルドキャッシュの件でモチベーションを無くしてしまい、gocode の開発は停止してしまいました。nsf 氏によると、キャッシュをサポートした事で、これまでバイナリをサポートしてきた gocode は意味を成さなくなったのです。その時の nsf 氏はこの様に言っています。

Yes, it sucks. With gocode you have to use "go install" anyway and that package cache feature is useless to you. Sadly there are no plans on my side to workaround it. I talked a bit about it a few times. A proper autocompletion service should use source files instead of package files. Somebody should make one. My enthusiasm for gocode is long gone.

I would suggest looking for alternatives. However I'm unaware of their state. I know there were few attempts of making "language server protocol" servers for Go. Have no idea how good they are. Sadly proper autocompletion tool of a kind should reimplement all language semantic analysis, because working with code that is being actively edited is a slightly different task that doing compilation or static analysis. I think I know how to make a proper service here, but... There's always but.. Maybe one day.

これはまずいですね。gocode ではとにかく "go install" を使わなければならないし、パッケージキャッシュ機能は君(上記 issue の発言主で go-langserver の開発者)にとっても無用な物になります。残念ながら私にはこれを回避する予定がありません。これについて少し話をしました。適切な自動コード補完サービスはパッケージファイルの代わりにソースファイルを使用する必要があります。誰かが作るはずです。gocode に対する私の熱意は長らく遠ざかってしまいました。

代替案を模索する事をお薦めします。しかし私はそれらの状況を良く知りません。Go 言語向けの "Language Server Protocol" を作ろうとする人がそれほどいなかった事は知っています。それらがどれほど良いか分かりません。賢くて適切な自動コード補完ツールは全ての言語セマンティック解析を再実装する必要があります。アクティブに編集されているコードを扱うというタスクは、コンパイルや静的解析を行う場合とは少し異なる物なのです。私はこの適切なサービスを作る方法を知っていると信じているが...いつの日か...しかしその時は来るのか...。

つまり nsf 氏は自ら gocode の開発に終止符を打ったのです。gocode の開発を続ける事が、本来の姿ではない事をこの時既に分かっていたのです。僕も正直、この issue を見た時は「なんで開発やめちゃうんだよ?まだ続けられるでしょ」と思っていましたが、あとあと読み返すとこの nsf 氏の発言は正しかったと思う様になりました。

その後、Go コンパイラにビルドキャッシュ機能を入れた本人でもある Matthew Dempsky 氏が(お詫びと言わんばかりに) gocode を fork し、現状のバイナリをパースしているコードを全て削除した上で、全てをソースコードから解析する変更を加えました。もちろんこれは nsf 氏が望む物ではありませんでしたが補完が効かなくなって悩んでいた僕を含む Go 言語ユーザの唯一の助けとなりました。しかし全てをソースコードから解析するのはとてもナンセンスでした。編集中のソースコードから import されるパッケージのソースを見つけ出したとしても、そこから import される新たなパッケージも見付かる訳ですから、これをテキストエディタのコード補完のトリガと同時に行っていたら遅くなってしまうのは誰でも分かる事でした。

GitHub - mdempsky/gocode: An autocompletion daemon for the Go programming language

github.com/mdempsky/gocode This version of gocode is a fork of the original , which is no longer sup...

https://github.com/mdempsky/gocode

さらにその後、Matthew Dempsky(mdempsky) 氏の fork 版をさらに fork する形で、gocode にビルドキャッシュと Go Module をサポートする修正を追加した Rebecca Stambler(stamblerre) 氏版も登場しました。これは最新の Go の安定版を使っている方であれば幾分使える物になっているはずです。

GitHub - stamblerre/gocode: An autocompletion daemon for the Go programming language

github.com/stamblerre/gocode This version of gocode works with Go Modules. An autocompletion daemon ...

https://github.com/stamblerre/gocode

gocode の終わり

gocode が fork され、fork の存在を知らない一部の Go ユーザから「nsf/gocode が使えなくなった」との報告が出始めました。fork の存在を知っているユーザからは「org で1か所で開発すべきでは」と言った意見も出てきました。同じころ Visual Studio Code の Go 拡張は Language Server への移行を行っていましたが go-langserver も内部では gocode を使っているのですから、Visual Studio Code でも動くはずがありません。Go のコード補完にどんよりとした空気が漂っていました。

golsp の誕生

これはまずいなと思っていた頃、Go 開発者チームが Go のサブリポジトリである golang.org/x で LSP をサポートする動きを見せ始めました。2018年9月の話ですから今から3ヶ月前の話です。

始めはインタフェースのみ実装されており中身はスッカラカン状態でしたが、次第にコミットを重ねて2018年12月現在ではコード補完が行える様になりました。現在 golang.org/x にある golsp の実装は Rebecca Stambler 氏(上記 gocode の fork 版 stamblerre/gocode の人)が担当しています。先日僕もこの golsp に pull-request を送り、現在 golsp は Windows でもちゃんと動作する様になっています。

つまり Language Server Client が実装されているテキストエディタであれば、go-langserver の代わりに golsp を使う事で正常なコード補完が使える様になるのです。とても喜ばしい事です。そして幸運な事に、僕が愛用する Vim には Language Server Protocol を実装したプラグイン、vim-lsp があり、これは実行する LSP コマンドを簡単に差し替えられる様になっています。

GitHub - prabirshrestha/vim-lsp: async language server protocol plugin for vim and neovim

While most of the time it is ok to just set the name , cmd and whitelist there are times when you ne...

https://github.com/prabirshrestha/vim-lsp

vim-lsp のインストールは以下の通り。

Plug 'prabirshrestha/async.vim'
Plug 'prabirshrestha/vim-lsp'

また vim-lsp に golsp を設定する方法は以下の通り。

if executable('golsp')
  augroup LspGo
    au!
    autocmd User lsp_setup call lsp#register_server({
        \ 'name''go-lang',
        \ 'cmd'{server_info->['golsp''-mode''stdio']},
        \ 'whitelist': ['go'],
        \ })
    autocmd FileType go setlocal omnifunc=lsp#complete
  augroup END
endif

さらに vim-lsp は非同期にコード補完を行う事も出来ます。非同期の場合は以下の様にインストールします。

Plug 'prabirshrestha/async.vim'
Plug 'prabirshrestha/vim-lsp'
Plug 'prabirshrestha/asyncomplete.vim'
Plug 'prabirshrestha/asyncomplete-lsp.vim'
Plug 'natebosch/vim-lsc'
let g:lsp_async_completion = 1

Vim の Language Server Protocol サポートは先月開催された VimConf 2018 でも話題になり、皆さんから頂いたアンケートの結果でも LSP のサポートを望んでいるユーザが多い事が分かっています。

実は先日、vim-lsp の作者からこんなメールを貰いました。

vim-lsp への貢献に感謝します。他のvimプラグインだけでなく、Vimコミュニティ全体でのあなたの働きかけが素晴らしい物である事をこれまでずっと見てきました。vim-lsp の中心的なコントリビュータの1人になる事に興味がありますか?

もちろん即答でOKを出し、先日 vim-lsp のコントリビュータにして頂きました。LSP は Go 言語に限った機能ではありません。今後 Vim の Language Server Protocol サポートを vim-lsp のコントリビュータとしてサポートして行きたいです。

さて、golsp ももちろん Vim の為だけの機能ではありません。Visual Studio Code も golsp の恩恵を受ける事が出来ます。Visual Studio Code の場合は標準で go-langserver を使う様になっているのですが、go-langserver の代替ソフトウェアを設定できる方法があります。

"go.alternateTools": {
   "go-langserver": "golsp"
},
"go.useLanguageServer": true

こうする事で go-langserver の代わりに golsp が使われます。筆者の手元でも問題なく Go のコード補完が出来ている事が確認出来ています。

bingo の誕生

さらに嬉しい事に、別の Go Language Server も登場しました。Language Server Protocol の機能の実装内容では golsp よりも多い様です。Vim および Visual Studio Code での設定内容は上記 golsp を bingo に変えるだけで OK です。

if executable('golsp')
  augroup LspGo
    au!
    autocmd User lsp_setup call lsp#register_server({
        \ 'name''go-lang',
        \ 'cmd'{server_info->['bingo''-mode''stdio']},
        \ 'whitelist': ['go'],
        \ })
    autocmd FileType go setlocal omnifunc=lsp#complete
  augroup END
endif

Visual Studio Code の場合は以下となります。

"go.alternateTools": {
  "go-langserver": "bingo"
},
"go.languageServerExperimentalFeatures": {
  "format": true,
  "autoComplete": true
},
"go.useLanguageServer": true

実は現在、golsp の担当 Rebecca Stambler 氏が、bingo の作者に「golsp とコラボレーションしよう」と持ち掛けている所です。

collaborating on golsp - Issue #13 - saibing/bingo - GitHub

Hi @saibing ! I'm one of the people currently working on golang.org/x/tools/cmd/golsp . We recently ...

https://github.com/saibing/bingo/issues/13

もしこれが実現すれば、一時はどんよりとしていた Go のコード補完に新たな光が見え始める事になります。とても嬉しい状況ですね。

本家が発展する事が一番望ましい事だと思っています。

Go のコード補完のこれから

golang.org/x は拡張用のリポジトリとは言えど、Go 言語がオフィシャルとして Language Server のサポートをし始めたと言って良いでしょう。今後 Go 自身のパーサに変更が加えられたとしても、Go 言語開発者が golsp も追従させて行くでしょう。とは言え golsp もまだ発展途上です。Language Server の数ある機能の中、以下の機能が未実装です。

  • 監視ファイルの変更イベント
  • シンボル一覧
  • コード補完処理の一部
  • 参照元検索
  • ドキュメントのハイライト
  • コードアクション
  • インタフェースから実装の生成
  • コードレンズ
  • 色のプレゼンテーション
  • リネーム

中には Go 言語には必要ない物もありますが、コード補完の一部は未だ改善の余地があります。Go 言語開発者に任せる事も出来ますが、皆さんからのコントリビューションにより、Go 言語のコード補完がより良くなっていきます。ぜひ golsp にコントリビューションしてみて下さい。vim-lsp も pull-request をお待ちしています。

gocode は開発を停止し、これから他の物が使われていくでしょう。もしかすると nsf 氏が gocode2 として復活させるかもしれないし、また別のコード補完ソフトウェアが誕生するかもしれない。しかしこれまで gocode が多くの Go 言語プログラマに与えてきた大きな貢献に対して、最後にももう一度言いたい。

gocode ありがとう

Go言語による並行処理 Go言語による並行処理
Katherine Cox-Buday
オライリージャパン / ¥ 3,024 (2018-10-26)
 
発送可能時間:在庫あり。


2018/12/14


先日、mopp さんが Vim に flatten() を追加するプルリクエストを追加してくれたのだけど、その時の記憶を整理する為に書く自分の為の記事。

add flatten() to flatten list by mopp - Pull Request #3676 - vim/vim - GitHub

I'm a bit confused by the maxdepth argument. I would expect it to specify the maximum depth of the r...

https://github.com/vim/vim/pull/3676

Vim script のリストは以下の様に、異なる型が混在できる。Ruby や他のスクリプト言語でも一般的。そしてスクリプト言語には一般的にリストを平坦化する為の flatten という関数ないしはメソッドが用意されている。

let foo = [12, ["bar"], 3]
Vim本体に組み込み関数を追加するパッチを投げた - Qiita

Vim本体に手を加える 次に本体への修正ですが、大体1週間くらいで出来ました。 しかし、これは私一人の力ではなく、7割りくらい vim-jp のおかげです。 vim-jpは日本のVim開発者(Plug...

https://qiita.com/mopp/items/084abe28681202bda30e

mopp さんが Advent Calendar でその時の様子を書いてくれているんだけど、flatten() ははじめ再帰を使って書かれていた。途中で僕が「ループに直したらこうなる」という感じにコードを貼ってしまったので、後でループに直す実装を楽しみにしていた mopp さんには悪い事をしてしまった。申し訳ない。ぜひ次は flat_map() を実装して下さい。その時考えていたのだけど、flatten() の様な関数を再帰でなくループにするには本来ならばスタックに相当する何かが必要になるはずだろうと踏んでいた。なぜならリストを再帰降下するという事は戻り場所を知っておく必要があり、ループに直すのであればそれ相当のスタック配列が必要だと考えていたからだ。そして一般的にはこのスタック配列の実装がめんどくさいので皆再帰を使ってお茶を濁そうとする。僕もよくやる。

例えば以下の様な簡単なリスト構造を作ってみたとする。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef enum _type_t {
  INT_T,
  STRING_T,
  LIST_T,
} type_t;

typedef struct _value_t {
  int ref;
  type_t type;
  union {
    int n;
    char *s;
    struct _list_t *l;
  } val;
} value_t;

typedef struct _item_t {
  struct _item_t *next;
  value_t *value;
} item_t;

typedef struct _list_t {
  item_t *first;
} list_t;

static void
free_value(value_t *v) {
  item_t *i;

  if (v->ref-- > 0return;

  switch (v->type) {
  case INT_T:
    break;
  case STRING_T:
    free((void*)v->val.s);
    break;
  case LIST_T:
    i = v->val.l->first;
    while (i != NULL) {
      item_t *next = i->next;
      free_value(i->value);
      free(i);
      i = next;
    }
    free((void*)v->val.l);
    break;
  }
  free((void*)v);
}

static value_t*
new_list_value() {
  value_t *v = malloc(sizeof(value_t));
  v->type = LIST_T;
  v->val.l = malloc(sizeof(list_t));
  v->val.l->first = NULL;
  v->ref = 0;
  return v;
}

item_t*
new_item(value_t *v) {
  item_t *item = malloc(sizeof(item_t));
  item->value = v;
  item->next = NULL;
  ++v->ref;
  return item;
}

static void
list_add_value(list_t *list, value_t *rhs) {
  item_t *i = list->first;

  if (i == NULL) {
    list->first= new_item(rhs);
    return;
  }

  while (i->next != NULL) {
    i = i->next;
  }

  i->next= new_item(rhs);
}

static void
list_insert_value(list_t *list, item_t *before, value_t *value) {
  item_t *next;
  
  if (before == NULL) {
    list->first= new_item(value);
    return;
  }

  next = before->next;

  before->next= new_item(value);
  before->next->next = next;
}

static void
list_remove_item(list_t *list, item_t *item) {
  item_t *i, *before = NULL;
  
  for (i = list->first; i != NULL; i = i->next) {
    if (i == item) {
      if (before == NULL)
        list->first = i->next;
      else
        before->next = i->next;

      free_value(item->value);
      free(item);
      return;
    }
    before = i;
  }
}

static value_t*
new_int_value(int n) {
  value_t *v = malloc(sizeof(value_t));
  v->type = INT_T;
  v->val.n = n;
  v->ref = 0;
  return v;
}

static value_t*
new_string_value(const char* s) {
  value_t *v = malloc(sizeof(value_t));
  v->type = STRING_T;
  v->val.s = strdup(s);
  v->ref = 0;
  return v;
}

static void
print_value(value_t *v) {
  item_t *i;

  switch (v->type) {
  case INT_T:
    printf("%d", v->val.n);
    break;
  case STRING_T:
    /* TODO: escape non-printable */
    printf("\"%s\"", v->val.s);
    break;
  case LIST_T:
    printf("[");
    for (i = v->val.l->first; i != NULL; i = i->next) {
      print_value(i->value);
      if (i->next) printf(", ");
    }
    printf("]");
    break;
  }
}

int
main(int argc, char* argv[]) {
  value_t *list, *sub;

  list = new_list_value();  
  list_add_value(list->val.l, new_int_value(1));
  list_add_value(list->val.l, new_string_value("foo"));

  sub = new_list_value();  
  list_add_value(sub->val.l, new_string_value("bar"));
  list_add_value(list->val.l, sub);

  list_add_value(list->val.l, new_int_value(3));

  print_value(list);
  free_value(list);
  return 0;
}

数値と文字列とリストが扱える物。リストの中にはそのいずれかを混入できる。お気持ち程度の参照カウンタを入れてあるが動くかどうか確認してないし本題はそこじゃない。これを実行すると以下の様に表示される。

[1, "foo", ["bar"], 3]

このリスト関数を使って flatten() を実装する場合、簡単に思い付くのが再帰を使った以下の方法。vital.vim でも再帰を使ってる。

functions:flatten(list, ...) abort
  let limit = a:0 > 0 ? a:1 : -1
  let memo = []
  if limit == 0
    return a:list
  endif
  let limit -= 1
  for Value in a:list
    let memo +=
          \ type(Value) == type([]) ?
          \   s:flatten(Value, limit) :
          \   [Value]
    unlet! Value
  endfor
  return memo
endfunction

上記のリスト関数を使った場合だと以下の様になる。

static void
flatten_list(item_t *before, list_t *list) {
  item_t *i, *j, *prev = NULL;

  for (i = list->first; i != NULL; i = i->next) {
    if (i->value->type == LIST_T) {
      flatten_list(i, i->value->val.l);
      list_remove_item(list, i);
      return;
    }
    if (before != NULL) {
      list_insert_value(list, before, i->value);
      before = before->next;
    }
  }
}

リストを舐めながら要素がリストだったら挿入位置とそのリストを引数に要素を追加する関数(自身)を呼び出す。呼び出したあと元々リストがあった箇所を削除する。この flatten() は再帰を使ってるのでメモリを多く消費するしスタックオーバーフローで突然死してしまう可能性がある。でも良く考えると flatten() は、現在いる要素の子要素がリストの場合、そのリストの中身をすべて現在いる場所に移動し、自身を削除し、そして今と同じ箇所で再検査すればいいだけなのだ。スタックとして覚えておく必要もない。なので実装は以下の様になる。

static void
flatten_list(list_t *list) {
  item_t *i, *j, *prev = NULL;

  for (i = list->first; i != NULL; i = i->next) {
    if (i->value->type == LIST_T) {
      item_t *before = i;
      for (j = i->value->val.l->first; j != NULL; j = j->next) {
        list_insert_value(list, before, j->value);
        before = before->next;
      }

      if (prev == NULL)
        list->first = i->next;

      prev->next = i->next;
      i = prev;
    }
    prev = i;
  }
}

言ってみるならば、自分がネストに降下するんじゃなく、flat にする事でネストがこっちに上がってくるという事。実行すると以下が表示される。

[1, "foo", "bar", 3]

再帰は消え、スタックオーバーフローの心配もなくなり、メモリの消費量も減り、良い事づくめだ。逆に、今まで何度か flatten() は書いた事があるけどなぜ自分はこれまで flatten() を再帰で作ろうと考えてしまったのかと思い起こしたくもなった。

追記 この最適化方は自身のリストが破壊されるから出来る方法なので、flatten 済みのリストをを返す場合には使えないので注意。