blog.syfm

徒然なるままに考えていることなどを書いていくブログ

esa、Google Cloud Functions、Hugo、Netlify で簡易 CMS をつくる

Hugo は、Markdown ファイルを元にブログポストの HTML を静的に生成することのできるツールです。Hugo で生成した HTML を Netlify や GitHub Pages にデプロイすることでブログをホストするためのサーバを用意せずにブログを公開することができます。

しかし、Hugo はデプロイのトリガーとして基本的に Git リポジトリへの push を必要とします。PC でブログを書いている場合はあまり気にならないかもしれませんが、スマホで雑にポストを書きたい時は Git 操作をするのは簡単ではありません。

そこで、esa でポストを管理しつつ、デプロイのトリガーまでできるしくみをシュッと作ってみました。

esa には Webhook が用意されており、ポストの変更に合わせて発火することができます。また、ポストの状態として WIP と (ほとんど) 完成が用意されているため、これを利用して下書き機能として利用できそうです。タグ機能もそのままポストに付けられたタグとして利用できるでしょう。

esa で設定した Webhook の発火により、Cloud Functions が起動し、変更された Markdown のコンテンツを Git リポジトリに適用し、push します。push により、Netlify が発火し、HTML を生成した後にサイトへデプロイします。 これらを図に表すと以下のような感じになります。

f:id:ktr_0731:20190304184259j:plain

esa の Webhook は以下のように設定します。ブログポストとして使うカテゴリ以下に対して Webhook を有効にします。(ここでは /blog 以下を対象にしています。) URL には Google Cloud Functions の関数への URL (後述) を指定します。

f:id:ktr_0731:20190303003311p:plain

Google Cloud Functions に登録する関数の例は以下のようになります。GitHub 上のブログコンテンツを管理するリポジトリをローカルへクローンし、Webhook から受け取ったコンテンツをコミットします。そしてそのコミットを GitHub へ push しています。

package p

import (
    "encoding/json"
    "fmt"
    "io"
    "net/http"
    "os"
    "path/filepath"
    "strings"
    "time"

    "github.com/pkg/errors"

    "gopkg.in/src-d/go-billy.v4/memfs"
    git "gopkg.in/src-d/go-git.v4"
    "gopkg.in/src-d/go-git.v4/plumbing/object"
    githttp "gopkg.in/src-d/go-git.v4/plumbing/transport/http"
    "gopkg.in/src-d/go-git.v4/storage/memory"
)

const (
    kindCreate = "post_create"
    kindUpdate = "post_update"
    kindDelete = "post_delete"
)

var tmpl = `---
title: "%s"
date: %s
type: posts
draft: false
tags:
%s
---

%s
`

var (
    repoURL     string
    githubToken string
    githubName  string

    authorName  string
    authorEmail string
)

var auth *githttp.BasicAuth

type request struct {
    Kind string `json:"kind"`
    Post post   `json:"post"`
}

type post struct {
    Name         string `json:"name"`
    BodyMarkdown string `json:"body_md"`
    WIP          bool   `json:"wip"`
    URL          string `json:"url"`
}

func init() {
    if repoURL = os.Getenv("REPO_URL"); repoURL == "" {
        panic("$REPO_URL must be required")
    }
    if githubToken = os.Getenv("GITHUB_TOKEN"); githubToken == "" {
        fmt.Fprintln(os.Stderr, "$GITHUB_TOKEN is not found")
    }
    if githubName = os.Getenv("GITHUB_NAME"); githubName == "" {
        panic("$GITHUB_NAME must be required")
    }
    if authorName = os.Getenv("AUTHOR_NAME"); authorName == "" {
        fmt.Fprintln(os.Stderr, "$AUTHOR_NAME is not found")
    }
    if authorEmail = os.Getenv("AUTHOR_EMAIL"); authorEmail == "" {
        fmt.Fprintln(os.Stderr, "$AUTHOR_EMAIL is not found")
    }

    if githubToken != "" {
        auth = &githttp.BasicAuth{
            Username: githubName,
            Password: githubToken,
        }
    }

}

