gpaths.nim

# A lazybuf is a lazily constructed path buffer.
# It supports append, reading previously appended chars,
# and retrieving the final string. It does not allocate a buffer
# to hold the output until that output diverges from s.
type lazybuf = object
  path:       string
  buf:        string
  w:          int
  volAndPath: string
  volLen:     int

type error = string

proc ReplaceAll(subject, target, repl: string): string
proc IsAbs(s: string): bool
proc join(s: openarray[string]): string
proc splitList(s: string): seq[string]
proc evalSymlinks(path: string): tuple[s: string, e: error]
proc abs(path: string): tuple[s: string, e: error]
proc Getwd(): tuple[s: string, e: error]
proc sameWord(a, b: string): bool
proc Count(a, b: string): int
proc copy(a, b: string): int {.discardable.}
proc Open(s: string): tuple[o: RootObj, e: error]
proc Readdirnames(o: RootObj, i: int): tuple[s: seq[string], e: error]
proc Close(o: RootObj)
proc sort(s: var seq[string])

proc IsPathSeparator*(c: char): bool
proc volumeNameLen*(s: string): int
proc index*(b: var lazybuf, i: int): char
proc append*(b: var lazybuf, c: char)
proc string*(b: var lazybuf): string
proc Clean*(ipath: string): string
proc ToSlash*(path: string): string
proc FromSlash*(path: string): string
proc SplitList*(path: string): seq[string]
proc Split*(path: string): tuple[dir, file: string]
proc Join*(elem: varargs[string]): string
proc Ext*(path: string): string
proc EvalSymlinks*(path: string): tuple[s: string, e: error]
proc Abs*(path: string): tuple[s: string, e: error]
proc unixAbs*(path: string): tuple[s: string, e: error]
proc Rel*(basepath, targpath: string): tuple[s: string, e: error]
# proc walk(path: string, info: os.FileInfo, walkFn: Walkproc): error
# proc Walk(root: string, walkFn: Walkproc): error
proc readDirNames*(dirname: string): tuple[s: seq[string], e: error]
proc Base*(path: string): string
proc Dir*(path: string): string
proc VolumeName*(path: string): string


proc index*(b: var lazybuf, i: int): char =
  if b.buf != "":
    return b.buf[i]

  return b.path[i]


proc append*(b: var lazybuf, c: char) =
  if b.buf == "":
    if b.w < len(b.path) and b.path[b.w] == c:
      b.w += 1
      return

    b.buf = newString(len(b.path))
    for i in 0 .. b.w-1:
      b.buf[i] = b.path[i]

  b.buf[b.w] = c
  b.w += 1


proc string*(b: var lazybuf): string =
  if b.buf == "":
    return b.volAndPath[.. (b.volLen+b.w-1)]

  return b.volAndPath[.. (b.volLen-1)] & b.buf[.. (b.w-1)]


const
  Separator*     = '/' # FIX
  ListSeparator* = ':' # FIX

