_ZN6google4grpc11transcoding12HttpTemplate5ParseERKNSt3__112basic_stringIcNS3_11char_traitsIcEENS3_9allocatorIcEEEE:
  364|    946|std::unique_ptr<HttpTemplate> HttpTemplate::Parse(const std::string &ht) {
  365|    946|  if (ht == "/") {
  ------------------
  |  Branch (365:7): [True: 1, False: 945]
  ------------------
  366|      1|    return std::unique_ptr<HttpTemplate>(new HttpTemplate({}, {}, {}));
  367|      1|  }
  368|       |
  369|    945|  Parser p(ht);
  370|    945|  if (!p.Parse() || !p.ValidateParts()) {
  ------------------
  |  Branch (370:7): [True: 502, False: 443]
  |  Branch (370:21): [True: 55, False: 388]
  ------------------
  371|    557|    return nullptr;
  372|    557|  }
  373|       |
  374|    388|  return std::unique_ptr<HttpTemplate>(new HttpTemplate(
  375|    388|      std::move(p.segments()), std::move(p.verb()), std::move(p.variables())));
  376|    945|}
http_template.cc:_ZN6google4grpc11transcoding12_GLOBAL__N_16ParserC2ERKNSt3__112basic_stringIcNS4_11char_traitsIcEENS4_9allocatorIcEEEE:
   45|    945|      : input_(input), tb_(0), te_(0), in_variable_(false) {}
http_template.cc:_ZN6google4grpc11transcoding12_GLOBAL__N_16Parser5ParseEv:
   47|    945|  bool Parse() {
   48|    945|    if (!ParseTemplate() || !ConsumedAllInput()) {
  ------------------
  |  Branch (48:9): [True: 405, False: 540]
  |  Branch (48:29): [True: 97, False: 443]
  ------------------
   49|    502|      return false;
   50|    502|    }
   51|    443|    PostProcessVariables();
   52|    443|    return true;
   53|    945|  }
http_template.cc:_ZN6google4grpc11transcoding12_GLOBAL__N_16Parser13ParseTemplateEv:
   78|    945|  bool ParseTemplate() {
   79|    945|    if (!Consume('/')) {
  ------------------
  |  Branch (79:9): [True: 28, False: 917]
  ------------------
   80|       |      // Expected '/'
   81|     28|      return false;
   82|     28|    }
   83|    917|    if (!ParseSegments()) {
  ------------------
  |  Branch (83:9): [True: 343, False: 574]
  ------------------
   84|    343|      return false;
   85|    343|    }
   86|       |
   87|    574|    if (EnsureCurrent() && current_char() == ':') {
  ------------------
  |  Branch (87:9): [True: 154, False: 420]
  |  Branch (87:28): [True: 63, False: 91]
  ------------------
   88|     63|      if (!ParseVerb()) {
  ------------------
  |  Branch (88:11): [True: 34, False: 29]
  ------------------
   89|     34|        return false;
   90|     34|      }
   91|     63|    }
   92|    540|    return true;
   93|    574|  }
http_template.cc:_ZN6google4grpc11transcoding12_GLOBAL__N_16Parser7ConsumeEc:
  249|  40.3M|  bool Consume(char c) {
  250|  40.3M|    if (tb_ >= te_ && !NextChar()) {
  ------------------
  |  Branch (250:9): [True: 3.21M, False: 37.0M]
  |  Branch (250:23): [True: 925, False: 3.21M]
  ------------------
  251|    925|      return false;
  252|    925|    }
  253|  40.3M|    if (current_char() != c) {
  ------------------
  |  Branch (253:9): [True: 3.75M, False: 36.5M]
  ------------------
  254|  3.75M|      return false;
  255|  3.75M|    }
  256|  36.5M|    tb_++;
  257|  36.5M|    return true;
  258|  40.3M|  }
http_template.cc:_ZN6google4grpc11transcoding12_GLOBAL__N_16Parser8NextCharEv:
  264|  36.5M|  bool NextChar() {
  265|  36.5M|    if (te_ < input_.size()) {
  ------------------
  |  Branch (265:9): [True: 36.5M, False: 1.92k]
  ------------------
  266|  36.5M|      te_++;
  267|  36.5M|      return true;
  268|  36.5M|    } else {
  269|  1.92k|      return false;
  270|  1.92k|    }
  271|  36.5M|  }
