1/*
2 * Copyright (C) 2012-2016 Apple Inc. All rights reserved.
3 *
4 * Redistribution and use in source and binary forms, with or without
5 * modification, are permitted provided that the following conditions
6 * are met:
7 * 1. Redistributions of source code must retain the above copyright
8 * notice, this list of conditions and the following disclaimer.
9 * 2. Redistributions in binary form must reproduce the above copyright
10 * notice, this list of conditions and the following disclaimer in the
11 * documentation and/or other materials provided with the distribution.
12 *
13 * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
14 * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
15 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
16 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR
17 * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
18 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
19 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
20 * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
21 * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
22 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
23 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
24 */
25
26#pragma once
27
28#include <stdint.h>
29#include <unicode/Unicode.h>
30
31namespace JSC { namespace Yarr {
32
33// This set of data provides information for each UCS2 code point as to the set of code points
34// that it should match under the ES6 case insensitive RegExp matching rules, specified in 21.2.2.8.2.
35// The non-Unicode tables are autogenerated using YarrCanonicalize.js into YarrCanonicalize.cpp.
36// The Unicode tables are autogenerated using the python script generateYarrCanonicalizeUnicode
37// which creates YarrCanonicalizeUnicode.cpp.
38enum UCS2CanonicalizationType {
39 CanonicalizeUnique, // No canonically equal values, e.g. 0x0.
40 CanonicalizeSet, // Value indicates a set in characterSetInfo.
41 CanonicalizeRangeLo, // Value is positive delta to pair, E.g. 0x41 has value 0x20, -> 0x61.
42 CanonicalizeRangeHi, // Value is positive delta to pair, E.g. 0x61 has value 0x20, -> 0x41.
43 CanonicalizeAlternatingAligned, // Aligned consequtive pair, e.g. 0x1f4,0x1f5.
44 CanonicalizeAlternatingUnaligned, // Unaligned consequtive pair, e.g. 0x241,0x242.
45};
46struct CanonicalizationRange {
47 UChar32 begin;
48 UChar32 end;
49 UChar32 value;
50 UCS2CanonicalizationType type;
51};
52
53extern const size_t UCS2_CANONICALIZATION_RANGES;
54extern const UChar32* const ucs2CharacterSetInfo[];
55extern const CanonicalizationRange ucs2RangeInfo[];
56extern const uint16_t canonicalTableLChar[256];
57
58extern const size_t UNICODE_CANONICALIZATION_RANGES;
59extern const UChar32* const unicodeCharacterSetInfo[];
60extern const CanonicalizationRange unicodeRangeInfo[];
61
62enum class CanonicalMode { UCS2, Unicode };
63
64inline const UChar32* canonicalCharacterSetInfo(unsigned index, CanonicalMode canonicalMode)
65{
66 const UChar32* const* rangeInfo = canonicalMode == CanonicalMode::UCS2 ? ucs2CharacterSetInfo : unicodeCharacterSetInfo;
67 return rangeInfo[index];
68}
69
70// This searches in log2 time over ~400-600 entries, so should typically result in 9 compares.
71inline const CanonicalizationRange* canonicalRangeInfoFor(UChar32 ch, CanonicalMode canonicalMode = CanonicalMode::UCS2)
72{
73 const CanonicalizationRange* info = canonicalMode == CanonicalMode::UCS2 ? ucs2RangeInfo : unicodeRangeInfo;
74 size_t entries = canonicalMode == CanonicalMode::UCS2 ? UCS2_CANONICALIZATION_RANGES : UNICODE_CANONICALIZATION_RANGES;
75
76 while (true) {
77 size_t candidate = entries >> 1;
78 const CanonicalizationRange* candidateInfo = info + candidate;
79 if (ch < candidateInfo->begin)
80 entries = candidate;
81 else if (ch <= candidateInfo->end)
82 return candidateInfo;
83 else {
84 info = candidateInfo + 1;
85 entries -= (candidate + 1);
86 }
87 }
88}
89
90// Should only be called for characters that have one canonically matching value.
91inline UChar32 getCanonicalPair(const CanonicalizationRange* info, UChar32 ch)
92{
93 ASSERT(ch >= info->begin && ch <= info->end);
94 switch (info->type) {
95 case CanonicalizeRangeLo:
96 return ch + info->value;
97 case CanonicalizeRangeHi:
98 return ch - info->value;
99 case CanonicalizeAlternatingAligned:
100 return ch ^ 1;
101 case CanonicalizeAlternatingUnaligned:
102 return ((ch - 1) ^ 1) + 1;
103 default:
104 RELEASE_ASSERT_NOT_REACHED();
105 }
106 RELEASE_ASSERT_NOT_REACHED();
107 return 0;
108}
109
110// Returns true if no other UCS2 codepoint can match this value.
111inline bool isCanonicallyUnique(UChar32 ch, CanonicalMode canonicalMode = CanonicalMode::UCS2)
112{
113 return canonicalRangeInfoFor(ch, canonicalMode)->type == CanonicalizeUnique;
114}
115
116// Returns true if values are equal, under the canonicalization rules.
117inline bool areCanonicallyEquivalent(UChar32 a, UChar32 b, CanonicalMode canonicalMode = CanonicalMode::UCS2)
118{
119 const CanonicalizationRange* info = canonicalRangeInfoFor(ch: a, canonicalMode);
120 switch (info->type) {
121 case CanonicalizeUnique:
122 return a == b;
123 case CanonicalizeSet: {
124 for (const UChar32* set = canonicalCharacterSetInfo(index: info->value, canonicalMode); (a = *set); ++set) {
125 if (a == b)
126 return true;
127 }
128 return false;
129 }
130 case CanonicalizeRangeLo:
131 return (a == b) || (a + info->value == b);
132 case CanonicalizeRangeHi:
133 return (a == b) || (a - info->value == b);
134 case CanonicalizeAlternatingAligned:
135 return (a | 1) == (b | 1);
136 case CanonicalizeAlternatingUnaligned:
137 return ((a - 1) | 1) == ((b - 1) | 1);
138 }
139
140 RELEASE_ASSERT_NOT_REACHED();
141 return false;
142}
143
144} } // JSC::Yarr
145

source code of qtdeclarative/src/3rdparty/masm/yarr/YarrCanonicalize.h