/* * LibXDiff by Davide Libenzi ( File Differential Library ) * Copyright (C) 2003 Davide Libenzi * * This library is free software; you can redistribute it and/or * modify it under the terms of the GNU Lesser General Public * License as published by the Free Software Foundation; either * version 2.1 of the License, or (at your option) any later version. * * This library is distributed in the hope that it will be useful, * but WITHOUT ANY WARRANTY; without even the implied warranty of * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU * Lesser General Public License for more details. * * You should have received a copy of the GNU Lesser General Public * License along with this library; if not, see * <http://www.gnu.org/licenses/>. * * Davide Libenzi <[email protected]> * */ #include "xinclude.h" #define XDL_MAX_COST_MIN … #define XDL_HEUR_MIN_COST … #define XDL_LINE_MAX … #define XDL_SNAKE_CNT … #define XDL_K_HEUR … xdpsplit_t; /* * See "An O(ND) Difference Algorithm and its Variations", by Eugene Myers. * Basically considers a "box" (off1, off2, lim1, lim2) and scan from both * the forward diagonal starting from (off1, off2) and the backward diagonal * starting from (lim1, lim2). If the K values on the same diagonal crosses * returns the furthest point of reach. We might encounter expensive edge cases * using this algorithm, so a little bit of heuristic is needed to cut the * search and to return a suboptimal point. */ static long xdl_split(unsigned long const *ha1, long off1, long lim1, unsigned long const *ha2, long off2, long lim2, long *kvdf, long *kvdb, int need_min, xdpsplit_t *spl, xdalgoenv_t *xenv) { … } /* * Rule: "Divide et Impera" (divide & conquer). Recursively split the box in * sub-boxes by calling the box splitting function. Note that the real job * (marking changed lines) is done in the two boundary reaching checks. */ int xdl_recs_cmp(diffdata_t *dd1, long off1, long lim1, diffdata_t *dd2, long off2, long lim2, long *kvdf, long *kvdb, int need_min, xdalgoenv_t *xenv) { … } int xdl_do_diff(mmfile_t *mf1, mmfile_t *mf2, xpparam_t const *xpp, xdfenv_t *xe) { … } static xdchange_t *xdl_add_change(xdchange_t *xscr, long i1, long i2, long chg1, long chg2) { … } static int recs_match(xrecord_t *rec1, xrecord_t *rec2) { … } /* * If a line is indented more than this, get_indent() just returns this value. * This avoids having to do absurd amounts of work for data that are not * human-readable text, and also ensures that the output of get_indent fits * within an int. */ #define MAX_INDENT … /* * Return the amount of indentation of the specified line, treating TAB as 8 * columns. Return -1 if line is empty or contains only whitespace. Clamp the * output value at MAX_INDENT. */ static int get_indent(xrecord_t *rec) { … } /* * If more than this number of consecutive blank rows are found, just return * this value. This avoids requiring O(N^2) work for pathological cases, and * also ensures that the output of score_split fits in an int. */ #define MAX_BLANKS … /* Characteristics measured about a hypothetical split position. */ struct split_measurement { … }; struct split_score { … }; /* * Fill m with information about a hypothetical split of xdf above line split. */ static void measure_split(const xdfile_t *xdf, long split, struct split_measurement *m) { … } /* * The empirically-determined weight factors used by score_split() below. * Larger values means that the position is a less favorable place to split. * * Note that scores are only ever compared against each other, so multiplying * all of these weight/penalty values by the same factor wouldn't change the * heuristic's behavior. Still, we need to set that arbitrary scale *somehow*. * In practice, these numbers are chosen to be large enough that they can be * adjusted relative to each other with sufficient precision despite using * integer math. */ /* Penalty if there are no non-blank lines before the split */ #define START_OF_FILE_PENALTY … /* Penalty if there are no non-blank lines after the split */ #define END_OF_FILE_PENALTY … /* Multiplier for the number of blank lines around the split */ #define TOTAL_BLANK_WEIGHT … /* Multiplier for the number of blank lines after the split */ #define POST_BLANK_WEIGHT … /* * Penalties applied if the line is indented more than its predecessor */ #define RELATIVE_INDENT_PENALTY … #define RELATIVE_INDENT_WITH_BLANK_PENALTY … /* * Penalties applied if the line is indented less than both its predecessor and * its successor */ #define RELATIVE_OUTDENT_PENALTY … #define RELATIVE_OUTDENT_WITH_BLANK_PENALTY … /* * Penalties applied if the line is indented less than its predecessor but not * less than its successor */ #define RELATIVE_DEDENT_PENALTY … #define RELATIVE_DEDENT_WITH_BLANK_PENALTY … /* * We only consider whether the sum of the effective indents for splits are * less than (-1), equal to (0), or greater than (+1) each other. The resulting * value is multiplied by the following weight and combined with the penalty to * determine the better of two scores. */ #define INDENT_WEIGHT … /* * How far do we slide a hunk at most? */ #define INDENT_HEURISTIC_MAX_SLIDING … /* * Compute a badness score for the hypothetical split whose measurements are * stored in m. The weight factors were determined empirically using the tools * and corpus described in * * https://github.com/mhagger/diff-slider-tools * * Also see that project if you want to improve the weights based on, for * example, a larger or more diverse corpus. */ static void score_add_split(const struct split_measurement *m, struct split_score *s) { … } static int score_cmp(struct split_score *s1, struct split_score *s2) { … } /* * Represent a group of changed lines in an xdfile_t (i.e., a contiguous group * of lines that was inserted or deleted from the corresponding version of the * file). We consider there to be such a group at the beginning of the file, at * the end of the file, and between any two unchanged lines, though most such * groups will usually be empty. * * If the first line in a group is equal to the line following the group, then * the group can be slid down. Similarly, if the last line in a group is equal * to the line preceding the group, then the group can be slid up. See * group_slide_down() and group_slide_up(). * * Note that loops that are testing for changed lines in xdf->rchg do not need * index bounding since the array is prepared with a zero at position -1 and N. */ struct xdlgroup { … }; /* * Initialize g to point at the first group in xdf. */ static void group_init(xdfile_t *xdf, struct xdlgroup *g) { … } /* * Move g to describe the next (possibly empty) group in xdf and return 0. If g * is already at the end of the file, do nothing and return -1. */ static inline int group_next(xdfile_t *xdf, struct xdlgroup *g) { … } /* * Move g to describe the previous (possibly empty) group in xdf and return 0. * If g is already at the beginning of the file, do nothing and return -1. */ static inline int group_previous(xdfile_t *xdf, struct xdlgroup *g) { … } /* * If g can be slid toward the end of the file, do so, and if it bumps into a * following group, expand this group to include it. Return 0 on success or -1 * if g cannot be slid down. */ static int group_slide_down(xdfile_t *xdf, struct xdlgroup *g) { … } /* * If g can be slid toward the beginning of the file, do so, and if it bumps * into a previous group, expand this group to include it. Return 0 on success * or -1 if g cannot be slid up. */ static int group_slide_up(xdfile_t *xdf, struct xdlgroup *g) { … } /* * Move back and forward change groups for a consistent and pretty diff output. * This also helps in finding joinable change groups and reducing the diff * size. */ int xdl_change_compact(xdfile_t *xdf, xdfile_t *xdfo, long flags) { … } int xdl_build_script(xdfenv_t *xe, xdchange_t **xscr) { … } void xdl_free_script(xdchange_t *xscr) { … } static int xdl_call_hunk_func(xdfenv_t *xe UNUSED, xdchange_t *xscr, xdemitcb_t *ecb, xdemitconf_t const *xecfg) { … } static void xdl_mark_ignorable_lines(xdchange_t *xscr, xdfenv_t *xe, long flags) { … } static int record_matches_regex(xrecord_t *rec, xpparam_t const *xpp) { … } static void xdl_mark_ignorable_regex(xdchange_t *xscr, const xdfenv_t *xe, xpparam_t const *xpp) { … } int xdl_diff(mmfile_t *mf1, mmfile_t *mf2, xpparam_t const *xpp, xdemitconf_t const *xecfg, xdemitcb_t *ecb) { … }
Codebase Browser
git