Module stack_graphs::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.