Changeset 6256


Ignore:
Timestamp:
Dec 24, 2018, 9:32:33 PM (3 months ago)
Author:
cameron
Message:

Fixes for contextual simplification

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

Legend:

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

    r6239 r6256  
    77#include "re_assertion.h"
    88#include "re_cc.h"
     9#include "re_start.h"
     10#include "re_end.h"
     11#include "re_any.h"
    912#include "re_seq.h"
    1013#include "re_alt.h"
     
    1720   
    1821RE * makeSOT () {
    19     return makeNegativeLookBehindAssertion(makeByte(0x00,0xFF));
     22    //return makeNegativeLookBehindAssertion(makeByte(0x00,0xFF));
     23    return makeStart();
    2024}
    2125
    2226RE * makeEOT () {
    23     return makeNegativeLookAheadAssertion(makeByte(0x00,0xFF));
     27    //return makeNegativeLookAheadAssertion(makeByte(0x00,0xFF));
     28    return makeEnd();
    2429}
    2530
  • icGREP/icgrep-devel/icgrep/re/re_assertion.h

    r6239 r6256  
    1010#include <re/re_re.h>
    1111#include <re/re_nullable.h>
     12#include <re/re_empty_set.h>
    1213#include <re/re_seq.h>
    1314#include <re/re_alt.h>
     
    4748
    4849inline RE * makeAssertion(RE * asserted, Assertion::Kind k, Assertion::Sense s) {
     50    if (isEmptySet(asserted)) {
     51        if (s == Assertion::Sense::Negative) return makeSeq();
     52        else return makeAlt();
     53    }
    4954    if (isNullable(asserted)) {
    5055        if (k == Assertion::Kind::Boundary) {
  • icGREP/icgrep-devel/icgrep/re/re_contextual_simplification.cpp

    r6251 r6256  
    1212#include <re/re_seq.h>
    1313#include <re/re_assertion.h>
     14#include <re/re_start.h>
     15#include <re/re_end.h>
    1416#include <re/validation.h>
    1517#include <llvm/Support/Casting.h>
     
    3335    template<typename Iterator>
    3436    std::vector<RE *> makeContext(Iterator begin, Iterator end);
     37    RE * transformStart(Start *) override;
     38    RE * transformEnd(End *) override;
    3539    RE * transformAssertion(Assertion * a) override;
    3640    RE * simplifyAsserted(RE * asserted, std::vector<RE *> const & context);
     
    4246class ResolvesToCC : public RE_Validator {
    4347public:
    44     inline bool validateCC(CC *) override { return true; }
    45     inline bool validateStart(Start *) override { return false; }
    46     inline bool validateEnd(End *) override { return false; }
    47     inline bool validateSeq(Seq * s) override { return (s) && s->size() <= 1; }
    48     inline bool validateIntersect(Intersect *) override { return false; }
    49     inline bool validateRange(Range *) override { return false; }
    50     inline bool validateAssertion(Assertion *) override { return false; }
     48    inline bool validateCC(const CC *) override { return true; }
     49    inline bool validateStart(const Start *) override { return false; }
     50    inline bool validateEnd(const End *) override { return false; }
     51    inline bool validateSeq(const Seq * s) override { return (s) && s->size() <= 1; }
     52    inline bool validateIntersect(const Intersect *) override { return false; }
     53    inline bool validateRange(const Range *) override { return false; }
     54    inline bool validateAssertion(const Assertion *) override { return false; }
    5155};
    5256
    5357class ValidateAsserted : public RE_Validator {
    5458public:
    55     inline bool validateStart(Start * s) override { return false; }
    56     inline bool validateEnd(End * e) override { return false; }
    57     inline bool validateRep(Rep * r) override { return false; }
    58     inline bool validateIntersect(Intersect * i) override { return false; }
    59     inline bool validateRange(Range * r) override { return false; }
    60     inline bool validateAssertion(Assertion * a) override { return false; }
    61     inline bool validateDiff(Diff * d) override {
     59    inline bool validateStart(const Start * s) override { return false; }
     60    inline bool validateEnd(const End * e) override { return false; }
     61    inline bool validateRep(const Rep * r) override { return false; }
     62    inline bool validateIntersect(const Intersect * i) override { return false; }
     63    inline bool validateRange(const Range * r) override { return false; }
     64    inline bool validateAssertion(const Assertion * a) override { return false; }
     65    inline bool validateDiff(const Diff * d) override {
    6266        return ResolvesToCC{}.validateRE(d);
    6367    }
    64     inline bool validateSeq(Seq * s) override {
     68    inline bool validateSeq(const Seq * s) override {
    6569        auto ccValidator = ResolvesToCC{};
    6670        for (auto e : *s) {
     
    7579class ValidateZeroWidth : public RE_Validator {
    7680public:
    77     inline bool validateStart(Start * s) { return false; }
    78     inline bool validateEnd(End * e) { return false; }
    79     inline bool validateCC(CC * cc) { return false; }
    80     inline bool validateRep(Rep * rep) { return false; }
    81     inline bool validateIntersect(Intersect * e) { return false; }
    82     inline bool validateRange(Range * rg) { return false; }
    83     inline bool validateAssertion(Assertion * a) { return true; }
    84 
    85     inline bool validateSeq(Seq * s) {
     81    inline bool validateStart(const Start * s) { return true; }
     82    inline bool validateEnd(const End * e) { return true; }
     83    inline bool validateCC(const CC * cc) { return false; }
     84    inline bool validateRep(const Rep * rep) { return false; }
     85    inline bool validateIntersect(const Intersect * e) { return false; }
     86    inline bool validateRange(const Range * rg) { return false; }
     87    inline bool validateAssertion(const Assertion * a) { return true; }
     88
     89    inline bool validateSeq(const Seq * s) {
    8690        for (auto e : *s) {
    8791            if (!validateRE(e)) return false;
     
    163167        return re;
    164168    }
     169}
     170
     171RE * Context::transformStart(Start * s) {
     172    if (before.empty()) return s;
     173    if (llvm::isa<Start>(before.back())) return makeSeq();
     174    return makeAlt();
     175}
     176
     177RE * Context::transformEnd(End * e) {
     178    if (after.empty()) return e;
     179    if (llvm::isa<End>(after.front())) return makeSeq();
     180    return makeAlt();
    165181}
    166182
     
    317333}
    318334
    319 
    320335RE * RE_ContextSimplifier::transformSeq(Seq * s) {
    321336    std::vector<RE *> seq{};
     
    345360    }
    346361
    347    
    348     if (hasChanged) {
    349         auto rt = makeSeq(seq.begin(), seq.end());
    350         return rt;
    351     } else {
    352         return s;
    353     }
     362if (hasChanged) {
     363    auto rt = makeSeq(seq.begin(), seq.end());
     364    return rt;
     365} else {
     366    return s;
     367}
    354368}
    355369
  • icGREP/icgrep-devel/icgrep/re/re_diff.cpp

    r6226 r6256  
    1010#include <re/re_name.h>
    1111#include <re/re_empty_set.h>
     12#include <re/re_nullable.h>
     13#include <re/validation.h>
    1214#include <llvm/Support/Casting.h>
    1315
     
    1921   
    2022RE * makeDiff(RE * lh, RE * rh) {
    21     if (LLVM_UNLIKELY(isEmptySeq(lh) && isEmptySeq(rh))) {
    22         return makeEmptySet();
     23    if (isEmptySeq(lh)) {
     24        if (isNullable(rh)) return makeEmptySet();
     25        if (validateAssertionFree(rh)) return lh; // EmptySeq()
    2326    } else if (LLVM_UNLIKELY(isEmptySet(rh))) {
    2427        return lh;
    2528    } else if (LLVM_UNLIKELY(isEmptySet(lh))) {
    2629        return lh;
    27     } else {
    28         return Diff::Create(lh, rh);
    2930    }
     31    return Diff::Create(lh, rh);
    3032}
    3133
  • icGREP/icgrep-devel/icgrep/re/re_intersect.cpp

    r6226 r6256  
    55 */
    66
    7 #include "re_intersect.h"
    8 #include "re_cc.h"
     7#include <re/re_intersect.h>
     8#include <re/re_cc.h>
    99#include <re/re_name.h>
     10#include <re/re_seq.h>
     11#include <re/re_empty_set.h>
     12#include <re/re_nullable.h>
    1013#include <llvm/Support/Casting.h>
    1114
     
    1518
    1619RE * makeIntersect(RE * lh, RE * rh) {
     20    if (isEmptySet(lh)) return lh;
     21    if (isEmptySet(rh)) return rh;
     22    if (isEmptySeq(lh)) {
     23        if (isNullable(rh)) return lh;
     24        else return makeEmptySet();
     25    }
     26    if (isEmptySeq(rh)) {
     27        if (isNullable(lh)) return rh;
     28        else return makeEmptySet();
     29    }
    1730    if (defined<CC>(lh) && defined<CC>(rh)) {
    1831        CC * lh_cc = defCast<CC>(lh);
  • icGREP/icgrep-devel/icgrep/re/re_name_resolve.cpp

    r6173 r6256  
    101101RE * AnchorResolution::transformStart(Start * s) {
    102102    if (mIsNegated) return makeNegativeLookBehindAssertion(mAnchorRE);
    103     return makeAlt({makeSOT(), makeLookBehindAssertion(mAnchorRE)});
     103    RE * sot = makeNegativeLookBehindAssertion(makeByte(0x00,0xFF));
     104    return makeAlt({sot, makeLookBehindAssertion(mAnchorRE)});
    104105}
    105106
    106107RE * AnchorResolution::transformEnd(End * e) {
    107108    if (mIsNegated) return makeNegativeLookAheadAssertion(mAnchorRE);
    108     return makeAlt({makeEOT(), makeLookAheadAssertion(mAnchorRE)});
     109    RE * eot = makeNegativeLookAheadAssertion(makeByte(0x00,0xFF));
     110    return makeAlt({eot, makeLookAheadAssertion(mAnchorRE)});
    109111}
    110112
  • icGREP/icgrep-devel/icgrep/re/re_nullable.cpp

    r6171 r6256  
    1010#include <re/re_group.h>             // for Seq, makeSeq
    1111#include <re/re_toolchain.h>
     12#include <re/validation.h>
    1213#include <vector>                  // for vector, allocator
    1314#include <llvm/Support/Casting.h>  // for dyn_cast, isa
     
    4142    } else if (const Rep* re_rep = dyn_cast<const Rep>(re)) {
    4243        return (re_rep->getLB() == 0) || isNullable(re_rep->getRE());
    43     } else if (isa<Diff>(re)) {
     44    } else if (const Diff * d = dyn_cast<const Diff>(re)) {
    4445        // a Diff of Seq({}) and an Assertion represents a complemented assertion.
     46        //return isNullable(d->getLH()) && (!isNullable(d->getRH())) && (!isZeroWidth(d->getRH()));
    4547        return false;
    4648    } else if (const Intersect * e = dyn_cast<const Intersect>(re)) {
     
    5254}
    5355
     56struct ZeroWidthValidator : public RE_Validator {
     57    ZeroWidthValidator() : RE_Validator() {}
     58    bool validateName(const Name * n) override {
     59        RE * defn = n->getDefinition();
     60        return defn && validate(defn);
     61    }
     62    bool validateAssertion(const Assertion * a) override {return true;}
     63    bool validateCC(const CC *) override {return false;}
     64    bool validateRange(const Range *) override {return false;}
     65    bool validateDiff(const Diff * d) override {return validate(d->getLH());}
     66    bool validateIntersect(const Intersect * x) override {return validate(x->getLH()) || validate(x->getRH());}
     67};
     68
     69bool isZeroWidth(const RE * re) {
     70    return ZeroWidthValidator().validateRE(re);
     71}
    5472
    5573class NullablePrefixRemover: public RE_Transformer {
     
    154172}
    155173   
    156 
    157174}
  • icGREP/icgrep-devel/icgrep/re/re_nullable.h

    r6171 r6256  
    77namespace re {
    88    bool isNullable(const RE * re);
     9    bool isZeroWidth(const RE * re);
    910    RE * removeNullablePrefix(RE * re);
    1011    RE * removeNullableSuffix(RE * re);
  • icGREP/icgrep-devel/icgrep/re/re_toolchain.cpp

    r6251 r6256  
    123123        r = simplifyRE(r);
    124124    }
    125     //r = RE_ContextSimplifier().transformRE(r);
     125    r = RE_ContextSimplifier().transformRE(r);
     126    r = resolveAnchors(r, makeAlt());
    126127    if (!DefiniteLengthBackReferencesOnly(r)) {
    127128        llvm::report_fatal_error("Future back reference support: references must be within a fixed distance from a fixed-length capture.");
  • icGREP/icgrep-devel/icgrep/re/validation.cpp

    r6178 r6256  
    2626namespace re {
    2727
    28 bool RE_Validator::validateRE(RE * re) {
     28bool RE_Validator::validateRE(const RE * re) {
    2929    bool validated = validate(re);
    3030    if ((mValidatorName != "") && (PrintOptionIsSet(ShowAllREs) || (PrintOptionIsSet(ShowREs) && (!validated))))  {
     
    3434}
    3535
    36 bool RE_Validator::validate(RE * const re) {
     36bool RE_Validator::validate(const RE * const re) {
    3737    using T = RE::ClassTypeId;
    3838#define VALIDATE(Type) \
     
    5656}
    5757
    58 bool RE_Validator::validateName(Name * n) {
     58bool RE_Validator::validateName(const Name * n) {
    5959    RE * def = n->getDefinition();
    6060    return (def) && validate(def);
    6161}
    6262
    63 bool RE_Validator::validateCC(CC * cc) {
     63bool RE_Validator::validateCC(const CC * cc) {
    6464    return true;
    6565}
    6666
    67 bool RE_Validator::validateStart(Start * s) {
     67bool RE_Validator::validateStart(const Start * s) {
    6868    return true;
    6969}
    7070
    71 bool RE_Validator::validateEnd(End * e) {
     71bool RE_Validator::validateEnd(const End * e) {
    7272    return true;
    7373}
    7474
    75 bool RE_Validator::validateSeq(Seq * seq) {
     75bool RE_Validator::validateSeq(const Seq * seq) {
    7676    for (RE * e : *seq) {
    7777        if (!validate(e)) return false;
     
    8080}
    8181
    82 bool RE_Validator::validateAlt(Alt * alt) {
     82bool RE_Validator::validateAlt(const Alt * alt) {
    8383    for (RE * e : *alt) {
    8484        if (!validate(e)) return false;
     
    8787}
    8888
    89 bool RE_Validator::validateRep(Rep * r) {
     89bool RE_Validator::validateRep(const Rep * r) {
    9090    return validate(r->getRE());
    9191}
    9292
    93 bool RE_Validator::validateIntersect(Intersect * ix) {
     93bool RE_Validator::validateIntersect(const Intersect * ix) {
    9494    return validate(ix->getLH()) && validate(ix->getRH());
    9595}
    9696
    97 bool RE_Validator::validateDiff(Diff * d) {
     97bool RE_Validator::validateDiff(const Diff * d) {
    9898    return validate(d->getLH()) && validate(d->getRH());
    9999}
    100100
    101 bool RE_Validator::validateRange(Range * rg) {
     101bool RE_Validator::validateRange(const Range * rg) {
    102102    return validate(rg->getLo()) && validate(rg->getHi());
    103103}
    104104
    105 bool RE_Validator::validateGroup(Group * g) {
     105bool RE_Validator::validateGroup(const Group * g) {
    106106    return validate(g->getRE());
    107107}
    108108
    109 bool RE_Validator::validateAssertion(Assertion * a) {
     109bool RE_Validator::validateAssertion(const Assertion * a) {
    110110    return validate(a->getAsserted());
    111111}
    112112
    113 bool validateNamesDefined(RE * r) {
     113bool validateNamesDefined(const RE * r) {
    114114    return RE_Validator("NamesDefinedValidator").validateRE(r);
    115115}
     
    119119    AlphabetValidator(const cc::Alphabet * a) : RE_Validator("AlphabetValidator"), mAlphabet(a) {}
    120120   
    121     bool validateCC(CC * cc) override {return cc->getAlphabet() == mAlphabet;}
     121    bool validateCC(const CC * cc) override {return cc->getAlphabet() == mAlphabet;}
    122122private:
    123123    const cc::Alphabet * mAlphabet;
    124124};
    125125
    126 bool validateAlphabet(const cc::Alphabet * a, RE * r) {
     126bool validateAlphabet(const cc::Alphabet * a, const RE * r) {
    127127    return AlphabetValidator(a).validateRE(r);
    128128}
     
    132132    AssertionFreeValidator() : RE_Validator("AssertionFreeValidator") {}
    133133   
    134     bool validateAssertion(Assertion * a) override {return false;}
    135     bool validateStart(Start * s) override {return false;}
    136     bool validateEnd(End * e) override {return false;}
     134    bool validateAssertion(const Assertion * a) override {return false;}
     135    bool validateStart(const Start * s) override {return false;}
     136    bool validateEnd(const End * e) override {return false;}
    137137};
    138138
    139 bool validateAssertionFree(RE * r) {
     139bool validateAssertionFree(const RE * r) {
    140140    return AssertionFreeValidator().validateRE(r);
    141141}
  • icGREP/icgrep-devel/icgrep/re/validation.h

    r6186 r6256  
    1818namespace re {
    1919/* Check that all names within an RE are defined. */
    20 bool validateNamesDefined(RE * r);
     20bool validateNamesDefined(const RE * r);
    2121
    2222/* Check that all CCs within an RE have the given Alphabet */
    23 bool validateAlphabet(const cc::Alphabet * a, RE * r);
     23bool validateAlphabet(const cc::Alphabet * a, const RE * r);
    2424
    2525/* Check that the RE is free of zero-width assertions */
    26 bool validateAssertionFree(RE * r);
     26bool validateAssertionFree(const RE * r);
    2727
    2828/* A generic visitor for validation tasks.   The generic routines
     
    3434class RE_Validator {
    3535public:
    36     bool validateRE(RE * r);
     36    bool validateRE(const RE * r);
    3737    RE_Validator(std::string name = "") : mValidatorName(name) {}
    3838    virtual ~RE_Validator() {}
    3939protected:
    40     bool validate(RE * r);
    41     virtual bool validateName(Name * n);
    42     virtual bool validateStart(Start * s);
    43     virtual bool validateEnd(End * e);
    44     virtual bool validateCC(CC * cc);
    45     virtual bool validateSeq(Seq * s);
    46     virtual bool validateAlt(Alt * a);
    47     virtual bool validateRep(Rep * rep);
    48     virtual bool validateIntersect(Intersect * e);
    49     virtual bool validateDiff(Diff * d);
    50     virtual bool validateRange(Range * rg);
    51     virtual bool validateGroup(Group * g);
    52     virtual bool validateAssertion(Assertion * a);
     40    bool validate(const RE * r);
     41    virtual bool validateName(const Name * n);
     42    virtual bool validateStart(const Start * s);
     43    virtual bool validateEnd(const End * e);
     44    virtual bool validateCC(const CC * cc);
     45    virtual bool validateSeq(const Seq * s);
     46    virtual bool validateAlt(const Alt * a);
     47    virtual bool validateRep(const Rep * rep);
     48    virtual bool validateIntersect(const Intersect * e);
     49    virtual bool validateDiff(const Diff * d);
     50    virtual bool validateRange(const Range * rg);
     51    virtual bool validateGroup(const Group * g);
     52    virtual bool validateAssertion(const Assertion * a);
    5353private:
    5454    std::string mValidatorName;
    5555};
    56    
    57 bool validateAlphabet(const cc::Alphabet * a, RE * r);
    5856
    5957}
Note: See TracChangeset for help on using the changeset viewer.