--- a/playground/jsonld.js Sat Jul 09 10:16:23 2011 -0400
+++ b/playground/jsonld.js Sat Jul 09 14:15:43 2011 -0400
@@ -21,6 +21,10 @@
module.exports = forge.jsonld = {};
}
+// local defines for keywords
+var __s = '@subject';
+var __t = '@type';
+
/*
* JSON-LD API.
*/
@@ -49,7 +53,6 @@
{
var ctx =
{
- a: jsonld.ns.rdf + 'type',
rdf: jsonld.ns.rdf,
rdfs: 'http://www.w3.org/2000/01/rdf-schema#',
owl: 'http://www.w3.org/2002/07/owl#',
@@ -112,6 +115,12 @@
}
}
+ // term not found, if term is rdf type, use built-in keyword
+ if(rval === null && iri === jsonld.ns.rdf + 'type')
+ {
+ rval = __t;
+ }
+
// term not found, check the context for a CURIE prefix
if(rval === null)
{
@@ -194,12 +203,17 @@
usedCtx[term] = rval;
}
}
- // 3. The property is the special-case '@'.
- else if(term === "@subject")
+ // 3. The property is the special-case subject.
+ else if(term === __s)
{
- rval = "@subject";
+ rval = __s;
}
- // 4. The property is a relative IRI, prepend the default vocab.
+ // 4. The property is the special-case rdf type.
+ else if(term === __t)
+ {
+ rval = jsonld.ns.rdf + 'type';
+ }
+ // 5. The property is a relative IRI, prepend the default vocab.
else
{
rval = ctx['@vocab'] + term;
@@ -241,9 +255,9 @@
/**
* Clones a string/number or an object and sorts the keys. Deep clone
- * is not performed. This function will not shallow or deep copy arrays, but
- * that feature isn't needed in this implementation at present. If it is
- * needed in the future, it will have to be implemented here.
+ * is not performed. This function will deep copy arrays, but that feature
+ * isn't needed in this implementation at present. If it is needed in the
+ * future, it will have to be implemented here.
*
* @param value the value to clone.
*
@@ -260,7 +274,14 @@
for(var i in keys)
{
var key = keys[i];
- rval[key] = value[key];
+ if(value[key].constructor === Array)
+ {
+ rval[key] = value[key].slice();
+ }
+ else
+ {
+ rval[key] = value[key];
+ }
}
}
else
@@ -318,7 +339,7 @@
var p = _expandTerm(ctx, property, null);
// built-in type coercion JSON-LD-isms
- if(p === '@' || p === jsonld.ns.rdf + 'type')
+ if(p === __s || p === jsonld.ns.rdf + 'type')
{
rval = xsd.anyURI;
}
@@ -405,10 +426,10 @@
// graph literal/disjoint graph
else if(
value.constructor === Object &&
- '@' in value && value['@'].constructor === Array)
+ __s in value && value[__s].constructor === Array)
{
rval = {};
- rval['@'] = _compact(ctx, property, value['@'], usedCtx);
+ rval[__s] = _compact(ctx, property, value[__s], usedCtx);
}
// value has sub-properties if it doesn't define a literal or IRI value
else if(
@@ -594,18 +615,18 @@
rval = {};
for(var key in value)
{
- if(key.length === 1 || key.indexOf('@') !== 0)
+ // preserve frame keywords
+ if(key === '@embed' || key === '@explicit')
+ {
+ _setProperty(rval, key, _clone(value[key]));
+ }
+ else if(key !== '@context' && key !== '@coerce')
{
// set object to expanded property
_setProperty(
rval, _expandTerm(ctx, key, null),
_expand(ctx, key, value[key], expandSubjects));
}
- else if(key !== '@context')
- {
- // preserve non-context json-ld keywords
- _setProperty(rval, key, _clone(value[key]));
- }
}
}
// value is already expanded
@@ -638,7 +659,7 @@
}
// coerce to appropriate datatype, only expand subjects if requested
- if(coerce !== null && (property !== '@' || expandSubjects))
+ if(coerce !== null && (property !== __s || expandSubjects))
{
rval = {};
@@ -679,8 +700,8 @@
{
// look for "_:" at the beginning of the subject
return (
- v.constructor === Object && '@' in v &&
- '@iri' in v['@'] && _isBlankNodeIri(v['@']['@iri']));
+ v.constructor === Object && __s in v &&
+ '@iri' in v[__s] && _isBlankNodeIri(v[__s]['@iri']));
};
var _isBlankNode = function(v)
@@ -689,7 +710,7 @@
return (
v.constructor === Object &&
!('@iri' in v || '@literal' in v) &&
- (!('@' in v) || _isNamedBlankNode(v)));
+ (!(__s in v) || _isNamedBlankNode(v)));
};
/**
@@ -864,6 +885,8 @@
// steps #3.2.2-3.2.9
if(rval === 0)
{
+ objsA.sort(_compareObjects);
+ objsB.sort(_compareObjects);
for(var i = 0; i < objsA.length && rval === 0; ++i)
{
rval = _compareObjects(objsA[i], objsB[i]);
@@ -927,17 +950,17 @@
}
else if(input.constructor === Object)
{
- if('@' in input)
+ if(__s in input)
{
// graph literal
- if(input['@'].constructor == Array)
+ if(input[__s].constructor == Array)
{
- _collectSubjects(input['@'], subjects, bnodes);
+ _collectSubjects(input[__s], subjects, bnodes);
}
// named subject
else
{
- subjects[input['@']['@iri']] = input;
+ subjects[input[__s]['@iri']] = input;
}
}
// unnamed blank node
@@ -989,7 +1012,7 @@
else if(value.constructor === Object)
{
// graph literal/disjoint graph
- if('@' in value && value['@'].constructor === Array)
+ if(__s in value && value[__s].constructor === Array)
{
// cannot flatten embedded graph literals
if(parent !== null)
@@ -1000,9 +1023,9 @@
}
// top-level graph literal
- for(var key in value['@'])
+ for(var key in value[__s])
{
- _flatten(parent, parentProperty, value['@'][key], subjects);
+ _flatten(parent, parentProperty, value[__s][key], subjects);
}
}
// already-expanded value
@@ -1015,18 +1038,18 @@
{
// create or fetch existing subject
var subject;
- if(value['@']['@iri'] in subjects)
+ if(value[__s]['@iri'] in subjects)
{
- // FIXME: '@' might be a graph literal (as {})
- subject = subjects[value['@']['@iri']];
+ // FIXME: __s might be a graph literal (as {})
+ subject = subjects[value[__s]['@iri']];
}
else
{
subject = {};
- if('@' in value)
+ if(__s in value)
{
- // FIXME: '@' might be a graph literal (as {})
- subjects[value['@']['@iri']] = subject;
+ // FIXME: __s might be a graph literal (as {})
+ subjects[value[__s]['@iri']] = subject;
}
}
flattened = subject;
@@ -1060,12 +1083,13 @@
// add flattened value to parent
if(flattened !== null && parent !== null)
{
- // remove top-level '@' for subjects
- // 'http://mypredicate': {'@': {'@iri': 'http://mysubject'}} becomes
+ // remove top-level __s for subjects
+ // 'http://mypredicate': {'@subject': {'@iri': 'http://mysubject'}}
+ // becomes
// 'http://mypredicate': {'@iri': 'http://mysubject'}
- if(flattened.constructor === Object && '@' in flattened)
+ if(flattened.constructor === Object && __s in flattened)
{
- flattened = flattened['@'];
+ flattened = flattened[__s];
}
if(parent.constructor === Array)
@@ -1097,7 +1121,11 @@
*/
jsonld.Processor = function()
{
- this.memo = {};
+ this.ng =
+ {
+ tmp: null,
+ c14n: null
+ };
};
/**
@@ -1128,10 +1156,18 @@
var subjects = {};
_flatten(null, null, expanded, subjects);
- // append subjects to array
+ // append subjects with sorted properties to array
for(var key in subjects)
{
- rval.push(subjects[key]);
+ var s = subjects[key];
+ var sorted = {};
+ var keys = Object.keys(s).sort();
+ for(var i in keys)
+ {
+ var k = keys[i];
+ sorted[k] = s[k];
+ }
+ rval.push(sorted);
}
// canonicalize blank nodes
@@ -1140,7 +1176,7 @@
// sort output
rval.sort(function(a, b)
{
- return _compare(a['@']['@iri'], b['@']['@iri']);
+ return _compare(a[__s]['@iri'], b[__s]['@iri']);
});
}
@@ -1155,7 +1191,7 @@
jsonld.Processor.prototype.nameBlankNodes = function(input)
{
// create temporary blank node name generator
- var ng = this.ng = _createNameGenerator('tmp');
+ var ng = this.ng.tmp = _createNameGenerator('tmp');
// collect subjects and unnamed bnodes
var subjects = {};
@@ -1166,11 +1202,11 @@
for(var i in bnodes)
{
var bnode = bnodes[i];
- if(!('@' in bnode))
+ if(!(__s in bnode))
{
// generate names until one is unique
while(ng.next() in subjects);
- bnode['@'] =
+ bnode[__s] =
{
'@iri': ng.current()
};
@@ -1188,10 +1224,10 @@
*/
jsonld.Processor.prototype.renameBlankNode = function(b, id)
{
- var old = b['@']['@iri'];
+ var old = b[__s]['@iri'];
// update bnode IRI
- b['@']['@iri'] = id;
+ b[__s]['@iri'] = id;
// update subjects map
var subjects = this.subjects;
@@ -1254,61 +1290,18 @@
};
/**
- * Deeply names the given blank node by first naming it if it doesn't already
- * have an appropriate prefix, and then by naming its properties and then
- * references.
- *
- * @param b the bnode to name.
- */
-jsonld.Processor.prototype.deepNameBlankNode = function(b)
-{
- // rename bnode (if not already renamed)
- var iri = b['@']['@iri'];
- var ng = this.ng;
- if(!ng.inNamespace(iri))
- {
- this.renameBlankNode(b, ng.next());
- iri = ng.current();
-
- var self = this;
- var subjects = this.subjects;
-
- // FIXME: can bnode edge sorting be optimized out due to sorting them
- // when they are unequal in other parts of this algorithm?
-
- // rename bnode properties
- var props = this.edges.props[iri].bnodes.sort(
- function(a, b) { return self.compareEdges(a, b); });
- for(var i in props)
- {
- if(props[i].s in subjects)
- {
- this.deepNameBlankNode(subjects[props[i].s]);
- }
- }
-
- // rename bnode references
- var refs = this.edges.refs[iri].bnodes.sort(
- function(a, b) { return self.compareEdges(a, b); });
- for(var i in refs)
- {
- if(refs[i].s in subjects)
- {
- this.deepNameBlankNode(subjects[refs[i].s]);
- }
- }
- }
-};
-
-/**
* Canonically names blank nodes in the given input.
*
* @param input the flat input graph to assign names to.
*/
jsonld.Processor.prototype.canonicalizeBlankNodes = function(input)
{
+ // create serialization state
+ this.renamed = {};
+ this.mappings = {};
+ this.serializations = {};
+
// collect subjects and bnodes from flat input graph
- var memo = this.memo = {};
var edges = this.edges =
{
refs: {},
@@ -1318,7 +1311,7 @@
var bnodes = [];
for(var i in input)
{
- var iri = input[i]['@']['@iri'];
+ var iri = input[i][__s]['@iri'];
subjects[iri] = input[i];
edges.refs[iri] =
{
@@ -1336,46 +1329,97 @@
}
}
- // build map of memoized bnode comparisons
- for(var i1 in bnodes)
- {
- var iri1 = bnodes[i1]['@']['@iri'];
- memo[iri1] = {};
- }
-
// collect edges in the graph
this.collectEdges();
- // sort blank nodes
- var self = this;
- bnodes.sort(function(a, b)
- {
- return self.deepCompareBlankNodes(a, b, {});
- });
+ // create canonical blank node name generator
+ var c14n = this.ng.c14n = _createNameGenerator('c14n');
+ var ngTmp = this.ng.tmp;
- // create canonical blank node name generator
- var c14n = _createNameGenerator('c14n');
-
- // rename all bnodes that have canonical names to temporary names
- var tmp = this.ng;
+ // rename all bnodes that happen to be in the c14n namespace
+ // and initialize serializations
for(var i in bnodes)
{
var bnode = bnodes[i];
- if(c14n.inNamespace(bnode['@']['@iri']))
+ var iri = bnode[__s]['@iri'];
+ this.serializations[iri] =
+ {
+ 'props': null,
+ 'refs': null
+ };
+ if(c14n.inNamespace(iri))
{
// generate names until one is unique
- while(tmp.next() in subjects);
- this.renameBlankNode(bnode, tmp.current());
+ while(ngTmp.next() in subjects);
+ this.renameBlankNode(bnode, ngTmp.current());
}
}
- // change internal name generator from tmp one to canonical one
- this.ng = c14n;
-
- // deeply-iterate over bnodes canonically-naming them
- for(var i in bnodes)
+ // keep sorting and naming blank nodes until they are all named
+ var self = this;
+ while(bnodes.length > 0)
{
- this.deepNameBlankNode(bnodes[i]);
+ bnodes.sort(function(a, b)
+ {
+ return self.deepCompareBlankNodes(a, b);
+ });
+
+ // name all bnodes according to the first bnode's relation mappings
+ var bnode = bnodes.shift(1);
+ var iri = bnode[__s]['@iri'];
+ var dirs = ['props', 'refs'];
+ for(var d in dirs)
+ {
+ var dir = dirs[d];
+
+ // if no serialization has been computed, name only the first node
+ if(this.serializations[iri][dir] === null)
+ {
+ var mapping = {};
+ mapping[iri] = 's1';
+ }
+ else
+ {
+ mapping = this.serializations[iri][dir].m;
+ }
+
+ // sort keys by value to name them in order
+ var keys = Object.keys(mapping);
+ keys.sort(function(a, b)
+ {
+ return _compare(mapping[a], mapping[b]);
+ });
+
+ // name bnodes in mapping
+ var renamed = [];
+ for(var i in keys)
+ {
+ var iri = keys[i];
+ if(!c14n.inNamespace(iri) && iri in subjects)
+ {
+ this.renameBlankNode(subjects[iri], c14n.next());
+ renamed.push(iri);
+ }
+ }
+
+ // only keep non-canonically named bnodes
+ var tmp = bnodes;
+ bnodes = [];
+ for(var i in tmp)
+ {
+ var b = tmp[i];
+ var iriB = b[__s]['@iri'];
+ if(!c14n.inNamespace(iriB))
+ {
+ // mark serializations related to the named bnodes as dirty
+ for(var i2 in renamed)
+ {
+ this.markSerializationDirty(iriB, renamed[i2], dir);
+ }
+ bnodes.push(b);
+ }
+ }
+ }
}
// sort property lists that now have canonically-named bnodes
@@ -1396,197 +1440,231 @@
};
/**
- * Checks to see if the given bnode IRIs are equivalent in the given
- * isomorphism.
- *
- * @param iso the isomorphism to check.
- * @param iriA the first bnode IRI.
- * @param iriB the second bnode IRI.
- * @param cycle a map to prevent cycles when checking.
- *
- * @return true if iriA and iriB are for equivalent bnodes per the isomorphism.
+ * A MappingBuilder is used to build a mapping of existing blank node names
+ * to a form for serialization. The serialization is used to compare blank
+ * nodes against one another to determine a sort order.
*/
-var _isIsoMatch = function(iso, iriA, iriB, cycle)
+MappingBuilder = function()
{
- var rval = false;
-
- if(iriA === iriB)
- {
- rval = true;
- }
- else if(iriA in iso)
+ this.count = 1;
+ this.mapped = {};
+ this.mapping = {};
+ this.output = {};
+};
+
+/**
+ * Copies a MappingBuilder.
+ *
+ * @param mb the MappingBuilder to copy.
+ */
+MappingBuilder.prototype.copy = function()
+{
+ var rval = new MappingBuilder();
+ rval.count = this.count;
+ rval.mapped = _clone(this.mapped);
+ rval.mapping = _clone(this.mapping);
+ rval.output = _clone(this.output);
+ return rval;
+};
+
+/**
+ * Maps the next name to the given bnode IRI if the bnode IRI isn't already in
+ * the mapping. If the given bnode IRI is canonical, then it will be given
+ * a shortened form of the same name.
+ *
+ * @param iri the blank node IRI to map the next name to.
+ *
+ * @return the mapped name.
+ */
+MappingBuilder.prototype.mapNode = function(iri)
+{
+ if(!(iri in this.mapping))
{
- if(iso[iriA] === iriB)
+ if(iri.indexOf('_:c14n') === 0)
{
- rval = true;
+ this.mapping[iri] = 'c' + iri.substr(6);
}
- else if(!(iriA in cycle))
+ else
{
- cycle[iriA] = true;
- rval = _isIsoMatch(iso, iso[iriA], iriB, cycle);
+ this.mapping[iri] = 's' + this.count++;
}
}
- else if(iriB in iso)
+ return this.mapping[iri];
+};
+
+/**
+ * Marks a relation serialization as dirty if necessary.
+ *
+ * @param iri the IRI of the bnode to check.
+ * @param changed the old IRI of the bnode that changed.
+ * @param dir the direction to check ('props' or 'refs').
+ */
+jsonld.Processor.prototype.markSerializationDirty = function(iri, changed, dir)
+{
+ var s = this.serializations[iri];
+ if(s[dir] !== null && changed in s[dir].m)
{
- rval = _isIsoMatch(iso, iriB, iriA, cycle);
+ s[dir] = null;
+ }
+};
+
+/**
+ * Rotates the elements in an array one position.
+ *
+ * @param a the array.
+ */
+var _rotate = function(a)
+{
+ a.unshift.apply(a, a.splice(1, a.length));
+};
+
+/**
+ * Recursively creates a relation serialization (partial or full).
+ *
+ * @param keys the keys to serialize in the current output.
+ * @param output the current mapping builder output.
+ * @param done the already serialized keys.
+ *
+ * @return the relation serialization.
+ */
+var _recursiveSerializeMapping = function(keys, output, done)
+{
+ var rval = '';
+ for(var i in keys)
+ {
+ var k = keys[i];
+ if(!(k in output))
+ {
+ break;
+ }
+
+ if(k in done)
+ {
+ // mark cycle
+ rval += '_' + k;
+ }
+ else
+ {
+ done[k] = true;
+ var tmp = output[k];
+ rval += k + tmp.join('');
+ rval += _recursiveSerializeMapping(tmp, output, done);
+ }
+ }
+ return rval;
+};
+
+/**
+ * Creates a relation serialization (partial or full).
+ *
+ * @param output the current mapping builder output.
+ *
+ * @return the relation serialization.
+ */
+var _serializeMapping = function(output)
+{
+ // get sorted keys for current output
+ var keys = Object.keys(output).sort();
+ var done = {};
+ return _recursiveSerializeMapping(keys, output, done);
+};
+
+/**
+ * Compares two serializations for the same blank node. If the two
+ * serializations aren't complete enough to determine if they are equal (or if
+ * they are actually equal), 0 is returned.
+ *
+ * @param s1 the first serialization.
+ * @param s2 the second serialization.
+ *
+ * @return -1 if s1 < s2, 0 if s1 == s2 (or indeterminate), 1 if s1 > v2.
+ */
+var _compareSerializations = function(s1, s2)
+{
+ var rval = 0;
+
+ if(s1.length == s2.length)
+ {
+ rval = _compare(s1, s2);
+ }
+ else if(s1.length > s2.length)
+ {
+ rval = _compare(s1.substr(0, s2.length), s2);
+ }
+ else
+ {
+ rval = _compare(s1, s2.substr(0, s1.length));
}
return rval;
};
/**
- * Compares the edges between two nodes for equivalence.
+ * Computes the relation serialization for the given blank node IRI.
*
- * @param a the first bnode.
- * @param b the second bnode.
- * @param dir the edge direction ('props' or 'refs').
- * @param iso the current subgraph isomorphism for connected bnodes.
- *
- * @return -1 if a < b, 0 if a == b, 1 if a > b.
+ * @param s the serialization to update.
+ * @param iri the current bnode IRI to be mapped.
+ * @param mb the MappingBuilder to use.
+ * @param dir the edge direction to use ('props' or 'refs').
*/
-jsonld.Processor.prototype.deepCompareEdges = function(a, b, dir, iso)
+jsonld.Processor.prototype.serializeBlankNode = function(s, iri, mb, dir)
{
- var rval = 0;
-
- /* Edge comparison algorithm:
- 1. Compare adjacent bnode lists for matches.
- 1.1. If a bnode IRI is in the potential isomorphism, then the other bnode
- under the same edge must be equivalent in that isomorphism.
- 1.2. If a bnode IRI is not in the potential isomorphism yet, then the
- associated bnode *must* have a bnode with the same edge that isn't
- in the isomorphism yet to match up. Iterate over each bnode until an
- equivalent one is found.
- 1.3. Recurse to compare the chosen bnodes.
- 1.4. The least bnode is the one with the least bnode for the edge.
- */
-
- // for every bnode edge in A, make sure there's a match in B
- var iriA = a['@']['@iri'];
- var iriB = b['@']['@iri'];
- var edgesA = this.edges[dir][iriA].bnodes;
- var edgesB = this.edges[dir][iriB].bnodes;
- for(var i1 = 0; i1 < edgesA.length && rval === 0; ++i1)
+ // only do mapping if iri not already mapped
+ if(!(iri in mb.mapped))
{
- var found = false;
- var edgeA = edgesA[i1];
+ // iri now mapped
+ mb.mapped[iri] = true;
+ var top = mb.mapNode(iri);
- // step #1.1
- if(edgeA.s in iso)
+ // copy original mapping builder, loop over adjacent values
+ var original = mb.copy();
+ var values = this.edges[dir][iri].bnodes.slice();
+ var loop = Math.max(1, values.length);
+ for(var i = 0; i < loop; ++i)
{
- for(var i2 = 0;
- !found && i2 < edgesB.length && edgesB[i2].p <= edgeA.p; ++i2)
+ var m = (i === 0) ? mb : original.copy();
+
+ // map all edge nodes
+ var tmp = [];
+ for(var i2 in values)
{
- var edgeB = edgesB[i2];
- if(edgeB.p === edgeA.p && _isIsoMatch(iso, edgeA.s, edgeB.s, {}))
+ tmp.push(m.mapNode(values[i2].s));
+ }
+ m.output[top] = tmp.sort();
+ var oldCount = m.count;
+
+ // optimize away mappings that are already too large
+ var _s = _serializeMapping(m.output);
+ if(s[dir] === null || _compareSerializations(_s, s[dir].s) <= 0)
+ {
+ // recurse into adjacent values
+ for(var i2 in values)
{
- found = true;
+ // TODO: optimization: for each value, see if the value already
+ // has a shortest serialization for the given direction that
+ // can be reused
+ this.serializeBlankNode(s, values[i2].s, m, dir);
+ }
+
+ // reserialize if more nodes were mapped
+ if(m.count > oldCount)
+ {
+ _s = _serializeMapping(m.output);
+ }
+
+ // update least serialization if new one has been found
+ if(s[dir] === null ||
+ (_compareSerializations(_s, s[dir].s) <= 0 &&
+ _s.length >= s[dir].s.length))
+ {
+ s[dir] = { s: _s, m: m.mapping };
}
}
- }
- // step #1.2
- else
- {
- for(var i2 = 0; i2 < edgesB.length && edgesB[i2].p <= edgeA.p; ++i2)
- {
- var edgeB = edgesB[i2];
- if(edgeB.p === edgeA.p)
- {
- // identical edge case
- if(edgeA.s === edgeB.s)
- {
- found = true;
- break;
- }
- else if(!(edgeB.s in iso))
- {
- // add bnode pair temporarily to iso
- iso[edgeB.s] = edgeA.s;
-
- // step #1.3
- var sA = this.subjects[edgeA.s];
- var sB = this.subjects[edgeB.s];
- if(this.deepCompareBlankNodes(sA, sB, iso) === 0)
- {
- found = true;
- break;
- }
-
- // remove non-matching bnode pair from iso
- delete iso[edgeB.s];
- }
- }
- }
- }
-
- // step #1.4
- if(!found)
- {
- // no matching bnode pair found, sort order is the bnode with the
- // least bnode for edgeA's property
- rval = this.compareEdgeType(a, b, edgeA.p, dir, iso);
+
+ // rotate values
+ _rotate(values);
}
}
-
- return rval;
-};
-
-/**
- * Compares bnodes along the same edge type to determine which is less.
- *
- * @param a the first bnode.
- * @param b the second bnode.
- * @param p the property.
- * @param dir the direction of the edge ('props' or 'refs').
- * @param iso the current subgraph isomorphism for connected bnodes.
- *
- * @return -1 if a < b, 0 if a == b, 1 if a > b.
- */
-jsonld.Processor.prototype.compareEdgeType = function(a, b, p, dir, iso)
-{
- var rval = 0;
-
- // compare adjacent bnodes for smallest
- var adjA = this.getSortedAdjacents(a, p, dir, iso);
- var adjB = this.getSortedAdjacents(a, p, dir, iso);
- for(var i = 0; i < adjA.length && rval === 0; ++i)
- {
- rval = this.deepCompareBlankNodes(adjA[i], adjB[i], iso);
- }
-
- return rval;
-};
-
-/**
- * Returns the bnode properties for a particular bnode in sorted order.
- *
- * @param b the bnode.
- * @param p the property (edge type).
- * @param direction the direction of the edge ('props' or 'refs').
- * @param iso the current subgraph isomorphism for connected bnodes.
- *
- * @return the sorted bnodes for the property.
- */
-jsonld.Processor.prototype.getSortedAdjacents = function(b, p, dir, iso)
-{
- var rval = [];
-
- // add all bnodes for the given property
- var iri = b['@']['@iri'];
- var edges = this.edges[dir][iri].bnodes;
- for(var i = 0; i < edges.length && edges[i].p <= p; ++i)
- {
- if(edges[i].p === p)
- {
- rval.push(this.subjects[edges[i].s]);
- }
- }
-
- // sort bnodes
- var self = this;
- return rval.sort(function(a, b)
- {
- return self.deepCompareBlankNodes(a, b, iso);
- });
};
/**
@@ -1594,53 +1672,61 @@
*
* @param a the first blank node.
* @param b the second blank node.
- * @param iso the current subgraph isomorphism for connected bnodes.
*
* @return -1 if a < b, 0 if a == b, 1 if a > b.
*/
-jsonld.Processor.prototype.deepCompareBlankNodes = function(a, b, iso)
+jsonld.Processor.prototype.deepCompareBlankNodes = function(a, b)
{
var rval = 0;
// compare IRIs
- var iriA = a['@']['@iri'];
- var iriB = b['@']['@iri'];
+ var iriA = a[__s]['@iri'];
+ var iriB = b[__s]['@iri'];
if(iriA === iriB)
{
rval = 0;
}
- // use memoized comparison if available
- else if(iriB in this.memo[iriA])
- {
- rval = this.memo[iriA][iriB];
- }
else
{
// do shallow compare first
rval = this.shallowCompareBlankNodes(a, b);
- if(rval !== 0)
- {
- // compare done
- this.memo[iriA][iriB] = rval;
- this.memo[iriB][iriA] = -rval;
- }
+
// deep comparison is necessary
- else
+ if(rval === 0)
{
- // compare properties
- rval = this.deepCompareEdges(a, b, 'props', iso);
-
- // compare references
- if(rval === 0)
+ // compare property edges and then reference edges
+ var dirs = ['props', 'refs'];
+ for(var i = 0; rval === 0 && i < dirs.length; ++i)
{
- rval = this.deepCompareEdges(a, b, 'refs', iso);
- }
-
- // update memo
- if(!(iriB in this.memo[iriA]))
- {
- this.memo[iriA][iriB] = rval;
- this.memo[iriB][iriA] = -rval;
+ // recompute 'a' and 'b' serializations as necessary
+ var dir = dirs[i];
+ var sA = this.serializations[iriA];
+ var sB = this.serializations[iriB];
+ if(sA[dir] === null)
+ {
+ var mb = new MappingBuilder();
+ if(dir === 'refs')
+ {
+ // keep same mapping and count from 'props' serialization
+ mb.mapping = _clone(sA['props'].m);
+ mb.count = Object.keys(mb.mapping).length + 1;
+ }
+ this.serializeBlankNode(sA, iriA, mb, dir);
+ }
+ if(sB[dir] === null)
+ {
+ var mb = new MappingBuilder();
+ if(dir === 'refs')
+ {
+ // keep same mapping and count from 'props' serialization
+ mb.mapping = _clone(sB['props'].m);
+ mb.count = Object.keys(mb.mapping).length + 1;
+ }
+ this.serializeBlankNode(sB, iriB, mb, dir);
+ }
+
+ // compare serializations
+ rval = _compare(sA[dir].s, sB[dir].s);
}
}
}
@@ -1694,8 +1780,8 @@
// step #4
if(rval === 0)
{
- var edgesA = this.edges.refs[a['@']['@iri']].all;
- var edgesB = this.edges.refs[b['@']['@iri']].all;
+ var edgesA = this.edges.refs[a[__s]['@iri']].all;
+ var edgesB = this.edges.refs[b[__s]['@iri']].all;
rval = _compare(edgesA.length, edgesB.length);
}
@@ -1714,8 +1800,9 @@
/**
* Compares two edges. Edges with an IRI (vs. a bnode ID) come first, then
* alphabetically-first IRIs, then alphabetically-first properties. If a blank
- * node appears in the blank node equality memo then they will be compared
- * after properties, otherwise they won't be.
+ * node has been canonically named, then blank nodes will be compared after
+ * properties (with a preference for canonically named over non-canonically
+ * named), otherwise they won't be.
*
* @param a the first edge.
* @param b the second edge.
@@ -1728,7 +1815,7 @@
var bnodeA = _isBlankNodeIri(a.s);
var bnodeB = _isBlankNodeIri(b.s);
- var memo = this.memo;
+ var c14n = this.ng.c14n;
// if not both bnodes, one that is a bnode is greater
if(bnodeA != bnodeB)
@@ -1745,9 +1832,20 @@
{
rval = _compare(a.p, b.p);
}
- if(rval === 0 && bnodeA && a.s in memo && b.s in memo[a.s])
+
+ // do bnode IRI comparison if canonical naming has begun
+ if(rval === 0 && c14n !== null)
{
- rval = memo[a.s][b.s];
+ var c14nA = c14n.inNamespace(a.s);
+ var c14nB = c14n.inNamespace(b.s);
+ if(c14nA != c14nB)
+ {
+ rval = c14nA ? 1 : -1;
+ }
+ else if(c14nA)
+ {
+ rval = _compare(a.s, b.s);
+ }
}
}
@@ -1772,7 +1870,7 @@
var subject = this.subjects[iri];
for(var key in subject)
{
- if(key !== '@')
+ if(key !== __s)
{
// normalize to array for single codepath
var object = subject[key];
@@ -1830,7 +1928,7 @@
// check if type(s) are specified in frame and input
var type = jsonld.ns.rdf + 'type';
if(type in frame &&
- input.constructor === Object && '@' in input && type in input)
+ input.constructor === Object && __s in input && type in input)
{
var tmp = (input[type].constructor === Array) ?
input[type] : [input[type]];
@@ -1877,10 +1975,10 @@
rval = true;
}
// input must be a subject with all the given properties
- else if(input.constructor === Object && '@' in input)
+ else if(input.constructor === Object && __s in input)
{
rval = true;
- for(i in props)
+ for(var i in props)
{
if(!(props[i] in input))
{
@@ -1963,26 +2061,26 @@
if(!embedOn)
{
// if value is a subject, only use subject IRI as reference
- if(value.constructor === Object && '@' in value)
+ if(value.constructor === Object && __s in value)
{
- value = value['@'];
+ value = value[__s];
}
}
else if(
value.constructor === Object &&
- '@' in value && value['@']['@iri'] in embeds)
+ __s in value && value[__s]['@iri'] in embeds)
{
// TODO: possibly support multiple embeds in the future ... and
// instead only prevent cycles?
throw {
message: 'Multiple embeds of the same subject is not supported.',
- subject: value['@']['@iri']
+ subject: value[__s]['@iri']
};
}
// if value is a subject, do embedding and subframing
- else if(value.constructor === Object && '@' in value)
+ else if(value.constructor === Object && __s in value)
{
- embeds[value['@']['@iri']] = true;
+ embeds[value[__s]['@iri']] = true;
// if explicit is on, remove keys from value that aren't in frame
var explicitOn = ('@explicit' in frame) ?
@@ -1992,7 +2090,7 @@
for(key in value)
{
// always include subject
- if(key !== '@' && !(key in frame))
+ if(key !== __s && !(key in frame))
{
delete value[key];
}
@@ -2087,7 +2185,7 @@
var subjects = {};
for(var i in input)
{
- subjects[input[i]['@']['@iri']] = input[i];
+ subjects[input[i][__s]['@iri']] = input[i];
}
// frame input
@@ -2121,7 +2219,7 @@
*
* @return the context-neutral JSON-LD object.
*/
-jsonld.removeContext = function(input)
+jsonld.expand = jsonld.removeContext = function(input)
{
var rval = null;
@@ -2186,7 +2284,7 @@
*
* @return the output JSON-LD object.
*/
-jsonld.changeContext = function(ctx, input)
+jsonld.compact = jsonld.changeContext = function(ctx, input)
{
// remove context and then add new one
return jsonld.addContext(ctx, jsonld.removeContext(input));