1200

pending completion

Build # 1200

Build Type

Pull #288

travis-ci-com

Committed by

web-flow

Commit Message

Merge bd3bb8c4d into 7422b9ea1

Pull Request Pull Request #288: Remove all code dealing with natural language

Run Details

4236 of 5910 branches covered (71.68%)

Branch coverage included in aggregate %.

137 of 171 new or added lines in 9 files covered. (80.12%)

62 existing lines in 13 files now uncovered.

9846 of 12155 relevant lines covered (81.0%)

36859.47 hits per line

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

89.72

/lib/utils/sr_parser_runtime.ts

// -*- mode: typescript; indent-tabs-mode: nil; js-basic-offset: 4 -*-
//
// This file is part of ThingTalk
//
// Copyright 2019 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>

// A ShiftReduce parser
// This is the runtime component of tools/generate_parser.js
// (and expects tables generated in the form of tools/generate_parser.js)

import { SourceRange } from './source_locations';
import { ThingTalkSyntaxError } from './errors';

const EOF_TOKEN = ' 1EOF';

const enum ParserAction {
    Accept = 0,
    Shift = 1,
    Reduce = 2
}

export type ActionTable = { [key : number] : { [key : number] : [ParserAction, number] } };
export type GotoTable = { [key : number] : { [key : number] : number } };
export type SymbolTable = { [key : string] : number };

export interface ParserInterface {
    location : SourceRange|null;
    error(msg : string) : never;
}

type SemanticAction = ($ : ParserInterface, ...args : any[]) => any;

interface ParserConfig {
    TERMINAL_IDS : SymbolTable;
    RULE_NON_TERMINALS : number[];
    ARITY : number[];
    GOTO : GotoTable;
    PARSER_ACTION : ActionTable;
    SEMANTIC_ACTION : SemanticAction[];
}

function findExpected(actions : { [key : number] : [ParserAction, number] }, terminalIds : SymbolTable) : string[] {
    const ret = [];
    for (const tokenId in actions) {
        for (const term in terminalIds) {
            if (terminalIds[term] === Number(tokenId)) {
                ret.push(term);
                break;
            }
        }
    }
    return ret;
}

interface Parser<RootType> {
    parse(sequence : Iterable<TokenWrapper<unknown>>) : RootType;
}

export interface ParserConstructor<RootType> {
    new() : Parser<RootType>;
}

export interface TokenWrapper<T> {
    token : string;
    value : T;
    location : SourceRange|null;
}

function mergeRanges(l1 : SourceRange|null, l2 : SourceRange|null) : SourceRange|null {
    if (l1 === null)
        return l2;
    if (l2 === null)
        return l1;

    return {
        start: {
            offset: Math.min(l1.start.offset, l2.start.offset),
            line: Math.min(l1.start.line, l2.start.line),
            column: Math.min(l1.start.column, l2.start.column),
            token: Math.min(l1.start.token!, l2.start.token!),
        },
        end: {
            offset: Math.max(l1.end.offset, l2.end.offset),
            line: Math.max(l1.end.line, l2.end.line),
            column: Math.max(l1.end.column, l2.end.column),
            token: Math.max(l1.end.token!, l2.end.token!),
        }
    };
}

function tokenToString(tok : TokenWrapper<any>|string) : string {
    if (typeof tok === 'string')
        return tok;
    else
        return tok.token;
}