http_template.cc:_ZN6google4grpc11transcoding12_GLOBAL__N_16Parser13ParseSegmentsEv:
   96|  14.9k|  bool ParseSegments() {
   97|  14.9k|    if (!ParseSegment()) {
  ------------------
  |  Branch (97:9): [True: 114, False: 14.8k]
  ------------------
   98|    114|      return false;
   99|    114|    }
  100|       |
  101|  5.96M|    for (;;) {
  102|  5.96M|      if (!Consume('/')) break;
  ------------------
  |  Branch (102:11): [True: 14.5k, False: 5.94M]
  ------------------
  103|  5.94M|      if (!ParseSegment()) {
  ------------------
  |  Branch (103:11): [True: 258, False: 5.94M]
  ------------------
  104|    258|        return false;
  105|    258|      }
  106|  5.94M|    }
  107|       |
  108|  14.5k|    return true;
  109|  14.8k|  }
http_template.cc:_ZN6google4grpc11transcoding12_GLOBAL__N_16Parser12ParseSegmentEv:
  112|  5.96M|  bool ParseSegment() {
  113|  5.96M|    if (!EnsureCurrent()) {
  ------------------
  |  Branch (113:9): [True: 54, False: 5.96M]
  ------------------
  114|     54|      return false;
  115|     54|    }
  116|  5.96M|    switch (current_char()) {
  117|  2.63M|      case '*': {
  ------------------
  |  Branch (117:7): [True: 2.63M, False: 3.32M]
  ------------------
  118|  2.63M|        Consume('*');
  119|  2.63M|        if (Consume('*')) {
  ------------------
  |  Branch (119:13): [True: 14.6k, False: 2.62M]
  ------------------
  120|       |          // **
  121|  14.6k|          segments_.push_back("**");
  122|  14.6k|          if (in_variable_) {
  ------------------
  |  Branch (122:15): [True: 6.59k, False: 8.05k]
  ------------------
  123|  6.59k|            return MarkVariableHasWildCardPath();
  124|  6.59k|          }
  125|  8.05k|          return true;
  126|  2.62M|        } else {
  127|  2.62M|          segments_.push_back("*");
  128|  2.62M|          return true;
  129|  2.62M|        }
  130|  2.63M|      }
  131|       |
  132|   565k|      case '{':
  ------------------
  |  Branch (132:7): [True: 565k, False: 5.39M]
  ------------------
  133|   565k|        return ParseVariable();
  134|  2.75M|      default:
  ------------------
  |  Branch (134:7): [True: 2.75M, False: 3.20M]
  ------------------
  135|  2.75M|        return ParseLiteralSegment();
  136|  5.96M|    }
  137|  5.96M|  }
http_template.cc:_ZN6google4grpc11transcoding12_GLOBAL__N_16Parser27MarkVariableHasWildCardPathEv:
  314|  6.59k|  bool MarkVariableHasWildCardPath() {
  315|  6.59k|    if (in_variable_ && !variables_.empty()) {
  ------------------
  |  Branch (315:9): [True: 6.59k, False: 0]
  |  Branch (315:25): [True: 6.59k, False: 0]
  ------------------
  316|  6.59k|      CurrentVariable().has_wildcard_path = true;
  317|  6.59k|      return true;
  318|  6.59k|    } else {
  319|       |      // something's wrong we're not in a variable
  320|      0|      return false;
  321|      0|    }
  322|  6.59k|  }
http_template.cc:_ZN6google4grpc11transcoding12_GLOBAL__N_16Parser15CurrentVariableEv:
  278|  3.50M|  HttpTemplate::Variable &CurrentVariable() { return variables_.back(); }
http_template.cc:_ZN6google4grpc11transcoding12_GLOBAL__N_16Parser13ParseVariableEv:
  140|   565k|  bool ParseVariable() {
  141|   565k|    if (!Consume('{')) {
  ------------------
  |  Branch (141:9): [True: 0, False: 565k]
  ------------------
  142|      0|      return false;
  143|      0|    }
  144|   565k|    if (!StartVariable()) {
  ------------------
  |  Branch (144:9): [True: 7, False: 565k]
  ------------------
  145|      7|      return false;
  146|      7|    }
  147|   565k|    if (!ParseFieldPath()) {
  ------------------
  |  Branch (147:9): [True: 80, False: 565k]
  ------------------
  148|     80|      return false;
  149|     80|    }
  150|   565k|    if (Consume('=')) {
  ------------------
  |  Branch (150:9): [True: 14.0k, False: 551k]
  ------------------
  151|  14.0k|      if (!ParseSegments()) {
  ------------------
  |  Branch (151:11): [True: 29, False: 14.0k]
  ------------------
  152|     29|        return false;
  153|     29|      }
  154|   551k|    } else {
  155|       |      // {field_path} is equivalent to {field_path=*}
  156|   551k|      segments_.push_back("*");
  157|   551k|    }
  158|   565k|    if (!EndVariable()) {
  ------------------
  |  Branch (158:9): [True: 0, False: 565k]
  ------------------
  159|      0|      return false;
  160|      0|    }
  161|   565k|    if (!Consume('}')) {
  ------------------
  |  Branch (161:9): [True: 177, False: 565k]
  ------------------
  162|    177|      return false;
  163|    177|    }
  164|   565k|    return true;
  165|   565k|  }
