← Back to branch summary

~ubuntu-branches/ubuntu/wily/apparmor/wily

« back to all changes in this revision

Viewing changes to parser/libapparmor_re/expr-tree.h

  • Committer: Bazaar Package Importer
  • Author(s): Kees Cook
  • Date: 2011-08-10 18:12:34 UTC
  • mto: This revision was merged to the branch mainline in revision 9.
  • Revision ID: james.westby@ubuntu.com-20110810181234-b6obckg60cp99crg
Tags: upstream-2.7.0~beta1+bzr1774
Import upstream version 2.7.0~beta1+bzr1774

Show diffs side-by-side

added added

removed removed

Lines of Context:
parser/libapparmor_re/expr-tree.h
 
1
/*
 
2
 * (C) 2006, 2007 Andreas Gruenbacher <agruen@suse.de>
 
3
 * Copyright (c) 2003-2008 Novell, Inc. (All rights reserved)
 
4
 * Copyright 2009-2010 Canonical Ltd.
 
5
 *
 
6
 * The libapparmor library is licensed under the terms of the GNU
 
7
 * Lesser General Public License, version 2.1. Please see the file
 
8
 * COPYING.LGPL.
 
9
 *
 
10
 * This library is distributed in the hope that it will be useful,
 
11
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 
12
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 
13
 * GNU Lesser General Public License for more details.
 
14
 *
 
15
 * You should have received a copy of the GNU Lesser General Public License
 
16
 * along with this program.  If not, see <http://www.gnu.org/licenses/>.
 
17
 *
 
18
 *
 
19
 * Functions to create/manipulate an expression tree for regular expressions
 
20
 * that have been parsed.
 
21
 *
 
22
 * The expression tree can be used directly after the parse creates it, or
 
23
 * it can be factored so that the set of important nodes is smaller.
 
24
 * Having a reduced set of important nodes generally results in a dfa that
 
25
 * is closer to minimum (fewer redundant states are created).  It also
 
26
 * results in fewer important nodes in a the state set during subset
 
27
 * construction resulting in less memory used to create a dfa.
 
28
 *
 
29
 * Generally it is worth doing expression tree simplification before dfa
 
30
 * construction, if the regular expression tree contains any alternations.
 
31
 * Even if the regular expression doesn't simplification should be fast
 
32
 * enough that it can be used with minimal overhead.
 
33
 */
 
34
#ifndef __LIBAA_RE_EXPR_H
 
35
#define __LIBAA_RE_EXPR_H
 
36
 
 
37
#include <map>
 
38
#include <set>
 
39
#include <stack>
 
40
#include <ostream>
 
41
 
 
42
#include <stdint.h>
 
43
 
 
44
#include "apparmor_re.h"
 
45
 
 
46
using namespace std;
 
47
 
 
48
typedef unsigned char uchar;
 
49
typedef set<uchar> Chars;
 
50
 
 
51
ostream &operator<<(ostream &os, uchar c);
 
52
 
 
53
/* Compute the union of two sets. */
 
54
template<class T> set<T> operator+(const set<T> &a, const set<T> &b)
 
55
{
 
56
        set<T> c(a);
 
57
        c.insert(b.begin(), b.end());
 
58
        return c;
 
59
}
 
60
 
 
61
/**
 
62
 * When creating DFAs from regex trees, a DFA state is constructed from
 
63
 * a set of important nodes in the syntax tree. This includes AcceptNodes,
 
64
 * which indicate that when a match ends in a particular state, the
 
65
 * regular expressions that the AcceptNode belongs to match.
 
66
 */
 
67
class Node;
 
68
class ImportantNode;
 
69
typedef set<ImportantNode *> NodeSet;
 
70
 
 
71
/**
 
72
 * Text-dump a state (for debugging).
 
73
 */
 
74
ostream &operator<<(ostream &os, const NodeSet &state);
 
75
 
 
76
/**
 
77
 * Out-edges from a state to another: we store the follow-set of Nodes
 
78
 * for each input character that is not a default match in
 
79
 * cases (i.e., following a CharNode or CharSetNode), and default
 
80
 * matches in otherwise as well as in all matching explicit cases
 
81
 * (i.e., following an AnyCharNode or NotCharSetNode). This avoids
 
82
 * enumerating all the explicit tranitions for default matches.
 
83
 */
 
