lib/widget/input_complete.c

   1 /*
   2    Input line filename/username/hostname/variable/command completion.
   3    (Let mc type for you...)
   4
   5    Copyright (C) 1995, 1998, 1999, 2000, 2001, 2002, 2003, 2004, 2005,
   6    2007, 2011, 2013
   7    the Free Software Foundation, Inc.
   8
   9    Written by:
  10    Jakub Jelinek, 1995
  11    Slava Zanko <slavazanko@gmail.com>, 2013
  12    Andrew Borodin <aborodin@vmail.ru>, 2013
  13
  14    This file is part of the Midnight Commander.
  15
  16    The Midnight Commander is free software: you can redistribute it
  17    and/or modify it under the terms of the GNU General Public License as
  18    published by the Free Software Foundation, either version 3 of the License,
  19    or (at your option) any later version.
  20
  21    The Midnight Commander is distributed in the hope that it will be useful,
  22    but WITHOUT ANY WARRANTY; without even the implied warranty of
  23    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  24    GNU General Public License for more details.
  25
  26    You should have received a copy of the GNU General Public License
  27    along with this program.  If not, see <http://www.gnu.org/licenses/>.
  28  */
  29
  30 /** \file lib/widget/input_complete.c
  31  *  \brief Source: Input line filename/username/hostname/variable/command completion
  32  */
  33
  34 #include <config.h>
  35
  36 #include <ctype.h>
  37 #include <stdio.h>
  38 #include <stdlib.h>
  39 #include <string.h>
  40 #include <dirent.h>
  41 #include <sys/types.h>
  42 #include <sys/stat.h>
  43 #include <pwd.h>
  44 #include <unistd.h>
  45
  46 #include "lib/global.h"
  47
  48 #include "lib/tty/tty.h"
  49 #include "lib/tty/key.h"        /* XCTRL and ALT macros */
  50 #include "lib/vfs/vfs.h"
  51 #include "lib/strescape.h"
  52 #include "lib/strutil.h"
  53 #include "lib/util.h"
  54 #include "lib/widget.h"
  55
  56 #include "input_complete.h"
  57
  58 /*** global variables ****************************************************************************/
  59
  60 /* Linux declares environ in <unistd.h>, so don't repeat it here. */
  61 #if (!(defined(__linux__) && defined (__USE_GNU)) && !defined(__CYGWIN__))
  62 extern char **environ;
  63 #endif
  64
  65 /*** file scope macro definitions ****************************************************************/
  66
  67 /* #define DO_COMPLETION_DEBUG */
  68 #ifdef DO_COMPLETION_DEBUG
  69 #define SHOW_C_CTX(func) fprintf(stderr, "%s: text='%s' flags=%s\n", func, text, show_c_flags(flags))
  70 #else
  71 #define SHOW_C_CTX(func)
  72 #endif /* DO_CMPLETION_DEBUG */
  73
  74 #define whitespace(c) ((c) == ' ' || (c) == '\t')
  75 #define cr_whitespace(c) (whitespace (c) || (c) == '\n' || (c) == '\r')
  76
  77 #define DO_INSERTION 1
  78 #define DO_QUERY     2
  79
  80 /*** file scope type declarations ****************************************************************/
  81
  82 typedef char *CompletionFunction (const char *text, int state, input_complete_t flags);
  83
  84 typedef struct
  85 {
  86     size_t in_command_position;
  87     char *word;
  88     char *p;
  89     char *q;
  90     char *r;
  91     gboolean is_cd;
  92     input_complete_t flags;
  93 } try_complete_automation_state_t;
  94
  95 /*** file scope variables ************************************************************************/
  96
  97 static char **hosts = NULL;
  98 static char **hosts_p = NULL;
  99 static int hosts_alloclen = 0;
 100
 101 static int query_height, query_width;
 102 static WInput *input;
 103 static int min_end;
 104 static int start = 0;
 105 static int end = 0;
 106
 107 /*** file scope functions ************************************************************************/
 108 /* --------------------------------------------------------------------------------------------- */
 109
 110 char **try_complete (char *text, int *lc_start, int *lc_end, input_complete_t flags);
 111 void complete_engine_fill_completions (WInput * in);
 112
 113 #ifdef DO_COMPLETION_DEBUG
 114 /**
 115  * Useful to print/debug completion flags
 116  */
 117 static const char *
 118 show_c_flags (input_complete_t flags)
 119 {
 120     static char s_cf[] = "FHCVUDS";
 121
 122     s_cf[0] = (flags & INPUT_COMPLETE_FILENAMES) ? 'F' : ' ';
 123     s_cf[1] = (flags & INPUT_COMPLETE_HOSTNAMES) ? 'H' : ' ';
 124     s_cf[2] = (flags & INPUT_COMPLETE_COMMANDS) ? 'C' : ' ';
 125     s_cf[3] = (flags & INPUT_COMPLETE_VARIABLES) ? 'V' : ' ';
 126     s_cf[4] = (flags & INPUT_COMPLETE_USERNAMES) ? 'U' : ' ';
 127     s_cf[5] = (flags & INPUT_COMPLETE_CD) ? 'D' : ' ';
 128     s_cf[6] = (flags & INPUT_COMPLETE_SHELL_ESC) ? 'S' : ' ';
 129
 130     return s_cf;
 131 }
 132 #endif /* DO_CMPLETION_DEBUG */
 133
 134 /* --------------------------------------------------------------------------------------------- */
 135
 136 static char *
 137 filename_completion_function (const char *text, int state, input_complete_t flags)
 138 {
 139     static DIR *directory = NULL;
 140     static char *filename = NULL;
 141     static char *dirname = NULL;
 142     static char *users_dirname = NULL;
 143     static size_t filename_len;
 144     int isdir = 1, isexec = 0;
 145     static vfs_path_t *dirname_vpath = NULL;
 146
 147     struct dirent *entry = NULL;
 148
 149     SHOW_C_CTX ("filename_completion_function");
 150
 151     if (text && (flags & INPUT_COMPLETE_SHELL_ESC))
 152     {
 153         char *u_text;
 154         char *result;
 155         char *e_result;
 156
 157         u_text = strutils_shell_unescape (text);
 158
 159         result = filename_completion_function (u_text, state, flags & (~INPUT_COMPLETE_SHELL_ESC));
 160         g_free (u_text);
 161
 162         e_result = strutils_shell_escape (result);
 163         g_free (result);
 164
 165         return e_result;
 166     }
 167
 168     /* If we're starting the match process, initialize us a bit. */
 169     if (state == 0)
 170     {
 171         const char *temp;
 172
 173         g_free (dirname);
 174         g_free (filename);
 175         g_free (users_dirname);
 176         vfs_path_free (dirname_vpath);
 177
 178         if ((*text != '\0') && (temp = strrchr (text, PATH_SEP)) != NULL)
 179         {
 180             filename = g_strdup (++temp);
 181             dirname = g_strndup (text, temp - text);
 182         }
 183         else
 184         {
 185             dirname = g_strdup (".");
 186             filename = g_strdup (text);
 187         }
 188
 189         /* We aren't done yet.  We also support the "~user" syntax. */
 190
 191         /* Save the version of the directory that the user typed. */
 192         users_dirname = dirname;
 193         dirname = tilde_expand (dirname);
 194         canonicalize_pathname (dirname);
 195         dirname_vpath = vfs_path_from_str (dirname);
 196
 197         /* Here we should do something with variable expansion
 198            and `command`.
 199            Maybe a dream - UNIMPLEMENTED yet. */
 200
 201         directory = mc_opendir (dirname_vpath);
 202         filename_len = strlen (filename);
 203     }
 204
 205     /* Now that we have some state, we can read the directory. */
 206
 207     while (directory && (entry = mc_readdir (directory)))
 208     {
 209         if (!str_is_valid_string (entry->d_name))
 210             continue;
 211
 212         /* Special case for no filename.
 213            All entries except "." and ".." match. */
 214         if (filename_len == 0)
 215         {
 216             if (DIR_IS_DOT (entry->d_name) || DIR_IS_DOTDOT (entry->d_name))
 217                 continue;
 218         }
 219         else
 220         {
 221             /* Otherwise, if these match up to the length of filename, then
 222                it may be a match. */
 223             if ((entry->d_name[0] != filename[0]) ||
 224                 ((NLENGTH (entry)) < filename_len) ||
 225                 strncmp (filename, entry->d_name, filename_len))
 226                 continue;
 227         }
 228         isdir = 1;
 229         isexec = 0;
 230         {
 231             struct stat tempstat;
 232             vfs_path_t *tmp_vpath;
 233
 234             tmp_vpath = vfs_path_build_filename (dirname, entry->d_name, (char *) NULL);
 235
 236             /* Unix version */
 237             if (mc_stat (tmp_vpath, &tempstat) == 0)
 238             {
 239                 uid_t my_uid = getuid ();
 240                 gid_t my_gid = getgid ();
 241
 242                 if (!S_ISDIR (tempstat.st_mode))
 243                 {
 244                     isdir = 0;
 245                     if ((!my_uid && (tempstat.st_mode & 0111)) ||
 246                         (my_uid == tempstat.st_uid && (tempstat.st_mode & 0100)) ||
 247                         (my_gid == tempstat.st_gid && (tempstat.st_mode & 0010)) ||
 248                         (tempstat.st_mode & 0001))
 249                         isexec = 1;
 250                 }
 251             }
 252             else
 253             {
 254                 /* stat failed, strange. not a dir in any case */
 255                 isdir = 0;
 256             }
 257             vfs_path_free (tmp_vpath);
 258         }
 259         if ((flags & INPUT_COMPLETE_COMMANDS) && (isexec || isdir))
 260             break;
 261         if ((flags & INPUT_COMPLETE_CD) && isdir)
 262             break;
 263         if (flags & (INPUT_COMPLETE_FILENAMES))
 264             break;
 265     }
 266
 267     if (entry == NULL)
 268     {
 269         if (directory)
 270         {
 271             mc_closedir (directory);
 272             directory = NULL;
 273         }
 274         g_free (dirname);
 275         dirname = NULL;
 276         vfs_path_free (dirname_vpath);
 277         dirname_vpath = NULL;
 278         g_free (filename);
 279         filename = NULL;
 280         g_free (users_dirname);
 281         users_dirname = NULL;
 282         return NULL;
 283     }
 284
 285     {
 286         GString *temp;
 287
 288         temp = g_string_sized_new (16);
 289
 290         if (users_dirname != NULL && (users_dirname[0] != '.' || users_dirname[1] != '\0'))
 291         {
 292             g_string_append (temp, users_dirname);
 293
 294             /* We need a '/' at the end. */
 295             if (temp->str[temp->len - 1] != PATH_SEP)
 296                 g_string_append_c (temp, PATH_SEP);
 297         }
 298         g_string_append (temp, entry->d_name);
 299         if (isdir)
 300             g_string_append_c (temp, PATH_SEP);
 301
 302         return g_string_free (temp, FALSE);
 303     }
 304 }
 305
 306 /* --------------------------------------------------------------------------------------------- */
 307 /** We assume here that text[0] == '~' , if you want to call it in another way,
 308    you have to change the code */
 309
 310 static char *
 311 username_completion_function (const char *text, int state, input_complete_t flags)
 312 {
 313     static struct passwd *entry;
 314     static size_t userlen;
 315
 316     (void) flags;
 317     SHOW_C_CTX ("username_completion_function");
 318
 319     if (text[0] == '\\' && text[1] == '~')
 320         text++;
 321     if (state == 0)
 322     {                           /* Initialization stuff */
 323         setpwent ();
 324         userlen = strlen (text + 1);
 325     }
 326     while ((entry = getpwent ()) != NULL)
 327     {
 328         /* Null usernames should result in all users as possible completions. */
 329         if (userlen == 0)
 330             break;
 331         if (text[1] == entry->pw_name[0] && !strncmp (text + 1, entry->pw_name, userlen))
 332             break;
 333     }
 334
 335     if (entry != NULL)
 336         return g_strconcat ("~", entry->pw_name, PATH_SEP_STR, (char *) NULL);
 337
 338     endpwent ();
 339     return NULL;
 340 }
 341
 342 /* --------------------------------------------------------------------------------------------- */
 343 /** We assume text [0] == '$' and want to have a look at text [1], if it is
 344    equal to '{', so that we should append '}' at the end */
 345
 346 static char *
 347 variable_completion_function (const char *text, int state, input_complete_t flags)
 348 {
 349     static char **env_p;
 350     static unsigned int isbrace;
 351     static size_t varlen;
 352     const char *p = NULL;
 353
 354     (void) flags;
 355     SHOW_C_CTX ("variable_completion_function");
 356
 357     if (state == 0)
 358     {                           /* Initialization stuff */
 359         isbrace = (text[1] == '{') ? 1 : 0;
 360         varlen = strlen (text + 1 + isbrace);
 361         env_p = environ;
 362     }
 363
 364     while (*env_p)
 365     {
 366         p = strchr (*env_p, '=');
 367         if (p && ((size_t) (p - *env_p) >= varlen) && !strncmp (text + 1 + isbrace, *env_p, varlen))
 368             break;
 369         env_p++;
 370     }
 371
 372     if (*env_p == NULL)
 373         return NULL;
 374
 375     {
 376         GString *temp;
 377
 378         temp = g_string_new_len (*env_p, p - *env_p);
 379
 380         if (isbrace != 0)
 381         {
 382             g_string_prepend_c (temp, '{');
 383             g_string_append_c (temp, '}');
 384         }
 385         g_string_prepend_c (temp, '$');
 386
 387         env_p++;
 388
 389         return g_string_free (temp, FALSE);
 390     }
 391 }
 392
 393 /* --------------------------------------------------------------------------------------------- */
 394
 395 static void
 396 fetch_hosts (const char *filename)
 397 {
 398     FILE *file = fopen (filename, "r");
 399     char buffer[256], *name;
 400     char *lc_start;
 401     char *bi;
 402
 403     if (!file)
 404         return;
 405
 406     while (fgets (buffer, 255, file) != NULL)
 407     {
 408         /* Skip to first character. */
 409         for (bi = buffer; bi[0] != '\0' && str_isspace (bi); str_next_char (&bi));
 410
 411         /* Ignore comments... */
 412         if (bi[0] == '#')
 413             continue;
 414         /* Handle $include. */
 415         if (!strncmp (bi, "$include ", 9))
 416         {
 417             char *includefile = bi + 9;
 418             char *t;
 419
 420             /* Find start of filename. */
 421             while (*includefile && whitespace (*includefile))
 422                 includefile++;
 423             t = includefile;
 424
 425             /* Find end of filename. */
 426             while (t[0] != '\0' && !str_isspace (t))
 427                 str_next_char (&t);
 428             *t = '\0';
 429
 430             fetch_hosts (includefile);
 431             continue;
 432         }
 433
 434         /* Skip IP #s. */
 435         while (bi[0] != '\0' && !str_isspace (bi))
 436             str_next_char (&bi);
 437
 438         /* Get the host names separated by white space. */
 439         while (bi[0] != '\0' && bi[0] != '#')
 440         {
 441             while (bi[0] != '\0' && str_isspace (bi))
 442                 str_next_char (&bi);
 443             if (bi[0] == '#')
 444                 continue;
 445             for (lc_start = bi; bi[0] != '\0' && !str_isspace (bi); str_next_char (&bi));
 446
 447             if (bi - lc_start == 0)
 448                 continue;
 449
 450             name = g_strndup (lc_start, bi - lc_start);
 451             {
 452                 char **host_p;
 453
 454                 if (hosts_p - hosts >= hosts_alloclen)
 455                 {
 456                     int j;
 457
 458                     j = hosts_p - hosts;
 459                     hosts_alloclen += 30;
 460                     hosts = g_renew (char *, hosts, hosts_alloclen + 1);
 461                     hosts_p = hosts + j;
 462                 }
 463                 for (host_p = hosts; host_p < hosts_p; host_p++)
 464                     if (!strcmp (name, *host_p))
 465                         break;  /* We do not want any duplicates */
 466                 if (host_p == hosts_p)
 467                 {
 468                     *(hosts_p++) = name;
 469                     *hosts_p = NULL;
 470                 }
 471                 else
 472                     g_free (name);
 473             }
 474         }
 475     }
 476     fclose (file);
 477 }
 478
 479 /* --------------------------------------------------------------------------------------------- */
 480
 481 static char *
 482 hostname_completion_function (const char *text, int state, input_complete_t flags)
 483 {
 484     static char **host_p;
 485     static unsigned int textstart;
 486     static size_t textlen;
 487
 488     (void) flags;
 489     SHOW_C_CTX ("hostname_completion_function");
 490
 491     if (state == 0)
 492     {                           /* Initialization stuff */
 493         const char *p;
 494
 495         g_strfreev (hosts);
 496         hosts_alloclen = 30;
 497         hosts = g_new (char *, hosts_alloclen + 1);
 498         *hosts = NULL;
 499         hosts_p = hosts;
 500         p = getenv ("HOSTFILE");
 501         fetch_hosts (p != NULL ? p : "/etc/hosts");
 502         host_p = hosts;
 503         textstart = (*text == '@') ? 1 : 0;
 504         textlen = strlen (text + textstart);
 505     }
 506
 507     for (; *host_p != NULL; host_p++)
 508     {
 509         if (textlen == 0)
 510             break;              /* Match all of them */
 511         if (strncmp (text + textstart, *host_p, textlen) == 0)
 512             break;
 513     }
 514
 515     if (*host_p == NULL)
 516     {
 517         g_strfreev (hosts);
 518         hosts = NULL;
 519         return NULL;
 520     }
 521
 522     {
 523         GString *temp;
 524
 525         temp = g_string_sized_new (8);
 526
 527         if (textstart != 0)
 528             g_string_append_c (temp, '@');
 529         g_string_append (temp, *host_p);
 530         host_p++;
 531
 532         return g_string_free (temp, FALSE);
 533     }
 534 }
 535
 536 /* --------------------------------------------------------------------------------------------- */
 537 /**
 538  * This is the function to call when the word to complete is in a position
 539  * where a command word can be found. It looks around $PATH, looking for
 540  * commands that match. It also scans aliases, function names, and the
 541  * table of shell built-ins.
 542  */
 543
 544 static char *
 545 command_completion_function (const char *_text, int state, input_complete_t flags)
 546 {
 547     char *text;
 548     static const char *path_end;
 549     static gboolean isabsolute;
 550     static int phase;
 551     static size_t text_len;
 552     static const char *const *words;
 553     static char *path;
 554     static char *cur_path;
 555     static char *cur_word;
 556     static int init_state;
 557     static const char *const bash_reserved[] = {
 558         "if", "then", "else", "elif", "fi", "case", "esac", "for",
 559         "select", "while", "until", "do", "done", "in", "function", 0
 560     };
 561     static const char *const bash_builtins[] = {
 562         "alias", "bg", "bind", "break", "builtin", "cd", "command",
 563         "continue", "declare", "dirs", "echo", "enable", "eval",
 564         "exec", "exit", "export", "fc", "fg", "getopts", "hash",
 565         "help", "history", "jobs", "kill", "let", "local", "logout",
 566         "popd", "pushd", "pwd", "read", "readonly", "return", "set",
 567         "shift", "source", "suspend", "test", "times", "trap", "type",
 568         "typeset", "ulimit", "umask", "unalias", "unset", "wait", 0
 569     };
 570     char *p, *found;
 571
 572     /* cppcheck-suppress uninitvar */
 573     SHOW_C_CTX ("command_completion_function");
 574
 575     if (!(flags & INPUT_COMPLETE_COMMANDS))
 576         return 0;
 577
 578     text = strutils_shell_unescape (_text);
 579     flags &= ~INPUT_COMPLETE_SHELL_ESC;
 580
 581     if (state == 0)
 582     {                           /* Initialize us a little bit */
 583         isabsolute = strchr (text, PATH_SEP) != NULL;
 584         if (!isabsolute)
 585         {
 586             words = bash_reserved;
 587             phase = 0;
 588             text_len = strlen (text);
 589
 590             if (path == NULL)
 591             {
 592                 path = g_strdup (getenv ("PATH"));
 593                 if (path != NULL)
 594                 {
 595                     p = path;
 596                     path_end = strchr (p, '\0');
 597                     while ((p = strchr (p, PATH_ENV_SEP)) != NULL)
 598                     {
 599                         *p++ = '\0';
 600                     }
 601                 }
 602             }
 603         }
 604     }
 605
 606     if (isabsolute)
 607     {
 608         p = filename_completion_function (text, state, flags);
 609
 610         if (p != NULL)
 611         {
 612             char *temp_p = p;
 613
 614             p = strutils_shell_escape (p);
 615             g_free (temp_p);
 616         }
 617
 618         g_free (text);
 619         return p;
 620     }
 621
 622     found = NULL;
 623     switch (phase)
 624     {
 625     case 0:                    /* Reserved words */
 626         for (; *words != NULL; words++)
 627             if (strncmp (*words, text, text_len) == 0)
 628             {
 629                 g_free (text);
 630                 return g_strdup (*(words++));
 631             }
 632         phase++;
 633         words = bash_builtins;
 634     case 1:                    /* Builtin commands */
 635         for (; *words != NULL; words++)
 636             if (strncmp (*words, text, text_len) == 0)
 637             {
 638                 g_free (text);
 639                 return g_strdup (*(words++));
 640             }
 641         phase++;
 642         if (!path)
 643             break;
 644         cur_path = path;
 645         cur_word = NULL;
 646     case 2:                    /* And looking through the $PATH */
 647         while (!found)
 648         {
 649             if (!cur_word)
 650             {
 651                 char *expanded;
 652
 653                 if (cur_path >= path_end)
 654                     break;
 655                 expanded = tilde_expand (*cur_path ? cur_path : ".");
 656                 cur_word = mc_build_filename (expanded, text, NULL);
 657                 g_free (expanded);
 658                 canonicalize_pathname (cur_word);
 659                 cur_path = strchr (cur_path, 0) + 1;
 660                 init_state = state;
 661             }
 662             found = filename_completion_function (cur_word, state - init_state, flags);
 663             if (!found)
 664             {
 665                 g_free (cur_word);
 666                 cur_word = NULL;
 667             }
 668         }
 669     }
 670
 671     if (found == NULL)
 672     {
 673         g_free (path);
 674         path = NULL;
 675     }
 676     else
 677     {
 678         p = strrchr (found, PATH_SEP);
 679         if (p != NULL)
 680         {
 681             char *tmp = found;
 682             found = strutils_shell_escape (p + 1);
 683             g_free (tmp);
 684         }
 685     }
 686
 687     g_free (text);
 688     return found;
 689 }
 690
 691 /* --------------------------------------------------------------------------------------------- */
 692
 693 static int
 694 match_compare (const void *a, const void *b)
 695 {
 696     return strcmp (*(char **) a, *(char **) b);
 697 }
 698
 699 /* --------------------------------------------------------------------------------------------- */
 700 /** Returns an array of char * matches with the longest common denominator
 701    in the 1st entry. Then a NULL terminated list of different possible
 702    completions follows.
 703    You have to supply your own CompletionFunction with the word you
 704    want to complete as the first argument and an count of previous matches
 705    as the second.
 706    In case no matches were found we return NULL. */
 707
 708 static char **
 709 completion_matches (const char *text, CompletionFunction entry_function, input_complete_t flags)
 710 {
 711     /* Number of slots in match_list. */
 712     size_t match_list_size = 30;
 713     /* The list of matches. */
 714     char **match_list;
 715     /* Number of matches actually found. */
 716     size_t matches = 0;
 717
 718     /* Temporary string binder. */
 719     char *string;
 720
 721     match_list = g_new (char *, match_list_size + 1);
 722     match_list[1] = NULL;
 723
 724     while ((string = (*entry_function) (text, matches, flags)) != NULL)
 725     {
 726         if (matches + 1 == match_list_size)
 727         {
 728             match_list_size += 30;
 729             match_list = (char **) g_renew (char *, match_list, match_list_size + 1);
 730         }
 731         match_list[++matches] = string;
 732         match_list[matches + 1] = NULL;
 733     }
 734
 735     /* If there were any matches, then look through them finding out the
 736        lowest common denominator.  That then becomes match_list[0]. */
 737     if (matches)
 738     {
 739
 740         /* If only one match, just use that. */
 741         if (matches == 1)
 742         {
 743             match_list[0] = match_list[1];
 744             match_list[1] = NULL;
 745         }
 746         else
 747         {
 748             size_t i = 1;
 749             int low = 4096;     /* Count of max-matched characters. */
 750             size_t j;
 751
 752             qsort (match_list + 1, matches, sizeof (char *), match_compare);
 753
 754             /* And compare each member of the list with
 755                the next, finding out where they stop matching.
 756                If we find two equal strings, we have to put one away... */
 757
 758             j = i + 1;
 759             while (j < matches + 1)
 760             {
 761                 char *si, *sj;
 762                 char *ni, *nj;
 763
 764                 for (si = match_list[i], sj = match_list[j]; si[0] && sj[0];)
 765                 {
 766
 767                     ni = str_get_next_char (si);
 768                     nj = str_get_next_char (sj);
 769
 770                     if (ni - si != nj - sj)
 771                         break;
 772                     if (strncmp (si, sj, ni - si) != 0)
 773                         break;
 774
 775                     si = ni;
 776                     sj = nj;
 777                 }
 778
 779                 if (si[0] == '\0' && sj[0] == '\0')
 780                 {               /* Two equal strings */
 781                     g_free (match_list[j]);
 782                     j++;
 783                     if (j > matches)
 784                         break;
 785                     continue;   /* Look for a run of equal strings */
 786                 }
 787                 else if (low > si - match_list[i])
 788                     low = si - match_list[i];
 789                 if (i + 1 != j) /* So there's some gap */
 790                     match_list[i + 1] = match_list[j];
 791                 i++;
 792                 j++;
 793             }
 794             matches = i;
 795             match_list[matches + 1] = NULL;
 796             match_list[0] = g_strndup (match_list[1], low);
 797         }
 798     }
 799     else
 800     {                           /* There were no matches. */
 801         g_free (match_list);
 802         match_list = NULL;
 803     }
 804     return match_list;
 805 }
 806
 807 /* --------------------------------------------------------------------------------------------- */
 808 /** Check if directory completion is needed */
 809 static gboolean
 810 check_is_cd (const char *text, int lc_start, input_complete_t flags)
 811 {
 812     char *p, *q;
 813
 814     SHOW_C_CTX ("check_is_cd");
 815
 816     if ((flags & INPUT_COMPLETE_CD) == 0)
 817         return FALSE;
 818
 819     /* Skip initial spaces */
 820     p = (char *) text;
 821     q = (char *) text + lc_start;
 822     while (p < q && p[0] != '\0' && str_isspace (p))
 823         str_next_char (&p);
 824
 825     /* Check if the command is "cd" and the cursor is after it */
 826     return (p[0] == 'c' && p[1] == 'd' && str_isspace (p + 2) && p + 2 < q);
 827 }
 828
 829 /* --------------------------------------------------------------------------------------------- */
 830
 831 static void
 832 try_complete_commands_prepare (try_complete_automation_state_t * state, char *text, int *lc_start)
 833 {
 834     const char *command_separator_chars = ";|&{(`";
 835     char *ti;
 836
 837     if (*lc_start == 0)
 838         ti = text;
 839     else
 840     {
 841         ti = str_get_prev_char (&text[*lc_start]);
 842         while (ti > text && (ti[0] == ' ' || ti[0] == '\t'))
 843             str_prev_char (&ti);
 844     }
 845
 846     if (ti == text)
 847         state->in_command_position++;
 848     else if (strchr (command_separator_chars, ti[0]) != NULL)
 849     {
 850         state->in_command_position++;
 851         if (ti != text)
 852         {
 853             int this_char, prev_char;
 854
 855             /* Handle the two character tokens '>&', '<&', and '>|'.
 856                We are not in a command position after one of these. */
 857             this_char = ti[0];
 858             prev_char = str_get_prev_char (ti)[0];
 859
 860             /* Quoted */
 861             if ((this_char == '&' && (prev_char == '<' || prev_char == '>'))
 862                 || (this_char == '|' && prev_char == '>') || (ti != text
 863                                                               && str_get_prev_char (ti)[0] == '\\'))
 864                 state->in_command_position = 0;
 865         }
 866     }
 867 }
 868
 869 /* --------------------------------------------------------------------------------------------- */
 870
 871 static void
 872 try_complete_find_start_sign (try_complete_automation_state_t * state)
 873 {
 874     if (state->flags & INPUT_COMPLETE_COMMANDS)
 875         state->p = strrchr (state->word, '`');
 876     if (state->flags & (INPUT_COMPLETE_COMMANDS | INPUT_COMPLETE_VARIABLES))
 877     {
 878         state->q = strrchr (state->word, '$');
 879
 880         /* don't substitute variable in \$ case */
 881         if (strutils_is_char_escaped (state->word, state->q))
 882         {
 883             size_t qlen;
 884
 885             qlen = strlen (state->q);
 886             /* drop '\\' */
 887             memmove (state->q - 1, state->q, qlen + 1);
 888             /* adjust flags */
 889             state->flags &= ~INPUT_COMPLETE_VARIABLES;
 890             state->q = NULL;
 891         }
 892     }
 893     if (state->flags & INPUT_COMPLETE_HOSTNAMES)
 894         state->r = strrchr (state->word, '@');
 895     if (state->q && state->q[1] == '(' && (state->flags & INPUT_COMPLETE_COMMANDS))
 896     {
 897         if (state->q > state->p)
 898             state->p = str_get_next_char (state->q);
 899         state->q = NULL;
 900     }
 901 }
 902
 903 /* --------------------------------------------------------------------------------------------- */
 904
 905 static char **
 906 try_complete_all_possible (try_complete_automation_state_t * state, char *text, int *lc_start)
 907 {
 908     char **matches = NULL;
 909
 910     if (state->in_command_position != 0)
 911     {
 912         SHOW_C_CTX ("try_complete:cmd_subst");
 913         matches =
 914             completion_matches (state->word, command_completion_function,
 915                                 state->flags & (~INPUT_COMPLETE_FILENAMES));
 916     }
 917     else if ((state->flags & INPUT_COMPLETE_FILENAMES) != 0)
 918     {
 919         if (state->is_cd)
 920             state->flags &= ~(INPUT_COMPLETE_FILENAMES | INPUT_COMPLETE_COMMANDS);
 921         SHOW_C_CTX ("try_complete:filename_subst_1");
 922         matches = completion_matches (state->word, filename_completion_function, state->flags);
 923
 924         if (matches == NULL && state->is_cd && *state->word != PATH_SEP && *state->word != '~')
 925         {
 926             state->q = text + *lc_start;
 927             for (state->p = text;
 928                  *state->p && state->p < state->q && (*state->p == ' ' || *state->p == '\t');
 929                  str_next_char (&state->p))
 930                 ;
 931             if (!strncmp (state->p, "cd", 2))
 932                 for (state->p += 2;
 933                      *state->p && state->p < state->q && (*state->p == ' ' || *state->p == '\t');
 934                      str_next_char (&state->p))
 935                     ;
 936             if (state->p == state->q)
 937             {
 938                 char *const cdpath_ref = g_strdup (getenv ("CDPATH"));
 939                 char *cdpath = cdpath_ref;
 940                 char c;
 941
 942                 c = (cdpath == NULL) ? '\0' : ':';
 943
 944                 while (!matches && c == ':')
 945                 {
 946                     char *s;
 947
 948                     s = strchr (cdpath, ':');
 949                     if (s == NULL)
 950                         s = strchr (cdpath, '\0');
 951                     c = *s;
 952                     *s = '\0';
 953                     if (*cdpath != '\0')
 954                     {
 955                         state->r = mc_build_filename (cdpath, state->word, NULL);
 956                         SHOW_C_CTX ("try_complete:filename_subst_2");
 957                         matches =
 958                             completion_matches (state->r, filename_completion_function,
 959                                                 state->flags);
 960                         g_free (state->r);
 961                     }
 962                     *s = c;
 963                     cdpath = str_get_next_char (s);
 964                 }
 965                 g_free (cdpath_ref);
 966             }
 967         }
 968     }
 969     return matches;
 970 }
 971
 972 /* --------------------------------------------------------------------------------------------- */
 973
 974 static gboolean
 975 insert_text (WInput * in, char *text, ssize_t size)
 976 {
 977     int buff_len;
 978
 979     buff_len = str_length (in->buffer);
 980     size = min (size, (ssize_t) strlen (text)) + start - end;
 981     if (strlen (in->buffer) + size >= (size_t) in->current_max_size)
 982     {
 983         /* Expand the buffer */
 984         char *narea;
 985         Widget *w = WIDGET (in);
 986
 987         narea = g_try_realloc (in->buffer, in->current_max_size + size + w->cols);
 988         if (narea != NULL)
 989         {
 990             in->buffer = narea;
 991             in->current_max_size += size + w->cols;
 992         }
 993     }
 994     if (strlen (in->buffer) + 1 < (size_t) in->current_max_size)
 995     {
 996         if (size != 0)
 997             memmove (in->buffer + end + size, in->buffer + end, strlen (&in->buffer[end]) + 1);
 998         memmove (in->buffer + start, text, size - (start - end));
 999         in->point += str_length (in->buffer) - buff_len;
1000         input_update (in, TRUE);
1001         end += size;
1002     }
1003     return size != 0;
1004 }
1005
1006 /* --------------------------------------------------------------------------------------------- */
1007
1008 static cb_ret_t
1009 query_callback (Widget * w, Widget * sender, widget_msg_t msg, int parm, void *data)
1010 {
1011     static int bl = 0;
1012
1013     WDialog *h = DIALOG (w);
1014
1015     switch (msg)
1016     {
1017     case MSG_KEY:
1018         switch (parm)
1019         {
1020         case KEY_LEFT:
1021         case KEY_RIGHT:
1022             bl = 0;
1023             h->ret_value = 0;
1024             dlg_stop (h);
1025             return MSG_HANDLED;
1026
1027         case KEY_BACKSPACE:
1028             bl = 0;
1029             /* exit from completion list if input line is empty */
1030             if (end == 0)
1031             {
1032                 h->ret_value = 0;
1033                 dlg_stop (h);
1034             }
1035             /* Refill the list box and start again */
1036             else if (end == min_end)
1037             {
1038                 end = str_get_prev_char (&input->buffer[end]) - input->buffer;
1039                 input_handle_char (input, parm);
1040                 h->ret_value = B_USER;
1041                 dlg_stop (h);
1042                 return MSG_HANDLED;
1043             }
1044             else
1045             {
1046                 int new_end;
1047                 int i;
1048                 GList *e;
1049
1050                 new_end = str_get_prev_char (&input->buffer[end]) - input->buffer;
1051
1052                 for (i = 0, e = LISTBOX (h->current->data)->list;
1053                      e != NULL; i++, e = g_list_next (e))
1054                 {
1055                     WLEntry *le = LENTRY (e->data);
1056
1057                     if (strncmp (input->buffer + start, le->text, new_end - start) == 0)
1058                     {
1059                         listbox_select_entry (LISTBOX (h->current->data), i);
1060                         end = new_end;
1061                         input_handle_char (input, parm);
1062                         widget_redraw (WIDGET (h->current->data));
1063                         break;
1064                     }
1065                 }
1066             }
1067             return MSG_HANDLED;
1068
1069         default:
1070             if (parm < 32 || parm > 255)
1071             {
1072                 bl = 0;
1073                 if (input_key_is_in_map (input, parm) != 2)
1074                     return MSG_NOT_HANDLED;
1075
1076                 if (end == min_end)
1077                     return MSG_HANDLED;
1078
1079                 /* This means we want to refill the list box and start again */
1080                 h->ret_value = B_USER;
1081                 dlg_stop (h);
1082                 return MSG_HANDLED;
1083             }
1084             else
1085             {
1086                 static char buff[MB_LEN_MAX] = "";
1087                 GList *e;
1088                 int i;
1089                 int need_redraw = 0;
1090                 int low = 4096;
1091                 char *last_text = NULL;
1092
1093                 buff[bl++] = (char) parm;
1094                 buff[bl] = '\0';
1095                 switch (str_is_valid_char (buff, bl))
1096                 {
1097                 case -1:
1098                     bl = 0;
1099                     /* fallthrough */
1100                 case -2:
1101                     return MSG_HANDLED;
1102                 }
1103
1104                 for (i = 0, e = LISTBOX (h->current->data)->list;
1105                      e != NULL; i++, e = g_list_next (e))
1106                 {
1107                     WLEntry *le = LENTRY (e->data);
1108
1109                     if (strncmp (input->buffer + start, le->text, end - start) == 0
1110                         && strncmp (&le->text[end - start], buff, bl) == 0)
1111                     {
1112                         if (need_redraw == 0)
1113                         {
1114                             need_redraw = 1;
1115                             listbox_select_entry (LISTBOX (h->current->data), i);
1116                             last_text = le->text;
1117                         }
1118                         else
1119                         {
1120                             char *si, *sl;
1121                             int si_num = 0;
1122                             int sl_num = 0;
1123
1124                             /* count symbols between start and end */
1125                             for (si = le->text + start; si < le->text + end;
1126                                  str_next_char (&si), si_num++)
1127                                 ;
1128                             for (sl = last_text + start; sl < last_text + end;
1129                                  str_next_char (&sl), sl_num++)
1130                                 ;
1131
1132                             /* pointers to next symbols */
1133                             si = &le->text[str_offset_to_pos (le->text, ++si_num)];
1134                             sl = &last_text[str_offset_to_pos (last_text, ++sl_num)];
1135
1136                             while (si[0] != '\0' && sl[0] != '\0')
1137                             {
1138                                 char *nexti, *nextl;
1139
1140                                 nexti = str_get_next_char (si);
1141                                 nextl = str_get_next_char (sl);
1142
1143                                 if (nexti - si != nextl - sl || strncmp (si, sl, nexti - si) != 0)
1144                                     break;
1145
1146                                 si = nexti;
1147                                 sl = nextl;
1148
1149                                 si_num++;
1150                             }
1151
1152                             last_text = le->text;
1153
1154                             si = &last_text[str_offset_to_pos (last_text, si_num)];
1155                             if (low > si - last_text)
1156                                 low = si - last_text;
1157
1158                             need_redraw = 2;
1159                         }
1160                     }
1161                 }
1162
1163                 if (need_redraw == 2)
1164                 {
1165                     insert_text (input, last_text, low);
1166                     widget_redraw (WIDGET (h->current->data));
1167                 }
1168                 else if (need_redraw == 1)
1169                 {
1170                     h->ret_value = B_ENTER;
1171                     dlg_stop (h);
1172                 }
1173                 bl = 0;
1174             }
1175             return MSG_HANDLED;
1176         }
1177         break;
1178
1179     default:
1180         return dlg_default_callback (w, sender, msg, parm, data);
1181     }
1182 }
1183
1184 /* --------------------------------------------------------------------------------------------- */
1185
1186 /** Returns 1 if the user would like to see us again */
1187 static int
1188 complete_engine (WInput * in, int what_to_do)
1189 {
1190     if (in->completions != NULL && str_offset_to_pos (in->buffer, in->point) != end)
1191         input_free_completions (in);
1192
1193     if (in->completions == NULL)
1194         complete_engine_fill_completions (in);
1195
1196     if (in->completions != NULL)
1197     {
1198         if (what_to_do & DO_INSERTION || ((what_to_do & DO_QUERY) && !in->completions[1]))
1199         {
1200             char *lc_complete = in->completions[0];
1201             if (insert_text (in, lc_complete, strlen (lc_complete)))
1202             {
1203                 if (in->completions[1])
1204                     tty_beep ();
1205                 else
1206                     input_free_completions (in);
1207             }
1208             else
1209                 tty_beep ();
1210         }
1211         if ((what_to_do & DO_QUERY) && in->completions && in->completions[1])
1212         {
1213             int maxlen = 0, i, count = 0;
1214             int x, y, w, h;
1215             int start_x, start_y;
1216             char **p, *q;
1217             WDialog *query_dlg;
1218             WListbox *query_list;
1219
1220             for (p = in->completions + 1; *p != NULL; count++, p++)
1221             {
1222                 i = str_term_width1 (*p);
1223                 if (i > maxlen)
1224                     maxlen = i;
1225             }
1226             start_x = WIDGET (in)->x;
1227             start_y = WIDGET (in)->y;
1228             if (start_y - 2 >= count)
1229             {
1230                 y = start_y - 2 - count;
1231                 h = 2 + count;
1232             }
1233             else
1234             {
1235                 if (start_y >= LINES - start_y - 1)
1236                 {
1237                     y = 0;
1238                     h = start_y;
1239                 }
1240                 else
1241                 {
1242                     y = start_y + 1;
1243                     h = LINES - start_y - 1;
1244                 }
1245             }
1246             x = start - in->term_first_shown - 2 + start_x;
1247             w = maxlen + 4;
1248             if (x + w > COLS)
1249                 x = COLS - w;
1250             if (x < 0)
1251                 x = 0;
1252             if (x + w > COLS)
1253                 w = COLS;
1254             input = in;
1255             min_end = end;
1256             query_height = h;
1257             query_width = w;
1258             query_dlg = dlg_create (TRUE, y, x, query_height, query_width,
1259                                     dialog_colors, query_callback, NULL,
1260                                     "[Completion]", NULL, DLG_COMPACT);
1261             query_list = listbox_new (1, 1, h - 2, w - 2, FALSE, NULL);
1262             add_widget (query_dlg, query_list);
1263             for (p = in->completions + 1; *p; p++)
1264                 listbox_add_item (query_list, LISTBOX_APPEND_AT_END, 0, *p, NULL);
1265             dlg_run (query_dlg);
1266             q = NULL;
1267             if (query_dlg->ret_value == B_ENTER)
1268             {
1269                 listbox_get_current (query_list, &q, NULL);
1270                 if (q)
1271                     insert_text (in, q, strlen (q));
1272             }
1273             if (q || end != min_end)
1274                 input_free_completions (in);
1275             i = query_dlg->ret_value;   /* B_USER if user wants to start over again */
1276             dlg_destroy (query_dlg);
1277             if (i == B_USER)
1278                 return 1;
1279         }
1280     }
1281     else
1282         tty_beep ();
1283     return 0;
1284 }
1285
1286 /* --------------------------------------------------------------------------------------------- */
1287 /*** public functions ****************************************************************************/
1288 /* --------------------------------------------------------------------------------------------- */
1289
1290 /** Returns an array of matches, or NULL if none. */
1291 char **
1292 try_complete (char *text, int *lc_start, int *lc_end, input_complete_t flags)
1293 {
1294     try_complete_automation_state_t state;
1295     char **matches = NULL;
1296
1297     memset (&state, 0, sizeof (try_complete_automation_state_t));
1298     state.flags = flags;
1299
1300     SHOW_C_CTX ("try_complete");
1301     state.word = g_strndup (text + *lc_start, *lc_end - *lc_start);
1302
1303     state.is_cd = check_is_cd (text, *lc_start, state.flags);
1304
1305     /* Determine if this could be a command word. It is if it appears at
1306        the start of the line (ignoring preceding whitespace), or if it
1307        appears after a character that separates commands. And we have to
1308        be in a INPUT_COMPLETE_COMMANDS flagged Input line. */
1309     if (!state.is_cd && (flags & INPUT_COMPLETE_COMMANDS))
1310         try_complete_commands_prepare (&state, text, lc_start);
1311
1312     try_complete_find_start_sign (&state);
1313
1314     /* Command substitution? */
1315     if (state.p > state.q && state.p > state.r)
1316     {
1317         SHOW_C_CTX ("try_complete:cmd_backq_subst");
1318         matches = completion_matches (str_cget_next_char (state.p),
1319                                       command_completion_function,
1320                                       state.flags & (~INPUT_COMPLETE_FILENAMES));
1321         if (matches)
1322             *lc_start += str_get_next_char (state.p) - state.word;
1323     }
1324
1325     /* Variable name? */
1326     else if (state.q > state.p && state.q > state.r)
1327     {
1328         SHOW_C_CTX ("try_complete:var_subst");
1329         matches = completion_matches (state.q, variable_completion_function, state.flags);
1330         if (matches)
1331             *lc_start += state.q - state.word;
1332     }
1333
1334     /* Starts with '@', then look through the known hostnames for
1335        completion first. */
1336     else if (state.r > state.p && state.r > state.q)
1337     {
1338         SHOW_C_CTX ("try_complete:host_subst");
1339         matches = completion_matches (state.r, hostname_completion_function, state.flags);
1340         if (matches)
1341             *lc_start += state.r - state.word;
1342     }
1343
1344     /* Starts with '~' and there is no slash in the word, then
1345        try completing this word as a username. */
1346     if (!matches && *state.word == '~' && (state.flags & INPUT_COMPLETE_USERNAMES)
1347         && !strchr (state.word, PATH_SEP))
1348     {
1349         SHOW_C_CTX ("try_complete:user_subst");
1350         matches = completion_matches (state.word, username_completion_function, state.flags);
1351     }
1352
1353     /* If this word is in a command position, then
1354        complete over possible command names, including aliases, functions,
1355        and command names. */
1356     if (matches == NULL)
1357         matches = try_complete_all_possible (&state, text, lc_start);
1358
1359     /* And finally if nothing found, try complete directory name */
1360     if (matches == NULL)
1361     {
1362         state.in_command_position = 0;
1363         matches = try_complete_all_possible (&state, text, lc_start);
1364     }
1365
1366     g_free (state.word);
1367
1368     if (matches != NULL &&
1369         (flags & (INPUT_COMPLETE_FILENAMES | INPUT_COMPLETE_SHELL_ESC)) !=
1370         (INPUT_COMPLETE_FILENAMES | INPUT_COMPLETE_SHELL_ESC))
1371     {
1372         /* FIXME: HACK? INPUT_COMPLETE_SHELL_ESC is used only in command line. */
1373         char **m;
1374
1375         for (m = matches; *m != NULL; m++)
1376         {
1377             char *p;
1378
1379             p = *m;
1380             *m = strutils_shell_escape (*m);
1381             g_free (p);
1382         }
1383     }
1384
1385     return matches;
1386 }
1387
1388 /* --------------------------------------------------------------------------------------------- */
1389
1390 void
1391 complete_engine_fill_completions (WInput * in)
1392 {
1393     char *s;
1394     const char *word_separators;
1395
1396     word_separators = (in->completion_flags & INPUT_COMPLETE_SHELL_ESC) ? " \t;|<>" : "\t;|<>";
1397
1398     end = str_offset_to_pos (in->buffer, in->point);
1399
1400     s = in->buffer;
1401     if (in->point != 0)
1402     {
1403         /* get symbol before in->point */
1404         size_t i;
1405
1406         for (i = in->point - 1; i > 0; i--)
1407             str_next_char (&s);
1408     }
1409
1410     for (; s >= in->buffer; str_prev_char (&s))
1411     {
1412         start = s - in->buffer;
1413         if (strchr (word_separators, *s) != NULL && !strutils_is_char_escaped (in->buffer, s))
1414             break;
1415     }
1416
1417     if (start < end)
1418     {
1419         str_next_char (&s);
1420         start = s - in->buffer;
1421     }
1422
1423     in->completions = try_complete (in->buffer, &start, &end, in->completion_flags);
1424 }
1425
1426 /* --------------------------------------------------------------------------------------------- */
1427
1428 /* declared in lib/widget/input.h */
1429 void
1430 complete (WInput * in)
1431 {
1432     int engine_flags;
1433
1434     if (!str_is_valid_string (in->buffer))
1435         return;
1436
1437     if (in->completions != NULL)
1438         engine_flags = DO_QUERY;
1439     else
1440     {
1441         engine_flags = DO_INSERTION;
1442
1443         if (mc_global.widget.show_all_if_ambiguous)
1444             engine_flags |= DO_QUERY;
1445     }
1446
1447     while (complete_engine (in, engine_flags))
1448         ;
1449 }
1450
1451 /* --------------------------------------------------------------------------------------------- */