| 1 | // Copyright 2011 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 vfs |
| 6 | |
| 7 | import ( |
| 8 | "fmt" |
| 9 | "io" |
| 10 | "os" |
| 11 | pathpkg "path" |
| 12 | "sort" |
| 13 | "strings" |
| 14 | "time" |
| 15 | ) |
| 16 | |
| 17 | // Setting debugNS = true will enable debugging prints about |
| 18 | // name space translations. |
| 19 | const debugNS = false |
| 20 | |
| 21 | // A NameSpace is a file system made up of other file systems |
| 22 | // mounted at specific locations in the name space. |
| 23 | // |
| 24 | // The representation is a map from mount point locations |
| 25 | // to the list of file systems mounted at that location. A traditional |
| 26 | // Unix mount table would use a single file system per mount point, |
| 27 | // but we want to be able to mount multiple file systems on a single |
| 28 | // mount point and have the system behave as if the union of those |
| 29 | // file systems were present at the mount point. |
| 30 | // For example, if the OS file system has a Go installation in |
| 31 | // c:\Go and additional Go path trees in d:\Work1 and d:\Work2, then |
| 32 | // this name space creates the view we want for the godoc server: |
| 33 | // |
| 34 | // NameSpace{ |
| 35 | // "/": { |
| 36 | // {old: "/", fs: OS(`c:\Go`), new: "/"}, |
| 37 | // }, |
| 38 | // "/src/pkg": { |
| 39 | // {old: "/src/pkg", fs: OS(`c:\Go`), new: "/src/pkg"}, |
| 40 | // {old: "/src/pkg", fs: OS(`d:\Work1`), new: "/src"}, |
| 41 | // {old: "/src/pkg", fs: OS(`d:\Work2`), new: "/src"}, |
| 42 | // }, |
| 43 | // } |
| 44 | // |
| 45 | // This is created by executing: |
| 46 | // |
| 47 | // ns := NameSpace{} |
| 48 | // ns.Bind("/", OS(`c:\Go`), "/", BindReplace) |
| 49 | // ns.Bind("/src/pkg", OS(`d:\Work1`), "/src", BindAfter) |
| 50 | // ns.Bind("/src/pkg", OS(`d:\Work2`), "/src", BindAfter) |
| 51 | // |
| 52 | // A particular mount point entry is a triple (old, fs, new), meaning that to |
| 53 | // operate on a path beginning with old, replace that prefix (old) with new |
| 54 | // and then pass that path to the FileSystem implementation fs. |
| 55 | // |
| 56 | // If you do not explicitly mount a FileSystem at the root mountpoint "/" of the |
| 57 | // NameSpace like above, Stat("/") will return a "not found" error which could |
| 58 | // break typical directory traversal routines. In such cases, use NewNameSpace() |
| 59 | // to get a NameSpace pre-initialized with an emulated empty directory at root. |
| 60 | // |
| 61 | // Given this name space, a ReadDir of /src/pkg/code will check each prefix |
| 62 | // of the path for a mount point (first /src/pkg/code, then /src/pkg, then /src, |
| 63 | // then /), stopping when it finds one. For the above example, /src/pkg/code |
| 64 | // will find the mount point at /src/pkg: |
| 65 | // |
| 66 | // {old: "/src/pkg", fs: OS(`c:\Go`), new: "/src/pkg"}, |
| 67 | // {old: "/src/pkg", fs: OS(`d:\Work1`), new: "/src"}, |
| 68 | // {old: "/src/pkg", fs: OS(`d:\Work2`), new: "/src"}, |
| 69 | // |
| 70 | // ReadDir will when execute these three calls and merge the results: |
| 71 | // |
| 72 | // OS(`c:\Go`).ReadDir("/src/pkg/code") |
| 73 | // OS(`d:\Work1').ReadDir("/src/code") |
| 74 | // OS(`d:\Work2').ReadDir("/src/code") |
| 75 | // |
| 76 | // Note that the "/src/pkg" in "/src/pkg/code" has been replaced by |
| 77 | // just "/src" in the final two calls. |
| 78 | // |
| 79 | // OS is itself an implementation of a file system: it implements |
| 80 | // OS(`c:\Go`).ReadDir("/src/pkg/code") as ioutil.ReadDir(`c:\Go\src\pkg\code`). |
| 81 | // |
| 82 | // Because the new path is evaluated by fs (here OS(root)), another way |
| 83 | // to read the mount table is to mentally combine fs+new, so that this table: |
| 84 | // |
| 85 | // {old: "/src/pkg", fs: OS(`c:\Go`), new: "/src/pkg"}, |
| 86 | // {old: "/src/pkg", fs: OS(`d:\Work1`), new: "/src"}, |
| 87 | // {old: "/src/pkg", fs: OS(`d:\Work2`), new: "/src"}, |
| 88 | // |
| 89 | // reads as: |
| 90 | // |
| 91 | // "/src/pkg" -> c:\Go\src\pkg |
| 92 | // "/src/pkg" -> d:\Work1\src |
| 93 | // "/src/pkg" -> d:\Work2\src |
| 94 | // |
| 95 | // An invariant (a redundancy) of the name space representation is that |
| 96 | // ns[mtpt][i].old is always equal to mtpt (in the example, ns["/src/pkg"]'s |
| 97 | // mount table entries always have old == "/src/pkg"). The 'old' field is |
| 98 | // useful to callers, because they receive just a []mountedFS and not any |
| 99 | // other indication of which mount point was found. |
| 100 | type NameSpace map[string][]mountedFS |
| 101 | |
| 102 | // A mountedFS handles requests for path by replacing |
| 103 | // a prefix 'old' with 'new' and then calling the fs methods. |
| 104 | type mountedFS struct { |
| 105 | old string |
| 106 | fs FileSystem |
| 107 | new string |
| 108 | } |
| 109 | |
| 110 | // hasPathPrefix reports whether x == y or x == y + "/" + more. |
| 111 | func hasPathPrefix(x, y string) bool { |
| 112 | return x == y || strings.HasPrefix(x, y) && (strings.HasSuffix(y, "/") || strings.HasPrefix(x[len(y):], "/")) |
| 113 | } |
| 114 | |
| 115 | // translate translates path for use in m, replacing old with new. |
| 116 | // |
| 117 | // mountedFS{"/src/pkg", fs, "/src"}.translate("/src/pkg/code") == "/src/code". |
| 118 | func (m mountedFS) translate(path string) string { |
| 119 | path = pathpkg.Clean("/" + path) |
| 120 | if !hasPathPrefix(path, m.old) { |
| 121 | panic("translate " + path + " but old=" + m.old) |
| 122 | } |
| 123 | return pathpkg.Join(m.new, path[len(m.old):]) |
| 124 | } |
| 125 | |
| 126 | func (NameSpace) String() string { |
| 127 | return "ns" |
| 128 | } |
| 129 | |
| 130 | // Fprint writes a text representation of the name space to w. |
| 131 | func (ns NameSpace) Fprint(w io.Writer) { |
| 132 | fmt.Fprint(w, "name space {\n") |
| 133 | var all []string |
| 134 | for mtpt := range ns { |
| 135 | all = append(all, mtpt) |
| 136 | } |
| 137 | sort.Strings(all) |
| 138 | for _, mtpt := range all { |
| 139 | fmt.Fprintf(w, "\t%s:\n", mtpt) |
| 140 | for _, m := range ns[mtpt] { |
| 141 | fmt.Fprintf(w, "\t\t%s %s\n", m.fs, m.new) |
| 142 | } |
| 143 | } |
| 144 | fmt.Fprint(w, "}\n") |
| 145 | } |
| 146 | |
| 147 | // clean returns a cleaned, rooted path for evaluation. |
| 148 | // It canonicalizes the path so that we can use string operations |
| 149 | // to analyze it. |
| 150 | func (NameSpace) clean(path string) string { |
| 151 | return pathpkg.Clean("/" + path) |
| 152 | } |
| 153 | |
| 154 | type BindMode int |
| 155 | |
| 156 | const ( |
| 157 | BindReplace BindMode = iota |
| 158 | BindBefore |
| 159 | BindAfter |
| 160 | ) |
| 161 | |
| 162 | // Bind causes references to old to redirect to the path new in newfs. |
| 163 | // If mode is BindReplace, old redirections are discarded. |
| 164 | // If mode is BindBefore, this redirection takes priority over existing ones, |
| 165 | // but earlier ones are still consulted for paths that do not exist in newfs. |
| 166 | // If mode is BindAfter, this redirection happens only after existing ones |
| 167 | // have been tried and failed. |
| 168 | func (ns NameSpace) Bind(old string, newfs FileSystem, new string, mode BindMode) { |
| 169 | old = ns.clean(old) |
| 170 | new = ns.clean(new) |
| 171 | m := mountedFS{old, newfs, new} |
| 172 | var mtpt []mountedFS |
| 173 | switch mode { |
| 174 | case BindReplace: |
| 175 | mtpt = append(mtpt, m) |
| 176 | case BindAfter: |
| 177 | mtpt = append(mtpt, ns.resolve(old)...) |
| 178 | mtpt = append(mtpt, m) |
| 179 | case BindBefore: |
| 180 | mtpt = append(mtpt, m) |
| 181 | mtpt = append(mtpt, ns.resolve(old)...) |
| 182 | } |
| 183 | |
| 184 | // Extend m.old, m.new in inherited mount point entries. |
| 185 | for i := range mtpt { |
| 186 | m := &mtpt[i] |
| 187 | if m.old != old { |
| 188 | if !hasPathPrefix(old, m.old) { |
| 189 | // This should not happen. If it does, panic so |
| 190 | // that we can see the call trace that led to it. |
| 191 | panic(fmt.Sprintf("invalid Bind: old=%q m={%q, %s, %q}", old, m.old, m.fs.String(), m.new)) |
| 192 | } |
| 193 | suffix := old[len(m.old):] |
| 194 | m.old = pathpkg.Join(m.old, suffix) |
| 195 | m.new = pathpkg.Join(m.new, suffix) |
| 196 | } |
| 197 | } |
| 198 | |
| 199 | ns[old] = mtpt |
| 200 | } |
| 201 | |
| 202 | // resolve resolves a path to the list of mountedFS to use for path. |
| 203 | func (ns NameSpace) resolve(path string) []mountedFS { |
| 204 | path = ns.clean(path) |
| 205 | for { |
| 206 | if m := ns[path]; m != nil { |
| 207 | if debugNS { |
| 208 | fmt.Printf("resolve %s: %v\n", path, m) |
| 209 | } |
| 210 | return m |
| 211 | } |
| 212 | if path == "/" { |
| 213 | break |
| 214 | } |
| 215 | path = pathpkg.Dir(path) |
| 216 | } |
| 217 | return nil |
| 218 | } |
| 219 | |
| 220 | // Open implements the FileSystem Open method. |
| 221 | func (ns NameSpace) Open(path string) (ReadSeekCloser, error) { |
| 222 | var err error |
| 223 | for _, m := range ns.resolve(path) { |
| 224 | if debugNS { |
| 225 | fmt.Printf("tx %s: %v\n", path, m.translate(path)) |
| 226 | } |
| 227 | tp := m.translate(path) |
| 228 | r, err1 := m.fs.Open(tp) |
| 229 | if err1 == nil { |
| 230 | return r, nil |
| 231 | } |
| 232 | // IsNotExist errors in overlay FSes can mask real errors in |
| 233 | // the underlying FS, so ignore them if there is another error. |
| 234 | if err == nil || os.IsNotExist(err) { |
| 235 | err = err1 |
| 236 | } |
| 237 | } |
| 238 | if err == nil { |
| 239 | err = &os.PathError{Op: "open", Path: path, Err: os.ErrNotExist} |
| 240 | } |
| 241 | return nil, err |
| 242 | } |
| 243 | |
| 244 | // stat implements the FileSystem Stat and Lstat methods. |
| 245 | func (ns NameSpace) stat(path string, f func(FileSystem, string) (os.FileInfo, error)) (os.FileInfo, error) { |
| 246 | var err error |
| 247 | for _, m := range ns.resolve(path) { |
| 248 | fi, err1 := f(m.fs, m.translate(path)) |
| 249 | if err1 == nil { |
| 250 | return fi, nil |
| 251 | } |
| 252 | if err == nil { |
| 253 | err = err1 |
| 254 | } |
| 255 | } |
| 256 | if err == nil { |
| 257 | err = &os.PathError{Op: "stat", Path: path, Err: os.ErrNotExist} |
| 258 | } |
| 259 | return nil, err |
| 260 | } |
| 261 | |
| 262 | func (ns NameSpace) Stat(path string) (os.FileInfo, error) { |
| 263 | return ns.stat(path, FileSystem.Stat) |
| 264 | } |
| 265 | |
| 266 | func (ns NameSpace) Lstat(path string) (os.FileInfo, error) { |
| 267 | return ns.stat(path, FileSystem.Lstat) |
| 268 | } |
| 269 | |
| 270 | // dirInfo is a trivial implementation of os.FileInfo for a directory. |
| 271 | type dirInfo string |
| 272 | |
| 273 | func (d dirInfo) Name() string { return string(d) } |
| 274 | func (d dirInfo) Size() int64 { return 0 } |
| 275 | func (d dirInfo) Mode() os.FileMode { return os.ModeDir | 0555 } |
| 276 | func (d dirInfo) ModTime() time.Time { return startTime } |
| 277 | func (d dirInfo) IsDir() bool { return true } |
| 278 | func (d dirInfo) Sys() interface{} { return nil } |
| 279 | |
| 280 | var startTime = time.Now() |
| 281 | |
| 282 | // ReadDir implements the FileSystem ReadDir method. It's where most of the magic is. |
| 283 | // (The rest is in resolve.) |
| 284 | // |
| 285 | // Logically, ReadDir must return the union of all the directories that are named |
| 286 | // by path. In order to avoid misinterpreting Go packages, of all the directories |
| 287 | // that contain Go source code, we only include the files from the first, |
| 288 | // but we include subdirectories from all. |
| 289 | // |
| 290 | // ReadDir must also return directory entries needed to reach mount points. |
| 291 | // If the name space looks like the example in the type NameSpace comment, |
| 292 | // but c:\Go does not have a src/pkg subdirectory, we still want to be able |
| 293 | // to find that subdirectory, because we've mounted d:\Work1 and d:\Work2 |
| 294 | // there. So if we don't see "src" in the directory listing for c:\Go, we add an |
| 295 | // entry for it before returning. |
| 296 | func (ns NameSpace) ReadDir(path string) ([]os.FileInfo, error) { |
| 297 | path = ns.clean(path) |
| 298 | |
| 299 | // List matching directories and determine whether any of them contain |
| 300 | // Go files. |
| 301 | var ( |
| 302 | dirs [][]os.FileInfo |
| 303 | goDirIndex = -1 |
| 304 | readDirErr error |
| 305 | ) |
| 306 | |
| 307 | for _, m := range ns.resolve(path) { |
| 308 | dir, err := m.fs.ReadDir(m.translate(path)) |
| 309 | if err != nil { |
| 310 | if readDirErr == nil { |
| 311 | readDirErr = err |
| 312 | } |
| 313 | continue |
| 314 | } |
| 315 | |
| 316 | dirs = append(dirs, dir) |
| 317 | |
| 318 | if goDirIndex < 0 { |
| 319 | for _, f := range dir { |
| 320 | if !f.IsDir() && strings.HasSuffix(f.Name(), ".go") { |
| 321 | goDirIndex = len(dirs) - 1 |
| 322 | break |
| 323 | } |
| 324 | } |
| 325 | } |
| 326 | } |
| 327 | |
| 328 | // Build a list of files and subdirectories. If a directory contains Go files, |
| 329 | // only include files from that directory. Otherwise, include files from |
| 330 | // all directories. Include subdirectories from all directories regardless |
| 331 | // of whether Go files are present. |
| 332 | haveName := make(map[string]bool) |
| 333 | var all []os.FileInfo |
| 334 | for i, dir := range dirs { |
| 335 | for _, f := range dir { |
| 336 | name := f.Name() |
| 337 | if !haveName[name] && (f.IsDir() || goDirIndex < 0 || goDirIndex == i) { |
| 338 | all = append(all, f) |
| 339 | haveName[name] = true |
| 340 | } |
| 341 | } |
| 342 | } |
| 343 | |
| 344 | // Add any missing directories needed to reach mount points. |
| 345 | for old := range ns { |
| 346 | if hasPathPrefix(old, path) && old != path { |
| 347 | // Find next element after path in old. |
| 348 | elem := old[len(path):] |
| 349 | elem = strings.TrimPrefix(elem, "/") |
| 350 | if i := strings.Index(elem, "/"); i >= 0 { |
| 351 | elem = elem[:i] |
| 352 | } |
| 353 | if !haveName[elem] { |
| 354 | haveName[elem] = true |
| 355 | all = append(all, dirInfo(elem)) |
| 356 | } |
| 357 | } |
| 358 | } |
| 359 | |
| 360 | if len(all) == 0 { |
| 361 | return nil, readDirErr |
| 362 | } |
| 363 | |
| 364 | sort.Sort(byName(all)) |
| 365 | return all, nil |
| 366 | } |
| 367 | |
| 368 | // RootType returns the RootType for the given path in the namespace. |
| 369 | func (ns NameSpace) RootType(path string) RootType { |
| 370 | // We resolve the given path to a list of mountedFS and then return |
| 371 | // the root type for the filesystem which contains the path. |
| 372 | for _, m := range ns.resolve(path) { |
| 373 | _, err := m.fs.ReadDir(m.translate(path)) |
| 374 | // Found a match, return the filesystem's root type |
| 375 | if err == nil { |
| 376 | return m.fs.RootType(path) |
| 377 | } |
| 378 | } |
| 379 | return "" |
| 380 | } |
| 381 | |
| 382 | // byName implements sort.Interface. |
| 383 | type byName []os.FileInfo |
| 384 | |
| 385 | func (f byName) Len() int { return len(f) } |
| 386 | func (f byName) Less(i, j int) bool { return f[i].Name() < f[j].Name() } |
| 387 | func (f byName) Swap(i, j int) { f[i], f[j] = f[j], f[i] } |
| 388 |
Members