source: icGREP/icgrep-devel/icgrep/re/to_utf8.cpp @ 5908

Last change on this file since 5908 was 5908, checked in by cameron, 14 months ago

Byte-Bit grep kernel optimizes when an RE begins with an initial trigraph

File size: 3.6 KB
Line 
1/*
2 *  Copyright (c) 2017 International Characters.
3 *  This software is licensed to the public under the Open Software License 3.0.
4 *  icgrep is a trademark of International Characters.
5 */
6
7#include <re/to_utf8.h>
8#include <UCD/unicode_set.h>
9#include <UCD/UTF.h>
10#include <cc/alphabet.h>
11#include <re/re_name.h>
12#include <re/re_start.h>
13#include <re/re_end.h>
14#include <re/re_cc.h>
15#include <re/re_seq.h>
16#include <re/re_alt.h>
17#include <re/re_rep.h>
18#include <re/re_diff.h>
19#include <re/re_intersect.h>
20#include <re/re_assertion.h>
21#include <llvm/Support/Casting.h>
22#include <llvm/Support/ErrorHandling.h>
23
24using namespace llvm;
25
26namespace re {
27   
28static RE * rangeCodeUnits(codepoint_t lo, codepoint_t hi, unsigned index, const unsigned lgth){
29    const codepoint_t hunit = UTF<8>::nthCodeUnit(hi, index);
30    const codepoint_t lunit = UTF<8>::nthCodeUnit(lo, index);
31    if (index == lgth) {
32        return makeByte(lunit, hunit);
33    }
34    else if (hunit == lunit) {
35        return makeSeq({makeByte(hunit), rangeCodeUnits(lo, hi, index + 1, lgth)});
36    }
37    else {
38        const unsigned suffix_mask = (static_cast<unsigned>(1) << ((lgth - index) * 6)) - 1;
39        if ((hi & suffix_mask) != suffix_mask) {
40            const unsigned hi_floor = (~suffix_mask) & hi;
41            return makeAlt({rangeCodeUnits(hi_floor, hi, index, lgth), rangeCodeUnits(lo, hi_floor - 1, index, lgth)});
42        }
43        else if ((lo & suffix_mask) != 0) {
44            const unsigned low_ceil = lo | suffix_mask;
45            return makeAlt({rangeCodeUnits(low_ceil + 1, hi, index, lgth), rangeCodeUnits(lo, low_ceil, index, lgth)});
46        }
47        else {
48            return makeSeq({makeByte(lunit, hunit), rangeCodeUnits(lo, hi, index + 1, lgth)});
49        }
50    }
51}
52
53static RE * rangeToUTF8(codepoint_t lo, codepoint_t hi) {
54    const auto min_lgth = UTF<8>::encoded_length(lo);
55    const auto max_lgth = UTF<8>::encoded_length(hi);
56    if (min_lgth < max_lgth) {
57        const auto m = UTF<8>::max_codepoint_of_length(min_lgth);
58        return makeAlt({rangeToUTF8(lo, m), rangeToUTF8(m + 1, hi)});
59    }
60    else {
61        return rangeCodeUnits(lo, hi, 1, max_lgth);
62    }
63}
64
65RE * toUTF8(RE * r) {
66    if (isa<Name>(r) || isa<Start>(r) || isa<End>(r)) {
67        return r;
68    } else if (const CC * cc = dyn_cast<CC>(r)) {
69        if (cc->getAlphabet() != &cc::Unicode) return r;
70        std::vector<RE *> alt;
71        for (const interval_t & i : *cc) {
72            alt.push_back(rangeToUTF8(lo_codepoint(i), hi_codepoint(i)));
73        }
74        return makeAlt(alt.begin(), alt.end());
75    } else if (Alt * alt = dyn_cast<Alt>(r)) {
76        std::vector<RE *> list;
77        list.reserve(alt->size());
78        for (RE * a : *alt) {
79            list.push_back(toUTF8(a));
80        }
81        return makeAlt(list.begin(), list.end());
82    } else if (Seq * seq = dyn_cast<Seq>(r)) {
83        std::vector<RE *> list;
84        list.reserve(seq->size());
85        for (RE * s : *seq) {
86            list.push_back(toUTF8(s));
87        }
88        return makeSeq(list.begin(), list.end());
89    } else if (Assertion * a = dyn_cast<Assertion>(r)) {
90        return makeAssertion(toUTF8(a->getAsserted()), a->getKind(), a->getSense());
91    } else if (Rep * rep = dyn_cast<Rep>(r)) {
92        RE * expr = toUTF8(rep->getRE());
93        return makeRep(expr, rep->getLB(), rep->getUB());
94    } else if (Diff * diff = dyn_cast<Diff>(r)) {
95        return makeDiff(toUTF8(diff->getLH()), toUTF8(diff->getRH()));
96    } else if (Intersect * e = dyn_cast<Intersect>(r)) {
97        return makeIntersect(toUTF8(e->getLH()), toUTF8(e->getRH()));
98    }
99    llvm_unreachable("unexpected RE type given to toUTF8");
100    return nullptr;
101}
102
103}
104
Note: See TracBrowser for help on using the repository browser.