Changeset 4203


Ignore:
Timestamp:
Oct 2, 2014, 3:22:19 PM (5 years ago)
Author:
nmedfort
Message:

Performance bug fix

Location:
icGREP/icgrep-devel/icgrep
Files:
15 edited

Legend:

Unmodified
Added
Removed
  • icGREP/icgrep-devel/icgrep/compiler.cpp

    r4199 r4203  
    8181    //Optimization passes to simplify the AST.
    8282    re_ast = RE_Nullable::removeNullablePrefix(re_ast);
     83    #ifdef DEBUG_PRINT_RE_AST
     84    std::cerr << "RemoveNullablePrefix:" << std::endl << Printer_RE::PrintRE(re_ast) << std::endl;
     85    #endif
    8386
    8487    re_ast = RE_Nullable::removeNullableSuffix(re_ast);
     88    #ifdef DEBUG_PRINT_RE_AST
     89    std::cerr << "RemoveNullableSuffix:" << std::endl << Printer_RE::PrintRE(re_ast) << std::endl;
     90    #endif
    8591
    8692    re_ast = RE_Simplifier::simplify(re_ast);
    87 
    8893    #ifdef DEBUG_PRINT_RE_AST
    8994    //Print to the terminal the AST that was generated by the simplifier.
  • icGREP/icgrep-devel/icgrep/re/re_alt.h

    r4194 r4203  
    99
    1010#include "re_re.h"
     11#include "re_cc.h"
     12#include <queue>
    1113
    1214namespace re {
     
    2527protected:
    2628    friend Alt * makeAlt();
    27     friend Alt * makeAlt(Alt::iterator, Alt::iterator);
     29    template<typename iterator> friend RE * makeAlt(iterator, iterator);
    2830    Alt()
    2931    : Vector(ClassTypeId::Alt) {
    30 
    31     }
    32     Alt(const Alt & alt)
    33     : Vector(ClassTypeId::Alt, alt.cbegin(), alt.cend(), true) {
    3432
    3533    }
     
    3735    : Vector(ClassTypeId::Alt, begin, end) {
    3836
     37    }   
     38private:
     39    template<typename iterator>
     40    void construct(iterator begin, iterator end, std::queue<CC*> & ccQ) {
     41        for (auto i = begin; i != end; ++i) {
     42            if (Alt * alt = dyn_cast<Alt>(*i)) {
     43                construct(alt->begin(), alt->end(), ccQ);
     44                continue;
     45            }
     46            else if (CC * cc = dyn_cast<CC>(*i)) {
     47                ccQ.push(cc);
     48                continue;
     49            }
     50            push_back(*i);
     51        }
    3952    }
    4053};
     54
     55/**
     56 * @brief makeAlt
     57 *
     58 * Build an Alt, flattening alternative subgroups, and combining character classes and
     59 * move character classes towards the end of the list to ensure that all combinations are found.
     60 *
     61 * @param list
     62 * @return simplified RE representing the Alt
     63 */
    4164
    4265inline Alt * makeAlt() {
     
    4467}
    4568
    46 inline Alt * makeAlt(Alt::iterator begin, Alt::iterator end) {
    47     return new Alt(begin, end);
     69template<typename iterator>
     70RE * makeAlt(iterator begin, iterator end) {
     71    Alt * alt = makeAlt();
     72    std::queue<CC*> ccQ;
     73    alt->construct(begin, end, ccQ);
     74    if (!ccQ.empty()) {
     75        while (ccQ.size() > 1) {
     76            CC * a = ccQ.front(); ccQ.pop();
     77            CC * b = ccQ.front(); ccQ.pop();
     78            ccQ.push(makeCC(a, b));
     79        }
     80        alt->push_back(ccQ.front());
     81    }
     82    if (alt->size() == 1) {
     83        return alt->back();
     84    }
     85    return alt;
     86}
     87
     88inline RE * makeAlt(RE::InitializerList list) {
     89    return makeAlt(list.begin(), list.end());
    4890}
    4991
  • icGREP/icgrep-devel/icgrep/re/re_compiler.cpp

    r4200 r4203  
    198198        compile(*i, cg_state);
    199199        while (++i != alt->end()) {
    200             std::string oldsym = cg_state.newsym;
     200            std::string alt1 = cg_state.newsym;
    201201            cg_state.newsym = startsym;
    202202            compile(*i, cg_state);
    203             std::string altsym = symgen.get("alt");
    204             cg_state.stmtsl.push_back(make_assign(altsym, make_or(make_var(oldsym), make_var(cg_state.newsym))));
    205             cg_state.newsym = altsym;
     203            std::string newsym = symgen.get("alt");
     204            cg_state.stmtsl.push_back(make_assign(newsym, make_or(make_var(alt1), make_var(cg_state.newsym))));
     205            cg_state.newsym = newsym;
    206206        }
    207207    }
  • icGREP/icgrep-devel/icgrep/re/re_nullable.cpp

    r4197 r4203  
    66#include "re_rep.h"
    77#include "re_simplifier.h"
    8 
     8#include <printer_re.h>
     9#include <iostream>
    910/*
    1011
     
    1920RE * RE_Nullable::removeNullablePrefix(RE * re) {
    2021    if (Seq * seq = dyn_cast<Seq>(re)) {
    21         re = removeNullablePrefix(seq);
     22        std::vector<RE*> list;
     23        for (auto i = seq->begin(); i != seq->end(); ++i) {
     24            if (!isNullable(*i)) {
     25                list.push_back(removeNullablePrefix(*i));
     26                std::copy(++i, seq->end(), std::back_inserter(list));
     27                break;
     28            }
     29        }
     30        re = makeSeq(seq->getType(), list.begin(), list.end());
    2231    }
    2332    else if (Alt * alt = dyn_cast<Alt>(re)) {
     33        std::vector<RE*> list;
    2434        for (auto i = alt->begin(); i != alt->end(); ++i) {
    25             *i = removeNullablePrefix(*i);
     35            list.push_back(removeNullablePrefix(*i));
    2636        }
    27         re = alt;
     37        re = makeAlt(list.begin(), list.end());
    2838    }
    2939    else if (Rep * rep = dyn_cast<Rep>(re)) {
     
    3242        }
    3343        else if (hasNullablePrefix(rep->getRE())) {
    34             Seq * seq = makeSeq();
    35             seq->push_back(removeNullablePrefix(rep->getRE()->clone()));
    36             seq->push_back(makeRep(rep->getRE(), rep->getLB() - 1, rep->getLB() - 1));
    37             rep->setRE(nullptr);
    38             delete rep;
    39             re = RE_Simplifier::simplify(seq);
     44            re = makeSeq({removeNullablePrefix(rep->getRE()), makeRep(rep->getRE(), rep->getLB() - 1, rep->getLB() - 1)});
    4045        }
    4146        else {
    42             re = RE_Simplifier::simplify(rep);
     47            re = makeRep(rep->getRE(), rep->getLB(), rep->getLB());
    4348        }
    4449    }
     
    4651}
    4752
    48 inline Seq * RE_Nullable::removeNullablePrefix(Seq * seq) {
    49     if (!seq->empty()) {
    50         std::vector<RE *> list;
    51         auto i = seq->begin();
    52         // find the first non-nullable prefix
    53         while (i != seq->end() && isNullable(*i)) {
    54             delete *i;
    55             ++i;
    56         }
    57         if (i != seq->end()) {
    58             // push the first non-nullable seq item to the front of the new_seq
    59             list.push_back(removeNullablePrefix(*i));
    60             std::copy(++i, seq->end(), std::back_inserter(list));
    61         }
    62         seq->swap(list);
    63     }
    64     return seq;
    65 }
    66 
    6753RE * RE_Nullable::removeNullableSuffix(RE * re) {
    6854    if (Seq * seq = dyn_cast<Seq>(re)) {
    69         re = removeNullableSuffix(seq);
     55        std::vector<RE*> list;
     56        for (auto i = seq->rbegin(); i != seq->rend(); ++i) {
     57            if (!isNullable(*i)) {
     58                std::copy(seq->begin(), (i + 1).base(), std::back_inserter(list));
     59                list.push_back(removeNullableSuffix(*i));
     60                break;
     61            }
     62        }
     63        re = makeSeq(seq->getType(), list.begin(), list.end());
    7064    }
    7165    else if (Alt* alt = dyn_cast<Alt>(re)) {
     66        std::vector<RE*> list;
    7267        for (auto i = alt->begin(); i != alt->end(); ++i) {
    73             *i = removeNullableSuffix(*i);
     68            list.push_back(removeNullableSuffix(*i));
    7469        }
     70        re = makeAlt(list.begin(), list.end());
    7571    }
    7672    else if (Rep * rep = dyn_cast<Rep>(re)) {
    7773        if ((rep->getLB() == 0) || (isNullable(rep->getRE()))) {
    78             delete rep;
    7974            re = makeSeq();
    8075        }
    8176        else if (hasNullableSuffix(rep->getRE())) {
    82             Seq * seq = makeSeq();
    83             seq->push_back(RE_Simplifier::simplify(makeRep(rep->getRE()->clone(), rep->getLB() - 1, rep->getLB() - 1)));
    84             seq->push_back(removeNullableSuffix(rep->getRE()));
    85             rep->setRE(nullptr);
    86             delete rep;
    87             re = RE_Simplifier::simplify(seq);
     77            re = makeSeq({makeRep(rep->getRE(), rep->getLB() - 1, rep->getLB() - 1), removeNullableSuffix(rep->getRE())});
    8878        }
    8979        else {
    90             re = RE_Simplifier::simplify(rep);
     80            re = makeRep(rep->getRE(), rep->getLB(), rep->getLB());
    9181        }
    9282    }
     
    9484}
    9585
    96 inline Seq * RE_Nullable::removeNullableSuffix(Seq * seq) {
    97     if (!seq->empty()) {
    98         std::vector<RE *> list;
    99         auto i = seq->end();
    100         // find the last non-nullable suffix
    101         while (i != seq->begin() && isNullable(*--i)) {
    102             delete *i;
    103         }
    104         if (i != seq->begin()) {
    105             std::copy(seq->begin(), i, std::back_inserter(list));
    106             list.push_back(removeNullableSuffix(*i));
    107         }
    108         seq->swap(list);
    109     }
    110     return seq;
    111 }
    112 
    11386bool RE_Nullable::isNullable(const RE * re) {
    11487    if (const Seq * re_seq = dyn_cast<const Seq>(re)) {
    115         return isNullable(re_seq);
     88        for (const RE * re : *re_seq) {
     89            if (!isNullable(re)) {
     90                return false;
     91            }
     92        }
     93        return true;
    11694    }
    117     else if (const Alt* re_alt = dyn_cast<const Alt>(re)) {
    118         return isNullable(re_alt);
     95    else if (const Alt * re_alt = dyn_cast<const Alt>(re)) {
     96        for (const RE * re : *re_alt) {
     97            if (isNullable(re)) {
     98                return true;
     99            }
     100        }
    119101    }
    120102    else if (const Rep* re_rep = dyn_cast<const Rep>(re)) {
     
    122104    }
    123105    return false;
    124 }
    125 
    126 inline bool RE_Nullable::isNullable(const Vector * vec) {
    127     for (const RE * re : *vec) {
    128         if (!isNullable(re)) {
    129             return false;
    130         }
    131     }
    132     return true;
    133106}
    134107
     
    139112    }
    140113    else if (const Alt * alt = dyn_cast<const Alt>(re)) {
    141         if (!alt->empty()) {
    142             nullable = true;
    143             for (const RE * re : *alt) {
    144                 if (!hasNullablePrefix(re)) {
    145                     nullable = false;
    146                     break;
    147                 }
     114        for (const RE * re : *alt) {
     115            if (hasNullablePrefix(re)) {
     116                nullable = true;
     117                break;
    148118            }
    149119        }
    150120    }
    151121    else if (const Rep * rep = dyn_cast<const Rep>(re)) {
    152         nullable = hasNullablePrefix(rep->getRE());
     122        nullable = true;
     123        if (rep->getLB() == rep->getUB()) {
     124            nullable = hasNullablePrefix(rep->getRE());
     125        }
    153126    }
    154127    return nullable;
     
    161134    }
    162135    else if (const Alt * alt = dyn_cast<const Alt>(re)) {
    163         if (!alt->empty()) {
    164             nullable = true;
    165             for (const RE * re : *alt) {
    166                 if (!hasNullableSuffix(re)) {
    167                     nullable = false;
    168                     break;
    169                 }
     136        for (const RE * re : *alt) {
     137            if (hasNullableSuffix(re)) {
     138                nullable = true;
     139                break;
    170140            }
    171141        }
    172142    }
    173143    else if (const Rep * rep = dyn_cast<const Rep>(re)) {
    174         nullable = hasNullableSuffix(rep->getRE());
     144        nullable = true;
     145        if (rep->getLB() == rep->getUB()) {
     146            nullable = hasNullableSuffix(rep->getRE());
     147        }
    175148    }
    176149    return nullable;
  • icGREP/icgrep-devel/icgrep/re/re_nullable.h

    r4197 r4203  
    1818    static bool hasNullablePrefix(const RE * re);
    1919    static bool hasNullableSuffix(const RE * re);
    20     static Seq * removeNullablePrefix(Seq * seq);
    21     static Seq * removeNullableSuffix(Seq * seq);
    2220};
    2321
  • icGREP/icgrep-devel/icgrep/re/re_parser.cpp

    r4194 r4203  
    3333}
    3434
    35 template<class T>
    36 inline static RE * simplify_vector(T & vec) {
    37     RE * re;
    38     if (vec->size() == 1) {
    39         re = vec->back();
    40         vec->pop_back();
    41     }
    42     else {
    43         re = vec.release();
    44     }
    45     return re;
    46 }
    47 
    4835RE * RE_Parser::parse_alt(const bool subexpression) {
    49     std::unique_ptr<Alt> alt(makeAlt());
     36    std::vector<RE *> alt;
    5037    for (;;) {
    51         alt->push_back(parse_seq());
     38        alt.push_back(parse_seq());
    5239        if (_cursor == _end || *_cursor != '|') {
    5340            break;
     
    5542        ++_cursor; // advance past the alternation character '|'
    5643    }
    57     if (alt->empty())
     44    if (alt.empty())
    5845    {
    5946        throw NoRegularExpressionFound();
     
    6855        throw ParseFailure("Cannot fully parse statement!");
    6956    }
    70     return simplify_vector(alt);
     57    return makeAlt(alt.begin(), alt.end());
    7158}
    7259
    7360inline RE * RE_Parser::parse_seq() {
    74     std::unique_ptr<Seq> seq(makeSeq());
     61    std::vector<RE *> seq;
    7562    for (;;) {
    7663        RE * re = parse_next_token();
     
    7865            break;
    7966        }
    80         seq->push_back(extend_item(re));
    81     }
    82     if (seq->empty())
     67        seq.push_back(extend_item(re));
     68    }
     69    if (seq.empty())
    8370    {
    8471        throw NoRegularExpressionFound();
    8572    }
    86     return simplify_vector(seq);
     73    return makeSeq(Seq::Type::Normal, seq.begin(), seq.end());
    8774}
    8875
     
    159146    ++_cursor;
    160147    throw_incomplete_expression_error_if_end_of_stream();
    161     Rep * rep = nullptr;
     148    RE * rep = nullptr;
    162149    unsigned lower_bound;
    163150    if (*_cursor == ',') {
  • icGREP/icgrep-devel/icgrep/re/re_re.h

    r4200 r4203  
    5151        return mClassTypeId;
    5252    }
     53    typedef std::initializer_list<RE *> InitializerList;
    5354    virtual RE * clone() const = 0;
    5455    virtual ~RE() = 0;
  • icGREP/icgrep-devel/icgrep/re/re_reducer.cpp

    r4194 r4203  
    1212
    1313RE * RE_Reducer::reduce(RE * re, std::map<std::string, RE*>& re_map) {
    14     RE * retVal = re;
    1514    assert (re);
    1615    if (Alt * alt = dyn_cast<Alt>(re)) {
     
    2726            std::string seqname = seq->getName();
    2827            re_map.insert(make_pair(seqname, seq));
    29             retVal = makeName(seqname, false, Name::Type::Unicode);
     28            re = makeName(seqname, false, Name::Type::Unicode);
    3029        }
    3130    }
     
    3837        re_map.insert(make_pair(ccname, cc));
    3938        //return a new name class with the name of the character class.
    40         retVal = makeName(ccname);
     39        re = makeName(ccname);
    4140    }
    42     return retVal;
     41    return re;
    4342}
    4443
  • icGREP/icgrep-devel/icgrep/re/re_rep.cpp

    r4187 r4203  
    66
    77#include "re_rep.h"
     8#include "re_seq.h"
     9
     10namespace re {
     11
     12inline int ubCombine(const int h1, const int h2) {
     13    if ((h1 == Rep::UNBOUNDED_REP) || (h2 == Rep::UNBOUNDED_REP)) {
     14        return Rep::UNBOUNDED_REP;
     15    }
     16    else {
     17        return h1 * h2;
     18    }
     19}
     20
     21RE * makeRep(RE * re, const int lb, const int ub) {
     22    if (Rep * rep = dyn_cast<Rep>(re)) {
     23        if (rep->getUB() == Rep::UNBOUNDED_REP && ((lb > 0) || (rep->getLB() <= 1))) {
     24            return new Rep(rep->getRE(), rep->getLB() * lb, Rep::UNBOUNDED_REP);
     25        }
     26        else if ((rep->getUB() == Rep::UNBOUNDED_REP) && (lb == 0)) {
     27            return new Rep(rep, 0, 1);
     28        }
     29        else if (lb == ub) {
     30            return new Rep(rep->getRE(), lb * rep->getLB(), ub * rep->getUB());
     31        }
     32        else if ((rep->getUB() * lb) >= (rep->getLB() * (lb + 1) - 1)) {
     33            return new Rep(rep->getRE(), rep->getUB() * lb, ubCombine(rep->getUB(), ub));
     34        }
     35    }
     36    else {
     37        if (Seq * seq = dyn_cast<Seq>(re)) {
     38            if (seq->empty()) {
     39                return seq;
     40            }
     41        }
     42        if ((lb == 0) && (ub == 0)) {
     43            return makeSeq();
     44        }
     45        else if ((lb == 1) && (ub == 1)) {
     46            return re;
     47        }
     48    }
     49    return new Rep(re, lb, ub);
     50}
     51
     52}
  • icGREP/icgrep-devel/icgrep/re/re_rep.h

    r4194 r4203  
    3232    virtual ~Rep();
    3333protected:
    34     friend Rep * makeRep(RE *, const int, const int);
     34    friend RE * makeRep(RE *, const int, const int);
    3535    Rep(RE * re, const int lb, const int ub);
    3636    Rep(const Rep & rep);
     
    8787}
    8888
    89 inline Rep * makeRep(RE * re, const int lower_bound, const int upper_bound) {
    90     return new Rep(re, lower_bound, upper_bound);
    91 }
     89RE * makeRep(RE * re, const int lower_bound, const int upper_bound);
    9290
    9391}
  • icGREP/icgrep-devel/icgrep/re/re_seq.cpp

    r4194 r4203  
    3232}
    3333
     34
     35
    3436}
  • icGREP/icgrep-devel/icgrep/re/re_seq.h

    r4194 r4203  
    1010#include "re_re.h"
    1111#include <string>
     12#include <initializer_list>
    1213
    1314namespace re {
     
    3435    inline void setType(const Type type) {
    3536        mType = type;
    36     }
     37    }   
    3738    virtual ~Seq() {}
    3839protected:
    3940    friend Seq * makeSeq(const Seq::Type);
    40     friend Seq * makeSeq(const Seq::Type, Seq::iterator, Seq::iterator);
     41    template<typename iterator> friend RE * makeSeq(const Seq::Type, iterator, iterator);
    4142    Seq(const Type type)
    4243    : Vector(ClassTypeId::Seq)
     
    5556
    5657    }
     58    template<typename itr> void construct(itr begin, itr end);
    5759private:
    5860    Type    mType;
     
    6365}
    6466
    65 inline Seq * makeSeq(const Seq::Type type, Seq::iterator begin, Seq::iterator end) {
    66     return new Seq(type, begin, end);
     67template<typename itr>
     68void Seq::construct(itr begin, itr end) {
     69    for (auto i = begin; i != end; ++i) {
     70        if (Seq * seq = dyn_cast<Seq>(*i)) {
     71            construct<Seq::iterator>(seq->begin(), seq->end());
     72            continue;
     73        }
     74        push_back(*i);
     75    }
     76}
     77
     78template<typename itr>
     79inline RE * makeSeq(const Seq::Type type, itr begin, itr end) {
     80    Seq * seq = makeSeq(type);
     81    seq->construct(begin, end);
     82    if (seq->size() == 1) {
     83        return seq->back();
     84    }
     85    return seq;
     86}
     87
     88inline RE * makeSeq(RE::InitializerList list) {
     89    return makeSeq(Seq::Type::Normal, list.begin(), list.end());
    6790}
    6891
  • icGREP/icgrep-devel/icgrep/re/re_simplifier.cpp

    r4194 r4203  
    1515RE * RE_Simplifier::simplify(RE * re) {
    1616    if (Alt * alt = dyn_cast<Alt>(re)) {
    17         for (auto i = alt->begin(); i != alt->end(); ++i) {
    18             *i = simplify(*i);
     17        std::vector<RE*> list;
     18        list.reserve(alt->size());
     19        for (RE * re : *alt) {
     20            list.push_back(simplify(re));
    1921        }
    20         re = simplify(alt);
     22        re = makeAlt(list.begin(), list.end());
    2123    }
    2224    else if (Seq * seq = dyn_cast<Seq>(re)) {
    23         for (auto i = seq->begin(); i != seq->end(); ++i) {
    24             *i = simplify(*i);
     25        std::vector<RE*> list;
     26        list.reserve(seq->size());
     27        for (RE * re : *seq) {
     28            list.push_back(simplify(re));
    2529        }
    26         re = simplify(seq);
     30        re = makeSeq(seq->getType(), list.begin(), list.end());
    2731    }
    2832    else if (Rep * rep = dyn_cast<Rep>(re)) {
    29         rep->setRE(simplify(rep->getRE()));
    30         simplify(rep);
     33        re = makeRep(simplify(rep->getRE()), rep->getLB(), rep->getUB());
    3134    }
    3235    return re;
    3336}
    3437
    35 RE * RE_Simplifier::simplify(Seq * seq) {
    36     /*
    37       mkSeq - make a sequence, but flatten.  Result might not be a Seq. If
    38       there is only one component for a sequence, simply return that.
    39     */
    40 
    41     RE * re = seq;
    42     if (!seq->empty()) {
    43         std::vector<RE*> list;
    44         list.reserve(seq->size());
    45         // Reverse the order of the input list so we can more efficiently "pull" the first
    46         // character from the end. Note: this uses a linear inplace reversal.
    47         std::reverse(seq->begin(), seq->end());
    48 
    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;
    58                     continue;
    59                 }
    60             }
    61             list.push_back(next);
    62         }
    63         if (list.size() == 1) {
    64             re = list.back();
    65             delete seq;
    66         }
    67         else {
    68             seq->swap(list);
    69         }
    70     }
    71     return re;
    7238}
    73 
    74 /**
    75  * @brief makeAlt
    76  *
    77  * Build an Alt, flattening alternative subgroups, and combining character classes and
    78  * move character classes towards the end of the list to ensure that all combinations are found.
    79  *
    80  * @param list
    81  * @return simplified RE representing the Alt
    82  */
    83 RE * RE_Simplifier::simplify(Alt * alt) {
    84     RE * re = alt;
    85     if (!alt->empty()) {
    86 
    87         std::queue<CC*> ccs;
    88 
    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;
    97             }
    98             else if (CC * cc = dyn_cast<CC>(next)) {
    99                 ccs.push(cc);
    100             }
    101             else {
    102                 list.push_back(next);
    103             }
    104         }
    105 
    106         if (!ccs.empty()) {
    107             while (ccs.size() > 1) {
    108                 CC * a = ccs.front(); ccs.pop();
    109                 CC * b = ccs.front(); ccs.pop();
    110                 ccs.push(makeCC(a, b));
    111             }
    112             list.push_back(ccs.front());
    113         }
    114 
    115         if (list.size() == 1) {
    116             // if only one alternation exists, discard the Alt object itself and return the internal RE.
    117             re = list.back();
    118             delete alt;
    119         }
    120         else {
    121             alt->swap(list);
    122         }
    123     }
    124     return re;
    125 }
    126 
    127 RE * 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             }
    145         }
    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);
    150         }
    151     }
    152     else {
    153         if (Seq * seq = dyn_cast<Seq>(re)) {
    154             if (seq->empty()) {
    155                 return seq;
    156             }
    157         }
    158         if ((lb == 0) && (ub == 0)) {
    159             delete re;
    160             return makeSeq();
    161         }
    162         else if ((lb == 1) && (ub == 1)) {
    163             return re;
    164         }
    165     }
    166     rep->setRE(re);
    167     return janitor.release();
    168 }
    169 
    170 inline int RE_Simplifier::ubCombine(const int h1, const int h2) {
    171     if ((h1 == Rep::UNBOUNDED_REP) || (h2 == Rep::UNBOUNDED_REP)) {
    172         return Rep::UNBOUNDED_REP;
    173     }
    174     else {
    175         return h1 * h2;
    176     }
    177 }
    178 
    179 }
  • icGREP/icgrep-devel/icgrep/re/re_simplifier.h

    r4194 r4203  
    1212class RE_Simplifier {
    1313public:
    14     static RE * simplify(Alt * alt);
    15     static RE * simplify(Seq * seq);
    16     static RE * simplify(Rep * rep);
    1714    static RE * simplify(RE * re);
    18 private:
    19     static int ubCombine(const int h1, const int h2);
    2015};
    2116
  • icGREP/icgrep-devel/icgrep/utf8_encoder.cpp

    r4194 r4203  
    1616
    1717#include <assert.h>
     18#include <algorithm>
    1819#include <stdexcept>
    1920
     
    3839        if (cc->size() == 1) {
    3940            re = rangeToUTF8(cc->front());
    40             delete cc;
    4141        }
    4242        else if (cc->size() > 1) {
    43             Alt * alt = makeAlt();
     43            std::vector<RE *> alt;
    4444            for (const CharSetItem & item : *cc) {
    45                 alt->push_back(rangeToUTF8(item));
     45                alt.push_back(rangeToUTF8(item));
    4646            }
    47             re = RE_Simplifier::simplify(alt);
    48             delete cc;
     47            re = makeAlt(alt.begin(), alt.end());
    4948        }
    5049    }
     
    6059    if (u8len_lo < u8len_hi) {
    6160        int m = max_of_u8len(u8len_lo);
    62         Alt* alt = makeAlt();
    63         alt->push_back(rangeToUTF8(CharSetItem(item.lo_codepoint, m)));
    64         alt->push_back(rangeToUTF8(CharSetItem(m + 1, item.hi_codepoint)));
    65         return alt;
     61        return makeAlt({rangeToUTF8(CharSetItem(item.lo_codepoint, m)), rangeToUTF8(CharSetItem(m + 1, item.hi_codepoint))});
    6662    }
    6763    else {
     
    8177    else if (hbyte == lbyte)
    8278    {
    83         Seq* seq = makeSeq();
    84         seq->setType((u8Prefix(hbyte) ? Seq::Type::Byte : Seq::Type::Normal));
     79        Seq* seq = makeSeq(u8Prefix(hbyte) ? Seq::Type::Byte : Seq::Type::Normal);
    8580        seq->push_back(makeByteClass(hbyte));
    8681        seq->push_back(rangeToUTF8_helper(lo, hi, n+1, hlen));
     
    9489        {
    9590            int hi_floor = (~suffix_mask) & hi;
    96 
    97             Alt* alt = makeAlt();
    98             alt->push_back(rangeToUTF8_helper(hi_floor, hi, n, hlen));
    99             alt->push_back(rangeToUTF8_helper(lo, hi_floor - 1, n, hlen));
    100             return alt;
     91            return makeAlt({rangeToUTF8_helper(hi_floor, hi, n, hlen), rangeToUTF8_helper(lo, hi_floor - 1, n, hlen)});
    10192        }
    10293        else if ((lo & suffix_mask) != 0)
Note: See TracChangeset for help on using the changeset viewer.