protobufのboolはどこまでcompatibleなのか

Protocol Buffers(以下、protobuf)におけるboolのcompatibilityは、Language Guideで以下のように述べられています。

int32, uint32, int64, uint64, and bool are all compatible

これを読むと、もともとboolだったMessage Typeをint32にアップデートできるように思えます。 本記事では、実際に起こりそうな例で、boolからint32へのアップデートを試してみた結果をまとめます。

ストーリー

今回は、一般ユーザnormalとプレミアムユーザpremiumが存在するシステムに、追加仕様としてゴールドユーザgoldを増やさなければならなくなった場合を考えます。

もともとの仕様

もともと、一般ユーザnormalとプレミアムユーザpremiumの2種類のユーザしか存在しなかったため、以下のようなboolでユーザのtypeを区別する.protoを定義します。 gRPCで呼ぶときはIsPremium()を呼ぶようなイメージです。

syntax = "proto3";
package user;

message User {
  bool type = 1; // 0: normal, 1: premium
}

仕様変更

さて、追加仕様としてゴールドユーザgoldを増やさなければなりません。 boolだったtypeフィールドをint32に変更しましょう。

syntax = "proto3";
package user;

message User {
  int32 type = 1; // 0: normal, 1: premium, 2: gold
}

互換性を確認

互換性を確認するにあたり、gRPCサーバを書いてもよかったですが、今回はバイナリをファイルに書き出すことにします。 書き出したバイナリを、仕様変更前のクライアントと仕様変更後のクライアントが読み込み、互換性が保たれるか確認します。

書き出し用のコードは以下の通りです。

package main

import (
    "io/ioutil"
    "log"

    pb "github.com/cipepser/protobuf-sample/user"
    "github.com/golang/protobuf/proto"
)

func main() {
    normal := &pb.User{
        Type: 0,
    }

    if err := write("./user/normal_int32.bin", normal); err != nil {
        log.Fatal(err)
    }

    premium := &pb.User{
        Type: 1,
    }
    if err := write("./user/premium_int32.bin", premium); err != nil {
        log.Fatal(err)
    }

    gold := &pb.User{
        Type: 2,
    }
    if err := write("./user/gold_int32.bin", gold); err != nil {
        log.Fatal(err)
    }
}

func write(file string, user *pb.User) error {
    out, err := proto.Marshal(user)
    if err != nil {
        return err
    }

    if err := ioutil.WriteFile(file, out, 0644); err != nil {
        return err
    }

    return nil
}

ユーザのtypeごとに以下のファイル名で保存しています。

ユーザ	file
一般	normal_int32.bin
プレミアム	premium_int32.bin
ゴールド	gold_int32.bin

仕様変更後のクライアントで読み込む

まずは、仕様変更 後 int32の.protoを知っているクライアントで読み込んでみましょう。

syntax = "proto3";
package user;

message User {
  int32 type = 1; // 0: normal, 1: premium, 2: gold
}

クライアント想定の読み込み用のコードは以下の通りです。

package main

import (
    "fmt"
    "io/ioutil"
    "log"

    pb "github.com/cipepser/protobuf-sample/user"
    "github.com/golang/protobuf/proto"
)

func main() {
    if err := read("./user/normal_int32.bin"); err != nil {
        log.Fatal(err)
    }
    if err := read("./user/premium_int32.bin"); err != nil {
        log.Fatal(err)
    }
    if err := read("./user/gold_int32.bin"); err != nil {
        log.Fatal(err)
    }
}

func read(file string) error {
    in, err := ioutil.ReadFile(file)
    if err != nil {
        return err
    }
    user := &pb.User{}
    if err := proto.Unmarshal(in, user); err != nil {
        return err
    }
    fmt.Println(file, ": ", user.Type)
    return nil
}

読み込み結果

結果は以下の通りです。

❯ go run UserRead.go
./user/normal.bin :  0
./user/premium_int32.bin :  1
./user/gold_int32.bin :  2

表にまとめると以下の通りなので、正しく動作していますね。compatibleです。

ユーザ	type
一般	0
プレミアム	1
ゴールド	2

仕様変更前のクライアントで読み込む

いよいよ問題の仕様変更 前 boolの.protoしか知らないクライアントで読み込んでみます。

syntax = "proto3";
package user;

message User {
  bool type = 1; // 0: normal, 1: premium
}

読み込み用のコードは、上述の仕様変更後で利用したものと同一です。

読み込み結果

結果は以下の通りです。

./user/normal.bin :  false
./user/premium_int32.bin :  true
./user/gold_int32.bin :  true

表にまとめると以下の通りです。

ユーザ	type
一般	false
プレミアム	true
ゴールド	true

考察

proto.Unmarshal()するときにエラーは起きていませんが、一般ユーザがfalse、プレミアムユーザとゴールドユーザがtrueとなる結果となりました。
最終的にboolで読み込む以上、1bit分の情報になるしかないのは納得ですが、サービスによって想定外の動作となる可能性がありますね。
例えば、冒頭で述べたIsPremium()では、ギリギリ問題ないかもしれませんが、IsNormal()を呼ぶような場合はNGです。以下表のように.protoを定義していた場合、boolしか知らないクライアントから、一般ユーザとゴールドユーザが同一に見えてしまいます。

ユーザ	仕様変更前	仕様変更後
プレミアム	false	0
一般	true	1

このようにboolからint32へ変更するとエラーが起きず互換性が崩れる場合があります。逆にすべてのクライアントが最新の.protoが使えるような場合は、仕様通りcompatibleに使えると思います。

おまけ：Unmarshalの実装

上記例で、一般ユーザtype=0とプレミアムユーザtype=1がそれぞれfalse、trueとして読み込まれるのは納得できる動作ですが、ゴールドユーザtype=2がtrueとなるのは少し気になるので、もう少し深掘りしていきます。

castが伴うようなパースについて、Language Guideで以下のように書かれています。

If a number is parsed from the wire which doesn't fit in the corresponding type, you will get the same effect as if you had cast the number to that type in C++ (e.g. if a 64-bit number is read as an int32, it will be truncated to 32 bits).

言語処理系の実装依存な気もしますが、64-bitを32-bitに切り詰めると後半32-bitだけが残るような気もしてきます。 なので、今回の実験をする前は、type=2では、0b0010(便宜上4-bit表記)はboolにするときに最後の1-bitだけが残り、0=falseになるのではないかと予想していました。 結論から言うと、この予想は誤りで、Googleの実装では0と0以外でfalse、trueを返します。

protobufのint32をboolにUnmarshalするときの実装は、ここです(関数を抜粋すると以下)。

func unmarshalBoolValue(b []byte, f pointer, w int) ([]byte, error) {
    if w != WireVarint {
        return b, errInternalBadWireType
    }
    // Note: any length varint is allowed, even though any sane
    // encoder will use one byte.
    // See https://github.com/golang/protobuf/issues/76
    x, n := decodeVarint(b)
    if n == 0 {
        return nil, io.ErrUnexpectedEOF
    }
    // TODO: check if x>1? Tests seem to indicate no.
    v := x != 0
    *f.toBool() = v
    return b[n:], nil
}

v := x != 0によって0だけがfalseになり、0以外はtrueとなります。

いくつかの言語の実装箇所も調べてみましたが、GoogleのProtocol Buffersのレポジトリにあるものは、いずれも0と0以外で区別しているようでした。

