[pure-lang-svn] SF.net SVN: pure-lang:[453] pure/trunk

[<ag...@us...>]

Revision: 453
          http://pure-lang.svn.sourceforge.net/pure-lang/?rev=453&view=rev
Author:   agraef
Date:     2008-08-08 08:53:33 +0000 (Fri, 08 Aug 2008)

Log Message:
-----------
Rework FMap structure so that it can accommodate a forest of local environments.

Modified Paths:
--------------
    pure/trunk/interpreter.cc
    pure/trunk/interpreter.hh

Modified: pure/trunk/interpreter.cc
===================================================================
--- pure/trunk/interpreter.cc	2008-08-07 08:07:20 UTC (rev 452)
+++ pure/trunk/interpreter.cc	2008-08-08 08:53:33 UTC (rev 453)
@@ -1932,8 +1932,11 @@
 FMap& FMap::operator= (const FMap& f)
 {
   clear(); m.resize(f.m.size());
-  for (size_t i = 0, n = f.m.size(); i < n; i++) m[i] = new EnvMap(*f.m[i]);
-  idx = f.idx; return *this;
+  for (size_t i = 0, n = f.m.size(); i < n; i++)
+    m[i] = new EnvMap(*f.m[i]);
+  root = f.root; pred = f.pred; succ = f.succ;
+  idx = f.idx; lastidx = f.lastidx;
+  return *this;
 }
 
 void FMap::clear()
@@ -1948,9 +1951,69 @@
   for (set<Env*>::iterator it = e.begin(), end = e.end();
        it != end; it++)
     delete *it;
-  m.clear(); idx = 0;
+  m.clear(); root.clear(); pred.clear(); succ.clear();
+  idx = 0; lastidx = -1;
 }
 
+void FMap::next()
+{
+  assert(pred[idx] < 0);
+  if (succ[idx] >= 0)
+    idx = succ[idx];
+  else {
+    // create a new root
+    size_t n = root.size(), k = m.size();
+    root.resize(n+1);
+    m.resize(k+1); pred.resize(k+1); succ.resize(k+1);
+    root[n] = succ[idx] = k;
+    pred[k] = succ[k] = -1;
+    m[k] = new EnvMap;
+    idx = k;
+  }
+  lastidx = -1;
+}
+
+void FMap::select(size_t n)
+{
+  if (root.size() > 1) {
+    assert(n < root.size());
+    idx = root[n];
+  } else
+    idx = 0;
+  lastidx = -1;
+}
+
+void FMap::push()
+{
+  if (lastidx >= 0) {
+    assert(pred[lastidx] == idx);
+    if (succ[lastidx] >= 0)
+      idx = succ[lastidx];
+    else {
+      // create a new child, link from the previous one
+      size_t k = m.size();
+      m.resize(k+1); pred.resize(k+1); succ.resize(k+1);
+      pred[k] = idx; succ[k] = -1;
+      m[k] = new EnvMap(*m[idx]);
+      succ[lastidx] = k;
+      idx = k;
+    }
+  } else if (++idx >= (int32_t)m.size()) {
+    // the first child always immediately follows its parent
+    assert(idx == m.size());
+    m.resize(idx+1); pred.resize(idx+1); succ.resize(idx+1);
+    pred[idx] = idx-1; succ[idx] = -1;
+    m[idx] = new EnvMap(*m[idx-1]);
+  }
+  lastidx = -1;
+}
+
+void FMap::pop()
+{
+  assert(pred[idx] >= 0);
+  lastidx = idx; idx = pred[idx];
+}
+
 Env& Env::operator= (const Env& e)
 {
   if (f) {

Modified: pure/trunk/interpreter.hh
===================================================================
--- pure/trunk/interpreter.hh	2008-08-07 08:07:20 UTC (rev 452)
+++ pure/trunk/interpreter.hh	2008-08-08 08:53:33 UTC (rev 453)
@@ -88,22 +88,49 @@
 typedef map<int32_t,Env*> EnvMap;
 typedef pair<int32_t,uint8_t> xmap_key;
 
+/* Manage local function environments. The FMap structure is organized as a
+   forest with one root per rule and one child per 'with' clause. Each node of
+   the forest holds a map mapping function symbols to the corresponding
+   environments. Initially, there is just one root holding an empty map. New
+   roots can be added with 'next', new children with 'push'; 'pop' backs out
+   to the parent level.
+
+   Child nodes are initialized to a copy of its parent map, to which you can
+   then add any local bindings. After the structure has been built, you can
+   use 'first' to reposition the "cursor" so that it points to the first root
+   and then traverse the forest using the same sequence of calls to 'next',
+   'push' and 'pop'. The 'select' method can be used to position the cursor at
+   the given root. The 'act' method returns the current map.
+
+   Implementation: The forest is encoded as a collection of vectors: 'm' holds
+   the map for each node, 'root' the node number of each root, 'pred' the
+   parent link for each node, and 'succ' the link to the next sibling of each
+   node. A 'pred' value of -1 denotes a root node, in which case 'succ' points
+   to the next root (or contains -1 to indicate the last root). The 'idx'
+   member points to the current node, 'lastidx' to the most recently visited
+   child after a 'pop' operation (-1 otherwise). */
+
 struct FMap {
-  // manage local function environments
+  // map of each node
   vector<EnvMap*> m;
-  // current map index
-  size_t idx;
+  // vectors encoding the forest structure (see explanation above)
+  vector<int32_t> root, pred, succ;
+  // index of current node and most previously visited child
+  int32_t idx, lastidx;
   // constructor (create one empty map by default)
-  FMap() : m(1), idx(0) { m[0] = new EnvMap; }
+  FMap() : m(1), root(1, 0), pred(1, -1), succ(1, -1), idx(0), lastidx(-1)
+  { m[0] = new EnvMap; }
   // assignment
   FMap& operator= (const FMap& f);
-  // clear local environments
+  // clear
   void clear();
-  // set index to first, next and given map
-  void first() { idx = 0; }
-  void next()
-  { if (++idx >= m.size()) { m.resize(idx+1); m[idx] = new EnvMap; } }
-  void select(size_t n) { if (m.size() > 1) idx = n; }
+  // set index to first, next and given root node
+  void first() { idx = 0; lastidx = -1; }
+  void next();
+  void select(size_t n);
+  // set index to the parent or next child of the current node
+  void push();
+  void pop();
   // access the current map
   EnvMap& act() { return *m[idx]; }
 };


This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site.