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-2019
   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     WDialog *h = DIALOG (w);
1023
1024     switch (msg)
1025     {
1026     case MSG_KEY:
1027         switch (parm)
1028         {
1029         case KEY_LEFT:
1030         case KEY_RIGHT:
1031             bl = 0;
1032             h->ret_value = 0;
1033             dlg_stop (h);
1034             return MSG_HANDLED;
1035
1036         case KEY_BACKSPACE:
1037             bl = 0;
1038             /* exit from completion list if input line is empty */
1039             if (end == 0)
1040             {
1041                 h->ret_value = 0;
1042                 dlg_stop (h);
1043             }
1044             /* Refill the list box and start again */
1045             else if (end == min_end)
1046             {
1047                 end = str_get_prev_char (&input->buffer[end]) - input->buffer;
1048                 input_handle_char (input, parm);
1049                 h->ret_value = B_USER;
1050                 dlg_stop (h);
1051             }
1052             else
1053             {
1054                 int new_end;
1055                 int i;
1056                 GList *e;
1057
1058                 new_end = str_get_prev_char (&input->buffer[end]) - input->buffer;
1059
1060                 for (i = 0, e = listbox_get_first_link (LISTBOX (h->current->data));
1061                      e != NULL; i++, e = g_list_next (e))
1062                 {
1063                     WLEntry *le = LENTRY (e->data);
1064
1065                     if (strncmp (input->buffer + start, le->text, new_end - start) == 0)
1066                     {
1067                         listbox_select_entry (LISTBOX (h->current->data), i);
1068                         end = new_end;
1069                         input_handle_char (input, parm);
1070                         widget_redraw (WIDGET (h->current->data));
1071                         break;
1072                     }
1073                 }
1074             }
1075             return MSG_HANDLED;
1076
1077         default:
1078             if (parm < 32 || parm > 255)
1079             {
1080                 bl = 0;
1081                 if (input_key_is_in_map (input, parm) != 2)
1082                     return MSG_NOT_HANDLED;
1083
1084                 if (end == min_end)
1085                     return MSG_HANDLED;
1086
1087                 /* This means we want to refill the list box and start again */
1088                 h->ret_value = B_USER;
1089                 dlg_stop (h);
1090             }
1091             else
1092             {
1093                 static char buff[MB_LEN_MAX] = "";
1094                 GList *e;
1095                 int i;
1096                 int need_redraw = 0;
1097                 int low = 4096;
1098                 char *last_text = NULL;
1099
1100                 buff[bl++] = (char) parm;
1101                 buff[bl] = '\0';
1102
1103                 switch (str_is_valid_char (buff, bl))
1104                 {
1105                 case -1:
1106                     bl = 0;
1107                     MC_FALLTHROUGH;
1108                 case -2:
1109                     return MSG_HANDLED;
1110                 default:
1111                     break;
1112                 }
1113
1114                 for (i = 0, e = listbox_get_first_link (LISTBOX (h->current->data));
1115                      e != NULL; i++, e = g_list_next (e))
1116                 {
1117                     WLEntry *le = LENTRY (e->data);
1118
1119                     if (strncmp (input->buffer + start, le->text, end - start) == 0
1120                         && strncmp (&le->text[end - start], buff, bl) == 0)
1121                     {
1122                         if (need_redraw == 0)
1123                         {
1124                             need_redraw = 1;
1125                             listbox_select_entry (LISTBOX (h->current->data), i);
1126                             last_text = le->text;
1127                         }
1128                         else
1129                         {
1130                             char *si, *sl;
1131                             int si_num = 0;
1132                             int sl_num = 0;
1133
1134                             /* count symbols between start and end */
1135                             for (si = le->text + start; si < le->text + end;
1136                                  str_next_char (&si), si_num++)
1137                                 ;
1138                             for (sl = last_text + start; sl < last_text + end;
1139                                  str_next_char (&sl), sl_num++)
1140                                 ;
1141
1142                             /* pointers to next symbols */
1143                             si = &le->text[str_offset_to_pos (le->text, ++si_num)];
1144                             sl = &last_text[str_offset_to_pos (last_text, ++sl_num)];
1145
1146                             while (si[0] != '\0' && sl[0] != '\0')
1147                             {
1148                                 char *nexti, *nextl;
1149
1150                                 nexti = str_get_next_char (si);
1151                                 nextl = str_get_next_char (sl);
1152
1153                                 if (nexti - si != nextl - sl || strncmp (si, sl, nexti - si) != 0)
1154                                     break;
1155
1156                                 si = nexti;
1157                                 sl = nextl;
1158
1159                                 si_num++;
1160                             }
1161
1162                             last_text = le->text;
1163
1164                             si = &last_text[str_offset_to_pos (last_text, si_num)];
1165                             if (low > si - last_text)
1166                                 low = si - last_text;
1167
1168                             need_redraw = 2;
1169                         }
1170                     }
1171                 }
1172
1173                 if (need_redraw == 2)
1174                 {
1175                     insert_text (input, last_text, low);
1176                     widget_redraw (WIDGET (h->current->data));
1177                 }
1178                 else if (need_redraw == 1)
1179                 {
1180                     h->ret_value = B_ENTER;
1181                     dlg_stop (h);
1182                 }
1183                 bl = 0;
1184             }
1185         }
1186         return MSG_HANDLED;
1187
1188     default:
1189         return dlg_default_callback (w, sender, msg, parm, data);
1190     }
1191 }
1192
1193 /* --------------------------------------------------------------------------------------------- */
1194
1195 /** Returns TRUE if the user would like to see us again */
1196 static gboolean
1197 complete_engine (WInput * in, int what_to_do)
1198 {
1199     if (in->completions != NULL && str_offset_to_pos (in->buffer, in->point) != end)
1200         input_free_completions (in);
1201
1202     if (in->completions == NULL)
1203         complete_engine_fill_completions (in);
1204
1205     if (in->completions == NULL)
1206         tty_beep ();
1207     else
1208     {
1209         if ((what_to_do & DO_INSERTION) != 0
1210             || ((what_to_do & DO_QUERY) != 0 && in->completions[1] == NULL))
1211         {
1212             char *lc_complete = in->completions[0];
1213
1214             if (!insert_text (in, lc_complete, strlen (lc_complete)) || in->completions[1] != NULL)
1215                 tty_beep ();
1216             else
1217                 input_free_completions (in);
1218         }
1219
1220         if ((what_to_do & DO_QUERY) != 0 && in->completions != NULL && in->completions[1] != NULL)
1221         {
1222             int maxlen = 0, count = 0, i;
1223             int x, y, w, h;
1224             int start_x, start_y;
1225             char **p, *q;
1226             WDialog *query_dlg;
1227             WListbox *query_list;
1228
1229             for (p = in->completions + 1; *p != NULL; count++, p++)
1230             {
1231                 i = str_term_width1 (*p);
1232                 if (i > maxlen)
1233                     maxlen = i;
1234             }
1235
1236             start_x = WIDGET (in)->x;
1237             start_y = WIDGET (in)->y;
1238             if (start_y - 2 >= count)
1239             {
1240                 y = start_y - 2 - count;
1241                 h = 2 + count;
1242             }
1243             else if (start_y >= LINES - start_y - 1)
1244             {
1245                 y = 0;
1246                 h = start_y;
1247             }
1248             else
1249             {
1250                 y = start_y + 1;
1251                 h = LINES - start_y - 1;
1252             }
1253             x = start - in->term_first_shown - 2 + start_x;
1254             w = maxlen + 4;
1255             if (x + w > COLS)
1256                 x = COLS - w;
1257             if (x < 0)
1258                 x = 0;
1259             if (x + w > COLS)
1260                 w = COLS;
1261
1262             input = in;
1263             min_end = end;
1264             query_height = h;
1265             query_width = w;
1266
1267             query_dlg = dlg_create (TRUE, y, x, query_height, query_width, WPOS_KEEP_DEFAULT, TRUE,
1268                                     dialog_colors, query_callback, NULL, "[Completion]", NULL);
1269             query_list = listbox_new (1, 1, h - 2, w - 2, FALSE, NULL);
1270             add_widget (query_dlg, query_list);
1271
1272             for (p = in->completions + 1; *p != NULL; p++)
1273                 listbox_add_item (query_list, LISTBOX_APPEND_AT_END, 0, *p, NULL, FALSE);
1274
1275             i = dlg_run (query_dlg);
1276             q = NULL;
1277             if (i == B_ENTER)
1278             {
1279                 listbox_get_current (query_list, &q, NULL);
1280                 if (q != NULL)
1281                     insert_text (in, q, strlen (q));
1282             }
1283             if (q != NULL || end != min_end)
1284                 input_free_completions (in);
1285             dlg_destroy (query_dlg);
1286
1287             /* B_USER if user wants to start over again */
1288             return (i == B_USER);
1289         }
1290     }
1291
1292     return FALSE;
1293 }
1294
1295 /* --------------------------------------------------------------------------------------------- */
1296 /*** public functions ****************************************************************************/
1297 /* --------------------------------------------------------------------------------------------- */
1298
1299 /** Returns an array of matches, or NULL if none. */
1300 char **
1301 try_complete (char *text, int *lc_start, int *lc_end, input_complete_t flags)
1302 {
1303     try_complete_automation_state_t state;
1304     char **matches = NULL;
1305
1306     memset (&state, 0, sizeof (state));
1307     state.flags = flags;
1308
1309     SHOW_C_CTX ("try_complete");
1310     state.word = g_strndup (text + *lc_start, *lc_end - *lc_start);
1311
1312     state.is_cd = check_is_cd (text, *lc_start, state.flags);
1313
1314     /* Determine if this could be a command word. It is if it appears at
1315        the start of the line (ignoring preceding whitespace), or if it
1316        appears after a character that separates commands. And we have to
1317        be in a INPUT_COMPLETE_COMMANDS flagged Input line. */
1318     if (!state.is_cd && (flags & INPUT_COMPLETE_COMMANDS) != 0)
1319         try_complete_commands_prepare (&state, text, lc_start);
1320
1321     try_complete_find_start_sign (&state);
1322
1323     /* Command substitution? */
1324     if (state.p > state.q && state.p > state.r)
1325     {
1326         SHOW_C_CTX ("try_complete:cmd_backq_subst");
1327         matches = completion_matches (str_cget_next_char (state.p),
1328                                       command_completion_function,
1329                                       state.flags & (~INPUT_COMPLETE_FILENAMES));
1330         if (matches != NULL)
1331             *lc_start += str_get_next_char (state.p) - state.word;
1332     }
1333
1334     /* Variable name? */
1335     else if (state.q > state.p && state.q > state.r)
1336     {
1337         SHOW_C_CTX ("try_complete:var_subst");
1338         matches = completion_matches (state.q, variable_completion_function, state.flags);
1339         if (matches != NULL)
1340             *lc_start += state.q - state.word;
1341     }
1342
1343     /* Starts with '@', then look through the known hostnames for
1344        completion first. */
1345     else if (state.r > state.p && state.r > state.q)
1346     {
1347         SHOW_C_CTX ("try_complete:host_subst");
1348         matches = completion_matches (state.r, hostname_completion_function, state.flags);
1349         if (matches != NULL)
1350             *lc_start += state.r - state.word;
1351     }
1352
1353     /* Starts with '~' and there is no slash in the word, then
1354        try completing this word as a username. */
1355     if (matches == NULL && *state.word == '~' && (state.flags & INPUT_COMPLETE_USERNAMES) != 0
1356         && strchr (state.word, PATH_SEP) == NULL)
1357     {
1358         SHOW_C_CTX ("try_complete:user_subst");
1359         matches = completion_matches (state.word, username_completion_function, state.flags);
1360     }
1361
1362     /* If this word is in a command position, then
1363        complete over possible command names, including aliases, functions,
1364        and command names. */
1365     if (matches == NULL)
1366         matches = try_complete_all_possible (&state, text, lc_start);
1367
1368     /* And finally if nothing found, try complete directory name */
1369     if (matches == NULL)
1370     {
1371         state.in_command_position = 0;
1372         matches = try_complete_all_possible (&state, text, lc_start);
1373     }
1374
1375     g_free (state.word);
1376
1377     if (matches != NULL &&
1378         (flags & (INPUT_COMPLETE_FILENAMES | INPUT_COMPLETE_SHELL_ESC)) !=
1379         (INPUT_COMPLETE_FILENAMES | INPUT_COMPLETE_SHELL_ESC))
1380     {
1381         /* FIXME: HACK? INPUT_COMPLETE_SHELL_ESC is used only in command line. */
1382         char **m;
1383
1384         for (m = matches; *m != NULL; m++)
1385         {
1386             char *p;
1387
1388             p = *m;
1389             *m = strutils_shell_escape (*m);
1390             g_free (p);
1391         }
1392     }
1393
1394     return matches;
1395 }
1396
1397 /* --------------------------------------------------------------------------------------------- */
1398
1399 void
1400 complete_engine_fill_completions (WInput * in)
1401 {
1402     char *s;
1403     const char *word_separators;
1404
1405     word_separators = (in->completion_flags & INPUT_COMPLETE_SHELL_ESC) ? " \t;|<>" : "\t;|<>";
1406
1407     end = str_offset_to_pos (in->buffer, in->point);
1408
1409     s = in->buffer;
1410     if (in->point != 0)
1411     {
1412         /* get symbol before in->point */
1413         size_t i;
1414
1415         for (i = in->point - 1; i > 0; i--)
1416             str_next_char (&s);
1417     }
1418
1419     for (; s >= in->buffer; str_prev_char (&s))
1420     {
1421         start = s - in->buffer;
1422         if (strchr (word_separators, *s) != NULL && !strutils_is_char_escaped (in->buffer, s))
1423             break;
1424     }
1425
1426     if (start < end)
1427     {
1428         str_next_char (&s);
1429         start = s - in->buffer;
1430     }
1431
1432     in->completions = try_complete (in->buffer, &start, &end, in->completion_flags);
1433 }
1434
1435 /* --------------------------------------------------------------------------------------------- */
1436
1437 /* declared in lib/widget/input.h */
1438 void
1439 complete (WInput * in)
1440 {
1441     int engine_flags;
1442
1443     if (!str_is_valid_string (in->buffer))
1444         return;
1445
1446     if (in->completions != NULL)
1447         engine_flags = DO_QUERY;
1448     else
1449     {
1450         engine_flags = DO_INSERTION;
1451
1452         if (mc_global.widget.show_all_if_ambiguous)
1453             engine_flags |= DO_QUERY;
1454     }
1455
1456     while (complete_engine (in, engine_flags))
1457         ;
1458 }
1459
1460 /* --------------------------------------------------------------------------------------------- */