_ZN6google4grpc11transcoding12HttpTemplate5ParseERKNSt3__112basic_stringIcNS3_11char_traitsIcEENS3_9allocatorIcEEEE:
  364|    927|std::unique_ptr<HttpTemplate> HttpTemplate::Parse(const std::string &ht) {
  365|    927|  if (ht == "/") {
  ------------------
  |  Branch (365:7): [True: 1, False: 926]
  ------------------
  366|      1|    return std::unique_ptr<HttpTemplate>(new HttpTemplate({}, {}, {}));
  367|      1|  }
  368|       |
  369|    926|  Parser p(ht);
  370|    926|  if (!p.Parse() || !p.ValidateParts()) {
  ------------------
  |  Branch (370:7): [True: 480, False: 446]
  |  Branch (370:21): [True: 71, False: 375]
  ------------------
  371|    551|    return nullptr;
  372|    551|  }
  373|       |
  374|    375|  return std::unique_ptr<HttpTemplate>(new HttpTemplate(
  375|    375|      std::move(p.segments()), std::move(p.verb()), std::move(p.variables())));
  376|    926|}
http_template.cc:_ZN6google4grpc11transcoding12_GLOBAL__N_16ParserC2ERKNSt3__112basic_stringIcNS4_11char_traitsIcEENS4_9allocatorIcEEEE:
   45|    926|      : input_(input), tb_(0), te_(0), in_variable_(false) {}
http_template.cc:_ZN6google4grpc11transcoding12_GLOBAL__N_16Parser5ParseEv:
   47|    926|  bool Parse() {
   48|    926|    if (!ParseTemplate() || !ConsumedAllInput()) {
  ------------------
  |  Branch (48:9): [True: 385, False: 541]
  |  Branch (48:29): [True: 95, False: 446]
  ------------------
   49|    480|      return false;
   50|    480|    }
   51|    446|    PostProcessVariables();
   52|    446|    return true;
   53|    926|  }
http_template.cc:_ZN6google4grpc11transcoding12_GLOBAL__N_16Parser13ParseTemplateEv:
   78|    926|  bool ParseTemplate() {
   79|    926|    if (!Consume('/')) {
  ------------------
  |  Branch (79:9): [True: 26, False: 900]
  ------------------
   80|       |      // Expected '/'
   81|     26|      return false;
   82|     26|    }
   83|    900|    if (!ParseSegments()) {
  ------------------
  |  Branch (83:9): [True: 326, False: 574]
  ------------------
   84|    326|      return false;
   85|    326|    }
   86|       |
   87|    574|    if (EnsureCurrent() && current_char() == ':') {
  ------------------
  |  Branch (87:9): [True: 147, False: 427]
  |  Branch (87:28): [True: 56, False: 91]
  ------------------
   88|     56|      if (!ParseVerb()) {
  ------------------
  |  Branch (88:11): [True: 33, False: 23]
  ------------------
   89|     33|        return false;
   90|     33|      }
   91|     56|    }
   92|    541|    return true;
   93|    574|  }
http_template.cc:_ZN6google4grpc11transcoding12_GLOBAL__N_16Parser7ConsumeEc:
  249|  37.4M|  bool Consume(char c) {
  250|  37.4M|    if (tb_ >= te_ && !NextChar()) {
  ------------------
  |  Branch (250:9): [True: 2.65M, False: 34.8M]
  |  Branch (250:23): [True: 931, False: 2.65M]
  ------------------
  251|    931|      return false;
  252|    931|    }
  253|  37.4M|    if (current_char() != c) {
  ------------------
  |  Branch (253:9): [True: 3.08M, False: 34.4M]
  ------------------
  254|  3.08M|      return false;
  255|  3.08M|    }
  256|  34.4M|    tb_++;
  257|  34.4M|    return true;
  258|  37.4M|  }
http_template.cc:_ZN6google4grpc11transcoding12_GLOBAL__N_16Parser8NextCharEv:
  264|  34.4M|  bool NextChar() {
  265|  34.4M|    if (te_ < input_.size()) {
  ------------------
  |  Branch (265:9): [True: 34.4M, False: 1.93k]
  ------------------
  266|  34.4M|      te_++;
  267|  34.4M|      return true;
  268|  34.4M|    } else {
  269|  1.93k|      return false;
  270|  1.93k|    }
  271|  34.4M|  }
