[lttng-tools.git] / src / lib / lttng-ctl / filter / filter-parser.y

%{
/*
 * filter-parser.y
 *
 * LTTng filter expression parser
 *
 * Copyright 2012 - Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
 *
 * This library is free software; you can redistribute it and/or modify it
 * under the terms of the GNU Lesser General Public License, version 2.1 only,
 * as published by the Free Software Foundation.
 *
 * This library is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
 * Lesser General Public License for more details.
 *
 * You should have received a copy of the GNU Lesser General Public License
 * along with this library; if not, write to the Free Software Foundation,
 * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
 *
 * Grammar inspired from http://www.quut.com/c/ANSI-C-grammar-y.html
 */

#include <stdio.h>
#include <unistd.h>
#include <string.h>
#include <stdlib.h>
#include <assert.h>
#include <errno.h>
#include <inttypes.h>
#include "filter-ast.h"
#include "filter-parser.h"

__attribute__((visibility("hidden")))
int yydebug;
__attribute__((visibility("hidden")))
int filter_parser_debug = 0;

__attribute__((visibility("hidden")))
int yyparse(struct filter_parser_ctx *parser_ctx);
__attribute__((visibility("hidden")))
int yylex(union YYSTYPE *yyval, struct filter_parser_ctx *parser_ctx);
__attribute__((visibility("hidden")))
int yylex_init_extra(struct filter_parser_ctx *parser_ctx, yyscan_t * ptr_yy_globals);
__attribute__((visibility("hidden")))
int yylex_destroy(yyscan_t yyparser_ctx);
__attribute__((visibility("hidden")))
void yyrestart(FILE * in_str, yyscan_t parser_ctx);

struct gc_string {
	struct cds_list_head gc;
	size_t alloclen;
	char s[];
};

static const char *node_type_to_str[] = {
	[ NODE_UNKNOWN ] = "NODE_UNKNOWN",
	[ NODE_ROOT ] = "NODE_ROOT",
	[ NODE_EXPRESSION ] = "NODE_EXPRESSION",
	[ NODE_OP ] = "NODE_OP",
	[ NODE_UNARY_OP ] = "NODE_UNARY_OP",
};

__attribute__((visibility("hidden")))
const char *node_type(struct filter_node *node)
{
	if (node->type < NR_NODE_TYPES)
		return node_type_to_str[node->type];
	else
		return NULL;
}

static struct gc_string *gc_string_alloc(struct filter_parser_ctx *parser_ctx,
					 size_t len)
{
	struct gc_string *gstr;
	size_t alloclen;

	/* TODO: could be faster with find first bit or glib Gstring */
	/* sizeof long to account for malloc header (int or long ?) */
	for (alloclen = 8; alloclen < sizeof(long) + sizeof(*gstr) + len;
	     alloclen *= 2);

	gstr = malloc(alloclen);
	cds_list_add(&gstr->gc, &parser_ctx->allocated_strings);
	gstr->alloclen = alloclen;
	return gstr;
}

/*
 * note: never use gc_string_append on a string that has external references.
 * gsrc will be garbage collected immediately, and gstr might be.
 * Should only be used to append characters to a string literal or constant.
 */
__attribute__((visibility("hidden")))
struct gc_string *gc_string_append(struct filter_parser_ctx *parser_ctx,
				   struct gc_string *gstr,
				   struct gc_string *gsrc)
{
	size_t newlen = strlen(gsrc->s) + strlen(gstr->s) + 1;
	size_t alloclen;

	/* TODO: could be faster with find first bit or glib Gstring */
	/* sizeof long to account for malloc header (int or long ?) */
	for (alloclen = 8; alloclen < sizeof(long) + sizeof(*gstr) + newlen;
	     alloclen *= 2);

	if (alloclen > gstr->alloclen) {
		struct gc_string *newgstr;

		newgstr = gc_string_alloc(parser_ctx, newlen);
		strcpy(newgstr->s, gstr->s);
		strcat(newgstr->s, gsrc->s);
		cds_list_del(&gstr->gc);
		free(gstr);
		gstr = newgstr;
	} else {
		strcat(gstr->s, gsrc->s);
	}
	cds_list_del(&gsrc->gc);
	free(gsrc);
	return gstr;
}

__attribute__((visibility("hidden")))
void setstring(struct filter_parser_ctx *parser_ctx, YYSTYPE *lvalp, const char *src)
{
	lvalp->gs = gc_string_alloc(parser_ctx, strlen(src) + 1);
	strcpy(lvalp->gs->s, src);
}

static struct filter_node *make_node(struct filter_parser_ctx *scanner,
				  enum node_type type)
{
	struct filter_ast *ast = filter_parser_get_ast(scanner);
	struct filter_node *node;

	node = malloc(sizeof(*node));
	if (!node)
		return NULL;
	memset(node, 0, sizeof(*node));
	node->type = type;
	cds_list_add(&node->gc, &ast->allocated_nodes);

	switch (type) {
	case NODE_ROOT:
		fprintf(stderr, "[error] %s: trying to create root node\n", __func__);
		break;

	case NODE_EXPRESSION:
		break;
	case NODE_OP:
		break;
	case NODE_UNARY_OP:
		break;

	case NODE_UNKNOWN:
	default:
		fprintf(stderr, "[error] %s: unknown node type %d\n", __func__,
			(int) type);
		break;
	}

	return node;
}

static struct filter_node *make_op_node(struct filter_parser_ctx *scanner,
			enum op_type type,
			struct filter_node *lchild,
			struct filter_node *rchild)
{
	struct filter_ast *ast = filter_parser_get_ast(scanner);
	struct filter_node *node;

	node = malloc(sizeof(*node));
	if (!node)
		return NULL;
	memset(node, 0, sizeof(*node));
	node->type = NODE_OP;
	cds_list_add(&node->gc, &ast->allocated_nodes);
	node->u.op.type = type;
	node->u.op.lchild = lchild;
	node->u.op.rchild = rchild;
	return node;
}

__attribute__((visibility("hidden")))
void yyerror(struct filter_parser_ctx *parser_ctx, const char *str)
{
	fprintf(stderr, "error %s\n", str);
}
 
__attribute__((visibility("hidden")))
int yywrap(void)
{
	return 1;
} 

#define parse_error(parser_ctx, str)				\
do {								\
	yyerror(parser_ctx, YY_("parse error: " str "\n"));	\
	YYERROR;						\
} while (0)

static void free_strings(struct cds_list_head *list)
{
	struct gc_string *gstr, *tmp;

	cds_list_for_each_entry_safe(gstr, tmp, list, gc)
		free(gstr);
}

static struct filter_ast *filter_ast_alloc(void)
{
	struct filter_ast *ast;

	ast = malloc(sizeof(*ast));
	if (!ast)
		return NULL;
	memset(ast, 0, sizeof(*ast));
	CDS_INIT_LIST_HEAD(&ast->allocated_nodes);
	ast->root.type = NODE_ROOT;
	return ast;
}

static void filter_ast_free(struct filter_ast *ast)
{
	struct filter_node *node, *tmp;

	cds_list_for_each_entry_safe(node, tmp, &ast->allocated_nodes, gc)
		free(node);
}

__attribute__((visibility("hidden")))
int filter_parser_ctx_append_ast(struct filter_parser_ctx *parser_ctx)
{
	return yyparse(parser_ctx);
}

__attribute__((visibility("hidden")))
struct filter_parser_ctx *filter_parser_ctx_alloc(FILE *input)
{
	struct filter_parser_ctx *parser_ctx;
	int ret;

	yydebug = filter_parser_debug;

	parser_ctx = malloc(sizeof(*parser_ctx));
	if (!parser_ctx)
		return NULL;
	memset(parser_ctx, 0, sizeof(*parser_ctx));

	ret = yylex_init_extra(parser_ctx, &parser_ctx->scanner);
	if (ret) {
		fprintf(stderr, "yylex_init error\n");
		goto cleanup_parser_ctx;
	}
	/* Start processing new stream */
	yyrestart(input, parser_ctx->scanner);

	parser_ctx->ast = filter_ast_alloc();
	if (!parser_ctx->ast)
		goto cleanup_lexer;
	CDS_INIT_LIST_HEAD(&parser_ctx->allocated_strings);

	if (yydebug)
		fprintf(stdout, "parser_ctx input is a%s.\n",
			isatty(fileno(input)) ? "n interactive tty" :
						" noninteractive file");

	return parser_ctx;

cleanup_lexer:
	ret = yylex_destroy(parser_ctx->scanner);
	if (!ret)
		fprintf(stderr, "yylex_destroy error\n");
cleanup_parser_ctx:
	free(parser_ctx);
	return NULL;
}

__attribute__((visibility("hidden")))
void filter_parser_ctx_free(struct filter_parser_ctx *parser_ctx)
{
	int ret;

	free_strings(&parser_ctx->allocated_strings);
	filter_ast_free(parser_ctx->ast);
	ret = yylex_destroy(parser_ctx->scanner);
	if (ret)
		fprintf(stderr, "yylex_destroy error\n");
	free(parser_ctx);
}

%}

