fnc

**fnc 0.9** 2022-03-04

- Add blame command `--line` option to open annotated file at the specified line
- merge upstream libfossil changes that eliminate gcc compiler warnings
- adopt libfossil diff v1 implementation into fnc tree to replace v2 API
- refactor diff implementation to comport with code style
- fix `--whitespace` option (`w` keymap) diffv2 regression from 0.7 [105123b40e]
- implement diff `--line-numbers` opt (`L` keymap) to display file line numbers
- implement display of enclosing function in diff chunk headers (enabled by  
  default like CVS and Git, disabled with `--no-prototype` or `p` keymap); works  
  with all C-like languages, but not Lisps or markup languages
- upstream libfossil fix for segv bug when fsl_int_d and fsl_id_t differ in size
- fix incorrect malloc producing undefined behaviour on 32-bit platforms
- add unveil (c)reate permission to the checkout dir to fix some diff commands
- change conflicting diff and blame view key maps
- implement taggable timeline nodes to interactively diff arbitrary commits
- implement `C` timeline keymap to diff selected commit against local changes
- clean code of OS-dependent ifdefs by consolidating them in called functions
- add support for landlock Linux security module in Linux builds
- significant diff driver refactoring for finer granularity in view manipulation
- implement `--sbs` (`S` keymap) to display side-by-side formatted diffs
- add FNC_COLOUR_DIFF_SBS_EDIT option to set colour of edited lines in SBS diff 
- plug small memory leak when interactively changing diff format

**fnc 0.8** 2022-01-10

- fix vertical split
- fix vertical split view init regression from 0.7 when terminal < 120 cols wide 
- fix DB lock when opening horizontal split that signals the timeline thread

**fnc 0.7** 2022-01-09

- factor out common make(1) and gmake build bits
- make build depend on make file
- make all commands compatible with `-R|--repository` (i.e., no checkout needed)

# README

# fnc 0.7
# fnc 0.9

## An interactive ncurses browser for [Fossil][0] repositories.

`fnc` uses [libfossil][1] to create a [`fossil ui`][2] experience in the
terminal.

Tested and confirmed to run on the following amd64 systems (additional platforms

#
# FNC Common Build
#

# CONFIGURATION
CC ?=		cc
PREFIX ?=	/usr/local
MANDIR ?=	/share/man
VERSION ?=	0.8
VERSION ?=	0.9

# FLAGS NEEDED TO BUILD SQLITE3
SQLITE_CFLAGS =	${CFLAGS} -Wall -Werror -Wno-sign-compare -pedantic -std=c99 \
		-DNDEBUG=1 \
		-DSQLITE_DQS=0 \
		-DSQLITE_THREADSAFE=0 \
		-DSQLITE_DEFAULT_MEMSTATUS=0 \
		-DSQLITE_DEFAULT_WAL_SYNCHRONOUS=1 \
		-DSQLITE_LIKE_DOESNT_MATCH_BLOBS \
		-DSQLITE_OMIT_DECLTYPE \
		-DSQLITE_OMIT_PROGRESS_CALLBACK \
		-DSQLITE_OMIT_SHARED_CACHE \
		-DSQLITE_OMIT_LOAD_EXTENSION \

lib/sqlite3.o: lib/sqlite3.c lib/sqlite3.h
	${CC} ${SQLITE_CFLAGS} -c $< -o $@

lib/libfossil.o: lib/libfossil.c lib/libfossil.h
	${CC} ${FOSSIL_CFLAGS} -c $< -o $@

src/diff.o: src/diff.c include/diff.h
	${CC} ${FNC_CFLAGS} -c $< -o $@

src/fnc.o: src/fnc.c include/settings.h fnc.bld.mk
src/fnc.o: src/fnc.c include/settings.h include/diff.h fnc.bld.mk
	${CC} ${FNC_CFLAGS} -c $< -o $@

src/fnc: src/fnc.o lib/libfossil.o lib/sqlite3.o fnc.bld.mk
	${CC} -o $@ src/fnc.o lib/libfossil.o lib/sqlite3.o ${FNC_LDFLAGS}
src/fnc: src/fnc.o src/diff.o lib/libfossil.o lib/sqlite3.o fnc.bld.mk
	${CC} -o $@ src/fnc.o src/diff.o lib/libfossil.o lib/sqlite3.o \
	${FNC_LDFLAGS}

install:
	install -s -m 0755 src/fnc ${PREFIX}/bin/fnc
	install -m 0644 src/fnc.1 ${PREFIX}${MANDIR}/man1/fnc.1

uninstall:
	rm -f ${PREFIX}/bin/fnc ${PREFIX}${MANDIR}/man1/fnc.1

/*
 * Copyright (c) 2022 Mark Jamsek <mark@bsdbox.org>
 *
 * Permission to use, copy, modify, and distribute this software for any
 * purpose with or without fee is hereby granted, provided that the above
 * copyright notice and this permission notice appear in all copies.
 *
 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
 * ANY SPECIAL, DIRECT, 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.
 */

#include "libfossil.h"
#include "settings.h"

enum fnc_diff_flag {
	FNC_DIFF_IGNORE_EOLWS	= 0x01,
	FNC_DIFF_IGNORE_ALLWS	= 0x03,
	FNC_DIFF_SIDEBYSIDE	= 1 <<  2,
	FNC_DIFF_VERBOSE	= 1 <<  3,
	FNC_DIFF_BRIEF		= 1 <<  4,
	FNC_DIFF_HTML		= 1 <<  5,
	FNC_DIFF_LINENO		= 1 <<  6,
	FNC_DIFF_NOOPT		= 1 <<  7,  /* og. 0x0100 */
	FNC_DIFF_INVERT		= 1 <<  8,  /* og. 0x0200 */
	FNC_DIFF_NOTTOOBIG	= 1 <<  9,  /* og. 0x0800 */
	FNC_DIFF_STRIP_EOLCR	= 1 << 10,  /* og. 0x1000 */
	FNC_DIFF_ANSI_COLOR	= 1 << 11,  /* og. 0x2000 */
	FNC_DIFF_PROTOTYPE	= 1 << 12
#define FNC_DIFF_CONTEXT_EX	(((uint64_t)0x04) << 32)  /* Allow 0 context */
#define FNC_DIFF_CONTEXT_MASK	((uint64_t)0x0000ffff)    /* Default context */
#define FNC_DIFF_WIDTH_MASK	((uint64_t)0x0fff0000)    /* SBS column width */
};

struct diff_out_state {
	fsl_output_f	 out;		/* Output callback */
	void		*state;		/* State for this->out() */
	enum line_type	*lines;		/* Diff line type (e.g., minus, plus) */
	uint32_t	*idx;		/* Index into this->lines */
	int		 rc;		/* Error reporting */
	char		 ansi;		/* ANSI colour code */
	struct {
		const fsl_buffer	*file;		/* Diffed file */
		char			*signature;	/* Matching function */
		uint32_t		 lastmatch;	/* Match line index */
		uint32_t		 lastline;	/* Last line scanned */
		fsl_size_t		 offset;	/* Match byte offset */
	} proto;
};
static const struct diff_out_state diff_out_state_empty =
    { NULL, NULL, NULL, 0, 0, 0, { NULL, NULL, 0, 0, 0 } };

struct sbsline {
	struct diff_out_state	*output;
	fsl_buffer		*cols[5];	/* Pointers to output columns */
	const char		*tag;		/* <span> tag */
	const char		*tag2;		/* <span> tag */
	int			 idx;		/* Write tag before idx */
	int			 end;		/* Close tag before end */
	int			 idx2;		/* Write tag2 before idx2 */
	int			 end2;		/* Close tag2 before end2 */
	int			 width;		/* Max column width in diff */
	bool			 esc;		/* Escape html characters */
	void			*regex;		/* Colour matching lines */
};

int		 fnc_diff_text_raw(fsl_buffer const *, fsl_buffer const *,
		    int, int **);
int		 fnc_diff_text_to_buffer(fsl_buffer const *, fsl_buffer const *,
		    fsl_buffer *, enum line_type **, uint32_t *, short, short,
		    int );
int		 fnc_diff_text(fsl_buffer const *, fsl_buffer const *,
		    fsl_output_f, void *, short, short, int );
int		 fnc_diff_blobs(fsl_buffer const *, fsl_buffer const *,
		    fsl_output_f, void *, enum line_type **, uint32_t *,
		    uint16_t, short, int, int **);
int		 fnc_output_f_diff_out(void *, void const *, fsl_size_t);
int		 diff_outf(struct diff_out_state *, char const *, ... );
int		 diff_out(struct diff_out_state * const, void const *,
		    fsl_int_t);
char		*match_chunk_function(struct diff_out_state *const, uint32_t);
int		 buffer_copy_lines_from(fsl_buffer *const,
		    const fsl_buffer *const, fsl_size_t *, fsl_size_t,
		    fsl_size_t);
uint64_t	 fnc_diff_flags_convert(int);
int		 diff_context_lines(uint64_t);
int		 match_dline(fsl_dline *, fsl_dline *);
bool		 longest_common_subsequence(const char *z, int, const char *,
		    int, int *);
int		 unidiff(fsl__diff_cx *, struct diff_out_state *, void *,
		    uint16_t, uint64_t);
int		 unidiff_lineno(struct diff_out_state *, int, int, bool);
int		 unidiff_txt( struct diff_out_state *const, char, fsl_dline *,
		    int, void *);
int		 sbsdiff(fsl__diff_cx *, struct diff_out_state *, void *,
		    uint16_t, uint64_t);
int		 alloc_lines_and_width(fsl__diff_cx *, int *, uint16_t,
		    uint32_t, enum line_type **);
unsigned short	 etcount(const char *str, unsigned short n);
int		 sbsdiff_width(uint64_t);
int		 sbsdiff_separator(struct sbsline *, int, int);
int		 sbsdiff_lineno(struct sbsline *, int, int);
void		 sbsdiff_shift_left(struct sbsline *, const char *);
void		 sbsdiff_simplify_line(struct sbsline *, const char *);
int		 sbsdiff_column(struct diff_out_state *,
		    fsl_buffer const *, int);
int		 sbsdiff_txt(struct sbsline *, fsl_dline *, int);
int		 sbsdiff_newline(struct sbsline *);
int		 sbsdiff_space(struct sbsline *, int, int);
int		 sbsdiff_marker(struct sbsline *, const char *, const char *);
int		 sbsdiff_close_gap(int *);
unsigned char	*sbsdiff_align(fsl_dline *, int, fsl_dline *, int);
int		 sbsdiff_write_change(struct sbsline *, fsl_dline *, int,
		    fsl_dline *, int);

	_(pfx, COLOUR_USER),					\
	_(pfx, COLOUR_DATE),					\
	_(pfx, COLOUR_DIFF_META),				\
	_(pfx, COLOUR_DIFF_MINUS),				\
	_(pfx, COLOUR_DIFF_PLUS),				\
	_(pfx, COLOUR_DIFF_CHUNK),				\
	_(pfx, COLOUR_DIFF_TAGS),				\
	_(pfx, COLOUR_DIFF_SBS_EDIT),				\
	_(pfx, COLOUR_TREE_LINK),				\
	_(pfx, COLOUR_TREE_DIR),				\
	_(pfx, COLOUR_TREE_EXEC),				\
	_(pfx, COLOUR_BRANCH_OPEN),				\
	_(pfx, COLOUR_BRANCH_CLOSED),				\
	_(pfx, COLOUR_BRANCH_CURRENT),				\
	_(pfx, COLOUR_BRANCH_PRIVATE),				\

	_(pfx, MONO)

#define INPUT_TYPE_ENUM(pfx, _)					\
	_(pfx, ALPHA),						\
	_(pfx, NUMERIC)

#define LINE_TYPE_ENUM(pfx, _)					\
	_(pfx, BLANK),						\
	_(pfx, TIMELINE_HEADER),				\
	_(pfx, TIMELINE_COMMIT),				\
	_(pfx, DIFF_HEADER),					\
	_(pfx, DIFF_ARTIFACT),					\
	_(pfx, DIFF_USER),					\
	_(pfx, DIFF_TAGS),					\
	_(pfx, DIFF_DATE),					\
	_(pfx, DIFF_COMMENT),					\
	_(pfx, DIFF_CHANGESET),					\
	_(pfx, DIFF_INDEX),					\
	_(pfx, DIFF_META),					\
	_(pfx, DIFF_MINUS),					\
	_(pfx, DIFF_PLUS),					\
	_(pfx, DIFF_EDIT),					\
	_(pfx, DIFF_CONTEXT),					\
	_(pfx, DIFF_CHUNK),					\
	_(pfx, DIFF_SEPARATOR)

#define VIEW_MODE_ENUM(pfx, _)					\
	_(pfx, NONE),						\
	_(pfx, VERT),						\
	_(pfx, HRZN)

#define ENUM_INFO(_)						\

    }
  }
#endif
  else{
    char const * zLocalRoot;
    char const * zFull;
    fsl_size_t nLocalRoot;
    fsl_size_t nFull;
    fsl_size_t nFull = 0;
    fsl_buffer * const full = fsl__cx_scratchpad(f);
    int (*xCmp)(char const *, char const *,fsl_size_t);
    bool endsWithSlash;
    assert(f->ckout.dir);
    zLocalRoot = f->ckout.dir;
    assert(zLocalRoot);
    assert(*zLocalRoot);

  fsl__cx_scratchpad_yield(f, fname);
  return rc;
}

