[lttng-tools.git] / src / lib / lttng-ctl / 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-parser.h"
#include "filter-ast.h"

int yydebug;
int filter_parser_debug = 0;

int yyparse(struct filter_parser_ctx *parser_ctx);
int yylex(union YYSTYPE *yyval, struct filter_parser_ctx *parser_ctx);
int yylex_init_extra(struct filter_parser_ctx *parser_ctx, yyscan_t * ptr_yy_globals);
int yylex_destroy(yyscan_t yyparser_ctx);
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",
};

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.
 */
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;
}

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;
}

void yyerror(struct filter_parser_ctx *parser_ctx, const char *str)
{
	fprintf(stderr, "error %s\n", str);
}
 
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);
}

int filter_parser_ctx_append_ast(struct filter_parser_ctx *parser_ctx)
{
	return yyparse(parser_ctx);
}

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;
}

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;
		}
	;

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