Pccts/h/PCCTSAST.cpp

	PCCTSAST.cpp revision 4fd606d1f5abe38e1f42c38de1d2e895166bd0f4
/*
 * PCCTSAST.C
 *
 * SOFTWARE RIGHTS
 *
 * We reserve no LEGAL rights to SORCERER -- SORCERER is in the public
 * domain.  An individual or company may do whatever they wish with
 * source code distributed with SORCERER or the code generated by
 * SORCERER, including the incorporation of SORCERER, or its output, into
 * commerical software.
 *
 * We encourage users to develop software with SORCERER.  However, we do
 * ask that credit is given to us for developing SORCERER.  By "credit",
 * we mean that if you incorporate our source code into one of your
 * programs (commercial product, research project, or otherwise) that you
 * acknowledge this fact somewhere in the documentation, research report,
 * etc...  If you like SORCERER and have developed a nice tool with the
 * output, please mention that you developed it using SORCERER.  In
 * addition, we ask that this header remain intact in our source code.
 * As long as these guidelines are kept, we expect to continue enhancing
 * this system and expect to make other tools available as they are
 * completed.
 *
 * SORCERER 1.00B14 and ANTLR 1.33
 * Terence Parr
 * Parr Research Corporation
 * AHPCRC, University of Minnesota
 * 1992-2000
 */

#define ANTLR_SUPPORT_CODE

#include "pcctscfg.h"

#include "PCCTSAST.h"
#include "pccts_stdarg.h"

PCCTS_NAMESPACE_STD

#include <ctype.h>

//#include "SList.h"

               /* String Scanning/Parsing Stuff */

const char *PCCTS_AST::scan_token_tbl[] = {     /* MR20 const */
    "invalid",  /*  0 */
    "LPAREN",   /*  1 */
    "RPAREN",   /*  2 */
    "PERCENT",  /*  3 */
    "INT",      /*  4 */
    "COLON",    /*  5 */
    "POUND",    /*  6 */
    "PERIOD",   /*  7 */
};

void PCCTS_AST::
addChild(PCCTS_AST *t)
{
    if ( t==NULL ) return;
    PCCTS_AST *s = down();
    if ( s!=NULL )
    {
        while ( s->right()!=NULL ) s = s->right();
        s->setRight(t);
    }
    else
        this->setDown(t);
}

void PCCTS_AST::
lisp(FILE *f)
{
    if ( down() != NULL ) /* MR23 */ printMessage(f," (");
    lisp_action(f);
    if ( down()!=NULL ) down()->lisp(f);
    if ( down() != NULL ) /* MR23 */ printMessage(f," )");
    if ( right()!=NULL ) right()->lisp(f);
}

/* build a tree (root child1 child2 ... NULL)
 * If root is NULL, simply make the children siblings and return ptr
 * to 1st sibling (child1).  If root is not single node, return NULL.
 *
 * Siblings that are actually sibling lists themselves are handled
 * correctly.  For example #( NULL, #( NULL, A, B, C), D) results
 * in the tree ( NULL A B C D ).
 *
 * Requires at least two parameters with the last one being NULL.  If
 * both are NULL, return NULL.
 *
 * The down() and right() down/right pointers are used to make the tree.
 */
PCCTS_AST *PCCTS_AST::
make(PCCTS_AST *rt, ...)
{
    va_list ap;
    register PCCTS_AST *child, *sibling=NULL, *tail=NULL /*MR23*/, *w;
    PCCTS_AST *root;

    va_start(ap, rt);
    root = rt;

    if ( root != NULL )
        if ( root->down() != NULL ) return NULL;
    child = va_arg(ap, PCCTS_AST *);
    while ( child != NULL )
    {
        /* find end of child */
        for (w=child; w->right()!=NULL; w=w->right()) {;}
        if ( sibling == NULL ) {sibling = child; tail = w;}
        else {tail->setRight(child); tail = w;}
        child = va_arg(ap, PCCTS_AST *);
    }
    if ( root==NULL ) root = sibling;
    else root->setDown(sibling);
    va_end(ap);
    return root;
}

/* The following push and pop routines are only used by ast_find_all() */

