Module c

Defines a C API for working with stack graphs in other languages.

Structs

sg_edge

Connects two nodes in a stack graph.

sg_file

A source file that we have extracted stack graph data from.

sg_files

An array of all of the files in a stack graph. File handles are indices into this array. There will never be a valid file at index 0; a handle with the value 0 represents a missing file.

sg_forward_partial_path_stitcher

Implements a phased forward partial path stitching algorithm.

sg_node

A node in a stack graph.

sg_node_handle_set

Encodes a set of node handles.

sg_node_id

Uniquely identifies a node in a stack graph.

sg_node_source_info

A tuple of a node handle and source information for that node. Used with the sg_add_source_info function to add source information to a stack graph.

sg_nodes

An array of all of the nodes in a stack graph. Node handles are indices into this array. There will never be a valid node at index 0; a handle with the value 0 represents a missing node.

sg_offset

The offset of a character within a string (typically a line of source code), using several different units

sg_partial_path

A portion of a name-binding path.

sg_partial_path_arena

Manages the state of a collection of partial paths to be used in the path-stitching algorithm.

sg_partial_path_database

Contains a “database” of partial paths.

sg_partial_path_edge

Details about one of the edges in a partial path

sg_partial_path_edge_list

The edges in a path keep track of precedence information so that we can correctly handle shadowed definitions.

sg_partial_path_edge_list_cell

An element of a partial path edge list.

sg_partial_path_edge_list_cells

The array of all of the partial path edge list content in a partial path arena.

sg_partial_path_list

A list of paths found by the path-finding algorithm.

sg_partial_paths

An array of all of the partial paths in a partial path database. Partial path handles are indices into this array. There will never be a valid partial path at index 0; a handle with the value 0 represents a missing partial path.

sg_partial_scope_stack

A pattern that might match against a scope stack. Consists of a (possibly empty) list of exported scopes, along with an optional scope stack variable.

sg_partial_scope_stack_cell

An element of a partial scope stack.

sg_partial_scope_stack_cells

The array of all of the partial scope stack content in a partial path arena.

sg_partial_scoped_symbol

A symbol with an unknown, but possibly empty, list of exported scopes attached to it.

sg_partial_symbol_stack

A pattern that might match against a symbol stack. Consists of a (possibly empty) list of partial scoped symbols.

sg_partial_symbol_stack_cell

An element of a partial symbol stack.

sg_partial_symbol_stack_cells

The array of all of the partial symbol stack content in a partial path arena.

sg_position

All of the position information that we have about a character in a source file

sg_source_info

Contains information about a range of code in a source code file.

sg_source_infos

An array of all of the source information in a stack graph. Source information is associated with nodes, so node handles are indices into this array. It is not guaranteed that there will an entry in this array for every node handle; if you have a node handle whose value is larger than count, then use a 0-valued sg_source_info if you need source information for that node.

sg_span

All of the position information that we have about a range of content in a source file

sg_stack_graph

Contains all of the nodes and edges that make up a stack graph.

sg_stitcher_config

sg_string

Arbitrary string content associated with some part of a stack graph.

sg_strings

An array of all of the interned strings in a stack graph. String handles are indices into this array. There will never be a valid string at index 0; a handle with the value 0 represents a missing string.

sg_symbol

A name that we are trying to resolve using stack graphs.

sg_symbols

An array of all of the symbols in a stack graph. Symbol handles are indices into this array. There will never be a valid symbol at index 0; a handle with the value 0 represents a missing symbol.

sg_utf8_bounds

A half-open range identifying a range of characters in a string.

Enums

sg_deque_direction

Describes in which direction the content of a deque is stored in memory.

sg_node_kind

The different kinds of node that can appear in a stack graph.

sg_result

Describes the result of a computation

Constants

SG_JUMP_TO_NODE_HANDLE

The handle of the singleton “jump to scope” node.

SG_JUMP_TO_NODE_ID

The local_id of the singleton “jump to scope” node.

SG_LIST_EMPTY_HANDLE

The handle of an empty list.

SG_NULL_HANDLE

The null value for all of our handles.

SG_ROOT_NODE_HANDLE

The handle of the singleton root node.

SG_ROOT_NODE_ID

The local_id of the singleton root node.

Functions

sg_forward_partial_path_stitcher_free

Frees a forward path stitcher.

