← Back to branch summary

~ubuntu-branches/ubuntu/saucy/augeas/saucy

« back to all changes in this revision

Viewing changes to src/lens.c

  • Committer: Bazaar Package Importer
  • Author(s): Nicolas Valcárcel Scerpella (Canonical)
  • Date: 2010-04-23 09:28:28 UTC
  • mfrom: (1.2.11 upstream)
  • Revision ID: james.westby@ubuntu.com-20100423092828-lx8lripknvhkawf3
Tags: 0.7.1-2
http://bugs.debian.org/578880
https://launchpad.net/bugs/566803
* Remove libaugeas0 from augeas-lenses depends. (Closes: #578880)
* Change iptables config location. (LP: #566803)

Show diffs side-by-side

added added

removed removed

Lines of Context:
src/lens.c
54
54
 
55
55
/* Lens names for pretty printing */
56
56
static const char *const tags[] = {
57
 
    "del", "store", "key", "label", "seq", "counter", "concat", "union",
 
57
    "del", "store", "value", "key", "label", "seq", "counter",
 
58
    "concat", "union",
58
59
    "subtree", "star", "maybe", "rec"
59
60
};
60
61
 
73
74
    return result;
74
75
}
75
76
 
 
77
#define BUG_LENS_TAG(lns)  bug_lens_tag(lns, __FILE__, __LINE__)
 
78
 
 
79
static void bug_lens_tag(struct lens *lens, const char *file, int lineno) {
 
80
    char *s = format_lens(lens);
 
81
 
 
82
    if (lens != NULL && lens->info != NULL && lens->info->error != NULL) {
 
83
        bug_on(lens->info->error, file, lineno, "Unexpected lens tag %s", s);
 
84
    } else {
 
85
        /* We are really screwed */
 
86
        assert(0);
 
87
    }
 
88
    free(s);
 
89
    return;
 
90
}
 
91
 
76
92
/* Construct a finite automaton from REGEXP and return it in *FA.
77
93
 *
78
94
 * Return NULL if REGEXP is valid, if the regexp REGEXP has syntax errors,
156
172
    lens->nchildren += (l2->tag == tag) ? l2->nchildren : 1;
157
173
 
158
174
    lens->recursive = l1->recursive || l2->recursive;
 
175
    lens->rec_internal = l1->rec_internal || l2->rec_internal;
159
176
 
160
177
    if (ALLOC_N(lens->children, lens->nchildren) < 0) {
161
178
        lens->nchildren = 0;
186
203
    if (ALLOC_N(types, lens->nchildren) < 0)
187
204
        goto error;
188
205
 
189
 
    if (!lens->recursive) {
 
206
    if (! lens->rec_internal) {
 
207
        /* Inside a recursive lens, we assign types with lns_check_rec
 
208
         * once we know the entire lens */
190
209
        for (int t=0; t < ntypes; t++) {
 
210
            if (lens->recursive && t == CTYPE)
 
211
                continue;
191
212
            for (int i=0; i < lens->nchildren; i++)
192
213
                types[i] = ltype(lens->children[i], t);
193
214
            ltype(lens, t) = (*combinator)(info, lens->nchildren, types);
194
215
        }
195
216
    }
196
 
 
197
217
    FREE(types);
198
218
 
199
219
    for (int i=0; i < lens->nchildren; i++)
200
 
        assert(tag != lens->children[i]->tag);
 
220
        ensure(tag != lens->children[i]->tag, lens->info);
201
221
 
202
222
    return lens;
203
223
 error:
220
240
    int recursive = l1->recursive || l2->recursive;
221
241
    int ctype_nullable = l1->ctype_nullable || l2->ctype_nullable;
222
242
 
