_ZN6google4grpc11transcoding12HttpTemplate5ParseERKNSt3__112basic_stringIcNS3_11char_traitsIcEENS3_9allocatorIcEEEE:
  364|    945|std::unique_ptr<HttpTemplate> HttpTemplate::Parse(const std::string &ht) {
  365|    945|  if (ht == "/") {
  ------------------
  |  Branch (365:7): [True: 1, False: 944]
  ------------------
  366|      1|    return std::unique_ptr<HttpTemplate>(new HttpTemplate({}, {}, {}));
  367|      1|  }
  368|       |
  369|    944|  Parser p(ht);
  370|    944|  if (!p.Parse() || !p.ValidateParts()) {
  ------------------
  |  Branch (370:7): [True: 486, False: 458]
  |  Branch (370:21): [True: 72, False: 386]
  ------------------
  371|    558|    return nullptr;
  372|    558|  }
  373|       |
  374|    386|  return std::unique_ptr<HttpTemplate>(new HttpTemplate(
  375|    386|      std::move(p.segments()), std::move(p.verb()), std::move(p.variables())));
  376|    944|}
http_template.cc:_ZN6google4grpc11transcoding12_GLOBAL__N_16ParserC2ERKNSt3__112basic_stringIcNS4_11char_traitsIcEENS4_9allocatorIcEEEE:
   45|    944|      : input_(input), tb_(0), te_(0), in_variable_(false) {}
http_template.cc:_ZN6google4grpc11transcoding12_GLOBAL__N_16Parser5ParseEv:
   47|    944|  bool Parse() {
   48|    944|    if (!ParseTemplate() || !ConsumedAllInput()) {
  ------------------
  |  Branch (48:9): [True: 390, False: 554]
  |  Branch (48:29): [True: 96, False: 458]
  ------------------
   49|    486|      return false;
   50|    486|    }
   51|    458|    PostProcessVariables();
   52|    458|    return true;
   53|    944|  }
http_template.cc:_ZN6google4grpc11transcoding12_GLOBAL__N_16Parser13ParseTemplateEv:
   78|    944|  bool ParseTemplate() {
   79|    944|    if (!Consume('/')) {
  ------------------
  |  Branch (79:9): [True: 26, False: 918]
  ------------------
   80|       |      // Expected '/'
   81|     26|      return false;
   82|     26|    }
   83|    918|    if (!ParseSegments()) {
  ------------------
  |  Branch (83:9): [True: 321, False: 597]
  ------------------
   84|    321|      return false;
   85|    321|    }
   86|       |
   87|    597|    if (EnsureCurrent() && current_char() == ':') {
  ------------------
  |  Branch (87:9): [True: 161, False: 436]
  |  Branch (87:28): [True: 69, False: 92]
  ------------------
   88|     69|      if (!ParseVerb()) {
  ------------------
  |  Branch (88:11): [True: 43, False: 26]
  ------------------
   89|     43|        return false;
   90|     43|      }
   91|     69|    }
   92|    554|    return true;
   93|    597|  }
http_template.cc:_ZN6google4grpc11transcoding12_GLOBAL__N_16Parser7ConsumeEc:
  249|  39.4M|  bool Consume(char c) {
  250|  39.4M|    if (tb_ >= te_ && !NextChar()) {
  ------------------
  |  Branch (250:9): [True: 3.41M, False: 36.0M]
  |  Branch (250:23): [True: 930, False: 3.41M]
  ------------------
  251|    930|      return false;
  252|    930|    }
  253|  39.4M|    if (current_char() != c) {
  ------------------
  |  Branch (253:9): [True: 3.75M, False: 35.7M]
  ------------------
  254|  3.75M|      return false;
  255|  3.75M|    }
  256|  35.7M|    tb_++;
  257|  35.7M|    return true;
  258|  39.4M|  }
http_template.cc:_ZN6google4grpc11transcoding12_GLOBAL__N_16Parser8NextCharEv:
  264|  35.7M|  bool NextChar() {
  265|  35.7M|    if (te_ < input_.size()) {
  ------------------
  |  Branch (265:9): [True: 35.7M, False: 1.95k]
  ------------------
  266|  35.7M|      te_++;
  267|  35.7M|      return true;
  268|  35.7M|    } else {
  269|  1.95k|      return false;
  270|  1.95k|    }
  271|  35.7M|  }
