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