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
36 /* ircd functions and types we need */
47 #else /* includes and defines to make the stand-alone test parser */
53 #define BadPtr(x) (!(x) || (*(x) == '\0'))
54 #define DupString(x,y) \
56 x = (char *)RunMalloc(strlen(y)+1); \
60 /* We don't care about collation discrepacies here, it seems.... */
61 #define strCasediff strcasecmp
67 #if defined(CR_DEBUG) || defined(CR_CHKCONF)
70 #define RunMalloc malloc
76 /* some constants and shared data types */
77 #define CR_MAXARGLEN 80 /* why 80? why not? it's > hostname lengths */
78 #define CR_MAXARGS 3 /* There's a better way to do this,
82 * Some symbols for easy reading
86 CR_UNKNOWN, CR_END, CR_AND, CR_OR, CR_NOT, CR_OPENPAREN, CR_CLOSEPAREN,
91 CR_NOERR, CR_UNEXPCTTOK, CR_UNKNWTOK, CR_EXPCTAND, CR_EXPCTOR,
92 CR_EXPCTPRIM, CR_EXPCTOPEN, CR_EXPCTCLOSE, CR_UNKNWFUNC, CR_ARGMISMAT
96 * Expression tree structure, function pointer, and tree pointer local!
98 typedef int (*crule_funcptr) (int, void **);
100 struct crule_treestruct {
101 crule_funcptr funcptr;
103 void *arg[CR_MAXARGS]; /* For operators arg points to a tree element;
104 for functions arg points to a char string. */
107 typedef struct crule_treestruct crule_treeelem;
108 typedef crule_treeelem *crule_treeptr;
110 /* local rule function prototypes */
111 static int crule_connected(int, void **);
112 static int crule_directcon(int, void **);
113 static int crule_via(int, void **);
114 static int crule_directop(int, void **);
115 static int crule__andor(int, void **);
116 static int crule__not(int, void **);
118 /* local parsing function prototypes */
119 static int crule_gettoken(int *, char **);
120 static void crule_getword(char *, int *, size_t, char **);
121 static int crule_parseandexpr(crule_treeptr *, int *, char **);
122 static int crule_parseorexpr(crule_treeptr *, int *, char **);
123 static int crule_parseprimary(crule_treeptr *, int *, char **);
124 static int crule_parsefunction(crule_treeptr *, int *, char **);
125 static int crule_parsearglist(crule_treeptr, int *, char **);
127 #if defined(CR_DEBUG) || defined(CR_CHKCONF)
129 * Prototypes for the test parser; if not debugging,
130 * these are defined in h.h
132 char *crule_parse(char *);
133 void crule_free(char **);
135 void print_tree(crule_treeptr);
140 char *crule_errstr[] = {
141 "Unknown error", /* NOERR? - for completeness */
142 "Unexpected token", /* UNEXPCTTOK */
143 "Unknown token", /* UNKNWTOK */
144 "And expr expected", /* EXPCTAND */
145 "Or expr expected", /* EXPCTOR */
146 "Primary expected", /* EXPCTPRIM */
147 "( expected", /* EXPCTOPEN */
148 ") expected", /* EXPCTCLOSE */
149 "Unknown function", /* UNKNWFUNC */
150 "Argument mismatch" /* ARGMISMAT */
153 /* function table - null terminated */
154 struct crule_funclistent {
155 char name[15]; /* MAXIMUM FUNCTION NAME LENGTH IS 14 CHARS!! */
157 crule_funcptr funcptr;
160 struct crule_funclistent crule_funclist[] = {
161 /* maximum function name length is 14 chars */
162 {"connected", 1, crule_connected},
163 {"directcon", 1, crule_directcon},
164 {"via", 2, crule_via},
165 {"directop", 0, crule_directop},
166 {"", 0, NULL} /* this must be here to mark end of list */
169 #if !defined(CR_DEBUG) && !defined(CR_CHKCONF)
170 static int crule_connected(int UNUSED(numargs), void *crulearg[])
174 /* taken from m_links */
175 for (acptr = client; acptr; acptr = acptr->next)
177 if (!IsServer(acptr) && !IsMe(acptr))
179 if (match((char *)crulearg[0], acptr->name))
186 static int crule_connected(int UNUSED(numargs), void **UNUSED(crulearg))
192 #if !defined(CR_DEBUG) && !defined(CR_CHKCONF)
193 static int crule_directcon(int UNUSED(numargs), void *crulearg[])
198 /* adapted from m_trace and exit_one_client */
199 for (i = 0; i <= highest_fd; i++)
201 if (!(acptr = loc_clients[i]) || !IsServer(acptr))
203 if (match((char *)crulearg[0], acptr->name))
210 static int crule_directcon(int UNUSED(numargs), void **UNUSED(crulearg))
216 #if !defined(CR_DEBUG) && !defined(CR_CHKCONF)
217 static int crule_via(int UNUSED(numargs), void *crulearg[])
221 /* adapted from m_links */
222 for (acptr = client; acptr; acptr = acptr->next)
224 if (!IsServer(acptr) && !IsMe(acptr))
226 if (match((char *)crulearg[1], acptr->name))
228 if (match((char *)crulearg[0], (loc_clients[acptr->from->fd])->name))
235 static int crule_via(int UNUSED(numargs), void **UNUSED(crulearg))
241 static int crule_directop(int UNUSED(numargs), void **UNUSED(crulearg))
243 #if !defined(CR_DEBUG) && !defined(CR_CHKCONF)
247 /* adapted from m_trace */
248 for (i = 0; i <= highest_fd; i++)
250 if (!(acptr = loc_clients[i]) || !IsAnOper(acptr))
258 static int crule__andor(int UNUSED(numargs), void *crulearg[])
262 result1 = ((crule_treeptr) crulearg[0])->funcptr
263 (((crule_treeptr) crulearg[0])->numargs,
264 ((crule_treeptr) crulearg[0])->arg);
265 if (crulearg[2]) /* or */
267 ((crule_treeptr) crulearg[1])->funcptr
268 (((crule_treeptr) crulearg[1])->numargs,
269 ((crule_treeptr) crulearg[1])->arg));
272 ((crule_treeptr) crulearg[1])->funcptr
273 (((crule_treeptr) crulearg[1])->numargs,
274 ((crule_treeptr) crulearg[1])->arg));
277 static int crule__not(int UNUSED(numargs), void *crulearg[])
279 return (!((crule_treeptr) crulearg[0])->funcptr
280 (((crule_treeptr) crulearg[0])->numargs,
281 ((crule_treeptr) crulearg[0])->arg));
284 #if !defined(CR_DEBUG) && !defined(CR_CHKCONF)
285 int crule_eval(char *rule)
287 return (((crule_treeptr) rule)->funcptr
288 (((crule_treeptr) rule)->numargs, ((crule_treeptr) rule)->arg));
292 static int crule_gettoken(int *next_tokp, char **ruleptr)
296 *next_tokp = CR_UNKNOWN;
297 while (*next_tokp == CR_UNKNOWN)
298 switch (*(*ruleptr)++)
306 else if (pending == '&')
309 return (CR_UNKNWTOK);
314 else if (pending == '|')
317 return (CR_UNKNWTOK);
323 *next_tokp = CR_OPENPAREN;
326 *next_tokp = CR_CLOSEPAREN;
329 *next_tokp = CR_COMMA;
339 if ((isAlpha(*(--(*ruleptr)))) || (**ruleptr == '*') ||
340 (**ruleptr == '?') || (**ruleptr == '.') || (**ruleptr == '-'))
341 *next_tokp = CR_WORD;
343 return (CR_UNKNWTOK);
349 static void crule_getword(char *word, int *wordlenp, size_t maxlen,
355 while ((size_t)(word_ptr - word) < maxlen
356 && (isAlnum(**ruleptr)
357 || **ruleptr == '*' || **ruleptr == '?'
358 || **ruleptr == '.' || **ruleptr == '-'))
359 *word_ptr++ = *(*ruleptr)++;
361 *wordlenp = word_ptr - word;
367 * orexpr END END is end of input or :
379 * word ( ) word is alphanumeric string, first character
380 * word ( arglist ) must be a letter
385 char *crule_parse(char *rule)
387 char *ruleptr = rule;
389 crule_treeptr ruleroot = NULL;
390 int errcode = CR_NOERR;
392 if ((errcode = crule_gettoken(&next_tok, &ruleptr)) == CR_NOERR)
394 if ((errcode = crule_parseorexpr(&ruleroot, &next_tok, &ruleptr))
397 if (ruleroot != NULL)
399 if (next_tok == CR_END)
400 return ((char *)ruleroot);
402 errcode = CR_UNEXPCTTOK;
405 errcode = CR_EXPCTOR;
408 if (ruleroot != NULL)
409 crule_free((char **)&ruleroot);
410 #if !defined(CR_DEBUG) && !defined(CR_CHKCONF)
411 Debug((DEBUG_ERROR, "%s in rule: %s", crule_errstr[errcode], rule));
413 fprintf(stderr, "%s in rule: %s\n", crule_errstr[errcode], rule);
418 static int crule_parseorexpr(crule_treeptr * orrootp, int *next_tokp,
421 int errcode = CR_NOERR;
422 crule_treeptr 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 = (crule_treeptr) RunMalloc(sizeof(crule_treeelem));
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(crule_treeptr * androotp, int *next_tokp,
477 int errcode = CR_NOERR;
478 crule_treeptr primary;
479 crule_treeptr andptr;
482 while (errcode == CR_NOERR)
484 errcode = crule_parseprimary(&primary, next_tokp, ruleptr);
485 if ((errcode == CR_NOERR) && (*next_tokp == CR_AND))
487 andptr = (crule_treeptr) RunMalloc(sizeof(crule_treeelem));
489 fprintf(stderr, "allocating and element at %ld\n", andptr);
491 andptr->funcptr = crule__andor;
493 andptr->arg[2] = (void *)0;
494 if (*androotp != NULL)
496 (*androotp)->arg[1] = primary;
497 andptr->arg[0] = *androotp;
500 andptr->arg[0] = primary;
505 if (*androotp != NULL)
509 (*androotp)->arg[1] = primary;
514 (*androotp)->arg[1] = NULL; /* so free doesn't seg fault */
515 return (CR_EXPCTPRIM);
524 if ((errcode = crule_gettoken(next_tokp, ruleptr)) != CR_NOERR)
530 static int crule_parseprimary(crule_treeptr * primrootp,
531 int *next_tokp, char **ruleptr)
533 crule_treeptr *insertionp;
534 int errcode = CR_NOERR;
537 insertionp = primrootp;
538 while (errcode == CR_NOERR)
543 if ((errcode = crule_gettoken(next_tokp, ruleptr)) != CR_NOERR)
545 if ((errcode = crule_parseorexpr(insertionp, next_tokp,
546 ruleptr)) != CR_NOERR)
548 if (*insertionp == NULL)
550 errcode = CR_EXPCTAND;
553 if (*next_tokp != CR_CLOSEPAREN)
555 errcode = CR_EXPCTCLOSE;
558 errcode = crule_gettoken(next_tokp, ruleptr);
561 *insertionp = (crule_treeptr) RunMalloc(sizeof(crule_treeelem));
563 fprintf(stderr, "allocating primary element at %ld\n", *insertionp);
565 (*insertionp)->funcptr = crule__not;
566 (*insertionp)->numargs = 1;
567 (*insertionp)->arg[0] = NULL;
568 insertionp = (crule_treeptr *) & ((*insertionp)->arg[0]);
569 if ((errcode = crule_gettoken(next_tokp, ruleptr)) != CR_NOERR)
573 errcode = crule_parsefunction(insertionp, next_tokp, ruleptr);
576 if (*primrootp == NULL)
579 errcode = CR_EXPCTPRIM;
587 static int crule_parsefunction(crule_treeptr * funcrootp,
588 int *next_tokp, char **ruleptr)
590 int errcode = CR_NOERR;
591 char funcname[CR_MAXARGLEN];
596 crule_getword(funcname, &namelen, CR_MAXARGLEN - 1, ruleptr);
597 if ((errcode = crule_gettoken(next_tokp, ruleptr)) != CR_NOERR)
599 if (*next_tokp == CR_OPENPAREN)
601 for (funcnum = 0;; funcnum++)
603 if (strCasediff(crule_funclist[funcnum].name, funcname) == 0)
605 if (crule_funclist[funcnum].name[0] == '\0')
606 return (CR_UNKNWFUNC);
608 if ((errcode = crule_gettoken(next_tokp, ruleptr)) != CR_NOERR)
610 *funcrootp = (crule_treeptr) RunMalloc(sizeof(crule_treeelem));
612 fprintf(stderr, "allocating function element at %ld\n", *funcrootp);
614 (*funcrootp)->funcptr = NULL; /* for freeing aborted trees */
616 crule_parsearglist(*funcrootp, next_tokp, ruleptr)) != CR_NOERR)
618 if (*next_tokp != CR_CLOSEPAREN)
619 return (CR_EXPCTCLOSE);
620 if ((crule_funclist[funcnum].reqnumargs != (*funcrootp)->numargs) &&
621 (crule_funclist[funcnum].reqnumargs != -1))
622 return (CR_ARGMISMAT);
623 if ((errcode = crule_gettoken(next_tokp, ruleptr)) != CR_NOERR)
625 (*funcrootp)->funcptr = crule_funclist[funcnum].funcptr;
629 return (CR_EXPCTOPEN);
632 static int crule_parsearglist(crule_treeptr argrootp, int *next_tokp,
635 int errcode = CR_NOERR;
636 char *argelemp = NULL;
637 char currarg[CR_MAXARGLEN];
639 char word[CR_MAXARGLEN];
642 argrootp->numargs = 0;
644 while (errcode == CR_NOERR)
649 crule_getword(word, &wordlen, CR_MAXARGLEN - 1, ruleptr);
650 if (currarg[0] != '\0')
652 if ((arglen + wordlen) < (CR_MAXARGLEN - 1))
654 strcat(currarg, " ");
655 strcat(currarg, word);
656 arglen += wordlen + 1;
661 strcpy(currarg, word);
664 errcode = crule_gettoken(next_tokp, ruleptr);
667 #if !defined(CR_DEBUG) && !defined(CR_CHKCONF)
670 if (!BadPtr(currarg))
672 DupString(argelemp, currarg);
673 argrootp->arg[argrootp->numargs++] = (void *)argelemp;
675 if (*next_tokp != CR_COMMA)
678 errcode = crule_gettoken(next_tokp, ruleptr);
686 * This function is recursive.. I wish I knew a nonrecursive way but
687 * I dont. anyway, recursion is fun.. :)
688 * DO NOT CALL THIS FUNTION WITH A POINTER TO A NULL POINTER
689 * (ie: If *elem is NULL, you're doing it wrong - seg fault)
691 void crule_free(char **elem)
695 if ((*((crule_treeptr *) elem))->funcptr == crule__not)
697 /* type conversions and ()'s are fun! ;) here have an asprin.. */
698 if ((*((crule_treeptr *) elem))->arg[0] != NULL)
699 crule_free((char **)&((*((crule_treeptr *) elem))->arg[0]));
701 else if ((*((crule_treeptr *) elem))->funcptr == crule__andor)
703 crule_free((char **)&((*((crule_treeptr *) elem))->arg[0]));
704 if ((*((crule_treeptr *) elem))->arg[1] != NULL)
705 crule_free((char **)&((*((crule_treeptr *) elem))->arg[1]));
709 numargs = (*((crule_treeptr *) elem))->numargs;
710 for (arg = 0; arg < numargs; arg++)
711 RunFree((char *)(*((crule_treeptr *) elem))->arg[arg]);
714 fprintf(stderr, "freeing element at %ld\n", *elem);
721 static void print_tree(crule_treeptr printelem)
725 if (printelem->funcptr == crule__not)
728 print_tree((crule_treeptr) printelem->arg[0]);
731 else if (printelem->funcptr == crule__andor)
734 print_tree((crule_treeptr) printelem->arg[0]);
735 if (printelem->arg[2])
739 print_tree((crule_treeptr) printelem->arg[1]);
744 for (funcnum = 0;; funcnum++)
746 if (printelem->funcptr == crule_funclist[funcnum].funcptr)
748 if (crule_funclist[funcnum].funcptr == NULL)
751 printf("%s(", crule_funclist[funcnum].name);
752 for (arg = 0; arg < printelem->numargs; arg++)
756 printf("%s", (char *)printelem->arg[arg]);
771 while (fgets(indata, 256, stdin) != NULL)
773 indata[strlen(indata) - 1] = '\0'; /* lose the newline */
774 if ((rule = crule_parse(indata)) != NULL)
776 printf("equivalent rule: ");
777 print_tree((crule_treeptr) rule);