diff options
author | Nicolas Stucki <nicolas.stucki@gmail.com> | 2016-07-20 16:25:25 +0200 |
---|---|---|
committer | Nicolas Stucki <nicolas.stucki@gmail.com> | 2016-08-24 16:53:11 +0200 |
commit | c3c796f6b46a93dbace9b3c281a634f2f49a4d2d (patch) | |
tree | 5750d201efc8421a784d4e732b058b65e42fbc79 /src/dotty/tools/dotc/util/DiffUtil.scala | |
parent | 0e8f05d88bfef95fac59f522fd9d06792126bd11 (diff) | |
download | dotty-c3c796f6b46a93dbace9b3c281a634f2f49a4d2d.tar.gz dotty-c3c796f6b46a93dbace9b3c281a634f2f49a4d2d.tar.bz2 dotty-c3c796f6b46a93dbace9b3c281a634f2f49a4d2d.zip |
Fix #1405: Implement Xprint-diff without external libraries.
Diffstat (limited to 'src/dotty/tools/dotc/util/DiffUtil.scala')
-rw-r--r-- | src/dotty/tools/dotc/util/DiffUtil.scala | 130 |
1 files changed, 105 insertions, 25 deletions
diff --git a/src/dotty/tools/dotc/util/DiffUtil.scala b/src/dotty/tools/dotc/util/DiffUtil.scala index b28f36382..b7c77ad62 100644 --- a/src/dotty/tools/dotc/util/DiffUtil.scala +++ b/src/dotty/tools/dotc/util/DiffUtil.scala @@ -1,7 +1,7 @@ package dotty.tools.dotc.util import scala.annotation.tailrec -import difflib._ +import scala.collection.mutable object DiffUtil { @@ -13,9 +13,8 @@ object DiffUtil { private final val ADDITION_COLOR = ANSI_GREEN def mkColoredCodeDiff(code: String, lastCode: String, printDiffDel: Boolean): String = { - import scala.collection.JavaConversions._ - @tailrec def split(str: String, acc: List[String]): List[String] = { + @tailrec def splitTokens(str: String, acc: List[String] = Nil): List[String] = { if (str == "") { acc.reverse } else { @@ -30,38 +29,119 @@ object DiffUtil { !Character.isMirrored(c) && !Character.isWhitespace(c) } } - split(rest, token :: acc) + splitTokens(rest, token :: acc) } } - val lines = split(code, Nil).toArray - val diff = DiffUtils.diff(split(lastCode, Nil), lines.toList) + val tokens = splitTokens(code, Nil).toArray + val lastTokens = splitTokens(lastCode, Nil).toArray - for (delta <- diff.getDeltas) { - val pos = delta.getRevised.getPosition - val endPos = pos + delta.getRevised.getLines.size - 1 + val diff = hirschberg(lastTokens, tokens) - delta.getType.toString match { // Issue #1355 forces us to use the toString - case "INSERT" => - lines(pos) = ADDITION_COLOR + lines(pos) - lines(endPos) = lines(endPos) + ANSI_DEFAULT + diff.collect { + case Unmodified(str) => str + case Inserted(str) => ADDITION_COLOR + str + ANSI_DEFAULT + case Modified(old, str) if printDiffDel => DELETION_COLOR + old + ADDITION_COLOR + str + ANSI_DEFAULT + case Modified(_, str) => ADDITION_COLOR + str + ANSI_DEFAULT + case Deleted(str) if printDiffDel => DELETION_COLOR + str + ANSI_DEFAULT + }.mkString + } - case "CHANGE" => - val old = if (!printDiffDel) "" else - DELETION_COLOR + delta.getOriginal.getLines.mkString + ANSI_DEFAULT - lines(pos) = old + ADDITION_COLOR + lines(pos) - lines(endPos) = lines(endPos) + ANSI_DEFAULT + private sealed trait Patch + private final case class Unmodified(str: String) extends Patch + private final case class Modified(original: String, str: String) extends Patch + private final case class Deleted(str: String) extends Patch + private final case class Inserted(str: String) extends Patch - case "DELETE" if printDiffDel => - val deleted = delta.getOriginal.getLines.mkString - if (!deleted.forall(Character.isWhitespace)) { - lines(pos) = DELETION_COLOR + deleted + ANSI_DEFAULT + lines(pos) - } + private def hirschberg(a: Array[String], b: Array[String]): Array[Patch] = { + def build(x: Array[String], y: Array[String], builder: mutable.ArrayBuilder[Patch]): Unit = { + if (x.isEmpty) { + builder += Inserted(y.mkString) + } else if (y.isEmpty) { + builder += Deleted(x.mkString) + } else if (x.length == 1 || y.length == 1) { + needlemanWunsch(x, y, builder) + } else { + val xlen = x.length + val xmid = xlen / 2 + val ylen = y.length + + val (x1, x2) = x.splitAt(xmid) + val leftScore = nwScore(x1, y) + val rightScore = nwScore(x2.reverse, y.reverse) + val scoreSum = (leftScore zip rightScore.reverse).map { + case (left, right) => left + right + } + val max = scoreSum.max + val ymid = scoreSum.indexOf(max) - case _ => + val (y1, y2) = y.splitAt(ymid) + build(x1, y1, builder) + build(x2, y2, builder) } } + val builder = Array.newBuilder[Patch] + build(a, b, builder) + builder.result() + } + + private def nwScore(x: Array[String], y: Array[String]): Array[Int] = { + def ins(s: String) = -2 + def del(s: String) = -2 + def sub(s1: String, s2: String) = if (s1 == s2) 2 else -1 - lines.mkString + val score = Array.fill(x.length + 1, y.length + 1)(0) + for (j <- 1 to y.length) + score(0)(j) = score(0)(j - 1) + ins(y(j - 1)) + for (i <- 1 to x.length) { + score(i)(0) = score(i - 1)(0) + del(x(i - 1)) + for (j <- 1 to y.length) { + val scoreSub = score(i - 1)(j - 1) + sub(x(i - 1), y(j - 1)) + val scoreDel = score(i - 1)(j) + del(x(i - 1)) + val scoreIns = score(i)(j - 1) + ins(y(j - 1)) + score(i)(j) = scoreSub max scoreDel max scoreIns + } + } + Array.tabulate(y.length + 1)(j => score(x.length)(j)) } + + private def needlemanWunsch(x: Array[String], y: Array[String], builder: mutable.ArrayBuilder[Patch]): Unit = { + def similarity(a: String, b: String) = if (a == b) 2 else -1 + val d = 1 + val score = Array.tabulate(x.length + 1, y.length + 1) { (i, j) => + if (i == 0) d * j + else if (j == 0) d * i + else 0 + } + for (i <- 1 to x.length) { + for (j <- 1 to y.length) { + val mtch = score(i - 1)(j - 1) + similarity(x(i - 1), y(j - 1)) + val delete = score(i - 1)(j) + d + val insert = score(i)(j - 1) + d + score(i)(j) = mtch max insert max delete + } + } + + var alignment = List.empty[Patch] + var i = x.length + var j = y.length + while (i > 0 || j > 0) { + if (i > 0 && j > 0 && score(i)(j) == score(i - 1)(j - 1) + similarity(x(i - 1), y(j - 1))) { + val newHead = + if (x(i - 1) == y(j - 1)) Unmodified(x(i - 1)) + else Modified(x(i - 1), y(j - 1)) + alignment = newHead :: alignment + i = i - 1 + j = j - 1 + } else if (i > 0 && score(i)(j) == score(i - 1)(j) + d) { + alignment = Deleted(x(i - 1)) :: alignment + i = i - 1 + } else { + alignment = Inserted(y(j - 1)) :: alignment + j = j - 1 + } + } + builder ++= alignment + } + } |