http_template.cc:_ZN6google4grpc11transcoding12_GLOBAL__N_16Parser13ParseSegmentsEv:
   96|  6.89k|  bool ParseSegments() {
   97|  6.89k|    if (!ParseSegment()) {
  ------------------
  |  Branch (97:9): [True: 124, False: 6.76k]
  ------------------
   98|    124|      return false;
   99|    124|    }
  100|       |
  101|  5.51M|    for (;;) {
  102|  5.51M|      if (!Consume('/')) break;
  ------------------
  |  Branch (102:11): [True: 6.54k, False: 5.51M]
  ------------------
  103|  5.51M|      if (!ParseSegment()) {
  ------------------
  |  Branch (103:11): [True: 229, False: 5.51M]
  ------------------
  104|    229|        return false;
  105|    229|      }
  106|  5.51M|    }
  107|       |
  108|  6.54k|    return true;
  109|  6.76k|  }
http_template.cc:_ZN6google4grpc11transcoding12_GLOBAL__N_16Parser12ParseSegmentEv:
  112|  5.51M|  bool ParseSegment() {
  113|  5.51M|    if (!EnsureCurrent()) {
  ------------------
  |  Branch (113:9): [True: 46, False: 5.51M]
  ------------------
  114|     46|      return false;
  115|     46|    }
  116|  5.51M|    switch (current_char()) {
  117|  2.19M|      case '*': {
  ------------------
  |  Branch (117:7): [True: 2.19M, False: 3.32M]
  ------------------
  118|  2.19M|        Consume('*');
  119|  2.19M|        if (Consume('*')) {
  ------------------
  |  Branch (119:13): [True: 10.0k, False: 2.18M]
  ------------------
  120|       |          // **
  121|  10.0k|          segments_.push_back("**");
  122|  10.0k|          if (in_variable_) {
  ------------------
  |  Branch (122:15): [True: 5.52k, False: 4.55k]
  ------------------
  123|  5.52k|            return MarkVariableHasWildCardPath();
  124|  5.52k|          }
  125|  4.55k|          return true;
  126|  2.18M|        } else {
  127|  2.18M|          segments_.push_back("*");
  128|  2.18M|          return true;
  129|  2.18M|        }
  130|  2.19M|      }
  131|       |
  132|   449k|      case '{':
  ------------------
  |  Branch (132:7): [True: 449k, False: 5.06M]
  ------------------
  133|   449k|        return ParseVariable();
  134|  2.87M|      default:
  ------------------
  |  Branch (134:7): [True: 2.87M, False: 2.64M]
  ------------------
  135|  2.87M|        return ParseLiteralSegment();
  136|  5.51M|    }
  137|  5.51M|  }
http_template.cc:_ZN6google4grpc11transcoding12_GLOBAL__N_16Parser27MarkVariableHasWildCardPathEv:
  314|  5.52k|  bool MarkVariableHasWildCardPath() {
  315|  5.52k|    if (in_variable_ && !variables_.empty()) {
  ------------------
  |  Branch (315:9): [True: 5.52k, False: 0]
  |  Branch (315:25): [True: 5.52k, False: 0]
  ------------------
  316|  5.52k|      CurrentVariable().has_wildcard_path = true;
  317|  5.52k|      return true;
  318|  5.52k|    } else {
  319|       |      // something's wrong we're not in a variable
  320|      0|      return false;
  321|      0|    }
  322|  5.52k|  }
http_template.cc:_ZN6google4grpc11transcoding12_GLOBAL__N_16Parser15CurrentVariableEv:
  278|  2.83M|  HttpTemplate::Variable &CurrentVariable() { return variables_.back(); }
http_template.cc:_ZN6google4grpc11transcoding12_GLOBAL__N_16Parser13ParseVariableEv:
  140|   449k|  bool ParseVariable() {
  141|   449k|    if (!Consume('{')) {
  ------------------
  |  Branch (141:9): [True: 0, False: 449k]
  ------------------
  142|      0|      return false;
  143|      0|    }
  144|   449k|    if (!StartVariable()) {
  ------------------
  |  Branch (144:9): [True: 9, False: 449k]
  ------------------
  145|      9|      return false;
  146|      9|    }
  147|   449k|    if (!ParseFieldPath()) {
  ------------------
  |  Branch (147:9): [True: 83, False: 448k]
  ------------------
  148|     83|      return false;
  149|     83|    }
  150|   448k|    if (Consume('=')) {
  ------------------
  |  Branch (150:9): [True: 5.99k, False: 443k]
  ------------------
  151|  5.99k|      if (!ParseSegments()) {
  ------------------
  |  Branch (151:11): [True: 27, False: 5.96k]
  ------------------
  152|     27|        return false;
  153|     27|      }
  154|   443k|    } else {
  155|       |      // {field_path} is equivalent to {field_path=*}
  156|   443k|      segments_.push_back("*");
  157|   443k|    }
  158|   448k|    if (!EndVariable()) {
  ------------------
  |  Branch (158:9): [True: 0, False: 448k]
  ------------------
  159|      0|      return false;
  160|      0|    }
  161|   448k|    if (!Consume('}')) {
  ------------------
  |  Branch (161:9): [True: 167, False: 448k]
  ------------------
  162|    167|      return false;
  163|    167|    }
  164|   448k|    return true;
  165|   448k|  }
