/******************************************************************************

 * Copyright 1994-2015,2016 by Thomas E. Dickey                               *

 * All Rights Reserved.                                                       *

 *                                                                            *

 * Permission to use, copy, modify, and distribute this software and its      *

 * documentation for any purpose and without fee is hereby granted, provided  *

 * that the above copyright notice appear in all copies and that both that    *

 * copyright notice and this permission notice appear in supporting           *

 * documentation, and that the name of the above listed copyright holder(s)   *

 * not be used in advertising or publicity pertaining to distribution of the  *

 * software without specific, written prior permission.                       *

 *                                                                            *

 * THE ABOVE LISTED COPYRIGHT HOLDER(S) DISCLAIM ALL WARRANTIES WITH REGARD   *

 * TO THIS SOFTWARE, INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND  *

 * FITNESS, IN NO EVENT SHALL THE ABOVE LISTED COPYRIGHT HOLDER(S) BE LIABLE  *

 * FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES          *

 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN      *

 * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF OR *

 * IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.                *

 ******************************************************************************/

#ifndef	NO_IDENT

static const char *Id = "$Id: diffstat.c,v 1.61 2016/01/14 00:52:29 tom Exp $";

#endif

/*

 * Title:	diffstat.c

 * Author:	T.E.Dickey

 * Created:	02 Feb 1992

 * Modified:

 *		14 Jan 2016, extend -S option to count unmodified files.

 *			     add -T option to show values with histogram

 *		06 Jul 2015, handle double-quotes, e.g., from diffutils 3.3

 *			     when filenames have embedded spaces.

 *		05 Jun 2014, add -E option to filter colordiff output.

 *		28 Oct 2013, portability improvements for MinGW.

 *		15 Apr 2013, modify to accommodate output of "diff -q", which

 *			     tells only if the files are different.  Work

 *			     around the equivalent ambiguous message introduced

 *			     in diffutils 2.8.4 and finally removed for 3.0

 *		11 Feb 2013, add -K option.  Use strtol() to provide error

 *			     checking of optarg values.

 *		10 Feb 2013, document -b, -C, -s option in usage (patch by

 *			     Tim Waugh, Red Hat #852770).  Improve pathname

 *			     merging.

 *		02 Jun 2012, fix for svn diff with spaces in path (patch by

 *			     Stuart Prescott, Debian #675465).

 *		03 Jan 2012, Correct case for "xz" suffix in is_compressed()

 *			     (patch from Frederic Culot in FreeBSD ports).  Add

 *			     "-R" option.  Improve dequoting of filenames in

 *			     headers.

 *		10 Oct 2010, correct display of new files when -S/-D options

 *			     are used.  Remove the temporary directory on

 *			     error, introduced in 1.48+ (patch by Solar

 *			     Designer).

 *		19 Jul 2010, add missing "break" statement which left "-c"

 *			     option falling-through into "-C".

 *		16 Jul 2010, configure "xz" path explicitly, in case lzcat

 *			     does not support xz format.  Add "-s" (summary)

 *			     and "-C" (color) options.

 *		15 Jul 2010, fix strict gcc warnings, e.g., using const.

 *		10 Jan 2010, improve a case where filenames have embedded blanks

 *			     (patch by Reinier Post).

 *		07 Nov 2009, correct suffix-check for ".xz" files as

 *			     command-line parameters rather than as piped

 *			     input (report by Moritz Barsnick).

 *		06 Oct 2009, fixes to build/run with MSYS or MinGW.  use

 *			     $TMPDIR for path of temporary file used in

 *			     decompression.  correct else-condition for

 *			     detecting compression type (patch by Zach Hirsch).

 *		31 Aug 2009, improve lzma support, add support for xz (patch by

 *			     Eric Blake).  Add special case for no-newline

 *			     message from some diff's (Ubuntu #269895).

 *			     Improve configure check for getopt().

 *		11 Aug 2009, Add logic to check standard input, decompress if

 *			     possible.  Add -N option, to truncate long names.

 *			     Add pack/pcat as a compression type.

 *			     Add lzma/lzcat as a compression type.

 *			     Allow overriding program paths with environment.

 *		10 Aug 2009, modify to work with Perforce-style diffs (patch

 *			     by Ed Schouten).

 *		29 Mar 2009, modify to work with patch ".rej" files, which have

 *			     no filename header (use the name of the ".rej"

 *			     file if it is available).

 *		29 Sep 2008, fix typo in usage message.

 *		06 Aug 2008, add "-m", "-S" and "-D" options.

 *		05 Aug 2008, add "-q" option to suppress 0-files-changed

 *			     message (patch by Greg Norris).

 *		04 Sep 2007, add "-b" option to suppress binary-files (patch

 *			     by Greg Norris).

 *		26 Aug 2007, add "-d" option to show debugging traces, rather

 *			     than by defining DEBUG.  Add check after

 *			     unified-diff chunk to avoid adding non-diff text

 *			     (report by Adrian Bunk).  Quote pathname passed

 *			     in command to gzip/uncompress.  Add a check for

 *			     default-diff output without the "diff" command

 *			     supplied to provide filename, mark as "unknown".

 *		16 Jul 2006, fix to avoid modifying which is being used by

 *			     tsearch() for ordering the binary tree (report by

 *			     Adrian Bunk).

 *		02 Jul 2006, do not ignore pathnames in /tmp/, since some tools

 *			     create usable pathnames for both old/new files

 *			     there (Debian #376086).  Correct ifdef for

 *			     fgetc_unlocked().  Add configure check for

 *			     compress, gzip and bzip2 programs that may be used

 *			     to decompress files.

 *		24 Aug 2005, update usage message for -l, -r changes.

 *		15 Aug 2005, apply PLURAL() to num_files (Jean Delvare).

 *			     add -l option (request by Michael Burian).

 *			     Use fgetc_locked() if available.

 *		14 Aug 2005, add -r2 option (rounding with adjustment to ensure

 *			     that nonzero values always display a histogram

 *			     bar), adapted from patch by Jean Delvare.  Extend

 *			     the -f option (2=filled, 4=verbose).

 *		12 Aug 2005, modify to use tsearch() for sorted lists.

 *		11 Aug 2005, minor fixes to scaling of modified lines.  Add

 *			     -r (round) option.

 *		05 Aug 2005, add -t (table) option.

 *		10 Apr 2005, change order of merging and prefix-stripping so

 *			     stripping all prefixes, e.g., with -p9, will be

 *			     sorted as expected (Patch by Jean Delvare

 *			     <khali@linux-fr.org>).

 *		10 Jan 2005, add support for '--help' and '--version' (Patch

 *			     by Eric Blake <ebb9@byu.net>.)

 *		16 Dec 2004, fix a different case for data beginning with "--"

 *			     which was treated as a header line.

 *		14 Dec 2004, Fix allocation problems.  Open files in binary

 *			     mode for reading.  Getopt returns -1, not

 *			     necessarily EOF.  Add const where useful.  Use

 *			     NO_IDENT where necessary.  malloc() comes from

 *			     <stdlib.h> in standard systems (Patch by Eric

 *			     Blake <ebb9@byu.net>.)

 *		08 Nov 2004, minor fix for resync of unified diffs checks for

 *			     range (line beginning with '@' without header

 *			     lines (successive lines beginning with "---" and

 *			     "+++").  Fix a few problems reported by valgrind.

 *		09 Nov 2003, modify check for lines beginning with '-' or '+'

 *			     to treat only "---" in old-style diffs as a

 *			     special case.

 *		14 Feb 2003, modify check for filenames to allow for some cases

 *			     of incomplete dates (the reported example omitted

 *			     the day of the month).  Correct a typo in usage().

 *			     Add -e, -h, -o options.

 *		04 Jan 2003, improve tracking of chunks in unified diff, in

 *			     case the original files contained a '+' or '-' in

 *			     the first column (Debian #155000).  Add -v option

 *			     (Debian #170947).  Modify to allocate buffers big

 *			     enough for long input lines.  Do additional

 *			     merging to handle unusual Index/diff constructs in

 *			     recent makepatch script.

 *		20 Aug 2002, add -u option to tell diffstat to preserve the

 *			     order of filenames as given rather than sort them

 *			     (request by H Peter Anvin <hpa@zytor.com>).  Add

 *			     -k option for completeness.

 *		09 Aug 2002, allow either '/' or '-' as delimiters in dates,

 *			     to accommodate diffutils 2.8 (report by Rik van

 *			     Riel <riel@conectiva.com.br>).

 *		10 Oct 2001, add bzip2 (.bz2) suffix as suggested by

 *			     Gregory T Norris <haphazard@socket.net> in Debian

 *			     bug report #82969).

 *			     add check for diff from RCS archive where the

 *			     "diff" lines do not reference a filename.

 *		29 Mar 2000, add -c option.  Check for compressed input, read

 *			     via pipe.  Change to ANSI C.  Adapted change from

 *			     Troy Engel to add option that displays a number

 *			     only, rather than a histogram.

 *		17 May 1998, handle Debian diff files, which do not contain

 *			     dates on the header lines.

 *		16 Jan 1998, accommodate patches w/o tabs in header lines (e.g.,

 *			     from cut/paste).  Strip suffixes such as ".orig".

 *		24 Mar 1996, corrected -p0 logic, more fixes in do_merging.

 *		16 Mar 1996, corrected state-change for "Binary".  Added -p

 *			     option.

 *		17 Dec 1995, corrected matching algorithm in 'do_merging()'

 *		11 Dec 1995, mods to accommodate diffs against /dev/null or

 *			     /tmp/XXX (tempfiles).

 *		06 May 1995, limit scaling -- only shrink-to-fit.

 *		29 Apr 1995, recognize 'rcsdiff -u' format.

 *		26 Dec 1994, strip common pathname-prefix.

 *		13 Nov 1994, added '-n' option.  Corrected logic of 'match'.

 *		17 Jun 1994, ifdef-<string.h>

 *		12 Jun 1994, recognize unified diff, and output of makepatch.

 *		04 Oct 1993, merge multiple diff-files, busy message when the

 *			     output is piped to a file.

 *

 * Function:	this program reads the output of 'diff' and displays a histogram

 *		of the insertions/deletions/modifications per-file.

 */