言語	実装	リンク
PHP	if ($value == 0) { $value = false; } else { $value = true; }	https://github.com/google/protobuf/blob/0b0890b36d01bf7b372cb237998ee793f5cdc433/php/src/Google/Protobuf/Internal/GPBWire.php#L263
C++	*value = temp != 0;	https://github.com/google/protobuf/blob/0b0890b36d01bf7b372cb237998ee793f5cdc433/src/google/protobuf/wire_format_lite_inl.h#L158
java	return readRawVarint64() != 0;	https://github.com/google/protobuf/blob/964201af37f8a0009440a52a30a66317724a52c3/java/core/src/main/java/com/google/protobuf/CodedInputStream.java#L807
python	wire_format.WIRETYPE_VARINT, _DecodeVarint, bool) # pythonの場合0以外の数値はtrueになる	https://github.com/google/protobuf/blob/39f9b43219bc5718b659ed72a2130a7b2ce66108/python/google/protobuf/internal/decoder.py#L458

References

• Proto3 Language Guide（和訳）
• Protocol Buffers - Encoding
• Protocol Buffers のエンコーディング仕様の解説
• The Go Programming Language Specification
• Protocol Buffers - Language Guide (proto3)
• Protocol Buffers - Google's data interchange format
• 真(true)と偽(false) - PythonWeb

gRPCでリクエストパラメータのValidation

goのgRPCで便利ツールを使うで紹介されているGo gRPC MiddlewareとGolang ProtoBuf Validator CompilerでgRPCのvalidationをします。 今回の例では、Userの年齢は負数にならない、電話番号やメールアドレスを正規表現でvalidationするといったことを実装します。

インストール

Go gRPC Middlewareのインストール

❯ go get github.com/grpc-ecosystem/go-grpc-middleware

Golang ProtoBuf Validator Compilerのインストール

❯ go get github.com/mwitkow/go-proto-validators/protoc-gen-govalidators

もとになるサーバとクライアント

protobufでgRPCを呼び出すサーバとクライアントを実装します。 今回はサーバにUserを登録できるだけのサービスです。

protobufの定義

// user.proto
syntax = "proto3";

package user;
service UserService {
  rpc GetUser (Name) returns (User) {}
  rpc GetUsers (Empty) returns (Users) {}
  rpc AddUser (User) returns (Empty) {}
}

message User {
  string name = 1;
  int32 age = 2;
  string phone = 3;
  string mail = 4;
}

message Name {
  string name = 1;
}

message Empty {}

message Users {
  repeated User users = 1;
}

server

// server.go
package main

import (
    "context"
    "errors"
    "log"
    "net"

    pb "github.com/cipepser/gRPC-validation/user"
    "google.golang.org/grpc"
)

type server struct {
    users map[*pb.User]struct{}
    names map[string]struct{}
}

var (
    empty = new(pb.Empty)
)

const (
    port = ":50051"
)

func (s *server) GetUser(ctx context.Context, in *pb.Name) (*pb.User, error) {
    for u := range s.users {
        if u.Name == in.Name {
            return u, nil
        }
    }
    return nil, errors.New("user not found")
}

func (s *server) GetUsers(ctx context.Context, in *pb.Empty) (*pb.Users, error) {
    out := new(pb.Users)
    for u := range s.users {
        out.Users = append(out.Users, u)
    }
    return out, nil
}

func (s *server) AddUser(ctx context.Context, in *pb.User) (*pb.Empty, error) {
    if _, ok := s.names[in.Name]; ok {
        return empty, errors.New("user already exists")
    }
    s.users[in] = struct{}{}
    s.names[in.Name] = struct{}{}
    return empty, nil
}

func main() {
    l, err := net.Listen("tcp", port)
    if err != nil {
        log.Fatalf("failed to listen: %v", err)
    }

    s := grpc.NewServer()
    pb.RegisterUserServiceServer(s,
        &server{
            users: map[*pb.User]struct{}{},
            names: map[string]struct{}{},
        },
    )
    s.Serve(l)
}

client

// client.go
package main

import (
    "context"
    "fmt"
    "log"

    pb "github.com/cipepser/gRPC-validation/user"
    "google.golang.org/grpc"
)

const (
    address = "localhost"
    port    = ":50051"
)

var (
    empty = new(pb.Empty)
)

type client struct {
}

func main() {
    conn, err := grpc.Dial(address+port, grpc.WithInsecure())
    if err != nil {
        log.Fatalf("failed to connect: %v", err)
    }
    defer conn.Close()

    c := pb.NewUserServiceClient(conn)

    u := pb.User{
        Name:  "Bob",
        Age:   24,
        Phone: "",
        Mail:  "",
    }

    _, err = c.AddUser(context.Background(), &u)
    if err != nil {
        log.Fatalf("failed to add user: %v", err)
    }

    resp, err := c.GetUsers(context.Background(), empty)
    if err != nil {
        log.Fatalf("failed to get users: %v", err)
    }
    log.Printf("users:")
    for _, u := range resp.Users {
        fmt.Println(u)
    }
}

validation

上記だけでもgo run server.goでサーバを起動し、go run client.goすればサービスが動きますが、以下に仕様に従ったvalidationをしてきましょう。

仕様

フィールド	制約
name	-
age	0〜150歳
phone	携帯電話の正規表現にマッチ
mail	メールアドレスの正規表現にマッチ

phoneとmailの正規表現は、よく使う正規表現はもうググりたくない！から拝借します。そのままだと動かないので、エスケープを\から\\に変更しています。

Golang ProtoBuf Validator Compilerでは、 [(validator.field) = {msg_exists : true}];とすることでrequiredを実現できますが、proto3でrequiredが廃止されたことからも利用しません(nameフィールドで使いたくなった)。

protobufの定義(validationあり)

// user.proto
syntax = "proto3";

package user;
import "github.com/mwitkow/go-proto-validators/validator.proto";

service UserService {
  rpc GetUser (Name) returns (User) {}
  rpc GetUsers (Empty) returns (Users) {}
  rpc AddUser (User) returns (Empty) {}
}

message User {
  string name = 1;
  int32 age = 2 [(validator.field) = {int_gt: -1, int_lt: 151}];;
  string phone = 3 [(validator.field) = {regex: "^(070|080|090)-\\d{4}-\\d{4}$"}];
  string mail = 4 [(validator.field) = {regex: "^\\w+([-+.]\\w+)*@\\w+([-.]\\w+)*\\.\\w+([-.]\\w+)*$"}];
}

message Name {
  string name = 1;
}

message Empty {}

message Users {
  repeated User users = 1;
}

以下でprotobufをコンパイルします。

❯ protoc  \
  --proto_path=${GOPATH}/src \
    --proto_path=. \
    --go_out=plugins=grpc:./ \
    --govalidators_out=./ \
    *.proto

server

Go gRPC Middlewareでvalidateさせるために、server.goに以下を追記する。

// server.go
s := grpc.NewServer(
  grpc.StreamInterceptor(grpc_middleware.ChainStreamServer(
    grpc_validator.StreamServerInterceptor(),
  )),
  grpc.UnaryInterceptor(grpc_middleware.ChainUnaryServer(
    grpc_validator.UnaryServerInterceptor(),
  )),
)

実行

validationされるか試してきましょう。
なお、ディレクトリ構成は以下のようになっています。

❯ tree .
.
├── README.md
├── client
│   └── client.go
├── server
│   └── server.go
└── user
    ├── user.pb.go
    ├── user.proto
    └── user.validator.pb.go

3 directories, 6 files

正常系

u := pb.User{
  Name:  "Alice",
  Age:   20,
  Phone: "090-1111-1111",
  Mail:  "alice@example.com",
}

