/*

 * rea.c --

 *

 *      This file holds the reverse engineering algorithm common for

 *      dump-cm.c and dump-svg.c.

 *

 * Copyright (c) 2000 A. Mueller, Technical University of Braunschweig.

 * Copyright (c) 2005 K. Sperner, Technical University of Braunschweig.

 *

 * See the file "COPYING" for information on usage and redistribution

 * of this file, and for a DISCLAIMER OF ALL WARRANTIES.

 *

 * @(#) $Id: rea.c 7823 2008-03-01 13:53:12Z schoenw $

 */

#include <config.h>

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

#include <ctype.h>

#ifdef HAVE_WIN_H

#include "win.h"

#endif

#include "smi.h"

#include "smidump.h"

#include "rea.h"

/*

 * Constants used by the reverse engineering algorithm.

 */

static char *pointer[] = {

    "Index", NULL

};

static char *suffix[] = {

    "OrZero", NULL

};

static char *supportObjs[] = {

    "RowStatus", "StorageType", NULL

};

static char *baseTypes[] = {

    "Integer32", "OctetString", "Unsigned32", "Integer64",

    "Unsigned64", "Float32", "Float64", "Float128",

    "Enumeration", "Counter32", "Counter64","Bits",

    "Gauge", "Gauge32", "Integer", "TimeTicks",

    "IpAddress", "Opaque", "ObjectIdentifier",

    NULL

};

/*

 * driver output control

 */

/*

 * variables for svg-output

 *

 * When you change CANVASHEIGHT, CANVASWIDTH values here, you should

 * also change them in initSvg() and the cgi-script.

 */

int       CANVASHEIGHT          = 700; /* height of the svg */

int       CANVASWIDTH           = 1100; /* width of the svg */

int       SHOW_DEPRECATED       = 0; /* false, show deprecated objects */

int       SHOW_DEPR_OBSOLETE    = 0; /* false, show deprecated and

					obsolete objects */

int       STATIC_OUTPUT         = 0; /* false, enable interactivity */

/* variables for cm-driver */

int       XPLAIN                = 0; /* false, generates ASCII output */

int       XPLAIN_DEBUG          = 0; /* false, generates additional

					       output in xplain-mode */

int       SUPPRESS_DEPRECATED   = 1; /* true, suppresses deprecated

					       objects */

/* common variables */

int       PRINT_DETAILED_ATTR   = 1; /* true, prints all column

					       objects */

int       IGNORE_IMPORTED_NODES = 1; /* true, ignores nodes which are

					       imported from other MIBs*/

/*

 * global variables

 */

Graph     *graph  = NULL;            /* the graph */

/* ------ Misc. -----------------                                            */

/*

 * cmpSmiNodes

 *

 * Compares two SmiNode and returns 1 if they are equal and 0 otherwise.

 */

int cmpSmiNodes(SmiNode *node1, SmiNode *node2)

{

    SmiModule *module1, *module2;

    module1 = smiGetNodeModule(node1);

    module2 = smiGetNodeModule(node2);

    if (!node1 || !node2 || !module1 || !module2) return 0;

    return (strcmp(node1->name, node2->name) == 0 &&

	    strcmp(module1->name, module2->name) == 0);

}

/*

 * strpfxlen

 *

 * Returns the number of identical characters at the beginning of s1 and s2.

 */

static int strpfxlen(const char *s1, const char *s2)

{

    int i;

    for (i = 0; s1[i] && s2[i]; i++) {

	if (s1[i] != s2[i]) {

	    break;

	}

    }

    return i;

}

/* ------ Graph primitives ------                                            */

/*

 * graphInsertNode

 *

 *          Inserts a new node into an existing graph.

 *

 * Result : pointer to the new node

 */

GraphNode *graphInsertNode(Graph *graph, SmiNode *smiNode)

