/* define DIFF_DETAIL for a detailed trace of diff synthesis */

#include <errno.h>
#include <fcntl.h>
#include <stdio.h>
#include <curses.h>
#include <stdlib.h>
#include <unistd.h>
#include <strings.h>
#include <sys/wait.h>

extern const char *__progname;

#include "fatal.h"
#include "subproc.h"
#include "git-intf.h"
#include "datastruct.h"

#include "ui.h"

typedef struct fhl FHL;

struct fhl {
  FIL *f;
  HUNK *h;
  HUNKLINE *l;
  } ;

static unsigned int tempserial = 0;
static int cursed = 0;
static FHL top;
static FHL cur;
static int curline;
static HUNK *merging;

void ui_abort(void)
{
 if (cursed)
  { move(LINES-1,0);
    refresh();
    endwin();
    printf("\n");
    cursed = 0;
  }
}

static void ui_save(void)
{
 ui_abort(); /* conceptually different, same implementation */
}

static void ui_setup(void)
{
 if (! cursed)
  { initscr();
    noecho();
    cbreak();
    cursed = 1;
  }
 merging = 0;
}

static void ui_restore(void)
{
 ui_setup(); /* conceptually different, same implemenation */
}

static void file_line(int y, FIL *f)
{
 mvprintw(y,0,"%c %.*s",
	(f->flags & FF_ALLAPPLIED) ? 'A' : ' ',
	COLS-3, f->escname );
 clrtoeol();
}

static void hunk_line(int y, HUNK *h)
{
 mvprintw(y,0,"%c | @@ -%d,%d +%d,%d",(h==merging)?'m':(h->flags&HF__HIDDEN)?'*':(h->flags&HF_SELECTED)?'>':' ',h->fl,h->fn,h->tl,h->tn);
 if (h->splitfrom) printw(" (split @@ -%d,%d +%d,%d)",h->splitfrom->fl,h->splitfrom->fn,h->splitfrom->tl,h->splitfrom->tn);
 clrtoeol();
}

static void line_line(int y, HUNKLINE *l)
{
 int c;
 unsigned const char *t;
 unsigned char q[8];
 int qx;
 int tch;
 int i;

 mvprintw(y,0,"%c | | ",(l->h==merging)?'m':(l->h->flags&HF_SELECTED)?'>':' ');
 switch (l->type)
  { default: abort(); break;
    case HLT_COMMON: addch(' '); break;
    case HLT_FROM:   addch('-'); break;
    case HLT_TO:     addch('+'); break;
  }
 addch(' ');
 c = 0;
 t = (const void *) l->text;
 qx = 0;
 while ((c < COLS-8-2) && *t)
  { tch = -1;
    if (qx > 0)
     { tch = q[--qx];
     }
    else if (*t == '\t')
     { i = 8 - (c & 7);
       memset(&q[0],' ',i);
       qx = i;
     }
    else if (*t < 32)
     { q[0] = *t ^ 64;
       q[1] = '^';
       qx = 2;
     }
    else if (*t == 127)
     { q[0] = '?';
       q[1] = '^';
       qx = 2;
     }
    else if ((*t >= 127) && (*t < 160))
     { q[0] = '0' + (*t & 7);
       q[1] = '0' + ((*t >> 3) & 7);
       q[2] = '0' + ((*t >> 6) & 7);
       q[3] = '\\';
       qx = 4;
     }
    else
     { tch = *t++;
     }
    if (tch < 0)
     { t ++;
     }
    else
     { addch(tch);
       c ++;
     }
  }
 clrtoeol();
}

static void fhl_down_f(FHL *c)
{
 do c->f = c->f->flink; while (c->f && (c->f->flags & FF_ALLAPPLIED));
 c->h = 0;
}

static void fhl_down_h(FHL *c)
{
 do c->h = c->h->fflink; while (c->h && (c->h->flags & HF__HIDDEN));
 if (! c->h) fhl_down_f(c);
 c->l = 0;
}

static void fhl_down_l(FHL *c)
{
 c->l = c->l->flink;
 if (! c->l) fhl_down_h(c);
}

static void fhl_up_f(FHL *c)
{
 do c->f = c->f->blink; while (c->f && (c->f->flags & FF_ALLAPPLIED));
 if (c->f && (c->f->flags & FF_EXPANDED))
  { c->h = c->f->diff_t;
    while (c->h->flags & HF__HIDDEN) c->h = c->h->fblink;
    if (c->h->flags & HF_EXPANDED) c->l = c->h->line_t;
  }
}

static void fhl_up_h(FHL *c)
{
 do c->h = c->h->fblink; while (c->h && (c->h->flags & HF__HIDDEN));
 if (c->h && (c->h->flags & HF_EXPANDED)) c->l = c->h->line_t;
}

static void fhl_up_l(FHL *c)
{
 c->l = c->l->blink;
}

static void fhl_down(FHL *c)
{
 if (! c->f) abort();
 if (c->f->flags & FF_EXPANDED)
  { if (c->h)
     { if (c->h->flags & HF_EXPANDED)
	{ if (c->l)
	   { fhl_down_l(c);
	   }
	  else
	   { c->l = c->h->line_h;
	   }
	}
       else
	{ fhl_down_h(c);
	}
     }
    else
     { c->h = c->f->diff_h;
       while (c->h->flags & HF__HIDDEN) c->h = c->h->fflink;
     }
  }
 else
  { fhl_down_f(c);
  }
}

