1 files changed, 46 insertions, 0 deletions

diff --git a/tree.cpp b/tree.cpp
index 8d677db..a259e9b 100644
--- a/tree.cpp
+++ b/tree.cpp
@@ -11,6 +11,8 @@ int uniqid(){
 }
 
 
+Variable::Variable(int id):id(id){}
+
 bool Variable::isOperator() const {
 	return id==0;
 }
@@ -167,6 +169,15 @@ Tree::Node* Tree::Node::apply(const Assign &as) const {
 	return n;
 }
 
+void Tree::Node::collectTemporaries(unordered_set<Variable> &accum) const {
+	if(v.isOperator()){
+		left->collectTemporaries(accum);
+		right->collectTemporaries(accum);
+	} else {
+		accum.insert(v);
+	}
+}
+
 int Tree::Node::nleaves() const {
 	if(v.isOperator()){
 		return left->nleaves()+right->nleaves();
@@ -175,6 +186,11 @@ int Tree::Node::nleaves() const {
 	}
 }
 
+int Tree::Node::height() const {
+	if(v.isOperator())return max(left->height(),right->height());
+	else return 1;
+}
+
 int Tree::Node::compare(const Node &other) const {
 	if(v.isTemp()&&other.v.isTemp())return 0;
 	if(v<other.v)return -1;
@@ -283,9 +299,27 @@ bool Tree::matches(const Tree &pat) const {
 	}
 }
 
+void Tree::refreshUnassigned(const Tree &repl,Assign &as) const {
+	unordered_set<Variable> temps=repl.collectTemporaries();
+	// cerr<<"rU:"<<endl;
+	for(Variable v : temps){
+		// cerr<<"  v = "<<v<<endl;
+		if(v.isTemp()&&as.find(v)==as.end()){
+			int id=uniqid();
+			as.emplace(v,Node(id));
+			// cerr<<"  emplace("<<v<<","<<Node(id)<<")"<<endl;
+		}
+	}
+}
+
 void Tree::replace(Node *subj,const Tree &pat,const Tree &repl,vector<Tree> &accum){
 	Assign *as=subj->match(*pat.root);
 	if(as){
+		refreshUnassigned(repl,*as);
+		cerr<<"replace("<<*subj<<","<<pat<<","<<repl<<"); as:"<<endl;
+		for(const pair<Variable,Node> &p : *as){
+			cerr<<"  "<<p.first<<" -> "<<p.second<<endl;
+		}
 		Node *res=repl.root->apply(*as);
 		Node backup=*subj;
 		*subj=*res;
@@ -307,11 +341,23 @@ vector<Tree> Tree::replace(const Tree &pat,const Tree &repl){
 	return res;
 }
 
+unordered_set<Variable> Tree::collectTemporaries() const {
+	assert(root);
+	unordered_set<Variable> temps;
+	root->collectTemporaries(temps);
+	return temps;
+}
+
 int Tree::nleaves() const {
 	assert(root);
 	return root->nleaves();
 }
 
+int Tree::height() const {
+	assert(root);
+	return root->height();
+}
+
 int Tree::compare(const Tree &other) const {
 	assert(root&&other.root);
 	return root->compare(*other.root);