test of N3.js utility to find bug dependent on the order of hashes in the Store object.

n3-js-forced-index-test.js

var n3 = require('n3')

function describe (dlabel, d) {
  d(it, xit)

  function it (ilabel, i) {
    try {
      i()
      ++passing
    } catch (e) {
      messages.push(dlabel + ' ' + ilabel + ' ' + e.message)
      ++failing
    }
  }

  function xit (label, i) {
    ++pending
  }
}

var passing = 0
var pending = 0
var failing = 0
var messages = []

var expect = function (v) {
  if (!v) {
    throw Error('failed')
  }
}

var deepEquals = function (l, r) {
  var lkeys = Object.keys(l)
  var rkeys = Object.keys(r)
  if (lkeys.length !== rkeys.length) {
    return false
  }
  if (lkeys.find(k => {
    return (l[k] !== r[k])
  })) {
    return false
  }
  return true
}

describe('graph equiv', function (it, xit) {
  var l = n3.Store([ { subject: 'tag:b0', predicate: 'http://shex.io/extensions/Map/#BPunitsDAM-systolic', object: '_:b0', graph: '' }, { subject: 'tag:b0', predicate: 'http://shex.io/extensions/Map/#BPunitsDAM-diastolic', object: '_:b1', graph: '' }, { subject: '_:b0', predicate: 'http://shex.io/extensions/Map/#BPunitsDAM-value', object: '"110"^^http://www.w3.org/2001/XMLSchema#float', graph: '' }, { subject: '_:b0', predicate: 'http://shex.io/extensions/Map/#BPunitsDAM-units', object: '"mmHg"', graph: '' }, { subject: '_:b1', predicate: 'http://shex.io/extensions/Map/#BPunitsDAM-value', object: '"70"^^http://www.w3.org/2001/XMLSchema#float', graph: '' }, { subject: '_:b1', predicate: 'http://shex.io/extensions/Map/#BPunitsDAM-units', object: '"mmHg"', graph: '' } ])
  var r = n3.Store([ { subject: 'tag:b0', predicate: 'http://shex.io/extensions/Map/#BPunitsDAM-diastolic', object: '_:b8', graph: '' }, { subject: 'tag:b0', predicate: 'http://shex.io/extensions/Map/#BPunitsDAM-systolic', object: '_:b7', graph: '' }, { subject: '_:b8', predicate: 'http://shex.io/extensions/Map/#BPunitsDAM-units', object: '"mmHg"', graph: '' }, { subject: '_:b8', predicate: 'http://shex.io/extensions/Map/#BPunitsDAM-value', object: '"70"^^http://www.w3.org/2001/XMLSchema#float', graph: '' }, { subject: '_:b7', predicate: 'http://shex.io/extensions/Map/#BPunitsDAM-units', object: '"mmHg"', graph: '' }, { subject: '_:b7', predicate: 'http://shex.io/extensions/Map/#BPunitsDAM-value', object: '"110"^^http://www.w3.org/2001/XMLSchema#float', graph: '' } ])
  var lobj = {'_size': null, '_graphs': {'': {'subjects': {'1': {'2': {'3': null}, '8': {'9': null}}, '3': {'4': {'5': null}, '6': {'7': null}}, '9': {'4': {'10': null}, '6': {'7': null}}}, 'predicates': {'2': {'3': {'1': null}}, '4': {'5': {'3': null}, '10': {'9': null}}, '6': {'7': {'3': null, '9': null}}, '8': {'9': {'1': null}}}, 'objects': {'3': {'1': {'2': null}}, '5': {'3': {'4': null}}, '7': {'3': {'6': null}, '9': {'6': null}}, '9': {'1': {'8': null}}, '10': {'9': {'4': null}}}}}, '_id': 10, '_ids': {'><': 0, 'tag:b0': 1, 'http://shex.io/extensions/Map/#BPunitsDAM-systolic': 2, '_:b0': 3, 'http://shex.io/extensions/Map/#BPunitsDAM-value': 4, '"110"^^http://www.w3.org/2001/XMLSchema#float': 5, 'http://shex.io/extensions/Map/#BPunitsDAM-units': 6, '"mmHg"': 7, 'http://shex.io/extensions/Map/#BPunitsDAM-diastolic': 8, '_:b1': 9, '"70"^^http://www.w3.org/2001/XMLSchema#float': 10}, '_entities': {'1': 'tag:b0', '2': 'http://shex.io/extensions/Map/#BPunitsDAM-systolic', '3': '_:b0', '4': 'http://shex.io/extensions/Map/#BPunitsDAM-value', '5': '"110"^^http://www.w3.org/2001/XMLSchema#float', '6': 'http://shex.io/extensions/Map/#BPunitsDAM-units', '7': '"mmHg"', '8': 'http://shex.io/extensions/Map/#BPunitsDAM-diastolic', '9': '_:b1', '10': '"70"^^http://www.w3.org/2001/XMLSchema#float'}, '_blankNodeIndex': 0, '_prefixes': {'': 'http://shex.io/extensions/Map/#BPunitsDAM-', 'xsd': 'http://www.w3.org/2001/XMLSchema#', 'bp': 'http://shex.io/extensions/Map/#BPDAM-', 'Map': 'http://shex.io/extensions/Map/#'}}
  var robj = {'_size': null, '_graphs': {'': {'subjects': {'1': {'2': {'3': null}, '8': {'9': null}}, '3': {'4': {'5': null}, '6': {'7': null}}, '9': {'4': {'5': null}, '6': {'10': null}}}, 'predicates': {'2': {'3': {'1': null}}, '4': {'5': {'3': null, '9': null}}, '6': {'7': {'3': null}, '10': {'9': null}}, '8': {'9': {'1': null}}}, 'objects': {'3': {'1': {'2': null}}, '5': {'3': {'4': null}, '9': {'4': null}}, '7': {'3': {'6': null}}, '9': {'1': {'8': null}}, '10': {'9': {'6': null}}}}}, '_id': 10, '_ids': {'><': 0, 'tag:b0': 1, 'http://shex.io/extensions/Map/#BPunitsDAM-diastolic': 2, '_:b8': 3, 'http://shex.io/extensions/Map/#BPunitsDAM-units': 4, '"mmHg"': 5, 'http://shex.io/extensions/Map/#BPunitsDAM-value': 6, '"70"^^http://www.w3.org/2001/XMLSchema#float': 7, 'http://shex.io/extensions/Map/#BPunitsDAM-systolic': 8, '_:b7': 9, '"110"^^http://www.w3.org/2001/XMLSchema#float': 10}, '_entities': {'1': 'tag:b0', '2': 'http://shex.io/extensions/Map/#BPunitsDAM-diastolic', '3': '_:b8', '4': 'http://shex.io/extensions/Map/#BPunitsDAM-units', '5': '"mmHg"', '6': 'http://shex.io/extensions/Map/#BPunitsDAM-value', '7': '"70"^^http://www.w3.org/2001/XMLSchema#float', '8': 'http://shex.io/extensions/Map/#BPunitsDAM-systolic', '9': '_:b7', '10': '"110"^^http://www.w3.org/2001/XMLSchema#float'}, '_blankNodeIndex': 0, '_prefixe': {}}
  let m = {}
  let mgood = { '_:b1': '_:b8', '_:b0': '_:b7' }
  let mbad = { '_:b0': '_:b8', '_:b1': '_:b7' }
  it('l == r', function () {
    Object.assign(l, lobj)
    expect(geq(l, r, m))
    expect(deepEquals(m, mgood))
    expect(!deepEquals(m, mbad))
  })
  xit('i(l) == r', function () {
    Object.assign(l, lobj)
    expect(geq(l, r))
  })
  it('i(l) == i(r)', function () {
    Object.assign(r, robj)
    expect(geq(l, r, mgood))
    expect(geq(l, r))
  })
})
console.log(`  ${passing} passing\n  ${pending} pending\n  ${failing} failing\n${
  messages.map((m, i) => {
    return i + 1 + ') ' + m
  })
}`)