func UpdatePost(w http.ResponseWriter, r *http.Request) {
    defer r.Body.Close()
    body, err := decodeRequestBody(r.Body)
    if err != nil {
        fmt.Fprintf(w, "failed to get the request body: %s", err)
        w.WriteHeader(http.StatusBadRequest)
        return
    }

    if body.Post.WIP {
        w.WriteHeader(http.StatusNotModified)
        return
    }

    title, tags := decodeName(body.Post.Name)

    switch body.Kind {
    case kindCreate, kindUpdate:
        var tagStr string
        for _, tag := range tags {
            tagStr += "  - " + tag + "\n"
        }
        content := fmt.Sprintf(tmpl, title, time.Now().Format(time.RFC3339), tagStr, body.Post.BodyMarkdown)
        if err := flush(title, content); err != nil {
            panic(err)
        }
        fmt.Fprintln(w, "done")
    case kindDelete:
        if err := remove(title); err != nil {
            panic(err)
        }
        fmt.Fprintln(w, "done")
    }
}

func flush(title, body string) error {
    fs := memfs.New()
    repo, err := git.Clone(memory.NewStorage(), fs, &git.CloneOptions{URL: repoURL, Auth: auth})
    if err != nil {
        return errors.Wrap(err, "failed to clone the blog repository")
    }
    fname := fmt.Sprintf("content/posts/%s.md", strings.Replace(title, " ", "-", -1))

    f, err := fs.Create(fname)
    if err != nil {
        return errors.Wrap(err, "failed to write content to the file")
    }
    defer f.Close()
    _, err = io.WriteString(f, body)
    if err != nil {
        return errors.Wrap(err, "failed to write content to the file")
    }

    w, err := repo.Worktree()
    if err != nil {
        return errors.Wrap(err, "failed to get the work tree")
    }
    _, err = w.Add(fname)
    if err != nil {
        return errors.Wrap(err, "failed to add the written file")
    }
    _, err = w.Commit(fmt.Sprintf("create or update %s", fname), &git.CommitOptions{
        Author: &object.Signature{
            Name:  authorName,
            Email: authorEmail,
            When:  time.Now(),
        },
    })
    if err != nil {
        return errors.Wrap(err, "failed to commit the changes")
    }
    if err := repo.Push(&git.PushOptions{Auth: auth}); err != nil {
        return errors.Wrap(err, "failed to push the committed changes")
    }
    return nil
}

func remove(title string) error {
    fs := memfs.New()
    repo, err := git.Clone(memory.NewStorage(), fs, &git.CloneOptions{URL: repoURL, Auth: auth})
    if err != nil {
        return errors.Wrap(err, "failed to clone the blog repository")
    }
    fname := fmt.Sprintf("content/posts/%s.md", strings.Replace(title, " ", "-", -1))

    err = fs.Remove(fname)
    if err != nil {
        return errors.Wrap(err, "failed to remove the post")
    }

    w, err := repo.Worktree()
    if err != nil {
        return errors.Wrap(err, "failed to get the work tree")
    }
    _, err = w.Add(fname)
    if err != nil {
        return errors.Wrap(err, "failed to add the removed file")
    }
    _, err = w.Commit(fmt.Sprintf("delete %s", fname), &git.CommitOptions{
        Author: &object.Signature{
            Name:  authorName,
            Email: authorEmail,
            When:  time.Now(),
        },
    })
    if err != nil {
        return errors.Wrap(err, "failed to commit the changes")
    }
    if err := repo.Push(&git.PushOptions{Auth: auth}); err != nil {
        return errors.Wrap(err, "failed to push the committed changes")
    }
    return nil
}

func decodeRequestBody(b io.Reader) (*request, error) {
    var r request
    if err := json.NewDecoder(b).Decode(&r); err != nil {
        return nil, err
    }
    return &r, nil
}

