Myers diff algorithm in Scala.
"app.tulz" %%% "stringdiff" % "0.3.4" The core algorithm is a Scala translation of the Python implementation described here: https://blog.robertelder.org/diff-algorithm/
Additionally, the following is implemented on top of it:
- interpretation of the algorithm's output
- customizable formatting of the interpreted result into a string (with a few provided out of the box formatters)
- additional transformations for when the input is expected to be a sequence of tokens (
TokenDiff)
The core algorithm outputs a set of instructions to get from SeqA to SeqB, something like this:
in order to get from s1="bcdefgzio" to s2="abcxyfgi":
Insert a from s2 before position 0 into s1.
Delete d from s1 at position 2 in s1.
Insert x from s2 before position 3 into s1.
Insert y from s2 before position 3 into s1.
Delete e from s1 at position 3 in s1.
Delete z from s1 at position 6 in s1.
Delete o from s1 at position 8 in s1.
It's hard to work with it. Also, it is somewhat tricky at first to understand how to follow these instructions (try it! :) ).
MyersInterpret object parses the raw output into a List[DiffElement]:
trait DiffElement[Repr]
object DiffElement {
final case class InBoth[Repr](v: Repr) extends DiffElement[Repr]
final case class InFirst[Repr](v: Repr) extends DiffElement[Repr]
final case class InSecond[Repr](v: Repr) extends DiffElement[Repr]
final case class Diff[Repr](x: Repr, y: Repr) extends DiffElement[Repr]
}The result of the interpretation (without any transformations applied) for the same example:
StringDiff
.raw(
"bcdefgzio",
"abcxyfgi",
collapse = false
).mkString("[\n ", "\n ", "\n]")[
InSecond(a)
InBoth(bc)
InFirst(d)
InSecond(x)
InSecond(y)
InFirst(e)
InBoth(fg)
InFirst(z)
InBoth(i)
InFirst(o)
]
By default, diff functions will collapse the diff:
StringDiff
.raw(
"bcdefgzio",
"abcxyfgi",
collapse = true // default is true
).mkString("[\n ", "\n ", "\n]")[
InSecond(a)
InBoth(bc)
Diff(de,xy)
InBoth(fg)
InFirst(z)
InBoth(i)
InFirst(o)
]
Here, the following list of DiffElements:
[
InFirst(d)
InSecond(x)
InSecond(y)
InFirst(e)
]
got collapsed into a single one:
[
Diff(de,xy)
]
In a nutshell, collapsing removes empty elements and joins same or otherwise "join-able" subsequent DiffElements.
Examples:
- any
InFirst,InLast,DifforInBothgets removed if the element is empty DiffbecomesInFirstorInSecondif one the elements is emptyInFirst(a)+InFirst(b) -> InFirst(ab)InFirst(a)+InSecond(b) -> Diff(a,b)InSecond(a)+InDiff(b,c) -> Diff(ab,c)- etc
SeqDiff
.seq(
Seq(1, 2, 3, 4, 5).toIndexedSeq,
Seq(1, 2, 8, 3, 8, 4, 5, 0).toIndexedSeq
).mkString("[\n ", "\n ", "\n]")[
InBoth(Vector(1, 2))
InSecond(Vector(8))
InBoth(Vector(3))
InSecond(Vector(8))
InBoth(Vector(4, 5))
InSecond(Vector(0))
]
println(
StringDiff.diff(
"bcdefgzio",
"abcxyfgi"
)
)[
InSecond(a)
InBoth(bc)
Diff(de,xy)
InBoth(fg)
InFirst(z)
InBoth(i)
InFirst(o)
]
println(
StringDiff.text(
"bcdefgzio",
"abcxyfgi"
)
)[∅|a]]bc][de|xy]]fg][z|∅]]i][o|∅]
println(
StringDiff.ansi(
"bcdefgzio",
"abcxyfgi"
)
)
(default formatters highlight missing text with yellow, extraneous text — with red, and matching text is underlined)
When the inputs are strings that are expected to contain whitespace-separated tokens, TokenDiff
will try to make the diff more comprehensible in terms of tokens (while preserving the accuracy).
println(
TokenDiff.ansi(
"match-1 match-2 diff-1 diff-2 match-3 match-4 diff-1 diff-2 match-1 match-2 diff-1 match-3 match-4 diff-1 match-1 match-2 diff-1 match-3 match-4 suffix-1",
"prefix-1 match-1 match-2 diff-3 match-3 match-4 match-1 match-2 diff-2 diff-3 match-3 match-4 diff-2 match-1 match-2 match-3 match-4"
)
)
With a StringDiff the output would look like the following:
println(
StringDiff.ansi(
"match-1 match-2 diff-1 diff-2 match-3 match-4 diff-1 diff-2 match-1 match-2 diff-1 match-3 match-4 diff-1 match-1 match-2 diff-1 match-3 match-4 suffix-1",
"prefix-1 match-1 match-2 diff-3 match-3 match-4 match-1 match-2 diff-2 diff-3 match-3 match-4 diff-2 match-1 match-2 match-3 match-4"
)
)
println(
TokenDiff.ansiBoth(
"match-1 match-2 diff-1 diff-2 match-3 match-4 diff-1 diff-2 match-1 match-2 diff-1 match-3 match-4 diff-1 match-1 match-2 diff-1 match-3 match-4 suffix-1",
"prefix-1 match-1 match-2 diff-3 match-3 match-4 match-1 match-2 diff-2 diff-3 match-3 match-4 diff-2 match-1 match-2 match-3 match-4"
)
)
SeqDiff.seq(
Seq(1, 2, 3),
Seq(2, 3, 4)
)
StringDiff.ansi("abc", "acb")
// OR
StringDiff("abc", "acb")
StringDiff.ansiBoth("abc", "acb")
StringDiff.text("abc", "acb")
StringDiff.diff("abc", "acb")
StringDiff.raw("abc", "acb")
TokenDiff.ansi("abc", "acb")
// OR
TokenDiff("abc", "acb")
TokenDiff.ansiBoth("abc", "acb")
TokenDiff.text("abc", "acb")
TokenDiff.diff("abc", "acb")
TokenDiff.raw("abc", "acb")
Formatters are instances of the DiffFormat[Out] trait:
trait DiffFormat[Out] {
def apply(diff: List[DiffElement[String]]): Out
}object MyFormat extends DiffFormat[MyDiffOutput] { ... }
val diff: MyDiffOutput = MyFormat(StringDiff("abc", "acb"))For example, the TextDiffFormat is implemented like this:
object TextDiffFormat extends DiffFormat[String] {
import DiffElement._
def apply(diff: List[DiffElement[String]]): String = {
val sb = new StringBuilder
diff.foreach {
case InBoth(both) =>
sb.append("]")
sb.appendAll(both)
sb.append("]")
case InSecond(second) =>
sb.append("[∅|")
sb.appendAll(second)
sb.append("]")
case InFirst(first) =>
sb.append("[")
sb.appendAll(first)
sb.append("|∅]")
case Diff(first, second) =>
sb.append("[")
sb.appendAll(first)
sb.append("|")
sb.appendAll(second)
sb.append("]")
case _ =>
}
sb.toString()
}Iurii Malchenko – @yurique
stringdiff is provided under the MIT license.