void PCCTS_AST::
_push(PCCTS_AST **st, int *sp, PCCTS_AST *e)
{
    (*sp)--;
    require((*sp)>=0, "stack overflow");
    st[(*sp)] = e;
}

PCCTS_AST *PCCTS_AST::
_pop(PCCTS_AST **st, int *sp)
{
    PCCTS_AST *e = st[*sp];
    (*sp)++;
    require((*sp)<=MaxTreeStackDepth, "stack underflow");
    return e;
}

/* Find all occurrences of u in t.
 * 'cursor' must be initialized to 't'.  It eventually
 * returns NULL when no more occurrences of 'u' are found.
 */
PCCTS_AST *PCCTS_AST::
ast_find_all(PCCTS_AST *u, PCCTS_AST **cursor)
{
    PCCTS_AST *sib;
    /*** static ***/ PCCTS_AST *template_stack[MaxTreeStackDepth];  /* MR23 Remove "static" */
    /*** static ***/ int tsp = MaxTreeStackDepth;                   /* MR23 Remove "static" */

////static int nesting = 0;                                         /* MR23 Not referenced */

    if ( *cursor == NULL ) return NULL;
    if ( *cursor!=this ) sib = *cursor;
    else {
        /* else, first time--start at top of template 't' */
        tsp = MaxTreeStackDepth;
        sib = this;
        /* bottom of stack is always a NULL--"cookie" indicates "done" */
        _push(template_stack, &tsp, NULL);
    }

keep_looking:
    if ( sib==NULL )    /* hit end of sibling list */
    {
        sib = _pop(template_stack, &tsp);
        if ( sib == NULL ) { *cursor = NULL; return NULL; }
    }

    if ( sib->type() != u->type() )
    {
        /* look for another match */
        if ( sib->down()!=NULL )
        {
            if ( sib->right()!=NULL ) _push(template_stack, &tsp, sib->right());
            sib=sib->down();
            goto keep_looking;
        }
        /* nothing below to try, try next sibling */
        sib=sib->right();
        goto keep_looking;
    }

    /* found a matching root node, try to match what's below */
    if ( match_partial(sib, u) )
    {
        /* record sibling cursor so we can pick up next from there */
        if ( sib->down()!=NULL )
        {
            if ( sib->right()!=NULL ) _push(template_stack, &tsp, sib->right());
            *cursor = sib->down();
        }
        else if ( sib->right()!=NULL ) *cursor = sib->right();
        else *cursor = _pop(template_stack, &tsp);
        return sib;
    }

    /* no match, keep searching */
    if ( sib->down()!=NULL )
    {
        if ( sib->right()!=NULL ) _push(template_stack, &tsp, sib->right());
        sib=sib->down();
    }
    else sib = sib->right();    /* else, try to right if zip below */
    goto keep_looking;
}

/* are two trees exactly alike? */
int PCCTS_AST::
match(PCCTS_AST *u)
{
    PCCTS_AST *t = this;
    PCCTS_AST *sib;

    if ( u==NULL ) return 0;

    for (sib=t; sib!=NULL&&u!=NULL; sib=sib->right(), u=u->right())
    {
        if ( sib->type() != u->type() ) return 0;
        if ( sib->down()!=NULL )
            if ( !sib->down()->match(u->down()) ) return 0;
    }
    return 1;
}

/* Is 'u' a subtree of 't' beginning at the root? */
int PCCTS_AST::
match_partial(PCCTS_AST *t, PCCTS_AST *u)
{
    PCCTS_AST *sib;

    if ( u==NULL ) return 1;
    if ( t==NULL ) return 0; /* MR23 removed unreachable code */

    for (sib=t; sib!=NULL&&u!=NULL; sib=sib->right(), u=u->right())
    {
        if ( sib->type() != u->type() ) return 0;
        if ( sib->down()!=NULL )
            if ( !match_partial(sib->down(), u->down()) ) return 0;
    }
    return 1;
}

#ifdef _MSC_VER  // MR23
//Turn off "unreachable code" warning
#pragma warning(disable : 4702)
#endif
/* Walk the template tree 't' (matching against 'this'), filling in the
 * 'labels' array, and setting 'n' according to how many labels were matched.
 */
