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.
19 func TestWalkToRoot(t *testing.T) {
20 testCases := []struct {
45 for _, tc := range testCases {
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))
52 got = append(got, name0)
57 if !reflect.DeepEqual(got, tc.want) {
58 t.Errorf("name=%q:\ngot %q\nwant %q", tc.name, got, tc.want)
63 var 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.
69 // lockTestNames are the names of a set of mutually compatible locks. For each
71 // - _ means no explicit lock.
72 // - i means a infinite-depth lock,
73 // - z means a zero-depth lock,
74 var lockTestNames = []string{
88 func lockTestZeroDepth(name string) bool {
89 switch name[len(name)-1] {
95 panic(fmt.Sprintf("lock name %q did not end with 'i' or 'z'", name))
98 func TestMemLSCanCreate(t *testing.T) {
99 now := time.Unix(0, 0)
100 m := NewMemLS().(*memLS)
102 for _, name := range lockTestNames {
103 _, err := m.Create(now, LockDetails{
105 Duration: infiniteTimeout,
106 ZeroDepth: lockTestZeroDepth(name),
109 t.Fatalf("creating lock for %q: %v", name, err)
113 wantCanCreate := func(name string, zeroDepth bool) bool {
114 for _, n := range lockTestNames {
117 // An existing lock has the same name as the proposed lock.
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.
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' {
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)
142 t.Errorf("canCreate name=%q zeroDepth=%t: got %t, want %t", name, zeroDepth, got, want)
151 for _, c := range "_iz" {
152 check(recursion+1, name+string(c))
158 func TestMemLSLookup(t *testing.T) {
159 now := time.Unix(0, 0)
160 m := NewMemLS().(*memLS)
162 badToken := m.nextToken()
163 t.Logf("badToken=%q", badToken)
165 for _, name := range lockTestNames {
166 token, err := m.Create(now, LockDetails{
168 Duration: infiniteTimeout,
169 ZeroDepth: lockTestZeroDepth(name),
172 t.Fatalf("creating lock for %q: %v", name, err)
174 t.Logf("%-15q -> node=%p token=%q", name, m.byName[name], token)
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
183 base := m.byName[baseName]
184 if base != nil && (suffix == "" || !lockTestZeroDepth(baseName)) {
185 goodToken = base.token
188 for _, token := range []string{badToken, goodToken} {
193 got := m.lookup(name, Condition{Token: token})
195 if token == badToken {
199 t.Errorf("name=%-20qtoken=%q (bad=%t): got %p, want %p",
200 name, token, token == badToken, got, want)
207 func TestMemLSConfirm(t *testing.T) {
208 now := time.Unix(0, 0)
209 m := NewMemLS().(*memLS)
210 alice, err := m.Create(now, LockDetails{
212 Duration: infiniteTimeout,
215 tweedle, err := m.Create(now, LockDetails{
217 Duration: infiniteTimeout,
221 t.Fatalf("Create: %v", err)
223 if err := m.consistent(); err != nil {
224 t.Fatalf("Create: inconsistent state: %v", err)
227 // Test a mismatch between name and condition.
228 _, err = m.Confirm(now, "/tweedle/dee", "", Condition{Token: alice})
229 if err != ErrConfirmationFailed {
230 t.Fatalf("Confirm (mismatch): got %v, want ErrConfirmationFailed", err)
232 if err := m.consistent(); err != nil {
233 t.Fatalf("Confirm (mismatch): inconsistent state: %v", err)
236 // Test two names (that fall under the same lock) in the one Confirm call.
237 release, err := m.Confirm(now, "/tweedle/dee", "/tweedle/dum", Condition{Token: tweedle})
239 t.Fatalf("Confirm (twins): %v", err)
241 if err := m.consistent(); err != nil {
242 t.Fatalf("Confirm (twins): inconsistent state: %v", err)
245 if err := m.consistent(); err != nil {
246 t.Fatalf("release (twins): inconsistent state: %v", err)
249 // Test the same two names in overlapping Confirm / release calls.
250 releaseDee, err := m.Confirm(now, "/tweedle/dee", "", Condition{Token: tweedle})
252 t.Fatalf("Confirm (sequence #0): %v", err)
254 if err := m.consistent(); err != nil {
255 t.Fatalf("Confirm (sequence #0): inconsistent state: %v", err)
258 _, err = m.Confirm(now, "/tweedle/dum", "", Condition{Token: tweedle})
259 if err != ErrConfirmationFailed {
260 t.Fatalf("Confirm (sequence #1): got %v, want ErrConfirmationFailed", err)
262 if err := m.consistent(); err != nil {
263 t.Fatalf("Confirm (sequence #1): inconsistent state: %v", err)
267 if err := m.consistent(); err != nil {
268 t.Fatalf("release (sequence #2): inconsistent state: %v", err)
271 releaseDum, err := m.Confirm(now, "/tweedle/dum", "", Condition{Token: tweedle})
273 t.Fatalf("Confirm (sequence #3): %v", err)
275 if err := m.consistent(); err != nil {
276 t.Fatalf("Confirm (sequence #3): inconsistent state: %v", err)
279 // Test that you can't unlock a held lock.
280 err = m.Unlock(now, tweedle)
281 if err != ErrLocked {
282 t.Fatalf("Unlock (sequence #4): got %v, want ErrLocked", err)
286 if err := m.consistent(); err != nil {
287 t.Fatalf("release (sequence #5): inconsistent state: %v", err)
290 err = m.Unlock(now, tweedle)
292 t.Fatalf("Unlock (sequence #6): %v", err)
294 if err := m.consistent(); err != nil {
295 t.Fatalf("Unlock (sequence #6): inconsistent state: %v", err)
299 func TestMemLSNonCanonicalRoot(t *testing.T) {
300 now := time.Unix(0, 0)
301 m := NewMemLS().(*memLS)
302 token, err := m.Create(now, LockDetails{
303 Root: "/foo/./bar//",
304 Duration: 1 * time.Second,
307 t.Fatalf("Create: %v", err)
309 if err := m.consistent(); err != nil {
310 t.Fatalf("Create: inconsistent state: %v", err)
312 if err := m.Unlock(now, token); err != nil {
313 t.Fatalf("Unlock: %v", err)
315 if err := m.consistent(); err != nil {
316 t.Fatalf("Unlock: inconsistent state: %v", err)
320 func TestMemLSExpiry(t *testing.T) {
321 m := NewMemLS().(*memLS)
322 testCases := []string{
329 "want /a.5 /a/b.7 /c.6",
331 "want /a.5 /a/b.7 /c.6",
344 "want /a.12 /a/d.16 /b.13 /c.15",
346 "want /a.14 /a/d.16 /b.13 /c.15",
348 "want /a.14 /a/d.16 /b.13 /c.15",
350 "want /a.14 /a/d.16 /c.15",
352 "want /a/d.16 /c.15",
355 "want /a/d.20 /c.20",
360 tokens := map[string]string{}
361 zTime := time.Unix(0, 0)
363 for i, tc := range testCases {
364 j := strings.IndexByte(tc, ' ')
366 t.Fatalf("test case #%d %q: invalid command", i, tc)
368 op, arg := tc[:j], tc[j+1:]
371 t.Fatalf("test case #%d %q: invalid operation %q", i, tc, op)
373 case "create", "refresh":
374 parts := strings.Split(arg, ".")
376 t.Fatalf("test case #%d %q: invalid create", i, tc)
379 d, err := strconv.Atoi(parts[1])
381 t.Fatalf("test case #%d %q: invalid duration", i, tc)
383 dur := time.Unix(0, 0).Add(time.Duration(d) * time.Second).Sub(now)
387 token, err := m.Create(now, LockDetails{
393 t.Fatalf("test case #%d %q: Create: %v", i, tc, err)
398 token := tokens[root]
400 t.Fatalf("test case #%d %q: no token for %q", i, tc, root)
402 got, err := m.Refresh(now, token, dur)
404 t.Fatalf("test case #%d %q: Refresh: %v", i, tc, err)
412 t.Fatalf("test case #%d %q:\ngot %v\nwant %v", i, tc, got, want)
417 d, err := strconv.Atoi(arg)
419 t.Fatalf("test case #%d %q: invalid duration", i, tc)
421 now = time.Unix(0, 0).Add(time.Duration(d) * time.Second)
425 m.collectExpiredNodes(now)
426 got := make([]string, 0, len(m.byToken))
427 for _, n := range m.byToken {
428 got = append(got, fmt.Sprintf("%s.%d",
429 n.details.Root, n.expiry.Sub(zTime)/time.Second))
435 want = strings.Split(arg, " ")
437 if !reflect.DeepEqual(got, want) {
438 t.Fatalf("test case #%d %q:\ngot %q\nwant %q", i, tc, got, want)
442 if err := m.consistent(); err != nil {
443 t.Fatalf("test case #%d %q: inconsistent state: %v", i, tc, err)
448 func TestMemLS(t *testing.T) {
449 now := time.Unix(0, 0)
450 m := NewMemLS().(*memLS)
451 rng := rand.New(rand.NewSource(0))
452 tokens := map[string]string{}
453 nConfirm, nCreate, nRefresh, nUnlock := 0, 0, 0, 0
456 for i := 0; i < N; i++ {
457 name := lockTestNames[rng.Intn(len(lockTestNames))]
458 duration := lockTestDurations[rng.Intn(len(lockTestDurations))]
459 confirmed, unlocked := false, false
461 // If the name was already locked, we randomly confirm/release, refresh
462 // or unlock it. Otherwise, we create a lock.
463 token := tokens[name]
469 release, err := m.Confirm(now, name, "", Condition{Token: token})
471 t.Fatalf("iteration #%d: Confirm %q: %v", i, name, err)
473 if err := m.consistent(); err != nil {
474 t.Fatalf("iteration #%d: inconsistent state: %v", i, err)
480 if _, err := m.Refresh(now, token, duration); err != nil {
481 t.Fatalf("iteration #%d: Refresh %q: %v", i, name, err)
487 if err := m.Unlock(now, token); err != nil {
488 t.Fatalf("iteration #%d: Unlock %q: %v", i, name, err)
495 token, err = m.Create(now, LockDetails{
498 ZeroDepth: lockTestZeroDepth(name),
501 t.Fatalf("iteration #%d: Create %q: %v", i, name, err)
506 if duration == 0 || unlocked {
507 // A zero-duration lock should expire immediately and is
508 // effectively equivalent to being unlocked.
515 if err := m.consistent(); err != nil {
516 t.Fatalf("iteration #%d: inconsistent state: %v", i, err)
521 t.Fatalf("too few Confirm calls: got %d, want >= %d", nConfirm, N/10)
524 t.Fatalf("too few Create calls: got %d, want >= %d", nCreate, N/10)
527 t.Fatalf("too few Refresh calls: got %d, want >= %d", nRefresh, N/10)
530 t.Fatalf("too few Unlock calls: got %d, want >= %d", nUnlock, N/10)
534 func (m *memLS) consistent() error {
538 // If m.byName is non-empty, then it must contain an entry for the root "/",
539 // and its refCount should equal the number of locked nodes.
540 if len(m.byName) > 0 {
543 return fmt.Errorf(`non-empty m.byName does not contain the root "/"`)
545 if n.refCount != len(m.byToken) {
546 return fmt.Errorf("root node refCount=%d, differs from len(m.byToken)=%d", n.refCount, len(m.byToken))
550 for name, n := range m.byName {
551 // The map keys should be consistent with the node's copy of the key.
552 if n.details.Root != name {
553 return fmt.Errorf("node name %q != byName map key %q", n.details.Root, name)
556 // A name must be clean, and start with a "/".
557 if len(name) == 0 || name[0] != '/' {
558 return fmt.Errorf(`node name %q does not start with "/"`, name)
560 if name != path.Clean(name) {
561 return fmt.Errorf(`node name %q is not clean`, name)
564 // A node's refCount should be positive.
566 return fmt.Errorf("non-positive refCount for node at name %q", name)
569 // A node's refCount should be the number of self-or-descendents that
570 // are locked (i.e. have a non-empty token).
572 for name0, n0 := range m.byName {
573 // All of lockTestNames' name fragments are one byte long: '_', 'i' or 'z',
574 // so strings.HasPrefix is equivalent to self-or-descendent name match.
575 // We don't have to worry about "/foo/bar" being a false positive match
577 if strings.HasPrefix(name0, name) && n0.token != "" {
578 list = append(list, name0)
581 if n.refCount != len(list) {
583 return fmt.Errorf("node at name %q has refCount %d but locked self-or-descendents are %q (len=%d)",
584 name, n.refCount, list, len(list))
587 // A node n is in m.byToken if it has a non-empty token.
589 if _, ok := m.byToken[n.token]; !ok {
590 return fmt.Errorf("node at name %q has token %q but not in m.byToken", name, n.token)
594 // A node n is in m.byExpiry if it has a non-negative byExpiryIndex.
595 if n.byExpiryIndex >= 0 {
596 if n.byExpiryIndex >= len(m.byExpiry) {
597 return fmt.Errorf("node at name %q has byExpiryIndex %d but m.byExpiry has length %d", name, n.byExpiryIndex, len(m.byExpiry))
599 if n != m.byExpiry[n.byExpiryIndex] {
600 return fmt.Errorf("node at name %q has byExpiryIndex %d but that indexes a different node", name, n.byExpiryIndex)
605 for token, n := range m.byToken {
606 // The map keys should be consistent with the node's copy of the key.
607 if n.token != token {
608 return fmt.Errorf("node token %q != byToken map key %q", n.token, token)
611 // Every node in m.byToken is in m.byName.
612 if _, ok := m.byName[n.details.Root]; !ok {
613 return fmt.Errorf("node at name %q in m.byToken but not in m.byName", n.details.Root)
617 for i, n := range m.byExpiry {
618 // The slice indices should be consistent with the node's copy of the index.
619 if n.byExpiryIndex != i {
620 return fmt.Errorf("node byExpiryIndex %d != byExpiry slice index %d", n.byExpiryIndex, i)
623 // Every node in m.byExpiry is in m.byName.
624 if _, ok := m.byName[n.details.Root]; !ok {
625 return fmt.Errorf("node at name %q in m.byExpiry but not in m.byName", n.details.Root)
628 // No node in m.byExpiry should be held.
630 return fmt.Errorf("node at name %q in m.byExpiry is held", n.details.Root)
636 func TestParseTimeout(t *testing.T) {
637 testCases := []struct {
671 4100000000 * time.Second,
703 4294967295 * time.Second,
706 // Section 10.7 says that "The timeout value for TimeType "Second"
707 // must not be greater than 2^32-1."
712 // This test case comes from section 9.10.9 of the spec. It says,
714 // "In this request, the client has specified that it desires an
715 // infinite-length lock, if available, otherwise a timeout of 4.1
716 // billion seconds, if available."
718 // The Go WebDAV package always supports infinite length locks,
719 // and ignores the fallback after the comma.
720 "Infinite, Second-4100000000",
725 for _, tc := range testCases {
726 got, gotErr := parseTimeout(tc.s)
727 if got != tc.want || gotErr != tc.wantErr {
728 t.Errorf("parsing %q:\ngot %v, %v\nwant %v, %v", tc.s, got, gotErr, tc.want, tc.wantErr)