source: icGREP/icgrep-devel/icgrep/re/re_rep.cpp @ 6259

Last change on this file since 6259 was 6259, checked in by cameron, 9 months ago

Small fixes for lookaround optimization

File size: 3.9 KB
Line 
1/*
2 *  Copyright (c) 2017 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_rep.h"
8#include "re_assertion.h"
9#include "re_seq.h"
10#include "re_empty_set.h"
11#include "re_alt.h"
12#include "re_nullable.h"
13#include <llvm/Support/Casting.h>
14#include <llvm/Support/ErrorHandling.h>
15
16using namespace llvm;
17
18namespace re {
19
20inline int ubCombine(const int h1, const int h2) {
21    if ((h1 == Rep::UNBOUNDED_REP) || (h2 == Rep::UNBOUNDED_REP)) {
22        return Rep::UNBOUNDED_REP;
23    }
24    else {
25        return h1 * h2;
26    }
27}
28   
29RE * makeRep(RE * re, int lb, const int ub) {
30    if (LLVM_UNLIKELY(lb == Rep::UNBOUNDED_REP)) {
31        report_fatal_error("repetition lower bound must be finite!");
32    }
33    if (LLVM_UNLIKELY(ub != Rep::UNBOUNDED_REP && ub < lb)) {
34        report_fatal_error("lower bound cannot exceed upper bound");
35    }
36    if (isEmptySet(re)) {
37        // Match failure.
38        return re;
39    }
40    if (isEmptySeq(re)) {
41        // Repeated match of empty string: just match once.
42        return re;
43    }
44    if (isNullable(re)) {
45        if (ub == 1) {
46            return re;
47        }
48        lb = 0;
49    }   
50    if (Rep * rep = dyn_cast<Rep>(re)) {
51        int l = rep->getLB();
52        int u = rep->getUB();
53        if (lb == ub) {
54            return Rep::Create(rep->getRE(), l * lb, ubCombine(u, ub));
55        }
56        else if (u == Rep::UNBOUNDED_REP) {
57            if (l == 0) {
58                /*  R{0,}{lb, ub} = R{0,} */
59                return rep;
60            } else if (l == 1) {
61                /*  R{1,}{lb, ub} = R{lb,} */
62                return Rep::Create(rep->getRE(), lb, Rep::UNBOUNDED_REP);
63            } else if (lb == 0) {
64                /*  R{l,}{0, ub} = R{l,}? */
65                return Rep::Create(rep, 0, 1);
66            } else {
67                /* R{l,}{lb, ub} = R{l * lb,} */
68                return Rep::Create(rep->getRE(), l * lb, Rep::UNBOUNDED_REP);
69            }
70        }
71        else if (u > l) {
72            // Calculate the smallest number of repetitions n such that n * u + 1 >= (n + 1) * l
73            int n = (u - 2)/(u-l);
74            if (lb >= n) {
75                return Rep::Create(rep->getRE(), l * lb, ubCombine(u, ub));
76            }
77            if ((ub == Rep::UNBOUNDED_REP) || (ub >= n)) {
78                RE * r1 = Rep::Create(rep->getRE(), n * l, ubCombine(u, ub));
79                RE * r2 = makeRep(rep, lb, n - 1);  // makeRep recursive simplifies.
80                return makeAlt({r1, r2});
81            }
82        }
83    }
84    else if (isa<Assertion>(re)) {
85        if (lb > 0) return re;
86        else return makeSeq();
87    }
88    else {
89        if (Seq * seq = dyn_cast<Seq>(re)) {
90            if (seq->empty()) {
91                return seq;
92            }
93        }
94        if ((lb == 0) && (ub == 0)) {
95            return makeSeq();
96        }
97        else if ((lb == 1) && (ub == 1)) {
98            return re;
99        }
100    }
101    return Rep::Create(re, lb, ub);
102}
103
104RE * unrollFirst(Rep * rep) {
105    RE * e = rep->getRE();
106    auto lb = rep->getLB();
107    auto ub = rep->getUB();
108    if (ub == 0) return makeAlt();  // Can't unroll - return unmatchable regexp.
109    // Unroll one copy of the loop and simplify.
110    RE * reduced = makeRep(e, lb == 0 ? lb : lb - 1, ub == Rep::UNBOUNDED_REP ? ub : ub - 1);
111    RE * unrolled = makeSeq({e, reduced});
112    if (lb == 0) return makeAlt({makeSeq(), unrolled});
113    else return unrolled;
114}
115RE * unrollLast(Rep * rep) {
116    RE * e = rep->getRE();
117    auto lb = rep->getLB();
118    auto ub = rep->getUB();
119    if (ub == 0) return makeAlt();  // Can't unroll - return unmatchable regexp.
120    // Unroll one copy of the loop and simplify.
121    RE * reduced = makeRep(e, lb == 0 ? lb : lb - 1, ub == Rep::UNBOUNDED_REP ? ub : ub - 1);
122    RE * unrolled = makeSeq({reduced, e});
123    if (lb == 0) return makeAlt({makeSeq(), unrolled});
124    else return unrolled;
125}
126}
Note: See TracBrowser for help on using the repository browser.