← Back to branch summary

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

« back to all changes in this revision

Viewing changes to parser/libapparmor_re/regexp.y

  • Committer: Bazaar Package Importer
  • Author(s): Kees Cook
  • Date: 2011-04-27 10:38:07 UTC
  • mfrom: (5.1.118 natty)
  • Revision ID: james.westby@ubuntu.com-20110427103807-ym3rhwys6o84ith0
Tags: 2.6.1-2
debian/copyright: clarify for some full organization names.

Show diffs side-by-side

added added

removed removed

Lines of Context:
parser/libapparmor_re/regexp.y
1
1
/*
2
2
 * regexp.y -- Regular Expression Matcher Generator
3
 
 * (C) 2006 Andreas Gruenbacher <agruen@suse.de>
 
3
 * (C) 2006, 2007 Andreas Gruenbacher <agruen@suse.de>
4
4
 *
5
5
 * Implementation based on the Lexical Analysis chapter of:
6
6
 *   Alfred V. Aho, Ravi Sethi, Jeffrey D. Ullman:
15
15
 */
16
16
 
17
17
%{
 
18
    /* #define DEBUG_TREE */
 
19
 
18
20
    #include <list>
19
21
    #include <vector>
 
22
    #include <stack>
20
23
    #include <set>
21
24
    #include <map>
22
25
    #include <ostream>
 
26
    #include <iostream>
 
27
    #include <fstream>
23
28
 
24
29
    using namespace std;
25
30
 
38
43
    }
39
44
 
40
45
    /**
41
 
     * A DFA state is a set of important nodes in the syntax tree. This
42
 
     * includes AcceptNodes, which indicate that when a match ends in a
43
 
     * particular state, the regular expressions that the AcceptNode
44
 
     * belongs to match.
 
46
     * When creating DFAs from regex trees, a DFA state is constructed from
 
47
     * a set of important nodes in the syntax tree. This includes AcceptNodes,
 
48
     * which indicate that when a match ends in a particular state, the
 
49
     * regular expressions that the AcceptNode belongs to match.
45
50
     */
46
51
    class ImportantNode;
47
 
    typedef set <ImportantNode *> State;
 
52
    typedef set <ImportantNode *> NodeSet;
48
53
 
49
54
    /**
50
 
     * Out-edges from a state to another: we store the follow-state
 
55
     * Out-edges from a state to another: we store the follow-set of Nodes
51
56
     * for each input character that is not a default match in
52
57
     * cases (i.e., following a CharNode or CharSetNode), and default
53
58
     * matches in otherwise as well as in all matching explicit cases
54
59
     * (i.e., following an AnyCharNode or NotCharSetNode). This avoids
55
60
     * enumerating all the explicit tranitions for default matches.
56
61
     */
57
 
    typedef struct Cases {
58
 
        typedef map<uchar, State *>::iterator iterator;
 
62
    typedef struct NodeCases {
 
63
        typedef map<uchar, NodeSet *>::iterator iterator;
59
64
        iterator begin() { return cases.begin(); }
60
65
        iterator end() { return cases.end(); }
61
66
 
62
 
        Cases() : otherwise(0) { }
63
 
        map<uchar, State *> cases;
64
 
        State *otherwise;
65
 
    } Cases;
 
67
        NodeCases() : otherwise(0) { }
 
68
        map<uchar, NodeSet *> cases;
 
69
        NodeSet *otherwise;
 
70
    } NodeCases;
 
71
 
66
72
 
67
73
    /* An abstract node in the syntax tree. */