static void fhl_up(FHL *c)
{
 if (! c->f) abort();
 if (c->f->flags & FF_EXPANDED)
  { if (c->h)
     { if (c->h->flags & HF_EXPANDED)
	{ if (c->l)
	   { fhl_up_l(c);
	   }
	  else
	   { fhl_up_h(c);
	   }
	}
       else
	{ fhl_up_h(c);
	}
     }
    else
     { fhl_up_f(c);
     }
  }
 else
  { fhl_up_f(c);
  }
}

static void fhl_down_level(FHL *c)
{
 if (! c->f) abort();
 if ((c->f->flags & FF_EXPANDED) && c->h)
  { fhl_down_h(c);
  }
 else
  { fhl_down_f(c);
  }
}

static void fhl_up_level(FHL *c)
{
 if (! c->f) abort();
 if ((c->f->flags & FF_EXPANDED) && c->h)
  { if ((c->h->flags & HF_EXPANDED) && c->l)
     { c->l = 0;
     }
    else
     { fhl_up_h(c);
       c->l = 0;
     }
  }
 else
  { fhl_up_f(c);
    c->h = 0;
    c->l = 0;
  }
}

static void redraw_list(void)
{
 int y;
 FHL c;

 y = 0;
 c = top;
 while (c.f)
  { if (c.f->flags & FF_EXPANDED)
     { if (c.h)
	{ if (c.h->flags & HF_EXPANDED)
	   { if (c.l)
	      { if ((c.f == cur.f) && (c.h == cur.h) && (c.l == cur.l)) curline = y;
		line_line(y,c.l);
	      }
	     else
	      { if ((c.f == cur.f) && (c.h == cur.h) && !cur.l) curline = y;
		hunk_line(y,c.h);
	      }
	   }
	  else
	   { if ((c.f == cur.f) && (c.h == cur.h)) curline = y;
	     hunk_line(y,c.h);
	   }
	}
       else
	{ if ((c.f == cur.f) && !cur.h) curline = y;
	  file_line(y,c.f);
	}
     }
    else
     { if (c.f == cur.f) curline = y;
       file_line(y,c.f);
     }
    y ++;
    if (y >= LINES) break;
    fhl_down(&c);
  }
 clrtobot();
}

static void recenter(void)
{
 FHL t;
 FHL t2;
 int i;

 t = cur;
 for (i=(LINES-1)/2;i>0;i--)
  { t2 = t;
    fhl_up(&t2);
    if (! t2.f) break;
    t = t2;
  }
 top = t;
}

static char *new_temp_name(const char *dname, const char *s)
{
 char *name;

 asprintf(&name,"%s/.~%s~%x",dname,s,tempserial++);
 return(name);
}

static void open_temp_in_dir(const char *dname, const char *s, unsigned int mode, int *fdp, char **namep)
{
 char *name;
 int fd;

 while (1)
  { name = new_temp_name(dname,s);
    fd = open(name,O_RDWR|O_CREAT|O_EXCL,mode);
    if (fd >= 0)
     { *fdp = fd;
       *namep = name;
       return;
     }
    if (errno == EEXIST)
     { free(name);
       continue;
     }
    fatal("can't open temp file %s: %s",name,strerror(errno));
  }
}

static char hlt_char(HLT type)
{
 switch (type)
  { case HLT_COMMON: return(' '); break;
    case HLT_FROM:   return('-'); break;
    case HLT_TO:     return('+'); break;
  }
 abort();
}

static MEMSTREAM *gen_applied_file(FIL *f)
{
 HUNK *h;
 HUNKLINE *l;
 int fln;
 int fx;
 unsigned char *nl;
 int ll;
 MEMSTREAM *ms;

 ms = memstream_open_w();
 h = f->diff_h;
 if (f->contents_len == 0)
  { if (h->fflink) fatal("multiple patches to an empty file %s",f->escname);
    if (h->fn != 0) fatal("patch deletes from an empty file %s",f->escname);
    if (h->flags & (HF_APPLIED|HF_SELECTED))
     { for (l=h->line_h;l;l=l->flink)
	{ if (l->type != HLT_TO) fatal("non-+ line in patch to empty file %s",f->escname);
	  memstream_append(ms,l->text,strlen(l->text));
	  memstream_append(ms,"\n",1);
	}
     }
  }
 else
  { fln = 1;
    fx = 0;
    while (h && ((h->flags & (HF_APPLIED|HF_SELECTED)) == 0)) h = h->fflink;
    l = h ? h->line_h : 0;
    while (1)
     { if (h && !l)
	{ do h = h->fflink; while (h && ((h->flags & (HF_APPLIED|HF_SELECTED)) == 0));
	  l = h ? h->line_h : 0;
	}
       else if (!h || (fln < h->fl))
	{ if (fx >= f->contents_len) break;
	  nl = memchr(f->contents+fx,'\n',f->contents_len-fx);
	  if (! nl) abort();
	  nl ++;
	  memstream_append(ms,f->contents+fx,nl-(f->contents+fx));
	  fln ++;
	  fx = nl - f->contents;
	}
       else
	{ switch (l->type)
	   { default:
		abort();
		break;
	     case HLT_COMMON:
	     case HLT_FROM:
		if (fx >= f->contents_len)
		 { fatal("diff overflows file (%s, hunk %s)",f->escname,h->hdrline);
		 }
		nl = memchr(f->contents+fx,'\n',f->contents_len-fx);
		if (! nl) abort();
		ll = nl - (f->contents + fx);
		if ( (ll != strlen(l->text)) ||
		     bcmp(l->text,f->contents+fx,ll) )
		 { fatal("diff line doesn't match file line (%s, line %d, hunk %s)\n",
				f->escname, fln, h->hdrline);
		 }
		nl ++;
		if (l->type == HLT_COMMON) memstream_append(ms,f->contents+fx,nl-(f->contents+fx));
		fln ++;
		fx = nl - f->contents;
		break;
	     case HLT_TO:
		memstream_append(ms,l->text,strlen(l->text));
		memstream_append(ms,"\n",1);
		break;
	   }
	  l = l->flink;
	}
     }
  }
 return(ms);
}