http_template.cc:_ZN6google4grpc11transcoding12_GLOBAL__N_16Parser13StartVariableEv:
  280|   449k|  bool StartVariable() {
  281|   449k|    if (!in_variable_) {
  ------------------
  |  Branch (281:9): [True: 449k, False: 9]
  ------------------
  282|   449k|      variables_.push_back(HttpTemplate::Variable{});
  283|   449k|      CurrentVariable().start_segment = segments_.size();
  284|   449k|      CurrentVariable().has_wildcard_path = false;
  285|   449k|      in_variable_ = true;
  286|   449k|      return true;
  287|   449k|    } else {
  288|       |      // nested variables are not allowed
  289|      9|      return false;
  290|      9|    }
  291|   449k|  }
http_template.cc:_ZN6google4grpc11transcoding12_GLOBAL__N_16Parser14ParseFieldPathEv:
  177|   449k|  bool ParseFieldPath() {
  178|   449k|    if (!ParseIdentifier()) {
  ------------------
  |  Branch (178:9): [True: 48, False: 449k]
  ------------------
  179|     48|      return false;
  180|     48|    }
  181|  1.02M|    while (Consume('.')) {
  ------------------
  |  Branch (181:12): [True: 580k, False: 448k]
  ------------------
  182|   580k|      if (!ParseIdentifier()) {
  ------------------
  |  Branch (182:11): [True: 35, False: 580k]
  ------------------
  183|     35|        return false;
  184|     35|      }
  185|   580k|    }
  186|   448k|    return true;
  187|   449k|  }
http_template.cc:_ZN6google4grpc11transcoding12_GLOBAL__N_16Parser15ParseIdentifierEv:
  196|  1.02M|  bool ParseIdentifier() {
  197|  1.02M|    std::string idf;
  198|       |
  199|       |    // Initialize to false to handle empty literal.
  200|  1.02M|    bool result = false;
  201|       |
  202|  9.71M|    while (NextChar()) {
  ------------------
  |  Branch (202:12): [True: 9.71M, False: 181]
  ------------------
  203|  9.71M|      char c;
  204|  9.71M|      switch (c = current_char()) {
  205|   580k|        case '.':
  ------------------
  |  Branch (205:9): [True: 580k, False: 9.13M]
  ------------------
  206|  1.02M|        case '}':
  ------------------
  |  Branch (206:9): [True: 442k, False: 9.27M]
  ------------------
  207|  1.02M|        case '=':
  ------------------
  |  Branch (207:9): [True: 6.00k, False: 9.70M]
  ------------------
  208|  1.02M|          return result && AddFieldIdentifier(std::move(idf));
  ------------------
  |  Branch (208:18): [True: 1.02M, False: 32]
  |  Branch (208:28): [True: 1.02M, False: 0]
  ------------------
  209|  8.68M|        default:
  ------------------
  |  Branch (209:9): [True: 8.68M, False: 1.02M]
  ------------------
  210|  8.68M|          Consume(c);
  211|  8.68M|          idf.push_back(c);
  212|  8.68M|          break;
  213|  9.71M|      }
  214|  8.68M|      result = true;
  215|  8.68M|    }
  216|    181|    return result && AddFieldIdentifier(std::move(idf));
  ------------------
  |  Branch (216:12): [True: 130, False: 51]
  |  Branch (216:22): [True: 130, False: 0]
  ------------------
  217|  1.02M|  }
http_template.cc:_ZN6google4grpc11transcoding12_GLOBAL__N_16Parser18AddFieldIdentifierENSt3__112basic_stringIcNS4_11char_traitsIcEENS4_9allocatorIcEEEE:
  304|  1.02M|  bool AddFieldIdentifier(std::string id) {
  305|  1.02M|    if (in_variable_ && !variables_.empty()) {
  ------------------
  |  Branch (305:9): [True: 1.02M, False: 0]
  |  Branch (305:25): [True: 1.02M, False: 0]
  ------------------
  306|  1.02M|      CurrentVariable().field_path.emplace_back(std::move(id));
  307|  1.02M|      return true;
  308|  1.02M|    } else {
  309|       |      // something's wrong we're not in a variable
  310|      0|      return false;
  311|      0|    }
  312|  1.02M|  }
