Merge pull request #2340 from folone/topic/kind-pr

Added a :kind command to the REPL

5 files changed, 260 insertions, 6 deletions

diff --git a/src/reflect/scala/reflect/internal/Kinds.scala b/src/reflect/scala/reflect/internal/Kinds.scala
index 4612e65e7a..46a95c7d26 100644
--- a/src/reflect/scala/reflect/internal/Kinds.scala
+++ b/src/reflect/scala/reflect/internal/Kinds.scala
@@ -230,4 +230,180 @@ trait Kinds {
       }
     }
   }
+
+  /**
+   * The data structure describing the kind of a given type.
+   * 
+   * Proper types are represented using ProperTypeKind.
+   *
+   * Type constructors are reprented using TypeConKind.
+   */
+  abstract class Kind {
+    import Kind.StringState
+    def description: String
+    def order: Int
+    def bounds: TypeBounds
+
+    /** Scala syntax notation of this kind.
+     * Proper types are expresses as A.
+     * Type constructors are expressed as F[k1 >: lo <: hi, k2, ...] where k1, k2, ... are parameter kinds.
+     * If the bounds exists at any level, it preserves the type variable names. Otherwise,
+     * it uses prescribed letters for each level: A, F, X, Y, Z.
+     */
+    def scalaNotation: String
+    
+    /** Kind notation used in http://adriaanm.github.com/files/higher.pdf.
+     * Proper types are expressed as *.
+     * Type constructors are expressed * -> *(lo, hi) -(+)-> *.
+     */
+    def starNotation: String
+
+    /** Contains bounds either as part of itself or its arguments.
+     */
+    def hasBounds: Boolean = !bounds.isEmptyBounds
+    
+    private[internal] def buildState(sym: Symbol, v: Variance)(s: StringState): StringState
+  }
+  object Kind {
+    private[internal] sealed trait ScalaNotation
+    private[internal] sealed case class Head(order: Int, n: Option[Int], alias: Option[String]) extends ScalaNotation {
+      override def toString: String = { 
+        alias getOrElse {
+          typeAlias(order) + n.map(_.toString).getOrElse("")
+        }
+      }
+      private def typeAlias(x: Int): String =
+        x match {
+          case 0 => "A"
+          case 1 => "F"
+          case 2 => "X"
+          case 3 => "Y"
+          case 4 => "Z"
+          case n if n < 12 => ('O'.toInt - 5 + n).toChar.toString
+          case _ => "V"
+        }
+    }
+    private[internal] sealed case class Text(value: String) extends ScalaNotation {
+      override def toString: String = value
+    } 
+    private[internal] case class StringState(tokens: Seq[ScalaNotation]) {
+      override def toString: String = tokens.mkString
+      def append(value: String): StringState = StringState(tokens :+ Text(value))
+      def appendHead(order: Int, sym: Symbol): StringState = {
+        val n = countByOrder(order) + 1
+        val alias = if (sym eq NoSymbol) None
+                    else Some(sym.nameString)
+        StringState(tokens :+ Head(order, Some(n), alias))
+      }
+      def countByOrder(o: Int): Int = tokens count {
+        case Head(`o`, _, _) => true
+        case t               => false
+      }
+      // Replace Head(o, Some(1), a) with Head(o, None, a) if countByOrder(o) <= 1, so F1[A] becomes F[A]
+      def removeOnes: StringState = {
+        val maxOrder = (tokens map {
+          case Head(o, _, _) => o
+          case _             => 0
+        }).max
+        StringState((tokens /: (0 to maxOrder)) { (ts: Seq[ScalaNotation], o: Int) =>
+          if (countByOrder(o) <= 1)
+            ts map {
+              case Head(`o`, _, a) => Head(o, None, a)
+              case t               => t
+            } 
+          else ts
+        })
+      }
+      // Replace Head(o, n, Some(_)) with Head(o, n, None), so F[F] becomes F[A].
+      def removeAlias: StringState = {
+        StringState(tokens map {
+          case Head(o, n, Some(_)) => Head(o, n, None)
+          case t                   => t
+        })
+      }
+    }
+    private[internal] object StringState {
+      def empty: StringState = StringState(Seq())
+    }
+  }
+  class ProperTypeKind(val bounds: TypeBounds) extends Kind {
+    import Kind.StringState
+    val description: String = "This is a proper type."
+    val order = 0
+    private[internal] def buildState(sym: Symbol, v: Variance)(s: StringState): StringState = {
+      s.append(v.symbolicString).appendHead(order, sym).append(bounds.scalaNotation(_.toString))
+    } 
+    def scalaNotation: String = Kind.Head(order, None, None) + bounds.scalaNotation(_.toString)
+    def starNotation: String = "*" + bounds.starNotation(_.toString)
+  }
+  object ProperTypeKind {
+    def apply: ProperTypeKind = this(TypeBounds.empty)
+    def apply(bounds: TypeBounds): ProperTypeKind = new ProperTypeKind(bounds)
+    def unapply(ptk: ProperTypeKind): Some[TypeBounds] = Some(ptk.bounds)
+  }
+
+  class TypeConKind(val bounds: TypeBounds, val args: Seq[TypeConKind.Argument]) extends Kind {
+    import Kind.StringState
+    val order = (args map {_.kind.order} max) + 1
+    def description: String =
+      if (order == 1) "This is a type constructor: a 1st-order-kinded type."
+      else  "This is a type constructor that takes type constructor(s): a higher-kinded type."
+    override def hasBounds: Boolean = super.hasBounds || args.exists(_.kind.hasBounds)
+    def scalaNotation: String = {
+      val s = buildState(NoSymbol, Variance.Invariant)(StringState.empty).removeOnes
+      val s2 = if (hasBounds) s
+               else s.removeAlias
+      s2.toString
+    }
+    private[internal] def buildState(sym: Symbol, v: Variance)(s0: StringState): StringState = {
+      var s: StringState = s0
+      s = s.append(v.symbolicString).appendHead(order, sym).append("[")
+      args.zipWithIndex foreach { case (arg, i) =>
+        s = arg.kind.buildState(arg.sym, arg.variance)(s)
+        if (i != args.size - 1) {
+          s = s.append(",")
+        }
+      }
+      s = s.append("]").append(bounds.scalaNotation(_.toString))
+      s
+    }
+    def starNotation: String = {
+      import Variance._
+      (args map { arg =>
+        (if (arg.kind.order == 0) arg.kind.starNotation
+        else "(" + arg.kind.starNotation + ")") +
+        (if (arg.variance == Invariant) " -> "
+        else " -(" + arg.variance.symbolicString + ")-> ")
+      }).mkString + "*" + bounds.starNotation(_.toString)
+    }
+  }
+  object TypeConKind {
+    def apply(args: Seq[TypeConKind.Argument]): TypeConKind = this(TypeBounds.empty, args)
+    def apply(bounds: TypeBounds, args: Seq[TypeConKind.Argument]): TypeConKind = new TypeConKind(bounds, args)
+    def unapply(tck: TypeConKind): Some[(TypeBounds, Seq[TypeConKind.Argument])] = Some(tck.bounds, tck.args)
+    case class Argument(variance: Variance, kind: Kind)(val sym: Symbol) {}
+  }
+
+  /**
+   * Starting from a Symbol (sym) or a Type (tpe), infer the kind that classifies it (sym.tpeHK/tpe).
+   */
+  object inferKind {
+    import TypeConKind.Argument
+    
+    abstract class InferKind {
+      protected def infer(tpe: Type, owner: Symbol, topLevel: Boolean): Kind
+      protected def infer(sym: Symbol, topLevel: Boolean): Kind = infer(sym.tpeHK, sym.owner, topLevel)
+      def apply(sym: Symbol): Kind = infer(sym, true)
+      def apply(tpe: Type, owner: Symbol): Kind = infer(tpe, owner, true)
+    }
+
+    def apply(pre: Type): InferKind = new InferKind {
+      protected def infer(tpe: Type, owner: Symbol, topLevel: Boolean): Kind = {        
+        val bounds = if (topLevel) TypeBounds.empty
+                     else tpe.asSeenFrom(pre, owner).bounds
+        if(!tpe.isHigherKinded) ProperTypeKind(bounds)
+        else TypeConKind(bounds, tpe.typeParams map { p => Argument(p.variance, infer(p, false))(p) })
+      }
+    }
+  }
 }