int PCCTS_AST::
scanmatch(ScanAST *t, PCCTS_AST **labels[], int *n)
{
    ScanAST *sib;
    PCCTS_AST *u = this;

    if ( u==NULL ) return 0;

    for (sib=t; sib!=NULL&&u!=NULL; sib=sib->right(), u=u->right())
    {
        /* make sure tokens match; token of '0' means wildcard match */
        if ( sib->type() != u->type() && sib->type()!=0 ) return 0;
        /* we have a matched token here; set label pointers if exists */
        if ( sib->label_num>0 )
        {
            require(labels!=NULL, "label found in template, but no array of labels");
            (*n)++;
            *(labels[sib->label_num-1]) = u;
        }
        /* match what's below if something there and current node is not wildcard */
        if ( sib->down()!=NULL && sib->type()!=0 )
        {
            if ( sib->down()==NULL )
            {
                if ( u->down()!=NULL )
                    return 0;
                else
                    return 1;
            }
            if ( !u->down()->scanmatch(sib->down(), labels, n) ) return 0;
        }
    }
    return 1;
}
#ifdef _MSC_VER  // MR23
#pragma warning(default : 4702)
#endif

void PCCTS_AST::
insert_after(PCCTS_AST *b)
{
    PCCTS_AST *end;
    if ( b==NULL ) return;
    /* find end of b's child list */
    for (end=b; end->right()!=NULL; end=end->right()) {;}
    end->setRight(this->right());
    this->setRight(b);
}

void PCCTS_AST::
append(PCCTS_AST *b)
{
    PCCTS_AST *end;
    require(b!=NULL, "append: NULL input tree");
    /* find end of child list */
    for (end=this; end->right()!=NULL; end=end->right()) {;}
    end->setRight(b);
}

PCCTS_AST *PCCTS_AST::
tail()
{
    PCCTS_AST *end;
    /* find end of child list */
    for (end=this; end->right()!=NULL; end=end->right()) {;}
    return end;
}

PCCTS_AST *PCCTS_AST::
bottom()
{
    PCCTS_AST *end;
    /* find end of child list */
    for (end=this; end->down()!=NULL; end=end->down()) {;}
    return end;
}

PCCTS_AST *PCCTS_AST::
cut_between(PCCTS_AST *a, PCCTS_AST *b)
{
    PCCTS_AST *end, *ret;
    if (a==NULL||b==NULL) return NULL;
    /* find node pointing to b */
    for (end=a; end->right()!=NULL&&end->right()!=b; end=end->right())
        {;}
    if (end->right()==NULL) return NULL; //ast_cut_between: a,b not connected
    end->setRight(NULL);    /* don't want it point to 'b' anymore */
    ret = a->right();
    a->setRight(b);
    return ret;
}

#ifdef NOT_YET
SList *PCCTS_AST::
to_slist()
{
    SList *list = new SList;
    PCCTS_AST *p;

    for (p=this; p!=NULL; p=p->right())
    {
        list->add(p);
    }
    return list;
}
#endif

void PCCTS_AST::
tfree()
{
    PCCTS_AST *t = this;
    if ( t->down()!=NULL ) t->down()->tfree();
    if ( t->right()!=NULL ) t->right()->tfree();
    delete t;
}

int PCCTS_AST::
nsiblings()
{
    PCCTS_AST *t = this;
    int n=0;

    while ( t!=NULL )
    {
        n++;
        t = t->right();
    }
    return n;
}

PCCTS_AST *PCCTS_AST::
sibling_index(int i)
{
    PCCTS_AST *t = this;
    int j=1;
    require(i>0, "sibling_index: i<=0");

    while ( t!=NULL )
    {
        if ( j==i ) return t;
        j++;
        t = t->right();
    }
    return NULL;
}

/* Assume this is a root node of a tree--
 * duplicate that node and what's below; ignore siblings of root node.
 */

// MR9 23-Sep-97 RJV
// MR9
// MR9 RJV: Original version only duplicated the node and down elements.
// MR9      Made copies of the pointers to sibling.
// MR9      Changed call "down()->deepCopy()" to "down()->deepCopyBushy()"
// MR9

PCCTS_AST *PCCTS_AST::
deepCopy()
{
    PCCTS_AST *u = this->shallowCopy();
    if ( down()!=NULL ) u->setDown(down()->deepCopyBushy());
    u->setRight(NULL);
    return u;
}