http_template.cc:_ZN6google4grpc11transcoding12_GLOBAL__N_16Parser13ParseSegmentsEv:
   96|  9.51k|  bool ParseSegments() {
   97|  9.51k|    if (!ParseSegment()) {
  ------------------
  |  Branch (97:9): [True: 117, False: 9.40k]
  ------------------
   98|    117|      return false;
   99|    117|    }
  100|       |
  101|  6.41M|    for (;;) {
  102|  6.41M|      if (!Consume('/')) break;
  ------------------
  |  Branch (102:11): [True: 9.17k, False: 6.41M]
  ------------------
  103|  6.41M|      if (!ParseSegment()) {
  ------------------
  |  Branch (103:11): [True: 230, False: 6.41M]
  ------------------
  104|    230|        return false;
  105|    230|      }
  106|  6.41M|    }
  107|       |
  108|  9.17k|    return true;
  109|  9.40k|  }
http_template.cc:_ZN6google4grpc11transcoding12_GLOBAL__N_16Parser12ParseSegmentEv:
  112|  6.42M|  bool ParseSegment() {
  113|  6.42M|    if (!EnsureCurrent()) {
  ------------------
  |  Branch (113:9): [True: 51, False: 6.42M]
  ------------------
  114|     51|      return false;
  115|     51|    }
  116|  6.42M|    switch (current_char()) {
  117|  3.02M|      case '*': {
  ------------------
  |  Branch (117:7): [True: 3.02M, False: 3.39M]
  ------------------
  118|  3.02M|        Consume('*');
  119|  3.02M|        if (Consume('*')) {
  ------------------
  |  Branch (119:13): [True: 14.1k, False: 3.01M]
  ------------------
  120|       |          // **
  121|  14.1k|          segments_.push_back("**");
  122|  14.1k|          if (in_variable_) {
  ------------------
  |  Branch (122:15): [True: 9.22k, False: 4.87k]
  ------------------
  123|  9.22k|            return MarkVariableHasWildCardPath();
  124|  9.22k|          }
  125|  4.87k|          return true;
  126|  3.01M|        } else {
  127|  3.01M|          segments_.push_back("*");
  128|  3.01M|          return true;
  129|  3.01M|        }
  130|  3.02M|      }
  131|       |
  132|   370k|      case '{':
  ------------------
  |  Branch (132:7): [True: 370k, False: 6.04M]
  ------------------
  133|   370k|        return ParseVariable();
  134|  3.02M|      default:
  ------------------
  |  Branch (134:7): [True: 3.02M, False: 3.39M]
  ------------------
  135|  3.02M|        return ParseLiteralSegment();
  136|  6.42M|    }
  137|  6.42M|  }
http_template.cc:_ZN6google4grpc11transcoding12_GLOBAL__N_16Parser27MarkVariableHasWildCardPathEv:
  314|  9.22k|  bool MarkVariableHasWildCardPath() {
  315|  9.22k|    if (in_variable_ && !variables_.empty()) {
  ------------------
  |  Branch (315:9): [True: 9.22k, False: 0]
  |  Branch (315:25): [True: 9.22k, False: 0]
  ------------------
  316|  9.22k|      CurrentVariable().has_wildcard_path = true;
  317|  9.22k|      return true;
  318|  9.22k|    } else {
  319|       |      // something's wrong we're not in a variable
  320|      0|      return false;
  321|      0|    }
  322|  9.22k|  }
http_template.cc:_ZN6google4grpc11transcoding12_GLOBAL__N_16Parser15CurrentVariableEv:
  278|  2.48M|  HttpTemplate::Variable &CurrentVariable() { return variables_.back(); }
