/*
 * fhist - file history and comparison tools
 * Copyright (C) 1991-1994, 1997-2000, 2002, 2005 Peter Miller;
 * All rights reserved.
 *
 * Derived from a work
 * Copyright (C) 1990 David I. Bell.
 *
 *      This program is free software; you can redistribute it and/or modify
 *      it under the terms of the GNU General Public License as published by
 *      the Free Software Foundation; either version 2 of the License, or
 *      (at your option) any later version.
 *
 *      This program 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 General Public License for more details.
 *
 *      You should have received a copy of the GNU General Public License
 *      along with this program; if not, write to the Free Software
 *      Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111, USA.
 *
 * MANIFEST: functions to merge differences from a base file.
 */

#include <ac/stdio.h>
#include <ac/string.h>
#include <ac/libintl.h>

#include <cmalloc.h>
#include <compare.h>
#include <error_intl.h>
#include <fcheck.h>
#include <fileio.h>
#include <work.h>

#define CONFLICT_BEGIN	\
"/-/-/-/-/-/-/-/-/-/ BEGIN CONFLICT  [O%ld A%ld B%ld] /-/-/-/-/-/-/-/-/-/-/\n"
#define CONFLICT_MIDDLE	\
"/-/-/-/-/-/-/-/-/-/-/-/-/-/-/-/-/-/-/-/-/-/-/-/-/-/-/-/-/-/-/-/-/-/-/-/-/-/\n"
#define CONFLICT_END	\
"/-/-/-/-/-/-/-/-/-/-/-/-/  END CONFLICT   /-/-/-/-/-/-/-/-/-/-/-/-/-/-/-/-/\n"

#define F_OLDDATA	0x0000	/* lines the same as the old ones */
#define F_DELETEA	0x0001	/* lines deleted by file A */
#define F_INSERTA	0x0002	/* lines inserted by file A */
#define F_DELETEB	0x0004	/* lines deleted by file B */
#define F_INSERTB	0x0008	/* lines inserted by file B */
#define F_CONFLICT	0x0010	/* this line is a conflict */

#define MAXSHORT	0x7fff	/* highest positive short value */


typedef struct MERGE MERGE;
struct MERGE
{
    long            m_baseline;     /* line number in base file */
    long            m_fileAline;    /* line number in file A */
    long            m_fileBline;    /* line number in file B */
    short           m_basecount;    /* lines in base file used or deleted */
    short           m_fileAcount;   /* number of lines inserted by file A */
    short           m_fileBcount;   /* number of lines inserted by file B */
    short           m_flags;        /* what is happening to this line */
    MERGE           *m_next;        /* next line */
};


long            conflicts;          /* number of conflicts */
long            failcount;          /* maximum conflicts allowable */
long            unchangecount;      /* maximum unchanged lines to output */
short           ignoreflag;         /* ignore conflicts */
short           ignore_identical;   /* ignore identical conflicts */

static MERGE    *begmergelist;      /* head of merge list */
static MERGE    *endmergelist;      /* end of merge list */
static LINE     **baselines;        /* lines of base file */
static LINE     **fileAlines;       /* lines of file A */
static LINE     **fileBlines;       /* lines of file B */


/*
 * Allocate a new merge structure and append it to the end of the merge list.
 */

static MERGE *
newmerge(void)
{
    MERGE           *mp;            /* new merge structure */

    mp = (MERGE *)cm_alloc_and_check(sizeof(MERGE));
    mp->m_next = NULL;
    mp->m_flags = 0;
    mp->m_baseline = 0;
    mp->m_fileAline = 0;
    mp->m_fileBline = 0;
    mp->m_basecount = 0;
    mp->m_fileAcount = 0;
    mp->m_fileBcount = 0;
    if (begmergelist == NULL)
        begmergelist = mp;
    else
        endmergelist->m_next = mp;
    endmergelist = mp;
    return mp;
}


/*
 * Merge differences between two divergent files, based on a common
 * precursor file.  The resulting output is saved in memory so that it
 * can be examined or output later.
 */

