selector.c

   1
   2 /*
   3  *  selector is a simple command line utility for selection of strings
   4  *  with a dynamic pattern-matching.
   5  *
   6  *  Copyright (c) 2009, 2010 Francois Fleuret
   7  *  Written by Francois Fleuret <francois@fleuret.org>
   8  *
   9  *  This file is part of selector.
  10  *
  11  *  selector is free software: you can redistribute it and/or modify
  12  *  it under the terms of the GNU General Public License version 3 as
  13  *  published by the Free Software Foundation.
  14  *
  15  *  selector is distributed in the hope that it will be useful, but
  16  *  WITHOUT ANY WARRANTY; without even the implied warranty of
  17  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  18  *  General Public License for more details.
  19  *
  20  *  You should have received a copy of the GNU General Public License
  21  *  along with selector.  If not, see <http://www.gnu.org/licenses/>.
  22  *
  23  */
  24
  25 /*
  26
  27   To use it as a super-history-search for bash:
  28   selector --bash <(history)
  29
  30 */
  31
  32 #define _GNU_SOURCE
  33
  34 #include <stdio.h>
  35 #include <stdlib.h>
  36 #include <unistd.h>
  37 #include <string.h>
  38 #include <errno.h>
  39 #include <ncurses.h>
  40 #include <fcntl.h>
  41 #include <sys/ioctl.h>
  42 #include <termios.h>
  43 #include <regex.h>
  44 #include <locale.h>
  45 #include <getopt.h>
  46 #include <limits.h>
  47
  48 #define VERSION "1.1.3"
  49
  50 #define BUFFER_SIZE 4096
  51
  52 /* Yeah, global variables! */
  53
  54 int nb_lines_max = 1000;
  55 char pattern_separator = ';';
  56 char label_separator = '\0';
  57 int output_to_vt_buffer = 0;
  58 int add_control_qs = 0;
  59 int with_colors = 1;
  60 int zsh_history = 0;
  61 int bash_history = 0;
  62 int inverse_order = 0;
  63 int remove_duplicates = 0;
  64 int use_regexp = 0;
  65 int case_sensitive = 0;
  66 char *title = 0;
  67 int error_flash = 0;
  68 int exclamation_negates = 0;
  69
  70 int attr_modeline, attr_focus_line, attr_error;
  71
  72 /********************************************************************/
  73
  74 /* malloc with error checking.  */
  75
  76 void *safe_malloc(size_t n) {
  77   void *p = malloc(n);
  78   if (!p && n != 0) {
  79     printf("Can not allocate memory: %s\n", strerror(errno));
  80     exit(EXIT_FAILURE);
  81   }
  82   return p;
  83 }
  84
  85 /*********************************************************************/
  86
  87 void inject_into_tty_buffer(char *string, int add_control_qs) {
  88   struct termios oldtio, newtio;
  89   const char *k;
  90   const char control_q = '\021';
  91   tcgetattr(STDIN_FILENO, &oldtio);
  92   memset(&newtio, 0, sizeof(newtio));
  93   /* Set input mode (non-canonical, *no echo*,...) */
  94   tcsetattr(STDIN_FILENO, TCSANOW, &newtio);
  95   /* Put the selected string in the tty input buffer */
  96   for(k = string; *k; k++) {
  97     if(add_control_qs && !(*k >= ' ' && *k <= '~')) {
  98       /* Add ^Q to quote control characters */
  99       ioctl(STDIN_FILENO, TIOCSTI, &control_q);
 100     }
 101     ioctl(STDIN_FILENO, TIOCSTI, k);
 102   }
 103   /* Restore the old settings */
 104   tcsetattr(STDIN_FILENO, TCSANOW, &oldtio);
 105 }
 106
 107 /*********************************************************************/
 108
 109 void str_to_positive_integers(char *string, int *values, int nb) {
 110   int current_value, gotone;
 111   char *s;
 112   int n;
 113
 114   n = 0;
 115   current_value = 0;
 116   gotone = 0;
 117   s = string;
 118
 119   while(1) {
 120     if(*s >= '0' && *s <= '9') {
 121       current_value = current_value * 10 + (int) (*s - '0');
 122       gotone = 1;
 123     } else if(*s == ',' || *s == '\0') {
 124       if(gotone) {
 125         if(n < nb) {
 126           values[n++] = current_value;
 127           if(*s == '\0') {
 128             if(n == nb) {
 129               return;
 130             } else {
 131               fprintf(stderr,
 132                       "selector: Missing value in `%s'.\n", string);
 133               exit(EXIT_FAILURE);
 134             }
 135           }
 136           current_value = 0;
 137           gotone = 0;
 138         } else {
 139           fprintf(stderr,
 140                   "selector: Too many values in `%s'.\n", string);
 141           exit(EXIT_FAILURE);
 142         }
 143       } else {
 144         fprintf(stderr,
 145                 "selector: Empty value in `%s'.\n", string);
 146         exit(EXIT_FAILURE);
 147       }
 148     } else {
 149       fprintf(stderr,
 150               "selector: Syntax error in `%s'.\n", string);
 151       exit(EXIT_FAILURE);
 152     }
 153     s++;
 154   }
 155 }
 156
 157 void error_feedback() {
 158   if(error_flash) {
 159     flash();
 160   } else {
 161     beep();
 162   }
 163 }
 164
 165 void usage(FILE *out) {
 166
 167   fprintf(out, "Selector version %s (%s)\n", VERSION, UNAME);
 168   fprintf(out, "Written by Francois Fleuret <francois@fleuret.org>.\n");
 169   fprintf(out, "\n");
 170   fprintf(out, "Usage: selector [options] [<filename1> [<filename2> ...]]\n");
 171   fprintf(out, "\n");
 172   fprintf(out, " -h, --help\n");
 173   fprintf(out, "         show this help\n");
 174   fprintf(out, " -v, --inject-in-tty\n");
 175   fprintf(out, "         inject the selected line in the tty\n");
 176   fprintf(out, " -w, --add-control-qs\n");
 177   fprintf(out, "         quote control characters with ^Qs when using -v\n");
 178   fprintf(out, " -d, --remove-duplicates\n");
 179   fprintf(out, "         remove duplicated lines\n");
 180   fprintf(out, " -b, --remove-bash-prefix\n");
 181   fprintf(out, "         remove the bash history line prefix\n");
 182   fprintf(out, " -z, --remove-zsh-prefix\n");
 183   fprintf(out, "         remove the zsh history line prefix\n");
 184   fprintf(out, " -i, --revert-order\n");
 185   fprintf(out, "         invert the order of lines\n");
 186   fprintf(out, " -e, --regexp\n");
 187   fprintf(out, "         start in regexp mode\n");
 188   fprintf(out, " -a, --case-sensitive\n");
 189   fprintf(out, "         start in case sensitive mode\n");
 190   fprintf(out, " -n, --exclamation-negates\n");
 191   fprintf(out, "         exclamation points in substring requires the string to be absent\n");
 192   fprintf(out, " -m, --monochrome\n");
 193   fprintf(out, "         monochrome mode\n");
 194   fprintf(out, " -q, --no-beep\n");
 195   fprintf(out, "         make a flash instead of a beep on an edition error\n");
 196   fprintf(out, " --bash\n");
 197   fprintf(out, "         setting for bash history search, same as -b -i -d -v -w -l ${HISTSIZE}\n");
 198   fprintf(out, " --      all following arguments are filenames\n");
 199   fprintf(out, " -t <title>, --title <title>\n");
 200   fprintf(out, "         add a title in the modeline\n");
 201   fprintf(out, " -c <colors>, --colors <colors>\n");
 202   fprintf(out, "         set the display colors with an argument of the form\n");
 203   fprintf(out, "         <fg_modeline>,<bg_modeline>,<fg_highlight>,<bg_highlight>\n");
 204   fprintf(out, " -o <output filename>, --output-file <output filename>\n");
 205   fprintf(out, "         set a file to write the selected line to\n");
 206   fprintf(out, " -s <pattern separator>, --pattern-separator <pattern separator>\n");
 207   fprintf(out, "         set the symbol to separate substrings in the pattern\n");
 208   fprintf(out, " -x <label separator>, --label-separator <label separator>\n");
 209   fprintf(out, "         set the symbol to terminate the label\n");
 210   fprintf(out, " -l <max number of lines>, --number-of-lines <max number of lines>\n");
 211   fprintf(out, "         set the maximum number of lines to take into account\n");
 212   fprintf(out, "\n");
 213 }
 214
 215 /*********************************************************************/
 216
 217 /* A quick and dirty hash table */
 218
 219 #define MAGIC_HASH_MULTIPLIER 387433
 220
 221 /* The table itself stores indexes of the strings taken in a char**
 222    table. When a string is added, if it was already in the table, the
 223    new index replaces the previous one.  */
 224
 225 struct hash_table_t {
 226   int size;
 227   int *entries;
 228 };
 229
 230 struct hash_table_t *new_hash_table(int size) {
 231   int k;
 232   struct hash_table_t *hash_table;
 233
 234   hash_table = safe_malloc(sizeof(struct hash_table_t));
 235
 236   hash_table->size = size;
 237   hash_table->entries = safe_malloc(hash_table->size * sizeof(int));
 238
 239   for(k = 0; k < hash_table->size; k++) {
 240     hash_table->entries[k] = -1;
 241   }
 242
 243   return hash_table;
 244 }
 245
 246 void free_hash_table(struct hash_table_t *hash_table) {
 247   free(hash_table->entries);
 248   free(hash_table);
 249 }
 250
 251 /* Adds new_string in the table, associated to new_index. If this
 252    string was not already in the table, returns -1. Otherwise, returns
 253    the previous index it had. */
 254
 255 int add_and_get_previous_index(struct hash_table_t *hash_table,
 256                                const char *new_string, int new_index,
 257                                char **strings) {
 258
 259   unsigned int code = 0, start;
 260   int k;
 261
 262   /* This is my recipe. I checked, it seems to work (as long as
 263      hash_table->size is not a multiple of MAGIC_HASH_MULTIPLIER that
 264      should be okay) */
 265
 266   for(k = 0; new_string[k]; k++) {
 267     code = code * MAGIC_HASH_MULTIPLIER + (unsigned int) (new_string[k]);
 268   }
 269
 270   code = code % hash_table->size;
 271   start = code;
 272
 273   while(hash_table->entries[code] >= 0) {
 274     /* There is a string with that code */
 275     if(strcmp(new_string, strings[hash_table->entries[code]]) == 0) {
 276       /* It is the same string, we keep a copy of the stored index */
 277       int result = hash_table->entries[code];
 278       /* Put the new one */
 279       hash_table->entries[code] = new_index;
 280       /* And return the previous one */
 281       return result;
 282     }
 283     /* This collision was not the same string, let's move to the next
 284        in the table */
 285     code = (code + 1) % hash_table->size;
 286     /* We came back to our original code, which means that the table
 287        is full */
 288     if(code == start) {
 289       printf("Full hash table (that should not happen)\n");
 290       exit(EXIT_FAILURE);
 291    }
 292   }
 293
 294   /* This string was not already in there, store the index in the
 295      table and return -1 */
 296
 297   hash_table->entries[code] = new_index;
 298   return -1;
 299 }
 300
 301 /*********************************************************************
 302  A matcher matches either with a collection of substrings, or with a
 303  regexp */
 304
 305 typedef struct {
 306   regex_t preg;
 307   int regexp_error;
 308   int nb_patterns;
 309   int case_sensitive;
 310   char *splitted_patterns, **patterns;
 311 } matcher_t;
 312
 313 int match(matcher_t *matcher, char *string) {
 314   int n;
 315   if(matcher->nb_patterns >= 0) {
 316     if(matcher->case_sensitive) {
 317       if(exclamation_negates) {
 318         for(n = 0; n < matcher->nb_patterns; n++) {
 319           if(matcher->patterns[n][0] == '!') {
 320             if(strstr(string, matcher->patterns[n] + 1) != 0) return 0;
 321           } else {
 322             if(strstr(string, matcher->patterns[n]) == 0) return 0;
 323           }
 324         }
 325       } else {
 326         for(n = 0; n < matcher->nb_patterns; n++) {
 327           if(strstr(string, matcher->patterns[n]) == 0) return 0;
 328         }
 329       }
 330     } else {
 331       if(exclamation_negates) {
 332         for(n = 0; n < matcher->nb_patterns; n++) {
 333           if(matcher->patterns[n][0] == '!') {
 334             if(strcasestr(string, matcher->patterns[n] + 1) != 0) return 0;
 335           } else {
 336             if(strcasestr(string, matcher->patterns[n]) == 0) return 0;
 337           }
 338         }
 339       } else {
 340         for(n = 0; n < matcher->nb_patterns; n++) {
 341           if(strcasestr(string, matcher->patterns[n]) == 0) return 0;
 342         }
 343       }
 344     }
 345     return 1;
 346   } else {
 347     return regexec(&matcher->preg, string, 0, 0, 0) == 0;
 348   }
 349 }
 350
 351 void free_matcher(matcher_t *matcher) {
 352   if(matcher->nb_patterns < 0) {
 353     if(!matcher->regexp_error) regfree(&matcher->preg);
 354   } else {
 355     free(matcher->splitted_patterns);
 356     free(matcher->patterns);
 357   }
 358 }
 359
 360 void initialize_matcher(matcher_t *matcher,
 361                         int use_regexp, int case_sensitive,
 362                         const char *pattern) {
 363   const char *s;
 364   char *t, *last_pattern_start;
 365   int n;
 366
 367   if(use_regexp) {
 368     matcher->nb_patterns = -1;
 369     matcher->regexp_error = regcomp(&matcher->preg, pattern,
 370                                     case_sensitive ? 0 : REG_ICASE);
 371   } else {
 372     matcher->regexp_error = 0;
 373     matcher->nb_patterns = 1;
 374     matcher->case_sensitive = case_sensitive;
 375
 376     for(s = pattern; *s; s++) {
 377       if(*s == pattern_separator) {
 378         matcher->nb_patterns++;
 379       }
 380     }
 381
 382     matcher->splitted_patterns =
 383       safe_malloc((strlen(pattern) + 1) * sizeof(char));
 384
 385     matcher->patterns =
 386       safe_malloc(matcher->nb_patterns * sizeof(char *));
 387
 388     strcpy(matcher->splitted_patterns, pattern);
 389
 390     n = 0;
 391     last_pattern_start = matcher->splitted_patterns;
 392     for(t = matcher->splitted_patterns; n < matcher->nb_patterns; t++) {
 393       if(*t == pattern_separator || *t == '\0') {
 394         *t = '\0';
 395         matcher->patterns[n++] = last_pattern_start;
 396         last_pattern_start = t + 1;
 397       }
 398     }
 399   }
 400 }
 401
 402 /*********************************************************************
 403  Buffer edition */
 404
 405 void delete_char(char *buffer, int *position) {
 406   if(buffer[*position]) {
 407     int c = *position;
 408     while(c < BUFFER_SIZE && buffer[c]) {
 409       buffer[c] = buffer[c+1];
 410       c++;
 411     }
 412   } else error_feedback();
 413 }
 414
 415 void backspace_char(char *buffer, int *position) {
 416   if(*position > 0) {
 417     if(buffer[*position]) {
 418       int c = *position - 1;
 419       while(buffer[c]) {
 420         buffer[c] = buffer[c+1];
 421         c++;
 422       }
 423     } else {
 424       buffer[*position - 1] = '\0';
 425     }
 426
 427     (*position)--;
 428   } else error_feedback();
 429 }
 430
 431 void insert_char(char *buffer, int *position, char character) {
 432   if(strlen(buffer) < BUFFER_SIZE - 1) {
 433     int c = *position;
 434     char t = buffer[c], u;
 435     while(t) {
 436       c++;
 437       u = buffer[c];
 438       buffer[c] = t;
 439       t = u;
 440     }
 441     c++;
 442     buffer[c] = '\0';
 443     buffer[(*position)++] = character;
 444   } else error_feedback();
 445 }
 446
 447 void kill_before_cursor(char *buffer, int *position) {
 448   int s = 0;
 449   while(buffer[*position + s]) {
 450     buffer[s] = buffer[*position + s];
 451     s++;
 452   }
 453   buffer[s] = '\0';
 454   *position = 0;
 455 }
 456
 457 void kill_after_cursor(char *buffer, int *position) {
 458   buffer[*position] = '\0';
 459 }
 460
 461 /*********************************************************************/
 462
 463 int previous_visible(int current_line, char **lines, matcher_t *matcher) {
 464   int line = current_line - 1;
 465   while(line >= 0 && !match(matcher, lines[line])) line--;
 466   return line;
 467 }
 468
 469 int next_visible(int current_line, int nb_lines, char **lines,
 470                  matcher_t *matcher) {
 471   int line = current_line + 1;
 472   while(line < nb_lines && !match(matcher, lines[line])) line++;
 473
 474   if(line < nb_lines)
 475     return line;
 476   else
 477     return -1;
 478 }
 479
 480 /*********************************************************************/
 481
 482 /* The line highlighted is the first one matching the matcher in that
 483    order: (1) current_focus_line after motion, if it does not match,
 484    then (2) the first with a greater index, if none matches, then (3)
 485    the first with a lesser index.
 486
 487    The index of the line actually shown highlighted is written in
 488    displayed_focus_line (it can be -1 if no line at all matches the
 489    matcher)
 490
 491    If there is a motion and a line is actually shown highlighted, its
 492    value is written in current_focus_line. */
 493
 494 void update_screen(int *current_focus_line, int *displayed_focus_line,
 495                    int motion,
 496                    int nb_lines, char **lines,
 497                    int cursor_position,
 498                    char *pattern) {
 499
 500   char buffer[BUFFER_SIZE];
 501   matcher_t matcher;
 502   int k, l, m;
 503   int console_width, console_height;
 504   int nb_printed_lines = 0;
 505   int cursor_x;
 506
 507   initialize_matcher(&matcher, use_regexp, case_sensitive, pattern);
 508
 509   console_width = getmaxx(stdscr);
 510   console_height = getmaxy(stdscr);
 511
 512   use_default_colors();
 513
 514   /* Add an empty line where we will print the modeline at the end */
 515
 516   addstr("\n");
 517
 518   /* If the regexp is erroneous, print a message saying so */
 519
 520   if(matcher.regexp_error) {
 521     attron(attr_error);
 522     addnstr("Regexp syntax error", console_width);
 523     attroff(attr_error);
 524   }
 525
 526   /* Else, and we do have lines to select from, find a visible line. */
 527
 528   else if(nb_lines > 0) {
 529     int new_focus_line;
 530     if(match(&matcher, lines[*current_focus_line])) {
 531       new_focus_line = *current_focus_line;
 532     } else {
 533       new_focus_line = next_visible(*current_focus_line, nb_lines, lines,
 534                                     &matcher);
 535       if(new_focus_line < 0) {
 536         new_focus_line = previous_visible(*current_focus_line, lines, &matcher);
 537       }
 538     }
 539
 540     /* If we found a visible line and we should move, let's move */
 541
 542     if(new_focus_line >= 0 && motion != 0) {
 543       int l = new_focus_line;
 544       if(motion > 0) {
 545         /* We want to go down, let's find the first visible line below */
 546         for(m = 0; l >= 0 && m < motion; m++) {
 547           l = next_visible(l, nb_lines, lines, &matcher);
 548           if(l >= 0) {
 549             new_focus_line = l;
 550           }
 551         }
 552       } else {
 553         /* We want to go up, let's find the first visible line above */
 554         for(m = 0; l >= 0 && m < -motion; m++) {
 555           l = previous_visible(l, lines, &matcher);
 556           if(l >= 0) {
 557             new_focus_line = l;
 558           }
 559         }
 560       }
 561     }
 562
 563     /* Here new_focus_line is either a line number matching the
 564        pattern, or -1 */
 565
 566     if(new_focus_line >= 0) {
 567
 568       int first_line = new_focus_line, last_line = new_focus_line;
 569       int nb_match = 1;
 570
 571       /* We find the first and last lines to show, so that the total
 572          of visible lines between them (them included) is
 573          console_height-1 */
 574
 575       while(nb_match < console_height-1 &&
 576             (first_line > 0 || last_line < nb_lines - 1)) {
 577
 578         if(first_line > 0) {
 579           first_line--;
 580           while(first_line > 0 && !match(&matcher, lines[first_line])) {
 581             first_line--;
 582           }
 583           if(match(&matcher, lines[first_line])) {
 584             nb_match++;
 585           }
 586         }
 587
 588         if(nb_match < console_height - 1 && last_line < nb_lines - 1) {
 589           last_line++;
 590           while(last_line < nb_lines - 1 && !match(&matcher, lines[last_line])) {
 591             last_line++;
 592           }
 593
 594           if(match(&matcher, lines[last_line])) {
 595             nb_match++;
 596           }
 597         }
 598       }
 599
 600       /* Now we display them */
 601
 602       for(l = first_line; l <= last_line; l++) {
 603         if(match(&matcher, lines[l])) {
 604           int k = 0;
 605
 606           while(lines[l][k] && k < BUFFER_SIZE - 2 && k < console_width - 2) {
 607             buffer[k] = lines[l][k];
 608             k++;
 609           }
 610
 611           /* We fill the rest of the line with blanks if this is the
 612              highlighted line */
 613
 614           if(l == new_focus_line) {
 615             while(k < console_width) {
 616               buffer[k++] = ' ';
 617             }
 618           }
 619
 620           buffer[k++] = '\n';
 621           buffer[k++] = '\0';
 622
 623           clrtoeol();
 624
 625           /* Highlight the highlighted line ... */
 626
 627           if(l == new_focus_line) {
 628             attron(attr_focus_line);
 629             addnstr(buffer, console_width);
 630             attroff(attr_focus_line);
 631           } else {
 632             addnstr(buffer, console_width);
 633           }
 634
 635           nb_printed_lines++;
 636         }
 637       }
 638
 639       /* If we are on a focused line and we moved, this become the new
 640          focus line */
 641
 642       if(motion != 0) {
 643         *current_focus_line = new_focus_line;
 644       }
 645     }
 646
 647     *displayed_focus_line = new_focus_line;
 648
 649     if(nb_printed_lines == 0) {
 650       attron(attr_error);
 651       addnstr("No selection", console_width);
 652       attroff(attr_error);
 653     }
 654   }
 655
 656   /* Else, print a message saying that there are no lines to select from */
 657
 658   else {
 659     attron(attr_error);
 660     addnstr("Empty choice", console_width);
 661     attroff(attr_error);
 662   }
 663
 664   clrtobot();
 665
 666   /* Draw the modeline */
 667
 668   move(0, 0);
 669
 670   attron(attr_modeline);
 671
 672   for(k = 0; k < console_width; k++) buffer[k] = ' ';
 673   buffer[console_width] = '\0';
 674   addnstr(buffer, console_width);
 675
 676   move(0, 0);
 677
 678   /* There must be a more elegant way of moving the cursor at a
 679      location met during display */
 680
 681   cursor_x = 0;
 682
 683   if(title) {
 684     addstr(title);
 685     addstr(" ");
 686     cursor_x += strlen(title) + 1;
 687   }
 688
 689   sprintf(buffer, "%d/%d ", nb_printed_lines, nb_lines);
 690   addstr(buffer);
 691   cursor_x += strlen(buffer);
 692
 693   addnstr(pattern, cursor_position);
 694   cursor_x += cursor_position;
 695
 696   if(pattern[cursor_position]) {
 697     addstr(pattern + cursor_position);
 698   } else {
 699     addstr(" ");
 700   }
 701
 702   /* Add a few info about the mode we are in (regexp and/or case
 703      sensitive) */
 704
 705   if(use_regexp || case_sensitive) {
 706     addstr(" [");
 707     if(use_regexp) {
 708       addstr("regexp");
 709     }
 710
 711     if(case_sensitive) {
 712       if(use_regexp) {
 713         addstr(",");
 714       }
 715       addstr("case");
 716     }
 717     addstr("]");
 718   }
 719
 720   move(0, cursor_x);
 721
 722   attroff(attr_modeline);
 723
 724   /* We are done */
 725
 726   refresh();
 727   free_matcher(&matcher);
 728 }
 729
 730 /*********************************************************************/
 731
 732 void store_line(struct hash_table_t *hash_table,
 733                 const char *new_line,
 734                 int *nb_lines, char **lines) {
 735   int dup;
 736
 737   /* Remove the zsh history prefix */
 738
 739   if(zsh_history && *new_line == ':') {
 740     while(*new_line && *new_line != ';') new_line++;
 741     if(*new_line == ';') new_line++;
 742   }
 743
 744   /* Remove the bash history prefix */
 745
 746   if(bash_history) {
 747     while(*new_line == ' ') new_line++;
 748     while(*new_line >= '0' && *new_line <= '9') new_line++;
 749     while(*new_line == ' ') new_line++;
 750   }
 751
 752   /* Check for duplicates with the hash table and insert the line in
 753      the list if necessary */
 754
 755   if(hash_table) {
 756     dup = add_and_get_previous_index(hash_table,
 757                                      new_line, *nb_lines, lines);
 758   } else {
 759     dup = -1;
 760   }
 761
 762   if(dup < 0) {
 763     lines[*nb_lines] = safe_malloc((strlen(new_line) + 1) * sizeof(char));
 764     strcpy(lines[*nb_lines], new_line);
 765   } else {
 766     /* The string was already in there, so we do not allocate a new
 767        string but use the pointer to the first occurence of it */
 768     lines[*nb_lines] = lines[dup];
 769     lines[dup] = 0;
 770   }
 771
 772   (*nb_lines)++;
 773 }
 774
 775 void read_file(struct hash_table_t *hash_table,
 776                const char *input_filename,
 777                int nb_lines_max, int *nb_lines, char **lines) {
 778
 779   char raw_line[BUFFER_SIZE];
 780   int start, end, eol, k;
 781   FILE *file;
 782
 783   file = fopen(input_filename, "r");
 784
 785   if(!file) {
 786     fprintf(stderr, "selector: Can not open `%s'.\n", input_filename);
 787     exit(EXIT_FAILURE);
 788   }
 789
 790   start = 0;
 791   end = 0;
 792
 793   while(*nb_lines < nb_lines_max && (end > start || !feof(file))) {
 794     eol = start;
 795
 796     /* Look for the end of a line in what is already in the buffer */
 797     while(eol < end && raw_line[eol] != '\n') eol++;
 798
 799     /* if we did not find the of a line, move what has not been
 800        processed and is in the buffer to the beginning of the buffer,
 801        fill the buffer with new data from the file, and look for the
 802        end of a line */
 803     if(eol == end) {
 804       for(k = 0; k < end - start; k++) {
 805         raw_line[k] = raw_line[k + start];
 806       }
 807       end -= start;
 808       eol -= start;
 809       start = 0;
 810       end += fread(raw_line + end, sizeof(char), BUFFER_SIZE - end, file);
 811       while(eol < end && raw_line[eol] != '\n') eol++;
 812     }
 813
 814     /* The end of the line is the buffer size, which means the line is
 815        too long */
 816
 817     if(eol == BUFFER_SIZE) {
 818       raw_line[BUFFER_SIZE - 1] = '\0';
 819       fprintf(stderr, "selector: Line too long (max is %d characters):\n",
 820               BUFFER_SIZE);
 821       fprintf(stderr, "%s", raw_line);
 822       fprintf(stderr, "\n");
 823       exit(EXIT_FAILURE);
 824     }
 825
 826     /* If we got a line, we replace the carriage return by a \0 to
 827        finish the string */
 828
 829     raw_line[eol] = '\0';
 830
 831     store_line(hash_table, raw_line + start,
 832                nb_lines, lines);
 833
 834     start = eol + 1;
 835   }
 836
 837   fclose(file);
 838 }
 839
 840 /*********************************************************************/
 841
 842 /* For long options that have no equivalent short option, use a
 843    non-character as a pseudo short option, starting with CHAR_MAX + 1.  */
 844 enum
 845 {
 846   OPT_BASH_MODE = CHAR_MAX + 1
 847 };
 848
 849 static struct option long_options[] = {
 850   { "output-file", 1, 0, 'o' },
 851   { "pattern-separator", 1, 0, 's' },
 852   { "label-separator", 1, 0, 'x' },
 853   { "inject-in-tty", no_argument, 0, 'v' },
 854   { "add-control-qs", no_argument, 0, 'w' },
 855   { "monochrome", no_argument, 0, 'm' },
 856   { "no-beep", no_argument, 0, 'q' },
 857   { "revert-order", no_argument, 0, 'i' },
 858   { "remove-bash-prefix", no_argument, 0, 'b' },
 859   { "remove-zsh-prefix", no_argument, 0, 'z' },
 860   { "remove-duplicates", no_argument, 0, 'd' },
 861   { "regexp", no_argument, 0, 'e' },
 862   { "case-sensitive", no_argument, 0, 'a' },
 863   { "title", 1, 0, 't' },
 864   { "number-of-lines", 1, 0, 'l' },
 865   { "colors", 1, 0, 'c' },
 866   { "bash", no_argument, 0, OPT_BASH_MODE },
 867   { "help", no_argument, 0, 'h' },
 868   { 0, 0, 0, 0 }
 869 };
 870
 871 int main(int argc, char **argv) {
 872
 873   char output_filename[BUFFER_SIZE];
 874   char pattern[BUFFER_SIZE];
 875   int c, k, l, n;
 876   int cursor_position;
 877   int error = 0, show_help = 0, done = 0;
 878   int key;
 879   int current_focus_line, displayed_focus_line;
 880
 881   int colors[4];
 882   int color_fg_modeline, color_bg_modeline;
 883   int color_fg_highlight, color_bg_highlight;
 884
 885   char **lines, **labels;
 886   int nb_lines;
 887   struct hash_table_t *hash_table;
 888   char *bash_histsize;
 889
 890   if(!isatty(STDIN_FILENO)) {
 891     fprintf(stderr, "selector: The standard input is not a tty.\n");
 892     exit(EXIT_FAILURE);
 893   }
 894
 895   color_fg_modeline  = COLOR_WHITE;
 896   color_bg_modeline  = COLOR_BLACK;
 897   color_fg_highlight = COLOR_BLACK;
 898   color_bg_highlight = COLOR_YELLOW;
 899
 900   setlocale(LC_ALL, "");
 901
 902   strcpy(output_filename, "");
 903
 904   while ((c = getopt_long(argc, argv, "o:s:x:vwmqf:ibzdeant:l:c:-h",
 905                           long_options, NULL)) != -1) {
 906
 907     switch(c) {
 908
 909     case 'o':
 910       strncpy(output_filename, optarg, BUFFER_SIZE);
 911       break;
 912
 913     case 's':
 914       pattern_separator = optarg[0];
 915       break;
 916
 917     case 'x':
 918       label_separator = optarg[0];
 919       break;
 920
 921     case 'v':
 922       output_to_vt_buffer = 1;
 923       break;
 924
 925     case 'w':
 926       add_control_qs = 1;
 927       break;
 928
 929     case 'm':
 930       with_colors = 0;
 931       break;
 932
 933     case 'q':
 934       error_flash = 1;
 935       break;
 936
 937     case 'i':
 938       inverse_order = 1;
 939       break;
 940
 941     case 'b':
 942       bash_history = 1;
 943       break;
 944
 945     case 'z':
 946       zsh_history = 1;
 947       break;
 948
 949     case 'd':
 950       remove_duplicates = 1;
 951       break;
 952
 953     case 'e':
 954       use_regexp = 1;
 955       break;
 956
 957     case 'a':
 958       case_sensitive = 1;
 959       break;
 960
 961     case 'n':
 962       exclamation_negates = 1;
 963       break;
 964
 965     case 't':
 966       free(title);
 967       title = safe_malloc((strlen(optarg) + 1) * sizeof(char));
 968       strcpy(title, optarg);
 969       break;
 970
 971     case 'l':
 972       str_to_positive_integers(optarg, &nb_lines_max, 1);
 973       break;
 974
 975     case 'c':
 976       str_to_positive_integers(optarg, colors, 4);
 977       color_fg_modeline = colors[0];
 978       color_bg_modeline = colors[1];
 979       color_fg_highlight = colors[2];
 980       color_bg_highlight = colors[3];
 981       break;
 982
 983     case 'h':
 984       show_help = 1;
 985       break;
 986
 987     case OPT_BASH_MODE:
 988       /* Same as -c 7,4,0,3 -q */
 989       /* color_fg_modeline = 7; */
 990       /* color_bg_modeline = 4; */
 991       /* color_fg_highlight = 0; */
 992       /* color_bg_highlight = 3; */
 993       /* error_flash = 1; */
 994       /* Same as -b -i -d -v -w */
 995       bash_history = 1;
 996       inverse_order = 1;
 997       remove_duplicates = 1;
 998       output_to_vt_buffer = 1;
 999       add_control_qs = 1;
1000       bash_histsize = getenv("HISTSIZE");
1001       if(bash_histsize) {
1002         str_to_positive_integers(bash_histsize, &nb_lines_max, 1);
1003       }
1004       break;
1005
1006     default:
1007       error = 1;
1008       break;
1009     }
1010   }
1011
1012   if(error) {
1013     usage(stderr);
1014     exit(EXIT_FAILURE);
1015   }
1016
1017   if(show_help) {
1018     usage(stdout);
1019     exit(EXIT_SUCCESS);
1020   }
1021
1022   lines = safe_malloc(nb_lines_max * sizeof(char *));
1023
1024   nb_lines = 0;
1025
1026   if(remove_duplicates) {
1027     hash_table = new_hash_table(nb_lines_max * 10);
1028   } else {
1029     hash_table = 0;
1030   }
1031
1032   while(optind < argc) {
1033     read_file(hash_table,
1034               argv[optind],
1035               nb_lines_max, &nb_lines, lines);
1036     optind++;
1037   }
1038
1039   if(hash_table) {
1040     free_hash_table(hash_table);
1041   }
1042
1043   /* Now remove the null strings */
1044
1045   n = 0;
1046   for(k = 0; k < nb_lines; k++) {
1047     if(lines[k]) {
1048       lines[n++] = lines[k];
1049     }
1050   }
1051
1052   nb_lines = n;
1053
1054   if(inverse_order) {
1055     for(l = 0; l < nb_lines / 2; l++) {
1056       char *s = lines[nb_lines - 1 - l];
1057       lines[nb_lines - 1 - l] = lines[l];
1058       lines[l] = s;
1059     }
1060   }
1061
1062   /* Build the labels from the strings, take only the part before the
1063      label_separator and transform control characters to printable
1064      ones */
1065
1066   labels = safe_malloc(nb_lines * sizeof(char *));
1067
1068   for(l = 0; l < nb_lines; l++) {
1069     char *s, *t;
1070     int e = 0;
1071     const char *u;
1072     t = lines[l];
1073
1074     while(*t && *t != label_separator) {
1075       u = unctrl(*t++);
1076       e += strlen(u);
1077     }
1078
1079     labels[l] = safe_malloc((e + 1) * sizeof(char));
1080     t = lines[l];
1081     s = labels[l];
1082     while(*t && *t != label_separator) {
1083       u = unctrl(*t++);
1084       while(*u) { *s++ = *u++; }
1085     }
1086     *s = '\0';
1087   }
1088
1089   pattern[0] = '\0';
1090
1091   cursor_position = 0;
1092
1093   /* Here we start to display with curse */
1094
1095   initscr();
1096   cbreak();
1097   noecho();
1098   intrflush(stdscr, FALSE);
1099
1100   /* So that the arrow keys work */
1101   keypad(stdscr, TRUE);
1102
1103   attr_error = A_STANDOUT;
1104   attr_modeline = A_REVERSE;
1105   attr_focus_line = A_STANDOUT;
1106
1107   if(with_colors && has_colors()) {
1108
1109     start_color();
1110
1111     if(color_fg_modeline < 0  || color_fg_modeline >= COLORS ||
1112        color_bg_modeline < 0  || color_bg_modeline >= COLORS ||
1113        color_fg_highlight < 0 || color_bg_highlight >= COLORS ||
1114        color_bg_highlight < 0 || color_bg_highlight >= COLORS) {
1115       echo();
1116       endwin();
1117       fprintf(stderr, "selector: Color numbers have to be between 0 and %d.\n",
1118               COLORS - 1);
1119       exit(EXIT_FAILURE);
1120     }
1121
1122     init_pair(1, color_fg_modeline, color_bg_modeline);
1123     attr_modeline = COLOR_PAIR(1);
1124
1125     init_pair(2, color_fg_highlight, color_bg_highlight);
1126     attr_focus_line = COLOR_PAIR(2);
1127
1128     init_pair(3, COLOR_WHITE, COLOR_RED);
1129     attr_error = COLOR_PAIR(3);
1130
1131   }
1132
1133   current_focus_line = 0;
1134   displayed_focus_line = 0;
1135
1136   update_screen(&current_focus_line, &displayed_focus_line,
1137                 0,
1138                 nb_lines, labels, cursor_position, pattern);
1139
1140   do {
1141     int motion = 0;
1142
1143     key = getch();
1144
1145     if(key >= ' ' && key <= '~') { /* Insert character */
1146       insert_char(pattern, &cursor_position, key);
1147     }
1148
1149     else if(key == KEY_BACKSPACE ||
1150             key == '\010' || /* ^H */
1151             key == '\177') { /* ^? */
1152       backspace_char(pattern, &cursor_position);
1153     }
1154
1155     else if(key == KEY_DC ||
1156             key == '\004') { /* ^D */
1157       delete_char(pattern, &cursor_position);
1158     }
1159
1160     else if(key == KEY_HOME) {
1161       current_focus_line = 0;
1162     }
1163
1164     else if(key == KEY_END) {
1165       current_focus_line = nb_lines - 1;
1166     }
1167
1168     else if(key == KEY_NPAGE) {
1169       motion = 10;
1170     }
1171
1172     else if(key == KEY_PPAGE) {
1173       motion = -10;
1174     }
1175
1176     else if(key == KEY_DOWN ||
1177             key == '\016') { /* ^N */
1178       motion = 1;
1179     }
1180
1181     else if(key == KEY_UP ||
1182             key == '\020') { /* ^P */
1183       motion = -1;
1184     }
1185
1186     else if(key == KEY_LEFT ||
1187             key == '\002') { /* ^B */
1188       if(cursor_position > 0) cursor_position--;
1189       else error_feedback();
1190     }
1191
1192     else if(key == KEY_RIGHT ||
1193             key == '\006') { /* ^F */
1194       if(pattern[cursor_position]) cursor_position++;
1195       else error_feedback();
1196     }
1197
1198     else if(key == '\001') { /* ^A */
1199       cursor_position = 0;
1200     }
1201
1202     else if(key == '\005') { /* ^E */
1203       cursor_position = strlen(pattern);
1204     }
1205
1206     else if(key == '\022') { /* ^R */
1207       use_regexp = !use_regexp;
1208     }
1209
1210     else if(key == '\011') { /* ^I */
1211       case_sensitive = !case_sensitive;
1212     }
1213
1214     else if(key == '\025') { /* ^U */
1215       kill_before_cursor(pattern, &cursor_position);
1216     }
1217
1218     else if(key == '\013') { /* ^K */
1219       kill_after_cursor(pattern, &cursor_position);
1220     }
1221
1222     else if(key == '\014') { /* ^L */
1223       /* I suspect that we may sometime mess up the display, so ^L is
1224          here to force a full refresh */
1225       clear();
1226     }
1227
1228     else if(key == '\007' || /* ^G */
1229             key == '\033' || /* ^[ (escape) */
1230             key == '\n' ||
1231             key == KEY_ENTER) {
1232       done = 1;
1233     }
1234
1235     else if(key == KEY_RESIZE || key == -1) {
1236       /* Do nothing when the tty is resized */
1237     }
1238
1239     else {
1240       /* Unknown key */
1241       error_feedback();
1242     }
1243
1244     update_screen(&current_focus_line, &displayed_focus_line,
1245                   motion,
1246                   nb_lines, labels, cursor_position, pattern);
1247
1248   } while(!done);
1249
1250   echo();
1251   endwin();
1252
1253   /* Here we come back to standard display */
1254
1255   if((key == KEY_ENTER || key == '\n')) {
1256
1257     char *t;
1258
1259     if(displayed_focus_line >= 0 && displayed_focus_line < nb_lines) {
1260       t = lines[displayed_focus_line];
1261       if(label_separator) {
1262         while(*t && *t != label_separator) t++;
1263         if(*t) t++;
1264       }
1265     } else {
1266       t = 0;
1267     }
1268
1269     if(output_to_vt_buffer && t) {
1270       inject_into_tty_buffer(t, add_control_qs);
1271     }
1272
1273     if(output_filename[0]) {
1274       FILE *out = fopen(output_filename, "w");
1275       if(out) {
1276         if(t) {
1277           fprintf(out, "%s", t);
1278         }
1279         fprintf(out, "\n");
1280       } else {
1281         fprintf(stderr,
1282                 "selector: Can not open %s for writing.\n",
1283                 output_filename);
1284         exit(EXIT_FAILURE);
1285       }
1286       fclose(out);
1287     }
1288
1289   } else {
1290     printf("Aborted.\n");
1291   }
1292
1293   for(l = 0; l < nb_lines; l++) {
1294     free(lines[l]);
1295     free(labels[l]);
1296   }
1297
1298   free(labels);
1299   free(lines);
1300   free(title);
1301
1302   exit(EXIT_SUCCESS);
1303 }