Generating Constraints In A Target Programming Language From Traces Of Operations Specified In An Input

Patent metadata

Field	Value
Publication number	US-2025147743-A1
Application number	US-202418770219-A
Country	US
Kind code	A1
Filing date	Jul 11, 2024
Priority date	Nov 8, 2023
Publication date	May 8, 2025
Grant date	—

Abstract

Constraints may be generated in a target programming language from traces of operations specified in a source input. Operations specified in an input, such as a data structure like a Directed Acyclic Graph (DAG) or source programming language, that access data may be traced. Based on the traces, a code template may be generated in a target programming language or data structure to test the operations of the traces to determine which traces are valid in order to add a portion of code in the target programing language that allow external code to be run only on valid traces.

First claim

What is claimed:

1 . A system, comprising:
at least one processor; a memory, comprising program instructions that when executed by the at least one processor cause the at least one processor to:
generate a plurality of traces of a plurality of operations specified in an input that access data between a start node and an end node, wherein the plurality of operations comprise one or more put operations using a put index variable to set a value in an entry in an array and one or more get operations using a get index variable to obtain the value from the entry in the array;
based on the plurality of traces, generate a code template in a target programming language to test the plurality of operations of the plurality of traces, wherein the code template:
identifies a valid trace in the plurality of traces between the start node and the end node by pairing corresponding ones of the one or more put operations and the one or more get operations and testing for equivalence of index values calculated for the put index variable and the get index variable in respective contexts of the put operations and the get operations, wherein the pairing of the corresponding put operations and the get operations and the respective contexts are determined according to at least a forward pass and a backward pass respectively performed over individual ones of the plurality of traces to construct a set of loops and loop index substitutions that test for equivalence of the index values in the paired corresponding ones of the one or more put operations and the one or more get operations of the valid trace; and
for the identified valid trace, add a portion of code in the target programming language into the set of loops that prevents execution of further code placed in the code template for additional valid traces.

2 . The system of claim 1 , wherein the input is a Directed Acyclic Graph (DAG).

3 . The system of claim 1 , wherein the portion of code in the target language comprises one or more additional loops that act as guard loops.

4 . The system of claim 1 , wherein the one or more additional loops are described in a guard description data object created as part of generating the code template.

5 . The system of claim 4 , wherein a check is performed when creating the guard description object to determine whether more than one constraint trace exists.

6 . The system of claim 1 , wherein to generate the code template in the target programming language, the program instructions cause the at least one processor to:
identify a put operation of the plurality of operations in a trace that updates a portion of shared state; and instead of adding instructions to modify the shared state, add a local variable declaration to store the value the put operation would assign as local at one or more locations in the code template that correspond to when the value would be calculated; and add instructions to read the local variable declarations instead of the portion of shared state.

7 . The system of claim 1 , wherein to add the portion of code in the target programming language into the set of loops that prevents execution of further code placed in the code template for additional valid traces, the program instructions cause the at least one processor to:
adding a guard for a conditional assignment reached in the valid trace responsive to the conditional assignment being reached via an if statement of the conditional assignment; or adding a negation of a guard for a conditional assignment reached in the valid trace responsive to the conditional assignment being reached via an else statement of the conditional assignment.

8 . A method, comprising:
generating a plurality of traces of a plurality of operations specified in an input that access data between a start node and an end node, wherein the plurality of operations comprise one or more put operations using a put index variable to set a value in an entry in an array and one or more get operations using a get index variable to obtain the value from the entry in the array; based on the plurality of traces, generating a code template in a target programming language to test the plurality of operations of the plurality of traces, wherein the code template: identifying a valid trace in the plurality of traces between the start node and the end node by pairing corresponding ones of the one or more put operations and the one or more get operations and testing for equivalence of index values calculated for the put index variable and the get index variable in respective contexts of the put operations and the get operations, wherein the pairing of the corresponding put operations and the get operations and the respective contexts are determined according to at least a forward pass and a backward pass respectively performed over individual ones of the plurality of traces to construct a set of loops and loop index substitutions that test for equivalence of the index values in the paired corresponding ones of the one or more put operations and the one or more get operations of the valid trace; and for the identified valid trace, adding a portion of code in the target programming language into the set of loops that prevents execution of further code placed in the code template for additional valid traces.

9 . The method of claim 8 , wherein the input is a probabilistic programming language and wherein the target programming language is a non-probabilistic programming language.

10 . The method of claim 8 , wherein the portion of code in the target language comprises one or more additional loops that act as guard loops.

11 . The method of claim 8 , wherein the one or more additional loops are described in guard description data object created as part of generating the code template.

12 . The method of claim 11 , wherein a check is performed when creating the guard description object to determine whether more than one constraint trace exists.

13 . The method of claim 8 , wherein generating the code template in the target programming language comprises:
identifying a put operation of the plurality of operations in a trace that updates a portion of shared state; and instead of adding instructions to modify the shared state, adding a local variable declaration to store the value the put operation would assign as local at one or more locations in the code template that correspond to when the value would be calculated; and adding instructions to read the local variable declarations instead of the portion of shared state.

14 . The method of claim 8 , wherein adding the portion of code in the target programming language into the set of loops that prevents execution of further code placed in the code template for additional valid traces comprises:
adding a guard for a conditional assignment reached in the valid trace responsive to the conditional assignment being reached via an if statement of the conditional assignment; or adding a negation of a guard for a conditional assignment reached in the valid trace responsive to the conditional assignment being reached via an else statement of the conditional assignment.

15 . One or more, non-transitory, computer-readable storage media, storing program instructions that when executed on or across one or more computing devices, cause the one or more computing devices to implement:
generating a plurality of traces of a plurality of operations specified in an input that access data between a start node and an end node, wherein the plurality of operations comprise one or more put operations using a put index variable to set a value in an entry in

Assignees

• Oracle Int Corp

Inventors

• Goodman Daniel

Classifications

• G06F11/3684

  for test design, e.g. generating new test cases · CPC title

• G06F8/41

  Compilation · CPC title

• G06F8/452

  Loops · CPC title

• G06F8/447 Primary

  Target code generation · CPC title

• G06F8/30

  Creation or generation of source code · CPC title