http_template.cc:_ZN6google4grpc11transcoding12_GLOBAL__N_16Parser11EndVariableEv:
  293|   448k|  bool EndVariable() {
  294|   448k|    if (in_variable_ && !variables_.empty()) {
  ------------------
  |  Branch (294:9): [True: 448k, False: 0]
  |  Branch (294:25): [True: 448k, False: 0]
  ------------------
  295|   448k|      CurrentVariable().end_segment = segments_.size();
  296|   448k|      in_variable_ = false;
  297|   448k|      return ValidateVariable(CurrentVariable());
  298|   448k|    } else {
  299|       |      // something's wrong we're not in a variable
  300|      0|      return false;
  301|      0|    }
  302|   448k|  }
http_template.cc:_ZN6google4grpc11transcoding12_GLOBAL__N_16Parser16ValidateVariableERKNS1_12HttpTemplate8VariableE:
  324|   448k|  bool ValidateVariable(const HttpTemplate::Variable &var) {
  325|   448k|    return !var.field_path.empty() && (var.start_segment < var.end_segment) &&
  ------------------
  |  Branch (325:12): [True: 448k, False: 0]
  |  Branch (325:39): [True: 448k, False: 0]
  ------------------
  326|   448k|           (var.end_segment <= static_cast<int>(segments_.size()));
  ------------------
  |  Branch (326:12): [True: 448k, False: 0]
  ------------------
  327|   448k|  }
http_template.cc:_ZN6google4grpc11transcoding12_GLOBAL__N_16Parser19ParseLiteralSegmentEv:
  167|  2.87M|  bool ParseLiteralSegment() {
  168|  2.87M|    std::string ls;
  169|  2.87M|    if (!ParseLiteral(&ls)) {
  ------------------
  |  Branch (169:9): [True: 21, False: 2.87M]
  ------------------
  170|     21|      return false;
  171|     21|    }
  172|  2.87M|    segments_.push_back(ls);
  173|  2.87M|    return true;
  174|  2.87M|  }
http_template.cc:_ZN6google4grpc11transcoding12_GLOBAL__N_16Parser12ParseLiteralEPNSt3__112basic_stringIcNS4_11char_traitsIcEENS4_9allocatorIcEEEE:
  219|  2.87M|  bool ParseLiteral(std::string *lit) {
  220|  2.87M|    if (!EnsureCurrent()) {
  ------------------
  |  Branch (220:9): [True: 30, False: 2.87M]
  ------------------
  221|     30|      return false;
  222|     30|    }
  223|       |
  224|       |    // Initialize to false in case we encounter an empty literal.
  225|  2.87M|    bool result = false;
  226|       |
  227|  19.3M|    for (;;) {
  228|  19.3M|      char c;
  229|  19.3M|      switch (c = current_char()) {
  230|  2.87M|        case '/':
  ------------------
  |  Branch (230:9): [True: 2.87M, False: 16.5M]
  ------------------
  231|  2.87M|        case ':':
  ------------------
  |  Branch (231:9): [True: 45, False: 19.3M]
  ------------------
  232|  2.87M|        case '}':
  ------------------
  |  Branch (232:9): [True: 2.47k, False: 19.3M]
  ------------------
  233|  2.87M|          return result;
  234|  16.5M|        default:
  ------------------
  |  Branch (234:9): [True: 16.5M, False: 2.87M]
  ------------------
  235|  16.5M|          Consume(c);
  236|  16.5M|          lit->push_back(c);
  237|  16.5M|          break;
  238|  19.3M|      }
  239|       |
  240|  16.5M|      result = true;
  241|       |
  242|  16.5M|      if (!NextChar()) {
  ------------------
  |  Branch (242:11): [True: 316, False: 16.5M]
  ------------------
  243|    316|        break;
  244|    316|      }
  245|  16.5M|    }
  246|    316|    return result;
  247|  2.87M|  }
http_template.cc:_ZN6google4grpc11transcoding12_GLOBAL__N_16Parser13EnsureCurrentEv:
  262|  8.39M|  bool EnsureCurrent() { return tb_ < te_ || NextChar(); }
  ------------------
  |  Branch (262:33): [True: 2.87M, False: 5.51M]
  |  Branch (262:46): [True: 5.51M, False: 503]
  ------------------
