search.c

一个很有名的浏览器

/* 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 void
add_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 void
sort_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 int
get_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 void
get_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 int
get_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_H
static int
is_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 int
is_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 int
is_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 void
get_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_H
static void
get_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)