84
typedef struct NodeCases {
 
85
        typedef map<uchar, NodeSet *>::iterator iterator;
 
86
        iterator begin() { return cases.begin(); }
 
87
        iterator end() { return cases.end(); }
 
88
 
 
89
        NodeCases(): otherwise(0) { }
 
90
        map<uchar, NodeSet *> cases;
 
91
        NodeSet *otherwise;
 
92
}
 
93
 
 
94
NodeCases;
 
95
 
 
96
ostream &operator<<(ostream &os, Node &node);
 
97
 
 
98
/* An abstract node in the syntax tree. */
 
99
class Node {
 
100
public:
 
101
        Node(): nullable(false) { child[0] = child[1] = 0; }
 
102
        Node(Node *left): nullable(false)
 
103
        {
 
104
                child[0] = left;
 
105
                child[1] = 0;
 
106
        }
 
107
        Node(Node *left, Node *right): nullable(false)
 
108
        {
 
109
                child[0] = left;
 
110
                child[1] = right;
 
111
        }
 
112
        virtual ~Node()
 
113
        {
 
114
                if (child[0])
 
115
                        child[0]->release();
 
116
                if (child[1])
 
117
                        child[1]->release();
 
118
        }
 
119
 
 
120
        /**
 
121
         * See the "Dragon Book" for an explanation of nullable, firstpos,
 
122
         * lastpos, and followpos.
 
123
         */
 
124
        virtual void compute_nullable() { }
 
125
        virtual void compute_firstpos() = 0;
 
126
        virtual void compute_lastpos() = 0;
 
127
        virtual void compute_followpos() { }
 
128
        virtual int eq(Node *other) = 0;
 
129
        virtual ostream &dump(ostream &os) = 0;
 
130
        void dump_syntax_tree(ostream &os);
 
131
 
 
132
        bool nullable;
 
133
        NodeSet firstpos, lastpos, followpos;
 
134
        /* child 0 is left, child 1 is right */
 
135
        Node *child[2];
 
136
 
 
137
        unsigned int label;     /* unique number for debug etc */
 
138
        /**
 
139
         * We indirectly release Nodes through a virtual function because
 
140
         * accept and Eps Nodes are shared, and must be treated specially.
 
141
         * We could use full reference counting here but the indirect release
 
142
         * is sufficient and has less overhead
 
143
         */
 
144
        virtual void release(void) { delete this; }
 
145
};
 
146
 
 
147
class InnerNode: public Node {
 
148
public:
 
149
        InnerNode(): Node() { };
 
150
        InnerNode(Node *left): Node(left) { };
 
151
        InnerNode(Node *left, Node *right): Node(left, right) { };
 
152
};
 
153
 
 
154
class OneChildNode: public InnerNode {
 
155
public:
 
156
        OneChildNode(Node *left): InnerNode(left) { };
 
157
};
 
158
 
 
159
class TwoChildNode: public InnerNode {
 
160
public:
 
161
        TwoChildNode(Node *left, Node *right): InnerNode(left, right) { };
 
162
};
 
163
 
 
164
class LeafNode: public Node {
 
165
public:
 
166
        LeafNode(): Node() { };
 
167
};
 
168
 
 
169
/* Match nothing (//). */
 
170
class EpsNode: public LeafNode {
 
171
public:
 
172
        EpsNode(): LeafNode()
 
173
        {
 
174
                nullable = true;
 
175
                label = 0;
 
176
        }
 
177
        void release(void)
 
178
        {
 
179
                /* don't delete Eps nodes because there is a single static
 
180
                 * instance shared by all trees.  Look for epsnode in the code
 
181
                 */
 
182
        }
 
183
 
 
184
        void compute_firstpos() { }
 
185
        void compute_lastpos() { }
 
186
        int eq(Node *other)
 
187
        {
 
188
                if (dynamic_cast<EpsNode *>(other))
 
189
                        return 1;
 
190
                return 0;
 
191
        }
 
192
        ostream &dump(ostream &os)
 
193
        {
 
194
                return os << "[]";
 
195
        }
 
196
};
 