sg_forward_partial_path_stitcher_from_nodes

Creates a new forward partial path stitcher that is “seeded” with a set of starting stack graph nodes. The path stitcher will be set up to find complete paths only.

sg_forward_partial_path_stitcher_from_partial_paths

Creates a new forward partial path stitcher that is “seeded” with a set of initial partial paths.

sg_forward_partial_path_stitcher_process_next_phase

Runs the next phase of the algorithm. We will have built up a set of incomplete partial paths during the previous phase. Before calling this function, you must ensure that db contains all of the possible partial paths that we might want to extend any of those candidate partial paths with.

sg_forward_partial_path_stitcher_set_max_work_per_phase

Sets the maximum amount of work that can be performed during each phase of the algorithm. By bounding our work this way, you can ensure that it’s not possible for our CPU-bound algorithm to starve any worker threads or processes that you might be using. If you don’t call this method, then we allow ourselves to process all of the extensions of all of the paths found in the previous phase, with no additional bound.

sg_forward_partial_path_stitcher_set_similar_path_detection

Sets whether similar path detection should be enabled during path stitching. Paths are similar if start and end node, and pre- and postconditions are the same. The presence of similar paths can lead to exponential blow up during path stitching. Similar path detection is disabled by default because of the accociated preformance cost.

sg_partial_path_arena_add_partial_path_edge_lists

Adds new partial path edge lists to the partial path arena. count is the number of partial path edge lists you want to create. The content of each partial path edge list comes from two arrays. The lengths array must have count elements, and provides the number of edges in each partial path edge list. The edges array contains the contents of each of these partial path edge lists in one contiguous array. Its length must be the sum of all of the counts in the lengths array.

sg_partial_path_arena_add_partial_scope_stacks

Adds new partial scope stacks to the partial path arena. count is the number of partial scope stacks you want to create. The content of each partial scope stack comes from three arrays. The lengths array must have count elements, and provides the number of scopes in each scope stack. The scopes array contains the contents of each of these scope stacks in one contiguous array. Its length must be the sum of all of the counts in the lengths array. The variables array must have count elements, and provides the optional scope stack variable for each partial scope stack.

sg_partial_path_arena_add_partial_symbol_stacks

Adds new partial symbol stacks to the partial path arena. count is the number of partial symbol stacks you want to create. The content of each partial symbol stack comes from two arrays. The lengths array must have count elements, and provides the number of symbols in each partial symbol stack. The symbols array contains the contents of each of these partial symbol stacks in one contiguous array. Its length must be the sum of all of the counts in the lengths array. The variables array must have count elements, and provides the optional symbol stack variable for each partial symbol stack.

sg_partial_path_arena_find_all_complete_paths

Finds all complete paths reachable from a set of starting nodes, placing the result into the path_list output parameter. You must free the path list when you are done with it by calling sg_path_list_done.

sg_partial_path_arena_find_partial_paths_in_file

Finds all partial paths in a file that are productive and as complete as possible, placing the result into the partial_path_list output parameter. You must free the path list when you are done with it by calling sg_partial_path_list_done.

sg_partial_path_arena_free

Frees a path arena, and all of its contents.

sg_partial_path_arena_new

Creates a new, initially empty partial path arena.

sg_partial_path_arena_partial_path_edge_list_cells

Returns a reference to the array of partial path edge list content in a partial path arena. The resulting array pointer is only valid until the next call to any function that mutates the partial path arena.

sg_partial_path_arena_partial_scope_stack_cells

Returns a reference to the array of partial scope stack content in a partial path arena. The resulting array pointer is only valid until the next call to any function that mutates the partial path arena.

sg_partial_path_arena_partial_symbol_stack_cells

Returns a reference to the array of partial symbol stack content in a partial path arena. The resulting array pointer is only valid until the next call to any function that mutates the path arena.

sg_partial_path_database_add_partial_paths

Adds new partial paths to the partial path database. paths is the array of partial paths that you want to add; count is the number of them.

sg_partial_path_database_ensure_both_directions

Ensures all partial paths in the database are availabe in both forwards and backwards orientation.

sg_partial_path_database_ensure_forwards

Ensures all partial paths in the database are in forwards orientation.

sg_partial_path_database_find_local_nodes

