Skip to main content

request/complement.js

var iterateKeySet = require("falcor-path-utils").iterateKeySet;

/**
 * Calculates what paths in requested path sets can be deduplicated based on an existing optimized path tree.
 *
 * For path sets with ranges or key sets, if some expanded paths can be found in the path tree, only matching paths are
 * returned as intersection. The non-matching expanded paths are returned as complement.
 *
 * The function returns an object consisting of:
 * - intersection: requested paths that were matched to the path tree
 * - optimizedComplement: optimized paths that were not found in the path tree
 * - requestedComplement: requested paths for the optimized paths that were not found in the path tree
 */
module.exports = function complement(requested, optimized, tree) {
    var optimizedComplement = [];
    var requestedComplement = [];
    var intersection = [];
    var i, iLen;

    for (i = 0, iLen = optimized.length; i < iLen; ++i) {
        var oPath = optimized[i];
        var rPath = requested[i];
        var subTree = tree[oPath.length];

        var intersectionData = findPartialIntersections(rPath, oPath, subTree);
        Array.prototype.push.apply(intersection, intersectionData[0]);
        Array.prototype.push.apply(optimizedComplement, intersectionData[1]);
        Array.prototype.push.apply(requestedComplement, intersectionData[2]);
    }

    return {
        intersection: intersection,
        optimizedComplement: optimizedComplement,
        requestedComplement: requestedComplement
    };
};

/**
 * Recursive function to calculate intersection and complement paths in 2 given pathsets at a given depth.
 *
 * Parameters:
 *  - requestedPath: full requested path set (can include ranges)
 *  - optimizedPath: corresponding optimized path (can include ranges)
 *  - requestTree: path tree for in-flight request, against which to dedupe
 *
 * Returns a 3-tuple consisting of
 *  - the intersection of requested paths with requestTree
 *  - the complement of optimized paths with requestTree
 *  - the complement of corresponding requested paths with requestTree
 *
 * Example scenario:
 *  - requestedPath: ['lolomo', 0, 0, 'tags', { from: 0, to: 2 }]
 *  - optimizedPath: ['videosById', 11, 'tags', { from: 0, to: 2 }]
 *  - requestTree: { videosById: 11: { tags: { 0: null, 1: null }}}
 *
 * This returns:
 * [
 *   [['lolomo', 0, 0, 'tags', 0], ['lolomo', 0, 0, 'tags', 1]],
 *   [['videosById', 11, 'tags', 2]],
 *   [['lolomo', 0, 0, 'tags', 2]]
 * ]
 *
 */
function findPartialIntersections(requestedPath, optimizedPath, requestTree) {
    var depthDiff = requestedPath.length - optimizedPath.length;
    var i;

    // Descend into the request path tree for the optimized-path prefix (when the optimized path is longer than the
    // requested path)
    for (i = 0; requestTree && i < -depthDiff; i++) {
        requestTree = requestTree[optimizedPath[i]];
    }

    // There is no matching path in the request path tree, thus no candidates for deduplication
    if (!requestTree) {
        return [[], [optimizedPath], [requestedPath]];
    }

    if (depthDiff === 0) {
        return recurse(requestedPath, optimizedPath, requestTree, 0, [], []);
    } else if (depthDiff > 0) {
        return recurse(requestedPath, optimizedPath, requestTree, 0, requestedPath.slice(0, depthDiff), []);
    } else {
        return recurse(requestedPath, optimizedPath, requestTree, -depthDiff, [], optimizedPath.slice(0, -depthDiff));
    }
}