int fsl_card_F_ckout_mtime(fsl_cx * const f,
                           fsl_id_t vid,
                           fsl_card_F const * fc,
                           fsl_time_t * repoMtime,
                           fsl_time_t * localMtime){
                           fsl_time_t * const repoMtime,
                           fsl_time_t * const localMtime){

  int rc = 0;
  fsl_id_t fid = 0;
  fsl_fstat fst = fsl_fstat_empty;
  if(!fsl_needs_ckout(f)) return FSL_RC_NOT_A_CKOUT;
  if(0>=vid){
    fsl_ckout_version_info(f, &vid, NULL);

  fsl_cx * f = fcli.f;
  assert(f);
  if(fcli.transient.repoDbArg){
    FCLI_V3(("Trying to open repo db file [%s]...\n", fcli.transient.repoDbArg));
    rc = fsl_repo_open( f, fcli.transient.repoDbArg );
  }
  else if(fcli.clientFlags.checkoutDir){
    fsl_buffer dir = fsl_buffer_empty;
    char const * dirName = fcli.clientFlags.checkoutDir;
    FCLI_V3(("Trying to open checkout from [%s]...\n",
             dirName));
    rc = fsl_ckout_open_dir(f, dirName, true);
    FCLI_V3(("checkout open rc=%s\n", fsl_rc_cstr(rc)));

    /* if(FSL_RC_NOT_FOUND==rc) rc = FSL_RC_NOT_A_CKOUT; */
    if(rc){
      if(!fsl_cx_err_get(f,NULL,NULL)){
        rc = fsl_cx_err_set(f, rc, "Opening of checkout under "
                            "[%s] failed with code %d (%s).",
                            dirName, rc, fsl_rc_cstr(rc));
      }
    }
    fsl_buffer_reserve(&dir, 0);
    if(rc) return rc;
  }
  if(!rc){
    if(fcli.clientFlags.verbose>1){
      fsl_db * dbC = fsl_cx_db_ckout(f);
      fsl_db * dbR = fsl_cx_db_repo(f);
      if(dbC){

    assert('/' == f->ckout.dir[f->ckout.dirLen-1]);
    f->flags |= FSL_CX_F_IS_OPENING_CKOUT;
    rc = fsl_repo_open_for_ckout(f);
    f->flags &= ~FSL_CX_F_IS_OPENING_CKOUT;
    if(!rc) rc = fsl_cx_after_open(f);
    if(rc){
      /* Is this sane? Is not doing it sane? */
      fsl_ckout_close(f);
      fsl_close_scm_dbs(f);
    }
  }
  end:
  fsl__cx_scratchpad_yield(f, buf);
  fsl__cx_scratchpad_yield(f, bufD);
  return rc;
}

  if(0==rc){
    f->cache.isCrosslinking = true;
  }else{
    fsl_cx_transaction_end(f, true);
  }
  return rc;
}

int fsl_deck_foreach(fsl_cx * const f, fsl_satype_e type,
                     fsl_deck_visitor_f visitor,
                     void * visitorState){
  int rc = 0;
  fsl_stmt q = fsl_stmt_empty;
  switch(type){
    case FSL_SATYPE_CHECKIN:
    case FSL_SATYPE_FORUMPOST:
    case FSL_SATYPE_CONTROL:
      rc = fsl_cx_prepare(f, &q,
                          "SELECT objid FROM event WHERE type=%Q",
                          fsl_satype_event_cstr(type));
      break;
    case FSL_SATYPE_WIKI:
      rc = fsl_cx_prepare(f, &q,
                          "SELECT x.rid AS mrid FROM tag t, tagxref x "
                          "WHERE x.tagid=t.tagid "
                          "AND t.tagname LIKE 'wiki-%%' "
                          "AND TYPEOF(x.value+0)='integer'"
                          // ^^^^ only 'wiki-%' tags which are wiki pages
                          "ORDER BY x.mtime DESC");
      break;
    case FSL_SATYPE_TICKET:
      rc = fsl_cx_prepare(f, &q,
                          "SELECT rid FROM tagxref WHERE tagid IN "
                          "(SELECT tagid FROM tag WHERE tagname LIKE "
                          "'tkt-%%' AND LENGTH(tagname)=44) "
                          "ORDER BY mtime");
      break;
    case FSL_SATYPE_TECHNOTE:
      rc = fsl_cx_prepare(f, &q,
                          "SELECT x.rid AS mrid FROM tag t, tagxref x "
                          "WHERE x.tagid=t.tagid "
                          "AND t.tagname LIKE 'event-%%' "
                          // ^^^^ only 'wiki-%' tags which are wiki pages
                          "ORDER BY x.mtime DESC");
      break;
#if 0
    case FSL_SATYPE_ANY:
      /* This case leads to confusion because ATTACHMENT records are
         recorded in the timeline as the underlying type of record to
         which the attachment is applied. e.g. an attachment on a wiki
         page is listed as a 'w' event. */
      rc = fsl_cx_prepare(f, &q,
                          "SELECT objid FROM event WHERE type IN"
                          "(%Q, %Q, %Q, %Q, %Q) /*%s()*/",
                          fsl_satype_event_cstr(FSL_SATYPE_CHECKIN),
                          fsl_satype_event_cstr(FSL_SATYPE_TICKET),
                          fsl_satype_event_cstr(FSL_SATYPE_FORUMPOST),
                          fsl_satype_event_cstr(FSL_SATYPE_WIKI),
                          fsl_satype_event_cstr(FSL_SATYPE_CONTROL),
                          __func__);
      break;
#endif
    default:
      return fsl_cx_err_set(f, FSL_RC_TYPE,
                            "Artifact type [%s] is not currently "
                            "supported by %s().",
                            fsl_satype_cstr(type),
                            __func__);
  }
  while(0==rc && (FSL_RC_STEP_ROW==fsl_stmt_step(&q))){
    fsl_id_t const rid = fsl_stmt_g_id(&q, 0);
    fsl_deck d = fsl_deck_empty;
    rc = fsl_deck_load_rid(f, &d, rid, type);
    if(0==rc){
      rc = visitor(f, &d, visitorState);
    }
    fsl_deck_finalize(&d);
    if(FSL_RC_BREAK==rc){
      rc = 0;
      break;
    }
  }
  fsl_stmt_finalize(&q);
  return rc;
}

#undef MARKER
#undef AGE_FUDGE_WINDOW
#undef AGE_ADJUST_INCREMENT
#undef F_at
/* end of file ./src/deck.c */
/* start of file ./src/delta.c */

  return fsl_delta_apply2(zSrc, lenSrc_, zDelta, lenDelta_, zOut, NULL);
}

#undef NHASH
#undef DEBUG1
#undef DEBUG2
/* end of file ./src/delta.c */
/* start of file ./src/diff.c */
/* start of file ./src/dibu.c */
/* -*- Mode: C; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 2 -*- */ 
/* vim: set ts=2 et sw=2 tw=80: */
/*
  Copyright 2013-2021 The Libfossil Authors, see LICENSES/BSD-2-Clause.txt
  Copyright 2022 The Libfossil Authors, see LICENSES/BSD-2-Clause.txt

  SPDX-License-Identifier: BSD-2-Clause-FreeBSD
  SPDX-FileCopyrightText: 2021 The Libfossil Authors
  SPDX-FileCopyrightText: 2013-2022 The Libfossil Authors
  SPDX-ArtifactOfProjectName: Libfossil
  SPDX-FileType: Code

  Heavily indebted to the Fossil SCM project (https://fossil-scm.org).
*/

/************************************************************************
  This file houses Fossil's diff-generation routines (as opposed to
  This file houses the "dibu" (Diff Builder) routines.
  the delta-generation).
*/
#include <assert.h>
#include <memory.h>
#include <stdlib.h>
#include <string.h> /* for memmove()/strlen() */


/**
   Length of a dline
*/
#define LENGTH(X)   ((X)->n)

/**
   Minimum of two values
*/
static int minInt(int a, int b){ return a<b ? a : b; }

/**
    Compute the optimal longest common subsequence (LCS) using an
    exhaustive search. This version of the LCS is only used for
    shorter input strings since runtime is O(N*N) where N is the
    input string length.
*/
static void fsl__diff_optimal_lcs(
  fsl__diff_cx * const p,     /* Two files being compared */
  int iS1, int iE1,          /* Range of lines in p->aFrom[] */
  int iS2, int iE2,          /* Range of lines in p->aTo[] */
  int *piSX, int *piEX,      /* Write p->aFrom[] common segment here */
  int *piSY, int *piEY       /* Write p->aTo[] common segment here */
){
  int mxLength = 0;          /* Length of longest common subsequence */
  int i, j;                  /* Loop counters */
  int k;                     /* Length of a candidate subsequence */
  int iSXb = iS1;            /* Best match so far */
  int iSYb = iS2;            /* Best match so far */

  for(i=iS1; i<iE1-mxLength; i++){
    for(j=iS2; j<iE2-mxLength; j++){
      if( p->cmpLine(&p->aFrom[i], &p->aTo[j]) ) continue;
      if( mxLength && p->cmpLine(&p->aFrom[i+mxLength], &p->aTo[j+mxLength]) ){
        continue;
      }
      k = 1;
      while( i+k<iE1 && j+k<iE2 && p->cmpLine(&p->aFrom[i+k],&p->aTo[j+k])==0 ){
        k++;
      }
      if( k>mxLength ){
        iSXb = i;
        iSYb = j;
        mxLength = k;
      }
    }
  }
  *piSX = iSXb;
  *piEX = iSXb + mxLength;
  *piSY = iSYb;
  *piEY = iSYb + mxLength;
}

/**
    Compare two blocks of text on lines iS1 through iE1-1 of the aFrom[]
    file and lines iS2 through iE2-1 of the aTo[] file.  Locate a sequence
    of lines in these two blocks that are exactly the same.  Return
    the bounds of the matching sequence.
   
    If there are two or more possible answers of the same length, the
    returned sequence should be the one closest to the center of the
    input range.
   
    Ideally, the common sequence should be the longest possible common
    sequence.  However, an exact computation of LCS is O(N*N) which is
    way too slow for larger files.  So this routine uses an O(N)
    heuristic approximation based on hashing that usually works about
    as well.  But if the O(N) algorithm doesn't get a good solution
    and N is not too large, we fall back to an exact solution by
    calling fsl__diff_optimal_lcs().
*/
static void fsl__diff_lcs(
  fsl__diff_cx * const p,     /* Two files being compared */
  int iS1, int iE1,          /* Range of lines in p->aFrom[] */
  int iS2, int iE2,          /* Range of lines in p->aTo[] */
  int *piSX, int *piEX,      /* Write p->aFrom[] common segment here */
  int *piSY, int *piEY       /* Write p->aTo[] common segment here */
){
  int i, j, k;               /* Loop counters */
  int n;                     /* Loop limit */
  fsl_dline *pA, *pB;            /* Pointers to lines */
  int iSX, iSY, iEX, iEY;    /* Current match */
  int skew = 0;              /* How lopsided is the match */
  int dist = 0;              /* Distance of match from center */
  int mid;                   /* Center of the chng */
  int iSXb, iSYb, iEXb, iEYb;   /* Best match so far */
  int iSXp, iSYp, iEXp, iEYp;   /* Previous match */
  sqlite3_int64 bestScore;      /* Best score so far */
  sqlite3_int64 score;          /* Score for current candidate LCS */
  int span;                     /* combined width of the input sequences */
  int cutoff = 4;            /* Max hash chain entries to follow */
  int nextCutoff = -1;       /* Value of cutoff for next iteration */

  span = (iE1 - iS1) + (iE2 - iS2);
  bestScore = -10000;
  score = 0;
  iSXb = iSXp = iS1;
  iEXb = iEXp = iS1;
  iSYb = iSYp = iS2;
  iEYb = iEYp = iS2;
  mid = (iE1 + iS1)/2;
  do{
    nextCutoff = 0;
    for(i=iS1; i<iE1; i++){
      int limit = 0;
      j = p->aTo[p->aFrom[i].h % p->nTo].iHash;
      while( j>0
        && (j-1<iS2 || j>=iE2 || p->cmpLine(&p->aFrom[i], &p->aTo[j-1]))
      ){
        if( limit++ > cutoff ){
          j = 0;
          nextCutoff = cutoff*4;
          break;
        }
        j = p->aTo[j-1].iNext;
      }
      if( j==0 ) continue;
      assert( i>=iSXb && i>=iSXp );
      if( i<iEXb && j>=iSYb && j<iEYb ) continue;
      if( i<iEXp && j>=iSYp && j<iEYp ) continue;
      iSX = i;
      iSY = j-1;
      pA = &p->aFrom[iSX-1];
      pB = &p->aTo[iSY-1];
      n = minInt(iSX-iS1, iSY-iS2);
      for(k=0; k<n && p->cmpLine(pA,pB)==0; k++, pA--, pB--){}
      iSX -= k;
      iSY -= k;
      iEX = i+1;
      iEY = j;
      pA = &p->aFrom[iEX];
      pB = &p->aTo[iEY];
      n = minInt(iE1-iEX, iE2-iEY);
      for(k=0; k<n && p->cmpLine(pA,pB)==0; k++, pA++, pB++){}
      iEX += k;
      iEY += k;
      skew = (iSX-iS1) - (iSY-iS2);
      if( skew<0 ) skew = -skew;
      dist = (iSX+iEX)/2 - mid;
      if( dist<0 ) dist = -dist;
      score = (iEX - iSX)*(sqlite3_int64)span - (skew + dist);
      if( score>bestScore ){
        bestScore = score;
        iSXb = iSX;
        iSYb = iSY;
        iEXb = iEX;
        iEYb = iEY;
      }else if( iEX>iEXp ){
        iSXp = iSX;
        iSYp = iSY;
        iEXp = iEX;
        iEYp = iEY;
      }
    }
  }while( iSXb==iEXb && nextCutoff && (cutoff=nextCutoff)<=64 );
  if( iSXb==iEXb && (sqlite3_int64)(iE1-iS1)*(iE2-iS2)<2500 ){
    fsl__diff_optimal_lcs(p, iS1, iE1, iS2, iE2, piSX, piEX, piSY, piEY);
  }else{
    *piSX = iSXb;
    *piSY = iSYb;
    *piEX = iEXb;
    *piEY = iEYb;
  }
}


void fsl__dump_triples(fsl__diff_cx const * const p,
                       char const * zFile, int ln ){
  // Compare this with (fossil xdiff --raw) on the same inputs
  fprintf(stderr,"%s:%d: Compare this with (fossil xdiff --raw) on the same inputs:\n",
          zFile, ln);
  for(int i = 0; p->aEdit[i] || p->aEdit[i+1] || p->aEdit[i+2]; i+=3){
    printf(" copy %6d  delete %6d  insert %6d\n",
           p->aEdit[i], p->aEdit[i+1], p->aEdit[i+2]);
  }
}

/** @internal
    Expand the size of p->aEdit array to hold at least nEdit elements.
 */
static int fsl__diff_expand_edit(fsl__diff_cx * const p, int nEdit){
  void * re = fsl_realloc(p->aEdit, nEdit*sizeof(int));
  if(!re) return FSL_RC_OOM;
  else{
    p->aEdit = (int*)re;
    p->nEditAlloc = nEdit;
    return 0;
  }
}

/**
    Append a new COPY/DELETE/INSERT triple.
   
    Returns 0 on success, FSL_RC_OOM on OOM.
 */
static int appendTriple(fsl__diff_cx *p, int nCopy, int nDel, int nIns){
  /* printf("APPEND %d/%d/%d\n", nCopy, nDel, nIns); */
  if( p->nEdit>=3 ){
    if( p->aEdit[p->nEdit-1]==0 ){
      if( p->aEdit[p->nEdit-2]==0 ){
        p->aEdit[p->nEdit-3] += nCopy;
        p->aEdit[p->nEdit-2] += nDel;
        p->aEdit[p->nEdit-1] += nIns;
        return 0;
      }
      if( nCopy==0 ){
        p->aEdit[p->nEdit-2] += nDel;
        p->aEdit[p->nEdit-1] += nIns;
        return 0;
      }
    }
    if( nCopy==0 && nDel==0 ){
      p->aEdit[p->nEdit-1] += nIns;
      return 0;
    }
  }
  if( p->nEdit+3>p->nEditAlloc ){
    int const rc = fsl__diff_expand_edit(p, p->nEdit*2 + 15);
    if(rc) return rc;
    else if( p->aEdit==0 ) return 0;
  }
  p->aEdit[p->nEdit++] = nCopy;
  p->aEdit[p->nEdit++] = nDel;
  p->aEdit[p->nEdit++] = nIns;
  return 0;
}

/**
    Do a single step in the difference.  Compute a sequence of
    copy/delete/insert steps that will convert lines iS1 through iE1-1
    of the input into lines iS2 through iE2-1 of the output and write
    that sequence into the difference context.
   
    The algorithm is to find a block of common text near the middle of
    the two segments being diffed.  Then recursively compute
    differences on the blocks before and after that common segment.
    Special cases apply if either input segment is empty or if the two
    segments have no text in common.
 */
static int diff_step(fsl__diff_cx *p, int iS1, int iE1, int iS2, int iE2){
  int iSX, iEX, iSY, iEY;
  int rc = 0;
  if( iE1<=iS1 ){
    /* The first segment is empty */
    if( iE2>iS2 ){
      rc = appendTriple(p, 0, 0, iE2-iS2);
    }
    return rc;
  }
  if( iE2<=iS2 ){
    /* The second segment is empty */
    return appendTriple(p, 0, iE1-iS1, 0);
  }

  /* Find the longest matching segment between the two sequences */
  fsl__diff_lcs(p, iS1, iE1, iS2, iE2, &iSX, &iEX, &iSY, &iEY);
  if( iEX>iSX ){
    /* A common segment has been found.
       Recursively diff either side of the matching segment */
    rc = diff_step(p, iS1, iSX, iS2, iSY);
    if(!rc){
      if(iEX>iSX){
        rc = appendTriple(p, iEX - iSX, 0, 0);
      }
      if(!rc) rc = diff_step(p, iEX, iE1, iEY, iE2);
    }
  }else{
    /* The two segments have nothing in common.  Delete the first then
       insert the second. */
    rc = appendTriple(p, 0, iE1-iS1, iE2-iS2);
  }
  return rc;
}

int fsl__diff_all(fsl__diff_cx * const p){
  int mnE, iS, iE1, iE2;
  int rc = 0;
  /* Carve off the common header and footer */
  iE1 = p->nFrom;
  iE2 = p->nTo;
  while( iE1>0 && iE2>0 && p->cmpLine(&p->aFrom[iE1-1], &p->aTo[iE2-1])==0 ){
    iE1--;
    iE2--;
  }
  mnE = iE1<iE2 ? iE1 : iE2;
  for(iS=0; iS<mnE && p->cmpLine(&p->aFrom[iS],&p->aTo[iS])==0; iS++){}

  /* do the difference */
  if( iS>0 ){
    rc = appendTriple(p, iS, 0, 0);
    if(rc) return rc;
  }
  rc = diff_step(p, iS, iE1, iS, iE2);
  //fsl__dump_triples(p, __FILE__, __LINE__);
  if(rc) return rc;
  else if( iE1<p->nFrom ){
    rc = appendTriple(p, p->nFrom - iE1, 0, 0);
    if(rc) return rc;
  }
  /* Terminate the COPY/DELETE/INSERT triples with three zeros */
  rc = fsl__diff_expand_edit(p, p->nEdit+3);
  if(0==rc){
    if(p->aEdit ){
      p->aEdit[p->nEdit++] = 0;
      p->aEdit[p->nEdit++] = 0;
      p->aEdit[p->nEdit++] = 0;
      //fsl__dump_triples(p, __FILE__, __LINE__);
    }
  }
  return rc;
}


/*
   Attempt to shift insertion or deletion blocks so that they begin and
   end on lines that are pure whitespace.  In other words, try to transform
   this:
  
        int func1(int x){
           return x*10;
       +}
       +
       +int func2(int x){
       +   return x*20;
        }
  
        int func3(int x){
           return x/5;
        }
  
   Into one of these:
  
        int func1(int x){              int func1(int x){
           return x*10;                   return x*10;
        }                              }
       +
       +int func2(int x){             +int func2(int x){
       +   return x*20;               +   return x*20;
       +}                             +}
                                      +
        int func3(int x){              int func3(int x){
           return x/5;                    return x/5;
        }                              }
*/
void fsl__diff_optimize(fsl__diff_cx * const p){
  int r;       /* Index of current triple */
  int lnFrom;  /* Line number in p->aFrom */
  int lnTo;    /* Line number in p->aTo */
  int cpy, del, ins;

  //fsl__dump_triples(p, __FILE__, __LINE__);
  lnFrom = lnTo = 0;
  for(r=0; r<p->nEdit; r += 3){
    cpy = p->aEdit[r];
    del = p->aEdit[r+1];
    ins = p->aEdit[r+2];
    lnFrom += cpy;
    lnTo += cpy;

    /* Shift insertions toward the beginning of the file */
    while( cpy>0 && del==0 && ins>0 ){
      fsl_dline *pTop = &p->aFrom[lnFrom-1];  /* Line before start of insert */
      fsl_dline *pBtm = &p->aTo[lnTo+ins-1];  /* Last line inserted */
      if( p->cmpLine(pTop, pBtm) ) break;
      if( LENGTH(pTop+1)+LENGTH(pBtm)<=LENGTH(pTop)+LENGTH(pBtm-1) ) break;
      lnFrom--;
      lnTo--;
      p->aEdit[r]--;
      p->aEdit[r+3]++;
      cpy--;
    }

    /* Shift insertions toward the end of the file */
    while( r+3<p->nEdit && p->aEdit[r+3]>0 && del==0 && ins>0 ){
      fsl_dline *pTop = &p->aTo[lnTo];       /* First line inserted */
      fsl_dline *pBtm = &p->aTo[lnTo+ins];   /* First line past end of insert */
      if( p->cmpLine(pTop, pBtm) ) break;
      if( LENGTH(pTop)+LENGTH(pBtm-1)<=LENGTH(pTop+1)+LENGTH(pBtm) ) break;
      lnFrom++;
      lnTo++;
      p->aEdit[r]++;
      p->aEdit[r+3]--;
      cpy++;
    }

    /* Shift deletions toward the beginning of the file */
    while( cpy>0 && del>0 && ins==0 ){
      fsl_dline *pTop = &p->aFrom[lnFrom-1];     /* Line before start of delete */
      fsl_dline *pBtm = &p->aFrom[lnFrom+del-1]; /* Last line deleted */
      if( p->cmpLine(pTop, pBtm) ) break;
      if( LENGTH(pTop+1)+LENGTH(pBtm)<=LENGTH(pTop)+LENGTH(pBtm-1) ) break;
      lnFrom--;
      lnTo--;
      p->aEdit[r]--;
      p->aEdit[r+3]++;
      cpy--;
    }

    /* Shift deletions toward the end of the file */
    while( r+3<p->nEdit && p->aEdit[r+3]>0 && del>0 && ins==0 ){
      fsl_dline *pTop = &p->aFrom[lnFrom];     /* First line deleted */
      fsl_dline *pBtm = &p->aFrom[lnFrom+del]; /* First line past end of delete */
      if( p->cmpLine(pTop, pBtm) ) break;
      if( LENGTH(pTop)+LENGTH(pBtm-1)<=LENGTH(pTop)+LENGTH(pBtm) ) break;
      lnFrom++;
      lnTo++;
      p->aEdit[r]++;
      p->aEdit[r+3]--;
      cpy++;
    }

    lnFrom += del;
    lnTo += ins;
  }
  //fsl__dump_triples(p, __FILE__, __LINE__);
}


#if !defined(FSL_OMIT_DEPRECATED)

#define MARKER(pfexp)                                               \
  do{ printf("MARKER: %s:%d:%s():\t",__FILE__,__LINE__,__func__);   \
    printf pfexp;                                                   \
  } while(0)

typedef uint64_t u64;
typedef void ReCompiled /* porting crutch. i would strongly prefer to
                           replace the regex support with a stateful
                           predicate callback.
                        */;

#define DIFF_CONTEXT_MASK ((u64)0x0000ffff) /* Lines of context. Default if 0 */
#define DIFF_WIDTH_MASK   ((u64)0x00ff0000) /* side-by-side column width */
#define DIFF_IGNORE_EOLWS ((u64)0x01000000) /* Ignore end-of-line whitespace */
#define DIFF_IGNORE_ALLWS ((u64)0x03000000) /* Ignore all whitespace */
#define DIFF_SIDEBYSIDE   ((u64)0x04000000) /* Generate a side-by-side diff */
#define DIFF_VERBOSE      ((u64)0x08000000) /* Missing shown as empty files */
#define DIFF_BRIEF        ((u64)0x10000000) /* Show filenames only */
#define DIFF_HTML         ((u64)0x20000000) /* Render for HTML */
#define DIFF_LINENO       ((u64)0x40000000) /* Show line numbers */
#define DIFF_NOOPT        (((u64)0x01)<<32) /* Suppress optimizations (debug) */
#define DIFF_INVERT       (((u64)0x02)<<32) /* Invert the diff (debug) */
#define DIFF_CONTEXT_EX   (((u64)0x04)<<32) /* Use context even if zero */
#define DIFF_NOTTOOBIG    (((u64)0x08)<<32) /* Only display if not too big */
#define DIFF_STRIP_EOLCR  (((u64)0x10)<<32) /* Strip trailing CR */

/*
  ANSI escape codes: https://en.wikipedia.org/wiki/ANSI_escape_code
*/
#define ANSI_COLOR_BLACK(BOLD) ((BOLD) ? "\x1b[30m" : "\x1b[30m")
#define ANSI_COLOR_RED(BOLD) ((BOLD) ? "\x1b[31;1m" : "\x1b[31m")
#define ANSI_COLOR_GREEN(BOLD) ((BOLD) ? "\x1b[32;1m" : "\x1b[32m")
#define ANSI_COLOR_YELLOW(BOLD) ((BOLD) ? "\x1b[33;1m" : "\x1b[33m")
#define ANSI_COLOR_BLUE(BOLD) ((BOLD) ? "\x1b[34;1m" : "\x1b[34m")
#define ANSI_COLOR_MAGENTA(BOLD) ((BOLD) ? "\x1b[35;1m" : "\x1b[35m")
#define ANSI_COLOR_CYAN(BOLD) ((BOLD) ? "\x1b[36;1m" : "\x1b[36m")
#define ANSI_COLOR_WHITE(BOLD) ((BOLD) ? "\x1b[37;1m" : "\x1b[37m")
#define ANSI_DIFF_ADD(BOLD) ANSI_COLOR_GREEN(BOLD)
#define ANSI_DIFF_RM(BOLD) ANSI_COLOR_RED(BOLD)
#define ANSI_DIFF_MOD(BOLD) ANSI_COLOR_BLUE(BOLD)
#define ANSI_BG_BLACK(BOLD) ((BOLD) ? "\x1b[40;1m" : "\x1b[40m")
#define ANSI_BG_RED(BOLD) ((BOLD) ? "\x1b[41;1m" : "\x1b[41m")
#define ANSI_BG_GREEN(BOLD) ((BOLD) ? "\x1b[42;1m" : "\x1b[42m")
#define ANSI_BG_YELLOW(BOLD) ((BOLD) ? "\x1b[43;1m" : "\x1b[43m")
#define ANSI_BG_BLUE(BOLD) ((BOLD) ? "\x1b[44;1m" : "\x1b[44m")
#define ANSI_BG_MAGENTA(BOLD) ((BOLD) ? "\x1b[45;1m" : "\x1b[45m")
#define ANSI_BG_CYAN(BOLD) ((BOLD) ? "\x1b[46;1m" : "\x1b[46m")
#define ANSI_BG_WHITE(BOLD) ((BOLD) ? "\x1b[47;1m" : "\x1b[47m")
#define ANSI_RESET_COLOR   "\x1b[39;49m"
#define ANSI_RESET_ALL     "\x1b[0m"
#define ANSI_RESET ANSI_RESET_ALL
/*#define ANSI_BOLD     ";1m"*/

/**
    Converts mask of public fsl_diff_flag_t (32-bit) values to the
    Fossil-internal 64-bit bitmask used by the DIFF_xxx macros. Why?
    (A) fossil(1) uses the macro approach and a low-level encoding of
    data in the bitmask (e.g. the context lines count). The public API
    hides the lower-level flags and allows the internal API to take
    care of the encoding.
*/
static uint64_t fsl_diff_flags_convert( int mask ){
  uint64_t rc = 0U;
#define DO(F) if( (mask & F)==F ) rc |= (((u64)F) << 24)
  DO(FSL_DIFF2_IGNORE_EOLWS);
  DO(FSL_DIFF2_IGNORE_ALLWS);
  DO(FSL_DIFF2_LINE_NUMBERS);
  DO(FSL_DIFF_SIDEBYSIDE);
  DO(FSL_DIFF2_NOTTOOBIG);
  DO(FSL_DIFF2_STRIP_EOLCR);
  DO(FSL_DIFF_VERBOSE);
  DO(FSL_DIFF_BRIEF);
  DO(FSL_DIFF_HTML);
  DO(FSL_DIFF_NOOPT);
  DO(FSL_DIFF_INVERT);
#undef DO
  return rc;
}

/**
    Holds output state for diff generation.
 */
struct DiffOutState {
  /** Output callback. */
  fsl_output_f out;
  /** State for this->out(). */
  void * oState;
  /** For propagating output errors. */
  int rc;
  char ansiColor;
};
typedef struct DiffOutState DiffOutState;
static const DiffOutState DiffOutState_empty = {
NULL/*out*/,
NULL/*oState*/,
0/*rc*/,
0/*useAnsiColor*/
};

/**
    Internal helper. Sends src to o->out(). If n is negative, fsl_strlen()
    is used to determine the length.
 */
static int diff_out( DiffOutState * const o, void const * src, fsl_int_t n ){
  return o->rc = n
    ? o->out(o->oState, src, n<0 ? fsl_strlen((char const *)src) : (fsl_size_t)n)
    : 0;
}

/**
    fsl_output_f() impl for use with diff_outf(). state must be a
    (DiffOutState*).
 */
static int fsl_output_f_diff_out( void * state, void const * src,
                                  fsl_size_t n ){
  DiffOutState * const os = (DiffOutState *)state;
  return os->rc = os->out(os->oState, src, n);
}

static int diff_outf( DiffOutState * o, char const * fmt, ... ){
  va_list va;
  va_start(va,fmt);
  fsl_appendfv(fsl_output_f_diff_out, o, fmt, va);
  va_end(va);
  return o->rc;
}

/*
   Append a single line of context-diff output to pOut.
*/
static int appendDiffLine(
  DiffOutState *const pOut, /* Where to write the line of output */
  char cPrefix,       /* One of " ", "+",  or "-" */
  fsl_dline *pLine,       /* The line to be output */
  int html,           /* True if generating HTML.  False for plain text */
  ReCompiled *pRe     /* Colorize only if line matches this Regex */
){
  int rc = 0;
  char const * ansiPrefix =
    !pOut->ansiColor
    ? NULL 
    : (('+'==cPrefix)
       ? ANSI_DIFF_ADD(0)
       : (('-'==cPrefix) ? ANSI_DIFF_RM(0) : NULL))
    ;
  if(ansiPrefix) rc = diff_out(pOut, ansiPrefix, -1 );
  if(!rc) rc = diff_out(pOut, &cPrefix, 1);
  if(rc) return rc;
  else if( html ){
#if 0
    if( pRe /*MISSING: && re_dline_match(pRe, pLine, 1)==0 */ ){
      cPrefix = ' ';
    }else
#endif
    if( cPrefix=='+' ){
      rc = diff_out(pOut, "<span class=\"fsl-diff-add\">", -1);
    }else if( cPrefix=='-' ){
      rc = diff_out(pOut, "<span class=\"fsl-diff-rm\">", -1);
    }
    if(!rc){
      /* unsigned short n = pLine->n; */
      /* while( n>0 && (pLine->z[n-1]=='\n' || pLine->z[n-1]=='\r') ) n--; */
      rc = pOut->rc = fsl_htmlize(pOut->out, pOut->oState,
                                  pLine->z, pLine->n);
      if( !rc && cPrefix!=' ' ){
        rc = diff_out(pOut, "</span>", -1);
      }
    }
  }else{
    rc = diff_out(pOut, pLine->z, pLine->n);
  }
  if(!rc){
    if(ansiPrefix){
      rc = diff_out(pOut, ANSI_RESET, -1 );
    }
    if(!rc) rc = diff_out(pOut, "\n", 1);
  }
  return rc;
}


/*
   Add two line numbers to the beginning of an output line for a context
   diff.  One or the other of the two numbers might be zero, which means
   to leave that number field blank.  The "html" parameter means to format
   the output for HTML.
*/
static int appendDiffLineno(DiffOutState *pOut, int lnA,
                            int lnB, int html){
  int rc = 0;
  if( html ){
    rc = diff_out(pOut, "<span class=\"fsl-diff-lineno\">", -1);
  }
  if(!rc){
    if( lnA>0 ){
      rc = diff_outf(pOut, "%6d ", lnA);
    }else{
      rc = diff_out(pOut, "       ", 7);
    }
  }
  if(!rc){
    if( lnB>0 ){
      rc = diff_outf(pOut, "%6d  ", lnB);
    }else{
      rc = diff_out(pOut, "        ", 8);
    }
    if( !rc && html ){
      rc = diff_out(pOut, "</span>", -1);
    }
  }
  return rc;
}

/**
    Extract the number of lines of context from diffFlags.
 */
static int diff_context_lines(uint64_t diffFlags){
  int n = diffFlags & DIFF_CONTEXT_MASK;
  if( n==0 && (diffFlags & DIFF_CONTEXT_EX)==0 ) n = 5;
  return n;
}

/*
   Extract the width of columns for side-by-side diff.  Supply an
   appropriate default if no width is given.
*/
static int diff_width(uint64_t diffFlags){
  int w = (diffFlags & DIFF_WIDTH_MASK)/(DIFF_CONTEXT_MASK+1);
  if( w==0 ) w = 80;
  return w;
}

/*
   Given a raw diff p[] in which the p->aEdit[] array has been filled
   in, compute a context diff into pOut.
*/
static int contextDiff(
  fsl__diff_cx *p,      /* The difference */
  DiffOutState *pOut,       /* Output a context diff to here */
  ReCompiled *pRe,  /* Only show changes that match this regex */
  u64 diffFlags     /* Flags controlling the diff format */
){
  fsl_dline *A;     /* Left side of the diff */
  fsl_dline *B;     /* Right side of the diff */
  int a = 0;    /* Index of next line in A[] */
  int b = 0;    /* Index of next line in B[] */
  int *R;       /* Array of COPY/DELETE/INSERT triples */
  int r;        /* Index into R[] */
  int nr;       /* Number of COPY/DELETE/INSERT triples to process */
  int mxr;      /* Maximum value for r */
  int na, nb;   /* Number of lines shown from A and B */
  int i, j;     /* Loop counters */
  int m;        /* Number of lines to output */
  int skip;     /* Number of lines to skip */
  static int nChunk = 0;  /* Number of diff chunks seen so far */
  int nContext;    /* Number of lines of context */
  int showLn;      /* Show line numbers */
  int html;        /* Render as HTML */
  int showDivider = 0;  /* True to show the divider between diff blocks */
  int rc = 0;
  nContext = diff_context_lines(diffFlags);
  showLn = (diffFlags & DIFF_LINENO)!=0;
  html = (diffFlags & DIFF_HTML)!=0;
  A = p->aFrom;
  B = p->aTo;
  R = p->aEdit;
  mxr = p->nEdit;
  while( mxr>2 && R[mxr-1]==0 && R[mxr-2]==0 ){ mxr -= 3; }
  for(r=0; r<mxr; r += 3*nr){
    /* Figure out how many triples to show in a single block */
    for(nr=1; R[r+nr*3]>0 && R[r+nr*3]<nContext*2; nr++){}
    /* printf("r=%d nr=%d\n", r, nr); */

    /* If there is a regex, skip this block (generate no diff output)
       if the regex matches or does not match both insert and delete.
       Only display the block if one side matches but the other side does
       not.
    */
#if 0
    /* MISSING: re. i would prefer a predicate function,
       anyway.
    */
    if( pRe ){
      int hideBlock = 1;
      int xa = a, xb = b;
      for(i=0; hideBlock && i<nr; i++){
        int c1, c2;
        xa += R[r+i*3];
        xb += R[r+i*3];
        c1 = re_dline_match(pRe, &A[xa], R[r+i*3+1]);
        c2 = re_dline_match(pRe, &B[xb], R[r+i*3+2]);
        hideBlock = c1==c2;
        xa += R[r+i*3+1];
        xb += R[r+i*3+2];
      }
      if( hideBlock ){
        a = xa;
        b = xb;
        continue;
      }
    }
#endif
    /* For the current block comprising nr triples, figure out
       how many lines of A and B are to be displayed
    */
    if( R[r]>nContext ){
      na = nb = nContext;
      skip = R[r] - nContext;
    }else{
      na = nb = R[r];
      skip = 0;
    }
    for(i=0; i<nr; i++){
      na += R[r+i*3+1];
      nb += R[r+i*3+2];
    }
    if( R[r+nr*3]>nContext ){
      na += nContext;
      nb += nContext;
    }else{
      na += R[r+nr*3];
      nb += R[r+nr*3];
    }
    for(i=1; i<nr; i++){
      na += R[r+i*3];
      nb += R[r+i*3];
    }

    /* Show the header for this block, or if we are doing a modified
       context diff that contains line numbers, show the separator from
       the previous block.
    */
    ++nChunk;
    if( showLn ){
      if( !showDivider ){
        /* Do not show a top divider */
        showDivider = 1;
      }else if( html ){
        rc = diff_outf(pOut, "<span class=\"fsl-diff-hr\">%.80c</span>\n", '.');
      }else{
        rc = diff_outf(pOut, "%.80c\n", '.');
      }
      if( !rc && html ){
        rc = diff_outf(pOut, "<span class=\"fsl-diff-chunk-%d\"></span>", nChunk);
      }
    }else{
      char const * ansi1 = "";
      char const * ansi2 = "";
      char const * ansi3 = "";
      if( html ) rc = diff_outf(pOut, "<span class=\"fsl-diff-lineno\">");
      else if(0 && pOut->ansiColor){
        /* Turns out this just confuses the output */
        ansi1 = ANSI_DIFF_RM(0);
        ansi2 = ANSI_DIFF_ADD(0);
        ansi3 = ANSI_RESET;
      }
      /*
       * If the patch changes an empty file or results in an empty file,
       * the block header must use 0,0 as position indicator and not 1,0.
       * Otherwise, patch would be confused and may reject the diff.
       */
      if(!rc) rc = diff_outf(pOut,"@@ %s-%d,%d %s+%d,%d%s @@",
                             ansi1, na ? a+skip+1 : 0, na,
                             ansi2, nb ? b+skip+1 : 0, nb,
                             ansi3);
      if( !rc ){
        if( html ) rc = diff_outf(pOut, "</span>");
        if(!rc) rc = diff_out(pOut, "\n", 1);
      }
    }
    if(rc) return rc;

    /* Show the initial common area */
    a += skip;
    b += skip;
    m = R[r] - skip;
    for(j=0; !rc && j<m; j++){
      if( showLn ) rc = appendDiffLineno(pOut, a+j+1, b+j+1, html);
      if(!rc) rc = appendDiffLine(pOut, ' ', &A[a+j], html, 0);
    }
    if(rc) return rc;
    a += m;
    b += m;

    /* Show the differences */
    for(i=0; i<nr; i++){
      m = R[r+i*3+1];
      for(j=0; !rc && j<m; j++){
        if( showLn ) rc = appendDiffLineno(pOut, a+j+1, 0, html);
        if(!rc) rc = appendDiffLine(pOut, '-', &A[a+j], html, pRe);
      }
      if(rc) return rc;
      a += m;
      m = R[r+i*3+2];
      for(j=0; !rc && j<m; j++){
        if( showLn ) rc = appendDiffLineno(pOut, 0, b+j+1, html);
        if(!rc) rc = appendDiffLine(pOut, '+', &B[b+j], html, pRe);
      }
      if(rc) return rc;
      b += m;
      if( i<nr-1 ){
        m = R[r+i*3+3];
        for(j=0; !rc && j<m; j++){
          if( showLn ) rc = appendDiffLineno(pOut, a+j+1, b+j+1, html);
          if(!rc) rc = appendDiffLine(pOut, ' ', &A[a+j], html, 0);
        }
        if(rc) return rc;
        b += m;
        a += m;
      }
    }

    /* Show the final common area */
    assert( nr==i );
    m = R[r+nr*3];
    if( m>nContext ) m = nContext;
    for(j=0; !rc && j<m; j++){
      if( showLn ) rc = appendDiffLineno(pOut, a+j+1, b+j+1, html);
      if(!rc) rc = appendDiffLine(pOut, ' ', &A[a+j], html, 0);
    }
  }/*big for() loop*/
  return rc;
}

/*
   Status of a single output line
*/
typedef struct SbsLine SbsLine;
struct SbsLine {
  fsl_buffer *apCols[5];   /* Array of pointers to output columns */
  int width;               /* Maximum width of a column in the output */
  unsigned char escHtml;   /* True to escape html characters */
  int iStart;              /* Write zStart prior to character iStart */
  const char *zStart;      /* A <span> tag */
  int iEnd;                /* Write </span> prior to character iEnd */
  int iStart2;             /* Write zStart2 prior to character iStart2 */
  const char *zStart2;     /* A <span> tag */
  int iEnd2;               /* Write </span> prior to character iEnd2 */
  ReCompiled *pRe;         /* Only colorize matching lines, if not NULL */
  DiffOutState * pOut;
};

/*
   Column indices for SbsLine.apCols[]
*/
#define SBS_LNA  0     /* Left line number */
#define SBS_TXTA 1     /* Left text */
#define SBS_MKR  2     /* Middle separator column */
#define SBS_LNB  3     /* Right line number */
#define SBS_TXTB 4     /* Right text */

/*
   Append newlines to all columns.
*/
static int sbsWriteNewlines(SbsLine *p){
  int i;
  int rc = 0;
  for( i=p->escHtml ? SBS_LNA : SBS_TXTB; !rc && i<=SBS_TXTB; i++ ){
    rc = fsl_buffer_append(p->apCols[i], "\n", 1);
  }
  return rc;
}

/*
   Append n spaces to the column.
*/
static int sbsWriteSpace(SbsLine *p, int n, int col){
  return fsl_buffer_appendf(p->apCols[col], "%*s", n, "");
}

/*
   Write the text of pLine into column iCol of p.
  
   If outputting HTML, write the full line.  Otherwise, only write the
   width characters.  Translate tabs into spaces.  Add newlines if col
   is SBS_TXTB.  Translate HTML characters if escHtml is true.  Pad the
   rendering to width bytes if col is SBS_TXTA and escHtml is false.
  
   This comment contains multibyte unicode characters (�, �, �) in order
   to test the ability of the diff code to handle such characters.
*/
static int sbsWriteText(SbsLine *p, fsl_dline *pLine, int col){
  fsl_buffer *pCol = p->apCols[col];
  int rc = 0;
  int n = pLine->n;
  int i;   /* Number of input characters consumed */
  int k;   /* Cursor position */
  int needEndSpan = 0;
  const char *zIn = pLine->z;
  int w = p->width;
  int colorize = p->escHtml;
#if 0
  /* MISSING: re bits, but want to replace those with a predicate. */
  if( colorize && p->pRe && re_dline_match(p->pRe, pLine, 1)==0 ){
    colorize = 0;
  }
#endif
  for(i=k=0; !rc && (p->escHtml || k<w) && i<n; i++, k++){
    char c = zIn[i];
    if( colorize ){
      if( i==p->iStart ){
        rc = fsl_buffer_append(pCol, p->zStart, -1);
        if(rc) break;
        needEndSpan = 1;
        if( p->iStart2 ){
          p->iStart = p->iStart2;
          p->zStart = p->zStart2;
          p->iStart2 = 0;
        }
      }else if( i==p->iEnd ){
        rc = fsl_buffer_append(pCol, "</span>", 7);
        if(rc) break;
        needEndSpan = 0;
        if( p->iEnd2 ){
          p->iEnd = p->iEnd2;
          p->iEnd2 = 0;
        }
      }
    }
    if( c=='\t' && !p->escHtml ){
      rc = fsl_buffer_append(pCol, " ", 1);
      while( !rc && (k&7)!=7 && (p->escHtml || k<w) ){
        rc = fsl_buffer_append(pCol, " ", 1);
        k++;
      }
    }else if( c=='\r' || c=='\f' ){
      rc = fsl_buffer_append(pCol, " ", 1);
    }else if( c=='<' && p->escHtml ){
      rc = fsl_buffer_append(pCol, "&lt;", 4);
    }else if( c=='&' && p->escHtml ){
      rc = fsl_buffer_append(pCol, "&amp;", 5);
    }else if( c=='>' && p->escHtml ){
      rc = fsl_buffer_append(pCol, "&gt;", 4);
    }else if( c=='"' && p->escHtml ){
      rc = fsl_buffer_append(pCol, "&quot;", 6);
    }else{
      rc = fsl_buffer_append(pCol, &zIn[i], 1);
      if( (c&0xc0)==0x80 ) k--;
    }
  }
  if( !rc && needEndSpan ){
    rc = fsl_buffer_append(pCol, "</span>", 7);
  }
  if(!rc){
    if( col==SBS_TXTB ){
      rc = sbsWriteNewlines(p);
    }else if( !p->escHtml ){
      rc = sbsWriteSpace(p, w-k, SBS_TXTA);
    }
  }
  return rc;
}


/*
   Append a column to the final output blob.
*/
static int sbsWriteColumn(DiffOutState *pOut, fsl_buffer const *pCol, int col){
  return diff_outf(pOut,
    "<td><div class=\"fsl-diff-%s-col\">\n"
    "<pre>\n"
    "%b"
    "</pre>\n"
    "</div></td>\n",
    col % 3 ? (col == SBS_MKR ? "separator" : "text") : "lineno",
    pCol
  );
}


/*
   Append a separator line to column iCol
*/
static int sbsWriteSep(SbsLine *p, int len, int col){
  char ch = '.';
  if( len<1 ){
    len = 1;
    ch = ' ';
  }
  return fsl_buffer_appendf(p->apCols[col],
                            "<span class=\"fsl-diff-hr\">%.*c</span>\n",
                            len, ch);
}


/*
   Append the appropriate marker into the center column of the diff.
*/
static int sbsWriteMarker(SbsLine *p, const char *zTxt,
                                 const char *zHtml){
  return fsl_buffer_append(p->apCols[SBS_MKR], p->escHtml ? zHtml : zTxt, -1);
}

/*
   Append a line number to the column.
*/
static int sbsWriteLineno(SbsLine *p, int ln, int col){
  int rc;
  if( p->escHtml ){
    rc = fsl_buffer_appendf(p->apCols[col], "%d", ln+1);
  }else{
    char zLn[8];
    fsl_snprintf(zLn, 8, "%5d ", ln+1);
    rc = fsl_buffer_appendf(p->apCols[col], "%s ", zLn);
  }
  return rc;
}


/*
   The two text segments zLeft and zRight are known to be different on
   both ends, but they might have  a common segment in the middle.  If
   they do not have a common segment, return 0.  If they do have a large
   common segment, return 1 and before doing so set:
  
     aLCS[0] = start of the common segment in zLeft
     aLCS[1] = end of the common segment in zLeft
     aLCS[2] = start of the common segment in zLeft
     aLCS[3] = end of the common segment in zLeft
  
   This computation is for display purposes only and does not have to be
   optimal or exact.
*/
static int textLCS(
  const char *zLeft,  int nA,       /* String on the left */
  const char *zRight,  int nB,      /* String on the right */
  int *aLCS                         /* Identify bounds of LCS here */
){
  const unsigned char *zA = (const unsigned char*)zLeft;    /* left string */
  const unsigned char *zB = (const unsigned char*)zRight;   /* right string */
  int nt;                    /* Number of target points */
  int ti[3];                 /* Index for start of each 4-byte target */
  unsigned int target[3];    /* 4-byte alignment targets */
  unsigned int probe;        /* probe to compare against target */
  int iAS, iAE, iBS, iBE;    /* Range of common segment */
  int i, j;                  /* Loop counters */
  int rc = 0;                /* Result code.  1 for success */

  if( nA<6 || nB<6 ) return 0;
  memset(aLCS, 0, sizeof(int)*4);
  ti[0] = i = nB/2-2;
  target[0] = (zB[i]<<24) | (zB[i+1]<<16) | (zB[i+2]<<8) | zB[i+3];
  probe = 0;
  if( nB<16 ){
    nt = 1;
  }else{
    ti[1] = i = nB/4-2;
    target[1] = (zB[i]<<24) | (zB[i+1]<<16) | (zB[i+2]<<8) | zB[i+3];
    ti[2] = i = (nB*3)/4-2;
    target[2] = (zB[i]<<24) | (zB[i+1]<<16) | (zB[i+2]<<8) | zB[i+3];
    nt = 3;
  }
  probe = (zA[0]<<16) | (zA[1]<<8) | zA[2];
  for(i=3; i<nA; i++){
    probe = (probe<<8) | zA[i];
    for(j=0; j<nt; j++){
      if( probe==target[j] ){
        iAS = i-3;
        iAE = i+1;
        iBS = ti[j];
        iBE = ti[j]+4;
        while( iAE<nA && iBE<nB && zA[iAE]==zB[iBE] ){ iAE++; iBE++; }
        while( iAS>0 && iBS>0 && zA[iAS-1]==zB[iBS-1] ){ iAS--; iBS--; }
        if( iAE-iAS > aLCS[1] - aLCS[0] ){
          aLCS[0] = iAS;
          aLCS[1] = iAE;
          aLCS[2] = iBS;
          aLCS[3] = iBE;
          rc = 1;
        }
      }
    }
  }
  return rc;
}


/*
   Try to shift iStart as far as possible to the left.
*/
static void sbsShiftLeft(SbsLine *p, const char *z){
  int i, j;
  while( (i=p->iStart)>0 && z[i-1]==z[i] ){
    for(j=i+1; j<p->iEnd && z[j-1]==z[j]; j++){}
    if( j<p->iEnd ) break;
    p->iStart--;
    p->iEnd--;
  }
}

/*
   Simplify iStart and iStart2:
  
      *  If iStart is a null-change then move iStart2 into iStart
      *  Make sure any null-changes are in canonoical form.
      *  Make sure all changes are at character boundaries for
         multi-byte characters.
*/
static void sbsSimplifyLine(SbsLine *p, const char *z){
  if( p->iStart2==p->iEnd2 ){
    p->iStart2 = p->iEnd2 = 0;
  }else if( p->iStart2 ){
    while( p->iStart2>0 && (z[p->iStart2]&0xc0)==0x80 ) p->iStart2--;
    while( (z[p->iEnd2]&0xc0)==0x80 ) p->iEnd2++;
  }
  if( p->iStart==p->iEnd ){
    p->iStart = p->iStart2;
    p->iEnd = p->iEnd2;
    p->zStart = p->zStart2;
    p->iStart2 = 0;
    p->iEnd2 = 0;
  }
  if( p->iStart==p->iEnd ){
    p->iStart = p->iEnd = -1;
  }else if( p->iStart>0 ){
    while( p->iStart>0 && (z[p->iStart]&0xc0)==0x80 ) p->iStart--;
    while( (z[p->iEnd]&0xc0)==0x80 ) p->iEnd++;
  }
}


/*
   Write out lines that have been edited.  Adjust the highlight to cover
   only those parts of the line that actually changed.
*/
static int sbsWriteLineChange(
  SbsLine *p,          /* The SBS output line */
  fsl_dline *pLeft,        /* Left line of the change */
  int lnLeft,          /* Line number for the left line */
  fsl_dline *pRight,       /* Right line of the change */
  int lnRight          /* Line number of the right line */
){
  int rc = 0;
  int nLeft;           /* Length of left line in bytes */
  int nRight;          /* Length of right line in bytes */
  int nShort;          /* Shortest of left and right */
  int nPrefix;         /* Length of common prefix */
  int nSuffix;         /* Length of common suffix */
  const char *zLeft;   /* Text of the left line */
  const char *zRight;  /* Text of the right line */
  int nLeftDiff;       /* nLeft - nPrefix - nSuffix */
  int nRightDiff;      /* nRight - nPrefix - nSuffix */
  int aLCS[4] = {0,0,0,0}; /* Bounds of common middle segment */
  static const char zClassRm[]   = "<span class=\"fsl-diff-rm\">";
  static const char zClassAdd[]  = "<span class=\"fsl-diff-add\">";
  static const char zClassChng[] = "<span class=\"fsl-diff-change\">";

  nLeft = pLeft->n;
  zLeft = pLeft->z;
  nRight = pRight->n;
  zRight = pRight->z;
  nShort = nLeft<nRight ? nLeft : nRight;

  nPrefix = 0;
  while( nPrefix<nShort && zLeft[nPrefix]==zRight[nPrefix] ){
    nPrefix++;
  }
  if( nPrefix<nShort ){
    while( nPrefix>0 && (zLeft[nPrefix]&0xc0)==0x80 ) nPrefix--;
  }
  nSuffix = 0;
  if( nPrefix<nShort ){
    while( nSuffix<nShort && zLeft[nLeft-nSuffix-1]==zRight[nRight-nSuffix-1] ){
      nSuffix++;
    }
    if( nSuffix<nShort ){
      while( nSuffix>0 && (zLeft[nLeft-nSuffix]&0xc0)==0x80 ) nSuffix--;
    }
    if( nSuffix==nLeft || nSuffix==nRight ) nPrefix = 0;
  }
  if( nPrefix+nSuffix > nShort ) nPrefix = nShort - nSuffix;

  /* A single chunk of text inserted on the right */
  if( nPrefix+nSuffix==nLeft ){
    rc = sbsWriteLineno(p, lnLeft, SBS_LNA);
    if(rc) return rc;
    p->iStart2 = p->iEnd2 = 0;
    p->iStart = p->iEnd = -1;
    rc = sbsWriteText(p, pLeft, SBS_TXTA);
    if( !rc && nLeft==nRight && zLeft[nLeft]==zRight[nRight] ){
      rc = sbsWriteMarker(p, "   ", "");
    }else{
      rc = sbsWriteMarker(p, " | ", "|");
    }
    if(!rc){
      rc = sbsWriteLineno(p, lnRight, SBS_LNB);
      if(!rc){
        p->iStart = nPrefix;
        p->iEnd = nRight - nSuffix;
        p->zStart = zClassAdd;
        rc = sbsWriteText(p, pRight, SBS_TXTB);
      }
    }
    return rc;
  }

  /* A single chunk of text deleted from the left */
  if( nPrefix+nSuffix==nRight ){
    /* Text deleted from the left */
    rc = sbsWriteLineno(p, lnLeft, SBS_LNA);
    if(!rc){
      p->iStart2 = p->iEnd2 = 0;
      p->iStart = nPrefix;
      p->iEnd = nLeft - nSuffix;
      p->zStart = zClassRm;
      rc = sbsWriteText(p, pLeft, SBS_TXTA);
      if(!rc){
        rc = sbsWriteMarker(p, " | ", "|");
        if(!rc){
          rc = sbsWriteLineno(p, lnRight, SBS_LNB);
          if(!rc){
            p->iStart = p->iEnd = -1;
            sbsWriteText(p, pRight, SBS_TXTB);
          }
        }
      }
    }
    return rc;
  }

  /* At this point we know that there is a chunk of text that has
     changed between the left and the right.  Check to see if there
     is a large unchanged section in the middle of that changed block.
  */
  nLeftDiff = nLeft - nSuffix - nPrefix;
  nRightDiff = nRight - nSuffix - nPrefix;
  if( p->escHtml
   && nLeftDiff >= 6
   && nRightDiff >= 6
   && textLCS(&zLeft[nPrefix], nLeftDiff, &zRight[nPrefix], nRightDiff, aLCS)
  ){
    rc = sbsWriteLineno(p, lnLeft, SBS_LNA);
    if(rc) return rc;
    p->iStart = nPrefix;
    p->iEnd = nPrefix + aLCS[0];
    if( aLCS[2]==0 ){
      sbsShiftLeft(p, pLeft->z);
      p->zStart = zClassRm;
    }else{
      p->zStart = zClassChng;
    }
    p->iStart2 = nPrefix + aLCS[1];
    p->iEnd2 = nLeft - nSuffix;
    p->zStart2 = aLCS[3]==nRightDiff ? zClassRm : zClassChng;
    sbsSimplifyLine(p, zLeft+nPrefix);
    rc = sbsWriteText(p, pLeft, SBS_TXTA);
    if(!rc) rc = sbsWriteMarker(p, " | ", "|");
    if(!rc) rc = sbsWriteLineno(p, lnRight, SBS_LNB);
    if(rc) return rc;
    p->iStart = nPrefix;
    p->iEnd = nPrefix + aLCS[2];
    if( aLCS[0]==0 ){
      sbsShiftLeft(p, pRight->z);
      p->zStart = zClassAdd;
    }else{
      p->zStart = zClassChng;
    }
    p->iStart2 = nPrefix + aLCS[3];
    p->iEnd2 = nRight - nSuffix;
    p->zStart2 = aLCS[1]==nLeftDiff ? zClassAdd : zClassChng;
    sbsSimplifyLine(p, zRight+nPrefix);
    rc = sbsWriteText(p, pRight, SBS_TXTB);
    return rc;
  }

  /* If all else fails, show a single big change between left and right */
  rc = sbsWriteLineno(p, lnLeft, SBS_LNA);
  if(!rc){
    p->iStart2 = p->iEnd2 = 0;
    p->iStart = nPrefix;
    p->iEnd = nLeft - nSuffix;
    p->zStart = zClassChng;
    rc = sbsWriteText(p, pLeft, SBS_TXTA);
    if(!rc){
      rc = sbsWriteMarker(p, " | ", "|");
      if(!rc){
        rc = sbsWriteLineno(p, lnRight, SBS_LNB);
        if(!rc){
          p->iEnd = nRight - nSuffix;
          sbsWriteText(p, pRight, SBS_TXTB);
        }
      }
    }
  }
  return rc;
}


/*
   Return the number between 0 and 100 that is smaller the closer pA and
   pB match.  Return 0 for a perfect match.  Return 100 if pA and pB are
   completely different.
  
   The current algorithm is as follows:
  
   (1) Remove leading and trailing whitespace.
   (2) Truncate both strings to at most 250 characters
   (3) Find the length of the longest common subsequence
   (4) Longer common subsequences yield lower scores.
*/
static int match_dline(fsl_dline *pA, fsl_dline *pB){
  const char *zA;            /* Left string */
  const char *zB;            /* right string */
  int nA;                    /* Bytes in zA[] */
  int nB;                    /* Bytes in zB[] */
  int avg;                   /* Average length of A and B */
  int i, j, k;               /* Loop counters */
  int best = 0;              /* Longest match found so far */
  int score;                 /* Final score.  0..100 */
  unsigned char c;           /* Character being examined */
  unsigned char aFirst[256]; /* aFirst[X] = index in zB[] of first char X */
  unsigned char aNext[252];  /* aNext[i] = index in zB[] of next zB[i] char */

  zA = pA->z;
  zB = pB->z;
  nA = pA->n;
  nB = pB->n;
  while( nA>0 && fsl_isspace(zA[0]) ){ nA--; zA++; }
  while( nA>0 && fsl_isspace(zA[nA-1]) ){ nA--; }
  while( nB>0 && fsl_isspace(zB[0]) ){ nB--; zB++; }
  while( nB>0 && fsl_isspace(zB[nB-1]) ){ nB--; }
  if( nA>250 ) nA = 250;
  if( nB>250 ) nB = 250;
  avg = (nA+nB)/2;
  if( avg==0 ) return 0;
  if( nA==nB && memcmp(zA, zB, nA)==0 ) return 0;
  memset(aFirst, 0, sizeof(aFirst));
  zA--; zB--;   /* Make both zA[] and zB[] 1-indexed */
  for(i=nB; i>0; i--){
    c = (unsigned char)zB[i];
    aNext[i] = aFirst[c];
    aFirst[c] = i;
  }
  best = 0;
  for(i=1; i<=nA-best; i++){
    c = (unsigned char)zA[i];
    for(j=aFirst[c]; j>0 && j<nB-best; j = aNext[j]){
      int limit = minInt(nA-i, nB-j);
      for(k=1; k<=limit && zA[k+i]==zB[k+j]; k++){}
      if( k>best ) best = k;
    }
  }
  score = (best>avg) ? 0 : (avg - best)*100/avg;

#if 0
  fprintf(stderr, "A: [%.*s]\nB: [%.*s]\nbest=%d avg=%d score=%d\n",
  nA, zA+1, nB, zB+1, best, avg, score);
#endif

  /* Return the result */
  return score;
}


/*
   There is a change block in which nLeft lines of text on the left are
   converted into nRight lines of text on the right.  This routine computes
   how the lines on the left line up with the lines on the right.
  
   The return value is a buffer of unsigned characters, obtained from
   fsl_malloc().  (The caller needs to free the return value using
   fsl_free().)  Entries in the returned array have values as follows:
  
      1.  Delete the next line of pLeft.
      2.  Insert the next line of pRight.
      3.  The next line of pLeft changes into the next line of pRight.
      4.  Delete one line from pLeft and add one line to pRight.
  
   Values larger than three indicate better matches.
  
   The length of the returned array will be just large enough to cause
   all elements of pLeft and pRight to be consumed.
  
   Algorithm:  Wagner's minimum edit-distance algorithm, modified by
   adding a cost to each match based on how well the two rows match
   each other.  Insertion and deletion costs are 50.  Match costs
   are between 0 and 100 where 0 is a perfect match 100 is a complete
   mismatch.
*/
static unsigned char *sbsAlignment(
   fsl_dline *aLeft, int nLeft,       /* Text on the left */
   fsl_dline *aRight, int nRight      /* Text on the right */
){
  int i, j, k;                 /* Loop counters */
  int *a;                      /* One row of the Wagner matrix */
  int *pToFree;                /* Space that needs to be freed */
  unsigned char *aM;           /* Wagner result matrix */
  int nMatch, iMatch;          /* Number of matching lines and match score */
  int mnLen;                   /* MIN(nLeft, nRight) */
  int mxLen;                   /* MAX(nLeft, nRight) */
  int aBuf[100];               /* Stack space for a[] if nRight not to big */

  aM = (unsigned char *)fsl_malloc( (nLeft+1)*(nRight+1) );
  if(!aM) return NULL;
  if( nLeft==0 ){
    memset(aM, 2, nRight);
    return aM;
  }
  if( nRight==0 ){
    memset(aM, 1, nLeft);
    return aM;
  }

  /* This algorithm is O(N**2).  So if N is too big, bail out with a
     simple (but stupid and ugly) result that doesn't take too long. */
  mnLen = nLeft<nRight ? nLeft : nRight;
  if( nLeft*nRight>100000 ){
    memset(aM, 4, mnLen);
    if( nLeft>mnLen )  memset(aM+mnLen, 1, nLeft-mnLen);
    if( nRight>mnLen ) memset(aM+mnLen, 2, nRight-mnLen);
    return aM;
  }

  if( nRight < (int)(sizeof(aBuf)/sizeof(aBuf[0]))-1 ){
    pToFree = 0;
    a = aBuf;
  }else{
    a = pToFree = fsl_malloc( sizeof(a[0])*(nRight+1) );
    if(!a){
      fsl_free(aM);
      return NULL;
    }
  }

  /* Compute the best alignment */
  for(i=0; i<=nRight; i++){
    aM[i] = 2;
    a[i] = i*50;
  }
  aM[0] = 0;
  for(j=1; j<=nLeft; j++){
    int p = a[0];
    a[0] = p+50;
    aM[j*(nRight+1)] = 1;
    for(i=1; i<=nRight; i++){
      int m = a[i-1]+50;
      int d = 2;
      if( m>a[i]+50 ){
        m = a[i]+50;
        d = 1;
      }
      if( m>p ){
        int score = match_dline(&aLeft[j-1], &aRight[i-1]);
        if( (score<=63 || (i<j+1 && i>j-1)) && m>p+score ){
          m = p+score;
          d = 3 | score*4;
        }
      }
      p = a[i];
      a[i] = m;
      aM[j*(nRight+1)+i] = d;
    }
  }

  /* Compute the lowest-cost path back through the matrix */
  i = nRight;
  j = nLeft;
  k = (nRight+1)*(nLeft+1)-1;
  nMatch = iMatch = 0;
  while( i+j>0 ){
    unsigned char c = aM[k];
    if( c>=3 ){
      assert( i>0 && j>0 );
      i--;
      j--;
      nMatch++;
      iMatch += (c>>2);
      aM[k] = 3;
    }else if( c==2 ){
      assert( i>0 );
      i--;
    }else{
      assert( j>0 );
      j--;
    }
    k--;
    aM[k] = aM[j*(nRight+1)+i];
  }
  k++;
  i = (nRight+1)*(nLeft+1) - k;
  memmove(aM, &aM[k], i);

  /* If:
       (1) the alignment is more than 25% longer than the longest side, and
       (2) the average match cost exceeds 15
     Then this is probably an alignment that will be difficult for humans
     to read.  So instead, just show all of the right side inserted followed
     by all of the left side deleted.
    
     The coefficients for conditions (1) and (2) above are determined by
     experimentation.
  */
  mxLen = nLeft>nRight ? nLeft : nRight;
  if( i*4>mxLen*5 && (nMatch==0 || iMatch/nMatch>15) ){
    memset(aM, 4, mnLen);
    if( nLeft>mnLen )  memset(aM+mnLen, 1, nLeft-mnLen);
    if( nRight>mnLen ) memset(aM+mnLen, 2, nRight-mnLen);
  }

  /* Return the result */
  fsl_free(pToFree);
  return aM;
}

/*
   R[] is an array of six integer, two COPY/DELETE/INSERT triples for a
   pair of adjacent differences.  Return true if the gap between these
   two differences is so small that they should be rendered as a single
   edit.
*/
static int smallGap(int *R){
  return R[3]<=2 || R[3]<=(R[1]+R[2]+R[4]+R[5])/8;
}

/*
   Given a diff context in which the aEdit[] array has been filled
   in, compute a side-by-side diff into pOut.
*/
static int sbsDiff(
  fsl__diff_cx *p,       /* The computed diff */
  DiffOutState *pOut,        /* Write the results here */
  ReCompiled *pRe,   /* Only show changes that match this regex */
  u64 diffFlags      /* Flags controlling the diff */
){
  fsl_dline *A;     /* Left side of the diff */
  fsl_dline *B;     /* Right side of the diff */
  int rc = 0;
  int a = 0;    /* Index of next line in A[] */
  int b = 0;    /* Index of next line in B[] */
  int *R;       /* Array of COPY/DELETE/INSERT triples */
  int r;        /* Index into R[] */
  int nr;       /* Number of COPY/DELETE/INSERT triples to process */
  int mxr;      /* Maximum value for r */
  int i, j;     /* Loop counters */
  int m, ma, mb;/* Number of lines to output */
  int skip;     /* Number of lines to skip */
  static int nChunk = 0; /* Number of chunks of diff output seen so far */
  SbsLine s;    /* Output line buffer */
  int nContext; /* Lines of context above and below each change */
  int showDivider = 0;  /* True to show the divider */
  fsl_buffer unesc = fsl_buffer_empty;
  fsl_buffer aCols[5] = { /* Array of column blobs */
  fsl_buffer_empty_m, fsl_buffer_empty_m, fsl_buffer_empty_m,
  fsl_buffer_empty_m, fsl_buffer_empty_m
  }; 

  memset(&s, 0, sizeof(s));
  s.pOut = pOut;
  s.width = diff_width(diffFlags);
  nContext = diff_context_lines(diffFlags);
  s.escHtml = (diffFlags & DIFF_HTML)!=0;
  if( s.escHtml ){
    for(i=SBS_LNA; i<=SBS_TXTB; i++){
      s.apCols[i] = &aCols[i];
    }
  }else{
    for(i=SBS_LNA; i<=SBS_TXTB; i++){
      s.apCols[i] = &unesc;
    }
  }
  s.pRe = pRe;
  s.iStart = -1;
  s.iStart2 = 0;
  s.iEnd = -1;
  A = p->aFrom;
  B = p->aTo;
  R = p->aEdit;
  mxr = p->nEdit;
  while( mxr>2 && R[mxr-1]==0 && R[mxr-2]==0 ){ mxr -= 3; }

  for(r=0; r<mxr; r += 3*nr){
    /* Figure out how many triples to show in a single block */
    for(nr=1; R[r+nr*3]>0 && R[r+nr*3]<nContext*2; nr++){}
    /* printf("r=%d nr=%d\n", r, nr); */
#if 0
    /* MISSING: re/predicate bits. */
    /* If there is a regex, skip this block (generate no diff output)
       if the regex matches or does not match both insert and delete.
       Only display the block if one side matches but the other side does
       not.
    */
    if( pRe ){
      int hideBlock = 1;
      int xa = a, xb = b;
      for(i=0; hideBlock && i<nr; i++){
        int c1, c2;
        xa += R[r+i*3];
        xb += R[r+i*3];
        c1 = re_dline_match(pRe, &A[xa], R[r+i*3+1]);
        c2 = re_dline_match(pRe, &B[xb], R[r+i*3+2]);
        hideBlock = c1==c2;
        xa += R[r+i*3+1];
        xb += R[r+i*3+2];
      }
      if( hideBlock ){
        a = xa;
        b = xb;
        continue;
      }
    }
#endif
    /* For the current block comprising nr triples, figure out
       how many lines to skip. */
    if( R[r]>nContext ){
      skip = R[r] - nContext;
    }else{
      skip = 0;
    }

    /* Draw the separator between blocks */
    if( showDivider ){
      if( s.escHtml ){
        char zLn[10];
        fsl_snprintf(zLn, sizeof(zLn), "%d", a+skip+1);
        rc = sbsWriteSep(&s, strlen(zLn), SBS_LNA);
        if(!rc) rc = sbsWriteSep(&s, s.width, SBS_TXTA);
        if(!rc) rc = sbsWriteSep(&s, 0, SBS_MKR);
        if(!rc){
          fsl_snprintf(zLn, sizeof(zLn), "%d", b+skip+1);
          rc = sbsWriteSep(&s, strlen(zLn), SBS_LNB);
          if(!rc) rc = sbsWriteSep(&s, s.width, SBS_TXTB);
        }
      }else{
        diff_outf(pOut, "%.*c\n", s.width*2+16, '.');
      }
      if(rc) goto end;
    }
    showDivider = 1;
    nChunk++;
    if( s.escHtml ){
      rc = fsl_buffer_appendf(s.apCols[SBS_LNA],
                              "<span class=\"fsl-diff-chunk-%d\"></span>",
                              nChunk);
    }

    /* Show the initial common area */
    a += skip;
    b += skip;
    m = R[r] - skip;
    for(j=0; !rc && j<m; j++){
      rc = sbsWriteLineno(&s, a+j, SBS_LNA);
      if(rc) break;
      s.iStart = s.iEnd = -1;
      rc = sbsWriteText(&s, &A[a+j], SBS_TXTA);
      if(!rc) rc = sbsWriteMarker(&s, "   ", "");
      if(!rc) rc = sbsWriteLineno(&s, b+j, SBS_LNB);
      if(!rc) rc = sbsWriteText(&s, &B[b+j], SBS_TXTB);
    }
    if(rc) goto end;
    a += m;
    b += m;

    /* Show the differences */
    for(i=0; i<nr; i++){
      unsigned char *alignment;
      ma = R[r+i*3+1];   /* Lines on left but not on right */
      mb = R[r+i*3+2];   /* Lines on right but not on left */

      /* If the gap between the current diff and then next diff within the
         same block is not too great, then render them as if they are a
         single diff. */
      while( i<nr-1 && smallGap(&R[r+i*3]) ){
        i++;
        m = R[r+i*3];
        ma += R[r+i*3+1] + m;
        mb += R[r+i*3+2] + m;
      }

      alignment = sbsAlignment(&A[a], ma, &B[b], mb);
      if(!alignment){
        rc = FSL_RC_OOM;
        goto end;
      }
      for(j=0; !rc && ma+mb>0; j++){
        if( alignment[j]==1 ){
          /* Delete one line from the left */
          rc = sbsWriteLineno(&s, a, SBS_LNA);
          if(rc) goto end_align;
          s.iStart = 0;
          s.zStart = "<span class=\"fsl-diff-rm\">";
          s.iEnd = LENGTH(&A[a]);
          rc = sbsWriteText(&s, &A[a], SBS_TXTA);
          if(!rc) rc = sbsWriteMarker(&s, " <", "&lt;");
          if(!rc) rc = sbsWriteNewlines(&s);
          if(rc) goto end_align;
          assert( ma>0 );
          ma--;
          a++;
        }else if( alignment[j]==3 ){
          /* The left line is changed into the right line */
          rc = sbsWriteLineChange(&s, &A[a], a, &B[b], b);
          if(rc) goto end_align;
          assert( ma>0 && mb>0 );
          ma--;
          mb--;
          a++;
          b++;
        }else if( alignment[j]==2 ){
          /* Insert one line on the right */
          if( !s.escHtml ){
            rc = sbsWriteSpace(&s, s.width + 7, SBS_TXTA);
          }
          if(!rc) rc = sbsWriteMarker(&s, " > ", "&gt;");
          if(!rc) rc = sbsWriteLineno(&s, b, SBS_LNB);
          if(rc) goto end_align;
          s.iStart = 0;
          s.zStart = "<span class=\"fsl-diff-add\">";
          s.iEnd = LENGTH(&B[b]);
          rc = sbsWriteText(&s, &B[b], SBS_TXTB);
          if(rc) goto end_align;
          assert( mb>0 );
          mb--;
          b++;
        }else{
          /* Delete from the left and insert on the right */
          rc = sbsWriteLineno(&s, a, SBS_LNA);
          if(rc) goto end_align;
          s.iStart = 0;
          s.zStart = "<span class=\"fsl-diff-rm\">";
          s.iEnd = LENGTH(&A[a]);
          rc = sbsWriteText(&s, &A[a], SBS_TXTA);
          if(!rc) rc = sbsWriteMarker(&s, " | ", "|");
          if(!rc) rc = sbsWriteLineno(&s, b, SBS_LNB);
          if(rc) goto end_align;
          s.iStart = 0;
          s.zStart = "<span class=\"fsl-diff-add\">";
          s.iEnd = LENGTH(&B[b]);
          rc = sbsWriteText(&s, &B[b], SBS_TXTB);
          if(rc) goto end_align;
          ma--;
          mb--;
          a++;
          b++;
        }
      }
      end_align:
      fsl_free(alignment);
      if(rc) goto end;
      if( i<nr-1 ){
        m = R[r+i*3+3];
        for(j=0; !rc && j<m; j++){
          rc = sbsWriteLineno(&s, a+j, SBS_LNA);
          s.iStart = s.iEnd = -1;
          if(!rc) rc = sbsWriteText(&s, &A[a+j], SBS_TXTA);
          if(!rc) rc = sbsWriteMarker(&s, "   ", "");
          if(!rc) rc = sbsWriteLineno(&s, b+j, SBS_LNB);
          if(!rc) rc = sbsWriteText(&s, &B[b+j], SBS_TXTB);
        }
        if(rc) goto end;
        b += m;
        a += m;
      }
    }

    /* Show the final common area */
    assert( nr==i );
    m = R[r+nr*3];
    if( m>nContext ) m = nContext;
    for(j=0; !rc && j<m; j++){
      rc = sbsWriteLineno(&s, a+j, SBS_LNA);
      s.iStart = s.iEnd = -1;
      if(!rc) rc = sbsWriteText(&s, &A[a+j], SBS_TXTA);
      if(!rc) rc = sbsWriteMarker(&s, "   ", "");
      if(!rc) rc = sbsWriteLineno(&s, b+j, SBS_LNB);
      if(!rc) rc = sbsWriteText(&s, &B[b+j], SBS_TXTB);
    }
    if(rc) goto end;
  } /* diff triplet loop */
  assert(!rc);
  
  if( s.escHtml && (s.apCols[SBS_LNA]->used>0) ){
    rc = diff_out(pOut, "<table class=\"fsl-sbsdiff-cols\"><tr>\n", -1);
    for(i=SBS_LNA; !rc && i<=SBS_TXTB; i++){
      rc = sbsWriteColumn(pOut, s.apCols[i], i);
    }
    rc = diff_out(pOut, "</tr></table>\n", -1);
  }else if(unesc.used){
    rc = pOut->out(pOut->oState, unesc.mem, unesc.used);
  }

  end:
  for( i = 0; i < (int)(sizeof(aCols)/sizeof(aCols[0])); ++i ){
    fsl_buffer_clear(&aCols[i]);
  }
  fsl_buffer_clear(&unesc);
  return rc;
}

/** @internal

    Performs a text diff on two buffers, either streaming the
    output to the 3rd argument or returning the results as an
    array of copy/delete/insert triples via the final argument.

    ONE of the 3rd or final arguments must be set and the other
    must be NULL

    If the 3rd argument is not NULL:

    - The 4th argument is the opaque state value passed to
    the 3rd when emitting output.
    
    - contextLines specifies the number of lines of context for the
    diff. A negative contextLines value uses a default.

    - sbsWidth, if not 0, specifies a side-by-side diff width. A
    negative sbsWidth uses a default. A 0 sbsWidth indicates a
    unified-style diff output.

    If the final argument is not NULL then the result array of
    copy/delete/insert triples is assigned to *outRaw. Ownership is
    transfered to the caller, who must eventually pass it to
    fsl_free().

    Returns 0 on success, any number of other codes on error.
*/
static int fsl_diff_text_impl(
  fsl_buffer const *pA,   /* FROM file */
  fsl_buffer const *pB,   /* TO file */
  fsl_output_f out, void * outState,
  /* ReCompiled *pRe, */ /* Only output changes where this Regexp matches */
  short contextLines,
  short sbsWidth,
  int diffFlags_,    /* FSL_DIFF_* flags */
  int ** outRaw
){
  int rc;
  fsl__diff_cx c = fsl__diff_cx_empty;
  uint64_t diffFlags = fsl_diff_flags_convert(diffFlags_)
    | DIFF_CONTEXT_EX /* to shoehorn newer 0-handling semantics into
                         older (ported-in) code. */;
  if(!pA || !pB || (out && outRaw) || (!out && !outRaw)) return FSL_RC_MISUSE;
  else if(contextLines<0) contextLines = 5;
  else if(contextLines & ~FSL__LINE_LENGTH_MASK){
    contextLines = (int)FSL__LINE_LENGTH_MASK;
  }
  diffFlags |= (FSL__LINE_LENGTH_MASK & contextLines);
  /* Encode SBS width... */
  if(sbsWidth<0
     || ((DIFF_SIDEBYSIDE & diffFlags) && !sbsWidth) ) sbsWidth = 80;
  if(sbsWidth) diffFlags |= DIFF_SIDEBYSIDE;
  diffFlags |= ((int)(sbsWidth & 0xFF))<<16;
  if( diffFlags & DIFF_INVERT ){
    fsl_buffer const *pTemp = pA;
    pA = pB;
    pB = pTemp;
  }

  /* Prepare the input files */
  if( (diffFlags & DIFF_IGNORE_ALLWS)==DIFF_IGNORE_ALLWS ){
    c.cmpLine = fsl_dline_cmp_ignore_ws;
  }else{
    c.cmpLine = fsl_dline_cmp;
  }
  rc = fsl_break_into_dlines(fsl_buffer_cstr(pA), (fsl_int_t)fsl_buffer_size(pA),
                             (uint32_t*)&c.nFrom, &c.aFrom, diffFlags);
  if(rc) goto end;
  rc = fsl_break_into_dlines(fsl_buffer_cstr(pB), (fsl_int_t)fsl_buffer_size(pB),
                             (uint32_t*)&c.nTo, &c.aTo, diffFlags);
  if(rc) goto end;

  /* Compute the difference */
  rc = fsl__diff_all(&c);
  //fsl__dump_triples(&c, __FILE__, __LINE__);
  if(rc) goto end;
  if( (diffFlags & DIFF_NOTTOOBIG)!=0 ){
    int i, m, n;
    int *a = c.aEdit;
    int mx = c.nEdit;
    for(i=m=n=0; i<mx; i+=3){ m += a[i]; n += a[i+1]+a[i+2]; }
    if( !n || n>10000 ){
      rc = FSL_RC_RANGE;
      /* diff_errmsg(pOut, DIFF_TOO_MANY_CHANGES, diffFlags); */
      goto end;
    }
  }
  //fsl__dump_triples(&c, __FILE__, __LINE__);
  if( (diffFlags & DIFF_NOOPT)==0 ){
    fsl__diff_optimize(&c);
  }
  //fsl__dump_triples(&c, __FILE__, __LINE__);

  if( out ){
    /* Compute a context or side-by-side diff */
    /* MISSING: regex support */
    DiffOutState dos = DiffOutState_empty;
    dos.out = out;
    dos.oState = outState;
    dos.ansiColor = !!(diffFlags_ & FSL_DIFF_ANSI_COLOR);
    if( diffFlags & DIFF_SIDEBYSIDE ){
      rc = sbsDiff(&c, &dos, NULL/*pRe*/, diffFlags);
    }else{
      rc = contextDiff(&c, &dos, NULL/*pRe*/, diffFlags);
    }
  }else if(outRaw){
    /* If a context diff is not requested, then return the
       array of COPY/DELETE/INSERT triples. */
    *outRaw = c.aEdit;
    c.aEdit = NULL;
  }
  end:
  fsl_free(c.aFrom);
  fsl_free(c.aTo);
  fsl_free(c.aEdit);
  return rc;
}

int fsl__diff_text_raw(fsl_buffer const *p1, fsl_buffer const *p2,
                      int diffFlags, int ** outRaw){
  return fsl_diff_text_impl(p1, p2, NULL, NULL, 0, 0, diffFlags, outRaw);
}

int fsl_diff_text(fsl_buffer const *pA, fsl_buffer const *pB,
                  fsl_output_f out, void * outState,
                  short contextLines,
                  short sbsWidth,
                  int diffFlags ){
  return fsl_diff_text_impl(pA, pB, out, outState,
                            contextLines, sbsWidth, diffFlags, NULL );
}

int fsl_diff_text_to_buffer(fsl_buffer const *pA, fsl_buffer const *pB,
                            fsl_buffer * pOut,
                            short contextLines,
                            short sbsWidth,
                            int diffFlags ){
  return (pA && pB && pOut)
    ? fsl_diff_text_impl(pA, pB, fsl_output_f_buffer, pOut,
                         contextLines, sbsWidth, diffFlags, NULL )
    : FSL_RC_MISUSE;
}

#undef MARKER
#undef LENGTH
#undef DIFF_CONTEXT_MASK
#undef DIFF_WIDTH_MASK
#undef DIFF_IGNORE_EOLWS
#undef DIFF_IGNORE_ALLWS
#undef DIFF_SIDEBYSIDE
#undef DIFF_VERBOSE
#undef DIFF_BRIEF
#undef DIFF_HTML
#undef DIFF_LINENO
#undef DIFF_NOOPT
#undef DIFF_INVERT
#undef DIFF_CONTEXT_EX
#undef DIFF_NOTTOOBIG
#undef DIFF_STRIP_EOLCR
#undef SBS_LNA
#undef SBS_TXTA
#undef SBS_MKR
#undef SBS_LNB
#undef SBS_TXTB

#undef ANSI_COLOR_BLACK
#undef ANSI_COLOR_RED
#undef ANSI_COLOR_GREEN
#undef ANSI_COLOR_YELLOW
#undef ANSI_COLOR_BLUE
#undef ANSI_COLOR_MAGENTA
#undef ANSI_COLOR_CYAN
#undef ANSI_COLOR_WHITE
#undef ANSI_BG_BLACK
#undef ANSI_BG_RED
#undef ANSI_BG_GREEN
#undef ANSI_BG_YELLOW
#undef ANSI_BG_BLUE
#undef ANSI_BG_MAGENTA
#undef ANSI_BG_CYAN
#undef ANSI_BG_WHITE
#undef ANSI_RESET_COLOR
#undef ANSI_RESET_ALL
#undef ANSI_RESET
#undef ANSI_DIFF_ADD
#undef ANSI_DIFF_MOD
#undef ANSI_DIFF_RM
#endif /*FSL_OMIT_DEPRECATED*/
/* end of file ./src/diff.c */
/* start of file ./src/diff2.c */
/* -*- Mode: C; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 2 -*- */ 
/* vim: set ts=2 et sw=2 tw=80: */
/*
  Copyright 2013-2021 The Libfossil Authors, see LICENSES/BSD-2-Clause.txt

  SPDX-License-Identifier: BSD-2-Clause-FreeBSD
  SPDX-FileCopyrightText: 2021 The Libfossil Authors
  SPDX-ArtifactOfProjectName: Libfossil
  SPDX-FileType: Code

  Heavily indebted to the Fossil SCM project (https://fossil-scm.org).
*/
/**
   This file houses the "2nd generation" diff-generation APIs. This
   code is a straight port of those algorithms from the Fossil SCM
   project, initially implemented by D. Richard Hipp, ported and
   the license re-assigned to this project with this consent.
*/
#include <memory.h>
#include <stdlib.h>
#include <string.h> /* for memmove()/strlen() */

#include <stdio.h>
#define MARKER(pfexp)                                               \
  do{ printf("MARKER: %s:%d:%s():\t",__FILE__,__LINE__,__func__);   \
    printf pfexp;                                                   \
  } while(0)


const fsl_dibu_opt fsl_dibu_opt_empty = fsl_dibu_opt_empty_m;
const fsl_dibu fsl_dibu_empty = fsl_dibu_empty_m;
const fsl_dline fsl_dline_empty = fsl_dline_empty_m;
const fsl_dline_change fsl_dline_change_empty = fsl_dline_change_empty_m;
const fsl__diff_cx fsl__diff_cx_empty = fsl__diff_cx_empty_m;

void fsl__diff_cx_clean(fsl__diff_cx * const cx){
  fsl_free(cx->aFrom);
  fsl_free(cx->aTo);
  fsl_free(cx->aEdit);
  cx->aFrom = cx->aTo = NULL;
  cx->aEdit = NULL;
  *cx = fsl__diff_cx_empty;
}

/**
   Counts the number of lines in the first n bytes of the given 
   string. If n<0 then fsl_strlen() is used to count it. 

   It includes the last line in the count even if it lacks the \n
   terminator. If an empty string is passed in, the number of lines
   is zero.

   For the purposes of this function, a string is considered empty if
   it contains no characters OR contains only NUL characters.

   If the input appears to be plain text it returns true and, if nOut
   is not NULL, writes the number of lines there. If the input appears
   to be binary, returns false and does not modify nOut.
*/
FSL_EXPORT bool fsl_count_lines(const char *z, fsl_int_t n, uint32_t * nOut );

bool fsl_count_lines(const char *z, fsl_int_t n, uint32_t * nOut ){
  uint32_t nLine;
  const char *zNL, *z2;
  if(n<0) n = (fsl_int_t)fsl_strlen(z);
  for(nLine=0, z2=z; (zNL = strchr(z2,'\n'))!=0; z2=zNL+1, nLine++){}
  if( z2[0]!='\0' ){
    nLine++;
    do{ z2++; }while( z2[0]!='\0' );
  }
  if( n!=(fsl_int_t)(z2-z) ) return false;
  if( nOut ) *nOut = nLine;
  return true;
}

int fsl_break_into_dlines(const char *z, fsl_int_t n,
                          uint32_t *pnLine,
                          fsl_dline **pOut, uint64_t diffFlags){
  uint32_t nLine, i, k, nn, s, x;
  uint64_t h, h2;
  fsl_dline *a = 0;
  const char *zNL;

  if(!z || !n){
    *pnLine = 0;
    *pOut = NULL;
    return 0;
  }
  if( !fsl_count_lines(z, n, &nLine) ){
    return FSL_RC_DIFF_BINARY;
  }
  assert( nLine>0 || z[0]=='\0' );
  if(nLine>0){
    a = fsl_malloc( sizeof(a[0])*nLine );
    if(!a) return FSL_RC_OOM;
    memset(a, 0, sizeof(a[0])*nLine);
  }else{
    *pnLine = 0;
    *pOut = a;
    return 0;
  }
  assert( a );
  i = 0;
  do{
    zNL = strchr(z,'\n');
    if( zNL==0 ) zNL = z+n;
    nn = (uint32_t)(zNL - z);
    if( nn>FSL__LINE_LENGTH_MASK ){
      fsl_free(a);
      *pOut = 0;
      *pnLine = 0;
      return FSL_RC_DIFF_BINARY;
    }
    a[i].z = z;
    k = nn;
    if( diffFlags & FSL_DIFF2_STRIP_EOLCR ){
      if( k>0 && z[k-1]=='\r' ){ k--; }
    }
    a[i].n = k;
    s = 0;
    if( diffFlags & FSL_DIFF2_IGNORE_EOLWS ){
      while( k>0 && fsl_isspace(z[k-1]) ){ k--; }
    }
    if( (diffFlags & FSL_DIFF2_IGNORE_ALLWS)
        ==FSL_DIFF2_IGNORE_ALLWS ){
      uint32_t numws = 0;
      while( s<k && fsl_isspace(z[s]) ){ ++s; }
      for(h=0, x=s; x<k; ++x){
        char c = z[x];
        if( fsl_isspace(c) ){
          ++numws;
        }else{
          h = (h^c)*9000000000000000041LL;
        }
      }
      k -= numws;
    }else{
      uint32_t k2 = k & ~0x7;
      uint64_t m;
      for(h=0, x=s; x<k2; x += 8){
        memcpy(&m, z+x, 8);
        h = (h^m)*9000000000000000041LL;
      }
      m = 0;
      memcpy(&m, z+x, k-k2);
      h ^= m;
    }
    a[i].indent = s;
    a[i].h = h = ((h%281474976710597LL)<<FSL__LINE_LENGTH_MASK_SZ) | (k-s);
    h2 = h % nLine;
    a[i].iNext = a[h2].iHash;
    a[h2].iHash = i+1;
    z += nn+1; n -= nn+1;
    i++;
  }while( zNL[0]!='\0' && zNL[1]!='\0' );
  assert( i==nLine );

  *pnLine = nLine;
  *pOut = a;
  return 0;
}

int fsl_dline_cmp(const fsl_dline * const pA,
                  const fsl_dline * const pB){
  if( pA->h!=pB->h ) return 1;
  return memcmp(pA->z,pB->z, pA->h&FSL__LINE_LENGTH_MASK);
}

int fsl_dline_cmp_ignore_ws(const fsl_dline * const pA,
                            const fsl_dline * const pB){
  unsigned short a = pA->indent, b = pB->indent;
  if( pA->h==pB->h ){
    while( a<pA->n || b<pB->n ){
      if( a<pA->n && b<pB->n && pA->z[a++] != pB->z[b++] ) return 1;
      while( a<pA->n && fsl_isspace(pA->z[a])) ++a;
      while( b<pB->n && fsl_isspace(pB->z[b])) ++b;
    }
    return pA->n-a != pB->n-b;
  }
  return 1;
}

/*
** The two text segments zLeft and zRight are known to be different on
** both ends, but they might have  a common segment in the middle.  If
** they do not have a common segment, return 0.  If they do have a large
** common segment, return non-0 and before doing so set:
**
**   aLCS[0] = start of the common segment in zLeft
**   aLCS[1] = end of the common segment in zLeft
**   aLCS[2] = start of the common segment in zLeft
**   aLCS[3] = end of the common segment in zLeft
**
** This computation is for display purposes only and does not have to be
** optimal or exact.
*/
static int textLCS2(
  const char *zLeft,  uint32_t nA, /* String on the left */
  const char *zRight, uint32_t nB, /* String on the right */
  uint32_t *aLCS                   /* Identify bounds of LCS here */
){
  const unsigned char *zA = (const unsigned char*)zLeft;    /* left string */
  const unsigned char *zB = (const unsigned char*)zRight;   /* right string */
  uint32_t i, j, k;               /* Loop counters */
  uint32_t lenBest = 0;           /* Match length to beat */

  for(i=0; i<nA-lenBest; i++){
    unsigned char cA = zA[i];
    if( (cA&0xc0)==0x80 ) continue;
    for(j=0; j<nB-lenBest; j++ ){
      if( zB[j]==cA ){
        for(k=1; j+k<nB && i+k<nA && zB[j+k]==zA[i+k]; k++){}
        while( (zB[j+k]&0xc0)==0x80 ){ k--; }
        if( k>lenBest ){
          lenBest = k;
          aLCS[0] = i;
          aLCS[1] = i+k;
          aLCS[2] = j;
          aLCS[3] = j+k;
        }
      }
    }
  }
  return lenBest>0;
}

/*
** Find the smallest spans that are different between two text strings
** that are known to be different on both ends. Returns the number
** of entries in p->a which get populated.
*/
static unsigned short textLineChanges(
  const char *zLeft,  uint32_t nA, /* String on the left */
  const char *zRight, uint32_t nB, /* String on the right */
  fsl_dline_change * const p             /* Write results here */
){
  p->n = 1;
  p->a[0].iStart1 = 0;
  p->a[0].iLen1 = nA;
  p->a[0].iStart2 = 0;
  p->a[0].iLen2 = nB;
  p->a[0].isMin = 0;
  while( p->n<fsl_dline_change_max_spans-1 ){
    int mxi = -1;
    int mxLen = -1;
    int x, i;
    uint32_t aLCS[4] = {0,0,0,0};
    struct fsl_dline_change_span *a, *b;
    for(i=0; i<p->n; i++){
      if( p->a[i].isMin ) continue;
      x = p->a[i].iLen1;
      if( p->a[i].iLen2<x ) x = p->a[i].iLen2;
      if( x>mxLen ){
        mxLen = x;
        mxi = i;
      }
    }
    if( mxLen<6 ) break;
    x = textLCS2(zLeft + p->a[mxi].iStart1, p->a[mxi].iLen1,
                 zRight + p->a[mxi].iStart2, p->a[mxi].iLen2, aLCS);
    if( x==0 ){
      p->a[mxi].isMin = 1;
      continue;
    }
    a = p->a+mxi;
    b = a+1;
    if( mxi<p->n-1 ){
      memmove(b+1, b, sizeof(*b)*(p->n-mxi-1));
    }
    p->n++;
    b->iStart1 = a->iStart1 + aLCS[1];
    b->iLen1 = a->iLen1 - aLCS[1];
    a->iLen1 = aLCS[0];
    b->iStart2 = a->iStart2 + aLCS[3];
    b->iLen2 = a->iLen2 - aLCS[3];
    a->iLen2 = aLCS[2];
    b->isMin = 0;
  }
  return p->n;
}

/*
** Return true if the string starts with n spaces
*/
static int allSpaces(const char *z, int n){
  int i;
  for(i=0; i<n && fsl_isspace(z[i]); ++i){}
  return i==n;
}

/*
** Try to improve the human-readability of the fsl_dline_change p.
**
** (1)  If the first change span shows a change of indentation, try to
**      move that indentation change to the left margin.
**
** (2)  Try to shift changes so that they begin or end with a space.
*/
static void improveReadability(
  const char *zA,  /* Left line of the change */
  const char *zB,  /* Right line of the change */
  fsl_dline_change * const p /* The fsl_dline_change to be adjusted */
){
  int j, n, len;
  if( p->n<1 ) return;

  /* (1) Attempt to move indentation changes to the left margin */
  if( p->a[0].iLen1==0
   && (len = p->a[0].iLen2)>0
   && (j = p->a[0].iStart2)>0
   && zB[0]==zB[j]
   && allSpaces(zB, j)
  ){
    for(n=1; n<len && n<j && zB[j]==zB[j+n]; n++){}
    if( n<len ){
      memmove(&p->a[1], &p->a[0], sizeof(p->a[0])*p->n);
      p->n++;
      p->a[0] = p->a[1];
      p->a[1].iStart2 += n;
      p->a[1].iLen2 -= n;
      p->a[0].iLen2 = n;
    }
    p->a[0].iStart1 = 0;
    p->a[0].iStart2 = 0;
  }else
  if( p->a[0].iLen2==0
   && (len = p->a[0].iLen1)>0
   && (j = p->a[0].iStart1)>0
   && zA[0]==zA[j]
   && allSpaces(zA, j)
  ){
    for(n=1; n<len && n<j && zA[j]==zA[j+n]; n++){}
    if( n<len ){
      memmove(&p->a[1], &p->a[0], sizeof(p->a[0])*p->n);
      p->n++;
      p->a[0] = p->a[1];
      p->a[1].iStart1 += n;
      p->a[1].iLen1 -= n;
      p->a[0].iLen1 = n;
    }
    p->a[0].iStart1 = 0;
    p->a[0].iStart2 = 0;
  }

  /* (2) Try to shift changes so that they begin or end with a
  ** space.  (TBD) */
}

void fsl_dline_change_spans(const fsl_dline *pLeft, const fsl_dline *pRight,
                            fsl_dline_change * const p){
  /* fossil(1) counterpart ==> diff.c oneLineChange() */
  int nLeft;           /* Length of left line in bytes */
  int nRight;          /* Length of right line in bytes */
  int nShort;          /* Shortest of left and right */
  int nPrefix;         /* Length of common prefix */
  int nSuffix;         /* Length of common suffix */
  int nCommon;         /* Total byte length of suffix and prefix */
  const char *zLeft;   /* Text of the left line */
  const char *zRight;  /* Text of the right line */
  int nLeftDiff;       /* nLeft - nPrefix - nSuffix */
  int nRightDiff;      /* nRight - nPrefix - nSuffix */

  nLeft = pLeft->n;
  zLeft = pLeft->z;
  nRight = pRight->n;
  zRight = pRight->z;
  nShort = nLeft<nRight ? nLeft : nRight;

  nPrefix = 0;
  while( nPrefix<nShort && zLeft[nPrefix]==zRight[nPrefix] ){
    nPrefix++;
  }
  if( nPrefix<nShort ){
    while( nPrefix>0 && (zLeft[nPrefix]&0xc0)==0x80 ) nPrefix--;
  }
  nSuffix = 0;
  if( nPrefix<nShort ){
    while( nSuffix<nShort
           && zLeft[nLeft-nSuffix-1]==zRight[nRight-nSuffix-1] ){
      nSuffix++;
    }
    if( nSuffix<nShort ){
      while( nSuffix>0 && (zLeft[nLeft-nSuffix]&0xc0)==0x80 ) nSuffix--;
    }
    if( nSuffix==nLeft || nSuffix==nRight ) nPrefix = 0;
  }
  nCommon = nPrefix + nSuffix;

  /* If the prefix and suffix overlap, that means that we are dealing with
  ** a pure insertion or deletion of text that can have multiple alignments.
  ** Try to find an alignment to begins and ends on whitespace, or on
  ** punctuation, rather than in the middle of a name or number.
  */
  if( nCommon > nShort ){
    int iBest = -1;
    int iBestVal = -1;
    int i;
    int nLong = nLeft<nRight ? nRight : nLeft;
    int nGap = nLong - nShort;
    for(i=nShort-nSuffix; i<=nPrefix; i++){
       int iVal = 0;
       char c = zLeft[i];
       if( fsl_isspace(c) ){
         iVal += 5;
       }else if( !fsl_isalnum(c) ){
         iVal += 2;
       }
       c = zLeft[i+nGap-1];
       if( fsl_isspace(c) ){
         iVal += 5;
       }else if( !fsl_isalnum(c) ){
         iVal += 2;
       }
       if( iVal>iBestVal ){
         iBestVal = iVal;
         iBest = i;
       }
    }
    nPrefix = iBest;
    nSuffix = nShort - nPrefix;
    nCommon = nPrefix + nSuffix;
  }

  /* A single chunk of text inserted */
  if( nCommon==nLeft ){
    p->n = 1;
    p->a[0].iStart1 = nPrefix;
    p->a[0].iLen1 = 0;
    p->a[0].iStart2 = nPrefix;
    p->a[0].iLen2 = nRight - nCommon;
    improveReadability(zLeft, zRight, p);
    return;
  }

  /* A single chunk of text deleted */
  if( nCommon==nRight ){
    p->n = 1;
    p->a[0].iStart1 = nPrefix;
    p->a[0].iLen1 = nLeft - nCommon;
    p->a[0].iStart2 = nPrefix;
    p->a[0].iLen2 = 0;
    improveReadability(zLeft, zRight, p);
    return;
  }

  /* At this point we know that there is a chunk of text that has
  ** changed between the left and the right.  Check to see if there
  ** is a large unchanged section in the middle of that changed block.
  */
  nLeftDiff = nLeft - nCommon;
  nRightDiff = nRight - nCommon;
  if( nLeftDiff >= 4
   && nRightDiff >= 4
   && textLineChanges(&zLeft[nPrefix], nLeftDiff,
                      &zRight[nPrefix], nRightDiff, p)>1
  ){
    int i;
    for(i=0; i<p->n; i++){
      p->a[i].iStart1 += nPrefix;
      p->a[i].iStart2 += nPrefix;
    }
    improveReadability(zLeft, zRight, p);
    return;
  }

  /* If all else fails, show a single big change between left and right */
  p->n = 1;
  p->a[0].iStart1 = nPrefix;
  p->a[0].iLen1 = nLeft - nCommon;
  p->a[0].iStart2 = nPrefix;
  p->a[0].iLen2 = nRight - nCommon;
  improveReadability(zLeft, zRight, p);
}



/*
** The threshold at which diffBlockAlignment transitions from the
** O(N*N) Wagner minimum-edit-distance algorithm to a less process
** O(NlogN) divide-and-conquer approach.
*/
#define DIFF_ALIGN_MX  1225

/**
   FSL_DIFF_SMALL_GAP=0 is a temporary(? as of 2022-01-04) patch for a
   cosmetic-only (but unsightly) quirk of the diff engine where it
   produces a pair of identical DELETE/INSERT lines. Richard's
   preliminary solution for it is to remove the "small gap merging,"
   but he notes (in fossil /chat) that he's not recommending this as
   "the" fix.

   PS: we colloquially know this as "the lineno diff" because it was first
   reported in a diff which resulted in:

```
-  int     lineno;
+  int     lineno;
```

   (No, there are no whitespace changes there.)

   To reiterate, though: this is not a "bug," in that it does not
   cause incorrect results when applying the resulting unfified-diff
   patches. It does, however, cause confusion for human users.


   Here are two inputs which, when diffed, expose the lineno behavior:

   #1:

```
struct fnc_diff_view_state {
  int     first_line_onscreen;
  int     last_line_onscreen;
  int     diff_flags;
  int     context;
  int     sbs;
  int     matched_line;
  int     current_line;
  int     lineno;
  size_t     ncols;
  size_t     nlines;
  off_t    *line_offsets;
  bool     eof;
  bool     colour;
  bool     showmeta;
  bool     showln;
};
```

   #2:

```
struct fnc_diff_view_state {
  int     first_line_onscreen;
  int     last_line_onscreen;
  int     diff_flags;
  int     context;
  int     sbs;
  int     matched_line;
  int     selected_line;
  int     lineno;
  int     gtl;
  size_t     ncols;
  size_t     nlines;
  off_t    *line_offsets;
  bool     eof;
  bool     colour;
  bool     showmeta;
  bool     showln;
};
```

   Result without this patch:

```
Index: X.0
==================================================================
--- X.0
+++ X.1
@@ -3,15 +3,16 @@
   int     last_line_onscreen;
   int     diff_flags;
   int     context;
   int     sbs;
   int     matched_line;
+  int     selected_line;
-  int     current_line;
-  int     lineno;
+  int     lineno;
+  int     gtl;
   size_t     ncols;
   size_t     nlines;
   off_t    *line_offsets;
   bool     eof;
   bool     colour;
   bool     showmeta;
   bool     showln;
 };
```

    And with the patch:

```
Index: X.0
==================================================================
--- X.0
+++ X.1
@@ -3,15 +3,16 @@
   int     last_line_onscreen;
   int     diff_flags;
   int     context;
   int     sbs;
   int     matched_line;
-  int     current_line;
+  int     selected_line;
   int     lineno;
+  int     gtl;
   size_t     ncols;
   size_t     nlines;
   off_t    *line_offsets;
   bool     eof;
   bool     colour;
   bool     showmeta;
   bool     showln;
 };
```

*/
#define FSL_DIFF_SMALL_GAP 0

#if FSL_DIFF_SMALL_GAP
/*
** R[] is an array of six integer, two COPY/DELETE/INSERT triples for a
** pair of adjacent differences.  Return true if the gap between these
** two differences is so small that they should be rendered as a single
** edit.
*/
static int smallGap2(const int *R, int ma, int mb){
  int m = R[3];
  ma += R[4] + m;
  mb += R[5] + m;
  if( ma*mb>DIFF_ALIGN_MX ) return 0;
  return m<=2 || m<=(R[1]+R[2]+R[4]+R[5])/8;
}
#endif

static unsigned short diff_opt_context_lines(fsl_dibu_opt const * opt){
  const unsigned short dflt = 5;
  unsigned short n = opt ? opt->contextLines : dflt;
  if( !n && (opt->diffFlags & FSL_DIFF2_CONTEXT_ZERO)==0 ){
    n = dflt;
  }
  return n;
}

/*
** Minimum of two values
*/
static int diffMin(int a, int b){ return a<b ? a : b; }

/****************************************************************************/
/*
** Return the number between 0 and 100 that is smaller the closer pA and
** pB match.  Return 0 for a perfect match.  Return 100 if pA and pB are
** completely different.
**
** The current algorithm is as follows:
**
** (1) Remove leading and trailing whitespace.
** (2) Truncate both strings to at most 250 characters
** (3) If the two strings have a common prefix, measure that prefix
** (4) Find the length of the longest common subsequence that is
**     at least 150% longer than the common prefix.
** (5) Longer common subsequences yield lower scores.
*/
static int match_dline2(const fsl_dline *pA, const fsl_dline *pB){
  const char *zA;            /* Left string */
  const char *zB;            /* right string */
  int nA;                    /* Bytes in zA[] */
  int nB;                    /* Bytes in zB[] */
  int nMin;
  int nPrefix;
  int avg;                   /* Average length of A and B */
  int i, j, k;               /* Loop counters */
  int best = 0;              /* Longest match found so far */
  int score;                 /* Final score.  0..100 */
  unsigned char c;           /* Character being examined */
  unsigned char aFirst[256]; /* aFirst[X] = index in zB[] of first char X */
  unsigned char aNext[252];  /* aNext[i] = index in zB[] of next zB[i] char */

  zA = pA->z;
  zB = pB->z;
  nA = pA->n;
  nB = pB->n;
  while( nA>0 && (unsigned char)zA[0]<=' ' ){ nA--; zA++; }
  while( nA>0 && (unsigned char)zA[nA-1]<=' ' ){ nA--; }
  while( nB>0 && (unsigned char)zB[0]<=' ' ){ nB--; zB++; }
  while( nB>0 && (unsigned char)zB[nB-1]<=' ' ){ nB--; }
  if( nA>250 ) nA = 250;
  if( nB>250 ) nB = 250;
  avg = (nA+nB)/2;
  if( avg==0 ) return 0;
  nMin = nA;
  if( nB<nMin ) nMin = nB;
  if( nMin==0 ) return 68;
  for(nPrefix=0; nPrefix<nMin && zA[nPrefix]==zB[nPrefix]; nPrefix++){}
  best = 0;
  if( nPrefix>5 && nPrefix>nMin/2 ){
    best = nPrefix*3/2;
    if( best>=avg - 2 ) best = avg - 2;
  }
  if( nA==nB && memcmp(zA, zB, nA)==0 ) return 0;
  memset(aFirst, 0xff, sizeof(aFirst));
  zA--; zB--;   /* Make both zA[] and zB[] 1-indexed */
  for(i=nB; i>0; i--){
    c = (unsigned char)zB[i];
    aNext[i] = aFirst[c];
    aFirst[c] = i;
  }
  for(i=1; i<=nA-best; i++){
    c = (unsigned char)zA[i];
    for(j=aFirst[c]; j<nB-best && memcmp(&zA[i],&zB[j],best)==0; j = aNext[j]){
      int limit = diffMin(nA-i, nB-j);
      for(k=best; k<=limit && zA[k+i]==zB[k+j]; k++){}
      if( k>best ) best = k;
    }
  }
  score = (best>=avg) ? 0 : (avg - best)*100/avg;

#if 0
  fprintf(stderr, "A: [%.*s]\nB: [%.*s]\nbest=%d avg=%d score=%d\n",
  nA, zA+1, nB, zB+1, best, avg, score);
#endif

  /* Return the result */
  return score;
}

/*
** There is a change block in which nLeft lines of text on the left are
** converted into nRight lines of text on the right.  This routine computes
** how the lines on the left line up with the lines on the right.
**
** The return value is a buffer of unsigned characters, obtained from
** fossil_malloc().  (The caller needs to free the return value using
** fossil_free().)  Entries in the returned array have values as follows:
**
**    1.  Delete the next line of pLeft.
**    2.  Insert the next line of pRight.
**    3.  The next line of pLeft changes into the next line of pRight.
**    4.  Delete one line from pLeft and add one line to pRight.
**
** The length of the returned array will be at most nLeft+nRight bytes.
** If the first bytes is 4,  that means we could not compute reasonable
** alignment between the two blocks.
**
** Algorithm:  Wagner's minimum edit-distance algorithm, modified by
** adding a cost to each match based on how well the two rows match
** each other.  Insertion and deletion costs are 50.  Match costs
** are between 0 and 100 where 0 is a perfect match 100 is a complete
** mismatch.
*/
static int diffBlockAlignment(
  const fsl_dline *aLeft, int nLeft,     /* Text on the left */
  const fsl_dline *aRight, int nRight,   /* Text on the right */
  fsl_dibu_opt * const pOpt,             /* Configuration options */
  unsigned char **pResult, /* Raw result */
  unsigned *pNResult               /* OUTPUT: length of result */
){
  int i, j, k;                 /* Loop counters */
  int *a = 0;                  /* One row of the Wagner matrix */
  int *pToFree = 0;            /* Space that needs to be freed */
  unsigned char *aM = 0;       /* Wagner result matrix */
  int nMatch, iMatch;          /* Number of matching lines and match score */
  int aBuf[100];               /* Stack space for a[] if nRight not to big */
  int rc = 0;

  if( nLeft==0 ){
    aM = fsl_malloc( nRight + 2 );
    if(!aM) return FSL_RC_OOM;
    memset(aM, 2, nRight);
    *pNResult = nRight;
    *pResult = aM;
    return 0;
  }
  if( nRight==0 ){
    aM = fsl_malloc( nLeft + 2 );
    if(!aM) return FSL_RC_OOM;
    memset(aM, 1, nLeft);
    *pNResult = nLeft;
    *pResult = aM;
    return 0;
  }

  /* For large alignments, use a divide and conquer algorithm that is
  ** O(NlogN).  The result is not as precise, but this whole thing is an
  ** approximation anyhow, and the faster response time is an acceptable
  ** trade-off for reduced precision.
  */
  if( nLeft*nRight>DIFF_ALIGN_MX
      && (pOpt->diffFlags & FSL_DIFF2_SLOW_SBS)==0 ){
    const fsl_dline *aSmall;   /* The smaller of aLeft and aRight */
    const fsl_dline *aBig;     /* The larger of aLeft and aRight */
    int nSmall, nBig;      /* Size of aSmall and aBig.  nSmall<=nBig */
    int iDivSmall, iDivBig;  /* Divider point for aSmall and aBig */
    int iDivLeft, iDivRight; /* Divider point for aLeft and aRight */
    unsigned char *a1 = 0, *a2 = 0;  /* Results of the alignments on two halves */
    unsigned int n1, n2;     /* Number of entries in a1 and a2 */
    int score, bestScore;    /* Score and best score seen so far */
    if( nLeft>nRight ){
      aSmall = aRight;
      nSmall = nRight;
      aBig = aLeft;
      nBig = nLeft;
    }else{
      aSmall = aLeft;
      nSmall = nLeft;
      aBig = aRight;
      nBig = nRight;
    }
    iDivBig = nBig/2;
    iDivSmall = nSmall/2;
    bestScore = 10000;
    for(i=0; i<nSmall; i++){
      score = match_dline2(aBig+iDivBig, aSmall+i) + abs(i-nSmall/2)*2;
      if( score<bestScore ){
        bestScore = score;
        iDivSmall = i;
      }
    }
    if( aSmall==aRight ){
      iDivRight = iDivSmall;
      iDivLeft = iDivBig;
    }else{
      iDivRight = iDivBig;
      iDivLeft = iDivSmall;
    }
    rc = diffBlockAlignment(aLeft,iDivLeft,aRight, iDivRight,
                            pOpt, &a1, &n1);
    if(!rc){
      rc = diffBlockAlignment(aLeft+iDivLeft, nLeft-iDivLeft,
                              aRight+iDivRight, nRight-iDivRight,
                              pOpt, &a2, &n2);
    }
    if(rc) goto bail;
    void * a1Re = fsl_realloc(a1, n1+n2 );
    if(!a1Re) goto bail;
    a1 = (unsigned char *)a1Re;
    memcpy(a1+n1,a2,n2);
    fsl_free(a2);
    a2 = 0;
    *pNResult = n1+n2;
    *pResult = a1;
    return 0;
    bail:
    assert(0!=rc);
    fsl_free( a1 );
    fsl_free( a2 );
    goto end;
  }

  /* If we reach this point, we will be doing an O(N*N) Wagner minimum
  ** edit distance to compute the alignment.
  */
  if( nRight < (int)(sizeof(aBuf)/sizeof(aBuf[0]))-1 ){
    pToFree = 0;
    a = aBuf;
  }else{
    a = pToFree = fsl_malloc( sizeof(a[0])*(nRight+1) );
    if(!a){
      rc = FSL_RC_OOM;
      goto end;
    }
  }
  aM = fsl_malloc( (nLeft+1)*(nRight+1) );
  if(!aM){
    rc = FSL_RC_OOM;
    goto end;
  }

  /* Compute the best alignment */
  for(i=0; i<=nRight; i++){
    aM[i] = 2;
    a[i] = i*50;
  }
  aM[0] = 0;
  for(j=1; j<=nLeft; j++){
    int p = a[0];
    a[0] = p+50;
    aM[j*(nRight+1)] = 1;
    for(i=1; i<=nRight; i++){
      int m = a[i-1]+50;
      int d = 2;
      if( m>a[i]+50 ){
        m = a[i]+50;
        d = 1;
      }
      if( m>p ){
        int const score =
          match_dline2(&aLeft[j-1], &aRight[i-1]);
        if( (score<=90 || (i<j+1 && i>j-1)) && m>p+score ){
          m = p+score;
          d = 3 | score*4;
        }
      }
      p = a[i];
      a[i] = m;
      aM[j*(nRight+1)+i] = d;
    }
  }

  /* Compute the lowest-cost path back through the matrix */
  i = nRight;
  j = nLeft;
  k = (nRight+1)*(nLeft+1)-1;
  nMatch = iMatch = 0;
  while( i+j>0 ){
    unsigned char c = aM[k];
    if( c>=3 ){
      assert( i>0 && j>0 );
      i--;
      j--;
      nMatch++;
      iMatch += (c>>2);
      aM[k] = 3;
    }else if( c==2 ){
      assert( i>0 );
      i--;
    }else{
      assert( j>0 );
      j--;
    }
    k--;
    aM[k] = aM[j*(nRight+1)+i];
  }
  k++;
  i = (nRight+1)*(nLeft+1) - k;
  memmove(aM, &aM[k], i);
  *pNResult = i;
  *pResult = aM;

  end:
  fsl_free(pToFree);
  return rc;
}


/*
** Format a diff using a fsl_dibu object
*/
static int fdb__format(
  fsl__diff_cx * const cx,
  fsl_dibu * const pBuilder
){
  const fsl_dline *A;        /* Left side of the diff */
  const fsl_dline *B;        /* Right side of the diff */
  fsl_dibu_opt * const pOpt = pBuilder->opt;
  const int *R;          /* Array of COPY/DELETE/INSERT triples */
  unsigned int a;    /* Index of next line in A[] */
  unsigned int b;    /* Index of next line in B[] */
  unsigned int r;        /* Index into R[] */
  unsigned int nr;       /* Number of COPY/DELETE/INSERT triples to process */
  unsigned int mxr;      /* Maximum value for r */
  unsigned int na, nb;   /* Number of lines shown from A and B */
  unsigned int i, j;     /* Loop counters */
  unsigned int m, ma, mb;/* Number of lines to output */
  signed int skip;   /* Number of lines to skip */
  unsigned int contextLines; /* Lines of context above and below each change */
  unsigned short passNumber = 0;
  int rc = 0;
  
#define RC if(rc) goto end
#define METRIC(M) if(1==passNumber) ++pBuilder->metrics.M
  pass_again:
  contextLines = diff_opt_context_lines(pOpt);
  skip = 0;
  a = b = 0;
  A = cx->aFrom;
  B = cx->aTo;
  R = cx->aEdit;
  mxr = cx->nEdit;
  //MARKER(("contextLines=%u, nEdit = %d, mxr=%u\n", contextLines, cx->nEdit, mxr));
  while( mxr>2 && R[mxr-1]==0 && R[mxr-2]==0 ){ mxr -= 3; }

  pBuilder->lnLHS = pBuilder->lnRHS = 0;
  ++passNumber;
  if(pBuilder->start){
    pBuilder->passNumber = passNumber;
    rc = pBuilder->start(pBuilder);
    RC;
  }
  for(r=0; r<mxr; r += 3*nr){
    /* Figure out how many triples to show in a single block */
    for(nr=1; R[r+nr*3]>0 && R[r+nr*3]<(int)contextLines*2; nr++){}

#if 0
    /* MISSING: this "should" be replaced by a stateful predicate
       function, probably in the fsl_dibu_opt class. */
    /* If there is a regex, skip this block (generate no diff output)
    ** if the regex matches or does not match both insert and delete.
    ** Only display the block if one side matches but the other side does
    ** not.
    */
    if( pOpt->pRe ){
      int hideBlock = 1;
      int xa = a, xb = b;
      for(i=0; hideBlock && i<nr; i++){
        int c1, c2;
        xa += R[r+i*3];
        xb += R[r+i*3];
        c1 = re_dline_match(pOpt->pRe, &A[xa], R[r+i*3+1]);
        c2 = re_dline_match(pOpt->pRe, &B[xb], R[r+i*3+2]);
        hideBlock = c1==c2;
        xa += R[r+i*3+1];
        xb += R[r+i*3+2];
      }
      if( hideBlock ){
        a = xa;
        b = xb;
        continue;
      }
    }
#endif

    /* Figure out how many lines of A and B are to be displayed
    ** for this change block.
    */
    if( R[r]>(int)contextLines ){
      na = nb = contextLines;
      skip = R[r] - contextLines;
    }else{
      na = nb = R[r];
      skip = 0;
    }
    for(i=0; i<nr; i++){
      na += R[r+i*3+1];
      nb += R[r+i*3+2];
    }
    if( R[r+nr*3]>(int)contextLines ){
      na += contextLines;
      nb += contextLines;
    }else{
      na += R[r+nr*3];
      nb += R[r+nr*3];
    }
    for(i=1; i<nr; i++){
      na += R[r+i*3];
      nb += R[r+i*3];
    }

    //MARKER(("Chunk header... a=%u, b=%u, na=%u, nb=%u, skip=%d\n", a, b, na, nb, skip));
    if(pBuilder->chunkHeader
       /* The following bit is a kludge to keep from injecting a chunk
          header between chunks which are directly adjacent.

          The problem, however, is that we cannot skip _reliably_
          without also knowing how the next chunk aligns. If we skip
          it here, the _previous_ chunk header may well be telling
          the user a lie with regards to line numbers.

          Fossil itself does not have this issue because it generates
          these chunk headers directly in this routine, instead of in
          the diff builder, depending on a specific flag being set in
          builder->opt. Also (related), in that implementation, fossil
          will collapse chunks which are separated by less than the
          context distance into contiguous chunks (see below). Because
          we farm out the chunkHeader lines to the builder, we cannot
          reliably do that here.
       */
#if 0
       && !skip
#endif
       ){
      rc = pBuilder->chunkHeader(pBuilder,
                                 (uint32_t)(na ? a+skip+1 : a+skip),
                                 (uint32_t)na,
                                 (uint32_t)(nb ? b+skip+1 : b+skip),
                                 (uint32_t)nb);
      RC;
    }

    /* Show the initial common area */
    a += skip;
    b += skip;
    m = R[r] - skip;
    if( r ) skip -= contextLines;

    //MARKER(("Show the initial common... a=%u, b=%u, m=%u, r=%u, skip=%d\n", a, b, m, r, skip));
    if( skip>0 ){
      if( NULL==pBuilder->chunkHeader && skip<(int)contextLines ){
        /* 2021-09-27: BUG: this is incompatible with unified diff
           format. The generated header lines say we're skipping X
           lines but we then end up including lines which that header
           says to skip. As a workaround, we'll only run this when
           pBuilder->chunkHeader is NULL, noting that fossil's diff
           builder interface does not have that method (and thus
           doesn't have this issue, instead generating chunk headers
           directly in this algorithm).

           Without this block, our "utxt" diff builder can mimic
           fossil's non-diff builder unified diff format, except that
           we add Index lines (feature or bug?). With this block,
           the header values output above are wrong.
        */
        /* If the amount to skip is less that the context band, then
        ** go ahead and show the skip band as it is not worth eliding */
        //MARKER(("skip %d < contextLines %d\n", skip, contextLines));
        /* from fossil(1) from formatDiff() */
        for(j=0; 0==rc && j<(unsigned)skip; j++){
          //MARKER(("(A) COMMON\n"));
          rc = pBuilder->common(pBuilder, &A[a+j-skip]);
        }
      }else{
        rc = pBuilder->skip(pBuilder, skip);
      }
      RC;
    }
    for(j=0; 0==rc && j<m; j++){
      //MARKER(("(B) COMMON\n"));
      rc = pBuilder->common(pBuilder, &A[a+j]);
    }
    RC;
    a += m;
    b += m;
    //MARKER(("Show the differences... a=%d, b=%d, m=%d\n", a, b, m));

    /* Show the differences */
    for(i=0; i<nr; i++){
      unsigned int nAlign;
      unsigned char *alignment = 0;
      ma = R[r+i*3+1];   /* Lines on left but not on right */
      mb = R[r+i*3+2];   /* Lines on right but not on left */

#if FSL_DIFF_SMALL_GAP
  /* Try merging the current block with subsequent blocks, if the
      ** subsequent blocks are nearby and their result isn't too big.
      */
      while( i<nr-1 && smallGap2(&R[r+i*3],ma,mb) ){
        i++;
        m = R[r+i*3];
        ma += R[r+i*3+1] + m;
        mb += R[r+i*3+2] + m;
      }
#endif

      /* Try to find an alignment for the lines within this one block */
      rc = diffBlockAlignment(&A[a], ma, &B[b], mb, pOpt,
                              &alignment, &nAlign);
      RC;
      for(j=0; ma+mb>0; j++){
        assert( j<nAlign );
        switch( alignment[j] ){
          case 1: {
            /* Delete one line from the left */
            METRIC(deletions);
            rc = pBuilder->deletion(pBuilder, &A[a]);
            if(rc) goto bail;
            ma--;
            a++;
            break;
          }
          case 2: {
            /* Insert one line on the right */
            METRIC(insertions);
            rc = pBuilder->insertion(pBuilder, &B[b]);
            if(rc) goto bail;
            assert( mb>0 );
            mb--;
            b++;
            break;
          }
          case 3: {
            /* The left line is changed into the right line */
            if( 0==cx->cmpLine(&A[a], &B[b]) ){
              rc = pBuilder->common(pBuilder, &A[a]);
            }else{
              METRIC(edits);
              rc = pBuilder->edit(pBuilder, &A[a], &B[b]);
            }
            if(rc) goto bail;
            assert( ma>0 && mb>0 );
            ma--;
            mb--;
            a++;
            b++;
            break;
          }
          case 4: {
            /* Delete from left then separately insert on the right */
            METRIC(replacements);
            rc = pBuilder->replacement(pBuilder, &A[a], &B[b]);
            if(rc) goto bail;
            ma--;
            a++;
            mb--;
            b++;
            break;
          }
        }
      }
      assert( nAlign==j );
      fsl_free(alignment);
      if( i<nr-1 ){
        m = R[r+i*3+3];
        for(j=0; 0==rc && j<m; j++){
          //MARKER(("D common\n"));
          rc = pBuilder->common(pBuilder, &A[a+j]);
        }
        RC;
        b += m;
        a += m;
      }
      continue;
      bail:
      assert(rc);
      fsl_free(alignment);
      goto end;
    }

    /* Show the final common area */
    assert( nr==i );
    m = R[r+nr*3];
    if( m>contextLines ) m = contextLines;
    for(j=0; 0==rc && j<m && j<contextLines; j++){
      //MARKER(("E common\n"));
      rc = pBuilder->common(pBuilder, &A[a+j]);
    }
    RC;
  }
  if( R[r]>(int)contextLines ){
    rc = pBuilder->skip(pBuilder, R[r] - contextLines);
  }
  end:
#undef RC
#undef METRIC
  if(0==rc){
    if(pBuilder->finish) pBuilder->finish(pBuilder);
    if(pBuilder->twoPass && 1==passNumber){
      goto pass_again;
    }
  }
  return rc;
}

/* MISSING(?) fossil(1) converts the diff inputs into utf8 with no
   BOM. Whether we really want to do that here or rely on the caller
   to is up for debate. If we do it here, we have to make the inputs
   non-const, which seems "wrong" for a library API. */
#define blob_to_utf8_no_bom(A,B) (void)0

/**
   Performs a diff of version 1 (pA) and version 2 (pB). ONE of
   pBuilder or outRaw must be non-NULL. If pBuilder is not NULL, all
   output for the diff is emitted via pBuilder. If outRaw is not NULL
   then on success *outRaw is set to the array of diff triples,
   transfering ownership to the caller, who must eventually fsl_free()
   it. On error, *outRaw is not modified but pBuilder may have emitted
   partial output. That is not knowable for the general
   case. Ownership of pBuilder is not changed. If pBuilder is not NULL
   then pBuilder->opt must be non-NULL.
*/
static int fsl_diff2_text_impl(fsl_buffer const *pA,
                               fsl_buffer const *pB,
                               fsl_dibu * const pBuilder,
                               fsl_dibu_opt const * const opt_,
                               int ** outRaw){
  int rc = 0;
  fsl__diff_cx c = fsl__diff_cx_empty;
  bool ignoreWs = false;
  int ansiOptCount = 0;
  fsl_dibu_opt opt = *opt_
    /*we need a copy for the sake of the FSL_DIFF2_INVERT flag*/;
  if(!pA || !pB || (pBuilder && outRaw)) return FSL_RC_MISUSE;

  blob_to_utf8_no_bom(pA, 0);
  blob_to_utf8_no_bom(pB, 0);

  if( opt.diffFlags & FSL_DIFF2_INVERT ){
    char const * z;
    fsl_buffer const *pTemp = pA;
    pA = pB;
    pB = pTemp;
    z = opt.hashRHS; opt.hashRHS = opt.hashLHS; opt.hashLHS = z;
    z = opt.nameRHS; opt.nameRHS = opt.nameLHS; opt.nameLHS = z;
  }
#define AOPT(OPT) \
  if(opt.ansiColor.OPT) ansiOptCount += (*opt.ansiColor.OPT) ? 1 : 0; \
  else opt.ansiColor.OPT = ""
  AOPT(insertion);
  AOPT(edit);
  AOPT(deletion);
#undef AOPT
  if(0==ansiOptCount){
    opt.ansiColor.reset = "";
  }else if(!opt.ansiColor.reset || !*opt.ansiColor.reset){
    opt.ansiColor.reset = "\x1b[0m";
  }
  ignoreWs = (opt.diffFlags & FSL_DIFF2_IGNORE_ALLWS)!=0;
  if(FSL_DIFF2_IGNORE_ALLWS==(opt.diffFlags & FSL_DIFF2_IGNORE_ALLWS)){
    c.cmpLine = fsl_dline_cmp_ignore_ws;
  }else{
    c.cmpLine = fsl_dline_cmp;
  }
 
  rc = fsl_break_into_dlines(fsl_buffer_cstr(pA), (fsl_int_t)pA->used,
                             (uint32_t*)&c.nFrom, &c.aFrom, opt.diffFlags);
  if(rc) goto end;
  rc = fsl_break_into_dlines(fsl_buffer_cstr(pB), (fsl_int_t)pB->used,
                             (uint32_t*)&c.nTo, &c.aTo, opt.diffFlags);
  if(rc) goto end;

  /* Compute the difference */
  rc = fsl__diff_all(&c);
  if(rc) goto end;
  if( ignoreWs && c.nEdit==6 && c.aEdit[1]==0 && c.aEdit[2]==0 ){
    rc = FSL_RC_DIFF_WS_ONLY;
    goto end;
  }
  if( (opt.diffFlags & FSL_DIFF2_NOTTOOBIG)!=0 ){
    int i, m, n;
    int const * const a = c.aEdit;
    int const mx = c.nEdit;
    for(i=m=n=0; i<mx; i+=3){ m += a[i]; n += a[i+1]+a[i+2]; }
    if( !n || n>10000 ){
      rc = FSL_RC_RANGE;
      /* diff_errmsg(pOut, DIFF_TOO_MANY_CHANGES, diffFlags); */
      goto end;
    }
  }
  //fsl__dump_triples(&c, __FILE__, __LINE__);
  if( (opt.diffFlags & FSL_DIFF2_NOOPT)==0 ){
    fsl__diff_optimize(&c);
  }
  //fsl__dump_triples(&c, __FILE__, __LINE__);

  /**
     Reference:

     https://fossil-scm.org/home/file?ci=cae7036bb7f07c1b&name=src/diff.c&ln=2749-2804

     Noting that:

     - That function's return value is this one's *outRaw

     - DIFF_NUMSTAT flag is not implemented. For that matter,
     flags which result in output going anywhere except for
     pBuilder->out are not implemented here, e.g. DIFF_RAW.

     That last point makes this impl tiny compared to the original!
  */
  if(pBuilder){
    fsl_dibu_opt * const oldOpt = pBuilder->opt;
    pBuilder->opt = &opt;
    rc = fdb__format(&c, pBuilder);
    pBuilder->opt = oldOpt;
  }
  end:
  if(0==rc && outRaw){
    *outRaw = c.aEdit;
    c.aEdit = 0;
  }
  fsl__diff_cx_clean(&c);
  return rc;
}

int fsl_diff_v2(fsl_buffer const * pv1,
                fsl_buffer const * pv2,
                fsl_dibu * const pBuilder){
  return fsl_diff2_text_impl(pv1, pv2, pBuilder, pBuilder->opt, NULL);
}

int fsl_diff_v2_raw(fsl_buffer const * pv1,
                    fsl_buffer const * pv2,
                    fsl_dibu_opt const * const opt,
                    int **outRaw ){
  return fsl_diff2_text_impl(pv1, pv2, NULL,
                             opt ? opt : &fsl_dibu_opt_empty,
                             outRaw);
}


fsl_dibu * fsl_dibu_alloc(fsl_size_t extra){
  fsl_dibu * rc =
    (fsl_dibu*)fsl_malloc(sizeof(fsl_dibu) + extra);
  if(rc){
    *rc = fsl_dibu_empty;

  uint32_t lineCount[2];
  /**
     The actual number of lines needed for rendering the file.
  */
  uint32_t displayLines;
};
typedef struct DiffCounter DiffCounter;
static const DiffCounter DiffCounter_empty = {{1,10,3,1,10},{0,0},0};
static const DiffCounter DiffCounter_empty = {{1,25,3,1,25},{0,0},0};
#define DICOSTATE(VNAME) DiffCounter * const VNAME = (DiffCounter *)b->pimpl

static int maxColWidth(fsl_dibu const * const b,
                       DiffCounter const * const sst,
                       int mwIndex){
  static const short minColWidth =
    10/*b->opt.columnWidth values smaller than this are treated as

#endif
  return rc;
}
static int fdb__tcl_finally(fsl_dibu * const b){
  int rc = 0;
  if(FSL_DIBU_TCL_TK==(b->implFlags & FSL_DIBU_TCL_TK)){
    extern char const * fsl_difftk_cstr;
    if(!b->fileCount) rc = fdb__out(b,"set difftxt {\n",-1);
    rc = fdb__out(b, "}\nset fossilcmd {}\n", -1);
    if(0==rc) fdb__out(b, fsl_difftk_cstr, -1);
    if(0==rc) rc = fdb__out(b, "}\nset fossilcmd {}\n", -1);
    if(0==rc) rc = fdb__out(b, fsl_difftk_cstr, -1);
  }
  return rc;
}

#undef BR_OPEN
#undef BR_CLOSE

  if(NULL!=factory){
    *pOut = factory();
    rc = *pOut ? 0 : FSL_RC_OOM;
  }
  return rc;
}

#undef DIFF_ALIGN_MX
#undef MARKER
#undef DIFF_CANNOT_COMPUTE_BINARY
#undef DIFF_CANNOT_COMPUTE_SYMLINK
#undef DIFF_TOO_MANY_CHANGES
#undef DIFF_WHITESPACE_ONLY
#undef fsl_dline_empty_m
#undef MARKER
#undef DICOSTATE
#undef DTCL_BUFFER
/* end of file ./src/dibu.c */
/* start of file ./src/diff.c */
/* -*- Mode: C; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 2 -*- */ 
/* vim: set ts=2 et sw=2 tw=80: */
/*
  Copyright 2013-2022 The Libfossil Authors, see LICENSES/BSD-2-Clause.txt

  SPDX-License-Identifier: BSD-2-Clause-FreeBSD
  SPDX-FileCopyrightText: 2013-2022 The Libfossil Authors
  SPDX-ArtifactOfProjectName: Libfossil
  SPDX-FileType: Code

  Heavily indebted to the Fossil SCM project (https://fossil-scm.org).
*/

/************************************************************************
  This file houses Fossil's diff-generation routines (as opposed to
  the delta-generation). This code is a straight port of those
  algorithms from the Fossil SCM project, initially implemented by
  D. Richard Hipp, ported and the license re-assigned to this project
  with this consent.
*/
#include <assert.h>
#include <memory.h>
#include <stdlib.h>
#include <string.h> /* for memmove()/strlen() */

#include <stdio.h>
#define MARKER(pfexp)                                               \
  do{ printf("MARKER: %s:%d:%s():\t",__FILE__,__LINE__,__func__);   \
    printf pfexp;                                                   \
  } while(0)


const fsl_dline fsl_dline_empty = fsl_dline_empty_m;
const fsl_dline_change fsl_dline_change_empty = fsl_dline_change_empty_m;
const fsl__diff_cx fsl__diff_cx_empty = fsl__diff_cx_empty_m;

void fsl__diff_cx_clean(fsl__diff_cx * const cx){
  fsl_free(cx->aFrom);
  fsl_free(cx->aTo);
  fsl_free(cx->aEdit);
  cx->aFrom = cx->aTo = NULL;
  cx->aEdit = NULL;
  *cx = fsl__diff_cx_empty;
}

/* Fast isspace for use by diff */
static const char diffIsSpace[] = {
  0, 0, 0, 0, 0, 0, 0, 0,   1, 1, 1, 0, 1, 1, 0, 0,
  0, 0, 0, 0, 0, 0, 0, 0,   0, 0, 0, 0, 0, 0, 0, 0,
  1, 0, 0, 0, 0, 0, 0, 0,   0, 0, 0, 0, 0, 0, 0, 0,
  0, 0, 0, 0, 0, 0, 0, 0,   0, 0, 0, 0, 0, 0, 0, 0,
  0, 0, 0, 0, 0, 0, 0, 0,   0, 0, 0, 0, 0, 0, 0, 0,
  0, 0, 0, 0, 0, 0, 0, 0,   0, 0, 0, 0, 0, 0, 0, 0,
  0, 0, 0, 0, 0, 0, 0, 0,   0, 0, 0, 0, 0, 0, 0, 0,
  0, 0, 0, 0, 0, 0, 0, 0,   0, 0, 0, 0, 0, 0, 0, 0,

  0, 0, 0, 0, 0, 0, 0, 0,   0, 0, 0, 0, 0, 0, 0, 0,
  0, 0, 0, 0, 0, 0, 0, 0,   0, 0, 0, 0, 0, 0, 0, 0,
  0, 0, 0, 0, 0, 0, 0, 0,   0, 0, 0, 0, 0, 0, 0, 0,
  0, 0, 0, 0, 0, 0, 0, 0,   0, 0, 0, 0, 0, 0, 0, 0,
  0, 0, 0, 0, 0, 0, 0, 0,   0, 0, 0, 0, 0, 0, 0, 0,
  0, 0, 0, 0, 0, 0, 0, 0,   0, 0, 0, 0, 0, 0, 0, 0,
  0, 0, 0, 0, 0, 0, 0, 0,   0, 0, 0, 0, 0, 0, 0, 0,
  0, 0, 0, 0, 0, 0, 0, 0,   0, 0, 0, 0, 0, 0, 0, 0,
};
#define diff_isspace(X)  (diffIsSpace[(unsigned char)(X)])


/**
   Length of a dline.
*/
#define LENGTH(X) ((X)->n)


/**
   Minimum of two values
*/
static int minInt(int a, int b){ return a<b ? a : b; }

/** @internal

   Compute the optimal longest common subsequence (LCS) using an
   exhaustive search. This version of the LCS is only used for
   shorter input strings since runtime is O(N*N) where N is the
   input string length.
*/
static void fsl__diff_optimal_lcs(
  fsl__diff_cx * const p,     /* Two files being compared */
  int iS1, int iE1,          /* Range of lines in p->aFrom[] */
  int iS2, int iE2,          /* Range of lines in p->aTo[] */
  int *piSX, int *piEX,      /* Write p->aFrom[] common segment here */
  int *piSY, int *piEY       /* Write p->aTo[] common segment here */
){
  int mxLength = 0;          /* Length of longest common subsequence */
  int i, j;                  /* Loop counters */
  int k;                     /* Length of a candidate subsequence */
  int iSXb = iS1;            /* Best match so far */
  int iSYb = iS2;            /* Best match so far */

  for(i=iS1; i<iE1-mxLength; i++){
    for(j=iS2; j<iE2-mxLength; j++){
      if( p->cmpLine(&p->aFrom[i], &p->aTo[j]) ) continue;
      if( mxLength && p->cmpLine(&p->aFrom[i+mxLength], &p->aTo[j+mxLength]) ){
        continue;
      }
      k = 1;
      while( i+k<iE1 && j+k<iE2 && p->cmpLine(&p->aFrom[i+k],&p->aTo[j+k])==0 ){
        k++;
      }
      if( k>mxLength ){
        iSXb = i;
        iSYb = j;
        mxLength = k;
      }
    }
  }
  *piSX = iSXb;
  *piEX = iSXb + mxLength;
  *piSY = iSYb;
  *piEY = iSYb + mxLength;
}

/**
    Compare two blocks of text on lines iS1 through iE1-1 of the aFrom[]
    file and lines iS2 through iE2-1 of the aTo[] file.  Locate a sequence
    of lines in these two blocks that are exactly the same.  Return
    the bounds of the matching sequence.
   
    If there are two or more possible answers of the same length, the
    returned sequence should be the one closest to the center of the
    input range.
   
    Ideally, the common sequence should be the longest possible common
    sequence.  However, an exact computation of LCS is O(N*N) which is
    way too slow for larger files.  So this routine uses an O(N)
    heuristic approximation based on hashing that usually works about
    as well.  But if the O(N) algorithm doesn't get a good solution
    and N is not too large, we fall back to an exact solution by
    calling fsl__diff_optimal_lcs().
*/
static void fsl__diff_lcs(
  fsl__diff_cx * const p,     /* Two files being compared */
  int iS1, int iE1,          /* Range of lines in p->aFrom[] */
  int iS2, int iE2,          /* Range of lines in p->aTo[] */
  int *piSX, int *piEX,      /* Write p->aFrom[] common segment here */
  int *piSY, int *piEY       /* Write p->aTo[] common segment here */
){
  int i, j, k;               /* Loop counters */
  int n;                     /* Loop limit */
  fsl_dline *pA, *pB;            /* Pointers to lines */
  int iSX, iSY, iEX, iEY;    /* Current match */
  int skew = 0;              /* How lopsided is the match */
  int dist = 0;              /* Distance of match from center */
  int mid;                   /* Center of the chng */
  int iSXb, iSYb, iEXb, iEYb;   /* Best match so far */
  int iSXp, iSYp, iEXp, iEYp;   /* Previous match */
  sqlite3_int64 bestScore;      /* Best score so far */
  sqlite3_int64 score;          /* Score for current candidate LCS */
  int span;                     /* combined width of the input sequences */
  int cutoff = 4;            /* Max hash chain entries to follow */
  int nextCutoff = -1;       /* Value of cutoff for next iteration */

  span = (iE1 - iS1) + (iE2 - iS2);
  bestScore = -10000;
  score = 0;
  iSXb = iSXp = iS1;
  iEXb = iEXp = iS1;
  iSYb = iSYp = iS2;
  iEYb = iEYp = iS2;
  mid = (iE1 + iS1)/2;
  do{
    nextCutoff = 0;
    for(i=iS1; i<iE1; i++){
      int limit = 0;
      j = p->aTo[p->aFrom[i].h % p->nTo].iHash;
      while( j>0
        && (j-1<iS2 || j>=iE2 || p->cmpLine(&p->aFrom[i], &p->aTo[j-1]))
      ){
        if( limit++ > cutoff ){
          j = 0;
          nextCutoff = cutoff*4;
          break;
        }
        j = p->aTo[j-1].iNext;
      }
      if( j==0 ) continue;
      assert( i>=iSXb && i>=iSXp );
      if( i<iEXb && j>=iSYb && j<iEYb ) continue;
      if( i<iEXp && j>=iSYp && j<iEYp ) continue;
      iSX = i;
      iSY = j-1;
      pA = &p->aFrom[iSX-1];
      pB = &p->aTo[iSY-1];
      n = minInt(iSX-iS1, iSY-iS2);
      for(k=0; k<n && p->cmpLine(pA,pB)==0; k++, pA--, pB--){}
      iSX -= k;
      iSY -= k;
      iEX = i+1;
      iEY = j;
      pA = &p->aFrom[iEX];
      pB = &p->aTo[iEY];
      n = minInt(iE1-iEX, iE2-iEY);
      for(k=0; k<n && p->cmpLine(pA,pB)==0; k++, pA++, pB++){}
      iEX += k;
      iEY += k;
      skew = (iSX-iS1) - (iSY-iS2);
      if( skew<0 ) skew = -skew;
      dist = (iSX+iEX)/2 - mid;
      if( dist<0 ) dist = -dist;
      score = (iEX - iSX)*(sqlite3_int64)span - (skew + dist);
      if( score>bestScore ){
        bestScore = score;
        iSXb = iSX;
        iSYb = iSY;
        iEXb = iEX;
        iEYb = iEY;
      }else if( iEX>iEXp ){
        iSXp = iSX;
        iSYp = iSY;
        iEXp = iEX;
        iEYp = iEY;
      }
    }
  }while( iSXb==iEXb && nextCutoff && (cutoff=nextCutoff)<=64 );
  if( iSXb==iEXb && (sqlite3_int64)(iE1-iS1)*(iE2-iS2)<2500 ){
    fsl__diff_optimal_lcs(p, iS1, iE1, iS2, iE2, piSX, piEX, piSY, piEY);
  }else{
    *piSX = iSXb;
    *piSY = iSYb;
    *piEX = iEXb;
    *piEY = iEYb;
  }
}

void fsl__dump_triples(fsl__diff_cx const * const p,
                       char const * zFile, int ln ){
  // Compare this with (fossil xdiff --raw) on the same inputs
  fprintf(stderr,"%s:%d: Compare this with (fossil xdiff --raw) on the same inputs:\n",
          zFile, ln);
  for(int i = 0; p->aEdit[i] || p->aEdit[i+1] || p->aEdit[i+2]; i+=3){
    printf(" copy %6d  delete %6d  insert %6d\n",
           p->aEdit[i], p->aEdit[i+1], p->aEdit[i+2]);
  }
}

/** @internal
    Expand the size of p->aEdit array to hold at least nEdit elements.
 */
static int fsl__diff_expand_edit(fsl__diff_cx * const p, int nEdit){
  void * re = fsl_realloc(p->aEdit, nEdit*sizeof(int));
  if(!re) return FSL_RC_OOM;
  else{
    p->aEdit = (int*)re;
    p->nEditAlloc = nEdit;
    return 0;
  }
}

/**
    Append a new COPY/DELETE/INSERT triple.
   
    Returns 0 on success, FSL_RC_OOM on OOM.
 */
static int appendTriple(fsl__diff_cx *p, int nCopy, int nDel, int nIns){
  /* printf("APPEND %d/%d/%d\n", nCopy, nDel, nIns); */
  if( p->nEdit>=3 ){
    if( p->aEdit[p->nEdit-1]==0 ){
      if( p->aEdit[p->nEdit-2]==0 ){
        p->aEdit[p->nEdit-3] += nCopy;
        p->aEdit[p->nEdit-2] += nDel;
        p->aEdit[p->nEdit-1] += nIns;
        return 0;
      }
      if( nCopy==0 ){
        p->aEdit[p->nEdit-2] += nDel;
        p->aEdit[p->nEdit-1] += nIns;
        return 0;
      }
    }
    if( nCopy==0 && nDel==0 ){
      p->aEdit[p->nEdit-1] += nIns;
      return 0;
    }
  }
  if( p->nEdit+3>p->nEditAlloc ){
    int const rc = fsl__diff_expand_edit(p, p->nEdit*2 + 15);
    if(rc) return rc;
    else if( p->aEdit==0 ) return 0;
  }
  p->aEdit[p->nEdit++] = nCopy;
  p->aEdit[p->nEdit++] = nDel;
  p->aEdit[p->nEdit++] = nIns;
  return 0;
}

/*
** A common subsequene between p->aFrom and p->aTo has been found.
** This routine tries to judge if the subsequence really is a valid
** match or rather is just an artifact of an indentation change.
**
** Return non-zero if the subsequence is valid.  Return zero if the
** subsequence seems likely to be an editing artifact and should be
** ignored.
**
** This routine is a heuristic optimization intended to give more
** intuitive diff results following an indentation change it code that
** is formatted similarly to C/C++, Javascript, Go, TCL, and similar
** languages that use {...} for nesting.  A correct diff is computed
** even if this routine always returns true (non-zero).  But sometimes
** a more intuitive diff can result if this routine returns false.
**
** The subsequences consists of the rows iSX through iEX-1 (inclusive)
** in p->aFrom[].  The total sequences is iS1 through iE1-1 (inclusive)
** of p->aFrom[].
**
** Example where this heuristic is useful, see the diff at
** https://www.sqlite.org/src/fdiff?v1=0e79dd15cbdb4f48&v2=33955a6fd874dd97
**
** See also discussion at https://fossil-scm.org/forum/forumpost/9ba3284295
**
** ALGORITHM (subject to change and refinement):
**
**    1.  If the subsequence is larger than 1/7th of the original span,
**        then consider it valid.  --> return 1
**
**    2.  If the subsequence contains any charaters other than '}', '{",
**        or whitespace, then consider it valid. --> return 1
**
**    3.  Otherwise, it is potentially an artifact of an indentation
**        change. --> return 0
*/
static bool likelyNotIndentChngArtifact(
  fsl__diff_cx const * const p,     /* The complete diff context */
  int iS1,         /* Start of the main segment */
  int iSX,         /* Start of the subsequence */
  int iEX,         /* First row past the end of the subsequence */
  int iE1          /* First row past the end of the main segment */
){
  int i, j;
  if( (iEX-iSX)*7 >= (iE1-iS1) ) return true;
  for(i=iSX; i<iEX; i++){
    const char *z = p->aFrom[i].z;
    for(j=p->aFrom[i].n-1; j>=0; j--){
      char c = z[j];
      if( c!='}' && c!='{' && !diff_isspace(c) ) return true;
    }
  }
  return false;
}

/**
    Do a single step in the difference.  Compute a sequence of
    copy/delete/insert steps that will convert lines iS1 through iE1-1
    of the input into lines iS2 through iE2-1 of the output and write
    that sequence into the difference context.
   
    The algorithm is to find a block of common text near the middle of
    the two segments being diffed.  Then recursively compute
    differences on the blocks before and after that common segment.
    Special cases apply if either input segment is empty or if the two
    segments have no text in common.
 */
static int diff_step(fsl__diff_cx *p, int iS1, int iE1, int iS2, int iE2){
  int iSX, iEX, iSY, iEY;
  int rc = 0;
  if( iE1<=iS1 ){
    /* The first segment is empty */
    if( iE2>iS2 ){
      rc = appendTriple(p, 0, 0, iE2-iS2);
    }
    return rc;
  }
  if( iE2<=iS2 ){
    /* The second segment is empty */
    return appendTriple(p, 0, iE1-iS1, 0);
  }

  /* Find the longest matching segment between the two sequences */
  fsl__diff_lcs(p, iS1, iE1, iS2, iE2, &iSX, &iEX, &iSY, &iEY);
  if( iEX>iSX+5
      || (iEX>iSX && likelyNotIndentChngArtifact(p,iS1,iSX,iEX,iE1) )){
    /* A common segment has been found.
       Recursively diff either side of the matching segment */
    rc = diff_step(p, iS1, iSX, iS2, iSY);
    if(!rc){
      if(iEX>iSX){
        rc = appendTriple(p, iEX - iSX, 0, 0);
      }
      if(!rc) rc = diff_step(p, iEX, iE1, iEY, iE2);
    }
  }else{
    /* The two segments have nothing in common.  Delete the first then
       insert the second. */
    rc = appendTriple(p, 0, iE1-iS1, iE2-iS2);
  }
  return rc;
}

int fsl__diff_all(fsl__diff_cx * const p){
  int mnE, iS, iE1, iE2;
  int rc = 0;
  /* Carve off the common header and footer */
  iE1 = p->nFrom;
  iE2 = p->nTo;
  while( iE1>0 && iE2>0 && p->cmpLine(&p->aFrom[iE1-1], &p->aTo[iE2-1])==0 ){
    iE1--;
    iE2--;
  }
  mnE = iE1<iE2 ? iE1 : iE2;
  for(iS=0; iS<mnE && p->cmpLine(&p->aFrom[iS],&p->aTo[iS])==0; iS++){}

  /* do the difference */
  if( iS>0 ){
    rc = appendTriple(p, iS, 0, 0);
    if(rc) return rc;
  }
  rc = diff_step(p, iS, iE1, iS, iE2);
  //fsl__dump_triples(p, __FILE__, __LINE__);
  if(rc) return rc;
  else if( iE1<p->nFrom ){
    rc = appendTriple(p, p->nFrom - iE1, 0, 0);
    if(rc) return rc;
  }
  /* Terminate the COPY/DELETE/INSERT triples with three zeros */
  rc = fsl__diff_expand_edit(p, p->nEdit+3);
  if(0==rc){
    if(p->aEdit ){
      p->aEdit[p->nEdit++] = 0;
      p->aEdit[p->nEdit++] = 0;
      p->aEdit[p->nEdit++] = 0;
      //fsl__dump_triples(p, __FILE__, __LINE__);
    }
  }
  return rc;
}

void fsl__diff_optimize(fsl__diff_cx * const p){
  int r;       /* Index of current triple */
  int lnFrom;  /* Line number in p->aFrom */
  int lnTo;    /* Line number in p->aTo */
  int cpy, del, ins;

  //fsl__dump_triples(p, __FILE__, __LINE__);
  lnFrom = lnTo = 0;
  for(r=0; r<p->nEdit; r += 3){
    cpy = p->aEdit[r];
    del = p->aEdit[r+1];
    ins = p->aEdit[r+2];
    lnFrom += cpy;
    lnTo += cpy;

    /* Shift insertions toward the beginning of the file */
    while( cpy>0 && del==0 && ins>0 ){
      fsl_dline *pTop = &p->aFrom[lnFrom-1];  /* Line before start of insert */
      fsl_dline *pBtm = &p->aTo[lnTo+ins-1];  /* Last line inserted */
      if( p->cmpLine(pTop, pBtm) ) break;
      if( LENGTH(pTop+1)+LENGTH(pBtm)<=LENGTH(pTop)+LENGTH(pBtm-1) ) break;
      lnFrom--;
      lnTo--;
      p->aEdit[r]--;
      p->aEdit[r+3]++;
      cpy--;
    }

    /* Shift insertions toward the end of the file */
    while( r+3<p->nEdit && p->aEdit[r+3]>0 && del==0 && ins>0 ){
      fsl_dline *pTop = &p->aTo[lnTo];       /* First line inserted */
      fsl_dline *pBtm = &p->aTo[lnTo+ins];   /* First line past end of insert */
      if( p->cmpLine(pTop, pBtm) ) break;
      if( LENGTH(pTop)+LENGTH(pBtm-1)<=LENGTH(pTop+1)+LENGTH(pBtm) ) break;
      lnFrom++;
      lnTo++;
      p->aEdit[r]++;
      p->aEdit[r+3]--;
      cpy++;
    }

    /* Shift deletions toward the beginning of the file */
    while( cpy>0 && del>0 && ins==0 ){
      fsl_dline *pTop = &p->aFrom[lnFrom-1];     /* Line before start of delete */
      fsl_dline *pBtm = &p->aFrom[lnFrom+del-1]; /* Last line deleted */
      if( p->cmpLine(pTop, pBtm) ) break;
      if( LENGTH(pTop+1)+LENGTH(pBtm)<=LENGTH(pTop)+LENGTH(pBtm-1) ) break;
      lnFrom--;
      lnTo--;
      p->aEdit[r]--;
      p->aEdit[r+3]++;
      cpy--;
    }

    /* Shift deletions toward the end of the file */
    while( r+3<p->nEdit && p->aEdit[r+3]>0 && del>0 && ins==0 ){
      fsl_dline *pTop = &p->aFrom[lnFrom];     /* First line deleted */
      fsl_dline *pBtm = &p->aFrom[lnFrom+del]; /* First line past end of delete */
      if( p->cmpLine(pTop, pBtm) ) break;
      if( LENGTH(pTop)+LENGTH(pBtm-1)<=LENGTH(pTop)+LENGTH(pBtm) ) break;
      lnFrom++;
      lnTo++;
      p->aEdit[r]++;
      p->aEdit[r+3]--;
      cpy++;
    }

    lnFrom += del;
    lnTo += ins;
  }
  //fsl__dump_triples(p, __FILE__, __LINE__);
}


/**
   Counts the number of lines in the first n bytes of the given 
   string. If n<0 then fsl_strlen() is used to count it. 

   It includes the last line in the count even if it lacks the \n
   terminator. If an empty string is passed in, the number of lines
   is zero.

   For the purposes of this function, a string is considered empty if
   it contains no characters OR contains only NUL characters.

   If the input appears to be plain text it returns true and, if nOut
   is not NULL, writes the number of lines there. If the input appears
   to be binary, returns false and does not modify nOut.
*/
static bool fsl__count_lines(const char *z, fsl_int_t n, uint32_t * nOut ){
  uint32_t nLine;
  const char *zNL, *z2;
  if(n<0) n = (fsl_int_t)fsl_strlen(z);
  for(nLine=0, z2=z; (zNL = strchr(z2,'\n'))!=0; z2=zNL+1, nLine++){}
  if( z2[0]!='\0' ){
    nLine++;
    do{ z2++; }while( z2[0]!='\0' );
  }
  if( n!=(fsl_int_t)(z2-z) ) return false;
  if( nOut ) *nOut = nLine;
  return true;
}

int fsl_break_into_dlines(const char *z, fsl_int_t n,
                          uint32_t *pnLine,
                          fsl_dline **pOut, uint64_t diffFlags){
  uint32_t nLine, i, k, nn, s, x;
  uint64_t h, h2;
  fsl_dline *a = 0;
  const char *zNL;

  if(!z || !n){
    *pnLine = 0;
    *pOut = NULL;
    return 0;
  }
  if( !fsl__count_lines(z, n, &nLine) ){
    return FSL_RC_DIFF_BINARY;
  }
  assert( nLine>0 || z[0]=='\0' );
  if(nLine>0){
    a = fsl_malloc( sizeof(a[0])*nLine );
    if(!a) return FSL_RC_OOM;
    memset(a, 0, sizeof(a[0])*nLine);
  }else{
    *pnLine = 0;
    *pOut = a;
    return 0;
  }
  assert( a );
  i = 0;
  do{
    zNL = strchr(z,'\n');
    if( zNL==0 ) zNL = z+n;
    nn = (uint32_t)(zNL - z);
    if( nn>FSL__LINE_LENGTH_MASK ){
      fsl_free(a);
      *pOut = 0;
      *pnLine = 0;
      return FSL_RC_DIFF_BINARY;
    }
    a[i].z = z;
    k = nn;
    if( diffFlags & FSL_DIFF2_STRIP_EOLCR ){
      if( k>0 && z[k-1]=='\r' ){ k--; }
    }
    a[i].n = k;
    if( diffFlags & FSL_DIFF2_IGNORE_EOLWS ){
      while( k>0 && diff_isspace(z[k-1]) ){ k--; }
    }
    if( (diffFlags & FSL_DIFF2_IGNORE_ALLWS)
        ==FSL_DIFF2_IGNORE_ALLWS ){
      uint32_t numws = 0;
      for(s=0; s<k && z[s]<=' '; s++){}
      a[i].indent = s;
      a[i].nw = k - s;
      for(h=0, x=s; x<k; ++x){
        char c = z[x];
        if( diff_isspace(c) ){
          ++numws;
        }else{
          h = (h^c)*9000000000000000041LL;
        }
      }
      k -= numws;
    }else{
      uint32_t k2 = k & ~0x7;
      uint64_t m;
      for(h=x=s=0; x<k2; x += 8){
        memcpy(&m, z+x, 8);
        h = (h^m)*9000000000000000041LL;
      }
      m = 0;
      memcpy(&m, z+x, k-k2);
      h ^= m;
    }
    a[i].h = h = ((h%281474976710597LL)<<FSL__LINE_LENGTH_MASK_SZ) | (k-s);
    h2 = h % nLine;
    a[i].iNext = a[h2].iHash;
    a[h2].iHash = i+1;
    z += nn+1; n -= nn+1;
    i++;
  }while( zNL[0]!='\0' && zNL[1]!='\0' );
  assert( i==nLine );

  *pnLine = nLine;
  *pOut = a;
  return 0;
}

int fsl_dline_cmp(const fsl_dline * const pA,
                  const fsl_dline * const pB){
  if( pA->h!=pB->h ) return 1;
  return memcmp(pA->z,pB->z, pA->h&FSL__LINE_LENGTH_MASK);
}

int fsl_dline_cmp_ignore_ws(const fsl_dline * const pA,
                            const fsl_dline * const pB){
  if( pA->h==pB->h ){
    unsigned short a, b;
    if( memcmp(pA->z, pB->z, pA->h&FSL__LINE_LENGTH_MASK)==0 ) return 0;
    a = pA->indent;
    b = pB->indent;
    while( a<pA->n || b<pB->n ){
      if( a<pA->n && b<pB->n && pA->z[a++] != pB->z[b++] ) return 1;
      while( a<pA->n && diff_isspace(pA->z[a])) ++a;
      while( b<pB->n && diff_isspace(pB->z[b])) ++b;
    }
    return pA->n-a != pB->n-b;
  }
  return 1;
}

/*
** The two text segments zLeft and zRight are known to be different on
** both ends, but they might have  a common segment in the middle.  If
** they do not have a common segment, return 0.  If they do have a large
** common segment, return non-0 and before doing so set:
**
**   aLCS[0] = start of the common segment in zLeft
**   aLCS[1] = end of the common segment in zLeft
**   aLCS[2] = start of the common segment in zLeft
**   aLCS[3] = end of the common segment in zLeft
**
** This computation is for display purposes only and does not have to be
** optimal or exact.
*/
static int textLCS2(
  const char *zLeft,  uint32_t nA, /* String on the left */
  const char *zRight, uint32_t nB, /* String on the right */
  uint32_t *aLCS                   /* Identify bounds of LCS here */
){
  const unsigned char *zA = (const unsigned char*)zLeft;    /* left string */
  const unsigned char *zB = (const unsigned char*)zRight;   /* right string */
  uint32_t i, j, k;               /* Loop counters */
  uint32_t lenBest = 0;           /* Match length to beat */

  for(i=0; i<nA-lenBest; i++){
    unsigned char cA = zA[i];
    if( (cA&0xc0)==0x80 ) continue;
    for(j=0; j<nB-lenBest; j++ ){
      if( zB[j]==cA ){
        for(k=1; j+k<nB && i+k<nA && zB[j+k]==zA[i+k]; k++){}
        while( (zB[j+k]&0xc0)==0x80 ){ k--; }
        if( k>lenBest ){
          lenBest = k;
          aLCS[0] = i;
          aLCS[1] = i+k;
          aLCS[2] = j;
          aLCS[3] = j+k;
        }
      }
    }
  }
  return lenBest>0;
}

/*
** Find the smallest spans that are different between two text strings
** that are known to be different on both ends. Returns the number
** of entries in p->a which get populated.
*/
static unsigned short textLineChanges(
  const char *zLeft,  uint32_t nA, /* String on the left */
  const char *zRight, uint32_t nB, /* String on the right */
  fsl_dline_change * const p             /* Write results here */
){
  p->n = 1;
  p->a[0].iStart1 = 0;
  p->a[0].iLen1 = nA;
  p->a[0].iStart2 = 0;
  p->a[0].iLen2 = nB;
  p->a[0].isMin = 0;
  while( p->n<fsl_dline_change_max_spans-1 ){
    int mxi = -1;
    int mxLen = -1;
    int x, i;
    uint32_t aLCS[4] = {0,0,0,0};
    struct fsl_dline_change_span *a, *b;
    for(i=0; i<p->n; i++){
      if( p->a[i].isMin ) continue;
      x = p->a[i].iLen1;
      if( p->a[i].iLen2<x ) x = p->a[i].iLen2;
      if( x>mxLen ){
        mxLen = x;
        mxi = i;
      }
    }
    if( mxLen<6 ) break;
    x = textLCS2(zLeft + p->a[mxi].iStart1, p->a[mxi].iLen1,
                 zRight + p->a[mxi].iStart2, p->a[mxi].iLen2, aLCS);
    if( x==0 ){
      p->a[mxi].isMin = 1;
      continue;
    }
    a = p->a+mxi;
    b = a+1;
    if( mxi<p->n-1 ){
      memmove(b+1, b, sizeof(*b)*(p->n-mxi-1));
    }
    p->n++;
    b->iStart1 = a->iStart1 + aLCS[1];
    b->iLen1 = a->iLen1 - aLCS[1];
    a->iLen1 = aLCS[0];
    b->iStart2 = a->iStart2 + aLCS[3];
    b->iLen2 = a->iLen2 - aLCS[3];
    a->iLen2 = aLCS[2];
    b->isMin = 0;
  }
  return p->n;
}

/*
** Return true if the string starts with n spaces
*/
static int allSpaces(const char *z, int n){
  int i;
  for(i=0; i<n && diff_isspace(z[i]); ++i){}
  return i==n;
}

/*
** Try to improve the human-readability of the fsl_dline_change p.
**
** (1)  If the first change span shows a change of indentation, try to
**      move that indentation change to the left margin.
**
** (2)  Try to shift changes so that they begin or end with a space.
*/
static void improveReadability(
  const char *zA,  /* Left line of the change */
  const char *zB,  /* Right line of the change */
  fsl_dline_change * const p /* The fsl_dline_change to be adjusted */
){
  int j, n, len;
  if( p->n<1 ) return;

  /* (1) Attempt to move indentation changes to the left margin */
  if( p->a[0].iLen1==0
   && (len = p->a[0].iLen2)>0
   && (j = p->a[0].iStart2)>0
   && zB[0]==zB[j]
   && allSpaces(zB, j)
  ){
    for(n=1; n<len && n<j && zB[j]==zB[j+n]; n++){}
    if( n<len ){
      memmove(&p->a[1], &p->a[0], sizeof(p->a[0])*p->n);
      p->n++;
      p->a[0] = p->a[1];
      p->a[1].iStart2 += n;
      p->a[1].iLen2 -= n;
      p->a[0].iLen2 = n;
    }
    p->a[0].iStart1 = 0;
    p->a[0].iStart2 = 0;
  }else
  if( p->a[0].iLen2==0
   && (len = p->a[0].iLen1)>0
   && (j = p->a[0].iStart1)>0
   && zA[0]==zA[j]
   && allSpaces(zA, j)
  ){
    for(n=1; n<len && n<j && zA[j]==zA[j+n]; n++){}
    if( n<len ){
      memmove(&p->a[1], &p->a[0], sizeof(p->a[0])*p->n);
      p->n++;
      p->a[0] = p->a[1];
      p->a[1].iStart1 += n;
      p->a[1].iLen1 -= n;
      p->a[0].iLen1 = n;
    }
    p->a[0].iStart1 = 0;
    p->a[0].iStart2 = 0;
  }

  /* (2) Try to shift changes so that they begin or end with a
  ** space.  (TBD) */
}

void fsl_dline_change_spans(const fsl_dline *pLeft, const fsl_dline *pRight,
                            fsl_dline_change * const p){
  /* fossil(1) counterpart ==> diff.c oneLineChange() */
  int nLeft;           /* Length of left line in bytes */
  int nRight;          /* Length of right line in bytes */
  int nShort;          /* Shortest of left and right */
  int nPrefix;         /* Length of common prefix */
  int nSuffix;         /* Length of common suffix */
  int nCommon;         /* Total byte length of suffix and prefix */
  const char *zLeft;   /* Text of the left line */
  const char *zRight;  /* Text of the right line */
  int nLeftDiff;       /* nLeft - nPrefix - nSuffix */
  int nRightDiff;      /* nRight - nPrefix - nSuffix */

  nLeft = pLeft->n;
  zLeft = pLeft->z;
  nRight = pRight->n;
  zRight = pRight->z;
  nShort = nLeft<nRight ? nLeft : nRight;

  nPrefix = 0;
  while( nPrefix<nShort && zLeft[nPrefix]==zRight[nPrefix] ){
    nPrefix++;
  }
  if( nPrefix<nShort ){
    while( nPrefix>0 && (zLeft[nPrefix]&0xc0)==0x80 ) nPrefix--;
  }
  nSuffix = 0;
  if( nPrefix<nShort ){
    while( nSuffix<nShort
           && zLeft[nLeft-nSuffix-1]==zRight[nRight-nSuffix-1] ){
      nSuffix++;
    }
    if( nSuffix<nShort ){
      while( nSuffix>0 && (zLeft[nLeft-nSuffix]&0xc0)==0x80 ) nSuffix--;
    }
    if( nSuffix==nLeft || nSuffix==nRight ) nPrefix = 0;
  }
  nCommon = nPrefix + nSuffix;

  /* If the prefix and suffix overlap, that means that we are dealing with
  ** a pure insertion or deletion of text that can have multiple alignments.
  ** Try to find an alignment to begins and ends on whitespace, or on
  ** punctuation, rather than in the middle of a name or number.
  */
  if( nCommon > nShort ){
    int iBest = -1;
    int iBestVal = -1;
    int i;
    int nLong = nLeft<nRight ? nRight : nLeft;
    int nGap = nLong - nShort;
    for(i=nShort-nSuffix; i<=nPrefix; i++){
       int iVal = 0;
       char c = zLeft[i];
       if( diff_isspace(c) ){
         iVal += 5;
       }else if( !fsl_isalnum(c) ){
         iVal += 2;
       }
       c = zLeft[i+nGap-1];
       if( diff_isspace(c) ){
         iVal += 5;
       }else if( !fsl_isalnum(c) ){
         iVal += 2;
       }
       if( iVal>iBestVal ){
         iBestVal = iVal;
         iBest = i;
       }
    }
    nPrefix = iBest;
    nSuffix = nShort - nPrefix;
    nCommon = nPrefix + nSuffix;
  }

  /* A single chunk of text inserted */
  if( nCommon==nLeft ){
    p->n = 1;
    p->a[0].iStart1 = nPrefix;
    p->a[0].iLen1 = 0;
    p->a[0].iStart2 = nPrefix;
    p->a[0].iLen2 = nRight - nCommon;
    improveReadability(zLeft, zRight, p);
    return;
  }

  /* A single chunk of text deleted */
  if( nCommon==nRight ){
    p->n = 1;
    p->a[0].iStart1 = nPrefix;
    p->a[0].iLen1 = nLeft - nCommon;
    p->a[0].iStart2 = nPrefix;
    p->a[0].iLen2 = 0;
    improveReadability(zLeft, zRight, p);
    return;
  }

  /* At this point we know that there is a chunk of text that has
  ** changed between the left and the right.  Check to see if there
  ** is a large unchanged section in the middle of that changed block.
  */
  nLeftDiff = nLeft - nCommon;
  nRightDiff = nRight - nCommon;
  if( nLeftDiff >= 4
   && nRightDiff >= 4
   && textLineChanges(&zLeft[nPrefix], nLeftDiff,
                      &zRight[nPrefix], nRightDiff, p)>1
  ){
    int i;
    for(i=0; i<p->n; i++){
      p->a[i].iStart1 += nPrefix;
      p->a[i].iStart2 += nPrefix;
    }
    improveReadability(zLeft, zRight, p);
    return;
  }

  /* If all else fails, show a single big change between left and right */
  p->n = 1;
  p->a[0].iStart1 = nPrefix;
  p->a[0].iLen1 = nLeft - nCommon;
  p->a[0].iStart2 = nPrefix;
  p->a[0].iLen2 = nRight - nCommon;
  improveReadability(zLeft, zRight, p);
}


/*
** The threshold at which diffBlockAlignment transitions from the
** O(N*N) Wagner minimum-edit-distance algorithm to a less process
** O(NlogN) divide-and-conquer approach.
*/
#define DIFF_ALIGN_MX  1225

/**
   FSL_DIFF_SMALL_GAP=0 is a temporary(? as of 2022-01-04) patch for a
   cosmetic-only (but unsightly) quirk of the diff engine where it
   produces a pair of identical DELETE/INSERT lines. Richard's
   preliminary solution for it is to remove the "small gap merging,"
   but he notes (in fossil /chat) that he's not recommending this as
   "the" fix.

   PS: we colloquially know this as "the lineno diff" because it was first
   reported in a diff which resulted in:

```
-  int     lineno;
+  int     lineno;
```

   (No, there are no whitespace changes there.)

   To reiterate, though: this is not a "bug," in that it does not
   cause incorrect results when applying the resulting unfified-diff
   patches. It does, however, cause confusion for human users.


   Here are two inputs which, when diffed, expose the lineno behavior:

   #1:

```
struct fnc_diff_view_state {
  int     first_line_onscreen;
  int     last_line_onscreen;
  int     diff_flags;
  int     context;
  int     sbs;
  int     matched_line;
  int     current_line;
  int     lineno;
  size_t     ncols;
  size_t     nlines;
  off_t    *line_offsets;
  bool     eof;
  bool     colour;
  bool     showmeta;
  bool     showln;
};
```
#undef blob_to_utf8_no_bom
#undef DICOSTATE

   #2:

```
struct fnc_diff_view_state {
  int     first_line_onscreen;
  int     last_line_onscreen;
  int     diff_flags;
  int     context;
  int     sbs;
  int     matched_line;
  int     selected_line;
  int     lineno;
  int     gtl;
  size_t     ncols;
  size_t     nlines;
  off_t    *line_offsets;
  bool     eof;
  bool     colour;
  bool     showmeta;
  bool     showln;
};
```

   Result without this patch:

```
Index: X.0
==================================================================
--- X.0
+++ X.1
@@ -3,15 +3,16 @@
   int     last_line_onscreen;
   int     diff_flags;
   int     context;
   int     sbs;
   int     matched_line;
+  int     selected_line;
-  int     current_line;
-  int     lineno;
+  int     lineno;
+  int     gtl;
   size_t     ncols;
   size_t     nlines;
   off_t    *line_offsets;
   bool     eof;
   bool     colour;
   bool     showmeta;
   bool     showln;
 };
```

    And with the patch:

```
Index: X.0
==================================================================
--- X.0
+++ X.1
@@ -3,15 +3,16 @@
   int     last_line_onscreen;
   int     diff_flags;
   int     context;
   int     sbs;
   int     matched_line;
-  int     current_line;
+  int     selected_line;
   int     lineno;
+  int     gtl;
   size_t     ncols;
   size_t     nlines;
   off_t    *line_offsets;
   bool     eof;
   bool     colour;
   bool     showmeta;
   bool     showln;
 };
```

*/
#define FSL_DIFF_SMALL_GAP 0

#if FSL_DIFF_SMALL_GAP
/*
** R[] is an array of six integer, two COPY/DELETE/INSERT triples for a
** pair of adjacent differences.  Return true if the gap between these
** two differences is so small that they should be rendered as a single
** edit.
*/
static int smallGap2(const int *R, int ma, int mb){
  int m = R[3];
  ma += R[4] + m;
  mb += R[5] + m;
  if( ma*mb>DIFF_ALIGN_MX ) return 0;
  return m<=2 || m<=(R[1]+R[2]+R[4]+R[5])/8;
}
#endif

static unsigned short diff_opt_context_lines(fsl_dibu_opt const * opt){
  const unsigned short dflt = 5;
  unsigned short n = opt ? opt->contextLines : dflt;
  if( !n && (opt->diffFlags & FSL_DIFF2_CONTEXT_ZERO)==0 ){
    n = dflt;
  }
  return n;
}

/*
** Minimum of two values
*/
static int diffMin(int a, int b){ return a<b ? a : b; }

/****************************************************************************/
/*
** Return the number between 0 and 100 that is smaller the closer pA and
** pB match.  Return 0 for a perfect match.  Return 100 if pA and pB are
** completely different.
**
** The current algorithm is as follows:
**
** (1) Remove leading and trailing whitespace.
** (2) Truncate both strings to at most 250 characters
** (3) If the two strings have a common prefix, measure that prefix
** (4) Find the length of the longest common subsequence that is
**     at least 150% longer than the common prefix.
** (5) Longer common subsequences yield lower scores.
*/
static int match_dline2(fsl_dline * const pA, fsl_dline * const pB){
  const char *zA;            /* Left string */
  const char *zB;            /* right string */
  int nA;                    /* Bytes in zA[] */
  int nB;                    /* Bytes in zB[] */
  int nMin;
  int nPrefix;
  int avg;                   /* Average length of A and B */
  int i, j, k;               /* Loop counters */
  int best = 0;              /* Longest match found so far */
  int score;                 /* Final score.  0..100 */
  unsigned char c;           /* Character being examined */
  unsigned char aFirst[256]; /* aFirst[X] = index in zB[] of first char X */
  unsigned char aNext[252];  /* aNext[i] = index in zB[] of next zB[i] char */

  zA = pA->z;
  if( pA->nw==0 && pA->n ){
    for(i=0; i<pA->n && diff_isspace(zA[i]); i++){}
    pA->indent = i;
    for(j=pA->n-1; j>i && diff_isspace(zA[j]); j--){}
    pA->nw = j - i + 1;
  }
  zA += pA->indent;
  nA = pA->nw;

  zB = pB->z;
  if( pB->nw==0 && pB->n ){
    for(i=0; i<pB->n && diff_isspace(zB[i]); i++){}
    pB->indent = i;
    for(j=pB->n-1; j>i && diff_isspace(zB[j]); j--){}
    pB->nw = j - i + 1;
  }
  zB += pB->indent;
  nB = pB->nw;

  if( nA>250 ) nA = 250;
  if( nB>250 ) nB = 250;
  avg = (nA+nB)/2;
  if( avg==0 ) return 0;
  nMin = nA;
  if( nB<nMin ) nMin = nB;
  if( nMin==0 ) return 68;
  for(nPrefix=0; nPrefix<nMin && zA[nPrefix]==zB[nPrefix]; nPrefix++){}
  best = 0;
  if( nPrefix>5 && nPrefix>nMin/2 ){
    best = nPrefix*3/2;
    if( best>=avg - 2 ) best = avg - 2;
  }
  if( nA==nB && memcmp(zA, zB, nA)==0 ) return 0;
  memset(aFirst, 0xff, sizeof(aFirst));
  zA--; zB--;   /* Make both zA[] and zB[] 1-indexed */
  for(i=nB; i>0; i--){
    c = (unsigned char)zB[i];
    aNext[i] = aFirst[c];
    aFirst[c] = i;
  }
  for(i=1; i<=nA-best; i++){
    c = (unsigned char)zA[i];
    for(j=aFirst[c]; j<nB-best && memcmp(&zA[i],&zB[j],best)==0; j = aNext[j]){
      int limit = diffMin(nA-i, nB-j);
      for(k=best; k<=limit && zA[k+i]==zB[k+j]; k++){}
      if( k>best ) best = k;
    }
  }
  score = 5 + ((best>=avg) ? 0 : (avg - best)*95/avg);

#if 0
  fprintf(stderr, "A: [%.*s]\nB: [%.*s]\nbest=%d avg=%d score=%d\n",
  nA, zA+1, nB, zB+1, best, avg, score);
#endif

  /* Return the result */
  return score;
}

// Forward decl for recursion's sake.
static int diffBlockAlignment(
  fsl_dline * const aLeft, int nLeft,
  fsl_dline * const aRight, int nRight,
  fsl_dibu_opt const * pOpt,
  unsigned char **pResult,
  unsigned *pNResult
);

/*
** Make a copy of a list of nLine DLine objects from one array to
** another.  Hash the new array to ignore whitespace.
*/
static void diffDLineXfer(
  fsl_dline *aTo,
  const fsl_dline *aFrom,
  int nLine
){
  int i, j, k;
  uint64_t h, h2;
  for(i=0; i<nLine; i++) aTo[i].iHash = 0;
  for(i=0; i<nLine; i++){
    const char *z = aFrom[i].z;
    int n = aFrom[i].n;
    for(j=0; j<n && diff_isspace(z[j]); j++){}
    aTo[i].z = &z[j];
    for(k=aFrom[i].n; k>j && diff_isspace(z[k-1]); k--){}
    aTo[i].n = n = k-j;
    aTo[i].indent = 0;
    aTo[i].nw = 0;
    for(h=0; j<k; j++){
      char c = z[j];
      if( !diff_isspace(c) ){
        h = (h^c)*9000000000000000041LL;
      }
    }
    aTo[i].h = h = ((h%281474976710597LL)<<FSL__LINE_LENGTH_MASK_SZ) | n;
    h2 = h % nLine;
    aTo[i].iNext = aTo[h2].iHash;
    aTo[h2].iHash = i+1;
  }
}

/*
** For a difficult diff-block alignment that was originally for
** the default consider-all-whitespace algorithm, try to find the
** longest common subsequence between the two blocks that involves
** only whitespace changes.
**
** Result is stored in *pOut and must be eventually fsl_free()d.
** Returns 0 on success, setting *pOut to NULL if no good match is
** found. Returns FSL_RC_OOM on allocation error.
*/
static int diffBlockAlignmentIgnoreSpace(
  fsl_dline * const aLeft, int nLeft,     /* Text on the left */
  fsl_dline * const aRight, int nRight,   /* Text on the right */
  fsl_dibu_opt const *pOpt,            /* Configuration options */
  unsigned char ** pOut,          /* OUTPUT: Result */
  unsigned *pNResult                /* OUTPUT: length of result */
){
  fsl__diff_cx dc;
  int iSX, iEX;                /* Start and end of LCS on the left */
  int iSY, iEY;                /* Start and end of the LCS on the right */
  unsigned char *a1, *a2;
  int n1, n2, nLCS, rc = 0;

  dc.aEdit = 0;
  dc.nEdit = 0;
  dc.nEditAlloc = 0;
  dc.nFrom = nLeft;
  dc.nTo = nRight;
  dc.cmpLine = fsl_dline_cmp_ignore_ws;
  dc.aFrom = fsl_malloc( sizeof(fsl_dline)*(nLeft+nRight) );
  if(!dc.aFrom) return FSL_RC_OOM;
  dc.aTo = &dc.aFrom[dc.nFrom];
  diffDLineXfer(dc.aFrom, aLeft, nLeft);
  diffDLineXfer(dc.aTo, aRight, nRight);
  fsl__diff_optimal_lcs(&dc,0,nLeft,0,nRight,&iSX,&iEX,&iSY,&iEY);
  fsl_free(dc.aFrom);
  nLCS = iEX - iSX;
  if( nLCS<5 ){
    /* No good LCS was found */
    *pOut = NULL;
    *pNResult = 0;
    return 0;
  }
  rc = diffBlockAlignment(aLeft,iSX,aRight,iSY,
                          pOpt,&a1, (unsigned *)&n1);
  if(rc) return rc;
  rc = diffBlockAlignment(aLeft+iEX, nLeft-iEX,
                          aRight+iEY, nRight-iEY,
                          pOpt, &a2, (unsigned *)&n2);
  if(rc){
    fsl_free(a1);
    return rc;
  }else{
    unsigned char * x = (unsigned char *)fsl_realloc(a1, n1+nLCS+n2);
    if(NULL==x){
      fsl_free(a1);
      fsl_free(a2);
      return FSL_RC_OOM;
    }
    a1 = x;
  }
  memcpy(a1+n1+nLCS,a2,n2);
  memset(a1+n1,3,nLCS);
  fsl_free(a2);
  *pNResult = (unsigned)(n1+n2+nLCS);
  *pOut = a1;
  return 0;
}

/*
** This is a helper route for diffBlockAlignment().  In this case,
** a very large block is encountered that might be too expensive to
** use the O(N*N) Wagner edit distance algorithm.  So instead, this
** block implements a less-precise but faster O(N*logN) divide-and-conquer
** approach.
**
** Result is stored in *pOut and must be eventually fsl_free()d.
** Returns 0 on success. Returns FSL_RC_OOM on allocation error.
*/
static int diffBlockAlignmentDivideAndConquer(
  fsl_dline * const aLeft, int nLeft,     /* Text on the left */
  fsl_dline * const aRight, int nRight,   /* Text on the right */
  fsl_dibu_opt const *pOpt,            /* Configuration options */
  unsigned char ** pOut,       /* OUTPUT: result */
  unsigned *pNResult                /* OUTPUT: length of result */
){
  fsl_dline *aSmall;               /* The smaller of aLeft and aRight */
  fsl_dline *aBig;                 /* The larger of aLeft and aRight */
  int nSmall, nBig;            /* Size of aSmall and aBig.  nSmall<=nBig */
  int iDivSmall, iDivBig;      /* Divider point for aSmall and aBig */
  int iDivLeft, iDivRight;     /* Divider point for aLeft and aRight */
  unsigned char *a1 = 0, *a2 = 0; /* Results of the alignments on two halves */
  int n1, n2;                  /* Number of entries in a1 and a2 */
  int score, bestScore;        /* Score and best score seen so far */
  int i;                       /* Loop counter */
  int rc;

  if( nLeft>nRight ){
    aSmall = aRight;
    nSmall = nRight;
    aBig = aLeft;
    nBig = nLeft;
  }else{
    aSmall = aLeft;
    nSmall = nLeft;
    aBig = aRight;
    nBig = nRight;
  }
  iDivBig = nBig/2;
  iDivSmall = nSmall/2;
  bestScore = 10000;
  for(i=0; i<nSmall; i++){
    score = match_dline2(aBig+iDivBig, aSmall+i) + abs(i-nSmall/2)*2;
    if( score<bestScore ){
      bestScore = score;
      iDivSmall = i;
    }
  }
  if( aSmall==aRight ){
    iDivRight = iDivSmall;
    iDivLeft = iDivBig;
  }else{
    iDivRight = iDivBig;
    iDivLeft = iDivSmall;
  }
  rc = diffBlockAlignment(aLeft,iDivLeft,aRight,iDivRight,
                          pOpt,&a1, (unsigned*)&n1);
  if(!rc){
    rc = diffBlockAlignment(aLeft+iDivLeft, nLeft-iDivLeft,
                            aRight+iDivRight, nRight-iDivRight,
                            pOpt, &a2, (unsigned*)&n2);
  }
  if(rc){
    fsl_free(a1);
    fsl_free(a2);
  }else{
    unsigned char * x = (unsigned char *)fsl_realloc(a1, n1+n2);
    if(!x) rc = FSL_RC_OOM;
    else{
      a1 = x;
      memcpy(a1+n1,a2,n2);
      *pNResult = (unsigned)(n1+n2);
      *pOut = a1;
    }
    fsl_free(a2);
  }
  return rc;
}


/*
** There is a change block in which nLeft lines of text on the left are
** converted into nRight lines of text on the right.  This routine computes
** how the lines on the left line up with the lines on the right.
**
** The return value is a buffer of unsigned characters, obtained from
** fsl_malloc().  (The caller needs to free the `*pResult` value using
** fsl_free().)  Entries in the returned array have values as follows:
**
**    1.  Delete the next line of pLeft.
**    2.  Insert the next line of pRight.
**    3.  The next line of pLeft changes into the next line of pRight.
**    4.  Delete one line from pLeft and add one line to pRight.
**
** The length of the returned array will be at most nLeft+nRight bytes.
** If the first bytes is 4, that means we could not compute reasonable
** alignment between the two blocks.
**
** Algorithm:  Wagner's minimum edit-distance algorithm, modified by
** adding a cost to each match based on how well the two rows match
** each other.  Insertion and deletion costs are 50.  Match costs
** are between 0 and 100 where 0 is a perfect match 100 is a complete
** mismatch.
*/
int diffBlockAlignment(
  fsl_dline * const aLeft, int nLeft,     /* Text on the left */
  fsl_dline * const aRight, int nRight,   /* Text on the right */
  fsl_dibu_opt const * pOpt,             /* Configuration options */
  unsigned char **pResult,         /* Raw result */
  unsigned *pNResult               /* OUTPUT: length of result */
){
  int i, j, k;                 /* Loop counters */
  int *a = 0;                  /* One row of the Wagner matrix */
  int *pToFree = 0;            /* Space that needs to be freed */
  unsigned char *aM = 0;       /* Wagner result matrix */
  int nMatch, iMatch;          /* Number of matching lines and match score */
  int aBuf[100];               /* Stack space for a[] if nRight not to big */
  int rc = 0;

  if( nLeft==0 ){
    aM = fsl_malloc( nRight + 2 );
    if(!aM) return FSL_RC_OOM;
    memset(aM, 2, nRight);
    *pNResult = nRight;
    *pResult = aM;
    return 0;
  }
  if( nRight==0 ){
    aM = fsl_malloc( nLeft + 2 );
    if(!aM) return FSL_RC_OOM;
    memset(aM, 1, nLeft);
    *pNResult = nLeft;
    *pResult = aM;
    return 0;
  }

  /* For large alignments, try to use alternative algorithms that are
  ** faster than the O(N*N) Wagner edit distance. */
  if( nLeft*nRight>DIFF_ALIGN_MX
      && (pOpt->diffFlags & FSL_DIFF2_SLOW_SBS)==0 ){
    if( (pOpt->diffFlags & FSL_DIFF2_IGNORE_ALLWS)==0 ){
      *pResult = NULL;
      rc = diffBlockAlignmentIgnoreSpace(aLeft, nLeft,aRight,nRight,
                                         pOpt, pResult, pNResult);
      if(rc || *pResult) return rc;
    }
    return diffBlockAlignmentDivideAndConquer(aLeft, nLeft,aRight, nRight,
                                              pOpt, pResult, pNResult);
  }

  /* If we reach this point, we will be doing an O(N*N) Wagner minimum
  ** edit distance to compute the alignment.
  */
  if( nRight < (int)(sizeof(aBuf)/sizeof(aBuf[0]))-1 ){
    pToFree = 0;
    a = aBuf;
  }else{
    a = pToFree = fsl_malloc( sizeof(a[0])*(nRight+1) );
    if(!a){
      rc = FSL_RC_OOM;
      goto end;
    }
  }
  aM = fsl_malloc( (nLeft+1)*(nRight+1) );
  if(!aM){
    rc = FSL_RC_OOM;
    goto end;
  }

  /* Compute the best alignment */
  for(i=0; i<=nRight; i++){
    aM[i] = 2;
    a[i] = i*50;
  }
  aM[0] = 0;
  for(j=1; j<=nLeft; j++){
    int p = a[0];
    a[0] = p+50;
    aM[j*(nRight+1)] = 1;
    for(i=1; i<=nRight; i++){
      int m = a[i-1]+50;
      int d = 2;
      if( m>a[i]+50 ){
        m = a[i]+50;
        d = 1;
      }
      if( m>p ){
        int const score =
          match_dline2(&aLeft[j-1], &aRight[i-1]);
        if( (score<=90 || (i<j+1 && i>j-1)) && m>p+score ){
          m = p+score;
          d = 3 | score*4;
        }
      }
      p = a[i];
      a[i] = m;
      aM[j*(nRight+1)+i] = d;
    }
  }

  /* Compute the lowest-cost path back through the matrix */
  i = nRight;
  j = nLeft;
  k = (nRight+1)*(nLeft+1)-1;
  nMatch = iMatch = 0;
  while( i+j>0 ){
    unsigned char c = aM[k];
    if( c>=3 ){
      assert( i>0 && j>0 );
      i--;
      j--;
      nMatch++;
      iMatch += (c>>2);
      aM[k] = 3;
    }else if( c==2 ){
      assert( i>0 );
      i--;
    }else{
      assert( j>0 );
      j--;
    }
    k--;
    aM[k] = aM[j*(nRight+1)+i];
  }
  k++;
  i = (nRight+1)*(nLeft+1) - k;
  memmove(aM, &aM[k], i);
  *pNResult = i;
  *pResult = aM;

  end:
  fsl_free(pToFree);
  return rc;
}


/*
** Format a diff using a fsl_dibu object
*/
static int fdb__format(
  fsl__diff_cx * const cx,
  fsl_dibu * const pBuilder
){
  fsl_dline *A;        /* Left side of the diff */
  fsl_dline *B;        /* Right side of the diff */
  fsl_dibu_opt const * pOpt = pBuilder->opt;
  const int *R;          /* Array of COPY/DELETE/INSERT triples */
  unsigned int a;    /* Index of next line in A[] */
  unsigned int b;    /* Index of next line in B[] */
  unsigned int r;        /* Index into R[] */
  unsigned int nr;       /* Number of COPY/DELETE/INSERT triples to process */
  unsigned int mxr;      /* Maximum value for r */
  unsigned int na, nb;   /* Number of lines shown from A and B */
  unsigned int i, j;     /* Loop counters */
  unsigned int m, ma, mb;/* Number of lines to output */
  signed int skip;   /* Number of lines to skip */
  unsigned int contextLines; /* Lines of context above and below each change */
  unsigned short passNumber = 0;
  int rc = 0;
  
#define RC if(rc) goto end
#define METRIC(M) if(1==passNumber) ++pBuilder->metrics.M
  pass_again:
  contextLines = diff_opt_context_lines(pOpt);
  skip = 0;
  a = b = 0;
  A = cx->aFrom;
  B = cx->aTo;
  R = cx->aEdit;
  mxr = cx->nEdit;
  //MARKER(("contextLines=%u, nEdit = %d, mxr=%u\n", contextLines, cx->nEdit, mxr));
  while( mxr>2 && R[mxr-1]==0 && R[mxr-2]==0 ){ mxr -= 3; }

  pBuilder->lnLHS = pBuilder->lnRHS = 0;
  ++passNumber;
  if(pBuilder->start){
    pBuilder->passNumber = passNumber;
    rc = pBuilder->start(pBuilder);
    RC;
  }
  for(r=0; r<mxr; r += 3*nr){
    /* Figure out how many triples to show in a single block */
    for(nr=1; R[r+nr*3]>0 && R[r+nr*3]<(int)contextLines*2; nr++){}

#if 0
    /* MISSING: this "should" be replaced by a stateful predicate
       function, probably in the fsl_dibu_opt class. */
    /* If there is a regex, skip this block (generate no diff output)
    ** if the regex matches or does not match both insert and delete.
    ** Only display the block if one side matches but the other side does
    ** not.
    */
    if( pOpt->pRe ){
      int hideBlock = 1;
      int xa = a, xb = b;
      for(i=0; hideBlock && i<nr; i++){
        int c1, c2;
        xa += R[r+i*3];
        xb += R[r+i*3];
        c1 = re_dline_match(pOpt->pRe, &A[xa], R[r+i*3+1]);
        c2 = re_dline_match(pOpt->pRe, &B[xb], R[r+i*3+2]);
        hideBlock = c1==c2;
        xa += R[r+i*3+1];
        xb += R[r+i*3+2];
      }
      if( hideBlock ){
        a = xa;
        b = xb;
        continue;
      }
    }
#endif

    /* Figure out how many lines of A and B are to be displayed
    ** for this change block.
    */
    if( R[r]>(int)contextLines ){
      na = nb = contextLines;
      skip = R[r] - contextLines;
    }else{
      na = nb = R[r];
      skip = 0;
    }
    for(i=0; i<nr; i++){
      na += R[r+i*3+1];
      nb += R[r+i*3+2];
    }
    if( R[r+nr*3]>(int)contextLines ){
      na += contextLines;
      nb += contextLines;
    }else{
      na += R[r+nr*3];
      nb += R[r+nr*3];
    }
    for(i=1; i<nr; i++){
      na += R[r+i*3];
      nb += R[r+i*3];
    }

    //MARKER(("Chunk header... a=%u, b=%u, na=%u, nb=%u, skip=%d\n", a, b, na, nb, skip));
    if(pBuilder->chunkHeader
       /* The following bit is a kludge to keep from injecting a chunk
          header between chunks which are directly adjacent.

          The problem, however, is that we cannot skip _reliably_
          without also knowing how the next chunk aligns. If we skip
          it here, the _previous_ chunk header may well be telling
          the user a lie with regards to line numbers.

          Fossil itself does not have this issue because it generates
          these chunk headers directly in this routine, instead of in
          the diff builder, depending on a specific flag being set in
          builder->opt. Also (related), in that implementation, fossil
          will collapse chunks which are separated by less than the
          context distance into contiguous chunks (see below). Because
          we farm out the chunkHeader lines to the builder, we cannot
          reliably do that here.
       */
#if 0
       && !skip
#endif
       ){
      rc = pBuilder->chunkHeader(pBuilder,
                                 (uint32_t)(na ? a+skip+1 : a+skip),
                                 (uint32_t)na,
                                 (uint32_t)(nb ? b+skip+1 : b+skip),
                                 (uint32_t)nb);
      RC;
    }

    /* Show the initial common area */
    a += skip;
    b += skip;
    m = R[r] - skip;
    if( r ) skip -= contextLines;

    //MARKER(("Show the initial common... a=%u, b=%u, m=%u, r=%u, skip=%d\n", a, b, m, r, skip));
    if( skip>0 ){
      if( NULL==pBuilder->chunkHeader && skip<(int)contextLines ){
        /* 2021-09-27: BUG: this is incompatible with unified diff
           format. The generated header lines say we're skipping X
           lines but we then end up including lines which that header
           says to skip. As a workaround, we'll only run this when
           pBuilder->chunkHeader is NULL, noting that fossil's diff
           builder interface does not have that method (and thus
           doesn't have this issue, instead generating chunk headers
           directly in this algorithm).

           Without this block, our "utxt" diff builder can mimic
           fossil's non-diff builder unified diff format, except that
           we add Index lines (feature or bug?). With this block,
           the header values output above are wrong.
        */
        /* If the amount to skip is less that the context band, then
        ** go ahead and show the skip band as it is not worth eliding */
        //MARKER(("skip %d < contextLines %d\n", skip, contextLines));
        /* from fossil(1) from formatDiff() */
        for(j=0; 0==rc && j<(unsigned)skip; j++){
          //MARKER(("(A) COMMON\n"));
          rc = pBuilder->common(pBuilder, &A[a+j-skip]);
        }
      }else{
        rc = pBuilder->skip(pBuilder, skip);
      }
      RC;
    }
    for(j=0; 0==rc && j<m; j++){
      //MARKER(("(B) COMMON\n"));
      rc = pBuilder->common(pBuilder, &A[a+j]);
    }
    RC;
    a += m;
    b += m;
    //MARKER(("Show the differences... a=%d, b=%d, m=%d\n", a, b, m));

    /* Show the differences */
    for(i=0; i<nr; i++){
      unsigned int nAlign;
      unsigned char *alignment = 0;
      ma = R[r+i*3+1];   /* Lines on left but not on right */
      mb = R[r+i*3+2];   /* Lines on right but not on left */

#if FSL_DIFF_SMALL_GAP
  /* Try merging the current block with subsequent blocks, if the
      ** subsequent blocks are nearby and their result isn't too big.
      */
      while( i<nr-1 && smallGap2(&R[r+i*3],ma,mb) ){
        i++;
        m = R[r+i*3];
        ma += R[r+i*3+1] + m;
        mb += R[r+i*3+2] + m;
      }
#endif

      /* Try to find an alignment for the lines within this one block */
      rc = diffBlockAlignment(&A[a], ma, &B[b], mb, pOpt,
                              &alignment, &nAlign);
      RC;
      for(j=0; ma+mb>0; j++){
        assert( j<nAlign );
        switch( alignment[j] ){
          case 1: {
            /* Delete one line from the left */
            METRIC(deletions);
            rc = pBuilder->deletion(pBuilder, &A[a]);
            if(rc) goto bail;
            ma--;
            a++;
            break;
          }
          case 2: {
            /* Insert one line on the right */
            METRIC(insertions);
            rc = pBuilder->insertion(pBuilder, &B[b]);
            if(rc) goto bail;
            assert( mb>0 );
            mb--;
            b++;
            break;
          }
          case 3: {
            /* The left line is changed into the right line */
            if( 0==cx->cmpLine(&A[a], &B[b]) ){
              rc = pBuilder->common(pBuilder, &A[a]);
            }else{
              METRIC(edits);
              rc = pBuilder->edit(pBuilder, &A[a], &B[b]);
            }
            if(rc) goto bail;
            assert( ma>0 && mb>0 );
            ma--;
            mb--;
            a++;
            b++;
            break;
          }
          case 4: {
            /* Delete from left then separately insert on the right */
            METRIC(replacements);
            rc = pBuilder->replacement(pBuilder, &A[a], &B[b]);
            if(rc) goto bail;
            ma--;
            a++;
            mb--;
            b++;
            break;
          }
        }
      }
      assert( nAlign==j );
      fsl_free(alignment);
      if( i<nr-1 ){
        m = R[r+i*3+3];
        for(j=0; 0==rc && j<m; j++){
          //MARKER(("D common\n"));
          rc = pBuilder->common(pBuilder, &A[a+j]);
        }
        RC;
        b += m;
        a += m;
      }
      continue;
      bail:
      assert(rc);
      fsl_free(alignment);
      goto end;
    }

    /* Show the final common area */
    assert( nr==i );
    m = R[r+nr*3];
    if( m>contextLines ) m = contextLines;
    for(j=0; 0==rc && j<m && j<contextLines; j++){
      //MARKER(("E common\n"));
      rc = pBuilder->common(pBuilder, &A[a+j]);
    }
    RC;
  }
  if( R[r]>(int)contextLines ){
    rc = pBuilder->skip(pBuilder, R[r] - contextLines);
  }
  end:
#undef RC
#undef METRIC
  if(0==rc){
    if(pBuilder->finish) pBuilder->finish(pBuilder);
    if(pBuilder->twoPass && 1==passNumber){
      goto pass_again;
    }
  }
  return rc;
}

/* MISSING(?) fossil(1) converts the diff inputs into utf8 with no
   BOM. Whether we really want to do that here or rely on the caller
   to is up for debate. If we do it here, we have to make the inputs
   non-const, which seems "wrong" for a library API. */
#define blob_to_utf8_no_bom(A,B) (void)0

/**
   Performs a diff of version 1 (pA) and version 2 (pB). ONE of
   pBuilder or outRaw must be non-NULL. If pBuilder is not NULL, all
   output for the diff is emitted via pBuilder. If outRaw is not NULL
   then on success *outRaw is set to the array of diff triples,
   transfering ownership to the caller, who must eventually fsl_free()
   it. On error, *outRaw is not modified but pBuilder may have emitted
   partial output. That is not knowable for the general
   case. Ownership of pBuilder is not changed. If pBuilder is not NULL
   then pBuilder->opt must be non-NULL.
*/
static int fsl_diff2_text_impl(fsl_buffer const *pA,
                               fsl_buffer const *pB,
                               fsl_dibu * const pBuilder,
                               fsl_dibu_opt const * const opt_,
                               int ** outRaw){
  int rc = 0;
  fsl__diff_cx c = fsl__diff_cx_empty;
  bool ignoreWs = false;
  int ansiOptCount = 0;
  fsl_dibu_opt opt = *opt_
    /*we need a copy for the sake of the FSL_DIFF2_INVERT flag*/;
  if(!pA || !pB || (pBuilder && outRaw)) return FSL_RC_MISUSE;

  blob_to_utf8_no_bom(pA, 0);
  blob_to_utf8_no_bom(pB, 0);

  if( opt.diffFlags & FSL_DIFF2_INVERT ){
    char const * z;
    fsl_buffer const *pTemp = pA;
    pA = pB;
    pB = pTemp;
    z = opt.hashRHS; opt.hashRHS = opt.hashLHS; opt.hashLHS = z;
    z = opt.nameRHS; opt.nameRHS = opt.nameLHS; opt.nameLHS = z;
  }
#define AOPT(OPT) \
  if(opt.ansiColor.OPT) ansiOptCount += (*opt.ansiColor.OPT) ? 1 : 0; \
  else opt.ansiColor.OPT = ""
  AOPT(insertion);
  AOPT(edit);
  AOPT(deletion);
#undef AOPT
  if(0==ansiOptCount){
    opt.ansiColor.reset = "";
  }else if(!opt.ansiColor.reset || !*opt.ansiColor.reset){
    opt.ansiColor.reset = "\x1b[0m";
  }
  ignoreWs = (opt.diffFlags & FSL_DIFF2_IGNORE_ALLWS)!=0;
  if(FSL_DIFF2_IGNORE_ALLWS==(opt.diffFlags & FSL_DIFF2_IGNORE_ALLWS)){
    c.cmpLine = fsl_dline_cmp_ignore_ws;
  }else{
    c.cmpLine = fsl_dline_cmp;
  }
 
  rc = fsl_break_into_dlines(fsl_buffer_cstr(pA), (fsl_int_t)pA->used,
                             (uint32_t*)&c.nFrom, &c.aFrom, opt.diffFlags);
  if(rc) goto end;
  rc = fsl_break_into_dlines(fsl_buffer_cstr(pB), (fsl_int_t)pB->used,
                             (uint32_t*)&c.nTo, &c.aTo, opt.diffFlags);
  if(rc) goto end;

  /* Compute the difference */
  rc = fsl__diff_all(&c);
  if(rc) goto end;
  if( ignoreWs && c.nEdit==6 && c.aEdit[1]==0 && c.aEdit[2]==0 ){
    rc = FSL_RC_DIFF_WS_ONLY;
    goto end;
  }
  if( (opt.diffFlags & FSL_DIFF2_NOTTOOBIG)!=0 ){
    int i, m, n;
    int const * const a = c.aEdit;
    int const mx = c.nEdit;
    for(i=m=n=0; i<mx; i+=3){ m += a[i]; n += a[i+1]+a[i+2]; }
    if( !n || n>10000 ){
      rc = FSL_RC_RANGE;
      /* diff_errmsg(pOut, DIFF_TOO_MANY_CHANGES, diffFlags); */
      goto end;
    }
  }
  //fsl__dump_triples(&c, __FILE__, __LINE__);
  if( (opt.diffFlags & FSL_DIFF2_NOOPT)==0 ){
    fsl__diff_optimize(&c);
  }
  //fsl__dump_triples(&c, __FILE__, __LINE__);

  /**
     Reference:

     https://fossil-scm.org/home/file?ci=cae7036bb7f07c1b&name=src/diff.c&ln=2749-2804

     Noting that:

     - That function's return value is this one's *outRaw

     - DIFF_NUMSTAT flag is not implemented. For that matter,
     flags which result in output going anywhere except for
     pBuilder->out are not implemented here, e.g. DIFF_RAW.

     That last point makes this impl tiny compared to the original!
  */
  if(pBuilder){
    fsl_dibu_opt const * oldOpt = pBuilder->opt;
    pBuilder->opt = &opt;
    rc = fdb__format(&c, pBuilder);
    pBuilder->opt = oldOpt;
  }
  end:
  if(0==rc && outRaw){
    *outRaw = c.aEdit;
    c.aEdit = 0;
  }
  fsl__diff_cx_clean(&c);
  return rc;
}

int fsl_diff_v2(fsl_buffer const * pv1,
                fsl_buffer const * pv2,
                fsl_dibu * const pBuilder){
  return fsl_diff2_text_impl(pv1, pv2, pBuilder, pBuilder->opt, NULL);
}

int fsl_diff_v2_raw(fsl_buffer const * pv1,
                    fsl_buffer const * pv2,
                    fsl_dibu_opt const * const opt,
                    int **outRaw ){
  return fsl_diff2_text_impl(pv1, pv2, NULL,
                             opt ? opt : &fsl_dibu_opt_empty,
                             outRaw);
}


#undef DIFF_ALIGN_MX
#undef blob_to_utf8_no_bom
#undef FSL_DIFF_SMALL_GAP
#undef diff_isspace
#undef LENGTH
/* end of file ./src/diff2.c */
/* end of file ./src/diff.c */
/* start of file ./src/encode.c */
/* -*- Mode: C; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 2 -*- */ 
/* vim: set ts=2 et sw=2 tw=80: */
/*
  Copyright 2013-2021 The Libfossil Authors, see LICENSES/BSD-2-Clause.txt

  SPDX-License-Identifier: BSD-2-Clause-FreeBSD

  if( pBomSize ) *pBomSize = bomSize;
  return fsl_buffer_size(b)<bomSize
    ? false
    : memcmp(z, bom, bomSize)==0;
}

bool fsl_invalid_utf8(fsl_buffer const * const b){
  fsl_size_t n;
  fsl_size_t n = 0;
  const unsigned char *z = (unsigned char *) fsl_buffer_cstr2(b, &n);
  unsigned char c; /* lead byte to be handled. */
  if( n==0 ) return false;  /* Empty file -> OK */
  c = *z;
  while( --n>0 ){
    if( c>=0x80 ){
      const unsigned char *def; /* pointer to range table*/

                    " WHERE tagid=%d AND tagxref.rid=ancestor.rid"
                    "   AND value=%Q AND tagtype>0)"
    "  LIMIT 1",
    rid, rid, FSL_TAGID_BRANCH, zBranch
  );
}

int fsl_branch_of_rid(fsl_cx * const f, fsl_int_t rid,
int fsl_branch_of_rid(fsl_cx * const f, fsl_id_t rid,
                      bool doFallback, char ** zOut ){
  char *zBr = 0;
  fsl_db * const db = fsl_cx_db_repo(f);
  fsl_stmt st = fsl_stmt_empty;
  int rc;
  if(!fsl_needs_repo(f)) return FSL_RC_NOT_A_REPO;
  assert(db);

      ? fsl_cx_err_set(f, FSL_RC_ALREADY_EXISTS,
                       "File already exists and "
                       "allowOverwrite is false: %s",
                       opt->filename)
      : FSL_RC_ALREADY_EXISTS;
  }
  if(f){
    rc = fsl_ckout_close(f)
    rc = fsl_close_scm_dbs(f)
      /* Will fail if a transaction is active! */;
    switch(rc){
      case 0:
        break;
      default:
        return rc;
    }

      fsl_stmt_finalize(&s);
    }
    return rc;
  }
}

/* UNTESTED */
char fsl_repo_is_readonly(fsl_cx const * f){
  if(!f || !f->dbMain) return 0;
bool fsl_repo_is_readonly(fsl_cx const * f){
  if(!f || !f->dbMain) return false;
  else{
    int const roleId = f->ckout.db.dbh ? FSL_DBROLE_MAIN : FSL_DBROLE_REPO
      /* If CKOUT is attached, it is the main DB and REPO is ATTACHed. */
      ;
    char const * zRole = fsl_db_role_name(roleId);
    assert(f->dbMain);
    return sqlite3_db_readonly(f->dbMain->dbh, zRole) ? 1 : 0;
    return sqlite3_db_readonly(f->dbMain->dbh, zRole) ? true : false;
  }
}

int fsl__repo_record_filename(fsl_cx * const f){
  fsl_db * dbR = fsl_needs_repo(f);
  fsl_db * dbC;
  fsl_db * dbConf;

}


bool fsl_repo_forbids_delta_manifests(fsl_cx * const f){
  return fsl_config_get_bool(f, FSL_CONFDB_REPO, false,
                             "forbid-delta-manifests");
}

int fsl_tkt_id_to_rids(fsl_cx * const f, char const * tktId,
                       fsl_id_t ** ridList){
  fsl_db * const dbR = fsl_needs_repo(f);
  if(!dbR) return FSL_RC_NOT_A_REPO;
  fsl_stmt q = fsl_stmt_empty;
  int rc;
  fsl_id_t * rids = 0;
  int const isFullId = fsl_is_uuid(tktId);
  unsigned int n = 0;
  if(FSL_STRLEN_SHA1<isFullId){
    return fsl_cx_err_set(f, FSL_RC_RANGE,
                          "Ticket ID is not valid. Expecting <=%d bytes of "
                          "lower-case hex values.", FSL_STRLEN_SHA1);
  }
  rc = fsl_cx_transaction_begin(f);
  if(rc) return rc;
  if(isFullId){
    // Expect an exact match...
    assert(FSL_STRLEN_SHA1==isFullId);
    rc = fsl_cx_prepare(f, &q,
                        "SELECT b.rid, b.uuid FROM blob b, tagxref x, tag t "
                        "WHERE t.tagname = 'tkt-'||%Q "
                        "AND t.tagid=x.tagid AND x.rid=b.rid "
                        "ORDER BY x.mtime, x.rowid",
                        tktId);
  }else{
    /* Check for an ambiguous match of an ID prefix...
     */
    int32_t const c =
      fsl_db_g_int32(dbR, -1,
                     "SELECT COUNT(distinct tagname) FROM tag "
                     "WHERE tagname GLOB 'tkt-'||%Q||'*'", tktId);
    if(c<0){
      rc = fsl_cx_uplift_db_error(f, dbR);
      goto end;
    }else if(0==c){
      n = 0;
      goto not_found;
    }else if(c>1){
      rc = fsl_cx_err_set(f, FSL_RC_AMBIGUOUS,
                          "Ticket ID prefix is ambiguous: %s",
                          tktId);
      goto end;
    }
    rc = fsl_cx_prepare(f, &q,
                        "SELECT b.rid, b.uuid FROM blob b, tagxref x, tag t "
                        "WHERE t.tagname GLOB 'tkt-'||%Q||'*' "
                        "AND t.tagid=x.tagid AND x.rid=b.rid "
                        "ORDER BY x.mtime, x.rowid",
                        tktId);
  }
  if(rc) return rc;
  // Count how many we have to allocate for...
  while(FSL_RC_STEP_ROW==fsl_stmt_step(&q)) ++n;
  fsl_stmt_reset(&q);
  not_found:
  if(!n){
    rc = fsl_cx_err_set(f, FSL_RC_NOT_FOUND,
                        "No ticket found with ID%s %s.",
                        isFullId ? "" : " prefix",
                        tktId);
    goto end;
  }
  // Populate the result list...
  rids = (fsl_id_t*)fsl_malloc(sizeof(fsl_id_t)*(n+1));
  if(!rids){
    rc = FSL_RC_OOM;
    goto end;
  }
  unsigned i = 0;
  while(FSL_RC_STEP_ROW==fsl_stmt_step(&q)){
    assert(i<n);
    rids[i++] = fsl_stmt_g_id(&q, 0);
  }
  assert(i==n);
  rids[i] = 0;
  end:
  if(0==rc) *ridList = rids;
  else fsl_free(rids);
  fsl_stmt_finalize(&q);
  fsl_cx_transaction_end(f,false);
  return rc;
}

#undef MARKER
/* end of file ./src/repo.c */
/* start of file ./src/schema.c */
/* -*- Mode: C; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 2 -*- */ 
/* vim: set ts=2 et sw=2 tw=80: */
/*

32, 91, 115, 112, 108, 105, 116, 32, 91, 114, 101, 97, 100, 32, 36, 105, 110, 93, 32, 92, 
110, 93, 10, 32, 32, 32, 32, 99, 108, 111, 115, 101, 32, 36, 105, 110, 10, 32, 32, 125, 
10, 32, 32, 115, 101, 116, 32, 78, 32, 91, 108, 108, 101, 110, 103, 116, 104, 32, 36, 100, 
105, 102, 102, 116, 120, 116, 93, 10, 32, 32, 115, 101, 116, 32, 105, 105, 32, 48, 10, 32, 
32, 115, 101, 116, 32, 110, 68, 105, 102, 102, 115, 32, 48, 10, 32, 32, 115, 101, 116, 32, 
110, 49, 32, 48, 10, 32, 32, 115, 101, 116, 32, 110, 50, 32, 48, 32, 32, 10, 32, 32, 
97, 114, 114, 97, 121, 32, 115, 101, 116, 32, 119, 105, 100, 116, 104, 115, 32, 123, 116, 120, 
116, 32, 51, 32, 108, 110, 32, 51, 32, 109, 107, 114, 32, 49, 125, 10, 32, 32, 119, 104, 
116, 32, 51, 32, 108, 110, 32, 54, 32, 109, 107, 114, 32, 49, 125, 10, 32, 32, 119, 104, 
105, 108, 101, 32, 123, 91, 115, 101, 116, 32, 108, 105, 110, 101, 32, 91, 103, 101, 116, 76, 
105, 110, 101, 32, 36, 100, 105, 102, 102, 116, 120, 116, 32, 36, 78, 32, 105, 105, 93, 93, 
32, 33, 61, 32, 45, 49, 125, 32, 123, 10, 32, 32, 32, 32, 115, 119, 105, 116, 99, 104, 
32, 45, 45, 32, 91, 108, 105, 110, 100, 101, 120, 32, 36, 108, 105, 110, 101, 32, 48, 93, 
32, 123, 10, 32, 32, 32, 32, 32, 32, 70, 73, 76, 69, 32, 123, 10, 32, 32, 32, 32, 
32, 32, 32, 32, 105, 110, 99, 114, 32, 110, 68, 105, 102, 102, 115, 10, 32, 32, 32, 32, 
32, 32, 32, 32, 102, 111, 114, 101, 97, 99, 104, 32, 119, 120, 32, 91, 108, 105, 115, 116, 

/** @typedef typedef int (*fsl_list_visitor_f)(void * p, void * visitorState )

    Generic visitor interface for fsl_list lists.  Used by
    fsl_list_visit(). p is the pointer held by that list entry and
    visitorState is the 4th argument passed to fsl_list_visit().

    Implementations must return 0 on success. Any other value causes
    looping to stop and that value to be returned, but interpration
    looping to stop and that value to be returned, but interpretation
    of the value is up to the caller (it might or might not be an
    error, depending on the context). Note that client code may use
    custom values, and is not strictly required to use FSL_RC_xxx
    values. HOWEVER...  all of the libfossil APIs which take these
    as arguments may respond differently to some codes (most notable
    FSL_RC_BREAK, which they tend to treat as a
    stop-iteration-without-error result), so clients are strongly

      The text of the line. Owned by higher-level code.  Not
      necessarily NUL-terminated: this->n holds its length.
  */
  const char *z;
  /** Number of bytes of z which belong to this line. */
  unsigned short n;
  // All members after this point are strictly for internal use only.
  /** Indent of the line. Only !=0 with certain options. */
  /** Index of first non-space char. */
  unsigned short indent;
  /** Number of bytes without leading/trailing space. */
  unsigned short nw;
  /** Hash of the line. Lower X bits are the length. */
  uint64_t h;
  /** 1+(Index of next line with same the same hash) */
  unsigned int iNext;
  /**
     An array of fsl_dline elements serves two purposes.  The fields
     above are one per line of input text.  But each entry is also

   The internal APIs which drive each instance of this class guaranty
   that if any method of this class returns non-0 (an error code) then
   no futher methods will be called except for finalize().
*/
struct fsl_dibu {
  /**
     Config info, owned by higher-level routines. Every diff builder
     requires one of these. Builders are prohibited from modifying
     these but the diff driver will.
     requires one of these but not all options are relevant for all
     builders.

     Note that the diff driver may make a bitwise copy of this object
     and use _that_ one for the actual diff generation. That is,
     methods of this class must never assume that this member's
     pointer refers to a specific object. (This leeway is necessary in
     order to implement diff inversion (swapping the LHS/RHS of a
     diff).)
  */
  fsl_dibu_opt * opt;
  fsl_dibu_opt const * opt;
  /**
     Can optionally be set by factory functions to some internal
     opaque value, so that non-member routines specific to that type can determine
     whether any given builder is of the proper type.
   */
  */
  void const * typeID;
  /**
     If not NULL, this is called once per pass per diff to give the
     builder a chance to perform any bootstrapping initialization or
     header output. At the point this is called, this->cfg is assumed
     to have been filled out properly. Diff builder implementations
     which require dynamic resource allocation may perform it here or

   @see fsl_deck_parse()
   @see fsl_deck_load_rid()
   @see fsl_deck_finalize()
   @see fsl_deck_clean()
   @see fsl_deck_save()
   @see fsl_deck_A_set()
   @see fsl_deck_B_set()
   @see fsl_deck_C_set()
   @see fsl_deck_D_set()
   @see fsl_deck_E_set()
   @see fsl_deck_F_add()
   @see fsl_deck_J_add()
   @see fsl_deck_K_set()
   @see fsl_deck_L_set()
   @see fsl_deck_M_add()

   Implementations must return 0 on success, non-0 on error. Some
   APIs using this interface may specify that FSL_RC_BREAK can be
   used to stop iteration over a loop without signaling an error.
   In such cases the APIs will translate FSL_RC_BREAK to 0 for
   result purposes, but will stop looping over whatever it is they
   are looping over.

   Note that the passed-in deck "should" be const but is not because
   iterating over a deck's F-cards requires non-const state.
*/
typedef int (*fsl_deck_visitor_f)( fsl_cx * f, fsl_deck const * d,
typedef int (*fsl_deck_visitor_f)( fsl_cx * const f, fsl_deck * const d,
                                   void * state );

/**
   For each unique wiki page name in f's repostory, this calls
   cb(), passing it the manifest of the most recent version of that
   page. The callback should return 0 on success, FSL_RC_BREAK to
   stop looping without an error, or any other non-0 code

/**
   Frees all memory owned by li and the F-cards it contains. Does not
   free the li pointer.
*/
FSL_EXPORT void fsl_card_F_list_finalize( fsl_card_F_list * li );

/**
   Iterates over all artifacts in f's current repository of the given
   type, passing each one to the given callback. If the callback
   returns non-0, iteration stops and that code is propagated back to
   the caller _unless_ the code is FSL_RC_BREAK, which means to stop
   iteration and return 0.

   The following artifact types are currently supported by this
   operation:

   FSL_SATYPE_CHECKIN, FSL_SATYPE_CONTROL, FSL_SATYPE_WIKI,
   FSL_SATYPE_TICKET, FSL_SATYPE_TECHNOTE, FSL_SATYPE_FORUMPOST

   (CLUSTER and ATTACHMENT are missing only because they're not(?)
   readily findable without parsing every blob in the blob table.)

   The decks are iterated over an an unspecified order except for:

   - WIKI and TECHNOTE entries are visited from newest to oldest.

   - TICKET entries are visited from oldest to newest to accommodate
     reconstructing their aggregate state in the callback.

   Each deck is finalized immediately after the callback returns, so the callback
   must not hold any pointers to the deck or its contents.

   Returns 0 on success or any number of error codes from lower levels,
   including, but not limited to:

   - FSL_RC_OOM on allocation error
   - FSL_RC_NOT_A_REPO if f has no repository opened.
   - FSL_RC_TYPE if the 2nd argument is invalid or if its type is
     not supported (e.g. FSL_SATYPE_CLUSTER).
   - FSL_RC_MISUSE if the 3rd argument is NULL.

*/
FSL_EXPORT int fsl_deck_foreach(fsl_cx * const f, fsl_satype_e type,
                                fsl_deck_visitor_f visitor,
                                void * visitorState);

/**
   Holds options for use with fsl_branch_create().
*/
struct fsl_branch_opt {
  /**
     The checkin RID from which the branch should originate.
  */

   is false and no direct branch name is found then it sets `*zOut` to
   NULL. If doFallback is true then, on success, `*zOut` will always be
   set to some non-NULL value. On error `*zOut` is not modified.

   On error it may return FSL_RC_NOT_A_REPO, FSL_RC_OOM, or any number
   of db-side error codes.
*/
FSL_EXPORT int fsl_branch_of_rid(fsl_cx * const f, fsl_int_t rid,
FSL_EXPORT int fsl_branch_of_rid(fsl_cx * const f, fsl_id_t rid,
                                 bool doFallback, char ** zOut );

/** Convenience typedef and obligatory forward declaration. */
typedef struct fsl_cidiff_state fsl_cidiff_state;

/**
   Callback type for use with fsl_cidiff(). It must return 0 on

/**
   UNTESTED.

   Returns true if f has an opened repository database which is
   opened in read-only mode, else returns false.
*/
FSL_EXPORT char fsl_repo_is_readonly(fsl_cx const * f);
FSL_EXPORT bool fsl_repo_is_readonly(fsl_cx const * f);

/**
   Searches for a matching blob records for a fossil ticket ID. (A
   ticket's ID is the value of its K-card.) The given ticket ID must
   be a full-length ticket ID (40 characters of lower-case hex) or an
   unambiguous prefix.

   If at least one match is found, it returns 0 and updates the 3rd
   argument: `*ridList` is assigned to an array of fsl_id_t
   (`blob.rid` values) terminated by an entry with the value
   0. Ownership of the array is passed to the caller, who must
   eventually pass it to fsl_free(). The entries are ordered from
   oldest to newest (based on their `tagxref.mtime` value).

   On error it may return:

   - FSL_RC_OOM on allocation error.
   - FSL_RC_RANGE if the given ticket ID is longer than FSL_STRLEN_SHA1.
   - FSL_RC_AMBIGUOUS if the ticket ID prefix would match multiple distinct
     ticket IDs. This result is not possible if passed a full-length ticket
     ID.
   - FSL_RC_NOT_FOUND if no match is found.
   - FSL_RC_NOT_A_REPO if f has no repository opened.
   - Any number of db-related errors if something goes horribly wrong
     in the db layer.

   On error, the 3rd argument is not modified.
*/
FSL_EXPORT int fsl_tkt_id_to_rids(fsl_cx * const f, char const * tktId,
                                  fsl_id_t ** ridList);

#if defined(__cplusplus)
} /*extern "C"*/
#endif
#endif
/* ORG_FOSSIL_SCM_FSL_REPO_H_INCLUDED */
/* end of file ./include/fossil-scm/repo.h */

   the checkout-local timestamp of the file.

   Returns non-0 on error. Some of the potential results include:

   - FSL_RC_NOT_A_CKOUT.

   - FSL_RC_NOT_FOUND if the filename cannot be resolved in the
     requested version or cannot be stat()'d.
     requested version or cannot be stat()'d. This can happen if,
     e.g. fc's file has been renamed, but not yet checked in, in the
     current checkout. A _potential_ TODO is to check for a
     (`vfile.origname=fc->name`) record and use `vfile.pathname` for
     the stat() call.

   - FSL_RC_OOM.
*/
FSL_EXPORT int fsl_card_F_ckout_mtime(fsl_cx * const f, fsl_id_t vid,
                                      fsl_card_F const * const fc,
                                      fsl_time_t * repoMtime,
                                      fsl_time_t * localMtime);
                                      fsl_time_t * const repoMtime,
                                      fsl_time_t * const localMtime);

/**
   File change types for use with fsl_merge_state::fileChangeType.

   Terminology used in some of the descriptions:

   - (P) is the "pivot" - the common ancestor for the merge.

     Array sizes of 6 and 10 do not appreciably change the hit rate
     compared to 4, at least not for current (2021-11-18) uses.
  */
  fsl_deck decks[4];
};

/** @internal
/** Convenience typedef. */
  Convenience typedef. */
typedef struct fsl__mcache fsl__mcache;

/** @internal
/** Initialized-with-defaults fsl__mcache structure, intended for
    Initialized-with-defaults fsl__mcache structure, intended for
    const-copy initialization. */
#define fsl__mcache_empty_m { \
  0,0,0,                      \
  {/*aAge*/0,0,0,0},          \
  {fsl_deck_empty_m,fsl_deck_empty_m, \
   fsl_deck_empty_m, fsl_deck_empty_m}\
}

/**@internal
/** Initialized-with-defaults fsl__mcache structure, intended for
    non-const copy initialization. */
  Initialized-with-defaults fsl__mcache structure, intended for
  non-const copy initialization. */
extern const fsl__mcache fsl__mcache_empty;


/* The fsl_cx class is documented in main public header. */
/* The fsl_cx class is documented in main public header. ALL of its
   members are to be considered private/internal. */
struct fsl_cx {
  /**
     A pointer to the "main" db handle. Exactly which db IS the
     main db is, because we have three DBs, not generally knowble.

     The internal management of fsl_cx's db handles has changed
     a couple of times. As of 2022-01-01 the following applies:

   by only supporting them in the way fossil does for platforms which
   do not support symlinks.
*/
int fsl__ckout_symlink_create(fsl_cx * const f, char const *zTgtFile,
                              char const * zLinkFile);


/**
/** @internal
   Compute all file name changes that occur going from check-in iFrom
   to check-in iTo. Requires an opened repository.

   If revOK is true, the algorithm is free to move backwards in the
   chain. This is the opposite of the oneWayOnly parameter for
   fsl_vpath_shortest().

int fsl__find_filename_changes(fsl_cx * const f,
                               fsl_id_t iFrom,
                               fsl_id_t iTo,
                               bool revOK,
                               uint32_t *pnChng,
                               fsl_id_t **aiChng);

/**
/**  @internal
   Bitmask of file change types for use with
   fsl__is_locally_modified().
 */
*/
enum fsl__localmod_e {
/** Sentinel value. */
FSL__LOCALMOD_NONE = 0,
/**
   Permissions changed.
*/
FSL__LOCALMOD_PERM = 0x01,

    Returns 0 on success. On error it initiates (or propagates) a
    rollback for the current transaction. If called when a rollback is
    pending, it unsets the crosslink-is-running flag and returns the
    propagating result code.
*/
int fsl__crosslink_end(fsl_cx * const f, int resultCode);


/** @internal

   Searches the current repository database for a fingerprint and
   returns it as a string in *zOut.

   If rcvid<=0 then the fingerprint matches the last entry in the
   [rcvfrom] table, where "last" means highest-numbered rcvid (as

   fingerprint is not found. Version 0 was very short-lived and is not
   expected to be in many repositories which are accessed via this
   library. Practice has, however, revealed some.

   @see fsl_ckout_fingerprint_check()
*/
int fsl__repo_fingerprint_search(fsl_cx * const f, fsl_id_t rcvid,
                                char ** zOut);
                                 char ** zOut);

/**
/** @internal
   State for running a raw diff.

   @see fsl__diff_all()
*/
struct fsl__diff_cx {
  /**
     aEdit describes the raw diff. Each triple of integers in aEdit[]

  /** File content for the right side of the diff. */
  fsl_dline *aTo;
  /** Number of lines in aTo[]. */
  int nTo /*TODO unsigned*/;
  /** Predicate for comparing LHS/RHS lines for equivalence. */
  int (*cmpLine)(const fsl_dline * const, const fsl_dline *const);
};
/**
/** @internal
   Convenience typeef.
*/
typedef struct fsl__diff_cx fsl__diff_cx;
/** @internal
/** Initialized-with-defaults fsl__diff_cx structure, intended for
    Initialized-with-defaults fsl__diff_cx structure, intended for
    const-copy initialization. */
#define fsl__diff_cx_empty_m {\
  NULL,0,0,NULL,0,NULL,0,fsl_dline_cmp \
}
/** @internal
/** Initialized-with-defaults fsl__diff_cx structure, intended for
    non-const copy initialization. */
   Initialized-with-defaults fsl__diff_cx structure, intended for
   non-const copy initialization. */
extern const fsl__diff_cx fsl__diff_cx_empty;

/** @internal

    Compute the differences between two files already loaded into
    the fsl__diff_cx structure.
   

    Any common text at the beginning and end of the two files is
    removed before starting the divide-and-conquer algorithm.
   
    Returns 0 on succes, FSL_RC_OOM on an allocation error.
*/
int fsl__diff_all(fsl__diff_cx * const p);

/** @internal */
void fsl__diff_optimize(fsl__diff_cx * const p);
void fsl__diff_cx_clean(fsl__diff_cx * const cx);

/** @internal */

void fsl__diff_cx_clean(fsl__diff_cx * const cx);

/** @internal

    Undocumented. For internal debugging only.
    Undocumented. For internal debugging only. The 2nd argument is
    intended to be __FILE__ and the 3rd is intended to be __LINE__.
*/
void fsl__dump_triples(fsl__diff_cx const * const p,
                       char const * zFile, int ln );

/** @internal

    Removes from the BLOB table all artifacts that are in the SHUN
    table. Returns 0 on success. Requires (asserts) that a repo is
    opened. Note that this is not a simple DELETE operation, as it
    requires ensuring that all removed blobs have been undeltified
    first so that no stale delta records are left behind.
*/
int fsl__shunned_remove(fsl_cx * const f);

/** @internal

   This function is, as of this writing, only exposed via a header file
   for the sake of fnc, which still relies on it after we moved the
   "v1" diff code out of this library and into fnc.

   Attempt to shift insertion or deletion blocks so that they begin and
   end on lines that are pure whitespace.  In other words, try to transform
   this:

   ```
        int func1(int x){
           return x*10;
       +}
       +
       +int func2(int x){
       +   return x*20;
        }
  
        int func3(int x){
           return x/5;
        }
   ```

   Into one of these:
  
   ```
        int func1(int x){              int func1(int x){
           return x*10;                   return x*10;
        }                              }
       +
       +int func2(int x){             +int func2(int x){
       +   return x*20;               +   return x*20;
       +}                             +}
                                      +
        int func3(int x){              int func3(int x){
           return x/5;                    return x/5;
        }                              }
   ```
*/
void fsl__diff_optimize(fsl__diff_cx * const p);

/** @internal

   This is a fossil-specific internal detail not needed by the more
   generic parts of the fsl_db API. It loops through all "cached"
   prepared statements for which stmt->role has been assigned a value
   which bitmasks as true against the given role and finalizes

   important to use the correct DB name when creating such constructs.

   Note that the role of FSL_DBROLE_TEMP is invalid here.
*/
char const * fsl_cx_db_name_for_role(fsl_cx const * const f,
                                     fsl_dbrole_e r,
                                     fsl_size_t * len);

/**
   Flags for use with text-diff generation APIs,
   e.g. fsl_diff_text().

   Maintenance reminders:

   - These values are holy and must not be changed without also
     changing the corresponding code in diff.c.

   - Where these entries semantically overlap with their fsl_diff2_flag_e
     counterparts, they MUST have the same values because some internal APIs
     are used by both of the diff APIs.

   @deprecated Prefer fsl_diff2_flag_e and fsl_diff_v2() instead.
*/
enum fsl_diff_flag_e {
/** Ignore end-of-line whitespace */
FSL_DIFF_IGNORE_EOLWS = 0x01,
/** Ignore end-of-line whitespace */
FSL_DIFF_IGNORE_ALLWS = 0x03,
/** Generate a side-by-side diff */
FSL_DIFF_SIDEBYSIDE =   0x04,
/** Missing shown as empty files */
FSL_DIFF_VERBOSE =      0x08,
/** Show filenames only. Not used in this impl! */
FSL_DIFF_BRIEF =        0x10,
/** Render HTML. */
FSL_DIFF_HTML =         0x20,
/** Show line numbers. */
FSL_DIFF_LINENO =       0x40,
/** Suppress optimizations (debug). */
FSL_DIFF_NOOPT =        0x0100,
/** Invert the diff (debug). */
FSL_DIFF_INVERT =       0x0200,
/* ACHTUNG: do not use 0x0400 because of semantic
   collision with FSL_DIFF2_CONTEXT_ZERO */
/** Only display if not "too big." */
FSL_DIFF_NOTTOOBIG =    0x0800,
/** Strip trailing CR */
FSL_DIFF_STRIP_EOLCR =    0x1000,
/**
   This flag tells text-mode diff generation to add ANSI color
   sequences to some output.  The colors are currently hard-coded
   and non-configurable. This has no effect for HTML output, and
   that flag trumps this one. It also currently only affects
   unified diffs, not side-by-side.

   Maintenance reminder: this one currently has no counterpart in
   fossil(1), is not tracked in the same way, and need not map to an
   internal flag value.
*/
FSL_DIFF_ANSI_COLOR =     0x2000
};

/**
   Generates a textual diff from two text inputs and writes
   it to the given output function.

   pA and pB are the buffers to diff.

   contextLines is the number of lines of context to output. This
   parameter has a built-in limit of 2^16, and values larger than
   that get truncated. A value of 0 is legal, in which case no
   surrounding context is provided. A negative value translates to
   some unspecified default value.

   sbsWidth specifies the width (in characters) of the side-by-side
   columns. If sbsWidth is not 0 then this function behaves as if
   diffFlags contains the FSL_DIFF_SIDEBYSIDE flag. If sbsWidth is
   negative, OR if diffFlags explicitly contains
   FSL_DIFF_SIDEBYSIDE and sbsWidth is 0, then some default width
   is used. This parameter has a built-in limit of 255, and values
   larger than that get truncated to 255.

   diffFlags is a mask of fsl_diff_flag_t values. Not all of the
   fsl_diff_flag_t flags are yet [sup]ported.

   The output is sent to out(outState,...). If out() returns non-0
   during processing, processing stops and that result is returned
   to the caller of this function.

   Returns 0 on success, FSL_RC_OOM on allocation error,
   FSL_RC_MISUSE if any arguments are invalid, FSL_RC_TYPE if any
   of the content appears to be binary (contains embedded NUL
   bytes), FSL_RC_RANGE if some range is exceeded (e.g. the maximum
   number of input lines).

   None of (pA, pB, out) may be NULL.

   TODOs:

   - Add a predicate function for outputing only matching
   differences, analog to fossil(1)'s regex support (but more
   flexible).

   - Expose the raw diff-generation bits via the internal API
   to facilitate/enable the creation of custom diff formats.

   @see fsl_diff_v2()
   @deprecated Prefer fsl_diff_v2() for new code.
*/
int fsl_diff_text(fsl_buffer const *pA, fsl_buffer const *pB,
                  fsl_output_f out, void * outState,
                  short contextLines, short sbsWidth,
                  int diffFlags );

/**
   Functionally equivalent to:

   ```
   fsl_diff_text(pA, pB, fsl_output_f_buffer, pOut,
   contextLines, sbsWidth, diffFlags);
   ```

   Except that it returns FSL_RC_MISUSE if !pOut.

   @see fsl_diff_v2()
   @deprecated Prefer fsl_diff_v2() for new code.
*/
int fsl_diff_text_to_buffer(fsl_buffer const *pA, fsl_buffer const *pB,
                            fsl_buffer *pOut, short contextLines,
                            short sbsWidth, int diffFlags );


/**
   Equivalent to `fcli_setup_v2(argc,argv,fcli.cliFlags,fcli.appHelp)`.

   @see fcli_pre_setup()
   @see fcli_setup_v2()
   @see fcli_end_of_main()
   @deprecated Its signature will change to fcli_setup_v2()'s at some point.
*/
int fcli_setup(int argc, char const * const * argv );

/** @internal

   Performs the same job as fsl_diff_text() but produces the results
   in the low-level form of an array of "copy/delete/insert triples."
   This is primarily intended for internal use in other
   library-internal algorithms, not for client code. Note all
   FSL_DIFF_xxx flags apply to this form.

   Returns 0 on success, any number of non-0 codes on error. On
   success *outRaw will contain the resulting array, which must
   eventually be fsl_free()'d by the caller. On error *outRaw is not
   modified.

   @deprecated Use fsl_diff_v2_raw() instead.
*/
int fsl__diff_text_raw(fsl_buffer const *p1, fsl_buffer const *p2,
                       int diffFlags, int ** outRaw);


/** @deprecated fsl_close_scm_dbs()

   As of 2021-01-01, this functions identically to
   fsl_close_scm_dbs(). Prior to that...

   If fsl_repo_open_xxx() has been used to open a respository db,

untrusted comment: fnc 0.7 public key
RWS7z+k9eoeF8OQp7R9VyUfKlxOODpUYCBM2v/YEbk8YXiSK1FzkIVJD

untrusted comment: fnc 0.9 public key
RWR/Unt0CGtNwq8vE59836HrU7Jt8ETbuxx2mnap+FakP2TCZLEcaS4j