Determines which nodes in the stack graph are “local”, taking into account the partial paths in this database. The result is valid until the next call to this function, or until the database is freed.

sg_partial_path_database_free

Frees a partial path database, and all of its contents.

sg_partial_path_database_local_nodes

Returns a reference to the set of stack graph nodes that are local, according to this database of partial paths. The resulting set is only valid until the next call to any function that mutates the partial path database.

sg_partial_path_database_mark_local_nodes

Marks that a list of stack graph nodes are local.

sg_partial_path_database_new

Creates a new, initially empty partial path database.

sg_partial_path_database_partial_paths

Returns a reference to the array of partial path data in this partial path database. The resulting array pointer is only valid until the next call to any function that mutates the partial path database.

sg_partial_path_list_count

sg_partial_path_list_free

sg_partial_path_list_new

Creates a new, empty sg_partial_path_list.

sg_partial_path_list_paths

sg_stack_graph_add_edges

Adds new edges to the stack graph. You provide an array of struct sg_edges instances. A stack graph can contain at most one edge between any two nodes. It is not an error if you try to add an edge that already exists, but it won’t have any effect on the graph.

sg_stack_graph_add_files

Adds new files to the stack graph. You provide all of the file content concatenated together into a single string, and an array of the lengths of each file. You also provide an output array, which must have the same size as lengths. We will place each file’s handle in the output array.

sg_stack_graph_add_source_infos

Adds new source information to the stack graph. You provide an array of sg_node_source_info instances. Any existing source information for any node mentioned in the array is overwritten.

sg_stack_graph_add_strings

Adds new strings to the stack graph. You provide all of the string content concatenated together into a single string, and an array of the lengths of each string. You also provide an output array, which must have the same size as lengths. We will place each string’s handle in the output array.

sg_stack_graph_add_symbols

Adds new symbols to the stack graph. You provide all of the symbol content concatenated together into a single string, and an array of the lengths of each symbol. You also provide an output array, which must have the same size as lengths. We will place each symbol’s handle in the output array.

sg_stack_graph_files

Returns a reference to the array of file data in this stack graph. The resulting array pointer is only valid until the next call to any function that mutates the stack graph.

sg_stack_graph_free

Frees a stack graph, and all of its contents.

sg_stack_graph_get_or_create_nodes

Adds new nodes to the stack graph. You provide an array of struct sg_node instances. You also provide an output array, which must have the same length as nodes, in which we will place each node’s handle in the stack graph.

sg_stack_graph_new

Creates a new, initially empty stack graph.

sg_stack_graph_nodes

Returns a reference to the array of nodes in this stack graph. The resulting array pointer is only valid until the next call to any function that mutates the stack graph.

sg_stack_graph_source_infos

Returns a reference to the array of source information in this stack graph. The resulting array pointer is only valid until the next call to any function that mutates the stack graph.

sg_stack_graph_strings

Returns a reference to the array of string data in this stack graph. The resulting array pointer is only valid until the next call to any function that mutates the stack graph.

sg_stack_graph_symbols

Returns a reference to the array of symbol data in this stack graph. The resulting array pointer is only valid until the next call to any function that mutates the stack graph.

Type Aliases

sg_file_handle

A handle to a file in a stack graph. A zero handle represents a missing file.

sg_node_handle

A handle to a node in a stack graph. A zero handle represents a missing node.

sg_partial_path_edge_list_cell_handle

A handle to an element of a partial path edge list. A zero handle represents a missing partial path edge list. A UINT32_MAX handle represents an empty partial path edge list.

sg_partial_path_handle

A handle to a partial path in a partial path database. A zero handle represents a missing partial path.

sg_partial_scope_stack_cell_handle

A handle to an element of a partial scope stack. A zero handle represents a missing partial scope stack. A UINT32_MAX handle represents an empty partial scope stack.

sg_partial_symbol_stack_cell_handle

A handle to an element of a partial symbol stack. A zero handle represents a missing partial symbol stack. A UINT32_MAX handle represents an empty partial symbol stack.

sg_scope_stack_variable

Represents an unknown list of exported scopes.

sg_string_handle

A handle to an interned string in a stack graph. A zero handle represents a missing string.

sg_symbol_handle

A handle to a symbol in a stack graph. A zero handle represents a missing symbol.

sg_symbol_stack_variable

Represents an unknown list of scoped symbols.