Revision 9a2b736416bc4dc0727c9c517c242fc3669afcc1 authored by Eric Prud'hommeaux on 04 January 2018, 21:35:30 UTC, committed by Eric Prud'hommeaux on 04 January 2018, 21:35:30 UTC
1 parent 679a517
ShExValidator.js
/* ShExValidator - javascript module to validate a graph with respect to Shape Expressions
*
* Status: 1/2 tested, no known bugs.
*
* TODO:
* constraint violation reporting.
*/
var ShExValidator = (function () {
var UNBOUNDED = -1;
// interface constants
var Start = { term: "START" }
var InterfaceOptions = {
"or": {
"oneOf": "exactly one disjunct must pass",
"someOf": "one or more disjuncts must pass",
"firstOf": "disjunct evaluation stops after one passes"
},
"partition": {
"greedy": "each triple constraint consumes all triples matching predicate and object",
"exhaustive": "search all mappings of triples to triple constriant"
}
};
var VERBOSE = "VERBOSE" in process.env;
// **ShExValidator** provides ShEx utility functions
var ProgramFlowError = { type: "ProgramFlowError", errors: { type: "UntrackedError" } };
var N3Util = require("n3").Util;
function getLexicalValue (term) {
return N3Util.isIRI(term) ? term :
N3Util.isLiteral(term) ? N3Util.getLiteralValue(term) :
term.substr(2); // bnodes start with "_:"
}
var XSD = "http://www.w3.org/2001/XMLSchema#";
var integerDatatypes = [
XSD + "integer",
XSD + "nonPositiveInteger",
XSD + "negativeInteger",
XSD + "long",
XSD + "int",
XSD + "short",
XSD + "byte",
XSD + "nonNegativeInteger",
XSD + "unsignedLong",
XSD + "unsignedInt",
XSD + "unsignedShort",
XSD + "unsignedByte",
XSD + "positiveInteger"
];
var decimalDatatypes = [
XSD + "decimal",
].concat(integerDatatypes);
var numericDatatypes = [
XSD + "float",
XSD + "double"
].concat(decimalDatatypes);
var numericParsers = {};
numericParsers[XSD + "integer"] = function (label, parseError) {
if (!(label.match(/^[+-]?[0-9]+$/))) {
parseError("illegal integer value '" + label + "'");
}
return parseInt(label);
};
numericParsers[XSD + "decimal"] = function (label, parseError) {
if (!(label.match(/^[+-]?(?:[0-9]*\.[0-9]+|[0-9]+)$/))) { // XSD has no pattern for decimal?
parseError("illegal decimal value '" + label + "'");
}
return parseFloat(label);
};
const DECIMAL_REGEX = /^[+\-]?(?:[0-9]+(?:\.[0-9]*)?|\.[0-9]+)(?:[eE][+\-]?[0-9]+)?$/;
numericParsers[XSD + "float" ] = function (label, parseError) {
if (label === "NaN") return NaN;
if (label === "INF") return Infinity;
if (label === "-INF") return -Infinity;
if (!(label.match(DECIMAL_REGEX))) { // XSD has no pattern for float?
parseError("illegal float value '" + label + "'");
}
return parseFloat(label);
};
numericParsers[XSD + "double" ] = function (label, parseError) {
if (label === "NaN") return NaN;
if (label === "INF") return Infinity;
if (label === "-INF") return -Infinity;
if (!(label.match(DECIMAL_REGEX))) {
parseError("illegal double value '" + label + "'");
}
return Number(label);
};
testRange = function (value, datatype, parseError) {
const ranges = {
// integer -1 0 1 +1 | "" -1.0 +1.0 1e0 NaN INF
// decimal -1 0 1 +1 -1.0 +1.0 | "" 1e0 NaN INF
// float -1 0 1 +1 -1.0 +1.0 1e0 1E0 NaN INF -INF | "" +INF
// double -1 0 1 +1 -1.0 +1.0 1e0 1E0 NaN INF -INF | "" +INF
// nonPositiveInteger -1 0 +0 -0 | 1 +1 1a a1
// negativeInteger -1 | 0 +0 -0 1
// long -1 0 1 +1 |
// int -1 0 1 +1 |
// short -32768 0 32767 | -32769 32768
// byte -128 0 127 | "" -129 128
// nonNegativeInteger 0 -0 +0 1 +1 | -1
// unsignedLong 0 1 | -1
// unsignedInt 0 1 | -1
// unsignedShort 0 65535 | -1 65536
// unsignedByte 0 255 | -1 256
// positiveInteger 1 | -1 0
// string "" "a" "0"
// boolean true false 0 1 | "" TRUE FALSE tRuE fAlSe -1 2 10 01
// dateTime "2012-01-02T12:34:56.78Z" | "" "2012-01-02T" "2012-01-02"
integer: { min: -Infinity , max: Infinity },
decimal: { min: -Infinity , max: Infinity },
float: { min: -Infinity , max: Infinity },
double: { min: -Infinity , max: Infinity },
nonPositiveInteger: { min: -Infinity , max: 0 },
negativeInteger: { min: -Infinity , max: -1 },
long: { min: -9223372036854775808, max: 9223372036854775807 },
int: { min: -2147483648 , max: 2147483647 },
short: { min: -32768 , max: 32767 },
byte: { min: -128 , max: 127 },
nonNegativeInteger: { min: 0 , max: Infinity },
unsignedLong: { min: 0 , max: 18446744073709551615 },
unsignedInt: { min: 0 , max: 4294967295 },
unsignedShort: { min: 0 , max: 65535 },
unsignedByte: { min: 0 , max: 255 },
positiveInteger: { min: 1 , max: Infinity }
}
var parms = ranges[datatype.substr(XSD.length)];
if (!parms) throw Error("unexpected datatype: " + datatype);
if (value < parms.min) {
parseError("\"" + value + "\"^^<" + datatype + "> is less than the min:", parms.min);
} else if (value > parms.max) {
parseError("\"" + value + "\"^^<" + datatype + "> is greater than the max:", parms.min);
}
};
/*
function intSubType (spec, label, parseError) {
var ret = numericParsers[XSD + "integer"](label, parseError);
if ("min" in spec && ret < spec.min)
parseError("illegal " + XSD + spec.type + " value '" + label + "' should not be < " + spec.min);
if ("max" in spec && ret > spec.max)
parseError("illegal " + XSD + spec.type + " value '" + label + "' should not be > " + spec.max);
return ret;
}
[{type: "nonPositiveInteger", max: 0},
{type: "negativeInteger", max: -1},
{type: "long", min: -9223372036854775808, max: 9223372036854775807}, // beyond IEEE double
{type: "int", min: -2147483648, max: 2147483647},
{type: "short", min: -32768, max: 32767},
{type: "byte", min: -128, max: 127},
{type: "nonNegativeInteger", min: 0},
{type: "unsignedLong", min: 0, max: 18446744073709551615},
{type: "unsignedInt", min: 0, max: 4294967295},
{type: "unsignedShort", min: 0, max: 65535},
{type: "unsignedByte", min: 0, max: 255},
{type: "positiveInteger", min: 1}].forEach(function (i) {
numericParsers[XSD + i.type ] = function (label, parseError) {
return intSubType(i, label, parseError);
};
});
*/
var stringTests = {
length : function (v, l) { return v.length === l; },
minlength: function (v, l) { return v.length >= l; },
maxlength: function (v, l) { return v.length <= l; }
};
var numericValueTests = {
mininclusive : function (n, m) { return n >= m; },
minexclusive : function (n, m) { return n > m; },
maxinclusive : function (n, m) { return n <= m; },
maxexclusive : function (n, m) { return n < m; }
};
var decimalLexicalTests = {
totaldigits : function (v, d) {
var m = v.match(/[0-9]/g);
return m && m.length <= d;
},
fractiondigits: function (v, d) {
var m = v.match(/^[+-]?[0-9]*\.?([0-9]*)$/);
return m && m[1].length <= d;
}
};
function ldify (term) {
if (term[0] !== "\"")
return term;
var ret = { value: N3Util.getLiteralValue(term) };
var dt = N3Util.getLiteralType(term);
if (dt &&
dt !== "http://www.w3.org/2001/XMLSchema#string" &&
dt !== "http://www.w3.org/1999/02/22-rdf-syntax-ns#langString")
ret.type = dt;
var lang = N3Util.getLiteralLanguage(term)
if (lang)
ret.language = lang;
return ret;
}
function isTerm (t) {
return typeof t !== "object" || "value" in t && Object.keys(t).reduce((r, k) => {
return r === false ? r : ["value", "type", "language"].indexOf(k) !== -1;
}, true);
}
/* ShExValidator_constructor - construct an object for validating a schema.
*
* schema: a structure produced by a ShEx parser or equivalent.
* options: object with controls for
* lax(true): boolean: whine about missing types in schema.
* diagnose(false): boolean: makde validate return a structure with errors.
*/
function ShExValidator_constructor(schema, options) {
if (!(this instanceof ShExValidator_constructor))
return new ShExValidator_constructor(schema, options);
this.type = "ShExValidator";
options = options || {};
this.options = options;
this.options.or = this.options.or || "someOf";
this.options.partition = this.options.partition || "exhaustive";
if (!("noCache" in options && options.noCache))
this.known = {};
var _ShExValidator = this;
this.schema = schema;
this._expect = this.options.lax ? noop : expect; // report errors on missing types.
this._optimize = {}; // optimizations:
// hasRepeatedGroups: whether there are patterns like (:p1 ., :p2 .)*
this.reset = function () { }; // included in case we need it later.
// var regexModule = this.options.regexModule || require("../lib/regex/nfax-val-1err");
var regexModule = this.options.regexModule || require("../lib/regex/threaded-val-nerr");
/* getAST - compile a traditional regular expression abstract syntax tree.
* Tested but not used at present.
*/
this.getAST = function () {
return {
type: "AST",
shapes: Object.keys(this.schema.shapes).reduce(function (ret, label) {
ret[label] = {
type: "ASTshape",
expression: _compileShapeToAST(_ShExValidator.schema.shapes[label].expression, [], _ShExValidator.schema)
};
return ret;
}, {})
};
};
/* indexTripleConstraints - compile regular expression and index triple constraints
*/
this.indexTripleConstraints = function (expression) {
// list of triple constraints from (:p1 ., (:p2 . | :p3 .))
var tripleConstraints = [];
if (expression)
indexTripleConstraints_dive(expression);
return tripleConstraints;
function indexTripleConstraints_dive (expr) {
if (expr.type === "TripleConstraint")
tripleConstraints.push(expr)-1;
else if (expr.type === "OneOf" || expr.type === "EachOf")
expr.expressions.forEach(function (nested) {
indexTripleConstraints_dive(nested);
});
else if (expr.type === "Inclusion")
indexTripleConstraints_dive(schema.productions[expr.include]);
// @@TODO shape.virtual, shape.inherit
else
runtimeError("unexpected expr type: " + expr.type);
};
};
/* validate - test point in db against the schema for labelOrShape
* depth: level of recurssion; for logging.
*/
this.validate = function (db, point, labelOrShape, depth, seen) {
// default to schema's start shape
if (typeof point === "object") {
var shapeMap = point;
if (this.options.results === "api") {
return shapeMap.map(pair => {
var res = this.validate(db, pair.node, pair.shape, depth, seen);
return {
node: pair.node,
shape: pair.shape,
status: "errors" in res ? "nonconformant" : "conformant",
appinfo: res
};
});
}
var results = shapeMap.reduce((ret, pair) => {
var res = this.validate(db, pair.node, pair.shape, depth, seen);
return "errors" in res ?
{ passes: ret.passes, failures: ret.failures.concat(res) } :
{ passes: ret.passes.concat(res), failures: ret.failures } ;
}, {passes: [], failures: []});
if (false && this.options.results === "api") {
var ret = {};
function _add (n, s, r) {
if (!(n in ret)) {
ret[n] = [{shape: s, result: r}];
return;
}
if (ret[n].filter(p => { return p.shape === s; }))
return;
ret[n].push({shape: s, results: r});
}
results.passes.forEach(p => { _add(p.node, p.shape, true); });
results.failures.forEach(p => { _add(p.node, p.shape, false); });
return ret;
}
if (results.failures.length) {
return results.failures.length !== 1 ?
{ type: "FailureList", errors: results.failures } :
results.failures [0];
} else {
return results.passes.length !== 1 ?
{ type: "SolutionList", solutions: results.passes } :
results.passes [0];
}
}
if (!labelOrShape || labelOrShape === Start) {
if (!schema.start)
runtimeError("start production not defined");
labelOrShape = schema.start;
}
if (typeof labelOrShape !== "string")
return this._validateShapeExpr(db, point, labelOrShape, "_: -start-", depth, seen);
if (!(labelOrShape in this.schema.shapes))
runtimeError("shape " + labelOrShape + " not found in:\n" + Object.keys(this.schema.shapes).map(s => " " + s).join("\n"));
var shapeLabel = labelOrShape; // for clarity
if (seen === undefined)
seen = {};
var seenKey = point + "|" + shapeLabel;
if (seenKey in seen)
return {
type: "Recursion",
node: ldify(point),
shape: shapeLabel
};
if ("known" in this && seenKey in this.known)
return this.known[seenKey];
seen[seenKey] = { point: point, shape: shapeLabel };
var ret = this._validateShapeExpr(db, point, schema.shapes[shapeLabel], shapeLabel, depth, seen);
delete seen[seenKey];
if ("known" in this)
this.known[seenKey] = ret;
return ret;
}
this._validateShapeExpr = function (db, point, shapeExpr, shapeLabel, depth, seen) {
if (point === "")
throw Error("validation needs a valid focus node");
if (shapeExpr.type === "NodeConstraint") {
var errors = this._errorsMatchingNodeConstraint(point, shapeExpr, null);
return errors.length ? {
type: "Failure",
node: ldify(point),
shape: shapeLabel,
errors: errors.map(function (miss) {
return {
type: "NodeConstraintViolation",
shapeExpr: shapeExpr
};
})
} : {
type: "NodeTest",
node: ldify(point),
shape: shapeLabel,
shapeExpr: shapeExpr
};
} else if (shapeExpr.type === "Shape") {
return this._validateShape(db, point, regexModule.compile(schema, shapeExpr),
shapeExpr, shapeLabel, depth, seen);
} else if (shapeExpr.type === "ShapeRef") {
return this._validateShapeExpr(db, point, schema.shapes[shapeExpr.reference], shapeExpr.reference, depth, seen);
} else if (shapeExpr.type === "ShapeExternal") {
return this.options.validateExtern(db, point, shapeLabel, depth, seen);
} else if (shapeExpr.type === "ShapeOr") {
var errors = [];
for (var i = 0; i < shapeExpr.shapeExprs.length; ++i) {
var nested = shapeExpr.shapeExprs[i];
var sub = this._validateShapeExpr(db, point, nested, shapeLabel, depth, seen);
if ("errors" in sub)
errors.push(sub);
else
return { type: "ShapeOrResults", solution: sub };
}
return { type: "ShapeOrFailure", errors: errors };
} else if (shapeExpr.type === "ShapeNot") {
var sub = this._validateShapeExpr(db, point, shapeExpr.shapeExpr, shapeLabel, depth, seen);
if ("errors" in sub)
return { type: "ShapeNotResults", solution: sub };
else
return { type: "ShapeNotFailure", errors: sub };
} else if (shapeExpr.type === "ShapeAnd") {
var passes = [];
for (var i = 0; i < shapeExpr.shapeExprs.length; ++i) {
var nested = shapeExpr.shapeExprs[i];
var sub = this._validateShapeExpr(db, point, nested, shapeLabel, depth, seen);
if ("errors" in sub)
return { type: "ShapeAndFailure", errors: [sub] };
else
passes.push(sub);
}
return { type: "ShapeAndResults", solutions: passes };
} else
throw Error("expected one of Shape{Ref,And,Or} or NodeConstraint, got " + JSON.stringify(shapeExpr));
}
this._validateShape = function (db, point, regexEngine, shape, shapeLabel, depth, seen) {
var _ShExValidator = this;
// logging stuff
if (depth === undefined)
depth = 0;
var padding = (new Array(depth + 1)).join(" "); // AKA " ".repeat(depth);
function _log () {
if (!VERBOSE) { return; }
console.log(padding + Array.prototype.join.call(arguments, ""));
}
var ret = null;
var startAcionStorage = {}; // !!! need test to see this write to results structure.
if ("startActs" in schema && !this.semActHandler.dispatchAll(schema.startActs, null, startAcionStorage))
return {
type: "Failure",
node: ldify(point),
shape: shapeLabel,
errors: ['semact failure']
}; // some semAct aborted !! return real error
_log("validating <" + point + "> as <" + shapeLabel + ">");
var outgoing = indexNeighborhood(db.getTriplesByIRI(point, null, null, null).sort(byObject));
var incoming = indexNeighborhood(db.getTriplesByIRI(null, null, point, null).sort(bySubject));
var neighborhood = outgoing.triples.concat(incoming.triples); // @@ make fancy array holder.
var constraintList = this.indexTripleConstraints(shape.expression);
var tripleList = constraintList.reduce(function (ret, constraint, ord) {
// subject and object depend on direction of constraint.
var searchSubject = constraint.inverse ? null : point;
var searchObject = constraint.inverse ? point : null;
var index = constraint.inverse ? incoming : outgoing;
// get triples matching predciate
var matchPredicate = index.byPredicate[constraint.predicate] ||
[]; // empty list when no triple matches that constraint
function _errorsByShapeLabel (focus, shapeLabel) {
var sub = _ShExValidator.validate(db, focus, shapeLabel, depth + 1, seen);
return "errors" in sub ? sub.errors : [];
}
function _errorsByShapeExpr (focus, shapeExpr) {
var sub = _ShExValidator._validateShapeExpr(db, focus, shapeExpr, shapeLabel, depth, seen);
return "errors" in sub ? sub.errors : [];
}
// strip to triples matching value constraints (apart from @<someShape>)
var matchConstraints = _ShExValidator._triplesMatchingShapeExpr(
matchPredicate,
constraint.valueExpr,
constraint.inverse,
/* _ShExValidator.options.partition === "exhaustive" ? undefined : */ _errorsByShapeLabel,
/* _ShExValidator.options.partition === "exhaustive" ? undefined : */ _errorsByShapeExpr
);
matchConstraints.hits.forEach(function (t) {
ret.constraintList[neighborhood.indexOf(t)].push(ord);
});
matchConstraints.misses.forEach(function (t) {
ret.misses[neighborhood.indexOf(t.triple)] = {constraintNo: ord, errors: t.errors};
});
return ret;
}, { misses: {}, constraintList:_seq(neighborhood.length).map(function () { return []; }) }); // start with [[],[]...]
_log("constraints by triple: ", JSON.stringify(tripleList.constraintList));
var extras = []; // triples accounted for by EXTRA
var misses = tripleList.constraintList.reduce(function (ret, constraints, ord) {
if (constraints.length === 0 && // matches no constraints
ord < outgoing.triples.length && // not an incoming triple
ord in tripleList.misses) { // predicate matched some constraint(s)
if (shape.extra !== undefined &&
shape.extra.indexOf(neighborhood[ord].predicate) !== -1) {
extras.push(ord);
} else { // not declared extra
ret.push({ // so it's a missed triple.
tripleNo: ord,
constraintNo: tripleList.misses[ord].constraintNo,
errors: tripleList.misses[ord].errors
});
}
}
return ret;
}, []);
var xp = crossProduct(tripleList.constraintList);
var partitionErrors = [];
while (misses.length === 0 && xp.next() && ret === null) {
// caution: early continues
var usedTriples = []; // [{s1,p1,o1},{s2,p2,o2}] implicated triples -- used for messages
var constraintMatchCount = // [2,1,0,1] how many triples matched a constraint
_seq(neighborhood.length).map(function () { return 0; });
var tripleToConstraintMapping = xp.get(); // [0,1,0,3] mapping from triple to constraint
// Triples not mapped to triple constraints are not allowed in closed shapes.
if (shape.closed) {
var unexpectedTriples = outgoing.triples.filter((t, i) => {
return tripleToConstraintMapping[i] === undefined && // didn't match a constraint
extras.indexOf(i) === -1; // wasn't in EXTRAs.
});
if (unexpectedTriples.length > 0) {
partitionErrors.push({
errors: [
{
type: "ClosedShapeViolation",
unexpectedTriples: unexpectedTriples
}
]
});
continue; // closed shape violation.
}
}
// Set usedTriples and constraintMatchCount.
tripleToConstraintMapping.forEach(function (tpNumber, ord) {
if (tpNumber !== undefined) {
usedTriples.push(neighborhood[ord]);
++constraintMatchCount[tpNumber];
}
});
// Pivot to triples by constraint.
function _constraintToTriples () {
var cll = constraintList.length;
return tripleToConstraintMapping.slice().
reduce(function (ret, c, ord) {
if (c !== undefined)
ret[c].push(ord);
return ret;
}, _seq(cll).map(function () { return []; }));
}
tripleToConstraintMapping.slice().sort(function (a,b) { return a-b; }).filter(function (i) { // sort constraint numbers
return i !== undefined;
}).map(function (n) { return n + " "; }).join(""); // e.g. 0 0 1 3
function _recurse (point, shapeLabel) {
return _ShExValidator.validate(db, point, shapeLabel, depth+1, seen);
}
function _direct (point, shapeExpr) {
return _ShExValidator._validateShapeExpr(db, point, shapeExpr, shapeLabel, depth, seen);
}
function _testExpr (term, valueExpr, recurse, direct) {
return _ShExValidator._errorsMatchingShapeExpr(term, valueExpr, recurse, direct)
}
var results = regexEngine.match(db, point, constraintList, _constraintToTriples(), tripleToConstraintMapping, neighborhood, _recurse, _direct, this.semActHandler, _testExpr, null);
if (false) {// testing parity between two engines
var nfa = require("../lib/regex/nfax-val-1err").compile(schema, shape);
var fromNFA = nfa.match(db, point, constraintList, _constraintToTriples(), tripleToConstraintMapping, neighborhood, _recurse, this.semActHandler, _testExpr, null);
if ("errors" in fromNFA !== "errors" in results)
{ throw Error(JSON.stringify(results) + " vs " + JSON.stringify(fromNFA)); }
}
if ("errors" in results) {
partitionErrors.push({
errors: results.errors
});
if (_ShExValidator.options.partition !== "exhaustive")
break;
else
continue;
}
_log("post-regexp " + usedTriples.join(" "));
var possibleRet = { type: "ShapeTest", node: ldify(point), shape: shapeLabel };
if (Object.keys(results).length > 0) // only include .solution for non-empty pattern
possibleRet.solution = results;
if ("semActs" in shape &&
!this.semActHandler.dispatchAll(shape.semActs, results, possibleRet)) {
// some semAct aborted
partitionErrors.push({
errors: [ { type: "SemActFailure", errors: [{ type: "UntrackedSemActFailure" }] } ]
});
if (_ShExValidator.options.partition !== "exhaustive")
break;
else
continue;
}
_log("final " + usedTriples.join(" "));
ret = possibleRet;
// alts.push(tripleToConstraintMapping);
}
if (ret === null/* !! && this.options.diagnose */) {
var missErrors = misses.map(function (miss) {
var t = neighborhood[miss.tripleNo];
return {
type: "TypeMismatch",
triple: {type: "TestedTriple", subject: t.subject, predicate: t.predicate, object: ldify(t.object)},
constraint: constraintList[miss.constraintNo],
errors: miss.errors
};
});
ret = {
type: "Failure",
node: ldify(point),
shape: shapeLabel,
errors: missErrors.concat(partitionErrors.length === 1 ? partitionErrors[0].errors : partitionErrors)
};
}
if (VERBOSE) { // remove N3jsTripleToString
neighborhood.forEach(function (t) {
delete t.toString;
});
}
if ("startActs" in schema && depth === 0) {
ret.startActs = schema.startActs;
}
_log("</" + shapeLabel + ">");
return addShapeAttributes(ret);
function addShapeAttributes (ret) {
if ("annotations" in shape)
ret.annotations = shape.annotations;
return ret;
}
};
this._triplesMatchingShapeExpr = function (triples, valueExpr, inverse, recurse, direct) {
var _ShExValidator = this;
var misses = [];
var hits = [];
triples.forEach(function (triple) {
var value = inverse ? triple.subject : triple.object;
var errors = valueExpr === undefined ?
[] :
_ShExValidator._errorsMatchingShapeExpr(value, valueExpr, recurse, direct);
if (errors.length === 0) {
hits.push(triple);
} else if (hits.indexOf(triple) === -1) {
misses.push({triple: triple, errors: errors});
}
});
return { hits: hits, misses: misses };
}
this._errorsMatchingShapeExpr = function (value, valueExpr, recurse, direct) {
var _ShExValidator = this;
if (valueExpr.type === "NodeConstraint") {
return this._errorsMatchingNodeConstraint(value, valueExpr, null);
} else if (valueExpr.type === "Shape") {
return direct === undefined ? [] : direct(value, valueExpr);
} else if (valueExpr.type === "ShapeRef") {
return recurse ? recurse(value, valueExpr.reference) : [];
} else if (valueExpr.type === "ShapeOr") {
var ret = [];
for (var i = 0; i < valueExpr.shapeExprs.length; ++i) {
var nested = _ShExValidator._errorsMatchingShapeExpr(value, valueExpr.shapeExprs[i], recurse, direct);
if (nested.length === 0)
return nested;
ret = ret.concat(nested);
}
return ret;
} else if (valueExpr.type === "ShapeAnd") {
return valueExpr.shapeExprs.reduce(function (ret, nested, iter) {
return ret.concat(_ShExValidator._errorsMatchingShapeExpr(value, nested, recurse, direct, true));
}, []);
} else if (valueExpr.type === "ShapeNot") {
var ret = _ShExValidator._errorsMatchingShapeExpr(value, valueExpr.shapeExpr, recurse, direct, true);
return ret.length ?
[] :
["Error validating " + value + " as " + JSON.stringify(valueExpr) + ": expected NOT to pass"];
} else {
throw Error("unknown value expression type '" + valueExpr.type + "'");
}
};
/* _errorsMatchingNodeConstraint - return whether the value matches the value
* expression without checking shape references.
*/
this._errorsMatchingNodeConstraint = function (value, valueExpr, recurse) {
var errors = [];
var label = N3Util.isLiteral(value) ? N3Util.getLiteralValue(value) :
N3Util.isBlank(value) ? value.substring(2) :
value;
var dt = N3Util.isLiteral(value) ? N3Util.getLiteralType(value) : null;
var numeric = integerDatatypes.indexOf(dt) !== -1 ? XSD + "integer" : numericDatatypes.indexOf(dt) !== -1 ? dt : undefined;
function validationError () {
var errorStr = Array.prototype.join.call(arguments, "");
errors.push("Error validating " + value + " as " + JSON.stringify(valueExpr) + ": " + errorStr);
return false;
}
// if (negated) ;
if (false) {
// wildcard -- ignore
} else {
if ("nodeKind" in valueExpr) {
if (["iri", "bnode", "literal", "nonliteral"].indexOf(valueExpr.nodeKind) === -1) {
validationError("unknown node kind '" + valueExpr.nodeKind + "'");
}
if (N3Util.isBlank(value)) {
if (valueExpr.nodeKind === "iri" || valueExpr.nodeKind === "literal") {
validationError("blank node found when " + valueExpr.nodeKind + " expected");
}
} else if (N3Util.isLiteral(value)) {
if (valueExpr.nodeKind !== "literal") {
validationError("literal found when " + valueExpr.nodeKind + " expected");
}
} else if (valueExpr.nodeKind === "bnode" || valueExpr.nodeKind === "literal") {
validationError("iri found when " + valueExpr.nodeKind + " expected");
}
}
if (valueExpr.datatype && valueExpr.values ) validationError("found both datatype and values in " +tripleConstraint);
if (valueExpr.datatype) {
if (!N3Util.isLiteral(value)) {
validationError("mismatched datatype: " + value + " is not a literal with datatype " + valueExpr.datatype);
}
else if (N3Util.getLiteralType(value) !== valueExpr.datatype) {
validationError("mismatched datatype: " + N3Util.getLiteralType(value) + " !== " + valueExpr.datatype);
}
else if (numeric) {
testRange(numericParsers[numeric](label, validationError), valueExpr.datatype, validationError);
}
else if (valueExpr.datatype === XSD + "boolean") {
if (label !== "true" && label !== "false" && label !== "1" && label !== "0")
validationError("illegal boolean value: " + label);
}
else if (valueExpr.datatype === XSD + "dateTime") {
if (!label.match(/^[+-]?\d{4}-[01]\d-[0-3]\dT[0-5]\d:[0-5]\d:[0-5]\d(\.\d+)?([+-][0-2]\d:[0-5]\d|Z)?$/))
validationError("illegal dateTime value: " + label);
}
}
if (valueExpr.values) {
if (N3Util.isLiteral(value) && valueExpr.values.reduce((ret, v) => {
if (ret) return true;
var ld = ldify(value);
if (v.type === "Language") {
return v.languageTag === ld.language; // @@ use equals/normalizeTest
}
if (!(typeof v === "object" && "value" in v))
return false;
return v.value === ld.value &&
v.type === ld.type &&
v.language === ld.language;
}, false)) {
// literal match
} else if (valueExpr.values.indexOf(value) !== -1) {
// trivial match
} else {
if (!(valueExpr.values.some(function (valueConstraint) {
if (typeof valueConstraint === "object" && !("value" in valueConstraint)) { // isTerm me -- strike "value" in
if (!("type" in valueConstraint))
runtimeError("expected "+JSON.stringify(valueConstraint)+" to have a 'type' attribute.");
var stemRangeTypes = [
"Language",
"IriStem", "LiteralStem", "LanguageStem",
"IriStemRange", "LiteralStemRange", "LanguageStemRange"
];
if (stemRangeTypes.indexOf(valueConstraint.type) === -1)
runtimeError("expected type attribute '"+valueConstraint.type+"' to be in '"+stemRangeTypes+"'.");
/* expect N3.js literals with {Literal,Language}StemRange
* or non-literals with IriStemRange
*/
function normalizedTest (val, ref, func) {
if (N3Util.isLiteral(val)) {
if (["LiteralStem", "LiteralStemRange"].indexOf(valueConstraint.type) !== -1) {
return func(N3Util.getLiteralValue(val), ref);
} else if (["LanguageStem", "LanguageStemRange"].indexOf(valueConstraint.type) !== -1) {
return func(N3Util.getLiteralLanguage(val), ref);
} else {
return validationError("literal " + val + " not comparable with non-literal " + ref);
}
} else {
if (["IriStem", "IriStemRange"].indexOf(valueConstraint.type) === -1) {
return validationError("nonliteral " + val + " not comparable with literal " + JSON.stringify(ref));
} else {
return func(val, ref);
}
}
}
function startsWith (val, ref) {
return normalizedTest(val, ref, (l, r) => {
return (valueConstraint.type === "LanguageStem" ||
valueConstraint.type === "LanguageStemRange") ?
// rfc4647 basic filtering
(l === r || l[r.length] === "-") :
// simple substring
l.startsWith(r);
});
}
function equals (val, ref) {
return normalizedTest(val, ref, (l, r) => { return l === r; });
}
if (!isTerm(valueConstraint.stem)) {
expect(valueConstraint.stem, "type", "Wildcard");
// match whatever but check exclusions below
} else {
if (!(startsWith(value, valueConstraint.stem))) {
return false;
}
}
if (valueConstraint.exclusions) {
return !valueConstraint.exclusions.some(function (c) {
if (!isTerm(c)) {
if (!("type" in c))
runtimeError("expected "+JSON.stringify(c)+" to have a 'type' attribute.");
var stemTypes = ["IriStem", "LiteralStem", "LanguageStem"];
if (stemTypes.indexOf(c.type) === -1)
runtimeError("expected type attribute '"+c.type+"' to be in '"+stemTypes+"'.");
return startsWith(value, c.stem);
} else {
return equals(value, c);
}
});
}
return true;
} else {
// ignore -- would have caught it above
}
}))) {
validationError("value " + value + " not found in set " + JSON.stringify(valueExpr.values));
}
}
}
}
if ("pattern" in valueExpr) {
var regexp = "flags" in valueExpr ?
new RegExp(valueExpr.pattern, valueExpr.flags) :
new RegExp(valueExpr.pattern);
if (!(getLexicalValue(value).match(regexp)))
validationError("value " + getLexicalValue(value) + " did not match pattern " + valueExpr.pattern);
}
Object.keys(stringTests).forEach(function (test) {
if (test in valueExpr && !stringTests[test](label, valueExpr[test])) {
validationError("facet violation: expected " + test + " of " + valueExpr[test] + " but got " + value);
}
});
Object.keys(numericValueTests).forEach(function (test) {
if (test in valueExpr) {
if (numeric) {
if (!numericValueTests[test](numericParsers[numeric](label, validationError), valueExpr[test])) {
validationError("facet violation: expected " + test + " of " + valueExpr[test] + " but got " + value);
}
} else {
validationError("facet violation: numeric facet " + test + " can't apply to " + value);
}
}
});
Object.keys(decimalLexicalTests).forEach(function (test) {
if (test in valueExpr) {
if (numeric === XSD + "integer" || numeric === XSD + "decimal") {
if (!decimalLexicalTests[test](""+numericParsers[numeric](label, validationError), valueExpr[test])) {
validationError("facet violation: expected " + test + " of " + valueExpr[test] + " but got " + value);
}
} else {
validationError("facet violation: numeric facet " + test + " can't apply to " + value);
}
}
});
return errors;
};
this.semActHandler = {
handlers: { },
results: { },
/**
* Store a semantic action handler.
*
* @param {string} name - semantic action's URL.
* @param {object} handler - handler function.
*
* The handler object has a dispatch function is invoked with:
* @param {string} code - text of the semantic action.
* @param {object} ctx - matched triple or results subset.
* @param {object} extensionStorage - place where the extension writes into the result structure.
* @return {bool} false if the extension failed or did not accept the ctx object.
*/
register: function (name, handler) {
this.handlers[name] = handler;
},
/**
* Calls all semantic actions, allowing each to write to resultsArtifact.
*
* @param {array} semActs - list of semantic actions to invoke.
* @return {bool} false if any result was false.
*/
dispatchAll: function (semActs, ctx, resultsArtifact) {
var _semActHanlder = this;
return semActs.reduce(function (ret, semAct) {
if (ret && semAct.name in _semActHanlder.handlers) {
var code = "code" in semAct ? semAct.code : _ShExValidator.options.semActs[semAct.name];
var existing = "extensions" in resultsArtifact && semAct.name in resultsArtifact.extensions;
var extensionStorage = existing ? resultsArtifact.extensions[semAct.name] : {};
ret = ret && _semActHanlder.handlers[semAct.name].dispatch(code, ctx, extensionStorage);
if (!existing && Object.keys(extensionStorage).length > 0) {
if (!("extensions" in resultsArtifact))
resultsArtifact.extensions = {};
resultsArtifact.extensions[semAct.name] = extensionStorage;
}
return ret;
}
return ret;
}, true);
}
};
}
/* _compileShapeToAST - compile a shape expression to an abstract syntax tree.
*
* currently tested but not used.
*/
function _compileShapeToAST (expression, tripleConstraints, schema) {
function Epsilon () {
this.type = "Epsilon";
}
function TripleConstraint (ordinal, predicate, inverse, negated, valueExpr) {
this.type = "TripleConstraint";
// this.ordinal = ordinal; @@ does 1card25
this.inverse = !!inverse;
this.negated = !!negated;
this.predicate = predicate;
if (valueExpr !== undefined)
this.valueExpr = valueExpr;
}
function Choice (disjuncts) {
this.type = "Choice";
this.disjuncts = disjuncts;
}
function EachOf (conjuncts) {
this.type = "EachOf";
this.conjuncts = conjuncts;
}
function SemActs (expression, semActs) {
this.type = "SemActs";
this.expression = expression;
this.semActs = semActs;
}
function KleeneStar (expression) {
this.type = "KleeneStar";
this.expression = expression;
}
function _compileExpression (expr, schema) {
var repeated, container;
/* _repeat: map expr with a min and max cardinality to a corresponding AST with Groups and Stars.
expr 1 1 => expr
expr 0 1 => Choice(expr, Eps)
expr 0 3 => Choice(EachOf(expr, Choice(EachOf(expr, Choice(expr, EPS)), Eps)), Eps)
expr 2 5 => EachOf(expr, expr, Choice(EachOf(expr, Choice(EachOf(expr, Choice(expr, EPS)), Eps)), Eps))
expr 0 * => KleeneStar(expr)
expr 1 * => EachOf(expr, KleeneStar(expr))
expr 2 * => EachOf(expr, expr, KleeneStar(expr))
@@TODO: favor Plus over Star if Epsilon not in expr.
*/
function _repeat (expr, min, max) {
if (min === undefined) { min = 1; }
if (max === undefined) { max = 1; }
if (min === 1 && max === 1) { return expr; }
var opts = max === UNBOUNDED ?
new KleeneStar(expr) :
_seq(max - min).reduce(function (ret, elt, ord) {
return ord === 0 ?
new Choice([expr, new Epsilon]) :
new Choice([new EachOf([expr, ret]), new Epsilon]);
}, undefined);
var reqd = min !== 0 ?
new EachOf(_seq(min).map(function (ret) {
return expr; // @@ something with ret
}).concat(opts)) : opts;
return reqd;
}
if (expr.type === "TripleConstraint") {
// predicate, inverse, negated, valueExpr, annotations, semActs, min, max
var valueExpr = "valueExprRef" in expr ?
schema.valueExprDefns[expr.valueExprRef] :
expr.valueExpr;
var ordinal = tripleConstraints.push(expr)-1;
var tp = new TripleConstraint(ordinal, expr.predicate, expr.inverse, expr.negated, valueExpr);
repeated = _repeat(tp, expr.min, expr.max);
return expr.semActs ? new SemActs(repeated, expr.semActs) : repeated;
}
else if (expr.type === "OneOf") {
container = new Choice(expr.expressions.map(function (e) {
return _compileExpression(e, schema);
}));
repeated = _repeat(container, expr.min, expr.max);
return expr.semActs ? new SemActs(repeated, expr.semActs) : repeated;
}
else if (expr.type === "EachOf") {
container = new EachOf(expr.expressions.map(function (e) {
return _compileExpression(e, schema);
}));
repeated = _repeat(container, expr.min, expr.max);
return expr.semActs ? new SemActs(repeated, expr.semActs) : repeated;
}
else if (expr.type === "Inclusion") {
var included = schema.shapes[expr.include].expression;
return _compileExpression(included, schema);
}
else throw Error("unexpected expr type: " + expr.type);
}
return expression ? _compileExpression(expression, schema) : new Epsilon();
}
// http://stackoverflow.com/questions/9422386/lazy-cartesian-product-of-arrays-arbitrary-nested-loops
function crossProduct(sets) {
var n = sets.length, carets = [], args = null;
function init() {
args = [];
for (var i = 0; i < n; i++) {
carets[i] = 0;
args[i] = sets[i][0];
}
}
function next() {
// special case: crossProduct([]).next().next() returns false.
if (args !== null && args.length === 0)
return false;
if (args === null) {
init();
return true;
}
var i = n - 1;
carets[i]++;
if (carets[i] < sets[i].length) {
args[i] = sets[i][carets[i]];
return true;
}
while (carets[i] >= sets[i].length) {
if (i == 0) {
return false;
}
carets[i] = 0;
args[i] = sets[i][0];
carets[--i]++;
}
args[i] = sets[i][carets[i]];
return true;
}
return {
next: next,
do: function (block, _context) { // old API
return block.apply(_context, args);
},
// new API because
// https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Functions/arguments#Description
// cautions about functions over arguments.
get: function () { return args; }
};
}
/* N3jsTripleToString - simple toString function to make N3.js's triples
* printable.
*/
var N3jsTripleToString = function () {
function fmt (n) {
return N3Util.isLiteral(n) ?
[ "http://www.w3.org/2001/XMLSchema#integer",
"http://www.w3.org/2001/XMLSchema#float",
"http://www.w3.org/2001/XMLSchema#double"
].indexOf(N3Util.getLiteralType(n)) !== -1 ?
parseInt(N3Util.getLiteralValue(n)) :
n :
N3Util.isBlank(n) ?
n :
"<" + n + ">";
}
return fmt(this.subject) + " " + fmt(this.predicate) + " " + fmt(this.object) + " .";
};
/* indexNeighborhood - index triples by predicate
* returns: {
* byPredicate: Object: mapping from predicate to triples containing that
* predicate.
*
* candidates: [[1,3], [0,2]]: mapping from triple to the triple constraints
* it matches. It is initialized to []. Mappings that remain an
* empty set indicate a triple which didn't matching anything in
* the shape.
*
* misses: list to recieve value constraint failures.
* }
*/
function indexNeighborhood (triples) {
return {
triples: triples,
byPredicate: triples.reduce(function (ret, t) {
var p = t.predicate;
if (!(p in ret))
ret[p] = [];
ret[p].push(t);
// If in VERBOSE mode, add a nice toString to N3.js's triple objects.
if (VERBOSE)
t.toString = N3jsTripleToString;
return ret;
}, {}),
candidates: _seq(triples.length).map(function () {
return [];
}),
misses: []
};
}
/* bySubject - sort triples by subject following SPARQL partial ordering.
*/
function bySubject (t1, t2) {
// if (t1.predicate !== t2.predicate) // sort predicate first for easier scanning of results
// return t1.predicate > t2.predicate;
var l = t1.subject, r = t2.subject;
var lprec = N3Util.isBlank(l) ? 1 : N3Util.isLiteral(l) ? 2 : 3;
var rprec = N3Util.isBlank(r) ? 1 : N3Util.isLiteral(r) ? 2 : 3;
return lprec === rprec ? l > r : lprec > rprec;
}
/* byObject - sort triples by object following SPARQL partial ordering.
*/
function byObject (t1, t2) {
// if (t1.predicate !== t2.predicate) // sort predicate first for easier scanning of results
// return t1.predicate > t2.predicate;
var l = t1.object, r = t2.object;
var lprec = N3Util.isBlank(l) ? 1 : N3Util.isLiteral(l) ? 2 : 3;
var rprec = N3Util.isBlank(r) ? 1 : N3Util.isLiteral(r) ? 2 : 3;
return lprec === rprec ? l > r : lprec > rprec;
}
/* Return a list of n ""s.
*
* Note that Array(n) on its own returns a "sparse array" so Array(n).map(f)
* never calls f.
*/
function _seq (n) {
return n === 0 ?
[] :
Array(n).join(" ").split(/ /); // hahaha, javascript, you suck.
}
/* Expect property p with value v in object o
*/
function expect (o, p, v) {
if (!(p in o))
runtimeError("expected "+JSON.stringify(o)+" to have a '"+p+"' attribute.");
if (arguments.length > 2 && o[p] !== v)
runtimeError("expected "+p+" attribute '"+o[p]+"' to equal '"+v+"'.");
}
function noop () { }
function runtimeError () {
var errorStr = Array.prototype.join.call(arguments, "");
var e = new Error("Runtime error: " + errorStr);
Error.captureStackTrace(e, runtimeError);
throw e;
}
return {
construct: ShExValidator_constructor,
start: Start,
options: InterfaceOptions
};
})();
// Export the `ShExValidator` class as a whole.
if (typeof require !== "undefined" && typeof exports !== "undefined")
module.exports = ShExValidator;
Computing file changes ...
