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 = hosts_p - hosts;
 456
 457                     hosts =
 458                         g_realloc ((void *) hosts, ((hosts_alloclen += 30) + 1) * sizeof (char *));
 459                     hosts_p = hosts + j;
 460                 }
 461                 for (host_p = hosts; host_p < hosts_p; host_p++)
 462                     if (!strcmp (name, *host_p))
 463                         break;  /* We do not want any duplicates */
 464                 if (host_p == hosts_p)
 465                 {
 466                     *(hosts_p++) = name;
 467                     *hosts_p = NULL;
 468                 }
 469                 else
 470                     g_free (name);
 471             }
 472         }
 473     }
 474     fclose (file);
 475 }
 476
 477 /* --------------------------------------------------------------------------------------------- */
 478
 479 static char *
 480 hostname_completion_function (const char *text, int state, input_complete_t flags)
 481 {
 482     static char **host_p;
 483     static unsigned int textstart;
 484     static size_t textlen;
 485
 486     (void) flags;
 487     SHOW_C_CTX ("hostname_completion_function");
 488
 489     if (!state)
 490     {                           /* Initialization stuff */
 491         const char *p;
 492
 493         if (hosts != NULL)
 494         {
 495             for (host_p = hosts; *host_p; host_p++)
 496                 g_free (*host_p);
 497             g_free (hosts);
 498         }
 499         hosts = g_new (char *, (hosts_alloclen = 30) + 1);
 500         *hosts = NULL;
 501         hosts_p = hosts;
 502         fetch_hosts ((p = getenv ("HOSTFILE")) ? p : "/etc/hosts");
 503         host_p = hosts;
 504         textstart = (*text == '@') ? 1 : 0;
 505         textlen = strlen (text + textstart);
 506     }
 507
 508     while (*host_p)
 509     {
 510         if (!textlen)
 511             break;              /* Match all of them */
 512         else if (!strncmp (text + textstart, *host_p, textlen))
 513             break;
 514         host_p++;
 515     }
 516
 517     if (!*host_p)
 518     {
 519         for (host_p = hosts; *host_p; host_p++)
 520             g_free (*host_p);
 521         g_free (hosts);
 522         hosts = NULL;
 523         return NULL;
 524     }
 525
 526     {
 527         GString *temp;
 528
 529         temp = g_string_sized_new (8);
 530
 531         if (textstart != 0)
 532             g_string_append_c (temp, '@');
 533         g_string_append (temp, *host_p);
 534         host_p++;
 535
 536         return g_string_free (temp, FALSE);
 537     }
 538 }
 539
 540 /* --------------------------------------------------------------------------------------------- */
 541 /**
 542  * This is the function to call when the word to complete is in a position
 543  * where a command word can be found. It looks around $PATH, looking for
 544  * commands that match. It also scans aliases, function names, and the
 545  * table of shell built-ins.
 546  */
 547
 548 static char *
 549 command_completion_function (const char *_text, int state, input_complete_t flags)
 550 {
 551     char *text;
 552     static const char *path_end;
 553     static gboolean isabsolute;
 554     static int phase;
 555     static size_t text_len;
 556     static const char *const *words;
 557     static char *path;
 558     static char *cur_path;
 559     static char *cur_word;
 560     static int init_state;
 561     static const char *const bash_reserved[] = {
 562         "if", "then", "else", "elif", "fi", "case", "esac", "for",
 563         "select", "while", "until", "do", "done", "in", "function", 0
 564     };
 565     static const char *const bash_builtins[] = {
 566         "alias", "bg", "bind", "break", "builtin", "cd", "command",
 567         "continue", "declare", "dirs", "echo", "enable", "eval",
 568         "exec", "exit", "export", "fc", "fg", "getopts", "hash",
 569         "help", "history", "jobs", "kill", "let", "local", "logout",
 570         "popd", "pushd", "pwd", "read", "readonly", "return", "set",
 571         "shift", "source", "suspend", "test", "times", "trap", "type",
 572         "typeset", "ulimit", "umask", "unalias", "unset", "wait", 0
 573     };
 574     char *p, *found;
 575
 576     SHOW_C_CTX ("command_completion_function");
 577
 578     if (!(flags & INPUT_COMPLETE_COMMANDS))
 579         return 0;
 580
 581     text = strutils_shell_unescape (_text);
 582     flags &= ~INPUT_COMPLETE_SHELL_ESC;
 583
 584     if (state == 0)
 585     {                           /* Initialize us a little bit */
 586         isabsolute = strchr (text, PATH_SEP) != NULL;
 587         if (!isabsolute)
 588         {
 589             words = bash_reserved;
 590             phase = 0;
 591             text_len = strlen (text);
 592
 593             if (path == NULL)
 594             {
 595                 path = g_strdup (getenv ("PATH"));
 596                 if (path != NULL)
 597                 {
 598                     p = path;
 599                     path_end = strchr (p, '\0');
 600                     while ((p = strchr (p, PATH_ENV_SEP)) != NULL)
 601                     {
 602                         *p++ = '\0';
 603                     }
 604                 }
 605             }
 606         }
 607     }
 608
 609     if (isabsolute)
 610     {
 611         p = filename_completion_function (text, state, flags);
 612
 613         if (p != NULL)
 614         {
 615             char *temp_p = p;
 616             p = strutils_shell_escape (p);
 617             g_free (temp_p);
 618         }
 619
 620         g_free (text);
 621         return p;
 622     }
 623
 624     found = NULL;
 625     switch (phase)
 626     {
 627     case 0:                    /* Reserved words */
 628         while (*words)
 629         {
 630             if (strncmp (*words, text, text_len) == 0)
 631             {
 632                 g_free (text);
 633                 return g_strdup (*(words++));
 634             }
 635             words++;
 636         }
 637         phase++;
 638         words = bash_builtins;
 639     case 1:                    /* Builtin commands */
 640         while (*words)
 641         {
 642             if (strncmp (*words, text, text_len) == 0)
 643             {
 644                 g_free (text);
 645                 return g_strdup (*(words++));
 646             }
 647             words++;
 648         }
 649         phase++;
 650         if (!path)
 651             break;
 652         cur_path = path;
 653         cur_word = NULL;
 654     case 2:                    /* And looking through the $PATH */
 655         while (!found)
 656         {
 657             if (!cur_word)
 658             {
 659                 char *expanded;
 660
 661                 if (cur_path >= path_end)
 662                     break;
 663                 expanded = tilde_expand (*cur_path ? cur_path : ".");
 664                 cur_word = mc_build_filename (expanded, text, NULL);
 665                 g_free (expanded);
 666                 canonicalize_pathname (cur_word);
 667                 cur_path = strchr (cur_path, 0) + 1;
 668                 init_state = state;
 669             }
 670             found = filename_completion_function (cur_word, state - init_state, flags);
 671             if (!found)
 672             {
 673                 g_free (cur_word);
 674                 cur_word = NULL;
 675             }
 676         }
 677     }
 678
 679     if (found == NULL)
 680     {
 681         g_free (path);
 682         path = NULL;
 683     }
 684     else
 685     {
 686         p = strrchr (found, PATH_SEP);
 687         if (p != NULL)
 688         {
 689             char *tmp = found;
 690             found = strutils_shell_escape (p + 1);
 691             g_free (tmp);
 692         }
 693     }
 694
 695     g_free (text);
 696     return found;
 697 }
 698
 699 /* --------------------------------------------------------------------------------------------- */
 700
 701 static int
 702 match_compare (const void *a, const void *b)
 703 {
 704     return strcmp (*(char **) a, *(char **) b);
 705 }
 706
 707 /* --------------------------------------------------------------------------------------------- */
 708 /** Returns an array of char * matches with the longest common denominator
 709    in the 1st entry. Then a NULL terminated list of different possible
 710    completions follows.
 711    You have to supply your own CompletionFunction with the word you
 712    want to complete as the first argument and an count of previous matches
 713    as the second.
 714    In case no matches were found we return NULL. */
 715
 716 static char **
 717 completion_matches (const char *text, CompletionFunction entry_function, input_complete_t flags)
 718 {
 719     /* Number of slots in match_list. */
 720     int match_list_size;
 721
 722     /* The list of matches. */
 723     char **match_list = g_new (char *, (match_list_size = 30) + 1);
 724
 725     /* Number of matches actually found. */
 726     int matches = 0;
 727
 728     /* Temporary string binder. */
 729     char *string;
 730
 731     match_list[1] = NULL;
 732
 733     while ((string = (*entry_function) (text, matches, flags)) != NULL)
 734     {
 735         if (matches + 1 == match_list_size)
 736             match_list =
 737                 (char **) g_realloc (match_list, ((match_list_size += 30) + 1) * sizeof (char *));
 738         match_list[++matches] = string;
 739         match_list[matches + 1] = NULL;
 740     }
 741
 742     /* If there were any matches, then look through them finding out the
 743        lowest common denominator.  That then becomes match_list[0]. */
 744     if (matches)
 745     {
 746         register int i = 1;
 747         int low = 4096;         /* Count of max-matched characters. */
 748
 749         /* If only one match, just use that. */
 750         if (matches == 1)
 751         {
 752             match_list[0] = match_list[1];
 753             match_list[1] = NULL;
 754         }
 755         else
 756         {
 757             int j;
 758
 759             qsort (match_list + 1, matches, sizeof (char *), match_compare);
 760
 761             /* And compare each member of the list with
 762                the next, finding out where they stop matching.
 763                If we find two equal strings, we have to put one away... */
 764
 765             j = i + 1;
 766             while (j < matches + 1)
 767             {
 768                 char *si, *sj;
 769                 char *ni, *nj;
 770
 771                 for (si = match_list[i], sj = match_list[j]; si[0] && sj[0];)
 772                 {
 773
 774                     ni = str_get_next_char (si);
 775                     nj = str_get_next_char (sj);
 776
 777                     if (ni - si != nj - sj)
 778                         break;
 779                     if (strncmp (si, sj, ni - si) != 0)
 780                         break;
 781
 782                     si = ni;
 783                     sj = nj;
 784                 }
 785
 786                 if (si[0] == '\0' && sj[0] == '\0')
 787                 {               /* Two equal strings */
 788                     g_free (match_list[j]);
 789                     j++;
 790                     if (j > matches)
 791                         break;
 792                     continue;   /* Look for a run of equal strings */
 793                 }
 794                 else if (low > si - match_list[i])
 795                     low = si - match_list[i];
 796                 if (i + 1 != j) /* So there's some gap */
 797                     match_list[i + 1] = match_list[j];
 798                 i++;
 799                 j++;
 800             }
 801             matches = i;
 802             match_list[matches + 1] = NULL;
 803             match_list[0] = g_strndup (match_list[1], low);
 804         }
 805     }
 806     else
 807     {                           /* There were no matches. */
 808         g_free (match_list);
 809         match_list = NULL;
 810     }
 811     return match_list;
 812 }
 813
 814 /* --------------------------------------------------------------------------------------------- */
 815 /** Check if directory completion is needed */
 816 static gboolean
 817 check_is_cd (const char *text, int lc_start, input_complete_t flags)
 818 {
 819     char *p, *q;
 820
 821     SHOW_C_CTX ("check_is_cd");
 822
 823     if ((flags & INPUT_COMPLETE_CD) == 0)
 824         return FALSE;
 825
 826     /* Skip initial spaces */
 827     p = (char *) text;
 828     q = (char *) text + lc_start;
 829     while (p < q && p[0] != '\0' && str_isspace (p))
 830         str_next_char (&p);
 831
 832     /* Check if the command is "cd" and the cursor is after it */
 833     return (p[0] == 'c' && p[1] == 'd' && str_isspace (p + 2) && p + 2 < q);
 834 }
 835
 836 /* --------------------------------------------------------------------------------------------- */
 837
 838 static void
 839 try_complete_commands_prepare (try_complete_automation_state_t * state, char *text, int *lc_start)
 840 {
 841     const char *command_separator_chars = ";|&{(`";
 842     char *ti;
 843
 844     if (*lc_start == 0)
 845         ti = text;
 846     else
 847     {
 848         ti = str_get_prev_char (&text[*lc_start]);
 849         while (ti > text && (ti[0] == ' ' || ti[0] == '\t'))
 850             str_prev_char (&ti);
 851     }
 852
 853     if (ti == text)
 854         state->in_command_position++;
 855     else if (strchr (command_separator_chars, ti[0]) != NULL)
 856     {
 857         int this_char, prev_char;
 858
 859         state->in_command_position++;
 860
 861         if (ti != text)
 862         {
 863             /* Handle the two character tokens `>&', `<&', and `>|'.
 864                We are not in a command position after one of these. */
 865             this_char = ti[0];
 866             prev_char = str_get_prev_char (ti)[0];
 867
 868             /* Quoted */
 869             if ((this_char == '&' && (prev_char == '<' || prev_char == '>'))
 870                 || (this_char == '|' && prev_char == '>') || (ti != text
 871                                                               && str_get_prev_char (ti)[0] == '\\'))
 872                 state->in_command_position = 0;
 873         }
 874     }
 875 }
 876
 877 /* --------------------------------------------------------------------------------------------- */
 878
 879 static void
 880 try_complete_find_start_sign (try_complete_automation_state_t * state)
 881 {
 882     if (state->flags & INPUT_COMPLETE_COMMANDS)
 883         state->p = strrchr (state->word, '`');
 884     if (state->flags & (INPUT_COMPLETE_COMMANDS | INPUT_COMPLETE_VARIABLES))
 885     {
 886         state->q = strrchr (state->word, '$');
 887
 888         /* don't substitute variable in \$ case */
 889         if (strutils_is_char_escaped (state->word, state->q))
 890         {
 891             size_t qlen;
 892
 893             qlen = strlen (state->q);
 894             /* drop '\\' */
 895             memmove (state->q - 1, state->q, qlen + 1);
 896             /* adjust flags */
 897             state->flags &= ~INPUT_COMPLETE_VARIABLES;
 898             state->q = NULL;
 899         }
 900     }
 901     if (state->flags & INPUT_COMPLETE_HOSTNAMES)
 902         state->r = strrchr (state->word, '@');
 903     if (state->q && state->q[1] == '(' && (state->flags & INPUT_COMPLETE_COMMANDS))
 904     {
 905         if (state->q > state->p)
 906             state->p = str_get_next_char (state->q);
 907         state->q = NULL;
 908     }
 909 }
 910
 911 /* --------------------------------------------------------------------------------------------- */
 912
 913 static char **
 914 try_complete_all_possible (try_complete_automation_state_t * state, char *text, int *lc_start)
 915 {
 916     char **matches = NULL;
 917
 918     if (state->in_command_position != 0)
 919     {
 920         SHOW_C_CTX ("try_complete:cmd_subst");
 921         matches =
 922             completion_matches (state->word, command_completion_function,
 923                                 state->flags & (~INPUT_COMPLETE_FILENAMES));
 924     }
 925     else if ((state->flags & INPUT_COMPLETE_FILENAMES) != 0)
 926     {
 927         if (state->is_cd)
 928             state->flags &= ~(INPUT_COMPLETE_FILENAMES | INPUT_COMPLETE_COMMANDS);
 929         SHOW_C_CTX ("try_complete:filename_subst_1");
 930         matches = completion_matches (state->word, filename_completion_function, state->flags);
 931
 932         if (matches == NULL && state->is_cd && *state->word != PATH_SEP && *state->word != '~')
 933         {
 934             state->q = text + *lc_start;
 935             for (state->p = text;
 936                  *state->p && state->p < state->q && (*state->p == ' ' || *state->p == '\t');
 937                  str_next_char (&state->p))
 938                 ;
 939             if (!strncmp (state->p, "cd", 2))
 940                 for (state->p += 2;
 941                      *state->p && state->p < state->q && (*state->p == ' ' || *state->p == '\t');
 942                      str_next_char (&state->p))
 943                     ;
 944             if (state->p == state->q)
 945             {
 946                 char *const cdpath_ref = g_strdup (getenv ("CDPATH"));
 947                 char *cdpath = cdpath_ref;
 948                 char c, *s;
 949
 950                 if (cdpath == NULL)
 951                     c = 0;
 952                 else
 953                     c = ':';
 954                 while (!matches && c == ':')
 955                 {
 956                     s = strchr (cdpath, ':');
 957                     if (s == NULL)
 958                         s = strchr (cdpath, 0);
 959                     c = *s;
 960                     *s = 0;
 961                     if (*cdpath)
 962                     {
 963                         state->r = mc_build_filename (cdpath, state->word, NULL);
 964                         SHOW_C_CTX ("try_complete:filename_subst_2");
 965                         matches =
 966                             completion_matches (state->r, filename_completion_function,
 967                                                 state->flags);
 968                         g_free (state->r);
 969                     }
 970                     *s = c;
 971                     cdpath = str_get_next_char (s);
 972                 }
 973                 g_free (cdpath_ref);
 974             }
 975         }
 976     }
 977     return matches;
 978 }
 979
 980 /* --------------------------------------------------------------------------------------------- */
 981
 982 static int
 983 insert_text (WInput * in, char *text, ssize_t size)
 984 {
 985     int buff_len = str_length (in->buffer);
 986
 987     size = min (size, (ssize_t) strlen (text)) + start - end;
 988     if (strlen (in->buffer) + size >= (size_t) in->current_max_size)
 989     {
 990         /* Expand the buffer */
 991         char *narea = g_try_realloc (in->buffer, in->current_max_size + size + in->field_width);
 992         if (narea != NULL)
 993         {
 994             in->buffer = narea;
 995             in->current_max_size += size + in->field_width;
 996         }
 997     }
 998     if (strlen (in->buffer) + 1 < (size_t) in->current_max_size)
 999     {
1000         if (size > 0)
1001         {
1002             int i = strlen (&in->buffer[end]);
1003             for (; i >= 0; i--)
1004                 in->buffer[end + size + i] = in->buffer[end + i];
1005         }
1006         else if (size < 0)
1007         {
1008             char *p = in->buffer + end + size, *q = in->buffer + end;
1009             while (*q)
1010                 *(p++) = *(q++);
1011             *p = 0;
1012         }
1013         memcpy (in->buffer + start, text, size - start + end);
1014         in->point += str_length (in->buffer) - buff_len;
1015         input_update (in, TRUE);
1016         end += size;
1017     }
1018     return size != 0;
1019 }
1020
1021 /* --------------------------------------------------------------------------------------------- */
1022
1023 static cb_ret_t
1024 query_callback (Widget * w, Widget * sender, widget_msg_t msg, int parm, void *data)
1025 {
1026     static char buff[MB_LEN_MAX] = "";
1027     static int bl = 0;
1028
1029     WDialog *h = DIALOG (w);
1030
1031     switch (msg)
1032     {
1033     case MSG_KEY:
1034         switch (parm)
1035         {
1036         case KEY_LEFT:
1037         case KEY_RIGHT:
1038             bl = 0;
1039             h->ret_value = 0;
1040             dlg_stop (h);
1041             return MSG_HANDLED;
1042
1043         case KEY_BACKSPACE:
1044             bl = 0;
1045             /* exit from completion list if input line is empty */
1046             if (end == 0)
1047             {
1048                 h->ret_value = 0;
1049                 dlg_stop (h);
1050             }
1051             /* Refill the list box and start again */
1052             else if (end == min_end)
1053             {
1054                 end = str_get_prev_char (&input->buffer[end]) - input->buffer;
1055                 input_handle_char (input, parm);
1056                 h->ret_value = B_USER;
1057                 dlg_stop (h);
1058                 return MSG_HANDLED;
1059             }
1060             else
1061             {
1062                 int new_end;
1063                 int i;
1064                 GList *e;
1065
1066                 new_end = str_get_prev_char (&input->buffer[end]) - input->buffer;
1067
1068                 for (i = 0, e = LISTBOX (h->current->data)->list;
1069                      e != NULL; i++, e = g_list_next (e))
1070                 {
1071                     WLEntry *le = LENTRY (e->data);
1072
1073                     if (strncmp (input->buffer + start, le->text, new_end - start) == 0)
1074                     {
1075                         listbox_select_entry (LISTBOX (h->current->data), i);
1076                         end = new_end;
1077                         input_handle_char (input, parm);
1078                         send_message (h->current->data, NULL, MSG_DRAW, 0, NULL);
1079                         break;
1080                     }
1081                 }
1082             }
1083             return MSG_HANDLED;
1084
1085         default:
1086             if (parm < 32 || parm > 255)
1087             {
1088                 bl = 0;
1089                 if (input_key_is_in_map (input, parm) != 2)
1090                     return MSG_NOT_HANDLED;
1091
1092                 if (end == min_end)
1093                     return MSG_HANDLED;
1094
1095                 /* This means we want to refill the list box and start again */
1096                 h->ret_value = B_USER;
1097                 dlg_stop (h);
1098                 return MSG_HANDLED;
1099             }
1100             else
1101             {
1102                 GList *e;
1103                 int i;
1104                 int need_redraw = 0;
1105                 int low = 4096;
1106                 char *last_text = NULL;
1107
1108                 buff[bl++] = (char) parm;
1109                 buff[bl] = '\0';
1110                 switch (str_is_valid_char (buff, bl))
1111                 {
1112                 case -1:
1113                     bl = 0;
1114                     /* fallthrough */
1115                 case -2:
1116                     return MSG_HANDLED;
1117                 }
1118
1119                 for (i = 0, e = LISTBOX (h->current->data)->list;
1120                      e != NULL; i++, e = g_list_next (e))
1121                 {
1122                     WLEntry *le = LENTRY (e->data);
1123
1124                     if (strncmp (input->buffer + start, le->text, end - start) == 0
1125                         && strncmp (&le->text[end - start], buff, bl) == 0)
1126                     {
1127                         if (need_redraw == 0)
1128                         {
1129                             need_redraw = 1;
1130                             listbox_select_entry (LISTBOX (h->current->data), i);
1131                             last_text = le->text;
1132                         }
1133                         else
1134                         {
1135                             char *si, *sl;
1136                             int si_num = 0;
1137                             int sl_num = 0;
1138
1139                             /* count symbols between start and end */
1140                             for (si = le->text + start; si < le->text + end;
1141                                  str_next_char (&si), si_num++)
1142                                 ;
1143                             for (sl = last_text + start; sl < last_text + end;
1144                                  str_next_char (&sl), sl_num++)
1145                                 ;
1146
1147                             /* pointers to next symbols */
1148                             si = &le->text[str_offset_to_pos (le->text, ++si_num)];
1149                             sl = &last_text[str_offset_to_pos (last_text, ++sl_num)];
1150
1151                             while (si[0] != '\0' && sl[0] != '\0')
1152                             {
1153                                 char *nexti, *nextl;
1154
1155                                 nexti = str_get_next_char (si);
1156                                 nextl = str_get_next_char (sl);
1157
1158                                 if (nexti - si != nextl - sl || strncmp (si, sl, nexti - si) != 0)
1159                                     break;
1160
1161                                 si = nexti;
1162                                 sl = nextl;
1163
1164                                 si_num++;
1165                             }
1166
1167                             last_text = le->text;
1168
1169                             si = &last_text[str_offset_to_pos (last_text, si_num)];
1170                             if (low > si - last_text)
1171                                 low = si - last_text;
1172
1173                             need_redraw = 2;
1174                         }
1175                     }
1176                 }
1177
1178                 if (need_redraw == 2)
1179                 {
1180                     insert_text (input, last_text, low);
1181                     send_message (h->current->data, NULL, MSG_DRAW, 0, NULL);
1182                 }
1183                 else if (need_redraw == 1)
1184                 {
1185                     h->ret_value = B_ENTER;
1186                     dlg_stop (h);
1187                 }
1188                 bl = 0;
1189             }
1190             return MSG_HANDLED;
1191         }
1192         break;
1193
1194     default:
1195         return dlg_default_callback (w, sender, msg, parm, data);
1196     }
1197 }
1198
1199 /* --------------------------------------------------------------------------------------------- */
1200
1201 /** Returns 1 if the user would like to see us again */
1202 static int
1203 complete_engine (WInput * in, int what_to_do)
1204 {
1205     if (in->completions != NULL && str_offset_to_pos (in->buffer, in->point) != end)
1206         input_free_completions (in);
1207
1208     if (in->completions == NULL)
1209         complete_engine_fill_completions (in);
1210
1211     if (in->completions != NULL)
1212     {
1213         if (what_to_do & DO_INSERTION || ((what_to_do & DO_QUERY) && !in->completions[1]))
1214         {
1215             char *lc_complete = in->completions[0];
1216             if (insert_text (in, lc_complete, strlen (lc_complete)))
1217             {
1218                 if (in->completions[1])
1219                     tty_beep ();
1220                 else
1221                     input_free_completions (in);
1222             }
1223             else
1224                 tty_beep ();
1225         }
1226         if ((what_to_do & DO_QUERY) && in->completions && in->completions[1])
1227         {
1228             int maxlen = 0, i, count = 0;
1229             int x, y, w, h;
1230             int start_x, start_y;
1231             char **p, *q;
1232             WDialog *query_dlg;
1233             WListbox *query_list;
1234
1235             for (p = in->completions + 1; *p != NULL; count++, p++)
1236             {
1237                 i = str_term_width1 (*p);
1238                 if (i > maxlen)
1239                     maxlen = i;
1240             }
1241             start_x = WIDGET (in)->x;
1242             start_y = WIDGET (in)->y;
1243             if (start_y - 2 >= count)
1244             {
1245                 y = start_y - 2 - count;
1246                 h = 2 + count;
1247             }
1248             else
1249             {
1250                 if (start_y >= LINES - start_y - 1)
1251                 {
1252                     y = 0;
1253                     h = start_y;
1254                 }
1255                 else
1256                 {
1257                     y = start_y + 1;
1258                     h = LINES - start_y - 1;
1259                 }
1260             }
1261             x = start - in->term_first_shown - 2 + start_x;
1262             w = maxlen + 4;
1263             if (x + w > COLS)
1264                 x = COLS - w;
1265             if (x < 0)
1266                 x = 0;
1267             if (x + w > COLS)
1268                 w = COLS;
1269             input = in;
1270             min_end = end;
1271             query_height = h;
1272             query_width = w;
1273             query_dlg = create_dlg (TRUE, y, x, query_height, query_width,
1274                                     dialog_colors, query_callback, NULL,
1275                                     "[Completion]", NULL, DLG_COMPACT);
1276             query_list = listbox_new (1, 1, h - 2, w - 2, FALSE, NULL);
1277             add_widget (query_dlg, query_list);
1278             for (p = in->completions + 1; *p; p++)
1279                 listbox_add_item (query_list, LISTBOX_APPEND_AT_END, 0, *p, NULL);
1280             run_dlg (query_dlg);
1281             q = NULL;
1282             if (query_dlg->ret_value == B_ENTER)
1283             {
1284                 listbox_get_current (query_list, &q, NULL);
1285                 if (q)
1286                     insert_text (in, q, strlen (q));
1287             }
1288             if (q || end != min_end)
1289                 input_free_completions (in);
1290             i = query_dlg->ret_value;   /* B_USER if user wants to start over again */
1291             destroy_dlg (query_dlg);
1292             if (i == B_USER)
1293                 return 1;
1294         }
1295     }
1296     else
1297         tty_beep ();
1298     return 0;
1299 }
1300
1301 /* --------------------------------------------------------------------------------------------- */
1302 /*** public functions ****************************************************************************/
1303 /* --------------------------------------------------------------------------------------------- */
1304
1305 /** Returns an array of matches, or NULL if none. */
1306 char **
1307 try_complete (char *text, int *lc_start, int *lc_end, input_complete_t flags)
1308 {
1309     try_complete_automation_state_t state;
1310     char **matches = NULL;
1311
1312     memset (&state, 0, sizeof (try_complete_automation_state_t));
1313     state.flags = flags;
1314
1315     SHOW_C_CTX ("try_complete");
1316     state.word = g_strndup (text + *lc_start, *lc_end - *lc_start);
1317
1318     state.is_cd = check_is_cd (text, *lc_start, state.flags);
1319
1320     /* Determine if this could be a command word. It is if it appears at
1321        the start of the line (ignoring preceding whitespace), or if it
1322        appears after a character that separates commands. And we have to
1323        be in a INPUT_COMPLETE_COMMANDS flagged Input line. */
1324     if (!state.is_cd && (flags & INPUT_COMPLETE_COMMANDS))
1325         try_complete_commands_prepare (&state, text, lc_start);
1326
1327     try_complete_find_start_sign (&state);
1328
1329     /* Command substitution? */
1330     if (state.p > state.q && state.p > state.r)
1331     {
1332         SHOW_C_CTX ("try_complete:cmd_backq_subst");
1333         matches = completion_matches (str_cget_next_char (state.p),
1334                                       command_completion_function,
1335                                       state.flags & (~INPUT_COMPLETE_FILENAMES));
1336         if (matches)
1337             *lc_start += str_get_next_char (state.p) - state.word;
1338     }
1339
1340     /* Variable name? */
1341     else if (state.q > state.p && state.q > state.r)
1342     {
1343         SHOW_C_CTX ("try_complete:var_subst");
1344         matches = completion_matches (state.q, variable_completion_function, state.flags);
1345         if (matches)
1346             *lc_start += state.q - state.word;
1347     }
1348
1349     /* Starts with '@', then look through the known hostnames for
1350        completion first. */
1351     else if (state.r > state.p && state.r > state.q)
1352     {
1353         SHOW_C_CTX ("try_complete:host_subst");
1354         matches = completion_matches (state.r, hostname_completion_function, state.flags);
1355         if (matches)
1356             *lc_start += state.r - state.word;
1357     }
1358
1359     /* Starts with `~' and there is no slash in the word, then
1360        try completing this word as a username. */
1361     if (!matches && *state.word == '~' && (state.flags & INPUT_COMPLETE_USERNAMES)
1362         && !strchr (state.word, PATH_SEP))
1363     {
1364         SHOW_C_CTX ("try_complete:user_subst");
1365         matches = completion_matches (state.word, username_completion_function, state.flags);
1366     }
1367
1368     /* And finally if this word is in a command position, then
1369        complete over possible command names, including aliases, functions,
1370        and command names. */
1371     if (matches == NULL)
1372         matches = try_complete_all_possible (&state, text, lc_start);
1373
1374     g_free (state.word);
1375
1376     return matches;
1377 }
1378
1379 /* --------------------------------------------------------------------------------------------- */
1380
1381 void
1382 complete_engine_fill_completions (WInput * in)
1383 {
1384     char *s;
1385
1386     end = str_offset_to_pos (in->buffer, in->point);
1387
1388     s = in->buffer;
1389     if (in->point != 0)
1390     {
1391         /* get symbol before in->point */
1392         size_t i;
1393
1394         for (i = in->point - 1; i > 0; i--)
1395             str_next_char (&s);
1396     }
1397
1398     for (; s >= in->buffer; str_prev_char (&s))
1399     {
1400         start = s - in->buffer;
1401         if (strchr (" \t;|<>", *s) != NULL)
1402             break;
1403     }
1404
1405     if (start < end)
1406     {
1407         str_next_char (&s);
1408         start = s - in->buffer;
1409     }
1410
1411     in->completions = try_complete (in->buffer, &start, &end, in->completion_flags);
1412 }
1413
1414 /* --------------------------------------------------------------------------------------------- */
1415
1416 /* declared in lib/widget/input.h */
1417 void
1418 complete (WInput * in)
1419 {
1420     int engine_flags;
1421
1422     if (!str_is_valid_string (in->buffer))
1423         return;
1424
1425     if (in->completions != NULL)
1426         engine_flags = DO_QUERY;
1427     else
1428     {
1429         engine_flags = DO_INSERTION;
1430
1431         if (mc_global.widget.show_all_if_ambiguous)
1432             engine_flags |= DO_QUERY;
1433     }
1434
1435     while (complete_engine (in, engine_flags))
1436         ;
1437 }
1438
1439 /* --------------------------------------------------------------------------------------------- */