Ignore:
Timestamp:
Oct 3, 2015, 3:31:16 PM (4 years ago)
Author:
nmedfort
Message:

Added union/diff/intersection functionality to RE_Compiler. Removed toUTF8 pass in favour of using the UCD_Compiler.

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

Legend:

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

    r4812 r4814  
    1414CC::CC(const CC * cc1, const CC * cc2)
    1515: RE(ClassTypeId::CC)
    16 , mSparseCharSet(std::move(cc1->mSparseCharSet + cc2->mSparseCharSet)) {
     16, UCD::UnicodeSet(std::move(*cc1 + *cc2)) {
    1717
    1818}
     
    2020CC::CC(const CC & cc)
    2121: RE(ClassTypeId::CC)
    22 , mSparseCharSet(cc.mSparseCharSet) {
     22, UCD::UnicodeSet(cc) {
    2323
    2424}
     
    3333    }
    3434    char separator = '_';
    35     for (const interval_t & i : mSparseCharSet) {
     35    for (const interval_t & i : *this) {
    3636        name << separator;
    3737        if (lo_codepoint(i) == hi_codepoint(i)) {
     
    4545    return name.str();
    4646}
    47 
    48 CC * subtractCC(const CC * a, const CC * b) {
    49     return makeCC(a->mSparseCharSet - b->mSparseCharSet);
    50 }
    51    
    52 CC * intersectCC(const CC * a, const CC * b) {
    53     return makeCC(a->mSparseCharSet & b->mSparseCharSet);
    54 }
    5547   
    5648CC * caseInsensitize(const CC * cc) {
  • icGREP/icgrep-devel/icgrep/re/re_cc.h

    r4812 r4814  
    2222enum CC_type {UnicodeClass, ByteClass};
    2323
    24 class CC : public RE {
     24class CC : public RE, public UCD::UnicodeSet {
    2525public:
    2626
     
    3232    }
    3333
    34     using iterator = UCD::UnicodeSet::iterator;
    35     using size_type = UCD::UnicodeSet::size_type;
    3634
    3735    std::string canonicalName(const CC_type type) const;
    3836
    3937    inline codepoint_t min_codepoint() const {
    40         return mSparseCharSet.front().first;
     38        return front().first;
    4139    }
    4240
    4341    inline codepoint_t max_codepoint() const {
    44         return mSparseCharSet.back().second;
    45     }
    46 
    47     void insert_range(const codepoint_t lo, const codepoint_t hi) {
    48         mSparseCharSet.insert_range(lo, hi);
    49     }
    50 
    51     inline void insert(const codepoint_t codepoint) {
    52         mSparseCharSet.insert(codepoint);
    53     }
    54 
    55     inline iterator begin() const {
    56         return mSparseCharSet.begin();
    57     }
    58 
    59     inline iterator end() const {
    60         return mSparseCharSet.end();
    61     }
    62 
    63     inline interval_t front() const {
    64         return mSparseCharSet.front();
    65     }
    66 
    67     inline interval_t back() const {
    68         return mSparseCharSet.back();
    69     }
    70 
    71     inline size_type size() const {
    72         return mSparseCharSet.size();
    73     }
    74 
    75     inline bool empty() const {
    76         return mSparseCharSet.empty();
     42        return back().second;
    7743    }
    7844
     
    9258
    9359    inline CC()
    94     : RE(ClassTypeId::CC)
    95     , mSparseCharSet() {
     60    : RE(ClassTypeId::CC) {
    9661
    9762    }
     63
    9864    CC(const CC & cc);
     65
    9966    inline CC(const codepoint_t codepoint)
    10067    : RE(ClassTypeId::CC)
    101     , mSparseCharSet(codepoint) {
     68    , UCD::UnicodeSet(codepoint) {
    10269
    10370    }
     71
    10472    inline CC(const codepoint_t lo_codepoint, const codepoint_t hi_codepoint)
    10573    : RE(ClassTypeId::CC)
    106     , mSparseCharSet(lo_codepoint, hi_codepoint) {
     74    , UCD::UnicodeSet(lo_codepoint, hi_codepoint) {
    10775
    10876    }
     77
    10978    CC(const CC * cc1, const CC * cc2);
    11079
    11180    inline CC(UCD::UnicodeSet && set)
    11281    : RE(ClassTypeId::CC)
    113     , mSparseCharSet(std::move(set)) {
     82    , UCD::UnicodeSet(std::move(set)) {
    11483
    11584    }
     
    11786    template <typename itr>
    11887    CC * initialize(itr begin, itr end);
    119 private:   
    120     UCD::UnicodeSet mSparseCharSet;
     88
    12189};
    12290
     
    146114CC * CC::initialize(itr begin, itr end) {
    147115    for (auto i = begin; i != end; ++i) {
    148         mSparseCharSet.insert_range(i->first, i->second);
     116        insert_range(i->first, i->second);
    149117    }
    150118    return this;
     
    184152
    185153inline CC * makeCC(UCD::UnicodeSet && set) {
    186     return makeCC(std::move(set));
     154    return new CC(std::move(set));
    187155}
    188156
    189 CC * subtractCC(const CC * a, const CC * b);
    190    
    191 CC * intersectCC(const CC * cc1, const CC * cc2);
     157inline CC * subtractCC(const CC * a, const CC * b) {
     158    return makeCC(std::move(*a - *b));
     159}
     160
     161inline CC * intersectCC(const CC * a, const CC * b) {
     162    return makeCC(std::move(*a & *b));
     163}
    192164
    193165CC * caseInsensitize(const CC * cc);
  • icGREP/icgrep-devel/icgrep/re/re_compiler.cpp

    r4809 r4814  
    2929#include <iostream>
    3030#include <pablo/printer_pablos.h>
     31#ifdef USE_BOOST
     32#include <boost/container/flat_set.hpp>
     33#else
     34#include <unordered_set>
     35#endif
    3136
    3237#include "llvm/Support/CommandLine.h"
     
    4651                     cl::desc("set mod64 approximate mode"), cl::cat(fREcompilationOptions));
    4752#ifndef DISABLE_PREGENERATED_UCD_FUNCTIONS
    48 static cl::opt<bool> UsePregeneratedUnicode("use-pregenerated-unicode", cl::init(true),
     53static cl::opt<bool> UsePregeneratedUnicode("use-pregenerated-unicode", cl::init(false),
    4954                     cl::desc("use fixed pregenerated Unicode character class sets instead"), cl::cat(fREcompilationOptions));
    5055#endif
     
    5863, mCRLF(nullptr)
    5964, mUnicodeLineBreak(nullptr)
     65, mNonLineBreak(nullptr)
    6066, mInitial(nullptr)
    6167, mNonFinal(nullptr)
     
    176182    mUnicodeLineBreak = mPB.createAnd(LB_chars, mPB.createNot(mCRLF));  // count the CR, but not CRLF
    177183    PabloAST * const lb = UNICODE_LINE_BREAK ? mUnicodeLineBreak : mLineFeed;
     184    mNonLineBreak = mPB.createNot(lb);
    178185    mFunction.setResult(1, mPB.createAssign("lf", mPB.createAnd(lb, mPB.createNot(mCRLF))));
    179186}
    180187
    181 void RE_Compiler::gatherUnicodePropertyNames(RE * re, NameSet & nameSet) {
    182 
    183     struct UnicodePropertyNameMap {
    184         using PropertyMap = std::map<std::string, Name *>;
    185         using NamespacedPropertyMap = std::map<std::pair<std::string, std::string>, Name *>;
    186         void process(RE * re) {
     188
     189RE * RE_Compiler::resolveUnicodeProperties(RE * re) {
     190
     191    using PropertyMap = std::map<std::string, RE *>;
     192    using NamespacedPropertyMap = std::map<std::pair<std::string, std::string>, RE *>;
     193    using NameMap = UCD::UCDCompiler::NameMap;
     194
     195    struct UnicodePropertyResolver {
     196
     197        static inline CC * getNamedCC(RE * re) {
     198            if (LLVM_LIKELY(isa<Name>(re))) {
     199                Name * name = cast<Name>(re);
     200                if (name->getDefinition() && isa<CC>(name->getDefinition())) {
     201                    return cast<CC>(name->getDefinition());
     202                }
     203            }
     204            return nullptr;
     205        }
     206
     207        RE * resolve(RE * re) {
    187208            if (Name * name = dyn_cast<Name>(re)) {
    188                 if (name->getDefinition()) {
    189                     process(name->getDefinition());
    190                     return;
    191                 }
    192                 if (name->hasNamespace()) {
    193                     const auto f = mNamespacedPropertyMap.find(std::make_pair(name->getNamespace(), name->getName()));
    194                     if (f != mNamespacedPropertyMap.end()) {
    195                         if (f->second != name) {
    196                             name->setDefinition(f->second);
     209                if (LLVM_LIKELY(name->getDefinition() != nullptr)) {
     210                    name->setDefinition(resolve(name->getDefinition()));
     211                } else if (LLVM_LIKELY(name->getType() == Name::Type::UnicodeProperty)) {
     212                    // Attempt to look up an equivalently named Name object
     213                    if (name->hasNamespace()) {
     214                        const auto f = mNamespacedPropertyMap.find(std::make_pair(name->getNamespace(), name->getName()));
     215                        if (f != mNamespacedPropertyMap.end()) {
     216                            if (f->second != name) {
     217                                return f->second;
     218                            }
    197219                        }
    198                         return;
     220                        mNamespacedPropertyMap.insert(std::make_pair(std::make_pair(name->getNamespace(), name->getName()), name));
     221                    } else {
     222                        const auto f = mPropertyMap.find(name->getName());
     223                        if (f != mPropertyMap.end()) {
     224                            if (f->second != name) {
     225                                return f->second;
     226                            }
     227                        }
     228                        mPropertyMap.insert(std::make_pair(name->getName(), name));
    199229                    }
    200                     mNamespacedPropertyMap.insert(std::make_pair(std::make_pair(name->getNamespace(), name->getName()), name));
     230                    if (UCD::resolvePropertyDefinition(name)) {
     231                        resolve(name->getDefinition());
     232                    } else {
     233                        #ifndef DISABLE_PREGENERATED_UCD_FUNCTIONS
     234                        if (UsePregeneratedUnicode) {
     235                            const std::string functionName = UCD::resolvePropertyFunction(name);
     236                            const UCD::ExternalProperty & ep = UCD::resolveExternalProperty(functionName);
     237                            Call * call = mPB.createCall(Prototype::Create(functionName, std::get<1>(ep), std::get<2>(ep), std::get<0>(ep)), mCCCompiler.getBasisBits());
     238                            name->setCompiled(mPB.createAnd(call, mNonLineBreak));
     239                        } else {
     240                        #endif
     241                            name->setDefinition(makeCC(std::move(UCD::resolveUnicodeSet(name))));
     242                        #ifndef DISABLE_PREGENERATED_UCD_FUNCTIONS
     243                        }
     244                        #endif
     245                    }
    201246                } else {
    202                     const auto f = mPropertyMap.find(name->getName());
    203                     if (f != mPropertyMap.end()) {
    204                         if (f->second != name) {
    205                             name->setDefinition(f->second);
    206                         }
    207                         return;
     247                    throw std::runtime_error("All non-unicode-property Name objects should have been defined prior to Unicode property resolution.");
     248                }
     249            } else if (Seq * seq = dyn_cast<Seq>(re)) {
     250                for (auto si = seq->begin(); si != seq->end(); ) {
     251                    RE * re = resolve(*si);
     252                    if (LLVM_UNLIKELY(isa<Seq>(re))) {
     253                        auto sj = cast<Seq>(re)->begin();
     254                        *si = *sj;
     255                        si = seq->insert(++si, ++sj, cast<Seq>(re)->end());
     256                    } else {
     257                        *si++ = re;
    208258                    }
    209                     mPropertyMap.insert(std::make_pair(name->getName(), name));
    210                 }
    211                 if (name->getType() == Name::Type::UnicodeProperty) {
    212                     RE * definition = UCD::resolvePropertyDefinition(name);
    213                     if (definition) {
    214                         process(definition);
     259                }
     260            } else if (Alt * alt = dyn_cast<Alt>(re)) {
     261                CC * unionCC = nullptr;
     262                for (auto ai = alt->begin(); ai != alt->end(); ) {
     263                    RE * re = resolve(*ai);
     264                    if (CC * cc = getNamedCC(re)) {
     265                        unionCC = (unionCC == nullptr) ? cc : makeCC(unionCC, cc);
     266                        ai = alt->erase(ai);
     267                    } else if (LLVM_UNLIKELY(isa<Alt>(re))) {
     268                        auto aj = cast<Alt>(re)->begin();
     269                        *ai = *aj;
     270                        ai = alt->insert(++ai, ++aj, cast<Alt>(re)->end());
    215271                    } else {
    216                         mNameSet.insert(name);
     272                        *ai++ = re;
    217273                    }
    218274                }
    219             } else if (Seq* seq = dyn_cast<Seq>(re)) {
    220                 for (RE * re : *seq) {
    221                     process(re);
     275                if (unionCC) {
     276                    alt->push_back(makeName("union", unionCC));
     277                }
     278                if (alt->size() == 1) {
     279                    return alt->front();
     280                }
     281            } else if (Rep * rep = dyn_cast<Rep>(re)) {
     282                rep->setRE(resolve(rep->getRE()));
     283            } else if (Assertion * a = dyn_cast<Assertion>(re)) {
     284                a->setAsserted(resolve(a->getAsserted()));
     285            } else if (Diff * diff = dyn_cast<Diff>(re)) {
     286                diff->setLH(resolve(diff->getLH()));
     287                diff->setRH(resolve(diff->getRH()));
     288                #ifndef DISABLE_PREGENERATED_UCD_FUNCTIONS
     289                if (!UsePregeneratedUnicode) {
     290                #endif
     291                    CC * lh = getNamedCC(diff->getLH());
     292                    CC * rh = getNamedCC(diff->getRH());
     293                    if (lh && rh) {
     294                        return resolve(makeName("diff", subtractCC(lh, rh)));
     295                    }
     296                #ifndef DISABLE_PREGENERATED_UCD_FUNCTIONS
     297                }
     298                #endif
     299            } else if (Intersect * ix = dyn_cast<Intersect>(re)) {
     300                ix->setLH(resolve(ix->getLH()));
     301                ix->setRH(resolve(ix->getRH()));
     302                #ifndef DISABLE_PREGENERATED_UCD_FUNCTIONS
     303                if (!UsePregeneratedUnicode) {
     304                #endif
     305                    CC * lh = getNamedCC(diff->getLH());
     306                    CC * rh = getNamedCC(diff->getRH());
     307                    if (lh && rh) {
     308                        return resolve(makeName("intersect", intersectCC(lh, rh)));
     309                    }
     310                #ifndef DISABLE_PREGENERATED_UCD_FUNCTIONS
     311                }
     312                #endif
     313            }
     314            return re;
     315        }
     316
     317        static void collect(RE * re, NameMap & nameMap) {
     318            if (Name * name = dyn_cast<Name>(re)) {
     319                if (isa<CC>(name->getDefinition())) {
     320                    nameMap.emplace(name, nullptr);
     321                } else {
     322                    collect(name->getDefinition(), nameMap);
     323                }
     324            } else if (Seq * seq = dyn_cast<Seq>(re)) {
     325                for (auto re : *seq) {
     326                    collect(re, nameMap);
    222327                }
    223328            } else if (Alt * alt = dyn_cast<Alt>(re)) {
    224                 for (RE * re : *alt) {
    225                     process(re);
     329                for (auto re : *alt) {
     330                    collect(re, nameMap);
    226331                }
    227332            } else if (Rep * rep = dyn_cast<Rep>(re)) {
    228                 process(rep->getRE());
     333                collect(rep->getRE(), nameMap);
    229334            } else if (Assertion * a = dyn_cast<Assertion>(re)) {
    230                 process(a->getAsserted());
     335                collect(a->getAsserted(), nameMap);
    231336            } else if (Diff * diff = dyn_cast<Diff>(re)) {
    232                 process(diff->getLH());
    233                 process(diff->getRH());
    234             } else if (Intersect * ix = dyn_cast<Intersect>(re)) {
    235                 process(ix->getLH());
    236                 process(ix->getRH());
     337                collect(diff->getLH(), nameMap);
     338                collect(diff->getRH(), nameMap);
    237339            }
    238 
    239         }
    240 
    241         UnicodePropertyNameMap(NameSet & nameSet) : mNameSet(nameSet) {}
     340        }
    242341
    243342    private:
    244         NameSet &                   mNameSet;
    245343        PropertyMap                 mPropertyMap;
    246344        NamespacedPropertyMap       mNamespacedPropertyMap;
    247     } ;
    248 
    249     UnicodePropertyNameMap(nameSet).process(re);
    250 }
    251 
    252 void RE_Compiler::compileUnicodeNames(RE * re) {
    253     NameSet nameSet;
    254     gatherUnicodePropertyNames(re, nameSet);
    255 #ifndef DISABLE_PREGENERATED_UCD_FUNCTIONS
    256     if (UsePregeneratedUnicode) {
    257         for (Name * name : nameSet) {
    258             const std::string functionName = UCD::resolvePropertyFunction(name);
    259             const UCD::ExternalProperty & ep = UCD::resolveExternalProperty(functionName);
    260             Call * call = mPB.createCall(Prototype::Create(functionName, std::get<1>(ep), std::get<2>(ep), std::get<0>(ep)), mCCCompiler.getBasisBits());
    261             name->setCompiled(mPB.createAnd(call, mPB.createNot(UNICODE_LINE_BREAK ? mUnicodeLineBreak : mLineFeed)));
    262         }
    263     } else {
    264 #endif
    265         std::vector<UCD::UnicodeSet> sets;
    266         for (Name * name : nameSet) {
    267             sets.push_back(std::move(UCD::resolveUnicodeSet(name)));
    268         }
    269         if (sets.size() > 0) {
    270             UCD::UCDCompiler ucdCompiler(mCCCompiler);
    271             std::vector<PabloAST *> classes(std::move(ucdCompiler.generateWithDefaultIfHierarchy(sets, mPB)));
    272             auto value = classes.begin();
    273             for (Name * name : nameSet) {
    274                 name->setCompiled(mPB.createAnd(*value++, mPB.createNot(UNICODE_LINE_BREAK ? mUnicodeLineBreak : mLineFeed)));
     345    };
     346
     347    UnicodePropertyResolver resolver;
     348    re = resolver.resolve(re);
     349    #ifndef DISABLE_PREGENERATED_UCD_FUNCTIONS
     350    if (UsePregeneratedUnicode) return re;
     351    #endif
     352    NameMap nameMap;
     353    resolver.collect(re, nameMap);
     354
     355    if (nameMap.size() > 0) {
     356        UCD::UCDCompiler ucdCompiler(mCCCompiler);
     357        ucdCompiler.generateWithDefaultIfHierarchy(nameMap, mPB);
     358        for (auto t : nameMap) {
     359            if (t.second) {
     360                t.first->setCompiled(mPB.createAnd(t.second, mNonLineBreak));
    275361            }
    276362        }
    277 #ifndef DISABLE_PREGENERATED_UCD_FUNCTIONS
    278     }
    279 #endif
     363    }
     364
     365    return re;
     366}
     367
     368void RE_Compiler::compileUnicodeNames(RE *& re) {
     369    re = resolveUnicodeProperties(re);
    280370}
    281371
    282372void RE_Compiler::finalizeMatchResult(MarkerType match_result) {
    283     //These three lines are specifically for grep.
    284     PabloAST * lb = UNICODE_LINE_BREAK ? mUnicodeLineBreak : mLineFeed;
    285     PabloAST * v = markerVar(match_result);
    286     mFunction.setResult(0, mPB.createAssign("matches", mPB.createAnd(mPB.createMatchStar(v, mPB.createNot(lb)), lb)));
     373    mFunction.setResult(0, mPB.createAssign("matches", mPB.createAnd(mPB.createMatchStar(markerVar(match_result), mNonLineBreak), UNICODE_LINE_BREAK ? mUnicodeLineBreak : mLineFeed)));
    287374}
    288375
     
    294381    if (markerPos(m) == MarkerPosition::FinalPostPositionByte) {
    295382        return markerVar(m);
    296     }
    297     else if (markerPos(m) == MarkerPosition::InitialPostPositionByte) {
     383    } else if (markerPos(m) == MarkerPosition::InitialPostPositionByte) {
    298384        return pb.createScanThru(pb.createAnd(mInitial, markerVar(m)), mNonFinal);
    299     }
    300     else {
     385    } else {
    301386        return pb.createScanThru(pb.createAnd(mInitial, pb.createAdvance(markerVar(m), 1)), mNonFinal);
    302387    }
     
    371456    if (LLVM_LIKELY(var != nullptr)) {
    372457        return var;
    373     } else if (name->getDefinition() != nullptr) {
     458    } else if (LLVM_LIKELY(name->getDefinition() != nullptr)) {
    374459        MarkerType m = compile(name->getDefinition(), pb);
    375460        assert(markerPos(m) == MarkerPosition::FinalMatchByte);
    376         var = markerVar(m);
     461        var = pb.createAnd(markerVar(m), mNonLineBreak);
     462        name->setCompiled(var);
     463        return var;
    377464    } else {
    378465        throw std::runtime_error("Unresolved name " + name->getName());
    379466    }
    380     var = pb.createAnd(var, pb.createNot(UNICODE_LINE_BREAK ? mUnicodeLineBreak : mLineFeed));
    381     name->setCompiled(var);
    382     return var;
    383467}
    384468
  • icGREP/icgrep-devel/icgrep/re/re_compiler.h

    r4808 r4814  
    1212#include <cc/cc_compiler.h>
    1313#include <pablo/builder.hpp>
    14 #ifdef USE_BOOST
    15 #include <boost/container/flat_set.hpp>
    16 #else
    17 #include <unordered_set>
    18 #endif
    1914
    2015namespace pablo {
     
    5954    RE_Compiler(pablo::PabloFunction & function, cc::CC_Compiler & ccCompiler);
    6055    void initializeRequiredStreams();
    61     void compileUnicodeNames(RE * re);
     56    void compileUnicodeNames(RE *& re);
    6257    void finalizeMatchResult(MarkerType match_result);
    6358    MarkerType compile(RE * re) {
     
    6661
    6762private:
    68 
    69     #ifdef USE_BOOST
    70     using NameSet = boost::container::flat_set<Name *>;
    71     #else
    72     using NameSet = std::unordered_set<Name *>;
    73     #endif
    7463
    7564    MarkerType compile(RE * re, pablo::PabloBuilder & cg);
     
    9584    MarkerType processUnboundedRep(RE * repeated, MarkerType marker, pablo::PabloBuilder & pb);
    9685    MarkerType processBoundedRep(RE * repeated, int ub, MarkerType marker, pablo::PabloBuilder & pb);
    97     static void gatherUnicodePropertyNames(RE * re, NameSet & nameSet);
     86    RE * resolveUnicodeProperties(RE * re);
    9887
    9988private:
     
    10392    pablo::PabloAST *                               mCRLF;
    10493    pablo::PabloAST *                               mUnicodeLineBreak;
     94    pablo::PabloAST *                               mNonLineBreak;
    10595    pablo::PabloAST *                               mInitial;
    10696    pablo::Assign *                                 mNonFinal;
Note: See TracChangeset for help on using the changeset viewer.