Rustでgit stashを検索できるツールを書いた

仕事でよくgit stashを使うのですが「あれ？あのstashどれだっけ？」が頻発します。git stash show stash@{n}を複数回行えば見つかるのですが、結構面倒くさいです。ということでstashを検索してくれるCLIツールを書きました。
Rust the bookを読みながらRustで書いています。今年はRust通して静的型付け言語やっていきたい。 github.com

https://crates.io/crates/harvest

crates.ioとHomebrewに公開してるので、Rustつかってない人でもbrewからインストールすることができます。

• cargo
  cargo install harvest
• Homebrew
  brew tap QWYNG/harvest
brew install harvest

使い方

harvest <pattern> で今のブランチとstashの間のdiffからpatternを検索してヒットしたstashを以下の形式で標準出力します。

harvest fn
stash@{0}: WIP on master: beb5221 rm tests module
 src/bm.rs | 2 ++
 1 file changed, 2 insertions(+)

stash@{1}: WIP on master: beb5221 rm tests module
 src/lib.rs | 1 +
 1 file changed, 1 insertion(+)

patternといってますが正規表現とかは渡せません。
なぜ検索結果の出力なのに検索した文字列が実際に書かれている箇所を抜き出さないかというと、僕がこっちのほうが見やすいと思ったからです。
単純にgit diff stash＠{n}の中身を全探索してるだけなので、例えばharvest +と実行すると全部のstashが出てきます。
文字列検索はせっかくなので自分でBMH法を実装してみました。（多分Rustのネイティブ関数のcontainsのほうが大分速い）

今後やりたいこと

• 真面目にパフォーマンスチューニング
• brewへの公開の自動化
• std::process::Outputのモックがよくわからなくてやってない統合テスト
• 単にgit stash show@{n}を全部行うだけのoption

感想

やっぱりバイナリにして色々配布できるのは便利。あとIDEでRustの開発するのは楽しい。

クリーンアーキテクチャ19章の問に答える

設計とかRailsの記事このブログなんもないことに気づいた。
最近クリーンアーキテクチャを社内で読書会を主催して読み進めてます。

Clean Architecture　達人に学ぶソフトウェアの構造と設計 (アスキードワンゴ)

一人だと挫折したり難しい表現があったりするので色んな人と読書会できて助かっています。
この本の19章の最後の問がソフトウエアアーキテクチャの原則をまとめるのに良い機会だったのでまとめてみますた。

問

クリーンアーキテクチャの19章では以下のようなアーキテクチャが示されます。暗号化プログラム作成が目的です。
19章の最後の「原則がどこで使われているのか、どうして使われているのかを確認してほしい」という問が記事の主題です。

返答

SRP（単一責任）、CCP（閉鎖性共通の原則)

変更理由が違うものを別のコンポーネントやモジュールにわける。入力クラスのConsoleReaderの変更理由とロジックの核であるEncryptの変更理由は明確にことなる。なので別モジュールになっているのである。

