1// Copyright 2014 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 webdav
6
7import (
8	"fmt"
9	"math/rand"
10	"path"
11	"reflect"
12	"sort"
13	"strconv"
14	"strings"
15	"testing"
16	"time"
17)
18
19func TestWalkToRoot(t *testing.T) {
20	testCases := []struct {
21		name string
22		want []string
23	}{{
24		"/a/b/c/d",
25		[]string{
26			"/a/b/c/d",
27			"/a/b/c",
28			"/a/b",
29			"/a",
30			"/",
31		},
32	}, {
33		"/a",
34		[]string{
35			"/a",
36			"/",
37		},
38	}, {
39		"/",
40		[]string{
41			"/",
42		},
43	}}
44
45	for _, tc := range testCases {
46		var got []string
47		if !walkToRoot(tc.name, func(name0 string, first bool) bool {
48			if first != (len(got) == 0) {
49				t.Errorf("name=%q: first=%t but len(got)==%d", tc.name, first, len(got))
50				return false
51			}
52			got = append(got, name0)
53			return true
54		}) {
55			continue
56		}
57		if !reflect.DeepEqual(got, tc.want) {
58			t.Errorf("name=%q:\ngot  %q\nwant %q", tc.name, got, tc.want)
59		}
60	}
61}
62
63var lockTestDurations = []time.Duration{
64	infiniteTimeout, // infiniteTimeout means to never expire.
65	0,               // A zero duration means to expire immediately.
66	100 * time.Hour, // A very large duration will not expire in these tests.
67}
68
69// lockTestNames are the names of a set of mutually compatible locks. For each
70// name fragment:
71//	- _ means no explicit lock.
72//	- i means an infinite-depth lock,
73//	- z means a zero-depth lock,
74var lockTestNames = []string{
75	"/_/_/_/_/z",
76	"/_/_/i",
77	"/_/z",
78	"/_/z/i",
79	"/_/z/z",
80	"/_/z/_/i",
81	"/_/z/_/z",
82	"/i",
83	"/z",
84	"/z/_/i",
85	"/z/_/z",
86}
87
88func lockTestZeroDepth(name string) bool {
89	switch name[len(name)-1] {
90	case 'i':
91		return false
92	case 'z':
93		return true
94	}
95	panic(fmt.Sprintf("lock name %q did not end with 'i' or 'z'", name))
96}
97
98func TestMemLSCanCreate(t *testing.T) {
99	now := time.Unix(0, 0)
100	m := NewMemLS().(*memLS)
101
102	for _, name := range lockTestNames {
103		_, err := m.Create(now, LockDetails{
104			Root:      name,
105			Duration:  infiniteTimeout,
106			ZeroDepth: lockTestZeroDepth(name),
107		})
108		if err != nil {
109			t.Fatalf("creating lock for %q: %v", name, err)
110		}
111	}
112
113	wantCanCreate := func(name string, zeroDepth bool) bool {
114		for _, n := range lockTestNames {
115			switch {
116			case n == name:
117				// An existing lock has the same name as the proposed lock.
118				return false
119			case strings.HasPrefix(n, name):
120				// An existing lock would be a child of the proposed lock,
121				// which conflicts if the proposed lock has infinite depth.
122				if !zeroDepth {
123					return false
124				}
125			case strings.HasPrefix(name, n):
126				// An existing lock would be an ancestor of the proposed lock,
127				// which conflicts if the ancestor has infinite depth.
128				if n[len(n)-1] == 'i' {
129					return false
130				}
131			}
132		}
133		return true
134	}
135
136	var check func(int, string)
137	check = func(recursion int, name string) {
138		for _, zeroDepth := range []bool{false, true} {
139			got := m.canCreate(name, zeroDepth)
140			want := wantCanCreate(name, zeroDepth)
141			if got != want {
142				t.Errorf("canCreate name=%q zeroDepth=%t: got %t, want %t", name, zeroDepth, got, want)
143			}
144		}
145		if recursion == 6 {
146			return
147		}
148		if name != "/" {
149			name += "/"
150		}
151		for _, c := range "_iz" {
152			check(recursion+1, name+string(c))
153		}
154	}
155	check(0, "/")
156}
157
158func TestMemLSLookup(t *testing.T) {
159	now := time.Unix(0, 0)
160	m := NewMemLS().(*memLS)
161
162	badToken := m.nextToken()
163	t.Logf("badToken=%q", badToken)
164
165	for _, name := range lockTestNames {
166		token, err := m.Create(now, LockDetails{
167			Root:      name,
168			Duration:  infiniteTimeout,
169			ZeroDepth: lockTestZeroDepth(name),
170		})
171		if err != nil {
172			t.Fatalf("creating lock for %q: %v", name, err)
173		}
174		t.Logf("%-15q -> node=%p token=%q", name, m.byName[name], token)
175	}
176
177	baseNames := append([]string{"/a", "/b/c"}, lockTestNames...)
178	for _, baseName := range baseNames {
179		for _, suffix := range []string{"", "/0", "/1/2/3"} {
180			name := baseName + suffix
181
182			goodToken := ""
183			base := m.byName[baseName]
184			if base != nil && (suffix == "" || !lockTestZeroDepth(baseName)) {
185				goodToken = base.token
186			}
187
188			for _, token := range []string{badToken, goodToken} {
189				if token == "" {
190					continue
191				}
192
193				got := m.lookup(name, Condition{Token: token})
194				want := base
195				if token == badToken {
196					want = nil
197				}
198				if got != want {
199					t.Errorf("name=%-20qtoken=%q (bad=%t): got %p, want %p",
200						name, token, token == badToken, got, want)
201				}
202			}
203		}
204	}
205}
206
207func TestMemLSConfirm(t *testing.T) {
208	now := time.Unix(0, 0)
209	m := NewMemLS().(*memLS)
210	alice, err := m.Create(now, LockDetails{
211		Root:      "/alice",
212		Duration:  infiniteTimeout,
213		ZeroDepth: false,
214	})
215	if err != nil {
216		t.Fatalf("Create: %v", err)
217	}
218
219	tweedle, err := m.Create(now, LockDetails{
220		Root:      "/tweedle",
221		Duration:  infiniteTimeout,
222		ZeroDepth: false,
223	})
224	if err != nil {
225		t.Fatalf("Create: %v", err)
226	}
227	if err := m.consistent(); err != nil {
228		t.Fatalf("Create: inconsistent state: %v", err)
229	}
230
231	// Test a mismatch between name and condition.
232	_, err = m.Confirm(now, "/tweedle/dee", "", Condition{Token: alice})
233	if err != ErrConfirmationFailed {
234		t.Fatalf("Confirm (mismatch): got %v, want ErrConfirmationFailed", err)
235	}
236	if err := m.consistent(); err != nil {
237		t.Fatalf("Confirm (mismatch): inconsistent state: %v", err)
238	}
239
240	// Test two names (that fall under the same lock) in the one Confirm call.
241	release, err := m.Confirm(now, "/tweedle/dee", "/tweedle/dum", Condition{Token: tweedle})
242	if err != nil {
243		t.Fatalf("Confirm (twins): %v", err)
244	}
245	if err := m.consistent(); err != nil {
246		t.Fatalf("Confirm (twins): inconsistent state: %v", err)
247	}
248	release()
249	if err := m.consistent(); err != nil {
250		t.Fatalf("release (twins): inconsistent state: %v", err)
251	}
252
253	// Test the same two names in overlapping Confirm / release calls.
254	releaseDee, err := m.Confirm(now, "/tweedle/dee", "", Condition{Token: tweedle})
255	if err != nil {
256		t.Fatalf("Confirm (sequence #0): %v", err)
257	}
258	if err := m.consistent(); err != nil {
259		t.Fatalf("Confirm (sequence #0): inconsistent state: %v", err)
260	}
261
262	_, err = m.Confirm(now, "/tweedle/dum", "", Condition{Token: tweedle})
263	if err != ErrConfirmationFailed {
264		t.Fatalf("Confirm (sequence #1): got %v, want ErrConfirmationFailed", err)
265	}
266	if err := m.consistent(); err != nil {
267		t.Fatalf("Confirm (sequence #1): inconsistent state: %v", err)
268	}
269
270	releaseDee()
271	if err := m.consistent(); err != nil {
272		t.Fatalf("release (sequence #2): inconsistent state: %v", err)
273	}
274
275	releaseDum, err := m.Confirm(now, "/tweedle/dum", "", Condition{Token: tweedle})
276	if err != nil {
277		t.Fatalf("Confirm (sequence #3): %v", err)
278	}
279	if err := m.consistent(); err != nil {
280		t.Fatalf("Confirm (sequence #3): inconsistent state: %v", err)
281	}
282
283	// Test that you can't unlock a held lock.
284	err = m.Unlock(now, tweedle)
285	if err != ErrLocked {
286		t.Fatalf("Unlock (sequence #4): got %v, want ErrLocked", err)
287	}
288
289	releaseDum()
290	if err := m.consistent(); err != nil {
291		t.Fatalf("release (sequence #5): inconsistent state: %v", err)
292	}
293
294	err = m.Unlock(now, tweedle)
295	if err != nil {
296		t.Fatalf("Unlock (sequence #6): %v", err)
297	}
298	if err := m.consistent(); err != nil {
299		t.Fatalf("Unlock (sequence #6): inconsistent state: %v", err)
300	}
301}
302
303func TestMemLSNonCanonicalRoot(t *testing.T) {
304	now := time.Unix(0, 0)
305	m := NewMemLS().(*memLS)
306	token, err := m.Create(now, LockDetails{
307		Root:     "/foo/./bar//",
308		Duration: 1 * time.Second,
309	})
310	if err != nil {
311		t.Fatalf("Create: %v", err)
312	}
313	if err := m.consistent(); err != nil {
314		t.Fatalf("Create: inconsistent state: %v", err)
315	}
316	if err := m.Unlock(now, token); err != nil {
317		t.Fatalf("Unlock: %v", err)
318	}
319	if err := m.consistent(); err != nil {
320		t.Fatalf("Unlock: inconsistent state: %v", err)
321	}
322}
323
324func TestMemLSExpiry(t *testing.T) {
325	m := NewMemLS().(*memLS)
326	testCases := []string{
327		"setNow 0",
328		"create /a.5",
329		"want /a.5",
330		"create /c.6",
331		"want /a.5 /c.6",
332		"create /a/b.7",
333		"want /a.5 /a/b.7 /c.6",
334		"setNow 4",
335		"want /a.5 /a/b.7 /c.6",
336		"setNow 5",
337		"want /a/b.7 /c.6",
338		"setNow 6",
339		"want /a/b.7",
340		"setNow 7",
341		"want ",
342		"setNow 8",
343		"want ",
344		"create /a.12",
345		"create /b.13",
346		"create /c.15",
347		"create /a/d.16",
348		"want /a.12 /a/d.16 /b.13 /c.15",
349		"refresh /a.14",
350		"want /a.14 /a/d.16 /b.13 /c.15",
351		"setNow 12",
352		"want /a.14 /a/d.16 /b.13 /c.15",
353		"setNow 13",
354		"want /a.14 /a/d.16 /c.15",
355		"setNow 14",
356		"want /a/d.16 /c.15",
357		"refresh /a/d.20",
358		"refresh /c.20",
359		"want /a/d.20 /c.20",
360		"setNow 20",
361		"want ",
362	}
363
364	tokens := map[string]string{}
365	zTime := time.Unix(0, 0)
366	now := zTime
367	for i, tc := range testCases {
368		j := strings.IndexByte(tc, ' ')
369		if j < 0 {
370			t.Fatalf("test case #%d %q: invalid command", i, tc)
371		}
372		op, arg := tc[:j], tc[j+1:]
373		switch op {
374		default:
375			t.Fatalf("test case #%d %q: invalid operation %q", i, tc, op)
376
377		case "create", "refresh":
378			parts := strings.Split(arg, ".")
379			if len(parts) != 2 {
380				t.Fatalf("test case #%d %q: invalid create", i, tc)
381			}
382			root := parts[0]
383			d, err := strconv.Atoi(parts[1])
384			if err != nil {
385				t.Fatalf("test case #%d %q: invalid duration", i, tc)
386			}
387			dur := time.Unix(0, 0).Add(time.Duration(d) * time.Second).Sub(now)
388
389			switch op {
390			case "create":
391				token, err := m.Create(now, LockDetails{
392					Root:      root,
393					Duration:  dur,
394					ZeroDepth: true,
395				})
396				if err != nil {
397					t.Fatalf("test case #%d %q: Create: %v", i, tc, err)
398				}
399				tokens[root] = token
400
401			case "refresh":
402				token := tokens[root]
403				if token == "" {
404					t.Fatalf("test case #%d %q: no token for %q", i, tc, root)
405				}
406				got, err := m.Refresh(now, token, dur)
407				if err != nil {
408					t.Fatalf("test case #%d %q: Refresh: %v", i, tc, err)
409				}
410				want := LockDetails{
411					Root:      root,
412					Duration:  dur,
413					ZeroDepth: true,
414				}
415				if got != want {
416					t.Fatalf("test case #%d %q:\ngot  %v\nwant %v", i, tc, got, want)
417				}
418			}
419
420		case "setNow":
421			d, err := strconv.Atoi(arg)
422			if err != nil {
423				t.Fatalf("test case #%d %q: invalid duration", i, tc)
424			}
425			now = time.Unix(0, 0).Add(time.Duration(d) * time.Second)
426
427		case "want":
428			m.mu.Lock()
429			m.collectExpiredNodes(now)
430			got := make([]string, 0, len(m.byToken))
431			for _, n := range m.byToken {
432				got = append(got, fmt.Sprintf("%s.%d",
433					n.details.Root, n.expiry.Sub(zTime)/time.Second))
434			}
435			m.mu.Unlock()
436			sort.Strings(got)
437			want := []string{}
438			if arg != "" {
439				want = strings.Split(arg, " ")
440			}
441			if !reflect.DeepEqual(got, want) {
442				t.Fatalf("test case #%d %q:\ngot  %q\nwant %q", i, tc, got, want)
443			}
444		}
445
446		if err := m.consistent(); err != nil {
447			t.Fatalf("test case #%d %q: inconsistent state: %v", i, tc, err)
448		}
449	}
450}
451
452func TestMemLS(t *testing.T) {
453	now := time.Unix(0, 0)
454	m := NewMemLS().(*memLS)
455	rng := rand.New(rand.NewSource(0))
456	tokens := map[string]string{}
457	nConfirm, nCreate, nRefresh, nUnlock := 0, 0, 0, 0
458	const N = 2000
459
460	for i := 0; i < N; i++ {
461		name := lockTestNames[rng.Intn(len(lockTestNames))]
462		duration := lockTestDurations[rng.Intn(len(lockTestDurations))]
463		confirmed, unlocked := false, false
464
465		// If the name was already locked, we randomly confirm/release, refresh
466		// or unlock it. Otherwise, we create a lock.
467		token := tokens[name]
468		if token != "" {
469			switch rng.Intn(3) {
470			case 0:
471				confirmed = true
472				nConfirm++
473				release, err := m.Confirm(now, name, "", Condition{Token: token})
474				if err != nil {
475					t.Fatalf("iteration #%d: Confirm %q: %v", i, name, err)
476				}
477				if err := m.consistent(); err != nil {
478					t.Fatalf("iteration #%d: inconsistent state: %v", i, err)
479				}
480				release()
481
482			case 1:
483				nRefresh++
484				if _, err := m.Refresh(now, token, duration); err != nil {
485					t.Fatalf("iteration #%d: Refresh %q: %v", i, name, err)
486				}
487
488			case 2:
489				unlocked = true
490				nUnlock++
491				if err := m.Unlock(now, token); err != nil {
492					t.Fatalf("iteration #%d: Unlock %q: %v", i, name, err)
493				}
494			}
495
496		} else {
497			nCreate++
498			var err error
499			token, err = m.Create(now, LockDetails{
500				Root:      name,
501				Duration:  duration,
502				ZeroDepth: lockTestZeroDepth(name),
503			})
504			if err != nil {
505				t.Fatalf("iteration #%d: Create %q: %v", i, name, err)
506			}
507		}
508
509		if !confirmed {
510			if duration == 0 || unlocked {
511				// A zero-duration lock should expire immediately and is
512				// effectively equivalent to being unlocked.
513				tokens[name] = ""
514			} else {
515				tokens[name] = token
516			}
517		}
518
519		if err := m.consistent(); err != nil {
520			t.Fatalf("iteration #%d: inconsistent state: %v", i, err)
521		}
522	}
523
524	if nConfirm < N/10 {
525		t.Fatalf("too few Confirm calls: got %d, want >= %d", nConfirm, N/10)
526	}
527	if nCreate < N/10 {
528		t.Fatalf("too few Create calls: got %d, want >= %d", nCreate, N/10)
529	}
530	if nRefresh < N/10 {
531		t.Fatalf("too few Refresh calls: got %d, want >= %d", nRefresh, N/10)
532	}
533	if nUnlock < N/10 {
534		t.Fatalf("too few Unlock calls: got %d, want >= %d", nUnlock, N/10)
535	}
536}
537
538func (m *memLS) consistent() error {
539	m.mu.Lock()
540	defer m.mu.Unlock()
541
542	// If m.byName is non-empty, then it must contain an entry for the root "/",
543	// and its refCount should equal the number of locked nodes.
544	if len(m.byName) > 0 {
545		n := m.byName["/"]
546		if n == nil {
547			return fmt.Errorf(`non-empty m.byName does not contain the root "/"`)
548		}
549		if n.refCount != len(m.byToken) {
550			return fmt.Errorf("root node refCount=%d, differs from len(m.byToken)=%d", n.refCount, len(m.byToken))
551		}
552	}
553
554	for name, n := range m.byName {
555		// The map keys should be consistent with the node's copy of the key.
556		if n.details.Root != name {
557			return fmt.Errorf("node name %q != byName map key %q", n.details.Root, name)
558		}
559
560		// A name must be clean, and start with a "/".
561		if len(name) == 0 || name[0] != '/' {
562			return fmt.Errorf(`node name %q does not start with "/"`, name)
563		}
564		if name != path.Clean(name) {
565			return fmt.Errorf(`node name %q is not clean`, name)
566		}
567
568		// A node's refCount should be positive.
569		if n.refCount <= 0 {
570			return fmt.Errorf("non-positive refCount for node at name %q", name)
571		}
572
573		// A node's refCount should be the number of self-or-descendents that
574		// are locked (i.e. have a non-empty token).
575		var list []string
576		for name0, n0 := range m.byName {
577			// All of lockTestNames' name fragments are one byte long: '_', 'i' or 'z',
578			// so strings.HasPrefix is equivalent to self-or-descendent name match.
579			// We don't have to worry about "/foo/bar" being a false positive match
580			// for "/foo/b".
581			if strings.HasPrefix(name0, name) && n0.token != "" {
582				list = append(list, name0)
583			}
584		}
585		if n.refCount != len(list) {
586			sort.Strings(list)
587			return fmt.Errorf("node at name %q has refCount %d but locked self-or-descendents are %q (len=%d)",
588				name, n.refCount, list, len(list))
589		}
590
591		// A node n is in m.byToken if it has a non-empty token.
592		if n.token != "" {
593			if _, ok := m.byToken[n.token]; !ok {
594				return fmt.Errorf("node at name %q has token %q but not in m.byToken", name, n.token)
595			}
596		}
597
598		// A node n is in m.byExpiry if it has a non-negative byExpiryIndex.
599		if n.byExpiryIndex >= 0 {
600			if n.byExpiryIndex >= len(m.byExpiry) {
601				return fmt.Errorf("node at name %q has byExpiryIndex %d but m.byExpiry has length %d", name, n.byExpiryIndex, len(m.byExpiry))
602			}
603			if n != m.byExpiry[n.byExpiryIndex] {
604				return fmt.Errorf("node at name %q has byExpiryIndex %d but that indexes a different node", name, n.byExpiryIndex)
605			}
606		}
607	}
608
609	for token, n := range m.byToken {
610		// The map keys should be consistent with the node's copy of the key.
611		if n.token != token {
612			return fmt.Errorf("node token %q != byToken map key %q", n.token, token)
613		}
614
615		// Every node in m.byToken is in m.byName.
616		if _, ok := m.byName[n.details.Root]; !ok {
617			return fmt.Errorf("node at name %q in m.byToken but not in m.byName", n.details.Root)
618		}
619	}
620
621	for i, n := range m.byExpiry {
622		// The slice indices should be consistent with the node's copy of the index.
623		if n.byExpiryIndex != i {
624			return fmt.Errorf("node byExpiryIndex %d != byExpiry slice index %d", n.byExpiryIndex, i)
625		}
626
627		// Every node in m.byExpiry is in m.byName.
628		if _, ok := m.byName[n.details.Root]; !ok {
629			return fmt.Errorf("node at name %q in m.byExpiry but not in m.byName", n.details.Root)
630		}
631
632		// No node in m.byExpiry should be held.
633		if n.held {
634			return fmt.Errorf("node at name %q in m.byExpiry is held", n.details.Root)
635		}
636	}
637	return nil
638}
639
640func TestParseTimeout(t *testing.T) {
641	testCases := []struct {
642		s       string
643		want    time.Duration
644		wantErr error
645	}{{
646		"",
647		infiniteTimeout,
648		nil,
649	}, {
650		"Infinite",
651		infiniteTimeout,
652		nil,
653	}, {
654		"Infinitesimal",
655		0,
656		errInvalidTimeout,
657	}, {
658		"infinite",
659		0,
660		errInvalidTimeout,
661	}, {
662		"Second-0",
663		0 * time.Second,
664		nil,
665	}, {
666		"Second-123",
667		123 * time.Second,
668		nil,
669	}, {
670		"  Second-456    ",
671		456 * time.Second,
672		nil,
673	}, {
674		"Second-4100000000",
675		4100000000 * time.Second,
676		nil,
677	}, {
678		"junk",
679		0,
680		errInvalidTimeout,
681	}, {
682		"Second-",
683		0,
684		errInvalidTimeout,
685	}, {
686		"Second--1",
687		0,
688		errInvalidTimeout,
689	}, {
690		"Second--123",
691		0,
692		errInvalidTimeout,
693	}, {
694		"Second-+123",
695		0,
696		errInvalidTimeout,
697	}, {
698		"Second-0x123",
699		0,
700		errInvalidTimeout,
701	}, {
702		"second-123",
703		0,
704		errInvalidTimeout,
705	}, {
706		"Second-4294967295",
707		4294967295 * time.Second,
708		nil,
709	}, {
710		// Section 10.7 says that "The timeout value for TimeType "Second"
711		// must not be greater than 2^32-1."
712		"Second-4294967296",
713		0,
714		errInvalidTimeout,
715	}, {
716		// This test case comes from section 9.10.9 of the spec. It says,
717		//
718		// "In this request, the client has specified that it desires an
719		// infinite-length lock, if available, otherwise a timeout of 4.1
720		// billion seconds, if available."
721		//
722		// The Go WebDAV package always supports infinite length locks,
723		// and ignores the fallback after the comma.
724		"Infinite, Second-4100000000",
725		infiniteTimeout,
726		nil,
727	}}
728
729	for _, tc := range testCases {
730		got, gotErr := parseTimeout(tc.s)
731		if got != tc.want || gotErr != tc.wantErr {
732			t.Errorf("parsing %q:\ngot  %v, %v\nwant %v, %v", tc.s, got, gotErr, tc.want, tc.wantErr)
733		}
734	}
735}
736