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

Last change on this file since 6297 was 6223, checked in by cameron, 6 months ago

Contextual assertion simplifier from Jeremy Schwartz - initial check-in

File size: 3.8 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 <util/slab_allocator.h>
12#include <vector>
13#include <re/re_cc.h>
14#include <re/re_seq.h>
15#include <re/re_rep.h>
16#include <re/printer_re.h>
17#include <llvm/Support/Casting.h>
18
19namespace re {
20
21class Alt : public RE, public std::vector<RE*, ProxyAllocator<RE *>> {
22public:
23    static inline bool classof(const RE * re) {
24        return re->getClassTypeId() == ClassTypeId::Alt;
25    }
26    static inline bool classof(const void *) {
27        return false;
28    }
29protected:
30    friend Alt * makeAlt();
31    template<typename iterator> friend RE * makeAlt(iterator, iterator);
32    Alt() : RE(ClassTypeId::Alt), std::vector<RE*, ProxyAllocator<RE *>>(mAllocator) {}
33    Alt(iterator begin, iterator end)
34    : RE(ClassTypeId::Alt), std::vector<RE*, ProxyAllocator<RE *>>(begin, end, mAllocator) { }
35};
36
37/**
38 * @brief makeAlt
39 *
40 * Build an Alt, flattening alternative subgroups, and combining character classes and
41 * move character classes towards the end of the list to ensure that all combinations are found.
42 *
43 * @param list
44 * @return simplified RE representing the Alt
45 */
46
47inline Alt * makeAlt() {
48    return new Alt();
49}
50   
51template<typename iterator>
52RE * makeAlt(iterator begin, iterator end) {
53    Alt * newAlt = makeAlt();
54    if (LLVM_UNLIKELY(begin == end)) {
55        return newAlt;
56    }
57
58    llvm::SmallVector<CC *, 2> CCs(0); // CCs with possibly different alphabets
59    auto combineCC = [&CCs] (CC * cc) {
60        for (CC *& existing : CCs) {
61            if (LLVM_LIKELY(existing->getAlphabet() == cc->getAlphabet())) {
62                existing = makeCC(existing, cc);
63                return;
64            }
65        }
66        CCs.push_back(cc);
67    };
68
69    bool nullable = false;
70    RE * nullableSeq = nullptr;
71    for (auto i = begin; i != end; ++i) {
72        if (CC * cc = llvm::dyn_cast<CC>(*i)) {
73            combineCC(cc);
74        } else if (const Alt * alt = llvm::dyn_cast<Alt>(*i)) {
75            // We have an Alt to embed within the alt.  We extract the individual
76            // elements to include within the new alt.   Note that recursive flattening
77            // is not required, if the elements themselves were created with makeAlt.
78            for (RE * a : *alt) {
79                if (CC * cc = llvm::dyn_cast<CC>(a)) {
80                    combineCC(cc);
81                } else if (isEmptySeq(a) && !nullable) {
82                    nullable = true;
83                    nullableSeq = a;
84                } else {
85                    newAlt->push_back(a);
86                }
87            }
88        } else if (const Rep * rep = llvm::dyn_cast<Rep>(*i)) {
89            if (rep->getLB() == 0) {
90                if (nullable) {
91                    // Already have a nullable case.
92                    newAlt->push_back(makeRep(rep->getRE(), 1, rep->getUB()));
93                }
94                else {
95                    // This will be the nullable case.
96                    nullableSeq = *i;
97                    nullable = true;
98                }
99            } else {
100                newAlt->push_back(*i);
101            }
102        } else if (isEmptySeq(*i)) {
103            if (!nullable) {
104                nullable = true;
105                nullableSeq = *i;
106            }
107        } else {
108            newAlt->push_back(*i);
109        }
110    }
111    newAlt->insert(newAlt->end(), CCs.begin(), CCs.end());
112    if (nullable) {
113        if (nullableSeq == nullptr) {
114            nullableSeq = makeSeq();
115        }
116        newAlt->push_back(nullableSeq);
117    }
118    return newAlt->size() == 1 ? newAlt->front() : newAlt;
119}
120
121inline RE * makeAlt(std::initializer_list<RE *> list) {
122    return makeAlt(list.begin(), list.end());
123}
124
125}
126
127#endif // ALT_H
128
Note: See TracBrowser for help on using the repository browser.