❯ go run client/client.go
2018/07/22 14:20:28 users:
name:"Alice" age:20 phone:"090-1111-1111" mail:"alice@example.com"

正常に登録できています。

異常系(age: -1歳)

u := pb.User{
  Name:  "Bob",
  Age:   -1,
  Phone: "090-1111-1111",
  Mail:  "bob@example.com",
}

❯ go run client/client.go
2018/07/22 14:22:19 failed to add user: rpc error: code = InvalidArgument desc = invalid field Age: value '-1' must be greater than '-1'
exit status 1

異常系(age: 200歳)

u := pb.User{
  Name:  "Bob",
  Age:   200,
  Phone: "090-1111-1111",
  Mail:  "bob@example.com",
}

❯ go run client/client.go
2018/07/22 14:22:35 failed to add user: rpc error: code = InvalidArgument desc = invalid field Age: value '200' must be less than '151'
exit status 1

異常系(phone: 英字)

u := pb.User{
  Name:  "Bob",
  Age:   20,
  Phone: "09a-1111-11112",
  Mail:  "bob@example.com",
}

❯ go run client/client.go
2018/07/22 14:23:40 failed to add user: rpc error: code = InvalidArgument desc = invalid field Phone: value '09a-1111-1111' must be a string conforming to regex "^(070|080|090)-\\d{4}-\\d{4}$"
exit status 1

異常系(phone: ハイフンなし)

u := pb.User{
  Name:  "Bob",
  Age:   20,
  Phone: "090111111112",
  Mail:  "bob@example.com",
}

❯ go run client/client.go
2018/07/22 14:23:48 failed to add user: rpc error: code = InvalidArgument desc = invalid field Phone: value '09011111111' must be a string conforming to regex "^(070|080|090)-\\d{4}-\\d{4}$"
exit status 1

異常系(phone: 桁が多い)

u := pb.User{
  Name:  "Bob",
  Age:   20,
  Phone: "090-1111-11112",
  Mail:  "bob@example.com",
}

❯ go run client/client.go
2018/07/22 14:23:55 failed to add user: rpc error: code = InvalidArgument desc = invalid field Phone: value '090-1111-11112' must be a string conforming to regex "^(070|080|090)-\\d{4}-\\d{4}$"
exit status 1

異常系(mail: @なし)

u := pb.User{
  Name:  "Bob",
  Age:   20,
  Phone: "090-1111-1111",
  Mail:  "bob.example.com",
}

❯ go run client/client.go
2018/07/22 14:24:40 failed to add user: rpc error: code = InvalidArgument desc = invalid field Mail: value 'bob.example.com' must be a string conforming to regex "^\\w+([-+.]\\w+)*@\\w+([-.]\\w+)*\\.\\w+([-.]\\w+)*$"
exit status 1

終わりに

異常系をちゃんとvalidationできていました。client側に正規表現の実装詳細を伝えてしまっているのが気になりますが、generateされたコードはuser/user.validator.pb.goにあるので、そちらのメッセージを変更すれば見えなくなると思います。ただ、これでやるとgenerateし直すたびにuser/user.validator.pb.goを直すことになるのでおすすめしませんが。

References

• goのgRPCで便利ツールを使う
• Golang ProtoBuf Validator Compiler
• Go gRPC Middleware
• よく使う正規表現はもうググりたくない！
• Language Guide - Protocol buffers

vgoを試してみる

Go1.11から導入されるvgoを試してみたメモ書きです。

基本的な流れは、和訳: A Tour of Versioned Go (vgo) (Go & Versioning, Part2)に沿っています。versioningが必要な理由や議論などは本記事では扱いません。

上記記事からvgoの開発が進みコマンドがいくつか変更になっていたので、同じくvgoを試す方の一助となればと思います。 今後も変更が入る可能性がありますが、x/vgoからgo本体にマージされたので、いい区切りかと思い、記事としてまとめることにしました。

環境

❯ vgo version
go version go1.10.3 darwin/amd64 go:2018-02-20.1

vgoのインストール

❯ go get -u golang.org/x/vgo

vgoを動かしてみる

サンプルプログラム

// hello.go
package main // import "github.com/you/hello"

import (
    "fmt"

    "rsc.io/quote" // この時点では、cannot find packageになるけどvgoが解決してくれる
)

func main() {
    fmt.Println(quote.Hello())
}

あとは何も書いていないgo.modも作っておく。

❯ touch go.mod

vgo build

❯ vgo build
vgo: resolving import "rsc.io/quote"
vgo: finding rsc.io/quote v1.5.2
vgo: finding rsc.io/quote (latest)
vgo: adding rsc.io/quote v1.5.2
vgo: finding rsc.io/sampler v1.3.0
vgo: finding golang.org/x/text v0.0.0-20170915032832-14c0d48ead0c
vgo: downloading rsc.io/quote v1.5.2
vgo: downloading rsc.io/sampler v1.3.0
vgo: downloading golang.org/x/text v0.0.0-20170915032832-14c0d48ead0c

これでbuildされるので、実行してみる。

❯ ./hello
こんにちは世界。

空だったgo.modにも追記されている。

// go.mod
module github.com/you/hello

require rsc.io/quote v1.5.2

依存しているモジュールをvgo list -mで表示できる。
コマンドが変更になったので、vgo list -mだと1個しか出てこない。
→vgo list -m allで全部出てくる。

❯ vgo list -m all
github.com/you/hello
golang.org/x/text v0.0.0-20170915032832-14c0d48ead0c
rsc.io/quote v1.5.2
rsc.io/sampler v1.3.0

Upgrade

-uオプションでupdated packageを確認できる。コマンドが変わって[]内にLATESTが表示されるようになった。

❯ vgo list -u -m all
vgo: finding golang.org/x/text v0.3.0
vgo: finding rsc.io/sampler v1.99.99
github.com/you/hello
golang.org/x/text v0.0.0-20170915032832-14c0d48ead0c [v0.3.0]
rsc.io/quote v1.5.2
rsc.io/sampler v1.3.0 [v1.99.99]

golang.org/x/textをUpgradeしてみる。

❯ vgo get golang.org/x/text
vgo: downloading golang.org/x/text v0.3.0

go.modが変わっている。

❯ git diff go.mod
diff --git a/go.mod b/go.mod
index 3200210..6246735 100644
--- a/go.mod
+++ b/go.mod
@@ -1,3 +1,6 @@
 module github.com/you/hello

-require rsc.io/quote v1.5.2
+require (
+       golang.org/x/text v0.3.0
+       rsc.io/quote v1.5.2
+)

listで見ても以下のようにv0.0.0-20170915032832-14c0d48ead0cからv0.3.0になっていることがわかる。

❯ vgo list -m all
github.com/you/hello
golang.org/x/text v0.3.0
rsc.io/quote v1.5.2
rsc.io/sampler v1.3.0

テストしてみる。

❯ vgo test all
?       github.com/you/hello    0.016s [no test files]
?       golang.org/x/text/internal/gen  0.078s [no test files]
ok      golang.org/x/text/internal/tag  0.011s
?       golang.org/x/text/internal/testtext 0.043s [no test files]
ok      golang.org/x/text/internal/ucd  0.015s
ok      golang.org/x/text/language  0.073s
ok      golang.org/x/text/unicode/cldr  0.132s
ok      rsc.io/quote    0.015s
ok      rsc.io/sampler  0.013s

