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