%define api.pure
	/* %locations */
%parse-param {struct filter_parser_ctx *parser_ctx}
%lex-param {struct filter_parser_ctx *parser_ctx}
%start translation_unit
%token CHARACTER_CONSTANT_START SQUOTE STRING_LITERAL_START DQUOTE
%token ESCSEQ CHAR_STRING_TOKEN
%token DECIMAL_CONSTANT OCTAL_CONSTANT HEXADECIMAL_CONSTANT FLOAT_CONSTANT
%token LSBRAC RSBRAC LPAREN RPAREN LBRAC RBRAC RARROW
%token STAR PLUS MINUS
%token MOD_OP DIV_OP RIGHT_OP LEFT_OP
%token EQ_OP NE_OP LE_OP GE_OP LT_OP GT_OP AND_OP OR_OP NOT_OP
%token ASSIGN COLON SEMICOLON DOTDOTDOT DOT EQUAL COMMA
%token XOR_BIN AND_BIN OR_BIN NOT_BIN

%token <gs> IDENTIFIER
%token ERROR
%union
{
	long long ll;
	char c;
	struct gc_string *gs;
	struct filter_node *n;
}

%type <gs> s_char s_char_sequence c_char c_char_sequence

%type <n> primary_expression
%type <n> postfix_expression
%type <n> unary_expression
%type <n> unary_operator
%type <n> multiplicative_expression
%type <n> additive_expression
%type <n> shift_expression
%type <n> relational_expression
%type <n> equality_expression
%type <n> and_expression
%type <n> exclusive_or_expression
%type <n> inclusive_or_expression
%type <n> logical_and_expression
%type <n> logical_or_expression
%type <n> expression