static FILE *fopen_info_file(char **namep)
{
 int fd;
 char *name;

 open_temp_in_dir(".","info",0644,&fd,&name);
 *namep = name;
 return(fdopen(fd,"w"));
}

static int fhl_equal(FHL a, FHL b)
{
 if (a.f != b.f) return(0);
 if (!a.f || !(a.f->flags & FF_EXPANDED)) return(1);
 if (a.h != b.h) return(0);
 if (!a.h || !(a.h->flags & HF_EXPANDED)) return(1);
 if (a.l != b.l) return(0);
 return(1);
}

static void cmd_down(void)
{
 FHL ct;

 ct = cur;
 fhl_down(&ct);
 if (ct.f) cur = ct;
}

static void cmd_up(void)
{
 FHL ct;

 ct = cur;
 fhl_up(&ct);
 if (ct.f) cur = ct;
}

static void cmd_down_screen(void)
{
 FHL t;
 int i;
 int match;

 t = top;
 match = fhl_equal(t,cur);
 for (i=(LINES*4)/5;i>0;i--)
  { fhl_down(&t);
    if (! t.f) break;
    top = t;
    if (match) cur = t; else if (fhl_equal(t,cur)) match = 1;
  }
}

static void cmd_up_screen(void)
{
 FHL t;
 FHL last;
 int i;

 t = top;
 for (i=(LINES*4)/5;i>0;i--)
  { fhl_up(&t);
    if (! t.f) break;
    top = t;
  }
 t = top;
 for (i=LINES;t.f&&(i>0);i--)
  { if (fhl_equal(t,cur)) return;
    last = t;
    fhl_down(&t);
  }
 cur = last;
}

static void cmd_down_level(void)
{
 FHL ct;

 ct = cur;
 fhl_down_level(&ct);
 if (ct.f) cur = ct;
}

static void cmd_up_level(void)
{
 FHL ct;

 ct = cur;
 fhl_up_level(&ct);
 if (ct.f) cur = ct;
}

static void cmd_close(void)
{
 if (cur.f->flags & FF_EXPANDED)
  { if (cur.h)
     { if (cur.h->flags & HF_EXPANDED)
	{ if (cur.l)
	   { cur.l = 0;
	   }
	  else
	   { cur.h->flags &= ~HF_EXPANDED;
	   }
	}
       else
	{ cur.h = 0;
	}
     }
    else
     { cur.f->flags &= ~FF_EXPANDED;
     }
  }
}

static void cmd_open(void)
{
 if (cur.f->flags & FF_EXPANDED)
  { if (cur.h)
     { if (cur.h->flags & HF_EXPANDED)
	{ if (! cur.l) cur.l = cur.h->line_h;
	}
       else
	{ cur.h->flags |= HF_EXPANDED;
	  cur.l = 0;
	}
     }
    else
     { cur.h = cur.f->diff_h;
       cur.l = 0;
     }
  }
 else
  { cur.f->flags |= FF_EXPANDED;
    cur.h = 0;
  }
}

static void cmd_seltoggle(void)
{
 if ((cur.f->flags & FF_EXPANDED) && cur.h)
  { cur.h->flags ^= HF_SELECTED;
  }
 else
  { beep();
  }
}

static int permitted_commit(void)
{
 FIL *f;
 HUNK *h;

 for (f=file_h;f;f=f->flink)
  { for (h=f->diff_h;h;h=h->fflink)
     { if ( h->splitfrom &&
	    h->fflink &&
	    (h->fflink->splitfrom == h->splitfrom) )
	{ if (!(h->flags & HF_APPLIED) && (h->fflink->flags & HF_APPLIED)) fatal("impossible split-up application");
	  if (!(h->flags & (HF_SELECTED|HF_APPLIED)) && (h->fflink->flags & HF_SELECTED)) return(0);
	}
     }
  }
 return(1);
}

