source: icGREP/icgrep-devel/icgrep/re/re_nullable.cpp @ 5816

Last change on this file since 5816 was 5806, checked in by cameron, 18 months ago

Correction for nullable assertions; clean-up

File size: 5.5 KB
RevLine 
[3917]1#include "re_nullable.h"
[5267]2#include <re/re_alt.h>             // for Alt, makeAlt
3#include <re/re_any.h>             // for makeAny, Any
4#include <re/re_assertion.h>       // for Assertion, Assertion::Sense, Asser...
5#include <re/re_diff.h>            // for Diff, makeDiff
6#include <re/re_intersect.h>       // for Intersect
7#include <re/re_name.h>            // for Name
8#include <re/re_rep.h>             // for Rep, makeRep
9#include <re/re_seq.h>             // for Seq, makeSeq
10#include <vector>                  // for vector, allocator
11#include <llvm/Support/Casting.h>  // for dyn_cast, isa
[4829]12
[3917]13/*
14
15 A regular expression is nullable if it (a) matches the empty
16 string, and (b) applies everywhere.  Note that Start (^) and
17 End ($) match the empty string, but not everywhere).
18
19*/
20
[5267]21using namespace llvm;
22
[4194]23namespace re {
24
[4187]25RE * RE_Nullable::removeNullablePrefix(RE * re) {
[4194]26    if (Seq * seq = dyn_cast<Seq>(re)) {
[4203]27        std::vector<RE*> list;
28        for (auto i = seq->begin(); i != seq->end(); ++i) {
29            if (!isNullable(*i)) {
30                list.push_back(removeNullablePrefix(*i));
31                std::copy(++i, seq->end(), std::back_inserter(list));
32                break;
33            }
34        }
[4249]35        re = makeSeq(list.begin(), list.end());
[4829]36    } else if (Alt * alt = dyn_cast<Alt>(re)) {
[4203]37        std::vector<RE*> list;
[4194]38        for (auto i = alt->begin(); i != alt->end(); ++i) {
[4203]39            list.push_back(removeNullablePrefix(*i));
[3917]40        }
[4203]41        re = makeAlt(list.begin(), list.end());
[4829]42    } else if (Rep * rep = dyn_cast<Rep>(re)) {
[4194]43        if ((rep->getLB() == 0) || (isNullable(rep->getRE()))) {
44            re = makeSeq();
[3917]45        }
[4194]46        else if (hasNullablePrefix(rep->getRE())) {
[4203]47            re = makeSeq({removeNullablePrefix(rep->getRE()), makeRep(rep->getRE(), rep->getLB() - 1, rep->getLB() - 1)});
[3917]48        }
[4182]49        else {
[4203]50            re = makeRep(rep->getRE(), rep->getLB(), rep->getLB());
[3917]51        }
[4829]52    } else if (Name * name = dyn_cast<Name>(re)) {
53        if (name->getDefinition()) {
54            name->setDefinition(removeNullablePrefix(name->getDefinition()));
55        }
[3917]56    }
[4182]57    return re;
[3917]58}
59
[4182]60RE * RE_Nullable::removeNullableSuffix(RE * re) {
[4194]61    if (Seq * seq = dyn_cast<Seq>(re)) {
[4203]62        std::vector<RE*> list;
63        for (auto i = seq->rbegin(); i != seq->rend(); ++i) {
64            if (!isNullable(*i)) {
65                std::copy(seq->begin(), (i + 1).base(), std::back_inserter(list));
66                list.push_back(removeNullableSuffix(*i));
67                break;
68            }
69        }
[4249]70        re = makeSeq(list.begin(), list.end());
[4829]71    } else if (Alt* alt = dyn_cast<Alt>(re)) {
[4203]72        std::vector<RE*> list;
[4194]73        for (auto i = alt->begin(); i != alt->end(); ++i) {
[4203]74            list.push_back(removeNullableSuffix(*i));
[3917]75        }
[4203]76        re = makeAlt(list.begin(), list.end());
[4829]77    } else if (Rep * rep = dyn_cast<Rep>(re)) {
[4194]78        if ((rep->getLB() == 0) || (isNullable(rep->getRE()))) {
79            re = makeSeq();
[3917]80        }
[4194]81        else if (hasNullableSuffix(rep->getRE())) {
[4203]82            re = makeSeq({makeRep(rep->getRE(), rep->getLB() - 1, rep->getLB() - 1), removeNullableSuffix(rep->getRE())});
[3917]83        }
[4182]84        else {
[4203]85            re = makeRep(rep->getRE(), rep->getLB(), rep->getLB());
[3917]86        }
[4829]87    } else if (Name * name = dyn_cast<Name>(re)) {
88        if (name->getDefinition()) {
89            name->setDefinition(removeNullableSuffix(name->getDefinition()));
90        }
[3917]91    }
[4182]92    return re;
[3917]93}
94
[4182]95bool RE_Nullable::isNullable(const RE * re) {
[4194]96    if (const Seq * re_seq = dyn_cast<const Seq>(re)) {
[4203]97        for (const RE * re : *re_seq) {
98            if (!isNullable(re)) {
99                return false;
100            }
101        }
102        return true;
[4829]103    } else if (const Alt * re_alt = dyn_cast<const Alt>(re)) {
[4203]104        for (const RE * re : *re_alt) {
105            if (isNullable(re)) {
106                return true;
107            }
108        }
[4829]109    } else if (const Rep* re_rep = dyn_cast<const Rep>(re)) {
[3917]110        return re_rep->getLB() == 0 ? true : isNullable(re_rep->getRE());
[5147]111    } else if (const Diff * diff = dyn_cast<const Diff>(re)) {
112        return isNullable(diff->getLH()) && !isNullable(diff->getRH());
113    } else if (const Intersect * e = dyn_cast<const Intersect>(re)) {
114        return isNullable(e->getLH()) && isNullable(e->getRH());
115    } 
[4182]116    return false;
[3917]117}
118
[4182]119bool RE_Nullable::hasNullablePrefix(const RE * re) {
120    bool nullable = false;
[4194]121    if (const Seq * seq = dyn_cast<const Seq>(re)) {
[4182]122        nullable = isNullable(seq->front()) ? true : hasNullablePrefix(seq->front());
[4829]123    } else if (const Alt * alt = dyn_cast<const Alt>(re)) {
[4203]124        for (const RE * re : *alt) {
125            if (hasNullablePrefix(re)) {
126                nullable = true;
127                break;
[3917]128            }
129        }
[4829]130    } else if (const Rep * rep = dyn_cast<const Rep>(re)) {
[4203]131        nullable = true;
132        if (rep->getLB() == rep->getUB()) {
133            nullable = hasNullablePrefix(rep->getRE());
134        }
[3917]135    }
[4182]136    return nullable;
[3917]137}
138
[4182]139bool RE_Nullable::hasNullableSuffix(const RE * re) {
140    bool nullable = false;
[4194]141    if (const Seq * seq = dyn_cast<const Seq>(re)) {
[4187]142        nullable = isNullable(seq->back()) ? true : hasNullableSuffix(seq->back());
[4829]143    } else if (const Alt * alt = dyn_cast<const Alt>(re)) {
[4203]144        for (const RE * re : *alt) {
145            if (hasNullableSuffix(re)) {
146                nullable = true;
147                break;
[3917]148            }
149        }
[4829]150    } else if (const Rep * rep = dyn_cast<const Rep>(re)) {
[4203]151        nullable = true;
152        if (rep->getLB() == rep->getUB()) {
153            nullable = hasNullableSuffix(rep->getRE());
154        }
[3917]155    }
[4182]156    return nullable;
[3917]157}
158
[4194]159}
Note: See TracBrowser for help on using the repository browser.