Changeset 6282


Ignore:
Timestamp:
Jan 19, 2019, 2:44:48 PM (3 months ago)
Author:
cameron
Message:

Form simplified REs while applying context matching; simplify asserted CCs by intersection.

File:
1 edited

Legend:

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

    r6279 r6282  
    1010#include <re/re_name.h>
    1111#include <re/re_seq.h>
     12#include <re/re_empty_set.h>
    1213#include <re/re_alt.h>
    1314#include <re/re_assertion.h>
     
    235236}
    236237
    237 enum class MatchResult {Fail, Possible, Success};
     238//enum class MatchResult {Fail, Possible, Success};
    238239
    239240struct ContextMatchCursor {
    240241    RE_Context ctxt;
    241     MatchResult rslt;
     242    RE * rslt;
    242243};
    243244
    244245ContextMatchCursor ctxt_match(RE * re, Assertion::Kind kind, ContextMatchCursor cursor) {
    245     if (cursor.ctxt.empty()) return ContextMatchCursor{cursor.ctxt, MatchResult::Possible};
     246    if (cursor.ctxt.empty()) return ContextMatchCursor{cursor.ctxt, re};
    246247    if (CC * cc = dyn_cast<CC>(re)) {
    247248        RE_Context nextContext = cursor.ctxt;
    248249        RE * item = cursor.ctxt.currentItem();
     250        if (isa<Start>(item) || isa<End>(item)) {
     251            return ContextMatchCursor{cursor.ctxt, makeAlt()};
     252        }
    249253        if (!nonEmpty(item)) {
    250             return ContextMatchCursor{RE_Context{nullptr, nullptr, 0}, MatchResult::Possible};
     254            return ContextMatchCursor{RE_Context{nullptr, nullptr, 0}, re};
    251255        }
    252256        RE * contextSym = nullptr;
     
    261265        //errs() << "contextSym:" << Printer_RE::PrintRE(contextSym) << "\n";
    262266        if (CC * contextCC = dyn_cast<CC>(contextSym)) {
    263             if (!(*contextCC).intersects(*cc)) return ContextMatchCursor{cursor.ctxt, MatchResult::Fail};
    264             if ((cursor.rslt == MatchResult::Success) && ((*contextCC).subset(*cc))) {
    265                 return ContextMatchCursor{nextContext, MatchResult::Success};
    266             }
    267         }
    268         if (isa<Start>(contextSym) || isa<End>(contextSym)) {
    269             return ContextMatchCursor{cursor.ctxt, MatchResult::Fail};
    270         }
    271         return ContextMatchCursor{nextContext, MatchResult::Possible};
     267            if (!(*contextCC).intersects(*cc)) return ContextMatchCursor{cursor.ctxt, makeAlt()};
     268            if (isEmptySeq(cursor.rslt) && (*contextCC).subset(*cc)) {
     269                return ContextMatchCursor{nextContext, makeSeq()};
     270            }
     271            return ContextMatchCursor{nextContext, intersectCC(contextCC, cc)};
     272        }
     273        return ContextMatchCursor{nextContext, re};
    272274    } else if (isa<Start>(re)) {
    273275        if (kind == Assertion::Kind::Lookbehind) {
    274276            RE * contextSym = finalSym(cursor.ctxt.currentItem());
    275277            RE_Context nextContext = cursor.ctxt.priorCCorNull();
    276             if (isa<Start>(contextSym)) return ContextMatchCursor{nextContext, MatchResult::Success};
    277         }
    278         return ContextMatchCursor{cursor.ctxt, MatchResult::Fail};
     278            if (isa<Start>(contextSym)) return ContextMatchCursor{nextContext, makeSeq()};
     279        }
     280        return ContextMatchCursor{cursor.ctxt, makeAlt()};
    279281    } else if (isa<End>(re)) {
    280282        if (kind == Assertion::Kind::Lookahead) {
    281283            RE * contextSym = firstSym(cursor.ctxt.currentItem());
    282284            RE_Context nextContext = cursor.ctxt.followingCCorNull();
    283             if (isa<End>(contextSym)) return ContextMatchCursor{nextContext, MatchResult::Success};
    284         }
    285         return ContextMatchCursor{cursor.ctxt, MatchResult::Fail};
     285            if (isa<End>(contextSym)) return ContextMatchCursor{nextContext, makeSeq()};
     286        }
     287        return ContextMatchCursor{cursor.ctxt, makeAlt()};
    286288    } else if (Name * n = dyn_cast<Name>(re)) {
    287289        RE * def = n->getDefinition();
    288290        ContextMatchCursor submatch = ctxt_match(def, kind, cursor);
    289         if (submatch.rslt == MatchResult::Fail) return submatch;
     291        if (isEmptySet(submatch.rslt)) return submatch;
    290292        if (n->getType() == Name::Type::Reference) {
    291             return ContextMatchCursor{submatch.ctxt, MatchResult::Possible};
     293            return ContextMatchCursor{submatch.ctxt, re};
    292294        } else {
    293295            return submatch;
    294296        }
    295297    } else if (Alt * alt = dyn_cast<Alt>(re)) {
    296         ContextMatchCursor bestSoFar = ContextMatchCursor{cursor.ctxt, MatchResult::Fail};
     298        ContextMatchCursor bestSoFar = ContextMatchCursor{cursor.ctxt, makeAlt()};
    297299        for (RE * a: *alt) {
    298300            ContextMatchCursor a_match = ctxt_match(a, kind, cursor);
    299             if (a_match.rslt == MatchResult::Success) return a_match;
    300             if (a_match.rslt == MatchResult::Possible) bestSoFar = a_match;
     301            if (isEmptySeq(a_match.rslt)) return a_match;
     302            if (!isEmptySet(a_match.rslt)) bestSoFar = a_match;
    301303        }
    302304        return bestSoFar;
     
    306308            for (RE * s: *seq) {
    307309                working = ctxt_match(s, kind, working);
    308                 if (working.rslt == MatchResult::Fail) return working;
     310                if (isEmptySet(working.rslt)) return working;
    309311            }
    310312        } else {
    311313            for (auto i = seq->rbegin(); i != seq->rend(); ++i) {
    312314                working = ctxt_match(*i, kind, working);
    313                 if (working.rslt == MatchResult::Fail) return working;
    314             }
    315         }
    316         return working;
     315                if (isEmptySet(working.rslt)) return working;
     316            }
     317        }
     318        if (isEmptySeq(working.rslt)) {
     319            return working;
     320        } else {
     321            return ContextMatchCursor{working.ctxt, seq};
     322        }
     323       
    317324    } else if (const Rep * rep = dyn_cast<Rep>(re)) {
    318325        int lb = rep->getLB();
     
    322329        for (int i = 0; i < lb; i++) {
    323330            lb_cursor = ctxt_match(repeated, kind, lb_cursor);
    324             if (lb_cursor.rslt == MatchResult::Fail) return lb_cursor;
     331            if (isEmptySet(lb_cursor.rslt)) return lb_cursor;
    325332        }
    326333        if (ub == Rep::UNBOUNDED_REP) {
     
    328335            for (;;) {
    329336                ContextMatchCursor next = ctxt_match(repeated, kind, star_rslt);
    330                 if (next.rslt == MatchResult::Fail) return star_rslt;
     337                if (isEmptySet(next.rslt)) return star_rslt;
    331338                if (next.ctxt.empty()) return next;
    332339                star_rslt = next;
     
    336343            for (int i = lb; i < ub; i++) {
    337344                ContextMatchCursor next = ctxt_match(repeated, kind, ub_cursor);
    338                 if (next.rslt == MatchResult::Fail) return ub_cursor;
     345                if (isEmptySet(next.rslt)) return ub_cursor;
    339346                if (next.ctxt.empty()) return next;
    340347                ub_cursor = next;
     
    345352        ContextMatchCursor lh_match = ctxt_match(d->getLH(), kind, cursor);
    346353        ContextMatchCursor rh_match = ctxt_match(d->getRH(), kind, cursor);
    347         if (rh_match.rslt == MatchResult::Fail) return lh_match;
    348         if (rh_match.rslt == MatchResult::Success) return ContextMatchCursor{cursor.ctxt, MatchResult::Fail};
    349         if (lh_match.rslt == MatchResult::Fail) return lh_match;
    350         return ContextMatchCursor{lh_match.ctxt, MatchResult::Possible};
     354        if (isEmptySet(rh_match.rslt)) return lh_match;
     355        if (isEmptySeq(rh_match.rslt)) return ContextMatchCursor{cursor.ctxt, makeAlt()};
     356        if (isEmptySet(lh_match.rslt)) return lh_match;
     357        return ContextMatchCursor{lh_match.ctxt, re};
    351358    } else if (const Intersect * x = dyn_cast<Intersect>(re)) {
    352359        ContextMatchCursor lh_match = ctxt_match(x->getLH(), kind, cursor);
    353360        ContextMatchCursor rh_match = ctxt_match(x->getRH(), kind, cursor);
    354         if (lh_match.rslt == MatchResult::Fail) return lh_match;
    355         if (rh_match.rslt == MatchResult::Fail) return rh_match;
    356         if (lh_match.rslt == MatchResult::Success) return rh_match;
    357         if (rh_match.rslt == MatchResult::Success) return lh_match;
     361        if (isEmptySet(lh_match.rslt)) return lh_match;
     362        if (isEmptySet(rh_match.rslt)) return rh_match;
     363        if (isEmptySeq(lh_match.rslt)) return rh_match;
     364        if (isEmptySeq(rh_match.rslt)) return lh_match;
    358365        return lh_match;
    359366    } else if (const Assertion * a = dyn_cast<Assertion>(re)) {
    360367        if (a->getKind() == kind) {
    361368            ContextMatchCursor assertResult = ctxt_match(a->getAsserted(), kind, cursor);
    362             if (assertResult.rslt == MatchResult::Possible) return ContextMatchCursor{cursor.ctxt, MatchResult::Possible};
    363             if ((assertResult.rslt == MatchResult::Success) == (a->getSense() == Assertion::Sense::Positive)) {
    364                 return ContextMatchCursor{cursor.ctxt, MatchResult::Success};
    365             }
    366             return ContextMatchCursor{cursor.ctxt, MatchResult::Fail};
    367         }
    368         return ContextMatchCursor{cursor.ctxt, MatchResult::Possible};
    369     }
    370     return ContextMatchCursor{cursor.ctxt, MatchResult::Possible};
     369            if (!isEmptySet(assertResult.rslt)) return ContextMatchCursor{cursor.ctxt, re};
     370            if (isEmptySeq(assertResult.rslt) == (a->getSense() == Assertion::Sense::Positive)) {
     371                return ContextMatchCursor{cursor.ctxt, makeSeq()};
     372            }
     373            return ContextMatchCursor{cursor.ctxt, makeAlt()};
     374        }
     375        return ContextMatchCursor{cursor.ctxt, re};
     376    }
     377    return ContextMatchCursor{cursor.ctxt, re};
    371378}
    372379   
     
    441448            return a;
    442449        }
    443         ContextMatchCursor x = ctxt_match(asserted, k, ContextMatchCursor{ctxt, MatchResult::Success});
    444         if (x.rslt == MatchResult::Possible) return a;
    445         if ((x.rslt == MatchResult::Success) == (s == Assertion::Sense::Positive)) return makeSeq();
    446         return makeAlt();
     450        ContextMatchCursor x = ctxt_match(asserted, k, ContextMatchCursor{ctxt, makeSeq()});
     451        return makeAssertion(x.rslt, k, s);
    447452    }
    448453   
Note: See TracChangeset for help on using the changeset viewer.