vendor/golang.org/x/net/webdav/lock.go

   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
   5 package webdav
   6
   7 import (
   8         "container/heap"
   9         "errors"
  10         "strconv"
  11         "strings"
  12         "sync"
  13         "time"
  14 )
  15
  16 var (
  17         // ErrConfirmationFailed is returned by a LockSystem's Confirm method.
  18         ErrConfirmationFailed = errors.New("webdav: confirmation failed")
  19         // ErrForbidden is returned by a LockSystem's Unlock method.
  20         ErrForbidden = errors.New("webdav: forbidden")
  21         // ErrLocked is returned by a LockSystem's Create, Refresh and Unlock methods.
  22         ErrLocked = errors.New("webdav: locked")
  23         // ErrNoSuchLock is returned by a LockSystem's Refresh and Unlock methods.
  24         ErrNoSuchLock = errors.New("webdav: no such lock")
  25 )
  26
  27 // Condition can match a WebDAV resource, based on a token or ETag.
  28 // Exactly one of Token and ETag should be non-empty.
  29 type Condition struct {
  30         Not   bool
  31         Token string
  32         ETag  string
  33 }
  34
  35 // LockSystem manages access to a collection of named resources. The elements
  36 // in a lock name are separated by slash ('/', U+002F) characters, regardless
  37 // of host operating system convention.
  38 type LockSystem interface {
  39         // Confirm confirms that the caller can claim all of the locks specified by
  40         // the given conditions, and that holding the union of all of those locks
  41         // gives exclusive access to all of the named resources. Up to two resources
  42         // can be named. Empty names are ignored.
  43         //
  44         // Exactly one of release and err will be non-nil. If release is non-nil,
  45         // all of the requested locks are held until release is called. Calling
  46         // release does not unlock the lock, in the WebDAV UNLOCK sense, but once
  47         // Confirm has confirmed that a lock claim is valid, that lock cannot be
  48         // Confirmed again until it has been released.
  49         //
  50         // If Confirm returns ErrConfirmationFailed then the Handler will continue
  51         // to try any other set of locks presented (a WebDAV HTTP request can
  52         // present more than one set of locks). If it returns any other non-nil
  53         // error, the Handler will write a "500 Internal Server Error" HTTP status.
  54         Confirm(now time.Time, name0, name1 string, conditions ...Condition) (release func(), err error)
  55
  56         // Create creates a lock with the given depth, duration, owner and root
  57         // (name). The depth will either be negative (meaning infinite) or zero.
  58         //
  59         // If Create returns ErrLocked then the Handler will write a "423 Locked"
  60         // HTTP status. If it returns any other non-nil error, the Handler will
  61         // write a "500 Internal Server Error" HTTP status.
  62         //
  63         // See http://www.webdav.org/specs/rfc4918.html#rfc.section.9.10.6 for
  64         // when to use each error.
  65         //
  66         // The token returned identifies the created lock. It should be an absolute
  67         // URI as defined by RFC 3986, Section 4.3. In particular, it should not
  68         // contain whitespace.
  69         Create(now time.Time, details LockDetails) (token string, err error)
  70
  71         // Refresh refreshes the lock with the given token.
  72         //
  73         // If Refresh returns ErrLocked then the Handler will write a "423 Locked"
  74         // HTTP Status. If Refresh returns ErrNoSuchLock then the Handler will write
  75         // a "412 Precondition Failed" HTTP Status. If it returns any other non-nil
  76         // error, the Handler will write a "500 Internal Server Error" HTTP status.
  77         //
  78         // See http://www.webdav.org/specs/rfc4918.html#rfc.section.9.10.6 for
  79         // when to use each error.
  80         Refresh(now time.Time, token string, duration time.Duration) (LockDetails, error)
  81
  82         // Unlock unlocks the lock with the given token.
  83         //
  84         // If Unlock returns ErrForbidden then the Handler will write a "403
  85         // Forbidden" HTTP Status. If Unlock returns ErrLocked then the Handler
  86         // will write a "423 Locked" HTTP status. If Unlock returns ErrNoSuchLock
  87         // then the Handler will write a "409 Conflict" HTTP Status. If it returns
  88         // any other non-nil error, the Handler will write a "500 Internal Server
  89         // Error" HTTP status.
  90         //
  91         // See http://www.webdav.org/specs/rfc4918.html#rfc.section.9.11.1 for
  92         // when to use each error.
  93         Unlock(now time.Time, token string) error
  94 }
  95
  96 // LockDetails are a lock's metadata.
  97 type LockDetails struct {
  98         // Root is the root resource name being locked. For a zero-depth lock, the
  99         // root is the only resource being locked.
 100         Root string
 101         // Duration is the lock timeout. A negative duration means infinite.
 102         Duration time.Duration
 103         // OwnerXML is the verbatim <owner> XML given in a LOCK HTTP request.
 104         //
 105         // TODO: does the "verbatim" nature play well with XML namespaces?
 106         // Does the OwnerXML field need to have more structure? See
 107         // https://codereview.appspot.com/175140043/#msg2
 108         OwnerXML string
 109         // ZeroDepth is whether the lock has zero depth. If it does not have zero
 110         // depth, it has infinite depth.
 111         ZeroDepth bool
 112 }
 113
 114 // NewMemLS returns a new in-memory LockSystem.
 115 func NewMemLS() LockSystem {
 116         return &memLS{
 117                 byName:  make(map[string]*memLSNode),
 118                 byToken: make(map[string]*memLSNode),
 119                 gen:     uint64(time.Now().Unix()),
 120         }
 121 }
 122
 123 type memLS struct {
 124         mu      sync.Mutex
 125         byName  map[string]*memLSNode
 126         byToken map[string]*memLSNode
 127         gen     uint64
 128         // byExpiry only contains those nodes whose LockDetails have a finite
 129         // Duration and are yet to expire.
 130         byExpiry byExpiry
 131 }
 132
 133 func (m *memLS) nextToken() string {
 134         m.gen++
 135         return strconv.FormatUint(m.gen, 10)
 136 }
 137
 138 func (m *memLS) collectExpiredNodes(now time.Time) {
 139         for len(m.byExpiry) > 0 {
 140                 if now.Before(m.byExpiry[0].expiry) {
 141                         break
 142                 }
 143                 m.remove(m.byExpiry[0])
 144         }
 145 }
 146
 147 func (m *memLS) Confirm(now time.Time, name0, name1 string, conditions ...Condition) (func(), error) {
 148         m.mu.Lock()
 149         defer m.mu.Unlock()
 150         m.collectExpiredNodes(now)
 151
 152         var n0, n1 *memLSNode
 153         if name0 != "" {
 154                 if n0 = m.lookup(slashClean(name0), conditions...); n0 == nil {
 155                         return nil, ErrConfirmationFailed
 156                 }
 157         }
 158         if name1 != "" {
 159                 if n1 = m.lookup(slashClean(name1), conditions...); n1 == nil {
 160                         return nil, ErrConfirmationFailed
 161                 }
 162         }
 163
 164         // Don't hold the same node twice.
 165         if n1 == n0 {
 166                 n1 = nil
 167         }
 168
 169         if n0 != nil {
 170                 m.hold(n0)
 171         }
 172         if n1 != nil {
 173                 m.hold(n1)
 174         }
 175         return func() {
 176                 m.mu.Lock()
 177                 defer m.mu.Unlock()
 178                 if n1 != nil {
 179                         m.unhold(n1)
 180                 }
 181                 if n0 != nil {
 182                         m.unhold(n0)
 183                 }
 184         }, nil
 185 }
 186
 187 // lookup returns the node n that locks the named resource, provided that n
 188 // matches at least one of the given conditions and that lock isn't held by
 189 // another party. Otherwise, it returns nil.
 190 //
 191 // n may be a parent of the named resource, if n is an infinite depth lock.
 192 func (m *memLS) lookup(name string, conditions ...Condition) (n *memLSNode) {
 193         // TODO: support Condition.Not and Condition.ETag.
 194         for _, c := range conditions {
 195                 n = m.byToken[c.Token]
 196                 if n == nil || n.held {
 197                         continue
 198                 }
 199                 if name == n.details.Root {
 200                         return n
 201                 }
 202                 if n.details.ZeroDepth {
 203                         continue
 204                 }
 205                 if n.details.Root == "/" || strings.HasPrefix(name, n.details.Root+"/") {
 206                         return n
 207                 }
 208         }
 209         return nil
 210 }
 211
 212 func (m *memLS) hold(n *memLSNode) {
 213         if n.held {
 214                 panic("webdav: memLS inconsistent held state")
 215         }
 216         n.held = true
 217         if n.details.Duration >= 0 && n.byExpiryIndex >= 0 {
 218                 heap.Remove(&m.byExpiry, n.byExpiryIndex)
 219         }
 220 }
 221
 222 func (m *memLS) unhold(n *memLSNode) {
 223         if !n.held {
 224                 panic("webdav: memLS inconsistent held state")
 225         }
 226         n.held = false
 227         if n.details.Duration >= 0 {
 228                 heap.Push(&m.byExpiry, n)
 229         }
 230 }
 231
 232 func (m *memLS) Create(now time.Time, details LockDetails) (string, error) {
 233         m.mu.Lock()
 234         defer m.mu.Unlock()
 235         m.collectExpiredNodes(now)
 236         details.Root = slashClean(details.Root)
 237
 238         if !m.canCreate(details.Root, details.ZeroDepth) {
 239                 return "", ErrLocked
 240         }
 241         n := m.create(details.Root)
 242         n.token = m.nextToken()
 243         m.byToken[n.token] = n
 244         n.details = details
 245         if n.details.Duration >= 0 {
 246                 n.expiry = now.Add(n.details.Duration)
 247                 heap.Push(&m.byExpiry, n)
 248         }
 249         return n.token, nil
 250 }
 251
 252 func (m *memLS) Refresh(now time.Time, token string, duration time.Duration) (LockDetails, error) {
 253         m.mu.Lock()
 254         defer m.mu.Unlock()
 255         m.collectExpiredNodes(now)
 256
 257         n := m.byToken[token]
 258         if n == nil {
 259                 return LockDetails{}, ErrNoSuchLock
 260         }
 261         if n.held {
 262                 return LockDetails{}, ErrLocked
 263         }
 264         if n.byExpiryIndex >= 0 {
 265                 heap.Remove(&m.byExpiry, n.byExpiryIndex)
 266         }
 267         n.details.Duration = duration
 268         if n.details.Duration >= 0 {
 269                 n.expiry = now.Add(n.details.Duration)
 270                 heap.Push(&m.byExpiry, n)
 271         }
 272         return n.details, nil
 273 }
 274
 275 func (m *memLS) Unlock(now time.Time, token string) error {
 276         m.mu.Lock()
 277         defer m.mu.Unlock()
 278         m.collectExpiredNodes(now)
 279
 280         n := m.byToken[token]
 281         if n == nil {
 282                 return ErrNoSuchLock
 283         }
 284         if n.held {
 285                 return ErrLocked
 286         }
 287         m.remove(n)
 288         return nil
 289 }
 290
 291 func (m *memLS) canCreate(name string, zeroDepth bool) bool {
 292         return walkToRoot(name, func(name0 string, first bool) bool {
 293                 n := m.byName[name0]
 294                 if n == nil {
 295                         return true
 296                 }
 297                 if first {
 298                         if n.token != "" {
 299                                 // The target node is already locked.
 300                                 return false
 301                         }
 302                         if !zeroDepth {
 303                                 // The requested lock depth is infinite, and the fact that n exists
 304                                 // (n != nil) means that a descendent of the target node is locked.
 305                                 return false
 306                         }
 307                 } else if n.token != "" && !n.details.ZeroDepth {
 308                         // An ancestor of the target node is locked with infinite depth.
 309                         return false
 310                 }
 311                 return true
 312         })
 313 }
 314
 315 func (m *memLS) create(name string) (ret *memLSNode) {
 316         walkToRoot(name, func(name0 string, first bool) bool {
 317                 n := m.byName[name0]
 318                 if n == nil {
 319                         n = &memLSNode{
 320                                 details: LockDetails{
 321                                         Root: name0,
 322                                 },
 323                                 byExpiryIndex: -1,
 324                         }
 325                         m.byName[name0] = n
 326                 }
 327                 n.refCount++
 328                 if first {
 329                         ret = n
 330                 }
 331                 return true
 332         })
 333         return ret
 334 }
 335
 336 func (m *memLS) remove(n *memLSNode) {
 337         delete(m.byToken, n.token)
 338         n.token = ""
 339         walkToRoot(n.details.Root, func(name0 string, first bool) bool {
 340                 x := m.byName[name0]
 341                 x.refCount--
 342                 if x.refCount == 0 {
 343                         delete(m.byName, name0)
 344                 }
 345                 return true
 346         })
 347         if n.byExpiryIndex >= 0 {
 348                 heap.Remove(&m.byExpiry, n.byExpiryIndex)
 349         }
 350 }
 351
 352 func walkToRoot(name string, f func(name0 string, first bool) bool) bool {
 353         for first := true; ; first = false {
 354                 if !f(name, first) {
 355                         return false
 356                 }
 357                 if name == "/" {
 358                         break
 359                 }
 360                 name = name[:strings.LastIndex(name, "/")]
 361                 if name == "" {
 362                         name = "/"
 363                 }
 364         }
 365         return true
 366 }
 367
 368 type memLSNode struct {
 369         // details are the lock metadata. Even if this node's name is not explicitly locked,
 370         // details.Root will still equal the node's name.
 371         details LockDetails
 372         // token is the unique identifier for this node's lock. An empty token means that
 373         // this node is not explicitly locked.
 374         token string
 375         // refCount is the number of self-or-descendent nodes that are explicitly locked.
 376         refCount int
 377         // expiry is when this node's lock expires.
 378         expiry time.Time
 379         // byExpiryIndex is the index of this node in memLS.byExpiry. It is -1
 380         // if this node does not expire, or has expired.
 381         byExpiryIndex int
 382         // held is whether this node's lock is actively held by a Confirm call.
 383         held bool
 384 }
 385
 386 type byExpiry []*memLSNode
 387
 388 func (b *byExpiry) Len() int {
 389         return len(*b)
 390 }
 391
 392 func (b *byExpiry) Less(i, j int) bool {
 393         return (*b)[i].expiry.Before((*b)[j].expiry)
 394 }
 395
 396 func (b *byExpiry) Swap(i, j int) {
 397         (*b)[i], (*b)[j] = (*b)[j], (*b)[i]
 398         (*b)[i].byExpiryIndex = i
 399         (*b)[j].byExpiryIndex = j
 400 }
 401
 402 func (b *byExpiry) Push(x interface{}) {
 403         n := x.(*memLSNode)
 404         n.byExpiryIndex = len(*b)
 405         *b = append(*b, n)
 406 }
 407
 408 func (b *byExpiry) Pop() interface{} {
 409         i := len(*b) - 1
 410         n := (*b)[i]
 411         (*b)[i] = nil
 412         n.byExpiryIndex = -1
 413         *b = (*b)[:i]
 414         return n
 415 }
 416
 417 const infiniteTimeout = -1
 418
 419 // parseTimeout parses the Timeout HTTP header, as per section 10.7. If s is
 420 // empty, an infiniteTimeout is returned.
 421 func parseTimeout(s string) (time.Duration, error) {
 422         if s == "" {
 423                 return infiniteTimeout, nil
 424         }
 425         if i := strings.IndexByte(s, ','); i >= 0 {
 426                 s = s[:i]
 427         }
 428         s = strings.TrimSpace(s)
 429         if s == "Infinite" {
 430                 return infiniteTimeout, nil
 431         }
 432         const pre = "Second-"
 433         if !strings.HasPrefix(s, pre) {
 434                 return 0, errInvalidTimeout
 435         }
 436         s = s[len(pre):]
 437         if s == "" || s[0] < '0' || '9' < s[0] {
 438                 return 0, errInvalidTimeout
 439         }
 440         n, err := strconv.ParseInt(s, 10, 64)
 441         if err != nil || 1<<32-1 < n {
 442                 return 0, errInvalidTimeout
 443         }
 444         return time.Duration(n) * time.Second, nil
 445 }