/* Oort
 * Copyright 2007, 2008, Soren Sandmann Pedersen
 *
 * This program is free software; you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation; either version 2 of the License, or
 * (at your option) any later version.
 *
 * This program 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 General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program; if not, write to the Free Software
 * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
 */
#include "ast.h"

static void
node_unlink (node_t *node)
{
    if (node->common.prev)
	node->common.prev->common.next = node->common.next;
    if (node->common.next)
	node->common.next->common.prev = node->common.prev;
    node->common.prev = NULL;
    node->common.next = NULL;
}

node_t *
node_insert_after (node_t *node,
		   node_t *pred)
{
    node_unlink (node);

    node->common.next = pred->common.next;
    if (pred->common.next)
	pred->common.next->common.prev = node;

    pred->common.next = node;
    node->common.prev = pred;

    return node;
}

static node_t *
node_new (node_type_t  type,
	  node_t      *node,
	  ast_t       *ast)
{
    node_t *new = g_new0 (node_t, 1);

    new->common.type = type;
    new->common.ast = ast;
    new->common.next = NULL;
    new->common.prev = NULL;

    if (node)
	node_insert_after (new, node);

    return new;
}

void
node_free (node_t *node)
{
    g_free (node);
}

node_t *
node_new_fun_ref (node_t *prolog,
		  node_t *pred,
		  ast_t  *ast)
{
    node_t *fun_ref = node_new (NODE_FUN_REF, pred, ast);

    g_assert (prolog->common.type == NODE_PROLOG);

    fun_ref->fun_ref.prolog = &prolog->prolog;

    g_queue_push_tail (prolog->prolog.sources, fun_ref);

    return fun_ref;
}

node_t *
node_new_prolog (node_t *pred,
		 ast_t  *ast)
{
    node_t *prolog = node_new (NODE_PROLOG, pred, ast);

    prolog->prolog.sources = g_queue_new ();

    return prolog;
}

node_t *
node_new_label (node_t *pred,
		ast_t  *ast)
{
    node_t *label = node_new (NODE_LABEL, pred, ast);

    label->label.sources = g_queue_new ();

    return label;
};

node_t *
node_new_goto (label_node_t *label,
	       node_t       *pred,
	       ast_t        *ast)
{
    node_t *node = node_new (NODE_GOTO, pred, ast);

    node->goto_.label = label;
    g_queue_push_tail (label->sources, node);

    return node;
}


node_t *
node_new_dyn_goto (node_t *pred,
		   ast_t  *ast)
{
    node_t *node = node_new (NODE_DYN_GOTO, pred, ast);

    return node;
}

node_t *
node_new_return (ast_type_spec_t *type,
		 node_t          *pred,
		 ast_t           *ast)
{
    node_t *node = node_new (NODE_RETURN, pred, ast);

    node->return_.type = type;

    return node;
}

node_t *
node_new_if (gboolean	   sense,
	     label_node_t *taken,
	     node_t       *pred,
	     ast_t *ast)
{
    node_t *node = node_new (NODE_IF, pred, ast);
    node->if_.sense = sense;
    node->if_.taken = taken;
    g_queue_push_tail (taken->sources, node);
    return node;
}

node_t *
node_new_literal (value_t value,
		  ast_type_spec_t *type,
		  node_t *pred,
		  ast_t *ast)
{
    node_t *node = node_new (NODE_LITERAL, pred, ast);

    node->literal.value = value;
    node->literal.type_spec = type;

    return node;
}

node_t *
node_new_closure (ast_function_definition_t *function,
		  ast_expression_t          *expr,
		  node_t                    *pred,
		  ast_t                     *ast)
{
    node_t *node = node_new (NODE_CLOSURE, pred, ast);

    g_assert (ast->type == AST_EXPRESSION);

    node->closure.function = function;
    node->closure.expression = expr;

    return node;
}

node_t *
node_new_dyn_label (label_node_t           *label,
		    ast_expression_t       *expr,
		    ast_label_definition_t *definition,
		    node_t                 *pred,
		    ast_t                  *ast)
{
    node_t *node = node_new (NODE_DYN_LABEL, pred, ast);

    node->dyn_label.label = label;
    node->dyn_label.expression = expr;
    node->dyn_label.definition = definition;

    g_queue_push_tail (label->sources, node);

    return node;
}

