source: icGREP/icgrep-devel/icgrep/re/re_analysis.cpp @ 5418

Last change on this file since 5418 was 5267, checked in by nmedfort, 3 years ago

Code clean-up. Removed Pablo Call, SetIthBit? and Prototype.

File size: 7.2 KB
RevLine 
[4393]1#include "re_analysis.h"
[4835]2#include <re/re_cc.h>
3#include <re/re_name.h>
4#include <re/re_start.h>
5#include <re/re_end.h>
6#include <re/re_any.h>
7#include <re/re_seq.h>
8#include <re/re_alt.h>
9#include <re/re_rep.h>
10#include <re/re_diff.h>
11#include <re/re_intersect.h>
12#include <re/re_assertion.h>
[4829]13#include <iostream>
14#include <re/printer_re.h>
[4442]15#include <limits.h>
[4393]16
[5267]17using namespace llvm;
18
[4393]19namespace re {
20
[4829]21bool isByteLength(const RE * re) {
22    if (const Alt * alt = dyn_cast<Alt>(re)) {
23        for (const RE * re : *alt) {
[4415]24            if (!isByteLength(re)) {
25                return false;
26            }
[4393]27        }
28        return true;
[4835]29    } else if (const Seq * seq = dyn_cast<Seq>(re)) {
[4393]30        return (seq->size() == 1) && isByteLength(&seq[0]);
[4835]31    } else if (const Rep * rep = dyn_cast<Rep>(re)) {
[4393]32        return (rep->getLB() == 1) && (rep->getUB() == 1) && isByteLength(rep->getRE());
[4835]33    } else if (const Diff * diff = dyn_cast<Diff>(re)) {
[4393]34        return isByteLength(diff->getLH()) && isByteLength(diff->getRH());
[4835]35    } else if (const Intersect * e = dyn_cast<Intersect>(re)) {
[4393]36        return isByteLength(e->getLH()) && isByteLength(e->getRH());
[4835]37    } else if (const Name * n = dyn_cast<Name>(re)) {
[5080]38        if (n->getType() == Name::Type::Byte) {
39            return true;
[5267]40        } else if (n->getType() == Name::Type::Capture || n->getType() == Name::Type::Reference) {
[5080]41            return isByteLength(n->getDefinition());
42        }
43        return false;
[4393]44    }
45    return false; // otherwise
46}
47
[4829]48bool isUnicodeUnitLength(const RE * re) {
49    if (const Alt * alt = dyn_cast<Alt>(re)) {
50        for (const RE * re : *alt) {
[4415]51            if (!isUnicodeUnitLength(re)) {
52                return false;
53            }
[4393]54        }
55        return true;
[4835]56    } else if (const Seq * seq = dyn_cast<Seq>(re)) {
[4393]57        return (seq->size() == 1) && isUnicodeUnitLength(&seq[0]);
[4835]58    } else if (const Rep * rep = dyn_cast<Rep>(re)) {
[4393]59        return (rep->getLB() == 1) && (rep->getUB() == 1) && isUnicodeUnitLength(rep->getRE());
[4835]60    } else if (isa<Assertion>(re)) {
[4405]61        return false;
[4835]62    } else if (const Diff * diff = dyn_cast<Diff>(re)) {
[4393]63        return isUnicodeUnitLength(diff->getLH()) && isUnicodeUnitLength(diff->getRH());
[4835]64    } else if (const Intersect * e = dyn_cast<Intersect>(re)) {
[4393]65        return isUnicodeUnitLength(e->getLH()) && isUnicodeUnitLength(e->getRH());
[4835]66    } else if (isa<Any>(re)) {
[4415]67        return true;
[4835]68    } else if (const Name * n = dyn_cast<Name>(re)) {
[4393]69        // Eventually names might be set up for not unit length items.
[5080]70        if (n->getType() == Name::Type::Unicode || n->getType() == Name::Type::UnicodeProperty || n->getType() == Name::Type::Byte) {
71            return true;
[5267]72        } else if (n->getType() == Name::Type::Capture || n->getType() == Name::Type::Reference) {
[5080]73            return isUnicodeUnitLength(n->getDefinition());
74        }
75        return false;
[4393]76    }
77    return false; // otherwise
78}
[4829]79
80std::pair<int, int> getUnicodeUnitLengthRange(const RE * re) {
81    if (const Alt * alt = dyn_cast<Alt>(re)) {
[5267]82        std::pair<int, int> range = std::make_pair(INT_MAX, 0);
[4829]83        for (const RE * re : *alt) {
84            auto r = getUnicodeUnitLengthRange(re);
85            range.first = std::min<int>(range.first, r.first);
86            range.second = std::max<int>(range.second, r.second);
87        }
88        return range;
89    } else if (const Seq * seq = dyn_cast<Seq>(re)) {
90        std::pair<int, int> range = std::make_pair(0, 0);
91        for (const RE * re : *seq) {
92            auto tmp = getUnicodeUnitLengthRange(re);
[5267]93            if (LLVM_LIKELY(tmp.first < (INT_MAX - range.first))) {
[4829]94                range.first += tmp.first;
95            } else {
[5267]96                range.first = INT_MAX;
[4829]97            }
[5267]98            if (LLVM_LIKELY(tmp.second < (INT_MAX - range.second))) {
[4829]99                range.second += tmp.second;
100            } else {
[5267]101                range.second = INT_MAX;
[4829]102            }
103        }
104        return range;
105    } else if (const Rep * rep = dyn_cast<Rep>(re)) {
106        auto range = getUnicodeUnitLengthRange(rep->getRE());
[5267]107        if (LLVM_LIKELY(rep->getLB() != Rep::UNBOUNDED_REP && range.first < INT_MAX)) {
[4829]108            range.first *= rep->getLB();
109        } else {
[5267]110            range.first = INT_MAX;
[4829]111        }
[5267]112        if (LLVM_LIKELY(rep->getUB() != Rep::UNBOUNDED_REP && range.second < INT_MAX)) {
[4829]113            range.second *= rep->getUB();
114        } else {
[5267]115            range.second = INT_MAX;
[4829]116        }
117        return range;
118    } else if (isa<Assertion>(re) || isa<Start>(re) || isa<End>(re)) {
119        return std::make_pair(0, 0);
120    } else if (const Diff * diff = dyn_cast<Diff>(re)) {
121        const auto r1 = getUnicodeUnitLengthRange(diff->getLH());
122        const auto r2 = getUnicodeUnitLengthRange(diff->getRH());
123        return std::make_pair(std::min(r1.first, r2.first), std::max(r1.second, r2.second));
124    } else if (const Intersect * i = dyn_cast<Intersect>(re)) {
125        const auto r1 = getUnicodeUnitLengthRange(i->getLH());
126        const auto r2 = getUnicodeUnitLengthRange(i->getRH());
127        return std::make_pair(std::min(r1.first, r2.first), std::max(r1.second, r2.second));
128    } else if (const Name * n = dyn_cast<Name>(re)) {
129        // Eventually names might be set up for not unit length items.
130        switch (n->getType()) {
131            case Name::Type::Byte:
132            case Name::Type::Unicode:
133            case Name::Type::UnicodeProperty:
134                return std::make_pair(1, 1);
[5080]135            case Name::Type::Capture:
136            case Name::Type::Reference:
137                return getUnicodeUnitLengthRange(n->getDefinition());
[5091]138            case Name::Type::ZeroWidth:
139                return std::make_pair(0, 0);
[4829]140            case Name::Type::Unknown:
[5267]141                return std::make_pair(0, INT_MAX);
[4829]142        }
[5091]143    } 
[4829]144    return std::make_pair(1, 1);
145}
[4442]146   
147int minMatchLength(RE * re) {
148    if (Alt * alt = dyn_cast<Alt>(re)) {
149        int minAltLength = INT_MAX;
150        for (RE * re : *alt) {
151            minAltLength = std::min(minAltLength, minMatchLength(re));
152        }
153        return minAltLength;
[5267]154    } else if (Seq * seq = dyn_cast<Seq>(re)) {
[4442]155        int minSeqLength = 0;
156        for (RE * re : *seq) {
157            minSeqLength += minMatchLength(re);
158        }
159        return minSeqLength;
[5267]160    } else if (Rep * rep = dyn_cast<Rep>(re)) {
[4442]161        if (rep->getLB() == 0) return 0;
162        else return (rep->getLB()) * minMatchLength(rep->getRE());
[5267]163    } else if (isa<Assertion>(re)) {
[4442]164        return 0;
[5267]165    } else if (Diff * diff = dyn_cast<Diff>(re)) {
[4442]166        return minMatchLength(diff->getLH());
[5267]167    } else if (Intersect * e = dyn_cast<Intersect>(re)) {
[4442]168        return std::min(minMatchLength(e->getLH()), minMatchLength(e->getRH()));
[5267]169    } else if (isa<Any>(re)) {
[4442]170        return 1;
[5233]171    } else if (const Name * n = dyn_cast<Name>(re)) {
172        // Eventually names might be set up for not unit length items.
[5080]173        switch (n->getType()) {
174            case Name::Type::Byte:
175            case Name::Type::Unicode:
176            case Name::Type::UnicodeProperty:
177                return 1;
178            case Name::Type::Capture:
179            case Name::Type::Reference:
180                return minMatchLength(n->getDefinition());
[5233]181            default:
[5080]182                return 0;
183        }
[4442]184    }
185    return 0; // otherwise
[4393]186}
[4442]187
188
189}
Note: See TracBrowser for help on using the repository browser.