1/**
  2 * Object#toString() ref for stringify().
  3 */
  4
  5var toString = Object.prototype.toString;
  6
  7/**
  8 * Object#hasOwnProperty ref
  9 */
 10
 11var hasOwnProperty = Object.prototype.hasOwnProperty;
 12
 13/**
 14 * Array#indexOf shim.
 15 */
 16
 17var indexOf = typeof Array.prototype.indexOf === 'function'
 18  ? function(arr, el) { return arr.indexOf(el); }
 19  : function(arr, el) {
 20      for (var i = 0; i < arr.length; i++) {
 21        if (arr[i] === el) return i;
 22      }
 23      return -1;
 24    };
 25
 26/**
 27 * Array.isArray shim.
 28 */
 29
 30var isArray = Array.isArray || function(arr) {
 31  return toString.call(arr) == '[object Array]';
 32};
 33
 34/**
 35 * Object.keys shim.
 36 */
 37
 38var objectKeys = Object.keys || function(obj) {
 39  var ret = [];
 40  for (var key in obj) ret.push(key);
 41  return ret;
 42};
 43
 44/**
 45 * Array#forEach shim.
 46 */
 47
 48var forEach = typeof Array.prototype.forEach === 'function'
 49  ? function(arr, fn) { return arr.forEach(fn); }
 50  : function(arr, fn) {
 51      for (var i = 0; i < arr.length; i++) fn(arr[i]);
 52    };
 53
 54/**
 55 * Array#reduce shim.
 56 */
 57
 58var reduce = function(arr, fn, initial) {
 59  if (typeof arr.reduce === 'function') return arr.reduce(fn, initial);
 60  var res = initial;
 61  for (var i = 0; i < arr.length; i++) res = fn(res, arr[i]);
 62  return res;
 63};
 64
 65/**
 66 * Create a nullary object if possible
 67 */
 68
 69function createObject() {
 70  return Object.create
 71    ? Object.create(null)
 72    : {};
 73}
 74
 75/**
 76 * Cache non-integer test regexp.
 77 */
 78
 79var isint = /^[0-9]+$/;
 80
 81function promote(parent, key) {
 82  if (parent[key].length == 0) return parent[key] = createObject();
 83  var t = createObject();
 84  for (var i in parent[key]) {
 85    if (hasOwnProperty.call(parent[key], i)) {
 86      t[i] = parent[key][i];
 87    }
 88  }
 89  parent[key] = t;
 90  return t;
 91}
 92
 93function parse(parts, parent, key, val) {
 94  var part = parts.shift();
 95  // end
 96  if (!part) {
 97    if (isArray(parent[key])) {
 98      parent[key].push(val);
 99    } else if ('object' == typeof parent[key]) {
100      parent[key] = val;
101    } else if ('undefined' == typeof parent[key]) {
102      parent[key] = val;
103    } else {
104      parent[key] = [parent[key], val];
105    }
106    // array
107  } else {
108    var obj = parent[key] = parent[key] || [];
109    if (']' == part) {
110      if (isArray(obj)) {
111        if ('' != val) obj.push(val);
112      } else if ('object' == typeof obj) {
113        obj[objectKeys(obj).length] = val;
114      } else {
115        obj = parent[key] = [parent[key], val];
116      }
117      // prop
118    } else if (~indexOf(part, ']')) {
119      part = part.substr(0, part.length - 1);
120      if (!isint.test(part) && isArray(obj)) obj = promote(parent, key);
121      parse(parts, obj, part, val);
122      // key
123    } else {
124      if (!isint.test(part) && isArray(obj)) obj = promote(parent, key);
125      parse(parts, obj, part, val);
126    }
127  }
128}
129
130/**
131 * Merge parent key/val pair.
132 */
133
134function merge(parent, key, val){
135  if (~indexOf(key, ']')) {
136    var parts = key.split('[')
137      , len = parts.length
138      , last = len - 1;
139    parse(parts, parent, 'base', val);
140    // optimize
141  } else {
142    if (!isint.test(key) && isArray(parent.base)) {
143      var t = createObject();
144      for (var k in parent.base) t[k] = parent.base[k];
145      parent.base = t;
146    }
147    set(parent.base, key, val);
148  }
149
150  return parent;
151}
152
153/**
154 * Compact sparse arrays.
155 */
156
157function compact(obj) {
158  if ('object' != typeof obj) return obj;
159
160  if (isArray(obj)) {
161    var ret = [];
162
163    for (var i in obj) {
164      if (hasOwnProperty.call(obj, i)) {
165        ret.push(obj[i]);
166      }
167    }
168
169    return ret;
170  }
171
172  for (var key in obj) {
173    obj[key] = compact(obj[key]);
174  }
175
176  return obj;
177}
178
179/**
180 * Restore Object.prototype.
181 * see pull-request #58
182 */
183
184function restoreProto(obj) {
185  if (!Object.create) return obj;
186  if (isArray(obj)) return obj;
187  if (obj && 'object' != typeof obj) return obj;
188
189  for (var key in obj) {
190    if (hasOwnProperty.call(obj, key)) {
191      obj[key] = restoreProto(obj[key]);
192    }
193  }
194
195  obj.__proto__ = Object.prototype;
196  return obj;
197}
198
199/**
200 * Parse the given obj.
201 */
202
203function parseObject(obj){
204  var ret = { base: {} };
205
206  forEach(objectKeys(obj), function(name){
207    merge(ret, name, obj[name]);
208  });
209
210  return compact(ret.base);
211}
212
213/**
214 * Parse the given str.
215 */
216
217function parseString(str){
218  var ret = reduce(String(str).split('&'), function(ret, pair){
219    var eql = indexOf(pair, '=')
220      , brace = lastBraceInKey(pair)
221      , key = pair.substr(0, brace || eql)
222      , val = pair.substr(brace || eql, pair.length)
223      , val = val.substr(indexOf(val, '=') + 1, val.length);
224
225    // ?foo
226    if ('' == key) key = pair, val = '';
227    if ('' == key) return ret;
228
229    return merge(ret, decode(key), decode(val));
230  }, { base: createObject() }).base;
231
232  return restoreProto(compact(ret));
233}
234
235/**
236 * Parse the given query `str` or `obj`, returning an object.
237 *
238 * @param {String} str | {Object} obj
239 * @return {Object}
240 * @api public
241 */
242
243exports.parse = function(str){
244  if (null == str || '' == str) return {};
245  return 'object' == typeof str
246    ? parseObject(str)
247    : parseString(str);
248};
249
250/**
251 * Turn the given `obj` into a query string
252 *
253 * @param {Object} obj
254 * @return {String}
255 * @api public
256 */
257
258var stringify = exports.stringify = function(obj, prefix) {
259  if (isArray(obj)) {
260    return stringifyArray(obj, prefix);
261  } else if ('[object Object]' == toString.call(obj)) {
262    return stringifyObject(obj, prefix);
263  } else if ('string' == typeof obj) {
264    return stringifyString(obj, prefix);
265  } else {
266    return prefix + '=' + encodeURIComponent(String(obj));
267  }
268};
269
270/**
271 * Stringify the given `str`.
272 *
273 * @param {String} str
274 * @param {String} prefix
275 * @return {String}
276 * @api private
277 */
278
279function stringifyString(str, prefix) {
280  if (!prefix) throw new TypeError('stringify expects an object');
281  return prefix + '=' + encodeURIComponent(str);
282}
283
284/**
285 * Stringify the given `arr`.
286 *
287 * @param {Array} arr
288 * @param {String} prefix
289 * @return {String}
290 * @api private
291 */
292
293function stringifyArray(arr, prefix) {
294  var ret = [];
295  if (!prefix) throw new TypeError('stringify expects an object');
296  for (var i = 0; i < arr.length; i++) {
297    ret.push(stringify(arr[i], prefix + '[' + i + ']'));
298  }
299  return ret.join('&');
300}
301
302/**
303 * Stringify the given `obj`.
304 *
305 * @param {Object} obj
306 * @param {String} prefix
307 * @return {String}
308 * @api private
309 */
310
311function stringifyObject(obj, prefix) {
312  var ret = []
313    , keys = objectKeys(obj)
314    , key;
315
316  for (var i = 0, len = keys.length; i < len; ++i) {
317    key = keys[i];
318    if ('' == key) continue;
319    if (null == obj[key]) {
320      ret.push(encodeURIComponent(key) + '=');
321    } else {
322      ret.push(stringify(obj[key], prefix
323        ? prefix + '[' + encodeURIComponent(key) + ']'
324        : encodeURIComponent(key)));
325    }
326  }
327
328  return ret.join('&');
329}
330
331/**
332 * Set `obj`'s `key` to `val` respecting
333 * the weird and wonderful syntax of a qs,
334 * where "foo=bar&foo=baz" becomes an array.
335 *
336 * @param {Object} obj
337 * @param {String} key
338 * @param {String} val
339 * @api private
340 */
341
342function set(obj, key, val) {
343  var v = obj[key];
344  if (undefined === v) {
345    obj[key] = val;
346  } else if (isArray(v)) {
347    v.push(val);
348  } else {
349    obj[key] = [v, val];
350  }
351}
352
353/**
354 * Locate last brace in `str` within the key.
355 *
356 * @param {String} str
357 * @return {Number}
358 * @api private
359 */
360
361function lastBraceInKey(str) {
362  var len = str.length
363    , brace
364    , c;
365  for (var i = 0; i < len; ++i) {
366    c = str[i];
367    if (']' == c) brace = false;
368    if ('[' == c) brace = true;
369    if ('=' == c && !brace) return i;
370  }
371}
372
373/**
374 * Decode `str`.
375 *
376 * @param {String} str
377 * @return {String}
378 * @api private
379 */
380
381function decode(str) {
382  try {
383    return decodeURIComponent(str.replace(/\+/g, ' '));
384  } catch (err) {
385    return str;
386  }
387}