commit 2f5ea1f2666b6fd29c2d1d96f9c4078dba7c1002 from: Martin Pieuchot date: Fri Mar 20 19:02:15 2020 UTC Abstract access to atoms.head commit - 2b0f870899f49223307dd81a4e2d4d63ca2ea936 commit + 2f5ea1f2666b6fd29c2d1d96f9c4078dba7c1002 blob - 5df77cf87ea5fd7b1b3e3d0073f2fa02e5c76edc blob + 54bfbd32659848193843158b18d13f6d04d16db9 --- debug.h +++ debug.h @@ -38,9 +38,9 @@ dump_atom(const struct diff_data *left, const struct d return; } if (left) - print(" %3ld", diff_atom_root_idx(left, atom)); + print(" %3ld", DD_ROOT_INDEX(left, atom)); if (right && atom->patience.pos_in_other) - print(" %3ld", diff_atom_root_idx(right, + print(" %3ld", DD_ROOT_INDEX(right, atom->patience.pos_in_other)); print(" %s%s '", atom->patience.unique_here ? "u" : " ", @@ -75,9 +75,9 @@ dump_atoms(const struct diff_data *d, struct diff_atom } static inline void -dump(struct diff_data *d) +dump(struct diff_data *dd) { - dump_atoms(d, d->atoms.head, d->atoms.len); + dump_atoms(dd, dd->atoms.head, dd->atoms.len); } static inline void @@ -129,7 +129,7 @@ dump_myers_graph(const struct diff_data *l, const stru print(" "); for (x = 0; x < l->atoms.len; x++) { - if (diff_atom_same(&l->atoms.head[x], &r->atoms.head[y])) + if (diff_atom_same(DD_ATOM_AT(l, x), DD_ATOM_AT(r, y))) print("|\\"); else print("| "); blob - 66efe86bc24a7dffe6d6b3200b6c590a6f7bcd79 blob + 176909cbcc2d9cf0db227ab76310509e550f0745 --- diff.c +++ diff.c @@ -248,8 +248,8 @@ chunk_context_get(struct chunk_context *cc, const stru if (info->flags & F_UNIFIED) context_lines = info->context; - left_start = diff_atom_root_idx(&r->left, c->left_start); - right_start = diff_atom_root_idx(&r->right, c->right_start); + left_start = DD_ROOT_INDEX(&r->left, c->left_start); + right_start = DD_ROOT_INDEX(&r->right, c->right_start); *cc = (struct chunk_context) { .chunk = { @@ -323,11 +323,11 @@ print_chunk(bool *header_printed, const struct output_ * so it suffices to look on the left. */ first_chunk = &result->chunks.head[cc->chunk.start]; - chunk_start_line = diff_atom_root_idx(&result->left, + chunk_start_line = DD_ROOT_INDEX(&result->left, first_chunk->left_start); if (cc->left.start < chunk_start_line) - print_lines(" ", &result->left.atoms.head[cc->left.start], + print_lines(" ", DD_ATOM_AT(&result->left, cc->left.start), chunk_start_line - cc->left.start); /* Now write out all the joined chunks and contexts between them */ @@ -347,10 +347,10 @@ print_chunk(bool *header_printed, const struct output_ /* Trailing context? */ last_chunk = &result->chunks.head[cc->chunk.end - 1]; - chunk_end_line = diff_atom_root_idx(&result->left, + chunk_end_line = DD_ROOT_INDEX(&result->left, last_chunk->left_start + last_chunk->left_count); if (cc->left.end > chunk_end_line) - print_lines(" ", &result->left.atoms.head[chunk_end_line], + print_lines(" ", DD_ATOM_AT(&result->left, chunk_end_line), cc->left.end - chunk_end_line); } blob - fce8dd1f1c4aba5c7ee0824dcfa879df54b90655 blob + c14efef129560f59679e467d0887f73cde78850d --- diff_main.c +++ diff_main.c @@ -120,21 +120,21 @@ diff_algo_none(const struct diff_algo_config *algo_con /* Add a chunk of equal lines, if any */ while (equal_atoms < state->left.atoms.len && equal_atoms < state->right.atoms.len && - diff_atom_same(&state->left.atoms.head[equal_atoms], - &state->right.atoms.head[equal_atoms])) + diff_atom_same(DD_ATOM_AT(&state->left, equal_atoms), + DD_ATOM_AT(&state->right, equal_atoms))) equal_atoms++; if (equal_atoms) { if (!diff_state_add_chunk(state, true, - &state->left.atoms.head[0], equal_atoms, - &state->right.atoms.head[0], equal_atoms)) + DD_ATOM_AT(&state->left, 0), equal_atoms, + DD_ATOM_AT(&state->right, 0), equal_atoms)) return DIFF_RC_ENOMEM; } /* Add a "minus" chunk with all lines from the left. */ if (equal_atoms < state->left.atoms.len) { if (!diff_state_add_chunk(state, true, - &state->left.atoms.head[equal_atoms], + DD_ATOM_AT(&state->left, equal_atoms), state->left.atoms.len - equal_atoms, NULL, 0)) return DIFF_RC_ENOMEM; @@ -144,7 +144,7 @@ diff_algo_none(const struct diff_algo_config *algo_con if (equal_atoms < state->right.atoms.len) { if (!diff_state_add_chunk(state, true, NULL, 0, - &state->right.atoms.head[equal_atoms], + DD_ATOM_AT(&state->right, equal_atoms), state->right.atoms.len - equal_atoms)) return DIFF_RC_ENOMEM; } blob - da1ebcfe0b9a1a629385cd999582df368828e91f blob + 4ed4751e18170b7687cd69954a5816da10a6743d --- diff_main.h +++ diff_main.h @@ -127,35 +127,45 @@ struct diff_data { void diff_data_free(struct diff_data *diff_data); +#define foreach_diff_atom(_atom, _first, _count) \ + for ((_atom) = (_first); \ + (_atom) && ((_atom) >= (_first)) && \ + ((_atom) - (_first) < (_count)); \ + (_atom)++) + /* - * The atom's index in the entire file. For atoms divided by lines of text, - * this yields the line number (starting with 0). Also works for diff_data - * that reference only a subsection of a file, always reflecting the global - * position in the file (and not the relative position within the subsection). + * Get Atom from `_dd' at given `_index'. */ -#define diff_atom_root_idx(DIFF_DATA, ATOM) \ - ((ATOM) ? (ATOM) - ((DIFF_DATA)->root->atoms.head) : \ - (DIFF_DATA)->root->atoms.len) +#define DD_ATOM_AT(_dd, _index) (&(_dd)->atoms.head[(_index)]) /* - * The atom's index within DIFF_DATA. For atoms divided by lines of text, - * this yields the line number (starting with0). + * Atom index within `_dd'. + * + * For atoms divided by lines of text, this yields the line number + * (starting with 0). */ -#define diff_atom_idx(DIFF_DATA, ATOM) \ - ((ATOM) ? (ATOM) - ((DIFF_DATA)->atoms.head) : (DIFF_DATA)->atoms.len) - -#define foreach_diff_atom(ATOM, FIRST_ATOM, COUNT) \ - for ((ATOM) = (FIRST_ATOM); \ - (ATOM) && ((ATOM) >= (FIRST_ATOM)) && ((ATOM) - (FIRST_ATOM) < (COUNT)); \ - (ATOM)++) +#define DD_ATOM_INDEX(_dd, _atom) \ + ((_atom) != NULL ? (_atom) - ((_dd)->atoms.head) : (_dd)->atoms.len) -#define diff_data_foreach_atom(ATOM, DIFF_DATA) \ - foreach_diff_atom(ATOM, (DIFF_DATA)->atoms.head, (DIFF_DATA)->atoms.len) +/* + * Atom index in the entire file. + * + * For atoms divided by lines of text, this yields the line number + * (starting with 0). Also works for diff_data that reference only a + * subsection of a file, always reflecting the global position in the + * file (and not the relative position within the subsection). + */ +#define DD_ROOT_INDEX(_dd, _atom) DD_ATOM_INDEX((_dd)->root, (_atom)) -#define diff_data_foreach_atom_from(FROM, ATOM, DIFF_DATA) \ - for ((ATOM) = (FROM); \ - (ATOM) && ((ATOM) >= (DIFF_DATA)->atoms.head) && ((ATOM) - (DIFF_DATA)->atoms.head < (DIFF_DATA)->atoms.len); \ - (ATOM)++) +/* + * Iterate over all atoms from `_dd' starting at index `_index'. + */ +#define DD_ATOM_FOREACH(_atom, _dd, _index) \ + for ((_atom) = DD_ATOM_AT(_dd, _index); \ + (_atom) && \ + ((_atom) >= (_dd)->atoms.head) && \ + ((_atom) - (_dd)->atoms.head < (_dd)->atoms.len); \ + (_atom)++) /* * A diff chunk represents a set of atoms on the left and/or a set of atoms blob - 5e0aa25f1daa1b2eee0d2c3c8df19e127ae02f19 blob + 12558d34034a00395ecdcfed676f506cb93e5046 --- diff_myers.c +++ diff_myers.c @@ -318,8 +318,8 @@ diff_divide_myers_forward(struct diff_data *left, stru /* Slide down any snake that we might find here. */ while (x < left->atoms.len && xk_to_y(x, k) < right->atoms.len && - diff_atom_same(&left->atoms.head[x], - &right->atoms.head[xk_to_y(x, k)])) + diff_atom_same(DD_ATOM_AT(left, x), + DD_ATOM_AT(right, xk_to_y(x, k)))) x++; kd_forward[k] = x; @@ -332,13 +332,13 @@ diff_divide_myers_forward(struct diff_data *left, stru if (kd_forward[fi] >= 0 && kd_forward[fi] < left->atoms.len) debug_dump_atom(left, right, - &left->atoms.head[kd_forward[fi]]); + DD_ATOM_AT(left, kd_forward[fi])); else debug("\n"); if (kd_forward[fi]-fi >= 0 && kd_forward[fi]-fi < right->atoms.len) debug_dump_atom(right, left, - &right->atoms.head[kd_forward[fi] + DD_ATOM_AT(right, kd_forward[fi) - fi]); else debug("\n"); @@ -606,16 +606,16 @@ diff_divide_myers_backward(struct diff_data *left, str xc_to_y(x, c, delta), xc_to_y(x, c, delta)-1); if (x > 0) { debug(" l="); debug_dump_atom(left, right, - &left->atoms.head[x-1]); + DD_ATOM_AT(left, x-1)); } if (xc_to_y(x, c, delta) > 0) { debug(" r="); debug_dump_atom(right, left, - &right->atoms.head[xc_to_y(x, c, delta)-1]); + DD_ATOM_AT(right, xc_to_y(x, c, delta)-1)); } while (x > 0 && xc_to_y(x, c, delta) > 0 && - diff_atom_same(&left->atoms.head[x - 1], - &right->atoms.head[xc_to_y(x, c, delta) - 1])) + diff_atom_same(DD_ATOM_AT(left, x - 1), + DD_ATOM_AT(right, xc_to_y(x, c, delta) - 1))) x--; kd_backward[c] = x; @@ -629,13 +629,13 @@ diff_divide_myers_backward(struct diff_data *left, str if (kd_backward[fi] >= 0 && kd_backward[fi] < left->atoms.len) debug_dump_atom(left, right, - &left->atoms.head[kd_backward[fi]]); + DD_ATOM_AT(left, kd_backward[fi])); else debug("\n"); if (kd_backward[fi]-fi+delta >= 0 && kd_backward[fi]-fi+delta < right->atoms.len) debug_dump_atom(right, left, - &right->atoms.head[kd_backward[fi]-fi+delta]); + DD_ATOM_AT(right, kd_backward[fi]-fi+delta)); else debug("\n"); #endif @@ -808,9 +808,9 @@ diff_algo_myers_divide(const struct diff_algo_config * /* Section before the mid-snake. */ debug("Section before the mid-snake\n"); - struct diff_atom *left_atom = &left->atoms.head[0]; + struct diff_atom *left_atom = DD_ATOM_AT(left, 0); unsigned int left_section_len = mid_snake.left_start; - struct diff_atom *right_atom = &right->atoms.head[0]; + struct diff_atom *right_atom = DD_ATOM_AT(right, 0); unsigned int right_section_len = mid_snake.right_start; if (left_section_len && right_section_len) { @@ -849,9 +849,9 @@ diff_algo_myers_divide(const struct diff_algo_config * /* the mid-snake, identical data on both sides: */ debug("the mid-snake\n"); if (!diff_state_add_chunk(state, true, - &left->atoms.head[mid_snake.left_start], + DD_ATOM_AT(left, mid_snake.left_start), mid_snake.left_end - mid_snake.left_start, - &right->atoms.head[mid_snake.right_start], + DD_ATOM_AT(right, mid_snake.right_start), mid_snake.right_end - mid_snake.right_start)) goto return_rc; @@ -862,9 +862,9 @@ diff_algo_myers_divide(const struct diff_algo_config * debug(" left_count %u right_count %u\n", left->atoms.len, right->atoms.len); - left_atom = &left->atoms.head[mid_snake.left_end]; + left_atom = DD_ATOM_AT(left, mid_snake.left_end); left_section_len = left->atoms.len - mid_snake.left_end; - right_atom = &right->atoms.head[mid_snake.right_end]; + right_atom = DD_ATOM_AT(right, mid_snake.right_end); right_section_len = right->atoms.len - mid_snake.right_end; if (left_section_len && right_section_len) { @@ -1070,8 +1070,8 @@ diff_algo_myers(const struct diff_algo_config *algo_co /* Slide down any snake that we might find here. */ while (x < left->atoms.len && xk_to_y(x, k) < right->atoms.len && - diff_atom_same(&left->atoms.head[x], - &right->atoms.head[xk_to_y(x, k)])) + diff_atom_same(DD_ATOM_AT(left, x), + DD_ATOM_AT(right, xk_to_y(x, k)))) x++; kd_column[k] = x; @@ -1084,13 +1084,13 @@ diff_algo_myers(const struct diff_algo_config *algo_co if (kd_column[fi] >= 0 && kd_column[fi] < left->atoms.len) debug_dump_atom(left, right, - &left->atoms.head[kd_column[fi]]); + DD_ATOM_AT(left, kd_column[fi])); else debug("\n"); if (kd_column[fi]-fi >= 0 && kd_column[fi]-fi < right->atoms.len) debug_dump_atom(right, left, - &right->atoms.head[kd_column[fi]-fi]); + DD_ATOM_AT(right, kd_column[fi]-fi)); else debug("\n"); #endif @@ -1208,9 +1208,9 @@ diff_algo_myers(const struct diff_algo_config *algo_co debug("Forward track from xy(%d,%d) to xy(%d,%d)\n", x, y, next_x, next_y); - struct diff_atom *left_atom = &left->atoms.head[x]; + struct diff_atom *left_atom = DD_ATOM_AT(left, x); int left_section_len = next_x - x; - struct diff_atom *right_atom = &right->atoms.head[y]; + struct diff_atom *right_atom = DD_ATOM_AT(right, y); int right_section_len = next_y - y; rc = DIFF_RC_ENOMEM; blob - e23b94cafee7ab142de2f55d8cb65f54ff9a1981 blob + ad1277540a1e9a2d0a96ca0573c21ca19a01481d --- diff_patience.c +++ diff_patience.c @@ -30,29 +30,29 @@ /* Set unique_here = true for all atoms that exist exactly once in this list. */ static void -diff_atoms_mark_unique(struct diff_data *d, unsigned int *unique_count) +diff_atoms_mark_unique(struct diff_data *dd, unsigned int *unique_count) { - struct diff_atom *i, *j; + struct diff_atom *atom, *anext; unsigned int count = 0; - diff_data_foreach_atom(i, d) { - i->patience.unique_here = true; - i->patience.unique_in_both = true; + DD_ATOM_FOREACH(atom, dd, 0) { + atom->patience.unique_here = true; + atom->patience.unique_in_both = true; count++; } - diff_data_foreach_atom(i, d) { - if (!i->patience.unique_here) + DD_ATOM_FOREACH(atom, dd, 0) { + if (!atom->patience.unique_here) continue; - diff_data_foreach_atom_from(i + 1, j, d) { - if (diff_atom_same(i, j)) { - if (i->patience.unique_here) { - i->patience.unique_here = false; - i->patience.unique_in_both = false; + DD_ATOM_FOREACH(anext, dd, DD_ATOM_INDEX(dd, atom + 1)) { + if (diff_atom_same(atom, anext)) { + if (atom->patience.unique_here) { + atom->patience.unique_here = false; + atom->patience.unique_in_both = false; count--; } - j->patience.unique_here = false; - j->patience.unique_in_both = false; + anext->patience.unique_here = false; + anext->patience.unique_in_both = false; count--; } } @@ -70,7 +70,7 @@ diff_atoms_mark_unique_in_both(struct diff_data *left, unsigned int *unique_in_both_count) { unsigned int unique_in_both; - struct diff_atom *i, *j; + struct diff_atom *atom, *j; int found_in_b; bool found_in_a; @@ -84,29 +84,29 @@ diff_atoms_mark_unique_in_both(struct diff_data *left, debug("unique_in_both %u\n", unique_in_both); - diff_data_foreach_atom(i, left) { - if (!i->patience.unique_here) + DD_ATOM_FOREACH(atom, left, 0) { + if (!atom->patience.unique_here) continue; found_in_b = 0; - diff_data_foreach_atom(j, right) { - if (!diff_atom_same(i, j)) + DD_ATOM_FOREACH(j, right, 0) { + if (!diff_atom_same(atom, j)) continue; if (!j->patience.unique_here) { found_in_b = 2; /* or more */ break; } else { found_in_b = 1; - j->patience.pos_in_other = i; - i->patience.pos_in_other = j; + j->patience.pos_in_other = atom; + atom->patience.pos_in_other = j; } } if (found_in_b == 0 || found_in_b > 1) { - i->patience.unique_in_both = false; + atom->patience.unique_in_both = false; unique_in_both--; debug("unique_in_both %u (%d) ", unique_in_both, found_in_b); - debug_dump_atom(left, NULL, i); + debug_dump_atom(left, NULL, atom); } } @@ -114,22 +114,22 @@ diff_atoms_mark_unique_in_both(struct diff_data *left, * Still need to unmark right[*]->patience.unique_in_both for * atoms that don't exist in left */ - diff_data_foreach_atom(i, right) { - if (!i->patience.unique_here || - !i->patience.unique_in_both) + DD_ATOM_FOREACH(atom, right, 0) { + if (!atom->patience.unique_here || + !atom->patience.unique_in_both) continue; found_in_a = false; - diff_data_foreach_atom(j, left) { + DD_ATOM_FOREACH(j, left, 0) { if (!j->patience.unique_in_both) continue; - if (!diff_atom_same(i, j)) + if (!diff_atom_same(atom, j)) continue; found_in_a = true; break; } if (!found_in_a) - i->patience.unique_in_both = false; + atom->patience.unique_in_both = false; } if (unique_in_both_count) @@ -150,7 +150,7 @@ diff_atoms_swallow_identical_neighbors(struct diff_dat debug("trivially combine identical lines around unique_in_both lines\n"); for (l_idx = 0; l_idx < left->atoms.len; l_idx = next_l_idx) { - struct diff_atom *l = &left->atoms.head[l_idx]; + struct diff_atom *l = DD_ATOM_AT(left, l_idx); next_l_idx = l_idx + 1; if (!l->patience.unique_in_both) @@ -159,7 +159,7 @@ diff_atoms_swallow_identical_neighbors(struct diff_dat debug("check identical lines around "); debug_dump_atom(left, right, l); - r_idx = diff_atom_idx(right, l->patience.pos_in_other); + r_idx = DD_ATOM_INDEX(right, l->patience.pos_in_other); /* Swallow upwards. @@ -173,8 +173,8 @@ diff_atoms_swallow_identical_neighbors(struct diff_dat */ for (identical_l.start = l_idx, identical_r.start = r_idx; (identical_l.start > l_min && identical_r.start > r_min && - diff_atom_same(&left->atoms.head[identical_l.start - 1], - &right->atoms.head[identical_r.start - 1])); + diff_atom_same(DD_ATOM_AT(left, identical_l.start - 1), + DD_ATOM_AT(right, identical_r.start - 1))); identical_l.start--, identical_r.start--) ; @@ -182,16 +182,16 @@ diff_atoms_swallow_identical_neighbors(struct diff_dat for (identical_l.end = l_idx + 1, identical_r.end = r_idx + 1; (identical_l.end < left->atoms.len && identical_r.end < right->atoms.len && - diff_atom_same(&left->atoms.head[identical_l.end], - &right->atoms.head[identical_r.end])); + diff_atom_same(DD_ATOM_AT(left, identical_l.end), + DD_ATOM_AT(right, identical_r.end))); identical_l.end++, identical_r.end++, next_l_idx++) { - if (left->atoms.head[identical_l.end].patience.unique_in_both) { + if (DD_ATOM_AT(left, identical_l.end)->patience.unique_in_both) { /* * Part of a chunk of identical lines, remove * from listing of unique_in_both lines */ - left->atoms.head[identical_l.end].patience.unique_in_both = false; - right->atoms.head[identical_r.end].patience.unique_in_both = false; + DD_ATOM_AT(left, identical_l.end)->patience.unique_in_both = false; + DD_ATOM_AT(right, identical_r.end)->patience.unique_in_both = false; (*unique_in_both_count)--; } } @@ -296,7 +296,7 @@ diff_algo_patience(const struct diff_algo_config *algo /* Take all common, unique items from 'left' ... */ uniques_end = uniques; - diff_data_foreach_atom(atom, left) { + DD_ATOM_FOREACH(atom, left, 0) { if (!atom->patience.unique_in_both) continue; *uniques_end = atom; @@ -414,8 +414,8 @@ diff_algo_patience(const struct diff_algo_config *algo atom = lcs[i]; atom_r = atom->patience.pos_in_other; debug("lcs[%u] = left[%ld] = right[%ld]\n", i, - diff_atom_idx(left, atom), - diff_atom_idx(right, atom_r)); + DD_ATOM_INDEX(left, atom), + DD_ATOM_INDEX(right, atom_r)); left_idx = atom->patience.identical_lines.start; right_idx = atom_r->patience.identical_lines.start; debug(" identical lines l %u-%u r %u-%u\n", @@ -451,10 +451,10 @@ diff_algo_patience(const struct diff_algo_config *algo right_idx); /* Section before the matching atom */ - struct diff_atom *left_atom = &left->atoms.head[left_pos]; + struct diff_atom *left_atom = DD_ATOM_AT(left, left_pos); unsigned int left_section_len = left_idx - left_pos; - struct diff_atom *right_atom = &(right->atoms.head[right_pos]); + struct diff_atom *right_atom = DD_ATOM_AT(right, right_pos); unsigned int right_section_len = right_idx - right_pos; if (left_section_len && right_section_len) { @@ -498,9 +498,9 @@ diff_algo_patience(const struct diff_algo_config *algo */ if (atom) { if (!diff_state_add_chunk(state, true, - left->atoms.head + atom->patience.identical_lines.start, + DD_ATOM_AT(left, atom->patience.identical_lines.start), range_len(&atom->patience.identical_lines), - right->atoms.head + atom_r->patience.identical_lines.start, + DD_ATOM_AT(right, atom_r->patience.identical_lines.start), range_len(&atom_r->patience.identical_lines))) goto return_rc; left_pos = atom->patience.identical_lines.end;