/* Copy all nodes including siblings of root. */
PCCTS_AST *PCCTS_AST::
deepCopyBushy()
{
    PCCTS_AST *u = this->shallowCopy();
    /* copy the rest of the tree */
    if ( down()!=NULL ) u->setDown(down()->deepCopyBushy());
    if ( right()!=NULL ) u->setRight(right()->deepCopyBushy());
    return u;
}

void PCCTS_AST::
scanast_free(ScanAST *t)
{
    if ( t == NULL ) return;
    scanast_free( t->down() );
    scanast_free( t->right() );
    free( (char *) t );                         // MR1
}

/*
 * scan
 *
 * This function is like scanf(): it attempts to match a template
 * against an input tree.  A variable number of tree pointers
 * may be set according to the '%i' labels in the template string.
 * For example:
 *
 *   t->ast_scan("#( 6 #(5 %1:4 %2:3) #(1 %3:3 %4:3) )",
 *            &w, &x, &y, &z);
 *
 * Naturally, you'd want this converted from
 *
 *   t->ast_scan("#( RangeOp #(Minus %1:IConst %2:Var) #(Plus %3:Var %4Var) )",
 *            &w, &x, &y, &z);
 *
 * by SORCERER.
 *
 * This function call must be done withing a SORCERER file because SORCERER
 * must convert the token references to the associated token number.
 *
 * This functions parses the template and creates trees which are then
 * matched against the input tree.  The labels are set as they are
 * encountered; hence, partial matches may leave some pointers set
 * and some NULL.  This routines initializes all argument pointers to NULL
 * at the beginning.
 *
 * This function returns the number of labels matched.
 */
int PCCTS_AST::
ast_scan(char *templ, ...)
{
    va_list ap;
    ScanAST *tmpl;
    int n, i, found=0;
    PCCTS_AST ***label_ptrs=NULL;

    va_start(ap, templ);

    /* make a ScanAST tree out of the template */
    tmpl = stringparser_parse_scanast(templ, &n);

    /* make an array out of the labels */
    if ( n>0 )
    {
        label_ptrs = (PCCTS_AST ***) calloc(n, sizeof(PCCTS_AST **));
        require(label_ptrs!=NULL, "scan: out of memory");
        for (i=1; i<=n; i++)
        {
            label_ptrs[i-1] = va_arg(ap, PCCTS_AST **);
            *(label_ptrs[i-1]) = NULL;
        }
    }

    /* match the input tree against the template */
    scanmatch(tmpl, label_ptrs, &found);

    scanast_free(tmpl);
    free( (char *) label_ptrs);                 // MR1

    return found;
}

ScanAST *PCCTS_AST::
new_scanast(int tok)
{
    ScanAST *p = (ScanAST *) calloc(1, sizeof(ScanAST));
//
//  7-Apr-97 133MR1
//
    if ( p == NULL )
        panic("out of memory\n");           // MR23
    p->_token = tok;
    return p;
}

ScanAST *PCCTS_AST::
stringparser_parse_scanast(char *templ, int *num_labels)
{
    StringLexer lex;
    StringParser parser;
    ScanAST *t;

    stringlexer_init(&lex, templ);
    stringparser_init(&parser, &lex);
    t = stringparser_parse_tree(&parser);
    *num_labels = parser.num_labels;
    return t;
}

void PCCTS_AST::
stringparser_match(StringParser *parser, int token)
{
    if ( parser->token != token ) panic("bad tree in scan()");
}

/*
 * Match a tree of the form:
 *      (root child1 child2 ... childn)
 * or,
 *      node
 *
 * where the elements are integers or labeled integers.
 */
ScanAST *PCCTS_AST::
stringparser_parse_tree(StringParser *parser)
{
    ScanAST *t=NULL, *root, *child, *last=NULL /*MR23*/;

    if ( parser->token != __POUND )
    {
        return stringparser_parse_element(parser);
    }
    stringparser_match(parser,__POUND);
    parser->token = stringscan_gettok(parser->lexer);
    stringparser_match(parser,__LPAREN);
    parser->token = stringscan_gettok(parser->lexer);
    root = stringparser_parse_element(parser);
    while ( parser->token != __RPAREN )
    {
        child = stringparser_parse_element(parser);
        if ( t==NULL ) { t = child; last = t; }
        else { last->_right = child; last = child; }
    }
    stringparser_match(parser,__RPAREN);
    parser->token = stringscan_gettok(parser->lexer);
    root->_down = t;
    return root;
}