rsc.io/quoteのv1.5.2には以下のようにバグがあるが、上記のようにokとなる。 これは、allの意味が"今の module 中の全てのパッケージと、それらが再帰的に import している全てのパッケージ"だから。

❯ vgo test rsc.io/quote/...
ok      rsc.io/quote    (cached)
--- FAIL: Test (0.00s)
    buggy_test.go:10: buggy!
FAIL
FAIL    rsc.io/quote/buggy  0.008s

vgo get -uですべてのmoduleをupgradeできる。

❯ vgo get -u
vgo: finding rsc.io/quote latest
vgo: finding golang.org/x/text latest
vgo: finding rsc.io/sampler latest
vgo: finding golang.org/x/text latest
vgo: finding rsc.io/sampler latest

rsc.io/samplerがv1.99.99にupgradeされた。

❯ vgo list -m all
github.com/you/hello
golang.org/x/text v0.3.0
rsc.io/quote v1.5.2
rsc.io/sampler v1.99.99

でもテストには失敗する。

❯ vgo test all
vgo: downloading rsc.io/sampler v1.99.99
?       github.com/you/hello    0.016s [no test files]
?       golang.org/x/text/internal/gen  0.032s [no test files]
ok      golang.org/x/text/internal/tag  (cached)
?       golang.org/x/text/internal/testtext 0.020s [no test files]
ok      golang.org/x/text/internal/ucd  (cached)
ok      golang.org/x/text/language  (cached)
ok      golang.org/x/text/unicode/cldr  (cached)
--- FAIL: TestHello (0.00s)
    quote_test.go:19: Hello() = "99 bottles of beer on the wall, 99 bottles of beer, ...", want "Hello, world."
FAIL
FAIL    rsc.io/quote    0.014s
--- FAIL: TestHello (0.00s)
    hello_test.go:31: Hello([en-US fr]) = "99 bottles of beer on the wall, 99 bottles of beer, ...", want "Hello, world."
    hello_test.go:31: Hello([fr en-US]) = "99 bottles of beer on the wall, 99 bottles of beer, ...", want "Bonjour le monde."
FAIL
FAIL    rsc.io/sampler  0.014s

Downgrade

v1.99.99へUpgradeしたらテストに失敗してしまったので、Downgradeして戻すことにする。 戻せるバージョンに何があるのか確認。

❯ vgo list -m -versions all
github.com/you/hello
golang.org/x/text v0.1.0 v0.2.0 v0.3.0
rsc.io/quote v1.0.0 v1.1.0 v1.2.0 v1.2.1 v1.3.0 v1.4.0 v1.5.0 v1.5.1 v1.5.2 v1.5.3-pre1
rsc.io/sampler v1.0.0 v1.2.0 v1.2.1 v1.3.0 v1.3.1 v1.99.99

rsc.io/samplerを一つ前のversionv1.3.1へ戻す。

❯ vgo get rsc.io/sampler@v1.3.1
vgo: finding rsc.io/sampler v1.3.1
vgo: downloading rsc.io/sampler v1.3.1

rsc.io/samplerがv1.99.99からv1.3.1にdowngradeされた。

❯ git diff go.mod
diff --git a/go.mod b/go.mod
index 6246735..a62aa4e 100644
--- a/go.mod
+++ b/go.mod
@@ -3,4 +3,5 @@ module github.com/you/hello
 require (
        golang.org/x/text v0.3.0
        rsc.io/quote v1.5.2
+       rsc.io/sampler v1.3.1
 )

ちゃんとテストも通る。

❯ vgo test all
?       github.com/you/hello    0.021s [no test files]
?       golang.org/x/text/internal/gen  0.020s [no test files]
ok      golang.org/x/text/internal/tag  (cached)
?       golang.org/x/text/internal/testtext 0.031s [no test files]
ok      golang.org/x/text/internal/ucd  (cached)
ok      golang.org/x/text/language  (cached)
ok      golang.org/x/text/unicode/cldr  (cached)
ok      rsc.io/quote    0.016s
ok      rsc.io/sampler  0.015s

もっと前のversionv.1.2.0にすることもできる。 rsc.io/quoteも依存しているので一緒にdowngradeする必要がある。

❯ vgo get rsc.io/sampler@v1.2.0
vgo: finding rsc.io/sampler v1.2.0
vgo: finding rsc.io/quote v1.5.1
vgo: finding rsc.io/quote v1.5.0
vgo: finding rsc.io/quote v1.4.0
vgo: finding rsc.io/sampler v1.0.0
vgo: downloading rsc.io/sampler v1.2.0

ただし、テストに失敗する。

❯ vgo test all
vgo: downloading rsc.io/quote v1.4.0
?       github.com/you/hello    0.019s [no test files]
?       golang.org/x/text/internal/gen  0.023s [no test files]
ok      golang.org/x/text/internal/tag  (cached)
?       golang.org/x/text/internal/testtext 0.035s [no test files]
ok      golang.org/x/text/internal/ucd  (cached)
ok      golang.org/x/text/language  (cached)
ok      golang.org/x/text/unicode/cldr  (cached)
--- FAIL: TestHello (0.00s)
    quote_test.go:12: Hello() = "こんにちは世界。", want "Hello, world."
FAIL
FAIL    rsc.io/quote    0.017s
--- FAIL: TestHello (0.00s)
    hello_test.go:31: Hello([fr en-US]) = "Bonjour le monde.", want "Bonjour la monde."
FAIL
FAIL    rsc.io/sampler  0.012s

noneで依存しているモジュールをすべて削除できる。

❯ vgo get rsc.io/sampler@none
vgo: finding rsc.io/quote v1.3.0

こうするとテストが通る（全然モジュールが残っていないけど）。

❯ vgo test all
vgo: downloading rsc.io/quote v1.3.0
?       github.com/you/hello    0.009s [no test files]
ok      rsc.io/quote    0.009s

Exclude

v1.99.99がうまく動かないことを記録したい。

事前準備として、最新化しておく。

❯ vgo get -u
vgo: finding rsc.io/quote latest
vgo: finding golang.org/x/text latest
vgo: finding rsc.io/quote latest
vgo: finding rsc.io/sampler latest
vgo: finding golang.org/x/text latest
vgo: finding rsc.io/sampler latest

たしかにv1.99.99になっている。

❯ vgo list -m all
github.com/you/hello
golang.org/x/text v0.3.0
rsc.io/quote v1.5.2
rsc.io/sampler v1.99.99

go.modにexclude "rsc.io/sampler" v1.99.99を追加すればよい。
合わせてgo.modでrsc.io/sampler v1.3.1にするのも忘れずに。

❯ vgo list -m all
github.com/you/hello
golang.org/x/text v0.3.0
rsc.io/quote v1.5.2
rsc.io/sampler v1.3.1

ちなみに、rsc.io/sampler v1.3.1にするのも忘れると以下のようにエラーになってくれるのでちゃんとExcludeされている。

❯ vgo get -u
vgo: github.com/you/hello() depends on excluded rsc.io/sampler(v1.99.99) with no newer version available

これでテストが通る。

❯ vgo test all
?       github.com/you/hello    0.016s [no test files]
?       golang.org/x/text/internal/gen  0.021s [no test files]
ok      golang.org/x/text/internal/tag  (cached)
?       golang.org/x/text/internal/testtext 0.021s [no test files]
ok      golang.org/x/text/internal/ucd  (cached)
ok      golang.org/x/text/language  (cached)
ok      golang.org/x/text/unicode/cldr  (cached)
ok      rsc.io/quote    (cached)
ok      rsc.io/sampler  (cached)

Replace

