1238730Sdelphij/* 2330571Sdelphij * Copyright (C) 1984-2017 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" 1660786Sps#include "position.h" 17172471Sdelphij#include "charset.h" 1860786Sps 1960786Sps#define MINPOS(a,b) (((a) < (b)) ? (a) : (b)) 2060786Sps#define MAXPOS(a,b) (((a) > (b)) ? (a) : (b)) 2160786Sps 2260786Spsextern int sigs; 2360786Spsextern int how_search; 2460786Spsextern int caseless; 2560786Spsextern int linenums; 2660786Spsextern int sc_height; 2760786Spsextern int jump_sline; 2860786Spsextern int bs_mode; 29128348Stjrextern int ctldisp; 3063131Spsextern int status_col; 31330571Sdelphijextern void *ml_search; 3260786Spsextern POSITION start_attnpos; 3360786Spsextern POSITION end_attnpos; 34191930Sdelphijextern int utf_mode; 35191930Sdelphijextern int screen_trashed; 3660786Sps#if HILITE_SEARCH 3760786Spsextern int hilite_search; 3860786Spsextern int size_linebuf; 3960786Spsextern int squished; 4060786Spsextern int can_goto_line; 4160786Spsstatic int hide_hilite; 4260786Spsstatic POSITION prep_startpos; 4360786Spsstatic POSITION prep_endpos; 44195941Sdelphijstatic int is_caseless; 45195941Sdelphijstatic int is_ucase_pattern; 4660786Sps 47294286Sdelphij/* 48294286Sdelphij * Structures for maintaining a set of ranges for hilites and filtered-out 49294286Sdelphij * lines. Each range is stored as a node within a red-black tree, and we 50294286Sdelphij * try to extend existing ranges (without creating overlaps) rather than 51294286Sdelphij * create new nodes if possible. We remember the last node found by a 52294286Sdelphij * search for constant-time lookup if the next search is near enough to 53294286Sdelphij * the previous. To aid that, we overlay a secondary doubly-linked list 54294286Sdelphij * on top of the red-black tree so we can find the preceding/succeeding 55294286Sdelphij * nodes also in constant time. 56294286Sdelphij * 57294286Sdelphij * Each node is allocated from a series of pools, each pool double the size 58294286Sdelphij * of the previous (for amortised constant time allocation). Since our only 59294286Sdelphij * tree operations are clear and node insertion, not node removal, we don't 60294286Sdelphij * need to maintain a usage bitmap or freelist and can just return nodes 61294286Sdelphij * from the pool in-order until capacity is reached. 62294286Sdelphij */ 6360786Spsstruct hilite 6460786Sps{ 6560786Sps POSITION hl_startpos; 6660786Sps POSITION hl_endpos; 6760786Sps}; 68294286Sdelphijstruct hilite_node 69294286Sdelphij{ 70294286Sdelphij struct hilite_node *parent; 71294286Sdelphij struct hilite_node *left; 72294286Sdelphij struct hilite_node *right; 73294286Sdelphij struct hilite_node *prev; 74294286Sdelphij struct hilite_node *next; 75294286Sdelphij int red; 76294286Sdelphij struct hilite r; 77294286Sdelphij}; 78294286Sdelphijstruct hilite_storage 79294286Sdelphij{ 80294286Sdelphij int capacity; 81294286Sdelphij int used; 82294286Sdelphij struct hilite_storage *next; 83294286Sdelphij struct hilite_node *nodes; 84294286Sdelphij}; 85294286Sdelphijstruct hilite_tree 86294286Sdelphij{ 87294286Sdelphij struct hilite_storage *first; 88294286Sdelphij struct hilite_storage *current; 89294286Sdelphij struct hilite_node *root; 90294286Sdelphij struct hilite_node *lookaside; 91294286Sdelphij}; 92294286Sdelphij#define HILITE_INITIALIZER() { NULL, NULL, NULL, NULL } 93294286Sdelphij#define HILITE_LOOKASIDE_STEPS 2 94294286Sdelphij 95294286Sdelphijstatic struct hilite_tree hilite_anchor = HILITE_INITIALIZER(); 96294286Sdelphijstatic struct hilite_tree filter_anchor = HILITE_INITIALIZER(); 97294286Sdelphij 9860786Sps#endif 9960786Sps 10060786Sps/* 10160786Sps * These are the static variables that represent the "remembered" 102195941Sdelphij * search pattern and filter pattern. 10360786Sps */ 104195941Sdelphijstruct pattern_info { 105330571Sdelphij PATTERN_TYPE compiled; 106195941Sdelphij char* text; 107195941Sdelphij int search_type; 108195941Sdelphij}; 109237613Sdelphij 110237613Sdelphij#if NO_REGEX 111237613Sdelphij#define info_compiled(info) ((void*)0) 112237613Sdelphij#else 113237613Sdelphij#define info_compiled(info) ((info)->compiled) 114237613Sdelphij#endif 115195941Sdelphij 116195941Sdelphijstatic struct pattern_info search_info; 117195941Sdelphijstatic struct pattern_info filter_info; 11860786Sps 119173685Sdelphij/* 120221715Sdelphij * Are there any uppercase letters in this string? 121221715Sdelphij */ 122221715Sdelphij static int 123221715Sdelphijis_ucase(str) 124221715Sdelphij char *str; 125221715Sdelphij{ 126221715Sdelphij char *str_end = str + strlen(str); 127221715Sdelphij LWCHAR ch; 128221715Sdelphij 129221715Sdelphij while (str < str_end) 130221715Sdelphij { 131221715Sdelphij ch = step_char(&str, +1, str_end); 132221715Sdelphij if (IS_UPPER(ch)) 133221715Sdelphij return (1); 134221715Sdelphij } 135221715Sdelphij return (0); 136221715Sdelphij} 137221715Sdelphij 138221715Sdelphij/* 139195941Sdelphij * Compile and save a search pattern. 140173685Sdelphij */ 141173685Sdelphij static int 142195941Sdelphijset_pattern(info, pattern, search_type) 143195941Sdelphij struct pattern_info *info; 144195941Sdelphij char *pattern; 145195941Sdelphij int search_type; 146173685Sdelphij{ 147237613Sdelphij#if !NO_REGEX 148195941Sdelphij if (pattern == NULL) 149237613Sdelphij CLEAR_PATTERN(info->compiled); 150195941Sdelphij else if (compile_pattern(pattern, search_type, &info->compiled) < 0) 151195941Sdelphij return -1; 152237613Sdelphij#endif 153195941Sdelphij /* Pattern compiled successfully; save the text too. */ 154195941Sdelphij if (info->text != NULL) 155195941Sdelphij free(info->text); 156195941Sdelphij info->text = NULL; 157195941Sdelphij if (pattern != NULL) 158195941Sdelphij { 159195941Sdelphij info->text = (char *) ecalloc(1, strlen(pattern)+1); 160195941Sdelphij strcpy(info->text, pattern); 161195941Sdelphij } 162195941Sdelphij info->search_type = search_type; 163221715Sdelphij 164221715Sdelphij /* 165221715Sdelphij * Ignore case if -I is set OR 166221715Sdelphij * -i is set AND the pattern is all lowercase. 167221715Sdelphij */ 168221715Sdelphij is_ucase_pattern = is_ucase(pattern); 169221715Sdelphij if (is_ucase_pattern && caseless != OPT_ONPLUS) 170221715Sdelphij is_caseless = 0; 171221715Sdelphij else 172221715Sdelphij is_caseless = caseless; 173195941Sdelphij return 0; 174173685Sdelphij} 175173685Sdelphij 176173685Sdelphij/* 177195941Sdelphij * Discard a saved pattern. 178173685Sdelphij */ 17960786Sps static void 180195941Sdelphijclear_pattern(info) 181195941Sdelphij struct pattern_info *info; 18260786Sps{ 183195941Sdelphij if (info->text != NULL) 184195941Sdelphij free(info->text); 185195941Sdelphij info->text = NULL; 186237613Sdelphij#if !NO_REGEX 187195941Sdelphij uncompile_pattern(&info->compiled); 188237613Sdelphij#endif 189195941Sdelphij} 19060786Sps 191195941Sdelphij/* 192195941Sdelphij * Initialize saved pattern to nothing. 193195941Sdelphij */ 194195941Sdelphij static void 195195941Sdelphijinit_pattern(info) 196195941Sdelphij struct pattern_info *info; 197195941Sdelphij{ 198195941Sdelphij CLEAR_PATTERN(info->compiled); 199195941Sdelphij info->text = NULL; 200195941Sdelphij info->search_type = 0; 201195941Sdelphij} 202170259Sdelphij 203195941Sdelphij/* 204195941Sdelphij * Initialize search variables. 205195941Sdelphij */ 206195941Sdelphij public void 207195941Sdelphijinit_search() 208195941Sdelphij{ 209195941Sdelphij init_pattern(&search_info); 210195941Sdelphij init_pattern(&filter_info); 21160786Sps} 21260786Sps 21360786Sps/* 214195941Sdelphij * Determine which text conversions to perform before pattern matching. 215128348Stjr */ 216128348Stjr static int 217128348Stjrget_cvt_ops() 218128348Stjr{ 219128348Stjr int ops = 0; 220128348Stjr if (is_caseless || bs_mode == BS_SPECIAL) 221128348Stjr { 222128348Stjr if (is_caseless) 223128348Stjr ops |= CVT_TO_LC; 224128348Stjr if (bs_mode == BS_SPECIAL) 225128348Stjr ops |= CVT_BS; 226128348Stjr if (bs_mode != BS_CONTROL) 227128348Stjr ops |= CVT_CRLF; 228128348Stjr } else if (bs_mode != BS_CONTROL) 229128348Stjr { 230128348Stjr ops |= CVT_CRLF; 231128348Stjr } 232128348Stjr if (ctldisp == OPT_ONPLUS) 233128348Stjr ops |= CVT_ANSI; 234128348Stjr return (ops); 235128348Stjr} 236128348Stjr 237128348Stjr/* 23860786Sps * Is there a previous (remembered) search pattern? 23960786Sps */ 24060786Sps static int 241195941Sdelphijprev_pattern(info) 242195941Sdelphij struct pattern_info *info; 24360786Sps{ 244237613Sdelphij#if !NO_REGEX 245237613Sdelphij if ((info->search_type & SRCH_NO_REGEX) == 0) 246237613Sdelphij return (!is_null_pattern(info->compiled)); 247237613Sdelphij#endif 248237613Sdelphij return (info->text != NULL); 24960786Sps} 25060786Sps 25160786Sps#if HILITE_SEARCH 25260786Sps/* 25360786Sps * Repaint the hilites currently displayed on the screen. 25460786Sps * Repaint each line which contains highlighted text. 25560786Sps * If on==0, force all hilites off. 25660786Sps */ 25760786Sps public void 25860786Spsrepaint_hilite(on) 25960786Sps int on; 26060786Sps{ 261330571Sdelphij int sindex; 26260786Sps POSITION pos; 26360786Sps int save_hide_hilite; 26460786Sps 26560786Sps if (squished) 26660786Sps repaint(); 26760786Sps 26860786Sps save_hide_hilite = hide_hilite; 26960786Sps if (!on) 27060786Sps { 27160786Sps if (hide_hilite) 27260786Sps return; 27360786Sps hide_hilite = 1; 27460786Sps } 27560786Sps 27660786Sps if (!can_goto_line) 27760786Sps { 27860786Sps repaint(); 27960786Sps hide_hilite = save_hide_hilite; 28060786Sps return; 28160786Sps } 28260786Sps 283330571Sdelphij for (sindex = TOP; sindex < TOP + sc_height-1; sindex++) 28460786Sps { 285330571Sdelphij pos = position(sindex); 28660786Sps if (pos == NULL_POSITION) 28760786Sps continue; 288195941Sdelphij (void) forw_line(pos); 289330571Sdelphij goto_line(sindex); 290195941Sdelphij put_line(); 29160786Sps } 292221715Sdelphij lower_left(); 29360786Sps hide_hilite = save_hide_hilite; 29460786Sps} 29560786Sps 29660786Sps/* 29760786Sps * Clear the attn hilite. 29860786Sps */ 29960786Sps public void 30060786Spsclear_attn() 30160786Sps{ 302330571Sdelphij int sindex; 30360786Sps POSITION old_start_attnpos; 30460786Sps POSITION old_end_attnpos; 30560786Sps POSITION pos; 30660786Sps POSITION epos; 307170898Sdelphij int moved = 0; 30860786Sps 30960786Sps if (start_attnpos == NULL_POSITION) 31060786Sps return; 31160786Sps old_start_attnpos = start_attnpos; 31260786Sps old_end_attnpos = end_attnpos; 31360786Sps start_attnpos = end_attnpos = NULL_POSITION; 31460786Sps 31560786Sps if (!can_goto_line) 31660786Sps { 31760786Sps repaint(); 31860786Sps return; 31960786Sps } 32060786Sps if (squished) 32160786Sps repaint(); 32260786Sps 323330571Sdelphij for (sindex = TOP; sindex < TOP + sc_height-1; sindex++) 32460786Sps { 325330571Sdelphij pos = position(sindex); 32660786Sps if (pos == NULL_POSITION) 32760786Sps continue; 328330571Sdelphij epos = position(sindex+1); 329330571Sdelphij if (pos <= old_end_attnpos && 33060786Sps (epos == NULL_POSITION || epos > old_start_attnpos)) 33160786Sps { 33260786Sps (void) forw_line(pos); 333330571Sdelphij goto_line(sindex); 33460786Sps put_line(); 335170898Sdelphij moved = 1; 33660786Sps } 33760786Sps } 338170898Sdelphij if (moved) 339170898Sdelphij lower_left(); 34060786Sps} 34160786Sps#endif 34260786Sps 34360786Sps/* 34460786Sps * Hide search string highlighting. 34560786Sps */ 34660786Sps public void 34760786Spsundo_search() 34860786Sps{ 349195941Sdelphij if (!prev_pattern(&search_info)) 35060786Sps { 351330571Sdelphij if (hilite_anchor.first == NULL) 352330571Sdelphij { 353330571Sdelphij error("No previous regular expression", NULL_PARG); 354330571Sdelphij return; 355330571Sdelphij } 356330571Sdelphij clr_hilite(); /* Next time, hilite_anchor.first will be NULL. */ 35760786Sps } 358330571Sdelphij clear_pattern(&search_info); 35960786Sps#if HILITE_SEARCH 36060786Sps hide_hilite = !hide_hilite; 36160786Sps repaint_hilite(1); 36260786Sps#endif 36360786Sps} 36460786Sps 36560786Sps#if HILITE_SEARCH 36660786Sps/* 36760786Sps * Clear the hilite list. 36860786Sps */ 36960786Sps public void 370191930Sdelphijclr_hlist(anchor) 371294286Sdelphij struct hilite_tree *anchor; 37260786Sps{ 373294286Sdelphij struct hilite_storage *hls; 374294286Sdelphij struct hilite_storage *nexthls; 37560786Sps 376294286Sdelphij for (hls = anchor->first; hls != NULL; hls = nexthls) 37760786Sps { 378294286Sdelphij nexthls = hls->next; 379294286Sdelphij free((void*)hls->nodes); 380294286Sdelphij free((void*)hls); 38160786Sps } 382294286Sdelphij anchor->first = NULL; 383294286Sdelphij anchor->current = NULL; 384294286Sdelphij anchor->root = NULL; 385294286Sdelphij 386294286Sdelphij anchor->lookaside = NULL; 387294286Sdelphij 38860786Sps prep_startpos = prep_endpos = NULL_POSITION; 38960786Sps} 39060786Sps 391191930Sdelphij public void 392191930Sdelphijclr_hilite() 393191930Sdelphij{ 394191930Sdelphij clr_hlist(&hilite_anchor); 395191930Sdelphij} 396191930Sdelphij 397191930Sdelphij public void 398191930Sdelphijclr_filter() 399191930Sdelphij{ 400191930Sdelphij clr_hlist(&filter_anchor); 401191930Sdelphij} 402191930Sdelphij 403294286Sdelphij struct hilite_node* 404294286Sdelphijhlist_last(anchor) 405294286Sdelphij struct hilite_tree *anchor; 406294286Sdelphij{ 407294286Sdelphij struct hilite_node *n = anchor->root; 408294286Sdelphij while (n != NULL && n->right != NULL) 409294286Sdelphij n = n->right; 410294286Sdelphij return n; 411294286Sdelphij} 412294286Sdelphij 413294286Sdelphij struct hilite_node* 414294286Sdelphijhlist_next(n) 415294286Sdelphij struct hilite_node *n; 416294286Sdelphij{ 417294286Sdelphij return n->next; 418294286Sdelphij} 419294286Sdelphij 420294286Sdelphij struct hilite_node* 421294286Sdelphijhlist_prev(n) 422294286Sdelphij struct hilite_node *n; 423294286Sdelphij{ 424294286Sdelphij return n->prev; 425294286Sdelphij} 426294286Sdelphij 42760786Sps/* 428294286Sdelphij * Find the node covering pos, or the node after it if no node covers it, 429294286Sdelphij * or return NULL if pos is after the last range. Remember the found node, 430294286Sdelphij * to speed up subsequent searches for the same or similar positions (if 431294286Sdelphij * we return NULL, remember the last node.) 432294286Sdelphij */ 433294286Sdelphij struct hilite_node* 434294286Sdelphijhlist_find(anchor, pos) 435294286Sdelphij struct hilite_tree *anchor; 436294286Sdelphij POSITION pos; 437294286Sdelphij{ 438294286Sdelphij struct hilite_node *n, *m; 439294286Sdelphij 440294286Sdelphij if (anchor->lookaside) 441294286Sdelphij { 442294286Sdelphij int steps = 0; 443294286Sdelphij int hit = 0; 444294286Sdelphij 445294286Sdelphij n = anchor->lookaside; 446294286Sdelphij 447294286Sdelphij for (;;) 448294286Sdelphij { 449294286Sdelphij if (pos < n->r.hl_endpos) 450294286Sdelphij { 451294286Sdelphij if (n->prev == NULL || pos >= n->prev->r.hl_endpos) 452294286Sdelphij { 453294286Sdelphij hit = 1; 454294286Sdelphij break; 455294286Sdelphij } 456294286Sdelphij } else if (n->next == NULL) 457294286Sdelphij { 458294286Sdelphij n = NULL; 459294286Sdelphij hit = 1; 460294286Sdelphij break; 461294286Sdelphij } 462294286Sdelphij 463294286Sdelphij /* 464294286Sdelphij * If we don't find the right node within a small 465294286Sdelphij * distance, don't keep doing a linear search! 466294286Sdelphij */ 467294286Sdelphij if (steps >= HILITE_LOOKASIDE_STEPS) 468294286Sdelphij break; 469294286Sdelphij steps++; 470294286Sdelphij 471294286Sdelphij if (pos < n->r.hl_endpos) 472294286Sdelphij anchor->lookaside = n = n->prev; 473294286Sdelphij else 474294286Sdelphij anchor->lookaside = n = n->next; 475294286Sdelphij } 476294286Sdelphij 477294286Sdelphij if (hit) 478294286Sdelphij return n; 479294286Sdelphij } 480294286Sdelphij 481294286Sdelphij n = anchor->root; 482294286Sdelphij m = NULL; 483294286Sdelphij 484294286Sdelphij while (n != NULL) 485294286Sdelphij { 486294286Sdelphij if (pos < n->r.hl_startpos) 487294286Sdelphij { 488294286Sdelphij if (n->left != NULL) 489294286Sdelphij { 490294286Sdelphij m = n; 491294286Sdelphij n = n->left; 492294286Sdelphij continue; 493294286Sdelphij } 494294286Sdelphij break; 495294286Sdelphij } 496294286Sdelphij if (pos >= n->r.hl_endpos) 497294286Sdelphij { 498294286Sdelphij if (n->right != NULL) 499294286Sdelphij { 500294286Sdelphij n = n->right; 501294286Sdelphij continue; 502294286Sdelphij } 503294286Sdelphij if (m != NULL) 504294286Sdelphij { 505294286Sdelphij n = m; 506294286Sdelphij } else 507294286Sdelphij { 508294286Sdelphij m = n; 509294286Sdelphij n = NULL; 510294286Sdelphij } 511294286Sdelphij } 512294286Sdelphij break; 513294286Sdelphij } 514294286Sdelphij 515294286Sdelphij if (n != NULL) 516294286Sdelphij anchor->lookaside = n; 517294286Sdelphij else if (m != NULL) 518294286Sdelphij anchor->lookaside = m; 519294286Sdelphij 520294286Sdelphij return n; 521294286Sdelphij} 522294286Sdelphij 523294286Sdelphij/* 52460786Sps * Should any characters in a specified range be highlighted? 525161478Sdelphij */ 526161478Sdelphij static int 527161478Sdelphijis_hilited_range(pos, epos) 528161478Sdelphij POSITION pos; 529161478Sdelphij POSITION epos; 530161478Sdelphij{ 531294286Sdelphij struct hilite_node *n = hlist_find(&hilite_anchor, pos); 532294286Sdelphij return (n != NULL && (epos == NULL_POSITION || epos > n->r.hl_startpos)); 533161478Sdelphij} 534161478Sdelphij 535191930Sdelphij/* 536191930Sdelphij * Is a line "filtered" -- that is, should it be hidden? 537191930Sdelphij */ 538191930Sdelphij public int 539191930Sdelphijis_filtered(pos) 540191930Sdelphij POSITION pos; 541191930Sdelphij{ 542294286Sdelphij struct hilite_node *n; 543191930Sdelphij 544191930Sdelphij if (ch_getflags() & CH_HELPFILE) 545191930Sdelphij return (0); 546191930Sdelphij 547294286Sdelphij n = hlist_find(&filter_anchor, pos); 548294286Sdelphij return (n != NULL && pos >= n->r.hl_startpos); 549294286Sdelphij} 550294286Sdelphij 551294286Sdelphij/* 552294286Sdelphij * If pos is hidden, return the next position which isn't, otherwise 553294286Sdelphij * just return pos. 554294286Sdelphij */ 555294286Sdelphij public POSITION 556294286Sdelphijnext_unfiltered(pos) 557294286Sdelphij POSITION pos; 558294286Sdelphij{ 559294286Sdelphij struct hilite_node *n; 560294286Sdelphij 561294286Sdelphij if (ch_getflags() & CH_HELPFILE) 562294286Sdelphij return (pos); 563294286Sdelphij 564294286Sdelphij n = hlist_find(&filter_anchor, pos); 565294286Sdelphij while (n != NULL && pos >= n->r.hl_startpos) 566191930Sdelphij { 567294286Sdelphij pos = n->r.hl_endpos; 568294286Sdelphij n = n->next; 569191930Sdelphij } 570294286Sdelphij return (pos); 571191930Sdelphij} 572191930Sdelphij 573161478Sdelphij/* 574294286Sdelphij * If pos is hidden, return the previous position which isn't or 0 if 575294286Sdelphij * we're filtered right to the beginning, otherwise just return pos. 576294286Sdelphij */ 577294286Sdelphij public POSITION 578294286Sdelphijprev_unfiltered(pos) 579294286Sdelphij POSITION pos; 580294286Sdelphij{ 581294286Sdelphij struct hilite_node *n; 582294286Sdelphij 583294286Sdelphij if (ch_getflags() & CH_HELPFILE) 584294286Sdelphij return (pos); 585294286Sdelphij 586294286Sdelphij n = hlist_find(&filter_anchor, pos); 587294286Sdelphij while (n != NULL && pos >= n->r.hl_startpos) 588294286Sdelphij { 589294286Sdelphij pos = n->r.hl_startpos; 590294286Sdelphij if (pos == 0) 591294286Sdelphij break; 592294286Sdelphij pos--; 593294286Sdelphij n = n->prev; 594294286Sdelphij } 595294286Sdelphij return (pos); 596294286Sdelphij} 597294286Sdelphij 598294286Sdelphij 599294286Sdelphij/* 600161478Sdelphij * Should any characters in a specified range be highlighted? 60160786Sps * If nohide is nonzero, don't consider hide_hilite. 60260786Sps */ 60360786Sps public int 604161478Sdelphijis_hilited(pos, epos, nohide, p_matches) 60560786Sps POSITION pos; 60660786Sps POSITION epos; 60760786Sps int nohide; 608161478Sdelphij int *p_matches; 60960786Sps{ 610161478Sdelphij int match; 61160786Sps 612161478Sdelphij if (p_matches != NULL) 613161478Sdelphij *p_matches = 0; 614161478Sdelphij 61563131Sps if (!status_col && 61663131Sps start_attnpos != NULL_POSITION && 61760786Sps pos < end_attnpos && 61860786Sps (epos == NULL_POSITION || epos > start_attnpos)) 61960786Sps /* 62060786Sps * The attn line overlaps this range. 62160786Sps */ 62260786Sps return (1); 62360786Sps 624161478Sdelphij match = is_hilited_range(pos, epos); 625161478Sdelphij if (!match) 626161478Sdelphij return (0); 627161478Sdelphij 628330571Sdelphij if (p_matches == NULL) 629161478Sdelphij /* 630330571Sdelphij * Kinda kludgy way to recognize that caller is checking for 631330571Sdelphij * hilite in status column. In this case we want to return 632330571Sdelphij * hilite status even if hiliting is disabled or hidden. 633161478Sdelphij */ 634330571Sdelphij return (1); 635161478Sdelphij 636330571Sdelphij /* 637330571Sdelphij * Report matches, even if we're hiding highlights. 638330571Sdelphij */ 639330571Sdelphij *p_matches = 1; 640330571Sdelphij 64160786Sps if (hilite_search == 0) 64260786Sps /* 64360786Sps * Not doing highlighting. 64460786Sps */ 64560786Sps return (0); 64660786Sps 64760786Sps if (!nohide && hide_hilite) 64860786Sps /* 64960786Sps * Highlighting is hidden. 65060786Sps */ 65160786Sps return (0); 65260786Sps 653161478Sdelphij return (1); 65460786Sps} 65560786Sps 65660786Sps/* 657294286Sdelphij * Tree node storage: get the current block of nodes if it has spare 658294286Sdelphij * capacity, or create a new one if not. 659294286Sdelphij */ 660294286Sdelphij static struct hilite_storage* 661294286Sdelphijhlist_getstorage(anchor) 662294286Sdelphij struct hilite_tree *anchor; 663294286Sdelphij{ 664294286Sdelphij int capacity = 1; 665294286Sdelphij struct hilite_storage *s; 666294286Sdelphij 667294286Sdelphij if (anchor->current) 668294286Sdelphij { 669294286Sdelphij if (anchor->current->used < anchor->current->capacity) 670294286Sdelphij return anchor->current; 671294286Sdelphij capacity = anchor->current->capacity * 2; 672294286Sdelphij } 673294286Sdelphij 674294286Sdelphij s = (struct hilite_storage *) ecalloc(1, sizeof(struct hilite_storage)); 675294286Sdelphij s->nodes = (struct hilite_node *) ecalloc(capacity, sizeof(struct hilite_node)); 676294286Sdelphij s->capacity = capacity; 677294286Sdelphij s->used = 0; 678294286Sdelphij s->next = NULL; 679294286Sdelphij if (anchor->current) 680294286Sdelphij anchor->current->next = s; 681294286Sdelphij else 682294286Sdelphij anchor->first = s; 683294286Sdelphij anchor->current = s; 684294286Sdelphij return s; 685294286Sdelphij} 686294286Sdelphij 687294286Sdelphij/* 688294286Sdelphij * Tree node storage: retrieve a new empty node to be inserted into the 689294286Sdelphij * tree. 690294286Sdelphij */ 691294286Sdelphij static struct hilite_node* 692294286Sdelphijhlist_getnode(anchor) 693294286Sdelphij struct hilite_tree *anchor; 694294286Sdelphij{ 695294286Sdelphij struct hilite_storage *s = hlist_getstorage(anchor); 696294286Sdelphij return &s->nodes[s->used++]; 697294286Sdelphij} 698294286Sdelphij 699294286Sdelphij/* 700294286Sdelphij * Rotate the tree left around a pivot node. 701294286Sdelphij */ 702294286Sdelphij static void 703294286Sdelphijhlist_rotate_left(anchor, n) 704294286Sdelphij struct hilite_tree *anchor; 705294286Sdelphij struct hilite_node *n; 706294286Sdelphij{ 707294286Sdelphij struct hilite_node *np = n->parent; 708294286Sdelphij struct hilite_node *nr = n->right; 709294286Sdelphij struct hilite_node *nrl = n->right->left; 710294286Sdelphij 711294286Sdelphij if (np != NULL) 712294286Sdelphij { 713294286Sdelphij if (n == np->left) 714294286Sdelphij np->left = nr; 715294286Sdelphij else 716294286Sdelphij np->right = nr; 717294286Sdelphij } else 718294286Sdelphij { 719294286Sdelphij anchor->root = nr; 720294286Sdelphij } 721294286Sdelphij nr->left = n; 722294286Sdelphij n->right = nrl; 723294286Sdelphij 724294286Sdelphij nr->parent = np; 725294286Sdelphij n->parent = nr; 726294286Sdelphij if (nrl != NULL) 727294286Sdelphij nrl->parent = n; 728294286Sdelphij} 729294286Sdelphij 730294286Sdelphij/* 731294286Sdelphij * Rotate the tree right around a pivot node. 732294286Sdelphij */ 733294286Sdelphij static void 734294286Sdelphijhlist_rotate_right(anchor, n) 735294286Sdelphij struct hilite_tree *anchor; 736294286Sdelphij struct hilite_node *n; 737294286Sdelphij{ 738294286Sdelphij struct hilite_node *np = n->parent; 739294286Sdelphij struct hilite_node *nl = n->left; 740294286Sdelphij struct hilite_node *nlr = n->left->right; 741294286Sdelphij 742294286Sdelphij if (np != NULL) 743294286Sdelphij { 744294286Sdelphij if (n == np->right) 745294286Sdelphij np->right = nl; 746294286Sdelphij else 747294286Sdelphij np->left = nl; 748294286Sdelphij } else 749294286Sdelphij { 750294286Sdelphij anchor->root = nl; 751294286Sdelphij } 752294286Sdelphij nl->right = n; 753294286Sdelphij n->left = nlr; 754294286Sdelphij 755294286Sdelphij nl->parent = np; 756294286Sdelphij n->parent = nl; 757294286Sdelphij if (nlr != NULL) 758294286Sdelphij nlr->parent = n; 759294286Sdelphij} 760294286Sdelphij 761294286Sdelphij 762294286Sdelphij/* 76360786Sps * Add a new hilite to a hilite list. 76460786Sps */ 76560786Sps static void 76660786Spsadd_hilite(anchor, hl) 767294286Sdelphij struct hilite_tree *anchor; 76860786Sps struct hilite *hl; 76960786Sps{ 770294286Sdelphij struct hilite_node *p, *n, *u; 77160786Sps 772294286Sdelphij /* Ignore empty ranges. */ 773294286Sdelphij if (hl->hl_startpos >= hl->hl_endpos) 774294286Sdelphij return; 775294286Sdelphij 776294286Sdelphij p = anchor->root; 777294286Sdelphij 778294286Sdelphij /* Inserting the very first node is trivial. */ 779294286Sdelphij if (p == NULL) 780294286Sdelphij { 781294286Sdelphij n = hlist_getnode(anchor); 782294286Sdelphij n->r = *hl; 783294286Sdelphij anchor->root = n; 784294286Sdelphij anchor->lookaside = n; 785294286Sdelphij return; 786294286Sdelphij } 787294286Sdelphij 78860786Sps /* 789294286Sdelphij * Find our insertion point. If we come across any overlapping 790294286Sdelphij * or adjoining existing ranges, shrink our range and discard 791294286Sdelphij * if it become empty. 79260786Sps */ 793294286Sdelphij for (;;) 79460786Sps { 795294286Sdelphij if (hl->hl_startpos < p->r.hl_startpos) 796294286Sdelphij { 797294286Sdelphij if (hl->hl_endpos > p->r.hl_startpos) 798294286Sdelphij hl->hl_endpos = p->r.hl_startpos; 799294286Sdelphij if (p->left != NULL) 800294286Sdelphij { 801294286Sdelphij p = p->left; 802294286Sdelphij continue; 803294286Sdelphij } 80460786Sps break; 805294286Sdelphij } 806294286Sdelphij if (hl->hl_startpos < p->r.hl_endpos) { 807294286Sdelphij hl->hl_startpos = p->r.hl_endpos; 808294286Sdelphij if (hl->hl_startpos >= hl->hl_endpos) 809294286Sdelphij return; 810294286Sdelphij } 811294286Sdelphij if (p->right != NULL) 812294286Sdelphij { 813294286Sdelphij p = p->right; 814294286Sdelphij continue; 815294286Sdelphij } 816294286Sdelphij break; 81760786Sps } 81860786Sps 81960786Sps /* 820294286Sdelphij * Now we're at the right leaf, again check for contiguous ranges 821294286Sdelphij * and extend the existing node if possible to avoid the 822294286Sdelphij * insertion. Otherwise insert a new node at the leaf. 82360786Sps */ 824294286Sdelphij if (hl->hl_startpos < p->r.hl_startpos) { 825294286Sdelphij if (hl->hl_endpos == p->r.hl_startpos) 826294286Sdelphij { 827294286Sdelphij p->r.hl_startpos = hl->hl_startpos; 828294286Sdelphij return; 829294286Sdelphij } 830294286Sdelphij if (p->prev != NULL && p->prev->r.hl_endpos == hl->hl_startpos) 831294286Sdelphij { 832294286Sdelphij p->prev->r.hl_endpos = hl->hl_endpos; 833294286Sdelphij return; 834294286Sdelphij } 835294286Sdelphij 836294286Sdelphij p->left = n = hlist_getnode(anchor); 837294286Sdelphij n->next = p; 838294286Sdelphij if (p->prev != NULL) 839294286Sdelphij { 840294286Sdelphij n->prev = p->prev; 841294286Sdelphij p->prev->next = n; 842294286Sdelphij } 843294286Sdelphij p->prev = n; 844294286Sdelphij } else { 845294286Sdelphij if (p->r.hl_endpos == hl->hl_startpos) 846294286Sdelphij { 847294286Sdelphij p->r.hl_endpos = hl->hl_endpos; 848294286Sdelphij return; 849294286Sdelphij } 850294286Sdelphij if (p->next != NULL && hl->hl_endpos == p->next->r.hl_startpos) { 851294286Sdelphij p->next->r.hl_startpos = hl->hl_startpos; 852294286Sdelphij return; 853294286Sdelphij } 854294286Sdelphij 855294286Sdelphij p->right = n = hlist_getnode(anchor); 856294286Sdelphij n->prev = p; 857294286Sdelphij if (p->next != NULL) 858294286Sdelphij { 859294286Sdelphij n->next = p->next; 860294286Sdelphij p->next->prev = n; 861294286Sdelphij } 862294286Sdelphij p->next = n; 863294286Sdelphij } 864294286Sdelphij n->parent = p; 865294286Sdelphij n->red = 1; 866294286Sdelphij n->r = *hl; 867294286Sdelphij 868294286Sdelphij /* 869294286Sdelphij * The tree is in the correct order and covers the right ranges 870294286Sdelphij * now, but may have become unbalanced. Rebalance it using the 871294286Sdelphij * standard red-black tree constraints and operations. 872294286Sdelphij */ 873294286Sdelphij for (;;) 87460786Sps { 875294286Sdelphij /* case 1 - current is root, root is always black */ 876294286Sdelphij if (n->parent == NULL) 877294286Sdelphij { 878294286Sdelphij n->red = 0; 879294286Sdelphij break; 880294286Sdelphij } 881294286Sdelphij 882294286Sdelphij /* case 2 - parent is black, we can always be red */ 883294286Sdelphij if (!n->parent->red) 884294286Sdelphij break; 885294286Sdelphij 88660786Sps /* 887294286Sdelphij * constraint: because the root must be black, if our 888294286Sdelphij * parent is red it cannot be the root therefore we must 889294286Sdelphij * have a grandparent 89060786Sps */ 891294286Sdelphij 892294286Sdelphij /* 893294286Sdelphij * case 3 - parent and uncle are red, repaint them black, 894294286Sdelphij * the grandparent red, and start again at the grandparent. 895294286Sdelphij */ 896294286Sdelphij u = n->parent->parent->left; 897294286Sdelphij if (n->parent == u) 898294286Sdelphij u = n->parent->parent->right; 899294286Sdelphij if (u != NULL && u->red) 900294286Sdelphij { 901294286Sdelphij n->parent->red = 0; 902294286Sdelphij u->red = 0; 903294286Sdelphij n = n->parent->parent; 904294286Sdelphij n->red = 1; 905294286Sdelphij continue; 906294286Sdelphij } 907294286Sdelphij 908294286Sdelphij /* 909294286Sdelphij * case 4 - parent is red but uncle is black, parent and 910294286Sdelphij * grandparent on opposite sides. We need to start 911294286Sdelphij * changing the structure now. This and case 5 will shorten 912294286Sdelphij * our branch and lengthen the sibling, between them 913294286Sdelphij * restoring balance. 914294286Sdelphij */ 915294286Sdelphij if (n == n->parent->right && 916294286Sdelphij n->parent == n->parent->parent->left) 917294286Sdelphij { 918294286Sdelphij hlist_rotate_left(anchor, n->parent); 919294286Sdelphij n = n->left; 920294286Sdelphij } else if (n == n->parent->left && 921294286Sdelphij n->parent == n->parent->parent->right) 922294286Sdelphij { 923294286Sdelphij hlist_rotate_right(anchor, n->parent); 924294286Sdelphij n = n->right; 925294286Sdelphij } 926294286Sdelphij 927294286Sdelphij /* 928294286Sdelphij * case 5 - parent is red but uncle is black, parent and 929294286Sdelphij * grandparent on same side 930294286Sdelphij */ 931294286Sdelphij n->parent->red = 0; 932294286Sdelphij n->parent->parent->red = 1; 933294286Sdelphij if (n == n->parent->left) 934294286Sdelphij hlist_rotate_right(anchor, n->parent->parent); 935294286Sdelphij else 936294286Sdelphij hlist_rotate_left(anchor, n->parent->parent); 937294286Sdelphij break; 93860786Sps } 93960786Sps} 94060786Sps 94160786Sps/* 942237613Sdelphij * Hilight every character in a range of displayed characters. 943237613Sdelphij */ 944237613Sdelphij static void 945237613Sdelphijcreate_hilites(linepos, start_index, end_index, chpos) 946237613Sdelphij POSITION linepos; 947237613Sdelphij int start_index; 948237613Sdelphij int end_index; 949237613Sdelphij int *chpos; 950237613Sdelphij{ 951294286Sdelphij struct hilite hl; 952237613Sdelphij int i; 953237613Sdelphij 954237613Sdelphij /* Start the first hilite. */ 955294286Sdelphij hl.hl_startpos = linepos + chpos[start_index]; 956237613Sdelphij 957237613Sdelphij /* 958237613Sdelphij * Step through the displayed chars. 959237613Sdelphij * If the source position (before cvt) of the char is one more 960237613Sdelphij * than the source pos of the previous char (the usual case), 961237613Sdelphij * just increase the size of the current hilite by one. 962237613Sdelphij * Otherwise (there are backspaces or something involved), 963237613Sdelphij * finish the current hilite and start a new one. 964237613Sdelphij */ 965237613Sdelphij for (i = start_index+1; i <= end_index; i++) 966237613Sdelphij { 967237613Sdelphij if (chpos[i] != chpos[i-1] + 1 || i == end_index) 968237613Sdelphij { 969294286Sdelphij hl.hl_endpos = linepos + chpos[i-1] + 1; 970294286Sdelphij add_hilite(&hilite_anchor, &hl); 971237613Sdelphij /* Start new hilite unless this is the last char. */ 972237613Sdelphij if (i < end_index) 973237613Sdelphij { 974294286Sdelphij hl.hl_startpos = linepos + chpos[i]; 975237613Sdelphij } 976237613Sdelphij } 977237613Sdelphij } 978237613Sdelphij} 979237613Sdelphij 980237613Sdelphij/* 98160786Sps * Make a hilite for each string in a physical line which matches 98260786Sps * the current pattern. 98360786Sps * sp,ep delimit the first match already found. 98460786Sps */ 98560786Sps static void 986195941Sdelphijhilite_line(linepos, line, line_len, chpos, sp, ep, cvt_ops) 98760786Sps POSITION linepos; 98860786Sps char *line; 989170259Sdelphij int line_len; 990195941Sdelphij int *chpos; 99160786Sps char *sp; 99260786Sps char *ep; 993128348Stjr int cvt_ops; 99460786Sps{ 99560786Sps char *searchp; 996170259Sdelphij char *line_end = line + line_len; 99760786Sps 99860786Sps /* 99960786Sps * sp and ep delimit the first match in the line. 100060786Sps * Mark the corresponding file positions, then 100160786Sps * look for further matches and mark them. 100260786Sps * {{ This technique, of calling match_pattern on subsequent 100360786Sps * substrings of the line, may mark more than is correct 100460786Sps * if the pattern starts with "^". This bug is fixed 100560786Sps * for those regex functions that accept a notbol parameter 1006170259Sdelphij * (currently POSIX, PCRE and V8-with-regexec2). }} 100760786Sps */ 100860786Sps searchp = line; 100960786Sps do { 1010294286Sdelphij if (sp == NULL || ep == NULL) 1011294286Sdelphij return; 1012237613Sdelphij create_hilites(linepos, sp-line, ep-line, chpos); 101360786Sps /* 101460786Sps * If we matched more than zero characters, 101560786Sps * move to the first char after the string we matched. 101660786Sps * If we matched zero, just move to the next char. 101760786Sps */ 101860786Sps if (ep > searchp) 101960786Sps searchp = ep; 1020170259Sdelphij else if (searchp != line_end) 102160786Sps searchp++; 102260786Sps else /* end of line */ 102360786Sps break; 1024237613Sdelphij } while (match_pattern(info_compiled(&search_info), search_info.text, 1025195941Sdelphij searchp, line_end - searchp, &sp, &ep, 1, search_info.search_type)); 102660786Sps} 102760786Sps#endif 102860786Sps 102960786Sps#if HILITE_SEARCH 103060786Sps/* 103160786Sps * Find matching text which is currently on screen and highlight it. 103260786Sps */ 103360786Sps static void 103460786Spshilite_screen() 103560786Sps{ 103660786Sps struct scrpos scrpos; 103760786Sps 1038330571Sdelphij get_scrpos(&scrpos, TOP); 103960786Sps if (scrpos.pos == NULL_POSITION) 104060786Sps return; 104160786Sps prep_hilite(scrpos.pos, position(BOTTOM_PLUS_ONE), -1); 104260786Sps repaint_hilite(1); 104360786Sps} 104460786Sps 104560786Sps/* 104660786Sps * Change highlighting parameters. 104760786Sps */ 104860786Sps public void 104960786Spschg_hilite() 105060786Sps{ 105160786Sps /* 105260786Sps * Erase any highlights currently on screen. 105360786Sps */ 105460786Sps clr_hilite(); 105560786Sps hide_hilite = 0; 105660786Sps 105760786Sps if (hilite_search == OPT_ONPLUS) 105860786Sps /* 105960786Sps * Display highlights. 106060786Sps */ 106160786Sps hilite_screen(); 106260786Sps} 106360786Sps#endif 106460786Sps 106560786Sps/* 106660786Sps * Figure out where to start a search. 106760786Sps */ 106860786Sps static POSITION 106960786Spssearch_pos(search_type) 107060786Sps int search_type; 107160786Sps{ 107260786Sps POSITION pos; 1073330571Sdelphij int sindex; 107460786Sps 107560786Sps if (empty_screen()) 107660786Sps { 107760786Sps /* 107860786Sps * Start at the beginning (or end) of the file. 107960786Sps * The empty_screen() case is mainly for 108060786Sps * command line initiated searches; 108160786Sps * for example, "+/xyz" on the command line. 108260786Sps * Also for multi-file (SRCH_PAST_EOF) searches. 108360786Sps */ 108460786Sps if (search_type & SRCH_FORW) 108560786Sps { 1086221715Sdelphij pos = ch_zero(); 108760786Sps } else 108860786Sps { 108960786Sps pos = ch_length(); 109060786Sps if (pos == NULL_POSITION) 109160786Sps { 109260786Sps (void) ch_end_seek(); 109360786Sps pos = ch_length(); 109460786Sps } 109560786Sps } 1096330571Sdelphij sindex = 0; 1097221715Sdelphij } else 109860786Sps { 1099221715Sdelphij int add_one = 0; 1100221715Sdelphij 1101221715Sdelphij if (how_search == OPT_ON) 110260786Sps { 1103221715Sdelphij /* 1104221715Sdelphij * Search does not include current screen. 1105221715Sdelphij */ 1106221715Sdelphij if (search_type & SRCH_FORW) 1107330571Sdelphij sindex = sc_height-1; /* BOTTOM_PLUS_ONE */ 1108221715Sdelphij else 1109330571Sdelphij sindex = 0; /* TOP */ 1110221715Sdelphij } else if (how_search == OPT_ONPLUS && !(search_type & SRCH_AFTER_TARGET)) 1111221715Sdelphij { 1112221715Sdelphij /* 1113221715Sdelphij * Search includes all of displayed screen. 1114221715Sdelphij */ 1115221715Sdelphij if (search_type & SRCH_FORW) 1116330571Sdelphij sindex = 0; /* TOP */ 1117221715Sdelphij else 1118330571Sdelphij sindex = sc_height-1; /* BOTTOM_PLUS_ONE */ 111960786Sps } else 112060786Sps { 1121221715Sdelphij /* 1122221715Sdelphij * Search includes the part of current screen beyond the jump target. 1123221715Sdelphij * It starts at the jump target (if searching backwards), 1124221715Sdelphij * or at the jump target plus one (if forwards). 1125221715Sdelphij */ 1126330571Sdelphij sindex = sindex_from_sline(jump_sline); 1127221715Sdelphij if (search_type & SRCH_FORW) 1128294286Sdelphij add_one = 1; 112960786Sps } 1130330571Sdelphij pos = position(sindex); 1131221715Sdelphij if (add_one) 1132221715Sdelphij pos = forw_raw_line(pos, (char **)NULL, (int *)NULL); 113360786Sps } 1134221715Sdelphij 1135221715Sdelphij /* 1136221715Sdelphij * If the line is empty, look around for a plausible starting place. 1137221715Sdelphij */ 1138221715Sdelphij if (search_type & SRCH_FORW) 1139221715Sdelphij { 1140294286Sdelphij while (pos == NULL_POSITION) 1141294286Sdelphij { 1142330571Sdelphij if (++sindex >= sc_height) 1143294286Sdelphij break; 1144330571Sdelphij pos = position(sindex); 1145294286Sdelphij } 1146221715Sdelphij } else 1147221715Sdelphij { 1148294286Sdelphij while (pos == NULL_POSITION) 1149294286Sdelphij { 1150330571Sdelphij if (--sindex < 0) 1151294286Sdelphij break; 1152330571Sdelphij pos = position(sindex); 1153294286Sdelphij } 1154221715Sdelphij } 115560786Sps return (pos); 115660786Sps} 115760786Sps 115860786Sps/* 115960786Sps * Search a subset of the file, specified by start/end position. 116060786Sps */ 116160786Sps static int 116260786Spssearch_range(pos, endpos, search_type, matches, maxlines, plinepos, pendpos) 116360786Sps POSITION pos; 116460786Sps POSITION endpos; 116560786Sps int search_type; 116660786Sps int matches; 116760786Sps int maxlines; 116860786Sps POSITION *plinepos; 116960786Sps POSITION *pendpos; 117060786Sps{ 117160786Sps char *line; 1172173685Sdelphij char *cline; 1173170259Sdelphij int line_len; 1174128348Stjr LINENUM linenum; 117560786Sps char *sp, *ep; 117660786Sps int line_match; 1177128348Stjr int cvt_ops; 1178195941Sdelphij int cvt_len; 1179195941Sdelphij int *chpos; 118060786Sps POSITION linepos, oldpos; 118160786Sps 118260786Sps linenum = find_linenum(pos); 118360786Sps oldpos = pos; 118460786Sps for (;;) 118560786Sps { 118660786Sps /* 118760786Sps * Get lines until we find a matching one or until 118860786Sps * we hit end-of-file (or beginning-of-file if we're 118960786Sps * going backwards), or until we hit the end position. 119060786Sps */ 119160786Sps if (ABORT_SIGS()) 119260786Sps { 119360786Sps /* 119460786Sps * A signal aborts the search. 119560786Sps */ 119660786Sps return (-1); 119760786Sps } 119860786Sps 119960786Sps if ((endpos != NULL_POSITION && pos >= endpos) || maxlines == 0) 120060786Sps { 120160786Sps /* 120260786Sps * Reached end position without a match. 120360786Sps */ 120460786Sps if (pendpos != NULL) 120560786Sps *pendpos = pos; 120660786Sps return (matches); 120760786Sps } 120860786Sps if (maxlines > 0) 120960786Sps maxlines--; 121060786Sps 121160786Sps if (search_type & SRCH_FORW) 121260786Sps { 121360786Sps /* 121460786Sps * Read the next line, and save the 121560786Sps * starting position of that line in linepos. 121660786Sps */ 121760786Sps linepos = pos; 1218170259Sdelphij pos = forw_raw_line(pos, &line, &line_len); 121960786Sps if (linenum != 0) 122060786Sps linenum++; 122160786Sps } else 122260786Sps { 122360786Sps /* 122460786Sps * Read the previous line and save the 122560786Sps * starting position of that line in linepos. 122660786Sps */ 1227170259Sdelphij pos = back_raw_line(pos, &line, &line_len); 122860786Sps linepos = pos; 122960786Sps if (linenum != 0) 123060786Sps linenum--; 123160786Sps } 123260786Sps 123360786Sps if (pos == NULL_POSITION) 123460786Sps { 123560786Sps /* 123660786Sps * Reached EOF/BOF without a match. 123760786Sps */ 123860786Sps if (pendpos != NULL) 123960786Sps *pendpos = oldpos; 124060786Sps return (matches); 124160786Sps } 124260786Sps 124360786Sps /* 124460786Sps * If we're using line numbers, we might as well 124560786Sps * remember the information we have now (the position 124660786Sps * and line number of the current line). 124760786Sps * Don't do it for every line because it slows down 124860786Sps * the search. Remember the line number only if 124960786Sps * we're "far" from the last place we remembered it. 125060786Sps */ 1251195941Sdelphij if (linenums && abs((int)(pos - oldpos)) > 2048) 125260786Sps add_lnum(linenum, pos); 125360786Sps oldpos = pos; 125460786Sps 1255191930Sdelphij if (is_filtered(linepos)) 1256191930Sdelphij continue; 1257191930Sdelphij 125860786Sps /* 125960786Sps * If it's a caseless search, convert the line to lowercase. 126060786Sps * If we're doing backspace processing, delete backspaces. 126160786Sps */ 1262128348Stjr cvt_ops = get_cvt_ops(); 1263195941Sdelphij cvt_len = cvt_length(line_len, cvt_ops); 1264195941Sdelphij cline = (char *) ecalloc(1, cvt_len); 1265195941Sdelphij chpos = cvt_alloc_chpos(cvt_len); 1266195941Sdelphij cvt_text(cline, line, chpos, &line_len, cvt_ops); 126760786Sps 1268191930Sdelphij#if HILITE_SEARCH 126960786Sps /* 1270191930Sdelphij * Check to see if the line matches the filter pattern. 1271191930Sdelphij * If so, add an entry to the filter list. 127260786Sps */ 1273294286Sdelphij if (((search_type & SRCH_FIND_ALL) || 1274294286Sdelphij prep_startpos == NULL_POSITION || 1275294286Sdelphij linepos < prep_startpos || linepos >= prep_endpos) && 1276294286Sdelphij prev_pattern(&filter_info)) { 1277237613Sdelphij int line_filter = match_pattern(info_compiled(&filter_info), filter_info.text, 1278195941Sdelphij cline, line_len, &sp, &ep, 0, filter_info.search_type); 1279191930Sdelphij if (line_filter) 1280191930Sdelphij { 1281294286Sdelphij struct hilite hl; 1282294286Sdelphij hl.hl_startpos = linepos; 1283294286Sdelphij hl.hl_endpos = pos; 1284294286Sdelphij add_hilite(&filter_anchor, &hl); 1285330571Sdelphij free(cline); 1286330571Sdelphij free(chpos); 1287294286Sdelphij continue; 1288191930Sdelphij } 1289173685Sdelphij } 1290191930Sdelphij#endif 1291191930Sdelphij 129260786Sps /* 1293191930Sdelphij * Test the next line to see if we have a match. 1294191930Sdelphij * We are successful if we either want a match and got one, 1295191930Sdelphij * or if we want a non-match and got one. 129660786Sps */ 1297195941Sdelphij if (prev_pattern(&search_info)) 129860786Sps { 1299237613Sdelphij line_match = match_pattern(info_compiled(&search_info), search_info.text, 1300221715Sdelphij cline, line_len, &sp, &ep, 0, search_type); 130160786Sps if (line_match) 130260786Sps { 130360786Sps /* 1304191930Sdelphij * Got a match. 130560786Sps */ 1306191930Sdelphij if (search_type & SRCH_FIND_ALL) 1307191930Sdelphij { 1308191930Sdelphij#if HILITE_SEARCH 1309191930Sdelphij /* 1310191930Sdelphij * We are supposed to find all matches in the range. 1311191930Sdelphij * Just add the matches in this line to the 1312191930Sdelphij * hilite list and keep searching. 1313191930Sdelphij */ 1314195941Sdelphij hilite_line(linepos, cline, line_len, chpos, sp, ep, cvt_ops); 1315191930Sdelphij#endif 1316191930Sdelphij } else if (--matches <= 0) 1317191930Sdelphij { 1318191930Sdelphij /* 1319191930Sdelphij * Found the one match we're looking for. 1320191930Sdelphij * Return it. 1321191930Sdelphij */ 1322191930Sdelphij#if HILITE_SEARCH 1323191930Sdelphij if (hilite_search == OPT_ON) 1324191930Sdelphij { 1325191930Sdelphij /* 1326191930Sdelphij * Clear the hilite list and add only 1327191930Sdelphij * the matches in this one line. 1328191930Sdelphij */ 1329191930Sdelphij clr_hilite(); 1330195941Sdelphij hilite_line(linepos, cline, line_len, chpos, sp, ep, cvt_ops); 1331191930Sdelphij } 1332191930Sdelphij#endif 1333191930Sdelphij free(cline); 1334195941Sdelphij free(chpos); 1335191930Sdelphij if (plinepos != NULL) 1336191930Sdelphij *plinepos = linepos; 1337191930Sdelphij return (0); 1338191930Sdelphij } 133960786Sps } 134060786Sps } 1341191930Sdelphij free(cline); 1342195941Sdelphij free(chpos); 134360786Sps } 134460786Sps} 134560786Sps 1346191930Sdelphij/* 1347170259Sdelphij * search for a pattern in history. If found, compile that pattern. 1348170259Sdelphij */ 1349170259Sdelphij static int 1350170259Sdelphijhist_pattern(search_type) 1351170259Sdelphij int search_type; 1352170259Sdelphij{ 1353170259Sdelphij#if CMD_HISTORY 1354170259Sdelphij char *pattern; 1355170259Sdelphij 1356170259Sdelphij set_mlist(ml_search, 0); 1357170259Sdelphij pattern = cmd_lastpattern(); 1358170259Sdelphij if (pattern == NULL) 1359170259Sdelphij return (0); 1360170259Sdelphij 1361195941Sdelphij if (set_pattern(&search_info, pattern, search_type) < 0) 1362170259Sdelphij return (0); 1363170259Sdelphij 1364170259Sdelphij#if HILITE_SEARCH 1365170259Sdelphij if (hilite_search == OPT_ONPLUS && !hide_hilite) 1366170259Sdelphij hilite_screen(); 1367170259Sdelphij#endif 1368170259Sdelphij 1369170259Sdelphij return (1); 1370170259Sdelphij#else /* CMD_HISTORY */ 1371170259Sdelphij return (0); 1372170259Sdelphij#endif /* CMD_HISTORY */ 1373170259Sdelphij} 1374170259Sdelphij 137560786Sps/* 1376330571Sdelphij * Change the caseless-ness of searches. 1377330571Sdelphij * Updates the internal search state to reflect a change in the -i flag. 1378330571Sdelphij */ 1379330571Sdelphij public void 1380330571Sdelphijchg_caseless() 1381330571Sdelphij{ 1382330571Sdelphij if (!is_ucase_pattern) 1383330571Sdelphij /* 1384330571Sdelphij * Pattern did not have uppercase. 1385330571Sdelphij * Just set the search caselessness to the global caselessness. 1386330571Sdelphij */ 1387330571Sdelphij is_caseless = caseless; 1388330571Sdelphij else 1389330571Sdelphij { 1390330571Sdelphij /* 1391330571Sdelphij * Pattern did have uppercase. 1392330571Sdelphij * Regenerate the pattern using the new state. 1393330571Sdelphij */ 1394330571Sdelphij clear_pattern(&search_info); 1395330571Sdelphij hist_pattern(search_info.search_type); 1396330571Sdelphij } 1397330571Sdelphij} 1398330571Sdelphij 1399330571Sdelphij/* 140060786Sps * Search for the n-th occurrence of a specified pattern, 140160786Sps * either forward or backward. 140260786Sps * Return the number of matches not yet found in this file 140360786Sps * (that is, n minus the number of matches found). 140460786Sps * Return -1 if the search should be aborted. 140560786Sps * Caller may continue the search in another file 140660786Sps * if less than n matches are found in this file. 140760786Sps */ 140860786Sps public int 140960786Spssearch(search_type, pattern, n) 141060786Sps int search_type; 141160786Sps char *pattern; 141260786Sps int n; 141360786Sps{ 141460786Sps POSITION pos; 141560786Sps 141660786Sps if (pattern == NULL || *pattern == '\0') 141760786Sps { 141860786Sps /* 141960786Sps * A null pattern means use the previously compiled pattern. 142060786Sps */ 1421221715Sdelphij search_type |= SRCH_AFTER_TARGET; 1422195941Sdelphij if (!prev_pattern(&search_info) && !hist_pattern(search_type)) 142360786Sps { 142460786Sps error("No previous regular expression", NULL_PARG); 142560786Sps return (-1); 142660786Sps } 142760786Sps if ((search_type & SRCH_NO_REGEX) != 1428195941Sdelphij (search_info.search_type & SRCH_NO_REGEX)) 142960786Sps { 143060786Sps error("Please re-enter search pattern", NULL_PARG); 143160786Sps return -1; 143260786Sps } 143360786Sps#if HILITE_SEARCH 1434330571Sdelphij if (hilite_search == OPT_ON || status_col) 143560786Sps { 143660786Sps /* 143760786Sps * Erase the highlights currently on screen. 143860786Sps * If the search fails, we'll redisplay them later. 143960786Sps */ 144060786Sps repaint_hilite(0); 144160786Sps } 144260786Sps if (hilite_search == OPT_ONPLUS && hide_hilite) 144360786Sps { 144460786Sps /* 144560786Sps * Highlight any matches currently on screen, 144660786Sps * before we actually start the search. 144760786Sps */ 144860786Sps hide_hilite = 0; 144960786Sps hilite_screen(); 145060786Sps } 145160786Sps hide_hilite = 0; 145260786Sps#endif 145360786Sps } else 145460786Sps { 145560786Sps /* 145660786Sps * Compile the pattern. 145760786Sps */ 1458195941Sdelphij if (set_pattern(&search_info, pattern, search_type) < 0) 145960786Sps return (-1); 146060786Sps#if HILITE_SEARCH 1461330571Sdelphij if (hilite_search || status_col) 146260786Sps { 146360786Sps /* 146460786Sps * Erase the highlights currently on screen. 146560786Sps * Also permanently delete them from the hilite list. 146660786Sps */ 146760786Sps repaint_hilite(0); 146860786Sps hide_hilite = 0; 146960786Sps clr_hilite(); 147060786Sps } 1471330571Sdelphij if (hilite_search == OPT_ONPLUS || status_col) 147260786Sps { 147360786Sps /* 147460786Sps * Highlight any matches currently on screen, 147560786Sps * before we actually start the search. 147660786Sps */ 147760786Sps hilite_screen(); 147860786Sps } 147960786Sps#endif 148060786Sps } 148160786Sps 148260786Sps /* 148360786Sps * Figure out where to start the search. 148460786Sps */ 148560786Sps pos = search_pos(search_type); 148660786Sps if (pos == NULL_POSITION) 148760786Sps { 148860786Sps /* 148960786Sps * Can't find anyplace to start searching from. 149060786Sps */ 149160786Sps if (search_type & SRCH_PAST_EOF) 149260786Sps return (n); 1493330571Sdelphij if (hilite_search == OPT_ON || status_col) 1494330571Sdelphij repaint_hilite(1); 149560786Sps error("Nothing to search", NULL_PARG); 149660786Sps return (-1); 149760786Sps } 149860786Sps 149960786Sps n = search_range(pos, NULL_POSITION, search_type, n, -1, 150060786Sps &pos, (POSITION*)NULL); 150160786Sps if (n != 0) 150260786Sps { 150360786Sps /* 150460786Sps * Search was unsuccessful. 150560786Sps */ 150660786Sps#if HILITE_SEARCH 1507330571Sdelphij if ((hilite_search == OPT_ON || status_col) && n > 0) 150860786Sps /* 150960786Sps * Redisplay old hilites. 151060786Sps */ 151160786Sps repaint_hilite(1); 151260786Sps#endif 151360786Sps return (n); 151460786Sps } 151560786Sps 151660786Sps if (!(search_type & SRCH_NO_MOVE)) 151760786Sps { 151860786Sps /* 151960786Sps * Go to the matching line. 152060786Sps */ 152160786Sps jump_loc(pos, jump_sline); 152260786Sps } 152360786Sps 152460786Sps#if HILITE_SEARCH 1525330571Sdelphij if (hilite_search == OPT_ON || status_col) 152660786Sps /* 152760786Sps * Display new hilites in the matching line. 152860786Sps */ 152960786Sps repaint_hilite(1); 153060786Sps#endif 153160786Sps return (0); 153260786Sps} 153360786Sps 153460786Sps 153560786Sps#if HILITE_SEARCH 153660786Sps/* 153760786Sps * Prepare hilites in a given range of the file. 153860786Sps * 153960786Sps * The pair (prep_startpos,prep_endpos) delimits a contiguous region 154060786Sps * of the file that has been "prepared"; that is, scanned for matches for 154160786Sps * the current search pattern, and hilites have been created for such matches. 154260786Sps * If prep_startpos == NULL_POSITION, the prep region is empty. 154360786Sps * If prep_endpos == NULL_POSITION, the prep region extends to EOF. 154460786Sps * prep_hilite asks that the range (spos,epos) be covered by the prep region. 154560786Sps */ 154660786Sps public void 154760786Spsprep_hilite(spos, epos, maxlines) 154860786Sps POSITION spos; 154960786Sps POSITION epos; 155060786Sps int maxlines; 155160786Sps{ 155260786Sps POSITION nprep_startpos = prep_startpos; 155360786Sps POSITION nprep_endpos = prep_endpos; 155460786Sps POSITION new_epos; 155560786Sps POSITION max_epos; 155660786Sps int result; 155760786Sps int i; 1558195941Sdelphij 155960786Sps/* 156060786Sps * Search beyond where we're asked to search, so the prep region covers 156160786Sps * more than we need. Do one big search instead of a bunch of small ones. 156260786Sps */ 156360786Sps#define SEARCH_MORE (3*size_linebuf) 156460786Sps 1565195941Sdelphij if (!prev_pattern(&search_info) && !is_filtering()) 156660786Sps return; 156760786Sps 156860786Sps /* 1569294286Sdelphij * Make sure our prep region always starts at the beginning of 1570294286Sdelphij * a line. (search_range takes care of the end boundary below.) 1571294286Sdelphij */ 1572294286Sdelphij spos = back_raw_line(spos+1, (char **)NULL, (int *)NULL); 1573294286Sdelphij 1574294286Sdelphij /* 157560786Sps * If we're limited to a max number of lines, figure out the 157660786Sps * file position we should stop at. 157760786Sps */ 157860786Sps if (maxlines < 0) 157960786Sps max_epos = NULL_POSITION; 158060786Sps else 158160786Sps { 158260786Sps max_epos = spos; 158360786Sps for (i = 0; i < maxlines; i++) 1584170259Sdelphij max_epos = forw_raw_line(max_epos, (char **)NULL, (int *)NULL); 158560786Sps } 158660786Sps 158760786Sps /* 158860786Sps * Find two ranges: 158960786Sps * The range that we need to search (spos,epos); and the range that 159060786Sps * the "prep" region will then cover (nprep_startpos,nprep_endpos). 159160786Sps */ 159260786Sps 159360786Sps if (prep_startpos == NULL_POSITION || 159460786Sps (epos != NULL_POSITION && epos < prep_startpos) || 159560786Sps spos > prep_endpos) 159660786Sps { 159760786Sps /* 159860786Sps * New range is not contiguous with old prep region. 159960786Sps * Discard the old prep region and start a new one. 160060786Sps */ 160160786Sps clr_hilite(); 1602191930Sdelphij clr_filter(); 160360786Sps if (epos != NULL_POSITION) 160460786Sps epos += SEARCH_MORE; 160560786Sps nprep_startpos = spos; 160660786Sps } else 160760786Sps { 160860786Sps /* 160960786Sps * New range partially or completely overlaps old prep region. 161060786Sps */ 161160786Sps if (epos == NULL_POSITION) 161260786Sps { 161360786Sps /* 161460786Sps * New range goes to end of file. 161560786Sps */ 161660786Sps ; 161760786Sps } else if (epos > prep_endpos) 161860786Sps { 161960786Sps /* 162060786Sps * New range ends after old prep region. 162160786Sps * Extend prep region to end at end of new range. 162260786Sps */ 162360786Sps epos += SEARCH_MORE; 162460786Sps } else /* (epos <= prep_endpos) */ 162560786Sps { 162660786Sps /* 162760786Sps * New range ends within old prep region. 162860786Sps * Truncate search to end at start of old prep region. 162960786Sps */ 163060786Sps epos = prep_startpos; 163160786Sps } 163260786Sps 163360786Sps if (spos < prep_startpos) 163460786Sps { 163560786Sps /* 163660786Sps * New range starts before old prep region. 163760786Sps * Extend old prep region backwards to start at 163860786Sps * start of new range. 163960786Sps */ 164060786Sps if (spos < SEARCH_MORE) 164160786Sps spos = 0; 164260786Sps else 164360786Sps spos -= SEARCH_MORE; 164460786Sps nprep_startpos = spos; 164560786Sps } else /* (spos >= prep_startpos) */ 164660786Sps { 164760786Sps /* 164860786Sps * New range starts within or after old prep region. 164960786Sps * Trim search to start at end of old prep region. 165060786Sps */ 165160786Sps spos = prep_endpos; 165260786Sps } 165360786Sps } 165460786Sps 165560786Sps if (epos != NULL_POSITION && max_epos != NULL_POSITION && 165660786Sps epos > max_epos) 165760786Sps /* 165860786Sps * Don't go past the max position we're allowed. 165960786Sps */ 166060786Sps epos = max_epos; 166160786Sps 166260786Sps if (epos == NULL_POSITION || epos > spos) 166360786Sps { 1664195941Sdelphij int search_type = SRCH_FORW | SRCH_FIND_ALL; 1665195941Sdelphij search_type |= (search_info.search_type & SRCH_NO_REGEX); 1666294286Sdelphij for (;;) 1667294286Sdelphij { 1668294286Sdelphij result = search_range(spos, epos, search_type, 0, maxlines, (POSITION*)NULL, &new_epos); 1669294286Sdelphij if (result < 0) 1670294286Sdelphij return; 1671294286Sdelphij if (prep_endpos == NULL_POSITION || new_epos > prep_endpos) 1672294286Sdelphij nprep_endpos = new_epos; 1673294286Sdelphij 1674294286Sdelphij /* 1675294286Sdelphij * Check both ends of the resulting prep region to 1676294286Sdelphij * make sure they're not filtered. If they are, 1677294286Sdelphij * keep going at least one more line until we find 1678294286Sdelphij * something that isn't filtered, or hit the end. 1679294286Sdelphij */ 1680294286Sdelphij if (prep_endpos == NULL_POSITION || nprep_endpos > prep_endpos) 1681294286Sdelphij { 1682294286Sdelphij if (new_epos >= nprep_endpos && is_filtered(new_epos-1)) 1683294286Sdelphij { 1684294286Sdelphij spos = nprep_endpos; 1685294286Sdelphij epos = forw_raw_line(nprep_endpos, (char **)NULL, (int *)NULL); 1686294286Sdelphij if (epos == NULL_POSITION) 1687294286Sdelphij break; 1688294286Sdelphij maxlines = 1; 1689294286Sdelphij continue; 1690294286Sdelphij } 1691294286Sdelphij } 1692294286Sdelphij 1693294286Sdelphij if (prep_startpos == NULL_POSITION || nprep_startpos < prep_startpos) 1694294286Sdelphij { 1695294286Sdelphij if (nprep_startpos > 0 && is_filtered(nprep_startpos)) 1696294286Sdelphij { 1697294286Sdelphij epos = nprep_startpos; 1698294286Sdelphij spos = back_raw_line(nprep_startpos, (char **)NULL, (int *)NULL); 1699294286Sdelphij if (spos == NULL_POSITION) 1700294286Sdelphij break; 1701294286Sdelphij nprep_startpos = spos; 1702294286Sdelphij maxlines = 1; 1703294286Sdelphij continue; 1704294286Sdelphij } 1705294286Sdelphij } 1706294286Sdelphij break; 1707294286Sdelphij } 170860786Sps } 170960786Sps prep_startpos = nprep_startpos; 171060786Sps prep_endpos = nprep_endpos; 171160786Sps} 1712191930Sdelphij 1713191930Sdelphij/* 1714191930Sdelphij * Set the pattern to be used for line filtering. 1715191930Sdelphij */ 1716191930Sdelphij public void 1717191930Sdelphijset_filter_pattern(pattern, search_type) 1718191930Sdelphij char *pattern; 1719191930Sdelphij int search_type; 1720191930Sdelphij{ 1721191930Sdelphij clr_filter(); 1722191930Sdelphij if (pattern == NULL || *pattern == '\0') 1723195941Sdelphij clear_pattern(&filter_info); 1724191930Sdelphij else 1725195941Sdelphij set_pattern(&filter_info, pattern, search_type); 1726191930Sdelphij screen_trashed = 1; 1727191930Sdelphij} 1728191930Sdelphij 1729191930Sdelphij/* 1730191930Sdelphij * Is there a line filter in effect? 1731191930Sdelphij */ 1732191930Sdelphij public int 1733191930Sdelphijis_filtering() 1734191930Sdelphij{ 1735191930Sdelphij if (ch_getflags() & CH_HELPFILE) 1736191930Sdelphij return (0); 1737195941Sdelphij return prev_pattern(&filter_info); 1738191930Sdelphij} 173960786Sps#endif 174060786Sps 174160786Sps#if HAVE_V8_REGCOMP 174260786Sps/* 174360786Sps * This function is called by the V8 regcomp to report 174460786Sps * errors in regular expressions. 174560786Sps */ 1746294286Sdelphijpublic int reg_show_error = 1; 1747294286Sdelphij 174860786Sps void 174960786Spsregerror(s) 175060786Sps char *s; 175160786Sps{ 175260786Sps PARG parg; 175360786Sps 1754294286Sdelphij if (!reg_show_error) 1755294286Sdelphij return; 175660786Sps parg.p_string = s; 175760786Sps error("%s", &parg); 175860786Sps} 175960786Sps#endif 176060786Sps 1761