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 (Widget * w, Widget * sender, widget_msg_t msg, int parm, void *data)
1052 {
1053     static char buff[MB_LEN_MAX] = "";
1054     static int bl = 0;
1055
1056     WDialog *h = DIALOG (w);
1057
1058     switch (msg)
1059     {
1060     case MSG_KEY:
1061         switch (parm)
1062         {
1063         case KEY_LEFT:
1064         case KEY_RIGHT:
1065             bl = 0;
1066             h->ret_value = 0;
1067             dlg_stop (h);
1068             return MSG_HANDLED;
1069
1070         case KEY_BACKSPACE:
1071             bl = 0;
1072             /* exit from completion list if input line is empty */
1073             if (end == 0)
1074             {
1075                 h->ret_value = 0;
1076                 dlg_stop (h);
1077             }
1078             /* Refill the list box and start again */
1079             else if (end == min_end)
1080             {
1081                 end = str_get_prev_char (&input->buffer[end]) - input->buffer;
1082                 input_handle_char (input, parm);
1083                 h->ret_value = B_USER;
1084                 dlg_stop (h);
1085                 return MSG_HANDLED;
1086             }
1087             else
1088             {
1089                 int new_end;
1090                 int i;
1091                 GList *e;
1092
1093                 new_end = str_get_prev_char (&input->buffer[end]) - input->buffer;
1094
1095                 for (i = 0, e = ((WListbox *) h->current->data)->list;
1096                      e != NULL; i++, e = g_list_next (e))
1097                 {
1098                     WLEntry *le = (WLEntry *) e->data;
1099
1100                     if (strncmp (input->buffer + start, le->text, new_end - start) == 0)
1101                     {
1102                         listbox_select_entry ((WListbox *) h->current->data, i);
1103                         end = new_end;
1104                         input_handle_char (input, parm);
1105                         send_message (h->current->data, NULL, MSG_DRAW, 0, NULL);
1106                         break;
1107                     }
1108                 }
1109             }
1110             return MSG_HANDLED;
1111
1112         default:
1113             if (parm < 32 || parm > 255)
1114             {
1115                 bl = 0;
1116                 if (input_key_is_in_map (input, parm) != 2)
1117                     return MSG_NOT_HANDLED;
1118
1119                 if (end == min_end)
1120                     return MSG_HANDLED;
1121
1122                 /* This means we want to refill the list box and start again */
1123                 h->ret_value = B_USER;
1124                 dlg_stop (h);
1125                 return MSG_HANDLED;
1126             }
1127             else
1128             {
1129                 GList *e;
1130                 int i;
1131                 int need_redraw = 0;
1132                 int low = 4096;
1133                 char *last_text = NULL;
1134
1135                 buff[bl++] = (char) parm;
1136                 buff[bl] = '\0';
1137                 switch (str_is_valid_char (buff, bl))
1138                 {
1139                 case -1:
1140                     bl = 0;
1141                     /* fallthrough */
1142                 case -2:
1143                     return MSG_HANDLED;
1144                 }
1145
1146                 for (i = 0, e = ((WListbox *) h->current->data)->list;
1147                      e != NULL; i++, e = g_list_next (e))
1148                 {
1149                     WLEntry *le = (WLEntry *) e->data;
1150
1151                     if (strncmp (input->buffer + start, le->text, end - start) == 0
1152                         && strncmp (&le->text[end - start], buff, bl) == 0)
1153                     {
1154                         if (need_redraw == 0)
1155                         {
1156                             need_redraw = 1;
1157                             listbox_select_entry ((WListbox *) h->current->data, i);
1158                             last_text = le->text;
1159                         }
1160                         else
1161                         {
1162                             char *si, *sl;
1163                             int si_num = 0;
1164                             int sl_num = 0;
1165
1166                             /* count symbols between start and end */
1167                             for (si = le->text + start; si < le->text + end;
1168                                  str_next_char (&si), si_num++)
1169                                 ;
1170                             for (sl = last_text + start; sl < last_text + end;
1171                                  str_next_char (&sl), sl_num++)
1172                                 ;
1173
1174                             /* pointers to next symbols */
1175                             si = &le->text[str_offset_to_pos (le->text, ++si_num)];
1176                             sl = &last_text[str_offset_to_pos (last_text, ++sl_num)];
1177
1178                             while (si[0] != '\0' && sl[0] != '\0')
1179                             {
1180                                 char *nexti, *nextl;
1181
1182                                 nexti = str_get_next_char (si);
1183                                 nextl = str_get_next_char (sl);
1184
1185                                 if (nexti - si != nextl - sl || strncmp (si, sl, nexti - si) != 0)
1186                                     break;
1187
1188                                 si = nexti;
1189                                 sl = nextl;
1190
1191                                 si_num++;
1192                             }
1193
1194                             last_text = le->text;
1195
1196                             si = &last_text[str_offset_to_pos (last_text, si_num)];
1197                             if (low > si - last_text)
1198                                 low = si - last_text;
1199
1200                             need_redraw = 2;
1201                         }
1202                     }
1203                 }
1204
1205                 if (need_redraw == 2)
1206                 {
1207                     insert_text (input, last_text, low);
1208                     send_message (h->current->data, NULL, MSG_DRAW, 0, NULL);
1209                 }
1210                 else if (need_redraw == 1)
1211                 {
1212                     h->ret_value = B_ENTER;
1213                     dlg_stop (h);
1214                 }
1215                 bl = 0;
1216             }
1217             return MSG_HANDLED;
1218         }
1219         break;
1220
1221     default:
1222         return dlg_default_callback (w, sender, msg, parm, data);
1223     }
1224 }
1225
1226 /* --------------------------------------------------------------------------------------------- */
1227 /** Returns 1 if the user would like to see us again */
1228
1229 static int
1230 complete_engine (WInput * in, int what_to_do)
1231 {
1232     if (in->completions != NULL && str_offset_to_pos (in->buffer, in->point) != end)
1233         input_free_completions (in);
1234     if (in->completions == NULL)
1235     {
1236         char *s;
1237
1238         end = str_offset_to_pos (in->buffer, in->point);
1239
1240         s = in->buffer;
1241         if (in->point != 0)
1242         {
1243             /* get symbol before in->point */
1244             size_t i;
1245             for (i = in->point - 1; i > 0; i--)
1246                 str_next_char (&s);
1247         }
1248
1249         for (; s >= in->buffer; str_prev_char (&s))
1250         {
1251             start = s - in->buffer;
1252             if (strchr (" \t;|<>", *s) != NULL)
1253                 break;
1254         }
1255
1256         if (start < end)
1257         {
1258             str_next_char (&s);
1259             start = s - in->buffer;
1260         }
1261
1262         in->completions = try_complete (in->buffer, &start, &end, in->completion_flags);
1263     }
1264
1265     if (in->completions != NULL)
1266     {
1267         if (what_to_do & DO_INSERTION || ((what_to_do & DO_QUERY) && !in->completions[1]))
1268         {
1269             char *lc_complete = in->completions[0];
1270             if (insert_text (in, lc_complete, strlen (lc_complete)))
1271             {
1272                 if (in->completions[1])
1273                     tty_beep ();
1274                 else
1275                     input_free_completions (in);
1276             }
1277             else
1278                 tty_beep ();
1279         }
1280         if ((what_to_do & DO_QUERY) && in->completions && in->completions[1])
1281         {
1282             int maxlen = 0, i, count = 0;
1283             int x, y, w, h;
1284             int start_x, start_y;
1285             char **p, *q;
1286             WDialog *query_dlg;
1287             WListbox *query_list;
1288
1289             for (p = in->completions + 1; *p != NULL; count++, p++)
1290             {
1291                 i = str_term_width1 (*p);
1292                 if (i > maxlen)
1293                     maxlen = i;
1294             }
1295             start_x = WIDGET (in)->x;
1296             start_y = WIDGET (in)->y;
1297             if (start_y - 2 >= count)
1298             {
1299                 y = start_y - 2 - count;
1300                 h = 2 + count;
1301             }
1302             else
1303             {
1304                 if (start_y >= LINES - start_y - 1)
1305                 {
1306                     y = 0;
1307                     h = start_y;
1308                 }
1309                 else
1310                 {
1311                     y = start_y + 1;
1312                     h = LINES - start_y - 1;
1313                 }
1314             }
1315             x = start - in->term_first_shown - 2 + start_x;
1316             w = maxlen + 4;
1317             if (x + w > COLS)
1318                 x = COLS - w;
1319             if (x < 0)
1320                 x = 0;
1321             if (x + w > COLS)
1322                 w = COLS;
1323             input = in;
1324             min_end = end;
1325             query_height = h;
1326             query_width = w;
1327             query_dlg = create_dlg (TRUE, y, x, query_height, query_width,
1328                                     dialog_colors, query_callback, NULL,
1329                                     "[Completion]", NULL, DLG_COMPACT);
1330             query_list = listbox_new (1, 1, h - 2, w - 2, FALSE, NULL);
1331             add_widget (query_dlg, query_list);
1332             for (p = in->completions + 1; *p; p++)
1333                 listbox_add_item (query_list, LISTBOX_APPEND_AT_END, 0, *p, NULL);
1334             run_dlg (query_dlg);
1335             q = NULL;
1336             if (query_dlg->ret_value == B_ENTER)
1337             {
1338                 listbox_get_current (query_list, &q, NULL);
1339                 if (q)
1340                     insert_text (in, q, strlen (q));
1341             }
1342             if (q || end != min_end)
1343                 input_free_completions (in);
1344             i = query_dlg->ret_value;   /* B_USER if user wants to start over again */
1345             destroy_dlg (query_dlg);
1346             if (i == B_USER)
1347                 return 1;
1348         }
1349     }
1350     else
1351         tty_beep ();
1352     return 0;
1353 }
1354
1355 /* --------------------------------------------------------------------------------------------- */
1356 /*** public functions ****************************************************************************/
1357 /* --------------------------------------------------------------------------------------------- */
1358
1359 /* declared in lib/widget/input.h */
1360 void
1361 complete (WInput * in)
1362 {
1363     int engine_flags;
1364
1365     if (!str_is_valid_string (in->buffer))
1366         return;
1367
1368     if (in->completions != NULL)
1369         engine_flags = DO_QUERY;
1370     else
1371     {
1372         engine_flags = DO_INSERTION;
1373
1374         if (mc_global.widget.show_all_if_ambiguous)
1375             engine_flags |= DO_QUERY;
1376     }
1377
1378     while (complete_engine (in, engine_flags))
1379         ;
1380 }
1381
1382 /* --------------------------------------------------------------------------------------------- */