http_template.cc:_ZN6google4grpc11transcoding12_GLOBAL__N_16Parser13ParseVariableEv:
  140|   370k|  bool ParseVariable() {
  141|   370k|    if (!Consume('{')) {
  ------------------
  |  Branch (141:9): [True: 0, False: 370k]
  ------------------
  142|      0|      return false;
  143|      0|    }
  144|   370k|    if (!StartVariable()) {
  ------------------
  |  Branch (144:9): [True: 8, False: 370k]
  ------------------
  145|      8|      return false;
  146|      8|    }
  147|   370k|    if (!ParseFieldPath()) {
  ------------------
  |  Branch (147:9): [True: 76, False: 370k]
  ------------------
  148|     76|      return false;
  149|     76|    }
  150|   370k|    if (Consume('=')) {
  ------------------
  |  Branch (150:9): [True: 8.60k, False: 361k]
  ------------------
  151|  8.60k|      if (!ParseSegments()) {
  ------------------
  |  Branch (151:11): [True: 26, False: 8.57k]
  ------------------
  152|     26|        return false;
  153|     26|      }
  154|   361k|    } else {
  155|       |      // {field_path} is equivalent to {field_path=*}
  156|   361k|      segments_.push_back("*");
  157|   361k|    }
  158|   370k|    if (!EndVariable()) {
  ------------------
  |  Branch (158:9): [True: 0, False: 370k]
  ------------------
  159|      0|      return false;
  160|      0|    }
  161|   370k|    if (!Consume('}')) {
  ------------------
  |  Branch (161:9): [True: 164, False: 369k]
  ------------------
  162|    164|      return false;
  163|    164|    }
  164|   369k|    return true;
  165|   370k|  }
http_template.cc:_ZN6google4grpc11transcoding12_GLOBAL__N_16Parser13StartVariableEv:
  280|   370k|  bool StartVariable() {
  281|   370k|    if (!in_variable_) {
  ------------------
  |  Branch (281:9): [True: 370k, False: 8]
  ------------------
  282|   370k|      variables_.push_back(HttpTemplate::Variable{});
  283|   370k|      CurrentVariable().start_segment = segments_.size();
  284|   370k|      CurrentVariable().has_wildcard_path = false;
  285|   370k|      in_variable_ = true;
  286|   370k|      return true;
  287|   370k|    } else {
  288|       |      // nested variables are not allowed
  289|      8|      return false;
  290|      8|    }
  291|   370k|  }
http_template.cc:_ZN6google4grpc11transcoding12_GLOBAL__N_16Parser14ParseFieldPathEv:
  177|   370k|  bool ParseFieldPath() {
  178|   370k|    if (!ParseIdentifier()) {
  ------------------
  |  Branch (178:9): [True: 48, False: 370k]
  ------------------
  179|     48|      return false;
  180|     48|    }
  181|   992k|    while (Consume('.')) {
  ------------------
  |  Branch (181:12): [True: 622k, False: 370k]
  ------------------
  182|   622k|      if (!ParseIdentifier()) {
  ------------------
  |  Branch (182:11): [True: 28, False: 622k]
  ------------------
  183|     28|        return false;
  184|     28|      }
  185|   622k|    }
  186|   370k|    return true;
  187|   370k|  }
http_template.cc:_ZN6google4grpc11transcoding12_GLOBAL__N_16Parser15ParseIdentifierEv:
  196|   992k|  bool ParseIdentifier() {
  197|   992k|    std::string idf;
  198|       |
  199|       |    // Initialize to false to handle empty literal.
  200|   992k|    bool result = false;
  201|       |
  202|  7.42M|    while (NextChar()) {
  ------------------
  |  Branch (202:12): [True: 7.42M, False: 177]
  ------------------
  203|  7.42M|      char c;
  204|  7.42M|      switch (c = current_char()) {
  205|   622k|        case '.':
  ------------------
  |  Branch (205:9): [True: 622k, False: 6.79M]
  ------------------
  206|   983k|        case '}':
  ------------------
  |  Branch (206:9): [True: 361k, False: 7.06M]
  ------------------
  207|   992k|        case '=':
  ------------------
  |  Branch (207:9): [True: 8.61k, False: 7.41M]
  ------------------
  208|   992k|          return result && AddFieldIdentifier(std::move(idf));
  ------------------
  |  Branch (208:18): [True: 992k, False: 29]
  |  Branch (208:28): [True: 992k, False: 0]
  ------------------
  209|  6.42M|        default:
  ------------------
  |  Branch (209:9): [True: 6.42M, False: 992k]
  ------------------
  210|  6.42M|          Consume(c);
  211|  6.42M|          idf.push_back(c);
  212|  6.42M|          break;
  213|  7.42M|      }
  214|  6.42M|      result = true;
  215|  6.42M|    }
  216|    177|    return result && AddFieldIdentifier(std::move(idf));
  ------------------
  |  Branch (216:12): [True: 130, False: 47]
  |  Branch (216:22): [True: 130, False: 0]
  ------------------
  217|   992k|  }