{

    GraphNode *newNode;

    GraphNode *tNode;

    GraphNode *lastNode;

    newNode = xmalloc(sizeof(GraphNode));

    memset(newNode, 0, sizeof(GraphNode));

    newNode->smiNode = smiNode;

    if (graph->nodes == NULL) {

	graph->nodes = newNode;

	return newNode;

    }

    lastNode = NULL; 

    for (tNode = graph->nodes; tNode; tNode = tNode->nextPtr) {

	lastNode = tNode;

    }

    lastNode->nextPtr = newNode;

    return newNode;

}

/*

 * graphInsertComponent

 *

 *          Inserts a new component into an existing graph.

 *

 * Result : pointer to the new component

 */

GraphComponent *graphInsertComponent(Graph *graph)

{

    GraphComponent *newComponent;

    GraphComponent *tComponent;

    GraphComponent *lastComponent;

    newComponent = xmalloc(sizeof(GraphComponent));

    memset(newComponent, 0, sizeof(GraphComponent));

    if (graph->components == NULL) {

	graph->components = newComponent;

	return newComponent;

    }

    lastComponent = NULL;

    for (tComponent = graph->components; tComponent;

					    tComponent = tComponent->nextPtr) {

	lastComponent = tComponent;

    }

    lastComponent->nextPtr = newComponent;

    return newComponent;

}

/*

 * graphInsertEdge

 *

 *          Inserts a new edge into an existing list of edges.

 *

 * Input  : graph     = pointer to an edge structure

 *          startNode = pointer to the starting node of the edge

 *          endNode   = pointer to the ending node of the edge

 *          indexkind = type of relationship between the two nodes

 *

 * Result : pointer to the new edge

 */

static GraphEdge *graphInsertEdge(Graph *graph, GraphNode *startNode,

			      GraphNode *endNode,

			      SmiIndexkind indexkind,

			      GraphEnhIndex enhancedindex)

{

    GraphEdge *newEdge;

    GraphEdge *tEdge;

    GraphEdge *lastEdge;

    newEdge = xmalloc(sizeof(GraphEdge));

    memset(newEdge, 0, sizeof(GraphEdge));

    newEdge->startNode = startNode;

    newEdge->endNode = endNode;

    newEdge->indexkind = indexkind;

    newEdge->connection = GRAPH_CON_ASSOCIATION;

    newEdge->enhancedindex = enhancedindex;

    switch (newEdge->indexkind) {

    case SMI_INDEX_AUGMENT : 

	newEdge->cardinality = GRAPH_CARD_ONE_TO_ONE; 

	break;

    case SMI_INDEX_SPARSE  : 

	newEdge->cardinality = GRAPH_CARD_ONE_TO_ZERO_OR_ONE; 

	break;

    case SMI_INDEX_EXPAND  : 

	newEdge->cardinality = GRAPH_CARD_UNKNOWN; 

	break;

    case SMI_INDEX_REORDER : 

	newEdge->cardinality = GRAPH_CARD_ONE_TO_ONE; 

	break;

    case SMI_INDEX_INDEX   : 

	newEdge->cardinality = GRAPH_CARD_UNKNOWN; 

	break;

    case SMI_INDEX_UNKNOWN : 

	newEdge->cardinality = GRAPH_CARD_UNKNOWN; 

	break;

    }

    if (graph->edges == NULL) {

	graph->edges = newEdge;

	return newEdge;

    }

    lastEdge = NULL; 

    for (tEdge = graph->edges; tEdge; tEdge = tEdge->nextPtr) {

	lastEdge = tEdge;

    }

    lastEdge->nextPtr = newEdge;

    return newEdge;

}

/*

 * graphExit

 *

 * Frees all memory allocated by the graph.

 */

void graphExit(Graph *graph)

{

    GraphEdge *tEdge, *dummyEdge;

    GraphNode *tNode, *dummyNode;

    GraphComponent *tComponent, *dummyComponent;

    if (graph) {

	dummyNode = NULL;

	tNode = graph->nodes;

	while (tNode != NULL) {

	    dummyNode = tNode;

	    tNode = tNode->nextPtr;

	    xfree(dummyNode);

	}

	dummyEdge = NULL;

	tEdge = graph->edges;

	while (tEdge != NULL) {

	    dummyEdge = tEdge;

	    tEdge = tEdge->nextPtr;

	    xfree(dummyEdge);

	}

	dummyComponent = NULL;

	tComponent = graph->components;

	while (tComponent != NULL) {

	    dummyComponent = tComponent;

	    tComponent = tComponent->nextPtr;

	    xfree(dummyComponent);

	}

	xfree(graph);

    }

}