export function createParser<RootType>({ TERMINAL_IDS, RULE_NON_TERMINALS, ARITY, GOTO, PARSER_ACTION, SEMANTIC_ACTION } : ParserConfig) : ParserConstructor<RootType> {
    return class ShiftReduceParser {
        private _helper(sequence : Iterable<TokenWrapper<any>>, applySemanticAction : boolean) : [number[], RootType] {
            const iterator = sequence[Symbol.iterator]();

            let state = 0;
            const stack : number[] = [0];
            const results : any[] = [null];
            const output : number[] = [];
            const locations : Array<SourceRange|null> = [null];
            let currentLocation : SourceRange|null = null;
            let tokenno = 0;

            let { done, value:nextToken } = iterator.next();
            if (!done) {
                currentLocation = nextToken.location;
                if (currentLocation) {
                    currentLocation.start.token = tokenno;
                    currentLocation.end.token = tokenno + 1;
                }
                tokenno++;
            }

            const $ = {
                location: currentLocation,

                error(msg : string) {
                    throw new ThingTalkSyntaxError(msg, currentLocation);
                }
            };

            for (;;) {
                if (done)
                    nextToken = EOF_TOKEN;
                const nextTokenId = TERMINAL_IDS[tokenToString(nextToken)];

                if (!(nextTokenId in PARSER_ACTION[state]))
                    throw new ThingTalkSyntaxError(`Parse error: unexpected token ${nextToken} in state ${state}, expected ${findExpected(PARSER_ACTION[state], TERMINAL_IDS)}`, currentLocation);
                const [action, param] = PARSER_ACTION[state][nextTokenId];

                if (action === ParserAction.Accept) // accept
                    return [output, results[1]];

                if (action === ParserAction.Shift) { // shift
                    state = param;
                    stack.push(state);
                    results.push(nextToken);
                    ({ done, value:nextToken } = iterator.next());
                    if (!done) {
                        currentLocation = nextToken.location;
                        if (currentLocation) {
                            currentLocation.start.token = tokenno;
                            currentLocation.end.token = tokenno + 1;
                        }
                        tokenno++;
                    }
                } else { // reduce
                    const ruleId = param;
                    output.push(ruleId);
                    const arity = ARITY[ruleId];
                    const args = results.slice(results.length-arity, results.length);
                    const locs = locations.slice(locations.length-arity, locations.length);
                    for (let i = 0; i < arity; i++) {
                        stack.pop();
                        results.pop();
                    }
                    state = stack[stack.length-1];
                    const lhs = RULE_NON_TERMINALS[ruleId];
                    const nextState = GOTO[state][lhs];
                    state = nextState;
                    stack.push(nextState);
                    if (applySemanticAction) {
                        const action = SEMANTIC_ACTION[ruleId];

                        let ruleLocation : SourceRange|null = null;
                        for (const loc of locs)
                            ruleLocation = mergeRanges(ruleLocation, loc);

                        $.location = ruleLocation;
                        results.push(action($, ...args));
                    } else {
                        results.push(null);
                    }
                }
            }
        }

        parse(sequence : Iterable<TokenWrapper<any>>) : RootType {
            const [, ast] = this._helper(sequence, true);
            return ast;
        }

        getReduceSequence(sequence : Iterable<TokenWrapper<any>>) : number[] {
            const [reduces, ] = this._helper(sequence, false);
            return reduces;
        }
    };
}

