<p> // (c) 2008 David Roberts 

// TODO:
//   - support for multiple rules matching goal
//   - support for relation as a variable
//   - raise error if goal is matched to neither freebase data nor a rule
//   - make a better clone() function
//   - support for hierarchical query

var log = "";
var goals = [];
var graph = {};
var root_node;
var topic_name = {};
var relation_name = {};
var relation_property = {};

function is_variable(topic) {
  var prefix = "/base/inference/variables/";
  if(topic.id.substring(0, prefix.length) == prefix)
    return true;
  else
    return false;
}

function combine_objects(list) {
  if(list.length == 0) {
    return [];
  } else if(list.length == 1) {
    return list[0];
  } else {
    var append_sets = list.pop();
    var base_sets = combine_objects(list);
    if(append_sets.length == 0) {
      return base_sets;
    } else if(base_sets.length == 0) {
      return append_sets;
    } else {
      var new_list = [];
      for(i in base_sets)
        for(j in append_sets)
          new_list.push(acre.freebase.extend_query(clone(base_sets[i]), append_sets[j]));
      return new_list;
    }
  }
}

function combine_arrays(list) {
  if(list.length == 0) {
    return [];
  } else if(list.length == 1) {
    return list[0];
  } else {
    var append_sets = list.pop();
    var base_sets = combine_arrays(list);
    if(append_sets.length == 0) {
      return base_sets;
    } else if(base_sets.length == 0) {
      return append_sets;
    } else {
      var new_list = [];
      for(i in base_sets)
        for(j in append_sets)
          new_list.push(base_sets[i].concat(append_sets[j]));
      return new_list;
    }
  }
}

function graph_push(subject, property, object) {
  if(is_variable(subject))
    subject = subject.id + subject.scope;
  else
    subject = subject.id;
  
  if(is_variable(object))
    object = object.id + object.scope;
  else
    object = object.id;
  
  if(typeof graph[subject] != "object")
    graph[subject] = {};
  if(typeof graph[object] != "object")
    graph[object] = {};
  
  var link_id = Math.floor(Math.random()*2147483648);
  
  graph[subject][object] = "link" + link_id + ":" + property;
  graph[object][subject] = "!" + "link" + link_id + ":" + property;
  
  log += "PUSHED ONTO GRAPH: " + subject + ", " + property + ", " + object + "\n";
}

function set_query(query) {
  for(var i in query) {
    var goal = {};
    /*goal.r_subject = acre.freebase.MqlRead({
      "id" : query[i][0],
      "type" : []
    }).result;*/
    goal.r_subject = {"id" : query[i][0]};
    var relation = acre.freebase.MqlRead({
      "name" : query[i][1],
      "id" : null,
      "type" : "/base/inference/relation",
      "equivalent_property" : null
    }).result;
    goal.r_object = {"id" : query[i][2]};
    /*goal.r_object = acre.freebase.MqlRead({
      "id" : query[i][2],
      "type" : []
    }).result;*/
    
    relation_name[relation.id] = relation.name;
    relation_property[relation.id] = relation.equivalent_property;
    
    goal.relation = {"id" : relation.id}; // TODO
    
    if(is_variable(goal.r_subject))
      goal.r_subject.scope = "";
    if(is_variable(goal.r_object))
      goal.r_object.scope = "";
    
    goals.push(goal);
  }
  
  //goals = [goals]; // TODO
  
  log += "INITIAL GOALS: " + JSON.stringify(goals, null, 2) + "\n";
}

function expand_node(node) {
  var subject = node[0];
  var relation = node[1];
  var object = node[2];
  
  var property = relation_property[relation];
  if(property != null)
    return [subject, property, object];
  
  // TODO move away from goal data structure to id triplets
  var goal = {"r_subject" : {"id":subject}, "relation" : {"id":relation}, "r_object" : {"id":object}};
  var rule = goal_to_rule(goal); // TODO support multiple rules
  // TODO if(rule == null)
  var new_goals = rule_replace_vars(clone(rule), goal); // TODO handle variable scopes
  
  // TODO support ORing child relations
  
  var branches = [[]];
  for(var i in new_goals) {
    var new_goal = new_goals[i];
    var subnode = [new_goal.r_subject, new_goal.relation, new_goal.r_object];
    branches[0].push(expand_node(subnode));
  }
  
  return branches;
}

