stanford-oval / thingtalk / 990

pending completion

Build # 990

Build Type

Pull #240

travis-ci-com

Committed by

web-flow

Commit Message

Merge 7de4b6224 into 5e815cadb

Pull Request Pull Request #240: Fix normalization of nested compute tables

Run Details

4359 of 5797 branches covered (75.19%)

Branch coverage included in aggregate %.

28 of 31 new or added lines in 1 file covered. (90.32%)

1 existing line in 1 file now uncovered.

8555 of 10236 relevant lines covered (83.58%)

1565.3 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

78.45

/lib/optimize.js

// -*- mode: js; indent-tabs-mode: nil; js-basic-offset: 4 -*-
//
// This file is part of ThingTalk
//
// Copyright 2017-2020 The Board of Trustees of the Leland Stanford Junior University
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
//    http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.
//
// Author: Giovanni Campagna <gcampagn@cs.stanford.edu>
"use strict";

const assert = require('assert');
const Ast = require('./ast');

const { isUnaryStreamToStreamOp,
        isUnaryTableToTableOp,
        getScalarExpressionName } = require('./utils');

function flattenAnd(expr) {
    let flattened = [];
    if (expr.isAnd) {
        for (let op of expr.operands) {
            let operands = flattenAnd(op);
            operands.forEach((op) => assert(op instanceof Ast.BooleanExpression));
            for (let subop of operands)
                flattened.push(subop);
        }
    } else {
        flattened.push(expr);
    }
    return flattened;
}

function flattenOr(expr) {
    let flattened = [];
    if (expr.isOr) {
        for (let op of expr.operands) {
            let operands = flattenOr(op);
            operands.forEach((op) => assert(op instanceof Ast.BooleanExpression));
            for (let subop of operands)
                flattened.push(subop);
        }
    } else {
        flattened.push(expr);
    }
    return flattened;
}

function optimizeFilter(expr) {
    if (expr.isTrue || expr.isFalse || expr.isDontCare)
        return expr;
    if (expr.isAnd) {
        let operands = flattenAnd(expr).map((o) => optimizeFilter(o)).filter((o) => !o.isTrue);
        operands.forEach((op) => assert(op instanceof Ast.BooleanExpression));
        for (let o of operands) {
            if (o.isFalse)
                return Ast.BooleanExpression.False;
        }
        if (operands.length === 0)
            return Ast.BooleanExpression.True;
        if (operands.length === 1)
            return operands[0];
        return new Ast.BooleanExpression.And(expr.location, operands);
    }
    if (expr.isOr) {
        let operands = flattenOr(expr).map((o) => optimizeFilter(o)).filter((o) => !o.isFalse);
        operands.forEach((op) => assert(op instanceof Ast.BooleanExpression));
        for (let o of operands) {
            if (o.isTrue)
                return Ast.BooleanExpression.True;
        }
        if (operands.length === 0)
            return Ast.BooleanExpression.False;
        if (operands.length === 1)
            return operands[0];

        // convert "x == foo || x == bar" to "x in_array [foo, bar]"
        // and "x =~ foo || x =~ bar" to "x in_array~ [foo, bar]"
        let equalityFilters = {};
        let likeFilters = {};
        let otherFilters = [];
        for (let operand of operands) {
            if (operand.isAtom) {
                if (operand.operator === '==') {
                    if (operand.name in equalityFilters)
                        equalityFilters[operand.name].push(operand.value);
                    else
                        equalityFilters[operand.name] = [operand.value];
                } else if (operand.operator === '=~') {
                    if (operand.name in likeFilters)
                        likeFilters[operand.name].push(operand.value);
                    else
                        likeFilters[operand.name] = [operand.value];
                } else {
                    otherFilters.push(operand);
                }
            } else {
                otherFilters.push(operand);
            }
        }
        for (let eqParam in equalityFilters) {
            if (equalityFilters[eqParam].length > 1) {
                otherFilters.push(new Ast.BooleanExpression.Atom(expr.location, eqParam, 'in_array',
                    new Ast.Value.Array(equalityFilters[eqParam])));
            } else {
                otherFilters.push(new Ast.BooleanExpression.Atom(expr.location, eqParam, '==', equalityFilters[eqParam][0]));
            }
        }
        for (let eqParam in likeFilters) {
            if (likeFilters[eqParam].length > 1) {
                otherFilters.push(new Ast.BooleanExpression.Atom(expr.location, eqParam, 'in_array~',
                    new Ast.Value.Array(likeFilters[eqParam])));
            } else {
                otherFilters.push(new Ast.BooleanExpression.Atom(expr.location, eqParam, '=~', likeFilters[eqParam][0]));
            }
        }

        return new Ast.BooleanExpression.Or(expr.location, otherFilters);
    }
    if (expr.isNot) {
        if (expr.expr.isNot) // double negation
            return optimizeFilter(expr.expr.expr);

        let subexpr = optimizeFilter(expr.expr);
        if (subexpr.isTrue)
            return Ast.BooleanExpression.False;
        if (subexpr.isFalse)
            return Ast.BooleanExpression.True;
        return new Ast.BooleanExpression.Not(expr.location, subexpr);
    }
    if (expr.isExternal) {
        let subfilter = optimizeFilter(expr.filter);
        if (subfilter.isFalse)
            return new Ast.BooleanExpression.False;
        // NOTE: it does not hold that if subfilter is True
        // the whole expression is true, because the invocation
        // might return no results!
        return new Ast.BooleanExpression.External(expr.location, expr.selector,
            expr.channel, expr.in_params, subfilter, expr.schema);
    }
    if (expr.isCompute) {
        // TODO
        return expr;
    }
    if (expr.isVarRef) {
        // TODO
        return expr;
    }

    let lhs = expr.name;
    let rhs = expr.value;
    let op = expr.operator;
    if (rhs.isVarRef && rhs.name === lhs) {
        // x = x , x =~ x , x >= x, x <= x
        if (op === '==' || op === '=~' || op === '>=' || op === '<=')
            return Ast.BooleanExpression.True;
    }
    return expr;
}

