構文木を簡易なツリー形式で表示してみた

Scala歴1年ちょっとにして初歩的なミスをしました。

これで嵌ってたので自分もまだ初心者だなって思った pic.twitter.com/2qLysoFm4K

— harry@求職中 (@harry0000jp) 2017年3月9日

このコードはどう動く？

例えば以下のコードはどのような実行結果になるでしょうか？

object Main extends App {
  def getValue(condition: => Boolean) = {
    if (!condition) {
      None
    } else {
      Some(1)
    } match {
      case Some(v) => v
      case _       => -1
    }
  }

  println( getValue(true) )
  println( getValue(false) )
}

if-else式に1つだけ条件が指定されていて、その後にmatch式が続いています。 match式はSome(v: Int)であればvを返し、Noneの場合は-1を返しています。

正解は？

object Main extends App {
  def getValue(condition: => Boolean): Any = {
    if (!condition) {
      None // false のときは 俺 !?
    } else {
      Some(1)
    } match {
      case Some(v) => v
      case _       => -1 // ちょ、おまっ !
    }
  }

  println( getValue(true) )
  println( getValue(false) )
}

1
None

関数の戻り値はAny型です。

どうしてこうなった？

以下のように式を変形すれば、どのように文が解釈されているか分かりやすいかと思います。 Scalaの{}は式で、値を返します。

def getValue(condition: => Boolean): Any = {
  if (!condition)
    { None }
  else
    { Some(1) } match {
      case Some(v) => v
      case _       => -1
    }
}

• ifの時 Noneが返ります

• elseの時 Some(1)の1が返ります

  • case _ => -1は実行されることがないUnreachable codeです

解決方法

なので、if式を{}式で囲めば意図した通りに？動作します。

def getValue(condition: => Boolean): Int = {
  (if (!condition) {
    None
  } else {
    Some(1)
  }) match {
    case Some(v) => v
    case _       => -1
  }
}

println( getValue(true) )
println( getValue(false) )

1
-1

…本当にそう解釈されてる？

ここまでは実行結果からコードがどのように解釈されているか推測しているだけです*1。 では本当にそのように解釈されているか確認してみます…scala.metaで。

scala.meta

http://scalameta.org/

http://scalameta.org/tutorial/

Scala.meta is a clean-room implementation of a metaprogramming toolkit for Scala

メタプログラミングのためのツールキットで、メタプログラミングに必要な機能が一通りあります。そのため構文(構文木)の解析も可能です。

いますぐREPLで試したい人向けのインストール方法

1.build.sbtを作る

name := "scala-meta-sandbox"

scalaVersion := "2.12.1"

libraryDependencies ++= Seq(
  "org.scalameta" %% "scalameta" % "1.6.0"
)

2.sbt consoleでREPLを起動

D:\scala-meta-sandbox> sbt console

(中略)

[info] Starting scala interpreter...
[info]
Welcome to Scala 2.12.1 (Java HotSpot(TM) 64-Bit Server VM, Java 1.8.0_121).
Type in expressions for evaluation. Or try :help.

scala>

3.import scala.meta._を実行

scala> import scala.meta._
import scala.meta._

scala> q"val x = 42"
res0: meta.Defn.Val = val x = 42

scala>

Tree

構文木は親(0 or 1)と子(0個以上)を持つ木構造のデータ型です。

scala/meta/Trees.scala

@root trait Tree extends InternalTree {
  def parent: Option[Tree]
  def children: Seq[Tree]

  def pos: Position
  def tokens(implicit dialect: Dialect): Tokens
}

• 継承図

http://scalameta.org/tutorial/img/tree.png

※Stat: Statement

Quasiquotes

準クォート(quasiquote)を使うと簡単にTreeが取得できます。q""内にコードを書きます。

scala> q"val x = 42"
res0: meta.Defn.Val = val x = 42

unapplyが定義されている為、パターンマッチもできます。