static void cmd_commit(void)
{
 FIL *f;
 HUNK *h;
 unsigned int fl;
 FHL t;
 FILE *lf;
 char *infofn;
 GITFI *gfi;
 MEMSTREAM *ms;

 if (! permitted_commit())
  { beep();
    return;
  }
 ui_save();
 lf = fopen_info_file(&infofn);
 setbuf(lf,0);
 fprintf(lf,"starting git fast-import\n");
 gfi = git_fast_import_start();
 for (f=file_h;f;f=f->flink)
  { fprintf(lf,"generating patched %s...",f->escname);
    ms = gen_applied_file(f);
    fprintf(lf,"feeding to git fast-import...");
    git_fast_import_file(gfi,f->escname,f->mode,ms);
    fprintf(lf,"freeing...\n");
    memstream_free(ms);
    fprintf(lf,"done\n");
  }
 fprintf(lf,"finishing git fast-import\n");
 git_fast_import_finish(gfi);
 fprintf(lf,"running git commit...");
 if (git_commit())
  { fprintf(lf,"success\n");
    for (h=hunk_h;h;h=h->aflink)
     { if (h->flags & HF_SELECTED) h->flags = (h->flags & ~HF_SELECTED) | HF_APPLIED;
     }
    for (f=file_h;f;f=f->flink)
     { fl = HF_APPLIED;
       for (h=f->diff_h;h;h=h->fflink) fl &= h->flags;
       if (fl & HF_APPLIED) f->flags = (f->flags & ~FF_EXPANDED) | FF_ALLAPPLIED;
     }
    if ( (cur.f->flags & FF_ALLAPPLIED) ||
	 ( (cur.f->flags & FF_EXPANDED) &&
	   cur.h &&
	   (cur.h->flags & HF_APPLIED) ) )
     { t = cur;
       if ( (t.f->flags & FF_EXPANDED) &&
	    t.h &&
	    (t.h->flags & HF_EXPANDED) ) t.l = t.h->line_t;
       fhl_down(&t);
       if (! t.f)
	{ t = cur;
	  t.l = 0;
	  fhl_up(&t);
	  if (! t.f)
	   { unlink(infofn);
	     printf("All hunks applied!\n");
	     exit(0);
	   }
	}
       cur = t;
     }
    if ( (top.f->flags & FF_ALLAPPLIED) ||
	 ( (top.f->flags & FF_EXPANDED) &&
	   top.h &&
	   (top.h->flags & HF_APPLIED) ) )
     { recenter();
     }
  }
 else
  { fprintf(lf,"failed\n");
  }
 fclose(lf);
 unlink(infofn);
 ui_restore();
}

static int run_editor(const char *fn)
{
 const char *editor;
 PROC *p;
 int status;

 editor = getenv("EDITOR");
 if (! editor) editor = "vi";
 p = proc_start(PROC_N,2,editor,fn,PROC_END);
 status = proc_await(p);
 return(WIFEXITED(status)&&(WEXITSTATUS(status)==0));
}

static void free_hunk_and_lines(HUNK *h)
{
 HUNKLINE *l;

 while ((l = h->line_h))
  { h->line_h = l->flink;
    free(l->text);
    free(l);
  }
 free(h->hdrline);
 free(h);
}

static void gen_hdrline(HUNK *h)
{
 asprintf(&h->hdrline,"@@ -%d,%d +%d,%d @@%s",h->fl,h->fn,h->tl,h->tn,h->splitfrom?" (split)":"");
}

static HUNK *read_hunk(FILE *f, HUNK *basis)
{
 HUNK *h;
 HUNKLINE *hl;
 unsigned char *lb;
 int la;
 int ll;
 int c;
 int lwh;
 HLT lt;

 void l_append(int ch)
  { if (ll >= la) lb = realloc(lb,la=ll+8);
    lb[ll++] = ch;
  }

 h = new_hunk();
 lwh = 0;
 lb = 0;
 la = 0;
 do <"done">
  { do <"err">
     { while <"lines"> (1)
	{ ll = 0;
	  while (1)
	   { c = getc(f);
	     if (c < 0)
	      { if (ll == 0) break <"lines">;
		break;
	      }
	     if (c == '\n') break;
	     l_append(c);
	   }
	  l_append('\0');
	  ll --;
	  hl = malloc(sizeof(HUNKLINE));
	  switch (lb[0])
	   { default:
		fprintf(stderr,"%s: invalid line type character `%c' in edited diff\n",__progname,lb[0]);
		fprintf(stderr,"%s: line is: %s\n",__progname,lb);
		break <"err">;
	     case '\0':
		fprintf(stderr,"%s: empty line in edited diff\n",__progname);
		break <"err">;
	     case '#':
		break;
	     case ' ':
		lt = HLT_COMMON;
		if (0)
		 {
	     case '-':
		   lt = HLT_FROM;
		 }
		if (0)
		 {
	     case '+':
		   lt = HLT_TO;
		 }
		hl = malloc(sizeof(HUNKLINE));
		hl->flink = 0;
		hl->blink = h->line_t;
		h->line_t = hl;
		if (hl->blink) hl->blink->flink = hl; else h->line_h = hl;
		hl->h = h;
		hl->l = lwh++;
		hl->type = lt;
		hl->text = strdup(lb+1);
		break;
	   }
	  ll = 0;
	}
       break <"done">;
     } while (0);
    free_hunk_and_lines(h);
    h = 0;
  } while (0);
 free(lb);
 if (h)
  { h->f = basis->f;
    h->flags = basis->flags;
    h->fl = basis->fl;
    h->tl = basis->tl;
    for (hl=h->line_h;hl;hl=hl->flink)
     { switch (hl->type)
	{ default:
	     abort();
	     break;
	  case HLT_COMMON:
	     h->fn ++;
	     h->tn ++;
	     break;
	  case HLT_FROM:
	     h->fn ++;
	     break;
	  case HLT_TO:
	     h->tn ++;
	     break;
	}
     }
    gen_hdrline(h);
  }
 return(h);
}

