Initial check-in.

7 files changed, 546 insertions, 0 deletions

diff --git a/cells-impl.hpp b/cells-impl.hpp
new file mode 100644
index 0000000..893d51c
--- /dev/null
+++ b/cells-impl.hpp
@@ -0,0 +1,212 @@
+// Copyright 2012, Matthias Andreas Benkard.
+
+#pragma once
+
+#ifndef CELLS_IMPL_HPP
+#define CELLS_IMPL_HPP
+
+#include "cells.hpp"
+
+#include "dynvars.hpp"
+
+#include <exception>
+#include <stdexcept>
+#include <functional>
+#include <memory>
+#include <unordered_map>
+#include <unordered_set>
+#include <forward_list>
+#include <deque>
+
+#ifndef thread_local
+//#define thread_local __thread
+#define thread_local
+#endif
+
+namespace cells {
+  using std::cout;
+  using std::cerr;
+  using std::endl;
+
+  using namespace dynvars;
+
+  struct dag_node {
+    dag_node(std::shared_ptr<observer> item_) : item(item_) { }
+    std::shared_ptr<observer> item;
+    std::unordered_set<dag_node*> incoming_edges;
+    std::unordered_set<dag_node*> outgoing_edges;
+  };
+
+  struct transaction {
+    std::unordered_map<std::shared_ptr<observer>, std::shared_ptr<dag_node>> dag;
+  };
+
+  static thread_local dynvar<std::forward_list<std::shared_ptr<observer>>> current_dependencies;
+  static thread_local dynvar<transaction> current_transaction;
+
+  void observer::clear_dependencies() {
+    for (auto const& dep : dependencies) {
+      dep->remove_dependent(this);
+    }
+    dependencies = {};
+  }
+
+  void observer::add_dependent(std::shared_ptr<observer> dependent) {
+    dependents.push_front(dependent);
+  }
+
+  void observer::remove_dependent(observer* dependent) {
+    dependents.remove_if([&](std::weak_ptr<observer> const& other) -> bool {
+      std::shared_ptr<observer> other2 = other.lock();
+      // note: this should also work for empty other
+      return (other2.get() == dependent);
+    });
+  }
+  
+  void observer::reset_dependencies(std::forward_list<std::shared_ptr<observer>> const& newdeps) {
+    clear_dependencies();
+    dependencies = newdeps;
+    for (auto const& dep : newdeps) {
+      dep->add_dependent(shared_from_this());
+    }
+  }
+
+  void observer::mark() {
+    if (!current_transaction) {
+      with_transaction([&]() { this->mark(); });
+      return;
+    }
+    std::shared_ptr<observer> self = shared_from_this();
+    if (current_transaction->dag.find(self) ==
+        current_transaction->dag.end()) {
+      std::unordered_set<dag_node*> incoming_edges;
+      std::unordered_set<dag_node*> outgoing_edges;
+      std::shared_ptr<dag_node> node = std::make_shared<dag_node>(self);
+      current_transaction->dag[self] = std::shared_ptr<dag_node>(node);
+      for (std::weak_ptr<observer> x : dependents) {
+        std::shared_ptr<observer> px = x.lock();
+        if (px) {
+          px->mark();
+          std::shared_ptr<dag_node> xn = current_transaction->dag[px];
+          xn->incoming_edges.insert(node.get());
+          node->outgoing_edges.insert(xn.get());
+        }
+      }
+    }
+  }
+
+  observer::~observer() {
+    clear_dependencies();
+  }
+
+  template <typename T>
+  cell<T>::cell() {
+  }
+
+  template <typename T>
+  void cell<T>::update() {
+    T oldval = current_value;
+    with<std::forward_list<std::shared_ptr<observer>>, void>
+      (current_dependencies,
+       std::forward_list<std::shared_ptr<observer>>(),
+       [=]{
+        current_value = recompute(current_value);
+        reset_dependencies(*current_dependencies);
+      });
+  }
+
+  template <typename T>
+  T& cell<T>::get() {
+    if (current_dependencies) {
+      current_dependencies->push_front(shared_from_this());
+      return current_value;
+    } else {
+      return current_value;
+    }
+  }
+
+  template <typename T>
+  cell<T>::~cell() {
+  }
+
+  template <typename T>
+  T formula_cell<T>::recompute(T old) {
+    return alt_formula(old);
+  }
+
+  template <typename T>
+  T formula_cell<T>::init() {
+    return formula();
+  }
+
+  template <typename T>
+  void formula_cell<T>::reset(T value) {
+    this->alt_formula = ([=](T) { return value; });
+    this->formula     = ([=]()  { return value; });
+    this->mark();
+  }
+
+  template <typename T>
+  void formula_cell<T>::reset(std::function<T ()> formula) {
+    this->formula = formula;
+    this->alt_formula = ([=](T old) { return formula(); });
+    this->mark();
+  }
+
+  template <typename T>
+  void formula_cell<T>::reset(std::function<T ()> formula,
+                              std::function<T (T)> alt_formula) {
+    this->formula = formula;
+    this->alt_formula = alt_formula;
+    this->mark();
+  }
+
+  template <typename T>
+  formula_cell<T>::~formula_cell() {
+  }
+
+  void with_transaction(std::function<void ()> thunk) {
+    using std::cout;
+    using std::cerr;
+    using std::endl;
+    with<transaction, void>(current_transaction, transaction(), [&]() -> void {
+      //cerr << "; transaction." << endl;
+      thunk();
+
+      //cerr << "; affected nodes: " << current_transaction->dag.size() << endl;
+      std::deque<std::shared_ptr<observer>> nodes;
+
+      // topological sort
+      std::forward_list<dag_node*> independent_nodes;
+      auto left = current_transaction->dag.size();
+
+      for (auto const& o_and_n : current_transaction->dag) {
+        auto node = o_and_n.second;
+        if (node->incoming_edges.size() == 0) {
+          independent_nodes.push_front(node.get());
+        }
+      }
+      while (!independent_nodes.empty()) {
+        left--;
+        auto node = independent_nodes.front();
+        independent_nodes.pop_front();
+        nodes.push_back(node->item);
+        for (dag_node* other : node->outgoing_edges) {
+          other->incoming_edges.erase(node);
+          if (other->incoming_edges.size() == 0) {
+            independent_nodes.push_front(other);
+          }
+        }
+      }
+      if (left != 0) {
+        throw std::logic_error("Cell cycle detected");
+      }
+
+      for (auto const& node : nodes) {
+        node->update();
+      }
+    });
+  }
+}
+
+#endif //CELLS_IMPL_HPP
diff --git a/cells-test.cpp b/cells-test.cpp
new file mode 100644
index 0000000..6905054
--- /dev/null
+++ b/cells-test.cpp
@@ -0,0 +1,63 @@
+// Copyright 2012, Matthias Andreas Benkard.
+
+#include "cells.hpp"
+
+#include <memory>
+#include <iostream>
+
+struct unit { };
+
+using namespace cells;
+using std::cout;
+using std::endl;
+
+typedef formula_cell<double> fcell;
+typedef shared_ptr<fcell>    sfcell;
+typedef formula_cell<unit>   ucell;
+typedef shared_ptr<ucell>    sucell;
+
+int main(int argc, char** argv) {
+  sfcell x0 = fcell::make();
+  sfcell x1 = fcell::make();
+  sfcell x2 = fcell::make();
+  sfcell y = fcell::make();
+  sfcell z = fcell::make();
+  sucell a = ucell::make();
+  sucell b = ucell::make();
+
+  with_transaction([=](){
+    x0->reset(10);
+    x1->reset([=](){ return *x0 + 5; });
+    x2->reset([=](){ return *x0 * 2; });
+    y->reset([=](){ return *x1 * *x2; });
+    z->reset([=](){ return *x0 * *y; });
+    a->reset([=]() -> unit { cout << "z is now " << *z << "." << endl; return unit(); });
+    b->reset([=]() -> unit { cout << "x2 is now " << *x2 << "." << endl; return unit(); });
+  });
+
+  x0->reset(15);
+  x0->reset(-20);
+  y->reset(-3);
+  x1->reset([=]() { return (double)*x0; });
+  y->reset([=]() { return *x1 + *x2; });
+}
+
+
+/*
+ * z
+ * |\
+ * | \
+ * |  \
+ * |   \
+ * |    \
+ * |     \
+ * |      \
+ * |       y
+ * |      /|
+ * |     / |
+ * |    /  |
+ * |   x1  x2
+ * |  /    |
+ * | /     |
+ * x0------+
+ */
diff --git a/cells.hpp b/cells.hpp
new file mode 100644
index 0000000..27b3633
--- /dev/null
+++ b/cells.hpp
@@ -0,0 +1,87 @@
+// Copyright 2012, Matthias Andreas Benkard.
+
+#pragma once
+
+#ifndef CELLS_HPP
+#define CELLS_HPP
+
+#include <functional>
+#include <memory>
+#include <forward_list>
+#include <algorithm>
+
+namespace cells {
+
+  class observer : public virtual std::enable_shared_from_this<observer> {
+  private:
+    std::forward_list<std::weak_ptr<observer>> dependents;
+    std::forward_list<std::shared_ptr<observer>> dependencies;
+
+    void clear_dependencies();
+    void mark_dependents();
+
+  protected:
+    void mark();
+
+  public:
+    void add_dependent(std::shared_ptr<observer> dependent);
+    void remove_dependent(observer* dependent);
+    void reset_dependencies(std::forward_list<std::shared_ptr<observer>> const& newdeps);
+
+    virtual void update() = 0;
+
+    virtual ~observer();
+  };
+
+
+  template <typename T>
+  class cell : public observer {
+  private:
+    T current_value;
+
+  protected:
+    cell();
+    virtual void update();
+    virtual T recompute(T) = 0;
+    virtual T init() = 0;
+
+  public:
+    T& get();
+    T& operator *() { return get(); }
+    //T operator ()() { return get(); }
+    operator T() { return get(); }
+
+    virtual ~cell();
+  };
+
+
+  template <typename T>
+  class formula_cell : public cell<T> {
+    //friend class std::shared_ptr<formula_cell<T>>;
+    //friend std::shared_ptr<formula_cell<T>> std::make_shared<formula_cell<T>>();
+  private:
+    std::function<T ()> formula;
+    std::function<T (T old)> alt_formula;
+
+  protected:
+    formula_cell() { }
+    virtual T recompute(T);
+    virtual T init();
+
+  public:
+    //static std::shared_ptr<formula_cell<T>> make() { return std::make_shared<formula_cell<T>>(); }
+    static std::shared_ptr<formula_cell<T>> make() { return std::shared_ptr<formula_cell<T>>(new formula_cell()); }
+
+    void reset(T value);
+    void reset(std::function<T ()>);
+    void reset(std::function<T ()>, std::function<T (T old)>);
+
+    virtual ~formula_cell();
+  };
+
+  void with_transaction(std::function<void ()>);
+}
+
+#endif //CELLS_HPP
+
+#include "cells-impl.hpp"
diff --git a/dynvars-impl.hpp b/dynvars-impl.hpp
new file mode 100644
index 0000000..5890888
--- /dev/null
+++ b/dynvars-impl.hpp
@@ -0,0 +1,80 @@
+// Copyright 2012, Matthias Andreas Benkard.
+
+#pragma once
+
+#ifndef DYNVARS_IMPL_HPP
+#define DYNVARS_IMPL_HPP
+
+#include <cstdlib>
+#include <cstdio>
+#include <iostream>
+#include <functional>
+#include <memory>
+#include <future>
+#include <list>
+
+#include "dynvars.hpp"
+
+namespace dynvars {
+
+using namespace ::std;
+
+template <typename T>
+dynvar<T>::dynvar(T val) {
+  this->push(val);
+}
+
+template <typename T>
+dynvar<T>& dynvar<T>::operator =(T val) {
+  if (!value_stack.empty()) {
+    this->pop();
+  }
+  this->push(val);
+  return *this;
+}
+
+template <typename T>
+void dynvar<T>::push(T val) {
+  value_stack.push_front(val);
+}
+
+template <typename T>
+void dynvar<T>::pop() {
+  value_stack.pop_front();
+}
+
+template <typename T>
+dynvar<T>::operator bool() const {
+  return !value_stack.empty();
+}
+
+template <typename T>
+T& dynvar<T>::operator *() {
+  return value_stack.front();
+}
+
+template <typename T>
+T* dynvar<T>::operator ->() {
+  return &value_stack.front();
+}
+
+template <typename R>
+dyn<R>::dyn(dynvar<R>& var, R val) : myvar(var) {
+  myvar.push(val);
+}
+
+template <typename R>
+dyn<R>::~dyn() {
+  myvar.pop();
+}
+
+template <typename R, typename T>
+T
+with(dynvar<R>& var, R val, function<T ()> f) {
+  dyn<R> d_(var, val);
+  return f();
+}
+
+}
+
+#endif //DYNVARS_IMPL_HPP
diff --git a/dynvars-test.cpp b/dynvars-test.cpp
new file mode 100644
index 0000000..c80a7ca
--- /dev/null
+++ b/dynvars-test.cpp
@@ -0,0 +1,39 @@
+#include <cstdlib>
+#include <cstdio>
+#include <iostream>
+#include <functional>
+#include <memory>
+#include <future>
+
+#include "dynvars.hpp"
+
+#include <boost/signals2.hpp>
+
+using namespace ::std;
+using namespace ::boost::signals2;
+using namespace ::dynvars;
+
+#define thread_local __thread
+thread_local dynvar<string> greetee;
+
+function<void ()>
+make_greeter(const string& greeting) {
+  return [=]() {
+    cout << greeting << " " << *greetee << "!" << endl;
+  };
+};
+
+int
+main(int argc, char **argv) {
+  greetee = "nobody";
+  signal<void ()> sig;
+
+  sig.connect(make_greeter("Hi"));
+
+  sig();
+  with<string, void>(greetee, "luser", [&](){ sig(); });
+  with<string, void>(greetee, "geek",  [&](){ sig(); });
+  sig();
+
+  return EXIT_SUCCESS;
+}
diff --git a/dynvars.hpp b/dynvars.hpp
new file mode 100644
index 0000000..fbe852a
--- /dev/null
+++ b/dynvars.hpp
@@ -0,0 +1,46 @@
+// Copyright 2012, Matthias Andreas Benkard.
+
+#pragma once
+
+#ifndef DYNVARS_HPP
+#define DYNVARS_HPP
+
+#include <functional>
+#include <list>
+
+#define thread_local __thread
+
+namespace dynvars {
+
+template <typename T>
+class dynvar {
+private:
+  std::list<T> value_stack;
+public:
+  dynvar() { };
+  dynvar(T val);
+  dynvar<T>& operator =(T val);
+  void push(T val);
+  void pop();
+  T& operator *();
+  T* operator ->();
+  operator bool() const;
+};
+
+template <typename R>
+class dyn {
+  dynvar<R>& myvar;
+public:
+  dyn(dynvar<R>& var, R val);
+  ~dyn();
+};
+
+template <typename R, typename T>
+T
+with(dynvar<R>& var, R val, std::function<T ()> f);
+
+}
+
+#endif  //DYNVARS_HPP
+
+#include "dynvars-impl.hpp"
diff --git a/makefile b/makefile
new file mode 100644
index 0000000..9848e0c
--- /dev/null
+++ b/makefile
@@ -0,0 +1,19 @@
+CXX = clang++
+CXXFLAGS = -g -O0 -stdlib=libc++ -std=c++11
+
+.PHONY: all clean distclean
+
+all: cells-test dynvars-test
+
+dynvars-test: dynvars-test.cpp dynvars.hpp dynvars-impl.hpp
+	$(CXX) $(CXXFLAGS) dynvars-test.cpp -o dynvars-test
+
+cells-test: cells-test.cpp dynvars.hpp dynvars-impl.hpp cells.hpp cells-impl.hpp
+	$(CXX) $(CXXFLAGS) cells-test.cpp   -o cells-test
+
+clean:
+	rm -f dynvars-test cells-test
+	rm -rf dynvars-test.dSYM cells-test.dSYM
+
+distclean: clean
+	rm -f *~