Ignore:
Timestamp:
Dec 28, 2017, 1:15:13 PM (13 months ago)
Author:
nmedfort
Message:

Bug fix for RE local + some clean up of RE local and the RE Compiler

File:
1 edited

Legend:

Unmodified
Added
Removed
  • icGREP/icgrep-devel/icgrep/re/re_local.cpp

    r5748 r5812  
    88#include <re/re_intersect.h>
    99#include <re/re_assertion.h>
    10 #include <re/re_any.h>
    1110#include <re/re_analysis.h>
    12 #include <UCD/resolve_properties.h>
    13 #include <boost/container/flat_set.hpp>
     11#include <re/re_nullable.h>
     12#include <boost/container/flat_map.hpp>
    1413#include <boost/range/adaptor/reversed.hpp>
    15 #include <util/slab_allocator.h>
    16 #include <map>
    1714
    1815using namespace boost::container;
     
    2017
    2118namespace re {
    22  
    23 inline void combine(CC *& a, CC * b) {
     19
     20using FollowMap = flat_map<const CC *, const CC*>;
     21
     22inline const CC * combine(const CC * a, const CC * b) {
    2423    if (a && b) {
    25         a = makeCC(a, b);
     24        return makeCC(a, b);
    2625    } else if (b) {
    27         a = b;
     26        return b;
    2827    }
     28    return a;
    2929}
    3030
    31 CC * RE_Local::first(RE * re) {
    32     if (Name * name = dyn_cast<Name>(re)) {
     31const CC * first(const RE * re) {
     32    if (const Name * name = dyn_cast<Name>(re)) {
    3333        if (LLVM_LIKELY(name->getDefinition() != nullptr)) {
    3434            return first(name->getDefinition());
     
    3636            UndefinedNameError(name);
    3737        }
    38     } else if (CC * cc = dyn_cast<CC>(re)) {
     38    } else if (const CC * cc = dyn_cast<CC>(re)) {
    3939        return cc;
    40     } else if (Seq * seq = dyn_cast<Seq>(re)) {
    41         CC * cc = nullptr;
     40    } else if (const Seq * seq = dyn_cast<Seq>(re)) {
     41        const CC * cc = nullptr;
    4242        for (auto & si : *seq) {
    43             combine(cc, first(si));
    44             if (!isNullable(si)) {
     43            cc = combine(cc, first(si));
     44            if (!RE_Nullable::isNullable(si)) {
    4545                break;
    4646            }
    4747        }
    4848        return cc;
    49     } else if (Alt * alt = dyn_cast<Alt>(re)) {
    50         CC * cc = nullptr;
     49    } else if (const Alt * alt = dyn_cast<Alt>(re)) {
     50        const CC * cc = nullptr;
    5151        for (auto & ai : *alt) {
    52             combine(cc, first(ai));
     52            cc = combine(cc, first(ai));
    5353        }
    5454        return cc;
    55     } else if (Rep * rep = dyn_cast<Rep>(re)) {
     55    } else if (const Rep * rep = dyn_cast<Rep>(re)) {
    5656        return first(rep->getRE());
    57     } else if (Diff * diff = dyn_cast<Diff>(re)) {
    58         if (CC * lh = first(diff->getLH())) {
    59             if (CC * rh = first(diff->getRH())) {
     57    } else if (const Diff * diff = dyn_cast<Diff>(re)) {
     58        if (const CC * lh = first(diff->getLH())) {
     59            if (const CC * rh = first(diff->getRH())) {
    6060                return subtractCC(lh, rh);
    6161            }
    6262        }
    63     } else if (Intersect * ix = dyn_cast<Intersect>(re)) {
    64         if (CC * lh = first(ix->getLH())) {
    65             if (CC * rh = first(ix->getRH())) {
     63    } else if (const Intersect * ix = dyn_cast<Intersect>(re)) {
     64        if (const CC * lh = first(ix->getLH())) {
     65            if (const CC * rh = first(ix->getRH())) {
    6666                return intersectCC(lh, rh);
    6767            }
     
    7171}
    7272
    73 CC * RE_Local::final(RE * re) {
    74     if (Name * name = dyn_cast<Name>(re)) {
     73const CC * final(const RE * re) {
     74    if (const Name * name = dyn_cast<Name>(re)) {
    7575        if (LLVM_LIKELY(name->getDefinition() != nullptr)) {
    7676            return final(name->getDefinition());
     
    7878            UndefinedNameError(name);
    7979        }
    80     } else if (CC * cc = dyn_cast<CC>(re)) {
     80    } else if (const CC * cc = dyn_cast<CC>(re)) {
    8181        return cc;
    82     } else if (Seq * seq = dyn_cast<Seq>(re)) {
    83         CC * cc = nullptr;
     82    } else if (const Seq * seq = dyn_cast<Seq>(re)) {
     83        const CC * cc = nullptr;
    8484        for (auto & si : boost::adaptors::reverse(*seq)) {
    85             combine(cc, first(si));
    86             if (!isNullable(si)) {
     85            cc = combine(cc, final(si));
     86            if (!RE_Nullable::isNullable(si)) {
    8787                break;
    8888            }
    8989        }
    9090        return cc;
    91     } else if (Alt * alt = dyn_cast<Alt>(re)) {
    92         CC * cc = nullptr;
     91    } else if (const Alt * alt = dyn_cast<Alt>(re)) {
     92        const CC * cc = nullptr;
    9393        for (auto & ai : *alt) {
    94             combine(cc, final(ai));
     94            cc = combine(cc, final(ai));
    9595        }
    9696        return cc;
    97     } else if (Rep * rep = dyn_cast<Rep>(re)) {
     97    } else if (const Rep * rep = dyn_cast<Rep>(re)) {
    9898        return final(rep->getRE());
    99     } else if (Diff * diff = dyn_cast<Diff>(re)) {
    100         if (CC * lh = final(diff->getLH())) {
    101             if (CC * rh = final(diff->getRH())) {
     99    } else if (const Diff * diff = dyn_cast<Diff>(re)) {
     100        if (const CC * lh = final(diff->getLH())) {
     101            if (const CC * rh = final(diff->getRH())) {
    102102                return subtractCC(lh, rh);
    103103            }
    104104        }
    105     } else if (Intersect * ix = dyn_cast<Intersect>(re)) {
    106         if (CC * lh = final(ix->getLH())) {
    107             if (CC * rh = final(ix->getRH())) {
     105    } else if (const Intersect * ix = dyn_cast<Intersect>(re)) {
     106        if (const CC * lh = final(ix->getLH())) {
     107            if (const CC * rh = final(ix->getRH())) {
    108108                return intersectCC(lh, rh);
    109109            }
     
    114114}
    115115
    116 void RE_Local::follow(RE * re, std::map<CC *, CC*> &follow_map) {
    117     if (Name * name = dyn_cast<Name>(re)) {
     116void follow(const RE * re, FollowMap & follows) {
     117    if (const Name * name = dyn_cast<Name>(re)) {
    118118        if (LLVM_LIKELY(name->getDefinition() != nullptr)) {
    119             return follow(name->getDefinition(), follow_map);
     119            return follow(name->getDefinition(), follows);
    120120        } else {
    121121            UndefinedNameError(name);
    122122        }
    123     } else if (Seq * seq = dyn_cast<Seq>(re)) {
    124         if (seq->size() > 0) {
    125             RE * re_first = *(seq->begin());
    126             RE * re_follow = makeSeq(seq->begin() + 1, seq->end());
     123    } else if (const Seq * seq = dyn_cast<Seq>(re)) {
     124        if (!seq->empty()) {
     125            const RE * const re_first = *(seq->begin());
     126            const RE * const re_follow = makeSeq(seq->begin() + 1, seq->end());
    127127            auto e1 = final(re_first);
    128128            auto e2 = first(re_follow);
    129129            if (e1 && e2) {
    130                 auto e = follow_map.find(e1);
    131                 if (e != follow_map.end()) {
     130                auto e = follows.find(e1);
     131                if (e != follows.end()) {
    132132                    e->second = makeCC(e->second, e2);
    133133                } else {
    134                     follow_map.emplace(e1, e2);
     134                    follows.emplace(e1, e2);
    135135                }
    136136            }
    137             follow(re_first, follow_map);
    138             follow(re_follow, follow_map);
     137            follow(re_first, follows);
     138            follow(re_follow, follows);
    139139        }
    140     } else if (Alt * alt = dyn_cast<Alt>(re)) {
     140    } else if (const Alt * alt = dyn_cast<Alt>(re)) {
    141141        for (auto ai = alt->begin(); ai != alt->end(); ++ai) {
    142             follow(*ai, follow_map);
     142            follow(*ai, follows);
    143143        }
    144     } else if (Rep * rep = dyn_cast<Rep>(re)) {
    145         auto e1 = final(rep->getRE());
     144    } else if (const Rep * rep = dyn_cast<Rep>(re)) {
     145        const auto e1 = final(rep->getRE());
    146146        auto e2 = first(rep->getRE());
    147147        if (e1 && e2) {
    148             auto e = follow_map.find(e1);
    149             if (e != follow_map.end()) {
     148            auto e = follows.find(e1);
     149            if (e != follows.end()) {
    150150                e->second = makeCC(e->second, e2);
    151151            } else {
    152                 follow_map.emplace(e1, e2);
     152                follows.emplace(e1, e2);
    153153            }
    154154        }
    155         follow(rep->getRE(), follow_map);
     155        follow(rep->getRE(), follows);
    156156    }
    157157}
    158158
    159 bool RE_Local::isLocalLanguage(RE * re) {   
    160     UCD::UnicodeSet seen;
    161     return isLocalLanguage_helper(re, seen);
    162 }
    163 
    164 bool RE_Local::isLocalLanguage_helper(const RE * re, UCD::UnicodeSet & seen) {
    165     assert ("RE object cannot be null!" && re);
    166     if (isa<Any>(re)) {
    167         const bool no_intersect = seen.empty();
    168         seen.insert_range(0x00, 0x10FFFF);
    169         return no_intersect;
    170     } else if (const CC * cc = dyn_cast<CC>(re)) {
    171         const bool has_intersect = cc->intersects(seen);
    172         seen = seen + *cc;
    173         return !has_intersect;
    174     } else if (const Name * n = dyn_cast<Name>(re)) {
    175         return isLocalLanguage_helper(n->getDefinition(), seen);
    176     } else if (const Seq * seq = dyn_cast<Seq>(re)) {
    177         for (const RE * item : *seq) {
    178             if (!isLocalLanguage_helper(item, seen)) return false;
    179         }
    180         return true;
    181     } else if (const Alt * alt = dyn_cast<Alt>(re)) {
    182         for (RE * item : *alt) {
    183             if (!isLocalLanguage_helper(item, seen)) return false;
    184         }
    185         return true;
    186     } else if (const Rep * rep = dyn_cast<Rep>(re)) {
    187         if (rep->getUB() > 1) return false;
    188         return isLocalLanguage_helper(rep->getRE(), seen);
    189     } else {
    190         // A local language cannot contain Intersects, Differences, Assertions, Start, End.
    191         return false;
    192     }
    193 }
    194 
    195 bool RE_Local::isNullable(const RE * re) {
    196     if (const Seq * re_seq = dyn_cast<const Seq>(re)) {
    197         for (const RE * re : *re_seq) {
    198             if (!isNullable(re)) {
    199                 return false;
     159CC * RE_Local::getFirstUniqueSymbol(RE * const re) {
     160    const CC * const re_first = first(re);
     161    if (re_first) {
     162        FollowMap follows;
     163        follow(re, follows);
     164        for (const auto & entry : follows) {
     165            if (entry.second->intersects(*re_first)) {
     166                return nullptr;
    200167            }
    201168        }
    202         return true;
    203     } else if (const Alt * re_alt = dyn_cast<const Alt>(re)) {
    204         for (const RE * re : *re_alt) {
    205             if (isNullable(re)) {
    206                 return true;
    207             }
    208         }
    209     } else if (const Rep* re_rep = dyn_cast<const Rep>(re)) {
    210         return re_rep->getLB() == 0 ? true : isNullable(re_rep->getRE());
    211     } else if (const Diff * diff = dyn_cast<const Diff>(re)) {
    212         return isNullable(diff->getLH()) && !isNullable(diff->getRH());
    213     } else if (const Intersect * e = dyn_cast<const Intersect>(re)) {
    214         return isNullable(e->getLH()) && isNullable(e->getRH());
    215     }
    216     return false;
     169    }
     170    return const_cast<CC *>(re_first);
    217171}
    218172
Note: See TracChangeset for help on using the changeset viewer.