Changeset 6264


Ignore:
Timestamp:
Jan 2, 2019, 7:52:34 PM (3 months ago)
Author:
cameron
Message:

Restructured contextual assertion simplifier

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

Legend:

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

    r6259 r6264  
    1212#include "re_seq.h"
    1313#include "re_alt.h"
     14#include "re_diff.h"
    1415#include "re_nullable.h"
    1516#include <re/re_toolchain.h>
     
    6263        return makeSeq(elems.begin(), elems.end());
    6364    }
     65    RE * transformDiff(Diff * d) override { return d;}
    6466    RE * transformRep(Rep * r) override { return r;}
    6567    RE * transformAssertion(Assertion * a) override {
  • icGREP/icgrep-devel/icgrep/re/re_contextual_simplification.cpp

    r6259 r6264  
    1414#include <re/re_start.h>
    1515#include <re/re_end.h>
     16#include <re/re_reverse.h>
    1617#include <re/validation.h>
    1718#include <llvm/Support/Casting.h>
    1819#include <llvm/Support/ErrorHandling.h>
     20#include <llvm/Support/raw_ostream.h>
     21#include <re/printer_re.h>
    1922
    2023namespace re {
    21 
    22 class Context : private RE_Transformer {
     24   
     25// RE_Context identifies the position of a regular expression in its
     26// containing sequence, as well as the context of that containing sequence
     27// recursively.
     28
     29class RE_Context {
    2330public:
    24     Context(Seq * s, size_t idx);
    25     bool empty() const noexcept;
    26     RE * simplify(RE * re);
     31    RE_Context(RE_Context * c, Seq * s, unsigned pos) : parentContext(c), contextSeq(s), contextPos(pos) {}
     32    RE_Context priorContext();
     33    RE_Context followingContext();
     34    RE * currentItem();
     35   
    2736private:
    28     std::vector<RE *> before;
    29     std::vector<RE *> after;
    30 
    31     template<typename Iterator>
    32     std::vector<RE *> makeContext(Iterator begin, Iterator end);
    33     RE * transformStart(Start *) override;
    34     RE * transformEnd(End *) override;
    35     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);
     37    RE_Context * parentContext;
     38    Seq * contextSeq;
     39    unsigned contextPos;
    3940};
    40 
    41 
    42 class ResolvesToCC : public RE_Validator {
     41   
     42RE_Context RE_Context::priorContext() {
     43    if (contextPos == 0) {
     44        if (parentContext) {
     45            return parentContext->priorContext();
     46        }
     47        return RE_Context{nullptr, nullptr, 0};
     48    }
     49    return RE_Context{parentContext, contextSeq, contextPos - 1};
     50}
     51
     52RE_Context RE_Context::followingContext() {
     53    if (!contextSeq) return RE_Context{nullptr, nullptr, 0};
     54    if (contextPos >= contextSeq->size()-1) {
     55        if (parentContext) {
     56            return parentContext->followingContext();
     57        }
     58        return RE_Context{nullptr, nullptr, 0};
     59    }
     60    return RE_Context{parentContext, contextSeq, contextPos + 1};
     61}
     62
     63RE * RE_Context::currentItem() {
     64    if (contextSeq) return (*contextSeq)[contextPos];
     65    return nullptr;
     66}
     67
     68RE * simplifyCC(CC * assertedCC, CC * contextCC) {
     69    //llvm::errs() << "assertedCC:" << Printer_RE::PrintRE(assertedCC) << "\n";
     70    //llvm::errs() << "contextCC:" << Printer_RE::PrintRE(contextCC) << "\n";
     71    if ((*contextCC).subset(*assertedCC)) return makeSeq();
     72    if ((*contextCC).intersects(*assertedCC)) return assertedCC;
     73    return makeAlt();
     74}
     75
     76class SimplifyAsserted : public RE_Transformer {
    4377public:
    44     inline bool validateCC(const CC *) override { return true; }
    45     inline bool validateStart(const Start *) override { return false; }
    46     inline bool validateEnd(const End *) override { return false; }
    47     inline bool validateSeq(const Seq * s) override { return (s) && s->size() <= 1; }
    48     inline bool validateIntersect(const Intersect *) override { return false; }
    49     inline bool validateRange(const Range *) override { return false; }
    50     inline bool validateAssertion(const Assertion *) override { return false; }
     78    SimplifyAsserted(RE_Context & context, Assertion::Kind kind) :
     79        RE_Transformer("SimplifyAsserted"),
     80        mContext(context), mKind(kind) {}
     81       
     82    RE * transformName(Name * name) override {
     83        RE * defn = name->getDefinition();
     84        if (defn) {
     85            RE * s = transform(defn);
     86            if (s == defn) return name;
     87            else return s;
     88        }
     89        return name;
     90    }
     91   
     92    RE * transformSeq(Seq * s) override {
     93        RE_Context ctxt = mContext;
     94        bool allSatisfied = true;
     95        if (mKind == Assertion::Kind::Lookbehind) {
     96            for (unsigned i = s->size() - 1; i >= 0; i--) {
     97                RE * simplifiedElem = SimplifyAsserted(ctxt, mKind).transform((*s)[i]);
     98                if (isEmptySet(simplifiedElem)) {
     99                    return makeAlt();
     100                } else if (!isEmptySeq(simplifiedElem)) {
     101                    allSatisfied = false;
     102                } else if (allSatisfied && (i == 0)) {
     103                    return makeSeq();
     104                }
     105                ctxt = ctxt.priorContext();
     106                RE * prev = ctxt.currentItem();
     107                if (!prev || !llvm::isa<CC>(ctxt.currentItem())) {
     108                    return s;
     109                }
     110            }
     111        } else if (mKind == Assertion::Kind::Lookahead) {
     112            for (unsigned i = 0; i < s->size(); i++) {
     113                RE * simplifiedElem = SimplifyAsserted(ctxt, mKind).transform((*s)[i]);
     114                if (isEmptySet(simplifiedElem)) {
     115                    return makeAlt();
     116                } else if (!isEmptySeq(simplifiedElem)) {
     117                    allSatisfied = false;
     118                } else if (allSatisfied && (i == s->size() - 1)) {
     119                    return makeSeq();
     120                }
     121                ctxt = ctxt.followingContext();
     122                RE * next = ctxt.currentItem();
     123                if (!next || !llvm::isa<CC>(next)) {
     124                    return s;
     125                }
     126            }
     127        }
     128        return s;
     129    }
     130   
     131    RE * transformCC(CC * cc) override {
     132        RE * context = nullptr;
     133        if (mKind == Assertion::Kind::Lookbehind) {
     134            context = mContext.priorContext().currentItem();
     135        } else if (mKind == Assertion::Kind::Lookahead) {
     136            context = mContext.followingContext().currentItem();
     137        }
     138        if (context) {
     139            if (CC * contextCC = llvm::dyn_cast<CC>(context)) {
     140                return simplifyCC(cc, contextCC);
     141            }
     142        }
     143        return cc;
     144    }
     145private:
     146    RE_Context mContext;
     147    Assertion::Kind mKind;
    51148};
    52149
    53 class ValidateAsserted : public RE_Validator {
     150class ContextualAssertionSimplifier : public RE_Transformer {
    54151public:
    55     inline bool validateStart(const Start * s) override { return false; }
    56     inline bool validateEnd(const End * e) override { return false; }
    57     inline bool validateRep(const Rep * r) override { return false; }
    58     inline bool validateIntersect(const Intersect * i) override { return false; }
    59     inline bool validateRange(const Range * r) override { return false; }
    60     inline bool validateAssertion(const Assertion * a) override { return false; }
    61     inline bool validateDiff(const Diff * d) override {
    62         return ResolvesToCC{}.validateRE(d);
    63     }
    64     inline bool validateSeq(const Seq * s) override {
    65         auto ccValidator = ResolvesToCC{};
    66         for (auto e : *s) {
    67             if (!ccValidator.validateRE(e) || !validateRE(e)) {
    68                 return false;
    69             }
    70         }
    71         return true;
    72     }
     152    ContextualAssertionSimplifier(RE_Context ctxt = RE_Context(nullptr, nullptr, 0)) :
     153        RE_Transformer("ContextualAssertionSimplifier", NameTransformationMode::TransformDefinition),
     154        mContext(ctxt) {}
     155    RE * transformSeq(Seq * s) override {
     156        std::vector<RE *> t;
     157        t.reserve(s->size());
     158        bool changeSeen = false;
     159        for (unsigned i = 0; i < s->size(); i++) {
     160            RE * s_i = (*s)[i];
     161            RE * t_i = ContextualAssertionSimplifier(RE_Context(&mContext, s, i)).transformRE(s_i);
     162            t.push_back(t_i);
     163            if (t_i != s_i) changeSeen = true;
     164        }
     165        if (changeSeen) return makeSeq(t.begin(), t.end());
     166        return s;
     167    }
     168   
     169    RE * transformRep(Rep * r) override {
     170        RE * repeated = r->getRE();
     171        RE * t = ContextualAssertionSimplifier().transformRE(repeated);
     172        if (t == repeated) return r;
     173        return makeRep(t, r->getLB(), r->getUB());
     174    }
     175   
     176    RE * transformStart(Start * s) override {
     177        RE * prior = mContext.priorContext().currentItem();
     178        if (prior) {
     179            if (llvm::isa<Start>(prior)) {
     180                return makeSeq();
     181            } else if (llvm::isa<CC>(prior)) {
     182                return makeAlt();
     183            }
     184        }
     185        return s;
     186    }
     187   
     188    RE * transformEnd(End * e) override {
     189        RE * following = mContext.followingContext().currentItem();
     190        if (following) {
     191            if (llvm::isa<End>(following)) {
     192                return makeSeq();
     193            } else if (llvm::isa<CC>(following)) {
     194                return makeAlt();
     195            }
     196        }
     197        return e;
     198    }
     199   
     200    RE * transformAssertion(Assertion * a) override {
     201        RE * asserted = a->getAsserted();
     202        Assertion::Kind k = a->getKind();
     203        Assertion::Sense s = a->getSense();
     204        RE * t = SimplifyAsserted(mContext, k).transformRE(asserted);
     205        if (t == asserted) return a;
     206        return makeAssertion(t, k, s);
     207    }
     208   
     209    private:
     210        RE_Context mContext;
    73211};
    74 
    75 class ValidateZeroWidth : public RE_Validator {
    76 public:
    77     inline bool validateStart(const Start * s) { return true; }
    78     inline bool validateEnd(const End * e) { return true; }
    79     inline bool validateCC(const CC * cc) { return false; }
    80     inline bool validateRep(const Rep * rep) { return false; }
    81     inline bool validateIntersect(const Intersect * e) { return false; }
    82     inline bool validateRange(const Range * rg) { return false; }
    83     inline bool validateAssertion(const Assertion * a) { return true; }
    84 
    85     inline bool validateSeq(const Seq * s) {
    86         for (auto e : *s) {
    87             if (!validateRE(e)) return false;
    88         }
    89         return s->size() == 0;
    90     }
    91 };
    92 
    93 class AssertionPrep : public RE_Transformer {
    94 public:
    95     AssertionPrep(Assertion * assertion);
    96     RE * transformDiff(Diff * d) override;
    97 };
    98 
    99 
    100 
    101 Context::Context(Seq * s, size_t idx)
    102 : RE_Transformer("Contextual Engine", NameTransformationMode::TransformDefinition)
    103 {
    104     this->before = makeContext(s->rbegin() + (s->size() - idx), s->rend());
    105     this->after = makeContext(s->begin() + idx + 1, s->end());
    106 }
    107 
    108 bool Context::empty() const noexcept {
    109     return before.empty() && after.empty();
    110 }
    111 
    112 RE * Context::simplify(RE * re) {
    113     RE * rt = transformRE(re);
    114     return rt;
    115 }
    116 
    117 template<typename Iterator>
    118 std::vector<RE *> Context::makeContext(Iterator begin, Iterator end) {
    119     std::vector<RE *> rt{};
    120     for (auto i = begin; i != end; i++) {
    121         if (llvm::isa<CC>(*i)) {
    122             rt.push_back(*i);
    123         } else if (llvm::isa<Diff>(*i)) {
    124             Diff * d = llvm::cast<Diff>(*i);
    125             if (llvm::isa<CC>(d->getLH()) && llvm::isa<CC>(d->getRH())) {
    126                 rt.push_back(subtractCC(llvm::cast<CC>(d->getLH()), llvm::cast<CC>(d->getRH())));
    127             } else {
    128                 break;
    129             }
    130         } else if (ValidateZeroWidth().validateRE(*i)) {
    131             continue;
    132         } else if (llvm::isa<Name>(*i)) {
    133             if (llvm::isa<CC>(llvm::cast<Name>(*i)->getDefinition())) {
    134                 rt.push_back(llvm::cast<Name>(*i)->getDefinition());
    135             } else {
    136                 break;
    137             }
    138         } else {
    139             break;
    140         }
    141     }
    142     return rt;
    143 }
    144 
    145 RE * reverseAsserted(RE * re) {
    146     if (llvm::isa<Seq>(re)) {
    147         Seq * seq = llvm::cast<Seq>(re);
    148         return makeSeq(seq->rbegin(), seq->rend());
    149     } else {
    150         return re;
    151     }
    152 }
    153 
    154 RE * Context::transformStart(Start * s) {
    155     if (before.empty()) return s;
    156     if (llvm::isa<Start>(before.back())) return makeSeq();
    157     return makeAlt();
    158 }
    159 
    160 RE * Context::transformEnd(End * e) {
    161     if (after.empty()) return e;
    162     if (llvm::isa<End>(after.front())) return makeSeq();
    163     return makeAlt();
    164 }
    165 
    166 RE * Context::transformAssertion(Assertion * a) {
    167     Assertion::Sense sense = a->getSense();
    168     AssertionPrep prep{a};
    169     RE * asserted = prep.transformRE(a->getAsserted());
    170     RE * simplifiedAsserted = nullptr;
    171     if (a->getKind() == Assertion::Kind::Lookahead) {
    172         if (after.empty()) return a;
    173         simplifiedAsserted = simplifyAsserted(asserted, after);
    174     } else if (a->getKind() == Assertion::Kind::Lookbehind) {
    175         if (before.empty()) return a;
    176         asserted = reverseAsserted(asserted);
    177         simplifiedAsserted = reverseAsserted(simplifyAsserted(asserted, before));
    178     } else {
    179         return a;
    180     }
    181     if (simplifiedAsserted != nullptr) {
    182         if (simplifiedAsserted == asserted) {
    183             return a;
    184         } else if (isEmptySet(simplifiedAsserted)) {
    185             if (sense == Assertion::Sense::Positive) return makeAlt();
    186             else return makeSeq();
    187         } else if (isEmptySeq(simplifiedAsserted)) {
    188             if (sense == Assertion::Sense::Positive) return makeSeq();
    189             else return makeAlt();
    190         } else {
    191             return makeAssertion(simplifiedAsserted, a->getKind(), sense);
    192         }
    193     } else {
    194         return a;
    195     }
    196 }
    197 
    198 RE * Context::simplifyAsserted(RE * asserted, std::vector<RE *> const & context) {
    199     if (LLVM_LIKELY(llvm::isa<CC>(asserted))) {
    200         if (context.size() > 0) {
    201             CC * assertedCC = llvm::cast<CC>(asserted);
    202             CC * contextCC = llvm::cast<CC>(context[0]);
    203             CC * intersect = intersectCC(assertedCC, contextCC);
    204             if (intersect->empty()) {
    205                 return makeAlt();
    206             } else if (subtractCC(contextCC, assertedCC)->empty()) {
    207                 return makeSeq();
    208             } else if (*intersectCC(contextCC, assertedCC) == *assertedCC) {
    209                 return asserted;
    210             } else {
    211                 return intersect;
    212             }
    213         }
    214         return asserted;
    215     } else if (llvm::isa<Seq>(asserted)) {
    216         Seq * a = llvm::cast<Seq>(asserted);
    217         std::vector<RE *> elems{a->begin(), a->end()};
    218         bool isWholeSeqSuperSet = context.size() >= a->size();
    219         bool didChange = false;
    220 
    221         for (size_t i = 0; i < std::min(a->size(), context.size()); ++i) {
    222             RE * simplifiedElem = simplifyAsserted((*a)[i], std::vector<RE *>{context[i]});
    223             if (isEmptySet(simplifiedElem)) {
    224                 return makeAlt();
    225             }
    226             if (simplifiedElem != (*a)[i]) {
    227                 didChange = true;
    228                 if (!isEmptySeq(simplifiedElem)) {
    229                     isWholeSeqSuperSet = false;
    230                     elems[i] = simplifiedElem;
    231                 } else {
    232                     // a[i] is supperset of context[i]. Can't change a[i] to
    233                     // Seq[] as it will invalidate the Seq structure. Instead,
    234                     // set a[i] to context[i] the smaller of the two CCs.
    235                     elems[i] = context[i];
    236                 }
    237             } else {
    238                 isWholeSeqSuperSet = false;
    239             }
    240         }
    241 
    242         if (isWholeSeqSuperSet) {
    243             return makeSeq();
    244         }
    245 
    246         if (didChange) {
    247             return makeSeq(elems.begin(), elems.end());
    248         } else {
    249             return asserted;
    250         }
    251     } else if (llvm::isa<Alt>(asserted)) {
    252         Alt * a = llvm::cast<Alt>(asserted);
    253         std::vector<RE *> elems{};
    254         elems.reserve(a->size());
    255         bool did_change = false;
    256         for (auto e : *a) {
    257             RE * e0 = simplifyAsserted(e, context);
    258             if (e0 != e) {
    259                 elems.push_back(e0);
    260                 did_change = true;
    261             } else {
    262                 elems.push_back(e);
    263             }
    264         }
    265 
    266         if (did_change) {
    267             return makeAlt(elems.begin(), elems.end());
    268         } else {
    269             return asserted;
    270         }
    271     } else if (llvm::isa<Name>(asserted)) {
    272         RE * def = llvm::cast<Name>(asserted)->getDefinition();
    273         if (LLVM_UNLIKELY(def == nullptr)) {
    274             llvm_unreachable("undefined name");
    275         }
    276         RE * simp = simplifyAsserted(def, context);
    277         if (simp == def) {
    278             return asserted;
    279         } else {
    280             return simp;
    281         }
    282     } else {
    283         // For other types, we do not apply any simplification rules.
    284         return asserted;
    285     }
    286 }
    287 
    288 
    289 
    290 AssertionPrep::AssertionPrep(Assertion * assertion)
    291 : RE_Transformer("", NameTransformationMode::TransformDefinition)
    292 {
    293 }
    294 
    295 RE * AssertionPrep::transformDiff(Diff * d) {
    296     CC * lh = llvm::dyn_cast<CC>(transform(d->getLH()));
    297     CC * rh = llvm::dyn_cast<CC>(transform(d->getRH()));
    298     if (LLVM_UNLIKELY(lh == nullptr || rh == nullptr)) {
    299         llvm_unreachable("Nonvalidated use of Diff");
    300     }
    301     return transform(subtractCC(lh, rh));
    302 }
    303 
    304 RE * RE_ContextSimplifier::transformSeq(Seq * s) {
    305     std::vector<RE *> seq{};
    306     seq.reserve(s->size());
    307     bool hasChanged = false;
    308     for (size_t i = 0; i < s->size(); ++i) {
    309         if (isZeroWidth((*s)[i])) {
    310             Context context{s, i};
    311             if (context.empty()) {
    312                 seq.push_back((*s)[i]);
    313                 continue;
    314             }
    315             RE * simp = context.simplify((*s)[i]);
    316             if (simp != (*s)[i]) {
    317                 hasChanged = true;
    318                 if (isEmptySet(simp)) {
    319                     return simp; // Propagate failure
    320                 } else {
    321                     seq.push_back(simp);
    322                 }
    323             } else {
    324                 seq.push_back((*s)[i]);
    325             }
    326         } else {
    327             seq.push_back((*s)[i]);
    328         }
    329     }
    330 
    331 if (hasChanged) {
    332     auto rt = makeSeq(seq.begin(), seq.end());
    333     return rt;
    334 } else {
    335     return s;
    336 }
     212   
     213   
     214RE * simplifyAssertions(RE * r) {
     215    return ContextualAssertionSimplifier().transformRE(r);
    337216}
    338217
  • icGREP/icgrep-devel/icgrep/re/re_contextual_simplification.h

    r6224 r6264  
    1212namespace re {
    1313
    14 class RE_ContextSimplifier : public RE_Transformer {
    15 public:
    16     inline RE_ContextSimplifier() : RE_Transformer("ContextSimplification") {}
    17     RE * transformSeq(Seq * s) override;
    18 };
    19 
     14RE * simplifyAssertions(RE * r);
    2015}
    2116
  • icGREP/icgrep-devel/icgrep/re/re_diff.cpp

    r6256 r6264  
    1212#include <re/re_nullable.h>
    1313#include <re/validation.h>
     14#include <re/re_toolchain.h>
    1415#include <llvm/Support/Casting.h>
    1516
     
    3233}
    3334
     35class DiffResolver : public RE_Transformer {
     36public:
     37    DiffResolver() : RE_Transformer("DiffResolver") {}
     38    RE * transformDiff(Diff * d) override {
     39        RE * lh = d->getLH();
     40        RE * rh = d->getRH();
     41        if (defined<CC>(lh) && defined<CC>(rh)) {
     42            CC * lh_cc = defCast<CC>(lh);
     43            CC * rh_cc = defCast<CC>(rh);
     44            if (lh_cc->getAlphabet() == rh_cc->getAlphabet()) {
     45                return subtractCC(lh_cc, rh_cc);
     46            }
     47        }
     48        return d;
     49    }
     50};
     51
     52RE * resolveDiffs(RE * r) {
     53    return DiffResolver().transformRE(r);
    3454}
     55}
  • icGREP/icgrep-devel/icgrep/re/re_diff.h

    r6226 r6264  
    1919
    2020RE * makeDiff(RE * lh, RE * rh);
     21   
     22RE * resolveDiffs(RE * r);
    2123}
    2224
  • icGREP/icgrep-devel/icgrep/re/re_toolchain.cpp

    r6256 r6264  
    9090    }
    9191    r = removeUnneededCaptures(r);
    92     r = lookaheadPromotion(r);
    9392    r = resolveGraphemeMode(r, false /* not in grapheme mode at top level*/);
    9493    r = re::resolveUnicodeNames(r);
     
    101100        r = resolveCaseInsensitiveMode(r, globallyCaseInsensitive);
    102101    }
     102    r = simplifyAssertions(r);
     103    r = lookaheadPromotion(r);
    103104    return r;
    104105}
     
    123124        r = simplifyRE(r);
    124125    }
    125     r = RE_ContextSimplifier().transformRE(r);
     126    r = resolveDiffs(r);
    126127    r = resolveAnchors(r, makeAlt());
    127128    if (!DefiniteLengthBackReferencesOnly(r)) {
     
    337338        return nm;
    338339    }
    339     RE * const d = nm->getDefinition();
    340     if (LLVM_UNLIKELY(d == nullptr)) {
     340    RE * const defn = nm->getDefinition();
     341    if (LLVM_UNLIKELY(defn == nullptr)) {
    341342        UndefinedNameError(nm);
    342343    }
    343     return transform(d);
     344    RE * t = transform(defn);
     345    if (t == defn) return nm;
     346    return t;
    344347}
    345348
Note: See TracChangeset for help on using the changeset viewer.