68
74
    class Node {
69
75
    public:
70
76
        Node() :
71
 
            nullable(false), left(0), right(0), refcount(1) { }
 
77
            nullable(false) { child[0] = child[1] = 0; }
72
78
        Node(Node *left) :
73
 
            nullable(false), left(left), right(0), refcount(1) { }
 
79
            nullable(false) { child[0] = left; child[1] = 0; }
74
80
        Node(Node *left, Node *right) :
75
 
            nullable(false), left(left), right(right), refcount(1) { }
 
81
            nullable(false) { child[0] = left; child[1] = right; }
76
82
        virtual ~Node()
77
83
        {
78
 
            if (left)
79
 
                left->release();
80
 
            if (right)
81
 
                right->release();
 
84
            if (child[0])
 
85
                    child[0]->release();
 
86
            if (child[1])
 
87
                    child[1]->release();
82
88
        }
83
89
 
84
90
        /**
89
95
        virtual void compute_firstpos() = 0;
90
96
        virtual void compute_lastpos() = 0;
91
97
        virtual void compute_followpos() { }
92
 
 
 
98
        virtual int eq(Node *other) = 0;
93
99
        virtual ostream& dump(ostream& os) = 0;
94
100
 
95
101
        bool nullable;
96
 
        State firstpos, lastpos, followpos;
97
 
        Node *left, *right;
 
102
        NodeSet firstpos, lastpos, followpos;
 
103
        /* child 0 is left, child 1 is right */
 
104
        Node *child[2];
98
105
 
 
106
        unsigned int label;     /* unique number for debug etc */
99
107
        /**
100
 
         * We need reference counting for AcceptNodes: sharing AcceptNodes
101
 
         * avoids introducing duplicate States with identical accept values.
 
108
         * We indirectly release Nodes through a virtual function because
 
109
         * accept and Eps Nodes are shared, and must be treated specially.
 
110
         * We could use full reference counting here but the indirect release
 
111
         * is sufficient and has less overhead
102
112
         */
103
 
        unsigned int refcount;
104
 
        void dup(void) { refcount++; }
105
 
        void release(void) {
106
 
            if (--refcount == 0)
107
 
                delete this;
 
113
        virtual void release(void) {
 
114
            delete this;
108
115
        }
109
116
    };
110
117
 
 
118
    class InnerNode : public Node {
 
119
    public:
 
120
        InnerNode() : Node() { };
 
121
        InnerNode(Node *left) : Node(left) {};
 
122
        InnerNode(Node *left, Node *right) : Node(left, right) { };
 
123
    };
 
124
 
 
125
    class OneChildNode : public InnerNode {
 
126
    public:
 
127
        OneChildNode(Node *left) : InnerNode(left) { };
 
128
    };
 
129
 
 
130
    class TwoChildNode : public InnerNode {
 
131
    public:
 
132
        TwoChildNode(Node *left, Node *right) :  InnerNode(left, right) { };
 
133
    };
 
134
 
 
135
    class LeafNode : public Node {
 
136
    public:
 
137
        LeafNode() : Node() { };
 
138
 
 
139
    };
 
140
 
111
141
    /* Match nothing (//). */
112
 
    class EpsNode : public Node {
 
142
    class EpsNode : public LeafNode {
113
143
    public:
114
 
        EpsNode()
 
144
    EpsNode() : LeafNode()
115
145
        {
116
146
            nullable = true;
117
 
        }
 
147
            label = 0;
 
148
        }
 
149
        void release(void)
 
150
        {
 
151
          /* don't delete Eps nodes because there is a single static instance
 
152
           * shared by all trees.  Look for epsnode in the code
 
153
           */
 
154
        }
 
155
 
118
156
        void compute_firstpos()
119
157
        {
120
158
        }
121
159
        void compute_lastpos()
122
160
        {
123
161
        }
 
162
        int eq(Node *other) {
 
163
                if (dynamic_cast<EpsNode *>(other))
 
164
                        return 1;
 
165
                return 0;
 
166
        }
124
167
        ostream& dump(ostream& os)
125
168
        {
126
169
            return os << "[]";
132
175
     * characters that the regular expression matches. We also consider
133
176
     * AcceptNodes import: they indicate when a regular expression matches.
134
177
     */
135
 
    class ImportantNode : public Node {
 
178
    class ImportantNode : public LeafNode {
136
179
    public:
137
 
        ImportantNode() { }
 
180
        ImportantNode() : LeafNode() { }
138
181
        void compute_firstpos()
139
182
        {
140
183
            firstpos.insert(this);
142
185
        void compute_lastpos() {
143
186
            lastpos.insert(this);
144
187
        }
145
 
        virtual void follow(Cases& cases) = 0;
 
188
        virtual void follow(NodeCases& cases) = 0;
 
189
    };
 
190
 
 
191
    /* common base class for all the different classes that contain
 
192
     * character information.
 
193
     */
 
194
    class CNode : public ImportantNode {
 
195
    public:
 
196
        CNode() : ImportantNode() { }
 
197
 
146
198
    };
147
199
 
148
200
    /* Match one specific character (/c/). */
149
 
    class CharNode : public ImportantNode {
 
201
    class CharNode : public CNode {
150
202
    public:
151
203
        CharNode(uchar c) : c(c) { }
152
 
        void follow(Cases& cases)
 
204
        void follow(NodeCases& cases)
153
205
        {
154
 
            State **x = &cases.cases[c];
 
206
            NodeSet **x = &cases.cases[c];
155
207
            if (!*x) {
156
208
                if (cases.otherwise)
157
 
                    *x = new State(*cases.otherwise);
 
209
                    *x = new NodeSet(*cases.otherwise);
158
210
                else
159
 
                    *x = new State;
 
211
                    *x = new NodeSet;
160
212
            }
161
213
            (*x)->insert(followpos.begin(), followpos.end());
162
214
        }
 
215
        int eq(Node *other) {
 
216
                CharNode *o = dynamic_cast<CharNode *>(other);
 
217
                if (o) {
 
218
                        return c == o->c;
 
219
                }
 
220
                return 0;
 
221
        }
163
222
        ostream& dump(ostream& os)
164
223
        {
165
224
            return os << c;
169
228
    };
170
229
 
171
230
    /* Match a set of characters (/[abc]/). */
172
 
    class CharSetNode : public ImportantNode {
 
231
    class CharSetNode : public CNode {
173
232
    public:
174
233
        CharSetNode(Chars& chars) : chars(chars) { }
175
 
        void follow(Cases& cases)
 
234
        void follow(NodeCases& cases)
176
235
        {
177
236
            for (Chars::iterator i = chars.begin(); i != chars.end(); i++) {
178
 
                State **x = &cases.cases[*i];
 
237
                NodeSet **x = &cases.cases[*i];
179
238
                if (!*x) {
180
239
                    if (cases.otherwise)
181
 
                        *x = new State(*cases.otherwise);
 
240
                        *x = new NodeSet(*cases.otherwise);
182
241
                    else
183
 
                        *x = new State;
 
242
                        *x = new NodeSet;
184
243
                }
185
244
                (*x)->insert(followpos.begin(), followpos.end());
186
245
            }
187
246
        }
 
247
        int eq(Node *other) {
 
248
                CharSetNode *o = dynamic_cast<CharSetNode *>(other);
 
249
                if (!o || chars.size() != o->chars.size())
 
250
                        return 0;
 
251
 
 
252
                for (Chars::iterator i = chars.begin(), j = o->chars.begin();
 
253
                     i != chars.end() && j != o->chars.end();
 
254
                     i++, j++) {
 
255
                        if (*i != *j)
 
256
                                return 0;
 
257
                }
 
258
                return 1;
 
259
        }
188
260
        ostream& dump(ostream& os)
189
261
        {
190
262
            os << '[';
197
269
    };
198
270
 
199
271
    /* Match all except one character (/[^abc]/). */
200
 
    class NotCharSetNode : public ImportantNode {
 
272
    class NotCharSetNode : public CNode {
201
273
    public:
202
274
        NotCharSetNode(Chars& chars) : chars(chars) { }
203
 
        void follow(Cases& cases)
 
275
        void follow(NodeCases& cases)
204
276
        {
205
277
            if (!cases.otherwise)
206
 
                cases.otherwise = new State;
 
278
                cases.otherwise = new NodeSet;
207
279
            for (Chars::iterator j = chars.begin(); j != chars.end(); j++) {
208
 
                State **x = &cases.cases[*j];
 
280
                NodeSet **x = &cases.cases[*j];
209
281
                if (!*x)
210
 
                    *x = new State(*cases.otherwise);
 
282
                    *x = new NodeSet(*cases.otherwise);
211
283
            }
212
284
            /**
213
285
             * Note: Add to the nonmatching characters after copying away the
214
286
             * old otherwise state for the matching characters.
215
287
             */
216
288
            cases.otherwise->insert(followpos.begin(), followpos.end());
217
 
            for (Cases::iterator i = cases.begin(); i != cases.end(); i++) {
 
289
            for (NodeCases::iterator i = cases.begin(); i != cases.end(); i++) {
218
290
                if (chars.find(i->first) == chars.end())
219
291
                    i->second->insert(followpos.begin(), followpos.end());
220
292
            }
221
293
        }
 
294
        int eq(Node *other) {
 
295
                NotCharSetNode *o = dynamic_cast<NotCharSetNode *>(other);
 
296
                if (!o || chars.size() != o->chars.size())
 
297
                        return 0;
 
298
 
 
299
                for (Chars::iterator i = chars.begin(), j = o->chars.begin();
 
300
                     i != chars.end() && j != o->chars.end();
 
301
                     i++, j++) {
 
302
                        if (*i != *j)
 
303
                                return 0;
 
304
                }
 
305
                return 1;
 
306
        }
222
307
        ostream& dump(ostream& os)
223
308
        {
224
309
            os << "[^";
231
316
    };
232
317
 
233
318
    /* Match any character (/./). */
234
 
    class AnyCharNode : public ImportantNode {
 
319
    class AnyCharNode : public CNode {
235
320
    public:
236
321
        AnyCharNode() { }
237
 
        void follow(Cases& cases)
 
322
        void follow(NodeCases& cases)
238
323
        {
239
324
            if (!cases.otherwise)
240
 
                cases.otherwise = new State;
 
325
                cases.otherwise = new NodeSet;
241
326
            cases.otherwise->insert(followpos.begin(), followpos.end());
242
 
            for (Cases::iterator i = cases.begin(); i != cases.end(); i++)
 
327
            for (NodeCases::iterator i = cases.begin(); i != cases.end(); i++)
243
328
                i->second->insert(followpos.begin(), followpos.end());
244
329
        }
 
330
        int eq(Node *other) {
 
331
                if (dynamic_cast<AnyCharNode *>(other))
 
332
                        return 1;
 
333
                return 0;
 
334
        }
245
335
        ostream& dump(ostream& os) {
246
336
            return os << ".";
247
337
        }
253
343
     */
254
344
    class AcceptNode : public ImportantNode {
255
345
    public:
256
 
        AcceptNode(uint32_t perms, int is_rerule)
257
 
            : perms(perms), is_rerule(is_rerule) {}
258
 
        void follow(Cases& cases)
 
346
        AcceptNode() {}
 
347
        void release(void)
 
348
        {
 
349
          /* don't delete AcceptNode via release as they are shared,
 
350
           * and will be deleted when the table the are stored in is deleted
 
351
           */
 
352
        }
 
353
 
 
354
        void follow(NodeCases& cases __attribute__((unused)))
259
355
        {
260
356
            /* Nothing to follow. */
261
357
        }
262
 
        ostream& dump(ostream& os) {
263
 
            return os << '<' << perms << ", " << is_rerule << '>';
264
 
        }
265
 
 
266
 
        uint32_t perms;
267
 
        int is_rerule;
268
 
    };
269
 
 
270
 
    /* Match a pair of consecutive nodes. */
271
 
    class CatNode : public Node {
272
 
    public:
273
 
        CatNode(Node *left, Node *right) :
274
 
            Node(left, right) { }
275
 
        void compute_nullable()
276
 
        {
277
 
            nullable = left->nullable && right->nullable;
278
 
        }
279
 
        void compute_firstpos()
280
 
        {
281
 
            if (left->nullable)
282
 
                firstpos = left->firstpos + right->firstpos;
283
 
            else
284
 
                firstpos = left->firstpos;
285
 
        }
286
 
        void compute_lastpos()
287
 
        {
288
 
            if (right->nullable)
289
 
                lastpos = left->lastpos + right->lastpos;
290
 
            else
291
 
                lastpos = right->lastpos;
292
 
        }
293
 
        void compute_followpos()
294
 
        {
295
 
            State from = left->lastpos, to = right->firstpos;
296
 
            for(State::iterator i = from.begin(); i != from.end(); i++) {
297
 
                (*i)->followpos.insert(to.begin(), to.end());
298
 
            }
299
 
        }
300
 
        ostream& dump(ostream& os)
301
 
        {
302
 
            return os;
303
 
            //return os << ' ';
 
358
        /* requires accept nodes to be common by pointer */
 
359
        int eq(Node *other) {
 
360
                if (dynamic_cast<AcceptNode *>(other))
 
361
                        return (this == other);
 
362
                return 0;
304
363
        }
305
364
    };
306
365
 
307
366
    /* Match a node zero or more times. (This is a unary operator.) */
308
 
    class StarNode : public Node {
 
367
    class StarNode : public OneChildNode {
309
368
    public:
310
369
        StarNode(Node *left) :
311
 
            Node(left)
 
370
            OneChildNode(left)
312
371
        {
313
372
            nullable = true;
314
373
        }
315
374
        void compute_firstpos()
316
375
        {
317
 
            firstpos = left->firstpos;
 
376
            firstpos = child[0]->firstpos;
318
377
        }
319
378
        void compute_lastpos()
320
379
        {
321
 
            lastpos = left->lastpos;
 
380
            lastpos = child[0]->lastpos;
322
381
        }
323
382
        void compute_followpos()
324
383
        {
325
 
            State from = left->lastpos, to = left->firstpos;
326
 
            for(State::iterator i = from.begin(); i != from.end(); i++) {
 
384
            NodeSet from = child[0]->lastpos, to = child[0]->firstpos;
 
385
            for(NodeSet::iterator i = from.begin(); i != from.end(); i++) {
327
386
                (*i)->followpos.insert(to.begin(), to.end());
328
387
            }
329
388
        }
 
389
        int eq(Node *other) {
 
390
                if (dynamic_cast<StarNode *>(other))
 
391
                        return child[0]->eq(other->child[0]);
 
392
                return 0;
 
393
        }
330
394
        ostream& dump(ostream& os)
331
395
        {
332
 
            return os << '*';
 
396
            os << '(';
 
397
            child[0]->dump(os);
 
398
            return os << ")*";
333
399
        }
334
400
    };
335
401
 
336
402
    /* Match a node one or more times. (This is a unary operator.) */
337
 
    class PlusNode : public Node {
 
403
    class PlusNode : public OneChildNode {
338
404
    public:
339
405
        PlusNode(Node *left) :
340
 
            Node(left) { }
341
 
        void compute_nullable()
342
 
        {
343
 
            nullable = left->nullable;
344
 
        }
345
 
        void compute_firstpos()
346
 
        {
347
 
            firstpos = left->firstpos;
348
 
        }
349
 
        void compute_lastpos()
350
 
        {
351
 
            lastpos = left->lastpos;
352
 
        }
353
 
        void compute_followpos()
354
 
        {
355
 
            State from = left->lastpos, to = left->firstpos;
356
 
            for(State::iterator i = from.begin(); i != from.end(); i++) {
357
 
                (*i)->followpos.insert(to.begin(), to.end());
358
 
            }
359
 
        }
360
 
        ostream& dump(ostream& os)
361
 
        {
362
 
            return os << '+';
 
406
            OneChildNode(left) { }
 
407
        void compute_nullable()
 
408
        {
 
409
            nullable = child[0]->nullable;
 
410
        }
 
411
        void compute_firstpos()
 
412
        {
 
413
            firstpos = child[0]->firstpos;
 
414
        }
 
415
        void compute_lastpos()
 
416
        {
 
417
            lastpos = child[0]->lastpos;
 
418
        }
 
419
        void compute_followpos()
 
420
        {
 
421
            NodeSet from = child[0]->lastpos, to = child[0]->firstpos;
 
422
            for(NodeSet::iterator i = from.begin(); i != from.end(); i++) {
 
423
                (*i)->followpos.insert(to.begin(), to.end());
 
424
            }
 
425
        }
 
426
        int eq(Node *other) {
 
427
                if (dynamic_cast<PlusNode *>(other))
 
428
                        return child[0]->eq(other->child[0]);
 
429
                return 0;
 
430
        }
 
431
        ostream& dump(ostream& os)
 
432
        {
 
433
            os << '(';
 
434
            child[0]->dump(os);
 
435
            return os << ")+";
 
436
        }
 
437
    };
 
438
 
 
439
    /* Match a pair of consecutive nodes. */
 
440
    class CatNode : public TwoChildNode {
 
441
    public:
 
442
        CatNode(Node *left, Node *right) :
 
443
            TwoChildNode(left, right) { }
 
444
        void compute_nullable()
 
445
        {
 
446
            nullable = child[0]->nullable && child[1]->nullable;
 
447
        }
 
448
        void compute_firstpos()
 
449
        {
 
450
            if (child[0]->nullable)
 
451
                firstpos = child[0]->firstpos + child[1]->firstpos;
 
452
            else
 
453
                firstpos = child[0]->firstpos;
 
454
        }
 
455
        void compute_lastpos()
 
456
        {
 
457
            if (child[1]->nullable)
 
458
                lastpos = child[0]->lastpos + child[1]->lastpos;
 
459
            else
 
460
                lastpos = child[1]->lastpos;
 
461
        }
 
462
        void compute_followpos()
 
463
        {
 
464
            NodeSet from = child[0]->lastpos, to = child[1]->firstpos;
 
465
            for(NodeSet::iterator i = from.begin(); i != from.end(); i++) {
 
466
                (*i)->followpos.insert(to.begin(), to.end());
 
467
            }
 
468
        }
 
469
        int eq(Node *other) {
 
470
                if (dynamic_cast<CatNode *>(other)) {
 
471
                        if (!child[0]->eq(other->child[0]))
 
472
                                return 0;
 
473
                        return child[1]->eq(other->child[1]);
 
474
                }
 
475
                return 0;
 
476
        }
 
477
        ostream& dump(ostream& os)
 
478
        {
 
479
            child[0]->dump(os);
 
480
            child[1]->dump(os);
 
481
            return os;
 
482
            //return os << ' ';
363
483
        }
364
484
    };
365
485
 
366
486
    /* Match one of two alternative nodes. */
367
 
    class AltNode : public Node {
 
487
    class AltNode : public TwoChildNode {
368
488
    public:
369
489
        AltNode(Node *left, Node *right) :
370
 
            Node(left, right) { }
 
490
            TwoChildNode(left, right) { }
371
491
        void compute_nullable()
372
492
        {
373
 
            nullable = left->nullable || right->nullable;
 
493
            nullable = child[0]->nullable || child[1]->nullable;
374
494
        }
375
495
        void compute_lastpos()
376
496
        {
377
 
            lastpos = left->lastpos + right->lastpos;
 
497
            lastpos = child[0]->lastpos + child[1]->lastpos;
378
498
        }
379
499
        void compute_firstpos()
380
500
        {
381
 
            firstpos = left->firstpos + right->firstpos;
 
501
            firstpos = child[0]->firstpos + child[1]->firstpos;
 
502
        }
 
503
        int eq(Node *other) {
 
504
                if (dynamic_cast<AltNode *>(other)) {
 
505
                        if (!child[0]->eq(other->child[0]))
 
506
                                return 0;
 
507
                        return child[1]->eq(other->child[1]);
 
508
                }
 
509
                return 0;
382
510
        }
383
511
        ostream& dump(ostream& os)
384
512
        {
385
 
            return os << '|';
 
513
            os << '(';
 
514
            child[0]->dump(os);
 
515
            os << '|';
 
516
            child[1]->dump(os);
 
517
            os << ')';
 
518
            return os;
386
519
        }
387
520
    };
 
521
 
 
522
/* Use a single static EpsNode as it carries no node specific information */
 
523
static EpsNode epsnode;
 
524
 
 
525
/*
 
526
 * Normalize the regex parse tree for factoring and cancelations. Normalization
 
527
 * reorganizes internal (alt and cat) nodes into a fixed "normalized" form that
 
528
 * simplifies factoring code, in that it produces a canonicalized form for
 
529
 * the direction being normalized so that the factoring code does not have
 
530
 * to consider as many cases.
 
531
 *
 
532
 * left normalization (dir == 0) uses these rules
 
533
 * (E | a) -> (a | E)
 
534
 * (a | b) | c -> a | (b | c)
 
535
 * (ab)c -> a(bc)
 
536
 *
 
537
 * right normalization (dir == 1) uses the same rules but reversed
 
538
 * (a | E) -> (E | a)
 
539
 * a | (b | c) -> (a | b) | c
 
540
 * a(bc) -> (ab)c
 
541
 *
 
542
 * Note: This is written iteratively for a given node (the top node stays
 
543
 *       fixed and the children are rotated) instead of recursively.
 
544
 *       For a given node under examination rotate over nodes from
 
545
 *       dir to !dir.   Until no dir direction node meets the criterial.
 
546
 *       Then recurse to the children (which will have a different node type)
 
547
 *       to make sure they are normalized.
 
548
 *       Normalization of a child node is guarenteed to not affect the
 
549
 *       normalization of the parent.
 
550
 *
 
551
 *       For cat nodes the depth first traverse order is guarenteed to be
 
552
 *       maintained.  This is not necessary for altnodes.
 
553
 *
 
554
 * Eg. For left normalization
 
555
 *
 
556
 *              |1               |1
 
557
 *             / \              / \
 
558
 *            |2  T     ->     a   |2
 
559
 *           / \                  / \
 
560
 *          |3  c                b   |3
 
561
 *         / \                      / \
 
562
 *        a   b                    c   T
 
563
 *
 
564
 */
 
565
static void rotate_node(Node *t, int dir) {
 
566
        // (a | b) | c -> a | (b | c)
 
567
        // (ab)c -> a(bc)
 
568
        Node *left = t->child[dir];
 
569
        t->child[dir] = left->child[dir];
 
570
        left->child[dir] = left->child[!dir];
 
571
        left->child[!dir] = t->child[!dir];
 
572
        t->child[!dir] = left;
 
573
}
 
574
 
 
575
void normalize_tree(Node *t, int dir)
 
576
{
 
577
        if (dynamic_cast<LeafNode *>(t))
 
578
                return;
 
579
 
 
580
        for (;;) {
 
581
                if ((&epsnode == t->child[dir]) &&
 
582
                    (&epsnode != t->child[!dir]) &&
 
583
                     dynamic_cast<TwoChildNode *>(t)) {
 
584
                        // (E | a) -> (a | E)
 
585
                        // Ea -> aE
 
586
                        Node *c = t->child[dir];
 
587
                        t->child[dir] = t->child[!dir];
 
588
                        t->child[!dir] = c;
 
589
                        // Don't break here as 'a' may be a tree that
 
590
                        // can be pulled up.
 
591
                } else if ((dynamic_cast<AltNode *>(t) &&
 
592
                            dynamic_cast<AltNode *>(t->child[dir])) ||
 
593
                           (dynamic_cast<CatNode *>(t) &&
 
594
                            dynamic_cast<CatNode *>(t->child[dir]))) {
 
595
                        // (a | b) | c -> a | (b | c)
 
596
                        // (ab)c -> a(bc)
 
597
                        rotate_node(t, dir);
 
598
                } else if (dynamic_cast<AltNode *>(t) &&
 
599
                           dynamic_cast<CharSetNode *>(t->child[dir]) &&
 
600
                           dynamic_cast<CharNode *>(t->child[!dir])) {
 
601
                        // [a] | b  ->  b | [a]
 
602
                        Node *c = t->child[dir];
 
603
                        t->child[dir] = t->child[!dir];
 
604
                        t->child[!dir] = c;
 
605
                } else {
 
606
                        break;
 
607
                }
 
608
        }
 
609
        if (t->child[dir])
 
610
                normalize_tree(t->child[dir], dir);
 
611
        if (t->child[!dir])
 
612
                normalize_tree(t->child[!dir], dir);
 
613
}
 
614
 
 
615
//charset conversion is disabled for now,
 
616
//it hinders tree optimization in some cases, so it need to be either
 
617
//done post optimization, or have extra factoring rules added
 
618
#if 0
 
619
static Node *merge_charset(Node *a, Node *b)
 
620
{
 
621
        if (dynamic_cast<CharNode *>(a) &&
 
622
            dynamic_cast<CharNode *>(b)) {
 
623
                Chars chars;
 
624
                chars.insert(dynamic_cast<CharNode *>(a)->c);
 
625
                chars.insert(dynamic_cast<CharNode *>(b)->c);
 
626
                CharSetNode *n = new CharSetNode(chars);
 
627
                return n;
 
628
        } else if (dynamic_cast<CharNode *>(a) &&
 
629
                   dynamic_cast<CharSetNode *>(b)) {
 
630
                Chars *chars = &dynamic_cast<CharSetNode *>(b)->chars;
 
631
                chars->insert(dynamic_cast<CharNode *>(a)->c);
 
632
                return b;
 
633
        } else if (dynamic_cast<CharSetNode *>(a) &&
 
634
                   dynamic_cast<CharSetNode *>(b)) {
 
635
                Chars *from = &dynamic_cast<CharSetNode *>(a)->chars;
 
636
                Chars *to = &dynamic_cast<CharSetNode *>(b)->chars;
 
637
                for (Chars::iterator i = from->begin(); i != from->end(); i++)
 
638
                        to->insert(*i);
 
639
                return b;
 
640
        }
 
641
 
 
642
        //return ???;
 
643
}
 
644
 
 
645
static Node *alt_to_charsets(Node *t, int dir)
 
646
{
 
647
/*
 
648
        Node *first = NULL;
 
649
        Node *p = t;
 
650
        Node *i = t;
 
651
        for (;dynamic_cast<AltNode *>(i);) {
 
652
                if (dynamic_cast<CharNode *>(i->child[dir]) ||
 
653
                    dynamic_cast<CharNodeSet *>(i->child[dir])) {
 
654
                        if (!first) {
 
655
                                first = i;
 
656
                                p = i;
 
657
                                i = i->child[!dir];
 
658
                        } else {
 
659
                                first->child[dir] = merge_charset(first->child[dir],
 
660
                                                      i->child[dir]);
 
661
                                p->child[!dir] = i->child[!dir];
 
662
                                Node *tmp = i;
 
663
                                i = tmp->child[!dir];
 
664
                                tmp->child[!dir] = NULL;
 
665
                                tmp->release();
 
666
                        }
 
667
                } else {
 
668
                        p = i;
 
669
                        i = i->child[!dir];
 
670
                }
 
671
        }
 
672
        // last altnode of chain check other dir as well
 
673
        if (first && (dynamic_cast<charNode *>(i) ||
 
674
                      dynamic_cast<charNodeSet *>(i))) {
 
675
                
 
676
        }
 
677
*/
 
678
 
 
679
/*
 
680
                if (dynamic_cast<CharNode *>(t->child[dir]) ||
 
681
                    dynamic_cast<CharSetNode *>(t->child[dir]))
 
682
                    char_test = true;
 
683
                            (char_test &&
 
684
                             (dynamic_cast<CharNode *>(i->child[dir]) ||
 
685
                              dynamic_cast<CharSetNode *>(i->child[dir])))) {
 
686
*/
 
687
        return t;
 
688
}
 
689
#endif
 
690
 
 
691
static Node *basic_alt_factor(Node *t, int dir)
 
692
{
 
693
        if (!dynamic_cast<AltNode *>(t))
 
694
                return t;
 
695
 
 
696
        if (t->child[dir]->eq(t->child[!dir])) {
 
697
                // (a | a) -> a
 
698
                Node *tmp = t->child[dir];
 
699
                t->child[dir] = NULL;
 
700
                t->release();
 
701
                return tmp;
 
702
        }
 
703
 
 
704
        // (ab) | (ac) -> a(b|c)
 
705
        if (dynamic_cast<CatNode *>(t->child[dir]) &&
 
706
            dynamic_cast<CatNode *>(t->child[!dir]) &&
 
707
            t->child[dir]->child[dir]->eq(t->child[!dir]->child[dir])) {
 
708
                // (ab) | (ac) -> a(b|c)
 
709
                Node *left = t->child[dir];
 
710
                Node *right = t->child[!dir];
 
711
                t->child[dir] = left->child[!dir];
 
712
                t->child[!dir] = right->child[!dir];
 
713
                right->child[!dir] = NULL;
 
714
                right->release();
 
715
                left->child[!dir] = t;
 
716
                return left;
 
717
        }
 
718
 
 
719
        // a | (ab) -> a (E | b) -> a (b | E)
 
720
        if (dynamic_cast<CatNode *>(t->child[!dir]) &&
 
721
            t->child[dir]->eq(t->child[!dir]->child[dir])) {
 
722
                Node *c = t->child[!dir];
 
723
                t->child[dir]->release();
 
724
                t->child[dir] = c->child[!dir];
 
725
                t->child[!dir] = &epsnode;
 
726
                c->child[!dir] = t;
 
727
                return c;
 
728
        }
 
729
 
 
730
        // ab | (a) -> a (b | E)
 
731
        if (dynamic_cast<CatNode *>(t->child[dir]) &&
 
732
            t->child[dir]->child[dir]->eq(t->child[!dir])) {
 
733
                Node *c = t->child[dir];
 
734
                t->child[!dir]->release();
 
735
                t->child[dir] = c->child[!dir];
 
736
                t->child[!dir] = &epsnode;
 
737
                c->child[!dir] = t;
 
738
                return c;
 
739
        }
 
740
 
 
741
        return t;
 
742
}
 
743
 
 
744
static Node *basic_simplify(Node *t, int dir)
 
745
{
 
746
        if (dynamic_cast<CatNode *>(t) &&
 
747
            &epsnode == t->child[!dir]) {
 
748
                // aE -> a
 
749
                Node *tmp = t->child[dir];
 
750
                t->child[dir] = NULL;
 
751
                t->release();
 
752
                return tmp;
 
753
        }
 
754
 
 
755
        return basic_alt_factor(t, dir);
 
756
}
 
757
 
 
758
/*
 
759
 * assumes a normalized tree.  reductions shown for left normalization
 
760
 * aE -> a
 
761
 * (a | a) -> a
 
762
 ** factoring patterns
 
763
 * a | (a | b) -> (a | b)
 
764
 * a | (ab) -> a (E | b) -> a (b | E)
 
765
 * (ab) | (ac) -> a(b|c)
 
766
 *
 
767
 * returns t - if no simplifications were made
 
768
 *         a new root node - if simplifications were made
 
769
 */
 
770
Node *simplify_tree_base(Node *t, int dir, bool &mod)
 
771
{
 
772
        if (dynamic_cast<ImportantNode *>(t))
 
773
                return t;
 
774
 
 
775
        for (int i=0; i < 2; i++) {
 
776
                if (t->child[i]) {
 
777
                        Node *c = simplify_tree_base(t->child[i], dir, mod);
 
778
                        if (c != t->child[i]) {
 
779
                                t->child[i] = c;
 
780
                                mod = true;
 
781
                        }
 
782
                }
 
783
        }
 
784
 
 
785
        // only iterate on loop if modification made
 
786
        for (;; mod = true) {
 
787
 
 
788
                Node *tmp = basic_simplify(t, dir);
 
789
                if (tmp != t) {
 
790
                        t = tmp;
 
791
                        continue;
 
792
                }
 
793
 
 
794
 
 
795
                /* all tests after this must meet 2 alt node condition */
 
796
                if (!dynamic_cast<AltNode *>(t) ||
 
797
                    !dynamic_cast<AltNode *>(t->child[!dir]))
 
798
                        break;
 
799
 
 
800
                // a | (a | b) -> (a | b)
 
801
                // a | (b | (c | a)) -> (b | (c | a))
 
802
                Node *p = t;
 
803
                Node *i = t->child[!dir];
 
804
                for (;dynamic_cast<AltNode *>(i); p = i, i = i->child[!dir]) {
 
805
                        if (t->child[dir]->eq(i->child[dir])) {
 
806
                                Node *tmp = t->child[!dir];
 
807
                                t->child[!dir] = NULL;
 
808
                                t->release();
 
809
                                t = tmp;
 
810
                                continue;
 
811
                        }
 
812
                }
 
813
                // last altnode of chain check other dir as well
 
814
                if (t->child[dir]->eq(p->child[!dir])) {
 
815
                        Node *tmp = t->child[!dir];
 
816
                        t->child[!dir] = NULL;
 
817
                        t->release();
 
818
                        t = tmp;
 
819
                        continue;
 
820
                }
 
821
 
 
822
                //exact match didn't work, try factoring front
 
823
                //a | (ac | (ad | () -> (a (E | c)) | (...)
 
824
                //ab | (ac | (...)) -> (a (b | c)) | (...)
 
825
                //ab | (a | (...)) -> (a (b | E)) | (...)
 
826
                Node *pp;
 
827
                int count = 0;
 
828
                Node *subject = t->child[dir];
 
829
                Node *a = subject;
 
830
                if (dynamic_cast<CatNode *>(subject))
 
831
                    a = subject->child[dir];
 
832
 
 
833
                for (pp = p = t, i = t->child[!dir];
 
834
                     dynamic_cast<AltNode *>(i); ) {
 
835
                        if ((dynamic_cast<CatNode *>(i->child[dir]) &&
 
836
                             a->eq(i->child[dir]->child[dir])) ||
 
837
                            (a->eq(i->child[dir]))) {
 
838
                                // extract matching alt node
 
839
                                p->child[!dir] = i->child[!dir];
 
840
                                i->child[!dir] = subject;
 
841
                                subject = basic_simplify(i, dir);
 
842
                                if (dynamic_cast<CatNode *>(subject))
 
843
                                        a = subject->child[dir];
 
844
                                else
 
845
                                        a = subject;
 
846
 
 
847
                                i = p->child[!dir];
 
848
                                count++;
 
849
                        } else {
 
850
                                pp = p; p = i; i = i->child[!dir];
 
851
                        }
 
852
                }
 
853
 
 
854
                // last altnode in chain check other dir as well
 
855
                if ((dynamic_cast<CatNode *>(i) &&
 
856
                     a->eq(i->child[dir])) ||
 
857
                    (a->eq(i))) {
 
858
                        count++;
 
859
                        if (t == p) {
 
860
                                t->child[dir] = subject;
 
861
                                t = basic_simplify(t, dir);
 
862
                        } else {
 
863
                                t->child[dir] = p->child[dir];
 
864
                                p->child[dir] = subject;
 
865
                                pp->child[!dir] = basic_simplify(p, dir);
 
866
                        }
 
867
                } else {
 
868
                        t->child[dir] = i;
 
869
                        p->child[!dir] = subject;
 
870
                }
 
871
 
 
872
                if (count == 0)
 
873
                        break;
 
874
        }
 
875
        return t;
 
876
}
 
877
 
 
878
int debug_tree(Node *t)
 
879
{
 
880
        int nodes = 1;
 
881
 
 
882
        if (!dynamic_cast<ImportantNode *>(t)) {
 
883
                if (t->child[0])
 
884
                        nodes += debug_tree(t->child[0]);
 
885
                if (t->child[1])
 
886
                        nodes += debug_tree(t->child[1]);
 
887
        }
 
888
        return nodes;
 
889
}
 
890
 
 
891
struct node_counts {
 
892
        int charnode;
 
893
        int charset;
 
894
        int notcharset;
 
895
        int alt;
 
896
        int plus;
 
897
        int star;
 
898
        int any;
 
899
        int cat;
 
900
};
 
901
 
 
902
 
 
903
static void count_tree_nodes(Node *t, struct node_counts *counts)
 
904
{
 
905
        if (dynamic_cast<AltNode *>(t)) {
 
906
                counts->alt++;
 
907
                count_tree_nodes(t->child[0], counts);
 
908
                count_tree_nodes(t->child[1], counts);
 
909
        } else if (dynamic_cast<CatNode *>(t)) {
 
910
                counts->cat++;
 
911
                count_tree_nodes(t->child[0], counts);
 
912
                count_tree_nodes(t->child[1], counts);
 
913
        } else if (dynamic_cast<PlusNode *>(t)) {
 
914
                counts->plus++;
 
915
                count_tree_nodes(t->child[0], counts);
 
916
        } else if (dynamic_cast<StarNode *>(t)) {
 
917
                counts->star++;
 
918
                count_tree_nodes(t->child[0], counts);
 
919
        } else if (dynamic_cast<CharNode *>(t)) {
 
920
                counts->charnode++;
 
921
        } else if (dynamic_cast<AnyCharNode *>(t)) {
 
922
                counts->any++;
 
923
        } else if (dynamic_cast<CharSetNode *>(t)) {
 
924
                counts->charset++;
 
925
        } else if (dynamic_cast<NotCharSetNode *>(t)) {
 
926
                counts->notcharset++;
 
927
        }
 
928
}
 
929
 
 
930
#include "stdio.h"
 
931
#include "stdint.h"
 
932
#include "apparmor_re.h"
 
933
 
 
934
Node *simplify_tree(Node *t, dfaflags_t flags)
 
935
{
 
936
        bool update;
 
937
 
 
938
        if (flags & DFA_DUMP_TREE_STATS) {
 
939
                struct node_counts counts = { 0, 0, 0, 0, 0, 0, 0, 0 };
 
940
                count_tree_nodes(t, &counts);
 
941
                fprintf(stderr, "expr tree: c %d, [] %d, [^] %d, | %d, + %d, * %d, . %d, cat %d\n", counts.charnode, counts.charset, counts.notcharset, counts.alt, counts.plus, counts.star, counts.any, counts.cat);
 
942
        }
 
943
        do {
 
944
                update = false;
 
945
                //default to right normalize first as this reduces the number
 
946
                //of trailing nodes which might follow an internal *
 
947
                //or **, which is where state explosion can happen
 
948
                //eg. in one test this makes the difference between
 
949
                //    the dfa having about 7 thousands states,
 
950
                //    and it having about  1.25 million states
 
951
                int dir = 1;
 
952
                if (flags & DFA_CONTROL_TREE_LEFT)
 
953
                        dir = 0;
 
954
                for (int count = 0; count < 2; count++) {
 
955
                        bool modified;
 
956
                        do {
 
957
                            modified = false;
 
958
                            if (flags & DFA_CONTROL_TREE_NORMAL)
 
959
                                normalize_tree(t, dir);
 
960
                            t = simplify_tree_base(t, dir, modified);
 
961
                            if (modified)
 
962
                                update = true;
 
963
                        } while (modified);
 
964
                        if (flags & DFA_CONTROL_TREE_LEFT)
 
965
                                dir++;
 
966
                        else
 
967
                                dir--;
 
968
                }
 
969
        } while(update);
 
970
        if (flags & DFA_DUMP_TREE_STATS) {
 
971
                struct node_counts counts = { 0, 0, 0, 0, 0, 0, 0, 0 };
 
972
                count_tree_nodes(t, &counts);
 
973
                fprintf(stderr, "simplified expr tree: c %d, [] %d, [^] %d, | %d, + %d, * %d, . %d, cat %d\n", counts.charnode, counts.charset, counts.notcharset, counts.alt, counts.plus, counts.star, counts.any, counts.cat);
 
974
        }
 
975
        return t;
 
976
}
 
977
 
 
978
 
388
979
%}
389
980
 
390
981
%union {
394
985
}
395
986
 
396
987
%{
397
 
    void regexp_error(Node **, const char *, int *, const char *);
 
988
    void regexp_error(Node **, const char *, const char *);
398
989
#   define YYLEX_PARAM &text
399
990
    int regexp_lex(YYSTYPE *, const char **);
400
991
 
420
1011
/* %error-verbose */
421
1012
%parse-param {Node **root}
422
1013
%parse-param {const char *text}
423
 
%parse-param {int *is_rerule}
424
1014
%name-prefix = "regexp_"
425
1015
 
426
1016
%token <c> CHAR
440
1030
          which precise grammer Perl regexps use, and rediscovering that
441
1031
          is proving to be painful. */
442
1032
 
443
 
regexp      : /* empty */       { *root = $$ = new EpsNode; }
 
1033
regexp      : /* empty */       { *root = $$ = &epsnode; }
444
1034
            | expr              { *root = $$ = $1; }
445
1035
            ;
446
1036
 
447
1037
expr        : terms
448
1038
            | expr '|' terms0   { $$ = new AltNode($1, $3); }
449
 
            | '|' terms0        { $$ = new AltNode(new EpsNode, $2); }
 
1039
            | '|' terms0        { $$ = new AltNode(&epsnode, $2); }
450
1040
            ;
451
1041
 
452
 
terms0      : /* empty */       { $$ = new EpsNode; }
 
1042
terms0      : /* empty */       { $$ = &epsnode; }
453
1043
            | terms
454
1044
            ;
455
1045
 
458
1048
            ;
459
1049
 
460
1050
qterm       : term
461
 
            | term '*'          { $$ = new StarNode($1); *is_rerule = 1; }
462
 
            | term '+'          { $$ = new PlusNode($1); *is_rerule = 1; }
 
1051
            | term '*'          { $$ = new StarNode($1); }
 
1052
            | term '+'          { $$ = new PlusNode($1); }
463
1053
            ;
464
1054
 
465
 
term        : '.'               { $$ = new AnyCharNode; *is_rerule = 1; }
 
1055
term        : '.'               { $$ = new AnyCharNode; }
466
1056
            | regex_char        { $$ = new CharNode($1); }
467
1057
            | '[' charset ']'   { $$ = new CharSetNode(*$2);
468
 
                                  delete $2; *is_rerule = 1; }
 
1058
                                  delete $2; }
469
1059
            | '[' '^' charset ']'
470
1060
                                { $$ = new NotCharSetNode(*$3);
471
 
                                  delete $3; *is_rerule = 1; }
 
1061
                                  delete $3; }
472
1062
            | '[' '^' '^' cset_chars ']'
473
1063
                                { $4->insert('^');
474
1064
                                  $$ = new NotCharSetNode(*$4);
475
 
                                  delete $4; *is_rerule = 1; }
 
1065
                                  delete $4; }
476
1066
            | '(' regexp ')'    { $$ = $2; }
477
1067
            ;
478
1068
 
526
1116
 
527
1117
#include "../immunix.h"
528
1118
 
529
 
#define NOT_RE_RULE 0
530
 
 
531
1119
/* Traverse the syntax tree depth-first in an iterator-like manner. */
532
1120
class depth_first_traversal {
533
 
    vector<Node *> stack;
534
 
    vector<bool> visited;
 
1121
    stack<Node *> pos;
 
1122
    void push_left(Node *node)
 
1123
    {
 
1124
        pos.push(node);
 
1125
 
 
1126
        while (dynamic_cast<InnerNode *>(node)) {
 
1127
            pos.push(node->child[0]);
 
1128
            node = node->child[0];
 
1129
        }
 
1130
    }
 
1131
 
535
1132
public:
536
1133
    depth_first_traversal(Node *node) {
537
 
        stack.push_back(node);
538
 
        while (node->left) {
539
 
            visited.push_back(false);
540
 
            stack.push_back(node->left);
541
 
            node = node->left;
542
 
        }
 
1134
        push_left(node);
543
1135
    }
544
1136
    Node *operator*()
545
1137
    {
546
 
        return stack.back();
 
1138
        return pos.top();
547
1139
    }
548
1140
    Node* operator->()
549
1141
    {
550
 
        return stack.back();
 
1142
        return pos.top();
551
1143
    }
552
1144
    operator bool()
553
1145
    {
554
 
        return !stack.empty();
 
1146
        return !pos.empty();
555
1147
    }
556
1148
    void operator++(int)
557
1149
    {
558
 
        stack.pop_back();
559
 
        if (!stack.empty()) {
560
 
            if (!visited.back() && stack.back()->right) {
561
 
                visited.pop_back();
562
 
                visited.push_back(true);
563
 
                stack.push_back(stack.back()->right);
564
 
                while (stack.back()->left) {
565
 
                    visited.push_back(false);
566
 
                    stack.push_back(stack.back()->left);
567
 
                }
568
 
            } else
569
 
                visited.pop_back();
 
1150
        Node *last = pos.top();
 
1151
        pos.pop();
 
1152
 
 
1153
        if (!pos.empty()) {
 
1154
            /* no need to dynamic cast, as we just popped a node so the top node
 
1155
             * must be an inner node */
 
1156
            InnerNode *node = (InnerNode *)(pos.top());
 
1157
 
 
1158
            if (node->child[1] && node->child[1] != last) {
 
1159
                push_left(node->child[1]);
 
1160
            }
570
1161
        }
571
1162
    }
572
1163
};
633
1224
            switch(*(*pos)++) {
634
1225
                case '\0':
635
1226
                    (*pos)--;
 
1227
                    /* fall through */
 
1228
                case '\\':
636
1229
                    val->c = '\\';
637
1230
                    break;
638
1231
 
693
1286
}
694
1287
 
695
1288
void
696
 
regexp_error(Node **, const char *text, int *is_rerule, const char *error)
 
1289
regexp_error(Node ** __attribute__((unused)),
 
1290
             const char *text __attribute__((unused)),
 
1291
             const char *error __attribute__((unused)))
697
1292
{
698
1293
    /* We don't want the library to print error messages. */
699
1294
}
701
1296
/**
702
1297
 * Assign a consecutive number to each node. This is only needed for
703
1298
 * pretty-printing the debug output.
 
1299
 *
 
1300
 * The epsnode is labeled 0.  Start labeling at 1
704
1301
 */
705
 
map<Node *, int> node_label;
706
1302
void label_nodes(Node *root)
707
1303
{
708
 
    int nodes = 0;
 
1304
    int nodes = 1;
709
1305
    for (depth_first_traversal i(root); i; i++)
710
 
        node_label.insert(make_pair(*i, nodes++));
 
1306
       i->label = nodes++;
711
1307
}
712
1308
 
713
1309
/**
714
1310
 * Text-dump a state (for debugging).
715
1311
 */
716
 
ostream& operator<<(ostream& os, const State& state)
 
1312
ostream& operator<<(ostream& os, const NodeSet& state)
717
1313
{
718
1314
    os << '{';
719
1315
    if (!state.empty()) {
720
 
        State::iterator i = state.begin();
 
1316
        NodeSet::iterator i = state.begin();
721
1317
        for(;;) {
722
 
            os << node_label[*i];
 
1318
           os << (*i)->label;
723
1319
            if (++i == state.end())
724
1320
                break;
725
1321
            os << ',';
734
1330
 */
735
1331
void dump_syntax_tree(ostream& os, Node *node) {
736
1332
    for (depth_first_traversal i(node); i; i++) {
737
 
        os << node_label[*i] << '\t';
738
 
        if ((*i)->left == 0)
 
1333
        os << i->label << '\t';
 
1334
        if ((*i)->child[0] == 0)
739
1335
            os << **i << '\t' << (*i)->followpos << endl;
740
1336
        else {
741
 
            if ((*i)->right == 0)
742
 
                os << node_label[(*i)->left] << **i;
 
1337
            if ((*i)->child[1] == 0)
 
1338
                os << (*i)->child[0]->label << **i;
743
1339
            else
744
 
                os << node_label[(*i)->left] << **i
745
 
                   << node_label[(*i)->right];
 
1340
                os << (*i)->child[0]->label << **i
 
1341
                   << (*i)->child[1]->label;
746
1342
            os << '\t' << (*i)->firstpos
747
1343
                       << (*i)->lastpos << endl;
748
1344
        }
750
1346
    os << endl;
751
1347
}
752
1348
 
753
 
/* Comparison operator for sets of <State *>. */
754
 
template<class T>
755
 
class deref_less_than {
 
1349
/* Comparison operator for sets of <NodeSet *>.
 
1350
 * Compare set hashes, and if the sets have the same hash
 
1351
 * do compare pointer comparison on set of <Node *>, the pointer comparison
 
1352
 * allows us to determine which Sets of <Node *> we have seen already from
 
1353
 * new ones when constructing the DFA.
 
1354
 */
 
1355
struct deref_less_than {
 
1356
  bool operator()(pair <unsigned long, NodeSet *> const & lhs, pair <unsigned long, NodeSet *> const & rhs) const
 
1357
  {
 
1358
          if (lhs.first == rhs.first)
 
1359
                  return *(lhs.second) < *(rhs.second);
 
1360
          else
 
1361
                  return lhs.first < rhs.first;
 
1362
  }
 
1363
};
 
1364
 
 
1365
unsigned long hash_NodeSet(const NodeSet *ns)
 
1366
{
 
1367
        unsigned long hash = 5381;
 
1368
 
 
1369
        for (NodeSet::iterator i = ns->begin(); i != ns->end(); i++) {
 
1370
          hash = ((hash << 5) + hash) + (unsigned long) *i;
 
1371
        }
 
1372
 
 
1373
        return hash;
 
1374
}
 
1375
 
 
1376
class State;
 
1377
/**
 
1378
 * State cases are identical to NodesCases except they map to State *
 
1379
 * instead of NodeSet.
 
1380
 * Out-edges from a state to another: we store the follow State
 
1381
 * for each input character that is not a default match in  cases and
 
1382
 * default matches in otherwise as well as in all matching explicit cases
 
1383
 * This avoids enumerating all the explicit tranitions for default matches.
 
1384
 */
 
1385
typedef struct Cases {
 
1386
        typedef map<uchar, State *>::iterator iterator;
 
1387
        iterator begin() { return cases.begin(); }
 
1388
        iterator end() { return cases.end(); }
 
1389
 
 
1390
        Cases() : otherwise(0) { }
 
1391
        map<uchar, State *> cases;
 
1392
        State *otherwise;
 
1393
} Cases;
 
1394
 
 
1395
typedef list<State *> Partition;
 
1396
 
 
1397
uint32_t accept_perms(NodeSet *state, uint32_t *audit_ctl, int *error);
 
1398
 
 
1399
/*
 
1400
 * State - DFA individual state information
 
1401
 * label: a unique label to identify the state used for pretty printing
 
1402
 *        the non-matching state is setup to have label == 0 and
 
1403
 *        the start state is setup to have label == 1
 
1404
 * audit: the audit permission mask for the state
 
1405
 * accept: the accept permissions for the state
 
1406
 * cases: set of transitions from this state
 
1407
 * parition: Is a temporary work variable used during dfa minimization.
 
1408
 *           it can be replaced with a map, but that is slower and uses more
 
1409
 *           memory.
 
1410
 * nodes: Is a temporary work variable used during dfa creation.  It can
 
1411
 *        be replaced by using the nodemap, but that is slower
 
1412
 */
 
1413
class State {
756
1414
public:
757
 
    deref_less_than() { }
758
 
    bool operator()(T a, T b)
759
 
    {
760
 
        return *a < *b;
761
 
    }
 
1415
        State() : label (0), audit(0), accept(0), cases(), nodes(NULL) { };
 
1416
        State(int l): label (l), audit(0), accept(0), cases(), nodes(NULL) { };
 
1417
        State(int l, NodeSet *n) throw (int):
 
1418
                label(l), audit(0), accept(0), cases(), nodes(n)
 
1419
        {
 
1420
                int error;
 
1421
 
 
1422
                /* Compute permissions associated with the State. */
 
1423
                accept = accept_perms(nodes, &audit, &error);
 
1424
                if (error) {
 
1425
cerr << "Failing on accept perms " << error << "\n";
 
1426
                        throw error;
 
1427
                }
 
1428
        };
 
1429
 
 
1430
        int label;
 
1431
        uint32_t audit, accept;
 
1432
        Cases cases;
 
1433
        union {
 
1434
                Partition *partition;
 
1435
                NodeSet *nodes;
 
1436
        };
762
1437
};
763
1438
 
764
 
/**
765
 
 * States in the DFA. The pointer comparison allows us to tell sets we
766
 
 * have seen already from new ones when constructing the DFA.
767
 
 */
768
 
typedef set<State *, deref_less_than<State *> > States;
 
1439
ostream& operator<<(ostream& os, const State& state)
 
1440
{
 
1441
        /* dump the state label */
 
1442
        os << '{';
 
1443
        os << state.label;
 
1444
        os << '}';
 
1445
        return os;
 
1446
}
 
1447
 
 
1448
typedef map<pair<unsigned long, NodeSet *>, State *, deref_less_than > NodeMap;
769
1449
/* Transitions in the DFA. */
770
 
typedef map<State *, Cases> Trans;
 
1450
 
 
1451
/* dfa_stats - structure to group various stats about dfa creation
 
1452
 * duplicates - how many duplicate NodeSets where encountered and discarded
 
1453
 * proto_max - maximum length of a NodeSet encountered during dfa construction
 
1454
 * proto_sum - sum of NodeSet length during dfa construction.  Used to find
 
1455
 *             average length.
 
1456
 */
 
1457
typedef struct dfa_stats {
 
1458
        unsigned int duplicates, proto_max, proto_sum;
 
1459
} dfa_stats_t;
771
1460
 
772
1461
class DFA {
 
1462
    void dump_node_to_dfa(void);
 
1463
    State* add_new_state(NodeMap &nodemap, pair <unsigned long, NodeSet *> index, NodeSet *nodes, dfa_stats_t &stats);
 
1464
    void update_state_transitions(NodeMap &nodemap, list <State *> &work_queue, State *state, dfa_stats_t &stats);
 
1465
    State *find_target_state(NodeMap &nodemap, list <State *> &work_queue,
 
1466
                             NodeSet *nodes, dfa_stats_t &stats);
773
1467
public:
774
 
    DFA(Node *root);
 
1468
    DFA(Node *root, dfaflags_t flags);
775
1469
    virtual ~DFA();
 
1470
    void remove_unreachable(dfaflags_t flags);
 
1471
    bool same_mappings(State *s1, State *s2);
 
1472
    size_t hash_trans(State *s);
 
1473
    void minimize(dfaflags_t flags);
776
1474
    void dump(ostream& os);
777
1475
    void dump_dot_graph(ostream& os);
778
 
    map<uchar, uchar> equivalence_classes();
 
1476
    void dump_uniq_perms(const char *s);
 
1477
    map<uchar, uchar> equivalence_classes(dfaflags_t flags);
779
1478
    void apply_equivalence_classes(map<uchar, uchar>& eq);
780
 
    State *verify_perms(void);
781
1479
    Node *root;
782
1480
    State *nonmatching, *start;
783
 
    States states;
784
 
    Trans trans;
 
1481
    Partition states;
785
1482
};
786
1483
 
 
1484
State* DFA::add_new_state(NodeMap &nodemap, pair <unsigned long, NodeSet *> index, NodeSet *nodes, dfa_stats_t &stats)
 
1485
{
 
1486
        State *state = new State(nodemap.size(), nodes);
 
1487
        states.push_back(state);
 
1488
        nodemap.insert(make_pair(index, state));
 
1489
        stats.proto_sum += nodes->size();
 
1490
        if (nodes->size() > stats.proto_max)
 
1491
                stats.proto_max = nodes->size();
 
1492
        return state;
 
1493
}
 
1494
 
 
1495
State *DFA::find_target_state(NodeMap &nodemap, list <State *> &work_queue,
 
1496
                              NodeSet *nodes, dfa_stats_t &stats)
 
1497
{
 
1498
        State *target;
 
1499
 
 
1500
        pair <unsigned long, NodeSet *> index = make_pair(hash_NodeSet(nodes), nodes);
 
1501
 
 
1502
        map<pair <unsigned long, NodeSet *>, State *, deref_less_than>::iterator x = nodemap.find(index);
 
1503
 
 
1504
        if (x == nodemap.end()) {
 
1505
                /* set of nodes isn't known so create new state, and nodes to
 
1506
                 * state mapping
 
1507
                 */
 
1508
                target = add_new_state(nodemap, index, nodes, stats);
 
1509
                work_queue.push_back(target);
 
1510
        } else {
 
1511
                /* set of nodes already has a mapping so free this one */
 
1512
                stats.duplicates++;
 
1513
                delete (nodes);
 
1514
                target = x->second;
 
1515
        }
 
1516
 
 
1517
        return target;
 
1518
}
 
1519
 
 
1520
void DFA::update_state_transitions(NodeMap &nodemap,
 
1521
                                   list <State *> &work_queue, State *state,
 
1522
                                   dfa_stats_t &stats)
 
1523
{
 
1524
        /* Compute possible transitions for state->nodes.  This is done by
 
1525
         * iterating over all the nodes in state->nodes and combining the
 
1526
         * transitions.
 
1527
         *
 
1528
         * The resultant transition set is a mapping of characters to
 
1529
         * sets of nodes.
 
1530
         */
 
1531
        NodeCases cases;
 
1532
        for (NodeSet::iterator i = state->nodes->begin(); i != state->nodes->end(); i++)
 
1533
                (*i)->follow(cases);
 
1534
 
 
1535
        /* Now for each set of nodes in the computed transitions, make
 
1536
         * sure that there is a state that maps to it, and add the
 
1537
         * matching case to the state.
 
1538
         */
 
1539
 
 
1540
        /* check the default transition first */
 
1541
        if (cases.otherwise)
 
1542
                state->cases.otherwise = find_target_state(nodemap, work_queue,
 
1543
                                                           cases.otherwise,
 
1544
                                                           stats);;
 
1545
 
 
1546
        /* For each transition from *from, check if the set of nodes it
 
1547
         * transitions to already has been mapped to a state
 
1548
         */
 
1549
        for (NodeCases::iterator j = cases.begin(); j != cases.end(); j++) {
 
1550
                State *target;
 
1551
                target = find_target_state(nodemap, work_queue, j->second,
 
1552
                                           stats);
 
1553
 
 
1554
                /* Don't insert transition that the default transition
 
1555
                 * already covers
 
1556
                 */
 
1557
                if (target != state->cases.otherwise)
 
1558
                        state->cases.cases[j->first] = target;
 
1559
        }
 
1560
}
 
1561
 
 
1562
 
 
1563
/* WARNING: This routine can only be called from within DFA creation as
 
1564
 * the nodes value is only valid during dfa construction.
 
1565
 */
 
1566
void DFA::dump_node_to_dfa(void)
 
1567
{
 
1568
        cerr << "Mapping of States to expr nodes\n"
 
1569
                "  State  <=   Nodes\n"
 
1570
                "-------------------\n";
 
1571
        for (Partition::iterator i = states.begin(); i != states.end(); i++)
 
1572
                cerr << "  " << (*i)->label << " <= " << *(*i)->nodes << "\n";
 
1573
}
 
1574
 
787
1575
/**
788
1576
 * Construct a DFA from a syntax tree.
789
1577
 */
790
 
DFA::DFA(Node *root) : root(root)
 
1578
DFA::DFA(Node *root, dfaflags_t flags) : root(root)
791
1579
{
792
 
    for (depth_first_traversal i(root); i; i++) {
793
 
        (*i)->compute_nullable();
794
 
        (*i)->compute_firstpos();
795
 
        (*i)->compute_lastpos();
796
 
    }
797
 
    for (depth_first_traversal i(root); i; i++) {
798
 
        (*i)->compute_followpos();
799
 
    }
800
 
 
801
 
    nonmatching = new State;
802
 
    states.insert(nonmatching);
803
 
 
804
 
    start = new State(root->firstpos);
805
 
    states.insert(start);
806
 
 
807
 
    list<State *> work_queue;
808
 
    work_queue.push_back(start);
809
 
    while (!work_queue.empty()) {
810
 
        State *from = work_queue.front();
811
 
        work_queue.pop_front();
812
 
        Cases cases;
813
 
        for (State::iterator i = from->begin(); i != from->end(); i++)
814
 
            (*i)->follow(cases);
815
 
        if (cases.otherwise) {
816
 
            pair <States::iterator, bool> x = states.insert(cases.otherwise);
817
 
            if (x.second)
818
 
                work_queue.push_back(cases.otherwise);
819
 
            else {
820
 
                delete cases.otherwise;
821
 
                cases.otherwise = *x.first;
822
 
            }
823
 
        }
824
 
        for (Cases::iterator j = cases.begin(); j != cases.end(); j++) {
825
 
            pair <States::iterator, bool> x = states.insert(j->second);
826
 
            if (x.second)
827
 
                work_queue.push_back(*x.first);
828
 
            else {
829
 
                delete j->second;
830
 
                j->second = *x.first;
831
 
            }
832
 
        }
833
 
        Cases& here = trans.insert(make_pair(from, Cases())).first->second;
834
 
        here.otherwise = cases.otherwise;
835
 
        for (Cases::iterator j = cases.begin(); j != cases.end(); j++) {
836
 
            /**
837
 
             * Do not insert transitions that the default transition already
838
 
             * covers.
839
 
             */
840
 
            if (j->second != cases.otherwise)
841
 
                here.cases.insert(*j);
842
 
        }
843
 
    }
 
1580
        dfa_stats_t stats = { 0, 0, 0 };
 
1581
        int i = 0;
 
1582
 
 
1583
        if (flags & DFA_DUMP_PROGRESS)
 
1584
                fprintf(stderr, "Creating dfa:\r");
 
1585
 
 
1586
        for (depth_first_traversal i(root); i; i++) {
 
1587
                (*i)->compute_nullable();
 
1588
                (*i)->compute_firstpos();
 
1589
                (*i)->compute_lastpos();
 
1590
        }
 
1591
 
 
1592
        if (flags & DFA_DUMP_PROGRESS)
 
1593
                fprintf(stderr, "Creating dfa: followpos\r");
 
1594
        for (depth_first_traversal i(root); i; i++) {
 
1595
                (*i)->compute_followpos();
 
1596
        }
 
1597
 
 
1598
        NodeMap nodemap;
 
1599
        NodeSet *emptynode = new NodeSet;
 
1600
        nonmatching = add_new_state(nodemap,
 
1601
                                  make_pair(hash_NodeSet(emptynode), emptynode),
 
1602
                                    emptynode, stats);
 
1603
 
 
1604
        NodeSet *first = new NodeSet(root->firstpos);
 
1605
        start = add_new_state(nodemap, make_pair(hash_NodeSet(first), first),
 
1606
                              first, stats);
 
1607
 
 
1608
        /* the work_queue contains the states that need to have their
 
1609
         * transitions computed.  This could be done with a recursive
 
1610
         * algorithm instead of a work_queue, but it would be slightly slower
 
1611
         * and consume more memory.
 
1612
         *
 
1613
         * TODO: currently the work_queue is treated in a breadth first
 
1614
         *       search manner.  Test using the work_queue in a depth first
 
1615
         *       manner, this may help reduce the number of entries on the
 
1616
         *       work_queue at any given time, thus reducing peak memory use.
 
1617
         */
 
1618
        list<State *> work_queue;
 
1619
        work_queue.push_back(start);
 
1620
 
 
1621
        while (!work_queue.empty()) {
 
1622
                if (i % 1000 == 0 && (flags & DFA_DUMP_PROGRESS))
 
1623
                        fprintf(stderr, "\033[2KCreating dfa: queue %ld\tstates %ld\teliminated duplicates %d\r", work_queue.size(), states.size(), stats.duplicates);
 
1624
                i++;
 
1625
 
 
1626
                State *from = work_queue.front();
 
1627
                work_queue.pop_front();
 
1628
 
 
1629
                /* Update 'from's transitions, and if it transitions to any
 
1630
                 * unknown State create it and add it to the work_queue
 
1631
                 */
 
1632
                update_state_transitions(nodemap, work_queue, from, stats);
 
1633
 
 
1634
        } /* for (NodeSet *nodes ... */
 
1635
 
 
1636
        /* cleanup Sets of nodes used computing the DFA as they are no longer
 
1637
         * needed.
 
1638
         */
 
1639
        for (depth_first_traversal i(root); i; i++) {
 
1640
                (*i)->firstpos.clear();
 
1641
                (*i)->lastpos.clear();
 
1642
                (*i)->followpos.clear();
 
1643
        }
 
1644
 
 
1645
        if (flags & DFA_DUMP_NODE_TO_DFA)
 
1646
                dump_node_to_dfa();
 
1647
 
 
1648
        for (NodeMap::iterator i = nodemap.begin(); i != nodemap.end(); i++)
 
1649
                delete i->first.second;
 
1650
        nodemap.clear();
 
1651
 
 
1652
        if (flags & (DFA_DUMP_STATS))
 
1653
          fprintf(stderr, "\033[2KCreated dfa: states %ld,\teliminated duplicates %d,\tprotostate sets: longest %u, avg %u\n", states.size(), stats.duplicates, stats.proto_max, (unsigned int) (stats.proto_sum/states.size()));
 
1654
 
844
1655
}
845
1656
 
 
1657
 
846
1658
DFA::~DFA()
847
1659
{
848
 
    for (States::iterator i = states.begin(); i != states.end(); i++)
 
1660
    for (Partition::iterator i = states.begin(); i != states.end(); i++)
849
1661
        delete *i;
850
1662
}
851
1663
 
852
 
/**
853
 
 * Result when this state matches.
 
1664
class MatchFlag : public AcceptNode {
 
1665
public:
 
1666
MatchFlag(uint32_t flag, uint32_t audit) : flag(flag), audit(audit) {}
 
1667
    ostream& dump(ostream& os)
 
1668
    {
 
1669
        return os << '<' << flag << '>';
 
1670
    }
 
1671
 
 
1672
    uint32_t flag;
 
1673
    uint32_t audit;
 
1674
 };
 
1675
 
 
1676
class ExactMatchFlag : public MatchFlag {
 
1677
public:
 
1678
    ExactMatchFlag(uint32_t flag, uint32_t audit) : MatchFlag(flag, audit) {}
 
1679
};
 
1680
 
 
1681
class DenyMatchFlag : public MatchFlag {
 
1682
public:
 
1683
    DenyMatchFlag(uint32_t flag, uint32_t quiet) : MatchFlag(flag, quiet) {}
 
1684
};
 
1685
 
 
1686
 
 
1687
void DFA::dump_uniq_perms(const char *s)
 
1688
{
 
1689
        set < pair<uint32_t, uint32_t> > uniq;
 
1690
        for (Partition::iterator i = states.begin(); i != states.end(); i++)
 
1691
                uniq.insert(make_pair((*i)->accept, (*i)->audit));
 
1692
 
 
1693
        cerr << "Unique Permission sets: " << s << " (" << uniq.size() << ")\n";
 
1694
        cerr << "----------------------\n";
 
1695
        for (set< pair<uint32_t, uint32_t> >::iterator i = uniq.begin();
 
1696
             i != uniq.end(); i++) {
 
1697
                cerr << "  " << hex << i->first << " " << i->second << dec <<"\n";
 
1698
        }
 
1699
}
 
1700
 
 
1701
 
 
1702
/* Remove dead or unreachable states */
 
1703
void DFA::remove_unreachable(dfaflags_t flags)
 
1704
{
 
1705
        set <State *> reachable;
 
1706
        list <State *> work_queue;
 
1707
 
 
1708
        /* find the set of reachable states */
 
1709
        reachable.insert(nonmatching);
 
1710
        work_queue.push_back(start);
 
1711
        while (!work_queue.empty()) {
 
1712
                State *from = work_queue.front();
 
1713
                work_queue.pop_front();
 
1714
                reachable.insert(from);
 
1715
 
 
1716
                if (from->cases.otherwise &&
 
1717
                    (reachable.find(from->cases.otherwise) == reachable.end()))
 
1718
                        work_queue.push_back(from->cases.otherwise);
 
1719
 
 
1720
                for (Cases::iterator j = from->cases.begin();
 
1721
                     j != from->cases.end(); j++) {
 
1722
                        if (reachable.find(j->second) == reachable.end())
 
1723
                                work_queue.push_back(j->second);
 
1724
                }
 
1725
        }
 
1726
 
 
1727
        /* walk the set of states and remove any that aren't reachable */
 
1728
        if (reachable.size() < states.size()) {
 
1729
                int count = 0;
 
1730
                Partition::iterator i;
 
1731
                Partition::iterator next;
 
1732
                for (i = states.begin(); i != states.end(); i = next) {
 
1733
                        next = i;
 
1734
                        next++;
 
1735
                        if (reachable.find(*i) == reachable.end()) {
 
1736
                                if (flags & DFA_DUMP_UNREACHABLE) {
 
1737
                                        cerr << "unreachable: "<< **i;
 
1738
                                        if (*i == start)
 
1739
                                                cerr << " <==";
 
1740
                                        if ((*i)->accept) {
 
1741
                                                cerr << " (0x" << hex << (*i)->accept
 
1742
                                                     << " " << (*i)->audit << dec << ')';
 
1743
                                        }
 
1744
                                        cerr << endl;
 
1745
                                }
 
1746
                                State *current = *i;
 
1747
                                states.erase(i);
 
1748
                                delete(current);
 
1749
                                count++;
 
1750
                        }
 
1751
                }
 
1752
 
 
1753
                if (count && (flags & DFA_DUMP_STATS))
 
1754
                        cerr << "DFA: states " << states.size() << " removed "
 
1755
                             << count << " unreachable states\n";
 
1756
        }
 
1757
}
 
1758
 
 
1759
/* test if two states have the same transitions under partition_map */
 
1760
bool DFA::same_mappings(State *s1, State *s2)
 
1761
{
 
1762
        if (s1->cases.otherwise && s1->cases.otherwise != nonmatching) {
 
1763
                if (!s2->cases.otherwise || s2->cases.otherwise == nonmatching)
 
1764
                        return false;
 
1765
                Partition *p1 = s1->cases.otherwise->partition;
 
1766
                Partition *p2 = s2->cases.otherwise->partition;
 
1767
                if (p1 != p2)
 
1768
                        return false;
 
1769
        } else if (s2->cases.otherwise && s2->cases.otherwise != nonmatching) {
 
1770
                return false;
 
1771
        }
 
1772
 
 
1773
        if (s1->cases.cases.size() != s2->cases.cases.size())
 
1774
                return false;
 
1775
        for (Cases::iterator j1 = s1->cases.begin(); j1 != s1->cases.end();
 
1776
             j1++){
 
1777
                Cases::iterator j2 = s2->cases.cases.find(j1->first);
 
1778
                if (j2 == s2->cases.end())
 
1779
                        return false;
 
1780
                Partition *p1 = j1->second->partition;
 
1781
                Partition *p2 = j2->second->partition;
 
1782
                if (p1 != p2)
 
1783
                        return false;
 
1784
        }
 
1785
 
 
1786
        return true;
 
1787
}
 
1788
 
 
1789
/* Do simple djb2 hashing against a States transition cases
 
1790
 * this provides a rough initial guess at state equivalence as if a state
 
1791
 * has a different number of transitions or has transitions on different
 
1792
 * cases they will never be equivalent.
 
1793
 * Note: this only hashes based off of the alphabet (not destination)
 
1794
 * as different destinations could end up being equiv
854
1795
 */
855
 
uint32_t accept_perms(State *state)
856
 
{
857
 
    uint32_t perms = 0;
858
 
    int is_exactXmatch = 0;
859
 
 
860
 
    for (State::iterator i = state->begin(); i != state->end(); i++) {
861
 
        if (AcceptNode *accept = dynamic_cast<AcceptNode *>(*i)) {
862
 
            if (is_exactXmatch) {
863
 
                /* exact match X perms override an re match X perm.  Only
864
 
                 * accumulate regular permissions
865
 
                 */
866
 
                if (accept->is_rerule)
867
 
                    perms |= AA_NOXMODS_PERM_MASK & accept->perms;
868
 
                else
869
 
                    /* N exact matches must have same X perm so accumulate
870
 
                     * to catch any error */
871
 
                    perms |= accept->perms;
872
 
            } else {
873
 
                if (accept->is_rerule ||
874
 
                    !(AA_EXEC_MODIFIERS & accept->perms)) {
875
 
                    perms |= accept->perms;
 
1796
size_t DFA::hash_trans(State *s)
 
1797
{
 
1798
        unsigned long hash = 5381;
 
1799
 
 
1800
        for (Cases::iterator j = s->cases.begin(); j != s->cases.end(); j++){
 
1801
                hash = ((hash << 5) + hash) + j->first;
 
1802
                State *k = j->second;
 
1803
                hash = ((hash << 5) + hash) + k->cases.cases.size();
 
1804
        }
 
1805
 
 
1806
        if (s->cases.otherwise && s->cases.otherwise != nonmatching) {
 
1807
                hash = ((hash << 5) + hash) + 5381;
 
1808
                State *k = s->cases.otherwise;
 
1809
                hash = ((hash << 5) + hash) + k->cases.cases.size();
 
1810
        }
 
1811
 
 
1812
        hash = (hash << 8) | s->cases.cases.size();
 
1813
        return hash;
 
1814
}
 
1815
 
 
1816
/* minimize the number of dfa states */
 
1817
void DFA::minimize(dfaflags_t flags)
 
1818
{
 
1819
        map <pair <uint64_t, size_t>, Partition *> perm_map;
 
1820
        list <Partition *> partitions;
 
1821
        
 
1822
        /* Set up the initial partitions
 
1823
         * minimium of - 1 non accepting, and 1 accepting
 
1824
         * if trans hashing is used the accepting and non-accepting partitions
 
1825
         * can be further split based on the number and type of transitions
 
1826
         * a state makes.
 
1827
         * If permission hashing is enabled the accepting partitions can
 
1828
         * be further divided by permissions.  This can result in not
 
1829
         * obtaining a truely minimized dfa but comes close, and can speedup
 
1830
         * minimization.
 
1831
         */
 
1832
        int accept_count = 0;
 
1833
        int final_accept = 0;
 
1834
        for (Partition::iterator i = states.begin(); i != states.end(); i++) {
 
1835
                uint64_t perm_hash = 0;
 
1836
                if (flags & DFA_CONTROL_MINIMIZE_HASH_PERMS) {
 
1837
                        /* make every unique perm create a new partition */
 
1838
                        perm_hash = ((uint64_t)(*i)->audit)<<32 |
 
1839
                                (uint64_t)(*i)->accept;
 
1840
                } else if ((*i)->audit || (*i)->accept) {
 
1841
                        /* combine all perms together into a single parition */
 
1842
                        perm_hash = 1;
 
1843
                } /* else not an accept state so 0 for perm_hash */
 
1844
 
 
1845
                size_t trans_hash = 0;
 
1846
                if (flags & DFA_CONTROL_MINIMIZE_HASH_TRANS)
 
1847
                        trans_hash = hash_trans(*i);
 
1848
                pair <uint64_t, size_t> group = make_pair(perm_hash, trans_hash);
 
1849
                map <pair <uint64_t, size_t>, Partition *>::iterator p = perm_map.find(group);
 
1850
                if (p == perm_map.end()) {
 
1851
                        Partition *part = new Partition();
 
1852
                        part->push_back(*i);
 
1853
                        perm_map.insert(make_pair(group, part));
 
1854
                        partitions.push_back(part);
 
1855
                        (*i)->partition = part;
 
1856
                        if (perm_hash)
 
1857
                                accept_count++;
876
1858
                } else {
877
 
                    /* exact match with an exec modifier override accumulated
878
 
                     * X permissions */
879
 
                    is_exactXmatch = 1;
880
 
                    perms = (AA_NOXMODS_PERM_MASK & perms) | accept->perms;
881
 
                }
882
 
            }
883
 
        }
884
 
    }
885
 
    return perms;
886
 
}
887
 
 
888
 
/**
889
 
 * verify that there are no conflicting X permissions on the dfa
890
 
 * return NULL - perms verified okay
891
 
 *     State of 1st encountered with bad X perms
892
 
 */
893
 
State *DFA::verify_perms(void)
894
 
{
895
 
    for (States::iterator i = states.begin(); i != states.end(); i++) {
896
 
        uint32_t accept = accept_perms(*i);
897
 
        if (*i == start || accept) {
898
 
            if ((accept & AA_EXEC_MODIFIERS) &&
899
 
                !AA_EXEC_SINGLE_MODIFIER_SET(accept))
900
 
                return *i;
901
 
        }
902
 
    }
903
 
    return NULL;
 
1859
                        (*i)->partition = p->second;
 
1860
                        p->second->push_back(*i);
 
1861
                }
 
1862
 
 
1863
                if ((flags & DFA_DUMP_PROGRESS) &&
 
1864
                    (partitions.size() % 1000 == 0))
 
1865
                        cerr << "\033[2KMinimize dfa: partitions " << partitions.size() << "\tinit " << partitions.size() << " (accept " << accept_count << ")\r";
 
1866
        }
 
1867
 
 
1868
        /* perm_map is no longer needed so free the memory it is using.
 
1869
         * Don't remove - doing it manually here helps reduce peak memory usage.
 
1870
         */
 
1871
        perm_map.clear();
 
1872
 
 
1873
        int init_count = partitions.size();
 
1874
        if (flags & DFA_DUMP_PROGRESS)
 
1875
                cerr << "\033[2KMinimize dfa: partitions " << partitions.size() << "\tinit " << init_count << " (accept " << accept_count << ")\r";
 
1876
 
 
1877
        /* Now do repartitioning until each partition contains the set of
 
1878
         * states that are the same.  This will happen when the partition
 
1879
         * splitting stables.  With a worse case of 1 state per partition
 
1880
         * ie. already minimized.
 
1881
         */
 
1882
        Partition *new_part;
 
1883
        int new_part_count;
 
1884
        do {
 
1885
                new_part_count = 0;
 
1886
                for (list <Partition *>::iterator p = partitions.begin();
 
1887
                     p != partitions.end(); p++) {
 
1888
                        new_part = NULL;
 
1889
                        State *rep = *((*p)->begin());
 
1890
                        Partition::iterator next;
 
1891
                        for (Partition::iterator s = ++(*p)->begin();
 
1892
                             s != (*p)->end(); ) {
 
1893
                                if (same_mappings(rep, *s)) {
 
1894
                                        ++s;
 
1895
                                        continue;
 
1896
                                }
 
1897
                                if (!new_part) {
 
1898
                                        new_part = new Partition;
 
1899
                                        list <Partition *>::iterator tmp = p;
 
1900
                                        partitions.insert(++tmp, new_part);
 
1901
                                        new_part_count++;
 
1902
                                }
 
1903
                                new_part->push_back(*s);
 
1904
                                s = (*p)->erase(s);
 
1905
                        }
 
1906
                        /* remapping partition_map for new_part entries
 
1907
                         * Do not do this above as it messes up same_mappings
 
1908
                         */
 
1909
                        if (new_part) {
 
1910
                                for (Partition::iterator m = new_part->begin();
 
1911
                                     m != new_part->end(); m++) {
 
1912
                                        (*m)->partition = new_part;
 
1913
                                }
 
1914
                        }
 
1915
                if ((flags & DFA_DUMP_PROGRESS) &&
 
1916
                    (partitions.size() % 100 == 0))
 
1917
                        cerr << "\033[2KMinimize dfa: partitions " << partitions.size() << "\tinit " << init_count << " (accept " << accept_count << ")\r";
 
1918
                }
 
1919
        } while(new_part_count);
 
1920
 
 
1921
        if (partitions.size() == states.size()) {
 
1922
                if (flags & DFA_DUMP_STATS)
 
1923
                        cerr << "\033[2KDfa minimization no states removed: partitions " << partitions.size() << "\tinit " << init_count << " (accept " << accept_count << ")\n";
 
1924
 
 
1925
 
 
1926
                goto out;
 
1927
        }
 
1928
 
 
1929
        /* Remap the dfa so it uses the representative states
 
1930
         * Use the first state of a partition as the representative state
 
1931
         * At this point all states with in a partion have transitions
 
1932
         * to states within the same partitions, however this can slow
 
1933
         * down compressed dfa compression as there are more states,
 
1934
         */
 
1935
        for (list <Partition *>::iterator p = partitions.begin();
 
1936
             p != partitions.end(); p++) {
 
1937
                /* representative state for this partition */
 
1938
                State *rep = *((*p)->begin());
 
1939
 
 
1940
                /* update representative state's transitions */
 
1941
                if (rep->cases.otherwise) {
 
1942
                        Partition *partition = rep->cases.otherwise->partition;
 
1943
                        rep->cases.otherwise = *partition->begin();
 
1944
                }
 
1945
                for (Cases::iterator c = rep->cases.begin();
 
1946
                     c != rep->cases.end(); c++) {
 
1947
                        Partition *partition = c->second->partition;
 
1948
                        c->second = *partition->begin();
 
1949
                }
 
1950
 
 
1951
//if ((*p)->size() > 1)
 
1952
//cerr << rep->label << ": ";
 
1953
                /* clear the state label for all non representative states,
 
1954
                 * and accumulate permissions */
 
1955
                for (Partition::iterator i = ++(*p)->begin(); i != (*p)->end(); i++) {
 
1956
//cerr << " " << (*i)->label;
 
1957
                        (*i)->label = -1;
 
1958
                        rep->accept |= (*i)->accept;
 
1959
                        rep->audit |= (*i)->audit;
 
1960
                }
 
1961
                if (rep->accept || rep->audit)
 
1962
                        final_accept++;
 
1963
//if ((*p)->size() > 1)
 
1964
//cerr << "\n";
 
1965
        }
 
1966
        if (flags & DFA_DUMP_STATS)
 
1967
                cerr << "\033[2KMinimized dfa: final partitions " << partitions.size() << " (accept " << final_accept << ")" << "\tinit " << init_count << " (accept " << accept_count << ")\n";
 
1968
 
 
1969
 
 
1970
 
 
1971
        /* make sure nonmatching and start state are up to date with the
 
1972
         * mappings */
 
1973
        {
 
1974
                Partition *partition = nonmatching->partition;
 
1975
                if (*partition->begin() != nonmatching) {
 
1976
                        nonmatching = *partition->begin();
 
1977
                }
 
1978
 
 
1979
                partition = start->partition;
 
1980
                if (*partition->begin() != start) {
 
1981
                        start = *partition->begin();
 
1982
                }
 
1983
        }
 
1984
 
 
1985
        /* Now that the states have been remapped, remove all states
 
1986
         * that are not the representive states for their partition, they
 
1987
         * will have a label == -1
 
1988
         */
 
1989
        for (Partition::iterator i = states.begin(); i != states.end(); ) {
 
1990
                if ((*i)->label == -1) {
 
1991
                        State *s = *i;
 
1992
                        i = states.erase(i);
 
1993
                        delete(s);
 
1994
                } else
 
1995
                        i++;
 
1996
        }
 
1997
 
 
1998
out:
 
1999
        /* Cleanup */
 
2000
        while (!partitions.empty()) {
 
2001
                Partition *p = partitions.front();
 
2002
                partitions.pop_front();
 
2003
                delete(p);
 
2004
        }
904
2005
}
905
2006
 
906
2007
/**
908
2009
 */
909
2010
void DFA::dump(ostream& os)
910
2011
{
911
 
    for (States::iterator i = states.begin(); i != states.end(); i++) {
912
 
        uint32_t accept = accept_perms(*i);
913
 
        if (*i == start || accept) {
 
2012
    for (Partition::iterator i = states.begin(); i != states.end(); i++) {
 
2013
            if (*i == start || (*i)->accept) {
914
2014
            os << **i;
915
2015
            if (*i == start)
916
2016
                os << " <==";
917
 
            if (accept) {
918
 
                os << " (" << accept << ')';
 
2017
            if ((*i)->accept) {
 
2018
                    os << " (0x" << hex << (*i)->accept << " " << (*i)->audit << dec << ')';
919
2019
            }
920
2020
            os << endl;
921
2021
        }
922
2022
    }
923
2023
    os << endl;
924
2024
 
925
 
    for (Trans::iterator i = trans.begin(); i != trans.end(); i++) {
926
 
        if (i->second.otherwise)
927
 
            os << *(i->first) << " -> " << *i->second.otherwise << endl;
928
 
        for (Cases::iterator j = i->second.begin(); j != i->second.end(); j++) {
929
 
            os << *(i->first) << " -> " << *(j->second) << ":  "
930
 
               << j->first << endl;
 
2025
    for (Partition::iterator i = states.begin(); i != states.end(); i++) {
 
2026
            if ((*i)->cases.otherwise)
 
2027
              os << **i << " -> " << (*i)->cases.otherwise << endl;
 
2028
            for (Cases::iterator j = (*i)->cases.begin(); j != (*i)->cases.end(); j++) {
 
2029
            os << **i << " -> " << j->second << ":  " << j->first << endl;
931
2030
        }
932
2031
    }
933
2032
    os << endl;
940
2039
{
941
2040
    os << "digraph \"dfa\" {" << endl;
942
2041
 
943
 
    for (States::iterator i = states.begin(); i != states.end(); i++) {
 
2042
    for (Partition::iterator i = states.begin(); i != states.end(); i++) {
944
2043
        if (*i == nonmatching)
945
2044
            continue;
946
2045
 
948
2047
        if (*i == start) {
949
2048
            os << "\t\tstyle=bold" << endl;
950
2049
        }
951
 
        uint32_t perms = accept_perms(*i);
 
2050
        uint32_t perms = (*i)->accept;
952
2051
        if (perms) {
953
2052
            os << "\t\tlabel=\"" << **i << "\\n("
954
2053
               << perms << ")\"" << endl;
955
2054
        }
956
2055
        os << "\t]" << endl;
957
2056
    }
958
 
    for (Trans::iterator i = trans.begin(); i != trans.end(); i++) {
959
 
        Cases& cases = i->second;
 
2057
    for (Partition::iterator i = states.begin(); i != states.end(); i++) {
 
2058
            Cases& cases = (*i)->cases;
960
2059
        Chars excluded;
961
2060
 
962
2061
        for (Cases::iterator j = cases.begin(); j != cases.end(); j++) {
963
2062
            if (j->second == nonmatching)
964
2063
                excluded.insert(j->first);
965
2064
            else {
966
 
                os << "\t\"" << *i->first << "\" -> \"";
967
 
                os << *j->second << "\" [" << endl;
968
 
                os << "\t\tlabel=\"" << (char)j->first << "\"" << endl;
969
 
                os << "\t]" << endl;
 
2065
                    os << "\t\"" << **i << "\" -> \"";
 
2066
                    os << j->second << "\" [" << endl;
 
2067
                    os << "\t\tlabel=\"" << j->first << "\"" << endl;
 
2068
                    os << "\t]" << endl;
970
2069
            }
971
2070
        }
972
 
        if (i->second.otherwise && i->second.otherwise != nonmatching) {
973
 
            os << "\t\"" << *i->first << "\" -> \"" << *i->second.otherwise
 
2071
        if (cases.otherwise && cases.otherwise != nonmatching) {
 
2072
                os << "\t\"" << **i << "\" -> \"" << cases.otherwise
974
2073
               << "\" [" << endl;
975
2074
            if (!excluded.empty()) {
976
2075
                os << "\t\tlabel=\"[^";
991
2090
 * Compute character equivalence classes in the DFA to save space in the
992
2091
 * transition table.
993
2092
 */
994
 
map<uchar, uchar> DFA::equivalence_classes()
 
2093
map<uchar, uchar> DFA::equivalence_classes(dfaflags_t flags)
995
2094
{
996
2095
    map<uchar, uchar> classes;
997
2096
    uchar next_class = 1;
998
2097
 
999
 
    for (Trans::iterator i = trans.begin(); i != trans.end(); i++) {
1000
 
        Cases& cases = i->second;
 
2098
    for (Partition::iterator i = states.begin(); i != states.end(); i++) {
 
2099
            Cases& cases = (*i)->cases;
1001
2100
 
1002
2101
        /* Group edges to the same next state together */
1003
2102
        map<const State *, Chars> node_sets;
1052
2151
            }
1053
2152
        }
1054
2153
    }
 
2154
 
 
2155
    if (flags & DFA_DUMP_EQUIV_STATS)
 
2156
        fprintf(stderr, "Equiv class reduces to %d classes\n", next_class - 1);
1055
2157
    return classes;
1056
2158
}
1057
2159
 
1088
2190
     * Note: We only transform the transition table; the nodes continue to
1089
2191
     * contain the original characters.
1090
2192
     */
1091
 
    for (Trans::iterator i = trans.begin(); i != trans.end(); i++) {
 
2193
    for (Partition::iterator i = states.begin(); i != states.end(); i++) {
1092
2194
        map<uchar, State *> tmp;
1093
 
        tmp.swap(i->second.cases);
 
2195
        tmp.swap((*i)->cases.cases);
1094
2196
        for (Cases::iterator j = tmp.begin(); j != tmp.end(); j++)
1095
 
            i->second.cases.insert(make_pair(eq[j->first], j->second));
 
2197
                (*i)->cases.cases.insert(make_pair(eq[j->first], j->second));
1096
2198
    }
1097
2199
}
1098
2200
 
1104
2206
{
1105
2207
    for (depth_first_traversal i(node); i; i++) {
1106
2208
        if (CatNode *cat = dynamic_cast<CatNode *>(*i)) {
1107
 
            swap(cat->left, cat->right);
 
2209
            swap(cat->child[0], cat->child[1]);
1108
2210
        }
1109
2211
    }
1110
2212
}
1113
2215
    typedef vector<pair<const State *, size_t> > DefaultBase;
1114
2216
    typedef vector<pair<const State *, const State *> > NextCheck;
1115
2217
public:
1116
 
    TransitionTable(DFA& dfa, map<uchar, uchar>& eq);
 
2218
    TransitionTable(DFA& dfa, map<uchar, uchar>& eq, dfaflags_t flags);
1117
2219
    void dump(ostream& os);
1118
2220
    void flex_table(ostream& os, const char *name);
1119
 
    bool fits_in(size_t base, Cases& cases);
1120
 
    void insert_state(State *state, DFA& dfa);
 
2221
    void init_free_list(vector <pair<size_t, size_t> > &free_list, size_t prev, size_t start);
 
2222
    bool fits_in(vector <pair<size_t, size_t> > &free_list,
 
2223
                 size_t base, Cases& cases);
 
2224
    void insert_state(vector <pair<size_t, size_t> > &free_list,
 
2225
                      State *state, DFA& dfa);
1121
2226
 
1122
2227
private:
1123
2228
    vector<uint32_t> accept;
 
2229
    vector<uint32_t> accept2;
1124
2230
    DefaultBase default_base;
1125
2231
    NextCheck next_check;
1126
2232
    map<const State *, size_t> num;
1127
2233
    map<uchar, uchar>& eq;
1128
2234
    uchar max_eq;
1129
 
    uint32_t min_base;
 
2235
    size_t first_free;
1130
2236
};
1131
2237
 
 
2238
 
 
2239
void TransitionTable::init_free_list(vector <pair<size_t, size_t> > &free_list,
 
2240
                                     size_t prev, size_t start) {
 
2241
        for (size_t i = start; i < free_list.size(); i++) {
 
2242
                if (prev)
 
2243
                        free_list[prev].second = i;
 
2244
                free_list[i].first = prev;
 
2245
                prev = i;
 
2246
        }
 
2247
        free_list[free_list.size() -1].second = 0;
 
2248
}
 
2249
 
1132
2250
/**
1133
 
 * Construct the transition table.
 
2251
 * new Construct the transition table.
1134
2252
 */
1135
 
TransitionTable::TransitionTable(DFA& dfa, map<uchar, uchar>& eq)
1136
 
    : eq(eq), min_base(0)
 
2253
TransitionTable::TransitionTable(DFA& dfa, map<uchar, uchar>& eq,
 
2254
                                 dfaflags_t flags)
 
2255
    : eq(eq)
1137
2256
{
1138
 
    /* Insert the dummy nonmatching transition by hand */
1139
 
    next_check.push_back(make_pair(dfa.nonmatching, dfa.nonmatching));
1140
 
 
1141
 
    if (eq.empty())
1142
 
        max_eq = 255;
1143
 
    else {
1144
 
        max_eq = 0;
1145
 
        for(map<uchar, uchar>::iterator i = eq.begin(); i != eq.end(); i++) {
1146
 
            if (i->second > max_eq)
1147
 
                max_eq = i->second;
1148
 
        }
1149
 
    }
1150
 
 
1151
 
    /**
1152
 
     * Insert all the DFA states into the transition table. The nonmatching
1153
 
     * and start states come first, followed by all other states.
1154
 
     */
1155
 
    insert_state(dfa.nonmatching, dfa);
1156
 
    insert_state(dfa.start, dfa);
1157
 
    for (States::iterator i = dfa.states.begin(); i != dfa.states.end(); i++) {
1158
 
        if (*i != dfa.nonmatching && *i != dfa.start)
1159
 
            insert_state(*i, dfa);
1160
 
    }
1161
 
 
1162
 
    num.insert(make_pair(dfa.nonmatching, num.size()));
1163
 
    num.insert(make_pair(dfa.start, num.size()));
1164
 
    for (States::iterator i = dfa.states.begin(); i != dfa.states.end(); i++) {
1165
 
        if (*i != dfa.nonmatching && *i != dfa.start)
1166
 
            num.insert(make_pair(*i, num.size()));
1167
 
    }
1168
 
 
1169
 
    accept.resize(dfa.states.size());
1170
 
    for (States::iterator i = dfa.states.begin(); i != dfa.states.end(); i++)
1171
 
        accept[num[*i]] = accept_perms(*i);
 
2257
 
 
2258
        if (flags & DFA_DUMP_TRANS_PROGRESS)
 
2259
                fprintf(stderr, "Compressing trans table:\r");
 
2260
 
 
2261
 
 
2262
        if (eq.empty())
 
2263
                max_eq = 255;
 
2264
        else {
 
2265
                max_eq = 0;
 
2266
                for(map<uchar, uchar>::iterator i = eq.begin(); i != eq.end(); i++) {
 
2267
                        if (i->second > max_eq)
 
2268
                                max_eq = i->second;
 
2269
                }
 
2270
        }
 
2271
 
 
2272
        /* Do initial setup adding up all the transitions and sorting by
 
2273
         * transition count.
 
2274
         */
 
2275
        size_t optimal = 2;
 
2276
        multimap <size_t, State *> order;
 
2277
        vector <pair<size_t, size_t> > free_list;
 
2278
 
 
2279
        for (Partition::iterator i = dfa.states.begin(); i != dfa.states.end(); i++) {
 
2280
                if (*i == dfa.start || *i == dfa.nonmatching)
 
2281
                        continue;
 
2282
                optimal += (*i)->cases.cases.size();
 
2283
                if (flags & DFA_CONTROL_TRANS_HIGH) {
 
2284
                        size_t range = 0;
 
2285
                        if ((*i)->cases.cases.size())
 
2286
                                range = (*i)->cases.cases.rbegin()->first - (*i)->cases.begin()->first;
 
2287
                        size_t ord = ((256 - (*i)->cases.cases.size()) << 8) |
 
2288
                                (256 - range);
 
2289
                        /* reverse sort by entry count, most entries first */
 
2290
                        order.insert(make_pair(ord, *i));
 
2291
                }
 
2292
        }
 
2293
 
 
2294
        /* Insert the dummy nonmatching transition by hand */
 
2295
        next_check.push_back(make_pair(dfa.nonmatching, dfa.nonmatching));
 
2296
        default_base.push_back(make_pair(dfa.nonmatching, 0));
 
2297
        num.insert(make_pair(dfa.nonmatching, num.size()));
 
2298
 
 
2299
        accept.resize(dfa.states.size());
 
2300
        accept2.resize(dfa.states.size());
 
2301
        next_check.resize(optimal);
 
2302
        free_list.resize(optimal);
 
2303
 
 
2304
        accept[0] = 0;
 
2305
        accept2[0] = 0;
 
2306
        first_free = 1;
 
2307
        init_free_list(free_list, 0, 1);
 
2308
 
 
2309
        insert_state(free_list, dfa.start, dfa);
 
2310
        accept[1] = 0;
 
2311
        accept2[1] = 0;
 
2312
        num.insert(make_pair(dfa.start, num.size()));
 
2313
 
 
2314
        int count = 2;
 
2315
 
 
2316
        if (!(flags & DFA_CONTROL_TRANS_HIGH)) {
 
2317
                for (Partition::iterator i = dfa.states.begin(); i != dfa.states.end();
 
2318
                     i++) {
 
2319
                        if (*i != dfa.nonmatching && *i != dfa.start) {
 
2320
                                insert_state(free_list, *i, dfa);
 
2321
                                accept[num.size()] = (*i)->accept;
 
2322
                                accept2[num.size()] = (*i)->audit;
 
2323
                                num.insert(make_pair(*i, num.size()));
 
2324
                        }
 
2325
                        if (flags & (DFA_DUMP_TRANS_PROGRESS)) {
 
2326
                                count++;
 
2327
                                if (count % 100 == 0)
 
2328
                                        fprintf(stderr, "\033[2KCompressing trans table: insert state: %d/%ld\r", count, dfa.states.size());
 
2329
                        }
 
2330
                }
 
2331
        } else {
 
2332
                for (multimap <size_t, State *>::iterator i = order.begin();
 
2333
                     i != order.end(); i++) {
 
2334
                        if (i->second != dfa.nonmatching && i->second != dfa.start) {
 
2335
                                insert_state(free_list, i->second, dfa);
 
2336
                                accept[num.size()] = i->second->accept;
 
2337
                                accept2[num.size()] = i->second->audit;
 
2338
                                num.insert(make_pair(i->second, num.size()));
 
2339
                        }
 
2340
                        if (flags & (DFA_DUMP_TRANS_PROGRESS)) {
 
2341
                                count++;
 
2342
                                if (count % 100 == 0)
 
2343
                                        fprintf(stderr, "\033[2KCompressing trans table: insert state: %d/%ld\r", count, dfa.states.size());
 
2344
                        }
 
2345
                }
 
2346
        }
 
2347
 
 
2348
        if (flags & (DFA_DUMP_TRANS_STATS | DFA_DUMP_TRANS_PROGRESS)) {
 
2349
                ssize_t size = 4 * next_check.size() + 6 * dfa.states.size();
 
2350
                fprintf(stderr, "\033[2KCompressed trans table: states %ld, next/check %ld, optimal next/check %ld avg/state %.2f, compression %ld/%ld = %.2f %%\n", dfa.states.size(), next_check.size(), optimal, (float)next_check.size()/(float)dfa.states.size(), size, 512 * dfa.states.size(), 100.0 - ((float) size * 100.0 / (float)(512 * dfa.states.size())));
 
2351
        }
1172
2352
}
1173
2353
 
 
2354
 
1174
2355
/**
1175
2356
 * Does <cases> fit into position <base> of the transition table?
1176
2357
 */
1177
 
bool TransitionTable::fits_in(size_t base, Cases& cases)
 
2358
bool TransitionTable::fits_in(vector <pair<size_t, size_t> > &free_list __attribute__((unused)),
 
2359
                              size_t pos, Cases& cases)
1178
2360
{
1179
 
    for (Cases::iterator i = cases.begin(); i != cases.end(); i++) {
1180
 
        size_t c = base + i->first;
1181
 
        if (c >= next_check.size())
1182
 
            continue;
1183
 
        if (next_check[c].second)
1184
 
            return false;
1185
 
    }
1186
 
    return true;
 
2361
        size_t c, base = pos - cases.begin()->first;
 
2362
        for (Cases::iterator i = cases.begin(); i != cases.end(); i++) {
 
2363
                c = base + i->first;
 
2364
                /* if it overflows the next_check array it fits in as we will
 
2365
                 * resize */
 
2366
                if (c >= next_check.size())
 
2367
                        return true;
 
2368
                if (next_check[c].second)
 
2369
                        return false;
 
2370
        }
 
2371
 
 
2372
        return true;
1187
2373
}
1188
2374
 
1189
2375
/**
1190
2376
 * Insert <state> of <dfa> into the transition table.
1191
2377
 */
1192
 
void TransitionTable::insert_state(State *from, DFA& dfa)
 
2378
void TransitionTable::insert_state(vector <pair<size_t, size_t> > &free_list,
 
2379
                                   State *from, DFA& dfa)
1193
2380
{
1194
 
    State *default_state = dfa.nonmatching;
1195
 
    size_t base = 0;
1196
 
 
1197
 
    Trans::iterator i = dfa.trans.find(from);
1198
 
    if (i != dfa.trans.end()) {
1199
 
        Cases& cases = i->second;
 
2381
        State *default_state = dfa.nonmatching;
 
2382
        size_t base = 0;
 
2383
        int resize;
 
2384
 
 
2385
        Cases& cases = from->cases;
 
2386
        size_t c = cases.begin()->first;
 
2387
        size_t prev = 0;
 
2388
        size_t x = first_free;
 
2389
 
1200
2390
        if (cases.otherwise)
1201
 
            default_state = cases.otherwise;
 
2391
                default_state = cases.otherwise;
1202
2392
        if (cases.cases.empty())
1203
 
            goto insert_state;
1204
 
 
1205
 
        size_t c = cases.begin()->first;
1206
 
        if (c < min_base)
1207
 
            base = min_base - c;
1208
 
        /* Try inserting until we succeed. */
1209
 
        while (!fits_in(base, cases))
1210
 
            base++;
1211
 
 
1212
 
        if (next_check.size() <= base + max_eq)
1213
 
            next_check.resize(base + max_eq + 1);
1214
 
        for (Cases::iterator j = cases.begin(); j != cases.end(); j++)
 
2393
                goto do_insert;
 
2394
 
 
2395
repeat:
 
2396
        resize = 0;
 
2397
        /* get the first free entry that won't underflow */
 
2398
        while (x && (x < c)) {
 
2399
                prev = x;
 
2400
                x = free_list[x].second;
 
2401
        }
 
2402
 
 
2403
        /* try inserting until we succeed. */
 
2404
        while (x && !fits_in(free_list, x, cases)) {
 
2405
                prev = x;
 
2406
                x = free_list[x].second;
 
2407
        }
 
2408
        if (!x) {
 
2409
                resize = 256 - cases.begin()->first;
 
2410
                x = free_list.size();
 
2411
                /* set prev to last free */
 
2412
        } else if (x + 255 - cases.begin()->first >= next_check.size()) {
 
2413
                resize = (255 - cases.begin()->first - (next_check.size() - 1 - x));
 
2414
                for (size_t y = x; y; y = free_list[y].second)
 
2415
                        prev = y;
 
2416
        }
 
2417
        if (resize) {
 
2418
                /* expand next_check and free_list */
 
2419
                size_t old_size = free_list.size();
 
2420
                next_check.resize(next_check.size() + resize);
 
2421
                free_list.resize(free_list.size() + resize);
 
2422
                init_free_list(free_list, prev, old_size);
 
2423
                if (!first_free)
 
2424
                        first_free = old_size;;
 
2425
                if (x == old_size)
 
2426
                        goto repeat;
 
2427
        }
 
2428
 
 
2429
        base = x - c;
 
2430
        for (Cases::iterator j = cases.begin(); j != cases.end(); j++) {
1215
2431
            next_check[base + j->first] = make_pair(j->second, from);
1216
 
 
1217
 
        while (min_base < next_check.size()) {
1218
 
            if (!next_check[min_base].second)
1219
 
                break;
1220
 
            min_base++;
 
2432
            size_t prev = free_list[base + j->first].first;
 
2433
            size_t next = free_list[base + j->first].second;
 
2434
            if (prev)
 
2435
                    free_list[prev].second = next;
 
2436
            if (next)
 
2437
                    free_list[next].first = prev;
 
2438
            if (base + j->first == first_free)
 
2439
                    first_free = next;
1221
2440
        }
1222
 
    }
1223
 
insert_state:
1224
 
    default_base.push_back(make_pair(default_state, base));
 
2441
 
 
2442
do_insert:
 
2443
        default_base.push_back(make_pair(default_state, base));
1225
2444
}
1226
2445
 
1227
2446
/**
1236
2455
        st.insert(make_pair(i->second, i->first));
1237
2456
    }
1238
2457
 
1239
 
    os << "(accept, default, base):" << endl;
 
2458
    os << "size=" << default_base.size() << " (accept, default, base):  {state} -> {default state}" << endl;
1240
2459
    for (size_t i = 0; i < default_base.size(); i++) {
 
2460
        os << i << ": ";
1241
2461
        os << "(" << accept[i] << ", "
1242
2462
           << num[default_base[i].first] << ", "
1243
2463
           << default_base[i].second << ")";
1248
2468
        os << endl;
1249
2469
    }
1250
2470
 
1251
 
    os << "(next, check):" << endl;
 
2471
    os << "size=" << next_check.size() << " (next, check): {check state} -> {next state} : offset from base" << endl;
1252
2472
    for (size_t i = 0; i < next_check.size(); i++) {
1253
2473
        if (!next_check[i].second)
1254
2474
            continue;
1339
2559
template<class Iter>
1340
2560
void write_flex_table(ostream& os, int id, Iter pos, Iter end)
1341
2561
{
1342
 
    struct table_header td = { };
 
2562
    struct table_header td = { 0, 0, 0, 0 };
1343
2563
    size_t size = end - pos;
1344
2564
 
1345
2565
    td.td_id = htons(id);
1365
2585
void TransitionTable::flex_table(ostream& os, const char *name)
1366
2586
{
1367
2587
    const char th_version[] = "notflex";
1368
 
    struct table_set_header th = { };
 
2588
    struct table_set_header th = { 0, 0, 0, 0 };
1369
2589
 
1370
2590
    /**
1371
2591
     * Change the following two data types to adjust the maximum flex
1422
2642
    th.th_hsize = htonl(hsize);
1423
2643
    th.th_ssize = htonl(hsize +
1424
2644
            flex_table_size(accept.begin(), accept.end()) +
 
2645
            flex_table_size(accept2.begin(), accept2.end()) +
1425
2646
            (eq.size() ?
1426
2647
                flex_table_size(equiv_vec.begin(), equiv_vec.end()) : 0) +
1427
2648
            flex_table_size(base_vec.begin(), base_vec.end()) +
1434
2655
 
1435
2656
 
1436
2657
    write_flex_table(os, YYTD_ID_ACCEPT, accept.begin(), accept.end());
 
2658
    write_flex_table(os, YYTD_ID_ACCEPT2, accept2.begin(), accept2.end());
1437
2659
    if (eq.size())
1438
2660
        write_flex_table(os, YYTD_ID_EC, equiv_vec.begin(), equiv_vec.end());
1439
2661
    write_flex_table(os, YYTD_ID_BASE, base_vec.begin(), base_vec.end());
1475
2697
 
1476
2698
void dump_regexp_rec(ostream& os, Node *tree)
1477
2699
{
1478
 
    if (tree->left)
1479
 
        dump_regexp_rec(os, tree->left);
 
2700
    if (tree->child[0])
 
2701
        dump_regexp_rec(os, tree->child[0]);
1480
2702
    os << *tree;
1481
 
    if (tree->right)
1482
 
        dump_regexp_rec(os, tree->right);
 
2703
    if (tree->child[1])
 
2704
        dump_regexp_rec(os, tree->child[1]);
1483
2705
}
1484
2706
 
1485
2707
void dump_regexp(ostream& os, Node *tree)
1490
2712
 
1491
2713
#include <sstream>
1492
2714
#include <ext/stdio_filebuf.h>
1493
 
#include "apparmor_re.h"
1494
2715
 
1495
2716
struct aare_ruleset {
1496
2717
    int reverse;
1503
2724
    if (!container)
1504
2725
        return NULL;
1505
2726
 
1506
 
    container->root = new EpsNode();
 
2727
    container->root = NULL;
1507
2728
    container->reverse = reverse;
1508
2729
 
1509
2730
    return container;
1512
2733
extern "C" void aare_delete_ruleset(aare_ruleset_t *rules)
1513
2734
{
1514
2735
    if (rules) {
1515
 
        rules->root->release();
 
2736
        if (rules->root)
 
2737
            rules->root->release();
1516
2738
        free(rules);
1517
2739
    }
1518
2740
}
1519
2741
 
1520
 
extern "C" int aare_add_rule(aare_ruleset_t *rules, char *rule, uint32_t perms)
1521
 
{
1522
 
    Node *tree;
1523
 
    int is_rerule = NOT_RE_RULE;
1524
 
 
1525
 
    if (regexp_parse(&tree, rule, &is_rerule)) {
 
2742
static inline int diff_qualifiers(uint32_t perm1, uint32_t perm2)
 
2743
{
 
2744
        return ((perm1 & AA_EXEC_TYPE) && (perm2 & AA_EXEC_TYPE) &&
 
2745
                (perm1 & AA_EXEC_TYPE) != (perm2 & AA_EXEC_TYPE));
 
2746
}
 
2747
 
 
2748
/**
 
2749
 * Compute the permission flags that this state corresponds to. If we
 
2750
 * have any exact matches, then they override the execute and safe
 
2751
 * execute flags.
 
2752
 */
 
2753
uint32_t accept_perms(NodeSet *state, uint32_t *audit_ctl, int *error)
 
2754
{
 
2755
    uint32_t perms = 0, exact_match_perms = 0, audit = 0, exact_audit = 0,
 
2756
            quiet = 0, deny = 0;
 
2757
 
 
2758
    if (error)
 
2759
            *error = 0;
 
2760
    for (NodeSet::iterator i = state->begin(); i != state->end(); i++) {
 
2761
            MatchFlag *match;
 
2762
            if (!(match= dynamic_cast<MatchFlag *>(*i)))
 
2763
                continue;
 
2764
            if (dynamic_cast<ExactMatchFlag *>(match)) {
 
2765
                    /* exact match only ever happens with x */
 
2766
                    if (!is_merged_x_consistent(exact_match_perms,
 
2767
                                                match->flag) && error)
 
2768
                            *error = 1;;
 
2769
                    exact_match_perms |= match->flag;
 
2770
                    exact_audit |= match->audit;
 
2771
            } else if (dynamic_cast<DenyMatchFlag *>(match)) {
 
2772
                    deny |= match->flag;
 
2773
                    quiet |= match->audit;
 
2774
            } else {
 
2775
                    if (!is_merged_x_consistent(perms, match->flag) && error)
 
2776
                            *error = 1;
 
2777
                    perms |= match->flag;
 
2778
                    audit |= match->audit;
 
2779
            }
 
2780
    }
 
2781
 
 
2782
//if (audit || quiet)
 
2783
//fprintf(stderr, "perms: 0x%x, audit: 0x%x exact: 0x%x eaud: 0x%x deny: 0x%x quiet: 0x%x\n", perms, audit, exact_match_perms, exact_audit, deny, quiet);
 
2784
 
 
2785
    perms |= exact_match_perms &
 
2786
            ~(AA_USER_EXEC_TYPE | AA_OTHER_EXEC_TYPE);
 
2787
 
 
2788
    if (exact_match_perms & AA_USER_EXEC_TYPE) {
 
2789
            perms = (exact_match_perms & AA_USER_EXEC_TYPE) |
 
2790
                    (perms & ~AA_USER_EXEC_TYPE);
 
2791
            audit = (exact_audit & AA_USER_EXEC_TYPE) |
 
2792
                    (audit & ~ AA_USER_EXEC_TYPE);
 
2793
    }
 
2794
    if (exact_match_perms & AA_OTHER_EXEC_TYPE) {
 
2795
            perms = (exact_match_perms & AA_OTHER_EXEC_TYPE) |
 
2796
                    (perms & ~AA_OTHER_EXEC_TYPE);
 
2797
            audit = (exact_audit & AA_OTHER_EXEC_TYPE) |
 
2798
                    (audit & ~AA_OTHER_EXEC_TYPE);
 
2799
    }
 
2800
    if (perms & AA_USER_EXEC & deny)
 
2801
            perms &= ~AA_USER_EXEC_TYPE;
 
2802
 
 
2803
    if (perms & AA_OTHER_EXEC & deny)
 
2804
            perms &= ~AA_OTHER_EXEC_TYPE;
 
2805
 
 
2806
    perms &= ~deny;
 
2807
 
 
2808
    if (audit_ctl)
 
2809
            *audit_ctl = PACK_AUDIT_CTL(audit, quiet & deny);
 
2810
 
 
2811
// if (perms & AA_ERROR_BIT) {
 
2812
//     fprintf(stderr, "error bit 0x%x\n", perms);
 
2813
//     exit(255);
 
2814
//}
 
2815
 
 
2816
 //if (perms & AA_EXEC_BITS)
 
2817
 //fprintf(stderr, "accept perm: 0x%x\n", perms);
 
2818
 /*
 
2819
     if (perms & ~AA_VALID_PERMS)
 
2820
        yyerror(_("Internal error accumulated invalid perm 0x%llx\n"), perms);
 
2821
 */
 
2822
 
 
2823
//if (perms & AA_CHANGE_HAT)
 
2824
//     fprintf(stderr, "change_hat 0x%x\n", perms);
 
2825
 
 
2826
    if (*error)
 
2827
            fprintf(stderr, "profile has merged rule with conflicting x modifiers\n");
 
2828
 
 
2829
    return perms;
 
2830
}
 
2831
 
 
2832
extern "C" int aare_add_rule(aare_ruleset_t *rules, char *rule, int deny,
 
2833
                             uint32_t perms, uint32_t audit,  dfaflags_t flags)
 
2834
{
 
2835
        return aare_add_rule_vec(rules, deny, perms, audit, 1, &rule, flags);
 
2836
}
 
2837
 
 
2838
#define FLAGS_WIDTH 2
 
2839
#define MATCH_FLAGS_SIZE (sizeof(uint32_t) * 8 - 1)
 
2840
MatchFlag *match_flags[FLAGS_WIDTH][MATCH_FLAGS_SIZE];
 
2841
DenyMatchFlag *deny_flags[FLAGS_WIDTH][MATCH_FLAGS_SIZE];
 
2842
#define EXEC_MATCH_FLAGS_SIZE (AA_EXEC_COUNT *2 * 2 * 2)        /* double for each of ix pux, unsafe x bits * u::o */
 
2843
MatchFlag *exec_match_flags[FLAGS_WIDTH][EXEC_MATCH_FLAGS_SIZE];        /* mods + unsafe + ix + pux * u::o*/
 
2844
ExactMatchFlag *exact_match_flags[FLAGS_WIDTH][EXEC_MATCH_FLAGS_SIZE];/* mods + unsafe + ix + pux *u::o*/
 
2845
 
 
2846
extern "C" void aare_reset_matchflags(void)
 
2847
{
 
2848
        uint32_t i, j;
 
2849
#define RESET_FLAGS(group, size) { \
 
2850
        for (i = 0; i < FLAGS_WIDTH; i++) { \
 
2851
                for (j = 0; j < size; j++) { \
 
2852
                    if ((group)[i][j]) delete (group)[i][j];    \
 
2853
                        (group)[i][j] = NULL; \
 
2854
                } \
 
2855
        } \
 
2856
}
 
2857
        RESET_FLAGS(match_flags,MATCH_FLAGS_SIZE);
 
2858
        RESET_FLAGS(deny_flags,MATCH_FLAGS_SIZE);
 
2859
        RESET_FLAGS(exec_match_flags,EXEC_MATCH_FLAGS_SIZE);
 
2860
        RESET_FLAGS(exact_match_flags,EXEC_MATCH_FLAGS_SIZE);
 
2861
#undef RESET_FLAGS
 
2862
}
 
2863
 
 
2864
extern "C" int aare_add_rule_vec(aare_ruleset_t *rules, int deny,
 
2865
                                 uint32_t perms, uint32_t audit,
 
2866
                                 int count, char **rulev,
 
2867
                                 dfaflags_t flags)
 
2868
{
 
2869
    Node *tree = NULL, *accept;
 
2870
    int exact_match;
 
2871
 
 
2872
    assert(perms != 0);
 
2873
 
 
2874
    if (regexp_parse(&tree, rulev[0]))
1526
2875
        return 0;
 
2876
    for (int i = 1; i < count; i++) {
 
2877
            Node *subtree = NULL;
 
2878
            Node *node = new CharNode(0);
 
2879
            if (!node)
 
2880
                return 0;
 
2881
            tree = new CatNode(tree, node);
 
2882
            if (regexp_parse(&subtree, rulev[i]))
 
2883
                return 0;
 
2884
            tree = new CatNode(tree, subtree);
 
2885
    }
 
2886
 
 
2887
    /*
 
2888
     * Check if we have an expression with or without wildcards. This
 
2889
     * determines how exec modifiers are merged in accept_perms() based
 
2890
     * on how we split permission bitmasks here.
 
2891
     */
 
2892
    exact_match = 1;
 
2893
    for (depth_first_traversal i(tree); i; i++) {
 
2894
        if (dynamic_cast<StarNode *>(*i) ||
 
2895
            dynamic_cast<PlusNode *>(*i) ||
 
2896
            dynamic_cast<AnyCharNode *>(*i) ||
 
2897
            dynamic_cast<CharSetNode *>(*i) ||
 
2898
            dynamic_cast<NotCharSetNode *>(*i))
 
2899
                exact_match = 0;
1527
2900
    }
1528
2901
 
1529
2902
    if (rules->reverse)
1530
2903
        flip_tree(tree);
1531
 
    AcceptNode *accept = new AcceptNode(perms, is_rerule);
1532
 
    tree = new CatNode(tree, accept);
1533
 
    rules->root = new AltNode(rules->root, tree);
 
2904
 
 
2905
 
 
2906
/* 0x7f == 4 bits x mods + 1 bit unsafe mask + 1 bit ix, + 1 pux after shift */
 
2907
#define EXTRACT_X_INDEX(perm, shift) (((perm) >> (shift + 7)) & 0x7f)
 
2908
 
 
2909
//if (perms & ALL_AA_EXEC_TYPE && (!perms & AA_EXEC_BITS))
 
2910
//      fprintf(stderr, "adding X rule without MAY_EXEC: 0x%x %s\n", perms, rulev[0]);
 
2911
 
 
2912
//if (perms & ALL_EXEC_TYPE)
 
2913
//    fprintf(stderr, "adding X rule %s 0x%x\n", rulev[0], perms);
 
2914
 
 
2915
//if (audit)
 
2916
//fprintf(stderr, "adding rule with audit bits set: 0x%x %s\n", audit, rulev[0]);
 
2917
 
 
2918
//if (perms & AA_CHANGE_HAT)
 
2919
//    fprintf(stderr, "adding change_hat rule %s\n", rulev[0]);
 
2920
 
 
2921
/* the permissions set is assumed to be non-empty if any audit
 
2922
 * bits are specified */
 
2923
    accept = NULL;
 
2924
    for (unsigned int n = 0; perms && n < (sizeof(perms) * 8) ; n++) {
 
2925
        uint32_t mask = 1 << n;
 
2926
 
 
2927
        if (perms & mask) {
 
2928
            int ai = audit & mask ? 1 : 0;
 
2929
            perms &= ~mask;
 
2930
 
 
2931
            Node *flag;
 
2932
            if (mask & ALL_AA_EXEC_TYPE)
 
2933
                    /* these cases are covered by EXEC_BITS */
 
2934
                    continue;
 
2935
            if (deny) {
 
2936
                    if (deny_flags[ai][n]) {
 
2937
                            flag = deny_flags[ai][n];
 
2938
                    } else {
 
2939
//fprintf(stderr, "Adding deny ai %d mask 0x%x audit 0x%x\n", ai, mask, audit & mask);
 
2940
                            deny_flags[ai][n] = new DenyMatchFlag(mask, audit&mask);
 
2941
                            flag = deny_flags[ai][n];
 
2942
                    }
 
2943
            } else if (mask & AA_EXEC_BITS) {
 
2944
                    uint32_t eperm = 0;
 
2945
                    uint32_t index = 0;
 
2946
                    if (mask & AA_USER_EXEC) {
 
2947
                            eperm = mask | (perms & AA_USER_EXEC_TYPE);
 
2948
                            index = EXTRACT_X_INDEX(eperm, AA_USER_SHIFT);
 
2949
                    } else {
 
2950
                            eperm = mask | (perms & AA_OTHER_EXEC_TYPE);
 
2951
                            index = EXTRACT_X_INDEX(eperm, AA_OTHER_SHIFT) + (AA_EXEC_COUNT << 2);
 
2952
                    }
 
2953
//fprintf(stderr, "index %d eperm 0x%x\n", index, eperm);
 
2954
                    if (exact_match) {
 
2955
                            if (exact_match_flags[ai][index]) {
 
2956
                                    flag = exact_match_flags[ai][index];
 
2957
                            } else {
 
2958
                                    exact_match_flags[ai][index] = new ExactMatchFlag(eperm, audit&mask);
 
2959
                                    flag = exact_match_flags[ai][index];
 
2960
                            }
 
2961
                    } else {
 
2962
                            if (exec_match_flags[ai][index]) {
 
2963
                                    flag = exec_match_flags[ai][index];
 
2964
                            } else {
 
2965
                                    exec_match_flags[ai][index] = new MatchFlag(eperm, audit&mask);
 
2966
                                    flag = exec_match_flags[ai][index];
 
2967
                            }
 
2968
                    }
 
2969
            } else {
 
2970
                    if (match_flags[ai][n]) {
 
2971
                        flag = match_flags[ai][n];
 
2972
                    } else {
 
2973
                            match_flags[ai][n] = new MatchFlag(mask, audit&mask);
 
2974
                            flag = match_flags[ai][n];
 
2975
                    }
 
2976
            }
 
2977
            if (accept)
 
2978
                    accept = new AltNode(accept, flag);
 
2979
            else
 
2980
                    accept = flag;
 
2981
        }
 
2982
    }
 
2983
 
 
2984
    if (flags & DFA_DUMP_RULE_EXPR) {
 
2985
            cerr << "rule: ";
 
2986
            cerr << rulev[0];
 
2987
            for (int i = 1; i < count; i++) {
 
2988
                    cerr << "\\x00";
 
2989
                    cerr << rulev[i];
 
2990
            }
 
2991
            cerr << "  ->  ";
 
2992
            tree->dump(cerr);
 
2993
            cerr << "\n\n";
 
2994
    }
 
2995
 
 
2996
    if (rules->root)
 
2997
        rules->root = new AltNode(rules->root, new CatNode(tree, accept));
 
2998
    else
 
2999
        rules->root = new CatNode(tree, accept);
1534
3000
 
1535
3001
    return 1;
 
3002
 
1536
3003
}
1537
3004
 
1538
3005
/* create a dfa from the ruleset
1539
3006
 * returns: buffer contain dfa tables, @size set to the size of the tables
1540
3007
 *          else NULL on failure
1541
3008
 */
1542
 
extern "C" void *aare_create_dfa(aare_ruleset_t *rules, int equiv_classes,
1543
 
                                 size_t *size)
 
3009
extern "C" void *aare_create_dfa(aare_ruleset_t *rules, size_t *size, dfaflags_t flags)
1544
3010
{
1545
3011
    char *buffer = NULL;
1546
3012
 
1547
3013
    label_nodes(rules->root);
1548
 
    DFA dfa(rules->root);
1549
 
    map<uchar, uchar> eq;
1550
 
    if (equiv_classes) {
1551
 
        eq = dfa.equivalence_classes();
1552
 
        dfa.apply_equivalence_classes(eq);
 
3014
    if (flags & DFA_DUMP_TREE) {
 
3015
            cerr << "\nDFA: Expression Tree\n";
 
3016
            rules->root->dump(cerr);
 
3017
            cerr << "\n\n";
1553
3018
    }
1554
3019
 
1555
 
    if (dfa.verify_perms()) {
1556
 
        *size = 0;
1557
 
        return NULL;
 
3020
    if (flags & DFA_CONTROL_TREE_SIMPLE) {
 
3021
            rules->root = simplify_tree(rules->root, flags);
 
3022
 
 
3023
            if (flags & DFA_DUMP_SIMPLE_TREE) {
 
3024
                    cerr << "\nDFA: Simplified Expression Tree\n";
 
3025
                    rules->root->dump(cerr);
 
3026
                    cerr << "\n\n";
 
3027
            }
1558
3028
    }
1559
3029
 
1560
3030
    stringstream stream;
1561
 
    TransitionTable transition_table(dfa, eq);
1562
 
    transition_table.flex_table(stream, "");
 
3031
    try {
 
3032
            DFA dfa(rules->root, flags);
 
3033
            if (flags & DFA_DUMP_UNIQ_PERMS)
 
3034
                    dfa.dump_uniq_perms("dfa");
 
3035
 
 
3036
            if (flags & DFA_CONTROL_MINIMIZE) {
 
3037
                    dfa.minimize(flags);
 
3038
 
 
3039
                    if (flags & DFA_DUMP_MIN_UNIQ_PERMS)
 
3040
                            dfa.dump_uniq_perms("minimized dfa");
 
3041
            }
 
3042
            if (flags & DFA_CONTROL_REMOVE_UNREACHABLE)
 
3043
                    dfa.remove_unreachable(flags);
 
3044
 
 
3045
            if (flags & DFA_DUMP_STATES)
 
3046
                    dfa.dump(cerr);
 
3047
 
 
3048
            if (flags & DFA_DUMP_GRAPH)
 
3049
                    dfa.dump_dot_graph(cerr);
 
3050
 
 
3051
            map<uchar, uchar> eq;
 
3052
            if (flags & DFA_CONTROL_EQUIV) {
 
3053
                    eq = dfa.equivalence_classes(flags);
 
3054
                    dfa.apply_equivalence_classes(eq);
 
3055
 
 
3056
                    if (flags & DFA_DUMP_EQUIV) {
 
3057
                            cerr << "\nDFA equivalence class\n";
 
3058
                            dump_equivalence_classes(cerr, eq);
 
3059
                    }
 
3060
            } else if (flags & DFA_DUMP_EQUIV)
 
3061
                    cerr << "\nDFA did not generate an equivalence class\n";
 
3062
 
 
3063
            TransitionTable transition_table(dfa, eq, flags);
 
3064
            if (flags & DFA_DUMP_TRANS_TABLE)
 
3065
                    transition_table.dump(cerr);
 
3066
            transition_table.flex_table(stream, "");
 
3067
    } catch (int error) {
 
3068
            *size = 0;
 
3069
            return NULL;
 
3070
    }
1563
3071
 
1564
3072
    stringbuf *buf = stream.rdbuf();
1565
3073