/* Part of publib.

   Copyright (c) 2012 Antti-Juhani Kaijanaho.
   Copyright (c) 1994-2006 Lars Wirzenius.  All rights reserved.

   Redistribution and use in source and binary forms, with or without
   modification, are permitted provided that the following conditions
   are met:

   1. Redistributions of source code must retain the above copyright
      notice, this list of conditions and the following disclaimer.

   2. Redistributions in binary form must reproduce the above
      copyright notice, this list of conditions and the following
      disclaimer in the documentation and/or other materials provided
      with the distribution.

   THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS
   OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
   WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
   ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY
   DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
   DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE
   GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
   INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
   WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
   NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
   SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
*/
/*
 * sbuf_aux.c -- auxiliary routines for text editors
 *
 * Part of Publib.  See manpage for more information.
 * "@(#)publib-sbuf:$Id: sbuf_aux.c,v 1.14 1996/12/18 15:52:26 liw Exp $"
 */


#include <assert.h>
#include <ctype.h>
#include <limits.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "publib/sbuf.h"
#include "publib/errormsg.h"


/*
 * This macro is used by sbuf_bow and sbuf_eow to determine if a
 * character is a `letter', i.e., if it can belong to a word.
 */
#define letter(c) ((c) == '_' || isalnum(c))



/*
 * Local function prototypes.
 */
static void put_into_cache(Sbuf *, long, long);
static int find_nearest(Sbuf *, long);
static long compute_lineno(Sbuf *, long, long, long);
static long find_pair(const unsigned char *, long, long);

#ifdef NDEBUG
#define check_pos_cache(x) ((void) 0)
#else
static void check_pos_cache(Sbuf *);
#endif



/*
 * Return position before first character on line containing pos.
 */
long sbuf_boln(Sbuf *buf, long pos) {
	while (pos > 0 && sbuf_charat(buf, pos-1) != '\n')
		--pos;
	return pos;
}


/*
 * Return position after last character (including newline) on line
 * containing pos.
 */
long sbuf_eoln(Sbuf *buf, long pos) {
        int c;

        while ((c = sbuf_charat(buf, pos)) != '\n' && c != EOF)
                ++pos; 
        if (c == EOF)
                return pos;
        return pos+1;
}


/*
 * Return position before first character of the word that contains
 * pos.  If pos is not within a word, return pos.
 */
long sbuf_bow(Sbuf *buf, long pos) {
        int c;

	c = sbuf_charat(buf, pos);
        if (!letter(c))
                return pos;
        while (pos > 0 && (c = sbuf_charat(buf, pos-1), letter(c)))
                --pos;
        return pos;
}



/*
 * Return position after last character of the word that contains
 * pos.  If pos is not within a word, return pos+1 (or pos, if at
 * EOF).
 */
long sbuf_eow(Sbuf *buf, long pos) {
        int c;

	c = sbuf_charat(buf, pos);
        if (!letter(c)) {
                if (c != EOF)
                        ++pos;
                return pos;
        }
        while (letter(c)) {
                ++pos;
		c = sbuf_charat(buf, pos);
	}
        return pos;
}


/*
 * Return line number of character after position pos.  The first line is line 0.
 */
long sbuf_lineno(Sbuf *buf, long pos) {
	int i;
	long lineno;
	struct __sbuf_pos_cache *cache;

	check_pos_cache(buf);

	cache = buf->pc.data;

	i = find_nearest(buf, pos);
	if (i == -1)
		lineno = compute_lineno(buf, pos, 0, 0);
	else
		lineno = compute_lineno(buf, pos, 
				cache[i].pos, cache[i].lineno);

	if (i == -1 || cache[i].pos != pos)
		put_into_cache(buf, pos, lineno);

	check_pos_cache(buf);
	return lineno;
}



/*
 * Return position before first character of line number lineno 
 * (first line is 0).  FIXME: this should use the poscache to
 * find the closest position.
 */
long sbuf_linepos(Sbuf *buf, long lineno) {
	long gaplen;
	char *p, *q;
	
	p = buf->block;
	q = buf->block + buf->gappos;
	while (p < q && lineno > 0) {
		if (*p == '\n')
			--lineno;
		++p;
	}
	
	if (lineno == 0)
		return p - buf->block;

	gaplen = buf->alloc - buf->len;
	p = buf->block + buf->gappos + gaplen;
	q = buf->block + buf->len + gaplen;
	while (p < q && lineno > 0) {
		if (*p == '\n')
			--lineno;
		++p;
	}

	return p - buf->block - gaplen;
}



/*
 * Function:	sbuf_colno
 * Purpose:	Return column number of a text position.
 * Arguments:	buf	the buffer
 *		pos	the position
 *		tab	tab distance
 * Return:	The column number.
 * Note:	The first column is number 0.
 */
