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