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, "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, "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, "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, "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, "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, "Unknown option %s.\n", argv[i]);
838 if(show_help || error) {
839 fprintf(stderr, "Selector version %s-R%s\n", VERSION, REVISION_NUMBER);
840 fprintf(stderr, "Written by Francois Fleuret <francois@fleuret.org>.\n");
841 fprintf(stderr, "Usage: %s [options] [<filename1> [<filename2> ...]]\n", argv[0]);
842 fprintf(stderr, "\n");
843 fprintf(stderr, " -h show this help\n");
844 fprintf(stderr, " -v inject the selected line in the tty\n");
845 fprintf(stderr, " -w quote control characters with ^Qs when using -v\n");
846 fprintf(stderr, " -d remove duplicated lines\n");
847 fprintf(stderr, " -b remove the bash history line prefix\n");
848 fprintf(stderr, " -z remove the zsh history line prefix\n");
849 fprintf(stderr, " -i invert the order of lines\n");
850 fprintf(stderr, " -e start in regexp mode\n");
851 fprintf(stderr, " -a start in case sensitive mode\n");
852 fprintf(stderr, " -m monochrome mode\n");
853 fprintf(stderr, " -q make a flash instead of a beep on an edition error\n");
854 fprintf(stderr, " -- all following arguments are filenames\n");
855 fprintf(stderr, " -t <title>\n");
856 fprintf(stderr, " add a title in the modeline\n");
857 fprintf(stderr, " -c <fg modeline> <bg modeline> <fg highlight> <bg highlight>\n");
858 fprintf(stderr, " set the display colors\n");
859 fprintf(stderr, " -o <output filename>\n");
860 fprintf(stderr, " set a file to write the selected line to\n");
861 fprintf(stderr, " -s <pattern separator>\n");
862 fprintf(stderr, " set the symbol to separate substrings in the pattern\n");
863 fprintf(stderr, " -x <label separator>\n");
864 fprintf(stderr, " set the symbol to terminate the label\n");
865 fprintf(stderr, " -l <max number of lines>\n");
866 fprintf(stderr, " set the maximum number of lines to take into account\n");
867 fprintf(stderr, "\n");
871 lines = (char **) malloc(nb_lines_max * sizeof(char *));
875 if(remove_duplicates) {
876 hash_table = new_hash_table(nb_lines_max * 10);
881 if(input_filename[0]) {
882 read_file(hash_table,
884 nb_lines_max, &nb_lines, lines);
888 read_file(hash_table,
890 nb_lines_max, &nb_lines, lines);
895 free_hash_table(hash_table);
898 /* Now remove the null strings */
901 for(k = 0; k < nb_lines; k++) {
903 lines[n++] = lines[k];
910 for(i = 0; i < nb_lines / 2; i++) {
911 char *s = lines[nb_lines - 1 - i];
912 lines[nb_lines - 1 - i] = lines[i];
917 /* Build the labels from the strings, take only the part before the
918 label_separator and transform control characters to printable
921 labels = (char **) malloc(nb_lines * sizeof(char *));
923 for(l = 0; l < nb_lines; l++) {
928 while(*t && *t != label_separator) {
932 labels[l] = (char *) malloc((e + 1) * sizeof(char));
935 while(*t && *t != label_separator) {
937 while(*u) { *s++ = *u++; }
946 /* Here we start to display with curse */
952 intrflush(stdscr, FALSE);
954 /* So that the arrow keys work */
955 keypad(stdscr, TRUE);
957 attr_error = A_STANDOUT;
958 attr_modeline = A_REVERSE;
959 attr_focus_line = A_STANDOUT;
961 if(with_colors && has_colors()) {
965 if(color_fg_modeline < 0 || color_fg_modeline >= COLORS ||
966 color_bg_modeline < 0 || color_bg_modeline >= COLORS ||
967 color_fg_highlight < 0 || color_bg_highlight >= COLORS ||
968 color_bg_highlight < 0 || color_bg_highlight >= COLORS) {
971 fprintf(stderr, "Color numbers have to be between 0 and %d.\n", COLORS - 1);
975 init_pair(1, color_fg_modeline, color_bg_modeline);
976 attr_modeline = COLOR_PAIR(1);
978 init_pair(2, color_fg_highlight, color_bg_highlight);
979 attr_focus_line = COLOR_PAIR(2);
981 init_pair(3, COLOR_WHITE, COLOR_RED);
982 attr_error = COLOR_PAIR(3);
986 current_focus_line = 0;
987 displayed_focus_line = 0;
989 update_screen(¤t_focus_line, &displayed_focus_line,
991 nb_lines, labels, cursor_position, pattern);
998 if(key >= ' ' && key <= '~') { /* Insert character */
999 insert_char(pattern, &cursor_position, key);
1002 else if(key == KEY_BACKSPACE ||
1003 key == '\010' || /* ^H */
1004 key == '\177') { /* ^? */
1005 backspace_char(pattern, &cursor_position);
1008 else if(key == KEY_DC ||
1009 key == '\004') { /* ^D */
1010 delete_char(pattern, &cursor_position);
1013 else if(key == KEY_HOME) {
1014 current_focus_line = 0;
1017 else if(key == KEY_END) {
1018 current_focus_line = nb_lines - 1;
1021 else if(key == KEY_NPAGE) {
1025 else if(key == KEY_PPAGE) {
1029 else if(key == KEY_DOWN ||
1030 key == '\016') { /* ^N */
1034 else if(key == KEY_UP ||
1035 key == '\020') { /* ^P */
1039 else if(key == KEY_LEFT ||
1040 key == '\002') { /* ^B */
1041 if(cursor_position > 0) cursor_position--;
1042 else error_feedback();
1045 else if(key == KEY_RIGHT ||
1046 key == '\006') { /* ^F */
1047 if(pattern[cursor_position]) cursor_position++;
1048 else error_feedback();
1051 else if(key == '\001') { /* ^A */
1052 cursor_position = 0;
1055 else if(key == '\005') { /* ^E */
1056 cursor_position = strlen(pattern);
1059 else if(key == '\022') { /* ^R */
1060 use_regexp = !use_regexp;
1063 else if(key == '\011') { /* ^I */
1064 case_sensitive = !case_sensitive;
1067 else if(key == '\025') { /* ^U */
1068 kill_before_cursor(pattern, &cursor_position);
1071 else if(key == '\013') { /* ^K */
1072 kill_after_cursor(pattern, &cursor_position);
1075 else if(key == '\014') { /* ^L */
1076 /* I suspect that we may sometime mess up the display */
1080 update_screen(¤t_focus_line, &displayed_focus_line,
1082 nb_lines, labels, cursor_position, pattern);
1084 } while(key != '\007' && /* ^G */
1085 key != '\033' && /* ^[ (escape) */
1092 /* Here we come back to standard display */
1094 if((key == KEY_ENTER || key == '\n')) {
1098 if(displayed_focus_line >= 0 && displayed_focus_line < nb_lines) {
1099 t = lines[displayed_focus_line];
1100 if(label_separator) {
1101 while(*t && *t != label_separator) t++;
1108 if(output_to_vt_buffer && t) {
1109 inject_into_tty_buffer(t);
1112 if(output_filename[0]) {
1113 FILE *out = fopen(output_filename, "w");
1120 fprintf(stderr, "Can not open %s for writing.\n", output_filename);
1127 printf("Aborted.\n");
1130 for(l = 0; l < nb_lines; l++) {