static int hunks_match(HUNK *h1, HUNK *h2, HUNKLINE **lp1, HUNKLINE **lp2)
{
 HUNKLINE *l1;
 HUNKLINE *l2;

 l1 = h1->line_h;
 l2 = h2->line_h;
 while (1)
  { while (l1 && (l1->type == HLT_TO)) l1 = l1->flink;
    while (l2 && (l2->type == HLT_TO)) l2 = l2->flink;
    if (!l1 && !l2) return(1);
    if (!l1 || !l2) break;
    if (strcmp(l1->text,l2->text)) break;
    l1 = l1->flink;
    l2 = l2->flink;
  }
 if (lp1) *lp1 = l1;
 if (lp2) *lp2 = l2;
 return(0);
}

static void load_hunk_lines(HUNKLINE *l, char **v, int vn)
{
 int i;

 i = 0;
 for (;l;l=l->flink)
  { if (l->type == HLT_FROM) continue;
    if (i >= vn) abort();
    v[i++] = l->text;
  }
 if (i != vn) abort();
}

#ifdef DIFF_DETAIL
#define f difftracef
static FILE *f;
#endif

static void do_diff(char **al, int an, char *acv, char **bl, int bn, char *bcv)
{
 int *cv[an];
 int cvdata[an*bn];
 int i;

 int search(int a, int b, int setc)
  {
#ifdef DIFF_DETAIL
    static int depth = 0;
    fprintf(f,"%*ssearch %d %d %d\n",depth,"",a,b,setc);
#endif
    if (a < 1)
     { if (b < 1)
	{
#ifdef DIFF_DETAIL
	  fprintf(f,"%*sreturn 0 [corner]\n",depth,"");
#endif
	  return(0);
	}
       else
	{ if (setc)
	   {
#ifdef DIFF_DETAIL
	     static int j;
	     for (j=b-1;j>=0;j--)
	      { fprintf(f,"bcv[%d] = 0\n",j);
		bcv[j] = 0;
	      }
#else
	     bzero(bcv,b);
#endif
	   }
#ifdef DIFF_DETAIL
	  fprintf(f,"%*sreturn %d [edge]\n",depth,"",b);
#endif
	  return(b);
	}
     }
    else
     { if (b < 1)
	{ if (setc)
	   {
#ifdef DIFF_DETAIL
	     static int j;
	     for (j=a-1;j>=0;j--)
	      { fprintf(f,"acv[%d] = 0\n",j);
		acv[j] = 0;
	      }
#else
	     bzero(acv,a);
#endif
	   }
#ifdef DIFF_DETAIL
	  fprintf(f,"%*sreturn %d [edge]\n",depth,"",a);
#endif
	  return(a);
	}
       else
	{ int v;
	  int v2;
	  v = cv[a-1][b-1];
	  if ((v >= 0) && !setc)
	   {
#ifdef DIFF_DETAIL
	     fprintf(f,"%*sreturn %d [memo]\n",depth,"",v);
#endif
	     return(v);
	   }
	  if (! strcmp(al[a-1],bl[b-1]))
	   {
#ifdef DIFF_DETAIL
	     fprintf(f,"%*sequal <%s>\n",depth,"",al[a-1]);
	     depth += 2;
#endif
	     v = search(a-1,b-1,setc);
#ifdef DIFF_DETAIL
	     depth -= 2;
#endif
	     if (setc)
	      { acv[a-1] = 1;
		bcv[b-1] = 1;
#ifdef DIFF_DETAIL
		fprintf(f,"acv[%d] = 1\nbcv[%d] = 1\n",a-1,b-1);
#endif
	      }
	   }
	  else
	   {
#ifdef DIFF_DETAIL
	     fprintf(f,"%*sdiffer <%s> <%s>\n",depth,"",al[a-1],bl[b-1]);
	     depth += 2;
#endif
	     v = search(a-1,b,0) + 1;
#ifdef DIFF_DETAIL
	     fprintf(f,"%*s----\n",depth-2,"");
#endif
	     v2 = search(a,b-1,0) + 1;
#ifdef DIFF_DETAIL
	     depth -= 2;
	     fprintf(f,"%*svalues are %d %d\n",depth,"",v,v2);
#endif
	     if (v2 < v)
	      { v = v2;
		if (setc)
		 {
#ifdef DIFF_DETAIL
		   fprintf(f,"%*ssetc, using second choice\n",depth,"");
		   depth += 2;
#endif
		   search(a,b-1,1);
#ifdef DIFF_DETAIL
		   depth -= 2;
		   fprintf(f,"bcv[%d] = 0\n",b-1);
#endif
		   bcv[b-1] = 0;
		 }
	      }
	     else
	      { if (setc)
		 {
#ifdef DIFF_DETAIL
		   fprintf(f,"%*ssetc, using first choice\n",depth,"");
		   depth += 2;
#endif
		   search(a-1,b,1);
#ifdef DIFF_DETAIL
		   depth -= 2;
		   fprintf(f,"acv[%d] = 0\n",a-1);
#endif
		   acv[a-1] = 0;
		 }
	      }
	   }
#ifdef DIFF_DETAIL
	  fprintf(f,"%*sreturn %d [&save]\n",depth,"",v);
#endif
	  cv[a-1][b-1] = v;
	  return(v);
	}
     }
  }

 for (i=(an*bn)-1;i>=0;i--) cvdata[i] = -1;
 for (i=an-1;i>=0;i--) cv[i] = &cvdata[i*bn];
 search(an,bn,1);
}