%%


/* 1.5 Constants */

c_char_sequence:
		c_char
		{	$$ = $1;					}
	|	c_char_sequence c_char
		{	$$ = gc_string_append(parser_ctx, $1, $2);		}
	;

c_char:
		CHAR_STRING_TOKEN
		{	$$ = yylval.gs;					}
	|	ESCSEQ
		{
			parse_error(parser_ctx, "escape sequences not supported yet");
		}
	;

/* 1.6 String literals */

s_char_sequence:
		s_char
		{	$$ = $1;					}
	|	s_char_sequence s_char
		{	$$ = gc_string_append(parser_ctx, $1, $2);		}
	;

s_char:
		CHAR_STRING_TOKEN
		{	$$ = yylval.gs;					}
	|	ESCSEQ
		{
			parse_error(parser_ctx, "escape sequences not supported yet");
		}
	;

primary_expression
	:	IDENTIFIER
		{
			$$ = make_node(parser_ctx, NODE_EXPRESSION);
			$$->u.expression.type = AST_EXP_IDENTIFIER;
			$$->u.expression.u.identifier = yylval.gs->s;
		}
	|	DECIMAL_CONSTANT
		{
			$$ = make_node(parser_ctx, NODE_EXPRESSION);
			$$->u.expression.type = AST_EXP_CONSTANT;
			sscanf(yylval.gs->s, "%" PRIu64,
			       &$$->u.expression.u.constant);
		}
	|	OCTAL_CONSTANT
		{
			$$ = make_node(parser_ctx, NODE_EXPRESSION);
			$$->u.expression.type = AST_EXP_CONSTANT;
			sscanf(yylval.gs->s, "0%" PRIo64,
			       &$$->u.expression.u.constant);
		}
	|	HEXADECIMAL_CONSTANT
		{
			$$ = make_node(parser_ctx, NODE_EXPRESSION);
			$$->u.expression.type = AST_EXP_CONSTANT;
			sscanf(yylval.gs->s, "0x%" PRIx64,
			       &$$->u.expression.u.constant);
		}
	|	FLOAT_CONSTANT
		{
			$$ = make_node(parser_ctx, NODE_EXPRESSION);
			$$->u.expression.type = AST_EXP_FLOAT_CONSTANT;
			sscanf(yylval.gs->s, "%lg",
			       &$$->u.expression.u.float_constant);
		}
	|	STRING_LITERAL_START DQUOTE
		{
			$$ = make_node(parser_ctx, NODE_EXPRESSION);
			$$->u.expression.type = AST_EXP_STRING;
			$$->u.expression.u.string = "";
		}
	|	STRING_LITERAL_START s_char_sequence DQUOTE
		{
			$$ = make_node(parser_ctx, NODE_EXPRESSION);
			$$->u.expression.type = AST_EXP_STRING;
			$$->u.expression.u.string = $2->s;
		}
	|	CHARACTER_CONSTANT_START c_char_sequence SQUOTE
		{
			$$ = make_node(parser_ctx, NODE_EXPRESSION);
			$$->u.expression.type = AST_EXP_STRING;
			$$->u.expression.u.string = $2->s;
		}
	|	LPAREN expression RPAREN
		{
			$$ = make_node(parser_ctx, NODE_EXPRESSION);
			$$->u.expression.type = AST_EXP_NESTED;
			$$->u.expression.u.child = $2;
		}
	;

postfix_expression
	: primary_expression
		{	$$ = $1;					}
	| postfix_expression DOT IDENTIFIER
		{
			$$ = make_node(parser_ctx, NODE_EXPRESSION);
			$$->u.expression.type = AST_EXP_IDENTIFIER;
			$$->u.expression.post_op = AST_LINK_DOT;
			$$->u.expression.u.identifier = $3->s;
			$$->u.expression.prev = $1;
		}
	| postfix_expression RARROW IDENTIFIER
		{
			$$ = make_node(parser_ctx, NODE_EXPRESSION);
			$$->u.expression.type = AST_EXP_IDENTIFIER;
			$$->u.expression.post_op = AST_LINK_RARROW;
			$$->u.expression.u.identifier = $3->s;
			$$->u.expression.prev = $1;
		}
	;

unary_expression
	: postfix_expression
		{	$$ = $1;					}
	| unary_operator unary_expression
		{
			$$ = $1;
			$$->u.unary_op.child = $2;
		}
	;

unary_operator
	: PLUS
		{
			$$ = make_node(parser_ctx, NODE_UNARY_OP);
			$$->u.unary_op.type = AST_UNARY_PLUS;
		}
	| MINUS
		{
			$$ = make_node(parser_ctx, NODE_UNARY_OP);
			$$->u.unary_op.type = AST_UNARY_MINUS;
		}
	| NOT_OP
		{
			$$ = make_node(parser_ctx, NODE_UNARY_OP);
			$$->u.unary_op.type = AST_UNARY_NOT;
		}
	| NOT_BIN
		{
			$$ = make_node(parser_ctx, NODE_UNARY_OP);
			$$->u.unary_op.type = AST_UNARY_BIN_NOT;
		}
	;

multiplicative_expression
	: unary_expression
		{	$$ = $1;					}
	| multiplicative_expression STAR unary_expression
		{
			$$ = make_op_node(parser_ctx, AST_OP_MUL, $1, $3);
		}
	| multiplicative_expression DIV_OP unary_expression
		{
			$$ = make_op_node(parser_ctx, AST_OP_DIV, $1, $3);
		}
	| multiplicative_expression MOD_OP unary_expression
		{
			$$ = make_op_node(parser_ctx, AST_OP_MOD, $1, $3);
		}
	;

