Read, Write, And Array Tracking In Code Representations

Patent metadata

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

Abstract

Read, write, and array tracking may be performed for a tree representing a program or a portion of a program. A tree may be obtained from a compiler or an interpreter. The tree may be traversed to generate a map data structure in a single pass, constructing a chain of dependencies between results observed at each node visited as part of traversing the tree.

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:
obtain a tree representing a program or a portion of a program;
traverse the tree to generate a map data structure in a single pass, wherein the map data structure maps the tree, and different subtrees of the tree, to respective data structures that comprise:
a first set of variables declared prior to the program or the portion of the program represented by the tree and in scope for the tree;
a second set of variables read by the program or the portion of the program represented by the tree; and
a third set of variables modified by the program or the portion of the program represented by the tree; and
a set of array references that respectively reference an array possibly modified by the program or the portion of the program represented by the tree; and
wherein to traverse the tree, the program instructions cause the at least one processor to construct a chain of dependencies between results observed at each node visited as part of traversing the tree.

2 . The system of claim 1 , wherein the program or the portion of the program is a probabilistic programming language.

3 . The system of claim 1 , wherein to traverse the tree, the program instructions cause the at least one processor to determine whether a variable name is overloaded.

4 . The system of claim 1 , wherein to traverse the tree, the program instructions cause the at least one processor to determine whether more than one global reference points to a same array.

5 . The system of claim 1 , wherein to traverse the tree, the program instructions cause the at least one processor to determine whether at least one reference is maintained to an outer most array.

6 . The system of claim 1 , wherein to traverse the tree, the program instructions cause the at least one processor to determine whether one of the set of array references to the array is placed in two or more other arrays.

7 . The system of claim 1 , wherein to traverse the tree, the program instructions cause the at least one processor to determine whether the first set of variables is within scope of at least:
a for statement; or an if-else statement; or the for statement and the if-else statement.

8 . A method, comprising:
performing, by one or more computing devices:
for a tree representing a program or a portion of the program:
traversing the tree to generate a map data structure in a single pass, wherein the map data structure maps the tree, and different subtrees of the tree, to respective data structures that comprise:
a first set of variables declared prior to the program or the portion of the program represented by the tree and in scope for the tree;
a second set of variables read by the program or the portion of the program represented by the tree;
a third set of variables modified by the program or the portion of the program represented by the tree; and
a set of array references that respectively reference an array possibly modified by the program or the portion of the program represented by the tree; and

wherein traversing the tree comprises constructing a chain of dependencies between results observed at each node visited as part of traversing the tree.

9 . The method of claim 8 , wherein the program or the portion of the program is specified in a probabilistic programming language.

10 . The method of claim 8 , wherein traversing the tree further comprises determining whether a variable name is overloaded.

11 . The method of claim 8 , wherein traversing the tree further comprises determining whether more than one global references points to a same array.

12 . The method of claim 8 , wherein traversing the tree further comprises determining whether at least one reference is maintained to an outer most array.

13 . The method of claim 8 , wherein traversing the tree further comprises determining whether one of the set of array references to the array is placed in two or more other arrays.

14 . The method of claim 8 , wherein traversing the tree further comprises determining whether the first set of variables is within scope of at least:
a for statement; or an if-else statement; or the for statement and the if-else statement.

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:
for a tree representing a program or the portion of the program:
traversing the tree to generate a map data structure in a single pass, wherein the map data structure maps the tree, and different subtrees of the tree, to respective data structures that comprise:
a first set of variables declared prior to the program or the portion of the program represented by the tree and in scope for the tree;
a second set of variables read by the program or the portion of the program represented by the tree; and
a third set of variables modified by the program or the portion of the program represented by the tree; and
a set of array references that respectively reference an array possibly modified by the program or the portion of the program represented by the tree; and

wherein in traversing the tree, the program instructions cause the one or more computing devices to implement constructing a chain of dependencies between results observed at each node visited as part of traversing the tree.

16 . The one or more non-transitory, computer-readable storage media of claim 15 , wherein the program or the portion of the program is specified in a probabilistic programming language.

17 . The one or more non-transitory, computer-readable storage media of claim 15 , wherein, in traversing the tree, the programming instructions cause the one or more computing devices to implement determining whether a variable name is overloaded.

18 . The one or more non-transitory, computer-readable storage media of claim 15 , wherein, in traversing the tree, the programming instructions cause the one or more computing devices to implement determining whether more than one global references points to a same array.

19 . The one or more non-transitory, computer-readable storage media of claim 15 , wherein, in traversing the tree, the programming instructions cause the one or more computing devices to implement determining whether one of the set of array references to the array is placed in two or more other arrays.

20 . The one or more non-transitory, computer-readable storage media of claim 15 ,
wherein, in traversing the tree, the programming instructions cause the one or more computing devices to implement determining whether the first set of variables is within scope of at least: a for statement; an if-else statement; or the for statement and the if-else statement.

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

  Target code generation · CPC title

• G06F8/30

  Creation or generation of source code · CPC title