function run() {
  //return; // TODO
  
  while(goals.length &gt; 0) {
    //log += "CURRENT GOALS: " + JSON.stringify(goals, null, 2);
    var new_goals = [];
    for(var i in goals) {
      var goal = goals[i];
      log += "CONSIDERING GOAL: " + goal.r_subject.id + " " + relation_name[goal.relation.id] + " " + goal.r_object.id + "\n";
      
      if(goal_match_fb(goal)) continue;
      var rule = goal_to_rule(goal);
      if(rule === null) return [];
      
      new_goals = new_goals.concat(rule_replace_vars(clone(rule), goal));
    }
    goals = new_goals;
  }
  
  var mql_query = inference.node_to_query(root_node);
  var mql_result = acre.freebase.MqlRead(mql_query).result;
  var result = inference.extract_vars(mql_result);
  
  //log += "MQL QUERY: " + JSON.stringify(mql_query, null, 2) + "\n";
  
  return result;
}

function get_rule(subject, relation, object) {
  var q = acre.require("goal_to_rule").query;
  
  q.then_clauses = {
    "r_subject" : {"id" : subject},
    "relation" : {"id" : relation},
    "r_object" : {"id" : object},
  };
  
  if(subject == null) q.then_clauses.r_subject.type = "/base/inference/variable";
  if(object  == null) q.then_clauses.r_object.type  = "/base/inference/variable";
  
  var rule = acre.freebase.MqlRead(q).result;
  return rule;
}

function goal_to_rule(goal) {
  var rule = null;
  
  if(!is_variable(goal.r_subject) &amp;&amp; !is_variable(goal.r_object))
    rule = get_rule(goal.r_subject.id, goal.relation.id, goal.r_object.id);
  if(rule == null &amp;&amp; !is_variable(goal.r_object))
    rule = get_rule(null, goal.relation.id, goal.r_object.id);
  if(rule == null &amp;&amp; !is_variable(goal.r_subject))
    rule = get_rule(goal.r_subject.id, goal.relation.id, null);
  if(rule == null)
    rule = get_rule(null, goal.relation.id, null);
  
  if(rule == null) {
    log += "UNABLE TO MATCH GOAL TO ANY RULE\n";
    return null;
  }
  
  log += "GOAL MATCHED TO RULE: " + rule.name + "\n";
  
  for(var i in rule.if_clauses) {
    var relation = rule.if_clauses[i].relation;
    relation_name[relation.id] = relation.name;
    relation_property[relation.id] = relation.equivalent_property;
  }
  
  return rule;
}

/*function goal_to_rule(goal) {
  var rule = null;
  
  if(!is_variable(goal.r_subject) &amp;&amp; !is_variable(goal.r_object)) {
    var q = acre.require("goal_to_rule").query;
    q.then_clauses = {
      "r_subject" : {"id" : goal.r_subject.id},
      "relation" : {"id" : goal.relation.id},
      "r_object" : {"id" : goal.r_object.id},
    };
    rule = acre.freebase.MqlRead(q).result;
  }
  
  if(rule == null &amp;&amp; !is_variable(goal.r_object)) {
    var q = acre.require("goal_to_rule").query;
    q.then_clauses = {
      "r_subject" : {"constrain:type" : "/base/inference/variable", "id": null},
      "relation" : {"id" : goal.relation.id},
      "r_object" : {"id" : goal.r_object.id},
    };
    rule = acre.freebase.MqlRead(q).result;
  }
  
  if(rule == null &amp;&amp; !is_variable(goal.r_subject)) {
    var q = acre.require("goal_to_rule").query;
    q.then_clauses = {
      "r_subject" : {"id" : goal.r_subject.id},
      "relation" : {"id" : goal.relation.id},
      "r_object" : {"constrain:type" : "/base/inference/variable", "id": null},
    };
    rule = acre.freebase.MqlRead(q).result;
  }
  
  if(rule == null) {
    var q = acre.require("goal_to_rule").query;
    q.then_clauses = {
      "r_subject" : {"constrain:type" : "/base/inference/variable", "id": null},
      "relation" : {"id" : goal.relation.id},
      "r_object" : {"constrain:type" : "/base/inference/variable", "id": null},
    };
    rule = acre.freebase.MqlRead(q).result;
  }
  
  if(rule == null) {
    log += "UNABLE TO MATCH GOAL TO ANY RULE\n";
    return null;
  }
  
  log += "GOAL MATCHED TO RULE: " + rule.name + "\n";
  
  for(var i in rule.if_clauses) {
    var relation = rule.if_clauses[i].relation;
    relation_name[relation.id] = relation.name;
    relation_property[relation.id] = relation.equivalent_property;
  }
  
  return rule;
}*/