func decodeName(n string) (string, []string) {
    n = filepath.Base(n)
    prev := strings.Index(n, "#")
    if prev == -1 {
        return n, nil
    }

    var tags []string
    var title string
    title = strings.TrimSpace(n[:prev])

    for {
        current := strings.Index(n[prev+1:], "#")
        if current == -1 {
            tags = append(tags, strings.TrimSpace(n[prev+1:]))
            return title, tags
        }
        tags = append(tags, strings.TrimSpace(n[prev+1:prev+current+1]))
        prev += current + 1
    }
    return title, tags
}

UpdatePost 関数を実行する関数に指定し、URL を先程の esa の Webhook に登録します。

Netlify ⇔ Hugo でやることは以下のページそのままなので割愛します。

gohugo.io

まとめ

esaCMS 的に使うことで Git 操作なしにブログの更新ができるようになりました。
今回紹介した、 Cloud Functions で使用しているソースは非常に単純なものなので、必要に応じて変更してください。

fzf ライクな fuzzy-finder を提供する Go ライブラリを書いた

f:id:ktr_0731:20190209113907p:plain

fuzzy-finder

fzffzyskim などの fuzzy-search (あいまい検索) を提供する CLI ツールの登場により、コマンドラインでの操作はますます表現豊かになっています。
例えば、カレントシェルのコマンドヒストリの一覧から fuzzy-finder を使って選択したり、ghq + fuzzy-finder + cd の組み合わせで選択したリポジトリのあるディレクトリへ移動したりといったケースが挙げられます。

また、fuzzy-finder それ自体をコア機能として組み込んだツールも増えています。例えば、cd コマンドの拡張である enhancd はパスの履歴を保持し、fuzzy-finder を使って移動したいディレクトリへすぐに移動することができます。また、拙作の itunes-cli は、iTunes で管理されている曲の一覧を入力にし、fuzzy-finder で選択・再生を行う機能を提供しています。

fuzzy-finder ツールの限界

しかし、fuzzy-finder は同名の要素を扱うことができない問題があります。
たとえば、先程紹介した itunes-cli を例として考えてみます。曲名はユニークではないので、当然衝突する可能性があります。そういった場合に fuzzy-finder で適切に選択するにはその他の情報も曲名と一緒に表示する必要がありますが、

  • 曲名は同じだが、アーティストが違う
  • 曲名もアーティストも同じだが、収録アルバムが違う
  • 曲名も収録アルバムも同じだが、アーティストが違う

ちょっと考えただけでこれだけのケースが挙げられます。そして、これらのケースをユニークに扱うためには、一行に曲名、アーティスト名、収録アルバム名を表示しなくてはならないため、ユーザの視点から見ると非常に冗長だと感じるでしょう。

インストールの複雑さ

インストールの複雑さに関する問題は、fuzzy-finder を組み込むツールをインストールする場合に発生します。そういったツールは内部でコマンド実行をすることで fuzzy-finder を起動しますが、そのためには fuzzy-finder が既にインストールされていなければいけません。もしその環境に fuzzy-finder がインストールされていないのであれば、ツールとは別に fuzzy-finder をインストールしなければいけません。また、ツールが検知するために環境変数などで fuzzy-finder のパスを指定しなければいけないかもしれません。

fuzzy-finder をライブラリとして提供する

github.com

上記二つのような問題を解決するために go-fuzzyfinder をつくりました。例えば以下のようなコードを書くだけで簡単に fuzzy-finder を起動できます。

type Track struct {
    Name      string
    AlbumName string
    Artist    string
}
var tracks = []Track{
    {"foo", "album1", "artist1"},
    {"bar", "album1", "artist1"},
    {"foo", "album2", "artist1"},
    {"baz", "album2", "artist2"},
    {"baz", "album3", "artist2"},
}

idx, err := fuzzyfinder.Find(tracks, func(i int) string {
    return tracks[i].Name
})

f:id:ktr_0731:20190208235230p:plain

この関数は戻り値として選択されたスライスのインデックスを返します。
しかし、上記の UI では先程挙げた、同名の行をうまく扱えない問題が発生しています。普通の fuzzy-finder の場合、この問題を解決するには一行あたりの情報量を増やすしかありません。 go-fuzzyfinder ではこの問題に対処するためにプレビューウインドウを提供しています。この機能は fzf を非常に参考にしています。 プレビューウインドウ付きで fuzzy-finder を起動するためには、以下のようにコードを変更します。