function optimizeStream(stream, allow_projection=true) {
    if (stream.isVarRef || stream.isTimer || stream.isAtTimer)
        return stream;

    if (stream.isProjection) {
        if (!allow_projection)
            return optimizeStream(stream.stream, allow_projection);

        const optimized = optimizeStream(stream.stream, allow_projection);
        if (!optimized)
            return null;

        // collapse projection of projection
        if (optimized.isProjection) {
            return new Ast.Stream.Projection(stream.location, optimized.stream,
                stream.args, stream.schema);
        }
        return new Ast.Stream.Projection(stream.location, optimized, stream.args, stream.schema);
    }

    if (stream.isMonitor) {
        // always allow projection inside a monitor, because the projection affects which parameters we monitor
        let table = optimizeTable(stream.table, true);
        if (!table)
            return null;

        // convert monitor of a projection to a projection of a monitor
        if (table.isProjection) {
            const newMonitor = new Ast.Stream.Monitor(table.location, table.table, stream.args || table.args, stream.schema);

            if (allow_projection)
                return new Ast.Stream.Projection(table.location, newMonitor, table.args, stream.schema);
            else
                return newMonitor;
        }

        stream.table = table;
        return stream;
    }

    if (stream.isFilter) {
        stream.filter = optimizeFilter(stream.filter);
        // handle constant filters
        if (stream.filter.isTrue)
            return optimizeStream(stream.stream, allow_projection);
        if (stream.filter.isFalse)
            return null;
        // compress filter of filter
        if (stream.stream.isFilter) {
            stream.filter = optimizeFilter(Ast.BooleanExpression.And([stream.filter, stream.stream.filter]));
            stream.stream = stream.stream.stream;
            return optimizeStream(stream, allow_projection);
        }

        // switch filter of monitor to monitor of filter
        if (stream.stream.isMonitor) {
            let newstream = new Ast.Stream.Monitor(
                stream.location,
                new Ast.Table.Filter(stream.location, stream.stream.table, stream.filter, stream.stream.table.schema),
                stream.stream.args,
                stream.stream.schema
            );
            return optimizeStream(newstream, allow_projection);
        }

        // switch filter of project to project of filter
        if (stream.stream.isProjection) {
            if (allow_projection) {
                return optimizeStream(new Ast.Stream.Projection(
                    stream.location,
                    new Ast.Stream.Filter(stream.location,
                        stream.stream.stream, stream.filter, stream.stream.stream.schema),
                    stream.stream.args,
                    stream.stream.schema
                ), allow_projection);
            } else {
                return optimizeStream(new Ast.Stream.Filter(
                    stream.location,
                    stream.stream.stream,
                    stream.filter,
                    stream.stream.stream.schema
                ), allow_projection);
            }
        }
    } else if (stream.isEdgeNew) {
        // collapse edge new of monitor or edge new of edge new
        if (stream.stream.isMonitor || stream.stream.isEdgeNew)
            return optimizeStream(stream.stream, allow_projection);
    } else if (stream.isEdgeFilter) {
        stream.filter = optimizeFilter(stream.filter);
        // handle constant filters
        // we don't optimize the isTrue case here: "edge on true" means only once
        if (stream.filter.isFalse)
            return null;
    }

    if (isUnaryStreamToStreamOp(stream)) {
        let inner = optimizeStream(stream.stream, allow_projection);
        if (!inner)
            return null;
        stream.stream = inner;
        return stream;
    }

    if (stream.isJoin) {
        let lhs = optimizeStream(stream.stream, allow_projection);
        if (!lhs)
            return null;
        let rhs = optimizeTable(stream.table, allow_projection);
        if (!rhs)
            return null;
        stream.stream = lhs;
        stream.table = rhs;
        return stream;
    }

    return stream;
}

