source: icGREP/icgrep-devel/icgrep/re/re_alt.h @ 5811

Last change on this file since 5811 was 5811, checked in by cameron, 15 months ago

RE optimizations

File size: 3.3 KB
Line 
1/*
2 *  Copyright (c) 2014 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#ifndef ALT_H
8#define ALT_H
9
10#include "re_re.h"
11#include <re/re_cc.h>
12#include <re/re_seq.h>
13#include <re/re_rep.h>
14#include <re/printer_re.h>
15#include <llvm/Support/Casting.h>
16
17namespace re {
18
19class Alt : public Vector {
20public:
21    static inline bool classof(const RE * re) {
22        return re->getClassTypeId() == ClassTypeId::Alt;
23    }
24    static inline bool classof(const void *) {
25        return false;
26    }
27protected:
28    friend Alt * makeAlt();
29    template<typename iterator> friend RE * makeAlt(iterator, iterator);
30    Alt()
31    : Vector(ClassTypeId::Alt) {
32
33    }
34    Alt(iterator begin, iterator end)
35    : Vector(ClassTypeId::Alt, begin, end) {
36
37    }
38};
39
40/**
41 * @brief makeAlt
42 *
43 * Build an Alt, flattening alternative subgroups, and combining character classes and
44 * move character classes towards the end of the list to ensure that all combinations are found.
45 *
46 * @param list
47 * @return simplified RE representing the Alt
48 */
49
50inline Alt * makeAlt() {
51    return new Alt();
52}
53   
54inline void add_CC(std::vector<CC *> & CCs_found, CC * cc) {
55    for (unsigned j = 0; j < CCs_found.size(); j++) {
56        if (CCs_found[j]->getAlphabet() == cc->getAlphabet()) {
57            CCs_found[j] = makeCC(CCs_found[j], cc);
58            return;
59        }
60    }
61    CCs_found.push_back(cc);
62}
63
64template<typename iterator>
65RE * makeAlt(iterator begin, iterator end) {
66    Alt * newAlt = makeAlt();
67    bool nullableAltFound = false;
68    std::vector<CC *> CCs_found;  // CCs with possibly different alphabets
69    for (auto i = begin; i != end; ++i) {
70        if (CC * cc = llvm::dyn_cast<CC>(*i)) {
71            add_CC(CCs_found, cc);
72        } else if (const Alt * alt = llvm::dyn_cast<Alt>(*i)) {
73            // We have an Alt to embed within the alt.  We extract the individual
74            // elements to include within the new alt.   Note that recursive flattening
75            // is not required, if the elements themselves were created with makeAlt.
76            for (RE * a : *alt) {
77                if (CC * cc = llvm::dyn_cast<CC>(a)) {
78                    add_CC(CCs_found, cc);
79                } else if (isEmptySeq(a)) {
80                    nullableAltFound = true;
81                } else {
82                    newAlt->push_back(a);
83                }
84            }
85        } else if (const Rep * rep = llvm::dyn_cast<Rep>(*i)) {
86            if (rep->getLB() == 0) {
87                nullableAltFound = true;
88                newAlt->push_back(makeRep(rep->getRE(), 1, rep->getUB()));
89            } else {
90                newAlt->push_back(*i);
91            }
92        } else if (isEmptySeq(*i)) {
93            nullableAltFound = true;
94        } else {
95            newAlt->push_back(*i);
96        }
97    }
98    for (CC * cc : CCs_found) {
99        newAlt->push_back(cc);
100    }
101    if (nullableAltFound) newAlt->push_back(makeSeq());
102    if (newAlt->size() == 1) return newAlt->front();
103    return newAlt;
104}
105
106inline RE * makeAlt(RE::InitializerList list) {
107    return makeAlt(list.begin(), list.end());
108}
109
110// An Alt with no members represent the empty set.
111inline bool isEmptySet(RE * r) {
112    return llvm::isa<Alt>(r) && llvm::cast<Alt>(r)->empty();
113}
114}
115
116#endif // ALT_H
117
Note: See TracBrowser for help on using the repository browser.