idx, _ := fuzzyfinder.Find(
    tracks,
    func(i int) string {
        return tracks[i].Name
    },
    fuzzyfinder.WithPreviewWindow(func(i, w, h int) string {
        return fmt.Sprintf("%s\n\nArtist: %s\nAlbum:  %s",
            tracks[i].Name,
            tracks[i].Artist,
            tracks[i].AlbumName)
    }))

f:id:ktr_0731:20190209000431p:plainf:id:ktr_0731:20190209000439p:plain
従来の方法とプレビューウインドウを使う方法

左の画像は従来の fuzzy-finder が取らなければならない方法で、右の画像がプレビューウインドウを使った方法です。付随する情報をプレビューウインドウへ分離したことでシンプルなインターフェースになっています。

この他にもいくつか機能がありますが、詳しくは GoDoc をご覧ください。

まとめ

fuzzy-finder をライブラリ化したことで、従来では難しかったことも実現できるようになりました。ぜひ使ってみてください!

fuzzy-finder で使われるスコアリングアルゴリズム

fuzzy-finder を構成するアルゴリズム

fzy や fzf といった fuzzy-finder を使うと、stdin などからリストを受け取り、ユーザの入力によってマッチする行を絞り込むことができます。このとき、入力文字列の各文字は隣接している必要がありません。例えば、以下の画像のように baz という入力が与えられた時、これにマッチする行が絞り込まれます。また、マッチした行のリストは、入力値に基づいてより最適な順番にソートされて表示されています。同じく以下の画像の例を見てみると、入力後では baz という行が foobarbaz よりもセレクタに近い位置に表示されていることが分かります。このように、入力値が曖昧でも目当ての文字列を即座に見つけることができるのが fuzzy-finder の便利なところです。

f:id:ktr_0731:20190130020555p:plainf:id:ktr_0731:20190130020634p:plain

上記のような機能は、approximate string matching と呼ばれ、主に以下の二つから構成されています。

  • 入力文字列とマッチする行を絞り込む処理 (マッチング)
  • ある行が入力文字列と比べてどのくらい類似しているかの評価処理 (スコアリング)

マッチングに関しては多少の差異はあるものの、単純な二重ループで各入力文字が出現するかどうかを調べれば良いだけなので、簡単に実装することができます。当然正規表現を使っても良いですが、ベンチマークを取ってみると圧倒的に素朴なループの方が早いので、どうしても必要なケースがない限り使うことはないかと思います。

スコアリングはユーザの体験に直結する部分で、fuzzy-finder の中でも重要かつ難しい部分です。ここでは、実装の一つとして fzy を見てみます。 fzy には ALGORITHM.md という、fzy で使われているアルゴリズムを解説しているマークダウンファイルがあります。

github.com

このファイルを見ると、fzy ではスコアリングを Levenshtein distance (Edit distance、編集距離) ベースの問題として扱い、Wagner-Fischer 法や Needleman-Wunsch (グローバルアラインメント) 法をベースとしたアルゴリズムを使用しているといった記述があります。

編集距離 (Levenshtein distance) と Wagner-Fischer 法

編集距離は以下のように定義されています。

二つの文字列間の編集距離は挿入、削除、置換によって片方の文字列をもう一方の文字列に変形するのにかかる最小の編集回数 *1

編集距離の基本的な考え方は 編集距離 (Levenshtein Distance) - naoyaのはてなダイアリー が非常に分かりやすいです。

編集距離を求めるために主に使われている手法が Wagner-Fischer 法で、動的計画法を用いたアルゴリズムです。Wikipedia に記載されている疑似コードを実装してみると以下のようなコードになります。見て分かる通り、Wagner-Fischer 法の時間計算量は O(mn) (m、n はそれぞれ二つの文字列の長さ) となります。