http_template.cc:_ZN6google4grpc11transcoding12_GLOBAL__N_16Parser18AddFieldIdentifierENSt3__112basic_stringIcNS4_11char_traitsIcEENS4_9allocatorIcEEEE:
  304|   992k|  bool AddFieldIdentifier(std::string id) {
  305|   992k|    if (in_variable_ && !variables_.empty()) {
  ------------------
  |  Branch (305:9): [True: 992k, False: 0]
  |  Branch (305:25): [True: 992k, False: 0]
  ------------------
  306|   992k|      CurrentVariable().field_path.emplace_back(std::move(id));
  307|   992k|      return true;
  308|   992k|    } else {
  309|       |      // something's wrong we're not in a variable
  310|      0|      return false;
  311|      0|    }
  312|   992k|  }
http_template.cc:_ZN6google4grpc11transcoding12_GLOBAL__N_16Parser11EndVariableEv:
  293|   370k|  bool EndVariable() {
  294|   370k|    if (in_variable_ && !variables_.empty()) {
  ------------------
  |  Branch (294:9): [True: 370k, False: 0]
  |  Branch (294:25): [True: 370k, False: 0]
  ------------------
  295|   370k|      CurrentVariable().end_segment = segments_.size();
  296|   370k|      in_variable_ = false;
  297|   370k|      return ValidateVariable(CurrentVariable());
  298|   370k|    } else {
  299|       |      // something's wrong we're not in a variable
  300|      0|      return false;
  301|      0|    }
  302|   370k|  }
http_template.cc:_ZN6google4grpc11transcoding12_GLOBAL__N_16Parser16ValidateVariableERKNS1_12HttpTemplate8VariableE:
  324|   370k|  bool ValidateVariable(const HttpTemplate::Variable &var) {
  325|   370k|    return !var.field_path.empty() && (var.start_segment < var.end_segment) &&
  ------------------
  |  Branch (325:12): [True: 370k, False: 0]
  |  Branch (325:39): [True: 370k, False: 0]
  ------------------
  326|   370k|           (var.end_segment <= static_cast<int>(segments_.size()));
  ------------------
  |  Branch (326:12): [True: 370k, False: 0]
  ------------------
  327|   370k|  }
http_template.cc:_ZN6google4grpc11transcoding12_GLOBAL__N_16Parser19ParseLiteralSegmentEv:
  167|  3.02M|  bool ParseLiteralSegment() {
  168|  3.02M|    std::string ls;
  169|  3.02M|    if (!ParseLiteral(&ls)) {
  ------------------
  |  Branch (169:9): [True: 22, False: 3.02M]
  ------------------
  170|     22|      return false;
  171|     22|    }
  172|  3.02M|    segments_.push_back(ls);
  173|  3.02M|    return true;
  174|  3.02M|  }
http_template.cc:_ZN6google4grpc11transcoding12_GLOBAL__N_16Parser12ParseLiteralEPNSt3__112basic_stringIcNS4_11char_traitsIcEENS4_9allocatorIcEEEE:
  219|  3.02M|  bool ParseLiteral(std::string *lit) {
  220|  3.02M|    if (!EnsureCurrent()) {
  ------------------
  |  Branch (220:9): [True: 39, False: 3.02M]
  ------------------
  221|     39|      return false;
  222|     39|    }
  223|       |
  224|       |    // Initialize to false in case we encounter an empty literal.
  225|  3.02M|    bool result = false;
  226|       |
  227|  21.4M|    for (;;) {
  228|  21.4M|      char c;
  229|  21.4M|      switch (c = current_char()) {
  230|  3.01M|        case '/':
  ------------------
  |  Branch (230:9): [True: 3.01M, False: 18.4M]
  ------------------
  231|  3.01M|        case ':':
  ------------------
  |  Branch (231:9): [True: 57, False: 21.4M]
  ------------------
  232|  3.02M|        case '}':
  ------------------
  |  Branch (232:9): [True: 2.50k, False: 21.4M]
  ------------------
  233|  3.02M|          return result;
  234|  18.4M|        default:
  ------------------
  |  Branch (234:9): [True: 18.4M, False: 3.02M]
  ------------------
  235|  18.4M|          Consume(c);
  236|  18.4M|          lit->push_back(c);
  237|  18.4M|          break;
  238|  21.4M|      }
  239|       |
  240|  18.4M|      result = true;
  241|       |
  242|  18.4M|      if (!NextChar()) {
  ------------------
  |  Branch (242:11): [True: 323, False: 18.4M]
  ------------------
  243|    323|        break;
  244|    323|      }
  245|  18.4M|    }
  246|    323|    return result;
  247|  3.02M|  }