void
fmerge(char *basename, char *nameA, char *nameB)
{
    SNAKE           *spA;           /* snake for edits of first file */
    SNAKE           *spB;           /* snake for edits of second file */
    MERGE           *mp;            /* current merge structure */
    SNAKE           *fileAsnakes;   /* snake for first edit */
    SNAKE           *fileBsnakes;   /* snake for second edit */
    long            baseline;       /* current line of base file */
    long            lineA;          /* current line of file A */
    long            lineB;          /* current line of file B */
    long            deletesA;       /* deletes needed for file A */
    long            insertsA;       /* inserts needed for file A */
    long            deletesB;       /* deletes needed for file B */
    long            insertsB;       /* inserts needed for file B */
    long            count;          /* number of lines being examined */
    long            elements;       /* number of elements used */
    int             bad;            /* 1 if bad merge detected */

    fc.maxjoin = 0;
    fc.maxchanges = INFINITY;
    fcomp(basename, nameA);
    baselines = fc.fileA.f_lines;
    fileAlines = fc.fileB.f_lines;
    fc.fileB.f_lines = NULL;
    fileAsnakes = fc.snakelist;
    fc.snakelist = NULL;
    fcomp(NULL, nameB);
    fileBsnakes = fc.snakelist;
    fileBlines = fc.fileB.f_lines;
    fc.fileB.f_lines = NULL;
    fc.snakelist = NULL;

    /*
     * Now walk through the snakes and merge the lines.
     */
#if 0
    if (fc.verbosity > VERBOSE_DEFAULT)
        error_raw("[Creating merge list]");
#endif
    spA = fileAsnakes;
    spB = fileBsnakes;
    baseline = 0;
    lineA = 0;
    lineB = 0;
    conflicts = 0;
    elements = 0;
    begmergelist = NULL;
    endmergelist = NULL;
    for (;;)
    {
	int             det;

        deletesA = spA->line1 - baseline;
        insertsA = spA->line2 - lineA;
        deletesB = spB->line1 - baseline;
        insertsB = spB->line2 - lineB;
        if (deletesA > MAXSHORT)
            deletesA = MAXSHORT;
        if (insertsA > MAXSHORT)
            insertsA = MAXSHORT;
        if (deletesB > MAXSHORT)
            deletesB = MAXSHORT;
        if (insertsB > MAXSHORT)
            insertsB = MAXSHORT;
        mp = newmerge();
        mp->m_baseline = baseline;
        mp->m_fileAline = lineA;
        mp->m_fileBline = lineB;
        mp->m_fileAcount = insertsA;
        mp->m_fileBcount = insertsB;
#if 0
        if ((fc.verbosity > VERBOSE_DEFAULT) && ((++elements % 1000) == 0))
            error_raw("[%ld merge elements]", elements);
#endif

        bad = ((deletesA < 0) || (insertsA < 0) ||
            (deletesB < 0) || (insertsB < 0));

        det =
            (
		(deletesA > 0 ? F_DELETEA : 0)
            +
		(insertsA > 0 ? F_INSERTA : 0)
            +
		(deletesB > 0 ? F_DELETEB : 0)
	    +
		(insertsB > 0 ? F_INSERTB : 0)
	    );

        if (fc.debugflag || bad)
        {
#if 0
            error_raw
	    (
		"SA %ld %ld %ld, SB %ld %ld %ld, Lines %ld %ld %ld, Case %ld",
                spA->line1,
                spA->line2,
                spA->count,
                spB->line1,
                spB->line2,
		spB->count,
		baseline,
		lineA,
		lineB,
		det
	    );
#endif
            if (bad)
                fatal_intl(0, i18n("bad merge calculation"));
        }

        switch (det)
        {
        case 0:
            /* no inserts or deletes at all */
            if ((spA->next == NULL) && (spB->next == NULL))
            {
#if 0
                if (fc.verbosity > VERBOSE_DEFAULT)
                    error_raw("[%ld merge elements used]", elements);
#endif
                if (ignoreflag)
                    conflicts = 0;
                return;
            }
            count = spA->count;
            if (count > spB->count)
                count = spB->count;
            if (count > MAXSHORT)
                count = MAXSHORT;
            mp->m_flags = F_OLDDATA;
            mp->m_basecount = count;
	    mp->m_fileAcount = count;
	    mp->m_fileBcount = count;
            spA->line1 += count;
            spA->line2 += count;
            spA->count -= count;
            spB->line1 += count;
            spB->line2 += count;
            spB->count -= count;
            break;

        case F_INSERTA:
            /* insert for file A */
            mp->m_flags = F_INSERTA;
            break;

        case (F_INSERTA | F_DELETEA):
            /* insert and delete for file A */
            mp->m_flags = F_INSERTA;
            /* Fall through... */

        case F_DELETEA:
            /* delete for file A */
            count = deletesA;
            if (count > spB->count)
                count = spB->count;
            mp->m_flags |= F_DELETEA;
            mp->m_basecount = count;
            mp->m_fileBcount = count;
            spB->line1 += count;
            spB->line2 += count;
            spB->count -= count;
            break;

        case (F_INSERTB | F_DELETEB):
            /* insert and delete for file B */
            mp->m_flags = F_INSERTB;
            /* Fall through... */

        case F_DELETEB:
            /* delete for file B */
            count = deletesB;
            if (count > spA->count)
                count = spA->count;
            mp->m_flags |= F_DELETEB;
            mp->m_basecount = count;
            mp->m_fileAcount = count;
            spA->line1 += count;
            spA->line2 += count;
            spA->count -= count;
            break;

        case (F_DELETEA | F_DELETEB):
            /* files A and B both delete */
            count = deletesA;
            if (count > deletesB)
                count = deletesB;
	    mp->m_flags |= F_DELETEA | F_DELETEB;
	    mp->m_basecount = count;
	    if (ignore_identical)
	    {
		/*
                 * This is not an actual conflict, even though it
                 * is a logical conflict, according to most users'
                 * expectations.
		 */
		break;
	    }
            mp->m_flags |= F_CONFLICT;
            conflicts += count;
            break;

        case (F_INSERTA | F_DELETEA | F_DELETEB):
            /* file A inserts and deletes, file B deletes */
            count = deletesA;
            if (count > deletesB)
                count = deletesB;
            mp->m_flags = (F_INSERTA | F_DELETEA | F_DELETEB | F_CONFLICT);
            mp->m_basecount = count;
            conflicts += count;
            break;

        case F_INSERTB:
            /* insert for file B */
            mp->m_flags = F_INSERTB;
            break;

        case (F_INSERTA | F_INSERTB):
            /* file A and file B both insert */
	    if (ignore_identical)
	    {
		for
		(
		    count = 0;
		    count < mp->m_fileAcount && count < mp->m_fileBcount;
		    ++count
		)
		{
		    LINE *lp_a = fileAlines[mp->m_fileAline + count];
		    LINE *lp_b = fileBlines[mp->m_fileBline + count];
		    if (0 != strcmp(lp_a->l_data, lp_b->l_data))
			break;
		}
		if (count > 0)
		{
		    /*
                     * This is not an actual conflict according to most
                     * users' expectations, even though it is a logical
                     * conflict.
		     */
		    mp->m_flags = F_INSERTA;
		    mp->m_basecount = 0;
		    mp->m_fileAcount = count;
		    mp->m_fileBcount = count;
		    break;
		}
	    }
            mp->m_flags = F_INSERTA | F_INSERTB | F_CONFLICT;
            conflicts++;
            break;

        case (F_INSERTA | F_DELETEA | F_INSERTB):
            /* insert and delete for A, insert for B */
            mp->m_flags = F_INSERTA;
            /* Fall through... */

        case (F_DELETEA | F_INSERTB):
            /* delete for file A and insert for file B */
            mp->m_flags |= (F_DELETEA | F_INSERTB | F_CONFLICT);
            mp->m_basecount = 1;
            spB->line1++;
            spB->line2++;
            spB->count--;
	    lineB++;
            conflicts++;
            break;

        case (F_DELETEA | F_INSERTB | F_DELETEB):
            /* file A deletes, file B inserts and deletes */
            count = deletesA;
            if (count > deletesB)
                count = deletesB;
            mp->m_flags = (F_DELETEA | F_INSERTB | F_DELETEB | F_CONFLICT);
            mp->m_basecount = count;
            conflicts += count;
            break;

        case (F_INSERTA | F_INSERTB | F_DELETEB):
            /* insert for A, insert and delete for B */
            mp->m_flags = F_INSERTB;
            /* Fall through... */

        case (F_INSERTA | F_DELETEB):
            /* insert for file A and delete for file B */
            mp->m_flags |= (F_INSERTA | F_DELETEB | F_CONFLICT);
            mp->m_basecount = 1;
            spA->line1++;
            spA->line2++;
            spA->count--;
	    lineA++;
            conflicts++;
            break;

        case (F_INSERTA | F_DELETEA | F_INSERTB | F_DELETEB):
            /* insert and delete for A and for B */
            count = deletesA;
            if (count > deletesB)
                count = deletesB;
            mp->m_basecount = count;
	    if (deletesA == deletesB && ignore_identical)
	    {
		for
		(
		    count = 0;
		    count < mp->m_fileAcount && count < mp->m_fileBcount;
		    ++count
		)
		{
		    LINE *lp_a = fileAlines[mp->m_fileAline + count];
		    LINE *lp_b = fileBlines[mp->m_fileBline + count];
		    if (0 != strcmp(lp_a->l_data, lp_b->l_data))
			break;
		}
		if (count > 0)
		{
		    /*
                     * This is not an actual conflict according to most
                     * users' expectations, even though it is a logical
                     * conflict.
		     */
		    mp->m_flags = F_INSERTA | F_DELETEA | F_DELETEB;
		    break;
		}
	    }
            mp->m_flags =
		(F_INSERTA | F_DELETEA | F_INSERTB | F_DELETEB | F_CONFLICT);
            conflicts += count;
            break;
        }
        if ((conflicts > failcount) && !ignoreflag)
        {
            sub_context_ty  *scp;

            scp = sub_context_new();
            sub_var_set_long(scp, "Number", failcount);
            fatal_intl
	    (
		scp,
		i18n("more than $number conflicts found during merge")
	    );
        }
        baseline += mp->m_basecount;
        lineA += mp->m_fileAcount;
        lineB += mp->m_fileBcount;
        if ((spA->count <= 0) && (spA->next))
            spA = spA->next;
        if ((spB->count <= 0) && (spB->next))
            spB = spB->next;
    }
}


