lib/widget/input_complete.c

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