Content deleted Content added
1.0.2 (August 24, 2014) text.new, text.old -> text.newText, text.oldText for MS IE 8 compatibility |
another background that could use some darkmode friendly color |
||
| (43 intermediate revisions by 3 users not shown) | |||
Line 1:
// <syntaxhighlight lang="JavaScript">
// ==UserScript==
// @
// @
// @date October 23, 2014
// @description improved word-based diff library with block move detection
// @homepage https://en.wikipedia.org/wiki/User:Cacycle/diff
Line 9 ⟶ 10:
// @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 { color: #000; } ' +
'.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-color: var(--background-color-base, #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: var(--background-color-interactive, #eaecf0); 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 node = corrElement;
do {
corrElementPos += node.offsetTop;
} while ( ( node = node.offsetParent ) !== null );
// Get scroll height
var top;
if ( window.pageYOffset !== undefined ) {
top = window.pageYOffset;
}
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 (
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 */
/** @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;
}
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' );
}
//
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();
//
if (
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
} );
}
//
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
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 longerToken;
if ( newToken.length < oldToken.length ) {
shorterToken = newToken;
longerToken = oldToken;
}
else {
shorterToken = oldToken;
longerToken = newToken;
}
// 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 ) {
//
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;
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;
}
//
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;
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;
}
}
//
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 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
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 (
break;
}
// Get next token
if ( up === false ) {
else {
}
}
/**
* 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] );
if ( recursionLevel === 0 ) {
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.
*/
//
var
for ( var match = 0; match < bordersLength; match ++ ) {
var
var j = bordersDown[match][1];
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.
*/
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 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
j = this.oldText.last;
// Cycle through old text tokens up
// Connect identical tokens, stop after first connected token
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 );
}
}
}
}
//
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
this.oldText.debugText( 'Old text' );
this.newText.debugText( '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();
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;
} );
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
}
// Save group to block
for ( var
}
// Save group
groups.push( {
oldNumber: blocks[groupStart].oldNumber,
blockStart: groupStart,
blockEnd: groupEnd,
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
for ( var section = 0; section < sectionsLength; section ++ ) {
var blockStart = sections[section].blockStart;
var blockEnd = sections[section].blockEnd;
var groupStart = blocks[blockStart].group;
var
// Recusively find path of groups in increasing old group order with longest char length
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 ++ ) {
}
}
}
if ( this.config.timer === true ) {
this.timeEnd( 'setFixed' );
}
};
/**
* 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 {
for ( var block = blockStart; block <= blockEnd; block ++ ) {
// Stop unlinking if more than one word or a unique word
if (
break;
}
this.unlinkSingleBlock( blocks[block] );
unlinked = true;
blockStart = block;
}
}
// Unlink blocks from end
if (
// 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[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 i = null;
while ( j !== null ) {
//
var
var
var text = '';
}
//
if ( count !== 0 ) {
oldBlock: null,
newBlock: null,
oldNumber: this.oldText.tokens[oldStart].number,
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 groups = this.groups;
var blocksOld = blocks.slice();
blocksOld.sort( function( a, b ) {
return a.oldNumber - b.oldNumber;
} );
// Cycle through blocks in old text order
var
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
//
var prevBlockNumber = null;
var prevBlock = null;
if ( block > 0 ) {
prevBlockNumber = blocksOld[block - 1].newBlock;
prevBlock = blocks[prevBlockNumber];
}
// Get old text next block
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;
}
//
else if ( nextBlock !== null && nextBlock.type === '=' && nextBlock.fixed === true ) {
refBlock = nextBlock;
}
// Move after prev block if not start of group
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;
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 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 !== 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;
//
var
for ( var group = 0; group < groupsLength; group ++ ) {
var
for ( var
if ( blocks[block].group === null ) {
blocks[block].group = group;
blocks[block].fixed = fixed;
}
}
}
//
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' );
}
// 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];
}
//
var nextBlock =
var block = lookupSorted[ movedGroup.blockEnd ];
if ( block < blocksOld.length - 1 ) {
nextBlock = blocksOld[block + 1];
}
//
var
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;
}
//
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;
//
newNumber = -1;
//
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;
}
//
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: ''
} );
//
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;
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
if ( color !== null ) {
var type;
if ( groupsSort[group].movedFrom < blocks[
}
else {
type = '(>';
}
fragments.push( {
text: '',
type: type,
color: color
} );
}
// Cycle through blocks
for ( var block = blockStart; block <= blockEnd; block ++ ) {
var type = blocks[block].type;
// Add '=' unchanged text and moved block
if ( type === '=' || type === '-' || type === '+' ) {
fragments.push( {
text: blocks[block].text,
type: type,
color: color
} );
}
//
else if (
var movedGroup = groups[ blocks[block].
//
var markText = '';
for (
var movedBlock = movedGroup.blockStart;
movedBlock <= movedGroup.blockEnd;
if ( blocks[movedBlock].type === '=' || blocks[movedBlock].type === '-' ) {
markText += blocks[movedBlock].text;
}
// Get mark direction
var markType;
if ( movedGroup.blockStart < blockStart ) {
markType = '<';
}
else {
markType = '>';
}
// Add mark
fragments.push( {
text: markText,
type: markType,
color: movedGroup.color
} );
}
}
// Add moved block end
if ( color !== null ) {
fragments.push( {
text: '',
type: ' )',
color: color
} );
}
}
// Cycle through fragments, join consecutive fragments of same type (i.e. '-' blocks)
var
for ( var fragment = 1; fragment < fragmentsLength; fragment ++ ) {
// Check if joinable
if (
fragments[fragment].type === fragments[fragment - 1].type &&
fragments[fragment].color === fragments[fragment - 1].color &&
fragments[fragment].text !== '' && fragments[fragment - 1].text !== ''
) {
// Join and splice
fragments[fragment - 1].text += fragments[fragment].text;
fragments.splice( fragment, 1 );
fragment --;
}
}
// Enclose in containers
fragments.unshift( { text: '', type: '{', color: null }, { text: '', type: '[', color: null } );
fragments.push( { text: '', type: ']', color: null }, { text: '', type: '}', color: null } );
};
/**
* Clip unchanged sections from unmoved block text.
* Adds the following fagment types:
* '~', ' ~', '~ ' omission indicators
* '[', ']', ',' fragment start and end, fragment separator
*
* @param[in/out] array fragments Fragments array, abstraction layer for diff code
*/
this.clipDiffFragments = function () {
var fragments = this.fragments;
// Skip if only one fragment in containers, no change
if ( fragments.length === 5 ) {
return;
}
//
var
if ( this.config.clipParagraphRightMin < minRight ) {
minRight = this.config.clipParagraphRightMin;
}
if ( this.config.clipLineRightMin < minRight ) {
minRight = this.config.clipLineRightMin;
}
if ( this.config.clipBlankRightMin < minRight ) {
minRight = this.config.clipBlankRightMin;
}
if ( this.config.clipCharsRight < minRight ) {
minRight = this.config.clipCharsRight;
}
//
var minLeft = this.config.clipHeadingLeft;
if ( this.config.clipParagraphLeftMin < minLeft ) {
minLeft = this.config.clipParagraphLeftMin;
}
if ( this.config.clipLineLeftMin < minLeft ) {
minLeft = this.config.clipLineLeftMin;
}
if ( this.config.clipBlankLeftMin < minLeft ) {
minLeft = this.config.clipBlankLeftMin;
}
if ( this.config.clipCharsLeft < minLeft ) {
minLeft = this.config.clipCharsLeft;
}
// Cycle through fragments
var fragmentsLength = fragments.length;
for ( var fragment = 0; fragment < fragmentsLength; fragment ++ ) {
// Skip if not an unmoved and unchanged block
var type = fragments[fragment].type;
var color = fragments[fragment].color;
if ( type !== '=' || color !== null ) {
continue;
}
// Skip if too short for clipping
var textLength = text.length;
if ( textLength < minRight && textLength < minLeft ) {
continue;
}
// Get line positions including start and end
var regExpMatch;
while ( ( regExpMatch = this.config.regExp.clipLine.exec( text ) ) !== null ) {
lines.push( regExpMatch.index );
lastIndex = this.config.regExp.clipLine.lastIndex;
}
if ( lines[0] !== 0 ) {
lines.unshift( 0 );
}
if ( lastIndex !== textLength ) {
lines.push( textLength );
}
//
var headings = [];
while ( ( regExpMatch = this.config.regExp.clipHeading.exec( text ) ) !== null ) {
headings.push( regExpMatch.index );
headingsEnd.push( regExpMatch.index + regExpMatch[0].length );
}
// Get paragraph positions including start and end
var paragraphs = [];
var lastIndex = null;
while ( ( regExpMatch = this.config.regExp.clipParagraph.exec( text ) ) !== null ) {
paragraphs.push( regExpMatch.index );
lastIndex = this.config.regExp.clipParagraph.lastIndex;
}
if ( paragraphs[0] !== 0 ) {
paragraphs.unshift( 0 );
}
if ( lastIndex !== textLength ) {
paragraphs.push( textLength );
}
// Determine ranges to keep on left and right side
var rangeRight = null;
var rangeLeft = null;
var rangeRightType = '';
var rangeLeftType = '';
// Find clip pos from left, skip for first non-container block
if ( fragment !== 2 ) {
// Maximum lines to search from left
var rangeLeftMax = textLength;
if ( this.config.clipLinesLeftMax < lines.length ) {
rangeLeftMax = lines[this.config.clipLinesLeftMax];
}
// Find first heading from left
if ( rangeLeft === null ) {
for ( var j = 0; j < headingsLength; j ++ ) {
if ( headingsEnd[j] > this.config.clipHeadingLeft || headingsEnd[j] > rangeLeftMax ) {
break;
rangeLeft = headingsEnd[j];
rangeLeftType = 'heading';
break;
}
}
// Find first paragraph from left
if ( rangeLeft === null ) {
var paragraphsLength = paragraphs.length;
for ( var j = 0; j < paragraphsLength; j ++ ) {
if (
paragraphs[j] > this.config.clipParagraphLeftMax ||
paragraphs[j] > rangeLeftMax
) {
break;
}
if ( paragraphs[j] > this.config.clipParagraphLeftMin ) {
rangeLeft = paragraphs[j];
rangeLeftType = 'paragraph';
break;
}
}
}
// Find first line break from left
if ( rangeLeft === null ) {
var linesLength = lines.length;
for ( var j = 0; j < linesLength; j ++ ) {
if ( lines[j] > this.config.clipLineLeftMax || lines[j] > rangeLeftMax ) {
break;
}
if ( lines[j] > this.config.clipLineLeftMin ) {
rangeLeft = lines[j];
rangeLeftType = 'line';
break;
}
}
}
// Find first blank from left
if ( rangeLeft === null ) {
this.config.regExp.clipBlank.lastIndex = this.config.clipBlankLeftMin;
if ( ( regExpMatch = this.config.regExp.clipBlank.exec( text ) ) !== null ) {
if (
regExpMatch.index < this.config.clipBlankLeftMax &&
regExpMatch.index < rangeLeftMax
) {
rangeLeft = regExpMatch.index;
rangeLeftType = 'blank';
}
}
}
// Fixed number of chars from left
if ( rangeLeft === null ) {
if ( this.config.clipCharsLeft < rangeLeftMax ) {
rangeLeft = this.config.clipCharsLeft;
rangeLeftType = 'chars';
}
}
// Fixed number of lines from left
if ( rangeLeft === null ) {
rangeLeft = rangeLeftMax;
rangeLeftType = 'fixed';
}
}
// Find clip pos from right, skip for last non-container block
if ( fragment !== fragments.length - 3 ) {
// Maximum lines to search from right
var rangeRightMin = 0;
if ( lines.length >= this.config.clipLinesRightMax ) {
rangeRightMin = lines[lines.length - this.config.clipLinesRightMax];
}
// Find last heading from right
if ( rangeRight === null ) {
for ( var j = headings.length - 1; j >= 0; j -- ) {
if (
headings[j] < textLength - this.config.clipHeadingRight ||
headings[j] < rangeRightMin
) {
break;
}
rangeRight = headings[j];
rangeRightType = 'heading';
break;
}
}
//
if ( rangeRight === null ) {
for ( var j = paragraphs.length - 1; j >= 0 ; j -- ) {
if (
paragraphs[j] < textLength - this.config.clipParagraphRightMax ||
paragraphs[j] < rangeRightMin
) {
break;
}
if ( paragraphs[j] < textLength - this.config.clipParagraphRightMin ) {
rangeRight = paragraphs[j];
rangeRightType = 'paragraph';
break;
}
}
}
//
if (
for ( var j = lines.length - 1; j >= 0; j -- ) {
if (
lines[j] < textLength - this.config.clipLineRightMax ||
lines[j] < rangeRightMin
) {
break;
}
if ( lines[j] < textLength - this.config.clipLineRightMin ) {
rangeRight = lines[j];
rangeRightType = 'line';
break;
}
}
}
//
if ( rangeRight === null ) {
var startPos = textLength - this.config.clipBlankRightMax;
if ( startPos < rangeRightMin ) {
startPos = rangeRightMin;
}
this.config.regExp.clipBlank.lastIndex = startPos;
var lastPos = null;
while ( ( regExpMatch = this.config.regExp.clipBlank.exec( text ) ) !== null ) {
if ( regExpMatch.index > textLength - this.config.clipBlankRightMin ) {
if ( lastPos !== null ) {
rangeRight = lastPos;
rangeRightType = 'blank';
}
break;
}
lastPos = regExpMatch.index;
}
}
// Fixed number of chars from right
if (
if ( textLength - this.config.clipCharsRight > rangeRightMin ) {
rangeRight = textLength - this.config.clipCharsRight;
rangeRightType = 'chars';
}
}
// Fixed number of lines from right
if ( rangeRight === null ) {
rangeRight = rangeRightMin;
rangeRightType = 'fixed';
}
}
// Check if we skip clipping if ranges are close together
// Skip if overlapping ranges
if ( rangeLeft > rangeRight ) {
continue;
}
// Skip if chars too close
var skipChars = rangeRight - rangeLeft;
if ( skipChars < this.config.clipSkipChars ) {
continue;
}
// Skip if lines too close
var skipLines = 0;
var linesLength = lines.length;
for ( var j = 0; j < linesLength; j ++ ) {
if ( lines[j] > rangeRight || skipLines > this.config.clipSkipLines ) {
break;
}
if ( lines[j] > rangeLeft ) {
skipLines ++;
}
}
if ( skipLines < this.config.clipSkipLines ) {
continue;
}
}
// Skip if nothing to clip
if ( rangeLeft === null && rangeRight === null ) {
continue;
}
// Split left text
var textLeft = null;
var
if ( rangeLeft !== null ) {
textLeft = text.slice( 0, rangeLeft );
// Remove trailing empty lines
textLeft = textLeft.replace( this.config.regExp.clipTrimNewLinesLeft, '' );
// Get omission indicators, remove trailing blanks
omittedLeft = '~';
textLeft = textLeft.replace( this.config.regExp.clipTrimBlanksLeft, '' );
}
else if ( rangeLeftType === 'blank' ) {
omittedLeft = ' ~';
textLeft = textLeft.replace( this.config.regExp.clipTrimBlanksLeft, '' );
}
}
var textRight = null;
var omittedRight = null;
if ( rangeRight !== null ) {
textRight = text.slice( rangeRight );
// Remove leading empty lines
textRight = textRight.replace( this.config.regExp.clipTrimNewLinesRight, '' );
// Get omission indicators, remove leading blanks
if ( rangeRightType === 'chars' ) {
omittedRight = '~';
textRight = textRight.replace( this.config.regExp.clipTrimBlanksRight, '' );
}
else if ( rangeRightType === 'blank' ) {
omittedRight = '~ ';
textRight = textRight.replace( this.config.regExp.clipTrimBlanksRight, '' );
}
}
// Remove split element
fragments.splice( fragment, 1 );
fragmentsLength --;
// Add left text to fragments list
if ( rangeLeft !== null ) {
fragments.splice( fragment ++, 0, { text: textLeft, type: '=', color: null } );
fragmentsLength ++;
if ( omittedLeft !== null ) {
fragments.splice( fragment ++, 0, { text: '', type: omittedLeft, color: null } );
fragmentsLength ++;
}
}
// Add fragment container and separator to list
if ( rangeLeft !== null && rangeRight !== null ) {
fragments.splice( fragment ++, 0, { text: '', type: ']', color: null } );
fragments.splice( fragment ++, 0, { text: '', type: ',', color: null } );
fragments.splice( fragment ++, 0, { text: '', type: '[', color: null } );
fragmentsLength += 3;
}
// Add right text to fragments list
if ( rangeRight !== null ) {
if ( omittedRight !== null ) {
fragments.splice( fragment ++, 0, { text: '', type: omittedRight, color: null } );
fragmentsLength ++;
}
fragments.splice( fragment ++, 0, { text: textRight, type: '=', color: null } );
fragmentsLength ++;
}
}
// Debug log
if (
this.debugFragments( 'Fragments' );
}
return;
};
/**
* Create html formatted diff code from diff fragments.
*
* @param[in] array fragments Fragments array, abstraction layer for diff code
* @param string|undefined version
* Output version: 'new' or 'old': only text from new or old version, used for unit tests
* @param[out] string html Html code of diff
*/
this.getDiffHtml = function ( version ) {
var fragments = this.fragments;
// No change, only one unchanged block in containers
if ( fragments.length === 5 && fragments[2].type === '=' ) {
this.html = '';
return;
}
//
var htmlFragments = [];
for ( var fragment = 0; fragment < fragmentsLength; fragment ++ ) {
var text = fragments[fragment].text;
var type = fragments[fragment].type;
var color = fragments[fragment].color;
var html = '';
//
var blank = false;
if ( text !== '' ) {
blank = this.config.regExp.blankBlock.test( text );
}
// Add container start markup
if ( type === '{' ) {
html = this.config.htmlCode.containerStart;
}
//
else if ( type === '
html = this.config.htmlCode.containerEnd;
}
//
html = this.config.htmlCode.fragmentStart;
}
//
else if ( type === '
html = this.config.htmlCode.fragmentEnd;
}
//
else if (
html = this.config.htmlCode.separator;
}
// Add omission markup
if ( type === '~' ) {
html = this.config.htmlCode.omittedChars;
}
// Add omission markup
if ( type === ' ~' ) {
html = ' ' + this.config.htmlCode.omittedChars;
}
// Add omission markup
if ( type === '~ ' ) {
html = this.config.htmlCode.omittedChars + ' ';
}
// Add colored left-pointing block start markup
//
var
if ( this.config.noUnicodeSymbols === true ) {
title = this.config.msg['wiked-diff-block-left-nounicode'];
}
else {
title = this.config.msg['wiked-diff-block-left'];
}
// Get html
if ( this.config.coloredBlocks === true ) {
html = this.config.htmlCode.blockColoredStart;
}
else {
html = this.config.htmlCode.blockStart;
}
html = this.htmlCustomize( html, color, title );
}
}
// Add colored right-pointing block start markup
else if ( type === '(>' ) {
if ( version !== 'old' ) {
// Get title
var title;
if ( this.config.noUnicodeSymbols === true ) {
title = this.config.msg['wiked-diff-block-right-nounicode'];
}
else {
title = this.config.msg['wiked-diff-block-right'];
}
// Get html
if ( this.config.coloredBlocks === true ) {
html = this.config.htmlCode.blockColoredStart;
}
else {
html = this.config.htmlCode.blockStart;
}
html = this.htmlCustomize( html, color, title );
}
}
//
else if ( type === ' )' ) {
if ( version !== 'old' ) {
}
}
// Add '=' (unchanged) text and moved block
if ( type === '=' ) {
text = this.htmlEscape( text );
if ( color !== null ) {
if ( version !== 'old' ) {
html = this.markupBlanks( text, true );
}
}
else {
}
}
// Add '-' text
else if ( type === '-' ) {
if ( version !== 'new' ) {
//
if ( version !== 'old' || color === null ) {
text = this.htmlEscape( text );
text = this.markupBlanks( text, true );
if ( blank === true ) {
html = this.config.htmlCode.deleteStartBlank;
}
else {
html = this.config.htmlCode.deleteStart;
}
html += text + this.config.htmlCode.deleteEnd;
}
}
}
else if ( type === '+' ) {
if ( version !== 'old' ) {
text = this.htmlEscape( text );
text = this.markupBlanks( text, true );
if ( blank === true ) {
html = this.config.htmlCode.insertStartBlank;
}
else {
html = this.config.htmlCode.insertStart;
}
html += text + this.config.htmlCode.insertEnd;
}
}
// Add '<' and '>' code
else if ( type === '<' || type === '>' ) {
if ( version !== 'new' ) {
// Display as deletion at original position
if ( this.config.showBlockMoves === false || version === 'old' ) {
text = this.htmlEscape( text );
text = this.markupBlanks( text, true );
if ( version === 'old' ) {
if ( this.config.coloredBlocks === true ) {
html =
this.htmlCustomize( this.config.htmlCode.blockColoredStart, color ) +
text +
this.config.htmlCode.blockEnd;
}
else {
html =
this.htmlCustomize( this.config.htmlCode.blockStart, color ) +
text +
this.config.htmlCode.blockEnd;
}
}
else {
if ( blank === true ) {
html =
this.config.htmlCode.deleteStartBlank +
text +
this.config.htmlCode.deleteEnd;
}
else {
html = this.config.htmlCode.deleteStart + text + this.config.htmlCode.deleteEnd;
}
}
}
// Display as mark
else {
if ( type === '<' ) {
if ( this.config.coloredBlocks === true ) {
html = this.htmlCustomize( this.config.htmlCode.markLeftColored, color, text );
}
else {
html = this.htmlCustomize( this.config.htmlCode.markLeft, color, text );
}
}
else {
if ( this.config.coloredBlocks === true ) {
html = this.htmlCustomize( this.config.htmlCode.markRightColored, color, text );
}
else {
html = this.htmlCustomize( this.config.htmlCode.markRight, color, text );
}
}
}
}
}
htmlFragments.push( html );
}
// Join fragments
this.html = htmlFragments.join( '' );
return;
};
/**
* Customize html code fragments.
* Replaces:
* {number}: class/color/block/mark/id number
* {title}: title attribute (popup)
* {nounicode}: noUnicodeSymbols fallback
* input: html, number: block number, title: title attribute (popup) text
*
* @param string html Html code to be customized
* @return string Customized html code
*/
this.htmlCustomize = function ( html, number, title ) {
// Replace {number} with class/color/block/mark/id number
html = html.replace( /\{number\}/g, number);
// Replace {nounicode} with wikEdDiffNoUnicode class name
if ( this.config.noUnicodeSymbols === true ) {
html = html.replace( /\{nounicode\}/g, ' wikEdDiffNoUnicode');
}
else {
html = html.replace( /\{nounicode\}/g, '');
}
// Shorten title text, replace {title}
if ( title !== undefined ) {
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, ' ');
html = html.replace( /\{title\}/, title);
}
return html;
};
/
* Replace html-sensitive characters in output text with character entities.
*
* @param string html Html code to be escaped
* @return string Escaped html code
*/
this.htmlEscape = function ( html ) {
html = html.replace( /&/g, '&');
html = html.replace( /</g, '<');
html = html.replace( />/g, '>');
html = html.replace( /"/g, '"');
return html;
};
/**
* Markup tabs, newlines, and spaces in diff fragment text.
*
* @param bool highlight Highlight newlines and spaces in addition to tabs
* @param string html Text code to be marked-up
* @return string Marked-up text
*/
this.markupBlanks = function ( html, highlight ) {
if ( highlight === true ) {
html = html.replace( / /g, this.config.htmlCode.space);
html = html.replace( /\n/g, this.config.htmlCode.newline);
}
html = html.replace( /\t/g, this.config.htmlCode.tab);
return html;
};
/
* Count real words in text.
*
* @param string text Text for word counting
* @return int Number of words in text
*/
this.wordCount = function ( text ) {
return ( text.match( this.config.regExp.countWords ) || [] ).length;
};
/**
* Test diff code for consistency with input versions.
* Prints results to debug console.
*
* @param[in] WikEdDiffText newText, oldText Text objects
*/
this.unitTests = function () {
// Check if output is consistent with new text
this.getDiffHtml( 'new' );
var diff = this.html.replace( /<[^>]*>/g, '');
var text = this.htmlEscape( this.newText.text );
if ( diff !== text ) {
console.log(
'Error: wikEdDiff unit test failure: diff not consistent with new text version!'
);
this.error = true;
console.log( 'new text:\n', text );
console.log( 'new diff:\n', diff );
}
else {
console.log( 'OK: wikEdDiff unit test passed: diff consistent with new text.' );
}
// Check if output is consistent with old text
this.getDiffHtml( 'old' );
var diff = this.html.replace( /<[^>]*>/g, '');
var text = this.htmlEscape( this.oldText.text );
if ( diff !== text ) {
console.log(
'Error: wikEdDiff unit test failure: diff not consistent with old text version!'
);
this.error = true;
console.log( 'old text:\n', text );
console.log( 'old diff:\n', diff );
}
else {
console.log( 'OK: wikEdDiff unit test passed: diff consistent with old text.' );
}
return;
};
/**
* Dump blocks object to browser console.
*
* @param string name Block name
* @param[in] array blocks Blocks table object
*/
this.debugBlocks = function ( name, blocks ) {
if ( blocks === undefined ) {
blocks = this.blocks;
}
var dump =
'\ni \toldBl \tnewBl \toldNm \tnewNm \toldSt \tcount \tuniq' +
'\twords \tchars \ttype \tsect \tgroup \tfixed \tmoved \ttext\n';
var blocksLength = blocks.length;
for ( var i = 0; i < blocksLength; i ++ ) {
dump +=
i + ' \t' + blocks[i].oldBlock + ' \t' + blocks[i].newBlock + ' \t' +
blocks[i].oldNumber + ' \t' + blocks[i].newNumber + ' \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.debugShortenText( blocks[i].text ) + '\n';
}
console.log( name + ':\n' + dump );
};
/**
* Dump groups object to browser console.
*
* @param string name Group name
* @param[in] array groups Groups table object
*/
this.debugGroups = function ( name, groups ) {
if ( groups === undefined ) {
groups = this.groups;
}
var dump =
'\ni \toldNm \tblSta \tblEnd \tuniq \tmaxWo' +
'\twords \tchars \tfixed \toldNm \tmFrom \tcolor\n';
var groupsLength = groupsLength;
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( name + ':\n' + dump );
};
/**
* Dump fragments array to browser console.
*
* @param string name Fragments name
* @param[in] array fragments Fragments array
*/
this.debugFragments = function ( name ) {
var fragments = this.fragments;
var dump = '\ni \ttype \tcolor \ttext\n';
var fragmentsLength = fragments.length;
for ( var i = 0; i < fragmentsLength; i ++ ) {
dump +=
i + ' \t"' + fragments[i].type + '" \t' + fragments[i].color + ' \t' +
this.debugShortenText( fragments[i].text, 120, 40 ) + '\n';
}
console.log( name + ':\n' + dump );
};
/**
* Dump borders array to browser console.
*
* @param string name Arrays name
* @param[in] array border Match border array
*/
this.debugBorders = function ( name, borders ) {
var dump = '\ni \t[ new \told ]\n';
for ( var i = 0; i < bordersLength; i ++ ) {
dump += i + ' \t[ ' + borders[i][0] + ' \t' + borders[i][1] + ' ]\n';
}
console.log( name, dump );
};
/**
* Shorten text for dumping.
*
* @param string text Text to be shortened
* @param int max Max length of (shortened) text
* @param int end Length of trailing fragment of shortened text
* @return string Shortened text
*/
this.debugShortenText = function ( text, max, end ) {
if ( typeof text !== 'string' ) {
text = text.toString();
}
text = text.replace( /\n/g, '\\n');
text = text.replace( /\t/g, ' ');
if ( max === undefined ) {
}
if ( end === undefined ) {
end = 15;
}
if ( text.length > max ) {
text = text.substr( 0, max - 1 - end ) + '…' + text.substr( text.length - end );
}
return '"' + text + '"';
};
/**
* Start timer 'label', analogous to JavaScript console timer.
* Usage: this.time( 'label' );
*
* @param string label Timer label
* @param[out] array timer Current time in milliseconds (float)
*/
this.time = function ( label ) {
this.timer[label] = new Date().getTime();
return;
};
/**
* Stop timer 'label', analogous to JavaScript console timer.
* Logs time in milliseconds since start to browser console.
* Usage: this.timeEnd( 'label' );
*
* @param string label Timer label
* @param bool noLog Do not log result
* @return float Time in milliseconds
*/
this.timeEnd = function ( label, noLog ) {
var diff = 0;
if ( this.timer[label] !== undefined ) {
var start = this.timer[label];
var stop = new Date().getTime();
diff = stop - start;
this.timer[label] = undefined;
if ( noLog !== true ) {
console.log( label + ': ' + diff.toFixed( 2 ) + ' ms' );
}
}
return diff;
};
/**
* Log recursion timer results to browser console.
* Usage: this.timeRecursionEnd();
*
* @param string text Text label for output
* @param[in] array recursionTimer Accumulated recursion times
*/
this.timeRecursionEnd = function ( text ) {
if ( this.recursionTimer.length > 1 ) {
// Subtract times spent in deeper recursions
var timerEnd = this.recursionTimer.length - 1;
for ( var i = 0; i < timerEnd; i ++ ) {
this.recursionTimer[i] -= this.recursionTimer[i + 1];
}
// Log recursion times
var timerLength = this.recursionTimer.length;
for ( var i = 0; i < timerLength; i ++ ) {
console.log( text + ' recursion ' + i + ': ' + this.recursionTimer[i].toFixed( 2 ) + ' ms' );
}
}
this.recursionTimer = [];
return;
};
/**
* Log variable values to debug console.
* Usage: this.debug( 'var', var );
*
* @param string name Object identifier
* @param mixed|undefined name Object to be logged
*/
this.debug = function ( name, object ) {
if ( object === undefined ) {
console.log( name );
}
else {
console.log( name + ': ' + object );
}
return;
};
/**
* Add script to document head.
*
* @param string code JavaScript code
*/
this.addScript = function ( code ) {
if ( document.getElementById( 'wikEdDiffBlockHandler' ) === null ) {
var script = document.createElement( 'script' );
script.id = 'wikEdDiffBlockHandler';
if ( script.innerText !== undefined ) {
script.innerText = code;
}
else {
script.textContent = code;
}
document.getElementsByTagName( 'head' )[0].appendChild( script );
}
return;
};
/**
* Add stylesheet to document head, cross-browser >= IE6.
*
* @param string css CSS code
*/
this.addStyleSheet = function ( css ) {
if ( document.getElementById( 'wikEdDiffStyles' ) === null ) {
// Replace mark symbols
css = css.replace( /\{cssMarkLeft\}/g, this.config.cssMarkLeft);
css = css.replace( /\{cssMarkRight\}/g, this.config.cssMarkRight);
var style = document.createElement( 'style' );
style.id = 'wikEdDiffStyles';
style.type = 'text/css';
if ( style.styleSheet !== undefined ) {
style.styleSheet.cssText = css;
}
else {
style.appendChild( document.createTextNode( css ) );
}
document.getElementsByTagName( 'head' )[0].appendChild( style );
}
return;
};
/**
* Recursive deep copy from target over source for customization import.
*
* @param object source Source object
* @param object target Target object
*/
this.deepCopy = function ( source, target ) {
for ( var key in source ) {
if ( Object.prototype.hasOwnProperty.call( source, key ) === true ) {
if ( typeof source[key] === 'object' ) {
this.deepCopy( source[key], target[key] );
}
else {
}
}
}
return;
};
// Initialze WikEdDiff object
this.init();
};
/**
* Data and methods for single text version (old or new one).
*
* @class WikEdDiffText
*/
WikEdDiff.WikEdDiffText = function ( text, parent ) {
/** @var WikEdDiff parent Parent object for configuration settings and debugging methods */
this.parent = parent;
/** @var string text Text of this version */
this.text = null;
/** @var array tokens Tokens list */
this.tokens = [];
/** @var int first, last First and last index of tokens list */
this.first = null;
this.last = null;
/** @var array words Word counts for version text */
this.words = {};
/**
* Constructor, initialize text object.
*
* @param string text Text of version
* @param WikEdDiff parent Parent, for configuration settings and debugging methods
*/
this.init = function () {
if ( typeof text !== 'string' ) {
text = text.toString();
}
// IE / Mac fix
this.text = text.replace( /\r\n?/g, '\n');
// Parse and count words and chunks for identification of unique real words
if ( this.parent.config.timer === true ) {
this.parent.time( 'wordParse' );
}
this.wordParse( this.parent.config.regExp.countWords );
this.wordParse( this.parent.config.regExp.countChunks );
if ( this.parent.config.timer === true ) {
this.parent.timeEnd( 'wordParse' );
}
return;
};
/**
* Parse and count words and chunks for identification of unique words.
*
* @param string regExp Regular expression for counting words
* @param[in] string text Text of version
* @param[out] array words Number of word occurrences
*/
this.wordParse = function ( regExp ) {
var regExpMatch = this.text.match( regExp );
if (
var matchLength = regExpMatch.length;
for (var i = 0; i < matchLength; i ++) {
var word = regExpMatch[i];
if ( Object.prototype.hasOwnProperty.call( this.words, word ) === false ) {
this.words[word] = 1;
}
else {
this.words[word] ++;
}
}
}
return;
};
/**
* Split text into paragraph, line, sentence, chunk, word, or character tokens.
*
* @param string level Level of splitting: paragraph, line, sentence, chunk, word, or character
* @param int|null token Index of token to be split, otherwise uses full text
* @param[in] string text Full text to be split
* @param[out] array tokens Tokens list
* @param[out] int first, last First and last index of tokens list
*/
this.splitText = function ( level, token ) {
var prev = null;
var next = null;
var current = this.tokens.length;
var first = current;
var text = '';
// Split full text or specified token
if ( token === undefined ) {
text = this.text;
}
else {
prev = this.tokens[token].prev;
next = this.tokens[token].next;
text = this.tokens[token].token;
}
// Split text into tokens, regExp match as separator
var number = 0;
var split = [];
var regExpMatch;
var lastIndex = 0;
var regExp = this.parent.config.regExp.split[level];
while ( ( regExpMatch = regExp.exec( text ) ) !== null ) {
if ( regExpMatch.index > lastIndex ) {
split.push( text.substring( lastIndex, regExpMatch.index ) );
}
split.push( regExpMatch[0] );
lastIndex = regExp.lastIndex;
}
if ( lastIndex < text.length ) {
split.push( text.substring( lastIndex ) );
}
// Cycle through new tokens
var splitLength = split.length;
for ( var i = 0; i < splitLength; i ++ ) {
// Insert current item, link to previous
this.tokens.push( {
token: split[i],
prev: prev,
next: null,
link: null,
number: null,
unique: false
} );
number ++;
// Link previous item to current
if ( prev !== null ) {
this.tokens[prev].next = current;
}
prev = current;
current ++;
}
// Connect last new item and existing next item
if ( number > 0 && token !== undefined ) {
if ( prev !== null ) {
this.tokens[prev].next = next;
}
if ( next !== null ) {
this.tokens[next].prev = prev;
}
}
// Set text first and last token index
if ( number > 0 ) {
// Initial text split
if ( token === undefined ) {
this.first = 0;
this.last = prev;
}
// First or last token has been split
else {
if ( token === this.first ) {
this.first = first;
}
if ( token === this.last ) {
this.last = prev;
}
}
}
return;
};
/**
* Split unique unmatched tokens into smaller tokens.
*
* @param string level Level of splitting: line, sentence, chunk, or word
* @param[in] array tokens Tokens list
*/
this.splitRefine = function ( regExp ) {
// Cycle through tokens list
var i = this.first;
while ( i !== null ) {
// Refine unique unmatched tokens into smaller tokens
if ( this.tokens[i].link === null ) {
this.splitText( regExp, i );
}
i = this.tokens[i].next;
}
return;
};
/
* Enumerate text token list before detecting blocks.
*
* @param[out] array tokens Tokens list
*/
this.enumerateTokens = function () {
// Enumerate tokens list
var number = 0;
while ( i !== null ) {
this.tokens[i].number = number;
number ++;
i = this.tokens[i].next;
}
return;
};
/
* Dump tokens object to browser console.
*
* @param string name Text name
* @param[in] int first, last First and last index of tokens list
* @param[in] array tokens Tokens list
*/
this.debugText = function ( name ) {
var tokens = this.tokens;
dump += '\ni \tlink \t(prev \tnext) \tuniq \t#num \t"token"\n';
var i = this.first;
while ( i !== null ) {
i + ' \t' + tokens[i].link + ' \t(' + tokens[i].prev + ' \t' + tokens[i].next + ') \t' +
tokens[i].unique + ' \t#' + tokens[i].number + ' \t' +
parent.debugShortenText( tokens[i].token ) + '\n';
i = tokens[i].next;
}
console.log( name + ':\n' + dump );
return;
};
// Initialize WikEdDiffText object
this.init();
};
// </syntaxhighlight>
| |||