Repository: icebob/fastest-validator (js)

Issue:
Recursive schema
Hi, trying to validate a recursive schema for f.ex a category tree, but errors during v.compile with "Maximum call stack size exceeded". 

```js
describe("Test recursive schema", () => {
	const v = new Validator();

	let schema = {};
	Object.assign(schema, {
		name: { type: "string" },
		subcategories: {
			type: "array",
			optional: true,
			items: { type: "object", props: schema}
		}
	});

	let check = v.compile(schema);

	it("should compile", () => {
		let category = {
			name: "top",
			subcategories: [
				{
					name: "sub1"
				},
				{
					name: "sub2"
				}
			]
		};

		let res = check(category);

		expect(res).toBe(true);
	});
});
```

Pull request description:
Support recursive schemas
Fixes #30

Currently the cache holds references to all schema rules for the lifetime of the validator. Should probably clear the cache after each compile to prevent leaks in long-running programs, but haven't made up my mind yet.

Patch:
diff --git a/lib/validator.js b/lib/validator.js
index bf55066..cf1ea4a 100644
--- a/lib/validator.js
+++ b/lib/validator.js
@@ -39,6 +39,7 @@ function Validator(opts) {
 
 	// Load rules
 	this.rules = loadRules();
+	this.cache = new Map();
 }
 
 /**
@@ -67,12 +68,14 @@ Validator.prototype.compile = function(schema) {
 		}
 
 		const rules = this.compileSchemaType(schema);
+		this.cache.clear();
 		return function(value) {
 			return self.checkSchemaType(value, rules, undefined, null);
 		};
 	} 
 
 	const rule = this.compileSchemaObject(schema);
+	this.cache.clear();
 	return function(value) {
 		return self.checkSchemaObject(value, rule, undefined, null);
 	};
@@ -83,26 +86,32 @@ Validator.prototype.compileSchemaObject = function(schemaObject) {
 		throw new Error("Invalid schema!");
 	}
 
-	const compiledObject = Object.keys(schemaObject).map(name => {
+	let compiledObject = this.cache.get(schemaObject);
+	if (compiledObject) {
+		compiledObject.cycle = true;
+		return compiledObject;
+	} else{
+		compiledObject = { cycle: false, properties: null, compiledObjectFunction: null, objectStack: [] };
+		this.cache.set(schemaObject, compiledObject);
+	}
+
+	compiledObject.properties = Object.keys(schemaObject).map(name => {
 		const compiledType = this.compileSchemaType(schemaObject[name]);
 		return {name: name, compiledType: compiledType};
 	});
 
-	// Uncomment this line to use compiled object validator:
-	// return compiledObject;
-
 	const sourceCode = [];
 	sourceCode.push("let res;");
 	sourceCode.push("let propertyPath;");
 	sourceCode.push("const errors = [];");
-	for (let i = 0; i < compiledObject.length; i++) {
-		const property = compiledObject[i];
+	for (let i = 0; i < compiledObject.properties.length; i++) {
+		const property = compiledObject.properties[i];
 		const name = property.name;
 		sourceCode.push(`propertyPath = (path !== undefined ? path + ".${name}" : "${name}");`);
 		if (Array.isArray(property.compiledType)) {
-			sourceCode.push(`res = this.checkSchemaType(value.${name}, compiledObject[${i}].compiledType, propertyPath, value);`);
+			sourceCode.push(`res = this.checkSchemaType(value.${name}, properties[${i}].compiledType, propertyPath, value);`);
 		} else {
-			sourceCode.push(`res = this.checkSchemaRule(value.${name}, compiledObject[${i}].compiledType, propertyPath, value);`);
+			sourceCode.push(`res = this.checkSchemaRule(value.${name}, properties[${i}].compiledType, propertyPath, value);`);
 		}
 		sourceCode.push("if (res !== true) {");
 		sourceCode.push("\tthis.handleResult(errors, propertyPath, res);");
@@ -111,12 +120,9 @@ Validator.prototype.compileSchemaObject = function(schemaObject) {
 
 	sourceCode.push("return errors.length === 0 ? true : errors;");
 
-	const compiledObjectFunction = new Function("value", "compiledObject", "path", "parent", sourceCode.join("\n"));
+	compiledObject.compiledObjectFunction = new Function("value", "properties", "path", "parent", sourceCode.join("\n"));
 
-	const self = this;
-	return function(value, _unused, path, parent) {
-		return compiledObjectFunction.call(self, value, compiledObject, path, parent);
-	};
+	return compiledObject;
 };
 
 Validator.prototype.compileSchemaType = function(schemaType) {
@@ -165,16 +171,32 @@ Validator.prototype.compileSchemaRule = function(schemaRule) {
 };
 
 Validator.prototype.checkSchemaObject = function(value, compiledObject, path, parent) {
-	if (compiledObject instanceof Function) {
-		return compiledObject(value, undefined, path, parent);
+	if (compiledObject.cycle) {
+		if (compiledObject.objectStack.indexOf(value) !== -1) {
+			return true;
+		}
+
+		compiledObject.objectStack.push(value);
+		const result = this.checkSchemaObjectInner(value, compiledObject, path, parent);
+		compiledObject.objectStack.pop();
+		return result;
+	} else {
+		return this.checkSchemaObjectInner(value, compiledObject, path, parent);
 	}
+};
+
+Validator.prototype.checkSchemaObjectInner = function(value, compiledObject, path, parent) {
+	return compiledObject.compiledObjectFunction.call(this, value, compiledObject.properties, path, parent);
+
+	/*
+	// Reference implementation of the object checker
 
 	const errors = [];
-	const checksLength = compiledObject.length;
-	for (let i = 0; i < checksLength; i++) {
-		const check = compiledObject[i];
-		const propertyPath = (path !== undefined ? path + "." : "") + check.name;
-		const res = this.checkSchemaType(value[check.name], check.compiledType, propertyPath, value);
+	const propertiesLength = compiledObject.properties.length;
+	for (let i = 0; i < propertiesLength; i++) {
+		const property = compiledObject.properties[i];
+		const propertyPath = (path !== undefined ? path + "." : "") + property.name;
+		const res = this.checkSchemaType(value[property.name], property.compiledType, propertyPath, value);
 
 		if (res !== true) {
 			this.handleResult(errors, propertyPath, res);
@@ -182,6 +204,7 @@ Validator.prototype.checkSchemaObject = function(value, compiledObject, path, pa
 	}
 
 	return errors.length === 0 ? true : errors;
+	*/
 };
 
 Validator.prototype.checkSchemaType = function(value, compiledType, path, parent) {


Test patch:
diff --git a/test/validator.spec.js b/test/validator.spec.js
index 821608b..62d68f1 100644
--- a/test/validator.spec.js
+++ b/test/validator.spec.js
@@ -1004,3 +1004,61 @@ describe("Test array without items", () => {
 		expect(res).toBe(true);
 	});
 });
+
+describe("Test recursive/cyclic schema", () => {
+	const v = new Validator();
+
+	let schema = {};
+	Object.assign(schema, {
+		name: { type: "string" },
+		parent: { type: "object", props: schema, optional: true },
+		subcategories: {
+			type: "array",
+			optional: true,
+			items: { type: "object", props: schema}
+		}
+	});
+
+	it("should compile and validate", () => {
+		let category = {};
+		Object.assign(category, {
+			name: "top",
+			subcategories: [
+				{
+					name: "sub1",
+					parent: category
+				},
+				{
+					name: "sub2",
+					parent: category
+				}
+			]
+		});
+
+		const res = v.validate(category, schema);
+
+		expect(res).toBe(true);
+	});
+
+	it("should give error if nested object is broken", () => {
+		const category = {
+			name: "top",
+			subcategories: [
+				{
+					name: "sub1"
+				},
+				{
+					name: "sub2",
+					subcategories: [ {} ]
+				}
+			]
+		};
+
+		const res = v.validate(category, schema);
+
+		expect(res).toBeInstanceOf(Array);
+		expect(res.length).toBe(1);
+		expect(res[0].type).toBe("required");
+		expect(res[0].field).toBe("subcategories[1].subcategories[0].name");
+	});
+});