Content deleted Content added
1.0.22 (September 15, 2014) fix newline and space markup |
1.1.0 (September 21, 2014) major clean-up/partial rewrite: objectified, findMaxPath bug fix, unit tests, del block positioning, marks as blocks, unique words in paragraph/sentence tokens |
||
Line 3:
// ==UserScript==
// @name wDiff
// @version 1.
// @date September
// @description improved word-based diff library with block move detection
// @homepage https://en.wikipedia.org/wiki/User:Cacycle/diff
Line 40:
Usage:
var diffHtml = wDiff.
Datastructures (abbreviations from publication):
.configurations see top of code below for configuration and customization options
.string: text
.words{}: word count hash
.tokens[]: token list for new or old string (doubly-linked list) (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
.unique: token is unique word in text
class TextDiff: diff object
.
.
.
.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:
.linked: flag: at least one unique token pair has been linked
.
.newNumber: new text token number of first token
.oldStart: old text token index of first token
.count number of tokens
.unique: contains unique matched token
.words: word count
.chars: char length
.type: 'same', 'del', 'ins', 'mark'
.section: section number
.group: group number of block
.fixed: belongs to a fixed (not moved) group
.moved: 'mark' block associated moved block group number
.string: string of block tokens
.groups[]: section blocks that are consecutive in old text
.oldNumber: first block oldNumber
.blockStart: first block index
.blockEnd: last block index
.unique: contains unique matched token
.maxWords: word count of longest block
.words: word count
.chars: char count
.fixed: not moved from original position
.movedFrom: group position this group has been moved from
.color: color number of moved group
*/
// JSHint options: W004: is already defined
/* jshint -W004
/* global console */
Line 111 ⟶ 113:
'use strict';
// define global
var wDiff; if (wDiff === undefined) { wDiff = {}; }
var WED;
//
// start of configuration and customization settings
//
//
Line 133 ⟶ 139:
// display blocks in different colors
if (wDiff.coloredBlocks === undefined) { wDiff.coloredBlocks = false; }
// show debug infos and stats
if (wDiff.debug === undefined) { wDiff.debug = false; }
// show debug infos and stats
if (wDiff.debugTime === undefined) { wDiff.debugTime = false; }
// run unit tests
if (wDiff.unitTesting === undefined) { wDiff.unitTesting = false; }
// UniCode letter support for regexps, from http://xregexp.com/addons/unicode/unicode-base.js v1.0.0
Line 179 ⟶ 194:
if (wDiff.regExpSlideBorder === undefined) { wDiff.regExpSlideBorder = new RegExp('[^' + wDiff.letters + ']$'); }
//
if (wDiff.
if (wDiff.regExpChunk === undefined) { wDiff.regExpChunk = wDiff.regExpSplit.chunk; }
// regExp detecting blank-only and single-char blocks
Line 214 ⟶ 230:
// maximal fragment distance to join close fragments
if (wDiff.fragmentJoinLines
if (wDiff.fragmentJoinChars
//
Line 238 ⟶ 254:
// block
'.wDiffBlockLeft, .wDiffBlockRight { font-weight: bold; background-color: #e8e8e8; border-radius: 0.25em; padding: 0.2em 1px; margin: 0 1px; }' +
'.wDiffBlock { }' +
'.wDiffBlock0 { background-color: #
'.wDiffBlock1 { background-color: #
'.wDiffBlock2 { background-color: #
'.wDiffBlock3 { background-color: #
'.wDiffBlock4 { background-color: #
'.wDiffBlock5 { background-color: #bbccff; }' +
'.wDiffBlock6 { background-color: #
'.wDiffBlock7 { background-color: #ffbbbb; }' +
'.wDiffBlock8 { background-color: #a0e8a0; }' +
'.wDiffBlockHighlight { background-color: #777; color: #fff; border: solid #777; border-width: 1px 0; }' +
// mark
'.wDiffMarkLeft, .wDiffMarkRight
'.wDiffMarkRight:before { content: "' + wDiff.symbolMarkRight + '"; }' +
'.wDiffMarkLeft:before
'.wDiffMark { background-color: #e8e8e8; color: #666; }' +
'.wDiffMark0 { background-color: #ffff60; }' +
'.wDiffMark1 { background-color: #c8f880; }' +
'.wDiffMark2 { background-color: #ffd0f0; }' +
'.wDiffMark3 { background-color: #a0ffff; }' +
'.wDiffMark4 { background-color: #fff860; }' +
'.wDiffMark5 { background-color: #b0c0ff; }' +
'.wDiffMark6 { background-color: #e0c0ff; }' +
'.wDiffMark7 { background-color: #ffa8a8; }' +
'.wDiffMark8 { background-color: #98e898; }' +
'.wDiffMarkHighlight { background-color: #777; color: #fff; }' +
// wrappers
Line 271 ⟶ 287:
'.wDiffNoChange { white-space: pre-wrap; background: #f0f0f0; border: #bbb solid; border-width: 1px 1px 1px 0.5em; border-radius: 0.5em; font-family: sans-serif; font-size: 88%; line-height: 1.6; box-shadow: 2px 2px 2px #ddd; padding: 0.5em; margin: 1em 0; }' +
'.wDiffSeparator { margin-bottom: 1em; }' +
'.wDiffOmittedChars
// newline
Line 307 ⟶ 323:
if (wDiff.styleInsertBlank === undefined) { wDiff.styleInsertBlank = ''; }
if (wDiff.styleDeleteBlank === undefined) { wDiff.styleDeleteBlank = ''; }
if (wDiff.
if (wDiff.styleBlockLeft === undefined) { wDiff.styleBlockLeft = ''; }
if (wDiff.styleBlockRight === undefined) { wDiff.styleBlockRight = ''; }
if (wDiff.styleBlockHighlight === undefined) { wDiff.styleBlockHighlight = ''; }
if (wDiff.styleBlockColor === undefined) { wDiff.styleBlockColor
if (wDiff.styleMark === undefined) { wDiff.styleMark = ''; }
if (wDiff.styleMarkLeft === undefined) { wDiff.styleMarkLeft = ''; }
if (wDiff.styleMarkRight === undefined) { wDiff.styleMarkRight = ''; }
Line 326 ⟶ 344:
//
// output html
//
// dynamic replacements: {block}: block number style, {mark}: mark number style, {class}: class number, {number}: block number, {title}: title attribute (popup)
// class plus html comment are required indicators for
if (wDiff.blockEvent === undefined) { wDiff.blockEvent = ' onmouseover="wDiff.blockHandler(undefined, this, \'mouseover\');"'; }
if (wDiff.htmlContainerStart === undefined) { wDiff.htmlContainerStart = '<div class="wDiffContainer" id="wDiffContainer" style="' + wDiff.styleContainer + '">'; }
if (wDiff.htmlContainerEnd
if (wDiff.htmlInsertStart === undefined) { wDiff.htmlInsertStart = '<span class="wDiffInsert" style="' + wDiff.styleInsert + '" title="+">'; }
if (wDiff.htmlInsertStartBlank === undefined) { wDiff.htmlInsertStartBlank = '<span class="wDiffInsert wDiffInsertBlank" style="
if (wDiff.htmlInsertEnd
if (wDiff.
if (wDiff.
if (wDiff.htmlDeleteEnd === undefined) { wDiff.htmlDeleteEnd = '</span><!--wDiffDelete-->'; }
if (wDiff.htmlBlockLeftStart === undefined) {
if (wDiff.coloredBlocks === false) {
wDiff.htmlBlockLeftStart = '<span class="wDiffBlockLeft" style="' + wDiff.styleBlockLeft + '" title="' + wDiff.symbolMarkLeft + '" id="wDiffBlock{number}"' + wDiff.blockEvent + '>';
}
else {
wDiff.htmlBlockLeftStart = '<span class="wDiffBlockLeft wDiffBlock wDiffBlock{class}" style="' + wDiff.styleBlockLeft + wDiff.styleBlock + '{block}" title="' + wDiff.symbolMarkLeft + '" id="wDiffBlock{number}"' + wDiff.blockEvent + '>';
}
}
if (wDiff.htmlBlockLeftEnd === undefined) { wDiff.htmlBlockLeftEnd = '</span><!--wDiffBlockLeft-->'; }
if (wDiff.htmlBlockRightStart === undefined) {
if (wDiff.coloredBlocks === false) {
wDiff.htmlBlockRightStart = '<span class="wDiffBlockRight" style="' + wDiff.styleBlockRight + '" title="' + wDiff.symbolMarkRight + '" id="wDiffBlock{number}"' + wDiff.blockEvent + '>';
}
else {
wDiff.htmlBlockRightStart = '<span class="wDiffBlockRight wDiffBlock wDiffBlock{class}" style="' + wDiff.styleBlockRight + wDiff.styleBlock + '{block}" title="' + wDiff.symbolMarkRight + '" id="wDiffBlock{number}"' + wDiff.blockEvent + '>';
}
}
if (wDiff.htmlBlockRightEnd === undefined) { wDiff.htmlBlockRightEnd = '</span><!--wDiffBlockRight-->'; }
if (wDiff.htmlMarkLeft === undefined) {
if (wDiff.coloredBlocks === false) {
wDiff.htmlMarkLeft = '<span class="wDiffMarkLeft" style="' + wDiff.styleMarkLeft + '"{title} id="wDiffMark{number}"' + wDiff.blockEvent + '></span><!--wDiffMarkLeft-->';
}
else {
wDiff.htmlMarkLeft = '<span class="wDiffMarkLeft wDiffMark wDiffMark{class}" style="' + wDiff.styleMarkLeft + wDiff.styleMark + '{mark}"{title} id="wDiffMark{number}"' + wDiff.blockEvent + '></span><!--wDiffMarkLeft-->';
}
}
if (wDiff.htmlMarkRight === undefined) {
if (wDiff.coloredBlocks === false) {
wDiff.htmlMarkRight = '<span class="wDiffMarkRight" style="' + wDiff.styleMarkRight + '"{title} id="wDiffMark{number}"' + wDiff.blockEvent + '></span><!--wDiffMarkRight-->';
}
else {
wDiff.htmlMarkRight = '<span class="wDiffMarkRight wDiffMark wDiffMark{class}" style="' + wDiff.styleMarkRight + wDiff.styleMark + '{mark}"{title} id="wDiffMark{number}"' + wDiff.blockEvent + '></span><!--wDiffMarkRight-->';
}
}
if (wDiff.htmlNewline === undefined) { wDiff.htmlNewline = '<span class="wDiffNewline" style="' + wDiff.styleNewline + '">\n</span>'; }
Line 357 ⟶ 404:
if (wDiff.htmlSpace === undefined) { wDiff.htmlSpace = '<span class="wDiffSpace" style="' + wDiff.styleSpace + '"><span class="wDiffSpaceSymbol" style="' + wDiff.styleSpaceSymbol + '"></span> </span>'; }
// shorten output
if (wDiff.htmlFragmentStart === undefined) { wDiff.htmlFragmentStart = '<pre class="wDiffFragment" style="' + wDiff.styleFragment + '">'; }
if (wDiff.htmlFragmentEnd
if (wDiff.htmlNoChange === undefined) { wDiff.htmlNoChange = '<pre class="wDiffNoChange" style="' + wDiff.styleNoChange + '" title="="></pre>'; }
Line 369 ⟶ 414:
//
// javascript handler for output code,
//
// wDiff.
if (wDiff.
// IE compatibility
Line 388 ⟶ 433:
if (type == 'mouseover') {
element.onmouseover = null;
element.onmouseout = function (event) { wDiff.
element.onclick = function (event) { wDiff.
block.className += ' wDiffBlockHighlight';
mark.className += ' wDiffMarkHighlight';
Line 397 ⟶ 442:
if ( (type == 'mouseout') || (type == 'click') ) {
element.onmouseout = null;
element.onmouseover = function (event) { wDiff.
// getElementsByClassName
Line 426 ⟶ 471:
}
// get element height (getOffsetTop)
var corrElementPos = 0;
var node = corrElement;
Line 433 ⟶ 478:
} while ( (node = node.offsetParent) !== null );
// get scroll
var top;
if (window.pageYOffset !== undefined) {
Line 442 ⟶ 487:
}
// get cursor pos
var cursor;
if (event.pageY !== undefined) {
Line 450 ⟶ 496:
}
// get line height
var line = 12;
if (window.getComputedStyle !== undefined) {
Line 455 ⟶ 502:
}
// scroll element under mouse cursor
window.scroll(0, corrElementPos + top - cursor + line / 2);
}
return;
}; }
//
// end of configuration and customization settings
//
// wDiff.
// called from: on code load
// calls:
wDiff.
// legacy for short time
// add styles to head
wDiff.
// add block handler to head if running under Greasemonkey
if (typeof GM_info == 'object') {
var script = 'var wDiff; if (wDiff === undefined) { wDiff = {}; } wDiff.
wDiff.
}
return;
Line 498 ⟶ 535:
// wDiff.
// called from: user land
// calls: new TextDiff, TextDiff.shortenOutput(), this.unitTests()
wDiff.
// create text diff object
var textDiff = new wDiff.TextDiff(oldString, newString, this);
// legacy for short time
wDiff.textDiff = textDiff;
wDiff.ShortenOutput = wDiff.textDiff.shortenOutput;
//
if (wDiff.debugTime === true) {
console.time('diff');
}
//
textDiff.diff();
// start timer
if (
console.timeEnd('diff');
}
// shorten output
if (full !== true) {
// start timer
if (wDiff.debugTime === true) {
console.time('shorten');
}
textDiff.shortenOutput();
// stop timer
if (wDiff.debugTime === true) {
console.timeEnd('shorten');
}
}
// stop timer
if (
console.timeEnd('diff');
}
// run unit tests
if (wDiff.unitTesting === true) {
}
return textDiff.html;
};
// wDiff.unitTests(): test diff for consistency between input and output
// input: textDiff: text diff object after calling .diff()
// called from: .diff()
wDiff.unitTests = function (textDiff) {
// start timer
if (wDiff.debugTime === true) {
console.time('unit tests');
}
var html = textDiff.html;
// check if output is consistent with new text
textDiff.assembleDiff('new');
var diff = textDiff.html.replace(/<[^>]*>/g, '');
var text = textDiff.htmlEscape(textDiff.newText.string);
if (diff != text) {
console.log('Error: wDiff unit test failure: output not consistent with new text');
console.log('new text:\n', text);
console.log('new diff:\n', diff);
}
else {
console.log('OK: wDiff unit test passed: output consistent with new text');
}
// check if output is consistent with old text
textDiff.assembleDiff('old');
var diff = textDiff.html.replace(/<[^>]*>/g, '');
var text = textDiff.htmlEscape(textDiff.oldText.string);
if (diff != text) {
console.log('Error: wDiff unit test failure: output not consistent with old text');
console.log('old text:\n', text);
console.log('old diff:\n', diff);
}
else {
console.log('OK: wDiff unit test passed: output consistent with old text');
}
textDiff.html = html;
// stop timer
if (wDiff.
console.timeEnd('unit tests');
}
return;
};
//
// wDiff.Text class: data and methods for single text version (old or new)
// called from: TextDiff.init()
//
wDiff.Text = function (string, parent) {
this.parent = parent;
this.string = null;
this.tokens = [];
this.first = null;
this.last = null;
this.words = {};
//
// Text.init(): initialize text object
//
this.init = function () {
if (typeof string != 'string') {
string = string.toString();
}
// IE / Mac fix
this.string = string.replace(/\r\n?/g, '\n');
this.wordParse(wDiff.regExpWord);
this.wordParse(wDiff.regExpChunk);
return;
};
// Text.wordParse(): parse and count words and chunks for identification of unique words
// called from: .init()
// changes: .words
this.wordParse = function (regExp) {
var
while ( (regExpMatch = regExp.exec(this.string)) !== null) {
var word =
if (this.words[word] === undefined) {
this.words[word] = 1;
else {
this.words[word] ++;
}
}
return;
//
// input:
// called from: TextDiff.diff(), .splitRefine()
// changes: .tokens list, .first, .last
string =
prev =
next =
string =
if (regExpMatch.index > lastIndex) {
split.push(string.substring(lastIndex, regExpMatch.index));
}
split.push(regExpMatch[0]);
lastIndex = wDiff.regExpSplit[level].lastIndex;
}
if (lastIndex < string.length) {
split.push(string.substring(lastIndex));
}
token: split[i],
prev: prev,
next: null,
link: null,
number: null,
};
// link previous item to current
if (prev !== null) {
}
prev = current;
current ++;
}
if (prev !== null) {
}
if (next !== null) {
this.tokens[next].prev = prev;
}
}
// initial text split
if (token === undefined) {
}
// first or last token has been split
else {
if (token ==
}
if (token == this.last) {
this.last = prev;
}
}
}
return;
};
// Text.splitRefine(): split unique unmatched tokens into smaller tokens
// changes: text (text.newText or text.oldText) .tokens list
// called from: TextDiff.diff()
// calls: .split()
this.splitRefine = function (regExp) {
// cycle through tokens list
var i = this.first;
while ( (i !== null) && (this.tokens[i] !== null) ) {
// refine unique unmatched tokens into smaller tokens
if (this.tokens[i].link === null) {
this.split(regExp, i);
}
i = this.tokens[i].next;
}
return;
// Text.enumerateTokens(): enumerate text token list
// called from: TextDiff.diff()
//
while ( (i !== null) && ( this.tokens[i].number = number;
number ++;
i = this.tokens[i].next;
}
return;
};
// Text.debugText(): dump text object for debugging
// input: text: title
this.debugText = function (text) {
var dump = 'first: ' + this.first + '\tlast: ' + this.last + '\n';
dump += '\ni \tlink \t(prev \tnext) \tuniq \t#num \t"token"\n';
var i = this.first;
while ( (i !== null) && (this.tokens[i] !== null) ) {
dump += i + ' \t' + this.tokens[i].link + ' \t(' + this.tokens[i].prev + ' \t' + this.tokens[i].next + ') \t' + this.tokens[i].unique + ' \t#' + this.tokens[i].number + ' \t' + parent.debugShortenString(this.tokens[i].token) + '\n';
i = this.tokens[i].next;
}
console.log(text + ':\n' + dump);
return;
// initialize text object
this.init();
};
//
// wDiff.TextDiff class: main wDiff class, includes all data structures and methods required for a diff
// called from: wDiff.diff()
//
wDiff.TextDiff = function (oldString, newString) {
this.newText = null;
this.oldText = null;
this.blocks = [];
this.groups = [];
this.sections = [];
this.html = '';
//
// TextDiff.init(): initialize diff object
//
this.init = function () {
this.newText = new wDiff.Text(newString, this);
this.oldText = new wDiff.Text(oldString, this);
return;
};
// TextDiff.diff(): main method
// input: version: 'new', 'old', show only one marked-up version, .oldString, .newString
// called from: wDiff.diff()
// calls: Text.split(), Text.splitRefine(), .calculateDiff(), .slideGaps(), .enumerateTokens(), .detectBlocks(), .assembleDiff()
// changes: .html
this.diff = function (version) {
// trap trivial changes: no change
if (this.newText.string == this.oldText.string) {
}
//
if ( (this.oldText.string === '') || ( (this.oldText.string == '\n') && (this.newText.string.charAt(this.newText.string.length - 1) == '\n') ) ) {
this.html = wDiff.htmlInsertStart + this.htmlEscape(this.newText.string) + wDiff.htmlInsertEnd;
return;
}
// trap trivial changes: new text deleted
if ( (this.newText.string === '') || ( (this.newText.string == '\n') && (this.oldText.string.charAt(this.oldText.string.length - 1) == '\n') ) ) {
this.html = wDiff.htmlDeleteStart + this.htmlEscape(this.oldText.string) + wDiff.htmlDeleteEnd;
return;
}
//
token: [],
hash: {},
linked: false
};
// split new and old text into paragraps
this.newText.split('paragraph');
this.oldText.split('paragraph');
// calculate diff
this.calculateDiff(symbols, 'paragraph');
// refine different paragraphs into sentences
this.newText.splitRefine('sentence');
this.oldText.splitRefine('sentence');
// calculate refined diff
this.calculateDiff(symbols, 'sentence');
// refine different paragraphs into chunks
this.newText.splitRefine('chunk');
this.oldText.splitRefine('chunk');
// calculate refined diff
this.calculateDiff(symbols, 'chunk');
// refine different sentences into words
this.newText.splitRefine('word');
this.oldText.splitRefine('word');
// calculate refined diff information with recursion for unresolved gaps
this.calculateDiff(symbols, 'word', true);
// slide gaps
this.slideGaps(this.newText, this.oldText);
this.slideGaps(this.oldText, this.newText);
// split tokens into chars in selected unresolved gaps
if (wDiff.charDiff === true) {
this.splitRefineChars();
// calculate refined diff information with recursion for unresolved gaps
this.calculateDiff(symbols, 'character', true);
// slide gaps
this.slideGaps(this.newText, this.oldText);
this.slideGaps(this.oldText, this.newText);
}
// enumerate token lists
this.newText.enumerateTokens();
this.oldText.enumerateTokens();
// detect moved blocks
this.detectBlocks();
this.assembleDiff(version);
if (wDiff.debug === true) {
console.log('HTML:\n', this.html);
}
return;
};
// TextDiff.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.newText or text.oldText) .tokens list
// called from: .diff()
// calls: Text.split()
// steps:
// find corresponding gaps
// select gaps of identical token number and strong similarity in all tokens
// refine words into chars in selected gaps
this.splitRefineChars = function () {
//
// find corresponding gaps
//
// cycle trough new text tokens list
var gaps = [];
var gap = null;
var i = this.newText.first;
var j = this.oldText.first;
while ( (i !== null) && (this.newText.tokens[i] !== null) ) {
// get token links
var newLink = this.newText.tokens[i].link;
var oldLink = null;
if (j !== null) {
oldLink = this.oldText.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 = this.oldText.tokens[newLink].next;
}
i = this.newText.tokens[i].next;
}
// cycle trough
for (var
//
var
while ( (j !== null) && (this.oldText.tokens[j] !== null) && (this.oldText.tokens[j].link === null) ) {
// count old chars and tokens in gap
gaps[gap].oldTokens ++;
j = this.oldText.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 (this.newText.tokens[ gaps[gap].newFirst ].token != this.oldText.tokens[ gaps[gap].oldFirst ].token + this.oldText.tokens[ gaps[gap].oldLast ].token ) {
continue;
}
}
else if ( (gaps[gap].oldTokens == 1) && (gaps[gap].newTokens == 3) ) {
if (this.oldText.tokens[ gaps[gap].oldFirst ].token != this.newText.tokens[ gaps[gap].newFirst ].token + this.newText.tokens[ gaps[gap].newLast ].token ) {
}
}
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 = this.newText.tokens[i].token;
var oldToken = this.oldText.tokens[j].token;
// get shorter and longer token
var longerToken;
if (newToken.length < oldToken.length) {
shorterToken = newToken;
longerToken = oldToken;
}
else {
shorterToken = oldToken;
longerToken = newToken;
}
// not same token 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 ++;
}
//
var
if (
}
right ++;
}
//
if (left + right != shorterToken.length) {
// not addition or deletion of flanking strings in tokens (smaller token not part of larger token)
if (
// 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
break;
}
}
}
}
// same token length
else if (newToken != oldToken) {
//
for (var pos = 0; pos < shorterToken.length; pos ++) {
if (shorterToken.charAt(pos) == longerToken.charAt(pos)) {
}
}
if (ident/shorterToken.length < 0.49) {
//
break;
}
}
Line 991 ⟶ 1,159:
break;
}
i =
j =
}
gaps[gap].charSplit = charSplit;
}
//
// refine words into chars in selected gaps
//
for (var gap = 0; gap < gaps.length; gap ++) {
if (gaps[gap].charSplit === true) {
// cycle trough new text tokens list
var i = gaps[gap].newFirst;
var j = gaps[gap].oldFirst;
while (i !== null) {
var newToken = this.newText.tokens[i].token;
var oldToken = this.oldText.tokens[j].token;
// link identical tokens (spaces)
if (newToken == oldToken) {
this.newText.tokens[i].link = j;
this.oldText.tokens[j].link = i;
}
// refine different words into chars
else {
this.newText.split('character', i);
this.oldText.split('character', j);
}
//
if (
}
i = this.newText.tokens[i].next;
j = this.oldText.tokens[j].next;
}
}
}
return;
};
// TextDiff.slideGaps(): move gaps with ambiguous identical fronts to last newline or, if absent, last word border
// called from: .diff(), .detectBlocks()
// changes: .newText/.oldText .tokens list
this.slideGaps = function (text, textLinked) {
// cycle through tokens list
var i = text.first;
var gapStart = null;
while ( (i !== null) && (text.tokens[i] !== null) ) {
// remember gap start
}
// find gap end
else if ( (gapStart !== null) && (text.tokens[i].link !== null) ) {
// slide down as deep as possible
var front = gapStart;
var back = i;
var frontTest = null;
var backTest = null;
while (
(front !== null) && (back !== null) &&
(text.tokens[front].link === null) && (text.tokens[back].link !== null) &&
(text.tokens[front].token === text.tokens[back].token)
) {
text.tokens[front].link = text.tokens[back].link;
textLinked.tokens[ text.tokens[front].link ].link = front;
text.tokens[back].link = null;
frontTest = front;
backTest = back;
front = text.tokens[front].next;
back = text.tokens[back].next;
}
//
while (
(
(text.tokens[
(text.tokens[
) {
if (wDiff.regExpSlideStop.test(text.tokens[
frontStop = frontTest;
break;
}
else if ( (frontStop === null) && (wDiff.regExpSlideBorder.test(text.tokens[frontTest].token) === true) ) {
frontStop = frontTest;
}
frontTest = text.tokens[frontTest].prev;
backTest = text.tokens[backTest].prev;
}
// actually slide up to line break or, if absent, word border
if (frontStop !== null) {
while (
(front !== null) && (back !== null) && (front !== frontStop) &&
(text.tokens[front].link !== null) && (text.tokens[back].link === null) &&
(text.tokens[front].token == text.tokens[back].token)
) {
text.tokens[back].link = text.tokens[front].link;
textLinked.tokens[ text.tokens[back].link ].link = back;
text.tokens[front].link = null;
front = text.tokens[front].prev;
back = text.tokens[back].prev;
}
}
gapStart = null;
}
}
return;
};
// TextDiff.calculateDiff(): calculate diff information, can be called repeatedly during refining
// input: level: 'paragraph', 'sentence', 'chunk', 'word', or 'character'
// optionally for recursive calls: recurse, newStart, newEnd, oldStart, oldEnd (tokens list indexes), recursionLevel
// called from: .diff()
// calls: itself recursively
// changes: .oldText/.newText.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 matched 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
this.calculateDiff = function (symbols, level, recurse, newStart, newEnd, oldStart, oldEnd, recursionLevel) {
// start timer
if ( (wDiff.debugTime === true) && (recursionLevel === undefined) ) {
console.time(level);
}
// set defaults
if (newStart === undefined) { newStart = this.newText.first; }
if (newEnd === undefined) { newEnd = this.newText.last; }
if (oldStart === undefined) { oldStart = this.oldText.first; }
if (oldEnd === undefined) { oldEnd = this.oldText.last; }
if (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) && (this.newText.tokens[i] !== null) ) {
// add new entry to symbol table
var token = this.newText.tokens[i].token;
if (Object.prototype.hasOwnProperty.call(symbols.hash, token) === false) {
var current = symbols.token.length;
symbols.hash[token] = current;
symbols.token[current] = {
newCount: 1,
oldCount: 0,
newToken: i,
oldToken: null
};
}
// or update existing entry
else {
// increment token counter for new text
var hashToArray = symbols.hash[token];
symbols.token[hashToArray].newCount ++;
}
// next list element
if (i == newEnd) {
break;
}
i = this.newText.tokens[i].next;
}
//
// pass 2: parse old text into symbol table
//
while ( (j !== null) && (this.oldText.tokens[j] !== null) ) {
// add new entry to symbol table
var token = this.oldText.tokens[j].token;
if (Object.prototype.hasOwnProperty.call(symbols.hash, token) === false) {
var current = symbols.token.length;
symbols.hash[token] = current;
symbols.token[current] = {
newCount: 0,
oldCount: 1,
newToken: null,
oldToken: j
};
}
// or update existing entry
else {
// increment token counter for old text
var hashToArray = symbols.hash[token];
symbols.token[hashToArray].oldCount ++;
// add
symbols.token[hashToArray].oldToken = j;
}
// next list element
if (j === oldEnd) {
}
j = this.oldText.tokens[j].next;
}
//
// pass 3: connect unique tokens
//
// cycle trough symbol array
// find tokens in the symbol table that occur only once in both versions
if ( (symbols.token[
var newToken = symbols.token[i].newToken;
var oldToken = symbols.token[i].oldToken;
// do not use spaces as unique markers
if (/^\s+$/.test(this.newText.tokens[newToken].token) === false) {
// connect from new to old and from old to new
if (this.newText.tokens[newToken].link === null) {
this.newText.tokens[newToken].link = oldToken;
this.oldText.tokens[oldToken].link = newToken;
symbols.linked = true;
// check if token contains unique word
if ( (
var
var
var words = (token.match(wDiff.regExpWord) || []).concat(token.match(wDiff.regExpChunk) || []);
//
if (words.length >= wDiff.blockMinLength) {
unique = true;
}
//
else {
for (var word = 0; word < words.length; word ++) {
if ( (this.oldText.words[ words[word] ] == 1) && (this.newText.words[ words[word] ] == 1) ) {
break;
}
}
}
//
if (
}
}
}
Line 1,235 ⟶ 1,443:
}
}
//
// pass 4: connect adjacent identical tokens downwards
//
// get surrounding connected tokens
var i = newStart;
if (
i =
}
var iStop = newEnd;
iStop = this.newText.tokens[iStop].next;
}
var j = null;
// cycle trough new text tokens list down
// connected pair
var link = this.newText.tokens[i].link;
if (link !== null) {
j = this.oldText.tokens[link].next;
}
//
else if ( (j !== null) && (this.oldText.tokens[j].link === null) && (this.newText.tokens[i].token == this.oldText.tokens[j].token) ) {
j = this.oldText.tokens[j].next;
}
// not same
j = null;
}
i = this.newText.tokens[i].next;
} while (i !== iStop);
//
// pass 5: connect adjacent identical tokens upwards
//
//
var i = newEnd;
}
var iStop = newStart;
if (this.newText.tokens[iStop].prev !== null) {
iStop = this.newText.tokens[iStop].prev;
}
var j = null;
// cycle trough new text tokens list up
do {
// connected pair
if (link !== null) {
j = this.oldText.tokens[link].prev;
}
// connect if tokens are the same
else if ( (j !== null) && (this.oldText.tokens[j].link === null) && (this.newText.tokens[i].token == this.oldText.tokens[j].token) ) {
this.newText.tokens[i].link = j;
this.oldText.tokens[j].link = i;
j = this.oldText.tokens[j].prev;
}
// not same
else {
}
} while (i !== iStop);
//
// connect adjacent identical tokens downwards from text start, treat boundary as connected, stop after first connected token
//
// only for full text diff
// from start
var i = this.newText.first;
var j = this.oldText.first;
// cycle trough new text tokens list down, connect identical tokens, stop after first connected token
while ( (i !== null) && (j !== null) && (this.newText.tokens[i].link === null) && (this.oldText.tokens[j].link === null) && (this.newText.tokens[i].token == this.oldText.tokens[j].token) ) {
this.newText.tokens[i].link = j;
this.oldText.tokens[j].link = i;
j = this.oldText.tokens[j].next;
i = this.newText.tokens[i].next;
}
// from end
var i = this.newText.last;
var j = this.oldText.last;
// cycle trough old text tokens list up, connect identical tokens, stop after first connected token
while ( (i !== null) && (j !== null) && (this.newText.tokens[i].link === null) && (this.oldText.tokens[j].link === null) && (this.newText.tokens[i].token == this.oldText.tokens[j].token) ) {
this.newText.tokens[i].link = j;
this.oldText.tokens[j].link = i;
j = this.oldText.tokens[j].prev;
i = this.newText.tokens[i].prev;
}
}
//
// 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
//
//
var
while ( (i !== null) && (this.newText.tokens[i] !== null) ) {
// get j from previous tokens match
var
var
}
}
//
if ( (j !== null) && (this.oldText.tokens[j] !== null) && (this.newText.tokens[i].link === null) && (this.oldText.tokens[j].link === null) ) {
// determine the limits of the unresolved new sequence
var
var iEnd = null;
while ( (iNext !== null) && (this.newText.tokens[iNext].link === null) ) {
iLength ++;
if (iEnd == newEnd) {
break;
}
iNext = this.newText.tokens[iNext].next;
}
//
var jStart = j;
var jEnd = null;
var jLength = 0;
var jNext = j;
while ( (jNext !== null) && (this.oldText.tokens[jNext].link === null) ) {
jEnd = jNext;
jLength ++;
if (jEnd == oldEnd) {
break;
}
jNext = this.oldText.tokens[jNext].next;
}
//
if ( (iLength > 1) || (jLength > 1) ) {
hash: {},
linked: false
};
this.calculateDiff(symbolsRecurse, level, true, iStart, iEnd, jStart, jEnd, recursionLevel + 1);
}
i = iEnd;
}
// next list element
if (i == newEnd) {
break;
}
i = this.newText.tokens[i].next;
}
//
// recursively diff still unresolved regions upwards
//
// cycle trough new text tokens list
var i = newEnd;
var j = oldEnd;
while ( (i !== null) && (
// get j from next matched tokens
var iPrev =
if (iPrev !== null) {
var jPrev =
if (jPrev !== null) {
j =
}
}
// check for the start of an unresolved sequence
if ( (j !== null) && (
// determine the limits of the unresolved new sequence
var iStart = null;
var iEnd = i;
var iLength = 0;
var iNext = i;
while ( (iNext !== null) && (
iStart = iNext;
iLength ++;
if (iStart == newStart) {
break;
}
iNext = this.newText.tokens[iNext].prev;
}
// determine the limits of the unresolved old sequence
var jStart = null;
var jEnd = j;
var jLength = 0;
var jNext = j;
while ( (jNext !== null) && (
jStart = jNext;
jLength ++;
if (jStart == oldStart) {
break;
}
jNext = this.oldText.tokens[jNext].prev;
}
// recursively diff the unresolved sequence
if ( (iLength > 1) || (jLength > 1) ) {
// new symbols object for sub-region
var symbolsRecurse = {
token: [],
hash: {},
linked: false
};
}
i = iStart;
}
// next list element
if (i == newStart) {
break;
}
i = this.newText.tokens[i].prev;
}
}
}
// stop timer
if ( (wDiff.debugTime === true) && (recursionLevel === 0) ) {
console.timeEnd(level);
}
return;
};
// TextDiff.detectBlocks(): main method for extracting deleted, inserted, and moved blocks from raw diff data
// called from: .diff()
// calls: .getSameBlocks(), .getSections(), .getGroups(), .setFixed(), getDelBlocks(), .positionDelBlocks(), .unlinkBlocks(), .getInsBlocks(), .setInsGroups(), .insertMarks()
// input:
// text: object containing text tokens list
// blocks: empty array for block data
// groups: empty array for group data
// changes: .text, .blocks, .groups
// 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: = + =-= = -= = + = = = = =
this.detectBlocks = function () {
if (wDiff.debug === true) {
this.oldText.debugText();
this.newText.debugText();
}
// collect identical corresponding ('same') blocks from old text and sort by new text
this.getSameBlocks();
// collect independent block sections (no old/new crosses outside section) for per-section determination of non-moving (fixed) groups
this.getSections();
// find groups of continuous old text blocks
this.getGroups();
// set longest sequence of increasing groups in sections as fixed (not moved)
this.setFixed();
// collect deletion ('del') blocks from old text
this.getDelBlocks();
this.positionDelBlocks();
// convert groups to insertions/deletions if maximal block length is too short
var unlink = 0;
if (wDiff.blockMinLength > 0) {
// repeat as long as unlinking is possible
var unlinked = false;
do {
unlinked = this.unlinkBlocks();
//
if (unlinked === true) {
unlink ++;
this.slideGaps(this.oldText, this.newText);
// repeat block detection from start
this.getSameBlocks();
this.getSections();
this.getGroups();
this.setFixed();
this.getDelBlocks();
this.positionDelBlocks();
}
} while (unlinked === true);
}
this.getInsBlocks();
// set group numbers of 'ins' blocks
this.setInsGroups();
// mark original positions of moved groups
this.insertMarks();
if (wDiff.debug === true) {
console.log('Unlinked: ', unlink);
this.debugGroups('Groups');
this.debugBlocks('Blocks');
}
return;
};
// TextDiff.getSameBlocks(): collect identical corresponding ('same') blocks from old text and sort by new text
// called from: .detectBlocks()
// calls: .wordCount()
// changes: .blocks
this.getSameBlocks = function () {
var blocks = this.blocks;
// clear blocks array
blocks.splice(0);
// cycle through old text to find matched (linked) blocks
var j = this.oldText.first;
var i = null;
while (j !== null) {
// skip 'del' blocks
while ( (j !== null) && (this.oldText.tokens[j].link === null) ) {
j = this.oldText.tokens[j].next;
}
// get 'same' block
if (j !== null) {
i = this.oldText.tokens[j].link;
var iStart = i;
var jStart = j;
//
var count = 0;
var unique = false;
var string = '';
while ( (i !== null) && (j !== null) && (this.oldText.tokens[j].link == i) ) {
var token = this.oldText.tokens[j].token;
count ++;
if (this.newText.tokens[i].unique === true) {
unique = true;
}
string += token;
i = this.newText.tokens[i].next;
j = this.oldText.tokens[j].next;
}
// save old text 'same' block
blocks.push({
oldBlock: blocks.length,
newBlock: null,
oldNumber: this.oldText.tokens[jStart].number,
newNumber: this.newText.tokens[iStart].number,
oldStart: jStart,
count: count,
unique: unique,
words: this.wordCount(string),
chars: string.length,
type: 'same',
section: null,
group: null,
fixed: null,
moved: null,
string: string
});
}
}
// sort blocks by new text token number
return a.newNumber - b.newNumber;
});
for (var block = 0; block < blocks.length; block ++) {
}
return;
};
// TextDiff.getSections(): collect independent block sections (no old/new crosses outside section) for per-section determination of non-moving (fixed) groups
// called from: .detectBlocks()
// changes: creates sections, blocks[].section
this.getSections = function () {
var blocks = this.blocks;
var sections = this.sections;
sections.splice(0);
// cycle through blocks
for (var block = 0; block < blocks.length; block ++) {
var sectionStart = block;
var oldMax = blocks[sectionStart].oldNumber;
var
// check right
for (var j = sectionStart + 1; j < blocks.length; j ++) {
// check
if (blocks[j].oldNumber > oldMax) {
oldMax = blocks[j].oldNumber;
}
else if (blocks[j].oldNumber
sectionOldMax = oldMax;
}
}
// save crossing sections
if (sectionEnd > sectionStart) {
// 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;
}
}
return;
//
// called from:
// calls: .wordCount()
// changes: creates .groups, .blocks[].group var blocks = this.blocks;
// clear groups array
groups.splice(0);
// cycle through blocks
for (var
var
var
var
// get word and char count of block
var maxWords = words;
var unique = blocks[block].unique;
var chars = blocks[block].chars;
// check
//
if (blocks[i].
break;
}
// get word and char count of block
if (blocks[i].words > maxWords) {
maxWords = blocks[i].words;
}
if (blocks[i].unique === true) {
unique = true;
}
words += blocks[i].words;
chars += blocks[i].chars;
groupEnd = i;
}
// save crossing group
if (groupEnd >= groupStart) {
// 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;
}
// save group
groups.push({
oldNumber: blocks[groupStart].oldNumber,
blockStart: groupStart,
blockEnd: groupEnd,
unique: unique,
maxWords: maxWords,
words: words,
chars: chars,
fixed: fixed,
});
block = groupEnd;
}
}
return;
//
// called from:
// calls:
// changes: .groups[].fixed, .blocks[].fixed
var blocks = this.blocks;
var groups = this.groups;
var
// 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
var cache = [];
var maxChars = 0;
var maxPath = null;
// start at each group of section
for (var i = groupStart; i <= groupEnd; i ++) {
var pathObj = this.findMaxPath(i, groupEnd, cache);
maxPath = pathObj.path;
maxChars = pathObj.chars;
}
}
// mark fixed groups
for (var i = 0; i < maxPath.length; i ++) {
var group = maxPath[i];
groups[group].fixed = true;
// mark fixed blocks
for (var block = groups[group].blockStart; block <= groups[group].blockEnd; block ++) {
blocks[block].fixed = true;
}
}
}
return;
//
// input: start
// called from: .setFixed()
// calls: itself recursively
// returns: returnObj, contains path and length
var groups = this.groups;
// 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 (deep copy)
var pathObj;
if (cache[i] !== undefined) {
pathObj = { path: cache[i].path.slice(), chars: cache[i].chars };
}
// get longest sub-path
else {
}
// select longest sub-path
if (pathObj.chars > maxChars) {
maxChars = pathObj.chars;
returnObj = pathObj;
}
}
returnObj.path.unshift(start);
returnObj.chars += groups[start].chars;
// save path to cache (deep copy)
if (cache[start] === undefined) {
cache[start] = { path: returnObj.path.slice(), chars: returnObj.chars };
}
return returnObj;
};
// TextDiff.getDelBlocks(): collect deletion ('del') blocks from old text
// called from: .detectBlocks()
// changes: .blocks
this.getDelBlocks = function () {
var blocks = this.blocks;
// cycle through old text to find matched (linked) blocks
var j = this.oldText.first;
while (j !== null) {
//
var count = 0;
var string = '';
count ++;
string += this.oldText.tokens[j].token;
j = this.oldText.tokens[j].next;
}
// save old text 'del' block
if (count !== 0) {
blocks.push({
oldBlock: null,
newBlock: null,
oldNumber: this.oldText.tokens[oldStart].number,
newNumber: null,
oldStart: oldStart,
count: count,
unique: false,
words: null,
chars: string.length,
type: 'del',
section: null,
group: null,
fixed: null,
moved: null,
string: string
});
}
// skip 'same' blocks
if (j !== null) {
i = this.oldText.tokens[j].link;
while ( (i !== null) && (j !== null) && (this.oldText.tokens[j].link == i) ) {
i = this.newText.tokens[i].next;
j = this.oldText.tokens[j].next;
}
}
}
return;
//
// called from:
// calls: .sortBlocks()
// changes: .blocks[].section/group/fixed/newNumber //
// deletion blocks move with fixed neighbor (new number +/- 0.1):
// old: 1 D 2 1 D 2
// /
// new: 1 D 2 1 D 2
// fixed: * *
// new number: 1 1.1 1.9 2
var blocks = this.blocks;
var blocksOld = blocks.slice();
blocksOld.sort(function(a, b) {
return a.oldNumber - b.oldNumber;
//
for (var block = 0; block < blocksOld.length; block ++) {
var delBlock = blocksOld[block];
//
if (delBlock.type != 'del') {
continue;
}
//
var
var prevBlock;
if (block > 0) {
prevBlockNumber = blocksOld[block - 1].newBlock;
prevBlock = blocks[prevBlockNumber];
}
//
var nextBlockNumber;
if (block < blocksOld.length - 1) {
nextBlockNumber = blocksOld[block + 1].newBlock;
nextBlock = blocks[nextBlockNumber];
}
// move after prev block if
var neighbor;
neighbor = prevBlock;
delBlock.newNumber = neighbor.newNumber + 0.1; }
// move before next block if fixed
else if ( (nextBlock !== undefined) && (nextBlock.fixed === true) ) {
neighbor = nextBlock;
delBlock.newNumber = neighbor.newNumber - 0.1;
}
// move
else if ( (prevBlock !== undefined) && (prevBlockNumber != groups[ prevBlock.group ].blockEnd) ) {
delBlock.newNumber = neighbor.newNumber + 0.1;
}
//
else if (
neighbor = nextBlock;
delBlock.
}
// move after closest previous fixed block
else {
for (var fixed = block; fixed >= 0; fixed --) {
if (blocksOld[fixed].fixed === true) {
neighbor = blocksOld[fixed];
delBlock.newNumber = neighbor.newNumber + 0.1;
break;
}
}
}
// move before first block
if (neighbor === undefined) {
delBlock.newNumber = -0.1;
}
// update 'del' block data
else {
delBlock.section = neighbor.section;
delBlock.group = neighbor.group;
delBlock.fixed = neighbor.fixed;
}
}
// sort 'del' blocks in and update groups
this.sortBlocks();
return;
};
// TextDiff.unlinkBlocks(): convert 'same' blocks in groups into 'ins'/'del' pairs if too short
// called from: .detectBlocks()
// calls: .unlinkSingleBlock()
// changes: .newText/oldText[].link
// returns: true if text tokens were unlinked
this.unlinkBlocks = function () {
var blocks = this.blocks;
// cycle through groups
var unlinked = false;
for (var group = 0; group < groups.length; group ++) {
var blockStart = groups[group].blockStart;
var blockEnd = groups[group].blockEnd;
// unlink whole group if no block is at least blockMinLength words long and unique
if ( (groups[group].maxWords < wDiff.blockMinLength) && (groups[group].unique === false) ) {
for (var block = blockStart; block <= blockEnd; block ++) {
if (blocks[block].type == 'same') {
unlinked = true;
}
Line 2,054 ⟶ 2,300:
}
// otherwise unlink block flanks
else {
// unlink blocks from start
for (var block = blockStart; block <= blockEnd; block ++) {
if
// stop unlinking if more than one word or a unique word
if ( (blocks[block].words > 1) ||
break;
}
unlinked = true;
blockStart = block;
Line 2,071 ⟶ 2,317:
}
// unlink blocks from end
for (var block = blockEnd; block > blockStart; block --) {
if (
// stop unlinking if more than one word or a unique word
Line 2,079 ⟶ 2,325:
break;
}
unlinked = true;
}
Line 2,085 ⟶ 2,331:
}
}
return unlinked;
};
//
// called from:
// changes: text.newText/oldText[].link
// unlink tokens
j =
};
//
// called from:
//
// changes: .blocks
var blocks = this.blocks;
// cycle through new text to find insertion blocks
while (i !== null) {
//
i = this.newText.tokens[i].next;
}
//
if (i !== null) {
var string = '';
string += this.newText.tokens[i].token;
i = this.newText.tokens[i].next;
}
blocks.push({
newNumber: this.newText.tokens[iStart].number,
oldStart: null,
count: count,
unique: false,
words: null,
chars: string.length,
type: 'ins',
section: null,
group: null,
fixed: null,
moved: null,
string: string
});
}
}
// sort 'ins' blocks in and update groups
this.sortBlocks();
return;
};
//
// called from:
// changes: .blocks, .groups
var blocks = this.blocks;
var groups = this.groups;
// sort by newNumber, then by old number
blocks.sort(function(a, b) {
var comp = a.newNumber - b.newNumber;
if (comp === 0) {
comp = a.oldNumber - b.oldNumber;
}
return comp;
});
// 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;
}
}
return;
//
// called from:
// changes: .groups, .blocks[].fixed/group
var blocks = this.blocks;
// set group numbers of 'ins' blocks inside existing groups
for (var block = groups[group].blockStart; block <= groups[group].blockEnd; block ++) {
if (blocks[block].group === null) {
blocks[block].group = group;
blocks[block].fixed = fixed;
}
}
}
// skip existing groups
if (blocks[block].group === null) {
blocks[block].group = groups.length;
// save new single-block group
groups.push({
oldNumber: blocks[block].oldNumber,
blockStart: block,
blockEnd: block,
unique:
maxWords:
words:
chars:
fixed: blocks[block].fixed,
});
}
}
return;
//
// called from:
// changes: .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:
// group side:
var blocks = this.blocks;
var groups = this.groups;
var moved = [];
var color = 1;
// make shallow copy of blocks
var blocksOld = blocks.slice();
// enumerate copy
for (var i = 0; i < blocksOld.length; i ++) {
blocksOld[i].number = i;
}
//
blocksOld.sort(function(a, b) {
return a.oldNumber - b.oldNumber;
});
//
var lookupSorted = [];
for (var i = 0; i < blocksOld.length; i ++) {
lookupSorted[ blocksOld[i].number ] = i;
}
// cycle through groups (moved group)
for (var moved = 0; moved < groups.length; moved ++) {
var movedGroup = groups[moved];
if (movedGroup.fixed !== false) {
continue;
}
var movedOldNumber = movedGroup.oldNumber;
// find closest fixed
var
var leftChars = 0;
for (var block = lookupSorted[ groups[moved].blockStart ] - 1; block >= 0; block --) {
leftChars += blocksOld[block].chars;
if (blocksOld[block].fixed === true) {
fixedLeft = blocksOld[block];
break;
}
}
// find closest fixed
var fixedRight = null;
for (var block = lookupSorted[ groups[moved].blockEnd ] + 1; block < blocksOld.length; block ++) {
rightChars += blocksOld[block].chars;
if (blocksOld[block].fixed === true) {
fixedLeft = blocksOld[block];
break;
}
}
// no larger fixed
var
if (
}
// no smaller fixed
else if (
}
// group moved from between two closest fixed neighbors, moved left or right depending on char distance
else if (rightChars <= leftChars) {
}
// moved left
else {
}
// from left side of fixed group
var newNumber;
if (movedOldNumber < fixedBlock.oldNumber) {
newNumber = fixedBlock.newNumber - 0.1;
}
// from right side of fixed group
else {
newNumber = fixedBlock.newNumber + 0.1;
}
// insert 'mark' block
blocks.push({
oldBlock: null,
oldNumber: movedOldNumber,
newNumber: newNumber,
oldStart: null,
count: null,
unique: null,
words: null,
chars: 0,
type: 'mark',
section: null,
group: fixedBlock.group,
fixed: true,
moved: moved,
string: ''
});
// set group color
movedGroup.color = color;
movedGroup.movedFrom = fixedBlock.group;
color ++;
}
// sort mark blocks in and update groups
this.sortBlocks();
return;
};
// TextDiff.assembleDiff(): create html formatted diff text from block and group data
// input: version: 'new', 'old', show only one marked-up version
// returns: diff html string
// called from: .diff()
// calls: .htmlCustomize(), .htmlEscape(), .htmlFormatBlock(), .htmlFormat()
this.assembleDiff = function (version) {
var blocks = this.blocks;
var
// make shallow copy of groups and sort by blockStart
var groupsSort = groups.slice();
groupsSort.sort(function(a, b) {
return a.blockStart - b.blockStart;
});
//
// create group diffs
//
var htmlFrags = [];
for (var group = 0; group < groupsSort.length; group ++) {
var color = groupsSort[group].color;
var blockStart = groupsSort[group].blockStart;
var blockEnd = groupsSort[group].blockEnd;
//
var groupUnSort = blocks[blockStart].group;
if (groupsSort[group].movedFrom < groupUnSort) {
moveDir = 'left';
}
else {
}
}
// add
var html = '';
if (moveDir == 'left') {
html = this.htmlCustomize(wDiff.htmlBlockLeftStart, color);
}
else if (moveDir == 'right') {
}
htmlFrags.push(html);
}
//
for (var block = blockStart; block <= blockEnd; block ++) {
var html = '';
var type = blocks[block].type;
var string = blocks[block].string;
// html escape text string
string = this.htmlEscape(string);
// add 'same' (unchanged) text and moved block
if (type == 'same') {
if (color !== null) {
if (version != 'old') {
html = this.htmlFormatBlock(string);
}
}
else {
html = string;
}
}
// add 'del' text && (blocks[block].fixed == true)
else if ( (type == 'del') && (version != 'new') ) {
// for old version skip 'del' inside moved group
if ( (version != 'old') || (color === null) ) {
if (wDiff.regExpBlankBlock.test(string) === true) {
html = wDiff.htmlDeleteStartBlank;
}
else {
html = wDiff.htmlDeleteStart;
}
html += this.htmlFormatBlock(string) + wDiff.htmlDeleteEnd;
}
}
// add
else if (
if (wDiff.regExpBlankBlock.test(string) === true) {
html = wDiff.htmlInsertStartBlank;
}
else {
html = wDiff.htmlInsertStart;
}
html += this.htmlFormatBlock(string) + wDiff.htmlInsertEnd;
}
// add 'mark' code
else if ( (type == 'mark') && (version != 'new') ) {
var moved = blocks[block].moved;
var movedGroup = groups[moved];
var markColor = movedGroup.color;
// get moved block text ('same' and 'del')
var string = '';
for (var mark = movedGroup.blockStart; mark <= movedGroup.blockEnd; mark ++) {
if ( (blocks[mark].type == 'same') || (blocks[mark].type == 'del') ) {
string += blocks[mark].string;
}
}
// display as deletion at original position
if ( (wDiff.showBlockMoves === false) || (version == 'old') ) {
string = this.htmlEscape(string);
string = this.htmlFormatBlock(string);
if (version == 'old') {
if (movedGroup.blockStart < groupsSort[group].blockStart) {
html = this.htmlCustomize(wDiff.htmlBlockLeftStart, markColor) + string + wDiff.htmlBlockLeftEnd;
}
else {
html = this.htmlCustomize(wDiff.htmlBlockRightStart, markColor) + string + wDiff.htmlBlockRightEnd;
}
}
else {
if (wDiff.regExpBlankBlock.test(string) === true) {
html = wDiff.htmlDeleteStartBlank + string + wDiff.htmlDeleteEnd;
}
else {
html = wDiff.htmlDeleteStart + string + wDiff.htmlDeleteEnd;
}
}
}
//
else {
html = this.htmlCustomize(wDiff.htmlMarkLeft, markColor, string);
}
else {
html = this.htmlCustomize(wDiff.htmlMarkRight, markColor, string);
}
}
}
htmlFrags.push(html);
}
// add colored block end markup
if (
var html = '';
if (
}
else if (moveDir == 'right') {
}
htmlFrags.push(html);
}
}
// join fragments
this.html = htmlFrags.join('');
// markup newlines and spaces in blocks
this.htmlFormat();
return;
};
//
// TextDiff.htmlCustomize(): customize move indicator html: {block}: block number style, {mark}: mark number style, {class}: class number, {number}: block number, {title}: title attribute (popup)
// input: text (html or css code), number: block number, title: title attribute (popup) text
// returns: customized text
// called from: .assembleDiff()
this.htmlCustomize = function (text, number, title) {
if (wDiff.coloredBlocks === true) {
var blockStyle = wDiff.styleBlockColor[number];
if (blockStyle === undefined) {
blockStyle = '';
}
var markStyle = wDiff.styleMarkColor[number];
if (markStyle === undefined) {
markStyle = '';
}
text = text.replace(/\{block\}/g, ' ' + blockStyle);
text = text.replace(/\{mark\}/g, ' ' + markStyle);
text = text.replace(/\{class\}/g, number);
}
else {
text = text.replace(/\{block\}|\{mark\}|\{class\}/g, '');
}
text = text.replace(/\{
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 = this.htmlEscape(title);
title = title.replace(/\t/g, ' ');
title = title.replace(/ /g, ' ');
text = text.replace(/\{title\}/, ' title="' + title + '"');
}
else {
}
return text;
};
//
// input: html text
// returns: escaped html text
// called from:
};
//
// input: string
// returns: formatted string
// called from: .diff(), .assembleDiff()
// spare blanks in tags
string = string.replace(/(<[^>]*>)|( )/g, function (p, p1, p2) {
if (p2 == ' ') {
return wDiff.htmlSpace;
}
return p1;
});
string = string.replace(/\n/g, wDiff.htmlNewline);
return string;
};
// TextDiff.htmlFormat(): markup tabs, add container
// changes: .diff
// called from: .diff(), .assembleDiff()
this.htmlFormat = function () {
this.html = this.html.replace(/\t/g, wDiff.htmlTab);
this.html = wDiff.htmlContainerStart + wDiff.htmlFragmentStart + this.html + wDiff.htmlFragmentEnd + wDiff.htmlContainerEnd;
return;
};
// TextDiff.shortenOutput(): shorten diff html by removing unchanged sections
// input: diff html string from .diff()
// returns: shortened html with removed unchanged passages indicated by (...) or separator
this.shortenOutput = function () {
var html = this.html;
var diff = '';
// remove container by non-regExp replace
html = html.replace(wDiff.htmlContainerStart, '');
html = html.replace(wDiff.htmlFragmentStart, '');
html = html.replace(wDiff.htmlFragmentEnd, '');
html = html.replace(wDiff.htmlContainerEnd, '');
// scan for diff html tags
var regExpDiff = /<\w+\b[^>]*\bclass="[^">]*?\bwDiff(MarkLeft|MarkRight|BlockLeft|BlockRight|Delete|Insert)\b[^">]*"[^>]*>(.|\n)*?<!--wDiff\1-->/g;
var tagsStart = [];
var tagsEnd = [];
var i = 0;
var regExpMatch;
// save tag positions
while ( (regExpMatch = regExpDiff.exec(html)) !== null ) {
// combine consecutive diff tags
if ( (i > 0) && (tagsEnd[i - 1] == regExpMatch.index) ) {
tagsEnd[i - 1] = regExpMatch.index + regExpMatch[0].length;
}
else {
tagsStart[i] = regExpMatch.index;
tagsEnd[i] = regExpMatch.index + regExpMatch[0].length;
i ++;
}
}
//
if (
this.html = wDiff.htmlNoChange;
return;
}
// define regexps
var regExpLine = /^(\n+|.)|(\n+|.)$|\n+/g;
var regExpHeading = /(^|\n)(<[^>]+>)*(==+.+?==+|\{\||\|\}).*?\n?/g;
var regExpParagraph = /^(\n\n+|.)|(\n\n+|.)$|\n\n+/g;
var regExpBlank = /(<[^>]+>)*\s+/g;
// get line positions
var regExpMatch;
var lines = [];
while ( (regExpMatch = regExpLine.exec(html)) !== null) {
lines.push(regExpMatch.index);
}
headingsEnd.push(regExpMatch.index + regExpMatch[0].length);
}
while ( (regExpMatch = regExpParagraph.exec(html)) !== null ) {
paragraphs.push(regExpMatch.index);
}
var headingBefore = 0;
var paragraphBefore = 0;
var lineBefore = 0;
var lineMaxAfter = 0;
// cycle through diff tag start positions
for (var i = 0; i < tagsStart.length; i ++) {
// maximal lines to search before diff tag
var rangeStartMin = 0;
for (var j = lineMaxBefore; j < lines.length - 1; j ++) {
if (tagStart < lines[j + 1]) {
if (j - wDiff.linesBeforeMax >= 0) {
rangeStartMin = lines[j - wDiff.linesBeforeMax];
}
lineMaxBefore = j;
break;
}
}
//
if (rangeStart[i] === undefined) {
for (var j =
if (
break;
}
if (headings[j + 1] > tagStart) {
if ( (headings[j] > tagStart - wDiff.headingBefore) && (headings[j] > rangeStartMin) ) {
rangeStart[i] = headings[j];
rangeStartType[i] = 'heading';
headingBefore = j;
}
break;
}
}
}
// find last
if (rangeStart[i] === undefined) {
for (var j =
if (
break;
}
if (paragraphs[j + 1] > tagStart - wDiff.paragraphBeforeMin) {
if ( (paragraphs[j] > tagStart - wDiff.paragraphBeforeMax) && (paragraphs[j] > rangeStartMin) ) {
rangeStart[i] = paragraphs[j];
rangeStartType[i] = 'paragraph';
paragraphBefore = j;
}
break;
}
}
}
// find last line break before diff tag
if (rangeStart[i] === undefined) {
for (var j = lineBefore; j < lines.length - 1; j ++) {
if (lines[j + 1] > tagStart - wDiff.lineBeforeMin) {
if ( (lines[j] > tagStart - wDiff.lineBeforeMax) && (lines[j] > rangeStartMin) ) {
rangeStart[i] = lines[j];
rangeStartType[i] = 'line';
lineBefore = j;
}
break;
}
}
}
// find last
if (rangeStart[i] === undefined) {
var lastPos = tagStart - wDiff.blankBeforeMax;
if (
}
regExpBlank.lastIndex = lastPos;
while ( (regExpMatch = regExpBlank.exec(html)) !== null ) {
if (regExpMatch.index > tagStart - wDiff.blankBeforeMin) {
break;
}
lastPos = regExpMatch.index;
}
}
//
if (rangeStart[i] === undefined) {
if (tagStart - wDiff.charsBefore > rangeStartMin) {
rangeStartType[i] = 'chars';
}
}
//
if (rangeStart[i] === undefined) {
rangeStart[i] = rangeStartMin;
rangeStartType[i] = 'lines';
}
// maximal lines to search after diff tag
var rangeEndMax = html.length;
for (var j = lineMaxAfter; j < lines.length; j ++) {
if (lines[j] > tagEnd) {
if (j + wDiff.linesAfterMax < lines.length) {
rangeEndMax = lines[j + wDiff.linesAfterMax];
}
lineMaxAfter = j;
break;
}
}
//
if (
for (var j = headingAfter; j < headingsEnd.length; j ++) {
if (headingsEnd[j] > tagEnd) {
if ( (headingsEnd[j] < tagEnd + wDiff.headingAfter) && (headingsEnd[j] < rangeEndMax) ) {
rangeEnd[i] = headingsEnd[j];
rangeEndType[i] = 'heading';
paragraphAfter = j;
}
break;
}
}
}
// find first
if (rangeEnd[i] === undefined) {
for (var j =
if (
if ( (
rangeEnd[i] =
rangeEndType[i] = '
paragraphAfter = j;
}
break;
}
}
}
// find first
if (rangeEnd[i] === undefined) {
for (var j =
if (
if ( (
rangeEnd[i] =
rangeEndType[i] = '
}
break;
}
}
}
// find
if (rangeEnd[i] === undefined) {
regExpBlank.lastIndex = tagEnd + wDiff.blankAfterMin;
if (
if ( (
rangeEnd[i] =
rangeEndType[i] = '
}
}
}
//
if (rangeEnd[i] === undefined) {
rangeEnd[i] = tagEnd + wDiff.charsAfter;
rangeEndType[i] = 'chars';
}
}
// fixed number of
if (rangeEnd[i] === undefined) {
}
}
// remove overlaps, join close fragments
var fragmentStart = [];
var fragmentEnd = [];
var fragmentStartType = [];
var fragmentEndType = [];
fragmentStart[0] = rangeStart[0];
fragmentEnd[0] = rangeEnd[0];
fragmentStartType[0] = rangeStartType[0];
fragmentEndType[0] = rangeEndType[0];
var j = 1;
for (var i = 1; i < rangeStart.length; i ++) {
// get lines between fragments
var lines = 0;
if (fragmentEnd[j - 1] < rangeStart[i]) {
var join = html.substring(fragmentEnd[j - 1], rangeStart[i]);
lines = (join.match(/\n/g) || []).length;
}
if ( (rangeStart[i] > fragmentEnd[j - 1] + wDiff.fragmentJoinChars) || (lines > wDiff.fragmentJoinLines) ) {
fragmentStart[j] = rangeStart[i];
fragmentEnd[j] = rangeEnd[i];
fragmentStartType[j] = rangeStartType[i];
fragmentEndType[j] = rangeEndType[i];
j ++;
}
else {
fragmentEnd[j - 1] = rangeEnd[i];
fragmentEndType[j - 1] = rangeEndType[i];
}
}
for (var i = 0; i < fragmentStart.length; i ++) {
// get
var fragment = html.substring(fragmentStart[i], fragmentEnd[i]);
fragment = fragment.replace(/^\n+|\n+$/g, '');
// add inline marks for omitted chars and words
if (fragmentStart[i] > 0) {
if (fragmentStartType[i] == 'chars') {
fragment = wDiff.htmlOmittedChars + fragment;
}
else if (fragmentStartType[i] == 'blank') {
fragment = wDiff.htmlOmittedChars + ' ' + fragment;
}
}
if (fragmentEnd[i] < html.length) {
if (fragmentStartType[i] == 'chars') {
fragment = fragment + wDiff.htmlOmittedChars;
}
else if (fragmentStartType[i] == 'blank') {
fragment = fragment + ' ' + wDiff.htmlOmittedChars;
}
}
// remove leading and trailing empty lines
fragment = fragment.replace(/^\n+|\n+$/g, '');
// add fragment separator
if (i > 0) {
diff += wDiff.htmlSeparator;
}
// add fragment wrapper
diff += wDiff.htmlFragmentStart + fragment + wDiff.htmlFragmentEnd;
}
// add diff wrapper
diff = wDiff.htmlContainerStart + diff + wDiff.htmlContainerEnd;
this.html = diff;
return;
};
// wDiff.wordCount(): count words in string
// called from: .getGroups(), .getSameBlocks()
//
this.wordCount = function (string) {
return (string.match(wDiff.regExpWord) || []).length;
};
// TextDiff.debugBlocks(): dump blocks object for debugging
// input: text: title, group: block object (optional)
//
this.debugBlocks = function (text, blocks) {
if (blocks === undefined) {
blocks = this.blocks;
}
var dump = '\ni \toldBl \tnewBl \toldNm \tnewNm \toldSt \tcount \tuniq \twords \tchars \ttype \tsect \tgroup \tfixed \tmoved \tstring\n';
for (var i = 0; i < blocks.length; i ++) {
dump += i + ' \t' + blocks[i].oldBlock + ' \t' + blocks[i].newBlock + ' \t' + blocks[i].oldNumber + ' \t' + (blocks[i].newNumber || 'null').toString().substr(0, 6) + ' \t' + blocks[i].oldStart + ' \t' + blocks[i].count + ' \t' + blocks[i].unique + ' \t' + blocks[i].words + ' \t' + blocks[i].chars + ' \t' + blocks[i].type + ' \t' + blocks[i].section + ' \t' + blocks[i].group + ' \t' + blocks[i].fixed + ' \t' + blocks[i].moved + ' \t' + this.debugShortenString(blocks[i].string) + '\n';
}
console.log(text + ':\n' + dump);
};
// TextDiff.debugGroups(): dump groups object for debugging
// input: text: title, group: group object (optional)
//
this.debugGroups = function (text, groups) {
groups = this.groups;
}
var dump = '\ni \toldNm \tblSta \tblEnd \tuniq \tmaxWo \twords \tchars \tfixed \toldNm \tmFrom \tcolor\n';
for (var i = 0; i < groups.length; i ++) {
dump += i + ' \t' + groups[i].oldNumber + ' \t' + groups[i].blockStart + ' \t' + groups[i].blockEnd + ' \t' + groups[i].unique + ' \t' + groups[i].maxWords + ' \t' + groups[i].words + ' \t' + groups[i].chars + ' \t' + groups[i].fixed + ' \t' + groups[i].oldNumber + ' \t' + groups[i].movedFrom + ' \t' + groups[i].color + '\n';
}
console.log(text + ':\n' + dump);
};
// TextDiff.debugShortenString(): shorten string for dumping
// called from .debugBlocks, .debugGroups, Text.debugText
//
this.debugShortenString = function (string) {
if (typeof string != 'string') {
string = string.toString();
}
string = string.replace(/\n/g, '\\n');
string = string.replace(/\t/g, ' ');
var max = 100;
if (string.length > max) {
string = string.substr(0, max - 1 - 30) + '…' + string.substr(string.length - 30);
}
return '"' + string + '"';
};
// initialze text diff object
};
// wDiff.addScript(): add script to head
// called from: wDiff.init()
//
wDiff.
var script = document.createElement('script');
Line 3,007 ⟶ 3,318:
// wDiff.addStyleSheet(): add CSS rules to new style sheet, cross-browser >= IE6
// called from: wDiff.init()
//
wDiff.
var style = document.createElement('style');
Line 3,023 ⟶ 3,334:
document.getElementsByTagName('head')[0].appendChild(style);
return;
};
// initialize wDiff
wDiff.
// </syntaxhighlight>
| |||