Tiered arrays

• US 9,632,760 B2
• Filed: 05/02/2016
• Issued: 04/25/2017
• Est. Priority Date: 09/30/2015
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Semmle Limited (Microsoft Corporation)
• Inventors: Hale, Joshua George
• Primary Examiner(s): Fan, Shiow-Jy
• Application Number:
  US15/143,970
• Publication Number:
  US 20170090888A1
• Time in Patent Office: 358 Days
• CPC Class Codes: G06F 11/3604 Software analysis for verifying properties of programs byte-code verification G06F9/44589
• CPC Class Codes: G06F 11/3668 Software testing software testing in telephone exchanges H04M3/242, testing of hardware G06F11/22
• CPC Class Codes: G06F 16/2237 Vectors, bitmaps or matrices
• CPC Class Codes: G06F 16/2246 Trees, e.g. B+trees
• CPC Class Codes: G06F 16/2379 Updates performed during online database operations; commit processing
• CPC Class Codes: G06F 16/245 Query processing
• CPC Class Codes: G06F 3/0481 based on specific properties of the displayed interaction object or a metaphor-based environment, e.g. interaction with desktop elements like windows or icons, or assisted by a cursor's changing behaviour or appearance
• CPC Class Codes: G06F 8/22 Procedural
• CPC Class Codes: G06F 8/24 Object-oriented
• CPC Class Codes: G06F 8/35 model driven
• CPC Class Codes: G06F 8/433 Dependency analysis; Data or control flow analysis
• CPC Class Codes: G06F 8/443 Optimisation
• CPC Class Codes: G06F 8/65 Updates security arrangements therefor G06F21/57
• CPC Class Codes: G06F 8/71 Version control security arrangements therefor G06F21/57; Configuration management
• CPC Class Codes: G06F 8/73 Program documentation
• CPC Class Codes: G06F 8/74 Reverse engineering; Extracting design information from source code
• CPC Class Codes: G06F 8/75 Structural analysis for program understanding
• CPC Class Codes: G06T 11/206 Drawing of charts or graphs
• CPC Class Codes: G06T 2200/24 involving graphical user interfaces [GUIs]
• CPC Class Codes: H04L 67/133 Protocols for remote procedure calls [RPC]

Abstract

Methods, systems, and apparatus, including computer programs encoded on computer storage media, for using tiered arrays to represent aggregated software dependencies. One of the methods includes receiving a request to generate a range of contiguous indexes having non-default values represented by a tiered array, wherein each non-default element of each tier is a reference to a catalog at a lower tier except for a bottom-most tier of the tiered array that stores non-default values. After descending one or more tiers to identify a first index that (i) is greater than or equal to the start index and (ii) has a non-default value, a system ascends one or more tiers in the tiered array and subsequently descends again to identify a second index that is a last index in a contiguous sequence of indexes having non-default values from the first index up to and including the second index.

Claims

1. A computer-implemented method comprising:

receiving a request to compute, for an overall range of indexes comprising set indexes having non-default values and unset indexes having default values, all contiguous ranges of unset indexes within the overall range of indexes,

wherein the overall range of indexes is represented by a tiered array having a plurality of tiers, wherein each tier of the tiered array comprises one or more catalogs,

wherein each catalog in each tier, except for a bottom-most tier, comprises (i) non-default elements that each identify a respective catalog at a lower tier and (ii) default elements that do not identify any catalogs, and

wherein each bottom-most catalog in the bottom-most tier comprises one or more non-default elements having non-default values, each non-default value being stored at a respective index value in the bottom-most catalog;

setting a reference index to be initially equal to a minimum index, the minimum index corresponding to an index that is first in an ordering of the overall range of indexes;

performing a search, from the reference index, for a first range [a0, b0] of contiguously set indexes having non-default values, wherein a0 is a first index in the first range of contiguously set indexes and b0 is a last index in the first range of contiguously set indexes, wherein the index a0 is a first index in the tiered array having a non-default value;

if a0 is greater than the minimum index, generating a range of indexes [0, a0−

1] having default values, wherein a0−

1 is a last index in the range of indexes having default values;

repeatedly performing the following operations until an end of the tiered array is reached;

setting the reference index to be equal to b0+2;

