Content deleted Content added
source -> syntaxhighlight |
1.0.0 (August 24, 2014) |
||
Line 1:
// <syntaxhighlight lang="JavaScript">
// @name wDiff
// @version 1.0.0
// @date August 24, 2014
// @description improved word-based diff library with block move detection
// @homepage https://en.wikipedia.org/wiki/User:Cacycle/diff
// @source https://en.wikipedia.org/wiki/User:Cacycle/diff.js
// @author Cacycle (https://en.wikipedia.org/wiki/User:Cacycle)
// @license released into the public ___domain
/*
Improved JavaScript diff library that returns html/css-formatted new text version with highlighted deletions, inserts, and block moves.
It is compatible with all browsers and is not dependent on external libraries.
An implementation of the word-based algorithm from:
Line 26 ⟶ 19:
http://doi.acm.org/10.1145/359460.359467
Additional features:
* Word (token) types have been optimized for MediaWiki source texts
* Stepwise token size refinement, starting with paragraphs, then sentences, words, and finally characters
* Additional post-pass
* Color coding of moved blocks and their marks at the original position
*
* Optional
* Fully customizable
* Well commented and documented code
This code is used by the MediaWiki in-browser text editors [[en:User:Cacycle/editor]] and [[en:User:Cacycle/wikEd]]
and the enhanced diff view tool wikEdDiff [[en:User:Cacycle/wikEd]].
Usage:
var diffHtml = wDiff.Diff(oldString, newString);
diffHtml = wDiff.ShortenOutput(diffHtml);
Datastructures (abbreviations from publication):
text:
.
.
.tokens[]: token data list for new or old string (N and O)
.prev: previous list item
.next: next list item
.token: token string
.link: index of corresponding token in new or old text (OA and NA)
.number: list enumeration number
.parsed: token has been added to symbol table
.first: index of first token in tokens list
.last: index of last token in tokens list
.diff: diff html
symbols[token]: associative array (hash) of parsed tokens for passes 1 - 3, points to symbol[i]
symbol[]: array of objects that hold token counters and pointers:
.newCount: new text token counter (NC)
.newToken: token index in text.new.tokens
blocks[]: array of objects that holds block (consecutive text tokens) data in order of the new text
.oldBlock: blocks.length, number of block in order of the old text
.
.
.
.type: 'same', 'del', 'ins'
.section: section number of block (for testing)
.group: group number of block
.
.string: string of block tokens
blockStart: first block index of group
words: word count of group
chars: char count of group
fixed: group is set to fixed (not moved)
moved[]: list of groups that have been moved from this position
movedFrom: position this group has been moved from
color: color number of moved group
diff: group diff
*/
// turn on ECMAScript 5 strict mode
'use strict';
if (typeof wDiff == 'undefined') { window.wDiff = {}; }
//
// css for core diff
//
if (typeof wDiff.styleContainer == 'undefined') { wDiff.styleContainer = ''; }
if (typeof wDiff.StyleDelete == 'undefined') { wDiff.styleDelete = 'font-weight: normal; text-decoration: none; color: #fff; background-color: #c33; border-radius: 0.25em; padding: 0.2em 1px;' }
if (typeof wDiff.styleInsert == 'undefined') { wDiff.styleInsert = 'font-weight: normal; text-decoration: none; color: #fff; background-color: #07e; border-radius: 0.25em; padding: 0.2em 1px;'; }
if (typeof wDiff.styleBlockLeft == 'undefined') { wDiff.styleBlockLeft = 'background-color: #d0d0d0; border-radius: 0.25em; padding: 0.25em 1px; margin: 0 1px;'; }
if (typeof wDiff.styleBlockRight == 'undefined') { wDiff.styleBlockRight = 'background-color: #d0d0d0; border-radius: 0.25em; padding: 0.25em 1px; margin: 0 1px;'; }
if (typeof wDiff.styleBlockColor == 'undefined') { wDiff.styleBlockColor = [
'
'
'background-color: #ffd8ff;',
'background-color: #a0ffff;',
'background-color: #ffe840;',
'background-color: #bbccff;',
'background-color: #ffaaff;',
'background-color: #ffbbbb;',
'background-color: #a0e8a0;'
]; }
if (typeof wDiff.styleMarkLeft == 'undefined') { wDiff.styleMarkLeft = 'color: #d0d0d0; background-color: #c33; border-radius: 0.25em; padding: 0.2em 0.2em; margin: 0 1px;'; }
if (typeof wDiff.styleMarkRight == 'undefined') { wDiff.styleMarkRight = 'color: #d0d0d0; background-color: #c33; border-radius: 0.25em; padding: 0.2em 0.2em; margin: 0 1px;'; }
if (typeof wDiff.styleMarkColor == 'undefined') { wDiff.styleMarkColor = [
'color: #ffff60;',
'color: #c0ff60;',
'color: #ffd8ff;',
'color: #a0ffff;',
'color: #ffd840;',
'color: #bbccff;',
'color: #ff99ff;',
'color: #ff9999;',
'color: #90d090;'
]; }
if (typeof wDiff.styleNewline == 'undefined') { wDiff.styleNewline = ''; }
if (typeof wDiff.styleTab == 'undefined') { wDiff.styleTab = ''; }
if (typeof wDiff.stylesheet == 'undefined') { wDiff.stylesheet = '.wDiffTab:before { content: "→"; color: #bbb; font-size: smaller; } .wDiffNewline:before { content: "¶"; color: #ccc; padding: 0.2em; } .wDiffMarkRight:before { content: "▶"; } .wDiffMarkLeft:before { content: "◀"; }' }
//
// css for shorten output
//
if (typeof wDiff.styleFragment == 'undefined') { wDiff.styleFragment = 'white-space: pre-wrap; background: #fcfcfc; border: #bbb solid; border-width: 1px 1px 1px 0.5em; border-radius: 0.5em; font-family: inherit; font-size: 88%; line-height: 1.6; box-shadow: 2px 2px 2px #ddd; padding: 1em; margin: 0;'; }
if (typeof wDiff.styleNoChange == 'undefined') { wDiff.styleNoChange = 'white-space: pre-wrap; background: #f0f0f0; border: #bbb solid; border-width: 1px 1px 1px 0.5em; border-radius: 0.5em; font-family: inherit; font-size: 88%; line-height: 1.6; box-shadow: 2px 2px 2px #ddd; padding: 0.5em; margin: 1em 0;'; }
if (typeof wDiff.styleSeparator == 'undefined') { wDiff.styleSeparator = 'margin-bottom: 1em;'; }
if (typeof wDiff.styleOmittedChars == 'undefined') { wDiff.styleOmittedChars = ''; }
//
// html for core diff,
//
// {block} and {mark} are replaced by block number color style, {title} is replaced by title attribute (popup)
// class plus html comment are required indicators for wDiff.ShortenOutput()
if (typeof wDiff.htmlContainerStart == 'undefined') { wDiff.htmlContainerStart = '<div class="wDiffContainer" style="' + wDiff.styleContainer + '">'; }
if (typeof wDiff.htmlContainerEnd == 'undefined') { wDiff.htmlContainerEnd = '</div>'; }
if (typeof wDiff.htmlDeleteStart == 'undefined') { wDiff.htmlDeleteStart = '<span class="wDiffDelete" style="' + wDiff.styleDelete + '" title="−">'; }
if (typeof wDiff.htmlDeleteEnd == 'undefined') { wDiff.htmlDeleteEnd = '</span><!--wDiffDelete-->'; }
if (typeof wDiff.htmlInsertStart == 'undefined') { wDiff.htmlInsertStart = '<span class="wDiffInsert" style="' + wDiff.styleInsert + '" title="+">'; }
if (typeof wDiff.htmlInsertEnd == 'undefined') { wDiff.htmlInsertEnd = '</span><!--wDiffInsert-->'; }
if (typeof wDiff.htmlBlockLeftStart == 'undefined') { wDiff.htmlBlockLeftStart = '<span class="wDiffBlockLeft" style="' + wDiff.styleBlockLeft + ' {block}" title="▶ ▢">'; }
if (typeof wDiff.htmlBlockLeftEnd == 'undefined') { wDiff.htmlBlockLeftEnd = '</span><!--wDiffBlockLeft-->'; }
if (typeof wDiff.htmlBlockRightStart == 'undefined') { wDiff.htmlBlockRightStart = '<span class="wDiffBlockRight" style="' + wDiff.styleBlockRight + ' {block}" title="▭ ◀">'; }
if (typeof wDiff.htmlBlockRightEnd == 'undefined') { wDiff.htmlBlockRightEnd = '</span><!--wDiffBlockRight-->'; }
if (typeof wDiff.htmlMarkRight == 'undefined') { wDiff.htmlMarkRight = '<span class="wDiffMarkRight" style="' + wDiff.styleMarkRight + ' {mark}"{title}></span><!--wDiffMarkRight-->'; }
if (typeof wDiff.htmlMarkLeft == 'undefined') { wDiff.htmlMarkLeft = '<span class="wDiffMarkLeft" style="' + wDiff.styleMarkLeft + ' {mark}"{title}></span><!--wDiffMarkLeft-->'; }
if (typeof wDiff.htmlNewline == 'undefined') { wDiff.htmlNewline = '<span class="wDiffNewline" style="' + wDiff.styleNewline + '"></span>\n'; }
if (typeof wDiff.htmlTab == 'undefined') { wDiff.htmlTab = '<span class="wDiffTab" style="' + wDiff.styleTab + '">\t</span>'; }
//
// html for shorten output
//
if (typeof wDiff.htmlFragmentStart == 'undefined') { wDiff.htmlFragmentStart = '<pre class="wDiffFragment" style="' + wDiff.styleFragment + '">'; }
if (typeof wDiff.htmlFragmentEnd == 'undefined') { wDiff.htmlFragmentEnd = '</pre>'; }
if (typeof wDiff.htmlNoChange == 'undefined') { wDiff.htmlNoChange = '<pre class="wDiffFragment" style="' + wDiff.styleNoChange + '" title="="></pre>'; }
if (typeof wDiff.htmlSeparator == 'undefined') { wDiff.htmlSeparator = '<div class="wDiffStyleSeparator" style="' + wDiff.styleSeparator + '"></div>'; }
if (typeof wDiff.htmlOmittedChars == 'undefined') { wDiff.htmlOmittedChars = '<span class="wDiffOmittedChars" style="' + wDiff.styleOmittedChars + '">…</span>'; }
//
// core diff settings
//
// enable block move layout with color coded blocks and marks at their original position
if (typeof
// minimal number of real words for a moved block (0 for always
if (typeof
// further resolve replacements character-wise from start and end
if (typeof
// enable recursive diff to resolve problematic sequences
if (typeof
// UniCode letter support for regexps, from http://xregexp.com/addons/unicode/unicode-base.js v1.0.0
wDiff.letters = 'a-zA-Z0-9' + '00AA00B500BA00C0-00D600D8-00F600F8-02C102C6-02D102E0-02E402EC02EE0370-037403760377037A-037D03860388-038A038C038E-03A103A3-03F503F7-0481048A-05270531-055605590561-058705D0-05EA05F0-05F20620-064A066E066F0671-06D306D506E506E606EE06EF06FA-06FC06FF07100712-072F074D-07A507B107CA-07EA07F407F507FA0800-0815081A082408280840-085808A008A2-08AC0904-0939093D09500958-09610971-09770979-097F0985-098C098F09900993-09A809AA-09B009B209B6-09B909BD09CE09DC09DD09DF-09E109F009F10A05-0A0A0A0F0A100A13-0A280A2A-0A300A320A330A350A360A380A390A59-0A5C0A5E0A72-0A740A85-0A8D0A8F-0A910A93-0AA80AAA-0AB00AB20AB30AB5-0AB90ABD0AD00AE00AE10B05-0B0C0B0F0B100B13-0B280B2A-0B300B320B330B35-0B390B3D0B5C0B5D0B5F-0B610B710B830B85-0B8A0B8E-0B900B92-0B950B990B9A0B9C0B9E0B9F0BA30BA40BA8-0BAA0BAE-0BB90BD00C05-0C0C0C0E-0C100C12-0C280C2A-0C330C35-0C390C3D0C580C590C600C610C85-0C8C0C8E-0C900C92-0CA80CAA-0CB30CB5-0CB90CBD0CDE0CE00CE10CF10CF20D05-0D0C0D0E-0D100D12-0D3A0D3D0D4E0D600D610D7A-0D7F0D85-0D960D9A-0DB10DB3-0DBB0DBD0DC0-0DC60E01-0E300E320E330E40-0E460E810E820E840E870E880E8A0E8D0E94-0E970E99-0E9F0EA1-0EA30EA50EA70EAA0EAB0EAD-0EB00EB20EB30EBD0EC0-0EC40EC60EDC-0EDF0F000F40-0F470F49-0F6C0F88-0F8C1000-102A103F1050-1055105A-105D106110651066106E-10701075-1081108E10A0-10C510C710CD10D0-10FA10FC-1248124A-124D1250-12561258125A-125D1260-1288128A-128D1290-12B012B2-12B512B8-12BE12C012C2-12C512C8-12D612D8-13101312-13151318-135A1380-138F13A0-13F41401-166C166F-167F1681-169A16A0-16EA1700-170C170E-17111720-17311740-17511760-176C176E-17701780-17B317D717DC1820-18771880-18A818AA18B0-18F51900-191C1950-196D1970-19741980-19AB19C1-19C71A00-1A161A20-1A541AA71B05-1B331B45-1B4B1B83-1BA01BAE1BAF1BBA-1BE51C00-1C231C4D-1C4F1C5A-1C7D1CE9-1CEC1CEE-1CF11CF51CF61D00-1DBF1E00-1F151F18-1F1D1F20-1F451F48-1F4D1F50-1F571F591F5B1F5D1F5F-1F7D1F80-1FB41FB6-1FBC1FBE1FC2-1FC41FC6-1FCC1FD0-1FD31FD6-1FDB1FE0-1FEC1FF2-1FF41FF6-1FFC2071207F2090-209C21022107210A-211321152119-211D212421262128212A-212D212F-2139213C-213F2145-2149214E218321842C00-2C2E2C30-2C5E2C60-2CE42CEB-2CEE2CF22CF32D00-2D252D272D2D2D30-2D672D6F2D80-2D962DA0-2DA62DA8-2DAE2DB0-2DB62DB8-2DBE2DC0-2DC62DC8-2DCE2DD0-2DD62DD8-2DDE2E2F300530063031-3035303B303C3041-3096309D-309F30A1-30FA30FC-30FF3105-312D3131-318E31A0-31BA31F0-31FF3400-4DB54E00-9FCCA000-A48CA4D0-A4FDA500-A60CA610-A61FA62AA62BA640-A66EA67F-A697A6A0-A6E5A717-A71FA722-A788A78B-A78EA790-A793A7A0-A7AAA7F8-A801A803-A805A807-A80AA80C-A822A840-A873A882-A8B3A8F2-A8F7A8FBA90A-A925A930-A946A960-A97CA984-A9B2A9CFAA00-AA28AA40-AA42AA44-AA4BAA60-AA76AA7AAA80-AAAFAAB1AAB5AAB6AAB9-AABDAAC0AAC2AADB-AADDAAE0-AAEAAAF2-AAF4AB01-AB06AB09-AB0EAB11-AB16AB20-AB26AB28-AB2EABC0-ABE2AC00-D7A3D7B0-D7C6D7CB-D7FBF900-FA6DFA70-FAD9FB00-FB06FB13-FB17FB1DFB1F-FB28FB2A-FB36FB38-FB3CFB3EFB40FB41FB43FB44FB46-FBB1FBD3-FD3DFD50-FD8FFD92-FDC7FDF0-FDFBFE70-FE74FE76-FEFCFF21-FF3AFF41-FF5AFF66-FFBEFFC2-FFC7FFCA-FFCFFFD2-FFD7FFDA-FFDC'.replace(/(\w{4})/g, '\\u$1');
// regExp for splitting into paragraphs after newline
wDiff.regExpParagraph = new RegExp('(.|\\n)+?(\\n|$)', 'g');
// regExp for splitting into sentences after .spaces or before newline
wDiff.regExpSentence = new RegExp('\\n|.*?\\.( +|(?=\\n))|.+?(?=\\n)', 'g');
// regExp for splitting into words, multi-char markup, and chars
wDiff.regExpWord = new RegExp('([' + wDiff.letters + '])+|\\[\\[|\\]\\]|\\{\\{|\\}\\}|&\\w+;|\'\'\'|\'\'|==+|\\{\\||\\|\\}|\\|-|.', 'g');
// regExp for splitting into chars
wDiff.regExpChar = new RegExp('[' + wDiff.letters + ']', 'g');
//
// shorten output settings
//
// characters before diff tag to search for previous heading, paragraph, line break, cut characters
if (typeof
if (typeof
if (typeof
if (typeof
if (typeof
if (typeof
if (typeof
// characters after diff tag to search for next heading, paragraph, line break, or characters
if (typeof
if (typeof
if (typeof
if (typeof
if (typeof
if (typeof
if (typeof
// maximal fragment distance to join close fragments
if (typeof
//
// wDiff.Init: initialize wDiff
// called from: on code load
// calls: wDiff.AddStyleSheet()
wDiff.Init = function() {
// compatibility fixes for old names of functions
window.StringDiff = wDiff.Diff;
window.WDiffString = wDiff.Diff;
window.WDiffShortenOutput = wDiff.ShortenOutput;
// shortcut to wikEd.Debug()
if (typeof WED != 'function') {
window.WED = console.log;
}
// add styles to head
wDiff.AddStyleSheet(wDiff.stylesheet);
return;
};
// wDiff.Diff: main method
// input: oldString, newString, strings containing the texts to be diffed
// called from: user code
// calls: wDiff.Split(), wDiff.SplitRefine(), wDiff.CalculateDiff(), wDiff.DetectBlocks(), wDiff.AssembleDiff()
// returns: diff html code, call wDiff.ShortenOutput() for shortening this output
wDiff.Diff = function(oldString, newString) {
var diff = '';
// IE / Mac fix
oldString = oldString.replace(/\r\n?/g, '\n');
newString = newString.replace(/\r\n?/g, '\n');
// prepare text data object
var text = {
new: {
string: newString,
tokens: [],
first: null,
last: null
},
old: {
string: oldString,
tokens: [],
first: null,
last: null
},
diff: ''
};
// trap trivial changes: no change
if (oldString == newString) {
text.diff = wDiff.HtmlEscape(newString)
wDiff.HtmlFormat(text);
return text.diff;
}
// trap trivial changes: old text deleted
if ( (
text.diff = wDiff.htmlInsertStart + wDiff.HtmlEscape(newString) + wDiff.htmlInsertEnd;
wDiff.HtmlFormat(text);
return text.diff;
}
// trap trivial changes: new text deleted
if ( (
text.diff = wDiff.htmlDeleteStart + wDiff.HtmlEscape(oldString) + wDiff.htmlDeleteEnd;
wDiff.HtmlFormat(text);
return text.diff;
}
// split new and old text into
wDiff.Split(text.new, wDiff.regExpParagraph);
wDiff.Split(text.old, wDiff.regExpParagraph);
// calculate diff
// refine different paragraphs into sentences
wDiff.SplitRefine(text.new, wDiff.regExpSentence);
wDiff.SplitRefine(text.old, wDiff.regExpSentence);
// calculate refined diff
wDiff.CalculateDiff(text);
// refine different sentences into words
wDiff.SplitRefine(text.new, wDiff.regExpWord);
wDiff.SplitRefine(text.old, wDiff.regExpWord);
// calculate refined diff information with recursion for unresolved gaps
wDiff.CalculateDiff(text, true);
// split tokens into chars in selected unresolved gaps
if (wDiff.charDiff == true) {
wDiff.SplitRefineChars(text);
// calculate refined diff information with recursion for unresolved gaps
wDiff.CalculateDiff(text, true);
}
// enumerate tokens lists
wDiff.EnumerateTokens(text.old);
// detect moved blocks
var blocks = [];
var groups = [];
wDiff.DetectBlocks(text, blocks, groups);
// assemble diff blocks into formatted html text
diff = wDiff.AssembleDiff(text, blocks, groups);
return
};
//
// input: text (text.new or text.old), object containing text data and strings; regExp, regular expression for splitting text into tokens; token, tokens index of token to be split
// changes: text (text.
// called from: wDiff.Diff()
var prev = null;
var next = null;
var current = text.tokens.length;
var first = current;
var string = '';
// split
if (token == null) {
string = text.string;
}
else {
prev = text.tokens[token].prev;
next = text.tokens[token].next;
string = text.tokens[token].token;
}
// split text into tokens
var number = 0;
var
while ( (regExpMatch = regExp.exec(string)) != null) {
// insert current item, link to previous
token: regExpMatch[0],
prev: prev,
next: null,
link: null,
number: null,
parsed: false,
};
number ++;
// link previous item to current
if (prev != null) {
text.tokens[prev].next = current;
}
prev = current;
current ++;
}
//
if ( (number > 0) && (token != null) ) {
if (prev != null) {
text.tokens[prev].next = next;
}
text.tokens[next].prev = prev;
}
}
// set text first and last token index
if (number > 0) {
// initial text split
if (token == null) {
text.first = 0;
text.last = prev;
}
// first or last token has been split
else {
if (token == text.first) {
text.first = first;
}
if (token == text.last) {
text.last = prev;
}
}
}
return;
};
// wDiff.SplitRefine: split unique unmatched tokens into smaller tokens
// changes: text (text.new or text.old) .tokens list
// called from: wDiff.Diff()
// calls: wDiff.Split()
// cycle through tokens list
var
while ( (i != null) && (text.tokens[i] != null) ) {
// refine unique unmatched tokens into smaller tokens
if (text.tokens[i].link == null) {
wDiff.Split(text, regExp, i);
}
i = text.tokens[i].next;
}
return;
};
// wDiff.SplitRefineChars: split tokens into chars in the following unresolved regions (gaps):
// - one token became separated by space, dash, or any string
// - same number of tokens in gap and strong similarity of all tokens:
// - addition or deletion of flanking strings in tokens
// - addition or deletion of internal string in tokens
// - same length and at least 50 % identity
// - same start or end, same text longer than different text
// - same length and at least 50 % identity
// identical tokens including space separators will be linked, resulting in word-wise char-level diffs
// changes: text (text.new or text.old) .tokens list
// called from: wDiff.Diff()
// calls: wDiff.Split()
// steps:
// find corresponding gaps
// select gaps of identical token number and strong similarity in all tokens
// refine words into chars in selected gaps
wDiff.SplitRefineChars = function(text) {
//
// find corresponding gaps
//
// cycle trough new text tokens list
var gaps = [];
var gap = null;
var i = text.new.first;
var j = text.old.first;
while ( (i != null) && (text.new.tokens[i] != null) ) {
// get list item properties
var newLink = text.new.tokens[i].link;
var oldLink = null;
if (j != null) {
oldLink = text.old.tokens[j].link;
}
// start of gap in new and old
if ( (gap == null) && (newLink == null) && (oldLink == null) ) {
gap = gaps.length;
gaps.push({
newFirst: i,
newLast: i,
newTokens: 1,
oldFirst: j,
oldLast: j,
oldTokens: null,
charSplit: null
});
}
// count chars and tokens in gap
else if ( (gap != null) && (newLink == null) ) {
gaps[gap].newLast = i;
gaps[gap].newTokens ++;
}
// gap ended
else if ( (gap != null) && (newLink != null) ) {
gap = null;
}
// next list elements
if (newLink != null) {
j = text.old.tokens[newLink].next;
}
i = text.new.tokens[i].next;
}
// cycle trough gaps and add old text gap data
for (var gap = 0; gap < gaps.length; gap ++) {
// cycle trough old text tokens list
var
while ( (j != null) && (text.old.tokens[j] != null) && (text.old.tokens[j].link == null) ) {
// count old chars and tokens in gap
gaps[gap].oldLast = j;
gaps[gap].oldTokens ++;
j = text.old.tokens[j].next;
}
}
//
// select gaps of identical token number and strong similarity of all tokens
//
for (var gap = 0; gap < gaps.length; gap ++) {
var charSplit = true;
// not same gap length
if (gaps[gap].newTokens != gaps[gap].oldTokens) {
// one word became separated by space, dash, or any string
if ( (gaps[gap].newTokens == 1) && (gaps[gap].oldTokens == 3) ) {
if (text.new.tokens[ gaps[gap].newFirst ].token != text.old.tokens[ gaps[gap].oldFirst ].token + text.old.tokens[ gaps[gap].oldLast ].token ) {
continue;
}
}
else if ( (gaps[gap].oldTokens == 1) && (gaps[gap].newTokens == 3) ) {
if (text.old.tokens[ gaps[gap].oldFirst ].token != text.new.tokens[ gaps[gap].newFirst ].token + text.new.tokens[ gaps[gap].newLast ].token ) {
continue;
}
}
else {
continue;
}
}
// cycle trough new text tokens list and set charSplit
var i = gaps[gap].newFirst;
var j = gaps[gap].oldFirst;
while (i != null) {
var newToken = text.new.tokens[i].token;
var oldToken = text.old.tokens[j].token;
// get shorter and longer token
var
var longerToken;
if (newToken.length < oldToken.length) {
shorterToken = newToken;
longerToken = oldToken;
}
else {
shorterToken = oldToken;
longerToken = newToken;
}
// not same token length
if (newToken.length != oldToken.length) {
// test for addition or deletion of internal string in tokens
// find number of identical chars from left
var left = 0;
while (left < shorterToken.length) {
if (newToken.charAt(left) != oldToken.charAt(left)) {
break;
}
left ++;
}
// find number of identical chars from right
var right = 0;
while (right < shorterToken.length) {
if (newToken.charAt(newToken.length - 1 - right) != oldToken.charAt(oldToken.length - 1 - right)) {
break;
}
right ++;
}
// no simple insertion or deletion of internal string
if (left + right != shorterToken.length) {
// not addition or deletion of flanking strings in tokens (smaller token not part of larger token)
if (longerToken.indexOf(shorterToken) == -1) {
// same text at start or end shorter than different text
if ( (left < shorterToken.length / 2) && (right < shorterToken.length / 2) ) {
// do not split into chars this gap
charSplit = false;
break;
}
}
}
}
// same token length
else if (newToken != oldToken) {
// tokens less than 50 % identical
var ident = 0;
for (var pos = 0; pos < shorterToken.length; pos ++) {
if (shorterToken.charAt(pos) == longerToken.charAt(pos)) {
ident ++;
}
}
if (ident/shorterToken.length < 0.49) {
// do not split into chars this gap
charSplit = false;
break
}
}
// next list elements
if (i == gaps[gap].newLast) {
break;
}
i = text.new.tokens[i].next;
j = text.old.tokens[j].next;
}
gaps[gap].charSplit = charSplit;
}
//
// refine words into chars in selected gaps
//
for (var gap = 0; gap < gaps.length; gap ++) {
if (
// cycle trough new text tokens list
var i = gaps[gap].newFirst;
var j = gaps[gap].oldFirst;
while (i != null) {
var newToken = text.new.tokens[i].token;
var oldToken = text.old.tokens[j].token;
// link identical tokens (spaces)
if (newToken == oldToken) {
text.new.tokens[i].link = j;
text.old.tokens[j].link = i;
}
// refine different words into chars
else {
wDiff.Split(text.new, wDiff.regExpChar, i);
wDiff.Split(text.old, wDiff.regExpChar, j);
}
// next list elements
if (i == gaps[gap].newLast) {
break;
}
i = text.new.tokens[i].next;
j = text.old.tokens[j].next;
}
}
}
// WED('Gap', wDiff.DebugGaps(gaps));
return;
};
// wDiff.EnumerateTokens: enumerate text token list
// changes: text (text.new or text.old) .tokens list
// called from: wDiff.Diff()
wDiff.EnumerateTokens = function(text) {
// enumerate tokens list
var number = 0;
var i = text.first;
while ( (i != null) && (text.tokens[i] != null) ) {
text.tokens[i].number = number;
number ++;
i = text.tokens[i].next;
}
return;
};
// wDiff.CalculateDiff: calculate diff information, can be called repeatedly during refining
// input: text, object containing text data and tokens
// optionally for recursive calls: newStart, newEnd, oldStart, oldEnd (tokens list indexes), recursionLevel
// changes: text.old/new.tokens[].link, links corresponding tokens from old and new text
// steps:
// pass 1: parse new text into symbol table
// pass 2: parse old text into symbol table
// pass 3: connect unique tokens
// pass 4: connect adjacent identical tokens downwards
// pass 5: connect adjacent identical tokens upwards
// recursively diff still unresolved regions downwards
// recursively diff still unresolved regions upwards
wDiff.CalculateDiff = function(text, recurse, newStart, newEnd, oldStart, oldEnd, recursionLevel) {
// symbol (token) data
var symbol = [];
var symbols = {};
// set defaults
if (typeof newStart == 'undefined') { newStart = text.new.first; }
if (typeof newEnd == 'undefined') { newEnd = text.new.last; }
if (typeof oldStart == 'undefined') { oldStart = text.old.first; }
if (typeof oldEnd == 'undefined') { oldEnd = text.old.last; }
if (typeof recursionLevel == 'undefined') { recursionLevel = 0; }
// limit recursion depth
if (recursionLevel > 10) {
return;
}
//
// pass 1: parse new text into symbol table
//
// cycle trough new text tokens list
var i = newStart;
while ( (i != null) && (text.new.tokens[i] != null) ) {
// parse token only once during split refinement
if ( (text.new.tokens[i].parsed == false) || (recursionLevel > 0) ) {
text.new.tokens[i].parsed = true;
// add new entry to symbol table
var token = text.new.tokens[i].token;
if (Object.prototype.hasOwnProperty.call(symbols, token) == false) {
var current = symbol.length;
symbols[token] = current;
symbol[current] = {
newCount: 1,
oldCount: 0,
newToken: i,
oldToken: null
};
}
// or update existing entry
else {
// increment token counter for new text
var hashToArray = symbols[token];
symbol[hashToArray].newCount ++;
}
}
// next list element
if (i == newEnd) {
break;
}
i = text.new.tokens[i].next;
}
//
// pass 2: parse old text into symbol table
//
//
var j = oldStart;
while ( (j != null) && (text.old.tokens[j] != null) ) {
// parse token only once during split refinement
if ( (text.old.tokens[j].parsed == false) || (recursionLevel > 0) ) {
text.old.tokens[j].parsed = true;
// add new entry to symbol table
var token = text.old.tokens[j].token;
if (Object.prototype.hasOwnProperty.call(symbols, token) == false) {
var current = symbol.length;
symbols[token] = current;
symbol[current] = {
newCount: 0,
oldCount: 1,
newToken: null,
oldToken: j
};
}
// or update existing entry
else {
// increment token counter for old text
var hashToArray = symbols[token];
symbol[hashToArray].oldCount ++;
// add token number for old text
symbol[hashToArray].oldToken = j;
}
}
// next list element
if (j == oldEnd) {
break;
}
j = text.old.tokens[j].next;
}
//
// pass 3: connect unique
//
// cycle trough symbol array
for (var i = 0; i < symbol.length; i ++) {
// find
if ( (symbol[i].
var
var
// do not use spaces as unique markers
if (/^\s+$/.test(text.
// connect from new to old and from old to new
if (text.
text.
text.old.tokens[oldToken].link = newToken;
}
}
}
}
//
// pass 4: connect adjacent identical
//
// cycle trough new text tokens list
var i = text.new.first;
while ( (i != null) && (text.new.tokens[i] != null) ) {
var iNext = text.new.tokens[i].next;
// find already connected pairs
var j = text.new.tokens[i].link;
if (j != null) {
var jNext = text.old.tokens[j].next;
//
if ( (text.new.tokens[iNext].link == null) && (text.old.tokens[jNext].link == null) ) {
// connect if the following tokens are the same
if (text.new.tokens[iNext].token == text.old.tokens[jNext].token) {
text.new.tokens[iNext].link = jNext;
text.old.tokens[jNext].link = iNext;
}
}
}
}
i = iNext;
}
//
// pass 5: connect adjacent identical
//
// cycle trough new text tokens list
var i = text.new.last;
while ( (i != null) && (text.new.tokens[i] != null) ) {
var iNext = text.new.tokens[i].prev;
// find already connected pairs
var j = text.new.tokens[i].link;
if (j != null) {
var jNext = text.old.tokens[j].prev;
//
if ( (text.new.tokens[iNext].link == null) && (text.old.tokens[jNext].link == null) ) {
// connect if the preceeding tokens are the same
if (text.new.tokens[iNext].token == text.old.tokens[jNext].token) {
text.new.tokens[iNext].link = jNext;
text.old.tokens[jNext].link = iNext;
}
}
}
}
i = iNext;
}
// refine by recursively diffing unresolved regions caused by addition of common tokens around sequences of common tokens, only at word level split
if ( (recurse == true) && (wDiff.recursiveDiff == true) ) {
//
// recursively diff still unresolved regions downwards
//
// cycle trough new text tokens list
var i = newStart;
var j = oldStart;
while (
// get j from previous tokens match
var iPrev = text.new.tokens[i].prev;
if (iPrev != null) {
var jPrev = text.new.tokens[iPrev].link;
if (jPrev != null) {
j = text.old.tokens[jPrev].next;
}
}
// check for the start of an unresolved sequence
if ( (j != null) && (text.
// determine the
var iStart = i;
var iEnd =
var iLength = 0;
while ( (iNext != null) && (text.new.tokens[iNext].link == null) ) {
iEnd = iNext;
iLength ++;
if (iEnd == newEnd) {
break;
}
iNext = text.new.tokens[iNext].next;
}
// determine the limits of of the unresolved old sequence
var jStart = j;
var jEnd =
var jLength = 0;
while ( (jNext != null) && (text.old.tokens[jNext].link == null) ) {
jEnd = jNext;
jLength ++;
if (jEnd == oldEnd) {
break;
}
jNext = text.old.tokens[jNext].next;
}
// recursively diff the unresolved sequence
if ( (iLength > 0) && (jLength > 0) ) {
if ( (iLength > 1) || (jLength > 1) ) {
if ( (iStart != newStart) || (iEnd != newEnd) || (jStart != oldStart) || (jEnd != oldEnd) ) {
}
}
Line 428 ⟶ 972:
i = iEnd;
}
// next list element
if (i == newEnd) {
break;
}
i = text.new.tokens[i].next;
}
//
//
//
// cycle trough new text tokens list
var
while (
// get j from next matched tokens
var iPrev = text.new.tokens[i].next;
if (iPrev != null) {
var jPrev = text.new.tokens[iPrev].link;
if (jPrev != null) {
j = text.old.tokens[jPrev].prev;
}
}
// check for the start of an unresolved sequence
if ( (j != null) && (text.
// determine the
var iStart =
var iEnd = i
var iLength = 0;
while ( (iNext != null) && (text.new.tokens[iNext].link == null) ) {
iStart = iNext;
iLength ++;
if (iStart == newStart) {
break;
}
iNext = text.new.tokens[iNext].prev;
}
// determine the limits of of the unresolved old sequence
var
var jEnd = j;
while ( (jNext != null) && (text.old.tokens[jNext].link == null) ) {
jStart =
jLength ++;
if (jStart == oldStart) {
break;
}
jNext = text.old.tokens[jNext].prev;
}
// recursively diff the unresolved sequence
if ( (iLength > 0) && (jLength > 0) ) {
if ( (iLength > 1) || (jLength > 1) ) {
if ( (iStart != newStart) || (iEnd != newEnd) || (jStart != oldStart) || (jEnd != oldEnd) ) {
}
}
}
i = iStart
}
// next list element
if (i == newStart) {
break;
}
i = text.new.tokens[i].prev;
}
}
Line 488 ⟶ 1,051:
// wDiff.DetectBlocks: extract block data for inserted, deleted, or moved blocks from diff data in text object
// input:
// text: object containing text tokens list
// blocks: empty array for block data
// groups: empty array for group data
// changes: blocks, groups
// called from: wDiff.Diff()
// steps:
// collect identical corresponding ('same') blocks from old text
// sort blocks by new text token number
// collect groups of continuous old text blocks
// collect independent block sections (no old/new crosses outside section)
// find groups of continuous old text blocks
// set longest sequence of increasing groups in sections as fixed (not moved)
// collect insertion ('ins') blocks from new text
// collect deletion ('del') blocks from old text
// position 'del' blocks into new text order
// re-sort blocks by new text token number and update groups
// set group numbers of 'ins' and 'del' blocks inside existing groups
// add remaining 'ins' and 'del' blocks to groups
// mark original positions of moved groups
// set moved block colors
//
// scheme of blocks, sections, and groups (old block numbers):
// old: 1 2 3D4 5E6 7 8 9 10 11
// | ‾/-/_ X | >|< |
// new: 1 I 3D4 2 E6 5 N 7 10 9 8 11
// section: 0 0 0 1 1 2 2 2
// group: 0 10 111 2 33 4 11 5 6 7 8 9
// fixed: + +++ - ++ - + + - - +
// type: = + =-= = -= = + = = = = =
// WED('text.old', wDiff.DebugText(text.old));
// WED('text.new', wDiff.DebugText(text.new));
//
// collect identical corresponding ('same') blocks from old text
//
// cycle through
var j = text.old.first;
while (j != null) {
// detect 'del' blocks and remember for later
var delStart = j;
var delEnd = null;
var string = '';
while ( (j != null) && (text.old.tokens[j].link == null) ) {
string += text.old.tokens[j].token;
delEnd = j;
j = text.old.tokens[j].next;
}
// save old text 'del' block data
if (delEnd != null) {
deletions.push({
oldStart: delStart,
oldBlock: blocks.length,
string: string
});
}
// get 'same' block
if (j != null) {
i = text.old.tokens[j].link;
var iStart = i;
var jStart = j;
// detect matching blocks ('same')
var chars = 0;
var string = '';
while ( (i != null) && (j != null) && (text.old.tokens[j].link == i) ) {
var token = text.old.tokens[j].token;
chars += token.length;
string += token;
i = text.new.tokens[i].next;
j = text.old.tokens[j].next;
}
// save old text 'same' block
blocks.push({
oldBlock: blocks.length,
oldNumber: text.old.tokens[jStart].number,
newNumber: text.new.tokens[iStart].number,
chars: chars,
type: 'same',
section: null,
group: null,
fixed: null,
string: string
});
}
}
//
// sort blocks by new text token number
//
blocks.sort(function(a, b) {
return a.newNumber - b.newNumber;
});
//
// collect independent block sections (no old/new crosses outside section) for per-section determination of non-moving (fixed) groups
//
var sections = [];
// cycle through blocks
var nextSectionStart = 0;
for (var block = 0; block < blocks.length; block ++) {
var sectionStart = block;
var sectionEnd = block;
var oldMax = blocks[sectionStart].oldNumber;
var sectionOldMax = oldMax;
// check right
for (var j = sectionStart + 1; j < blocks.length; j ++) {
// check for crossing over to the left
if (blocks[j].oldNumber > oldMax) {
oldMax = blocks[j].oldNumber;
}
else if (blocks[j].oldNumber < sectionOldMax) {
sectionEnd = j;
sectionOldMax = oldMax;
}
}
// save crossing sections
if (
// save section to block
for (var i = sectionStart; i <= sectionEnd; i ++) {
blocks[i].section = sections.length;
}
// save section
sections.push({
blockStart: sectionStart,
blockEnd: sectionEnd,
});
block = sectionEnd;
}
}
//
// find groups of continuous old text blocks
//
var regExpWordCount = new RegExp('(^|[^' + wDiff.letters + '])[' + wDiff.letters + '][' + wDiff.letters + '_\'’]*', 'g');
// cycle through blocks
for (var block = 0; block < blocks.length; block ++) {
var groupEnd = null;
// get word and char count of block
var words = (blocks[block].string.match(regExpWordCount) || []).length;
var maxWords = words;
var chars = blocks[block].chars;
groupStart = block;
groupEnd = block;
var oldBlock = blocks[groupStart].oldBlock;
// check right
for (var i = groupEnd + 1; i < blocks.length; i ++) {
// check for crossing over to the left
if (blocks[i].oldBlock != oldBlock + 1) {
break;
}
oldBlock = blocks[i].oldBlock;
// get word and char count of block
var blockWords = (blocks[i].string.match(regExpWordCount) || []).length;
maxWords = blockWords;
}
words += blockWords;
chars += blocks[i].chars;
// skip trailing 'del'
groupEnd = i;
}
// save crossing groups
// set groups outside sections as fixed
var fixed = false;
if (blocks[groupStart].section == null) {
fixed = true;
}
// save group to block
for (var i = groupStart; i <= groupEnd; i ++) {
blocks[i].group = groups.length;
blocks[i].fixed = fixed;
}
groups.push({
oldNumber: blocks[groupStart].oldNumber,
blockStart: groupStart,
blockEnd: groupEnd,
words: words,
maxWords: maxWords,
chars: chars,
fixed: fixed,
moved: [],
movedFrom: null,
color: null,
diff: ''
});
block = groupEnd;
}
}
//
// set longest sequence of increasing groups in sections as fixed (not moved)
//
// cycle through sections
for (var section = 0; section < sections.length; section ++) {
var blockStart = sections[section].blockStart;
var blockEnd = sections[section].blockEnd;
var groupStart = blocks[blockStart].group;
var groupEnd = blocks[blockEnd].group;
// recusively find path of groups in increasing old group order with longest char length
// start at each group of section
var cache = [];
var maxChars = 0;
var maxPath = null;
for (var i = groupStart; i <= groupEnd; i ++) {
var pathObj = wDiff.FindMaxPath(i, [], 0, cache, groups, groupEnd);
if (pathObj.chars > maxChars) {
maxPath = pathObj.path;
maxChars = pathObj.chars
}
}
// mark fixed groups
groups[group].fixed = true
// mark fixed blocks
for (var block = groups[group].blockStart; block <= groups[group].blockEnd; block ++) {
blocks[block].fixed = true;
}
}
}
//
// collect insertion ('ins') blocks from new text
//
// cycle through new text to find insertion blocks
var i = text.new.first;
while (i != null) {
// jump over linked (matched) block
i = text.new.tokens[i].next;
}
// detect insertion blocks ('ins')
if (i != null) {
var iStart = i;
var string = '';
while ( (i != null) && (text.new.tokens[i].link == null) ) {
string += text.new.tokens[i].token;
i = text.new.tokens[i].next;
}
// save new text 'ins' block
blocks.push({
oldBlock: null,
oldNumber: null,
newNumber: text.new.tokens[iStart].number,
chars: null,
type: 'ins',
section: null,
group: null,
fixed: null,
string: string
});
}
}
//
// collect deletion ('del') blocks from old text
//
// cycle through 'del' blocks and hash oldBlock indexes
var oldBlocks = [];
for (var block = 0; block < blocks.length; block ++) {
oldBlocks[ blocks[block].oldBlock ] = block;
}
// cycle through deletions detected earlier
for (var del = 0; del < deletions.length; del ++) {
var newNumber = 0;
var oldBlock = deletions[del].oldBlock;
//
var nextBlock = oldBlocks[oldBlock];
// get old text prev block
if (oldBlock > 0) {
prevBlock = oldBlocks[oldBlock - 1];
}
//
// position 'del' blocks into new text order
//
// deletion blocks move with fixed neighbor (new number +/- 0.3):
// old: 1 D 2 1 D 2
// / / \ ‾/-/_
// new: 1 D 2 D 2 1
// fixed: * *
// new number: 1 1.3 1.7 2
// move direction important for general del-ins order
// move after prev block if fixed
var neighbor = null;
if ( (prevBlock != null) && (blocks[prevBlock].fixed == true) ) {
neighbor = blocks[prevBlock];
newNumber = neighbor.newNumber + 0.3;
}
// move before next block if fixed
else if ( (nextBlock != null) && (blocks[nextBlock].fixed == true) ) {
neighbor = blocks[nextBlock];
newNumber = neighbor.newNumber - 0.3;
}
// move after prev block if existent
else if (
neighbor = blocks[prevBlock];
newNumber = neighbor.newNumber + 0.3;
}
// move before next block
else if (nextBlock != null) {
neighbor = blocks[nextBlock];
newNumber = neighbor.newNumber - 0.3;
}
// move before first block
else {
newNumber = -0.3;
}
// get neighbor data
var section = null;
var group = null;
var fixed = null;
if (neighbor != null) {
section = neighbor.section;
group = neighbor.group;
fixed = neighbor.fixed;
}
// save old text 'del' block
blocks.push({
oldBlock: null,
oldNumber: text.old.tokens[ deletions[del].oldStart ].number,
newNumber: newNumber,
chars: null,
type: 'del',
section: section,
group: group,
fixed: fixed,
string: deletions[del].string
});
}
//
// re-sort blocks by new text token number and update groups
//
// sort by newNumber
blocks.sort(function(a, b) {
return a.newNumber - b.newNumber;
});
// cycle through blocks and update groups with new block numbers
var group = null;
for (var block = 0; block < blocks.length; block ++) {
var blockGroup = blocks[block].group;
if (blockGroup != null) {
if (blockGroup != group) {
group = blocks[block].group;
groups[group].blockStart = block;
groups[group].oldNumber = blocks[block].oldNumber;
}
groups[blockGroup].blockEnd = block
}
}
//
// set group numbers of 'ins' and 'del' blocks inside existing groups
//
for (var group = 0; group < groups.length; group ++) {
var fixed = groups[group].fixed;
for (var block = groups[group].blockStart; block <= groups[group].blockEnd; block ++) {
if (blocks[block].group == null) {
blocks[block].group = group;
blocks[block].fixed = fixed;
}
}
}
//
// add remaining 'ins' and 'del' blocks to groups
//
// cycle through blocks
// skip existing groups
if (blocks[block].group == null) {
blocks[block].group = groups.length;
var fixed = blocks[block].fixed;
// save group
groups.push({
oldNumber: blocks[block].oldNumber,
blockStart: block,
blockEnd: block,
maxWords: null,
words: null,
chars: null,
fixed: fixed,
moved: [],
movedFrom: null,
color: null,
diff: ''
});
}
}
//
// mark original positions of moved groups
//
// moved block marks at original positions relative to fixed groups:
// groups: 3 7
// 1 <| | (no next smaller fixed)
// 5 |< |
// |> 5 |
// | 5 <|
// | >| 5
// | |> 9 (no next larger fixed)
// fixed: * *
// mark direction: groups[movedGroup].blockStart < groups[group].blockStart
// group side: groups[movedGroup].oldNumber < groups[group].oldNumber
// cycle through groups (moved group)
for (var movedGroup = 0; movedGroup < groups.length; movedGroup ++) {
if (groups[movedGroup].fixed != false) {
continue;
}
var movedOldNumber = groups[movedGroup].oldNumber;
// find closest fixed groups
var nextSmallerNumber = null;
var nextSmallerGroup = null;
var nextLargerNumber = null;
var nextLargerGroup = null;
// cycle through groups (original positions)
for (var group = 0; group < groups.length; group ++) {
if ( (groups[group].fixed != true) || (group == movedGroup) ) {
continue;
}
// find fixed group with closest smaller oldNumber
var oldNumber = groups[group].oldNumber;
if ( (oldNumber < movedOldNumber) && ( (nextSmallerNumber == null) || (oldNumber > nextSmallerNumber) ) ) {
nextSmallerNumber = oldNumber;
nextSmallerGroup = group;
}
// find fixed group with closest larger oldNumber
if ( (oldNumber > movedOldNumber) && ( (nextLargerNumber == null) || (oldNumber < nextLargerNumber) ) ) {
nextLargerNumber = oldNumber;
nextLargerGroup = group;
}
}
// no larger fixed group, moved right
var movedFrom = '';
if (nextLargerGroup == null) {
movedFrom = 'left';
}
// no smaller fixed group, moved right
else if (nextSmallerGroup == null) {
movedFrom = 'right';
}
// group moved from between two closest fixed neighbors, moved left or right depending on char distance
else {
var rightChars = 0;
for (var group = nextSmallerGroup + 1; group < movedGroup; group ++) {
rightChars += groups[group].chars;
}
var leftChars = 0;
for (var group = movedGroup + 1; group < nextLargerGroup; group ++) {
leftChars += groups[group].chars;
}
// moved right
if (rightChars <= leftChars) {
movedFrom = 'left';
}
// moved left
else {
movedFrom = 'right';
}
}
// check for null-moves
if (movedFrom == 'left') {
if (groups[nextSmallerGroup].blockEnd + 1 != groups[movedGroup].blockStart) {
groups[nextSmallerGroup].moved.push(movedGroup);
groups[movedGroup].movedFrom = nextSmallerGroup;
}
}
else if (movedFrom == 'right') {
if (groups[movedGroup].blockEnd + 1 != groups[nextLargerGroup].blockStart) {
groups[nextLargerGroup].moved.push(movedGroup);
groups[movedGroup].movedFrom = nextLargerGroup;
}
}
}
//
// set moved block colors
//
// cycle through groups
var moved = [];
for (var group = 0; group < groups.length; group ++) {
moved = moved.concat(groups[group].moved);
}
// sort moved array by old number
moved.sort(function(a, b) {
return groups[a].oldNumber - groups[b].oldNumber;
});
// set color
var color = 0;
for (var i = 0; i < moved.length; i ++) {
var movedGroup = moved[i];
if ( (groups[movedGroup].maxWords >= wDiff.blockMinLength) && (wDiff.showBlockMoves == true) ) {
groups[movedGroup].color = color;
color ++;
}
}
// WED('Deletions', wDiff.DebugDeletions(deletions));
// WED('Groups', wDiff.DebugGroups(groups));
// WED('Blocks', wDiff.DebugBlocks(blocks));
return;
};
// wDiff.FindMaxPath: recusively find path of groups in increasing old group order with longest char length
// input: start, path start group; path, array of path groups; chars, char count of path; cache, cached sub-path lengths; groups, groups, group object; groupEnd, last group
// returns: returnObj, contains path and length
// called from: wDiff.DetectBlocks()
// calls: itself recursively
wDiff.FindMaxPath = function(start, path, chars, cache, groups, groupEnd) {
// add current path point
var pathLocal = path.slice();
pathLocal.push(start);
chars = chars + groups[start].chars;
// last group, terminate recursion
var returnObj = { path: pathLocal, chars: chars };
if (i == groupEnd) {
return returnObj;
}
// find longest sub-path
var maxChars = 0;
var oldNumber = groups[start].oldNumber;
for (var i = start + 1; i <= groupEnd; i ++) {
// only in increasing old group order
if (groups[i].oldNumber < oldNumber) {
continue;
}
// get longest sub-path from cache
if (cache[start] != null) {
returnObj = cache[start];
}
// get longest sub-path by recursion
else {
var pathObj = wDiff.FindMaxPath(i, pathLocal, chars, cache, groups, groupEnd);
// select longest sub-path
if (pathObj.chars > maxChars) {
returnObj = pathObj;
}
}
}
// save longest path to cache
if (cache[i] == null) {
cache[start] = returnObj;
}
return returnObj;
};
// wDiff.AssembleDiff: process diff data into formatted html text
// input: text, object containing text tokens list; blocks, array containing block type; groups, array containing fixed (not moved), color, and moved mark data
// returns: diff html string
// called from: wDiff.Diff()
// calls: wDiff.HtmlCustomize(), wDiff.HtmlFormat()
//
// create group diffs
//
// cycle through groups
for (var group = 0; group < groups.length; group ++) {
var fixed = groups[group].fixed;
var color = groups[group].color;
var blockStart = groups[group].blockStart;
var blockEnd = groups[group].blockEnd;
var diff = '';
//
var blockFrom = null;
if ( (fixed == false) && (color != null) ) {
if (groups[ groups[group].movedFrom ].blockStart < blockStart) {
blockFrom = 'left';
}
else {
blockFrom = 'right';
}
}
//
if (blockFrom == 'left') {
diff += wDiff.HtmlCustomize(wDiff.htmlBlockLeftStart, color);
}
else if (blockFrom == 'right') {
diff += wDiff.HtmlCustomize(wDiff.htmlBlockRightStart, color);
}
// cycle through blocks
for (var block = blockStart; block <= blockEnd; block ++) {
var type = blocks[block].type;
var string = blocks[block].string;
// html escape text string
string = wDiff.HtmlEscape(string);
// moved block too small, make it an insertion and place it as a deletion at its original position
if ( ( (groups[group].maxWords < wDiff.blockMinLength) || (wDiff.showBlockMoves == false) ) && (fixed == false) ) {
if (type != 'del') {
string = string.replace(/\n/g, wDiff.htmlNewline);
diff += wDiff.htmlInsertStart + string + wDiff.htmlInsertEnd;
}
}
// add 'same' (unchanged) text
else if (type == 'same') {
diff += string;
}
// add 'del' text
else if (type == 'del') {
string = string.replace(/\n/g, wDiff.htmlNewline);
diff += wDiff.htmlDeleteStart + string + wDiff.htmlDeleteEnd;
}
// add 'ins' text
else if (type == 'ins') {
string = string.replace(/\n/g, wDiff.htmlNewline);
diff += wDiff.htmlInsertStart + string + wDiff.htmlInsertEnd;
}
}
//
if (blockFrom == 'left') {
diff += wDiff.htmlBlockLeftEnd;
}
else if (blockFrom == 'right') {
diff += wDiff.htmlBlockRightEnd;
}
groups[group].diff = diff;
}
//
// mark original block positions
//
// cycle through groups
for (var group = 0; group < groups.length; group ++) {
var moved = groups[group].moved;
// cycle through list of groups moved from here
var leftMarks = '';
var rightMarks = '';
for (var i = 0; i < moved.length; i ++) {
var movedGroup = moved[i];
var markColor = groups[movedGroup].color
var mark = '';
// get moved block text
var movedText = '';
for (var block = groups[movedGroup].blockStart; block <= groups[movedGroup].blockEnd; block ++) {
if (blocks[block].type != 'ins') {
movedText += blocks[block].string;
}
}
// moved block too small, make it a deletion at its original position
if ( (groups[movedGroup].words < wDiff.blockMinLength) || (wDiff.showBlockMoves == false) ) {
mark = wDiff.htmlDeleteStart + wDiff.HtmlEscape(movedText) + wDiff.htmlDeleteEnd;
}
// get mark direction
else {
if (groups[movedGroup].blockStart < groups[group].blockStart) {
mark = wDiff.htmlMarkLeft;
}
else {
mark = wDiff.htmlMarkRight;
}
mark = wDiff.HtmlCustomize(mark, markColor, movedText);
}
// get side of group to mark
if (groups[movedGroup].oldNumber < groups[group].oldNumber) {
leftMarks += mark;
}
else {
rightMarks += mark;
}
}
groups[group].diff = leftMarks + groups[group].diff + rightMarks;
}
//
// join diffs
//
// make shallow copy of groups and sort by blockStart
var groupsSort = groups.slice();
groupsSort.sort(function(a, b) {
return a.blockStart - b.blockStart;
});
// cycle through sorted groups and assemble diffs
for (var group = 0; group < groupsSort.length; group ++) {
text.diff += groupsSort[group].diff;
}
// WED('Groups', wDiff.DebugGroups(groups));
// keep newlines and multiple spaces
wDiff.HtmlFormat(text);
// WED('text.diff', text.diff);
return text.diff;
};
//
// wDiff.HtmlCustomize: customize move indicator html: replace {block} with block style, {mark} with mark style, and {title} with title attribute
// input: text (html or css code)
// returns: customized text
// called from: wDiff.AssembleDiff()
wDiff.HtmlCustomize = function(text, number, title) {
text = text.replace(/\{block\}/, wDiff.styleBlockColor[number] || '');
text = text.replace(/\{mark\}/, wDiff.styleMarkColor[number] || '');
// shorten title text, replace {title}
if ( (title != null) && (title != '') ) {
var max = 512;
var end = 128;
var gapMark = ' [...] ';
if (title.length > max) {
title = title.substr(0, max - gapMark.length - end) + gapMark + title.substr(title.length - end);
}
title = wDiff.HtmlEscape(title);
title = title.replace(/\t/g, ' ');
title = title.replace(/ /g, ' ');
text = text.replace(/\{title\}/, ' title="' + title + '"');
}
return text;
};
//
// wDiff.HtmlEscape: replace html-sensitive characters in output text with character entities
// input: text
// returns: escaped text
// called from: wDiff.Diff(), wDiff.AssembleDiff()
wDiff.HtmlEscape = function(text) {
text = text.replace(/&/g, '&');
text = text.replace(/</g, '<');
text = text.replace(/>/g, '>');
text = text.replace(/"/g, '"');
return (text);
};
//
// wDiff.HtmlFormat: tidy html, keep newlines and multiple spaces, add container
// changes: text.diff
// called from: wDiff.Diff(), wDiff.AssembleDiff()
wDiff.HtmlFormat = function(text) {
text.diff = text.diff.replace(/<\/(\w+)><!--wDiff(Delete|Insert)--><\1\b[^>]*\bclass="wDiff\2"[^>]*>/g, '');
text.diff = text.diff.replace(/\t/g, wDiff.htmlTab);
text.diff = wDiff.htmlContainerStart + text.diff + wDiff.htmlContainerEnd;
return;
};
// wDiff.ShortenOutput: shorten diff html by removing unchanged parts
// input:
// returns:
var diff = '';
// empty text
if ( (html == null) || (html == '') ) {
return '';
}
// remove container by non-regExp replace
diff = diff.replace(wDiff.htmlContainerStart, '');
diff = diff.replace(wDiff.htmlContainerEnd, '')
// scan for diff html tags
var regExpDiff = /<\w+\b[^>]*\bclass="wDiff(MarkLeft|MarkRight|BlockLeft|BlockRight|Delete|Insert)"[^>]*>(.|\n)*?<!--wDiff\1-->/g;
var tagStart = [];
var tagEnd = [];
var i = 0;
var
// save tag positions
while ( (regExpMatch = regExpDiff.exec(html)) != null ) {
// combine consecutive diff tags
if ( (i > 0) && (tagEnd[i - 1] ==
tagEnd[i - 1] =
}
else {
tagStart[i] =
tagEnd[i] =
i ++;
}
}
// no diff tags detected
if (tagStart.length == 0) {
return
}
// define regexps
var regExpHeading = /\n=+.+?=+ *\n|\n\{\||\n\|\}/g;
var regExpParagraph = /\n\n+/g;
Line 939 ⟶ 1,961:
var regExpBlank = /(<[^>]+>)*\s+/g;
// determine fragment border positions around diff tags
var rangeStart = [];
var rangeEnd = [];
var rangeStartType = [];
var rangeEndType = [];
// cycle through diff tag start positions
for (var i = 0; i < tagStart.length; i ++) {
var
// find last heading before diff tag
var lastPos = tagStart[i] -
if (lastPos < 0) {
lastPos = 0;
}
regExpHeading.lastIndex = lastPos;
while ( (
if (
break;
}
rangeStart[i] =
rangeStartType[i] = 'heading';
}
// find last paragraph before diff tag
if (rangeStart[i] == null) {
lastPos = tagStart[i] -
if (lastPos < 0) {
lastPos = 0;
}
regExpParagraph.lastIndex = lastPos;
while ( (
if (
break;
}
rangeStart[i] =
rangeStartType[i] = 'paragraph';
}
}
// find last line break before diff tag
if (rangeStart[i] == null) {
lastPos = tagStart[i] -
if (lastPos < 0) {
lastPos = 0;
}
regExpLine.lastIndex = lastPos;
while ( (
if (
break;
}
rangeStart[i] =
rangeStartType[i] = 'line';
}
}
// find last blank before diff tag
if (rangeStart[i] == null) {
lastPos = tagStart[i] -
if (lastPos < 0) {
lastPos = 0;
}
regExpBlank.lastIndex = lastPos;
while ( (
if (
break;
}
rangeStart[i] =
rangeStartType[i] = 'blank';
}
}
// fixed number of chars before diff tag
if (rangeStart[i] == null) {
rangeStart[i] = tagStart[i] -
rangeStartType[i] = 'chars';
if (rangeStart[i] < 0) {
Line 1,018 ⟶ 2,042:
}
// find first heading after diff tag
regExpHeading.lastIndex = tagEnd[i];
if ( (
if (
rangeEnd[i] =
rangeEndType[i] = 'heading';
}
}
// find first paragraph after diff tag
if (rangeEnd[i] == null) {
regExpParagraph.lastIndex = tagEnd[i];
if ( (
if (
rangeEnd[i] =
rangeEndType[i] = 'paragraph';
}
Line 1,038 ⟶ 2,062:
}
// find first line break after diff tag
if (rangeEnd[i] == null) {
regExpLine.lastIndex = tagEnd[i] +
if ( (
if (
rangeEnd[i] =
rangeEndType[i] = 'break';
}
Line 1,049 ⟶ 2,073:
}
// find blank after diff tag
if (rangeEnd[i] == null) {
regExpBlank.lastIndex = tagEnd[i] +
if ( (
if (
rangeEnd[i] =
rangeEndType[i] = 'blank';
}
Line 1,060 ⟶ 2,084:
}
// fixed number of chars after diff tag
if (rangeEnd[i] == null) {
rangeEnd[i] = tagEnd[i] +
if (rangeEnd[i] >
rangeEnd[i] =
rangeEndType[i] = 'chars';
}
Line 1,070 ⟶ 2,094:
}
// remove overlaps, join close fragments
var fragmentStart = [];
var fragmentEnd = [];
Line 1,081 ⟶ 2,105:
var j = 1;
for (var i = 1; i < rangeStart.length; i ++) {
if (rangeStart[i] > fragmentEnd[j - 1] +
fragmentStart[j] = rangeStart[i];
fragmentEnd[j] = rangeEnd[i];
Line 1,094 ⟶ 2,118:
}
// assemble the fragments
for (var i = 0; i < fragmentStart.length; i ++) {
// get text fragment
var fragment =
var fragment = fragment.replace(/^\n+|\n+$/g, '');
// add inline marks for omitted chars and words
if (fragmentStart[i] > 0) {
if (fragmentStartType[i] == 'chars') {
fragment =
}
else if (fragmentStartType[i] == 'blank') {
fragment =
}
}
if (fragmentEnd[i] <
if (fragmentStartType[i] == 'chars') {
fragment = fragment +
}
else if (fragmentStartType[i] == 'blank') {
fragment = fragment + ' ' +
}
}
// remove leading and trailing empty lines
fragment = fragment.replace(/^\n+|\n+$/g, '');
// add fragment separator
if (i > 0) {
diff += wDiff.htmlSeparator;
}
// encapsulate span errors
}
// add
diff = wDiff.htmlContainerStart + diff + wDiff.htmlContainerEnd;
// WED('diff', diff);
return diff;
};
//
// wDiff.AddStyleSheet: add CSS rules to new style sheet, cross-browser >= IE6
//
wDiff.AddStyleSheet = function(css) {
var style = document.createElement('style');
style.type = 'text/css';
if (style.styleSheet != null) {
style.styleSheet.cssText = css;
}
else {
style.appendChild( document.createTextNode(css) );
}
document.getElementsByTagName('head')[0].appendChild(style);
return;
};
//
// wDiff.DebugText: dump text (text.old or text.new) object
//
wDiff.DebugText = function(text) {
var dump = 'first: ' + text.first + '\tlast: ' + text.last + '\n';
dump += '\ni \tlink \t(prev \tnext) \t#num \t"token"\n';
var i = text.first;
while ( (i != null) && (text.tokens[i] != null) ) {
dump += i + ' \t' + text.tokens[i].link + ' \t(' + text.tokens[i].prev + ' \t' + text.tokens[i].next + ') \t#' + text.tokens[i].number + ' \t' + wDiff.DebugShortenString(text.tokens[i].token) + '\n';
i = text.tokens[i].next;
}
return dump;
};
//
// wDiff.DebugBlocks: dump blocks object
//
wDiff.DebugBlocks = function(blocks) {
var dump = '\ni \toldBl \toldNm \tnewNm \tchars \ttype \tsect \tgroup \tfixed \tstring\n';
for (var i = 0; i < blocks.length; i ++) {
dump += i + ' \t' + blocks[i].oldBlock + ' \t' + blocks[i].oldNumber + ' \t' + blocks[i].newNumber + ' \t' + blocks[i].chars + ' \t' + blocks[i].type + ' \t' + blocks[i].section + ' \t' + blocks[i].group + ' \t' + blocks[i].fixed + ' \t' + wDiff.DebugShortenString(blocks[i].string) + '\n';
}
return dump;
};
//
// wDiff.DebugGroups: dump groups object
//
wDiff.DebugGroups = function(groups) {
var dump = '\ni \tblSta \tblEnd \tmWord \twords \tchars \tfixed \oldNm \tmoved \tmFrom \tcolor \tdiff\n';
for (var i = 0; i < groups.length; i ++) {
dump += i + ' \t' + groups[i].blockStart + ' \t' + groups[i].blockEnd + ' \t' + groups[i].maxWords + ' \t' + groups[i].words + ' \t' + groups[i].chars + ' \t' + groups[i].fixed + ' \t' + groups[i].oldNumber + ' \t' + groups[i].moved.toString() + ' \t' + groups[i].movedFrom + ' \t' + groups[i].color + ' \t' + wDiff.DebugShortenString(groups[i].diff) + '\n';
}
return dump;
};
//
// wDiff.DebugGaps: dump gaps object
//
wDiff.DebugGaps = function(gaps) {
var dump = '\ni \tnFirs \tnLast \tnTok \toFirs \toLast \toTok \tcharSplit\n';
for (var i = 0; i < gaps.length; i ++) {
dump += i + ' \t' + gaps[i].newFirst + ' \t' + gaps[i].newLast + ' \t' + gaps[i].newTokens + ' \t' + gaps[i].oldFirst + ' \t' + gaps[i].oldLast + ' \t' + gaps[i].oldTokens + ' \t' + gaps[i].charSplit + '\n';
}
return dump;
};
//
// wDiff.DebugShortenString: shorten string for debugging
//
wDiff.DebugShortenString = function(string) {
if (string == null) {
return 'null';
}
string = string.replace(/\n/g, '\\n');
var max = 100;
if (string.length > max) {
string = string.substr(0, max - 1 - 30) + '…' + string.substr(string.length - 30);
}
return '"' + string + '"';
};
// initialize wDiff
wDiff.Init();
// </syntaxhighlight>
| |||