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

Last change on this file was 5866, checked in by cameron, 2 weeks ago

Revised canonical form for nullable expressions; extended star-normal xfrm

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 <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   
54template<typename iterator>
55RE * makeAlt(iterator begin, iterator end) {
56    Alt * newAlt = makeAlt();
57    if (LLVM_UNLIKELY(begin == end)) {
58        return newAlt;
59    }
60
61    llvm::SmallVector<CC *, 2> CCs(0); // CCs with possibly different alphabets
62    auto combineCC = [&CCs] (CC * cc) {
63        for (CC *& existing : CCs) {
64            if (LLVM_LIKELY(existing->getAlphabet() == cc->getAlphabet())) {
65                existing = makeCC(existing, cc);
66                return;
67            }
68        }
69        CCs.push_back(cc);
70    };
71
72    bool nullable = false;
73    RE * nullableSeq = nullptr;
74    for (auto i = begin; i != end; ++i) {
75        if (CC * cc = llvm::dyn_cast<CC>(*i)) {
76            combineCC(cc);
77        } else if (const Alt * alt = llvm::dyn_cast<Alt>(*i)) {
78            // We have an Alt to embed within the alt.  We extract the individual
79            // elements to include within the new alt.   Note that recursive flattening
80            // is not required, if the elements themselves were created with makeAlt.
81            for (RE * a : *alt) {
82                if (CC * cc = llvm::dyn_cast<CC>(a)) {
83                    combineCC(cc);
84                } else if (isEmptySeq(a) && !nullable) {
85                    nullable = true;
86                    nullableSeq = a;
87                } else {
88                    newAlt->push_back(a);
89                }
90            }
91        } else if (const Rep * rep = llvm::dyn_cast<Rep>(*i)) {
92            if (rep->getLB() == 0) {
93                if (nullable) {
94                    // Already have a nullable case.
95                    newAlt->push_back(makeRep(rep->getRE(), 1, rep->getUB()));
96                }
97                else {
98                    // This will be the nullable case.
99                    nullableSeq = *i;
100                    nullable = true;
101                }
102            } else {
103                newAlt->push_back(*i);
104            }
105        } else if (isEmptySeq(*i)) {
106            if (!nullable) {
107                nullable = true;
108                nullableSeq = *i;
109            }
110        } else {
111            newAlt->push_back(*i);
112        }
113    }
114    newAlt->insert(newAlt->end(), CCs.begin(), CCs.end());
115    if (nullable) {
116        if (nullableSeq == nullptr) {
117            nullableSeq = makeSeq();
118        }
119        newAlt->push_back(nullableSeq);
120    }
121    return newAlt->size() == 1 ? newAlt->front() : newAlt;
122}
123
124inline RE * makeAlt(RE::InitializerList list) {
125    return makeAlt(list.begin(), list.end());
126}
127
128// An Alt with no members represent the empty set.
129inline bool isEmptySet(RE * r) {
130    return llvm::isa<Alt>(r) && llvm::cast<Alt>(r)->empty();
131}
132}
133
134#endif // ALT_H
135
Note: See TracBrowser for help on using the repository browser.