Return-Path: X-Original-To: apmail-clerezza-commits-archive@www.apache.org Delivered-To: apmail-clerezza-commits-archive@www.apache.org Received: from mail.apache.org (hermes.apache.org [140.211.11.3]) by minotaur.apache.org (Postfix) with SMTP id 16FC010CC1 for ; Wed, 4 Jun 2014 21:54:26 +0000 (UTC) Received: (qmail 7042 invoked by uid 500); 4 Jun 2014 21:54:26 -0000 Delivered-To: apmail-clerezza-commits-archive@clerezza.apache.org Received: (qmail 6990 invoked by uid 500); 4 Jun 2014 21:54:26 -0000 Mailing-List: contact commits-help@clerezza.apache.org; run by ezmlm Precedence: bulk List-Help: List-Unsubscribe: List-Post: List-Id: Reply-To: dev@clerezza.apache.org Delivered-To: mailing list commits@clerezza.apache.org Received: (qmail 6928 invoked by uid 99); 4 Jun 2014 21:54:25 -0000 Received: from tyr.zones.apache.org (HELO tyr.zones.apache.org) (140.211.11.114) by apache.org (qpsmtpd/0.29) with ESMTP; Wed, 04 Jun 2014 21:54:25 +0000 Received: by tyr.zones.apache.org (Postfix, from userid 65534) id AA49893FC49; Wed, 4 Jun 2014 21:54:25 +0000 (UTC) Content-Type: text/plain; charset="us-ascii" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit From: reto@apache.org To: commits@clerezza.apache.org Date: Wed, 04 Jun 2014 21:54:27 -0000 Message-Id: In-Reply-To: <76fde1399b0a4fd8b962d1536c106717@git.apache.org> References: <76fde1399b0a4fd8b962d1536c106717@git.apache.org> X-Mailer: ASF-Git Admin Mailer Subject: [3/7] CLEREZZA-829: USing rdfstore-js to store the parsed RDFa data, working around changes in literal roundtripping using the content property (even though according to the spec this is ignored for XMLLiterals) http://git-wip-us.apache.org/repos/asf/clerezza/blob/8d34e62b/platform.editor/src/main/resources/META-INF/resources/tools/editor/scripts/rdfstore.js ---------------------------------------------------------------------- diff --git a/platform.editor/src/main/resources/META-INF/resources/tools/editor/scripts/rdfstore.js b/platform.editor/src/main/resources/META-INF/resources/tools/editor/scripts/rdfstore.js new file mode 100644 index 0000000..41ecf4d --- /dev/null +++ b/platform.editor/src/main/resources/META-INF/resources/tools/editor/scripts/rdfstore.js @@ -0,0 +1,31836 @@ +(function() { + + + if(typeof(console)=='undefined') { + console = {}; + console.log = function(e){}; + } + + window.process = {}; + process.nextTick = function(f) { + setTimeout(f,0); + }; +var Utils = {}; + + + +Utils['extends'] = function(supertype, descendant) { + descendant.prototype = new supertype(); +}; + + +Utils.stackCounterLimit = 1000; +Utils.stackCounter = 0; + +Utils.recur = function(c){ + if(Utils.stackCounter === Utils.stackCounterLimit) { + Utils.stackCounter = 0; + setTimeout(c, 0); + } else { + Utils.stackCounter++; + c(); + } +}; + +Utils.clone = function(o) { + return JSON.parse(JSON.stringify(o)); +}; + +Utils.shuffle = function(o){ //v1.0 + for(var j, x, i = o.length; i; j = parseInt(Math.random() * i), x = o[--i], o[i] = o[j], o[j] = x){}; + return o; +}; + +Utils.include = function(a,v) { + var cmp = arguments[2]; + + for(var i=(a.length-1); i>=0; i--) { + var res = false; + if(cmp == null) { + res = (a[i] === v); + } else { + res = (cmp(a[i],v) === 0); + } + + if(res === true) { + return true; + } + } + + return false; +}; + +Utils.remove = function(a,v) { + var acum = []; + for(var i=0; i tb && ta > (tb - offset)) { + return 1; + } else { + return null; + } + } else { + da = Utils.parseISO8601(stra); + db = Utils.parseISO8601(strb); + ta = da.getTime(); + tb = db.getTime(); + + var offset = 14*60*60; + if(ta < tb && (ta + offset) < tb) { + return -1; + } else if(ta > tb && (ta + offset) > tb) { + return 1; + } else { + return null; + } + } +}; + +// RDF utils +Utils.lexicalFormLiteral = function(term, env) { + var value = term.value; + var lang = term.lang; + var type = term.type; + + var indexedValue = null; + if(value != null && type != null && typeof(type) != 'string') { + var typeValue = type.value; + + if(typeValue == null) { + var typePrefix = type.prefix; + var typeSuffix = type.suffix; + + var resolvedPrefix = env.namespaces[typePrefix]; + term.type = resolvedPrefix+typeSuffix; + typeValue = resolvedPrefix+typeSuffix; + } + // normalization + if(typeValue.indexOf('hexBinary') != -1) { + indexedValue = '"' + term.value.toLowerCase() + '"^^<' + typeValue + '>'; + } else { + indexedValue = '"' + term.value + '"^^<' + typeValue + '>'; + } + } else { + if(lang == null && type == null) { + indexedValue = '"' + value + '"'; + } else if(type == null) { + indexedValue = '"' + value + '"' + "@" + lang; + } else { + // normalization + if(type.indexOf('hexBinary') != -1) { + indexedValue = '"' + term.value.toLowerCase() + '"^^<'+type+'>'; + } else { + indexedValue = '"' + term.value + '"^^<'+type+'>'; + } + } + } + return indexedValue; +}; + +Utils.lexicalFormBaseUri = function(term, env) { + var uri = null; + env = env || {}; + //console.log("*** normalizing URI token:"); + //console.log(term); + if(term.value == null) { + //console.log(" - URI has prefix and suffix"); + //console.log(" - prefix:"+term.prefix); + //console.log(" - suffixx:"+term.suffix); + var prefix = term.prefix; + var suffix = term.suffix; + var resolvedPrefix = env.namespaces[prefix]; + if(resolvedPrefix != null) { + uri = resolvedPrefix+suffix; + } else { + uri = prefix+":"+suffix; + } + } else { + //console.log(" - URI is not prefixed"); + uri = term.value; + } + + if(uri===null) { + return null; + } else { + //console.log(" - resolved URI is "+uri); + if(uri.indexOf(":") == -1) { + //console.log(" - URI is partial"); + uri = (env.base||"") + uri; // applyBaseUri + } else { + //console.log(" - URI is complete"); + } + //console.log(" -> FINAL URI: "+uri); + } + + return uri; +}; + + +Utils.lexicalFormTerm = function(term, ns) { + if(term.token === 'uri') { + return {'uri': Utils.lexicalFormBaseUri(term, ns)}; + } else if(term.token === 'literal') { + return {'literal': Utils.lexicalFormLiteral(term, ns)}; + } else if(term.token === 'blank') { + var label = '_:'+term.value; + return {'blank': label}; + } else { + throw "Error, cannot get lexical form of unknown token: "+term.token; + } +}; + +Utils.normalizeUnicodeLiterals = function (string) { + var escapedUnicode = string.match(/\\u[0-9abcdefABCDEF]{4,4}/g) || []; + var dups = {}; + for (var i = 0; i < escapedUnicode.length; i++) { + if (dups[escapedUnicode[i]] == null) { + dups[escapedUnicode[i]] = true; + string = string.replace(new RegExp("\\" + escapedUnicode[i], "g"), eval("'" + escapedUnicode[i] + "'")); + } + } + + return string; +}; + +Utils.hashTerm = function(term) { + try { + if(term == null) { + return ""; + } if(term.token==='uri') { + return "u"+term.value; + } else if(term.token === 'blank') { + return "b"+term.value; + } else if(term.token === 'literal') { + var l = "l"+term.value; + l = l + (term.type || ""); + l = l + (term.lang || ""); + + return l; + } + } catch(e) { + if(typeof(term) === 'object') { + var key = ""; + for(p in term) { + key = key + p + term[p]; + } + + return key; + } + return term; + } +}; + +// end of ./src/js-trees/src/utils.js +// exports +var InMemoryBTree = {}; + +var left = -1; +var right = 1; + + +/** + * @doc + * Implementation based on + * + */ + +/** + * Tree + * + * Implements the interface of BinarySearchTree.Tree + * + * An implementation of an in memory B-Tree. + */ + +InMemoryBTree.Tree = function(order) { + if(arguments.length != 0) { + this.order = order; + this.root = this._allocateNode(); + this.root.isLeaf = true; + this.root.level = 0; + this._diskWrite(this.root); + this._updateRootNode(this.root); + + this.comparator = function(a,b) { + if(a < b) { + return -1; + } else if(a > b){ + return 1; + } else { + return 0; + } + }; + this.merger = null; + } +}; + +/** + * Creates the new node. + * + * This class can be overwritten by different versions of + * the tree t select the right kind of node to be used + * + * @returns the new alloacted node + */ +InMemoryBTree.Tree.prototype._allocateNode = function () { + return new InMemoryBTree.Node(); +}; + +/** + * _diskWrite + * + * Persists the node to secondary memory. + */ +InMemoryBTree.Tree.prototype._diskWrite= function(node) { + // dummy implementation; + // no-op +}; + + +/** + * _diskRead + * + * Retrieves a node from secondary memory using the provided + * pointer + */ +InMemoryBTree.Tree.prototype._diskRead = function(pointer) { + // dummy implementation; + // no-op + return pointer; +}; + + +InMemoryBTree.Tree.prototype._diskDelete= function(node) { + // dummy implmentation + // no-op +}; + +/** + * _updateRootNode + * + * Updates the pointer to the root node stored in disk. + */ +InMemoryBTree.Tree.prototype._updateRootNode = function(node) { + // dummy implementation; + // no-op + return node; +}; + +InMemoryBTree.Tree.prototype.clear = function() { + this.root = this._allocateNode(); + this.root.isLeaf = true; + this.root.level = 0; + this._updateRootNode(this.root); +}; + +/** + * search + * + * Retrieves the node matching the given value. + * If no node is found, null is returned. + */ +InMemoryBTree.Tree.prototype.search = function(key, checkExists) { + var searching = true; + var node = this.root; + + while(searching) { + var idx = 0; + while(idx < node.numberActives && this.comparator(key, node.keys[idx].key) === 1) { + idx++; + } + + if(idx < node.numberActives && this.comparator(node.keys[idx].key,key) === 0) { + if(checkExists != null && checkExists == true) { + return true; + } else { + return node.keys[idx].data; + } + } else { + if(node.isLeaf === true) { + searching = false; + } else { + node = this._diskRead(node.children[idx]); + } + } + } + + return null; +}; + + +/** + * walk + * Applies a function to all the nodes key and data in the the + * tree in key order. + */ +InMemoryBTree.Tree.prototype.walk = function(f) { + this._walk(f,this.root); +}; + +InMemoryBTree.Tree.prototype._walk = function(f,node) { + if(node.isLeaf) { + for(var i=0; iindex+1; i--) { + parent.children[i] = parent.children[i-1]; + } + + parent.children[index+1] = newChild; + + for(i = parent.numberActives; i>index; i--) { + parent.keys[i] = parent.keys[i-1]; + } + + parent.keys[index] = newParentChild; + parent.numberActives++; + + this._diskWrite(newChild); + this._diskWrite(parent); + this._diskWrite(child); +}; + +/** + * insert + * + * Creates a new node with value key and data and inserts it + * into the tree. + */ +InMemoryBTree.Tree.prototype.insert = function(key,data) { + if(this.root.numberActives === (2 * this.order - 1)) { + var newRoot = this._allocateNode(); + newRoot.isLeaf = false; + newRoot.level = this.root.level + 1; + newRoot.numberActives = 0; + newRoot.children[0] = this.root; + + this._splitChild(newRoot, 0, this.root); + this.root = newRoot; + this._updateRootNode(this.root); + this._insertNonFull(newRoot, key, data); + } else { + this._insertNonFull(this.root, key, data); + } +}; + +/** + * _insertNonFull + * + * Recursive function that tries to insert the new key in + * in the prvided node, or splits it and go deeper + * in the BTree hierarchy. + */ +InMemoryBTree.Tree.prototype._insertNonFull = function(node,key,data) { + var idx = node.numberActives - 1; + + while(!node.isLeaf) { + while(idx>=0 && this.comparator(key,node.keys[idx].key) === -1) { + idx--; + } + idx++; + var child = this._diskRead(node.children[idx]); + + if(child.numberActives === 2*this.order -1) { + this._splitChild(node,idx,child); + if(this.comparator(key, node.keys[idx].key)===1) { + idx++; + } + } + node = this._diskRead(node.children[idx]); + idx = node.numberActives -1; + } + + while(idx>=0 && this.comparator(key,node.keys[idx].key) === -1) { + node.keys[idx+1] = node.keys[idx]; + idx--; + } + + node.keys[idx + 1] = {key:key, data:data}; + node.numberActives++; + this._diskWrite(node); +}; + +/** + * delete + * + * Deletes the key from the BTree. + * If the key is not found, an exception is thrown. + * + * @param key the key to be deleted + * @returns true if the key is deleted false otherwise + */ +InMemoryBTree.Tree.prototype['delete'] = function(key) { + var node = this.root; + var parent = null; + var searching = true; + var idx = null; + var lsibling = null; + var rsibling = null; + var shouldContinue = true; + + while(shouldContinue === true) { + shouldContinue = false; + + while(searching === true) { + i = 0; + + if(node.numberActives === 0) { + return false; + } + + while(i (this.order-1)) { + // The current node has (t - 1) keys but the right sibling has > (t - 1) keys + this._moveKey(parent,i,left); + } else if(lsibling != null && lsibling.numberActives > (this.order-1)) { + // The current node has (t - 1) keys but the left sibling has > (t - 1) keys + this._moveKey(parent,i,right); + } else if(lsibling != null && lsibling.numberActives === (this.order-1)) { + // The current node has (t - 1) keys but the left sibling has (t - 1) keys + node = this._mergeSiblings(parent,i,left); + } else if(rsibling != null && rsibling.numberActives === (this.order-1)){ + // The current node has (t - 1) keys but the left sibling has (t - 1) keys + node = this._mergeSiblings(parent,i,right); + } + } + } + } + + + //Case 1 : The node containing the key is found and is the leaf node. + //Also the leaf node has keys greater than the minimum required. + //Simply remove the key + if(node.isLeaf && (node.numberActives > (this.order-1))) { + this._deleteKeyFromNode(node,idx); + return true; + } + + + //If the leaf node is the root permit deletion even if the number of keys is + //less than (t - 1) + if(node.isLeaf && (node === this.root)) { + this._deleteKeyFromNode(node,idx); + return true; + } + + + //Case 2: The node containing the key is found and is an internal node + if(node.isLeaf === false) { + var tmpNode = null; + var tmpNode2 = null; + if((tmpNode=this._diskRead(node.children[idx])).numberActives > (this.order-1)) { + var subNodeIdx = this._getMaxKeyPos(tmpNode); + key = subNodeIdx.node.keys[subNodeIdx.index]; + + node.keys[idx] = key; + + //this._delete(node.children[idx],key.key); + this._diskWrite(node); + node = tmpNode; + key = key.key; + shouldContinue = true; + searching = true; + } else if ((tmpNode = this._diskRead(node.children[idx+1])).numberActives >(this.order-1)) { + var subNodeIdx = this._getMinKeyPos(tmpNode); + key = subNodeIdx.node.keys[subNodeIdx.index]; + + node.keys[idx] = key; + + //this._delete(node.children[idx+1],key.key); + this._diskWrite(node); + node = tmpNode; + key = key.key; + shouldContinue = true; + searching = true; + } else if((tmpNode = this._diskRead(node.children[idx])).numberActives === (this.order-1) && + (tmpNode2 = this._diskRead(node.children[idx+1])).numberActives === (this.order-1)) { + + var combNode = this._mergeNodes(tmpNode, node.keys[idx], tmpNode2); + node.children[idx] = combNode; + + idx++; + for(var i=idx; i this.order - 1) && searching===false) { + this._deleteKeyFromNode(node,idx); + } + + if(shouldContinue === false) { + return true; + } + } +}; + +/** + * _moveKey + * + * Move key situated at position i of the parent node + * to the left or right child at positions i-1 and i+1 + * according to the provided position + * + * @param parent the node whose is going to be moved to a child + * @param i Index of the key in the parent + * @param position left, or right + */ +InMemoryBTree.Tree.prototype._moveKey = function (parent, i, position) { + + if (position === right) { + i--; + } + + //var lchild = parent.children[i-1]; + var lchild = this._diskRead(parent.children[i]); + var rchild = this._diskRead(parent.children[i + 1]); + + + if (position == left) { + lchild.keys[lchild.numberActives] = parent.keys[i]; + lchild.children[lchild.numberActives + 1] = rchild.children[0]; + rchild.children[0] = null; + lchild.numberActives++; + + parent.keys[i] = rchild.keys[0]; + + for (var _i = 1; _i < rchild.numberActives; _i++) { + rchild.keys[_i - 1] = rchild.keys[_i]; + rchild.children[_i - 1] = rchild.children[_i]; + } + rchild.children[rchild.numberActives - 1] = rchild.children[rchild.numberActives]; + rchild.numberActives--; + } else { + rchild.children[rchild.numberActives + 1] = rchild.children[rchild.numberActives]; + for (var _i = rchild.numberActives; _i > 0; _i--) { + rchild.children[_i] = rchild.children[_i - 1]; + rchild.keys[_i] = rchild.keys[_i - 1]; + } + rchild.keys[0] = null; + rchild.children[0] = null; + + rchild.children[0] = lchild.children[lchild.numberActives]; + rchild.keys[0] = parent.keys[i]; + rchild.numberActives++; + + lchild.children[lchild.numberActives] = null; + parent.keys[i] = lchild.keys[lchild.numberActives - 1]; + lchild.keys[lchild.numberActives - 1] = null; + lchild.numberActives--; + } + + this._diskWrite(lchild); + this._diskWrite(rchild); + this._diskWrite(parent); +}; + +/** + * _mergeSiblings + * + * Merges two nodes at the left and right of the provided + * index in the parent node. + * + * @param parent the node whose children will be merged + * @param i Index of the key in the parent pointing to the nodes to merge + */ +InMemoryBTree.Tree.prototype._mergeSiblings = function (parent, index, pos) { + var i, j; + var n1, n2; + + if (index === (parent.numberActives)) { + index--; + n1 = this._diskRead(parent.children[parent.numberActives - 1]); + n2 = this._diskRead(parent.children[parent.numberActives]); + } else { + n1 = this._diskRead(parent.children[index]); + n2 = this._diskRead(parent.children[index + 1]); + } + + //Merge the current node with the left node + var newNode = this._allocateNode(); + newNode.isLeaf = n1.isLeaf; + newNode.level = n1.level; + + for (j = 0; j < this.order - 1; j++) { + newNode.keys[j] = n1.keys[j]; + newNode.children[j] = n1.children[j]; + } + + newNode.keys[this.order - 1] = parent.keys[index]; + newNode.children[this.order - 1] = n1.children[this.order - 1]; + + for (j = 0; j < this.order - 1; j++) { + newNode.keys[j + this.order] = n2.keys[j]; + newNode.children[j + this.order] = n2.children[j]; + } + newNode.children[2 * this.order - 1] = n2.children[this.order - 1]; + + parent.children[index] = newNode; + + for (j = index; j < parent.numberActives; j++) { + parent.keys[j] = parent.keys[j + 1]; + parent.children[j + 1] = parent.children[j + 2]; + } + + newNode.numberActives = n1.numberActives + n2.numberActives + 1; + parent.numberActives--; + + for (i = parent.numberActives; i < 2 * this.order - 1; i++) { + parent.keys[i] = null; + } + + if (parent.numberActives === 0 && this.root === parent) { + this.root = newNode; + if (newNode.level) { + newNode.isLeaf = false; + } else { + newNode.isLeaf = true; + } + } + + this._diskWrite(newNode); + if (this.root === newNode) { + this._updateRootNode(this.root); + } + this._diskWrite(parent); + this._diskDelete(n1); + this._diskDelete(n2); + + return newNode; +}; + +/** + * _deleteKeyFromNode + * + * Deletes the key at position index from the provided node. + * + * @param node The node where the key will be deleted. + * @param index The index of the key that will be deletd. + * @return true if the key can be deleted, false otherwise + */ +InMemoryBTree.Tree.prototype._deleteKeyFromNode = function (node, index) { + var keysMax = (2 * this.order) - 1; + if (node.numberActives < keysMax) { + keysMax = node.numberActives; + } + ; + + var i; + + if (node.isLeaf === false) { + return false; + } + + var key = node.keys[index]; + + for (i = index; i < keysMax - 1; i++) { + node.keys[i] = node.keys[i + 1]; + } + + // cleaning invalid reference + node.keys.pop(); + + node.numberActives--; + + this._diskWrite(node); + + return true; +}; + +InMemoryBTree.Tree.prototype._mergeNodes = function (n1, key, n2) { + var newNode; + var i; + + newNode = this._allocateNode(); + newNode.isLeaf = true; + + for (i = 0; i < n1.numberActives; i++) { + newNode.keys[i] = n1.keys[i]; + newNode.children[i] = n1.children[i]; + } + newNode.children[n1.numberActives] = n1.children[n1.numberActives]; + newNode.keys[n1.numberActives] = key; + + for (i = 0; i < n2.numberActives; i++) { + newNode.keys[i + n1.numberActives + 1] = n2.keys[i]; + newNode.children[i + n1.numberActives + 1] = n2.children[i]; + } + newNode.children[(2 * this.order) - 1] = n2.children[n2.numberActives]; + + newNode.numberActives = n1.numberActives + n2.numberActives + 1; + newNode.isLeaf = n1.isLeaf; + newNode.level = n1.level; + + + this._diskWrite(newNode); + // @todo + // delte old nodes from disk + return newNode; +}; + +/** + * audit + * + * Checks that the tree data structure is + * valid. + */ +InMemoryBTree.Tree.prototype.audit = function (showOutput) { + var errors = []; + var alreadySeen = []; + var that = this; + + var foundInArray = function (data) { + for (var i = 0; i < alreadySeen.length; i++) { + if (that.comparator(alreadySeen[i], data) === 0) { + var error = " !!! duplicated key " + data; + if (showOutput === true) { + console.log(error); + } + errors.push(error); + } + } + }; + + var length = null; + var that = this; + this.walkNodes(function (n) { + if (showOutput === true) { + console.log("--- Node at " + n.level + " level"); + console.log(" - leaf? " + n.isLeaf); + console.log(" - num actives? " + n.numberActives); + console.log(" - keys: "); + } + for (var i = n.numberActives; i < n.keys.length; i++) { + if (n.keys[i] != null) { + if (showOutput === true) { + console.log(" * warning : redundant key data"); + errors.push(" * warning : redundant key data"); + } + } + } + + for (var i = n.numberActives + 1; i < n.children.length; i++) { + if (n.children[i] != null) { + if (showOutput === true) { + console.log(" * warning : redundant children data"); + errors.push(" * warning : redundant key data"); + } + } + } + + + if (n.isLeaf === false) { + for (var i = 0; i < n.numberActives; i++) { + var maxLeft = that._diskRead(n.children[i]).keys[that._diskRead(n.children[i]).numberActives - 1 ].key; + var minRight = that._diskRead(n.children[i + 1]).keys[0].key; + if (showOutput === true) { + console.log(" " + n.keys[i].key + "(" + maxLeft + "," + minRight + ")"); + } + if (that.comparator(n.keys[i].key, maxLeft) === -1) { + var error = " !!! value max left " + maxLeft + " > key " + n.keys[i].key; + if (showOutput === true) { + console.log(error); + } + errors.push(error); + } + if (that.comparator(n.keys[i].key, minRight) === 1) { + var error = " !!! value min right " + minRight + " < key " + n.keys[i].key; + if (showOutput === true) { + console.log(error); + } + errors.push(error); + } + + foundInArray(n.keys[i].key); + alreadySeen.push(n.keys[i].key); + } + } else { + if (length === null) { + length = n.level; + } else { + if (length != n.level) { + var error = " !!! Leaf node with wrong level value"; + if (showOutput === true) { + console.log(error); + } + errors.push(error); + } + } + for (var i = 0; i < n.numberActives; i++) { + if (showOutput === true) { + console.log(" " + n.keys[i].key); + } + foundInArray(n.keys[i].key); + alreadySeen.push(n.keys[i].key); + + } + } + + if (n != that.root) { + if (n.numberActives > ((2 * that.order) - 1)) { + if (showOutput === true) { + var error = " !!!! MAX num keys restriction violated "; + } + console.log(error); + errors.push(error); + } + if (n.numberActives < (that.order - 1)) { + if (showOutput === true) { + var error = " !!!! MIN num keys restriction violated "; + } + console.log(error); + errors.push(error); + } + + } + }); + + return errors; +}; + +/** + * _getMaxKeyPos + * + * Used to get the position of the MAX key within the subtree + * @return An object containing the key and position of the key + */ +InMemoryBTree.Tree.prototype._getMaxKeyPos = function (node) { + var node_pos = {}; + + while (true) { + if (node === null) { + break; + } + + if (node.isLeaf === true) { + node_pos.node = node; + node_pos.index = node.numberActives - 1; + return node_pos; + } else { + node_pos.node = node; + node_pos.index = node.numberActives - 1; + node = this._diskRead(node.children[node.numberActives]); + } + } + + return node_pos; +}; + +/** + * _getMinKeyPos + * + * Used to get the position of the MAX key within the subtree + * @return An object containing the key and position of the key + */ +InMemoryBTree.Tree.prototype._getMinKeyPos = function (node) { + var node_pos = {}; + + while (true) { + if (node === null) { + break; + } + + if (node.isLeaf === true) { + node_pos.node = node; + node_pos.index = 0; + return node_pos; + } else { + node_pos.node = node; + node_pos.index = 0; + node = this._diskRead(node.children[0]); + } + } + + return node_pos; +}; + + +/** + * Node + * + * Implements the interface of BinarySearchTree.Node + * + * A Tree node augmented with BTree + * node structures + */ +InMemoryBTree.Node = function() { + this.numberActives = 0; + this.isLeaf = null; + this.keys = []; + this.children = []; + this.level = 0; +}; + +// end of ./src/js-trees/src/in_memory_b_tree.js +// exports +var QuadIndexCommon = {}; + +/** + * NodeKey + * + * Implements the interface of BinarySearchTree.Node + * + * A Tree node augmented with BPlusTree + * node structures + */ +QuadIndexCommon.NodeKey = function(components, order) { + this.subject = components.subject; + this.predicate = components.predicate; + this.object = components.object; + this.graph = components.graph; + this.order = order; +}; + +QuadIndexCommon.NodeKey.prototype.comparator = function(keyPattern) { + for(var i=0; i keyPattern[component]) { + return 1 + } + } + } + + return 0; +}; + +/** + * Pattern + * + * A pattern with some variable components + */ +QuadIndexCommon.Pattern = function (components) { + this.subject = components.subject; + this.predicate = components.predicate; + this.object = components.object; + this.graph = components.graph; + this.indexKey = []; + + this.keyComponents = {}; + + var order = []; + var indif = []; + var components = ['subject', 'predicate', 'object', 'graph']; + + // components must have been already normalized and + // inserted in the lexicon. + // OIDs retrieved from the lexicon *are* numbers so + // they can be told apart from variables (strings) + for (var i = 0; i < components.length; i++) { + if (typeof(this[components[i]]) === 'string') { + indif.push(components[i]); + this.keyComponents[components[i]] = null; + } else { + order.push(components[i]); + this.keyComponents[components[i]] = this[components[i]]; + this.indexKey.push(components[i]); + } + } + + this.order = order.concat(indif); + this.key = new QuadIndexCommon.NodeKey(this.keyComponents, this.order); +}; + +// end of ./src/js-rdf-persistence/src/quad_index_common.js +// exports +var QuadIndex = {}; + +// imports +var BaseTree = InMemoryBTree; + +QuadIndex.Tree = function(params,callback) { + if(arguments != 0) { + this.componentOrder = params.componentOrder; + + + // @todo change this if using the file backed implementation + BaseTree.Tree.call(this, params.order, params['name'], params['persistent'], params['cacheMaxSize']); + + this.comparator = function (a, b) { + for (var i = 0; i < this.componentOrder.length; i++) { + var component = this.componentOrder[i]; + var vala = a[component]; + var valb = b[component]; + if (vala < valb) { + return -1; + } else if (vala > valb) { + return 1; + } + } + return 0; + }; + + this.rangeComparator = function (a, b) { + for (var i = 0; i < this.componentOrder.length; i++) { + var component = this.componentOrder[i]; + if (b[component] == null || a[component] == null) { + return 0; + } else { + if (a[component] < b[component]) { + return -1 + } else if (a[component] > b[component]) { + return 1 + } + } + } + + return 0; + }; + + if(callback!=null) { + callback(this); + } + } +}; + +Utils['extends'](BaseTree.Tree, QuadIndex.Tree); + +QuadIndex.Tree.prototype.insert = function(quad, callback) { + BaseTree.Tree.prototype.insert.call(this, quad, null); + if(callback) + callback(true); + + return true +}; + +QuadIndex.Tree.prototype.search = function(quad, callback) { + var result = BaseTree.Tree.prototype.search.call(this, quad, true); // true -> check exists : not present in all the b-tree implementations, check first. + if(callback) + callback(result); + + return result; +}; + +QuadIndex.Tree.prototype.range = function (pattern, callback) { + var result = null; + if (typeof(this.root) === 'string') { + result = this._rangeTraverse(this, this._diskRead(this.root), pattern); + } else { + result = this._rangeTraverse(this, this.root, pattern); + } + + if (callback) + callback(result); + + return result; +}; + +QuadIndex.Tree.prototype._rangeTraverse = function(tree,node, pattern) { + var patternKey = pattern.key; + var acum = []; + var pendingNodes = [node]; + var node, idxMin, idxMax; + while(pendingNodes.length > 0) { + node = pendingNodes.shift(); + idxMin = 0; + + while(idxMin < node.numberActives && tree.rangeComparator(node.keys[idxMin].key,patternKey) === -1) { + idxMin++; + } + if(node.isLeaf === true) { + idxMax = idxMin; + + while(idxMax < node.numberActives && tree.rangeComparator(node.keys[idxMax].key,patternKey) === 0) { + acum.push(node.keys[idxMax].key); + idxMax++; + } + + } else { + var pointer = node.children[idxMin]; + var childNode = tree._diskRead(pointer); + pendingNodes.push(childNode); + + var idxMax = idxMin; + while(true) { + if(idxMax < node.numberActives && tree.rangeComparator(node.keys[idxMax].key,patternKey) === 0) { + acum.push(node.keys[idxMax].key); + idxMax++; + childNode = tree._diskRead(node.children[idxMax]); + pendingNodes.push(childNode); + } else { + break; + } + } + } + } + return acum; +}; + +// end of ./src/js-rdf-persistence/src/quad_index.js +// exports +var QuadBackend = {}; + + +// imports + + +/* + * "perfect" indices for RDF indexing + * + * SPOG (?, ?, ?, ?), (s, ?, ?, ?), (s, p, ?, ?), (s, p, o, ?), (s, p, o, g) + * GP (?, ?, ?, g), (?, p, ?, g) + * OGS (?, ?, o, ?), (?, ?, o, g), (s, ?, o, g) + * POG (?, p, ?, ?), (?, p, o, ?), (?, p, o, g) + * GSP (s, ?, ?, g), (s, p, ?, g) + * OS (s, ?, o, ?) + */ +QuadBackend.QuadBackend = function (configuration, callback) { + if (arguments != 0) { + this.indexMap = {}; + this.treeOrder = configuration['treeOrder']; + this.indices = ['SPOG', 'GP', 'OGS', 'POG', 'GSP', 'OS']; + this.componentOrders = { + SPOG:['subject', 'predicate', 'object', 'graph'], + GP:['graph', 'predicate', 'subject', 'object'], + OGS:['object', 'graph', 'subject', 'predicate'], + POG:['predicate', 'object', 'graph', 'subject'], + GSP:['graph', 'subject', 'predicate', 'object'], + OS:['object', 'subject', 'predicate', 'graph'] + }; + + for (var i = 0; i < this.indices.length; i++) { + var indexKey = this.indices[i]; + this.indexMap[indexKey] = new QuadIndex.Tree({order:this.treeOrder, + componentOrder:this.componentOrders[indexKey], + persistent:configuration['persistent'], + name:(configuration['name'] || "") + indexKey, + cacheMaxSize:configuration['cacheMaxSize']}); + } + + if (callback) + callback(this); + } +}; + +QuadBackend.QuadBackend.prototype.clear = function() { + for(var i=0; i') { + var value = literalString.substring(1,parts-1); + var type = literalString.substring(parts+3, literalString.length-1); + + return {token: "literal", value:value, type:type}; + } + + var value = literalString.substring(1,literalString.length-1); + return {token:"literal", value:value}; +}; + +Lexicon.Lexicon.prototype.parseUri = function(uriString) { + return {token: "uri", value:uriString}; +}; + +Lexicon.Lexicon.prototype.retrieve = function(oid) { + try { + if(oid === this.defaultGraphOid) { + return({ token: "uri", + value:this.defaultGraphUri, + prefix: null, + suffix: null, + defaultGraph: true }); + } else { + var maybeUri = this.OIDToUri['u'+oid]; + if(maybeUri != null) { + return(this.parseUri(maybeUri)); + } else { + var maybeLiteral = this.OIDToLiteral['l'+oid]; + if(maybeLiteral != null) { + return(this.parseLiteral(maybeLiteral)); + } else { + var maybeBlank = this.OIDToBlank[""+oid]; + if(maybeBlank != null) { + return({token:"blank", value:"_:"+oid}); + } else { + throw("Null value for OID"); + } + } + } + } + } catch(e) { + console.log("error in lexicon retrieving OID:"); + console.log(oid); + if(e.message || e.stack) { + if(e.message) { + console.log(e.message); + } + if(e.stack) { + console.log(e.stack); + } + } else { + console.log(e); + } + throw new Error("Unknown retrieving OID in lexicon:"+oid); + + } +}; + +Lexicon.Lexicon.prototype.clear = function() { + this.uriToOID = {}; + this.OIDToUri = {}; + + this.literalToOID = {}; + this.OIDToLiteral = {}; + + this.blankToOID = {}; + this.OIDToBlank = {}; +}; + +Lexicon.Lexicon.prototype.unregister = function (quad, key) { + try { + this.unregisterTerm(quad.subject.token, key.subject); + this.unregisterTerm(quad.predicate.token, key.predicate); + this.unregisterTerm(quad.object.token, key.object); + if (quad.graph != null) { + this.unregisterTerm(quad.graph.token, key.graph); + } + return(true); + } catch (e) { + console.log("Error unregistering quad"); + console.log(e.message); + return(false); + } +}; + +Lexicon.Lexicon.prototype.unregisterTerm = function (kind, oid) { + if (kind === 'uri') { + if (oid != this.defaultGraphOid) { + var oidStr = 'u' + oid; + var uri = this.OIDToUri[oidStr]; // = uri; + var oidCounter = this.uriToOID[uri]; // =[oid, 0]; + + var counter = oidCounter[1]; + if ("" + oidCounter[0] === "" + oid) { + if (counter === 0) { + delete this.OIDToUri[oidStr]; + delete this.uriToOID[uri]; + // delete the graph oid from known graphs + // in case this URI is a graph identifier + delete this.knownGraphs[oid]; + } else { + this.uriToOID[uri] = [oid, counter - 1]; + } + } else { + throw("Not matching OID : " + oid + " vs " + oidCounter[0]); + } + } + } else if (kind === 'literal') { + this.oidCounter++; + var oidStr = 'l' + oid; + var literal = this.OIDToLiteral[oidStr]; // = literal; + var oidCounter = this.literalToOID[literal]; // = [oid, 0]; + + var counter = oidCounter[1]; + if ("" + oidCounter[0] === "" + oid) { + if (counter === 0) { + delete this.OIDToLiteral[oidStr]; + delete this.literalToOID[literal]; + } else { + this.literalToOID[literal] = [oid, counter - 1]; + } + } else { + throw("Not matching OID : " + oid + " vs " + oidCounter[0]); + } + + } else if (kind === 'blank') { + delete this.OIDToBlank["" + oid]; + } +}; + +// end of ./src/js-rdf-persistence/src/lexicon.js +// exports +var NetworkTransport = {}; + +NetworkTransport.load = function (uri, accept, callback, redirect) { + var transport = jQuery; + + transport.ajax({ + url:uri, + headers:{"Accept":accept}, + + success:function (data, status, xhr) { + if (("" + xhr.status)[0] == '2') { + var headers = xhr.getAllResponseHeaders().split("\n"); + var acum = {}; + for (var i = 0; i < headers.length; i++) { + var header = headers[i].split(":"); + acum[header[0]] = header[1]; + } + + callback(true, {headers:acum, + data:data}); + } + }, + + error:function (xhr, textStatus, ex) { + if (("" + xhr.status)[0] == '3') { + if (redirection == 0) { + callback(false, 500); + } else { + var location = (xhr.getAllResponseHeaders()["Location"] || xhr.getAllResponseHeaders()["location"]); + if (location != null) { + NetworkTransport.load(location, accept, callback, (redirection - 1)); + } else { + callback(false, 500); + } + } + } else { + callback(false, xhr.statusCode()); + } + } + }); +}; + +// end of ./src/js-communication/src/ajax_transport.js + +/** + * Javascript implementation of JSON-LD. + * + * @author Dave Longley + * + * Copyright (c) 2011 Digital Bazaar, Inc. All rights reserved. + */ + +var jsonldParser = null; + +(function() +{ + +// used by Exception +var _setMembers = function(self, obj) +{ + self.stack = ''; + for(var key in obj) + { + self[key] = obj[key]; + } +}; + +// define jsonld +if(typeof(window) !== 'undefined') +{ + var jsonld = window.jsonld = window.jsonld || {}; + Exception = function(obj) + { + _setMembers(this, obj); + }; + + // define js 1.8.5 Object.keys method unless present + if(!Object.keys) + { + Object.keys = function(o) + { + if(o !== Object(o)) + { + throw new TypeError('Object.keys called on non-object'); + } + var rval = []; + for(var p in o) + { + if(Object.prototype.hasOwnProperty.call(o, p)) + { + rval.push(p); + } + } + return rval; + }; + } + + if (!Array.prototype.filter) + { + Array.prototype.filter = function(fun /*, thisp */) + { + "use strict"; + + if (this == null) + throw new TypeError(); + + var t = Object(this); + var len = t.length >>> 0; + if (typeof fun != "function") + throw new TypeError(); + + var res = []; + var thisp = arguments[1]; + for (var i = 0; i < len; i++) + { + if (i in t) + { + var val = t[i]; // in case fun mutates this + if (fun.call(thisp, val, i, t)) + res.push(val); + } + } + + return res; + }; + } + +} +// define node.js module +else if(typeof(module) !== 'undefined' && module.exports) +{ + var jsonld = {}; + //module.exports = jsonld; + Exception = function(obj) + { + _setMembers(this, obj); + this.stack = new Error().stack; + }; +} + + +jsonldParser = jsonld; + +var defaultContext = { "rdf": "http://www.w3.org/1999/02/22-rdf-syntax-ns#", + "rdfs": "http://www.w3.org/2000/01/rdf-schema#", + "owl": "http://www.w3.org/2002/07/owl#", + "xsd": "http://www.w3.org/2001/XMLSchema#", + "dcterms": "http://purl.org/dc/terms/", + "foaf": "http://xmlns.com/foaf/0.1/", + "cal": "http://www.w3.org/2002/12/cal/ical#", + "vcard": "http://www.w3.org/2006/vcard/ns# ", + "geo": "http://www.w3.org/2003/01/geo/wgs84_pos#", + "cc": "http://creativecommons.org/ns#", + "sioc": "http://rdfs.org/sioc/ns#", + "doap": "http://usefulinc.com/ns/doap#", + "com": "http://purl.org/commerce#", + "ps": "http://purl.org/payswarm#", + "gr": "http://purl.org/goodrelations/v1#", + "sig": "http://purl.org/signature#", + "ccard": "http://purl.org/commerce/creditcard#" + }; + +/* + * Globals and helper functions. + */ +var ns = +{ + xsd: 'http://www.w3.org/2001/XMLSchema#' +}; + +var xsd = +{ + 'boolean': ns.xsd + 'boolean', + 'double': ns.xsd + 'double', + 'integer': ns.xsd + 'integer' +}; + +/** + * Sets a subject's property to the given object value. If a value already + * exists, it will be appended to an array. + * + * @param s the subject. + * @param p the property. + * @param o the object. + */ +var _setProperty = function(s, p, o) +{ + if(p in s) + { + if(s[p].constructor === Array) + { + s[p].push(o); + } + else + { + s[p] = [s[p], o]; + } + } + else + { + s[p] = o; + } +}; + +/** + * Clones an object, array, or string/number. If cloning an object, the keys + * will be sorted. + * + * @param value the value to clone. + * + * @return the cloned value. + */ +var _clone = function(value) +{ + var rval; + + if(value.constructor === Object) + { + rval = {}; + var keys = Object.keys(value).sort(); + for(var i in keys) + { + var key = keys[i]; + rval[key] = _clone(value[key]); + } + } + else if(value.constructor === Array) + { + rval = []; + for(var i in value) + { + rval[i] = _clone(value[i]); + } + } + else + { + rval = value; + } + + return rval; +}; + +/** + * Gets the keywords from a context. + * + * @param ctx the context. + * + * @return the keywords. + */ +var _getKeywords = function(ctx) +{ + // TODO: reduce calls to this function by caching keywords in processor + // state + + var rval = + { + '@id': '@id', + '@language': '@language', + '@literal': '@literal', + '@type': '@type' + }; + + if(ctx) + { + // gather keyword aliases from context + var keywords = {}; + for(var key in ctx) + { + if(ctx[key].constructor === String && ctx[key] in rval) + { + keywords[ctx[key]] = key; + } + } + + // overwrite keywords + for(var key in keywords) + { + rval[key] = keywords[key]; + } + } + + return rval; +}; + +/** + * Gets the iri associated with a term. + * + * @param ctx the context. + * @param term the term. + * + * @return the iri or NULL. + */ +var _getTermIri = function(ctx, term) +{ + var rval = null; + if(term in ctx) + { + if(ctx[term].constructor === String) + { + rval = ctx[term]; + } + else if(ctx[term].constructor === Object && '@id' in ctx[term]) + { + rval = ctx[term]['@id']; + } + } + return rval; +}; + +/** + * Compacts an IRI into a term or prefix if it can be. IRIs will not be + * compacted to relative IRIs if they match the given context's default + * vocabulary. + * + * @param ctx the context to use. + * @param iri the IRI to compact. + * @param usedCtx a context to update if a value was used from "ctx". + * + * @return the compacted IRI as a term or prefix or the original IRI. + */ +var _compactIri = function(ctx, iri, usedCtx) +{ + var rval = null; + + // check the context for a term that could shorten the IRI + // (give preference to terms over prefixes) + for(var key in ctx) + { + // skip special context keys (start with '@') + if(key.length > 0 && key[0] !== '@') + { + // compact to a term + if(iri === _getTermIri(ctx, key)) + { + rval = key; + if(usedCtx !== null) + { + usedCtx[key] = _clone(ctx[key]); + } + break; + } + } + } + + // term not found, if term is @type, use keyword + if(rval === null && iri === '@type') + { + rval = _getKeywords(ctx)['@type']; + } + + // term not found, check the context for a prefix + if(rval === null) + { + for(var key in ctx) + { + // skip special context keys (start with '@') + if(key.length > 0 && key[0] !== '@') + { + // see if IRI begins with the next IRI from the context + var ctxIri = _getTermIri(ctx, key); + if(ctxIri !== null) + { + var idx = iri.indexOf(ctxIri); + + // compact to a prefix + if(idx === 0 && iri.length > ctxIri.length) + { + rval = key + ':' + iri.substr(ctxIri.length); + if(usedCtx !== null) + { + usedCtx[key] = _clone(ctx[key]); + } + break; + } + } + } + } + } + + // could not compact IRI + if(rval === null) + { + rval = iri; + } + + return rval; +}; + +/** + * Expands a term into an absolute IRI. The term may be a regular term, a + * prefix, a relative IRI, or an absolute IRI. In any case, the associated + * absolute IRI will be returned. + * + * @param ctx the context to use. + * @param term the term to expand. + * @param usedCtx a context to update if a value was used from "ctx". + * + * @return the expanded term as an absolute IRI. + */ +var _expandTerm = function(ctx, term, usedCtx) +{ + var rval = term; + + // get JSON-LD keywords + var keywords = _getKeywords(ctx); + + // 1. If the property has a colon, it is a prefix or an absolute IRI: + var idx = term.indexOf(':'); + if(idx !== -1) + { + // get the potential prefix + var prefix = term.substr(0, idx); + + // expand term if prefix is in context, otherwise leave it be + if(prefix in ctx) + { + // prefix found, expand property to absolute IRI + var iri = _getTermIri(ctx, prefix); + rval = iri + term.substr(idx + 1); + if(usedCtx !== null) + { + usedCtx[prefix] = _clone(ctx[prefix]); + } + } + } + // 2. If the property is in the context, then it's a term. + else if(term in ctx) + { + rval = _getTermIri(ctx, term); + if(usedCtx !== null) + { + usedCtx[term] = _clone(ctx[term]); + } + } + // 3. The property is a keyword. + else + { + for(var key in keywords) + { + if(term === keywords[key]) + { + rval = key; + break; + } + } + } + + return rval; +}; + +/** + * Sorts the keys in a context. + * + * @param ctx the context to sort. + * + * @return the sorted context. + */ +var _sortContextKeys = function(ctx) +{ + // sort keys + var rval = {}; + var keys = Object.keys(ctx).sort(); + for(var k in keys) + { + var key = keys[k]; + rval[key] = ctx[key]; + } + return rval; +}; + +/** + * Gets whether or not a value is a reference to a subject (or a subject with + * no properties). + * + * @param value the value to check. + * + * @return true if the value is a reference to a subject, false if not. + */ +var _isReference = function(value) +{ + // Note: A value is a reference to a subject if all of these hold true: + // 1. It is an Object. + // 2. It is has an @id key. + // 3. It has only 1 key. + return (value !== null && + value.constructor === Object && + '@id' in value && + Object.keys(value).length === 1); +}; + +/** + * Gets whether or not a value is a subject with properties. + * + * @param value the value to check. + * + * @return true if the value is a subject with properties, false if not. + */ +var _isSubject = function(value) +{ + var rval = false; + + // Note: A value is a subject if all of these hold true: + // 1. It is an Object. + // 2. It is not a literal. + // 3. It has more than 1 key OR any existing key is not '@id'. + if(value !== null && value.constructor === Object && !('@literal' in value)) + { + var keyCount = Object.keys(value).length; + rval = (keyCount > 1 || !('@id' in value)); + } + + return rval; +}; + +/* + * JSON-LD API. + */ + +/** + * Normalizes a JSON-LD object. + * + * @param input the JSON-LD object to normalize. + * + * @return the normalized JSON-LD object. + */ +jsonld.normalize = function(input) +{ + return new Processor().normalize(input); +}; + +/** + * Removes the context from a JSON-LD object, expanding it to full-form. + * + * @param input the JSON-LD object to remove the context from. + * + * @return the context-neutral JSON-LD object. + */ +jsonld.expand = function(input) +{ + return new Processor().expand({}, null, input); +}; + +/** + * Expands the given JSON-LD object and then compacts it using the + * given context. + * + * @param ctx the new context to use. + * @param input the input JSON-LD object. + * + * @return the output JSON-LD object. + */ +jsonld.compact = function(ctx, input) +{ + var rval = null; + + // TODO: should context simplification be optional? (ie: remove context + // entries that are not used in the output) + + if(input !== null) + { + // fully expand input + input = jsonld.expand(input); + + var tmp; + if(input.constructor === Array) + { + rval = []; + tmp = input; + } + else + { + tmp = [input]; + } + + // merge context if it is an array + if(ctx.constructor === Array) + { + ctx = jsonld.mergeContexts({}, ctx); + } + + for(var i in tmp) + { + // setup output context + var ctxOut = {}; + + // compact + var out = new Processor().compact(_clone(ctx), null, tmp[i], ctxOut); + + // add context if used + if(Object.keys(ctxOut).length > 0) + { + // sort context keys + ctxOut = _sortContextKeys(ctxOut); + + // sort keys + var keys = Object.keys(out); + keys.sort(); + + // put @context first + keys.unshift('@context'); + out['@context'] = ctxOut; + + // order keys in output + var ordered = {}; + for(var k in keys) + { + var key = keys[k]; + ordered[key] = out[key]; + } + out = ordered; + } + + if(rval === null) + { + rval = out; + } + else + { + rval.push(out); + } + } + } + + return rval; +}; + +/** + * Merges one context with another. + * + * @param ctx1 the context to overwrite/append to. + * @param ctx2 the new context to merge onto ctx1. + * + * @return the merged context. + */ +jsonld.mergeContexts = function(ctx1, ctx2) +{ + // merge first context if it is an array + if(ctx1.constructor === Array) + { + ctx1 = jsonld.mergeContexts({}, ctx1); + } + + // copy context to merged output + var merged = _clone(ctx1); + + if(ctx2.constructor === Array) + { + // merge array of contexts in order + for(var i in ctx2) + { + merged = jsonld.mergeContexts(merged, ctx2[i]); + } + } + else + { + // if the new context contains any IRIs that are in the merged context, + // remove them from the merged context, they will be overwritten + for(var key in ctx2) + { + // ignore special keys starting with '@' + if(key.indexOf('@') !== 0) + { + for(var mkey in merged) + { + if(merged[mkey] === ctx2[key]) + { + // FIXME: update related coerce rules + delete merged[mkey]; + break; + } + } + } + } + + // merge contexts + for(var key in ctx2) + { + merged[key] = _clone(ctx2[key]); + } + } + + return merged; +}; + +/** + * Expands a term into an absolute IRI. The term may be a regular term, a + * prefix, a relative IRI, or an absolute IRI. In any case, the associated + * absolute IRI will be returned. + * + * @param ctx the context to use. + * @param term the term to expand. + * + * @return the expanded term as an absolute IRI. + */ +jsonld.expandTerm = _expandTerm; + +/** + * Compacts an IRI into a term or prefix if it can be. IRIs will not be + * compacted to relative IRIs if they match the given context's default + * vocabulary. + * + * @param ctx the context to use. + * @param iri the IRI to compact. + * + * @return the compacted IRI as a term or prefix or the original IRI. + */ +jsonld.compactIri = function(ctx, iri) +{ + return _compactIri(ctx, iri, null); +}; + +/** + * Frames JSON-LD input. + * + * @param input the JSON-LD input. + * @param frame the frame to use. + * @param options framing options to use. + * + * @return the framed output. + */ +jsonld.frame = function(input, frame, options) +{ + return new Processor().frame(input, frame, options); +}; + +/** + * Generates triples given a JSON-LD input. Each triple that is generated + * results in a call to the given callback. The callback takes 3 parameters: + * subject, property, and object. If the callback returns false then this + * method will stop generating triples and return. If the callback is null, + * then an array with triple objects containing "s", "p", "o" properties will + * be returned. + * + * The object or "o" property will be a JSON-LD formatted object. + * + * @param input the JSON-LD input. + * @param callback the triple callback. + * + * @return an array of triple objects if callback is null, null otherwise. + */ +jsonld.toTriples = function(input, graph, callback) +{ + var rval = null; + + // normalize input + var normalized = jsonld.normalize(input); + + // setup default callback + callback = callback || null; + if(callback === null) + { + rval = []; + callback = function(s, p, o) + { + rval.push({'subject': Utils.lexicalFormTerm(s), + 'predicate': Utils.lexicalFormTerm(p), + 'object': Utils.lexicalFormTerm(o), + 'graph': graph}); + }; + } + + // generate triples + var quit = false; + for(var i1 in normalized) + { + var e = normalized[i1]; + var s = e['@id']; + if(s[0] == "_") { + s = {'token':'blank', 'value':s.split(":")[1]}; + } else { + s = {'token':'uri', 'value':s}; + } + + for(var p in e) + { + if(p !== '@id') + { + var obj = e[p]; + if(obj.constructor !== Array) + { + obj = [obj]; + } + for(var i2 in obj) + { + var obji2 = obj[i2]; + if(p === '@type' || p === 'http://www.w3.org/1999/02/22-rdf-syntax-ns#type') { + p = 'http://www.w3.org/1999/02/22-rdf-syntax-ns#type'; + obji2 = {'token':'uri', 'value':obji2}; + } else if(typeof(obji2) === 'string') { + obji2 = {'token': 'literal', 'value':obji2}; + } else if(obji2['@id'] != null) { + if(obji2['@id'][0] == "_") { + obji2 = {'token':'blank', 'value':obji2['@id'].split(":")[1]}; + } else { + obji2 = {'token':'uri', 'value':obji2['@id']}; + } + } else if(obji2['@type'] != null) { + obji2 = {'token':'literal', 'value':obji2['@literal'], 'type':obji2['@type']}; + } else if(obji2['@language'] != null) { + obji2 = {'token':'literal', 'value':obji2['@literal'], 'lang':obji2['@language']}; + } + + quit = (callback(s, {'token':'uri', 'value':p}, obji2) === false); + if(quit) + { + break; + } + } + if(quit) + { + break; + } + } + } + if(quit) + { + break; + } + } + + return rval; +}; + +/** + * Resolves external @context URLs. Every @context URL in the given JSON-LD + * object is resolved using the given URL-resolver function. Once all of + * the @contexts have been resolved, the given result callback is invoked. + * + * @param input the JSON-LD input object (or array). + * @param resolver the resolver method that takes a URL and a callback that + * receives a JSON-LD serialized @context or null on error (with + * optional an error object as the second parameter). + * @param callback the callback to be invoked with the fully-resolved + * JSON-LD output (object or array) or null on error (with an + * optional error array as the second parameter). + */ +jsonld.resolve = function(input, resolver, callback) +{ + // find all @context URLs + var urls = {}; + var findUrls = function(input, replace) + { + if(input.constructor === Array) + { + for(var i in input) + { + findUrls(input[i]); + } + } + else if(input.constructor === Object) + { + for(var key in input) + { + if(key === '@context') + { + // @context is an array that might contain URLs + if(input[key].constructor === Array) + { + var list = input[key]; + for(var i in list) + { + if(list[i].constructor === String) + { + // replace w/resolved @context if appropriate + if(replace) + { + list[i] = urls[list[i]]; + } + // unresolved @context found + else + { + urls[list[i]] = {}; + } + } + } + } + else if(input[key].constructor === String) + { + // replace w/resolved @context if appropriate + if(replace) + { + input[key] = urls[input[key]]; + } + // unresolved @context found + else + { + urls[input[key]] = {}; + } + } + } + } + } + }; + findUrls(input, false); + + // state for resolving URLs + var count = Object.keys(urls).length; + var errors = null; + + if(count === 0) + { + callback(input, errors); + } + else + { + // resolve all URLs + for(var url in urls) + { + resolver(url, function(result, error) + { + --count; + + if(result === null) + { + errors = errors || []; + errors.push({ url: url, error: error }); + } + else + { + try + { + if(result.constructor === String) + { + urls[url] = JSON.parse(result)['@context']; + } + else + { + urls[url] = result['@context']; + } + } + catch(ex) + { + errors = errors || []; + errors.push({ url: url, error: ex }); + } + } + + if(count === 0) + { + if(errors === null) + { + findUrls(input, true); + } + callback(input, errors); + } + }); + } + } +}; + +// TODO: organizational rewrite + +/** + * Constructs a new JSON-LD processor. + */ +var Processor = function() +{ +}; + +/** + * Recursively compacts a value. This method will compact IRIs to prefixes or + * terms and do reverse type coercion to compact a value. + * + * @param ctx the context to use. + * @param property the property that points to the value, NULL for none. + * @param value the value to compact. + * @param usedCtx a context to update if a value was used from "ctx". + * + * @return the compacted value. + */ +Processor.prototype.compact = function(ctx, property, value, usedCtx) +{ + var rval; + + // get JSON-LD keywords + var keywords = _getKeywords(ctx); + + if(value === null) + { + // return null, but check coerce type to add to usedCtx + rval = null; + this.getCoerceType(ctx, property, usedCtx); + } + else if(value.constructor === Array) + { + // recursively add compacted values to array + rval = []; + for(var i in value) + { + rval.push(this.compact(ctx, property, value[i], usedCtx)); + } + } + // graph literal/disjoint graph + else if( + value.constructor === Object && + '@id' in value && value['@id'].constructor === Array) + { + rval = {}; + rval[keywords['@id']] = this.compact( + ctx, property, value['@id'], usedCtx); + } + // recurse if value is a subject + else if(_isSubject(value)) + { + // recursively handle sub-properties that aren't a sub-context + rval = {}; + for(var key in value) + { + if(value[key] !== '@context') + { + // set object to compacted property, only overwrite existing + // properties if the property actually compacted + var p = _compactIri(ctx, key, usedCtx); + if(p !== key || !(p in rval)) + { + // FIXME: clean old values from the usedCtx here ... or just + // change usedCtx to be built at the end of processing? + rval[p] = this.compact(ctx, key, value[key], usedCtx); + } + } + } + } + else + { + // get coerce type + var coerce = this.getCoerceType(ctx, property, usedCtx); + + // get type from value, to ensure coercion is valid + var type = null; + if(value.constructor === Object) + { + // type coercion can only occur if language is not specified + if(!('@language' in value)) + { + // type must match coerce type if specified + if('@type' in value) + { + type = value['@type']; + } + // type is ID (IRI) + else if('@id' in value) + { + type = '@id'; + } + // can be coerced to any type + else + { + type = coerce; + } + } + } + // type can be coerced to anything + else if(value.constructor === String) + { + type = coerce; + } + + // types that can be auto-coerced from a JSON-builtin + if(coerce === null && + (type === xsd['boolean'] || type === xsd['integer'] || + type === xsd['double'])) + { + coerce = type; + } + + // do reverse type-coercion + if(coerce !== null) + { + // type is only null if a language was specified, which is an error + // if type coercion is specified + if(type === null) + { + throw { + message: 'Cannot coerce type when a language is specified. ' + + 'The language information would be lost.' + }; + } + // if the value type does not match the coerce type, it is an error + else if(type !== coerce) + { + throw new Exception({ + message: 'Cannot coerce type because the type does ' + + 'not match.', + type: type, + expected: coerce + }); + } + // do reverse type-coercion + else + { + if(value.constructor === Object) + { + if('@id' in value) + { + rval = value['@id']; + } + else if('@literal' in value) + { + rval = value['@literal']; + } + } + else + { + rval = value; + } + + // do basic JSON types conversion + if(coerce === xsd['boolean']) + { + rval = (rval === 'true' || rval != 0); + } + else if(coerce === xsd['double']) + { + rval = parseFloat(rval); + } + else if(coerce === xsd['integer']) + { + rval = parseInt(rval); + } + } + } + // no type-coercion, just change keywords/copy value + else if(value.constructor === Object) + { + rval = {}; + for(var key in value) + { + rval[keywords[key]] = value[key]; + } + } + else + { + rval = _clone(value); + } + + // compact IRI + if(type === '@id') + { + if(rval.constructor === Object) + { + rval[keywords['@id']] = _compactIri( + ctx, rval[keywords['@id']], usedCtx); + } + else + { + rval = _compactIri(ctx, rval, usedCtx); + } + } + } + + return rval; +}; + +/** + * Recursively expands a value using the given context. Any context in + * the value will be removed. + * + * @param ctx the context. + * @param property the property that points to the value, NULL for none. + * @param value the value to expand. + * + * @return the expanded value. + */ +Processor.prototype.expand = function(ctx, property, value) +{ + var rval; + + // TODO: add data format error detection? + + // value is null, nothing to expand + if(value === null) + { + rval = null; + } + // if no property is specified and the value is a string (this means the + // value is a property itself), expand to an IRI + else if(property === null && value.constructor === String) + { + rval = _expandTerm(ctx, value, null); + } + else if(value.constructor === Array) + { + // recursively add expanded values to array + rval = []; + for(var i in value) + { + rval.push(this.expand(ctx, property, value[i])); + } + } + else if(value.constructor === Object) + { + // if value has a context, use it + if('@context' in value) + { + ctx = jsonld.mergeContexts(ctx, value['@context']); + } + + // recursively handle sub-properties that aren't a sub-context + rval = {}; + for(var key in value) + { + // preserve frame keywords + if(key === '@embed' || key === '@explicit' || + key === '@default' || key === '@omitDefault') + { + _setProperty(rval, key, _clone(value[key])); + } + else if(key !== '@context') + { +