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

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

Couple more bug fixes for UCD Compiler.

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