# Clean returns the shortest path name equivalent to path
# by purely lexical processing. It applies the following rules
# iteratively until no further processing can be done:
#
#	1. Replace multiple Separator elements with a single one.
#	2. Eliminate each . path name element (the current directory).
#	3. Eliminate each inner .. path name element (the parent directory)
#	   along with the non-.. element that precedes it.
#	4. Eliminate .. elements that begin a rooted path:
#	   that is, replace "/.." by "/" at the beginning of a path,
#	   assuming Separator is '/'.
#
# The returned path ends in a slash only if it represents a root directory,
# such as "/" on Unix or `C:\` on Windows.
#
# Finally, any occurrences of slash are replaced by Separator.
#
# If the result of this process is an empty string, Clean
# returns the string ".".
#
# See also Rob Pike, ``Lexical File Names in Plan 9 or
# Getting Dot-Dot Right,''
# https:#9p.io/sys/doc/lexnames.html
proc Clean*(ipath: string): string =
  var
    originalPath = ipath
    volLen = volumeNameLen(ipath)
    path = ipath[volLen..^1]

  if path == "":
    if volLen > 1 and originalPath[1] != ':':
      # should be UNC
      return FromSlash(originalPath)

    return originalPath & "."

  var rooted = IsPathSeparator(path[0])

  # Invariants:
  #	reading from path; r is index of next char to process.
  #	writing to buf; w is index of next char to write.
  #	dotdot is index in buf where .. must stop, either because
  #		it is the leading slash or it is a leading ../../.. prefix.
  var
    n = len(path)
    res = lazybuf(path: path, volAndPath: originalPath, volLen: volLen)
    (r, dotdot) = (0, 0)

  if rooted:
    res.append(Separator)
    (r, dotdot) = (1, 1)

  while r < n:
    if IsPathSeparator(path[r]):
      # empty path element
      r += 1
    elif path[r] == '.' and (r+1 == n or IsPathSeparator(path[r+1])):
      # . element
      r += 1
    elif path[r] == '.' and path[r+1] == '.' and (r+2 == n or IsPathSeparator(path[r+2])):
      # .. element: remove to last separator
      r += 2
      if res.w > dotdot:
        # can backtrack
        res.w -= 1
        while res.w > dotdot and not IsPathSeparator(res.index(res.w)):
          res.w -= 1

      elif not rooted:
        # cannot backtrack, but not rooted, so append .. element.
        if res.w > 0:
          res.append(Separator)

        res.append('.')
        res.append('.')
        dotdot = res.w

    else:
      # real path element.
      # add slash if needed
      if rooted and res.w != 1 or not rooted and res.w != 0:
        res.append(Separator)

      # copy element
      while r < n and not IsPathSeparator(path[r]):
        res.append(path[r])
        r += 1

  # Turn empty string into "."
  if res.w == 0:
    res.append('.')

  return FromSlash(res.string())


# ToSlash returns the result of replacing each separator character
# in path with a slash ('/') character. Multiple separators are
# replaced by multiple slashes.
proc ToSlash*(path: string): string =
  if Separator == '/':
    return path

  return ReplaceAll(path, $Separator, "/")


# FromSlash returns the result of replacing each slash ('/') character
# in path with a separator character. Multiple slashes are replaced
# by multiple separators.
proc FromSlash*(path: string): string =
  if Separator == '/':
    return path

  return ReplaceAll(path, "/", $Separator)


# SplitList splits a list of paths joined by the OS-specific ListSeparator,
# usually found in PATH or GOPATH environment variables.
# Unlike strings.Split, SplitList returns an empty slice when passed an empty
# string.
proc SplitList*(path: string): seq[string] =
  return splitList(path) # UNDO


# Split splits path immediately following the final Separator,
# separating it into a directory and file name component.
# If there is no Separator in path, Split returns an empty dir
# and file set to path.
# The returned values have the property that path = dir+file.
proc Split*(path: string): tuple[dir, file: string] =
  var
    vol = VolumeName(path)
    i = len(path) - 1

  while i >= len(vol) and not IsPathSeparator(path[i]):
    i -= 1

  return (path[..i], path[i+1..^1])


# Join joins any number of path elements into a single path,
# separating them with an OS specific Separator. Empty elements
# are ignored. The result is Cleaned. However, if the argument
# list is empty or all its elements are empty, Join returns
# an empty string.
# On Windows, the result will only be a UNC path if the first
# non-empty element is a UNC path.
proc Join*(elem: varargs[string]): string =
  return join(elem)


# Ext returns the file name extension used by path.
# The extension is the suffix beginning at the final dot
# in the final element of path; it is empty if there is
# no dot.
proc Ext*(path: string): string =
  var i = len(path) - 1
  while i >= 0 and not IsPathSeparator(path[i]):
    if path[i] == '.':
      return path[i..^1]
    i -= 1

  return ""


# EvalSymlinks returns the path name after the evaluation of any symbolic
# links.
# If path is relative the result will be relative to the current directory,
# unless one of the components is an absolute symbolic link.
# EvalSymlinks calls Clean on the result.
proc EvalSymlinks*(path: string): tuple[s: string, e: error] =
  return evalSymlinks(path)


