/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 <cassert>
#include <string>
#include <vector>

#include "grpc_transcoding/http_template.h"

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: 2021-09-22 07:37

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 <cassert>
18		#include <string>
19		#include <vector>
20
21		#include "grpc_transcoding/http_template.h"
22
23		namespace google {
24		namespace grpc {
25		namespace transcoding {
26
27		namespace {
28
29		// TODO: implement an error sink.
30
31		// HTTP Template Grammar:
32		// Questions:
33		// - what are the constraints on LITERAL and IDENT?
34		// - what is the character set for the grammar?
35		//
36		// Template = "/" \| "/" Segments [ Verb ] ;
37		// Segments = Segment { "/" Segment } ;
38		// Segment = "" \| "*" \| LITERAL \| Variable ;
39		// Variable = "{" FieldPath [ "=" Segments ] "}" ;
40		// FieldPath = IDENT { "." IDENT } ;
41		// Verb = ":" LITERAL ;
42		class Parser {
43		public:
44		Parser(const std::string &input)
45	1.01k	: input_(input), tb_(0), te_(0), in_variable_(false) {}
46
47	1.01k	bool Parse() {
48	1.01k	if (!ParseTemplate() \|\| !ConsumedAllInput()) {
49	570	return false;
50	570	}
51	442	PostProcessVariables();
52	442	return true;
53	1.01k	}
54
55	364	std::vector<std::string> &segments() { return segments_; }
56	364	std::string &verb() { return verb_; }
57	364	std::vector<HttpTemplate::Variable> &variables() { return variables_; }
58
59		// only constant path segments are allowed after '**'.
60	442	bool ValidateParts() {
61	442	bool found_wild_card = false;
62	1.79M	for (size_t i = 0; i < segments_.size(); i++) {
63	1.79M	if (!found_wild_card) {
64	1.78M	if (segments_[i] == HttpTemplate::kWildCardPathKey) {
65	219	found_wild_card = true;
66	219	}
67	1.78M	} else if (segments_[i] == HttpTemplate::kSingleParameterKey \|\|
68	3.37k	segments_[i] == HttpTemplate::kWildCardPathPartKey \|\|
69	3.37k	segments_[i] == HttpTemplate::kWildCardPathKey) {
70	78	return false;
71	78	}
72	1.79M	}
73	364	return true;
74	442	}
75
76		private:
77		// Template = "/" Segments [ Verb ] ;
78	1.01k	bool ParseTemplate() {
79	1.01k	if (!Consume('/')) {
80		// Expected '/'
81	29	return false;
82	29	}
83	983	if (!ParseSegments()) {
84	407	return false;
85	407	}
86
87	576	if (EnsureCurrent() && current_char() == ':') {
88	66	if (!ParseVerb()) {
89	36	return false;
90	36	}
91	66	}
92	540	return true;
93	576	}
94
95		// Segments = Segment { "/" Segment } ;
96	18.2k	bool ParseSegments() {
97	18.2k	if (!ParseSegment()) {
98	162	return false;
99	162	}
100
101	5.96M	for (;;) {
102	5.96M	if (!Consume('/')) break;
103	5.94M	if (!ParseSegment()) {
104	295	return false;
105	295	}
106	5.94M	}
107
108	17.7k	return true;
109	18.0k	}
110
111		// Segment = "" \| "*" \| LITERAL \| Variable ;
112	5.96M	bool ParseSegment() {
113	5.96M	if (!EnsureCurrent()) {
114	68	return false;
115	68	}
116	5.96M	switch (current_char()) {
117	241k	case '*': {
118	241k	Consume('*');
119	241k	if (Consume('*')) {
120		// **
121	55.3k	segments_.push_back("**");
122	55.3k	if (in_variable_) {
123	9.26k	return MarkVariableHasWildCardPath();
124	9.26k	}
125	46.0k	return true;
126	185k	} else {
127	185k	segments_.push_back("*");
128	185k	return true;
129	185k	}
130	241k	}
131
132	721k	case '{':
133	721k	return ParseVariable();
134	4.99M	default:
135	4.99M	return ParseLiteralSegment();
136	5.96M	}
137	5.96M	}
138
139		// Variable = "{" FieldPath [ "=" Segments ] "}" ;
140	721k	bool ParseVariable() {
141	721k	if (!Consume('{')) {
142	0	return false;
143	0	}
144	721k	if (!StartVariable()) {
145	13	return false;
146	13	}
147	721k	if (!ParseFieldPath()) {
148	95	return false;
149	95	}
150	721k	if (Consume('=')) {
151	17.2k	if (!ParseSegments()) {
152	50	return false;
153	50	}
154	704k	} else {
155		// {field_path} is equivalent to {field_path=*}
156	704k	segments_.push_back("*");
157	704k	}
158	721k	if (!EndVariable()) {
159	0	return false;
160	0	}
161	721k	if (!Consume('}')) {
162	198	return false;
163	198	}
164	721k	return true;
165	721k	}
166
167	4.99M	bool ParseLiteralSegment() {
168	4.99M	std::string ls;
169	4.99M	if (!ParseLiteral(&ls)) {
170	33	return false;
171	33	}
172	4.99M	segments_.push_back(ls);
173	4.99M	return true;
174	4.99M	}
175
176		// FieldPath = IDENT { "." IDENT } ;
177	721k	bool ParseFieldPath() {
178	721k	if (!ParseIdentifier()) {
179	62	return false;
180	62	}
181	1.64M	while (Consume('.')) {
182	924k	if (!ParseIdentifier()) {
183	33	return false;
184	33	}
185	924k	}
186	721k	return true;
187	721k	}
188
189		// Verb = ":" LITERAL ;
190	66	bool ParseVerb() {
191	66	if (!Consume(':')) return false;
192	66	if (!ParseLiteral(&verb_)) return false;
193	30	return true;
194	66	}
195
196	1.64M	bool ParseIdentifier() {
197	1.64M	std::string idf;
198
199		// Initialize to false to handle empty literal.
200	1.64M	bool result = false;
201
202	15.6M	while (NextChar()) {
203	15.6M	char c;
204	15.6M	switch (c = current_char()) {
205	924k	case '.':
206	1.62M	case '}':
207	1.64M	case '=':
208	1.64M	return result && AddFieldIdentifier(std::move(idf));
209	14.0M	default:
210	14.0M	Consume(c);
211	14.0M	idf.push_back(c);
212	14.0M	break;
213	15.6M	}
214	14.0M	result = true;
215	14.0M	}
216	185	return result && AddFieldIdentifier(std::move(idf));
217	1.64M	}
218
219	4.99M	bool ParseLiteral(std::string *lit) {
220	4.99M	if (!EnsureCurrent()) {
221	32	return false;
222	32	}
223
224		// Initialize to false in case we encounter an empty literal.
225	4.99M	bool result = false;
226
227	22.0M	for (;;) {
228	22.0M	char c;
229	22.0M	switch (c = current_char()) {
230	4.98M	case '/':
231	4.98M	case ':':
232	4.99M	case '}':
233	4.99M	return result;
234	17.0M	default:
235	17.0M	Consume(c);
236	17.0M	lit->push_back(c);
237	17.0M	break;
238	22.0M	}
239
240	17.0M	result = true;
241
242	17.0M	if (!NextChar()) {
243	337	break;
244	337	}
245	17.0M	}
246	337	return result;
247	4.99M	}
248
249	41.3M	bool Consume(char c) {
250	41.3M	if (tb_ >= te_ && !NextChar()) {
251	923	return false;
252	923	}
253	41.3M	if (current_char() != c) {
254	1.62M	return false;
255	1.62M	}
256	39.6M	tb_++;
257	39.6M	return true;
258	41.3M	}
259
260	540	bool ConsumedAllInput() { return tb_ >= input_.size(); }
261
262	10.9M	bool EnsureCurrent() { return tb_ < te_ \|\| NextChar(); }
263
264	39.6M	bool NextChar() {
265	39.6M	if (te_ < input_.size()) {
266	39.6M	te_++;
267	39.6M	return true;
268	39.6M	} else {
269	1.96k	return false;
270	1.96k	}
271	39.6M	}
272
273		// Returns the character looked at.
274	84.9M	char current_char() const {
275	84.9M	return tb_ < te_ && te_ <= input_.size() ? input_[te_ - 1] : -1;
276	84.9M	}
277
278	4.54M	HttpTemplate::Variable &CurrentVariable() { return variables_.back(); }
279
280	721k	bool StartVariable() {
281	721k	if (!in_variable_) {
282	721k	variables_.push_back(HttpTemplate::Variable{});
283	721k	CurrentVariable().start_segment = segments_.size();
284	721k	CurrentVariable().has_wildcard_path = false;
285	721k	in_variable_ = true;
286	721k	return true;
287	721k	} else {
288		// nested variables are not allowed
289	13	return false;
290	13	}
291	721k	}
292
293	721k	bool EndVariable() {
294	721k	if (in_variable_ && !variables_.empty()) {
295	721k	CurrentVariable().end_segment = segments_.size();
296	721k	in_variable_ = false;
297	721k	return ValidateVariable(CurrentVariable());
298	721k	} else {
299		// something's wrong we're not in a variable
300	0	return false;
301	0	}
302	721k	}
303
304	1.64M	bool AddFieldIdentifier(std::string id) {
305	1.64M	if (in_variable_ && !variables_.empty()) {
306	1.64M	CurrentVariable().field_path.emplace_back(std::move(id));
307	1.64M	return true;
308	1.64M	} else {
309		// something's wrong we're not in a variable
310	0	return false;
311	0	}
312	1.64M	}
313
314	9.26k	bool MarkVariableHasWildCardPath() {
315	9.26k	if (in_variable_ && !variables_.empty()) {
316	9.26k	CurrentVariable().has_wildcard_path = true;
317	9.26k	return true;
318	9.26k	} else {
319		// something's wrong we're not in a variable
320	0	return false;
321	0	}
322	9.26k	}
323
324	721k	bool ValidateVariable(const HttpTemplate::Variable &var) {
325	721k	return !var.field_path.empty() && (var.start_segment < var.end_segment) &&
326	721k	(var.end_segment <= static_cast<int>(segments_.size()));
327	721k	}
328
329	442	void PostProcessVariables() {
330	439k	for (auto &var : variables_) {
331	439k	if (var.has_wildcard_path) {
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	4.10k	var.end_segment = (var.end_segment - segments_.size() - 1);
338	4.10k	}
339	439k	}
340	442	}
341
342		const std::string &input_;
343
344		// Token delimiter indexes
345		size_t tb_;
346		size_t te_;
347
348		// are we in nested Segments of a variable?
349		bool in_variable_;
350
351		std::vector<std::string> segments_;
352		std::string verb_;
353		std::vector<HttpTemplate::Variable> variables_;
354		};
355
356		} // namespace
357
358		const char HttpTemplate::kSingleParameterKey[] = "/.";
359
360		const char HttpTemplate::kWildCardPathPartKey[] = "*";
361
362		const char HttpTemplate::kWildCardPathKey[] = "**";
363
364	1.01k	std::unique_ptr<HttpTemplate> HttpTemplate::Parse(const std::string &ht) {
365	1.01k	if (ht == "/") {
366	1	return std::unique_ptr<HttpTemplate>(new HttpTemplate({}, {}, {}));
367	1	}
368
369	1.01k	Parser p(ht);
370	1.01k	if (!p.Parse() \|\| !p.ValidateParts()) {
371	648	return nullptr;
372	648	}
373
374	364	return std::unique_ptr<HttpTemplate>(new HttpTemplate(
375	364	std::move(p.segments()), std::move(p.verb()), std::move(p.variables())));
376	1.01k	}
377
378		} // namespace transcoding
379		} // namespace grpc
380		} // namespace google