glcpp-parse.y

%{
/*
 * Copyright © 2010 Intel Corporation
 *
 * Permission is hereby granted, free of charge, to any person obtaining a
 * copy of this software and associated documentation files (the "Software"),
 * to deal in the Software without restriction, including without limitation
 * the rights to use, copy, modify, merge, publish, distribute, sublicense,
 * and/or sell copies of the Software, and to permit persons to whom the
 * Software is furnished to do so, subject to the following conditions:
 *
 * The above copyright notice and this permission notice (including the next
 * paragraph) shall be included in all copies or substantial portions of the
 * Software.
 *
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL
 * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
 * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
 * DEALINGS IN THE SOFTWARE.
 */

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <talloc.h>

#include "glcpp.h"

#define YYLEX_PARAM parser->scanner

typedef struct {
	int is_function;
	string_list_t *parameters;
	string_list_t *replacements;
} macro_t;

struct glcpp_parser {
	yyscan_t scanner;
	struct hash_table *defines;
};

void
yyerror (void *scanner, const char *error);

void
_define_object_macro (glcpp_parser_t *parser,
		      const char *macro,
		      string_list_t *replacements);

void
_define_function_macro (glcpp_parser_t *parser,
			const char *macro,
			string_list_t *parameters,
			string_list_t *replacements);

string_list_t *
_expand_object_macro (glcpp_parser_t *parser, const char *identifier);

string_list_t *
_expand_function_macro (glcpp_parser_t *parser,
			const char *identifier,
			argument_list_t *arguments);

void
_print_string_list (string_list_t *list);

string_list_t *
_string_list_create (void *ctx);

void
_string_list_append_item (string_list_t *list, const char *str);

void
_string_list_append_list (string_list_t *list, string_list_t *tail);

void
_string_list_push (string_list_t *list, const char *str);

void
_string_list_pop (string_list_t *list);

int
_string_list_contains (string_list_t *list, const char *member, int *index);

int
_string_list_length (string_list_t *list);

argument_list_t *
_argument_list_create (void *ctx);

void
_argument_list_append (argument_list_t *list, string_list_t *argument);

int
_argument_list_length (argument_list_t *list);

string_list_t *
_argument_list_member_at (argument_list_t *list, int index);

%}

%union {
	char *str;
	string_list_t *string_list;
	argument_list_t *argument_list;
}

%parse-param {glcpp_parser_t *parser}
%lex-param {void *scanner}

%token DEFINE FUNC_MACRO IDENTIFIER NEWLINE OBJ_MACRO SPACE TOKEN UNDEF
%type <str> FUNC_MACRO IDENTIFIER identifier_perhaps_macro OBJ_MACRO replacement_word TOKEN word
%type <string_list> argument macro parameter_list replacement_list
%type <argument_list> argument_list

/* Hard to remove shift/reduce conflicts documented as follows:
 *
 * 1. '(' after FUNC_MACRO name which is correctly resolved to shift
 *    to form macro invocation rather than reducing directly to
 *    content.
 */
%expect 1

%%

input:
	/* empty */
|	input content
;

	/* We do all printing at the content level */
content:
	IDENTIFIER {
		printf ("%s", $1);
		talloc_free ($1);
	}
|	TOKEN {
		printf ("%s", $1);
		talloc_free ($1);
	}
|	FUNC_MACRO {
		printf ("%s", $1);
		talloc_free ($1);
	}
|	macro {
		_print_string_list ($1);
	}
|	directive_with_newline { printf ("\n"); }
|	'('	{ printf ("("); }
|	')'	{ printf (")"); }
|	','	{ printf (","); }
;

macro:
	FUNC_MACRO '(' argument_list ')' {
		$$ = _expand_function_macro (parser, $1, $3);
	}
|	OBJ_MACRO {
		$$ = _expand_object_macro (parser, $1);
		talloc_free ($1);
	}
;

argument_list:
	/* empty */ {
		$$ = _argument_list_create (parser);
	}
