3 * connection rule patch
4 * by Tony Vencill (Tonto on IRC) <vencill@bga.com>
6 * The majority of this file is a recusive descent parser used to convert
7 * connection rules into expression trees when the conf file is read.
8 * All parsing structures and types are hidden in the interest of good
9 * programming style and to make possible future data structure changes
10 * without affecting the interface between this patch and the rest of the
11 * server. The only functions accessible externally are crule_parse,
12 * crule_free, and crule_eval. Prototypes for these functions can be
15 * Please direct any connection rule or SmartRoute questions to Tonto on
16 * IRC or by email to vencill@bga.com.
18 * For parser testing, defining CR_DEBUG generates a stand-alone parser
19 * that takes rules from stdin and prints out memory allocation
20 * information and the parsed rule. This stand alone parser is ignorant
21 * of the irc server and thus cannot do rule evaluation. Do not define
22 * this flag when compiling the server! If you wish to generate the
23 * test parser, compile from the ircd directory with a line similar to
24 * cc -o parser -DCR_DEBUG crule.c
26 * The define CR_CHKCONF is provided to generate routines needed in
27 * chkconf. These consist of the parser, a different crule_parse that
28 * prints errors to stderr, and crule_free (just for good style and to
29 * more closely simulate the actual ircd environment). crule_eval and
30 * the rule functions are made empty functions as in the stand-alone
40 /* ircd functions and types we need */
43 #include "ircd_alloc.h"
44 #include "ircd_chattr.h"
45 #include "ircd_string.h"
54 #else /* includes and defines to make the stand-alone test parser */
59 #define BadPtr(x) (!(x) || (*(x) == '\0'))
60 #define DupString(x,y) \
62 x = (char*) MyMalloc(strlen(y)+1); \
66 /* We don't care about collation discrepacies here, it seems.... */
67 #define ircd_strcmp strcasecmp
74 #if defined(CR_DEBUG) || defined(CR_CHKCONF)
77 #define MyMalloc malloc
83 /* some constants and shared data types */
84 #define CR_MAXARGLEN 80 /* why 80? why not? it's > hostname lengths */
85 #define CR_MAXARGS 3 /* There's a better way to do this,
89 * Some symbols for easy reading
93 CR_UNKNOWN, CR_END, CR_AND, CR_OR, CR_NOT, CR_OPENPAREN, CR_CLOSEPAREN,
98 CR_NOERR, CR_UNEXPCTTOK, CR_UNKNWTOK, CR_EXPCTAND, CR_EXPCTOR,
99 CR_EXPCTPRIM, CR_EXPCTOPEN, CR_EXPCTCLOSE, CR_UNKNWFUNC, CR_ARGMISMAT
103 * Expression tree structure, function pointer, and tree pointer local!
105 typedef int (*crule_funcptr) (int, void **);
108 crule_funcptr funcptr;
110 void *arg[CR_MAXARGS]; /* For operators arg points to a tree element;
111 for functions arg points to a char string. */
114 typedef struct CRuleNode* CRuleNodePtr;
116 /* local rule function prototypes */
117 static int crule_connected(int, void **);
118 static int crule_directcon(int, void **);
119 static int crule_via(int, void **);
120 static int crule_directop(int, void **);
121 static int crule__andor(int, void **);
122 static int crule__not(int, void **);
124 /* local parsing function prototypes */
125 static int crule_gettoken(int* token, const char** str);
126 static void crule_getword(char*, int*, size_t, const char**);
127 static int crule_parseandexpr(CRuleNodePtr*, int *, const char**);
128 static int crule_parseorexpr(CRuleNodePtr*, int *, const char**);
129 static int crule_parseprimary(CRuleNodePtr*, int *, const char**);
130 static int crule_parsefunction(CRuleNodePtr*, int *, const char**);
131 static int crule_parsearglist(CRuleNodePtr, int *, const char**);
133 #if defined(CR_DEBUG) || defined(CR_CHKCONF)
135 * Prototypes for the test parser; if not debugging,
136 * these are defined in h.h
138 struct CRuleNode* crule_parse(const char*);
139 void crule_free(struct CRuleNode**);
141 void print_tree(CRuleNodePtr);
146 char *crule_errstr[] = {
147 "Unknown error", /* NOERR? - for completeness */
148 "Unexpected token", /* UNEXPCTTOK */
149 "Unknown token", /* UNKNWTOK */
150 "And expr expected", /* EXPCTAND */
151 "Or expr expected", /* EXPCTOR */
152 "Primary expected", /* EXPCTPRIM */
153 "( expected", /* EXPCTOPEN */
154 ") expected", /* EXPCTCLOSE */
155 "Unknown function", /* UNKNWFUNC */
156 "Argument mismatch" /* ARGMISMAT */
159 /* function table - null terminated */
160 struct crule_funclistent {
161 char name[15]; /* MAXIMUM FUNCTION NAME LENGTH IS 14 CHARS!! */
163 crule_funcptr funcptr;
166 struct crule_funclistent crule_funclist[] = {
167 /* maximum function name length is 14 chars */
168 {"connected", 1, crule_connected},
169 {"directcon", 1, crule_directcon},
170 {"via", 2, crule_via},
171 {"directop", 0, crule_directop},
172 {"", 0, NULL} /* this must be here to mark end of list */
175 #if !defined(CR_DEBUG) && !defined(CR_CHKCONF)
176 static int crule_connected(int numargs, void *crulearg[])
178 struct Client *acptr;
180 /* taken from m_links */
181 for (acptr = GlobalClientList; acptr; acptr = cli_next(acptr))
183 if (!IsServer(acptr) && !IsMe(acptr))
185 if (match((char *)crulearg[0], cli_name(acptr)))
192 static int crule_connected(int numargs, void **crulearg)
198 #if !defined(CR_DEBUG) && !defined(CR_CHKCONF)
199 static int crule_directcon(int numargs, void *crulearg[])
202 struct Client *acptr;
204 /* adapted from m_trace and exit_one_client */
205 for (i = 0; i <= HighestFd; i++)
207 if (!(acptr = LocalClientArray[i]) || !IsServer(acptr))
209 if (match((char *)crulearg[0], cli_name(acptr)))
216 static int crule_directcon(int numargs, void **crulearg)
222 #if !defined(CR_DEBUG) && !defined(CR_CHKCONF)
223 static int crule_via(int numargs, void *crulearg[])
225 struct Client *acptr;
227 /* adapted from m_links */
228 for (acptr = GlobalClientList; acptr; acptr = cli_next(acptr))
230 if (!IsServer(acptr) && !IsMe(acptr))
232 if (match((char *)crulearg[1], cli_name(acptr)))
234 if (match((char *)crulearg[0],
235 cli_name(LocalClientArray[cli_fd(cli_from(acptr))])))
242 static int crule_via(int numargs, void **crulearg)
248 static int crule_directop(int numargs, void **crulearg)
250 #if !defined(CR_DEBUG) && !defined(CR_CHKCONF)
252 struct Client *acptr;
254 /* adapted from m_trace */
255 for (i = 0; i <= HighestFd; i++)
257 if (!(acptr = LocalClientArray[i]) || !IsAnOper(acptr))
265 static int crule__andor(int numargs, void *crulearg[])
269 result1 = ((CRuleNodePtr) crulearg[0])->funcptr
270 (((CRuleNodePtr) crulearg[0])->numargs,
271 ((CRuleNodePtr) crulearg[0])->arg);
272 if (crulearg[2]) /* or */
274 ((CRuleNodePtr) crulearg[1])->funcptr
275 (((CRuleNodePtr) crulearg[1])->numargs,
276 ((CRuleNodePtr) crulearg[1])->arg));
279 ((CRuleNodePtr) crulearg[1])->funcptr
280 (((CRuleNodePtr) crulearg[1])->numargs,
281 ((CRuleNodePtr) crulearg[1])->arg));
284 static int crule__not(int numargs, void *crulearg[])
286 return (!((CRuleNodePtr) crulearg[0])->funcptr
287 (((CRuleNodePtr) crulearg[0])->numargs,
288 ((CRuleNodePtr) crulearg[0])->arg));
291 #if !defined(CR_DEBUG) && !defined(CR_CHKCONF)
292 int crule_eval(struct CRuleNode* rule)
294 return (rule->funcptr(rule->numargs, rule->arg));
298 static int crule_gettoken(int* next_tokp, const char** ruleptr)
302 *next_tokp = CR_UNKNOWN;
303 while (*next_tokp == CR_UNKNOWN)
304 switch (*(*ruleptr)++)
312 else if (pending == '&')
315 return (CR_UNKNWTOK);
320 else if (pending == '|')
323 return (CR_UNKNWTOK);
329 *next_tokp = CR_OPENPAREN;
332 *next_tokp = CR_CLOSEPAREN;
335 *next_tokp = CR_COMMA;
345 if ((IsAlpha(*(--(*ruleptr)))) || (**ruleptr == '*') ||
346 (**ruleptr == '?') || (**ruleptr == '.') || (**ruleptr == '-'))
347 *next_tokp = CR_WORD;
349 return (CR_UNKNWTOK);
355 static void crule_getword(char* word, int* wordlenp, size_t maxlen, const char** ruleptr)
360 while ((size_t)(word_ptr - word) < maxlen
361 && (IsAlnum(**ruleptr)
362 || **ruleptr == '*' || **ruleptr == '?'
363 || **ruleptr == '.' || **ruleptr == '-'))
364 *word_ptr++ = *(*ruleptr)++;
366 *wordlenp = word_ptr - word;
372 * orexpr END END is end of input or :
384 * word ( ) word is alphanumeric string, first character
385 * word ( arglist ) must be a letter
390 struct CRuleNode* crule_parse(const char *rule)
392 const char* ruleptr = rule;
394 struct CRuleNode* ruleroot = 0;
395 int errcode = CR_NOERR;
397 if ((errcode = crule_gettoken(&next_tok, &ruleptr)) == CR_NOERR) {
398 if ((errcode = crule_parseorexpr(&ruleroot, &next_tok, &ruleptr)) == CR_NOERR) {
399 if (ruleroot != NULL) {
400 if (next_tok == CR_END)
403 errcode = CR_UNEXPCTTOK;
406 errcode = CR_EXPCTOR;
409 if (ruleroot != NULL)
410 crule_free(&ruleroot);
411 #if !defined(CR_DEBUG) && !defined(CR_CHKCONF)
412 Debug((DEBUG_ERROR, "%s in rule: %s", crule_errstr[errcode], rule));
414 fprintf(stderr, "%s in rule: %s\n", crule_errstr[errcode], rule);
419 static int crule_parseorexpr(CRuleNodePtr * orrootp, int *next_tokp, const char** ruleptr)
421 int errcode = CR_NOERR;
422 CRuleNodePtr andexpr;
426 while (errcode == CR_NOERR)
428 errcode = crule_parseandexpr(&andexpr, next_tokp, ruleptr);
429 if ((errcode == CR_NOERR) && (*next_tokp == CR_OR))
431 orptr = (CRuleNodePtr) MyMalloc(sizeof(struct CRuleNode));
433 fprintf(stderr, "allocating or element at %ld\n", orptr);
435 orptr->funcptr = crule__andor;
437 orptr->arg[2] = (void *)1;
438 if (*orrootp != NULL)
440 (*orrootp)->arg[1] = andexpr;
441 orptr->arg[0] = *orrootp;
444 orptr->arg[0] = andexpr;
449 if (*orrootp != NULL)
453 (*orrootp)->arg[1] = andexpr;
458 (*orrootp)->arg[1] = NULL; /* so free doesn't seg fault */
459 return (CR_EXPCTAND);
468 if ((errcode = crule_gettoken(next_tokp, ruleptr)) != CR_NOERR)
474 static int crule_parseandexpr(CRuleNodePtr * androotp, int *next_tokp, const char** ruleptr)
476 int errcode = CR_NOERR;
477 CRuleNodePtr primary;
481 while (errcode == CR_NOERR)
483 errcode = crule_parseprimary(&primary, next_tokp, ruleptr);
484 if ((errcode == CR_NOERR) && (*next_tokp == CR_AND))
486 andptr = (CRuleNodePtr) MyMalloc(sizeof(struct CRuleNode));
488 fprintf(stderr, "allocating and element at %ld\n", andptr);
490 andptr->funcptr = crule__andor;
492 andptr->arg[2] = (void *)0;
493 if (*androotp != NULL)
495 (*androotp)->arg[1] = primary;
496 andptr->arg[0] = *androotp;
499 andptr->arg[0] = primary;
504 if (*androotp != NULL)
508 (*androotp)->arg[1] = primary;
513 (*androotp)->arg[1] = NULL; /* so free doesn't seg fault */
514 return (CR_EXPCTPRIM);
523 if ((errcode = crule_gettoken(next_tokp, ruleptr)) != CR_NOERR)
529 static int crule_parseprimary(CRuleNodePtr* primrootp, int *next_tokp, const char** ruleptr)
531 CRuleNodePtr *insertionp;
532 int errcode = CR_NOERR;
535 insertionp = primrootp;
536 while (errcode == CR_NOERR)
541 if ((errcode = crule_gettoken(next_tokp, ruleptr)) != CR_NOERR)
543 if ((errcode = crule_parseorexpr(insertionp, next_tokp, ruleptr)) != CR_NOERR)
545 if (*insertionp == NULL)
547 errcode = CR_EXPCTAND;
550 if (*next_tokp != CR_CLOSEPAREN)
552 errcode = CR_EXPCTCLOSE;
555 errcode = crule_gettoken(next_tokp, ruleptr);
558 *insertionp = (CRuleNodePtr) MyMalloc(sizeof(struct CRuleNode));
560 fprintf(stderr, "allocating primary element at %ld\n", *insertionp);
562 (*insertionp)->funcptr = crule__not;
563 (*insertionp)->numargs = 1;
564 (*insertionp)->arg[0] = NULL;
565 insertionp = (CRuleNodePtr *) & ((*insertionp)->arg[0]);
566 if ((errcode = crule_gettoken(next_tokp, ruleptr)) != CR_NOERR)
570 errcode = crule_parsefunction(insertionp, next_tokp, ruleptr);
573 if (*primrootp == NULL)
576 errcode = CR_EXPCTPRIM;
584 static int crule_parsefunction(CRuleNodePtr* funcrootp, int* next_tokp, const char** ruleptr)
586 int errcode = CR_NOERR;
587 char funcname[CR_MAXARGLEN];
592 crule_getword(funcname, &namelen, CR_MAXARGLEN - 1, ruleptr);
593 if ((errcode = crule_gettoken(next_tokp, ruleptr)) != CR_NOERR)
595 if (*next_tokp == CR_OPENPAREN)
597 for (funcnum = 0;; funcnum++)
599 if (0 == ircd_strcmp(crule_funclist[funcnum].name, funcname))
601 if (crule_funclist[funcnum].name[0] == '\0')
602 return (CR_UNKNWFUNC);
604 if ((errcode = crule_gettoken(next_tokp, ruleptr)) != CR_NOERR)
606 *funcrootp = (CRuleNodePtr) MyMalloc(sizeof(struct CRuleNode));
608 fprintf(stderr, "allocating function element at %ld\n", *funcrootp);
610 (*funcrootp)->funcptr = NULL; /* for freeing aborted trees */
612 crule_parsearglist(*funcrootp, next_tokp, ruleptr)) != CR_NOERR)
614 if (*next_tokp != CR_CLOSEPAREN)
615 return (CR_EXPCTCLOSE);
616 if ((crule_funclist[funcnum].reqnumargs != (*funcrootp)->numargs) &&
617 (crule_funclist[funcnum].reqnumargs != -1))
618 return (CR_ARGMISMAT);
619 if ((errcode = crule_gettoken(next_tokp, ruleptr)) != CR_NOERR)
621 (*funcrootp)->funcptr = crule_funclist[funcnum].funcptr;
625 return (CR_EXPCTOPEN);
628 static int crule_parsearglist(CRuleNodePtr argrootp, int *next_tokp, const char** ruleptr)
630 int errcode = CR_NOERR;
631 char *argelemp = NULL;
632 char currarg[CR_MAXARGLEN];
634 char word[CR_MAXARGLEN];
637 argrootp->numargs = 0;
639 while (errcode == CR_NOERR)
644 crule_getword(word, &wordlen, CR_MAXARGLEN - 1, ruleptr);
645 if (currarg[0] != '\0')
647 if ((arglen + wordlen) < (CR_MAXARGLEN - 1))
649 strcat(currarg, " ");
650 strcat(currarg, word);
651 arglen += wordlen + 1;
656 strcpy(currarg, word);
659 errcode = crule_gettoken(next_tokp, ruleptr);
662 #if !defined(CR_DEBUG) && !defined(CR_CHKCONF)
665 if (!BadPtr(currarg))
667 DupString(argelemp, currarg);
668 argrootp->arg[argrootp->numargs++] = (void *)argelemp;
670 if (*next_tokp != CR_COMMA)
673 errcode = crule_gettoken(next_tokp, ruleptr);
681 * This function is recursive.. I wish I knew a nonrecursive way but
682 * I dont. anyway, recursion is fun.. :)
683 * DO NOT CALL THIS FUNTION WITH A POINTER TO A NULL POINTER
684 * (ie: If *elem is NULL, you're doing it wrong - seg fault)
686 void crule_free(struct CRuleNode** elem)
690 if ((*(elem))->funcptr == crule__not)
692 /* type conversions and ()'s are fun! ;) here have an asprin.. */
693 if ((*(elem))->arg[0] != NULL)
694 crule_free((struct CRuleNode**) &((*(elem))->arg[0]));
696 else if ((*(elem))->funcptr == crule__andor)
698 crule_free((struct CRuleNode**) &((*(elem))->arg[0]));
699 if ((*(elem))->arg[1] != NULL)
700 crule_free((struct CRuleNode**) &((*(elem))->arg[1]));
704 numargs = (*(elem))->numargs;
705 for (arg = 0; arg < numargs; arg++)
706 MyFree((*(elem))->arg[arg]);
709 fprintf(stderr, "freeing element at %ld\n", *elem);
716 static void print_tree(CRuleNodePtr printelem)
720 if (printelem->funcptr == crule__not)
723 print_tree((CRuleNodePtr) printelem->arg[0]);
726 else if (printelem->funcptr == crule__andor)
729 print_tree((CRuleNodePtr) printelem->arg[0]);
730 if (printelem->arg[2])
734 print_tree((CRuleNodePtr) printelem->arg[1]);
739 for (funcnum = 0;; funcnum++)
741 if (printelem->funcptr == crule_funclist[funcnum].funcptr)
743 if (crule_funclist[funcnum].funcptr == NULL)
746 printf("%s(", crule_funclist[funcnum].name);
747 for (arg = 0; arg < printelem->numargs; arg++)
751 printf("%s", (char *)printelem->arg[arg]);
766 while (fgets(indata, 256, stdin) != NULL)
768 indata[strlen(indata) - 1] = '\0'; /* lose the newline */
769 if ((rule = crule_parse(indata)) != NULL)
771 printf("equivalent rule: ");
772 print_tree((CRuleNodePtr) rule);