/src/git/xdiff/xemit.c

Source
/*
 *  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 <davidel@xmailserver.org>
 *
 */

#include "xinclude.h"


static int xdl_emit_record(xdfile_t *xdf, long ri, char const *pre, xdemitcb_t *ecb)
{
  xrecord_t *rec = &xdf->recs[ri];

  if (xdl_emit_diffrec((char const *)rec->ptr, (long)rec->size, pre, strlen(pre), ecb) < 0)
    return -1;

  return 0;
}

static long saturating_add(long a, long b)
{
  return signed_add_overflows(a, b) ? LONG_MAX : a + b;
}

/*
 * Starting at the passed change atom, find the latest change atom to be included
 * inside the differential hunk according to the specified configuration.
 * Also advance xscr if the first changes must be discarded.
 */
xdchange_t *xdl_get_hunk(xdchange_t **xscr, xdemitconf_t const *xecfg)
{
  xdchange_t *xch, *xchp, *lxch;
  long max_common = saturating_add(saturating_add(xecfg->ctxlen,
              xecfg->ctxlen),
           xecfg->interhunkctxlen);
  long max_ignorable = xecfg->ctxlen;
  long ignored = 0; /* number of ignored blank lines */

  /* remove ignorable changes that are too far before other changes */
  for (xchp = *xscr; xchp && xchp->ignore; xchp = xchp->next) {
    xch = xchp->next;

    if (xch == NULL ||
        xch->i1 - (xchp->i1 + xchp->chg1) >= max_ignorable)
      *xscr = xch;
  }

  if (!*xscr)
    return NULL;

  lxch = *xscr;

  for (xchp = *xscr, xch = xchp->next; xch; xchp = xch, xch = xch->next) {
    long distance = xch->i1 - (xchp->i1 + xchp->chg1);
    if (distance > max_common)
      break;

    if (distance < max_ignorable && (!xch->ignore || lxch == xchp)) {
      lxch = xch;
      ignored = 0;
    } else if (distance < max_ignorable && xch->ignore) {
      ignored += xch->chg2;
    } else if (lxch != xchp &&
         xch->i1 + ignored - (lxch->i1 + lxch->chg1) > max_common) {
      break;
    } else if (!xch->ignore) {
      lxch = xch;
      ignored = 0;
    } else {
      ignored += xch->chg2;
    }
  }

  return lxch;
}


static long def_ff(const char *rec, long len, char *buf, long sz)
{
  if (len > 0 &&
      (isalpha((unsigned char)*rec) || /* identifier? */
       *rec == '_' || /* also identifier? */
       *rec == '$')) { /* identifiers from VMS and other esoterico */
    if (len > sz)
      len = sz;
    while (0 < len && isspace((unsigned char)rec[len - 1]))
      len--;
    memcpy(buf, rec, len);
    return len;
  }
  return -1;
}

static long match_func_rec(xdfile_t *xdf, xdemitconf_t const *xecfg, long ri,
         char *buf, long sz)
{
  xrecord_t *rec = &xdf->recs[ri];

  if (!xecfg->find_func)
    return def_ff((const char *)rec->ptr, (long)rec->size, buf, sz);
  return xecfg->find_func((const char *)rec->ptr, (long)rec->size, buf, sz, xecfg->find_func_priv);
}

static int is_func_rec(xdfile_t *xdf, xdemitconf_t const *xecfg, long ri)
{
  char dummy[1];
  return match_func_rec(xdf, xecfg, ri, dummy, sizeof(dummy)) >= 0;
}

struct func_line {
  long len;
  char buf[80];
};

static long get_func_line(xdfenv_t *xe, xdemitconf_t const *xecfg,
        struct func_line *func_line, long start, long limit)
{
  long l, size, step = (start > limit) ? -1 : 1;
  char *buf, dummy[1];

  buf = func_line ? func_line->buf : dummy;
  size = func_line ? sizeof(func_line->buf) : sizeof(dummy);

  for (l = start; l != limit && 0 <= l && l < (long)xe->xdf1.nrec; l += step) {
    long len = match_func_rec(&xe->xdf1, xecfg, l, buf, size);
    if (len >= 0) {
      if (func_line)
        func_line->len = len;
      return l;
    }
  }
  return -1;
}

static int is_empty_rec(xdfile_t *xdf, long ri)
{
  xrecord_t *rec = &xdf->recs[ri];
  size_t i = 0;

  for (; i < rec->size && XDL_ISSPACE(rec->ptr[i]); i++);

  return i == rec->size;
}