#if defined(HAVE_CONFIG_H)

#include <config.h>

#endif

#if defined(WIN32) && !defined(HAVE_CONFIG_H)

#define HAVE_STDLIB_H

#define HAVE_STRING_H

#define HAVE_MALLOC_H

#define HAVE_GETOPT_H

#endif

#include <stdio.h>

#include <ctype.h>

#ifdef HAVE_STRING_H

#include <string.h>

#else

#include <strings.h>

#define strchr index

#define strrchr rindex

#endif

#ifdef HAVE_STDLIB_H

#include <stdlib.h>

#else

extern int atoi(const char *);

#endif

#ifdef HAVE_UNISTD_H

#include <unistd.h>

#else

extern int isatty(int);

#endif

#ifdef HAVE_OPENDIR

#include <dirent.h>

#endif

#ifdef HAVE_MALLOC_H

#include <malloc.h>

#endif

#if defined(HAVE_SEARCH_H) && defined(HAVE_TSEARCH)

#include <search.h>

#else

#undef HAVE_TSEARCH

#endif

#ifdef HAVE_GETC_UNLOCKED

#define MY_GETC getc_unlocked

#else

#define MY_GETC getc

#endif

#ifdef HAVE_GETOPT_H

#include <getopt.h>

#elif !defined(HAVE_GETOPT_HEADER)

