1// Copyright (c) 2014-2015 The Notify Authors. All rights reserved.
2// Use of this source code is governed by the MIT license that can be
3// found in the LICENSE file.
4
5package notify
6
7import "sync"
8
9// nonrecursiveTree TODO(rjeczalik)
10type nonrecursiveTree struct {
11	rw   sync.RWMutex // protects root
12	root root
13	w    watcher
14	c    chan EventInfo
15	rec  chan EventInfo
16}
17
18// newNonrecursiveTree TODO(rjeczalik)
19func newNonrecursiveTree(w watcher, c, rec chan EventInfo) *nonrecursiveTree {
20	if rec == nil {
21		rec = make(chan EventInfo, buffer)
22	}
23	t := &nonrecursiveTree{
24		root: root{nd: newnode("")},
25		w:    w,
26		c:    c,
27		rec:  rec,
28	}
29	go t.dispatch(c)
30	go t.internal(rec)
31	return t
32}
33
34// dispatch TODO(rjeczalik)
35func (t *nonrecursiveTree) dispatch(c <-chan EventInfo) {
36	for ei := range c {
37		dbgprintf("dispatching %v on %q", ei.Event(), ei.Path())
38		go func(ei EventInfo) {
39			var nd node
40			var isrec bool
41			dir, base := split(ei.Path())
42			fn := func(it node, isbase bool) error {
43				isrec = isrec || it.Watch.IsRecursive()
44				if isbase {
45					nd = it
46				} else {
47					it.Watch.Dispatch(ei, recursive)
48				}
49				return nil
50			}
51			t.rw.RLock()
52			// Notify recursive watchpoints found on the path.
53			if err := t.root.WalkPath(dir, fn); err != nil {
54				dbgprint("dispatch did not reach leaf:", err)
55				t.rw.RUnlock()
56				return
57			}
58			// Notify parent watchpoint.
59			nd.Watch.Dispatch(ei, 0)
60			isrec = isrec || nd.Watch.IsRecursive()
61			// If leaf watchpoint exists, notify it.
62			if nd, ok := nd.Child[base]; ok {
63				isrec = isrec || nd.Watch.IsRecursive()
64				nd.Watch.Dispatch(ei, 0)
65			}
66			t.rw.RUnlock()
67			// If the event describes newly leaf directory created within
68			if !isrec || ei.Event() != Create {
69				return
70			}
71			if ok, err := ei.(isDirer).isDir(); !ok || err != nil {
72				return
73			}
74			t.rec <- ei
75		}(ei)
76	}
77}
78
79// internal TODO(rjeczalik)
80func (t *nonrecursiveTree) internal(rec <-chan EventInfo) {
81	for ei := range rec {
82		var nd node
83		var eset = internal
84		t.rw.Lock()
85		t.root.WalkPath(ei.Path(), func(it node, _ bool) error {
86			if e := it.Watch[t.rec]; e != 0 && e > eset {
87				eset = e
88			}
89			nd = it
90			return nil
91		})
92		if eset == internal {
93			t.rw.Unlock()
94			continue
95		}
96		err := nd.Add(ei.Path()).AddDir(t.recFunc(eset))
97		t.rw.Unlock()
98		if err != nil {
99			dbgprintf("internal(%p) error: %v", rec, err)
100		}
101	}
102}
103
104// watchAdd TODO(rjeczalik)
105func (t *nonrecursiveTree) watchAdd(nd node, c chan<- EventInfo, e Event) eventDiff {
106	if e&recursive != 0 {
107		diff := nd.Watch.Add(t.rec, e|Create|omit)
108		nd.Watch.Add(c, e)
109		return diff
110	}
111	return nd.Watch.Add(c, e)
112}
113
114// watchDelMin TODO(rjeczalik)
115func (t *nonrecursiveTree) watchDelMin(min Event, nd node, c chan<- EventInfo, e Event) eventDiff {
116	old, ok := nd.Watch[t.rec]
117	if ok {
118		nd.Watch[t.rec] = min
119	}
120	diff := nd.Watch.Del(c, e)
121	if ok {
122		switch old &^= diff[0] &^ diff[1]; {
123		case old|internal == internal:
124			delete(nd.Watch, t.rec)
125			if set, ok := nd.Watch[nil]; ok && len(nd.Watch) == 1 && set == 0 {
126				delete(nd.Watch, nil)
127			}
128		default:
129			nd.Watch.Add(t.rec, old|Create)
130			switch {
131			case diff == none:
132			case diff[1]|Create == diff[0]:
133				diff = none
134			default:
135				diff[1] |= Create
136			}
137		}
138	}
139	return diff
140}
141
142// watchDel TODO(rjeczalik)
143func (t *nonrecursiveTree) watchDel(nd node, c chan<- EventInfo, e Event) eventDiff {
144	return t.watchDelMin(0, nd, c, e)
145}
146
147// Watch TODO(rjeczalik)
148func (t *nonrecursiveTree) Watch(path string, c chan<- EventInfo, events ...Event) error {
149	if c == nil {
150		panic("notify: Watch using nil channel")
151	}
152	// Expanding with empty event set is a nop.
153	if len(events) == 0 {
154		return nil
155	}
156	path, isrec, err := cleanpath(path)
157	if err != nil {
158		return err
159	}
160	eset := joinevents(events)
161	t.rw.Lock()
162	defer t.rw.Unlock()
163	nd := t.root.Add(path)
164	if isrec {
165		return t.watchrec(nd, c, eset|recursive)
166	}
167	return t.watch(nd, c, eset)
168}
169
170func (t *nonrecursiveTree) watch(nd node, c chan<- EventInfo, e Event) (err error) {
171	diff := nd.Watch.Add(c, e)
172	switch {
173	case diff == none:
174		return nil
175	case diff[1] == 0:
176		// TODO(rjeczalik): cleanup this panic after implementation is stable
177		panic("eset is empty: " + nd.Name)
178	case diff[0] == 0:
179		err = t.w.Watch(nd.Name, diff[1])
180	default:
181		err = t.w.Rewatch(nd.Name, diff[0], diff[1])
182	}
183	if err != nil {
184		nd.Watch.Del(c, diff.Event())
185		return err
186	}
187	return nil
188}
189
190func (t *nonrecursiveTree) recFunc(e Event) walkFunc {
191	return func(nd node) error {
192		switch diff := nd.Watch.Add(t.rec, e|omit|Create); {
193		case diff == none:
194		case diff[1] == 0:
195			// TODO(rjeczalik): cleanup this panic after implementation is stable
196			panic("eset is empty: " + nd.Name)
197		case diff[0] == 0:
198			t.w.Watch(nd.Name, diff[1])
199		default:
200			t.w.Rewatch(nd.Name, diff[0], diff[1])
201		}
202		return nil
203	}
204}
205
206func (t *nonrecursiveTree) watchrec(nd node, c chan<- EventInfo, e Event) error {
207	var traverse func(walkFunc) error
208	// Non-recursive tree listens on Create event for every recursive
209	// watchpoint in order to automagically set a watch for every
210	// created directory.
211	switch diff := nd.Watch.dryAdd(t.rec, e|Create); {
212	case diff == none:
213		t.watchAdd(nd, c, e)
214		nd.Watch.Add(t.rec, e|omit|Create)
215		return nil
216	case diff[1] == 0:
217		// TODO(rjeczalik): cleanup this panic after implementation is stable
218		panic("eset is empty: " + nd.Name)
219	case diff[0] == 0:
220		// TODO(rjeczalik): BFS into directories and skip subtree as soon as first
221		// recursive watchpoint is encountered.
222		traverse = nd.AddDir
223	default:
224		traverse = nd.Walk
225	}
226	// TODO(rjeczalik): account every path that failed to be (re)watched
227	// and retry.
228	if err := traverse(t.recFunc(e)); err != nil {
229		return err
230	}
231	t.watchAdd(nd, c, e)
232	return nil
233}
234
235type walkWatchpointFunc func(Event, node) error
236
237func (t *nonrecursiveTree) walkWatchpoint(nd node, fn walkWatchpointFunc) error {
238	type minode struct {
239		min Event
240		nd  node
241	}
242	mnd := minode{nd: nd}
243	stack := []minode{mnd}
244Traverse:
245	for n := len(stack); n != 0; n = len(stack) {
246		mnd, stack = stack[n-1], stack[:n-1]
247		// There must be no recursive watchpoints if the node has no watchpoints
248		// itself (every node in subtree rooted at recursive watchpoints must
249		// have at least nil (total) and t.rec watchpoints).
250		if len(mnd.nd.Watch) != 0 {
251			switch err := fn(mnd.min, mnd.nd); err {
252			case nil:
253			case errSkip:
254				continue Traverse
255			default:
256				return err
257			}
258		}
259		for _, nd := range mnd.nd.Child {
260			stack = append(stack, minode{mnd.nd.Watch[t.rec], nd})
261		}
262	}
263	return nil
264}
265
266// Stop TODO(rjeczalik)
267func (t *nonrecursiveTree) Stop(c chan<- EventInfo) {
268	fn := func(min Event, nd node) error {
269		// TODO(rjeczalik): aggregate watcher errors and retry; in worst case
270		// forward to the user.
271		switch diff := t.watchDelMin(min, nd, c, all); {
272		case diff == none:
273			return nil
274		case diff[1] == 0:
275			t.w.Unwatch(nd.Name)
276		default:
277			t.w.Rewatch(nd.Name, diff[0], diff[1])
278		}
279		return nil
280	}
281	t.rw.Lock()
282	err := t.walkWatchpoint(t.root.nd, fn) // TODO(rjeczalik): store max root per c
283	t.rw.Unlock()
284	dbgprintf("Stop(%p) error: %v\n", c, err)
285}
286
287// Close TODO(rjeczalik)
288func (t *nonrecursiveTree) Close() error {
289	err := t.w.Close()
290	close(t.c)
291	return err
292}
293