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