197
 
 
198
/**
 
199
 * Leaf nodes in the syntax tree are important to us: they describe the
 
200
 * characters that the regular expression matches. We also consider
 
201
 * AcceptNodes import: they indicate when a regular expression matches.
 
202
 */
 
203
class ImportantNode: public LeafNode {
 
204
public:
 
205
        ImportantNode(): LeafNode() { }
 
206
        void compute_firstpos() { firstpos.insert(this); }
 
207
        void compute_lastpos() { lastpos.insert(this); }
 
208
        virtual void follow(NodeCases &cases) = 0;
 
209
};
 
210
 
 
211
/* common base class for all the different classes that contain
 
212
 * character information.
 
213
 */
 
214
class CNode: public ImportantNode {
 
215
public:
 
216
        CNode(): ImportantNode() { }
 
217
};
 
218
 
 
219
/* Match one specific character (/c/). */
 
220
class CharNode: public CNode {
 
221
public:
 
222
        CharNode(uchar c): c(c) { }
 
223
        void follow(NodeCases &cases)
 
224
        {
 
225
                NodeSet **x = &cases.cases[c];
 
226
                if (!*x) {
 
227
                        if (cases.otherwise)
 
228
                                *x = new NodeSet(*cases.otherwise);
 
229
                        else
 
230
                                *x = new NodeSet;
 
231
                }
 
232
                (*x)->insert(followpos.begin(), followpos.end());
 
233
        }
 
234
        int eq(Node *other)
 
235
        {
 
236
                CharNode *o = dynamic_cast<CharNode *>(other);
 
237
                if (o) {
 
238
                        return c == o->c;
 
239
                }
 
240
                return 0;
 
241
        }
 
242
        ostream &dump(ostream &os)
 
243
        {
 
244
                return os << c;
 
245
        }
 
246
 
 
247
        uchar c;
 
248
};
 
249
 
 
250
/* Match a set of characters (/[abc]/). */
 
251
class CharSetNode: public CNode {
 
252
public:
 
253
        CharSetNode(Chars &chars): chars(chars) { }
 
254
        void follow(NodeCases &cases)
 
255
        {
 
256
                for (Chars::iterator i = chars.begin(); i != chars.end(); i++) {
 
257
                        NodeSet **x = &cases.cases[*i];
 
258
                        if (!*x) {
 
259
                                if (cases.otherwise)
 
260
                                        *x = new NodeSet(*cases.otherwise);
 
261
                                else
 
262
                                        *x = new NodeSet;
 
263
                        }
 
264
                        (*x)->insert(followpos.begin(), followpos.end());
 
265
                }
 
266
        }
 
267
        int eq(Node *other)
 
268
        {
 
269
                CharSetNode *o = dynamic_cast<CharSetNode *>(other);
 
270
                if (!o || chars.size() != o->chars.size())
 
271
                        return 0;
 
272
 
 
273
                for (Chars::iterator i = chars.begin(), j = o->chars.begin();
 
274
                     i != chars.end() && j != o->chars.end(); i++, j++) {
 
275
                        if (*i != *j)
 
276
                                return 0;
 
277
                }
 
278
                return 1;
 
279
        }
 
280
        ostream &dump(ostream &os)
 
281
        {
 
282
                os << '[';
 
283
                for (Chars::iterator i = chars.begin(); i != chars.end(); i++)
 
284
                        os << *i;
 
285
                return os << ']';
 
286
        }
 
287
 
 
288
        Chars chars;
 
289
};
 
290
 
 
291
/* Match all except one character (/[^abc]/). */
 