ScanAST *PCCTS_AST::
stringparser_parse_element(StringParser *parser)
{
    char ebuf[100];
    int label = 0;

    if ( parser->token == __POUND )
    {
        return stringparser_parse_tree(parser);
    }
    if ( parser->token == __PERCENT )
    {
        parser->token = stringscan_gettok(parser->lexer);
        stringparser_match(parser,__INT);
        label = atoi(parser->lexer->text);
        parser->num_labels++;
        if ( label==0 ) panic("%%0 is an invalid label");
        parser->token = stringscan_gettok(parser->lexer);
        stringparser_match(parser,__COLON);
        parser->token = stringscan_gettok(parser->lexer);
        /* can label tokens and wildcards */
        if ( parser->token != __INT && parser->token != __PERIOD )
            panic("can only label tokens");
    }
    if ( parser->token == __INT )
    {
        ScanAST *p = new_scanast(atoi(parser->lexer->text));
        parser->token = stringscan_gettok(parser->lexer);
        p->label_num = label;
        return p;
    }
    if ( parser->token == __PERIOD )
    {
        ScanAST *p = new_scanast(0);    /* token of 0 is wildcard */
        parser->token = stringscan_gettok(parser->lexer);
        p->label_num = label;
        return p;
    }
    sprintf(ebuf, "mismatch token in scan(): %s", scan_token_str(parser->token));
    panic(ebuf);
    return NULL;
}

void PCCTS_AST::
stringparser_init(StringParser *parser, StringLexer *input)
{
    parser->lexer = input;
    parser->token = stringscan_gettok(parser->lexer);
    parser->num_labels = 0;
}

void PCCTS_AST::
stringlexer_init(StringLexer *scanner, char *input)
{
    scanner->text[0]='\0';
    scanner->input = input;
    scanner->p = input;
    stringscan_advance(scanner);
}

void PCCTS_AST::
stringscan_advance(StringLexer *scanner)
{
    if ( *(scanner->p) == '\0' ) scanner->c = __StringScanEOF;
    scanner->c = *(scanner->p)++;
}

int PCCTS_AST::
stringscan_gettok(StringLexer *scanner)
{
    char *index = &scanner->text[0];
    char ebuf[100]; /* MR23 Remove static */

    while ( isspace(scanner->c) ) { stringscan_advance(scanner); }
    if ( isdigit(scanner->c) )
    {
        int tok = __INT;
        while ( isdigit(scanner->c) ) {
            *index++ = (char) /* static_cast<char> */ (scanner->c);     // MR23
            stringscan_advance(scanner);
        }
        *index = '\0';
        return tok;
    }
    switch ( scanner->c )
    {
        case '#' : stringscan_advance(scanner); return __POUND;
        case '(' : stringscan_advance(scanner); return __LPAREN;
        case ')' : stringscan_advance(scanner); return __RPAREN;
        case '%' : stringscan_advance(scanner); return __PERCENT;
        case ':' : stringscan_advance(scanner); return __COLON;
        case '.' : stringscan_advance(scanner); return __PERIOD;
        case '\0' : return __StringScanEOF;
        case __StringScanEOF : return __StringScanEOF;
        default  :
            sprintf(ebuf, "invalid char in scan: '%c'", scanner->c);
            panic(ebuf);
    }
    return __StringScanEOF; // never reached
}

const char *PCCTS_AST:: /* MR20 const */
scan_token_str(int t)
{
    if ( VALID_SCAN_TOKEN(t) ) return scan_token_tbl[t];
    else if ( t==__StringScanEOF ) return "<end-of-string>";
    else return "<invalid-token>";
}

//MR23
int PCCTS_AST::printMessage(FILE* pFile, const char* pFormat, ...)
{
    va_list marker;
    va_start( marker, pFormat );
    int iRet = vfprintf(pFile, pFormat, marker);
    va_end( marker );
    return iRet;
}