From 655ca0dfc401ab291a82dd8fbc99ce7548b90b11 Mon Sep 17 00:00:00 2001 From: Vsevolod Stakhov Date: Mon, 5 Aug 2013 17:50:05 +0100 Subject: [PATCH] Start rcl parser implementation. --- config.h.in | 2 +- contrib/uthash/utlist.h | 757 ++++++++++++++++++++++++++++++++++++++++ src/rcl/rcl.h | 8 + src/rcl/rcl_internal.h | 45 +++ src/rcl/rcl_parser.c | 298 ++++++++++++++++ 5 files changed, 1109 insertions(+), 1 deletion(-) create mode 100644 contrib/uthash/utlist.h diff --git a/config.h.in b/config.h.in index 9e2995dd6..9dbc84c9b 100644 --- a/config.h.in +++ b/config.h.in @@ -202,7 +202,7 @@ #if (defined(__i386__) || defined(__x86_64__) || defined(_M_IX86)) /* Use murmur hash for UTHash for these platforms */ -#define HASH_FUNCTION MUR +#define HASH_FUNCTION HASH_MUR #define HASH_USING_NO_STRICT_ALIASING #endif /* Configure allocator */ diff --git a/contrib/uthash/utlist.h b/contrib/uthash/utlist.h new file mode 100644 index 000000000..c82dd916e --- /dev/null +++ b/contrib/uthash/utlist.h @@ -0,0 +1,757 @@ +/* +Copyright (c) 2007-2013, Troy D. Hanson http://troydhanson.github.com/uthash/ +All rights reserved. + +Redistribution and use in source and binary forms, with or without +modification, are permitted provided that the following conditions are met: + + * Redistributions of source code must retain the above copyright + notice, this list of conditions and the following disclaimer. + +THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS +IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED +TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A +PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER +OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, +EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, +PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR +PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF +LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING +NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS +SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. +*/ + +#ifndef UTLIST_H +#define UTLIST_H + +#define UTLIST_VERSION 1.9.8 + +#include + +/* + * This file contains macros to manipulate singly and doubly-linked lists. + * + * 1. LL_ macros: singly-linked lists. + * 2. DL_ macros: doubly-linked lists. + * 3. CDL_ macros: circular doubly-linked lists. + * + * To use singly-linked lists, your structure must have a "next" pointer. + * To use doubly-linked lists, your structure must "prev" and "next" pointers. + * Either way, the pointer to the head of the list must be initialized to NULL. + * + * ----------------.EXAMPLE ------------------------- + * struct item { + * int id; + * struct item *prev, *next; + * } + * + * struct item *list = NULL: + * + * int main() { + * struct item *item; + * ... allocate and populate item ... + * DL_APPEND(list, item); + * } + * -------------------------------------------------- + * + * For doubly-linked lists, the append and delete macros are O(1) + * For singly-linked lists, append and delete are O(n) but prepend is O(1) + * The sort macro is O(n log(n)) for all types of single/double/circular lists. + */ + +/* These macros use decltype or the earlier __typeof GNU extension. + As decltype is only available in newer compilers (VS2010 or gcc 4.3+ + when compiling c++ code), this code uses whatever method is needed + or, for VS2008 where neither is available, uses casting workarounds. */ +#ifdef _MSC_VER /* MS compiler */ +#if _MSC_VER >= 1600 && defined(__cplusplus) /* VS2010 or newer in C++ mode */ +#define LDECLTYPE(x) decltype(x) +#else /* VS2008 or older (or VS2010 in C mode) */ +#define NO_DECLTYPE +#define LDECLTYPE(x) char* +#endif +#elif defined(__ICCARM__) +#define NO_DECLTYPE +#define LDECLTYPE(x) char* +#else /* GNU, Sun and other compilers */ +#define LDECLTYPE(x) __typeof(x) +#endif + +/* for VS2008 we use some workarounds to get around the lack of decltype, + * namely, we always reassign our tmp variable to the list head if we need + * to dereference its prev/next pointers, and save/restore the real head.*/ +#ifdef NO_DECLTYPE +#define _SV(elt,list) _tmp = (char*)(list); {char **_alias = (char**)&(list); *_alias = (elt); } +#define _NEXT(elt,list,next) ((char*)((list)->next)) +#define _NEXTASGN(elt,list,to,next) { char **_alias = (char**)&((list)->next); *_alias=(char*)(to); } +/* #define _PREV(elt,list,prev) ((char*)((list)->prev)) */ +#define _PREVASGN(elt,list,to,prev) { char **_alias = (char**)&((list)->prev); *_alias=(char*)(to); } +#define _RS(list) { char **_alias = (char**)&(list); *_alias=_tmp; } +#define _CASTASGN(a,b) { char **_alias = (char**)&(a); *_alias=(char*)(b); } +#else +#define _SV(elt,list) +#define _NEXT(elt,list,next) ((elt)->next) +#define _NEXTASGN(elt,list,to,next) ((elt)->next)=(to) +/* #define _PREV(elt,list,prev) ((elt)->prev) */ +#define _PREVASGN(elt,list,to,prev) ((elt)->prev)=(to) +#define _RS(list) +#define _CASTASGN(a,b) (a)=(b) +#endif + +/****************************************************************************** + * The sort macro is an adaptation of Simon Tatham's O(n log(n)) mergesort * + * Unwieldy variable names used here to avoid shadowing passed-in variables. * + *****************************************************************************/ +#define LL_SORT(list, cmp) \ + LL_SORT2(list, cmp, next) + +#define LL_SORT2(list, cmp, next) \ +do { \ + LDECLTYPE(list) _ls_p; \ + LDECLTYPE(list) _ls_q; \ + LDECLTYPE(list) _ls_e; \ + LDECLTYPE(list) _ls_tail; \ + int _ls_insize, _ls_nmerges, _ls_psize, _ls_qsize, _ls_i, _ls_looping; \ + if (list) { \ + _ls_insize = 1; \ + _ls_looping = 1; \ + while (_ls_looping) { \ + _CASTASGN(_ls_p,list); \ + list = NULL; \ + _ls_tail = NULL; \ + _ls_nmerges = 0; \ + while (_ls_p) { \ + _ls_nmerges++; \ + _ls_q = _ls_p; \ + _ls_psize = 0; \ + for (_ls_i = 0; _ls_i < _ls_insize; _ls_i++) { \ + _ls_psize++; \ + _SV(_ls_q,list); _ls_q = _NEXT(_ls_q,list,next); _RS(list); \ + if (!_ls_q) break; \ + } \ + _ls_qsize = _ls_insize; \ + while (_ls_psize > 0 || (_ls_qsize > 0 && _ls_q)) { \ + if (_ls_psize == 0) { \ + _ls_e = _ls_q; _SV(_ls_q,list); _ls_q = \ + _NEXT(_ls_q,list,next); _RS(list); _ls_qsize--; \ + } else if (_ls_qsize == 0 || !_ls_q) { \ + _ls_e = _ls_p; _SV(_ls_p,list); _ls_p = \ + _NEXT(_ls_p,list,next); _RS(list); _ls_psize--; \ + } else if (cmp(_ls_p,_ls_q) <= 0) { \ + _ls_e = _ls_p; _SV(_ls_p,list); _ls_p = \ + _NEXT(_ls_p,list,next); _RS(list); _ls_psize--; \ + } else { \ + _ls_e = _ls_q; _SV(_ls_q,list); _ls_q = \ + _NEXT(_ls_q,list,next); _RS(list); _ls_qsize--; \ + } \ + if (_ls_tail) { \ + _SV(_ls_tail,list); _NEXTASGN(_ls_tail,list,_ls_e,next); _RS(list); \ + } else { \ + _CASTASGN(list,_ls_e); \ + } \ + _ls_tail = _ls_e; \ + } \ + _ls_p = _ls_q; \ + } \ + if (_ls_tail) { \ + _SV(_ls_tail,list); _NEXTASGN(_ls_tail,list,NULL,next); _RS(list); \ + } \ + if (_ls_nmerges <= 1) { \ + _ls_looping=0; \ + } \ + _ls_insize *= 2; \ + } \ + } \ +} while (0) + + +#define DL_SORT(list, cmp) \ + DL_SORT2(list, cmp, prev, next) + +#define DL_SORT2(list, cmp, prev, next) \ +do { \ + LDECLTYPE(list) _ls_p; \ + LDECLTYPE(list) _ls_q; \ + LDECLTYPE(list) _ls_e; \ + LDECLTYPE(list) _ls_tail; \ + int _ls_insize, _ls_nmerges, _ls_psize, _ls_qsize, _ls_i, _ls_looping; \ + if (list) { \ + _ls_insize = 1; \ + _ls_looping = 1; \ + while (_ls_looping) { \ + _CASTASGN(_ls_p,list); \ + list = NULL; \ + _ls_tail = NULL; \ + _ls_nmerges = 0; \ + while (_ls_p) { \ + _ls_nmerges++; \ + _ls_q = _ls_p; \ + _ls_psize = 0; \ + for (_ls_i = 0; _ls_i < _ls_insize; _ls_i++) { \ + _ls_psize++; \ + _SV(_ls_q,list); _ls_q = _NEXT(_ls_q,list,next); _RS(list); \ + if (!_ls_q) break; \ + } \ + _ls_qsize = _ls_insize; \ + while (_ls_psize > 0 || (_ls_qsize > 0 && _ls_q)) { \ + if (_ls_psize == 0) { \ + _ls_e = _ls_q; _SV(_ls_q,list); _ls_q = \ + _NEXT(_ls_q,list,next); _RS(list); _ls_qsize--; \ + } else if (_ls_qsize == 0 || !_ls_q) { \ + _ls_e = _ls_p; _SV(_ls_p,list); _ls_p = \ + _NEXT(_ls_p,list,next); _RS(list); _ls_psize--; \ + } else if (cmp(_ls_p,_ls_q) <= 0) { \ + _ls_e = _ls_p; _SV(_ls_p,list); _ls_p = \ + _NEXT(_ls_p,list,next); _RS(list); _ls_psize--; \ + } else { \ + _ls_e = _ls_q; _SV(_ls_q,list); _ls_q = \ + _NEXT(_ls_q,list,next); _RS(list); _ls_qsize--; \ + } \ + if (_ls_tail) { \ + _SV(_ls_tail,list); _NEXTASGN(_ls_tail,list,_ls_e,next); _RS(list); \ + } else { \ + _CASTASGN(list,_ls_e); \ + } \ + _SV(_ls_e,list); _PREVASGN(_ls_e,list,_ls_tail,prev); _RS(list); \ + _ls_tail = _ls_e; \ + } \ + _ls_p = _ls_q; \ + } \ + _CASTASGN(list->prev, _ls_tail); \ + _SV(_ls_tail,list); _NEXTASGN(_ls_tail,list,NULL,next); _RS(list); \ + if (_ls_nmerges <= 1) { \ + _ls_looping=0; \ + } \ + _ls_insize *= 2; \ + } \ + } \ +} while (0) + +#define CDL_SORT(list, cmp) \ + CDL_SORT2(list, cmp, prev, next) + +#define CDL_SORT2(list, cmp, prev, next) \ +do { \ + LDECLTYPE(list) _ls_p; \ + LDECLTYPE(list) _ls_q; \ + LDECLTYPE(list) _ls_e; \ + LDECLTYPE(list) _ls_tail; \ + LDECLTYPE(list) _ls_oldhead; \ + LDECLTYPE(list) _tmp; \ + int _ls_insize, _ls_nmerges, _ls_psize, _ls_qsize, _ls_i, _ls_looping; \ + if (list) { \ + _ls_insize = 1; \ + _ls_looping = 1; \ + while (_ls_looping) { \ + _CASTASGN(_ls_p,list); \ + _CASTASGN(_ls_oldhead,list); \ + list = NULL; \ + _ls_tail = NULL; \ + _ls_nmerges = 0; \ + while (_ls_p) { \ + _ls_nmerges++; \ + _ls_q = _ls_p; \ + _ls_psize = 0; \ + for (_ls_i = 0; _ls_i < _ls_insize; _ls_i++) { \ + _ls_psize++; \ + _SV(_ls_q,list); \ + if (_NEXT(_ls_q,list,next) == _ls_oldhead) { \ + _ls_q = NULL; \ + } else { \ + _ls_q = _NEXT(_ls_q,list,next); \ + } \ + _RS(list); \ + if (!_ls_q) break; \ + } \ + _ls_qsize = _ls_insize; \ + while (_ls_psize > 0 || (_ls_qsize > 0 && _ls_q)) { \ + if (_ls_psize == 0) { \ + _ls_e = _ls_q; _SV(_ls_q,list); _ls_q = \ + _NEXT(_ls_q,list,next); _RS(list); _ls_qsize--; \ + if (_ls_q == _ls_oldhead) { _ls_q = NULL; } \ + } else if (_ls_qsize == 0 || !_ls_q) { \ + _ls_e = _ls_p; _SV(_ls_p,list); _ls_p = \ + _NEXT(_ls_p,list,next); _RS(list); _ls_psize--; \ + if (_ls_p == _ls_oldhead) { _ls_p = NULL; } \ + } else if (cmp(_ls_p,_ls_q) <= 0) { \ + _ls_e = _ls_p; _SV(_ls_p,list); _ls_p = \ + _NEXT(_ls_p,list,next); _RS(list); _ls_psize--; \ + if (_ls_p == _ls_oldhead) { _ls_p = NULL; } \ + } else { \ + _ls_e = _ls_q; _SV(_ls_q,list); _ls_q = \ + _NEXT(_ls_q,list,next); _RS(list); _ls_qsize--; \ + if (_ls_q == _ls_oldhead) { _ls_q = NULL; } \ + } \ + if (_ls_tail) { \ + _SV(_ls_tail,list); _NEXTASGN(_ls_tail,list,_ls_e,next); _RS(list); \ + } else { \ + _CASTASGN(list,_ls_e); \ + } \ + _SV(_ls_e,list); _PREVASGN(_ls_e,list,_ls_tail,prev); _RS(list); \ + _ls_tail = _ls_e; \ + } \ + _ls_p = _ls_q; \ + } \ + _CASTASGN(list->prev,_ls_tail); \ + _CASTASGN(_tmp,list); \ + _SV(_ls_tail,list); _NEXTASGN(_ls_tail,list,_tmp,next); _RS(list); \ + if (_ls_nmerges <= 1) { \ + _ls_looping=0; \ + } \ + _ls_insize *= 2; \ + } \ + } \ +} while (0) + +/****************************************************************************** + * singly linked list macros (non-circular) * + *****************************************************************************/ +#define LL_PREPEND(head,add) \ + LL_PREPEND2(head,add,next) + +#define LL_PREPEND2(head,add,next) \ +do { \ + (add)->next = head; \ + head = add; \ +} while (0) + +#define LL_CONCAT(head1,head2) \ + LL_CONCAT2(head1,head2,next) + +#define LL_CONCAT2(head1,head2,next) \ +do { \ + LDECLTYPE(head1) _tmp; \ + if (head1) { \ + _tmp = head1; \ + while (_tmp->next) { _tmp = _tmp->next; } \ + _tmp->next=(head2); \ + } else { \ + (head1)=(head2); \ + } \ +} while (0) + +#define LL_APPEND(head,add) \ + LL_APPEND2(head,add,next) + +#define LL_APPEND2(head,add,next) \ +do { \ + LDECLTYPE(head) _tmp; \ + (add)->next=NULL; \ + if (head) { \ + _tmp = head; \ + while (_tmp->next) { _tmp = _tmp->next; } \ + _tmp->next=(add); \ + } else { \ + (head)=(add); \ + } \ +} while (0) + +#define LL_DELETE(head,del) \ + LL_DELETE2(head,del,next) + +#define LL_DELETE2(head,del,next) \ +do { \ + LDECLTYPE(head) _tmp; \ + if ((head) == (del)) { \ + (head)=(head)->next; \ + } else { \ + _tmp = head; \ + while (_tmp->next && (_tmp->next != (del))) { \ + _tmp = _tmp->next; \ + } \ + if (_tmp->next) { \ + _tmp->next = ((del)->next); \ + } \ + } \ +} while (0) + +/* Here are VS2008 replacements for LL_APPEND and LL_DELETE */ +#define LL_APPEND_VS2008(head,add) \ + LL_APPEND2_VS2008(head,add,next) + +#define LL_APPEND2_VS2008(head,add,next) \ +do { \ + if (head) { \ + (add)->next = head; /* use add->next as a temp variable */ \ + while ((add)->next->next) { (add)->next = (add)->next->next; } \ + (add)->next->next=(add); \ + } else { \ + (head)=(add); \ + } \ + (add)->next=NULL; \ +} while (0) + +#define LL_DELETE_VS2008(head,del) \ + LL_DELETE2_VS2008(head,del,next) + +#define LL_DELETE2_VS2008(head,del,next) \ +do { \ + if ((head) == (del)) { \ + (head)=(head)->next; \ + } else { \ + char *_tmp = (char*)(head); \ + while ((head)->next && ((head)->next != (del))) { \ + head = (head)->next; \ + } \ + if ((head)->next) { \ + (head)->next = ((del)->next); \ + } \ + { \ + char **_head_alias = (char**)&(head); \ + *_head_alias = _tmp; \ + } \ + } \ +} while (0) +#ifdef NO_DECLTYPE +#undef LL_APPEND +#define LL_APPEND LL_APPEND_VS2008 +#undef LL_DELETE +#define LL_DELETE LL_DELETE_VS2008 +#undef LL_DELETE2 +#define LL_DELETE2 LL_DELETE2_VS2008 +#undef LL_APPEND2 +#define LL_APPEND2 LL_APPEND2_VS2008 +#undef LL_CONCAT /* no LL_CONCAT_VS2008 */ +#undef DL_CONCAT /* no DL_CONCAT_VS2008 */ +#endif +/* end VS2008 replacements */ + +#define LL_COUNT(head,el,counter) \ + LL_COUNT2(head,el,counter,next) \ + +#define LL_COUNT2(head,el,counter,next) \ +{ \ + counter = 0; \ + LL_FOREACH2(head,el,next){ ++counter; } \ +} + +#define LL_FOREACH(head,el) \ + LL_FOREACH2(head,el,next) + +#define LL_FOREACH2(head,el,next) \ + for(el=head;el;el=(el)->next) + +#define LL_FOREACH_SAFE(head,el,tmp) \ + LL_FOREACH_SAFE2(head,el,tmp,next) + +#define LL_FOREACH_SAFE2(head,el,tmp,next) \ + for((el)=(head);(el) && (tmp = (el)->next, 1); (el) = tmp) + +#define LL_SEARCH_SCALAR(head,out,field,val) \ + LL_SEARCH_SCALAR2(head,out,field,val,next) + +#define LL_SEARCH_SCALAR2(head,out,field,val,next) \ +do { \ + LL_FOREACH2(head,out,next) { \ + if ((out)->field == (val)) break; \ + } \ +} while(0) + +#define LL_SEARCH(head,out,elt,cmp) \ + LL_SEARCH2(head,out,elt,cmp,next) + +#define LL_SEARCH2(head,out,elt,cmp,next) \ +do { \ + LL_FOREACH2(head,out,next) { \ + if ((cmp(out,elt))==0) break; \ + } \ +} while(0) + +#define LL_REPLACE_ELEM(head, el, add) \ +do { \ + LDECLTYPE(head) _tmp; \ + assert(head != NULL); \ + assert(el != NULL); \ + assert(add != NULL); \ + (add)->next = (el)->next; \ + if ((head) == (el)) { \ + (head) = (add); \ + } else { \ + _tmp = head; \ + while (_tmp->next && (_tmp->next != (el))) { \ + _tmp = _tmp->next; \ + } \ + if (_tmp->next) { \ + _tmp->next = (add); \ + } \ + } \ +} while (0) + +#define LL_PREPEND_ELEM(head, el, add) \ +do { \ + LDECLTYPE(head) _tmp; \ + assert(head != NULL); \ + assert(el != NULL); \ + assert(add != NULL); \ + (add)->next = (el); \ + if ((head) == (el)) { \ + (head) = (add); \ + } else { \ + _tmp = head; \ + while (_tmp->next && (_tmp->next != (el))) { \ + _tmp = _tmp->next; \ + } \ + if (_tmp->next) { \ + _tmp->next = (add); \ + } \ + } \ +} while (0) \ + + +/****************************************************************************** + * doubly linked list macros (non-circular) * + *****************************************************************************/ +#define DL_PREPEND(head,add) \ + DL_PREPEND2(head,add,prev,next) + +#define DL_PREPEND2(head,add,prev,next) \ +do { \ + (add)->next = head; \ + if (head) { \ + (add)->prev = (head)->prev; \ + (head)->prev = (add); \ + } else { \ + (add)->prev = (add); \ + } \ + (head) = (add); \ +} while (0) + +#define DL_APPEND(head,add) \ + DL_APPEND2(head,add,prev,next) + +#define DL_APPEND2(head,add,prev,next) \ +do { \ + if (head) { \ + (add)->prev = (head)->prev; \ + (head)->prev->next = (add); \ + (head)->prev = (add); \ + (add)->next = NULL; \ + } else { \ + (head)=(add); \ + (head)->prev = (head); \ + (head)->next = NULL; \ + } \ +} while (0) + +#define DL_CONCAT(head1,head2) \ + DL_CONCAT2(head1,head2,prev,next) + +#define DL_CONCAT2(head1,head2,prev,next) \ +do { \ + LDECLTYPE(head1) _tmp; \ + if (head2) { \ + if (head1) { \ + _tmp = (head2)->prev; \ + (head2)->prev = (head1)->prev; \ + (head1)->prev->next = (head2); \ + (head1)->prev = _tmp; \ + } else { \ + (head1)=(head2); \ + } \ + } \ +} while (0) + +#define DL_DELETE(head,del) \ + DL_DELETE2(head,del,prev,next) + +#define DL_DELETE2(head,del,prev,next) \ +do { \ + assert((del)->prev != NULL); \ + if ((del)->prev == (del)) { \ + (head)=NULL; \ + } else if ((del)==(head)) { \ + (del)->next->prev = (del)->prev; \ + (head) = (del)->next; \ + } else { \ + (del)->prev->next = (del)->next; \ + if ((del)->next) { \ + (del)->next->prev = (del)->prev; \ + } else { \ + (head)->prev = (del)->prev; \ + } \ + } \ +} while (0) + +#define DL_COUNT(head,el,counter) \ + DL_COUNT2(head,el,counter,next) \ + +#define DL_COUNT2(head,el,counter,next) \ +{ \ + counter = 0; \ + DL_FOREACH2(head,el,next){ ++counter; } \ +} + +#define DL_FOREACH(head,el) \ + DL_FOREACH2(head,el,next) + +#define DL_FOREACH2(head,el,next) \ + for(el=head;el;el=(el)->next) + +/* this version is safe for deleting the elements during iteration */ +#define DL_FOREACH_SAFE(head,el,tmp) \ + DL_FOREACH_SAFE2(head,el,tmp,next) + +#define DL_FOREACH_SAFE2(head,el,tmp,next) \ + for((el)=(head);(el) && (tmp = (el)->next, 1); (el) = tmp) + +/* these are identical to their singly-linked list counterparts */ +#define DL_SEARCH_SCALAR LL_SEARCH_SCALAR +#define DL_SEARCH LL_SEARCH +#define DL_SEARCH_SCALAR2 LL_SEARCH_SCALAR2 +#define DL_SEARCH2 LL_SEARCH2 + +#define DL_REPLACE_ELEM(head, el, add) \ +do { \ + assert(head != NULL); \ + assert(el != NULL); \ + assert(add != NULL); \ + if ((head) == (el)) { \ + (head) = (add); \ + (add)->next = (el)->next; \ + if ((el)->next == NULL) { \ + (add)->prev = (add); \ + } else { \ + (add)->prev = (el)->prev; \ + (add)->next->prev = (add); \ + } \ + } else { \ + (add)->next = (el)->next; \ + (add)->prev = (el)->prev; \ + (add)->prev->next = (add); \ + if ((el)->next == NULL) { \ + (head)->prev = (add); \ + } else { \ + (add)->next->prev = (add); \ + } \ + } \ +} while (0) + +#define DL_PREPEND_ELEM(head, el, add) \ +do { \ + assert(head != NULL); \ + assert(el != NULL); \ + assert(add != NULL); \ + (add)->next = (el); \ + (add)->prev = (el)->prev; \ + (el)->prev = (add); \ + if ((head) == (el)) { \ + (head) = (add); \ + } else { \ + (add)->prev->next = (add); \ + } \ +} while (0) \ + + +/****************************************************************************** + * circular doubly linked list macros * + *****************************************************************************/ +#define CDL_PREPEND(head,add) \ + CDL_PREPEND2(head,add,prev,next) + +#define CDL_PREPEND2(head,add,prev,next) \ +do { \ + if (head) { \ + (add)->prev = (head)->prev; \ + (add)->next = (head); \ + (head)->prev = (add); \ + (add)->prev->next = (add); \ + } else { \ + (add)->prev = (add); \ + (add)->next = (add); \ + } \ +(head)=(add); \ +} while (0) + +#define CDL_DELETE(head,del) \ + CDL_DELETE2(head,del,prev,next) + +#define CDL_DELETE2(head,del,prev,next) \ +do { \ + if ( ((head)==(del)) && ((head)->next == (head))) { \ + (head) = 0L; \ + } else { \ + (del)->next->prev = (del)->prev; \ + (del)->prev->next = (del)->next; \ + if ((del) == (head)) (head)=(del)->next; \ + } \ +} while (0) + +#define CDL_COUNT(head,el,counter) \ + CDL_COUNT2(head,el,counter,next) \ + +#define CDL_COUNT2(head, el, counter,next) \ +{ \ + counter = 0; \ + CDL_FOREACH2(head,el,next){ ++counter; } \ +} + +#define CDL_FOREACH(head,el) \ + CDL_FOREACH2(head,el,next) + +#define CDL_FOREACH2(head,el,next) \ + for(el=head;el;el=((el)->next==head ? 0L : (el)->next)) + +#define CDL_FOREACH_SAFE(head,el,tmp1,tmp2) \ + CDL_FOREACH_SAFE2(head,el,tmp1,tmp2,prev,next) + +#define CDL_FOREACH_SAFE2(head,el,tmp1,tmp2,prev,next) \ + for((el)=(head), ((tmp1)=(head)?((head)->prev):NULL); \ + (el) && ((tmp2)=(el)->next, 1); \ + ((el) = (((el)==(tmp1)) ? 0L : (tmp2)))) + +#define CDL_SEARCH_SCALAR(head,out,field,val) \ + CDL_SEARCH_SCALAR2(head,out,field,val,next) + +#define CDL_SEARCH_SCALAR2(head,out,field,val,next) \ +do { \ + CDL_FOREACH2(head,out,next) { \ + if ((out)->field == (val)) break; \ + } \ +} while(0) + +#define CDL_SEARCH(head,out,elt,cmp) \ + CDL_SEARCH2(head,out,elt,cmp,next) + +#define CDL_SEARCH2(head,out,elt,cmp,next) \ +do { \ + CDL_FOREACH2(head,out,next) { \ + if ((cmp(out,elt))==0) break; \ + } \ +} while(0) + +#define CDL_REPLACE_ELEM(head, el, add) \ +do { \ + assert(head != NULL); \ + assert(el != NULL); \ + assert(add != NULL); \ + if ((el)->next == (el)) { \ + (add)->next = (add); \ + (add)->prev = (add); \ + (head) = (add); \ + } else { \ + (add)->next = (el)->next; \ + (add)->prev = (el)->prev; \ + (add)->next->prev = (add); \ + (add)->prev->next = (add); \ + if ((head) == (el)) { \ + (head) = (add); \ + } \ + } \ +} while (0) + +#define CDL_PREPEND_ELEM(head, el, add) \ +do { \ + assert(head != NULL); \ + assert(el != NULL); \ + assert(add != NULL); \ + (add)->next = (el); \ + (add)->prev = (el)->prev; \ + (el)->prev = (add); \ + (add)->prev->next = (add); \ + if ((head) == (el)) { \ + (head) = (add); \ + } \ +} while (0) \ + +#endif /* UTLIST_H */ + diff --git a/src/rcl/rcl.h b/src/rcl/rcl.h index 0cb505a57..76f9523fb 100644 --- a/src/rcl/rcl.h +++ b/src/rcl/rcl.h @@ -34,6 +34,13 @@ * using as a configuration language */ +enum rspamd_cl_error { + RSPAMD_CL_EOK = 0, + RSPAMD_CL_ESYNTAX, + RSPAMD_CL_EIO, + RSPAMD_CL_ESTATE +}; + enum rspamd_cl_type { RSPAMD_CL_OBJECT = 0, RSPAMD_CL_ARRAY, @@ -56,6 +63,7 @@ typedef struct rspamd_cl_object_s { gdouble dv; /**< double value of an object */ } value; enum rspamd_cl_type type; /**< real type */ + struct rspamd_cl_object_s *next; /**< array handle */ UT_hash_handle hh; /**< hash handle */ } rspamd_cl_object_t; diff --git a/src/rcl/rcl_internal.h b/src/rcl/rcl_internal.h index b94ecd90f..48047b19f 100644 --- a/src/rcl/rcl_internal.h +++ b/src/rcl/rcl_internal.h @@ -25,10 +25,55 @@ #define RCL_INTERNAL_H_ #include "rcl.h" +#include "utlist.h" /** * @file rcl_internal.h * Internal structures and functions of RCL library */ +#define RCL_ERROR rcl_error_quark () +static inline GQuark +rcl_error_quark (void) +{ + return g_quark_from_static_string ("rcl-error-quark"); +} + +enum rspamd_cl_parser_state { + RSPAMD_RCL_STATE_INIT = 0, + RSPAMD_RCL_STATE_OBJECT, + RSPAMD_RCL_STATE_ARRAY, + RSPAMD_RCL_STATE_KEY, + RSPAMD_RCL_STATE_VALUE, + RSPAMD_RCL_STATE_SCOMMENT, + RSPAMD_RCL_STATE_MCOMMENT, + RSPAMD_RCL_STATE_MACRO_NAME, + RSPAMD_RCL_STATE_MACRO, + RSPAMD_RCL_STATE_ERROR +}; + +struct rspamd_cl_macro { + gchar *name; + rspamd_cl_macro_handler handler; + gpointer ud; + UT_hash_handle hh; +}; + +struct rspamd_cl_stack { + rspamd_cl_object_t *obj; + struct rspamd_cl_stack *next; +}; + +struct rspamd_cl_parser { + enum rspamd_cl_parser_state state; + enum rspamd_cl_parser_state prev_state; + gint comments_nested; + rspamd_cl_object_t *top_obj; + rspamd_cl_object_t *cur_obj; + struct rspamd_cl_macro *macroes; + struct rspamd_cl_stack *stack; + guint line; + guint column; +}; + #endif /* RCL_INTERNAL_H_ */ diff --git a/src/rcl/rcl_parser.c b/src/rcl/rcl_parser.c index 574edf8c0..8ace95cf0 100644 --- a/src/rcl/rcl_parser.c +++ b/src/rcl/rcl_parser.c @@ -29,3 +29,301 @@ * @file rcl_parser.c * The implementation of rcl parser */ + +/** + * Create a new object + * @return new object + */ +static inline rspamd_cl_object_t * +rspamd_cl_object_new (void) +{ + return g_slice_alloc0 (sizeof (rspamd_cl_object_t)); +} + +/** + * Move up to len characters + * @param parser + * @param begin + * @param len + * @return new position in chunk + */ +static inline const guchar * +rspamd_cl_chunk_getc (struct rspamd_cl_parser *parser, const guchar *begin, gsize len) +{ + while (len > 0) { + len --; + if (*begin == '\n') { + parser->line ++; + parser->column = 0; + } + else { + parser->column ++; + } + begin ++; + } + return begin; +} + +static gboolean +rspamd_cl_check_open_comment (struct rspamd_cl_parser *parser, const guchar **begin, gsize *len) +{ + const guchar *p = *begin; + + if (*p == '#') { + if (parser->state != RSPAMD_RCL_STATE_SCOMMENT && + parser->state != RSPAMD_RCL_STATE_MCOMMENT) { + parser->prev_state = parser->state; + parser->state = RSPAMD_RCL_STATE_SCOMMENT; + *begin = rspamd_cl_chunk_getc (parser, *begin, 1); + (*len) --; + return TRUE; + } + } + else if (*p == '/' && *len >= 2) { + if (*p == '/' && parser->state != RSPAMD_RCL_STATE_SCOMMENT && + parser->state != RSPAMD_RCL_STATE_MCOMMENT) { + parser->prev_state = parser->state; + parser->state = RSPAMD_RCL_STATE_SCOMMENT; + *begin = rspamd_cl_chunk_getc (parser, *begin, 2); + (*len) -= 2; + return TRUE; + } + else if (*p == '*') { + /* Multiline comment */ + if (parser->state == RSPAMD_RCL_STATE_SCOMMENT) { + /* Immediately finish single line comment and start multiline one */ + parser->state = RSPAMD_RCL_STATE_MCOMMENT; + parser->comments_nested ++; + } + else if (parser->state == RSPAMD_RCL_STATE_MCOMMENT) { + parser->comments_nested ++; + } + else { + parser->prev_state = parser->state; + parser->state = RSPAMD_RCL_STATE_SCOMMENT; + } + *begin = rspamd_cl_chunk_getc (parser, *begin, 2); + (*len) -= 2; + } + } + + return FALSE; +} + +/** + * Handle include macro + * @param data include data + * @param len length of data + * @param ud user data + * @param err error ptr + * @return + */ +static gboolean +rspamd_cl_include_handler (const guchar *data, gsize len, gpointer ud, GError **err) +{ + return TRUE; +} + +/** + * Handle includes macro + * @param data include data + * @param len length of data + * @param ud user data + * @param err error ptr + * @return + */ +static gboolean +rspamd_cl_includes_handler (const guchar *data, gsize len, gpointer ud, GError **err) +{ + return TRUE; +} + +static const guchar * +rspamd_cl_skip_spaces (struct rspamd_cl_parser *parser, const guchar *data, gsize *len) +{ + const guchar *p, *end; + + p = data; + end = data + *len; + + if (parser->state == RSPAMD_RCL_STATE_KEY) { + /* Skip any space character */ + while (p < end) { + if (!g_ascii_isspace (*p)) { + break; + } + p = rspamd_cl_chunk_getc (parser, p, 1); + (*len) --; + } + } + else { + while (p < end) { + if (!g_ascii_isspace (*p) || *p == '\n' || *p == '\r') { + break; + } + p = rspamd_cl_chunk_getc (parser, p, 1); + (*len) --; + } + } + + return p; +} + +static gboolean +rspamd_cl_parse_key (struct rspamd_cl_parser *parser, const guchar **data, + gsize *len, GError **err) +{ + const guchar *p, *c = NULL, *end; + + + p = *data; + end = p + *len; + + while (p < end) { + /* + * A key must start with alpha and end with space character + */ + if (*p == '.') { + /* It is macro actually */ + p = rspamd_cl_chunk_getc (parser, p, 1); + len --; + parser->state = RSPAMD_RCL_STATE_MACRO_NAME; + *data = p; + return TRUE; + } + else if (c == NULL) { + if (g_ascii_isalpha (*p)) { + /* The first symbol */ + c = p; + p = rspamd_cl_chunk_getc (parser, p, 1); + (*len) --; + } + else if (*p == '"') { + /* JSON style key */ + c = p + 1; + p = rspamd_cl_chunk_getc (parser, p, 2); + (*len) -= 2; + } + else { + /* Invalid identifier */ + parser->state = RSPAMD_RCL_STATE_ERROR; + g_set_error (err, RCL_ERROR, RSPAMD_CL_ESYNTAX, "key must start with a letter, " + "line %d, pos: %d", parser->line, parser->column); + return FALSE; + } + } + else { + if (g_ascii_isalnum (*p)) { + p = rspamd_cl_chunk_getc (parser, p, 1); + (*len) --; + } + else if (*p == ' ' || *p == '\t') { + p = rspamd_cl_skip_spaces (parser, p, len); + } + } + } + *data = p; + + return TRUE; +} + +/** + * Handle the main states of rcl parser + * @param parser parser structure + * @param data the pointer to the beginning of a chunk + * @param len the length of a chunk + * @param err if *err is NULL it is set to parser error + * @return TRUE if chunk has been parsed and FALSE in case of error + */ +static gboolean +rspamd_cl_state_machine (struct rspamd_cl_parser *parser, const guchar *data, + gsize len, GError **err) +{ + const guchar *p, *end; + rspamd_cl_object_t *obj; + + p = data; + end = p + len; + while (p < end) { + switch (parser->state) { + case RSPAMD_RCL_STATE_INIT: + /* + * At the init state we can either go to the parse array or object + * if we got [ or { correspondingly or can just treat new data as + * a key of newly created object + */ + if (!rspamd_cl_check_open_comment (parser, &p, &len)) { + obj = rspamd_cl_object_new (); + if (*p == '[') { + parser->state = RSPAMD_RCL_STATE_ARRAY; + obj->type = RSPAMD_CL_ARRAY; + p = rspamd_cl_chunk_getc (parser, p, 1); + len --; + } + else { + parser->state = RSPAMD_RCL_STATE_KEY; + obj->type = RSPAMD_CL_OBJECT; + if (*p == '{') { + p = rspamd_cl_chunk_getc (parser, p, 1); + len --; + } + } + parser->cur_obj = obj; + parser->top_obj = obj; + p = rspamd_cl_skip_spaces (parser, p, &len); + } + break; + case RSPAMD_RCL_STATE_KEY: + if (!rspamd_cl_parse_key (parser, &p, &len, err)) { + return FALSE; + } + break; + default: + /* TODO: add all states */ + return FALSE; + } + } + + return TRUE; +} + +struct rspamd_cl_parser* +rspamd_cl_parser_new (void) +{ + struct rspamd_cl_parser *new; + + new = g_slice_alloc0 (sizeof (struct rspamd_cl_parser)); + + new->line = 1; + rspamd_cl_parser_register_macro (new, "include", rspamd_cl_include_handler, new); + rspamd_cl_parser_register_macro (new, "includes", rspamd_cl_includes_handler, new); + + return new; +} + + +void +rspamd_cl_parser_register_macro (struct rspamd_cl_parser *parser, const gchar *macro, + rspamd_cl_macro_handler handler, gpointer ud) +{ + struct rspamd_cl_macro *new; + + new = g_slice_alloc0 (sizeof (struct rspamd_cl_macro)); + new->handler = handler; + new->name = g_strdup (macro); + new->ud = ud; + HASH_ADD_KEYPTR (hh, parser->macroes, new->name, strlen (new->name), new); +} + +gboolean +rspamd_cl_parser_add_chunk (struct rspamd_cl_parser *parser, const guchar *data, + gsize len, GError **err) +{ + if (parser->state != RSPAMD_RCL_STATE_ERROR) { + return rspamd_cl_state_machine (parser, data, len, err); + } + + g_set_error (err, RCL_ERROR, RSPAMD_CL_ESTATE, "a parser is in an invalid state"); + + return FALSE; +} -- 2.39.5