jslinq.md

Language-integrated Query syntax for ECMAScript

This is a strawman for an advanced generator-comprehension syntax for ECMAScript based in the LINQ syntax. The syntax allows for custom semantics for evaluation, as each clause in a query is translated into regular function calls for special symbol-named methods that are evaluated if found on the sequence (see Abstract Operations for more information).

Examples

const q = from user of users
          where user.role === "guest"
          select user;

for (const user of q) {
    ...
}

Proof-of-concept

You can see a proof-of-concept of this syntax using tagged templates at https://github.com/rbuckton/iterable-query-linq.

Definitions

• Query – One or more Ranges defined using integrated query syntax that produce a resulting Sequence.
• Sequence – A value that is either an Iterable (i.e. having an @@iterator method), or an AsyncIterable (i.e. having an @@asyncIterator method).
• Outer sequence – The sequence produced by the Range for any preceeding query body clauses.
• Inner sequence – A related sequence produced by the current query body clause.
• Range – The sequence and any related range variables bound to the sequence.
  • A Range begins with a from, join, join into, or into clause and ends at the next group or select clause.
  • The first Range in a QueryExpression must begin with a from clause.
  • A Range is the lexical scope for a range variable.
  • A Range is has the following internal slots:
    • [[Source]] – The underlying Sequence for the Range.
    • [[Bindings]] – The bound names for any Range Variables in scope within the Range.
    • [[Async]] – A boolean value indicating whether the Range is asynchronous (i.e. contains a from or join clause with an await modifier).
• Range Variable – A variable binding that is lexically scoped to the current Range.
  • The value for a Range Variable will be based on the per-iteration value of the Range.
  • A Range Variable may be a BindingIdentifier, ObjectBindingPattern, or ArrayBindingPattern.
• Grouping – An Object that has an @@grouping method (see CreateGrouping).
  • When called, the @@grouping method should return an object with the following properties:
    • key – The key for the current group of results.
    • values – An Iterable containing the values in the group.
  • For convenience, a runtime-generated Grouping will define the following properties:
    • key – The key for the current group of results.
    • values – An Iterable containing the values in the group.
    • @@grouping – A method that returns this.
    • @@iterator – A method that returns this.values[@@iterator]().

Syntax

A Query starts with a from clause, consists of zero or more query body clauses, and ends with either a select or group clause.

from clause

The from clause begins a QueryExpression, binding a range variable that refers to each element of a sequence:

from x of y ...

• Introduces a range variable (x) over an Iterable (y).
• When evaluated, the runtime will execute the QuerySelect abstract operation with the following arguments:
  • outer – The sequence (y).
  • selector – A runtime-generated function that evaluates and introduces the new range variable (i.e. (x) => ({ x })).
  • async – A value indicating whether the await modifier was present (see Asynchronous Ranges, below).

Asynchronous Ranges

A from clause may also bind a range variable over an AsyncIterable by applying the await modifier, similar to for await of. Unlike for await of, the await modifier supported outside of an async function.

from await x of y ...

If any from clause in a Range includes the await keyword, the entire Range is converted into an AsyncIterable.

Cartesian Joins

Subsequent from clauses result in a cartesian-join:

... from x of y ...

• Introduces a new range variable (x) over an inner sequence (y).
• The resulting Range is a cartesian-join of the outer sequence and the inner sequence.
• When evaluated, the runtime will execute the QuerySelectMany abstract operation with the following arguments:
  • outer – The outer sequence.
  • projection – A runtime-generated function that evaluates and returns the inner sequence (y) for each element (a) of the outer sequence (i.e. ({ a }) => y).
  • resultSelector – A runtime-generated function that binds the range variables of both the outer sequence (a) and inner sequence (x) (i.e. ({ a }, x) => ({ a, x })).
  • async – A value indicating whether the await modifier was present in this Range or any outer Range (see Asynchronous Ranges, below).
• Cartesian Joins may also use the await modifier.

join clause

