path.go (3691B)
1 // Copyright 2013 Julien Schmidt. All rights reserved. 2 // Based on the path package, Copyright 2009 The Go Authors. 3 // Use of this source code is governed by a BSD-style license that can be found 4 // at https://github.com/julienschmidt/httprouter/blob/master/LICENSE. 5 6 package gin 7 8 // cleanPath is the URL version of path.Clean, it returns a canonical URL path 9 // for p, eliminating . and .. elements. 10 // 11 // The following rules are applied iteratively until no further processing can 12 // be done: 13 // 1. Replace multiple slashes with a single slash. 14 // 2. Eliminate each . path name element (the current directory). 15 // 3. Eliminate each inner .. path name element (the parent directory) 16 // along with the non-.. element that precedes it. 17 // 4. Eliminate .. elements that begin a rooted path: 18 // that is, replace "/.." by "/" at the beginning of a path. 19 // 20 // If the result of this process is an empty string, "/" is returned. 21 func cleanPath(p string) string { 22 const stackBufSize = 128 23 // Turn empty string into "/" 24 if p == "" { 25 return "/" 26 } 27 28 // Reasonably sized buffer on stack to avoid allocations in the common case. 29 // If a larger buffer is required, it gets allocated dynamically. 30 buf := make([]byte, 0, stackBufSize) 31 32 n := len(p) 33 34 // Invariants: 35 // reading from path; r is index of next byte to process. 36 // writing to buf; w is index of next byte to write. 37 38 // path must start with '/' 39 r := 1 40 w := 1 41 42 if p[0] != '/' { 43 r = 0 44 45 if n+1 > stackBufSize { 46 buf = make([]byte, n+1) 47 } else { 48 buf = buf[:n+1] 49 } 50 buf[0] = '/' 51 } 52 53 trailing := n > 1 && p[n-1] == '/' 54 55 // A bit more clunky without a 'lazybuf' like the path package, but the loop 56 // gets completely inlined (bufApp calls). 57 // loop has no expensive function calls (except 1x make) // So in contrast to the path package this loop has no expensive function 58 // calls (except make, if needed). 59 60 for r < n { 61 switch { 62 case p[r] == '/': 63 // empty path element, trailing slash is added after the end 64 r++ 65 66 case p[r] == '.' && r+1 == n: 67 trailing = true 68 r++ 69 70 case p[r] == '.' && p[r+1] == '/': 71 // . element 72 r += 2 73 74 case p[r] == '.' && p[r+1] == '.' && (r+2 == n || p[r+2] == '/'): 75 // .. element: remove to last / 76 r += 3 77 78 if w > 1 { 79 // can backtrack 80 w-- 81 82 if len(buf) == 0 { 83 for w > 1 && p[w] != '/' { 84 w-- 85 } 86 } else { 87 for w > 1 && buf[w] != '/' { 88 w-- 89 } 90 } 91 } 92 93 default: 94 // Real path element. 95 // Add slash if needed 96 if w > 1 { 97 bufApp(&buf, p, w, '/') 98 w++ 99 } 100 101 // Copy element 102 for r < n && p[r] != '/' { 103 bufApp(&buf, p, w, p[r]) 104 w++ 105 r++ 106 } 107 } 108 } 109 110 // Re-append trailing slash 111 if trailing && w > 1 { 112 bufApp(&buf, p, w, '/') 113 w++ 114 } 115 116 // If the original string was not modified (or only shortened at the end), 117 // return the respective substring of the original string. 118 // Otherwise return a new string from the buffer. 119 if len(buf) == 0 { 120 return p[:w] 121 } 122 return string(buf[:w]) 123 } 124 125 // Internal helper to lazily create a buffer if necessary. 126 // Calls to this function get inlined. 127 func bufApp(buf *[]byte, s string, w int, c byte) { 128 b := *buf 129 if len(b) == 0 { 130 // No modification of the original string so far. 131 // If the next character is the same as in the original string, we do 132 // not yet have to allocate a buffer. 133 if s[w] == c { 134 return 135 } 136 137 // Otherwise use either the stack buffer, if it is large enough, or 138 // allocate a new buffer on the heap, and copy all previous characters. 139 length := len(s) 140 if length > cap(b) { 141 *buf = make([]byte, length) 142 } else { 143 *buf = (*buf)[:length] 144 } 145 b = *buf 146 147 copy(b, s[:w]) 148 } 149 b[w] = c 150 }