additive_expression
	: multiplicative_expression
		{	$$ = $1;					}
	| additive_expression PLUS multiplicative_expression
		{
			$$ = make_op_node(parser_ctx, AST_OP_PLUS, $1, $3);
		}
	| additive_expression MINUS multiplicative_expression
		{
			$$ = make_op_node(parser_ctx, AST_OP_MINUS, $1, $3);
		}
	;

shift_expression
	: additive_expression
		{	$$ = $1;					}
	| shift_expression LEFT_OP additive_expression
		{
			$$ = make_op_node(parser_ctx, AST_OP_LSHIFT, $1, $3);
		}
	| shift_expression RIGHT_OP additive_expression
		{
			$$ = make_op_node(parser_ctx, AST_OP_RSHIFT, $1, $3);
		}
	;

relational_expression
	: shift_expression
		{	$$ = $1;					}
	| relational_expression LT_OP shift_expression
		{
			$$ = make_op_node(parser_ctx, AST_OP_LT, $1, $3);
		}
	| relational_expression GT_OP shift_expression
		{
			$$ = make_op_node(parser_ctx, AST_OP_GT, $1, $3);
		}
	| relational_expression LE_OP shift_expression
		{
			$$ = make_op_node(parser_ctx, AST_OP_LE, $1, $3);
		}
	| relational_expression GE_OP shift_expression
		{
			$$ = make_op_node(parser_ctx, AST_OP_GE, $1, $3);
		}
	;

equality_expression
	: relational_expression
		{	$$ = $1;					}
	| equality_expression EQ_OP relational_expression
		{
			$$ = make_op_node(parser_ctx, AST_OP_EQ, $1, $3);
		}
	| equality_expression NE_OP relational_expression
		{
			$$ = make_op_node(parser_ctx, AST_OP_NE, $1, $3);
		}
	;

and_expression
	: equality_expression
		{	$$ = $1;					}
	| and_expression AND_BIN equality_expression
		{
			$$ = make_op_node(parser_ctx, AST_OP_BIN_AND, $1, $3);
		}
	;

exclusive_or_expression
	: and_expression
		{	$$ = $1;					}
	| exclusive_or_expression XOR_BIN and_expression
		{
			$$ = make_op_node(parser_ctx, AST_OP_BIN_XOR, $1, $3);
		}
	;

inclusive_or_expression
	: exclusive_or_expression
		{	$$ = $1;					}
	| inclusive_or_expression OR_BIN exclusive_or_expression
		{
			$$ = make_op_node(parser_ctx, AST_OP_BIN_OR, $1, $3);
		}
	;

logical_and_expression
	: inclusive_or_expression
		{	$$ = $1;					}
	| logical_and_expression AND_OP inclusive_or_expression
		{
			$$ = make_op_node(parser_ctx, AST_OP_AND, $1, $3);
		}
	;

logical_or_expression
	: logical_and_expression
		{	$$ = $1;					}
	| logical_or_expression OR_OP logical_and_expression
		{
			$$ = make_op_node(parser_ctx, AST_OP_OR, $1, $3);
		}
	;

expression
	: logical_or_expression
		{	$$ = $1;					}
	;

translation_unit
	: expression
		{
			parser_ctx->ast->root.u.root.child = $1;
		}
	;
