Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
wikEd diff
// <syntaxhighlight lang="JavaScript">
// ==UserScript==
// @name wikEd diff
// @version 1.2.4
// @date October 23, 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
// ==/UserScript==
/**
* wikEd diff: inline-style difference engine with block move support
*
* Improved JavaScript diff library that returns html/css-formatted new text version with
* highlighted deletions, insertions, and block moves. It is compatible with all browsers and is
* not dependent on external libraries.
*
* WikEdDiff.php and the JavaScript library wikEd diff are synced one-to-one ports. Changes and
* fixes are to be applied to both versions.
*
* JavaScript library (mirror): https://en.wikipedia.org/wiki/User:Cacycle/diff
* JavaScript online tool: http://cacycle.altervista.org/wikEd-diff-tool.html
* MediaWiki extension: https://www.mediawiki.org/wiki/Extension:wikEdDiff
*
* This difference engine applies a word-based algorithm that uses unique words as anchor points
* to identify matching text and moved blocks (Paul Heckel: A technique for isolating differences
* between files. Communications of the ACM 21(4):264 (1978)).
*
* Additional features:
*
* - Visual inline style, changes are shown in a single output text
* - Block move detection and highlighting
* - Resolution down to characters level
* - Unicode and multilingual support
* - Stepwise split (paragraphs, lines, sentences, words, characters)
* - Recursive diff
* - Optimized code for resolving unmatched sequences
* - Minimization of length of moved blocks
* - Alignment of ambiguous unmatched sequences to next line break or word border
* - Clipping of unchanged irrelevant parts from the output (optional)
* - Fully customizable
* - Text split optimized for MediaWiki source texts
* - Well commented and documented code
*
* Datastructures (abbreviations from publication):
*
* class WikEdDiffText: diff text object (new or old version)
* .text text of version
* .words[] word count table
* .first index of first token in tokens list
* .last index of last token in tokens list
*
* .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 WikEdDiff: diff object
* .config[]: configuration settings, see top of code for customization options
* .regExp[]: all regular expressions
* .split regular expressions used for splitting text into tokens
* .htmlCode HTML code fragments used for creating the output
* .msg output messages
* .newText new text
* .oldText old text
* .maxWords word count of longest linked block
* .html diff html
* .error flag: result has not passed unit tests
* .bordersDown[] linked region borders downwards, [new index, old index]
* .bordersUp[] linked region borders upwards, [new index, old index]
* .symbols: symbols table for whole text at all refinement levels
* .token[] hash table 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)
* .oldCount old text token counter (OC)
* .newToken token index in text.newText.tokens
* .oldToken token index in text.oldText.tokens
* .linked flag: at least one unique token pair has been linked
*
* .blocks[]: array, block data (consecutive text tokens) in new text order
* .oldBlock number of block in old text order
* .newBlock number of block in new text order
* .oldNumber old text token number of first token
* .newNumber new text token number of first token
* .oldStart old text token index of first token
* .count number of tokens
* .unique contains unique linked token
* .words word count
* .chars char length
* .type '=', '-', '+', '|' (same, deletion, insertion, mark)
* .section section number
* .group group number of block
* .fixed belongs to a fixed (not moved) group
* .moved moved block group number corresponding with mark block
* .text text of block tokens
*
* .sections[]: array, block sections with no block move crosses outside a section
* .blockStart first block in section
* .blockEnd last block in section
* .groups[]: array, section blocks that are consecutive in old text order
* .oldNumber first block oldNumber
* .blockStart first block index
* .blockEnd last block index
* .unique contains unique linked token
* .maxWords word count of longest linked 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
*
* .fragments[]: diff fragment list ready for markup, abstraction layer for customization
* .text block or mark text
* .color moved block or mark color number
* .type '=', '-', '+' same, deletion, insertion
* '<', '>' mark left, mark right
* '(<', '(>', ')' block start and end
* '~', ' ~', '~ ' omission indicators
* '[', ']', ',' fragment start and end, fragment separator
* '{', '}' container start and end
*
*/
// JSHint options
/* jshint -W004, -W100, newcap: true, browser: true, jquery: true, sub: true, bitwise: true,
curly: true, evil: true, forin: true, freeze: true, globalstrict: true, immed: true,
latedef: true, loopfunc: true, quotmark: single, strict: true, undef: true */
/* global console */
// Turn on ECMAScript 5 strict mode
'use strict';
/** Define global objects. */
var wikEdDiffConfig;
var WED;
/**
* wikEd diff main class.
*
* @class WikEdDiff
*/
var WikEdDiff = function () {
/** @var array config Configuration and customization settings. */
this.config = {
/** Core diff settings (with default values). */
/**
* @var bool config.fullDiff
* Show complete un-clipped diff text (false)
*/
'fullDiff': false,
/**
* @var bool config.showBlockMoves
* Enable block move layout with highlighted blocks and marks at the original positions (true)
*/
'showBlockMoves': true,
/**
* @var bool config.charDiff
* Enable character-refined diff (true)
*/
'charDiff': true,
/**
* @var bool config.repeatedDiff
* Enable repeated diff to resolve problematic sequences (true)
*/
'repeatedDiff': true,
/**
* @var bool config.recursiveDiff
* Enable recursive diff to resolve problematic sequences (true)
*/
'recursiveDiff': true,
/**
* @var int config.recursionMax
* Maximum recursion depth (10)
*/
'recursionMax': 10,
/**
* @var bool config.unlinkBlocks
* Reject blocks if they are too short and their words are not unique,
* prevents fragmentated diffs for very different versions (true)
*/
'unlinkBlocks': true,
/**
* @var int config.unlinkMax
* Maximum number of rejection cycles (5)
*/
'unlinkMax': 5,
/**
* @var int config.blockMinLength
* Reject blocks if shorter than this number of real words (3)
*/
'blockMinLength': 3,
/**
* @var bool config.coloredBlocks
* Display blocks in differing colors (rainbow color scheme) (false)
*/
'coloredBlocks': false,
/**
* @var bool config.coloredBlocks
* Do not use UniCode block move marks (legacy browsers) (false)
*/
'noUnicodeSymbols': false,
/**
* @var bool config.stripTrailingNewline
* Strip trailing newline off of texts (true in .js, false in .php)
*/
'stripTrailingNewline': true,
/**
* @var bool config.debug
* Show debug infos and stats (block, group, and fragment data) in debug console (false)
*/
'debug': false,
/**
* @var bool config.timer
* Show timing results in debug console (false)
*/
'timer': false,
/**
* @var bool config.unitTesting
* Run unit tests to prove correct working, display results in debug console (false)
*/
'unitTesting': false,
/** RegExp character classes. */
// UniCode letter support for regexps
// From http://xregexp.com/addons/unicode/unicode-base.js v1.0.0
'regExpLetters':
'a-zA-Z0-9' + (
'00AA00B500BA00C0-00D600D8-00F600F8-02C102C6-02D102E0-02E402EC02EE0370-037403760377037A-' +
'037D03860388-038A038C038E-03A103A3-03F503F7-0481048A-05270531-055605590561-058705D0-05EA' +
'05F0-05F20620-064A066E066F0671-06D306D506E506E606EE06EF06FA-06FC06FF07100712-072F074D-' +
'07A507B107CA-07EA07F407F507FA0800-0815081A082408280840-085808A008A2-08AC0904-0939093D' +
'09500958-09610971-09770979-097F0985-098C098F09900993-09A809AA-09B009B209B6-09B909BD09CE' +
'09DC09DD09DF-09E109F009F10A05-0A0A0A0F0A100A13-0A280A2A-0A300A320A330A350A360A380A39' +
'0A59-0A5C0A5E0A72-0A740A85-0A8D0A8F-0A910A93-0AA80AAA-0AB00AB20AB30AB5-0AB90ABD0AD00AE0' +
'0AE10B05-0B0C0B0F0B100B13-0B280B2A-0B300B320B330B35-0B390B3D0B5C0B5D0B5F-0B610B710B83' +
'0B85-0B8A0B8E-0B900B92-0B950B990B9A0B9C0B9E0B9F0BA30BA40BA8-0BAA0BAE-0BB90BD00C05-0C0C' +
'0C0E-0C100C12-0C280C2A-0C330C35-0C390C3D0C580C590C600C610C85-0C8C0C8E-0C900C92-0CA80CAA-' +
'0CB30CB5-0CB90CBD0CDE0CE00CE10CF10CF20D05-0D0C0D0E-0D100D12-0D3A0D3D0D4E0D600D610D7A-' +
'0D7F0D85-0D960D9A-0DB10DB3-0DBB0DBD0DC0-0DC60E01-0E300E320E330E40-0E460E810E820E840E87' +
'0E880E8A0E8D0E94-0E970E99-0E9F0EA1-0EA30EA50EA70EAA0EAB0EAD-0EB00EB20EB30EBD0EC0-0EC4' +
'0EC60EDC-0EDF0F000F40-0F470F49-0F6C0F88-0F8C1000-102A103F1050-1055105A-105D106110651066' +
'106E-10701075-1081108E10A0-10C510C710CD10D0-10FA10FC-1248124A-124D1250-12561258125A-125D' +
'1260-1288128A-128D1290-12B012B2-12B512B8-12BE12C012C2-12C512C8-12D612D8-13101312-1315' +
'1318-135A1380-138F13A0-13F41401-166C166F-167F1681-169A16A0-16EA1700-170C170E-17111720-' +
'17311740-17511760-176C176E-17701780-17B317D717DC1820-18771880-18A818AA18B0-18F51900-191C' +
'1950-196D1970-19741980-19AB19C1-19C71A00-1A161A20-1A541AA71B05-1B331B45-1B4B1B83-1BA0' +
'1BAE1BAF1BBA-1BE51C00-1C231C4D-1C4F1C5A-1C7D1CE9-1CEC1CEE-1CF11CF51CF61D00-1DBF1E00-1F15' +
'1F18-1F1D1F20-1F451F48-1F4D1F50-1F571F591F5B1F5D1F5F-1F7D1F80-1FB41FB6-1FBC1FBE1FC2-1FC4' +
'1FC6-1FCC1FD0-1FD31FD6-1FDB1FE0-1FEC1FF2-1FF41FF6-1FFC2071207F2090-209C21022107210A-2113' +
'21152119-211D212421262128212A-212D212F-2139213C-213F2145-2149214E218321842C00-2C2E2C30-' +
'2C5E2C60-2CE42CEB-2CEE2CF22CF32D00-2D252D272D2D2D30-2D672D6F2D80-2D962DA0-2DA62DA8-2DAE' +
'2DB0-2DB62DB8-2DBE2DC0-2DC62DC8-2DCE2DD0-2DD62DD8-2DDE2E2F300530063031-3035303B303C3041-' +
'3096309D-309F30A1-30FA30FC-30FF3105-312D3131-318E31A0-31BA31F0-31FF3400-4DB54E00-9FCC' +
'A000-A48CA4D0-A4FDA500-A60CA610-A61FA62AA62BA640-A66EA67F-A697A6A0-A6E5A717-A71FA722-' +
'A788A78B-A78EA790-A793A7A0-A7AAA7F8-A801A803-A805A807-A80AA80C-A822A840-A873A882-A8B3' +
'A8F2-A8F7A8FBA90A-A925A930-A946A960-A97CA984-A9B2A9CFAA00-AA28AA40-AA42AA44-AA4BAA60-' +
'AA76AA7AAA80-AAAFAAB1AAB5AAB6AAB9-AABDAAC0AAC2AADB-AADDAAE0-AAEAAAF2-AAF4AB01-AB06AB09-' +
'AB0EAB11-AB16AB20-AB26AB28-AB2EABC0-ABE2AC00-D7A3D7B0-D7C6D7CB-D7FBF900-FA6DFA70-FAD9' +
'FB00-FB06FB13-FB17FB1DFB1F-FB28FB2A-FB36FB38-FB3CFB3EFB40FB41FB43FB44FB46-FBB1FBD3-FD3D' +
'FD50-FD8FFD92-FDC7FDF0-FDFBFE70-FE74FE76-FEFCFF21-FF3AFF41-FF5AFF66-FFBEFFC2-FFC7FFCA-' +
'FFCFFFD2-FFD7FFDA-FFDC'
).replace( /(\w{4})/g, '\\u$1' ),
// New line characters without and with \n and \r
'regExpNewLines': '\\u0085\\u2028',
'regExpNewLinesAll': '\\n\\r\\u0085\\u2028',
// Breaking white space characters without \n, \r, and \f
'regExpBlanks': ' \\t\\x0b\\u2000-\\u200b\\u202f\\u205f\\u3000',
// Full stops without '.'
'regExpFullStops':
'\\u0589\\u06D4\\u0701\\u0702\\u0964\\u0DF4\\u1362\\u166E\\u1803\\u1809' +
'\\u2CF9\\u2CFE\\u2E3C\\u3002\\uA4FF\\uA60E\\uA6F3\\uFE52\\uFF0E\\uFF61',
// New paragraph characters without \n and \r
'regExpNewParagraph': '\\f\\u2029',
// Exclamation marks without '!'
'regExpExclamationMarks':
'\\u01C3\\u01C3\\u01C3\\u055C\\u055C\\u07F9\\u1944\\u1944' +
'\\u203C\\u203C\\u2048\\u2048\\uFE15\\uFE57\\uFF01',
// Question marks without '?'
'regExpQuestionMarks':
'\\u037E\\u055E\\u061F\\u1367\\u1945\\u2047\\u2049' +
'\\u2CFA\\u2CFB\\u2E2E\\uA60F\\uA6F7\\uFE56\\uFF1F',
/** Clip settings. */
// Find clip position: characters from right
'clipHeadingLeft': 1500,
'clipParagraphLeftMax': 1500,
'clipParagraphLeftMin': 500,
'clipLineLeftMax': 1000,
'clipLineLeftMin': 500,
'clipBlankLeftMax': 1000,
'clipBlankLeftMin': 500,
'clipCharsLeft': 500,
// Find clip position: characters from right
'clipHeadingRight': 1500,
'clipParagraphRightMax': 1500,
'clipParagraphRightMin': 500,
'clipLineRightMax': 1000,
'clipLineRightMin': 500,
'clipBlankRightMax': 1000,
'clipBlankRightMin': 500,
'clipCharsRight': 500,
// Maximum number of lines to search for clip position
'clipLinesRightMax': 10,
'clipLinesLeftMax': 10,
// Skip clipping if ranges are too close
'clipSkipLines': 5,
'clipSkipChars': 1000,
// Css stylesheet
'cssMarkLeft': '',
'cssMarkRight': '',
'stylesheet':
// Insert
'.wikEdDiffInsert {' +
'font-weight: bold; background-color: #bbddff; ' +
'color: #222; border-radius: 0.25em; padding: 0.2em 1px; ' +
'} ' +
'.wikEdDiffInsertBlank { background-color: #66bbff; } ' +
'.wikEdDiffFragment:hover .wikEdDiffInsertBlank { background-color: #bbddff; } ' +
// Delete
'.wikEdDiffDelete {' +
'font-weight: bold; background-color: #ffe49c; ' +
'color: #222; border-radius: 0.25em; padding: 0.2em 1px; ' +
'} ' +
'.wikEdDiffDeleteBlank { background-color: #ffd064; } ' +
'.wikEdDiffFragment:hover .wikEdDiffDeleteBlank { background-color: #ffe49c; } ' +
// Block
'.wikEdDiffBlock {' +
'font-weight: bold; background-color: #e8e8e8; ' +
'border-radius: 0.25em; padding: 0.2em 1px; margin: 0 1px; ' +
'} ' +
'.wikEdDiffBlock { } ' +
'.wikEdDiffBlock0 { background-color: #ffff80; } ' +
'.wikEdDiffBlock1 { background-color: #d0ff80; } ' +
'.wikEdDiffBlock2 { background-color: #ffd8f0; } ' +
'.wikEdDiffBlock3 { background-color: #c0ffff; } ' +
'.wikEdDiffBlock4 { background-color: #fff888; } ' +
'.wikEdDiffBlock5 { background-color: #bbccff; } ' +
'.wikEdDiffBlock6 { background-color: #e8c8ff; } ' +
'.wikEdDiffBlock7 { background-color: #ffbbbb; } ' +
'.wikEdDiffBlock8 { background-color: #a0e8a0; } ' +
'.wikEdDiffBlockHighlight {' +
'background-color: #777; color: #fff; ' +
'border: solid #777; border-width: 1px 0; ' +
'} ' +
// Mark
'.wikEdDiffMarkLeft, .wikEdDiffMarkRight {' +
'font-weight: bold; background-color: #ffe49c; ' +
'color: #666; border-radius: 0.25em; padding: 0.2em; margin: 0 1px; ' +
'} ' +
'.wikEdDiffMarkLeft:before { content: "{cssMarkLeft}"; } ' +
'.wikEdDiffMarkRight:before { content: "{cssMarkRight}"; } ' +
'.wikEdDiffMarkLeft.wikEdDiffNoUnicode:before { content: "<"; } ' +
'.wikEdDiffMarkRight.wikEdDiffNoUnicode:before { content: ">"; } ' +
'.wikEdDiffMark { background-color: #e8e8e8; color: #666; } ' +
'.wikEdDiffMark0 { background-color: #ffff60; } ' +
'.wikEdDiffMark1 { background-color: #c8f880; } ' +
'.wikEdDiffMark2 { background-color: #ffd0f0; } ' +
'.wikEdDiffMark3 { background-color: #a0ffff; } ' +
'.wikEdDiffMark4 { background-color: #fff860; } ' +
'.wikEdDiffMark5 { background-color: #b0c0ff; } ' +
'.wikEdDiffMark6 { background-color: #e0c0ff; } ' +
'.wikEdDiffMark7 { background-color: #ffa8a8; } ' +
'.wikEdDiffMark8 { background-color: #98e898; } ' +
'.wikEdDiffMarkHighlight { background-color: #777; color: #fff; } ' +
// Wrappers
'.wikEdDiffContainer { } ' +
'.wikEdDiffFragment {' +
'white-space: pre-wrap; background: #fff; 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: 1em; margin: 0; ' +
'} ' +
'.wikEdDiffNoChange { background: #f0f0f0; border: 1px #bbb solid; border-radius: 0.5em; ' +
'line-height: 1.6; box-shadow: 2px 2px 2px #ddd; padding: 0.5em; margin: 1em 0; ' +
'text-align: center; ' +
'} ' +
'.wikEdDiffSeparator { margin-bottom: 1em; } ' +
'.wikEdDiffOmittedChars { } ' +
// Newline
'.wikEdDiffNewline:before { content: "¶"; color: transparent; } ' +
'.wikEdDiffBlock:hover .wikEdDiffNewline:before { color: #aaa; } ' +
'.wikEdDiffBlockHighlight .wikEdDiffNewline:before { color: transparent; } ' +
'.wikEdDiffBlockHighlight:hover .wikEdDiffNewline:before { color: #ccc; } ' +
'.wikEdDiffBlockHighlight:hover .wikEdDiffInsert .wikEdDiffNewline:before, ' +
'.wikEdDiffInsert:hover .wikEdDiffNewline:before' +
'{ color: #999; } ' +
'.wikEdDiffBlockHighlight:hover .wikEdDiffDelete .wikEdDiffNewline:before, ' +
'.wikEdDiffDelete:hover .wikEdDiffNewline:before' +
'{ color: #aaa; } ' +
// Tab
'.wikEdDiffTab { position: relative; } ' +
'.wikEdDiffTabSymbol { position: absolute; top: -0.2em; } ' +
'.wikEdDiffTabSymbol:before { content: "→"; font-size: smaller; color: #ccc; } ' +
'.wikEdDiffBlock .wikEdDiffTabSymbol:before { color: #aaa; } ' +
'.wikEdDiffBlockHighlight .wikEdDiffTabSymbol:before { color: #aaa; } ' +
'.wikEdDiffInsert .wikEdDiffTabSymbol:before { color: #aaa; } ' +
'.wikEdDiffDelete .wikEdDiffTabSymbol:before { color: #bbb; } ' +
// Space
'.wikEdDiffSpace { position: relative; } ' +
'.wikEdDiffSpaceSymbol { position: absolute; top: -0.2em; left: -0.05em; } ' +
'.wikEdDiffSpaceSymbol:before { content: "·"; color: transparent; } ' +
'.wikEdDiffBlock:hover .wikEdDiffSpaceSymbol:before { color: #999; } ' +
'.wikEdDiffBlockHighlight .wikEdDiffSpaceSymbol:before { color: transparent; } ' +
'.wikEdDiffBlockHighlight:hover .wikEdDiffSpaceSymbol:before { color: #ddd; } ' +
'.wikEdDiffBlockHighlight:hover .wikEdDiffInsert .wikEdDiffSpaceSymbol:before,' +
'.wikEdDiffInsert:hover .wikEdDiffSpaceSymbol:before ' +
'{ color: #888; } ' +
'.wikEdDiffBlockHighlight:hover .wikEdDiffDelete .wikEdDiffSpaceSymbol:before,' +
'.wikEdDiffDelete:hover .wikEdDiffSpaceSymbol:before ' +
'{ color: #999; } ' +
// Error
'.wikEdDiffError .wikEdDiffFragment,' +
'.wikEdDiffError .wikEdDiffNoChange' +
'{ background: #faa; }'
};
/** Add regular expressions to configuration settings. */
this.config.regExp = {
// RegExps for splitting text
'split': {
// Split into paragraphs, after double newlines
'paragraph': new RegExp(
'(\\r\\n|\\n|\\r){2,}|[' +
this.config.regExpNewParagraph +
']',
'g'
),
// Split into lines
'line': new RegExp(
'\\r\\n|\\n|\\r|[' +
this.config.regExpNewLinesAll +
']',
'g'
),
// Split into sentences /[^ ].*?[.!?:;]+(?= |$)/
'sentence': new RegExp(
'[^' +
this.config.regExpBlanks +
'].*?[.!?:;' +
this.config.regExpFullStops +
this.config.regExpExclamationMarks +
this.config.regExpQuestionMarks +
']+(?=[' +
this.config.regExpBlanks +
']|$)',
'g'
),
// Split into inline chunks
'chunk': new RegExp(
'\\[\\[[^\\[\\]\\n]+\\]\\]|' + // [[wiki link]]
'\\{\\{[^\\{\\}\\n]+\\}\\}|' + // {{template}}
'\\[[^\\[\\]\\n]+\\]|' + // [ext. link]
'<\\/?[^<>\\[\\]\\{\\}\\n]+>|' + // <html>
'\\[\\[[^\\[\\]\\|\\n]+\\]\\]\\||' + // [[wiki link|
'\\{\\{[^\\{\\}\\|\\n]+\\||' + // {{template|
'\\b((https?:|)\\/\\/)[^\\x00-\\x20\\s"\\[\\]\\x7f]+', // link
'g'
),
// Split into words, multi-char markup, and chars
// regExpLetters speed-up: \\w+
'word': new RegExp(
'(\\w+|[_' +
this.config.regExpLetters +
'])+([\'’][_' +
this.config.regExpLetters +
']*)*|\\[\\[|\\]\\]|\\{\\{|\\}\\}|&\\w+;|\'\'\'|\'\'|==+|\\{\\||\\|\\}|\\|-|.',
'g'
),
// Split into chars
'character': /./g
},
// RegExp to detect blank tokens
'blankOnlyToken': new RegExp(
'[^' +
this.config.regExpBlanks +
this.config.regExpNewLinesAll +
this.config.regExpNewParagraph +
']'
),
// RegExps for sliding gaps: newlines and space/word breaks
'slideStop': new RegExp(
'[' +
this.config.regExpNewLinesAll +
this.config.regExpNewParagraph +
']$'
),
'slideBorder': new RegExp(
'[' +
this.config.regExpBlanks +
']$'
),
// RegExps for counting words
'countWords': new RegExp(
'(\\w+|[_' +
this.config.regExpLetters +
'])+([\'’][_' +
this.config.regExpLetters +
']*)*',
'g'
),
'countChunks': new RegExp(
'\\[\\[[^\\[\\]\\n]+\\]\\]|' + // [[wiki link]]
'\\{\\{[^\\{\\}\\n]+\\}\\}|' + // {{template}}
'\\[[^\\[\\]\\n]+\\]|' + // [ext. link]
'<\\/?[^<>\\[\\]\\{\\}\\n]+>|' + // <html>
'\\[\\[[^\\[\\]\\|\\n]+\\]\\]\\||' + // [[wiki link|
'\\{\\{[^\\{\\}\\|\\n]+\\||' + // {{template|
'\\b((https?:|)\\/\\/)[^\\x00-\\x20\\s"\\[\\]\\x7f]+', // link
'g'
),
// RegExp detecting blank-only and single-char blocks
'blankBlock': /^([^\t\S]+|[^\t])$/,
// RegExps for clipping
'clipLine': new RegExp(
'[' + this.config.regExpNewLinesAll +
this.config.regExpNewParagraph +
']+',
'g'
),
'clipHeading': new RegExp(
'( ^|\\n)(==+.+?==+|\\{\\||\\|\\}).*?(?=\\n|$)', 'g' ),
'clipParagraph': new RegExp(
'( (\\r\\n|\\n|\\r){2,}|[' +
this.config.regExpNewParagraph +
'])+',
'g'
),
'clipBlank': new RegExp(
'[' +
this.config.regExpBlanks + ']+',
'g'
),
'clipTrimNewLinesLeft': new RegExp(
'[' +
this.config.regExpNewLinesAll +
this.config.regExpNewParagraph +
']+$',
'g'
),
'clipTrimNewLinesRight': new RegExp(
'^[' +
this.config.regExpNewLinesAll +
this.config.regExpNewParagraph +
']+',
'g'
),
'clipTrimBlanksLeft': new RegExp(
'[' +
this.config.regExpBlanks +
this.config.regExpNewLinesAll +
this.config.regExpNewParagraph +
']+$',
'g'
),
'clipTrimBlanksRight': new RegExp(
'^[' +
this.config.regExpBlanks +
this.config.regExpNewLinesAll +
this.config.regExpNewParagraph +
']+',
'g'
)
};
/** Add messages to configuration settings. */
this.config.msg = {
'wiked-diff-empty': '(No difference)',
'wiked-diff-same': '=',
'wiked-diff-ins': '+',
'wiked-diff-del': '-',
'wiked-diff-block-left': '',
'wiked-diff-block-right': '',
'wiked-diff-block-left-nounicode': '<',
'wiked-diff-block-right-nounicode': '>',
'wiked-diff-error': 'Error: diff not consistent with versions!'
};
/**
* Add output html fragments to configuration settings.
* Dynamic replacements:
* {number}: class/color/block/mark/id number
* {title}: title attribute (popup)
* {nounicode}: noUnicodeSymbols fallback
*/
this.config.htmlCode = {
'noChangeStart':
'<div class="wikEdDiffNoChange" title="' +
this.config.msg['wiked-diff-same'] +
'">',
'noChangeEnd': '</div>',
'containerStart': '<div class="wikEdDiffContainer" id="wikEdDiffContainer">',
'containerEnd': '</div>',
'fragmentStart': '<pre class="wikEdDiffFragment" style="white-space: pre-wrap;">',
'fragmentEnd': '</pre>',
'separator': '<div class="wikEdDiffSeparator"></div>',
'insertStart':
'<span class="wikEdDiffInsert" title="' +
this.config.msg['wiked-diff-ins'] +
'">',
'insertStartBlank':
'<span class="wikEdDiffInsert wikEdDiffInsertBlank" title="' +
this.config.msg['wiked-diff-ins'] +
'">',
'insertEnd': '</span>',
'deleteStart':
'<span class="wikEdDiffDelete" title="' +
this.config.msg['wiked-diff-del'] +
'">',
'deleteStartBlank':
'<span class="wikEdDiffDelete wikEdDiffDeleteBlank" title="' +
this.config.msg['wiked-diff-del'] +
'">',
'deleteEnd': '</span>',
'blockStart':
'<span class="wikEdDiffBlock"' +
'title="{title}" id="wikEdDiffBlock{number}"' +
'onmouseover="wikEdDiffBlockHandler(undefined, this, \'mouseover\');">',
'blockColoredStart':
'<span class="wikEdDiffBlock wikEdDiffBlock wikEdDiffBlock{number}"' +
'title="{title}" id="wikEdDiffBlock{number}"' +
'onmouseover="wikEdDiffBlockHandler(undefined, this, \'mouseover\');">',
'blockEnd': '</span>',
'markLeft':
'<span class="wikEdDiffMarkLeft{nounicode}"' +
'title="{title}" id="wikEdDiffMark{number}"' +
'onmouseover="wikEdDiffBlockHandler(undefined, this, \'mouseover\');"></span>',
'markLeftColored':
'<span class="wikEdDiffMarkLeft{nounicode} wikEdDiffMark wikEdDiffMark{number}"' +
'title="{title}" id="wikEdDiffMark{number}"' +
'onmouseover="wikEdDiffBlockHandler(undefined, this, \'mouseover\');"></span>',
'markRight':
'<span class="wikEdDiffMarkRight{nounicode}"' +
'title="{title}" id="wikEdDiffMark{number}"' +
'onmouseover="wikEdDiffBlockHandler(undefined, this, \'mouseover\');"></span>',
'markRightColored':
'<span class="wikEdDiffMarkRight{nounicode} wikEdDiffMark wikEdDiffMark{number}"' +
'title="{title}" id="wikEdDiffMark{number}"' +
'onmouseover="wikEdDiffBlockHandler(undefined, this, \'mouseover\');"></span>',
'newline': '<span class="wikEdDiffNewline">\n</span>',
'tab': '<span class="wikEdDiffTab"><span class="wikEdDiffTabSymbol"></span>\t</span>',
'space': '<span class="wikEdDiffSpace"><span class="wikEdDiffSpaceSymbol"></span> </span>',
'omittedChars': '<span class="wikEdDiffOmittedChars">…</span>',
'errorStart': '<div class="wikEdDiffError" title="Error: diff not consistent with versions!">',
'errorEnd': '</div>'
};
/*
* Add JavaScript event handler function to configuration settings
* Highlights corresponding block and mark elements on hover and jumps between them on click
* Code for use in non-jQuery environments and legacy browsers (at least IE 8 compatible)
*
* @option Event|undefined event Browser event if available
* @option element Node DOM node
* @option type string Event type
*/
this.config.blockHandler = function ( event, element, type ) {
// IE compatibility
if ( event === undefined && window.event !== undefined ) {
event = window.event;
}
// Get mark/block elements
var number = element.id.replace( /\D/g, '' );
var block = document.getElementById( 'wikEdDiffBlock' + number );
var mark = document.getElementById( 'wikEdDiffMark' + number );
if ( block === null || mark === null ) {
return;
}
// Highlight corresponding mark/block pairs
if ( type === 'mouseover' ) {
element.onmouseover = null;
element.onmouseout = function ( event ) {
window.wikEdDiffBlockHandler( event, element, 'mouseout' );
};
element.onclick = function ( event ) {
window.wikEdDiffBlockHandler( event, element, 'click' );
};
block.className += ' wikEdDiffBlockHighlight';
mark.className += ' wikEdDiffMarkHighlight';
}
// Remove mark/block highlighting
if ( type === 'mouseout' || type === 'click' ) {
element.onmouseout = null;
element.onmouseover = function ( event ) {
window.wikEdDiffBlockHandler( event, element, 'mouseover' );
};
// Reset, allow outside container (e.g. legend)
if ( type !== 'click' ) {
block.className = block.className.replace( / wikEdDiffBlockHighlight/g, '' );
mark.className = mark.className.replace( / wikEdDiffMarkHighlight/g, '' );
// GetElementsByClassName
var container = document.getElementById( 'wikEdDiffContainer' );
if ( container !== null ) {
var spans = container.getElementsByTagName( 'span' );
var spansLength = spans.length;
for ( var i = 0; i < spansLength; i ++ ) {
if ( spans[i] !== block && spans[i] !== mark ) {
if ( spans[i].className.indexOf( ' wikEdDiffBlockHighlight' ) !== -1 ) {
spans[i].className = spans[i].className.replace( / wikEdDiffBlockHighlight/g, '' );
}
else if ( spans[i].className.indexOf( ' wikEdDiffMarkHighlight') !== -1 ) {
spans[i].className = spans[i].className.replace( / wikEdDiffMarkHighlight/g, '' );
}
}
}
}
}
}
// Scroll to corresponding mark/block element
if ( type === 'click' ) {
// Get corresponding element
var corrElement;
if ( element === block ) {
corrElement = mark;
}
else {
corrElement = block;
}
// Get element height (getOffsetTop)
var corrElementPos = 0;
var node = corrElement;
do {
corrElementPos += node.offsetTop;
} while ( ( node = node.offsetParent ) !== null );
// Get scroll height
var top;
if ( window.pageYOffset !== undefined ) {
top = window.pageYOffset;
}
else {
top = document.documentElement.scrollTop;
}
// Get cursor pos
var cursor;
if ( event.pageY !== undefined ) {
cursor = event.pageY;
}
else if ( event.clientY !== undefined ) {
cursor = event.clientY + top;
}
// Get line height
var line = 12;
if ( window.getComputedStyle !== undefined ) {
line = parseInt( window.getComputedStyle( corrElement ).getPropertyValue( 'line-height' ) );
}
// Scroll element under mouse cursor
window.scroll( 0, corrElementPos + top - cursor + line / 2 );
}
return;
};
/** Internal data structures. */
/** @var WikEdDiffText newText New text version object with text and token list */
this.newText = null;
/** @var WikEdDiffText oldText Old text version object with text and token list */
this.oldText = null;
/** @var object symbols Symbols table for whole text at all refinement levels */
this.symbols = {
token: [],
hashTable: {},
linked: false
};
/** @var array bordersDown Matched region borders downwards */
this.bordersDown = [];
/** @var array bordersUp Matched region borders upwards */
this.bordersUp = [];
/** @var array blocks Block data (consecutive text tokens) in new text order */
this.blocks = [];
/** @var int maxWords Maximal detected word count of all linked blocks */
this.maxWords = 0;
/** @var array groups Section blocks that are consecutive in old text order */
this.groups = [];
/** @var array sections Block sections with no block move crosses outside a section */
this.sections = [];
/** @var object timer Debug timer array: string 'label' => float milliseconds. */
this.timer = {};
/** @var array recursionTimer Count time spent in recursion level in milliseconds. */
this.recursionTimer = [];
/** Output data. */
/** @var bool error Unit tests have detected a diff error */
this.error = false;
/** @var array fragments Diff fragment list for markup, abstraction layer for customization */
this.fragments = [];
/** @var string html Html code of diff */
this.html = '';
/**
* Constructor, initialize settings, load js and css.
*
* @param[in] object wikEdDiffConfig Custom customization settings
* @param[out] object config Settings
*/
this.init = function () {
// Import customizations from wikEdDiffConfig{}
if ( typeof wikEdDiffConfig === 'object' ) {
this.deepCopy( wikEdDiffConfig, this.config );
}
// Add CSS stylescheet
this.addStyleSheet( this.config.stylesheet );
// Load block handler script
if ( this.config.showBlockMoves === true ) {
// Add block handler to head if running under Greasemonkey
if ( typeof GM_info === 'object' ) {
var script = 'var wikEdDiffBlockHandler = ' + this.config.blockHandler.toString() + ';';
this.addScript( script );
}
else {
window.wikEdDiffBlockHandler = this.config.blockHandler;
}
}
return;
};
/**
* Main diff method.
*
* @param string oldString Old text version
* @param string newString New text version
* @param[out] array fragment
* Diff fragment list ready for markup, abstraction layer for customized diffs
* @param[out] string html Html code of diff
* @return string Html code of diff
*/
this.diff = function ( oldString, newString ) {
// Start total timer
if ( this.config.timer === true ) {
this.time( 'total' );
}
// Start diff timer
if ( this.config.timer === true ) {
this.time( 'diff' );
}
// Reset error flag
this.error = false;
// Strip trailing newline (.js only)
if ( this.config.stripTrailingNewline === true ) {
if ( newString.substr( -1 ) === '\n' && oldString.substr( -1 === '\n' ) ) {
newString = newString.substr( 0, newString.length - 1 );
oldString = oldString.substr( 0, oldString.length - 1 );
}
}
// Load version strings into WikEdDiffText objects
this.newText = new WikEdDiff.WikEdDiffText( newString, this );
this.oldText = new WikEdDiff.WikEdDiffText( oldString, this );
// Trap trivial changes: no change
if ( this.newText.text === this.oldText.text ) {
this.html =
this.config.htmlCode.containerStart +
this.config.htmlCode.noChangeStart +
this.htmlEscape( this.config.msg['wiked-diff-empty'] ) +
this.config.htmlCode.noChangeEnd +
this.config.htmlCode.containerEnd;
return this.html;
}
// Trap trivial changes: old text deleted
if (
this.oldText.text === '' || (
this.oldText.text === '\n' &&
( this.newText.text.charAt( this.newText.text.length - 1 ) === '\n' )
)
) {
this.html =
this.config.htmlCode.containerStart +
this.config.htmlCode.fragmentStart +
this.config.htmlCode.insertStart +
this.htmlEscape( this.newText.text ) +
this.config.htmlCode.insertEnd +
this.config.htmlCode.fragmentEnd +
this.config.htmlCode.containerEnd;
return this.html;
}
// Trap trivial changes: new text deleted
if (
this.newText.text === '' || (
this.newText.text === '\n' &&
( this.oldText.text.charAt( this.oldText.text.length - 1 ) === '\n' )
)
) {
this.html =
this.config.htmlCode.containerStart +
this.config.htmlCode.fragmentStart +
this.config.htmlCode.deleteStart +
this.htmlEscape( this.oldText.text ) +
this.config.htmlCode.deleteEnd +
this.config.htmlCode.fragmentEnd +
this.config.htmlCode.containerEnd;
return this.html;
}
// Split new and old text into paragraps
if ( this.config.timer === true ) {
this.time( 'paragraph split' );
}
this.newText.splitText( 'paragraph' );
this.oldText.splitText( 'paragraph' );
if ( this.config.timer === true ) {
this.timeEnd( 'paragraph split' );
}
// Calculate diff
this.calculateDiff( 'line' );
// Refine different paragraphs into lines
if ( this.config.timer === true ) {
this.time( 'line split' );
}
this.newText.splitRefine( 'line' );
this.oldText.splitRefine( 'line' );
if ( this.config.timer === true ) {
this.timeEnd( 'line split' );
}
// Calculate refined diff
this.calculateDiff( 'line' );
// Refine different lines into sentences
if ( this.config.timer === true ) {
this.time( 'sentence split' );
}
this.newText.splitRefine( 'sentence' );
this.oldText.splitRefine( 'sentence' );
if ( this.config.timer === true ) {
this.timeEnd( 'sentence split' );
}
// Calculate refined diff
this.calculateDiff( 'sentence' );
// Refine different sentences into chunks
if ( this.config.timer === true ) {
this.time( 'chunk split' );
}
this.newText.splitRefine( 'chunk' );
this.oldText.splitRefine( 'chunk' );
if ( this.config.timer === true ) {
this.timeEnd( 'chunk split' );
}
// Calculate refined diff
this.calculateDiff( 'chunk' );
// Refine different chunks into words
if ( this.config.timer === true ) {
this.time( 'word split' );
}
this.newText.splitRefine( 'word' );
this.oldText.splitRefine( 'word' );
if ( this.config.timer === true ) {
this.timeEnd( 'word split' );
}
// Calculate refined diff information with recursion for unresolved gaps
this.calculateDiff( 'word', true );
// Slide gaps
if ( this.config.timer === true ) {
this.time( 'word slide' );
}
this.slideGaps( this.newText, this.oldText );
this.slideGaps( this.oldText, this.newText );
if ( this.config.timer === true ) {
this.timeEnd( 'word slide' );
}
// Split tokens into chars
if ( this.config.charDiff === true ) {
// Split tokens into chars in selected unresolved gaps
if ( this.config.timer === true ) {
this.time( 'character split' );
}
this.splitRefineChars();
if ( this.config.timer === true ) {
this.timeEnd( 'character split' );
}
// Calculate refined diff information with recursion for unresolved gaps
this.calculateDiff( 'character', true );
// Slide gaps
if ( this.config.timer === true ) {
this.time( 'character slide' );
}
this.slideGaps( this.newText, this.oldText );
this.slideGaps( this.oldText, this.newText );
if ( this.config.timer === true ) {
this.timeEnd( 'character slide' );
}
}
// Free memory
this.symbols = undefined;
this.bordersDown = undefined;
this.bordersUp = undefined;
this.newText.words = undefined;
this.oldText.words = undefined;
// Enumerate token lists
this.newText.enumerateTokens();
this.oldText.enumerateTokens();
// Detect moved blocks
if ( this.config.timer === true ) {
this.time( 'blocks' );
}
this.detectBlocks();
if ( this.config.timer === true ) {
this.timeEnd( 'blocks' );
}
// Free memory
this.newText.tokens = undefined;
this.oldText.tokens = undefined;
// Assemble blocks into fragment table
this.getDiffFragments();
// Free memory
this.blocks = undefined;
this.groups = undefined;
this.sections = undefined;
// Stop diff timer
if ( this.config.timer === true ) {
this.timeEnd( 'diff' );
}
// Unit tests
if ( this.config.unitTesting === true ) {
// Test diff to test consistency between input and output
if ( this.config.timer === true ) {
this.time( 'unit tests' );
}
this.unitTests();
if ( this.config.timer === true ) {
this.timeEnd( 'unit tests' );
}
}
// Clipping
if ( this.config.fullDiff === false ) {
// Clipping unchanged sections from unmoved block text
if ( this.config.timer === true ) {
this.time( 'clip' );
}
this.clipDiffFragments();
if ( this.config.timer === true ) {
this.timeEnd( 'clip' );
}
}
// Create html formatted diff code from diff fragments
if ( this.config.timer === true ) {
this.time( 'html' );
}
this.getDiffHtml();
if ( this.config.timer === true ) {
this.timeEnd( 'html' );
}
// No change
if ( this.html === '' ) {
this.html =
this.config.htmlCode.containerStart +
this.config.htmlCode.noChangeStart +
this.htmlEscape( this.config.msg['wiked-diff-empty'] ) +
this.config.htmlCode.noChangeEnd +
this.config.htmlCode.containerEnd;
}
// Add error indicator
if ( this.error === true ) {
this.html = this.config.htmlCode.errorStart + this.html + this.config.htmlCode.errorEnd;
}
// Stop total timer
if ( this.config.timer === true ) {
this.timeEnd( 'total' );
}
return this.html;
};
/**
* Split tokens into chars in the following unresolved regions (gaps):
* - One token became connected or separated by space or dash (or any token)
* - 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
* Identical tokens including space separators will be linked,
* resulting in word-wise char-level diffs
*
* @param[in/out] WikEdDiffText newText, oldText Text object tokens list
*/
this.splitRefineChars = function () {
/** Find corresponding gaps. */
// Cycle through new text tokens list
var gaps = [];
var gap = null;
var i = this.newText.first;
var j = this.oldText.first;
while ( 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 through gaps and add old text gap data
var gapsLength = gaps.length;
for ( var gap = 0; gap < gapsLength; gap ++ ) {
// Cycle through old text tokens list
var j = gaps[gap].oldFirst;
while (
j !== null &&
this.oldText.tokens[j] !== null &&
this.oldText.tokens[j].link === null
) {
// Count old chars and tokens in gap
gaps[gap].oldLast = j;
gaps[gap].oldTokens ++;
j = this.oldText.tokens[j].next;
}
}
/** Select gaps of identical token number and strong similarity of all tokens. */
var gapsLength = gaps.length;
for ( var gap = 0; gap < gapsLength; 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 ) {
var token = this.newText.tokens[ gaps[gap].newFirst ].token;
var tokenFirst = this.oldText.tokens[ gaps[gap].oldFirst ].token;
var tokenLast = this.oldText.tokens[ gaps[gap].oldLast ].token;
if (
token.indexOf( tokenFirst ) !== 0 ||
token.indexOf( tokenLast ) !== token.length - tokenLast.length
) {
continue;
}
}
else if ( gaps[gap].oldTokens === 1 && gaps[gap].newTokens === 3 ) {
var token = this.oldText.tokens[ gaps[gap].oldFirst ].token;
var tokenFirst = this.newText.tokens[ gaps[gap].newFirst ].token;
var tokenLast = this.newText.tokens[ gaps[gap].newLast ].token;
if (
token.indexOf( tokenFirst ) !== 0 ||
token.indexOf( tokenLast ) !== token.length - tokenLast.length
) {
continue;
}
}
else {
continue;
}
gaps[gap].charSplit = true;
}
// Cycle through new text tokens list and set charSplit
else {
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 shorterToken;
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 in this gap
charSplit = false;
break;
}
}
}
}
// Same token length
else if ( newToken !== oldToken ) {
// Tokens less than 50 % identical
var ident = 0;
var tokenLength = shorterToken.length;
for ( var pos = 0; pos < tokenLength; 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 = this.newText.tokens[i].next;
j = this.oldText.tokens[j].next;
}
gaps[gap].charSplit = charSplit;
}
}
/** Refine words into chars in selected gaps. */
var gapsLength = gaps.length;
for ( var gap = 0; gap < gapsLength; gap ++ ) {
if ( gaps[gap].charSplit === true ) {
// Cycle through new text tokens list, link spaces, and split into chars
var i = gaps[gap].newFirst;
var j = gaps[gap].oldFirst;
var newGapLength = i - gaps[gap].newLast;
var oldGapLength = j - gaps[gap].oldLast;
while ( i !== null || j !== null ) {
// Link identical tokens (spaces) to keep char refinement to words
if (
newGapLength === oldGapLength &&
this.newText.tokens[i].token === this.oldText.tokens[j].token
) {
this.newText.tokens[i].link = j;
this.oldText.tokens[j].link = i;
}
// Refine words into chars
else {
if ( i !== null ) {
this.newText.splitText( 'character', i );
}
if ( j !== null ) {
this.oldText.splitText( 'character', j );
}
}
// Next list elements
if ( i === gaps[gap].newLast ) {
i = null;
}
if ( j === gaps[gap].oldLast ) {
j = null;
}
if ( i !== null ) {
i = this.newText.tokens[i].next;
}
if ( j !== null ) {
j = this.oldText.tokens[j].next;
}
}
}
}
return;
};
/**
* Move gaps with ambiguous identical fronts to last newline border or otherwise last word border.
*
* @param[in/out] wikEdDiffText text, textLinked These two are newText and oldText
*/
this.slideGaps = function ( text, textLinked ) {
var regExpSlideBorder = this.config.regExp.slideBorder;
var regExpSlideStop = this.config.regExp.slideStop;
// Cycle through tokens list
var i = text.first;
var gapStart = null;
while ( i !== null ) {
// Remember gap start
if ( gapStart === null && text.tokens[i].link === null ) {
gapStart = i;
}
// Find gap end
else if ( gapStart !== null && text.tokens[i].link !== null ) {
var gapFront = gapStart;
var gapBack = text.tokens[i].prev;
// Slide down as deep as possible
var front = gapFront;
var back = text.tokens[gapBack].next;
if (
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;
gapFront = text.tokens[gapFront].next;
gapBack = text.tokens[gapBack].next;
front = text.tokens[front].next;
back = text.tokens[back].next;
}
// Test slide up, remember last line break or word border
var front = text.tokens[gapFront].prev;
var back = gapBack;
var gapFrontBlankTest = regExpSlideBorder.test( text.tokens[gapFront].token );
var frontStop = front;
if ( text.tokens[back].link === null ) {
while (
front !== null &&
back !== null &&
text.tokens[front].link !== null &&
text.tokens[front].token === text.tokens[back].token
) {
if ( front !== null ) {
// Stop at line break
if ( regExpSlideStop.test( text.tokens[front].token ) === true ) {
frontStop = front;
break;
}
// Stop at first word border (blank/word or word/blank)
if (
regExpSlideBorder.test( text.tokens[front].token ) !== gapFrontBlankTest ) {
frontStop = front;
}
}
front = text.tokens[front].prev;
back = text.tokens[back].prev;
}
}
// Actually slide up to stop
var front = text.tokens[gapFront].prev;
var back = gapBack;
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;
}
i = text.tokens[i].next;
}
return;
};
/**
* Calculate diff information, can be called repeatedly during refining.
* 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 matching tokens
* Pass 4: connect adjacent identical tokens downwards
* Pass 5: connect adjacent identical tokens upwards
* Repeat with empty symbol table (against crossed-over gaps)
* Recursively diff still unresolved regions downwards with empty symbol table
* Recursively diff still unresolved regions upwards with empty symbol table
*
* @param array symbols Symbol table object
* @param string level Split level: 'paragraph', 'line', 'sentence', 'chunk', 'word', 'character'
*
* Optionally for recursive or repeated calls:
* @param bool repeating Currently repeating with empty symbol table
* @param bool recurse Enable recursion
* @param int newStart, newEnd, oldStart, oldEnd Text object tokens indices
* @param int recursionLevel Recursion level
* @param[in/out] WikEdDiffText newText, oldText Text object, tokens list link property
*/
this.calculateDiff = function (
level,
recurse,
repeating,
newStart,
oldStart,
up,
recursionLevel
) {
// Set defaults
if ( repeating === undefined ) { repeating = false; }
if ( recurse === undefined ) { recurse = false; }
if ( newStart === undefined ) { newStart = this.newText.first; }
if ( oldStart === undefined ) { oldStart = this.oldText.first; }
if ( up === undefined ) { up = false; }
if ( recursionLevel === undefined ) { recursionLevel = 0; }
// Start timers
if ( this.config.timer === true && repeating === false && recursionLevel === 0 ) {
this.time( level );
}
if ( this.config.timer === true && repeating === false ) {
this.time( level + recursionLevel );
}
// Get object symbols table and linked region borders
var symbols;
var bordersDown;
var bordersUp;
if ( recursionLevel === 0 && repeating === false ) {
symbols = this.symbols;
bordersDown = this.bordersDown;
bordersUp = this.bordersUp;
}
// Create empty local symbols table and linked region borders arrays
else {
symbols = {
token: [],
hashTable: {},
linked: false
};
bordersDown = [];
bordersUp = [];
}
// Updated versions of linked region borders
var bordersUpNext = [];
var bordersDownNext = [];
/**
* Pass 1: parse new text into symbol table.
*/
// Cycle through new text tokens list
var i = newStart;
while ( i !== null ) {
if ( this.newText.tokens[i].link === null ) {
// Add new entry to symbol table
var token = this.newText.tokens[i].token;
if ( Object.prototype.hasOwnProperty.call( symbols.hashTable, token ) === false ) {
symbols.hashTable[token] = symbols.token.length;
symbols.token.push( {
newCount: 1,
oldCount: 0,
newToken: i,
oldToken: null
} );
}
// Or update existing entry
else {
// Increment token counter for new text
var hashToArray = symbols.hashTable[token];
symbols.token[hashToArray].newCount ++;
}
}
// Stop after gap if recursing
else if ( recursionLevel > 0 ) {
break;
}
// Get next token
if ( up === false ) {
i = this.newText.tokens[i].next;
}
else {
i = this.newText.tokens[i].prev;
}
}
/**
* Pass 2: parse old text into symbol table.
*/
// Cycle through old text tokens list
var j = oldStart;
while ( j !== null ) {
if ( this.oldText.tokens[j].link === null ) {
// Add new entry to symbol table
var token = this.oldText.tokens[j].token;
if ( Object.prototype.hasOwnProperty.call( symbols.hashTable, token ) === false ) {
symbols.hashTable[token] = symbols.token.length;
symbols.token.push( {
newCount: 0,
oldCount: 1,
newToken: null,
oldToken: j
} );
}
// Or update existing entry
else {
// Increment token counter for old text
var hashToArray = symbols.hashTable[token];
symbols.token[hashToArray].oldCount ++;
// Add token number for old text
symbols.token[hashToArray].oldToken = j;
}
}
// Stop after gap if recursing
else if ( recursionLevel > 0 ) {
break;
}
// Get next token
if ( up === false ) {
j = this.oldText.tokens[j].next;
}
else {
j = this.oldText.tokens[j].prev;
}
}
/**
* Pass 3: connect unique tokens.
*/
// Cycle through symbol array
var symbolsLength = symbols.token.length;
for ( var i = 0; i < symbolsLength; i ++ ) {
// Find tokens in the symbol table that occur only once in both versions
if ( symbols.token[i].newCount === 1 && symbols.token[i].oldCount === 1 ) {
var newToken = symbols.token[i].newToken;
var oldToken = symbols.token[i].oldToken;
var newTokenObj = this.newText.tokens[newToken];
var oldTokenObj = this.oldText.tokens[oldToken];
// Connect from new to old and from old to new
if ( newTokenObj.link === null ) {
// Do not use spaces as unique markers
if (
this.config.regExp.blankOnlyToken.test( newTokenObj.token ) === true
) {
// Link new and old tokens
newTokenObj.link = oldToken;
oldTokenObj.link = newToken;
symbols.linked = true;
// Save linked region borders
bordersDown.push( [newToken, oldToken] );
bordersUp.push( [newToken, oldToken] );
// Check if token contains unique word
if ( recursionLevel === 0 ) {
var unique = false;
if ( level === 'character' ) {
unique = true;
}
else {
var token = newTokenObj.token;
var words =
( token.match( this.config.regExp.countWords ) || [] ).concat(
( token.match( this.config.regExp.countChunks ) || [] )
);
// Unique if longer than min block length
var wordsLength = words.length;
if ( wordsLength >= this.config.blockMinLength ) {
unique = true;
}
// Unique if it contains at least one unique word
else {
for ( var i = 0;i < wordsLength; i ++ ) {
var word = words[i];
if (
this.oldText.words[word] === 1 &&
this.newText.words[word] === 1 &&
Object.prototype.hasOwnProperty.call( this.oldText.words, word ) === true &&
Object.prototype.hasOwnProperty.call( this.newText.words, word ) === true
) {
unique = true;
break;
}
}
}
}
// Set unique
if ( unique === true ) {
newTokenObj.unique = true;
oldTokenObj.unique = true;
}
}
}
}
}
}
// Continue passes only if unique tokens have been linked previously
if ( symbols.linked === true ) {
/**
* Pass 4: connect adjacent identical tokens downwards.
*/
// Cycle through list of linked new text tokens
var bordersLength = bordersDown.length;
for ( var match = 0; match < bordersLength; match ++ ) {
var i = bordersDown[match][0];
var j = bordersDown[match][1];
// Next down
var iMatch = i;
var jMatch = j;
i = this.newText.tokens[i].next;
j = this.oldText.tokens[j].next;
// Cycle through new text list gap region downwards
while (
i !== null &&
j !== null &&
this.newText.tokens[i].link === null &&
this.oldText.tokens[j].link === null
) {
// Connect if same token
if ( this.newText.tokens[i].token === this.oldText.tokens[j].token ) {
this.newText.tokens[i].link = j;
this.oldText.tokens[j].link = i;
}
// Not a match yet, maybe in next refinement level
else {
bordersDownNext.push( [iMatch, jMatch] );
break;
}
// Next token down
iMatch = i;
jMatch = j;
i = this.newText.tokens[i].next;
j = this.oldText.tokens[j].next;
}
}
/**
* Pass 5: connect adjacent identical tokens upwards.
*/
// Cycle through list of connected new text tokens
var bordersLength = bordersUp.length;
for ( var match = 0; match < bordersLength; match ++ ) {
var i = bordersUp[match][0];
var j = bordersUp[match][1];
// Next up
var iMatch = i;
var jMatch = j;
i = this.newText.tokens[i].prev;
j = this.oldText.tokens[j].prev;
// Cycle through new text gap region upwards
while (
i !== null &&
j !== null &&
this.newText.tokens[i].link === null &&
this.oldText.tokens[j].link === null
) {
// Connect if same token
if ( this.newText.tokens[i].token === this.oldText.tokens[j].token ) {
this.newText.tokens[i].link = j;
this.oldText.tokens[j].link = i;
}
// Not a match yet, maybe in next refinement level
else {
bordersUpNext.push( [iMatch, jMatch] );
break;
}
// Next token up
iMatch = i;
jMatch = j;
i = this.newText.tokens[i].prev;
j = this.oldText.tokens[j].prev;
}
}
/**
* Connect adjacent identical tokens downwards from text start.
* Treat boundary as connected, stop after first connected token.
*/
// Only for full text diff
if ( recursionLevel === 0 && repeating === false ) {
// From start
var i = this.newText.first;
var j = this.oldText.first;
var iMatch = null;
var jMatch = null;
// Cycle through old text tokens 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;
iMatch = i;
jMatch = j;
i = this.newText.tokens[i].next;
j = this.oldText.tokens[j].next;
}
if ( iMatch !== null ) {
bordersDownNext.push( [iMatch, jMatch] );
}
// From end
i = this.newText.last;
j = this.oldText.last;
iMatch = null;
jMatch = null;
// Cycle through old text tokens 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;
iMatch = i;
jMatch = j;
i = this.newText.tokens[i].prev;
j = this.oldText.tokens[j].prev;
}
if ( iMatch !== null ) {
bordersUpNext.push( [iMatch, jMatch] );
}
}
// Save updated linked region borders to object
if ( recursionLevel === 0 && repeating === false ) {
this.bordersDown = bordersDownNext;
this.bordersUp = bordersUpNext;
}
// Merge local updated linked region borders into object
else {
this.bordersDown = this.bordersDown.concat( bordersDownNext );
this.bordersUp = this.bordersUp.concat( bordersUpNext );
}
/**
* Repeat once with empty symbol table to link hidden unresolved common tokens in cross-overs.
* ("and" in "and this a and b that" -> "and this a and b that")
*/
if ( repeating === false && this.config.repeatedDiff === true ) {
var repeat = true;
this.calculateDiff( level, recurse, repeat, newStart, oldStart, up, recursionLevel );
}
/**
* Refine by recursively diffing not linked regions with new symbol table.
* At word and character level only.
* Helps against gaps caused by addition of common tokens around sequences of common tokens.
*/
if (
recurse === true &&
this.config['recursiveDiff'] === true &&
recursionLevel < this.config.recursionMax
) {
/**
* Recursively diff gap downwards.
*/
// Cycle through list of linked region borders
var bordersLength = bordersDownNext.length;
for ( match = 0; match < bordersLength; match ++ ) {
var i = bordersDownNext[match][0];
var j = bordersDownNext[match][1];
// Next token down
i = this.newText.tokens[i].next;
j = this.oldText.tokens[j].next;
// Start recursion at first gap token pair
if (
i !== null &&
j !== null &&
this.newText.tokens[i].link === null &&
this.oldText.tokens[j].link === null
) {
var repeat = false;
var dirUp = false;
this.calculateDiff( level, recurse, repeat, i, j, dirUp, recursionLevel + 1 );
}
}
/**
* Recursively diff gap upwards.
*/
// Cycle through list of linked region borders
var bordersLength = bordersUpNext.length;
for ( match = 0; match < bordersLength; match ++ ) {
var i = bordersUpNext[match][0];
var j = bordersUpNext[match][1];
// Next token up
i = this.newText.tokens[i].prev;
j = this.oldText.tokens[j].prev;
// Start recursion at first gap token pair
if (
i !== null &&
j !== null &&
this.newText.tokens[i].link === null &&
this.oldText.tokens[j].link === null
) {
var repeat = false;
var dirUp = true;
this.calculateDiff( level, recurse, repeat, i, j, dirUp, recursionLevel + 1 );
}
}
}
}
// Stop timers
if ( this.config.timer === true && repeating === false ) {
if ( this.recursionTimer[recursionLevel] === undefined ) {
this.recursionTimer[recursionLevel] = 0;
}
this.recursionTimer[recursionLevel] += this.timeEnd( level + recursionLevel, true );
}
if ( this.config.timer === true && repeating === false && recursionLevel === 0 ) {
this.timeRecursionEnd( level );
this.timeEnd( level );
}
return;
};
/**
* Main method for processing raw diff data, extracting deleted, inserted, and moved blocks.
*
* 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: = . =-= = -= = . = = = = =
*
* @param[out] array groups Groups table object
* @param[out] array blocks Blocks table object
* @param[in/out] WikEdDiffText newText, oldText Text object tokens list
*/
this.detectBlocks = function () {
// Debug log
if ( this.config.debug === true ) {
this.oldText.debugText( 'Old text' );
this.newText.debugText( 'New text' );
}
// Collect identical corresponding ('=') blocks from old text and sort by new text
this.getSameBlocks();
// Collect independent block sections with no block move crosses outside a section
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();
// Convert groups to insertions/deletions if maximum block length is too short
// Only for more complex texts that actually have blocks of minimum block length
var unlinkCount = 0;
if (
this.config.unlinkBlocks === true &&
this.config.blockMinLength > 0 &&
this.maxWords >= this.config.blockMinLength
) {
if ( this.config.timer === true ) {
this.time( 'total unlinking' );
}
// Repeat as long as unlinking is possible
var unlinked = true;
while ( unlinked === true && unlinkCount < this.config.unlinkMax ) {
// Convert '=' to '+'/'-' pairs
unlinked = this.unlinkBlocks();
// Start over after conversion
if ( unlinked === true ) {
unlinkCount ++;
this.slideGaps( this.newText, this.oldText );
this.slideGaps( this.oldText, this.newText );
// Repeat block detection from start
this.maxWords = 0;
this.getSameBlocks();
this.getSections();
this.getGroups();
this.setFixed();
}
}
if ( this.config.timer === true ) {
this.timeEnd( 'total unlinking' );
}
}
// Collect deletion ('-') blocks from old text
this.getDelBlocks();
// Position '-' blocks into new text order
this.positionDelBlocks();
// Collect insertion ('+') blocks from new text
this.getInsBlocks();
// Set group numbers of '+' blocks
this.setInsGroups();
// Mark original positions of moved groups
this.insertMarks();
// Debug log
if ( this.config.timer === true || this.config.debug === true ) {
console.log( 'Unlink count: ', unlinkCount );
}
if ( this.config.debug === true ) {
this.debugGroups( 'Groups' );
this.debugBlocks( 'Blocks' );
}
return;
};
/**
* Collect identical corresponding matching ('=') blocks from old text and sort by new text.
*
* @param[in] WikEdDiffText newText, oldText Text objects
* @param[in/out] array blocks Blocks table object
*/
this.getSameBlocks = function () {
if ( this.config.timer === true ) {
this.time( 'getSameBlocks' );
}
var blocks = this.blocks;
// Clear blocks array
blocks.splice( 0 );
// Cycle through old text to find connected (linked, matched) blocks
var j = this.oldText.first;
var i = null;
while ( j !== null ) {
// Skip '-' blocks
while ( j !== null && this.oldText.tokens[j].link === null ) {
j = this.oldText.tokens[j].next;
}
// Get '=' block
if ( j !== null ) {
i = this.oldText.tokens[j].link;
var iStart = i;
var jStart = j;
// Detect matching blocks ('=')
var count = 0;
var unique = false;
var text = '';
while ( i !== null && j !== null && this.oldText.tokens[j].link === i ) {
text += this.oldText.tokens[j].token;
count ++;
if ( this.newText.tokens[i].unique === true ) {
unique = true;
}
i = this.newText.tokens[i].next;
j = this.oldText.tokens[j].next;
}
// Save old text '=' 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( text ),
chars: text.length,
type: '=',
section: null,
group: null,
fixed: null,
moved: null,
text: text
} );
}
}
// Sort blocks by new text token number
blocks.sort( function( a, b ) {
return a.newNumber - b.newNumber;
} );
// Number blocks in new text order
var blocksLength = blocks.length;
for ( var block = 0; block < blocksLength; block ++ ) {
blocks[block].newBlock = block;
}
if ( this.config.timer === true ) {
this.timeEnd( 'getSameBlocks' );
}
return;
};
/**
* Collect independent block sections with no block move crosses
* outside a section for per-section determination of non-moving fixed groups.
*
* @param[out] array sections Sections table object
* @param[in/out] array blocks Blocks table object, section property
*/
this.getSections = function () {
if ( this.config.timer === true ) {
this.time( 'getSections' );
}
var blocks = this.blocks;
var sections = this.sections;
// Clear sections array
sections.splice( 0 );
// Cycle through blocks
var blocksLength = blocks.length;
for ( var block = 0; block < blocksLength; block ++ ) {
var sectionStart = block;
var sectionEnd = block;
var oldMax = blocks[sectionStart].oldNumber;
var sectionOldMax = oldMax;
// Check right
for ( var j = sectionStart + 1; j < blocksLength; 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 ( 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;
}
}
if ( this.config.timer === true ) {
this.timeEnd( 'getSections' );
}
return;
};
/**
* Find groups of continuous old text blocks.
*
* @param[out] array groups Groups table object
* @param[in/out] array blocks Blocks table object, group property
*/
this.getGroups = function () {
if ( this.config.timer === true ) {
this.time( 'getGroups' );
}
var blocks = this.blocks;
var groups = this.groups;
// Clear groups array
groups.splice( 0 );
// Cycle through blocks
var blocksLength = blocks.length;
for ( var block = 0; block < blocksLength; block ++ ) {
var groupStart = block;
var groupEnd = block;
var oldBlock = blocks[groupStart].oldBlock;
// Get word and char count of block
var words = this.wordCount( blocks[block].text );
var maxWords = words;
var unique = blocks[block].unique;
var chars = blocks[block].chars;
// Check right
for ( var i = groupEnd + 1; i < blocksLength; 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
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,
movedFrom: null,
color: null
} );
block = groupEnd;
// Set global word count of longest linked block
if ( maxWords > this.maxWords ) {
this.maxWords = maxWords;
}
}
}
if ( this.config.timer === true ) {
this.timeEnd( 'getGroups' );
}
return;
};
/**
* Set longest sequence of increasing groups in sections as fixed (not moved).
*
* @param[in] array sections Sections table object
* @param[in/out] array groups Groups table object, fixed property
* @param[in/out] array blocks Blocks table object, fixed property
*/
this.setFixed = function () {
if ( this.config.timer === true ) {
this.time( 'setFixed' );
}
var blocks = this.blocks;
var groups = this.groups;
var sections = this.sections;
// Cycle through sections
var sectionsLength = sections.length;
for ( var section = 0; section < sectionsLength; 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 );
if ( pathObj.chars > maxChars ) {
maxPath = pathObj.path;
maxChars = pathObj.chars;
}
}
// Mark fixed groups
var maxPathLength = maxPath.length;
for ( var i = 0; i < maxPathLength; 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;
}
}
}
if ( this.config.timer === true ) {
this.timeEnd( 'setFixed' );
}
return;
};
/**
* Recusively find path of groups in increasing old group order with longest char length.
*
* @param int start Path start group
* @param int groupEnd Path last group
* @param array cache Cache object, contains returnObj for start
* @return array returnObj Contains path and char length
*/
this.findMaxPath = function ( start, groupEnd, cache ) {
var groups = this.groups;
// Find longest sub-path
var maxChars = 0;
var oldNumber = groups[start].oldNumber;
var returnObj = { path: [], chars: 0};
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 by recursion
else {
pathObj = this.findMaxPath( i, groupEnd, cache );
}
// Select longest sub-path
if ( pathObj.chars > maxChars ) {
maxChars = pathObj.chars;
returnObj = pathObj;
}
}
// Add current start to path
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;
};
/**
* Convert matching '=' blocks in groups into insertion/deletion ('+'/'-') pairs
* if too short and too common.
* Prevents fragmentated diffs for very different versions.
*
* @param[in] array blocks Blocks table object
* @param[in/out] WikEdDiffText newText, oldText Text object, linked property
* @param[in/out] array groups Groups table object
* @return bool True if text tokens were unlinked
*/
this.unlinkBlocks = function () {
var blocks = this.blocks;
var groups = this.groups;
// Cycle through groups
var unlinked = false;
var groupsLength = groups.length;
for ( var group = 0; group < groupsLength; 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 < this.config.blockMinLength && groups[group].unique === false ) {
for ( var block = blockStart; block <= blockEnd; block ++ ) {
if ( blocks[block].type === '=' ) {
this.unlinkSingleBlock( blocks[block] );
unlinked = true;
}
}
}
// Otherwise unlink block flanks
else {
// Unlink blocks from start
for ( var block = blockStart; block <= blockEnd; block ++ ) {
if ( blocks[block].type === '=' ) {
// Stop unlinking if more than one word or a unique word
if ( blocks[block].words > 1 || blocks[block].unique === true ) {
break;
}
this.unlinkSingleBlock( blocks[block] );
unlinked = true;
blockStart = block;
}
}
// Unlink blocks from end
for ( var block = blockEnd; block > blockStart; block -- ) {
if ( blocks[block].type === '=' ) {
// Stop unlinking if more than one word or a unique word
if (
blocks[block].words > 1 ||
( blocks[block].words === 1 && blocks[block].unique === true )
) {
break;
}
this.unlinkSingleBlock( blocks[block] );
unlinked = true;
}
}
}
}
return unlinked;
};
/**
* Unlink text tokens of single block, convert them into into insertion/deletion ('+'/'-') pairs.
*
* @param[in] array blocks Blocks table object
* @param[out] WikEdDiffText newText, oldText Text objects, link property
*/
this.unlinkSingleBlock = function ( block ) {
// Cycle through old text
var j = block.oldStart;
for ( var count = 0; count < block.count; count ++ ) {
// Unlink tokens
this.newText.tokens[ this.oldText.tokens[j].link ].link = null;
this.oldText.tokens[j].link = null;
j = this.oldText.tokens[j].next;
}
return;
};
/**
* Collect deletion ('-') blocks from old text.
*
* @param[in] WikEdDiffText oldText Old Text object
* @param[out] array blocks Blocks table object
*/
this.getDelBlocks = function () {
if ( this.config.timer === true ) {
this.time( 'getDelBlocks' );
}
var blocks = this.blocks;
// Cycle through old text to find connected (linked, matched) blocks
var j = this.oldText.first;
var i = null;
while ( j !== null ) {
// Collect '-' blocks
var oldStart = j;
var count = 0;
var text = '';
while ( j !== null && this.oldText.tokens[j].link === null ) {
count ++;
text += this.oldText.tokens[j].token;
j = this.oldText.tokens[j].next;
}
// Save old text '-' 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: text.length,
type: '-',
section: null,
group: null,
fixed: null,
moved: null,
text: text
} );
}
// Skip '=' 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;
}
}
}
if ( this.config.timer === true ) {
this.timeEnd( 'getDelBlocks' );
}
return;
};
/**
* Position deletion '-' blocks into new text order.
* Deletion blocks move with fixed reference:
* Old: 1 D 2 1 D 2
* / \ / \ \
* New: 1 D 2 1 D 2
* Fixed: * *
* newNumber: 1 1 2 2
*
* Marks '|' and deletions '-' get newNumber of reference block
* and are sorted around it by old text number.
*
* @param[in/out] array blocks Blocks table, newNumber, section, group, and fixed properties
*
*/
this.positionDelBlocks = function () {
if ( this.config.timer === true ) {
this.time( 'positionDelBlocks' );
}
var blocks = this.blocks;
var groups = this.groups;
// Sort shallow copy of blocks by oldNumber
var blocksOld = blocks.slice();
blocksOld.sort( function( a, b ) {
return a.oldNumber - b.oldNumber;
} );
// Cycle through blocks in old text order
var blocksOldLength = blocksOld.length;
for ( var block = 0; block < blocksOldLength; block ++ ) {
var delBlock = blocksOld[block];
// '-' block only
if ( delBlock.type !== '-' ) {
continue;
}
// Find fixed '=' reference block from original block position to position '-' block
// Similar to position marks '|' code
// Get old text prev block
var prevBlockNumber = null;
var prevBlock = null;
if ( block > 0 ) {
prevBlockNumber = blocksOld[block - 1].newBlock;
prevBlock = blocks[prevBlockNumber];
}
// Get old text next block
var nextBlockNumber = null;
var nextBlock = null;
if ( block < blocksOld.length - 1 ) {
nextBlockNumber = blocksOld[block + 1].newBlock;
nextBlock = blocks[nextBlockNumber];
}
// Move after prev block if fixed
var refBlock = null;
if ( prevBlock !== null && prevBlock.type === '=' && prevBlock.fixed === true ) {
refBlock = prevBlock;
}
// Move before next block if fixed
else if ( nextBlock !== null && nextBlock.type === '=' && nextBlock.fixed === true ) {
refBlock = nextBlock;
}
// Move after prev block if not start of group
else if (
prevBlock !== null &&
prevBlock.type === '=' &&
prevBlockNumber !== groups[ prevBlock.group ].blockEnd
) {
refBlock = prevBlock;
}
// Move before next block if not start of group
else if (
nextBlock !== null &&
nextBlock.type === '=' &&
nextBlockNumber !== groups[ nextBlock.group ].blockStart
) {
refBlock = nextBlock;
}
// Move after closest previous fixed block
else {
for ( var fixed = block; fixed >= 0; fixed -- ) {
if ( blocksOld[fixed].type === '=' && blocksOld[fixed].fixed === true ) {
refBlock = blocksOld[fixed];
break;
}
}
}
// Move before first block
if ( refBlock === null ) {
delBlock.newNumber = -1;
}
// Update '-' block data
else {
delBlock.newNumber = refBlock.newNumber;
delBlock.section = refBlock.section;
delBlock.group = refBlock.group;
delBlock.fixed = refBlock.fixed;
}
}
// Sort '-' blocks in and update groups
this.sortBlocks();
if ( this.config.timer === true ) {
this.timeEnd( 'positionDelBlocks' );
}
return;
};
/**
* Collect insertion ('+') blocks from new text.
*
* @param[in] WikEdDiffText newText New Text object
* @param[out] array blocks Blocks table object
*/
this.getInsBlocks = function () {
if ( this.config.timer === true ) {
this.time( 'getInsBlocks' );
}
var blocks = this.blocks;
// Cycle through new text to find insertion blocks
var i = this.newText.first;
while ( i !== null ) {
// Jump over linked (matched) block
while ( i !== null && this.newText.tokens[i].link !== null ) {
i = this.newText.tokens[i].next;
}
// Detect insertion blocks ('+')
if ( i !== null ) {
var iStart = i;
var count = 0;
var text = '';
while ( i !== null && this.newText.tokens[i].link === null ) {
count ++;
text += this.newText.tokens[i].token;
i = this.newText.tokens[i].next;
}
// Save new text '+' block
blocks.push( {
oldBlock: null,
newBlock: null,
oldNumber: null,
newNumber: this.newText.tokens[iStart].number,
oldStart: null,
count: count,
unique: false,
words: null,
chars: text.length,
type: '+',
section: null,
group: null,
fixed: null,
moved: null,
text: text
} );
}
}
// Sort '+' blocks in and update groups
this.sortBlocks();
if ( this.config.timer === true ) {
this.timeEnd( 'getInsBlocks' );
}
return;
};
/**
* Sort blocks by new text token number and update groups.
*
* @param[in/out] array groups Groups table object
* @param[in/out] array blocks Blocks table object
*/
this.sortBlocks = function () {
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;
var blocksLength = blocks.length;
for ( var block = 0; block < blocksLength; 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;
};
/**
* Set group numbers of insertion '+' blocks.
*
* @param[in/out] array groups Groups table object
* @param[in/out] array blocks Blocks table object, fixed and group properties
*/
this.setInsGroups = function () {
if ( this.config.timer === true ) {
this.time( 'setInsGroups' );
}
var blocks = this.blocks;
var groups = this.groups;
// Set group numbers of '+' blocks inside existing groups
var groupsLength = groups.length;
for ( var group = 0; group < groupsLength; 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 '+' blocks to new groups
// Cycle through blocks
var blocksLength = blocks.length;
for ( var block = 0; block < blocksLength; block ++ ) {
// 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: blocks[block].unique,
maxWords: blocks[block].words,
words: blocks[block].words,
chars: blocks[block].chars,
fixed: blocks[block].fixed,
movedFrom: null,
color: null
} );
}
}
if ( this.config.timer === true ) {
this.timeEnd( 'setInsGroups' );
}
return;
};
/**
* Mark original positions of moved groups.
* Scheme: 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
*
* Marks '|' and deletions '-' get newNumber of reference block
* and are sorted around it by old text number.
*
* @param[in/out] array groups Groups table object, movedFrom property
* @param[in/out] array blocks Blocks table object
*/
this.insertMarks = function () {
if ( this.config.timer === true ) {
this.time( 'insertMarks' );
}
var blocks = this.blocks;
var groups = this.groups;
var moved = [];
var color = 1;
// Make shallow copy of blocks
var blocksOld = blocks.slice();
// Enumerate copy
var blocksOldLength = blocksOld.length;
for ( var i = 0; i < blocksOldLength; i ++ ) {
blocksOld[i].number = i;
}
// Sort copy by oldNumber
blocksOld.sort( function( a, b ) {
var comp = a.oldNumber - b.oldNumber;
if ( comp === 0 ) {
comp = a.newNumber - b.newNumber;
}
return comp;
} );
// Create lookup table: original to sorted
var lookupSorted = [];
for ( var i = 0; i < blocksOldLength; i ++ ) {
lookupSorted[ blocksOld[i].number ] = i;
}
// Cycle through groups (moved group)
var groupsLength = groups.length;
for ( var moved = 0; moved < groupsLength; moved ++ ) {
var movedGroup = groups[moved];
if ( movedGroup.fixed !== false ) {
continue;
}
var movedOldNumber = movedGroup.oldNumber;
// Find fixed '=' reference block from original block position to position '|' block
// Similar to position deletions '-' code
// Get old text prev block
var prevBlock = null;
var block = lookupSorted[ movedGroup.blockStart ];
if ( block > 0 ) {
prevBlock = blocksOld[block - 1];
}
// Get old text next block
var nextBlock = null;
var block = lookupSorted[ movedGroup.blockEnd ];
if ( block < blocksOld.length - 1 ) {
nextBlock = blocksOld[block + 1];
}
// Move after prev block if fixed
var refBlock = null;
if ( prevBlock !== null && prevBlock.type === '=' && prevBlock.fixed === true ) {
refBlock = prevBlock;
}
// Move before next block if fixed
else if ( nextBlock !== null && nextBlock.type === '=' && nextBlock.fixed === true ) {
refBlock = nextBlock;
}
// Find closest fixed block to the left
else {
for ( var fixed = lookupSorted[ movedGroup.blockStart ] - 1; fixed >= 0; fixed -- ) {
if ( blocksOld[fixed].type === '=' && blocksOld[fixed].fixed === true ) {
refBlock = blocksOld[fixed];
break;
}
}
}
// Get position of new mark block
var newNumber;
var markGroup;
// No smaller fixed block, moved right from before first block
if ( refBlock === null ) {
newNumber = -1;
markGroup = groups.length;
// Save new single-mark-block group
groups.push( {
oldNumber: 0,
blockStart: blocks.length,
blockEnd: blocks.length,
unique: false,
maxWords: null,
words: null,
chars: 0,
fixed: null,
movedFrom: null,
color: null
} );
}
else {
newNumber = refBlock.newNumber;
markGroup = refBlock.group;
}
// Insert '|' block
blocks.push( {
oldBlock: null,
newBlock: null,
oldNumber: movedOldNumber,
newNumber: newNumber,
oldStart: null,
count: null,
unique: null,
words: null,
chars: 0,
type: '|',
section: null,
group: markGroup,
fixed: true,
moved: moved,
text: ''
} );
// Set group color
movedGroup.color = color;
movedGroup.movedFrom = markGroup;
color ++;
}
// Sort '|' blocks in and update groups
this.sortBlocks();
if ( this.config.timer === true ) {
this.timeEnd( 'insertMarks' );
}
return;
};
/**
* Collect diff fragment list for markup, create abstraction layer for customized diffs.
* Adds the following fagment types:
* '=', '-', '+' same, deletion, insertion
* '<', '>' mark left, mark right
* '(<', '(>', ')' block start and end
* '[', ']' fragment start and end
* '{', '}' container start and end
*
* @param[in] array groups Groups table object
* @param[in] array blocks Blocks table object
* @param[out] array fragments Fragments array, abstraction layer for diff code
*/
this.getDiffFragments = function () {
var blocks = this.blocks;
var groups = this.groups;
var fragments = this.fragments;
// 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 groups
var groupsSortLength = groupsSort.length;
for ( var group = 0; group < groupsSortLength; group ++ ) {
var blockStart = groupsSort[group].blockStart;
var blockEnd = groupsSort[group].blockEnd;
// Add moved block start
var color = groupsSort[group].color;