依存していたrsc.io/quoteを置き換えてみる。

❯ git clone https://github.com/rsc/quote ../quote

../quote/quote.goを以下のように書き換える。

// Hello returns a greeting.
func Hello() string {
    // return sampler.Hello() // これを消して
    return sampler.Glass() // こっちを追加
}

go.modの末尾にreplace "rsc.io/quote" v1.5.2 => "../quote"を追記する。 すると以下のようにreplaceされていることが確認できる。

❯ vgo list -m all
github.com/you/hello
golang.org/x/text v0.3.0
rsc.io/quote v1.5.2 => ../quote
rsc.io/sampler v1.3.1

buildして実行する。

❯ vgo build

❯ ./hello
私はガラスを食べられます。それは私を傷つけません。

references

• A Tour of Versioned Go (vgo) (Go & Versioning, Part 2)
• 和訳: A Tour of Versioned Go (vgo) (Go & Versioning, Part2)
• vgo

RustでTOMLを読み込む

toml-rsで、以下のPerson.tomlを読み込みます。

# Person.toml
[profile]
name = "Alice"
age = 20

準備

toml-rsに加えて、 DeserializeにSerdeを使うので、Cargo.tomlに以下を追記します。

# Cargo.toml
[dependencies]
serde = "1.0"
serde_derive = "1.0"
toml = "0.4"

実装

パースは、toml::from_str()でできるので、パースするための構造体を定義します。 今回は、読み込み元のtomlファイルに値が存在しないことを考慮して、Optionにしましたが、確実に値が存在するのであれば、Optionにしないのもありだと思います。(参照するときにunwrap()だらけになりそうなので...)

#[derive(Debug, Deserialize)]
struct Person {
    profile: Option<Profile>,
}

#[derive(Debug, Deserialize)]
struct Profile {
    name: Option<String>,
    age: Option<i32>,
}

ファイル読み込みからパースまでの実装です。

#[macro_use]
extern crate serde_derive;
extern crate toml;

use std::fs;
use std::io::{BufReader, Read};

#[derive(Debug, Deserialize)]
struct Person {
    profile: Option<Profile>,
}

#[derive(Debug, Deserialize)]
struct Profile {
    name: Option<String>,
    age: Option<i32>,
}

fn read_file(path: String) -> Result<String, String> {
    let mut file_content = String::new();

    let mut fr = fs::File::open(path)
        .map(|f| BufReader::new(f))
        .map_err(|e| e.to_string())?;

    fr.read_to_string(&mut file_content)
        .map_err(|e| e.to_string())?;

    Ok(file_content)
}

fn main() {
    let s = match read_file("./Person.toml".to_owned()) {
        Ok(s) => s,
        Err(e) => panic!("fail to read file: {}", e),
    };

    let person: Result<Person, toml::de::Error> = toml::from_str(&s);
    match person {
        Ok(p) => println!("{:#?}", p),
        Err(e) => panic!("fail to parse toml: {}", e),
    };
}

　実行

以下のようにパースできます。

❯ cargo run
Person {
    profile: Some(
        Profile {
            name: Some(
                "Alice"
            ),
            age: Some(
                20
            )
        }
    )
}

References

• toml-rs
• Serde
• RustでOption値やResult値を上手に扱う
• エラーハンドリング - プログラミング言語Rust
• 設定ファイル記述言語 TOML

ルーター自作本を試す環境をnetnsの仮想ネットワークで実現する

ルーター自作でわかるパケットの流れ/小俣　光之を読みました。

本文にほとんどがソースコードのためひたすら写経しました。 ちなみに後半に差し掛かったあたりで気づいたのですが、サポートページでソースコードは公開されています。

「せっかく書いたのだから動かしたい！」という欲求が生まれたものの、本書に書かれているような物理機器が手元になかったので、netnsで仮想ネットワークを構築しました。

構成

ネットワーク構成図は以下のとおりです。

環境

手元にあった環境のため古いですが、vagrantで立てたlinux環境を使いました。

$ cat /etc/redhat-release
CentOS release 6.6 (Final)

netnsを使ってネットワークを構築する

基本的にroot権限が必要です。

namespaceを区切る

host、RT、NextRouterをnamespaceを区切ることで実現します。

sudo ip netns add host
sudo ip netns add RT
sudo ip netns add NextRouter

以下で作成されたことが確認できます。

$ ip netns show
RT
host
NextRouter

ケーブルをつなぐ

Linux Network Namespaceでは、vethを物理ケーブルだと思うとわかりやすいです。 構成図の通り繋いでいきます。
命名規則は<ホスト名>_<I/F名>としました。NextRouterだけ文字制限なのか設定できなかったのでNRと略しています。 I/Fは、本書中でルータのLAN側をeth0、WAN側をeth1と指定されていたので、その他の機器でも統一しています。

sudo ip link add host_veth1 type veth peer name RT_veth0
sudo ip link add RT_veth1 type veth peer name NR_veth0
sudo ip link add NR_veth1 type veth peer name Linux_veth0

上記でケーブルは繋いだので、各機器に所属させます。

sudo ip link set host_veth1 netns host
sudo ip link set RT_veth0 netns RT
sudo ip link set RT_veth1 netns RT
sudo ip link set NR_veth0 netns NextRouter
sudo ip link set NR_veth1 netns NextRouter

上記のip link setを実行する前は、ホストOS(CentOS)上でip link showとすると見えていたリンクが以下のようになっていると思います。

$ ip link show
1: lo: <LOOPBACK,UP,LOWER_UP> mtu 65536 qdisc noqueue state UNKNOWN
    link/loopback 00:00:00:00:00:00 brd 00:00:00:00:00:00
2: eth0: <BROADCAST,MULTICAST,UP,LOWER_UP> mtu 1500 qdisc pfifo_fast state UP qlen 1000
    link/ether 08:00:27:2d:82:3a brd ff:ff:ff:ff:ff:ff
10: Linux_veth0: <BROADCAST,MULTICAST,UP,LOWER_UP> mtu 1500 qdisc pfifo_fast state DOWN qlen 1000
    link/ether 1a:dd:55:e7:f4:bd brd ff:ff:ff:ff:ff:ff

ifconfigでもOKですが、この時点ではifconfig -aとしないとDOWNしているI/Fは表示されないはずです。 loとeth0はvagrantが割り当てているのもので今回の対象でないので、Linux_veth0だけになっていることに注目してください。 言い換えると、host_veth1、RT_veth0、RT_veth1、NR_veth0、NR_veth1がそれぞれのnamespaceに所属したので、ホストOS(CentOS)から見えなくなっています。

IPアドレスを採番する

/24単位でセグメントを分ける設計としました。また、hostは拡張性を見据え（今は関係ないですが。。。）、若番から採番します。 next hopになる機器は老番からの採番としています。

sudo ip netns exec host ip addr add 192.168.0.1/24 dev host_veth1
sudo ip netns exec RT ip addr add 192.168.0.254/24 dev RT_veth0
sudo ip netns exec RT ip addr add 192.168.1.1/24 dev RT_veth1
sudo ip netns exec NextRouter ip addr add 192.168.1.254/24 dev NR_veth0
sudo ip netns exec NextRouter ip addr add 192.168.2.1/24 dev NR_veth1
sudo ip addr add 192.168.2.254/24 dev Linux_veth0

確認コマンドのため、ここでは省略しますが、ip addr showで採番は確認できます。

I/Fを立ち上げる

各機器のI/Fをupさせます。loも忘れずに。