performing a search, from the reference index, for a next range [a1, b1] of contiguously set indexes starting at or after the index b0+2,

after obtaining the next range of contiguously set indexes, outputting generating a range of indexes [b0+1, a1−

1] having default values, and

updating b0 to be equal to b1; and

providing, in response to the request, the generated pairs of index values representing the contiguous ranges of unset indexes within the overall range of indexes.

2. The method of claim 1, wherein obtaining the first range [a0, b0] of contiguously set indexes comprises:

obtaining an index a0 that is a first index in the tiered array having a non-default value, wherein the index a0 is greater than or equal to the minimum index of the tiered array; and

obtaining an index b0 that is a last index having a non-default value in a first contiguous range of indexes having non-default values from a0 to b0 in the overall range of indexes.

3. The method of claim 2, wherein obtaining the index a0 comprises descending one or more tiers in the tiered array from a non-default element in a top-level catalog to identify a first index that (i) is greater than or equal to the minimum index and (ii) has a non-default value.

4. The method of claim 2, wherein obtaining the index b0 comprises ascending one or more tiers in the tiered array and subsequently descending one or more tiers in the tiered array to identify a second index that is a last index in a contiguous range of indexes having non-default values.

5. The method of claim 4, wherein an index c having a default value occurs immediately after the index b0.

6. The method of claim 1, further comprising:

determining that an end of the tiered array has been reached;

determining that b1 is less than a maximum index, max_index, of the tiered array; and

in response, generating a range of indexes [b1+1, max_index] having default values.

7. The method of claim 1, wherein the tiered array represents a plurality of dependencies inbound to or outbound from a node in a raw dependency graph of software elements in a project, wherein each node in the raw dependency graph represents a software element in the project, and wherein each link in the raw dependency graph represents a software dependency of a first software element on a second software element.

8. A system comprising:

one or more computers and one or more storage devices storing instructions that are operable, when executed by the one or more computers, to cause the one or more computers to perform operations comprising;

receiving a request to compute, for an overall range of indexes comprising set indexes having non-default values and unset indexes having default values, all contiguous ranges of unset indexes within the overall range of indexes,

wherein the overall range of indexes is represented by a tiered array having a plurality of tiers, wherein each tier of the tiered array comprises one or more catalogs,

wherein each catalog in each tier, except for a bottom-most tier, comprises (i) non-default elements that each identify a respective catalog at a lower tier and (ii) default elements that do not identify any catalogs, and

wherein each bottom-most catalog in the bottom-most tier comprises one or more non-default elements having non-default values, each non-default value being stored at a respective index value in the bottom-most catalog;

setting a reference index to be initially equal to a minimum index, the minimum index corresponding to an index that is first in an ordering of the overall range of indexes;

performing a search, from the reference index, for a first range [a0, b0] of contiguously set indexes having non-default values, wherein a0 is a first index in the first range of contiguously set indexes and b0 is a last index in the first range of contiguously set indexes, wherein the index a0 is a first index in the tiered array having a non-default value;

if a0 is greater than the minimum index, generating a range of indexes [0, a0−

1] having default values, wherein a0−

1 is a last index in the range of indexes having default values;

repeatedly performing the following operations until an end of the tiered array is reached;

setting the reference index to be equal to b0+2;

performing a search, from the reference index, for a next range [a1, b1] of contiguously set indexes starting at or after the index b0+2,

after obtaining the next range of contiguously set indexes, generating a range of indexes [b0+1, a1−

1] having default values, and

updating b0 to be equal to b1; and

providing, in response to the request, the generated pairs of index values representing the contiguous ranges of unset indexes within the overall range of indexes.

9. The system of claim 8, wherein obtaining the first range [a0, b0] of contiguously set indexes comprises:

obtaining an index a0 that is a first index in the tiered array having a non-default value, wherein the index a0 is greater than or equal to the minimum index of the tiered array; and

obtaining an index b0 that is a last index having a non-default value in a first contiguous range of indexes having non-default values from a0 to b0 in the overall range of indexes.

10. The system of claim 9, wherein obtaining the index a0 comprises descending one or more tiers in the tiered array from a non-default element in a top-level catalog to identify a first index that (i) is greater than or equal to the minimum index and (ii) has a non-default value.

