Ignore:
Timestamp:
Sep 27, 2014, 11:12:13 PM (5 years ago)
Author:
nmedfort
Message:

Modified RE module to use a LLVM-like dyn_cast system; added 'make' functions to hide RE constructors.

File:
1 edited

Legend:

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

    r4187 r4194  
    1111#include <queue>
    1212
    13 RE* RE_Simplifier::simplify(RE * re) {
    14     RE * retVal = re;
    15     if (Alt * re_alt = dynamic_cast<Alt*>(re)) {
    16         Vector simplified_alt;
    17         for (RE * re : *re_alt) {
    18             simplified_alt.push_back(simplify(re));
     13namespace re {
     14
     15RE * RE_Simplifier::simplify(RE * re) {
     16    if (Alt * alt = dyn_cast<Alt>(re)) {
     17        for (auto i = alt->begin(); i != alt->end(); ++i) {
     18            *i = simplify(*i);
    1919        }
    20         retVal = makeAlt(simplified_alt);
     20        re = simplify(alt);
    2121    }
    22     else if (Seq * re_seq = dynamic_cast<Seq*>(re)) {
    23         Vector simplified_seq;
    24         for (RE * re : *re_seq)
    25         {
    26             simplified_seq.push_back(simplify(re));
     22    else if (Seq * seq = dyn_cast<Seq>(re)) {
     23        for (auto i = seq->begin(); i != seq->end(); ++i) {
     24            *i = simplify(*i);
    2725        }
    28         retVal = makeSeq(re_seq->getType(), simplified_seq);
     26        re = simplify(seq);
    2927    }
    30     else if (CC* re_cc = dynamic_cast<CC*>(re)) {
    31         retVal = re_cc;
     28    else if (Rep * rep = dyn_cast<Rep>(re)) {
     29        rep->setRE(simplify(rep->getRE()));
     30        simplify(rep);
    3231    }
    33     else if (Name* re_name = dynamic_cast<Name*>(re)) {
    34         retVal = new Name(re_name);
    35     }
    36     else if (Rep* re_rep = dynamic_cast<Rep*>(re)) {
    37         retVal = makeRep(simplify(re_rep->getRE()), re_rep->getLB(), re_rep->getUB());
    38     }
    39     else if (dynamic_cast<Start*>(re)) {
    40         retVal = new Start();
    41     }
    42     else if (dynamic_cast<End*>(re)) {
    43         retVal = new End();
    44     }
    45     return retVal;
     32    return re;
    4633}
    4734
    48 RE * RE_Simplifier::makeSeq(const Seq::Type type, Vector & list) {
     35RE * RE_Simplifier::simplify(Seq * seq) {
    4936    /*
    5037      mkSeq - make a sequence, but flatten.  Result might not be a Seq. If
     
    5239    */
    5340
    54     RE * re = nullptr;
    55     if (!list.empty()) {
    56         std::unique_ptr<Seq> seq = std::unique_ptr<Seq>(new Seq(type));
     41    RE * re = seq;
     42    if (!seq->empty()) {
     43        std::vector<RE*> list;
     44        list.reserve(seq->size());
    5745        // Reverse the order of the input list so we can more efficiently "pull" the first
    58         // character from the end. Note: this ought to be an inplace reversal.
    59         std::reverse(list.begin(), list.end());
     46        // character from the end. Note: this uses a linear inplace reversal.
     47        std::reverse(seq->begin(), seq->end());
    6048
    61         while (!list.empty()) {
    62             RE * next = list.back();
    63             list.pop_back();
    64             if (Seq * re_seq = dynamic_cast<Seq*>(next)) {
    65                 if (re_seq->getType() != Seq::Byte) {
    66                     // like above, insert the "subsequence" in reverse order
    67                     list.reserve(re_seq->size());
    68                     std::reverse_copy(re_seq->begin(), re_seq->end(), std::back_inserter(list));
     49        while (!seq->empty()) {
     50            RE * next = seq->back();
     51            seq->pop_back();
     52            if (Seq * re_seq = dyn_cast<Seq>(next)) {
     53                if (re_seq->getType() != Seq::Type::Byte) {
     54                    // like above, insert the "subsequence" to flatten in reverse order
     55                    std::reverse_copy(re_seq->begin(), re_seq->end(), std::back_inserter(*seq));
     56                    re_seq->clear();
     57                    delete re_seq;
    6958                    continue;
    7059                }
    7160            }
    72             seq->push_back(next);
     61            list.push_back(next);
    7362        }
    74         if (seq->size() == 1) {
    75             re = seq->back();
    76             seq->pop_back();
     63        if (list.size() == 1) {
     64            re = list.back();
     65            delete seq;
    7766        }
    7867        else {
    79             re = seq.release();
     68            seq->swap(list);
    8069        }
    8170    }
     
    9281 * @return simplified RE representing the Alt
    9382 */
    94 RE * RE_Simplifier::makeAlt(Vector & list) {
    95     RE * re = nullptr;
    96     if (!list.empty()) {
     83RE * RE_Simplifier::simplify(Alt * alt) {
     84    RE * re = alt;
     85    if (!alt->empty()) {
    9786
    98         std::unique_ptr<Alt> new_alt = std::unique_ptr<Alt>(new Alt());
    9987        std::queue<CC*> ccs;
    10088
    101         while (!list.empty()) {
    102             RE * next = list.back();
    103             list.pop_back();
    104             if (Alt * re_alt = dynamic_cast<Alt*>(next)) {
    105                 list.insert(list.end(), re_alt->begin(), re_alt->end());
     89        std::vector<RE *> list;
     90        while (!alt->empty()) {
     91            RE * next = alt->back();
     92            alt->pop_back();
     93            if (Alt * re_alt = dyn_cast<Alt>(next)) {
     94                alt->insert(alt->end(), re_alt->begin(), re_alt->end());
     95                re_alt->clear();
     96                delete re_alt;
    10697            }
    107             else if (CC * cc = dynamic_cast<CC*>(next)) {
     98            else if (CC * cc = dyn_cast<CC>(next)) {
    10899                ccs.push(cc);
    109100            }
    110101            else {
    111                 new_alt->push_back(next);
     102                list.push_back(next);
    112103            }
    113104        }
     
    117108                CC * a = ccs.front(); ccs.pop();
    118109                CC * b = ccs.front(); ccs.pop();
    119                 ccs.push(new CC(a, b));
     110                ccs.push(makeCC(a, b));
    120111            }
    121             new_alt->push_back(ccs.front());
     112            list.push_back(ccs.front());
    122113        }
    123114
    124         if (new_alt->size() == 1) {
     115        if (list.size() == 1) {
    125116            // if only one alternation exists, discard the Alt object itself and return the internal RE.
    126             re = new_alt->back();
    127             new_alt->pop_back();
     117            re = list.back();
     118            delete alt;
    128119        }
    129120        else {
    130             re = cse(new_alt.release());
     121            alt->swap(list);
    131122        }
    132123    }
     
    134125}
    135126
    136 inline RE * RE_Simplifier::cse(Alt * alt) {
    137 
    138 
    139 
    140 
    141     return alt;
    142 }
    143 
    144 
    145 RE * RE_Simplifier::makeRep(RE * re, const int lb, const int ub)
    146 {
    147     if (Rep* rep = dynamic_cast<Rep*>(re)) {
    148         if (((rep->getUB() == Rep::UNBOUNDED_REP) && (lb > 0)) ||
    149                 ((rep->getUB() == Rep::UNBOUNDED_REP) && (rep->getLB() <= 1))) {
    150             return new Rep(rep->getRE(), rep->getLB() * lb, Rep::UNBOUNDED_REP);
     127RE * RE_Simplifier::simplify(Rep * rep) {
     128    RE * re = rep->getRE();
     129    const int lb = rep->getLB();
     130    const int ub = rep->getUB();
     131    std::unique_ptr<Rep> janitor(rep);
     132    rep->setRE(nullptr);
     133    if (Rep * nrep = dyn_cast<Rep>(re)) {
     134        if (nrep->getUB() == Rep::UNBOUNDED_REP) {
     135            if ((lb > 0) || (nrep->getLB() <= 1)) {
     136                nrep->setLB(nrep->getLB() * lb);
     137                nrep->setUB(Rep::UNBOUNDED_REP);
     138                return simplify(nrep);
     139            }
     140            else if (lb == 0) {
     141                nrep->setLB(0);
     142                nrep->setUB(1);
     143                return simplify(nrep);
     144            }
    151145        }
    152         else if ((rep->getUB() == Rep::UNBOUNDED_REP) && (lb == 0)) {
    153             return new Rep(rep, 0, 1);
    154         }
    155         else if ((rep->getUB() * lb) >= (rep->getLB() * (lb + 1) - 1)) {
    156             return new Rep(rep->getRE(), rep->getLB() * lb, ubCombine(rep->getUB(), ub));
    157         }
    158         else {
    159             return new Rep(rep, lb, ub);
     146        else if ((nrep->getUB() * lb) >= (nrep->getLB() * (lb + 1) - 1)) {
     147            nrep->setLB(nrep->getUB() * lb);
     148            nrep->setUB(ubCombine(nrep->getUB(), ub));
     149            return simplify(nrep);
    160150        }
    161151    }
    162152    else {
    163         if (Seq * seq = dynamic_cast<Seq*>(re)) {
     153        if (Seq * seq = dyn_cast<Seq>(re)) {
    164154            if (seq->empty()) {
    165155                return seq;
    166156            }
    167157        }
    168 
    169158        if ((lb == 0) && (ub == 0)) {
    170             return new Seq();
     159            delete re;
     160            return makeSeq();
    171161        }
    172162        else if ((lb == 1) && (ub == 1)) {
    173163            return re;
    174164        }
    175         else {
    176             return new Rep(re, lb, ub);
    177         }
    178165    }
     166    rep->setRE(re);
     167    return janitor.release();
    179168}
    180169
     
    187176    }
    188177}
     178
     179}
Note: See TracChangeset for help on using the changeset viewer.