git
1/*2* LibXDiff by Davide Libenzi ( File Differential Library )3* Copyright (C) 2003 Davide Libenzi4*5* This library is free software; you can redistribute it and/or6* modify it under the terms of the GNU Lesser General Public7* License as published by the Free Software Foundation; either8* version 2.1 of the License, or (at your option) any later version.9*10* This library is distributed in the hope that it will be useful,11* but WITHOUT ANY WARRANTY; without even the implied warranty of12* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU13* Lesser General Public License for more details.14*15* You should have received a copy of the GNU Lesser General Public16* License along with this library; if not, see17* <http://www.gnu.org/licenses/>.18*19* Davide Libenzi <davidel@xmailserver.org>20*21*/22/*37* See "An O(ND) Difference Algorithm and its Variations", by Eugene Myers.38* Basically considers a "box" (off1, off2, lim1, lim2) and scan from both39* the forward diagonal starting from (off1, off2) and the backward diagonal40* starting from (lim1, lim2). If the K values on the same diagonal crosses41* returns the furthest point of reach. We might encounter expensive edge cases42* using this algorithm, so a little bit of heuristic is needed to cut the43* search and to return a suboptimal point.44*/45static long xdl_split(unsigned long const *ha1, long off1, long lim1,46unsigned long const *ha2, long off2, long lim2,47long *kvdf, long *kvdb, int need_min, xdpsplit_t *spl,48xdalgoenv_t *xenv) {49long dmin = off1 - lim2, dmax = lim1 - off2;50long fmid = off1 - off2, bmid = lim1 - lim2;51long odd = (fmid - bmid) & 1;52long fmin = fmid, fmax = fmid;53long bmin = bmid, bmax = bmid;54long ec, d, i1, i2, prev1, best, dd, v, k;55* Set initial diagonal values for both forward and backward path.58*/59kvdf[fmid] = off1;60kvdb[bmid] = lim1;61* We need to extend the diagonal "domain" by one. If the next67* values exits the box boundaries we need to change it in the68* opposite direction because (max - min) must be a power of69* two.70*71* Also we initialize the external K value to -1 so that we can72* avoid extra conditions in the check inside the core loop.73*/74if (fmin > dmin)75kvdf[--fmin - 1] = -1;76else77++fmin;78if (fmax < dmax)79kvdf[++fmax + 1] = -1;80else81--fmax;82* We need to extend the diagonal "domain" by one. If the next104* values exits the box boundaries we need to change it in the105* opposite direction because (max - min) must be a power of106* two.107*108* Also we initialize the external K value to -1 so that we can109* avoid extra conditions in the check inside the core loop.110*/111if (bmin > dmin)112kvdb[--bmin - 1] = XDL_LINE_MAX;113else114++bmin;115if (bmax < dmax)116kvdb[++bmax + 1] = XDL_LINE_MAX;117else118--bmax;119* If the edit cost is above the heuristic trigger and if144* we got a good snake, we sample current diagonals to see145* if some of them have reached an "interesting" path. Our146* measure is a function of the distance from the diagonal147* corner (i1 + i2) penalized with the distance from the148* mid diagonal itself. If this value is above the current149* edit cost times a magic factor (XDL_K_HEUR) we consider150* it interesting.151*/152if (got_snake && ec > xenv->heur_min) {153for (best = 0, d = fmax; d >= fmin; d -= 2) {154dd = d > fmid ? d - fmid: fmid - d;155i1 = kvdf[d];156i2 = i1 - d;157v = (i1 - off1) + (i2 - off2) - dd;158* Enough is enough. We spent too much time here and now we204* collect the furthest reaching path using the (i1 + i2)205* measure.206*/207if (ec >= xenv->mxcost) {208long fbest, fbest1, bbest, bbest1;209}249/*252* Rule: "Divide et Impera" (divide & conquer). Recursively split the box in253* sub-boxes by calling the box splitting function. Note that the real job254* (marking changed lines) is done in the two boundary reaching checks.255*/256int xdl_recs_cmp(diffdata_t *dd1, long off1, long lim1,257diffdata_t *dd2, long off2, long lim2,258long *kvdf, long *kvdb, int need_min, xdalgoenv_t *xenv) {259unsigned long const *ha1 = dd1->ha, *ha2 = dd2->ha;260* Shrink the box by walking through each diagonal snake (SW and NE).263*/264for (; off1 < lim1 && off2 < lim2 && ha1[off1] == ha2[off2]; off1++, off2++);265for (; off1 < lim1 && off2 < lim2 && ha1[lim1 - 1] == ha2[lim2 - 1]; lim1--, lim2--);266* If one dimension is empty, then all records on the other one must269* be obviously changed.270*/271if (off1 == lim1) {272char *rchg2 = dd2->rchg;273long *rindex2 = dd2->rindex;274* Divide ...289*/290if (xdl_split(ha1, off1, lim1, ha2, off2, lim2, kvdf, kvdb,291need_min, &spl, xenv) < 0) {292* ... et Impera.298*/299if (xdl_recs_cmp(dd1, off1, spl.i1, dd2, off2, spl.i2,300kvdf, kvdb, spl.min_lo, xenv) < 0 ||301xdl_recs_cmp(dd1, spl.i1, lim1, dd2, spl.i2, lim2,302kvdf, kvdb, spl.min_hi, xenv) < 0) {303}310* Allocate and setup K vectors to be used by the differential335* algorithm.336*337* One is to store the forward path and one to store the backward path.338*/339ndiags = xe->xdf1.nreff + xe->xdf2.nreff + 3;340if (!XDL_ALLOC_ARRAY(kvd, 2 * ndiags + 2)) {341}375}392{396return (rec1->ha == rec2->ha);397}398/*400* If a line is indented more than this, get_indent() just returns this value.401* This avoids having to do absurd amounts of work for data that are not402* human-readable text, and also ensures that the output of get_indent fits403* within an int.404*/405#define MAX_INDENT 200406/*408* Return the amount of indentation of the specified line, treating TAB as 8409* columns. Return -1 if line is empty or contains only whitespace. Clamp the410* output value at MAX_INDENT.411*/412static int get_indent(xrecord_t *rec)413{414long i;415int ret = 0;416}435/*437* If more than this number of consecutive blank rows are found, just return438* this value. This avoids requiring O(N^2) work for pathological cases, and439* also ensures that the output of score_split fits in an int.440*/441#define MAX_BLANKS 20442/* Characteristics measured about a hypothetical split position. */444struct split_measurement {445/*446* Is the split at the end of the file (aside from any blank lines)?447*/448int end_of_file;449* How much is the line immediately following the split indented (or -1452* if the line is blank):453*/454int indent;455* How many consecutive lines above the split are blank?458*/459int pre_blank;460* How much is the nearest non-blank line above the split indented (or463* -1 if there is no such line)?464*/465int pre_indent;466* How many lines after the line following the split are blank?469*/470int post_blank;471* How much is the nearest non-blank line after the line following the474* split indented (or -1 if there is no such line)?475*/476int post_indent;477};478/*488* Fill m with information about a hypothetical split of xdf above line split.489*/490static void measure_split(const xdfile_t *xdf, long split,491struct split_measurement *m)492{493long i;494}529/*531* The empirically-determined weight factors used by score_split() below.532* Larger values means that the position is a less favorable place to split.533*534* Note that scores are only ever compared against each other, so multiplying535* all of these weight/penalty values by the same factor wouldn't change the536* heuristic's behavior. Still, we need to set that arbitrary scale *somehow*.537* In practice, these numbers are chosen to be large enough that they can be538* adjusted relative to each other with sufficient precision despite using539* integer math.540*/541/* Penalty if there are no non-blank lines before the split */543#define START_OF_FILE_PENALTY 1544/* Penalty if there are no non-blank lines after the split */546#define END_OF_FILE_PENALTY 21547/* Multiplier for the number of blank lines around the split */549#define TOTAL_BLANK_WEIGHT (-30)550/* Multiplier for the number of blank lines after the split */552#define POST_BLANK_WEIGHT 6553/*555* Penalties applied if the line is indented more than its predecessor556*/557#define RELATIVE_INDENT_PENALTY (-4)558#define RELATIVE_INDENT_WITH_BLANK_PENALTY 10559/*561* Penalties applied if the line is indented less than both its predecessor and562* its successor563*/564#define RELATIVE_OUTDENT_PENALTY 24565#define RELATIVE_OUTDENT_WITH_BLANK_PENALTY 17566/*568* Penalties applied if the line is indented less than its predecessor but not569* less than its successor570*/571#define RELATIVE_DEDENT_PENALTY 23572#define RELATIVE_DEDENT_WITH_BLANK_PENALTY 17573/*575* We only consider whether the sum of the effective indents for splits are576* less than (-1), equal to (0), or greater than (+1) each other. The resulting577* value is multiplied by the following weight and combined with the penalty to578* determine the better of two scores.579*/580#define INDENT_WEIGHT 60581/*583* How far do we slide a hunk at most?584*/585#define INDENT_HEURISTIC_MAX_SLIDING 100586/*588* Compute a badness score for the hypothetical split whose measurements are589* stored in m. The weight factors were determined empirically using the tools590* and corpus described in591*592* https://github.com/mhagger/diff-slider-tools593*594* Also see that project if you want to improve the weights based on, for595* example, a larger or more diverse corpus.596*/597static void score_add_split(const struct split_measurement *m, struct split_score *s)598{599/*600* A place to accumulate penalty factors (positive makes this index more601* favored):602*/603int post_blank, total_blank, indent, any_blanks;604* Set post_blank to the number of blank lines following the split,613* including the line immediately after the split:614*/615post_blank = (m->indent == -1) ? 1 + m->post_blank : 0;616total_blank = m->pre_blank + post_blank;617* The line is indented more than its predecessor.639*/640s->penalty += any_blanks ?641RELATIVE_INDENT_WITH_BLANK_PENALTY :642RELATIVE_INDENT_PENALTY;643} else if (indent == m->pre_indent) {644/*645* The line has the same indentation level as its predecessor.646* No additional adjustments needed.647*/648} else {649/*650* The line is indented less than its predecessor. It could be651* the block terminator of the previous block, but it could652* also be the start of a new block (e.g., an "else" block, or653* maybe the previous block didn't have a block terminator).654* Try to distinguish those cases based on what comes next:655*/656if (m->post_indent != -1 && m->post_indent > indent) {657/*658* The following line is indented more. So it is likely659* that this line is the start of a block.660*/661s->penalty += any_blanks ?662RELATIVE_OUTDENT_WITH_BLANK_PENALTY :663RELATIVE_OUTDENT_PENALTY;664} else {665/*666* That was probably the end of a block.667*/668s->penalty += any_blanks ?669RELATIVE_DEDENT_WITH_BLANK_PENALTY :670RELATIVE_DEDENT_PENALTY;671}672}673}674{677/* -1 if s1.effective_indent < s2->effective_indent, etc. */678int cmp_indents = ((s1->effective_indent > s2->effective_indent) -679(s1->effective_indent < s2->effective_indent));680}683/*685* Represent a group of changed lines in an xdfile_t (i.e., a contiguous group686* of lines that was inserted or deleted from the corresponding version of the687* file). We consider there to be such a group at the beginning of the file, at688* the end of the file, and between any two unchanged lines, though most such689* groups will usually be empty.690*691* If the first line in a group is equal to the line following the group, then692* the group can be slid down. Similarly, if the last line in a group is equal693* to the line preceding the group, then the group can be slid up. See694* group_slide_down() and group_slide_up().695*696* Note that loops that are testing for changed lines in xdf->rchg do not need697* index bounding since the array is prepared with a zero at position -1 and N.698*/699struct xdlgroup {700/*701* The index of the first changed line in the group, or the index of702* the unchanged line above which the (empty) group is located.703*/704long start;705* The index of the first unchanged line after the group. For an empty708* group, end is equal to start.709*/710long end;711};712/*714* Initialize g to point at the first group in xdf.715*/716static void group_init(xdfile_t *xdf, struct xdlgroup *g)717{718g->start = g->end = 0;719while (xdf->rchg[g->end])720g->end++;721}722/*724* Move g to describe the next (possibly empty) group in xdf and return 0. If g725* is already at the end of the file, do nothing and return -1.726*/727static inline int group_next(xdfile_t *xdf, struct xdlgroup *g)728{729if (g->end == xdf->nrec)730return -1;731}738/*740* Move g to describe the previous (possibly empty) group in xdf and return 0.741* If g is already at the beginning of the file, do nothing and return -1.742*/743static inline int group_previous(xdfile_t *xdf, struct xdlgroup *g)744{745if (g->start == 0)746return -1;747}754/*756* If g can be slid toward the end of the file, do so, and if it bumps into a757* following group, expand this group to include it. Return 0 on success or -1758* if g cannot be slid down.759*/760static int group_slide_down(xdfile_t *xdf, struct xdlgroup *g)761{762if (g->end < xdf->nrec &&763recs_match(xdf->recs[g->start], xdf->recs[g->end])) {764xdf->rchg[g->start++] = 0;765xdf->rchg[g->end++] = 1;766}775/*777* If g can be slid toward the beginning of the file, do so, and if it bumps778* into a previous group, expand this group to include it. Return 0 on success779* or -1 if g cannot be slid up.780*/781static int group_slide_up(xdfile_t *xdf, struct xdlgroup *g)782{783if (g->start > 0 &&784recs_match(xdf->recs[g->start - 1], xdf->recs[g->end - 1])) {785xdf->rchg[--g->start] = 1;786xdf->rchg[--g->end] = 0;787}796/*798* Move back and forward change groups for a consistent and pretty diff output.799* This also helps in finding joinable change groups and reducing the diff800* size.801*/802int xdl_change_compact(xdfile_t *xdf, xdfile_t *xdfo, long flags) {803struct xdlgroup g, go;804long earliest_end, end_matching_other;805long groupsize;806* If the group is empty in the to-be-compacted file, skip it:813*/814if (g.end == g.start)815goto next;816* Now shift the change up and then down as far as possible in819* each direction. If it bumps into any other changes, merge820* them.821*/822do {823groupsize = g.end - g.start;824* Keep track of the last "end" index that causes this827* group to align with a group of changed lines in the828* other file. -1 indicates that we haven't found such829* a match yet:830*/831end_matching_other = -1;832* This is this highest that this group can be shifted.840* Record its end index:841*/842earliest_end = g.end;843* If the group can be shifted, then we can possibly use this861* freedom to produce a more intuitive diff.862*863* The group is currently shifted as far down as possible, so864* the heuristics below only have to handle upwards shifts.865*/866* Move the possibly merged group of changes back to872* line up with the last group of changes from the873* other file that it can align with.874*/875while (go.end == go.start) {876if (group_slide_up(xdf, &g))877BUG("match disappeared");878if (group_previous(xdfo, &go))879BUG("group sync broken sliding to match");880}881} else if (flags & XDF_INDENT_HEURISTIC) {882/*883* Indent heuristic: a group of pure add/delete lines884* implies two splits, one between the end of the885* "before" context and the start of the group, and886* another between the end of the group and the887* beginning of the "after" context. Some splits are888* aesthetically better and some are worse. We compute889* a badness "score" for each split, and add the scores890* for the two splits to define a "score" for each891* position that the group can be shifted to. Then we892* pick the shift with the lowest score.893*/894long shift, best_shift = -1;895struct split_score best_score;896}939* Trivial. Collects "groups" of changes and creates an edit script.948*/949for (i1 = xe->xdf1.nrec, i2 = xe->xdf2.nrec; i1 >= 0 || i2 >= 0; i1--, i2--)950if (rchg1[i1 - 1] || rchg2[i2 - 1]) {951for (l1 = i1; rchg1[i1 - 1]; i1--);952for (l2 = i2; rchg2[i2 - 1]; i2--);953}965}975{979xdchange_t *xch, *xche;980}992{995xdchange_t *xch;996}1013}1025{1029xdchange_t *xch;1030* Do not override --ignore-blank-lines.1038*/1039if (xch->ignore)1040continue;1041}1053}1090