Ada 4.1.1
Fast spec-compliant URL parser
Loading...
Searching...
No Matches
validity.cpp
Go to the documentation of this file.
1#include "table_store.hpp"
2
3#include <algorithm>
4#include <span>
5#include <string_view>
6
7namespace ada::idna {
8
9// Values stored in dir_value; keep in sync with BIDI_CLASSES in
10// scripts/unicode_data_table.py.
11enum direction : uint8_t {
12 NONE,
13 BN,
14 CS,
15 ES,
16 ON,
17 EN,
18 L,
19 R,
20 NSM,
21 AL,
22 AN,
23 ET,
24 WS,
25 RLO,
26 LRO,
27 PDF,
28 RLE,
29 RLI,
30 FSI,
31 PDI,
32 LRI,
33 B,
34 S,
35 LRE
36};
37
38// Values stored in joining_value; keep in sync with JOINING_TYPES in
39// scripts/unicode_data_table.py. Code points without a range are U.
40enum class joining_type : uint8_t { U, C, D, L, R, T };
41
42// Bidi direction and Joining_Type ranges live in the compressed blob as const
43// SoA arrays (dir_* and joining_*). See table_store.hpp layout asserts.
44// Regenerate with: python3 scripts/unicode_data_table.py --write
45
46// Defined in normalization.cpp.
47uint8_t get_ccc(char32_t c) noexcept;
48
49// CheckJoiners and CheckBidi are true for URL specification.
50
51// Returns the index of the range [start[i], last[i]] that contains code_point,
52// or count if there is none. `last` must be sorted.
53inline static size_t find_range(const uint32_t* start, const uint32_t* last,
54 size_t count, uint32_t code_point) noexcept {
55 size_t lo = 0, hi = count;
56 while (lo < hi) {
57 size_t mid = lo + (hi - lo) / 2;
58 if (last[mid] < code_point) {
59 lo = mid + 1;
60 } else {
61 hi = mid;
62 }
63 }
64 return lo < count && code_point >= start[lo] ? lo : count;
65}
66
67// Assumes ensure_tables() has already been called by is_label_valid().
68inline static direction find_direction(uint32_t code_point) noexcept {
69 size_t i = find_range(dir_start, dir_final, dir_table_count, code_point);
70 return i == dir_table_count ? direction::NONE
71 : static_cast<direction>(dir_value[i]);
72}
73
74// Assumes ensure_tables() has already been called by is_label_valid().
75inline static joining_type find_joining_type(uint32_t code_point) noexcept {
76 size_t i =
79 : static_cast<joining_type>(joining_value[i]);
80}
81
82// The ContextJ rules for U+200C and U+200D from RFC 5892 Appendix A.
83inline static bool is_contextj_valid(std::u32string_view label) noexcept {
84 constexpr uint8_t virama_ccc = 9;
85 for (size_t i = 0; i < label.size(); i++) {
86 if (label[i] != 0x200C && label[i] != 0x200D) {
87 continue;
88 }
89 // If Canonical_Combining_Class(Before(cp)) .eq. Virama Then True;
90 if (i > 0 && get_ccc(label[i - 1]) == virama_ccc) {
91 continue;
92 }
93 if (label[i] == 0x200D) {
94 return false;
95 }
96 // If RegExpMatch((Joining_Type:{L,D})(Joining_Type:T)*\u200C
97 // (Joining_Type:T)*(Joining_Type:{R,D})) Then True;
99 for (size_t j = i; j > 0;) {
100 before = find_joining_type(label[--j]);
101 if (before != joining_type::T) {
102 break;
103 }
104 }
105 if (before != joining_type::L && before != joining_type::D) {
106 return false;
107 }
109 for (size_t j = i + 1; j < label.size(); j++) {
110 after = find_joining_type(label[j]);
111 if (after != joining_type::T) {
112 break;
113 }
114 }
115 if (after != joining_type::R && after != joining_type::D) {
116 return false;
117 }
118 }
119 return true;
120}
121
122inline static size_t find_last_not_of_nsm(
123 const std::u32string_view label) noexcept {
124 for (int i = static_cast<int>(label.size() - 1); i >= 0; i--)
125 if (find_direction(label[i]) != direction::NSM) return i;
126
127 return std::u32string_view::npos;
128}
129
130// An RTL label is a label that contains at least one character of type R, AL,
131// or AN. A domain containing one is a Bidi domain name: RFC 5893 then applies
132// to every label, including labels that are themselves all LTR.
133// https://www.rfc-editor.org/rfc/rfc5893#section-2
134inline static bool is_rtl_label(const std::u32string_view label) noexcept {
135 const size_t mask =
136 (1u << direction::R) | (1u << direction::AL) | (1u << direction::AN);
137
138 size_t directions = 0;
139 for (size_t i = 0; i < label.size(); i++) {
140 directions |= 1u << find_direction(label[i]);
141 }
142 return (directions & mask) != 0;
143}
144
145// Same as is_rtl_label, but loads the Bidi tables first. Visible to to_ascii
146// and to_unicode, which are part of this translation unit.
147inline static bool label_contains_rtl(std::u32string_view label) noexcept {
148 if (label.empty() || !ensure_tables() || dir_start == nullptr ||
149 dir_final == nullptr || dir_value == nullptr) {
150 return false;
151 }
152 return is_rtl_label(label);
153}
154
155// `bidi_domain` is true when the domain name contains at least one RTL label.
156// CheckBidi then applies to this label even if the label itself has no R, AL,
157// or AN character (RFC 5893). The one-argument is_label_valid() passes false,
158// which preserves the per-label check for callers that do not know yet.
159static bool check_label(const std::u32string_view label, bool bidi_domain) {
160 if (label.empty()) {
161 return true;
162 }
163 if (!ensure_tables() || combining_ranges == nullptr || dir_start == nullptr ||
164 dir_final == nullptr || dir_value == nullptr ||
165 joining_start == nullptr || joining_final == nullptr ||
166 joining_value == nullptr) {
167 return false;
168 }
169
171 // We have a normalization step which ensures that we are in NFC.
172 // If we receive punycode, we normalize and check that the normalized
173 // version matches the original.
174 // --------------------------------------
175 // The label must be in Unicode Normalization Form NFC.
176
177 // Current URL standard indicatest that CheckHyphens is set to false.
178 // ---------------------------------------
179 // If CheckHyphens, the label must not contain a U+002D HYPHEN-MINUS character
180 // in both the third and fourth positions. If CheckHyphens, the label must
181 // neither begin nor end with a U+002D HYPHEN-MINUS character.
182
183 // This is not necessary because we segment the
184 // labels by '.'.
185 // ---------------------------------------
186 // The label must not contain a U+002E ( . ) FULL STOP.
187 // if (label.find('.') != std::string_view::npos) return false;
188
189 // The label must not begin with a combining mark.
190 // Range membership via lower_bound on range end.
191 const std::span<const uint32_t[2]> comb_span{combining_ranges,
193 const auto comb_it = std::ranges::lower_bound(
194 comb_span, label.front(), {}, [](const auto& range) { return range[1]; });
195 if (comb_it != comb_span.end() && label.front() >= (*comb_it)[0]) {
196 return false;
197 }
198 // We verify this next step as part of the mapping:
199 // ---------------------------------------------
200 // Each code point in the label must only have certain status values
201 // according to Section 5, IDNA Mapping Table:
202 // - For Transitional Processing, each value must be valid.
203 // - For Nontransitional Processing, each value must be either valid or
204 // deviation.
205
206 // If CheckJoiners, the label must satisfy the ContextJ rules from Appendix
207 // A, in The Unicode Code Points and Internationalized Domain Names for
208 // Applications (IDNA) [IDNA2008].
209 if (!is_contextj_valid(label)) {
210 return false;
211 }
212
213 // If CheckBidi, and if the domain name is a Bidi domain name, then the label
214 // must satisfy all six of the numbered conditions in [IDNA2008] RFC 5893,
215 // Section 2.
216
217 // The following rule, consisting of six conditions, applies to labels
218 // in Bidi domain names. The requirements that this rule satisfies are
219 // described in Section 3. All of the conditions must be satisfied for
220 // the rule to be satisfied.
221 //
222 // 1. The first character must be a character with Bidi property L, R,
223 // or AL. If it has the R or AL property, it is an RTL label; if it
224 // has the L property, it is an LTR label.
225 //
226 // 2. In an RTL label, only characters with the Bidi properties R, AL,
227 // AN, EN, ES, CS, ET, ON, BN, or NSM are allowed.
228 //
229 // 3. In an RTL label, the end of the label must be a character with
230 // Bidi property R, AL, EN, or AN, followed by zero or more
231 // characters with Bidi property NSM.
232 //
233 // 4. In an RTL label, if an EN is present, no AN may be present, and
234 // vice versa.
235 //
236 // 5. In an LTR label, only characters with the Bidi properties L, EN,
237 // ES, CS, ET, ON, BN, or NSM are allowed.
238 //
239 // 6. In an LTR label, the end of the label must be a character with
240 // Bidi property L or EN, followed by zero or more characters with
241 // Bidi property NSM.
242
243 size_t last_non_nsm_char = find_last_not_of_nsm(label);
244 if (last_non_nsm_char == std::u32string_view::npos) {
245 return false;
246 }
247
248 // A "Bidi domain name" is a domain name that contains at least one RTL label.
249 // The following rule, consisting of six conditions, applies to labels in Bidi
250 // domain names: every label, not only the RTL ones.
251 if (bidi_domain || is_rtl_label(label)) {
252 // The first character must be a character with Bidi property L, R,
253 // or AL. If it has the R or AL property, it is an RTL label; if it
254 // has the L property, it is an LTR label.
255
256 if (find_direction(label[0]) == direction::L) {
257 // Eval as LTR
258
259 // In an LTR label, only characters with the Bidi properties L, EN,
260 // ES, CS, ET, ON, BN, or NSM are allowed.
261 for (size_t i = 0; i <= last_non_nsm_char; i++) {
262 const direction d = find_direction(label[i]);
263 if (!(d == direction::L || d == direction::EN || d == direction::ES ||
264 d == direction::CS || d == direction::ET || d == direction::ON ||
265 d == direction::BN || d == direction::NSM)) {
266 return false;
267 }
268 }
269
270 const direction last_dir = find_direction(label[last_non_nsm_char]);
271 if (!(last_dir == direction::L || last_dir == direction::EN)) {
272 return false;
273 }
274
275 return true;
276
277 } else {
278 // Eval as RTL
279
280 // The first character must be R or AL; a leading AN (or any other
281 // direction) does not start a valid RTL label.
282 const direction first_dir = find_direction(label[0]);
283 if (first_dir != direction::R && first_dir != direction::AL) {
284 return false;
285 }
286
287 bool has_an = false;
288 bool has_en = false;
289 for (size_t i = 0; i <= last_non_nsm_char; i++) {
290 const direction d = find_direction(label[i]);
291
292 // In an RTL label, if an EN is present, no AN may be present, and vice
293 // versa.
294 if ((d == direction::EN && ((has_en = true) && has_an)) ||
295 (d == direction::AN && ((has_an = true) && has_en))) {
296 return false;
297 }
298
299 if (!(d == direction::R || d == direction::AL || d == direction::AN ||
300 d == direction::EN || d == direction::ES || d == direction::CS ||
301 d == direction::ET || d == direction::ON || d == direction::BN ||
302 d == direction::NSM)) {
303 return false;
304 }
305
306 if (i == last_non_nsm_char &&
307 !(d == direction::R || d == direction::AL || d == direction::AN ||
308 d == direction::EN)) {
309 return false;
310 }
311 }
312
313 return true;
314 }
315 }
316
317 return true;
318}
319
320bool is_label_valid(const std::u32string_view label) {
321 return check_label(label, false);
322}
323
324} // namespace ada::idna
static bool is_rtl_label(const std::u32string_view label) noexcept
const uint8_t * dir_value
const uint32_t * joining_final
static size_t find_range(const uint32_t *start, const uint32_t *last, size_t count, uint32_t code_point) noexcept
static bool check_label(const std::u32string_view label, bool bidi_domain)
const uint8_t * joining_value
const uint32_t * joining_start
static joining_type find_joining_type(uint32_t code_point) noexcept
constexpr size_t combining_range_count
static direction find_direction(uint32_t code_point) noexcept
range_pair_ptr combining_ranges
constexpr size_t joining_table_count
uint8_t get_ccc(char32_t c) noexcept
bool ensure_tables() noexcept
static size_t find_last_not_of_nsm(const std::u32string_view label) noexcept
constexpr size_t dir_table_count
const uint32_t * dir_final
bool is_label_valid(std::u32string_view label)
const uint32_t * dir_start
static bool is_contextj_valid(std::u32string_view label) noexcept
static bool label_contains_rtl(std::u32string_view label) noexcept