Changeset 5632


Ignore:
Timestamp:
Sep 8, 2017, 9:57:59 AM (2 weeks ago)
Author:
cameron
Message:

Optimizations for re_local

Location:
icGREP/icgrep-devel/icgrep
Files:
4 edited

Legend:

Unmodified
Added
Removed
  • icGREP/icgrep-devel/icgrep/UCD/unicode_set.cpp

    r5620 r5632  
    653653    return false;
    654654}
     655   
     656   
     657/** ------------------------------------------------------------------------------------------------------------- *
     658 * @brief intersects
     659 * @param other_set
     660 *
     661 * Return true if this UnicodeSet has a non-empty intersection with other_set
     662 ** ------------------------------------------------------------------------------------------------------------- */
     663bool UnicodeSet::intersects(const UnicodeSet & other) const {
     664    std::vector<run_t> runs;
     665    std::vector<bitquad_t> quads;
     666    const auto e1 = quad_end();
     667    const auto e2 = other.quad_end();
     668    for (auto i1 = quad_begin(), i2 = other.quad_begin(); i1 != e1 && i2 != e2; ) {
     669        const auto n = std::min(i1.length(), i2.length());
     670        if (i1.type() == Empty) {
     671            i1 += i1.length();
     672            i2 += i1.length();
     673        }
     674        else if (i2.type() == Empty) {
     675            i1 += i2.length();
     676            i2 += i2.length();
     677        }
     678        else if (i1.type() == Full) {
     679            return false;
     680        }
     681        else if (i2.type() == Full) {
     682            return false;
     683        }
     684        else { //both Mixed
     685            for (unsigned i = 0; i != n; ++i, ++i1, ++i2) {
     686                if ((i1.quad() & i2.quad()) != 0) return false;
     687            }
     688        }
     689    }
     690    return true;
     691}
     692
    655693
    656694/** ------------------------------------------------------------------------------------------------------------- *
  • icGREP/icgrep-devel/icgrep/UCD/unicode_set.h

    r5620 r5632  
    106106
    107107    bool intersects(const codepoint_t lo, const codepoint_t hi) const;
    108 
     108   
     109    bool intersects(const UnicodeSet & other) const;
     110   
    109111    void insert(const codepoint_t cp);
    110112
  • icGREP/icgrep-devel/icgrep/re/re_local.cpp

    r5620 r5632  
    155155
    156156bool RE_Local::isLocalLanguage(RE * re) {
    157     std::vector<UCD::UnicodeSet> UnicodeSets;
    158     collect_UnicodeSets_helper(re, UnicodeSets);
    159     if (UnicodeSets.size() == 0) return false;
    160     for (unsigned i = 0; i < UnicodeSets.size(); i++) {
    161         for (unsigned j = i + 1; j < UnicodeSets.size(); j++) {
    162             for (const UCD::UnicodeSet::interval_t & range : UnicodeSets[i]) {
    163                 auto lo = re::lo_codepoint(range);
    164                 auto hi = re::hi_codepoint(range);
    165                 if (UnicodeSets[j].intersects(lo, hi)) {
    166                     return false;
    167                 }
    168             }
    169         }
    170     }
    171     return true;
    172 }
    173 
    174 
    175 RE * RE_Local::collect_UnicodeSets_helper(RE * re, std::vector<UCD::UnicodeSet> & UnicodeSets) {
     157    UCD::UnicodeSet seen = UCD::UnicodeSet();
     158    return isLocalLanguage_helper(re, seen);
     159}
     160
     161bool RE_Local::isLocalLanguage_helper(const RE * re, UCD::UnicodeSet & codepoints_seen) {
    176162    assert ("RE object cannot be null!" && re);
    177     if (isa<Name>(re)) {
    178         if (CC * cc = dyn_cast<CC>(cast<Name>(re)->getDefinition())) {
    179             UnicodeSets.push_back(* cast<UCD::UnicodeSet>(cc));
    180         } else {
    181             collect_UnicodeSets_helper(cast<Name>(re)->getDefinition(), UnicodeSets);
    182         }
    183     } else if (isa<Seq>(re)) {
    184         for (RE * item : *cast<Seq>(re)) {
    185             collect_UnicodeSets_helper(item, UnicodeSets);
    186         }
    187     } else if (isa<Alt>(re)) {
    188         for (RE * item : *cast<Alt>(re)) {
    189             collect_UnicodeSets_helper(item, UnicodeSets);
    190         }
    191     } else if (isa<Rep>(re)) {
    192         collect_UnicodeSets_helper(cast<Rep>(re)->getRE(), UnicodeSets);
    193     } else if (isa<Assertion>(re)) {
    194         collect_UnicodeSets_helper(cast<Assertion>(re)->getAsserted(), UnicodeSets);
    195     } else if (isa<Diff>(re)) {
    196         collect_UnicodeSets_helper(cast<Diff>(re)->getLH(), UnicodeSets);
    197         collect_UnicodeSets_helper(cast<Diff>(re)->getRH(), UnicodeSets);
    198     } else if (isa<Intersect>(re)) {
    199         collect_UnicodeSets_helper(cast<Intersect>(re)->getLH(), UnicodeSets);
    200         collect_UnicodeSets_helper(cast<Intersect>(re)->getRH(), UnicodeSets);
    201     } else if (isa<Any>(re)) {
    202         UnicodeSets.push_back(UCD::UnicodeSet(0x00, 0x10FFFF));
    203     }
    204     return re;
     163    if (isa<Any>(re)) {
     164        bool no_intersect = codepoints_seen.empty();
     165        codepoints_seen = UCD::UnicodeSet(0x00, 0x10FFFF);
     166        return no_intersect;
     167    } else if (const CC * cc = dyn_cast<CC>(re)) {
     168        bool has_intersect = cast<UCD::UnicodeSet>(cc)->intersects(codepoints_seen);
     169        codepoints_seen = codepoints_seen + *cast<UCD::UnicodeSet>(cc);
     170        return !has_intersect;
     171    } else if (const Name * n = dyn_cast<Name>(re)) {
     172        return isLocalLanguage_helper(n->getDefinition(), codepoints_seen);
     173    } else if (const Seq * re_seq = dyn_cast<const Seq>(re)) {
     174        for (const RE * item : *re_seq) {
     175            if (!isLocalLanguage_helper(item, codepoints_seen)) return false;
     176        }
     177        return true;
     178    } else if (const Alt * re_alt = dyn_cast<const Alt>(re)) {
     179        for (RE * item : *re_alt) {
     180            if (!isLocalLanguage_helper(item, codepoints_seen)) return false;
     181        }
     182        return true;
     183    } else if (const Rep* re_rep = dyn_cast<const Rep>(re)) {
     184        if (re_rep->getUB() > 1) return false;
     185        return isLocalLanguage_helper(re_rep->getRE(), codepoints_seen);
     186    } else {
     187        // A local language cannot contain Intersects, Differences, Assertions, Start, End.
     188        return false;
     189    }
    205190}
    206191
  • icGREP/icgrep-devel/icgrep/re/re_local.h

    r5620 r5632  
    1616        static bool isLocalLanguage(RE * re);
    1717private:
    18         static RE * collect_UnicodeSets_helper(RE * re, std::vector<UCD::UnicodeSet> & UnicodeSets);
     18        static bool isLocalLanguage_helper(const RE * re, UCD::UnicodeSet & seen);
    1919        static bool isNullable(const RE * re);
    2020};
Note: See TracChangeset for help on using the changeset viewer.