sudo ip netns exec host ip link set lo up
sudo ip netns exec RT ip link set lo up
sudo ip netns exec NextRouter ip link set lo up

sudo ip netns exec host ip link set host_veth1 up
sudo ip netns exec RT ip link set RT_veth0 up
sudo ip netns exec RT ip link set RT_veth1 up
sudo ip netns exec NextRouter ip link set NR_veth0 up
sudo ip netns exec NextRouter ip link set NR_veth1 up
sudo ip link set Linux_veth0 up

確認コマンドのため、ここでは省略しますが、ip link showでstateがUPになっていることが確認でき、ifconfigでも見えるようになります。

ルーティングを設定する

各機器のWAN側にデフォルトゲートウェイを設定します。
ホストOS(CentOS)とNextRouterには、LAN側へstatic routeを設定します。

• ホストOS(CentOS): 192.168.0.0/24, 192.168.1.0/24
• NextRouter: 192.168.0.0/24

Direct Connectedになるセグメントはルーティング不要です。

sudo ip netns exec host ip route add default via 192.168.0.254
sudo ip netns exec RT ip route add default via 192.168.1.254
sudo ip netns exec NextRouter ip route add default via 192.168.2.254
sudo ip netns exec NextRouter ip route add 192.168.0.0/24 via 192.168.1.1
sudo ip route add 192.168.0.0/24 via 192.168.2.1
sudo ip route add 192.168.1.0/24 via 192.168.2.1

ip_forwardを有効化する

パケット転送を行えるようにip_forwardを有効化します。 ただし、RTは自作ルータのため転送機能があるためLinuxと機能が重複しないよう無効化します。 つまり、hostとNextRouterがip_forwardを有効化する対象です。

しかしnetnsでは、ネットワークまわりの設定だけがnamespaceごとに区切られていますが、ファイルシステムは共通のため、 sudo sysctl -w net.ipv4.ip_forward=1で設定するとRTも含めて全機器で有効化されてしまいます。

netnsでは、/etc/netns/<namespace名>が優先的に読み込まれるので、 RTについては、net.ipv4.ip_forward=0とした/etc/sysctl.confを/etc/netns/RT/sysctl.confとしてコピーしておけばOKです。 デフォルト値は、0のはずなので、念の為sysctl net.ipv4.ip_forwardでnet.ipv4.ip_forward = 0になっていることを確認したあと、以下のようにコピーしましょう。

sudo cp /etc/sysctl.conf /etc/netns/RT/

RT以外は共通で有効化するので以下を実行しましょう。

sudo sysctl -w net.ipv4.ip_forward=1

sysctl net.ipv4.ip_forwardでnet.ipv4.ip_forward = 1になっていればOKです。

自作ルータ

自作ルータのコードは、サポートページで公開されています。 もしくは本書を見ていただくのがよいと思います。

パラメータ

main.c中のパラメータは以下のように設定します。

PARAM Param = {"RT_veth0", "RT_veth1", 1, "192.168.0.254"};

実行してみる

hostからホストOS(CentOS)のveth0(192.168.2.254)にpingを打ってみましょう。

先に自作ルータを 起動せず にpingを打ってみましょう。

sudo ip netns exec RT bash #hostにログイン
$ ping 192.168.2.254 -c 1
PING 192.168.2.254 (192.168.2.254) 56(84) bytes of data.

--- 192.168.2.254 ping statistics ---
1 packets transmitted, 0 received, 100% packet loss, time 10000ms

予想通り、タイムアウトします。

では、いよいよ自作ルータを試します。 sudo ip netns exec RT bashでRTにログインしてからmakeした./routerを実行します。 (ログインしないとI/Fがないと怒られるはずです)

ping 192.168.2.254 -c 1
PING 192.168.2.254 (192.168.2.254) 56(84) bytes of data.
64 bytes from 192.168.2.254: icmp_seq=1 ttl=62 time=0.304 ms

--- 192.168.2.254 ping statistics ---
1 packets transmitted, 1 received, 0% packet loss, time 0ms
rtt min/avg/max/mdev = 0.304/0.304/0.304/0.000 ms

ちゃんとping応答がありました！

ルータ側のログ

おまけです。ルータ側のログを見てみましょう。 本書に記載のものに加えていくつか自分で見やすいようにデバッグログを追加しています。 <INFO>となっているものが追加したものです（デバッグしながらだったので他にもあるかも）。

$ ./router
NextRouter=192.168.1.254
RT_veth0 OK
addr=192.168.0.254
subnet=192.168.0.0
netmask=255.255.255.0
RT_veth1 OK
addr=192.168.1.1
subnet=192.168.1.0
netmask=255.255.255.0
router start

ここまでがルータ起動処理です。RT_veth0とRT_veth1を自作ルータに割り当て、NextRouterのIPを設定しています。

--------AnalyzePacket-------
<INFO> dst IP: 192.168.2.254
<INFO> subnet: 255.255.255.0
[0]:192.168.2.254 to NextRouter
----Ip2MacSearch----
Ip2Mac ADD [1] 192.168.1.254 = 0
<INFO> dst MAC: 00:00:00:00:00:00
Ip2Mac(192.168.1.254):NG
Ip2Mac(192.168.1.254):Send Arp Request
[0]:Ip2Mac:error or sending
AppendSendData:[1] 192.168.1.254 98bytes(Total=1:98bytes)

上記が192.168.2.254宛にpingを打ったログです。 192.168.2.0/24は自作ルータのI/Fが持っているセグメントではないので、NextRouterへパケットを転送しようとしています。 しかし、NextRouterのIP192.168.1.254に紐づくMACアドレスを知らないので、Arp Requestを投げ、pingパケットはバッファに積んでいます。

--------AnalyzePacket-------
[1]recv: ARP REPLY: 42bytes
----Ip2MacSearch----
AppendSendReqData:[1] 0
Ip2Mac EXIST [1] 192.168.1.254 = 0
Ip2Mac(192.168.1.254):OK
dst MAC(Ip2Mac): 7e:85:60:2f:76:fb
GetSendReqData:[1] 0
GetSendData:[1] 192.168.1.254 98bytes
iphdr.ttl 64->63
write:BufferSendOne:[1] 98bytes

Arp Replyが返ってきました。これでNextRouterのMACアドレスを知ることができたのでバッファにあったpingパケットを[1](RT_veth1)から送出しています。 L3ホップになるのでttlも減算しています。

--------AnalyzePacket-------
<INFO> dst IP: 192.168.0.1
<INFO> subnet: 255.255.255.0
[1]:192.168.0.1 to TargetSegment
----Ip2MacSearch----
Ip2Mac ADD [0] 192.168.0.1 = 0
<INFO> dst MAC: 00:00:00:00:00:00
Ip2Mac(192.168.0.1):NG
Ip2Mac(192.168.0.1):Send Arp Request
[1]:Ip2Mac:error or sending
AppendSendData:[1] 192.168.0.1 98bytes(Total=1:98bytes)

宛先が192.168.0.1となっていることがからもわかるように、pingの戻りパケットです。 先程と同じようにArp RequestでIP-MACアドレス解決を図っています。

--------AnalyzePacket-------
[0]recv: ARP REPLY: 42bytes
----Ip2MacSearch----
AppendSendReqData:[0] 0
Ip2Mac EXIST [0] 192.168.0.1 = 0
Ip2Mac(192.168.0.1):OK
dst MAC(Ip2Mac): 02:01:1d:da:db:04
GetSendReqData:[0] 0
GetSendData:[0] 192.168.0.1 98bytes
iphdr.ttl 63->62
write:BufferSendOne:[0] 98bytes