/*

 * graphGetFirstEdgeByNode

 *

 * Returns the first edge adjacent to the given node (as startNode or EndNode).

 */

GraphEdge *graphGetFirstEdgeByNode(Graph *graph, GraphNode *node)

{

    GraphEdge *tEdge;

    if (!graph || !node) {

	return NULL;

    }

    for (tEdge = graph->edges; tEdge; tEdge = tEdge->nextPtr) {

	/*if (tEdge->startNode->smiNode->name == node->smiNode->name ||

	  tEdge->endNode->smiNode->name == node->smiNode->name) break;*/

	if (cmpSmiNodes(tEdge->startNode->smiNode, node->smiNode) ||

	    cmpSmiNodes(tEdge->endNode->smiNode, node->smiNode)) break;

    }

    return tEdge;

}

/*

 * graphGetNextEdgeByNode

 *

 * Returns the next edge adjacent to the given node (as startNode or EndNode)

 * after the given edge.

 */

GraphEdge *graphGetNextEdgeByNode(Graph *graph, 

					 GraphEdge *edge,

					 GraphNode *node) 

{

    GraphEdge *tEdge;

    if (!graph || !node) {

	return NULL;

    }

    for (tEdge = graph->edges; tEdge; tEdge = tEdge->nextPtr) {

	/*if (tEdge->startNode->smiNode->name ==

	    edge->startNode->smiNode->name &&

	    tEdge->endNode->smiNode->name ==

	    edge->endNode->smiNode->name) break;*/

	if (cmpSmiNodes(tEdge->startNode->smiNode,edge->startNode->smiNode) &&

	    cmpSmiNodes(tEdge->endNode->smiNode,edge->endNode->smiNode))

	    break;

    }

    for (tEdge = tEdge->nextPtr; tEdge; tEdge = tEdge->nextPtr) {

	/*if (tEdge->startNode->smiNode->name == node->smiNode->name ||

	  tEdge->endNode->smiNode->name == node->smiNode->name) break;*/

	if (cmpSmiNodes(tEdge->startNode->smiNode, node->smiNode) ||

	    cmpSmiNodes(tEdge->endNode->smiNode, node->smiNode)) break;

    }

    return tEdge;

}

/*

 * graphCheckForRedundantEdge

 *

 * Finds redundant edges and returns 1 if one is found and 0 otherwise.

 */

static int graphCheckForRedundantEdge(Graph *graph,

			       GraphNode *startNode,

			       GraphNode *endNode)

{

    GraphEdge *tEdge;

    if (!graph || !startNode || !endNode) {

	return 0;

    }

    for (tEdge = graph->edges; tEdge; tEdge = tEdge->nextPtr) {

	/*if (tEdge->startNode->smiNode->name == startNode->smiNode->name &&

	  tEdge->endNode->smiNode->name == endNode->smiNode->name) {*/

	if (cmpSmiNodes(tEdge->startNode->smiNode, startNode->smiNode) &&

	    cmpSmiNodes(tEdge->endNode->smiNode, endNode->smiNode)) {

	    return 1;

	}

    }

    return 0;

}

/*

 * graphGetNode

 *

 * Returns the graph node containing smiNode.

 */

static GraphNode *graphGetNode(Graph *graph, SmiNode *smiNode)

{

    GraphNode *tNode;

    if (!smiNode || !graph) {

	return NULL;

    }

    for (tNode = graph->nodes; tNode; tNode = tNode->nextPtr) {

	if (tNode->smiNode->name == smiNode->name) {

	    break;

	}

    }

    return tNode;

}

/*

 * graphShowNodes

 *

 * Prints the nodes of the graph.

 */

void graphShowNodes(Graph *graph) 

