diff options
Diffstat (limited to 'src/compiler')
19 files changed, 176 insertions, 41 deletions
diff --git a/src/compiler/scala/reflect/internal/Importers.scala b/src/compiler/scala/reflect/internal/Importers.scala index 6d672d9263..60b353a7c4 100644 --- a/src/compiler/scala/reflect/internal/Importers.scala +++ b/src/compiler/scala/reflect/internal/Importers.scala @@ -231,6 +231,8 @@ trait Importers { self: SymbolTable => new PackageDef(importRefTree(pid), stats map importTree) case from.ModuleDef(mods, name, impl) => new ModuleDef(importModifiers(mods), importName(name).toTermName, importTemplate(impl)) + case from.emptyValDef => + emptyValDef case from.ValDef(mods, name, tpt, rhs) => new ValDef(importModifiers(mods), importName(name).toTermName, importTree(tpt), importTree(rhs)) case from.DefDef(mods, name, tparams, vparamss, tpt, rhs) => diff --git a/src/compiler/scala/reflect/internal/Types.scala b/src/compiler/scala/reflect/internal/Types.scala index 320fb949ff..265261f594 100644 --- a/src/compiler/scala/reflect/internal/Types.scala +++ b/src/compiler/scala/reflect/internal/Types.scala @@ -4174,8 +4174,16 @@ A type's typeSymbol should never be inspected directly. private def adaptToNewRun(pre: Type, sym: Symbol): Symbol = { if (phase.flatClasses) { sym + } else if (sym == definitions.RootClass) { + definitions.RootClass + } else if (sym == definitions.RootPackage) { + definitions.RootPackage } else if (sym.isModuleClass) { - adaptToNewRun(pre, sym.sourceModule).moduleClass + val sourceModule1 = adaptToNewRun(pre, sym.sourceModule) + val result = sourceModule1.moduleClass + val msg = "sym = %s, sourceModule = %s, sourceModule.moduleClass = %s => sourceModule1 = %s, sourceModule1.moduleClass = %s" + assert(result != NoSymbol, msg.format(sym, sym.sourceModule, sym.sourceModule.moduleClass, sourceModule1, sourceModule1.moduleClass)) + result } else if ((pre eq NoPrefix) || (pre eq NoType) || sym.isPackageClass) { sym } else { diff --git a/src/compiler/scala/reflect/internal/pickling/UnPickler.scala b/src/compiler/scala/reflect/internal/pickling/UnPickler.scala index 00dc04de80..9aa3d8a2c3 100644 --- a/src/compiler/scala/reflect/internal/pickling/UnPickler.scala +++ b/src/compiler/scala/reflect/internal/pickling/UnPickler.scala @@ -509,7 +509,7 @@ abstract class UnPickler /*extends reflect.generic.UnPickler*/ { val tpe = if (tag == EMPTYtree) NoType else readTypeRef() // Set by the three functions to follow. If symbol is non-null - // after the the new tree 't' has been created, t has its Symbol + // after the new tree 't' has been created, t has its Symbol // set to symbol; and it always has its Type set to tpe. var symbol: Symbol = null var mods: Modifiers = null diff --git a/src/compiler/scala/tools/ant/templates/tool-unix.tmpl b/src/compiler/scala/tools/ant/templates/tool-unix.tmpl index 4275ef7ba1..7e51930fa4 100644 --- a/src/compiler/scala/tools/ant/templates/tool-unix.tmpl +++ b/src/compiler/scala/tools/ant/templates/tool-unix.tmpl @@ -58,12 +58,17 @@ if uname | grep -q ^CYGWIN; then cygwin="$(uname)" fi +unset mingw +if uname | grep -q ^MINGW; then + mingw="$(uname)" +fi + # Finding the root folder for this Scala distribution SCALA_HOME="$(findScalaHome)" SEP=":" # Possible additional command line options -CYGWIN_OPT="" +WINDOWS_OPT="" EMACS_OPT="" [[ -n "$EMACS" ]] && EMACS_OPT="-Denv.emacs=$EMACS" @@ -94,10 +99,16 @@ if [[ -n "$cygwin" ]]; then fi SCALA_HOME="$(cygpath --$format "$SCALA_HOME")" TOOL_CLASSPATH="$(cygpath --path --$format "$TOOL_CLASSPATH")" +elif [[ -n "$mingw" ]]; then + SCALA_HOME="$(cmd //c echo "$SCALA_HOME")" + TOOL_CLASSPATH="$(cmd //c echo "$TOOL_CLASSPATH")" +fi + +if [[ -n "$cygwin$mingw" ]]; then case "$TERM" in rxvt* | xterm*) stty -icanon min 1 -echo - CYGWIN_OPT="-Djline.terminal=scala.tools.jline.UnixTerminal" + WINDOWS_OPT="-Djline.terminal=scala.tools.jline.UnixTerminal" ;; esac fi @@ -110,9 +121,10 @@ fi declare -a java_args declare -a scala_args -# default to the boot classpath for speed, except on cygwin/mingw. +# default to the boot classpath for speed, except on cygwin/mingw because +# JLine on Windows requires a custom DLL to be loaded. unset usebootcp -if [[ -z $cygwin ]]; then +if [[ -z "$cygwin$mingw" ]]; then usebootcp="true" fi @@ -181,7 +193,7 @@ execCommand \ -Dscala.home="$SCALA_HOME" \ -Dscala.usejavacp=true \ $EMACS_OPT \ - $CYGWIN_OPT \ + $WINDOWS_OPT \ @properties@ @class@ @toolflags@ "$@@" # record the exit status lest it be overwritten: diff --git a/src/compiler/scala/tools/nsc/ast/Trees.scala b/src/compiler/scala/tools/nsc/ast/Trees.scala index 9668debbbb..85849cfad4 100644 --- a/src/compiler/scala/tools/nsc/ast/Trees.scala +++ b/src/compiler/scala/tools/nsc/ast/Trees.scala @@ -257,6 +257,10 @@ trait Trees extends reflect.internal.Trees { self: Global => case _: DefTree | Function(_, _) | Template(_, _, _) => resetDef(tree) tree.tpe = null + tree match { + case tree: DefDef => tree.tpt.tpe = null + case _ => () + } case tpt: TypeTree => if (tpt.wasEmpty) tree.tpe = null case This(_) if tree.symbol != null && tree.symbol.isPackageClass => diff --git a/src/compiler/scala/tools/nsc/ast/parser/TreeBuilder.scala b/src/compiler/scala/tools/nsc/ast/parser/TreeBuilder.scala index f65481e29a..13f608ed4e 100644 --- a/src/compiler/scala/tools/nsc/ast/parser/TreeBuilder.scala +++ b/src/compiler/scala/tools/nsc/ast/parser/TreeBuilder.scala @@ -310,7 +310,7 @@ abstract class TreeBuilder { * for (P <- G) E ==> G.foreach (P => E) * * Here and in the following (P => E) is interpreted as the function (P => E) - * if P is a a variable pattern and as the partial function { case P => E } otherwise. + * if P is a variable pattern and as the partial function { case P => E } otherwise. * * 2. * diff --git a/src/compiler/scala/tools/nsc/backend/icode/Linearizers.scala b/src/compiler/scala/tools/nsc/backend/icode/Linearizers.scala index 8130c99978..1978a23d90 100644 --- a/src/compiler/scala/tools/nsc/backend/icode/Linearizers.scala +++ b/src/compiler/scala/tools/nsc/backend/icode/Linearizers.scala @@ -284,7 +284,7 @@ trait Linearizers { handler.startBlock +=: lb } - // The first block emitted after a try-catch must be the the one that the try / catch + // The first block emitted after a try-catch must be the one that the try / catch // blocks jump to (because in msil, these jumps cannot be emitted manually) var firstAfter: Option[BasicBlock] = None diff --git a/src/compiler/scala/tools/nsc/backend/jvm/BytecodeWriters.scala b/src/compiler/scala/tools/nsc/backend/jvm/BytecodeWriters.scala index 70aa8ff54e..865bacffaa 100644 --- a/src/compiler/scala/tools/nsc/backend/jvm/BytecodeWriters.scala +++ b/src/compiler/scala/tools/nsc/backend/jvm/BytecodeWriters.scala @@ -7,7 +7,7 @@ package scala.tools.nsc package backend.jvm import ch.epfl.lamp.fjbg._ -import java.io.{ DataOutputStream, OutputStream, File => JFile } +import java.io.{ DataOutputStream, FileOutputStream, OutputStream, File => JFile } import scala.tools.nsc.io._ import scala.tools.nsc.util.ScalaClassLoader import scala.tools.util.JavapClass @@ -85,7 +85,7 @@ trait BytecodeWriters { emitJavap(bytes, javapFile) } } - + trait ClassBytecodeWriter extends BytecodeWriter { def writeClass(label: String, jclass: JClass, sym: Symbol) { val outfile = getFile(sym, jclass, ".class") @@ -96,4 +96,20 @@ trait BytecodeWriters { informProgress("wrote '" + label + "' to " + outfile) } } + + trait DumpBytecodeWriter extends BytecodeWriter { + val baseDir = Directory(settings.Ydumpclasses.value).createDirectory() + + abstract override def writeClass(label: String, jclass: JClass, sym: Symbol) { + super.writeClass(label, jclass, sym) + + val pathName = jclass.getName() + var dumpFile = pathName.split("[./]").foldLeft(baseDir: Path) (_ / _) changeExtension "class" toFile; + dumpFile.parent.createDirectory() + val outstream = new DataOutputStream(new FileOutputStream(dumpFile.path)) + + try jclass writeTo outstream + finally outstream.close() + } + } } diff --git a/src/compiler/scala/tools/nsc/backend/jvm/GenJVM.scala b/src/compiler/scala/tools/nsc/backend/jvm/GenJVM.scala index 3fe5b83515..e80927f620 100644 --- a/src/compiler/scala/tools/nsc/backend/jvm/GenJVM.scala +++ b/src/compiler/scala/tools/nsc/backend/jvm/GenJVM.scala @@ -129,7 +129,12 @@ abstract class GenJVM extends SubComponent with GenJVMUtil with GenAndroid with new DirectToJarfileWriter(f.file) case _ => - if (settings.Ygenjavap.isDefault) new ClassBytecodeWriter { } + if (settings.Ygenjavap.isDefault) { + if(settings.Ydumpclasses.isDefault) + new ClassBytecodeWriter { } + else + new ClassBytecodeWriter with DumpBytecodeWriter { } + } else new ClassBytecodeWriter with JavapBytecodeWriter { } } @@ -308,6 +313,18 @@ abstract class GenJVM extends SubComponent with GenJVMUtil with GenAndroid with private var innerClassBuffer = mutable.LinkedHashSet[Symbol]() + /** Drop redundant interfaces (ones which are implemented by some + * other parent) from the immediate parents. This is important on + * android because there is otherwise an interface explosion. + */ + private def minimizeInterfaces(interfaces: List[Symbol]): List[Symbol] = ( + interfaces filterNot (int1 => + interfaces exists (int2 => + (int1 ne int2) && (int2 isSubClass int1) + ) + ) + ) + def genClass(c: IClass) { clasz = c innerClassBuffer.clear() @@ -322,7 +339,7 @@ abstract class GenJVM extends SubComponent with GenJVMUtil with GenAndroid with } val ifaces = superInterfaces match { case Nil => JClass.NO_INTERFACES - case _ => mkArray(superInterfaces map (x => javaName(x.typeSymbol))) + case _ => mkArray(minimizeInterfaces(superInterfaces map (_.typeSymbol)) map javaName) } jclass = fjbgContext.JClass(javaFlags(c.symbol), @@ -469,7 +486,7 @@ abstract class GenJVM extends SubComponent with GenJVMUtil with GenAndroid with // push the class jcode emitPUSH javaType(c.symbol).asInstanceOf[JReferenceType] - // push the the string array of field information + // push the string array of field information jcode emitPUSH fieldList.length jcode emitANEWARRAY strKind push(fieldList) diff --git a/src/compiler/scala/tools/nsc/doc/model/Entity.scala b/src/compiler/scala/tools/nsc/doc/model/Entity.scala index 266b9294dd..6eb14a4907 100644 --- a/src/compiler/scala/tools/nsc/doc/model/Entity.scala +++ b/src/compiler/scala/tools/nsc/doc/model/Entity.scala @@ -376,7 +376,7 @@ trait ParameterEntity extends Entity { /** A type parameter to a class, trait, or method. */ trait TypeParam extends ParameterEntity with HigherKinded { - /** The variance of this type type parameter. Valid values are "+", "-", and the empty string. */ + /** The variance of this type parameter. Valid values are "+", "-", and the empty string. */ def variance: String /** The lower bound for this type parameter, if it has been defined. */ diff --git a/src/compiler/scala/tools/nsc/interactive/CompilerControl.scala b/src/compiler/scala/tools/nsc/interactive/CompilerControl.scala index c2e27cd205..f2d59206e0 100644 --- a/src/compiler/scala/tools/nsc/interactive/CompilerControl.scala +++ b/src/compiler/scala/tools/nsc/interactive/CompilerControl.scala @@ -128,7 +128,7 @@ trait CompilerControl { self: Global => } /** Sets sync var `response` to the smallest fully attributed tree that encloses position `pos`. - * Note: Unlike for most other ask... operations, the source file belonging to `pos` needs not be be loaded. + * Note: Unlike for most other ask... operations, the source file belonging to `pos` needs not be loaded. */ def askTypeAt(pos: Position, response: Response[Tree]) = postWorkItem(new AskTypeAtItem(pos, response)) diff --git a/src/compiler/scala/tools/nsc/io/Lexer.scala b/src/compiler/scala/tools/nsc/io/Lexer.scala index 8f103f9b98..5ffb5b4d4f 100644 --- a/src/compiler/scala/tools/nsc/io/Lexer.scala +++ b/src/compiler/scala/tools/nsc/io/Lexer.scala @@ -281,7 +281,7 @@ class Lexer(rd: Reader) { /** The current token is a delimiter consisting of given character, reads next token, * otherwise raises an error. * @param c the given delimiter character to compare current token with - * @throws MalformedInput if the the current token `token` is not a delimiter, or + * @throws MalformedInput if the current token `token` is not a delimiter, or * consists of a character different from `c`. */ def accept(ch: Char) { diff --git a/src/compiler/scala/tools/nsc/settings/ScalaSettings.scala b/src/compiler/scala/tools/nsc/settings/ScalaSettings.scala index 6be15e4e98..7fcfb6fc6d 100644 --- a/src/compiler/scala/tools/nsc/settings/ScalaSettings.scala +++ b/src/compiler/scala/tools/nsc/settings/ScalaSettings.scala @@ -139,6 +139,7 @@ trait ScalaSettings extends AbsScalaSettings val Yshowsyms = BooleanSetting ("-Yshow-syms", "Print the AST symbol hierarchy after each phase.") val skip = PhasesSetting ("-Yskip", "Skip") val Ygenjavap = StringSetting ("-Ygen-javap", "dir", "Generate a parallel output directory of .javap files.", "") + val Ydumpclasses = StringSetting ("-Ydump-classes", "dir", "Dump the generated bytecode to .class files (useful for reflective compilation that utilizes in-memory classloaders).", "") val Ynosqueeze = BooleanSetting ("-Yno-squeeze", "Disable creation of compact code in matching.") val Ystatistics = BooleanSetting ("-Ystatistics", "Print compiler statistics.") . withPostSetHook(set => util.Statistics.enabled = set.value) diff --git a/src/compiler/scala/tools/nsc/transform/LiftCode.scala b/src/compiler/scala/tools/nsc/transform/LiftCode.scala index 7a64fc9b5e..f3f823d197 100644 --- a/src/compiler/scala/tools/nsc/transform/LiftCode.scala +++ b/src/compiler/scala/tools/nsc/transform/LiftCode.scala @@ -95,7 +95,7 @@ abstract class LiftCode extends Transform with TypingTransformers { buf.append(", " + "List(" + annotations + ")") var s = buf.toString - if (s.endsWith(", Map()")) s = s.substring(0, s.length - ", Map()".length) + if (s.endsWith(", List()")) s = s.substring(0, s.length - ", List()".length) if (s.endsWith(", newTypeName(\"\")")) s = s.substring(0, s.length - ", newTypeName(\"\")".length) if (s.endsWith("Set()")) s = s.substring(0, s.length - "Set()".length) "Modifiers(" + s + ")" @@ -475,7 +475,7 @@ abstract class LiftCode extends Transform with TypingTransformers { case tt: TypeTree if (tt.tpe != null) => if (!(boundSyms exists (tt.tpe contains _))) mirrorCall("TypeTree", reifyType(tt.tpe)) else if (tt.original != null) reify(tt.original) - else TypeTree() + else mirrorCall("TypeTree") case global.emptyValDef => mirrorSelect("emptyValDef") case _ => 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/NamesDefaults.scala b/src/compiler/scala/tools/nsc/typechecker/NamesDefaults.scala index cc88f471ab..e4ebe13217 100644 --- a/src/compiler/scala/tools/nsc/typechecker/NamesDefaults.scala +++ b/src/compiler/scala/tools/nsc/typechecker/NamesDefaults.scala @@ -227,7 +227,7 @@ trait NamesDefaults { self: Analyzer => // super constructor calls case Select(sp @ Super(_, _), _) if isConstr => // 'moduleQual' fixes #3207. selection of the companion module of the - // superclass needs to have the same prefix as the the superclass. + // superclass needs to have the same prefix as the superclass. blockWithoutQualifier(moduleQual(baseFun.pos, sp.symbol.tpe.parents.head)) // self constructor calls (in secondary constructors) diff --git a/src/compiler/scala/tools/nsc/typechecker/SuperAccessors.scala b/src/compiler/scala/tools/nsc/typechecker/SuperAccessors.scala index 3c72dc8413..c9991614e4 100644 --- a/src/compiler/scala/tools/nsc/typechecker/SuperAccessors.scala +++ b/src/compiler/scala/tools/nsc/typechecker/SuperAccessors.scala @@ -284,7 +284,7 @@ abstract class SuperAccessors extends transform.Transform with transform.TypingT } /** Add a protected accessor, if needed, and return a tree that calls - * the accessor and returns the the same member. The result is already + * the accessor and returns the same member. The result is already * typed. */ private def makeAccessor(tree: Select, targs: List[Tree]): Tree = { diff --git a/src/compiler/scala/tools/nsc/typechecker/Typers.scala b/src/compiler/scala/tools/nsc/typechecker/Typers.scala index b969e9629f..7671ccbed7 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. @@ -3457,12 +3458,10 @@ trait Typers extends Modes with Adaptations with PatMatVirtualiser { if (treeInfo.isVariableOrGetter(qual1)) { stopTimer(failedOpEqNanos, opeqStart) convertToAssignment(fun, qual1, name, args, ex) - } else { + } + else { stopTimer(failedApplyNanos, appStart) - if ((qual1.symbol ne null) && qual1.symbol.isValue) - error(tree.pos, "reassignment to val") - else - reportTypeError(fun.pos, ex) + reportTypeError(fun.pos, ex) setError(tree) } case _ => @@ -3754,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 @@ -3770,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 @@ -3874,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 (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..a8d7408532 --- /dev/null +++ b/src/compiler/scala/tools/util/EditDistance.scala @@ -0,0 +1,54 @@ +/* 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 = 1, maxSuggestions = 2) + if (suggested.isEmpty) "" + else suggested.mkString(" (similar: ", ", ", ")") + } + + def suggestions(a: String, bs: Seq[String], maxDistance: Int, maxSuggestions: Int): 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, transpositions = true) + + def levenshtein(s: String, t: String, transpositions: Boolean): 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) 0 else 1 + + val c1 = d(i - 1)(j) + 1 + val c2 = d(i)(j - 1) + 1 + 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) + } +} |