lib-search.c

   1 /*
   2  * Copyright Neil Brown ©2015-2023 <neil@brown.name>
   3  * May be distributed under terms of GPLv2 - see file:COPYING
   4  *
   5  * Searching.
   6  * "text-search" command searches from given mark until it
   7  * finds the given pattern or end of buffer.
   8  * If the pattern is found, then 'm' is left at the extremity of
   9  * the match in the direction of search: so the start if search backwards
  10  * or the end if searching forwards.
  11  * The returned value is the length of the match + 1, or an Efail
  12  * In the case of an error, the location of ->mark is undefined.
  13  * If mark2 is given, don't go beyond there.
  14  *
  15  * "text-match" is similar to text-search forwards, but requires that
  16  * the match starts at ->mark.  ->mark is moved to the end of the
  17  * match if the text does, in fact, match.
  18  * If the match fails, Efalse is returned (different to "text-search")
  19  */
  20
  21 #include <stdlib.h>
  22 #include <wctype.h>
  23 #include <string.h>
  24 #include "core.h"
  25 #include "rexel.h"
  26
  27 struct search_state {
  28         struct match_state *st safe;
  29         struct mark *end;
  30         struct mark *endmark;
  31         struct mark *point;
  32         wint_t prev_ch;
  33         bool prev_point;
  34         struct command c;
  35         char prefix[64];
  36         int prefix_len;
  37         bool anchor_at_end;
  38
  39         unsigned short *rxl safe;
  40 };
  41
  42 static void state_free(struct command *c safe)
  43 {
  44         struct search_state *ss = container_of(c, struct search_state, c);
  45
  46         free(ss->rxl);
  47         rxl_free_state(ss->st);
  48         mark_free(ss->end);
  49         mark_free(ss->endmark);
  50         mark_free(ss->point);
  51         free(ss);
  52 }
  53
  54 static int is_word(wint_t ch)
  55 {
  56         return ch == '_' || iswalnum(ch);
  57 }
  58
  59 /*
  60  * 'search_test' together with 'stuct search_state' encapsulates
  61  * a parsed regexp and some matching state.  If called as 'consume'
  62  * (or anything starting 'c') it processes one char into the match
  63  * and returns 1 if it is worth providing more characters.
  64  * Other options for ci->key are:
  65  * - reinit - state is re-initialised with flags from ->num, end and
  66  *            endmark from ->mark and ->mark2
  67  * - getinfo - extract total, start, len, since-start from match
  68  * - getcapture - get "start" or "len" for a capture in ->num
  69  * - interp - interpolate \N captures in ->str
  70  */
  71 DEF_CB(search_test)
  72 {
  73         struct search_state *ss = container_of(ci->comm,
  74                                                struct search_state, c);
  75
  76         if (ci->key[0] == 'c') {
  77                 /* consume */
  78                 wint_t wch = ci->num & 0xFFFFF;
  79                 wint_t flags = 0;
  80                 int maxlen, since_start;
  81                 enum rxl_found found;
  82                 int anchored;
  83
  84                 if ((unsigned int)ci->num == WEOF) {
  85                         wch = 0;
  86                         flags |= RXL_EOD;
  87                 }
  88                 if (ss->prev_ch == WEOF)
  89                         flags |= RXL_SOD;
  90                 if (is_eol(ss->prev_ch) || ss->prev_ch == WEOF ||
  91                     ss->prev_ch == 0)
  92                         flags |= RXL_SOL;
  93                 switch (is_word(ss->prev_ch) * 2 + is_word(wch)) {
  94                 case 0: /* in space */
  95                 case 3: /* within word */
  96                         flags |= RXL_NOWBRK;
  97                         break;
  98                 case 1: /* start of word */
  99                         flags |= RXL_SOW;
 100                         break;
 101                 case 2: /* end of word */
 102                         flags |= RXL_EOW;
 103                         break;
 104                 }
 105                 if (is_eol(wch))
 106                         flags |= RXL_EOL;
 107                 if (ss->prev_point) {
 108                         flags |= RXL_POINT;
 109                         ss->prev_point = False;
 110                 }
 111                 if (ss->point && ci->mark && mark_same(ss->point, ci->mark))
 112                         /* Need to assert POINT before next char */
 113                         ss->prev_point = True;
 114
 115                 found = rxl_advance(ss->st, wch | flags);
 116                 anchored = rxl_info(ss->st, &maxlen, NULL, NULL, &since_start);
 117
 118                 if (found >= RXL_MATCH && ss->endmark && ci->mark &&
 119                     since_start - maxlen <= 1) {
 120                         mark_to_mark(ss->endmark, ci->mark);
 121                         if (found == RXL_MATCH_FLAG)
 122                                 doc_prev(ci->home, ss->endmark);
 123                 }
 124                 if (ss->end && ci->mark &&
 125                     mark_ordered_not_same(ss->end, ci->mark)) {
 126                         /* Mark is *after* the char, so if end and mark
 127                          * are the same, we haven't passed the 'end' yet,
 128                          * and it is too early to abort.  Hence 'not' above
 129                          */
 130                         if (ss->anchor_at_end) {
 131                                 found = rxl_advance(ss->st, RXL_ANCHOR);
 132                                 anchored = 1;
 133                         } else
 134                                 return Efalse;
 135                 }
 136                 if (found == RXL_DONE)
 137                         /* No match here */
 138                         return Efalse;
 139                 if (!anchored && ci->str &&
 140                     ss->prefix_len && ci->num2 > ss->prefix_len) {
 141                         /* It is worth searching for the prefix to improve
 142                          * search speed.
 143                          */
 144                         int pstart = rxl_fast_match(ss->prefix, ss->prefix_len,
 145                                                     ci->str, ci->num2);
 146                         /* This may not be a full match even for the prefix,
 147                          * but it is a good place to skip to.
 148                          * If there was no match, pstart is ci->num2,
 149                          * so we skip the entire chunk.
 150                          * We reposition to just before the possible match
 151                          * so that ->end processesing is handled before the
 152                          * match can start.
 153                          */
 154                         if (pstart > 1)
 155                                 pstart = utf8_round_len(ci->str, pstart - 1);
 156                         if (pstart > 0) {
 157                                 const char *s;
 158                                 int prev = utf8_round_len(ci->str, pstart - 1);
 159                                 s = ci->str + prev;
 160                                 ss->prev_ch = get_utf8(&s, NULL);
 161                                 return pstart + 1;
 162                         }
 163                 }
 164                 ss->prev_ch = wch;
 165                 return 1;
 166         }
 167         if (strcmp(ci->key, "reinit") == 0) {
 168                 rxl_free_state(ss->st);
 169                 ss->st = rxl_prepare(ss->rxl, ci->num & 3);
 170                 ss->prev_ch = (unsigned int)ci->num2 ?: WEOF;
 171                 mark_free(ss->end);
 172                 mark_free(ss->endmark);
 173                 if (ci->mark) {
 174                         ss->end = mark_dup(ci->mark);
 175                         ss->anchor_at_end = ci->num & 4;
 176                 } else
 177                         ss->end = NULL;
 178                 if (ci->mark2)
 179                         ss->endmark = mark_dup(ci->mark2);
 180                 else
 181                         ss->endmark = NULL;
 182                 return 1;
 183         }
 184         if (strcmp(ci->key, "setpoint") == 0 && ci->mark) {
 185                 mark_free(ss->point);
 186                 ss->point = mark_dup(ci->mark);
 187                 return 1;
 188         }
 189         if (strcmp(ci->key, "getinfo") == 0 && ci->str) {
 190                 int len, total, start, since_start;
 191                 rxl_info(ss->st, &len, &total, &start, &since_start);
 192                 if (strcmp(ci->str, "len") == 0)
 193                         return len < 0 ? Efalse : len+1;
 194                 if (strcmp(ci->str, "total") == 0)
 195                         return total+1;
 196                 if (strcmp(ci->str, "start") == 0)
 197                         return start < 0 ? Efalse : start + 1;
 198                 if (strcmp(ci->str, "since-start") == 0)
 199                         return since_start < 0 ? Efalse : since_start + 1;
 200                 return Einval;
 201         }
 202         if (strcmp(ci->key, "getcapture") == 0 && ci->str) {
 203                 int start, len;
 204                 if (rxl_capture(ss->st, ci->num, ci->num2, &start, &len)) {
 205                         if (strcmp(ci->str, "start") == 0)
 206                                 return start + 1;
 207                         if (strcmp(ci->str, "len") == 0)
 208                                 return len + 1;
 209                         return Einval;
 210                 }
 211                 return Efalse;
 212         }
 213         if (strcmp(ci->key, "interp") == 0 && ci->str) {
 214                 char *ret;
 215                 ret = rxl_interp(ss->st, ci->str);
 216                 comm_call(ci->comm2, "cb", ci->focus, 0, NULL, ret);
 217                 free(ret);
 218                 return 1;
 219         }
 220         return Efail;
 221 }
 222
 223 static int search_forward(struct pane *p safe,
 224                           struct mark *m safe, struct mark *m2,
 225                           struct mark *point,
 226                           unsigned short *rxl safe,
 227                           struct mark *endmark, bool anchored)
 228 {
 229         /* Search forward from @m in @p for @rxl looking as far as @m2,
 230          * and leaving @endmark at the end point, and returning the
 231          * length of the match, or -1.
 232          */
 233         struct search_state ss;
 234         int maxlen;
 235
 236         if (m2 && m->seq >= m2->seq)
 237                 return -1;
 238         ss.st = rxl_prepare(rxl, anchored ? RXLF_ANCHORED : 0);
 239         ss.prefix_len = rxl_prefix(rxl, ss.prefix, sizeof(ss.prefix));
 240         ss.end = m2;
 241         ss.endmark = endmark;
 242         ss.point = point;
 243         ss.prev_point = point ? mark_same(point, m) : False;
 244         ss.c = search_test;
 245         ss.prev_ch = doc_prior(p, m);
 246         ss.anchor_at_end = False;
 247         call_comm("doc:content", p, &ss.c, 0, m, NULL, 0, m2);
 248         rxl_info(ss.st, &maxlen, NULL, NULL, NULL);
 249         rxl_free_state(ss.st);
 250         return maxlen;
 251 }
 252
 253 static int search_backward(struct pane *p safe,
 254                            struct mark *m safe, struct mark *m2,
 255                            struct mark *point,
 256                            unsigned short *rxl safe,
 257                            struct mark *endmark safe)
 258 {
 259         /* Search backward from @m in @p for a match of @s.  The match
 260          * must start at or before m, but may finish later.  Only search
 261          * as far as @m2 (if set), and leave endmark pointing at the
 262          * start of the match, if one is found.
 263          * Return length of match, or negative.
 264          *
 265          * rexel only lets us search forwards, and stepping back
 266          * one char at a time to match the pattern is too slow.
 267          * So we step back a steadily growing number of
 268          * chars, and search forward as far as the previous location.
 269          * Once we find any match, we check if there is a later one
 270          * that still satisfies.
 271          */
 272         struct search_state ss;
 273         int step_size = 65536;
 274         int maxlen;
 275         int ret = -1;
 276         struct mark *start = mark_dup(m); /* Start of the range to search */
 277         struct mark *end = mark_dup(m);
 278
 279         ss.end = end;
 280         ss.endmark = endmark;
 281         ss.point = point;
 282         ss.c = search_test;
 283         ss.prefix_len = rxl_prefix(rxl, ss.prefix, sizeof(ss.prefix));
 284         ss.anchor_at_end = True;
 285
 286         pane_set_time(p);
 287
 288         while (!m2 || m2->seq < start->seq) {
 289                 mark_to_mark(end, start);
 290                 call("doc:char", p, -step_size, start, NULL, 0, m2);
 291                 if (mark_same(start, end))
 292                         /* We have hit the start, don't continue */
 293                         break;
 294                 step_size *= 2;
 295                 ss.prev_ch = doc_prior(p, start);
 296                 ss.st = rxl_prepare(rxl, 0);
 297                 ss.prev_point = point ? mark_same(point, m) : False;
 298
 299                 mark_to_mark(m, start);
 300                 call_comm("doc:content", p, &ss.c, 0, m);
 301                 rxl_info(ss.st, &maxlen, NULL, NULL, NULL);
 302                 rxl_free_state(ss.st);
 303                 if (maxlen >= 0) {
 304                         /* found a match */
 305                         ret = maxlen;
 306                         break;
 307                 }
 308
 309                 if (pane_too_long(p, 2000)) {
 310                         /* FIXME returning success is wrong if we timed out
 311                          * But I want to move the point, and this is easiest.
 312                          * What do I really want here?
 313                          * Do I just need to make reverse search faster?
 314                          */
 315                         mark_to_mark(endmark, start);
 316                         ret = 0;
 317                         break;
 318                 }
 319         }
 320         while (maxlen >= 0) {
 321                 /* There is a match starting at 'endmark'.
 322                  * The might be a later match - check for it.
 323                  */
 324                 call("doc:char", p, -maxlen, ss.endmark);
 325                 if (mark_ordered_not_same(end, ss.endmark))
 326                         break;
 327                 ret = maxlen;
 328                 if (endmark != ss.endmark &&
 329                     mark_ordered_or_same(ss.endmark, endmark))
 330                         /* Didn't move forward!!  Presumably
 331                          * buggy doc:step implementation.
 332                          */
 333                         break;
 334
 335                 mark_to_mark(endmark, ss.endmark);
 336                 ss.endmark = m;
 337                 mark_to_mark(start, endmark);
 338                 ss.prev_ch = doc_next(p, start);
 339                 ss.st = rxl_prepare(rxl, 0);
 340                 call_comm("doc:content", p, &ss.c, 0, start);
 341                 rxl_info(ss.st, &maxlen, NULL, NULL, NULL);
 342                 rxl_free_state(ss.st);
 343         }
 344         mark_free(start);
 345         mark_free(end);
 346         return ret;
 347 }
 348
 349 DEF_CMD(text_search)
 350 {
 351         struct mark *m, *endmark = NULL;
 352         unsigned short *rxl;
 353         int since_start;
 354         int ret;
 355
 356         if (!ci->str)
 357                 return Enoarg;
 358
 359         rxl = rxl_parse(ci->str, NULL, ci->num);
 360         if (!rxl)
 361                 return Einval;
 362
 363         if (ci->mark) {
 364                 struct mark *point;
 365
 366                 m = ci->mark;
 367                 endmark = mark_dup(m);
 368                 point = call_ret(mark, "doc:point", ci->focus);
 369                 if (!endmark)
 370                         return Efail;
 371                 if (strcmp(ci->key, "text-match") == 0)
 372                         since_start = search_forward(ci->focus, m, ci->mark2,
 373                                                      point, rxl, endmark, True);
 374                 else if (ci->num2)
 375                         since_start = search_backward(ci->focus, m, ci->mark2,
 376                                                       point, rxl, endmark);
 377                 else
 378                         since_start = search_forward(ci->focus, m, ci->mark2,
 379                                                      point, rxl, endmark, False);
 380
 381                 if (since_start >= 0)
 382                         mark_to_mark(m, endmark);
 383                 mark_free(endmark);
 384                 if (since_start < 0) {
 385                         if (strcmp(ci->key, "text-match") == 0)
 386                                 ret = Efalse; /* non-fatal */
 387                         else
 388                                 ret = Efail;
 389                 } else
 390                         ret = since_start + 1;
 391         } else if (ci->str2) {
 392                 struct match_state *st = rxl_prepare(
 393                         rxl, strcmp(ci->key, "text-match") == 0 ? RXLF_ANCHORED : 0);
 394                 int flags = RXL_SOL|RXL_SOD;
 395                 const char *t = ci->str2;
 396                 int thelen = -1, start = 0;
 397                 enum rxl_found r;
 398                 wint_t prev_ch = WEOF;
 399
 400                 do {
 401                         wint_t wc = get_utf8(&t, NULL);
 402                         if (wc >= WERR|| (ci->num2 > 0 && t > ci->str2 + ci->num2)) {
 403                                 rxl_advance(st, RXL_EOL|RXL_EOD);
 404                                 break;
 405                         }
 406                         switch (is_word(prev_ch) * 2 + is_word(wc)) {
 407                         case 0: /* in space */
 408                         case 3: /* within word */
 409                                 flags |= RXL_NOWBRK;
 410                                 break;
 411                         case 1: /* start of word */
 412                                 flags |= RXL_SOW;
 413                                 break;
 414                         case 2: /* end of word */
 415                                 flags |= RXL_EOW;
 416                                 break;
 417                         }
 418                         if (is_eol(wc))
 419                                 flags |= RXL_EOL;
 420                         if (prev_ch == WEOF || is_eol(prev_ch))
 421                                 flags |= RXL_SOL;
 422                         prev_ch = wc;
 423                         r = rxl_advance(st, wc | flags);
 424                         flags = 0;
 425                         if (r >= RXL_MATCH) {
 426                                 /* "start" is in chars, not bytes, so we cannot.
 427                                  * use it.  Need since_start and then count
 428                                  * back.
 429                                  */
 430                                 rxl_info(st, &thelen, NULL, NULL, &since_start);
 431                                 start = t - ci->str2;
 432                                 while (since_start > 0) {
 433                                         start = utf8_round_len(ci->str2, start-1);
 434                                         since_start -= 1;
 435                                 }
 436                         }
 437                 } while (r != RXL_DONE);
 438                 rxl_free_state(st);
 439                 if (thelen < 0)
 440                         ret = Efalse;
 441                 else if (strcmp(ci->key, "text-match") == 0)
 442                         ret = thelen + 1;
 443                 else
 444                         ret = start + 1;
 445         } else {
 446                 ret = Einval;
 447         }
 448         free(rxl);
 449         return ret;
 450 }
 451
 452 DEF_CMD(make_search)
 453 {
 454         struct search_state *ss;
 455         unsigned short *rxl;
 456
 457         if (!ci->str)
 458                 return Enoarg;
 459
 460         rxl = rxl_parse(ci->str, NULL, ci->num2);
 461         if (!rxl)
 462                 return Einval;
 463         ss = calloc(1, sizeof(*ss));
 464         ss->rxl = rxl;
 465         ss->prefix_len = rxl_prefix(rxl, ss->prefix, sizeof(ss->prefix));
 466         ss->c = search_test;
 467         ss->c.free = state_free;
 468         command_get(&ss->c);
 469         comm_call(&ss->c, "reinit", ci->focus,
 470                   ci->num, ci->mark, NULL, 0, ci->mark2);
 471         comm_call(ci->comm2, "cb", ci->focus,
 472                   0, NULL, NULL,
 473                   0, NULL, NULL, 0,0, &ss->c);
 474         command_put(&ss->c);
 475         return 1;
 476 }
 477
 478 struct texteql {
 479         struct command c;
 480         const char *text safe;
 481         bool matched;
 482 };
 483
 484 DEF_CB(equal_test)
 485 {
 486         struct texteql *te = container_of(ci->comm, struct texteql, c);
 487         wint_t have, want;
 488         int i;
 489
 490         if (!te->text[0])
 491                 return Efalse;
 492         have = ci->num & 0xFFFFF;
 493         want = get_utf8(&te->text, NULL);
 494         if (have != want)
 495                 return Efalse;
 496         for (i = 0;
 497              i < ci->num2 && ci->str;
 498              i++)
 499                 if (!te->text[i] || te->text[i] != ci->str[i])
 500                         break;
 501         te->text += i;
 502         if (!te->text[0])
 503                 te->matched = True;
 504         if (ci->str && i < ci->num2)
 505                 /* Stop looking */
 506                 return Efalse;
 507         return 1 + i;
 508 }
 509
 510 DEF_CMD(text_equals)
 511 {
 512         struct texteql te;
 513
 514         if (!ci->str || !ci->mark)
 515                 return Enoarg;
 516
 517         te.c = equal_test;
 518         te.text = ci->str;
 519         te.matched = False;
 520         call_comm("doc:content", ci->focus, &te.c, 0, ci->mark);
 521         return te.matched ? 1 : Efalse;
 522 }
 523
 524 void edlib_init(struct pane *ed safe)
 525 {
 526         call_comm("global-set-command", ed, &text_search, 0, NULL,
 527                   "text-search");
 528         call_comm("global-set-command", ed, &text_search, 0, NULL,
 529                   "text-match");
 530         call_comm("global-set-command", ed, &make_search, 0, NULL,
 531                   "make-search");
 532         call_comm("global-set-command", ed, &text_equals, 0, NULL,
 533                   "text-equals");
 534 }