Ignore:
Timestamp:
Dec 14, 2018, 6:09:23 AM (10 months ago)
Author:
cameron
Message:

Bug fix from Jeremy for negative assertions

File:
1 edited

Legend:

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

    r6224 r6227  
    3434    std::vector<RE *> makeContext(Iterator begin, Iterator end);
    3535    RE * transformAssertion(Assertion * a) override;
    36     RE * simplifyAsserted(RE * asserted, std::vector<RE *> const & context);
    37     RE * simplifyForwardAssertion(RE * asserted);
    38     RE * simplifyBackwardAssertion(RE * asserted);
     36    RE * simplifyPositiveAsserted(RE * asserted, std::vector<RE *> const & context);
     37    RE * simplifyNegativeAsserted(RE * asserted, std::vector<RE *> const & context);
    3938};
    4039
     
    9594    using Sense = Assertion::Sense;
    9695    AssertionPrep(Assertion * assertion);
    97     RE * transformCC(CC * cc) override;
    9896    RE * transformDiff(Diff * d) override;
    9997private:
    10098    Sense sense;
    101     Name * any;
    10299};
    103100
     
    168165RE * Context::transformAssertion(Assertion * a) {
    169166    using Kind = Assertion::Kind;
     167    using Sense = Assertion::Sense;
    170168    if (good() && ValidateAsserted{}.validateRE(a->getAsserted())) {
    171169        AssertionPrep prep{a};
    172170        RE * asserted = prep.transformRE(a->getAsserted());
     171        RE *(Context::* simpFunction)(RE *, std::vector<RE*> const &);
     172        switch(a->getSense()) {
     173        case Sense::Positive:
     174            simpFunction = &Context::simplifyPositiveAsserted;
     175            break;
     176        case Sense::Negative:       
     177            simpFunction = &Context::simplifyNegativeAsserted;
     178            break;
     179        default:
     180            llvm_unreachable("unexpected sense");
     181        }
     182
    173183        RE * simplifiedAsserted = nullptr;
    174184        if (a->getKind() == Kind::Lookahead) {
    175             simplifiedAsserted = simplifyAsserted(asserted, after);
     185            simplifiedAsserted = (this->*simpFunction)(asserted, after);
    176186        } else if (a->getKind() == Kind::Lookbehind) {
    177187            asserted = reverseAsserted(asserted);
    178             simplifiedAsserted = reverseAsserted(simplifyAsserted(asserted, before));
     188            simplifiedAsserted = reverseAsserted((this->*simpFunction)(asserted, before));
    179189        } else {
    180190            return a;
     
    189199                return makeSeq();
    190200            } else {
    191                 return makeAssertion(simplifiedAsserted, a->getKind(), Assertion::Sense::Positive);
     201                return makeAssertion(simplifiedAsserted, a->getKind(), a->getSense());
    192202            }
    193203        } else {
     
    207217}
    208218
    209 RE * Context::simplifyAsserted(RE * asserted, std::vector<RE *> const & context) {
     219RE * Context::simplifyPositiveAsserted(RE * asserted, std::vector<RE *> const & context) {
    210220    if (LLVM_LIKELY(llvm::isa<CC>(asserted))) {
    211221        if (context.size() > 0) {
     
    224234        }
    225235        return asserted;
    226     } else if (llvm::isa<Seq>(asserted)) {
     236    }
     237   
     238    else if (llvm::isa<Seq>(asserted)) {
    227239        Seq * a = llvm::cast<Seq>(asserted);
    228240        std::vector<RE *> elems{a->begin(), a->end()};
    229241        bool isWholeSeqSuperSet = context.size() >= a->size();
    230242        bool didChange = false;
    231         elems.reserve(a->size());
    232243
    233244        for (size_t i = 0; i < std::min(a->size(), context.size()); ++i) {
    234             RE * simplifiedElem = simplifyAsserted((*a)[i], std::vector<RE *>{context[i]});
     245            RE * simplifiedElem = simplifyPositiveAsserted((*a)[i], std::vector<RE *>{context[i]});
    235246            if (isEmptySet(simplifiedElem)) {
    236247                return makeAlt();
     
    261272            return asserted;
    262273        }
    263     } else if (llvm::isa<Alt>(asserted)) {
     274    }
     275   
     276    else if (llvm::isa<Alt>(asserted)) {
    264277        Alt * a = llvm::cast<Alt>(asserted);
    265278        std::vector<RE *> elems{};
     
    267280        bool did_change = false;
    268281        for (auto e : *a) {
    269             RE * e0 = simplifyAsserted(e, context);
     282            RE * e0 = simplifyPositiveAsserted(e, context);
    270283            if (e0 != e) {
    271284                elems.push_back(e0);
     
    281294            return asserted;
    282295        }
    283     } else if (llvm::isa<Name>(asserted)) {
     296    }
     297   
     298    else if (llvm::isa<Name>(asserted)) {
    284299        RE * def = llvm::cast<Name>(asserted)->getDefinition();
    285300        if (LLVM_UNLIKELY(def == nullptr)) {
    286301            llvm_unreachable("undefined name");
    287302        }
    288         RE * simp = simplifyAsserted(def, context);
     303        RE * simp = simplifyPositiveAsserted(def, context);
    289304        if (simp == def) {
    290305            return asserted;
     
    292307            return simp;
    293308        }
    294     } else {
    295         llvm_unreachable("Context::simplifyAsserted: Unexpected asserted value");
     309    }
     310   
     311    else {
     312        llvm_unreachable("Context::simplifyPositiveAsserted: Unexpected asserted value");
     313    }
     314}
     315
     316RE * Context::simplifyNegativeAsserted(RE * asserted, std::vector<RE *> const & context) {
     317    if (LLVM_LIKELY(llvm::isa<CC>(asserted))) {
     318        if (context.size() == 0) {
     319            return asserted;
     320        }
     321
     322        CC * assertedCC = llvm::cast<CC>(asserted);
     323        CC * contextCC = llvm::dyn_cast<CC>(context.front());
     324        if (LLVM_UNLIKELY(contextCC == nullptr)) {
     325            llvm_unreachable("invalid context");
     326        }
     327        CC * intersect = intersectCC(contextCC, assertedCC);
     328        if (intersect->empty()) {
     329            return makeSeq();
     330        } else if (subtractCC(contextCC, assertedCC)->empty()) {
     331            return makeAlt();
     332        } else if (intersect->size() == assertedCC->size()) {
     333            return asserted;
     334        } else {
     335            return intersect;
     336        }
     337    }
     338
     339    else if (llvm::isa<Seq>(asserted)) {
     340        Seq * a = llvm::cast<Seq>(asserted);
     341        std::vector<RE *> elems{a->begin(), a->end()};
     342        bool isWholeSeqSuperSet = context.size() >= a->size();
     343        bool didChange = false;
     344
     345        for (size_t i = 0; i < std::min(a->size(), context.size()); ++i) {
     346            RE * simplifiedElem = simplifyNegativeAsserted((*a)[i], std::vector<RE *>{context[i]});
     347            if (isEmptySet(simplifiedElem)) {
     348                return makeAlt();
     349            }
     350            if (simplifiedElem != (*a)[i]) {
     351                didChange = true;
     352                if (!isEmptySeq(simplifiedElem)) {
     353                    isWholeSeqSuperSet = false;
     354                    elems[i] = simplifiedElem;
     355                }
     356            } else {
     357                isWholeSeqSuperSet = false;
     358            }
     359        }
     360
     361        if (isWholeSeqSuperSet) {
     362            return makeSeq();
     363        }
     364
     365        if (didChange) {
     366            return makeSeq(elems.begin(), elems.end());
     367        } else {
     368            return asserted;
     369        }
     370    }
     371   
     372    else if (llvm::isa<Alt>(asserted)) {
     373        Alt * a = llvm::cast<Alt>(asserted);
     374        std::vector<RE *> elems{};
     375        elems.reserve(a->size());
     376        bool did_change = false;
     377        for (auto e : *a) {
     378            RE * e0 = simplifyNegativeAsserted(e, context);
     379            if (e0 != e) {
     380                did_change = true;
     381            } else {
     382                elems.push_back(e);
     383            }
     384        }
     385
     386        if (did_change) {
     387            return makeAlt(elems.begin(), elems.end());
     388        } else {
     389            return asserted;
     390        }
     391    }
     392   
     393    else if (llvm::isa<Name>(asserted)) {
     394        RE * def = llvm::cast<Name>(asserted)->getDefinition();
     395        if (LLVM_UNLIKELY(def == nullptr)) {
     396            llvm_unreachable("undefined name");
     397        }
     398        RE * simp = simplifyNegativeAsserted(def, context);
     399        if (simp == def) {
     400            return asserted;
     401        } else {
     402            return simp;
     403        }
     404    }
     405   
     406    else {
     407        llvm_unreachable("Context::simplifyNegativeAsserted: Unexpected asserted value");
    296408    }
    297409}
     
    302414: RE_Transformer("", NameTransformationMode::TransformDefinition),
    303415  sense(assertion->getSense())
    304 {
    305     this->any = llvm::cast<Name>(makeAny());
    306 }
    307 
    308 RE * AssertionPrep::transformCC(CC * cc) {
    309     if (sense == Sense::Negative) {
    310         return subtractCC(llvm::dyn_cast<CC>(any->getDefinition()), cc);
    311     } else {
    312         return cc;
    313     }
    314 }
     416{}
    315417
    316418RE * AssertionPrep::transformDiff(Diff * d) {
Note: See TracChangeset for help on using the changeset viewer.