223
 
    if (check && !recursive) {
 
243
    if (check) {
224
244
        struct value *exn = typecheck_union(info, l1, l2);
225
245
        if (exn != NULL)
226
246
            return exn;
240
260
    int recursive = l1->recursive || l2->recursive;
241
261
    int ctype_nullable = l1->ctype_nullable && l2->ctype_nullable;
242
262
 
243
 
    if (check && !recursive) {
 
263
    if (check) {
244
264
        struct value *exn = typecheck_concat(info, l1, l2);
245
 
        if (exn != NULL) {
 
265
        if (exn != NULL)
246
266
            return exn;
247
 
        }
248
267
    }
249
268
    if (l1->value && l2->value) {
250
269
        return make_exn_value(info, "Multiple stores in concat");
313
332
        lens->atype = subtree_atype(info, l->ktype, l->vtype);
314
333
    lens->value = lens->key = 0;
315
334
    lens->recursive = l->recursive;
 
335
    lens->rec_internal = l->rec_internal;
316
336
    if (! l->recursive)
317
337
        lens->ctype_nullable = l->ctype_nullable;
318
338
    return make_lens_value(lens);
321
341
struct value *lns_make_star(struct info *info, struct lens *l, int check) {
322
342
    struct lens *lens;
323
343
 
324
 
    if (check && !l->recursive) {
 
344
    if (check) {
325
345
        struct value *exn = typecheck_iter(info, l);
326
 
        if (exn != NULL) {
 
346
        if (exn != NULL)
327
347
            return exn;
328
 
        }
329
348
    }
330
349
    if (l->value) {
331
350
        return make_exn_value(info, "Multiple stores in iteration");
339
358
        ltype(lens, t) = regexp_iter(info, ltype(l, t), 0, -1);
340
359
    }
341
360
    lens->recursive = l->recursive;
 
361
    lens->rec_internal = l->rec_internal;
342
362
    lens->ctype_nullable = 1;
343
363
    return make_lens_value(lens);
344
364
}
358
378
struct value *lns_make_maybe(struct info *info, struct lens *l, int check) {
359
379
    struct lens *lens;
360
380
 
361
 
    if (check && !l->recursive) {
 
381
    if (check) {
362
382
        struct value *exn = typecheck_maybe(info, l);
363
 
        if (exn != NULL) {
 
383
        if (exn != NULL)
364
384
            return exn;
365
 
        }
366
385
    }
367
386
    lens = make_lens_unop(L_MAYBE, info, l);
368
387
    for (int t=0; t < ntypes; t++)
370
389
    lens->value = l->value;
371
390
    lens->key = l->key;
372
391
    lens->recursive = l->recursive;
 
392
    lens->rec_internal = l->rec_internal;
373
393
    lens->ctype_nullable = 1;
374
394
    return make_lens_value(lens);
375
395
}
392
412
 
393
413
static struct regexp *restrict_regexp(struct regexp *r) {
394
414
    char *nre = NULL;
 
415
    struct regexp *result = NULL;
395
416
    size_t nre_len;
396
417
    int ret;
397
418
 
398
419
    ret = fa_restrict_alphabet(r->pattern->str, strlen(r->pattern->str),
399
420
                               &nre, &nre_len,
400
421
                               RESERVED_FROM, RESERVED_TO);
401
 
    assert(nre_len == strlen(nre));
402
 
    // FIXME: Tell the user what's wrong
403
 
    if (ret != 0)
404
 
        return NULL;
 
422
    ERR_NOMEM(ret == REG_ESPACE || ret < 0, r->info);
 
423
    BUG_ON(ret != 0, r->info, NULL);
 
424
    ensure(nre_len == strlen(nre), r->info);
405
425
 
406
426
    ret = regexp_c_locale(&nre, &nre_len);
407
 
    if (ret < 0) {
408
 
        free(nre);
409
 
        return NULL;
410
 
    }
 
427
    ERR_NOMEM(ret < 0, r->info);
411
428
 
412
 
    r = make_regexp(r->info, nre, r->nocase);
413
 
    if (regexp_compile(r) != 0)
414
 
        abort();
415
 
    return r;
 
429
    result = make_regexp(r->info, nre, r->nocase);
 
430
    nre = NULL;
 
431
    BUG_ON(regexp_compile(result) != 0, r->info,
 
432
           "Could not compile restricted regexp");
 
433
 done:
 
434
    free(nre);
 
435
    return result;
 
436
 error:
 
437
    unref(result, regexp);
 
438
    goto done;
416
439
}
417
440
 
418
441
struct value *lns_make_prim(enum lens_tag tag, struct info *info,
472
495
    lens->regexp = regexp;
473
496
    lens->string = string;
474
497
    lens->key = (tag == L_KEY || tag == L_LABEL || tag == L_SEQ);
475
 
    lens->value = (tag == L_STORE);
476
 
    lens->consumes_value = (tag == L_STORE);
 
498
    lens->value = (tag == L_STORE || tag == L_VALUE);
 
499
    lens->consumes_value = (tag == L_STORE || tag == L_VALUE);
477
500
    lens->atype = regexp_make_empty(info);
478
501
    /* Set the ctype */
479
502
    if (tag == L_DEL || tag == L_STORE || tag == L_KEY) {
480
503
        lens->ctype = ref(regexp);
481
504
        lens->ctype_nullable = regexp_matches_empty(lens->ctype);
482
 
    } else if (tag == L_LABEL || tag == L_SEQ || tag == L_COUNTER) {
 
505
    } else if (tag == L_LABEL || tag == L_VALUE
 
506
               || tag == L_SEQ || tag == L_COUNTER) {
483
507
        lens->ctype = regexp_make_empty(info);
484
508
        lens->ctype_nullable = 1;
485
509
    } else {
486
 
        assert(0);
 
510
        BUG_LENS_TAG(lens);
 
511
        goto error;
487
512
    }
488
513
 
489
514
 
504
529
    /* Set the vtype */
505
530
    if (tag == L_STORE) {
506
531
        lens->vtype = restrict_regexp(lens->regexp);
 
532
    } else if (tag == L_VALUE) {
 
533
        lens->vtype = make_regexp_literal(info, lens->string->str);
507
534
    }
508
535
 
509
536
    return make_lens_value(lens);
586
613
    return exn;
587
614
}
588
615
 
589
 
static struct value *ambig_check(struct info *info,
590
 
                                 struct fa *fa1, struct fa *fa2,
591
 
                                 struct regexp *r1, struct regexp *r2,
592
 
                                 const char *msg, bool iterated) {
 
616
static struct value *
 
617
ambig_check(struct info *info, struct fa *fa1, struct fa *fa2,
 
618
            enum lens_type typ,  struct lens *l1, struct lens *l2,
 
619
            const char *msg, bool iterated) {
593
620
    char *upv, *pv, *v;
594
621
    size_t upv_len;
595
622
    struct value *exn = NULL;
607
634
    }
608
635
 
609
636
    if (upv != NULL) {
610
 
        char *e_u = escape(upv, pv - upv);
611
 
        char *e_up = escape(upv, v - upv);
612
 
        char *e_upv = escape(upv, -1);
613
 
        char *e_pv = escape(pv, -1);
614
 
        char *e_v = escape(v, -1);
615
 
        char *s1 = regexp_escape(r1);
616
 
        char *s2 = regexp_escape(r2);
 
637
        char *e_u, *e_up, *e_upv, *e_pv, *e_v;
 
638
        char *s1, *s2;
 
639
 
 
640
        if (typ == ATYPE) {
 
641
            e_u = enc_format(upv, pv - upv);
 
642
            e_up = enc_format(upv, v - upv);
 
643
            e_upv = enc_format(upv, upv_len);
 
644
            e_pv = enc_format(pv, strlen(pv));
 
645
            e_v = enc_format(v, strlen(v));
 
646
            lns_format_atype(l1, &s1);
 
647
            lns_format_atype(l2, &s2);
 
648
        } else {
 
649
            e_u = escape(upv, pv - upv);
 
650
            e_up = escape(upv, v - upv);
 
651
            e_upv = escape(upv, -1);
 
652
            e_pv = escape(pv, -1);
 
653
            e_v = escape(v, -1);
 
654
            s1 = regexp_escape(ltype(l1, typ));
 
655
            s2 = regexp_escape(ltype(l2, typ));
 
656
        }
617
657
        exn = make_exn_value(ref(info), "%s", msg);
618
658
        if (iterated) {
619
659
            exn_printf_line(exn, "  Iterated regexp: /%s/", s1);
637
677
    return exn;
638
678
}
639
679
 
640
 
static struct value *ambig_concat_check(struct info *info, const char *msg,
641
 
                                        struct regexp *r1, struct regexp *r2) {
 
680
static struct value *
 
681
ambig_concat_check(struct info *info, const char *msg,
 
682
                   enum lens_type typ, struct lens *l1, struct lens *l2) {
642
683
    struct fa *fa1 = NULL;
643
684
    struct fa *fa2 = NULL;
644
685
    struct value *result = NULL;
 
686
    struct regexp *r1 = ltype(l1, typ);
 
687
    struct regexp *r2 = ltype(l2, typ);
645
688
 
646
689
    if (r1 == NULL || r2 == NULL)
647
690
        return NULL;
654
697
    if (result != NULL)
655
698
        goto done;
656
699
 
657
 
    result = ambig_check(info, fa1, fa2, r1, r2, msg, false);
 
700
    result = ambig_check(info, fa1, fa2, typ, l1, l2, msg, false);
658
701
 done:
659
702
    fa_free(fa1);
660
703
    fa_free(fa2);
666
709
    struct value *result = NULL;
667
710
 
668
711
    result = ambig_concat_check(info, "ambiguous concatenation",
669
 
                                l1->ctype, l2->ctype);
 
712
                                CTYPE, l1, l2);
670
713
    if (result == NULL) {
671
714
        result = ambig_concat_check(info, "ambiguous tree concatenation",
672
 
                                    l1->atype, l2->atype);
 
715
                                    ATYPE, l1, l2);
673
716
    }
674
717
    if (result != NULL) {
675
718
        char *fi = format_info(l1->info);
682
725
    return result;
683
726
}
684
727
 
685
 
static struct value *ambig_iter_check(struct info *info, const char *msg,
686
 
                                      struct regexp *r) {
 
728
static struct value *
 
729
ambig_iter_check(struct info *info, const char *msg,
 
730
                 enum lens_type typ, struct lens *l) {
687
731
    struct fa *fas = NULL, *fa = NULL;
688
732
    struct value *result = NULL;
 
733
    struct regexp *r = ltype(l, typ);
689
734
 
690
735
    if (r == NULL)
691
736
        return NULL;
696
741
 
697
742
    fas = fa_iter(fa, 0, -1);
698
743
 
699
 
    result = ambig_check(info, fa, fas, r, r, msg, true);
 
744
    result = ambig_check(info, fa, fas, typ, l, l, msg, true);
700
745
 
701
746
 done:
702
747
    fa_free(fa);
707
752
static struct value *typecheck_iter(struct info *info, struct lens *l) {
708
753
    struct value *result = NULL;
709
754
 
710
 
    result = ambig_iter_check(info, "ambiguous iteration", l->ctype);
 
755
    result = ambig_iter_check(info, "ambiguous iteration", CTYPE, l);
711
756
    if (result == NULL) {
712
 
        result = ambig_iter_check(info, "ambiguous tree iteration", l->atype);
 
757
        result = ambig_iter_check(info, "ambiguous tree iteration", ATYPE, l);
713
758
    }
714
759
    if (result != NULL) {
715
760
        char *fi = format_info(l->info);
723
768
    /* Check (r)? as (<e>|r) where <e> is the empty language */
724
769
    struct value *exn = NULL;
725
770
 
726
 
    if (regexp_matches_empty(l->ctype)) {
 
771
    if (l->ctype != NULL && regexp_matches_empty(l->ctype)) {
727
772
        exn = make_exn_value(ref(info),
728
773
                "illegal optional expression: /%s/ matches the empty word",
729
774
                l->ctype->pattern->str);
736
781
           depending on whether the current node has a non NULL value or not
737
782
    */
738
783
    if (exn == NULL && ! l->consumes_value) {
739
 
        if (regexp_matches_empty(l->atype)) {
 
784
        if (l->atype != NULL && regexp_matches_empty(l->atype)) {
740
785
            exn = make_exn_value(ref(info),
741
786
               "optional expression matches the empty tree but does not consume a value");
742
787
        }
747
792
void free_lens(struct lens *lens) {
748
793
    if (lens == NULL)
749
794
        return;
750
 
    assert(lens->ref == 0);
 
795
    ensure(lens->ref == 0, lens->info);
751
796
 
752
797
    switch (lens->tag) {
753
798
    case L_DEL:
761
806
    case L_LABEL:
762
807
    case L_SEQ:
763
808
    case L_COUNTER:
 
809
    case L_VALUE:
764
810
        unref(lens->string, string);
765
811
        break;
766
812
    case L_SUBTREE:
781
827
        }
782
828
        break;
783
829
    default:
784
 
        assert(0);
 
830
        BUG_LENS_TAG(lens);
785
831
        break;
786
832
    }
787
833
 
791
837
    unref(lens->info, info);
792
838
 
793
839
    free(lens);
 
840
 error:
 
841
    return;
794
842
}
795
843
 
796
844
void lens_release(struct lens *lens) {
1019
1067
    return result;
1020
1068
}
1021
1069
 
 
1070
static int lns_format_rec_atype(struct lens *l, char **buf) {
 
1071
    int r;
 
1072
 
 
1073
    if (l->rec_internal) {
 
1074
        *buf = strdup("<<rec>>");
 
1075
        return (*buf == NULL) ? -1 : 0;
 
1076
    }
 
1077
 
 
1078
    char *c = NULL;
 
1079
    r = lns_format_atype(l->body, &c);
 
1080
    if (r < 0)
 
1081
        return -1;
 
1082
    r = xasprintf(buf, "<<rec:%s>>", c);
 
1083
    free(c);
 
1084
    return (r < 0) ? -1 : 0;
 
1085
}
 
1086
 
1022
1087
int lns_format_atype(struct lens *l, char **buf) {
1023
1088
    *buf = NULL;
1024
1089
 
1027
1092
    case L_STORE:
1028
1093
    case L_KEY:
1029
1094
    case L_LABEL:
 
1095
    case L_VALUE:
1030
1096
    case L_SEQ:
1031
1097
    case L_COUNTER:
1032
1098
        *buf = strdup("");
1047
1113
    case L_UNION:
1048
1114
        return lns_format_union_atype(l, buf);
1049
1115
        break;
 
1116
    case L_REC:
 
1117
        return lns_format_rec_atype(l, buf);
 
1118
        break;
1050
1119
    default:
1051
 
        assert(0);
 
1120
        BUG_LENS_TAG(l);
1052
1121
        break;
1053
1122
    };
1054
 
 
 
1123
    return -1;
1055
1124
}
1056
1125
 
1057
1126
/*
1060
1129
struct value *lns_make_rec(struct info *info) {
1061
1130
    struct lens *l = make_lens(L_REC, info);
1062
1131
    l->recursive = 1;
 
1132
    l->rec_internal = 1;
1063
1133
 
1064
1134
    return make_lens_value(l);
1065
1135
}
1379
1449
            break;
1380
1450
        }
1381
1451
        default:
1382
 
            assert(0);
 
1452
            BUG_ON(true, rtn->info, "Unexpected lens type %d", rtn->lens_type);
 
1453
            break;
1383
1454
        }
1384
1455
        break;
1385
1456
    case L_MAYBE:
1399
1470
        RTN_BAIL(rtn);
1400
1471
        break;
1401
1472
    default:
1402
 
        assert(0);
 
1473
        BUG_LENS_TAG(l);
 
1474
        break;
1403
1475
    }
1404
1476
 error:
1405
1477
    return;
1648
1720
        struct regexp *loop = NULL;
1649
1721
        for (int i=0; i < s->ntrans; i++) {
1650
1722
            if (s == s->trans[i].to) {
1651
 
                assert(loop == NULL);
 
1723
                ensure(loop == NULL, rtn->info);
1652
1724
                loop = s->trans[i].re;
1653
1725
            }
1654
1726
        }
1675
1747
    struct regexp *result = NULL;
1676
1748
    for (int i=0; i < prod->start->ntrans; i++) {
1677
1749
        if (prod->start->trans[i].to == prod->end) {
1678
 
            assert(result == NULL);
 
1750
            ensure(result == NULL, rtn->info);
1679
1751
            result = ref(prod->start->trans[i].re);
1680
1752
        }
1681
1753
    }
1731
1803
        /* Nothing to do */
1732
1804
        break;
1733
1805
    default:
1734
 
        assert(0);
 
1806
        BUG_LENS_TAG(l);
 
1807
        break;
1735
1808
    }
1736
1809
 
1737
1810
 error:
1766
1839
    struct value *exn = NULL;
1767
1840
    struct lens *acc = NULL;
1768
1841
 
1769
 
    assert(l->tag == L_CONCAT || l->tag == L_UNION);
 
1842
    ensure(l->tag == L_CONCAT || l->tag == L_UNION, l->info);
1770
1843
    for (int i=0; i < l->nchildren; i++) {
1771
1844
        exn = typecheck(l->children[i], check);
1772
1845
        if (exn != NULL)
1779
1852
        exn = (*make)(info, acc, ref(l->children[i]), check);
1780
1853
        if (EXN(exn))
1781
1854
            goto error;
1782
 
        assert(exn->tag == V_LENS);
 
1855
        ensure(exn->tag == V_LENS, l->info);
1783
1856
        acc = ref(exn->lens);
1784
1857
        unref(exn, value);
1785
1858
    }
1825
1898
        /* Nothing to do */
1826
1899
        break;
1827
1900
    default:
1828
 
        assert(0);
 
1901
        BUG_LENS_TAG(l);
 
1902
        break;
1829
1903
    }
1830
1904
 
1831
1905
    return exn;
1929
2003
        nullable = lens->body->ctype_nullable;
1930
2004
        break;
1931
2005
    default:
1932
 
        assert(0);
 
2006
        BUG_LENS_TAG(lens);
 
2007
        break;
1933
2008
    }
1934
2009
    if (*exn != NULL)
1935
2010
        return 0;
1945
2020
                            int check) {
1946
2021
    /* The types in the order of approximation */
1947
2022
    static const enum lens_type types[] = { KTYPE, VTYPE, ATYPE };
1948
 
 
1949
 
    assert(rec->tag == L_REC);
1950
 
    assert(body->recursive);
1951
2023
    struct value *result = NULL;
1952
2024
 
 
2025
    ensure(rec->tag == L_REC, info);
 
2026
    ensure(body->recursive, info);
 
2027
    ensure(rec->rec_internal, info);
 
2028
 
1953
2029
    /* To help memory management, we avoid the cycle inherent ina recursive
1954
2030
     * lens by using two instances of an L_REC lens. One is marked with
1955
2031
     * rec_internal, and used inside the body of the lens. The other is the
1958
2034
     * The internal instance of the recursive lens is REC, the external one
1959
2035
     * is TOP, constructed below
1960
2036
     */
1961
 
    rec->rec_internal = 1;
1962
2037
    rec->body = body;                          /* REC does not own BODY */
1963
2038
 
1964
2039
    for (int i=0; i < ARRAY_CARDINALITY(types); i++) {
1967
2042
    }
1968
2043
 
1969
2044
    if (rec->atype == NULL) {
1970
 
        result = make_exn_value(rec->info,
 
2045
        result = make_exn_value(ref(rec->info),
1971
2046
        "recursive lens generates the empty language for its %s",
1972
2047
         rec->ctype == NULL ? "ctype" : "atype");
1973
2048
        goto error;
1986
2061
    if (result != NULL)
1987
2062
        goto error;
1988
2063
 
1989
 
    struct jmt *jmt = jmt_build(rec);
1990
 
    ERR_BAIL(info);
1991
 
 
1992
2064
    result = lns_make_rec(ref(rec->info));
1993
2065
    struct lens *top = result->lens;
1994
2066
    for (int t=0; t < ntypes; t++)
1999
2071
    top->ctype_nullable = rec->ctype_nullable;
2000
2072
    top->body = ref(body);
2001
2073
    top->alias = rec;
 
2074
    top->rec_internal = 0;
2002
2075
    rec->alias = top;
2003
2076
 
2004
 
    top->jmt = jmt;
 
2077
    top->jmt = jmt_build(top);
 
2078
    ERR_BAIL(info);
2005
2079
 
2006
2080
    return result;
2007
2081
 error:
 
2082
    if (result != NULL && result->tag != V_EXN)
 
2083
        unref(result, value);
2008
2084
    if (result == NULL)
2009
2085
        result = exn_error();
2010
2086
    return result;