summaryrefslogtreecommitdiff
path: root/macros/texinfo/texinfo/info/search.c
diff options
context:
space:
mode:
authorNorbert Preining <norbert@preining.info>2019-09-02 13:46:59 +0900
committerNorbert Preining <norbert@preining.info>2019-09-02 13:46:59 +0900
commite0c6872cf40896c7be36b11dcc744620f10adf1d (patch)
tree60335e10d2f4354b0674ec22d7b53f0f8abee672 /macros/texinfo/texinfo/info/search.c
Initial commit
Diffstat (limited to 'macros/texinfo/texinfo/info/search.c')
-rw-r--r--macros/texinfo/texinfo/info/search.c746
1 files changed, 746 insertions, 0 deletions
diff --git a/macros/texinfo/texinfo/info/search.c b/macros/texinfo/texinfo/info/search.c
new file mode 100644
index 0000000000..9f1d5e26f7
--- /dev/null
+++ b/macros/texinfo/texinfo/info/search.c
@@ -0,0 +1,746 @@
+/* search.c -- searching large bodies of text.
+
+ Copyright 1993-2019 Free Software Foundation, Inc.
+
+ This program is free software: you can redistribute it and/or modify
+ it under the terms of the GNU General Public License as published by
+ the Free Software Foundation, either version 3 of the License, or
+ (at your option) any later version.
+
+ This program is distributed in the hope that it will be useful,
+ but WITHOUT ANY WARRANTY; without even the implied warranty of
+ MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ GNU General Public License for more details.
+
+ You should have received a copy of the GNU General Public License
+ along with this program. If not, see <http://www.gnu.org/licenses/>.
+
+ Originally written by Brian Fox. */
+
+#include "info.h"
+#include <regex.h>
+
+#include "session.h"
+#include "info-utils.h"
+#include "search.h"
+
+
+/* **************************************************************** */
+/* */
+/* The Actual Searching Functions */
+/* */
+/* **************************************************************** */
+
+/* Search forwards or backwards for the text delimited by BINDING.
+ The search is forwards if BINDING->start is greater than BINDING->end. */
+enum search_result
+search (char *string, SEARCH_BINDING *binding, long *poff)
+{
+ enum search_result result;
+
+ /* If the search is backwards, then search backwards, otherwise forwards. */
+ if (binding->start > binding->end)
+ result = search_backward (string, binding, poff);
+ else
+ result = search_forward (string, binding, poff);
+
+ return result;
+}
+
+/* Expand \n and \t in regexp to newlines and tabs */
+static char *
+regexp_expand_newlines_and_tabs (char *regexp)
+{
+ char *unescaped_regexp = xmalloc (1 + strlen (regexp));
+ char *p, *q;
+
+ for (p = regexp, q = unescaped_regexp; *p != '\0'; p++, q++)
+ {
+ if (*p == '\\')
+ switch(*++p)
+ {
+ case 'n':
+ *q = '\n';
+ break;
+ case 't':
+ *q = '\t';
+ break;
+ case '\0':
+ *q = '\\';
+ p--;
+ break;
+ default:
+ *q++ = '\\';
+ *q = *p;
+ break;
+ }
+ else
+ *q = *p;
+ }
+ *q = '\0';
+
+ return unescaped_regexp;
+}
+
+/* Escape any special characters in SEARCH_STRING. */
+static char *
+regexp_escape_string (char *search_string)
+{
+ char *special_chars = "\\[]^$.*(){}|+?";
+ char *p, *q;
+
+ char *escaped_string = xmalloc (strlen (search_string) * 2 + 1);
+
+ for (p = search_string, q = escaped_string; *p != '\0'; )
+ {
+ if (strchr (special_chars, *p))
+ {
+ *q++ = '\\';
+ }
+ *q++ = *p++;
+ }
+
+ *q = '\0';
+
+ return escaped_string;
+}
+
+
+static void
+extend_matches (MATCH_STATE *state)
+{
+ regmatch_t *matches = state->matches;
+ size_t match_alloc = state->match_alloc;
+ size_t match_count = state->match_count;
+ char *buffer = state->buffer;
+ size_t buflen = state->buflen;
+
+ regoff_t offset = 0;
+ char saved_char;
+ size_t initial_match_count = match_count;
+
+ if (state->finished)
+ return;
+
+ saved_char = buffer[buflen];
+ buffer[buflen] = '\0';
+
+ if (match_count > 0)
+ {
+ offset = matches[match_count - 1].rm_eo;
+
+ /* move past zero-length match */
+ if (offset == matches[match_count - 1].rm_so)
+ offset++;
+ }
+
+ while (offset < buflen && match_count < initial_match_count + 5)
+ {
+ int result = 0;
+ regmatch_t m;
+
+ result = regexec (&state->regex, &buffer[offset], 1, &m, REG_NOTBOL);
+ if (result == 0)
+ {
+ if (match_count == match_alloc)
+ {
+ /* The match list is full. */
+ if (match_alloc == 0)
+ match_alloc = 50;
+ matches = x2nrealloc
+ (matches, &match_alloc, sizeof matches[0]);
+ }
+
+ matches[match_count] = m;
+ matches[match_count].rm_so += offset;
+ matches[match_count].rm_eo += offset;
+ offset = matches[match_count++].rm_eo;
+
+ if (m.rm_eo == 0)
+ offset++; /* Avoid finding match again for a pattern of "$". */
+ }
+ else
+ {
+ state->finished = 1;
+ break;
+ }
+ }
+ buffer[buflen] = saved_char;
+
+ state->matches = matches;
+ state->match_alloc = match_alloc;
+ state->match_count = match_count;
+}
+
+/* Search BUFFER for REGEXP. If matches are found, pass back the list of
+ matches in MATCH_STATE. */
+enum search_result
+regexp_search (char *regexp, int is_literal, int is_insensitive,
+ char *buffer, size_t buflen,
+ MATCH_STATE *match_state)
+{
+ regex_t preg; /* Compiled pattern buffer for regexp. */
+ int result;
+ char *regexp_str;
+
+ if (!is_literal)
+ regexp_str = regexp_expand_newlines_and_tabs (regexp);
+ else
+ regexp_str = regexp_escape_string (regexp);
+
+ result = regcomp (&preg, regexp_str,
+ REG_EXTENDED | REG_NEWLINE
+ | (is_insensitive ? REG_ICASE : 0));
+ free (regexp_str);
+
+ if (result != 0)
+ {
+ int size = regerror (result, &preg, NULL, 0);
+ char *buf = xmalloc (size);
+ regerror (result, &preg, buf, size);
+ info_error (_("regexp error: %s"), buf);
+ free (buf);
+ return search_invalid;
+ }
+
+ match_state->matches = 0;
+ match_state->match_count = 0;
+ match_state->match_alloc = 0;
+ match_state->finished = 0;
+ match_state->regex = preg;
+ match_state->buffer = buffer;
+ match_state->buflen = buflen;
+
+ extend_matches (match_state);
+
+ if (match_state->match_count == 0)
+ {
+ free_matches (match_state);
+ return search_not_found;
+ }
+ else
+ return search_success;
+}
+
+/* Search forwards for STRING through the text delimited in BINDING. */
+enum search_result
+search_forward (char *string, SEARCH_BINDING *binding, long *poff)
+{
+ register int c, i, len;
+ register char *buff, *end;
+ char *alternate = NULL;
+
+ len = strlen (string);
+
+ /* We match characters in the search buffer against STRING and ALTERNATE.
+ ALTERNATE is a case reversed version of STRING; this is cheaper than
+ case folding each character before comparison. Alternate is only
+ used if the case folding bit is turned on in the passed BINDING. */
+
+ if (binding->flags & S_FoldCase)
+ {
+ alternate = xstrdup (string);
+
+ for (i = 0; i < len; i++)
+ {
+ if (islower (alternate[i]))
+ alternate[i] = toupper (alternate[i]);
+ else if (isupper (alternate[i]))
+ alternate[i] = tolower (alternate[i]);
+ }
+ }
+
+ buff = binding->buffer + binding->start;
+ end = binding->buffer + binding->end + 1;
+
+ while (buff < (end - len))
+ {
+ for (i = 0; i < len; i++)
+ {
+ c = buff[i];
+
+ if ((c != string[i]) && (!alternate || c != alternate[i]))
+ break;
+ }
+
+ if (!string[i])
+ {
+ if (alternate)
+ free (alternate);
+ if (binding->flags & S_SkipDest)
+ buff += len;
+ *poff = buff - binding->buffer;
+ return search_success;
+ }
+
+ buff++;
+ }
+
+ if (alternate)
+ free (alternate);
+
+ return search_not_found;
+}
+
+/* Search for STRING backwards through the text delimited in BINDING. */
+enum search_result
+search_backward (char *input_string, SEARCH_BINDING *binding, long *poff)
+{
+ register int c, i, len;
+ register char *buff, *end;
+ char *string;
+ char *alternate = NULL;
+
+ len = strlen (input_string);
+
+ /* Reverse the characters in the search string. */
+ string = xmalloc (1 + len);
+ for (c = 0, i = len - 1; input_string[c]; c++, i--)
+ string[i] = input_string[c];
+
+ string[c] = '\0';
+
+ /* We match characters in the search buffer against STRING and ALTERNATE.
+ ALTERNATE is a case reversed version of STRING; this is cheaper than
+ case folding each character before comparison. ALTERNATE is only
+ used if the case folding bit is turned on in the passed BINDING. */
+
+ if (binding->flags & S_FoldCase)
+ {
+ alternate = xstrdup (string);
+
+ for (i = 0; i < len; i++)
+ {
+ if (islower (alternate[i]))
+ alternate[i] = toupper (alternate[i]);
+ else if (isupper (alternate[i]))
+ alternate[i] = tolower (alternate[i]);
+ }
+ }
+
+ buff = binding->buffer + binding->start - 1;
+ end = binding->buffer + binding->end;
+
+ while (buff > (end + len))
+ {
+ for (i = 0; i < len; i++)
+ {
+ c = *(buff - i);
+
+ if (c != string[i] && (!alternate || c != alternate[i]))
+ break;
+ }
+
+ if (!string[i])
+ {
+ free (string);
+ if (alternate)
+ free (alternate);
+
+ if (binding->flags & S_SkipDest)
+ buff -= len;
+ *poff = 1 + buff - binding->buffer;
+ return search_success;
+ }
+
+ buff--;
+ }
+
+ free (string);
+ if (alternate)
+ free (alternate);
+
+ return search_not_found;
+}
+
+/* Find STRING in LINE, returning the offset of the end of the string.
+ Return an offset of -1 if STRING does not appear in LINE. The search
+ is bound by the end of the line (i.e., either NEWLINE or 0). */
+int
+string_in_line (char *string, char *line)
+{
+ register int end;
+ SEARCH_BINDING binding;
+ long offset;
+
+ /* Find the end of the line. */
+ for (end = 0; line[end] && line[end] != '\n'; end++);
+
+ /* Search for STRING within these confines. */
+ binding.buffer = line;
+ binding.start = 0;
+ binding.end = end;
+ binding.flags = S_FoldCase | S_SkipDest;
+
+ if (search_forward (string, &binding, &offset) == search_success)
+ return offset;
+ return -1;
+}
+
+/* Return non-zero if STRING is the first text to appear at BINDING. */
+int
+looking_at (char *string, SEARCH_BINDING *binding)
+{
+ long search_end;
+
+ if (search (string, binding, &search_end) != search_success)
+ return 0;
+
+ /* If the string was not found, SEARCH_END is -1. If the string was found,
+ but not right away, SEARCH_END is != binding->start. Otherwise, the
+ string was found at binding->start. */
+ return search_end == binding->start;
+}
+
+/* Return non-zero if POINTER is looking at the text at STRING before an
+ end-of-line. */
+int
+looking_at_line (char *string, char *pointer)
+{
+ int len;
+
+ len = strlen (string);
+ if (strncasecmp (pointer, string, len) != 0)
+ return 0;
+
+ pointer += len;
+ if (*pointer == '\n' || !strncmp (pointer, "\r\n", 2)
+ || *pointer == '\0')
+ return 1;
+ return 0;
+}
+
+/* **************************************************************** */
+/* */
+/* Accessing matches */
+/* */
+/* **************************************************************** */
+/* Search forwards or backwards for entries in MATCHES that start within
+ the search area. The search is forwards if DIR > 0, backward if
+ DIR < 0. Return index of match in *MATCH_INDEX. */
+enum search_result
+match_in_match_list (MATCH_STATE *match_state,
+ long start, long end, int dir,
+ int *match_index)
+{
+ regmatch_t *matches = match_state->matches;
+ size_t match_count = match_state->match_count;
+
+ int i;
+ int index = -1;
+
+ for (i = 0; i < match_count || !match_state->finished; i++)
+ {
+ /* get more matches as we need them */
+ if (i == match_count)
+ {
+ extend_matches (match_state);
+ matches = match_state->matches;
+ match_count = match_state->match_count;
+
+ if (i == match_count)
+ break;
+ }
+
+ if (matches[i].rm_so >= end)
+ break; /* No more matches found in search area. */
+
+ if (matches[i].rm_so >= start)
+ {
+ index = i;
+ if (dir > 0)
+ {
+ *match_index = index;
+ return search_success;
+ }
+ }
+ }
+
+ if (index != -1)
+ {
+ *match_index = index;
+ return search_success;
+ }
+
+ /* not found */
+ return search_not_found;
+}
+
+/* Return match INDEX in STATE. INDEX must be a valid index. */
+regmatch_t
+match_by_index (MATCH_STATE *state, int index)
+{
+ while (state->match_alloc <= index)
+ extend_matches (state);
+ return state->matches[index];
+}
+
+/* Free and clear all data in STATE. */
+void
+free_matches (MATCH_STATE *state)
+{
+ free (state->matches);
+ state->matches = 0;
+ state->match_count = state->match_alloc = state->finished = 0;
+ state->buffer = 0; /* do not free as it is kept elsewhere */
+ state->buflen = 0;
+ regfree (&state->regex);
+}
+
+int
+matches_ready (MATCH_STATE *state)
+{
+ return state->matches ? 1 : 0;
+}
+
+/* Starting at index *MATCH_INDEX, decide if we are inside a match
+ in MATCHES at offset OFF. The matches are assumed not to overlap
+ and to be in order. */
+void
+decide_if_in_match (long off, int *in_match,
+ MATCH_STATE *matches, size_t *match_index)
+{
+ size_t i = *match_index;
+ int m = *in_match;
+
+ for (; !at_end_of_matches (matches, i); i++)
+ {
+ if (match_by_index (matches, i).rm_so > off)
+ break;
+
+ m = 1;
+
+ if (match_by_index (matches, i).rm_eo > off)
+ break;
+
+ m = 0;
+ }
+
+ *match_index = i;
+ *in_match = m;
+}
+
+/* Used for iterating through a match list. */
+int
+at_end_of_matches (MATCH_STATE *state, int index)
+{
+ if (index < state->match_count)
+ return 0;
+ else
+ {
+ if (!state->finished)
+ extend_matches (state);
+
+ if (state->finished)
+ return (state->match_count == index) ? 1 : 0;
+ else
+ return 0;
+ }
+}
+
+
+
+/* **************************************************************** */
+/* */
+/* Small String Searches */
+/* */
+/* **************************************************************** */
+
+/* Function names that start with "skip" are passed a string, and return
+ an offset from the start of that string. Function names that start
+ with "find" are passed a SEARCH_BINDING, and return an absolute position
+ marker of the item being searched for. "Find" functions return a value
+ of -1 if the item being looked for couldn't be found. */
+
+/* Return the index of the first non-whitespace character in STRING. */
+int
+skip_whitespace (char *string)
+{
+ register int i;
+
+ for (i = 0; string && whitespace (string[i]); i++);
+ return i;
+}
+
+/* Return the index of the first non-whitespace or newline character in
+ STRING. */
+int
+skip_whitespace_and_newlines (char *string)
+{
+ register int i;
+
+ for (i = 0; string && whitespace_or_newline (string[i]); i++);
+ return i;
+}
+
+/* Return the index of the first whitespace character in STRING. */
+int
+skip_non_whitespace (char *string)
+{
+ register int i;
+
+ for (i = 0; string && string[i] && !whitespace (string[i]); i++);
+ return i;
+}
+
+/* **************************************************************** */
+/* */
+/* Searching FILE_BUFFER's */
+/* */
+/* **************************************************************** */
+
+/* Return the absolute position of the first occurence of a node separator
+ starting in BINDING->buffer between BINDING->start and BINDING->end
+ inclusive. Return -1 if no node separator was found. */
+long
+find_node_separator (SEARCH_BINDING *binding)
+{
+ register long i;
+ char *body;
+ int dir;
+
+ body = binding->buffer;
+ dir = binding->start < binding->end ? 1 : -1;
+
+ /* A node is started by [^L]^_[^L][\r]\n. That is to say, the C-l's are
+ optional, but the US and NEWLINE are not. This separator holds
+ true for all separated elements in an Info file, including the tags
+ table (if present) and the indirect tags table (if present). */
+ i = binding->start;
+ while (1)
+ {
+ /* Note that bytes are read in order from the buffer, so if at any
+ point a null byte is encountered signifying the end of the buffer,
+ no more bytes will be read past that point. */
+ if (body[i] == INFO_COOKIE)
+ {
+ int j = i + 1;
+
+ if (body[j] == INFO_FF)
+ j++;
+ if (body[j] == '\r')
+ j++;
+
+ if (body[j] == '\n')
+ return i;
+ }
+
+ if (i == binding->end)
+ break;
+ i += dir;
+ }
+
+ return -1;
+}
+
+/* Return the length of the node separator characters that BODY is currently
+ pointing at. If it's not pointing at a node separator, return 0. */
+int
+skip_node_separator (char *body)
+{
+ register int i;
+
+ i = 0;
+
+ if (body[i] == INFO_FF)
+ i++;
+
+ if (body[i++] != INFO_COOKIE)
+ return 0;
+
+ if (body[i] == INFO_FF)
+ i++;
+
+ if (body[i] == '\r')
+ i++;
+
+ if (body[i++] != '\n')
+ return 0;
+
+ return i;
+}
+
+/* Return the absolute position of the beginning of a section in this file
+ whose first line is LABEL, starting the search at binding->start. */
+long
+find_file_section (SEARCH_BINDING *binding, char *label)
+{
+ SEARCH_BINDING s;
+ long position;
+ int dir;
+
+ s.buffer = binding->buffer;
+ s.start = binding->start;
+ s.end = binding->end;
+ s.flags = S_FoldCase;
+ dir = binding->start < binding->end ? 1 : -1;
+
+ while ((position = find_node_separator (&s)) != -1 )
+ {
+ long offset = position;
+ offset += skip_node_separator (s.buffer + offset);
+ if (looking_at_line (label, s.buffer + offset))
+ return position;
+
+ if (dir > 0)
+ {
+ s.start = offset;
+ if (s.start >= s.end)
+ break;
+ }
+ else
+ {
+ s.start = position - 1;
+ if (s.start <= s.end)
+ break;
+ }
+ }
+ return -1;
+}
+
+/* Return the absolute position of the node named NODENAME in BINDING.
+ This is a brute force search, and we wish to avoid it when possible.
+ This function is called when a tag (indirect or otherwise) doesn't
+ really point to the right node. It returns the absolute position of
+ the separator preceding the node. */
+long
+find_node_in_binding (char *nodename, SEARCH_BINDING *binding)
+{
+ long position;
+ int offset;
+ SEARCH_BINDING s;
+
+ s.buffer = binding->buffer;
+ s.start = binding->start;
+ s.end = binding->end;
+ s.flags = 0;
+
+ while ((position = find_node_separator (&s)) != -1)
+ {
+ char *nodename_start;
+ char *read_nodename;
+ int found;
+
+ s.start = position;
+ s.start += skip_node_separator (s.buffer + s.start);
+
+ offset = string_in_line (INFO_NODE_LABEL, s.buffer + s.start);
+
+ if (offset == -1)
+ continue;
+
+ s.start += offset;
+ s.start += skip_whitespace (s.buffer + s.start);
+ nodename_start = s.buffer + s.start;
+ read_quoted_string (nodename_start, "\n\r\t,", 0, &read_nodename);
+ if (!read_nodename)
+ return -1;
+
+ found = !strcmp (read_nodename, nodename);
+ free (read_nodename);
+
+ if (found)
+ return position;
+ }
+ return -1;
+}