diff.js 9.8 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287
  1. /* See license.txt for terms of usage */
  2. /*
  3. * Text diff implementation.
  4. *
  5. * This library supports the following APIS:
  6. * JsDiff.diffChars: Character by character diff
  7. * JsDiff.diffWords: Word (as defined by \b regex) diff which ignores whitespace
  8. * JsDiff.diffLines: Line based diff
  9. *
  10. * JsDiff.diffCss: Diff targeted at CSS content
  11. *
  12. * These methods are based on the implementation proposed in
  13. * "An O(ND) Difference Algorithm and its Variations" (Myers, 1986).
  14. * http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.4.6927
  15. */
  16. var JsDiff = (function() {
  17. function clonePath(path) {
  18. return { newPos: path.newPos, components: path.components.slice(0) };
  19. }
  20. function removeEmpty(array) {
  21. var ret = [];
  22. for (var i = 0; i < array.length; i++) {
  23. if (array[i]) {
  24. ret.push(array[i]);
  25. }
  26. }
  27. return ret;
  28. }
  29. function escapeHTML(s) {
  30. var n = s;
  31. n = n.replace(/&/g, "&amp;");
  32. n = n.replace(/</g, "&lt;");
  33. n = n.replace(/>/g, "&gt;");
  34. n = n.replace(/"/g, "&quot;");
  35. return n;
  36. }
  37. var fbDiff = function(ignoreWhitespace) {
  38. this.ignoreWhitespace = ignoreWhitespace;
  39. };
  40. fbDiff.prototype = {
  41. diff: function(oldString, newString) {
  42. // Handle the identity case (this is due to unrolling editLength == 0
  43. if (newString == oldString) {
  44. return [{ value: newString }];
  45. }
  46. if (!newString) {
  47. return [{ value: oldString, removed: true }];
  48. }
  49. if (!oldString) {
  50. return [{ value: newString, added: true }];
  51. }
  52. newString = this.tokenize(newString);
  53. oldString = this.tokenize(oldString);
  54. var newLen = newString.length, oldLen = oldString.length;
  55. var maxEditLength = newLen + oldLen;
  56. var bestPath = [{ newPos: -1, components: [] }];
  57. // Seed editLength = 0
  58. var oldPos = this.extractCommon(bestPath[0], newString, oldString, 0);
  59. if (bestPath[0].newPos+1 >= newLen && oldPos+1 >= oldLen) {
  60. return bestPath[0].components;
  61. }
  62. for (var editLength = 1; editLength <= maxEditLength; editLength++) {
  63. for (var diagonalPath = -1*editLength; diagonalPath <= editLength; diagonalPath+=2) {
  64. var basePath;
  65. var addPath = bestPath[diagonalPath-1],
  66. removePath = bestPath[diagonalPath+1];
  67. oldPos = (removePath ? removePath.newPos : 0) - diagonalPath;
  68. if (addPath) {
  69. // No one else is going to attempt to use this value, clear it
  70. bestPath[diagonalPath-1] = undefined;
  71. }
  72. var canAdd = addPath && addPath.newPos+1 < newLen;
  73. var canRemove = removePath && 0 <= oldPos && oldPos < oldLen;
  74. if (!canAdd && !canRemove) {
  75. bestPath[diagonalPath] = undefined;
  76. continue;
  77. }
  78. // Select the diagonal that we want to branch from. We select the prior
  79. // path whose position in the new string is the farthest from the origin
  80. // and does not pass the bounds of the diff graph
  81. if (!canAdd || (canRemove && addPath.newPos < removePath.newPos)) {
  82. basePath = clonePath(removePath);
  83. this.pushComponent(basePath.components, oldString[oldPos], undefined, true);
  84. } else {
  85. basePath = clonePath(addPath);
  86. basePath.newPos++;
  87. this.pushComponent(basePath.components, newString[basePath.newPos], true, undefined);
  88. }
  89. var oldPos = this.extractCommon(basePath, newString, oldString, diagonalPath);
  90. if (basePath.newPos+1 >= newLen && oldPos+1 >= oldLen) {
  91. return basePath.components;
  92. } else {
  93. bestPath[diagonalPath] = basePath;
  94. }
  95. }
  96. }
  97. },
  98. pushComponent: function(components, value, added, removed) {
  99. var last = components[components.length-1];
  100. if (last && last.added === added && last.removed === removed) {
  101. // We need to clone here as the component clone operation is just
  102. // as shallow array clone
  103. components[components.length-1] =
  104. {value: this.join(last.value, value), added: added, removed: removed };
  105. } else {
  106. components.push({value: value, added: added, removed: removed });
  107. }
  108. },
  109. extractCommon: function(basePath, newString, oldString, diagonalPath) {
  110. var newLen = newString.length,
  111. oldLen = oldString.length,
  112. newPos = basePath.newPos,
  113. oldPos = newPos - diagonalPath;
  114. while (newPos+1 < newLen && oldPos+1 < oldLen && this.equals(newString[newPos+1], oldString[oldPos+1])) {
  115. newPos++;
  116. oldPos++;
  117. this.pushComponent(basePath.components, newString[newPos], undefined, undefined);
  118. }
  119. basePath.newPos = newPos;
  120. return oldPos;
  121. },
  122. equals: function(left, right) {
  123. var reWhitespace = /\S/;
  124. if (this.ignoreWhitespace && !reWhitespace.test(left) && !reWhitespace.test(right)) {
  125. return true;
  126. } else {
  127. return left == right;
  128. }
  129. },
  130. join: function(left, right) {
  131. return left + right;
  132. },
  133. tokenize: function(value) {
  134. return value;
  135. }
  136. };
  137. var CharDiff = new fbDiff();
  138. var WordDiff = new fbDiff(true);
  139. WordDiff.tokenize = function(value) {
  140. return removeEmpty(value.split(/(\s+|\b)/));
  141. };
  142. var CssDiff = new fbDiff(true);
  143. CssDiff.tokenize = function(value) {
  144. return removeEmpty(value.split(/([{}:;,]|\s+)/));
  145. };
  146. var LineDiff = new fbDiff();
  147. LineDiff.tokenize = function(value) {
  148. return value.split(/^/m);
  149. };
  150. return {
  151. diffChars: function(oldStr, newStr) { return CharDiff.diff(oldStr, newStr); },
  152. diffWords: function(oldStr, newStr) { return WordDiff.diff(oldStr, newStr); },
  153. diffLines: function(oldStr, newStr) { return LineDiff.diff(oldStr, newStr); },
  154. diffCss: function(oldStr, newStr) { return CssDiff.diff(oldStr, newStr); },
  155. createPatch: function(fileName, oldStr, newStr, oldHeader, newHeader) {
  156. var ret = [];
  157. ret.push("Index: " + fileName);
  158. ret.push("===================================================================");
  159. ret.push("--- " + fileName + (typeof oldHeader === "undefined" ? "" : "\t" + oldHeader));
  160. ret.push("+++ " + fileName + (typeof newHeader === "undefined" ? "" : "\t" + newHeader));
  161. var diff = LineDiff.diff(oldStr, newStr);
  162. if (!diff[diff.length-1].value) {
  163. diff.pop(); // Remove trailing newline add
  164. }
  165. diff.push({value: "", lines: []}); // Append an empty value to make cleanup easier
  166. function contextLines(lines) {
  167. return lines.map(function(entry) { return ' ' + entry; });
  168. }
  169. function eofNL(curRange, i, current) {
  170. var last = diff[diff.length-2],
  171. isLast = i === diff.length-2,
  172. isLastOfType = i === diff.length-3 && (current.added === !last.added || current.removed === !last.removed);
  173. // Figure out if this is the last line for the given file and missing NL
  174. if (!/\n$/.test(current.value) && (isLast || isLastOfType)) {
  175. curRange.push('\\ No newline at end of file');
  176. }
  177. }
  178. var oldRangeStart = 0, newRangeStart = 0, curRange = [],
  179. oldLine = 1, newLine = 1;
  180. for (var i = 0; i < diff.length; i++) {
  181. var current = diff[i],
  182. lines = current.lines || current.value.replace(/\n$/, "").split("\n");
  183. current.lines = lines;
  184. if (current.added || current.removed) {
  185. if (!oldRangeStart) {
  186. var prev = diff[i-1];
  187. oldRangeStart = oldLine;
  188. newRangeStart = newLine;
  189. if (prev) {
  190. curRange = contextLines(prev.lines.slice(-4));
  191. oldRangeStart -= curRange.length;
  192. newRangeStart -= curRange.length;
  193. }
  194. }
  195. curRange.push.apply(curRange, lines.map(function(entry) { return (current.added?"+":"-") + entry; }));
  196. eofNL(curRange, i, current);
  197. if (current.added) {
  198. newLine += lines.length;
  199. } else {
  200. oldLine += lines.length;
  201. }
  202. } else {
  203. if (oldRangeStart) {
  204. // Close out any changes that have been output (or join overlapping)
  205. if (lines.length <= 8 && i < diff.length-2) {
  206. // Overlapping
  207. curRange.push.apply(curRange, contextLines(lines));
  208. } else {
  209. // end the range and output
  210. var contextSize = Math.min(lines.length, 4);
  211. ret.push(
  212. "@@ -" + oldRangeStart + "," + (oldLine-oldRangeStart+contextSize)
  213. + " +" + newRangeStart + "," + (newLine-newRangeStart+contextSize)
  214. + " @@");
  215. ret.push.apply(ret, curRange);
  216. ret.push.apply(ret, contextLines(lines.slice(0, contextSize)));
  217. if (lines.length <= 4) {
  218. eofNL(ret, i, current);
  219. }
  220. oldRangeStart = 0; newRangeStart = 0; curRange = [];
  221. }
  222. }
  223. oldLine += lines.length;
  224. newLine += lines.length;
  225. }
  226. }
  227. return ret.join('\n') + '\n';
  228. },
  229. convertChangesToXML: function(changes){
  230. var ret = [];
  231. for ( var i = 0; i < changes.length; i++) {
  232. var change = changes[i];
  233. if (change.added) {
  234. ret.push("<ins>");
  235. } else if (change.removed) {
  236. ret.push("<del>");
  237. }
  238. ret.push(escapeHTML(change.value));
  239. if (change.added) {
  240. ret.push("</ins>");
  241. } else if (change.removed) {
  242. ret.push("</del>");
  243. }
  244. }
  245. return ret.join("");
  246. }
  247. };
  248. })();
  249. if (typeof module !== "undefined") {
  250. module.exports = JsDiff;
  251. }