3 * @brief Connection rule parser and checker
6 * by Tony Vencill (Tonto on IRC) <vencill@bga.com>
8 * The majority of this file is a recursive descent parser used to convert
9 * connection rules into expression trees when the conf file is read.
10 * All parsing structures and types are hidden in the interest of good
11 * programming style and to make possible future data structure changes
12 * without affecting the interface between this patch and the rest of the
13 * server. The only functions accessible externally are crule_parse,
14 * crule_free, and crule_eval. Prototypes for these functions can be
17 * Please direct any connection rule or SmartRoute questions to Tonto on
18 * IRC or by email to vencill@bga.com.
20 * For parser testing, defining CR_DEBUG generates a stand-alone parser
21 * that takes rules from stdin and prints out memory allocation
22 * information and the parsed rule. This stand alone parser is ignorant
23 * of the irc server and thus cannot do rule evaluation. Do not define
24 * this flag when compiling the server! If you wish to generate the
25 * test parser, compile from the ircd directory with a line similar to
26 * cc -o parser -DCR_DEBUG crule.c
28 * The define CR_CHKCONF is provided to generate routines needed in
29 * chkconf. These consist of the parser, a different crule_parse that
30 * prints errors to stderr, and crule_free (just for good style and to
31 * more closely simulate the actual ircd environment). crule_eval and
32 * the rule functions are made empty functions as in the stand-alone
35 * The production rules for the grammar are as follows ("rule" is the
36 * starting production):
39 * orexpr END END is end of input or :
51 * word ( ) word is alphanumeric string, first character
52 * word ( arglist ) must be a letter
62 /* ircd functions and types we need */
65 #include "ircd_alloc.h"
66 #include "ircd_chattr.h"
67 #include "ircd_string.h"
76 #else /* includes and defines to make the stand-alone test parser */
81 #define BadPtr(x) (!(x) || (*(x) == '\0'))
82 #define DupString(x,y) \
84 x = (char*) MyMalloc(strlen(y)+1); \
88 /* We don't care about collation discrepancies here, it seems.... */
89 #define ircd_strcmp strcasecmp
96 #if defined(CR_DEBUG) || defined(CR_CHKCONF)
99 #define MyMalloc malloc
105 /* some constants and shared data types */
106 #define CR_MAXARGLEN 80 /**< Maximum arg length (must be > HOSTLEN) */
107 #define CR_MAXARGS 3 /**< Maximum number of args for a rule */
110 * Some symbols for easy reading
113 /** Input scanner tokens. */
115 CR_UNKNOWN, /**< Unknown token type. */
116 CR_END, /**< End of input ('\\0' or ':'). */
117 CR_AND, /**< Logical and operator (&&). */
118 CR_OR, /**< Logical or operator (||). */
119 CR_NOT, /**< Logical not operator (!). */
120 CR_OPENPAREN, /**< Open parenthesis. */
121 CR_CLOSEPAREN, /**< Close parenthesis. */
122 CR_COMMA, /**< Comma. */
123 CR_WORD /**< Something that looks like a hostmask (alphanumerics, "*?.-"). */
126 /** Parser error codes. */
128 CR_NOERR, /**< No error. */
129 CR_UNEXPCTTOK, /**< Invalid token given context. */
130 CR_UNKNWTOK, /**< Input did not form a valid token. */
131 CR_EXPCTAND, /**< Did not see expected && operator. */
132 CR_EXPCTOR, /**< Did not see expected || operator. */
133 CR_EXPCTPRIM, /**< Expected a primitive (parentheses, ! or word). */
134 CR_EXPCTOPEN, /**< Expected an open parenthesis after function name. */
135 CR_EXPCTCLOSE, /**< Expected a close parenthesis to match open parenthesis. */
136 CR_UNKNWFUNC, /**< Attempt to use an unknown function. */
137 CR_ARGMISMAT /**< Wrong number of arguments to function. */
141 * Expression tree structure, function pointer, and tree pointer local!
143 /** Evaluation function for a connection rule. */
144 typedef int (*crule_funcptr) (int, void **);
146 /** Node in a connection rule tree. */
148 crule_funcptr funcptr; /**< Evaluation function for this node. */
149 int numargs; /**< Number of arguments. */
150 void *arg[CR_MAXARGS]; /**< Array of arguments. For operators, each arg
151 is a tree element; for functions, each arg is
155 /** Typedef to save typing effort. */
156 typedef struct CRuleNode* CRuleNodePtr;
158 /* local rule function prototypes */
159 static int crule_connected(int, void *[]);
160 static int crule_directcon(int, void *[]);
161 static int crule_via(int, void *[]);
162 static int crule_directop(int, void *[]);
163 static int crule__andor(int, void *[]);
164 static int crule__not(int, void *[]);
166 /* local parsing function prototypes */
167 static int crule_gettoken(int* token, const char** str);
168 static void crule_getword(char*, int*, size_t, const char**);
169 static int crule_parseandexpr(CRuleNodePtr*, int *, const char**);
170 static int crule_parseorexpr(CRuleNodePtr*, int *, const char**);
171 static int crule_parseprimary(CRuleNodePtr*, int *, const char**);
172 static int crule_parsefunction(CRuleNodePtr*, int *, const char**);
173 static int crule_parsearglist(CRuleNodePtr, int *, const char**);
175 #if defined(CR_DEBUG) || defined(CR_CHKCONF)
177 * Prototypes for the test parser; if not debugging,
178 * these are defined in h.h
180 struct CRuleNode* crule_parse(const char*);
181 void crule_free(struct CRuleNode**);
183 void print_tree(CRuleNodePtr);
187 /** Error messages, indexed by the corresponding crule_errcode. */
188 char *crule_errstr[] = {
189 "Unknown error", /* NOERR? - for completeness */
190 "Unexpected token", /* UNEXPCTTOK */
191 "Unknown token", /* UNKNWTOK */
192 "And expr expected", /* EXPCTAND */
193 "Or expr expected", /* EXPCTOR */
194 "Primary expected", /* EXPCTPRIM */
195 "( expected", /* EXPCTOPEN */
196 ") expected", /* EXPCTCLOSE */
197 "Unknown function", /* UNKNWFUNC */
198 "Argument mismatch" /* ARGMISMAT */
201 /** Connection rule function table entry. */
202 struct crule_funclistent {
203 char name[15]; /**< Function name. */
204 int reqnumargs; /**< Required number of arguments. */
205 crule_funcptr funcptr; /**< Handler function. */
208 /** Defined connection rules. */
209 struct crule_funclistent crule_funclist[] = {
210 /* maximum function name length is 14 chars */
211 {"connected", 1, crule_connected},
212 {"directcon", 1, crule_directcon},
213 {"via", 2, crule_via},
214 {"directop", 0, crule_directop},
215 {"", 0, NULL} /* this must be here to mark end of list */
218 /** Check whether any connected server matches crulearg[0].
219 * @param[in] numargs Number of valid args in \a crulearg.
220 * @param[in] crulearg Argument array.
221 * @return Non-zero if the condition is true, zero if not.
223 static int crule_connected(int numargs, void *crulearg[])
225 #if !defined(CR_DEBUG) && !defined(CR_CHKCONF)
226 struct Client *acptr;
228 /* taken from m_links */
229 for (acptr = GlobalClientList; acptr; acptr = cli_next(acptr))
231 if (!IsServer(acptr) && !IsMe(acptr))
233 if (match((char *)crulearg[0], cli_name(acptr)))
241 /** Check whether any directly connected server matches crulearg[0].
242 * @param[in] numargs Number of valid args in \a crulearg.
243 * @param[in] crulearg Argument array.
244 * @return Non-zero if the condition is true, zero if not.
246 static int crule_directcon(int numargs, void *crulearg[])
248 #if !defined(CR_DEBUG) && !defined(CR_CHKCONF)
250 struct Client *acptr;
252 /* adapted from m_trace and exit_one_client */
253 for (i = 0; i <= HighestFd; i++)
255 if (!(acptr = LocalClientArray[i]) || !IsServer(acptr))
257 if (match((char *)crulearg[0], cli_name(acptr)))
265 /** Check whether a connected server matching crulearg[1] is
266 * connnected to me behind one matching crulearg[0].
267 * @param[in] numargs Number of valid args in \a crulearg.
268 * @param[in] crulearg Argument array.
269 * @return Non-zero if the condition is true, zero if not.
271 static int crule_via(int numargs, void *crulearg[])
273 #if !defined(CR_DEBUG) && !defined(CR_CHKCONF)
274 struct Client *acptr;
276 /* adapted from m_links */
277 for (acptr = GlobalClientList; acptr; acptr = cli_next(acptr))
279 if (!IsServer(acptr) && !IsMe(acptr))
281 if (match((char *)crulearg[1], cli_name(acptr)))
283 if (match((char *)crulearg[0], cli_name(cli_from(acptr))))
291 /** Check whether we have a local IRC operator.
292 * @param[in] numargs Number of valid args in \a crulearg.
293 * @param[in] crulearg Argument array.
294 * @return Non-zero if the condition is true, zero if not.
296 static int crule_directop(int numargs, void *crulearg[])
298 #if !defined(CR_DEBUG) && !defined(CR_CHKCONF)
300 struct Client *acptr;
302 /* adapted from m_trace */
303 for (i = 0; i <= HighestFd; i++)
305 if (!(acptr = LocalClientArray[i]) || !IsAnOper(acptr))
313 /** Evaluate a connection rule.
314 * @param[in] rule Rule to evalute.
315 * @return Non-zero if the rule allows the connection, zero otherwise.
317 int crule_eval(struct CRuleNode* rule)
319 return (rule->funcptr(rule->numargs, rule->arg));
322 /** Perform an and-or-or test on crulearg[0] and crulearg[1].
323 * If crulearg[2] is non-NULL, it means do OR; if it is NULL, do AND.
324 * @param[in] numargs Number of valid args in \a crulearg.
325 * @param[in] crulearg Argument array.
326 * @return Non-zero if the condition is true, zero if not.
328 static int crule__andor(int numargs, void *crulearg[])
332 result1 = crule_eval(crulearg[0]);
333 if (crulearg[2]) /* or */
334 return (result1 || crule_eval(crulearg[1]));
336 return (result1 && crule_eval(crulearg[1]));
339 /** Logically invert the result of crulearg[0].
340 * @param[in] numargs Number of valid args in \a crulearg.
341 * @param[in] crulearg Argument array.
342 * @return Non-zero if the condition is true, zero if not.
344 static int crule__not(int numargs, void *crulearg[])
346 return (!crule_eval(crulearg[0]));
349 /** Scan an input token from \a ruleptr.
350 * @param[out] next_tokp Receives type of next token.
351 * @param[in,out] ruleptr Next readable character from input.
352 * @return Either CR_UNKNWTOK if the input was unrecognizable, else CR_NOERR.
354 static int crule_gettoken(int* next_tokp, const char** ruleptr)
358 *next_tokp = CR_UNKNOWN;
359 while (*next_tokp == CR_UNKNOWN)
360 switch (*(*ruleptr)++)
368 else if (pending == '&')
371 return (CR_UNKNWTOK);
376 else if (pending == '|')
379 return (CR_UNKNWTOK);
385 *next_tokp = CR_OPENPAREN;
388 *next_tokp = CR_CLOSEPAREN;
391 *next_tokp = CR_COMMA;
401 if ((IsAlpha(*(--(*ruleptr)))) || (**ruleptr == '*') ||
402 (**ruleptr == '?') || (**ruleptr == '.') || (**ruleptr == '-'))
403 *next_tokp = CR_WORD;
405 return (CR_UNKNWTOK);
411 /** Scan a word from \a ruleptr.
412 * @param[out] word Output buffer.
413 * @param[out] wordlenp Length of word written to \a word (not including terminating NUL).
414 * @param[in] maxlen Maximum number of bytes writable to \a word.
415 * @param[in,out] ruleptr Next readable character from input.
417 static void crule_getword(char* word, int* wordlenp, size_t maxlen, const char** ruleptr)
422 while ((size_t)(word_ptr - word) < maxlen
423 && (IsAlnum(**ruleptr)
424 || **ruleptr == '*' || **ruleptr == '?'
425 || **ruleptr == '.' || **ruleptr == '-'))
426 *word_ptr++ = *(*ruleptr)++;
428 *wordlenp = word_ptr - word;
431 /** Parse an entire rule.
432 * @param[in] rule Text form of rule.
433 * @return CRuleNode for rule, or NULL if there was a parse error.
435 struct CRuleNode* crule_parse(const char *rule)
437 const char* ruleptr = rule;
439 struct CRuleNode* ruleroot = 0;
440 int errcode = CR_NOERR;
442 if ((errcode = crule_gettoken(&next_tok, &ruleptr)) == CR_NOERR) {
443 if ((errcode = crule_parseorexpr(&ruleroot, &next_tok, &ruleptr)) == CR_NOERR) {
444 if (ruleroot != NULL) {
445 if (next_tok == CR_END)
448 errcode = CR_UNEXPCTTOK;
451 errcode = CR_EXPCTOR;
454 if (ruleroot != NULL)
455 crule_free(&ruleroot);
456 #if !defined(CR_DEBUG) && !defined(CR_CHKCONF)
457 Debug((DEBUG_ERROR, "%s in rule: %s", crule_errstr[errcode], rule));
459 fprintf(stderr, "%s in rule: %s\n", crule_errstr[errcode], rule);
464 /** Parse an or expression.
465 * @param[out] orrootp Receives parsed node.
466 * @param[in,out] next_tokp Next input token type.
467 * @param[in,out] ruleptr Next input character.
468 * @return A crule_errcode value.
470 static int crule_parseorexpr(CRuleNodePtr * orrootp, int *next_tokp, const char** ruleptr)
472 int errcode = CR_NOERR;
473 CRuleNodePtr andexpr;
477 while (errcode == CR_NOERR)
479 errcode = crule_parseandexpr(&andexpr, next_tokp, ruleptr);
480 if ((errcode == CR_NOERR) && (*next_tokp == CR_OR))
482 orptr = (CRuleNodePtr) MyMalloc(sizeof(struct CRuleNode));
484 fprintf(stderr, "allocating or element at %ld\n", orptr);
486 orptr->funcptr = crule__andor;
488 orptr->arg[2] = (void *)1;
489 if (*orrootp != NULL)
491 (*orrootp)->arg[1] = andexpr;
492 orptr->arg[0] = *orrootp;
495 orptr->arg[0] = andexpr;
500 if (*orrootp != NULL)
504 (*orrootp)->arg[1] = andexpr;
509 (*orrootp)->arg[1] = NULL; /* so free doesn't seg fault */
510 return (CR_EXPCTAND);
519 if ((errcode = crule_gettoken(next_tokp, ruleptr)) != CR_NOERR)
525 /** Parse an and expression.
526 * @param[out] androotp Receives parsed node.
527 * @param[in,out] next_tokp Next input token type.
528 * @param[in,out] ruleptr Next input character.
529 * @return A crule_errcode value.
531 static int crule_parseandexpr(CRuleNodePtr * androotp, int *next_tokp, const char** ruleptr)
533 int errcode = CR_NOERR;
534 CRuleNodePtr primary;
538 while (errcode == CR_NOERR)
540 errcode = crule_parseprimary(&primary, next_tokp, ruleptr);
541 if ((errcode == CR_NOERR) && (*next_tokp == CR_AND))
543 andptr = (CRuleNodePtr) MyMalloc(sizeof(struct CRuleNode));
545 fprintf(stderr, "allocating and element at %ld\n", andptr);
547 andptr->funcptr = crule__andor;
549 andptr->arg[2] = (void *)0;
550 if (*androotp != NULL)
552 (*androotp)->arg[1] = primary;
553 andptr->arg[0] = *androotp;
556 andptr->arg[0] = primary;
561 if (*androotp != NULL)
565 (*androotp)->arg[1] = primary;
570 (*androotp)->arg[1] = NULL; /* so free doesn't seg fault */
571 return (CR_EXPCTPRIM);
580 if ((errcode = crule_gettoken(next_tokp, ruleptr)) != CR_NOERR)
586 /** Parse a primary expression.
587 * @param[out] primrootp Receives parsed node.
588 * @param[in,out] next_tokp Next input token type.
589 * @param[in,out] ruleptr Next input character.
590 * @return A crule_errcode value.
592 static int crule_parseprimary(CRuleNodePtr* primrootp, int *next_tokp, const char** ruleptr)
594 CRuleNodePtr *insertionp;
595 int errcode = CR_NOERR;
598 insertionp = primrootp;
599 while (errcode == CR_NOERR)
604 if ((errcode = crule_gettoken(next_tokp, ruleptr)) != CR_NOERR)
606 if ((errcode = crule_parseorexpr(insertionp, next_tokp, ruleptr)) != CR_NOERR)
608 if (*insertionp == NULL)
610 errcode = CR_EXPCTAND;
613 if (*next_tokp != CR_CLOSEPAREN)
615 errcode = CR_EXPCTCLOSE;
618 errcode = crule_gettoken(next_tokp, ruleptr);
621 *insertionp = (CRuleNodePtr) MyMalloc(sizeof(struct CRuleNode));
623 fprintf(stderr, "allocating primary element at %ld\n", *insertionp);
625 (*insertionp)->funcptr = crule__not;
626 (*insertionp)->numargs = 1;
627 (*insertionp)->arg[0] = NULL;
628 insertionp = (CRuleNodePtr *) & ((*insertionp)->arg[0]);
629 if ((errcode = crule_gettoken(next_tokp, ruleptr)) != CR_NOERR)
633 errcode = crule_parsefunction(insertionp, next_tokp, ruleptr);
636 if (*primrootp == NULL)
639 errcode = CR_EXPCTPRIM;
647 /** Parse a function call.
648 * @param[out] funcrootp Receives parsed node.
649 * @param[in,out] next_tokp Next input token type.
650 * @param[in,out] ruleptr Next input character.
651 * @return A crule_errcode value.
653 static int crule_parsefunction(CRuleNodePtr* funcrootp, int* next_tokp, const char** ruleptr)
655 int errcode = CR_NOERR;
656 char funcname[CR_MAXARGLEN];
661 crule_getword(funcname, &namelen, CR_MAXARGLEN - 1, ruleptr);
662 if ((errcode = crule_gettoken(next_tokp, ruleptr)) != CR_NOERR)
664 if (*next_tokp == CR_OPENPAREN)
666 for (funcnum = 0;; funcnum++)
668 if (0 == ircd_strcmp(crule_funclist[funcnum].name, funcname))
670 if (crule_funclist[funcnum].name[0] == '\0')
671 return (CR_UNKNWFUNC);
673 if ((errcode = crule_gettoken(next_tokp, ruleptr)) != CR_NOERR)
675 *funcrootp = (CRuleNodePtr) MyMalloc(sizeof(struct CRuleNode));
677 fprintf(stderr, "allocating function element at %ld\n", *funcrootp);
679 (*funcrootp)->funcptr = NULL; /* for freeing aborted trees */
681 crule_parsearglist(*funcrootp, next_tokp, ruleptr)) != CR_NOERR)
683 if (*next_tokp != CR_CLOSEPAREN)
684 return (CR_EXPCTCLOSE);
685 if ((crule_funclist[funcnum].reqnumargs != (*funcrootp)->numargs) &&
686 (crule_funclist[funcnum].reqnumargs != -1))
687 return (CR_ARGMISMAT);
688 if ((errcode = crule_gettoken(next_tokp, ruleptr)) != CR_NOERR)
690 (*funcrootp)->funcptr = crule_funclist[funcnum].funcptr;
694 return (CR_EXPCTOPEN);
697 /** Parse the argument list to a CRuleNode.
698 * @param[in,out] argrootp Node whos argument list is being populated.
699 * @param[in,out] next_tokp Next input token type.
700 * @param[in,out] ruleptr Next input character.
701 * @return A crule_errcode value.
703 static int crule_parsearglist(CRuleNodePtr argrootp, int *next_tokp, const char** ruleptr)
705 int errcode = CR_NOERR;
706 char *argelemp = NULL;
707 char currarg[CR_MAXARGLEN];
709 char word[CR_MAXARGLEN];
712 argrootp->numargs = 0;
714 while (errcode == CR_NOERR)
719 crule_getword(word, &wordlen, CR_MAXARGLEN - 1, ruleptr);
720 if (currarg[0] != '\0')
722 if ((arglen + wordlen) < (CR_MAXARGLEN - 1))
724 strcat(currarg, " ");
725 strcat(currarg, word);
726 arglen += wordlen + 1;
731 strcpy(currarg, word);
734 errcode = crule_gettoken(next_tokp, ruleptr);
737 #if !defined(CR_DEBUG) && !defined(CR_CHKCONF)
740 if (!BadPtr(currarg))
742 DupString(argelemp, currarg);
743 argrootp->arg[argrootp->numargs++] = (void *)argelemp;
745 if (*next_tokp != CR_COMMA)
748 errcode = crule_gettoken(next_tokp, ruleptr);
756 * This function is recursive.. I wish I knew a nonrecursive way but
757 * I don't. Anyway, recursion is fun.. :)
758 * DO NOT CALL THIS FUNCTION WITH A POINTER TO A NULL POINTER
759 * (i.e.: If *elem is NULL, you're doing it wrong - seg fault)
761 /** Free a connection rule and all its children.
762 * @param[in,out] elem Pointer to pointer to element to free. MUST NOT BE NULL.
764 void crule_free(struct CRuleNode** elem)
768 if ((*(elem))->funcptr == crule__not)
770 /* type conversions and ()'s are fun! ;) here have an aspirin.. */
771 if ((*(elem))->arg[0] != NULL)
772 crule_free((struct CRuleNode**) &((*(elem))->arg[0]));
774 else if ((*(elem))->funcptr == crule__andor)
776 crule_free((struct CRuleNode**) &((*(elem))->arg[0]));
777 if ((*(elem))->arg[1] != NULL)
778 crule_free((struct CRuleNode**) &((*(elem))->arg[1]));
782 numargs = (*(elem))->numargs;
783 for (arg = 0; arg < numargs; arg++)
784 MyFree((*(elem))->arg[arg]);
787 fprintf(stderr, "freeing element at %ld\n", *elem);
794 /** Display a connection rule as text.
795 * @param[in] printelem Connection rule to display.
797 static void print_tree(CRuleNodePtr printelem)
801 if (printelem->funcptr == crule__not)
804 print_tree((CRuleNodePtr) printelem->arg[0]);
807 else if (printelem->funcptr == crule__andor)
810 print_tree((CRuleNodePtr) printelem->arg[0]);
811 if (printelem->arg[2])
815 print_tree((CRuleNodePtr) printelem->arg[1]);
820 for (funcnum = 0;; funcnum++)
822 if (printelem->funcptr == crule_funclist[funcnum].funcptr)
824 if (crule_funclist[funcnum].funcptr == NULL)
827 printf("%s(", crule_funclist[funcnum].name);
828 for (arg = 0; arg < printelem->numargs; arg++)
832 printf("%s", (char *)printelem->arg[arg]);
841 /** Read connection rules from stdin and display parsed forms as text.
850 while (fgets(indata, 256, stdin) != NULL)
852 indata[strlen(indata) - 1] = '\0'; /* lose the newline */
853 if ((rule = crule_parse(indata)) != NULL)
855 printf("equivalent rule: ");
856 print_tree((CRuleNodePtr) rule);