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 test_and_add(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 read_file(const char *input_filename,
576 int nb_lines_max, int *nb_lines, char **lines,
577 int hash_table_size, int *hash_table) {
579 char raw_line[buffer_size];
581 FILE *file = fopen(input_filename, "r");
584 fprintf(stderr, "Can not open `%s'.\n", input_filename);
588 int start = 0, end = 0, k;
590 while(*nb_lines < nb_lines_max && (end > start || !feof(file))) {
592 while(eol < end && raw_line[eol] != '\n') eol++;
595 for(k = 0; k < end - start; k++) {
596 raw_line[k] = raw_line[k + start];
601 end += fread(raw_line + end, sizeof(char), buffer_size - end, file);
602 while(eol < end && raw_line[eol] != '\n') eol++;
605 if(eol == buffer_size) {
606 raw_line[buffer_size - 1] = '\0';
607 fprintf(stderr, "Line too long (max is %d characters):\n", buffer_size);
608 fprintf(stderr, raw_line);
609 fprintf(stderr, "\n");
613 raw_line[eol] = '\0';
615 char *t = raw_line + start;
617 /* Remove the zsh history prefix */
619 if(zsh_history && *t == ':') {
620 while(*t && *t != ';') t++;
624 /* Remove the bash history prefix */
627 while(*t == ' ') t++;
628 while(*t >= '0' && *t <= '9') t++;
629 while(*t == ' ') t++;
632 /* Check for duplicates with the hash table and insert the line in
633 the list if necessary */
638 dup = test_and_add(t, *nb_lines, lines, hash_table, hash_table_size);
644 lines[*nb_lines] = (char *) malloc((strlen(t) + 1) * sizeof(char));
645 strcpy(lines[*nb_lines], t);
647 /* The string was already in there, so we do not allocate a new
648 string but use the pointer to the first occurence of it */
649 lines[*nb_lines] = lines[dup];
661 /*********************************************************************/
663 int main(int argc, char **argv) {
665 if(!ttyname(STDIN_FILENO)) {
666 fprintf(stderr, "The standard input is not a tty.\n");
670 char input_filename[buffer_size], output_filename[buffer_size];
672 int error = 0, show_help = 0;
673 int rest_are_files = 0;
675 int color_fg_modeline, color_bg_modeline;
676 int color_fg_highlight, color_bg_highlight;
678 color_fg_modeline = COLOR_WHITE;
679 color_bg_modeline = COLOR_BLACK;
680 color_fg_highlight = COLOR_BLACK;
681 color_bg_highlight = COLOR_YELLOW;
683 setlocale(LC_ALL, "");
685 strcpy(input_filename, "");
686 strcpy(output_filename, "");
689 while(!error && !show_help && i < argc && argv[i][0] == '-' && !rest_are_files) {
691 if(strcmp(argv[i], "-o") == 0) {
692 check_opt(argc, argv, i, 1, "<output filename>");
693 strncpy(output_filename, argv[i+1], buffer_size);
697 else if(strcmp(argv[i], "-s") == 0) {
698 check_opt(argc, argv, i, 1, "<pattern separator>");
699 pattern_separator = argv[i+1][0];
703 else if(strcmp(argv[i], "-x") == 0) {
704 check_opt(argc, argv, i, 1, "<label separator>");
705 label_separator = argv[i+1][0];
709 else if(strcmp(argv[i], "-v") == 0) {
710 output_to_vt_buffer = 1;
714 else if(strcmp(argv[i], "-w") == 0) {
719 else if(strcmp(argv[i], "-m") == 0) {
724 else if(strcmp(argv[i], "-q") == 0) {
729 else if(strcmp(argv[i], "-f") == 0) {
730 check_opt(argc, argv, i, 1, "<input filename>");
731 strncpy(input_filename, argv[i+1], buffer_size);
735 else if(strcmp(argv[i], "-i") == 0) {
740 else if(strcmp(argv[i], "-b") == 0) {
745 else if(strcmp(argv[i], "-z") == 0) {
750 else if(strcmp(argv[i], "-d") == 0) {
751 remove_duplicates = 1;
755 else if(strcmp(argv[i], "-e") == 0) {
760 else if(strcmp(argv[i], "-a") == 0) {
765 else if(strcmp(argv[i], "-t") == 0) {
766 check_opt(argc, argv, i, 1, "<title>");
768 title = (char *) malloc((strlen(argv[i+1]) + 1) * sizeof(char));
769 strcpy(title, argv[i+1]);
773 else if(strcmp(argv[i], "-l") == 0) {
774 check_opt(argc, argv, i, 1, "<maximum number of lines>");
775 nb_lines_max = string_to_positive_integer(argv[i+1]);
779 else if(strcmp(argv[i], "-c") == 0) {
780 check_opt(argc, argv, i, 4, "<fg modeline> <bg modeline> <fg highlight> <bg highlight>");
781 color_fg_modeline = string_to_positive_integer(argv[i + 1]);
782 color_bg_modeline = string_to_positive_integer(argv[i + 2]);
783 color_fg_highlight = string_to_positive_integer(argv[i + 3]);
784 color_bg_highlight = string_to_positive_integer(argv[i + 4]);
788 else if(strcmp(argv[i], "--") == 0) {
793 else if(strcmp(argv[i], "-h") == 0) {
799 fprintf(stderr, "Unknown option %s.\n", argv[i]);
804 if(show_help || error) {
805 fprintf(stderr, "Selector version %s-R%s\n", VERSION, REVISION_NUMBER);
806 fprintf(stderr, "Written by Francois Fleuret <francois@fleuret.org>.\n");
807 fprintf(stderr, "Usage: %s [options] [<filename1> [<filename2> ...]]\n", argv[0]);
808 fprintf(stderr, "\n");
809 fprintf(stderr, " -h show this help\n");
810 fprintf(stderr, " -v inject the selected line in the tty\n");
811 fprintf(stderr, " -w quote control characters with ^Qs when using -v\n");
812 fprintf(stderr, " -d remove duplicated lines\n");
813 fprintf(stderr, " -b remove the bash history line prefix\n");
814 fprintf(stderr, " -z remove the zsh history line prefix\n");
815 fprintf(stderr, " -i invert the order of lines\n");
816 fprintf(stderr, " -e start in regexp mode\n");
817 fprintf(stderr, " -a start in case sensitive mode\n");
818 fprintf(stderr, " -m monochrome mode\n");
819 fprintf(stderr, " -q make a flash instead of a beep on an edition error\n");
820 fprintf(stderr, " -- all following arguments are filenames\n");
821 fprintf(stderr, " -t <title>\n");
822 fprintf(stderr, " add a title in the modeline\n");
823 fprintf(stderr, " -c <fg modeline> <bg modeline> <fg highlight> <bg highlight>\n");
824 fprintf(stderr, " set the display colors\n");
825 fprintf(stderr, " -o <output filename>\n");
826 fprintf(stderr, " set a file to write the selected line to\n");
827 fprintf(stderr, " -s <pattern separator>\n");
828 fprintf(stderr, " set the symbol to separate substrings in the pattern\n");
829 fprintf(stderr, " -x <label separator>\n");
830 fprintf(stderr, " set the symbol to terminate the label\n");
831 fprintf(stderr, " -l <max number of lines>\n");
832 fprintf(stderr, " set the maximum number of lines to take into account\n");
833 fprintf(stderr, "\n");
837 char **lines = (char **) malloc(nb_lines_max * sizeof(char *));
840 int hash_table_size = nb_lines_max * 10;
843 if(remove_duplicates) {
844 hash_table = new_hash_table(hash_table_size);
847 if(input_filename[0]) {
848 read_file(input_filename,
849 nb_lines_max, &nb_lines, lines,
850 hash_table_size, hash_table);
855 nb_lines_max, &nb_lines, lines,
856 hash_table_size, hash_table);
862 /* Now remove the null strings */
865 for(k = 0; k < nb_lines; k++) {
867 lines[n++] = lines[k];
874 for(i = 0; i < nb_lines / 2; i++) {
875 char *s = lines[nb_lines - 1 - i];
876 lines[nb_lines - 1 - i] = lines[i];
881 /* Build the labels from the strings, take only the part before the
882 label_separator and transform control characters to printable
885 char **labels = (char **) malloc(nb_lines * sizeof(char *));
886 for(l = 0; l < nb_lines; l++) {
891 while(*t && *t != label_separator) {
895 labels[l] = (char *) malloc((e + 1) * sizeof(char));
898 while(*t && *t != label_separator) {
900 while(*u) { *s++ = *u++; }
905 char pattern[buffer_size];
911 /* Here we start to display with curse */
917 intrflush(stdscr, FALSE);
919 /* So that the arrow keys work */
920 keypad(stdscr, TRUE);
922 attr_error = A_STANDOUT;
923 attr_modeline = A_REVERSE;
924 attr_focus_line = A_STANDOUT;
926 if(with_colors && has_colors()) {
930 if(color_fg_modeline < 0 || color_fg_modeline >= COLORS ||
931 color_bg_modeline < 0 || color_bg_modeline >= COLORS ||
932 color_fg_highlight < 0 || color_bg_highlight >= COLORS ||
933 color_bg_highlight < 0 || color_bg_highlight >= COLORS) {
936 fprintf(stderr, "Color numbers have to be between 0 and %d.\n", COLORS - 1);
940 init_pair(1, color_fg_modeline, color_bg_modeline);
941 attr_modeline = COLOR_PAIR(1);
943 init_pair(2, color_fg_highlight, color_bg_highlight);
944 attr_focus_line = COLOR_PAIR(2);
946 init_pair(3, COLOR_WHITE, COLOR_RED);
947 attr_error = COLOR_PAIR(3);
952 int current_focus_line = 0, displayed_focus_line = 0;
954 update_screen(¤t_focus_line, &displayed_focus_line,
956 nb_lines, labels, cursor_position, pattern);
964 if(key >= ' ' && key <= '~') { /* Insert character */
965 insert_char(pattern, &cursor_position, key);
968 else if(key == KEY_BACKSPACE ||
969 key == '\010' || /* ^H */
970 key == '\177') { /* ^? */
971 backspace_char(pattern, &cursor_position);
974 else if(key == KEY_DC ||
975 key == '\004') { /* ^D */
976 delete_char(pattern, &cursor_position);
979 else if(key == KEY_HOME) {
980 current_focus_line = 0;
983 else if(key == KEY_END) {
984 current_focus_line = nb_lines - 1;
987 else if(key == KEY_NPAGE) {
991 else if(key == KEY_PPAGE) {
995 else if(key == KEY_DOWN ||
996 key == '\016') { /* ^N */
1000 else if(key == KEY_UP ||
1001 key == '\020') { /* ^P */
1005 else if(key == KEY_LEFT ||
1006 key == '\002') { /* ^B */
1007 if(cursor_position > 0) cursor_position--;
1008 else error_feedback();
1011 else if(key == KEY_RIGHT ||
1012 key == '\006') { /* ^F */
1013 if(pattern[cursor_position]) cursor_position++;
1014 else error_feedback();
1017 else if(key == '\001') { /* ^A */
1018 cursor_position = 0;
1021 else if(key == '\005') { /* ^E */
1022 cursor_position = strlen(pattern);
1025 else if(key == '\022') { /* ^R */
1026 use_regexp = !use_regexp;
1029 else if(key == '\011') { /* ^I */
1030 case_sensitive = !case_sensitive;
1033 else if(key == '\025') { /* ^U */
1034 kill_before_cursor(pattern, &cursor_position);
1037 else if(key == '\013') { /* ^K */
1038 kill_after_cursor(pattern, &cursor_position);
1041 else if(key == '\014') { /* ^L */
1042 /* I suspect that we may sometime mess up the display */
1046 update_screen(¤t_focus_line, &displayed_focus_line,
1048 nb_lines, labels, cursor_position, pattern);
1050 } while(key != '\007' && /* ^G */
1051 key != '\033' && /* ^[ (escape) */
1058 /* Here we come back to standard display */
1060 if((key == KEY_ENTER || key == '\n')) {
1064 if(displayed_focus_line >= 0 && displayed_focus_line < nb_lines) {
1065 t = lines[displayed_focus_line];
1066 if(label_separator) {
1067 while(*t && *t != label_separator) t++;
1074 if(output_to_vt_buffer && t) {
1075 inject_into_tty_buffer(t);
1078 if(output_filename[0]) {
1079 FILE *out = fopen(output_filename, "w");
1086 fprintf(stderr, "Can not open %s for writing.\n", output_filename);
1093 printf("Aborted.\n");
1096 for(l = 0; l < nb_lines; l++) {