node_t *
node_new_dyn_closure (ast_function_definition_t *function,
		      node_t                    *pred,
		      ast_t                     *ast)
{
    node_t *node = node_new (NODE_DYN_CLOSURE, pred, ast);

    g_assert (ast->type == AST_EXPRESSION);

    node->dyn_closure.function = function;

    return node;
}

node_t *
node_new_print (int		 n_exprs,
		node_t          *pred,
		ast_t           *ast)
{
    node_t *node = node_new (NODE_PRINT, pred, ast);

    node->print.n_exprs = n_exprs;
    
    return node;
}

node_t *
node_new_to_string   (ast_type_spec_t		*type_spec,
		      node_t			*pred,
		      ast_t			*ast)
{
    node_t *node = node_new (NODE_TO_STRING, pred, ast);

    node->to_string.type_spec = type_spec;

    return node;
}

node_t *
node_new_call (node_t *pred,
	       ast_t  *ast)
{
    return node_new (NODE_CALL, pred, ast);
}

node_t *
node_new_pop (node_t *pred,
	      ast_t  *ast)
{
    return node_new (NODE_POP, pred, ast);
}

node_t *
node_new_dup (node_t *pred,
	      ast_t  *ast)
{
    return node_new (NODE_DUP, pred, ast);
}

node_t *
node_new_nop (node_t *pred,
	      ast_t  *ast)
{
    return node_new (NODE_NOP, pred, ast);
}

node_t *
node_new_load (ast_variable_definition_t *def,
	       ast_expression_t          *expr,
	       node_t                    *pred,
	       ast_t                     *ast)
{
    node_t *node = node_new (NODE_LOAD, pred, ast);

    node->load.definition = def;
    node->load.expression = expr;

    return node;
}

node_t *
node_new_load_ind (ast_variable_definition_t *def,
		   node_t                    *pred,
		   ast_t                     *ast)
{
    node_t *node = node_new (NODE_LOAD_IND, pred, ast);

    node->load_ind.definition = def;

    return node;
}

node_t *
node_new_load_array (ast_array_type_spec_t *array,
		     node_t *pred,
		     ast_t  *ast)
{
    node_t *node = node_new (NODE_LOAD_ARRAY, pred, ast);

    node->load_array.array = array;

    return node;
}

node_t *
node_new_store (ast_variable_definition_t *def,
		ast_expression_t          *expr,
		node_t                    *pred,
		ast_t                     *ast)
{
    node_t *node = node_new (NODE_STORE, pred, ast);

    node->store.definition = def;
    node->store.expression = expr;

    return node;
}

node_t *
node_new_store_ind (ast_variable_definition_t *def,
		    node_t                    *pred,
		    ast_t                     *ast)
{
    node_t *node = node_new (NODE_STORE_IND, pred, ast);

    node->store_ind.definition = def;

    return node;
}

node_t *
node_new_store_array (ast_array_type_spec_t *array,
		      node_t                *pred,
		      ast_t                 *ast)
{
    node_t *node = node_new (NODE_STORE_ARRAY, pred, ast);

    node->store_array.array = array;

    return node;
}

node_t *
node_new_initialize (ast_variable_definition_t *def,
		     node_t                    *pred,
		     ast_t                     *ast)
{
    node_t *node = node_new (NODE_INIT, pred, ast);

    node->initialize.definition = def;

    return node;
}

node_t *
node_new_binop (ast_binary_operator_t  operator,
		ast_type_spec_t       *left_type,
		ast_type_spec_t       *right_type,
		ast_type_spec_t       *type,
		node_t                *pred,
		ast_t                 *ast)
{
    node_t *node = node_new (NODE_BINOP, pred, ast);

    g_assert (operator != AST_AND && operator != AST_OR);

    node->binop.operator = operator;
    node->binop.left_type = left_type;
    node->binop.right_type = right_type;
    node->binop.type_spec = type;

    return node;
}

