1
2
3
4
5 package webdav
6
7 import (
8 "fmt"
9 "math/rand"
10 "path"
11 "reflect"
12 "sort"
13 "strconv"
14 "strings"
15 "testing"
16 "time"
17 )
18
19 func 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
63 var lockTestDurations = []time.Duration{
64 infiniteTimeout,
65 0,
66 100 * time.Hour,
67 }
68
69
70
71
72
73
74 var 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
88 func 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
98 func 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
118 return false
119 case strings.HasPrefix(n, name):
120
121
122 if !zeroDepth {
123 return false
124 }
125 case strings.HasPrefix(name, n):
126
127
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
158 func 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
207 func 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
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
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
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
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
303 func 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
324 func 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
452 func 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
466
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
512
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
538 func (m *memLS) consistent() error {
539 m.mu.Lock()
540 defer m.mu.Unlock()
541
542
543
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
556 if n.details.Root != name {
557 return fmt.Errorf("node name %q != byName map key %q", n.details.Root, name)
558 }
559
560
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
569 if n.refCount <= 0 {
570 return fmt.Errorf("non-positive refCount for node at name %q", name)
571 }
572
573
574
575 var list []string
576 for name0, n0 := range m.byName {
577
578
579
580
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
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
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
611 if n.token != token {
612 return fmt.Errorf("node token %q != byToken map key %q", n.token, token)
613 }
614
615
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
623 if n.byExpiryIndex != i {
624 return fmt.Errorf("node byExpiryIndex %d != byExpiry slice index %d", n.byExpiryIndex, i)
625 }
626
627
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
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
640 func 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
711
712 "Second-4294967296",
713 0,
714 errInvalidTimeout,
715 }, {
716
717
718
719
720
721
722
723
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
View as plain text