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 5package vfs 6 7import ( 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. 19const 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// 101type NameSpace map[string][]mountedFS 102 103// A mountedFS handles requests for path by replacing 104// a prefix 'old' with 'new' and then calling the fs methods. 105type mountedFS struct { 106 old string 107 fs FileSystem 108 new string 109} 110 111// hasPathPrefix returns true if x == y or x == y + "/" + more 112func hasPathPrefix(x, y string) bool { 113 return x == y || strings.HasPrefix(x, y) && (strings.HasSuffix(y, "/") || strings.HasPrefix(x[len(y):], "/")) 114} 115 116// translate translates path for use in m, replacing old with new. 117// 118// mountedFS{"/src/pkg", fs, "/src"}.translate("/src/pkg/code") == "/src/code". 119func (m mountedFS) translate(path string) string { 120 path = pathpkg.Clean("/" + path) 121 if !hasPathPrefix(path, m.old) { 122 panic("translate " + path + " but old=" + m.old) 123 } 124 return pathpkg.Join(m.new, path[len(m.old):]) 125} 126 127func (NameSpace) String() string { 128 return "ns" 129} 130 131// Fprint writes a text representation of the name space to w. 132func (ns NameSpace) Fprint(w io.Writer) { 133 fmt.Fprint(w, "name space {\n") 134 var all []string 135 for mtpt := range ns { 136 all = append(all, mtpt) 137 } 138 sort.Strings(all) 139 for _, mtpt := range all { 140 fmt.Fprintf(w, "\t%s:\n", mtpt) 141 for _, m := range ns[mtpt] { 142 fmt.Fprintf(w, "\t\t%s %s\n", m.fs, m.new) 143 } 144 } 145 fmt.Fprint(w, "}\n") 146} 147 148// clean returns a cleaned, rooted path for evaluation. 149// It canonicalizes the path so that we can use string operations 150// to analyze it. 151func (NameSpace) clean(path string) string { 152 return pathpkg.Clean("/" + path) 153} 154 155type BindMode int 156 157const ( 158 BindReplace BindMode = iota 159 BindBefore 160 BindAfter 161) 162 163// Bind causes references to old to redirect to the path new in newfs. 164// If mode is BindReplace, old redirections are discarded. 165// If mode is BindBefore, this redirection takes priority over existing ones, 166// but earlier ones are still consulted for paths that do not exist in newfs. 167// If mode is BindAfter, this redirection happens only after existing ones 168// have been tried and failed. 169func (ns NameSpace) Bind(old string, newfs FileSystem, new string, mode BindMode) { 170 old = ns.clean(old) 171 new = ns.clean(new) 172 m := mountedFS{old, newfs, new} 173 var mtpt []mountedFS 174 switch mode { 175 case BindReplace: 176 mtpt = append(mtpt, m) 177 case BindAfter: 178 mtpt = append(mtpt, ns.resolve(old)...) 179 mtpt = append(mtpt, m) 180 case BindBefore: 181 mtpt = append(mtpt, m) 182 mtpt = append(mtpt, ns.resolve(old)...) 183 } 184 185 // Extend m.old, m.new in inherited mount point entries. 186 for i := range mtpt { 187 m := &mtpt[i] 188 if m.old != old { 189 if !hasPathPrefix(old, m.old) { 190 // This should not happen. If it does, panic so 191 // that we can see the call trace that led to it. 192 panic(fmt.Sprintf("invalid Bind: old=%q m={%q, %s, %q}", old, m.old, m.fs.String(), m.new)) 193 } 194 suffix := old[len(m.old):] 195 m.old = pathpkg.Join(m.old, suffix) 196 m.new = pathpkg.Join(m.new, suffix) 197 } 198 } 199 200 ns[old] = mtpt 201} 202 203// resolve resolves a path to the list of mountedFS to use for path. 204func (ns NameSpace) resolve(path string) []mountedFS { 205 path = ns.clean(path) 206 for { 207 if m := ns[path]; m != nil { 208 if debugNS { 209 fmt.Printf("resolve %s: %v\n", path, m) 210 } 211 return m 212 } 213 if path == "/" { 214 break 215 } 216 path = pathpkg.Dir(path) 217 } 218 return nil 219} 220 221// Open implements the FileSystem Open method. 222func (ns NameSpace) Open(path string) (ReadSeekCloser, error) { 223 var err error 224 for _, m := range ns.resolve(path) { 225 if debugNS { 226 fmt.Printf("tx %s: %v\n", path, m.translate(path)) 227 } 228 tp := m.translate(path) 229 r, err1 := m.fs.Open(tp) 230 if err1 == nil { 231 return r, nil 232 } 233 // IsNotExist errors in overlay FSes can mask real errors in 234 // the underlying FS, so ignore them if there is another error. 235 if err == nil || os.IsNotExist(err) { 236 err = err1 237 } 238 } 239 if err == nil { 240 err = &os.PathError{Op: "open", Path: path, Err: os.ErrNotExist} 241 } 242 return nil, err 243} 244 245// stat implements the FileSystem Stat and Lstat methods. 246func (ns NameSpace) stat(path string, f func(FileSystem, string) (os.FileInfo, error)) (os.FileInfo, error) { 247 var err error 248 for _, m := range ns.resolve(path) { 249 fi, err1 := f(m.fs, m.translate(path)) 250 if err1 == nil { 251 return fi, nil 252 } 253 if err == nil { 254 err = err1 255 } 256 } 257 if err == nil { 258 err = &os.PathError{Op: "stat", Path: path, Err: os.ErrNotExist} 259 } 260 return nil, err 261} 262 263func (ns NameSpace) Stat(path string) (os.FileInfo, error) { 264 return ns.stat(path, FileSystem.Stat) 265} 266 267func (ns NameSpace) Lstat(path string) (os.FileInfo, error) { 268 return ns.stat(path, FileSystem.Lstat) 269} 270 271// dirInfo is a trivial implementation of os.FileInfo for a directory. 272type dirInfo string 273 274func (d dirInfo) Name() string { return string(d) } 275func (d dirInfo) Size() int64 { return 0 } 276func (d dirInfo) Mode() os.FileMode { return os.ModeDir | 0555 } 277func (d dirInfo) ModTime() time.Time { return startTime } 278func (d dirInfo) IsDir() bool { return true } 279func (d dirInfo) Sys() interface{} { return nil } 280 281var startTime = time.Now() 282 283// ReadDir implements the FileSystem ReadDir method. It's where most of the magic is. 284// (The rest is in resolve.) 285// 286// Logically, ReadDir must return the union of all the directories that are named 287// by path. In order to avoid misinterpreting Go packages, of all the directories 288// that contain Go source code, we only include the files from the first, 289// but we include subdirectories from all. 290// 291// ReadDir must also return directory entries needed to reach mount points. 292// If the name space looks like the example in the type NameSpace comment, 293// but c:\Go does not have a src/pkg subdirectory, we still want to be able 294// to find that subdirectory, because we've mounted d:\Work1 and d:\Work2 295// there. So if we don't see "src" in the directory listing for c:\Go, we add an 296// entry for it before returning. 297// 298func (ns NameSpace) ReadDir(path string) ([]os.FileInfo, error) { 299 path = ns.clean(path) 300 301 var ( 302 haveGo = false 303 haveName = map[string]bool{} 304 all []os.FileInfo 305 err error 306 first []os.FileInfo 307 ) 308 309 for _, m := range ns.resolve(path) { 310 dir, err1 := m.fs.ReadDir(m.translate(path)) 311 if err1 != nil { 312 if err == nil { 313 err = err1 314 } 315 continue 316 } 317 318 if dir == nil { 319 dir = []os.FileInfo{} 320 } 321 322 if first == nil { 323 first = dir 324 } 325 326 // If we don't yet have Go files in 'all' and this directory 327 // has some, add all the files from this directory. 328 // Otherwise, only add subdirectories. 329 useFiles := false 330 if !haveGo { 331 for _, d := range dir { 332 if strings.HasSuffix(d.Name(), ".go") { 333 useFiles = true 334 haveGo = true 335 break 336 } 337 } 338 } 339 340 for _, d := range dir { 341 name := d.Name() 342 if (d.IsDir() || useFiles) && !haveName[name] { 343 haveName[name] = true 344 all = append(all, d) 345 } 346 } 347 } 348 349 // We didn't find any directories containing Go files. 350 // If some directory returned successfully, use that. 351 if !haveGo { 352 for _, d := range first { 353 if !haveName[d.Name()] { 354 haveName[d.Name()] = true 355 all = append(all, d) 356 } 357 } 358 } 359 360 // Built union. Add any missing directories needed to reach mount points. 361 for old := range ns { 362 if hasPathPrefix(old, path) && old != path { 363 // Find next element after path in old. 364 elem := old[len(path):] 365 elem = strings.TrimPrefix(elem, "/") 366 if i := strings.Index(elem, "/"); i >= 0 { 367 elem = elem[:i] 368 } 369 if !haveName[elem] { 370 haveName[elem] = true 371 all = append(all, dirInfo(elem)) 372 } 373 } 374 } 375 376 if len(all) == 0 { 377 return nil, err 378 } 379 380 sort.Sort(byName(all)) 381 return all, nil 382} 383 384// RootType returns the RootType for the given path in the namespace. 385func (ns NameSpace) RootType(path string) RootType { 386 // We resolve the given path to a list of mountedFS and then return 387 // the root type for the filesystem which contains the path. 388 for _, m := range ns.resolve(path) { 389 _, err := m.fs.ReadDir(m.translate(path)) 390 // Found a match, return the filesystem's root type 391 if err == nil { 392 return m.fs.RootType(path) 393 } 394 } 395 return "" 396} 397 398// byName implements sort.Interface. 399type byName []os.FileInfo 400 401func (f byName) Len() int { return len(f) } 402func (f byName) Less(i, j int) bool { return f[i].Name() < f[j].Name() } 403func (f byName) Swap(i, j int) { f[i], f[j] = f[j], f[i] } 404