1 /*
2  * nghttp2 - HTTP/2 C Library
3  *
4  * Copyright (c) 2012 Tatsuhiro Tsujikawa
5  *
6  * Permission is hereby granted, free of charge, to any person obtaining
7  * a copy of this software and associated documentation files (the
8  * "Software"), to deal in the Software without restriction, including
9  * without limitation the rights to use, copy, modify, merge, publish,
10  * distribute, sublicense, and/or sell copies of the Software, and to
11  * permit persons to whom the Software is furnished to do so, subject to
12  * the following conditions:
13  *
14  * The above copyright notice and this permission notice shall be
15  * included in all copies or substantial portions of the Software.
16  *
17  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
18  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
19  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
20  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
21  * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
22  * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
23  * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
24  */
25 #include "http2.h"
26 
27 #include "llhttp.h"
28 
29 #include "util.h"
30 
31 namespace nghttp2 {
32 
33 namespace http2 {
34 
get_reason_phrase(unsigned int status_code)35 StringRef get_reason_phrase(unsigned int status_code) {
36   switch (status_code) {
37   case 100:
38     return StringRef::from_lit("Continue");
39   case 101:
40     return StringRef::from_lit("Switching Protocols");
41   case 103:
42     return StringRef::from_lit("Early Hints");
43   case 200:
44     return StringRef::from_lit("OK");
45   case 201:
46     return StringRef::from_lit("Created");
47   case 202:
48     return StringRef::from_lit("Accepted");
49   case 203:
50     return StringRef::from_lit("Non-Authoritative Information");
51   case 204:
52     return StringRef::from_lit("No Content");
53   case 205:
54     return StringRef::from_lit("Reset Content");
55   case 206:
56     return StringRef::from_lit("Partial Content");
57   case 300:
58     return StringRef::from_lit("Multiple Choices");
59   case 301:
60     return StringRef::from_lit("Moved Permanently");
61   case 302:
62     return StringRef::from_lit("Found");
63   case 303:
64     return StringRef::from_lit("See Other");
65   case 304:
66     return StringRef::from_lit("Not Modified");
67   case 305:
68     return StringRef::from_lit("Use Proxy");
69   // case 306: return StringRef::from_lit("(Unused)");
70   case 307:
71     return StringRef::from_lit("Temporary Redirect");
72   case 308:
73     return StringRef::from_lit("Permanent Redirect");
74   case 400:
75     return StringRef::from_lit("Bad Request");
76   case 401:
77     return StringRef::from_lit("Unauthorized");
78   case 402:
79     return StringRef::from_lit("Payment Required");
80   case 403:
81     return StringRef::from_lit("Forbidden");
82   case 404:
83     return StringRef::from_lit("Not Found");
84   case 405:
85     return StringRef::from_lit("Method Not Allowed");
86   case 406:
87     return StringRef::from_lit("Not Acceptable");
88   case 407:
89     return StringRef::from_lit("Proxy Authentication Required");
90   case 408:
91     return StringRef::from_lit("Request Timeout");
92   case 409:
93     return StringRef::from_lit("Conflict");
94   case 410:
95     return StringRef::from_lit("Gone");
96   case 411:
97     return StringRef::from_lit("Length Required");
98   case 412:
99     return StringRef::from_lit("Precondition Failed");
100   case 413:
101     return StringRef::from_lit("Payload Too Large");
102   case 414:
103     return StringRef::from_lit("URI Too Long");
104   case 415:
105     return StringRef::from_lit("Unsupported Media Type");
106   case 416:
107     return StringRef::from_lit("Requested Range Not Satisfiable");
108   case 417:
109     return StringRef::from_lit("Expectation Failed");
110   case 421:
111     return StringRef::from_lit("Misdirected Request");
112   case 425:
113     // https://tools.ietf.org/html/rfc8470
114     return StringRef::from_lit("Too Early");
115   case 426:
116     return StringRef::from_lit("Upgrade Required");
117   case 428:
118     return StringRef::from_lit("Precondition Required");
119   case 429:
120     return StringRef::from_lit("Too Many Requests");
121   case 431:
122     return StringRef::from_lit("Request Header Fields Too Large");
123   case 451:
124     return StringRef::from_lit("Unavailable For Legal Reasons");
125   case 500:
126     return StringRef::from_lit("Internal Server Error");
127   case 501:
128     return StringRef::from_lit("Not Implemented");
129   case 502:
130     return StringRef::from_lit("Bad Gateway");
131   case 503:
132     return StringRef::from_lit("Service Unavailable");
133   case 504:
134     return StringRef::from_lit("Gateway Timeout");
135   case 505:
136     return StringRef::from_lit("HTTP Version Not Supported");
137   case 511:
138     return StringRef::from_lit("Network Authentication Required");
139   default:
140     return StringRef{};
141   }
142 }
143 
stringify_status(BlockAllocator & balloc,unsigned int status_code)144 StringRef stringify_status(BlockAllocator &balloc, unsigned int status_code) {
145   switch (status_code) {
146   case 100:
147     return StringRef::from_lit("100");
148   case 101:
149     return StringRef::from_lit("101");
150   case 103:
151     return StringRef::from_lit("103");
152   case 200:
153     return StringRef::from_lit("200");
154   case 201:
155     return StringRef::from_lit("201");
156   case 202:
157     return StringRef::from_lit("202");
158   case 203:
159     return StringRef::from_lit("203");
160   case 204:
161     return StringRef::from_lit("204");
162   case 205:
163     return StringRef::from_lit("205");
164   case 206:
165     return StringRef::from_lit("206");
166   case 300:
167     return StringRef::from_lit("300");
168   case 301:
169     return StringRef::from_lit("301");
170   case 302:
171     return StringRef::from_lit("302");
172   case 303:
173     return StringRef::from_lit("303");
174   case 304:
175     return StringRef::from_lit("304");
176   case 305:
177     return StringRef::from_lit("305");
178   // case 306: return StringRef::from_lit("306");
179   case 307:
180     return StringRef::from_lit("307");
181   case 308:
182     return StringRef::from_lit("308");
183   case 400:
184     return StringRef::from_lit("400");
185   case 401:
186     return StringRef::from_lit("401");
187   case 402:
188     return StringRef::from_lit("402");
189   case 403:
190     return StringRef::from_lit("403");
191   case 404:
192     return StringRef::from_lit("404");
193   case 405:
194     return StringRef::from_lit("405");
195   case 406:
196     return StringRef::from_lit("406");
197   case 407:
198     return StringRef::from_lit("407");
199   case 408:
200     return StringRef::from_lit("408");
201   case 409:
202     return StringRef::from_lit("409");
203   case 410:
204     return StringRef::from_lit("410");
205   case 411:
206     return StringRef::from_lit("411");
207   case 412:
208     return StringRef::from_lit("412");
209   case 413:
210     return StringRef::from_lit("413");
211   case 414:
212     return StringRef::from_lit("414");
213   case 415:
214     return StringRef::from_lit("415");
215   case 416:
216     return StringRef::from_lit("416");
217   case 417:
218     return StringRef::from_lit("417");
219   case 421:
220     return StringRef::from_lit("421");
221   case 426:
222     return StringRef::from_lit("426");
223   case 428:
224     return StringRef::from_lit("428");
225   case 429:
226     return StringRef::from_lit("429");
227   case 431:
228     return StringRef::from_lit("431");
229   case 451:
230     return StringRef::from_lit("451");
231   case 500:
232     return StringRef::from_lit("500");
233   case 501:
234     return StringRef::from_lit("501");
235   case 502:
236     return StringRef::from_lit("502");
237   case 503:
238     return StringRef::from_lit("503");
239   case 504:
240     return StringRef::from_lit("504");
241   case 505:
242     return StringRef::from_lit("505");
243   case 511:
244     return StringRef::from_lit("511");
245   default:
246     return util::make_string_ref_uint(balloc, status_code);
247   }
248 }
249 
capitalize(DefaultMemchunks * buf,const StringRef & s)250 void capitalize(DefaultMemchunks *buf, const StringRef &s) {
251   buf->append(util::upcase(s[0]));
252   for (size_t i = 1; i < s.size(); ++i) {
253     if (s[i - 1] == '-') {
254       buf->append(util::upcase(s[i]));
255     } else {
256       buf->append(s[i]);
257     }
258   }
259 }
260 
lws(const char * value)261 bool lws(const char *value) {
262   for (; *value; ++value) {
263     switch (*value) {
264     case '\t':
265     case ' ':
266       continue;
267     default:
268       return false;
269     }
270   }
271   return true;
272 }
273 
copy_url_component(std::string & dest,const http_parser_url * u,int field,const char * url)274 void copy_url_component(std::string &dest, const http_parser_url *u, int field,
275                         const char *url) {
276   if (u->field_set & (1 << field)) {
277     dest.assign(url + u->field_data[field].off, u->field_data[field].len);
278   }
279 }
280 
to_header(const uint8_t * name,size_t namelen,const uint8_t * value,size_t valuelen,bool no_index,int32_t token)281 Headers::value_type to_header(const uint8_t *name, size_t namelen,
282                               const uint8_t *value, size_t valuelen,
283                               bool no_index, int32_t token) {
284   return Header(std::string(reinterpret_cast<const char *>(name), namelen),
285                 std::string(reinterpret_cast<const char *>(value), valuelen),
286                 no_index, token);
287 }
288 
add_header(Headers & nva,const uint8_t * name,size_t namelen,const uint8_t * value,size_t valuelen,bool no_index,int32_t token)289 void add_header(Headers &nva, const uint8_t *name, size_t namelen,
290                 const uint8_t *value, size_t valuelen, bool no_index,
291                 int32_t token) {
292   if (valuelen > 0) {
293     size_t i, j;
294     for (i = 0; i < valuelen && (value[i] == ' ' || value[i] == '\t'); ++i)
295       ;
296     for (j = valuelen - 1; j > i && (value[j] == ' ' || value[j] == '\t'); --j)
297       ;
298     value += i;
299     valuelen -= i + (valuelen - j - 1);
300   }
301   nva.push_back(to_header(name, namelen, value, valuelen, no_index, token));
302 }
303 
get_header(const Headers & nva,const char * name)304 const Headers::value_type *get_header(const Headers &nva, const char *name) {
305   const Headers::value_type *res = nullptr;
306   for (auto &nv : nva) {
307     if (nv.name == name) {
308       res = &nv;
309     }
310   }
311   return res;
312 }
313 
non_empty_value(const HeaderRefs::value_type * nv)314 bool non_empty_value(const HeaderRefs::value_type *nv) {
315   return nv && !nv->value.empty();
316 }
317 
318 namespace {
make_nv_internal(const std::string & name,const std::string & value,bool no_index,uint8_t nv_flags)319 nghttp2_nv make_nv_internal(const std::string &name, const std::string &value,
320                             bool no_index, uint8_t nv_flags) {
321   uint8_t flags;
322 
323   flags =
324       nv_flags | (no_index ? NGHTTP2_NV_FLAG_NO_INDEX : NGHTTP2_NV_FLAG_NONE);
325 
326   return {(uint8_t *)name.c_str(), (uint8_t *)value.c_str(), name.size(),
327           value.size(), flags};
328 }
329 } // namespace
330 
331 namespace {
make_nv_internal(const StringRef & name,const StringRef & value,bool no_index,uint8_t nv_flags)332 nghttp2_nv make_nv_internal(const StringRef &name, const StringRef &value,
333                             bool no_index, uint8_t nv_flags) {
334   uint8_t flags;
335 
336   flags =
337       nv_flags | (no_index ? NGHTTP2_NV_FLAG_NO_INDEX : NGHTTP2_NV_FLAG_NONE);
338 
339   return {(uint8_t *)name.c_str(), (uint8_t *)value.c_str(), name.size(),
340           value.size(), flags};
341 }
342 } // namespace
343 
make_nv(const std::string & name,const std::string & value,bool no_index)344 nghttp2_nv make_nv(const std::string &name, const std::string &value,
345                    bool no_index) {
346   return make_nv_internal(name, value, no_index, NGHTTP2_NV_FLAG_NONE);
347 }
348 
make_nv(const StringRef & name,const StringRef & value,bool no_index)349 nghttp2_nv make_nv(const StringRef &name, const StringRef &value,
350                    bool no_index) {
351   return make_nv_internal(name, value, no_index, NGHTTP2_NV_FLAG_NONE);
352 }
353 
make_nv_nocopy(const std::string & name,const std::string & value,bool no_index)354 nghttp2_nv make_nv_nocopy(const std::string &name, const std::string &value,
355                           bool no_index) {
356   return make_nv_internal(name, value, no_index,
357                           NGHTTP2_NV_FLAG_NO_COPY_NAME |
358                               NGHTTP2_NV_FLAG_NO_COPY_VALUE);
359 }
360 
make_nv_nocopy(const StringRef & name,const StringRef & value,bool no_index)361 nghttp2_nv make_nv_nocopy(const StringRef &name, const StringRef &value,
362                           bool no_index) {
363   return make_nv_internal(name, value, no_index,
364                           NGHTTP2_NV_FLAG_NO_COPY_NAME |
365                               NGHTTP2_NV_FLAG_NO_COPY_VALUE);
366 }
367 
368 namespace {
copy_headers_to_nva_internal(std::vector<nghttp2_nv> & nva,const HeaderRefs & headers,uint8_t nv_flags,uint32_t flags)369 void copy_headers_to_nva_internal(std::vector<nghttp2_nv> &nva,
370                                   const HeaderRefs &headers, uint8_t nv_flags,
371                                   uint32_t flags) {
372   auto it_forwarded = std::end(headers);
373   auto it_xff = std::end(headers);
374   auto it_xfp = std::end(headers);
375   auto it_via = std::end(headers);
376 
377   for (auto it = std::begin(headers); it != std::end(headers); ++it) {
378     auto kv = &(*it);
379     if (kv->name.empty() || kv->name[0] == ':') {
380       continue;
381     }
382     switch (kv->token) {
383     case HD_COOKIE:
384     case HD_CONNECTION:
385     case HD_HOST:
386     case HD_HTTP2_SETTINGS:
387     case HD_KEEP_ALIVE:
388     case HD_PROXY_CONNECTION:
389     case HD_SERVER:
390     case HD_TE:
391     case HD_TRANSFER_ENCODING:
392     case HD_UPGRADE:
393       continue;
394     case HD_EARLY_DATA:
395       if (flags & HDOP_STRIP_EARLY_DATA) {
396         continue;
397       }
398       break;
399     case HD_SEC_WEBSOCKET_ACCEPT:
400       if (flags & HDOP_STRIP_SEC_WEBSOCKET_ACCEPT) {
401         continue;
402       }
403       break;
404     case HD_SEC_WEBSOCKET_KEY:
405       if (flags & HDOP_STRIP_SEC_WEBSOCKET_KEY) {
406         continue;
407       }
408       break;
409     case HD_FORWARDED:
410       if (flags & HDOP_STRIP_FORWARDED) {
411         continue;
412       }
413 
414       if (it_forwarded == std::end(headers)) {
415         it_forwarded = it;
416         continue;
417       }
418 
419       kv = &(*it_forwarded);
420       it_forwarded = it;
421       break;
422     case HD_X_FORWARDED_FOR:
423       if (flags & HDOP_STRIP_X_FORWARDED_FOR) {
424         continue;
425       }
426 
427       if (it_xff == std::end(headers)) {
428         it_xff = it;
429         continue;
430       }
431 
432       kv = &(*it_xff);
433       it_xff = it;
434       break;
435     case HD_X_FORWARDED_PROTO:
436       if (flags & HDOP_STRIP_X_FORWARDED_PROTO) {
437         continue;
438       }
439 
440       if (it_xfp == std::end(headers)) {
441         it_xfp = it;
442         continue;
443       }
444 
445       kv = &(*it_xfp);
446       it_xfp = it;
447       break;
448     case HD_VIA:
449       if (flags & HDOP_STRIP_VIA) {
450         continue;
451       }
452 
453       if (it_via == std::end(headers)) {
454         it_via = it;
455         continue;
456       }
457 
458       kv = &(*it_via);
459       it_via = it;
460       break;
461     }
462     nva.push_back(
463         make_nv_internal(kv->name, kv->value, kv->no_index, nv_flags));
464   }
465 }
466 } // namespace
467 
copy_headers_to_nva(std::vector<nghttp2_nv> & nva,const HeaderRefs & headers,uint32_t flags)468 void copy_headers_to_nva(std::vector<nghttp2_nv> &nva,
469                          const HeaderRefs &headers, uint32_t flags) {
470   copy_headers_to_nva_internal(nva, headers, NGHTTP2_NV_FLAG_NONE, flags);
471 }
472 
copy_headers_to_nva_nocopy(std::vector<nghttp2_nv> & nva,const HeaderRefs & headers,uint32_t flags)473 void copy_headers_to_nva_nocopy(std::vector<nghttp2_nv> &nva,
474                                 const HeaderRefs &headers, uint32_t flags) {
475   copy_headers_to_nva_internal(
476       nva, headers,
477       NGHTTP2_NV_FLAG_NO_COPY_NAME | NGHTTP2_NV_FLAG_NO_COPY_VALUE, flags);
478 }
479 
build_http1_headers_from_headers(DefaultMemchunks * buf,const HeaderRefs & headers,uint32_t flags)480 void build_http1_headers_from_headers(DefaultMemchunks *buf,
481                                       const HeaderRefs &headers,
482                                       uint32_t flags) {
483   auto it_forwarded = std::end(headers);
484   auto it_xff = std::end(headers);
485   auto it_xfp = std::end(headers);
486   auto it_via = std::end(headers);
487 
488   for (auto it = std::begin(headers); it != std::end(headers); ++it) {
489     auto kv = &(*it);
490     if (kv->name.empty() || kv->name[0] == ':') {
491       continue;
492     }
493     switch (kv->token) {
494     case HD_CONNECTION:
495     case HD_COOKIE:
496     case HD_HOST:
497     case HD_HTTP2_SETTINGS:
498     case HD_KEEP_ALIVE:
499     case HD_PROXY_CONNECTION:
500     case HD_SERVER:
501     case HD_UPGRADE:
502       continue;
503     case HD_EARLY_DATA:
504       if (flags & HDOP_STRIP_EARLY_DATA) {
505         continue;
506       }
507       break;
508     case HD_TRANSFER_ENCODING:
509       if (flags & HDOP_STRIP_TRANSFER_ENCODING) {
510         continue;
511       }
512       break;
513     case HD_FORWARDED:
514       if (flags & HDOP_STRIP_FORWARDED) {
515         continue;
516       }
517 
518       if (it_forwarded == std::end(headers)) {
519         it_forwarded = it;
520         continue;
521       }
522 
523       kv = &(*it_forwarded);
524       it_forwarded = it;
525       break;
526     case HD_X_FORWARDED_FOR:
527       if (flags & HDOP_STRIP_X_FORWARDED_FOR) {
528         continue;
529       }
530 
531       if (it_xff == std::end(headers)) {
532         it_xff = it;
533         continue;
534       }
535 
536       kv = &(*it_xff);
537       it_xff = it;
538       break;
539     case HD_X_FORWARDED_PROTO:
540       if (flags & HDOP_STRIP_X_FORWARDED_PROTO) {
541         continue;
542       }
543 
544       if (it_xfp == std::end(headers)) {
545         it_xfp = it;
546         continue;
547       }
548 
549       kv = &(*it_xfp);
550       it_xfp = it;
551       break;
552     case HD_VIA:
553       if (flags & HDOP_STRIP_VIA) {
554         continue;
555       }
556 
557       if (it_via == std::end(headers)) {
558         it_via = it;
559         continue;
560       }
561 
562       kv = &(*it_via);
563       it_via = it;
564       break;
565     }
566     capitalize(buf, kv->name);
567     buf->append(": ");
568     buf->append(kv->value);
569     buf->append("\r\n");
570   }
571 }
572 
determine_window_update_transmission(nghttp2_session * session,int32_t stream_id)573 int32_t determine_window_update_transmission(nghttp2_session *session,
574                                              int32_t stream_id) {
575   int32_t recv_length, window_size;
576   if (stream_id == 0) {
577     recv_length = nghttp2_session_get_effective_recv_data_length(session);
578     window_size = nghttp2_session_get_effective_local_window_size(session);
579   } else {
580     recv_length = nghttp2_session_get_stream_effective_recv_data_length(
581         session, stream_id);
582     window_size = nghttp2_session_get_stream_effective_local_window_size(
583         session, stream_id);
584   }
585   if (recv_length != -1 && window_size != -1) {
586     if (recv_length >= window_size / 2) {
587       return recv_length;
588     }
589   }
590   return -1;
591 }
592 
dump_nv(FILE * out,const char ** nv)593 void dump_nv(FILE *out, const char **nv) {
594   for (size_t i = 0; nv[i]; i += 2) {
595     fprintf(out, "%s: %s\n", nv[i], nv[i + 1]);
596   }
597   fputc('\n', out);
598   fflush(out);
599 }
600 
dump_nv(FILE * out,const nghttp2_nv * nva,size_t nvlen)601 void dump_nv(FILE *out, const nghttp2_nv *nva, size_t nvlen) {
602   auto end = nva + nvlen;
603   for (; nva != end; ++nva) {
604     fprintf(out, "%s: %s\n", nva->name, nva->value);
605   }
606   fputc('\n', out);
607   fflush(out);
608 }
609 
dump_nv(FILE * out,const Headers & nva)610 void dump_nv(FILE *out, const Headers &nva) {
611   for (auto &nv : nva) {
612     fprintf(out, "%s: %s\n", nv.name.c_str(), nv.value.c_str());
613   }
614   fputc('\n', out);
615   fflush(out);
616 }
617 
dump_nv(FILE * out,const HeaderRefs & nva)618 void dump_nv(FILE *out, const HeaderRefs &nva) {
619   for (auto &nv : nva) {
620     fprintf(out, "%s: %s\n", nv.name.c_str(), nv.value.c_str());
621   }
622   fputc('\n', out);
623   fflush(out);
624 }
625 
erase_header(HeaderRef * hd)626 void erase_header(HeaderRef *hd) {
627   hd->name = StringRef{};
628   hd->token = -1;
629 }
630 
rewrite_location_uri(BlockAllocator & balloc,const StringRef & uri,const http_parser_url & u,const StringRef & match_host,const StringRef & request_authority,const StringRef & upstream_scheme)631 StringRef rewrite_location_uri(BlockAllocator &balloc, const StringRef &uri,
632                                const http_parser_url &u,
633                                const StringRef &match_host,
634                                const StringRef &request_authority,
635                                const StringRef &upstream_scheme) {
636   // We just rewrite scheme and authority.
637   if ((u.field_set & (1 << UF_HOST)) == 0) {
638     return StringRef{};
639   }
640   auto field = &u.field_data[UF_HOST];
641   if (!util::starts_with(std::begin(match_host), std::end(match_host),
642                          &uri[field->off], &uri[field->off] + field->len) ||
643       (match_host.size() != field->len && match_host[field->len] != ':')) {
644     return StringRef{};
645   }
646 
647   auto len = 0;
648   if (!request_authority.empty()) {
649     len += upstream_scheme.size() + str_size("://") + request_authority.size();
650   }
651 
652   if (u.field_set & (1 << UF_PATH)) {
653     field = &u.field_data[UF_PATH];
654     len += field->len;
655   }
656 
657   if (u.field_set & (1 << UF_QUERY)) {
658     field = &u.field_data[UF_QUERY];
659     len += 1 + field->len;
660   }
661 
662   if (u.field_set & (1 << UF_FRAGMENT)) {
663     field = &u.field_data[UF_FRAGMENT];
664     len += 1 + field->len;
665   }
666 
667   auto iov = make_byte_ref(balloc, len + 1);
668   auto p = iov.base;
669 
670   if (!request_authority.empty()) {
671     p = std::copy(std::begin(upstream_scheme), std::end(upstream_scheme), p);
672     p = util::copy_lit(p, "://");
673     p = std::copy(std::begin(request_authority), std::end(request_authority),
674                   p);
675   }
676   if (u.field_set & (1 << UF_PATH)) {
677     field = &u.field_data[UF_PATH];
678     p = std::copy_n(&uri[field->off], field->len, p);
679   }
680   if (u.field_set & (1 << UF_QUERY)) {
681     field = &u.field_data[UF_QUERY];
682     *p++ = '?';
683     p = std::copy_n(&uri[field->off], field->len, p);
684   }
685   if (u.field_set & (1 << UF_FRAGMENT)) {
686     field = &u.field_data[UF_FRAGMENT];
687     *p++ = '#';
688     p = std::copy_n(&uri[field->off], field->len, p);
689   }
690 
691   *p = '\0';
692 
693   return StringRef{iov.base, p};
694 }
695 
check_nv(const uint8_t * name,size_t namelen,const uint8_t * value,size_t valuelen)696 int check_nv(const uint8_t *name, size_t namelen, const uint8_t *value,
697              size_t valuelen) {
698   if (!nghttp2_check_header_name(name, namelen)) {
699     return 0;
700   }
701   if (!nghttp2_check_header_value(value, valuelen)) {
702     return 0;
703   }
704   return 1;
705 }
706 
parse_http_status_code(const StringRef & src)707 int parse_http_status_code(const StringRef &src) {
708   if (src.size() != 3) {
709     return -1;
710   }
711 
712   int status = 0;
713   for (auto c : src) {
714     if (!isdigit(c)) {
715       return -1;
716     }
717     status *= 10;
718     status += c - '0';
719   }
720 
721   if (status < 100) {
722     return -1;
723   }
724 
725   return status;
726 }
727 
lookup_token(const StringRef & name)728 int lookup_token(const StringRef &name) {
729   return lookup_token(name.byte(), name.size());
730 }
731 
732 // This function was generated by genheaderfunc.py.  Inspired by h2o
733 // header lookup.  https://github.com/h2o/h2o
lookup_token(const uint8_t * name,size_t namelen)734 int lookup_token(const uint8_t *name, size_t namelen) {
735   switch (namelen) {
736   case 2:
737     switch (name[1]) {
738     case 'e':
739       if (util::streq_l("t", name, 1)) {
740         return HD_TE;
741       }
742       break;
743     }
744     break;
745   case 3:
746     switch (name[2]) {
747     case 'a':
748       if (util::streq_l("vi", name, 2)) {
749         return HD_VIA;
750       }
751       break;
752     }
753     break;
754   case 4:
755     switch (name[3]) {
756     case 'e':
757       if (util::streq_l("dat", name, 3)) {
758         return HD_DATE;
759       }
760       break;
761     case 'k':
762       if (util::streq_l("lin", name, 3)) {
763         return HD_LINK;
764       }
765       break;
766     case 't':
767       if (util::streq_l("hos", name, 3)) {
768         return HD_HOST;
769       }
770       break;
771     }
772     break;
773   case 5:
774     switch (name[4]) {
775     case 'h':
776       if (util::streq_l(":pat", name, 4)) {
777         return HD__PATH;
778       }
779       break;
780     case 't':
781       if (util::streq_l(":hos", name, 4)) {
782         return HD__HOST;
783       }
784       break;
785     }
786     break;
787   case 6:
788     switch (name[5]) {
789     case 'e':
790       if (util::streq_l("cooki", name, 5)) {
791         return HD_COOKIE;
792       }
793       break;
794     case 'r':
795       if (util::streq_l("serve", name, 5)) {
796         return HD_SERVER;
797       }
798       break;
799     case 't':
800       if (util::streq_l("expec", name, 5)) {
801         return HD_EXPECT;
802       }
803       break;
804     }
805     break;
806   case 7:
807     switch (name[6]) {
808     case 'c':
809       if (util::streq_l("alt-sv", name, 6)) {
810         return HD_ALT_SVC;
811       }
812       break;
813     case 'd':
814       if (util::streq_l(":metho", name, 6)) {
815         return HD__METHOD;
816       }
817       break;
818     case 'e':
819       if (util::streq_l(":schem", name, 6)) {
820         return HD__SCHEME;
821       }
822       if (util::streq_l("upgrad", name, 6)) {
823         return HD_UPGRADE;
824       }
825       break;
826     case 'r':
827       if (util::streq_l("traile", name, 6)) {
828         return HD_TRAILER;
829       }
830       break;
831     case 's':
832       if (util::streq_l(":statu", name, 6)) {
833         return HD__STATUS;
834       }
835       break;
836     }
837     break;
838   case 8:
839     switch (name[7]) {
840     case 'n':
841       if (util::streq_l("locatio", name, 7)) {
842         return HD_LOCATION;
843       }
844       break;
845     }
846     break;
847   case 9:
848     switch (name[8]) {
849     case 'd':
850       if (util::streq_l("forwarde", name, 8)) {
851         return HD_FORWARDED;
852       }
853       break;
854     case 'l':
855       if (util::streq_l(":protoco", name, 8)) {
856         return HD__PROTOCOL;
857       }
858       break;
859     }
860     break;
861   case 10:
862     switch (name[9]) {
863     case 'a':
864       if (util::streq_l("early-dat", name, 9)) {
865         return HD_EARLY_DATA;
866       }
867       break;
868     case 'e':
869       if (util::streq_l("keep-aliv", name, 9)) {
870         return HD_KEEP_ALIVE;
871       }
872       break;
873     case 'n':
874       if (util::streq_l("connectio", name, 9)) {
875         return HD_CONNECTION;
876       }
877       break;
878     case 't':
879       if (util::streq_l("user-agen", name, 9)) {
880         return HD_USER_AGENT;
881       }
882       break;
883     case 'y':
884       if (util::streq_l(":authorit", name, 9)) {
885         return HD__AUTHORITY;
886       }
887       break;
888     }
889     break;
890   case 12:
891     switch (name[11]) {
892     case 'e':
893       if (util::streq_l("content-typ", name, 11)) {
894         return HD_CONTENT_TYPE;
895       }
896       break;
897     }
898     break;
899   case 13:
900     switch (name[12]) {
901     case 'l':
902       if (util::streq_l("cache-contro", name, 12)) {
903         return HD_CACHE_CONTROL;
904       }
905       break;
906     }
907     break;
908   case 14:
909     switch (name[13]) {
910     case 'h':
911       if (util::streq_l("content-lengt", name, 13)) {
912         return HD_CONTENT_LENGTH;
913       }
914       break;
915     case 's':
916       if (util::streq_l("http2-setting", name, 13)) {
917         return HD_HTTP2_SETTINGS;
918       }
919       break;
920     }
921     break;
922   case 15:
923     switch (name[14]) {
924     case 'e':
925       if (util::streq_l("accept-languag", name, 14)) {
926         return HD_ACCEPT_LANGUAGE;
927       }
928       break;
929     case 'g':
930       if (util::streq_l("accept-encodin", name, 14)) {
931         return HD_ACCEPT_ENCODING;
932       }
933       break;
934     case 'r':
935       if (util::streq_l("x-forwarded-fo", name, 14)) {
936         return HD_X_FORWARDED_FOR;
937       }
938       break;
939     }
940     break;
941   case 16:
942     switch (name[15]) {
943     case 'n':
944       if (util::streq_l("proxy-connectio", name, 15)) {
945         return HD_PROXY_CONNECTION;
946       }
947       break;
948     }
949     break;
950   case 17:
951     switch (name[16]) {
952     case 'e':
953       if (util::streq_l("if-modified-sinc", name, 16)) {
954         return HD_IF_MODIFIED_SINCE;
955       }
956       break;
957     case 'g':
958       if (util::streq_l("transfer-encodin", name, 16)) {
959         return HD_TRANSFER_ENCODING;
960       }
961       break;
962     case 'o':
963       if (util::streq_l("x-forwarded-prot", name, 16)) {
964         return HD_X_FORWARDED_PROTO;
965       }
966       break;
967     case 'y':
968       if (util::streq_l("sec-websocket-ke", name, 16)) {
969         return HD_SEC_WEBSOCKET_KEY;
970       }
971       break;
972     }
973     break;
974   case 20:
975     switch (name[19]) {
976     case 't':
977       if (util::streq_l("sec-websocket-accep", name, 19)) {
978         return HD_SEC_WEBSOCKET_ACCEPT;
979       }
980       break;
981     }
982     break;
983   }
984   return -1;
985 }
986 
init_hdidx(HeaderIndex & hdidx)987 void init_hdidx(HeaderIndex &hdidx) {
988   std::fill(std::begin(hdidx), std::end(hdidx), -1);
989 }
990 
index_header(HeaderIndex & hdidx,int32_t token,size_t idx)991 void index_header(HeaderIndex &hdidx, int32_t token, size_t idx) {
992   if (token == -1) {
993     return;
994   }
995   assert(token < HD_MAXIDX);
996   hdidx[token] = idx;
997 }
998 
get_header(const HeaderIndex & hdidx,int32_t token,const Headers & nva)999 const Headers::value_type *get_header(const HeaderIndex &hdidx, int32_t token,
1000                                       const Headers &nva) {
1001   auto i = hdidx[token];
1002   if (i == -1) {
1003     return nullptr;
1004   }
1005   return &nva[i];
1006 }
1007 
get_header(const HeaderIndex & hdidx,int32_t token,Headers & nva)1008 Headers::value_type *get_header(const HeaderIndex &hdidx, int32_t token,
1009                                 Headers &nva) {
1010   auto i = hdidx[token];
1011   if (i == -1) {
1012     return nullptr;
1013   }
1014   return &nva[i];
1015 }
1016 
1017 namespace {
skip_lws(InputIt first,InputIt last)1018 template <typename InputIt> InputIt skip_lws(InputIt first, InputIt last) {
1019   for (; first != last; ++first) {
1020     switch (*first) {
1021     case ' ':
1022     case '\t':
1023       continue;
1024     default:
1025       return first;
1026     }
1027   }
1028   return first;
1029 }
1030 } // namespace
1031 
1032 namespace {
1033 template <typename InputIt>
skip_to_next_field(InputIt first,InputIt last)1034 InputIt skip_to_next_field(InputIt first, InputIt last) {
1035   for (; first != last; ++first) {
1036     switch (*first) {
1037     case ' ':
1038     case '\t':
1039     case ',':
1040       continue;
1041     default:
1042       return first;
1043     }
1044   }
1045   return first;
1046 }
1047 } // namespace
1048 
1049 namespace {
1050 // Skip to the right dquote ('"'), handling backslash escapes.
1051 // Returns |last| if input is not terminated with '"'.
1052 template <typename InputIt>
skip_to_right_dquote(InputIt first,InputIt last)1053 InputIt skip_to_right_dquote(InputIt first, InputIt last) {
1054   for (; first != last;) {
1055     switch (*first) {
1056     case '"':
1057       return first;
1058     case '\\':
1059       ++first;
1060       if (first == last) {
1061         return first;
1062       }
1063       break;
1064     }
1065     ++first;
1066   }
1067   return first;
1068 }
1069 } // namespace
1070 
1071 namespace {
1072 // Returns true if link-param does not match pattern |pat| of length
1073 // |patlen| or it has empty value ("").  |pat| should be parmname
1074 // followed by "=".
check_link_param_empty(const char * first,const char * last,const char * pat,size_t patlen)1075 bool check_link_param_empty(const char *first, const char *last,
1076                             const char *pat, size_t patlen) {
1077   if (first + patlen <= last) {
1078     if (std::equal(pat, pat + patlen, first, util::CaseCmp())) {
1079       // we only accept URI if pat is followd by "" (e.g.,
1080       // loadpolicy="") here.
1081       if (first + patlen + 2 <= last) {
1082         if (*(first + patlen) != '"' || *(first + patlen + 1) != '"') {
1083           return false;
1084         }
1085       } else {
1086         // here we got invalid production (anchor=") or anchor=?
1087         return false;
1088       }
1089     }
1090   }
1091   return true;
1092 }
1093 } // namespace
1094 
1095 namespace {
1096 // Returns true if link-param consists of only parmname, and it
1097 // matches string [pat, pat + patlen).
check_link_param_without_value(const char * first,const char * last,const char * pat,size_t patlen)1098 bool check_link_param_without_value(const char *first, const char *last,
1099                                     const char *pat, size_t patlen) {
1100   if (first + patlen > last) {
1101     return false;
1102   }
1103 
1104   if (first + patlen == last) {
1105     return std::equal(pat, pat + patlen, first, util::CaseCmp());
1106   }
1107 
1108   switch (*(first + patlen)) {
1109   case ';':
1110   case ',':
1111     return std::equal(pat, pat + patlen, first, util::CaseCmp());
1112   }
1113 
1114   return false;
1115 }
1116 } // namespace
1117 
1118 namespace {
1119 std::pair<LinkHeader, const char *>
parse_next_link_header_once(const char * first,const char * last)1120 parse_next_link_header_once(const char *first, const char *last) {
1121   first = skip_to_next_field(first, last);
1122   if (first == last || *first != '<') {
1123     return {{StringRef{}}, last};
1124   }
1125   auto url_first = ++first;
1126   first = std::find(first, last, '>');
1127   if (first == last) {
1128     return {{StringRef{}}, first};
1129   }
1130   auto url_last = first++;
1131   if (first == last) {
1132     return {{StringRef{}}, first};
1133   }
1134   // we expect ';' or ',' here
1135   switch (*first) {
1136   case ',':
1137     return {{StringRef{}}, ++first};
1138   case ';':
1139     ++first;
1140     break;
1141   default:
1142     return {{StringRef{}}, last};
1143   }
1144 
1145   auto ok = false;
1146   auto ign = false;
1147   for (;;) {
1148     first = skip_lws(first, last);
1149     if (first == last) {
1150       return {{StringRef{}}, first};
1151     }
1152     // we expect link-param
1153 
1154     if (!ign) {
1155       if (!ok) {
1156         // rel can take several relations using quoted form.
1157         static constexpr char PLP[] = "rel=\"";
1158         static constexpr size_t PLPLEN = str_size(PLP);
1159 
1160         static constexpr char PLT[] = "preload";
1161         static constexpr size_t PLTLEN = str_size(PLT);
1162         if (first + PLPLEN < last && *(first + PLPLEN - 1) == '"' &&
1163             std::equal(PLP, PLP + PLPLEN, first, util::CaseCmp())) {
1164           // we have to search preload in whitespace separated list:
1165           // rel="preload something http://example.org/foo"
1166           first += PLPLEN;
1167           auto start = first;
1168           for (; first != last;) {
1169             if (*first != ' ' && *first != '"') {
1170               ++first;
1171               continue;
1172             }
1173 
1174             if (start == first) {
1175               return {{StringRef{}}, last};
1176             }
1177 
1178             if (!ok && start + PLTLEN == first &&
1179                 std::equal(PLT, PLT + PLTLEN, start, util::CaseCmp())) {
1180               ok = true;
1181             }
1182 
1183             if (*first == '"') {
1184               break;
1185             }
1186             first = skip_lws(first, last);
1187             start = first;
1188           }
1189           if (first == last) {
1190             return {{StringRef{}}, last};
1191           }
1192           assert(*first == '"');
1193           ++first;
1194           if (first == last || *first == ',') {
1195             goto almost_done;
1196           }
1197           if (*first == ';') {
1198             ++first;
1199             // parse next link-param
1200             continue;
1201           }
1202           return {{StringRef{}}, last};
1203         }
1204       }
1205       // we are only interested in rel=preload parameter.  Others are
1206       // simply skipped.
1207       static constexpr char PL[] = "rel=preload";
1208       static constexpr size_t PLLEN = str_size(PL);
1209       if (first + PLLEN == last) {
1210         if (std::equal(PL, PL + PLLEN, first, util::CaseCmp())) {
1211           // ok = true;
1212           // this is the end of sequence
1213           return {{{url_first, url_last}}, last};
1214         }
1215       } else if (first + PLLEN + 1 <= last) {
1216         switch (*(first + PLLEN)) {
1217         case ',':
1218           if (!std::equal(PL, PL + PLLEN, first, util::CaseCmp())) {
1219             break;
1220           }
1221           // ok = true;
1222           // skip including ','
1223           first += PLLEN + 1;
1224           return {{{url_first, url_last}}, first};
1225         case ';':
1226           if (!std::equal(PL, PL + PLLEN, first, util::CaseCmp())) {
1227             break;
1228           }
1229           ok = true;
1230           // skip including ';'
1231           first += PLLEN + 1;
1232           // continue parse next link-param
1233           continue;
1234         }
1235       }
1236       // we have to reject URI if we have nonempty anchor parameter.
1237       static constexpr char ANCHOR[] = "anchor=";
1238       static constexpr size_t ANCHORLEN = str_size(ANCHOR);
1239       if (!ign && !check_link_param_empty(first, last, ANCHOR, ANCHORLEN)) {
1240         ign = true;
1241       }
1242 
1243       // reject URI if we have non-empty loadpolicy.  This could be
1244       // tightened up to just pick up "next" or "insert".
1245       static constexpr char LOADPOLICY[] = "loadpolicy=";
1246       static constexpr size_t LOADPOLICYLEN = str_size(LOADPOLICY);
1247       if (!ign &&
1248           !check_link_param_empty(first, last, LOADPOLICY, LOADPOLICYLEN)) {
1249         ign = true;
1250       }
1251 
1252       // reject URI if we have nopush attribute.
1253       static constexpr char NOPUSH[] = "nopush";
1254       static constexpr size_t NOPUSHLEN = str_size(NOPUSH);
1255       if (!ign &&
1256           check_link_param_without_value(first, last, NOPUSH, NOPUSHLEN)) {
1257         ign = true;
1258       }
1259     }
1260 
1261     auto param_first = first;
1262     for (; first != last;) {
1263       if (util::in_attr_char(*first)) {
1264         ++first;
1265         continue;
1266       }
1267       // '*' is only allowed at the end of parameter name and must be
1268       // followed by '='
1269       if (last - first >= 2 && first != param_first) {
1270         if (*first == '*' && *(first + 1) == '=') {
1271           ++first;
1272           break;
1273         }
1274       }
1275       if (*first == '=' || *first == ';' || *first == ',') {
1276         break;
1277       }
1278       return {{StringRef{}}, last};
1279     }
1280     if (param_first == first) {
1281       // empty parmname
1282       return {{StringRef{}}, last};
1283     }
1284     // link-param without value is acceptable (see link-extension) if
1285     // it is not followed by '='
1286     if (first == last || *first == ',') {
1287       goto almost_done;
1288     }
1289     if (*first == ';') {
1290       ++first;
1291       // parse next link-param
1292       continue;
1293     }
1294     // now parsing link-param value
1295     assert(*first == '=');
1296     ++first;
1297     if (first == last) {
1298       // empty value is not acceptable
1299       return {{StringRef{}}, first};
1300     }
1301     if (*first == '"') {
1302       // quoted-string
1303       first = skip_to_right_dquote(first + 1, last);
1304       if (first == last) {
1305         return {{StringRef{}}, first};
1306       }
1307       ++first;
1308       if (first == last || *first == ',') {
1309         goto almost_done;
1310       }
1311       if (*first == ';') {
1312         ++first;
1313         // parse next link-param
1314         continue;
1315       }
1316       return {{StringRef{}}, last};
1317     }
1318     // not quoted-string, skip to next ',' or ';'
1319     if (*first == ',' || *first == ';') {
1320       // empty value
1321       return {{StringRef{}}, last};
1322     }
1323     for (; first != last; ++first) {
1324       if (*first == ',' || *first == ';') {
1325         break;
1326       }
1327     }
1328     if (first == last || *first == ',') {
1329       goto almost_done;
1330     }
1331     assert(*first == ';');
1332     ++first;
1333     // parse next link-param
1334   }
1335 
1336 almost_done:
1337   assert(first == last || *first == ',');
1338 
1339   if (first != last) {
1340     ++first;
1341   }
1342   if (ok && !ign) {
1343     return {{{url_first, url_last}}, first};
1344   }
1345   return {{StringRef{}}, first};
1346 }
1347 } // namespace
1348 
parse_link_header(const StringRef & src)1349 std::vector<LinkHeader> parse_link_header(const StringRef &src) {
1350   std::vector<LinkHeader> res;
1351   for (auto first = std::begin(src); first != std::end(src);) {
1352     auto rv = parse_next_link_header_once(first, std::end(src));
1353     first = rv.second;
1354     auto &link = rv.first;
1355     if (!link.uri.empty()) {
1356       res.push_back(link);
1357     }
1358   }
1359   return res;
1360 }
1361 
path_join(const StringRef & base_path,const StringRef & base_query,const StringRef & rel_path,const StringRef & rel_query)1362 std::string path_join(const StringRef &base_path, const StringRef &base_query,
1363                       const StringRef &rel_path, const StringRef &rel_query) {
1364   BlockAllocator balloc(1024, 1024);
1365 
1366   return path_join(balloc, base_path, base_query, rel_path, rel_query).str();
1367 }
1368 
expect_response_body(int status_code)1369 bool expect_response_body(int status_code) {
1370   return status_code == 101 ||
1371          (status_code / 100 != 1 && status_code != 304 && status_code != 204);
1372 }
1373 
expect_response_body(const std::string & method,int status_code)1374 bool expect_response_body(const std::string &method, int status_code) {
1375   return method != "HEAD" && expect_response_body(status_code);
1376 }
1377 
expect_response_body(int method_token,int status_code)1378 bool expect_response_body(int method_token, int status_code) {
1379   return method_token != HTTP_HEAD && expect_response_body(status_code);
1380 }
1381 
lookup_method_token(const StringRef & name)1382 int lookup_method_token(const StringRef &name) {
1383   return lookup_method_token(name.byte(), name.size());
1384 }
1385 
1386 // This function was generated by genmethodfunc.py.
lookup_method_token(const uint8_t * name,size_t namelen)1387 int lookup_method_token(const uint8_t *name, size_t namelen) {
1388   switch (namelen) {
1389   case 3:
1390     switch (name[2]) {
1391     case 'L':
1392       if (util::streq_l("AC", name, 2)) {
1393         return HTTP_ACL;
1394       }
1395       break;
1396     case 'T':
1397       if (util::streq_l("GE", name, 2)) {
1398         return HTTP_GET;
1399       }
1400       if (util::streq_l("PU", name, 2)) {
1401         return HTTP_PUT;
1402       }
1403       break;
1404     }
1405     break;
1406   case 4:
1407     switch (name[3]) {
1408     case 'D':
1409       if (util::streq_l("BIN", name, 3)) {
1410         return HTTP_BIND;
1411       }
1412       if (util::streq_l("HEA", name, 3)) {
1413         return HTTP_HEAD;
1414       }
1415       break;
1416     case 'E':
1417       if (util::streq_l("MOV", name, 3)) {
1418         return HTTP_MOVE;
1419       }
1420       break;
1421     case 'K':
1422       if (util::streq_l("LIN", name, 3)) {
1423         return HTTP_LINK;
1424       }
1425       if (util::streq_l("LOC", name, 3)) {
1426         return HTTP_LOCK;
1427       }
1428       break;
1429     case 'T':
1430       if (util::streq_l("POS", name, 3)) {
1431         return HTTP_POST;
1432       }
1433       break;
1434     case 'Y':
1435       if (util::streq_l("COP", name, 3)) {
1436         return HTTP_COPY;
1437       }
1438       break;
1439     }
1440     break;
1441   case 5:
1442     switch (name[4]) {
1443     case 'E':
1444       if (util::streq_l("MERG", name, 4)) {
1445         return HTTP_MERGE;
1446       }
1447       if (util::streq_l("PURG", name, 4)) {
1448         return HTTP_PURGE;
1449       }
1450       if (util::streq_l("TRAC", name, 4)) {
1451         return HTTP_TRACE;
1452       }
1453       break;
1454     case 'H':
1455       if (util::streq_l("PATC", name, 4)) {
1456         return HTTP_PATCH;
1457       }
1458       break;
1459     case 'L':
1460       if (util::streq_l("MKCO", name, 4)) {
1461         return HTTP_MKCOL;
1462       }
1463       break;
1464     }
1465     break;
1466   case 6:
1467     switch (name[5]) {
1468     case 'D':
1469       if (util::streq_l("REBIN", name, 5)) {
1470         return HTTP_REBIND;
1471       }
1472       if (util::streq_l("UNBIN", name, 5)) {
1473         return HTTP_UNBIND;
1474       }
1475       break;
1476     case 'E':
1477       if (util::streq_l("DELET", name, 5)) {
1478         return HTTP_DELETE;
1479       }
1480       if (util::streq_l("SOURC", name, 5)) {
1481         return HTTP_SOURCE;
1482       }
1483       break;
1484     case 'H':
1485       if (util::streq_l("SEARC", name, 5)) {
1486         return HTTP_SEARCH;
1487       }
1488       break;
1489     case 'K':
1490       if (util::streq_l("UNLIN", name, 5)) {
1491         return HTTP_UNLINK;
1492       }
1493       if (util::streq_l("UNLOC", name, 5)) {
1494         return HTTP_UNLOCK;
1495       }
1496       break;
1497     case 'T':
1498       if (util::streq_l("REPOR", name, 5)) {
1499         return HTTP_REPORT;
1500       }
1501       break;
1502     case 'Y':
1503       if (util::streq_l("NOTIF", name, 5)) {
1504         return HTTP_NOTIFY;
1505       }
1506       break;
1507     }
1508     break;
1509   case 7:
1510     switch (name[6]) {
1511     case 'H':
1512       if (util::streq_l("MSEARC", name, 6)) {
1513         return HTTP_MSEARCH;
1514       }
1515       break;
1516     case 'S':
1517       if (util::streq_l("OPTION", name, 6)) {
1518         return HTTP_OPTIONS;
1519       }
1520       break;
1521     case 'T':
1522       if (util::streq_l("CONNEC", name, 6)) {
1523         return HTTP_CONNECT;
1524       }
1525       break;
1526     }
1527     break;
1528   case 8:
1529     switch (name[7]) {
1530     case 'D':
1531       if (util::streq_l("PROPFIN", name, 7)) {
1532         return HTTP_PROPFIND;
1533       }
1534       break;
1535     case 'T':
1536       if (util::streq_l("CHECKOU", name, 7)) {
1537         return HTTP_CHECKOUT;
1538       }
1539       break;
1540     }
1541     break;
1542   case 9:
1543     switch (name[8]) {
1544     case 'E':
1545       if (util::streq_l("SUBSCRIB", name, 8)) {
1546         return HTTP_SUBSCRIBE;
1547       }
1548       break;
1549     case 'H':
1550       if (util::streq_l("PROPPATC", name, 8)) {
1551         return HTTP_PROPPATCH;
1552       }
1553       break;
1554     }
1555     break;
1556   case 10:
1557     switch (name[9]) {
1558     case 'R':
1559       if (util::streq_l("MKCALENDA", name, 9)) {
1560         return HTTP_MKCALENDAR;
1561       }
1562       break;
1563     case 'Y':
1564       if (util::streq_l("MKACTIVIT", name, 9)) {
1565         return HTTP_MKACTIVITY;
1566       }
1567       break;
1568     }
1569     break;
1570   case 11:
1571     switch (name[10]) {
1572     case 'E':
1573       if (util::streq_l("UNSUBSCRIB", name, 10)) {
1574         return HTTP_UNSUBSCRIBE;
1575       }
1576       break;
1577     }
1578     break;
1579   }
1580   return -1;
1581 }
1582 
to_method_string(int method_token)1583 StringRef to_method_string(int method_token) {
1584   // we happened to use same value for method with llhttp.
1585   return StringRef{
1586       llhttp_method_name(static_cast<llhttp_method>(method_token))};
1587 }
1588 
get_pure_path_component(const StringRef & uri)1589 StringRef get_pure_path_component(const StringRef &uri) {
1590   int rv;
1591 
1592   http_parser_url u{};
1593   rv = http_parser_parse_url(uri.c_str(), uri.size(), 0, &u);
1594   if (rv != 0) {
1595     return StringRef{};
1596   }
1597 
1598   if (u.field_set & (1 << UF_PATH)) {
1599     auto &f = u.field_data[UF_PATH];
1600     return StringRef{uri.c_str() + f.off, f.len};
1601   }
1602 
1603   return StringRef::from_lit("/");
1604 }
1605 
construct_push_component(BlockAllocator & balloc,StringRef & scheme,StringRef & authority,StringRef & path,const StringRef & base,const StringRef & uri)1606 int construct_push_component(BlockAllocator &balloc, StringRef &scheme,
1607                              StringRef &authority, StringRef &path,
1608                              const StringRef &base, const StringRef &uri) {
1609   int rv;
1610   StringRef rel, relq;
1611 
1612   if (uri.size() == 0) {
1613     return -1;
1614   }
1615 
1616   http_parser_url u{};
1617 
1618   rv = http_parser_parse_url(uri.c_str(), uri.size(), 0, &u);
1619 
1620   if (rv != 0) {
1621     if (uri[0] == '/') {
1622       return -1;
1623     }
1624 
1625     // treat link_url as relative URI.
1626     auto end = std::find(std::begin(uri), std::end(uri), '#');
1627     auto q = std::find(std::begin(uri), end, '?');
1628 
1629     rel = StringRef{std::begin(uri), q};
1630     if (q != end) {
1631       relq = StringRef{q + 1, std::end(uri)};
1632     }
1633   } else {
1634     if (u.field_set & (1 << UF_SCHEMA)) {
1635       scheme = util::get_uri_field(uri.c_str(), u, UF_SCHEMA);
1636     }
1637 
1638     if (u.field_set & (1 << UF_HOST)) {
1639       auto auth = util::get_uri_field(uri.c_str(), u, UF_HOST);
1640       auto len = auth.size();
1641       auto port_exists = u.field_set & (1 << UF_PORT);
1642       if (port_exists) {
1643         len += 1 + str_size("65535");
1644       }
1645       auto iov = make_byte_ref(balloc, len + 1);
1646       auto p = iov.base;
1647       p = std::copy(std::begin(auth), std::end(auth), p);
1648       if (port_exists) {
1649         *p++ = ':';
1650         p = util::utos(p, u.port);
1651       }
1652       *p = '\0';
1653 
1654       authority = StringRef{iov.base, p};
1655     }
1656 
1657     if (u.field_set & (1 << UF_PATH)) {
1658       auto &f = u.field_data[UF_PATH];
1659       rel = StringRef{uri.c_str() + f.off, f.len};
1660     } else {
1661       rel = StringRef::from_lit("/");
1662     }
1663 
1664     if (u.field_set & (1 << UF_QUERY)) {
1665       auto &f = u.field_data[UF_QUERY];
1666       relq = StringRef{uri.c_str() + f.off, f.len};
1667     }
1668   }
1669 
1670   path = http2::path_join(balloc, base, StringRef{}, rel, relq);
1671 
1672   return 0;
1673 }
1674 
1675 namespace {
eat_file(InputIt first,InputIt last)1676 template <typename InputIt> InputIt eat_file(InputIt first, InputIt last) {
1677   if (first == last) {
1678     *first++ = '/';
1679     return first;
1680   }
1681 
1682   if (*(last - 1) == '/') {
1683     return last;
1684   }
1685 
1686   auto p = last;
1687   for (; p != first && *(p - 1) != '/'; --p)
1688     ;
1689   if (p == first) {
1690     // this should not happened in normal case, where we expect path
1691     // starts with '/'
1692     *first++ = '/';
1693     return first;
1694   }
1695 
1696   return p;
1697 }
1698 } // namespace
1699 
1700 namespace {
eat_dir(InputIt first,InputIt last)1701 template <typename InputIt> InputIt eat_dir(InputIt first, InputIt last) {
1702   auto p = eat_file(first, last);
1703 
1704   --p;
1705 
1706   assert(*p == '/');
1707 
1708   return eat_file(first, p);
1709 }
1710 } // namespace
1711 
path_join(BlockAllocator & balloc,const StringRef & base_path,const StringRef & base_query,const StringRef & rel_path,const StringRef & rel_query)1712 StringRef path_join(BlockAllocator &balloc, const StringRef &base_path,
1713                     const StringRef &base_query, const StringRef &rel_path,
1714                     const StringRef &rel_query) {
1715   auto res = make_byte_ref(
1716       balloc, std::max(static_cast<size_t>(1), base_path.size()) +
1717                   rel_path.size() + 1 +
1718                   std::max(base_query.size(), rel_query.size()) + 1);
1719   auto p = res.base;
1720 
1721   if (rel_path.empty()) {
1722     if (base_path.empty()) {
1723       *p++ = '/';
1724     } else {
1725       p = std::copy(std::begin(base_path), std::end(base_path), p);
1726     }
1727     if (rel_query.empty()) {
1728       if (!base_query.empty()) {
1729         *p++ = '?';
1730         p = std::copy(std::begin(base_query), std::end(base_query), p);
1731       }
1732       *p = '\0';
1733       return StringRef{res.base, p};
1734     }
1735     *p++ = '?';
1736     p = std::copy(std::begin(rel_query), std::end(rel_query), p);
1737     *p = '\0';
1738     return StringRef{res.base, p};
1739   }
1740 
1741   auto first = std::begin(rel_path);
1742   auto last = std::end(rel_path);
1743 
1744   if (rel_path[0] == '/') {
1745     *p++ = '/';
1746     ++first;
1747     for (; first != last && *first == '/'; ++first)
1748       ;
1749   } else if (base_path.empty()) {
1750     *p++ = '/';
1751   } else {
1752     p = std::copy(std::begin(base_path), std::end(base_path), p);
1753   }
1754 
1755   for (; first != last;) {
1756     if (*first == '.') {
1757       if (first + 1 == last) {
1758         break;
1759       }
1760       if (*(first + 1) == '/') {
1761         first += 2;
1762         continue;
1763       }
1764       if (*(first + 1) == '.') {
1765         if (first + 2 == last) {
1766           p = eat_dir(res.base, p);
1767           break;
1768         }
1769         if (*(first + 2) == '/') {
1770           p = eat_dir(res.base, p);
1771           first += 3;
1772           continue;
1773         }
1774       }
1775     }
1776     if (*(p - 1) != '/') {
1777       p = eat_file(res.base, p);
1778     }
1779     auto slash = std::find(first, last, '/');
1780     if (slash == last) {
1781       p = std::copy(first, last, p);
1782       break;
1783     }
1784     p = std::copy(first, slash + 1, p);
1785     first = slash + 1;
1786     for (; first != last && *first == '/'; ++first)
1787       ;
1788   }
1789   if (!rel_query.empty()) {
1790     *p++ = '?';
1791     p = std::copy(std::begin(rel_query), std::end(rel_query), p);
1792   }
1793   *p = '\0';
1794   return StringRef{res.base, p};
1795 }
1796 
normalize_path(BlockAllocator & balloc,const StringRef & path,const StringRef & query)1797 StringRef normalize_path(BlockAllocator &balloc, const StringRef &path,
1798                          const StringRef &query) {
1799   // First, decode %XX for unreserved characters, then do
1800   // http2::path_join
1801 
1802   // We won't find %XX if length is less than 3.
1803   if (path.size() < 3 ||
1804       std::find(std::begin(path), std::end(path), '%') == std::end(path)) {
1805     return path_join(balloc, StringRef{}, StringRef{}, path, query);
1806   }
1807 
1808   // includes last terminal NULL.
1809   auto result = make_byte_ref(balloc, path.size() + 1);
1810   auto p = result.base;
1811 
1812   auto it = std::begin(path);
1813   for (; it + 2 < std::end(path);) {
1814     if (*it == '%') {
1815       if (util::is_hex_digit(*(it + 1)) && util::is_hex_digit(*(it + 2))) {
1816         auto c =
1817             (util::hex_to_uint(*(it + 1)) << 4) + util::hex_to_uint(*(it + 2));
1818         if (util::in_rfc3986_unreserved_chars(c)) {
1819           *p++ = c;
1820 
1821           it += 3;
1822 
1823           continue;
1824         }
1825         *p++ = '%';
1826         *p++ = util::upcase(*(it + 1));
1827         *p++ = util::upcase(*(it + 2));
1828 
1829         it += 3;
1830 
1831         continue;
1832       }
1833     }
1834     *p++ = *it++;
1835   }
1836 
1837   p = std::copy(it, std::end(path), p);
1838   *p = '\0';
1839 
1840   return path_join(balloc, StringRef{}, StringRef{}, StringRef{result.base, p},
1841                    query);
1842 }
1843 
normalize_path_colon(BlockAllocator & balloc,const StringRef & path,const StringRef & query)1844 StringRef normalize_path_colon(BlockAllocator &balloc, const StringRef &path,
1845                                const StringRef &query) {
1846   // First, decode %XX for unreserved characters and ':', then do
1847   // http2::path_join
1848 
1849   // We won't find %XX if length is less than 3.
1850   if (path.size() < 3 ||
1851       std::find(std::begin(path), std::end(path), '%') == std::end(path)) {
1852     return path_join(balloc, StringRef{}, StringRef{}, path, query);
1853   }
1854 
1855   // includes last terminal NULL.
1856   auto result = make_byte_ref(balloc, path.size() + 1);
1857   auto p = result.base;
1858 
1859   auto it = std::begin(path);
1860   for (; it + 2 < std::end(path);) {
1861     if (*it == '%') {
1862       if (util::is_hex_digit(*(it + 1)) && util::is_hex_digit(*(it + 2))) {
1863         auto c =
1864             (util::hex_to_uint(*(it + 1)) << 4) + util::hex_to_uint(*(it + 2));
1865         if (util::in_rfc3986_unreserved_chars(c) || c == ':') {
1866           *p++ = c;
1867 
1868           it += 3;
1869 
1870           continue;
1871         }
1872         *p++ = '%';
1873         *p++ = util::upcase(*(it + 1));
1874         *p++ = util::upcase(*(it + 2));
1875 
1876         it += 3;
1877 
1878         continue;
1879       }
1880     }
1881     *p++ = *it++;
1882   }
1883 
1884   p = std::copy(it, std::end(path), p);
1885   *p = '\0';
1886 
1887   return path_join(balloc, StringRef{}, StringRef{}, StringRef{result.base, p},
1888                    query);
1889 }
1890 
normalize_path(const StringRef & path,const StringRef & query)1891 std::string normalize_path(const StringRef &path, const StringRef &query) {
1892   BlockAllocator balloc(1024, 1024);
1893 
1894   return normalize_path(balloc, path, query).str();
1895 }
1896 
rewrite_clean_path(BlockAllocator & balloc,const StringRef & src)1897 StringRef rewrite_clean_path(BlockAllocator &balloc, const StringRef &src) {
1898   if (src.empty() || src[0] != '/') {
1899     return src;
1900   }
1901   // probably, not necessary most of the case, but just in case.
1902   auto fragment = std::find(std::begin(src), std::end(src), '#');
1903   auto raw_query = std::find(std::begin(src), fragment, '?');
1904   auto query = raw_query;
1905   if (query != fragment) {
1906     ++query;
1907   }
1908   return normalize_path(balloc, StringRef{std::begin(src), raw_query},
1909                         StringRef{query, fragment});
1910 }
1911 
copy_lower(BlockAllocator & balloc,const StringRef & src)1912 StringRef copy_lower(BlockAllocator &balloc, const StringRef &src) {
1913   auto iov = make_byte_ref(balloc, src.size() + 1);
1914   auto p = iov.base;
1915   p = std::copy(std::begin(src), std::end(src), p);
1916   *p = '\0';
1917   util::inp_strlower(iov.base, p);
1918   return StringRef{iov.base, p};
1919 }
1920 
contains_trailers(const StringRef & s)1921 bool contains_trailers(const StringRef &s) {
1922   constexpr auto trailers = StringRef::from_lit("trailers");
1923 
1924   for (auto p = std::begin(s), end = std::end(s);; ++p) {
1925     p = std::find_if(p, end, [](char c) { return c != ' ' && c != '\t'; });
1926     if (p == end || static_cast<size_t>(end - p) < trailers.size()) {
1927       return false;
1928     }
1929     if (util::strieq(trailers, StringRef{p, p + trailers.size()})) {
1930       // Make sure that there is no character other than white spaces
1931       // before next "," or end of string.
1932       p = std::find_if(p + trailers.size(), end,
1933                        [](char c) { return c != ' ' && c != '\t'; });
1934       if (p == end || *p == ',') {
1935         return true;
1936       }
1937     }
1938     // Skip to next ",".
1939     p = std::find_if(p, end, [](char c) { return c == ','; });
1940     if (p == end) {
1941       return false;
1942     }
1943   }
1944 }
1945 
make_websocket_accept_token(uint8_t * dest,const StringRef & key)1946 StringRef make_websocket_accept_token(uint8_t *dest, const StringRef &key) {
1947   static constexpr uint8_t magic[] = "258EAFA5-E914-47DA-95CA-C5AB0DC85B11";
1948   std::array<uint8_t, base64::encode_length(16) + str_size(magic)> s;
1949   auto p = std::copy(std::begin(key), std::end(key), std::begin(s));
1950   std::copy_n(magic, str_size(magic), p);
1951 
1952   std::array<uint8_t, 20> h;
1953   if (util::sha1(h.data(), StringRef{std::begin(s), std::end(s)}) != 0) {
1954     return StringRef{};
1955   }
1956 
1957   auto end = base64::encode(std::begin(h), std::end(h), dest);
1958   return StringRef{dest, end};
1959 }
1960 
legacy_http1(int major,int minor)1961 bool legacy_http1(int major, int minor) {
1962   return major <= 0 || (major == 1 && minor == 0);
1963 }
1964 
1965 } // namespace http2
1966 
1967 } // namespace nghttp2
1968