diff --git a/src/reflect/scala/reflect/internal/Types.scala b/src/reflect/scala/reflect/internal/Types.scala
index 00fd20a46b..3956bbcdec 100644
--- a/src/reflect/scala/reflect/internal/Types.scala
+++ b/src/reflect/scala/reflect/internal/Types.scala
@@ -1435,13 +1435,27 @@ trait Types
       case TypeBounds(_, _) => that <:< this
       case _                => lo <:< that && that <:< hi
     }
-    private def lowerString = if (emptyLowerBound) "" else " >: " + lo
-    private def upperString = if (emptyUpperBound) "" else " <: " + hi
     private def emptyLowerBound = typeIsNothing(lo) || lo.isWildcard
     private def emptyUpperBound = typeIsAny(hi) || hi.isWildcard
     def isEmptyBounds = emptyLowerBound && emptyUpperBound
 
-    override def safeToString = lowerString + upperString
+    override def safeToString = scalaNotation(_.toString)
+
+    /** Bounds notation used in Scala sytanx.
+      * For example +This <: scala.collection.generic.Sorted[K,This].
+      */
+    private[internal] def scalaNotation(typeString: Type => String): String = {
+      (if (emptyLowerBound) "" else " >: " + typeString(lo)) +
+      (if (emptyUpperBound) "" else " <: " + typeString(hi))
+    }
+    /** Bounds notation used in http://adriaanm.github.com/files/higher.pdf.
+      * For example *(scala.collection.generic.Sorted[K,This]).
+      */
+    private[internal] def starNotation(typeString: Type => String): String = {
+      if (emptyLowerBound && emptyUpperBound) ""
+      else if (emptyLowerBound) "(" + typeString(hi) + ")"
+      else "(%s, %s)" format (typeString(lo), typeString(hi))
+    }
     override def kind = "TypeBoundsType"
   }
 
