git » hoplite.git » master » tree

let _ = new Proxy({}, {get: (target, prop) => Symbol.for(prop)});

function isVar(x) {
  return typeof x === "symbol" && x.description !== "_";
}

function isBlank(x) {
  return typeof x === "symbol" && x.description === "_";
}

const ANY = {
  VALUE: new Object(),
};

function match(clause, fact) {
  let matches = {};
  for (let i = 0; i < clause.length; i++) {
    if (isVar(clause[i])) {
      if (matches.hasOwnProperty(clause[i].description)) {
        if (matches[clause[i].description] !== fact[i]) {
          return;
        }
      }
      matches[clause[i].description] = fact[i];
    } else if (isBlank(clause[i])) {
      continue;
    } else if (clause[i] !== fact[i]) {
      return;
    }
  }
  return matches;
}

function tupleEqual(x, y) {
  if (x.length !== y.length)
    return false;
  for (let i = 0; i < x.length; i++) {
    if (x[i] !== y[i])
      return false;
  }
  return true;
}

function relEqual(o1, o2) {
  let [ks1, ks2] = [o1, o2].map(o => Object.keys(o));
  if (ks1.length !== ks2.length) return false;
  for (let k of ks1) {
    if (o1[k] !== o2[k]) return false;
  }
  return true;
}

class StupidTupleSet {
  constructor(tuples = []) {
    this.tuples = [];
    tuples.forEach(tuple => this.add(tuple));
  }
  add(tuple) {
    if (!this.has(tuple)) {
      this.tuples.push(tuple);
    }
  }
  remove(tuple) {
    if (!this.has(tuple)) {
      return false;
    } else {
      this.tuples = this.tuples.filter(v => !tupleEqual(v, tuple));
      return true;
    }
  }
  [Symbol.iterator]() {
    return this.tuples[Symbol.iterator]();
  }
  has(tuple) {
    return this.tuples.some(v => tupleEqual(v, tuple));
  }
  clear() {
    this.tuples = [];
  }
  complement(other) {
    return new StupidTupleSet([...this].filter(tuple => !other.has(tuple)));
  }
  size() {
    return this.tuples.length;
  }
  toArray() {
    return [...this.tuples];
  }
  equals(other) {
    if (!(other instanceof StupidTupleSet)) return false;
    if (other.size() !== this.size()) return false;
    if (this.complement(other).size()) return false;
    if (other.complement(this).size()) return false;
    return true;
  }
}

class Relation {
  constructor(vars) {
    this.vars = new Set(vars);
    this.rels = [];
  }
  add(rel) {
    if (!this.has(rel)) {
      this.rels.push(rel);
    }
    return this;
  }
  has(rel) {
    return this.rels.some(v => relEqual(v, rel));
  }
  size() {
    return this.rels.length;
  }
  [Symbol.iterator]() {
    return this.rels[Symbol.iterator]();
  }
}

function varNames(clause) {
  return clause.filter(isVar).map(v => v.description);
}

function scan(database, clause) {
  let rel = new Relation(varNames(clause));
  for (let fact of database) {
    let matched = match(clause, fact);
    if (matched) rel.add(matched);
  }
  return rel;
}

function crossJoin(rel1, rel2) {
  let rel3 = new Relation([...rel1.vars, ...rel2.vars]);
  for (let rx of rel1) {
    for (let ry of rel2) {
      rel3.add(Object.assign({}, rx, ry));
    }
  }
  return rel3;
}

function innerJoin(rel1, rel2) {
  let rel3 = new Relation([...rel1.vars, ...rel2.vars]);
  for (let rx of rel1) {
    next: for (let ry of rel2) {
      let joined = {};
      for (let k of rel3.vars) {
        if (rel1.vars.has(k)
            && rel2.vars.has(k)
            && !(rx[k] === ANY.VALUE && ry[k] !== ANY.VALUE)
            && !(rx[k] !== ANY.VALUE && ry[k] === ANY.VALUE)
            && rx[k] !== ry[k]) {
          continue next;
        }
        if (rx[k] === ANY.VALUE) {
          joined[k] = ry[k];
        } else if (ry[k] === ANY.VALUE) {
          joined[k] = rx[k];
        } else {
          joined[k] = rel1.vars.has(k) ? rx[k] : ry[k];
        }
      }
      rel3.add(joined);
    }
  }
  return rel3;
}

function intersects(rel1, rel2) {
  return [...rel1.vars].filter(v => rel2.vars.has(v)).length > 0;
}

function join(rel1, rel2) {
  return intersects(rel1, rel2) ? innerJoin(rel1, rel2) : crossJoin(rel1, rel2);
}

function initRel(use, vals) {
  let rx = Object.fromEntries(use.map((u, i) => [u.description, vals[i]]));
  return new Relation(varNames(use)).add(rx);
}

function findAll(pred, xs) {
  return xs.reduce((xs, y, i) => pred(y) ? [...xs, i] : xs, []);
}

function select(rel, vars) {
  return new StupidTupleSet([...rel].map(rx => vars.map(v => rx[v])));
  // let varIdxs = findAll(isVar, find),
  //     aggIdxs = findAll(x => !isVar(x), find);
  // if (!rel.size()) {
  //   return rel; 
  // } else if (!aggIdxs.length) {
  //   return new StupidTupleSet([...rel].map(rx => find.map(v => rx[v.description])));
  // } else if (!varIdxs.length) {
  //   return new StupidTupleSet(find.map(([op, sym]) => {
  //     if (op === "min") {
  //       return [
  //         [...rel].map(rx => rx[sym.description]).sort((a, b) => a - b)[0]
  //       ];
  //     } else {
  //       throw new Error(`Unsupported aggregation operator: ${op}`);
  //     }
  //   }));
  // } else {
  //   // TODO agg + vars
  //   throw new Error(`TODO grouping`)
  // }
}

