CVE-2018-25074 (JavaScript, published 2023-01-11T15:15Z)
Description: value: A vulnerability was found in Prestaul skeemas and classified as problematic. This issue affects some unknown processing of the file validators/base.js. The manipulation of the argument uri leads to inefficient regular expression complexity. The patch is named 65e94eda62dc8dc148ab3e59aa2ccc086ac448fd. It is recommended to apply a patch to fix this issue. The associated identifier of this vulnerability is VDB-218003.
Severity: nan (CVSS v3 base score: 7.5)
Weakness: CWE-1333 \u2014 Inefficient Regular Expression Complexity
The product uses a regular expression with an inefficient, possibly exponential worst-case computational complexity that consumes excessive CPU cycles.
Repository: https://github.com/Prestaul/skeemas
Files changed:
.gitignore
.gitmodules
.jshintignore
.jshintrc
LICENSE
README.md
index.js
package.json
tests/bootstrap.js
tests/index.test.js
tests/json-schema-test-suite
tests/json-schema-test-suite.test.js
tests/plugins.test.js
tests/refs/json-schema-draft-03.json
tests/refs/json-schema-draft-04.json
tests/validators/base.test.js
tests/validators/number.test.js
validation-context.js
validation-result.js
validators/array.js
validators/base.js
validators/boolean.js
validators/deep-equal.js
validators/index.js
validators/null.js
validators/number.js
validators/object.js
validators/string.js
Commit message: Resolved potential ReDoS issue with uri format regexp.

Special thanks to James Davis <davisjam@vt.edu> for finding and reporting the vulnerability


Vulnerable code:

Fixed code:
node_modules
.DS_Store
npm-debug.log
[submodule "tests/json-schema-test-suite"]
	path = tests/json-schema-test-suite
	url = git@github.com:json-schema/JSON-Schema-Test-Suite.git
node_modules
{
	"node": true,
	"undef": true,
	"eqeqeq": true,
	"eqnull": false,
	"newcap": true,
	"nomen": true,
	"trailing": true,

	"predef": [
		"describe",
		"it",
		"assert",
		"validate"
	]
}
The MIT License (MIT)

Copyright (C) 2009-2014 Kristopher Michael Kowal and contributors

Permission is hereby granted, free of charge, to any person obtaining a copy
of this software and associated documentation files (the "Software"), to deal
in the Software without restriction, including without limitation the rights
to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
copies of the Software, and to permit persons to whom the Software is
furnished to do so, subject to the following conditions:

The above copyright notice and this permission notice shall be included in
all copies or substantial portions of the Software.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
THE SOFTWARE.
# skeemas
Comprehensive JSON Schema (drafts 3 and 4) validation.


## Installation
```bash
npm install skeemas --save
```


## Basic Validation
**`skeemas.validate(subject, schema[, options])`**

```js
var skeemas = require('skeemas');

skeemas.validate('foo', { type:'string' }).valid; // true
skeemas.validate(10000, { type:'string' }).valid; // false
skeemas.validate(10000, { type:'number' }).valid; // true

// Result contains an array of errors
var result = skeemas.validate('test', { enum:['foobar'], minLength:5 });
result.valid; // false
result.errors; // array with 2 error objects

// Pass the "breakOnError" option to stop processing on the first error
var result = skeemas.validate('test', { enum:['foobar'], minLength:5 }, { breakOnError:true });
result.valid; // false
result.errors; // array with 1 error object

var result = skeemas.validate({
    foo: 'bar',
    nested: {
        stuff: [1,2,3],
        ignoreMe: 'undeclared property'
    }
}, {
    properties: {
        foo: { type:'string' },
        nested: {
            properties: {
                stuff: {
                    type: 'array',
                    items: { type:'integer' }
                }
                // We aren't going to declare `ignoreMe`. To disallow extra 
                // props we could set `additionalProperties:false`.
            }
        }
    }
}); 
result.valid; // true
assert.deepEqual(result.cleanInstance, {
    foo: 'bar',
    nested: {
        stuff: [1,2,3]
        // notice the `ignoreMe` property is removed from `cleanInstance`
    }
});
```

For more information about constructing schemas see http://json-schema.org/ or the wonderful guide at http://spacetelescope.github.io/understanding-json-schema/index.html


## Adding Schemas
Skeemas supports validation by schema id and refrences between schemas via the `$ref` property:

```js
// Create an instance of a validator
var validator = require('skeemas')();

// Add schemas to the validator
validator.addRef({ type:'string', pattern:'^[a-z0-9]+$' }, '/identifier');

// Validate by uri/id
validator.validate('foo123', '/identifier').valid; // true

// Use a $ref reference in other schemas
validator.validate(user, { 
    type: 'object',
    properties: {
        id: { '$ref':'/identifier' },
        name: { type:'string' }
    } 
}).valid; // true
```


## Related Modules