extern int getopt(int, char *const *, const char *);

extern char *optarg;

extern int optind;

#endif

#include <sys/types.h>

#include <sys/stat.h>

#if defined(HAVE_POPEN) && !defined(HAVE_POPEN_PROTOTYPE)

extern FILE *popen(const char *, const char *);

extern int pclose(FILE *);

#endif

#if !defined(EXIT_SUCCESS)

#define EXIT_SUCCESS 0

#define EXIT_FAILURE 1

#endif

#ifndef BZCAT_PATH

#define BZCAT_PATH ""

#endif

#ifndef BZIP2_PATH

#define BZIP2_PATH ""

#endif

#ifndef COMPRESS_PATH

#define COMPRESS_PATH ""

#endif

#ifndef GZIP_PATH

#define GZIP_PATH ""

#endif

#ifndef LZCAT_PATH

#define LZCAT_PATH ""

#endif

#ifndef PCAT_PATH

#define PCAT_PATH ""

#endif

#ifndef UNCOMPRESS_PATH

#define UNCOMPRESS_PATH ""

#endif

#ifndef XZ_PATH

#define XZ_PATH ""

#endif

#ifndef ZCAT_PATH

#define ZCAT_PATH ""

#endif

/******************************************************************************/

#if defined(__MINGW32__) || defined(WIN32)