The join clause is used to define a one-to-one relationship between the elements of two Iterables. All joins are performed using an "equijoin", comparing the the keys selected from the outer sequence and inner sequence using the SameValueZero abstract operation:

... join x of y on a.key equals x.key ...

• Introduces a new range variable x over an inner sequence y.
• The resulting Range is an inner-join of the outer sequence and the inner sequence.
• When evaluated, the runtime will execute the QueryJoin abstract operation with the following arugments:
  • outer – The outer sequence.
  • inner – The inner sequence (i.e. y)
  • outerKeySelector – A runtime-generated function that selects the key for the outer sequence (i.e. ({ a }) => a.key)
  • innerKeySelector – A runtime-generated function that selects the key for the inner sequence (i.e. (x) => x.key)
  • resultSelector – A runtime-generated function that binds the range variables (a) of the preceeding Range and the new range variable (x) of the join clause (i.e. ({ a }, x) => ({ a, x })).
  • async – A value indicating whether the await modifier was present in this Range or any outer Range (see Asynchronous Ranges, below).
• The join clause also supports the await modifier: ... join await x of y ...

join into clause

The join into clause is used to define a one-to-many relationship between the elements of two Iterables. All joins are performed using an "equijoin", comparing the the keys selected from the outer sequence and inner sequence using the SameValueZero abstract operation:

... join x of y on a.key equals x.key into z ...

• Introduces a new range variable (x) over an inner sequence (y) that is scoped only to the join clause itself.
• Introduces a new range variable (z) containing elements of the inner sequence related to each element of the outer sequence.
• The resulting Range is a left-join of the outer sequence and the inner sequence.
• When evaluated, the runtime will execute the QueryGroupJoin abstract operation with the following arugments:
  • outer – The outer sequence.
  • inner – The inner sequence (i.e. y)
  • outerKeySelector - A runtime-generated function that selects the key for the outer sequence (i.e. ({ a }) => a.key)
  • innerKeySelector - A runtime-generated function that selects the key for the inner sequence (i.e. (x) => x.key)
  • resultSelector - A runtime-generated function that binds the range variables (a) of the preceeding Range and the new range variable (z) of the join into clause (i.e. ({ a }, z) => ({ a, z })).
  • async – A value indicating whether the await modifier was present in this Range or any outer Range (see Asynchronous Ranges, below).
• The join into clause also supports the await modifier: ... join await x of y ... into z ...

let clause

The let clause introduces a new range variable into the current Range:

... let x = a.y ...

• Introduces a new range variable (x) over the outer sequence.
• The resulting Range combines the range variables of the preceeding range with the new range variable.
• When evaluated, the runtime will execute the QuerySelect abstract operation with the following arguments:
  • outer – The outer sequence.
  • selector – A runtime-generated function that binds the range variables (a) of the preceeding Range and the new range variable (x) of the let clause (i.e. ({ a }) => ({ a, x: a.y })).
  • async – A value indicating whether the await modifier was present in the outer Range (see Asynchronous Ranges, below).

where clause

The where clause filters the current Range, skipping items that do not match the supplied criteria:

... where a.id === 1 ...

• When evaluated, the runtime will execute the QueryWhere abstract operation with the following arguments:
  • outer – The outer sequence.
  • predicate – A runtime-generated function that evaluates the filter expression against the range variables of the current range (i.e. ({ a }) => a.id === 1).
  • async – A value indicating whether the await modifier was present in the outer Range (see Asynchronous Ranges, below).

orderby clause

The orderby clause is used to sort the preceeding Range:

... orderby a.lastName, a.age descending ...

• Composed of one or more comma-separated comparators.
• A comparator is a selector expression followed by either the ascending (optional) or descending keyword.
• When the first comparator is evaluated, the runtime will execute the QueryOrderBy abstract operation with the following arguments:
  • outer – The outer sequence.
  • keySelector – A runtime-generated function that selects the expression to use as the sort key (i.e. ({ a }) => a.lastName).
  • descending – true if the descending keyword was present.
  • async – A value indicating whether the await modifier was present in the outer Range (see Asynchronous Ranges, below).
