/*
 * Copyright (c) 2010 Jiri Svoboda
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 *
 * - Redistributions of source code must retain the above copyright
 *   notice, this list of conditions and the following disclaimer.
 * - Redistributions in binary form must reproduce the above copyright
 *   notice, this list of conditions and the following disclaimer in the
 *   documentation and/or other materials provided with the distribution.
 * - The name of the author may not be used to endorse or promote products
 *   derived from this software without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 */

/** @file Ancestry resolver.
 *
 * A chicken-and-egg problem is that in order to match identifiers to CSI
 * definitions we need to know CSI ancestry. To know CSI ancestry we need
 * to match identifiers to CSI definitions. Thus both must be done at the
 * same time. Once we know the ancestry of some CSI, we are able to resolve
 * symbols referenced within the scope of that CSI (but not in nested scopes).
 *
 * Here lies probably the most complicated (although not so complicated)
 * algorithm. To process node N we must first process outer(N). This allows
 * us to find all base(N) nodes and process them.
 *
 * To ensure all nodes get processed correctly, we use a two-layer walk.
 * In the lower layer (ancr_csi_process) we follow the dependencies.
 * ancr_csi_process(N) ensures N (and possibly other nodes) get resolved.
 *
 * In the second layer we simply do a DFS of the CSI tree, calling
 * ancr_csi_process() on each node. This ensures that eventually all
 * nodes get processed.
 */

#include <stdlib.h>
#include <assert.h>
#include "builtin.h"
#include "cspan.h"
#include "list.h"
#include "mytypes.h"
#include "stree.h"
#include "strtab.h"
#include "symbol.h"

#include "ancr.h"

static void ancr_csi_dfs(stree_program_t *prog, stree_csi_t *csi);
static void ancr_csi_process(stree_program_t *prog, stree_csi_t *node);
static stree_csi_t *ancr_csi_get_pred(stree_program_t *prog, stree_csi_t *csi,
    stree_texpr_t *pred_ref);
static void ancr_csi_print_cycle(stree_program_t *prog, stree_csi_t *node);

/** Process ancestry of all CSIs in a module.
 *
 * Note that currently we expect there to be exactly one module in the
 * whole program.
 *
 * @param prog		Program being processed.
 * @param module	Module to process.
 */
void ancr_module_process(stree_program_t *prog, stree_module_t *module)
{
	list_node_t *node;
	stree_modm_t *modm;

	(void) module;
	node = list_first(&prog->module->members);

	while (node != NULL) {
		modm = list_node_data(node, stree_modm_t *);

		switch (modm->mc) {
		case mc_csi:
			ancr_csi_dfs(prog, modm->u.csi);
			break;
		case mc_enum:
			break;
		}

		node = list_next(&prog->module->members, node);
	}
}

/** Walk CSI node tree depth-first.
 *
 * This is the outer depth-first walk whose purpose is to eventually
 * process all CSI nodes by calling ancr_csi_process() on them.
 * (Which causes that and possibly some other nodes to be processed).
 *
 * @param prog		Program being processed.
 * @param csi		CSI node to visit.
 */
static void ancr_csi_dfs(stree_program_t *prog, stree_csi_t *csi)
{
	list_node_t *node;
	stree_csimbr_t *csimbr;

	/* Process this node first. */
	ancr_csi_process(prog, csi);

	/* Now visit all children. */
	node = list_first(&csi->members);
	while (node != NULL) {
		csimbr = list_node_data(node, stree_csimbr_t *);
		if (csimbr->cc == csimbr_csi)
			ancr_csi_dfs(prog, csimbr->u.csi);

		node = list_next(&csi->members, node);
	}
}

/** Process csi node.
 *
 * Fist processes the pre-required nodes (outer CSI and base CSIs),
 * then processes @a node. This is the core 'outward-and-baseward' walk.
 *
 * @param prog		Program being processed.
 * @param csi		CSI node to process.
 */
