Added -Ysuggest-idents.

Suggest possible alternatives when an identifier is not in scope.

  % scala -Ysuggest-idents

  scala> import scala.collection.mutable._
  import scala.collection.mutable._

  scala> new MistBuffer
  <console>:11: error: not found: type MistBuffer (similar: ListBuffer, Buffer)
                new MistBuffer
                    ^

Too bad, no MistBuffer.  We'll settle for ListBuffer.

4 files changed, 94 insertions, 15 deletions

diff --git a/src/compiler/scala/tools/nsc/settings/ScalaSettings.scala b/src/compiler/scala/tools/nsc/settings/ScalaSettings.scala
index 6be15e4e98..1f8fa5bbe2 100644
--- a/src/compiler/scala/tools/nsc/settings/ScalaSettings.scala
+++ b/src/compiler/scala/tools/nsc/settings/ScalaSettings.scala
@@ -178,6 +178,7 @@ trait ScalaSettings extends AbsScalaSettings
 
   val exposeEmptyPackage = BooleanSetting("-Yexpose-empty-package", "Internal only: expose the empty package.").internalOnly()
   val YnoProductN = BooleanSetting ("-Yno-productN", "Do not add ProductN to case classes")
+  val suggestIdents = BooleanSetting("-Ysuggest-idents", "Suggest alternatives for `not found` identifiers")
 
   def stop = stopAfter
 