long sbuf_colno(Sbuf *buf, long pos, long tab) {
	long p, col;

	p = sbuf_boln(buf, pos);
	col = 0;
	while (p < pos) {
		if (sbuf_charat(buf, p) == '\t')
			col += tab - (col % tab);
		else
			++col;
		++p;
	}
	return col;
}



/*
 * Function:	sbuf_colpos
 * Purpose:	Return the position of the character in a given column.
 * Arguments:	buf	the buffer
 *		pos	the beginning of the line
 *		col	the column
 *		tab	tab distance
 * Return:	The text position of the character that occupies the given
 *		column.
 * Note:	A tab occupies several character positions.  If the line
 *		is too short, the position of the newline or EOF that
 *		ends the line is returned.
 */
long sbuf_colpos(Sbuf *buf, long pos, long col, long tab) {
	long i;

	i = 0;
	while (i < col) {
		switch (sbuf_charat(buf, pos)) {
		case '\n':
		case EOF:
			return pos;
		case '\t':
			i += tab - (i % tab);
			if (i > col)
				return pos;
			break;
		default:
			++i;
			break;
		}
		++pos;
	}
	return pos;

}


/*
 * Function:	sbuf_clear_pos_cache
 * Purpose:	Clear the poscache starting at position pos.
 */
void sbuf_clear_pos_cache(Sbuf *buf, long pos) {
	struct __sbuf_pos_cache *cache;
	
	check_pos_cache(buf);
	cache = buf->pc.data;
	while (buf->pc.used > 0 && cache[buf->pc.used-1].pos >= pos)
		--buf->pc.used;
	check_pos_cache(buf);
}



/*
 * Function:	sbuf_adjust_pos_cache
 * Purpose:	Adjust the poscache.
 * Description:	The buffer has been modified by replacing pos..pos+oldlen-1
 *		with new text that is newlen chars long.  The range now
 *		has n more (n > 0) or fewer (n < 0) newlines.  The cache
 *		is adjusted so that each (p,lineno) pair is deleted or
 *		updated as necessary to bring it up to date to the current
 *		situation: pairs in the old range are deleted and those after
 *		it are moved and the line number adjusted.
 */
void sbuf_adjust_pos_cache(Sbuf *buf, long pos, long oldlen, long newlen,
long n) {
	int i, j;
	struct __sbuf_pos_cache *cache;

	check_pos_cache(buf);
	
	cache = buf->pc.data;

	/* fixme: bsearch should be used */
	for (i = 0; i < buf->pc.used && cache[i].pos < pos; ++i)
		continue;

	j = i;
	for (; i < buf->pc.used && cache[i].pos < pos + oldlen; ++i)
		continue;

	memmove(cache + j, cache + i, (buf->pc.used - i) * sizeof(cache[0]));
	buf->pc.used -= i - j;

	for (; j < buf->pc.used; ++j) {
		cache[j].pos += newlen - oldlen;
		cache[j].lineno += n;
	}

	check_pos_cache(buf);
}



/*
 * Function:	sbuf_find_pair
 * Purpose:	Find pair to character at a given position.
 */
long sbuf_find_pair(Sbuf *buf, long pos) {
	unsigned char *str;

	str = (unsigned char *) sbuf_lock(buf);
	if (str == NULL)
		return -1;
	pos = find_pair(str, sbuf_length(buf), pos);
	sbuf_unlock(buf);
	return pos;
}



/*
 * Write position cache statistics to file.
 */
void sbuf_cache_stats(Sbuf *buf, FILE *f) {
	fprintf(f, "Sbuf position cache statistics (%p):\n", (void *) buf);
	fprintf(f, "   hits:     %6ld\n", buf->poshits);
	fprintf(f, "   misses:   %6ld\n", buf->posmisses);
	fprintf(f, "   avg miss: %8.1f\n", buf->posmissavg);
}


/*
 * Is a position inside a mark?
 */
int sbuf_pos_inside_mark(Sbufmark *mark, long pos) {
	long begin, end, tabsize, poscol;
	
	begin = sbuf_mark_begin(mark);
	if (pos < begin)
		return 0;
	end = sbuf_mark_end(mark);
	if (pos >= end)
		return 0;
	if (!sbuf_mark_is_columnar(mark))
		return 1;

	tabsize = 8;	
	poscol = sbuf_colno(mark->buf, pos, tabsize);
	if (poscol < sbuf_colno(mark->buf, begin, tabsize))
		return 0;
	return poscol < sbuf_colno(mark->buf, end, tabsize);
}



/**************************************************************************
 * Local functions follow.
 */


static int find_nearest(Sbuf *buf, long pos) {
	struct __sbuf_pos_cache *cache;
	int i;

	check_pos_cache(buf);

	cache = buf->pc.data;
	
	if (buf->pc.used == 0)
		return -1;
	if (buf->pc.used == 1 || pos <= cache[0].pos)
		return 0;
	if (pos >= cache[buf->pc.used-1].pos)
		return buf->pc.used-1;

	for (i = 0; pos > cache[i+1].pos; ++i)
		continue;

	check_pos_cache(buf);

	if (i == buf->pc.used-1)
		return i;
	else if (pos - cache[i].pos < cache[i+1].pos - pos)
		return i;
	else
		return i+1;
}