static void ancr_csi_process(stree_program_t *prog, stree_csi_t *csi)
{
	stree_csi_t *base_csi, *outer_csi;
	stree_csi_t *gf_class;

	list_node_t *pred_n;
	stree_texpr_t *pred;
	stree_csi_t *pred_csi;

	if (csi->ancr_state == ws_visited) {
		/* Node already processed */
		return;
	}

	if (csi->ancr_state == ws_active) {
		/* Error, closed reference loop. */
		printf("Error: Circular class, struct or interface chain: ");
		ancr_csi_print_cycle(prog, csi);
		printf(".\n");
		exit(1);
	}

	csi->ancr_state = ws_active;

	outer_csi = csi_to_symbol(csi)->outer_csi;
	gf_class = builtin_get_gf_class(prog->builtin);

	if (csi != gf_class) {
		/* Implicit inheritance from grandfather class. */
		base_csi = gf_class;
	} else {
		/* Grandfather class has no base class. */
		base_csi = NULL;
	}

	/* Process outer CSI */
	if (outer_csi != NULL)
		ancr_csi_process(prog, outer_csi);

	/*
	 * Process inheritance list.
	 */
	pred_n = list_first(&csi->inherit);

	/* For a class node, the first entry can be a class. */
	if (csi->cc == csi_class && pred_n != NULL) {
		pred = list_node_data(pred_n, stree_texpr_t *);
		pred_csi = ancr_csi_get_pred(prog, csi, pred);
		assert(pred_csi != NULL);

		if (pred_csi->cc == csi_class) {
			/* Process base class */
			base_csi = pred_csi;
			ancr_csi_process(prog, pred_csi);

			pred_n = list_next(&csi->inherit, pred_n);
		}
	}

	/* Following entires can only be interfaces. */
	while (pred_n != NULL) {
		pred = list_node_data(pred_n, stree_texpr_t *);
		pred_csi = ancr_csi_get_pred(prog, csi, pred);
		assert(pred_csi != NULL);

		/* Process implemented or accumulated interface. */
		ancr_csi_process(prog, pred_csi);

		switch (pred_csi->cc) {
		case csi_class:
			switch (csi->cc) {
			case csi_class:
				cspan_print(csi->name->cspan);
				printf(" Error: Only the first predecessor "
				    "can be a class. ('");
				symbol_print_fqn(csi_to_symbol(csi));
				printf("' deriving from '");
				symbol_print_fqn(csi_to_symbol(pred_csi));
				printf("').\n");
				exit(1);
				break;
			case csi_struct:
				assert(b_false); /* XXX */
				break;
			case csi_interface:
				cspan_print(csi->name->cspan);
				printf(" Error: Interface predecessor must be "
				    "an interface ('");
				symbol_print_fqn(csi_to_symbol(csi));
				printf("' deriving from '");
				symbol_print_fqn(csi_to_symbol(pred_csi));
				printf("').\n");
				exit(1);
				break;
			}
			break;
		case csi_struct:
			assert(b_false); /* XXX */
			break;
		case csi_interface:
			break;
		}

		pred_n = list_next(&csi->inherit, pred_n);
	}

	/* Store base CSI and update node state. */
	csi->ancr_state = ws_visited;
	csi->base_csi = base_csi;
}

/** Resolve CSI predecessor reference.
 *
 * Returns the CSI predecessor referenced by @a pred_ref.
 * If the referenced CSI does not exist, an error is generated.
 *
 * @param prog		Program being processed.
 * @param csi		CSI node to process.
 * @param pred_ref	Type expression referencing the predecessor.
 * @return		Predecessor CSI.
 */
static stree_csi_t *ancr_csi_get_pred(stree_program_t *prog, stree_csi_t *csi,
    stree_texpr_t *pred_ref)
{
	stree_csi_t *outer_csi;
	stree_symbol_t *pred_sym;
	stree_csi_t *pred_csi;

	outer_csi = csi_to_symbol(csi)->outer_csi;
	pred_sym = symbol_xlookup_in_csi(prog, outer_csi, pred_ref);
	pred_csi = symbol_to_csi(pred_sym);
	assert(pred_csi != NULL); /* XXX */

	return pred_csi;
}

/** Print loop in CSI ancestry.
 *
 * We have detected a loop in CSI ancestry. Traverse it (by following the
 * nodes in ws_active state and print it.
 *
 * @param prog		Program.
 * @param node		CSI node participating in an ancestry cycle.
 */
static void ancr_csi_print_cycle(stree_program_t *prog, stree_csi_t *node)
{
	stree_csi_t *n;
	stree_symbol_t *pred_sym, *node_sym;
	stree_csi_t *pred_csi, *outer_csi;
	stree_texpr_t *pred;
	list_node_t *pred_n;

	n = node;
	do {
		node_sym = csi_to_symbol(node);
		symbol_print_fqn(node_sym);
		printf(", ");

		outer_csi = node_sym->outer_csi;

		if (outer_csi != NULL && outer_csi->ancr_state == ws_active) {
			node = outer_csi;
		} else {
			node = NULL;

			pred_n = list_first(&node->inherit);
			while (pred_n != NULL) {
				pred = list_node_data(pred_n, stree_texpr_t *);
				pred_sym = symbol_xlookup_in_csi(prog,
				    outer_csi, pred);
				pred_csi = symbol_to_csi(pred_sym);
				assert(pred_csi != NULL);

				if (pred_csi->ancr_state == ws_active) {
					node = pred_csi;
					break;
				}
			}

			assert(node != NULL);
		}
	} while (n != node);

	node_sym = csi_to_symbol(node);
	symbol_print_fqn(node_sym);
}