/*
 * Walk through the merge list and output the resulting file.
 * Conflicts will be identified by conflict identification lines.
 */

void
dumpmergedfile(char *outputname)
{
    MERGE           *mp;            /* current merge structure */
    LINE            **lp;           /* current line */
    FILE            *fp;            /* file to output to (or TERMINAL) */
    long            count;          /* line count */
    int             conflict;       /* 1 if inside of a conflict */
    int             newconflict;    /* new conflict value */

#if 0
    if ((fc.verbosity > VERBOSE_DEFAULT) && outputname)
        error_raw("[Writing merged lines to \"%s\"]", outputname);
#endif
    if (outputname)
    {
        fp = fopen_and_check(outputname, "w");
    }
    else
    {
        fp = stdout;
        outputname = gettext("standard output");
    }
    conflict = 0;
    for (mp = begmergelist; mp; mp = mp->m_next)
    {
        newconflict = ((mp->m_flags & F_CONFLICT) && !ignoreflag);
        if (newconflict != conflict)
        {
            conflict = newconflict;
            fprintf
    	    (
		fp,
		conflict ? CONFLICT_BEGIN : CONFLICT_END,
                mp->m_baseline + 1,
		mp->m_fileAline + 1,
		mp->m_fileBline + 1
	    );
        }
        if (mp->m_flags == F_OLDDATA)
        {
            lp = &baselines[mp->m_baseline];
            for (count = mp->m_basecount; count > 0; count--)
                fputs((*lp++)->l_data, fp);
            continue;
        }
        if (mp->m_flags & F_INSERTA)
        {
            lp = &fileAlines[mp->m_fileAline];
            for (count = mp->m_fileAcount; count > 0; count--)
                fputs((*lp++)->l_data, fp);
        }
        if (conflict && (mp->m_flags & F_INSERTA) && (mp->m_flags & F_INSERTB))
            fputs(CONFLICT_MIDDLE, fp);
        if (mp->m_flags & F_INSERTB)
        {
            lp = &fileBlines[mp->m_fileBline];
            for (count = mp->m_fileBcount; count > 0; count--)
                fputs((*lp++)->l_data, fp);
        }
    }
    if (conflict)
        fputs(CONFLICT_END, fp);
    fflush_and_check(fp, outputname);
    fclose_and_check(fp, outputname);
}