static long compute_lineno(Sbuf *buf, long pos, long known_pos, long lineno) {
	long orig_pos;

	orig_pos = known_pos;

	while (known_pos < pos) {
		if (sbuf_charat(buf, known_pos) == '\n')
			++lineno;
		++known_pos;
	}

	while (known_pos > pos) {
		--known_pos;
		if (sbuf_charat(buf, known_pos) == '\n')
			--lineno;
	}
	
	if (known_pos == orig_pos)
		++buf->poshits;
	else {
		buf->posmissavg = 
		    (buf->posmisses * buf->posmissavg + 
		        labs(known_pos - orig_pos)) / (buf->posmisses + 1);
		++buf->posmisses;
	}

	return lineno;
}



static void put_into_cache(Sbuf *buf, long pos, long lineno) {
	struct __sbuf_pos_cache *cache;
	long dist, mindist;
	int i, min;
	
	check_pos_cache(buf);
	
	if (buf->pc.used < SBUF_POS_CACHE_MAX && buf->pc.used == buf->pc.alloc)
		(void) dynarr_resize(&buf->pc, buf->pc.used + 1);
	
	cache = buf->pc.data;

	assert(buf->pc.alloc >= SBUF_POS_CACHE_MIN);
	if (buf->pc.used >= buf->pc.alloc - 1) {
		min = 2;
		mindist = cache[min].pos - cache[min-2].pos;
		for (i = 3; i < buf->pc.used; ++i) {
			dist = cache[i].pos - cache[i-2].pos;
			if (dist < mindist) {
				min = i;
				mindist = dist;
			}
		}
		for (i = min; i < buf->pc.used; ++i)
			cache[i-1] = cache[i];
		--buf->pc.used;
	}

	for (i = buf->pc.used; i > 0; --i) {
		if (pos > cache[i-1].pos)
			break;
		cache[i] = cache[i-1];
	}
	cache[i].pos = pos;
	cache[i].lineno = lineno;
	++buf->pc.used;

	check_pos_cache(buf);
}



/*
 * Function:	find_pair
 * Purpose:	Given a buffer, find the pair of a character
 * Arguments:	str	the string of the buffer
 *		len	length of buffer
 *		pos	the position of the character
 * Return:	-1 for no pair found, or position in buffer of pair.
 */
static long find_pair(const unsigned char *str, long len, long pos) {
	static unsigned char pairstr[] = "(){}[]";
	static int pair[UCHAR_MAX + 1];
	static int dir[UCHAR_MAX + 1];
	static int init = 0;
	int c;

	if (pos < 0 || pos >= len)
		return -1;

	if (!init) {
		for (c = 0; c < UCHAR_MAX + 1; ++c) {
			pair[c] = EOF;
			dir[c] = 0;
		}

		assert(strlen((char*)pairstr) % 2 == 0);
		for (c = 0; pairstr[c] != '\0'; c += 2) {
			pair[pairstr[c]] = pairstr[c+1];
			pair[pairstr[c+1]] =pairstr[c];
			dir[pairstr[c]] = 1;
			dir[pairstr[c+1]] = -1;
		}

		init = 1;
	}

	c = str[pos];
	if (pair[c] == EOF)
		return -1;

	for (;;) {
		assert(dir[c] != 0);
		do {
			pos += dir[c];
			if (pos < 0 || pos >= len)
				return -1;
		} while (pair[str[pos]] == EOF);
	
		if (pair[str[pos]] == c)
			return pos;
		if (dir[str[pos]] != dir[c])
			return -1;
		pos = find_pair(str, len, pos);
		if (pos < 0 || pos >= len)
			return -1;
	}
}



/*
 * Function:	check_pos_cache
 * Purpose:	Check that the pos cache is OK.
 */
#ifndef NDEBUG
static void check_pos_cache(Sbuf *buf) {
	int i;
	struct __sbuf_pos_cache *cache;

	assert(buf->pc.alloc >= SBUF_POS_CACHE_MIN);
	assert(buf->pc.alloc <= SBUF_POS_CACHE_MAX);
	
	if (buf->pc.used == 0)
		return;
	
	cache = buf->pc.data;
	assert(buf->pc.used > 0);
	assert(cache[0].pos >= 0);
	assert(cache[0].lineno >= 0);
	for (i = 1; i < buf->pc.used; ++i) {
		assert(cache[i].pos >= 0);
		assert(cache[i].lineno >= 0);
		assert(cache[i].pos > cache[i-1].pos);
		assert(cache[i].lineno >= cache[i-1].lineno);
	}
}
#endif