/proc/self/cwd/src/http_template.cc

Source (jump to first uncovered line)
// Copyright 2016 Google Inc. All Rights Reserved.
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
//    http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.
//
////////////////////////////////////////////////////////////////////////////////
//
#include "grpc_transcoding/http_template.h"

#include <string>
#include <vector>

namespace google {
namespace grpc {
namespace transcoding {

namespace {

// TODO: implement an error sink.

// HTTP Template Grammar:
// Questions:
//   - what are the constraints on LITERAL and IDENT?
//   - what is the character set for the grammar?
//
// Template = "/" | "/" Segments [ Verb ] ;
// Segments = Segment { "/" Segment } ;
// Segment  = "*" | "**" | LITERAL | Variable ;
// Variable = "{" FieldPath [ "=" Segments ] "}" ;
// FieldPath = IDENT { "." IDENT } ;
// Verb     = ":" LITERAL ;
class Parser {
 public:
  Parser(const std::string &input)
      : input_(input), tb_(0), te_(0), in_variable_(false) {}

  bool Parse() {
    if (!ParseTemplate() || !ConsumedAllInput()) {
      return false;
    }
    PostProcessVariables();
    return true;
  }

  std::vector<std::string> &segments() { return segments_; }
  std::string &verb() { return verb_; }
  std::vector<HttpTemplate::Variable> &variables() { return variables_; }

  // only constant path segments are allowed after '**'.
  bool ValidateParts() {
    bool found_wild_card = false;
    for (size_t i = 0; i < segments_.size(); i++) {
      if (!found_wild_card) {
        if (segments_[i] == HttpTemplate::kWildCardPathKey) {
          found_wild_card = true;
        }
      } else if (segments_[i] == HttpTemplate::kSingleParameterKey ||
                 segments_[i] == HttpTemplate::kWildCardPathPartKey ||
                 segments_[i] == HttpTemplate::kWildCardPathKey) {
        return false;
      }
    }
    return true;
  }

 private:
  // Template = "/" Segments [ Verb ] ;
  bool ParseTemplate() {
    if (!Consume('/')) {
      // Expected '/'
      return false;
    }
    if (!ParseSegments()) {
      return false;
    }

    if (EnsureCurrent() && current_char() == ':') {
      if (!ParseVerb()) {
        return false;
      }
    }
    return true;
  }

  // Segments = Segment { "/" Segment } ;
  bool ParseSegments() {
    if (!ParseSegment()) {
      return false;
    }

    for (;;) {
      if (!Consume('/')) break;
      if (!ParseSegment()) {
        return false;
      }
    }

    return true;
  }

  // Segment  = "*" | "**" | LITERAL | Variable ;
  bool ParseSegment() {
    if (!EnsureCurrent()) {
      return false;
    }
    switch (current_char()) {
      case '*': {
        Consume('*');
        if (Consume('*')) {
          // **
          segments_.push_back("**");
          if (in_variable_) {
            return MarkVariableHasWildCardPath();
          }
          return true;
        } else {
          segments_.push_back("*");
          return true;
        }
      }

      case '{':
        return ParseVariable();
      default:
        return ParseLiteralSegment();
    }
  }

  // Variable = "{" FieldPath [ "=" Segments ] "}" ;
  bool ParseVariable() {
    if (!Consume('{')) {
      return false;
    }
    if (!StartVariable()) {
      return false;
    }
    if (!ParseFieldPath()) {
      return false;
    }
    if (Consume('=')) {
      if (!ParseSegments()) {
        return false;
      }
    } else {
      // {field_path} is equivalent to {field_path=*}
      segments_.push_back("*");
    }
    if (!EndVariable()) {
      return false;
    }
    if (!Consume('}')) {
      return false;
    }
    return true;
  }

  bool ParseLiteralSegment() {
    std::string ls;
    if (!ParseLiteral(&ls)) {
      return false;
    }
    segments_.push_back(ls);
    return true;
  }

  // FieldPath = IDENT { "." IDENT } ;
  bool ParseFieldPath() {
    if (!ParseIdentifier()) {
      return false;
    }
    while (Consume('.')) {
      if (!ParseIdentifier()) {
        return false;
      }
    }
    return true;
  }

  // Verb     = ":" LITERAL ;
  bool ParseVerb() {
    if (!Consume(':')) return false;
    if (!ParseLiteral(&verb_)) return false;
    return true;
  }

