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