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

Last change on this file was 5646, checked in by nmedfort, 13 hours ago

Minor clean up. Bug fix for object cache when the same cached kernel is used twice in a single run. Improvement to RE Minimizer.

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