/*
 * Walk down and dump out a list of merges, either for non-conflicts,
 * or for either file A or B of a conflict.  Returns the first merge
 * structure not processed due to the change of conflict.
 */

static MERGE *
walkmerges(FILE *fp, MERGE *mp, int flagmask, const char *filename)
{
    LINE            **lp;           /* current line */
    short           count;          /* number of lines to handle */
    short           flags;          /* flags to be checked */

    for (;; mp = mp->m_next)
    {
        if
       	(
	    (mp == NULL)
	||
            ((flagmask & F_CONFLICT) == (mp->m_flags & F_CONFLICT))
	)
            return mp;
        flags = mp->m_flags;
        if (flags == F_OLDDATA)
        {
            /* show original lines */
            lp = &baselines[mp->m_baseline];
            count = mp->m_basecount;
            if (((count - 1) / 2) < unchangecount)
            {
                while (--count >= 0)
                {
                    writefx(fp, "   ", 3L, filename);
                    fputs((*lp++)->l_data, fp);
                }
                continue;
            }
            /*
             * Number of unchanged lines exceeds specified limit.
             * So only show the first few and last few changes.
             */
            for (count = unchangecount; count > 0; count--)
            {
                writefx(fp, "   ", 3L, filename);
                fputs((*lp++)->l_data, fp);
            }
            fprintf(fp, "U  %ld\n", mp->m_basecount - (unchangecount * 2));
            lp = &baselines[mp->m_baseline + mp->m_basecount - unchangecount];
            for (count = unchangecount; count > 0; count--)
            {
                writefx(fp, "   ", 3L, filename);
                fputs((*lp++)->l_data, fp);
            }
            continue;
        }
        flags &= flagmask;
        if (flags & F_INSERTA)
        {
            lp = &fileAlines[mp->m_fileAline];
            for (count = mp->m_fileAcount; count > 0; count--)
            {
                writefx(fp, "IA ", 3L, filename);
                fputs((*lp++)->l_data, fp);
            }
        }
        if (flags & F_DELETEA)
        {
            lp = &baselines[mp->m_baseline];
            for (count = mp->m_basecount; count > 0; count--)
            {
                writefx(fp, "DA ", 3L, filename);
                fputs((*lp++)->l_data, fp);
            }
        }
        if (flags & F_INSERTB)
        {
            lp = &fileBlines[mp->m_fileBline];
            for (count = mp->m_fileBcount; count > 0; count--)
            {
                writefx(fp, "IB ", 3L, filename);
                fputs((*lp++)->l_data, fp);
            }
        }
        if (flags & F_DELETEB)
        {
            lp = &baselines[mp->m_baseline];
            for (count = mp->m_basecount; count > 0; count--)
            {
                writefx(fp, "DB ", 3L, filename);
                fputs((*lp++)->l_data, fp);
            }
        }
    }
}


