Botan 3.14.1
Crypto and TLS for C&
algorithm_spec.h
Go to the documentation of this file.
1/*
2* Algorithm Specification Parsing and Matching
3* (C) 2008,2015,2026 Jack Lloyd
4*
5* Botan is released under the Simplified BSD License (see license.txt)
6*/
7
8#ifndef BOTAN_ALGORITHM_SPEC_H_
9#define BOTAN_ALGORITHM_SPEC_H_
10
11#include <botan/assert.h>
12#include <botan/types.h>
13#include <array>
14#include <optional>
15#include <span>
16#include <string>
17#include <string_view>
18#include <vector>
19
20namespace Botan {
21
22class AlgorithmSpec;
23class AlgorithmMatch;
24
25/**
26* A compile-time validated pattern describing the accepted form of an algorithm
27* specification. See AlgorithmSpec::match for how patterns are used.
28*
29* Pattern grammar:
30*
31* pattern := head [ '(' element (',' element)* ')' ]
32* head := token ('|' token)* alternatives (aliases)
33* | '*' any head
34* element := placeholder [ '...' ] '...' = one or more, must be last
35* | literal a token which must appear
36* | '[' literal ']' an optional literal, skipped if absent
37* | token '(' element (',' element)* ')' a literal with nested elements
38* placeholder := '{' ident [':' type] ['=' default | '?'] '}'
39* type := name | int | str default is name
40*
41* A placeholder with a default ('=') or marked '?' is optional. Once an optional
42* element appears, every following element must also be optional. Defaults are
43* only permitted for int and str placeholders. An int must be a canonical
44* decimal integer with no arguments; a str binds the text of the argument
45* verbatim, including any nested arguments; a name binds the argument as a
46* specification for passing on to another factory.
47*
48* A '*' head matches any name, with AlgorithmMatch::head reporting which one.
49* This is for provider wrappers which immediately look the head up in a table
50* of supported algorithms; a factory pattern should always name its heads.
51*
52* Patterns are only constructible from string literals, so a pattern and any
53* match made from it may reference the pattern text indefinitely.
54*/
56 public:
57 static constexpr size_t MaxElements = 4;
58 // TODO(Botan4) reduce this when deprecated aliases are dropped
59 static constexpr size_t MaxHeadAlternatives = 4;
60
61 // This is actually only "thrown" at compile time which is why it
62 // does not derive from a standard Botan exception base
63 class InvalidAlgorithmPattern final : public std::exception {
64 public:
65 explicit InvalidAlgorithmPattern(const char* msg) : m_msg(msg) {}
66
67 const char* what() const noexcept final { return m_msg; }
68
69 private:
70 const char* m_msg;
71 };
72
73 enum class Type : uint8_t {
74 Name,
75 Int,
76 Str,
77 };
78
79 struct Element {
80 std::string_view text; // literal token, or placeholder variable name
81 std::string_view default_value;
83 uint8_t depth = 0;
84 bool placeholder = false;
85 bool optional = false;
86 bool has_default = false;
87 bool variadic = false;
88 };
89
90 /**
91 * Construct a pattern from a string literal. The pattern is parsed and
92 * validated at compile time; a malformed pattern is a compile error.
93 */
94 template <size_t N>
95 consteval AlgorithmPattern(const char (&pattern)[N]) : // NOLINT(*-explicit-conversions,*-explicit-constructor)
96 AlgorithmPattern(std::string_view(pattern, N - 1)) {}
97
98 std::string_view to_string() const { return m_text; }
99
100 /**
101 * @return true if the pattern accepts any head
102 */
103 bool any_head() const { return m_head_count == 0; }
104
105 std::span<const std::string_view> head_alternatives() const { return std::span(m_heads).first(m_head_count); }
106
107 std::span<const Element> elements() const { return std::span(m_elements).first(m_element_count); }
108
109 private:
110 explicit constexpr AlgorithmPattern(std::string_view pattern);
111
112 constexpr void parse_pattern(std::string_view p);
113 constexpr void parse_elements(std::string_view p, size_t& pos, uint8_t depth);
114 constexpr void parse_placeholder(std::string_view p, size_t& pos, Element& e) const;
115
116 static constexpr bool is_token_char(char c) {
117 return c != '(' && c != ')' && c != '{' && c != '}' && c != '[' && c != ']' && c != ',' && c != '|' &&
118 c != '*';
119 }
120
121 template <typename Pred>
122 static constexpr std::string_view read_while(std::string_view p, size_t& pos, Pred pred) {
123 const size_t start = pos;
124 while(pos < p.size() && pred(p[pos])) {
125 ++pos;
126 }
127 return p.substr(start, pos - start);
128 }
129
130 std::string_view m_text;
131 std::array<std::string_view, MaxHeadAlternatives> m_heads{};
132 // A '*' head is encoded as an empty list (boolean hits a Clang 14 codegen bug)
133 size_t m_head_count = 0;
134 std::array<Element, MaxElements> m_elements{};
135 size_t m_element_count = 0;
136};
137
138/**
139* A parsed algorithm specification such as "HMAC(SHA-256)" or "AES-128/GCM(12)"
140*
141* Specifications have the form Head(arg,arg,...) where each argument is itself
142* a specification. With Syntax::CipherMode the form "Cipher/Mode(args)/Pad" is
143* also accepted at the top level and canonicalized to "Mode(Cipher,args,Pad)";
144* otherwise a slash is an ordinary character.
145*
146* Factories should match against an AlgorithmPattern, which expresses the
147* entire accepted form including defaults, rather than inspecting arguments
148* positionally.
149*/
151 public:
152 enum class Syntax : uint8_t {
154 CipherMode,
155 };
156
157 /**
158 * Parse a specification
159 * @throws Invalid_Algorithm_Name if the string is malformed
160 */
161 explicit AlgorithmSpec(std::string_view spec, Syntax syntax = Syntax::Standard);
162
163 /**
164 * @return the original text of the specification
165 */
166 std::string_view to_string() const { return m_text; }
167
168 /**
169 * @return the outermost algorithm name, eg "GCM" for "AES-128/GCM"
170 */
171 std::string_view head() const { return m_head; }
172
173 size_t arg_count() const { return m_args.size(); }
174
175 std::span<const AlgorithmSpec> args() const { return m_args; }
176
177 /**
178 * @return the ith argument
179 * @throws Invalid_Argument if i is out of range
180 */
181 const AlgorithmSpec& arg(size_t i) const;
182
183 /**
184 * @return the specification written as Head(arg,arg,...), which differs
185 * from to_string only for the cipher mode syntax
186 */
187 std::string canonical_form() const { return text_with_head(m_head); }
188
189 /**
190 * @return a copy of this specification with the head replaced, for
191 * folding deprecated aliases before matching
192 */
193 AlgorithmSpec with_head(std::string_view head) const { return AlgorithmSpec(text_with_head(head)); }
194
195 /**
196 * Match this specification against a pattern
197 *
198 * @return the bound variables, or nullopt if the pattern does not match.
199 * The result references this object and must not outlive it.
200 */
201 std::optional<AlgorithmMatch> match(const AlgorithmPattern& pattern) const&;
202
203 // The match refers into this spec, so it cannot outlive a temporary
204 std::optional<AlgorithmMatch> match(const AlgorithmPattern& pattern) const&& = delete;
205
206 /**
207 * @return true if this specification matches the pattern
208 */
209 bool matches(const AlgorithmPattern& pattern) const;
210
211 private:
212 AlgorithmSpec() = default;
213
214 static AlgorithmSpec parse_name(std::string_view text, size_t& pos, size_t depth, bool mode_syntax);
215
216 std::string text_with_head(std::string_view head) const;
217
218 bool match_args(std::span<const AlgorithmPattern::Element> elems,
219 size_t& idx,
220 uint8_t depth,
221 AlgorithmMatch& m) const;
222
223 std::string m_text;
224 std::string m_head;
225 std::vector<AlgorithmSpec> m_args;
226};
227
228/**
229* The variables bound by a successful AlgorithmSpec::match
230*
231* Requesting a variable which the pattern does not declare, or with an accessor
232* that does not fit its type, is a programmer error and throws Internal_Error.
233*/
234class BOTAN_TEST_API AlgorithmMatch final {
235 public:
236 /**
237 * @return the head of the matched specification, which is useful when the
238 * pattern lists several alternatives
239 */
240 std::string_view head() const { return m_head; }
241
242 /**
243 * @return true if the variable was bound, either from the input or a default
244 */
245 bool has(std::string_view var) const;
246
247 /**
248 * @return the text bound to a variable of any type
249 */
250 std::string_view str(std::string_view var) const;
251
252 /**
253 * @return the value bound to an int variable
254 */
255 size_t integer(std::string_view var) const;
256
257 /**
258 * @return the specification bound to a name variable
259 */
260 const AlgorithmSpec& name(std::string_view var) const;
261
262 /**
263 * @return the specifications bound to a variadic variable
264 */
265 std::span<const AlgorithmSpec> rest(std::string_view var) const;
266
267 private:
268 friend class AlgorithmSpec;
269
270 struct Binding {
271 std::string_view var;
273 bool variadic = false;
274 bool bound = false;
275 std::string_view text;
276 size_t integer = 0;
277 const AlgorithmSpec* node = nullptr;
278 std::span<const AlgorithmSpec> rest;
279 };
280
281 AlgorithmMatch(const AlgorithmPattern& pattern, const AlgorithmSpec& spec);
282
283 Binding& declared(std::string_view var);
284 const Binding& bound(std::string_view var, const char* accessor) const;
285
286 std::string_view m_pattern;
287 std::string_view m_head;
288 std::array<Binding, AlgorithmPattern::MaxElements> m_bindings{};
289 size_t m_binding_count = 0;
290};
291
292inline bool AlgorithmSpec::matches(const AlgorithmPattern& pattern) const {
293 return match(pattern).has_value();
294}
295
296// Implementation of the compile time pattern parser follows
297
298constexpr AlgorithmPattern::AlgorithmPattern(std::string_view pattern) : m_text(pattern) {
299 parse_pattern(pattern);
300}
301
302constexpr void AlgorithmPattern::parse_placeholder(std::string_view p, size_t& pos, Element& e) const {
303 const auto is_ident_char = [](char c) {
304 return (c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z') || (c >= '0' && c <= '9') || c == '_';
305 };
306
307 const auto is_canonical_decimal = [](std::string_view s) {
308 // Upper bound is arbitrary but sufficient
309 if(s.empty() || s.size() > 10) {
310 return false;
311 }
312 // Don't accept leading 0s except for literal "0"
313 if(s.size() > 1 && s[0] == '0') {
314 return false;
315 }
316 for(const char c : s) {
317 if(c < '0' || c > '9') {
318 return false;
319 }
320 }
321 return true;
322 };
323
324 BOTAN_ASSERT_NOMSG(pos < p.size() && p[pos] == '{');
325 ++pos;
326
327 e.placeholder = true;
328 e.text = read_while(p, pos, is_ident_char);
329 if(e.text.empty()) {
330 throw InvalidAlgorithmPattern("AlgorithmPattern: placeholder without a name");
331 }
332
333 if(pos < p.size() && p[pos] == ':') {
334 ++pos;
335 const auto type = read_while(p, pos, is_ident_char);
336 if(type == "name") {
337 e.type = Type::Name;
338 } else if(type == "int") {
339 e.type = Type::Int;
340 } else if(type == "str") {
341 e.type = Type::Str;
342 } else {
343 throw InvalidAlgorithmPattern("AlgorithmPattern: unknown placeholder type");
344 }
345 }
346
347 if(pos < p.size() && p[pos] == '=') {
348 ++pos;
349 const size_t start = pos;
350 while(pos < p.size() && p[pos] != '}') {
351 ++pos;
352 }
353 e.default_value = p.substr(start, pos - start);
354 e.optional = true;
355 e.has_default = true;
356
357 if(e.type == Type::Name) {
358 throw InvalidAlgorithmPattern("AlgorithmPattern: only int and str placeholders can have a default");
359 }
360 if(e.type == Type::Int && !is_canonical_decimal(e.default_value)) {
361 throw InvalidAlgorithmPattern("AlgorithmPattern: int default is not a canonical decimal integer");
362 }
363 } else if(pos < p.size() && p[pos] == '?') {
364 ++pos;
365 e.optional = true;
366 }
367
368 if(pos >= p.size() || p[pos] != '}') {
369 throw InvalidAlgorithmPattern("AlgorithmPattern: expected '}'");
370 }
371 ++pos;
372}
373
374constexpr void AlgorithmPattern::parse_elements(std::string_view p, size_t& pos, uint8_t depth) {
375 // pos is just past the '('
376 bool seen_optional = false;
377 bool seen_variadic = false;
378
379 for(;;) {
380 if(pos >= p.size()) {
381 throw InvalidAlgorithmPattern("AlgorithmPattern: unterminated element list");
382 }
383 if(seen_variadic) {
384 throw InvalidAlgorithmPattern("AlgorithmPattern: variadic placeholder must be the last element");
385 }
386 if(m_element_count == MaxElements) {
387 throw InvalidAlgorithmPattern("AlgorithmPattern: too many elements");
388 }
389
390 Element e;
391 e.depth = depth;
392 bool pushed = false;
393
394 if(p[pos] == '{') {
395 parse_placeholder(p, pos, e);
396 if(p.substr(pos, 3) == "...") {
397 pos += 3;
398 if(e.optional) {
399 throw InvalidAlgorithmPattern("AlgorithmPattern: variadic placeholder cannot be optional");
400 }
401 if(e.type != Type::Name) {
402 throw InvalidAlgorithmPattern("AlgorithmPattern: variadic placeholder must have type name");
403 }
404 e.variadic = true;
405 seen_variadic = true;
406 }
407 } else if(p[pos] == '[') {
408 ++pos;
409 e.text = read_while(p, pos, is_token_char);
410 if(e.text.empty()) {
411 throw InvalidAlgorithmPattern("AlgorithmPattern: empty optional literal");
412 }
413 if(pos >= p.size() || p[pos] != ']') {
414 throw InvalidAlgorithmPattern("AlgorithmPattern: expected ']'");
415 }
416 ++pos;
417 e.optional = true;
418 } else {
419 e.text = read_while(p, pos, is_token_char);
420 if(e.text.empty()) {
421 throw InvalidAlgorithmPattern("AlgorithmPattern: empty element");
422 }
423 if(pos < p.size() && p[pos] == '(') {
424 if(seen_optional) {
425 throw InvalidAlgorithmPattern("AlgorithmPattern: required element after optional element");
426 }
427 if(static_cast<size_t>(depth) + 1 >= MaxElements) {
428 throw InvalidAlgorithmPattern("AlgorithmPattern: nesting too deep");
429 }
430 m_elements[m_element_count++] = e;
431 pushed = true;
432 ++pos;
433 parse_elements(p, pos, static_cast<uint8_t>(depth + 1));
434 }
435 }
436
437 if(e.optional) {
438 seen_optional = true;
439 } else if(seen_optional) {
440 throw InvalidAlgorithmPattern("AlgorithmPattern: required element after optional element");
441 }
442
443 if(!pushed) {
444 m_elements[m_element_count++] = e;
445 }
446
447 if(pos >= p.size()) {
448 throw InvalidAlgorithmPattern("AlgorithmPattern: unterminated element list");
449 }
450 if(p[pos] == ',') {
451 ++pos;
452 continue;
453 }
454 if(p[pos] == ')') {
455 ++pos;
456 return; // done
457 }
458 throw InvalidAlgorithmPattern("AlgorithmPattern: unexpected character in element list");
459 }
460}
461
462constexpr void AlgorithmPattern::parse_pattern(std::string_view p) {
463 size_t pos = 0;
464
465 if(p.empty()) {
466 throw InvalidAlgorithmPattern("AlgorithmPattern: empty pattern");
467 }
468
469 if(p[pos] == '*') {
470 ++pos;
471 if(pos < p.size() && p[pos] == '|') {
472 throw InvalidAlgorithmPattern("AlgorithmPattern: wildcard head cannot have alternatives");
473 }
474 } else {
475 for(;;) {
476 if(m_head_count == MaxHeadAlternatives) {
477 throw InvalidAlgorithmPattern("AlgorithmPattern: too many head alternatives");
478 }
479 const auto tok = read_while(p, pos, is_token_char);
480 if(tok.empty()) {
481 throw InvalidAlgorithmPattern("AlgorithmPattern: empty head");
482 }
483 m_heads[m_head_count++] = tok;
484 if(pos < p.size() && p[pos] == '|') {
485 ++pos;
486 continue;
487 }
488 break;
489 }
490 }
491
492 if(pos < p.size()) {
493 if(p[pos] != '(') {
494 throw InvalidAlgorithmPattern("AlgorithmPattern: unexpected character after head");
495 }
496 ++pos;
497 parse_elements(p, pos, 0);
498 if(pos != p.size()) {
499 throw InvalidAlgorithmPattern("AlgorithmPattern: trailing characters");
500 }
501 }
502
503 // Variable names must be unique
504 for(size_t i = 0; i != m_element_count; ++i) {
505 if(!m_elements[i].placeholder) {
506 continue;
507 }
508 for(size_t j = 0; j != i; ++j) {
509 if(m_elements[j].placeholder && m_elements[j].text == m_elements[i].text) {
510 throw InvalidAlgorithmPattern("AlgorithmPattern: duplicate variable name");
511 }
512 }
513 }
514
515 // accept
516}
517
518} // namespace Botan
519
520#endif
#define BOTAN_TEST_API
Definition api.h:41
#define BOTAN_ASSERT_NOMSG(expr)
Definition assert.h:82
std::span< const AlgorithmSpec > rest(std::string_view var) const
size_t integer(std::string_view var) const
std::string_view head() const
const char * what() const noexcept final
std::string_view to_string() const
std::span< const Element > elements() const
consteval AlgorithmPattern(const char(&pattern)[N])
static constexpr size_t MaxElements
static constexpr size_t MaxHeadAlternatives
std::span< const std::string_view > head_alternatives() const
std::span< const AlgorithmSpec > args() const
std::string canonical_form() const
std::optional< AlgorithmMatch > match(const AlgorithmPattern &pattern) const &&=delete
AlgorithmSpec with_head(std::string_view head) const
bool matches(const AlgorithmPattern &pattern) const
std::string_view to_string() const
std::optional< AlgorithmMatch > match(const AlgorithmPattern &pattern) const &
std::string_view head() const
AlgorithmSpec(std::string_view spec, Syntax syntax=Syntax::Standard)
size_t arg_count() const
const char * text
Definition ffi_tls.h:75
const char * name
Definition ffi_tls.h:59