array.js

'use strict';

const Assert = require('@hapi/hoek/lib/assert');
const DeepEqual = require('@hapi/hoek/lib/deepEqual');
const Reach = require('@hapi/hoek/lib/reach');

const Any = require('./any');
const Common = require('../common');
const Compile = require('../compile');


const internals = {};


module.exports = Any.extend({

    type: 'array',

    flags: {

        single: { default: false },
        sparse: { default: false }
    },

    terms: {

        items: { init: [], manifest: 'schema' },
        ordered: { init: [], manifest: 'schema' },

        _exclusions: { init: [] },
        _inclusions: { init: [] },
        _requireds: { init: [] }
    },

    coerce: {
        from: 'object',
        method(value, { schema, state, prefs }) {

            if (!Array.isArray(value)) {
                return;
            }

            const sort = schema.$_getRule('sort');
            if (!sort) {
                return;
            }

            return internals.sort(schema, value, sort.args.options, state, prefs);
        }
    },

    validate(value, { schema, error }) {

        if (!Array.isArray(value)) {
            if (schema._flags.single) {
                const single = [value];
                single[Common.symbols.arraySingle] = true;
                return { value: single };
            }

            return { errors: error('array.base') };
        }

        if (!schema.$_getRule('items') &&
            !schema.$_terms.externals) {

            return;
        }

        return { value: value.slice() };        // Clone the array so that we don't modify the original
    },

    rules: {

        has: {
            method(schema) {

                schema = this.$_compile(schema, { appendPath: true });
                const obj = this.$_addRule({ name: 'has', args: { schema } });
                obj.$_mutateRegister(schema);
                return obj;
            },
            validate(value, { state, prefs, error }, { schema: has }) {

                const ancestors = [value, ...state.ancestors];
                for (let i = 0; i < value.length; ++i) {
                    const localState = state.localize([...state.path, i], ancestors, has);
                    if (has.$_match(value[i], localState, prefs)) {
                        return value;
                    }
                }

                const patternLabel = has._flags.label;
                if (patternLabel) {
                    return error('array.hasKnown', { patternLabel });
                }

                return error('array.hasUnknown', null);
            },
            multi: true
        },

        items: {
            method(...schemas) {

                Common.verifyFlat(schemas, 'items');

                const obj = this.$_addRule('items');

                for (let i = 0; i < schemas.length; ++i) {
                    const type = Common.tryWithPath(() => this.$_compile(schemas[i]), i, { append: true });
                    obj.$_terms.items.push(type);
                }

                return obj.$_mutateRebuild();
            },
            validate(value, { schema, error, state, prefs }) {

                const requireds = schema.$_terms._requireds.slice();
                const ordereds = schema.$_terms.ordered.slice();
                const inclusions = [...schema.$_terms._inclusions, ...requireds];

                const wasArray = !value[Common.symbols.arraySingle];
                delete value[Common.symbols.arraySingle];

                const errors = [];
                let il = value.length;
                for (let i = 0; i < il; ++i) {
                    const item = value[i];

                    let errored = false;
                    let isValid = false;

                    const key = wasArray ? i : new Number(i);       // eslint-disable-line no-new-wrappers
                    const path = [...state.path, key];

                    // Sparse

                    if (!schema._flags.sparse &&
                        item === undefined) {

                        errors.push(error('array.sparse', { key, path, pos: i, value: undefined }, state.localize(path)));
                        if (prefs.abortEarly) {
                            return errors;
                        }

                        ordereds.shift();
                        continue;
                    }

                    // Exclusions

                    const ancestors = [value, ...state.ancestors];

                    for (const exclusion of schema.$_terms._exclusions) {
                        if (!exclusion.$_match(item, state.localize(path, ancestors, exclusion), prefs, { presence: 'ignore' })) {
                            continue;
                        }

                        errors.push(error('array.excludes', { pos: i, value: item }, state.localize(path)));
                        if (prefs.abortEarly) {
                            return errors;
                        }

                        errored = true;
                        ordereds.shift();
                        break;
                    }

                    if (errored) {
                        continue;
                    }

                    // Ordered

                    if (schema.$_terms.ordered.length) {
                        if (ordereds.length) {
                            const ordered = ordereds.shift();
                            const res = ordered.$_validate(item, state.localize(path, ancestors, ordered), prefs);
                            if (!res.errors) {
                                if (ordered._flags.result === 'strip') {
                                    internals.fastSplice(value, i);
                                    --i;
                                    --il;
                                }
                                else if (!schema._flags.sparse && res.value === undefined) {
                                    errors.push(error('array.sparse', { key, path, pos: i, value: undefined }, state.localize(path)));
                                    if (prefs.abortEarly) {
                                        return errors;
                                    }

                                    continue;
                                }
                                else {
                                    value[i] = res.value;
                                }
                            }
                            else {
                                errors.push(...res.errors);
                                if (prefs.abortEarly) {
                                    return errors;
                                }
                            }

                            continue;
                        }
                        else if (!schema.$_terms.items.length) {
                            errors.push(error('array.orderedLength', { pos: i, limit: schema.$_terms.ordered.length }));
                            if (prefs.abortEarly) {
                                return errors;
                            }

                            break;      // No reason to continue since there are no other rules to validate other than array.orderedLength
                        }
                    }

                    // Requireds

                    const requiredChecks = [];
                    let jl = requireds.length;
                    for (let j = 0; j < jl; ++j) {
                        const localState = state.localize(path, ancestors, requireds[j]);
                        localState.snapshot();

                        const res = requireds[j].$_validate(item, localState, prefs);
                        requiredChecks[j] = res;

                        if (!res.errors) {
                            value[i] = res.value;
                            isValid = true;
                            internals.fastSplice(requireds, j);
                            --j;
                            --jl;

                            if (!schema._flags.sparse &&
                                res.value === undefined) {

                                errors.push(error('array.sparse', { key, path, pos: i, value: undefined }, state.localize(path)));
                                if (prefs.abortEarly) {
                                    return errors;
                                }
                            }

                            break;
                        }

                        localState.restore();
                    }

                    if (isValid) {
                        continue;
                    }

                    // Inclusions

                    const stripUnknown = prefs.stripUnknown && !!prefs.stripUnknown.arrays || false;

                    jl = inclusions.length;
                    for (const inclusion of inclusions) {

                        // Avoid re-running requireds that already didn't match in the previous loop

                        let res;
                        const previousCheck = requireds.indexOf(inclusion);
                        if (previousCheck !== -1) {
                            res = requiredChecks[previousCheck];
                        }
                        else {
                            const localState = state.localize(path, ancestors, inclusion);
                            localState.snapshot();

                            res = inclusion.$_validate(item, localState, prefs);
                            if (!res.errors) {
                                if (inclusion._flags.result === 'strip') {
                                    internals.fastSplice(value, i);
                                    --i;
                                    --il;
                                }
                                else if (!schema._flags.sparse &&
                                    res.value === undefined) {

                                    errors.push(error('array.sparse', { key, path, pos: i, value: undefined }, state.localize(path)));
                                    errored = true;
                                }
                                else {
                                    value[i] = res.value;
                                }

                                isValid = true;
                                break;
                            }

                            localState.restore();
                        }

                        // Return the actual error if only one inclusion defined

                        if (jl === 1) {
                            if (stripUnknown) {
                                internals.fastSplice(value, i);
                                --i;
                                --il;
                                isValid = true;
                                break;
                            }

                            errors.push(...res.errors);
                            if (prefs.abortEarly) {
                                return errors;
                            }

                            errored = true;
                            break;
                        }
                    }

                    if (errored) {
                        continue;
                    }

                    if (schema.$_terms._inclusions.length &&
                        !isValid) {

                        if (stripUnknown) {
                            internals.fastSplice(value, i);
                            --i;
                            --il;
                            continue;
                        }

                        errors.push(error('array.includes', { pos: i, value: item }, state.localize(path)));
                        if (prefs.abortEarly) {
                            return errors;
                        }
                    }
                }

                if (requireds.length) {
                    internals.fillMissedErrors(schema, errors, requireds, value, state, prefs);
                }

                if (ordereds.length) {
                    internals.fillOrderedErrors(schema, errors, ordereds, value, state, prefs);
                }

                return errors.length ? errors : value;
            },

            priority: true,
            manifest: false
        },

        length: {
            method(limit) {

                return this.$_addRule({ name: 'length', args: { limit }, operator: '=' });
            },
            validate(value, helpers, { limit }, { name, operator, args }) {

                if (Common.compare(value.length, limit, operator)) {
                    return value;
                }

                return helpers.error('array.' + name, { limit: args.limit, value });
            },
            args: [
                {
                    name: 'limit',
                    ref: true,
                    assert: Common.limit,
                    message: 'must be a positive integer'
                }
            ]
        },

        max: {
            method(limit) {

                return this.$_addRule({ name: 'max', method: 'length', args: { limit }, operator: '<=' });
            }
        },

        min: {
            method(limit) {

                return this.$_addRule({ name: 'min', method: 'length', args: { limit }, operator: '>=' });
            }
        },

        ordered: {
            method(...schemas) {

                Common.verifyFlat(schemas, 'ordered');

                const obj = this.$_addRule('items');

                for (let i = 0; i < schemas.length; ++i) {
                    const type = Common.tryWithPath(() => this.$_compile(schemas[i]), i, { append: true });
                    internals.validateSingle(type, obj);

                    obj.$_mutateRegister(type);
                    obj.$_terms.ordered.push(type);
                }

                return obj.$_mutateRebuild();
            }
        },

        single: {
            method(enabled) {

                const value = enabled === undefined ? true : !!enabled;
                Assert(!value || !this._flags._arrayItems, 'Cannot specify single rule when array has array items');

                return this.$_setFlag('single', value);
            }
        },

        sort: {
            method(options = {}) {

                Common.assertOptions(options, ['by', 'order']);

                const settings = {
                    order: options.order || 'ascending'
                };

                if (options.by) {
                    settings.by = Compile.ref(options.by, { ancestor: 0 });
                    Assert(!settings.by.ancestor, 'Cannot sort by ancestor');
                }

                return this.$_addRule({ name: 'sort', args: { options: settings } });
            },
            validate(value, { error, state, prefs, schema }, { options }) {

                const { value: sorted, errors } = internals.sort(schema, value, options, state, prefs);
                if (errors) {
                    return errors;
                }

                for (let i = 0; i < value.length; ++i) {
                    if (value[i] !== sorted[i]) {
                        return error('array.sort', { order: options.order, by: options.by ? options.by.key : 'value' });
                    }
                }

                return value;
            },
            convert: true
        },

        sparse: {
            method(enabled) {

                const value = enabled === undefined ? true : !!enabled;

                if (this._flags.sparse === value) {
                    return this;
                }

                const obj = value ? this.clone() : this.$_addRule('items');
                return obj.$_setFlag('sparse', value, { clone: false });
            }
        },

        unique: {
            method(comparator, options = {}) {

                Assert(!comparator || typeof comparator === 'function' || typeof comparator === 'string', 'comparator must be a function or a string');
                Common.assertOptions(options, ['ignoreUndefined', 'separator']);

                const rule = { name: 'unique', args: { options, comparator } };

                if (comparator) {
                    if (typeof comparator === 'string') {
                        const separator = Common.default(options.separator, '.');
                        rule.path = separator ? comparator.split(separator) : [comparator];
                    }
                    else {
                        rule.comparator = comparator;
                    }
                }

                return this.$_addRule(rule);
            },
            validate(value, { state, error, schema }, { comparator: raw, options }, { comparator, path }) {

                const found = {
                    string: Object.create(null),
                    number: Object.create(null),
                    undefined: Object.create(null),
                    boolean: Object.create(null),
                    object: new Map(),
                    function: new Map(),
                    custom: new Map()
                };

                const compare = comparator || DeepEqual;
                const ignoreUndefined = options.ignoreUndefined;

                for (let i = 0; i < value.length; ++i) {
                    const item = path ? Reach(value[i], path) : value[i];
                    const records = comparator ? found.custom : found[typeof item];
                    Assert(records, 'Failed to find unique map container for type', typeof item);

                    if (records instanceof Map) {
                        const entries = records.entries();
                        let current;
                        while (!(current = entries.next()).done) {
                            if (compare(current.value[0], item)) {
                                const localState = state.localize([...state.path, i], [value, ...state.ancestors]);
                                const context = {
                                    pos: i,
                                    value: value[i],
                                    dupePos: current.value[1],
                                    dupeValue: value[current.value[1]]
                                };

                                if (path) {
                                    context.path = raw;
                                }

                                return error('array.unique', context, localState);
                            }
                        }

                        records.set(item, i);
                    }
                    else {
                        if ((!ignoreUndefined || item !== undefined) &&
                            records[item] !== undefined) {

                            const context = {
                                pos: i,
                                value: value[i],
                                dupePos: records[item],
                                dupeValue: value[records[item]]
                            };

                            if (path) {
                                context.path = raw;
                            }

                            const localState = state.localize([...state.path, i], [value, ...state.ancestors]);
                            return error('array.unique', context, localState);
                        }

                        records[item] = i;
                    }
                }

                return value;
            },
            args: ['comparator', 'options'],
            multi: true
        }
    },

    cast: {
        set: {
            from: Array.isArray,
            to(value, helpers) {

                return new Set(value);
            }
        }
    },

    rebuild(schema) {

        schema.$_terms._inclusions = [];
        schema.$_terms._exclusions = [];
        schema.$_terms._requireds = [];

        for (const type of schema.$_terms.items) {
            internals.validateSingle(type, schema);

            if (type._flags.presence === 'required') {
                schema.$_terms._requireds.push(type);
            }
            else if (type._flags.presence === 'forbidden') {
                schema.$_terms._exclusions.push(type);
            }
            else {
                schema.$_terms._inclusions.push(type);
            }
        }

        for (const type of schema.$_terms.ordered) {
            internals.validateSingle(type, schema);
        }
    },

    manifest: {

        build(obj, desc) {

            if (desc.items) {
                obj = obj.items(...desc.items);
            }

            if (desc.ordered) {
                obj = obj.ordered(...desc.ordered);
            }

            return obj;
        }
    },

    messages: {
        'array.base': '"{{#label}}" must be an array',
        'array.excludes': '"{{#label}}" contains an excluded value',
        'array.hasKnown': '"{{#label}}" does not contain at least one required match for type "{#patternLabel}"',
        'array.hasUnknown': '"{{#label}}" does not contain at least one required match',
        'array.includes': '"{{#label}}" does not match any of the allowed types',
        'array.includesRequiredBoth': '"{{#label}}" does not contain {{#knownMisses}} and {{#unknownMisses}} other required value(s)',
        'array.includesRequiredKnowns': '"{{#label}}" does not contain {{#knownMisses}}',
        'array.includesRequiredUnknowns': '"{{#label}}" does not contain {{#unknownMisses}} required value(s)',
        'array.length': '"{{#label}}" must contain {{#limit}} items',
        'array.max': '"{{#label}}" must contain less than or equal to {{#limit}} items',
        'array.min': '"{{#label}}" must contain at least {{#limit}} items',
        'array.orderedLength': '"{{#label}}" must contain at most {{#limit}} items',
        'array.sort': '"{{#label}}" must be sorted in {#order} order by {{#by}}',
        'array.sort.mismatching': '"{{#label}}" cannot be sorted due to mismatching types',
        'array.sort.unsupported': '"{{#label}}" cannot be sorted due to unsupported type {#type}',
        'array.sparse': '"{{#label}}" must not be a sparse array item',
        'array.unique': '"{{#label}}" contains a duplicate value'
    }
});