1	// -- mode: typescript; indent-tabs-mode: nil; js-basic-offset: 4 --
2	//
3	// This file is part of ThingTalk
4	//
5	// Copyright 2019 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
21	// A ShiftReduce parser
22	// This is the runtime component of tools/generate_parser.js
23	// (and expects tables generated in the form of tools/generate_parser.js)
24
25	import { SourceRange } from './source_locations';
26	import { ThingTalkSyntaxError } from './errors';	2✔
27
28	const EOF_TOKEN = ' 1EOF';	2✔
29
30	const enum ParserAction {
31	Accept = 0,
32	Shift = 1,
33	Reduce = 2
34	}
35
36	export type ActionTable = { [key : number] : { [key : number] : [ParserAction, number] } };
37	export type GotoTable = { [key : number] : { [key : number] : number } };
38	export type SymbolTable = { [key : string] : number };
39
40	export interface ParserInterface {
41	location : SourceRange\|null;
42	error(msg : string) : never;
43	}
44
45	type SemanticAction = ($ : ParserInterface, ...args : any[]) => any;
46
47	interface ParserConfig {
48	TERMINAL_IDS : SymbolTable;
49	RULE_NON_TERMINALS : number[];
50	ARITY : number[];
51	GOTO : GotoTable;
52	PARSER_ACTION : ActionTable;
53	SEMANTIC_ACTION : SemanticAction[];
54	}
55
56	function findExpected(actions : { [key : number] : [ParserAction, number] }, terminalIds : SymbolTable) : string[] {
57	const ret = [];	8✔
58	for (const tokenId in actions) {	8✔
59	for (const term in terminalIds) {	356✔
60	if (terminalIds[term] === Number(tokenId)) {	39,308✔
61	ret.push(term);	356✔
62	break;	356✔
63	}
64	}
65	}
66	return ret;	8✔
67	}
68
69	interface Parser<RootType> {
70	parse(sequence : Iterable<TokenWrapper<unknown>>) : RootType;
71	}
72
73	export interface ParserConstructor<RootType> {
74	new() : Parser<RootType>;
75	}
76
77	export interface TokenWrapper<T> {
78	token : string;
79	value : T;
80	location : SourceRange\|null;
81	}
82
83	function mergeRanges(l1 : SourceRange\|null, l2 : SourceRange\|null) : SourceRange\|null {
84	if (l1 === null)	4,102,442!
85	return l2;	4,102,442✔
86	if (l2 === null)	×
87	return l1;	×
88
89	return {	×
90	start: {
91	offset: Math.min(l1.start.offset, l2.start.offset),
92	line: Math.min(l1.start.line, l2.start.line),
93	column: Math.min(l1.start.column, l2.start.column),
94	token: Math.min(l1.start.token!, l2.start.token!),
95	},
96	end: {
97	offset: Math.max(l1.end.offset, l2.end.offset),
98	line: Math.max(l1.end.line, l2.end.line),
99	column: Math.max(l1.end.column, l2.end.column),
100	token: Math.max(l1.end.token!, l2.end.token!),
101	}
102	};
103	}
104
105	function tokenToString(tok : TokenWrapper<any>\|string) : string {
106	if (typeof tok === 'string')	6,106,348✔
107	return tok;	16,560✔
108	else
109	return tok.token;	6,089,788✔
110	}
111
112	export function createParser<RootType>({ TERMINAL_IDS, RULE_NON_TERMINALS, ARITY, GOTO, PARSER_ACTION, SEMANTIC_ACTION } : ParserConfig) : ParserConstructor<RootType> {	2✔
113	return class ShiftReduceParser {	6✔
114	private _helper(sequence : Iterable<TokenWrapper<any>>, applySemanticAction : boolean) : [number[], RootType] {
115	const iterator = sequence[Symbol.iterator]();	3,072✔
116
117	let state = 0;	3,072✔
118	const stack : number[] = [0];	3,072✔
119	const results : any[] = [null];	3,072✔
120	const output : number[] = [];	3,072✔
121	const locations : Array<SourceRange\|null> = [null];	3,072✔
122	let currentLocation : SourceRange\|null = null;	3,072✔
123	let tokenno = 0;	3,072✔
124
125	let { done, value:nextToken } = iterator.next();	3,072✔
126	if (!done) {	3,072✔
127	currentLocation = nextToken.location;	3,068✔
128	if (currentLocation) {	3,068✔
129	currentLocation.start.token = tokenno;	3,064✔
130	currentLocation.end.token = tokenno + 1;	3,064✔
131	}
132	tokenno++;	3,068✔
133	}
134
135	const $ = {	3,072✔
136	location: currentLocation,
137
138	error(msg : string) {
UNCOV 139	throw new ThingTalkSyntaxError(msg, currentLocation);	×
140	}
141	};
142
143	for (;;) {	3,072✔
144	if (done)	6,106,348✔
145	nextToken = EOF_TOKEN;	16,524✔
146	const nextTokenId = TERMINAL_IDS[tokenToString(nextToken)];	6,106,348✔
147
148	if (!(nextTokenId in PARSER_ACTION[state]))	6,106,348✔
149	throw new ThingTalkSyntaxError(`Parse error: unexpected token ${nextToken} in state ${state}, expected ${findExpected(PARSER_ACTION[state], TERMINAL_IDS)}`, currentLocation);	8✔
150	const [action, param] = PARSER_ACTION[state][nextTokenId];	6,106,340✔
151
152	if (action === ParserAction.Accept) // accept	6,106,340✔
153	return [output, results[1]];	3,064✔
154
155	if (action === ParserAction.Shift) { // shift	6,103,276✔
156	state = param;	2,000,834✔
157	stack.push(state);	2,000,834✔
158	results.push(nextToken);	2,000,834✔
159	({ done, value:nextToken } = iterator.next());	2,000,834✔
160	if (!done) {	2,000,834✔
161	currentLocation = nextToken.location;	1,997,770✔
162	if (currentLocation) {	1,997,770✔
163	currentLocation.start.token = tokenno;	1,997,756✔
164	currentLocation.end.token = tokenno + 1;	1,997,756✔
165	}
166	tokenno++;	1,997,770✔
167	}
168	} else { // reduce
169	const ruleId = param;	4,102,442✔
170	output.push(ruleId);	4,102,442✔
171	const arity = ARITY[ruleId];	4,102,442✔
172	const args = results.slice(results.length-arity, results.length);	4,102,442✔
173	const locs = locations.slice(locations.length-arity, locations.length);	4,102,442✔
174	for (let i = 0; i < arity; i++) {	4,102,442✔
175	stack.pop();	6,100,204✔
176	results.pop();	6,100,204✔
177	}
178	state = stack[stack.length-1];	4,102,442✔
179	const lhs = RULE_NON_TERMINALS[ruleId];	4,102,442✔
180	const nextState = GOTO[state][lhs];	4,102,442✔
181	state = nextState;	4,102,442✔
182	stack.push(nextState);	4,102,442✔
183	if (applySemanticAction) {	4,102,442!
184	const action = SEMANTIC_ACTION[ruleId];	4,102,442✔
185
186	let ruleLocation : SourceRange\|null = null;	4,102,442✔
187	for (const loc of locs)	4,102,442✔
188	ruleLocation = mergeRanges(ruleLocation, loc);	4,102,442✔
189
190	$.location = ruleLocation;	4,102,442✔
191	results.push(action($, ...args));	4,102,442✔
192	} else {
UNCOV 193	results.push(null);	×
194	}
195	}
196	}
197	}
198
199	parse(sequence : Iterable<TokenWrapper<any>>) : RootType {
200	const [, ast] = this._helper(sequence, true);	3,072✔
201	return ast;	3,064✔
202	}
203
204	getReduceSequence(sequence : Iterable<TokenWrapper<any>>) : number[] {
UNCOV 205	const [reduces, ] = this._helper(sequence, false);	×
UNCOV 206	return reduces;	×
207	}
208	};
209	}

stanford-oval / thingtalk / 1200

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