• When each remaining comparator is evaluated, the runtime will execute the QueryThenBy abstract operation with the following arguments:
  • outer – The sequence produced by the previous comparator.
  • keySelector – A runtime-generated function that selects the expression to use as the sort key (i.e. ({ a }) => a.lastName).
  • descending – true if the descending keyword was present.
  • async – A value indicating whether the await modifier was present in the outer Range (see Asynchronous Ranges, below).

group clause

The group clause is used to group elements of the preceeding Range by a specific key:

... group a.firstName by a.lastName

• Groups the elements of the outer sequence by the provided key selector (x.lastName).
• Each element in the group is mapped using the provided element selector (x.firstName).
• Keys are compared using the SameValueZero abstract operation.
• The final result is a sequence of Groupings.
• A group clause can end a Query.
• A group clause may start a new Query by appending an into clause (see below).
• When evaluated, the runtime will execute the QueryGroupBy abstract operation with the following arguments:
  • outer – The outer sequence.
  • keySelector – A runtime-generated function that selects the key used to group the results (i.e. ({ a }) => a.lastName).
  • elementSelector – A runtime-generated function that selects the value for each element in the group (i.e. ({ a }) => a.firstName).
  • async – A value indicating whether the await modifier was present in the outer Range (see Asynchronous Ranges, below).

select clause

The select clause is used to select the results for each element of the preceeding Range:

... select a.fullName

• Selects the elements of the outer sequence by the provided selector (x.fullName).
• The final result is a sequence of elements produced by the selector.
• A select clause can end a Query.
• A select clause may start a new Query by appending an into clause (see below).
• When evaluated, the runtime will execute the QuerySelect abstract operation with the following arguments:
  • outer – The outer sequence.
  • selector – A runtime-generated function that selects the value for each element in the outer sequence (i.e. ({ a }) => a.fullName).
  • async – A value indicating whether the await modifier was present in the outer Range (see Asynchronous Ranges, below).

into clause

An into clause may follow a select or group clause to start a new top-level Range using the elements of the outer sequence bound to a fresh range variable:

... group x by x.role into y ...
... select x.fullName into y ...

• Introduces a new range variable (y) over the outer sequence.

Abstract Operations

The following are rough outlines of the abstract operations mentioned above.

QuerySelect

TODO: Detailed algorithm steps.

// approximate algorithm
function QuerySelect(outer, selector, async) {
    if (async) {
        const selectAsync = outer[@@selectAsync];
        if (selectAsync) return selectAsync.call(outer, selector);
        return {
            async * [@@asyncIterator]() {
                for await (const outerElement of outer) {
                    yield selector(outerElement);
                }
            }
        };
    }
    else {
        const select = outer[@@select];
        if (select) return select.call(outer, selector);
        return {
            * [@@iterator]() {
                for (const outerElement of outer) {
                    yield selector(outerElement);
                }
            }
        };
    }
}

QuerySelectMany

TODO: Detailed algorithm steps.

// approximate algorithm
function QuerySelectMany(outer, projection, resultSelector, async) {
    if (async) {
        const selectManyAsync = outer[@@selectManyAsync];
        if (selectManyAsync) return selectManyAsync.call(outer, projection, resultSelector);
        return {
            async * [@@asyncIterator]() {
                for await (const outerElement of outer) {
                    const inner = projection(outerElement);
                    for (await const innerElement of inner) {
                        yield resultSelector(outerElement, innerElement);
                    }
                }
            }
        };
    }
    else {
        const selectMany = outer[@@selectMany];
        if (selectMany) return selectMany.call(outer, projection);
        return {
            * [@@iterator]() {
                for (const outerElement of outer) {
                    const inner = projection(outerElement);
                    for (const innerElement of inner) {
                        yield resultSelector(outerElement, innerElement);
                    }
                }
            }
        };
    }
}

QueryJoin

TODO: Detailed algorithm steps.

