tree.c

C程序漏洞检查！

/***** uno: tree.c *****/

/* Copyright (c) 2000-2003 by Lucent Technologies - Bell Laboratories     */
/* All Rights Reserved.  This software is for educational purposes only.  */
/* Permission is given to distribute this code provided that this intro-  */
/* ductory message is not removed and no monies are exchanged.            */
/* No guarantee is expressed or implied by the distribution of this code. */
/* Software written by Gerard J. Holzmann based on the public domain      */
/* ANSI-C parser Ctree Version 0.14 from Shaun Flisakowski                */

/* Original version by Shaun Flisakowski, Jan 21, 1995 */
/* Revisions by Kurt Cockrum */
/* Extensions and revisions for Uno by Gerard Holzmann */

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

#include    "tree.h"
#include    "gram.h"
#include    "globals.h"
#include    "token.h"
#include    "prnttree.h"

extern void	efree(void *);
extern char	*progname;

char*
print_ptr(void *ptr)
{	static char buf[32];

	sprintf(buf, "%p", ptr);

	return buf;
}

if_node *
make_if(tn_t type)
{
    if_node *tmp_node;

    tmp_node = (if_node *) HeapAlloc(Parse_TOS->node_heap);
    if (tmp_node == NULL)
    {
        fputs("Error: Out of memory in make_if.\n",stderr);
        exit(1);
    }

    tmp_node->hdr.which = IF_T;
    tmp_node->hdr.type  = type;
    tmp_node->hdr.defuse = 0;
    tmp_node->cond  = (treenode *) NULL;
    tmp_node->then_n = (treenode *) NULL;
    tmp_node->else_n = (treenode *) NULL;
    return tmp_node;
}

for_node *
make_for(tn_t type)
{
    for_node *tmp_node;

    tmp_node = (for_node *) HeapAlloc(Parse_TOS->node_heap);

    if (tmp_node == NULL)
    {
        fputs("Error: Out of memory in make_for.\n",stderr);
        exit(1);
    }

    tmp_node->hdr.which = FOR_T;
    tmp_node->hdr.type = type;
    tmp_node->hdr.defuse = 0;
    tmp_node->init = (treenode *) NULL;
    tmp_node->test = (treenode *) NULL;
    tmp_node->incr = (treenode *) NULL;
    tmp_node->stemnt = (treenode *) NULL;
    return tmp_node;
}

leafnode *
make_leaf(tn_t type)
{
    leafnode *tmp_node;

    tmp_node = (leafnode *) HeapAlloc(Parse_TOS->node_heap);

    if (tmp_node == NULL)
    {
        fputs("Error: Out of memory in make_leaf.\n",stderr);
        exit(1);
    }

    tmp_node->hdr.which = LEAF_T;
    tmp_node->hdr.type = type;
    tmp_node->hdr.defuse = 0;

    tmp_node->syment = (symentry_t *) NULL;
    return tmp_node;
}

treenode *
make_node(tn_t type)
{
    treenode *tmp_node;

    tmp_node = (treenode *) HeapAlloc(Parse_TOS->node_heap);

    if (tmp_node == NULL)
    {
        fputs("Error: Out of memory in make_node.\n",stderr);
        exit(1);
    }

    tmp_node->hdr.which = NODE_T;
    tmp_node->hdr.type  = type;
    tmp_node->hdr.defuse = 0;

    tmp_node->lnode = (treenode *) NULL;
    tmp_node->rnode = (treenode *) NULL;
    tmp_node->syment = (symentry_t *) NULL;

    return tmp_node;
}

void
free_tree(treenode *root)
{
    leafnode *leaf;
    if_node  *ifn;
    for_node *forn;

    if (!root)
        return;

    switch (root->hdr.which){

    case LEAF_T:
        leaf = (leafnode *) root;
        if (leaf->hdr.tok == STRING)
           efree(leaf->data.str);
        break;

    case NODE_T:
        free_tree(root->lnode);
        free_tree(root->rnode);
        break;

    case IF_T:
        ifn = (if_node *) root;
        free_tree(ifn->cond);
        free_tree(ifn->then_n);
        free_tree(ifn->else_n);
        break;

    case FOR_T:
        forn = (for_node *) root;
        free_tree(forn->init);
        free_tree(forn->test);
        free_tree(forn->incr);
        free_tree(forn->stemnt);
        break;

    default:
    case NONE_T:
        break;
    }

    HeapFree(Parse_TOS->node_heap,root);
}

