1/*
2 * Copyright (C) 2012 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#ifndef YarrCanonicalizeUCS2_H
27#define YarrCanonicalizeUCS2_H
28
29#include <stdint.h>
30#include <unicode/utypes.h>
31
32namespace JSC { namespace Yarr {
33
34// This set of data (autogenerated using YarrCanonicalizeUCS2.js into YarrCanonicalizeUCS2.cpp)
35// provides information for each UCS2 code point as to the set of code points that it should
36// match under the ES5.1 case insensitive RegExp matching rules, specified in 15.10.2.8.
37enum UCS2CanonicalizationType {
38    CanonicalizeUnique,               // No canonically equal values, e.g. 0x0.
39    CanonicalizeSet,                  // Value indicates a set in characterSetInfo.
40    CanonicalizeRangeLo,              // Value is positive delta to pair, E.g. 0x41 has value 0x20, -> 0x61.
41    CanonicalizeRangeHi,              // Value is positive delta to pair, E.g. 0x61 has value 0x20, -> 0x41.
42    CanonicalizeAlternatingAligned,   // Aligned consequtive pair, e.g. 0x1f4,0x1f5.
43    CanonicalizeAlternatingUnaligned, // Unaligned consequtive pair, e.g. 0x241,0x242.
44};
45struct UCS2CanonicalizationRange { uint16_t begin, end, value, type; };
46extern const size_t UCS2_CANONICALIZATION_RANGES;
47extern const uint16_t* characterSetInfo[];
48extern const UCS2CanonicalizationRange rangeInfo[];
49
50// This table is similar to the full rangeInfo table, however this maps from UCS2 codepoints to
51// the set of Latin1 codepoints that could match.
52enum LatinCanonicalizationType {
53    CanonicalizeLatinSelf,     // This character is in the Latin1 range, but has no canonical equivalent in the range.
54    CanonicalizeLatinMask0x20, // One of a pair of characters, under the mask 0x20.
55    CanonicalizeLatinOther,    // This character is not in the Latin1 range, but canonicalizes to another that is.
56    CanonicalizeLatinInvalid,  // Cannot match against Latin1 input.
57};
58struct LatinCanonicalizationRange { uint16_t begin, end, value, type; };
59extern const size_t LATIN_CANONICALIZATION_RANGES;
60extern LatinCanonicalizationRange latinRangeInfo[];
61
62// This searches in log2 time over ~364 entries, so should typically result in 8 compares.
63inline const UCS2CanonicalizationRange* rangeInfoFor(UChar ch)
64{
65    const UCS2CanonicalizationRange* info = rangeInfo;
66    size_t entries = UCS2_CANONICALIZATION_RANGES;
67
68    while (true) {
69        size_t candidate = entries >> 1;
70        const UCS2CanonicalizationRange* candidateInfo = info + candidate;
71        if (ch < candidateInfo->begin)
72            entries = candidate;
73        else if (ch <= candidateInfo->end)
74            return candidateInfo;
75        else {
76            info = candidateInfo + 1;
77            entries -= (candidate + 1);
78        }
79    }
80}
81
82// Should only be called for characters that have one canonically matching value.
83inline UChar getCanonicalPair(const UCS2CanonicalizationRange* info, UChar ch)
84{
85    ASSERT(ch >= info->begin && ch <= info->end);
86    switch (info->type) {
87    case CanonicalizeRangeLo:
88        return ch + info->value;
89    case CanonicalizeRangeHi:
90        return ch - info->value;
91    case CanonicalizeAlternatingAligned:
92        return ch ^ 1;
93    case CanonicalizeAlternatingUnaligned:
94        return ((ch - 1) ^ 1) + 1;
95    default:
96        RELEASE_ASSERT_NOT_REACHED();
97    }
98    RELEASE_ASSERT_NOT_REACHED();
99    return 0;
100}
101
102// Returns true if no other UCS2 codepoint can match this value.
103inline bool isCanonicallyUnique(UChar ch)
104{
105    return rangeInfoFor(ch)->type == CanonicalizeUnique;
106}
107
108// Returns true if values are equal, under the canonicalization rules.
109inline bool areCanonicallyEquivalent(UChar a, UChar b)
110{
111    const UCS2CanonicalizationRange* info = rangeInfoFor(a);
112    switch (info->type) {
113    case CanonicalizeUnique:
114        return a == b;
115    case CanonicalizeSet: {
116        for (const uint16_t* set = characterSetInfo[info->value]; (a = *set); ++set) {
117            if (a == b)
118                return true;
119        }
120        return false;
121    }
122    case CanonicalizeRangeLo:
123        return (a == b) || (a + info->value == b);
124    case CanonicalizeRangeHi:
125        return (a == b) || (a - info->value == b);
126    case CanonicalizeAlternatingAligned:
127        return (a | 1) == (b | 1);
128    case CanonicalizeAlternatingUnaligned:
129        return ((a - 1) | 1) == ((b - 1) | 1);
130    }
131
132    RELEASE_ASSERT_NOT_REACHED();
133    return false;
134}
135
136} } // JSC::Yarr
137
138#endif
139