readline/histsearch.c

   1 /* histsearch.c -- searching the history list. */
   2
   3 /* Copyright (C) 1989, 1992-2009,2017 Free Software Foundation, Inc.
   4
   5    This file contains the GNU History Library (History), a set of
   6    routines for managing the text of previously typed lines.
   7
   8    History is free software: you can redistribute it and/or modify
   9    it under the terms of the GNU General Public License as published by
  10    the Free Software Foundation, either version 3 of the License, or
  11    (at your option) any later version.
  12
  13    History is distributed in the hope that it will be useful,
  14    but WITHOUT ANY WARRANTY; without even the implied warranty of
  15    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  16    GNU General Public License for more details.
  17
  18    You should have received a copy of the GNU General Public License
  19    along with History.  If not, see <http://www.gnu.org/licenses/>.
  20 */
  21
  22 #define READLINE_LIBRARY
  23
  24 #if defined (HAVE_CONFIG_H)
  25 #  include <config.h>
  26 #endif
  27
  28 #include <stdio.h>
  29 #if defined (HAVE_STDLIB_H)
  30 #  include <stdlib.h>
  31 #else
  32 #  include "ansi_stdlib.h"
  33 #endif /* HAVE_STDLIB_H */
  34
  35 #if defined (HAVE_UNISTD_H)
  36 #  ifdef _MINIX
  37 #    include <sys/types.h>
  38 #  endif
  39 #  include <unistd.h>
  40 #endif
  41
  42 #if defined (HAVE_FNMATCH)
  43 #  include <fnmatch.h>
  44 #endif
  45
  46 #include "history.h"
  47 #include "histlib.h"
  48 #include "xmalloc.h"
  49
  50 /* The list of alternate characters that can delimit a history search
  51    string. */
  52 char *history_search_delimiter_chars = (char *)NULL;
  53
  54 static int history_search_internal PARAMS((const char *, int, int));
  55
  56 /* Search the history for STRING, starting at history_offset.
  57    If DIRECTION < 0, then the search is through previous entries, else
  58    through subsequent.  If ANCHORED is non-zero, the string must
  59    appear at the beginning of a history line, otherwise, the string
  60    may appear anywhere in the line.  If the string is found, then
  61    current_history () is the history entry, and the value of this
  62    function is the offset in the line of that history entry that the
  63    string was found in.  Otherwise, nothing is changed, and a -1 is
  64    returned. */
  65
  66 static int
  67 history_search_internal (const char *string, int direction, int flags)
  68 {
  69   register int i, reverse;
  70   register char *line;
  71   register int line_index;
  72   int string_len, anchored, patsearch;
  73   HIST_ENTRY **the_history;     /* local */
  74
  75   i = history_offset;
  76   reverse = (direction < 0);
  77   anchored = (flags & ANCHORED_SEARCH);
  78 #if defined (HAVE_FNMATCH)
  79   patsearch = (flags & PATTERN_SEARCH);
  80 #else
  81   patsearch = 0;
  82 #endif
  83
  84   /* Take care of trivial cases first. */
  85   if (string == 0 || *string == '\0')
  86     return (-1);
  87
  88   if (!history_length || ((i >= history_length) && !reverse))
  89     return (-1);
  90
  91   if (reverse && (i >= history_length))
  92     i = history_length - 1;
  93
  94 #define NEXT_LINE() do { if (reverse) i--; else i++; } while (0)
  95
  96   the_history = history_list ();
  97   string_len = strlen (string);
  98   while (1)
  99     {
 100       /* Search each line in the history list for STRING. */
 101
 102       /* At limit for direction? */
 103       if ((reverse && i < 0) || (!reverse && i == history_length))
 104         return (-1);
 105
 106       line = the_history[i]->line;
 107       line_index = strlen (line);
 108
 109       /* If STRING is longer than line, no match. */
 110       if (patsearch == 0 && (string_len > line_index))
 111         {
 112           NEXT_LINE ();
 113           continue;
 114         }
 115
 116       /* Handle anchored searches first. */
 117       if (anchored == ANCHORED_SEARCH)
 118         {
 119 #if defined (HAVE_FNMATCH)
 120           if (patsearch)
 121             {
 122               if (fnmatch (string, line, 0) == 0)
 123                 {
 124                   history_offset = i;
 125                   return (0);
 126                 }
 127             }
 128           else
 129 #endif
 130           if (STREQN (string, line, string_len))
 131             {
 132               history_offset = i;
 133               return (0);
 134             }
 135
 136           NEXT_LINE ();
 137           continue;
 138         }
 139
 140       /* Do substring search. */
 141       if (reverse)
 142         {
 143           line_index -= (patsearch == 0) ? string_len : 1;
 144
 145           while (line_index >= 0)
 146             {
 147 #if defined (HAVE_FNMATCH)
 148               if (patsearch)
 149                 {
 150                   if (fnmatch (string, line + line_index, 0) == 0)
 151                     {
 152                       history_offset = i;
 153                       return (line_index);
 154                     }
 155                 }
 156               else
 157 #endif
 158               if (STREQN (string, line + line_index, string_len))
 159                 {
 160                   history_offset = i;
 161                   return (line_index);
 162                 }
 163               line_index--;
 164             }
 165         }
 166       else
 167         {
 168           register int limit;
 169
 170           limit = line_index - string_len + 1;
 171           line_index = 0;
 172
 173           while (line_index < limit)
 174             {
 175 #if defined (HAVE_FNMATCH)
 176               if (patsearch)
 177                 {
 178                   if (fnmatch (string, line + line_index, 0) == 0)
 179                     {
 180                       history_offset = i;
 181                       return (line_index);
 182                     }
 183                 }
 184               else
 185 #endif
 186               if (STREQN (string, line + line_index, string_len))
 187                 {
 188                   history_offset = i;
 189                   return (line_index);
 190                 }
 191               line_index++;
 192             }
 193         }
 194       NEXT_LINE ();
 195     }
 196 }
 197
 198 int
 199 _hs_history_patsearch (const char *string, int direction, int flags)
 200 {
 201   char *pat;
 202   size_t len, start;
 203   int ret, unescaped_backslash;
 204
 205 #if defined (HAVE_FNMATCH)
 206   /* Assume that the string passed does not have a leading `^' and any
 207      anchored search request is captured in FLAGS */
 208   len = strlen (string);
 209   ret = len - 1;
 210   /* fnmatch is required to reject a pattern that ends with an unescaped
 211      backslash */
 212   if (unescaped_backslash = (string[ret] == '\\'))
 213     {
 214       while (ret > 0 && string[--ret] == '\\')
 215         unescaped_backslash = 1 - unescaped_backslash;
 216     }
 217   if (unescaped_backslash)
 218     return -1;
 219   pat = (char *)xmalloc (len + 3);
 220   /* If the search string is not anchored, we'll be calling fnmatch (assuming
 221      we have it). Prefix a `*' to the front of the search string so we search
 222      anywhere in the line. */
 223   if ((flags & ANCHORED_SEARCH) == 0 && string[0] != '*')
 224     {
 225       pat[0] = '*';
 226       start = 1;
 227       len++;
 228     }
 229   else
 230     {
 231       start = 0;
 232     }
 233
 234   /* Attempt to reduce the number of searches by tacking a `*' onto the end
 235      of a pattern that doesn't have one.  Assume a pattern that ends in a
 236      backslash contains an even number of trailing backslashes; we check
 237      above */
 238   strcpy (pat + start, string);
 239   if (pat[len - 1] != '*')
 240     {
 241       pat[len] = '*';           /* XXX */
 242       pat[len+1] = '\0';
 243     }
 244 #else
 245   pat = string;
 246 #endif
 247
 248   ret = history_search_internal (pat, direction, flags|PATTERN_SEARCH);
 249
 250   if (pat != string)
 251     free (pat);
 252   return ret;
 253 }
 254
 255 /* Do a non-anchored search for STRING through the history in DIRECTION. */
 256 int
 257 history_search (const char *string, int direction)
 258 {
 259   return (history_search_internal (string, direction, NON_ANCHORED_SEARCH));
 260 }
 261
 262 /* Do an anchored search for string through the history in DIRECTION. */
 263 int
 264 history_search_prefix (const char *string, int direction)
 265 {
 266   return (history_search_internal (string, direction, ANCHORED_SEARCH));
 267 }
 268
 269 /* Search for STRING in the history list.  DIR is < 0 for searching
 270    backwards.  POS is an absolute index into the history list at
 271    which point to begin searching. */
 272 int
 273 history_search_pos (const char *string, int dir, int pos)
 274 {
 275   int ret, old;
 276
 277   old = where_history ();
 278   history_set_pos (pos);
 279   if (history_search (string, dir) == -1)
 280     {
 281       history_set_pos (old);
 282       return (-1);
 283     }
 284   ret = where_history ();
 285   history_set_pos (old);
 286   return ret;
 287 }