|	argument {
		$$ = _argument_list_create (parser);
		_argument_list_append ($$, $1);
	}
|	argument_list ',' argument {
		_argument_list_append ($1, $3);
		$$ = $1;
	}
;

argument:
	word {
		$$ = _string_list_create (parser);
		_string_list_append_item ($$, $1);
	}
|	macro {
		$$ = $1;
	}
|	argument word {
		_string_list_append_item ($1, $2);
		talloc_free ($2);
		$$ = $1;
	}
|	argument '(' argument ')' {
		_string_list_append_item ($1, "(");
		_string_list_append_list ($1, $3);
		_string_list_append_item ($1, ")");
		$$ = $1;
	}
;

directive_with_newline:
	directive NEWLINE
;

directive:
	DEFINE IDENTIFIER {
		string_list_t *list = _string_list_create (parser);
		_define_object_macro (parser, $2, list);
	}
|	DEFINE IDENTIFIER SPACE replacement_list {
		_define_object_macro (parser, $2, $4);
	}
|	DEFINE IDENTIFIER '(' parameter_list ')' {
		string_list_t *list = _string_list_create (parser);
		_define_function_macro (parser, $2, $4, list);
	}
|	DEFINE IDENTIFIER '(' parameter_list ')' replacement_list {
		_define_function_macro (parser, $2, $4, $6);
	}
|	UNDEF FUNC_MACRO {
		string_list_t *replacement = hash_table_find (parser->defines, $2);
		if (replacement) {
			/* XXX: Need hash table to support a real way
			 * to remove an element rather than prefixing
			 * a new node with data of NULL like this. */
			hash_table_insert (parser->defines, NULL, $2);
			talloc_free (replacement);
		}
		talloc_free ($2);
	}
|	UNDEF OBJ_MACRO {
		string_list_t *replacement = hash_table_find (parser->defines, $2);
		if (replacement) {
			/* XXX: Need hash table to support a real way
			 * to remove an element rather than prefixing
			 * a new node with data of NULL like this. */
			hash_table_insert (parser->defines, NULL, $2);
			talloc_free (replacement);
		}
		talloc_free ($2);
	}
;

replacement_list:
	replacement_word {
		$$ = _string_list_create (parser);
		_string_list_append_item ($$, $1);
		talloc_free ($1);
	}
|	replacement_list replacement_word {
		_string_list_append_item ($1, $2);
		talloc_free ($2);
		$$ = $1;
	}
;

replacement_word:
	word		{ $$ = $1; }
|	FUNC_MACRO	{ $$ = $1; }
|	OBJ_MACRO	{ $$ = $1; }
|	'('		{ $$ = xtalloc_strdup (parser, "("); }
|	')'		{ $$ = xtalloc_strdup (parser, ")"); }
|	','		{ $$ = xtalloc_strdup (parser, ","); }
;

parameter_list:
	/* empty */ {
		$$ = _string_list_create (parser);
	}
|	identifier_perhaps_macro {
		$$ = _string_list_create (parser);
		_string_list_append_item ($$, $1);
		talloc_free ($1);
	}
|	parameter_list ',' identifier_perhaps_macro {
		_string_list_append_item ($1, $3);
		talloc_free ($3);
		$$ = $1;
	}
;

identifier_perhaps_macro:
	IDENTIFIER { $$ = $1; }
|	FUNC_MACRO { $$ = $1; }
|	OBJ_MACRO { $$ = $1; }
;

word:
	IDENTIFIER { $$ = $1; }
|	TOKEN { $$ = $1; }
;

%%

string_list_t *
_string_list_create (void *ctx)
{
	string_list_t *list;

	list = xtalloc (ctx, string_list_t);
	list->head = NULL;
	list->tail = NULL;

	return list;
}

void
_string_list_append_list (string_list_t *list, string_list_t *tail)
{
	if (list->head == NULL) {
		list->head = tail->head;
	} else {
		list->tail->next = tail->head;
	}

	list->tail = tail->tail;
}

