1use http::header::*;
2use http::*;
3
4use quickcheck::{Arbitrary, Gen, QuickCheck, TestResult};
5use rand::rngs::StdRng;
6use rand::seq::SliceRandom;
7use rand::{Rng, SeedableRng};
8
9use std::collections::HashMap;
10
11#[cfg(not(miri))]
12#[test]
13fn header_map_fuzz() {
14 fn prop(fuzz: Fuzz) -> TestResult {
15 fuzz.run();
16 TestResult::from_bool(true)
17 }
18
19 QuickCheck::new().quickcheck(prop as fn(Fuzz) -> TestResult)
20}
21
22#[derive(Debug, Clone)]
23#[allow(dead_code)]
24struct Fuzz {
25 // The magic seed that makes the test case reproducible
26 seed: [u8; 32],
27
28 // Actions to perform
29 steps: Vec<Step>,
30
31 // Number of steps to drop
32 reduce: usize,
33}
34
35#[derive(Debug)]
36struct Weight {
37 insert: usize,
38 remove: usize,
39 append: usize,
40}
41
42#[derive(Debug, Clone)]
43struct Step {
44 action: Action,
45 expect: AltMap,
46}
47
48#[derive(Debug, Clone)]
49enum Action {
50 Insert {
51 name: HeaderName, // Name to insert
52 val: HeaderValue, // Value to insert
53 old: Option<HeaderValue>, // Old value
54 },
55 Append {
56 name: HeaderName,
57 val: HeaderValue,
58 ret: bool,
59 },
60 Remove {
61 name: HeaderName, // Name to remove
62 val: Option<HeaderValue>, // Value to get
63 },
64}
65
66// An alternate implementation of HeaderMap backed by HashMap
67#[derive(Debug, Clone, Default)]
68struct AltMap {
69 map: HashMap<HeaderName, Vec<HeaderValue>>,
70}
71
72impl Fuzz {
73 fn new(seed: [u8; 32]) -> Fuzz {
74 // Seed the RNG
75 let mut rng = StdRng::from_seed(seed);
76
77 let mut steps = vec![];
78 let mut expect = AltMap::default();
79 let num = rng.gen_range(5, 500);
80
81 let weight = Weight {
82 insert: rng.gen_range(1, 10),
83 remove: rng.gen_range(1, 10),
84 append: rng.gen_range(1, 10),
85 };
86
87 while steps.len() < num {
88 steps.push(expect.gen_step(&weight, &mut rng));
89 }
90
91 Fuzz {
92 seed: seed,
93 steps: steps,
94 reduce: 0,
95 }
96 }
97
98 fn run(self) {
99 // Create a new header map
100 let mut map = HeaderMap::new();
101
102 // Number of steps to perform
103 let take = self.steps.len() - self.reduce;
104
105 for step in self.steps.into_iter().take(take) {
106 step.action.apply(&mut map);
107
108 step.expect.assert_identical(&map);
109 }
110 }
111}
112
113impl Arbitrary for Fuzz {
114 fn arbitrary<G: Gen>(g: &mut G) -> Self {
115 Fuzz::new(Rng::gen(g))
116 }
117}
118
119impl AltMap {
120 fn gen_step(&mut self, weight: &Weight, rng: &mut StdRng) -> Step {
121 let action = self.gen_action(weight, rng);
122
123 Step {
124 action: action,
125 expect: self.clone(),
126 }
127 }
128
129 /// This will also apply the action against `self`
130 fn gen_action(&mut self, weight: &Weight, rng: &mut StdRng) -> Action {
131 let sum = weight.insert + weight.remove + weight.append;
132
133 let mut num = rng.gen_range(0, sum);
134
135 if num < weight.insert {
136 return self.gen_insert(rng);
137 }
138
139 num -= weight.insert;
140
141 if num < weight.remove {
142 return self.gen_remove(rng);
143 }
144
145 num -= weight.remove;
146
147 if num < weight.append {
148 return self.gen_append(rng);
149 }
150
151 unreachable!();
152 }
153
154 fn gen_insert(&mut self, rng: &mut StdRng) -> Action {
155 let name = self.gen_name(4, rng);
156 let val = gen_header_value(rng);
157 let old = self.insert(name.clone(), val.clone());
158
159 Action::Insert {
160 name: name,
161 val: val,
162 old: old,
163 }
164 }
165
166 fn gen_remove(&mut self, rng: &mut StdRng) -> Action {
167 let name = self.gen_name(-4, rng);
168 let val = self.remove(&name);
169
170 Action::Remove {
171 name: name,
172 val: val,
173 }
174 }
175
176 fn gen_append(&mut self, rng: &mut StdRng) -> Action {
177 let name = self.gen_name(-5, rng);
178 let val = gen_header_value(rng);
179
180 let vals = self.map.entry(name.clone()).or_insert(vec![]);
181
182 let ret = !vals.is_empty();
183 vals.push(val.clone());
184
185 Action::Append {
186 name: name,
187 val: val,
188 ret: ret,
189 }
190 }
191
192 /// Negative numbers weigh finding an existing header higher
193 fn gen_name(&self, weight: i32, rng: &mut StdRng) -> HeaderName {
194 let mut existing = rng.gen_ratio(1, weight.abs() as u32);
195
196 if weight < 0 {
197 existing = !existing;
198 }
199
200 if existing {
201 // Existing header
202 if let Some(name) = self.find_random_name(rng) {
203 name
204 } else {
205 gen_header_name(rng)
206 }
207 } else {
208 gen_header_name(rng)
209 }
210 }
211
212 fn find_random_name(&self, rng: &mut StdRng) -> Option<HeaderName> {
213 if self.map.is_empty() {
214 None
215 } else {
216 let n = rng.gen_range(0, self.map.len());
217 self.map.keys().nth(n).map(Clone::clone)
218 }
219 }
220
221 fn insert(&mut self, name: HeaderName, val: HeaderValue) -> Option<HeaderValue> {
222 let old = self.map.insert(name, vec![val]);
223 old.and_then(|v| v.into_iter().next())
224 }
225
226 fn remove(&mut self, name: &HeaderName) -> Option<HeaderValue> {
227 self.map.remove(name).and_then(|v| v.into_iter().next())
228 }
229
230 fn assert_identical(&self, other: &HeaderMap<HeaderValue>) {
231 assert_eq!(self.map.len(), other.keys_len());
232
233 for (key, val) in &self.map {
234 // Test get
235 assert_eq!(other.get(key), val.get(0));
236
237 // Test get_all
238 let vals = other.get_all(key);
239 let actual: Vec<_> = vals.iter().collect();
240 assert_eq!(&actual[..], &val[..]);
241 }
242 }
243}
244
245impl Action {
246 fn apply(self, map: &mut HeaderMap<HeaderValue>) {
247 match self {
248 Action::Insert { name, val, old } => {
249 let actual = map.insert(name, val);
250 assert_eq!(actual, old);
251 }
252 Action::Remove { name, val } => {
253 // Just to help track the state, load all associated values.
254 let _ = map.get_all(&name).iter().collect::<Vec<_>>();
255
256 let actual = map.remove(&name);
257 assert_eq!(actual, val);
258 }
259 Action::Append { name, val, ret } => {
260 assert_eq!(ret, map.append(name, val));
261 }
262 }
263 }
264}
265
266fn gen_header_name(g: &mut StdRng) -> HeaderName {
267 const STANDARD_HEADERS: &'static [HeaderName] = &[
268 header::ACCEPT,
269 header::ACCEPT_CHARSET,
270 header::ACCEPT_ENCODING,
271 header::ACCEPT_LANGUAGE,
272 header::ACCEPT_RANGES,
273 header::ACCESS_CONTROL_ALLOW_CREDENTIALS,
274 header::ACCESS_CONTROL_ALLOW_HEADERS,
275 header::ACCESS_CONTROL_ALLOW_METHODS,
276 header::ACCESS_CONTROL_ALLOW_ORIGIN,
277 header::ACCESS_CONTROL_EXPOSE_HEADERS,
278 header::ACCESS_CONTROL_MAX_AGE,
279 header::ACCESS_CONTROL_REQUEST_HEADERS,
280 header::ACCESS_CONTROL_REQUEST_METHOD,
281 header::AGE,
282 header::ALLOW,
283 header::ALT_SVC,
284 header::AUTHORIZATION,
285 header::CACHE_CONTROL,
286 header::CACHE_STATUS,
287 header::CDN_CACHE_CONTROL,
288 header::CONNECTION,
289 header::CONTENT_DISPOSITION,
290 header::CONTENT_ENCODING,
291 header::CONTENT_LANGUAGE,
292 header::CONTENT_LENGTH,
293 header::CONTENT_LOCATION,
294 header::CONTENT_RANGE,
295 header::CONTENT_SECURITY_POLICY,
296 header::CONTENT_SECURITY_POLICY_REPORT_ONLY,
297 header::CONTENT_TYPE,
298 header::COOKIE,
299 header::DNT,
300 header::DATE,
301 header::ETAG,
302 header::EXPECT,
303 header::EXPIRES,
304 header::FORWARDED,
305 header::FROM,
306 header::HOST,
307 header::IF_MATCH,
308 header::IF_MODIFIED_SINCE,
309 header::IF_NONE_MATCH,
310 header::IF_RANGE,
311 header::IF_UNMODIFIED_SINCE,
312 header::LAST_MODIFIED,
313 header::LINK,
314 header::LOCATION,
315 header::MAX_FORWARDS,
316 header::ORIGIN,
317 header::PRAGMA,
318 header::PROXY_AUTHENTICATE,
319 header::PROXY_AUTHORIZATION,
320 header::PUBLIC_KEY_PINS,
321 header::PUBLIC_KEY_PINS_REPORT_ONLY,
322 header::RANGE,
323 header::REFERER,
324 header::REFERRER_POLICY,
325 header::REFRESH,
326 header::RETRY_AFTER,
327 header::SEC_WEBSOCKET_ACCEPT,
328 header::SEC_WEBSOCKET_EXTENSIONS,
329 header::SEC_WEBSOCKET_KEY,
330 header::SEC_WEBSOCKET_PROTOCOL,
331 header::SEC_WEBSOCKET_VERSION,
332 header::SERVER,
333 header::SET_COOKIE,
334 header::STRICT_TRANSPORT_SECURITY,
335 header::TE,
336 header::TRAILER,
337 header::TRANSFER_ENCODING,
338 header::UPGRADE,
339 header::UPGRADE_INSECURE_REQUESTS,
340 header::USER_AGENT,
341 header::VARY,
342 header::VIA,
343 header::WARNING,
344 header::WWW_AUTHENTICATE,
345 header::X_CONTENT_TYPE_OPTIONS,
346 header::X_DNS_PREFETCH_CONTROL,
347 header::X_FRAME_OPTIONS,
348 header::X_XSS_PROTECTION,
349 ];
350
351 if g.gen_ratio(1, 2) {
352 STANDARD_HEADERS.choose(g).unwrap().clone()
353 } else {
354 let value = gen_string(g, 1, 25);
355 HeaderName::from_bytes(value.as_bytes()).unwrap()
356 }
357}
358
359fn gen_header_value(g: &mut StdRng) -> HeaderValue {
360 let value = gen_string(g, 0, 70);
361 HeaderValue::from_bytes(value.as_bytes()).unwrap()
362}
363
364fn gen_string(g: &mut StdRng, min: usize, max: usize) -> String {
365 let bytes: Vec<_> = (min..max)
366 .map(|_| {
367 // Chars to pick from
368 b"ABCDEFGHIJKLMNOPQRSTUVabcdefghilpqrstuvwxyz----"
369 .choose(g)
370 .unwrap()
371 .clone()
372 })
373 .collect();
374
375 String::from_utf8(bytes).unwrap()
376}
377