src/filemanager/complete.c

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