1238730Sdelphij/* 2294286Sdelphij * Copyright (C) 1984-2015 Mark Nudelman 3238730Sdelphij * 4238730Sdelphij * You may distribute under the terms of either the GNU General Public 5238730Sdelphij * License or the Less License, as specified in the README file. 6238730Sdelphij * 7238730Sdelphij * For more information, see the README file. 8238730Sdelphij */ 960786Sps 1060786Sps 1160786Sps/* 1260786Sps * Routines to search a file for a pattern. 1360786Sps */ 1460786Sps 1560786Sps#include "less.h" 16195941Sdelphij#include "pattern.h" 1760786Sps#include "position.h" 18172471Sdelphij#include "charset.h" 1960786Sps 2060786Sps#define MINPOS(a,b) (((a) < (b)) ? (a) : (b)) 2160786Sps#define MAXPOS(a,b) (((a) > (b)) ? (a) : (b)) 2260786Sps 2360786Spsextern int sigs; 2460786Spsextern int how_search; 2560786Spsextern int caseless; 2660786Spsextern int linenums; 2760786Spsextern int sc_height; 2860786Spsextern int jump_sline; 2960786Spsextern int bs_mode; 30128348Stjrextern int ctldisp; 3163131Spsextern int status_col; 32170259Sdelphijextern void * constant ml_search; 3360786Spsextern POSITION start_attnpos; 3460786Spsextern POSITION end_attnpos; 35191930Sdelphijextern int utf_mode; 36191930Sdelphijextern int screen_trashed; 3760786Sps#if HILITE_SEARCH 3860786Spsextern int hilite_search; 3960786Spsextern int size_linebuf; 4060786Spsextern int squished; 4160786Spsextern int can_goto_line; 4260786Spsstatic int hide_hilite; 4360786Spsstatic POSITION prep_startpos; 4460786Spsstatic POSITION prep_endpos; 45195941Sdelphijstatic int is_caseless; 46195941Sdelphijstatic int is_ucase_pattern; 4760786Sps 48294286Sdelphij/* 49294286Sdelphij * Structures for maintaining a set of ranges for hilites and filtered-out 50294286Sdelphij * lines. Each range is stored as a node within a red-black tree, and we 51294286Sdelphij * try to extend existing ranges (without creating overlaps) rather than 52294286Sdelphij * create new nodes if possible. We remember the last node found by a 53294286Sdelphij * search for constant-time lookup if the next search is near enough to 54294286Sdelphij * the previous. To aid that, we overlay a secondary doubly-linked list 55294286Sdelphij * on top of the red-black tree so we can find the preceding/succeeding 56294286Sdelphij * nodes also in constant time. 57294286Sdelphij * 58294286Sdelphij * Each node is allocated from a series of pools, each pool double the size 59294286Sdelphij * of the previous (for amortised constant time allocation). Since our only 60294286Sdelphij * tree operations are clear and node insertion, not node removal, we don't 61294286Sdelphij * need to maintain a usage bitmap or freelist and can just return nodes 62294286Sdelphij * from the pool in-order until capacity is reached. 63294286Sdelphij */ 6460786Spsstruct hilite 6560786Sps{ 6660786Sps POSITION hl_startpos; 6760786Sps POSITION hl_endpos; 6860786Sps}; 69294286Sdelphijstruct hilite_node 70294286Sdelphij{ 71294286Sdelphij struct hilite_node *parent; 72294286Sdelphij struct hilite_node *left; 73294286Sdelphij struct hilite_node *right; 74294286Sdelphij struct hilite_node *prev; 75294286Sdelphij struct hilite_node *next; 76294286Sdelphij int red; 77294286Sdelphij struct hilite r; 78294286Sdelphij}; 79294286Sdelphijstruct hilite_storage 80294286Sdelphij{ 81294286Sdelphij int capacity; 82294286Sdelphij int used; 83294286Sdelphij struct hilite_storage *next; 84294286Sdelphij struct hilite_node *nodes; 85294286Sdelphij}; 86294286Sdelphijstruct hilite_tree 87294286Sdelphij{ 88294286Sdelphij struct hilite_storage *first; 89294286Sdelphij struct hilite_storage *current; 90294286Sdelphij struct hilite_node *root; 91294286Sdelphij struct hilite_node *lookaside; 92294286Sdelphij}; 93294286Sdelphij#define HILITE_INITIALIZER() { NULL, NULL, NULL, NULL } 94294286Sdelphij#define HILITE_LOOKASIDE_STEPS 2 95294286Sdelphij 96294286Sdelphijstatic struct hilite_tree hilite_anchor = HILITE_INITIALIZER(); 97294286Sdelphijstatic struct hilite_tree filter_anchor = HILITE_INITIALIZER(); 98294286Sdelphij 9960786Sps#endif 10060786Sps 10160786Sps/* 10260786Sps * These are the static variables that represent the "remembered" 103195941Sdelphij * search pattern and filter pattern. 10460786Sps */ 105195941Sdelphijstruct pattern_info { 106195941Sdelphij DEFINE_PATTERN(compiled); 107195941Sdelphij char* text; 108195941Sdelphij int search_type; 109195941Sdelphij}; 110237613Sdelphij 111237613Sdelphij#if NO_REGEX 112237613Sdelphij#define info_compiled(info) ((void*)0) 113237613Sdelphij#else 114237613Sdelphij#define info_compiled(info) ((info)->compiled) 115237613Sdelphij#endif 116195941Sdelphij 117195941Sdelphijstatic struct pattern_info search_info; 118195941Sdelphijstatic struct pattern_info filter_info; 11960786Sps 120173685Sdelphij/* 121221715Sdelphij * Are there any uppercase letters in this string? 122221715Sdelphij */ 123221715Sdelphij static int 124221715Sdelphijis_ucase(str) 125221715Sdelphij char *str; 126221715Sdelphij{ 127221715Sdelphij char *str_end = str + strlen(str); 128221715Sdelphij LWCHAR ch; 129221715Sdelphij 130221715Sdelphij while (str < str_end) 131221715Sdelphij { 132221715Sdelphij ch = step_char(&str, +1, str_end); 133221715Sdelphij if (IS_UPPER(ch)) 134221715Sdelphij return (1); 135221715Sdelphij } 136221715Sdelphij return (0); 137221715Sdelphij} 138221715Sdelphij 139221715Sdelphij/* 140195941Sdelphij * Compile and save a search pattern. 141173685Sdelphij */ 142173685Sdelphij static int 143195941Sdelphijset_pattern(info, pattern, search_type) 144195941Sdelphij struct pattern_info *info; 145195941Sdelphij char *pattern; 146195941Sdelphij int search_type; 147173685Sdelphij{ 148237613Sdelphij#if !NO_REGEX 149195941Sdelphij if (pattern == NULL) 150237613Sdelphij CLEAR_PATTERN(info->compiled); 151195941Sdelphij else if (compile_pattern(pattern, search_type, &info->compiled) < 0) 152195941Sdelphij return -1; 153237613Sdelphij#endif 154195941Sdelphij /* Pattern compiled successfully; save the text too. */ 155195941Sdelphij if (info->text != NULL) 156195941Sdelphij free(info->text); 157195941Sdelphij info->text = NULL; 158195941Sdelphij if (pattern != NULL) 159195941Sdelphij { 160195941Sdelphij info->text = (char *) ecalloc(1, strlen(pattern)+1); 161195941Sdelphij strcpy(info->text, pattern); 162195941Sdelphij } 163195941Sdelphij info->search_type = search_type; 164221715Sdelphij 165221715Sdelphij /* 166221715Sdelphij * Ignore case if -I is set OR 167221715Sdelphij * -i is set AND the pattern is all lowercase. 168221715Sdelphij */ 169221715Sdelphij is_ucase_pattern = is_ucase(pattern); 170221715Sdelphij if (is_ucase_pattern && caseless != OPT_ONPLUS) 171221715Sdelphij is_caseless = 0; 172221715Sdelphij else 173221715Sdelphij is_caseless = caseless; 174195941Sdelphij return 0; 175173685Sdelphij} 176173685Sdelphij 177173685Sdelphij/* 178195941Sdelphij * Discard a saved pattern. 179173685Sdelphij */ 18060786Sps static void 181195941Sdelphijclear_pattern(info) 182195941Sdelphij struct pattern_info *info; 18360786Sps{ 184195941Sdelphij if (info->text != NULL) 185195941Sdelphij free(info->text); 186195941Sdelphij info->text = NULL; 187237613Sdelphij#if !NO_REGEX 188195941Sdelphij uncompile_pattern(&info->compiled); 189237613Sdelphij#endif 190195941Sdelphij} 19160786Sps 192195941Sdelphij/* 193195941Sdelphij * Initialize saved pattern to nothing. 194195941Sdelphij */ 195195941Sdelphij static void 196195941Sdelphijinit_pattern(info) 197195941Sdelphij struct pattern_info *info; 198195941Sdelphij{ 199195941Sdelphij CLEAR_PATTERN(info->compiled); 200195941Sdelphij info->text = NULL; 201195941Sdelphij info->search_type = 0; 202195941Sdelphij} 203170259Sdelphij 204195941Sdelphij/* 205195941Sdelphij * Initialize search variables. 206195941Sdelphij */ 207195941Sdelphij public void 208195941Sdelphijinit_search() 209195941Sdelphij{ 210195941Sdelphij init_pattern(&search_info); 211195941Sdelphij init_pattern(&filter_info); 21260786Sps} 21360786Sps 21460786Sps/* 215195941Sdelphij * Determine which text conversions to perform before pattern matching. 216128348Stjr */ 217128348Stjr static int 218128348Stjrget_cvt_ops() 219128348Stjr{ 220128348Stjr int ops = 0; 221128348Stjr if (is_caseless || bs_mode == BS_SPECIAL) 222128348Stjr { 223128348Stjr if (is_caseless) 224128348Stjr ops |= CVT_TO_LC; 225128348Stjr if (bs_mode == BS_SPECIAL) 226128348Stjr ops |= CVT_BS; 227128348Stjr if (bs_mode != BS_CONTROL) 228128348Stjr ops |= CVT_CRLF; 229128348Stjr } else if (bs_mode != BS_CONTROL) 230128348Stjr { 231128348Stjr ops |= CVT_CRLF; 232128348Stjr } 233128348Stjr if (ctldisp == OPT_ONPLUS) 234128348Stjr ops |= CVT_ANSI; 235128348Stjr return (ops); 236128348Stjr} 237128348Stjr 238128348Stjr/* 23960786Sps * Is there a previous (remembered) search pattern? 24060786Sps */ 24160786Sps static int 242195941Sdelphijprev_pattern(info) 243195941Sdelphij struct pattern_info *info; 24460786Sps{ 245237613Sdelphij#if !NO_REGEX 246237613Sdelphij if ((info->search_type & SRCH_NO_REGEX) == 0) 247237613Sdelphij return (!is_null_pattern(info->compiled)); 248237613Sdelphij#endif 249237613Sdelphij return (info->text != NULL); 25060786Sps} 25160786Sps 25260786Sps#if HILITE_SEARCH 25360786Sps/* 25460786Sps * Repaint the hilites currently displayed on the screen. 25560786Sps * Repaint each line which contains highlighted text. 25660786Sps * If on==0, force all hilites off. 25760786Sps */ 25860786Sps public void 25960786Spsrepaint_hilite(on) 26060786Sps int on; 26160786Sps{ 26260786Sps int slinenum; 26360786Sps POSITION pos; 26460786Sps int save_hide_hilite; 26560786Sps 26660786Sps if (squished) 26760786Sps repaint(); 26860786Sps 26960786Sps save_hide_hilite = hide_hilite; 27060786Sps if (!on) 27160786Sps { 27260786Sps if (hide_hilite) 27360786Sps return; 27460786Sps hide_hilite = 1; 27560786Sps } 27660786Sps 27760786Sps if (!can_goto_line) 27860786Sps { 27960786Sps repaint(); 28060786Sps hide_hilite = save_hide_hilite; 28160786Sps return; 28260786Sps } 28360786Sps 28460786Sps for (slinenum = TOP; slinenum < TOP + sc_height-1; slinenum++) 28560786Sps { 28660786Sps pos = position(slinenum); 28760786Sps if (pos == NULL_POSITION) 28860786Sps continue; 289195941Sdelphij (void) forw_line(pos); 290195941Sdelphij goto_line(slinenum); 291195941Sdelphij put_line(); 29260786Sps } 293221715Sdelphij lower_left(); 29460786Sps hide_hilite = save_hide_hilite; 29560786Sps} 29660786Sps 29760786Sps/* 29860786Sps * Clear the attn hilite. 29960786Sps */ 30060786Sps public void 30160786Spsclear_attn() 30260786Sps{ 30360786Sps int slinenum; 30460786Sps POSITION old_start_attnpos; 30560786Sps POSITION old_end_attnpos; 30660786Sps POSITION pos; 30760786Sps POSITION epos; 308170898Sdelphij int moved = 0; 30960786Sps 31060786Sps if (start_attnpos == NULL_POSITION) 31160786Sps return; 31260786Sps old_start_attnpos = start_attnpos; 31360786Sps old_end_attnpos = end_attnpos; 31460786Sps start_attnpos = end_attnpos = NULL_POSITION; 31560786Sps 31660786Sps if (!can_goto_line) 31760786Sps { 31860786Sps repaint(); 31960786Sps return; 32060786Sps } 32160786Sps if (squished) 32260786Sps repaint(); 32360786Sps 32460786Sps for (slinenum = TOP; slinenum < TOP + sc_height-1; slinenum++) 32560786Sps { 32660786Sps pos = position(slinenum); 32760786Sps if (pos == NULL_POSITION) 32860786Sps continue; 32960786Sps epos = position(slinenum+1); 33060786Sps if (pos < old_end_attnpos && 33160786Sps (epos == NULL_POSITION || epos > old_start_attnpos)) 33260786Sps { 33360786Sps (void) forw_line(pos); 33460786Sps goto_line(slinenum); 33560786Sps put_line(); 336170898Sdelphij moved = 1; 33760786Sps } 33860786Sps } 339170898Sdelphij if (moved) 340170898Sdelphij lower_left(); 34160786Sps} 34260786Sps#endif 34360786Sps 34460786Sps/* 34560786Sps * Hide search string highlighting. 34660786Sps */ 34760786Sps public void 34860786Spsundo_search() 34960786Sps{ 350195941Sdelphij if (!prev_pattern(&search_info)) 35160786Sps { 35260786Sps error("No previous regular expression", NULL_PARG); 35360786Sps return; 35460786Sps } 35560786Sps#if HILITE_SEARCH 35660786Sps hide_hilite = !hide_hilite; 35760786Sps repaint_hilite(1); 35860786Sps#endif 35960786Sps} 36060786Sps 36160786Sps#if HILITE_SEARCH 36260786Sps/* 36360786Sps * Clear the hilite list. 36460786Sps */ 36560786Sps public void 366191930Sdelphijclr_hlist(anchor) 367294286Sdelphij struct hilite_tree *anchor; 36860786Sps{ 369294286Sdelphij struct hilite_storage *hls; 370294286Sdelphij struct hilite_storage *nexthls; 37160786Sps 372294286Sdelphij for (hls = anchor->first; hls != NULL; hls = nexthls) 37360786Sps { 374294286Sdelphij nexthls = hls->next; 375294286Sdelphij free((void*)hls->nodes); 376294286Sdelphij free((void*)hls); 37760786Sps } 378294286Sdelphij anchor->first = NULL; 379294286Sdelphij anchor->current = NULL; 380294286Sdelphij anchor->root = NULL; 381294286Sdelphij 382294286Sdelphij anchor->lookaside = NULL; 383294286Sdelphij 38460786Sps prep_startpos = prep_endpos = NULL_POSITION; 38560786Sps} 38660786Sps 387191930Sdelphij public void 388191930Sdelphijclr_hilite() 389191930Sdelphij{ 390191930Sdelphij clr_hlist(&hilite_anchor); 391191930Sdelphij} 392191930Sdelphij 393191930Sdelphij public void 394191930Sdelphijclr_filter() 395191930Sdelphij{ 396191930Sdelphij clr_hlist(&filter_anchor); 397191930Sdelphij} 398191930Sdelphij 399294286Sdelphij struct hilite_node* 400294286Sdelphijhlist_last(anchor) 401294286Sdelphij struct hilite_tree *anchor; 402294286Sdelphij{ 403294286Sdelphij struct hilite_node *n = anchor->root; 404294286Sdelphij while (n != NULL && n->right != NULL) 405294286Sdelphij n = n->right; 406294286Sdelphij return n; 407294286Sdelphij} 408294286Sdelphij 409294286Sdelphij struct hilite_node* 410294286Sdelphijhlist_next(n) 411294286Sdelphij struct hilite_node *n; 412294286Sdelphij{ 413294286Sdelphij return n->next; 414294286Sdelphij} 415294286Sdelphij 416294286Sdelphij struct hilite_node* 417294286Sdelphijhlist_prev(n) 418294286Sdelphij struct hilite_node *n; 419294286Sdelphij{ 420294286Sdelphij return n->prev; 421294286Sdelphij} 422294286Sdelphij 42360786Sps/* 424294286Sdelphij * Find the node covering pos, or the node after it if no node covers it, 425294286Sdelphij * or return NULL if pos is after the last range. Remember the found node, 426294286Sdelphij * to speed up subsequent searches for the same or similar positions (if 427294286Sdelphij * we return NULL, remember the last node.) 428294286Sdelphij */ 429294286Sdelphij struct hilite_node* 430294286Sdelphijhlist_find(anchor, pos) 431294286Sdelphij struct hilite_tree *anchor; 432294286Sdelphij POSITION pos; 433294286Sdelphij{ 434294286Sdelphij struct hilite_node *n, *m; 435294286Sdelphij 436294286Sdelphij if (anchor->lookaside) 437294286Sdelphij { 438294286Sdelphij int steps = 0; 439294286Sdelphij int hit = 0; 440294286Sdelphij 441294286Sdelphij n = anchor->lookaside; 442294286Sdelphij 443294286Sdelphij for (;;) 444294286Sdelphij { 445294286Sdelphij if (pos < n->r.hl_endpos) 446294286Sdelphij { 447294286Sdelphij if (n->prev == NULL || pos >= n->prev->r.hl_endpos) 448294286Sdelphij { 449294286Sdelphij hit = 1; 450294286Sdelphij break; 451294286Sdelphij } 452294286Sdelphij } else if (n->next == NULL) 453294286Sdelphij { 454294286Sdelphij n = NULL; 455294286Sdelphij hit = 1; 456294286Sdelphij break; 457294286Sdelphij } 458294286Sdelphij 459294286Sdelphij /* 460294286Sdelphij * If we don't find the right node within a small 461294286Sdelphij * distance, don't keep doing a linear search! 462294286Sdelphij */ 463294286Sdelphij if (steps >= HILITE_LOOKASIDE_STEPS) 464294286Sdelphij break; 465294286Sdelphij steps++; 466294286Sdelphij 467294286Sdelphij if (pos < n->r.hl_endpos) 468294286Sdelphij anchor->lookaside = n = n->prev; 469294286Sdelphij else 470294286Sdelphij anchor->lookaside = n = n->next; 471294286Sdelphij } 472294286Sdelphij 473294286Sdelphij if (hit) 474294286Sdelphij return n; 475294286Sdelphij } 476294286Sdelphij 477294286Sdelphij n = anchor->root; 478294286Sdelphij m = NULL; 479294286Sdelphij 480294286Sdelphij while (n != NULL) 481294286Sdelphij { 482294286Sdelphij if (pos < n->r.hl_startpos) 483294286Sdelphij { 484294286Sdelphij if (n->left != NULL) 485294286Sdelphij { 486294286Sdelphij m = n; 487294286Sdelphij n = n->left; 488294286Sdelphij continue; 489294286Sdelphij } 490294286Sdelphij break; 491294286Sdelphij } 492294286Sdelphij if (pos >= n->r.hl_endpos) 493294286Sdelphij { 494294286Sdelphij if (n->right != NULL) 495294286Sdelphij { 496294286Sdelphij n = n->right; 497294286Sdelphij continue; 498294286Sdelphij } 499294286Sdelphij if (m != NULL) 500294286Sdelphij { 501294286Sdelphij n = m; 502294286Sdelphij } else 503294286Sdelphij { 504294286Sdelphij m = n; 505294286Sdelphij n = NULL; 506294286Sdelphij } 507294286Sdelphij } 508294286Sdelphij break; 509294286Sdelphij } 510294286Sdelphij 511294286Sdelphij if (n != NULL) 512294286Sdelphij anchor->lookaside = n; 513294286Sdelphij else if (m != NULL) 514294286Sdelphij anchor->lookaside = m; 515294286Sdelphij 516294286Sdelphij return n; 517294286Sdelphij} 518294286Sdelphij 519294286Sdelphij/* 52060786Sps * Should any characters in a specified range be highlighted? 521161478Sdelphij */ 522161478Sdelphij static int 523161478Sdelphijis_hilited_range(pos, epos) 524161478Sdelphij POSITION pos; 525161478Sdelphij POSITION epos; 526161478Sdelphij{ 527294286Sdelphij struct hilite_node *n = hlist_find(&hilite_anchor, pos); 528294286Sdelphij return (n != NULL && (epos == NULL_POSITION || epos > n->r.hl_startpos)); 529161478Sdelphij} 530161478Sdelphij 531191930Sdelphij/* 532191930Sdelphij * Is a line "filtered" -- that is, should it be hidden? 533191930Sdelphij */ 534191930Sdelphij public int 535191930Sdelphijis_filtered(pos) 536191930Sdelphij POSITION pos; 537191930Sdelphij{ 538294286Sdelphij struct hilite_node *n; 539191930Sdelphij 540191930Sdelphij if (ch_getflags() & CH_HELPFILE) 541191930Sdelphij return (0); 542191930Sdelphij 543294286Sdelphij n = hlist_find(&filter_anchor, pos); 544294286Sdelphij return (n != NULL && pos >= n->r.hl_startpos); 545294286Sdelphij} 546294286Sdelphij 547294286Sdelphij/* 548294286Sdelphij * If pos is hidden, return the next position which isn't, otherwise 549294286Sdelphij * just return pos. 550294286Sdelphij */ 551294286Sdelphij public POSITION 552294286Sdelphijnext_unfiltered(pos) 553294286Sdelphij POSITION pos; 554294286Sdelphij{ 555294286Sdelphij struct hilite_node *n; 556294286Sdelphij 557294286Sdelphij if (ch_getflags() & CH_HELPFILE) 558294286Sdelphij return (pos); 559294286Sdelphij 560294286Sdelphij n = hlist_find(&filter_anchor, pos); 561294286Sdelphij while (n != NULL && pos >= n->r.hl_startpos) 562191930Sdelphij { 563294286Sdelphij pos = n->r.hl_endpos; 564294286Sdelphij n = n->next; 565191930Sdelphij } 566294286Sdelphij return (pos); 567191930Sdelphij} 568191930Sdelphij 569161478Sdelphij/* 570294286Sdelphij * If pos is hidden, return the previous position which isn't or 0 if 571294286Sdelphij * we're filtered right to the beginning, otherwise just return pos. 572294286Sdelphij */ 573294286Sdelphij public POSITION 574294286Sdelphijprev_unfiltered(pos) 575294286Sdelphij POSITION pos; 576294286Sdelphij{ 577294286Sdelphij struct hilite_node *n; 578294286Sdelphij 579294286Sdelphij if (ch_getflags() & CH_HELPFILE) 580294286Sdelphij return (pos); 581294286Sdelphij 582294286Sdelphij n = hlist_find(&filter_anchor, pos); 583294286Sdelphij while (n != NULL && pos >= n->r.hl_startpos) 584294286Sdelphij { 585294286Sdelphij pos = n->r.hl_startpos; 586294286Sdelphij if (pos == 0) 587294286Sdelphij break; 588294286Sdelphij pos--; 589294286Sdelphij n = n->prev; 590294286Sdelphij } 591294286Sdelphij return (pos); 592294286Sdelphij} 593294286Sdelphij 594294286Sdelphij 595294286Sdelphij/* 596161478Sdelphij * Should any characters in a specified range be highlighted? 59760786Sps * If nohide is nonzero, don't consider hide_hilite. 59860786Sps */ 59960786Sps public int 600161478Sdelphijis_hilited(pos, epos, nohide, p_matches) 60160786Sps POSITION pos; 60260786Sps POSITION epos; 60360786Sps int nohide; 604161478Sdelphij int *p_matches; 60560786Sps{ 606161478Sdelphij int match; 60760786Sps 608161478Sdelphij if (p_matches != NULL) 609161478Sdelphij *p_matches = 0; 610161478Sdelphij 61163131Sps if (!status_col && 61263131Sps start_attnpos != NULL_POSITION && 61360786Sps pos < end_attnpos && 61460786Sps (epos == NULL_POSITION || epos > start_attnpos)) 61560786Sps /* 61660786Sps * The attn line overlaps this range. 61760786Sps */ 61860786Sps return (1); 61960786Sps 620161478Sdelphij match = is_hilited_range(pos, epos); 621161478Sdelphij if (!match) 622161478Sdelphij return (0); 623161478Sdelphij 624161478Sdelphij if (p_matches != NULL) 625161478Sdelphij /* 626161478Sdelphij * Report matches, even if we're hiding highlights. 627161478Sdelphij */ 628161478Sdelphij *p_matches = 1; 629161478Sdelphij 63060786Sps if (hilite_search == 0) 63160786Sps /* 63260786Sps * Not doing highlighting. 63360786Sps */ 63460786Sps return (0); 63560786Sps 63660786Sps if (!nohide && hide_hilite) 63760786Sps /* 63860786Sps * Highlighting is hidden. 63960786Sps */ 64060786Sps return (0); 64160786Sps 642161478Sdelphij return (1); 64360786Sps} 64460786Sps 64560786Sps/* 646294286Sdelphij * Tree node storage: get the current block of nodes if it has spare 647294286Sdelphij * capacity, or create a new one if not. 648294286Sdelphij */ 649294286Sdelphij static struct hilite_storage* 650294286Sdelphijhlist_getstorage(anchor) 651294286Sdelphij struct hilite_tree *anchor; 652294286Sdelphij{ 653294286Sdelphij int capacity = 1; 654294286Sdelphij struct hilite_storage *s; 655294286Sdelphij 656294286Sdelphij if (anchor->current) 657294286Sdelphij { 658294286Sdelphij if (anchor->current->used < anchor->current->capacity) 659294286Sdelphij return anchor->current; 660294286Sdelphij capacity = anchor->current->capacity * 2; 661294286Sdelphij } 662294286Sdelphij 663294286Sdelphij s = (struct hilite_storage *) ecalloc(1, sizeof(struct hilite_storage)); 664294286Sdelphij s->nodes = (struct hilite_node *) ecalloc(capacity, sizeof(struct hilite_node)); 665294286Sdelphij s->capacity = capacity; 666294286Sdelphij s->used = 0; 667294286Sdelphij s->next = NULL; 668294286Sdelphij if (anchor->current) 669294286Sdelphij anchor->current->next = s; 670294286Sdelphij else 671294286Sdelphij anchor->first = s; 672294286Sdelphij anchor->current = s; 673294286Sdelphij return s; 674294286Sdelphij} 675294286Sdelphij 676294286Sdelphij/* 677294286Sdelphij * Tree node storage: retrieve a new empty node to be inserted into the 678294286Sdelphij * tree. 679294286Sdelphij */ 680294286Sdelphij static struct hilite_node* 681294286Sdelphijhlist_getnode(anchor) 682294286Sdelphij struct hilite_tree *anchor; 683294286Sdelphij{ 684294286Sdelphij struct hilite_storage *s = hlist_getstorage(anchor); 685294286Sdelphij return &s->nodes[s->used++]; 686294286Sdelphij} 687294286Sdelphij 688294286Sdelphij/* 689294286Sdelphij * Rotate the tree left around a pivot node. 690294286Sdelphij */ 691294286Sdelphij static void 692294286Sdelphijhlist_rotate_left(anchor, n) 693294286Sdelphij struct hilite_tree *anchor; 694294286Sdelphij struct hilite_node *n; 695294286Sdelphij{ 696294286Sdelphij struct hilite_node *np = n->parent; 697294286Sdelphij struct hilite_node *nr = n->right; 698294286Sdelphij struct hilite_node *nrl = n->right->left; 699294286Sdelphij 700294286Sdelphij if (np != NULL) 701294286Sdelphij { 702294286Sdelphij if (n == np->left) 703294286Sdelphij np->left = nr; 704294286Sdelphij else 705294286Sdelphij np->right = nr; 706294286Sdelphij } else 707294286Sdelphij { 708294286Sdelphij anchor->root = nr; 709294286Sdelphij } 710294286Sdelphij nr->left = n; 711294286Sdelphij n->right = nrl; 712294286Sdelphij 713294286Sdelphij nr->parent = np; 714294286Sdelphij n->parent = nr; 715294286Sdelphij if (nrl != NULL) 716294286Sdelphij nrl->parent = n; 717294286Sdelphij} 718294286Sdelphij 719294286Sdelphij/* 720294286Sdelphij * Rotate the tree right around a pivot node. 721294286Sdelphij */ 722294286Sdelphij static void 723294286Sdelphijhlist_rotate_right(anchor, n) 724294286Sdelphij struct hilite_tree *anchor; 725294286Sdelphij struct hilite_node *n; 726294286Sdelphij{ 727294286Sdelphij struct hilite_node *np = n->parent; 728294286Sdelphij struct hilite_node *nl = n->left; 729294286Sdelphij struct hilite_node *nlr = n->left->right; 730294286Sdelphij 731294286Sdelphij if (np != NULL) 732294286Sdelphij { 733294286Sdelphij if (n == np->right) 734294286Sdelphij np->right = nl; 735294286Sdelphij else 736294286Sdelphij np->left = nl; 737294286Sdelphij } else 738294286Sdelphij { 739294286Sdelphij anchor->root = nl; 740294286Sdelphij } 741294286Sdelphij nl->right = n; 742294286Sdelphij n->left = nlr; 743294286Sdelphij 744294286Sdelphij nl->parent = np; 745294286Sdelphij n->parent = nl; 746294286Sdelphij if (nlr != NULL) 747294286Sdelphij nlr->parent = n; 748294286Sdelphij} 749294286Sdelphij 750294286Sdelphij 751294286Sdelphij/* 75260786Sps * Add a new hilite to a hilite list. 75360786Sps */ 75460786Sps static void 75560786Spsadd_hilite(anchor, hl) 756294286Sdelphij struct hilite_tree *anchor; 75760786Sps struct hilite *hl; 75860786Sps{ 759294286Sdelphij struct hilite_node *p, *n, *u; 76060786Sps 761294286Sdelphij /* Ignore empty ranges. */ 762294286Sdelphij if (hl->hl_startpos >= hl->hl_endpos) 763294286Sdelphij return; 764294286Sdelphij 765294286Sdelphij p = anchor->root; 766294286Sdelphij 767294286Sdelphij /* Inserting the very first node is trivial. */ 768294286Sdelphij if (p == NULL) 769294286Sdelphij { 770294286Sdelphij n = hlist_getnode(anchor); 771294286Sdelphij n->r = *hl; 772294286Sdelphij anchor->root = n; 773294286Sdelphij anchor->lookaside = n; 774294286Sdelphij return; 775294286Sdelphij } 776294286Sdelphij 77760786Sps /* 778294286Sdelphij * Find our insertion point. If we come across any overlapping 779294286Sdelphij * or adjoining existing ranges, shrink our range and discard 780294286Sdelphij * if it become empty. 78160786Sps */ 782294286Sdelphij for (;;) 78360786Sps { 784294286Sdelphij if (hl->hl_startpos < p->r.hl_startpos) 785294286Sdelphij { 786294286Sdelphij if (hl->hl_endpos > p->r.hl_startpos) 787294286Sdelphij hl->hl_endpos = p->r.hl_startpos; 788294286Sdelphij if (p->left != NULL) 789294286Sdelphij { 790294286Sdelphij p = p->left; 791294286Sdelphij continue; 792294286Sdelphij } 79360786Sps break; 794294286Sdelphij } 795294286Sdelphij if (hl->hl_startpos < p->r.hl_endpos) { 796294286Sdelphij hl->hl_startpos = p->r.hl_endpos; 797294286Sdelphij if (hl->hl_startpos >= hl->hl_endpos) 798294286Sdelphij return; 799294286Sdelphij } 800294286Sdelphij if (p->right != NULL) 801294286Sdelphij { 802294286Sdelphij p = p->right; 803294286Sdelphij continue; 804294286Sdelphij } 805294286Sdelphij break; 80660786Sps } 80760786Sps 80860786Sps /* 809294286Sdelphij * Now we're at the right leaf, again check for contiguous ranges 810294286Sdelphij * and extend the existing node if possible to avoid the 811294286Sdelphij * insertion. Otherwise insert a new node at the leaf. 81260786Sps */ 813294286Sdelphij if (hl->hl_startpos < p->r.hl_startpos) { 814294286Sdelphij if (hl->hl_endpos == p->r.hl_startpos) 815294286Sdelphij { 816294286Sdelphij p->r.hl_startpos = hl->hl_startpos; 817294286Sdelphij return; 818294286Sdelphij } 819294286Sdelphij if (p->prev != NULL && p->prev->r.hl_endpos == hl->hl_startpos) 820294286Sdelphij { 821294286Sdelphij p->prev->r.hl_endpos = hl->hl_endpos; 822294286Sdelphij return; 823294286Sdelphij } 824294286Sdelphij 825294286Sdelphij p->left = n = hlist_getnode(anchor); 826294286Sdelphij n->next = p; 827294286Sdelphij if (p->prev != NULL) 828294286Sdelphij { 829294286Sdelphij n->prev = p->prev; 830294286Sdelphij p->prev->next = n; 831294286Sdelphij } 832294286Sdelphij p->prev = n; 833294286Sdelphij } else { 834294286Sdelphij if (p->r.hl_endpos == hl->hl_startpos) 835294286Sdelphij { 836294286Sdelphij p->r.hl_endpos = hl->hl_endpos; 837294286Sdelphij return; 838294286Sdelphij } 839294286Sdelphij if (p->next != NULL && hl->hl_endpos == p->next->r.hl_startpos) { 840294286Sdelphij p->next->r.hl_startpos = hl->hl_startpos; 841294286Sdelphij return; 842294286Sdelphij } 843294286Sdelphij 844294286Sdelphij p->right = n = hlist_getnode(anchor); 845294286Sdelphij n->prev = p; 846294286Sdelphij if (p->next != NULL) 847294286Sdelphij { 848294286Sdelphij n->next = p->next; 849294286Sdelphij p->next->prev = n; 850294286Sdelphij } 851294286Sdelphij p->next = n; 852294286Sdelphij } 853294286Sdelphij n->parent = p; 854294286Sdelphij n->red = 1; 855294286Sdelphij n->r = *hl; 856294286Sdelphij 857294286Sdelphij /* 858294286Sdelphij * The tree is in the correct order and covers the right ranges 859294286Sdelphij * now, but may have become unbalanced. Rebalance it using the 860294286Sdelphij * standard red-black tree constraints and operations. 861294286Sdelphij */ 862294286Sdelphij for (;;) 86360786Sps { 864294286Sdelphij /* case 1 - current is root, root is always black */ 865294286Sdelphij if (n->parent == NULL) 866294286Sdelphij { 867294286Sdelphij n->red = 0; 868294286Sdelphij break; 869294286Sdelphij } 870294286Sdelphij 871294286Sdelphij /* case 2 - parent is black, we can always be red */ 872294286Sdelphij if (!n->parent->red) 873294286Sdelphij break; 874294286Sdelphij 87560786Sps /* 876294286Sdelphij * constraint: because the root must be black, if our 877294286Sdelphij * parent is red it cannot be the root therefore we must 878294286Sdelphij * have a grandparent 87960786Sps */ 880294286Sdelphij 881294286Sdelphij /* 882294286Sdelphij * case 3 - parent and uncle are red, repaint them black, 883294286Sdelphij * the grandparent red, and start again at the grandparent. 884294286Sdelphij */ 885294286Sdelphij u = n->parent->parent->left; 886294286Sdelphij if (n->parent == u) 887294286Sdelphij u = n->parent->parent->right; 888294286Sdelphij if (u != NULL && u->red) 889294286Sdelphij { 890294286Sdelphij n->parent->red = 0; 891294286Sdelphij u->red = 0; 892294286Sdelphij n = n->parent->parent; 893294286Sdelphij n->red = 1; 894294286Sdelphij continue; 895294286Sdelphij } 896294286Sdelphij 897294286Sdelphij /* 898294286Sdelphij * case 4 - parent is red but uncle is black, parent and 899294286Sdelphij * grandparent on opposite sides. We need to start 900294286Sdelphij * changing the structure now. This and case 5 will shorten 901294286Sdelphij * our branch and lengthen the sibling, between them 902294286Sdelphij * restoring balance. 903294286Sdelphij */ 904294286Sdelphij if (n == n->parent->right && 905294286Sdelphij n->parent == n->parent->parent->left) 906294286Sdelphij { 907294286Sdelphij hlist_rotate_left(anchor, n->parent); 908294286Sdelphij n = n->left; 909294286Sdelphij } else if (n == n->parent->left && 910294286Sdelphij n->parent == n->parent->parent->right) 911294286Sdelphij { 912294286Sdelphij hlist_rotate_right(anchor, n->parent); 913294286Sdelphij n = n->right; 914294286Sdelphij } 915294286Sdelphij 916294286Sdelphij /* 917294286Sdelphij * case 5 - parent is red but uncle is black, parent and 918294286Sdelphij * grandparent on same side 919294286Sdelphij */ 920294286Sdelphij n->parent->red = 0; 921294286Sdelphij n->parent->parent->red = 1; 922294286Sdelphij if (n == n->parent->left) 923294286Sdelphij hlist_rotate_right(anchor, n->parent->parent); 924294286Sdelphij else 925294286Sdelphij hlist_rotate_left(anchor, n->parent->parent); 926294286Sdelphij break; 92760786Sps } 92860786Sps} 92960786Sps 93060786Sps/* 931237613Sdelphij * Hilight every character in a range of displayed characters. 932237613Sdelphij */ 933237613Sdelphij static void 934237613Sdelphijcreate_hilites(linepos, start_index, end_index, chpos) 935237613Sdelphij POSITION linepos; 936237613Sdelphij int start_index; 937237613Sdelphij int end_index; 938237613Sdelphij int *chpos; 939237613Sdelphij{ 940294286Sdelphij struct hilite hl; 941237613Sdelphij int i; 942237613Sdelphij 943237613Sdelphij /* Start the first hilite. */ 944294286Sdelphij hl.hl_startpos = linepos + chpos[start_index]; 945237613Sdelphij 946237613Sdelphij /* 947237613Sdelphij * Step through the displayed chars. 948237613Sdelphij * If the source position (before cvt) of the char is one more 949237613Sdelphij * than the source pos of the previous char (the usual case), 950237613Sdelphij * just increase the size of the current hilite by one. 951237613Sdelphij * Otherwise (there are backspaces or something involved), 952237613Sdelphij * finish the current hilite and start a new one. 953237613Sdelphij */ 954237613Sdelphij for (i = start_index+1; i <= end_index; i++) 955237613Sdelphij { 956237613Sdelphij if (chpos[i] != chpos[i-1] + 1 || i == end_index) 957237613Sdelphij { 958294286Sdelphij hl.hl_endpos = linepos + chpos[i-1] + 1; 959294286Sdelphij add_hilite(&hilite_anchor, &hl); 960237613Sdelphij /* Start new hilite unless this is the last char. */ 961237613Sdelphij if (i < end_index) 962237613Sdelphij { 963294286Sdelphij hl.hl_startpos = linepos + chpos[i]; 964237613Sdelphij } 965237613Sdelphij } 966237613Sdelphij } 967237613Sdelphij} 968237613Sdelphij 969237613Sdelphij/* 97060786Sps * Make a hilite for each string in a physical line which matches 97160786Sps * the current pattern. 97260786Sps * sp,ep delimit the first match already found. 97360786Sps */ 97460786Sps static void 975195941Sdelphijhilite_line(linepos, line, line_len, chpos, sp, ep, cvt_ops) 97660786Sps POSITION linepos; 97760786Sps char *line; 978170259Sdelphij int line_len; 979195941Sdelphij int *chpos; 98060786Sps char *sp; 98160786Sps char *ep; 982128348Stjr int cvt_ops; 98360786Sps{ 98460786Sps char *searchp; 985170259Sdelphij char *line_end = line + line_len; 98660786Sps 98760786Sps /* 98860786Sps * sp and ep delimit the first match in the line. 98960786Sps * Mark the corresponding file positions, then 99060786Sps * look for further matches and mark them. 99160786Sps * {{ This technique, of calling match_pattern on subsequent 99260786Sps * substrings of the line, may mark more than is correct 99360786Sps * if the pattern starts with "^". This bug is fixed 99460786Sps * for those regex functions that accept a notbol parameter 995170259Sdelphij * (currently POSIX, PCRE and V8-with-regexec2). }} 99660786Sps */ 99760786Sps searchp = line; 99860786Sps do { 999294286Sdelphij if (sp == NULL || ep == NULL) 1000294286Sdelphij return; 1001237613Sdelphij create_hilites(linepos, sp-line, ep-line, chpos); 100260786Sps /* 100360786Sps * If we matched more than zero characters, 100460786Sps * move to the first char after the string we matched. 100560786Sps * If we matched zero, just move to the next char. 100660786Sps */ 100760786Sps if (ep > searchp) 100860786Sps searchp = ep; 1009170259Sdelphij else if (searchp != line_end) 101060786Sps searchp++; 101160786Sps else /* end of line */ 101260786Sps break; 1013237613Sdelphij } while (match_pattern(info_compiled(&search_info), search_info.text, 1014195941Sdelphij searchp, line_end - searchp, &sp, &ep, 1, search_info.search_type)); 101560786Sps} 101660786Sps#endif 101760786Sps 101860786Sps/* 101960786Sps * Change the caseless-ness of searches. 102060786Sps * Updates the internal search state to reflect a change in the -i flag. 102160786Sps */ 102260786Sps public void 102360786Spschg_caseless() 102460786Sps{ 102560786Sps if (!is_ucase_pattern) 102660786Sps /* 102760786Sps * Pattern did not have uppercase. 102860786Sps * Just set the search caselessness to the global caselessness. 102960786Sps */ 103060786Sps is_caseless = caseless; 103160786Sps else 103260786Sps /* 103360786Sps * Pattern did have uppercase. 103460786Sps * Discard the pattern; we can't change search caselessness now. 103560786Sps */ 1036195941Sdelphij clear_pattern(&search_info); 103760786Sps} 103860786Sps 103960786Sps#if HILITE_SEARCH 104060786Sps/* 104160786Sps * Find matching text which is currently on screen and highlight it. 104260786Sps */ 104360786Sps static void 104460786Spshilite_screen() 104560786Sps{ 104660786Sps struct scrpos scrpos; 104760786Sps 104860786Sps get_scrpos(&scrpos); 104960786Sps if (scrpos.pos == NULL_POSITION) 105060786Sps return; 105160786Sps prep_hilite(scrpos.pos, position(BOTTOM_PLUS_ONE), -1); 105260786Sps repaint_hilite(1); 105360786Sps} 105460786Sps 105560786Sps/* 105660786Sps * Change highlighting parameters. 105760786Sps */ 105860786Sps public void 105960786Spschg_hilite() 106060786Sps{ 106160786Sps /* 106260786Sps * Erase any highlights currently on screen. 106360786Sps */ 106460786Sps clr_hilite(); 106560786Sps hide_hilite = 0; 106660786Sps 106760786Sps if (hilite_search == OPT_ONPLUS) 106860786Sps /* 106960786Sps * Display highlights. 107060786Sps */ 107160786Sps hilite_screen(); 107260786Sps} 107360786Sps#endif 107460786Sps 107560786Sps/* 107660786Sps * Figure out where to start a search. 107760786Sps */ 107860786Sps static POSITION 107960786Spssearch_pos(search_type) 108060786Sps int search_type; 108160786Sps{ 108260786Sps POSITION pos; 108360786Sps int linenum; 108460786Sps 108560786Sps if (empty_screen()) 108660786Sps { 108760786Sps /* 108860786Sps * Start at the beginning (or end) of the file. 108960786Sps * The empty_screen() case is mainly for 109060786Sps * command line initiated searches; 109160786Sps * for example, "+/xyz" on the command line. 109260786Sps * Also for multi-file (SRCH_PAST_EOF) searches. 109360786Sps */ 109460786Sps if (search_type & SRCH_FORW) 109560786Sps { 1096221715Sdelphij pos = ch_zero(); 109760786Sps } else 109860786Sps { 109960786Sps pos = ch_length(); 110060786Sps if (pos == NULL_POSITION) 110160786Sps { 110260786Sps (void) ch_end_seek(); 110360786Sps pos = ch_length(); 110460786Sps } 110560786Sps } 1106221715Sdelphij linenum = 0; 1107221715Sdelphij } else 110860786Sps { 1109221715Sdelphij int add_one = 0; 1110221715Sdelphij 1111221715Sdelphij if (how_search == OPT_ON) 111260786Sps { 1113221715Sdelphij /* 1114221715Sdelphij * Search does not include current screen. 1115221715Sdelphij */ 1116221715Sdelphij if (search_type & SRCH_FORW) 1117221715Sdelphij linenum = BOTTOM_PLUS_ONE; 1118221715Sdelphij else 1119221715Sdelphij linenum = TOP; 1120221715Sdelphij } else if (how_search == OPT_ONPLUS && !(search_type & SRCH_AFTER_TARGET)) 1121221715Sdelphij { 1122221715Sdelphij /* 1123221715Sdelphij * Search includes all of displayed screen. 1124221715Sdelphij */ 1125221715Sdelphij if (search_type & SRCH_FORW) 1126221715Sdelphij linenum = TOP; 1127221715Sdelphij else 1128221715Sdelphij linenum = BOTTOM_PLUS_ONE; 112960786Sps } else 113060786Sps { 1131221715Sdelphij /* 1132221715Sdelphij * Search includes the part of current screen beyond the jump target. 1133221715Sdelphij * It starts at the jump target (if searching backwards), 1134221715Sdelphij * or at the jump target plus one (if forwards). 1135221715Sdelphij */ 1136294286Sdelphij linenum = adjsline(jump_sline); 1137221715Sdelphij if (search_type & SRCH_FORW) 1138294286Sdelphij add_one = 1; 113960786Sps } 1140221715Sdelphij pos = position(linenum); 1141221715Sdelphij if (add_one) 1142221715Sdelphij pos = forw_raw_line(pos, (char **)NULL, (int *)NULL); 114360786Sps } 1144221715Sdelphij 1145221715Sdelphij /* 1146221715Sdelphij * If the line is empty, look around for a plausible starting place. 1147221715Sdelphij */ 1148221715Sdelphij if (search_type & SRCH_FORW) 1149221715Sdelphij { 1150294286Sdelphij while (pos == NULL_POSITION) 1151294286Sdelphij { 1152294286Sdelphij if (++linenum >= sc_height) 1153294286Sdelphij break; 1154294286Sdelphij pos = position(linenum); 1155294286Sdelphij } 1156221715Sdelphij } else 1157221715Sdelphij { 1158294286Sdelphij while (pos == NULL_POSITION) 1159294286Sdelphij { 1160294286Sdelphij if (--linenum < 0) 1161294286Sdelphij break; 1162294286Sdelphij pos = position(linenum); 1163294286Sdelphij } 1164221715Sdelphij } 116560786Sps return (pos); 116660786Sps} 116760786Sps 116860786Sps/* 116960786Sps * Search a subset of the file, specified by start/end position. 117060786Sps */ 117160786Sps static int 117260786Spssearch_range(pos, endpos, search_type, matches, maxlines, plinepos, pendpos) 117360786Sps POSITION pos; 117460786Sps POSITION endpos; 117560786Sps int search_type; 117660786Sps int matches; 117760786Sps int maxlines; 117860786Sps POSITION *plinepos; 117960786Sps POSITION *pendpos; 118060786Sps{ 118160786Sps char *line; 1182173685Sdelphij char *cline; 1183170259Sdelphij int line_len; 1184128348Stjr LINENUM linenum; 118560786Sps char *sp, *ep; 118660786Sps int line_match; 1187128348Stjr int cvt_ops; 1188195941Sdelphij int cvt_len; 1189195941Sdelphij int *chpos; 119060786Sps POSITION linepos, oldpos; 119160786Sps 119260786Sps linenum = find_linenum(pos); 119360786Sps oldpos = pos; 119460786Sps for (;;) 119560786Sps { 119660786Sps /* 119760786Sps * Get lines until we find a matching one or until 119860786Sps * we hit end-of-file (or beginning-of-file if we're 119960786Sps * going backwards), or until we hit the end position. 120060786Sps */ 120160786Sps if (ABORT_SIGS()) 120260786Sps { 120360786Sps /* 120460786Sps * A signal aborts the search. 120560786Sps */ 120660786Sps return (-1); 120760786Sps } 120860786Sps 120960786Sps if ((endpos != NULL_POSITION && pos >= endpos) || maxlines == 0) 121060786Sps { 121160786Sps /* 121260786Sps * Reached end position without a match. 121360786Sps */ 121460786Sps if (pendpos != NULL) 121560786Sps *pendpos = pos; 121660786Sps return (matches); 121760786Sps } 121860786Sps if (maxlines > 0) 121960786Sps maxlines--; 122060786Sps 122160786Sps if (search_type & SRCH_FORW) 122260786Sps { 122360786Sps /* 122460786Sps * Read the next line, and save the 122560786Sps * starting position of that line in linepos. 122660786Sps */ 122760786Sps linepos = pos; 1228170259Sdelphij pos = forw_raw_line(pos, &line, &line_len); 122960786Sps if (linenum != 0) 123060786Sps linenum++; 123160786Sps } else 123260786Sps { 123360786Sps /* 123460786Sps * Read the previous line and save the 123560786Sps * starting position of that line in linepos. 123660786Sps */ 1237170259Sdelphij pos = back_raw_line(pos, &line, &line_len); 123860786Sps linepos = pos; 123960786Sps if (linenum != 0) 124060786Sps linenum--; 124160786Sps } 124260786Sps 124360786Sps if (pos == NULL_POSITION) 124460786Sps { 124560786Sps /* 124660786Sps * Reached EOF/BOF without a match. 124760786Sps */ 124860786Sps if (pendpos != NULL) 124960786Sps *pendpos = oldpos; 125060786Sps return (matches); 125160786Sps } 125260786Sps 125360786Sps /* 125460786Sps * If we're using line numbers, we might as well 125560786Sps * remember the information we have now (the position 125660786Sps * and line number of the current line). 125760786Sps * Don't do it for every line because it slows down 125860786Sps * the search. Remember the line number only if 125960786Sps * we're "far" from the last place we remembered it. 126060786Sps */ 1261195941Sdelphij if (linenums && abs((int)(pos - oldpos)) > 2048) 126260786Sps add_lnum(linenum, pos); 126360786Sps oldpos = pos; 126460786Sps 1265191930Sdelphij if (is_filtered(linepos)) 1266191930Sdelphij continue; 1267191930Sdelphij 126860786Sps /* 126960786Sps * If it's a caseless search, convert the line to lowercase. 127060786Sps * If we're doing backspace processing, delete backspaces. 127160786Sps */ 1272128348Stjr cvt_ops = get_cvt_ops(); 1273195941Sdelphij cvt_len = cvt_length(line_len, cvt_ops); 1274195941Sdelphij cline = (char *) ecalloc(1, cvt_len); 1275195941Sdelphij chpos = cvt_alloc_chpos(cvt_len); 1276195941Sdelphij cvt_text(cline, line, chpos, &line_len, cvt_ops); 127760786Sps 1278191930Sdelphij#if HILITE_SEARCH 127960786Sps /* 1280191930Sdelphij * Check to see if the line matches the filter pattern. 1281191930Sdelphij * If so, add an entry to the filter list. 128260786Sps */ 1283294286Sdelphij if (((search_type & SRCH_FIND_ALL) || 1284294286Sdelphij prep_startpos == NULL_POSITION || 1285294286Sdelphij linepos < prep_startpos || linepos >= prep_endpos) && 1286294286Sdelphij prev_pattern(&filter_info)) { 1287237613Sdelphij int line_filter = match_pattern(info_compiled(&filter_info), filter_info.text, 1288195941Sdelphij cline, line_len, &sp, &ep, 0, filter_info.search_type); 1289191930Sdelphij if (line_filter) 1290191930Sdelphij { 1291294286Sdelphij struct hilite hl; 1292294286Sdelphij hl.hl_startpos = linepos; 1293294286Sdelphij hl.hl_endpos = pos; 1294294286Sdelphij add_hilite(&filter_anchor, &hl); 1295294286Sdelphij continue; 1296191930Sdelphij } 1297173685Sdelphij } 1298191930Sdelphij#endif 1299191930Sdelphij 130060786Sps /* 1301191930Sdelphij * Test the next line to see if we have a match. 1302191930Sdelphij * We are successful if we either want a match and got one, 1303191930Sdelphij * or if we want a non-match and got one. 130460786Sps */ 1305195941Sdelphij if (prev_pattern(&search_info)) 130660786Sps { 1307237613Sdelphij line_match = match_pattern(info_compiled(&search_info), search_info.text, 1308221715Sdelphij cline, line_len, &sp, &ep, 0, search_type); 130960786Sps if (line_match) 131060786Sps { 131160786Sps /* 1312191930Sdelphij * Got a match. 131360786Sps */ 1314191930Sdelphij if (search_type & SRCH_FIND_ALL) 1315191930Sdelphij { 1316191930Sdelphij#if HILITE_SEARCH 1317191930Sdelphij /* 1318191930Sdelphij * We are supposed to find all matches in the range. 1319191930Sdelphij * Just add the matches in this line to the 1320191930Sdelphij * hilite list and keep searching. 1321191930Sdelphij */ 1322195941Sdelphij hilite_line(linepos, cline, line_len, chpos, sp, ep, cvt_ops); 1323191930Sdelphij#endif 1324191930Sdelphij } else if (--matches <= 0) 1325191930Sdelphij { 1326191930Sdelphij /* 1327191930Sdelphij * Found the one match we're looking for. 1328191930Sdelphij * Return it. 1329191930Sdelphij */ 1330191930Sdelphij#if HILITE_SEARCH 1331191930Sdelphij if (hilite_search == OPT_ON) 1332191930Sdelphij { 1333191930Sdelphij /* 1334191930Sdelphij * Clear the hilite list and add only 1335191930Sdelphij * the matches in this one line. 1336191930Sdelphij */ 1337191930Sdelphij clr_hilite(); 1338195941Sdelphij hilite_line(linepos, cline, line_len, chpos, sp, ep, cvt_ops); 1339191930Sdelphij } 1340191930Sdelphij#endif 1341191930Sdelphij free(cline); 1342195941Sdelphij free(chpos); 1343191930Sdelphij if (plinepos != NULL) 1344191930Sdelphij *plinepos = linepos; 1345191930Sdelphij return (0); 1346191930Sdelphij } 134760786Sps } 134860786Sps } 1349191930Sdelphij free(cline); 1350195941Sdelphij free(chpos); 135160786Sps } 135260786Sps} 135360786Sps 1354191930Sdelphij/* 1355170259Sdelphij * search for a pattern in history. If found, compile that pattern. 1356170259Sdelphij */ 1357170259Sdelphij static int 1358170259Sdelphijhist_pattern(search_type) 1359170259Sdelphij int search_type; 1360170259Sdelphij{ 1361170259Sdelphij#if CMD_HISTORY 1362170259Sdelphij char *pattern; 1363170259Sdelphij 1364170259Sdelphij set_mlist(ml_search, 0); 1365170259Sdelphij pattern = cmd_lastpattern(); 1366170259Sdelphij if (pattern == NULL) 1367170259Sdelphij return (0); 1368170259Sdelphij 1369195941Sdelphij if (set_pattern(&search_info, pattern, search_type) < 0) 1370170259Sdelphij return (0); 1371170259Sdelphij 1372170259Sdelphij#if HILITE_SEARCH 1373170259Sdelphij if (hilite_search == OPT_ONPLUS && !hide_hilite) 1374170259Sdelphij hilite_screen(); 1375170259Sdelphij#endif 1376170259Sdelphij 1377170259Sdelphij return (1); 1378170259Sdelphij#else /* CMD_HISTORY */ 1379170259Sdelphij return (0); 1380170259Sdelphij#endif /* CMD_HISTORY */ 1381170259Sdelphij} 1382170259Sdelphij 138360786Sps/* 138460786Sps * Search for the n-th occurrence of a specified pattern, 138560786Sps * either forward or backward. 138660786Sps * Return the number of matches not yet found in this file 138760786Sps * (that is, n minus the number of matches found). 138860786Sps * Return -1 if the search should be aborted. 138960786Sps * Caller may continue the search in another file 139060786Sps * if less than n matches are found in this file. 139160786Sps */ 139260786Sps public int 139360786Spssearch(search_type, pattern, n) 139460786Sps int search_type; 139560786Sps char *pattern; 139660786Sps int n; 139760786Sps{ 139860786Sps POSITION pos; 139960786Sps 140060786Sps if (pattern == NULL || *pattern == '\0') 140160786Sps { 140260786Sps /* 140360786Sps * A null pattern means use the previously compiled pattern. 140460786Sps */ 1405221715Sdelphij search_type |= SRCH_AFTER_TARGET; 1406195941Sdelphij if (!prev_pattern(&search_info) && !hist_pattern(search_type)) 140760786Sps { 140860786Sps error("No previous regular expression", NULL_PARG); 140960786Sps return (-1); 141060786Sps } 141160786Sps if ((search_type & SRCH_NO_REGEX) != 1412195941Sdelphij (search_info.search_type & SRCH_NO_REGEX)) 141360786Sps { 141460786Sps error("Please re-enter search pattern", NULL_PARG); 141560786Sps return -1; 141660786Sps } 141760786Sps#if HILITE_SEARCH 141860786Sps if (hilite_search == OPT_ON) 141960786Sps { 142060786Sps /* 142160786Sps * Erase the highlights currently on screen. 142260786Sps * If the search fails, we'll redisplay them later. 142360786Sps */ 142460786Sps repaint_hilite(0); 142560786Sps } 142660786Sps if (hilite_search == OPT_ONPLUS && hide_hilite) 142760786Sps { 142860786Sps /* 142960786Sps * Highlight any matches currently on screen, 143060786Sps * before we actually start the search. 143160786Sps */ 143260786Sps hide_hilite = 0; 143360786Sps hilite_screen(); 143460786Sps } 143560786Sps hide_hilite = 0; 143660786Sps#endif 143760786Sps } else 143860786Sps { 143960786Sps /* 144060786Sps * Compile the pattern. 144160786Sps */ 1442195941Sdelphij if (set_pattern(&search_info, pattern, search_type) < 0) 144360786Sps return (-1); 144460786Sps#if HILITE_SEARCH 144560786Sps if (hilite_search) 144660786Sps { 144760786Sps /* 144860786Sps * Erase the highlights currently on screen. 144960786Sps * Also permanently delete them from the hilite list. 145060786Sps */ 145160786Sps repaint_hilite(0); 145260786Sps hide_hilite = 0; 145360786Sps clr_hilite(); 145460786Sps } 145560786Sps if (hilite_search == OPT_ONPLUS) 145660786Sps { 145760786Sps /* 145860786Sps * Highlight any matches currently on screen, 145960786Sps * before we actually start the search. 146060786Sps */ 146160786Sps hilite_screen(); 146260786Sps } 146360786Sps#endif 146460786Sps } 146560786Sps 146660786Sps /* 146760786Sps * Figure out where to start the search. 146860786Sps */ 146960786Sps pos = search_pos(search_type); 147060786Sps if (pos == NULL_POSITION) 147160786Sps { 147260786Sps /* 147360786Sps * Can't find anyplace to start searching from. 147460786Sps */ 147560786Sps if (search_type & SRCH_PAST_EOF) 147660786Sps return (n); 147760786Sps /* repaint(); -- why was this here? */ 147860786Sps error("Nothing to search", NULL_PARG); 147960786Sps return (-1); 148060786Sps } 148160786Sps 148260786Sps n = search_range(pos, NULL_POSITION, search_type, n, -1, 148360786Sps &pos, (POSITION*)NULL); 148460786Sps if (n != 0) 148560786Sps { 148660786Sps /* 148760786Sps * Search was unsuccessful. 148860786Sps */ 148960786Sps#if HILITE_SEARCH 149060786Sps if (hilite_search == OPT_ON && n > 0) 149160786Sps /* 149260786Sps * Redisplay old hilites. 149360786Sps */ 149460786Sps repaint_hilite(1); 149560786Sps#endif 149660786Sps return (n); 149760786Sps } 149860786Sps 149960786Sps if (!(search_type & SRCH_NO_MOVE)) 150060786Sps { 150160786Sps /* 150260786Sps * Go to the matching line. 150360786Sps */ 150460786Sps jump_loc(pos, jump_sline); 150560786Sps } 150660786Sps 150760786Sps#if HILITE_SEARCH 150860786Sps if (hilite_search == OPT_ON) 150960786Sps /* 151060786Sps * Display new hilites in the matching line. 151160786Sps */ 151260786Sps repaint_hilite(1); 151360786Sps#endif 151460786Sps return (0); 151560786Sps} 151660786Sps 151760786Sps 151860786Sps#if HILITE_SEARCH 151960786Sps/* 152060786Sps * Prepare hilites in a given range of the file. 152160786Sps * 152260786Sps * The pair (prep_startpos,prep_endpos) delimits a contiguous region 152360786Sps * of the file that has been "prepared"; that is, scanned for matches for 152460786Sps * the current search pattern, and hilites have been created for such matches. 152560786Sps * If prep_startpos == NULL_POSITION, the prep region is empty. 152660786Sps * If prep_endpos == NULL_POSITION, the prep region extends to EOF. 152760786Sps * prep_hilite asks that the range (spos,epos) be covered by the prep region. 152860786Sps */ 152960786Sps public void 153060786Spsprep_hilite(spos, epos, maxlines) 153160786Sps POSITION spos; 153260786Sps POSITION epos; 153360786Sps int maxlines; 153460786Sps{ 153560786Sps POSITION nprep_startpos = prep_startpos; 153660786Sps POSITION nprep_endpos = prep_endpos; 153760786Sps POSITION new_epos; 153860786Sps POSITION max_epos; 153960786Sps int result; 154060786Sps int i; 1541195941Sdelphij 154260786Sps/* 154360786Sps * Search beyond where we're asked to search, so the prep region covers 154460786Sps * more than we need. Do one big search instead of a bunch of small ones. 154560786Sps */ 154660786Sps#define SEARCH_MORE (3*size_linebuf) 154760786Sps 1548195941Sdelphij if (!prev_pattern(&search_info) && !is_filtering()) 154960786Sps return; 155060786Sps 155160786Sps /* 1552294286Sdelphij * Make sure our prep region always starts at the beginning of 1553294286Sdelphij * a line. (search_range takes care of the end boundary below.) 1554294286Sdelphij */ 1555294286Sdelphij spos = back_raw_line(spos+1, (char **)NULL, (int *)NULL); 1556294286Sdelphij 1557294286Sdelphij /* 155860786Sps * If we're limited to a max number of lines, figure out the 155960786Sps * file position we should stop at. 156060786Sps */ 156160786Sps if (maxlines < 0) 156260786Sps max_epos = NULL_POSITION; 156360786Sps else 156460786Sps { 156560786Sps max_epos = spos; 156660786Sps for (i = 0; i < maxlines; i++) 1567170259Sdelphij max_epos = forw_raw_line(max_epos, (char **)NULL, (int *)NULL); 156860786Sps } 156960786Sps 157060786Sps /* 157160786Sps * Find two ranges: 157260786Sps * The range that we need to search (spos,epos); and the range that 157360786Sps * the "prep" region will then cover (nprep_startpos,nprep_endpos). 157460786Sps */ 157560786Sps 157660786Sps if (prep_startpos == NULL_POSITION || 157760786Sps (epos != NULL_POSITION && epos < prep_startpos) || 157860786Sps spos > prep_endpos) 157960786Sps { 158060786Sps /* 158160786Sps * New range is not contiguous with old prep region. 158260786Sps * Discard the old prep region and start a new one. 158360786Sps */ 158460786Sps clr_hilite(); 1585191930Sdelphij clr_filter(); 158660786Sps if (epos != NULL_POSITION) 158760786Sps epos += SEARCH_MORE; 158860786Sps nprep_startpos = spos; 158960786Sps } else 159060786Sps { 159160786Sps /* 159260786Sps * New range partially or completely overlaps old prep region. 159360786Sps */ 159460786Sps if (epos == NULL_POSITION) 159560786Sps { 159660786Sps /* 159760786Sps * New range goes to end of file. 159860786Sps */ 159960786Sps ; 160060786Sps } else if (epos > prep_endpos) 160160786Sps { 160260786Sps /* 160360786Sps * New range ends after old prep region. 160460786Sps * Extend prep region to end at end of new range. 160560786Sps */ 160660786Sps epos += SEARCH_MORE; 160760786Sps } else /* (epos <= prep_endpos) */ 160860786Sps { 160960786Sps /* 161060786Sps * New range ends within old prep region. 161160786Sps * Truncate search to end at start of old prep region. 161260786Sps */ 161360786Sps epos = prep_startpos; 161460786Sps } 161560786Sps 161660786Sps if (spos < prep_startpos) 161760786Sps { 161860786Sps /* 161960786Sps * New range starts before old prep region. 162060786Sps * Extend old prep region backwards to start at 162160786Sps * start of new range. 162260786Sps */ 162360786Sps if (spos < SEARCH_MORE) 162460786Sps spos = 0; 162560786Sps else 162660786Sps spos -= SEARCH_MORE; 162760786Sps nprep_startpos = spos; 162860786Sps } else /* (spos >= prep_startpos) */ 162960786Sps { 163060786Sps /* 163160786Sps * New range starts within or after old prep region. 163260786Sps * Trim search to start at end of old prep region. 163360786Sps */ 163460786Sps spos = prep_endpos; 163560786Sps } 163660786Sps } 163760786Sps 163860786Sps if (epos != NULL_POSITION && max_epos != NULL_POSITION && 163960786Sps epos > max_epos) 164060786Sps /* 164160786Sps * Don't go past the max position we're allowed. 164260786Sps */ 164360786Sps epos = max_epos; 164460786Sps 164560786Sps if (epos == NULL_POSITION || epos > spos) 164660786Sps { 1647195941Sdelphij int search_type = SRCH_FORW | SRCH_FIND_ALL; 1648195941Sdelphij search_type |= (search_info.search_type & SRCH_NO_REGEX); 1649294286Sdelphij for (;;) 1650294286Sdelphij { 1651294286Sdelphij result = search_range(spos, epos, search_type, 0, maxlines, (POSITION*)NULL, &new_epos); 1652294286Sdelphij if (result < 0) 1653294286Sdelphij return; 1654294286Sdelphij if (prep_endpos == NULL_POSITION || new_epos > prep_endpos) 1655294286Sdelphij nprep_endpos = new_epos; 1656294286Sdelphij 1657294286Sdelphij /* 1658294286Sdelphij * Check both ends of the resulting prep region to 1659294286Sdelphij * make sure they're not filtered. If they are, 1660294286Sdelphij * keep going at least one more line until we find 1661294286Sdelphij * something that isn't filtered, or hit the end. 1662294286Sdelphij */ 1663294286Sdelphij if (prep_endpos == NULL_POSITION || nprep_endpos > prep_endpos) 1664294286Sdelphij { 1665294286Sdelphij if (new_epos >= nprep_endpos && is_filtered(new_epos-1)) 1666294286Sdelphij { 1667294286Sdelphij spos = nprep_endpos; 1668294286Sdelphij epos = forw_raw_line(nprep_endpos, (char **)NULL, (int *)NULL); 1669294286Sdelphij if (epos == NULL_POSITION) 1670294286Sdelphij break; 1671294286Sdelphij maxlines = 1; 1672294286Sdelphij continue; 1673294286Sdelphij } 1674294286Sdelphij } 1675294286Sdelphij 1676294286Sdelphij if (prep_startpos == NULL_POSITION || nprep_startpos < prep_startpos) 1677294286Sdelphij { 1678294286Sdelphij if (nprep_startpos > 0 && is_filtered(nprep_startpos)) 1679294286Sdelphij { 1680294286Sdelphij epos = nprep_startpos; 1681294286Sdelphij spos = back_raw_line(nprep_startpos, (char **)NULL, (int *)NULL); 1682294286Sdelphij if (spos == NULL_POSITION) 1683294286Sdelphij break; 1684294286Sdelphij nprep_startpos = spos; 1685294286Sdelphij maxlines = 1; 1686294286Sdelphij continue; 1687294286Sdelphij } 1688294286Sdelphij } 1689294286Sdelphij break; 1690294286Sdelphij } 169160786Sps } 169260786Sps prep_startpos = nprep_startpos; 169360786Sps prep_endpos = nprep_endpos; 169460786Sps} 1695191930Sdelphij 1696191930Sdelphij/* 1697191930Sdelphij * Set the pattern to be used for line filtering. 1698191930Sdelphij */ 1699191930Sdelphij public void 1700191930Sdelphijset_filter_pattern(pattern, search_type) 1701191930Sdelphij char *pattern; 1702191930Sdelphij int search_type; 1703191930Sdelphij{ 1704191930Sdelphij clr_filter(); 1705191930Sdelphij if (pattern == NULL || *pattern == '\0') 1706195941Sdelphij clear_pattern(&filter_info); 1707191930Sdelphij else 1708195941Sdelphij set_pattern(&filter_info, pattern, search_type); 1709191930Sdelphij screen_trashed = 1; 1710191930Sdelphij} 1711191930Sdelphij 1712191930Sdelphij/* 1713191930Sdelphij * Is there a line filter in effect? 1714191930Sdelphij */ 1715191930Sdelphij public int 1716191930Sdelphijis_filtering() 1717191930Sdelphij{ 1718191930Sdelphij if (ch_getflags() & CH_HELPFILE) 1719191930Sdelphij return (0); 1720195941Sdelphij return prev_pattern(&filter_info); 1721191930Sdelphij} 172260786Sps#endif 172360786Sps 172460786Sps#if HAVE_V8_REGCOMP 172560786Sps/* 172660786Sps * This function is called by the V8 regcomp to report 172760786Sps * errors in regular expressions. 172860786Sps */ 1729294286Sdelphijpublic int reg_show_error = 1; 1730294286Sdelphij 173160786Sps void 173260786Spsregerror(s) 173360786Sps char *s; 173460786Sps{ 173560786Sps PARG parg; 173660786Sps 1737294286Sdelphij if (!reg_show_error) 1738294286Sdelphij return; 173960786Sps parg.p_string = s; 174060786Sps error("%s", &parg); 174160786Sps} 174260786Sps#endif 174360786Sps 1744