source: icGREP/icgrep-devel/icgrep/UCD/ucd_compiler.cpp @ 4622

Last change on this file since 4622 was 4622, checked in by nmedfort, 4 years ago

Preliminary changes to inclusion of UCD Compiler into the RE Compiler.

File size: 19.4 KB
Line 
1#include "ucd_compiler.hpp"
2#include <utf8_encoder.h>
3
4using namespace cc;
5using namespace re;
6using namespace pablo;
7
8namespace UCD {
9
10/** ------------------------------------------------------------------------------------------------------------- *
11 * @brief generateWithDefaultIfHierarchy
12 * @param set the unicode set to generate
13 * @param the entry block to the function we're filling
14 * @return the output stream with a 1-bit in any position of a character in the unicode set
15 ** ------------------------------------------------------------------------------------------------------------- */
16inline PabloAST * UCDCompiler::generateWithIfHierarchy(const RangeList & ifRanges, const UnicodeSet & set, PabloBuilder & entry) {
17    return generateWithIfHierarchy(ifRanges, set, 0, CC::UNICODE_MAX, entry);
18}
19
20/** ------------------------------------------------------------------------------------------------------------- *
21 * @brief generateCharClassDefsInIfHierarchy
22 * @param ifRangeList
23 ** ------------------------------------------------------------------------------------------------------------- */
24PabloAST * UCDCompiler::generateWithIfHierarchy(const RangeList & ifRanges, const UnicodeSet & set, const codepoint_t lo, const codepoint_t hi, PabloBuilder & block) {
25
26    PabloAST * target = block.createZeroes();
27    // Codepoints in unenclosed ranges will be computed unconditionally.
28    // Generate them first so that computed subexpressions may be shared
29    // with calculations within the if hierarchy.
30
31    const auto enclosed = rangeIntersect(ifRanges, lo, hi);
32
33    for (const auto rg : rangeGaps(enclosed, lo, hi)) {
34        target = generateSubRanges(set, lo_codepoint(rg), hi_codepoint(rg), block, target);
35    }
36
37    const auto outer = outerRanges(enclosed);
38    const auto inner = innerRanges(enclosed);
39
40    for (const auto range : outer) {
41        codepoint_t lo, hi;
42        std::tie(lo, hi) = range;
43        if (rangeIntersect(set, lo, hi).empty()) {
44            continue;
45        }
46        PabloBuilder inner_block(block);
47        PabloAST * inner_target = generateWithIfHierarchy(inner, set, lo, hi, inner_block);
48        // If this range is empty, just skip creating the if block
49        if (LLVM_UNLIKELY(isa<Zeroes>(inner_target))) {
50            continue;
51        }
52        Assign * matches = inner_block.createAssign("m", inner_target);
53        block.createIf(ifTestCompiler(lo, hi, block), {matches}, inner_block.getPabloBlock());
54        target = block.createOr(target, matches);
55    }
56
57    return target;
58}
59
60/** ------------------------------------------------------------------------------------------------------------- *
61 * @brief generateCharClassSubDefs
62 * @param ifRangeList
63 ** ------------------------------------------------------------------------------------------------------------- */
64PabloAST * UCDCompiler::generateSubRanges(const UnicodeSet & set, const codepoint_t lo, const codepoint_t hi, PabloBuilder & block, PabloAST * target) {
65    const auto range = rangeIntersect(set, lo, hi);
66    // Divide by UTF-8 length, separating out E0, ED, F0 and F4 ranges
67    const std::array<interval_t, 9> ranges =
68        {{{0, 0x7F}, {0x80, 0x7FF}, {0x800, 0xFFF}, {0x1000, 0xD7FF}, {0xD800, 0xDFFF},
69         {0xE000, 0xFFFF}, {0x10000, 0x3FFFF}, {0x40000, 0xFFFFF}, {0x100000, 0x10FFFF}}};
70    for (auto r : ranges) {
71        const auto subrange = rangeIntersect(range, lo_codepoint(r), hi_codepoint(r));
72        target = sequenceGenerator(std::move(subrange), 1, block, target, nullptr);
73    }
74    return target;
75}
76
77/** ------------------------------------------------------------------------------------------------------------- *
78 * @brief sequenceGenerator
79 * @param ifRangeList
80 *
81 *
82 * Generate remaining code to match UTF-8 code sequences within the codepoint set cpset, assuming that the code
83 * matching the sequences up to byte number byte_no have been generated.
84 ** ------------------------------------------------------------------------------------------------------------- */
85PabloAST * UCDCompiler::sequenceGenerator(const RangeList && ranges, const unsigned byte_no, PabloBuilder & block, PabloAST * target, PabloAST * prefix) {
86
87    if (LLVM_LIKELY(!ranges.empty())) {
88
89        codepoint_t lo, hi;
90        std::tie(lo, hi) = ranges[0];
91
92        const auto min = UTF8_Encoder::length(lo_codepoint(ranges.front()));
93        const auto max = UTF8_Encoder::length(hi_codepoint(ranges.back()));
94
95        if (min != max) {
96            const auto mid = UTF8_Encoder::maxCodePoint(min);
97            target = sequenceGenerator(std::move(rangeIntersect(ranges, lo, mid)), byte_no, block, target, prefix);
98            target = sequenceGenerator(std::move(rangeIntersect(ranges, mid + 1, hi)), byte_no, block, target, prefix);
99        }
100        else if (min == byte_no) {
101            // We have a single byte remaining to marangetch for all codepoints in this cc.
102            // Use the byte class compiler to generate matches for these codepoints.
103            const auto bytes = byteDefinitions(ranges, byte_no);
104            PabloAST * testVar = mCharacterClassCompiler.compileCC(makeCC(bytes), block);
105            if (byte_no > 1) {
106                testVar = block.createAnd(testVar, block.createAdvance(makePrefix(lo, byte_no, block), 1));
107            }
108            target = block.createOr(target, testVar);
109        }
110        else {
111            for (auto rg : ranges) {
112                codepoint_t lo, hi;
113                std::tie(lo, hi) = rg;
114                const auto lo_byte = UTF8_Encoder::encodingByte(lo, byte_no);
115                const auto hi_byte = UTF8_Encoder::encodingByte(hi, byte_no);
116                if (lo_byte != hi_byte) {
117                    if (!UTF8_Encoder::isLowCodePointAfterByte(lo, byte_no)) {
118                        const codepoint_t mid = lo | ((1 << (6 * (min - byte_no))) - 1);
119                        target = sequenceGenerator(lo, mid, byte_no, block, target, prefix);
120                        target = sequenceGenerator(mid + 1, hi, byte_no, block, target, prefix);
121                    }
122                    else if (!UTF8_Encoder::isHighCodePointAfterByte(hi, byte_no)) {
123                        const codepoint_t mid = hi & ~((1 << (6 * (min - byte_no))) - 1);
124                        target = sequenceGenerator(lo, mid - 1, byte_no, block, target, prefix);
125                        target = sequenceGenerator(mid, hi, byte_no, block, target, prefix);
126                    }
127                    else { // we have a prefix group of type (a)
128                        PabloAST * byteVar = mCharacterClassCompiler.compileCC(makeCC(lo_byte, hi_byte), block);
129                        PabloAST * infix = byteVar;
130                        if (byte_no > 1) {
131                            infix = block.createAnd(block.createAdvance(prefix, 1), byteVar);
132                        }
133                        PabloAST * suffixVar = mCharacterClassCompiler.compileCC(mSuffix, block);
134                        for (auto i = byte_no; i < UTF8_Encoder::length(lo); ++i) {
135                            infix = block.createAnd(suffixVar, block.createAdvance(infix, 1));
136                        }
137                        target = block.createOr(target, infix);
138                    }
139                }
140                else { // lbyte == hbyte
141                    PabloAST * byteVar = mCharacterClassCompiler.compileCC(makeCC(lo_byte, hi_byte), block);
142                    PabloAST * infix = byteVar;
143                    if (byte_no > 1) {
144                        infix = block.createAnd(block.createAdvance(prefix ? prefix : byteVar, 1), byteVar);
145                    }
146                    if (byte_no < UTF8_Encoder::length(lo)) {
147                        target = sequenceGenerator(lo, hi, byte_no + 1, block, target, infix);
148                    }
149                }
150            }
151        }
152    }
153
154    return target;
155}
156
157/** ------------------------------------------------------------------------------------------------------------- *
158 * @brief sequenceGenerator
159 ** ------------------------------------------------------------------------------------------------------------- */
160inline PabloAST * UCDCompiler::sequenceGenerator(const codepoint_t lo, const codepoint_t hi, const unsigned byte_no, PabloBuilder & block, PabloAST * target, PabloAST * prefix) {
161    return sequenceGenerator({{ lo, hi }}, byte_no, block, target, prefix);
162}
163
164/** ------------------------------------------------------------------------------------------------------------- *
165 * @brief ifTestCompiler
166 ** ------------------------------------------------------------------------------------------------------------- */
167inline PabloAST * UCDCompiler::ifTestCompiler(const codepoint_t lo, const codepoint_t hi, PabloBuilder & block) {
168    return ifTestCompiler(lo, hi, 1, block, block.createOnes());
169}
170
171/** ------------------------------------------------------------------------------------------------------------- *
172 * @brief ifTestCompiler
173 ** ------------------------------------------------------------------------------------------------------------- */
174PabloAST * UCDCompiler::ifTestCompiler(const codepoint_t lo, const codepoint_t hi, const unsigned byte_no, PabloBuilder & block, PabloAST * target) {
175    codepoint_t lo_byte = UTF8_Encoder::encodingByte(lo, byte_no);
176    codepoint_t hi_byte = UTF8_Encoder::encodingByte(hi, byte_no);
177    const bool at_lo_boundary = (lo == 0 || UTF8_Encoder::encodingByte(lo - 1, byte_no) != lo_byte);
178    const bool at_hi_boundary = (hi == 0x10FFFF || UTF8_Encoder::encodingByte(hi + 1, byte_no) != hi_byte);
179    if (at_lo_boundary && at_hi_boundary) {
180        if (lo_byte != hi_byte) {
181            if (lo == 0x80) lo_byte = 0xC0;
182            if (hi == 0x10FFFF) hi_byte = 0xFF;
183        }
184        PabloAST * cc = mCharacterClassCompiler.compileCC(makeCC(lo_byte, hi_byte), block);
185        target = block.createAnd(cc, target);
186    }
187    else if (lo_byte == hi_byte) {
188        PabloAST * cc = mCharacterClassCompiler.compileCC(makeCC(lo_byte, hi_byte), block);
189        target = block.createAnd(cc, target);
190        target = block.createAdvance(target, 1);
191        target = ifTestCompiler(lo, hi, byte_no + 1, block, target);
192    }
193    else if (at_hi_boundary) {
194        const auto mid = UTF8_Encoder::maxCodePointWithCommonBytes(hi, byte_no);
195        PabloAST * e1 = ifTestCompiler(lo, mid, byte_no, block, target);
196        PabloAST * e2 = ifTestCompiler(mid + 1, hi, byte_no, block, target);
197        target = block.createOr(e1, e2);
198    }
199    else {
200        const auto mid = UTF8_Encoder::minCodePointWithCommonBytes(hi, byte_no);
201        PabloAST * e1 = ifTestCompiler(lo, mid - 1, byte_no, block, target);
202        PabloAST * e2 = ifTestCompiler(mid, hi, byte_no, block, target);
203        target = block.createOr(e1, e2);
204    }
205    return target;
206}
207
208/** ------------------------------------------------------------------------------------------------------------- *
209 * @brief definePrecedingPrefix
210 * @param ifRangeList
211 *
212 *
213 * Ensure the sequence of preceding bytes is defined, up to, but not including the given byte_no
214 ** ------------------------------------------------------------------------------------------------------------- */
215PabloAST * UCDCompiler::makePrefix(const codepoint_t cp, const unsigned byte_no, pablo::PabloBuilder & pb) {
216    std::array<PabloAST *, 4> prefixes;
217    assert (byte_no >= 1 && byte_no <= 4);
218    for (unsigned i = 1; i != byte_no; ++i) {
219        const CC * const cc = makeCC(UTF8_Encoder::encodingByte(cp, i));
220        prefixes[i - 1] = mCharacterClassCompiler.compileCC(cc, pb);
221        if (i > 1) {
222            prefixes[i - 1] = pb.createAnd(prefixes[i - 1], pb.createAdvance(prefixes[i - 2], 1));
223        }
224    }
225    return prefixes[byte_no - 1];
226}
227
228/** ------------------------------------------------------------------------------------------------------------- *
229 * @brief definePrecedingPrefix
230 * @param ifRangeList
231 *
232 *
233 * Ensure the sequence of preceding bytes is defined, up to, but not including the given byte_no
234 ** ------------------------------------------------------------------------------------------------------------- */
235UCDCompiler::RangeList UCDCompiler::byteDefinitions(const RangeList & list, const unsigned byte_no) {
236    RangeList result;
237    result.reserve(list.size());
238    for (const auto & i : list) {
239        result.emplace_back(UTF8_Encoder::encodingByte(lo_codepoint(i), byte_no), UTF8_Encoder::encodingByte(hi_codepoint(i), byte_no));
240    }
241    return result;
242}
243
244/** ------------------------------------------------------------------------------------------------------------- *
245 * @brief rangeIntersect
246 * @param list
247 * @param lo
248 * @param hi
249 ** ------------------------------------------------------------------------------------------------------------- */
250template <typename RangeListOrUnicodeSet>
251UCDCompiler::RangeList UCDCompiler::rangeIntersect(const RangeListOrUnicodeSet & list, const codepoint_t lo, const codepoint_t hi) {
252    RangeList intersection;
253    for (const auto i : list) {
254        if ((lo_codepoint(i) <= hi) && (hi_codepoint(i) >= lo)) {
255            intersection.emplace_back(std::max(lo, lo_codepoint(i)), std::min(hi, hi_codepoint(i)));
256        }
257    }
258    return intersection;
259}
260
261/** ------------------------------------------------------------------------------------------------------------- *
262 * @brief rangeGaps
263 * @param cc
264 * @param lo
265 * @param hi
266 ** ------------------------------------------------------------------------------------------------------------- */
267UCDCompiler::RangeList UCDCompiler::rangeGaps(const RangeList & list, const codepoint_t lo, const codepoint_t hi) {
268    RangeList gaps;
269    if (LLVM_LIKELY(lo < hi)) {
270        if (LLVM_UNLIKELY(list.empty())) {
271            gaps.emplace_back(lo, hi);
272        }
273        else {
274            codepoint_t cp = lo;
275            for (const auto & i : list) {
276                if (hi_codepoint(i) < cp) {
277                    continue;
278                }
279                else if (lo_codepoint(i) > cp) {
280                    gaps.emplace_back(cp, lo_codepoint(i) - 1);
281                }
282                else if (hi_codepoint(i) >= hi) {
283                    continue;
284                }
285                cp = hi_codepoint(i) + 1;
286            }
287        }
288    }
289    return gaps;
290}
291
292/** ------------------------------------------------------------------------------------------------------------- *
293 * @brief rangeOuter
294 * @param list
295 ** ------------------------------------------------------------------------------------------------------------- */
296UCDCompiler::RangeList UCDCompiler::outerRanges(const RangeList & list) {
297    RangeList ranges;
298    for (auto i = list.cbegin(), j = i; ++j != list.cend(); ) {
299        if (hi_codepoint(*j) > hi_codepoint(*i)) {
300            ranges.emplace_back(lo_codepoint(*i), hi_codepoint(*i));
301            i = j;
302        }
303    }
304    return ranges;
305}
306
307/** ------------------------------------------------------------------------------------------------------------- *
308 * @brief rangeInner
309 * @param list
310 ** ------------------------------------------------------------------------------------------------------------- */
311UCDCompiler::RangeList UCDCompiler::innerRanges(const RangeList & list) {
312    RangeList ranges;
313    for (auto i = list.cbegin(), j = i; ++j != list.cend(); ) {
314        if (hi_codepoint(*j) <= hi_codepoint(*i)) {
315            ranges.emplace_back(lo_codepoint(*j), hi_codepoint(*j));
316        }
317        else {
318            i = j;
319        }
320    }
321    return ranges;
322}
323
324/** ------------------------------------------------------------------------------------------------------------- *
325 * @brief generateWithDefaultIfHierarchy
326 * @param set the unicode set to generate
327 * @param the entry block to the function we're filling
328 * @return the output stream with a 1-bit in any position of a character in the unicode set
329 ** ------------------------------------------------------------------------------------------------------------- */
330inline PabloAST * UCDCompiler::generateWithDefaultIfHierarchy(const UnicodeSet & set, PabloBuilder & entry) {
331
332    const RangeList ifRanges = {
333        // Non-ASCII
334        {0x80, 0x10FFFF},
335        // Two-byte sequences
336        {0x80, 0x7FF},
337        {0x100, 0x3FF},
338        // 0100..017F; Latin Extended-A
339        // 0180..024F; Latin Extended-B
340        // 0250..02AF; IPA Extensions
341        // 02B0..02FF; Spacing Modifier Letters
342        {0x100, 0x2FF}, {0x100, 0x24F}, {0x100, 0x17F}, {0x180, 0x24F}, {0x250, 0x2AF}, {0x2B0, 0x2FF},
343        // 0300..036F; Combining Diacritical Marks
344        // 0370..03FF; Greek and Coptic
345        {0x300, 0x36F}, {0x370, 0x3FF},
346        // 0400..04FF; Cyrillic
347        // 0500..052F; Cyrillic Supplement
348        // 0530..058F; Armenian
349        // 0590..05FF; Hebrew
350        // 0600..06FF; Arabic
351        {0x400, 0x5FF}, {0x400, 0x4FF}, {0x500, 0x058F}, {0x500, 0x52F}, {0x530, 0x58F}, {0x590, 0x5FF}, {0x600, 0x6FF},
352        // 0700..074F; Syriac
353        // 0750..077F; Arabic Supplement
354        // 0780..07BF; Thaana
355        // 07C0..07FF; NKo
356        {0x700, 0x77F}, {0x700, 0x74F}, {0x750, 0x77F}, {0x780, 0x7FF}, {0x780, 0x7BF}, {0x7C0, 0x7FF},
357        // Three-byte sequences
358        {0x800, 0xFFFF}, {0x800, 0x4DFF}, {0x800, 0x1FFF}, {0x800, 0x0FFF},
359        // 0800..083F; Samaritan
360        // 0840..085F; Mandaic
361        // 08A0..08FF; Arabic Extended-A
362        // 0900..097F; Devanagari
363        // 0980..09FF; Bengali
364        // 0A00..0A7F; Gurmukhi
365        // 0A80..0AFF; Gujarati
366        // 0B00..0B7F; Oriya
367        // 0B80..0BFF; Tamil
368        // 0C00..0C7F; Telugu
369        // 0C80..0CFF; Kannada
370        // 0D00..0D7F; Malayalam
371        // 0D80..0DFF; Sinhala
372        // 0E00..0E7F; Thai
373        // 0E80..0EFF; Lao
374        // 0F00..0FFF; Tibetan
375        {0x1000, 0x1FFF},
376        // 1000..109F; Myanmar
377        // 10A0..10FF; Georgian
378        // 1100..11FF; Hangul Jamo
379        // 1200..137F; Ethiopic
380        // 1380..139F; Ethiopic Supplement
381        // 13A0..13FF; Cherokee
382        // 1400..167F; Unified Canadian Aboriginal Syllabics
383        // 1680..169F; Ogham
384        // 16A0..16FF; Runic
385        // 1700..171F; Tagalog
386        // 1720..173F; Hanunoo
387        // 1740..175F; Buhid
388        // 1760..177F; Tagbanwa
389        // 1780..17FF; Khmer
390        // 1800..18AF; Mongolian
391        // 18B0..18FF; Unified Canadian Aboriginal Syllabics Extended
392        // 1900..194F; Limbu
393        // 1950..197F; Tai Le
394        // 1980..19DF; New Tai Lue
395        // 19E0..19FF; Khmer Symbols
396        // 1A00..1A1F; Buginese
397        // 1A20..1AAF; Tai Tham
398        // 1AB0..1AFF; Combining Diacritical Marks Extended
399        // 1B00..1B7F; Balinese
400        // 1B80..1BBF; Sundanese
401        // 1BC0..1BFF; Batak
402        // 1C00..1C4F; Lepcha
403        // 1C50..1C7F; Ol Chiki
404        // 1CC0..1CCF; Sundanese Supplement
405        // 1CD0..1CFF; Vedic Extensions
406        // 1D00..1D7F; Phonetic Extensions
407        // 1D80..1DBF; Phonetic Extensions Supplement
408        // 1DC0..1DFF; Combining Diacritical Marks Supplement
409        // 1E00..1EFF; Latin Extended Additional
410        // 1F00..1FFF; Greek Extended
411        {0x2000, 0x4DFF}, {0x2000, 0x2FFF},
412        {0x3000, 0x4DFF},
413        {0x4E00, 0x9FFF},
414        // 4E00..9FFF; CJK Unified Ideographs
415        {0xA000, 0xFFFF},
416
417        {0x10000, 0x10FFFF}};
418
419    return generateWithIfHierarchy(ifRanges, set, entry);
420}
421
422/** ------------------------------------------------------------------------------------------------------------- *
423 * @brief constructor
424 ** ------------------------------------------------------------------------------------------------------------- */
425UCDCompiler::UCDCompiler(cc::CC_Compiler & ccCompiler)
426: mCharacterClassCompiler(ccCompiler)
427, mSuffix(makeCC(0x80, 0xBF)) { }
428
429}
Note: See TracBrowser for help on using the repository browser.