Jkroll has uploaded a new change for review. (
https://gerrit.wikimedia.org/r/328685 )
Change subject: [WIP] Extend WikiDiff2 to show changes inside moved paragraphes
......................................................................
[WIP] Extend WikiDiff2 to show changes inside moved paragraphes
Change-Id: If6855bcddbfea47614130daedf21a3de43510fc4
---
M InlineDiff.cpp
M InlineDiff.h
M TableDiff.cpp
M TableDiff.h
M Wikidiff2.cpp
M Wikidiff2.h
M config.m4
7 files changed, 197 insertions(+), 19 deletions(-)
git pull ssh://gerrit.wikimedia.org:29418/mediawiki/php/wikidiff2
refs/changes/85/328685/1
diff --git a/InlineDiff.cpp b/InlineDiff.cpp
index d60215c..f87f3f9 100644
--- a/InlineDiff.cpp
+++ b/InlineDiff.cpp
@@ -10,7 +10,7 @@
printWrappedLine("<div class=\"mw-diff-inline-deleted\"><del>", line,
"</del></div>\n");
}
-void InlineDiff::printWordDiff(const String& text1, const String& text2)
+void InlineDiff::printWordDiff(const String& text1, const String& text2, bool
printLeft, bool printRight)
{
WordVector words1, words2;
@@ -19,6 +19,8 @@
WordDiff worddiff(words1, words2, MAX_WORD_LEVEL_DIFF_COMPLEXITY);
String word;
+ // XXXX todo: omit left side & do strike-through according to
printLeft/printRight
+
result += "<div class=\"mw-diff-inline-changed\">";
for (unsigned i = 0; i < worddiff.size(); ++i) {
DiffOp<Word> & op = worddiff[i];
diff --git a/InlineDiff.h b/InlineDiff.h
index 01304ca..0dc7f66 100644
--- a/InlineDiff.h
+++ b/InlineDiff.h
@@ -8,7 +8,7 @@
protected:
void printAdd(const String& line);
void printDelete(const String& line);
- void printWordDiff(const String& text1, const String& text2);
+ void printWordDiff(const String& text1, const String& text2,
bool printLeft = true, bool printRight = true);
void printBlockHeader(int leftLine, int rightLine);
void printContext(const String& input);
diff --git a/TableDiff.cpp b/TableDiff.cpp
index 5a4969f..f2565eb 100644
--- a/TableDiff.cpp
+++ b/TableDiff.cpp
@@ -23,7 +23,7 @@
"</tr>\n";
}
-void TableDiff::printWordDiff(const String & text1, const String & text2)
+void TableDiff::printWordDiff(const String & text1, const String & text2, bool
printLeft, bool printRight)
{
WordVector words1, words2;
@@ -33,17 +33,29 @@
//debugPrintWordDiff(worddiff);
- // print twice; first for left side, then for right side
- result += "<tr>\n"
- " <td class=\"diff-marker\">−</td>\n"
- " <td class=\"diff-deletedline\"><div>";
- printWordDiffSide(worddiff, false);
- result += "</div></td>\n"
- " <td class=\"diff-marker\">+</td>\n"
- " <td class=\"diff-addedline\"><div>";
- printWordDiffSide(worddiff, true);
- result += "</div></td>\n"
- "</tr>\n";
+ result += "<tr>\n";
+
+ // print left side or blank placeholder.
+ if (printLeft) {
+ result += " <td class=\"diff-marker\">−</td>\n"
+ " <td class=\"diff-deletedline\"><div>";
+ printWordDiffSide(worddiff, false);
+ result += "</div></td>\n";
+ } else {
+ result += " <td colspan=\"2\"
class=\"diff-empty\"> </td>\n";
+ }
+
+ // print right side or blank placeholder.
+ if (printRight) {
+ result += " <td class=\"diff-marker\">+</td>\n"
+ " <td class=\"diff-addedline\"><div>";
+ printWordDiffSide(worddiff, true);
+ result += "</div></td>\n"
+ "</tr>\n";
+ } else {
+ result += " <td colspan=\"2\"
class=\"diff-empty\"> </td>\n"
+ "</tr>\n";
+ }
}
void TableDiff::printWordDiffSide(WordDiff &worddiff, bool added)
diff --git a/TableDiff.h b/TableDiff.h
index 0a3adc6..4a4115a 100644
--- a/TableDiff.h
+++ b/TableDiff.h
@@ -8,7 +8,7 @@
protected:
void printAdd(const String& line);
void printDelete(const String& line);
- void printWordDiff(const String& text1, const String & text2);
+ void printWordDiff(const String& text1, const String & text2,
bool printLeft = true, bool printRight = true);
void printTextWithDiv(const String& input);
void printBlockHeader(int leftLine, int rightLine);
void printContext(const String& input);
diff --git a/Wikidiff2.cpp b/Wikidiff2.cpp
index d579b61..e3ee143 100644
--- a/Wikidiff2.cpp
+++ b/Wikidiff2.cpp
@@ -11,6 +11,7 @@
#include <thai/thailib.h>
#include <thai/thwchar.h>
#include <thai/thbrk.h>
+#include <stdarg.h>
void Wikidiff2::diffLines(const StringVector & lines1, const StringVector &
lines2,
@@ -37,7 +38,9 @@
// inserted lines
n = linediff[i].to.size();
for (j=0; j<n; j++) {
- printAdd(*linediff[i].to[j]);
+ if (!printMovedLineDiff(linediff, i,
j)) {
+ printAdd(*linediff[i].to[j]);
+ }
}
to_index += n;
break;
@@ -45,7 +48,9 @@
// deleted lines
n = linediff[i].from.size();
for (j=0; j<n; j++) {
- printDelete(*linediff[i].from[j]);
+ if (!printMovedLineDiff(linediff, i,
j)) {
+
printDelete(*linediff[i].from[j]);
+ }
}
from_index += n;
break;
@@ -93,6 +98,115 @@
}
}
+//#define DEBUG_MOVED_LINES
+
+bool Wikidiff2::printMovedLineDiff(StringDiff & linediff, int opIndex, int
opLine)
+{
+ // helper fn creates 64-bit lookup key from opIndex and opLine
+ auto makeKey = [](int index, int line) {
+ return uint64_t(index) << 32 | line;
+ };
+
+#ifdef DEBUG_MOVED_LINES
+ auto debugPrintf = [this](const char *fmt, ...) {
+ char ch[2048];
+ va_list ap;
+ va_start(ap, fmt);
+ vsnprintf(ch, sizeof(ch), fmt, ap);
+ va_end(ap);
+
+ result += "<tr><td /><td class=\"diff-context\" colspan=3>";
+ result += ch;
+ result += "</td></tr>";
+ };
+#else
+ auto debugPrintf = [](...) { };
+#endif
+
+ debugPrintf("printMovedLineDiff (...), %d, %d\n", opIndex, opLine);
+
+ // look for corresponding moved line for the opposite case in
moved-line-map
+ // if moved line exists:
+ // print diff to the moved line, omitting the left/right side for
added/deleted line
+ uint64_t key = makeKey(opIndex, opLine);
+ auto it = diffMap.find(key);
+ if (it != diffMap.end()) {
+ auto best = it->second;
+
+ bool printLeft = linediff[opIndex].op == DiffOp<String>::del ?
true : false;
+ bool printRight = !printLeft;
+ // XXXX todo: we already have the diff, don't have to do it
again, just have to print it
+
printWordDiff(*linediff[best->opIndexFrom].from[best->opLineFrom],
*linediff[best->opIndexTo].to[best->opLineTo],
+ printLeft, printRight);
+
+ debugPrintf("found in diffmap. copy: %d, del: %d, add: %d,
change: %d, similarity: %.4f\n"
+ "from: (%d,%d) to: (%d,%d)\n",
+ best->opCharCount[DiffOp<Word>::copy],
best->opCharCount[DiffOp<Word>::del], best->opCharCount[DiffOp<Word>::add],
best->opCharCount[DiffOp<Word>::change], best->similarity,
+ best->opIndexFrom, best->opLineFrom, best->opIndexTo,
best->opLineTo);
+
+ return true;
+ }
+
+ // else:
+ // try to find a corresponding moved line in deleted/added lines
+ int otherOp = (linediff[opIndex].op == DiffOp<String>::add ?
DiffOp<String>::del : DiffOp<String>::add);
+ std::shared_ptr<DiffMapEntry> found = nullptr;
+ for (int i = 0; i < linediff.size(); ++i) {
+ if (linediff[i].op == otherOp) {
+ auto& lines = (linediff[opIndex].op ==
DiffOp<String>::add ? linediff[i].from : linediff[i].to);
+ for (int k = 0; k < lines.size(); ++k) {
+ WordVector words1, words2;
+ std::shared_ptr<DiffMapEntry> tmp;
+ explodeWords(*lines[k], words1);
+ if (otherOp == DiffOp<String>::del) {
+
explodeWords(*linediff[opIndex].to[opLine], words2);
+ tmp =
std::make_shared<DiffMapEntry>(words1, words2, i, k, opIndex, opLine);
+ } else {
+
explodeWords(*linediff[opIndex].from[opLine], words2);
+ tmp =
std::make_shared<DiffMapEntry>(words1, words2, opIndex, opLine, i, k);
+ }
+ if (!found || tmp->similarity >
found->similarity) {
+ found= tmp;
+ }
+ }
+ }
+ }
+
+ // if candidate exists:
+ // add candidate to moved-line-map twice, for add/del case
+ // print diff to the moved line, omitting the left/right side for
added/deleted line
+ if (found && found->similarity > 0.25) {
+ // if we displayed a diff to the found block before, don't
display this one as moved.
+ // XXXX does not work for the case where the block is moved "upwards"?
+ uint64_t otherKey = linediff[opIndex].op == DiffOp<String>::add
?
+ makeKey(found->opIndexFrom, found->opLineFrom) :
+ makeKey(found->opIndexTo, found->opLineTo);
+ if (diffMap.find(otherKey) != diffMap.end()) {
+ debugPrintf("printMovedLineDiff(..., %d, %d): not printing diff
again...", opIndex, opLine);
+ return false;
+ }
+
+ diffMap[key] = found;
+ uint64_t oppositeKey = makeKey(found->opIndexTo,
found->opLineTo);
+ diffMap[oppositeKey] = found;
+
+ bool printLeft = linediff[opIndex].op == DiffOp<String>::del ?
true : false;
+ bool printRight = !printLeft;
+ // XXXX todo: we already have the diff, don't have to do it
again, just have to print it
+
printWordDiff(*linediff[found->opIndexFrom].from[found->opLineFrom],
*linediff[found->opIndexTo].to[found->opLineTo],
+ printLeft, printRight);
+
+ debugPrintf("copy: %d, del: %d, add: %d, change: %d,
similarity: %.4f\n"
+ "from: (%d,%d) to: (%d,%d)\n",
+ found->opCharCount[DiffOp<Word>::copy],
found->opCharCount[DiffOp<Word>::del], found->opCharCount[DiffOp<Word>::add],
found->opCharCount[DiffOp<Word>::change], found->similarity,
+ found->opIndexFrom, found->opLineFrom,
found->opIndexTo, found->opLineTo);
+
+ return true;
+ }
+
+ return false;
+}
+
void Wikidiff2::debugPrintWordDiff(WordDiff & worddiff)
{
for (unsigned i = 0; i < worddiff.size(); ++i) {
diff --git a/Wikidiff2.h b/Wikidiff2.h
index da75e7b..1079930 100644
--- a/Wikidiff2.h
+++ b/Wikidiff2.h
@@ -14,6 +14,7 @@
#include <string>
#include <vector>
#include <set>
+#include <memory>
class Wikidiff2 {
public:
@@ -34,11 +35,24 @@
enum { MAX_WORD_LEVEL_DIFF_COMPLEXITY = 40000000 };
String result;
+ struct DiffMapEntry
+ {
+ WordDiff diff;
+ int opCharCount[4] = { 0 };
+ double similarity;
+ int opIndexFrom, opLineFrom, opIndexTo, opLineTo;
+
+ DiffMapEntry(WordVector& words1, WordVector& words2,
int opIndexFrom_, int opLineFrom_, int opIndexTo_, int opLineTo_);
+ };
+ // PhpAllocator can't be specialized for std::pair, so we're
using the standard allocator.
+ typedef std::map<uint64_t, std::shared_ptr<struct
Wikidiff2::DiffMapEntry> > DiffMap;
+ DiffMap diffMap;
+
virtual void diffLines(const StringVector & lines1, const
StringVector & lines2,
int numContextLines);
virtual void printAdd(const String & line) = 0;
virtual void printDelete(const String & line) = 0;
- virtual void printWordDiff(const String & text1, const String &
text2) = 0;
+ virtual void printWordDiff(const String & text1, const String &
text2, bool printLeft = true, bool printRight = true) = 0;
virtual void printBlockHeader(int leftLine, int rightLine) = 0;
virtual void printContext(const String & input) = 0;
@@ -52,6 +66,8 @@
void explodeWords(const String & text, WordVector &tokens);
void explodeLines(const String & text, StringVector &lines);
+
+ bool printMovedLineDiff(StringDiff & linediff, int opIndex, int
opLine);
};
inline bool Wikidiff2::isLetter(int ch)
@@ -83,4 +99,38 @@
return result;
}
+inline Wikidiff2::DiffMapEntry::DiffMapEntry(Wikidiff2::WordVector& words1,
Wikidiff2::WordVector& words2, int opIndexFrom_, int opLineFrom_, int
opIndexTo_, int opLineTo_):
+ diff(words1, words2, MAX_WORD_LEVEL_DIFF_COMPLEXITY),
+ opIndexFrom(opIndexFrom_), opLineFrom(opLineFrom_),
opIndexTo(opIndexTo_), opLineTo(opLineTo_)
+{
+ int charsTotal = 0;
+ for (int i = 0; i < diff.size(); ++i) {
+ int op = diff[i].op;
+ int charCount;
+ switch (diff[i].op) {
+ case DiffOp<Word>::del:
+ case DiffOp<Word>::copy:
+ charCount = diff[i].from.size();
+ break;
+ case DiffOp<Word>::add:
+ charCount = diff[i].to.size();
+ break;
+ case DiffOp<Word>::change:
+ charCount = std::max(diff[i].from.size(),
diff[i].to.size());
+ break;
+ }
+ opCharCount[op] += charCount;
+ charsTotal += charCount;
+ }
+ if (opCharCount[DiffOp<Word>::copy] == 0) {
+ similarity = 0.0;
+ } else {
+ if (charsTotal) {
+ similarity = double(opCharCount[DiffOp<Word>::copy]) /
charsTotal;
+ } else {
+ similarity = 0.0;
+ }
+ }
+}
+
#endif
diff --git a/config.m4 b/config.m4
index b848398..c9e2197 100644
--- a/config.m4
+++ b/config.m4
@@ -36,6 +36,6 @@
PHP_SUBST(WIKIDIFF2_SHARED_LIBADD)
AC_DEFINE(HAVE_WIKIDIFF2, 1, [ ])
- export CXXFLAGS="-Wno-write-strings $CXXFLAGS"
+ export CXXFLAGS="-Wno-write-strings -std=c++11 $CXXFLAGS"
PHP_NEW_EXTENSION(wikidiff2, php_wikidiff2.cpp Wikidiff2.cpp TableDiff.cpp
InlineDiff.cpp, $ext_shared)
fi
--
To view, visit https://gerrit.wikimedia.org/r/328685
To unsubscribe, visit https://gerrit.wikimedia.org/r/settings
Gerrit-MessageType: newchange
Gerrit-Change-Id: If6855bcddbfea47614130daedf21a3de43510fc4
Gerrit-PatchSet: 1
Gerrit-Project: mediawiki/php/wikidiff2
Gerrit-Branch: master
Gerrit-Owner: Jkroll <[email protected]>
_______________________________________________
MediaWiki-commits mailing list
[email protected]
https://lists.wikimedia.org/mailman/listinfo/mediawiki-commits