#define MKDIR(name,mode) mkdir(name)

#else

#define MKDIR(name,mode) mkdir(name,mode)

#endif

#if defined(WIN32) && !defined(__MINGW32__)

#define PATHSEP '\\'

#else

#define PATHSEP '/'

#endif

#define DQUOTE  '"'

#define SQUOTE  '\''

#define EOS     '\0'

#define BLANK   ' '

#define UC(c)   ((unsigned char)(c))

#ifndef OPT_TRACE

#define OPT_TRACE 1

#endif

#if OPT_TRACE

#define TRACE(p) if (trace_opt) printf p

#else

#define TRACE(p)		/*nothing */

#endif

#define contain_any(s,reject) (strcspn(s,reject) != strlen(s))

#define maximum(a,b) ((a) < (b) ? (b) : (a))

#define HAVE_NOTHING 0

#define HAVE_GENERIC 1		/* e.g., "Index: foo" w/o pathname */

#define HAVE_PATH    2		/* reference-file from "diff dirname/foo" */

#define HAVE_PATH2   4		/* comparison-file from "diff dirname/foo" */

#define FMT_CONCISE  0

#define FMT_NORMAL   1

#define FMT_FILLED   2

#define FMT_VERBOSE  4

typedef enum comment {

    Normal, Only, OnlyLeft, OnlyRight, Binary, Differs, Either

} Comment;

#define MARKS 4			/* each of +, - and ! */

typedef enum {

    cInsert = 0,

    cDelete,

    cModify,

    cEquals

} Change;

#define InsOf(p) (p)->count[cInsert]	/* "+" count inserted lines */

#define DelOf(p) (p)->count[cDelete]	/* "-" count deleted lines */

#define ModOf(p) (p)->count[cModify]	/* "!" count modified lines */

#define EqlOf(p) (p)->count[cEquals]	/* "=" count unmodified lines */

#define TotalOf(p) (InsOf(p) + DelOf(p) + ModOf(p) + EqlOf(p))

#define for_each_mark(n) for (n = 0; n < num_marks; ++n)

typedef struct _data {

    struct _data *link;

    char *name;			/* the filename */

    int copy;			/* true if filename is const-literal */

    int base;			/* beginning of name if -p option used */

    Comment cmt;

    int pending;

    long chunks;		/* total number of chunks */

    long chunk[MARKS];		/* counts for the current chunk */

    long count[MARKS];		/* counts for the file */

} DATA;

typedef enum {

    dcNone = 0,

    dcBzip,

    dcCompress,

    dcGzip,

    dcLzma,

    dcPack,

    dcXz,

    dcEmpty

} Decompress;

static const char marks[MARKS + 1] = "+-!=";

static const int colors[MARKS + 1] =

{2, 1, 6, 4};

static DATA *all_data;

static const char *comment_opt = "";

static char *path_opt = 0;

static int count_files;		/* true if we count added/deleted files */

static int format_opt = FMT_NORMAL;

static int max_name_wide;	/* maximum amount reserved for filenames */

static int max_width;		/* the specified width-limit */