#ifdef DIFF_DETAIL
static void dump_diffs(FILE *f, char **l, char *c, int n, const char *p)
{
 int i;

 fprintf(f,"%scomm\t%slines\n",p,p);
 for (i=0;i<n;i++) fprintf(f,"%d\t%s\n",c[i],l[i]);
}
#endif

static HUNK *intermediate_hunk(HUNK *a, HUNK *b)
{
 char *alines[a->tn];
 char *blines[b->tn];
 char acomm[a->tn];
 char bcomm[b->tn];
 int i;
 int j;
 HUNKLINE *hl;
 HUNK *h;
 HLT lt;
 const char *txt;
 int lwh;

#ifdef DIFF_DETAIL
 f = fopen("z.fnord","w");
#endif
 load_hunk_lines(a->line_h,&alines[0],a->tn);
 load_hunk_lines(b->line_h,&blines[0],b->tn);
 memset(&acomm[0],2,a->tn);
 memset(&bcomm[0],2,b->tn);
 do_diff(&alines[0],a->tn,&acomm[0],&blines[0],b->tn,&bcomm[0]);
#ifdef DIFF_DETAIL
 dump_diffs(f,&alines[0],&acomm[0],a->tn,"a");
 fprintf(f,"\n");
 dump_diffs(f,&blines[0],&bcomm[0],b->tn,"b");
 fclose(f);
#undef f
#endif
 if (memchr(&acomm[0],2,a->tn)) abort();
 if (memchr(&bcomm[0],2,b->tn)) abort();
 h = new_hunk();
 i = 0;
 j = 0;
 if ((a->f != b->f) || (a->fl != b->fl) || (a->tl != b->tl)) abort();
 h->f = a->f;
 h->flags = a->flags;
 h->fl = a->fl;
 h->tl = a->tl;
 lwh = 0;
 while ((i < a->tn) || (j < b->tn))
  { if ((i < a->tn) && !acomm[i])
     { lt = HLT_FROM;
       txt = alines[i];
       h->fn ++;
       i ++;
     }
    else if ((j < b->tn) && !bcomm[j])
     { lt = HLT_TO;
       txt = blines[j];
       h->tn ++;
       j ++;
     }
    else
     { if ((i >= a->tn) || (j >= b->tn) || !acomm[i] || !bcomm[j]) abort();
       if (strcmp(alines[i],blines[j])) abort();
       lt = HLT_COMMON;
       txt = alines[i];
       h->fn ++;
       h->tn ++;
       i ++;
       j ++;
     }
    hl = malloc(sizeof(HUNKLINE));
    hl->h = h;
    hl->l = lwh++;
    hl->type = lt;
    hl->text = strdup(txt);
    hl->flink = 0;
    hl->blink = h->line_t;
    if (hl->blink) hl->blink->flink = hl; else h->line_h = hl;
    h->line_t = hl;
  }
 if ((h->fn != a->tn) || (h->tn != b->tn)) abort();
 gen_hdrline(h);
 return(h);
}