http_template.cc:_ZN6google4grpc11transcoding12_GLOBAL__N_16Parser13EnsureCurrentEv:
  262|  9.44M|  bool EnsureCurrent() { return tb_ < te_ || NextChar(); }
  ------------------
  |  Branch (262:33): [True: 3.02M, False: 6.42M]
  |  Branch (262:46): [True: 6.42M, False: 526]
  ------------------
http_template.cc:_ZNK6google4grpc11transcoding12_GLOBAL__N_16Parser12current_charEv:
  274|  74.7M|  char current_char() const {
  275|  74.7M|    return tb_ < te_ && te_ <= input_.size() ? input_[te_ - 1] : -1;
  ------------------
  |  Branch (275:12): [True: 74.7M, False: 0]
  |  Branch (275:25): [True: 74.7M, False: 0]
  ------------------
  276|  74.7M|  }
http_template.cc:_ZN6google4grpc11transcoding12_GLOBAL__N_16Parser9ParseVerbEv:
  190|     69|  bool ParseVerb() {
  191|     69|    if (!Consume(':')) return false;
  ------------------
  |  Branch (191:9): [True: 0, False: 69]
  ------------------
  192|     69|    if (!ParseLiteral(&verb_)) return false;
  ------------------
  |  Branch (192:9): [True: 43, False: 26]
  ------------------
  193|     26|    return true;
  194|     69|  }
http_template.cc:_ZN6google4grpc11transcoding12_GLOBAL__N_16Parser16ConsumedAllInputEv:
  260|    554|  bool ConsumedAllInput() { return tb_ >= input_.size(); }
http_template.cc:_ZN6google4grpc11transcoding12_GLOBAL__N_16Parser20PostProcessVariablesEv:
  329|    458|  void PostProcessVariables() {
  330|   246k|    for (auto &var : variables_) {
  ------------------
  |  Branch (330:20): [True: 246k, False: 458]
  ------------------
  331|   246k|      if (var.has_wildcard_path) {
  ------------------
  |  Branch (331:11): [True: 2.93k, False: 243k]
  ------------------
  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.93k|        var.end_segment = (var.end_segment - segments_.size() - 1);
  338|  2.93k|      }
  339|   246k|    }
  340|    458|  }
http_template.cc:_ZN6google4grpc11transcoding12_GLOBAL__N_16Parser13ValidatePartsEv:
   60|    458|  bool ValidateParts() {
   61|    458|    bool found_wild_card = false;
   62|  4.23M|    for (size_t i = 0; i < segments_.size(); i++) {
  ------------------
  |  Branch (62:24): [True: 4.23M, False: 386]
  ------------------
   63|  4.23M|      if (!found_wild_card) {
  ------------------
  |  Branch (63:11): [True: 4.22M, False: 6.69k]
  ------------------
   64|  4.22M|        if (segments_[i] == HttpTemplate::kWildCardPathKey) {
  ------------------
  |  Branch (64:13): [True: 220, False: 4.22M]
  ------------------
   65|    220|          found_wild_card = true;
   66|    220|        }
   67|  4.22M|      } else if (segments_[i] == HttpTemplate::kSingleParameterKey ||
  ------------------
  |  Branch (67:18): [True: 0, False: 6.69k]
  ------------------
   68|  6.69k|                 segments_[i] == HttpTemplate::kWildCardPathPartKey ||
  ------------------
  |  Branch (68:18): [True: 27, False: 6.66k]
  ------------------
   69|  6.69k|                 segments_[i] == HttpTemplate::kWildCardPathKey) {
  ------------------
  |  Branch (69:18): [True: 45, False: 6.62k]
  ------------------
   70|     72|        return false;
   71|     72|      }
   72|  4.23M|    }
   73|    386|    return true;
   74|    458|  }
http_template.cc:_ZN6google4grpc11transcoding12_GLOBAL__N_16Parser8segmentsEv:
   55|    386|  std::vector<std::string> &segments() { return segments_; }
http_template.cc:_ZN6google4grpc11transcoding12_GLOBAL__N_16Parser4verbEv:
   56|    386|  std::string &verb() { return verb_; }
http_template.cc:_ZN6google4grpc11transcoding12_GLOBAL__N_16Parser9variablesEv:
   57|    386|  std::vector<HttpTemplate::Variable> &variables() { return variables_; }

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