1 //  $Id$
2 // Copyright (c) 2001,2002                        RIPE NCC
3 //
4 // All Rights Reserved
5 //
6 // Permission to use, copy, modify, and distribute this software and its
7 // documentation for any purpose and without fee is hereby granted,
8 // provided that the above copyright notice appear in all copies and that
9 // both that copyright notice and this permission notice appear in
10 // supporting documentation, and that the name of the author not be
11 // used in advertising or publicity pertaining to distribution of the
12 // software without specific, written prior permission.
13 //
14 // THE AUTHOR DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE, INCLUDING
15 // ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS; IN NO EVENT SHALL
16 // AUTHOR BE LIABLE FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL DAMAGES OR ANY
17 // DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN
18 // AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
19 // OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
20 //
21 //
22 //  Copyright (c) 1994 by the University of Southern California
23 //  All rights reserved.
24 //
25 //    Permission is hereby granted, free of charge, to any person obtaining a copy
26 //    of this software and associated documentation files (the "Software"), to deal
27 //    in the Software without restriction, including without limitation the rights
28 //    to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
29 //    copies of the Software, and to permit persons to whom the Software is
30 //    furnished to do so, subject to the following conditions:
31 //
32 //    The above copyright notice and this permission notice shall be included in
33 //    all copies or substantial portions of the Software.
34 //
35 //    THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
36 //    IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
37 //    FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
38 //    AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
39 //    LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
40 //    OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
41 //    THE SOFTWARE.
42 //
43 //  Questions concerning this software should be directed to
44 //  irrtoolset@cs.usc.edu.
45 //
46 //  Author(s): Cengiz Alaettinoglu <cengiz@ISI.EDU>
47 
48 #ifndef REGEXP_NF_H
49 #define REGEXP_NF_H
50 
51 #include "config.h"
52 #include <iostream>
53 #include "rpsl/List.hh"
54 #include "rpsl/regexp.hh"
55 #include "rpsl/rpsl_item.hh"
56 
57 typedef unsigned int ASt;
58 const int RE_INVALID_AS = RANGE_TOP + 1;
59 
60 extern "C" {
61 #include "re2dfa.h"
62 }
63 
64 #define REGEXPNF_FRIENDS \
65    friend std::ostream& operator<<(std::ostream& os, const regexp& r); \
66    friend class regexp; \
67    friend class CiscoConfig;\
68    friend class CiscoXRConfig;\
69    friend class JunosConfig;
70 
71 class regexp_nf : public regexp {
72 REGEXPNF_FRIENDS
73 friend std::ostream& operator<<(std::ostream& os, const regexp_nf& r);
74 private:
75    rd_fm* m;
76    static bool expand_as_macros;
77 
78 private:
79    class RegexpConjunct : public ListNode {
80    public:
81       class ReInt : public ListNode {
82       public:
83 	 regexp *re;
84 	 int    negated;
ReInt()85 	 ReInt() {
86 	    re = (regexp *) NULL;
87 	    negated = 0;
88 	 }
ReInt(const ReInt & b)89 	 ReInt(const ReInt& b) {
90 	    re = b.re->dup();
91 	    negated = b.negated;
92 	 }
~ReInt(void)93 	~ReInt(void) {
94 	  if (re) delete re;
95 	}
96       };
97       int    mark;
98       List<ReInt> regexs;
RegexpConjunct()99       RegexpConjunct() {
100 	 mark    = 0;
101       }
102       RegexpConjunct(const RegexpConjunct &s);
103    };
104    List<RegexpConjunct> rclist;
105 
106 public:
regexp_nf()107    regexp_nf() {
108       m = (rd_fm *) NULL;
109       become_empty();
110    }
111 
112    regexp_nf(const regexp_nf& s);
113 
regexp_nf(regexp * re,ASt peerAS=RE_INVALID_AS)114    regexp_nf(regexp* re, ASt peerAS = RE_INVALID_AS) {
115       RegexpConjunct *rc = new RegexpConjunct;
116       RegexpConjunct::ReInt *ri = new RegexpConjunct::ReInt;
117       ri->re = re;
118       ri->negated = 0;
119       rc->regexs.append(ri);
120       rclist.append(rc);
121       m = (rd_fm *) NULL;
122       m = dfa(peerAS);
123   }
124 
~regexp_nf(void)125   ~regexp_nf(void) {
126      if (m) rd_free_dfa(m);
127   }
128 
129    virtual regexp* dup() const;
130 
dup_nf() const131    regexp_nf* dup_nf() const {
132       return new regexp_nf(*this);
133    }
134 
135    void become_universal();
136    void become_empty();
137 
138    bool operator==(regexp_nf& b);
equals(const regexp & b)139    bool equals(const regexp &b) {
140       return typeid(b) == typeid(regexp_nf)
141 	 && (*this) == (regexp_nf &) b;
142    }
143 
144    bool is_universal();
145    bool isEmpty();
146    bool isEmptyStr();
147 
148    void do_not();
149    void do_or(regexp_nf &b);	// destroys b
150    void do_and(regexp_nf &b);	// destroys b
151 
expandASSets()152    static void expandASSets() {
153       expand_as_macros = true;
154    }
155 
156    regexp* construct() const;
157 
158    bool match(List<ItemASNO> & path);  //Added by mehringe@isi.edu
159 
160 private:
161    regexp* buildCat(regexp *l, regexp *r) const;
162    regexp* buildOr(regexp *l, regexp *r) const;
163    regexp* buildStar(regexp *l) const;
164    regexp* buildQuestion(regexp *l) const;
165 
166 
167    rd_fm* dfa(ASt peerAS = RE_INVALID_AS);
168    rd_fm* re2nfa(regexp *re, ASt peerAS) const;
169    void do_and_terms(regexp_nf &b);	// destroys b's terms
170    rd_fm *do_tildaplus_as(rd_fm *result, ASt as, bool star) const;
171    rd_fm *do_tildaplus(regexp_symbol *sym, ASt peerAS, bool star) const;
172 };
173 
174 #endif   // REGEXP_NF_H
175