{

    GraphNode *tNode;

    if (!graph->nodes) {

	printf("No nodes!\n");

	return;

    }

    for (tNode = graph->nodes; tNode; tNode = tNode->nextPtr) {

	if (tNode->smiNode->nodekind == SMI_NODEKIND_TABLE)

	    printf(" [TABLE]");

	else printf("[SCALAR]");

	printf("%40s [%s]\n", tNode->smiNode->name,

	       smiGetNodeModule(tNode->smiNode)->name);

    }

}

/*

 * graphShowEdges

 *

 * Prints the edges with their attributes in the following order :

 *    - start node

 *    - reason for the link

 *    - connection type in UML

 *    - cardinality

 *    - index relationship derived from the row-objects of the tables

 *

 */

static void graphShowEdges(Graph *graph) 

{

    GraphEdge  *tEdge;

    if (!graph->edges) {

	printf("No edges!\n");

	return;

    }

    for (tEdge = graph->edges; tEdge; tEdge = tEdge->nextPtr) {

	if (XPLAIN_DEBUG) {

	    switch (tEdge->enhancedindex) {

	    case GRAPH_ENHINDEX_UNKNOWN :

		printf("[UNKNOWN] ");

		break;

	    case GRAPH_ENHINDEX_NOTIFICATION :

		break;

	    case GRAPH_ENHINDEX_NAMES :

		printf("  [NAMES] ");

		break;

	    case GRAPH_ENHINDEX_TYPES :

		printf("  [TYPES] ");

		break;

	    case GRAPH_ENHINDEX_INDEX :

		printf("  [INDEX] ");

		break;

	    case GRAPH_ENHINDEX_REROUTE :

		printf("[REROUTE] ");

		break;

	    case GRAPH_ENHINDEX_POINTER :

		printf("[POINTER] ");

		break;	    

	    }

	}

	switch (tEdge->connection) {

	case GRAPH_CON_AGGREGATION:

	    printf("AG.");

	    break;

	case GRAPH_CON_DEPENDENCY:

	    printf("D. ");

	    break;

	case GRAPH_CON_ASSOCIATION:

	    printf("A. ");

	    break;    

	case GRAPH_CON_UNKNOWN:

	    break;

	}

	switch (tEdge->cardinality) {

	case GRAPH_CARD_UNKNOWN      :

	    printf("  (-:-)  ");

	    break;

	case GRAPH_CARD_ONE_TO_ONE   :

	    printf("  (1:1)  ");

	    break;

	case GRAPH_CARD_ONE_TO_MANY  :

	    printf("  (1:n)  ");

	    break;

	case GRAPH_CARD_ZERO_TO_ONE  :

	    printf("  (0:1)  ");

	    break;

	case GRAPH_CARD_ZERO_TO_MANY :

	    printf("  (0:n)  ");

	    break;

	case GRAPH_CARD_ONE_TO_ZERO_OR_ONE :

	    printf("(1:0..1) ");

	    break;	    

	}

	switch (tEdge->indexkind) {

	case SMI_INDEX_UNKNOWN  :

	    printf("GENERIC ");

	    break;

	case SMI_INDEX_INDEX    :

	    printf("  INDEX ");

	    break;

	case SMI_INDEX_AUGMENT  :

	    printf("AUGMENT ");

	    break;

	case SMI_INDEX_SPARSE   :

	    printf(" SPARSE ");

	    break;

	case SMI_INDEX_EXPAND   :

	    printf(" EXPAND ");

	    break;

	case SMI_INDEX_REORDER  :

	    printf("REORDER ");

	    break;

	}

	printf("%29s - ",tEdge->startNode->smiNode->name);

	printf("%s\n",tEdge->endNode->smiNode->name);

    }

}

/* ------ algorithm primitives ------                                        */

/*

 * algCountIndexElements

 *

 * Returns the number of index elements in a given row entry.

 */

static int algCountIndexElements(SmiNode *smiNode) 

{

    int          count;

    SmiElement   *smiElement;

    if (smiNode->nodekind != SMI_NODEKIND_ROW) {

	return 0;

    }

    count = 0;

    for (smiElement = smiGetFirstElement(smiNode);

	 smiElement;

	 smiElement = smiGetNextElement(smiElement)) {

	count++;

    }

    return count;

}