leafnode *
leftmost(treenode *root)
{
    if_node *ifn;
    for_node *forn;

	if (!root) return (leafnode *) 0;

    switch (root->hdr.which){

    case LEAF_T:
        return((leafnode *) root);
        break;

    case NODE_T:
        if (root->lnode)
            return(leftmost(root->lnode));
        else if (root->rnode)
            return(leftmost(root->rnode));
        fprintf(stderr,
            "Tree node %s with no children reached in leftmost.\n",
                print_ptr(root));
        break;

    case IF_T:
        ifn = (if_node *) root;
        if (ifn->cond)
            return(leftmost(ifn->cond));
        else if (ifn->then_n)
            return(leftmost(ifn->then_n));
        else if (ifn->else_n)
            return(leftmost(ifn->else_n));
        fprintf(stderr,
            "If-node %s with no children reached in leftmost.\n",
                print_ptr(root));
        break;

    case FOR_T:
        forn = (for_node *) root;
        if (forn->init)
            return(leftmost(forn->init));
        else if (forn->test)
            return(leftmost(forn->test));
        else if (forn->incr)
            return(leftmost(forn->incr));
        else if (forn->stemnt)
            return(leftmost(forn->stemnt));
        fprintf(stderr,
            "For-node %s with no children reached in leftmost.\n",
                print_ptr(root));
        break;

    case NONE_T:
	break;

    default:
        fprintf(stderr, "%s: parse error: unknown node %s in leftmost; "
         "  type: %s\n", progname, print_ptr(root), name_of_nodetype(root->hdr.which));
        break;
    }

    return((leafnode *) NULL);
}

/* Scans the typedef declaration node N for the ident
   naming the new type. --jsh */
void
find_typedef_name(treenode *n, treenode *def, FindFunction find)
{
    if (!n)
        return;

	if (0)
	printf("%s: find_typedef_name %s - %s\n",
		progname, name_of_nodetype(n->hdr.which), name_of_node(n->hdr.type));

    switch(n->hdr.which)
    {
        case LEAF_T:
            (find)((leafnode*) n, def, NULL);
            break;

        case NODE_T:
        {
            switch(n->hdr.type)
            {
            case TN_DECL:
                find_typedef_name(n->rnode,def,find);
                break;

            case TN_ARRAY_DECL:
                find_typedef_name(n->lnode,def,find);
                break;

            case TN_PNTR:
#if 0
                fprintf(stderr,
                    "%s: parse error: TN_PNTR reached in find_typedef_name!\n", progname);
		/* can happen, e.g.: typedef long name(int *); */
#endif
                break;

            case TN_DECL_LIST:
            case TN_DECLS:
                find_typedef_name(n->lnode,def,find);
                find_typedef_name(n->rnode,def,find);
                break;

            case TN_FUNC_DECL:

		if (0) printf("lnode=%s %s rnode=%s %s\n",
		name_of_nodetype(n->lnode->hdr.which), name_of_node(n->lnode->hdr.type),
		name_of_nodetype(n->rnode->hdr.which), name_of_node(n->rnode->hdr.type));

		if (n->lnode->hdr.which == LEAF_T)		/* gjh added */
			find_typedef_name(n->lnode,def,find);
		else if (n->lnode->hdr.type == TN_DECL)
                    find_typedef_name(n->lnode,def,find);
                else
                    find_typedef_name(n->rnode,def,find);
                break;

	    case TN_PARAM_LIST:
		return;

            default:
                fprintf(stderr,
                        "%s: parse error: "
                        "unknown node type (%s) in find_typedef_name\n",
                        progname, name_of_node(n->hdr.type));
                break;
            }
        }
        break;

        case IF_T:
        case FOR_T:
        case NONE_T:
        default:
            fprintf(stderr,
                "%s: parse error: unknown node %s in find_typedef_name;"
                "  type: %s\n", progname, print_ptr(n), name_of_nodetype(n->hdr.which));
            break;
    }
}

void
find_ident_name(treenode *n, treenode *def, treenode *container, FindFunction find)
{
    if (!n)
        return;

    switch(n->hdr.which)
    {
    case LEAF_T:
        (find)((leafnode*) n,def,container);
        break;

    case NODE_T:
    {
        switch(n->hdr.type)
        {
        case TN_IDENT:
            (find)((leafnode*) n,def,container);
            break;

        case TN_DECL:
            find_ident_name(n->rnode,def,container,find);
            break;

        case TN_COMP_DECL:
            find_ident_name(n->rnode,def,container,find);
            break;

        case TN_ASSIGN:
        case TN_ARRAY_DECL:
            find_ident_name(n->lnode,def,container,find);