int xdl_emit_diff(xdfenv_t *xe, xdchange_t *xscr, xdemitcb_t *ecb,
      xdemitconf_t const *xecfg) {
  long s1, s2, e1, e2, lctx;
  xdchange_t *xch, *xche;
  long funclineprev = -1;
  struct func_line func_line = { 0 };

  for (xch = xscr; xch; xch = xche->next) {
    xdchange_t *xchp = xch;
    xche = xdl_get_hunk(&xch, xecfg);
    if (!xch)
      break;

pre_context_calculation:
    s1 = XDL_MAX(xch->i1 - xecfg->ctxlen, 0);
    s2 = XDL_MAX(xch->i2 - xecfg->ctxlen, 0);

    if (xecfg->flags & XDL_EMIT_FUNCCONTEXT) {
      long fs1, i1 = xch->i1;

      /* Appended chunk? */
      if (i1 >= (long)xe->xdf1.nrec) {
        long i2 = xch->i2;

        /*
         * We don't need additional context if
         * a whole function was added.
         */
        while (i2 < (long)xe->xdf2.nrec) {
          if (is_func_rec(&xe->xdf2, xecfg, i2))
            goto post_context_calculation;
          i2++;
        }

        /*
         * Otherwise get more context from the
         * pre-image.
         */
        i1 = (long)xe->xdf1.nrec - 1;
      }

      fs1 = get_func_line(xe, xecfg, NULL, i1, -1);
      while (fs1 > 0 && !is_empty_rec(&xe->xdf1, fs1 - 1) &&
             !is_func_rec(&xe->xdf1, xecfg, fs1 - 1))
        fs1--;
      if (fs1 < 0)
        fs1 = 0;
      if (fs1 < s1) {
        s2 = XDL_MAX(s2 - (s1 - fs1), 0);
        s1 = fs1;

        /*
         * Did we extend context upwards into an
         * ignored change?
         */
        while (xchp != xch &&
               xchp->i1 + xchp->chg1 <= s1 &&
               xchp->i2 + xchp->chg2 <= s2)
          xchp = xchp->next;

        /* If so, show it after all. */
        if (xchp != xch) {
          xch = xchp;
          goto pre_context_calculation;
        }
      }
    }

 post_context_calculation:
    lctx = xecfg->ctxlen;
    lctx = XDL_MIN(lctx, (long)xe->xdf1.nrec - (xche->i1 + xche->chg1));
    lctx = XDL_MIN(lctx, (long)xe->xdf2.nrec - (xche->i2 + xche->chg2));

    e1 = xche->i1 + xche->chg1 + lctx;
    e2 = xche->i2 + xche->chg2 + lctx;

    if (xecfg->flags & XDL_EMIT_FUNCCONTEXT) {
      long fe1 = get_func_line(xe, xecfg, NULL,
             xche->i1 + xche->chg1,
             (long)xe->xdf1.nrec);
      while (fe1 > 0 && is_empty_rec(&xe->xdf1, fe1 - 1))
        fe1--;
      if (fe1 < 0)
        fe1 = (long)xe->xdf1.nrec;
      if (fe1 > e1) {
        e2 = XDL_MIN(e2 + (fe1 - e1), (long)xe->xdf2.nrec);
        e1 = fe1;
      }

      /*
       * Overlap with next change?  Then include it
       * in the current hunk and start over to find
       * its new end.
       */
      if (xche->next) {
        long l = XDL_MIN(xche->next->i1,
             (long)xe->xdf1.nrec - 1);
        if (l - xecfg->ctxlen <= e1 ||
            get_func_line(xe, xecfg, NULL, l, e1) < 0) {
          xche = xche->next;
          goto post_context_calculation;
        }
      }
    }

    /*
     * Emit current hunk header.
     */

    if (xecfg->flags & XDL_EMIT_FUNCNAMES) {
      get_func_line(xe, xecfg, &func_line,
              s1 - 1, funclineprev);
      funclineprev = s1 - 1;
    }
    if (!(xecfg->flags & XDL_EMIT_NO_HUNK_HDR) &&
        xdl_emit_hunk_hdr(s1 + 1, e1 - s1, s2 + 1, e2 - s2,
              func_line.buf, func_line.len, ecb) < 0)
      return -1;

    /*
     * Emit pre-context.
     */
    for (; s2 < xch->i2; s2++)
      if (xdl_emit_record(&xe->xdf2, s2, " ", ecb) < 0)
        return -1;

    for (s1 = xch->i1, s2 = xch->i2;; xch = xch->next) {
      /*
       * Merge previous with current change atom.
       */
      for (; s1 < xch->i1 && s2 < xch->i2; s1++, s2++)
        if (xdl_emit_record(&xe->xdf2, s2, " ", ecb) < 0)
          return -1;

      /*
       * Removes lines from the first file.
       */
      for (s1 = xch->i1; s1 < xch->i1 + xch->chg1; s1++)
        if (xdl_emit_record(&xe->xdf1, s1, "-", ecb) < 0)
          return -1;

      /*
       * Adds lines from the second file.
       */
      for (s2 = xch->i2; s2 < xch->i2 + xch->chg2; s2++)
        if (xdl_emit_record(&xe->xdf2, s2, "+", ecb) < 0)
          return -1;

      if (xch == xche)
        break;
      s1 = xch->i1 + xch->chg1;
      s2 = xch->i2 + xch->chg2;
    }

    /*
     * Emit post-context.
     */
    for (s2 = xche->i2 + xche->chg2; s2 < e2; s2++)
      if (xdl_emit_record(&xe->xdf2, s2, " ", ecb) < 0)
        return -1;
  }

  return 0;
}

