Extract path.c from misc1.c

1 files changed, 1319 insertions, 0 deletions

diff --git a/src/path.c b/src/path.c
new file mode 100644
index 0000000000..2e8865b0c7
--- /dev/null
+++ b/src/path.c
@@ -0,0 +1,1319 @@
+#include "vim.h"
+#include "path.h"
+#include "charset.h"
+#include "eval.h"
+#include "ex_getln.h"
+#include "fileio.h"
+#include "memline.h"
+#include "misc1.h"
+#include "misc2.h"
+#include "garray.h"
+#include "types.h"
+#include "os_unix.h"
+#include "regexp.h"
+#include "tag.h"
+#include "ui.h"
+#include "window.h"
+#include "os/os.h"
+
+/*
+ * Compare two file names and return:
+ * FPC_SAME   if they both exist and are the same file.
+ * FPC_SAMEX  if they both don't exist and have the same file name.
+ * FPC_DIFF   if they both exist and are different files.
+ * FPC_NOTX   if they both don't exist.
+ * FPC_DIFFX  if one of them doesn't exist.
+ * For the first name environment variables are expanded
+ */
+int 
+fullpathcmp (
+    char_u *s1,
+    char_u *s2,
+    int checkname                  /* when both don't exist, check file names */
+)
+{
+#ifdef UNIX
+  char_u exp1[MAXPATHL];
+  char_u full1[MAXPATHL];
+  char_u full2[MAXPATHL];
+  struct stat st1, st2;
+  int r1, r2;
+
+  expand_env(s1, exp1, MAXPATHL);
+  r1 = mch_stat((char *)exp1, &st1);
+  r2 = mch_stat((char *)s2, &st2);
+  if (r1 != 0 && r2 != 0) {
+    /* if mch_stat() doesn't work, may compare the names */
+    if (checkname) {
+      if (fnamecmp(exp1, s2) == 0)
+        return FPC_SAMEX;
+      r1 = vim_FullName(exp1, full1, MAXPATHL, FALSE);
+      r2 = vim_FullName(s2, full2, MAXPATHL, FALSE);
+      if (r1 == OK && r2 == OK && fnamecmp(full1, full2) == 0)
+        return FPC_SAMEX;
+    }
+    return FPC_NOTX;
+  }
+  if (r1 != 0 || r2 != 0)
+    return FPC_DIFFX;
+  if (st1.st_dev == st2.st_dev && st1.st_ino == st2.st_ino)
+    return FPC_SAME;
+  return FPC_DIFF;
+#else
+  char_u  *exp1;                /* expanded s1 */
+  char_u  *full1;               /* full path of s1 */
+  char_u  *full2;               /* full path of s2 */
+  int retval = FPC_DIFF;
+  int r1, r2;
+
+  /* allocate one buffer to store three paths (alloc()/free() is slow!) */
+  if ((exp1 = alloc(MAXPATHL * 3)) != NULL) {
+    full1 = exp1 + MAXPATHL;
+    full2 = full1 + MAXPATHL;
+
+    expand_env(s1, exp1, MAXPATHL);
+    r1 = vim_FullName(exp1, full1, MAXPATHL, FALSE);
+    r2 = vim_FullName(s2, full2, MAXPATHL, FALSE);
+
+    /* If vim_FullName() fails, the file probably doesn't exist. */
+    if (r1 != OK && r2 != OK) {
+      if (checkname && fnamecmp(exp1, s2) == 0)
+        retval = FPC_SAMEX;
+      else
+        retval = FPC_NOTX;
+    } else if (r1 != OK || r2 != OK)
+      retval = FPC_DIFFX;
+    else if (fnamecmp(full1, full2))
+      retval = FPC_DIFF;
+    else
+      retval = FPC_SAME;
+    vim_free(exp1);
+  }
+  return retval;
+#endif
+}
+
+/*
+ * Get the tail of a path: the file name.
+ * When the path ends in a path separator the tail is the NUL after it.
+ * Fail safe: never returns NULL.
+ */
+char_u *gettail(char_u *fname)
+{
+  char_u  *p1, *p2;
+
+  if (fname == NULL)
+    return (char_u *)"";
+  for (p1 = p2 = get_past_head(fname); *p2; ) { /* find last part of path */
+    if (vim_ispathsep_nocolon(*p2))
+      p1 = p2 + 1;
+    mb_ptr_adv(p2);
+  }
+  return p1;
+}
+
+static char_u *gettail_dir(char_u *fname);
+
+/*
+ * Return the end of the directory name, on the first path
+ * separator:
+ * "/path/file", "/path/dir/", "/path//dir", "/file"
+ *	 ^	       ^	     ^	      ^
+ */
+static char_u *gettail_dir(char_u *fname)
+{
+  char_u      *dir_end = fname;
+  char_u      *next_dir_end = fname;
+  int look_for_sep = TRUE;
+  char_u      *p;
+
+  for (p = fname; *p != NUL; ) {
+    if (vim_ispathsep(*p)) {
+      if (look_for_sep) {
+        next_dir_end = p;
+        look_for_sep = FALSE;
+      }
+    } else {
+      if (!look_for_sep)
+        dir_end = next_dir_end;
+      look_for_sep = TRUE;
+    }
+    mb_ptr_adv(p);
+  }
+  return dir_end;
+}
+
+/*
+ * Get pointer to tail of "fname", including path separators.  Putting a NUL
+ * here leaves the directory name.  Takes care of "c:/" and "//".
+ * Always returns a valid pointer.
+ */
+char_u *gettail_sep(char_u *fname)
+{
+  char_u      *p;
+  char_u      *t;
+
+  p = get_past_head(fname);     /* don't remove the '/' from "c:/file" */
+  t = gettail(fname);
+  while (t > p && after_pathsep(fname, t))
+    --t;
+  return t;
+}
+
+/*
+ * get the next path component (just after the next path separator).
+ */
+char_u *getnextcomp(char_u *fname)
+{
+  while (*fname && !vim_ispathsep(*fname))
+    mb_ptr_adv(fname);
+  if (*fname)
+    ++fname;
+  return fname;
+}
+
+/*
+ * Get a pointer to one character past the head of a path name.
+ * Unix: after "/"; DOS: after "c:\"; Amiga: after "disk:/"; Mac: no head.
+ * If there is no head, path is returned.
+ */
+char_u *get_past_head(char_u *path)
+{
+  char_u  *retval;
+
+  retval = path;
+
+  while (vim_ispathsep(*retval))
+    ++retval;
+
+  return retval;
+}
+
+/*
+ * Return TRUE if 'c' is a path separator.
+ * Note that for MS-Windows this includes the colon.
+ */
+int vim_ispathsep(int c)
+{
+#ifdef UNIX
+  return c == '/';          /* UNIX has ':' inside file names */
+#else
+# ifdef BACKSLASH_IN_FILENAME
+  return c == ':' || c == '/' || c == '\\';
+# else
+  return c == ':' || c == '/';
+# endif
+#endif
+}
+
+/*
+ * Like vim_ispathsep(c), but exclude the colon for MS-Windows.
+ */
+int vim_ispathsep_nocolon(int c)
+{
+  return vim_ispathsep(c)
+#ifdef BACKSLASH_IN_FILENAME
+         && c != ':'
+#endif
+  ;
+}
+
+/*
+ * return TRUE if 'c' is a path list separator.
+ */
+int vim_ispathlistsep(int c)
+{
+#ifdef UNIX
+  return c == ':';
+#else
+  return c == ';';      /* might not be right for every system... */
+#endif
+}
+
+#if defined(FEAT_GUI_TABLINE) || defined(FEAT_WINDOWS) \
+  || defined(FEAT_EVAL) || defined(PROTO)
+/*
+ * Shorten the path of a file from "~/foo/../.bar/fname" to "~/f/../.b/fname"
+ * It's done in-place.
+ */
+void shorten_dir(char_u *str)
+{
+  char_u      *tail, *s, *d;
+  int skip = FALSE;
+
+  tail = gettail(str);
+  d = str;
+  for (s = str;; ++s) {
+    if (s >= tail) {                /* copy the whole tail */
+      *d++ = *s;
+      if (*s == NUL)
+        break;
+    } else if (vim_ispathsep(*s)) {       /* copy '/' and next char */
+      *d++ = *s;
+      skip = FALSE;
+    } else if (!skip) {
+      *d++ = *s;                    /* copy next char */
+      if (*s != '~' && *s != '.')       /* and leading "~" and "." */
+        skip = TRUE;
+      if (has_mbyte) {
+        int l = mb_ptr2len(s);
+
+        while (--l > 0)
+          *d++ = *++s;
+      }
+    }
+  }
+}
+#endif
+
+/*
+ * Return TRUE if the directory of "fname" exists, FALSE otherwise.
+ * Also returns TRUE if there is no directory name.
+ * "fname" must be writable!.
+ */
+int dir_of_file_exists(char_u *fname)
+{
+  char_u      *p;
+  int c;
+  int retval;
+
+  p = gettail_sep(fname);
+  if (p == fname)
+    return TRUE;
+  c = *p;
+  *p = NUL;
+  retval = os_isdir(fname);
+  *p = c;
+  return retval;
+}
+
+/*
+ * Versions of fnamecmp() and fnamencmp() that handle '/' and '\' equally
+ * and deal with 'fileignorecase'.
+ */
+int vim_fnamecmp(char_u *x, char_u *y)
+{
+#ifdef BACKSLASH_IN_FILENAME
+  return vim_fnamencmp(x, y, MAXPATHL);
+#else
+  if (p_fic)
+    return MB_STRICMP(x, y);
+  return STRCMP(x, y);
+#endif
+}
+
+int vim_fnamencmp(char_u *x, char_u *y, size_t len)
+{
+#ifdef BACKSLASH_IN_FILENAME
+  char_u      *px = x;
+  char_u      *py = y;
+  int cx = NUL;
+  int cy = NUL;
+
+  while (len > 0) {
+    cx = PTR2CHAR(px);
+    cy = PTR2CHAR(py);
+    if (cx == NUL || cy == NUL
+        || ((p_fic ? MB_TOLOWER(cx) != MB_TOLOWER(cy) : cx != cy)
+            && !(cx == '/' && cy == '\\')
+            && !(cx == '\\' && cy == '/')))
+      break;
+    len -= MB_PTR2LEN(px);
+    px += MB_PTR2LEN(px);
+    py += MB_PTR2LEN(py);
+  }
+  if (len == 0)
+    return 0;
+  return cx - cy;
+#else
+  if (p_fic)
+    return MB_STRNICMP(x, y, len);
+  return STRNCMP(x, y, len);
+#endif
+}
+
+/*
+ * Concatenate file names fname1 and fname2 into allocated memory.
+ * Only add a '/' or '\\' when 'sep' is TRUE and it is necessary.
+ */
+char_u *concat_fnames(char_u *fname1, char_u *fname2, int sep)
+{
+  char_u  *dest;
+
+  dest = alloc((unsigned)(STRLEN(fname1) + STRLEN(fname2) + 3));
+  if (dest != NULL) {
+    STRCPY(dest, fname1);
+    if (sep)
+      add_pathsep(dest);
+    STRCAT(dest, fname2);
+  }
+  return dest;
+}
+
+/*
+ * Concatenate two strings and return the result in allocated memory.
+ * Returns NULL when out of memory.
+ */
+char_u *concat_str(char_u *str1, char_u *str2)
+{
+  char_u  *dest;
+  size_t l = STRLEN(str1);
+
+  dest = alloc((unsigned)(l + STRLEN(str2) + 1L));
+  if (dest != NULL) {
+    STRCPY(dest, str1);
+    STRCPY(dest + l, str2);
+  }
+  return dest;
+}
+
+/*
+ * Add a path separator to a file name, unless it already ends in a path
+ * separator.
+ */
+void add_pathsep(char_u *p)
+{
+  if (*p != NUL && !after_pathsep(p, p + STRLEN(p)))
+    STRCAT(p, PATHSEPSTR);
+}
+
+/*
+ * FullName_save - Make an allocated copy of a full file name.
+ * Returns NULL when out of memory.
+ */
+char_u *
+FullName_save (
+    char_u *fname,
+    int force                      /* force expansion, even when it already looks
+                                 * like a full path name */
+)
+{
+  char_u      *buf;
+  char_u      *new_fname = NULL;
+
+  if (fname == NULL)
+    return NULL;
+
+  buf = alloc((unsigned)MAXPATHL);
+  if (buf != NULL) {
+    if (vim_FullName(fname, buf, MAXPATHL, force) != FAIL)
+      new_fname = vim_strsave(buf);
+    else
+      new_fname = vim_strsave(fname);
+    vim_free(buf);
+  }
+  return new_fname;
+}
+
+#if !defined(NO_EXPANDPATH) || defined(PROTO)
+
+static int vim_backtick(char_u *p);
+static int expand_backtick(garray_T *gap, char_u *pat, int flags);
+
+
+#if (defined(UNIX) && !defined(VMS)) || defined(USE_UNIXFILENAME) \
+  || defined(PROTO)
+/*
+ * Unix style wildcard expansion code.
+ * It's here because it's used both for Unix and Mac.
+ */
+static int pstrcmp(const void *, const void *);
+
+static int pstrcmp(const void *a, const void *b)
+{
+  return pathcmp(*(char **)a, *(char **)b, -1);
+}
+
+/*
+ * Recursively expand one path component into all matching files and/or
+ * directories.  Adds matches to "gap".  Handles "*", "?", "[a-z]", "**", etc.
+ * "path" has backslashes before chars that are not to be expanded, starting
+ * at "path + wildoff".
+ * Return the number of matches found.
+ * NOTE: much of this is identical to dos_expandpath(), keep in sync!
+ */
+int 
+unix_expandpath (
+    garray_T *gap,
+    char_u *path,
+    int wildoff,
+    int flags,                      /* EW_* flags */
+    int didstar                    /* expanded "**" once already */
+)
+{
+  char_u      *buf;
+  char_u      *path_end;
+  char_u      *p, *s, *e;
+  int start_len = gap->ga_len;
+  char_u      *pat;
+  regmatch_T regmatch;
+  int starts_with_dot;
+  int matches;
+  int len;
+  int starstar = FALSE;
+  static int stardepth = 0;         /* depth for "**" expansion */
+
+  DIR         *dirp;
+  struct dirent *dp;
+
+  /* Expanding "**" may take a long time, check for CTRL-C. */
+  if (stardepth > 0) {
+    ui_breakcheck();
+    if (got_int)
+      return 0;
+  }
+
+  /* make room for file name */
+  buf = alloc((int)STRLEN(path) + BASENAMELEN + 5);
+  if (buf == NULL)
+    return 0;
+
+  /*
+   * Find the first part in the path name that contains a wildcard.
+   * When EW_ICASE is set every letter is considered to be a wildcard.
+   * Copy it into "buf", including the preceding characters.
+   */
+  p = buf;
+  s = buf;
+  e = NULL;
+  path_end = path;
+  while (*path_end != NUL) {
+    /* May ignore a wildcard that has a backslash before it; it will
+     * be removed by rem_backslash() or file_pat_to_reg_pat() below. */
+    if (path_end >= path + wildoff && rem_backslash(path_end))
+      *p++ = *path_end++;
+    else if (*path_end == '/') {
+      if (e != NULL)
+        break;
+      s = p + 1;
+    } else if (path_end >= path + wildoff
+               && (vim_strchr((char_u *)"*?[{~$", *path_end) != NULL
+                   || (!p_fic && (flags & EW_ICASE)
+                       && isalpha(PTR2CHAR(path_end)))))
+      e = p;
+    if (has_mbyte) {
+      len = (*mb_ptr2len)(path_end);
+      STRNCPY(p, path_end, len);
+      p += len;
+      path_end += len;
+    } else
+      *p++ = *path_end++;
+  }
+  e = p;
+  *e = NUL;
+
+  /* Now we have one wildcard component between "s" and "e". */
+  /* Remove backslashes between "wildoff" and the start of the wildcard
+   * component. */
+  for (p = buf + wildoff; p < s; ++p)
+    if (rem_backslash(p)) {
+      STRMOVE(p, p + 1);
+      --e;
+      --s;
+    }
+
+  /* Check for "**" between "s" and "e". */
+  for (p = s; p < e; ++p)
+    if (p[0] == '*' && p[1] == '*')
+      starstar = TRUE;
+
+  /* convert the file pattern to a regexp pattern */
+  starts_with_dot = (*s == '.');
+  pat = file_pat_to_reg_pat(s, e, NULL, FALSE);
+  if (pat == NULL) {
+    vim_free(buf);
+    return 0;
+  }
+
+  /* compile the regexp into a program */
+  if (flags & EW_ICASE)
+    regmatch.rm_ic = TRUE;              /* 'wildignorecase' set */
+  else
+    regmatch.rm_ic = p_fic;     /* ignore case when 'fileignorecase' is set */
+  if (flags & (EW_NOERROR | EW_NOTWILD))
+    ++emsg_silent;
+  regmatch.regprog = vim_regcomp(pat, RE_MAGIC);
+  if (flags & (EW_NOERROR | EW_NOTWILD))
+    --emsg_silent;
+  vim_free(pat);
+
+  if (regmatch.regprog == NULL && (flags & EW_NOTWILD) == 0) {
+    vim_free(buf);
+    return 0;
+  }
+
+  /* If "**" is by itself, this is the first time we encounter it and more
+   * is following then find matches without any directory. */
+  if (!didstar && stardepth < 100 && starstar && e - s == 2
+      && *path_end == '/') {
+    STRCPY(s, path_end + 1);
+    ++stardepth;
+    (void)unix_expandpath(gap, buf, (int)(s - buf), flags, TRUE);
+    --stardepth;
+  }
+
+  /* open the directory for scanning */
+  *s = NUL;
+  dirp = opendir(*buf == NUL ? "." : (char *)buf);
+
+  /* Find all matching entries */
+  if (dirp != NULL) {
+    for (;; ) {
+      dp = readdir(dirp);
+      if (dp == NULL)
+        break;
+      if ((dp->d_name[0] != '.' || starts_with_dot)
+          && ((regmatch.regprog != NULL && vim_regexec(&regmatch,
+                   (char_u *)dp->d_name, (colnr_T)0))
+              || ((flags & EW_NOTWILD)
+                  && fnamencmp(path + (s - buf), dp->d_name, e - s) == 0))) {
+        STRCPY(s, dp->d_name);
+        len = STRLEN(buf);
+
+        if (starstar && stardepth < 100) {
+          /* For "**" in the pattern first go deeper in the tree to
+           * find matches. */
+          STRCPY(buf + len, "/**");
+          STRCPY(buf + len + 3, path_end);
+          ++stardepth;
+          (void)unix_expandpath(gap, buf, len + 1, flags, TRUE);
+          --stardepth;
+        }
+
+        STRCPY(buf + len, path_end);
+        if (mch_has_exp_wildcard(path_end)) {       /* handle more wildcards */
+          /* need to expand another component of the path */
+          /* remove backslashes for the remaining components only */
+          (void)unix_expandpath(gap, buf, len + 1, flags, FALSE);
+        } else {
+          /* no more wildcards, check if there is a match */
+          /* remove backslashes for the remaining components only */
+          if (*path_end != NUL)
+            backslash_halve(buf + len + 1);
+          if (os_file_exists(buf)) {          /* add existing file */
+#ifdef MACOS_CONVERT
+            size_t precomp_len = STRLEN(buf)+1;
+            char_u *precomp_buf =
+              mac_precompose_path(buf, precomp_len, &precomp_len);
+
+            if (precomp_buf) {
+              memmove(buf, precomp_buf, precomp_len);
+              vim_free(precomp_buf);
+            }
+#endif
+            addfile(gap, buf, flags);
+          }
+        }
+      }
+    }
+
+    closedir(dirp);
+  }
+
+  vim_free(buf);
+  vim_regfree(regmatch.regprog);
+
+  matches = gap->ga_len - start_len;
+  if (matches > 0)
+    qsort(((char_u **)gap->ga_data) + start_len, matches,
+        sizeof(char_u *), pstrcmp);
+  return matches;
+}
+#endif
+
+static int find_previous_pathsep(char_u *path, char_u **psep);
+static int is_unique(char_u *maybe_unique, garray_T *gap, int i);
+static void expand_path_option(char_u *curdir, garray_T *gap);
+static char_u *get_path_cutoff(char_u *fname, garray_T *gap);
+static void uniquefy_paths(garray_T *gap, char_u *pattern);
+static int expand_in_path(garray_T *gap, char_u *pattern, int flags);
+
+/*
+ * Moves "*psep" back to the previous path separator in "path".
+ * Returns FAIL is "*psep" ends up at the beginning of "path".
+ */
+static int find_previous_pathsep(char_u *path, char_u **psep)
+{
+  /* skip the current separator */
+  if (*psep > path && vim_ispathsep(**psep))
+    --*psep;
+
+  /* find the previous separator */
+  while (*psep > path) {
+    if (vim_ispathsep(**psep))
+      return OK;
+    mb_ptr_back(path, *psep);
+  }
+
+  return FAIL;
+}
+
+/*
+ * Returns TRUE if "maybe_unique" is unique wrt other_paths in "gap".
+ * "maybe_unique" is the end portion of "((char_u **)gap->ga_data)[i]".
+ */
+static int is_unique(char_u *maybe_unique, garray_T *gap, int i)
+{
+  int j;
+  int candidate_len;
+  int other_path_len;
+  char_u  **other_paths = (char_u **)gap->ga_data;
+  char_u  *rival;
+
+  for (j = 0; j < gap->ga_len; j++) {
+    if (j == i)
+      continue;        /* don't compare it with itself */
+
+    candidate_len = (int)STRLEN(maybe_unique);
+    other_path_len = (int)STRLEN(other_paths[j]);
+    if (other_path_len < candidate_len)
+      continue;        /* it's different when it's shorter */
+
+    rival = other_paths[j] + other_path_len - candidate_len;
+    if (fnamecmp(maybe_unique, rival) == 0
+        && (rival == other_paths[j] || vim_ispathsep(*(rival - 1))))
+      return FALSE;        /* match */
+  }
+
+  return TRUE;    /* no match found */
+}
+
+/*
+ * Split the 'path' option into an array of strings in garray_T.  Relative
+ * paths are expanded to their equivalent fullpath.  This includes the "."
+ * (relative to current buffer directory) and empty path (relative to current
+ * directory) notations.
+ *
+ * TODO: handle upward search (;) and path limiter (**N) notations by
+ * expanding each into their equivalent path(s).
+ */
+static void expand_path_option(char_u *curdir, garray_T *gap)
+{
+  char_u      *path_option = *curbuf->b_p_path == NUL
+                             ? p_path : curbuf->b_p_path;
+  char_u      *buf;
+  char_u      *p;
+  int len;
+
+  if ((buf = alloc((int)MAXPATHL)) == NULL)
+    return;
+
+  while (*path_option != NUL) {
+    copy_option_part(&path_option, buf, MAXPATHL, " ,");
+
+    if (buf[0] == '.' && (buf[1] == NUL || vim_ispathsep(buf[1]))) {
+      /* Relative to current buffer:
+       * "/path/file" + "." -> "/path/"
+       * "/path/file"  + "./subdir" -> "/path/subdir" */
+      if (curbuf->b_ffname == NULL)
+        continue;
+      p = gettail(curbuf->b_ffname);
+      len = (int)(p - curbuf->b_ffname);
+      if (len + (int)STRLEN(buf) >= MAXPATHL)
+        continue;
+      if (buf[1] == NUL)
+        buf[len] = NUL;
+      else
+        STRMOVE(buf + len, buf + 2);
+      memmove(buf, curbuf->b_ffname, len);
+      simplify_filename(buf);
+    } else if (buf[0] == NUL)
+      /* relative to current directory */
+      STRCPY(buf, curdir);
+    else if (path_with_url(buf))
+      /* URL can't be used here */
+      continue;
+    else if (!os_is_absolute_path(buf)) {
+      /* Expand relative path to their full path equivalent */
+      len = (int)STRLEN(curdir);
+      if (len + (int)STRLEN(buf) + 3 > MAXPATHL)
+        continue;
+      STRMOVE(buf + len + 1, buf);
+      STRCPY(buf, curdir);
+      buf[len] = PATHSEP;
+      simplify_filename(buf);
+    }
+
+    if (ga_grow(gap, 1) == FAIL)
+      break;
+
+
+    p = vim_strsave(buf);
+    if (p == NULL)
+      break;
+    ((char_u **)gap->ga_data)[gap->ga_len++] = p;
+  }
+
+  vim_free(buf);
+}
+
+/*
+ * Returns a pointer to the file or directory name in "fname" that matches the
+ * longest path in "ga"p, or NULL if there is no match. For example:
+ *
+ *    path: /foo/bar/baz
+ *   fname: /foo/bar/baz/quux.txt
+ * returns:		 ^this
+ */
+static char_u *get_path_cutoff(char_u *fname, garray_T *gap)
+{
+  int i;
+  int maxlen = 0;
+  char_u  **path_part = (char_u **)gap->ga_data;
+  char_u  *cutoff = NULL;
+
+  for (i = 0; i < gap->ga_len; i++) {
+    int j = 0;
+
+    while ((fname[j] == path_part[i][j]
+            ) && fname[j] != NUL && path_part[i][j] != NUL)
+      j++;
+    if (j > maxlen) {
+      maxlen = j;
+      cutoff = &fname[j];
+    }
+  }
+
+  /* skip to the file or directory name */
+  if (cutoff != NULL)
+    while (vim_ispathsep(*cutoff))
+      mb_ptr_adv(cutoff);
+
+  return cutoff;
+}
+
+/*
+ * Sorts, removes duplicates and modifies all the fullpath names in "gap" so
+ * that they are unique with respect to each other while conserving the part
+ * that matches the pattern. Beware, this is at least O(n^2) wrt "gap->ga_len".
+ */
+static void uniquefy_paths(garray_T *gap, char_u *pattern)
+{
+  int i;
+  int len;
+  char_u      **fnames = (char_u **)gap->ga_data;
+  int sort_again = FALSE;
+  char_u      *pat;
+  char_u      *file_pattern;
+  char_u      *curdir;
+  regmatch_T regmatch;
+  garray_T path_ga;
+  char_u      **in_curdir = NULL;
+  char_u      *short_name;
+
+  remove_duplicates(gap);
+  ga_init2(&path_ga, (int)sizeof(char_u *), 1);
+
+  /*
+   * We need to prepend a '*' at the beginning of file_pattern so that the
+   * regex matches anywhere in the path. FIXME: is this valid for all
+   * possible patterns?
+   */
+  len = (int)STRLEN(pattern);
+  file_pattern = alloc(len + 2);
+  if (file_pattern == NULL)
+    return;
+  file_pattern[0] = '*';
+  file_pattern[1] = NUL;
+  STRCAT(file_pattern, pattern);
+  pat = file_pat_to_reg_pat(file_pattern, NULL, NULL, TRUE);
+  vim_free(file_pattern);
+  if (pat == NULL)
+    return;
+
+  regmatch.rm_ic = TRUE;                /* always ignore case */
+  regmatch.regprog = vim_regcomp(pat, RE_MAGIC + RE_STRING);
+  vim_free(pat);
+  if (regmatch.regprog == NULL)
+    return;
+
+  if ((curdir = alloc((int)(MAXPATHL))) == NULL)
+    goto theend;
+  os_dirname(curdir, MAXPATHL);
+  expand_path_option(curdir, &path_ga);
+
+  in_curdir = (char_u **)alloc_clear(gap->ga_len * sizeof(char_u *));
+  if (in_curdir == NULL)
+    goto theend;
+
+  for (i = 0; i < gap->ga_len && !got_int; i++) {
+    char_u      *path = fnames[i];
+    int is_in_curdir;
+    char_u      *dir_end = gettail_dir(path);
+    char_u      *pathsep_p;
+    char_u      *path_cutoff;
+
+    len = (int)STRLEN(path);
+    is_in_curdir = fnamencmp(curdir, path, dir_end - path) == 0
+                   && curdir[dir_end - path] == NUL;
+    if (is_in_curdir)
+      in_curdir[i] = vim_strsave(path);
+
+    /* Shorten the filename while maintaining its uniqueness */
+    path_cutoff = get_path_cutoff(path, &path_ga);
+
+    /* we start at the end of the path */
+    pathsep_p = path + len - 1;
+
+    while (find_previous_pathsep(path, &pathsep_p))
+      if (vim_regexec(&regmatch, pathsep_p + 1, (colnr_T)0)
+          && is_unique(pathsep_p + 1, gap, i)
+          && path_cutoff != NULL && pathsep_p + 1 >= path_cutoff) {
+        sort_again = TRUE;
+        memmove(path, pathsep_p + 1, STRLEN(pathsep_p));
+        break;
+      }
+
+    if (os_is_absolute_path(path)) {
+      /*
+       * Last resort: shorten relative to curdir if possible.
+       * 'possible' means:
+       * 1. It is under the current directory.
+       * 2. The result is actually shorter than the original.
+       *
+       *	    Before		  curdir	After
+       *	    /foo/bar/file.txt	  /foo/bar	./file.txt
+       *	    c:\foo\bar\file.txt   c:\foo\bar	.\file.txt
+       *	    /file.txt		  /		/file.txt
+       *	    c:\file.txt		  c:\		.\file.txt
+       */
+      short_name = shorten_fname(path, curdir);
+      if (short_name != NULL && short_name > path + 1
+          ) {
+        STRCPY(path, ".");
+        add_pathsep(path);
+        STRMOVE(path + STRLEN(path), short_name);
+      }
+    }
+    ui_breakcheck();
+  }
+
+  /* Shorten filenames in /in/current/directory/{filename} */
+  for (i = 0; i < gap->ga_len && !got_int; i++) {
+    char_u *rel_path;
+    char_u *path = in_curdir[i];
+
+    if (path == NULL)
+      continue;
+
+    /* If the {filename} is not unique, change it to ./{filename}.
+     * Else reduce it to {filename} */
+    short_name = shorten_fname(path, curdir);
+    if (short_name == NULL)
+      short_name = path;
+    if (is_unique(short_name, gap, i)) {
+      STRCPY(fnames[i], short_name);
+      continue;
+    }
+
+    rel_path = alloc((int)(STRLEN(short_name) + STRLEN(PATHSEPSTR) + 2));
+    if (rel_path == NULL)
+      goto theend;
+    STRCPY(rel_path, ".");
+    add_pathsep(rel_path);
+    STRCAT(rel_path, short_name);
+
+    vim_free(fnames[i]);
+    fnames[i] = rel_path;
+    sort_again = TRUE;
+    ui_breakcheck();
+  }
+
+theend:
+  vim_free(curdir);
+  if (in_curdir != NULL) {
+    for (i = 0; i < gap->ga_len; i++)
+      vim_free(in_curdir[i]);
+    vim_free(in_curdir);
+  }
+  ga_clear_strings(&path_ga);
+  vim_regfree(regmatch.regprog);
+
+  if (sort_again)
+    remove_duplicates(gap);
+}
+
+/*
+ * Calls globpath() with 'path' values for the given pattern and stores the
+ * result in "gap".
+ * Returns the total number of matches.
+ */
+static int 
+expand_in_path (
+    garray_T *gap,
+    char_u *pattern,
+    int flags                      /* EW_* flags */
+)
+{
+  char_u      *curdir;
+  garray_T path_ga;
+  char_u      *files = NULL;
+  char_u      *s;       /* start */
+  char_u      *e;       /* end */
+  char_u      *paths = NULL;
+
+  if ((curdir = alloc((unsigned)MAXPATHL)) == NULL)
+    return 0;
+  os_dirname(curdir, MAXPATHL);
+
+  ga_init2(&path_ga, (int)sizeof(char_u *), 1);
+  expand_path_option(curdir, &path_ga);
+  vim_free(curdir);
+  if (path_ga.ga_len == 0)
+    return 0;
+
+  paths = ga_concat_strings(&path_ga);
+  ga_clear_strings(&path_ga);
+  if (paths == NULL)
+    return 0;
+
+  files = globpath(paths, pattern, (flags & EW_ICASE) ? WILD_ICASE : 0);
+  vim_free(paths);
+  if (files == NULL)
+    return 0;
+
+  /* Copy each path in files into gap */
+  s = e = files;
+  while (*s != NUL) {
+    while (*e != '\n' && *e != NUL)
+      e++;
+    if (*e == NUL) {
+      addfile(gap, s, flags);
+      break;
+    } else {
+      /* *e is '\n' */
+      *e = NUL;
+      addfile(gap, s, flags);
+      e++;
+      s = e;
+    }
+  }
+  vim_free(files);
+
+  return gap->ga_len;
+}
+
+/*
+ * Sort "gap" and remove duplicate entries.  "gap" is expected to contain a
+ * list of file names in allocated memory.
+ */
+void remove_duplicates(garray_T *gap)
+{
+  int i;
+  int j;
+  char_u  **fnames = (char_u **)gap->ga_data;
+
+  sort_strings(fnames, gap->ga_len);
+  for (i = gap->ga_len - 1; i > 0; --i)
+    if (fnamecmp(fnames[i - 1], fnames[i]) == 0) {
+      vim_free(fnames[i]);
+      for (j = i + 1; j < gap->ga_len; ++j)
+        fnames[j - 1] = fnames[j];
+      --gap->ga_len;
+    }
+}
+
+static int has_env_var(char_u *p);
+
+/*
+ * Return TRUE if "p" contains what looks like an environment variable.
+ * Allowing for escaping.
+ */
+static int has_env_var(char_u *p)
+{
+  for (; *p; mb_ptr_adv(p)) {
+    if (*p == '\\' && p[1] != NUL)
+      ++p;
+    else if (vim_strchr((char_u *)
+                 "$"
+                 , *p) != NULL)
+      return TRUE;
+  }
+  return FALSE;
+}
+
+#ifdef SPECIAL_WILDCHAR
+static int has_special_wildchar(char_u *p);
+
+/*
+ * Return TRUE if "p" contains a special wildcard character.
+ * Allowing for escaping.
+ */
+static int has_special_wildchar(char_u *p)
+{
+  for (; *p; mb_ptr_adv(p)) {
+    if (*p == '\\' && p[1] != NUL)
+      ++p;
+    else if (vim_strchr((char_u *)SPECIAL_WILDCHAR, *p) != NULL)
+      return TRUE;
+  }
+  return FALSE;
+}
+#endif
+
+/*
+ * Generic wildcard expansion code.
+ *
+ * Characters in "pat" that should not be expanded must be preceded with a
+ * backslash. E.g., "/path\ with\ spaces/my\*star*"
+ *
+ * Return FAIL when no single file was found.  In this case "num_file" is not
+ * set, and "file" may contain an error message.
+ * Return OK when some files found.  "num_file" is set to the number of
+ * matches, "file" to the array of matches.  Call FreeWild() later.
+ */
+int 
+gen_expand_wildcards (
+    int num_pat,                    /* number of input patterns */
+    char_u **pat,              /* array of input patterns */
+    int *num_file,          /* resulting number of files */
+    char_u ***file,            /* array of resulting files */
+    int flags                      /* EW_* flags */
+)
+{
+  int i;
+  garray_T ga;
+  char_u              *p;
+  static int recursive = FALSE;
+  int add_pat;
+  int did_expand_in_path = FALSE;
+
+  /*
+   * expand_env() is called to expand things like "~user".  If this fails,
+   * it calls ExpandOne(), which brings us back here.  In this case, always
+   * call the machine specific expansion function, if possible.  Otherwise,
+   * return FAIL.
+   */
+  if (recursive)
+#ifdef SPECIAL_WILDCHAR
+    return mch_expand_wildcards(num_pat, pat, num_file, file, flags);
+#else
+    return FAIL;
+#endif
+
+#ifdef SPECIAL_WILDCHAR
+  /*
+   * If there are any special wildcard characters which we cannot handle
+   * here, call machine specific function for all the expansion.  This
+   * avoids starting the shell for each argument separately.
+   * For `=expr` do use the internal function.
+   */
+  for (i = 0; i < num_pat; i++) {
+    if (has_special_wildchar(pat[i])
+        && !(vim_backtick(pat[i]) && pat[i][1] == '=')
+        )
+      return mch_expand_wildcards(num_pat, pat, num_file, file, flags);
+  }
+#endif
+
+  recursive = TRUE;
+
+  /*
+   * The matching file names are stored in a growarray.  Init it empty.
+   */
+  ga_init2(&ga, (int)sizeof(char_u *), 30);
+
+  for (i = 0; i < num_pat; ++i) {
+    add_pat = -1;
+    p = pat[i];
+
+    if (vim_backtick(p))
+      add_pat = expand_backtick(&ga, p, flags);
+    else {
+      /*
+       * First expand environment variables, "~/" and "~user/".
+       */
+      if (has_env_var(p) || *p == '~') {
+        p = expand_env_save_opt(p, TRUE);
+        if (p == NULL)
+          p = pat[i];
+#ifdef UNIX
+        /*
+         * On Unix, if expand_env() can't expand an environment
+         * variable, use the shell to do that.  Discard previously
+         * found file names and start all over again.
+         */
+        else if (has_env_var(p) || *p == '~') {
+          vim_free(p);
+          ga_clear_strings(&ga);
+          i = mch_expand_wildcards(num_pat, pat, num_file, file,
+              flags);
+          recursive = FALSE;
+          return i;
+        }
+#endif
+      }
+
+      /*
+       * If there are wildcards: Expand file names and add each match to
+       * the list.  If there is no match, and EW_NOTFOUND is given, add
+       * the pattern.
+       * If there are no wildcards: Add the file name if it exists or
+       * when EW_NOTFOUND is given.
+       */
+      if (mch_has_exp_wildcard(p)) {
+        if ((flags & EW_PATH)
+            && !os_is_absolute_path(p)
+            && !(p[0] == '.'
+                 && (vim_ispathsep(p[1])
+                     || (p[1] == '.' && vim_ispathsep(p[2]))))
+            ) {
+          /* :find completion where 'path' is used.
+           * Recursiveness is OK here. */
+          recursive = FALSE;
+          add_pat = expand_in_path(&ga, p, flags);
+          recursive = TRUE;
+          did_expand_in_path = TRUE;
+        } else
+          add_pat = mch_expandpath(&ga, p, flags);
+      }
+    }
+
+    if (add_pat == -1 || (add_pat == 0 && (flags & EW_NOTFOUND))) {
+      char_u      *t = backslash_halve_save(p);
+
+      /* When EW_NOTFOUND is used, always add files and dirs.  Makes
+       * "vim c:/" work. */
+      if (flags & EW_NOTFOUND)
+        addfile(&ga, t, flags | EW_DIR | EW_FILE);
+      else if (os_file_exists(t))
+        addfile(&ga, t, flags);
+      vim_free(t);
+    }
+
+    if (did_expand_in_path && ga.ga_len > 0 && (flags & EW_PATH))
+      uniquefy_paths(&ga, p);
+    if (p != pat[i])
+      vim_free(p);
+  }
+
+  *num_file = ga.ga_len;
+  *file = (ga.ga_data != NULL) ? (char_u **)ga.ga_data : (char_u **)"";
+
+  recursive = FALSE;
+
+  return (ga.ga_data != NULL) ? OK : FAIL;
+}
+
+
+/*
+ * Return TRUE if we can expand this backtick thing here.
+ */
+static int vim_backtick(char_u *p)
+{
+  return *p == '`' && *(p + 1) != NUL && *(p + STRLEN(p) - 1) == '`';
+}
+
+/*
+ * Expand an item in `backticks` by executing it as a command.
+ * Currently only works when pat[] starts and ends with a `.
+ * Returns number of file names found.
+ */
+static int 
+expand_backtick (
+    garray_T *gap,
+    char_u *pat,
+    int flags              /* EW_* flags */
+)
+{
+  char_u      *p;
+  char_u      *cmd;
+  char_u      *buffer;
+  int cnt = 0;
+  int i;
+
+  /* Create the command: lop off the backticks. */
+  cmd = vim_strnsave(pat + 1, (int)STRLEN(pat) - 2);
+  if (cmd == NULL)
+    return 0;
+
+  if (*cmd == '=')          /* `={expr}`: Expand expression */
+    buffer = eval_to_string(cmd + 1, &p, TRUE);
+  else
+    buffer = get_cmd_output(cmd, NULL,
+        (flags & EW_SILENT) ? SHELL_SILENT : 0);
+  vim_free(cmd);
+  if (buffer == NULL)
+    return 0;
+
+  cmd = buffer;
+  while (*cmd != NUL) {
+    cmd = skipwhite(cmd);               /* skip over white space */
+    p = cmd;
+    while (*p != NUL && *p != '\r' && *p != '\n')     /* skip over entry */
+      ++p;
+    /* add an entry if it is not empty */
+    if (p > cmd) {
+      i = *p;
+      *p = NUL;
+      addfile(gap, cmd, flags);
+      *p = i;
+      ++cnt;
+    }
+    cmd = p;
+    while (*cmd != NUL && (*cmd == '\r' || *cmd == '\n'))
+      ++cmd;
+  }
+
+  vim_free(buffer);
+  return cnt;
+}
+
+/*
+ * Add a file to a file list.  Accepted flags:
+ * EW_DIR	add directories
+ * EW_FILE	add files
+ * EW_EXEC	add executable files
+ * EW_NOTFOUND	add even when it doesn't exist
+ * EW_ADDSLASH	add slash after directory name
+ */
+void 
+addfile (
+    garray_T *gap,
+    char_u *f,         /* filename */
+    int flags
+)
+{
+  char_u      *p;
+  int isdir;
+
+  /* if the file/dir doesn't exist, may not add it */
+  if (!(flags & EW_NOTFOUND) && !os_file_exists(f))
+    return;
+
+#ifdef FNAME_ILLEGAL
+  /* if the file/dir contains illegal characters, don't add it */
+  if (vim_strpbrk(f, (char_u *)FNAME_ILLEGAL) != NULL)
+    return;
+#endif
+
+  isdir = os_isdir(f);
+  if ((isdir && !(flags & EW_DIR)) || (!isdir && !(flags & EW_FILE)))
+    return;
+
+  /* If the file isn't executable, may not add it.  Do accept directories. */
+  if (!isdir && (flags & EW_EXEC) && !os_can_exe(f))
+    return;
+
+  /* Make room for another item in the file list. */
+  if (ga_grow(gap, 1) == FAIL)
+    return;
+
+  p = alloc((unsigned)(STRLEN(f) + 1 + isdir));
+  if (p == NULL)
+    return;
+
+  STRCPY(p, f);
+#ifdef BACKSLASH_IN_FILENAME
+  slash_adjust(p);
+#endif
+  /*
+   * Append a slash or backslash after directory names if none is present.
+   */
+#ifndef DONT_ADD_PATHSEP_TO_DIR
+  if (isdir && (flags & EW_ADDSLASH))
+    add_pathsep(p);
+#endif
+  ((char_u **)gap->ga_data)[gap->ga_len++] = p;
+}
+#endif /* !NO_EXPANDPATH */