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_TRAILER:
 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_TRAILER:
 260     case HD_UPGRADE:
 261     case HD_VIA:
 262     case HD_X_FORWARDED_FOR:
 263     case HD_X_FORWARDED_PROTO:
 264       continue;
 265     }
 266     hdrs += kv.name;
 267     capitalize(hdrs, hdrs.size() - kv.name.size());
 268     hdrs += ": ";
 269     hdrs += kv.value;
 270     hdrs += "\r\n";
 271   }
 272 }
 273
 274 int32_t determine_window_update_transmission(nghttp2_session *session,
 275                                              int32_t stream_id) {
 276   int32_t recv_length, window_size;
 277   if (stream_id == 0) {
 278     recv_length = nghttp2_session_get_effective_recv_data_length(session);
 279     window_size = nghttp2_session_get_effective_local_window_size(session);
 280   } else {
 281     recv_length = nghttp2_session_get_stream_effective_recv_data_length(
 282         session, stream_id);
 283     window_size = nghttp2_session_get_stream_effective_local_window_size(
 284         session, stream_id);
 285   }
 286   if (recv_length != -1 && window_size != -1) {
 287     if (recv_length >= window_size / 2) {
 288       return recv_length;
 289     }
 290   }
 291   return -1;
 292 }
 293
 294 void dump_nv(FILE *out, const char **nv) {
 295   for (size_t i = 0; nv[i]; i += 2) {
 296     fwrite(nv[i], strlen(nv[i]), 1, out);
 297     fwrite(": ", 2, 1, out);
 298     fwrite(nv[i + 1], strlen(nv[i + 1]), 1, out);
 299     fwrite("\n", 1, 1, out);
 300   }
 301   fwrite("\n", 1, 1, out);
 302   fflush(out);
 303 }
 304
 305 void dump_nv(FILE *out, const nghttp2_nv *nva, size_t nvlen) {
 306   auto end = nva + nvlen;
 307   for (; nva != end; ++nva) {
 308     fwrite(nva->name, nva->namelen, 1, out);
 309     fwrite(": ", 2, 1, out);
 310     fwrite(nva->value, nva->valuelen, 1, out);
 311     fwrite("\n", 1, 1, out);
 312   }
 313   fwrite("\n", 1, 1, out);
 314   fflush(out);
 315 }
 316
 317 void dump_nv(FILE *out, const Headers &nva) {
 318   for (auto &nv : nva) {
 319     fwrite(nv.name.c_str(), nv.name.size(), 1, out);
 320     fwrite(": ", 2, 1, out);
 321     fwrite(nv.value.c_str(), nv.value.size(), 1, out);
 322     fwrite("\n", 1, 1, out);
 323   }
 324   fwrite("\n", 1, 1, out);
 325   fflush(out);
 326 }
 327
 328 std::string rewrite_location_uri(const std::string &uri,
 329                                  const http_parser_url &u,
 330                                  const std::string &match_host,
 331                                  const std::string &request_authority,
 332                                  const std::string &upstream_scheme) {
 333   // We just rewrite scheme and authority.
 334   if ((u.field_set & (1 << UF_HOST)) == 0) {
 335     return "";
 336   }
 337   auto field = &u.field_data[UF_HOST];
 338   if (!util::startsWith(std::begin(match_host), std::end(match_host),
 339                         &uri[field->off], &uri[field->off] + field->len) ||
 340       (match_host.size() != field->len && match_host[field->len] != ':')) {
 341     return "";
 342   }
 343   std::string res;
 344   if (!request_authority.empty()) {
 345     res += upstream_scheme;
 346     res += "://";
 347     res += request_authority;
 348   }
 349   if (u.field_set & (1 << UF_PATH)) {
 350     field = &u.field_data[UF_PATH];
 351     res.append(&uri[field->off], field->len);
 352   }
 353   if (u.field_set & (1 << UF_QUERY)) {
 354     field = &u.field_data[UF_QUERY];
 355     res += "?";
 356     res.append(&uri[field->off], field->len);
 357   }
 358   if (u.field_set & (1 << UF_FRAGMENT)) {
 359     field = &u.field_data[UF_FRAGMENT];
 360     res += "#";
 361     res.append(&uri[field->off], field->len);
 362   }
 363   return res;
 364 }
 365
 366 int check_nv(const uint8_t *name, size_t namelen, const uint8_t *value,
 367              size_t valuelen) {
 368   if (!nghttp2_check_header_name(name, namelen)) {
 369     return 0;
 370   }
 371   if (!nghttp2_check_header_value(value, valuelen)) {
 372     return 0;
 373   }
 374   return 1;
 375 }
 376
 377 int parse_http_status_code(const std::string &src) {
 378   if (src.size() != 3) {
 379     return -1;
 380   }
 381
 382   int status = 0;
 383   for (auto c : src) {
 384     if (!isdigit(c)) {
 385       return -1;
 386     }
 387     status *= 10;
 388     status += c - '0';
 389   }
 390
 391   if (status < 100) {
 392     return -1;
 393   }
 394
 395   return status;
 396 }
 397
 398 int lookup_token(const std::string &name) {
 399   return lookup_token(reinterpret_cast<const uint8_t *>(name.c_str()),
 400                       name.size());
 401 }
 402
 403 // This function was generated by genheaderfunc.py.  Inspired by h2o
 404 // header lookup.  https://github.com/h2o/h2o
 405 int lookup_token(const uint8_t *name, size_t namelen) {
 406   switch (namelen) {
 407   case 2:
 408     switch (name[namelen - 1]) {
 409     case 'e':
 410       if (util::streq("t", name, 1)) {
 411         return HD_TE;
 412       }
 413       break;
 414     }
 415     break;
 416   case 3:
 417     switch (name[namelen - 1]) {
 418     case 'a':
 419       if (util::streq("vi", name, 2)) {
 420         return HD_VIA;
 421       }
 422       break;
 423     }
 424     break;
 425   case 4:
 426     switch (name[namelen - 1]) {
 427     case 'k':
 428       if (util::streq("lin", name, 3)) {
 429         return HD_LINK;
 430       }
 431       break;
 432     case 't':
 433       if (util::streq("hos", name, 3)) {
 434         return HD_HOST;
 435       }
 436       break;
 437     }
 438     break;
 439   case 5:
 440     switch (name[namelen - 1]) {
 441     case 'h':
 442       if (util::streq(":pat", name, 4)) {
 443         return HD__PATH;
 444       }
 445       break;
 446     case 't':
 447       if (util::streq(":hos", name, 4)) {
 448         return HD__HOST;
 449       }
 450       break;
 451     }
 452     break;
 453   case 6:
 454     switch (name[namelen - 1]) {
 455     case 'e':
 456       if (util::streq("cooki", name, 5)) {
 457         return HD_COOKIE;
 458       }
 459       break;
 460     case 'r':
 461       if (util::streq("serve", name, 5)) {
 462         return HD_SERVER;
 463       }
 464       break;
 465     case 't':
 466       if (util::streq("expec", name, 5)) {
 467         return HD_EXPECT;
 468       }
 469       break;
 470     }
 471     break;
 472   case 7:
 473     switch (name[namelen - 1]) {
 474     case 'c':
 475       if (util::streq("alt-sv", name, 6)) {
 476         return HD_ALT_SVC;
 477       }
 478       break;
 479     case 'd':
 480       if (util::streq(":metho", name, 6)) {
 481         return HD__METHOD;
 482       }
 483       break;
 484     case 'e':
 485       if (util::streq(":schem", name, 6)) {
 486         return HD__SCHEME;
 487       }
 488       if (util::streq("upgrad", name, 6)) {
 489         return HD_UPGRADE;
 490       }
 491       break;
 492     case 'r':
 493       if (util::streq("traile", name, 6)) {
 494         return HD_TRAILER;
 495       }
 496       break;
 497     case 's':
 498       if (util::streq(":statu", name, 6)) {
 499         return HD__STATUS;
 500       }
 501       break;
 502     }
 503     break;
 504   case 8:
 505     switch (name[namelen - 1]) {
 506     case 'n':
 507       if (util::streq("locatio", name, 7)) {
 508         return HD_LOCATION;
 509       }
 510       break;
 511     }
 512     break;
 513   case 10:
 514     switch (name[namelen - 1]) {
 515     case 'e':
 516       if (util::streq("keep-aliv", name, 9)) {
 517         return HD_KEEP_ALIVE;
 518       }
 519       break;
 520     case 'n':
 521       if (util::streq("connectio", name, 9)) {
 522         return HD_CONNECTION;
 523       }
 524       break;
 525     case 't':
 526       if (util::streq("user-agen", name, 9)) {
 527         return HD_USER_AGENT;
 528       }
 529       break;
 530     case 'y':
 531       if (util::streq(":authorit", name, 9)) {
 532         return HD__AUTHORITY;
 533       }
 534       break;
 535     }
 536     break;
 537   case 13:
 538     switch (name[namelen - 1]) {
 539     case 'l':
 540       if (util::streq("cache-contro", name, 12)) {
 541         return HD_CACHE_CONTROL;
 542       }
 543       break;
 544     }
 545     break;
 546   case 14:
 547     switch (name[namelen - 1]) {
 548     case 'h':
 549       if (util::streq("content-lengt", name, 13)) {
 550         return HD_CONTENT_LENGTH;
 551       }
 552       break;
 553     case 's':
 554       if (util::streq("http2-setting", name, 13)) {
 555         return HD_HTTP2_SETTINGS;
 556       }
 557       break;
 558     }
 559     break;
 560   case 15:
 561     switch (name[namelen - 1]) {
 562     case 'e':
 563       if (util::streq("accept-languag", name, 14)) {
 564         return HD_ACCEPT_LANGUAGE;
 565       }
 566       break;
 567     case 'g':
 568       if (util::streq("accept-encodin", name, 14)) {
 569         return HD_ACCEPT_ENCODING;
 570       }
 571       break;
 572     case 'r':
 573       if (util::streq("x-forwarded-fo", name, 14)) {
 574         return HD_X_FORWARDED_FOR;
 575       }
 576       break;
 577     }
 578     break;
 579   case 16:
 580     switch (name[namelen - 1]) {
 581     case 'n':
 582       if (util::streq("proxy-connectio", name, 15)) {
 583         return HD_PROXY_CONNECTION;
 584       }
 585       break;
 586     }
 587     break;
 588   case 17:
 589     switch (name[namelen - 1]) {
 590     case 'e':
 591       if (util::streq("if-modified-sinc", name, 16)) {
 592         return HD_IF_MODIFIED_SINCE;
 593       }
 594       break;
 595     case 'g':
 596       if (util::streq("transfer-encodin", name, 16)) {
 597         return HD_TRANSFER_ENCODING;
 598       }
 599       break;
 600     case 'o':
 601       if (util::streq("x-forwarded-prot", name, 16)) {
 602         return HD_X_FORWARDED_PROTO;
 603       }
 604       break;
 605     }
 606     break;
 607   }
 608   return -1;
 609 }
 610
 611 void init_hdidx(HeaderIndex &hdidx) {
 612   std::fill(std::begin(hdidx), std::end(hdidx), -1);
 613 }
 614
 615 void index_header(HeaderIndex &hdidx, int16_t token, size_t idx) {
 616   if (token == -1) {
 617     return;
 618   }
 619   assert(token < HD_MAXIDX);
 620   hdidx[token] = idx;
 621 }
 622
 623 bool check_http2_request_pseudo_header(const HeaderIndex &hdidx,
 624                                        int16_t token) {
 625   switch (token) {
 626   case HD__AUTHORITY:
 627   case HD__METHOD:
 628   case HD__PATH:
 629   case HD__SCHEME:
 630     return hdidx[token] == -1;
 631   default:
 632     return false;
 633   }
 634 }
 635
 636 bool check_http2_response_pseudo_header(const HeaderIndex &hdidx,
 637                                         int16_t token) {
 638   switch (token) {
 639   case HD__STATUS:
 640     return hdidx[token] == -1;
 641   default:
 642     return false;
 643   }
 644 }
 645
 646 bool http2_header_allowed(int16_t token) {
 647   switch (token) {
 648   case HD_CONNECTION:
 649   case HD_KEEP_ALIVE:
 650   case HD_PROXY_CONNECTION:
 651   case HD_TRANSFER_ENCODING:
 652   case HD_UPGRADE:
 653     return false;
 654   default:
 655     return true;
 656   }
 657 }
 658
 659 bool http2_mandatory_request_headers_presence(const HeaderIndex &hdidx) {
 660   if (hdidx[HD__METHOD] == -1 || hdidx[HD__PATH] == -1 ||
 661       hdidx[HD__SCHEME] == -1 ||
 662       (hdidx[HD__AUTHORITY] == -1 && hdidx[HD_HOST] == -1)) {
 663     return false;
 664   }
 665   return true;
 666 }
 667
 668 const Headers::value_type *get_header(const HeaderIndex &hdidx, int16_t token,
 669                                       const Headers &nva) {
 670   auto i = hdidx[token];
 671   if (i == -1) {
 672     return nullptr;
 673   }
 674   return &nva[i];
 675 }
 676
 677 namespace {
 678 template <typename InputIt> InputIt skip_lws(InputIt first, InputIt last) {
 679   for (; first != last; ++first) {
 680     switch (*first) {
 681     case ' ':
 682     case '\t':
 683       continue;
 684     default:
 685       return first;
 686     }
 687   }
 688   return first;
 689 }
 690 } // namespace
 691
 692 namespace {
 693 template <typename InputIt>
 694 InputIt skip_to_next_field(InputIt first, InputIt last) {
 695   for (; first != last; ++first) {
 696     switch (*first) {
 697     case ' ':
 698     case '\t':
 699     case ',':
 700       continue;
 701     default:
 702       return first;
 703     }
 704   }
 705   return first;
 706 }
 707 } // namespace
 708
 709 namespace {
 710 std::pair<LinkHeader, const char *>
 711 parse_next_link_header_once(const char *first, const char *last) {
 712   first = skip_to_next_field(first, last);
 713   if (first == last || *first != '<') {
 714     return {{{0, 0}}, last};
 715   }
 716   auto url_first = ++first;
 717   first = std::find(first, last, '>');
 718   if (first == last) {
 719     return {{{0, 0}}, first};
 720   }
 721   auto url_last = first++;
 722   if (first == last) {
 723     return {{{0, 0}}, first};
 724   }
 725   // we expect ';' or ',' here
 726   switch (*first) {
 727   case ',':
 728     return {{{0, 0}}, ++first};
 729   case ';':
 730     ++first;
 731     break;
 732   default:
 733     return {{{0, 0}}, last};
 734   }
 735
 736   auto ok = false;
 737   for (;;) {
 738     first = skip_lws(first, last);
 739     if (first == last) {
 740       return {{{0, 0}}, first};
 741     }
 742     // we expect link-param
 743
 744     // we are only interested in rel=preload parameter.  Others are
 745     // simply skipped.
 746     static const char PL[] = "rel=preload";
 747     static const size_t PLLEN = sizeof(PL) - 1;
 748     if (first + PLLEN == last) {
 749       if (std::equal(PL, PL + PLLEN, first)) {
 750         ok = true;
 751         // this is the end of sequence
 752         return {{{url_first, url_last}}, last};
 753       }
 754     } else if (first + PLLEN + 1 <= last) {
 755       switch (*(first + PLLEN)) {
 756       case ',':
 757         if (!std::equal(PL, PL + PLLEN, first)) {
 758           break;
 759         }
 760         ok = true;
 761         // skip including ','
 762         first += PLLEN + 1;
 763         return {{{url_first, url_last}}, first};
 764       case ';':
 765         if (!std::equal(PL, PL + PLLEN, first)) {
 766           break;
 767         }
 768         ok = true;
 769         // skip including ';'
 770         first += PLLEN + 1;
 771         // continue parse next link-param
 772         continue;
 773       }
 774     }
 775     auto param_first = first;
 776     for (; first != last;) {
 777       if (util::in_attr_char(*first)) {
 778         ++first;
 779         continue;
 780       }
 781       // '*' is only allowed at the end of parameter name and must be
 782       // followed by '='
 783       if (last - first >= 2 && first != param_first) {
 784         if (*first == '*' && *(first + 1) == '=') {
 785           ++first;
 786           break;
 787         }
 788       }
 789       if (*first == '=' || *first == ';' || *first == ',') {
 790         break;
 791       }
 792       return {{{0, 0}}, last};
 793     }
 794     if (param_first == first) {
 795       // empty parmname
 796       return {{{0, 0}}, last};
 797     }
 798     // link-param without value is acceptable (see link-extension) if
 799     // it is not followed by '='
 800     if (first == last || *first == ',') {
 801       goto almost_done;
 802     }
 803     if (*first == ';') {
 804       ++first;
 805       // parse next link-param
 806       continue;
 807     }
 808     // now parsing lin-param value
 809     assert(*first == '=');
 810     ++first;
 811     if (first == last) {
 812       // empty value is not acceptable
 813       return {{{0, 0}}, first};
 814     }
 815     if (*first == '"') {
 816       // quoted-string
 817       first = std::find(first + 1, last, '"');
 818       if (first == last) {
 819         return {{{0, 0}}, first};
 820       }
 821       ++first;
 822       if (first == last || *first == ',') {
 823         goto almost_done;
 824       }
 825       if (*first == ';') {
 826         ++first;
 827         // parse next link-param
 828         continue;
 829       }
 830       return {{{0, 0}}, last};
 831     }
 832     // not quoted-string, skip to next ',' or ';'
 833     if (*first == ',' || *first == ';') {
 834       // empty value
 835       return {{{0, 0}}, last};
 836     }
 837     for (; first != last; ++first) {
 838       if (*first == ',' || *first == ';') {
 839         break;
 840       }
 841     }
 842     if (first == last || *first == ',') {
 843       goto almost_done;
 844     }
 845     assert(*first == ';');
 846     ++first;
 847     // parse next link-param
 848   }
 849
 850 almost_done:
 851   assert(first == last || *first == ',');
 852
 853   if (*first == ',') {
 854     ++first;
 855   }
 856   if (ok) {
 857     return {{{url_first, url_last}}, first};
 858   }
 859   return {{{0, 0}}, first};
 860 }
 861 } // namespace
 862
 863 std::vector<LinkHeader> parse_link_header(const char *src, size_t len) {
 864   auto first = src;
 865   auto last = src + len;
 866   std::vector<LinkHeader> res;
 867   for (; first != last;) {
 868     auto rv = parse_next_link_header_once(first, last);
 869     first = rv.second;
 870     if (rv.first.uri.first != 0 || rv.first.uri.second != 0) {
 871       res.push_back(rv.first);
 872     }
 873   }
 874   return res;
 875 }
 876
 877 namespace {
 878 void eat_file(std::string &path) {
 879   if (path.empty()) {
 880     path = "/";
 881     return;
 882   }
 883   auto p = path.size() - 1;
 884   if (path[p] == '/') {
 885     return;
 886   }
 887   p = path.rfind('/', p);
 888   if (p == std::string::npos) {
 889     // this should not happend in normal case, where we expect path
 890     // starts with '/'
 891     path = "/";
 892     return;
 893   }
 894   path.erase(std::begin(path) + p + 1, std::end(path));
 895 }
 896 } // namespace
 897
 898 namespace {
 899 void eat_dir(std::string &path) {
 900   if (path.empty()) {
 901     path = "/";
 902     return;
 903   }
 904   auto p = path.size() - 1;
 905   if (path[p] != '/') {
 906     p = path.rfind('/', p);
 907     if (p == std::string::npos) {
 908       // this should not happend in normal case, where we expect path
 909       // starts with '/'
 910       path = "/";
 911       return;
 912     }
 913   }
 914   if (path[p] == '/') {
 915     if (p == 0) {
 916       return;
 917     }
 918     --p;
 919   }
 920   p = path.rfind('/', p);
 921   if (p == std::string::npos) {
 922     // this should not happend in normal case, where we expect path
 923     // starts with '/'
 924     path = "/";
 925     return;
 926   }
 927   path.erase(std::begin(path) + p + 1, std::end(path));
 928 }
 929 } // namespace
 930
 931 std::string path_join(const char *base_path, size_t base_pathlen,
 932                       const char *base_query, size_t base_querylen,
 933                       const char *rel_path, size_t rel_pathlen,
 934                       const char *rel_query, size_t rel_querylen) {
 935   std::string res;
 936   if (rel_pathlen == 0) {
 937     if (base_pathlen == 0) {
 938       res = "/";
 939     } else {
 940       res.assign(base_path, base_pathlen);
 941     }
 942     if (rel_querylen == 0) {
 943       if (base_querylen) {
 944         res += "?";
 945         res.append(base_query, base_querylen);
 946       }
 947       return res;
 948     }
 949     res += "?";
 950     res.append(rel_query, rel_querylen);
 951     return res;
 952   }
 953
 954   auto first = rel_path;
 955   auto last = rel_path + rel_pathlen;
 956
 957   if (rel_path[0] == '/') {
 958     res = "/";
 959     ++first;
 960   } else if (base_pathlen == 0) {
 961     res = "/";
 962   } else {
 963     res.assign(base_path, base_pathlen);
 964   }
 965
 966   for (; first != last;) {
 967     if (*first == '.') {
 968       if (first + 1 == last) {
 969         break;
 970       }
 971       if (*(first + 1) == '/') {
 972         first += 2;
 973         continue;
 974       }
 975       if (*(first + 1) == '.') {
 976         if (first + 2 == last) {
 977           eat_dir(res);
 978           break;
 979         }
 980         if (*(first + 2) == '/') {
 981           eat_dir(res);
 982           first += 3;
 983           continue;
 984         }
 985       }
 986     }
 987     if (res.back() != '/') {
 988       eat_file(res);
 989     }
 990     auto slash = std::find(first, last, '/');
 991     if (slash == last) {
 992       res.append(first, last);
 993       break;
 994     }
 995     res.append(first, slash + 1);
 996     first = slash + 1;
 997     for (; first != last && *first == '/'; ++first)
 998       ;
 999   }
1000   if (rel_querylen) {
1001     res += "?";
1002     res.append(rel_query, rel_querylen);
1003   }
1004   return res;
1005 }
1006
1007 } // namespace http2
1008
1009 } // namespace nghttp2