scala> val q"val $name = $literal" = res0
name: scala.meta.Pat = x
literal: scala.meta.Term = 42

複数行のソースコードで.stripMarginを使いたい

q""では.stripMarginが使えませんので、"".parse[Source].getや"".parse[Stat].getを使いましょう。

scala> """
     | |if (condition)
     | |  Some(1)
     | |else
     | |  None
     | """.stripMargin.parse[Stat].get
res0: scala.meta.Stat =

if (condition)
  Some(1)
else
  None

parseに失敗した…

parseに失敗する可能性がある場合、str.parse[Stat].getではなく、以下のように書くと失敗をキャッチできます。

import scala.meta.parsers.Parsed

str.parse[Stat] match {
  case Parsed.Success(stat) =>
  case Parsed.Error((position, message, exception)) =>
}

失敗する例

• 括弧や引用符の対応関係がおかしい

• 2つ以上のStatementがある文字列をStatでparseしようとした

scala> """
     | val x = 2
     | val y = 3
     | """.parse[Stat].get
scala.meta.parsers.ParseException: <input>:3: error: end of file expected but val found
val y = 3
^

etc.

str.parse[]に指定できる型は？

実はいっぱいありますが、SourceとStatだけ覚えておけばしばらくは困らないと思います。

実はinterpolationにもいくつか種類が

q""だけ覚えておけば困らないと思います。

scala/meta/quasiquotes/Api.scala

構文木を簡易なツリーで表示する

話を元に戻して…

コードの文字列から構文木を取得する方法はわかりました。ただし、このままでは構文木がどのような構造になっているのか一目でわかりません。そこで、構文木を可視化するためのコードを書きました。

import scala.meta._

Graph.prettyPrint(
  q"""
      if (condition) {
        Some(1)
      } else {
        None
      }
    """
)

Term$If
├─Term$Name (condition)
├─Term$Block
│　└─Term$Apply
│　　　├─Term$Name (Some)
│　　　└─Lit (1)
└─Term$Block
　　└─Term$Name (None)

sealed trait Graph {
  def prefix: String
  def value: String
  def parent: Option[Graph]

  def padding: String = {
    @annotation.tailrec
    def add(acc: List[Char])(parent: Option[Graph]): Seq[Char] = parent match {
      case Some(p: Branch) => add('│' :: '　' :: acc)(p.parent)
      case Some(p: Leaf)   => add('　' :: '　' :: acc)(p.parent)
      case _ => acc
    }

    add(Nil)(parent).mkString
  }

  override def toString: String = padding + prefix + value
}
object Graph {
  import scala.util.matching.Regex
  import scala.meta._

  type Parent = Option[Graph]
  private[this] val regex: Regex = """^class scala\.meta\.(.+)\$.+Impl""".r

  private def simpleName(tree: Tree): String = {
    regex.findFirstMatchIn(tree.getClass.toString)
      .map { m =>
        val name = m.group(1)
        if (name == s"Type$$Name" ||
            name == s"Term$$Name" ||
            name == "Lit")
          s"$name ($tree)"
        else
          name
      }
      .getOrElse("")
  }

  def apply(root: Tree): Seq[Graph] = {
    import collection.mutable

    def append(buf: mutable.Buffer[Graph])(root: Tree): Unit = {
      val stack = mutable.Stack[(Parent, (Parent, String) => Graph, Tree)]()
      stack.push((None, (_, n) => Root(n), root))

      while (stack.nonEmpty) {
        val (parent, apply, tree) = stack.pop()
        val node = apply(parent, simpleName(tree))
        buf += node
        tree.children.reverse match {
          case h :: t =>
            stack.push((Some(node), Leaf, h))
            stack.pushAll(t.map((Some(node), Branch, _)))
          case _ =>
        }
      }
    }

    val buf = mutable.ListBuffer.empty[Graph]
    append(buf)(root)
    buf
  }

  def prettyPrint(root: Tree): Unit = Graph(root).foreach(println)
}