// Helpers

internals.fillMissedErrors = function (schema, errors, requireds, value, state, prefs) {

    const knownMisses = [];
    let unknownMisses = 0;
    for (const required of requireds) {
        const label = required._flags.label;
        if (label) {
            knownMisses.push(label);
        }
        else {
            ++unknownMisses;
        }
    }

    if (knownMisses.length) {
        if (unknownMisses) {
            errors.push(schema.$_createError('array.includesRequiredBoth', value, { knownMisses, unknownMisses }, state, prefs));
        }
        else {
            errors.push(schema.$_createError('array.includesRequiredKnowns', value, { knownMisses }, state, prefs));
        }
    }
    else {
        errors.push(schema.$_createError('array.includesRequiredUnknowns', value, { unknownMisses }, state, prefs));
    }
};


internals.fillOrderedErrors = function (schema, errors, ordereds, value, state, prefs) {

    const requiredOrdereds = [];

    for (const ordered of ordereds) {
        if (ordered._flags.presence === 'required') {
            requiredOrdereds.push(ordered);
        }
    }

    if (requiredOrdereds.length) {
        internals.fillMissedErrors(schema, errors, requiredOrdereds, value, state, prefs);
    }
};


internals.fastSplice = function (arr, i) {

    let pos = i;
    while (pos < arr.length) {
        arr[pos++] = arr[pos];
    }

    --arr.length;
};


