Changeset 4829


Ignore:
Timestamp:
Oct 11, 2015, 1:45:52 PM (2 years ago)
Author:
nmedfort
Message:

Back-up check in

Location:
icGREP/icgrep-devel/icgrep
Files:
1 added
16 edited

Legend:

Unmodified
Added
Removed
  • icGREP/icgrep-devel/icgrep/UCD/resolve_properties.cpp

    r4820 r4829  
    99#include <re/re_name.h>
    1010#include <re/re_diff.h>
    11 #include <re/re_parser.h>
    1211#include "UCD/PropertyAliases.h"
    1312#include "UCD/PropertyObjects.h"
  • icGREP/icgrep-devel/icgrep/icgrep-devel.files

    r4820 r4829  
    406406re/re_rep.cpp
    407407re/re_alt.h
     408re/re_grapheme_boundary.hpp
  • icGREP/icgrep-devel/icgrep/pablo/optimizers/pablo_simplifier.cpp

    r4805 r4829  
    2525    eliminateRedundantCode(function.getEntryBlock());
    2626    deadCodeElimination(function.getEntryBlock());
    27     // eliminateRedundantComplexStatements(function.getEntryBlock());
     27    eliminateRedundantEquations(function.getEntryBlock());
    2828    #ifndef NDEBUG
    2929    PabloVerifier::verify(function, "post-simplification");
     
    3232}
    3333
    34 inline static bool canTriviallyFold(const Statement * stmt) {
     34inline static PabloAST * canTriviallyFold(Statement * stmt, PabloBlock & block) {
    3535    for (unsigned i = 0; i != stmt->getNumOperands(); ++i) {
    36         switch (stmt->getOperand(i)->getClassTypeId()) {
    37             case PabloAST::ClassTypeId::Zeroes:
    38             case PabloAST::ClassTypeId::Ones:
    39                 return true;
    40             default: break;
    41         }
    42     }
    43     return false;
     36        if (LLVM_UNLIKELY(isa<Zeroes>(stmt->getOperand(i)))) {
     37            switch (stmt->getClassTypeId()) {
     38                case PabloAST::ClassTypeId::And:
     39                case PabloAST::ClassTypeId::Advance:
     40                    return block.createZeroes();
     41                case PabloAST::ClassTypeId::Xor:
     42                case PabloAST::ClassTypeId::Or:
     43                    return stmt->getOperand(1 - i);
     44                case PabloAST::ClassTypeId::Not:
     45                    return block.createOnes();
     46                case PabloAST::ClassTypeId::Sel:
     47                    block.setInsertPoint(stmt->getPrevNode());
     48                    switch (i) {
     49                        case 0: return stmt->getOperand(2);
     50                        case 1: return block.createAnd(block.createNot(stmt->getOperand(0)), stmt->getOperand(2));
     51                        case 2: return block.createAnd(stmt->getOperand(0), stmt->getOperand(1));
     52                    }
     53                case PabloAST::ClassTypeId::ScanThru:
     54                case PabloAST::ClassTypeId::MatchStar:
     55                    return stmt->getOperand(0);
     56                default: break;
     57            }
     58        } else if (LLVM_UNLIKELY(isa<Ones>(stmt->getOperand(i)))) {
     59            block.setInsertPoint(stmt->getPrevNode());
     60            switch (stmt->getClassTypeId()) {
     61                case PabloAST::ClassTypeId::And:
     62                    return stmt->getOperand(1 - i);
     63                case PabloAST::ClassTypeId::Or:
     64                    return block.createOnes();
     65                case PabloAST::ClassTypeId::Xor:
     66                    return block.createNot(stmt->getOperand(1 - i));
     67                case PabloAST::ClassTypeId::Not:
     68                    return block.createZeroes();
     69                case PabloAST::ClassTypeId::Sel:
     70                    block.setInsertPoint(stmt->getPrevNode());
     71                    switch (i) {
     72                        case 0: return stmt->getOperand(1);
     73                        case 1: return block.createOr(stmt->getOperand(0), stmt->getOperand(2));
     74                        case 2: return block.createOr(block.createNot(stmt->getOperand(0)), stmt->getOperand(1));
     75                    }
     76                default: break;
     77            }
     78        }
     79    }
     80    return nullptr;
    4481}
    4582
     
    114151        for (auto j = i + 1; j != list.end(); ) {
    115152            if (LLVM_UNLIKELY(equals(*i, *j))) {
    116                 (*j)->replaceWith(*i, false, true);
     153                Statement * redundantValue = *j;
    117154                j = list.erase(j);
     155                redundantValue->replaceWith(*i, false, true);
    118156                continue;
    119157            }
     
    178216
    179217        } else if (While * whileNode = dyn_cast<While>(stmt)) {
    180 
    181218            const PabloAST * initial = whileNode->getCondition();
    182219            if (LLVM_LIKELY(isa<Next>(initial))) {
     
    187224                continue;
    188225            }
    189 
    190226            eliminateRedundantCode(whileNode->getBody(), &encountered);
    191 
    192227            removeIdenticalEscapedValues(whileNode->getVariants());
    193 
    194         } else if (canTriviallyFold(stmt)) { // non-Assign node
    195             // Do a trivial folding test to see if we're using all 0s or 1s as an operand.
    196             PabloAST * expr = nullptr;
    197             block.setInsertPoint(stmt->getPrevNode());
    198             switch (stmt->getClassTypeId()) {
    199                 case PabloAST::ClassTypeId::Advance:
    200                     expr = block.createAdvance(stmt->getOperand(0), stmt->getOperand(1));
    201                     break;
    202                 case PabloAST::ClassTypeId::And:
    203                     expr = block.createAnd(stmt->getOperand(0), stmt->getOperand(1));
    204                     break;
    205                 case PabloAST::ClassTypeId::Or:
    206                     expr = block.createOr(stmt->getOperand(0), stmt->getOperand(1));
    207                     break;
    208                 case PabloAST::ClassTypeId::Not:
    209                     expr = block.createNot(stmt->getOperand(0));
    210                     break;
    211                 case PabloAST::ClassTypeId::Xor:
    212                     expr = block.createXor(stmt->getOperand(0), stmt->getOperand(1));
    213                     break;
    214                 case PabloAST::ClassTypeId::Sel:
    215                     expr = block.createSel(stmt->getOperand(0), stmt->getOperand(1), stmt->getOperand(2));
    216                     break;
    217                 case PabloAST::ClassTypeId::ScanThru:
    218                     expr = block.createScanThru(stmt->getOperand(0), stmt->getOperand(1));
    219                     break;
    220                 case PabloAST::ClassTypeId::MatchStar:
    221                     expr = block.createMatchStar(stmt->getOperand(0), stmt->getOperand(1));
    222                     break;
    223                 case PabloAST::ClassTypeId::Next:
    224                     expr = stmt;
    225                     break;
    226                 default: {
    227                     std::string tmp;
    228                     llvm::raw_string_ostream msg(tmp);
    229                     PabloPrinter::print(stmt, "Unhandled trivial folding optimization! ", msg);
    230                     throw std::runtime_error(msg.str());
    231                 }
    232             }
    233             stmt = stmt->replaceWith(expr);
    234             block.setInsertPoint(block.back());
     228        } else if (PabloAST * expr = canTriviallyFold(stmt, block)) {
     229            stmt = stmt->replaceWith(expr, true, true);
    235230            continue;
    236231        } else {
     
    240235            // and erase this statement from the AST
    241236            const auto f = encountered.findOrAdd(stmt);
    242             if (f.second == false) {
     237            if (!f.second) {
    243238                stmt = stmt->replaceWith(f.first, true, true);
    244239                continue;
     
    255250        if (isa<If>(stmt)) {
    256251            deadCodeElimination(cast<If>(stmt)->getBody());
    257         }
    258         else if (isa<While>(stmt)) {
     252        } else if (isa<While>(stmt)) {
    259253            deadCodeElimination(cast<While>(stmt)->getBody());
    260         }
    261         else if (stmt->getNumUses() == 0){
     254        } else if (stmt->getNumUses() == 0){
    262255            stmt = stmt->eraseFromParent(true);
    263256            continue;
     
    267260}
    268261
    269 void Simplifier::eliminateRedundantComplexStatements(PabloBlock & block) {
     262void Simplifier::eliminateRedundantEquations(PabloBlock & block) {
    270263    Statement * stmt = block.front();
    271264    while (stmt) {
    272265        if (isa<If>(stmt)) {
    273             eliminateRedundantComplexStatements(cast<If>(stmt)->getBody());
     266            eliminateRedundantEquations(cast<If>(stmt)->getBody());
    274267        }
    275268        else if (isa<While>(stmt)) {
    276             eliminateRedundantComplexStatements(cast<While>(stmt)->getBody());
    277         }
    278         else if (stmt->getNumOperands() == 2){
    279             if (isa<Advance>(stmt)) {
    280                 // If we're advancing an Advance and the internal Advance does not have any other user,
    281                 // we can merge both Advance instructions.
    282                 if (LLVM_UNLIKELY(isa<Advance>(stmt->getOperand(0)))) {
    283                     Advance * op = cast<Advance>(stmt->getOperand(0));
    284                     if (LLVM_UNLIKELY(op->getNumUses() == 1)) {
    285                         Advance * adv = cast<Advance>(stmt);
    286                         adv->setOperand(0, op->getOperand(0));
    287                         adv->setOperand(1, block.getInteger(adv->getAdvanceAmount() + op->getAdvanceAmount()));
    288                         assert(op->getNumUses() == 0);
    289                         op->eraseFromParent();
    290                     }
    291                 }
    292             } else if (LLVM_UNLIKELY(isa<Advance>(stmt->getOperand(1)) && isa<Advance>(stmt->getOperand(0)))) {
    293                 // If an AND, OR or XOR instruction has two Advance instructions as inputs and neither Advance
    294                 // has another user and both shift their input by the same amount, we can perform the AND, OR
    295                 // or XOR on the inputs to the Advances and remove one of the Advance statements.
    296 
    297                 Advance * const a0 = cast<Advance>(stmt->getOperand(0));
    298                 Advance * const a1 = cast<Advance>(stmt->getOperand(1));
    299                 switch (stmt->getClassTypeId()) {
    300                     case PabloAST::ClassTypeId::And:
    301                     case PabloAST::ClassTypeId::Or:
    302                     case PabloAST::ClassTypeId::Xor:
    303                         if (LLVM_UNLIKELY(a0->getNumUses() == 1 && a1->getNumUses() == 1 && a0->getOperand(1) == a1->getOperand(1))) {
    304                             block.setInsertPoint(stmt);
    305                             stmt->setOperand(0, a0->getOperand(0));
    306                             stmt->setOperand(1, a1->getOperand(0));
    307                             a0->insertAfter(stmt);
    308                             a0->setOperand(0, stmt);
    309                             stmt->replaceAllUsesWith(a0);
    310                             assert(a1->getNumUses() == 0);
    311                             a1->eraseFromParent();
    312                             stmt = a0;
    313                     }
    314                     default: break;
    315                 }
    316             } else if (LLVM_UNLIKELY(isa<MatchStar>(stmt->getOperand(1)) && isa<MatchStar>(stmt->getOperand(0))) && isa<Or>(stmt)) {
    317 
    318 
    319             } /*else if (LLVM_UNLIKELY(isa<Or>(stmt) && isa<And>(stmt->getOperand(0)) && isa<And>(stmt->getOperand(1)))) {
    320 
    321                 // If we have an OR(AND(A,B),AND(NOT(A),C)) statement and neither of the inner operands are used elsewhere, we can
    322                 // promote the Or to a Sel statement.
    323 
    324                 And * const a0 = cast<And>(stmt->getOperand(0));
    325                 And * const a1 = cast<And>(stmt->getOperand(1));
    326 
    327                 if (LLVM_UNLIKELY(a0->getNumUses() == 1 && a1->getNumUses() == 1)) {
    328 
    329                     bool neg[4] = { false, false, false, false };
    330 
    331                     for (unsigned i = 0; i != 2; ++i) {
    332                         if (isa<Not>(a0->getOperand(i))) {
    333                             PabloAST * i0 = cast<Not>(a0->getOperand(i))->getOperand(0);
    334                             for (unsigned j = 0; j != 2; ++j) {
    335                                 if (a0->getOperand(j) == i0) {
    336                                     neg[i + j * 2] = true;
    337                                 }
    338                             }
    339                         }
    340                     }
    341 
    342 
    343 
    344 
    345 
    346 
    347 
    348 
    349 
    350                 }
    351 
    352             }*/
     269            eliminateRedundantEquations(cast<While>(stmt)->getBody());
     270        } else if (isa<Advance>(stmt)) {
     271            Advance * adv = cast<Advance>(stmt);
     272            if (LLVM_UNLIKELY(isa<Advance>(adv->getOperand(0)))) {
     273                // Replace an Advance(Advance(x, n), m) with an Advance(x,n + m)
     274                Advance * op = cast<Advance>(stmt->getOperand(0));
     275                if (LLVM_UNLIKELY(op->getNumUses() == 1)) {
     276                    adv->setOperand(0, op->getOperand(0));
     277                    adv->setOperand(1, block.getInteger(adv->getAdvanceAmount() + op->getAdvanceAmount()));
     278                    op->eraseFromParent(false);
     279                }
     280            }
     281        } else if (LLVM_UNLIKELY(isa<ScanThru>(stmt))) {
     282            ScanThru * scanThru = cast<ScanThru>(stmt);
     283            if (LLVM_UNLIKELY(isa<Advance>(scanThru->getOperand(0)))) {
     284                // Replace a ScanThru(Advance(x,n),y) with an ScanThru(Advance(x, n - 1), Advance(x, n - 1) | y), where Advance(x, 0) = x
     285                Advance * op = cast<Advance>(stmt->getOperand(0));
     286                if (LLVM_UNLIKELY(op->getNumUses() == 1)) {
     287                    block.setInsertPoint(scanThru);
     288                    PabloAST * expr = block.createAdvance(op->getOperand(0), op->getAdvanceAmount() - 1);
     289                    scanThru->setOperand(0, expr);
     290                    scanThru->setOperand(1, block.createOr(scanThru->getOperand(1), expr));
     291                    op->eraseFromParent(false);
     292                }
     293            }
    353294        }
    354295        stmt = stmt->getNextNode();
     
    357298}
    358299
    359 Simplifier::Simplifier()
    360 {
    361 
    362 }
    363 
    364 
    365 }
     300}
  • icGREP/icgrep-devel/icgrep/pablo/optimizers/pablo_simplifier.hpp

    r4768 r4829  
    1414    static void deadCodeElimination(PabloBlock & block);
    1515protected:
    16     Simplifier();
     16    Simplifier() = default;
    1717private:
    1818    static void eliminateRedundantCode(PabloBlock & block, ExpressionTable * predecessor = nullptr);
    19     static void eliminateRedundantComplexStatements(PabloBlock & block);
     19    static void eliminateRedundantEquations(PabloBlock & block);
    2020    static bool isSuperfluous(const Assign * const assign);
    21 private:
    22 
    2321};
    2422
  • icGREP/icgrep-devel/icgrep/pablo/pabloAST.cpp

    r4805 r4829  
    212212        mOperand[i]->removeUser(this);
    213213    }
     214    Statement * redundantBranch = nullptr;
    214215    // If this is an If or While statement, we'll have to remove the statements within the
    215216    // body or we'll lose track of them.
     
    217218        PabloBlock & body = isa<If>(this) ? cast<If>(this)->getBody() : cast<While>(this)->getBody();
    218219        Statement * stmt = body.front();
     220        // Note: by erasing the body, any Assign/Next nodes will be replaced with Zero.
    219221        while (stmt) {
    220222            stmt = stmt->eraseFromParent(recursively);
     
    223225        for (PabloAST * use : mUsers) {
    224226            if (If * ifNode = dyn_cast<If>(use)) {
    225                 const auto & defs = ifNode->getDefined();
    226                 if (LLVM_LIKELY(std::find(defs.begin(), defs.end(), this) != defs.end())) {
     227                auto & defs = ifNode->getDefined();
     228                auto f = std::find(defs.begin(), defs.end(), this);
     229                if (LLVM_LIKELY(f != defs.end())) {
    227230                    this->removeUser(ifNode);
    228231                    ifNode->removeUser(this);
     232                    defs.erase(f);
     233                    if (LLVM_UNLIKELY(defs.empty())) {
     234                        redundantBranch = ifNode;
     235                    }
    229236                    break;
    230237                }
     
    234241        for (PabloAST * use : mUsers) {
    235242            if (While * whileNode = dyn_cast<While>(use)) {
    236                 const auto & vars = whileNode->getVariants();
    237                 if (LLVM_LIKELY(std::find(vars.begin(), vars.end(), this) != vars.end())) {
     243                auto & vars = whileNode->getVariants();
     244                auto f = std::find(vars.begin(), vars.end(), this);
     245                if (LLVM_LIKELY(f != vars.end())) {
    238246                    this->removeUser(whileNode);
    239247                    whileNode->removeUser(this);
     248                    vars.erase(f);
     249                    if (LLVM_UNLIKELY(vars.empty())) {
     250                        redundantBranch = whileNode;
     251                    }
    240252                    break;
    241253                }
     
    249261        for (unsigned i = 0; i != mOperands; ++i) {
    250262            PabloAST * const op = mOperand[i];
    251             if (op->getNumUses() == 0 && isa<Statement>(op)) {
    252                 cast<Statement>(op)->eraseFromParent(true);
    253             }
     263            if (LLVM_LIKELY(isa<Statement>(op))) {
     264                bool erase = false;
     265                if (op->getNumUses() == 0) {
     266                    erase = true;
     267                } else if ((isa<Assign>(op) || isa<Next>(op)) && op->getNumUses() == 1) {
     268                    erase = true;
     269                }
     270                if (erase) {
     271                    cast<Statement>(op)->eraseFromParent(true);
     272                }
     273            }
     274        }
     275        if (LLVM_UNLIKELY(redundantBranch != nullptr)) {
     276            redundantBranch->eraseFromParent(true);
    254277        }
    255278    }
  • icGREP/icgrep-devel/icgrep/re/printer_re.cpp

    r4614 r4829  
    2020#include <re/re_intersect.h>
    2121#include <re/re_assertion.h>
     22#include <re/re_grapheme_boundary.hpp>
    2223
    2324using namespace re;
     
    8586        retVal += ") ";
    8687    }
     88    else if (const GraphemeBoundary * g = dyn_cast<GraphemeBoundary>(re))
     89    {
     90        retVal = "Grapheme";
     91        switch (g->getType()) {
     92            case GraphemeBoundary::Type::ClusterBoundary:
     93                retVal += "Cluster"; break;
     94            case GraphemeBoundary::Type::LineBreakBoundary:
     95                retVal += "LineBreak"; break;
     96            case GraphemeBoundary::Type::SentenceBoundary:
     97                retVal += "Sentence"; break;
     98            case GraphemeBoundary::Type::WordBoundary:
     99                retVal += "Word"; break;
     100        }
     101        retVal += "Boundary(";
     102        retVal += PrintRE(g->getExpression());
     103        retVal += ") ";
     104    }
    87105    else if (isa<const End>(re))
    88106    {
  • icGREP/icgrep-devel/icgrep/re/re_analysis.cpp

    r4442 r4829  
    1111#include "re_intersect.h"
    1212#include "re_assertion.h"
     13#include <iostream>
     14#include <re/printer_re.h>
    1315#include <limits.h>
    1416
    1517namespace re {
    1618
    17 bool isByteLength(RE * re) {
    18     if (Alt * alt = dyn_cast<Alt>(re)) {
    19         for (RE * re : *alt) {
     19bool isByteLength(const RE * re) {
     20    if (const Alt * alt = dyn_cast<Alt>(re)) {
     21        for (const RE * re : *alt) {
    2022            if (!isByteLength(re)) {
    2123                return false;
     
    2426        return true;
    2527    }
    26     else if (Seq * seq = dyn_cast<Seq>(re)) {
     28    else if (const Seq * seq = dyn_cast<Seq>(re)) {
    2729        return (seq->size() == 1) && isByteLength(&seq[0]);
    2830    }
    29     else if (Rep * rep = dyn_cast<Rep>(re)) {
     31    else if (const Rep * rep = dyn_cast<Rep>(re)) {
    3032        return (rep->getLB() == 1) && (rep->getUB() == 1) && isByteLength(rep->getRE());
    3133    }
     
    3335        return false;
    3436    }
    35     else if (Diff * diff = dyn_cast<Diff>(re)) {
     37    else if (const Diff * diff = dyn_cast<Diff>(re)) {
    3638        return isByteLength(diff->getLH()) && isByteLength(diff->getRH());
    3739    }
    38     else if (Intersect * e = dyn_cast<Intersect>(re)) {
     40    else if (const Intersect * e = dyn_cast<Intersect>(re)) {
    3941        return isByteLength(e->getLH()) && isByteLength(e->getRH());
    4042    }
     
    4244        return false;
    4345    }
    44     else if (Name * n = dyn_cast<Name>(re)) {
     46    else if (const Name * n = dyn_cast<Name>(re)) {
    4547        return (n->getType() == Name::Type::Byte);
    4648    }
     
    4850}
    4951
    50 bool isUnicodeUnitLength(RE * re) {
    51     if (Alt * alt = dyn_cast<Alt>(re)) {
    52         for (RE * re : *alt) {
     52bool isUnicodeUnitLength(const RE * re) {
     53    if (const Alt * alt = dyn_cast<Alt>(re)) {
     54        for (const RE * re : *alt) {
    5355            if (!isUnicodeUnitLength(re)) {
    5456                return false;
     
    5759        return true;
    5860    }
    59     else if (Seq * seq = dyn_cast<Seq>(re)) {
     61    else if (const Seq * seq = dyn_cast<Seq>(re)) {
    6062        return (seq->size() == 1) && isUnicodeUnitLength(&seq[0]);
    6163    }
    62     else if (Rep * rep = dyn_cast<Rep>(re)) {
     64    else if (const Rep * rep = dyn_cast<Rep>(re)) {
    6365        return (rep->getLB() == 1) && (rep->getUB() == 1) && isUnicodeUnitLength(rep->getRE());
    6466    }
     
    6668        return false;
    6769    }
    68     else if (Diff * diff = dyn_cast<Diff>(re)) {
     70    else if (const Diff * diff = dyn_cast<Diff>(re)) {
    6971        return isUnicodeUnitLength(diff->getLH()) && isUnicodeUnitLength(diff->getRH());
    7072    }
    71     else if (Intersect * e = dyn_cast<Intersect>(re)) {
     73    else if (const Intersect * e = dyn_cast<Intersect>(re)) {
    7274        return isUnicodeUnitLength(e->getLH()) && isUnicodeUnitLength(e->getRH());
    7375    }
     
    7577        return true;
    7678    }
    77     else if (Name * n = dyn_cast<Name>(re)) {
     79    else if (const Name * n = dyn_cast<Name>(re)) {
    7880        // Eventually names might be set up for not unit length items.
    7981        return (n->getType() == Name::Type::Unicode || n->getType() == Name::Type::UnicodeProperty || n->getType() == Name::Type::Byte);
    8082    }
    8183    return false; // otherwise
     84}
     85
     86std::pair<int, int> getUnicodeUnitLengthRange(const RE * re) {
     87    if (const Alt * alt = dyn_cast<Alt>(re)) {
     88        std::pair<int, int> range = std::make_pair(std::numeric_limits<int>::max(), 0);
     89        for (const RE * re : *alt) {
     90            auto r = getUnicodeUnitLengthRange(re);
     91            range.first = std::min<int>(range.first, r.first);
     92            range.second = std::max<int>(range.second, r.second);
     93        }
     94        return range;
     95    } else if (const Seq * seq = dyn_cast<Seq>(re)) {
     96        std::pair<int, int> range = std::make_pair(0, 0);
     97        for (const RE * re : *seq) {
     98            auto tmp = getUnicodeUnitLengthRange(re);
     99            if (LLVM_LIKELY(tmp.first < std::numeric_limits<int>::max() - range.first)) {
     100                range.first += tmp.first;
     101            } else {
     102                range.first = std::numeric_limits<int>::max();
     103            }
     104            if (LLVM_LIKELY(tmp.second < std::numeric_limits<int>::max() - range.second)) {
     105                range.second += tmp.second;
     106            } else {
     107                range.second = std::numeric_limits<int>::max();
     108            }
     109        }
     110        return range;
     111    } else if (const Rep * rep = dyn_cast<Rep>(re)) {
     112        auto range = getUnicodeUnitLengthRange(rep->getRE());
     113        if (LLVM_LIKELY(rep->getLB() != Rep::UNBOUNDED_REP && range.first < std::numeric_limits<int>::max())) {
     114            range.first *= rep->getLB();
     115        } else {
     116            range.first = std::numeric_limits<int>::max();
     117        }
     118        if (LLVM_LIKELY(rep->getUB() != Rep::UNBOUNDED_REP && range.second < std::numeric_limits<int>::max())) {
     119            range.second *= rep->getUB();
     120        } else {
     121            range.second = std::numeric_limits<int>::max();
     122        }
     123        return range;
     124    } else if (isa<Assertion>(re) || isa<Start>(re) || isa<End>(re)) {
     125        return std::make_pair(0, 0);
     126    } else if (const Diff * diff = dyn_cast<Diff>(re)) {
     127        const auto r1 = getUnicodeUnitLengthRange(diff->getLH());
     128        const auto r2 = getUnicodeUnitLengthRange(diff->getRH());
     129        return std::make_pair(std::min(r1.first, r2.first), std::max(r1.second, r2.second));
     130    } else if (const Intersect * i = dyn_cast<Intersect>(re)) {
     131        const auto r1 = getUnicodeUnitLengthRange(i->getLH());
     132        const auto r2 = getUnicodeUnitLengthRange(i->getRH());
     133        return std::make_pair(std::min(r1.first, r2.first), std::max(r1.second, r2.second));
     134    } else if (const Name * n = dyn_cast<Name>(re)) {
     135        // Eventually names might be set up for not unit length items.
     136        switch (n->getType()) {
     137            case Name::Type::Byte:
     138            case Name::Type::Unicode:
     139            case Name::Type::UnicodeProperty:
     140                return std::make_pair(1, 1);
     141            case Name::Type::Unknown:
     142                return std::make_pair(0, std::numeric_limits<int>::max());
     143        }
     144    }
     145    return std::make_pair(1, 1);
    82146}
    83147   
  • icGREP/icgrep-devel/icgrep/re/re_analysis.h

    r4442 r4829  
    88namespace re {
    99
    10 bool isByteLength(RE * re);
     10bool isByteLength(const RE *re);
    1111   
    12 bool isUnicodeUnitLength(RE * re);
     12bool isUnicodeUnitLength(const RE * re);
     13
     14std::pair<int, int> getUnicodeUnitLengthRange(const RE * re);
    1315
    1416int minMatchLength(RE * re);
  • icGREP/icgrep-devel/icgrep/re/re_assertion.h

    r4516 r4829  
    4444}
    4545
     46inline RE * makeLookAheadAssertion(RE * r) {
     47    return makeAssertion(r, Assertion::Kind::Lookahead, Assertion::Sense::Positive);
     48}
     49
     50inline RE * makeNegativeLookAheadAssertion(RE * r) {
     51    return makeAssertion(r, Assertion::Kind::Lookahead, Assertion::Sense::Negative);
     52}
     53
     54inline RE * makeLookBehindAssertion(RE * r) {
     55    return makeAssertion(r, Assertion::Kind::Lookbehind, Assertion::Sense::Positive);
     56}
     57
     58inline RE * makeNegativeLookBehindAssertion(RE * r) {
     59    return makeAssertion(r, Assertion::Kind::Lookbehind, Assertion::Sense::Negative);
     60}
     61
    4662}
    4763
  • icGREP/icgrep-devel/icgrep/re/re_cc.cpp

    r4814 r4829  
    3333    }
    3434    char separator = '_';
    35     for (const interval_t & i : *this) {
     35    for (const interval_t i : *this) {
    3636        name << separator;
    3737        if (lo_codepoint(i) == hi_codepoint(i)) {
     
    4848CC * caseInsensitize(const CC * cc) {
    4949    CC * cci = makeCC();
    50     for (const interval_t & i : *cc) {
     50    for (const interval_t i : *cc) {
    5151        caseInsensitiveInsertRange(cci, lo_codepoint(i), hi_codepoint(i));
    5252    }
  • icGREP/icgrep-devel/icgrep/re/re_compiler.cpp

    r4820 r4829  
    1717#include <re/re_intersect.h>
    1818#include <re/re_assertion.h>
     19#include <re/re_grapheme_boundary.hpp>
    1920#include <re/re_analysis.h>
    2021#include <re/re_memoizer.hpp>
     
    3031#include <iostream>
    3132#include <pablo/printer_pablos.h>
    32 
    3333#include "llvm/Support/CommandLine.h"
    34 static cl::OptionCategory fREcompilationOptions("Regex Compilation Options",
    35                                       "These options control the compilation of regular expressions to Pablo.");
     34#include <sstream>
     35
     36static cl::OptionCategory fREcompilationOptions("Regex Compilation Options", "These options control the compilation of regular expressions to Pablo.");
    3637
    3738static cl::opt<bool> DisableLog2BoundedRepetition("disable-log2-bounded-repetition", cl::init(false),
     
    4647static cl::opt<bool> SetMod64Approximation("mod64-approximate", cl::init(false),
    4748                     cl::desc("set mod64 approximate mode"), cl::cat(fREcompilationOptions));
     49
    4850#ifndef DISABLE_PREGENERATED_UCD_FUNCTIONS
    4951static cl::opt<bool> UsePregeneratedUnicode("use-pregenerated-unicode", cl::init(false),
    5052                     cl::desc("use fixed pregenerated Unicode character class sets instead"), cl::cat(fREcompilationOptions));
    5153#endif
     54
     55#define UNICODE_LINE_BREAK (!DisableUnicodeLineBreak)
     56
    5257using namespace pablo;
    5358
    5459namespace re {
    55 
    56 RE_Compiler::RE_Compiler(pablo::PabloFunction & function, cc::CC_Compiler & ccCompiler)
    57 : mCCCompiler(ccCompiler)
    58 , mLineFeed(nullptr)
    59 , mCRLF(nullptr)
    60 , mUnicodeLineBreak(nullptr)
    61 , mNonLineBreak(nullptr)
    62 , mInitial(nullptr)
    63 , mNonFinal(nullptr)
    64 , mFinal(nullptr)
    65 , mWhileTest(nullptr)
    66 , mStarDepth(0)
    67 , mLoopVariants()
    68 , mPB(*ccCompiler.getBuilder().getPabloBlock(), ccCompiler.getBuilder())
    69 , mFunction(function)
    70 {
    71 
    72 }
    73    
    74 MarkerType RE_Compiler::AdvanceMarker(MarkerType m, MarkerPosition newpos, PabloBuilder & pb) {
    75     if (m.pos == newpos) return m;
    76     PabloAST * a = m.stream;
    77     if (m.pos == MarkerPosition::FinalMatchByte) {
    78         // Must advance at least to InitialPostPositionByte
    79         a = pb.createAdvance(a, 1, "adv");
    80     }
    81     // Now at InitialPostPositionByte; is a further advance needed?
    82     if (newpos == MarkerPosition::FinalPostPositionByte) {
    83         // Must advance through nonfinal bytes
    84         a = pb.createScanThru(pb.createAnd(mInitial, a), mNonFinal, "scanToFinal");
    85     }
    86     return {newpos, a};
    87 }
    88 
    89 void RE_Compiler::AlignMarkers(MarkerType & m1, MarkerType & m2, PabloBuilder & pb) {
    90     if (m1.pos < m2.pos) {
    91         m1 = AdvanceMarker(m1, m2.pos, pb);
    92     }
    93     else if (m2.pos < m1.pos) {
    94         m2 = AdvanceMarker(m2, m1.pos, pb);
    95     }
    96 }
    97 
    98 #define UNICODE_LINE_BREAK (!DisableUnicodeLineBreak)
    9960
    10061void RE_Compiler::initializeRequiredStreams() {
     
    178139    mUnicodeLineBreak = mPB.createAnd(LB_chars, mPB.createNot(mCRLF));  // count the CR, but not CRLF
    179140    PabloAST * const lb = UNICODE_LINE_BREAK ? mUnicodeLineBreak : mLineFeed;
    180     mNonLineBreak = mPB.createNot(lb);
     141    mAny = mPB.createNot(lb, "any");
    181142    mFunction.setResult(1, mPB.createAssign("lf", mPB.createAnd(lb, mPB.createNot(mCRLF))));
    182143}
     
    195156
    196157    Memoizer memoizer;
     158    Name * gcbRule = nullptr;
    197159
    198160    std::function<RE*(RE*)> resolve = [&](RE * re) -> RE * {
     
    211173                            const UCD::ExternalProperty & ep = UCD::resolveExternalProperty(functionName);
    212174                            Call * call = mPB.createCall(Prototype::Create(functionName, std::get<1>(ep), std::get<2>(ep), std::get<0>(ep)), mCCCompiler.getBasisBits());
    213                             name->setCompiled(mPB.createAnd(call, mNonLineBreak));
     175                            name->setCompiled(mPB.createAnd(call, mAny));
    214176                        } else {
    215177                        #endif
     
    231193        } else if (Alt * alt = dyn_cast<Alt>(re)) {
    232194            CC * unionCC = nullptr;
     195            std::stringstream name;
    233196            for (auto ai = alt->begin(); ai != alt->end(); ) {
    234197                RE * re = resolve(*ai);
    235198                if (CC * cc = getDefinitionIfCC(re)) {
    236                     unionCC = (unionCC == nullptr) ? cc : makeCC(unionCC, cc);
     199                    if (unionCC == nullptr) {
     200                        unionCC = cc;
     201                    } else {
     202                        unionCC = makeCC(unionCC, cc);
     203                        name << '+';
     204                    }
     205                    Name * n = cast<Name>(re);
     206                    if (n->hasNamespace()) {
     207                        name << n->getNamespace() << ':';
     208                    }
     209                    name << n->getName();
    237210                    ai = alt->erase(ai);
    238211                } else {
     
    241214            }
    242215            if (unionCC) {
    243                 alt->push_back(makeName("union", unionCC));
     216                alt->push_back(makeName(name.str(), unionCC));
    244217            }
    245218            if (alt->size() == 1) {
     
    266239                return resolve(makeName("intersect", intersectCC(lh, rh)));
    267240            }
     241        } else if (GraphemeBoundary * gb = dyn_cast<GraphemeBoundary>(re)) {
     242            if (LLVM_LIKELY(gb->getGraphemeBoundaryRule() == nullptr)) {
     243                switch (gb->getType()) {
     244                    case GraphemeBoundary::Type::ClusterBoundary:
     245                        if (gcbRule == nullptr) {
     246                            gcbRule = cast<Name>(resolve(generateGraphemeClusterBoundaryRule()));
     247                        }
     248                        gb->setBoundaryRule(gcbRule);
     249                        break;
     250                    default:
     251                        throw std::runtime_error("Only grapheme cluster boundary rules are supported in icGrep 1.0");
     252                }
     253            }
     254            gb->setExpression(resolve(gb->getExpression()));
    268255        }
    269256        return re;
     
    296283            gather(diff->getLH());
    297284            gather(diff->getRH());
     285        } else if (Intersect * ix = dyn_cast<Intersect>(re)) {
     286            gather(ix->getLH());
     287            gather(ix->getRH());
     288        } else if (GraphemeBoundary * gb = dyn_cast<GraphemeBoundary>(re)) {
     289            gather(gb->getExpression());
     290            gather(gb->getGraphemeBoundaryRule());
    298291        }
    299292    };
     
    302295    gather(re);
    303296
    304     if (nameMap.size() > 0) {
     297    if (LLVM_LIKELY(nameMap.size() > 0)) {
    305298        UCD::UCDCompiler ucdCompiler(mCCCompiler);
    306299        ucdCompiler.generateWithDefaultIfHierarchy(nameMap, mPB);
    307300        for (auto t : nameMap) {
    308301            if (t.second) {
    309                 t.first->setCompiled(mPB.createAnd(t.second, mNonLineBreak));
    310             }
    311         }
    312     }
    313 
     302                t.first->setCompiled(mPB.createAnd(t.second, mAny));
     303            }
     304        }
     305    }
     306
     307    // Now precompile any grapheme segmentation rules
     308    if (gcbRule) {
     309        compileName(gcbRule, mPB);
     310    }
    314311    return re;
    315312}
     
    319316}
    320317
     318Name * RE_Compiler::generateGraphemeClusterBoundaryRule() {
     319    // 3.1.1 Grapheme Cluster Boundary Rules
     320    #define Behind(x) makeLookBehindAssertion(x)
     321    #define Ahead(x) makeLookAheadAssertion(x)
     322
     323    RE * GCB_Control = makeName("gcb", "cn", Name::Type::UnicodeProperty);
     324
     325    RE * GCB_1 = makeStart();
     326    RE * GCB_2 = makeEnd();
     327    RE * GCB_4 = Behind(GCB_Control);
     328    RE * GCB_5 = Ahead(GCB_Control);
     329
     330    RE * GCB_1_5 = makeAlt({GCB_1, GCB_2, makeSeq({GCB_4, GCB_5})});
     331
     332    RE * GCB_L = makeName("gcb", "l", Name::Type::UnicodeProperty);
     333    RE * GCB_V = makeName("gcb", "v", Name::Type::UnicodeProperty);
     334    RE * GCB_LV = makeName("gcb", "lv", Name::Type::UnicodeProperty);
     335    RE * GCB_LVT = makeName("gcb", "lvt", Name::Type::UnicodeProperty);
     336    RE * GCB_T = makeName("gcb", "t", Name::Type::UnicodeProperty);
     337    RE * GCB_RI = makeName("gcb", "ri", Name::Type::UnicodeProperty);
     338    // Legacy rules
     339    RE * GCB_6 = makeSeq({Behind(GCB_L), Ahead(makeAlt({GCB_L, GCB_V, GCB_LV, GCB_LVT}))});
     340    RE * GCB_7 = makeSeq({Behind(makeAlt({GCB_LV, GCB_V})), Ahead(makeAlt({GCB_V, GCB_T}))});
     341    RE * GCB_8 = makeSeq({Behind(makeAlt({GCB_LVT, GCB_T})), Ahead(GCB_T)});
     342    RE * GCB_8a = makeSeq({Behind(GCB_RI), Ahead(GCB_RI)});
     343    RE * GCB_9 = Ahead(makeName("gcb", "ex", Name::Type::UnicodeProperty));
     344    // Extended rules
     345    RE * GCB_9a = Ahead(makeName("gcb", "sm", Name::Type::UnicodeProperty));
     346    RE * GCB_9b = Behind(makeName("gcb", "pp", Name::Type::UnicodeProperty));
     347
     348    RE * GCB_6_9b = makeAlt({GCB_6, GCB_7, GCB_8, GCB_8a, GCB_9, GCB_9a, GCB_9b});
     349    Name * gcb = makeName("gcb", Name::Type::UnicodeProperty);
     350    gcb->setDefinition(makeDiff(GCB_6_9b,  GCB_1_5));
     351
     352    return gcb;
     353}
     354
    321355void RE_Compiler::finalizeMatchResult(MarkerType match_result) {
    322     mFunction.setResult(0, mPB.createAssign("matches", mPB.createAnd(mPB.createMatchStar(markerVar(match_result), mNonLineBreak), UNICODE_LINE_BREAK ? mUnicodeLineBreak : mLineFeed)));
     356    mFunction.setResult(0, mPB.createAssign("matches", mPB.createAnd(mPB.createMatchStar(markerVar(match_result), mAny), UNICODE_LINE_BREAK ? mUnicodeLineBreak : mLineFeed)));
    323357}
    324358
     
    327361}
    328362
    329 PabloAST * RE_Compiler::nextUnicodePosition(MarkerType m, PabloBuilder & pb) {
    330     if (markerPos(m) == MarkerPosition::FinalPostPositionByte) {
    331         return markerVar(m);
    332     } else if (markerPos(m) == MarkerPosition::InitialPostPositionByte) {
    333         return pb.createScanThru(pb.createAnd(mInitial, markerVar(m)), mNonFinal);
    334     } else {
    335         return pb.createScanThru(pb.createAnd(mInitial, pb.createAdvance(markerVar(m), 1)), mNonFinal);
    336     }
    337 }
    338 
    339363MarkerType RE_Compiler::process(RE * re, MarkerType marker, PabloBuilder & pb) {
    340364    if (Name * name = dyn_cast<Name>(re)) {
    341         return process(name, marker, pb);
    342     }
    343     else if (Seq* seq = dyn_cast<Seq>(re)) {
     365        return compileName(name, marker, pb);
     366    } else if (Seq* seq = dyn_cast<Seq>(re)) {
    344367        return process(seq, marker, pb);
    345     }
    346     else if (Alt * alt = dyn_cast<Alt>(re)) {
     368    } else if (Alt * alt = dyn_cast<Alt>(re)) {
    347369        return process(alt, marker, pb);
    348     }
    349     else if (Rep * rep = dyn_cast<Rep>(re)) {
     370    } else if (Rep * rep = dyn_cast<Rep>(re)) {
    350371        return process(rep, marker, pb);
    351     }
    352     else if (Assertion * a = dyn_cast<Assertion>(re)) {
     372    } else if (Assertion * a = dyn_cast<Assertion>(re)) {
    353373        return process(a, marker, pb);
    354     }
    355     else if (isa<Any>(re)) {
    356         PabloAST * nextPos = nextUnicodePosition(marker, pb);
    357         PabloAST * dot = pb.createNot(UNICODE_LINE_BREAK ? pb.createOr(mUnicodeLineBreak, mCRLF) : mLineFeed);
    358         return makeMarker(MarkerPosition::FinalMatchByte, pb.createAnd(nextPos, dot, "dot"));
    359     }
    360     else if (Diff * diff = dyn_cast<Diff>(re)) {
     374    } else if (isa<Any>(re)) {
     375        return compileAny(marker, pb);
     376    } else if (Diff * diff = dyn_cast<Diff>(re)) {
    361377        return process(diff, marker, pb);
    362     }
    363     else if (Intersect * ix = dyn_cast<Intersect>(re)) {
     378    } else if (Intersect * ix = dyn_cast<Intersect>(re)) {
    364379        return process(ix, marker, pb);
    365     }
    366     else if (isa<Start>(re)) {
     380    } else if (isa<Start>(re)) {
    367381        MarkerType m = AdvanceMarker(marker, MarkerPosition::InitialPostPositionByte, pb);
    368382        if (UNICODE_LINE_BREAK) {
     
    370384            PabloAST * sol = pb.createNot(pb.createOr(pb.createAdvance(pb.createNot(line_end), 1), mCRLF));
    371385            return makeMarker(MarkerPosition::InitialPostPositionByte, pb.createAnd(markerVar(m), sol, "sol"));
    372         }
    373         else {
     386        } else {
    374387            PabloAST * sol = pb.createNot(pb.createAdvance(pb.createNot(mLineFeed), 1));
    375388            return makeMarker(MarkerPosition::FinalPostPositionByte, pb.createAnd(markerVar(m), sol, "sol"));
    376389        }
    377     }
    378     else if (isa<End>(re)) {
     390    } else if (isa<End>(re)) {
    379391        if (UNICODE_LINE_BREAK) {
    380392            PabloAST * nextPos = markerVar(AdvanceMarker(marker, MarkerPosition::FinalPostPositionByte, pb));
     
    383395        PabloAST * nextPos = markerVar(AdvanceMarker(marker, MarkerPosition::InitialPostPositionByte, pb));  // For LF match
    384396        return makeMarker(MarkerPosition::FinalPostPositionByte, pb.createAnd(nextPos, mLineFeed, "eol"));
     397    } else if (GraphemeBoundary * gb = dyn_cast<GraphemeBoundary>(re)) {
     398        const auto inGraphemeBoundaryRule = mGraphemeBoundaryRule;
     399        mGraphemeBoundaryRule = gb->getGraphemeBoundaryRule();
     400        assert (mGraphemeBoundaryRule);
     401        marker = process(gb->getExpression(), marker, pb);
     402        mGraphemeBoundaryRule = inGraphemeBoundaryRule;
    385403    }
    386404    return marker;
    387405}
    388406
    389 MarkerType RE_Compiler::process(Name * name, MarkerType marker, PabloBuilder & pb) {
     407inline MarkerType RE_Compiler::compileAny(const MarkerType m, PabloBuilder & pb) {
     408    PabloAST * nextFinalByte = markerVar(AdvanceMarker(m, MarkerPosition::FinalPostPositionByte, pb));
     409    PabloAST * lb = mLineFeed;
     410    if (UNICODE_LINE_BREAK) {
     411        lb = pb.createOr(mUnicodeLineBreak, mCRLF);
     412    }
     413    PabloAST * dot = pb.createAnd(nextFinalByte, pb.createNot(lb), "dot");
     414    MarkerPosition pos = MarkerPosition::FinalMatchByte;
     415    if (mGraphemeBoundaryRule) {
     416        dot = pb.createScanThru(dot, pb.createOr(dot, mGraphemeBoundaryRule->getCompiled()), "dot_gext");
     417        pos = MarkerPosition::InitialPostPositionByte;
     418    }
     419    return makeMarker(pos, dot);
     420}
     421
     422inline MarkerType RE_Compiler::compileName(Name * name, MarkerType marker, PabloBuilder & pb) {
    390423    MarkerType nextPos;
    391424    if (markerPos(marker) == MarkerPosition::FinalPostPositionByte) {
    392425        nextPos = marker;
    393     }
    394     else if (name->getType() == Name::Type::Byte) {
     426    } else if (name->getType() == Name::Type::Byte) {
    395427        nextPos = AdvanceMarker(marker, MarkerPosition::InitialPostPositionByte, pb);
    396     }
    397     else {
     428    } else {
    398429        nextPos = AdvanceMarker(marker, MarkerPosition::FinalPostPositionByte, pb);
    399430    }
    400     return makeMarker(MarkerPosition::FinalMatchByte, pb.createAnd(markerVar(nextPos), getNamedCharacterClassStream(name, pb), "m"));
    401 }
    402 
    403 PabloAST * RE_Compiler::getNamedCharacterClassStream(Name * name, PabloBuilder & pb) {
     431    PabloAST * namePos = pb.createAnd(markerVar(nextPos), compileName(name, pb), name->getName());
     432    MarkerPosition pos = MarkerPosition::FinalMatchByte;
     433    if (mGraphemeBoundaryRule) {
     434        namePos = pb.createScanThru(namePos, pb.createOr(namePos, pb.createOr(mNonFinal, mGraphemeBoundaryRule->getCompiled())), name->getName() + "_gext");
     435        pos = MarkerPosition::FinalPostPositionByte;
     436    }
     437    return makeMarker(pos, namePos);
     438}
     439
     440inline PabloAST * RE_Compiler::compileName(Name * name, PabloBuilder & pb) {
    404441    PabloAST * var = name->getCompiled();
    405442    if (LLVM_LIKELY(var != nullptr)) {
     
    408445        MarkerType m = compile(name->getDefinition(), pb);
    409446        assert(markerPos(m) == MarkerPosition::FinalMatchByte);
    410         var = pb.createAnd(markerVar(m), mNonLineBreak);
     447        var = pb.createAnd(markerVar(m), mAny);
    411448        name->setCompiled(var);
    412449        return var;
    413     } else {
    414         throw std::runtime_error("Unresolved name " + name->getName());
    415     }
     450    }
     451    throw std::runtime_error("Unresolved name " + name->getName());
    416452}
    417453
     
    423459        }
    424460        return marker;
    425     }
    426     else {
     461    } else {
    427462        return processSeqTail(seq->begin(), seq->end(), 0, marker, pb);
    428463    }
     
    436471        current++;
    437472        return processSeqTail(current, end, matchLenSoFar + minMatchLength(r), marker, pb);
    438     }
    439     else {
     473    } else {
    440474        PabloBuilder nested = PabloBuilder::Create(pb);
    441475        MarkerType m1 = processSeqTail(current, end, 0, marker, nested);
     
    479513        }
    480514        return makeMarker(markerPos(m), pb.createAnd(markerVar(marker), lb, "lookback"));
    481     }
    482     else if (isUnicodeUnitLength(asserted)) {
     515    } else if (isUnicodeUnitLength(asserted)) {
    483516        MarkerType lookahead = compile(asserted, pb);
    484517        assert(markerPos(lookahead) == MarkerPosition::FinalMatchByte);
     
    490523        return makeMarker(MarkerPosition::FinalPostPositionByte, pb.createAnd(markerVar(fbyte), la, "lookahead"));
    491524    }
    492     else {
    493         throw std::runtime_error("Unsupported lookahead assertion.");
    494     }
     525    throw std::runtime_error("Unsupported lookahead assertion.");
     526}
     527
     528inline bool alignedUnicodeLength(const RE * lh, const RE * rh) {
     529    const auto lhl = getUnicodeUnitLengthRange(lh);
     530    const auto rhl = getUnicodeUnitLengthRange(rh);
     531    return (lhl.first == lhl.second && lhl.first == rhl.first && lhl.second == rhl.second);
    495532}
    496533
     
    498535    RE * lh = diff->getLH();
    499536    RE * rh = diff->getRH();
    500     if (isUnicodeUnitLength(lh) && isUnicodeUnitLength(rh)) {
     537    if (alignedUnicodeLength(lh, rh)) {
    501538        MarkerType t1 = process(lh, marker, pb);
    502539        MarkerType t2 = process(rh, marker, pb);
     
    510547    RE * lh = x->getLH();
    511548    RE * rh = x->getRH();
    512     if (isUnicodeUnitLength(lh) && isUnicodeUnitLength(rh)) {
     549    if (alignedUnicodeLength(lh, rh)) {
    513550        MarkerType t1 = process(lh, marker, pb);
    514551        MarkerType t2 = process(rh, marker, pb);
     
    619656   
    620657    if (isByteLength(repeated)  && !DisableMatchStar) {
    621         PabloAST * cc = markerVar(compile(repeated, pb)); 
    622         PabloAST * mstar = SetMod64Approximation ? pb.createMod64MatchStar(base, cc) : pb.createMatchStar(base, cc, "unbounded");
     658        PabloAST * cc = markerVar(compile(repeated, pb));
     659        PabloAST * mstar = nullptr;
     660        if (SetMod64Approximation) {
     661            mstar = pb.createMod64MatchStar(base, cc, "unbounded");
     662        } else {
     663            mstar = pb.createMatchStar(base, cc, "unbounded");
     664        }
    623665        return makeMarker(MarkerPosition::InitialPostPositionByte, mstar);
    624666    }
    625667    else if (isUnicodeUnitLength(repeated) && !DisableMatchStar && !DisableUnicodeMatchStar) {
    626668        PabloAST * cc = markerVar(compile(repeated, pb));
    627         PabloAST * mstar = SetMod64Approximation ? pb.createMod64MatchStar(base, pb.createOr(mNonFinal, cc)) : pb.createMatchStar(base, pb.createOr(mNonFinal, cc));
    628         return makeMarker(MarkerPosition::FinalPostPositionByte, pb.createAnd(mstar, mFinal, "unbounded"));
    629     }
    630     else if (mStarDepth > 0){
    631        
     669        PabloAST * mstar = nullptr;
     670        PabloAST * nonFinal = mNonFinal;
     671        if (mGraphemeBoundaryRule) {
     672            nonFinal = pb.createOr(nonFinal, pb.createNot(mGraphemeBoundaryRule->getCompiled()));
     673        }
     674        cc = pb.createOr(cc, nonFinal);
     675        if (SetMod64Approximation) {
     676            mstar = pb.createMod64MatchStar(base, cc);
     677        } else {
     678            mstar = pb.createMatchStar(base, cc);
     679        }
     680        PabloAST * final = mFinal;
     681        if (mGraphemeBoundaryRule) {
     682            final = pb.createOr(final, mGraphemeBoundaryRule->getCompiled());
     683        }
     684        return makeMarker(MarkerPosition::FinalPostPositionByte, pb.createAnd(mstar, final, "unbounded"));
     685    } else if (mStarDepth > 0){
     686
    632687        PabloBuilder * outerb = pb.getParent();
    633688       
     
    647702       
    648703        return makeMarker(MarkerPosition::InitialPostPositionByte, pb.createAssign("unbounded", pb.createOr(base, nextStarAccum)));
    649     }   
    650     else {
     704    } else {
    651705        Assign * whileTest = pb.createAssign("test", base);
    652706        Assign * whilePending = pb.createAssign("pending", base);
     
    669723        return makeMarker(MarkerPosition::InitialPostPositionByte, pb.createAssign("unbounded", nextWhileAccum));
    670724    }   
     725}
     726
     727inline MarkerType RE_Compiler::AdvanceMarker(const MarkerType m, const MarkerPosition newpos, PabloBuilder & pb) {
     728    if (m.pos == newpos) return m;
     729    PabloAST * a = m.stream;
     730    if (m.pos == MarkerPosition::FinalMatchByte) {
     731        // Must advance the previous marker to the InitialPostPositionByte
     732        a = pb.createAdvance(a, 1, "initial");
     733    }
     734    // Now at InitialPostPositionByte; is a further advance needed?
     735    if (newpos == MarkerPosition::FinalPostPositionByte) {
     736        // Must advance through nonfinal bytes
     737        a = pb.createScanThru(pb.createAnd(mInitial, a), mNonFinal, "final");
     738    }
     739    return {newpos, a};
     740}
     741
     742inline void RE_Compiler::AlignMarkers(MarkerType & m1, MarkerType & m2, PabloBuilder & pb) {
     743    if (m1.pos < m2.pos) {
     744        m1 = AdvanceMarker(m1, m2.pos, pb);
     745    } else if (m2.pos < m1.pos) {
     746        m2 = AdvanceMarker(m2, m1.pos, pb);
     747    }
     748}
     749
     750RE_Compiler::RE_Compiler(pablo::PabloFunction & function, cc::CC_Compiler & ccCompiler)
     751: mCCCompiler(ccCompiler)
     752, mLineFeed(nullptr)
     753, mCRLF(nullptr)
     754, mUnicodeLineBreak(nullptr)
     755, mAny(nullptr)
     756, mGraphemeBoundaryRule(nullptr)
     757, mInitial(nullptr)
     758, mNonFinal(nullptr)
     759, mFinal(nullptr)
     760, mWhileTest(nullptr)
     761, mStarDepth(0)
     762, mLoopVariants()
     763, mPB(*ccCompiler.getBuilder().getPabloBlock(), ccCompiler.getBuilder())
     764, mFunction(function)
     765{
     766
     767}
     768
    671769} // end of namespace re
    672 }
  • icGREP/icgrep-devel/icgrep/re/re_compiler.h

    r4814 r4829  
    6363
    6464    MarkerType compile(RE * re, pablo::PabloBuilder & cg);
    65     MarkerType AdvanceMarker(MarkerType m, MarkerPosition newpos, pablo::PabloBuilder & pb);
     65    MarkerType AdvanceMarker(const MarkerType m, const MarkerPosition newpos, pablo::PabloBuilder & pb);
    6666   
    6767    void AlignMarkers(MarkerType & m1, MarkerType & m2, pablo::PabloBuilder & pb);
    6868   
    69     pablo::PabloAST * getNamedCharacterClassStream(Name * name, pablo::PabloBuilder & pb);
    70     pablo::PabloAST * nextUnicodePosition(MarkerType m, pablo::PabloBuilder & pb);
    7169    MarkerType process(RE * re, MarkerType marker, pablo::PabloBuilder & pb);
    72     MarkerType process(Name * name, MarkerType marker, pablo::PabloBuilder & pb);
     70    MarkerType compileName(Name * name, MarkerType marker, pablo::PabloBuilder & pb);
    7371    MarkerType process(Seq * seq, MarkerType marker, pablo::PabloBuilder & pb);
    7472    MarkerType processSeqTail(Seq::iterator current, Seq::iterator end, int matchLenSoFar, MarkerType marker, pablo::PabloBuilder & pb);
     
    8684    RE * resolveUnicodeProperties(RE * re);
    8785
     86    Name * generateGraphemeClusterBoundaryRule();
     87    pablo::PabloAST * compileName(Name * name, pablo::PabloBuilder & pb);
     88    MarkerType compileAny(const MarkerType m, pablo::PabloBuilder & pb);
     89
    8890private:
    8991
     
    9294    pablo::PabloAST *                               mCRLF;
    9395    pablo::PabloAST *                               mUnicodeLineBreak;
    94     pablo::PabloAST *                               mNonLineBreak;
     96    pablo::PabloAST *                               mAny;
     97    Name *                                          mGraphemeBoundaryRule;
    9598    pablo::PabloAST *                               mInitial;
    9699    pablo::Assign *                                 mNonFinal;
  • icGREP/icgrep-devel/icgrep/re/re_nullable.cpp

    r4684 r4829  
    55#include <re/re_alt.h>
    66#include <re/re_rep.h>
    7 #include <re/re_simplifier.h>
    8 #include <re/printer_re.h>
    9 #include <iostream>
     7#include <re/re_grapheme_boundary.hpp>
     8#include <re/re_name.h>
     9
    1010/*
    1111
     
    2929        }
    3030        re = makeSeq(list.begin(), list.end());
    31     }
    32     else if (Alt * alt = dyn_cast<Alt>(re)) {
     31    } else if (Alt * alt = dyn_cast<Alt>(re)) {
    3332        std::vector<RE*> list;
    3433        for (auto i = alt->begin(); i != alt->end(); ++i) {
     
    3635        }
    3736        re = makeAlt(list.begin(), list.end());
    38     }
    39     else if (Rep * rep = dyn_cast<Rep>(re)) {
     37    } else if (Rep * rep = dyn_cast<Rep>(re)) {
    4038        if ((rep->getLB() == 0) || (isNullable(rep->getRE()))) {
    4139            re = makeSeq();
     
    4745            re = makeRep(rep->getRE(), rep->getLB(), rep->getLB());
    4846        }
     47    } else if (Name * name = dyn_cast<Name>(re)) {
     48        if (name->getDefinition()) {
     49            name->setDefinition(removeNullablePrefix(name->getDefinition()));
     50        }
     51    } else if (GraphemeBoundary * g = dyn_cast<GraphemeBoundary>(re)) {
     52        g->setExpression(removeNullablePrefix(g->getExpression()));
    4953    }
    5054    return re;
     
    6266        }
    6367        re = makeSeq(list.begin(), list.end());
    64     }
    65     else if (Alt* alt = dyn_cast<Alt>(re)) {
     68    } else if (Alt* alt = dyn_cast<Alt>(re)) {
    6669        std::vector<RE*> list;
    6770        for (auto i = alt->begin(); i != alt->end(); ++i) {
     
    6972        }
    7073        re = makeAlt(list.begin(), list.end());
    71     }
    72     else if (Rep * rep = dyn_cast<Rep>(re)) {
     74    } else if (Rep * rep = dyn_cast<Rep>(re)) {
    7375        if ((rep->getLB() == 0) || (isNullable(rep->getRE()))) {
    7476            re = makeSeq();
     
    8082            re = makeRep(rep->getRE(), rep->getLB(), rep->getLB());
    8183        }
     84    } else if (Name * name = dyn_cast<Name>(re)) {
     85        if (name->getDefinition()) {
     86            name->setDefinition(removeNullableSuffix(name->getDefinition()));
     87        }
     88    } else if (GraphemeBoundary * g = dyn_cast<GraphemeBoundary>(re)) {
     89        g->setExpression(removeNullableSuffix(g->getExpression()));
    8290    }
    8391    return re;
     
    92100        }
    93101        return true;
    94     }
    95     else if (const Alt * re_alt = dyn_cast<const Alt>(re)) {
     102    } else if (const Alt * re_alt = dyn_cast<const Alt>(re)) {
    96103        for (const RE * re : *re_alt) {
    97104            if (isNullable(re)) {
     
    99106            }
    100107        }
    101     }
    102     else if (const Rep* re_rep = dyn_cast<const Rep>(re)) {
     108    } else if (const Rep* re_rep = dyn_cast<const Rep>(re)) {
    103109        return re_rep->getLB() == 0 ? true : isNullable(re_rep->getRE());
    104110    }
     
    110116    if (const Seq * seq = dyn_cast<const Seq>(re)) {
    111117        nullable = isNullable(seq->front()) ? true : hasNullablePrefix(seq->front());
    112     }
    113     else if (const Alt * alt = dyn_cast<const Alt>(re)) {
     118    } else if (const Alt * alt = dyn_cast<const Alt>(re)) {
    114119        for (const RE * re : *alt) {
    115120            if (hasNullablePrefix(re)) {
     
    118123            }
    119124        }
    120     }
    121     else if (const Rep * rep = dyn_cast<const Rep>(re)) {
     125    } else if (const Rep * rep = dyn_cast<const Rep>(re)) {
    122126        nullable = true;
    123127        if (rep->getLB() == rep->getUB()) {
     
    132136    if (const Seq * seq = dyn_cast<const Seq>(re)) {
    133137        nullable = isNullable(seq->back()) ? true : hasNullableSuffix(seq->back());
    134     }
    135     else if (const Alt * alt = dyn_cast<const Alt>(re)) {
     138    } else if (const Alt * alt = dyn_cast<const Alt>(re)) {
    136139        for (const RE * re : *alt) {
    137140            if (hasNullableSuffix(re)) {
     
    140143            }
    141144        }
    142     }
    143     else if (const Rep * rep = dyn_cast<const Rep>(re)) {
     145    } else if (const Rep * rep = dyn_cast<const Rep>(re)) {
    144146        nullable = true;
    145147        if (rep->getLB() == rep->getUB()) {
  • icGREP/icgrep-devel/icgrep/re/re_parser.cpp

    r4826 r4829  
    1515#include <re/re_intersect.h>
    1616#include <re/re_assertion.h>
    17 #include <re/parsefailure.h>
     17#include <re/re_grapheme_boundary.hpp>
    1818#include <re/printer_re.h>
    1919#include <UCD/resolve_properties.h>
     
    4141    RE_Parser parser(regular_expression);
    4242    parser.fModeFlagSet = initialFlags;
     43
    4344    parser.fNested = false;
    4445    RE * re = parser.parse_RE();
     
    5051
    5152inline RE_Parser::RE_Parser(const std::string & regular_expression)
    52     : _cursor(regular_expression.begin())
    53     , _end(regular_expression.end())
     53    : mCursor(regular_expression)
    5454    , fModeFlagSet(0)
    5555    , fNested(false)
     
    5757
    5858    }
    59 
    60 RE * makeLookAheadAssertion(RE * r) {
    61     return makeAssertion(r, Assertion::Kind::Lookahead, Assertion::Sense::Positive);
    62 }
    63 
    64 RE * makeNegativeLookAheadAssertion(RE * r) {
    65     return makeAssertion(r, Assertion::Kind::Lookahead, Assertion::Sense::Negative);
    66 }
    67 
    68 RE * makeLookBehindAssertion(RE * r) {
    69     return makeAssertion(r, Assertion::Kind::Lookbehind, Assertion::Sense::Positive);
    70 }
    71 
    72 RE * makeNegativeLookBehindAssertion(RE * r) {
    73     return makeAssertion(r, Assertion::Kind::Lookbehind, Assertion::Sense::Negative);
    74 }
    7559
    7660RE * makeAtomicGroup(RE * r) {
     
    9377    for (;;) {
    9478        alt.push_back(parse_seq());
    95         if (_cursor == _end || *_cursor != '|') {
     79        if (mCursor.noMore() || *mCursor != '|') {
    9680            break;
    9781        }
    98         ++_cursor; // advance past the alternation character '|'
     82        ++mCursor; // advance past the alternation character '|'
    9983    }
    10084    if (alt.empty())
     
    120104RE * RE_Parser::parse_next_item() {
    121105    RE * re = nullptr;
    122     if (_cursor != _end) {
    123         switch (*_cursor) {
     106    if (mCursor.more()) {
     107        switch (*mCursor) {
    124108            case '(':
    125                 ++_cursor;
     109                ++mCursor;
    126110                return parse_group();
    127111            case '^':
    128                 ++_cursor;
     112                ++mCursor;
    129113                return makeStart();
    130114            case '$':
    131                 ++_cursor;
     115                ++mCursor;
    132116                return makeEnd();
    133117            case '|': case ')':
     
    149133                else throw ParseFailure("Use \\} for literal }.");
    150134            case '[':
    151                 _cursor++;
     135                mCursor++;
    152136                return parse_charset();
    153137            case '.': // the 'any' metacharacter
    154                 _cursor++;
     138                mCursor++;
    155139                return makeAny();
    156140            case '\\':  // escape processing
    157                 ++_cursor;
     141                ++mCursor;
    158142                return parse_escaped();
    159143            default:
     
    171155    RE * group_expr;
    172156    ModeFlagSet savedModeFlags = fModeFlagSet;
    173     throw_incomplete_expression_error_if_end_of_stream();
    174     if (*_cursor == '?') {
    175         ++_cursor;
    176         throw_incomplete_expression_error_if_end_of_stream();
    177         switch (*_cursor) {
     157    if (*mCursor == '?') {
     158        switch (*++mCursor) {
    178159            case '#':  // comment
    179                 ++_cursor;
    180                 while (_cursor != _end && *_cursor != ')') {
    181                     ++_cursor;
    182                 }
    183                 throw_incomplete_expression_error_if_end_of_stream();
    184                 ++_cursor;
     160                ++mCursor;
     161                while (mCursor.more() && *mCursor != ')') {
     162                    ++mCursor;
     163                }
     164                ++mCursor;
    185165                return parse_next_item();
    186166            case ':':  // Non-capturing paren
    187                 ++_cursor;
     167                ++mCursor;
    188168                group_expr = parse_alt();
    189169                break;
    190170            case '=':
    191                 ++_cursor;
     171                ++mCursor;
    192172                subexpr = parse_alt();
    193173                group_expr = makeLookAheadAssertion(subexpr);
    194174                break;
    195175            case '!':
    196                 ++_cursor;
     176                ++mCursor;
    197177                subexpr = parse_alt();
    198178                group_expr = makeNegativeLookAheadAssertion(subexpr);
    199179                break;
    200180            case '>':
    201                 ++_cursor;
     181                ++mCursor;
    202182                subexpr = parse_alt();
    203183                group_expr = makeAtomicGroup(subexpr);
    204184                break;
    205185            case '|':
    206                 ++_cursor;
     186                ++mCursor;
    207187                subexpr = parse_alt();
    208188                group_expr = makeBranchResetGroup(subexpr);
    209189                break;
    210190            case '<':
    211                 ++_cursor;
    212                 throw_incomplete_expression_error_if_end_of_stream();
    213                 if (*_cursor == '=') {
    214                     ++_cursor;
     191                ++mCursor;
     192                if (*mCursor == '=') {
     193                    ++mCursor;
    215194                    subexpr = parse_alt();
    216195                    group_expr = makeLookBehindAssertion(subexpr);
    217196                }
    218                 else if (*_cursor == '!') {
    219                     ++_cursor;
     197                else if (*mCursor == '!') {
     198                    ++mCursor;
    220199                    subexpr = parse_alt();
    221200                    group_expr = makeNegativeLookBehindAssertion(subexpr);
    222                 }
    223                 else {
     201                } else {
    224202                    throw ParseFailure("Illegal lookbehind assertion syntax.");
    225203                }
     
    228206                bool negateMode = false;
    229207                ModeFlagType modeBit;
    230                 while (_cursor != _end && *_cursor != ')' && *_cursor != ':') {
    231                     if (*_cursor == '-') {
     208                while (mCursor.more() && *mCursor != ')' && *mCursor != ':') {
     209                    if (*mCursor == '-') {
    232210                        negateMode = true;
    233                         _cursor++;
    234                         throw_incomplete_expression_error_if_end_of_stream();
    235                     }
    236                     switch (*_cursor++) {
     211                        ++mCursor;
     212                    }
     213                    switch (*mCursor++) {
    237214                        case 'i': modeBit = CASE_INSENSITIVE_MODE_FLAG; break;
    238215                        //case 'm': modeBit = MULTILINE_MODE_FLAG; break;
     
    245222                        fModeFlagSet &= ~modeBit;
    246223                        negateMode = false;  // for next flag
    247                     }
    248                     else fModeFlagSet |= modeBit;
    249                 }
    250                 throw_incomplete_expression_error_if_end_of_stream();
    251                 if (*_cursor == ':') {
    252                     ++_cursor;
     224                    } else {
     225                        fModeFlagSet |= modeBit;
     226                    }
     227                }
     228                if (*mCursor == ':') {
     229                    ++mCursor;
    253230                    group_expr = parse_alt();
    254                 }
    255                 else {  // if *_cursor == ')'
    256                     ++_cursor;
    257             // return immediately without restoring mode flags
     231                } else {  // if *_cursor == ')'
     232                    ++mCursor;
     233                    // return immediately without restoring mode flags
    258234                    return parse_next_item();
    259235                }
     
    263239                throw ParseFailure("Illegal (? syntax.");
    264240        }
    265     }
    266     else {
    267         // Capturing paren group, but ignore capture in icgrep.
     241    } else { // Capturing paren group, but ignore capture in icgrep.
    268242        group_expr = parse_alt();
    269243    }
    270244    // Restore mode flags.
    271245    fModeFlagSet = savedModeFlags;
    272     if (_cursor == _end || *_cursor++ != ')')
    273         throw ParseFailure("Closing paren required.");
     246    if (*mCursor != ')') {
     247        throw ParseFailure("Closing parenthesis required.");
     248    }
     249    ++mCursor;
    274250    return group_expr;
    275251}
    276252
    277253RE * RE_Parser::extend_item(RE * re) {
    278     int lower_bound, upper_bound;
    279     if (_cursor == _end) {
     254    if (mCursor.noMore()) {
    280255        return re;
    281     }
    282     switch (*_cursor) {
    283         case '*':
    284             lower_bound = 0;
    285             upper_bound = Rep::UNBOUNDED_REP;
    286             break;
    287         case '?':
    288             lower_bound = 0;
    289             upper_bound = 1;
    290             break;
    291         case '+':
    292             lower_bound = 1;
    293             upper_bound = Rep::UNBOUNDED_REP;
    294             break;
    295         case '{':
    296             parse_range_bound(lower_bound, upper_bound);
    297             break;
    298         default:
     256    } else {
     257        int lb = 0, ub = 0;
     258        switch (*mCursor) {
     259            case '*':
     260                lb = 0;
     261                ub = Rep::UNBOUNDED_REP;
     262                break;
     263            case '?':
     264                lb = 0;
     265                ub = 1;
     266                break;
     267            case '+':
     268                lb = 1;
     269                ub = Rep::UNBOUNDED_REP;
     270                break;
     271            case '{':
     272                std::tie(lb, ub) = parse_range_bound();
     273                break;
     274            case '\\':
     275                re = parseGraphemeBoundary(re);
     276            default:
     277                return re;
     278        }
     279        if (lb > MAX_REPETITION_LOWER_BOUND || ub > MAX_REPETITION_UPPER_BOUND) {
     280            throw ParseFailure("Bounded repetition exceeds icgrep implementation limit");
     281        }
     282        if ((ub != Rep::UNBOUNDED_REP) && (lb > ub)) {
     283            throw ParseFailure("Lower bound cannot exceed upper bound in bounded repetition");
     284        }
     285        ++mCursor;
     286        if (mCursor.more()) {
     287            if (*mCursor == '?') { // Non-greedy qualifier
     288                // Greedy vs. non-greedy makes no difference for icgrep.
     289                ++mCursor;
     290            } else if (*mCursor == '+') {
     291                ++mCursor;
     292                throw ParseFailure("Possessive repetition is not supported in icgrep 1.0");
     293            }
     294        }
     295        return makeRep(re, lb, ub);
     296    }
     297}
     298
     299RE * RE_Parser::parseGraphemeBoundary(RE * re) {
     300    if (mCursor.remaining() > 3) {
     301        Cursor cursor(mCursor);
     302        bool complement = false;
     303        ++cursor;
     304        if (*cursor == 'b') {
     305            complement = false;
     306        } else if (*cursor == 'B') {
     307            complement = true;
     308        } else {
    299309            return re;
    300     }
    301     if (lower_bound > MAX_REPETITION_LOWER_BOUND || upper_bound > MAX_REPETITION_UPPER_BOUND) {
    302         throw ParseFailure("Bounded repetition exceeds icgrep implementation limit");
    303     }
    304     if ((upper_bound != Rep::UNBOUNDED_REP) && (lower_bound > upper_bound)) {
    305         throw ParseFailure("Lower bound cannot exceed upper bound in bounded repetition");
    306     }
    307     ++_cursor;
    308     if (*_cursor == '?') {
    309         // Non-greedy qualifier
    310         ++_cursor;
    311         //return makeNonGreedyRep(re, lower_bound, upper_bound);
    312         // Greedy vs. non-greedy makes no difference for icgrep.
    313         return makeRep(re, lower_bound, upper_bound);
    314     }
    315     else if (*_cursor == '+') {
    316         // Possessive qualifier
    317         ++_cursor;
    318         //return makePossessiveRep(re, lower_bound, upper_bound);
    319         throw ParseFailure("Possessive repetition is not supported in icgrep 1.0");
    320     }
    321     else {
    322         // Normal repetition operator.
    323         return makeRep(re, lower_bound, upper_bound);
    324     }
    325 }
    326 
    327 inline void RE_Parser::parse_range_bound(int & lower_bound, int & upper_bound) {
    328     ++_cursor;
    329     throw_incomplete_expression_error_if_end_of_stream();
    330     if (*_cursor == ',') {
    331         ++_cursor;
     310        }
     311        // since /b and /B also denote word break, which could also be extended with a range,
     312        // we'll quietly abort if we cannot find a valid grapheme boundary identifier
     313        if (*++cursor == '{') {
     314            GraphemeBoundary::Type type = GraphemeBoundary::Type::ClusterBoundary;
     315            switch (*++cursor) {
     316                case 'g': type = GraphemeBoundary::Type::ClusterBoundary; break;
     317                case 'w': type = GraphemeBoundary::Type::WordBoundary; break;
     318                case 'l': type = GraphemeBoundary::Type::LineBreakBoundary; break;
     319                case 's': type = GraphemeBoundary::Type::SentenceBoundary; break;
     320                default: return re;
     321            }
     322            if (*++cursor == '}') {
     323                mCursor = ++cursor;
     324                re = makeGraphemeBoundary(re, type);
     325            }
     326        }
     327    }
     328    return re;
     329}
     330
     331inline std::pair<int, int> RE_Parser::parse_range_bound() {
     332    int lower_bound = 0, upper_bound = 0;
     333    ++mCursor;
     334    if (*mCursor == ',') {
     335        ++mCursor;
    332336        lower_bound = 0;
    333     }
    334     else {
     337    } else {
    335338        lower_bound = parse_int();
    336339    }
    337     throw_incomplete_expression_error_if_end_of_stream();
    338     if (*_cursor == '}') {
     340    if (*mCursor == '}') {
    339341        upper_bound = lower_bound;
    340     }
    341     else if (*_cursor != ',') {
     342    } else if (*mCursor != ',') {
    342343        throw BadLowerBound();
    343     }
    344     else { // [^,}]
    345         ++_cursor;
    346         throw_incomplete_expression_error_if_end_of_stream();
    347         if (*_cursor == '}') {
     344    } else { // [^,}]
     345        ++mCursor;
     346        if (*mCursor == '}') {
    348347            upper_bound = Rep::UNBOUNDED_REP;
    349348        }
    350349        else {
    351350            upper_bound = parse_int();
    352             if (*_cursor != '}') {
     351            if (*mCursor != '}') {
    353352                throw BadUpperBound();
    354353            }
    355354        }
    356355    }
     356    return std::make_pair(lower_bound, upper_bound);
    357357}
    358358
    359359unsigned RE_Parser::parse_int() {
    360360    unsigned value = 0;
    361     for (; _cursor != _end; ++_cursor) {
    362         if (!isdigit(*_cursor)) {
     361    for (; mCursor.more(); ++mCursor) {
     362        if (!isdigit(*mCursor)) {
    363363            break;
    364364        }
    365365        value *= 10;
    366         value += static_cast<int>(*_cursor) - 48;
     366        value += static_cast<int>(*mCursor) - 48;
    367367    }
    368368    return value;
     
    371371
    372372#define bit40(x) (1ULL << ((x) - 0x40))
    373 const uint64_t setEscapeCharacters = bit40('b') | bit40('p') | bit40('d') | bit40('w') | bit40('s') |
    374                                      bit40('B') | bit40('P') | bit40('D') | bit40('W') | bit40('S') | bit40('N');
     373const uint64_t setEscapeCharacters = bit40('b') | bit40('p') | bit40('q') | bit40('d') | bit40('w') | bit40('s') |
     374                                     bit40('B') | bit40('P') | bit40('Q') | bit40('D') | bit40('W') | bit40('S') | bit40('N') | bit40('X');
    375375
    376376inline bool isSetEscapeChar(char c) {
     
    379379
    380380inline RE * RE_Parser::parse_escaped() {
    381     throw_incomplete_expression_error_if_end_of_stream();
    382     if (isSetEscapeChar(*_cursor))
     381    if (isSetEscapeChar(*mCursor))
    383382      return parseEscapedSet();
    384383    else
     
    388387RE * RE_Parser::parseEscapedSet() {
    389388    bool complemented = false;
    390     RE * s;
    391     switch (*_cursor) {
     389    RE * re = nullptr;
     390    switch (*mCursor) {
    392391        case 'b':
    393             ++_cursor;
     392            ++mCursor;
    394393            return makeWordBoundary();
    395394        case 'B':
    396             ++_cursor;
     395            ++mCursor;
    397396            return makeWordNonBoundary();
    398397        case 'd':
    399             ++_cursor;
     398            ++mCursor;
    400399            return makeDigitSet();
    401400        case 'D':
    402             ++_cursor;
     401            ++mCursor;
    403402            return makeComplement(makeDigitSet());
    404403        case 's':
    405             ++_cursor;
     404            ++mCursor;
    406405            return makeWhitespaceSet();
    407406        case 'S':
    408             ++_cursor;
     407            ++mCursor;
    409408            return makeComplement(makeWhitespaceSet());
    410409        case 'w':
    411             ++_cursor;
     410            ++mCursor;
    412411            return makeWordSet();
    413412        case 'W':
    414             ++_cursor;
     413            ++mCursor;
    415414            return makeComplement(makeWordSet());
     415        case 'Q':
     416            complemented = true;
     417        case 'q':
     418            if (*++mCursor != '{') {
     419                throw ParseFailure("Malformed grapheme-boundary property expression");
     420            }
     421            ++mCursor;
     422            re = parsePropertyExpression();
     423            if (*mCursor != '}') {
     424                throw ParseFailure("Malformed grapheme-boundary property expression");
     425            }
     426            ++mCursor;
     427            re = makeGraphemeBoundary(re, GraphemeBoundary::Type::ClusterBoundary);
     428            return complemented ? makeComplement(re) : re;
    416429        case 'P':
    417430            complemented = true;
    418431        case 'p':
    419             ++_cursor;
    420             if (_cursor == _end || *_cursor != '{') throw ParseFailure("Malformed property expression");
    421             ++_cursor;
    422             s = parsePropertyExpression();
    423             if (_cursor == _end || *_cursor != '}') throw ParseFailure("Malformed property expression");
    424             ++_cursor;
    425             return complemented ? makeComplement(s) : s;
     432            if (*++mCursor != '{') {
     433                throw ParseFailure("Malformed property expression");
     434            }
     435            ++mCursor;
     436            re = parsePropertyExpression();
     437            if (*mCursor != '}') {
     438                throw ParseFailure("Malformed property expression");
     439            }
     440            ++mCursor;
     441            return complemented ? makeComplement(re) : re;
     442        case 'X':
     443            // \X is equivalent to ".+?\b{g}"; proceed the minimal number of characters (but at least one)
     444            // to get to the next extended grapheme cluster boundary. Nullable transforms this to ".\b{g}".
     445            ++mCursor;
     446            return makeGraphemeBoundary(makeAny(), GraphemeBoundary::Type::ClusterBoundary);
    426447        case 'N':
    427             ++_cursor;
    428             if (_cursor == _end || *_cursor != '{') throw ParseFailure("Malformed \\N expression");
    429             ++_cursor;
    430             s = parseNamePatternExpression();
    431             if (_cursor == _end || *_cursor != '}') throw ParseFailure("Malformed \\N expression");
    432             ++_cursor;
    433             return s;
     448            if (*++mCursor != '{') {
     449                throw ParseFailure("Malformed \\N expression");
     450            }
     451            ++mCursor;
     452            re = parseNamePatternExpression();
     453            if (*mCursor != '}') {
     454                throw ParseFailure("Malformed \\N expression");
     455            }
     456            ++mCursor;
     457            return re;
    434458        default:
    435459            throw ParseFailure("Internal error");
     
    439463codepoint_t RE_Parser::parse_utf8_codepoint() {
    440464    // Must cast to unsigned char to avoid sign extension.
    441     unsigned char pfx = static_cast<unsigned char>(*_cursor++);
     465    unsigned char pfx = static_cast<unsigned char>(*mCursor++);
    442466    codepoint_t cp = pfx;
    443467    if (pfx < 0x80) return cp;
    444     unsigned suffix_bytes;
     468    unsigned suffix_bytes = 0;
    445469    if (pfx < 0xE0) {
    446470        if (pfx < 0xC2) {  // bare suffix or illegal prefix 0xC0 or 0xC2
     
    449473        suffix_bytes = 1;
    450474        cp &= 0x1F;
    451     }
    452     else if (pfx < 0xF0) { // [0xE0, 0xEF]
     475    } else if (pfx < 0xF0) { // [0xE0, 0xEF]
    453476        cp &= 0x0F;
    454477        suffix_bytes = 2;
    455     }
    456     else { // [0xF0, 0xFF]
     478    } else { // [0xF0, 0xFF]
    457479        cp &= 0x0F;
    458480        suffix_bytes = 3;
    459481    }
    460482    while (suffix_bytes--) {
    461         if (_cursor == _end) {
     483        if (mCursor.noMore()) {
    462484            throw InvalidUTF8Encoding();
    463485        }
    464         unsigned char sfx = static_cast<unsigned char>(*_cursor++);
     486        char_t sfx = *mCursor++;
    465487        if ((sfx & 0xC0) != 0x80) {
    466488            throw InvalidUTF8Encoding();
     
    483505std::string RE_Parser::canonicalize(const cursor_t begin, const cursor_t end) {
    484506    std::locale loc;
    485     std::stringstream s;
     507    std::stringstream s;   
    486508    for (auto i = begin; i != end; ++i) {
    487509        switch (*i) {
     
    496518
    497519RE * RE_Parser::parsePropertyExpression() {
    498     const cursor_t start = _cursor;
    499     while (_cursor != _end && *_cursor != '}' and *_cursor != ':' and *_cursor != '=') {
    500         _cursor++;
    501     }
    502     if (_cursor != _end && *_cursor == '=') {
    503         const cursor_t prop_end = _cursor;
    504         _cursor++;
    505         const cursor_t val_start = _cursor;
    506         while (_cursor != _end && *_cursor != '}' and *_cursor != ':') {
    507             _cursor++;
     520    const auto start = mCursor.pos();
     521    while (mCursor.more()) {
     522        bool done = false;
     523        switch (*mCursor) {
     524            case '}': case ':': case '=':
     525                done = true;
     526        }
     527        if (done) {
     528            break;
     529        }
     530        ++mCursor;
     531    }
     532    if (*mCursor == '=') {
     533        const auto prop_end = mCursor.pos();
     534        mCursor++;
     535        const auto val_start = mCursor.pos();
     536        while (mCursor.more()) {
     537            bool done = false;
     538            switch (*mCursor) {
     539                case '}': case ':':
     540                    done = true;
     541            }
     542            if (done) {
     543                break;
     544            }
     545            ++mCursor;
    508546        }
    509547        // We have a property-name = value expression
    510         return createName(canonicalize(start, prop_end), canonicalize(val_start, _cursor));
    511     }
    512     return createName(canonicalize(start, _cursor));
     548        return createName(std::move(canonicalize(start, prop_end)), std::move(canonicalize(val_start, mCursor.pos())));
     549    }
     550    return createName(std::move(canonicalize(start, mCursor.pos())));
    513551}
    514552
     
    522560
    523561    RE * nameRE = parse_RE();
    524 #ifndef NDEBUG
    525     std::cerr << "nameRE:" << std::endl << Printer_RE::PrintRE(nameRE) << std::endl;
    526 #endif
     562
    527563    // Reset outer parsing state.
    528564    fModeFlagSet = outerFlags;
    529565    fNested = outerNested;
    530 
    531566
    532567    // Embed the nameRE in ";.*$nameRE" to skip the codepoint field of Uname.txt
     
    534569    Encoding encoding(Encoding::Type::UTF_8, 8);
    535570    embedded = regular_expression_passes(encoding, embedded);
    536 #ifndef NDEBUG
    537     std::cerr << "embedded:" << std::endl << Printer_RE::PrintRE(embedded) << std::endl;
    538 #endif
     571
    539572    pablo::PabloFunction * nameSearchFunction = re2pablo_compiler(encoding, embedded);
    540573    llvm::Function * nameSearchIR = nullptr;
     
    550583        throw e;
    551584    }
    552 #ifndef NDEBUG
    553     nameSearchIR->dump();
    554 #endif
    555     llvm::ExecutionEngine * engine = JIT_to_ExecutionEngine(nameSearchIR);
    556    
     585
     586    llvm::ExecutionEngine * engine = JIT_to_ExecutionEngine(nameSearchIR);   
    557587    icgrep_Linking(nameSearchIR->getParent(), engine);
    558588   
     
    576606
    577607CharsetOperatorKind RE_Parser::getCharsetOperator() {
    578     throw_incomplete_expression_error_if_end_of_stream();
    579     switch (*_cursor) {
     608    switch (*mCursor) {
    580609        case '&':
    581             ++_cursor;
    582             if (_cursor != _end && *_cursor == '&') {
    583                 ++_cursor;
     610            ++mCursor;
     611            if (mCursor.more() && *mCursor == '&') {
     612                ++mCursor;
    584613                return intersectOp;
    585614            }
    586             else if (_cursor != _end && *_cursor == '[') {
     615            else if (mCursor.more() && *mCursor == '[') {
    587616                // Short-hand for intersectOp when a set follows
    588617                return intersectOp;
     
    590619            else return ampChar;
    591620        case '-':
    592             ++_cursor;
    593             if (_cursor != _end && *_cursor == '-') {
    594                 ++_cursor;
     621            ++mCursor;
     622            if (mCursor.more() && *mCursor == '-') {
     623                ++mCursor;
    595624                return setDiffOp;
    596625            }
    597             else if (_cursor != _end && *_cursor == '[') {
     626            else if (mCursor.more() && *mCursor == '[') {
    598627                return setDiffOp;
    599628            }
    600             else if (_cursor != _end && *_cursor == ']') {
     629            else if (mCursor.more() && *mCursor == ']') {
    601630                return hyphenChar;
    602631            }
    603632            else return rangeHyphen;
    604633        case '[':
    605             ++_cursor;
    606             if (_cursor != _end && *_cursor == ':') {
    607                 ++_cursor;
     634            ++mCursor;
     635            if (mCursor.more() && *mCursor == ':') {
     636                ++mCursor;
    608637                return posixPropertyOpener;
    609638            }
    610639            else return setOpener;
    611640        case ']':
    612             ++_cursor;
     641            ++mCursor;
    613642            return setCloser;
    614643        case '\\':
    615             ++_cursor;
     644            ++mCursor;
    616645            return backSlash;
    617646        default:
     
    639668    // If the first character after the [ is a ^ (caret) then the matching character class is complemented.
    640669    bool negated = false;
    641     if (_cursor != _end && *_cursor == '^') {
     670    if (*mCursor == '^') {
    642671        negated = true;
    643         ++_cursor;
    644     }
    645     throw_incomplete_expression_error_if_end_of_stream();
     672        ++mCursor;
     673    }
    646674    // Legacy rule: an unescaped ] may appear as a literal set character
    647675    // if and only if it appears immediately after the opening [ or [^
    648     if ( *_cursor == ']' && LEGACY_UNESCAPED_RBRAK_RBRACE_ALLOWED) {
     676    if ( *mCursor == ']' && LEGACY_UNESCAPED_RBRAK_RBRACE_ALLOWED) {
    649677        insert(cc, ']');
    650678        lastItemKind = CodepointItem;
    651679        lastCodepointItem = static_cast<codepoint_t> (']');
    652         ++_cursor;
    653     }
    654     else if ( *_cursor == '-' && LEGACY_UNESCAPED_HYPHEN_ALLOWED) {
    655         ++_cursor;
     680        ++mCursor;
     681    } else if ( *mCursor == '-' && LEGACY_UNESCAPED_HYPHEN_ALLOWED) {
     682        ++mCursor;
    656683        insert(cc, '-');
    657684        lastItemKind = CodepointItem;
    658685        lastCodepointItem = static_cast<codepoint_t> ('-');
    659         if (*_cursor == '-') {
     686        if (*mCursor == '-') {
    660687            throw ParseFailure("Set operator has no left operand.");
    661688        }
    662689    }
    663     while (_cursor != _end) {
     690    while (mCursor.more()) {
    664691        const CharsetOperatorKind op = getCharsetOperator();
    665692        switch (op) {
     
    726753                        if (pendingOperationKind == intersectOp) {
    727754                            pendingOperand = makeIntersect(pendingOperand, newOperand);
    728                         }
    729                         else {
     755                        } else {
    730756                            pendingOperand = makeDiff(pendingOperand, newOperand);
    731757                        }
     
    743769                else if (op == posixPropertyOpener) {
    744770                    bool negated = false;
    745                     if (*_cursor == '^') {
     771                    if (*mCursor == '^') {
    746772                        negated = true;
    747                         _cursor++;
     773                        mCursor++;
    748774                    }
    749775                    RE * posixSet = parsePropertyExpression();
    750                     if (negated) posixSet = makeComplement(posixSet);
    751                     subexprs.push_back(posixSet);
     776                    subexprs.push_back(negated ? makeComplement(posixSet) : posixSet);
    752777                    lastItemKind = BrackettedSetItem;
    753                     if (_cursor == _end || *_cursor++ != ':' || _cursor == _end || *_cursor++ != ']')
     778                    if (*mCursor++ != ':' || *mCursor++ != ']')
    754779                        throw ParseFailure("Posix set expression improperly terminated.");
    755780                }
     
    774799                break;
    775800            case backSlash:
    776                 throw_incomplete_expression_error_if_end_of_stream();
    777                 if (isSetEscapeChar(*_cursor)) {
     801                if (isSetEscapeChar(*mCursor)) {
    778802                    subexprs.push_back(parseEscapedSet());
    779803                    lastItemKind = SetItem;
     
    797821
    798822codepoint_t RE_Parser::parse_codepoint() {
    799     if (_cursor != _end && *_cursor == '\\') {
    800         _cursor++;
     823    if (mCursor.more() && *mCursor == '\\') {
     824        mCursor++;
    801825        return parse_escaped_codepoint();
    802826    }
     
    820844codepoint_t RE_Parser::parse_escaped_codepoint() {
    821845    codepoint_t cp_value;
    822     throw_incomplete_expression_error_if_end_of_stream();
    823     switch (*_cursor) {
    824         case 'a': ++_cursor; return 0x07; // BEL
    825         case 'e': ++_cursor; return 0x1B; // ESC
    826         case 'f': ++_cursor; return 0x0C; // FF
    827         case 'n': ++_cursor; return 0x0A; // LF
    828         case 'r': ++_cursor; return 0x0D; // CR
    829         case 't': ++_cursor; return 0x09; // HT
    830         case 'v': ++_cursor; return 0x0B; // VT
     846    switch (*mCursor) {
     847        case 'a': ++mCursor; return 0x07; // BEL
     848        case 'e': ++mCursor; return 0x1B; // ESC
     849        case 'f': ++mCursor; return 0x0C; // FF
     850        case 'n': ++mCursor; return 0x0A; // LF
     851        case 'r': ++mCursor; return 0x0D; // CR
     852        case 't': ++mCursor; return 0x09; // HT
     853        case 'v': ++mCursor; return 0x0B; // VT
    831854        case 'c': // Control-escape based on next char
    832             ++_cursor;
    833             throw_incomplete_expression_error_if_end_of_stream();
     855            ++mCursor;
    834856            // \c@, \cA, ... \c_, or \ca, ..., \cz
    835             if (((*_cursor >= '@') && (*_cursor <= '_')) || ((*_cursor >= 'a') && (*_cursor <= 'z'))) {
    836                 cp_value = static_cast<codepoint_t>(*_cursor & 0x1F);
    837                 _cursor++;
     857            if (((*mCursor >= '@') && (*mCursor <= '_')) || ((*mCursor >= 'a') && (*mCursor <= 'z'))) {
     858                cp_value = static_cast<codepoint_t>(*mCursor & 0x1F);
     859                mCursor++;
    838860                return cp_value;
    839861            }
    840             else if (*_cursor++ == '?') return 0x7F;  // \c? ==> DEL
     862            else if (*mCursor++ == '?') return 0x7F;  // \c? ==> DEL
    841863            else throw("Illegal \\c escape sequence");
    842864        case '0': // Octal escape:  0 - 0377
    843             ++_cursor;
     865            ++mCursor;
    844866            return parse_octal_codepoint(0,3);
    845867        case 'o':
    846             ++_cursor;
    847             throw_incomplete_expression_error_if_end_of_stream();
    848             if (*_cursor == '{') {
    849                 ++_cursor;
     868            ++mCursor;
     869            if (*mCursor == '{') {
     870                ++mCursor;
    850871                cp_value = parse_octal_codepoint(1, 7);
    851                 if (_cursor == _end || *_cursor++ != '}') throw ParseFailure("Malformed octal escape sequence");
     872                if (*mCursor++ != '}') throw ParseFailure("Malformed octal escape sequence");
    852873                return cp_value;
    853874            }
     
    856877            }
    857878        case 'x':
    858             ++_cursor;
    859             throw_incomplete_expression_error_if_end_of_stream();
    860             if (*_cursor == '{') {
    861               ++_cursor;
     879            ++mCursor;
     880            if (*mCursor == '{') {
     881              ++mCursor;
    862882              cp_value = parse_hex_codepoint(1, 6);
    863               if (_cursor == _end || *_cursor++ != '}') throw ParseFailure("Malformed hex escape sequence");
     883              if (*mCursor++ != '}') throw ParseFailure("Malformed hex escape sequence");
    864884              return cp_value;
    865885            }
     
    868888            }
    869889        case 'u':
    870             ++_cursor;
    871             throw_incomplete_expression_error_if_end_of_stream();
    872             if (*_cursor == '{') {
    873                 ++_cursor;
     890            ++mCursor;
     891            if (*mCursor == '{') {
     892                ++mCursor;
    874893                cp_value = parse_hex_codepoint(1, 6);
    875                 if (_cursor == _end || *_cursor++ != '}') throw ParseFailure("Malformed hex escape sequence");
     894                if (*mCursor++ != '}') throw ParseFailure("Malformed hex escape sequence");
    876895                return cp_value;
    877896            }
     
    880899            }
    881900        case 'U':
    882             ++_cursor;
     901            ++mCursor;
    883902            return parse_hex_codepoint(8,8);  // ICU compatibility
    884903        default:
    885904            // Escaped letters should be reserved for special functions.
    886             if (((*_cursor >= 'A') && (*_cursor <= 'Z')) || ((*_cursor >= 'a') && (*_cursor <= 'z')))
     905            if (((*mCursor >= 'A') && (*mCursor <= 'Z')) || ((*mCursor >= 'a') && (*mCursor <= 'z')))
    887906                throw ParseFailure("Undefined or unsupported escape sequence");
    888             else if ((*_cursor < 0x20) || (*_cursor >= 0x7F))
     907            else if ((*mCursor < 0x20) || (*mCursor >= 0x7F))
    889908                throw ParseFailure("Illegal escape sequence");
    890             else return static_cast<codepoint_t>(*_cursor++);
    891     }
    892 }
    893 
     909            else return static_cast<codepoint_t>(*mCursor++);
     910    }
     911}
    894912
    895913codepoint_t RE_Parser::parse_octal_codepoint(int mindigits, int maxdigits) {
    896914    codepoint_t value = 0;
    897915    int count = 0;
    898     while (_cursor != _end && count < maxdigits) {
    899         const char t = *_cursor;
     916    while (mCursor.more() && count < maxdigits) {
     917        const char t = *mCursor;
    900918        if (t < '0' || t > '7') {
    901919            break;
    902920        }
    903921        value = value * 8 | (t - '0');
    904         ++_cursor;
     922        ++mCursor;
    905923        ++count;
    906924    }
     
    913931    codepoint_t value = 0;
    914932    int count = 0;
    915     while (_cursor != _end && isxdigit(*_cursor) && count < maxdigits) {
    916         const char t = *_cursor;
     933    while (mCursor.more() && isxdigit(*mCursor) && count < maxdigits) {
     934        const char t = *mCursor;
    917935        if (isdigit(t)) {
    918936            value = (value * 16) | (t - '0');
     
    921939            value = (value * 16) | ((t | 32) - 'a') + 10;
    922940        }
    923         ++_cursor;
     941        ++mCursor;
    924942        ++count;
    925943    }
     
    927945    if (value > UCD::UNICODE_MAX) throw ParseFailure("Hexadecimal value too large");
    928946    return value;
    929 }
    930 
    931 
    932 inline void RE_Parser::throw_incomplete_expression_error_if_end_of_stream() const {
    933     if (_cursor == _end) throw IncompleteRegularExpression();
    934947}
    935948
     
    965978}
    966979
    967 RE * RE_Parser::makeWordBoundary () {
    968     RE * wordC = makeWordSet();
     980RE * RE_Parser::makeWordBoundary() {
     981    Name * wordC = makeWordSet();
    969982    return makeAlt({makeSeq({makeNegativeLookBehindAssertion(wordC), makeLookAheadAssertion(wordC)}),
    970983                    makeSeq({makeLookBehindAssertion(wordC), makeNegativeLookAheadAssertion(wordC)})});
    971984}
    972985
    973 RE * RE_Parser::makeWordNonBoundary () {
    974     RE * wordC = makeWordSet();
     986RE * RE_Parser::makeWordNonBoundary() {
     987    Name * wordC = makeWordSet();
    975988    return makeAlt({makeSeq({makeNegativeLookBehindAssertion(wordC), makeNegativeLookAheadAssertion(wordC)}),
    976989                    makeSeq({makeLookBehindAssertion(wordC), makeLookAheadAssertion(wordC)})});
    977990}
    978991
    979 inline RE * RE_Parser::makeDigitSet() {
    980     return createName("nd");
    981 }
    982 
    983 inline RE * RE_Parser::makeAlphaNumeric() {
    984     return createName("alnum");
    985 }
    986 
    987 inline RE * RE_Parser::makeWhitespaceSet() {
    988     return createName("whitespace");
    989 }
    990 
    991 inline RE * RE_Parser::makeWordSet() {
    992     return createName("word");
    993 }
    994 
    995 RE * RE_Parser::createName(const std::string value) {
     992inline Name * RE_Parser::makeDigitSet() {
     993    return mMemoizer.memoize(createName("nd"));
     994}
     995
     996inline Name * RE_Parser::makeAlphaNumeric() {
     997    return mMemoizer.memoize(createName("alnum"));
     998}
     999
     1000inline Name * RE_Parser::makeWhitespaceSet() {
     1001    return mMemoizer.memoize(createName("whitespace"));
     1002}
     1003
     1004inline Name * RE_Parser::makeWordSet() {
     1005    return mMemoizer.memoize(createName("word"));
     1006}
     1007
     1008Name * RE_Parser::createName(std::string && value) {
    9961009    auto key = std::make_pair("", value);
    9971010    auto f = mNameMap.find(key);
     
    9991012        return f->second;
    10001013    }
    1001     RE * const property = mMemoizer.memoize(makeName(value, Name::Type::UnicodeProperty));
     1014    Name * const property = mMemoizer.memoize(makeName(value, Name::Type::UnicodeProperty));
    10021015    mNameMap.insert(std::make_pair(std::move(key), property));
    10031016    return property;
    10041017}
    10051018
    1006 RE * RE_Parser::createName(const std::string prop, const std::string value) {
     1019Name * RE_Parser::createName(std::string && prop, std::string && value) {
    10071020    auto key = std::make_pair(prop, value);
    10081021    auto f = mNameMap.find(key);
     
    10101023        return f->second;
    10111024    }
    1012     RE * const property = mMemoizer.memoize(makeName(prop, value, Name::Type::UnicodeProperty));
     1025    Name * const property = mMemoizer.memoize(makeName(prop, value, Name::Type::UnicodeProperty));
    10131026    mNameMap.insert(std::make_pair(std::move(key), property));
    10141027    return property;
  • icGREP/icgrep-devel/icgrep/re/re_parser.h

    r4819 r4829  
    1717#include <map>
    1818#include <re/re_memoizer.hpp>
     19#include <re/parsefailure.h>
    1920
    2021namespace re {
     
    4344private:
    4445
    45     using NameMap = std::map<std::pair<std::string, std::string>, re::RE *>;
     46    using NameMap = std::map<std::pair<std::string, std::string>, re::Name *>;
    4647
    4748    using cursor_t = std::string::const_iterator;
     49
     50    using char_t = const std::string::value_type;
     51
     52    struct Cursor {
     53
     54        inline Cursor & operator++() {
     55            if (LLVM_UNLIKELY(mCursor == mEnd)) {
     56                throw IncompleteRegularExpression();
     57            }
     58            ++mCursor;
     59            return *this;
     60        }
     61
     62        inline Cursor operator++(int) {
     63            if (LLVM_UNLIKELY(mCursor == mEnd)) {
     64                throw IncompleteRegularExpression();
     65            }
     66            Cursor tmp(*this);
     67            ++mCursor;
     68            return tmp;
     69        }
     70
     71        inline const char_t operator*() const {
     72            if (LLVM_UNLIKELY(mCursor == mEnd)) {
     73                throw IncompleteRegularExpression();
     74            }
     75            return *mCursor;
     76        }
     77
     78        inline bool noMore() const {
     79            return mCursor == mEnd;
     80        }
     81
     82        inline bool more() const {
     83            return mCursor != mEnd;
     84        }
     85
     86        inline cursor_t::difference_type remaining() const {
     87            return mEnd - mCursor;
     88        }
     89
     90        inline cursor_t pos() const {
     91            return mCursor;
     92        }
     93
     94        Cursor(const std::string & expression) : mCursor(expression.cbegin()), mEnd(expression.cend()) {}
     95        Cursor(const Cursor & cursor) : mCursor(cursor.mCursor), mEnd(cursor.mEnd) {}
     96        inline Cursor & operator=(const Cursor & cursor) {
     97            mCursor = cursor.mCursor;
     98            mEnd = cursor.mEnd;
     99            return *this;
     100        }
     101    private:
     102        cursor_t    mCursor;
     103        cursor_t    mEnd;
     104    };
    48105
    49106    RE_Parser(const std::string & regular_expression);
     
    63120    RE * extend_item(RE * re);
    64121
    65     void parse_range_bound(int & lo_codepoint, int & hi_codepoint);
     122    RE * parseGraphemeBoundary(RE * re);
     123
     124    std::pair<int, int> parse_range_bound();
    66125
    67126    unsigned parse_int();
     
    80139    RE * makeWordBoundary();
    81140    RE * makeWordNonBoundary();
    82     RE * makeDigitSet();
    83     RE * makeAlphaNumeric();
    84     RE * makeWhitespaceSet();
    85     RE * makeWordSet();
     141    Name * makeDigitSet();
     142    Name * makeAlphaNumeric();
     143    Name * makeWhitespaceSet();
     144    Name * makeWordSet();
    86145
    87     RE * createName(const std::string value);
    88     RE * createName(const std::string prop, const std::string value);
     146    Name * createName(std::string && value);
     147    Name * createName(std::string && prop, std::string && value);
    89148
    90149    CharsetOperatorKind getCharsetOperator();
     
    100159    codepoint_t parse_octal_codepoint(int mindigits, int maxdigits);
    101160
    102     inline void throw_incomplete_expression_error_if_end_of_stream() const;
    103 
    104161    // CC insertion dependent on case-insensitive flag.
    105162    Name * createCC(const codepoint_t cp);
     
    111168private:
    112169
    113     cursor_t                    _cursor;
    114     const cursor_t              _end;
     170    Cursor                      mCursor;
    115171    ModeFlagSet                 fModeFlagSet;
    116172    bool                        fNested;
  • icGREP/icgrep-devel/icgrep/re/re_re.h

    r4526 r4829  
    3434class SymDiff;
    3535class Union;
     36class GraphemeBoundary;
    3637
    3738class RE {
     
    5455        , SymDiff
    5556        , Union
     57        , GraphemeBoundary
    5658    };
    5759    inline ClassTypeId getClassTypeId() const {
Note: See TracChangeset for help on using the changeset viewer.