たにしきんぐダム

プログラミングやったりゲームしてます

WartRemover で Scala を静的解析

この記事は CAMPHOR- Advent Calendar 2016 7日目の記事です。

WartRemoverScala のASTレベルの静的解析ツールで、WartRemover に組み込まれているパターンに加えて、自分で定義したパターンをビルド時に検出することができます。
これを使えばscalacはエラーや警告を出さないけど検出してほしいコーディング規約などをビルド時に検出することができるようになって便利。

github.com

もとから組み込まれてるパターンはGitHubのREADMEに詳しく書かれています。

使ってみる

詳しくは GitHubREADME を参照。

project/plugins.sbt に以下を追記

addSbtPlugin("org.wartremover" % "sbt-wartremover" % wartremoverVersion)

build.sbt に以下を追記

wartremoverErrors ++= Warts.all

これだけでビルド時にビルド対象のscalaプログラムを見て、すべてのパターンにマッチするASTを探索し、マッチしたパターンをエラーとして出力してくれるようになります、簡単ですね。

上の例だとすべてのプログラムに対して、すべてのパターンを検出しますが

  • 特定ファイルは検出対象から外す
  • 一部のパターンのみ/一部のパターンを除いてすべてのパターンを検出
  • あるパターンはエラー、あるパターンは警告を出すようにする

