Botan 3.14.1
Crypto and TLS for C&
algorithm_spec.cpp
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#include <botan/internal/algorithm_spec.h>
9
10#include <botan/assert.h>
11#include <botan/exceptn.h>
12#include <botan/internal/fmt.h>
13#include <botan/internal/parsing.h>
14
15namespace Botan {
16
17namespace {
18
19constexpr size_t MaxNestingDepth = 16;
20
21bool is_spec_separator(char c, bool slash_separates) {
22 return c == '(' || c == ')' || c == ',' || (slash_separates && c == '/');
23}
24
25} // namespace
26
27//static
28AlgorithmSpec AlgorithmSpec::parse_name(std::string_view text, size_t& pos, size_t depth, bool mode_syntax) {
29 if(depth > MaxNestingDepth) {
30 throw Invalid_Algorithm_Name(text);
31 }
32
33 // The '/' separator is only significant at the top level of a cipher mode
34 const bool slash_separates = mode_syntax && (depth == 0);
35 const size_t start = pos;
36
37 while(pos < text.size() && !is_spec_separator(text[pos], slash_separates)) {
38 ++pos;
39 }
40
41 AlgorithmSpec node;
42 node.m_head = std::string(text.substr(start, pos - start));
43
44 if(node.m_head.empty()) {
45 throw Invalid_Algorithm_Name(text);
46 }
47
48 if(pos < text.size() && text[pos] == '(') {
49 do { // NOLINT(*-avoid-do-while)
50 ++pos; // skip the '(' or ','
51 node.m_args.push_back(parse_name(text, pos, depth + 1, mode_syntax));
52 } while(pos < text.size() && text[pos] == ',');
53
54 if(pos >= text.size() || text[pos] != ')') {
55 throw Invalid_Algorithm_Name(text);
56 }
57 ++pos;
58 }
59
60 node.m_text = std::string(text.substr(start, pos - start));
61 return node;
62}
63
64AlgorithmSpec::AlgorithmSpec(std::string_view spec, Syntax syntax) {
65 if(spec.empty()) {
66 throw Invalid_Algorithm_Name(spec);
67 }
68
69 const bool mode_syntax = (syntax == Syntax::CipherMode);
70
71 // Fast path for a bare name such as "SHA-256", which is the common case
72 if(spec.find_first_of(mode_syntax ? "(),/" : "(),") == std::string_view::npos) {
73 m_text = std::string(spec);
74 m_head = std::string(spec);
75 return;
76 }
77
78 size_t pos = 0;
79 std::vector<AlgorithmSpec> parts;
80 parts.push_back(parse_name(spec, pos, 0, mode_syntax));
81
82 while(mode_syntax && pos < spec.size() && spec[pos] == '/') {
83 ++pos;
84 parts.push_back(parse_name(spec, pos, 0, mode_syntax));
85 }
86
87 if(pos != spec.size()) {
88 throw Invalid_Algorithm_Name(spec);
89 }
90
91 if(parts.size() == 1) {
92 m_head = std::move(parts[0].m_head);
93 m_args = std::move(parts[0].m_args);
94 } else {
95 // Cipher/Mode(args)/Pad becomes Mode(Cipher,args,Pad)
96 AlgorithmSpec& mode = parts[1];
97 m_head = std::move(mode.m_head);
98 m_args.push_back(std::move(parts[0]));
99 for(auto& mode_arg : mode.m_args) {
100 m_args.push_back(std::move(mode_arg));
101 }
102 for(size_t i = 2; i < parts.size(); ++i) {
103 m_args.push_back(std::move(parts[i]));
104 }
105 }
106
107 m_text = std::string(spec);
108}
109
110const AlgorithmSpec& AlgorithmSpec::arg(size_t i) const {
111 if(i >= m_args.size()) {
112 throw Invalid_Argument(fmt("AlgorithmSpec::arg {} out of range for '{}'", i, m_text));
113 }
114 return m_args[i];
115}
116
117std::string AlgorithmSpec::text_with_head(std::string_view head) const {
118 std::string text(head);
119 if(!m_args.empty()) {
120 text += '(';
121 for(size_t i = 0; i != m_args.size(); ++i) {
122 if(i > 0) {
123 text += ',';
124 }
125 text += m_args[i].m_text;
126 }
127 text += ')';
128 }
129 return text;
130}
131
132std::optional<AlgorithmMatch> AlgorithmSpec::match(const AlgorithmPattern& pattern) const& {
133 // Factories try many patterns in turn, so reject on the head before
134 // setting up the (fairly large) match object
135 if(!pattern.any_head()) {
136 bool head_matches = false;
137 for(const auto alt : pattern.head_alternatives()) {
138 if(alt == m_head) {
139 head_matches = true;
140 break;
141 }
142 }
143 if(!head_matches) {
144 return std::nullopt;
145 }
146 }
147
148 AlgorithmMatch m(pattern, *this);
149
150 size_t idx = 0;
151 if(!match_args(pattern.elements(), idx, 0, m)) {
152 return std::nullopt;
153 }
154
155 return m;
156}
157
158bool AlgorithmSpec::match_args(std::span<const AlgorithmPattern::Element> elems,
159 size_t& idx,
160 uint8_t depth,
161 AlgorithmMatch& m) const {
162 using Type = AlgorithmPattern::Type;
163
164 size_t arg_idx = 0;
165
166 while(idx < elems.size() && elems[idx].depth == depth) {
167 const auto& e = elems[idx];
168 ++idx;
169
170 if(arg_idx >= m_args.size()) {
171 // No argument was provided for this element
172 if(!e.optional) {
173 return false;
174 }
175
176 if(e.placeholder && e.has_default) {
177 auto& b = m.declared(e.text);
178 b.bound = true;
179 b.text = e.default_value;
180 if(e.type == Type::Int) {
181 // The pattern parser already checked this is a canonical decimal
182 const auto v = parse_sz(e.default_value, true);
183 BOTAN_ASSERT_NOMSG(v.has_value());
184 b.integer = *v;
185 }
186 }
187
188 continue;
189 }
190
191 const AlgorithmSpec& arg = m_args[arg_idx];
192
193 if(e.variadic) {
194 auto& b = m.declared(e.text);
195 b.bound = true;
196 b.rest = std::span(m_args).subspan(arg_idx);
197 arg_idx = m_args.size();
198 continue;
199 }
200
201 if(e.placeholder) {
202 auto& b = m.declared(e.text);
203
204 if(e.type == Type::Int) {
205 if(!arg.m_args.empty()) {
206 return false;
207 }
208 const auto v = parse_sz(arg.m_text, true);
209 if(!v) {
210 return false;
211 }
212 b.integer = *v;
213 }
214
215 b.bound = true;
216 b.text = arg.m_text;
217 b.node = &arg;
218 } else if(e.optional) {
219 // An optional literal which is not present is skipped without consuming the argument
220 if(arg.m_head != e.text || !arg.m_args.empty()) {
221 continue;
222 }
223 } else {
224 if(arg.m_head != e.text) {
225 return false;
226 }
227
228 if(idx < elems.size() && elems[idx].depth == depth + 1) {
229 if(!arg.match_args(elems, idx, depth + 1, m)) {
230 return false;
231 }
232 } else if(!arg.m_args.empty()) {
233 return false;
234 }
235 }
236
237 ++arg_idx;
238 }
239
240 return arg_idx == m_args.size();
241}
242
243AlgorithmMatch::AlgorithmMatch(const AlgorithmPattern& pattern, const AlgorithmSpec& spec) :
244 m_pattern(pattern.to_string()), m_head(spec.head()) {
245 for(const auto& e : pattern.elements()) {
246 if(e.placeholder) {
247 Binding b;
248 b.var = e.text;
249 b.type = e.type;
250 b.variadic = e.variadic;
251 m_bindings[m_binding_count++] = b;
252 }
253 }
254}
255
256AlgorithmMatch::Binding& AlgorithmMatch::declared(std::string_view var) {
257 for(size_t i = 0; i != m_binding_count; ++i) {
258 if(m_bindings[i].var == var) {
259 return m_bindings[i];
260 }
261 }
262 throw Internal_Error(fmt("AlgorithmMatch: no variable '{}' in pattern '{}'", var, m_pattern));
263}
264
265const AlgorithmMatch::Binding& AlgorithmMatch::bound(std::string_view var, const char* accessor) const {
266 for(size_t i = 0; i != m_binding_count; ++i) {
267 if(m_bindings[i].var == var) {
268 if(!m_bindings[i].bound) {
269 throw Internal_Error(
270 fmt("AlgorithmMatch::{}: variable '{}' in pattern '{}' was not bound; check has() first",
271 accessor,
272 var,
273 m_pattern));
274 }
275 return m_bindings[i];
276 }
277 }
278 throw Internal_Error(fmt("AlgorithmMatch::{}: no variable '{}' in pattern '{}'", accessor, var, m_pattern));
279}
280
281bool AlgorithmMatch::has(std::string_view var) const {
282 for(size_t i = 0; i != m_binding_count; ++i) {
283 if(m_bindings[i].var == var) {
284 return m_bindings[i].bound;
285 }
286 }
287 throw Internal_Error(fmt("AlgorithmMatch::has: no variable '{}' in pattern '{}'", var, m_pattern));
288}
289
290std::string_view AlgorithmMatch::str(std::string_view var) const {
291 const auto& b = bound(var, "str");
292 if(b.variadic) {
293 throw Internal_Error(fmt("AlgorithmMatch::str: variable '{}' in pattern '{}' is variadic", var, m_pattern));
294 }
295 return b.text;
296}
297
298size_t AlgorithmMatch::integer(std::string_view var) const {
299 const auto& b = bound(var, "integer");
300 if(b.type != AlgorithmPattern::Type::Int) {
301 throw Internal_Error(fmt("AlgorithmMatch::integer: variable '{}' in pattern '{}' is not an int", var, m_pattern));
302 }
303 return b.integer;
304}
305
306const AlgorithmSpec& AlgorithmMatch::name(std::string_view var) const {
307 const auto& b = bound(var, "name");
308 if(b.type != AlgorithmPattern::Type::Name || b.variadic || b.node == nullptr) {
309 throw Internal_Error(fmt("AlgorithmMatch::name: variable '{}' in pattern '{}' is not a name", var, m_pattern));
310 }
311 return *b.node;
312}
313
314std::span<const AlgorithmSpec> AlgorithmMatch::rest(std::string_view var) const {
315 const auto& b = bound(var, "rest");
316 if(!b.variadic) {
317 throw Internal_Error(fmt("AlgorithmMatch::rest: variable '{}' in pattern '{}' is not variadic", var, m_pattern));
318 }
319 return b.rest;
320}
321
322} // namespace Botan
#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
bool has(std::string_view var) const
std::string_view str(std::string_view var) const
const AlgorithmSpec & name(std::string_view var) const
const AlgorithmSpec & arg(size_t i) const
std::optional< AlgorithmMatch > match(const AlgorithmPattern &pattern) const &
std::string_view head() const
AlgorithmSpec(std::string_view spec, Syntax syntax=Syntax::Standard)
const char * text
Definition ffi_tls.h:75
std::string fmt(std::string_view format, const T &... args)
Definition fmt.h:53
std::optional< size_t > parse_sz(std::string_view input, bool require_canonical)
Definition parsing.cpp:71
std::string to_string(ErrorType type)
Convert an ErrorType to string.
Definition exceptn.cpp:13