Commit	Line	Data
953192ba MD	1	%{
	2	/*
	3	* filter-parser.y
	4	*
	5	* LTTng filter expression parser
	6	*
	7	* Copyright 2012 - Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
	8	*
	9	* This library is free software; you can redistribute it and/or modify it
	10	* under the terms of the GNU Lesser General Public License, version 2.1 only,
	11	* as published by the Free Software Foundation.
	12	*
	13	* This library is distributed in the hope that it will be useful,
	14	* but WITHOUT ANY WARRANTY; without even the implied warranty of
	15	* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
	16	* Lesser General Public License for more details.
	17	*
	18	* You should have received a copy of the GNU Lesser General Public License
	19	* along with this library; if not, write to the Free Software Foundation,
	20	* Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
	21	*
	22	* Grammar inspired from http://www.quut.com/c/ANSI-C-grammar-y.html
	23	*/
	24
	25	#include <stdio.h>
	26	#include <unistd.h>
	27	#include <string.h>
	28	#include <stdlib.h>
	29	#include <assert.h>
	30	#include <errno.h>
	31	#include <inttypes.h>
953192ba	32	#include "filter-ast.h"
95b9bd90	33	#include "filter-parser.h"
953192ba	34
5439dd25	35	__attribute__((visibility("hidden")))
953192ba	36	int yydebug;
d00c599e	37	__attribute__((visibility("hidden")))
953192ba MD	38	int filter_parser_debug = 0;
953192ba MD	39
5439dd25	40	__attribute__((visibility("hidden")))
953192ba	41	int yyparse(struct filter_parser_ctx *parser_ctx);
5439dd25	42	__attribute__((visibility("hidden")))
953192ba	43	int yylex(union YYSTYPE yyval, struct filter_parser_ctx parser_ctx);
5439dd25	44	__attribute__((visibility("hidden")))
953192ba	45	int yylex_init_extra(struct filter_parser_ctx parser_ctx, yyscan_t ptr_yy_globals);
5439dd25	46	__attribute__((visibility("hidden")))
953192ba	47	int yylex_destroy(yyscan_t yyparser_ctx);
5439dd25	48	__attribute__((visibility("hidden")))
953192ba MD	49	void yyrestart(FILE * in_str, yyscan_t parser_ctx);
	50
	51	struct gc_string {
	52	struct cds_list_head gc;
	53	size_t alloclen;
	54	char s[];
	55	};
	56
	57	static const char *node_type_to_str[] = {
	58	[ NODE_UNKNOWN ] = "NODE_UNKNOWN",
	59	[ NODE_ROOT ] = "NODE_ROOT",
	60	[ NODE_EXPRESSION ] = "NODE_EXPRESSION",
	61	[ NODE_OP ] = "NODE_OP",
	62	[ NODE_UNARY_OP ] = "NODE_UNARY_OP",
	63	};
	64
5439dd25	65	__attribute__((visibility("hidden")))
953192ba MD	66	const char node_type(struct filter_node node)
	67	{
	68	if (node->type < NR_NODE_TYPES)
	69	return node_type_to_str[node->type];
	70	else
	71	return NULL;
	72	}
	73
	74	static struct gc_string gc_string_alloc(struct filter_parser_ctx parser_ctx,
	75	size_t len)
	76	{
	77	struct gc_string *gstr;
	78	size_t alloclen;
	79
	80	/* TODO: could be faster with find first bit or glib Gstring */
	81	/* sizeof long to account for malloc header (int or long ?) */
	82	for (alloclen = 8; alloclen < sizeof(long) + sizeof(*gstr) + len;
	83	alloclen *= 2);
	84
	85	gstr = malloc(alloclen);
	86	cds_list_add(&gstr->gc, &parser_ctx->allocated_strings);
	87	gstr->alloclen = alloclen;
	88	return gstr;
	89	}
	90
	91	/*
	92	* note: never use gc_string_append on a string that has external references.
	93	* gsrc will be garbage collected immediately, and gstr might be.
	94	* Should only be used to append characters to a string literal or constant.
	95	*/
5439dd25	96	__attribute__((visibility("hidden")))
953192ba MD	97	struct gc_string gc_string_append(struct filter_parser_ctx parser_ctx,
	98	struct gc_string *gstr,
	99	struct gc_string *gsrc)
	100	{
	101	size_t newlen = strlen(gsrc->s) + strlen(gstr->s) + 1;
	102	size_t alloclen;
	103
	104	/* TODO: could be faster with find first bit or glib Gstring */
	105	/* sizeof long to account for malloc header (int or long ?) */
	106	for (alloclen = 8; alloclen < sizeof(long) + sizeof(*gstr) + newlen;
	107	alloclen *= 2);
	108
	109	if (alloclen > gstr->alloclen) {
	110	struct gc_string *newgstr;
	111
	112	newgstr = gc_string_alloc(parser_ctx, newlen);
	113	strcpy(newgstr->s, gstr->s);
	114	strcat(newgstr->s, gsrc->s);
	115	cds_list_del(&gstr->gc);
	116	free(gstr);
	117	gstr = newgstr;
	118	} else {
	119	strcat(gstr->s, gsrc->s);
	120	}
	121	cds_list_del(&gsrc->gc);
	122	free(gsrc);
	123	return gstr;
	124	}
	125
5439dd25	126	__attribute__((visibility("hidden")))
953192ba MD	127	void setstring(struct filter_parser_ctx parser_ctx, YYSTYPE lvalp, const char *src)
	128	{
	129	lvalp->gs = gc_string_alloc(parser_ctx, strlen(src) + 1);
	130	strcpy(lvalp->gs->s, src);
	131	}
	132
	133	static struct filter_node make_node(struct filter_parser_ctx scanner,
	134	enum node_type type)
	135	{
	136	struct filter_ast *ast = filter_parser_get_ast(scanner);
	137	struct filter_node *node;
	138
	139	node = malloc(sizeof(*node));
	140	if (!node)
	141	return NULL;
	142	memset(node, 0, sizeof(*node));
	143	node->type = type;
	144	cds_list_add(&node->gc, &ast->allocated_nodes);
	145
	146	switch (type) {
	147	case NODE_ROOT:
	148	fprintf(stderr, "[error] %s: trying to create root node\n", __func__);
	149	break;
	150
	151	case NODE_EXPRESSION:
	152	break;
	153	case NODE_OP:
	154	break;
	155	case NODE_UNARY_OP:
	156	break;
	157
	158	case NODE_UNKNOWN:
	159	default:
	160	fprintf(stderr, "[error] %s: unknown node type %d\n", __func__,
	161	(int) type);
	162	break;
	163	}
	164
	165	return node;
	166	}
	167
	168	static struct filter_node make_op_node(struct filter_parser_ctx scanner,
	169	enum op_type type,
	170	struct filter_node *lchild,
	171	struct filter_node *rchild)
	172	{
	173	struct filter_ast *ast = filter_parser_get_ast(scanner);
	174	struct filter_node *node;
	175
	176	node = malloc(sizeof(*node));
	177	if (!node)
	178	return NULL;
	179	memset(node, 0, sizeof(*node));
	180	node->type = NODE_OP;
	181	cds_list_add(&node->gc, &ast->allocated_nodes);
	182	node->u.op.type = type;
	183	node->u.op.lchild = lchild;
	184	node->u.op.rchild = rchild;
	185	return node;
	186	}
	187
5439dd25	188	__attribute__((visibility("hidden")))
953192ba MD	189	void yyerror(struct filter_parser_ctx parser_ctx, const char str)
	190	{
	191	fprintf(stderr, "error %s\n", str);
	192	}
	193
5439dd25	194	__attribute__((visibility("hidden")))
953192ba MD	195	int yywrap(void)
	196	{
	197	return 1;
	198	}
	199
	200	#define parse_error(parser_ctx, str) \
	201	do { \
	202	yyerror(parser_ctx, YY_("parse error: " str "\n")); \
	203	YYERROR; \
	204	} while (0)
	205
	206	static void free_strings(struct cds_list_head *list)
	207	{
	208	struct gc_string gstr, tmp;
	209
	210	cds_list_for_each_entry_safe(gstr, tmp, list, gc)
	211	free(gstr);
	212	}
	213
	214	static struct filter_ast *filter_ast_alloc(void)
	215	{
	216	struct filter_ast *ast;
	217
	218	ast = malloc(sizeof(*ast));
	219	if (!ast)
	220	return NULL;
	221	memset(ast, 0, sizeof(*ast));
	222	CDS_INIT_LIST_HEAD(&ast->allocated_nodes);
	223	ast->root.type = NODE_ROOT;
	224	return ast;
	225	}
	226
	227	static void filter_ast_free(struct filter_ast *ast)
	228	{
	229	struct filter_node node, tmp;
	230
	231	cds_list_for_each_entry_safe(node, tmp, &ast->allocated_nodes, gc)
	232	free(node);
	233	}
	234
d00c599e	235	__attribute__((visibility("hidden")))
953192ba MD	236	int filter_parser_ctx_append_ast(struct filter_parser_ctx *parser_ctx)
	237	{
	238	return yyparse(parser_ctx);
	239	}
	240
d00c599e	241	__attribute__((visibility("hidden")))
953192ba MD	242	struct filter_parser_ctx filter_parser_ctx_alloc(FILE input)
	243	{
	244	struct filter_parser_ctx *parser_ctx;
	245	int ret;
	246
	247	yydebug = filter_parser_debug;
	248
	249	parser_ctx = malloc(sizeof(*parser_ctx));
	250	if (!parser_ctx)
	251	return NULL;
	252	memset(parser_ctx, 0, sizeof(*parser_ctx));
	253
	254	ret = yylex_init_extra(parser_ctx, &parser_ctx->scanner);
	255	if (ret) {
	256	fprintf(stderr, "yylex_init error\n");
	257	goto cleanup_parser_ctx;
	258	}
	259	/* Start processing new stream */
	260	yyrestart(input, parser_ctx->scanner);
	261
	262	parser_ctx->ast = filter_ast_alloc();
	263	if (!parser_ctx->ast)
	264	goto cleanup_lexer;
	265	CDS_INIT_LIST_HEAD(&parser_ctx->allocated_strings);
	266
	267	if (yydebug)
	268	fprintf(stdout, "parser_ctx input is a%s.\n",
	269	isatty(fileno(input)) ? "n interactive tty" :
	270	" noninteractive file");
	271
	272	return parser_ctx;
	273
	274	cleanup_lexer:
	275	ret = yylex_destroy(parser_ctx->scanner);
	276	if (!ret)
	277	fprintf(stderr, "yylex_destroy error\n");
	278	cleanup_parser_ctx:
	279	free(parser_ctx);
	280	return NULL;
	281	}
	282
d00c599e	283	__attribute__((visibility("hidden")))
953192ba MD	284	void filter_parser_ctx_free(struct filter_parser_ctx *parser_ctx)
	285	{
	286	int ret;
	287
	288	free_strings(&parser_ctx->allocated_strings);
	289	filter_ast_free(parser_ctx->ast);
	290	ret = yylex_destroy(parser_ctx->scanner);
	291	if (ret)
	292	fprintf(stderr, "yylex_destroy error\n");
	293	free(parser_ctx);
	294	}
	295
	296	%}
	297
	298	%define api.pure
	299	/* %locations */
	300	%parse-param {struct filter_parser_ctx *parser_ctx}
	301	%lex-param {struct filter_parser_ctx *parser_ctx}
	302	%start translation_unit
	303	%token CHARACTER_CONSTANT_START SQUOTE STRING_LITERAL_START DQUOTE
	304	%token ESCSEQ CHAR_STRING_TOKEN