function recurse(requestedPath, optimizedPath, currentTree, depth, rCurrentPath, oCurrentPath) {
    var depthDiff = requestedPath.length - optimizedPath.length;
    var intersections = [];
    var rComplementPaths = [];
    var oComplementPaths = [];
    var oPathLen = optimizedPath.length;

    // Loop over the optimized path, looking for deduplication opportunities
    for (; depth < oPathLen; ++depth) {
        var key = optimizedPath[depth];
        var keyType = typeof key;

        if (key && keyType === "object") {
            // If a range key is found, start an inner loop to iterate over all keys in the range, and add
            // intersections and complements from each iteration separately.
            //
            // Range keys branch out this way, providing individual deduping opportunities for each inner key.
            var note = {};
            var innerKey = iterateKeySet(key, note);

            while (!note.done) {
                var nextTree = currentTree[innerKey];
                if (nextTree === undefined) {
                    // If no next sub tree exists for an inner key, it's a dead-end and we can add this to
                    // complement paths
                    oComplementPaths[oComplementPaths.length] = arrayConcatSlice2(
                        oCurrentPath,
                        innerKey,
                        optimizedPath, depth + 1
                    );
                    rComplementPaths[rComplementPaths.length] = arrayConcatSlice2(
                        rCurrentPath,
                        innerKey,
                        requestedPath, depth + 1 + depthDiff
                    );
                } else if (depth === oPathLen - 1) {
                    // Reaching the end of the optimized path means that we found the entire path in the path tree,
                    // so add it to intersections
                    intersections[intersections.length] = arrayConcatElement(rCurrentPath, innerKey);
                } else {
                    // Otherwise keep trying to find further partial deduping opportunities in the remaining path
                    var intersectionData = recurse(
                        requestedPath, optimizedPath,
                        nextTree,
                        depth + 1,
                        arrayConcatElement(rCurrentPath, innerKey),
                        arrayConcatElement(oCurrentPath, innerKey)
                    );

                    Array.prototype.push.apply(intersections, intersectionData[0]);
                    Array.prototype.push.apply(oComplementPaths, intersectionData[1]);
                    Array.prototype.push.apply(rComplementPaths, intersectionData[2]);
                }
                innerKey = iterateKeySet(key, note);
            }

            // The remainder of the path was handled by the recursive call, terminate the loop
            break;
        } else {
            // For simple keys, we don't need to branch out. Loop over `depth` instead of iterating over a range.
            currentTree = currentTree[key];
            oCurrentPath[oCurrentPath.length] = optimizedPath[depth];
            rCurrentPath[rCurrentPath.length] = requestedPath[depth + depthDiff];

            if (currentTree === undefined) {
                // The path was not found in the tree, add this to complements
                oComplementPaths[oComplementPaths.length] = arrayConcatSlice(
                    oCurrentPath, optimizedPath, depth + 1
                );
                rComplementPaths[rComplementPaths.length] = arrayConcatSlice(
                    rCurrentPath, requestedPath, depth + depthDiff + 1
                );

                break;
            } else if (depth === oPathLen - 1) {
                // The end of optimized path was reached, add to intersections
                intersections[intersections.length] = rCurrentPath;
            }
        }
    }

    // Return accumulated intersection and complement paths
    return [intersections, oComplementPaths, rComplementPaths];
}

// Exported for unit testing.
module.exports.__test = { findPartialIntersections: findPartialIntersections };

/**
 * Create a new array consisting of a1 + a subset of a2. Avoids allocating an extra array by calling `slice` on a2.
 */
function arrayConcatSlice(a1, a2, start) {
    var result = a1.slice();
    var l1 = result.length;
    var length = a2.length - start;
    result.length = l1 + length;
    for (var i = 0; i < length; ++i) {
        result[l1 + i] = a2[start + i];
    }
    return result;
}

/**
 * Create a new array consisting of a1 + a2 + a subset of a3. Avoids allocating an extra array by calling `slice` on a3.
 */
function arrayConcatSlice2(a1, a2, a3, start) {
    var result = a1.concat(a2);
    var l1 = result.length;
    var length = a3.length - start;
    result.length = l1 + length;
    for (var i = 0; i < length; ++i) {
        result[l1 + i] = a3[start + i];
    }
    return result;
}

/**
 * Create a new array consistent of a1 plus an additional element. Avoids the unnecessary array allocation when using `a1.concat([element])`.
 */
function arrayConcatElement(a1, element) {
    var result = a1.slice();
    result.push(element);
    return result;
}