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 /*********************************************************************
130 A quick and dirty hash table
132 The table itself stores indexes of the strings taken in a char
133 **table. When a string is added, if it was already in the table, the
134 new index replaces the previous one. */
136 int *new_hash_table(int hash_table_size) {
138 result = (int *) malloc(hash_table_size * sizeof(int));
139 for(k = 0; k < hash_table_size; k++) {
145 /* Adds new_string in the table, associated to new_index. If this
146 string was not already in the table, returns -1. Otherwise, returns
147 the previous index it had. */
149 int add_and_get_previous_index(const char *new_string, int new_index,
151 int *hash_table, int hash_table_size) {
153 unsigned int code = 0;
156 /* This is my recipe. I checked, it seems to work (as long as
157 hash_table_size is not a multiple of 387433 that should be
160 for(k = 0; new_string[k]; k++) {
161 code = code * 387433 + (unsigned int) (new_string[k]);
164 code = code % hash_table_size;
166 while(hash_table[code] >= 0) {
167 /* There is a string with that code */
168 if(strcmp(new_string, strings[hash_table[code]]) == 0) {
169 /* It is the same string, we keep a copy of the stored index */
170 int result = hash_table[code];
171 /* Put the new one */
172 hash_table[code] = new_index;
173 /* And return the previous one */
176 /* This collision was not the same string, let's move to the next
178 code = (code + 1) % hash_table_size;
181 /* This string was not already in there, store the index in the
182 table and return -1 */
184 hash_table[code] = new_index;
188 /*********************************************************************
189 A matcher matches either with a collection of substrings, or with a
197 char *splitted_patterns, **patterns;
200 int match(char *string, matcher_t *matcher) {
202 if(matcher->nb_patterns >= 0) {
203 if(matcher->case_sensitive) {
204 for(n = 0; n < matcher->nb_patterns; n++) {
205 if(strstr(string, matcher->patterns[n]) == 0) return 0;
208 for(n = 0; n < matcher->nb_patterns; n++) {
209 if(strcasestr(string, matcher->patterns[n]) == 0) return 0;
214 return regexec(&matcher->preg, string, 0, 0, 0) == 0;
218 void free_matcher(matcher_t *matcher) {
219 if(matcher->nb_patterns < 0) {
220 if(!matcher->regexp_error) regfree(&matcher->preg);
222 free(matcher->splitted_patterns);
223 free(matcher->patterns);
227 void initialize_matcher(int use_regexp, int case_sensitive,
228 matcher_t *matcher, const char *pattern) {
230 char *t, *last_pattern_start;
234 matcher->nb_patterns = -1;
235 matcher->regexp_error = regcomp(&matcher->preg, pattern, case_sensitive ? 0 : REG_ICASE);
237 matcher->regexp_error = 0;
238 matcher->nb_patterns = 1;
239 matcher->case_sensitive = case_sensitive;
241 for(s = pattern; *s; s++) {
242 if(*s == pattern_separator) {
243 matcher->nb_patterns++;
247 matcher->splitted_patterns = (char *) malloc((strlen(pattern) + 1) * sizeof(char));
248 matcher->patterns = (char **) malloc(matcher->nb_patterns * sizeof(char *));
250 strcpy(matcher->splitted_patterns, pattern);
253 last_pattern_start = matcher->splitted_patterns;
254 for(t = matcher->splitted_patterns; n < matcher->nb_patterns; t++) {
255 if(*t == pattern_separator || *t == '\0') {
257 matcher->patterns[n++] = last_pattern_start;
258 last_pattern_start = t + 1;
264 /*********************************************************************
267 void delete_char(char *buffer, int *position) {
268 if(buffer[*position]) {
270 while(c < BUFFER_SIZE && buffer[c]) {
271 buffer[c] = buffer[c+1];
274 } else error_feedback();
277 void backspace_char(char *buffer, int *position) {
279 if(buffer[*position]) {
280 int c = *position - 1;
282 buffer[c] = buffer[c+1];
286 buffer[*position - 1] = '\0';
290 } else error_feedback();
293 void insert_char(char *buffer, int *position, char character) {
294 if(strlen(buffer) < BUFFER_SIZE - 1) {
296 char t = buffer[c], u;
305 buffer[(*position)++] = character;
306 } else error_feedback();
309 void kill_before_cursor(char *buffer, int *position) {
311 while(buffer[*position + s]) {
312 buffer[s] = buffer[*position + s];
319 void kill_after_cursor(char *buffer, int *position) {
320 buffer[*position] = '\0';
323 /*********************************************************************/
325 int previous_visible(int current_line, int nb_lines, char **lines, matcher_t *matcher) {
326 int line = current_line - 1;
327 while(line >= 0 && !match(lines[line], matcher)) line--;
331 int next_visible(int current_line, int nb_lines, char **lines, matcher_t *matcher) {
332 int line = current_line + 1;
333 while(line < nb_lines && !match(lines[line], matcher)) line++;
341 /*********************************************************************/
343 /* The value passed to this routine in current_focus_line is the index
344 of the line we should have highlighted if there was no motion and if
345 it matched the matcher. So, the line actually highlighted is the
346 first one matching the matcher in that order: (1)
347 current_focus_line after motion, (2) the first with a greater
348 index, (3) the first with a lesser index.
350 The index of the line actually shown highlighted is written in
351 displayed_focus_line (it can be -1)
353 If there is a motion and a line is actually shown highlighted, its
354 value is written in current_focus_line. */
356 void update_screen(int *current_focus_line, int *displayed_focus_line,
358 int nb_lines, char **lines,
362 char buffer[BUFFER_SIZE];
365 int console_width, console_height;
366 int nb_printed_lines = 0;
369 initialize_matcher(use_regexp, case_sensitive, &matcher, pattern);
371 console_width = getmaxx(stdscr);
372 console_height = getmaxy(stdscr);
374 use_default_colors();
378 /* First, we find a visible line. */
380 if(matcher.regexp_error) {
382 addnstr("Regexp syntax error", console_width);
384 } else if(nb_lines > 0) {
386 if(match(lines[*current_focus_line], &matcher)) {
387 new_focus_line = *current_focus_line;
389 new_focus_line = next_visible(*current_focus_line, nb_lines, lines, &matcher);
390 if(new_focus_line < 0) {
391 new_focus_line = previous_visible(*current_focus_line, nb_lines, lines, &matcher);
395 /* If we found a visible line and we should move, let's move */
397 if(new_focus_line >= 0 && motion != 0) {
398 int l = new_focus_line;
400 /* We want to go down, let's find the first visible line below */
401 for(m = 0; l >= 0 && m < motion; m++) {
402 l = next_visible(l, nb_lines, lines, &matcher);
408 /* We want to go up, let's find the first visible line above */
409 for(m = 0; l >= 0 && m < -motion; m++) {
410 l = previous_visible(l, nb_lines, lines, &matcher);
418 /* Here new_focus_line is either a line number matching the pattern, or -1 */
420 if(new_focus_line >= 0) {
422 int first_line = new_focus_line, last_line = new_focus_line, nb_match = 1;
424 /* We find the first and last line to show, so that the total of
425 visible lines between them (them included) is
428 while(nb_match < console_height-1 && (first_line > 0 || last_line < nb_lines - 1)) {
432 while(first_line > 0 && !match(lines[first_line], &matcher)) {
435 if(match(lines[first_line], &matcher)) {
440 if(nb_match < console_height - 1 && last_line < nb_lines - 1) {
442 while(last_line < nb_lines - 1 && !match(lines[last_line], &matcher)) {
446 if(match(lines[last_line], &matcher)) {
452 /* Now we display them */
454 for(l = first_line; l <= last_line; l++) {
455 if(match(lines[l], &matcher)) {
458 while(lines[l][k] && k < BUFFER_SIZE - 2 && k < console_width - 2) {
459 buffer[k] = lines[l][k];
463 /* We fill the rest of the line with blanks if this is the
466 if(l == new_focus_line) {
467 while(k < console_width) {
477 /* Highlight the highlighted line ... */
479 if(l == new_focus_line) {
480 attron(attr_focus_line);
481 addnstr(buffer, console_width);
482 attroff(attr_focus_line);
484 addnstr(buffer, console_width);
491 /* If we are on a focused line and we moved, this become the new
495 *current_focus_line = new_focus_line;
499 *displayed_focus_line = new_focus_line;
501 if(nb_printed_lines == 0) {
503 addnstr("No selection", console_width);
508 addnstr("Empty choice", console_width);
514 /* Draw the modeline */
518 attron(attr_modeline);
520 for(k = 0; k < console_width; k++) buffer[k] = ' ';
521 buffer[console_width] = '\0';
522 addnstr(buffer, console_width);
526 /* There must be a more elegant way of moving the cursor at a
527 location met during display */
534 cursor_x += strlen(title) + 1;
537 sprintf(buffer, "%d/%d ", nb_printed_lines, nb_lines);
539 cursor_x += strlen(buffer);
541 addnstr(pattern, cursor_position);
542 cursor_x += cursor_position;
544 if(pattern[cursor_position]) {
545 addstr(pattern + cursor_position);
550 if(use_regexp || case_sensitive) {
567 attroff(attr_modeline);
572 free_matcher(&matcher);
575 /*********************************************************************/
577 void store_line(const char *t,
578 int nb_lines_max, int *nb_lines, char **lines,
579 int hash_table_size, int *hash_table) {
582 /* Remove the zsh history prefix */
584 if(zsh_history && *t == ':') {
585 while(*t && *t != ';') t++;
589 /* Remove the bash history prefix */
592 while(*t == ' ') t++;
593 while(*t >= '0' && *t <= '9') t++;
594 while(*t == ' ') t++;
597 /* Check for duplicates with the hash table and insert the line in
598 the list if necessary */
601 dup = add_and_get_previous_index(t, *nb_lines, lines, hash_table, hash_table_size);
607 lines[*nb_lines] = (char *) malloc((strlen(t) + 1) * sizeof(char));
608 strcpy(lines[*nb_lines], t);
610 /* The string was already in there, so we do not allocate a new
611 string but use the pointer to the first occurence of it */
612 lines[*nb_lines] = lines[dup];
619 void read_file(const char *input_filename,
620 int nb_lines_max, int *nb_lines, char **lines,
621 int hash_table_size, int *hash_table) {
623 char raw_line[BUFFER_SIZE];
627 file = fopen(input_filename, "r");
630 fprintf(stderr, "Can not open `%s'.\n", input_filename);
637 while(*nb_lines < nb_lines_max && (end > start || !feof(file))) {
639 while(eol < end && raw_line[eol] != '\n') eol++;
642 for(k = 0; k < end - start; k++) {
643 raw_line[k] = raw_line[k + start];
648 end += fread(raw_line + end, sizeof(char), BUFFER_SIZE - end, file);
649 while(eol < end && raw_line[eol] != '\n') eol++;
652 if(eol == BUFFER_SIZE) {
653 raw_line[BUFFER_SIZE - 1] = '\0';
654 fprintf(stderr, "Line too long (max is %d characters):\n", BUFFER_SIZE);
655 fprintf(stderr, raw_line);
656 fprintf(stderr, "\n");
660 raw_line[eol] = '\0';
662 store_line(raw_line + start,
663 nb_lines_max, nb_lines, lines,
664 hash_table_size, hash_table);
672 /*********************************************************************/
674 int main(int argc, char **argv) {
676 char input_filename[BUFFER_SIZE], output_filename[BUFFER_SIZE];
677 char pattern[BUFFER_SIZE];
680 int error = 0, show_help = 0;
681 int rest_are_files = 0;
683 int current_focus_line, displayed_focus_line;
685 int color_fg_modeline, color_bg_modeline;
686 int color_fg_highlight, color_bg_highlight;
688 char **lines, **labels;
689 int nb_lines, hash_table_size, *hash_table;
691 if(!ttyname(STDIN_FILENO)) {
692 fprintf(stderr, "The standard input is not a tty.\n");
696 color_fg_modeline = COLOR_WHITE;
697 color_bg_modeline = COLOR_BLACK;
698 color_fg_highlight = COLOR_BLACK;
699 color_bg_highlight = COLOR_YELLOW;
701 setlocale(LC_ALL, "");
703 strcpy(input_filename, "");
704 strcpy(output_filename, "");
707 while(!error && !show_help && i < argc && argv[i][0] == '-' && !rest_are_files) {
709 if(strcmp(argv[i], "-o") == 0) {
710 check_opt(argc, argv, i, 1, "<output filename>");
711 strncpy(output_filename, argv[i+1], BUFFER_SIZE);
715 else if(strcmp(argv[i], "-s") == 0) {
716 check_opt(argc, argv, i, 1, "<pattern separator>");
717 pattern_separator = argv[i+1][0];
721 else if(strcmp(argv[i], "-x") == 0) {
722 check_opt(argc, argv, i, 1, "<label separator>");
723 label_separator = argv[i+1][0];
727 else if(strcmp(argv[i], "-v") == 0) {
728 output_to_vt_buffer = 1;
732 else if(strcmp(argv[i], "-w") == 0) {
737 else if(strcmp(argv[i], "-m") == 0) {
742 else if(strcmp(argv[i], "-q") == 0) {
747 else if(strcmp(argv[i], "-f") == 0) {
748 check_opt(argc, argv, i, 1, "<input filename>");
749 strncpy(input_filename, argv[i+1], BUFFER_SIZE);
753 else if(strcmp(argv[i], "-i") == 0) {
758 else if(strcmp(argv[i], "-b") == 0) {
763 else if(strcmp(argv[i], "-z") == 0) {
768 else if(strcmp(argv[i], "-d") == 0) {
769 remove_duplicates = 1;
773 else if(strcmp(argv[i], "-e") == 0) {
778 else if(strcmp(argv[i], "-a") == 0) {
783 else if(strcmp(argv[i], "-t") == 0) {
784 check_opt(argc, argv, i, 1, "<title>");
786 title = (char *) malloc((strlen(argv[i+1]) + 1) * sizeof(char));
787 strcpy(title, argv[i+1]);
791 else if(strcmp(argv[i], "-l") == 0) {
792 check_opt(argc, argv, i, 1, "<maximum number of lines>");
793 nb_lines_max = string_to_positive_integer(argv[i+1]);
797 else if(strcmp(argv[i], "-c") == 0) {
798 check_opt(argc, argv, i, 4, "<fg modeline> <bg modeline> <fg highlight> <bg highlight>");
799 color_fg_modeline = string_to_positive_integer(argv[i + 1]);
800 color_bg_modeline = string_to_positive_integer(argv[i + 2]);
801 color_fg_highlight = string_to_positive_integer(argv[i + 3]);
802 color_bg_highlight = string_to_positive_integer(argv[i + 4]);
806 else if(strcmp(argv[i], "--") == 0) {
811 else if(strcmp(argv[i], "-h") == 0) {
817 fprintf(stderr, "Unknown option %s.\n", argv[i]);
822 if(show_help || error) {
823 fprintf(stderr, "Selector version %s-R%s\n", VERSION, REVISION_NUMBER);
824 fprintf(stderr, "Written by Francois Fleuret <francois@fleuret.org>.\n");
825 fprintf(stderr, "Usage: %s [options] [<filename1> [<filename2> ...]]\n", argv[0]);
826 fprintf(stderr, "\n");
827 fprintf(stderr, " -h show this help\n");
828 fprintf(stderr, " -v inject the selected line in the tty\n");
829 fprintf(stderr, " -w quote control characters with ^Qs when using -v\n");
830 fprintf(stderr, " -d remove duplicated lines\n");
831 fprintf(stderr, " -b remove the bash history line prefix\n");
832 fprintf(stderr, " -z remove the zsh history line prefix\n");
833 fprintf(stderr, " -i invert the order of lines\n");
834 fprintf(stderr, " -e start in regexp mode\n");
835 fprintf(stderr, " -a start in case sensitive mode\n");
836 fprintf(stderr, " -m monochrome mode\n");
837 fprintf(stderr, " -q make a flash instead of a beep on an edition error\n");
838 fprintf(stderr, " -- all following arguments are filenames\n");
839 fprintf(stderr, " -t <title>\n");
840 fprintf(stderr, " add a title in the modeline\n");
841 fprintf(stderr, " -c <fg modeline> <bg modeline> <fg highlight> <bg highlight>\n");
842 fprintf(stderr, " set the display colors\n");
843 fprintf(stderr, " -o <output filename>\n");
844 fprintf(stderr, " set a file to write the selected line to\n");
845 fprintf(stderr, " -s <pattern separator>\n");
846 fprintf(stderr, " set the symbol to separate substrings in the pattern\n");
847 fprintf(stderr, " -x <label separator>\n");
848 fprintf(stderr, " set the symbol to terminate the label\n");
849 fprintf(stderr, " -l <max number of lines>\n");
850 fprintf(stderr, " set the maximum number of lines to take into account\n");
851 fprintf(stderr, "\n");
855 lines = (char **) malloc(nb_lines_max * sizeof(char *));
858 hash_table_size = nb_lines_max * 10;
861 if(remove_duplicates) {
862 hash_table = new_hash_table(hash_table_size);
865 if(input_filename[0]) {
866 read_file(input_filename,
867 nb_lines_max, &nb_lines, lines,
868 hash_table_size, hash_table);
873 nb_lines_max, &nb_lines, lines,
874 hash_table_size, hash_table);
880 /* Now remove the null strings */
883 for(k = 0; k < nb_lines; k++) {
885 lines[n++] = lines[k];
892 for(i = 0; i < nb_lines / 2; i++) {
893 char *s = lines[nb_lines - 1 - i];
894 lines[nb_lines - 1 - i] = lines[i];
899 /* Build the labels from the strings, take only the part before the
900 label_separator and transform control characters to printable
903 labels = (char **) malloc(nb_lines * sizeof(char *));
905 for(l = 0; l < nb_lines; l++) {
910 while(*t && *t != label_separator) {
914 labels[l] = (char *) malloc((e + 1) * sizeof(char));
917 while(*t && *t != label_separator) {
919 while(*u) { *s++ = *u++; }
928 /* Here we start to display with curse */
934 intrflush(stdscr, FALSE);
936 /* So that the arrow keys work */
937 keypad(stdscr, TRUE);
939 attr_error = A_STANDOUT;
940 attr_modeline = A_REVERSE;
941 attr_focus_line = A_STANDOUT;
943 if(with_colors && has_colors()) {
947 if(color_fg_modeline < 0 || color_fg_modeline >= COLORS ||
948 color_bg_modeline < 0 || color_bg_modeline >= COLORS ||
949 color_fg_highlight < 0 || color_bg_highlight >= COLORS ||
950 color_bg_highlight < 0 || color_bg_highlight >= COLORS) {
953 fprintf(stderr, "Color numbers have to be between 0 and %d.\n", COLORS - 1);
957 init_pair(1, color_fg_modeline, color_bg_modeline);
958 attr_modeline = COLOR_PAIR(1);
960 init_pair(2, color_fg_highlight, color_bg_highlight);
961 attr_focus_line = COLOR_PAIR(2);
963 init_pair(3, COLOR_WHITE, COLOR_RED);
964 attr_error = COLOR_PAIR(3);
968 current_focus_line = 0;
969 displayed_focus_line = 0;
971 update_screen(¤t_focus_line, &displayed_focus_line,
973 nb_lines, labels, cursor_position, pattern);
980 if(key >= ' ' && key <= '~') { /* Insert character */
981 insert_char(pattern, &cursor_position, key);
984 else if(key == KEY_BACKSPACE ||
985 key == '\010' || /* ^H */
986 key == '\177') { /* ^? */
987 backspace_char(pattern, &cursor_position);
990 else if(key == KEY_DC ||
991 key == '\004') { /* ^D */
992 delete_char(pattern, &cursor_position);
995 else if(key == KEY_HOME) {
996 current_focus_line = 0;
999 else if(key == KEY_END) {
1000 current_focus_line = nb_lines - 1;
1003 else if(key == KEY_NPAGE) {
1007 else if(key == KEY_PPAGE) {
1011 else if(key == KEY_DOWN ||
1012 key == '\016') { /* ^N */
1016 else if(key == KEY_UP ||
1017 key == '\020') { /* ^P */
1021 else if(key == KEY_LEFT ||
1022 key == '\002') { /* ^B */
1023 if(cursor_position > 0) cursor_position--;
1024 else error_feedback();
1027 else if(key == KEY_RIGHT ||
1028 key == '\006') { /* ^F */
1029 if(pattern[cursor_position]) cursor_position++;
1030 else error_feedback();
1033 else if(key == '\001') { /* ^A */
1034 cursor_position = 0;
1037 else if(key == '\005') { /* ^E */
1038 cursor_position = strlen(pattern);
1041 else if(key == '\022') { /* ^R */
1042 use_regexp = !use_regexp;
1045 else if(key == '\011') { /* ^I */
1046 case_sensitive = !case_sensitive;
1049 else if(key == '\025') { /* ^U */
1050 kill_before_cursor(pattern, &cursor_position);
1053 else if(key == '\013') { /* ^K */
1054 kill_after_cursor(pattern, &cursor_position);
1057 else if(key == '\014') { /* ^L */
1058 /* I suspect that we may sometime mess up the display */
1062 update_screen(¤t_focus_line, &displayed_focus_line,
1064 nb_lines, labels, cursor_position, pattern);
1066 } while(key != '\007' && /* ^G */
1067 key != '\033' && /* ^[ (escape) */
1074 /* Here we come back to standard display */
1076 if((key == KEY_ENTER || key == '\n')) {
1080 if(displayed_focus_line >= 0 && displayed_focus_line < nb_lines) {
1081 t = lines[displayed_focus_line];
1082 if(label_separator) {
1083 while(*t && *t != label_separator) t++;
1090 if(output_to_vt_buffer && t) {
1091 inject_into_tty_buffer(t);
1094 if(output_filename[0]) {
1095 FILE *out = fopen(output_filename, "w");
1102 fprintf(stderr, "Can not open %s for writing.\n", output_filename);
1109 printf("Aborted.\n");
1112 for(l = 0; l < nb_lines; l++) {