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 / VSLDef.C < prev    next >
C/C++ Source or Header  |  1998-11-23  |  11KB  |  500 lines
  1. // $Id: VSLDef.C,v 1.13 1998/11/23 17:43:41 zeller Exp $
  2. // VSL definition
  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 VSLDef_rcsid[] = 
  30.     "$Id: VSLDef.C,v 1.13 1998/11/23 17:43:41 zeller Exp $";
  31.  
  32. #ifdef __GNUG__
  33. #pragma implementation
  34. #endif
  35.  
  36.  
  37. #include <iostream.h>
  38. #include <strstream.h>
  39. #include <stdlib.h>
  40.  
  41. #include "assert.h"
  42. #include "hash.h"
  43.  
  44. #include "VSEFlags.h"
  45.  
  46. #include "VSLLib.h"
  47. #include "VSLDef.h"
  48. #include "VSLDefList.h"
  49. #include "VSLBuiltin.h"
  50.  
  51. #include "Box.h"
  52. #include "ListBox.h"
  53. #include "MatchBox.h"
  54.  
  55. #include "VSLNode.h"
  56. #include "ArgNode.h"
  57.  
  58. DEFINE_TYPE_INFO_0(VSLDef)
  59.  
  60. // VSLDef
  61.  
  62. // Constructor
  63. VSLDef::VSLDef(VSLDefList* l, VSLNode *pattern, VSLNode *e, 
  64.            string filename, int lineno)
  65.     : _expr(e),
  66.       _node_pattern(pattern),
  67.       _box_pattern(0),
  68.       _nargs(pattern->nargs()),
  69.       _straight(pattern->isStraight()),
  70.       _filename(filename),
  71.       _lineno(lineno),
  72.     _listnext(0), _libnext(0), _libprev(0),
  73.       being_compiled(false),
  74.       deflist(l)
  75. {}
  76.  
  77. // `Dummy' copy constructor
  78. VSLDef::VSLDef(const VSLDef&)
  79.     : _expr(0),
  80.       _node_pattern(0),
  81.       _box_pattern(0),
  82.       _nargs(0),
  83.       _straight(0),
  84.       _filename(),
  85.       _lineno(0),
  86.       _listnext(0), _libnext(0), _libprev(0),
  87.       being_compiled(false),
  88.       deflist(0)
  89. {
  90.     assert(0);
  91.     abort();
  92. }
  93.  
  94. // `Dummy' assignment
  95. VSLDef& VSLDef::operator = (const VSLDef&)
  96. {
  97.     assert(0);
  98.     return *this;
  99. }
  100.  
  101.  
  102. // Pattern matching
  103.  
  104. const int max_instances = 256;
  105.  
  106. // Pattern matching with nodes
  107.  
  108. static VSLNode *node_instances[max_instances];
  109.  
  110. static void node_matches(int data, const VSLNode *node)
  111. {
  112.     node_instances[data] = (VSLNode *)node;
  113. }
  114.  
  115. // Check if definition is conformant to argument ARG;
  116. // store matched values from arg in node_instances
  117. bool VSLDef::matches(const VSLNode *arg) const
  118. {
  119.     // While comparing, for all X, ArgNode == X holds.
  120.  
  121.     ArgNodeFunc oldCB = ArgNode::matchCallback;
  122.     ArgNode::matchCallback = node_matches;
  123.  
  124.     bool oldFlag = ArgNode::matchesAll;
  125.     ArgNode::matchesAll = true;
  126.     
  127.     if (VSEFlags::show_match_defs)
  128.     {
  129.     cout << "\nDef Match: " << longname() << " ? " << *arg;
  130.     cout.flush();
  131.     }
  132.  
  133.     bool ret = (*_node_pattern == *arg);
  134.  
  135.     if (VSEFlags::show_match_defs)
  136.     {
  137.     if (ret)
  138.         cout << "\nDef Match: " << longname() << " matches " << *arg;
  139.     else
  140.         cout << "\nDef Match: " << longname() << " does not match " 
  141.         << *arg;
  142.     cout.flush();
  143.     }
  144.  
  145.     ArgNode::matchCallback = oldCB;
  146.     ArgNode::matchesAll = oldFlag;
  147.  
  148.     return ret;
  149. }
  150.  
  151. // Return nodes matched against A
  152. VSLNode **VSLDef::nodelist(const VSLNode *arg) const
  153. {
  154.     for (unsigned i = 0; i < nargs(); i++)
  155.     node_instances[i] = 0;
  156.  
  157.     bool ok = matches(arg);
  158.     if (!ok)
  159.     return 0;
  160.  
  161.     return node_instances;
  162. }
  163.  
  164.  
  165.  
  166. // Pattern matching with boxes
  167.  
  168. static Box *box_instances[max_instances];
  169.  
  170. static void box_matches(int data, const Box *box)
  171. {
  172.     box_instances[data] = (Box *)box;
  173. }
  174.  
  175. // Check if definition is conformant to argument ARG;
  176. // store matched values from arg in box_instances
  177. bool VSLDef::matches(const Box *arg) const
  178. {
  179.     bool ret = false;
  180.  
  181.     // While comparing, for all X, MatchBox == X holds.
  182.  
  183.     MatchBoxFunc oldCB = MatchBox::matchCallback;
  184.     MatchBox::matchCallback = box_matches;
  185.  
  186.     MatchBox::matchesAll = true;
  187.  
  188.     if (VSEFlags::show_match_defs)
  189.     {
  190.     cout << "\nDef Match: " << longname() << " ? " << *arg;
  191.     cout.flush();
  192.     }
  193.  
  194.     if (_box_pattern == 0)
  195.     compilePattern();
  196.  
  197.     if (_box_pattern)
  198.     ret = (*_box_pattern == *arg);
  199.  
  200.     if (VSEFlags::show_match_defs)
  201.     {
  202.     if (ret)
  203.         cout << "\nDef Match: " << longname() << " matches " << *arg;
  204.     else
  205.         cout << "\nDef Match: " << longname() << " does not match " 
  206.         << *arg;
  207.     cout.flush();
  208.     }
  209.  
  210.     MatchBox::matchesAll = false;
  211.  
  212.     MatchBox::matchCallback = oldCB;
  213.     return ret;
  214. }
  215.  
  216.  
  217. // Convert node_pattern into box_pattern
  218. void VSLDef::compilePattern() const
  219. {
  220.     // Protect against patterns like f(f(a)) = ...
  221.     if (being_compiled)
  222.     {
  223.     VSLLib::eval_error("recursive pattern", this);
  224.     return;
  225.     }
  226.  
  227.     uncompilePattern();
  228.  
  229.     // Use a list of match boxes as argument
  230.     ListBox *list = new ListBox;
  231.     unsigned i;
  232.     for (i = 0; i < nargs(); i++)
  233.     {
  234.     MatchBox *m = new MatchBox(i);
  235.     (*list) += m;
  236.     m->unlink();
  237.     }
  238.  
  239.     ((VSLDef *)this)->being_compiled = true;
  240.     const Box *result = _node_pattern->eval(list);
  241.     ((VSLDef *)this)->being_compiled = false;
  242.  
  243.     list->unlink();
  244.  
  245.     // Check if valid
  246.     if (result == 0)
  247.     VSLLib::eval_error("cannot evaluate pattern", this);
  248.     else
  249.     {
  250.     // Each MatchBox must be used exactly once
  251.     int *instances = new int [nargs()];
  252.     for (i = 0; i < nargs(); i++)
  253.         instances[i] = 0;
  254.     result->countMatchBoxes(instances);
  255.  
  256.     for (i = 0; i < nargs(); i++)
  257.     {
  258.         if (instances[i] == 0)
  259.         {
  260.         ostrstream os;
  261.         os << "invalid pattern: arg" << i 
  262.            << " is never instantiated";
  263.         VSLLib::eval_error(os, this);
  264.         }
  265.         if (instances[i] > 1)
  266.         {
  267.         ostrstream os;
  268.         os << "invalid pattern: arg" << i 
  269.            << " is instantiated several times";
  270.         VSLLib::eval_error(os, this);
  271.         }
  272.     }
  273.     delete[] instances;
  274.     }
  275.  
  276.     ((VSLDef *)this)->_box_pattern = (Box *)result;
  277. }
  278.  
  279.  
  280.  
  281. // Evaluation
  282.  
  283. // Backtrace
  284.  
  285. const VSLDef **VSLDef::backtrace = 0; 
  286. const Box **VSLDef::backtrace_args = 0;
  287. // (doesn't work without initializing --  why?)
  288.  
  289. // Evaluate def
  290. const Box *VSLDef::eval(Box *arg) const
  291. {
  292.     static int depth = 0;
  293.  
  294.     // Create backtrace
  295.     if (backtrace == 0)
  296.     {
  297.     backtrace = new const VSLDef *[VSEFlags::max_eval_nesting + 2];
  298.     backtrace_args = new const Box *[VSEFlags::max_eval_nesting + 2];
  299.     }
  300.  
  301.     backtrace[depth] = this;
  302.     backtrace_args[depth] = arg->link();
  303.     backtrace[depth + 1] = 0;   // End marker
  304.  
  305.     // Debugging
  306.     if (VSEFlags::show_large_eval)
  307.     {
  308.     cout << "\n" << depth << " ";
  309.     for (int i = 0; i < depth; i++)
  310.         cout << "  ";
  311.  
  312.     cout << longname() << *arg << ":";
  313.     cout.flush();
  314.     }
  315.  
  316.     // Actual function
  317.     const Box *box = 0;
  318.  
  319.     if (depth < VSEFlags::max_eval_nesting)
  320.     {
  321.     ListBox *myarglist = arglist(arg);
  322.  
  323.     if (myarglist)
  324.     {
  325.         depth++;
  326.         if (_expr)
  327.         box = _expr->eval(myarglist);
  328.         else
  329.         VSLLib::eval_error("undefined function");
  330.         depth--;
  331.  
  332.         myarglist->unlink();
  333.     }
  334.     else
  335.         VSLLib::eval_error("invalid argument");
  336.     }
  337.     else
  338.     VSLLib::eval_error("infinite recursion");
  339.  
  340.     // Debugging
  341.     if (VSEFlags::show_large_eval)
  342.     {
  343.     cout << "\n" << depth << " ";
  344.     for (int i = 0; i < depth; i++)
  345.         cout << "  ";
  346.  
  347.     cout << longname() << *arg;
  348.  
  349.     if (box == 0)
  350.         cout << " FAILS";
  351.     else
  352.         cout << " = " << *box;
  353.  
  354.     cout.flush();
  355.     }
  356.  
  357.     // Delete backtrace
  358.     backtrace[depth] = 0;
  359.     ((Box *)backtrace_args[depth])->unlink();
  360.  
  361.     return box;
  362. }
  363.  
  364. // Convert argument list into a format suitable for ArgNode instances.
  365. ListBox *VSLDef::arglist(const Box *arg) const
  366. {
  367.     if (straight())
  368.     {
  369.     assert (arg->isListBox());
  370.     return (ListBox *)((Box *)arg)->link();
  371.     }
  372.  
  373.     unsigned i;
  374.     for (i = 0; i < nargs(); i++)
  375.     box_instances[i] = 0;
  376.  
  377.     bool ok = matches(arg);
  378.     if (!ok)
  379.     return (ListBox *)0;
  380.  
  381.     ListBox *list = new ListBox;
  382.     for (i = 0; i < nargs(); i++)
  383.     {
  384.     assert(box_instances[i] != 0);  // cannot isolate arg
  385.     (*list) += box_instances[i];
  386.     }
  387.  
  388.     return list;
  389. }
  390.  
  391.  
  392.  
  393. // Resolve function names
  394. int VSLDef::resolveNames()
  395. {
  396.     // Apply to body
  397.     int changes = expr()->resolveNames(this, nargs());
  398.  
  399.     // Now replace all NameNodes in the pattern by equivalent ArgNodes.
  400.     string s = "";
  401.     unsigned offset = 0;
  402.  
  403.     while ((s = node_pattern()->firstName(), s) != "")
  404.     {
  405.     // Replace in body
  406.     int ch = expr()->resolveName(this, &expr(), s, offset);
  407.     if (ch == 0)
  408.         VSLLib::eval_warning("`" + s + "' unused", this);
  409.     changes += ch;
  410.  
  411.     // Replace in pattern
  412.     ch = node_pattern()->resolveName(this, &node_pattern(), s, offset);
  413.     assert(ch > 0);
  414.     if (ch > 1)
  415.         VSLLib::eval_error("`" + s + "' used several times", this);
  416.  
  417.     offset += ch;
  418.     }
  419.  
  420.     assert(offset == nargs());
  421.  
  422.     // Remove remaining NameNodes (replace them by arg0)
  423.     while ((s = expr()->firstName(), s) != "")
  424.     {
  425.     VSLLib::eval_error("`" + s + "' undefined", this);
  426.     expr()->resolveName(this, &expr(), s, 0);
  427.     }
  428.  
  429.     return changes;
  430. }
  431.  
  432.  
  433. // Resources
  434.  
  435. // Create function args (for error messages, etc.)
  436. string VSLDef::args() const
  437. {
  438.     // Konstant: has no arg
  439.     if ((deflist->func_name())[0] == '#')
  440.     return string("");
  441.  
  442.     ostrstream os;
  443.  
  444.     if (_node_pattern->isArgNode())
  445.     os << "(" << *_node_pattern << "...)";
  446.     else
  447.     os << *_node_pattern;
  448.  
  449.     return os;
  450. }
  451.  
  452. // Internal function name
  453. string VSLDef::func_name() const
  454. {
  455.     return deflist->func_name() + args();
  456. }
  457.  
  458. // External function name
  459. string VSLDef::f_name() const
  460. {
  461.     return deflist->f_name() + args();
  462. }
  463.  
  464. // External function name, including location
  465. string VSLDef::longname() const
  466. {
  467.     ostrstream os;
  468.     ostream& s = os;
  469.     
  470.     if (_filename != "")
  471.     s << _filename << ":" << _lineno << ": ";
  472.     s << f_name();
  473.  
  474.     return os;
  475. }
  476.  
  477. // Delete definition *and all successors*
  478. VSLDef::~VSLDef()
  479. {
  480.     if (_listnext)      delete _listnext;
  481.     if (_expr)          delete _expr;
  482.     if (_node_pattern)  delete _node_pattern;
  483.     if (_box_pattern)   _box_pattern->unlink();
  484. }
  485.  
  486. // Representation invariant (*without* successors)
  487. bool VSLDef::OK() const
  488. {
  489.     // Check expressions
  490.     assert (_expr == 0 || _expr->OK());
  491.     assert (_node_pattern && _node_pattern->OK());
  492.     assert (_box_pattern == 0 || _box_pattern->OK());
  493.  
  494.     // Check pointers to successor and predecessor
  495.     assert (libnext() == 0 || libnext()->libprev() == this);
  496.     assert (libprev() == 0 || libprev()->libnext() == this);
  497.  
  498.     return true;
  499. }
  500.