Arp Replyで192.168.0.1に紐づくMACアドレスが学習できたので、パケットを送出します。 ここでも、L3ホップになるのでttlも減算しています。

これらの処理が行われた結果、hostでもping応答を確認できたわけです。

最後に

Cでechoサーバやチャットサーバを書いたことがあったものの、写経時にtypoが多すぎてデバッグに時間取られました。 奇しくも動作をより理解する結果に繋がったので悪くはなかったかなと思っています。 本記事のnetnsも普段dockerがいい感じにやってくれる部分を知ることができたので、いい勉強になりました。

ちなみに、本記事タイトルは、本書タイトルそのままだと長くなりすぎなので、略しましたが通称あるんでしょうか。

ルーター自作でわかるパケットの流れ

References

• ルーター自作でわかるパケットの流れ/小俣　光之
• netnsを触ってみる - 隙あらば寝る
• netnsを使ったホスト内ネットワーク構築
• ip netns コマンドが意外にきめ細やかにコンテナを作ってくれる - TenForward
• Dockerのネットワーク管理とnetnsの関係 - めもめも

【Golang】DFS(深さ優先探索)による有向グラフのcycle detectを実装する

【Golang】DFS(深さ優先探索)による無向グラフのcycle detectを実装する - 逆さまにしたの続きで、今度は有向グラフのcycle detectです。 Detect Cycle in Directed Graph Algorithmを視聴したので、実装してみることにします。

有向グラフにおけるDFSによるcycle detectのアルゴリズム

有向グラフでは、同じDFSによるcycle detectでも、無向グラフのときと異なり、White Set、Grey Set、Black Setという3つの集合を利用します。特にGrey Setは、無向グラフにおけるVisited Setの役割を果たします。 これらの集合を使い、以下のアルゴリズムでDFSによるcycle detectを行います。

1. すべての頂点をWhite Setに追加する
2. White Setから頂点sを取り出す
3. 頂点sをGrey Setに加える
4. 頂点sの接続先である頂点cを順番に訪問する。未訪問の接続先がなくなった(葉のように元々接続先がない場合も含む)場合、頂点sをBlack Setに加え、一つ前に訪問した頂点を頂点sとして、4.を繰り返す
5. 頂点cがBlack Setに含まれていれば、4.における次の頂点へ
6. 頂点cがGrey Setに含まれていれば、cycleありとして探索終了
7. 5.,6.のいずれでもない(=頂点cがWhite Setに含まれる)場合は、3.から繰り返し
8. White Setが空になったら、cycleなしとして探索終了

※sはstartの意で命名(White Setから取り出す度に設定されるので厳密には始点ではないですが) ※cはcurrentの意で命名

例：cycleあり

2→4→5→2のcycleがある例です。

頂点0から上記のアルゴリズムを適用した場合のWhite Set、Grey Set、Black Setの変化を表にまとめると以下の通りです。

頂点	White Set	Grey Set	Black Set
-	0,1,2,3,4,5	-	-
0	1,2,3,4,5	0	-
1	2,3,4,5	0,1	-
3	2,4,5	0,1,3	-
1	2,4,5	0,1	3
4	2,5	0,1,4	3
5	2	0,1,4,5	3
2	-	0,1,2,4,5	3

最終行の時点で、頂点2がGrey Setに含まれるため、cycleありとなります。

例：cycleなし

上記の例から2→4の辺を除き、cycleをなくした例です。

こちらも先程と同様に、White Set、Grey Set、Black Setの変化を表にまとめます。途中までは一緒ですね。

頂点	White Set	Grey Set	Black Set
-	0,1,2,3,4,5	-	-
0	1,2,3,4,5	0	-
1	2,3,4,5	0,1	-
3	2,4,5	0,1,3	-
3	2,4,5	0,1	3
1	2,4,5	0,1	3
4	2,5	0,1,4	3
5	2	0,1,4,5	3
2	-	0,1,2,4,5	3
5	-	0,1,4,5	2,3
4	-	0,1,4	2,3,5
1	-	0,1	2,3,4,5
0	-	0	1,2,3,4,5
-	-	-	0,1,2,3,4,5

White Setを探索し終わったので、cycleなしとなります。

設計

隣接リスト

【Golang】DFS(深さ優先探索)による無向グラフのcycle detectを実装する - 逆さまにした同様に隣接リストで実装します。上記の例はそれぞれ以下のようにリストを持つことになります。

例：cycleあり

頂点	隣接リスト
0	1,2
1	3,4
2	4
3	-
4	5
5	2

例：cycleなし

頂点	隣接リスト
0	1,2
1	3,4
2	-
3	-
4	5
5	2

各Setをどうするか

White Set、Grey Set、Black Setをcolorという[]int型で実装することも考えましたが、有向グラフでは強連結でないグラフに対して扱いが難しくなりそうだったのでmapで実装します。 sliceとmapのdelete(+make)はどちらが速いのか - 逆さまにしたの結果が、無駄になってしまったのは残念ですが、Setと言っているのでmapのほうがわかりやすく実装できると考えて前に進むことにします。

実装

【Golang】DFS(深さ優先探索)による無向グラフのcycle detectを実装する - 逆さまにしたと同様に以下のようにGraphを定義します。

// Graph is a graph with n vertices and edges.
type Graph struct {
    n     int
    edges [][]int
}

コンストラクタも同様です。

// NewGraph creates a new graph with n vertices.
func NewGraph(n int) *Graph {
    g := &Graph{
        n:     n,
        edges: make([][]int, n),
    }
    return g
}

辺の追加

AddEdgeは、無向グラフと異なり、片方向にだけ辺を追加する点に注意です。

// AddEdge adds a edge connects vertex u to v and v to u.
func (g *Graph) AddEdge(u, v int) {
    g.edges[u] = append(g.edges[u], v)
}

DFSによるcycle detectの実装

基本的には、記事の先頭で述べたアルゴリズムを実装していくだけですが、White Setから頂点を選ぶ操作は以下のように実装しました。

c := -1
for c = range wSet {
  break
}

mapにはpopがないので、rangeでランダムに(mapに対するrangeは順序を保ちません)1つ取得し、breakしています。 これを踏まえた実装は以下です。

func dfs(c int, wSet, gSet, bSet map[int]struct{}, edges [][]int) bool {
    delete(wSet, c)
    gSet[c] = struct{}{}

    for _, n := range edges[c] {
        _, ok := bSet[n]
        if ok {
            continue
        }
        _, ok = gSet[n]
        if ok {
            return true
        }
        if dfs(n, wSet, gSet, bSet, edges) {
            return true
        }
    }

    delete(gSet, c)
    bSet[c] = struct{}{}
    return false
}

呼び出し側では、初期化も含めて行っています。

func (g *Graph) ExistsCycle() bool {
    wSet := make(map[int]struct{}, g.n)
    gSet := make(map[int]struct{}, g.n)
    bSet := make(map[int]struct{}, g.n)

    for i := 0; i < g.n; i++ {
        wSet[i] = struct{}{}
    }

    for len(wSet) != 0 {
        c := -1
        for c = range wSet {
            break
        }
        if dfs(c, wSet, gSet, bSet, g.edges) {
            return true
        }
    }
    return false
}

テスト

最後に上述の例で正しく動作することを試してみます。

例：cycleあり

頂点	隣接リスト
0	1,2
1	3,4
2	4
3	-
4	5
5	2