diff --git a/src/repl/scala/tools/nsc/interpreter/ExprTyper.scala b/src/repl/scala/tools/nsc/interpreter/ExprTyper.scala
index 55182a4f95..9353215e1e 100644
--- a/src/repl/scala/tools/nsc/interpreter/ExprTyper.scala
+++ b/src/repl/scala/tools/nsc/interpreter/ExprTyper.scala
@@ -95,4 +95,19 @@ trait ExprTyper {
     }
     finally typeOfExpressionDepth -= 1
   }
+
+  // This only works for proper types.
+  def typeOfTypeString(typeString: String): Type = {
+    def asProperType(): Option[Type] = {
+      val name = freshInternalVarName()
+      val line = "def %s: %s = ???" format (name, typeString)
+      interpretSynthetic(line) match {
+        case IR.Success =>
+          val sym0 = symbolOfTerm(name)
+          Some(sym0.asMethod.returnType)
+        case _          => None
+      }
+    }
+    beSilentDuring(asProperType()) getOrElse NoType
+  }
 }
diff --git a/src/repl/scala/tools/nsc/interpreter/ILoop.scala b/src/repl/scala/tools/nsc/interpreter/ILoop.scala
index 197e76d990..f4e06f6bfc 100644
--- a/src/repl/scala/tools/nsc/interpreter/ILoop.scala
+++ b/src/repl/scala/tools/nsc/interpreter/ILoop.scala
@@ -222,6 +222,7 @@ class ILoop(in0: Option[BufferedReader], protected val out: JPrintWriter)
     shCommand,
     nullary("silent", "disable/enable automatic printing of results", verbosity),
     cmd("type", "[-v] <expr>", "display the type of an expression without evaluating it", typeCommand),