static void split_hunk(void)
{
 char *tempfn;
 int fd;
 FILE *fp;
 HUNKLINE *l;
 HUNKLINE *l2;
 HUNK *h;
 HUNK *h2;
 int iresp;

 if (!(cur.f->flags & FF_EXPANDED) || !cur.h)
  { beep();
    return;
  }
 if (cur.h->flags & HF__HIDDEN) abort();
 ui_save();
 open_temp_in_dir(".","split",0644,&fd,&tempfn);
 fp = fdopen(fd,"r+");
 rewind(fp);
 for (l=cur.h->line_h;l;l=l->flink)
  { switch (l->type)
     { default:
	  abort();
	  break;
       case HLT_COMMON:
       case HLT_FROM:
       case HLT_TO:
	  putc(hlt_char(l->type),fp);
	  break;
     }
    fprintf(fp,"%s\n",l->text);
  }
 fclose(fp);
 while <"edit"> (1)
  { if (run_editor(tempfn))
     { fd = open(tempfn,O_RDONLY,0);
       if (fd < 0)
	{ switch (errno)
	   { case EEXIST:
		printf("Editor destroyed %s\n",tempfn);
		break;
	     case EACCES:
		printf("Editor revoked read access to %s\n",tempfn);
		break;
	     default:
		printf("Can't reopen %s: %s\n",tempfn,strerror(errno));
		break;
	   }
	  exit(1);
	}
       do <"err">
	{ fp = fdopen(fd,"r");
	  h = read_hunk(fp,cur.h);
	  if (! h) break <"err">;
	  if (! hunks_match(h,cur.h,&l,&l2))
	   { printf("Old text doesn't match:\n");
	     if (l)
	      { printf("  edited hunk: %c%s\n",hlt_char(l->type),l->text);
	      }
	     else
	      { printf("  edited hunk ends\n");
	      }
	     if (l2)
	      { printf("original hunk: %c%s\n",hlt_char(l2->type),l2->text);
	      }
	     else
	      { printf("original hunk ends\n");
	      }
	     break <"err">;
	   }
	  h2 = intermediate_hunk(h,cur.h);
	  h->aflink = h2;
	  h2->aflink = cur.h->aflink;
	  h->ablink = cur.h->ablink;
	  h2->ablink = h;
	  h->fflink = h2;
	  h2->fflink = cur.h->fflink;
	  h->fblink = cur.h->fblink;
	  h2->fblink = h;
	  if (cur.h->ablink) cur.h->ablink->aflink = h; else hunk_h = h;
	  if (cur.h->aflink) cur.h->aflink->ablink = h2; else hunk_t = h2;
	  if (cur.h->fblink) cur.h->fblink->fflink = h; else cur.h->f->diff_h = h;
	  if (cur.h->fflink) cur.h->fflink->fblink = h2; else cur.h->f->diff_t = h2;
	  if (cur.h->splitfrom)
	   { h->splitfrom = cur.h->splitfrom;
	     h2->splitfrom = cur.h->splitfrom;
	     free_hunk_and_lines(cur.h);
	   }
	  else
	   { cur.h->flags = HF_SPLIT; /* drop other flags */
	     cur.h->ablink = h->ablink;
	     cur.h->aflink = h;
	     if (h->ablink) h->ablink->aflink = cur.h; else hunk_h = cur.h;
	     h->ablink = cur.h;
	     h->splitfrom = cur.h;
	     h2->splitfrom = cur.h;
	   }
	  cur.h = h;
	  cur.l = h->line_h;
	  break <"edit">;
	} while (0);
       if (h) free_hunk_and_lines(h);
       while (1)
	{ printf("<r>e-edit or <d>iscard edits? ");
	  fpurge(stdin);
	  iresp = getchar();
	  fpurge(stdin);
	  switch (iresp)
	   { case 'r': case 'R':
		continue <"edit">;
		break;
	     case 'd': case 'D':
	     case EOF:
		break <"edit">;
	   }
	}
     }
  }
 unlink(tempfn);
 ui_restore();
}

static HUNK *do_merge(HUNK *a, HUNK *b)
{
 HUNK *new;
 HUNKLINE *al;
 HUNKLINE *bl;
 int lwh;

 void new_line(HLT t, HUNKLINE *src)
  { HUNKLINE *nl;
    nl = malloc(sizeof(HUNKLINE));
    nl->flink = 0;
    nl->blink = new->line_t;
    new->line_t = nl;
    if (nl->blink) nl->blink->flink = nl; else new->line_h = nl;
    nl->h = new;
    nl->l = lwh++;
    nl->type = t;
    nl->text = strdup(src->text);
    switch (t)
     { case HLT_COMMON: new->fn ++; new->tn ++; break;
       case HLT_FROM:   new->fn ++;             break;
       case HLT_TO:                 new->tn ++; break;
       default: abort(); break;
     }
  }

 if ( (a->aflink != b) ||
      (a != b->ablink) ||
      (a->fflink != b) ||
      (a != b->fblink) ||
      (a->f != b->f) ||
      !a->splitfrom ||
      (a->splitfrom != b->splitfrom) ) abort();
 new = new_hunk();
 lwh = 0;
 al = a->line_h;
 bl = b->line_h;
 while (1)
  { while (al && (al->type == HLT_FROM))
     { new_line(HLT_FROM,al);
       al = al->flink;
     }
    while (bl && (bl->type == HLT_TO))
     { new_line(HLT_TO,bl);
       bl = bl->flink;
     }
    if (!al && !bl) break;
    if (!al || !bl || strcmp(al->text,bl->text))
     { void dump_hunk(HUNK *h)
	{ HUNKLINE *l;
	  printf("    %s @@ -%d,%d +%d,%d\n",h->f->escname,h->fl,h->fn,h->tl,h->tn);
	  for (l=h->line_h;l;l=l->flink) printf("\t%c%s\n",hlt_char(l->type),l->text);
	}
       ui_abort();
       printf("do_merge: hunks don't match\nhunk 1:\n");
       dump_hunk(a);
       printf("hunk 2:\n");
       dump_hunk(b);
       exit(1);
     }
    switch (al->type)
     { case HLT_COMMON:
	  switch (bl->type)
	   { case HLT_COMMON:
		new_line(HLT_COMMON,al);
		break;
	     case HLT_FROM:
		new_line(HLT_FROM,al);
		break;
	     default:
		abort();
		break;
	   }
	  break;
       case HLT_TO:
	  switch (bl->type)
	   { case HLT_COMMON:
		new_line(HLT_TO,al);
		break;
	     case HLT_FROM:
		break;
	     default:
		abort();
		break;
	   }
	  break;
       default:
	  abort();
	  break;
     }
    al = al->flink;
    bl = bl->flink;
  }
 new->fl = a->fl;
 new->tl = a->tl;
 gen_hdrline(new);
 new->f = a->f;
 new->flags = (a->flags | b->flags) & HF_EXPANDED;
 new->splitfrom = a->splitfrom;
 new->ablink = a->ablink;
 new->aflink = b->aflink;
 if (new->ablink) new->ablink->aflink = new; else hunk_h = new;
 if (new->aflink) new->aflink->ablink = new; else hunk_t = new;
 new->fblink = a->fblink;
 new->fflink = b->fflink;
 if (new->fblink) new->fblink->fflink = new; else a->f->diff_h = new;
 if (new->fflink) new->fflink->fblink = new; else a->f->diff_t = new;
 free_hunk_and_lines(a);
 free_hunk_and_lines(b);
 return(new);
}

