ns.gno
13.38 Kb · 489 lines
1// Package ns is a Plan 9 namespace: a private, mutable mount table over
2// gno.land/p/moul/x/plan9/ninep file trees.
3//
4// This is the idea the rest of the suite exists for. Plan 9's leverage does
5// not come from "everything is a file", it comes from every process owning its
6// own name-to-resource mapping, so a name can be REPLACED and any service can
7// be composed, shadowed, sandboxed or mocked without the program knowing. Gno
8// has one global tree and no way to hold a view of it; an Ns is that view.
9//
10// Bind flags follow bind(2): MREPL replaces, MBEFORE splices the new directory
11// in front of the old one, MAFTER behind it, and MCREATE (OR'd onto any of
12// them) marks the union member that new files are created in.
13//
14// Two Plan 9 properties are load-bearing and reproduced deliberately:
15//
16// - A union is TOP LEVEL ONLY. Binding /a onto /b unions the two directories
17// at /b; /b/c resolves in whichever member won the walk, and is not itself
18// a union unless something is bound there too.
19// - A bind captures a CHANNEL, not a name. The source is resolved once, at
20// bind time, and the resulting file is what is stored. Rebinding the
21// source afterwards does not retroactively move the target.
22//
23// ".." is removed lexically before resolution starts and never reaches a
24// server, per "Lexical File Names in Plan 9, or Getting Dot-Dot Right".
25//
26// NOTICE. Plan 9 from Bell Labs is the work of the Computing Science Research
27// Center at Bell Labs; the name and the marks are theirs, and the copyright is
28// held by the Plan 9 Foundation (https://p9f.org). This package is not
29// affiliated with, endorsed by, or sponsored by them, and contains no Plan 9
30// code: it borrows the vocabulary so that the design reads without a glossary,
31// and it is an homage, asking what that ecosystem's spirit looks like on a
32// chain. Full attribution: NOTICE.md at the root of moul/gno-contracts.
33package ns
34
35import (
36 "errors"
37 "strings"
38
39 "gno.land/p/nt/avl/v0"
40
41 ninep "gno.land/p/moul/x/plan9/ninep/v0"
42)
43
44// Flag is a bind(2) mount flag. The low two bits pick the mode; MCREATE is
45// OR'd onto it.
46type Flag uint32
47
48// Mount flags, with Plan 9's values.
49const (
50 MREPL Flag = 0x0000 // replace the old file with the new one
51 MBEFORE Flag = 0x0001 // union, new directory first
52 MAFTER Flag = 0x0002 // union, new directory last
53 MCREATE Flag = 0x0004 // creates in this union go here
54)
55
56func (f Flag) mode() Flag { return f & 0x0003 }
57func (f Flag) creates() bool { return f&MCREATE != 0 }
58
59// String renders the flag as the command-line letters bind(1) uses.
60func (f Flag) String() string {
61 s := ""
62 switch f.mode() {
63 case MBEFORE:
64 s = "-b"
65 case MAFTER:
66 s = "-a"
67 }
68 if f.creates() {
69 if s == "" {
70 s = "-c"
71 } else {
72 s += "c"
73 }
74 }
75 return s
76}
77
78// Limits. Resolution costs one call per element per union member, and those
79// calls may cross a realm boundary, so both are capped rather than trusted.
80const (
81 MaxUnion = 8 // members in one union
82 MaxOps = 64
83)
84
85var (
86 // ErrNoRoot means the namespace has nothing bound at "/".
87 ErrNoRoot = errors.New("no root in namespace")
88 // ErrWideUnion means a bind would exceed MaxUnion members.
89 ErrWideUnion = errors.New("union too wide")
90 // ErrTooManyOps means the namespace has reached MaxOps bindings.
91 ErrTooManyOps = errors.New("too many namespace operations")
92 // ErrNotBound means unmount was asked to remove something that is not
93 // bound at that name.
94 ErrNotBound = errors.New("not bound")
95)
96
97// member is one element of a union. A nil file is the placeholder standing for
98// "whatever walking to this name would have found", which is how MBEFORE and
99// MAFTER keep the original directory in the union.
100type member struct {
101 file ninep.File
102 create bool
103}
104
105type entry struct {
106 members []member
107}
108
109// Op records one bind or mount, in application order, so that String can print
110// the namespace the way Plan 9's ns(1) does.
111type Op struct {
112 Verb string // "bind" or "mount"
113 Flag Flag
114 Source string
115 Target string
116}
117
118// Ns is one namespace: a mount table, a working directory, and the ordered
119// list of operations that produced them.
120type Ns struct {
121 table *avl.Tree // cleaned target path -> *entry
122 ops []Op
123 cwd string
124}
125
126// New returns a namespace whose root is the given file. The root is the one
127// binding that cannot be expressed as a bind of something else, so it is
128// installed directly.
129func New(root ninep.File) *Ns {
130 n := &Ns{table: avl.NewTree(), cwd: "/"}
131 n.table.Set("/", &entry{members: []member{{file: root, create: true}}})
132 return n
133}
134
135// Cwd returns the working directory.
136func (n *Ns) Cwd() string { return n.cwd }
137
138// Cd sets the working directory, which must resolve to a directory.
139func (n *Ns) Cd(p string) error {
140 abs := n.Abs(p)
141 st, err := n.Stat(abs)
142 if err != nil {
143 return err
144 }
145 if !st.IsDir() {
146 return ninep.ErrNotDir
147 }
148 n.cwd = abs
149 return nil
150}
151
152// Abs resolves p against the working directory.
153func (n *Ns) Abs(p string) string { return ninep.Abs(n.cwd, p) }
154
155func (n *Ns) entry(p string) *entry {
156 v := n.table.Get(p)
157 if v == nil {
158 return nil
159 }
160 return v.(*entry)
161}
162
163// expand substitutes the walk result for the placeholder member.
164func expand(ms []member, under []member) []member {
165 out := []member{}
166 for _, m := range ms {
167 if m.file == nil {
168 out = append(out, under...)
169 continue
170 }
171 out = append(out, m)
172 }
173 return out
174}
175
176// resolve walks p and returns the union found there, richest form: members
177// still carry their create bit, and bound reports whether a mount entry
178// applied at the final element.
179func (n *Ns) resolve(p string) ([]member, error) {
180 root := n.entry("/")
181 if root == nil {
182 return nil, ErrNoRoot
183 }
184 cur := expand(root.members, nil)
185 if len(cur) == 0 {
186 return nil, ErrNoRoot
187 }
188 elems := ninep.Elems(ninep.Clean(p))
189 if len(elems) > ninep.MaxDepth {
190 return nil, ninep.ErrTooDeep
191 }
192 prefix := ""
193 for _, e := range elems {
194 // First match wins. Walking INTO a union does not produce a union
195 // of the members' subdirectories: in Plan 9 a union is top level
196 // only, and a walk returns one channel.
197 walked := []member{}
198 for _, m := range cur {
199 f, err := m.file.Walk(e)
200 if err == nil {
201 walked = append(walked, member{file: f})
202 break
203 }
204 }
205 prefix += "/" + e
206 next := walked
207 if ent := n.entry(prefix); ent != nil {
208 next = expand(ent.members, walked)
209 }
210 if len(next) == 0 {
211 return nil, ninep.ErrNotExist
212 }
213 cur = next
214 }
215 return cur, nil
216}
217
218// Resolve returns every union member visible at p, in search order.
219func (n *Ns) Resolve(p string) ([]ninep.File, error) {
220 ms, err := n.resolve(n.Abs(p))
221 if err != nil {
222 return nil, err
223 }
224 out := []ninep.File{}
225 for _, m := range ms {
226 out = append(out, m.file)
227 }
228 return out, nil
229}
230
231// Open returns the file a name resolves to: the first member of its union,
232// which is the one a walk through this name would reach.
233func (n *Ns) Open(p string) (ninep.File, error) {
234 fs, err := n.Resolve(p)
235 if err != nil {
236 return nil, err
237 }
238 return fs[0], nil
239}
240
241// Stat returns the entry for p, with the name replaced by the last element of
242// the path as asked for, so that a union member's own name never leaks.
243func (n *Ns) Stat(p string) (ninep.Stat, error) {
244 f, err := n.Open(p)
245 if err != nil {
246 return ninep.Stat{}, err
247 }
248 st := f.Stat()
249 st.Name = ninep.Base(n.Abs(p))
250 return st, nil
251}
252
253// ReadFile reads the whole file at p.
254func (n *Ns) ReadFile(p string) (string, error) {
255 f, err := n.Open(p)
256 if err != nil {
257 return "", err
258 }
259 return ninep.ReadAll(f)
260}
261
262// ReadDir lists p. A union directory is the CONCATENATION of its members'
263// contents, as in Plan 9, so duplicate names can appear and shadowing is
264// visible. Pass unique to collapse them first-wins instead, which is the set
265// of names a walk can actually reach.
266func (n *Ns) ReadDir(p string, unique bool) ([]ninep.Stat, error) {
267 ms, err := n.resolve(n.Abs(p))
268 if err != nil {
269 return nil, err
270 }
271 if len(ms) == 1 && !ms[0].file.Stat().IsDir() {
272 return nil, ninep.ErrNotDir
273 }
274 out := []ninep.Stat{}
275 seen := map[string]bool{}
276 for _, m := range ms {
277 ents, err := m.file.ReadDir()
278 if err != nil {
279 continue // a non-directory member contributes nothing
280 }
281 for _, e := range ents {
282 if unique {
283 if seen[e.Name] {
284 continue
285 }
286 seen[e.Name] = true
287 }
288 out = append(out, e)
289 }
290 }
291 return out, nil
292}
293
294// CreateTarget returns the directory that a create at p should happen in.
295//
296// For a plain directory that is just the directory. For a union it is the
297// first member carrying MCREATE, and if no member has it, creation is refused,
298// which is bind(2)'s rule.
299func (n *Ns) CreateTarget(p string) (ninep.Mutable, error) {
300 abs := n.Abs(p)
301 ms, err := n.resolve(abs)
302 if err != nil {
303 return nil, err
304 }
305 isUnion := n.entry(abs) != nil && len(ms) > 1
306 for _, m := range ms {
307 if isUnion && !m.create {
308 continue
309 }
310 mu, ok := m.file.(ninep.Mutable)
311 if !ok {
312 continue // a read-only server, for instance a mounted realm
313 }
314 if !mu.Stat().IsDir() {
315 continue
316 }
317 return mu, nil
318 }
319 if isUnion {
320 return nil, ninep.ErrNoCreate
321 }
322 return nil, ninep.ErrPerm
323}
324
325// Bind makes source visible at target, as bind(1) does. Both names are
326// resolved in THIS namespace, and the source is resolved once: what is stored
327// is the file it names today, not the name.
328func (n *Ns) Bind(source, target string, flag Flag) error {
329 return n.BindVerb("bind", source, target, flag)
330}
331
332// BindVerb is Bind with the verb that String should print. Plan 9 spells the
333// same operation "bind" or "mount" depending on whether the source is a name
334// or a channel, and ns(1) echoes back whichever was used.
335func (n *Ns) BindVerb(verb, source, target string, flag Flag) error {
336 ms, err := n.resolve(n.Abs(source))
337 if err != nil {
338 return err
339 }
340 files := []ninep.File{}
341 for _, m := range ms {
342 files = append(files, m.file)
343 }
344 return n.graft(verb, source, target, flag, files)
345}
346
347// Mount grafts a file tree that has no name in this namespace yet, which is
348// how a service posted by another realm gets in. source is a label, used only
349// when printing the namespace.
350func (n *Ns) Mount(f ninep.File, source, target string, flag Flag) error {
351 return n.graft("mount", source, target, flag, []ninep.File{f})
352}
353
354func (n *Ns) graft(verb, source, target string, flag Flag, files []ninep.File) error {
355 if len(n.ops) >= MaxOps {
356 return ErrTooManyOps
357 }
358 abs := n.Abs(target)
359 // bind(1) requires the target to exist: you can only rebind a name that
360 // already resolves to something.
361 if _, err := n.resolve(abs); err != nil {
362 return err
363 }
364 add := []member{}
365 for _, f := range files {
366 add = append(add, member{file: f, create: flag.creates()})
367 }
368
369 ent := n.entry(abs)
370 var members []member
371 switch {
372 case ent == nil:
373 // The name has never been bound: its current contents are the
374 // placeholder. It does NOT carry MCREATE, which is why creating
375 // in a freshly unioned directory is refused until some member is
376 // bound with -c.
377 members = []member{{file: nil}}
378 default:
379 members = ent.members
380 }
381 switch flag.mode() {
382 case MBEFORE:
383 members = append(add, members...)
384 case MAFTER:
385 members = append(members, add...)
386 default: // MREPL: the old file is gone, not unioned
387 members = add
388 }
389 if len(members) > MaxUnion {
390 return ErrWideUnion
391 }
392 n.table.Set(abs, &entry{members: members})
393 n.ops = append(n.ops, Op{Verb: verb, Flag: flag, Source: source, Target: abs})
394 return nil
395}
396
397// Unmount undoes bindings at target. With an empty source it removes every
398// binding there, restoring the name to whatever it resolved to originally.
399func (n *Ns) Unmount(source, target string) error {
400 abs := n.Abs(target)
401 ent := n.entry(abs)
402 if ent == nil {
403 return ErrNotBound
404 }
405 if source == "" {
406 n.table.Remove(abs)
407 n.dropOps(abs, "")
408 return nil
409 }
410 ms, err := n.resolve(n.Abs(source))
411 if err != nil {
412 return err
413 }
414 kept := []member{}
415 removed := false
416 for _, m := range ent.members {
417 drop := false
418 for _, s := range ms {
419 if m.file != nil && m.file == s.file {
420 drop = true
421 break
422 }
423 }
424 if drop {
425 removed = true
426 continue
427 }
428 kept = append(kept, m)
429 }
430 if !removed {
431 return ErrNotBound
432 }
433 if onlyPlaceholders(kept) {
434 // Nothing but "whatever was here originally" is left, so the entry
435 // is a no-op: drop it rather than leave a phantom binding behind.
436 n.table.Remove(abs)
437 } else {
438 n.table.Set(abs, &entry{members: kept})
439 }
440 n.dropOps(abs, source)
441 return nil
442}
443
444func onlyPlaceholders(ms []member) bool {
445 for _, m := range ms {
446 if m.file != nil {
447 return false
448 }
449 }
450 return true
451}
452
453func (n *Ns) dropOps(target, source string) {
454 kept := []Op{}
455 for _, op := range n.ops {
456 if op.Target == target && (source == "" || op.Source == source) {
457 continue
458 }
459 kept = append(kept, op)
460 }
461 n.ops = kept
462}
463
464// Ops returns the bindings in application order.
465func (n *Ns) Ops() []Op { return n.ops }
466
467// String prints the namespace the way Plan 9's ns(1) does: one line per
468// binding, in the order they were applied, then the working directory.
469func (n *Ns) String() string {
470 var b strings.Builder
471 for _, op := range n.ops {
472 b.WriteString(op.Verb)
473 if f := op.Flag.String(); f != "" {
474 b.WriteString(" " + f)
475 }
476 b.WriteString(" " + quote(op.Source) + " " + quote(op.Target) + "\n")
477 }
478 b.WriteString("cd " + quote(n.cwd) + "\n")
479 return b.String()
480}
481
482// quote applies rc quoting: single quotes when the word contains a space or a
483// quote, with an embedded quote doubled.
484func quote(s string) string {
485 if s != "" && !strings.ContainsAny(s, " \t'") {
486 return s
487 }
488 return "'" + strings.ReplaceAll(s, "'", "''") + "'"
489}