+    cmd("kind", "[-v] <expr>", "display the kind of expression's type", kindCommand),
     nullary("warnings", "show the suppressed warnings from the most recent line which had any", warningsCommand)
   )
 
@@ -287,9 +288,15 @@ class ILoop(in0: Option[BufferedReader], protected val out: JPrintWriter)
   // Still todo: modules.
   private def typeCommand(line0: String): Result = {
     line0.trim match {
-      case ""                      => ":type [-v] <expression>"
-      case s if s startsWith "-v " => intp.typeCommandInternal(s stripPrefix "-v " trim, verbose = true)
-      case s                       => intp.typeCommandInternal(s, verbose = false)
+      case "" => ":type [-v] <expression>"
+      case s  => intp.typeCommandInternal(s stripPrefix "-v " trim, verbose = s startsWith "-v ")
+    }
+  }
+
+  private def kindCommand(expr: String): Result = {
+    expr.trim match {
+      case "" => ":kind [-v] <expression>"
+      case s  => intp.kindCommandInternal(s stripPrefix "-v " trim, verbose = s startsWith "-v ")
     }
   }
 
diff --git a/src/repl/scala/tools/nsc/interpreter/package.scala b/src/repl/scala/tools/nsc/interpreter/package.scala
index 52a085080b..f82c38f5e7 100644
--- a/src/repl/scala/tools/nsc/interpreter/package.scala
+++ b/src/repl/scala/tools/nsc/interpreter/package.scala
@@ -10,6 +10,7 @@ import scala.reflect.{ classTag, ClassTag }
 import scala.reflect.runtime.{ universe => ru }
 import scala.reflect.{ClassTag, classTag}
 import scala.reflect.api.{Mirror, TypeCreator, Universe => ApiUniverse}
+import scala.util.control.Exception.catching
 
 /** The main REPL related classes and values are as follows.
  *  In addition to standard compiler classes Global and Settings, there are:
@@ -127,6 +128,47 @@ package object interpreter extends ReplConfig with ReplStrings {
       ""
     }
 
+    def kindCommandInternal(expr: String, verbose: Boolean): Unit = {
+      val catcher = catching(classOf[MissingRequirementError],
+                             classOf[ScalaReflectionException])
+      def typeFromTypeString: Option[ClassSymbol] = catcher opt {
+        exprTyper.typeOfTypeString(expr).typeSymbol.asClass
+      }
+      def typeFromNameTreatedAsTerm: Option[ClassSymbol] = catcher opt {
+        val moduleClass = exprTyper.typeOfExpression(expr).typeSymbol
+        moduleClass.linkedClassOfClass.asClass
+      }
+      def typeFromFullName: Option[ClassSymbol] = catcher opt {
+        intp.global.rootMirror.staticClass(expr)
+      }
+      def typeOfTerm: Option[TypeSymbol] = replInfo(symbolOfLine(expr)).typeSymbol match {
+        case sym: TypeSymbol => Some(sym)
+        case _ => None
+      }
+      (typeFromTypeString orElse typeFromNameTreatedAsTerm orElse typeFromFullName orElse typeOfTerm) foreach { sym => 
+        val (kind, tpe) = exitingTyper { 
+          val tpe = sym.tpeHK
+          (intp.global.inferKind(NoPrefix)(tpe, sym.owner), tpe)
+        }
+        echoKind(tpe, kind, verbose)
+      }
+    }
+
+    def echoKind(tpe: Type, kind: Kind, verbose: Boolean) {
+      def typeString(tpe: Type): String = {
+        tpe match {
+          case TypeRef(_, sym, _) => typeString(sym.typeSignature)
+          case RefinedType(_, _)  => tpe.toString
+          case _                  => tpe.typeSymbol.fullName
+        }
+      }
+      printAfterTyper(typeString(tpe) + "'s kind is " + kind.scalaNotation)
+      if (verbose) {
+        echo(kind.starNotation)
+        echo(kind.description)
+      }
+    }
+
     /** TODO -
      *  -n normalize
      *  -l label with case class parameter names