3 * selector is a simple command line utility for selection of strings
4 * with a dynamic pattern-matching.
6 * Copyright (c) 2009 Francois Fleuret
7 * Written by Francois Fleuret <francois@fleuret.org>
9 * This file is part of selector.
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.
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.
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/>.
27 To use it as a super-history-search for bash:
28 selector -q -b -i -d -v -w -l ${HISTSIZE} <(history)
40 #include <sys/ioctl.h>
47 #define BUFFER_SIZE 4096
49 /* Yeah, global variables! */
51 int nb_lines_max = 1000;
52 char pattern_separator = ';';
53 char label_separator = '\0';
54 int output_to_vt_buffer = 0;
55 int add_control_qs = 0;
59 int inverse_order = 0;
60 int remove_duplicates = 0;
62 int case_sensitive = 0;
66 int attr_modeline, attr_focus_line, attr_error;
68 /*********************************************************************/
70 void inject_into_tty_buffer(char *string) {
71 struct termios oldtio, newtio;
73 const char control_q = '\021';
74 tcgetattr(STDIN_FILENO, &oldtio);
75 memset(&newtio, 0, sizeof(newtio));
76 /* Set input mode (non-canonical, *no echo*,...) */
77 tcsetattr(STDIN_FILENO, TCSANOW, &newtio);
78 /* Put the selected string in the tty input buffer */
79 for(k = string; *k; k++) {
80 if(add_control_qs && !(*k >= ' ' && *k <= '~')) {
81 /* Add ^Q to quote control characters */
82 ioctl(STDIN_FILENO, TIOCSTI, &control_q);
84 ioctl(STDIN_FILENO, TIOCSTI, k);
86 /* Restore the old settings */
87 tcsetattr(STDIN_FILENO, TCSANOW, &oldtio);
90 /*********************************************************************/
92 void check_opt(int argc, char **argv, int n_opt, int n, const char *help) {
93 if(n_opt + n >= argc) {
94 fprintf(stderr, "Selector: Missing argument for %s, expecting %s.\n",
100 int string_to_positive_integer(char *string) {
106 for(s = string; *s; s++) {
107 if(*s >= '0' && *s <= '9') {
108 result = result * 10 + (int) (*s - '0');
114 fprintf(stderr, "Selector: Value `%s' is not a positive integer.\n", string);
121 void error_feedback() {
129 /* A quick and dirty hash table */
131 /* The table itself stores indexes of the strings taken in a char
132 **table. When a string is added, if it was already in the table,
133 **the new index replaces the previous one. */
140 hash_table_t *new_hash_table(int size) {
142 hash_table_t *hash_table;
144 hash_table = (hash_table_t *) malloc(sizeof(hash_table_t));
146 hash_table->size = size;
147 hash_table->entries = (int *) malloc(hash_table->size * sizeof(int));
149 for(k = 0; k < hash_table->size; k++) {
150 hash_table->entries[k] = -1;
156 void free_hash_table(hash_table_t *hash_table) {
157 free(hash_table->entries);
161 /* Adds new_string in the table, associated to new_index. If this
162 string was not already in the table, returns -1. Otherwise, returns
163 the previous index it had. */
165 int add_and_get_previous_index(hash_table_t *hash_table,
166 const char *new_string, int new_index,
169 unsigned int code = 0;
172 /* This is my recipe. I checked, it seems to work (as long as
173 hash_table->size is not a multiple of 387433 that should be
176 for(k = 0; new_string[k]; k++) {
177 code = code * 387433 + (unsigned int) (new_string[k]);
180 code = code % hash_table->size;
182 while(hash_table->entries[code] >= 0) {
183 /* There is a string with that code */
184 if(strcmp(new_string, strings[hash_table->entries[code]]) == 0) {
185 /* It is the same string, we keep a copy of the stored index */
186 int result = hash_table->entries[code];
187 /* Put the new one */
188 hash_table->entries[code] = new_index;
189 /* And return the previous one */
192 /* This collision was not the same string, let's move to the next
194 code = (code + 1) % hash_table->size;
197 /* This string was not already in there, store the index in the
198 table and return -1 */
200 hash_table->entries[code] = new_index;
204 /*********************************************************************
205 A matcher matches either with a collection of substrings, or with a
213 char *splitted_patterns, **patterns;
216 int match(char *string, matcher_t *matcher) {
218 if(matcher->nb_patterns >= 0) {
219 if(matcher->case_sensitive) {
220 for(n = 0; n < matcher->nb_patterns; n++) {
221 if(strstr(string, matcher->patterns[n]) == 0) return 0;
224 for(n = 0; n < matcher->nb_patterns; n++) {
225 if(strcasestr(string, matcher->patterns[n]) == 0) return 0;
230 return regexec(&matcher->preg, string, 0, 0, 0) == 0;
234 void free_matcher(matcher_t *matcher) {
235 if(matcher->nb_patterns < 0) {
236 if(!matcher->regexp_error) regfree(&matcher->preg);
238 free(matcher->splitted_patterns);
239 free(matcher->patterns);
243 void initialize_matcher(int use_regexp, int case_sensitive,
244 matcher_t *matcher, const char *pattern) {
246 char *t, *last_pattern_start;
250 matcher->nb_patterns = -1;
251 matcher->regexp_error = regcomp(&matcher->preg, pattern, case_sensitive ? 0 : REG_ICASE);
253 matcher->regexp_error = 0;
254 matcher->nb_patterns = 1;
255 matcher->case_sensitive = case_sensitive;
257 for(s = pattern; *s; s++) {
258 if(*s == pattern_separator) {
259 matcher->nb_patterns++;
263 matcher->splitted_patterns = (char *) malloc((strlen(pattern) + 1) * sizeof(char));
264 matcher->patterns = (char **) malloc(matcher->nb_patterns * sizeof(char *));
266 strcpy(matcher->splitted_patterns, pattern);
269 last_pattern_start = matcher->splitted_patterns;
270 for(t = matcher->splitted_patterns; n < matcher->nb_patterns; t++) {
271 if(*t == pattern_separator || *t == '\0') {
273 matcher->patterns[n++] = last_pattern_start;
274 last_pattern_start = t + 1;
280 /*********************************************************************
283 void delete_char(char *buffer, int *position) {
284 if(buffer[*position]) {
286 while(c < BUFFER_SIZE && buffer[c]) {
287 buffer[c] = buffer[c+1];
290 } else error_feedback();
293 void backspace_char(char *buffer, int *position) {
295 if(buffer[*position]) {
296 int c = *position - 1;
298 buffer[c] = buffer[c+1];
302 buffer[*position - 1] = '\0';
306 } else error_feedback();
309 void insert_char(char *buffer, int *position, char character) {
310 if(strlen(buffer) < BUFFER_SIZE - 1) {
312 char t = buffer[c], u;
321 buffer[(*position)++] = character;
322 } else error_feedback();
325 void kill_before_cursor(char *buffer, int *position) {
327 while(buffer[*position + s]) {
328 buffer[s] = buffer[*position + s];
335 void kill_after_cursor(char *buffer, int *position) {
336 buffer[*position] = '\0';
339 /*********************************************************************/
341 int previous_visible(int current_line, int nb_lines, char **lines, matcher_t *matcher) {
342 int line = current_line - 1;
343 while(line >= 0 && !match(lines[line], matcher)) line--;
347 int next_visible(int current_line, int nb_lines, char **lines, matcher_t *matcher) {
348 int line = current_line + 1;
349 while(line < nb_lines && !match(lines[line], matcher)) line++;
357 /*********************************************************************/
359 /* The value passed to this routine in current_focus_line is the index
360 of the line we should have highlighted if there was no motion and if
361 it matched the matcher. So, the line actually highlighted is the
362 first one matching the matcher in that order: (1)
363 current_focus_line after motion, (2) the first with a greater
364 index, (3) the first with a lesser index.
366 The index of the line actually shown highlighted is written in
367 displayed_focus_line (it can be -1)
369 If there is a motion and a line is actually shown highlighted, its
370 value is written in current_focus_line. */
372 void update_screen(int *current_focus_line, int *displayed_focus_line,
374 int nb_lines, char **lines,
378 char buffer[BUFFER_SIZE];
381 int console_width, console_height;
382 int nb_printed_lines = 0;
385 initialize_matcher(use_regexp, case_sensitive, &matcher, pattern);
387 console_width = getmaxx(stdscr);
388 console_height = getmaxy(stdscr);
390 use_default_colors();
394 /* First, we find a visible line. */
396 if(matcher.regexp_error) {
398 addnstr("Regexp syntax error", console_width);
400 } else if(nb_lines > 0) {
402 if(match(lines[*current_focus_line], &matcher)) {
403 new_focus_line = *current_focus_line;
405 new_focus_line = next_visible(*current_focus_line, nb_lines, lines, &matcher);
406 if(new_focus_line < 0) {
407 new_focus_line = previous_visible(*current_focus_line, nb_lines, lines, &matcher);
411 /* If we found a visible line and we should move, let's move */
413 if(new_focus_line >= 0 && motion != 0) {
414 int l = new_focus_line;
416 /* We want to go down, let's find the first visible line below */
417 for(m = 0; l >= 0 && m < motion; m++) {
418 l = next_visible(l, nb_lines, lines, &matcher);
424 /* We want to go up, let's find the first visible line above */
425 for(m = 0; l >= 0 && m < -motion; m++) {
426 l = previous_visible(l, nb_lines, lines, &matcher);
434 /* Here new_focus_line is either a line number matching the pattern, or -1 */
436 if(new_focus_line >= 0) {
438 int first_line = new_focus_line, last_line = new_focus_line, nb_match = 1;
440 /* We find the first and last line to show, so that the total of
441 visible lines between them (them included) is
444 while(nb_match < console_height-1 && (first_line > 0 || last_line < nb_lines - 1)) {
448 while(first_line > 0 && !match(lines[first_line], &matcher)) {
451 if(match(lines[first_line], &matcher)) {
456 if(nb_match < console_height - 1 && last_line < nb_lines - 1) {
458 while(last_line < nb_lines - 1 && !match(lines[last_line], &matcher)) {
462 if(match(lines[last_line], &matcher)) {
468 /* Now we display them */
470 for(l = first_line; l <= last_line; l++) {
471 if(match(lines[l], &matcher)) {
474 while(lines[l][k] && k < BUFFER_SIZE - 2 && k < console_width - 2) {
475 buffer[k] = lines[l][k];
479 /* We fill the rest of the line with blanks if this is the
482 if(l == new_focus_line) {
483 while(k < console_width) {
493 /* Highlight the highlighted line ... */
495 if(l == new_focus_line) {
496 attron(attr_focus_line);
497 addnstr(buffer, console_width);
498 attroff(attr_focus_line);
500 addnstr(buffer, console_width);
507 /* If we are on a focused line and we moved, this become the new
511 *current_focus_line = new_focus_line;
515 *displayed_focus_line = new_focus_line;
517 if(nb_printed_lines == 0) {
519 addnstr("No selection", console_width);
524 addnstr("Empty choice", console_width);
530 /* Draw the modeline */
534 attron(attr_modeline);
536 for(k = 0; k < console_width; k++) buffer[k] = ' ';
537 buffer[console_width] = '\0';
538 addnstr(buffer, console_width);
542 /* There must be a more elegant way of moving the cursor at a
543 location met during display */
550 cursor_x += strlen(title) + 1;
553 sprintf(buffer, "%d/%d ", nb_printed_lines, nb_lines);
555 cursor_x += strlen(buffer);
557 addnstr(pattern, cursor_position);
558 cursor_x += cursor_position;
560 if(pattern[cursor_position]) {
561 addstr(pattern + cursor_position);
566 if(use_regexp || case_sensitive) {
583 attroff(attr_modeline);
588 free_matcher(&matcher);
591 /*********************************************************************/
593 void store_line(hash_table_t *hash_table,
595 int nb_lines_max, int *nb_lines, char **lines) {
598 /* Remove the zsh history prefix */
600 if(zsh_history && *t == ':') {
601 while(*t && *t != ';') t++;
605 /* Remove the bash history prefix */
608 while(*t == ' ') t++;
609 while(*t >= '0' && *t <= '9') t++;
610 while(*t == ' ') t++;
613 /* Check for duplicates with the hash table and insert the line in
614 the list if necessary */
617 dup = add_and_get_previous_index(hash_table, t, *nb_lines, lines);
623 lines[*nb_lines] = (char *) malloc((strlen(t) + 1) * sizeof(char));
624 strcpy(lines[*nb_lines], t);
626 /* The string was already in there, so we do not allocate a new
627 string but use the pointer to the first occurence of it */
628 lines[*nb_lines] = lines[dup];
635 void read_file(hash_table_t *hash_table,
636 const char *input_filename,
637 int nb_lines_max, int *nb_lines, char **lines) {
639 char raw_line[BUFFER_SIZE];
643 file = fopen(input_filename, "r");
646 fprintf(stderr, "Selector: Can not open `%s'.\n", input_filename);
653 while(*nb_lines < nb_lines_max && (end > start || !feof(file))) {
655 while(eol < end && raw_line[eol] != '\n') eol++;
658 for(k = 0; k < end - start; k++) {
659 raw_line[k] = raw_line[k + start];
664 end += fread(raw_line + end, sizeof(char), BUFFER_SIZE - end, file);
665 while(eol < end && raw_line[eol] != '\n') eol++;
668 if(eol == BUFFER_SIZE) {
669 raw_line[BUFFER_SIZE - 1] = '\0';
670 fprintf(stderr, "Selector: Line too long (max is %d characters):\n", BUFFER_SIZE);
671 fprintf(stderr, raw_line);
672 fprintf(stderr, "\n");
676 raw_line[eol] = '\0';
678 store_line(hash_table, raw_line + start,
679 nb_lines_max, nb_lines, lines);
687 /*********************************************************************/
689 int main(int argc, char **argv) {
691 char input_filename[BUFFER_SIZE], output_filename[BUFFER_SIZE];
692 char pattern[BUFFER_SIZE];
695 int error = 0, show_help = 0;
696 int rest_are_files = 0;
698 int current_focus_line, displayed_focus_line;
700 int color_fg_modeline, color_bg_modeline;
701 int color_fg_highlight, color_bg_highlight;
703 char **lines, **labels;
705 hash_table_t *hash_table;
707 if(!ttyname(STDIN_FILENO)) {
708 fprintf(stderr, "Selector: The standard input is not a tty.\n");
712 color_fg_modeline = COLOR_WHITE;
713 color_bg_modeline = COLOR_BLACK;
714 color_fg_highlight = COLOR_BLACK;
715 color_bg_highlight = COLOR_YELLOW;
717 setlocale(LC_ALL, "");
719 strcpy(input_filename, "");
720 strcpy(output_filename, "");
723 while(!error && !show_help && i < argc && argv[i][0] == '-' && !rest_are_files) {
725 if(strcmp(argv[i], "-o") == 0) {
726 check_opt(argc, argv, i, 1, "<output filename>");
727 strncpy(output_filename, argv[i+1], BUFFER_SIZE);
731 else if(strcmp(argv[i], "-s") == 0) {
732 check_opt(argc, argv, i, 1, "<pattern separator>");
733 pattern_separator = argv[i+1][0];
737 else if(strcmp(argv[i], "-x") == 0) {
738 check_opt(argc, argv, i, 1, "<label separator>");
739 label_separator = argv[i+1][0];
743 else if(strcmp(argv[i], "-v") == 0) {
744 output_to_vt_buffer = 1;
748 else if(strcmp(argv[i], "-w") == 0) {
753 else if(strcmp(argv[i], "-m") == 0) {
758 else if(strcmp(argv[i], "-q") == 0) {
763 else if(strcmp(argv[i], "-f") == 0) {
764 check_opt(argc, argv, i, 1, "<input filename>");
765 strncpy(input_filename, argv[i+1], BUFFER_SIZE);
769 else if(strcmp(argv[i], "-i") == 0) {
774 else if(strcmp(argv[i], "-b") == 0) {
779 else if(strcmp(argv[i], "-z") == 0) {
784 else if(strcmp(argv[i], "-d") == 0) {
785 remove_duplicates = 1;
789 else if(strcmp(argv[i], "-e") == 0) {
794 else if(strcmp(argv[i], "-a") == 0) {
799 else if(strcmp(argv[i], "-t") == 0) {
800 check_opt(argc, argv, i, 1, "<title>");
802 title = (char *) malloc((strlen(argv[i+1]) + 1) * sizeof(char));
803 strcpy(title, argv[i+1]);
807 else if(strcmp(argv[i], "-l") == 0) {
808 check_opt(argc, argv, i, 1, "<maximum number of lines>");
809 nb_lines_max = string_to_positive_integer(argv[i+1]);
813 else if(strcmp(argv[i], "-c") == 0) {
814 check_opt(argc, argv, i, 4, "<fg modeline> <bg modeline> <fg highlight> <bg highlight>");
815 color_fg_modeline = string_to_positive_integer(argv[i + 1]);
816 color_bg_modeline = string_to_positive_integer(argv[i + 2]);
817 color_fg_highlight = string_to_positive_integer(argv[i + 3]);
818 color_bg_highlight = string_to_positive_integer(argv[i + 4]);
822 else if(strcmp(argv[i], "--") == 0) {
827 else if(strcmp(argv[i], "-h") == 0) {
833 fprintf(stderr, "Selector: Unknown option %s.\n", argv[i]);
838 if(show_help || error) {
846 fprintf(out, "Selector version %s-R%s\n", VERSION, REVISION_NUMBER);
847 fprintf(out, "Written by Francois Fleuret <francois@fleuret.org>.\n");
849 fprintf(out, "Usage: %s [options] [<filename1> [<filename2> ...]]\n", argv[0]);
851 fprintf(out, " -h show this help\n");
852 fprintf(out, " -v inject the selected line in the tty\n");
853 fprintf(out, " -w quote control characters with ^Qs when using -v\n");
854 fprintf(out, " -d remove duplicated lines\n");
855 fprintf(out, " -b remove the bash history line prefix\n");
856 fprintf(out, " -z remove the zsh history line prefix\n");
857 fprintf(out, " -i invert the order of lines\n");
858 fprintf(out, " -e start in regexp mode\n");
859 fprintf(out, " -a start in case sensitive mode\n");
860 fprintf(out, " -m monochrome mode\n");
861 fprintf(out, " -q make a flash instead of a beep on an edition error\n");
862 fprintf(out, " -- all following arguments are filenames\n");
863 fprintf(out, " -t <title>\n");
864 fprintf(out, " add a title in the modeline\n");
865 fprintf(out, " -c <fg modeline> <bg modeline> <fg highlight> <bg highlight>\n");
866 fprintf(out, " set the display colors\n");
867 fprintf(out, " -o <output filename>\n");
868 fprintf(out, " set a file to write the selected line to\n");
869 fprintf(out, " -s <pattern separator>\n");
870 fprintf(out, " set the symbol to separate substrings in the pattern\n");
871 fprintf(out, " -x <label separator>\n");
872 fprintf(out, " set the symbol to terminate the label\n");
873 fprintf(out, " -l <max number of lines>\n");
874 fprintf(out, " set the maximum number of lines to take into account\n");
879 lines = (char **) malloc(nb_lines_max * sizeof(char *));
883 if(remove_duplicates) {
884 hash_table = new_hash_table(nb_lines_max * 10);
889 if(input_filename[0]) {
890 read_file(hash_table,
892 nb_lines_max, &nb_lines, lines);
896 read_file(hash_table,
898 nb_lines_max, &nb_lines, lines);
903 free_hash_table(hash_table);
906 /* Now remove the null strings */
909 for(k = 0; k < nb_lines; k++) {
911 lines[n++] = lines[k];
918 for(i = 0; i < nb_lines / 2; i++) {
919 char *s = lines[nb_lines - 1 - i];
920 lines[nb_lines - 1 - i] = lines[i];
925 /* Build the labels from the strings, take only the part before the
926 label_separator and transform control characters to printable
929 labels = (char **) malloc(nb_lines * sizeof(char *));
931 for(l = 0; l < nb_lines; l++) {
936 while(*t && *t != label_separator) {
940 labels[l] = (char *) malloc((e + 1) * sizeof(char));
943 while(*t && *t != label_separator) {
945 while(*u) { *s++ = *u++; }
954 /* Here we start to display with curse */
960 intrflush(stdscr, FALSE);
962 /* So that the arrow keys work */
963 keypad(stdscr, TRUE);
965 attr_error = A_STANDOUT;
966 attr_modeline = A_REVERSE;
967 attr_focus_line = A_STANDOUT;
969 if(with_colors && has_colors()) {
973 if(color_fg_modeline < 0 || color_fg_modeline >= COLORS ||
974 color_bg_modeline < 0 || color_bg_modeline >= COLORS ||
975 color_fg_highlight < 0 || color_bg_highlight >= COLORS ||
976 color_bg_highlight < 0 || color_bg_highlight >= COLORS) {
979 fprintf(stderr, "Selector: Color numbers have to be between 0 and %d.\n", COLORS - 1);
983 init_pair(1, color_fg_modeline, color_bg_modeline);
984 attr_modeline = COLOR_PAIR(1);
986 init_pair(2, color_fg_highlight, color_bg_highlight);
987 attr_focus_line = COLOR_PAIR(2);
989 init_pair(3, COLOR_WHITE, COLOR_RED);
990 attr_error = COLOR_PAIR(3);
994 current_focus_line = 0;
995 displayed_focus_line = 0;
997 update_screen(¤t_focus_line, &displayed_focus_line,
999 nb_lines, labels, cursor_position, pattern);
1006 if(key >= ' ' && key <= '~') { /* Insert character */
1007 insert_char(pattern, &cursor_position, key);
1010 else if(key == KEY_BACKSPACE ||
1011 key == '\010' || /* ^H */
1012 key == '\177') { /* ^? */
1013 backspace_char(pattern, &cursor_position);
1016 else if(key == KEY_DC ||
1017 key == '\004') { /* ^D */
1018 delete_char(pattern, &cursor_position);
1021 else if(key == KEY_HOME) {
1022 current_focus_line = 0;
1025 else if(key == KEY_END) {
1026 current_focus_line = nb_lines - 1;
1029 else if(key == KEY_NPAGE) {
1033 else if(key == KEY_PPAGE) {
1037 else if(key == KEY_DOWN ||
1038 key == '\016') { /* ^N */
1042 else if(key == KEY_UP ||
1043 key == '\020') { /* ^P */
1047 else if(key == KEY_LEFT ||
1048 key == '\002') { /* ^B */
1049 if(cursor_position > 0) cursor_position--;
1050 else error_feedback();
1053 else if(key == KEY_RIGHT ||
1054 key == '\006') { /* ^F */
1055 if(pattern[cursor_position]) cursor_position++;
1056 else error_feedback();
1059 else if(key == '\001') { /* ^A */
1060 cursor_position = 0;
1063 else if(key == '\005') { /* ^E */
1064 cursor_position = strlen(pattern);
1067 else if(key == '\022') { /* ^R */
1068 use_regexp = !use_regexp;
1071 else if(key == '\011') { /* ^I */
1072 case_sensitive = !case_sensitive;
1075 else if(key == '\025') { /* ^U */
1076 kill_before_cursor(pattern, &cursor_position);
1079 else if(key == '\013') { /* ^K */
1080 kill_after_cursor(pattern, &cursor_position);
1083 else if(key == '\014') { /* ^L */
1084 /* I suspect that we may sometime mess up the display */
1088 update_screen(¤t_focus_line, &displayed_focus_line,
1090 nb_lines, labels, cursor_position, pattern);
1092 } while(key != '\007' && /* ^G */
1093 key != '\033' && /* ^[ (escape) */
1100 /* Here we come back to standard display */
1102 if((key == KEY_ENTER || key == '\n')) {
1106 if(displayed_focus_line >= 0 && displayed_focus_line < nb_lines) {
1107 t = lines[displayed_focus_line];
1108 if(label_separator) {
1109 while(*t && *t != label_separator) t++;
1116 if(output_to_vt_buffer && t) {
1117 inject_into_tty_buffer(t);
1120 if(output_filename[0]) {
1121 FILE *out = fopen(output_filename, "w");
1128 fprintf(stderr, "Selector: Can not open %s for writing.\n", output_filename);
1135 printf("Aborted.\n");
1138 for(l = 0; l < nb_lines; l++) {