- [skeemas-body-parser](https://github.com/Prestaul/skeemas-body-parser) - json body parser middleware with schema validation
- [skeemas-markdown-validation](https://github.com/Prestaul/skeemas-markdown-validation) - simple testing of json blocks in your markdown documentation


## Development
Our tests are running the JSON Schema test suite at [https://github.com/json-schema/JSON-Schema-Test-Suite](https://github.com/json-schema/JSON-Schema-Test-Suite). Those tests are referenced as a submodule and therefore dev setup is a little non-standard.
```bash
# clone the repo

# install dependencies from npm
npm install

# install the test suite
git submodule init
git submodule update

# run the tests
npm test
```



## Feature Status

- [X] Full Validation (all errors)
- [X] Quick Validation (first error)
- [X] Instance cleaning
- [X] Manual reference additions
- [X] Validate by reference
- [ ] Missing reference resolution
- [ ] Custom format validation
- [ ] Custom attribute validation
- [X] Plugins
- [X] JSON-Schema draft 03 and 04 feature support
    - Ignored schema attributes
        - $schema
        - title
        - description
        - default
    - [X] References
        - [X] id
        - [X] definitions
        - [X] $ref
    - [X] Validations by type
        - [X] any
            - [X] type
            - [X] enum
            - [X] extends
            - [X] allOf
            - [X] anyOf
            - [X] oneOf
            - [X] not
            - [X] disallow
            - [X] required
            - [X] format
        - [X] array
            - [X] items
            - [X] additionalItems
            - [X] minItems
            - [X] maxItems
            - [X] uniqueItems
        - [X] boolean
        - [X] null
        - [X] number, integer
            - [X] multipleOf
            - [X] divisibleBy
            - [X] minimum
            - [X] maximum
            - [X] exclusiveMinimum
            - [X] exclusiveMaximum
        - [X] object
            - [X] properties
            - [X] patternProperties
            - [X] additionalProperties
            - [X] required
            - [X] dependencies
            - [X] minProperties
            - [X] maxProperties
            - [X] dependencies
        - [X] string
            - [X] minLength
            - [X] maxLength
            - [X] pattern
            - [X] format
                - [X] date-time
                - [X] date
                - [X] time
                - [X] utc-millisec
                - [X] email
                - [X] hostname
                - [X] host-name
                - [X] ip-address
                - [X] ipv4
                - [X] ipv6
                - [X] uri
                - [X] regex
                - [X] color
                - [X] style
                - [X] phone
var validators = require('./validators'),
	validationContext = require('./validation-context'),
	jsonRefs = require('skeemas-json-refs');

var protoValidator = {
	addRef: function(uri, ref) {
		if(typeof uri === 'object') {
			ref = uri;
			uri = null;
		}
		uri = uri || ref.id;

		if(!uri) throw new Error('Cannot add a json schema reference without a uri/id.');

		this._refs.add(uri, ref);

		return this;
	},
	validate: function(instance, schema, options) {
		if(instance === undefined) throw new Error('Instance undefined in call to validate.');
		if(!schema) throw new Error('No schema specified in call to validate.');

		if(typeof schema === 'string') {
			var uri = schema;
			schema = this._refs.get(uri);

			if(!schema) throw new Error('Unable to locate schema (' + uri + '). Did you call addRef with this schema?');
		}

		var context = validationContext(schema, {
			instance: instance,
			refs: this._refs,
			breakOnError: options && options.breakOnError,
			cleanWithDefaults: options && options.cleanWithDefaults
		});
		validators.base(context, instance, schema);
		if(context.result.valid) context.result.cleanInstance = context.cleanSubject;
		return context.result;
	}
};

function makeValidator() {
	return Object.create(protoValidator, {
		_refs: { enumerable:false, writable:false, value:jsonRefs() }
	});
}

module.exports = makeValidator;

module.exports.validate = function(instance, schema, options) {
	if(instance === undefined) throw new Error('Instance undefined in call to validate.');
	if(!schema) throw new Error('No schema specified in call to validate.');

	var context = validationContext(schema, {
		instance: instance,
		breakOnError: options && options.breakOnError,
		cleanWithDefaults: options && options.cleanWithDefaults
	});
	validators.base(context, instance, schema);
	if(context.result.valid) context.result.cleanInstance = context.cleanSubject;
	return context.result;
};

module.exports.use = function(plugin) {
	if(typeof plugin !== 'function') throw new Error('skeemas.use called with non-function. Plugins are in the form function(skeemas){}.');
	plugin(protoValidator);
	return this;
};
{
  "name": "skeemas",
  "version": "1.2.4",
  "description": "Lightweight JSON Schema valiation",
  "main": "index.js",
  "scripts": {
    "test": "mocha -R dot --require tests/bootstrap.js tests/{**/,}/*.test.js",
    "lint": "jshint ."
  },
  "keywords": [
    "json-schema",
    "validate",
    "validation",
    "json",
    "schema"
  ],
  "author": "Matt Dunlap <mpdunlap@gmail.com>",
  "license": "MIT",
  "repository": {
    "type": "git",
    "url": "git@github.com:Prestaul/skeemas.git"
  },
  "devDependencies": {
    "chai": "^1.10.0",
    "glob": "^4.3.5",
    "jshint": "^2.6.0",
    "mocha": "^2.1.0"
  },
  "dependencies": {
    "skeemas-json-pointer": "^1.0.0",
    "skeemas-json-refs": "^1.0.1"
  }
}
var validator = require('../')();

validator
	.addRef('http://json-schema.org/draft-03/schema', require('./refs/json-schema-draft-03'))
	.addRef('http://json-schema.org/draft-04/schema', require('./refs/json-schema-draft-04'))
	.addRef('http://localhost:1234/integer.json', require('./json-schema-test-suite/remotes/integer.json'))
	.addRef('http://localhost:1234/name.json', require('./json-schema-test-suite/remotes/name.json'))
	.addRef('http://localhost:1234/subSchemas.json', require('./json-schema-test-suite/remotes/subSchemas.json'))
	.addRef('http://localhost:1234/folder/folderInteger.json', require('./json-schema-test-suite/remotes/folder/folderInteger.json'));

global.validate = validator.validate.bind(validator);
global.assert = require('chai').assert;
var skeemas = require('../');

describe('Validate', function() {
	it('should throw an error if missing schema', function() {
		assert.throws(function() {
			validate('test');
		});
	});

	it('should throw an error if adding a reference schema without a uri/id', function() {
		assert.throws(function() {
			skeemas().addRef({});
		});
	});

	describe('an empty schema', function() {
		it('should validate an array', function() {
			assert.isTrue(validate([], {}).valid);
		});

		it('should validate a boolean true value', function() {
			assert.isTrue(validate(true, {}).valid);
		});

		it('should validate a boolean false value', function() {
			assert.isTrue(validate(false, {}).valid);
		});

		it('should validate an integer', function() {
			assert.isTrue(validate(42, {}).valid);
		});

		it('should validate a null', function() {
			assert.isTrue(validate(null, {}).valid);
		});

		it('should validate a number', function() {
			assert.isTrue(validate(42.1337, {}).valid);
		});

		it('should validate an object', function() {
			assert.isTrue(validate({ test:true }, {}).valid);
		});

		it('should validate an empty object', function() {
			assert.isTrue(validate({}, {}).valid);
		});

		it('should validate a string', function() {
			assert.isTrue(validate('test', {}).valid);
		});

		it('should validate an empty string', function() {
			assert.isTrue(validate('', {}).valid);
		});
	});

	describe('result object', function() {
		it('should have valid:true when valid', function() {
			var result = validate('test', {});
			assert.isTrue(result.valid);
		});

		it('should have valid:false when invalid', function() {
			var result = validate('test', { type:'object' });
			assert.isFalse(result.valid);
		});

		it('should have an empty errors array when valid', function() {
			var result = validate('test', {});
			assert.isArray(result.errors);
			assert.lengthOf(result.errors, 0);
		});

		it('should have populated errors array when invalid', function() {
			var result = validate('test', { type:'object' });
			assert.isArray(result.errors);
			assert.lengthOf(result.errors, 1);
		});

		it('should have multiple errors when multiple conditions are invalid', function() {
			var result = validate('test', { enum:['foobar'], minLength:5 });
			assert.isArray(result.errors);
			assert.lengthOf(result.errors, 2);
		});

		it('should have single error if breakOnError', function() {
			var result = validate('test', { enum:['foobar'], minLength:5 }, { breakOnError:true });
			assert.isArray(result.errors);
			assert.lengthOf(result.errors, 1);
		});
	});

	describe('result.cleanInstance', function() {
		it('should leave null untouched', function() {
			var result = validate(null, { type:'null' });
			assert.strictEqual(result.cleanInstance, null);
		});

		it('should leave true untouched', function() {
			var result = validate(true, { type:'boolean' });
			assert.strictEqual(result.cleanInstance, true);
		});

		it('should leave false untouched', function() {
			var result = validate(false, { type:'boolean' });
			assert.strictEqual(result.cleanInstance, false);
		});

		it('should leave an integer untouched', function() {
			var result = validate(1337, { type:'integer' });
			assert.strictEqual(result.cleanInstance, 1337);
		});

		it('should leave a number untouched', function() {
			var result = validate(42.1337, { type:'number' });
			assert.strictEqual(result.cleanInstance, 42.1337);
		});

		it('should leave a string untouched', function() {
			var result = validate('test', { type:'string' });
			assert.strictEqual(result.cleanInstance, 'test');
		});

		it('should clone an array', function() {
			var subject = [1, 2, 3],
				result = validate(subject, { type:'array' });
			assert.deepEqual(result.cleanInstance, subject);
			assert.notStrictEqual(result.cleanInstance, subject);
		});

		describe('an object', function() {
			it('should leave defined properties', function() {
				var result = validate({
					foo: 'bar',
					foobar: 42,
					foobat: [1, 'test'],
					foobaz: 'far',
					boo: 'far',
					boofar: 'bad'
				}, {
					properties: {
						foo: {},
						boo: {}
					}
				});

				assert.deepEqual(result.cleanInstance, {
					foo: 'bar',
					boo: 'far'
				});
			});

			it('should leave pattern properties', function() {
				var result = validate({
					foo: 'bar',
					foobar: 42,
					foobat: [1, 'test'],
					foobaz: 'far',
					boo: 'far',
					boofar: 'bad'
				}, {
					properties: {
						boo: {}
					},
					patternProperties: {
						'^foo': {}
					}
				});

				assert.deepEqual(result.cleanInstance, {
					foo: 'bar',
					foobar: 42,
					foobat: [1, 'test'],
					foobaz: 'far',
					boo: 'far'
				});
			});

			it('should remove undefined additional properties', function() {
				var result = validate({
					foo: 'bar',
					foobar: 42,
					boo: 'far'
				}, {
					properties: {
						foo: {}
					},
					additionalProperties: true
				});

				assert.deepEqual(result.cleanInstance, {
					foo: 'bar'
				});
			});

			it('should leave defined additional properties', function() {
				var result = validate({
					foo: 'bar',
					foobar: 42,
					boo: 'far'
				}, {
					properties: {
						foo: {}
					},
					additionalProperties: { type:'any' }
				});

				assert.deepEqual(result.cleanInstance, {
					foo: 'bar',
					foobar: 42,
					boo: 'far'
				});
			});

			it('should leave defined nested properties', function() {
				var result = validate({
					foo: 'bar',
					boo: 'far',
					nested: {
						foo: 'nestbar',
						boo: 'nestfar',
						arr: [{
							foo:'arrfoo',
							boo:'nestbar'
						}]
					}
				}, {
					definitions: {
						foo: {
							properties: {
								foo: {},
								arr: {
									items: { $ref:'#/definitions/foo' }
								},
								nested: { $ref:'#/definitions/foo' }
							}
						}
					},
					$ref:'#/definitions/foo'
				});

				assert.deepEqual(result.cleanInstance, {
					foo: 'bar',
					nested: {
						foo: 'nestbar',
						arr: [{
							foo:'arrfoo'
						}]
					}
				});
			});

			it('should clean instance properly even with reference properties', function() {
				var localValidator = skeemas().addRef('/ref', {}),
					result = localValidator.validate({
						foo: 'bar',
						boo: 'far'
					}, {
						properties: {
							foo: { '$ref':'/ref' },
							boo: {}
						}
					});

				assert.deepEqual(result.cleanInstance, {
					foo: 'bar',
					boo: 'far'
				});
			});

			describe('with cleanWithDefaults', function() {
				it('should add defaults', function() {
					var result = validate({}, {
						properties: {
							foo: { default:'bar' },
							boo: { default:'far' }
						}
					}, { cleanWithDefaults:true });

					assert.deepEqual(result.cleanInstance, {
						foo: 'bar',
						boo: 'far'
					});
				});

				it('should not override values with defaults', function() {
					var result = validate({
						foo: 'bat'
					}, {
						properties: {
							foo: { default:'bar' },
							boo: { default:'far' }
						}
					}, { cleanWithDefaults:true });

					assert.deepEqual(result.cleanInstance, {
						foo: 'bat',
						boo: 'far'
					});
				});

				it('should add complex default', function() {
					var result = validate({}, {
						properties: {
							foo: { default: { bar:'bat' } }
						}
					}, { cleanWithDefaults:true });

					assert.deepEqual(result.cleanInstance, {
						foo: { bar:'bat' }
					});
				});

				it('should add null default', function() {
					var result = validate({}, {
						properties: {
							foo: { default: null }
						}
					}, { cleanWithDefaults:true });

					assert.deepEqual(result.cleanInstance, {
						foo: null
					});
				});
			});
		});
	});

	describe('with reference schema', function() {
		var localValidator = skeemas().addRef('/some/schema', {
			properties: { foo: { type:'string' } }
		});

		it('should validate against a referenced schema', function() {
			assert.isTrue(localValidator.validate({ foo:'test' }, '/some/schema').valid);
		});

		it('should invalidate against a referenced schema', function() {
			assert.isFalse(localValidator.validate({ foo:42 }, '/some/schema').valid);
		});

		it('should validate against a referenced schema fragment', function() {
			assert.isTrue(localValidator.validate('test', '/some/schema#/properties/foo').valid);
		});

		it('should invalidate against a referenced schema fragment', function() {
			assert.isFalse(localValidator.validate(42, '/some/schema#/properties/foo').valid);
		});

		it('should throw an error for missing reference', function() {
			assert.throws(function() {
				localValidator.validate('test', '/some/missing/schema');
			});
		});

		it('should throw an error for missing fragment reference', function() {
			assert.throws(function() {
				localValidator.validate('test', '/some/schema#/not/here');
			});
		});
	});

	describe('with reference schema added by id', function() {
		var localValidator = skeemas().addRef({
			id: '/some/schema',
			properties: { foo: { type:'string' } }
		});

		it('should validate against a referenced schema', function() {
			assert.isTrue(localValidator.validate({ foo:'test' }, '/some/schema').valid);
		});

		it('should invalidate against a referenced schema', function() {
			assert.isFalse(localValidator.validate({ foo:42 }, '/some/schema').valid);
		});

		it('should validate against a referenced schema fragment', function() {
			assert.isTrue(localValidator.validate('test', '/some/schema#/properties/foo').valid);
		});

		it('should invalidate against a referenced schema fragment', function() {
			assert.isFalse(localValidator.validate(42, '/some/schema#/properties/foo').valid);
		});

		it('should throw an error for missing reference', function() {
			assert.throws(function() {
				localValidator.validate('test', '/some/missing/schema');
			});
		});

		it('should throw an error for missing fragment reference', function() {
			assert.throws(function() {
				localValidator.validate('test', '/some/schema#/not/here');
			});
		});
	});

	describe('schema having anyOf with references', function() {
		var localValidator = skeemas().addRef('/foo/schema', {
				enum: [ 'foo' ]
			}),
			schema = {
				definitions: {
					bars: {
						enum: [ 'bar' ]
					},
					ints: {
						type: 'integer'
					}
				},
				anyOf: [
					{ $ref: '#/definitions/ints' },
					{ $ref: '/foo/schema' },
					{ $ref: '#/definitions/bars' }
				]
			};

		it('should validate correctly', function() {
			assert.isTrue(localValidator.validate(42, schema).valid, 'should validate an int');
			assert.isTrue(localValidator.validate('foo', schema).valid, 'should validate "foo"');
			assert.isTrue(localValidator.validate('bar', schema).valid, 'should validate "bar"');
		});

		it('should invalidate correctly', function() {
			var result = localValidator.validate(42.1337, schema);
			assert.isFalse(result.valid, 'float should be invalid');
			assert.lengthOf(result.errors, 1, 'should have one error');
			assert.match(result.errors[0].message, /anyOf/, 'should be an "anyOf" error');

			result = localValidator.validate('boo', schema);
			assert.isFalse(result.valid, '"boo" should be invalid');
			assert.lengthOf(result.errors, 1, 'should have one error');
			assert.match(result.errors[0].message, /anyOf/, 'should be an "anyOf" error');
		});
	});

	describe('schema having oneOf with references', function() {
		var localValidator = skeemas().addRef('/foo/schema', {
				enum: [ 'foo' ]
			}),
			schema = {
				definitions: {
					bars: {
						enum: [ 'bar' ]
					},
					ints: {
						type: 'integer'
					}
				},
				oneOf: [
					{ $ref: '#/definitions/ints' },
					{ $ref: '/foo/schema' },
					{ $ref: '#/definitions/bars' }
				]
			};

		it('should validate correctly', function() {
			assert.isTrue(localValidator.validate(42, schema).valid, 'should validate an int');
			assert.isTrue(localValidator.validate('foo', schema).valid, 'should validate "foo"');
			assert.isTrue(localValidator.validate('bar', schema).valid, 'should validate "bar"');
		});

		it('should invalidate correctly', function() {
			var result = localValidator.validate(42.1337, schema);
			assert.isFalse(result.valid, 'float should be invalid');
			assert.lengthOf(result.errors, 1, 'should have one error');
			assert.match(result.errors[0].message, /oneOf/, 'should be an "oneOf" error');

			result = localValidator.validate('boo', schema);
			assert.isFalse(result.valid, '"boo" should be invalid');
			assert.lengthOf(result.errors, 1, 'should have one error');
			assert.match(result.errors[0].message, /oneOf/, 'should be an "oneOf" error');
		});
	});

	it('should handle required:true in props', function() {
		var schema = {
			properties: {
				foo: {
					required: true
				}
			}
		};
		assert.isTrue(validate({ foo: { bar:1 } }, schema).valid);
		assert.isFalse(validate({ boo: { bar:1 } }, schema).valid);
	});

	it('should handle required:[] in props', function() {
		var schema = {
			properties: {
				foo: {
					required: ['bar']
				}
			}
		};
		assert.isTrue(validate({ foo: { bar:1 } }, schema).valid);
		assert.isFalse(validate({ foo: { far:1 } }, schema).valid);
		assert.isTrue(validate({ boo: { far:1 } }, schema).valid);
	});

	describe('errors', function() {
		describe('after arrays of objects', function() {
			it('should have correct context', function() {
				var result = validate({
					"someArray": [ {} ]
				}, {
					properties: {
						someArray: {
							items: {
								type: "object",
								properties: {
									foo: { required: true }
								}
							}
						},
						missingProp: {
							required: true
						}
					}
				});

				assert.isFalse(result.valid);
				assert.lengthOf(result.errors, 3);
				assert.strictEqual(result.errors[2].context, '#');
			});
		});
	});
});
Subproject commit 728066f9c5c258ba3b1804a22a5b998f2ec77ec0
var glob = require('glob');

/**
 * Load up the tests from the JSON Schema Test Suite (https://github.com/json-schema/JSON-Schema-Test-Suite)
 */
describe('JSON Schema Test Suite -', function() {
	function addTests(description, files) {
		describe(description, function() {
			files.forEach(function(file) {
				// Skip "zeroTerminatedFloats" because in javascript 1 === 1.0
				if(/zeroTerminatedFloats\.json$/.test(file)) return;

				// Load the suite
				require(file).forEach(function(suite) {
					describe(suite.description, function() {
						// Load the tests
						suite.tests.forEach(function(test) {
							// Create individual tests
							it(test.description, function() {
								var result = validate(test.data, suite.schema);
								assert.strictEqual(result.valid, test.valid, test.valid ? 'validates the instance' : 'invalidates the instance');
							});

						});
					});
				});
			});
		});
	}

	var draft3 = glob.sync('./json-schema-test-suite/tests/draft3/{**/,}*.json', { cwd:__dirname });
	addTests('draft3:', draft3);

	var draft4 = glob.sync('./json-schema-test-suite/tests/draft4/{**/,}*.json', { cwd:__dirname });
	addTests('draft4:', draft4);
});
var skeemas = require('../');

describe('Plugins', function() {
	it('should be called correctly', function() {
		var called = false;
		skeemas.use(function(protoValidator) {
			called = true;
			assert.isObject(protoValidator);
		});
		assert.isTrue(called);
	});

	it('should allow validator modifications', function() {
		skeemas.use(function(protoValidator) {
			protoValidator.testMethod = function() {
				assert.isFunction(this.validate);
				assert.isObject(this._refs);
				return this;
			};
		});

		var validator = skeemas();
		assert.isFunction(validator.testMethod);
		assert.strictEqual(validator.testMethod(), validator);
	});
});
{
    "$schema": "http://json-schema.org/draft-03/schema#",
    "id": "http://json-schema.org/draft-03/schema#",
    "type": "object",

    "properties": {
        "type": {
            "type": [ "string", "array" ],
            "items": {
                "type": [ "string", { "$ref": "#" } ]
            },
            "uniqueItems": true,
            "default": "any"
        },

        "properties": {
            "type": "object",
            "additionalProperties": { "$ref": "#" },
            "default": {}
        },

        "patternProperties": {
            "type": "object",
            "additionalProperties": { "$ref": "#" },
            "default": {}
        },

        "additionalProperties": {
            "type": [ { "$ref": "#" }, "boolean" ],
            "default": {}
        },

        "items": {
            "type": [ { "$ref": "#" }, "array" ],
            "items": { "$ref": "#" },
            "default": {}
        },

        "additionalItems": {
            "type": [ { "$ref": "#" }, "boolean" ],
            "default": {}
        },

        "required": {
            "type": "boolean",
            "default": false
        },

        "dependencies": {
            "type": "object",
            "additionalProperties": {
                "type": [ "string", "array", { "$ref": "#" } ],
                "items": {
                    "type": "string"
                }
            },
            "default": {}
        },

        "minimum": {
            "type": "number"
        },

        "maximum": {
            "type": "number"
        },

        "exclusiveMinimum": {
            "type": "boolean",
            "default": false
        },

        "exclusiveMaximum": {
            "type": "boolean",
            "default": false
        },

        "minItems": {
            "type": "integer",
            "minimum": 0,
            "default": 0
        },

        "maxItems": {
            "type": "integer",
            "minimum": 0
        },

        "uniqueItems": {
            "type": "boolean",
            "default": false
        },

        "pattern": {
            "type": "string",
            "format": "regex"
        },

        "minLength": {
            "type": "integer",
            "minimum": 0,
            "default": 0
        },

        "maxLength": {
            "type": "integer"
        },

        "enum": {
            "type": "array",
            "minItems": 1,
            "uniqueItems": true
        },

        "default": {
            "type": "any"
        },

        "title": {
            "type": "string"
        },

        "description": {
            "type": "string"
        },

        "format": {
            "type": "string"
        },

        "divisibleBy": {
            "type": "number",
            "minimum": 0,
            "exclusiveMinimum": true,
            "default": 1
        },

        "disallow": {
            "type": [ "string", "array" ],
            "items": {
                "type": [ "string", { "$ref": "#" } ]
            },
            "uniqueItems": true
        },

        "extends": {
            "type": [ { "$ref": "#" }, "array" ],
            "items": { "$ref": "#" },
            "default": {}
        },

        "id": {
            "type": "string",
            "format": "uri"
        },

        "$ref": {
            "type": "string",
            "format": "uri"
        },

        "$schema": {
            "type": "string",
            "format": "uri"
        }
    },

    "dependencies": {
        "exclusiveMinimum": "minimum",
        "exclusiveMaximum": "maximum"
    },

    "default": {}
}
{
    "id": "http://json-schema.org/draft-04/schema#",
    "$schema": "http://json-schema.org/draft-04/schema#",
    "description": "Core schema meta-schema",
    "definitions": {
        "schemaArray": {
            "type": "array",
            "minItems": 1,
            "items": { "$ref": "#" }
        },
        "positiveInteger": {
            "type": "integer",
            "minimum": 0
        },
        "positiveIntegerDefault0": {
            "allOf": [ { "$ref": "#/definitions/positiveInteger" }, { "default": 0 } ]
        },
        "simpleTypes": {
            "enum": [ "array", "boolean", "integer", "null", "number", "object", "string" ]
        },
        "stringArray": {
            "type": "array",
            "items": { "type": "string" },
            "minItems": 1,
            "uniqueItems": true
        }
    },
    "type": "object",
    "properties": {
        "id": {
            "type": "string",
            "format": "uri"
        },
        "$schema": {
            "type": "string",
            "format": "uri"
        },
        "title": {
            "type": "string"
        },
        "description": {
            "type": "string"
        },
        "default": {},
        "multipleOf": {
            "type": "number",
            "minimum": 0,
            "exclusiveMinimum": true
        },
        "maximum": {
            "type": "number"
        },
        "exclusiveMaximum": {
            "type": "boolean",
            "default": false
        },
        "minimum": {
            "type": "number"
        },
        "exclusiveMinimum": {
            "type": "boolean",
            "default": false
        },
        "maxLength": { "$ref": "#/definitions/positiveInteger" },
        "minLength": { "$ref": "#/definitions/positiveIntegerDefault0" },
        "pattern": {
            "type": "string",
            "format": "regex"
        },
        "additionalItems": {
            "anyOf": [
                { "type": "boolean" },
                { "$ref": "#" }
            ],
            "default": {}
        },
        "items": {
            "anyOf": [
                { "$ref": "#" },
                { "$ref": "#/definitions/schemaArray" }
            ],
            "default": {}
        },
        "maxItems": { "$ref": "#/definitions/positiveInteger" },
        "minItems": { "$ref": "#/definitions/positiveIntegerDefault0" },
        "uniqueItems": {
            "type": "boolean",
            "default": false
        },
        "maxProperties": { "$ref": "#/definitions/positiveInteger" },
        "minProperties": { "$ref": "#/definitions/positiveIntegerDefault0" },
        "required": { "$ref": "#/definitions/stringArray" },
        "additionalProperties": {
            "anyOf": [
                { "type": "boolean" },
                { "$ref": "#" }
            ],
            "default": {}
        },
        "definitions": {
            "type": "object",
            "additionalProperties": { "$ref": "#" },
            "default": {}
        },
        "properties": {
            "type": "object",
            "additionalProperties": { "$ref": "#" },
            "default": {}
        },
        "patternProperties": {
            "type": "object",
            "additionalProperties": { "$ref": "#" },
            "default": {}
        },
        "dependencies": {
            "type": "object",
            "additionalProperties": {
                "anyOf": [
                    { "$ref": "#" },
                    { "$ref": "#/definitions/stringArray" }
                ]
            }
        },
        "enum": {
            "type": "array",
            "minItems": 1,
            "uniqueItems": true
        },
        "type": {
            "anyOf": [
                { "$ref": "#/definitions/simpleTypes" },
                {
                    "type": "array",
                    "items": { "$ref": "#/definitions/simpleTypes" },
                    "minItems": 1,
                    "uniqueItems": true
                }
            ]
        },
        "allOf": { "$ref": "#/definitions/schemaArray" },
        "anyOf": { "$ref": "#/definitions/schemaArray" },
        "oneOf": { "$ref": "#/definitions/schemaArray" },
        "not": { "$ref": "#" }
    },
    "dependencies": {
        "exclusiveMaximum": [ "maximum" ],
        "exclusiveMinimum": [ "minimum" ]
    },
    "default": {}
}
var validateBase = require('../../validators').base,
	validationContext = require('../../validation-context');


describe('Base validator', function() {
	describe('an empty schema', function() {
		it('should validate an array', function() {
			var ctx = validationContext({});
			assert.isTrue(validateBase(ctx, [], ctx.schema));
		});

		it('should validate a boolean true value', function() {
			var ctx = validationContext({});
			assert.isTrue(validateBase(ctx, true, ctx.schema));
		});

		it('should validate a boolean false value', function() {
			var ctx = validationContext({});
			assert.isTrue(validateBase(ctx, false, ctx.schema));
		});

		it('should validate an integer', function() {
			var ctx = validationContext({});
			assert.isTrue(validateBase(ctx, 42, ctx.schema));
		});

		it('should validate a null', function() {
			var ctx = validationContext({});
			assert.isTrue(validateBase(ctx, null, ctx.schema));
		});

		it('should validate a number', function() {
			var ctx = validationContext({});
			assert.isTrue(validateBase(ctx, 42.1337, ctx.schema));
		});

		it('should validate an object', function() {
			var ctx = validationContext({});
			assert.isTrue(validateBase(ctx, { test:true }, ctx.schema));
		});

		it('should validate an empty object', function() {
			var ctx = validationContext({});
			assert.isTrue(validateBase(ctx, {}, ctx.schema));
		});

		it('should validate a string', function() {
			var ctx = validationContext({});
			assert.isTrue(validateBase(ctx, 'test', ctx.schema));
		});

		it('should validate an empty string', function() {
			var ctx = validationContext({});
			assert.isTrue(validateBase(ctx, '', ctx.schema));
		});
	});

	describe('format', function() {
		it('should validate integer string utc-millisec', function() {
			var ctx = validationContext({ format:'utc-millisec' });
			assert.isTrue(validateBase(ctx, '1337', ctx.schema));
		});

		it('should invalidate float string utc-millisec', function() {
			var ctx = validationContext({ format:'utc-millisec' });
			assert.isFalse(validateBase(ctx, '1337.42', ctx.schema));
		});

		it('should validate integer number utc-millisec', function() {
			var ctx = validationContext({ format:'utc-millisec' });
			assert.isTrue(validateBase(ctx, 1337, ctx.schema));
		});

		it('should invalidate float number utc-millisec', function() {
			var ctx = validationContext({ format:'utc-millisec' });
			assert.isFalse(validateBase(ctx, 1337.42, ctx.schema));
		});

		it('should validate an email string', function() {
			var ctx = validationContext({ format:'email' });
			assert.isTrue(validateBase(ctx, 'foo@bar.com', ctx.schema));
		});

		it('should validate an uncommon email string', function() {
			var ctx = validationContext({ format:'email' });
			assert.isTrue(validateBase(ctx, 'foo.bar+junk@boo.far.museum', ctx.schema));
		});
	});

	describe('result object', function() {
		it('should have valid:true when valid', function() {
			var ctx = validationContext({});
			validateBase(ctx, 'test', ctx.schema);
			assert.isTrue(ctx.result.valid);
		});

		it('should have valid:false when invalid', function() {
			var ctx = validationContext({ type:'object' });
			validateBase(ctx, 'test', ctx.schema);
			assert.isFalse(ctx.result.valid);
		});

		it('should have an empty errors array when valid', function() {
			var ctx = validationContext({});
			validateBase(ctx, 'test', ctx.schema);
			assert.isArray(ctx.result.errors);
			assert.lengthOf(ctx.result.errors, 0);
		});

		it('should have populated errors array when invalid', function() {
			var ctx = validationContext({ type:'object' });
			validateBase(ctx, 'test', ctx.schema);
			assert.isArray(ctx.result.errors);
			assert.lengthOf(ctx.result.errors, 1);
		});
	});
});
var validateNumber = require('../../validators').types.number,
	validationContext = require('../../validation-context');


describe('Number validator', function() {
	describe('for type:number', function() {
		it('should validate an integer', function() {
			var ctx = validationContext({ type:'number' });
			assert.isTrue(validateNumber(ctx, 42, ctx.schema));
		});

		it('should validate a non-integer number', function() {
			var ctx = validationContext({ type:'number' });
			assert.isTrue(validateNumber(ctx, 42.1337, ctx.schema));
		});

		it('should validate a number over minimum', function() {
			var ctx = validationContext({ type:'number', minimum:0 });
			assert.isTrue(validateNumber(ctx, 42.1337, ctx.schema));
		});

		it('should invalidate a number under minimum', function() {
			var ctx = validationContext({ type:'number', minimum:1337 });
			assert.isFalse(validateNumber(ctx, 42.1337, ctx.schema));
		});

		it('should validate a number under maximum', function() {
			var ctx = validationContext({ type:'number', maximum:1337 });
			assert.isTrue(validateNumber(ctx, 42.1337, ctx.schema));
		});

		it('should invalidate a number over maximum', function() {
			var ctx = validationContext({ type:'number', maximum:0 });
			assert.isFalse(validateNumber(ctx, 42.1337, ctx.schema));
		});

		it('should validate that 4.5 is divisible by 1.5', function() {
			var ctx = validationContext({ divisibleBy:1.5 });
			assert.isTrue(validateNumber(ctx, 4.5, ctx.schema));
		});

		it('should validate that 0.0075 is multiple of 0.0001', function() {
			var ctx = validationContext({ multipleOf:0.0001 });
			assert.isTrue(validateNumber(ctx, 0.0075, ctx.schema));
		});
	});

	describe('for type:integer', function() {
		it('should validate an integer', function() {
			var ctx = validationContext({ type:'integer' });
			assert.isTrue(validateNumber(ctx, 42, ctx.schema));
		});

		it('should validate a non-integer number', function() {
			var ctx = validationContext({ type:'integer' });
			assert.isFalse(validateNumber(ctx, 42.1337, ctx.schema));
		});

		it('should validate an integer over minimum', function() {
			var ctx = validationContext({ type:'integer', minimum:0 });
			assert.isTrue(validateNumber(ctx, 42, ctx.schema));
		});

		it('should invalidate an integer under minimum', function() {
			var ctx = validationContext({ type:'integer', minimum:1337 });
			assert.isFalse(validateNumber(ctx, 42, ctx.schema));
		});

		it('should validate an integer under maximum', function() {
			var ctx = validationContext({ type:'integer', maximum:1337 });
			assert.isTrue(validateNumber(ctx, 42, ctx.schema));
		});

		it('should invalidate an integer over maximum', function() {
			var ctx = validationContext({ type:'integer', maximum:0 });
			assert.isFalse(validateNumber(ctx, 42, ctx.schema));
		});

		it('should validate that 42 is divisible by 6', function() {
			var ctx = validationContext({ divisibleBy:6 });
			assert.isTrue(validateNumber(ctx, 42, ctx.schema));
		});
	});
});
var validationResult = require('./validation-result'),
	jsonRefs = require('skeemas-json-refs');

var protoContext = {
	addError: function(message, subject, criteria) {
		if(!this.silent) this.result.addError(message, subject, criteria, this);
		return this;
	},
	silently: function(fn) {
		this.silent = true;
		var result = fn();
		this.silent = false;
		return result;
	},
	subcontext: function(schema) {
		return makeContext(schema, this, this.silent);
	},
	runValidations: function(validations, subject, schema) {
		var breakOnError = this.breakOnError,
			args = Array.prototype.slice.call(arguments),
			valid = true,
			validation;

		args[0] = this;

		for(var i = 0, len = validations.length; i < len; i++) {
			validation = validations[i];
			if(!validation[0]) continue;
			valid = validation[1].apply(null, args) && valid;
			if(breakOnError && !valid) return false;
		}

		return valid;
	}
};

var makeContext = module.exports = function(schema, context, forceNewResult) {
	context = context || {};
	return Object.create(protoContext, {
		id: { enumerable:true, writable:false, value: [] },
		schema: { enumerable:true, writable:false, value: schema || context.schema },
		path: { enumerable:true, writable:false, value: context.path && context.path.slice() || ['#'] },
		result: { enumerable:true, writable:false, value: (!forceNewResult && context.result) || validationResult(context.instance) },
		refs: { enumerable:true, writable:false, value: context.refs || jsonRefs() },
		silent: { enumerable:true, writable:true, value: false },
		breakOnError: { enumerable:true, writable:true, value: context.breakOnError || false },
		cleanWithDefaults: { enumerable:true, writable:true, value: context.cleanWithDefaults || false },
		cleanSubject: { enumerable:true, writable:true, value: undefined }
	});
};
function errorToString() {
	return this.message + ' (pointer: ' + this.context + ')';
}

var protoValidationResult = {
	addError: function(message, subject, criteria, context) {
		this.errors.push({
			message: message,
			context: context.path.join('/'),
			value: subject,
			criteria: criteria,
			toString: errorToString
		});
		this.valid = false;
		return this;
	}
};

module.exports = function(instance) {
	return Object.create(protoValidationResult, {
		instance: { enumerable:true, writable:false, value:instance },
		cleanInstance: { enumerable:true, writable:true, value: undefined },
		valid: { enumerable:true, writable:true, value:true },
		errors: { enumerable:true, writable:false, value:[] }
	});
};
var validateBase = require('./base'),
	deepEqual = require('./deep-equal');

function items(context, subject, schema, cleanItems) {
	var valid = true;

	if(Array.isArray(schema.items)) {
		valid = tupleItems(context, subject, schema, cleanItems);
		if('additionalItems' in schema) valid = additionalItems(context, subject, schema, cleanItems) && valid;
	} else if(schema.items) {
		valid = itemSchema(context, subject, schema, cleanItems);
	}

	return valid;
}

function itemSchema(context, subject, schema, cleanItems) {
	var items = schema.items;

	if(typeof items !== 'object')
		throw new Error('Invalid schema: invalid "items"');

	var lastPath = context.path.length;
	for(var i = 0, len = subject.length; i < len; i++) {
		context.path[lastPath] = i;
		if(!validateBase(context, subject[i], items)) {
			context.addError('Failed "items" criteria', subject, items);
			context.path.length = lastPath;
			return false;
		}
		cleanItems.push(context.cleanSubject);
	}
	context.path.length = lastPath;

	return true;
}

function tupleItems(context, subject, schema, cleanItems) {
	var items = schema.items,
		lastPath = context.path.length;
	for(var i = 0, len = items.length, lenSubject = subject.length; i < len && i < lenSubject; i++) {
		context.path[lastPath] = i;
		if(!validateBase(context, subject[i], items[i])) {
			context.addError('Failed "items" criteria', subject, items);
			context.path.length = lastPath;
			return false;
		}
		cleanItems.push(context.cleanSubject);
	}
	context.path.length = lastPath;

	return true;
}

function additionalItems(context, subject, schema, cleanItems) {
	var i = schema.items.length,
		len = subject.length,
		additionalItemSchema = schema.additionalItems;

	if(additionalItemSchema === false) {
		if(len <= i) return true;

		context.addError('Failed "additionalItems" criteria: no additional items are allowed', subject, schema);
		return false;
	}

	if(typeof additionalItemSchema !== 'object')
		throw new Error('Invalid schema: invalid "additionalItems"');

	var lastPath = context.path.length;
	for(; i < len; i++) {
		context.path[lastPath] = i;
		if(!validateBase(context, subject[i], additionalItemSchema)) {
			context.addError('Failed "additionalItems" criteria', subject, schema);
			context.path.length = lastPath;
			return false;
		}
		cleanItems.push(context.cleanSubject);
	}
	context.path.length = lastPath;

	return true;
}

function minItems(context, subject, schema) {
	if(subject.length < schema.minItems) {
		context.addError('Failed "minItems" criteria', subject, schema);
		return false;
	}

	return true;
}

function maxItems(context, subject, schema) {
	if(subject.length > schema.maxItems) {
		context.addError('Failed "maxItems" criteria', subject, schema);
		return false;
	}

	return true;
}

function uniqueItems(context, subject, schema) {
	var i = subject.length, j;

	while(i--) {
		j = i;
		while(j--) {
			if(deepEqual(subject[i], subject[j])) {
				context.addError('Failed "uniqueItems" criteria', subject, schema);
				return false;
			}
		}
	}

	return true;
}


module.exports = function(context, subject, schema) {
	if(!Array.isArray(subject)) {
		context.addError('Failed type:array criteria', schema);
		return false;
	}

	var cleanItems = [],
		valid = context.runValidations([
			[ 'minItems' in schema, minItems ],
			[ 'maxItems' in schema, maxItems ],
			[ 'uniqueItems' in schema, uniqueItems ],
			[ 'items' in schema, items ]
		], subject, schema, cleanItems);

	if('items' in schema)
		context.cleanSubject = cleanItems;
	else
		context.cleanSubject = subject.slice();

	return valid;
};
var INVALID_ESCAPES = /[^\\]\\[^.*+?^${}()|[\]\\bBcdDfnrsStvwWxu0-9]/;
var validators = require('./'),
	formats = {
		'date-time': /^\d{4}-(0[0-9]{1}|1[0-2]{1})-[0-9]{2}[t ]\d{2}:\d{2}:\d{2}(\.\d+)?([zZ]|[+-]\d{2}:\d{2})$/i,
		'date': /^\d{4}-(0[0-9]{1}|1[0-2]{1})-[0-9]{2}$/,
		'time': /^\d{2}:\d{2}:\d{2}$/,
		'color': /^(#[0-9a-f]{3}|#[0-9a-f]{6}|aqua|black|blue|fuchsia|gray|green|lime|maroon|navy|olive|orange|purple|red|silver|teal|white|yellow)$/i,
		'style': /^(?:\s*-?[_A-Z]+[_A-Z0-9-]*:[^\n\r\f;]+;)*\s*-?[_A-Z]+[_A-Z0-9-]*:[^\n\r\f;]+;?\s*$/i,
		'phone': /^(?:(?:\(?(?:00|\+)(?:[1-4]\d\d|[1-9]\d?)\)?)?[\-\.\ \\\/]?)?(?:(?:\(?\d{1,}\)?[\-\.\ \\\/]?){0,})(?:[\-\.\ \\\/]?(?:#|ext\.?|extension|x)[\-\.\ \\\/]?(?:\d+))?$/i,
		'uri': /^(?:([a-z0-9+.-]+:\/\/)((?:(?:[a-z0-9-._~!$&'()*+,;=:]|%[0-9A-F]{2})*)@)?((?:[a-z0-9-._~!$&'()*+,;=]|%[0-9A-F]{2})*)(:(?:\d*))?(\/(?:[a-z0-9-._~!$&'()*+,;=:@\/]|%[0-9A-F]{2})*)?|([a-z0-9+.-]+:)(\/?(?:[a-z0-9-._~!$&'()*+,;=:@]|%[0-9A-F]{2})(?:[a-z0-9-._~!$&'()*+,;=:@\/]|%[0-9A-F]{2})*)?)(\?(?:[a-z0-9-._~!$&'()*+,;=:\/?@]|%[0-9A-F]{2})*)?(#(?:[a-z0-9-._~!$&'()*+,;=:\/?@]|%[0-9A-F]{2})*)?$/i,
		'email': /^[A-Z0-9._%+-]+@(?:[A-Z0-9-]+\.)+[A-Z]{2,}$/i,
		'ipv4': /^(\d{1,2}|1\d\d|2[0-4]\d|25[0-5])\.(\d{1,2}|1\d\d|2[0-4]\d|25[0-5])\.(\d{1,2}|1\d\d|2[0-4]\d|25[0-5])\.(\d{1,2}|1\d\d|2[0-4]\d|25[0-5])$/,
		'ipv6': /^\s*((([0-9A-F]{1,4}:){7}([0-9A-F]{1,4}|:))|(([0-9A-F]{1,4}:){6}(:[0-9A-F]{1,4}|((25[0-5]|2[0-4]\d|1\d\d|[1-9]?\d)(\.(25[0-5]|2[0-4]\d|1\d\d|[1-9]?\d)){3})|:))|(([0-9A-F]{1,4}:){5}(((:[0-9A-F]{1,4}){1,2})|:((25[0-5]|2[0-4]\d|1\d\d|[1-9]?\d)(\.(25[0-5]|2[0-4]\d|1\d\d|[1-9]?\d)){3})|:))|(([0-9A-F]{1,4}:){4}(((:[0-9A-F]{1,4}){1,3})|((:[0-9A-F]{1,4})((25[0-5]|2[0-4]\d|1\d\d|[1-9]?\d)(\.(25[0-5]|2[0-4]\d|1\d\d|[1-9]?\d)){3}))|:))|(([0-9A-F]{1,4}:){3}(((:[0-9A-F]{1,4}){1,4})|((:[0-9A-F]{1,4}){0,2}:((25[0-5]|2[0-4]\d|1\d\d|[1-9]?\d)(\.(25[0-5]|2[0-4]\d|1\d\d|[1-9]?\d)){3}))|:))|(([0-9A-F]{1,4}:){2}(((:[0-9A-F]{1,4}){1,5})|((:[0-9A-F]{1,4}){0,3}:((25[0-5]|2[0-4]\d|1\d\d|[1-9]?\d)(\.(25[0-5]|2[0-4]\d|1\d\d|[1-9]?\d)){3}))|:))|(([0-9A-F]{1,4}:){1}(((:[0-9A-F]{1,4}){1,6})|((:[0-9A-F]{1,4}){0,4}:((25[0-5]|2[0-4]\d|1\d\d|[1-9]?\d)(\.(25[0-5]|2[0-4]\d|1\d\d|[1-9]?\d)){3}))|:))|(:(((:[0-9A-F]{1,4}){1,7})|((:[0-9A-F]{1,4}){0,5}:((25[0-5]|2[0-4]\d|1\d\d|[1-9]?\d)(\.(25[0-5]|2[0-4]\d|1\d\d|[1-9]?\d)){3}))|:)))(%.+)?\s*$/i,

		// hostname regex from: http://stackoverflow.com/a/1420225/5628
		'hostname': /^(?=.{1,255}$)[0-9A-Z](?:(?:[0-9A-Z]|-){0,61}[0-9A-Z])?(?:\.[0-9A-Z](?:(?:[0-9A-Z]|-){0,61}[0-9A-Z])?)*\.?$/i,

		'utc-millisec': function(subject) {
			var parsed = parseInt(subject, 10);
			return !isNaN(parsed) && parsed.toString() === subject.toString();
		},
		'regex': function (subject) {
			if(INVALID_ESCAPES.test(subject)) return false;
			try {
				new RegExp(subject);
				return true;
			}
			catch(e) {
				return false;
			}
		}
	};

// aliases
formats['host-name'] = formats.hostname;
formats['ip-address'] = formats.ipv4;


function getType(subject) {
	var type = typeof subject;

	if(type === 'object') {
		if(subject === null) return 'null';
		if(Array.isArray(subject)) return 'array';
	}

	if(type === 'number' && subject === Math.round(subject)) return 'integer';

	return type;
}

function format(context, subject, schema) {
	var fmt = schema.format,
		validator = formats[fmt];

	if(!validator)
		throw new Error('Invalid schema: unknown format (' + fmt + ')');

	var valid = validator.test ? validator.test(subject) : validator(subject);
	if(!valid) {
		context.addError('Failed "format" criteria (' + fmt + ')', subject, schema);
	}

	return valid;
}

function validateTypes(context, subject, type, validTypes) {
	var i = validTypes.length,
		validType, valid;
	while(i--) {
		validType = validTypes[i];

		if(validType === 'any') return true;

		if(typeof validType === 'object') {
			valid = context.silently(function() {
				return validateBase(context, subject, validType);
			}); // jshint ignore:line
			if(valid) return true;
			else continue;
		}

		if(!(validType in validators.types))
			throw new Error('Invalid schema: invalid type (' + validType + ')');

		if(validType === 'number' && type === 'integer') return true;

		if(type === validType) return true;
	}

	return false;
}

function allOf(context, subject, schema) {
	var schemas = schema.allOf;

	if(!Array.isArray(schemas))
		throw new Error('Invalid schema: "allOf" value must be an array');

	var i = schemas.length,
		invalidCount = 0;
	while(i--) {
		if(!validateBase(context, subject, schemas[i])) {
			invalidCount += 1;
		}
	}

	if(invalidCount === 0) return true;

	context.addError('Failed "allOf" criteria', subject, schemas);
	return false;
}

function anyOf(context, subject, schema) {
	var schemas = schema.anyOf;

	if(!Array.isArray(schemas))
		throw new Error('Invalid schema: "anyOf" value must be an array');

	var matched = context.silently(function() {
		var i = schemas.length;
		while(i--) {
			if(validateBase(context, subject, schemas[i])) return true;
		}
		return false;
	});

	if(matched) return true;

	context.addError('Failed "anyOf" criteria', subject, schemas);
	return false;
}

function oneOf(context, subject, schema) {
	var schemas = schema.oneOf;

	if(!Array.isArray(schemas))
		throw new Error('Invalid schema: "oneOf" value must be an array');

	var i = schemas.length,
		validCount = 0;
	context.silently(function() {
		while(i--) {
			if(validateBase(context, subject, schemas[i])) validCount += 1;
		}
	});

	if(validCount === 1) return true;

	context.addError('Failed "oneOf" criteria', subject, schemas);
	return false;
}

function not(context, subject, schema) {
	var badSchema = schema.not,
		valid = context.silently(function() {
			return !validateBase(context, subject, badSchema);
		});

	if(valid) return true;

	context.addError('Failed "not" criteria', subject, schema);
	return false;
}

function disallow(context, subject, schema, type) {
	var invalidTypes = Array.isArray(schema.disallow) ? schema.disallow : [ schema.disallow ],
		valid = !validateTypes(context, subject, type, invalidTypes);

	if(!valid) {
		context.addError('Failed "disallow" criteria: expecting ' + invalidTypes.join(' or ') + ', found ' + type, subject, schema);
	}

	return valid;
}

function validateExtends(context, subject, schema) {
	var schemas = Array.isArray(schema["extends"]) ? schema["extends"] : [ schema["extends"] ];

	var i = schemas.length,
		invalidCount = 0;
	while(i--) {
		if(!validateBase(context, subject, schemas[i])) {
			invalidCount += 1;
		}
	}

	return invalidCount === 0;
}

function validateEnum(context, subject, schema) {
	var values = schema['enum'];

	if(!Array.isArray(values))
		throw new Error('Invalid schema: "enum" value must be an array');

	var i = values.length;
	while(i--) {
		if(validators.deepEqual(subject, values[i])) return true;
	}

	context.addError('Failed "enum" criteria', subject, values);
	return false;
}

function validateType(context, subject, schema, type) {
	var validTypes = Array.isArray(schema.type) ? schema.type : [ schema.type ],
		valid = validateTypes(context, subject, type, validTypes);

	if(!valid) {
		context.addError('Failed "type" criteria: expecting ' + validTypes.join(' or ') + ', found ' + type, subject, schema);
	}

	return valid;
}

function typeValidations(context, subject, schema, type) {
	return validators.types[type](context, subject, schema);
}

function pathFromIds(ids) {
	return ids.map(function(id) {
		var lastSlash = id.lastIndexOf("/");
		if(lastSlash === -1) return id;
		return id.substr(0, lastSlash + 1);
	}).join('');
}

function $ref(context, subject, schema) {
	var absolute = /^(#|\/)/.test(schema.$ref),
		ref = absolute ? schema.$ref : pathFromIds(context.id) + schema.$ref,
		refSchema = context.refs.get(ref, context.schema),
		ctx = context;

	if(schema.$ref[0] !== '#') {
		ctx = context.subcontext(context.refs.get(ref, context.schema, true));
	}

	var valid = validateBase(ctx, subject, refSchema);

	context.cleanSubject = ctx.cleanSubject;

	return valid;
}



function validateBase(context, subject, schema) {
	if(schema.$ref) {
		return $ref(context, subject, schema);
	}

	if(schema.id) context.id.push(schema.id);

	var valid = context.runValidations([
		[ 'type' in schema, validateType ],
		[ 'disallow' in schema, disallow ],
		[ 'enum' in schema, validateEnum ],
		[ true, typeValidations ],
		[ 'format' in schema, format ],
		[ 'extends' in schema, validateExtends ],
		[ 'allOf' in schema, allOf ],
		[ 'anyOf' in schema, anyOf ],
		[ 'oneOf' in schema, oneOf ],
		[ 'not' in schema, not ]
	], subject, schema, getType(subject));

	if(schema.id) context.id.pop();

	return valid;
}

module.exports = validateBase;
function validateBoolean(context, subject, schema) {
	if(typeof subject !== 'boolean') {
		context.addError('Failed type:boolean criteria', subject, schema);
		return false;
	}

	context.cleanSubject = subject;

	return true;
}

module.exports = validateBoolean;
function getType(subject) {
	var type = typeof subject;

	if(type === 'object') {
		if(subject === null) return 'null';
		if(Array.isArray(subject)) return 'array';
	}
	return type;
}

function arrayEqual(a, b) {
	var i = a.length;

	if(i !== b.length) return false;

	while(i--) {
		if(!deepEqual(a[i], b[i])) return false;
	}

	return true;
}

function objectEqual(a, b) {
	var keys = Object.keys(a),
		i = keys.length;

	if(i !== Object.keys(b).length) return false;

	while(i--) {
		if(!deepEqual(a[keys[i]], b[keys[i]])) return false;
	}

	return true;
}

var deepEqual = module.exports = function(a, b) {
	if(a === b) return true;

	var t = getType(a);

	if(t !== getType(b)) return false;

	if(t === 'array') return arrayEqual(a, b);
	if(t === 'object') return objectEqual(a, b);

	return false;
};
exports.types = {
	'any': function() { return true; },
	'array': require('./array'),
	'boolean': require('./boolean'),
	'integer': require('./number'),
	'null': require('./null'),
	'number': require('./number'),
	'object': require('./object'),
	'string': require('./string')
};

exports.deepEqual = require('./deep-equal');

// base cannot be required until other validators are added
exports.base = require('./base');
function validateNull(context, subject, schema) {
	if(subject !== null) {
		context.addError('Failed type:null criteria', subject, schema);
		return false;
	}

	context.cleanSubject = subject;

	return true;
}

module.exports = validateNull;
function validateNumber(context, subject, schema) {
	if(typeof subject !== 'number') {
		context.addError('Failed type:number criteria', subject, schema);
		return false;
	}

	return true;
}

function validateInteger(context, subject, schema) {
	if(typeof subject !== 'number' || subject !== Math.round(subject)) {
		context.addError('Failed type:integer criteria', subject, schema);
		return false;
	}

	return true;
}

function minimum(context, subject, schema) {
	var valid = (schema.exclusiveMinimum) ? subject > schema.minimum : subject >= schema.minimum;

	if(!valid) context.addError('Failed "minimum" criteria', subject, schema);

	return valid;
}

function maximum(context, subject, schema) {
	var valid = (schema.exclusiveMaximum) ? subject < schema.maximum : subject <= schema.maximum;

	if(!valid) context.addError('Failed "maximum" criteria', subject, schema);

	return valid;
}

function multipleOf(context, subject, schema, key) {
	key = key || 'multipleOf';

	var valid = (subject / schema[key] % 1) === 0;

	if(!valid) context.addError('Failed "' + key + '" criteria', subject, schema);

	return valid;
}

function divisibleBy(context, subject, schema) {
	return multipleOf(context, subject, schema, 'divisibleBy');
}



module.exports = function(context, subject, schema) {
	var valid = true,
		isType = true;

	if(schema.type === 'number') isType = validateNumber(context, subject, schema);
	if(schema.type === 'integer') isType = validateInteger(context, subject, schema);

	context.cleanSubject = subject;

	return isType && context.runValidations([
		[ 'minimum' in schema, minimum ],
		[ 'maximum' in schema, maximum ],
		[ 'multipleOf' in schema, multipleOf ],
		[ 'divisibleBy' in schema, divisibleBy ]
	], subject, schema);
};
var validateBase = require('./base');

function properties(context, subject, schema, handledProps) {
	var props = schema.properties,
		valid = true;
	for(var key in props) {
		if(key in subject) {
			context.path.push(key);
			valid = validateBase(context, subject[key], props[key]) && valid;
			context.path.pop();
			handledProps[key] = context.cleanSubject;
		} else if(props[key].required === true) {
			context.addError('Failed "required" criteria: missing property (' + key + ')', subject, props);
			valid = false;
		}
	}

	return valid;
}

function patternProperties(context, subject, schema, handledProps) {
	var patternProps = schema.patternProperties;

	if(typeof patternProps !== 'object')
		throw new Error('Invalid schema: "patternProperties" must be an object');

	var valid = true,
		patterns = Object.keys(patternProps),
		len = patterns.length,
		keys = Object.keys(subject),
		i = keys.length,
		j, key;

	while(i--) {
		key = keys[i];

		j = len;
		while(j--) {
			if(key.match(patterns[j])) {
				context.path.push(key);
				valid = validateBase(context, subject[key], patternProps[patterns[j]]) && valid;
				context.path.pop();
				if(!(key in handledProps)) handledProps[key] = context.cleanSubject;
			}
		}
	}

	return valid;
}

function additionalProperties(context, subject, schema, handledProps) {
	var additionalProps = schema.additionalProperties;

	if(additionalProps === true) return true;

	var keys = Object.keys(subject),
		i = keys.length;
	if(additionalProps === false) {
		while(i--) {
			if(!(keys[i] in handledProps)) {
				context.addError('Failed "additionalProperties" criteria: unexpected property (' + keys[i] + ')', subject, schema);
				return false;
			}
		}
		return true;
	}

	if(typeof additionalProps !== 'object')
		throw new Error('Invalid schema: "additionalProperties" must be a valid schema');

	var valid;
	while(i--) {
		if(keys[i] in handledProps) continue;

		context.path.push(keys[i]);
		valid = validateBase(context, subject[keys[i]], additionalProps) && valid;
		context.path.pop();
		handledProps[keys[i]] = context.cleanSubject;
	}

	return valid;
}

function minProperties(context, subject, schema) {
	var keys = Object.keys(subject);
	if(keys.length < schema.minProperties) {
		context.addError('Failed "minProperties" criteria', subject, schema);
		return false;
	}
	return true;
}

function maxProperties(context, subject, schema) {
	var keys = Object.keys(subject);
	if(keys.length > schema.maxProperties) {
		context.addError('Failed "maxProperties" criteria', subject, schema);
		return false;
	}
	return true;
}

function required(context, subject, schema) {
	var requiredProps = schema.required;

	if(!Array.isArray(requiredProps))
		throw new Error('Invalid schema: "required" must be an array');

	var valid = true,
		i = requiredProps.length;
	while(i--) {
		if(!(requiredProps[i] in subject)) {
			context.addError('Missing required property "' + requiredProps[i] + '"', subject, requiredProps[i]);
			valid = false;
		}
	}

	return valid;
}

function dependencies(context, subject, schema) {
	var deps = schema.dependencies;

	if(typeof deps !== 'object')
		throw new Error('Invalid schema: "dependencies" must be an object');

	var valid = true,
		keys = Object.keys(deps),
		i = keys.length,
		requiredProps, j;

	while(i--) {
		if(!(keys[i] in subject)) continue;

		requiredProps = deps[keys[i]];

		if(typeof requiredProps === 'string') requiredProps = [ requiredProps ];

		if(Array.isArray(requiredProps)) {
			j = requiredProps.length;
			while(j--) {
				if(!(requiredProps[j] in subject)) {
					context.addError('Missing required property "' + requiredProps[j] + '"', subject, requiredProps[j]);
					valid = false;
				}
			}
		} else if(typeof requiredProps === 'object') {
			valid = validateBase(context, subject, requiredProps) && valid;
		} else {
			throw new Error('Invalid schema: dependencies must be string, array, or object');
		}
	}

	return valid;
}

function addDefaults(subject, schema) {
	var props = schema.properties;

	if(!props) return;

	for(var key in props) {
		if('default' in props[key] && !(key in subject)) {
			subject[key] = props[key].default;
		}
	}
}


function validateObject(context, subject, schema) {
	if(typeof subject !== 'object') {
		context.addError('Failed type:object criteria', subject, schema);
		return false;
	}

	var handledProps = {},
		valid = context.runValidations([
			[ 'properties' in schema, properties ],
			[ 'patternProperties' in schema, patternProperties ],
			[ 'additionalProperties' in schema, additionalProperties ],
			[ 'minProperties' in schema, minProperties ],
			[ 'maxProperties' in schema, maxProperties ],
			[ Array.isArray(schema.required), required ],
			[ 'dependencies' in schema, dependencies ]
		], subject, schema, handledProps);

	if(context.cleanWithDefaults) addDefaults(handledProps, schema);

	context.cleanSubject = handledProps;

	return valid;
}

module.exports = validateObject;
var decode = require('punycode').ucs2.decode;


function minLength(context, subject, schema) {
	if(decode(subject).length < schema.minLength) {
		context.addError('Failed "minLength" criteria', subject, schema);
		return false;
	}

	return true;
}

function maxLength(context, subject, schema) {
	if(decode(subject).length > schema.maxLength) {
		context.addError('Failed "maxLength" criteria', subject, schema);
		return false;
	}

	return true;
}

function pattern(context, subject, schema) {
	var strPattern = schema.pattern;

	if(!subject.match(strPattern)) {
		context.addError('Failed "pattern" criteria (' + strPattern + ')', subject, strPattern);
		return false;
	}

	return true;
}



function validateString(context, subject, schema) {
	if(typeof subject !== 'string') {
		context.addError('Failed type:string criteria', schema);
		return false;
	}

	context.cleanSubject = subject;

	return context.runValidations([
		[ 'minLength' in schema, minLength ],
		[ 'maxLength' in schema, maxLength ],
		[ 'pattern' in schema, pattern ]
	], subject, schema);
}

module.exports = validateString;