PC World Komputer 1999 March/PCWK3A99.iso/Linux/DDD331/DDD-3_1_.000/DDD-3_1_/ddd-3.1.1/ddd/LetNode.C

C/C++ Source or Header | 1998-11-23 | 11.5 KB | 516 lines

// $Id: LetNode.C,v 1.12 1998/11/23 17:43:27 zeller Exp $
// LET..IN construct in VSL

// Copyright (C) 1995 Technische Universitaet Braunschweig, Germany.
// Written by Andreas Zeller <[e-mail]>.
//
// This file is part of DDD.
//
// DDD 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.
//
// DDD 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 DDD -- see the file COPYING.
// If not, write to the Free Software Foundation, Inc.,
// 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
//
// DDD is the data display debugger.
// For details, see the DDD World-Wide-Web page,
// `http://www.cs.tu-bs.de/softech/ddd/',
// or send a mail to the DDD developers <[e-mail]>.

char LetNode_rcsid[] =
    "$Id: LetNode.C,v 1.12 1998/11/23 17:43:27 zeller Exp $";

#ifdef __GNUG__
#pragma implementation
#endif


#include "assert.h"
#include <iostream.h>
#include <strstream.h>

#include "VSLLib.h"

#include "VSLNode.h"
#include "CallNode.h"
#include "LetNode.h"
#include "ArgNode.h"
#include "VSLDef.h"
#include "MatchBox.h"
#include "ListBox.h"
#include "VSEFlags.h"

DEFINE_TYPE_INFO_1(LetNode, CallNode)
DEFINE_TYPE_INFO_1(WhereNode, LetNode)

// LetNode

// Dump Let
void LetNode::dump(ostream& s) const
{
    s << "let " << *node_pattern() << " = "  << *args()
      << "\n  in " << *body();
}

// Dump where
void WhereNode::dump(ostream& s) const
{
    s << *body()
       << "\n  where " << *node_pattern() << " = " << *args();
}


// ...as tree
void LetNode::_dumpTree(ostream& s) const
{
    node_pattern()->dumpTree(s);
    s << ", ";
    args()->dumpTree(s);
    s << ", ";
    body()->dumpTree(s);
}


// Evaluate
const Box *LetNode::_eval(ListBox *arglst) const
{
    const Box *result = 0;

    if (arglst)
    assert(int(_base) == arglst->length());

    // Create arguments for pattern
    const Box *patternArgs = args()->eval(arglst);

    // Create new argument list
    ListBox *moreArgs = arglist(patternArgs);

    if (moreArgs)
    {
    ListBox *attach = 0;

    // If needed, append new arg list to existing one
    if (arglst && !(arglst->isEmpty()))
    {
        attach = arglst->cons(moreArgs);
        moreArgs->unlink();
        moreArgs = (ListBox *)arglst->link();
    }

    result = body()->eval(moreArgs);
    moreArgs->unlink();

    // Remove new arg list
    if (attach)
        arglst->uncons(attach);
    }
    else
    VSLLib::eval_error("invalid arguments");

    ((Box *)patternArgs)->unlink();
    return result;
}


// Pattern matching

const int max_instances = 256;    // Max number of args


// Pattern matching with boxes

static Box *box_instances[max_instances];

static void box_matches(int data, const Box *box)
{
    box_instances[data] = (Box *)box;
}

// Check if definition is conformant to argument A;
// store matched values from arg in box_instances
bool LetNode::domatch(const Box *a) const
{
    bool ret = false;

    // While comparing, for all X, MatchBox == X holds.

    MatchBoxFunc oldCB = MatchBox::matchCallback;
    MatchBox::matchCallback = box_matches;

    MatchBox::matchesAll = true;

    if (_box_pattern == 0)
    compilePatterns(0);

    if (_box_pattern)
    ret = (*_box_pattern == *a);

    MatchBox::matchesAll = false;

    MatchBox::matchCallback = oldCB;
    return ret;
}


// Pattern matching with nodes

static VSLNode *node_instances[max_instances];

// Check if definition is conformant to argument A;
// store matched values from arg in node_instances
static void node_matches(int data, const VSLNode *node)
{
    node_instances[data] = (VSLNode *)node;
}

