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 /* First, we find a visible line. */
372 int nb_printed_lines = 0;
374 use_default_colors();
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:\n");
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];
659 /*********************************************************************/
661 int main(int argc, char **argv) {
663 if(!ttyname(STDIN_FILENO)) {
664 fprintf(stderr, "The standard input is not a tty.\n");
668 char input_filename[buffer_size], output_filename[buffer_size];
670 int error = 0, show_help = 0;
671 int rest_are_files = 0;
673 int color_fg_modeline, color_bg_modeline;
674 int color_fg_highlight, color_bg_highlight;
676 color_fg_modeline = COLOR_WHITE;
677 color_bg_modeline = COLOR_BLACK;
678 color_fg_highlight = COLOR_BLACK;
679 color_bg_highlight = COLOR_YELLOW;
681 setlocale(LC_ALL, "");
683 strcpy(input_filename, "");
684 strcpy(output_filename, "");
687 while(!error && !show_help && i < argc && argv[i][0] == '-' && !rest_are_files) {
689 if(strcmp(argv[i], "-o") == 0) {
690 check_opt(argc, argv, i, 1, "<output filename>");
691 strncpy(output_filename, argv[i+1], buffer_size);
695 else if(strcmp(argv[i], "-s") == 0) {
696 check_opt(argc, argv, i, 1, "<pattern separator>");
697 pattern_separator = argv[i+1][0];
701 else if(strcmp(argv[i], "-x") == 0) {
702 check_opt(argc, argv, i, 1, "<label separator>");
703 label_separator = argv[i+1][0];
707 else if(strcmp(argv[i], "-v") == 0) {
708 output_to_vt_buffer = 1;
712 else if(strcmp(argv[i], "-w") == 0) {
717 else if(strcmp(argv[i], "-m") == 0) {
722 else if(strcmp(argv[i], "-q") == 0) {
727 else if(strcmp(argv[i], "-f") == 0) {
728 check_opt(argc, argv, i, 1, "<input filename>");
729 strncpy(input_filename, argv[i+1], buffer_size);
733 else if(strcmp(argv[i], "-i") == 0) {
738 else if(strcmp(argv[i], "-b") == 0) {
743 else if(strcmp(argv[i], "-z") == 0) {
748 else if(strcmp(argv[i], "-d") == 0) {
749 remove_duplicates = 1;
753 else if(strcmp(argv[i], "-e") == 0) {
758 else if(strcmp(argv[i], "-a") == 0) {
763 else if(strcmp(argv[i], "-t") == 0) {
764 check_opt(argc, argv, i, 1, "<title>");
766 title = (char *) malloc((strlen(argv[i+1]) + 1) * sizeof(char));
767 strcpy(title, argv[i+1]);
771 else if(strcmp(argv[i], "-l") == 0) {
772 check_opt(argc, argv, i, 1, "<maximum number of lines>");
773 nb_lines_max = string_to_positive_integer(argv[i+1]);
777 else if(strcmp(argv[i], "-c") == 0) {
778 check_opt(argc, argv, i, 4, "<fg modeline> <bg modeline> <fg highlight> <bg highlight>");
779 color_fg_modeline = string_to_positive_integer(argv[i + 1]);
780 color_bg_modeline = string_to_positive_integer(argv[i + 2]);
781 color_fg_highlight = string_to_positive_integer(argv[i + 3]);
782 color_bg_highlight = string_to_positive_integer(argv[i + 4]);
786 else if(strcmp(argv[i], "--") == 0) {
791 else if(strcmp(argv[i], "-h") == 0) {
797 fprintf(stderr, "Unknown option %s.\n", argv[i]);
802 if(show_help || error) {
803 fprintf(stderr, "Selector version %s-R%s\n", VERSION, REVISION_NUMBER);
804 fprintf(stderr, "Written by Francois Fleuret <francois@fleuret.org>.\n");
805 fprintf(stderr, "Usage: %s [options] [<filename1> [<filename2> ...]]\n", argv[0]);
806 fprintf(stderr, "\n");
807 fprintf(stderr, " -h show this help\n");
808 fprintf(stderr, " -v inject the selected line in the tty\n");
809 fprintf(stderr, " -w quote control characters with ^Qs when using -v\n");
810 fprintf(stderr, " -d remove duplicated lines\n");
811 fprintf(stderr, " -b remove the bash history line prefix\n");
812 fprintf(stderr, " -z remove the zsh history line prefix\n");
813 fprintf(stderr, " -i invert the order of lines\n");
814 fprintf(stderr, " -e start in regexp mode\n");
815 fprintf(stderr, " -a start in case sensitive mode\n");
816 fprintf(stderr, " -m monochrome mode\n");
817 fprintf(stderr, " -q make a flash instead of a beep on an edition error\n");
818 fprintf(stderr, " -- all following arguments are filenames\n");
819 fprintf(stderr, " -t <title>\n");
820 fprintf(stderr, " add a title in the modeline\n");
821 fprintf(stderr, " -c <fg modeline> <bg modeline> <fg highlight> <bg highlight>\n");
822 fprintf(stderr, " set the display colors\n");
823 fprintf(stderr, " -o <output filename>\n");
824 fprintf(stderr, " set a file to write the selected line to\n");
825 fprintf(stderr, " -s <pattern separator>\n");
826 fprintf(stderr, " set the symbol to separate substrings in the pattern\n");
827 fprintf(stderr, " -x <label separator>\n");
828 fprintf(stderr, " set the symbol to terminate the label\n");
829 fprintf(stderr, " -l <max number of lines>\n");
830 fprintf(stderr, " set the maximum number of lines to take into account\n");
831 fprintf(stderr, "\n");
835 char **lines = (char **) malloc(nb_lines_max * sizeof(char *));
838 int hash_table_size = nb_lines_max * 10;
841 if(remove_duplicates) {
842 hash_table = new_hash_table(hash_table_size);
845 if(input_filename[0]) {
846 read_file(input_filename,
847 nb_lines_max, &nb_lines, lines,
848 hash_table_size, hash_table);
853 nb_lines_max, &nb_lines, lines,
854 hash_table_size, hash_table);
860 /* Now remove the null strings */
863 for(k = 0; k < nb_lines; k++) {
865 lines[n++] = lines[k];
872 for(i = 0; i < nb_lines / 2; i++) {
873 char *s = lines[nb_lines - 1 - i];
874 lines[nb_lines - 1 - i] = lines[i];
879 /* Build the labels from the strings, take only the part before the
880 label_separator and transform control characters to printable
883 char **labels = (char **) malloc(nb_lines * sizeof(char *));
884 for(l = 0; l < nb_lines; l++) {
889 while(*t && *t != label_separator) {
893 labels[l] = (char *) malloc((e + 1) * sizeof(char));
896 while(*t && *t != label_separator) {
898 while(*u) { *s++ = *u++; }
903 char pattern[buffer_size];
909 /* Here we start to display with curse */
915 intrflush(stdscr, FALSE);
917 /* So that the arrow keys work */
918 keypad(stdscr, TRUE);
920 attr_error = A_STANDOUT;
921 attr_modeline = A_REVERSE;
922 attr_focus_line = A_STANDOUT;
924 if(with_colors && has_colors()) {
928 if(color_fg_modeline < 0 || color_fg_modeline >= COLORS ||
929 color_bg_modeline < 0 || color_bg_modeline >= COLORS ||
930 color_fg_highlight < 0 || color_bg_highlight >= COLORS ||
931 color_bg_highlight < 0 || color_bg_highlight >= COLORS) {
934 fprintf(stderr, "Color numbers have to be between 0 and %d.\n", COLORS - 1);
938 init_pair(1, color_fg_modeline, color_bg_modeline);
939 attr_modeline = COLOR_PAIR(1);
941 init_pair(2, color_fg_highlight, color_bg_highlight);
942 attr_focus_line = COLOR_PAIR(2);
944 init_pair(3, COLOR_WHITE, COLOR_RED);
945 attr_error = COLOR_PAIR(3);
950 int current_focus_line = 0, displayed_focus_line = 0;
952 update_screen(¤t_focus_line, &displayed_focus_line,
954 nb_lines, labels, cursor_position, pattern);
962 if(key >= ' ' && key <= '~') { /* Insert character */
963 insert_char(pattern, &cursor_position, key);
966 else if(key == KEY_BACKSPACE ||
967 key == '\010' || /* ^H */
968 key == '\177') { /* ^? */
969 backspace_char(pattern, &cursor_position);
972 else if(key == KEY_DC ||
973 key == '\004') { /* ^D */
974 delete_char(pattern, &cursor_position);
977 else if(key == KEY_HOME) {
978 current_focus_line = 0;
981 else if(key == KEY_END) {
982 current_focus_line = nb_lines - 1;
985 else if(key == KEY_NPAGE) {
989 else if(key == KEY_PPAGE) {
993 else if(key == KEY_DOWN ||
994 key == '\016') { /* ^N */
998 else if(key == KEY_UP ||
999 key == '\020') { /* ^P */
1003 else if(key == KEY_LEFT ||
1004 key == '\002') { /* ^B */
1005 if(cursor_position > 0) cursor_position--;
1006 else error_feedback();
1009 else if(key == KEY_RIGHT ||
1010 key == '\006') { /* ^F */
1011 if(pattern[cursor_position]) cursor_position++;
1012 else error_feedback();
1015 else if(key == '\001') { /* ^A */
1016 cursor_position = 0;
1019 else if(key == '\005') { /* ^E */
1020 cursor_position = strlen(pattern);
1023 else if(key == '\022') { /* ^R */
1024 use_regexp = !use_regexp;
1027 else if(key == '\011') { /* ^I */
1028 case_sensitive = !case_sensitive;
1031 else if(key == '\025') { /* ^U */
1032 kill_before_cursor(pattern, &cursor_position);
1035 else if(key == '\013') { /* ^K */
1036 kill_after_cursor(pattern, &cursor_position);
1039 else if(key == '\014') { /* ^L */
1040 /* I suspect that we may sometime mess up the display */
1044 update_screen(¤t_focus_line, &displayed_focus_line,
1046 nb_lines, labels, cursor_position, pattern);
1048 } while(key != '\007' && /* ^G */
1049 key != '\033' && /* ^[ (escape) */
1056 /* Here we come back to standard display */
1058 if((key == KEY_ENTER || key == '\n')) {
1062 if(displayed_focus_line >= 0 && displayed_focus_line < nb_lines) {
1063 t = lines[displayed_focus_line];
1064 if(label_separator) {
1065 while(*t && *t != label_separator) t++;
1072 if(output_to_vt_buffer && t) {
1073 inject_into_tty_buffer(t);
1076 if(output_filename[0]) {
1077 FILE *out = fopen(output_filename, "w");
1084 fprintf(stderr, "Can not open %s for writing.\n", output_filename);
1091 printf("Aborted.\n");
1094 for(l = 0; l < nb_lines; l++) {