  bool ParseIdentifier() {
    std::string idf;

    // Initialize to false to handle empty literal.
    bool result = false;

    while (NextChar()) {
      char c;
      switch (c = current_char()) {
        case '.':
        case '}':
        case '=':
          return result && AddFieldIdentifier(std::move(idf));
        default:
          Consume(c);
          idf.push_back(c);
          break;
      }
      result = true;
    }
    return result && AddFieldIdentifier(std::move(idf));
  }

  bool ParseLiteral(std::string *lit) {
    if (!EnsureCurrent()) {
      return false;
    }

    // Initialize to false in case we encounter an empty literal.
    bool result = false;

    for (;;) {
      char c;
      switch (c = current_char()) {
        case '/':
        case ':':
        case '}':
          return result;
        default:
          Consume(c);
          lit->push_back(c);
          break;
      }

      result = true;

      if (!NextChar()) {
        break;
      }
    }
    return result;
  }

  bool Consume(char c) {
    if (tb_ >= te_ && !NextChar()) {
      return false;
    }
    if (current_char() != c) {
      return false;
    }
    tb_++;
    return true;
  }

  bool ConsumedAllInput() { return tb_ >= input_.size(); }

  bool EnsureCurrent() { return tb_ < te_ || NextChar(); }

  bool NextChar() {
    if (te_ < input_.size()) {
      te_++;
      return true;
    } else {
      return false;
    }
  }

  // Returns the character looked at.
  char current_char() const {
    return tb_ < te_ && te_ <= input_.size() ? input_[te_ - 1] : -1;
  }

  HttpTemplate::Variable &CurrentVariable() { return variables_.back(); }

  bool StartVariable() {
    if (!in_variable_) {
      variables_.push_back(HttpTemplate::Variable{});
      CurrentVariable().start_segment = segments_.size();
      CurrentVariable().has_wildcard_path = false;
      in_variable_ = true;
      return true;
    } else {
      // nested variables are not allowed
      return false;
    }
  }

  bool EndVariable() {
    if (in_variable_ && !variables_.empty()) {
      CurrentVariable().end_segment = segments_.size();
      in_variable_ = false;
      return ValidateVariable(CurrentVariable());
    } else {
      // something's wrong we're not in a variable
      return false;
    }
  }

  bool AddFieldIdentifier(std::string id) {
    if (in_variable_ && !variables_.empty()) {
      CurrentVariable().field_path.emplace_back(std::move(id));
      return true;
    } else {
      // something's wrong we're not in a variable
      return false;
    }
  }

  bool MarkVariableHasWildCardPath() {
    if (in_variable_ && !variables_.empty()) {
      CurrentVariable().has_wildcard_path = true;
      return true;
    } else {
      // something's wrong we're not in a variable
      return false;
    }
  }

  bool ValidateVariable(const HttpTemplate::Variable &var) {
    return !var.field_path.empty() && (var.start_segment < var.end_segment) &&
           (var.end_segment <= static_cast<int>(segments_.size()));
  }

  void PostProcessVariables() {
    for (auto &var : variables_) {
      if (var.has_wildcard_path) {
        // if the variable contains a '**', store the end_positon
        // relative to the end, such that -1 corresponds to the end
        // of the path. As we only support fixed path after '**',
        // this will allow the matcher code to reconstruct the variable
        // value based on the url segments.
        var.end_segment = (var.end_segment - segments_.size() - 1);
      }
    }
  }

  const std::string &input_;

  // Token delimiter indexes
  size_t tb_;
  size_t te_;

  // are we in nested Segments of a variable?
  bool in_variable_;

  std::vector<std::string> segments_;
  std::string verb_;
  std::vector<HttpTemplate::Variable> variables_;
};

}  // namespace

const char HttpTemplate::kSingleParameterKey[] = "/.";

const char HttpTemplate::kWildCardPathPartKey[] = "*";

const char HttpTemplate::kWildCardPathKey[] = "**";

std::unique_ptr<HttpTemplate> HttpTemplate::Parse(const std::string &ht) {
  if (ht == "/") {
    return std::unique_ptr<HttpTemplate>(new HttpTemplate({}, {}, {}));
  }

  Parser p(ht);
  if (!p.Parse() || !p.ValidateParts()) {
    return nullptr;
  }

  return std::unique_ptr<HttpTemplate>(new HttpTemplate(
      std::move(p.segments()), std::move(p.verb()), std::move(p.variables())));
}

}  // namespace transcoding
}  // namespace grpc
}  // namespace google

