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

Last change on this file since 6184 was 5866, checked in by cameron, 19 months ago

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

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"
[5811]11#include <re/re_cc.h>
12#include <re/re_seq.h>
13#include <re/re_rep.h>
14#include <re/printer_re.h>
[5267]15#include <llvm/Support/Casting.h>
[3850]16
[4194]17namespace re {
[3914]18
[4194]19class Alt : public Vector {
[3850]20public:
[4194]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();
[4203]29    template<typename iterator> friend RE * makeAlt(iterator, iterator);
[4194]30    Alt()
31    : Vector(ClassTypeId::Alt) {
32
33    }
34    Alt(iterator begin, iterator end)
35    : Vector(ClassTypeId::Alt, begin, end) {
36
[4272]37    }
[3850]38};
39
[4203]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
[4194]50inline Alt * makeAlt() {
51    return new Alt();
52}
[5811]53   
[4203]54template<typename iterator>
55RE * makeAlt(iterator begin, iterator end) {
[5775]56    Alt * newAlt = makeAlt();
[5835]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;
[5866]73    RE * nullableSeq = nullptr;
[5775]74    for (auto i = begin; i != end; ++i) {
[5782]75        if (CC * cc = llvm::dyn_cast<CC>(*i)) {
[5835]76            combineCC(cc);
[5775]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)) {
[5835]83                    combineCC(cc);
[5866]84                } else if (isEmptySeq(a) && !nullable) {
[5835]85                    nullable = true;
[5866]86                    nullableSeq = a;
[5782]87                } else {
88                    newAlt->push_back(a);
[5775]89                }
90            }
[5811]91        } else if (const Rep * rep = llvm::dyn_cast<Rep>(*i)) {
92            if (rep->getLB() == 0) {
[5866]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                }
[5811]102            } else {
103                newAlt->push_back(*i);
104            }
105        } else if (isEmptySeq(*i)) {
[5866]106            if (!nullable) {
107                nullable = true;
108                nullableSeq = *i;
109            }
[5811]110        } else {
[5775]111            newAlt->push_back(*i);
112        }
[4203]113    }
[5835]114    newAlt->insert(newAlt->end(), CCs.begin(), CCs.end());
115    if (nullable) {
[5866]116        if (nullableSeq == nullptr) {
117            nullableSeq = makeSeq();
[5835]118        }
[5866]119        newAlt->push_back(nullableSeq);
[5782]120    }
[5835]121    return newAlt->size() == 1 ? newAlt->front() : newAlt;
[4194]122}
123
[4203]124inline RE * makeAlt(RE::InitializerList list) {
125    return makeAlt(list.begin(), list.end());
[4194]126}
127
[5811]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();
[4203]131}
[5811]132}
[4203]133
[3850]134#endif // ALT_H
135
Note: See TracBrowser for help on using the repository browser.