source: icGREP/icgrep-devel/icgrep/UCD/PropertyObjects.cpp

Last change on this file was 6276, checked in by cameron, 6 months ago

Eliminate pessimizing moves

File size: 18.6 KB
Line 
1/*
2 *  Copyright (c) 2018 International Characters, Inc.
3 *  This software is licensed to the public under the Open Software License 3.0.
4 *  icgrep is a trademark of International Characters, Inc.
5 *
6 */
7
8#include "PropertyObjects.h"
9#include "PropertyObjectTable.h"
10#include <llvm/Support/Casting.h>
11#include <llvm/Support/raw_ostream.h>
12#include <sstream>
13#include <llvm/Support/ErrorHandling.h>
14#include <toolchain/cpudriver.h>
15#include <grep/grep_engine.h>
16#include <util/aligned_allocator.h>
17#include <re/re_analysis.h>
18#include <re/re_cc.h>
19#include <codecvt>
20
21
22using namespace llvm;
23
24namespace UCD {
25
26std::string canonicalize_value_name(const std::string & prop_or_val) {
27    std::locale loc;
28    std::stringstream s;
29
30    for (char c : prop_or_val) {
31        if ((c != '_') && (c != ' ') && (c != '-')) {
32            s << std::tolower(c, loc);
33        }
34    }
35    return s.str();
36}
37
38const std::string & PropertyObject::GetPropertyValueGrepString() {
39    llvm::report_fatal_error("Property Value Grep String unsupported.");
40}
41
42const UnicodeSet PropertyObject::GetCodepointSet(const std::string &) {
43    llvm::report_fatal_error("Property " + UCD::property_full_name[the_property] + " unsupported.");
44}
45
46const UnicodeSet PropertyObject::GetCodepointSetMatchingPattern(re::RE * pattern) {
47    llvm::report_fatal_error("GetCodepointSetMatchingPattern unsupported");
48}
49
50const std::string PropertyObject::GetStringValue(codepoint_t cp) const {
51    llvm::report_fatal_error("GetStringValue unsupported");
52}
53
54const UnicodeSet EnumeratedPropertyObject::GetCodepointSet(const std::string & value_spec) {
55    const int property_enum_val = GetPropertyValueEnumCode(value_spec);
56    if (property_enum_val < 0) {
57        llvm::report_fatal_error("Enumerated Property " + UCD::property_full_name[the_property] + ": unknown value: " + value_spec);
58    }
59    return GetCodepointSet(property_enum_val);
60}
61   
62const UnicodeSet PropertyObject::GetReflexiveSet() const {
63    return UnicodeSet();
64}
65
66
67class PropertyValueAccumulator : public grep::MatchAccumulator {
68public:
69   
70    PropertyValueAccumulator(std::vector<std::string> & accumulatedPropertyValues)
71    : mParsedPropertyValueSet(accumulatedPropertyValues) {}
72   
73    void accumulate_match(const size_t lineNum, char * line_start, char * line_end) override;
74private:
75    std::vector<std::string> & mParsedPropertyValueSet;
76};
77void PropertyValueAccumulator::accumulate_match(const size_t lineNum, char * line_start, char * line_end) {
78    assert (line_start <= line_end);
79    mParsedPropertyValueSet.emplace_back(line_start, line_end);
80}
81
82const UnicodeSet EnumeratedPropertyObject::GetCodepointSetMatchingPattern(re::RE * pattern) {
83
84
85    AlignedAllocator<char, 32> alloc;
86    std::vector<std::string> accumulatedValues;
87   
88    const std::string & str = GetPropertyValueGrepString();
89   
90    const unsigned segmentSize = 8;
91    const auto n = str.length();
92    const auto w = 256 * segmentSize;
93    const auto m = w - (n % w);
94   
95    char * aligned = alloc.allocate(n + m, 0);
96    std::memcpy(aligned, str.data(), n);
97    std::memset(aligned + n, 0, m);
98   
99    PropertyValueAccumulator accum(accumulatedValues);
100    CPUDriver driver("driver");
101    grep::InternalSearchEngine engine(driver);
102    engine.setRecordBreak(grep::GrepRecordBreakKind::LF);
103    engine.grepCodeGen(pattern, nullptr);
104    engine.doGrep(aligned, n, accum);
105    //grepBuffer(pattern, aligned, n, & accum);
106    alloc.deallocate(aligned, 0);
107   
108    UnicodeSet a;
109    for (const auto & v : accumulatedValues) {       
110        const auto e = GetPropertyValueEnumCode(v);
111        a.insert(GetCodepointSet(e));
112    }
113    return a;
114}
115
116const UnicodeSet & EnumeratedPropertyObject::GetCodepointSet(const int property_enum_val) const {
117    assert (property_enum_val >= 0);
118    return *(property_value_sets[property_enum_val]);
119}
120
121std::vector<UnicodeSet> & EnumeratedPropertyObject::GetEnumerationBasisSets() {
122    // Return the previously computed vector of basis sets, if it exists.
123    if (LLVM_UNLIKELY(enumeration_basis_sets.empty())) {
124        // Otherwise compute and return.
125        // Basis set i is the set of all codepoints whose numerical enumeration code e
126        // has bit i set, i.e., (e >> i) & 1 == 1.
127        unsigned basis_count = 1;
128        while ((1UL << basis_count) < independent_enum_count) {
129            basis_count++;
130        }
131        for (unsigned i = 0; i < basis_count; i++) {
132            enumeration_basis_sets.push_back(UnicodeSet());
133            for (unsigned e = 0; e < independent_enum_count; e++) {
134                if (((e >> i) & 1UL) == 1UL) {
135                    enumeration_basis_sets[i] = enumeration_basis_sets[i] + *property_value_sets[e];
136                }
137            }
138        }
139    }
140    return enumeration_basis_sets;
141}
142
143unsigned EnumeratedPropertyObject::GetEnumerationValue(codepoint_t cp) {
144    unsigned enum_value = 0;
145    if (LLVM_UNLIKELY(enumeration_basis_sets.empty())) {
146        GetEnumerationBasisSets();
147    }
148    unsigned basis_count = enumeration_basis_sets.size();
149    for (unsigned i = 0; i < basis_count; i++) {
150        if (enumeration_basis_sets[i].contains(cp)) {
151            enum_value += 1 << i;
152        }
153    }
154    return enum_value;
155}
156
157const std::string & EnumeratedPropertyObject::GetPropertyValueGrepString() {
158    if (LLVM_LIKELY(mPropertyValueGrepString.empty())) {
159        std::stringstream buffer;
160        for (unsigned i = 0; i != property_value_full_names.size(); i++) {
161            buffer << property_value_full_names[i] + "\n";
162        }
163        for (unsigned i = 0; i != property_value_enum_names.size(); i++) {
164            if (property_value_enum_names[i] == property_value_full_names[i]) continue;
165            buffer << property_value_enum_names[i] + "\n";
166        }
167        for (auto & a : property_value_aliases) {
168            buffer << a.first + "\n";
169        }
170        mPropertyValueGrepString = buffer.str();
171    }
172    return mPropertyValueGrepString;
173}
174
175int EnumeratedPropertyObject::GetPropertyValueEnumCode(const std::string & value_spec) {
176    // The canonical full names are not stored in the precomputed alias map,
177    // to save space in the executable.   Add them if the property is used.
178    if (uninitialized) {
179        for (unsigned i = 0; i != property_value_full_names.size(); i++) {
180            property_value_aliases.insert({canonicalize_value_name(property_value_full_names[i]), i});
181        }
182        for (unsigned i = 0; i != property_value_enum_names.size(); i++) {
183            property_value_aliases.insert({canonicalize_value_name(property_value_enum_names[i]), i});
184        }
185        uninitialized = false;
186    }
187    const auto valit = property_value_aliases.find(canonicalize_value_name(value_spec));
188    if (valit == property_value_aliases.end())
189        return -1;
190    return valit->second;
191}
192
193PropertyObject::iterator ExtensionPropertyObject::begin() const {
194    if (const auto * obj = dyn_cast<EnumeratedPropertyObject>(property_object_table[base_property])) {
195        return obj->begin();
196    }
197    llvm::report_fatal_error("Iterators unsupported for this type of PropertyObject.");
198}
199
200PropertyObject::iterator ExtensionPropertyObject::end() const {
201    if (const auto * obj = dyn_cast<EnumeratedPropertyObject>(property_object_table[base_property])) {
202        return obj->end();
203    }
204    llvm::report_fatal_error("Iterators unsupported for this type of PropertyObject.");
205}
206
207const UnicodeSet ExtensionPropertyObject::GetCodepointSet(const std::string & value_spec) {
208    int property_enum_val = GetPropertyValueEnumCode(value_spec);
209    if (property_enum_val == -1) {
210        llvm::report_fatal_error("Extension Property " + UCD::property_full_name[the_property] +  ": unknown value: " + value_spec);
211    }
212    return GetCodepointSet(property_enum_val);
213}
214
215const UnicodeSet & ExtensionPropertyObject::GetCodepointSet(const int property_enum_val) const {
216    assert (property_enum_val >= 0);
217    return *(property_value_sets[property_enum_val]);
218}
219
220int ExtensionPropertyObject::GetPropertyValueEnumCode(const std::string & value_spec) {
221    return cast<EnumeratedPropertyObject>(property_object_table[base_property])->GetPropertyValueEnumCode(value_spec);
222}
223   
224const UnicodeSet ExtensionPropertyObject::GetCodepointSetMatchingPattern(re::RE * pattern) {
225    AlignedAllocator<char, 32> alloc;
226    std::vector<std::string> accumulatedValues;
227   
228    EnumeratedPropertyObject * baseObj = cast<EnumeratedPropertyObject>(property_object_table[base_property]);
229   
230    const std::string & str = baseObj->GetPropertyValueGrepString();
231   
232    const unsigned segmentSize = 8;
233    const auto n = str.length();
234    const auto w = 256 * segmentSize;
235    const auto m = w - (n % w);
236   
237    char * aligned = alloc.allocate(n + m, 0);
238    std::memcpy(aligned, str.data(), n);
239    std::memset(aligned + n, 0, m);
240   
241    PropertyValueAccumulator accum(accumulatedValues);
242    CPUDriver driver("driver");
243    grep::InternalSearchEngine engine(driver);
244    engine.setRecordBreak(grep::GrepRecordBreakKind::LF);
245    engine.grepCodeGen(pattern, nullptr);
246    engine.doGrep(aligned, n, accum);
247    alloc.deallocate(aligned, 0);
248   
249    UnicodeSet a;
250    for (const auto & v : accumulatedValues) {
251        int e = baseObj->GetPropertyValueEnumCode(v);
252        a.insert(GetCodepointSet(e));
253    }
254    return a;
255}
256
257
258const std::string & ExtensionPropertyObject::GetPropertyValueGrepString() {
259    return property_object_table[base_property]->GetPropertyValueGrepString();
260}
261
262const UnicodeSet BinaryPropertyObject::GetCodepointSet(const std::string & value_spec) {
263    int property_enum_val = Binary_ns::Y;
264    if (value_spec.length() != 0) {
265        auto valit = Binary_ns::aliases_only_map.find(canonicalize_value_name(value_spec));
266        if (valit == Binary_ns::aliases_only_map.end()) {
267            llvm::report_fatal_error("Binary Property " + UCD::property_full_name[the_property] +  ": bad value: " + value_spec);
268        }
269        property_enum_val = valit->second;
270    }
271    return GetCodepointSet(property_enum_val);
272}
273
274const UnicodeSet & BinaryPropertyObject::GetCodepointSet(const int property_enum_val) {
275    if (property_enum_val == Binary_ns::Y) {
276        return mY;
277    }
278    if (mN.get() == nullptr) {
279        mN = llvm::make_unique<UnicodeSet>(~mY);
280    }
281    return *mN;
282}
283
284const UnicodeSet BinaryPropertyObject::GetCodepointSetMatchingPattern(re::RE * pattern) {
285    llvm::report_fatal_error("Enumerated Property GetCodepointSetMatchingPattern not yet implemented");
286}
287   
288const std::string & BinaryPropertyObject::GetPropertyValueGrepString() {
289    if (mPropertyValueGrepString.empty()) {
290        std::stringstream buffer;
291        for (const auto & prop : Binary_ns::aliases_only_map) {
292            buffer << std::get<0>(prop) + "\n";
293        }
294        mPropertyValueGrepString = buffer.str();
295    }
296    return mPropertyValueGrepString;
297}
298   
299const unsigned firstCodepointLengthAndVal(const std::string & s, codepoint_t & cp) {
300    size_t lgth = s.length();
301    cp = 0;
302    if (lgth == 0) return 0;
303    unsigned char s0 = s[0];
304    cp = static_cast<codepoint_t>(s0);
305    if (s0 < 0x80) return 1;
306    if (lgth == 1) return 0;  // invalid UTF-8
307    cp = ((cp & 0x1F) << 6) | (s[1] & 0x3F);
308    if ((s0 >= 0xC2) && (s0 <= 0xDF)) return 2;
309    if (lgth == 2) return 0;  // invalid UTF-8
310    cp = ((cp & 0x3FFF) << 6) | (s[2] & 0x3F);
311    if ((s0 >= 0xE0) && (s0 <= 0xEF)) return 3;
312    if (lgth == 3) return 0;  // invalid UTF-8
313    cp = ((cp & 0x7FFF) << 6) | (s[3] & 0x3F);
314    if ((s0 >= 0xF0) && (s0 <= 0xF4)) return 4;
315    return 0;
316}
317   
318class SetByLineNumberAccumulator : public grep::MatchAccumulator {
319public:
320   
321    SetByLineNumberAccumulator(const std::vector<UCD::codepoint_t> & cps, const UnicodeSet & defaultValueSet)
322    : mCodepointTableByLineNum(cps)
323    , mDefaultValueSet(defaultValueSet) {
324
325    }
326   
327    void accumulate_match(const size_t lineNum, char * line_start, char * line_end) override;
328    UnicodeSet && getAccumulatedSet() { return std::move(mAccumSet); }
329private:
330    const std::vector<UCD::codepoint_t> & mCodepointTableByLineNum;
331    const UnicodeSet & mDefaultValueSet;
332    UnicodeSet mAccumSet;
333};
334
335void SetByLineNumberAccumulator::accumulate_match(const size_t lineNum, char * /* line_start */, char * /* line_end */) {
336    if (lineNum >= mCodepointTableByLineNum.size()) {
337        mAccumSet.insert(mDefaultValueSet);
338    } else {
339        mAccumSet.insert(mCodepointTableByLineNum[lineNum]);
340    }
341}
342
343const UnicodeSet NumericPropertyObject::GetCodepointSet(const std::string & value_spec) {
344    if (value_spec == "NaN") {
345        return mNaNCodepointSet;
346    } else {
347        UnicodeSet result_set;
348        unsigned val_bytes = value_spec.length();
349        const char * value_str = value_spec.c_str();
350        const char * search_str = mStringBuffer;
351        unsigned buffer_line = 0;
352        while (buffer_line < mExplicitCps.size()) {
353            const char * eol = strchr(search_str, '\n');
354            unsigned len = eol - search_str;
355            if ((len == val_bytes) && (memcmp(search_str, value_str, len) == 0)) {
356                result_set.insert(mExplicitCps[buffer_line]);
357            }
358            buffer_line++;
359            search_str = eol+1;
360        }
361        return result_set;
362    }
363}
364
365const UnicodeSet NumericPropertyObject::GetCodepointSetMatchingPattern(re::RE * pattern) {
366    SetByLineNumberAccumulator accum(mExplicitCps, mNaNCodepointSet);
367    CPUDriver driver("driver");
368    grep::InternalSearchEngine engine(driver);
369    engine.setRecordBreak(grep::GrepRecordBreakKind::LF);
370    engine.grepCodeGen(pattern, nullptr);
371    engine.doGrep(mStringBuffer, mBufSize, accum);
372    //grepBuffer(pattern, mStringBuffer, mBufSize, &accum);
373    return accum.getAccumulatedSet();
374}
375
376
377const UnicodeSet StringPropertyObject::GetCodepointSet(const std::string & value_spec) {
378    if (value_spec.empty()) {
379        return mNullCodepointSet;
380    } else {
381        UnicodeSet result_set;
382        unsigned val_bytes = value_spec.length();
383        codepoint_t cp;
384        if (val_bytes == firstCodepointLengthAndVal(value_spec, cp)) {
385            if (mSelfCodepointSet.contains(cp)) {
386                result_set.insert(cp);
387            }
388        }
389        const char * value_str = value_spec.c_str();
390        const char * search_str = mStringBuffer;
391        unsigned buffer_line = 0;
392        while (buffer_line < mExplicitCps.size()) {
393            const char * eol = strchr(search_str, '\n');
394            unsigned len = eol - search_str;
395            if ((len == val_bytes) && (memcmp(search_str, value_str, len) == 0)) {
396                result_set.insert(mExplicitCps[buffer_line]);
397            }
398            buffer_line++;
399            search_str = eol+1;
400        }
401        return result_set;
402    }
403}
404
405const UnicodeSet StringPropertyObject::GetCodepointSetMatchingPattern(re::RE * pattern) {
406    UnicodeSet matched(*matchableCodepoints(pattern) & mSelfCodepointSet);
407    if (re::matchesEmptyString(pattern)) {
408        matched.insert(mNullCodepointSet);
409    }
410    SetByLineNumberAccumulator accum(mExplicitCps, mNullCodepointSet);
411    CPUDriver driver("driver");
412    grep::InternalSearchEngine engine(driver);
413    engine.setRecordBreak(grep::GrepRecordBreakKind::LF);
414    engine.grepCodeGen(pattern, nullptr);
415    const unsigned bufSize = mStringOffsets[mExplicitCps.size()];
416    engine.doGrep(mStringBuffer, bufSize, accum);
417    matched.insert(accum.getAccumulatedSet());
418    return matched;
419}
420   
421const UnicodeSet StringPropertyObject::GetReflexiveSet() const {
422    return mSelfCodepointSet;
423}
424
425const std::string StringPropertyObject::GetStringValue(codepoint_t cp) const {
426    if (mNullCodepointSet.contains(cp)) return "";
427    if (mSelfCodepointSet.contains(cp)) {
428        std::u32string s(1, cp);
429        std::wstring_convert<std::codecvt_utf8<char32_t>, char32_t> conv;
430        return conv.to_bytes(s);
431    }
432    // Otherwise, binary search through the explicit cps to find the index.
433    // string index.
434    unsigned lo = 0;
435    unsigned hi = mExplicitCps.size()-1;
436    while (lo < hi) {
437        unsigned mid = (lo + hi)/2;
438        if (cp <= mExplicitCps[mid]) hi = mid;
439        else lo = mid + 1;
440    }
441    // Now lo == hi is the index of the desired string.
442    unsigned offset = mStringOffsets[lo];
443    unsigned lgth = mStringOffsets[lo+1] - offset - 1;
444    return std::string(&mStringBuffer[offset], lgth);
445}
446
447const UnicodeSet StringOverridePropertyObject::GetCodepointSet(const std::string & value_spec) {
448    // First step: get the codepoints from the base object and then remove any overridden ones.
449    UnicodeSet result_set = mBaseObject.GetCodepointSet(value_spec) - mOverriddenSet;
450    // Now search for additional entries.
451    unsigned val_bytes = value_spec.length();
452    const char * value_str = value_spec.c_str();
453    const char * search_str = mStringBuffer;
454    unsigned buffer_line = 0;
455    while (buffer_line < mExplicitCps.size()) {
456        const char * eol = strchr(search_str, '\n');
457        unsigned len = eol - search_str;
458        if ((len == val_bytes) && (memcmp(search_str, value_str, len) == 0)) {
459            result_set.insert(mExplicitCps[buffer_line]);
460        }
461        buffer_line++;
462        search_str = eol+1;
463    }
464    return result_set;
465}
466   
467   
468const UnicodeSet StringOverridePropertyObject::GetCodepointSetMatchingPattern(re::RE * pattern) {
469    UnicodeSet base_set = mBaseObject.GetCodepointSetMatchingPattern(pattern) - mOverriddenSet;
470    SetByLineNumberAccumulator accum(mExplicitCps, UnicodeSet());
471    CPUDriver driver("driver");
472    grep::InternalSearchEngine engine(driver);
473    engine.setRecordBreak(grep::GrepRecordBreakKind::LF);
474    engine.grepCodeGen(pattern, nullptr);
475    const unsigned bufSize = mStringOffsets[mExplicitCps.size()];
476    engine.doGrep(mStringBuffer, bufSize, accum);
477    base_set.insert(accum.getAccumulatedSet());
478    return base_set;
479}
480
481const UnicodeSet StringOverridePropertyObject::GetReflexiveSet() const {
482    return mBaseObject.GetReflexiveSet() - mOverriddenSet;
483}
484
485const std::string StringOverridePropertyObject::GetStringValue(codepoint_t cp) const {
486    if (!mOverriddenSet.contains(cp)) return mBaseObject.GetStringValue(cp);
487    // Otherwise, binary search through the explicit cps to find the index.
488    // string index.
489    unsigned lo = 0;
490    unsigned hi = mExplicitCps.size()-1;
491    while (lo < hi) {
492        unsigned mid = (lo + hi)/2;
493        if (cp <= mExplicitCps[mid]) hi = mid;
494        else lo = mid + 1;
495    }
496    // Now lo == hi is the index of the desired string.
497    unsigned offset = mStringOffsets[lo];
498    unsigned lgth = mStringOffsets[lo+1] - offset - 1;
499    return std::string(&mStringBuffer[offset], lgth);
500}
501
502const std::string & ObsoletePropertyObject::GetPropertyValueGrepString() {
503    llvm::report_fatal_error("Property " + UCD::property_full_name[the_property] + " is obsolete.");
504}
505
506const UnicodeSet ObsoletePropertyObject::GetCodepointSet(const std::string &) {
507    llvm::report_fatal_error("Property " + UCD::property_full_name[the_property] + " is obsolete.");
508}
509
510
511}
Note: See TracBrowser for help on using the repository browser.