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 const int 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 tcgetattr(STDIN_FILENO, &oldtio);
74 memset(&newtio, 0, sizeof(newtio));
75 /* Set input mode (non-canonical, *no echo*,...) */
76 tcsetattr(STDIN_FILENO, TCSANOW, &newtio);
77 const char control_q = '\021';
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) {
233 matcher->nb_patterns = -1;
234 matcher->regexp_error = regcomp(&matcher->preg, pattern, case_sensitive ? 0 : REG_ICASE);
236 matcher->regexp_error = 0;
237 matcher->nb_patterns = 1;
238 matcher->case_sensitive = case_sensitive;
240 for(s = pattern; *s; s++) {
241 if(*s == pattern_separator) {
242 matcher->nb_patterns++;
246 matcher->splitted_patterns = (char *) malloc((strlen(pattern) + 1) * sizeof(char));
247 matcher->patterns = (char **) malloc(matcher->nb_patterns * sizeof(char *));
249 strcpy(matcher->splitted_patterns, pattern);
252 char *last_pattern_start = matcher->splitted_patterns;
253 for(t = matcher->splitted_patterns; n < matcher->nb_patterns; t++) {
254 if(*t == pattern_separator || *t == '\0') {
256 matcher->patterns[n++] = last_pattern_start;
257 last_pattern_start = t + 1;
263 /*********************************************************************
266 void delete_char(char *buffer, int *position) {
267 if(buffer[*position]) {
269 while(c < buffer_size && buffer[c]) {
270 buffer[c] = buffer[c+1];
273 } else error_feedback();
276 void backspace_char(char *buffer, int *position) {
278 if(buffer[*position]) {
279 int c = *position - 1;
281 buffer[c] = buffer[c+1];
285 buffer[*position - 1] = '\0';
289 } else error_feedback();
292 void insert_char(char *buffer, int *position, char character) {
293 if(strlen(buffer) < buffer_size - 1) {
295 char t = buffer[c], u;
304 buffer[(*position)++] = character;
305 } else error_feedback();
308 void kill_before_cursor(char *buffer, int *position) {
310 while(buffer[*position + s]) {
311 buffer[s] = buffer[*position + s];
318 void kill_after_cursor(char *buffer, int *position) {
319 buffer[*position] = '\0';
322 /*********************************************************************/
324 int previous_visible(int current_line, int nb_lines, char **lines, matcher_t *matcher) {
325 int line = current_line - 1;
326 while(line >= 0 && !match(lines[line], matcher)) line--;
330 int next_visible(int current_line, int nb_lines, char **lines, matcher_t *matcher) {
331 int line = current_line + 1;
332 while(line < nb_lines && !match(lines[line], matcher)) line++;
340 /*********************************************************************/
342 /* The value passed to this routine in current_focus_line is the index
343 of the line we should have highlighted if there was no motion and if
344 it matched the matcher. So, the line actually highlighted is the
345 first one matching the matcher in that order: (1)
346 current_focus_line after motion, (2) the first with a greater
347 index, (3) the first with a lesser index.
349 The index of the line actually shown highlighted is written in
350 displayed_focus_line (it can be -1)
352 If there is a motion and a line is actually shown highlighted, its
353 value is written in current_focus_line. */
355 void update_screen(int *current_focus_line, int *displayed_focus_line,
357 int nb_lines, char **lines,
361 char buffer[buffer_size];
365 initialize_matcher(use_regexp, case_sensitive, &matcher, pattern);
367 int console_width = getmaxx(stdscr);
368 int console_height = getmaxy(stdscr);
370 int nb_printed_lines = 0;
372 use_default_colors();
376 /* First, we find a visible line. */
378 if(matcher.regexp_error) {
380 addnstr("Regexp syntax error", console_width);
382 } else if(nb_lines > 0) {
384 if(match(lines[*current_focus_line], &matcher)) {
385 new_focus_line = *current_focus_line;
387 new_focus_line = next_visible(*current_focus_line, nb_lines, lines, &matcher);
388 if(new_focus_line < 0) {
389 new_focus_line = previous_visible(*current_focus_line, nb_lines, lines, &matcher);
393 /* If we found a visible line and we should move, let's move */
395 if(new_focus_line >= 0 && motion != 0) {
396 int l = new_focus_line;
398 /* We want to go down, let's find the first visible line below */
399 for(m = 0; l >= 0 && m < motion; m++) {
400 l = next_visible(l, nb_lines, lines, &matcher);
406 /* We want to go up, let's find the first visible line above */
407 for(m = 0; l >= 0 && m < -motion; m++) {
408 l = previous_visible(l, nb_lines, lines, &matcher);
416 /* Here new_focus_line is either a line number matching the pattern, or -1 */
418 if(new_focus_line >= 0) {
420 int first_line = new_focus_line, last_line = new_focus_line, nb_match = 1;
422 /* We find the first and last line to show, so that the total of
423 visible lines between them (them included) is
426 while(nb_match < console_height-1 && (first_line > 0 || last_line < nb_lines - 1)) {
430 while(first_line > 0 && !match(lines[first_line], &matcher)) {
433 if(match(lines[first_line], &matcher)) {
438 if(nb_match < console_height - 1 && last_line < nb_lines - 1) {
440 while(last_line < nb_lines - 1 && !match(lines[last_line], &matcher)) {
444 if(match(lines[last_line], &matcher)) {
450 /* Now we display them */
452 for(l = first_line; l <= last_line; l++) {
453 if(match(lines[l], &matcher)) {
456 while(lines[l][k] && k < buffer_size - 2 && k < console_width - 2) {
457 buffer[k] = lines[l][k];
461 /* We fill the rest of the line with blanks if this is the
464 if(l == new_focus_line) {
465 while(k < console_width) {
475 /* Highlight the highlighted line ... */
477 if(l == new_focus_line) {
478 attron(attr_focus_line);
479 addnstr(buffer, console_width);
480 attroff(attr_focus_line);
482 addnstr(buffer, console_width);
489 /* If we are on a focused line and we moved, this become the new
493 *current_focus_line = new_focus_line;
497 *displayed_focus_line = new_focus_line;
499 if(nb_printed_lines == 0) {
501 addnstr("No selection", console_width);
506 addnstr("Empty choice", console_width);
512 /* Draw the modeline */
516 attron(attr_modeline);
518 for(k = 0; k < console_width; k++) buffer[k] = ' ';
519 buffer[console_width] = '\0';
520 addnstr(buffer, console_width);
524 /* There must be a more elegant way of moving the cursor at a
525 location met during display */
532 cursor_x += strlen(title) + 1;
535 sprintf(buffer, "%d/%d ", nb_printed_lines, nb_lines);
537 cursor_x += strlen(buffer);
539 addnstr(pattern, cursor_position);
540 cursor_x += cursor_position;
542 if(pattern[cursor_position]) {
543 addstr(pattern + cursor_position);
548 if(use_regexp || case_sensitive) {
565 attroff(attr_modeline);
570 free_matcher(&matcher);
573 /*********************************************************************/
575 void store_line(const char *t,
576 int nb_lines_max, int *nb_lines, char **lines,
577 int hash_table_size, int *hash_table) {
579 /* Remove the zsh history prefix */
581 if(zsh_history && *t == ':') {
582 while(*t && *t != ';') t++;
586 /* Remove the bash history prefix */
589 while(*t == ' ') t++;
590 while(*t >= '0' && *t <= '9') t++;
591 while(*t == ' ') t++;
594 /* Check for duplicates with the hash table and insert the line in
595 the list if necessary */
600 dup = add_and_get_previous_index(t, *nb_lines, lines, hash_table, hash_table_size);
606 lines[*nb_lines] = (char *) malloc((strlen(t) + 1) * sizeof(char));
607 strcpy(lines[*nb_lines], t);
609 /* The string was already in there, so we do not allocate a new
610 string but use the pointer to the first occurence of it */
611 lines[*nb_lines] = lines[dup];
618 void read_file(const char *input_filename,
619 int nb_lines_max, int *nb_lines, char **lines,
620 int hash_table_size, int *hash_table) {
622 char raw_line[buffer_size];
624 FILE *file = fopen(input_filename, "r");
627 fprintf(stderr, "Can not open `%s'.\n", input_filename);
631 int start = 0, end = 0, k;
633 while(*nb_lines < nb_lines_max && (end > start || !feof(file))) {
635 while(eol < end && raw_line[eol] != '\n') eol++;
638 for(k = 0; k < end - start; k++) {
639 raw_line[k] = raw_line[k + start];
644 end += fread(raw_line + end, sizeof(char), buffer_size - end, file);
645 while(eol < end && raw_line[eol] != '\n') eol++;
648 if(eol == buffer_size) {
649 raw_line[buffer_size - 1] = '\0';
650 fprintf(stderr, "Line too long (max is %d characters):\n", buffer_size);
651 fprintf(stderr, raw_line);
652 fprintf(stderr, "\n");
656 raw_line[eol] = '\0';
658 store_line(raw_line + start,
659 nb_lines_max, nb_lines, lines,
660 hash_table_size, hash_table);
668 /*********************************************************************/
670 int main(int argc, char **argv) {
672 if(!ttyname(STDIN_FILENO)) {
673 fprintf(stderr, "The standard input is not a tty.\n");
677 char input_filename[buffer_size], output_filename[buffer_size];
679 int error = 0, show_help = 0;
680 int rest_are_files = 0;
682 int color_fg_modeline, color_bg_modeline;
683 int color_fg_highlight, color_bg_highlight;
685 color_fg_modeline = COLOR_WHITE;
686 color_bg_modeline = COLOR_BLACK;
687 color_fg_highlight = COLOR_BLACK;
688 color_bg_highlight = COLOR_YELLOW;
690 setlocale(LC_ALL, "");
692 strcpy(input_filename, "");
693 strcpy(output_filename, "");
696 while(!error && !show_help && i < argc && argv[i][0] == '-' && !rest_are_files) {
698 if(strcmp(argv[i], "-o") == 0) {
699 check_opt(argc, argv, i, 1, "<output filename>");
700 strncpy(output_filename, argv[i+1], buffer_size);
704 else if(strcmp(argv[i], "-s") == 0) {
705 check_opt(argc, argv, i, 1, "<pattern separator>");
706 pattern_separator = argv[i+1][0];
710 else if(strcmp(argv[i], "-x") == 0) {
711 check_opt(argc, argv, i, 1, "<label separator>");
712 label_separator = argv[i+1][0];
716 else if(strcmp(argv[i], "-v") == 0) {
717 output_to_vt_buffer = 1;
721 else if(strcmp(argv[i], "-w") == 0) {
726 else if(strcmp(argv[i], "-m") == 0) {
731 else if(strcmp(argv[i], "-q") == 0) {
736 else if(strcmp(argv[i], "-f") == 0) {
737 check_opt(argc, argv, i, 1, "<input filename>");
738 strncpy(input_filename, argv[i+1], buffer_size);
742 else if(strcmp(argv[i], "-i") == 0) {
747 else if(strcmp(argv[i], "-b") == 0) {
752 else if(strcmp(argv[i], "-z") == 0) {
757 else if(strcmp(argv[i], "-d") == 0) {
758 remove_duplicates = 1;
762 else if(strcmp(argv[i], "-e") == 0) {
767 else if(strcmp(argv[i], "-a") == 0) {
772 else if(strcmp(argv[i], "-t") == 0) {
773 check_opt(argc, argv, i, 1, "<title>");
775 title = (char *) malloc((strlen(argv[i+1]) + 1) * sizeof(char));
776 strcpy(title, argv[i+1]);
780 else if(strcmp(argv[i], "-l") == 0) {
781 check_opt(argc, argv, i, 1, "<maximum number of lines>");
782 nb_lines_max = string_to_positive_integer(argv[i+1]);
786 else if(strcmp(argv[i], "-c") == 0) {
787 check_opt(argc, argv, i, 4, "<fg modeline> <bg modeline> <fg highlight> <bg highlight>");
788 color_fg_modeline = string_to_positive_integer(argv[i + 1]);
789 color_bg_modeline = string_to_positive_integer(argv[i + 2]);
790 color_fg_highlight = string_to_positive_integer(argv[i + 3]);
791 color_bg_highlight = string_to_positive_integer(argv[i + 4]);
795 else if(strcmp(argv[i], "--") == 0) {
800 else if(strcmp(argv[i], "-h") == 0) {
806 fprintf(stderr, "Unknown option %s.\n", argv[i]);
811 if(show_help || error) {
812 fprintf(stderr, "Selector version %s-R%s\n", VERSION, REVISION_NUMBER);
813 fprintf(stderr, "Written by Francois Fleuret <francois@fleuret.org>.\n");
814 fprintf(stderr, "Usage: %s [options] [<filename1> [<filename2> ...]]\n", argv[0]);
815 fprintf(stderr, "\n");
816 fprintf(stderr, " -h show this help\n");
817 fprintf(stderr, " -v inject the selected line in the tty\n");
818 fprintf(stderr, " -w quote control characters with ^Qs when using -v\n");
819 fprintf(stderr, " -d remove duplicated lines\n");
820 fprintf(stderr, " -b remove the bash history line prefix\n");
821 fprintf(stderr, " -z remove the zsh history line prefix\n");
822 fprintf(stderr, " -i invert the order of lines\n");
823 fprintf(stderr, " -e start in regexp mode\n");
824 fprintf(stderr, " -a start in case sensitive mode\n");
825 fprintf(stderr, " -m monochrome mode\n");
826 fprintf(stderr, " -q make a flash instead of a beep on an edition error\n");
827 fprintf(stderr, " -- all following arguments are filenames\n");
828 fprintf(stderr, " -t <title>\n");
829 fprintf(stderr, " add a title in the modeline\n");
830 fprintf(stderr, " -c <fg modeline> <bg modeline> <fg highlight> <bg highlight>\n");
831 fprintf(stderr, " set the display colors\n");
832 fprintf(stderr, " -o <output filename>\n");
833 fprintf(stderr, " set a file to write the selected line to\n");
834 fprintf(stderr, " -s <pattern separator>\n");
835 fprintf(stderr, " set the symbol to separate substrings in the pattern\n");
836 fprintf(stderr, " -x <label separator>\n");
837 fprintf(stderr, " set the symbol to terminate the label\n");
838 fprintf(stderr, " -l <max number of lines>\n");
839 fprintf(stderr, " set the maximum number of lines to take into account\n");
840 fprintf(stderr, "\n");
844 char **lines = (char **) malloc(nb_lines_max * sizeof(char *));
847 int hash_table_size = nb_lines_max * 10;
850 if(remove_duplicates) {
851 hash_table = new_hash_table(hash_table_size);
854 if(input_filename[0]) {
855 read_file(input_filename,
856 nb_lines_max, &nb_lines, lines,
857 hash_table_size, hash_table);
862 nb_lines_max, &nb_lines, lines,
863 hash_table_size, hash_table);
869 /* Now remove the null strings */
872 for(k = 0; k < nb_lines; k++) {
874 lines[n++] = lines[k];
881 for(i = 0; i < nb_lines / 2; i++) {
882 char *s = lines[nb_lines - 1 - i];
883 lines[nb_lines - 1 - i] = lines[i];
888 /* Build the labels from the strings, take only the part before the
889 label_separator and transform control characters to printable
892 char **labels = (char **) malloc(nb_lines * sizeof(char *));
893 for(l = 0; l < nb_lines; l++) {
898 while(*t && *t != label_separator) {
902 labels[l] = (char *) malloc((e + 1) * sizeof(char));
905 while(*t && *t != label_separator) {
907 while(*u) { *s++ = *u++; }
912 char pattern[buffer_size];
918 /* Here we start to display with curse */
924 intrflush(stdscr, FALSE);
926 /* So that the arrow keys work */
927 keypad(stdscr, TRUE);
929 attr_error = A_STANDOUT;
930 attr_modeline = A_REVERSE;
931 attr_focus_line = A_STANDOUT;
933 if(with_colors && has_colors()) {
937 if(color_fg_modeline < 0 || color_fg_modeline >= COLORS ||
938 color_bg_modeline < 0 || color_bg_modeline >= COLORS ||
939 color_fg_highlight < 0 || color_bg_highlight >= COLORS ||
940 color_bg_highlight < 0 || color_bg_highlight >= COLORS) {
943 fprintf(stderr, "Color numbers have to be between 0 and %d.\n", COLORS - 1);
947 init_pair(1, color_fg_modeline, color_bg_modeline);
948 attr_modeline = COLOR_PAIR(1);
950 init_pair(2, color_fg_highlight, color_bg_highlight);
951 attr_focus_line = COLOR_PAIR(2);
953 init_pair(3, COLOR_WHITE, COLOR_RED);
954 attr_error = COLOR_PAIR(3);
959 int current_focus_line = 0, displayed_focus_line = 0;
961 update_screen(¤t_focus_line, &displayed_focus_line,
963 nb_lines, labels, cursor_position, pattern);
971 if(key >= ' ' && key <= '~') { /* Insert character */
972 insert_char(pattern, &cursor_position, key);
975 else if(key == KEY_BACKSPACE ||
976 key == '\010' || /* ^H */
977 key == '\177') { /* ^? */
978 backspace_char(pattern, &cursor_position);
981 else if(key == KEY_DC ||
982 key == '\004') { /* ^D */
983 delete_char(pattern, &cursor_position);
986 else if(key == KEY_HOME) {
987 current_focus_line = 0;
990 else if(key == KEY_END) {
991 current_focus_line = nb_lines - 1;
994 else if(key == KEY_NPAGE) {
998 else if(key == KEY_PPAGE) {
1002 else if(key == KEY_DOWN ||
1003 key == '\016') { /* ^N */
1007 else if(key == KEY_UP ||
1008 key == '\020') { /* ^P */
1012 else if(key == KEY_LEFT ||
1013 key == '\002') { /* ^B */
1014 if(cursor_position > 0) cursor_position--;
1015 else error_feedback();
1018 else if(key == KEY_RIGHT ||
1019 key == '\006') { /* ^F */
1020 if(pattern[cursor_position]) cursor_position++;
1021 else error_feedback();
1024 else if(key == '\001') { /* ^A */
1025 cursor_position = 0;
1028 else if(key == '\005') { /* ^E */
1029 cursor_position = strlen(pattern);
1032 else if(key == '\022') { /* ^R */
1033 use_regexp = !use_regexp;
1036 else if(key == '\011') { /* ^I */
1037 case_sensitive = !case_sensitive;
1040 else if(key == '\025') { /* ^U */
1041 kill_before_cursor(pattern, &cursor_position);
1044 else if(key == '\013') { /* ^K */
1045 kill_after_cursor(pattern, &cursor_position);
1048 else if(key == '\014') { /* ^L */
1049 /* I suspect that we may sometime mess up the display */
1053 update_screen(¤t_focus_line, &displayed_focus_line,
1055 nb_lines, labels, cursor_position, pattern);
1057 } while(key != '\007' && /* ^G */
1058 key != '\033' && /* ^[ (escape) */
1065 /* Here we come back to standard display */
1067 if((key == KEY_ENTER || key == '\n')) {
1071 if(displayed_focus_line >= 0 && displayed_focus_line < nb_lines) {
1072 t = lines[displayed_focus_line];
1073 if(label_separator) {
1074 while(*t && *t != label_separator) t++;
1081 if(output_to_vt_buffer && t) {
1082 inject_into_tty_buffer(t);
1085 if(output_filename[0]) {
1086 FILE *out = fopen(output_filename, "w");
1093 fprintf(stderr, "Can not open %s for writing.\n", output_filename);
1100 printf("Aborted.\n");
1103 for(l = 0; l < nb_lines; l++) {