function findComputeTable(table) {
    if (table.isCompute)
        return table;
    if (table.isInvocation || table.isVarRef)
        return null;

    // do not traverse joins or aliases, as those
    // change the meaning of parameters and therefore the expressions
    if (table.isJoin || table.isAlias)
        return null;

    if (isUnaryTableToTableOp(table))
        return findComputeTable(table.table);

    throw new TypeError(table.constructor.name);
}

function expressionUsesParam(expr, pname) {
    let used = false;
    expr.visit(new class extends Ast.NodeVisitor {
        visitVarRefValue(value) {
            used = used || value.name === pname;
            return true;
        }
    });
    return used;
}

function optimizeTable(table, allow_projection=true) {
    if (table.isVarRef || table.isInvocation)
        return table;

    if (table.isProjection) {
        if (!allow_projection)
            return optimizeTable(table.table);
        if (table.table.isAggregation)
            return optimizeTable(table.table);

        const optimized = optimizeTable(table.table, allow_projection);
        if (!optimized)
            return null;

        // collapse projection of projection
        if (optimized.isProjection)
            return new Ast.Table.Projection(table.location, optimized.table, table.args, table.schema);
        return new Ast.Table.Projection(table.location, optimized, table.args, table.schema);
    }

    if (table.isCompute) {
        if (table.expression.isVarRef) // entirely redundant
            return optimizeTable(table.table);

        // look for a nested compute table and find one that has the same
        // expression (note that joins and aliases stop the traversal)
        // if so, we remove this compute expression entirely
        let inner = findComputeTable(table.table);
        while (inner) {
            // check that our expression doesn't depend on the result of the computation
            // (if it does, the computation is not redundant)
            const innerOutputName = inner.alias || getScalarExpressionName(inner.expression);

            if (expressionUsesParam(table.expression, innerOutputName))
                break;

            // check that our expression is equal to the inner expression,
            if (inner.expression.equals(table.expression)) {
                // yep, found it!
                return optimizeTable(table.table);
            }

            // try going deeper
            inner = findComputeTable(inner.table);
        }

        // nope, no optimization here
        inner = optimizeTable(table.table, allow_projection);
        if (!inner)
            return null;
        table.table = inner;
        return table;
    }

    if (table.isFilter) {
        table.filter = optimizeFilter(table.filter);
        // handle constant filters
        if (table.filter.isTrue)
            return optimizeTable(table.table, allow_projection);
        if (table.filter.isFalse)
            return null;
        // compress filter of filter
        if (table.table.isFilter) {
            table.filter = optimizeFilter(new Ast.BooleanExpression.And(table.filter.location,
                [table.filter, table.table.filter]));
            table.table = table.table.table;
            return optimizeTable(table, allow_projection);
        }

        // switch filter of project to project of filter
        if (table.table.isProjection) {
            if (allow_projection) {
                return new Ast.Table.Projection(
                    table.location,
                    optimizeTable(new Ast.Table.Filter(
                        table.table.location,
                        table.table.table,
                        table.filter,
                        table.table.table.schema),
                    allow_projection),
                    table.table.args,
                    table.table.schema
                );
            } else {
                return optimizeTable(new Ast.Table.Filter(
                    table.location,
                    table.table.table,
                    table.filter,
                    table.table.table.schema
                ), allow_projection);
            }
        }
    }

    if (table.isIndex && table.indices.length === 1 && table.indices[0].isArray)
        table.indices = table.indices[0].value;

    // turn a slice with a constant limit of 1 to an index
    if (table.isSlice && table.limit.isNumber && table.limit.value === 1)
        return optimizeTable(new Ast.Table.Index(table.location, table.table, [table.base], table.table.schema), allow_projection);

    if (isUnaryTableToTableOp(table)) {
        let inner = optimizeTable(table.table, allow_projection);
        if (!inner)
            return null;
        table.table = inner;
        return table;
    }
    if (table.isJoin) {
        let lhs = optimizeTable(table.lhs, allow_projection);
        if (!lhs)
            return null;
        let rhs = optimizeTable(table.rhs, allow_projection);
        if (!rhs)
            return null;
        table.lhs = lhs;
        table.rhs = rhs;
        return table;
    }

    return table;
}