/*
 * Dump out the possible conflicts to a file that indicates what both
 * divergent files did to the base file.  This is useful even if there
 * are no physical conflicts in order to manually find logical conflicts.
 */

void
dumpconflicts(char *outputname)
{
    MERGE           *mp;            /* current merge structure */
    FILE            *fp;            /* file to output to */

#if 0
    if ((fc.verbosity > VERBOSE_DEFAULT) && outputname)
        error_raw("[Writing conflict lines to \"%s\"]", outputname);
#endif
    if (outputname)
    {
        fp = fopen_and_check(outputname, "w");
    }
    else
    {
        fp = stdout;
        outputname = gettext("standard output");
    }
    fprintf(fp, "T %ld conflict%s\n", conflicts, (conflicts == 1) ? "" : "s");
    mp = begmergelist;
    while (mp)
    {
	/* non-conflicts */
        mp = walkmerges(fp, mp, -1, outputname);
        if (mp == NULL)
            break;
        if (!ignoreflag)
        {
            writefx(fp, "X  ", 3L, outputname);
            fprintf(fp, CONFLICT_BEGIN, mp->m_baseline + 1,
                mp->m_fileAline + 1, mp->m_fileBline + 1);
        }
	/* file A conflicts */
        walkmerges(fp, mp, F_INSERTA | F_DELETEA, outputname);
        if (!ignoreflag)
            fprintf(fp, "X  %s", CONFLICT_MIDDLE);
	/* file B conflicts */
        mp = walkmerges(fp, mp, F_INSERTB | F_DELETEB, outputname);
        if (!ignoreflag)
            fprintf(fp, "X  %s", CONFLICT_END);
    }
    fflush_and_check(fp, outputname);
    fclose_and_check(fp, outputname);
}