/*

 * algInsertEdge

 *

 * Inserts an edge in a given graph. The edge is adjacent to snode 

 * and enode.

 * The type of edge is given in indexkind and the enhanced index as

 * an additional information in enhancedindex.

 * Nodes which are not loaded yet into the node list of the graph

 * are added (nodes from imported MIBs).

 */

static void algInsertEdge(SmiNode *snode, SmiNode *enode, 

			  SmiIndexkind indexkind,

			  GraphEnhIndex enhancedindex) 

{

    GraphNode *startNode;

    GraphNode *endNode;

    if (!graph) return;

    startNode = graphGetNode(graph, snode);

    endNode   = graphGetNode(graph, enode);

    /* insert imported nodes into graph if needed */

    if (startNode == NULL) {

	if (IGNORE_IMPORTED_NODES) return;

	startNode = graphInsertNode(graph, snode);

    }

    if (endNode == NULL) {

	if (IGNORE_IMPORTED_NODES) return;

	endNode = graphInsertNode(graph, enode);

    }  

    if (graphCheckForRedundantEdge(graph, startNode, endNode) == 0 &&

	graphCheckForRedundantEdge(graph, endNode, startNode) == 0) {

	graphInsertEdge(graph, startNode, endNode, indexkind, enhancedindex); 

    }

}

/*

 * algGetGroupByFatherNode

 *

 * Returns the group number associated with the father node of the

 * given node. If there is no group the result is 0 for no

 * grouping.

 */

static int algGetGroupByFatherNode(SmiNode *smiNode)

{

    GraphNode *tNode;

    for (tNode = graph->nodes; tNode; tNode = tNode->nextPtr) {

	if (tNode->smiNode->nodekind == SMI_NODEKIND_SCALAR &&

	    !graphGetFirstEdgeByNode(graph, tNode)) {

	    if (cmpSmiNodes(smiGetParentNode(smiNode),

			    smiGetParentNode(tNode->smiNode))) {

		return tNode->group;

	    }

	}

    }

    return 0;

}

/*

 * algGetNumberOfGroups

 *

 * Returns the number of groups.

 */

int algGetNumberOfGroups()

{

    GraphNode *tNode;

    int       maxGroup;

    maxGroup = 0;

    for (tNode = graph->nodes; tNode; tNode = tNode->nextPtr) {

	maxGroup = max(maxGroup, tNode->group); 

    }

    return maxGroup;

}

/*

 * algPrintGroup

 *

 * Prints the group with the number group.

 */

static void algPrintGroup(int group)

{

    GraphNode *tNode;

    for (tNode = graph->nodes; tNode; tNode = tNode->nextPtr) {

	if (tNode->group == group) {

	    printf("%2d - %35s\n", group, tNode->smiNode->name);

	}

    }

}

/*

 * algGetTypeDescription

 *

 * Returns the description of the data type used in smiNode.

 */

char *algGetTypeDescription(SmiNode *smiNode)

{

    SmiType *smiType, *parentType;

    smiType = smiGetNodeType(smiNode);

    if (!smiType || smiNode->nodekind == SMI_NODEKIND_TABLE)

	return NULL;

    if (smiType->decl == SMI_DECL_IMPLICIT_TYPE) {

	parentType = smiGetParentType(smiType);

	smiType = parentType;

    }

    return smiType->description;

}

/*

 * algGetTypeName

 *

 * Returns the name of the data type used in smiNode.

 */

char *algGetTypeName(SmiNode *smiNode)

{

    SmiType *smiType, *parentType;

    smiType = smiGetNodeType(smiNode);

    if (!smiType || smiNode->nodekind == SMI_NODEKIND_TABLE)

	return NULL;

    if (smiType->decl == SMI_DECL_IMPLICIT_TYPE) {

	parentType = smiGetParentType(smiType);

	smiType = parentType;

    }

    return smiType->name;

}

