[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"

#include <common/macros.h>

#define WIDTH_u64_SCANF_IS_A_BROKEN_API	"20"
#define WIDTH_o64_SCANF_IS_A_BROKEN_API	"22"
#define WIDTH_x64_SCANF_IS_A_BROKEN_API	"17"
#define WIDTH_lg_SCANF_IS_A_BROKEN_API	"4096"	/* Hugely optimistic approximation */

LTTNG_HIDDEN
int yydebug;
LTTNG_HIDDEN
int filter_parser_debug = 0;

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

LTTNG_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 = zmalloc(alloclen);
	if (!gstr) {
		goto end;
	}
	cds_list_add(&gstr->gc, &parser_ctx->allocated_strings);
	gstr->alloclen = alloclen;
end:
	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.
 */
LTTNG_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;
}

LTTNG_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 = zmalloc(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 = zmalloc(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;
}

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

#define parse_error(parser_ctx, str)				\
do {								\
	yyerror(parser_ctx, parser_ctx->scanner, 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 = zmalloc(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);
	free(ast);
}

LTTNG_HIDDEN
int filter_parser_ctx_append_ast(struct filter_parser_ctx *parser_ctx)
{
	return yyparse(parser_ctx, parser_ctx->scanner);
}

LTTNG_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 = zmalloc(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;
}

LTTNG_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}
%parse-param {yyscan_t scanner}
%lex-param {yyscan_t scanner}
%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 GLOBAL_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;
		}
	|	GLOBAL_IDENTIFIER
		{
			$$ = make_node(parser_ctx, NODE_EXPRESSION);
			$$->u.expression.type = AST_EXP_GLOBAL_IDENTIFIER;
			$$->u.expression.u.identifier = yylval.gs->s;
		}

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