// approximate algorithm
function QueryJoin(outer, inner, outerKeySelector, innerKeySelector, resultSelector, async) {
    if (async) {
        const joinAsync = outer[@@joinAsync];
        if (joinAsync) return joinAsync.call(outer, inner, outerKeySelector, innerKeySelector, resultSelector);
        return {
            async * [@@asyncIterator]() {
                const groupings = await CreateGroupingsAsync(inner, innerKeySelector, _ => _);
                for await (const outerElement of outer) {
                    const outerKey = outerKeySelector(outerElement);
                    if (groupings.has(outerKey)) {
                        const innerElements = groupings.get(outerKey);
                        for (const innerElement of innerElements) {
                            yield resultSelector(outerElement, innerElement);
                        }
                    }
                }
            }
        };
    }
    else {
        const join = outer[@@join];
        if (join) return join.call(outer, inner, outerKeySelector, innerKeySelector, resultSelector);
        return {
            * [@@iterator]() {
                const groupings = CreateGroupings(inner, innerKeySelector, _ => _);
                for (const outerElement of outer) {
                    const outerKey = outerKeySelector(outerElement);
                    if (groupings.has(outerKey)) {
                        const innerElements = groupings.get(outerKey);
                        for (const innerElement of innerElements) {
                            yield resultSelector(outerElement, innerElement);
                        }
                    }
                }
            }
        };
    }
}

QueryGroupJoin

TODO: Detailed algorithm steps.

// approximate algorithm
function QueryGroupJoin(outer, inner, outerKeySelector, innerKeySelector, resultSelector, async) {
    if (async) {
        const joinAsync = outer[@@joinAsync];
        if (joinAsync) return joinAsync.call(outer, inner, outerKeySelector, innerKeySelector, resultSelector);
        return {
            async * [@@asyncIterator]() {
                const groupings = await CreateGroupingsAsync(inner, innerKeySelector, _ => _);
                for await (const outerElement of outer) {
                    const outerKey = outerKeySelector(outerElement);
                    if (groupings.has(outerKey)) {
                        const innerElements = groupings.get(outerKey);
                        yield resultSelector(outerElement, innerElements);
                    }
                }
            }
        };
    }
    else {
        const join = outer[@@join];
        if (join) return join.call(outer, inner, outerKeySelector, innerKeySelector, resultSelector);
        return {
            * [@@iterator]() {
                const groupings = CreateGroupings(inner, innerKeySelector, _ => _);
                for (const outerElement of outer) {
                    const outerKey = outerKeySelector(outerElement);
                    if (groupings.has(outerKey)) {
                        const innerElements = groupings.get(outerKey);
                        yield resultSelector(outerElement, innerElement);
                    }
                }
            }
        };
    }
}

QueryWhere

TODO: Detailed algorithm steps.

// approximate algorithm
function QueryWhere(outer, predicate, async) {
    if (async) {
        const whereAsync = outer[@@whereAsync];
        if (whereAsync) return whereAsync.call(outer, predicate);
        return {
            async * [@@asyncIterator]() {
                for await (const outerElement of outer) {
                    if (predicate(outerElement)) {
                        yield outerElement;
                    }
                }
            }
        };
    }
    else {
        const where = outer[@@where];
        if (where) return where.call(outer, predicate);
        return {
            * [@@iterator]() {
                for (const outerElement of outer) {
                    if (predicate(outerElement)) {
                        yield outerElement;
                    }
                }
            }
        };
    }
}

QueryOrderBy

TODO: Detailed algorithm steps.

// approximate algorithm
function QueryOrderBy(outer, keySelector, descending, async) {
    if (async) {
        const orderByAsync = outer[@@orderByAsync];
        if (orderByAsync) return orderByAsync.call(outer, keySelector, descending);
        return CreateAsyncOrderByIterable(outer, keySelector, descending, undefined);
    }
    else {
        const orderBy = outer[@@orderBy];
        if (orderBy) return orderBy.call(outer, keySelector, descending);
        return CreateOrderByIterable(outer, keySelector, descending, undefined);
    }
}