e90d8561	305	%token DECIMAL_CONSTANT OCTAL_CONSTANT HEXADECIMAL_CONSTANT FLOAT_CONSTANT
953192ba MD	306	%token LSBRAC RSBRAC LPAREN RPAREN LBRAC RBRAC RARROW
	307	%token STAR PLUS MINUS
	308	%token MOD_OP DIV_OP RIGHT_OP LEFT_OP
	309	%token EQ_OP NE_OP LE_OP GE_OP LT_OP GT_OP AND_OP OR_OP NOT_OP
	310	%token ASSIGN COLON SEMICOLON DOTDOTDOT DOT EQUAL COMMA
	311	%token XOR_BIN AND_BIN OR_BIN NOT_BIN
	312
	313	%token <gs> IDENTIFIER
	314	%token ERROR
	315	%union
	316	{
	317	long long ll;
	318	char c;
	319	struct gc_string *gs;
	320	struct filter_node *n;
	321	}
	322
	323	%type <gs> s_char s_char_sequence c_char c_char_sequence
	324
	325	%type <n> primary_expression
	326	%type <n> postfix_expression
	327	%type <n> unary_expression
	328	%type <n> unary_operator
	329	%type <n> multiplicative_expression
	330	%type <n> additive_expression
	331	%type <n> shift_expression
	332	%type <n> relational_expression
	333	%type <n> equality_expression
	334	%type <n> and_expression
	335	%type <n> exclusive_or_expression
	336	%type <n> inclusive_or_expression
	337	%type <n> logical_and_expression
	338	%type <n> logical_or_expression
	339	%type <n> expression
	340
	341	%%
	342
	343
	344	/* 1.5 Constants */
	345
	346	c_char_sequence:
	347	c_char
	348	{ $$ = $1; }
	349	\| c_char_sequence c_char
	350	{ $$ = gc_string_append(parser_ctx, $1, $2); }
	351	;
	352
	353	c_char:
	354	CHAR_STRING_TOKEN
	355	{ $$ = yylval.gs; }
	356	\| ESCSEQ
	357	{
	358	parse_error(parser_ctx, "escape sequences not supported yet");
	359	}
	360	;
	361
	362	/* 1.6 String literals */
	363
	364	s_char_sequence:
	365	s_char
	366	{ $$ = $1; }
	367	\| s_char_sequence s_char
	368	{ $$ = gc_string_append(parser_ctx, $1, $2); }
	369	;