static int hunks_identical(HUNK *a, HUNK *b)
{
 HUNKLINE *al;
 HUNKLINE *bl;

 if ( (a->fl != b->fl) || (a->fn != b->fn) ||
      (a->tl != b->tl) || (a->tn != b->tn) ) return(0);
 al = a->line_h;
 bl = b->line_h;
 while (1)
  { if (!al && !bl) break;
    if (!al || !bl) return(0);
    if (al->type != bl->type) return(0);
    if (strcmp(al->text,bl->text)) return(0);
    al = al->flink;
    bl = bl->flink;
  }
 return(1);
}

static void cmd_mergesplit(void)
{
 if (!(cur.f->flags & FF_EXPANDED) || !cur.h)
  { beep();
    return;
  }
 if (cur.h == merging)
  { merging = 0;
    return;
  }
 if (cur.h->flags & HF__HIDDEN) abort();
 if (merging)
  { if (merging->flags & HF__HIDDEN) abort();
    if ((cur.h->flags ^ merging->flags) & HF_SELECTED)
     { beep();
       return;
     }
    if (cur.h->splitfrom != merging->splitfrom)
     { beep();
     }
    else if (cur.h->fflink == merging)
     { cur.h = do_merge(cur.h,merging);
       cur.l = 0;
       merging = 0;
     }
    else if (merging->fflink == cur.h)
     { cur.h = do_merge(merging,cur.h);
       cur.l = 0;
       merging = 0;
     }
    else
     { beep();
     }
    if ( !merging &&
	 (!cur.h->fblink || (cur.h->fblink->splitfrom != cur.h->splitfrom)) &&
	 (!cur.h->fflink || (cur.h->fflink->splitfrom != cur.h->splitfrom)) )
     { HUNK *h;
       h = cur.h->splitfrom;
       if (! hunks_identical(cur.h,h)) abort();
       if (h->aflink) h->aflink->ablink = h->ablink; else hunk_t = h->ablink;
       if (h->ablink) h->ablink->aflink = h->aflink; else hunk_h = h->aflink;
       free_hunk_and_lines(h);
       cur.h->splitfrom = 0;
       free(cur.h->hdrline);
       gen_hdrline(cur.h);
     }
  }
 else
  { if (cur.h->splitfrom)
     { merging = cur.h;
     }
    else
     { beep();
     }
  }
}

HUNK *new_hunk(void)
{
 HUNK *h;

 h = malloc(sizeof(HUNK));
 h->aflink = 0;
 h->ablink = 0;
 h->fflink = 0;
 h->fblink = 0;
 h->f = 0;
 h->flags = 0;
 h->splitfrom = 0;
 h->hdrline = 0;
 h->fl = 0;
 h->fn = 0;
 h->tl = 0;
 h->tn = 0;
 h->line_h = 0;
 h->line_t = 0;
 return(h);
}

void ui_main_loop(void)
{
 int c;

 ui_setup();
 top.f = file_h;
 cur = top;
 while (1)
  { curline = -1;
    redraw_list();
    if (curline < 0)
     { recenter();
       continue;
     }
    else
     { move(curline,0);
     }
    refresh();
    c = getch();
    switch (c)
     { case 'j':
	  cmd_down();
	  break;
       case 'k':
	  cmd_up();
	  break;
       case 'J':
	  cmd_down_level();
	  break;
       case 'K':
	  cmd_up_level();
	  break;
       case 'h':
	  cmd_close();
	  break;
       case 'l':
	  cmd_open();
	  break;
       case 'm':
	  cmd_mergesplit();
	  break;
       case 'a':
	  cmd_seltoggle();
	  break;
       case 'C':
	  cmd_commit();
	  break;
       case 'S':
	  split_hunk();
	  break;
       case ' ':
       case 'f':
	  cmd_down_screen();
	  break;
       case 'b':
	  cmd_up_screen();
	  break;
     }
  }
}