function geq (l, r, m) { // graphEquals needs a this
  return graphEquals.call(l, r, m)
}

/** graphEquals: test if two graphs are isomorphic through some bnode mapping.
 *
 * this: one of the graphs to test, referred to as "left" below.
 * right: the other graph to test.
 * m: (optional) writable mapping from left bnodes to write bnodes.
 * returns: true or false
 * side effects: m is populated with a working mapping.
 */
function graphEquals (right, m) {
  if (this.size !== right.size) {
    return false
  }
  m = m || {}                                    // Left→right mappings (optional argument).
  var back = Object.keys(m).reduce(function (ret, from) { // Right→left mappings
    ret[m[from]] = from                                  //  populated if m was passed in.
    return ret
  }, {})
  function match (g) {
    function val (term, mapping) {
      mapping = mapping || m                     // Mostly used for left→right mappings.
      if (n3.Util.isBlank(term)) {
        return (term in mapping) ? mapping[term] : null // Bnodes get current binding or null.
      } else {
        return term                              // Other terms evaluate to themselves.
      }
    }

    if (g.length === 0) {                         // Success if there's nothing left to match.
      return true
    }
    var t = g.pop()
    var s = val(t.subject)
    var o = val(t.object) // Take the first triple in left.
    var tm = right.getTriplesByIRI(s, t.predicate, o)  // Find candidates in right.

    var r = tm.reduce(function (ret, triple) {    // Walk through candidates in right.
      if (ret) return true                       // Only examine first successful mapping.
      var adds = []                              // List of candidate mappings.
      function add (from, to) {
        if (val(from) === null) {                   // If there's no binding from tₗ to tᵣ,
          if (val(to, back) === null) {                // If we can bind to to the object
            adds.push(from)                           //  add a candidate binding.
            m[from] = to
            back[to] = from
            return true
          } else {                                     // Otherwise,
            return false                              //  it's not a viable mapping.
          }
        } else {                                    // Otherwise,
          return true                                 //  there's no new binding.
        }
      }
      if (!add(t.subject, triple.subject) ||     // If the bindings for tₗ.s→tᵣ.s fail
          !add(t.object, triple.object) ||       // or the bindings for tₗ.o→tᵣ.o fail
          !match(g)) {                           // of the remaining triples fail,
        adds.forEach(function (added) {             // remove each added binding.
          delete back[m[added]]
          delete m[added]
        })
        return false
      } else {
        return true
      }
    }, false)                                    // Empty tm returns failure.
    if (!r) {
      g.push(t)                                  // No binding for t in cancidate mapping.
    }
    return r
  }
  return match(this.getTriples(null, null, null))     // Start with all triples.
}