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