http_template.cc:_ZN6google4grpc11transcoding12_GLOBAL__N_16Parser13StartVariableEv:
  280|   565k|  bool StartVariable() {
  281|   565k|    if (!in_variable_) {
  ------------------
  |  Branch (281:9): [True: 565k, False: 7]
  ------------------
  282|   565k|      variables_.push_back(HttpTemplate::Variable{});
  283|   565k|      CurrentVariable().start_segment = segments_.size();
  284|   565k|      CurrentVariable().has_wildcard_path = false;
  285|   565k|      in_variable_ = true;
  286|   565k|      return true;
  287|   565k|    } else {
  288|       |      // nested variables are not allowed
  289|      7|      return false;
  290|      7|    }
  291|   565k|  }
http_template.cc:_ZN6google4grpc11transcoding12_GLOBAL__N_16Parser14ParseFieldPathEv:
  177|   565k|  bool ParseFieldPath() {
  178|   565k|    if (!ParseIdentifier()) {
  ------------------
  |  Branch (178:9): [True: 48, False: 565k]
  ------------------
  179|     48|      return false;
  180|     48|    }
  181|  1.23M|    while (Consume('.')) {
  ------------------
  |  Branch (181:12): [True: 671k, False: 565k]
  ------------------
  182|   671k|      if (!ParseIdentifier()) {
  ------------------
  |  Branch (182:11): [True: 32, False: 671k]
  ------------------
  183|     32|        return false;
  184|     32|      }
  185|   671k|    }
  186|   565k|    return true;
  187|   565k|  }
http_template.cc:_ZN6google4grpc11transcoding12_GLOBAL__N_16Parser15ParseIdentifierEv:
  196|  1.23M|  bool ParseIdentifier() {
  197|  1.23M|    std::string idf;
  198|       |
  199|       |    // Initialize to false to handle empty literal.
  200|  1.23M|    bool result = false;
  201|       |
  202|  12.9M|    while (NextChar()) {
  ------------------
  |  Branch (202:12): [True: 12.9M, False: 183]
  ------------------
  203|  12.9M|      char c;
  204|  12.9M|      switch (c = current_char()) {
  205|   671k|        case '.':
  ------------------
  |  Branch (205:9): [True: 671k, False: 12.2M]
  ------------------
  206|  1.22M|        case '}':
  ------------------
  |  Branch (206:9): [True: 551k, False: 12.4M]
  ------------------
  207|  1.23M|        case '=':
  ------------------
  |  Branch (207:9): [True: 14.0k, False: 12.9M]
  ------------------
  208|  1.23M|          return result && AddFieldIdentifier(std::move(idf));
  ------------------
  |  Branch (208:18): [True: 1.23M, False: 30]
  |  Branch (208:28): [True: 1.23M, False: 0]
  ------------------
  209|  11.7M|        default:
  ------------------
  |  Branch (209:9): [True: 11.7M, False: 1.23M]
  ------------------
  210|  11.7M|          Consume(c);
  211|  11.7M|          idf.push_back(c);
  212|  11.7M|          break;
  213|  12.9M|      }
  214|  11.7M|      result = true;
  215|  11.7M|    }
  216|    183|    return result && AddFieldIdentifier(std::move(idf));
  ------------------
  |  Branch (216:12): [True: 133, False: 50]
  |  Branch (216:22): [True: 133, False: 0]
  ------------------
  217|  1.23M|  }