OCP(オープンアンドクローズドの原則）

依存が一方向で統一されているためConsoleReaderの変更はEncryptにはなんの影響もなく変更が容易

DIP(依存関係逆転）

変化しやすいConsoleReaderを参照したり継承はしない。変更されやすいものに依存してしまうとインターフェイスを安定したものにできない。

SDP(安定依存の原則)

安定度が高いEncryptに依存していること。安定度が低いものに依存すると安定度が低いモジュールやコンポーネントが変更しにくくなってしまう。

SAP(安定度・抽象度等価）

Encryptは抽象的であるべき、なぜなら複数のモジュールから依存されていて安定度が高いから。逆にConsoleReaderは具象であるべき。依存されていないので抽象的にするのが無駄だから。

まとめ

共通言語と理由を客観的に説明できるか？が設計における壁だと思うのでやっていきである。

RubyでPriority Queue

精進でこの問題を解いてたらPriority Queueがでてきました。

atcoder.jp

"Ruby Priority Queue"でググれば実装はたくさんでてくるのですが、実際自分で組んだ方が身につくと思い実装してみました。

github.com

MaxHeapかMinHeapかを外部から注入するのについsendを使いがち。 だいたいこんなふうに動きます。

RSpec.describe 'PriorityQueue' do
  context 'direction is max' do
    it 'enqueue element' do
      pq = PriorityQueue.new(:max, [])

      pq.enqueue(3)
      pq.enqueue(9)
      pq.enqueue(6)
      pq.enqueue(1)

      expect(pq.heap.nodes).to eq([9, 3, 6, 1])
    end

    it 'dequeue element' do
      pq = PriorityQueue.new(:max, [9, 3, 6, 1])

      expect(pq.dequeue).to eq(9)
      expect(pq.heap.nodes).to eq([6, 3, 1])
    end
  end

  context 'direction is min' do
    it 'enqueue element' do
      pq = PriorityQueue.new(:min, [])

      pq.enqueue(3)
      pq.enqueue(9)
      pq.enqueue(6)
      pq.enqueue(1)

      expect(pq.heap.nodes).to eq([1, 3, 6, 9])
    end

    it 'dequeue element' do
      pq = PriorityQueue.new(:min, [1, 3, 6, 9])

      expect(pq.dequeue).to eq(1)
      expect(pq.heap.nodes).to eq([3, 9, 6])
    end
  end
end

Priority Queueというかヒープの特徴は

• 最小値、最大値を探す時に全探査だとO(n)のところがO(1)で取れる
• 追加、再構築はヒープの高さ（この場合二分ヒープ）がlog 2 nなので計算時間はO(log n)
• 全探査でいちいち最大値、最小値を探すよりもO(n) - O( 1 + 2 (log n))分早い？
• 何度も数字をいじってそのたびに最小値、最大値を求めるときに便利。

書いててわかってるか不安になってきた。

Atcoderで茶色になりました

ratedやった～～～
33回目にしてついに茶色！ pic.twitter.com/MgVolhexeU

— とるめん (@qwyngg) May 2, 2020

というわけでなんとかやりました。 数学の素養が全く無い人間でも数こなせばなんとかなるものですね。

茶色に必要なこと

有名な記事で茶色についての記述にこのようなものがあります。

レッドコーダーが教える、競プロ・AtCoder上達のガイドライン【初級編：競プロを始めよう】 - Qiita

• AtCoder Beginner Contest の A, B 問題が確実に（大方 15 分以内で）解ける
• AtCoder Beginner Contest の C 問題も簡単なものなら解ける

ですが、参加者がかなり増えてる現在、茶色になるには

• AtCoder Beginner Contest の A, B, C問題が確実に（大方 30 分以内で）解ける

ぐらいに茶色の難易度が上がっていると思います。この上でDが安定し解けると緑が見えてくると思います。

茶色になる上で役に立ったこと

僕は典型的な私立文系でこの前まで分数の割り算すら怪しいレベルでした。おそらく数学の素養みたいなものがなに一つなく、組み合わせや確率等アルゴリズム以前の基礎の概念からしてあやふやでした。 そんな僕に一番役に立った本は結城浩先生の「プログラマの数学」です。

プログラマの数学第2版

この本は本当に良書です。数学の基礎がない自分でも読み進められるくらい解説が易しいですし、組み合わせ、順列、確率、再帰等競プロの常識ともいえる概念がコンパクトにまとまっていました。 この本を読んだ後はABCの茶色diffの問題を毎日少しづつ解いていきました。

精進継続中！

やっぱり精進をはじめてからグンと（当社比）レートが伸びたのでやっぱり精進が一番の近道ですね。

茶色になって思うこと

正直茶色になるのにアルゴリズムの知識はいらないと思います。Cまでは基本的に全探査で解けます。Dではじめて蟻本や螺旋本にでてくるアルゴリズムを使うと思います。
僕みたいに数学の素養が全くない人間が最初に蟻本や螺旋本に手をだすと勉強したことが自分の毎週解くべき課題にあんまり役に立たないという事態になりやすいです。
逆にいうとこれでやっとアルゴリズムというものを学ぶ準備ができたのだと思います。緑diffの問題で精進やっていくぞ。

追記

RubyでAtcoderのテスト自動生成するライブラリを自作しているので、Ruby使ってる方ぜひ試してみてください。 僕はこれでうっかりWAはだいぶ減りました。

qiita.com

OSSコードリーディング Batch-loader

Batch-loaderというRubyでバッチローディングをするGemを読んで、そのきれいな実装に感心したのでまとめた。

github.com

実装自体はシンプルだけど、特定のGemに依存しているわけではないので使い方に融通が効くし、困った時にトラブルシューティングしやすい。
この記事は社内で一度発表したものだけど、上司に確認したらブログに載せても問題ないとのことだったので載せる。

README、Gem作成者のスライドの２つを読むのが一番という説がある。

Batch-loaderがやりたいこと

そもそもこのGem何がしたいの？という人はこの記事を読むといい。
Rails: N+1クエリを「バッチング」で解決するBatchLoader gem（翻訳）
DBやHTTPリクエストのN + 1問題をbatch load(一塊りでロードする）で解消するというもの。リクエストされた引数をまとめておき、値とマッピングだけコレクションしておき、実際の値の取得は最後に解決しようとする。

def load_user(post)
  BatchLoader.for(post.user_id).batch do |user_ids, loader|
    User.where(id: user_ids).each { |user| loader.call(user.id, user) }
  end
end

posts = Post.where(id: [1, 2, 3]) #  SELECT * FROM posts WHERE id IN (1, 2, 3)

users = posts.map do |post|
  load_user(post)
end

puts users # SELECT * FROM users WHERE id IN (1, 2, 3)

load_userの中身がBatch-loaderの基本的な使い方。

この記事では大きく分けて

• 実際に複数回呼び出されるpost.user_idをどうやってbatch(一群)にしているのか
• batchしたもの(今回の例だとuser_id)をどうやって本当のオブジェクトにしているのか

の２つに分けて書いていく。

図でまとめたやつ

最初に図でザックリまとめたやつをのっけておく。

def load_user(post)
  BatchLoader.for(post.user_id).batch do |user_ids, loader|
    User.where(id: user_ids).each { |user| loader.call(user.id, user) }
  end
end

実際に複数回呼び出されるpost.user_idをどうやってbatch(一群)にしているのか

最初に例に上げたload_userメソッド内では

BatchLoader.for(post.user_id).batch(&block)

という形の処理を書いていた。 forはnewのエイリアス。BatchLoaderのインスタンスは引数を@itemとして持つ。 batchの中身は以下。

  def batch(default_value: nil, cache: true, replace_methods: nil, key: nil, &batch_block)
    @default_value = default_value
    @cache = cache
    @replace_methods = replace_methods.nil? ? cache : replace_methods
    @key = key
    @batch_block = batch_block

    __executor_proxy.add(item: @item)

    __singleton_class.class_eval { undef_method(:batch) }

    self
  end

@key = key以上の行はオプション処理。渡したブロックは@batch_block変数に入る。

ここでは大きく分けて２つ処理がある

• __executor_proxy.add(item: @item)
• __singleton_class.class_eval { undef_method(:batch) }

__executor_proxy.add(item: @item)

__executor_proxyの中身はBatchLoader::Executorというクラスのプロキシオブジェクト。

  def __executor_proxy
    @__executor_proxy ||= begin
      raise NoBatchError.new("Please provide a batch block first") unless @batch_block
      BatchLoader::ExecutorProxy.new(@default_value, @key, &@batch_block)
    end
  end

class BatchLoader
  class ExecutorProxy
    def initialize(default_value, key, &block)
      @default_value = default_value
      @block = block
      @block_hash_key = [block.source_location, key]
      @global_executor = BatchLoader::Executor.ensure_current
    end

実際のBatchLoader::Executorの中身。

class BatchLoader
  class Executor
    NAMESPACE = :batch_loader

    def self.ensure_current
      Thread.current[NAMESPACE] ||= new
    end

    attr_reader :items_by_block, :loaded_values_by_block

    def initialize
      @items_by_block = Hash.new { |hash, key| hash[key] = Set.new }
      @loaded_values_by_block = Hash.new { |hash, key| hash[key] = {} }
    end
  end
end

要はスレッドごとに@items_by_blockと@loaded_values_by_blockという２つハッシュを持つのがExecutor。 ExecutorProxyの役割はインスタンスごとに@blockを保持し自身を通してブロックごとにBatchLoaderからアクセスするExecutorのハッシュを特定すること。

   # in ExecutorProxy
    def items_to_load
      global_executor.items_by_block[@block_hash_key]
    end

    def loaded
      global_executor.loaded_values_by_block[@block_hash_key]
    end

最終的にBatchLoaderのインスタンスが複数作られ、それらは全て同じExecutorの@items_by_blockに対してBatchLoader#batchに渡されたブロックそのものをkeyとしてpost.user_idをためていく。 @loaded_values_by_blockは実際の値とuser.idを紐づけたものが入っていくことになる。

__executor_proxy.add(item: @item)についてまとめると

__executor_proxy.add(item: post.user_id)
 # ↓
 BatchLoader::ExecutorProxy.new(&@batch_block).items_by_block["#{`batch_blockのソースライン情報`}"] << post.user_id
 # items_by_block[@block_hash_key]はデフォルトで空のSetのインスタンスが入っている。

BatchLoader.for(post.user_id).batch(&block)は何度実行しても&blockのソースロケーションが同じであれば同一の items_by_block[batch_blockのソースライン情報]というSetにpost.user_id`をつめこんでいくことになる。

__singleton_class.class_eval { undef_method(:batch) }

最後の__singleton_class.class_eval { undef_method(:batch) }について。 BatchLoaderのインスタンスの特異クラスからbatchメソッドを消している。 これは同じインスタンスに対してbatchの次の二回目メソッドの呼び出しはbatch自身も含めて全てmethod_missingに飛ばしたいという意図があると思われる。

そしてこれがBatchLoaderクラスのmethod_missing。

  def method_missing(method_name, *args, &block)
    __sync!.public_send(method_name, *args, &block)
  end

実際にmethod_missingが走る時（本当にUserのインスタンスそのものが必要になった時) については次章で解説する。

ここまででexecutor.items_by_block[#{BatchLoader#batchに渡したブロック}"]にpost.user_idが複数積み込まれたことになる。

batchしたものをどうやって本当のオブジェクトにしているのか

ここから実際にオブジェクトをロードする過程に入る。

実際にlazyなオブジェクトが使用される時、ということはなにかしらメソッドが呼び出される時であり、その時にBatchLoaderのインスタンスでは method_missingが呼び出される。

  def method_missing(method_name, *args, &block)
    __sync!.public_send(method_name, *args, &block)
  end

__sync!は概ね__syncのラッパー。 BatchLoaderクラス内では多くのメソッドが__というprefixが付いているが、実際のオブジェクトのメソッドと極力かぶらないためだろう。

  def __sync!
    loaded_value = __sync

    if @replace_methods
      __replace_with!(loaded_value)
    else
      loaded_value
    end
  end

  def __sync
    return @loaded_value if @synced

    __ensure_batched
    @loaded_value = __executor_proxy.loaded_value(item: @item)

    if @cache
      @synced = true
    else
      __purge_cache
    end

    @loaded_value
  end

__ensure_batchedをみると

  def __ensure_batched
    return if __executor_proxy.value_loaded?(item: @item)

    items = __executor_proxy.list_items
    loader = __loader
    args = {default_value: @default_value, cache: @cache, replace_methods: @replace_methods, key: @key}
    @batch_block.call(items, loader, args)
    items.each do |item|
      next if __executor_proxy.value_loaded?(item: item)
      loader.call(item, @default_value)
    en
    __executor_proxy.delete(items: items)
  end

最初にloaderを作っている。

  def __loader
    mutex = Mutex.new
    -> (item, value = (no_value = true; nil), &block) do
      if no_value && !block
        raise ArgumentError, "Please pass a value or a block"
      elsif block && !no_value
        raise ArgumentError, "Please pass a value or a block, not both"
      end

      mutex.synchronize do
        next_value = block ? block.call(__executor_proxy.loaded_value(item: item)) : value]
        __executor_proxy.load(item: item, value: next_value)
      end
    end
  end

lamdaオブジェクト。「(item, value xor block)を引数にとって実際にvalueをloadするlamda」がloaderである。

__ensure_batchedでは次に@batch_block.call(items, loader, args)が実行される。 最初のload_userで書いたbatchに渡しているブロックが@batch_block。loaderには先程のlamdaオブジェクトが渡される。

def load_user(post)
  BatchLoader.for(post.user_id).batch do |user_ids, loader|
    User.where(id: user_ids).each { |user| loader.call(user.id, user) }
  end
end

loaderというlamdaに渡しているのはuser.idと実際のvalueであるuser。 この２つの引数がExecutorProxyを通してExecutorの@loaded_values_by_block[batch_blockのソースライン情報]というハッシュに { user.id: user }　という形で追加されていくことになる。
ここで__syncに戻ると
@loaded_value = __executor_proxy.loaded_value(item: @item)
これはBatchLoaderのインスタンスがもつそれぞれの@item( = post.user_id) を使ってExecuterの@loaded_values_by_block[batch_blockのソースライン情報][@item]としてハッシュから値をとりだしている処理。
post.user_idと先程loadした{ user.id: user }のuser.idは等しいはずなのでここで無事にBatchLoaderのインスタンスごとに正しいuserを引っ張ってくることができる。
以降は別のBatchLoaderインスタンスでは@loaded_values_by_block[batch_blockのソースライン情報]というハッシュが中身付きでメモリに存在するため、再度User.where(id: user_ids).each { |user| loader.call(user.id, user) }という行為をする必要がなくなる。これにてBatch-Loading完了となる。

Gatsby.jsとTypeScriptでミニブログを作った

Scalaをそこそこやって型いいじゃん！とすこしづつ思いはじめてきたのでTypeScriptとReactで遊ぶがてらGatsby.jsでブログを書いてみた。

tallmanlog.netlify.app

なんのOGPもなくて寂しい。 ソースコードはこれ github.com

TypeScript

とりあえずTypeScript deep diveでundefind使えと書いてあったのでundefind使ったりよちよち歩きでやっている。とはいえよちよちでもIDEはしっかりと補完してくれるしESLintはしっかり指摘してくれるので型の恩恵にはあずかれてる気がする。

React

公式のチュートリアルをみながら色々やったのだけど、Hookというのが直感的だし記述量も少ないしで楽しかった。コンポーネントディドマウントとかよりだいぶわかりやすくなった気がする。
今回のブログだとトップページのLOLのランクステータスをfetchしてるところでHookを使っている。 このブログのコードを社のフロントの人にみせたらfetchしてる間もなにか表示した方がいいという金言をもらったので is Loading..をfetch中に表示するようにした。
バックエンドだと非同期ジョブとかDBのロックとかいかにも非同期非同期してるところしか非同期処理を意識しないので、フロントでhttpレスポンスが返ってくるのを待っている間とかの処理を考えるのは脳に新鮮な刺激で楽しい。

クライアントにとってのGraphQL

Gatsbyは静的データをGraphQLで扱うことができる。 とってくるクエリごとに名前をつけて型を作れるため、サンプルレスポンスといちいちにらめっこしたりする必要がないのが体験がいい。 nullableはできるだけ避けたいとか、空文字はjs界だとfalseだったりとかも面白かった。 業務では逆に僕がGraphQLサーバーを書く側なのだけれど、Gatsby.jsの経験を通してよりよいスキーマを定義できればいいな。

ブログの内容の予定

本当にチラ裏みたいなことを書いていくと思う。まだまだブログとしても寂しいしソースコードも記事もちょこちょこいじっていくぞ。

ScalaとRubyで関数合成してみる

N予備校でScala応用編を受講したのでRubyと比較して色々やってみたくなった。

まえおき

ScalaはRubyと似てる気がする

これは思想が似てる(オブジェクト思考と関数型の融合）だからなのかもしれないけどscalaとrubyって似てる気がするんだよな
DSLかけたりとかシンプルな構文だったりとか

— とるめん (@qwyngg) March 30, 2020

Rubyは関数（というか処理をまとめたProcかMethodのインスタンス）も他のオブジェクトと同等だし、Scalaも同様で関数の返り値や引数を関数にしたりできる。

関数合成してみる

例えば文字列 "true"と”false"をパースする関数を書くためにtruePaser、falsePaserそれぞれを定義して関数合成したいとする。 Rubyなら

class ParseResult
  attr_accessor :value
end

class Success < ParseResult
  def initialize(value)
    @value = value
  end
end

class Failure < ParseResult
  def initialize; end
end


def true_parser(input)
  if input == "true"
    Success.new(true)
  else
    Failure.new
  end
end

def false_parser(input)
  if input == "false"
    Success.new(false)
  else
    Failure.new
  end
end

def select(left, right)
  Proc.new do |input|
    if (success = left.call(input)).class == Success
      success
    else
      right.call(input)
    end
  end
end

true_parser_method = method(:true_parser)
false_parser_method = method(:false_parser)

puts select(true_parser_method, false_parser_method).call('true').value　        # true
puts select(true_parser_method, false_parser_method).call('false').value          # false
puts select(true_parser_method, false_parser_method).call('hogehoge').value # （何も出力されない）

合成は問題なくできるが結局selectが何をするProcを返すのかわかりにくい。

ここで型があるScalaだと

object Main extends App {
  sealed trait ParseResult[+T] {
    def value :Option[T]
  }

  case class Success[+T](in_value: T) extends ParseResult[T] {
    def value: Option[T] = Option(in_value)
  }

  case object Failure extends ParseResult[Nothing] {
    def value: Option[Nothing] = None
  }

  type Parser[+T] = String => ParseResult[T]

  def trueParser: Parser[Boolean] = input =>
    if (input == "true") {
      Success(true)
    } else {
      Failure
    }

  def falseParser: Parser[Boolean] = input =>
    if (input == "false") {
      Success(false)
    } else {
      Failure
    }

  def select[T, U >: T](left: => Parser[T], right: => Parser[U]): Parser[U] = input => {
    left(input) match {
      case success@Success(_) => success
      case Failure => right(input)
    }
  }

  println(select(trueParser, falseParser)("true").value) // Success(true)
  println(select(trueParser, falseParser)("false").value) // Success(false)
  println(select(trueParser, falseParser)("hogehoge").value) // None
}

型があると、関数合成をする関数を定義する時点で引数に取りたい関数のパラメーターを表現でき、合成関数の返り値に何を引数として渡したら良いかわかりやすい。 後Rust同様Option型が便利。
対して、Rubyは型がないことで明らかに記述量へるし多分僕の書いた以上に研ぎ澄ますこともできると思う。あとobject Main extends Appみたいなのがいらない。

まとめ

関数型言語として関数の集まりを書いていくなら型があったほうが扱いやすいのでは？という気持ち。Lisｐは型ないけど。 入出力に対してルールがある程度形式張って表現されていたほうが関数を組み合わせやすい気がする。