1 |
|
2 | var diffsync = (typeof(module) != 'undefined') ? module.exports : {}
|
3 |
|
4 | diffsync.version = 1039
|
5 | diffsync.port = 60607
|
6 |
|
7 |
|
8 |
|
9 |
|
10 |
|
11 |
|
12 |
|
13 |
|
14 |
|
15 |
|
16 |
|
17 |
|
18 |
|
19 |
|
20 |
|
21 |
|
22 |
|
23 |
|
24 |
|
25 |
|
26 |
|
27 |
|
28 |
|
29 | diffsync.create_client = function (options) {
|
30 | var self = {}
|
31 | self.on_change = null
|
32 | self.on_window_closing = null
|
33 | self.get_channels = null
|
34 |
|
35 | var on_channels = null
|
36 |
|
37 | var uid = guid()
|
38 | var minigit = diffsync.create_minigit()
|
39 | var unacknowledged_commits = {}
|
40 |
|
41 | var prev_range = [-1, -1]
|
42 | var peer_ranges = {}
|
43 |
|
44 | window.addEventListener('beforeunload', function () {
|
45 | if (self.on_window_closing) self.on_window_closing()
|
46 | })
|
47 |
|
48 | var connected = false
|
49 | function reconnect() {
|
50 | connected = false
|
51 | console.log('connecting...')
|
52 | var ws = new WebSocket(options.ws_url)
|
53 |
|
54 | function send(o) {
|
55 | o.v = diffsync.version
|
56 | o.uid = uid
|
57 | o.channel = options.channel
|
58 | try {
|
59 | ws.send(JSON.stringify(o))
|
60 | } catch (e) {}
|
61 | }
|
62 |
|
63 | self.on_window_closing = function () {
|
64 | send({ close : true })
|
65 | }
|
66 |
|
67 | self.get_channels = function (cb) {
|
68 | on_channels = cb
|
69 | send({ get_channels : true })
|
70 | }
|
71 |
|
72 | ws.onopen = function () {
|
73 | connected = true
|
74 | send({ join : true })
|
75 | on_pong()
|
76 | }
|
77 |
|
78 | var pong_timer = null
|
79 | function on_pong() {
|
80 | clearTimeout(pong_timer)
|
81 | setTimeout(function () {
|
82 | send({ ping : true })
|
83 | pong_timer = setTimeout(function () {
|
84 | console.log('no pong came!!')
|
85 | if (ws) {
|
86 | ws = null
|
87 | reconnect()
|
88 | }
|
89 | }, 4000)
|
90 | }, 3000)
|
91 | }
|
92 |
|
93 | ws.onclose = function () {
|
94 | console.log('connection closed...')
|
95 | if (ws) {
|
96 | ws = null
|
97 | reconnect()
|
98 | }
|
99 | }
|
100 |
|
101 | var sent_unacknowledged_commits = false
|
102 |
|
103 | function adjust_range(range, patch) {
|
104 | return map_array(range, function (x) {
|
105 | each(patch, function (p) {
|
106 | if (p[0] < x) {
|
107 | if (p[0] + p[1] <= x) {
|
108 | x += -p[1] + p[2].length
|
109 | } else {
|
110 | x = p[0] + p[2].length
|
111 | }
|
112 | } else return false
|
113 | })
|
114 | return x
|
115 | })
|
116 | }
|
117 |
|
118 | ws.onmessage = function (event) {
|
119 | if (!ws) { return }
|
120 | var o = JSON.parse(event.data)
|
121 | if (o.pong) { return on_pong() }
|
122 |
|
123 | console.log('message: ' + event.data)
|
124 |
|
125 | if (o.channels) {
|
126 | if (on_channels) on_channels(o.channels)
|
127 | }
|
128 | if (o.commits) {
|
129 | self.on_change()
|
130 | minigit.merge(o.commits)
|
131 |
|
132 | var patch = get_diff_patch(options.get_text(), minigit.cache)
|
133 | each(peer_ranges, function (range, peer) {
|
134 | peer_ranges[peer] = adjust_range(range, patch)
|
135 | })
|
136 |
|
137 | prev_range = adjust_range(options.get_range(), patch)
|
138 | options.on_text(minigit.cache, prev_range)
|
139 |
|
140 | if (o.welcome) {
|
141 | each(extend(o.commits, minigit.get_ancestors(o.commits)), function (_, id) {
|
142 | delete unacknowledged_commits[id]
|
143 | })
|
144 | if (Object.keys(unacknowledged_commits).length > 0) {
|
145 | send({ commits : unacknowledged_commits })
|
146 | }
|
147 | sent_unacknowledged_commits = true
|
148 | }
|
149 |
|
150 | send({ leaves : minigit.leaves })
|
151 | }
|
152 | if (o.may_delete) {
|
153 | each(o.may_delete, function (_, id) {
|
154 | delete unacknowledged_commits[id]
|
155 | minigit.remove(id)
|
156 | })
|
157 | }
|
158 | if (o.range) {
|
159 | peer_ranges[o.uid] = o.range
|
160 | }
|
161 | if (o.close) {
|
162 | delete peer_ranges[o.uid]
|
163 | }
|
164 | if ((o.range || o.close || o.commits) && options.on_ranges) {
|
165 | options.on_ranges(peer_ranges)
|
166 | }
|
167 | }
|
168 |
|
169 | self.on_change = function () {
|
170 | if (!connected) { return }
|
171 |
|
172 | var old_cache = minigit.cache
|
173 | var cs = minigit.commit(options.get_text())
|
174 | if (cs) {
|
175 | extend(unacknowledged_commits, cs)
|
176 |
|
177 | var patch = null
|
178 | var c = cs[Object.keys(cs)[0]]
|
179 | var parents = Object.keys(c.from_parents)
|
180 | if (parents.length == 1)
|
181 | patch = c.from_parents[parents[0]]
|
182 | else
|
183 | patch = get_diff_patch(old_cache, minigit.cache)
|
184 |
|
185 | each(peer_ranges, function (range, peer) {
|
186 | peer_ranges[peer] = adjust_range(range, patch)
|
187 | })
|
188 | if (options.on_ranges) options.on_ranges(peer_ranges)
|
189 | }
|
190 |
|
191 | if (!sent_unacknowledged_commits) { return }
|
192 |
|
193 | var range = options.get_range()
|
194 | var range_changed = (range[0] != prev_range[0]) || (range[1] != prev_range[1])
|
195 | prev_range = range
|
196 |
|
197 | var msg = {}
|
198 | if (cs) msg.commits = cs
|
199 |
|
200 | if (range_changed) msg.range = range
|
201 | if (cs || range_changed) send(msg)
|
202 | }
|
203 | }
|
204 | reconnect()
|
205 |
|
206 | return self
|
207 | }
|
208 |
|
209 |
|
210 |
|
211 |
|
212 |
|
213 |
|
214 |
|
215 |
|
216 |
|
217 |
|
218 |
|
219 |
|
220 |
|
221 |
|
222 |
|
223 |
|
224 |
|
225 |
|
226 |
|
227 |
|
228 |
|
229 |
|
230 |
|
231 |
|
232 |
|
233 |
|
234 |
|
235 |
|
236 |
|
237 |
|
238 |
|
239 |
|
240 |
|
241 | diffsync.create_server = function (options) {
|
242 | var self = {}
|
243 | self.channels = {}
|
244 |
|
245 | function new_channel(name) {
|
246 | return self.channels[name] = {
|
247 | name : name,
|
248 | minigit : diffsync.create_minigit(),
|
249 | members : {}
|
250 | }
|
251 | }
|
252 | function get_channel(name) {
|
253 | return self.channels[name] || new_channel(name)
|
254 | }
|
255 |
|
256 | var users_to_sockets = {}
|
257 |
|
258 | if (options.initial_data) {
|
259 | each(options.initial_data, function (data, channel) {
|
260 | var c = get_channel(channel)
|
261 | c.minigit.merge(data.commits)
|
262 | extend(c.members, data.members)
|
263 | })
|
264 | }
|
265 |
|
266 | options.wss.on('connection', function connection(ws) {
|
267 | console.log('new connection')
|
268 | var uid = null
|
269 | var channel_name = null
|
270 |
|
271 | function myClose() {
|
272 | if (!uid) { return }
|
273 | delete users_to_sockets[uid]
|
274 | each(users_to_sockets, function (_ws, _uid) {
|
275 | try {
|
276 | _ws.send(JSON.stringify({
|
277 | v : diffsync.version,
|
278 | uid : uid,
|
279 | channel : channel_name,
|
280 | close : true
|
281 | }))
|
282 | } catch (e) {}
|
283 | })
|
284 | }
|
285 |
|
286 | ws.on('close', myClose)
|
287 | ws.on('error', myClose)
|
288 |
|
289 | ws.on('message', function (message) {
|
290 | var o = JSON.parse(message)
|
291 | if (o.v != diffsync.version) { return }
|
292 | if (o.ping) { return try_send(ws, JSON.stringify({ pong : true })) }
|
293 |
|
294 | console.log('message: ' + message)
|
295 |
|
296 | uid = o.uid
|
297 | var channel = get_channel(o.channel)
|
298 | channel_name = channel.name
|
299 | users_to_sockets[uid] = ws
|
300 |
|
301 | var changes = { channel : channel.name, commits : {}, members : {} }
|
302 |
|
303 | if (!channel.members[uid]) channel.members[uid] = { do_not_delete : {}, last_sent : 0 }
|
304 | channel.members[uid].last_seen = Date.now()
|
305 | changes.members[uid] = channel.members[uid]
|
306 |
|
307 | function try_send(ws, message) {
|
308 | try {
|
309 | ws.send(message)
|
310 | } catch (e) {}
|
311 | }
|
312 | function send_to_all_but_me(message) {
|
313 | each(channel.members, function (_, them) {
|
314 | if (them != uid) {
|
315 | try_send(users_to_sockets[them], message)
|
316 | }
|
317 | })
|
318 | }
|
319 |
|
320 | if (o.get_channels) {
|
321 | try_send(ws, JSON.stringify({ channels : Object.keys(self.channels) }))
|
322 | }
|
323 | if (o.join) {
|
324 | try_send(ws, JSON.stringify({ commits : channel.minigit.commits, welcome : true }))
|
325 | }
|
326 | if (o.commits) {
|
327 | var new_commits = {}
|
328 | each(o.commits, function (c, id) {
|
329 | if (!channel.minigit.commits[id]) {
|
330 | new_commits[id] = c
|
331 | changes.commits[id] = c
|
332 | }
|
333 | })
|
334 | channel.minigit.merge(new_commits)
|
335 |
|
336 | var new_message = {
|
337 | channel : channel.name,
|
338 | commits : new_commits
|
339 | }
|
340 | if (o.range) {
|
341 | new_message.uid = o.uid
|
342 | new_message.range = o.range
|
343 | }
|
344 | new_message = JSON.stringify(new_message)
|
345 |
|
346 | leaves = channel.minigit.get_leaves(new_commits)
|
347 | var now = Date.now()
|
348 | each(channel.members, function (m, them) {
|
349 | if (them != uid) {
|
350 | if (m.last_seen > m.last_sent) {
|
351 | m.last_sent = now
|
352 | changes.members[them] = m
|
353 | } else if (m.last_sent < now - 3000) {
|
354 | return
|
355 | }
|
356 | extend(m.do_not_delete, leaves)
|
357 | try_send(users_to_sockets[them], new_message)
|
358 | }
|
359 | })
|
360 | if (!o.leaves) o.leaves = channel.minigit.get_leaves(o.commits)
|
361 | } else if (o.range) {
|
362 | send_to_all_but_me(message)
|
363 | }
|
364 | if (o.leaves) {
|
365 | extend(channel.members[uid].do_not_delete, o.leaves)
|
366 | each(channel.minigit.get_ancestors(o.leaves), function (_, id) {
|
367 | delete channel.members[uid].do_not_delete[id]
|
368 | })
|
369 |
|
370 | var necessary = {}
|
371 | each(channel.members, function (m) {
|
372 | extend(necessary, m.do_not_delete)
|
373 | })
|
374 |
|
375 | var affected = channel.minigit.remove_unnecessary(necessary)
|
376 | extend(changes.commits, affected)
|
377 |
|
378 | var new_message = {
|
379 | channel : channel.name,
|
380 | may_delete : {}
|
381 | }
|
382 | each(affected, function (c, id) {
|
383 | if (c.delete_me) {
|
384 | new_message.may_delete[id] = true
|
385 | }
|
386 | })
|
387 | if (Object.keys(new_message.may_delete).length > 0) {
|
388 | new_message = JSON.stringify(new_message)
|
389 | each(channel.members, function (m, them) {
|
390 | try_send(users_to_sockets[them], new_message)
|
391 | })
|
392 | }
|
393 | }
|
394 | if (o.close) {
|
395 | channel.members[uid].delete_me = true
|
396 | delete channel.members[uid]
|
397 | }
|
398 |
|
399 | if (options.on_change) options.on_change(changes)
|
400 | })
|
401 | })
|
402 |
|
403 | return self
|
404 | }
|
405 |
|
406 |
|
407 |
|
408 | diffsync.create_minigit = function () {
|
409 | var self = {
|
410 | commits : {},
|
411 | to_children : {},
|
412 | commit_cache : {},
|
413 | leaves : {},
|
414 | cache : ''
|
415 | }
|
416 |
|
417 | self.remove_unnecessary = function (spare_us) {
|
418 | var affected = {}
|
419 | while (true) {
|
420 | var found = false
|
421 | each(self.commits, function (c, id) {
|
422 | if (spare_us[id]) { return }
|
423 | var aff = self.remove(id)
|
424 | if (aff) {
|
425 | extend(affected, aff)
|
426 | found = true
|
427 | }
|
428 | })
|
429 | if (!found) break
|
430 | }
|
431 | return affected
|
432 | }
|
433 |
|
434 | self.remove = function (id) {
|
435 | var keys = Object.keys(self.to_children[id])
|
436 | if (keys.length == 1) {
|
437 | var affected = {}
|
438 |
|
439 | var being_removed = self.commits[id]
|
440 | var c_id = keys[0]
|
441 | var c = self.commits[c_id]
|
442 |
|
443 | self.get_text(c_id)
|
444 | each(being_removed.to_parents, function (_, id) {
|
445 | self.get_text(id)
|
446 | })
|
447 |
|
448 | delete self.commits[id]
|
449 | delete self.commit_cache[id]
|
450 | delete c.to_parents[id]
|
451 | delete c.from_parents[id]
|
452 | being_removed.delete_me = true
|
453 | affected[id] = being_removed
|
454 |
|
455 | each(being_removed.to_parents, function (_, id) {
|
456 | var x = get_diff_patch_2(self.get_text(c_id), self.get_text(id))
|
457 | c.to_parents[id] = x[0]
|
458 | c.from_parents[id] = x[1]
|
459 | })
|
460 | if (Object.keys(c.to_parents).length == 0) {
|
461 | c.text = self.get_text(c_id)
|
462 | }
|
463 | affected[c_id] = c
|
464 |
|
465 | self.calc_children()
|
466 |
|
467 | return affected
|
468 | }
|
469 | }
|
470 |
|
471 | self.commit = function (s) {
|
472 | if (s == self.cache) { return }
|
473 |
|
474 | var c = {
|
475 | to_parents : {},
|
476 | from_parents : {}
|
477 | }
|
478 | if (Object.keys(self.leaves).length == 0) {
|
479 | c.text = s
|
480 | } else {
|
481 | each(self.leaves, function (_, leaf) {
|
482 | var x = get_diff_patch_2(s, self.get_text(leaf))
|
483 | c.to_parents[leaf] = x[0]
|
484 | c.from_parents[leaf] = x[1]
|
485 | })
|
486 | }
|
487 |
|
488 | var id = guid()
|
489 | self.commits[id] = c
|
490 | self.calc_children()
|
491 | self.leaves = {}
|
492 | self.leaves[id] = true
|
493 | self.commit_cache[id] = s
|
494 | self.cache = s
|
495 | self.purge_cache()
|
496 |
|
497 | var cs = {}
|
498 | cs[id] = c
|
499 | return cs
|
500 | }
|
501 |
|
502 | self.merge = function (cs) {
|
503 | each(cs, function (c, id) {
|
504 | if (!self.commits[id]) {
|
505 | self.commits[id] = c
|
506 | } else {
|
507 | if (c.text) self.commits[id].text = c.text
|
508 | extend(self.commits[id].to_parents, c.to_parents)
|
509 | extend(self.commits[id].from_parents, c.from_parents)
|
510 | }
|
511 | })
|
512 | self.calc_children()
|
513 | self.leaves = self.get_leaves()
|
514 | self.cache = self.rec_merge(self.leaves)
|
515 | self.purge_cache()
|
516 | return self.cache
|
517 | }
|
518 |
|
519 | self.calc_children = function () {
|
520 | self.to_children = {}
|
521 | each(self.commits, function (c, id) {
|
522 | self.to_children[id] = {}
|
523 | })
|
524 | each(self.commits, function (c, id) {
|
525 | each(c.from_parents, function (d, p_id) {
|
526 | self.to_children[p_id][id] = d
|
527 | })
|
528 | })
|
529 | }
|
530 |
|
531 | self.purge_cache = function () {
|
532 | each(self.commits, function (c, id) {
|
533 | if (Object.keys(c.to_parents).length > 0 && !self.leaves[id]) {
|
534 | delete self.commit_cache[id]
|
535 | }
|
536 | })
|
537 | }
|
538 |
|
539 | self.get_text = function (id) {
|
540 | if (self.commit_cache[id] != null) return self.commit_cache[id]
|
541 |
|
542 | var frontier = [id]
|
543 | var back_pointers = {}
|
544 | back_pointers[id] = id
|
545 | while (true) {
|
546 | var next = frontier.shift()
|
547 |
|
548 | if (!next) { throw 'data structure corrupted' }
|
549 | var c_id = next
|
550 | var c = self.commits[c_id]
|
551 | var text = (c.text != null) ? c.text : self.commit_cache[c_id]
|
552 | if (text != null) {
|
553 | var snowball = text
|
554 | while (true) {
|
555 | if (next == id) {
|
556 | return self.commit_cache[id] = snowball
|
557 | }
|
558 | next = back_pointers[next]
|
559 | snowball = apply_diff_patch(snowball, c.to_parents[next] || self.to_children[c_id][next])
|
560 | c_id = next
|
561 | c = self.commits[c_id]
|
562 | }
|
563 | }
|
564 |
|
565 | each(c.to_parents, function (_, id) {
|
566 | if (!back_pointers[id]) {
|
567 | back_pointers[id] = next
|
568 | frontier.push(id)
|
569 | }
|
570 | })
|
571 | each(self.to_children[c_id], function (_, id) {
|
572 | if (!back_pointers[id]) {
|
573 | back_pointers[id] = next
|
574 | frontier.push(id)
|
575 | }
|
576 | })
|
577 | }
|
578 | }
|
579 |
|
580 | self.rec_merge = function (these) {
|
581 | these = Object.keys(these)
|
582 | if (these.length == 0) { return '' }
|
583 | var r = self.get_text(these[0])
|
584 | if (these.length == 1) { return r }
|
585 | var r_ancestors = self.get_ancestors(these[0])
|
586 | for (var i = 1; i < these.length; i++) {
|
587 | var i_ancestors = self.get_ancestors(these[i])
|
588 | var o = self.rec_merge(self.get_leaves(intersection(r_ancestors, i_ancestors)))
|
589 | r = apply_diff_patch(o, get_merged_diff_patch(r, self.get_text(these[i]), o))
|
590 | extend(r_ancestors, i_ancestors)
|
591 | }
|
592 | return r
|
593 | }
|
594 |
|
595 | self.get_leaves = function (commits) {
|
596 | if (!commits) commits = self.commits
|
597 | var leaves = {}
|
598 | each(commits, function (_, id) { leaves[id] = true })
|
599 | each(commits, function (c) {
|
600 | each(c.to_parents, function (_, p) {
|
601 | delete leaves[p]
|
602 | })
|
603 | })
|
604 | return leaves
|
605 | }
|
606 |
|
607 | self.get_ancestors = function (id_or_set) {
|
608 | var frontier = null
|
609 | if (typeof(id_or_set) == 'object') {
|
610 | frontier = Object.keys(id_or_set)
|
611 | } else {
|
612 | frontier = [id_or_set]
|
613 | }
|
614 | var ancestors = {}
|
615 | while (frontier.length > 0) {
|
616 | var next = frontier.shift()
|
617 | each(self.commits[next].to_parents, function (_, p) {
|
618 | if (!ancestors[p]) {
|
619 | ancestors[p] = self.commits[p]
|
620 | frontier.push(p)
|
621 | }
|
622 | })
|
623 | }
|
624 | return ancestors
|
625 | }
|
626 |
|
627 | return self
|
628 | }
|
629 |
|
630 |
|
631 |
|
632 | function guid() {
|
633 | var x = '0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ'
|
634 | var s = []
|
635 | for (var i = 0; i < 15; i++) {
|
636 | s.push(x[Math.floor(Math.random() * x.length)])
|
637 | }
|
638 | return s.join('')
|
639 | }
|
640 |
|
641 | function each(o, cb) {
|
642 | if (o instanceof Array) {
|
643 | for (var i = 0; i < o.length; i++) {
|
644 | if (cb(o[i], i, o) == false)
|
645 | return false
|
646 | }
|
647 | } else {
|
648 | for (var k in o) {
|
649 | if (o.hasOwnProperty(k)) {
|
650 | if (cb(o[k], k, o) == false)
|
651 | return false
|
652 | }
|
653 | }
|
654 | }
|
655 | return true
|
656 | }
|
657 |
|
658 | function map_array(a, f) {
|
659 | var b = []
|
660 | each(a, function (v, k) { b[k] = f(v) })
|
661 | return b
|
662 | }
|
663 |
|
664 | function extend(a, b) {
|
665 | each(b, function (x, key) { a[key] = x })
|
666 | return a
|
667 | }
|
668 |
|
669 | function intersection(a, b) {
|
670 | var common = {}
|
671 | each(a, function (_, x) {
|
672 | if (b[x]) {
|
673 | common[x] = a[x]
|
674 | }
|
675 | })
|
676 | return common
|
677 | }
|
678 |
|
679 |
|
680 |
|
681 | var DIFF_DELETE = -1;
|
682 | var DIFF_INSERT = 1;
|
683 | var DIFF_EQUAL = 0;
|
684 |
|
685 | function get_merged_diff_patch(a, b, o) {
|
686 | var a_diff = get_diff_patch(o, a)
|
687 | var b_diff = get_diff_patch(o, b)
|
688 | var ds = []
|
689 | var prev_d = null
|
690 | while (a_diff.length > 0 || b_diff.length > 0) {
|
691 | var d = a_diff.length == 0 ?
|
692 | b_diff.shift() :
|
693 | b_diff.length == 0 ?
|
694 | a_diff.shift() :
|
695 | a_diff[0][0] < b_diff[0][0] ?
|
696 | a_diff.shift() :
|
697 | a_diff[0][0] > b_diff[0][0] ?
|
698 | b_diff.shift() :
|
699 | a_diff[0][2] < b_diff[0][2] ?
|
700 | a_diff.shift() :
|
701 | b_diff.shift()
|
702 | if (prev_d && d[0] < prev_d[0] + prev_d[1]) {
|
703 | if (d[0] + d[1] > prev_d[0] + prev_d[1]) {
|
704 | prev_d[1] = d[0] + d[1] - prev_d[0]
|
705 | }
|
706 | prev_d[2] += d[2]
|
707 | } else {
|
708 | ds.push(d)
|
709 | prev_d = d
|
710 | }
|
711 | }
|
712 | return ds
|
713 | }
|
714 |
|
715 | function apply_diff_patch(s, diff) {
|
716 | var offset = 0
|
717 | for (var i = 0; i < diff.length; i++) {
|
718 | var d = diff[i]
|
719 | s = s.slice(0, d[0] + offset) + d[2] + s.slice(d[0] + offset + d[1])
|
720 | offset += d[2].length - d[1]
|
721 | }
|
722 | return s
|
723 | }
|
724 |
|
725 | function diff_convert_to_my_format(d, factor) {
|
726 | if (factor === undefined) factor = 1
|
727 | var x = []
|
728 | var ii = 0
|
729 | for (var i = 0; i < d.length; i++) {
|
730 | var dd = d[i]
|
731 | if (dd[0] == DIFF_EQUAL) {
|
732 | ii += dd[1].length
|
733 | continue
|
734 | }
|
735 | var xx = [ii, 0, '']
|
736 | if (dd[0] == DIFF_INSERT * factor) {
|
737 | xx[2] = dd[1]
|
738 | } else if (dd[0] == DIFF_DELETE * factor) {
|
739 | xx[1] = dd[1].length
|
740 | ii += xx[1]
|
741 | }
|
742 | if (i + 1 < d.length) {
|
743 | dd = d[i + 1]
|
744 | if (dd[0] != DIFF_EQUAL) {
|
745 | if (dd[0] == DIFF_INSERT * factor) {
|
746 | xx[2] = dd[1]
|
747 | } else if (dd[0] == DIFF_DELETE * factor) {
|
748 | xx[1] = dd[1].length
|
749 | ii += xx[1]
|
750 | }
|
751 | i++
|
752 | }
|
753 | }
|
754 | x.push(xx)
|
755 | }
|
756 | return x
|
757 | }
|
758 |
|
759 | function get_diff_patch(a, b) {
|
760 | return diff_convert_to_my_format(diff_main(a, b))
|
761 | }
|
762 |
|
763 | function get_diff_patch_2(a, b) {
|
764 | var x = diff_main(a, b)
|
765 | return [diff_convert_to_my_format(x),
|
766 | diff_convert_to_my_format(x, -1)]
|
767 | }
|
768 |
|
769 | diffsync.get_diff_patch = get_diff_patch
|
770 | diffsync.get_diff_patch_2 = get_diff_patch_2
|
771 |
|
772 |
|
773 |
|
774 |
|
775 |
|
776 |
|
777 |
|
778 |
|
779 |
|
780 |
|
781 |
|
782 |
|
783 |
|
784 |
|
785 |
|
786 |
|
787 |
|
788 |
|
789 |
|
790 |
|
791 |
|
792 |
|
793 |
|
794 |
|
795 |
|
796 |
|
797 |
|
798 |
|
799 |
|
800 |
|
801 |
|
802 |
|
803 | var DIFF_DELETE = -1;
|
804 | var DIFF_INSERT = 1;
|
805 | var DIFF_EQUAL = 0;
|
806 |
|
807 |
|
808 |
|
809 |
|
810 |
|
811 |
|
812 |
|
813 |
|
814 |
|
815 |
|
816 | function diff_main(text1, text2, cursor_pos) {
|
817 |
|
818 | if (text1 == text2) {
|
819 | if (text1) {
|
820 | return [[DIFF_EQUAL, text1]];
|
821 | }
|
822 | return [];
|
823 | }
|
824 |
|
825 |
|
826 | if (cursor_pos < 0 || text1.length < cursor_pos) {
|
827 | cursor_pos = null;
|
828 | }
|
829 |
|
830 |
|
831 | var commonlength = diff_commonPrefix(text1, text2);
|
832 | var commonprefix = text1.substring(0, commonlength);
|
833 | text1 = text1.substring(commonlength);
|
834 | text2 = text2.substring(commonlength);
|
835 |
|
836 |
|
837 | commonlength = diff_commonSuffix(text1, text2);
|
838 | var commonsuffix = text1.substring(text1.length - commonlength);
|
839 | text1 = text1.substring(0, text1.length - commonlength);
|
840 | text2 = text2.substring(0, text2.length - commonlength);
|
841 |
|
842 |
|
843 | var diffs = diff_compute_(text1, text2);
|
844 |
|
845 |
|
846 | if (commonprefix) {
|
847 | diffs.unshift([DIFF_EQUAL, commonprefix]);
|
848 | }
|
849 | if (commonsuffix) {
|
850 | diffs.push([DIFF_EQUAL, commonsuffix]);
|
851 | }
|
852 | diff_cleanupMerge(diffs);
|
853 | if (cursor_pos != null) {
|
854 | diffs = fix_cursor(diffs, cursor_pos);
|
855 | }
|
856 | return diffs;
|
857 | };
|
858 |
|
859 |
|
860 |
|
861 |
|
862 |
|
863 |
|
864 |
|
865 |
|
866 |
|
867 | function diff_compute_(text1, text2) {
|
868 | var diffs;
|
869 |
|
870 | if (!text1) {
|
871 |
|
872 | return [[DIFF_INSERT, text2]];
|
873 | }
|
874 |
|
875 | if (!text2) {
|
876 |
|
877 | return [[DIFF_DELETE, text1]];
|
878 | }
|
879 |
|
880 | var longtext = text1.length > text2.length ? text1 : text2;
|
881 | var shorttext = text1.length > text2.length ? text2 : text1;
|
882 | var i = longtext.indexOf(shorttext);
|
883 | if (i != -1) {
|
884 |
|
885 | diffs = [[DIFF_INSERT, longtext.substring(0, i)],
|
886 | [DIFF_EQUAL, shorttext],
|
887 | [DIFF_INSERT, longtext.substring(i + shorttext.length)]];
|
888 |
|
889 | if (text1.length > text2.length) {
|
890 | diffs[0][0] = diffs[2][0] = DIFF_DELETE;
|
891 | }
|
892 | return diffs;
|
893 | }
|
894 |
|
895 | if (shorttext.length == 1) {
|
896 |
|
897 |
|
898 | return [[DIFF_DELETE, text1], [DIFF_INSERT, text2]];
|
899 | }
|
900 |
|
901 |
|
902 | var hm = diff_halfMatch_(text1, text2);
|
903 | if (hm) {
|
904 |
|
905 | var text1_a = hm[0];
|
906 | var text1_b = hm[1];
|
907 | var text2_a = hm[2];
|
908 | var text2_b = hm[3];
|
909 | var mid_common = hm[4];
|
910 |
|
911 | var diffs_a = diff_main(text1_a, text2_a);
|
912 | var diffs_b = diff_main(text1_b, text2_b);
|
913 |
|
914 | return diffs_a.concat([[DIFF_EQUAL, mid_common]], diffs_b);
|
915 | }
|
916 |
|
917 | return diff_bisect_(text1, text2);
|
918 | };
|
919 |
|
920 |
|
921 |
|
922 |
|
923 |
|
924 |
|
925 |
|
926 |
|
927 |
|
928 |
|
929 |
|
930 | function diff_bisect_(text1, text2) {
|
931 |
|
932 | var text1_length = text1.length;
|
933 | var text2_length = text2.length;
|
934 | var max_d = Math.ceil((text1_length + text2_length) / 2);
|
935 | var v_offset = max_d;
|
936 | var v_length = 2 * max_d;
|
937 | var v1 = new Array(v_length);
|
938 | var v2 = new Array(v_length);
|
939 |
|
940 |
|
941 | for (var x = 0; x < v_length; x++) {
|
942 | v1[x] = -1;
|
943 | v2[x] = -1;
|
944 | }
|
945 | v1[v_offset + 1] = 0;
|
946 | v2[v_offset + 1] = 0;
|
947 | var delta = text1_length - text2_length;
|
948 |
|
949 |
|
950 | var front = (delta % 2 != 0);
|
951 |
|
952 |
|
953 | var k1start = 0;
|
954 | var k1end = 0;
|
955 | var k2start = 0;
|
956 | var k2end = 0;
|
957 | for (var d = 0; d < max_d; d++) {
|
958 |
|
959 | for (var k1 = -d + k1start; k1 <= d - k1end; k1 += 2) {
|
960 | var k1_offset = v_offset + k1;
|
961 | var x1;
|
962 | if (k1 == -d || (k1 != d && v1[k1_offset - 1] < v1[k1_offset + 1])) {
|
963 | x1 = v1[k1_offset + 1];
|
964 | } else {
|
965 | x1 = v1[k1_offset - 1] + 1;
|
966 | }
|
967 | var y1 = x1 - k1;
|
968 | while (x1 < text1_length && y1 < text2_length &&
|
969 | text1.charAt(x1) == text2.charAt(y1)) {
|
970 | x1++;
|
971 | y1++;
|
972 | }
|
973 | v1[k1_offset] = x1;
|
974 | if (x1 > text1_length) {
|
975 |
|
976 | k1end += 2;
|
977 | } else if (y1 > text2_length) {
|
978 |
|
979 | k1start += 2;
|
980 | } else if (front) {
|
981 | var k2_offset = v_offset + delta - k1;
|
982 | if (k2_offset >= 0 && k2_offset < v_length && v2[k2_offset] != -1) {
|
983 |
|
984 | var x2 = text1_length - v2[k2_offset];
|
985 | if (x1 >= x2) {
|
986 |
|
987 | return diff_bisectSplit_(text1, text2, x1, y1);
|
988 | }
|
989 | }
|
990 | }
|
991 | }
|
992 |
|
993 |
|
994 | for (var k2 = -d + k2start; k2 <= d - k2end; k2 += 2) {
|
995 | var k2_offset = v_offset + k2;
|
996 | var x2;
|
997 | if (k2 == -d || (k2 != d && v2[k2_offset - 1] < v2[k2_offset + 1])) {
|
998 | x2 = v2[k2_offset + 1];
|
999 | } else {
|
1000 | x2 = v2[k2_offset - 1] + 1;
|
1001 | }
|
1002 | var y2 = x2 - k2;
|
1003 | while (x2 < text1_length && y2 < text2_length &&
|
1004 | text1.charAt(text1_length - x2 - 1) ==
|
1005 | text2.charAt(text2_length - y2 - 1)) {
|
1006 | x2++;
|
1007 | y2++;
|
1008 | }
|
1009 | v2[k2_offset] = x2;
|
1010 | if (x2 > text1_length) {
|
1011 |
|
1012 | k2end += 2;
|
1013 | } else if (y2 > text2_length) {
|
1014 |
|
1015 | k2start += 2;
|
1016 | } else if (!front) {
|
1017 | var k1_offset = v_offset + delta - k2;
|
1018 | if (k1_offset >= 0 && k1_offset < v_length && v1[k1_offset] != -1) {
|
1019 | var x1 = v1[k1_offset];
|
1020 | var y1 = v_offset + x1 - k1_offset;
|
1021 |
|
1022 | x2 = text1_length - x2;
|
1023 | if (x1 >= x2) {
|
1024 |
|
1025 | return diff_bisectSplit_(text1, text2, x1, y1);
|
1026 | }
|
1027 | }
|
1028 | }
|
1029 | }
|
1030 | }
|
1031 |
|
1032 |
|
1033 | return [[DIFF_DELETE, text1], [DIFF_INSERT, text2]];
|
1034 | };
|
1035 |
|
1036 |
|
1037 |
|
1038 |
|
1039 |
|
1040 |
|
1041 |
|
1042 |
|
1043 |
|
1044 |
|
1045 |
|
1046 | function diff_bisectSplit_(text1, text2, x, y) {
|
1047 | var text1a = text1.substring(0, x);
|
1048 | var text2a = text2.substring(0, y);
|
1049 | var text1b = text1.substring(x);
|
1050 | var text2b = text2.substring(y);
|
1051 |
|
1052 |
|
1053 | var diffs = diff_main(text1a, text2a);
|
1054 | var diffsb = diff_main(text1b, text2b);
|
1055 |
|
1056 | return diffs.concat(diffsb);
|
1057 | };
|
1058 |
|
1059 |
|
1060 |
|
1061 |
|
1062 |
|
1063 |
|
1064 |
|
1065 |
|
1066 |
|
1067 | function diff_commonPrefix(text1, text2) {
|
1068 |
|
1069 | if (!text1 || !text2 || text1.charAt(0) != text2.charAt(0)) {
|
1070 | return 0;
|
1071 | }
|
1072 |
|
1073 |
|
1074 | var pointermin = 0;
|
1075 | var pointermax = Math.min(text1.length, text2.length);
|
1076 | var pointermid = pointermax;
|
1077 | var pointerstart = 0;
|
1078 | while (pointermin < pointermid) {
|
1079 | if (text1.substring(pointerstart, pointermid) ==
|
1080 | text2.substring(pointerstart, pointermid)) {
|
1081 | pointermin = pointermid;
|
1082 | pointerstart = pointermin;
|
1083 | } else {
|
1084 | pointermax = pointermid;
|
1085 | }
|
1086 | pointermid = Math.floor((pointermax - pointermin) / 2 + pointermin);
|
1087 | }
|
1088 | return pointermid;
|
1089 | };
|
1090 |
|
1091 |
|
1092 |
|
1093 |
|
1094 |
|
1095 |
|
1096 |
|
1097 |
|
1098 | function diff_commonSuffix(text1, text2) {
|
1099 |
|
1100 | if (!text1 || !text2 ||
|
1101 | text1.charAt(text1.length - 1) != text2.charAt(text2.length - 1)) {
|
1102 | return 0;
|
1103 | }
|
1104 |
|
1105 |
|
1106 | var pointermin = 0;
|
1107 | var pointermax = Math.min(text1.length, text2.length);
|
1108 | var pointermid = pointermax;
|
1109 | var pointerend = 0;
|
1110 | while (pointermin < pointermid) {
|
1111 | if (text1.substring(text1.length - pointermid, text1.length - pointerend) ==
|
1112 | text2.substring(text2.length - pointermid, text2.length - pointerend)) {
|
1113 | pointermin = pointermid;
|
1114 | pointerend = pointermin;
|
1115 | } else {
|
1116 | pointermax = pointermid;
|
1117 | }
|
1118 | pointermid = Math.floor((pointermax - pointermin) / 2 + pointermin);
|
1119 | }
|
1120 | return pointermid;
|
1121 | };
|
1122 |
|
1123 |
|
1124 |
|
1125 |
|
1126 |
|
1127 |
|
1128 |
|
1129 |
|
1130 |
|
1131 |
|
1132 |
|
1133 |
|
1134 | function diff_halfMatch_(text1, text2) {
|
1135 | var longtext = text1.length > text2.length ? text1 : text2;
|
1136 | var shorttext = text1.length > text2.length ? text2 : text1;
|
1137 | if (longtext.length < 4 || shorttext.length * 2 < longtext.length) {
|
1138 | return null;
|
1139 | }
|
1140 |
|
1141 | |
1142 |
|
1143 |
|
1144 |
|
1145 |
|
1146 |
|
1147 |
|
1148 |
|
1149 |
|
1150 |
|
1151 |
|
1152 |
|
1153 | function diff_halfMatchI_(longtext, shorttext, i) {
|
1154 |
|
1155 | var seed = longtext.substring(i, i + Math.floor(longtext.length / 4));
|
1156 | var j = -1;
|
1157 | var best_common = '';
|
1158 | var best_longtext_a, best_longtext_b, best_shorttext_a, best_shorttext_b;
|
1159 | while ((j = shorttext.indexOf(seed, j + 1)) != -1) {
|
1160 | var prefixLength = diff_commonPrefix(longtext.substring(i),
|
1161 | shorttext.substring(j));
|
1162 | var suffixLength = diff_commonSuffix(longtext.substring(0, i),
|
1163 | shorttext.substring(0, j));
|
1164 | if (best_common.length < suffixLength + prefixLength) {
|
1165 | best_common = shorttext.substring(j - suffixLength, j) +
|
1166 | shorttext.substring(j, j + prefixLength);
|
1167 | best_longtext_a = longtext.substring(0, i - suffixLength);
|
1168 | best_longtext_b = longtext.substring(i + prefixLength);
|
1169 | best_shorttext_a = shorttext.substring(0, j - suffixLength);
|
1170 | best_shorttext_b = shorttext.substring(j + prefixLength);
|
1171 | }
|
1172 | }
|
1173 | if (best_common.length * 2 >= longtext.length) {
|
1174 | return [best_longtext_a, best_longtext_b,
|
1175 | best_shorttext_a, best_shorttext_b, best_common];
|
1176 | } else {
|
1177 | return null;
|
1178 | }
|
1179 | }
|
1180 |
|
1181 |
|
1182 | var hm1 = diff_halfMatchI_(longtext, shorttext,
|
1183 | Math.ceil(longtext.length / 4));
|
1184 |
|
1185 | var hm2 = diff_halfMatchI_(longtext, shorttext,
|
1186 | Math.ceil(longtext.length / 2));
|
1187 | var hm;
|
1188 | if (!hm1 && !hm2) {
|
1189 | return null;
|
1190 | } else if (!hm2) {
|
1191 | hm = hm1;
|
1192 | } else if (!hm1) {
|
1193 | hm = hm2;
|
1194 | } else {
|
1195 |
|
1196 | hm = hm1[4].length > hm2[4].length ? hm1 : hm2;
|
1197 | }
|
1198 |
|
1199 |
|
1200 | var text1_a, text1_b, text2_a, text2_b;
|
1201 | if (text1.length > text2.length) {
|
1202 | text1_a = hm[0];
|
1203 | text1_b = hm[1];
|
1204 | text2_a = hm[2];
|
1205 | text2_b = hm[3];
|
1206 | } else {
|
1207 | text2_a = hm[0];
|
1208 | text2_b = hm[1];
|
1209 | text1_a = hm[2];
|
1210 | text1_b = hm[3];
|
1211 | }
|
1212 | var mid_common = hm[4];
|
1213 | return [text1_a, text1_b, text2_a, text2_b, mid_common];
|
1214 | };
|
1215 |
|
1216 |
|
1217 |
|
1218 |
|
1219 |
|
1220 |
|
1221 |
|
1222 | function diff_cleanupMerge(diffs) {
|
1223 | diffs.push([DIFF_EQUAL, '']);
|
1224 | var pointer = 0;
|
1225 | var count_delete = 0;
|
1226 | var count_insert = 0;
|
1227 | var text_delete = '';
|
1228 | var text_insert = '';
|
1229 | var commonlength;
|
1230 | while (pointer < diffs.length) {
|
1231 | switch (diffs[pointer][0]) {
|
1232 | case DIFF_INSERT:
|
1233 | count_insert++;
|
1234 | text_insert += diffs[pointer][1];
|
1235 | pointer++;
|
1236 | break;
|
1237 | case DIFF_DELETE:
|
1238 | count_delete++;
|
1239 | text_delete += diffs[pointer][1];
|
1240 | pointer++;
|
1241 | break;
|
1242 | case DIFF_EQUAL:
|
1243 |
|
1244 | if (count_delete + count_insert > 1) {
|
1245 | if (count_delete !== 0 && count_insert !== 0) {
|
1246 |
|
1247 | commonlength = diff_commonPrefix(text_insert, text_delete);
|
1248 | if (commonlength !== 0) {
|
1249 | if ((pointer - count_delete - count_insert) > 0 &&
|
1250 | diffs[pointer - count_delete - count_insert - 1][0] ==
|
1251 | DIFF_EQUAL) {
|
1252 | diffs[pointer - count_delete - count_insert - 1][1] +=
|
1253 | text_insert.substring(0, commonlength);
|
1254 | } else {
|
1255 | diffs.splice(0, 0, [DIFF_EQUAL,
|
1256 | text_insert.substring(0, commonlength)]);
|
1257 | pointer++;
|
1258 | }
|
1259 | text_insert = text_insert.substring(commonlength);
|
1260 | text_delete = text_delete.substring(commonlength);
|
1261 | }
|
1262 |
|
1263 | commonlength = diff_commonSuffix(text_insert, text_delete);
|
1264 | if (commonlength !== 0) {
|
1265 | diffs[pointer][1] = text_insert.substring(text_insert.length -
|
1266 | commonlength) + diffs[pointer][1];
|
1267 | text_insert = text_insert.substring(0, text_insert.length -
|
1268 | commonlength);
|
1269 | text_delete = text_delete.substring(0, text_delete.length -
|
1270 | commonlength);
|
1271 | }
|
1272 | }
|
1273 |
|
1274 | if (count_delete === 0) {
|
1275 | diffs.splice(pointer - count_insert,
|
1276 | count_delete + count_insert, [DIFF_INSERT, text_insert]);
|
1277 | } else if (count_insert === 0) {
|
1278 | diffs.splice(pointer - count_delete,
|
1279 | count_delete + count_insert, [DIFF_DELETE, text_delete]);
|
1280 | } else {
|
1281 | diffs.splice(pointer - count_delete - count_insert,
|
1282 | count_delete + count_insert, [DIFF_DELETE, text_delete],
|
1283 | [DIFF_INSERT, text_insert]);
|
1284 | }
|
1285 | pointer = pointer - count_delete - count_insert +
|
1286 | (count_delete ? 1 : 0) + (count_insert ? 1 : 0) + 1;
|
1287 | } else if (pointer !== 0 && diffs[pointer - 1][0] == DIFF_EQUAL) {
|
1288 |
|
1289 | diffs[pointer - 1][1] += diffs[pointer][1];
|
1290 | diffs.splice(pointer, 1);
|
1291 | } else {
|
1292 | pointer++;
|
1293 | }
|
1294 | count_insert = 0;
|
1295 | count_delete = 0;
|
1296 | text_delete = '';
|
1297 | text_insert = '';
|
1298 | break;
|
1299 | }
|
1300 | }
|
1301 | if (diffs[diffs.length - 1][1] === '') {
|
1302 | diffs.pop();
|
1303 | }
|
1304 |
|
1305 |
|
1306 |
|
1307 |
|
1308 | var changes = false;
|
1309 | pointer = 1;
|
1310 |
|
1311 | while (pointer < diffs.length - 1) {
|
1312 | if (diffs[pointer - 1][0] == DIFF_EQUAL &&
|
1313 | diffs[pointer + 1][0] == DIFF_EQUAL) {
|
1314 |
|
1315 | if (diffs[pointer][1].substring(diffs[pointer][1].length -
|
1316 | diffs[pointer - 1][1].length) == diffs[pointer - 1][1]) {
|
1317 |
|
1318 | diffs[pointer][1] = diffs[pointer - 1][1] +
|
1319 | diffs[pointer][1].substring(0, diffs[pointer][1].length -
|
1320 | diffs[pointer - 1][1].length);
|
1321 | diffs[pointer + 1][1] = diffs[pointer - 1][1] + diffs[pointer + 1][1];
|
1322 | diffs.splice(pointer - 1, 1);
|
1323 | changes = true;
|
1324 | } else if (diffs[pointer][1].substring(0, diffs[pointer + 1][1].length) ==
|
1325 | diffs[pointer + 1][1]) {
|
1326 |
|
1327 | diffs[pointer - 1][1] += diffs[pointer + 1][1];
|
1328 | diffs[pointer][1] =
|
1329 | diffs[pointer][1].substring(diffs[pointer + 1][1].length) +
|
1330 | diffs[pointer + 1][1];
|
1331 | diffs.splice(pointer + 1, 1);
|
1332 | changes = true;
|
1333 | }
|
1334 | }
|
1335 | pointer++;
|
1336 | }
|
1337 |
|
1338 | if (changes) {
|
1339 | diff_cleanupMerge(diffs);
|
1340 | }
|
1341 | };
|
1342 |
|
1343 |
|
1344 |
|
1345 |
|
1346 |
|
1347 |
|
1348 |
|
1349 |
|
1350 |
|
1351 |
|
1352 |
|
1353 |
|
1354 |
|
1355 |
|
1356 | function cursor_normalize_diff (diffs, cursor_pos) {
|
1357 | if (cursor_pos === 0) {
|
1358 | return [DIFF_EQUAL, diffs];
|
1359 | }
|
1360 | for (var current_pos = 0, i = 0; i < diffs.length; i++) {
|
1361 | var d = diffs[i];
|
1362 | if (d[0] === DIFF_DELETE || d[0] === DIFF_EQUAL) {
|
1363 | var next_pos = current_pos + d[1].length;
|
1364 | if (cursor_pos === next_pos) {
|
1365 | return [i + 1, diffs];
|
1366 | } else if (cursor_pos < next_pos) {
|
1367 |
|
1368 | diffs = diffs.slice();
|
1369 |
|
1370 | var split_pos = cursor_pos - current_pos;
|
1371 | var d_left = [d[0], d[1].slice(0, split_pos)];
|
1372 | var d_right = [d[0], d[1].slice(split_pos)];
|
1373 | diffs.splice(i, 1, d_left, d_right);
|
1374 | return [i + 1, diffs];
|
1375 | } else {
|
1376 | current_pos = next_pos;
|
1377 | }
|
1378 | }
|
1379 | }
|
1380 | throw new Error('cursor_pos is out of bounds!')
|
1381 | }
|
1382 |
|
1383 |
|
1384 |
|
1385 |
|
1386 |
|
1387 |
|
1388 |
|
1389 |
|
1390 |
|
1391 |
|
1392 |
|
1393 |
|
1394 |
|
1395 |
|
1396 |
|
1397 |
|
1398 |
|
1399 |
|
1400 |
|
1401 | function fix_cursor (diffs, cursor_pos) {
|
1402 | var norm = cursor_normalize_diff(diffs, cursor_pos);
|
1403 | var ndiffs = norm[1];
|
1404 | var cursor_pointer = norm[0];
|
1405 | var d = ndiffs[cursor_pointer];
|
1406 | var d_next = ndiffs[cursor_pointer + 1];
|
1407 |
|
1408 | if (d == null) {
|
1409 |
|
1410 |
|
1411 | return diffs;
|
1412 | } else if (d[0] !== DIFF_EQUAL) {
|
1413 |
|
1414 |
|
1415 | return diffs;
|
1416 | } else {
|
1417 | if (d_next != null && d[1] + d_next[1] === d_next[1] + d[1]) {
|
1418 |
|
1419 |
|
1420 | ndiffs.splice(cursor_pointer, 2, d_next, d)
|
1421 | return merge_tuples(ndiffs, cursor_pointer, 2)
|
1422 | } else if (d_next != null && d_next[1].indexOf(d[1]) === 0) {
|
1423 |
|
1424 |
|
1425 |
|
1426 |
|
1427 | ndiffs.splice(cursor_pointer, 2, [d_next[0], d[1]], [0, d[1]]);
|
1428 | var suffix = d_next[1].slice(d[1].length);
|
1429 | if (suffix.length > 0) {
|
1430 | ndiffs.splice(cursor_pointer + 2, 0, [d_next[0], suffix]);
|
1431 | }
|
1432 | return merge_tuples(ndiffs, cursor_pointer, 3)
|
1433 | } else {
|
1434 |
|
1435 | return diffs;
|
1436 | }
|
1437 | }
|
1438 |
|
1439 | }
|
1440 |
|
1441 |
|
1442 |
|
1443 |
|
1444 |
|
1445 |
|
1446 |
|
1447 |
|
1448 |
|
1449 |
|
1450 | function merge_tuples (diffs, start, length) {
|
1451 |
|
1452 | for (var i = start + length - 1; i >= 0 && i >= start - 1; i--) {
|
1453 | if (i + 1 < diffs.length) {
|
1454 | var left_d = diffs[i];
|
1455 | var right_d = diffs[i+1];
|
1456 | if (left_d[0] === right_d[1]) {
|
1457 | diffs.splice(i, 2, [left_d[0], left_d[1] + right_d[1]]);
|
1458 | }
|
1459 | }
|
1460 | }
|
1461 | return diffs;
|
1462 | }
|