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