function CreateAsyncOrderByIterable(outer, keySelector, descending, parent) {
    const orderByInfo = { keySelector, descending, parent };
    return {
        [@@thenByAsync](keySelector, descending) {
            return CreateAsyncOrderByIterable(outer, keySelector, descending, orderByInfo);
        },
        async * [@@asyncIterator]() {
            let outerElements;
            for (await outerElement of outer) {
                if (outerElements === undefined) {
                    outerElements = [outerElement];
                }
                else {
                    outerElements.push(outerElement);
                }
            }
            const sorter = CreateSorter(outerElements, orderByInfo);
            const length = outerElements.length;
            const indices = Array(length);
            for (let i = 0; i < length; i++) {
                indices[i] = i;
            }
            indices.sort(sorter);
            for (const index of indices) {
                yield outerElements[index];
            }
        }
    };
}

function CreateOrderByIterable(outer, keySelector, descending, parent) {
    const orderByInfo = { keySelector, descending, parent };
    return {
        [@@thenBy](keySelector, descending) {
            return CreateOrderByIterable(outer, keySelector, descending, orderByInfo);
        },
        * [@@iterator]() {
            const outerElements = Array.from(outer);
            const sorter = CreateSorter(outerElements, orderByInfo);
            const length = outerElements.length;
            const indices = Array(length);
            for (let i = 0; i < length; i++) {
                indices[i] = i;
            }
            indices.sort(sorter);
            for (const index of indices) {
                yield outerElements[index];
            }
        }
    };
}

function CreateSorter(elements, { keySelector, descending, parent }, nextSorter) {
    const keys = elements.map(keySelector);
    const sorter = (a, b) => {
        const result = CompareValues(keys[a], keys[b]);
        if (result === 0) {
            if (nextSorter) return nextSorter(a, b);
            return a - b;
        }
        if (descending) return -result;
        return result;
    };
    if (parent) return CreateSorter(elements, parent, sorter);
    return sorter;
}

QueryThenBy

TODO: Detailed algorithm steps.

// approximate algorithm
function QueryThenBy(outer, keySelector, descending, async) {
    if (async) {
        const thenByAsync = outer[@@thenByAsync];
        if (thenByAsync) return thenByAsync.call(outer, keySelector, descending);
    }
    else {
        const thenBy = outer[@@thenBy];
        if (thenBy) return thenBy.call(outer, keySelector, descending);
    }
    throw new TypeError();
}

QueryGroupBy

TODO: Detailed algorithm steps.

// approximate algorithm
function QueryGroupBy(outer, keySelector, elementSelector, async) {
    if (async) {
        const groupByAsync = outer[@@groupByAsync];
        if (groupByAsync) return groupByAsync.call(outer, keySelector, elementSelector);
        return {
            async * [@@asyncIterator]() {
                const groupings = await CreateGroupingsAsync(outer, keySelector, elementSelector);
                for (const [key, values] of groupings) {
                    yield CreateGrouping(key, values);
                }
            }
        };
    }
    else {
        const groupBy = outer[@@groupBy];
        if (groupBy) return groupBy.call(outer, keySelector, elementSelector);
        return {
            * [@@iterator]() {
                const groupings = CreateGroupings(outer, keySelector, elementSelector);
                for (const [key, values] of groupings) {
                    yield CreateGrouping(key, values);
                }
            }
        };
    }
}

function CreateGrouping(key, values) {
    return {
        key,
        values,
        [@@grouping]() {
            return this;
        },
        * [@@iterator]() {
            yield* values;
        }
    };
}

CreateGroupings

TODO: Detailed algorithm steps.

// approximate algorithm
function CreateGroupings(sequence, keySelector, elementSelector) {
    const groupings = new Map();
    for (const item of sequence) {
        const key = keySelector(item);
        const element = elementSelector(item);
        if (groupings.has(key)) {
            groupings.get(key).push(element);
        }
        else {
            groupings.set(key, [element]);
        }
    }
    return groupings;
}

CreateGroupingsAsync

TODO: Detailed algorithm steps.

