src/http2.cc

   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 "util.h"
  28
  29 namespace nghttp2 {
  30
  31 namespace http2 {
  32
  33 std::string get_status_string(unsigned int status_code) {
  34   switch (status_code) {
  35   case 100:
  36     return "100 Continue";
  37   case 101:
  38     return "101 Switching Protocols";
  39   case 200:
  40     return "200 OK";
  41   case 201:
  42     return "201 Created";
  43   case 202:
  44     return "202 Accepted";
  45   case 203:
  46     return "203 Non-Authoritative Information";
  47   case 204:
  48     return "204 No Content";
  49   case 205:
  50     return "205 Reset Content";
  51   case 206:
  52     return "206 Partial Content";
  53   case 300:
  54     return "300 Multiple Choices";
  55   case 301:
  56     return "301 Moved Permanently";
  57   case 302:
  58     return "302 Found";
  59   case 303:
  60     return "303 See Other";
  61   case 304:
  62     return "304 Not Modified";
  63   case 305:
  64     return "305 Use Proxy";
  65   // case 306: return "306 (Unused)";
  66   case 307:
  67     return "307 Temporary Redirect";
  68   case 308:
  69     return "308 Permanent Redirect";
  70   case 400:
  71     return "400 Bad Request";
  72   case 401:
  73     return "401 Unauthorized";
  74   case 402:
  75     return "402 Payment Required";
  76   case 403:
  77     return "403 Forbidden";
  78   case 404:
  79     return "404 Not Found";
  80   case 405:
  81     return "405 Method Not Allowed";
  82   case 406:
  83     return "406 Not Acceptable";
  84   case 407:
  85     return "407 Proxy Authentication Required";
  86   case 408:
  87     return "408 Request Timeout";
  88   case 409:
  89     return "409 Conflict";
  90   case 410:
  91     return "410 Gone";
  92   case 411:
  93     return "411 Length Required";
  94   case 412:
  95     return "412 Precondition Failed";
  96   case 413:
  97     return "413 Payload Too Large";
  98   case 414:
  99     return "414 URI Too Long";
 100   case 415:
 101     return "415 Unsupported Media Type";
 102   case 416:
 103     return "416 Requested Range Not Satisfiable";
 104   case 417:
 105     return "417 Expectation Failed";
 106   case 421:
 107     return "421 Misdirected Request";
 108   case 426:
 109     return "426 Upgrade Required";
 110   case 428:
 111     return "428 Precondition Required";
 112   case 429:
 113     return "429 Too Many Requests";
 114   case 431:
 115     return "431 Request Header Fields Too Large";
 116   case 500:
 117     return "500 Internal Server Error";
 118   case 501:
 119     return "501 Not Implemented";
 120   case 502:
 121     return "502 Bad Gateway";
 122   case 503:
 123     return "503 Service Unavailable";
 124   case 504:
 125     return "504 Gateway Timeout";
 126   case 505:
 127     return "505 HTTP Version Not Supported";
 128   case 511:
 129     return "511 Network Authentication Required";
 130   default:
 131     return util::utos(status_code);
 132   }
 133 }
 134
 135 void capitalize(std::string &s, size_t offset) {
 136   s[offset] = util::upcase(s[offset]);
 137   for (size_t i = offset + 1, eoi = s.size(); i < eoi; ++i) {
 138     if (s[i - 1] == '-') {
 139       s[i] = util::upcase(s[i]);
 140     } else {
 141       s[i] = util::lowcase(s[i]);
 142     }
 143   }
 144 }
 145
 146 bool lws(const char *value) {
 147   for (; *value; ++value) {
 148     switch (*value) {
 149     case '\t':
 150     case ' ':
 151       continue;
 152     default:
 153       return false;
 154     }
 155   }
 156   return true;
 157 }
 158
 159 void copy_url_component(std::string &dest, const http_parser_url *u, int field,
 160                         const char *url) {
 161   if (u->field_set & (1 << field)) {
 162     dest.assign(url + u->field_data[field].off, u->field_data[field].len);
 163   }
 164 }
 165
 166 Headers::value_type to_header(const uint8_t *name, size_t namelen,
 167                               const uint8_t *value, size_t valuelen,
 168                               bool no_index, int16_t token) {
 169   return Header(std::string(reinterpret_cast<const char *>(name), namelen),
 170                 std::string(reinterpret_cast<const char *>(value), valuelen),
 171                 no_index, token);
 172 }
 173
 174 void add_header(Headers &nva, const uint8_t *name, size_t namelen,
 175                 const uint8_t *value, size_t valuelen, bool no_index,
 176                 int16_t token) {
 177   if (valuelen > 0) {
 178     size_t i, j;
 179     for (i = 0; i < valuelen && (value[i] == ' ' || value[i] == '\t'); ++i)
 180       ;
 181     for (j = valuelen - 1; j > i && (value[j] == ' ' || value[j] == '\t'); --j)
 182       ;
 183     value += i;
 184     valuelen -= i + (valuelen - j - 1);
 185   }
 186   nva.push_back(to_header(name, namelen, value, valuelen, no_index, token));
 187 }
 188
 189 const Headers::value_type *get_header(const Headers &nva, const char *name) {
 190   const Headers::value_type *res = nullptr;
 191   for (auto &nv : nva) {
 192     if (nv.name == name) {
 193       res = &nv;
 194     }
 195   }
 196   return res;
 197 }
 198
 199 std::string value_to_str(const Headers::value_type *nv) {
 200   if (nv) {
 201     return nv->value;
 202   }
 203   return "";
 204 }
 205
 206 bool non_empty_value(const Headers::value_type *nv) {
 207   return nv && !nv->value.empty();
 208 }
 209
 210 nghttp2_nv make_nv(const std::string &name, const std::string &value,
 211                    bool no_index) {
 212   uint8_t flags;
 213
 214   flags = no_index ? NGHTTP2_NV_FLAG_NO_INDEX : NGHTTP2_NV_FLAG_NONE;
 215
 216   return {(uint8_t *)name.c_str(), (uint8_t *)value.c_str(), name.size(),
 217           value.size(), flags};
 218 }
 219
 220 void copy_headers_to_nva(std::vector<nghttp2_nv> &nva, const Headers &headers) {
 221   for (auto &kv : headers) {
 222     if (kv.name.empty() || kv.name[0] == ':') {
 223       continue;
 224     }
 225     switch (kv.token) {
 226     case HD_COOKIE:
 227     case HD_CONNECTION:
 228     case HD_HOST:
 229     case HD_HTTP2_SETTINGS:
 230     case HD_KEEP_ALIVE:
 231     case HD_PROXY_CONNECTION:
 232     case HD_SERVER:
 233     case HD_TE:
 234     case HD_TRANSFER_ENCODING:
 235     case HD_UPGRADE:
 236     case HD_VIA:
 237     case HD_X_FORWARDED_FOR:
 238     case HD_X_FORWARDED_PROTO:
 239       continue;
 240     }
 241     nva.push_back(make_nv(kv.name, kv.value, kv.no_index));
 242   }
 243 }
 244
 245 void build_http1_headers_from_headers(std::string &hdrs,
 246                                       const Headers &headers) {
 247   for (auto &kv : headers) {
 248     if (kv.name.empty() || kv.name[0] == ':') {
 249       continue;
 250     }
 251     switch (kv.token) {
 252     case HD_CONNECTION:
 253     case HD_COOKIE:
 254     case HD_HOST:
 255     case HD_HTTP2_SETTINGS:
 256     case HD_KEEP_ALIVE:
 257     case HD_PROXY_CONNECTION:
 258     case HD_SERVER:
 259     case HD_UPGRADE:
 260     case HD_VIA:
 261     case HD_X_FORWARDED_FOR:
 262     case HD_X_FORWARDED_PROTO:
 263       continue;
 264     }
 265     hdrs += kv.name;
 266     capitalize(hdrs, hdrs.size() - kv.name.size());
 267     hdrs += ": ";
 268     hdrs += kv.value;
 269     hdrs += "\r\n";
 270   }
 271 }
 272
 273 int32_t determine_window_update_transmission(nghttp2_session *session,
 274                                              int32_t stream_id) {
 275   int32_t recv_length, window_size;
 276   if (stream_id == 0) {
 277     recv_length = nghttp2_session_get_effective_recv_data_length(session);
 278     window_size = nghttp2_session_get_effective_local_window_size(session);
 279   } else {
 280     recv_length = nghttp2_session_get_stream_effective_recv_data_length(
 281         session, stream_id);
 282     window_size = nghttp2_session_get_stream_effective_local_window_size(
 283         session, stream_id);
 284   }
 285   if (recv_length != -1 && window_size != -1) {
 286     if (recv_length >= window_size / 2) {
 287       return recv_length;
 288     }
 289   }
 290   return -1;
 291 }
 292
 293 void dump_nv(FILE *out, const char **nv) {
 294   for (size_t i = 0; nv[i]; i += 2) {
 295     fprintf(out, "%s: %s\n", nv[i], nv[i + 1]);
 296   }
 297   fputc('\n', out);
 298   fflush(out);
 299 }
 300
 301 void dump_nv(FILE *out, const nghttp2_nv *nva, size_t nvlen) {
 302   auto end = nva + nvlen;
 303   for (; nva != end; ++nva) {
 304     fprintf(out, "%s: %s\n", nva->name, nva->value);
 305   }
 306   fputc('\n', out);
 307   fflush(out);
 308 }
 309
 310 void dump_nv(FILE *out, const Headers &nva) {
 311   for (auto &nv : nva) {
 312     fprintf(out, "%s: %s\n", nv.name.c_str(), nv.value.c_str());
 313   }
 314   fputc('\n', out);
 315   fflush(out);
 316 }
 317
 318 std::string rewrite_location_uri(const std::string &uri,
 319                                  const http_parser_url &u,
 320                                  const std::string &match_host,
 321                                  const std::string &request_authority,
 322                                  const std::string &upstream_scheme) {
 323   // We just rewrite scheme and authority.
 324   if ((u.field_set & (1 << UF_HOST)) == 0) {
 325     return "";
 326   }
 327   auto field = &u.field_data[UF_HOST];
 328   if (!util::startsWith(std::begin(match_host), std::end(match_host),
 329                         &uri[field->off], &uri[field->off] + field->len) ||
 330       (match_host.size() != field->len && match_host[field->len] != ':')) {
 331     return "";
 332   }
 333   std::string res;
 334   if (!request_authority.empty()) {
 335     res += upstream_scheme;
 336     res += "://";
 337     res += request_authority;
 338   }
 339   if (u.field_set & (1 << UF_PATH)) {
 340     field = &u.field_data[UF_PATH];
 341     res.append(&uri[field->off], field->len);
 342   }
 343   if (u.field_set & (1 << UF_QUERY)) {
 344     field = &u.field_data[UF_QUERY];
 345     res += "?";
 346     res.append(&uri[field->off], field->len);
 347   }
 348   if (u.field_set & (1 << UF_FRAGMENT)) {
 349     field = &u.field_data[UF_FRAGMENT];
 350     res += "#";
 351     res.append(&uri[field->off], field->len);
 352   }
 353   return res;
 354 }
 355
 356 int check_nv(const uint8_t *name, size_t namelen, const uint8_t *value,
 357              size_t valuelen) {
 358   if (!nghttp2_check_header_name(name, namelen)) {
 359     return 0;
 360   }
 361   if (!nghttp2_check_header_value(value, valuelen)) {
 362     return 0;
 363   }
 364   return 1;
 365 }
 366
 367 int parse_http_status_code(const std::string &src) {
 368   if (src.size() != 3) {
 369     return -1;
 370   }
 371
 372   int status = 0;
 373   for (auto c : src) {
 374     if (!isdigit(c)) {
 375       return -1;
 376     }
 377     status *= 10;
 378     status += c - '0';
 379   }
 380
 381   if (status < 100) {
 382     return -1;
 383   }
 384
 385   return status;
 386 }
 387
 388 int lookup_token(const std::string &name) {
 389   return lookup_token(reinterpret_cast<const uint8_t *>(name.c_str()),
 390                       name.size());
 391 }
 392
 393 // This function was generated by genheaderfunc.py.  Inspired by h2o
 394 // header lookup.  https://github.com/h2o/h2o
 395 int lookup_token(const uint8_t *name, size_t namelen) {
 396   switch (namelen) {
 397   case 2:
 398     switch (name[1]) {
 399     case 'e':
 400       if (util::streq_l("t", name, 1)) {
 401         return HD_TE;
 402       }
 403       break;
 404     }
 405     break;
 406   case 3:
 407     switch (name[2]) {
 408     case 'a':
 409       if (util::streq_l("vi", name, 2)) {
 410         return HD_VIA;
 411       }
 412       break;
 413     }
 414     break;
 415   case 4:
 416     switch (name[3]) {
 417     case 'k':
 418       if (util::streq_l("lin", name, 3)) {
 419         return HD_LINK;
 420       }
 421       break;
 422     case 't':
 423       if (util::streq_l("hos", name, 3)) {
 424         return HD_HOST;
 425       }
 426       break;
 427     }
 428     break;
 429   case 5:
 430     switch (name[4]) {
 431     case 'h':
 432       if (util::streq_l(":pat", name, 4)) {
 433         return HD__PATH;
 434       }
 435       break;
 436     case 't':
 437       if (util::streq_l(":hos", name, 4)) {
 438         return HD__HOST;
 439       }
 440       break;
 441     }
 442     break;
 443   case 6:
 444     switch (name[5]) {
 445     case 'e':
 446       if (util::streq_l("cooki", name, 5)) {
 447         return HD_COOKIE;
 448       }
 449       break;
 450     case 'r':
 451       if (util::streq_l("serve", name, 5)) {
 452         return HD_SERVER;
 453       }
 454       break;
 455     case 't':
 456       if (util::streq_l("expec", name, 5)) {
 457         return HD_EXPECT;
 458       }
 459       break;
 460     }
 461     break;
 462   case 7:
 463     switch (name[6]) {
 464     case 'c':
 465       if (util::streq_l("alt-sv", name, 6)) {
 466         return HD_ALT_SVC;
 467       }
 468       break;
 469     case 'd':
 470       if (util::streq_l(":metho", name, 6)) {
 471         return HD__METHOD;
 472       }
 473       break;
 474     case 'e':
 475       if (util::streq_l(":schem", name, 6)) {
 476         return HD__SCHEME;
 477       }
 478       if (util::streq_l("upgrad", name, 6)) {
 479         return HD_UPGRADE;
 480       }
 481       break;
 482     case 'r':
 483       if (util::streq_l("traile", name, 6)) {
 484         return HD_TRAILER;
 485       }
 486       break;
 487     case 's':
 488       if (util::streq_l(":statu", name, 6)) {
 489         return HD__STATUS;
 490       }
 491       break;
 492     }
 493     break;
 494   case 8:
 495     switch (name[7]) {
 496     case 'n':
 497       if (util::streq_l("locatio", name, 7)) {
 498         return HD_LOCATION;
 499       }
 500       break;
 501     }
 502     break;
 503   case 10:
 504     switch (name[9]) {
 505     case 'e':
 506       if (util::streq_l("keep-aliv", name, 9)) {
 507         return HD_KEEP_ALIVE;
 508       }
 509       break;
 510     case 'n':
 511       if (util::streq_l("connectio", name, 9)) {
 512         return HD_CONNECTION;
 513       }
 514       break;
 515     case 't':
 516       if (util::streq_l("user-agen", name, 9)) {
 517         return HD_USER_AGENT;
 518       }
 519       break;
 520     case 'y':
 521       if (util::streq_l(":authorit", name, 9)) {
 522         return HD__AUTHORITY;
 523       }
 524       break;
 525     }
 526     break;
 527   case 13:
 528     switch (name[12]) {
 529     case 'l':
 530       if (util::streq_l("cache-contro", name, 12)) {
 531         return HD_CACHE_CONTROL;
 532       }
 533       break;
 534     }
 535     break;
 536   case 14:
 537     switch (name[13]) {
 538     case 'h':
 539       if (util::streq_l("content-lengt", name, 13)) {
 540         return HD_CONTENT_LENGTH;
 541       }
 542       break;
 543     case 's':
 544       if (util::streq_l("http2-setting", name, 13)) {
 545         return HD_HTTP2_SETTINGS;
 546       }
 547       break;
 548     }
 549     break;
 550   case 15:
 551     switch (name[14]) {
 552     case 'e':
 553       if (util::streq_l("accept-languag", name, 14)) {
 554         return HD_ACCEPT_LANGUAGE;
 555       }
 556       break;
 557     case 'g':
 558       if (util::streq_l("accept-encodin", name, 14)) {
 559         return HD_ACCEPT_ENCODING;
 560       }
 561       break;
 562     case 'r':
 563       if (util::streq_l("x-forwarded-fo", name, 14)) {
 564         return HD_X_FORWARDED_FOR;
 565       }
 566       break;
 567     }
 568     break;
 569   case 16:
 570     switch (name[15]) {
 571     case 'n':
 572       if (util::streq_l("proxy-connectio", name, 15)) {
 573         return HD_PROXY_CONNECTION;
 574       }
 575       break;
 576     }
 577     break;
 578   case 17:
 579     switch (name[16]) {
 580     case 'e':
 581       if (util::streq_l("if-modified-sinc", name, 16)) {
 582         return HD_IF_MODIFIED_SINCE;
 583       }
 584       break;
 585     case 'g':
 586       if (util::streq_l("transfer-encodin", name, 16)) {
 587         return HD_TRANSFER_ENCODING;
 588       }
 589       break;
 590     case 'o':
 591       if (util::streq_l("x-forwarded-prot", name, 16)) {
 592         return HD_X_FORWARDED_PROTO;
 593       }
 594       break;
 595     }
 596     break;
 597   }
 598   return -1;
 599 }
 600
 601 void init_hdidx(HeaderIndex &hdidx) {
 602   std::fill(std::begin(hdidx), std::end(hdidx), -1);
 603 }
 604
 605 void index_header(HeaderIndex &hdidx, int16_t token, size_t idx) {
 606   if (token == -1) {
 607     return;
 608   }
 609   assert(token < HD_MAXIDX);
 610   hdidx[token] = idx;
 611 }
 612
 613 bool check_http2_request_pseudo_header(const HeaderIndex &hdidx,
 614                                        int16_t token) {
 615   switch (token) {
 616   case HD__AUTHORITY:
 617   case HD__METHOD:
 618   case HD__PATH:
 619   case HD__SCHEME:
 620     return hdidx[token] == -1;
 621   default:
 622     return false;
 623   }
 624 }
 625
 626 bool check_http2_response_pseudo_header(const HeaderIndex &hdidx,
 627                                         int16_t token) {
 628   switch (token) {
 629   case HD__STATUS:
 630     return hdidx[token] == -1;
 631   default:
 632     return false;
 633   }
 634 }
 635
 636 bool http2_header_allowed(int16_t token) {
 637   switch (token) {
 638   case HD_CONNECTION:
 639   case HD_KEEP_ALIVE:
 640   case HD_PROXY_CONNECTION:
 641   case HD_TRANSFER_ENCODING:
 642   case HD_UPGRADE:
 643     return false;
 644   default:
 645     return true;
 646   }
 647 }
 648
 649 bool http2_mandatory_request_headers_presence(const HeaderIndex &hdidx) {
 650   if (hdidx[HD__METHOD] == -1 || hdidx[HD__PATH] == -1 ||
 651       hdidx[HD__SCHEME] == -1 ||
 652       (hdidx[HD__AUTHORITY] == -1 && hdidx[HD_HOST] == -1)) {
 653     return false;
 654   }
 655   return true;
 656 }
 657
 658 const Headers::value_type *get_header(const HeaderIndex &hdidx, int16_t token,
 659                                       const Headers &nva) {
 660   auto i = hdidx[token];
 661   if (i == -1) {
 662     return nullptr;
 663   }
 664   return &nva[i];
 665 }
 666
 667 namespace {
 668 template <typename InputIt> InputIt skip_lws(InputIt first, InputIt last) {
 669   for (; first != last; ++first) {
 670     switch (*first) {
 671     case ' ':
 672     case '\t':
 673       continue;
 674     default:
 675       return first;
 676     }
 677   }
 678   return first;
 679 }
 680 } // namespace
 681
 682 namespace {
 683 template <typename InputIt>
 684 InputIt skip_to_next_field(InputIt first, InputIt last) {
 685   for (; first != last; ++first) {
 686     switch (*first) {
 687     case ' ':
 688     case '\t':
 689     case ',':
 690       continue;
 691     default:
 692       return first;
 693     }
 694   }
 695   return first;
 696 }
 697 } // namespace
 698
 699 namespace {
 700 // Skip to the right dquote ('"'), handling backslash escapes.
 701 // Returns |last| if input is not terminated with '"'.
 702 template <typename InputIt>
 703 InputIt skip_to_right_dquote(InputIt first, InputIt last) {
 704   for (; first != last;) {
 705     switch (*first) {
 706     case '"':
 707       return first;
 708     case '\\':
 709       ++first;
 710       if (first == last) {
 711         return first;
 712       }
 713       break;
 714     }
 715     ++first;
 716   }
 717   return first;
 718 }
 719 } // namespace
 720
 721 namespace {
 722 // Returns true if link-param does not match pattern |pat| of length
 723 // |patlen| or it has empty value ("").  |pat| should be parmname
 724 // followed by "=".
 725 bool check_link_param_empty(const char *first, const char *last,
 726                             const char *pat, size_t patlen) {
 727   if (first + patlen <= last) {
 728     if (std::equal(pat, pat + patlen, first, util::CaseCmp())) {
 729       // we only accept URI if pat is followd by "" (e.g.,
 730       // loadpolicy="") here.
 731       if (first + patlen + 2 <= last) {
 732         if (*(first + patlen) != '"' || *(first + patlen + 1) != '"') {
 733           return false;
 734         }
 735       } else {
 736         // here we got invalid production (anchor=") or anchor=?
 737         return false;
 738       }
 739     }
 740   }
 741   return true;
 742 }
 743 } // namespace
 744
 745 namespace {
 746 std::pair<LinkHeader, const char *>
 747 parse_next_link_header_once(const char *first, const char *last) {
 748   first = skip_to_next_field(first, last);
 749   if (first == last || *first != '<') {
 750     return {{{nullptr, nullptr}}, last};
 751   }
 752   auto url_first = ++first;
 753   first = std::find(first, last, '>');
 754   if (first == last) {
 755     return {{{nullptr, nullptr}}, first};
 756   }
 757   auto url_last = first++;
 758   if (first == last) {
 759     return {{{nullptr, nullptr}}, first};
 760   }
 761   // we expect ';' or ',' here
 762   switch (*first) {
 763   case ',':
 764     return {{{nullptr, nullptr}}, ++first};
 765   case ';':
 766     ++first;
 767     break;
 768   default:
 769     return {{{nullptr, nullptr}}, last};
 770   }
 771
 772   auto ok = false;
 773   auto ign = false;
 774   for (;;) {
 775     first = skip_lws(first, last);
 776     if (first == last) {
 777       return {{{nullptr, nullptr}}, first};
 778     }
 779     // we expect link-param
 780
 781     // rel can take several relations using quoted form.
 782     static constexpr char PLP[] = "rel=\"";
 783     static constexpr size_t PLPLEN = sizeof(PLP) - 1;
 784
 785     static constexpr char PLT[] = "preload";
 786     static constexpr size_t PLTLEN = sizeof(PLT) - 1;
 787     if (first + PLPLEN < last && *(first + PLPLEN - 1) == '"' &&
 788         std::equal(PLP, PLP + PLPLEN, first, util::CaseCmp())) {
 789       // we have to search preload in whitespace separated list:
 790       // rel="preload something http://example.org/foo"
 791       first += PLPLEN;
 792       auto start = first;
 793       for (; first != last;) {
 794         if (*first != ' ' && *first != '"') {
 795           ++first;
 796           continue;
 797         }
 798
 799         if (start == first) {
 800           return {{{nullptr, nullptr}}, last};
 801         }
 802
 803         if (!ok && start + PLTLEN == first &&
 804             std::equal(PLT, PLT + PLTLEN, start, util::CaseCmp())) {
 805           ok = true;
 806         }
 807
 808         if (*first == '"') {
 809           break;
 810         }
 811         first = skip_lws(first, last);
 812         start = first;
 813       }
 814       if (first == last) {
 815         return {{{nullptr, nullptr}}, first};
 816       }
 817       assert(*first == '"');
 818       ++first;
 819       if (first == last || *first == ',') {
 820         goto almost_done;
 821       }
 822       if (*first == ';') {
 823         ++first;
 824         // parse next link-param
 825         continue;
 826       }
 827       return {{{nullptr, nullptr}}, last};
 828     }
 829     // we are only interested in rel=preload parameter.  Others are
 830     // simply skipped.
 831     static constexpr char PL[] = "rel=preload";
 832     static constexpr size_t PLLEN = sizeof(PL) - 1;
 833     if (first + PLLEN == last) {
 834       if (std::equal(PL, PL + PLLEN, first, util::CaseCmp())) {
 835         ok = true;
 836         // this is the end of sequence
 837         return {{{url_first, url_last}}, last};
 838       }
 839     } else if (first + PLLEN + 1 <= last) {
 840       switch (*(first + PLLEN)) {
 841       case ',':
 842         if (!std::equal(PL, PL + PLLEN, first, util::CaseCmp())) {
 843           break;
 844         }
 845         ok = true;
 846         // skip including ','
 847         first += PLLEN + 1;
 848         return {{{url_first, url_last}}, first};
 849       case ';':
 850         if (!std::equal(PL, PL + PLLEN, first, util::CaseCmp())) {
 851           break;
 852         }
 853         ok = true;
 854         // skip including ';'
 855         first += PLLEN + 1;
 856         // continue parse next link-param
 857         continue;
 858       }
 859     }
 860     // we have to reject URI if we have nonempty anchor parameter.
 861     static constexpr char ANCHOR[] = "anchor=";
 862     static constexpr size_t ANCHORLEN = sizeof(ANCHOR) - 1;
 863     if (!ign && !check_link_param_empty(first, last, ANCHOR, ANCHORLEN)) {
 864       ign = true;
 865     }
 866
 867     // reject URI if we have non-empty loadpolicy.  This could be
 868     // tightened up to just pick up "next" or "insert".
 869     static constexpr char LOADPOLICY[] = "loadpolicy=";
 870     static constexpr size_t LOADPOLICYLEN = sizeof(LOADPOLICY) - 1;
 871     if (!ign &&
 872         !check_link_param_empty(first, last, LOADPOLICY, LOADPOLICYLEN)) {
 873       ign = true;
 874     }
 875
 876     auto param_first = first;
 877     for (; first != last;) {
 878       if (util::in_attr_char(*first)) {
 879         ++first;
 880         continue;
 881       }
 882       // '*' is only allowed at the end of parameter name and must be
 883       // followed by '='
 884       if (last - first >= 2 && first != param_first) {
 885         if (*first == '*' && *(first + 1) == '=') {
 886           ++first;
 887           break;
 888         }
 889       }
 890       if (*first == '=' || *first == ';' || *first == ',') {
 891         break;
 892       }
 893       return {{{nullptr, nullptr}}, last};
 894     }
 895     if (param_first == first) {
 896       // empty parmname
 897       return {{{nullptr, nullptr}}, last};
 898     }
 899     // link-param without value is acceptable (see link-extension) if
 900     // it is not followed by '='
 901     if (first == last || *first == ',') {
 902       goto almost_done;
 903     }
 904     if (*first == ';') {
 905       ++first;
 906       // parse next link-param
 907       continue;
 908     }
 909     // now parsing link-param value
 910     assert(*first == '=');
 911     ++first;
 912     if (first == last) {
 913       // empty value is not acceptable
 914       return {{{nullptr, nullptr}}, first};
 915     }
 916     if (*first == '"') {
 917       // quoted-string
 918       first = skip_to_right_dquote(first + 1, last);
 919       if (first == last) {
 920         return {{{nullptr, nullptr}}, first};
 921       }
 922       ++first;
 923       if (first == last || *first == ',') {
 924         goto almost_done;
 925       }
 926       if (*first == ';') {
 927         ++first;
 928         // parse next link-param
 929         continue;
 930       }
 931       return {{{nullptr, nullptr}}, last};
 932     }
 933     // not quoted-string, skip to next ',' or ';'
 934     if (*first == ',' || *first == ';') {
 935       // empty value
 936       return {{{nullptr, nullptr}}, last};
 937     }
 938     for (; first != last; ++first) {
 939       if (*first == ',' || *first == ';') {
 940         break;
 941       }
 942     }
 943     if (first == last || *first == ',') {
 944       goto almost_done;
 945     }
 946     assert(*first == ';');
 947     ++first;
 948     // parse next link-param
 949   }
 950
 951 almost_done:
 952   assert(first == last || *first == ',');
 953
 954   if (first != last) {
 955     ++first;
 956   }
 957   if (ok && !ign) {
 958     return {{{url_first, url_last}}, first};
 959   }
 960   return {{{nullptr, nullptr}}, first};
 961 }
 962 } // namespace
 963
 964 std::vector<LinkHeader> parse_link_header(const char *src, size_t len) {
 965   auto first = src;
 966   auto last = src + len;
 967   std::vector<LinkHeader> res;
 968   for (; first != last;) {
 969     auto rv = parse_next_link_header_once(first, last);
 970     first = rv.second;
 971     if (rv.first.uri.first != nullptr && rv.first.uri.second != nullptr) {
 972       res.push_back(rv.first);
 973     }
 974   }
 975   return res;
 976 }
 977
 978 namespace {
 979 void eat_file(std::string &path) {
 980   if (path.empty()) {
 981     path = "/";
 982     return;
 983   }
 984   auto p = path.size() - 1;
 985   if (path[p] == '/') {
 986     return;
 987   }
 988   p = path.rfind('/', p);
 989   if (p == std::string::npos) {
 990     // this should not happend in normal case, where we expect path
 991     // starts with '/'
 992     path = "/";
 993     return;
 994   }
 995   path.erase(std::begin(path) + p + 1, std::end(path));
 996 }
 997 } // namespace
 998
 999 namespace {
1000 void eat_dir(std::string &path) {
1001   if (path.empty()) {
1002     path = "/";
1003     return;
1004   }
1005   auto p = path.size() - 1;
1006   if (path[p] != '/') {
1007     p = path.rfind('/', p);
1008     if (p == std::string::npos) {
1009       // this should not happend in normal case, where we expect path
1010       // starts with '/'
1011       path = "/";
1012       return;
1013     }
1014   }
1015   if (path[p] == '/') {
1016     if (p == 0) {
1017       return;
1018     }
1019     --p;
1020   }
1021   p = path.rfind('/', p);
1022   if (p == std::string::npos) {
1023     // this should not happend in normal case, where we expect path
1024     // starts with '/'
1025     path = "/";
1026     return;
1027   }
1028   path.erase(std::begin(path) + p + 1, std::end(path));
1029 }
1030 } // namespace
1031
1032 std::string path_join(const char *base_path, size_t base_pathlen,
1033                       const char *base_query, size_t base_querylen,
1034                       const char *rel_path, size_t rel_pathlen,
1035                       const char *rel_query, size_t rel_querylen) {
1036   std::string res;
1037   if (rel_pathlen == 0) {
1038     if (base_pathlen == 0) {
1039       res = "/";
1040     } else {
1041       res.assign(base_path, base_pathlen);
1042     }
1043     if (rel_querylen == 0) {
1044       if (base_querylen) {
1045         res += "?";
1046         res.append(base_query, base_querylen);
1047       }
1048       return res;
1049     }
1050     res += "?";
1051     res.append(rel_query, rel_querylen);
1052     return res;
1053   }
1054
1055   auto first = rel_path;
1056   auto last = rel_path + rel_pathlen;
1057
1058   if (rel_path[0] == '/') {
1059     res = "/";
1060     ++first;
1061   } else if (base_pathlen == 0) {
1062     res = "/";
1063   } else {
1064     res.assign(base_path, base_pathlen);
1065   }
1066
1067   for (; first != last;) {
1068     if (*first == '.') {
1069       if (first + 1 == last) {
1070         break;
1071       }
1072       if (*(first + 1) == '/') {
1073         first += 2;
1074         continue;
1075       }
1076       if (*(first + 1) == '.') {
1077         if (first + 2 == last) {
1078           eat_dir(res);
1079           break;
1080         }
1081         if (*(first + 2) == '/') {
1082           eat_dir(res);
1083           first += 3;
1084           continue;
1085         }
1086       }
1087     }
1088     if (res.back() != '/') {
1089       eat_file(res);
1090     }
1091     auto slash = std::find(first, last, '/');
1092     if (slash == last) {
1093       res.append(first, last);
1094       break;
1095     }
1096     res.append(first, slash + 1);
1097     first = slash + 1;
1098     for (; first != last && *first == '/'; ++first)
1099       ;
1100   }
1101   if (rel_querylen) {
1102     res += "?";
1103     res.append(rel_query, rel_querylen);
1104   }
1105   return res;
1106 }
1107
1108 bool expect_response_body(int status_code) {
1109   return status_code / 100 != 1 && status_code != 304 && status_code != 204;
1110 }
1111
1112 bool expect_response_body(const std::string &method, int status_code) {
1113   return method != "HEAD" && expect_response_body(status_code);
1114 }
1115
1116 } // namespace http2
1117
1118 } // namespace nghttp2