function parseVals(use, vals) {
  if (use.length > 0 && use[0] instanceof Array) {
    let sourceNames = use[0];
    if (vals.length < sourceNames.length) {
      throw new Error(`Not enough data sources passed query`);
    }
    return {
      multipleSources: true,
      namedSources: Object.fromEntries(sourceNames.map((sourceName, i) => [
        sourceName,
        vals[i]
      ])),
      valueNames: use.slice(1),
      values: vals.slice(sourceNames.length)
    };
  } else if (!vals.length) {
    throw new Error(`No data source passed to query`);
  } else {
    return {
      multipleSources: false,
      source: vals[0],
      valueNames: use,
      values: vals.slice(1)
    };
  }
}

function isPredicateClause(clause) {
  return clause.length === 1 && clause[0] instanceof Array;
}

function isSimpleClause(clause) {
  return !isPredicateClause(clause);
}

function evalPred(predExpr) {
  let [op, ...args] = predExpr;
  if (op === '<') {
    for (let i = 0; i < args.length-1; i += 2) {
      if (!(args[i] < args[i+1])) return false;
    }
    return true;
  } else if (op === '<=') {
    for (let i = 0; i < args.length-1; i += 2) {
      if (!(args[i] <= args[i+1])) return false;
    }
    return true;
  } else if (op === '>') {
    for (let i = 0; i < args.length-1; i += 2) {
      if (!(args[i] > args[i+1])) return false;
    }
    return true;
  } else if (op === '>=') {
    for (let i = 0; i < args.length-1; i += 2) {
      if (!(args[i] >= args[i+1])) return false;
    }
    return true;
  } else {
    throw new Error(`Unknown predicate: ${op}`);
  }
}

function filterByPredicate(rel, predClause) {
  return [...rel].reduce((xs, x) => {
    let predExpr = [];
    for (let y of predClause) {
      if (isBlank(y)) {
        throw new Error("Blanks not allowed in predicates");
      } else if (isVar(y)) {
        if (!x.hasOwnProperty(y.description)) {
          throw new Error("Unknown variable ${y.description} in predicate");
        }
        if (x[y.description] === ANY.VALUE) continue;
        predExpr.push(x[y.description]);
      } else {
        predExpr.push(y);
      }
    };
    if (evalPred(predExpr)) xs.add(x);
    return xs;
  }, new Relation(rel.vars));
}

function query({find = [], use = [], where = []}, ...vals) {
  let parsed = parseVals(use, vals);
  if (parsed.multipleSources) {
    let rels = [initRel(parsed.valueNames, parsed.values)];
    for (let sourceName of Object.getOwnPropertySymbols(parsed.namedSources)) {
      where
        .filter(c => c[0] === sourceName)
        .map(c => scan(parsed.namedSources[sourceName], c.slice(1)))
        .forEach(rel => rels.push(rel));
    }
    return select(rels.reduce(join), varNames(find));
  } else {
    let rel = [
      initRel(parsed.valueNames, parsed.values),
      ...where
        .filter(isSimpleClause)
        .map(c => scan(parsed.source, c))
    ].reduce(join);
    let preds = where.filter(isPredicateClause).map(x => x[0]);
    if (preds.length) {
      rel = preds.reduce(filterByPredicate, rel);
    }
    return select(rel, varNames(find));
  }
} 

function partialQuery(q) {
  return (...vals) => query(q, ...vals);
}

function paths(x, parent = []) {
  if (x instanceof Array) {
    return x.flatMap((y, i) => paths(y, [...parent, i]));
  } else if (x instanceof Object) {
    return Object
      .entries(x)
      .flatMap(([k, v]) => paths(v, [...parent, k]));
  } else {
    return [[...parent, x]];
  }
}

export { ANY, _, query, StupidTupleSet, partialQuery, paths };
// let db = new JSONSet([
//   ["sally", "age", 21],
//   ["fred", "age", 42],
//   ["ethel", "age", 42],
//   ["fred", "likes", "pizza"],
//   ["sally", "likes", "opera"],
//   ["ethel", "likes", "sushi"]
// ]);

// let db2 = new JSONSet([
//   ["ethel", "sex", "female"],
//   ["fred", "sex", "male"]
// ]);

// let log = db => console.log(JSON.stringify([...db]));

// log(
//   query({
//     find: [_.sex],
//     use: [[_.db1, _.db2], _.age],
//     where: [
//       [_.db1, _.e, "age", _.age],
//       [_.db2, _.e, "sex", _.sex]
//     ]
//   }, db, db2, 42)
// );
// // [["male"],["female"]]

// log(
//   query({
//     find: [_.e],
//     use: [[_.db]],
//     where: [
//       [_.db, _.e, "age", 42]
//     ]
//   }, db)
// );
// // [["fred"],["ethel"]]

// log(
//   query({
//     find: [_.e, _.x],
//     use: [_.age],
//     where: [
//       [_.e, "likes", _.x],
//       [_.e, "age", _.age]
//     ]}, db, 42)
// );
// // [["fred","pizza"],["ethel","sushi"]]

// log(
//   query({
//     find: [_.x],
//     where: [
//       [_._, "likes", _.x]
//     ]}, db)
// );
// // [["pizza"],["opera"],["sushi"]]

// log(
//   query({
//     find: [_.x, _.y],
//     use: [_.z],
//     where: [
//       [_.z, "likes", _.x],
//       [_.z, "age", _.y]
//     ]}, db, "sally")
// );
// // [["opera",21]]

// log(
//   query({
//     find: [_.x],
//     where: [[_.x, _._, _._]]
//   }, db)
// );
// // [["sally"],["fred"],["ethel"]]