370
371	s_char:
372	CHAR_STRING_TOKEN
373	{ $$ = yylval.gs; }
374	\| ESCSEQ
375	{
376	parse_error(parser_ctx, "escape sequences not supported yet");
377	}
378	;
379
380	primary_expression
381	: IDENTIFIER
382	{
383	$$ = make_node(parser_ctx, NODE_EXPRESSION);
384	$$->u.expression.type = AST_EXP_IDENTIFIER;
385	$$->u.expression.u.identifier = yylval.gs->s;
386	}
387	\| DECIMAL_CONSTANT
388	{
389	$$ = make_node(parser_ctx, NODE_EXPRESSION);
390	$$->u.expression.type = AST_EXP_CONSTANT;
391	sscanf(yylval.gs->s, "%" PRIu64,
392	&$$->u.expression.u.constant);
393	}
394	\| OCTAL_CONSTANT
395	{
396	$$ = make_node(parser_ctx, NODE_EXPRESSION);
397	$$->u.expression.type = AST_EXP_CONSTANT;
398	sscanf(yylval.gs->s, "0%" PRIo64,
399	&$$->u.expression.u.constant);
400	}
401	\| HEXADECIMAL_CONSTANT
402	{
403	$$ = make_node(parser_ctx, NODE_EXPRESSION);
404	$$->u.expression.type = AST_EXP_CONSTANT;
405	sscanf(yylval.gs->s, "0x%" PRIx64,
406	&$$->u.expression.u.constant);
407	}
e90d8561 MD	408	\| FLOAT_CONSTANT
	409	{
	410	$$ = make_node(parser_ctx, NODE_EXPRESSION);
	411	$$->u.expression.type = AST_EXP_FLOAT_CONSTANT;
	412	sscanf(yylval.gs->s, "%lg",
	413	&$$->u.expression.u.float_constant);
	414	}
953192ba MD	415	\| STRING_LITERAL_START DQUOTE
	416	{
	417	$$ = make_node(parser_ctx, NODE_EXPRESSION);
	418	$$->u.expression.type = AST_EXP_STRING;
	419	$$->u.expression.u.string = "";
	420	}
	421	\| STRING_LITERAL_START s_char_sequence DQUOTE
	422	{
	423	$$ = make_node(parser_ctx, NODE_EXPRESSION);
	424	$$->u.expression.type = AST_EXP_STRING;
	425	$$->u.expression.u.string = $2->s;
	426	}
	427	\| CHARACTER_CONSTANT_START c_char_sequence SQUOTE
	428	{
	429	$$ = make_node(parser_ctx, NODE_EXPRESSION);
	430	$$->u.expression.type = AST_EXP_STRING;
	431	$$->u.expression.u.string = $2->s;
	432	}
	433	\| LPAREN expression RPAREN
	434	{
	435	$$ = make_node(parser_ctx, NODE_EXPRESSION);
	436	$$->u.expression.type = AST_EXP_NESTED;
	437	$$->u.expression.u.child = $2;
	438	}
	439	;
	440
	441	postfix_expression
	442	: primary_expression
	443	{ $$ = $1; }
	444	\| postfix_expression DOT IDENTIFIER
	445	{
	446	$$ = make_node(parser_ctx, NODE_EXPRESSION);
	447	$$->u.expression.type = AST_EXP_IDENTIFIER;
	448	$$->u.expression.post_op = AST_LINK_DOT;
	449	$$->u.expression.u.identifier = $3->s;
	450	$$->u.expression.prev = $1;
	451	}
	452	\| postfix_expression RARROW IDENTIFIER
	453	{
	454	$$ = make_node(parser_ctx, NODE_EXPRESSION);
	455	$$->u.expression.type = AST_EXP_IDENTIFIER;
	456	$$->u.expression.post_op = AST_LINK_RARROW;
	457	$$->u.expression.u.identifier = $3->s;
	458	$$->u.expression.prev = $1;
	459	}
	460	;
	461
	462	unary_expression
	463	: postfix_expression
	464	{ $$ = $1; }
	465	\| unary_operator unary_expression
	466	{
	467	$$ = $1;
	468	$$->u.unary_op.child = $2;
	469	}
	470	;
	471
	472	unary_operator
	473	: PLUS
	474	{
	475	$$ = make_node(parser_ctx, NODE_UNARY_OP);
	476	$$->u.unary_op.type = AST_UNARY_PLUS;
	477	}
	478	\| MINUS
