Goの自作パーサーライブラリでJSON・TOMLパーサーを作った話
はじめに
Goの自作パーサーコンビネーターライブラリ「takenoco」を使って、トイ言語を作ったり、まだ公開していないプロジェクトでパーサーを作ったりしているのですが、自分も活用できる実用的なサンプルを作ろうと思い、JSON・TOMLパーサーの作成を思いつきました。
完成したのがこちら「go-loose-json-parser」です。
※作り始めたとき、JSONパーサーだけのサンプルにしようかと思っていたので、リポジトリ名にはTOMLが入っていません😖
Live demoはこちら ※wasmで動いています
Goには既に有名なTOMLパーサー(1),(2)もあるので、作成する必然性は無いのですが、車輪の再発明は楽しいですね。また、プロジェクトの依存関係が自家製なのは精神衛生上、大変良いです。
コンセプト
まず、最初に作り始めたJSONパーサーについて、パーサーライブラリの特性も考え、ゴリゴリにチューンして速度を狙うよりも、コメント付きや、キーがダブルクォーテーションで囲まれていないものを読めるようにしたいと思いました。JSONCやJSON5を概ね包含するイメージですね。
設定ファイルにコメントを書きたい、というのもありますし、モックアップに直書きしてあるようなダミーデータをモックAPIサーバーに移そうと思ったときに楽に使えるものがあると良いと思った次第です。
さらに、他のスクリプト言語のリスト・マップリテラルをなるべく読み込めるようにしようと思い、キーワード(null、NaN、Infinity 等)やキー・バリューの区切り文字を複数種類許すことを考えました。
TOMLに関しては、プリミティブやインラインのリスト・マップのパーサーをJSONと共通化しつつ、TOML 1.0 仕様のサンプルをパース出来ることを目標としました。
文字列についてはTOML準拠の新しいパーサーを作りつつ、JavaScriptのバックスラッシュ複数行文字列も輸入することにしました。
TOMLのドットで繋がったキー(foo.bar 等)は、JSONパーサーに輸入しました。
製作
パーサーライブラリへのフィードバック
以下のの汎用的なパースについて「takenoco」の機能としてフィードバックすることができました。
- Unicodeの識別子、Unicode単語境界(ゼロ幅)
- Date、DateTime、Time
※DateTimeについては、TOML仕様で厳密なISO8601拡張形式以外もパースする必要が生じたため、結局「go-loose-json-parser」ではカスタムなパーサーを採用しました。
まずは、Unicode識別子、単語境界について説明したいと思います。
以下のコードに登場する ID_Start, ID_Continue とは Unicode character properties の名前です。識別子の最初の文字と2文字目以降は汎用的にこうすると良いですよ、という仕様(多分)で、JavaScript等が参照しています。Goでは、ID_Start, ID_Continue は直接定義されていないので、構成するプロパティのOrを取っています。
// Parse the Unicode identifier
func UnicodeIdentifierStr() ParserFn {
return Trans(
FlatGroup(
Once(First(
// ID_Start + '_' + '$'
CharClass("_", "$"),
CharClassFn(func(c rune) bool {
// ID_Start: Alpha(), and ...
return (unicode.Is(unicode.L, c) ||
unicode.Is(unicode.Nl, c) ||
unicode.Is(unicode.Other_ID_Start, c)) &&
!unicode.Is(unicode.Pattern_Syntax, c) &&
!unicode.Is(unicode.Pattern_White_Space, c)
}),
)),
ZeroOrMoreTimes(First(
// ID_Continue + '$' + U+200C + U+200D
CharClass("$"),
CharClassFn(func(c rune) bool {
// Alnum(), '_', and ...
return (unicode.Is(unicode.L, c) ||
unicode.Is(unicode.Nl, c) ||
unicode.Is(unicode.Other_ID_Start, c) ||
unicode.Is(unicode.Mn, c) ||
unicode.Is(unicode.Mc, c) ||
unicode.Is(unicode.Nd, c) ||
unicode.Is(unicode.Pc, c) ||
unicode.Is(unicode.Other_ID_Continue, c) ||
c == 0x0200c || c == 0x0200d) &&
!unicode.Is(unicode.Pattern_Syntax, c) &&
!unicode.Is(unicode.Pattern_White_Space, c)
}),
)),
),
Concat,
ChangeClassName(clsz.IdentifierStr),
)
}
次に、Date、DateTime、Timeですが、ここでは代表してTOML用にカスタマイズしたDateTimeで説明したいと思います。これは苦労が見て取れますね。
Goの time.Parse(layout, value) において、日付書式を示す layout はすべて固定です。
ISO8601において、秒や小数点以下はオプショナルかつ可変長、また、タイムゾーンもZとオフセット指定が許されますが、time.Parse が期待するのは常に固定の書式です (json.Unmarshal する裏技もありますが)。パース結果を固定フォーマットに合致するように変換しています。
※パーサーは5桁以上、またはマイナスの年を切り出していますが、残念ながら time.Parse が対応していません。
// Parse the ISO 8601 datetime string.
// (yyyy-MM-ddThh:mmZ , ... , yyyy-MM-ddThh:mm:ss.fffffffffZ)
// (yyyy-MM-ddThh:mm+00:00 , ... , yyyy-MM-ddThh:mm:ss.fffffffff+00:00)
func dateTimeStr() ParserFn {
return Trans(
FlatGroup(
ZeroOrOnce(Seq("-")),
Repeat(Times{Min: 4, Max: -1}, Number()),
Seq("-"),
CharRange(RuneRange{Start: '0', End: '1'}),
CharRange(RuneRange{Start: '0', End: '9'}),
Seq("-"),
CharRange(RuneRange{Start: '0', End: '3'}),
CharRange(RuneRange{Start: '0', End: '9'}),
First(
Seq("T"),
// TOML allows Datetime format with date and time delimited by space
// (RFC 3339 section 5.6)
FlatGroup(
erase(Seq(" ")),
Zero(Ast{
Type: AstType_String,
Value: "T",
}),
),
),
CharRange(RuneRange{Start: '0', End: '2'}),
CharRange(RuneRange{Start: '0', End: '9'}),
Seq(":"),
CharRange(RuneRange{Start: '0', End: '5'}),
CharRange(RuneRange{Start: '0', End: '9'}),
First(
FlatGroup(
Seq(":"),
CharRange(RuneRange{Start: '0', End: '6'}),
CharRange(RuneRange{Start: '0', End: '9'}),
First(
FlatGroup(
Seq("."),
Trans(
Repeat(Times{Min: 1, Max: 9}, // 3: milli, 6: micro, 9: nano
CharRange(RuneRange{Start: '0', End: '9'}),
),
Concat,
func(ctx ParserContext, asts AstSlice) (AstSlice, error) {
return AstSlice{{
Type: AstType_String,
Value: (asts[len(asts)-1].Value.(string) + "000000000")[0:9],
}}, nil
},
),
),
Zero(Ast{
Type: AstType_String,
Value: ".000000000",
}),
),
),
Zero(Ast{
Type: AstType_String,
Value: ":00.000000000",
}),
),
First(
FlatGroup(
erase(Seq("Z")),
Zero(Ast{
Type: AstType_String,
Value: "+00:00",
}),
),
FlatGroup(
CharClass("+", "-"),
Repeat(Times{Min: 2, Max: 2},
CharRange(RuneRange{Start: '0', End: '9'}),
),
Seq(":"),
CharRange(RuneRange{Start: '0', End: '5'}),
CharRange(RuneRange{Start: '0', End: '9'}),
),
FlatGroup(
// TOML allows Datetime format without timezone
Zero(Ast{
Type: AstType_String,
Value: "+00:00",
}),
),
),
),
Concat,
ChangeClassName(class.DateTimeStr),
)
}
time.Parse にISO8601のプリセットが欲しいですね。
以下はGo 1.20の time パッケージのConstantsです。DateTime, DateOnly, TimeOnly が追加になったそうですが、「違う、そうじゃない」！
const (
Layout = "01/02 03:04:05PM '06 -0700" // The reference time, in numerical order.
ANSIC = "Mon Jan _2 15:04:05 2006"
UnixDate = "Mon Jan _2 15:04:05 MST 2006"
RubyDate = "Mon Jan 02 15:04:05 -0700 2006"
RFC822 = "02 Jan 06 15:04 MST"
RFC822Z = "02 Jan 06 15:04 -0700" // RFC822 with numeric zone
RFC850 = "Monday, 02-Jan-06 15:04:05 MST"
RFC1123 = "Mon, 02 Jan 2006 15:04:05 MST"
RFC1123Z = "Mon, 02 Jan 2006 15:04:05 -0700" // RFC1123 with numeric zone
RFC3339 = "2006-01-02T15:04:05Z07:00"
RFC3339Nano = "2006-01-02T15:04:05.999999999Z07:00"
Kitchen = "3:04PM"
// Handy time stamps.
Stamp = "Jan _2 15:04:05"
StampMilli = "Jan _2 15:04:05.000"
StampMicro = "Jan _2 15:04:05.000000"
StampNano = "Jan _2 15:04:05.000000000"
DateTime = "2006-01-02 15:04:05"
DateOnly = "2006-01-02"
TimeOnly = "15:04:05"
)
TOMLにおけるテーブルのパース
TOMLには、「テーブル」と「テーブルの配列」という構造があります。
テーブルはJSONにおけるオブジェクト、テーブルの配列はオブジェクトの配列に相当します。それぞれを自由にネストすることができます。
[table-A]
item-a = 1
item-b = 2
[table-A.sub-table-P]
item-m = 11
item-n = 12
sub-table-X.sub-table-Y = 111
[[array-of-table-U]]
foo = 1
[array-of-table-U.sub-table-V]
bar = 11
[[array-of-table-U]]
foo = 2
[array-of-table-U.sub-table-V]
bar = 22
一見難しそうですが、それぞれの識別子の階層について、最後に登場したインスタンスを保持しておけばよい (以下のソースでは lastRefs) という、パーサーに優しい仕様となっています。
func tableTransformer(ctx ParserContext, asts AstSlice) (AstSlice, error) {
length := len(asts)
v := make(map[string]interface{})
lastRefs := make(map[string]*map[string]interface{})
lastRefs[""] = &v
for i := 0; i < length; i += 2 {
switch w := asts[i].Value.(type) {
case string:
// Simple identifier
merged := false
if asts[i+1].ClassName == class.TomlArrayOfTable {
var a2 []map[string]interface{}
if tmp, ok := v[w].([]map[string]interface{}); ok {
a2 = tmp
} else {
// Register (case of v[w] == nil) or overwrite
// NOTE: If overwrite, it is invalid TOML
a2 = make([]map[string]interface{}, 0, 8)
v[w] = a2
}
if m1, ok := asts[i+1].Value.(map[string]interface{}); ok {
dottedKey := makeDottedKeyForSimpleName(w)
lastRefs[dottedKey] = &m1
a2 = append(a2, m1)
v[w] = a2
}
} else {
if m1, ok := asts[i+1].Value.(map[string]interface{}); ok {
dottedKey := makeDottedKeyForSimpleName(w)
lastRefs[dottedKey] = &m1
if m2, ok := v[w].(map[string]interface{}); ok {
// Merge redefined table
// NOTE: Possibly an invalid TOML (except in cases such as `[x.y.z] ... [x]`)
for xKey, xVal := range m1 {
m2[xKey] = xVal
}
merged = true
}
}
if !merged {
v[w] = asts[i+1].Value
}
}
case []string:
// Dotted identifier
for j, key := range w {
if j == len(w)-1 {
merged := false
table := lastRefs[makeDottedKey(w, j)]
if asts[i+1].ClassName == class.TomlArrayOfTable {
var a2 []map[string]interface{}
if tmp, ok := (*table)[key].([]map[string]interface{}); ok {
a2 = tmp
} else {
// Register (case of (*table)[key] == nil) or overwrite
// NOTE: If overwrite, it is invalid TOML
a2 = make([]map[string]interface{}, 0, 8)
(*table)[key] = a2
}
if m1, ok := asts[i+1].Value.(map[string]interface{}); ok {
dottedKey := makeDottedKey(w, j+1)
lastRefs[dottedKey] = &m1
a2 = append(a2, m1)
(*table)[key] = a2
}
} else {
if m1, ok := asts[i+1].Value.(map[string]interface{}); ok {
dottedKey := makeDottedKey(w, j+1)
lastRefs[dottedKey] = &m1
if m2, ok := (*table)[key].(map[string]interface{}); ok {
// Merge redefined table
// NOTE: Possibly an invalid TOML
// (except in cases such as `[x.y.z] ... [x.y]`)
for xKey, xVal := range m1 {
m2[xKey] = xVal
}
merged = true
}
}
if !merged {
(*table)[key] = asts[i+1].Value
}
}
} else {
prev := lastRefs[makeDottedKey(w, j)]
dottedKey := makeDottedKey(w, j+1)
if _, ok := lastRefs[dottedKey]; ok {
// Already registerd to lastRefs
} else {
// Not registerd to lastRefs
if cur, ok := (*prev)[key]; ok {
switch next := cur.(type) {
case map[string]interface{}:
// Register
lastRefs[dottedKey] = &next
default:
// Overwrite
// NOTE: it is invalid TOML
table := make(map[string]interface{})
(*prev)[key] = table
lastRefs[dottedKey] = &table
}
} else {
// Append
table := make(map[string]interface{})
(*prev)[key] = table
lastRefs[dottedKey] = &table
}
}
}
}
}
}
return AstSlice{{
ClassName: class.Object,
Type: AstType_Any,
Value: v,
}}, nil
}
Unmarshalとリフレクション
リフレクションってビジネスロジックを組み立てるような場面では中々登場しないですよね。標準ライブラリの database/sql 等もリフレクションを使用しているので、日常的にお世話になっているのですけど。
ということで、普段リフレクションの知識はあまり積み上がらないのですが、今回はリフレクションが主役です。
Unmarshaller は大雑把に言えば、シリアル化または共通の表現形式に変換されたデータからオブジェクトを復元する機能です。
標準の encoding/json の Unmarshal のシグネチャは以下の通りです。data にソースとするJSONのUTF-8バイト列、v にデコード先の struct, []any, map[string]any 等のポインタを渡します。
func Unmarshal(data []byte, v any) error
今回、私はパーサーとUnmarshallerを分離しました。パーサーは常に []any, map[string]any またはプリミティブにデコードします。
そして Unmarshal のシグネチャは次のようにしました。from が変換元の []any, map[string]any またはプリミティブ、to がマッピング先の struct 等のポインタです。
パーサーとUnmarshallerを分離した理由は、[]any, map[string]any から struct への変換関数が以前から欲しいと思っていたため、また、パーサーを単純化するためです。
func Unmarshal(from interface{}, to interface{}, opts *MarshalOptions) error
Unmarshal の中では、from/to それぞれの型とデータを調べて、配下のフィールドを取得したり、値をキャストしたりしているのですが、それらを行う前にしなければならないことがあります。
from
reflect.Value が
-
IsValid()である
また、値を取る前には -
CanInterface()である
ことが必要です。
何を言っているのか分からないと思いますのでそれぞれ説明していきます。
IsValid は reflect.Value 自身がゼロ値ではないことを示します。 reflect.Value の指す先がゼロ値の意味ではないことに注意が必要です。ゼロ値の reflect.Value を得るのは例えば、マップの要素を取得する MapIndex(key) で存在しないキーを指定した場合などです。
IsValid が false の場合、文字列表現を得る String() 以外のすべてのメソッドが失敗します。
CanInterface は名前の通り reflect.Value の指す値を any として取れるかどうかをテストする関数ですが、これが false を返すのは、struct 等のフィールドがエクスポートされていない (小文字から始まるフィールド) 場合などです。 CanInterface が false の場合、unsafe を介さずに値を取得することができません。 CanInterface というのは実は フィールドの可視性をテストしてるのです。内部的には flagRO というフラグをテストしてます。
CanInterface が false でも配下の型をリフレクトすることはできます。
to
reflect.Value が
-
IsValid()である
また、値を取る前には -
CanSet()である
ことが必要です。
CanSet は reflect.Value の値が変更可能かどうかをテストします。CanSet は CanAddr() かつ CanInterface() と等価です。つまり、フィールドがエクスポートされており、アドレスを持っている (つまり、lvalue (左辺値) である) ということです。内部的には flagAddr と flagRO というフラグ両方をテストしてます。
reflect パッケージのコメントには次のように記載されています。
// The next set of bits are flag bits:
// - flagStickyRO: obtained via unexported not embedded field, so read-only
// - flagEmbedRO: obtained via unexported embedded field, so read-only
// - flagIndir: val holds a pointer to the data
// - flagAddr: v.CanAddr is true (implies flagIndir and ptr is non-nil)
// - flagMethod: v is a method value.
なお、テンポラリとして CanSet な reflect.Value を作るには、関数内で定義した変数のポインタをreflect.ValueOf() に渡しても上手くいきません。次のようなトリックが必要です。(理解が足りず、なぜ前者では駄目なのか説明できません。ValueOfの内部でヒープへのエスケープをしているんですが……なぜでしょう？)
s := make([]float64, 1)
rvDest := reflect.ValueOf(s).Index(0)
CanInterface、CanSet が false でフィールドにアクセスできない場合でも、より上の階層で struct 全体を Set すれば直接は見れなくても値を取得/更新することはできます。
case reflect.Struct:
switch rvFrom.Kind() {
case reflect.Struct:
length := rvTo.NumField()
if rtTo == rvFrom.Type() {
// shallow copy all the fields
if !ctx.opts.NoCopyUnexportedFields {
rvTo.Set(rvFrom)
}
}
// deep copy
for i := 0; i < length; i++ {
rtDestField := rtTo.Field(i)
destFieldName := rtDestField.Name
if err := unmarshalCore(rvFrom.FieldByName(destFieldName), rvTo.Field(i), ctx, false); err != nil {
return err
}
}
デモの作成
Live demo は生の html、JavaScript でビルド無しで作っています。wasm にビルドした関数を呼んで結果を表示するだけですからね。
エディタ部分には CodeMirror 5 を使用しています。CDNから読み込むだけで使えます。このような簡易なツールを作る際のテキストエリアに大変おすすめです！
<link rel="stylesheet" href="https://cdnjs.cloudflare.com/ajax/libs/codemirror/5.65.11/codemirror.min.css"
integrity="sha512-uf06llspW44/LZpHzHT6qBOIVODjWtv4MxCricRxkzvopAlSWnTf6hpZTFxuuZcuNE9CBQhqE0Seu1CoRk84nQ=="
crossorigin="anonymous" referrerpolicy="no-referrer" />
<link rel="stylesheet" href="https://cdnjs.cloudflare.com/ajax/libs/codemirror/5.65.11/theme/dracula.min.css"
integrity="sha512-gFMl3u9d0xt3WR8ZeW05MWm3yZ+ZfgsBVXLSOiFz2xeVrZ8Neg0+V1kkRIo9LikyA/T9HuS91kDfc2XWse0K0A=="
crossorigin="anonymous" referrerpolicy="no-referrer" />
<script src="https://cdnjs.cloudflare.com/ajax/libs/codemirror/5.65.11/codemirror.min.js"
integrity="sha512-rdFIN28+neM8H8zNsjRClhJb1fIYby2YCNmoqwnqBDEvZgpcp7MJiX8Wd+Oi6KcJOMOuvGztjrsI59rly9BsVQ=="
crossorigin="anonymous" referrerpolicy="no-referrer"></script>
<script src="https://cdnjs.cloudflare.com/ajax/libs/codemirror/5.65.11/mode/javascript/javascript.min.js"
integrity="sha512-Cbz+kvn+l5pi5HfXsEB/FYgZVKjGIhOgYNBwj4W2IHP2y8r3AdyDCQRnEUqIQ+6aJjygKPTyaNT2eIihaykJlw=="
crossorigin="anonymous" referrerpolicy="no-referrer"></script>
<script src="https://cdnjs.cloudflare.com/ajax/libs/codemirror/5.65.11/mode/toml/toml.min.js"
integrity="sha512-O6QYGRZVa6FLNVTWPdLXXiVC4pNCVA6NNVW29i7qHFprs/Wat4QrjSKjINcoCT+2IySTFmfIoIp2yZmWoafQsg=="
crossorigin="anonymous" referrerpolicy="no-referrer"></script>
さいごに
パーサーを自分で作れるようになると、プログラミングで出来ることの幅が広がります。
皆さんもぜひ、自分に合ったパーサーライブラリを見つけて (または自作して)、プログラミングを楽しんでくださいね。
追記 (2023/02/23)
📢本ライブラリが使用している自作パーサーコンビネーター「takenoco」について🔰入門記事🔰を書きました。よろしければご覧ください
Discussion