Code completion with holes
A code completion tool uses a neural transformer model with attention to generate syntactically-correct candidates with holes to complete a partially-formed code snippet. The model is trained to predict the expansion of non-terminal symbols of the production rules of the underlying grammar of the code snippet without being constrained to a left-to-right expansion order. A hole is a non-terminal symbol of the grammar of a programming language that marks a position in a candidate where the code completion engine is not certain of the production rule that should be used to expand the non-terminal symbol. The hole allows the code completion engine to expand other non-terminal symbols in a candidate and allow the user to guide the expansion of the holes in a candidate.
1. A system for code completion, comprising:
a processor; and a memory that stores a program configured to be executed by the processor, the program including instructions to perform acts that:
detect a partially-formed source code snippet in a source code program, wherein the source code program is associated with a programming language, wherein the programming language comprises a grammar having a plurality of production rules, wherein a production rule comprises an ordered sequence of symbols, wherein a symbol comprises a terminal symbol or a non-terminal symbol; represent the partially-formed source code snippet as a partial code state, wherein the partial code state comprises at least one non-terminal symbol;
generate a first candidate to complete the partially-formed source code snippet, wherein the generation of the first candidate iteratively expands each non-terminal symbol of the partial code state and each subsequently-generated partial code state until a termination condition exists, wherein the expansion of a non-terminal symbol is based on a probability output from a deep learning model given a respective partial code state, wherein the probability output from the deep learning model is conditioned on the respective partial code state and non-terminal symbol being expanded, wherein the expansion produces a subsequently-generated partial code state that replaces a select non-terminal symbol in accordance with a select production rule without constraint to a left-to-right expansion order; and upon existence of the termination condition, output the partial code state or subsequently-generated partial code state having a highest accumulated expansion probability as the first candidate, wherein the first candidate comprises a hole, wherein the hole is a non-terminal symbol that the deep learning model is uncertain on how to expand.
2. The system of claim 1 , wherein the program includes instructions to perform acts that:
upon user selection of the first candidate, augment the partially-formed source code snippet with the first candidate; and
generate a second candidate to complete the hole.
3. The system of claim 2 , wherein generating the second candidate to complete the hole includes instructions to perform acts that: predict top-k expansions for each non-terminal symbol of the second candidate based on a probability output from the deep learning model given the second candidate; and generate subsequently-generated partial code states from the top-k expansions of each non-terminal symbol.
4. The system of claim 1 , wherein the highest accumulated expansion probability comprises an aggregation of each probability output from the deep learning model for each expansion.
5. The system of claim 1 , wherein the program includes instructions to perform acts that: terminate the generation when the probability output by the deep learning model fails to meet a confidence threshold.
6. The system of claim 1 , wherein the program includes instructions to perform acts that:
obtain the partially-formed source code snippet in an edit session of the source code program.
7. The system of claim 1 , wherein the program includes instructions to perform acts that:
obtain a string of characters input by a user of the source code program;
find at least one non-terminal symbol that matches the string of characters; and
upon user input selecting the at least one non-terminal symbol, construct the partially-formed source code snippet from tokens preceding the selected at least one non-terminal symbol.
8. A computer-implemented method of code completion, comprising:
obtaining a partially-formed source code snippet in an edit session of a source code program, wherein the source code program is associated with a programming language, wherein the programming language comprises a grammar having a plurality of production rules, wherein a production rule comprises an ordered sequence of symbols, wherein a symbol comprises a terminal symbol or a non-terminal symbol;
transforming the partially-formed source code snippet in a partial code state, wherein the partial code state comprises at least one non-terminal symbol;
searching for a first candidate to complete the partially-formed source code snippet, wherein the search of the first candidate iteratively expands each non-terminal symbol of the partial code state and each subsequently-generated partial code state until a termination condition exists, wherein the expansion of a non-terminal symbol is based on a probability output from a deep learning model given a respective partial code state, wherein the probability of an expansion is conditioned on the respective partial code state and non-terminal symbol being expanded, wherein the expansion produces a subsequently-generated partial code state that replaces a select non-terminal symbol in accordance with a select production rule without constraint to a left-to-right expansion order; and
upon existence of the termination condition, displaying the partial code state or subsequently-generated partial code state having a highest accumulated expansion probability as the first candidate, wherein the first candidate comprises a hole, wherein the hole is a non-terminal symbol that the deep learning model is uncertain to expand.
9. The computer-implemented method of claim 8 , further comprising:
upon user selection of the first candidate, augmenting the partially-formed source code snippet with the first candidate; and
searching for a second candidate to complete the hole.
10. The computer-implemented method 9 , wherein searching for the second candidate to complete the hole further comprises:
predicting top-k expansions for each non-terminal symbol of the second candidate based on a probability output from the deep learning model given the second candidate;
expanding each non-terminal symbol in accordance with the predicted top-k expansions into partial code states; and
for each partial code state having a non-terminal symbol, iteratively expanding the non-terminal symbols in each partial code state until each partial code state comprises all terminal symbols.
11. The computer-implemented method of claim 8 , wherein the highest accumulated probability comprises an aggregation of each probability output from the deep learning model for each expansion.
12. The computer-implemented method of claim 8 , further comprising: terminating the search when the probability output by the deep learning model fails to meet a confidence threshold.
13. The computer-implemented method of claim 8 , further comprising:
obtaining the partially-formed source code snippet in an edit session of the source code program.
14. The computer-implemented method of claim 8 , further comprising:
obtaining a string of characters input by a user in the source code program;
finding at least one non-terminal symbol that matches the string of characters; and
upon user input selecting the at least one non-terminal symbol, constructing the partially-formed source code snippet from tokens preceding the selected at least one non-terminal symbol.
15. A hardware storage device having stored thereon computer executable instructions that are structured to be executable by a processor of a computing device to thereby cause the computing device to perform actions that:
obtain a partially-formed source code snippet of a source code program associated with a programming language, wherein the programming language comprises a grammar having a plurality of production rules, wherein a production rule comprises symbols, wherein a symbol comprises a terminal symbol or a non-terminal symbol;
represent the partially-formed source code snippet as a partial code state, wherein the partial code state comprises a sequence of symbols with at least one non-terminal symbol; and
search for a first candidate to complete the partially-formed source code snippet, wherein the search performs actions that:
predict top-k expansions for each non-terminal symbol of the partial code state based on a probability output from a deep learning model given the partial code state, wherein the probability of an expansion is conditioned on the partial code state and a select non-terminal symbol being expanded, wherein the expansion replaces the select non-terminal symbol in accordance with a select production rule;
expand the select non-terminal symbol in accordance with the predicted top-k expansions into partial code states without constraint to a left-to-right expansion order;
for each partial code state having a non-terminal symbol, repeat the predict and the expand actions until a termination condition is met; and
output a partial code state as the first candidate based on a highest accumulated expansion probability, wherein the first candidate comprises a hole, wherein the hole is a non-terminal symbol that the deep learning model is uncertain to expand.
16. The hardware storage device of claim 15 , having stored thereon computer executable instructions that are structured to be executable by a processor of a computing device to thereby cause the computing device to perform actions that: upon user selection of the first candidate, augment the partially-formed source code snippet with the first candidate; and search for a second candidate to complete the hole.
17. The hardware storage device of claim 16 , having stored thereon computer executable instructions that are structured to be executable by the processor of the computing device to thereby cause the computing device to perform actions that:
generate top-k expansions for each non-terminal symbol of the second candidate based on a probability output from the deep learning model given the second candidate; perform expansions of each non-terminal symbol in accordance with the predicted top-k expansions into partial code states; and for each partial code state having a non-terminal symbol, repeat the generating and performing actions until a partial code state is generated comprising all terminal symbols.
18. The hardware storage device of claim 15 , wherein the highest accumulated probability comprises an aggregation of each probability output from the deep learning model for each expansion.
19. The hardware storage device of claim 15 , having stored thereon computer executable instructions that are structured to be executable by the processor of the computing device to thereby cause the computing device to perform actions that:
terminate the search when the probability output by the deep learning model fails to meet a confidence threshold.
20. The hardware storage device of claim 15 , having stored thereon computer executable instructions that are structured to be executable by the processor of the computing device to thereby cause the computing device to perform actions that: obtain the partially-formed source code snippet in an edit session of the source code program.