def wagner_fischer(s1, s2):
    m = [[0] * (len(s2)+1) for _ in range(len(s1)+1)]
    for i in range(len(s1)+1):
        m[i][0] = i
    for j in range(len(s2)+1):
        m[0][j] = j

    for i in range(1, len(s1)+1):
        for j in range(1, len(s2)+1):
            insert = m[i-1][j] + 1
            delete = m[i][j-1] + 1
            replace = m[i-1][j-1] + 1 if s1[i-1] != s2[j-1] else m[i-1][j-1]
            m[i][j] = min(insert, delete, replace)

    return m[len(s1)][len(s2)]

print(wagner_fischer("kitten", "sitting")) # 3

Needleman-Wunsch 法 (グローバルアラインメント)

Needleman-Wunsch 法 は、バイオインフォマティクス分野で DNA などの配列から類似領域を特定するためのシーケンスアラインメントアルゴリズムです。*2 このアルゴリズム動的計画法を用いており、実装は Wagner-Fischer 法と非常に似ています。シーケンスアラインメントアルゴリズムでは、二つの文字列の共通列が揃うようにギャップが挿入されます。ある地点 ij におけるスコア m[i][j] は以下の 3 つが考えられます。

  • スコア m[i-1][j] にギャップが発生した
  • スコア m[i][j-1] にギャップが発生した
  • スコア m[i-1][j-1] に加えて最後に追加した文字がマッチ or ミスマッチしている場合

これらのうち、最もスコアが大きいものを実際のスコアとします。

def needleman_wunsch(s1, s2):
    GAP = 2
    MATCH = 2
    MISMATCH = 1

    m = [[0] * (len(s2)+1) for _ in range(len(s1)+1)]
    for i in range(len(s1)+1):
        m[i][0] = i * -GAP
    for j in range(len(s2)+1):
        m[0][j] = j * -GAP

    for i in range(1, len(s1)+1):
        for j in range(1, len(s2)+1):
            s1gap = m[i-1][j] - GAP
            s2gap = m[i][j-1] - GAP
            match = m[i-1][j-1] + MATCH if s1[i-1] == s2[j-1] else m[i-1][j-1] - MISMATCH
            m[i][j] = max(s1gap, s2gap, match)

    return m[len(s1)][len(s2)]

needleman_wunsch("GCATGCU", "GATTACA") で関数を呼び出した後、m は以下のようになっています。

   |       G   A   T   T   A   C   A
------------------------------------
   |   0  -2  -4  -6  -8 -10 -12 -14
  G|  -2   2   0  -2  -4  -6  -8 -10
  C|  -4   0   1  -1  -3  -5  -4  -6
  A|  -6  -2   2   0  -2  -1  -3  -2
  T|  -8  -4   0   4   2   0  -2  -4
  G| -10  -6  -2   2   3   1  -1  -3
  C| -12  -8  -4   0   1   2   3   1
  U| -14 -10  -6  -2  -1   0   1   2

m を構築する際に m[0][0] から m[len(s1)][len(s2)] までで、それぞれ最も大きな値だったセルをパスとします。もし、最大値が複数ある場合は、パスが分岐します。m の構築後、記録したパスを m[0][0] へ向かってトレースバックしていくことでアラインメントを求めることができます。この時、ある時点での進路が左上であればマッチまたはミスマッチ、左であれば s1 へギャップの挿入、上であれば s2 へギャップの挿入を行います。例えば、上記の例では以下のようなアラインメントが一つの解として得られます。

GCATG-CU
G-ATTACA

そして、m[len(s1)][len(s2)] がこのグローバルアラインメントにおけるスコアになっています。

Smith-Waterman 法 (ローカルアラインメント)

一方、fzf では Smith-Waterman 法 が使われています。*3 このアルゴリズムは Needleman-Wunsch 法とほとんど同じですが、各セルの最小値が 0 未満にならないように設定されています。

