/* Searching in the HTML document *//* $Id: search.c,v 1.305.2.5 2005/04/06 09:11:19 jonas Exp $ */#ifndef _GNU_SOURCE#define _GNU_SOURCE /* XXX: we _WANT_ strcasestr() ! */#endif#ifdef HAVE_CONFIG_H#include "config.h"#endif#include <ctype.h> /* tolower(), isprint() */#include <sys/types.h> /* FreeBSD needs this before regex.h */#ifdef HAVE_REGEX_H#include <regex.h>#endif#include <stdlib.h>#include <string.h>#include "elinks.h"#include "bfu/dialog.h"#include "config/kbdbind.h"#include "document/document.h"#include "document/view.h"#include "intl/gettext/libintl.h"#include "sched/event.h"#include "sched/session.h"#include "terminal/screen.h"#include "terminal/terminal.h"#include "util/color.h"#include "util/error.h"#include "util/memory.h"#include "util/string.h"#include "viewer/text/draw.h"#include "viewer/text/link.h"#include "viewer/text/search.h"#include "viewer/text/view.h"#include "viewer/text/vs.h"#define SEARCH_HISTORY_FILENAME		"searchhist"static INIT_INPUT_HISTORY(search_history);static inline voidadd_srch_chr(struct document *document, unsigned char c, int x, int y, int nn){	assert(document);	if_assert_failed return;	if (c == ' ' && !document->nsearch) return;	if (document->search) {		int n = document->nsearch;		if (c == ' ' && document->search[n - 1].c == ' ')			return;		document->search[n].c = c;		document->search[n].x = x;		document->search[n].y = y;		document->search[n].n = nn;	}	document->nsearch++;}static voidsort_srch(struct document *document){	int i;	int *min, *max;	assert(document);	if_assert_failed return;	document->slines1 = mem_calloc(document->height, sizeof(*document->slines1));	if (!document->slines1) return;	document->slines2 = mem_calloc(document->height, sizeof(*document->slines2));	if (!document->slines2) {		mem_free(document->slines1);		return;	}	min = mem_calloc(document->height, sizeof(*min));	if (!min) {		mem_free(document->slines1);		mem_free(document->slines2);		return;	}	max = mem_calloc(document->height, sizeof(*max));	if (!max) {		mem_free(document->slines1);		mem_free(document->slines2);		mem_free(min);		return;	}	for (i = 0; i < document->height; i++) {		min[i] = INT_MAX;		max[i] = 0;	}	for (i = 0; i < document->nsearch; i++) {		struct search *s = &document->search[i];		int sxn = s->x + s->n;		if (s->x < min[s->y]) {			min[s->y] = s->x;		   	document->slines1[s->y] = s;		}		if (sxn > max[s->y]) {			max[s->y] = sxn;			document->slines2[s->y] = s;		}	}	mem_free(min);	mem_free(max);}static intget_srch(struct document *document){	struct node *node;	assert(document && document->nsearch == 0);	if_assert_failed return 0;	foreachback (node, document->nodes) {		int x, y;		int height = int_min(node->box.y + node->box.height, document->height);		for (y = node->box.y; y < height; y++) {			int width = int_min(node->box.x + node->box.width,					    document->data[y].length);			for (x = node->box.x;			     x < width && document->data[y].chars[x].data <= ' ';			     x++);			for (; x < width; x++) {				unsigned char c = document->data[y].chars[x].data;				int count = 0;				int xx;				if (document->data[y].chars[x].attr & SCREEN_ATTR_UNSEARCHABLE)					continue;				if (c > ' ') {					add_srch_chr(document, c, x, y, 1);					continue;				}				for (xx = x + 1; xx < width; xx++) {					if (document->data[y].chars[xx].data < ' ')						continue;					count = xx - x;					break;				}				add_srch_chr(document, ' ', x, y, count);				x = xx - 1;			}			add_srch_chr(document, ' ', x, y, 0);		}	}	return document->nsearch;}static voidget_search_data(struct document *document){	int n;	assert(document);	if_assert_failed return;	if (document->search) return;	n = get_srch(document);	if (!n) return;	document->nsearch = 0;	document->search = mem_alloc(n * sizeof(*document->search));	if (!document->search) return;	get_srch(document);	while (document->nsearch	       && document->search[--document->nsearch].c == ' ');	sort_srch(document);}/* Returns -1 on assertion failure, 1 if s1 and s2 are not found, * and 0 if they are found. */static intget_range(struct document *document, int y, int height, int l,	  struct search **s1, struct search **s2){	int i;	assert(document && s1 && s2);	if_assert_failed return -1;	*s1 = *s2 = NULL;	int_lower_bound(&y, 0);	for (i = y; i < y + height && i < document->height; i++) {		if (document->slines1[i] && (!*s1 || document->slines1[i] < *s1))			*s1 = document->slines1[i];		if (document->slines2[i] && (!*s2 || document->slines2[i] > *s2))			*s2 = document->slines2[i];	}	if (!*s1 || !*s2) return 1;	*s1 -= l;	if (*s1 < document->search)		*s1 = document->search;	if (*s2 > document->search + document->nsearch - l + 1)		*s2 = document->search + document->nsearch - l + 1;	if (*s1 > *s2)		*s1 = *s2 = NULL;	if (!*s1 || !*s2)		return 1;	return 0;}/* Returns a string |doc| that is a copy of the text in the search nodes * from |s1| to |s1 + doclen - 1| with the space at the end of each line * converted to a new-line character (LF). */static unsigned char *get_search_region_from_search_nodes(struct search *s1, int doclen){	unsigned char *doc;	int i;	doc = mem_alloc(sizeof(unsigned char ) * (doclen + 1));	if (!doc) return NULL;	for (i = 0; i < doclen; i++) {		if (i > 0 && s1[i - 1].c == ' ' && s1[i - 1].y != s1[i].y) {			doc[i - 1] = '\n';		}		doc[i] = s1[i].c;	}	doc[doclen] = 0;	return doc;}#ifdef HAVE_REGEX_Hstatic intis_in_range_regex(struct document *document, int y, int height,		  unsigned char *text, int textlen,		  int *min, int *max,		  struct search *s1, struct search *s2){	int yy = y + height;	unsigned char *doc;	unsigned char *doctmp;	int doclen;	int found = 0;	int regex_flags = REG_NEWLINE;	int regexec_flags = 0;	int i;	int reg_err;	regex_t regex;	regmatch_t regmatch;	int pos = 0;	struct search *search_start = s1;	unsigned char save_c;	if (get_opt_int("document.browse.search.regex") == 2)		regex_flags |= REG_EXTENDED;	if (!get_opt_bool("document.browse.search.case"))		regex_flags |= REG_ICASE;	reg_err = regcomp(&regex, text, regex_flags);	if (reg_err) {		regfree(&regex);		return -2;	}	doclen = s2 - s1 + textlen;	if (!doclen) {		regfree(&regex);		return 0;	}	doc = get_search_region_from_search_nodes(s1, doclen);	if (!doc) {		regfree(&regex);		return -1;	}	doctmp = doc;find_next:	while (pos < doclen && (search_start[pos].y < y - 1				|| search_start[pos].y > yy)) pos++;	doctmp = &doc[pos];	s1 = &search_start[pos];	while (pos < doclen && search_start[pos].y >= y - 1			    && search_start[pos].y <= yy) pos++;	save_c = doc[pos];	doc[pos] = 0;	while (*doctmp && !regexec(&regex, doctmp, 1, &regmatch, regexec_flags)) {		regexec_flags = REG_NOTBOL;		textlen = regmatch.rm_eo - regmatch.rm_so;		if (!textlen) { doc[pos] = save_c; found = 1; goto free_stuff; }		s1 += regmatch.rm_so;		doctmp += regmatch.rm_so;		if (s1[textlen].y < y || s1[textlen].y >= yy)			goto next;		found = 1;		for (i = 0; i < textlen; i++) {			if (!s1[i].n) continue;			int_upper_bound(min, s1[i].x);			int_lower_bound(max, s1[i].x + s1[i].n);		}next:		doctmp += int_max(textlen, 1);		s1 += int_max(textlen, 1);	}	doc[pos] = save_c;	if (pos < doclen)		goto find_next;free_stuff:	regfree(&regex);	mem_free(doc);	return found;}#endif /* HAVE_REGEX_H *//* Returns an allocated string which is a lowered copy of passed one. */static unsigned char *lowered_string(unsigned char *text, int textlen){	unsigned char *ret;	if (textlen < 0) textlen = strlen(text);	ret = mem_calloc(1, textlen + 1);	if (ret && textlen) {		do {			ret[textlen] = tolower(text[textlen]);		} while (textlen--);	}	return ret;}static intis_in_range_plain(struct document *document, int y, int height,		  unsigned char *text, int textlen,		  int *min, int *max,		  struct search *s1, struct search *s2){	int yy = y + height;	unsigned char *txt;	int found = 0;	int case_sensitive = get_opt_bool("document.browse.search.case");	txt = case_sensitive ? stracpy(text) : lowered_string(text, textlen);	if (!txt) return -1;	/* TODO: This is a great candidate for nice optimizations. Fresh CS	 * graduates can use their knowledge of ie. KMP (should be quite	 * trivial, probably a starter; very fast as well) or Turbo-BM (or	 * maybe some other Boyer-Moore variant, I don't feel that strong in	 * this area), hmm?  >:) --pasky */#define maybe_tolower(c) (case_sensitive ? (c) : tolower(c))	for (; s1 <= s2; s1++) {		int i;		if (maybe_tolower(s1->c) != txt[0]) {srch_failed:			continue;		}		for (i = 1; i < textlen; i++)			if (maybe_tolower(s1[i].c) != txt[i])				goto srch_failed;		if (s1[i].y < y || s1[i].y >= yy)			continue;		found = 1;		for (i = 0; i < textlen; i++) {			if (!s1[i].n) continue;			int_upper_bound(min, s1[i].x);			int_lower_bound(max, s1[i].x + s1[i].n);		}	}#undef maybe_tolower	mem_free(txt);	return found;}static intis_in_range(struct document *document, int y, int height,	    unsigned char *text, int *min, int *max){	struct search *s1, *s2;	int textlen;	assert(document && text && min && max);	if_assert_failed return -1;	*min = INT_MAX, *max = 0;	textlen = strlen(text);	if (get_range(document, y, height, textlen, &s1, &s2))		return 0;#ifdef HAVE_REGEX_H	if (get_opt_int("document.browse.search.regex"))		return is_in_range_regex(document, y, height, text, textlen,					 min, max, s1, s2);#endif	return is_in_range_plain(document, y, height, text, textlen,				 min, max, s1, s2);}#define realloc_points(pts, size) \	mem_align_alloc(pts, size, (size) + 1, struct point, 0xFF)static voidget_searched_plain(struct document_view *doc_view, struct point **pt, int *pl,		   int l, struct search *s1, struct search *s2){	unsigned char *txt;	struct point *points = NULL;	struct box *box;	int xoffset, yoffset;	int len = 0;	int case_sensitive = get_opt_bool("document.browse.search.case");	txt = case_sensitive ? stracpy(*doc_view->search_word)			     : lowered_string(*doc_view->search_word, l);	if (!txt) return;	box = &doc_view->box;	xoffset = box->x - doc_view->vs->x;	yoffset = box->y - doc_view->vs->y;#define maybe_tolower(c) (case_sensitive ? (c) : tolower(c))	for (; s1 <= s2; s1++) {		int i;		if (maybe_tolower(s1[0].c) != txt[0]) {srch_failed:			continue;		}		for (i = 1; i < l; i++)			if (maybe_tolower(s1[i].c) != txt[i])				goto srch_failed;		for (i = 0; i < l; i++) {			int j;			int y = s1[i].y + yoffset;			if (!row_is_in_box(box, y))				continue;			for (j = 0; j < s1[i].n; j++) {				int sx = s1[i].x + j;				int x = sx + xoffset;				if (!col_is_in_box(box, x))					continue;				if (!realloc_points(&points, len))					continue;				points[len].x = sx;				points[len++].y = s1[i].y;			}		}	}#undef maybe_tolower	mem_free(txt);	*pt = points;	*pl = len;}#ifdef HAVE_REGEX_Hstatic voidget_searched_regex(struct document_view *doc_view, struct point **pt, int *pl,		   int l, struct search *s1, struct search *s2){	unsigned char *doc;	unsigned char *doctmp;	int doclen;	struct point *points = NULL;	int xoffset, yoffset;	int len = 0;	int regex_flags = REG_NEWLINE;	int regexec_flags = 0;	int reg_err;	int i;	regex_t regex;	regmatch_t regmatch;	int pos = 0;	struct search *search_start = s1;	unsigned char save_c;	struct box *box;	int y1, y2;	if (get_opt_int("document.browse.search.regex") == 2)