node_t *
node_new_unary (ast_unary_operator_t  operator,
		ast_type_spec_t      *child_type,
		ast_type_spec_t      *type,
		node_t               *pred,
		ast_t                *ast)
{
    node_t *node = node_new (NODE_UNARY, pred, ast);

    /* These were converted to load/store/binop in graph.c */
    g_assert (operator != AST_POSTFIX_INC &&
	      operator != AST_POSTFIX_DEC &&
	      operator != AST_PREFIX_INC  &&
	      operator != AST_PREFIX_DEC);

    node->unary.operator = operator;
    node->unary.child_type = child_type;
    node->unary.type_spec = type;

    return node;
}

node_t *
node_new_new (ast_class_definition_t *class,
	      ast_expression_t       *expr,
	      node_t                 *pred,
	      ast_t                  *ast)
{
    node_t *node = node_new (NODE_NEW, pred, ast);

    node->new.expression = expr;
    node->new.class = class;

    return node;
}

node_t *
node_new_new_array (ast_array_type_spec_t	*array,
		    int				 element_size,
		    node_t			*pred,
		    ast_t			*ast)
{
    node_t *node = node_new (NODE_NEW_ARRAY, pred, ast);

    node->new_array.array = array;
    node->new_array.element_size = element_size;

    return node;
}

node_t *
node_new_this (ast_class_definition_t *class,
	       ast_expression_t       *expr,
	       node_t                 *pred,
	       ast_t                  *ast)
{
    node_t *node = node_new (NODE_THIS, pred, ast);

    node->this.expression = expr;
    node->this.class = class;

    return node;
}

GList *
node_list_predecessors (node_t *node)
{
    GList *result = NULL;
    GQueue *sources = NULL;

    if (node->common.type == NODE_LABEL)
	sources = node->label.sources;
    else if (node->common.type == NODE_PROLOG)
	sources = node->prolog.sources;
    else
	sources = NULL;

    if (sources)
    {
	GList *list;

	for (list = sources->head; list; list = list->next)
	{
	    node_t *source = list->data;

	    result = g_list_prepend (result, source);
	}
    }

    if (node->common.prev && node->common.prev->common.type != NODE_GOTO)
	result = g_list_prepend (result, node->common.prev);

    return result;
}

GList *
node_list_successors (node_t *node)
{
    GList *result = NULL;

    if (node->common.type == NODE_GOTO)
	result = g_list_prepend (result, node->goto_.label);

    if (node->common.type == NODE_IF)
	result = g_list_prepend (result, node->if_.taken);

    if (node->common.type == NODE_FUN_REF)
	result = g_list_prepend (result, node->fun_ref.prolog);

    if (node->common.type == NODE_DYN_LABEL)
	result = g_list_prepend (result, node->dyn_label.label);

    if (node->common.next			&&
	node->common.type != NODE_GOTO		&&
	node->common.type != NODE_DYN_GOTO	&&
	node->common.type != NODE_RETURN)
    {
	result = g_list_prepend (result, node->common.next);
    }

    return result;
}

void
node_breadth_first (node_t	     *start,
		    node_callback_t   callback,
		    gpointer	      data)
{
    GHashTable *queued;
    GQueue *work_list;

    if (!start)
	return;

    queued = g_hash_table_new (NULL, NULL);
    work_list = g_queue_new ();

    g_queue_push_tail (work_list, start);

    while (!g_queue_is_empty (work_list))
    {
	node_t *node = g_queue_pop_head (work_list);
	GList *list;

	callback (node, data);

	for (list = node_list_successors (node); list; list = list->next)
	{
	    node_t *successor = list->data;

	    if (!g_hash_table_lookup (queued, successor))
	    {
		g_hash_table_insert (queued, successor, successor);
		g_queue_push_tail (work_list, successor);
	    }
	}
    }

    g_queue_free (work_list);
    g_hash_table_destroy (queued);
}

static void
add_node (node_t *node, gpointer data)
{
    GPtrArray *nodes = data;

    g_ptr_array_add (nodes, node);
}

node_t **
node_list_all (node_t *start)
{
    GPtrArray *nodes = g_ptr_array_new ();

    node_breadth_first (start, add_node, nodes);

    g_ptr_array_add (nodes, NULL);

    return (node_t **)g_ptr_array_free (nodes, FALSE);
}