def smith_waterman(s1, s2):
    GAP = 2
    MATCH = 2
    MISMATCH = 1

    m = [[0] * (len(s2)+1) for _ in range(len(s1)+1)]

    max_score = 0
    for i in range(1, len(s1)+1):
        for j in range(1, len(s2)+1):
            s1gap = m[i-1][j] - GAP
            s2gap = m[i][j-1] - GAP
            match = m[i-1][j-1] + MATCH if s1[i-1] == s2[j-1] else m[i-1][j-1] - MISMATCH
            m[i][j] = max(s1gap, s2gap, match, 0)
            max_score = max(max_score, m[i][j])

    return max_score

先程と同様の入力で実行すると m の状態は以下のようになります。

   |       G   A   T   T   A   C   A
------------------------------------
   |   0   0   0   0   0   0   0   0
  G|   0   2   0   0   0   0   0   0
  C|   0   0   1   0   0   0   2   0
  A|   0   0   2   0   0   2   0   4
  T|   0   0   0   4   2   0   1   2
  G|   0   2   0   2   3   1   0   0
  C|   0   0   1   0   1   2   3   1
  U|   0   0   0   0   0   0   1   2

Smith-Waterman 法では m[len(s1][len(s2)] ではなく、最大スコアを出したセルの位置を記録しておき、その地点からセル 0 になるまで左上へと遡っていきます。 上記の例では、m[4][3] の値 4 が最大スコアであるため、その位置から開始し、 m[0][0] まで遡ります。Needleman-Wunsch 法と同様にパスを求めると、以下のようになります。

GCAT
G-AT

最大スコアがこのローカルアラインメントにおけるスコアになります。Smith-Waterman 法は、配列全体ではなく、局所的なアラインメントを求めるため、全体としてはあまり類似していない文字列間のスコアを求めるのに向いています。

ギャップペナルティ

通常、シーケンスアラインメントではギャップの挿入によるペナルティを課し、スコアを減点します。ペナルティ戦略にはいくつかの種類がありますが、ここではリニアギャップペナルティとアフィンギャップペナルティを紹介します。 ギャップペナルティに関しては Wikipedia のページ が良い感じに概要がまとまっていて感覚を掴むのに適しています。

リニアギャップペナルティは、ギャップの長さ (拡張) に比例してギャップペナルティが線形に増加します。増分は実装によります。 上記の Python のコードもリニアギャップペナルティを用いていて、増分は GAP = 2 です。

アフィンギャップペナルティは、リニアギャップペナルティに加えてギャップの開始にも一定のペナルティを課します。通常、ギャップの拡張に関するペナルティを大きくするとギャップの長さが長いほどスコアが低くなり、ギャップの開始に関するペナルティを大きくすると非連続なギャップの数だけスコアが低くなります。

マッチボーナス

fzy や fzf では、さらにギャップペナルティとは反対に、スコアを増加させることのできるマッチボーナスを導入しています。こちらも実装により様々ですが、以下のようなルールが採用されることが多いようです。

  • 単語の先頭などの特殊な箇所にマッチしている
  • マッチしている文字が隣接している

fzy や fzf などの fuzzy-finder はこのペナルティやボーナスのルールを調整することでより目的に合った候補を表示することができています。 ただし、闇雲にマッチボーナスを付与してしまうと適切ではない結果が生まれてしまう可能性があるため、ギャップペナルティとのバランスが重要です。fzf のコードコメントにはスコアリングルールが非常に詳細に記述されているので、それを読んでみると雰囲気をつかめるかと思います。

github.com

まとめ

fzy や fzf を元に、fuzzy-finder を構成しているアルゴリズムの概要を紹介しました。最近 Go ライブラリとしての fuzzy-finder をつくるためにこれらのアルゴリズムを学んでいて、だいたいの実装は終わったのですがやはりギャップペナルティとマッチボーナスをどう設定するかで悩んでいます。頑張って完成させるぞー。

*1:http://books.google.co.jp/books?id=Ofw5w1yuD8kC&pg=PA216&dq=%22%22

*2:バイオインフォマティクスは全くの無知なのでこれ以上のことはわかりません。

*3:入力文字列長が長すぎる場合は、時間計算量 O(n) で動作する別なアルゴリズムに切り替えています。