g := directed.NewGraph(6)
g.AddEdge(0, 1)
g.AddEdge(0, 2)
g.AddEdge(1, 3)
g.AddEdge(1, 4)
g.AddEdge(2, 4)
g.AddEdge(4, 5)
g.AddEdge(5, 2)

fmt.Println(g.ExistsCycle()) // true

例：cycleなし

頂点	隣接リスト
0	1,2
1	3,4
2	-
3	-
4	5
5	2

g := directed.NewGraph(6)
g.AddEdge(0, 1)
g.AddEdge(0, 2)
g.AddEdge(1, 3)
g.AddEdge(1, 4)
g.AddEdge(4, 5)
g.AddEdge(5, 2)

fmt.Println(g.ExistsCycle()) // false

References

• Detect Cycle in Directed Graph Algorithm
• Go言語 - enumを定義する
• 強連結成分分解の意味とアルゴリズム

sliceとmapのdelete(+make)はどちらが速いのか

Golangでmapとsliceどちらが速いのかに引き続いて、要素を削除する場合のベンチマークを取ってみる。

やり方

slice

メモリリークしないようにSliceTricksにある以下の方法で要素を削除する。

copy(a[i:], a[i+1:])
a[len(a)-1] = nil // or the zero value of T
a = a[:len(a)-1]

map

組み込みのdeleteで削除する

delete(map[typeA]typeB, typeA)

条件

• sliceは[]int型とする
• mapはmap[int]int型とする
• sliceから削除したい要素のindexはn/2を使う
• mapから削除したい要素をn/2とする

環境

macOS High Sierra version 10.13.4（17E202）
MacBook Pro (Retina, 13-inch, Early 2015)
2.7 GHz Intel Core i5
16 GB 1867 MHz DDR3
Intel Iris Graphics 6100 1536 MB

❯ go version
go version go1.10.1 darwin/amd64

実装

map, sliceどちらも削除前の状態を毎回使いまわす必要があるが、どちらも参照型で実装されるので、毎回makeで作り直すことにする。 make自体がmapとsliceで差がある(Appendix参照)ので、それぞれmakeするだけベンチマークも測定し、差分(make+delete-make)を結果とする。 makeに掛かる時間は要素数に単調増加するので、それぞれ差分の計算は、同じ要素数でmakeした結果から求める。

ベンチマークの実装は以下の通り。

slice

func benchmarkOfDeleteFromSlice(n int, b *testing.B) {
    idx := n / 2

    for i := 0; i < b.N; i++ {
        s := make([]int, n)
        copy(s[idx:], s[idx+1:])
        s[len(s)-1] = 0
        s = s[:len(s)-1]
    }
}

func benchmarkOfMakeSlice(n int, b *testing.B) {
    for i := 0; i < b.N; i++ {
        _ = make([]int, n)
    }
}

map

func benchmarkOfDeleteFromMap(n int, b *testing.B) {
    idx := n / 2

    for i := 0; i < b.N; i++ {
        m := make(map[int]int, n)
        delete(m, idx)
    }
}
func benchmarkOfMakeMap(n int, b *testing.B) {
    for i := 0; i < b.N; i++ {
        _ = make(map[int]int, n)
    }
}

結果

要素数が少ないとmakeに掛かる時間が測定によってばらつきがあり、差分がマイナスになったが、要素数が1000を超えたあたりからmapよりsliceが有利であることがわかる。またsliceは削除に要する時間が要素数に依らず、ある程度一定の値となっている。

Appendix

ベンチマーク結果の生データは以下の通り。

BenchmarkOfDeleteFromSlice10-4        30000000           40.0 ns/op
BenchmarkOfDeleteFromSlice30-4         20000000           66.5 ns/op
BenchmarkOfDeleteFromSlice70-4         10000000          134 ns/op
BenchmarkOfDeleteFromSlice100-4        10000000          229 ns/op
BenchmarkOfDeleteFromSlice300-4         3000000          554 ns/op
BenchmarkOfDeleteFromSlice700-4         1000000         1034 ns/op
BenchmarkOfDeleteFromSlice1000-4        1000000         1478 ns/op
BenchmarkOfDeleteFromSlice3000-4         300000         3903 ns/op

BenchmarkOfMakeSlice10-4               50000000           33.8 ns/op
BenchmarkOfMakeSlice30-4               20000000           59.6 ns/op
BenchmarkOfMakeSlice70-4               10000000          119 ns/op
BenchmarkOfMakeSlice100-4              10000000          173 ns/op
BenchmarkOfMakeSlice300-4               3000000          494 ns/op
BenchmarkOfMakeSlice700-4               2000000          938 ns/op
BenchmarkOfMakeSlice1000-4              1000000         1465 ns/op
BenchmarkOfMakeSlice3000-4               300000         3785 ns/op

BenchmarkOfDeleteFromMap10-4           20000000          102 ns/op
BenchmarkOfDeleteFromMap30-4            5000000          255 ns/op
BenchmarkOfDeleteFromMap70-4            3000000          604 ns/op
BenchmarkOfDeleteFromMap100-4           3000000          583 ns/op
BenchmarkOfDeleteFromMap300-4           1000000         1546 ns/op
BenchmarkOfDeleteFromMap700-4            500000         2992 ns/op
BenchmarkOfDeleteFromMap1000-4           200000         6079 ns/op
BenchmarkOfDeleteFromMap3000-4           100000        12120 ns/op

BenchmarkOfMakeMap10-4                 20000000           97.8 ns/op
BenchmarkOfMakeMap30-4                  5000000          251 ns/op
BenchmarkOfMakeMap70-4                  3000000          590 ns/op
BenchmarkOfMakeMap100-4                 2000000          580 ns/op
BenchmarkOfMakeMap300-4                 1000000         1563 ns/op
BenchmarkOfMakeMap700-4                  500000         3100 ns/op
BenchmarkOfMakeMap1000-4                 200000         5980 ns/op
BenchmarkOfMakeMap3000-4                 100000        11305 ns/op

すべてまとめてグラフにすると以下の通り。

makeのみの所要時間は以下の通り。

一貫して、sliceのほうがmakeに要する時間は少なかった。 sliceとmapの内部実装も以下の通りで、sliceのほうが初期化に掛かる時間が少ないと思われる。

sliceの内部実装

type slice struct {
    array unsafe.Pointer
    len   int
    cap   int
}

mapの内部実装

// A hash iteration structure.
// If you modify hiter, also change cmd/internal/gc/reflect.go to indicate
// the layout of this structure.
type hiter struct {
    key         unsafe.Pointer // Must be in first position.  Write nil to indicate iteration end (see cmd/internal/gc/range.go).
    value       unsafe.Pointer // Must be in second position (see cmd/internal/gc/range.go).
    t           *maptype
    h           *hmap
    buckets     unsafe.Pointer // bucket ptr at hash_iter initialization time
    bptr        *bmap          // current bucket
    overflow    *[]*bmap       // keeps overflow buckets of hmap.buckets alive
    oldoverflow *[]*bmap       // keeps overflow buckets of hmap.oldbuckets alive
    startBucket uintptr        // bucket iteration started at
    offset      uint8          // intra-bucket offset to start from during iteration (should be big enough to hold bucketCnt-1)
    wrapped     bool           // already wrapped around from end of bucket array to beginning
    B           uint8
    i           uint8
    bucket      uintptr
    checkBucket uintptr
}

References

• Golangでmapとsliceどちらが速いのか
• SliceTricks
• Source file src/runtime/hashmap.go - The Go Programming Language
• Source file src/runtime/slice.go - The Go Programming Language