function goal_match_fb(goal) {
  // find solution to goal from freebase data
  var property = relation_property[goal.relation.id];
  if(property == null) 
    return false;
  
  log += "GOAL MATCHED TO PROPERTY: " + property + "\n";
  //log += "  SUBJECT HAS TYPES: " + JSON.stringify(goal.r_subject.type) + "\n";
  //log += "  OBJECT HAS TYPES: " + JSON.stringify(goal.r_object.type) + "\n";
  
  graph_push(goal.r_subject, property, goal.r_object);
  
  return true;
}

function rule_replace_vars(rule, goal) {
  // map topics in goal to variables in rule
  var variable_replacements = {};
  if(is_variable(rule.then_clauses.r_subject)) {
    log += "MARKING " + rule.then_clauses.r_subject.id + " FOR REPLACEMENT WITH " + goal.r_subject.id + "\n";
    variable_replacements[rule.then_clauses.r_subject.id] = goal.r_subject;
  }
  if(is_variable(rule.then_clauses.r_object)) {
    log += "MARKING " + rule.then_clauses.r_object.id + " FOR REPLACEMENT WITH " + goal.r_object.id + "\n";
    variable_replacements[rule.then_clauses.r_object.id] = goal.r_object;
  }
  
  var scope_id = ":" + Math.floor(Math.random()*2147483648);
  
  // replace variables in rule.if_clauses with topics in goal
  for(var i in rule.if_clauses) {
    new_topic = variable_replacements[rule.if_clauses[i].r_subject.id];
    if(typeof new_topic == "object") {
      log += "REPLACING SUBJECT " + rule.if_clauses[i].r_subject.id + " WITH " + new_topic.id + "\n";
      rule.if_clauses[i].r_subject = new_topic;
    } else {
      rule.if_clauses[i].r_subject.scope = scope_id;
    }
    
    new_topic = variable_replacements[rule.if_clauses[i].r_object.id];
    if(typeof new_topic == "object") {
      log += "REPLACING OBJECT " + rule.if_clauses[i].r_object.id + " WITH " + new_topic.id + "\n";
      rule.if_clauses[i].r_object = new_topic;
    } else {
      rule.if_clauses[i].r_object.scope = scope_id;
    }
  }
  return rule.if_clauses;
}

function clone(x) {
  return JSON.parse(JSON.stringify(x));
}

  function is_empty(x) {
  for(var i in x) return false;
  return true;
}

function extract_vars(obj) {
  var combine_list = [];
  
  for(var key in obj) {
    if(key.indexOf(":/base/inference/variable/symbol") != -1) { // is a global variable tag
      var symbol = key.substring(0, key.indexOf(':'));
      var self_set = {};
      self_set[symbol] = obj.id;
      combine_list.push([self_set]);
      topic_name[obj.id] = obj.name;
    } else if(obj instanceof Array) {
      combine_list = combine_list.concat(extract_vars(obj[key]));
    } else if(typeof obj == "object") {
      combine_list.push(extract_vars(obj[key]));
    }
  }
  
  if(obj instanceof Array)
    return combine_list;
  else
    return combine_objects(combine_list);
}

function explode_andor_tree(list, or_level) {
  var combine_list = [];
  
  if(typeof list == "string") // TODO is a fact
    return [[list]];
  
  for(var i in list) {
    if(or_level)
      combine_list = combine_list.concat(explode_andor_tree(list[i], !or_level));
    else
      combine_list.push(explode_andor_tree(list[i], !or_level));
  }
  
  if(or_level)
    return combine_list;
  else
    return combine_arrays(combine_list);
}

function id_to_symbol(id) {
  var prefix = "/base/inference/variables/";
  if(id.substring(0, prefix.length) == prefix)
    return id.substring(prefix.length, id.length);
  else
    return null;
}

function node_to_query(id, parent) {
  symbol = id_to_symbol(id);
  
  var q = {
    "id" : (symbol == null ? id : null),
    "name" : null
  };
  
  if(symbol != null &amp;&amp; symbol.indexOf(":") == -1) // is a global variable
    q[symbol + ":/base/inference/variable/symbol"] = null;
  
  for(object in inference.graph[id]) {
    if(object == parent)
      continue;
    q[inference.graph[id][object]] = node_to_query(object, id);
  }
  
  return [q];
}

 </p>