diff --git a/src/compiler/scala/tools/nsc/typechecker/Contexts.scala b/src/compiler/scala/tools/nsc/typechecker/Contexts.scala
index d252281002..1d9eb9c292 100644
--- a/src/compiler/scala/tools/nsc/typechecker/Contexts.scala
+++ b/src/compiler/scala/tools/nsc/typechecker/Contexts.scala
@@ -17,13 +17,16 @@ import annotation.tailrec
 trait Contexts { self: Analyzer =>
   import global._
 
-  val NoContext = new Context {
-    override def implicitss: List[List[ImplicitInfo]] = List()
-    outer = this
+  object NoContext extends Context {
+    outer      = this
+    enclClass  = this
+    enclMethod = this
+    
+    override def nextEnclosing(p: Context => Boolean): Context = this
+    override def enclosingContextChain: List[Context] = Nil
+    override def implicitss: List[List[ImplicitInfo]] = Nil
     override def toString = "NoContext"
   }
-  NoContext.enclClass = NoContext
-  NoContext.enclMethod = NoContext
 
   private val startContext = {
     NoContext.make(
@@ -337,7 +340,9 @@ trait Contexts { self: Analyzer =>
     }
 
     def nextEnclosing(p: Context => Boolean): Context =
-      if (this == NoContext || p(this)) this else outer.nextEnclosing(p)
+      if (p(this)) this else outer.nextEnclosing(p)
+
+    def enclosingContextChain: List[Context] = this :: outer.enclosingContextChain
 
     override def toString = "Context(%s@%s unit=%s scope=%s)".format(
       owner.fullName, tree.shortClass, unit, scope.##
diff --git a/src/compiler/scala/tools/nsc/typechecker/Typers.scala b/src/compiler/scala/tools/nsc/typechecker/Typers.scala
index 16c0cb40ff..30d10325be 100644
--- a/src/compiler/scala/tools/nsc/typechecker/Typers.scala
+++ b/src/compiler/scala/tools/nsc/typechecker/Typers.scala
@@ -19,6 +19,7 @@ import symtab.Flags._
 import util.Statistics
 import util.Statistics._
 import scala.tools.util.StringOps.{ countAsString, countElementsAsString }
+import scala.tools.util.EditDistance.similarString
 
 // Suggestion check whether we can do without priming scopes with symbols of outer scopes,
 // like the IDE does.
@@ -3752,7 +3753,11 @@ trait Typers extends Modes with Adaptations with PatMatVirtualiser {
           defSym = EmptyPackageClass.tpe.nonPrivateMember(name)
           defSym != NoSymbol
         }
-
+        def startingIdentContext = (
+          // ignore current variable scope in patterns to enforce linearity
+          if ((mode & (PATTERNmode | TYPEPATmode)) == 0) context
+          else context.outer
+        )
         // A symbol qualifies if it exists and is not stale. Stale symbols
         // are made to disappear here. In addition,
         // if we are in a constructor of a pattern, we ignore all definitions
@@ -3768,13 +3773,7 @@ trait Typers extends Modes with Adaptations with PatMatVirtualiser {
         if (defSym == NoSymbol) {
           var defEntry: ScopeEntry = null // the scope entry of defSym, if defined in a local scope
 
-          var cx = context
-          if ((mode & (PATTERNmode | TYPEPATmode)) != 0) {
-            // println("ignoring scope: "+name+" "+cx.scope+" "+cx.outer.scope)
-            // ignore current variable scope in patterns to enforce linearity
-            cx = cx.outer
-          }
-
+          var cx = startingIdentContext
           while (defSym == NoSymbol && cx != NoContext) {
             currentRun.compileSourceFor(context.asInstanceOf[analyzer.Context], name)
             pre = cx.enclClass.prefix
@@ -3872,7 +3871,26 @@ trait Typers extends Modes with Adaptations with PatMatVirtualiser {
               if (inaccessibleSym eq NoSymbol) {
                 // Avoiding some spurious error messages: see SI-2388.
                 if (reporter.hasErrors && (name startsWith tpnme.ANON_CLASS_NAME)) ()
-                else error(tree.pos, "not found: "+decodeWithKind(name, context.owner))
+                else {
+                  val similar = (
+                    // name length check to limit unhelpful suggestions for e.g. "x" and "b1"
+                    if (settings.suggestIdents.value && name.length > 2) {
+                      val allowed = (
+                        startingIdentContext.enclosingContextChain
+                            flatMap (ctx => ctx.scope.toList ++ ctx.imports.flatMap(_.allImportedSymbols))
+                             filter (sym => sym.isTerm == name.isTermName)
+                          filterNot (sym => sym.isPackage || sym.isSynthetic || sym.hasMeaninglessName)
+                      )
+                      val allowedStrings = (
+                        allowed.map("" + _.name).distinct.sorted
+                          filterNot (s => (s contains '$') || (s contains ' '))
+                      )
+                      similarString("" + name, allowedStrings)
+                    }
+                    else ""
+                  )
+                  error(tree.pos, "not found: "+decodeWithKind(name, context.owner) + similar)
+                }
               }
               else new AccessError(
                 tree, inaccessibleSym, context.enclClass.owner.thisType,
diff --git a/src/compiler/scala/tools/util/EditDistance.scala b/src/compiler/scala/tools/util/EditDistance.scala
new file mode 100644
index 0000000000..704286d47e
--- /dev/null
+++ b/src/compiler/scala/tools/util/EditDistance.scala
@@ -0,0 +1,55 @@
+/* NSC -- new Scala compiler
+ * Copyright 2005-2011 LAMP/EPFL
+ * @author  Paul Phillips
+ */
+
+package scala.tools
+package util
+
+object EditDistance {
+  def similarString(name: String, allowed: TraversableOnce[String]): String = {
+    val suggested = suggestions(name, allowed.toSeq, maxDistance = 2, maxSuggestions = 2)
+    if (suggested.isEmpty) "" 
+    else suggested.mkString(" (similar: ", ", ", ")")
+  }
+
+  def suggestions(a: String, bs: Seq[String], maxDistance: Int = 3, maxSuggestions: Int = 3): Seq[String] =
+    bs.map { b => (b, distance(a, b) ) } filter (_._2 <= maxDistance) sortBy(_._2) take(maxSuggestions) map(_._1)
+
+  def distance(a: String, b: String): Int =
+    levenshtein(a, b, insertCost = 1, deleteCost = 1, subCost = 2, transposeCost = 1, matchCost = -1, true)
+
+  /** Translated from the java version at
+  *    http://www.merriampark.com/ld.htm
+  *  which is declared to be public domain.
+  */
+  def levenshtein(s: String, t: String, insertCost: Int = 1, deleteCost: Int = 1, subCost: Int = 1, transposeCost: Int = 1, matchCost: Int = 0, transpositions: Boolean = false): Int = {
+    val n = s.length
+    val m = t.length
+    if (n == 0) return m
+    if (m == 0) return n
+
+    val d = Array.ofDim[Int](n + 1, m + 1)
+    0 to n foreach (x => d(x)(0) = x)
+    0 to m foreach (x => d(0)(x) = x)
+
+    for (i <- 1 to n ; val s_i = s(i - 1) ; j <- 1 to m) {
+      val t_j   = t(j - 1)
+      val cost  = if (s_i == t_j) matchCost else subCost
+      val tcost = if (s_i == t_j) matchCost else transposeCost
+
+      val c1 = d(i - 1)(j) + deleteCost
+      val c2 = d(i)(j - 1) + insertCost
+      val c3 = d(i - 1)(j - 1) + cost
+
+      d(i)(j) = c1 min c2 min c3
+
+      if (transpositions) {
+        if (i > 1 && j > 1 && s(i - 1) == t(j - 2) && s(i - 2) == t(j - 1))
+        d(i)(j) = d(i)(j) min (d(i - 2)(j - 2) + cost)
+      }
+    }
+
+    d(n)(m)
+  }
+}