# Abs returns an absolute representation of path.
# If the path is not absolute it will be joined with the current
# working directory to turn it into an absolute path. The absolute
# path name for a given file is not guaranteed to be unique.
# Abs calls Clean on the result.
proc Abs*(path: string): tuple[s: string, e: error] =
  return abs(path)


proc unixAbs*(path: string): tuple[s: string, e: error] =
  if IsAbs(path):
    return (Clean(path), "")

  var (wd, err) = Getwd()
  if err != "":
    return ("", err)

  return (Join(wd, path), "")


# Rel returns a relative path that is lexically equivalent to targpath when
# joined to basepath with an intervening separator. That is,
# Join(basepath, Rel(basepath, targpath)) is equivalent to targpath itself.
# On success, the returned path will always be relative to basepath,
# even if basepath and targpath share no elements.
# An error is returned if targpath can't be made relative to basepath or if
# knowing the current working directory would be necessary to compute it.
# Rel calls Clean on the result.
proc Rel*(basepath, targpath: string): tuple[s: string, e: error] =
  var
    baseVol = VolumeName(basepath)
    targVol = VolumeName(targpath)
    base = Clean(basepath)
    targ = Clean(targpath)

  if sameWord(targ, base):
    return (".", "")

  base = base[len(baseVol)..^1]
  targ = targ[len(targVol)..^1]
  if base == ".":
    base = ""

  # Can't use IsAbs - `\a` and `a` are both relative in Windows.
  var
    baseSlashed = (len(base) > 0 and base[0] == Separator)
    targSlashed = (len(targ) > 0 and targ[0] == Separator)
  if baseSlashed != targSlashed or not sameWord(baseVol, targVol):
    return ("", "Rel: can't make " & targpath & " relative to " & basepath)

  # Position base[b0:bi] and targ[t0:ti] at the first differing elements.
  var
    bl = len(base)
    tl = len(targ)
    b0, bi, t0, ti: int

  while true:
    while bi < bl and base[bi] != Separator:
      bi += 1

    while ti < tl and targ[ti] != Separator:
      ti += 1

    if not sameWord(targ[t0..ti-1], base[b0..bi-1]):
      break

    if bi < bl:
      bi += 1

    if ti < tl:
      ti += 1

    b0 = bi
    t0 = ti

  if base[b0..bi-1] == "..":
    return ("", "Rel: can't make " & targpath & " relative to " & basepath)

  if b0 != bl:
    # Base elements left. Must go up before going down.
    var
      seps = Count(base[b0..bl-1], $Separator)
      size = 2 + seps*3
    if tl != t0:
      size += 1 + tl - t0

    var
      buf = newString(size)
      n = copy(buf, "..")
      i = 0

    while i < seps:
      buf[n] = Separator
      copy(buf[n+1..^1], "..")
      n += 3
      i += 1

    if t0 != tl:
      buf[n] = Separator
      copy(buf[n+1..^1], targ[t0..^1])

    return (buf, "")

  return (targ[t0..^1], "")


# SkipDir is used as a return value from Walkprocs to indicate that
# the directory named in the call is to be skipped. It is not returned
# as an error by any proction.
var SkipDir = "skip this directory"

# # Walkproc is the type of the proction called for each file or directory
# # visited by Walk. The path argument contains the argument to Walk as a
# # prefix; that is, if Walk is called with "dir", which is a directory
# # containing the file "a", the walk proction will be called with argument
# # "dir/a". The info argument is the os.FileInfo for the named path.
# #
# # If there was a problem walking to the file or directory named by path, the
# # incoming error will describe the problem and the proction can decide how
# # to handle that error (and Walk will not descend into that directory). In the
# # case of an error, the info argument will be nil. If an error is returned,
# # processing stops. The sole exception is when the proction returns the special
# # value SkipDir. If the proction returns SkipDir when invoked on a directory,
# # Walk skips the directory's contents entirely. If the proction returns SkipDir
# # when invoked on a non-directory file, Walk skips the remaining files in the
# # containing directory.
# type Walkproc = proc(path: string, info: os.FileInfo, err: error): error

