libgo/go/path/filepath/path.go

   1 // Copyright 2009 The Go Authors. All rights reserved.
   2 // Use of this source code is governed by a BSD-style
   3 // license that can be found in the LICENSE file.
   4
   5 // Package filepath implements utility routines for manipulating filename paths
   6 // in a way compatible with the target operating system-defined file paths.
   7 package filepath
   8
   9 import (
  10         "errors"
  11         "os"
  12         "sort"
  13         "strings"
  14 )
  15
  16 const (
  17         Separator     = os.PathSeparator
  18         ListSeparator = os.PathListSeparator
  19 )
  20
  21 // Clean returns the shortest path name equivalent to path
  22 // by purely lexical processing.  It applies the following rules
  23 // iteratively until no further processing can be done:
  24 //
  25 //      1. Replace multiple Separator elements with a single one.
  26 //      2. Eliminate each . path name element (the current directory).
  27 //      3. Eliminate each inner .. path name element (the parent directory)
  28 //         along with the non-.. element that precedes it.
  29 //      4. Eliminate .. elements that begin a rooted path:
  30 //         that is, replace "/.." by "/" at the beginning of a path,
  31 //         assuming Separator is '/'.
  32 //
  33 // If the result of this process is an empty string, Clean
  34 // returns the string ".".
  35 //
  36 // See also Rob Pike, ``Lexical File Names in Plan 9 or
  37 // Getting Dot-Dot Right,''
  38 // http://plan9.bell-labs.com/sys/doc/lexnames.html
  39 func Clean(path string) string {
  40         vol := VolumeName(path)
  41         path = path[len(vol):]
  42         if path == "" {
  43                 if len(vol) > 1 && vol[1] != ':' {
  44                         // should be UNC
  45                         return FromSlash(vol)
  46                 }
  47                 return vol + "."
  48         }
  49         rooted := os.IsPathSeparator(path[0])
  50
  51         // Invariants:
  52         //      reading from path; r is index of next byte to process.
  53         //      writing to buf; w is index of next byte to write.
  54         //      dotdot is index in buf where .. must stop, either because
  55         //              it is the leading slash or it is a leading ../../.. prefix.
  56         n := len(path)
  57         buf := []byte(path)
  58         r, w, dotdot := 0, 0, 0
  59         if rooted {
  60                 buf[0] = Separator
  61                 r, w, dotdot = 1, 1, 1
  62         }
  63
  64         for r < n {
  65                 switch {
  66                 case os.IsPathSeparator(path[r]):
  67                         // empty path element
  68                         r++
  69                 case path[r] == '.' && (r+1 == n || os.IsPathSeparator(path[r+1])):
  70                         // . element
  71                         r++
  72                 case path[r] == '.' && path[r+1] == '.' && (r+2 == n || os.IsPathSeparator(path[r+2])):
  73                         // .. element: remove to last separator
  74                         r += 2
  75                         switch {
  76                         case w > dotdot:
  77                                 // can backtrack
  78                                 w--
  79                                 for w > dotdot && !os.IsPathSeparator(buf[w]) {
  80                                         w--
  81                                 }
  82                         case !rooted:
  83                                 // cannot backtrack, but not rooted, so append .. element.
  84                                 if w > 0 {
  85                                         buf[w] = Separator
  86                                         w++
  87                                 }
  88                                 buf[w] = '.'
  89                                 w++
  90                                 buf[w] = '.'
  91                                 w++
  92                                 dotdot = w
  93                         }
  94                 default:
  95                         // real path element.
  96                         // add slash if needed
  97                         if rooted && w != 1 || !rooted && w != 0 {
  98                                 buf[w] = Separator
  99                                 w++
 100                         }
 101                         // copy element
 102                         for ; r < n && !os.IsPathSeparator(path[r]); r++ {
 103                                 buf[w] = path[r]
 104                                 w++
 105                         }
 106                 }
 107         }
 108
 109         // Turn empty string into "."
 110         if w == 0 {
 111                 buf[w] = '.'
 112                 w++
 113         }
 114
 115         return FromSlash(vol + string(buf[0:w]))
 116 }
 117
 118 // ToSlash returns the result of replacing each separator character
 119 // in path with a slash ('/') character. Multiple separators are
 120 // replaced by multiple slashes.
 121 func ToSlash(path string) string {
 122         if Separator == '/' {
 123                 return path
 124         }
 125         return strings.Replace(path, string(Separator), "/", -1)
 126 }
 127
 128 // FromSlash returns the result of replacing each slash ('/') character
 129 // in path with a separator character. Multiple slashes are replaced
 130 // by multiple separators.
 131 func FromSlash(path string) string {
 132         if Separator == '/' {
 133                 return path
 134         }
 135         return strings.Replace(path, "/", string(Separator), -1)
 136 }
 137
 138 // SplitList splits a list of paths joined by the OS-specific ListSeparator,
 139 // usually found in PATH or GOPATH environment variables.
 140 // Unlike strings.Split, SplitList returns an empty slice when passed an empty string.
 141 func SplitList(path string) []string {
 142         if path == "" {
 143                 return []string{}
 144         }
 145         return strings.Split(path, string(ListSeparator))
 146 }
 147
 148 // Split splits path immediately following the final Separator,
 149 // separating it into a directory and file name component.
 150 // If there is no Separator in path, Split returns an empty dir
 151 // and file set to path.
 152 // The returned values have the property that path = dir+file.
 153 func Split(path string) (dir, file string) {
 154         vol := VolumeName(path)
 155         i := len(path) - 1
 156         for i >= len(vol) && !os.IsPathSeparator(path[i]) {
 157                 i--
 158         }
 159         return path[:i+1], path[i+1:]
 160 }
 161
 162 // Join joins any number of path elements into a single path, adding
 163 // a Separator if necessary. The result is Cleaned, in particular
 164 // all empty strings are ignored.
 165 func Join(elem ...string) string {
 166         for i, e := range elem {
 167                 if e != "" {
 168                         return Clean(strings.Join(elem[i:], string(Separator)))
 169                 }
 170         }
 171         return ""
 172 }
 173
 174 // Ext returns the file name extension used by path.
 175 // The extension is the suffix beginning at the final dot
 176 // in the final element of path; it is empty if there is
 177 // no dot.
 178 func Ext(path string) string {
 179         for i := len(path) - 1; i >= 0 && !os.IsPathSeparator(path[i]); i-- {
 180                 if path[i] == '.' {
 181                         return path[i:]
 182                 }
 183         }
 184         return ""
 185 }
 186
 187 // EvalSymlinks returns the path name after the evaluation of any symbolic
 188 // links.
 189 // If path is relative the result will be relative to the current directory,
 190 // unless one of the components is an absolute symbolic link.
 191 func EvalSymlinks(path string) (string, error) {
 192         return evalSymlinks(path)
 193 }
 194
 195 // Abs returns an absolute representation of path.
 196 // If the path is not absolute it will be joined with the current
 197 // working directory to turn it into an absolute path.  The absolute
 198 // path name for a given file is not guaranteed to be unique.
 199 func Abs(path string) (string, error) {
 200         if IsAbs(path) {
 201                 return Clean(path), nil
 202         }
 203         wd, err := os.Getwd()
 204         if err != nil {
 205                 return "", err
 206         }
 207         return Join(wd, path), nil
 208 }
 209
 210 // Rel returns a relative path that is lexically equivalent to targpath when
 211 // joined to basepath with an intervening separator. That is,
 212 // Join(basepath, Rel(basepath, targpath)) is equivalent to targpath itself.
 213 // On success, the returned path will always be relative to basepath,
 214 // even if basepath and targpath share no elements.
 215 // An error is returned if targpath can't be made relative to basepath or if
 216 // knowing the current working directory would be necessary to compute it.
 217 func Rel(basepath, targpath string) (string, error) {
 218         baseVol := VolumeName(basepath)
 219         targVol := VolumeName(targpath)
 220         base := Clean(basepath)
 221         targ := Clean(targpath)
 222         if targ == base {
 223                 return ".", nil
 224         }
 225         base = base[len(baseVol):]
 226         targ = targ[len(targVol):]
 227         if base == "." {
 228                 base = ""
 229         }
 230         // Can't use IsAbs - `\a` and `a` are both relative in Windows.
 231         baseSlashed := len(base) > 0 && base[0] == Separator
 232         targSlashed := len(targ) > 0 && targ[0] == Separator
 233         if baseSlashed != targSlashed || baseVol != targVol {
 234                 return "", errors.New("Rel: can't make " + targ + " relative to " + base)
 235         }
 236         // Position base[b0:bi] and targ[t0:ti] at the first differing elements.
 237         bl := len(base)
 238         tl := len(targ)
 239         var b0, bi, t0, ti int
 240         for {
 241                 for bi < bl && base[bi] != Separator {
 242                         bi++
 243                 }
 244                 for ti < tl && targ[ti] != Separator {
 245                         ti++
 246                 }
 247                 if targ[t0:ti] != base[b0:bi] {
 248                         break
 249                 }
 250                 if bi < bl {
 251                         bi++
 252                 }
 253                 if ti < tl {
 254                         ti++
 255                 }
 256                 b0 = bi
 257                 t0 = ti
 258         }
 259         if base[b0:bi] == ".." {
 260                 return "", errors.New("Rel: can't make " + targ + " relative to " + base)
 261         }
 262         if b0 != bl {
 263                 // Base elements left. Must go up before going down.
 264                 seps := strings.Count(base[b0:bl], string(Separator))
 265                 size := 2 + seps*3
 266                 if tl != t0 {
 267                         size += 1 + tl - t0
 268                 }
 269                 buf := make([]byte, size)
 270                 n := copy(buf, "..")
 271                 for i := 0; i < seps; i++ {
 272                         buf[n] = Separator
 273                         copy(buf[n+1:], "..")
 274                         n += 3
 275                 }
 276                 if t0 != tl {
 277                         buf[n] = Separator
 278                         copy(buf[n+1:], targ[t0:])
 279                 }
 280                 return string(buf), nil
 281         }
 282         return targ[t0:], nil
 283 }
 284
 285 // SkipDir is used as a return value from WalkFuncs to indicate that
 286 // the directory named in the call is to be skipped. It is not returned
 287 // as an error by any function.
 288 var SkipDir = errors.New("skip this directory")
 289
 290 // WalkFunc is the type of the function called for each file or directory
 291 // visited by Walk.  If there was a problem walking to the file or directory
 292 // named by path, the incoming error will describe the problem and the
 293 // function can decide how to handle that error (and Walk will not descend
 294 // into that directory).  If an error is returned, processing stops.  The
 295 // sole exception is that if path is a directory and the function returns the
 296 // special value SkipDir, the contents of the directory are skipped
 297 // and processing continues as usual on the next file.
 298 type WalkFunc func(path string, info os.FileInfo, err error) error
 299
 300 // walk recursively descends path, calling w.
 301 func walk(path string, info os.FileInfo, walkFn WalkFunc) error {
 302         err := walkFn(path, info, nil)
 303         if err != nil {
 304                 if info.IsDir() && err == SkipDir {
 305                         return nil
 306                 }
 307                 return err
 308         }
 309
 310         if !info.IsDir() {
 311                 return nil
 312         }
 313
 314         list, err := readDir(path)
 315         if err != nil {
 316                 return walkFn(path, info, err)
 317         }
 318
 319         for _, fileInfo := range list {
 320                 if err = walk(Join(path, fileInfo.Name()), fileInfo, walkFn); err != nil {
 321                         return err
 322                 }
 323         }
 324         return nil
 325 }
 326
 327 // Walk walks the file tree rooted at root, calling walkFn for each file or
 328 // directory in the tree, including root. All errors that arise visiting files
 329 // and directories are filtered by walkFn. The files are walked in lexical
 330 // order, which makes the output deterministic but means that for very
 331 // large directories Walk can be inefficient.
 332 func Walk(root string, walkFn WalkFunc) error {
 333         info, err := os.Lstat(root)
 334         if err != nil {
 335                 return walkFn(root, nil, err)
 336         }
 337         return walk(root, info, walkFn)
 338 }
 339
 340 // readDir reads the directory named by dirname and returns
 341 // a sorted list of directory entries.
 342 // Copied from io/ioutil to avoid the circular import.
 343 func readDir(dirname string) ([]os.FileInfo, error) {
 344         f, err := os.Open(dirname)
 345         if err != nil {
 346                 return nil, err
 347         }
 348         list, err := f.Readdir(-1)
 349         f.Close()
 350         if err != nil {
 351                 return nil, err
 352         }
 353         sort.Sort(byName(list))
 354         return list, nil
 355 }
 356
 357 // byName implements sort.Interface.
 358 type byName []os.FileInfo
 359
 360 func (f byName) Len() int           { return len(f) }
 361 func (f byName) Less(i, j int) bool { return f[i].Name() < f[j].Name() }
 362 func (f byName) Swap(i, j int)      { f[i], f[j] = f[j], f[i] }
 363
 364 // Base returns the last element of path.
 365 // Trailing path separators are removed before extracting the last element.
 366 // If the path is empty, Base returns ".".
 367 // If the path consists entirely of separators, Base returns a single separator.
 368 func Base(path string) string {
 369         if path == "" {
 370                 return "."
 371         }
 372         // Strip trailing slashes.
 373         for len(path) > 0 && os.IsPathSeparator(path[len(path)-1]) {
 374                 path = path[0 : len(path)-1]
 375         }
 376         // Throw away volume name
 377         path = path[len(VolumeName(path)):]
 378         // Find the last element
 379         i := len(path) - 1
 380         for i >= 0 && !os.IsPathSeparator(path[i]) {
 381                 i--
 382         }
 383         if i >= 0 {
 384                 path = path[i+1:]
 385         }
 386         // If empty now, it had only slashes.
 387         if path == "" {
 388                 return string(Separator)
 389         }
 390         return path
 391 }
 392
 393 // Dir returns all but the last element of path, typically the path's directory.
 394 // Trailing path separators are removed before processing.
 395 // If the path is empty, Dir returns ".".
 396 // If the path consists entirely of separators, Dir returns a single separator.
 397 // The returned path does not end in a separator unless it is the root directory.
 398 func Dir(path string) string {
 399         vol := VolumeName(path)
 400         i := len(path) - 1
 401         for i >= len(vol) && !os.IsPathSeparator(path[i]) {
 402                 i--
 403         }
 404         dir := Clean(path[len(vol) : i+1])
 405         last := len(dir) - 1
 406         if last > 0 && os.IsPathSeparator(dir[last]) {
 407                 dir = dir[:last]
 408         }
 409         if dir == "" {
 410                 dir = "."
 411         }
 412         return vol + dir
 413 }