source: icGREP/icgrep-devel/icgrep/re/re_contextual_simplification.cpp @ 6224

Last change on this file since 6224 was 6224, checked in by cameron, 5 months ago

Contextual assertion simplifier from Jeremy Schwartz - initial check-in

File size: 11.1 KB
Line 
1/*
2 *  Copyright (c) 2018 International Characters.
3 *  This software is licensed to the public under the Open Software License 3.0.
4 *  icgrep is a trademark of International Characters.
5 */
6
7#include "re_contextual_simplification.h"
8#include <re/re_any.h>
9#include <re/re_cc.h>
10#include <re/re_diff.h>
11#include <re/re_name.h>
12#include <re/re_seq.h>
13#include <re/re_assertion.h>
14#include <re/validation.h>
15#include <llvm/Support/Casting.h>
16#include <llvm/Support/ErrorHandling.h>
17
18namespace re {
19
20class Context : private RE_Transformer {
21public:
22    Context(Seq * s, size_t idx);
23    bool good() const noexcept;
24    RE * simplify(RE * re);
25private:
26    std::vector<RE *> before;
27    std::vector<RE *> after;
28
29    Name * any;
30
31    bool _good = true;
32
33    template<typename Iterator>
34    std::vector<RE *> makeContext(Iterator begin, Iterator end);
35    RE * transformAssertion(Assertion * a) override;
36    RE * simplifyAsserted(RE * asserted, std::vector<RE *> const & context);
37    RE * simplifyForwardAssertion(RE * asserted);
38    RE * simplifyBackwardAssertion(RE * asserted);
39};
40
41
42class ResolvesToCC : public RE_Validator {
43public:
44    inline bool validateCC(CC *) override { return true; }
45    inline bool validateStart(Start *) override { return false; }
46    inline bool validateEnd(End *) override { return false; }
47    inline bool validateSeq(Seq * s) override { return (s) && s->size() <= 1; }
48    inline bool validateIntersect(Intersect *) override { return false; }
49    inline bool validateRange(Range *) override { return false; }
50    inline bool validateAssertion(Assertion *) override { return false; }
51};
52
53class ValidateAsserted : public RE_Validator {
54public:
55    inline bool validateStart(Start * s) override { return false; }
56    inline bool validateEnd(End * e) override { return false; }
57    inline bool validateRep(Rep * r) override { return false; }
58    inline bool validateIntersect(Intersect * i) override { return false; }
59    inline bool validateRange(Range * r) override { return false; }
60    inline bool validateAssertion(Assertion * a) override { return false; }
61    inline bool validateDiff(Diff * d) override {
62        return ResolvesToCC{}.validateRE(d);
63    }
64    inline bool validateSeq(Seq * s) {
65        auto ccValidator = ResolvesToCC{};
66        for (auto e : *s) {
67            if (!ccValidator.validateRE(e) || !validateRE(e)) {
68                return false;
69            }
70        }
71        return true;
72    }
73};
74
75class ValidateZeroWidth : public RE_Validator {
76public:
77    inline bool validateStart(Start * s) { return false; }
78    inline bool validateEnd(End * e) { return false; }
79    inline bool validateCC(CC * cc) { return false; }
80    inline bool validateRep(Rep * rep) { return false; }
81    inline bool validateIntersect(Intersect * e) { return false; }
82    inline bool validateRange(Range * rg) { return false; }
83    inline bool validateAssertion(Assertion * a) { return true; }
84
85    inline bool validateSeq(Seq * s) { 
86        for (auto e : *s) {
87            if (!validateRE(e)) return false;
88        }
89        return s->size() == 0;
90    }
91};
92
93class AssertionPrep : public RE_Transformer {
94public:
95    using Sense = Assertion::Sense;
96    AssertionPrep(Assertion * assertion);
97    RE * transformCC(CC * cc) override;
98    RE * transformDiff(Diff * d) override;
99private:
100    Sense sense;
101    Name * any;
102};
103
104
105
106Context::Context(Seq * s, size_t idx) 
107: RE_Transformer("Contextual Engine", NameTransformationMode::TransformDefinition)
108{
109    if (idx < s->size()) {
110        this->before = makeContext(s->rbegin() + (s->size() - idx), s->rend());
111        this->after = makeContext(s->begin() + idx + 1, s->end());
112        if (before.size() == 0 && after.size() == 0) {
113            _good = false;
114        }
115    } else {
116        this->_good = false;
117    }
118
119    this->any = llvm::cast<Name>(makeAny());
120}
121
122bool Context::good() const noexcept {
123    return this->_good;
124}
125
126RE * Context::simplify(RE * re) {
127    RE * rt = transformRE(re);
128    return rt;
129}
130
131template<typename Iterator>
132std::vector<RE *> Context::makeContext(Iterator begin, Iterator end) {
133    std::vector<RE *> rt{};
134    for (auto i = begin; i != end; i++) {
135        if (llvm::isa<CC>(*i)) {
136            rt.push_back(*i);
137        } else if (llvm::isa<Diff>(*i)) {
138            Diff * d = llvm::cast<Diff>(*i);
139            if (llvm::isa<CC>(d->getLH()) && llvm::isa<CC>(d->getRH())) {
140                rt.push_back(subtractCC(llvm::cast<CC>(d->getLH()), llvm::cast<CC>(d->getRH())));
141            } else {
142                break;
143            }
144        } else if (ValidateZeroWidth().validateRE(*i)) {
145            continue;
146        } else if (llvm::isa<Name>(*i)) {
147            if (llvm::isa<CC>(llvm::cast<Name>(*i)->getDefinition())) {
148                rt.push_back(llvm::cast<Name>(*i)->getDefinition());
149            } else {
150                break;
151            }
152        } else {
153            break;
154        }
155    }
156    return rt;
157}
158
159RE * reverseAsserted(RE * re) {
160    if (llvm::isa<Seq>(re)) {
161        Seq * seq = llvm::cast<Seq>(re);
162        return makeSeq(seq->rbegin(), seq->rend());
163    } else {
164        return re;
165    }
166}
167
168RE * Context::transformAssertion(Assertion * a) {
169    using Kind = Assertion::Kind;
170    if (good() && ValidateAsserted{}.validateRE(a->getAsserted())) {
171        AssertionPrep prep{a};
172        RE * asserted = prep.transformRE(a->getAsserted());
173        RE * simplifiedAsserted = nullptr;
174        if (a->getKind() == Kind::Lookahead) {
175            simplifiedAsserted = simplifyAsserted(asserted, after);
176        } else if (a->getKind() == Kind::Lookbehind) {
177            asserted = reverseAsserted(asserted);
178            simplifiedAsserted = reverseAsserted(simplifyAsserted(asserted, before));
179        } else {
180            return a;
181        }
182
183        if (simplifiedAsserted != nullptr) {
184            if (simplifiedAsserted == asserted) {
185                return a;
186            } else if (isEmptySet(simplifiedAsserted)) {
187                return makeAlt();
188            } else if (isEmptySeq(simplifiedAsserted)) {
189                return makeSeq();
190            } else {
191                return makeAssertion(simplifiedAsserted, a->getKind(), Assertion::Sense::Positive);
192            }
193        } else {
194            return a;
195        }
196    } else {
197        return a;
198    }
199}
200
201Seq * latterSeq(Seq * s, size_t i) {
202    Seq * seq = llvm::cast<Seq>(makeSeq());
203    for (auto it = s->begin() + i; it != s->end(); it++) {
204        seq->push_back(*it);
205    }
206    return s;
207}
208
209RE * Context::simplifyAsserted(RE * asserted, std::vector<RE *> const & context) {
210    if (LLVM_LIKELY(llvm::isa<CC>(asserted))) {
211        if (context.size() > 0) {
212            CC * assertedCC = llvm::cast<CC>(asserted);
213            CC * contextCC = llvm::cast<CC>(context[0]);
214            CC * intersect = intersectCC(assertedCC, contextCC);
215            if (intersect->empty()) {
216                return makeAlt();
217            } else if (subtractCC(contextCC, assertedCC)->empty()) {
218                return makeSeq();
219            } else if (*intersectCC(contextCC, assertedCC) == *assertedCC) {
220                return asserted;
221            } else {
222                return intersect;
223            }
224        }
225        return asserted;
226    } else if (llvm::isa<Seq>(asserted)) {
227        Seq * a = llvm::cast<Seq>(asserted);
228        std::vector<RE *> elems{a->begin(), a->end()};
229        bool isWholeSeqSuperSet = context.size() >= a->size();
230        bool didChange = false;
231        elems.reserve(a->size());
232
233        for (size_t i = 0; i < std::min(a->size(), context.size()); ++i) {
234            RE * simplifiedElem = simplifyAsserted((*a)[i], std::vector<RE *>{context[i]});
235            if (isEmptySet(simplifiedElem)) {
236                return makeAlt();
237            }
238            if (simplifiedElem != (*a)[i]) {
239                didChange = true;
240                if (!isEmptySeq(simplifiedElem)) {
241                    isWholeSeqSuperSet = false;
242                    elems[i] = simplifiedElem;
243                } else {
244                    // a[i] is supperset of context[i]. Can't change a[i] to
245                    // Seq[] as it will invalidate the Seq structure. Instead,
246                    // set a[i] to context[i] the smaller of the two CCs.
247                    elems[i] = context[i];
248                }
249            } else {
250                isWholeSeqSuperSet = false;
251            }
252        }
253
254        if (isWholeSeqSuperSet) {
255            return makeSeq();
256        }
257
258        if (didChange) {
259            return makeSeq(elems.begin(), elems.end());
260        } else {
261            return asserted;
262        }
263    } else if (llvm::isa<Alt>(asserted)) {
264        Alt * a = llvm::cast<Alt>(asserted);
265        std::vector<RE *> elems{};
266        elems.reserve(a->size());
267        bool did_change = false;
268        for (auto e : *a) {
269            RE * e0 = simplifyAsserted(e, context);
270            if (e0 != e) {
271                elems.push_back(e0);
272                did_change = true;
273            } else {
274                elems.push_back(e);
275            }
276        }
277
278        if (did_change) {
279            return makeAlt(elems.begin(), elems.end());
280        } else {
281            return asserted;
282        }
283    } else if (llvm::isa<Name>(asserted)) {
284        RE * def = llvm::cast<Name>(asserted)->getDefinition();
285        if (LLVM_UNLIKELY(def == nullptr)) {
286            llvm_unreachable("undefined name");
287        }
288        RE * simp = simplifyAsserted(def, context);
289        if (simp == def) {
290            return asserted;
291        } else {
292            return simp;
293        }
294    } else {
295        llvm_unreachable("Context::simplifyAsserted: Unexpected asserted value");
296    }
297}
298
299
300
301AssertionPrep::AssertionPrep(Assertion * assertion)
302: RE_Transformer("", NameTransformationMode::TransformDefinition), 
303  sense(assertion->getSense())
304{
305    this->any = llvm::cast<Name>(makeAny());
306}
307
308RE * AssertionPrep::transformCC(CC * cc) {
309    if (sense == Sense::Negative) {
310        return subtractCC(llvm::dyn_cast<CC>(any->getDefinition()), cc);
311    } else {
312        return cc;
313    }
314}
315
316RE * AssertionPrep::transformDiff(Diff * d) {
317    CC * lh = llvm::dyn_cast<CC>(transform(d->getLH()));
318    CC * rh = llvm::dyn_cast<CC>(transform(d->getRH()));
319    if (LLVM_UNLIKELY(lh == nullptr || rh == nullptr)) {
320        llvm_unreachable("Nonvalidated use of Diff");
321    }
322    return transform(subtractCC(lh, rh));
323}
324
325
326RE * RE_ContextSimplifier::transformSeq(Seq * s) {
327    std::vector<RE *> seq{};
328    seq.reserve(s->size());
329    bool hasChanged = false;
330    for (size_t i = 0; i < s->size(); ++i) {
331        if (!validateAssertionFree((*s)[i])) {
332            Context context{s, i};
333            if (!context.good()) {  // abort simplification is context is bad
334                seq.push_back((*s)[i]);
335                continue;
336            }
337            RE * simp = context.simplify((*s)[i]);
338            if (simp != (*s)[i]) {
339                hasChanged = true;
340                if (isEmptySet(simp)) {
341                    return makeAlt();
342                } else {
343                    seq.push_back(simp);
344                }
345            } else {
346                seq.push_back((*s)[i]);
347            }
348        } else {
349            seq.push_back((*s)[i]);
350        }
351    }
352
353   
354    if (hasChanged) {
355        auto rt = makeSeq(seq.begin(), seq.end());
356        return rt;
357    } else {
358        return s;
359    }
360}
361
362} // namespace re
Note: See TracBrowser for help on using the repository browser.