292
class NotCharSetNode: public CNode {
 
293
public:
 
294
        NotCharSetNode(Chars &chars): chars(chars) { }
 
295
        void follow(NodeCases & cases)
 
296
        {
 
297
                if (!cases.otherwise)
 
298
                        cases.otherwise = new NodeSet;
 
299
                for (Chars::iterator j = chars.begin(); j != chars.end(); j++) {
 
300
                        NodeSet **x = &cases.cases[*j];
 
301
                        if (!*x)
 
302
                                *x = new NodeSet(*cases.otherwise);
 
303
                }
 
304
                /* Note: Add to the nonmatching characters after copying away
 
305
                 * the old otherwise state for the matching characters.
 
306
                 */
 
307
                cases.otherwise->insert(followpos.begin(), followpos.end());
 
308
                for (NodeCases::iterator i = cases.begin(); i != cases.end();
 
309
                     i++) {
 
310
                        if (chars.find(i->first) == chars.end())
 
311
                                i->second->insert(followpos.begin(),
 
312
                                                  followpos.end());
 
313
                }
 
314
        }
 
315
        int eq(Node *other)
 
316
        {
 
317
                NotCharSetNode *o = dynamic_cast<NotCharSetNode *>(other);
 
318
                if (!o || chars.size() != o->chars.size())
 
319
                        return 0;
 
320
 
 
321
                for (Chars::iterator i = chars.begin(), j = o->chars.begin();
 
322
                     i != chars.end() && j != o->chars.end(); i++, j++) {
 
323
                        if (*i != *j)
 
324
                                return 0;
 
325
                }
 
326
                return 1;
 
327
        }
 
328
        ostream &dump(ostream &os)
 
329
        {
 
330
                os << "[^";
 
331
                for (Chars::iterator i = chars.begin(); i != chars.end(); i++)
 
332
                        os << *i;
 
333
                return os << ']';
 
334
        }
 
335
 
 
336
        Chars chars;
 
337
};
 
338
 
 
339
/* Match any character (/./). */
 
340
class AnyCharNode: public CNode {
 
341
public:
 
342
        AnyCharNode() { }
 
343
        void follow(NodeCases &cases)
 
344
        {
 
345
                if (!cases.otherwise)
 
346
                        cases.otherwise = new NodeSet;
 
347
                cases.otherwise->insert(followpos.begin(), followpos.end());
 
348
                for (NodeCases::iterator i = cases.begin(); i != cases.end();
 
349
                     i++)
 
350
                        i->second->insert(followpos.begin(), followpos.end());
 
351
        }
 
352
        int eq(Node *other)
 
353
        {
 
354
                if (dynamic_cast<AnyCharNode *>(other))
 
355
                        return 1;
 
356
                return 0;
 
357
        }
 
358
        ostream &dump(ostream &os) { return os << "."; }
 
359
};
 
360
 
 
361
/**
 
362
 * Indicate that a regular expression matches. An AcceptNode itself
 
363
 * doesn't match anything, so it will never generate any transitions.
 
364
 */
 
365
class AcceptNode: public ImportantNode {
 
366
public:
 
367
        AcceptNode() { }
 
368
        void release(void)
 
369
        {
 
370
                /* don't delete AcceptNode via release as they are shared, and
 
371
                 * will be deleted when the table the are stored in is deleted
 
372
                 */
 
373
        }
 
374
 
 
375
        void follow(NodeCases &cases __attribute__ ((unused)))
 
376
        {
 
377
                /* Nothing to follow. */
 
378
        }
 
379
 
 
380
        /* requires accept nodes to be common by pointer */
 
381
        int eq(Node *other)
 
382
        {
 
383
                if (dynamic_cast<AcceptNode *>(other))
 
384
                        return (this == other);
 
385
                return 0;
 
386
        }
 
387
};
 
388
 
 
389
/* Match a node zero or more times. (This is a unary operator.) */
 
390
class StarNode: public OneChildNode {
 
391
public:
 
392
        StarNode(Node *left): OneChildNode(left) { nullable = true; }
 
393
        void compute_firstpos() { firstpos = child[0]->firstpos; }
 
394
        void compute_lastpos() { lastpos = child[0]->lastpos; }
 
395
        void compute_followpos()
 
396
        {
 
397
                NodeSet from = child[0]->lastpos, to = child[0]->firstpos;
 
398
                for (NodeSet::iterator i = from.begin(); i != from.end(); i++) {
 
399
                        (*i)->followpos.insert(to.begin(), to.end());
 
400
                }
 
401
        }
 
402
        int eq(Node *other)
 
403
        {
 
404
                if (dynamic_cast<StarNode *>(other))
 
405
                        return child[0]->eq(other->child[0]);
 
406
                return 0;
 
407
        }
 
408
        ostream &dump(ostream &os)
 
409
        {
 
410
                os << '(';
 
411
                child[0]->dump(os);
 
412
                return os << ")*";
 
413
        }
 
414
};
 
