Changeset 5869


Ignore:
Timestamp:
Feb 12, 2018, 1:26:29 PM (9 months ago)
Author:
cameron
Message:

excludeNullable transform

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

Legend:

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

    r5806 r5869  
    88#include <re/re_rep.h>             // for Rep, makeRep
    99#include <re/re_seq.h>             // for Seq, makeSeq
     10#include <re/re_group.h>             // for Seq, makeSeq
    1011#include <vector>                  // for vector, allocator
    1112#include <llvm/Support/Casting.h>  // for dyn_cast, isa
     
    2324namespace re {
    2425
     26   
     27RE * RE_Nullable::excludeNullable(RE * re) {
     28    if (!isNullable(re)) return re;
     29    if (Seq * seq = dyn_cast<Seq>(re)) {
     30        // All items in the seq must be nullable.  We must allow
     31        // all possibilities that all but one continue to match empty.
     32        std::vector<RE*> alts;
     33        for (auto i = 0; i < seq->size(); i++) {
     34            std::vector<RE*> list;
     35            for (auto j = 0; j < seq->size(); j++) {
     36                if (i == j) {
     37                    list.push_back(excludeNullable(&seq[j]));
     38                } else {
     39                    list.push_back(&seq[j]);
     40                }
     41            }
     42            alts.push_back(makeSeq(list.begin(), list.end()));
     43        }
     44        return makeAlt(alts.begin(), alts.end());
     45    } else if (Alt * alt = dyn_cast<Alt>(re)) {
     46        std::vector<RE*> list;
     47        for (auto i = alt->begin(); i != alt->end(); ++i) {
     48            list.push_back(excludeNullable(*i));
     49        }
     50        return makeAlt(list.begin(), list.end());
     51    } else if (Rep * rep = dyn_cast<Rep>(re)) {
     52        auto lb = rep->getLB();
     53        auto ub = rep->getUB();
     54        auto e = rep->getRE();
     55        if (!isNullable(e)) {
     56            assert (lb == 0);  // because isNullable(re) is true
     57            return makeRep(e, 1, ub);
     58        }
     59        auto e1 = excludeNullable(e);
     60        if (ub == 1) {
     61            return e1;
     62        } else {
     63            return makeSeq({e1, makeRep(e, lb == 0 ? 0 : lb - 1, ub == Rep::UNBOUNDED_REP ? ub : ub - 1)});
     64        }
     65    } else if (Group * g = dyn_cast<Group>(re)) {
     66        return makeGroup(g->getMode(), excludeNullable(g->getRE()), g->getSense());
     67    } else if (Name * name = dyn_cast<Name>(re)) {
     68        return excludeNullable(name->getDefinition());
     69    }
     70    return re;
     71}
     72
     73   
    2574RE * RE_Nullable::removeNullablePrefix(RE * re) {
     75    if (!hasNullablePrefix(re)) return re;
    2676    if (Seq * seq = dyn_cast<Seq>(re)) {
    2777        std::vector<RE*> list;
     
    3383            }
    3484        }
    35         re = makeSeq(list.begin(), list.end());
     85        return makeSeq(list.begin(), list.end());
    3686    } else if (Alt * alt = dyn_cast<Alt>(re)) {
    3787        std::vector<RE*> list;
     
    3989            list.push_back(removeNullablePrefix(*i));
    4090        }
    41         re = makeAlt(list.begin(), list.end());
     91        return makeAlt(list.begin(), list.end());
    4292    } else if (Rep * rep = dyn_cast<Rep>(re)) {
    43         if ((rep->getLB() == 0) || (isNullable(rep->getRE()))) {
    44             re = makeSeq();
    45         }
    46         else if (hasNullablePrefix(rep->getRE())) {
    47             re = makeSeq({removeNullablePrefix(rep->getRE()), makeRep(rep->getRE(), rep->getLB() - 1, rep->getLB() - 1)});
     93        auto lb = rep->getLB();
     94        auto e = rep->getRE();
     95        if ((lb == 0) || isNullable(e)) {
     96            return makeSeq();
     97        }
     98        else if (hasNullablePrefix(e)) {
     99            return makeSeq({removeNullablePrefix(e), makeRep(e, lb - 1, lb - 1)});
    48100        }
    49101        else {
    50             re = makeRep(rep->getRE(), rep->getLB(), rep->getLB());
     102            return makeRep(e, lb, lb);
    51103        }
    52104    } else if (Name * name = dyn_cast<Name>(re)) {
    53         if (name->getDefinition()) {
    54             name->setDefinition(removeNullablePrefix(name->getDefinition()));
     105        auto def = name->getDefinition();
     106        if (hasNullablePrefix(def)) {
     107            return removeNullablePrefix(def);
    55108        }
    56109    }
     
    68121            }
    69122        }
    70         re = makeSeq(list.begin(), list.end());
     123        return makeSeq(list.begin(), list.end());
    71124    } else if (Alt* alt = dyn_cast<Alt>(re)) {
    72125        std::vector<RE*> list;
     
    74127            list.push_back(removeNullableSuffix(*i));
    75128        }
    76         re = makeAlt(list.begin(), list.end());
     129        return makeAlt(list.begin(), list.end());
    77130    } else if (Rep * rep = dyn_cast<Rep>(re)) {
    78         if ((rep->getLB() == 0) || (isNullable(rep->getRE()))) {
    79             re = makeSeq();
    80         }
    81         else if (hasNullableSuffix(rep->getRE())) {
    82             re = makeSeq({makeRep(rep->getRE(), rep->getLB() - 1, rep->getLB() - 1), removeNullableSuffix(rep->getRE())});
     131        auto lb = rep->getLB();
     132        auto e = rep->getRE();
     133        if ((lb == 0) || isNullable(e)) {
     134            return makeSeq();
     135        }
     136        else if (hasNullableSuffix(e)) {
     137            return makeSeq({makeRep(e, lb - 1, lb - 1), removeNullableSuffix(e)});
    83138        }
    84139        else {
    85             re = makeRep(rep->getRE(), rep->getLB(), rep->getLB());
     140            return makeRep(e, lb, lb);
    86141        }
    87142    } else if (Name * name = dyn_cast<Name>(re)) {
    88         if (name->getDefinition()) {
    89             name->setDefinition(removeNullableSuffix(name->getDefinition()));
     143        auto def = name->getDefinition();
     144        if (hasNullableSuffix(def)) {
     145            return removeNullableSuffix(def);
    90146        }
    91147    }
     
    108164        }
    109165    } else if (const Rep* re_rep = dyn_cast<const Rep>(re)) {
    110         return re_rep->getLB() == 0 ? true : isNullable(re_rep->getRE());
     166        return (re_rep->getLB() == 0) || isNullable(re_rep->getRE());
    111167    } else if (const Diff * diff = dyn_cast<const Diff>(re)) {
    112168        return isNullable(diff->getLH()) && !isNullable(diff->getRH());
    113169    } else if (const Intersect * e = dyn_cast<const Intersect>(re)) {
    114170        return isNullable(e->getLH()) && isNullable(e->getRH());
    115     }
     171    } else if (const Group * g = dyn_cast<const Group>(re)) {
     172        return isNullable(g->getRE());
     173    }
    116174    return false;
    117175}
    118176
    119177bool RE_Nullable::hasNullablePrefix(const RE * re) {
    120     bool nullable = false;
    121178    if (const Seq * seq = dyn_cast<const Seq>(re)) {
    122         nullable = isNullable(seq->front()) ? true : hasNullablePrefix(seq->front());
     179        if (seq->empty()) return false;
     180        return isNullable(seq->front()) || hasNullablePrefix(seq->front());
    123181    } else if (const Alt * alt = dyn_cast<const Alt>(re)) {
    124         for (const RE * re : *alt) {
    125             if (hasNullablePrefix(re)) {
    126                 nullable = true;
    127                 break;
    128             }
    129         }
     182        for (const RE * a : *alt) {
     183            if (hasNullablePrefix(a)) {
     184                return true;
     185            }
     186        }
     187        return false;
    130188    } else if (const Rep * rep = dyn_cast<const Rep>(re)) {
    131         nullable = true;
    132         if (rep->getLB() == rep->getUB()) {
    133             nullable = hasNullablePrefix(rep->getRE());
    134         }
    135     }
    136     return nullable;
     189        return (rep->getLB() != rep->getUB()) || hasNullablePrefix(rep->getRE());
     190    } else if (const Group * g = dyn_cast<const Group>(re)) {
     191        return hasNullablePrefix(g->getRE());
     192    }
     193    return false;
    137194}
    138195
    139196bool RE_Nullable::hasNullableSuffix(const RE * re) {
    140     bool nullable = false;
    141197    if (const Seq * seq = dyn_cast<const Seq>(re)) {
    142         nullable = isNullable(seq->back()) ? true : hasNullableSuffix(seq->back());
     198        if (seq->empty()) return false;
     199        return isNullable(seq->back()) || hasNullableSuffix(seq->back());
    143200    } else if (const Alt * alt = dyn_cast<const Alt>(re)) {
    144         for (const RE * re : *alt) {
    145             if (hasNullableSuffix(re)) {
    146                 nullable = true;
    147                 break;
    148             }
    149         }
     201        for (const RE * a : *alt) {
     202            if (hasNullableSuffix(a)) {
     203                return true;
     204            }
     205        }
     206        return false;
    150207    } else if (const Rep * rep = dyn_cast<const Rep>(re)) {
    151         nullable = true;
    152         if (rep->getLB() == rep->getUB()) {
    153             nullable = hasNullableSuffix(rep->getRE());
    154         }
    155     }
    156     return nullable;
    157 }
    158 
    159 }
     208        return (rep->getLB() != rep->getUB()) || hasNullableSuffix(rep->getRE());
     209    } else if (const Group * g = dyn_cast<const Group>(re)) {
     210        return hasNullableSuffix(g->getRE());
     211    }
     212    return false;
     213}
     214
     215}
  • icGREP/icgrep-devel/icgrep/re/re_nullable.h

    r5812 r5869  
    99class RE_Nullable {
    1010public:
     11    static RE * excludeNullable(RE * re);
    1112    static RE * removeNullablePrefix(RE * re);
    1213    static RE * removeNullableSuffix(RE * re);
Note: See TracChangeset for help on using the changeset viewer.