1 3b0f3d61 2020-01-22 neels /* Implementation of the Patience Diff algorithm invented by Bram Cohen:
  2 3b0f3d61 2020-01-22 neels  * Divide a diff problem into smaller chunks by an LCS of common-unique lines. */
  3 3b0f3d61 2020-01-22 neels /*
  4 3b0f3d61 2020-01-22 neels  * Copyright (c) 2020 Neels Hofmeyr <neels@hofmeyr.de>
  5 3b0f3d61 2020-01-22 neels  *
  6 3b0f3d61 2020-01-22 neels  * Permission to use, copy, modify, and distribute this software for any
  7 3b0f3d61 2020-01-22 neels  * purpose with or without fee is hereby granted, provided that the above
  8 3b0f3d61 2020-01-22 neels  * copyright notice and this permission notice appear in all copies.
  9 3b0f3d61 2020-01-22 neels  *
 10 3b0f3d61 2020-01-22 neels  * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
 11 3b0f3d61 2020-01-22 neels  * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
 12 3b0f3d61 2020-01-22 neels  * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
 13 3b0f3d61 2020-01-22 neels  * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
 14 3b0f3d61 2020-01-22 neels  * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
 15 3b0f3d61 2020-01-22 neels  * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
 16 3b0f3d61 2020-01-22 neels  * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
 17 3b0f3d61 2020-01-22 neels  */
 18 3b0f3d61 2020-01-22 neels 
 19 3b0f3d61 2020-01-22 neels #include <assert.h>
 20 3b0f3d61 2020-01-22 neels #include <diff/diff_main.h>
 21 3b0f3d61 2020-01-22 neels 
 22 3b0f3d61 2020-01-22 neels #include "debug.h"
 23 3b0f3d61 2020-01-22 neels 
 24 3b0f3d61 2020-01-22 neels /* Set unique_here = true for all atoms that exist exactly once in this list. */
 25 3b0f3d61 2020-01-22 neels static void diff_atoms_mark_unique(struct diff_data *d, unsigned int *unique_count)
 26 3b0f3d61 2020-01-22 neels {
 27 3b0f3d61 2020-01-22 neels 	struct diff_atom *i;
 28 3b0f3d61 2020-01-22 neels 	unsigned int count = 0;
 29 3b0f3d61 2020-01-22 neels 	diff_data_foreach_atom(i, d) {
 30 3b0f3d61 2020-01-22 neels 		i->patience.unique_here = true;
 31 3b0f3d61 2020-01-22 neels 		i->patience.unique_in_both = true;
 32 3b0f3d61 2020-01-22 neels 		count++;
 33 3b0f3d61 2020-01-22 neels 	}
 34 3b0f3d61 2020-01-22 neels 	diff_data_foreach_atom(i, d) {
 35 3b0f3d61 2020-01-22 neels 		struct diff_atom *j;
 36 3b0f3d61 2020-01-22 neels 
 37 3b0f3d61 2020-01-22 neels 		if (!i->patience.unique_here)
 38 3b0f3d61 2020-01-22 neels 			continue;
 39 3b0f3d61 2020-01-22 neels 
 40 3b0f3d61 2020-01-22 neels 		diff_data_foreach_atom_from(i + 1, j, d) {
 41 3b0f3d61 2020-01-22 neels 			if (diff_atom_same(i, j)) {
 42 3b0f3d61 2020-01-22 neels 				if (i->patience.unique_here) {
 43 3b0f3d61 2020-01-22 neels 					i->patience.unique_here = false;
 44 3b0f3d61 2020-01-22 neels 					i->patience.unique_in_both = false;
 45 3b0f3d61 2020-01-22 neels 					count--;
 46 3b0f3d61 2020-01-22 neels 				}
 47 3b0f3d61 2020-01-22 neels 				j->patience.unique_here = false;
 48 3b0f3d61 2020-01-22 neels 				j->patience.unique_in_both = false;
 49 3b0f3d61 2020-01-22 neels 				count--;
 50 3b0f3d61 2020-01-22 neels 			}
 51 3b0f3d61 2020-01-22 neels 		}
 52 3b0f3d61 2020-01-22 neels 	}
 53 3b0f3d61 2020-01-22 neels 	if (unique_count)
 54 3b0f3d61 2020-01-22 neels 		*unique_count = count;
 55 3b0f3d61 2020-01-22 neels }
 56 3b0f3d61 2020-01-22 neels 
 57 3b0f3d61 2020-01-22 neels /* Mark those lines as atom->patience.unique_in_both = true that appear exactly once in each side. */
 58 3b0f3d61 2020-01-22 neels static void diff_atoms_mark_unique_in_both(struct diff_data *left, struct diff_data *right,
 59 3b0f3d61 2020-01-22 neels 					   unsigned int *unique_in_both_count)
 60 3b0f3d61 2020-01-22 neels {
 61 3b0f3d61 2020-01-22 neels 	/* Derive the final unique_in_both count without needing an explicit iteration. So this is just some
 62 3b0f3d61 2020-01-22 neels 	 * optimiziation to save one iteration in the end. */
 63 3b0f3d61 2020-01-22 neels 	unsigned int unique_in_both;
 64 3b0f3d61 2020-01-22 neels 
 65 3b0f3d61 2020-01-22 neels 	diff_atoms_mark_unique(left, &unique_in_both);
 66 3b0f3d61 2020-01-22 neels 	diff_atoms_mark_unique(right, NULL);
 67 3b0f3d61 2020-01-22 neels 
 68 3b0f3d61 2020-01-22 neels 	debug("unique_in_both %u\n", unique_in_both);
 69 3b0f3d61 2020-01-22 neels 
 70 3b0f3d61 2020-01-22 neels 	struct diff_atom *i;
 71 3b0f3d61 2020-01-22 neels 	diff_data_foreach_atom(i, left) {
 72 3b0f3d61 2020-01-22 neels 		if (!i->patience.unique_here)
 73 3b0f3d61 2020-01-22 neels 			continue;
 74 3b0f3d61 2020-01-22 neels 		struct diff_atom *j;
 75 3b0f3d61 2020-01-22 neels 		int found_in_b = 0;
 76 3b0f3d61 2020-01-22 neels 		diff_data_foreach_atom(j, right) {
 77 3b0f3d61 2020-01-22 neels 			if (!diff_atom_same(i, j))
 78 3b0f3d61 2020-01-22 neels 				continue;
 79 3b0f3d61 2020-01-22 neels 			if (!j->patience.unique_here) {
 80 3b0f3d61 2020-01-22 neels 				found_in_b = 2; /* or more */
 81 3b0f3d61 2020-01-22 neels 				break;
 82 3b0f3d61 2020-01-22 neels 			} else {
 83 3b0f3d61 2020-01-22 neels 				found_in_b = 1;
 84 3b0f3d61 2020-01-22 neels 				j->patience.pos_in_other = i;
 85 3b0f3d61 2020-01-22 neels 				i->patience.pos_in_other = j;
 86 3b0f3d61 2020-01-22 neels 			}
 87 3b0f3d61 2020-01-22 neels 		}
 88 3b0f3d61 2020-01-22 neels 
 89 3b0f3d61 2020-01-22 neels 		if (found_in_b == 0 || found_in_b > 1) {
 90 3b0f3d61 2020-01-22 neels 			i->patience.unique_in_both = false;
 91 3b0f3d61 2020-01-22 neels 			unique_in_both--;
 92 3b0f3d61 2020-01-22 neels 			debug("unique_in_both %u  (%d) ", unique_in_both, found_in_b);
 93 3b0f3d61 2020-01-22 neels 			debug_dump_atom(left, NULL, i);
 94 3b0f3d61 2020-01-22 neels 		}
 95 3b0f3d61 2020-01-22 neels 	}
 96 3b0f3d61 2020-01-22 neels 
 97 3b0f3d61 2020-01-22 neels 	/* Still need to unmark right[*]->patience.unique_in_both for atoms that don't exist in left */
 98 3b0f3d61 2020-01-22 neels 	diff_data_foreach_atom(i, right) {
 99 3b0f3d61 2020-01-22 neels 		if (!i->patience.unique_here
100 3b0f3d61 2020-01-22 neels 		    || !i->patience.unique_in_both)
101 3b0f3d61 2020-01-22 neels 			continue;
102 3b0f3d61 2020-01-22 neels 		struct diff_atom *j;
103 3b0f3d61 2020-01-22 neels 		bool found_in_a = false;
104 3b0f3d61 2020-01-22 neels 		diff_data_foreach_atom(j, left) {
105 3b0f3d61 2020-01-22 neels 			if (!j->patience.unique_in_both)
106 3b0f3d61 2020-01-22 neels 				continue;
107 3b0f3d61 2020-01-22 neels 			if (!diff_atom_same(i, j))
108 3b0f3d61 2020-01-22 neels 				continue;
109 3b0f3d61 2020-01-22 neels 			found_in_a = true;
110 3b0f3d61 2020-01-22 neels 			break;
111 3b0f3d61 2020-01-22 neels 		}
112 3b0f3d61 2020-01-22 neels 
113 3b0f3d61 2020-01-22 neels 		if (!found_in_a)
114 3b0f3d61 2020-01-22 neels 			i->patience.unique_in_both = false;
115 3b0f3d61 2020-01-22 neels 	}
116 3b0f3d61 2020-01-22 neels 
117 3b0f3d61 2020-01-22 neels 	if (unique_in_both_count)
118 3b0f3d61 2020-01-22 neels 		*unique_in_both_count = unique_in_both;
119 3b0f3d61 2020-01-22 neels }
120 3b0f3d61 2020-01-22 neels 
121 bb7fb738 2020-01-27 neels static void diff_atoms_swallow_identical_neighbors(struct diff_data *left, struct diff_data *right,
122 bb7fb738 2020-01-27 neels 						   unsigned int *unique_in_both_count)
123 bb7fb738 2020-01-27 neels {
124 bb7fb738 2020-01-27 neels 	debug("trivially combine identical lines arount unique_in_both lines\n");
125 3b0f3d61 2020-01-22 neels 
126 bb7fb738 2020-01-27 neels 	unsigned int l_idx;
127 bb7fb738 2020-01-27 neels 	unsigned int next_l_idx;
128 bb7fb738 2020-01-27 neels 	unsigned int l_min = 0;
129 bb7fb738 2020-01-27 neels 	unsigned int r_min = 0;
130 bb7fb738 2020-01-27 neels 	for (l_idx = 0; l_idx < left->atoms.len; l_idx = next_l_idx) {
131 bb7fb738 2020-01-27 neels 		next_l_idx = l_idx + 1;
132 bb7fb738 2020-01-27 neels 		struct diff_atom *l = &left->atoms.head[l_idx];
133 bb7fb738 2020-01-27 neels 
134 bb7fb738 2020-01-27 neels 		if (!l->patience.unique_in_both)
135 bb7fb738 2020-01-27 neels 			continue;
136 bb7fb738 2020-01-27 neels 
137 bb7fb738 2020-01-27 neels 		debug("check identical lines around ");
138 bb7fb738 2020-01-27 neels 		debug_dump_atom(left, right, l);
139 bb7fb738 2020-01-27 neels 
140 bb7fb738 2020-01-27 neels 		unsigned int r_idx = diff_atom_idx(right, l->patience.pos_in_other);
141 bb7fb738 2020-01-27 neels 
142 bb7fb738 2020-01-27 neels 		struct range identical_l;
143 bb7fb738 2020-01-27 neels 		struct range identical_r;
144 bb7fb738 2020-01-27 neels 
145 bb7fb738 2020-01-27 neels 		/* Swallow upwards.
146 bb7fb738 2020-01-27 neels 		 * Each common-unique line swallows identical lines upwards and downwards.
147 bb7fb738 2020-01-27 neels 		 * All common-unique lines that were part of the identical lines following below were already swallowed
148 bb7fb738 2020-01-27 neels 		 * in the previous iteration, so we will never hit another common-unique line above. */
149 bb7fb738 2020-01-27 neels 		for (identical_l.start = l_idx, identical_r.start = r_idx;
150 bb7fb738 2020-01-27 neels 		     identical_l.start > l_min
151 bb7fb738 2020-01-27 neels 		     && identical_r.start > r_min
152 bb7fb738 2020-01-27 neels 		     && diff_atom_same(&left->atoms.head[identical_l.start - 1],
153 bb7fb738 2020-01-27 neels 				       &right->atoms.head[identical_r.start - 1]);
154 bb7fb738 2020-01-27 neels 		     identical_l.start--, identical_r.start--);
155 bb7fb738 2020-01-27 neels 
156 bb7fb738 2020-01-27 neels 		/* Swallow downwards */
157 bb7fb738 2020-01-27 neels 		for (identical_l.end = l_idx + 1, identical_r.end = r_idx + 1;
158 bb7fb738 2020-01-27 neels 		     identical_l.end < left->atoms.len
159 bb7fb738 2020-01-27 neels 		     && identical_r.end < right->atoms.len
160 bb7fb738 2020-01-27 neels 		     && diff_atom_same(&left->atoms.head[identical_l.end],
161 bb7fb738 2020-01-27 neels 				       &right->atoms.head[identical_r.end]);
162 bb7fb738 2020-01-27 neels 		     identical_l.end++, identical_r.end++,
163 bb7fb738 2020-01-27 neels 		     next_l_idx++) {
164 bb7fb738 2020-01-27 neels 			if (left->atoms.head[identical_l.end].patience.unique_in_both) {
165 bb7fb738 2020-01-27 neels 				/* Part of a chunk of identical lines, remove from listing of unique_in_both lines */
166 bb7fb738 2020-01-27 neels 				left->atoms.head[identical_l.end].patience.unique_in_both = false;
167 bb7fb738 2020-01-27 neels 				right->atoms.head[identical_r.end].patience.unique_in_both = false;
168 bb7fb738 2020-01-27 neels 				(*unique_in_both_count)--;
169 bb7fb738 2020-01-27 neels 			}
170 bb7fb738 2020-01-27 neels 		}
171 bb7fb738 2020-01-27 neels 
172 bb7fb738 2020-01-27 neels 		l->patience.identical_lines = identical_l;
173 bb7fb738 2020-01-27 neels 		l->patience.pos_in_other->patience.identical_lines = identical_r;
174 bb7fb738 2020-01-27 neels 
175 bb7fb738 2020-01-27 neels 		l_min = identical_l.end;
176 bb7fb738 2020-01-27 neels 		r_min = identical_r.end;
177 bb7fb738 2020-01-27 neels 
178 bb7fb738 2020-01-27 neels 		if (!range_empty(&l->patience.identical_lines)) {
179 bb7fb738 2020-01-27 neels 			debug("common-unique line at l=%u r=%u swallowed identical lines l=%u-%u r=%u-%u\n",
180 bb7fb738 2020-01-27 neels 			      l_idx, r_idx,
181 bb7fb738 2020-01-27 neels 			      identical_l.start, identical_l.end,
182 bb7fb738 2020-01-27 neels 			      identical_r.start, identical_r.end);
183 bb7fb738 2020-01-27 neels 		}
184 bb7fb738 2020-01-27 neels 		debug("next_l_idx = %u\n", next_l_idx);
185 bb7fb738 2020-01-27 neels 	}
186 bb7fb738 2020-01-27 neels }
187 bb7fb738 2020-01-27 neels 
188 3b0f3d61 2020-01-22 neels /* Among the lines that appear exactly once in each side, find the longest streak that appear in both files in the same
189 3b0f3d61 2020-01-22 neels  * order (with other stuff allowed to interleave). Use patience sort for that, as in the Patience Diff algorithm.
190 3b0f3d61 2020-01-22 neels  * See https://bramcohen.livejournal.com/73318.html and, for a much more detailed explanation,
191 3b0f3d61 2020-01-22 neels  * https://blog.jcoglan.com/2017/09/19/the-patience-diff-algorithm/ */
192 3b0f3d61 2020-01-22 neels enum diff_rc diff_algo_patience(const struct diff_algo_config *algo_config, struct diff_state *state)
193 3b0f3d61 2020-01-22 neels {
194 3b0f3d61 2020-01-22 neels 	enum diff_rc rc = DIFF_RC_ENOMEM;
195 3b0f3d61 2020-01-22 neels 
196 3b0f3d61 2020-01-22 neels 	struct diff_data *left = &state->left;
197 3b0f3d61 2020-01-22 neels 	struct diff_data *right = &state->right;
198 3b0f3d61 2020-01-22 neels 
199 3b0f3d61 2020-01-22 neels 	unsigned int unique_in_both_count;
200 3b0f3d61 2020-01-22 neels 
201 3b0f3d61 2020-01-22 neels 	debug("\n** %s\n", __func__);
202 3b0f3d61 2020-01-22 neels 
203 3b0f3d61 2020-01-22 neels 	/* Find those lines that appear exactly once in 'left' and exactly once in 'right'. */
204 3b0f3d61 2020-01-22 neels 	diff_atoms_mark_unique_in_both(left, right, &unique_in_both_count);
205 3b0f3d61 2020-01-22 neels 
206 3b0f3d61 2020-01-22 neels 	debug("unique_in_both_count %u\n", unique_in_both_count);
207 3b0f3d61 2020-01-22 neels 	debug("left:\n");
208 3b0f3d61 2020-01-22 neels 	debug_dump(left);
209 3b0f3d61 2020-01-22 neels 	debug("right:\n");
210 3b0f3d61 2020-01-22 neels 	debug_dump(right);
211 3b0f3d61 2020-01-22 neels 
212 3b0f3d61 2020-01-22 neels 	if (!unique_in_both_count) {
213 3b0f3d61 2020-01-22 neels 		/* Cannot apply Patience, tell the caller to use fallback_algo instead. */
214 3b0f3d61 2020-01-22 neels 		return DIFF_RC_USE_DIFF_ALGO_FALLBACK;
215 3b0f3d61 2020-01-22 neels 	}
216 3b0f3d61 2020-01-22 neels 
217 bb7fb738 2020-01-27 neels 	diff_atoms_swallow_identical_neighbors(left, right, &unique_in_both_count);
218 bb7fb738 2020-01-27 neels 	debug("After swallowing identical neighbors: unique_in_both = %u\n",
219 bb7fb738 2020-01-27 neels 	      unique_in_both_count);
220 bb7fb738 2020-01-27 neels 
221 3b0f3d61 2020-01-22 neels 	/* An array of Longest Common Sequence is the result of the below subscope: */
222 3b0f3d61 2020-01-22 neels 	unsigned int lcs_count = 0;
223 3b0f3d61 2020-01-22 neels 	struct diff_atom **lcs = NULL;
224 3b0f3d61 2020-01-22 neels 	struct diff_atom *lcs_tail = NULL;
225 3b0f3d61 2020-01-22 neels 
226 3b0f3d61 2020-01-22 neels 	{
227 3b0f3d61 2020-01-22 neels 		/* This subscope marks the lifetime of the atom_pointers allocation */
228 3b0f3d61 2020-01-22 neels 
229 3b0f3d61 2020-01-22 neels 		/* One chunk of storage for atom pointers */
230 3b0f3d61 2020-01-22 neels 		struct diff_atom **atom_pointers = recallocarray(NULL, 0, unique_in_both_count * 2, sizeof(struct diff_atom*));
231 3b0f3d61 2020-01-22 neels 
232 3b0f3d61 2020-01-22 neels 		/* Half for the list of atoms that still need to be put on stacks */
233 3b0f3d61 2020-01-22 neels 		struct diff_atom **uniques = atom_pointers;
234 3b0f3d61 2020-01-22 neels 
235 3b0f3d61 2020-01-22 neels 		/* Half for the patience sort state's "card stacks" -- we remember only each stack's topmost "card" */
236 3b0f3d61 2020-01-22 neels 		struct diff_atom **patience_stacks = atom_pointers + unique_in_both_count;
237 3b0f3d61 2020-01-22 neels 		unsigned int patience_stacks_count = 0;
238 3b0f3d61 2020-01-22 neels 
239 3b0f3d61 2020-01-22 neels 		/* Take all common, unique items from 'left' ... */
240 3b0f3d61 2020-01-22 neels 
241 3b0f3d61 2020-01-22 neels 		struct diff_atom *atom;
242 3b0f3d61 2020-01-22 neels 		struct diff_atom **uniques_end = uniques;
243 3b0f3d61 2020-01-22 neels 		diff_data_foreach_atom(atom, left) {
244 3b0f3d61 2020-01-22 neels 			if (!atom->patience.unique_in_both)
245 3b0f3d61 2020-01-22 neels 				continue;
246 3b0f3d61 2020-01-22 neels 			*uniques_end = atom;
247 3b0f3d61 2020-01-22 neels 			uniques_end++;
248 3b0f3d61 2020-01-22 neels 		}
249 3b0f3d61 2020-01-22 neels 
250 3b0f3d61 2020-01-22 neels 		/* ...and sort them to the order found in 'right'.
251 3b0f3d61 2020-01-22 neels 		 * The idea is to find the leftmost stack that has a higher line number and add it to the stack's top.
252 3b0f3d61 2020-01-22 neels 		 * If there is no such stack, open a new one on the right. The line number is derived from the atom*,
253 3b0f3d61 2020-01-22 neels 		 * which are array items and hence reflect the relative position in the source file. So we got the
254 3b0f3d61 2020-01-22 neels 		 * common-uniques from 'left' and sort them according to atom->patience.pos_in_other. */
255 3b0f3d61 2020-01-22 neels 		unsigned int i;
256 3b0f3d61 2020-01-22 neels 		for (i = 0; i < unique_in_both_count; i++) {
257 3b0f3d61 2020-01-22 neels 			atom = uniques[i];
258 3b0f3d61 2020-01-22 neels 			unsigned int target_stack;
259 3b0f3d61 2020-01-22 neels 
260 3b0f3d61 2020-01-22 neels 			if (!patience_stacks_count)
261 3b0f3d61 2020-01-22 neels 				target_stack = 0;
262 3b0f3d61 2020-01-22 neels 			else {
263 3b0f3d61 2020-01-22 neels 				/* binary search to find the stack to put this atom "card" on. */
264 3b0f3d61 2020-01-22 neels 				unsigned int lo = 0;
265 3b0f3d61 2020-01-22 neels 				unsigned int hi = patience_stacks_count;
266 3b0f3d61 2020-01-22 neels 				while (lo < hi) {
267 3b0f3d61 2020-01-22 neels 					unsigned int mid = (lo + hi) >> 1;
268 3b0f3d61 2020-01-22 neels 					if (patience_stacks[mid]->patience.pos_in_other < atom->patience.pos_in_other)
269 3b0f3d61 2020-01-22 neels 						lo = mid + 1;
270 3b0f3d61 2020-01-22 neels 					else
271 3b0f3d61 2020-01-22 neels 						hi = mid;
272 3b0f3d61 2020-01-22 neels 				}
273 3b0f3d61 2020-01-22 neels 
274 3b0f3d61 2020-01-22 neels 				target_stack = lo;
275 3b0f3d61 2020-01-22 neels 			}
276 3b0f3d61 2020-01-22 neels 
277 3b0f3d61 2020-01-22 neels 			assert(target_stack <= patience_stacks_count);
278 3b0f3d61 2020-01-22 neels 			patience_stacks[target_stack] = atom;
279 3b0f3d61 2020-01-22 neels 			if (target_stack == patience_stacks_count)
280 3b0f3d61 2020-01-22 neels 				patience_stacks_count++;
281 3b0f3d61 2020-01-22 neels 
282 3b0f3d61 2020-01-22 neels 			/* Record a back reference to the next stack on the left, which will form the final longest sequence
283 3b0f3d61 2020-01-22 neels 			 * later. */
284 3b0f3d61 2020-01-22 neels 			atom->patience.prev_stack = target_stack ? patience_stacks[target_stack - 1] : NULL;
285 3b0f3d61 2020-01-22 neels 
286 3b0f3d61 2020-01-22 neels 		}
287 3b0f3d61 2020-01-22 neels 
288 3b0f3d61 2020-01-22 neels 		/* backtrace through prev_stack references to form the final longest common sequence */
289 3b0f3d61 2020-01-22 neels 		lcs_tail = patience_stacks[patience_stacks_count - 1];
290 3b0f3d61 2020-01-22 neels 		lcs_count = patience_stacks_count;
291 3b0f3d61 2020-01-22 neels 
292 3b0f3d61 2020-01-22 neels 		/* uniques and patience_stacks are no longer needed. Backpointers are in atom->patience.prev_stack */
293 3b0f3d61 2020-01-22 neels 		free(atom_pointers);
294 3b0f3d61 2020-01-22 neels 	}
295 3b0f3d61 2020-01-22 neels 
296 3b0f3d61 2020-01-22 neels 	lcs = recallocarray(NULL, 0, lcs_count, sizeof(struct diff_atom*));
297 3b0f3d61 2020-01-22 neels 	struct diff_atom **lcs_backtrace_pos = &lcs[lcs_count - 1];
298 3b0f3d61 2020-01-22 neels 	struct diff_atom *atom;
299 3b0f3d61 2020-01-22 neels 	for (atom = lcs_tail; atom; atom = atom->patience.prev_stack, lcs_backtrace_pos--) {
300 3b0f3d61 2020-01-22 neels 		assert(lcs_backtrace_pos >= lcs);
301 3b0f3d61 2020-01-22 neels 		*lcs_backtrace_pos = atom;
302 3b0f3d61 2020-01-22 neels 	}
303 3b0f3d61 2020-01-22 neels 
304 3b0f3d61 2020-01-22 neels 	unsigned int i;
305 3b0f3d61 2020-01-22 neels 	if (DEBUG) {
306 3b0f3d61 2020-01-22 neels 		debug("\npatience LCS:\n");
307 3b0f3d61 2020-01-22 neels 		for (i = 0; i < lcs_count; i++) {
308 3b0f3d61 2020-01-22 neels 			debug_dump_atom(left, right, lcs[i]);
309 3b0f3d61 2020-01-22 neels 		}
310 3b0f3d61 2020-01-22 neels 	}
311 3b0f3d61 2020-01-22 neels 
312 3b0f3d61 2020-01-22 neels 
313 3b0f3d61 2020-01-22 neels 	/* TODO: For each common-unique line found (now listed in lcs), swallow lines upwards and downwards that are
314 3b0f3d61 2020-01-22 neels 	 * identical on each side. Requires a way to represent atoms being glued to adjacent atoms. */
315 3b0f3d61 2020-01-22 neels 
316 3b0f3d61 2020-01-22 neels 	debug("\ntraverse LCS, possibly recursing:\n");
317 3b0f3d61 2020-01-22 neels 
318 3b0f3d61 2020-01-22 neels 	/* Now we have pinned positions in both files at which it makes sense to divide the diff problem into smaller
319 3b0f3d61 2020-01-22 neels 	 * chunks. Go into the next round: look at each section in turn, trying to again find common-unique lines in
320 3b0f3d61 2020-01-22 neels 	 * those smaller sections. As soon as no more are found, the remaining smaller sections are solved by Myers. */
321 3b0f3d61 2020-01-22 neels 	unsigned int left_pos = 0;
322 3b0f3d61 2020-01-22 neels 	unsigned int right_pos = 0;
323 3b0f3d61 2020-01-22 neels 	for (i = 0; i <= lcs_count; i++) {
324 3b0f3d61 2020-01-22 neels 		struct diff_atom *atom;
325 bb7fb738 2020-01-27 neels 		struct diff_atom *atom_r;
326 3b0f3d61 2020-01-22 neels 		unsigned int left_idx;
327 3b0f3d61 2020-01-22 neels 		unsigned int right_idx;
328 3b0f3d61 2020-01-22 neels 
329 3b0f3d61 2020-01-22 neels 		if (i < lcs_count) {
330 3b0f3d61 2020-01-22 neels 			atom = lcs[i];
331 bb7fb738 2020-01-27 neels 			atom_r = atom->patience.pos_in_other;
332 15ac50e2 2020-05-05 neels 			debug("lcs[%u] = left[%ld] = right[%ld]\n", i,
333 bb7fb738 2020-01-27 neels 			      diff_atom_idx(left, atom), diff_atom_idx(right, atom_r));
334 bb7fb738 2020-01-27 neels 			left_idx = atom->patience.identical_lines.start;
335 bb7fb738 2020-01-27 neels 			right_idx = atom_r->patience.identical_lines.start;
336 bb7fb738 2020-01-27 neels 			debug(" identical lines l %u-%u  r %u-%u\n",
337 bb7fb738 2020-01-27 neels 			      atom->patience.identical_lines.start, atom->patience.identical_lines.end,
338 bb7fb738 2020-01-27 neels 			      atom_r->patience.identical_lines.start, atom_r->patience.identical_lines.end);
339 3b0f3d61 2020-01-22 neels 		} else {
340 3b0f3d61 2020-01-22 neels 			atom = NULL;
341 bb7fb738 2020-01-27 neels 			atom_r = NULL;
342 3b0f3d61 2020-01-22 neels 			left_idx = left->atoms.len;
343 3b0f3d61 2020-01-22 neels 			right_idx = right->atoms.len;
344 3b0f3d61 2020-01-22 neels 		}
345 3b0f3d61 2020-01-22 neels 
346 3b0f3d61 2020-01-22 neels 		/* 'atom' now marks an atom that matches on both sides according to patience-diff
347 3b0f3d61 2020-01-22 neels 		 * (a common-unique identical atom in both files).
348 3b0f3d61 2020-01-22 neels 		 * Handle the section before and the atom itself; the section after will be handled by the next loop
349 3b0f3d61 2020-01-22 neels 		 * iteration -- note that i loops to last element + 1 ("i <= lcs_count"), so that there will be another
350 3b0f3d61 2020-01-22 neels 		 * final iteration to pick up the last remaining items after the last LCS atom.
351 3b0f3d61 2020-01-22 neels 		 * The sections before might also be empty on left and/or right.
352 3b0f3d61 2020-01-22 neels 		 * left_pos and right_pos mark the indexes of the first atoms that have not yet been handled in the
353 3b0f3d61 2020-01-22 neels 		 * previous loop iteration.
354 3b0f3d61 2020-01-22 neels 		 * left_idx and right_idx mark the indexes of the matching atom on left and right, respectively. */
355 3b0f3d61 2020-01-22 neels 
356 3b0f3d61 2020-01-22 neels 		debug("iteration %u  left_pos %u  left_idx %u  right_pos %u  right_idx %u\n",
357 3b0f3d61 2020-01-22 neels 		      i, left_pos, left_idx, right_pos, right_idx);
358 3b0f3d61 2020-01-22 neels 
359 3b0f3d61 2020-01-22 neels 		/* Section before the matching atom */
360 3b0f3d61 2020-01-22 neels 		struct diff_atom *left_atom = &left->atoms.head[left_pos];
361 3b0f3d61 2020-01-22 neels 		unsigned int left_section_len = left_idx - left_pos;
362 3b0f3d61 2020-01-22 neels 
363 3b0f3d61 2020-01-22 neels 		struct diff_atom *right_atom = &(right->atoms.head[right_pos]);
364 3b0f3d61 2020-01-22 neels 		unsigned int right_section_len = right_idx - right_pos;
365 3b0f3d61 2020-01-22 neels 
366 3b0f3d61 2020-01-22 neels 		if (left_section_len && right_section_len) {
367 3b0f3d61 2020-01-22 neels 			/* Record an unsolved chunk, the caller will apply inner_algo() on this chunk. */
368 3b0f3d61 2020-01-22 neels 			if (!diff_state_add_chunk(state, false,
369 3b0f3d61 2020-01-22 neels 						  left_atom, left_section_len,
370 3b0f3d61 2020-01-22 neels 						  right_atom, right_section_len))
371 3b0f3d61 2020-01-22 neels 				goto return_rc;
372 3b0f3d61 2020-01-22 neels 		} else if (left_section_len && !right_section_len) {
373 3b0f3d61 2020-01-22 neels 			/* Only left atoms and none on the right, they form a "minus" chunk, then. */
374 3b0f3d61 2020-01-22 neels 			if (!diff_state_add_chunk(state, true,
375 3b0f3d61 2020-01-22 neels 						  left_atom, left_section_len,
376 3b0f3d61 2020-01-22 neels 						  right_atom, 0))
377 3b0f3d61 2020-01-22 neels 				goto return_rc;
378 3b0f3d61 2020-01-22 neels 		} else if (!left_section_len && right_section_len) {
379 3b0f3d61 2020-01-22 neels 			/* No left atoms, only atoms on the right, they form a "plus" chunk, then. */
380 3b0f3d61 2020-01-22 neels 			if (!diff_state_add_chunk(state, true,
381 3b0f3d61 2020-01-22 neels 						  left_atom, 0,
382 3b0f3d61 2020-01-22 neels 						  right_atom, right_section_len))
383 3b0f3d61 2020-01-22 neels 				goto return_rc;
384 3b0f3d61 2020-01-22 neels 		}
385 3b0f3d61 2020-01-22 neels 		/* else: left_section_len == 0 and right_section_len == 0, i.e. nothing here. */
386 3b0f3d61 2020-01-22 neels 
387 3b0f3d61 2020-01-22 neels 		/* The atom found to match on both sides forms a chunk of equals on each side. In the very last
388 3b0f3d61 2020-01-22 neels 		 * iteration of this loop, there is no matching atom, we were just cleaning out the remaining lines. */
389 3b0f3d61 2020-01-22 neels 		if (atom) {
390 3b0f3d61 2020-01-22 neels 			if (!diff_state_add_chunk(state, true,
391 bb7fb738 2020-01-27 neels 						  left->atoms.head + atom->patience.identical_lines.start,
392 bb7fb738 2020-01-27 neels 						  range_len(&atom->patience.identical_lines),
393 bb7fb738 2020-01-27 neels 						  right->atoms.head + atom_r->patience.identical_lines.start,
394 bb7fb738 2020-01-27 neels 						  range_len(&atom_r->patience.identical_lines)))
395 3b0f3d61 2020-01-22 neels 				goto return_rc;
396 bb7fb738 2020-01-27 neels 			left_pos = atom->patience.identical_lines.end;
397 bb7fb738 2020-01-27 neels 			right_pos = atom_r->patience.identical_lines.end;
398 bb7fb738 2020-01-27 neels 		} else {
399 bb7fb738 2020-01-27 neels 			left_pos = left_idx + 1;
400 bb7fb738 2020-01-27 neels 			right_pos = right_idx + 1;
401 3b0f3d61 2020-01-22 neels 		}
402 bb7fb738 2020-01-27 neels 		debug("end of iteration %u  left_pos %u  left_idx %u  right_pos %u  right_idx %u\n",
403 bb7fb738 2020-01-27 neels 		      i, left_pos, left_idx, right_pos, right_idx);
404 3b0f3d61 2020-01-22 neels 	}
405 3b0f3d61 2020-01-22 neels 	debug("** END %s\n", __func__);
406 3b0f3d61 2020-01-22 neels 
407 3b0f3d61 2020-01-22 neels 	rc = DIFF_RC_OK;
408 3b0f3d61 2020-01-22 neels 
409 3b0f3d61 2020-01-22 neels return_rc:
410 3b0f3d61 2020-01-22 neels 	free(lcs);
411 3b0f3d61 2020-01-22 neels 	return rc;
412 3b0f3d61 2020-01-22 neels }