home *** CD-ROM | disk | FTP | other *** search
/ PC World Komputer 1999 mARCH / PCWK3A99.iso / Linux / DDD331 / DDD-3_1_.000 / DDD-3_1_ / ddd-3.1.1 / ddd / LetNode.C < prev    next >
C/C++ Source or Header  |  1998-11-23  |  12KB  |  516 lines
  1. // $Id: LetNode.C,v 1.12 1998/11/23 17:43:27 zeller Exp $
  2. // LET..IN construct in VSL
  3.  
  4. // Copyright (C) 1995 Technische Universitaet Braunschweig, Germany.
  5. // Written by Andreas Zeller <zeller@ips.cs.tu-bs.de>.
  6. // 
  7. // This file is part of DDD.
  8. // 
  9. // DDD is free software; you can redistribute it and/or
  10. // modify it under the terms of the GNU General Public
  11. // License as published by the Free Software Foundation; either
  12. // version 2 of the License, or (at your option) any later version.
  13. // 
  14. // DDD is distributed in the hope that it will be useful,
  15. // but WITHOUT ANY WARRANTY; without even the implied warranty of
  16. // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
  17. // See the GNU General Public License for more details.
  18. // 
  19. // You should have received a copy of the GNU General Public
  20. // License along with DDD -- see the file COPYING.
  21. // If not, write to the Free Software Foundation, Inc.,
  22. // 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
  23. // 
  24. // DDD is the data display debugger.
  25. // For details, see the DDD World-Wide-Web page, 
  26. // `http://www.cs.tu-bs.de/softech/ddd/',
  27. // or send a mail to the DDD developers <ddd@ips.cs.tu-bs.de>.
  28.  
  29. char LetNode_rcsid[] = 
  30.     "$Id: LetNode.C,v 1.12 1998/11/23 17:43:27 zeller Exp $";
  31.  
  32. #ifdef __GNUG__
  33. #pragma implementation
  34. #endif
  35.  
  36.  
  37. #include "assert.h"
  38. #include <iostream.h>
  39. #include <strstream.h>
  40.  
  41. #include "VSLLib.h"
  42.  
  43. #include "VSLNode.h"
  44. #include "CallNode.h"
  45. #include "LetNode.h"
  46. #include "ArgNode.h"
  47. #include "VSLDef.h"
  48. #include "MatchBox.h"
  49. #include "ListBox.h"
  50. #include "VSEFlags.h"
  51.  
  52. DEFINE_TYPE_INFO_1(LetNode, CallNode)
  53. DEFINE_TYPE_INFO_1(WhereNode, LetNode)
  54.  
  55. // LetNode
  56.  
  57. // Dump Let
  58. void LetNode::dump(ostream& s) const
  59. {
  60.     s << "let " << *node_pattern() << " = "  << *args() 
  61.       << "\n  in " << *body();
  62. }
  63.  
  64. // Dump where
  65. void WhereNode::dump(ostream& s) const
  66. {
  67.     s << *body() 
  68.        << "\n  where " << *node_pattern() << " = " << *args();
  69. }
  70.  
  71.  
  72. // ...as tree
  73. void LetNode::_dumpTree(ostream& s) const
  74. {
  75.     node_pattern()->dumpTree(s);
  76.     s << ", ";
  77.     args()->dumpTree(s);
  78.     s << ", ";
  79.     body()->dumpTree(s);
  80. }
  81.  
  82.  
  83. // Evaluate
  84. const Box *LetNode::_eval(ListBox *arglst) const
  85. {
  86.     const Box *result = 0;
  87.  
  88.     if (arglst)
  89.     assert(int(_base) == arglst->length());
  90.  
  91.     // Create arguments for pattern
  92.     const Box *patternArgs = args()->eval(arglst);
  93.  
  94.     // Create new argument list
  95.     ListBox *moreArgs = arglist(patternArgs);
  96.  
  97.     if (moreArgs)
  98.     {
  99.     ListBox *attach = 0;
  100.  
  101.     // If needed, append new arg list to existing one
  102.     if (arglst && !(arglst->isEmpty()))
  103.     {
  104.         attach = arglst->cons(moreArgs);
  105.         moreArgs->unlink();
  106.         moreArgs = (ListBox *)arglst->link();
  107.     }
  108.  
  109.     result = body()->eval(moreArgs);
  110.     moreArgs->unlink();
  111.  
  112.     // Remove new arg list
  113.     if (attach)
  114.         arglst->uncons(attach);
  115.     }
  116.     else
  117.     VSLLib::eval_error("invalid arguments");
  118.  
  119.     ((Box *)patternArgs)->unlink();
  120.     return result;
  121. }
  122.  
  123.  
  124. // Pattern matching
  125.  
  126. const int max_instances = 256;    // Max number of args
  127.  
  128.  
  129. // Pattern matching with boxes
  130.  
  131. static Box *box_instances[max_instances];
  132.  
  133. static void box_matches(int data, const Box *box)
  134. {
  135.     box_instances[data] = (Box *)box;
  136. }
  137.  
  138. // Check if definition is conformant to argument A;
  139. // store matched values from arg in box_instances
  140. bool LetNode::domatch(const Box *a) const
  141. {
  142.     bool ret = false;
  143.  
  144.     // While comparing, for all X, MatchBox == X holds.
  145.  
  146.     MatchBoxFunc oldCB = MatchBox::matchCallback;
  147.     MatchBox::matchCallback = box_matches;
  148.  
  149.     MatchBox::matchesAll = true;
  150.  
  151.     if (_box_pattern == 0)
  152.     compilePatterns(0);
  153.  
  154.     if (_box_pattern)
  155.     ret = (*_box_pattern == *a);
  156.  
  157.     MatchBox::matchesAll = false;
  158.  
  159.     MatchBox::matchCallback = oldCB;
  160.     return ret;
  161. }
  162.  
  163.  
  164. // Pattern matching with nodes
  165.  
  166. static VSLNode *node_instances[max_instances];
  167.  
  168. // Check if definition is conformant to argument A;
  169. // store matched values from arg in node_instances
  170. static void node_matches(int data, const VSLNode *node)
  171. {
  172.     node_instances[data] = (VSLNode *)node;
  173. }
  174.  
  175. bool LetNode::domatch(const VSLNode *a) const
  176. {
  177.     // While comparing, for all X, ArgNode == X holds.
  178.  
  179.     ArgNodeFunc oldCB = ArgNode::matchCallback;
  180.     ArgNode::matchCallback = node_matches;
  181.  
  182.     bool oldFlag = ArgNode::matchesAll;
  183.     ArgNode::matchesAll = true;
  184.  
  185.     bool ret = (*_node_pattern == *a);
  186.  
  187.     ArgNode::matchCallback = oldCB;
  188.     ArgNode::matchesAll = oldFlag;
  189.  
  190.     return ret;
  191. }
  192.  
  193. // Return nodes matched against A
  194. VSLNode **LetNode::nodelist(const VSLNode *a) const
  195. {
  196.     for (unsigned i = _base; i < _base + _nargs; i++)
  197.     node_instances[i] = 0;
  198.  
  199.     bool ok = domatch(a);
  200.     if (!ok)
  201.     return 0;
  202.  
  203.     return node_instances;
  204. }
  205.  
  206.  
  207. // Convert argument list into a format suitable for ArgNode instances.
  208. ListBox* LetNode::arglist(const Box *a) const
  209. {
  210.     if (_straight)
  211.     {
  212.     assert (a->isListBox());
  213.     return (ListBox *)((Box *)a)->link();
  214.     }
  215.  
  216.     unsigned i;
  217.     for (i = _base; i < _base + _nargs; i++)
  218.     box_instances[i] = 0;
  219.  
  220.     bool ok = domatch(a);
  221.     if (!ok)
  222.     return (ListBox *)0;
  223.  
  224.     ListBox *list = new ListBox;
  225.     for (i = _base; i < _base + _nargs; i++)
  226.     {
  227.     assert(box_instances[i] != 0);  // cannot isolate arg
  228.     (*list) += box_instances[i];
  229.     }
  230.  
  231.     return list;
  232. }
  233.  
  234.  
  235. // Convert node_pattern into box_pattern
  236. void LetNode::compilePatterns(VSLDef *cdef) const
  237. {
  238.     // Compile args first
  239.     CallNode::compilePatterns(cdef);
  240.  
  241.     // Protect against patterns like f(f(a)) = ...
  242.     if (being_compiled)
  243.     {
  244.     VSLLib::eval_error("recursive pattern", cdef);
  245.     return;
  246.     }
  247.  
  248.     uncompilePatterns(cdef);
  249.  
  250.     // Use a list of match boxes as argument
  251.     ListBox *list = new ListBox;
  252.     unsigned i;
  253.     for (i = 0; i < _base + _nargs; i++)
  254.     {
  255.     MatchBox *m = new MatchBox(i);
  256.     (*list) += m;
  257.     m->unlink();
  258.     }
  259.  
  260.     ((LetNode *)this)->being_compiled = true;
  261.     const Box *result = node_pattern()->eval(list);
  262.     ((LetNode *)this)->being_compiled = false;
  263.  
  264.     list->unlink();
  265.  
  266.     // Check if valid
  267.     if (result == 0)
  268.     VSLLib::eval_error("cannot evaluate pattern", cdef);
  269.     else
  270.     {
  271.     // Each MatchBox must be used exactly once
  272.     int *instances = new int [_base + _nargs];
  273.     for (i = _base; i < _base + _nargs; i++)
  274.         instances[i] = 0;
  275.     result->countMatchBoxes(instances);
  276.  
  277.     for (i = _base; i < _base + _nargs; i++)
  278.     {
  279.         if (instances[i] == 0)
  280.         {
  281.         ostrstream os;
  282.         os << "invalid pattern: arg" << i << " is never instantiated";
  283.         VSLLib::eval_error(os);
  284.         }
  285.         if (instances[i] > 1)
  286.         {
  287.         ostrstream os;
  288.         os << "invalid pattern: arg" << i 
  289.            << " is instantiated several times";
  290.         VSLLib::eval_error(os);
  291.         }
  292.     }
  293.     delete[] instances;
  294.     }
  295.  
  296.     ((LetNode *)this)->_box_pattern = (Box *)result;
  297. }
  298.  
  299.  
  300.  
  301.  
  302.  
  303.  
  304. // Resolve function names
  305. int LetNode::_resolveNames(VSLDef *cdef, unsigned base)
  306. {
  307.     if (_nargs == 0)
  308.     VSLLib::eval_warning("pattern without variables", cdef);
  309.  
  310.     // First apply to body and pattern args
  311.     // Within body, increase the base: While evaluating the body,
  312.     // we have _nargs more variables.
  313.     int changes = 0;
  314.     
  315.     changes += args()->resolveNames(cdef, base);
  316.     changes += body()->resolveNames(cdef, base + _nargs);
  317.  
  318.     // Now replace all NameNodes in the pattern by equivalent ArgNodes.
  319.     string s = "";
  320.     unsigned offset = 0;
  321.  
  322.     while ((s = node_pattern()->firstName(), s) != "")
  323.     {
  324.     // Replace in body
  325.     int ch = body()->resolveName(cdef, &body(), s, base + offset);
  326.     if (ch == 0)
  327.         VSLLib::eval_warning("`" + s + "' is unused", cdef);
  328.     changes += ch;
  329.  
  330.     // Replace in pattern
  331.     ch = node_pattern()->resolveName(cdef, &node_pattern(), s, 
  332.         base + offset);
  333.     assert(ch > 0);
  334.     if (ch > 1)
  335.         VSLLib::eval_error("`" + s + "' is used several times", cdef);
  336.  
  337.     offset++;
  338.     }
  339.  
  340.     assert(offset == _nargs);
  341.  
  342.     return changes;
  343. }
  344.  
  345.  
  346. // Optimization
  347.  
  348. // inlineFuncs: Replace pattern vars by function body
  349. // Example: Replace `let a = 45 in a + a' by `45 + 45'
  350.  
  351. int LetNode::inlineFuncs(VSLDef *cdef, VSLNode **node)
  352. {
  353.     assert (this == *node);
  354.     int changes = 0;
  355.  
  356.     // Apply to all args
  357.     changes += CallNode::inlineFuncs(cdef, node);
  358.  
  359.     // Create instance list: abort if ambiguous
  360.     VSLNode **values = nodelist(args());
  361.     if (values == 0)
  362.     return changes;
  363.  
  364.     // Create instance counter
  365.     int *instances = new int [_base + _nargs];
  366.     unsigned i;
  367.     for (i = 0; i < _base + _nargs; i++)
  368.     instances[i] = 0;
  369.  
  370.     // Count how often the variables are used
  371.     body()->countArgNodes(cdef, instances, _base, _nargs);
  372.  
  373.     // Check if each instantiation is defined
  374.     bool fail = false;
  375.     for (i = _base; i < _base + _nargs; i++)
  376.     if (instances[i] > 0 && values[i] == 0)
  377.     {
  378.         ostrstream os;
  379.         os << "cannot isolate arg" << i;
  380.         VSLLib::eval_warning(os, cdef);
  381.         fail = true;
  382.     }
  383.  
  384.     // Each instance must be used only once (efficiency)
  385.     for (i = _base; i < _base + _nargs; i++)
  386.     if (values[i] && instances[i] > 1)
  387.     {
  388.         // However, if we replace an arg by a constant or another
  389.         // arg, the arg may be instantiated multiple times.
  390.  
  391.         if (!values[i]->isConstNode() && !values[i]->isArgNode())
  392.         fail = true;
  393.     }
  394.  
  395.     delete[] instances;
  396.  
  397.     if (fail)
  398.     return changes;
  399.  
  400.     // Now perform inlining.
  401.  
  402.     // Copy function body
  403.     VSLNode *newbody = body()->dup();
  404.  
  405.     // The arg nodes in BODY refer to EXPR; not to the function of
  406.     // this DefCallNode.  We must replace them by the arguments of
  407.     // this DefCallNode.
  408.  
  409.     newbody->instantiateArgs(cdef, &newbody, values, _base, _nargs);
  410.  
  411.  
  412.     // Remaining arg nides in BODY refer to LET constructs.  If the
  413.     // current funtion and NEWBODY have a different number of args,
  414.     // we'll get into trouble.  So, renumber the arg nodes.
  415.  
  416.     newbody->reBase(cdef, _base);
  417.  
  418.  
  419.     // Here's the actual replacement
  420.     *node = newbody;
  421.  
  422.     if (VSEFlags::show_optimize)
  423.     {
  424.     cout << "\n" << cdef->longname() << ": inlineFuncs: replacing\n"
  425.         << *this << "\nby " << **node << '\n';
  426.     cout.flush();
  427.     }
  428.  
  429.     delete this;
  430.  
  431.     return ++changes;
  432. }
  433.  
  434.  
  435. // Set a new base
  436. int LetNode::_reBase(VSLDef *cdef, unsigned newBase)
  437. {
  438.     int changes = 0;
  439.  
  440.     // Rename all LET variables: arg_i -> arg_(i + offset):
  441.     int offset = newBase - _base;
  442.  
  443.     if (offset == 0)
  444.     return changes;
  445.  
  446.     // Apply to pattern args
  447.     args()->reBase(cdef, newBase);
  448.  
  449.     // If offset > 0, rename in body first (to prevent collisions)
  450.     if (offset > 0)
  451.     changes = body()->reBase(cdef, newBase + _nargs);
  452.  
  453.     VSLNode **argnodes = new VSLNode *[_base + _nargs];
  454.     unsigned i;
  455.     for (i = 0; i < _base; i++)
  456.     argnodes[i] = 0;
  457.     for (i = _base; i < _base + _nargs; i++)
  458.     argnodes[i] = new ArgNode(i + offset);
  459.  
  460.     if (VSEFlags::show_optimize)
  461.     {
  462.     cout << "\n" << cdef->longname() << ": reBase: replacing\n" << *this;
  463.     cout.flush();
  464.     }
  465.  
  466.     // Rename vars in body
  467.     body()->instantiateArgs(cdef, &body(), argnodes, _base, _nargs);
  468.  
  469.     // Rename vars in pattern
  470.     node_pattern()->instantiateArgs(cdef, &node_pattern(), 
  471.     argnodes, _base, _nargs);
  472.  
  473.     if (VSEFlags::show_optimize)
  474.     {
  475.     cout << "\nby " << *this << "\n";
  476.     cout.flush();
  477.     }
  478.  
  479.     for (i = _base; i < _base + _nargs; i++)
  480.     delete argnodes[i];
  481.     delete[] argnodes;
  482.  
  483.     // If offset < 0, now rename vars in body
  484.     if (offset < 0)
  485.     changes = body()->reBase(cdef, newBase + _nargs);
  486.  
  487.     // Recompile pattern
  488.     _base = newBase;
  489.     compilePatterns(cdef);
  490.  
  491.     return ++changes;
  492. }
  493.  
  494.  
  495. // Debugging
  496.  
  497. // Representation invariant
  498. bool LetNode::OK() const
  499. {
  500.     EmptyListNode empty;
  501.  
  502.     assert (CallNode::OK());
  503.  
  504.     // Arg must be list of length 2
  505.     assert (arg() && arg()->isListNode());
  506.     assert (_args() && _args()->tail() && _args()->tail()->isListNode());
  507.     assert (_body() && _body()->tail() && *(_body()->tail()) == empty);
  508.  
  509.     // All list elems must exist
  510.     assert (args());
  511.     assert (body());
  512.     assert (node_pattern());
  513.  
  514.     return true;
  515. }
  516.