479	{
480	$$ = make_node(parser_ctx, NODE_UNARY_OP);
481	$$->u.unary_op.type = AST_UNARY_MINUS;
482	}
483	\| NOT_OP
484	{
485	$$ = make_node(parser_ctx, NODE_UNARY_OP);
486	$$->u.unary_op.type = AST_UNARY_NOT;
487	}
ab78f161 CB	488	\| NOT_BIN
	489	{
	490	$$ = make_node(parser_ctx, NODE_UNARY_OP);
	491	$$->u.unary_op.type = AST_UNARY_BIN_NOT;
	492	}
953192ba MD	493	;
	494
	495	multiplicative_expression
	496	: unary_expression
	497	{ $$ = $1; }
	498	\| multiplicative_expression STAR unary_expression
	499	{
	500	$$ = make_op_node(parser_ctx, AST_OP_MUL, $1, $3);
	501	}
	502	\| multiplicative_expression DIV_OP unary_expression
	503	{
	504	$$ = make_op_node(parser_ctx, AST_OP_DIV, $1, $3);
	505	}
	506	\| multiplicative_expression MOD_OP unary_expression
	507	{
	508	$$ = make_op_node(parser_ctx, AST_OP_MOD, $1, $3);
	509	}
	510	;
	511
	512	additive_expression
	513	: multiplicative_expression
	514	{ $$ = $1; }
	515	\| additive_expression PLUS multiplicative_expression
	516	{
	517	$$ = make_op_node(parser_ctx, AST_OP_PLUS, $1, $3);
	518	}
	519	\| additive_expression MINUS multiplicative_expression
	520	{
	521	$$ = make_op_node(parser_ctx, AST_OP_MINUS, $1, $3);
	522	}
	523	;
	524
	525	shift_expression
	526	: additive_expression
	527	{ $$ = $1; }
	528	\| shift_expression LEFT_OP additive_expression
	529	{
	530	$$ = make_op_node(parser_ctx, AST_OP_LSHIFT, $1, $3);
	531	}
	532	\| shift_expression RIGHT_OP additive_expression
	533	{
	534	$$ = make_op_node(parser_ctx, AST_OP_RSHIFT, $1, $3);
	535	}
	536	;
	537
	538	relational_expression
	539	: shift_expression
	540	{ $$ = $1; }
	541	\| relational_expression LT_OP shift_expression
	542	{
	543	$$ = make_op_node(parser_ctx, AST_OP_LT, $1, $3);
	544	}
	545	\| relational_expression GT_OP shift_expression
	546	{
	547	$$ = make_op_node(parser_ctx, AST_OP_GT, $1, $3);
	548	}
	549	\| relational_expression LE_OP shift_expression
	550	{
	551	$$ = make_op_node(parser_ctx, AST_OP_LE, $1, $3);
	552	}
	553	\| relational_expression GE_OP shift_expression
	554	{
	555	$$ = make_op_node(parser_ctx, AST_OP_GE, $1, $3);
	556	}
557	;
558
559	equality_expression
560	: relational_expression
561	{ $$ = $1; }
562	\| equality_expression EQ_OP relational_expression
563	{
564	$$ = make_op_node(parser_ctx, AST_OP_EQ, $1, $3);
565	}
566	\| equality_expression NE_OP relational_expression
567	{
568	$$ = make_op_node(parser_ctx, AST_OP_NE, $1, $3);
569	}
570	;
571
572	and_expression
573	: equality_expression
574	{ $$ = $1; }
575	\| and_expression AND_BIN equality_expression
576	{
577	$$ = make_op_node(parser_ctx, AST_OP_BIN_AND, $1, $3);
578	}
579	;
580
581	exclusive_or_expression
582	: and_expression
583	{ $$ = $1; }
584	\| exclusive_or_expression XOR_BIN and_expression
585	{
586	$$ = make_op_node(parser_ctx, AST_OP_BIN_XOR, $1, $3);
587	}
588	;
589
590	inclusive_or_expression
591	: exclusive_or_expression
592	{ $$ = $1; }
593	\| inclusive_or_expression OR_BIN exclusive_or_expression
594	{
595	$$ = make_op_node(parser_ctx, AST_OP_BIN_OR, $1, $3);
596	}
597	;
598
599	logical_and_expression
600	: inclusive_or_expression
601	{ $$ = $1; }
602	\| logical_and_expression AND_OP inclusive_or_expression
603	{
604	$$ = make_op_node(parser_ctx, AST_OP_AND, $1, $3);
605	}
606	;
607
608	logical_or_expression
609	: logical_and_expression
610	{ $$ = $1; }
611	\| logical_or_expression OR_OP logical_and_expression
612	{
613	$$ = make_op_node(parser_ctx, AST_OP_OR, $1, $3);
614	}
615	;
616
617	expression
618	: logical_or_expression
619	{ $$ = $1; }
620	;
621
622	translation_unit
623	: expression
624	{
625	parser_ctx->ast->root.u.root.child = $1;
626	}
627	;