void
_string_list_append_item (string_list_t *list, const char *str)
{
	string_node_t *node;

	node = xtalloc (list, string_node_t);
	node->str = xtalloc_strdup (node, str);
		
	node->next = NULL;

	if (list->head == NULL) {
		list->head = node;
	} else {
		list->tail->next = node;
	}

	list->tail = node;
}

void
_string_list_push (string_list_t *list, const char *str)
{
	string_node_t *node;

	node = xtalloc (list, string_node_t);
	node->str = xtalloc_strdup (node, str);

	node->next = list->head;

	if (list->tail == NULL) {
		list->tail = node;
	}

	list->head = node;
}

void
_string_list_pop (string_list_t *list)
{
	string_node_t *node;

	node = list->head;

	if (node == NULL) {
		fprintf (stderr, "Internal error: _string_list_pop called on an empty list.\n");
		exit (1);
	}

	list->head = node->next;

	if (list->tail == node) {
		assert (node->next == NULL);
		list->tail = NULL;
	}

	talloc_free (node);
}

int
_string_list_contains (string_list_t *list, const char *member, int *index)
{
	string_node_t *node;
	int i;

	if (list == NULL)
		return 0;

	for (i = 0, node = list->head; node; i++, node = node->next) {
		if (strcmp (node->str, member) == 0) {
			if (index)
				*index = i;
			return 1;
		}
	}

	return 0;
}

int
_string_list_length (string_list_t *list)
{
	int length = 0;
	string_node_t *node;

	if (list == NULL)
		return 0;

	for (node = list->head; node; node = node->next)
		length++;

	return length;
}

void
_print_string_list (string_list_t *list)
{
	string_node_t *node;

	if (list == NULL)
		return;

	for (node = list->head; node; node = node->next) {
		printf ("%s", node->str);
		if (node->next)
			printf (" ");
	}
}

argument_list_t *
_argument_list_create (void *ctx)
{
	argument_list_t *list;

	list = xtalloc (ctx, argument_list_t);
	list->head = NULL;
	list->tail = NULL;

	return list;
}

void
_argument_list_append (argument_list_t *list, string_list_t *argument)
{
	argument_node_t *node;

	if (argument == NULL || argument->head == NULL)
		return;

	node = xtalloc (list, argument_node_t);
	node->argument = argument;

	node->next = NULL;

	if (list->head == NULL) {
		list->head = node;
	} else {
		list->tail->next = node;
	}

	list->tail = node;
}

int
_argument_list_length (argument_list_t *list)
{
	int length = 0;
	argument_node_t *node;

	if (list == NULL)
		return 0;

	for (node = list->head; node; node = node->next)
		length++;

	return length;
}

string_list_t *
_argument_list_member_at (argument_list_t *list, int index)
{
	argument_node_t *node;
	int i;

	if (list == NULL)
		return NULL;

	node = list->head;
	for (i = 0; i < index; i++) {
		node = node->next;
		if (node == NULL)
			break;
	}

	if (node)
		return node->argument;

	return NULL;
}
		
void
yyerror (void *scanner, const char *error)
{
	fprintf (stderr, "Parse error: %s\n", error);
}

glcpp_parser_t *
glcpp_parser_create (void)
{
	glcpp_parser_t *parser;

	parser = xtalloc (NULL, glcpp_parser_t);

	yylex_init_extra (parser, &parser->scanner);
	parser->defines = hash_table_ctor (32, hash_table_string_hash,
					   hash_table_string_compare);

	return parser;
}

int
glcpp_parser_parse (glcpp_parser_t *parser)
{
	return yyparse (parser);
}

void
glcpp_parser_destroy (glcpp_parser_t *parser)
{
	yylex_destroy (parser->scanner);
	hash_table_dtor (parser->defines);
	talloc_free (parser);
}

macro_type_t
glcpp_parser_macro_type (glcpp_parser_t *parser, const char *identifier)
{
	macro_t *macro;

	macro = hash_table_find (parser->defines, identifier);

	if (macro == NULL)
		return MACRO_TYPE_UNDEFINED;

	if (macro->is_function)
		return MACRO_TYPE_FUNCTION;
	else
		return MACRO_TYPE_OBJECT;
}

