1use std::{borrow::Cow, collections::BTreeMap};
2
3use crate::decode::{parse_bytes, parse_char, Reference};
4
5#[derive(Clone, Copy)]
17struct Key<'a>(&'a [u8], Option<&'a [u8]>);
18
19impl<'a> Key<'a> {
20 fn parse(slice: &'a [u8]) -> (Self, usize) {
21 let mut index = 0;
22 while index < slice.len() {
23 match slice[index] {
24 b'[' => {
25 let res = Key::parse_remains(&slice[..index], &slice[(index + 1)..]);
26 return (res.0, res.1 + index + 1);
27 }
28 b'%' => {
29 if index + 2 < slice.len()
31 && parse_char(slice[index + 1], slice[index + 2]) == Some(b'[')
32 {
33 let res = Key::parse_remains(&slice[..index], &slice[(index + 3)..]);
34 return (res.0, res.1 + index + 3);
35 };
36 index += 1;
37 }
38 b'&' | b'=' => break,
39 _ => index += 1,
40 }
41 }
42
43 (Self(&slice[..index], None), index)
44 }
45
46 fn parse_remains(key: &'a [u8], slice: &'a [u8]) -> (Self, usize) {
47 let mut index = 0;
48 while index < slice.len() {
49 match slice[index] {
50 b'&' | b'=' => break,
51 _ => index += 1,
52 }
53 }
54
55 (Self(key, Some(&slice[..index])), index)
56 }
57
58 fn subkey(self) -> Option<Self> {
59 let remains = self.1?;
60
61 let mut key_end_index = 0;
62 let mut index = 0;
63 while index < remains.len() {
64 match remains[index] {
65 b']' => {
66 key_end_index = index;
67 break;
68 }
69 b'%' => {
70 if index + 2 < remains.len()
72 && parse_char(remains[index + 1], remains[index + 2]) == Some(b']')
73 {
74 key_end_index = index;
75 index += 2;
76 break;
77 };
78 index += 1;
79 }
80 _ => index += 1,
81 }
82 key_end_index = index;
83 }
84
85 if index + 1 < remains.len() && remains[index + 1] == b'[' {
86 Some(Self(&remains[..key_end_index], Some(&remains[index + 2..])))
87 } else if index + 3 < remains.len()
88 && remains[index + 1] == b'%'
89 && parse_char(remains[index + 2], remains[index + 3]) == Some(b'[')
90 {
91 Some(Self(&remains[..key_end_index], Some(&remains[index + 4..])))
92 } else {
93 Some(Self(&remains[..key_end_index], None))
94 }
95 }
96
97 fn has_subkey(&self) -> bool {
98 match self.1 {
99 Some(remains) => {
100 let mut index = 0;
101 while index < remains.len() {
102 match remains[index] {
103 b']' => return true,
104 b'%' => {
105 if index + 2 < remains.len()
107 && parse_char(remains[index + 1], remains[index + 2]) == Some(b']')
108 {
109 return true;
110 };
111 index += 1;
112 }
113 _ => index += 1,
114 }
115 }
116 false
117 }
118 None => false,
119 }
120 }
121
122 fn is_empty(&self) -> bool {
123 match self.1 {
124 Some(r) => self.0.is_empty() && r.is_empty(),
125 None => self.0.is_empty(),
126 }
127 }
128
129 fn decode<'s>(&self, scratch: &'s mut Vec<u8>) -> Reference<'a, 's, [u8]> {
130 parse_bytes(self.0, scratch)
131 }
132}
133
134#[derive(Default, Clone, Copy)]
135struct Value<'a>(&'a [u8]);
136
137impl<'a> Value<'a> {
138 fn parse(slice: &'a [u8]) -> (Option<Self>, usize) {
139 match slice.first() {
140 Some(b'&') | None => {
141 return (None, 0);
142 }
143 _ => {}
144 }
145
146 let mut index = 1;
147 while index < slice.len() {
148 match slice[index] {
149 b'&' => break,
150 _ => index += 1,
151 }
152 }
153
154 (Some(Self(&slice[1..index])), index)
155 }
156
157 fn decode<'s>(&self, scratch: &'s mut Vec<u8>) -> Reference<'a, 's, [u8]> {
158 parse_bytes(self.0, scratch)
159 }
160
161 fn slice(&self) -> &'a [u8] {
162 self.0
163 }
164}
165
166#[derive(Clone, Copy)]
167struct Pair<'a>(Key<'a>, Option<Value<'a>>);
168
169impl<'a> Pair<'a> {
170 fn parse(slice: &'a [u8]) -> (Self, usize) {
176 let (key, key_len) = Key::parse(slice);
177 let (value, value_len) = Value::parse(&slice[key_len..]);
178
179 (Self(key, value), key_len + value_len + 1)
180 }
181
182 fn new(k: Key<'a>, v: Option<Value<'a>>) -> Pair<'a> {
183 Self(k, v)
184 }
185}
186
187pub struct BracketsQS<'a> {
229 pairs: BTreeMap<Cow<'a, [u8]>, Vec<Pair<'a>>>,
230}
231
232impl<'a> BracketsQS<'a> {
233 pub fn parse(slice: &'a [u8]) -> Self {
235 let mut pairs: BTreeMap<_, Vec<Pair<'a>>> = BTreeMap::new();
236 let mut scratch = Vec::new();
237
238 let mut index = 0;
239
240 while index < slice.len() {
241 let (pair, pair_len) = Pair::parse(&slice[index..]);
242 index += pair_len;
243
244 let decoded_key = pair.0.decode(&mut scratch);
245
246 if let Some(values) = pairs.get_mut(decoded_key.as_ref()) {
247 values.push(pair);
248 } else {
249 pairs.insert(decoded_key.into_cow(), vec![pair]);
250 }
251 }
252
253 Self { pairs }
254 }
255
256 fn from_pairs<I>(iter: I) -> Self
257 where
258 I: Iterator<Item = Pair<'a>>,
259 {
260 let mut pairs: BTreeMap<_, Vec<Pair<'a>>> = BTreeMap::new();
261
262 let mut scratch = Vec::new();
263 let subpairs = iter.filter_map(|p| Some((p.0.subkey()?, p.1)));
264
265 for (k, v) in subpairs {
266 let decoded_key = k.decode(&mut scratch);
267 let pair = Pair::new(k, v);
268
269 if let Some(values) = pairs.get_mut(decoded_key.as_ref()) {
270 values.push(pair);
271 } else {
272 pairs.insert(decoded_key.into_cow(), vec![pair]);
273 }
274 }
275
276 Self { pairs }
277 }
278
279 pub fn keys(&self) -> Vec<&Cow<'a, [u8]>> {
281 self.pairs.keys().collect()
282 }
283
284 pub fn sub_values(&self, key: &'a [u8]) -> Option<BracketsQS> {
286 Some(Self::from_pairs(self.pairs.get(key)?.iter().copied()))
287 }
288
289 pub fn values(&self, key: &'a [u8]) -> Option<Vec<Option<Cow<'a, [u8]>>>> {
297 let mut scratch = Vec::new();
298
299 Some(
300 self.pairs
301 .get(key)?
302 .iter()
303 .filter(|p| !p.0.has_subkey())
304 .map(|p| p.1.as_ref().map(|v| v.decode(&mut scratch).into_cow()))
305 .collect(),
306 )
307 }
308
309 pub fn value(&self, key: &'a [u8]) -> Option<Option<Cow<'a, [u8]>>> {
317 let mut scratch = Vec::new();
318
319 self.pairs
320 .get(key)?
321 .iter()
322 .filter(|p| !p.0.has_subkey())
323 .last()
324 .map(|p| p.1.as_ref().map(|v| v.decode(&mut scratch).into_cow()))
325 }
326}
327
328#[cfg(feature = "serde")]
329mod de {
330 use _serde::{de, forward_to_deserialize_any, Deserialize, Deserializer};
331
332 use crate::de::{
333 Error, ErrorKind, QSDeserializer,
334 __implementors::{DecodedSlice, IntoDeserializer, RawSlice},
335 };
336
337 use super::{BracketsQS, Pair};
338
339 pub struct Pairs<'a>(Vec<Pair<'a>>);
340
341 impl<'a> BracketsQS<'a> {
342 pub fn deserialize<T: Deserialize<'a>>(self) -> Result<T, Error> {
344 T::deserialize(QSDeserializer::new(self.into_iter()))
345 }
346
347 pub(crate) fn into_iter(self) -> impl Iterator<Item = (DecodedSlice<'a>, Pairs<'a>)> {
348 self.pairs
349 .into_iter()
350 .map(|(key, pairs)| (DecodedSlice(key), Pairs(pairs)))
351 }
352 }
353
354 impl<'a, 's> IntoDeserializer<'a, 's> for Pairs<'a> {
355 type Deserializer = PairsDeserializer<'a, 's>;
356
357 fn into_deserializer(self, scratch: &'s mut Vec<u8>) -> Self::Deserializer {
358 PairsDeserializer(self.0, scratch)
359 }
360 }
361
362 pub struct PairsDeserializer<'a, 's>(Vec<Pair<'a>>, &'s mut Vec<u8>);
363
364 impl<'a, 's> PairsDeserializer<'a, 's> {
365 #[inline]
366 fn to_seq_values(&mut self) -> Result<Vec<(usize, RawSlice<'a>)>, Error> {
367 let mut values = std::mem::take(&mut self.0)
368 .into_iter()
369 .map(|pair| {
370 let index = match pair.0.subkey() {
371 Some(subkey) if !subkey.is_empty() => lexical::parse::<usize, _>(subkey.0)
372 .map_err(|e| {
373 Error::new(ErrorKind::InvalidNumber)
374 .message(format!("invalid index: {}", e))
375 })?,
376 _ => 0,
377 };
378 Ok((index, RawSlice(pair.1.unwrap_or_default().slice())))
379 })
380 .collect::<Result<Vec<(usize, RawSlice)>, Error>>()?;
381
382 values.sort_by_key(|item| item.0);
383 Ok(values)
384 }
385 }
386
387 macro_rules! forware_to_slice_deserializer {
388 ($($method:ident ,)*) => {
389 $(
390 #[inline]
391 fn $method<V>(self, visitor: V) -> Result<V::Value, Error>
392 where
393 V: de::Visitor<'de>,
394 {
395 let scratch = self.1;
396 let value = self.0.last().unwrap().1.unwrap_or_default().slice();
397 RawSlice(value).into_deserializer(scratch).$method(visitor)
398 }
399 )*
400 };
401 }
402
403 impl<'de, 's> de::Deserializer<'de> for PairsDeserializer<'de, 's> {
404 type Error = crate::de::Error;
405
406 fn deserialize_seq<V>(mut self, visitor: V) -> Result<V::Value, Self::Error>
407 where
408 V: de::Visitor<'de>,
409 {
410 visitor.visit_seq(PairsSeqDeserializer(
411 self.to_seq_values()?.into_iter().map(|v| v.1),
412 self.1,
413 ))
414 }
415
416 fn deserialize_tuple<V>(mut self, len: usize, visitor: V) -> Result<V::Value, Self::Error>
417 where
418 V: de::Visitor<'de>,
419 {
420 let values = self.to_seq_values()?;
421
422 if values.len() == len {
423 visitor.visit_seq(PairsSeqDeserializer(
424 values.into_iter().map(|v| v.1),
425 self.1,
426 ))
427 } else {
428 Err(Error::new(ErrorKind::InvalidLength))
429 }
430 }
431
432 fn deserialize_tuple_struct<V>(
433 self,
434 _: &'static str,
435 len: usize,
436 visitor: V,
437 ) -> Result<V::Value, Self::Error>
438 where
439 V: de::Visitor<'de>,
440 {
441 self.deserialize_tuple(len, visitor)
442 }
443
444 fn deserialize_newtype_struct<V>(
445 self,
446 _: &'static str,
447 visitor: V,
448 ) -> Result<V::Value, Self::Error>
449 where
450 V: de::Visitor<'de>,
451 {
452 visitor.visit_newtype_struct(self)
453 }
454
455 fn deserialize_map<V>(self, visitor: V) -> Result<V::Value, Self::Error>
456 where
457 V: de::Visitor<'de>,
458 {
459 visitor.visit_map(PairsMapDeserializer {
460 iter: BracketsQS::from_pairs(self.0.into_iter()).into_iter(),
461 scratch: self.1,
462 value: None,
463 })
464 }
465
466 fn deserialize_struct<V>(
467 self,
468 _: &'static str,
469 _: &'static [&'static str],
470 visitor: V,
471 ) -> Result<V::Value, Self::Error>
472 where
473 V: de::Visitor<'de>,
474 {
475 self.deserialize_map(visitor)
476 }
477
478 fn deserialize_enum<V>(
479 self,
480 _: &'static str,
481 _: &'static [&'static str],
482 visitor: V,
483 ) -> Result<V::Value, Self::Error>
484 where
485 V: de::Visitor<'de>,
486 {
487 visitor.visit_enum(self)
488 }
489
490 fn deserialize_option<V>(self, visitor: V) -> Result<V::Value, Self::Error>
491 where
492 V: de::Visitor<'de>,
493 {
494 if self.0.is_empty()
495 || (self.0.len() == 1 && !self.0[0].0.has_subkey() && self.0[0].1.is_none())
496 {
497 visitor.visit_none()
498 } else {
499 visitor.visit_some(self)
500 }
501 }
502
503 forware_to_slice_deserializer! {
504 deserialize_i8, deserialize_i16, deserialize_i32, deserialize_i64, deserialize_i128,
505 deserialize_u8, deserialize_u16, deserialize_u32, deserialize_u64, deserialize_u128,
506 deserialize_f32, deserialize_f64,
507 deserialize_char, deserialize_str, deserialize_string, deserialize_identifier,
508 deserialize_bool, deserialize_bytes, deserialize_byte_buf, deserialize_unit,
509 deserialize_any, deserialize_ignored_any,
510 }
511
512 forward_to_deserialize_any! {
513 unit_struct
514 }
515 }
516
517 impl<'de, 's> de::EnumAccess<'de> for PairsDeserializer<'de, 's> {
518 type Error = Error;
519
520 type Variant = Self;
521
522 fn variant_seed<V>(self, seed: V) -> Result<(V::Value, Self::Variant), Self::Error>
523 where
524 V: de::DeserializeSeed<'de>,
525 {
526 let last_pair = self.0.last().expect("Values iterator can't be empty");
527 if let Some(subkey) = last_pair.0.subkey() {
528 let scratch = self.1;
529 let pairs = BracketsQS::from_pairs(self.0.into_iter())
530 .pairs
531 .remove(subkey.0)
532 .unwrap();
533 seed.deserialize(RawSlice(subkey.0).into_deserializer(scratch))
534 .map(move |v| (v, Self(pairs, scratch)))
535 } else {
536 let scratch = self.1;
537 seed.deserialize(
538 RawSlice(last_pair.1.unwrap_or_default().0).into_deserializer(scratch),
539 )
540 .map(move |v| (v, PairsDeserializer(Vec::new(), scratch)))
541 }
542 }
543 }
544
545 impl<'de, 's> de::VariantAccess<'de> for PairsDeserializer<'de, 's> {
546 type Error = Error;
547
548 fn unit_variant(self) -> Result<(), Self::Error> {
549 if self.0.is_empty() {
550 Ok(())
551 } else {
552 Err(Error::new(ErrorKind::Other)
553 .message("Unit enum variants should not have values".to_string()))
554 }
555 }
556
557 fn newtype_variant_seed<T>(self, seed: T) -> Result<T::Value, Self::Error>
558 where
559 T: de::DeserializeSeed<'de>,
560 {
561 seed.deserialize(self)
562 }
563
564 fn tuple_variant<V>(self, len: usize, visitor: V) -> Result<V::Value, Self::Error>
565 where
566 V: de::Visitor<'de>,
567 {
568 self.deserialize_tuple(len, visitor)
569 }
570
571 fn struct_variant<V>(
572 self,
573 fields: &'static [&'static str],
574 visitor: V,
575 ) -> Result<V::Value, Self::Error>
576 where
577 V: de::Visitor<'de>,
578 {
579 self.deserialize_struct("name", fields, visitor)
580 }
581 }
582
583 struct PairsSeqDeserializer<'s, I>(I, &'s mut Vec<u8>);
584
585 impl<'de, 's, I> de::SeqAccess<'de> for PairsSeqDeserializer<'s, I>
586 where
587 I: Iterator<Item = RawSlice<'de>>,
588 {
589 type Error = Error;
590
591 fn next_element_seed<T>(&mut self, seed: T) -> Result<Option<T::Value>, Self::Error>
592 where
593 T: de::DeserializeSeed<'de>,
594 {
595 if let Some(v) = self.0.next() {
596 seed.deserialize(v.into_deserializer(self.1)).map(Some)
597 } else {
598 Ok(None)
599 }
600 }
601 }
602
603 struct PairsMapDeserializer<'de, 's, I>
604 where
605 I: Iterator<Item = (DecodedSlice<'de>, Pairs<'de>)>,
606 {
607 iter: I,
608 scratch: &'s mut Vec<u8>,
609 value: Option<Pairs<'de>>,
610 }
611
612 impl<'de, 's, I> de::MapAccess<'de> for PairsMapDeserializer<'de, 's, I>
613 where
614 I: Iterator<Item = (DecodedSlice<'de>, Pairs<'de>)>,
615 {
616 type Error = Error;
617
618 fn next_key_seed<K>(&mut self, seed: K) -> Result<Option<K::Value>, Self::Error>
619 where
620 K: de::DeserializeSeed<'de>,
621 {
622 if let Some((k, v)) = self.iter.next() {
623 self.value = Some(v);
624
625 seed.deserialize(k.into_deserializer(self.scratch))
626 .map(Some)
627 } else {
628 Ok(None)
629 }
630 }
631
632 fn next_value_seed<V>(&mut self, seed: V) -> Result<V::Value, Self::Error>
633 where
634 V: de::DeserializeSeed<'de>,
635 {
636 seed.deserialize(
637 self.value
638 .take()
639 .expect("next_value is called before next_key")
640 .into_deserializer(self.scratch),
641 )
642 }
643
644 fn size_hint(&self) -> Option<usize> {
645 self.iter.size_hint().1
646 }
647 }
648}
649
650#[cfg(test)]
651mod tests {
652 use std::borrow::Cow;
653
654 use super::BracketsQS;
655
656 #[test]
657 fn parse_pair() {
658 let slice = b"key=value";
659
660 let parser = BracketsQS::parse(slice);
661
662 assert_eq!(parser.keys(), vec![&Cow::Borrowed(b"key")]);
663 assert_eq!(
664 parser.values(b"key"),
665 Some(vec![Some(Cow::Borrowed("value".as_bytes()))])
666 );
667 assert_eq!(
668 parser.value(b"key"),
669 Some(Some(Cow::Borrowed("value".as_bytes())))
670 );
671
672 assert_eq!(parser.values(b"test"), None);
673 }
674
675 #[test]
676 fn parse_multiple_pairs() {
677 let slice = b"foo=bar&foobar=baz&qux=box";
678
679 let parser = BracketsQS::parse(slice);
680
681 assert_eq!(
682 parser.values(b"foo"),
683 Some(vec![Some("bar".as_bytes().into())])
684 );
685 assert_eq!(
686 parser.values(b"foobar"),
687 Some(vec![Some("baz".as_bytes().into())])
688 );
689 assert_eq!(
690 parser.values(b"qux"),
691 Some(vec![Some("box".as_bytes().into())])
692 );
693 }
694
695 #[test]
696 fn parse_no_value() {
697 let slice = b"foo&foobar=";
698
699 let parser = BracketsQS::parse(slice);
700
701 assert_eq!(parser.values(b"foo"), Some(vec![None]));
702 assert_eq!(
703 parser.values(b"foobar"),
704 Some(vec![Some("".as_bytes().into())])
705 );
706 }
707
708 #[test]
709 fn parse_multiple_values() {
710 let slice = b"foo=bar&foo=baz&foo=foobar&foo&foo=";
711
712 let parser = BracketsQS::parse(slice);
713
714 assert_eq!(
715 parser.values(b"foo"),
716 Some(vec![
717 Some("bar".as_bytes().into()),
718 Some("baz".as_bytes().into()),
719 Some("foobar".as_bytes().into()),
720 None,
721 Some("".as_bytes().into())
722 ])
723 );
724
725 assert_eq!(parser.value(b"foo"), Some(Some("".as_bytes().into())));
726 }
727
728 #[test]
729 fn parse_subkeys() {
730 let slice = b"foo[bar]=baz&foo[bar]=buzz&foo[foobar]=qux&foo=bar";
731
732 let parser = BracketsQS::parse(slice);
733
734 assert_eq!(
735 parser.values(b"foo"),
736 Some(vec![Some("bar".as_bytes().into())])
737 );
738
739 let foo_values = parser.sub_values(b"foo");
740 assert!(foo_values.is_some());
741
742 let foo_values = foo_values.unwrap();
743
744 assert_eq!(
745 foo_values.values(b"bar"),
746 Some(vec![
747 Some("baz".as_bytes().into()),
748 Some("buzz".as_bytes().into())
749 ])
750 );
751
752 assert_eq!(
753 foo_values.values(b"foobar"),
754 Some(vec![Some("qux".as_bytes().into())])
755 )
756 }
757
758 #[test]
759 fn parse_invalid() {
760 let slice = b"foo[bar]xyz=baz&foo[bar][xyz=buzz&foo[foobar]xyz]=qux&foo[xyz=bar";
763
764 let parser = BracketsQS::parse(slice);
765
766 assert_eq!(
767 parser.values(b"foo"),
768 Some(vec![Some("bar".as_bytes().into())])
769 );
770
771 let foo_values = parser.sub_values(b"foo");
772 assert!(foo_values.is_some());
773
774 let foo_values = foo_values.unwrap();
775
776 assert_eq!(
777 foo_values.values(b"bar"),
778 Some(vec![
779 Some("baz".as_bytes().into()),
780 Some("buzz".as_bytes().into())
781 ])
782 );
783
784 assert_eq!(
785 foo_values.values(b"foobar"),
786 Some(vec![Some("qux".as_bytes().into())])
787 )
788 }
789}