/*

 * algGetTypeModule

 *

 * Returns the module which defines the data type used in smiNode.

 */

SmiModule *algGetTypeModule(SmiNode *smiNode)

{

    SmiType *smiType, *parentType;

    SmiModule *smiModule;

    smiType = smiGetNodeType(smiNode);

    if (!smiType || smiNode->nodekind == SMI_NODEKIND_TABLE)

	return NULL;

    if (smiType->decl == SMI_DECL_IMPLICIT_TYPE) {

	parentType = smiGetParentType(smiType);

	smiType = parentType;

    }

    smiModule = smiGetTypeModule(smiType);

    return smiModule;

}

/*

 * algCountElementsFromOtherTables

 *

 * Returns the number of index objects derived from other tables than

 * the given one.

 */

static int algCountElementsFromOtherTables(SmiNode *smiNode)

{

    SmiElement *smiElement;

    SmiNode    *tNode;

    int        elems = 0;

    for (smiElement = smiGetFirstElement(smiNode);

	 smiElement;

	 smiElement = smiGetNextElement(smiElement)) {

	tNode = smiGetElementNode(smiElement);

	if (cmpSmiNodes(smiGetParentNode(smiGetParentNode(tNode)),

			smiGetParentNode(smiNode)) != 1) {

	    elems++;

	}

    }

    return elems;

}

/*

 * algGetNumberOfRows

 *

 * Returns the number of rows =

 *   number of elements in smiNode - number of rows 

 *   + RowStatus-Objects + StorageType-Objects

 *

 * If the number is > 0 it is only a supporting table (like entLPMappingTable) 

 * and if the number is < 0 it is a "full" table (like ifTable).

 *

 * Subroutine for algCheckForDependency.

 */

static int algGetNumberOfRows(SmiNode *smiNode)

{

    SmiNode *tSmiNode;

    SmiNode *table;

    int     i, elemCount;

    elemCount = 0;

    table = smiNode;

    tSmiNode = smiGetFirstChildNode(table);

    elemCount = algCountIndexElements(tSmiNode) -

	algCountElementsFromOtherTables(tSmiNode);

    for (tSmiNode = smiGetNextNode(tSmiNode, SMI_NODEKIND_COLUMN);

	 tSmiNode;

	 tSmiNode = smiGetNextNode(tSmiNode, SMI_NODEKIND_COLUMN)) {

	if (cmpSmiNodes(table, smiGetParentNode(smiGetParentNode(tSmiNode)))

	    != 1) {

	    break;

	}

	for (i = 0; supportObjs[i]; i++) {

	    char *typeName = algGetTypeName(tSmiNode);

	    if (typeName && (strcasecmp(typeName, supportObjs[i]) == 0)) {

		break;

	    }

	}

	if (!supportObjs[i]) elemCount--;

    }

    return elemCount;

}

/*

 * isBaseType

 *

 * returns 1 if smiElement is a basetype used in SMIv2/SMIng. Otherwise

 * the result is 0.

 */

int isBaseType(SmiNode *node)

{

    int i;

    for (i = 0; baseTypes[i]; i++) {

	if (strcasecmp(algGetTypeName(node), baseTypes[i]) == 0) {

	    return 1;

	}

    }

    return 0;

}

/*

 * algFindEqualType

 *

 * Looks in all tables indices for an equal type to the type used in typeNode.

 * It returns the first table found which is different to startTable.

 *

 * Subroutine for algCheckForDependency. 

 */

static SmiNode *algFindEqualType(SmiNode *startTable, SmiNode *typeNode)

{

    SmiElement *smiElement;

    SmiNode    *tSmiNode;

    char       *typeName;

    GraphNode  *tNode;

    typeName = algGetTypeName(typeNode);

    /* if (isBaseType(typeNode)) return NULL; */

    for (tNode = graph->nodes; tNode; tNode = tNode->nextPtr) {

	if (tNode->smiNode->nodekind == SMI_NODEKIND_TABLE) {

	    tSmiNode = tNode->smiNode;

	    if (cmpSmiNodes(tSmiNode, startTable) == 1) break;