// approximate algorithm
async function CreateGroupingsAsync(sequence, keySelector, elementSelector) {
    const groupings = new Map();
    for await (const item of sequence) {
        const key = keySelector(item);
        const element = elementSelector(item);
        if (groupings.has(key)) {
            groupings.get(key).push(element);
        }
        else {
            groupings.set(key, [element]);
        }
    }
    return groupings;
}

Syntax

QueryExpression :
    FromClause QueryBody

QueryBody :
    QueryBodyClauses? SelectOrGroupClause QueryContinuation?

QueryBodyClauses :
    QueryBodyClause
    QueryBodyClauses QueryBodyClause

QueryBodyClause :
    FromClause
    JoinClause
    LetClause
    WhereClause
    OrderbyClause

SelectOrGroupClause :
    SelectClause
    GroupClause

RangeBinding :
    BindingIdentifier[~Yield, ~Await]
    BindingPattern[~Yield, ~Await]

QueryContinuation :
    `into` RangeBinding QueryBody

FromClause :
    `from` `await`? RangeBinding `of` AssignmentExpression[+In, ~Yield, ~Await]
    CoverElementAccessExpressionAndQueryExpressionHead[~Yield, ~Await] `of` AssignmentExpression[+In, ~Yield, +Await]

JoinClause :
    `join` `await`? RangeBinding `of` AssignmentExpression[+In, ~Yield, ~Await] `on` AssignmentExpression[+In, ~Yield, ~Await] `equals` AssignmentExpression[+In, ~Yield, ~Await]
    `join` `await`? RangeBinding `of` AssignmentExpression[+In, ~Yield, ~Await] `on` AssignmentExpression[+In, ~Yield, ~Await] `equals` AssignmentExpression[+In, ~Yield, ~Await] `into` RangeBinding

LetClause :
    `let` RangeBinding `=` AssignmentExpression[+In, ~Yield, ~Await]

WhereClause :
    `where` AssignmentExpression[+In, ~Yield, ~Await]

OrderbyClause :
    `orderby` OrderbyComparatorList

OrderbyComparatorList :
    OrderbyComparator
    OrderbyComparatorList `,` OrderbyComparator

OrderbyComparator :
    AssignmentExpression[+In, ~Yield, ~Await] `ascending`?
    AssignmentExpression[+In, ~Yield, ~Await] `descending`

GroupClause :
    `group` AssignmentExpression[+In, ~Yield, ~Await] `by` AssignmentExpression[+In, ~Yield, ~Await]

SelectClause :
    `select` AssignmentExpression[+In, ~Yield, ~Await]

CoverElementAccessExpressionAndQueryExpressionHead[Yield, Await] :
    MemberExpression[?Yield, ?Await] ArrayLiteral[?Yield, ?Await]
    MemberExpression[?Yield, ?Await] [no LineTerminator here] ObjectBindingPattern[~Yield, ~Await]
    MemberExpression[?Yield, ?Await] [no LineTerminator here] BindingIdentifier[~Yield, ~Await]
    MemberExpression[?Yield, ?Await] [no LineTerminator here] `await` RangeBinding

MemberExpression[Yield, Await] :
    <del>MemberExpression[?Yield, ?Await] `[` Expression[+In, ?Yield, ?Await] `]`</del>
    <ins>CoverElementAccessExpressionAndQueryExpressionHead[?Yield, ?Await]</ins>

AssignmentExpression[In, Yield, Await] :
    <ins>QueryExpression</ins>

When processing an instance of the production MemberExpression : CoverElementAccessExpressionAndQueryExpressionHead, the interpretation of CoverElementAccessExpressionAndQueryExpressionHead is refined using the following grammar:

MemberExpression[Yield, Await] :
    MemberExpression[?Yield, ?Await] `[` Expression[+In, ?Yield, ?Await] `]`

When processing an instance of the production FromClause : CoverElementAccessExpressionAndQueryExpressionHead `of` AssignmentExpression, the interpretation of CoverElementAccessExpressionAndQueryExpressionHead is refined using the following grammar:

QueryExpressionHead :
    `from` `await`? RangeBinding