http_template.cc:_ZNK6google4grpc11transcoding12_GLOBAL__N_16Parser12current_charEv:
  274|  72.1M|  char current_char() const {
  275|  72.1M|    return tb_ < te_ && te_ <= input_.size() ? input_[te_ - 1] : -1;
  ------------------
  |  Branch (275:12): [True: 72.1M, False: 0]
  |  Branch (275:25): [True: 72.1M, False: 0]
  ------------------
  276|  72.1M|  }
http_template.cc:_ZN6google4grpc11transcoding12_GLOBAL__N_16Parser9ParseVerbEv:
  190|     56|  bool ParseVerb() {
  191|     56|    if (!Consume(':')) return false;
  ------------------
  |  Branch (191:9): [True: 0, False: 56]
  ------------------
  192|     56|    if (!ParseLiteral(&verb_)) return false;
  ------------------
  |  Branch (192:9): [True: 33, False: 23]
  ------------------
  193|     23|    return true;
  194|     56|  }
http_template.cc:_ZN6google4grpc11transcoding12_GLOBAL__N_16Parser16ConsumedAllInputEv:
  260|    541|  bool ConsumedAllInput() { return tb_ >= input_.size(); }
http_template.cc:_ZN6google4grpc11transcoding12_GLOBAL__N_16Parser20PostProcessVariablesEv:
  329|    446|  void PostProcessVariables() {
  330|   229k|    for (auto &var : variables_) {
  ------------------
  |  Branch (330:20): [True: 229k, False: 446]
  ------------------
  331|   229k|      if (var.has_wildcard_path) {
  ------------------
  |  Branch (331:11): [True: 2.03k, False: 227k]
  ------------------
  332|       |        // if the variable contains a '**', store the end_positon
  333|       |        // relative to the end, such that -1 corresponds to the end
  334|       |        // of the path. As we only support fixed path after '**',
  335|       |        // this will allow the matcher code to reconstruct the variable
  336|       |        // value based on the url segments.
  337|  2.03k|        var.end_segment = (var.end_segment - segments_.size() - 1);
  338|  2.03k|      }
  339|   229k|    }
  340|    446|  }
http_template.cc:_ZN6google4grpc11transcoding12_GLOBAL__N_16Parser13ValidatePartsEv:
   60|    446|  bool ValidateParts() {
   61|    446|    bool found_wild_card = false;
   62|  4.46M|    for (size_t i = 0; i < segments_.size(); i++) {
  ------------------
  |  Branch (62:24): [True: 4.46M, False: 375]
  ------------------
   63|  4.46M|      if (!found_wild_card) {
  ------------------
  |  Branch (63:11): [True: 4.46M, False: 1.73k]
  ------------------
   64|  4.46M|        if (segments_[i] == HttpTemplate::kWildCardPathKey) {
  ------------------
  |  Branch (64:13): [True: 213, False: 4.46M]
  ------------------
   65|    213|          found_wild_card = true;
   66|    213|        }
   67|  4.46M|      } else if (segments_[i] == HttpTemplate::kSingleParameterKey ||
  ------------------
  |  Branch (67:18): [True: 0, False: 1.73k]
  ------------------
   68|  1.73k|                 segments_[i] == HttpTemplate::kWildCardPathPartKey ||
  ------------------
  |  Branch (68:18): [True: 23, False: 1.71k]
  ------------------
   69|  1.73k|                 segments_[i] == HttpTemplate::kWildCardPathKey) {
  ------------------
  |  Branch (69:18): [True: 48, False: 1.66k]
  ------------------
   70|     71|        return false;
   71|     71|      }
   72|  4.46M|    }
   73|    375|    return true;
   74|    446|  }
http_template.cc:_ZN6google4grpc11transcoding12_GLOBAL__N_16Parser8segmentsEv:
   55|    375|  std::vector<std::string> &segments() { return segments_; }
http_template.cc:_ZN6google4grpc11transcoding12_GLOBAL__N_16Parser4verbEv:
   56|    375|  std::string &verb() { return verb_; }
http_template.cc:_ZN6google4grpc11transcoding12_GLOBAL__N_16Parser9variablesEv:
   57|    375|  std::vector<HttpTemplate::Variable> &variables() { return variables_; }

LLVMFuzzerTestOneInput:
    7|    927|extern "C" int LLVMFuzzerTestOneInput(const uint8_t *data, size_t size) {
    8|    927|  std::string path((const char *)data, size);
    9|    927|  google::grpc::transcoding::HttpTemplate::Parse(path);
   10|    927|  return 0;
   11|    927|}