415
 
 
416
/* Match a node one or more times. (This is a unary operator.) */
 
417
class PlusNode: public OneChildNode {
 
418
public:
 
419
        PlusNode(Node *left): OneChildNode(left) {
 
420
        }
 
421
        void compute_nullable() { nullable = child[0]->nullable; }
 
422
        void compute_firstpos() { firstpos = child[0]->firstpos; }
 
423
        void compute_lastpos() { lastpos = child[0]->lastpos; }
 
424
        void compute_followpos()
 
425
        {
 
426
                NodeSet from = child[0]->lastpos, to = child[0]->firstpos;
 
427
                for (NodeSet::iterator i = from.begin(); i != from.end(); i++) {
 
428
                        (*i)->followpos.insert(to.begin(), to.end());
 
429
                }
 
430
        }
 
431
        int eq(Node *other) {
 
432
                if (dynamic_cast<PlusNode *>(other))
 
433
                        return child[0]->eq(other->child[0]);
 
434
                return 0;
 
435
        }
 
436
        ostream &dump(ostream &os) {
 
437
                os << '(';
 
438
                child[0]->dump(os);
 
439
                return os << ")+";
 
440
        }
 
441
};
 
442
 
 
443
/* Match a pair of consecutive nodes. */
 
444
class CatNode: public TwoChildNode {
 
445
public:
 
446
        CatNode(Node *left, Node *right): TwoChildNode(left, right) { }
 
447
        void compute_nullable()
 
448
        {
 
449
                nullable = child[0]->nullable && child[1]->nullable;
 
450
        }
 
451
        void compute_firstpos()
 
452
        {
 
453
                if (child[0]->nullable)
 
454
                        firstpos = child[0]->firstpos + child[1]->firstpos;
 
455
                else
 
456
                        firstpos = child[0]->firstpos;
 
457
        }
 
458
        void compute_lastpos()
 
459
        {
 
460
                if (child[1]->nullable)
 
461
                        lastpos = child[0]->lastpos + child[1]->lastpos;
 
462
                else
 
463
                        lastpos = child[1]->lastpos;
 
464
        }
 
465
        void compute_followpos()
 
466
        {
 
467
                NodeSet from = child[0]->lastpos, to = child[1]->firstpos;
 
468
                for (NodeSet::iterator i = from.begin(); i != from.end(); i++) {
 
469
                        (*i)->followpos.insert(to.begin(), to.end());
 
470
                }
 
471
        }
 
472
        int eq(Node *other)
 
473
        {
 
474
                if (dynamic_cast<CatNode *>(other)) {
 
475
                        if (!child[0]->eq(other->child[0]))
 
476
                                return 0;
 
477
                        return child[1]->eq(other->child[1]);
 
478
                }
 
479
                return 0;
 
480
        }
 
481
        ostream &dump(ostream &os)
 
482
        {
 
483
                child[0]->dump(os);
 
484
                child[1]->dump(os);
 
485
                return os;
 
486
        }
 
487
};
 
488
 
 
489
/* Match one of two alternative nodes. */
 
490
class AltNode: public TwoChildNode {
 
491
public:
 
492
        AltNode(Node *left, Node *right): TwoChildNode(left, right) { }
 
493
        void compute_nullable()
 
494
        {
 
495
                nullable = child[0]->nullable || child[1]->nullable;
 
496
        }
 
497
        void compute_lastpos()
 
498
        {
 
499
                lastpos = child[0]->lastpos + child[1]->lastpos;
 
500
        }
 
501
        void compute_firstpos()
 
502
        {
 
503
                firstpos = child[0]->firstpos + child[1]->firstpos;
 
504
        }
 
505
        int eq(Node *other)
 
506
        {
 
507
                if (dynamic_cast<AltNode *>(other)) {
 
508
                        if (!child[0]->eq(other->child[0]))
 
509
                                return 0;
 
510
                        return child[1]->eq(other->child[1]);
 
511
                }
 
512
                return 0;
 
513
        }
 
514
        ostream &dump(ostream &os)
 
515
        {
 
516
                os << '(';
 
517
                child[0]->dump(os);
 
518
                os << '|';
 
519
                child[1]->dump(os);
 
520
                os << ')';
 
521
                return os;
 
522
        }
 
523
};
 