internals.validateSingle = function (type, obj) {

    if (type.type === 'array' ||
        type._flags._arrayItems) {

        Assert(!obj._flags.single, 'Cannot specify array item with single rule enabled');
        obj.$_setFlag('_arrayItems', true, { clone: false });
    }
};


internals.sort = function (schema, value, settings, state, prefs) {

    const order = settings.order === 'ascending' ? 1 : -1;
    const aFirst = -1 * order;
    const bFirst = order;

    const sort = (a, b) => {

        let compare = internals.compare(a, b, aFirst, bFirst);
        if (compare !== null) {
            return compare;
        }

        if (settings.by) {
            a = settings.by.resolve(a, state, prefs);
            b = settings.by.resolve(b, state, prefs);
        }

        compare = internals.compare(a, b, aFirst, bFirst);
        if (compare !== null) {
            return compare;
        }

        const type = typeof a;
        if (type !== typeof b) {
            throw schema.$_createError('array.sort.mismatching', value, null, state, prefs);
        }

        if (type !== 'number' &&
            type !== 'string') {

            throw schema.$_createError('array.sort.unsupported', value, { type }, state, prefs);
        }

        if (type === 'number') {
            return (a - b) * order;
        }

        return a < b ? aFirst : bFirst;
    };

    try {
        return { value: value.slice().sort(sort) };
    }
    catch (err) {
        return { errors: err };
    }
};


internals.compare = function (a, b, aFirst, bFirst) {

    if (a === b) {
        return 0;
    }

    if (a === undefined) {
        return 1;           // Always last regardless of sort order
    }

    if (b === undefined) {
        return -1;           // Always last regardless of sort order
    }

    if (a === null) {
        return bFirst;
    }

    if (b === null) {
        return aFirst;
    }

    return null;
};