void
_define_object_macro (glcpp_parser_t *parser,
		      const char *identifier,
		      string_list_t *replacements)
{
	macro_t *macro;

	macro = xtalloc (parser, macro_t);

	macro->is_function = 0;
	macro->parameters = NULL;
	macro->replacements = talloc_steal (macro, replacements);

	hash_table_insert (parser->defines, macro, identifier);
}

void
_define_function_macro (glcpp_parser_t *parser,
			const char *identifier,
			string_list_t *parameters,
			string_list_t *replacements)
{
	macro_t *macro;

	macro = xtalloc (parser, macro_t);

	macro->is_function = 1;
	macro->parameters = talloc_steal (macro, parameters);
	macro->replacements = talloc_steal (macro, replacements);

	hash_table_insert (parser->defines, macro, identifier);
}

static string_list_t *
_expand_macro_recursive (glcpp_parser_t *parser,
			 const char *token,
			 string_list_t *active,
			 string_list_t *parameters,
			 argument_list_t *arguments);

static string_list_t *
_expand_string_list_recursive (glcpp_parser_t *parser,
			       string_list_t *list,
			       string_list_t *active,
			       string_list_t *parameters,
			       argument_list_t *arguments)
{
	string_list_t *result;
	string_list_t *child;
	const char *token;
	string_node_t *node;
	int index;

	result = _string_list_create (parser);

	for (node = list->head ; node ; node = node->next) {
		token = node->str;

		/* Don't expand this macro if it's on the active
		 * stack, (meaning we're already in the process of
		 * expanding it). */
		if (_string_list_contains (active, token, NULL)) {
			_string_list_append_item (result, token);
			continue;
		}

		if (_string_list_contains (parameters, token, &index)) {
			string_list_t *argument;

			argument = _argument_list_member_at (arguments, index);
			child = _expand_string_list_recursive (parser, argument,
							       active, NULL, NULL);
			_string_list_append_list (result, child);
		} else {
			child = _expand_macro_recursive (parser, token,
							 active, parameters,
							 arguments);
			_string_list_append_list (result, child);
		}
	}

	return result;
}


static string_list_t *
_expand_macro_recursive (glcpp_parser_t *parser,
			 const char *token,
			 string_list_t *active,
			 string_list_t *parameters,
			 argument_list_t *arguments)
{
	macro_t *macro;
	string_list_t *replacements;
	string_list_t *result;

	if (active == NULL)
		active = _string_list_create (NULL);

	_string_list_push (active, token);

	macro = hash_table_find (parser->defines, token);
	if (macro == NULL) {
		string_list_t *result;

		result = _string_list_create (parser);
		_string_list_append_item (result, token);
		return result;
	}

	replacements = macro->replacements;

	result = _expand_string_list_recursive (parser, replacements,
						active, parameters, arguments);

	_string_list_pop (active);
	if (_string_list_length (active) == 0)
		talloc_free (active);

	return result;
}

string_list_t *
_expand_object_macro (glcpp_parser_t *parser, const char *identifier)
{
	macro_t *macro;

	macro = hash_table_find (parser->defines, identifier);
	assert (! macro->is_function);

	return _expand_macro_recursive (parser, identifier, NULL,
					NULL, NULL);
}

string_list_t *
_expand_function_macro (glcpp_parser_t *parser,
			const char *identifier,
			argument_list_t *arguments)
{
	macro_t *macro;

	macro = hash_table_find (parser->defines, identifier);
	assert (macro->is_function);

	if (_argument_list_length (arguments) !=
	    _string_list_length (macro->parameters))
	{
		fprintf (stderr,
			 "Error: macro %s invoked with %d arguments (expected %d)\n",
			 identifier,
			 _argument_list_length (arguments),
			 _string_list_length (macro->parameters));
		return NULL;
	}

	return _expand_macro_recursive (parser, identifier, NULL,
					macro->parameters, arguments);
}