などのことが build.sbt に記述するだけでシュッとできるようになります。
詳しい設定方法はREADMEを(ry

カスタム Wart を作ってみる

ここ を見ると wart rule を自分で追加できるようです。

今回は HOGE_HOGE みたいな全部大文字とアンスコのみの変数名を見つけてみます。
Scala の定数は 公式のscala code styleUpperCamel だよって言われているのですが、僕はよくミスって LIMIT みたいな定数名を作ってしまうし、scalac も scalastyle も warning を出さないからです。(もしかして僕の設定が足りてないだけ?)(まあそこは本題じゃないし)

完成したものはこちら

github.com

WartRemoverはscalaのASTとのマッチングによって検出を行うので、まずは val HOGE = 1 みたいなプログラムがどういう AST になるのか確認しましょう。

scala> import scala.reflect.runtime.universe
import scala.reflect.runtime.universe

scala> universe.showRaw(universe.reify { val HOGE = 1 }.tree)
res1: String = Block(
List(ValDef(Modifiers(), TermName("HOGE"), TypeTree(), Literal(Constant(1)))),
Literal(Constant(())))

なんとなく ValDef(Modifiers(), TermName(), TypeTree(), Litenarl()) にマッチさせてやれば良いことがわかりますね。
(Modifiers には final private みたいな修飾子 が入ります。TypeTree はよく分からない...)

ちなみにScalaのリフレクションを使った構文木へのアクセスは公式ドキュメントが詳しい

概要

よっしゃ、それでは ValDef(Modifiers(), TermName(), TypeTree(), Litenarl()) のうち TermName が全部大文字かアンスコだけな構文木にマッチしてくれるwartを書いていきましょう!
ディレクトリ構成はこんな感じ、LargeValueName.scala は wartルールを記述するプログラム、wartsは別プロジェクトとして管理しています。

.
├── build.sbt
├── project
│   ├── build.properties
│   └── plugins.sbt
├── src/main/scala/Main.scala
└── warts
    └── src/main/scala/LargeValueName.scala

LargeValueName.scala

自分で wart を作るときはだいたい以下のような必要があります。

  • wart object は WartTraverser を継承
  • def apply(u: WartUniverse): u.Traverser のみをメソッドとして持ち
    • WartUniversereflect.api.Universe を内部にもつ
  • apply が返す Traversertraverse(tree: Tree): Unit を override
    • 引数として与えられたASTと、検出したいパターンとのマッチングさせる
package warts

import org.wartremover.{WartTraverser, WartUniverse}

object LargeValueName extends WartTraverser {
  def apply(u: WartUniverse): u.Traverser = {
    import u.universe._

    new Traverser {
      override def traverse(tree: Tree) {
        tree match {
          case t @ ValDef(_, TermName(s), _, _)
            if s.trim.matches("[A-Z_]+") =>
            u.error(tree.pos, s"Value name $s should be upper/lower camel case")
            // 他のwartもチェックするかもしれないので super.traverse を呼ぶ
            super.traverse(tree)
          case _ =>
            super.traverse(tree)
        }
      }
    }
  }
}

build.sbt

それじゃあこれを build.sbt に登録してみます、今回は LargeValueName.scala は sbt のマルチプロジェクトを使ってメインプロジェクトとは別で管理します。

  • wartremoverClasspaths にカスタム wart の classpath を追加
  • wartremoverWarnings += Wart.custom("your.own.wart")

build.sbt はこんな感じ、

val wartremoverVersion = "1.2.1"
val customWartProjectName = "MyWarts"

lazy val commonSettings = Seq(
  scalaVersion := "2.11.8"
)

lazy val root = (project in file(".")).
  settings(commonSettings: _*).
  dependsOn(warts).
  settings(
    name := "wartremoverPlayground",
    version := "1.0",
    // warts project の jar ファイルが欲しい
    // wartremoverClasspaths += 
    //   "file://" + baseDirectory.value + "/warts/target/scala-2.11/mywarts_2.11-1.0.jar",
    wartremoverClasspaths ++= {
       // lazy val warts = ... settings( exportJars := true) と
       // dependsOn(warts) により dependencyClasspath in Compile に上記のjarが追加されてるはず
      (dependencyClasspath in Compile).value.files
        .find(_.name.contains(customWartProjectName.toLowerCase()))
        .map(_.toURI.toString)
        .toList
    },
    wartremoverWarnings += Wart.custom("warts.LargeValueName")
  )

lazy val warts = (project in file("warts")).
  settings(commonSettings: _*).
  settings(
    name := customWartProjectName,
    version := "1.0",
    exportJars := true,
    libraryDependencies ++= Seq(
      "org.wartremover" %% "wartremover" % wartremoverVersion
    )
  )

warts project に移動して jar ファイルをいちいち生成して、頑張ってjarへのpathを渡しても動くのですが大変、自動化したすぎます。

wartremoverClasspaths += "file://" + baseDirectory.value + "/warts/target/scala-2.11/mywarts_2.11-1.0.jar"

この部分で、wartsプロジェクトの生成したjarファイルを見つけています。

wartremoverClasspaths ++= {
  (dependencyClasspath in Compile).value.files
     .find(_.name.contains(customWartProjectName.toLowerCase()))
     .map(_.toURI.toString)
     .toList
}

動かしてみる

Main.scala

package playground

object Main {
  val LIMIT = 1
}

これで sbt compile すると

[warn] /path/to/Main.scala:4: Value name LIMIT should be upper/lower camel case
[warn]   val LIMIT = 1

おお、警告出してくれた!
これを使って、簡単にパターンとして記述できるコーディング規約などは静的解析で検出してくれると良いですね!

明日は id:ryota-ka の「 Vim script でジェネレータを作ったり、遅延評価してみる」です。

参考

Scala関西勉強会でscala.Eitherとscalaz.\/の違いを話してきた

Scala関西勉強会で scala.Eitherscalaz.\/ の違いについて話してきました!
connpass.com

この話題、ブログとか漁ってみると3年前あたりに活発に議論されてる話だった...
僕自身for式の中でパターンマッチさせようとしてハマったものの(僕の検索能力の低さもあるけど)それを解説している記事にぶつかるまで時間がかかってしまったので、これについて解説する記事が一つでも増えると良いなーと思って発表しました。

考え事

\/単位元も定義されてる\/-(Monoid[B].zero)

https://github.com/scalaz/scalaz/blob/series/7.3.x/core/src/main/scala/scalaz/Either.scala#L411-L418

-\/(Monoid[A].zero)じゃないのかーって思ったけど、+++の実装を見てみると確かに\/-(Monoid[B].zero)\/appendについての単位元になってるなぁ@@

https://github.com/scalaz/scalaz/blob/series/7.3.x/core/src/main/scala/scalaz/Either.scala#L230-L238


今回の勉強会、バリュエーション豊かで基礎から応用まで幅広い内容のセッションがあってすごく良かった!
会場提供のエムオーテックス株式会社様、主催の@aa7thさん、@ryu1_okdさん、ありがとうございました!

参考

余談

発表中両手あげてバンザイして全身で\/を表現したりしてた

また参加します!

空間インデックス(R-tree)入門

R-treeとは空間データを効率良く検索するためのインデックス構造。R-tree について調べたのまとめておく。

目次

  • 目次
  • 参考資料
  • ナイーブな例
  • R-tree の概要
  • 参照処理
    • 点検索
    • 範囲検索
  • データの挿入・削除
    • 挿入処理
    • ノードの分割
      • Exhaustive Algorithm
      • Quadratic-Cost Algorithm
      • Linear-Cost Algorithm
    • 削除
    • 更新処理
  • まとめ

参考資料

続きを読む

Scala でジェネレータを作ったり、遅延評価してみる

メリークリスマス!!!!!!
この記事は CAMPHOR- Advent Calendar 2015 の25日目の記事です.

Scala はまだ始めたばかりですがとりあえずジェネレータ作ったり遅延評価してみようと思います.

これまでの流れ

ジェネレータ

とりあえず1から順番に無限に数字を生成するジェネレータを作ってみます.
Scalaではクロージャを使うことで割と簡単に実現することができます.

クロージャは評価可能な局所変数と評価する関数をまとめたもので、以上の例のように状態を保持する、関数を返す関数のようなものを定義することができます.

上の例の無名関数は実行されるたびに局所変数numの値を増やしてからnum:Intを返します.

遅延評価

クロージャを使ったジェネレータでも遅延評価が実現できていることが分かると思いますが、Stream を使うことによって遅延評価を簡単に実現することもできます.

まずは Stream の簡単な例を見てみましょう. Stream は List によく似ています.

Stream(1, ?) とはどういうことでしょうか?
Stream は先ほど述べたように List に似ているのですが、List の tail には残りの List へのポインタが入っているのに対して
Stream の tail には lazy val (? の正体) が入っています. lazy val はもちろん実際に計算に値が必要になるまで評価されることはないため、Streamの要素は遅延評価され無限の長さを持つことができます.

以下の例はStreamを使って同様のことを実現したものです.

range は Stream型を返すので以上のように再帰的に定義することができます.

フィボナッチ数列を無限に返すストリーム

それでは Stream を使って無限にフィボナッチ数を返すストリームを作ってみましょう.
コードは以下のような感じになります.

何故これが無限にフィボナッチ数を返すストリームになるかを解説していきます.

以下のような表を見てみると分かりやすいかもしれません.
これはfibGenfibGen.tail などの Stream を正格コレクションに直した場合の数字列です.

1 2 3 4 5 #
1 1 2 3 5 fibGen.tail
0 1 1 2 3 fibGen
(0,1) (1,1) (1,2) (2,3) (3,5) fibGen.zip(fibGen.tail)
1 2 3 5 8 fibGen.zip(fibGen.tail).map(n => n._1 + n._2)

このようにfibGenをひとつシフトしてその和を足せば 残りのストリームを定義することができます.

追記

View

scala にはコレクションを仮想的に遅延評価するためにビューという機能があります.
Stream以外のコレクションはすべて正格評価されるのですが、任意のコレクションをビューという遅延評価される仮想的なコレクションに変換し、forceメソッドで正格評価されるコレクションに戻すことができます. 例えば以下のような感じです

Stream と違って無限リストを生成することは出来ませんが、異常に巨大なコレクションの一部のみを取得したい場合などは気軽に遅延評価をすることができて便利だと思います. 詳しくは Collections - ビュー - Scala Documentation を参照お願いします


CAMPHOR- Advent Calendar は延長します!!!
明日は@ryota-kaです. お楽しみに!

参考

pixivインターンに参加して中学生から使ってるpixivのコード見た

12/12(土), 12/13(日) の二日間で pixiv株式会社の短期インターンに参加してきました.

ssl.pixiv.net

pixivはほぼROM専ながらも中学生の頃からよく使っているサイトで(ちなみに今は大学3回生) その中身を触らせてもらっただけでなく、まだ新鮮なバグにも取り組まさせてもらえて最高だった!

f:id:tanishiking24:20151215165007j:plain:w300

はしゃいでいる様子

エントリー

2日間だけだし、面接もなく事前課題に対して出したプルリクの内容で決めるということらしかったのでかなり気軽にエントリーしたのを覚えてる.

事前課題

事前課題として与えられたのは脆弱性が含まれているという小さなウェブアプリケーション. その中から脆弱性を発見してそれを改善するプルリクを出すことで事前課題提出ということになった.(先進的っぽい!)

直せたのは一つだけだったけれど、ほかにもたくさん脆弱性はあったっぽいし もっと頑張りたかった...!

インターン開始

インターンが始まってみると まさかのpixiv本体のインターン1日前のスナップショットと その時点で本体に残ってたissue(社員もまだ手をつけてない?)から適当にメンター陣が選んだissue(15個くらい)をインターン生たちでつぶすという感じでした. 現場感あってすごい.

インターン生の開発環境として開発サーバーが与えられます. 開発環境のセットアップはほとんど自動化されてたりREADMEに詳しく書かれていたりしたのでサクサクっとストレスなく開発環境を整えることができて体験が良かった.

開発中

Github上でも現実でもメンターさんが手厚くフォローしてくれます.

f:id:tanishiking24:20151215163745j:plain 様子です

バグを直すのにpixivの重厚なコードに目を通す必要があったのですが、10年前からあるサービスなのにきちんと設計されていたので全然読みやすかった.

オフィス

すごい楽しげだった.

色使い凄いし集中できるのかなぁと思ってたけど 開発中は画面しか見てないから気にならないし、ふと周りを見回したら自分の好きな物(フィギュアとかイラストとか)が視界に入って幸せでした. 椅子も座り心地最高だった

f:id:tanishiking24:20151215171414j:plain:w400

絵馬凄い

総評

最終的には2日間で6つくらいのissueに対してプルリクを投げてOKをもらった(割と簡単めなissueにばかり手を出していたけど)

早めに作られたプルリクで良さそうなコードが本体に取り込まれるという感じで、結局僕の提出したプルリクでとりこまれることになったのは 1つで社内フレームワークに対するバグフィックスでした. 社会貢献できてよかった.

感想

楽しかったし勉強になった!

やはり自分はセキュリティまわりの知識が乏しいなぁという印象も受けたのでこれから勉強すべきことも分かった.(とりあえず徳丸本読みます)

pixivのエンジニアさんのレベルは非常に高く、会社の雰囲気も凄く楽しげで、こういう会社で働くのはとても楽しいだろうなぁ

懇切丁寧に指導してくれたメンターさんも二日間ながらも一緒にした皆もありがとうございました!