http_template.cc:_ZN6google4grpc11transcoding12_GLOBAL__N_16Parser18AddFieldIdentifierENSt3__112basic_stringIcNS4_11char_traitsIcEENS4_9allocatorIcEEEE:
  304|  1.23M|  bool AddFieldIdentifier(std::string id) {
  305|  1.23M|    if (in_variable_ && !variables_.empty()) {
  ------------------
  |  Branch (305:9): [True: 1.23M, False: 0]
  |  Branch (305:25): [True: 1.23M, False: 0]
  ------------------
  306|  1.23M|      CurrentVariable().field_path.emplace_back(std::move(id));
  307|  1.23M|      return true;
  308|  1.23M|    } else {
  309|       |      // something's wrong we're not in a variable
  310|      0|      return false;
  311|      0|    }
  312|  1.23M|  }
http_template.cc:_ZN6google4grpc11transcoding12_GLOBAL__N_16Parser11EndVariableEv:
  293|   565k|  bool EndVariable() {
  294|   565k|    if (in_variable_ && !variables_.empty()) {
  ------------------
  |  Branch (294:9): [True: 565k, False: 0]
  |  Branch (294:25): [True: 565k, False: 0]
  ------------------
  295|   565k|      CurrentVariable().end_segment = segments_.size();
  296|   565k|      in_variable_ = false;
  297|   565k|      return ValidateVariable(CurrentVariable());
  298|   565k|    } else {
  299|       |      // something's wrong we're not in a variable
  300|      0|      return false;
  301|      0|    }
  302|   565k|  }
http_template.cc:_ZN6google4grpc11transcoding12_GLOBAL__N_16Parser16ValidateVariableERKNS1_12HttpTemplate8VariableE:
  324|   565k|  bool ValidateVariable(const HttpTemplate::Variable &var) {
  325|   565k|    return !var.field_path.empty() && (var.start_segment < var.end_segment) &&
  ------------------
  |  Branch (325:12): [True: 565k, False: 0]
  |  Branch (325:39): [True: 565k, False: 0]
  ------------------
  326|   565k|           (var.end_segment <= static_cast<int>(segments_.size()));
  ------------------
  |  Branch (326:12): [True: 565k, False: 0]
  ------------------
  327|   565k|  }
http_template.cc:_ZN6google4grpc11transcoding12_GLOBAL__N_16Parser19ParseLiteralSegmentEv:
  167|  2.75M|  bool ParseLiteralSegment() {
  168|  2.75M|    std::string ls;
  169|  2.75M|    if (!ParseLiteral(&ls)) {
  ------------------
  |  Branch (169:9): [True: 25, False: 2.75M]
  ------------------
  170|     25|      return false;
  171|     25|    }
  172|  2.75M|    segments_.push_back(ls);
  173|  2.75M|    return true;
  174|  2.75M|  }
http_template.cc:_ZN6google4grpc11transcoding12_GLOBAL__N_16Parser12ParseLiteralEPNSt3__112basic_stringIcNS4_11char_traitsIcEENS4_9allocatorIcEEEE:
  219|  2.75M|  bool ParseLiteral(std::string *lit) {
  220|  2.75M|    if (!EnsureCurrent()) {
  ------------------
  |  Branch (220:9): [True: 33, False: 2.75M]
  ------------------
  221|     33|      return false;
  222|     33|    }
  223|       |
  224|       |    // Initialize to false in case we encounter an empty literal.
  225|  2.75M|    bool result = false;
  226|       |
  227|  17.1M|    for (;;) {
  228|  17.1M|      char c;
  229|  17.1M|      switch (c = current_char()) {
  230|  2.75M|        case '/':
  ------------------
  |  Branch (230:9): [True: 2.75M, False: 14.4M]
  ------------------
  231|  2.75M|        case ':':
  ------------------
  |  Branch (231:9): [True: 54, False: 17.1M]
  ------------------
  232|  2.75M|        case '}':
  ------------------
  |  Branch (232:9): [True: 7.35k, False: 17.1M]
  ------------------
  233|  2.75M|          return result;
  234|  14.4M|        default:
  ------------------
  |  Branch (234:9): [True: 14.4M, False: 2.75M]
  ------------------
  235|  14.4M|          Consume(c);
  236|  14.4M|          lit->push_back(c);
  237|  14.4M|          break;
  238|  17.1M|      }
  239|       |
  240|  14.4M|      result = true;
  241|       |
  242|  14.4M|      if (!NextChar()) {
  ------------------
  |  Branch (242:11): [True: 313, False: 14.4M]
  ------------------
  243|    313|        break;
  244|    313|      }
  245|  14.4M|    }
  246|    313|    return result;
  247|  2.75M|  }