bool LetNode::domatch(const VSLNode *a) const
{
    // While comparing, for all X, ArgNode == X holds.

    ArgNodeFunc oldCB = ArgNode::matchCallback;
    ArgNode::matchCallback = node_matches;

    bool oldFlag = ArgNode::matchesAll;
    ArgNode::matchesAll = true;

    bool ret = (*_node_pattern == *a);

    ArgNode::matchCallback = oldCB;
    ArgNode::matchesAll = oldFlag;

    return ret;
}

// Return nodes matched against A
VSLNode **LetNode::nodelist(const VSLNode *a) const
{
    for (unsigned i = _base; i < _base + _nargs; i++)
    node_instances[i] = 0;

    bool ok = domatch(a);
    if (!ok)
    return 0;

    return node_instances;
}


// Convert argument list into a format suitable for ArgNode instances.
ListBox* LetNode::arglist(const Box *a) const
{
    if (_straight)
    {
    assert (a->isListBox());
    return (ListBox *)((Box *)a)->link();
    }

    unsigned i;
    for (i = _base; i < _base + _nargs; i++)
    box_instances[i] = 0;

    bool ok = domatch(a);
    if (!ok)
    return (ListBox *)0;

    ListBox *list = new ListBox;
    for (i = _base; i < _base + _nargs; i++)
    {
    assert(box_instances[i] != 0);  // cannot isolate arg
    (*list) += box_instances[i];
    }

    return list;
}


// Convert node_pattern into box_pattern
void LetNode::compilePatterns(VSLDef *cdef) const
{
    // Compile args first
    CallNode::compilePatterns(cdef);

    // Protect against patterns like f(f(a)) = ...
    if (being_compiled)
    {
    VSLLib::eval_error("recursive pattern", cdef);
    return;
    }

    uncompilePatterns(cdef);

    // Use a list of match boxes as argument
    ListBox *list = new ListBox;
    unsigned i;
    for (i = 0; i < _base + _nargs; i++)
    {
    MatchBox *m = new MatchBox(i);
    (*list) += m;
    m->unlink();
    }

    ((LetNode *)this)->being_compiled = true;
    const Box *result = node_pattern()->eval(list);
    ((LetNode *)this)->being_compiled = false;

    list->unlink();

    // Check if valid
    if (result == 0)
    VSLLib::eval_error("cannot evaluate pattern", cdef);
    else
    {
    // Each MatchBox must be used exactly once
    int *instances = new int [_base + _nargs];
    for (i = _base; i < _base + _nargs; i++)
        instances[i] = 0;
    result->countMatchBoxes(instances);

    for (i = _base; i < _base + _nargs; i++)
    {
        if (instances[i] == 0)
        {
        ostrstream os;
        os << "invalid pattern: arg" << i << " is never instantiated";
        VSLLib::eval_error(os);
        }
        if (instances[i] > 1)
        {
        ostrstream os;
        os << "invalid pattern: arg" << i
           << " is instantiated several times";
        VSLLib::eval_error(os);
        }
    }
    delete[] instances;
    }

    ((LetNode *)this)->_box_pattern = (Box *)result;
}






// Resolve function names
int LetNode::_resolveNames(VSLDef *cdef, unsigned base)
{
    if (_nargs == 0)
    VSLLib::eval_warning("pattern without variables", cdef);

    // First apply to body and pattern args
    // Within body, increase the base: While evaluating the body,
    // we have _nargs more variables.
    int changes = 0;

    changes += args()->resolveNames(cdef, base);
    changes += body()->resolveNames(cdef, base + _nargs);

    // Now replace all NameNodes in the pattern by equivalent ArgNodes.
    string s = "";
    unsigned offset = 0;

    while ((s = node_pattern()->firstName(), s) != "")
    {
    // Replace in body
    int ch = body()->resolveName(cdef, &body(), s, base + offset);
    if (ch == 0)
        VSLLib::eval_warning("`" + s + "' is unused", cdef);
    changes += ch;

    // Replace in pattern
    ch = node_pattern()->resolveName(cdef, &node_pattern(), s,
        base + offset);
    assert(ch > 0);
    if (ch > 1)
        VSLLib::eval_error("`" + s + "' is used several times", cdef);

    offset++;
    }

    assert(offset == _nargs);

    return changes;
}


// Optimization

// inlineFuncs: Replace pattern vars by function body
// Example: Replace `let a = 45 in a + a' by `45 + 45'

