search.c

elinks下lynx是最重要的二个文本浏览器, 在linux下非常实用, elinks也是gentoo安装过程中默认使用的浏览器, 这是elinks源代码

/* Searching in the HTML document */

#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 "main/event.h"
#include "main/module.h"
#include "session/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/action.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);
}

/* Assign s1 and s2 the first search node and the last search node needed to
 * form the region starting at line y and ending at the greater of y + height
 * and the end of the document, with allowance at the start to allow for
 * multi-line matches that would otherwise be partially outside of the region.
 *
 * 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);

	/* Starting with line y, find the search node referencing the earliest
	 * point in the document text and the node referencing the last point,
	 * respectively s1 and s2.
	 */
	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;

	/* Skip back by l to facilitate multi-line matches where the match
	 * begins before the start of the search region but is still partly
	 * within. */
	*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, struct search *s2,
				    int pattern_len, int *doclen)
{
	unsigned char *doc;
	int i;

	*doclen = s2 - s1 + pattern_len;
	if (!*doclen) return NULL;

	doc = mem_alloc(*doclen + 1);
	if (!doc) {
		*doclen = -1;
		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
struct regex_match_context {
	struct search *s1;
	struct search *s2;
	int textlen;
	int y1;
	int y2;
	int found;
	unsigned char *pattern;
};

static int
init_regex(regex_t *regex, unsigned char *pattern)
{
	int regex_flags = REG_NEWLINE;
	int reg_err;

	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, pattern, regex_flags);
	if (reg_err) {
		regfree(regex);
		return 0;
	}

	return 1;
}

static void
search_for_pattern(struct regex_match_context *common_ctx, void *data,
		   void (*match)(struct regex_match_context *, void *))
{
	unsigned char *doc;
	unsigned char *doctmp;
	int doclen;
	int regexec_flags = 0;
	regex_t regex;
	regmatch_t regmatch;
	int pos = 0;
	struct search *search_start = common_ctx->s1;
	unsigned char save_c;

	/* TODO: show error message */
	/* XXX: This will probably require that reg_err be passed thru
	 * common_ctx to the caller. */
	if (!init_regex(&regex, common_ctx->pattern)) {
#if 0
		/* Where and how should we display the error dialog ? */
		unsigned char regerror_string[MAX_STR_LEN];

		regerror(reg_err, &regex, regerror_string, sizeof(regerror_string));
#endif
		common_ctx->found = -2;
		return;
	}

	doc = get_search_region_from_search_nodes(common_ctx->s1, common_ctx->s2, common_ctx->textlen, &doclen);
	if (!doc) {
		regfree(&regex);
		common_ctx->found = doclen;
		return;
	}

	doctmp = doc;

find_next:
	while (pos < doclen) {
		int y = search_start[pos].y;

		if (y >= common_ctx->y1 && y <= common_ctx->y2) break;
		pos++;
	}
	doctmp = &doc[pos];
	common_ctx->s1 = &search_start[pos];

	while (pos < doclen) {
		int y = search_start[pos].y;

		if (y < common_ctx->y1 || y > common_ctx->y2) break;
		pos++;
	}
	save_c = doc[pos];
	doc[pos] = 0;

	while (*doctmp && !regexec(&regex, doctmp, 1, &regmatch, regexec_flags)) {
		regexec_flags = REG_NOTBOL;
		common_ctx->textlen = regmatch.rm_eo - regmatch.rm_so;
		if (!common_ctx->textlen) { doc[pos] = save_c; common_ctx->found = 1; goto free_stuff; }
		common_ctx->s1 += regmatch.rm_so;
		doctmp += regmatch.rm_so;

		match(common_ctx, data);

		doctmp += int_max(common_ctx->textlen, 1);
		common_ctx->s1 += int_max(common_ctx->textlen, 1);
	}

	doc[pos] = save_c;
	if (pos < doclen)
		goto find_next;

free_stuff:
	regfree(&regex);
	mem_free(doc);
}

struct is_in_range_regex_context {
	int y;
	int *min;
	int *max;
};

static void
is_in_range_regex_match(struct regex_match_context *common_ctx, void *data)
{
	struct is_in_range_regex_context *ctx = data;
	int i;

	if (common_ctx->s1[common_ctx->textlen].y < ctx->y || common_ctx->s1[common_ctx->textlen].y >= common_ctx->y2)
		return;

	common_ctx->found = 1;

	for (i = 0; i < common_ctx->textlen; i++) {
		if (!common_ctx->s1[i].n) continue;

		int_upper_bound(ctx->min, common_ctx->s1[i].x);
		int_lower_bound(ctx->max, common_ctx->s1[i].x + common_ctx->s1[i].n);
	}
}

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)
{
	struct regex_match_context common_ctx;
	struct is_in_range_regex_context ctx;

	ctx.y = y;
	ctx.min = min;
	ctx.max = max;

	common_ctx.found = 0;
	common_ctx.textlen = textlen;
	common_ctx.y1 = y - 1;
	common_ctx.y2 = y + height;
	common_ctx.pattern = text;
	common_ctx.s1 = s1;
	common_ctx.s2 = s2;

	search_for_pattern(&common_ctx, &ctx, is_in_range_regex_match);

	return common_ctx.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");