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

Last change on this file since 5509 was 5509, checked in by cameron, 2 years ago

Bounded repetition optimizations and bug fix; test case

File size: 2.3 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_alt.h"
11#include "re_nullable.h"
12#include <llvm/Support/Casting.h>
13
14using namespace llvm;
15
16namespace re {
17
18inline int ubCombine(const int h1, const int h2) {
19    if ((h1 == Rep::UNBOUNDED_REP) || (h2 == Rep::UNBOUNDED_REP)) {
20        return Rep::UNBOUNDED_REP;
21    }
22    else {
23        return h1 * h2;
24    }
25}
26   
27RE * makeRep(RE * re, int lb, const int ub) {
28    if (RE_Nullable::isNullable(re)) {
29        if (ub == 1) {
30            return re;
31        }
32        lb = 0;
33    }
34    if (Rep * rep = dyn_cast<Rep>(re)) {
35        int l = rep->getLB();
36        int u = rep->getUB();
37        if (u == Rep::UNBOUNDED_REP) {
38            if (l == 0) {
39                /*  R{0,}{lb, ub} = R{0,} */
40                return rep;
41            } else if (l == 1) {
42                /*  R{1,}{lb, ub} = R{lb,} */
43                return new Rep(rep->getRE(), lb, Rep::UNBOUNDED_REP);
44            } else if (lb == 0) {
45                /*  R{l,}{0, ub} = R{l,}? */
46                return new Rep(rep, 0, 1);
47            } else {
48                /* R{l,}{lb, ub} = R{l * lb,} */
49                return new Rep(rep->getRE(), l * lb, Rep::UNBOUNDED_REP);
50            }
51        }
52        else if (u > l) {
53            // Calculate the smallest number of repetitions n such that n * u + 1 >= (n + 1) * l
54            int n = (u - 2)/(u-l);
55            if (lb >= n) {
56                return new Rep(rep->getRE(), l * lb, ubCombine(u, ub));
57            }
58            if ((ub == Rep::UNBOUNDED_REP) || (ub >= n)) {
59                RE * r1 = new Rep(rep->getRE(), n * l, ubCombine(u, ub));
60                RE * r2 = new Rep(rep, lb, n - 1);
61                return makeAlt({r1, r2});
62            }
63        }
64    }
65    else if (isa<Assertion>(re)) {
66        if (lb > 0) return re;
67        else return makeSeq();
68    }
69    else {
70        if (Seq * seq = dyn_cast<Seq>(re)) {
71            if (seq->empty()) {
72                return seq;
73            }
74        }
75        if ((lb == 0) && (ub == 0)) {
76            return makeSeq();
77        }
78        else if ((lb == 1) && (ub == 1)) {
79            return re;
80        }
81    }
82    return new Rep(re, lb, ub);
83}
84
85}
Note: See TracBrowser for help on using the repository browser.