524
 
 
525
/* Traverse the syntax tree depth-first in an iterator-like manner. */
 
526
class depth_first_traversal {
 
527
        stack<Node *>pos;
 
528
        void push_left(Node *node) {
 
529
                pos.push(node);
 
530
 
 
531
                while (dynamic_cast<InnerNode *>(node)) {
 
532
                        pos.push(node->child[0]);
 
533
                        node = node->child[0];
 
534
                }
 
535
        }
 
536
public:
 
537
        depth_first_traversal(Node *node) { push_left(node); }
 
538
        Node *operator*() { return pos.top(); }
 
539
        Node *operator->() { return pos.top(); }
 
540
        operator  bool() { return !pos.empty(); }
 
541
        void operator++(int)
 
542
        {
 
543
                Node *last = pos.top();
 
544
                pos.pop();
 
545
 
 
546
                if (!pos.empty()) {
 
547
                        /* no need to dynamic cast, as we just popped a node so
 
548
                         * the top node must be an inner node */
 
549
                        InnerNode *node = (InnerNode *) (pos.top());
 
550
                        if (node->child[1] && node->child[1] != last) {
 
551
                                push_left(node->child[1]);
 
552
                        }
 
553
                }
 
554
        }
 
555
};
 
556
 
 
557
struct node_counts {
 
558
        int charnode;
 
559
        int charset;
 
560
        int notcharset;
 
561
        int alt;
 
562
        int plus;
 
563
        int star;
 
564
        int any;
 
565
        int cat;
 
566
};
 
567
 
 
568
extern EpsNode epsnode;
 
569
 
 
570
int debug_tree(Node *t);
 
571
Node *simplify_tree(Node *t, dfaflags_t flags);
 
572
void label_nodes(Node *root);
 
573
unsigned long hash_NodeSet(NodeSet *ns);
 
574
void flip_tree(Node *node);
 
575
 
 
576
/* Comparison operator for sets of <NodeSet *>.
 
577
 * Compare set hashes, and if the sets have the same hash
 
578
 * do compare pointer comparison on set of <Node *>, the pointer comparison
 
579
 * allows us to determine which Sets of <Node *> we have seen already from
 
580
 * new ones when constructing the DFA.
 
581
 */
 
582
struct deref_less_than {
 
583
        bool operator()(pair<unsigned long, NodeSet *>const &lhs,
 
584
                        pair<unsigned long, NodeSet *>const &rhs)const
 
585
        {
 
586
                if (lhs.first == rhs.first)
 
587
                        return *(lhs.second) < *(rhs.second);
 
588
                else
 
589
                        return lhs.first < rhs.first;
 
590
        }
 
591
};
 
592
 
 
593
class MatchFlag: public AcceptNode {
 
594
public:
 
595
        MatchFlag(uint32_t flag, uint32_t audit): flag(flag), audit(audit) { }
 
596
        ostream &dump(ostream &os) { return os << '<' << flag << '>'; }
 
597
 
 
598
        uint32_t flag;
 
599
        uint32_t audit;
 
600
};
 
601
 
 
602
class ExactMatchFlag: public MatchFlag {
 
603
public:
 
604
        ExactMatchFlag(uint32_t flag, uint32_t audit): MatchFlag(flag, audit) {}
 
605
};
 
606
 
 
607
class DenyMatchFlag: public MatchFlag {
 
608
public:
 
609
        DenyMatchFlag(uint32_t flag, uint32_t quiet): MatchFlag(flag, quiet) {}
 
610
};
 
611
 
 
612
#endif /* __LIBAA_RE_EXPR */