3 * @brief Connection rule parser and checker
4 * @version $Id: crule.c,v 1.9 2005/03/20 16:06:17 entrope Exp $
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
);