Coverage Report

Created: 2025-02-02 06:38

Line	Count	Source (jump to first uncovered line)
1		// Copyright 2016 Google Inc. All Rights Reserved.
2		//
3		// Licensed under the Apache License, Version 2.0 (the "License");
4		// you may not use this file except in compliance with the License.
5		// You may obtain a copy of the License at
6		//
7		// http://www.apache.org/licenses/LICENSE-2.0
8		//
9		// Unless required by applicable law or agreed to in writing, software
10		// distributed under the License is distributed on an "AS IS" BASIS,
11		// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12		// See the License for the specific language governing permissions and
13		// limitations under the License.
14		//
15		////////////////////////////////////////////////////////////////////////////////
16		//
17		#include "grpc_transcoding/http_template.h"
18
19		#include <string>
20		#include <vector>
21
22		namespace google {
23		namespace grpc {
24		namespace transcoding {
25
26		namespace {
27
28		// TODO: implement an error sink.
29
30		// HTTP Template Grammar:
31		// Questions:
32		// - what are the constraints on LITERAL and IDENT?
33		// - what is the character set for the grammar?
34		//
35		// Template = "/" \| "/" Segments [ Verb ] ;
36		// Segments = Segment { "/" Segment } ;
37		// Segment = "" \| "*" \| LITERAL \| Variable ;
38		// Variable = "{" FieldPath [ "=" Segments ] "}" ;
39		// FieldPath = IDENT { "." IDENT } ;
40		// Verb = ":" LITERAL ;
41		class Parser {
42		public:
43		Parser(const std::string &input)
44	1.01k	: input_(input), tb_(0), te_(0), in_variable_(false) {}
45
46	1.01k	bool Parse() {
47	1.01k	if (!ParseTemplate() \|\| !ConsumedAllInput()) {
48	508	return false;
49	508	}
50	509	PostProcessVariables();
51	509	return true;
52	1.01k	}
53
54	441	std::vector<std::string> &segments() { return segments_; }
55	441	std::string &verb() { return verb_; }
56	441	std::vector<HttpTemplate::Variable> &variables() { return variables_; }
57
58		// only constant path segments are allowed after '**'.
59	509	bool ValidateParts() {
60	509	bool found_wild_card = false;
61	3.74M	for (size_t i = 0; i < segments_.size(); i++) {
62	3.74M	if (!found_wild_card) {
63	3.73M	if (segments_[i] == HttpTemplate::kWildCardPathKey) {
64	216	found_wild_card = true;
65	216	}
66	3.73M	} else if (segments_[i] == HttpTemplate::kSingleParameterKey \|\|
67	4.17k	segments_[i] == HttpTemplate::kWildCardPathPartKey \|\|
68	4.17k	segments_[i] == HttpTemplate::kWildCardPathKey) {
69	68	return false;
70	68	}
71	3.74M	}
72	441	return true;
73	509	}
74
75		private:
76		// Template = "/" Segments [ Verb ] ;
77	1.01k	bool ParseTemplate() {
78	1.01k	if (!Consume('/')) {
79		// Expected '/'
80	26	return false;
81	26	}
82	991	if (!ParseSegments()) {
83	368	return false;
84	368	}
85
86	623	if (EnsureCurrent() && current_char() == ':') {
87	57	if (!ParseVerb()) {
88	30	return false;
89	30	}
90	57	}
91	593	return true;
92	623	}
93
94		// Segments = Segment { "/" Segment } ;
95	17.3k	bool ParseSegments() {
96	17.3k	if (!ParseSegment()) {
97	128	return false;
98	128	}
99
100	5.64M	for (;;) {
101	5.64M	if (!Consume('/')) break;
102	5.62M	if (!ParseSegment()) {
103	268	return false;
104	268	}
105	5.62M	}
106
107	16.9k	return true;
108	17.2k	}
109
110		// Segment = "" \| "*" \| LITERAL \| Variable ;
111	5.64M	bool ParseSegment() {
112	5.64M	if (!EnsureCurrent()) {
113	49	return false;
114	49	}
115	5.64M	switch (current_char()) {
116	2.85M	case '*': {
117	2.85M	Consume('*');
118	2.85M	if (Consume('*')) {
119		// **
120	42.3k	segments_.push_back("**");
121	42.3k	if (in_variable_) {
122	17.2k	return MarkVariableHasWildCardPath();
123	17.2k	}
124	25.0k	return true;
125	2.81M	} else {
126	2.81M	segments_.push_back("*");
127	2.81M	return true;
128	2.81M	}
129	2.85M	}
130
131	441k	case '{':
132	441k	return ParseVariable();
133	2.34M	default:
134	2.34M	return ParseLiteralSegment();
135	5.64M	}
136	5.64M	}
137
138		// Variable = "{" FieldPath [ "=" Segments ] "}" ;
139	441k	bool ParseVariable() {
140	441k	if (!Consume('{')) {
141	0	return false;
142	0	}
143	441k	if (!StartVariable()) {
144	8	return false;
145	8	}
146	441k	if (!ParseFieldPath()) {
147	101	return false;
148	101	}
149	440k	if (Consume('=')) {
150	16.3k	if (!ParseSegments()) {
151	28	return false;
152	28	}
153	424k	} else {
154		// {field_path} is equivalent to {field_path=*}
155	424k	segments_.push_back("*");
156	424k	}
157	440k	if (!EndVariable()) {
158	0	return false;
159	0	}
160	440k	if (!Consume('}')) {
161	185	return false;
162	185	}
163	440k	return true;
164	440k	}
165
166	2.34M	bool ParseLiteralSegment() {
167	2.34M	std::string ls;
168	2.34M	if (!ParseLiteral(&ls)) {
169	25	return false;
170	25	}
171	2.34M	segments_.push_back(ls);
172	2.34M	return true;
173	2.34M	}
174
175		// FieldPath = IDENT { "." IDENT } ;
176	441k	bool ParseFieldPath() {
177	441k	if (!ParseIdentifier()) {
178	66	return false;
179	66	}
180	1.08M	while (Consume('.')) {
181	645k	if (!ParseIdentifier()) {
182	35	return false;
183	35	}
184	645k	}
185	440k	return true;
186	440k	}
187
188		// Verb = ":" LITERAL ;
189	57	bool ParseVerb() {
190	57	if (!Consume(':')) return false;
191	57	if (!ParseLiteral(&verb_)) return false;
192	27	return true;
193	57	}
194
195	1.08M	bool ParseIdentifier() {
196	1.08M	std::string idf;
197
198		// Initialize to false to handle empty literal.
199	1.08M	bool result = false;
200
201	9.52M	while (NextChar()) {
202	9.52M	char c;
203	9.52M	switch (c = current_char()) {
204	645k	case '.':
205	1.07M	case '}':
206	1.08M	case '=':
207	1.08M	return result && AddFieldIdentifier(std::move(idf));
208	8.43M	default:
209	8.43M	Consume(c);
210	8.43M	idf.push_back(c);
211	8.43M	break;
212	9.52M	}
213	8.43M	result = true;
214	8.43M	}
215	211	return result && AddFieldIdentifier(std::move(idf));
216	1.08M	}
217
218	2.34M	bool ParseLiteral(std::string *lit) {
219	2.34M	if (!EnsureCurrent()) {
220	29	return false;
221	29	}
222
223		// Initialize to false in case we encounter an empty literal.
224	2.34M	bool result = false;
225
226	29.6M	for (;;) {
227	29.6M	char c;
228	29.6M	switch (c = current_char()) {
229	2.34M	case '/':
230	2.34M	case ':':
231	2.34M	case '}':
232	2.34M	return result;
233	27.3M	default:
234	27.3M	Consume(c);
235	27.3M	lit->push_back(c);
236	27.3M	break;
237	29.6M	}
238
239	27.3M	result = true;
240
241	27.3M	if (!NextChar()) {
242	381	break;
243	381	}
244	27.3M	}
245	381	return result;
246	2.34M	}
247
248	49.5M	bool Consume(char c) {
249	49.5M	if (tb_ >= te_ && !NextChar()) {
250	1.01k	return false;
251	1.01k	}
252	49.5M	if (current_char() != c) {
253	3.69M	return false;
254	3.69M	}
255	45.8M	tb_++;
256	45.8M	return true;
257	49.5M	}
258
259	593	bool ConsumedAllInput() { return tb_ >= input_.size(); }
260
261	7.99M	bool EnsureCurrent() { return tb_ < te_ \|\| NextChar(); }
262
263	45.8M	bool NextChar() {
264	45.8M	if (te_ < input_.size()) {
265	45.8M	te_++;
266	45.8M	return true;
267	45.8M	} else {
268	2.16k	return false;
269	2.16k	}
270	45.8M	}
271
272		// Returns the character looked at.
273	94.3M	char current_char() const {
274	94.3M	return tb_ < te_ && te_ <= input_.size() ? input_[te_ - 1] : -1;
275	94.3M	}
276
277	2.86M	HttpTemplate::Variable &CurrentVariable() { return variables_.back(); }
278
279	441k	bool StartVariable() {
280	441k	if (!in_variable_) {
281	441k	variables_.push_back(HttpTemplate::Variable{});
282	441k	CurrentVariable().start_segment = segments_.size();
283	441k	CurrentVariable().has_wildcard_path = false;
284	441k	in_variable_ = true;
285	441k	return true;
286	441k	} else {
287		// nested variables are not allowed
288	8	return false;
289	8	}
290	441k	}
291
292	440k	bool EndVariable() {
293	440k	if (in_variable_ && !variables_.empty()) {
294	440k	CurrentVariable().end_segment = segments_.size();
295	440k	in_variable_ = false;
296	440k	return ValidateVariable(CurrentVariable());
297	440k	} else {
298		// something's wrong we're not in a variable
299	0	return false;
300	0	}
301	440k	}
302
303	1.08M	bool AddFieldIdentifier(std::string id) {
304	1.08M	if (in_variable_ && !variables_.empty()) {
305	1.08M	CurrentVariable().field_path.emplace_back(std::move(id));
306	1.08M	return true;
307	1.08M	} else {
308		// something's wrong we're not in a variable
309	0	return false;
310	0	}
311	1.08M	}
312
313	17.2k	bool MarkVariableHasWildCardPath() {
314	17.2k	if (in_variable_ && !variables_.empty()) {
315	17.2k	CurrentVariable().has_wildcard_path = true;
316	17.2k	return true;
317	17.2k	} else {
318		// something's wrong we're not in a variable
319	0	return false;
320	0	}
321	17.2k	}
322
323	440k	bool ValidateVariable(const HttpTemplate::Variable &var) {
324	440k	return !var.field_path.empty() && (var.start_segment < var.end_segment) &&
325	440k	(var.end_segment <= static_cast<int>(segments_.size()));
326	440k	}
327
328	509	void PostProcessVariables() {
329	218k	for (auto &var : variables_) {
330	218k	if (var.has_wildcard_path) {
331		// if the variable contains a '**', store the end_positon
332		// relative to the end, such that -1 corresponds to the end
333		// of the path. As we only support fixed path after '**',
334		// this will allow the matcher code to reconstruct the variable
335		// value based on the url segments.
336	5.11k	var.end_segment = (var.end_segment - segments_.size() - 1);
337	5.11k	}
338	218k	}
339	509	}
340
341		const std::string &input_;
342
343		// Token delimiter indexes
344		size_t tb_;
345		size_t te_;
346
347		// are we in nested Segments of a variable?
348		bool in_variable_;
349
350		std::vector<std::string> segments_;
351		std::string verb_;
352		std::vector<HttpTemplate::Variable> variables_;
353		};
354
355		} // namespace
356
357		const char HttpTemplate::kSingleParameterKey[] = "/.";
358
359		const char HttpTemplate::kWildCardPathPartKey[] = "*";
360
361		const char HttpTemplate::kWildCardPathKey[] = "**";
362
363	1.01k	std::unique_ptr<HttpTemplate> HttpTemplate::Parse(const std::string &ht) {
364	1.01k	if (ht == "/") {
365	1	return std::unique_ptr<HttpTemplate>(new HttpTemplate({}, {}, {}));
366	1	}
367
368	1.01k	Parser p(ht);
369	1.01k	if (!p.Parse() \|\| !p.ValidateParts()) {
370	576	return nullptr;
371	576	}
372
373	441	return std::unique_ptr<HttpTemplate>(new HttpTemplate(
374	441	std::move(p.segments()), std::move(p.verb()), std::move(p.variables())));
375	1.01k	}
376
377		} // namespace transcoding
378		} // namespace grpc
379		} // namespace google