Coverage Report

Created: 2025-12-31 07:01

Line	Count	Source
1		/*
2		* LibXDiff by Davide Libenzi ( File Differential Library )
3		* Copyright (C) 2003 Davide Libenzi
4		*
5		* This library is free software; you can redistribute it and/or
6		* modify it under the terms of the GNU Lesser General Public
7		* License as published by the Free Software Foundation; either
8		* 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 of
12		* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
13		* Lesser General Public License for more details.
14		*
15		* You should have received a copy of the GNU Lesser General Public
16		* License along with this library; if not, see
17		* <http://www.gnu.org/licenses/>.
18		*
19		* Davide Libenzi <davidel@xmailserver.org>
20		*
21		*/
22
23		#include "xinclude.h"
24
25
26		static int xdl_emit_record(xdfile_t xdf, long ri, char const pre, xdemitcb_t *ecb)
27	0	{
28	0	xrecord_t *rec = &xdf->recs[ri];
29
30	0	if (xdl_emit_diffrec((char const *)rec->ptr, (long)rec->size, pre, strlen(pre), ecb) < 0)
31	0	return -1;
32
33	0	return 0;
34	0	}
35
36		static long saturating_add(long a, long b)
37	0	{
38	0	return signed_add_overflows(a, b) ? LONG_MAX : a + b;
39	0	}
40
41		/*
42		* Starting at the passed change atom, find the latest change atom to be included
43		* inside the differential hunk according to the specified configuration.
44		* Also advance xscr if the first changes must be discarded.
45		*/
46		xdchange_t xdl_get_hunk(xdchange_t xscr, xdemitconf_t const xecfg)
47	0	{
48	0	xdchange_t xch, xchp, *lxch;
49	0	long max_common = saturating_add(saturating_add(xecfg->ctxlen,
50	0	xecfg->ctxlen),
51	0	xecfg->interhunkctxlen);
52	0	long max_ignorable = xecfg->ctxlen;
53	0	long ignored = 0; /* number of ignored blank lines */
54
55		/* remove ignorable changes that are too far before other changes */
56	0	for (xchp = *xscr; xchp && xchp->ignore; xchp = xchp->next) {
57	0	xch = xchp->next;
58
59	0	if (xch == NULL \|\|
60	0	xch->i1 - (xchp->i1 + xchp->chg1) >= max_ignorable)
61	0	*xscr = xch;
62	0	}
63
64	0	if (!*xscr)
65	0	return NULL;
66
67	0	lxch = *xscr;
68
69	0	for (xchp = *xscr, xch = xchp->next; xch; xchp = xch, xch = xch->next) {
70	0	long distance = xch->i1 - (xchp->i1 + xchp->chg1);
71	0	if (distance > max_common)
72	0	break;
73
74	0	if (distance < max_ignorable && (!xch->ignore \|\| lxch == xchp)) {
75	0	lxch = xch;
76	0	ignored = 0;
77	0	} else if (distance < max_ignorable && xch->ignore) {
78	0	ignored += xch->chg2;
79	0	} else if (lxch != xchp &&
80	0	xch->i1 + ignored - (lxch->i1 + lxch->chg1) > max_common) {
81	0	break;
82	0	} else if (!xch->ignore) {
83	0	lxch = xch;
84	0	ignored = 0;
85	0	} else {
86	0	ignored += xch->chg2;
87	0	}
88	0	}
89
90	0	return lxch;
91	0	}
92
93
94		static long def_ff(const char rec, long len, char buf, long sz)
95	0	{
96	0	if (len > 0 &&
97	0	(isalpha((unsigned char)rec) \|\| / identifier? */
98	0	rec == '_' \|\| / also identifier? */
99	0	rec == '$')) { / identifiers from VMS and other esoterico */
100	0	if (len > sz)
101	0	len = sz;
102	0	while (0 < len && isspace((unsigned char)rec[len - 1]))
103	0	len--;
104	0	memcpy(buf, rec, len);
105	0	return len;
106	0	}
107	0	return -1;
108	0	}
109
110		static long match_func_rec(xdfile_t xdf, xdemitconf_t const xecfg, long ri,
111		char *buf, long sz)
112	0	{
113	0	xrecord_t *rec = &xdf->recs[ri];
114
115	0	if (!xecfg->find_func)
116	0	return def_ff((const char *)rec->ptr, (long)rec->size, buf, sz);
117	0	return xecfg->find_func((const char *)rec->ptr, (long)rec->size, buf, sz, xecfg->find_func_priv);
118	0	}
119
120		static int is_func_rec(xdfile_t xdf, xdemitconf_t const xecfg, long ri)
121	0	{
122	0	char dummy[1];
123	0	return match_func_rec(xdf, xecfg, ri, dummy, sizeof(dummy)) >= 0;
124	0	}
125
126		struct func_line {
127		long len;
128		char buf[80];
129		};
130
131		static long get_func_line(xdfenv_t xe, xdemitconf_t const xecfg,
132		struct func_line *func_line, long start, long limit)
133	0	{
134	0	long l, size, step = (start > limit) ? -1 : 1;
135	0	char *buf, dummy[1];
136
137	0	buf = func_line ? func_line->buf : dummy;
138	0	size = func_line ? sizeof(func_line->buf) : sizeof(dummy);
139
140	0	for (l = start; l != limit && 0 <= l && l < (long)xe->xdf1.nrec; l += step) {
141	0	long len = match_func_rec(&xe->xdf1, xecfg, l, buf, size);
142	0	if (len >= 0) {
143	0	if (func_line)
144	0	func_line->len = len;
145	0	return l;
146	0	}
147	0	}
148	0	return -1;
149	0	}
150
151		static int is_empty_rec(xdfile_t *xdf, long ri)
152	0	{
153	0	xrecord_t *rec = &xdf->recs[ri];
154	0	size_t i = 0;
155
156	0	for (; i < rec->size && XDL_ISSPACE(rec->ptr[i]); i++);
157
158	0	return i == rec->size;
159	0	}
160
161		int xdl_emit_diff(xdfenv_t xe, xdchange_t xscr, xdemitcb_t *ecb,
162	0	xdemitconf_t const *xecfg) {
163	0	long s1, s2, e1, e2, lctx;
164	0	xdchange_t xch, xche;
165	0	long funclineprev = -1;
166	0	struct func_line func_line = { 0 };
167
168	0	for (xch = xscr; xch; xch = xche->next) {
169	0	xdchange_t *xchp = xch;
170	0	xche = xdl_get_hunk(&xch, xecfg);
171	0	if (!xch)
172	0	break;
173
174	0	pre_context_calculation:
175	0	s1 = XDL_MAX(xch->i1 - xecfg->ctxlen, 0);
176	0	s2 = XDL_MAX(xch->i2 - xecfg->ctxlen, 0);
177
178	0	if (xecfg->flags & XDL_EMIT_FUNCCONTEXT) {
179	0	long fs1, i1 = xch->i1;
180
181		/* Appended chunk? */
182	0	if (i1 >= (long)xe->xdf1.nrec) {
183	0	long i2 = xch->i2;
184
185		/*
186		* We don't need additional context if
187		* a whole function was added.
188		*/
189	0	while (i2 < (long)xe->xdf2.nrec) {
190	0	if (is_func_rec(&xe->xdf2, xecfg, i2))
191	0	goto post_context_calculation;
192	0	i2++;
193	0	}
194
195		/*
196		* Otherwise get more context from the
197		* pre-image.
198		*/
199	0	i1 = (long)xe->xdf1.nrec - 1;
200	0	}
201
202	0	fs1 = get_func_line(xe, xecfg, NULL, i1, -1);
203	0	while (fs1 > 0 && !is_empty_rec(&xe->xdf1, fs1 - 1) &&
204	0	!is_func_rec(&xe->xdf1, xecfg, fs1 - 1))
205	0	fs1--;
206	0	if (fs1 < 0)
207	0	fs1 = 0;
208	0	if (fs1 < s1) {
209	0	s2 = XDL_MAX(s2 - (s1 - fs1), 0);
210	0	s1 = fs1;
211
212		/*
213		* Did we extend context upwards into an
214		* ignored change?
215		*/
216	0	while (xchp != xch &&
217	0	xchp->i1 + xchp->chg1 <= s1 &&
218	0	xchp->i2 + xchp->chg2 <= s2)
219	0	xchp = xchp->next;
220
221		/* If so, show it after all. */
222	0	if (xchp != xch) {
223	0	xch = xchp;
224	0	goto pre_context_calculation;
225	0	}
226	0	}
227	0	}
228
229	0	post_context_calculation:
230	0	lctx = xecfg->ctxlen;
231	0	lctx = XDL_MIN(lctx, (long)xe->xdf1.nrec - (xche->i1 + xche->chg1));
232	0	lctx = XDL_MIN(lctx, (long)xe->xdf2.nrec - (xche->i2 + xche->chg2));
233
234	0	e1 = xche->i1 + xche->chg1 + lctx;
235	0	e2 = xche->i2 + xche->chg2 + lctx;
236
237	0	if (xecfg->flags & XDL_EMIT_FUNCCONTEXT) {
238	0	long fe1 = get_func_line(xe, xecfg, NULL,
239	0	xche->i1 + xche->chg1,
240	0	(long)xe->xdf1.nrec);
241	0	while (fe1 > 0 && is_empty_rec(&xe->xdf1, fe1 - 1))
242	0	fe1--;
243	0	if (fe1 < 0)
244	0	fe1 = (long)xe->xdf1.nrec;
245	0	if (fe1 > e1) {
246	0	e2 = XDL_MIN(e2 + (fe1 - e1), (long)xe->xdf2.nrec);
247	0	e1 = fe1;
248	0	}
249
250		/*
251		* Overlap with next change? Then include it
252		* in the current hunk and start over to find
253		* its new end.
254		*/
255	0	if (xche->next) {
256	0	long l = XDL_MIN(xche->next->i1,
257	0	(long)xe->xdf1.nrec - 1);
258	0	if (l - xecfg->ctxlen <= e1 \|\|
259	0	get_func_line(xe, xecfg, NULL, l, e1) < 0) {
260	0	xche = xche->next;
261	0	goto post_context_calculation;
262	0	}
263	0	}
264	0	}
265
266		/*
267		* Emit current hunk header.
268		*/
269
270	0	if (xecfg->flags & XDL_EMIT_FUNCNAMES) {
271	0	get_func_line(xe, xecfg, &func_line,
272	0	s1 - 1, funclineprev);
273	0	funclineprev = s1 - 1;
274	0	}
275	0	if (!(xecfg->flags & XDL_EMIT_NO_HUNK_HDR) &&
276	0	xdl_emit_hunk_hdr(s1 + 1, e1 - s1, s2 + 1, e2 - s2,
277	0	func_line.buf, func_line.len, ecb) < 0)
278	0	return -1;
279
280		/*
281		* Emit pre-context.
282		*/
283	0	for (; s2 < xch->i2; s2++)
284	0	if (xdl_emit_record(&xe->xdf2, s2, " ", ecb) < 0)
285	0	return -1;
286
287	0	for (s1 = xch->i1, s2 = xch->i2;; xch = xch->next) {
288		/*
289		* Merge previous with current change atom.
290		*/
291	0	for (; s1 < xch->i1 && s2 < xch->i2; s1++, s2++)
292	0	if (xdl_emit_record(&xe->xdf2, s2, " ", ecb) < 0)
293	0	return -1;
294
295		/*
296		* Removes lines from the first file.
297		*/
298	0	for (s1 = xch->i1; s1 < xch->i1 + xch->chg1; s1++)
299	0	if (xdl_emit_record(&xe->xdf1, s1, "-", ecb) < 0)
300	0	return -1;
301
302		/*
303		* Adds lines from the second file.
304		*/
305	0	for (s2 = xch->i2; s2 < xch->i2 + xch->chg2; s2++)
306	0	if (xdl_emit_record(&xe->xdf2, s2, "+", ecb) < 0)
307	0	return -1;
308
309	0	if (xch == xche)
310	0	break;
311	0	s1 = xch->i1 + xch->chg1;
312	0	s2 = xch->i2 + xch->chg2;
313	0	}
314
315		/*
316		* Emit post-context.
317		*/
318	0	for (s2 = xche->i2 + xche->chg2; s2 < e2; s2++)
319	0	if (xdl_emit_record(&xe->xdf2, s2, " ", ecb) < 0)
320	0	return -1;
321	0	}
322
323	0	return 0;
324	0	}