source: icGREP/icgrep-devel/icgrep/UCD/unicode_set.cpp @ 5672

Last change on this file since 5672 was 5646, checked in by nmedfort, 2 years ago

Minor clean up. Bug fix for object cache when the same cached kernel is used twice in a single run. Improvement to RE Minimizer.

File size: 36.2 KB
Line 
1//
2// unicode_set.cpp - representing and manipulating sets of Unicode
3// characters, based on data from UCD - the Unicode Character Database
4//
5// Robert D. Cameron
6// September 18, 2014
7//
8// Licensed under Open Software License 3.0.
9//
10// Unicode Sparse Bitset Representation
11//
12// The Unicode Sparse Bitset representation is based on
13// (a) Dividing the Unicode codepoint space into groups of 2^k codepoints called quads.
14// (b) Specifying the quads using a run-length encoding, in which each run
15//     is Empty (quads contain no members), Mixed (quads contain some members and
16//     some nonmembers) or Full (all codepoints in each quad are members of the set).
17// (c) Explicitly listing all the quads of Mixed type.
18//
19
20#include "unicode_set.h"
21#include "assert.h"
22#include <string>
23#include <llvm/Support/raw_ostream.h>
24#include <llvm/Support/Format.h>
25
26namespace UCD {
27
28using bitquad_t = UnicodeSet::bitquad_t;
29using run_t = UnicodeSet::run_t;
30using interval_t = UnicodeSet::interval_t;
31
32//
33// Select the correct built-in scan function, dependent on whatever
34// bitquad_t resolves to, when scan_forwrad_zeroes<bitquad_t> is called.
35template <typename T> int scan_forward_zeroes(T x);
36template <> inline int scan_forward_zeroes<unsigned int>(unsigned int x){return __builtin_ctz(x);}
37template <> inline int scan_forward_zeroes<unsigned long>(unsigned long x){return __builtin_ctzl(x);}
38template <> inline int scan_forward_zeroes<unsigned long long>(unsigned long long x){return __builtin_ctzll(x);}
39
40SlabAllocator<> UnicodeSet::mAllocator;
41
42const uint64_t QUAD_BITS = (8 * sizeof(bitquad_t));
43const uint64_t MOD_QUAD_BIT_MASK = QUAD_BITS - 1;
44const uint64_t UNICODE_QUAD_COUNT = (UNICODE_MAX + 1) / QUAD_BITS;
45const bitquad_t FULL_QUAD_MASK = -1;
46
47inline run_type_t typeOf(const run_t & run) {
48    return run.first;
49}
50
51inline UnicodeSet::length_t lengthOf(const run_t & run) {
52    return run.second;
53}
54
55/** ------------------------------------------------------------------------------------------------------------- *
56 * @brief append_run
57 ** ------------------------------------------------------------------------------------------------------------- */
58template <class RunVector>
59inline void append_run(const run_type_t type, const unsigned length, RunVector & runs) {
60    if (LLVM_UNLIKELY(length == 0)) {
61        return;
62    } else if (!runs.empty() && typeOf(runs.back()) == type) {
63        std::get<1>(runs.back()) += length;
64        return;
65    }
66    runs.emplace_back(type, length);
67}
68
69/** ------------------------------------------------------------------------------------------------------------- *
70 * @brief append_quad
71 ** ------------------------------------------------------------------------------------------------------------- */
72template <class QuadVector, class RunVector>
73inline void append_quad(const bitquad_t quad, QuadVector & quads, RunVector & runs) {
74    run_type_t type = Empty;
75    if (LLVM_UNLIKELY(quad == 0)) {
76        type = Empty;
77    } else if (LLVM_UNLIKELY(quad == FULL_QUAD_MASK)) {
78        type = Full;
79    } else {
80        quads.emplace_back(quad);
81        type = Mixed;
82    }
83    append_run(type, 1, runs);
84}
85
86#ifndef NDEBUG
87/** ------------------------------------------------------------------------------------------------------------- *
88 * @brief verify
89 *
90 * Sanity check for each function that constructs or modifies a UnicodeSet
91 ** ------------------------------------------------------------------------------------------------------------- */
92template <class RunVector, class QuadVector>
93inline bool verify(const RunVector & runs, const QuadVector & quads) {
94    unsigned sum = 0;
95    unsigned mixedQuads = 0;
96    for (auto run : runs) {
97        const auto l = lengthOf(run);
98        if (l == 0) {
99            throw std::runtime_error("Zero-length quad found!");
100        }
101        if (typeOf(run) == Mixed) {
102            mixedQuads += l;
103        }
104        sum += l;
105    }
106    if (sum != UNICODE_QUAD_COUNT) {
107        throw std::runtime_error("Invalid quad count: found " + std::to_string(sum) + " but expected " + std::to_string(UNICODE_QUAD_COUNT));
108    }
109    if (mixedQuads != quads.size()) {
110        throw std::runtime_error("Invalid mixed quad count: found " + std::to_string(quads.size()) + " but expected " + std::to_string(mixedQuads));
111    }
112    for (auto quad : quads) {
113        if (quad == 0) {
114            throw std::runtime_error("Empty quad found in Mixed quad array!");
115        } else if (quad == FULL_QUAD_MASK) {
116            throw std::runtime_error("Full quad found in Mixed quad array!");
117        }
118    }
119    return true;
120}
121#endif
122
123/** ------------------------------------------------------------------------------------------------------------- *
124 * @brief empty
125 ** ------------------------------------------------------------------------------------------------------------- */
126bool UnicodeSet::empty() const {
127    return (mRuns.size() == 1) && typeOf(mRuns.front()) == Empty;
128}
129
130/** ------------------------------------------------------------------------------------------------------------- *
131 * @brief size
132 ** ------------------------------------------------------------------------------------------------------------- */
133UnicodeSet::size_type UnicodeSet::size() const {
134    return std::distance(begin(), end());
135}
136
137/** ------------------------------------------------------------------------------------------------------------- *
138 * @brief front
139 ** ------------------------------------------------------------------------------------------------------------- */
140UnicodeSet::interval_t UnicodeSet::front() const {
141    return *begin();
142}
143
144/** ------------------------------------------------------------------------------------------------------------- *
145 * @brief back
146 ** ------------------------------------------------------------------------------------------------------------- */
147UnicodeSet::interval_t UnicodeSet::back() const {
148    auto back = begin();
149    for (auto i = back; i != end(); back = i++);
150    return *back;
151}
152
153/** ------------------------------------------------------------------------------------------------------------- *
154 * @brief print
155 ** ------------------------------------------------------------------------------------------------------------- */
156void UnicodeSet::print(llvm::raw_ostream & out) const {
157    if (LLVM_UNLIKELY(empty())) {
158        out << "()";
159    } else {
160        char joiner = '(';
161        for (auto r : *this) {
162            out << joiner << std::get<0>(r);
163            if (std::get<0>(r) != std::get<1>(r)) {
164                out << '-' << std::get<1>(r);
165            }
166            joiner = ',';
167        }
168        out << ')';
169
170    }
171}
172
173/** ------------------------------------------------------------------------------------------------------------- *
174 * @brief dump
175 ** ------------------------------------------------------------------------------------------------------------- */
176void UnicodeSet::dump(llvm::raw_ostream & out) const {
177    auto qi = mQuads.cbegin();
178    for (const run_t & run : mRuns) {
179        if (typeOf(run) == Empty) {
180            out << "Empty(" << lengthOf(run) << ")\n";
181        }
182        else if (typeOf(run) == Full) {
183            out << "Full(" << lengthOf(run) << ")\n";
184        }
185        else {
186            for (const auto qi_end = qi + lengthOf(run); qi != qi_end; ++qi) {
187                assert (qi != mQuads.cend());
188                out << "Mixed(" << llvm::format("%08x", *qi) << ")\n";
189            }
190        }
191    }
192}
193
194/** ------------------------------------------------------------------------------------------------------------- *
195 * @brief complement
196 ** ------------------------------------------------------------------------------------------------------------- */
197UnicodeSet UnicodeSet::operator~() const {
198    std::vector<run_t> runs;
199    std::vector<bitquad_t> quads;
200    runs.reserve(mRuns.size());
201    quads.reserve(mQuads.size());
202    auto qi = quads.cbegin();
203    for (const run_t & run : mRuns) {
204        if (typeOf(run) == Empty) {
205            append_run(Full, lengthOf(run), runs);
206        }
207        else if (typeOf(run) == Full) {
208            append_run(Empty, lengthOf(run), runs);
209        }
210        else {
211            for (const auto qi_end = qi + lengthOf(run); qi != qi_end; ++qi) {
212                assert (qi != quads.cend());
213                append_quad(FULL_QUAD_MASK ^ *qi, quads, runs);
214            }
215        }
216    }
217    return UnicodeSet(std::move(runs), std::move(quads));
218}
219
220/** ------------------------------------------------------------------------------------------------------------- *
221 * @brief intersection
222 ** ------------------------------------------------------------------------------------------------------------- */
223UnicodeSet UnicodeSet::operator&(const UnicodeSet & other) const {
224    std::vector<run_t> runs;
225    std::vector<bitquad_t> quads;
226    const auto e1 = quad_end();
227    const auto e2 = other.quad_end();
228    for (auto i1 = quad_begin(), i2 = other.quad_begin(); i1 != e1 && i2 != e2; ) {
229        const auto n = std::min(i1.length(), i2.length());
230        if ((i1.type() == Full) && (i2.type() == Full)) {
231            append_run(Full, n, runs);
232            i1 += n;
233            i2 += n;
234        }
235        else if ((i1.type() == Empty) || (i2.type() == Empty)) {
236            append_run(Empty, n, runs);
237            i1 += n;
238            i2 += n;
239        }
240        else if (i1.type() == Full) {
241            for (unsigned i = 0; i != n; ++i, ++i2) {
242                append_quad(i2.quad(), quads, runs);
243            }
244            i1 += n;
245        }
246        else if (i2.type() == Full) {
247            for (unsigned i = 0; i != n; ++i, ++i1) {
248                append_quad(i1.quad(), quads, runs);
249            }
250            i2 += n;
251        }
252        else { //both Mixed
253            for (unsigned i = 0; i != n; ++i, ++i1, ++i2) {
254                append_quad(i1.quad() & i2.quad(), quads, runs);
255            }
256        }
257    }
258    return UnicodeSet(std::move(runs), std::move(quads));
259}
260
261/** ------------------------------------------------------------------------------------------------------------- *
262 * @brief union
263 ** ------------------------------------------------------------------------------------------------------------- */
264UnicodeSet UnicodeSet::operator+(const UnicodeSet & other) const {
265    std::vector<run_t> runs;
266    std::vector<bitquad_t> quads;
267    const auto e1 = quad_end();
268    const auto e2 = other.quad_end();
269    auto i1 = quad_begin(), i2 = other.quad_begin();
270    for (; i1 != e1 && i2 != e2; ) {
271        const auto n = std::min(i1.length(), i2.length());
272        if ((i1.type() == Empty) && (i2.type() == Empty)) {
273            append_run(Empty, n, runs);
274            i1 += n;
275            i2 += n;
276        } else if ((i1.type() == Full) || (i2.type() == Full)) {
277            append_run(Full, n, runs);
278            i1 += n;
279            i2 += n;
280        } else if (i1.type() == Empty) {
281            for (unsigned i = 0; i != n; ++i, ++i2) {
282                append_quad(i2.quad(), quads, runs);
283            }
284            i1 += n;
285        } else if (i2.type() == Empty) {
286            for (unsigned i = 0; i != n; ++i, ++i1) {
287                append_quad(i1.quad(), quads, runs);
288            }
289            i2 += n;
290        } else {
291            for (unsigned i = 0; i < n; ++i, ++i1, ++i2) {
292                append_quad(i1.quad() | i2.quad(), quads, runs);
293            }
294        }
295    }
296    return UnicodeSet(std::move(runs), std::move(quads));
297}
298
299/** ------------------------------------------------------------------------------------------------------------- *
300 * @brief difference
301 ** ------------------------------------------------------------------------------------------------------------- */
302UnicodeSet UnicodeSet::operator-(const UnicodeSet & other) const {
303    std::vector<run_t> runs;
304    std::vector<bitquad_t> quads;
305    const auto e1 = quad_end();
306    const auto e2 = other.quad_end();
307    for (auto i1 = quad_begin(), i2 = other.quad_begin(); i1 != e1 && i2 != e2; ) {
308        unsigned n = std::min(i1.length(), i2.length());
309        if ((i1.type() == Empty) || (i2.type() == Full) || (i1.type() == Full && i2.type() == Empty)) {
310            append_run(i1.type(), n, runs);
311            i1 += n;
312            i2 += n;
313        }
314        else if (i1.type() == Full) {
315            for (unsigned i = 0; i != n; ++i, ++i2) {
316                append_quad(FULL_QUAD_MASK ^ i2.quad(), quads, runs);
317            }
318            i1 += n;
319        }
320        else if (i2.type() == Empty) {
321            for (unsigned i = 0; i != n; ++i, ++i1) {
322                append_quad(i1.quad(), quads, runs);
323            }
324            i2 += n;
325        }
326        else {
327            for (unsigned i = 0; i != n; ++i, ++i1, ++i2) {
328                append_quad(i1.quad() &~ i2.quad(), quads, runs);
329            }
330        }
331    }
332    return UnicodeSet(std::move(runs), std::move(quads));
333}
334
335/** ------------------------------------------------------------------------------------------------------------- *
336 * @brief symmetric difference
337 ** ------------------------------------------------------------------------------------------------------------- */
338UnicodeSet UnicodeSet::operator^(const UnicodeSet & other) const {
339    std::vector<run_t> runs;
340    std::vector<bitquad_t> quads;
341    const auto e1 = quad_end();
342    const auto e2 = other.quad_end();
343    for (auto i1 = quad_begin(), i2 = other.quad_begin(); i1 != e1 && i2 != e2; ) {
344        unsigned n = std::min(i1.length(), i2.length());
345        if (i1.type() != Mixed && i2.type() != Mixed) {
346            append_run(i1.type() == i2.type() ? Empty : Full, n, runs);
347            i1 += n;
348            i2 += n;
349        } else if (i1.type() == Empty) {
350            for (unsigned i = 0; i < n; ++i, ++i2) {
351                append_quad(i2.quad(), quads, runs);
352            }
353            i1 += n;
354        } else if (i2.type() == Empty) {
355            for (unsigned i = 0; i < n; ++i, ++i1) {
356                append_quad(i1.quad(), quads, runs);
357            }
358            i2 += n;
359        } else if (i1.type() == Full) {
360            for (unsigned i = 0; i < n; ++i, ++i2) {
361                append_quad(FULL_QUAD_MASK ^ i2.quad(), quads, runs);
362            }
363            i1 += n;
364        } else if (i2.type() == Full) {
365            for (unsigned i = 0; i < n; ++i, ++i1) {
366                append_quad(FULL_QUAD_MASK ^ i1.quad(), quads, runs);
367            }
368            i2 += n;
369        } else {
370            for (unsigned i = 0; i != n; ++i, ++i1, ++i2) {
371                append_quad(i1.quad() ^ i2.quad(), quads, runs);
372            }
373        }
374    }
375    return UnicodeSet(std::move(runs), std::move(quads));
376}
377
378/** ------------------------------------------------------------------------------------------------------------- *
379 * @brief equality
380 ** ------------------------------------------------------------------------------------------------------------- */
381bool UnicodeSet::operator==(const UnicodeSet & other) const {
382    if (mRuns.size() != other.mRuns.size() || mQuads.size() != other.mQuads.size()) {
383        return false;
384    }
385    for (auto i = mQuads.begin(), j = other.mQuads.begin(); i != mQuads.end(); ++i, ++j) {
386        if (*i != *j) return false;
387    }
388    for (auto i = mRuns.begin(), j = other.mRuns.begin(); i != mRuns.end(); ++i, ++j) {
389        if (*i != *j) return false;
390    }
391    return true;
392}
393
394/** ------------------------------------------------------------------------------------------------------------- *
395 * @brief less operator
396 ** ------------------------------------------------------------------------------------------------------------- */
397bool UnicodeSet::operator<(const UnicodeSet & other) const {
398    if (LLVM_LIKELY(mRuns.size() != other.mRuns.size())) {
399        return mRuns.size() < other.mRuns.size();
400    } else if (LLVM_LIKELY(mQuads.size() != other.mQuads.size())) {
401        return (mQuads.size() < other.mQuads.size());
402    } else { // equal run and quad lengths; test their individual values
403        for (auto ri = mRuns.cbegin(), end = mRuns.cend(), rj = other.mRuns.cbegin(); ri != end; ++ri, ++rj) {
404            if (*ri < *rj) {
405                return true;
406            } else if (*ri > *rj) {
407                return false;
408            }
409        }
410        for (auto qi = mQuads.cbegin(), end = mQuads.cend(), qj = other.mQuads.cbegin(); qi != end; ++qi, ++qj) {
411            if (*qi < *qj) {
412                return true;
413            } else if (*qi > *qj) {
414                return false;
415            }
416        }
417        return false;
418    }
419}
420
421/** ------------------------------------------------------------------------------------------------------------- *
422 * @brief insert
423 ** ------------------------------------------------------------------------------------------------------------- */
424void UnicodeSet::insert(const codepoint_t cp) {
425
426    if (LLVM_UNLIKELY(cp >= UNICODE_MAX)) {
427        throw std::runtime_error(std::to_string(cp) + " exceeds maximum code point.");
428    }
429
430    codepoint_t offset = cp / QUAD_BITS;
431    const bitquad_t value = static_cast<bitquad_t>(1) << (cp & MOD_QUAD_BIT_MASK);
432    auto run = mRuns.begin();
433    auto quad = mQuads.begin();
434    length_t l = 0;
435    run_type_t t = Empty;
436    for (;;) {
437        std::tie(t, l) = *run;
438        if (offset < l) {
439            break;
440        }
441        if (t == Mixed) {
442            quad += l;
443        }
444        offset -= l;
445        ++run;
446    }
447    if (LLVM_LIKELY(t == Mixed)) {
448        quad += offset;
449        *quad |= value;
450        if (LLVM_LIKELY(*quad != FULL_QUAD_MASK)) {
451            assert (contains(cp));
452            return;
453        }
454        mQuads.erase(quad);
455    } else if (t == Empty) {
456        mQuads.insert(quad, value);
457    } else { // if (t == Full) {
458        assert (contains(cp));
459        return;
460    }
461    const unsigned remaining = l - (offset + 1);
462    if (offset == 0) {
463        *run = std::make_pair(t == Empty ? Mixed : Full, 1);
464        if (remaining != 0) {
465            mRuns.insert(++run, std::make_pair(t, remaining));
466        }
467    } else {
468        run->second = offset;
469        if (remaining == 0) {
470            mRuns.insert(++run, std::make_pair(t == Empty ? Mixed : Full, 1));
471        } else {
472            mRuns.insert(++run, {std::make_pair(t == Empty ? Mixed : Full, 1), std::make_pair(t, remaining)});
473        }
474    }
475
476    assert (verify(mRuns, mQuads));
477    assert (contains(cp));
478}
479
480/** ------------------------------------------------------------------------------------------------------------- *
481 * @brief insert_range
482 ** ------------------------------------------------------------------------------------------------------------- */
483void UnicodeSet::insert_range(const codepoint_t lo, const codepoint_t hi)  {
484
485    if (LLVM_UNLIKELY(lo > hi)) {
486        throw std::runtime_error('[' + std::to_string(lo) + ',' + std::to_string(hi) + "] is an illegal codepoint range!");
487    } else if (LLVM_UNLIKELY(hi > UNICODE_MAX)) {
488        throw std::runtime_error(std::to_string(hi) + " exceeds maximum code point.");
489    }
490
491    // Create a temporary run and quad set for the given range
492    std::vector<run_t> runs;
493    std::vector<bitquad_t> quads;
494
495    codepoint_t lo_index = lo / QUAD_BITS;
496    codepoint_t hi_index = hi / QUAD_BITS;
497
498    auto ri = mRuns.cbegin();
499    auto qi = mQuads.cbegin();
500
501    codepoint_t length = 0;
502    run_type_t type = Empty;
503
504    // Advance past any runs prior to the lo_index
505    for (;;) {
506        assert (ri != mRuns.cend());
507        std::tie(type, length) = *ri;       
508        if (lo_index < length) {
509            break;
510        }
511        if (type == Mixed) {
512            assert (std::distance(qi, mQuads.cend()) >= length);
513            qi += length;
514        }
515        lo_index -= length;
516        hi_index -= length;
517        ++ri;
518    }
519
520    // Now record the runs and any quads prior to lo_index
521    runs.assign(mRuns.cbegin(), ri++);
522    if (lo_index) {
523        runs.emplace_back(type, lo_index);
524        if (type == Mixed) {
525            assert (static_cast<codepoint_t>(std::distance(qi, mQuads.cend())) >= lo_index);
526            qi += lo_index;
527        }
528        hi_index -= lo_index;
529        length -= lo_index;
530    }
531
532    quads.assign(mQuads.cbegin(), qi);
533    // We now have everything up to the first quad added to our temporary buffers; merge in the first new quad.
534    bitquad_t lo_quad = (FULL_QUAD_MASK << (lo & MOD_QUAD_BIT_MASK));
535    bitquad_t hi_quad = (FULL_QUAD_MASK >> (QUAD_BITS - 1 - (hi & MOD_QUAD_BIT_MASK)));
536
537    // If our original quad is full, just append a Full run
538    if (LLVM_UNLIKELY(type == Full)) {
539        append_run(Full, 1, runs);
540    } else { // Otherwise merge the new quad value with the original one
541        if (hi_index == 0) {
542            lo_quad &= hi_quad;
543        }
544        if (type == Mixed) {
545            assert (std::distance(qi, mQuads.cend()) > 0);
546            lo_quad |= *qi++;
547        }
548        append_quad(lo_quad, quads, runs);
549    }
550    --length;
551
552    // Now check if we need to write out any Full blocks between the lo and hi code points; adjust our position
553    // in the original quad to suit.
554    if (hi_index) {
555        // Add in any full runs between the lo and hi quads
556        append_run(Full, hi_index - 1, runs);
557        // Advance past original quads that were filled in
558        while (ri != mRuns.cend()) {
559            if (type == Mixed) {
560                assert (std::distance(qi, mQuads.cend()) >= length);
561                qi += length;
562            }
563            std::tie(type, length) = *ri++;
564            if (hi_index < length) {
565                break;
566            }
567            hi_index -= length;
568            length = 0;
569        }       
570        // Write out the hi_quad value
571        if (LLVM_UNLIKELY(type == Full)) {
572            append_run(Full, 1, runs);
573        } else {
574            if (type == Mixed) {
575                assert (static_cast<codepoint_t>(std::distance(qi, mQuads.cend())) > hi_index);
576                qi += hi_index;
577                hi_quad |= *qi++;
578            }
579            append_quad(hi_quad, quads, runs);
580        }
581    }
582
583    // And append any remaining values from the original data
584    assert (length >= hi_index);
585    append_run(type, length - hi_index, runs);
586    assert ("We wrote all the runs but still have remaining quads?" && (ri != mRuns.cend() || qi == mQuads.cend()));
587    runs.insert(runs.end(), ri, mRuns.cend());
588    quads.insert(quads.end(), qi, mQuads.cend());
589    assert (verify(runs, quads));
590    mRuns.assign(runs.cbegin(), runs.cend());
591    mQuads.assign(quads.cbegin(), quads.cend());   
592}
593
594/** ------------------------------------------------------------------------------------------------------------- *
595 * @brief contains
596 * @param codepoint
597 *
598 * Return whether this UnicodeSet contains the specified code point
599 ** ------------------------------------------------------------------------------------------------------------- */
600bool UnicodeSet::contains(const codepoint_t cp) const {
601    codepoint_t offset = cp / QUAD_BITS;
602    auto quad = mQuads.cbegin();
603    for (const auto r : mRuns) {
604        length_t l = 0;
605        run_type_t t = Empty;
606        std::tie(t, l) = r;
607        if (offset < l) {
608            if (t == Mixed) {
609                quad += offset;
610                return (*quad & static_cast<bitquad_t>(1) << (cp & MOD_QUAD_BIT_MASK)) != 0;
611            }
612            return (t == Full);
613        }
614        if (t == Mixed) {
615            quad += l;
616        }       
617        offset -= l;
618    }
619    return false;
620}
621
622/** ------------------------------------------------------------------------------------------------------------- *
623 * @brief intersects
624 * @param lo_codepoint
625 * @param hi_codepoint
626 *
627 * Return true if this UnicodeSet contains any code point(s) between lo and hi (inclusive)
628 ** ------------------------------------------------------------------------------------------------------------- */
629bool UnicodeSet::intersects(const codepoint_t lo, const codepoint_t hi) const {
630    for (auto range : *this) {
631        if (range.second < lo) {
632            continue;
633        }
634        if (range.first > hi) {
635            break;
636        }
637        return true;
638    }
639    return false;
640}
641   
642   
643/** ------------------------------------------------------------------------------------------------------------- *
644 * @brief intersects
645 * @param other_set
646 *
647 * Return true if this UnicodeSet has a non-empty intersection with other_set
648 ** ------------------------------------------------------------------------------------------------------------- */
649bool UnicodeSet::intersects(const UnicodeSet & other) const {
650    const auto e1 = quad_end();
651    const auto e2 = other.quad_end();
652    for (auto i1 = quad_begin(), i2 = other.quad_begin(); i1 != e1 && i2 != e2; ) {
653        const auto n = std::min(i1.length(), i2.length());
654        if (i1.type() == Empty) {
655            i1 += i1.length();
656            i2 += i1.length();
657        }
658        else if (i2.type() == Empty) {
659            i1 += i2.length();
660            i2 += i2.length();
661        }
662        else if (i1.type() == Full) {
663            return false;
664        }
665        else if (i2.type() == Full) {
666            return false;
667        }
668        else { //both Mixed
669            for (unsigned i = 0; i != n; ++i, ++i1, ++i2) {
670                if ((i1.quad() & i2.quad()) != 0) return false;
671            }
672        }
673    }
674    return true;
675}
676
677
678/** ------------------------------------------------------------------------------------------------------------- *
679 * @brief UnicodeSet::quad_iterator::advance
680 ** ------------------------------------------------------------------------------------------------------------- */
681void UnicodeSet::quad_iterator::advance(unsigned n) {
682    while (n > 0) {
683        const unsigned remain = lengthOf(*mRunIterator) - mOffset;
684        if (remain > n) {
685            if (typeOf(*mRunIterator) == Mixed) {
686                mQuadIterator += n;
687            }
688            mOffset += n;
689            break;
690        }
691        if (typeOf(*mRunIterator) == Mixed) {
692            mQuadIterator += remain;
693        }
694        ++mRunIterator;
695        mOffset = 0;
696        n -= remain;
697    }
698}
699
700/** ------------------------------------------------------------------------------------------------------------- *
701 * @brief UnicodeSet::iterator::advance
702 ** ------------------------------------------------------------------------------------------------------------- */
703void UnicodeSet::iterator::advance(const unsigned n) {
704
705    assert (n == 1);
706
707    if (LLVM_UNLIKELY(mMinCodePoint >= 0x110000)) {
708        throw std::runtime_error("UnicodeSet iterator exceeded maximum code point.");
709    }
710
711    bool found = false;
712    // Find the start of our interval
713    while ( mBaseCodePoint < 0x110000 ) {
714        // Find the first non-empty block
715        if (typeOf(*mRunIterator) != Mixed) {           
716            // If we found a full run, this must be the start of our interval.
717            const auto baseCodePoint = mBaseCodePoint;
718            const auto type = typeOf(*mRunIterator);
719            mBaseCodePoint += lengthOf(*mRunIterator++) * QUAD_BITS;
720            if (type == Full) {
721                mMinCodePoint = baseCodePoint;
722                found = true;
723                break;
724            }
725        } else { // if (typeOf(t) == Mixed)
726            while (mMixedRunIndex != lengthOf(*mRunIterator)) {
727                const bitquad_t m = (*mQuadIterator) & (FULL_QUAD_MASK << mQuadOffset);
728                // If we found a marker in m, it marks the beginning of our current interval.
729                // Find it and break out of the loop.
730                if (m) {
731                    mQuadOffset = scan_forward_zeroes<bitquad_t>(m);
732                    mMinCodePoint = mBaseCodePoint + mQuadOffset;
733                    found = true;
734                    break;
735                }
736                mBaseCodePoint += QUAD_BITS;
737                ++mQuadIterator;
738                ++mMixedRunIndex;
739                mQuadOffset = 0;
740            }
741            if (found) break;
742            ++mRunIterator;
743            mQuadOffset = 0;
744            mMixedRunIndex = 0;
745        }
746    }
747
748    if (!found) {
749        assert (mBaseCodePoint == 0x110000);
750        mMinCodePoint = 0x110000;
751        return;
752    }
753
754    // at this stage, the max code point is the previous max code point (initially 0)
755    assert (mMaxCodePoint <= mMinCodePoint);
756    found = false;
757    // Find the end of our interval
758    while ( mBaseCodePoint < 0x110000 ) {
759
760        // Find the first non-Full block
761        if (typeOf(*mRunIterator) != Mixed) {
762            // If this run is Empty, the max code point is the last computed base code point - 1.
763            const auto baseCodePoint = mBaseCodePoint;
764            const auto type = typeOf(*mRunIterator);
765            mBaseCodePoint += lengthOf(*mRunIterator++) * QUAD_BITS;
766            if (type == Empty) {
767                mMaxCodePoint = baseCodePoint - 1;
768                found = true;
769                break;
770            }
771        } else { // if (typeOf(t) == Mixed)
772            while (mMixedRunIndex != lengthOf(*mRunIterator)) {
773                const bitquad_t m = ((~(*mQuadIterator)) & FULL_QUAD_MASK) & (FULL_QUAD_MASK << mQuadOffset);
774
775                // If we found a marker in m, it marks the end of our current interval.
776                // Find it and break out of the loop.
777                if (m) {
778                    mQuadOffset = scan_forward_zeroes<bitquad_t>(m);
779                    mMaxCodePoint = mBaseCodePoint + mQuadOffset - 1;
780                    found = true;
781                    break;
782                }
783                mBaseCodePoint += QUAD_BITS;
784                ++mQuadIterator;
785                ++mMixedRunIndex;
786                mQuadOffset = 0;
787            }
788            if (found) break;
789            ++mRunIterator;
790            mQuadOffset = 0;
791            mMixedRunIndex = 0;
792        }
793    }
794    // if the very last block is a mixed block and we go past it, the last code point of the range is 0x10FFFF
795    if (!found) {
796        assert (mBaseCodePoint == 0x110000);
797        mMaxCodePoint = 0x10FFFF;
798    }
799
800    assert (mMinCodePoint <= mMaxCodePoint);
801}
802
803/** ------------------------------------------------------------------------------------------------------------- *
804 * @brief Empty Set Constructor
805 ** ------------------------------------------------------------------------------------------------------------- */
806UnicodeSet::UnicodeSet()
807: mRuns(mAllocator)
808, mQuads(mAllocator)
809{
810    append_run(Empty, UNICODE_QUAD_COUNT, mRuns);
811    assert (verify(mRuns, mQuads));
812}
813
814/** ------------------------------------------------------------------------------------------------------------- *
815 * @brief Singleton Set Constructor
816 ** ------------------------------------------------------------------------------------------------------------- */
817UnicodeSet::UnicodeSet(const codepoint_t codepoint)
818: mRuns(mAllocator)
819, mQuads(mAllocator)
820{
821    const codepoint_t quad_no = codepoint / QUAD_BITS;
822    append_run(Empty, quad_no, mRuns);
823    append_quad(static_cast<bitquad_t>(1) << (codepoint & MOD_QUAD_BIT_MASK), mQuads, mRuns);
824    append_run(Empty, UNICODE_QUAD_COUNT - (quad_no + 1), mRuns);
825    assert (verify(mRuns, mQuads));
826}
827
828/** ------------------------------------------------------------------------------------------------------------- *
829 * @brief Range Set Constructor
830 ** ------------------------------------------------------------------------------------------------------------- */
831UnicodeSet::UnicodeSet(const codepoint_t lo, const codepoint_t hi)
832: mRuns(mAllocator)
833, mQuads(mAllocator)
834{
835    const codepoint_t lo_index = lo / QUAD_BITS;
836    const codepoint_t hi_index = hi / QUAD_BITS;
837    const codepoint_t lo_offset = lo & MOD_QUAD_BIT_MASK;
838    const codepoint_t hi_offset = hi & MOD_QUAD_BIT_MASK;
839    const bitquad_t lo_quad = (FULL_QUAD_MASK << lo_offset);
840    const bitquad_t hi_quad = (FULL_QUAD_MASK >> (QUAD_BITS - 1 - hi_offset));
841    append_run(Empty, lo_index, mRuns);
842    bitquad_t mask = hi_quad;
843    if (lo_index == hi_index) {
844        mask &= lo_quad;
845    } else {
846        append_quad(lo_quad, mQuads, mRuns);
847        append_run(Full, hi_index - (lo_index + 1), mRuns);
848    }
849    append_quad(mask, mQuads, mRuns);
850    append_run(Empty, UNICODE_QUAD_COUNT - (hi_index + 1), mRuns);
851    assert (verify(mRuns, mQuads));
852}
853
854/** ------------------------------------------------------------------------------------------------------------- *
855 * @brief Range List Set Constructor
856 ** ------------------------------------------------------------------------------------------------------------- */
857template <typename itr>
858void convertIntervalRangesToSparseSet(const itr begin, const itr end, UnicodeSet::RunVector & mRuns, UnicodeSet::QuadVector & mQuads) {
859    assert (std::is_sorted(begin, end, [](const interval_t l, const interval_t r) {
860        assert (l.first <= l.second);
861        assert (l.second < UNICODE_MAX);
862        assert (r.first <= r.second);
863        assert (r.second < UNICODE_MAX);
864        return l.second < r.first;
865    }));
866
867    std::vector<run_t> runs;
868    std::vector<bitquad_t> quads;
869
870    codepoint_t prior_index = 0;
871    bitquad_t mask = 0;
872    for (auto interval = begin; interval != end; ) {
873        codepoint_t lo, hi;
874        std::tie(lo, hi) = *interval;
875        const codepoint_t lo_index = (lo / QUAD_BITS);
876        const codepoint_t hi_index = (hi / QUAD_BITS);
877        const codepoint_t lo_offset = lo & MOD_QUAD_BIT_MASK;
878        const codepoint_t hi_offset = hi & MOD_QUAD_BIT_MASK;
879        const bitquad_t lo_quad = (FULL_QUAD_MASK << lo_offset);
880        const bitquad_t hi_quad = (FULL_QUAD_MASK >> (QUAD_BITS - 1 - hi_offset));
881        append_run(Empty, lo_index - prior_index, runs);
882        if (lo_index == hi_index) {
883            mask |= (lo_quad & hi_quad);
884        } else {
885            append_quad(mask | lo_quad, quads, runs);
886            append_run(Full, hi_index - (lo_index + 1), runs);
887            mask = hi_quad;
888        }
889        // if the next interval is in our current quad, continue to the next range
890        prior_index = hi_index;
891        if (LLVM_LIKELY(++interval != end)) {
892            if (hi_index == (interval->first / QUAD_BITS)) {
893                continue;
894            }
895        }
896        append_quad(mask, quads, runs);
897        mask = 0;
898        ++prior_index;
899    }
900    assert (mask == 0);
901    if (prior_index < UNICODE_QUAD_COUNT) {
902        append_run(Empty, UNICODE_QUAD_COUNT - prior_index, runs);
903    }   
904    assert (verify(runs, quads));
905    mRuns.assign(runs.begin(), runs.end());
906    mQuads.assign(quads.begin(), quads.end());
907}
908
909/** ------------------------------------------------------------------------------------------------------------- *
910 * @brief Interval Range Constructor
911 ** ------------------------------------------------------------------------------------------------------------- */
912UnicodeSet::UnicodeSet(std::initializer_list<interval_t>::iterator begin, std::initializer_list<interval_t>::iterator end)
913: mRuns(0, {Empty, 0}, mAllocator)
914, mQuads(0, 0, mAllocator) {
915    convertIntervalRangesToSparseSet(begin, end, mRuns, mQuads);
916}
917
918/** ------------------------------------------------------------------------------------------------------------- *
919 * @brief Interval Range Constructor
920 ** ------------------------------------------------------------------------------------------------------------- */
921UnicodeSet::UnicodeSet(const std::vector<interval_t>::iterator begin, const std::vector<interval_t>::iterator end)
922: mRuns(0, {Empty, 0}, mAllocator)
923, mQuads(0, 0, mAllocator) {
924    convertIntervalRangesToSparseSet(begin, end, mRuns, mQuads);
925}
926
927/** ------------------------------------------------------------------------------------------------------------- *
928 * @brief Copy Constructor
929 ** ------------------------------------------------------------------------------------------------------------- */
930UnicodeSet::UnicodeSet(const UnicodeSet & other)
931: mRuns(other.mRuns, mAllocator)
932, mQuads(other.mQuads, mAllocator) {
933    assert (verify(mRuns, mQuads));
934}
935
936/** ------------------------------------------------------------------------------------------------------------- *
937 * @brief Initializer Constructor
938 ** ------------------------------------------------------------------------------------------------------------- */
939UnicodeSet::UnicodeSet(std::initializer_list<run_t> r, std::initializer_list<bitquad_t> q)
940: mRuns(r.begin(), r.end(), mAllocator)
941, mQuads(q.begin(), q.end(), mAllocator) {
942    assert (verify(mRuns, mQuads));
943}
944
945/** ------------------------------------------------------------------------------------------------------------- *
946 * @brief Internal Vector Constructor
947 ** ------------------------------------------------------------------------------------------------------------- */
948inline UnicodeSet::UnicodeSet(std::vector<run_t> && r, std::vector<bitquad_t> && q)
949: mRuns(r.begin(), r.end(), mAllocator)
950, mQuads(q.begin(), q.end(), mAllocator) {
951    assert (verify(mRuns, mQuads));
952}
953
954}
Note: See TracBrowser for help on using the repository browser.