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

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

Contextual assertion simplifier from Jeremy Schwartz - initial check-in

File size: 3.8 KB
RevLine 
[3850]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"
[6195]11#include <util/slab_allocator.h>
12#include <vector>
[5811]13#include <re/re_cc.h>
14#include <re/re_seq.h>
15#include <re/re_rep.h>
16#include <re/printer_re.h>
[5267]17#include <llvm/Support/Casting.h>
[3850]18
[4194]19namespace re {
[3914]20
[6195]21class Alt : public RE, public std::vector<RE*, ProxyAllocator<RE *>> {
[3850]22public:
[4194]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();
[4203]31    template<typename iterator> friend RE * makeAlt(iterator, iterator);
[6195]32    Alt() : RE(ClassTypeId::Alt), std::vector<RE*, ProxyAllocator<RE *>>(mAllocator) {}
[4194]33    Alt(iterator begin, iterator end)
[6195]34    : RE(ClassTypeId::Alt), std::vector<RE*, ProxyAllocator<RE *>>(begin, end, mAllocator) { }
[3850]35};
36
[4203]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
[4194]47inline Alt * makeAlt() {
48    return new Alt();
49}
[5811]50   
[4203]51template<typename iterator>
52RE * makeAlt(iterator begin, iterator end) {
[5775]53    Alt * newAlt = makeAlt();
[5835]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;
[5866]70    RE * nullableSeq = nullptr;
[5775]71    for (auto i = begin; i != end; ++i) {
[5782]72        if (CC * cc = llvm::dyn_cast<CC>(*i)) {
[5835]73            combineCC(cc);
[5775]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)) {
[5835]80                    combineCC(cc);
[5866]81                } else if (isEmptySeq(a) && !nullable) {
[5835]82                    nullable = true;
[5866]83                    nullableSeq = a;
[5782]84                } else {
85                    newAlt->push_back(a);
[5775]86                }
87            }
[5811]88        } else if (const Rep * rep = llvm::dyn_cast<Rep>(*i)) {
89            if (rep->getLB() == 0) {
[5866]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                }
[5811]99            } else {
100                newAlt->push_back(*i);
101            }
102        } else if (isEmptySeq(*i)) {
[5866]103            if (!nullable) {
104                nullable = true;
105                nullableSeq = *i;
106            }
[5811]107        } else {
[5775]108            newAlt->push_back(*i);
109        }
[4203]110    }
[5835]111    newAlt->insert(newAlt->end(), CCs.begin(), CCs.end());
112    if (nullable) {
[5866]113        if (nullableSeq == nullptr) {
114            nullableSeq = makeSeq();
[5835]115        }
[5866]116        newAlt->push_back(nullableSeq);
[5782]117    }
[5835]118    return newAlt->size() == 1 ? newAlt->front() : newAlt;
[4194]119}
120
[6223]121inline RE * makeAlt(std::initializer_list<RE *> list) {
[4203]122    return makeAlt(list.begin(), list.end());
[4194]123}
124
[4203]125}
126
[3850]127#endif // ALT_H
128
Note: See TracBrowser for help on using the repository browser.