case class Root(value: String) extends Graph {
  val prefix: String = ""
  val parent: Option[Graph] = None
}
case class Branch(parent: Option[Graph], value: String) extends Graph {
  val prefix: String = "├─"
}
case class Leaf(parent: Option[Graph], value: String) extends Graph {
  val prefix: String = "└─"
}

元のコードの構文木

Statementが1つのif式となっており、ifの条件に一致した場合はNone、elseの場合はSome(1) match { ... }が返ります。

if (!condition) {
  None
} else {
  Some(1)
} match {
  case Some(v) => v
  case _       => -1
}

Term$If
├─Term$ApplyUnary
│　├─Term$Name (!)
│　└─Term$Name (condition)
├─Term$Block
│　└─Term$Name (None)
└─Term$Match
　　├─Term$Block
　　│　└─Term$Apply
　　│　　　├─Term$Name (Some)
　　│　　　└─Lit (1)
　　├─Case
　　│　├─Pat$Extract
　　│　│　├─Term$Name (Some)
　　│　│　└─Pat$Var$Term
　　│　│　　　└─Term$Name (v)
　　│　└─Term$Name (v)
　　└─Case
　　　　├─Pat$Wildcard
　　　　└─Lit (-1)

修正後のコードの構文木

Statement全体がパターンマッチになり、パターンマッチに渡される値がif式の結果になっています。 推測した結果と修正方法が正しかったことが確認できました。

(if (!condition) {
  None
} else {
  Some(1)
}) match {
  case Some(v) => v
  case _       => -1
}

Term$Match
├─Term$If
│　├─Term$ApplyUnary
│　│　├─Term$Name (!)
│　│　└─Term$Name (condition)
│　├─Term$Block
│　│　└─Term$Name (None)
│　└─Term$Block
│　　　└─Term$Apply
│　　　　　├─Term$Name (Some)
│　　　　　└─Lit (1)
├─Case
│　├─Pat$Extract
│　│　├─Term$Name (Some)
│　│　└─Pat$Var$Term
│　│　　　└─Term$Name (v)
│　└─Term$Name (v)
└─Case
　　├─Pat$Wildcard
　　└─Lit (-1)

おまけ

中置記法の解釈のされ方です。

Graph.prettyPrint(q"a b c")

Term$ApplyInfix
├─Term$Name (a)
├─Term$Name (b)
└─Term$Name (c)

=> a.b(c)

Graph.prettyPrint(q"a b c d")

Term$Select
├─Term$ApplyInfix
│　├─Term$Name (a)
│　├─Term$Name (b)
│　└─Term$Name (c)
└─Term$Name (d)

=> a.b(c).d

Graph.prettyPrint(q"a b c d e")

Term$ApplyInfix
├─Term$ApplyInfix
│　├─Term$Name (a)
│　├─Term$Name (b)
│　└─Term$Name (c)
├─Term$Name (d)
└─Term$Name (e)

=> a.b(c).d(e)

Graph.prettyPrint(q"a b c d e f")

Term$Select
├─Term$ApplyInfix
│　├─Term$ApplyInfix
│　│　├─Term$Name (a)
│　│　├─Term$Name (b)
│　│　└─Term$Name (c)
│　├─Term$Name (d)
│　└─Term$Name (e)
└─Term$Name (f)

=> a.b(c).d(e).f

関連リンク

ScalaMatsuri 2017のscala.metaに関連するトーク

• 2月25日 (土曜日) 会場A 15:30 - 16:10
  メタメタにしてやんよ。(メタプログラミングもしくは Shapeless のすすめ) Chris Birchall氏

• 2月26日 (日曜日) 会場A 14:30 - 15:10
  scala.meta Crash Course Devon Stewart氏

ScalaMatsuri 2017の感想ブログ

• typesafe configの設定パスをscalaのコードで表現する - tototoshi の日記
  http://tototoshi.hatenablog.com/entry/2017/03/09/231701

*1:仮に推測結果が正しかったとしても