WhereCircuit.cpp

Go to the documentation of this file.

/**
 * @file WhereCircuit.cpp
 * @brief WhereCircuit method implementations and where-provenance evaluation.
 *
 * Implements:
 * - Gate creation methods: @c setGate(), @c setGateInput(),
 *   @c setGateProjection(), @c setGateEquality().
 * - @c toString(): human-readable gate representation for debugging.
 * - @c evaluate(): recursive DFS that computes the set of @c Locator
 *   values for each output column position, propagating provenance
 *   through TIMES (Cartesian product), PLUS (union), PROJECT
 *   (column selection), and EQ (equijoin merging) gates.
 * - @c WhereCircuit::Locator::operator<() and @c toString().
 */
#include "WhereCircuit.h"
 
extern "C" {
#include "provsql_utils.h"
#include <unistd.h>
}
 
#include <cassert>
#include <string>
#include <fstream>
#include <sstream>
#include <cstdlib>
 
using namespace std;
 
gate_t WhereCircuit::setGate(const uuid &u, WhereGate type)
{
  return Circuit::setGate(u, type);
}
 
gate_t WhereCircuit::setGateProjection(const uuid &u, vector<int> &&infos)
{
  auto id = setGate(u, WhereGate::PROJECT);
  projection_info[id]=infos;
  return id;
}
 
gate_t WhereCircuit::setGateEquality(const uuid &u, int pos1, int pos2)
{
  auto id = setGate(u, WhereGate::EQ);
  equality_info[id]=make_pair(pos1,pos2);
  return id;
}
 
gate_t WhereCircuit::setGateInput(const uuid &u, string table, int nb_columns)
{
  auto id = setGate(u, WhereGate::IN);
  input_token[id]=u;
  input_info[id]=make_pair(table, nb_columns);
  return id;
}
 
string WhereCircuit::toString(gate_t g) const
{
  return toStringHelper(g, WhereGate::UNDETERMINED);
}
 
string WhereCircuit::toStringHelper(gate_t g, WhereGate parent) const
{
  std::string op;
  string result;
  auto gtype = getGateType(g);
 
  switch(gtype) {
  case WhereGate::IN:
    return input_info.find(g)->second.first+":"+to_string(input_info.find(g)->second.second)+":"+input_token.find(g)->second;
  case WhereGate::UNDETERMINED:
    op="?";
    break;
  case WhereGate::TIMES:
    op="⊗";
    break;
  case WhereGate::PLUS:
    op="⊕";
    break;
  case WhereGate::PROJECT:
    op="Π[";
    {
      bool first=true;
      for(auto i : projection_info.find(g)->second) {
        if(!first)
          op+=",";
        op+=to_string(i);
        first=false;
      }
    }
    op+="]";
    break;
  case WhereGate::EQ:
    op="=["+to_string(equality_info.find(g)->second.first)+","+to_string(equality_info.find(g)->second.second)+"]";
  }
 
  for(auto s: getWires(g)) {
    if(gtype==WhereGate::PROJECT || gtype==WhereGate::EQ)
      result = op;
    else if(!result.empty())
      result+=" "+op+" ";
    result+=toStringHelper(s, gtype);
  }
 
  // Parenthesis elision (mirrors BooleanCircuit::toStringHelper):
  //   * single-wire TIMES/PLUS: drop the now-meaningless wrap.
  //   * root call (parent = UNDETERMINED): drop the outer wrap.
  //   * same-op nesting (parent == gtype, TIMES/PLUS only): associative.
  // PROJECT and EQ keep their parens so the prefix-bracketed shape
  // (e.g., @c =[i,j](...)) renders unambiguously inside a parent gate.
  bool single_join = (gtype==WhereGate::TIMES || gtype==WhereGate::PLUS)
                     && getWires(g).size()==1;
  bool same_op_assoc = (gtype==WhereGate::TIMES || gtype==WhereGate::PLUS)
                       && parent==gtype;
  if(single_join || parent==WhereGate::UNDETERMINED || same_op_assoc)
    return result;
  return "("+result+")";
}
 
vector<set<WhereCircuit::Locator> > WhereCircuit::evaluate(gate_t g) const
{
  vector<set<Locator> > v;
 
  switch(getGateType(g)) {
  case WhereGate::IN:
  {
    string table=input_info.find(g)->second.first;
    uuid tid=input_token.find(g)->second;
    int nb_columns=input_info.find(g)->second.second;
    for(int i=0; i<nb_columns; ++i) {
      set<Locator> s;
      s.insert(Locator(table,tid,i+1));
      v.push_back(s);
    }
  }
  break;
 
  case WhereGate::TIMES:
    if(getWires(g).empty())
      throw CircuitException("No wire connected to ⊗ gate");
 
    for(auto g2 : getWires(g)) {
      if(v.empty())
        v=evaluate(g2);
      else {
        vector<set<Locator> > w=evaluate(g2);
        v.insert(v.end(), w.begin(), w.end());
      }
    }
    break;
 
  case WhereGate::PLUS:
    if(getWires(g).empty())
      throw CircuitException("No wire connected to ⊕ gate");
 
    for(auto g2 : getWires(g)) {
      if(v.empty())
        v=evaluate(g2);
      else {
        vector<set<Locator> > w=evaluate(g2);
        if(w.size()!=v.size())
          throw CircuitException("Incompatible inputs for ⊕ gate");
 
        for(size_t k=0; k<v.size(); ++k) {
          v[k].insert(w[k].begin(), w[k].end());
        }
      }
    }
    break;
 
  case WhereGate::PROJECT:
    if(getWires(g).size()!=1)
      throw CircuitException("Not exactly one wire connected to Π gate");
 
    {
      vector<set<Locator> > w=evaluate(*getWires(g).begin());
      vector<int> positions=projection_info.find(g)->second;
      for(auto i : positions) {
        if(i==0 || i>(int)w.size())
          v.push_back(set<Locator>());
        else
          v.push_back(w[i-1]);
      }
    }
    break;
 
  case WhereGate::EQ:
    if(getWires(g).size()!=1)
      throw CircuitException("Not exactly one wire connected to = gate");
 
    v=evaluate(*getWires(g).begin());
    {
      pair<int,int> positions=equality_info.find(g)->second;
      if(positions.first>=1 && positions.first<=(int)v.size() &&
         positions.second>=1 && positions.second<=(int)v.size()) {
        v[positions.first-1].insert(v[positions.second-1].begin(), v[positions.second-1].end());
        v[positions.second-1].insert(v[positions.first-1].begin(), v[positions.first-1].end());
      }
    }
    break;
 
  default:
    throw CircuitException("Gate type not supported by where-provenance");
  }
 
  return v;
}
 
bool WhereCircuit::Locator::operator<(WhereCircuit::Locator that) const
{
  if(this->table != that.table)
    return this->table < that.table;
  if(this->tid != that.tid)
    return this->tid < that.tid;
  return this->position < that.position;
}
 
std::string WhereCircuit::Locator::toString() const
{
  return table + ":" + tid + ":" +to_string(position);
}