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