static int merge_names = 1;	/* true if we merge similar filenames */

static int merge_opt = 0;	/* true if we merge ins/del as modified */

static int min_name_wide;	/* minimum amount reserved for filenames */

static int names_only;		/* true if we list filenames only */

static int num_marks = 3;	/* 3 or 4, according to "-P" option */

static int path_dest;		/* true if path_opt is destination (patched) */

static int plot_width;		/* the amount left over for histogram */

static int prefix_opt = -1;	/* if positive, controls stripping of PATHSEP */

static int quiet = 0;		/* -q option */

static int reverse_opt;		/* true if results are reversed */

static int round_opt = 0;	/* if nonzero, round data for histogram */

static int show_colors;		/* true if showing SGR colors */

static int show_progress;	/* if not writing to tty, show progress */

static int sort_names = 1;	/* true if we sort filenames */

static int summary_only = 0;	/* true if only summary line is shown */

static int suppress_binary = 0;	/* -b option */

static int trim_escapes = 0;	/* -E option */

static int table_opt = 0;	/* if 1/2, write table instead/also plot */

static int trace_opt = 0;	/* if nonzero, write debugging information */

static int unchanged = 0;	/* special-case for -S vs modified-files */

static int verbose = 0;		/* -v option */

static long plot_scale;		/* the effective scale (1:maximum) */

#ifdef HAVE_TSEARCH

static int use_tsearch;

static void *sorted_data;

#endif

static int number_len = 5;

static int prefix_len = -1;

/******************************************************************************/

#ifdef GCC_NORETURN

static void failed(const char *) GCC_NORETURN;

#endif

static void

failed(const char *s)

{

    perror(s);

    exit(EXIT_FAILURE);

}

/* malloc wrapper that never returns NULL */

static void *

xmalloc(size_t s)

{

    void *p;

    if ((p = malloc(s)) == NULL)

	failed("malloc");

    return p;

}

static mode_t

get_stat(const char *name)

{

    struct stat sb;

    int rc;

#ifdef HAVE_LSTAT

    rc = lstat(name, &sb);

#else

    rc = stat(name, &sb);

#endif

    return ((rc == 0) ? (sb.st_mode & S_IFMT) : 0);

}

static int

is_dir(const char *name)

{

    return get_stat(name) == S_IFDIR;

}

static int

is_file(const char *name)

{

    return get_stat(name) == S_IFREG;

}

static void

blip(int c)

{

    if (show_progress) {

	(void) fputc(c, stderr);

	(void) fflush(stderr);

    }

}

static char *

new_string(const char *s)

{

    return strcpy((char *) xmalloc((size_t) (strlen(s) + 1)), s);

}

static int

compare_data(const void *a, const void *b)

{

    const DATA *p = (const DATA *) a;

    const DATA *q = (const DATA *) b;

    return strcmp(p->name + p->base, q->name + q->base);

}

static void

init_data(DATA * data, const char *name, int copy, int base)

{

    memset(data, 0, sizeof(*data));

    data->name = (char *) name;

    data->copy = copy;

    data->base = base;

    data->cmt = Normal;

}

static DATA *

new_data(const char *name, int base)

{

    DATA *r = (DATA *) xmalloc(sizeof(DATA));

    init_data(r, new_string(name), 0, base);

    return r;

}

#ifdef HAVE_TSEARCH

static DATA *

add_tsearch_data(const char *name, int base)

{

    DATA find;

    DATA *result;

    void *pp;

    init_data(&find, name, 1, base);

    if ((pp = tfind(&find, &sorted_data, compare_data)) != 0) {

	result = *(DATA **) pp;

	return result;

    }

    result = new_data(name, base);

    (void) tsearch(result, &sorted_data, compare_data);

    result->link = all_data;

    all_data = result;

    return result;

}

#endif

static int

count_prefix(const char *name)

{

    int count = 0;

    const char *s;

    while ((s = strchr(name, PATHSEP)) != 0) {

	name = s + 1;

	++count;

    }

    return count;

}

static const char *

skip_prefix(const char *name, int prefix, int *base)