function optimizeRule(rule) {
    let allow_projection = false;
    // projectino is only allowed when the actions include notify/return
    if (rule.actions.some((a) => a.isNotify))
        allow_projection = true;
    if (rule.stream) {
        rule.stream = optimizeStream(rule.stream, allow_projection);
        if (!rule.stream)
            return null;
    } else if (rule.table) {
        rule.table = optimizeTable(rule.table, allow_projection);
        if (!rule.table)
            return null;
    }
    if (!rule.actions.length)
        return null;
    return rule;
}

function optimizeProgram(program) {
    let rules = [];
    program.rules.forEach((rule) => {
        if (rule.isAssignment) {
            rules.push(rule);
        } else {
            let newrule = optimizeRule(rule);
            if (newrule)
                rules.push(newrule);
        }
    });
    program.rules = rules;
    if (program.rules.length === 0 && program.declarations.length === 0 && Object.keys(program.classes).length === 0 && program.oninputs.length === 0)
        return null;
    else
        return program;
}

module.exports = {
    optimizeRule,
    optimizeProgram,
    optimizeFilter
};

1	// -- mode: js; indent-tabs-mode: nil; js-basic-offset: 4 --
2	//
3	// This file is part of ThingTalk
4	//
5	// Copyright 2017-2020 The Board of Trustees of the Leland Stanford Junior University
6	//
7	// Licensed under the Apache License, Version 2.0 (the "License");
8	// you may not use this file except in compliance with the License.
9	// You may obtain a copy of the License at
10	//
11	// http://www.apache.org/licenses/LICENSE-2.0
12	//
13	// Unless required by applicable law or agreed to in writing, software
14	// distributed under the License is distributed on an "AS IS" BASIS,
15	// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
16	// See the License for the specific language governing permissions and
17	// limitations under the License.
18	//
19	// Author: Giovanni Campagna <gcampagn@cs.stanford.edu>
20	"use strict";
21
22	const assert = require('assert');	2✔
23	const Ast = require('./ast');	2✔
24
25	const { isUnaryStreamToStreamOp,
26	isUnaryTableToTableOp,
27	getScalarExpressionName } = require('./utils');	2✔
28
29	function flattenAnd(expr) {
30	let flattened = [];	1,752✔
31	if (expr.isAnd) {	1,752✔
32	for (let op of expr.operands) {	638✔
33	let operands = flattenAnd(op);	1,136✔
34	operands.forEach((op) => assert(op instanceof Ast.BooleanExpression));	1,138✔
35	for (let subop of operands)	1,136✔
36	flattened.push(subop);	1,138✔
37	}
38	} else {
39	flattened.push(expr);	1,114✔
40	}
41	return flattened;	1,752✔
42	}
43
44	function flattenOr(expr) {
45	let flattened = [];	488✔
46	if (expr.isOr) {	488✔
47	for (let op of expr.operands) {	170✔
48	let operands = flattenOr(op);	318✔
49	operands.forEach((op) => assert(op instanceof Ast.BooleanExpression));	318✔
50	for (let subop of operands)	318✔
51	flattened.push(subop);	318✔
52	}
53	} else {
54	flattened.push(expr);	318✔
55	}
56	return flattened;	488✔
57	}
58
59	function optimizeFilter(expr) {
60	if (expr.isTrue \|\| expr.isFalse \|\| expr.isDontCare)	4,874✔
61	return expr;	614✔
62	if (expr.isAnd) {	4,260✔
63	let operands = flattenAnd(expr).map((o) => optimizeFilter(o)).filter((o) => !o.isTrue);	1,114✔
64	operands.forEach((op) => assert(op instanceof Ast.BooleanExpression));	1,014✔
65	for (let o of operands) {	616✔
66	if (o.isFalse)	1,014!
67	return Ast.BooleanExpression.False;	×
68	}
69	if (operands.length === 0)	616✔
70	return Ast.BooleanExpression.True;	30✔
71	if (operands.length === 1)	586✔
72	return operands[0];	170✔
73	return new Ast.BooleanExpression.And(expr.location, operands);	416✔
74	}
75	if (expr.isOr) {	3,644✔
76	let operands = flattenOr(expr).map((o) => optimizeFilter(o)).filter((o) => !o.isFalse);	318✔
77	operands.forEach((op) => assert(op instanceof Ast.BooleanExpression));	318✔
78	for (let o of operands) {	170✔
79	if (o.isTrue)	318!
80	return Ast.BooleanExpression.True;	×
81	}
82	if (operands.length === 0)	170!
83	return Ast.BooleanExpression.False;	×
84	if (operands.length === 1)	170✔
85	return operands[0];	28✔
86
87	// convert "x == foo \|\| x == bar" to "x in_array [foo, bar]"
88	// and "x =~ foo \|\| x =~ bar" to "x in_array~ [foo, bar]"
89	let equalityFilters = {};	142✔
90	let likeFilters = {};	142✔
91	let otherFilters = [];	142✔
92	for (let operand of operands) {	142✔
93	if (operand.isAtom) {	290✔
94	if (operand.operator === '==') {	240✔
95	if (operand.name in equalityFilters)	28✔
96	equalityFilters[operand.name].push(operand.value);	12✔
97	else
98	equalityFilters[operand.name] = [operand.value];	16✔
99	} else if (operand.operator === '=~') {	212✔
100	if (operand.name in likeFilters)	56✔
101	likeFilters[operand.name].push(operand.value);	8✔
102	else
103	likeFilters[operand.name] = [operand.value];	48✔
104	} else {
105	otherFilters.push(operand);	156✔
106	}
107	} else {
108	otherFilters.push(operand);	50✔
109	}
110	}
111	for (let eqParam in equalityFilters) {	142✔
112	if (equalityFilters[eqParam].length > 1) {	16✔
113	otherFilters.push(new Ast.BooleanExpression.Atom(expr.location, eqParam, 'in_array',	12✔
114	new Ast.Value.Array(equalityFilters[eqParam])));
115	} else {
116	otherFilters.push(new Ast.BooleanExpression.Atom(expr.location, eqParam, '==', equalityFilters[eqParam][0]));	4✔
117	}
118	}
119	for (let eqParam in likeFilters) {	142✔
120	if (likeFilters[eqParam].length > 1) {	48✔
121	otherFilters.push(new Ast.BooleanExpression.Atom(expr.location, eqParam, 'in_array~',	8✔
122	new Ast.Value.Array(likeFilters[eqParam])));
123	} else {
124	otherFilters.push(new Ast.BooleanExpression.Atom(expr.location, eqParam, '=~', likeFilters[eqParam][0]));	40✔
125	}
126	}
127
128	return new Ast.BooleanExpression.Or(expr.location, otherFilters);	142✔
129	}
130	if (expr.isNot) {	3,474✔
131	if (expr.expr.isNot) // double negation	168!
132	return optimizeFilter(expr.expr.expr);	×
133
134	let subexpr = optimizeFilter(expr.expr);	168✔
135	if (subexpr.isTrue)	168!
136	return Ast.BooleanExpression.False;	×
137	if (subexpr.isFalse)	168!
138	return Ast.BooleanExpression.True;	×
139	return new Ast.BooleanExpression.Not(expr.location, subexpr);	168✔
140	}
141	if (expr.isExternal) {	3,306✔
142	let subfilter = optimizeFilter(expr.filter);	266✔
143	if (subfilter.isFalse)	266!
144	return new Ast.BooleanExpression.False;	×
145	// NOTE: it does not hold that if subfilter is True
146	// the whole expression is true, because the invocation
147	// might return no results!
148	return new Ast.BooleanExpression.External(expr.location, expr.selector,	266✔
149	expr.channel, expr.in_params, subfilter, expr.schema);
150	}
151	if (expr.isCompute) {	3,040✔
152	// TODO
153	return expr;	190✔
154	}
155	if (expr.isVarRef) {	2,850!
156	// TODO
157	return expr;	×
158	}
159
160	let lhs = expr.name;	2,850✔
161	let rhs = expr.value;	2,850✔
162	let op = expr.operator;	2,850✔
163	if (rhs.isVarRef && rhs.name === lhs) {	2,850!
164	// x = x , x =~ x , x >= x, x <= x
165	if (op === '==' \|\| op === '=~' \|\| op === '>=' \|\| op === '<=')	×
166	return Ast.BooleanExpression.True;	×
167	}
168	return expr;	2,850✔
169	}
170
171	function optimizeStream(stream, allow_projection=true) {	×
172	if (stream.isVarRef \|\| stream.isTimer \|\| stream.isAtTimer)	792✔
173	return stream;	122✔
174
175	if (stream.isProjection) {	670!
176	if (!allow_projection)	×
177	return optimizeStream(stream.stream, allow_projection);	×
178
179	const optimized = optimizeStream(stream.stream, allow_projection);	×
180	if (!optimized)	×
181	return null;	×
182
183	// collapse projection of projection
184	if (optimized.isProjection) {	×
185	return new Ast.Stream.Projection(stream.location, optimized.stream,	×
186	stream.args, stream.schema);
187	}
188	return new Ast.Stream.Projection(stream.location, optimized, stream.args, stream.schema);	×
189	}
190
191	if (stream.isMonitor) {	670✔
192	// always allow projection inside a monitor, because the projection affects which parameters we monitor
193	let table = optimizeTable(stream.table, true);	428✔
194	if (!table)	428!
195	return null;	×
196
197	// convert monitor of a projection to a projection of a monitor
198	if (table.isProjection) {	428✔
199	const newMonitor = new Ast.Stream.Monitor(table.location, table.table, stream.args \|\| table.args, stream.schema);	12✔
200
201	if (allow_projection)	12✔
202	return new Ast.Stream.Projection(table.location, newMonitor, table.args, stream.schema);	6✔
203	else
204	return newMonitor;	6✔
205	}
206
207	stream.table = table;	416✔
208	return stream;	416✔
209	}
210
211	if (stream.isFilter) {	242✔
212	stream.filter = optimizeFilter(stream.filter);	110✔
213	// handle constant filters
214	if (stream.filter.isTrue)	110!
215	return optimizeStream(stream.stream, allow_projection);	×
216	if (stream.filter.isFalse)	110!
217	return null;	×
218	// compress filter of filter
219	if (stream.stream.isFilter) {	110!
220	stream.filter = optimizeFilter(Ast.BooleanExpression.And([stream.filter, stream.stream.filter]));	×
221	stream.stream = stream.stream.stream;	×
222	return optimizeStream(stream, allow_projection);	×
223	}
224
225	// switch filter of monitor to monitor of filter
226	if (stream.stream.isMonitor) {	110✔
227	let newstream = new Ast.Stream.Monitor(	104✔
228	stream.location,
229	new Ast.Table.Filter(stream.location, stream.stream.table, stream.filter, stream.stream.table.schema),
230	stream.stream.args,
231	stream.stream.schema
232	);
233	return optimizeStream(newstream, allow_projection);	104✔
234	}
235
236	// switch filter of project to project of filter
237	if (stream.stream.isProjection) {	6!
238	if (allow_projection) {	×
239	return optimizeStream(new Ast.Stream.Projection(	×
240	stream.location,
241	new Ast.Stream.Filter(stream.location,
242	stream.stream.stream, stream.filter, stream.stream.stream.schema),
243	stream.stream.args,
244	stream.stream.schema
245	), allow_projection);
246	} else {
247	return optimizeStream(new Ast.Stream.Filter(	×
248	stream.location,
249	stream.stream.stream,
250	stream.filter,
251	stream.stream.stream.schema
252	), allow_projection);
253	}
254	}
255	} else if (stream.isEdgeNew) {	132!
256	// collapse edge new of monitor or edge new of edge new
257	if (stream.stream.isMonitor \|\| stream.stream.isEdgeNew)	×
258	return optimizeStream(stream.stream, allow_projection);	×
259	} else if (stream.isEdgeFilter) {	132✔
260	stream.filter = optimizeFilter(stream.filter);	8✔
261	// handle constant filters
262	// we don't optimize the isTrue case here: "edge on true" means only once
263	if (stream.filter.isFalse)	8!
264	return null;	×
265	}
266
267	if (isUnaryStreamToStreamOp(stream)) {	138✔
268	let inner = optimizeStream(stream.stream, allow_projection);	16✔
269	if (!inner)	16!
270	return null;	×
271	stream.stream = inner;	16✔
272	return stream;	16✔
273	}
274
275	if (stream.isJoin) {	122!
276	let lhs = optimizeStream(stream.stream, allow_projection);	122✔
277	if (!lhs)	122!
278	return null;	×
279	let rhs = optimizeTable(stream.table, allow_projection);	122✔
280	if (!rhs)	122!
281	return null;	×
282	stream.stream = lhs;	122✔
283	stream.table = rhs;	122✔
284	return stream;	122✔
285	}
286
287	return stream;	×
288	}
289
290	function findComputeTable(table) {
291	if (table.isCompute)	154✔
292	return table;	30✔
293	if (table.isInvocation \|\| table.isVarRef)	124✔
294	return null;	114✔
295
296	// do not traverse joins or aliases, as those
297	// change the meaning of parameters and therefore the expressions
298	if (table.isJoin \|\| table.isAlias)	10!
NEW 299	return null;	×
300
301	if (isUnaryTableToTableOp(table))	10!
302	return findComputeTable(table.table);	10✔
303
NEW 304	throw new TypeError(table.constructor.name);	×
305	}
306
307	function expressionUsesParam(expr, pname) {
308	let used = false;	30✔
309	expr.visit(new class extends Ast.NodeVisitor {	30✔
310	visitVarRefValue(value) {
311	used = used \|\| value.name === pname;	30✔
312	return true;	30✔
313	}
314	});
315	return used;	30✔
316	}
317
318	function optimizeTable(table, allow_projection=true) {	14✔
319	if (table.isVarRef \|\| table.isInvocation)	3,226✔
320	return table;	1,910✔
321
322	if (table.isProjection) {	1,316✔
323	if (!allow_projection)	146✔
324	return optimizeTable(table.table);	2✔
325	if (table.table.isAggregation)	144✔
326	return optimizeTable(table.table);	2✔
327
328	const optimized = optimizeTable(table.table, allow_projection);	142✔
329	if (!optimized)	142!
330	return null;	×
331
332	// collapse projection of projection
333	if (optimized.isProjection)	142✔
334	return new Ast.Table.Projection(table.location, optimized.table, table.args, table.schema);	4✔
335	return new Ast.Table.Projection(table.location, optimized, table.args, table.schema);	138✔
336	}
337
338	if (table.isCompute) {	1,170✔
339	if (table.expression.isVarRef) // entirely redundant	134✔
340	return optimizeTable(table.table);	4✔
341
342	// look for a nested compute table and find one that has the same
343	// expression (note that joins and aliases stop the traversal)
344	// if so, we remove this compute expression entirely
345	let inner = findComputeTable(table.table);	130✔
346	while (inner) {	130✔
347	// check that our expression doesn't depend on the result of the computation
348	// (if it does, the computation is not redundant)
349	const innerOutputName = inner.alias \|\| getScalarExpressionName(inner.expression);	30✔
350
351	if (expressionUsesParam(table.expression, innerOutputName))	30✔
352	break;	10✔
353
354	// check that our expression is equal to the inner expression,
355	if (inner.expression.equals(table.expression)) {	20✔
356	// yep, found it!
357	return optimizeTable(table.table);	6✔
358	}
359
360	// try going deeper
361	inner = findComputeTable(inner.table);	14✔
362	}
363
364	// nope, no optimization here
365	inner = optimizeTable(table.table, allow_projection);	124✔
366	if (!inner)	124!
NEW 367	return null;	×
368	table.table = inner;	124✔
369	return table;	124✔
370	}
371
372	if (table.isFilter) {	1,036✔
373	table.filter = optimizeFilter(table.filter);	576✔
374	// handle constant filters
375	if (table.filter.isTrue)	576✔
376	return optimizeTable(table.table, allow_projection);	4✔
377	if (table.filter.isFalse)	572!
378	return null;	×
379	// compress filter of filter
380	if (table.table.isFilter) {	572✔
381	table.filter = optimizeFilter(new Ast.BooleanExpression.And(table.filter.location,	6✔
382	[table.filter, table.table.filter]));
383	table.table = table.table.table;	6✔
384	return optimizeTable(table, allow_projection);	6✔
385	}
386
387	// switch filter of project to project of filter
388	if (table.table.isProjection) {	566✔
389	if (allow_projection) {	16✔
390	return new Ast.Table.Projection(	14✔
391	table.location,
392	optimizeTable(new Ast.Table.Filter(
393	table.table.location,
394	table.table.table,
395	table.filter,
396	table.table.table.schema),
397	allow_projection),
398	table.table.args,
399	table.table.schema
400	);
401	} else {
402	return optimizeTable(new Ast.Table.Filter(	2✔
403	table.location,
404	table.table.table,
405	table.filter,
406	table.table.table.schema
407	), allow_projection);
408	}
409	}
410	}
411
412	if (table.isIndex && table.indices.length === 1 && table.indices[0].isArray)	1,010✔
413	table.indices = table.indices[0].value;	4✔
414
415	// turn a slice with a constant limit of 1 to an index
416	if (table.isSlice && table.limit.isNumber && table.limit.value === 1)	1,010✔
417	return optimizeTable(new Ast.Table.Index(table.location, table.table, [table.base], table.table.schema), allow_projection);	6✔
418
419	if (isUnaryTableToTableOp(table)) {	1,004✔
420	let inner = optimizeTable(table.table, allow_projection);	902✔
421	if (!inner)	902!
422	return null;	×
423	table.table = inner;	902✔
424	return table;	902✔
425	}
426	if (table.isJoin) {	102!
427	let lhs = optimizeTable(table.lhs, allow_projection);	102✔
428	if (!lhs)	102!
429	return null;	×
430	let rhs = optimizeTable(table.rhs, allow_projection);	102✔
431	if (!rhs)	102!
432	return null;	×
433	table.lhs = lhs;	102✔
434	table.rhs = rhs;	102✔
435	return table;	102✔
436	}
437
438	return table;	×
439	}
440
441	function optimizeRule(rule) {
442	let allow_projection = false;	2,144✔
443	// projectino is only allowed when the actions include notify/return
444	if (rule.actions.some((a) => a.isNotify))	2,146✔
445	allow_projection = true;	1,446✔
446	if (rule.stream) {	2,144✔
447	rule.stream = optimizeStream(rule.stream, allow_projection);	550✔
448	if (!rule.stream)	550!
449	return null;	×
450	} else if (rule.table) {	1,594✔
451	rule.table = optimizeTable(rule.table, allow_projection);	1,258✔
452	if (!rule.table)	1,258!
453	return null;	×
454	}
455	if (!rule.actions.length)	2,144!
456	return null;	×
457	return rule;	2,144✔
458	}
459
460	function optimizeProgram(program) {
461	let rules = [];	1,838✔
462	program.rules.forEach((rule) => {	1,838✔
463	if (rule.isAssignment) {	2,132✔
464	rules.push(rule);	84✔
465	} else {
466	let newrule = optimizeRule(rule);	2,048✔
467	if (newrule)	2,048!
468	rules.push(newrule);	2,048✔
469	}
470	});
471	program.rules = rules;	1,838✔
472	if (program.rules.length === 0 && program.declarations.length === 0 && Object.keys(program.classes).length === 0 && program.oninputs.length === 0)	1,838!
473	return null;	×
474	else
475	return program;	1,838✔
476	}
477
478	module.exports = {	2✔
479	optimizeRule,
480	optimizeProgram,
481	optimizeFilter
482	};

stanford-oval / thingtalk / 990

Source File Press 'n' to go to next uncovered line, 'b' for previous

Source File
Press 'n' to go to next uncovered line, 'b' for previous