11. The system of claim 9, wherein obtaining the index b0 comprises ascending one or more tiers in the tiered array and subsequently descending one or more tiers in the tiered array to identify a second index that is a last index in a contiguous range of indexes having non-default values.

12. The system of claim 11, wherein an index c having a default value occurs immediately after the index b0.

13. The system of claim 8, wherein the operations further comprise:

determining that an end of the tiered array has been reached;

determining that b1 is less than a maximum index, max_index, of the tiered array; and

in response, generating a range of indexes [b1+1, max_index] having default values.

14. The system of claim 8, wherein the tiered array represents a plurality of dependencies inbound to or outbound from a node in a raw dependency graph of software elements in a project, wherein each node in the raw dependency graph represents a software element in the project, and wherein each link in the raw dependency graph represents a software dependency of a first software element on a second software element.

15. A computer program product, encoded on one or more non-transitory computer storage media, comprising instructions that when executed by one or more computers cause the one or more computers to perform operations comprising:

receiving a request to compute, for an overall range of indexes comprising set indexes having non-default values and unset indexes having default values, all contiguous ranges of unset indexes within the overall range of indexes,

wherein the overall range of indexes is represented by a tiered array having a plurality of tiers, wherein each tier of the tiered array comprises one or more catalogs,

wherein each catalog in each tier, except for a bottom-most tier, comprises (i) non-default elements that each identify a respective catalog at a lower tier and (ii) default elements that do not identify any catalogs, and

wherein each bottom-most catalog in the bottom-most tier comprises one or more non-default elements having non-default values, each non-default value being stored at a respective index value in the bottom-most catalog;

setting a reference index to be initially equal to a minimum index, the minimum index corresponding to an index that is first in an ordering of the overall range of indexes;

performing a search, from the reference index, for a first range [a0, b0] of contiguously set indexes having non-default values, wherein a0 is a first index in the first range of contiguously set indexes and b0 is a last index in the first range of contiguously set indexes, wherein the index a0 is a first index in the tiered array having a non-default value;

if a0 is greater than the minimum index, generating a range of indexes [0, a0−

1] having default values, wherein a0−

1 is a last index in the range of indexes having default values;

repeatedly performing the following operations until an end of the tiered array is reached;

setting the reference index to be equal to b0+2;

performing a search, from the reference index, for a next range [a1, b1] of contiguously set indexes starting at or after the index b0+2,

after obtaining the next range of contiguously set indexes, generating a range of indexes [b0+1, a1−

1] having default values, and

updating b0 to be equal to b1; and

providing, in response to the request, the generated pairs of index values representing the contiguous ranges of unset indexes within the overall range of indexes.

16. The computer program product of claim 15, wherein obtaining the first range [a0, b0] of contiguously set indexes comprises:

obtaining an index a0 that is a first index in the tiered array having a non-default value, wherein the index a0 is greater than or equal to the minimum index of the tiered array; and

obtaining an index b0 that is a last index having a non-default value in a first contiguous range of indexes having non-default values from a0 to b0 in the overall range of indexes.

17. The computer program product of claim 16, wherein obtaining the index a0 comprises descending one or more tiers in the tiered array from a non-default element in a top-level catalog to identify a first index that (i) is greater than or equal to the minimum index and (ii) has a non-default value.

18. The computer program product of claim 16, wherein obtaining the index b0 comprises ascending one or more tiers in the tiered array and subsequently descending one or more tiers in the tiered array to identify a second index that is a last index in a contiguous range of indexes having non-default values.

19. The computer program product of claim 18, wherein an index c having a default value occurs immediately after the index b0.

20. The computer program product of claim 15, wherein the operations further comprise:

determining that an end of the tiered array has been reached;

determining that b1 is less than a maximum index, max_index, of the tiered array; and

in response, generating a range of indexes [b1+1, max_index] having default values.

21. The computer program product of claim 15, wherein the tiered array represents a plurality of dependencies inbound to or outbound from a node in a raw dependency graph of software elements in a project, wherein each node in the raw dependency graph represents a software element in the project, and wherein each link in the raw dependency graph represents a software dependency of a first software element on a second software element.