{

    if (prefix >= 0) {

	int n;

	*base = 0;

	for (n = prefix; n > 0; n--) {

	    const char *s = strchr(name + *base, PATHSEP);

	    if (s == 0 || *++s == EOS) {

		name = s;

		break;

	    }

	    *base = (int) (s - name);

	}

	TRACE(("** base set to %d\n", *base));

    }

    return name;

}

static DATA *

find_data(const char *name)

{

    DATA *p, *q, *r;

    DATA find;

    int base = 0;

    TRACE(("** find_data(%s)\n", name));

    /* Compute the base offset if the prefix option is used */

    if (prefix_opt >= 0) {

	(void) skip_prefix(name, prefix_opt, &base);

    }

    /* Insert into sorted list (usually sorted).  If we are not sorting or

     * merging names, we fall off the end and link the new entry to the end of

     * the list.  If the prefix option is used, the prefix is ignored by the

     * merge and sort operations.

     *

     * If we have tsearch(), we will maintain the sorted list using it and

     * tfind().

     */

#ifdef HAVE_TSEARCH

    if (use_tsearch) {

	r = add_tsearch_data(name, base);

    } else

#endif

    {

	init_data(&find, name, 1, base);

	for (p = all_data, q = 0; p != 0; q = p, p = p->link) {

	    int cmp = compare_data(p, &find);

	    if (merge_names && (cmp == 0))

		return p;

	    if (sort_names && (cmp > 0))

		break;

	}

	r = new_data(name, base);

	if (q != 0)

	    q->link = r;

	else

	    all_data = r;

	r->link = p;

    }

    return r;

}

/*

 * Remove a unneeded data item from the linked list.  Free the name as well.

 */

static int

delink(DATA * data)

{

    DATA *p, *q;

    TRACE(("** delink '%s'\n", data->name));

#ifdef HAVE_TSEARCH

    if (use_tsearch) {

	if (tdelete(data, &sorted_data, compare_data) == 0)

	    return 0;

    }

#endif

    for (p = all_data, q = 0; p != 0; q = p, p = p->link) {

	if (p == data) {

	    if (q != 0)

		q->link = p->link;

	    else

		all_data = p->link;

	    if (!p->copy)

		free(p->name);

	    free(p);

	    return 1;

	}

    }

    return 0;

}

/*

 * Compare string 's' against a constant, returning either a pointer just

 * past the matched part of 's' if it matches exactly, or null if a mismatch

 * was found.

 */

static char *

match(char *s, const char *p)

{

    int ok = 0;

    while (*s != EOS) {

	if (*p == EOS) {

	    ok = 1;

	    break;

	}

	if (*s++ != *p++)

	    break;

	if (*s == EOS && *p == EOS) {

	    ok = 1;

	    break;

	}

    }

    return ok ? s : 0;

}

static int

version_num(const char *s)

{

    int main_ver, sub_ver;

    char temp[2];

    return (sscanf(s, "%d.%d%c", &main_ver, &sub_ver, temp) == 2);

}

/*

 * Check for a range of line-numbers, used in editing scripts.

 */

static int

edit_range(const char *s)

{

    int first, last;

    char temp[2];

    return (sscanf(s, "%d,%d%c", &first, &last, temp) == 2)

	|| (sscanf(s, "%d%c", &first, temp) == 1);

}

/*

 * Decode a range for default diff.

 */

static int

decode_default(char *s,

	       long *first, long *first_size,

	       long *second, long *second_size)

{

    int rc = 0;

    char *next;

    if (isdigit(UC(*s))) {

	*first_size = 1;

	*second_size = 1;

	*first = strtol(s, &next, 10);

	if (next != 0 && next != s) {

	    if (*next == ',') {

		s = ++next;

		*first_size = strtol(s, &next, 10) + 1 - *first;

	    }

	}

	if (next != 0 && next != s) {

	    switch (*next++) {

	    case 'a':

	    case 'c':

	    case 'd':

		s = next;

		*second = strtol(s, &next, 10);

		if (next != 0 && next != s) {

		    if (*next == ',') {

			s = ++next;

			*second_size = strtol(s, &next, 10) + 1 - *second;

		    }

		}

		if (next != 0 && next != s && *next == EOS)

		    rc = 1;

		break;

	    }

	}

    }

    return rc;

}

