Analysis

This page describes the algorithms and data structures for performing analysis on FPP source models.

Data Structures

• Abstract syntax tree (AST): The structure representing the abstract source syntax of an input model. The AST consists of nodes arranged in a tree with a parent-child relationship.

• Analysis data structure: Defined here.

• AST node: An AST node represents an element of the source syntax. Each AST node has a unique integer identifier.

• Command: An FPP command specifier.

• Component: An FPP component, consisting of the following:

  1. A map from port names to port instances.

  2. A map from special port kinds to special port instances.

  3. A map from event identifiers to events.

  4. A map from command opcodes to commands.

  5. A map from parameter identifiers to parameters.

  6. A map from telemetry channel identifiers to telemetry channels.

  7. A map from container identifiers to containers.

  8. A map from record identifiers to records.

• Component instance: An FPP component instance. Contains a map from execution phases to init specifiers.

• Connection: An FPP connection consisting of an output port instance, an optional output port number, an input port instance, and an optional input port number.

• Connection graph pattern: An FPP connection graph pattern consisting of a pattern kind, a source instance, and a list of target instances.

• Container: An FPP specifier for a data product container.

• Dictionary data structure: Structure representing the dictionary produced for an FPP topology, consisting of:

  1. The set of type symbols used in the topology

  2. A map from resolved identifiers to commands

  3. A map from resolved identifiers to telemetry channels

  4. A map from resolved identifiers to events

  5. A map from resolved identifiers to parameters

  6. A map from resolved identifiers to records

  7. A map from resolved identifiers to containers

• Event: An FPP specifier for an event report.

• Expression: A syntactic expression. Expressions with identical form (e.g., two instances of the literal value 3) appearing at distinct nodes in the AST count as distinct expressions.

• File: One of (a) an absolute path on the system where the analysis occurs; or (b) a special system file such as stdin or stdout.

• Init specifier: An FPP init specifier.

• Internal port: An internal port used in a component definition.

• Location map: A map from AST nodes to their locations.

• Location: A file and line number indicating the location of an AST node.

• Name-symbol map: A local mapping of unqualified names to symbols. For any name-symbol map s and name n, if the mapping s[n] already exists, then it is an error to attempt to add a new mapping for n.

• Name: A name, either qualified or unqualified. Names are not associated with nodes in the AST. For example, there is only one name a.b.c.

• Nested scope: A stack of scopes that represents the nesting of scopes inside each other. Scopes are pushed on the stack (starting with the global scope) when moving inwards in the nesting, and popped off the stack when returning outwards. New mappings of names to symbols are added to the innermost scope. Lookup of names n starts with the innermost scope S, moving to the next level up only if there is no entry for n in S, and finally giving up with an error if there is no entry for n at the outermost scope.

• Parameter: An FPP ground parameter specifier.

• Port instance: A instance of a port definition used in a component definition. A port instance can be (1) a general instance of a port definition or (2) a special port instance or (3) an instance of an internal port.

• Port: An FPP port definition.

• Qualified identifier: A qualified identifier appearing in the source syntax. A qualified identifier is either an unqualified name (e.g., a) or a qualified identifier followed by an unqualified name (e.g., a.b). A qualified identifier represents a qualified name. Qualified identifiers representing the same qualified name (e.g., the name a.b.c) and appearing at distinct nodes in the AST count as distinct qualified identifiers.

• Record: An FPP specifier for a data product record.

• Scope: A collection of name-symbol maps that represents a single flat scope (the global scope or a brace-delimited scope). Within each scope, there is one name-symbol map for each name group (values, types, etc.).

• Symbol: A data structure that represents a definition. There is one kind of symbol for each kind of definition. A module symbol for a module M stores the first AST node encountered that adds definitions to M. A non-module symbol stores the unique AST node where the definition occurs.

• Telemetry channel: An FPP telemetry channel specifier.

• Topology: An FPP topology, consisting of the following:

  1. A set of topology symbols representing the directly imported topology definitions.

  2. A set of topology symbols representing the transitively imported topology definitions.

  3. A set of component instances. Each instance may be either public or private for this topology.

  4. A set of connection graph patterns.

  5. A map from connection graph names to sets of connections.

  6. A map from connection graph names to sets of locally defined (i.e., not imported) connections.

  7. A map from ports to their output connections.

  8. A map from ports to their input connections.

  9. A map from connections to their from port numbers.

  10. A map from connections to their to port numbers.

  11. The set of unconnected port instances.

• Type name: A syntactic type name. A type name is associated with a node in the AST, so two different type names can refer to the same type. For example, if the keyword U32 appears at multiple nodes in the AST, then there are multiple type names that all refer to the same type U32.

• Type: An FPP type. Types include internal types such as Integer. Types are not associated with nodes in the AST. For example, there is only one type U32. Multiple type names can refer to the same type. Array types have resolved constants for their size expressions.

• Use-def matching: A data structure that matches the use of a symbol with the symbol it uses. A use-def matching stores an AST node identifier (the use), a qualified name (the qualified name appearing in the use), and a symbol (the definition that the use refers to).

• Value: An FPP value.

State Machine Data Structures

• Guarded transition: A pair consisting of an optional guard and a transition.

• Signal-transition map: A map from signals to guarded transitions. For each signal in the map, the corresponding transition is the state transition on that signal.

• State machine analysis data structure: Defined here.

• State machine name-symbol map: A local mapping of unqualified names to symbols inside a state machine definition. State machine name-symbol maps operate in the same way as name-symbol maps.

• State machine nested scope: A stack of scopes that represents the nesting of scopes inside a state machine definition. State machine nested scopes operate in the same way as nested scopes.

• State machine scope: A collection of state machine name-symbol maps that represents a single flat scope within a state machine definition. State machine scopes operate in the same way as scopes.

• State machine symbol: A data structure that represents a definition of a state machine element inside a state machine definition. There is one kind of state machine symbol for each kind of definition.

• State machine: An FPP state machine. It stores a state machine analysis data structure representing the results of analysis on the state machine.

• State or choice: A data structure that represents either a state definition symbol or a choice definition symbol.

• State-transition map: A map from states to guarded transitions. One of these maps exists for each signal in the state machine.

• Transition: A data structure representing a transition in a state machine. It is either an external transition or an internal transition. An external transition stores a list of actions and a state or choice. The actions are performed when making the transition. The state or choice is the target of the transition. An internal transition stores a list of actions to perform without leaving the current state.

• Transition expression: An expression that provides the target for an external transition, together with an optional list of actions to perform. Each transition expression appearing in the source syntax has a distinct identity.

• Transition graph arc: An arc in the transition graph. It is one of the following three kinds of values: (1) an initial transition arc consisting of a start state, an initial transition specifier, and an end node; or (2) a state transition arc consisting of a start state, a state transition specifier, and and end node; or (3) a choice transition arc consisting of a choice definition, a transition expression, and an end node.

• Transition graph node: A data structure that represents a node in the transition graph. It stores a state or choice.

• Transition graph: A data structure that represents the possible transitions in the state machine. It stores (1) an initial transition graph node and (2) a map from transition graph nodes to sets of transition graph arcs.

• Typed element: A typed element is an element of a state machine definition that is assigned an optional type. It is an initial transition specifier, a state entry specifier, a state transition specifier, a state exit specifier, or a choice definition.

Algorithms

• Computing Dependencies

• Checking Semantics

• Dictionary Construction