/*
 * Read in a conflict file and produce an output file.
 */

void
convertconflicts(char *inputname, char *outputname)
{
    char            *cp;            /* current line */
    FILE            *ip;            /* input file */
    FILE            *op;            /* output file */
    long            inputlines;
    long            outputlines;    /* input and output line counts */
    long            retlen;         /* length of current line */
    sub_context_ty  *scp;

#if 0
    if (fc.verbosity > VERBOSE_DEFAULT && outputname)
        error_raw("[Converting conflict file \"%s\" to output file \"%s\"]",
            inputname, outputname);
#endif
    inputlines = 0;
    outputlines = 0;
    ip = fopen_and_check(inputname, "r");
    if (outputname)
    {
        op = fopen_and_check(outputname, "w");
    }
    else
    {
        op = stdout;
        outputname = gettext("standard output");
    }
    for (;;)
    {
        int             bin;

	bin = 0;
        cp = readlinef(ip, &retlen, 0, inputname, &bin);
        if (cp == NULL)
            break;
        if (bin)
            binary_fatal(inputname);
#if 0
        if (((++inputlines % 1000) == 0) && (fc.verbosity > VERBOSE_DEFAULT))
            error_raw("[%ld lines]", inputlines);
#endif
        switch (*cp)
        {
        case 'I':       /* inserted lines */
        case ' ':       /* original base lines */
            cp += 3;
            retlen -= 3;
            if (retlen <= 0)
            {
                cp = "\n";
                retlen = 1;
            }
            writefx(op, cp, retlen, outputname);
            outputlines++;
            break;

        case '\n':      /* original blank line */
            writefx(op, "\n", 1L, outputname);
            break;

        case 'D':       /* deleted lines */
        case 'T':       /* the total line */
            break;

        case 'X':
            if (ignoreflag)
                break;
            scp = sub_context_new();
            sub_var_set_long(scp, "Number", inputlines);
            fatal_with_filename
	    (
		inputname,
                scp,
		i18n("unresolved conflict remaining at line $number")
	    );

        case 'U':
            fatal_with_filename
	    (
		inputname,
		0,
		i18n("incomplete due to -u option being used")
	    );

        default:
            scp = sub_context_new();
            sub_var_set_long(scp, "Number", inputlines);
            fatal_with_filename
	    (
		inputname,
		scp,
		i18n("unknown line $number read")
	    );
        }
    }
    fclose_and_check(ip, inputname);
    fflush_and_check(op, outputname);
    fclose_and_check(op, outputname);
#if 0
    if (fc.verbosity > VERBOSE_DEFAULT)
        error_raw("[%ld lines read, %ld lines written]",
            inputlines, outputlines);
#endif
}