http_template.cc:_ZN6google4grpc11transcoding12_GLOBAL__N_16Parser13EnsureCurrentEv:
  262|  8.72M|  bool EnsureCurrent() { return tb_ < te_ || NextChar(); }
  ------------------
  |  Branch (262:33): [True: 2.75M, False: 5.96M]
  |  Branch (262:46): [True: 5.96M, False: 507]
  ------------------
http_template.cc:_ZNK6google4grpc11transcoding12_GLOBAL__N_16Parser12current_charEv:
  274|  76.4M|  char current_char() const {
  275|  76.4M|    return tb_ < te_ && te_ <= input_.size() ? input_[te_ - 1] : -1;
  ------------------
  |  Branch (275:12): [True: 76.4M, False: 0]
  |  Branch (275:25): [True: 76.4M, False: 0]
  ------------------
  276|  76.4M|  }
http_template.cc:_ZN6google4grpc11transcoding12_GLOBAL__N_16Parser9ParseVerbEv:
  190|     63|  bool ParseVerb() {
  191|     63|    if (!Consume(':')) return false;
  ------------------
  |  Branch (191:9): [True: 0, False: 63]
  ------------------
  192|     63|    if (!ParseLiteral(&verb_)) return false;
  ------------------
  |  Branch (192:9): [True: 34, False: 29]
  ------------------
  193|     29|    return true;
  194|     63|  }
http_template.cc:_ZN6google4grpc11transcoding12_GLOBAL__N_16Parser16ConsumedAllInputEv:
  260|    540|  bool ConsumedAllInput() { return tb_ >= input_.size(); }
http_template.cc:_ZN6google4grpc11transcoding12_GLOBAL__N_16Parser20PostProcessVariablesEv:
  329|    443|  void PostProcessVariables() {
  330|   408k|    for (auto &var : variables_) {
  ------------------
  |  Branch (330:20): [True: 408k, False: 443]
  ------------------
  331|   408k|      if (var.has_wildcard_path) {
  ------------------
  |  Branch (331:11): [True: 769, False: 407k]
  ------------------
  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|    769|        var.end_segment = (var.end_segment - segments_.size() - 1);
  338|    769|      }
  339|   408k|    }
  340|    443|  }
http_template.cc:_ZN6google4grpc11transcoding12_GLOBAL__N_16Parser13ValidatePartsEv:
   60|    443|  bool ValidateParts() {
   61|    443|    bool found_wild_card = false;
   62|  4.39M|    for (size_t i = 0; i < segments_.size(); i++) {
  ------------------
  |  Branch (62:24): [True: 4.39M, False: 388]
  ------------------
   63|  4.39M|      if (!found_wild_card) {
  ------------------
  |  Branch (63:11): [True: 4.32M, False: 65.5k]
  ------------------
   64|  4.32M|        if (segments_[i] == HttpTemplate::kWildCardPathKey) {
  ------------------
  |  Branch (64:13): [True: 201, False: 4.32M]
  ------------------
   65|    201|          found_wild_card = true;
   66|    201|        }
   67|  4.32M|      } else if (segments_[i] == HttpTemplate::kSingleParameterKey ||
  ------------------
  |  Branch (67:18): [True: 0, False: 65.5k]
  ------------------
   68|  65.5k|                 segments_[i] == HttpTemplate::kWildCardPathPartKey ||
  ------------------
  |  Branch (68:18): [True: 24, False: 65.5k]
  ------------------
   69|  65.5k|                 segments_[i] == HttpTemplate::kWildCardPathKey) {
  ------------------
  |  Branch (69:18): [True: 31, False: 65.5k]
  ------------------
   70|     55|        return false;
   71|     55|      }
   72|  4.39M|    }
   73|    388|    return true;
   74|    443|  }
http_template.cc:_ZN6google4grpc11transcoding12_GLOBAL__N_16Parser8segmentsEv:
   55|    388|  std::vector<std::string> &segments() { return segments_; }
http_template.cc:_ZN6google4grpc11transcoding12_GLOBAL__N_16Parser4verbEv:
   56|    388|  std::string &verb() { return verb_; }
http_template.cc:_ZN6google4grpc11transcoding12_GLOBAL__N_16Parser9variablesEv:
   57|    388|  std::vector<HttpTemplate::Variable> &variables() { return variables_; }

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