int LetNode::inlineFuncs(VSLDef *cdef, VSLNode **node)
{
    assert (this == *node);
    int changes = 0;

    // Apply to all args
    changes += CallNode::inlineFuncs(cdef, node);

    // Create instance list: abort if ambiguous
    VSLNode **values = nodelist(args());
    if (values == 0)
    return changes;

    // Create instance counter
    int *instances = new int [_base + _nargs];
    unsigned i;
    for (i = 0; i < _base + _nargs; i++)
    instances[i] = 0;

    // Count how often the variables are used
    body()->countArgNodes(cdef, instances, _base, _nargs);

    // Check if each instantiation is defined
    bool fail = false;
    for (i = _base; i < _base + _nargs; i++)
    if (instances[i] > 0 && values[i] == 0)
    {
        ostrstream os;
        os << "cannot isolate arg" << i;
        VSLLib::eval_warning(os, cdef);
        fail = true;
    }

    // Each instance must be used only once (efficiency)
    for (i = _base; i < _base + _nargs; i++)
    if (values[i] && instances[i] > 1)
    {
        // However, if we replace an arg by a constant or another
        // arg, the arg may be instantiated multiple times.

        if (!values[i]->isConstNode() && !values[i]->isArgNode())
        fail = true;
    }

    delete[] instances;

    if (fail)
    return changes;

    // Now perform inlining.

    // Copy function body
    VSLNode *newbody = body()->dup();

    // The arg nodes in BODY refer to EXPR; not to the function of
    // this DefCallNode.  We must replace them by the arguments of
    // this DefCallNode.

    newbody->instantiateArgs(cdef, &newbody, values, _base, _nargs);


    // Remaining arg nides in BODY refer to LET constructs.  If the
    // current funtion and NEWBODY have a different number of args,
    // we'll get into trouble.  So, renumber the arg nodes.

    newbody->reBase(cdef, _base);


    // Here's the actual replacement
    *node = newbody;

    if (VSEFlags::show_optimize)
    {
    cout << "\n" << cdef->longname() << ": inlineFuncs: replacing\n"
        << *this << "\nby " << **node << '\n';
    cout.flush();
    }

    delete this;

    return ++changes;
}


// Set a new base
int LetNode::_reBase(VSLDef *cdef, unsigned newBase)
{
    int changes = 0;

    // Rename all LET variables: arg_i -> arg_(i + offset):
    int offset = newBase - _base;

    if (offset == 0)
    return changes;

    // Apply to pattern args
    args()->reBase(cdef, newBase);

    // If offset > 0, rename in body first (to prevent collisions)
    if (offset > 0)
    changes = body()->reBase(cdef, newBase + _nargs);

    VSLNode **argnodes = new VSLNode *[_base + _nargs];
    unsigned i;
    for (i = 0; i < _base; i++)
    argnodes[i] = 0;
    for (i = _base; i < _base + _nargs; i++)
    argnodes[i] = new ArgNode(i + offset);

    if (VSEFlags::show_optimize)
    {
    cout << "\n" << cdef->longname() << ": reBase: replacing\n" << *this;
    cout.flush();
    }

    // Rename vars in body
    body()->instantiateArgs(cdef, &body(), argnodes, _base, _nargs);

    // Rename vars in pattern
    node_pattern()->instantiateArgs(cdef, &node_pattern(),
    argnodes, _base, _nargs);

    if (VSEFlags::show_optimize)
    {
    cout << "\nby " << *this << "\n";
    cout.flush();
    }

    for (i = _base; i < _base + _nargs; i++)
    delete argnodes[i];
    delete[] argnodes;

    // If offset < 0, now rename vars in body
    if (offset < 0)
    changes = body()->reBase(cdef, newBase + _nargs);

    // Recompile pattern
    _base = newBase;
    compilePatterns(cdef);

    return ++changes;
}


// Debugging

// Representation invariant
bool LetNode::OK() const
{
    EmptyListNode empty;

    assert (CallNode::OK());

    // Arg must be list of length 2
    assert (arg() && arg()->isListNode());
    assert (_args() && _args()->tail() && _args()->tail()->isListNode());
    assert (_body() && _body()->tail() && *(_body()->tail()) == empty);

    // All list elems must exist
    assert (args());
    assert (body());
    assert (node_pattern());

    return true;
}