/*

 * Decode a range for unified diff.  Oddly, the comments in diffutils code

 * claim that both numbers are line-numbers.  However, inspection of the output

 * shows that the numbers are a line-number followed by a count.

 */

static int

decode_range(const char *s, int *first, int *second)

{

    int rc = 0;

    char check;

    if (isdigit(UC(*s))) {

	if (sscanf(s, "%d,%d%c", first, second, &check) == 2) {

	    TRACE(("** decode_range #1 first=%d, second=%d\n", *first, *second));

	    rc = 1;

	} else if (sscanf(s, "%d%c", first, &check) == 1) {

	    *second = *first;	/* diffutils 2.7 does this */

	    TRACE(("** decode_range #2 first=%d, second=%d\n", *first, *second));

	    rc = 1;

	}

    }

    return rc;

}

static int

HadDiffs(const DATA * data)

{

    return InsOf(data) != 0

	|| DelOf(data) != 0

	|| ModOf(data) != 0

	|| data->cmt != Normal;

}

/*

 * If the given path is not one of the "ignore" paths, then return true.

 */

static int

can_be_merged(const char *path)

{

    int result = 0;

    if (strcmp(path, "")

	&& strcmp(path, "/dev/null"))

	result = 1;

    return result;

}

static int

is_leaf(const char *theLeaf, const char *path)

{

    char *s;

    if (strchr(theLeaf, PATHSEP) == 0

	&& (s = strrchr(path, PATHSEP)) != 0

	&& !strcmp(++s, theLeaf))

	return 1;

    return 0;

}

static char *

trim_datapath(DATA ** datap, size_t length, int *localp)

{

    char *target = (*datap)->name;

#ifdef HAVE_TSEARCH

    /*

     * If we are using tsearch(), make a local copy of the data

     * so we can trim it without interfering with tsearch's

     * notion of the ordering of data.  That will create some

     * spurious empty data, so we add the changed() macro in a

     * few places to skip over those.

     */

    if (use_tsearch) {

	char *trim = new_string(target);

	trim[length] = EOS;

	*datap = add_tsearch_data(trim, (*datap)->base);

	target = (*datap)->name;

	free(trim);

	*localp = 1;

    } else

#endif

	target[length] = EOS;

    return target;

}

static size_t

compare_tails(const char *target, const char *source, int *diff)

{

    size_t len1 = strlen(target);

    size_t len2 = strlen(source);

    size_t n;

    size_t matched = 0;

    *diff = 0;

    for (n = 1; n <= len1 && n <= len2; n++) {

	if (target[len1 - n] != source[len2 - n]) {

	    *diff = (int) n;

	    break;

	}

	if (source[len2 - n] == PATHSEP) {

	    matched = n;

	}

    }

    return matched;

}

/*

 * The 'data' parameter points to the first of two markers, while

 * 'path' is the pathname from the second marker.

 *

 * On the first call for

 * a given file, the 'data' parameter stores no differences.

 */

static char *

do_merging(DATA * data, char *path, int *freed)

{

    char *target = reverse_opt ? path : data->name;

    char *source = reverse_opt ? data->name : path;

    char *result = source;

    int diff;

    TRACE(("** do_merging(\"%s\",\"%s\") diffs:%d\n",

	   data->name, path, HadDiffs(data)));

    *freed = 0;

    if (!HadDiffs(data)) {

	if (is_leaf(target, source)) {

	    TRACE(("** is_leaf: \"%s\" vs \"%s\"\n", target, source));

	    if (reverse_opt) {

		TRACE((".. no action @%d\n", __LINE__));

	    } else {

		*freed = delink(data);

	    }

	} else if (can_be_merged(target)

		   && can_be_merged(source)) {

	    size_t len1 = strlen(target);