# var lstat = os.Lstat # for testing

# # walk recursively descends path, calling walkFn.
# proc walk(path: string, info: os.FileInfo, walkFn: Walkproc): error =
#   if not info.IsDir():
#     return walkFn(path, info, nil)


#   var
#     (names, err) = readDirNames(path)
#     err1 = walkFn(path, info, err)
#   # If err != "", walk can't walk into this directory.
#   # err1 != nil means walkFn want walk to skip this directory or stop walking.
#   # Therefore, if one of err and err1 isn't nil, walk will return.
#   if err != "" or err1 != nil:
#     # The caller's behavior is controlled by the return value, which is decided
#     # by walkFn. walkFn may ignore err and return nil.
#     # If walkFn returns SkipDir, it will be handled by the caller.
#     # So walk should return whatever walkFn returns.
#     return err1


#   for name in names:
#     var
#       filename = Join(path, name)
#       fileInfo, err = lstat(filename)

#     if err != "":
#       var err = walkFn(filename, fileInfo, err)
#       if err != "" and err != SkipDir:
#         return err

#     else:
#       err = walk(filename, fileInfo, walkFn)
#       if err != "":
#         if not fileInfo.IsDir() or err != SkipDir:
#           return err

#   return nil


# # Walk walks the file tree rooted at root, calling walkFn for each file or
# # directory in the tree, including root. All errors that arise visiting files
# # and directories are filtered by walkFn. The files are walked in lexical
# # order, which makes the output deterministic but means that for very
# # large directories Walk can be inefficient.
# # Walk does not follow symbolic links.
# proc Walk(root: string, walkFn: Walkproc): error =
#   var (info, err) = os.Lstat(root)
#   if err != "":
#     err = walkFn(root, nil, err)
#  else:
#     err = walk(root, info, walkFn)

#   if err == SkipDir:
#     return nil

#   return err


# readDirNames reads the directory named by dirname and returns
# a sorted list of directory entries.
proc readDirNames(dirname: string): tuple[s: seq[string], e: error] =
  var (f, err) = Open(dirname)
  if err != "":
    return (@[], err)

  var (names, err2) = f.Readdirnames(-1)
  err = err2
  f.Close()
  if err != "":
    return (@[], err)

  sort(names)
  return (names, "")


# Base returns the last element of path.
# Trailing path separators are removed before extracting the last element.
# If the path is empty, Base returns ".".
# If the path consists entirely of separators, Base returns a single separator.
proc Base(ipath: string): string =
  var path = ipath
  if path == "":
    return "."

  # Strip trailing slashes.
  while len(path) > 0 and IsPathSeparator(path[len(path)-1]):
    path = path[0..len(path)-2]

  # Throw away volume name
  path = path[len(VolumeName(path))..^1]
  # Find the last element
  var i = len(path) - 1
  while i >= 0 and not IsPathSeparator(path[i]):
    i -= 1

  if i >= 0:
    path = path[i+1..^1]

  # If empty now, it had only slashes.
  if path == "":
    return $Separator

  return path


# Dir returns all but the last element of path, typically the path's directory.
# After dropping the final element, Dir calls Clean on the path and trailing
# slashes are removed.
# If the path is empty, Dir returns ".".
# If the path consists entirely of separators, Dir returns a single separator.
# The returned path does not end in a separator unless it is the root directory.
proc Dir(path: string): string =
  var
    vol = VolumeName(path)
    i = len(path) - 1

  while i >= len(vol) and not IsPathSeparator(path[i]):
    i -= 1


  var dir = Clean(path[len(vol) .. (i-1)])
  if dir == "." and len(vol) > 2:
    # must be UNC
    return vol

  return vol & dir


# VolumeName returns leading volume name.
# Given "C:\foo\bar" it returns "C:" on Windows.
# Given "\\host\share\foo" it returns "\\host\share".
# On other platforms it returns "".
proc VolumeName(path: string): string =
  return path[.. (volumeNameLen(path)-1)]