fpp/docs/spec/Definitions/Topology-Definitions.adoc

=== Topology Definitions

A *topology definition* defines an F Prime topology,
that is, a set of objects with ports (component instances and subtopologies)
and the connections among the ports.
Before generating code, connections involving topology ports are flattened,
so that all connection endpoints occur at ports of component instances.

The connections are divided into named *connection graphs*.
The different graphs capture different aspects of FSW
function, such as commanding and telemetry.

When one topology refers to another one, we say
that the second topology is a *subtopology* of the first one.
The component instances, topologies, and connections of the second
topology are merged into the first one.
The connections are merged graph by graph.

==== Syntax

`topology`
<<Lexical-Elements_Identifiers,_identifier_>>
_[_ `implements` _interface-list_ _]_
`{` _topology-member-sequence_ `}`

The optional _interface-list_ is an
<<Element-Sequences,element sequence>> in which
each element is a <<Scoping-of-Names_Qualified-Identifiers,
qualified identifier>> and the terminating punctuation is a comma.

_topology-member-sequence_ is an
<<Element-Sequences,element sequence>> in
which each element is a *topology member*,
and the terminating punctuation is a semicolon.
A topology member is one of the following:

* A <<Specifiers_Connection-Graph-Specifiers,connection graph specifier>>

* A <<Specifiers_Port-Interface-Instance-Specifiers,port interface
instance specifier>>

* A <<Specifiers_Telemetry-Packet-Set-Specifiers,telemetry packet set specifier>>

* A <<Specifiers_Topology-Port-Instance-Specifiers,topology port instance specifier>>

* An <<Specifiers_Include-Specifiers,include specifier>>

==== Semantics

The identifier is the name of the topology.

The topology definition _D_ must be resolvable to a topology _T_,
according to the following algorithm:

. Resolve _D_ to a
<<Definitions_Topology-Definitions_Semantics_Resolving-to-a-Partially-Numbered-Topology,
partially numbered topology>> _T'_.

. <<Definitions_Topology-Definitions_Semantics_Checking-Telemetry-Packet-Set-Specifiers,
Check telemetry packet set specifiers>> for _T'_.

. Apply
<<Definitions_Topology-Definitions_Semantics_Automatic-Numbering-of-Ports,
automatic numbering of ports>>
to _T'_.

. Check the
<<Definitions_Topology-Definitions_Semantics_Topology-Interface,
topology interface>> for _T'_.

===== Resolving to a Partially Numbered Topology

A *partially numbered topology* is a topology in which (a) all connection 
endpoints are <<Specifiers_Connection-Graph-Specifiers_Semantics,component 
instance endpoints>>
and (b) port number assignments may or may not exist for each connection.
A port number assignment exists if
it is specified in the model source.

. For each <<Specifiers_Connection-Graph-Specifiers_Syntax,endpoint>> _E_
(output or input) in each connection _C_
appearing in a 
<<Specifiers_Connection-Graph-Specifiers,direct connection graph>> of _D_,
if _E_ has a port number  expression _e_ in the FPP source, then
<<Evaluation,evaluate>> _e_,
<<Type-Checking_Type-Conversion,convert>> the result to a value _n_ of type
_Integer_, and assign the port number _n_ at endpoint _E_ of connection _C_.
Check that _n_ is in bounds for the port instance being numbered.

. Let _S_ be the set of all topologies that are named as
<<Specifiers_Port-Interface-Instance-Specifiers,instances>>
in _D_.
Recursively resolve all the topologies in _S_.

. Construct the connection graphs of _T_ given by the
<<Specifiers_Connection-Graph-Specifiers,direct connection graphs>>
appearing in
_D_, after merging each set of connection graphs with the same name into
a single graph.
For example, the two connection graphs
+
[source,fpp]
----
connections C { a.b -> c.d }
----
+
and
+
[source,fpp]
----
connections C { e.f -> g.h }
----
+
are treated as the single graph
+
[source,fpp]
----
connections C { a.b -> c.d, e.f -> g.h }
----
+

. Let the initial set of instances of _T_ be the
<<Specifiers_Port-Interface-Instance-Specifiers,port interface instances>>
specified in the definition of _T_.
For each topology _T'_ in _S_ (step 2),
<<Definitions_Topology-Definitions_Importing-Subtopologies_Importing-Interface-Instances,import 
the instances>>
of _T'_ into _T_.
Note that _T'_ is resolved (step 2), so the set of instances of _T'_ contains 
all topologies transitively
imported by the definition of _T'_.

. For each connection _C_ discovered in step 3, check that each
<<Specifiers_Connection-Graph-Specifiers_Syntax,endpoint>> of _C_
refers to one of the port interface instances computed in the previous step.

. For each 
<<Specifiers_Connection-Graph-Specifiers_Syntax,connection endpoint>>
_E_ of a connection computed in step 3, do the following:

.. If _E_ is a <<Specifiers_Connection-Graph-Specifiers_Semantics,component instance endpoint>>,
then do nothing.

.. Otherwise the <<Instance-Member-Identifiers_Port-Instance-Identifiers,port instance identifier>>
_P_ appearing in _E_ has the form _Q_ 
`.` _I_, where _Q_ refers to a topology _T'_, and
_I_ names a port of _T'_.

... Find the <<Specifiers_Topology-Port-Instance-Specifiers,
topology port instance specifier>> `port` _I_ `=` _P'_ in _T'_.

...  Replace _P_ with _P'_ in the endpoint _E_.
Retain the port number assignment, if any, at _E_ computed in step 1.

... Reapply steps a and b to the endpoint _E_.

. For each topology _T'_ in _S_,
<<Definitions_Topology-Definitions_Importing-Subtopologies_Importing-Connections,import 
the connections>>
of _T'_ into _T_.
Note that _T'_ is resolved (step 2), so all the connections in _T'_
have <<Specifiers_Connection-Graph-Specifiers_Semantics,component instance 
endpoints>>.

. At this point all connection endpoints are component instance endpoints.
There are no connections whose endpoints are topology endpoints.

. Resolve
<<Specifiers_Connection-Graph-Specifiers,graph pattern specifiers>>,
adding connections between component instances in _T_.
Add only connections that are not already present in _T_.
For example, if a command pattern indicates a command
registration connection between two ports, and there is already
a command registration connection between those ports, then
do not add the connection.

===== Checking Telemetry Packet Set Specifiers

FPP checks telemetry packet set specifiers as follows:

. Check that no two telemetry packet set specifiers have
the same name.

. Check that each telemetry packet set specifier is
<<Specifiers_Telemetry-Packet-Set-Specifiers_Semantics,valid>>.

Note that a telemetry packet set specifier is not required.
If there is no specifier, then the topology has no packet definitions.
Note also that two or more telemetry packet set specifiers
are allowed.
Each one specifies a way of assigning the telemetry channels
of the topology to a set of packets.

===== Automatic Numbering of Ports

FPP automatically assigns port numbers as follows.

*Check output port numbers:*
At each output port _p_ of each <<Definitions_Component-Instance-Definitions,
component instance _I_>>, check the following:

. The number of connections is in bounds for the
size of _I_ `.` _p_.

. There is no pair of connections stem:[c_1] and stem:[c_2]
at the same port number of _I_ `.` _p_.
For example, the following pair of connections is not allowed:
+
[source,fpp]
----
a.p[0] -> b.p
a.p[0] -> c.p
----

*Apply matched numbering:*
Assign matching numbers to matched pairs of ports.
For each component instance definition _I_ in the topology:

. Let _C_ be the <<Definitions_Component-Definitions,component definition>> of _I_.

.  For each
<<Specifiers_Port-Matching-Specifiers,port matching specifier>>
`match` stem:[p_1] `with` stem:[p_2] appearing in _C_:

.. For each of _i_ = 1 and _i_ = 2, check that no two distinct connections
at _I_ `.` stem:[p_i] have the same port number assigned to them.

.. Any connection that names _I_ `.` stem:[p_1] or _I_ `.` stem:[p_2]
is *match constrained*. If a match constrained connection is marked
`unmatched` then it is *unmatched*; otherwise it is *matched*.

..  For each matched connection stem:[c_1] with an endpoint at _I_ `.` stem:[p_1]:

... Let _I'_ be the port interface instance at the other endpoint
of stem:[c_1].

... Check that there is one and only one matched connection
stem:[c_2] between _I'_ and _I_ `.` stem:[p_2].

.. Check that the connections stem:[c_2] computed in the previous
step are all the matched connections at _I_ `.` stem:[p_2].

.. For each pair stem:[(c_1,c_2)] computed in step c:

... If stem:[c_1] has a port number stem:[n_1] assigned at _I_ `.` stem:[p_1] and
stem:[c_2] has a port number stem:[n_2] assigned at
_I_ `.` stem:[p_2], then check that stem:[n_1 = n_2].

... Otherwise if stem:[c_1] has a port number _n_ assigned at _I_ `.` stem:[p_1],

.... If no connection at _I_ `.` stem:[p_2] has port number _n_ assigned to it,
then assign _n_ to stem:[c_2] at _I_ `.` stem:[p_2].

.... Otherwise an error occurs.

... Otherwise if stem:[c_2] has a port number _n_ assigned at _I_ `.` stem:[p_2],

.... If no connection at _I_ `.` stem:[p_1] has port number _n_ assigned to it,
then assign _n_ to stem:[c_1] at _I_ `.` stem:[p_1].

.... Otherwise an error occurs.

.. Traverse the pairs stem:[(c_1,c_2)] computed in step c according to the
<<Definitions_Topology-Definitions_Ordering-of-Component-Instance-Connections,
order>> of the connections stem:[c_1], least to greatest.
For each pair stem:[(c_1,c_2)] that does not yet have assigned
port numbers, find the lowest available port number
and assign it at _I_ `.` stem:[p_1] and _I_ `.` stem:[p_2].
A port number _n_ is available if (a) _n_ is in bounds for _I_ `.` stem:[p_1]
and _I_ `.` stem:[p_2]; and (b)
_n_ is not already assigned to a connection at _I_ `.` stem:[p_1]; and (c)
_n_ is not already assigned to a connection at _I_ `.` stem:[p_2].
If no port number is available, then an error occurs.
Note that stem:[p_1] and stem:[p_2]
<<Specifiers_Port-Matching-Specifiers_Semantics,are required to have the
same size for their port arrays>>.

*Apply general numbering:*
Fill in any remaining port numbers.

. Traverse the connections
<<Definitions_Topology-Definitions_Ordering-of-Component-Instance-Connections,
in order>>, least to greatest.

. For each output endpoint _P_ in each connection _C_,
if no port number is already assigned, then assign the lowest available port
number at position _P_.


. For each input endpoint _P_ in each connection _C_, if no port number is
already assigned, then assign the port number zero.

See Example 4 in the <<Definitions_Topology-Definitions_Examples,Examples section>>.

===== Topology Interface

The FPP analyzer checks the topology interface as follows:

. Check that each <<Specifiers_Topology-Port-Instance-Specifiers,topology port 
instance specifier>>
in the topology definition is valid and has a distinct name.

. <<Ports_Port-Interfaces_Topology-Definitions,Compute the port interface>>
_I_ for the topology definition.

. If the optional `implements` keyword is present, then do the
following for each qualified identifier _Q_ that appears
after `implements`:

..  Check that _Q_ 
<<Scoping-of-Names_Resolution-of-Qualified-Identifiers,refers to>> a
<<Definitions_Port-Interface-Definitions,port interface definition>> _D_
with <<Ports_Port-Interfaces_Port-Interface-Definitions,associated port 
interface>> _I'_.

.. Check that _I'_ is a
<<Ports_Sub-Interfaces,sub-interface>> of _I_.

==== Importing Subtopologies

When a topology _T_ has a port interface instance specifier `instance` _Q_
as a member, and _Q_ refers to a topology
_T'_, _T'_ is called a *subtopology* of _T_.
In this case the instances and connections are imported from _T'_ into _T_.

===== Importing Interface Instances

FPP uses the following algorithm to import the port interface instances
of topology _T'_ into topology _T_:

. Let _I_ be the set of
 <<Ports_Port-Interface-Instances,port interface instances>>
of _T_.

. Let _I'_ be the set of <<Ports_Port-Interface-Instances,port interface instances>>
of _T'_.

. Let _I''_ be the set union of _I_ and _I'_.
That means that if either or both of _I_ and _I'_ contain the instance _S_,
then _I''_ contains the instance _S_ once.

===== Importing Connections

FPP uses the following algorithm to import the connections
of topology _T'_ into topology _T_.

. For each
<<Specifiers_Connection-Graph-Specifiers,connection graph name>> stem:[N_i]
that appears in either _T_ or _T'_:

.. Let stem:[G_i] be the connection graph named stem:[N_i] in _T_.
If no such graph exists, then let stem:[G_i] be the empty connection graph
with name stem:[N_i].

.. Let stem:[G'_i] be the connection graph named stem:[N_i] in _T'_.
If no such graph exists, then let stem:[G'_i] be the empty connection graph
with name stem:[N_i].

.. Let stem:[C_i] be the set of
<<Specifiers_Connection-Graph-Specifiers,connections>>
of stem:[G_i].

.. Let stem:[C'_i] be the set of
<<Specifiers_Connection-Graph-Specifiers,connections>>
of stem:[G'_i] such that the connection
is defined by a direct or pattern specifier in _T'_
(i.e., not imported into _T'_ from another topology).

.. Let stem:[C''_i] be the disjoint union of stem:[C_i] and stem:[C'_i].
That means that if stem:[C_i] contains _n_ connections between port
_p_ and port _p'_, and stem:[C'_i] contains _m_ connections between
port _p_ and port _p'_, then stem:[C_i] contains _n + m_ connections
between port _p_ and port _p'_.

.. Let stem:[G''_i] be the connection graph with name stem:[N_i]
and connections stem:[C''_i].

. Return the connection graphs stem:[G''_i].

==== Ordering of Component Instance Connections

For purposes of port numbering, FPP orders connections between
component instances as follows.

*Component instance endpoints:*
A *component instance endpoint* is _I_ `.` _p_ or _I_ `.` _p_ `[` _n_ `]`, where

* _I_ refers to a
<<Definitions_Component-Instance-Definitions,component instance>>.

* _p_ is an identifier that names a port instance specified in
the component definition associated with _I_.

* _n_ is an optional port number.

When a component instance endpoint _e_ has the form _I_ `.` _p_ `[` _n_ `]`,
we say that the endpoint *has source port number* _n_.

Each component instance endpoint has a *fully qualified name*.
The fully qualified name is _Q_ `.` _p_, where _Q_ is the
<<Scoping-of-Names_Names-of-Definitions,fully qualified name>>
of the instance _I_.

FPP orders component instance endpoints stem:[e_1] and stem:[e_2] as follows:

. If the fully qualified name of stem:[e_1] is lexically less
than (respectively greater than) the fully qualified name of
stem:[e_2], then stem:[e_1] is less than (respectively greater than) stem:[e_2].

. Otherwise if stem:[e_1] and stem:[e_2] have source port numbers
port numbers stem:[n_1] and stem:[n_2],
then the ordering of stem:[e_1]
and stem:[e_2] is the same as the numerical ordering of stem:[n_1]
and stem:[n_2].

. Otherwise stem:[e_1] and stem:[e_2] are equal in the ordering.

*Component instance connections:* A *component instance connection* is 
stem:[e_1] `pass:[->]` stem:[e_2],
where stem:[e_1] and stem:[e_2] are component instance endpoints.
FPP orders component instance connections stem:[c_1] and stem:[c_2] as follows:

. Let connection stem:[c_1] be stem:[e_1] `pass:[->]`
stem:[e'_1].

. Let connection stem:[c_2] be stem:[e_2] `pass:[->]`
stem:[e'_2].

. If stem:[e_1] is less than (respectively greater than)
stem:[e_2],
then stem:[c_1] is less than (respectively greater than) stem:[c_2].

. Otherwise if stem:[e'_1] is less than (respectively greater than)
stem:[e'_2], then stem:[c_1] is less than (respectively greater than)
stem:[c_2].

. Otherwise stem:[c_1] and stem:[c_2] are equal in the ordering.

==== Implied Uses

When generating a dictionary from a topology _T_, the analyzer
treats the definition of _T_ as if it contained 
<<Definitions-and-Uses_Implied-Uses, implied uses>> of
several <<Definitions_Framework-Definitions,
framework definitions>> required by the dictionary.
Those framework definitions are specified
in the https://fprime.jpl.nasa.gov/latest/docs/reference/fpp-json-dict/[F Prime
dictionary specification].

==== Examples

*Example 1.*

[source,fpp]
----
@ Command and data handling topology
topology CDH {

  # ----------------------------------------------------------------------
  # Public instances
  # ----------------------------------------------------------------------

  instance commandSequencer
  instance engineeringRateGroup
  instance engineeringTelemetryLogger
  instance engineeringTelemetryConverter
  instance engineeringTelemetrySplitter
  instance eventLogger
  instance rateGroupDriver
  instance telemetryDatabase
  instance timeSource

  # ----------------------------------------------------------------------
  # Connection patterns
  # ----------------------------------------------------------------------

  command connections instance commandDispatcher
  event connections instance eventLogger
  time connections instance timeSource

  # ----------------------------------------------------------------------
  # Connection graphs
  # ----------------------------------------------------------------------

  connections CommandSequences {
    commandSequencer.comCmdOut -> commandDispatcher.comCmdIn
  }

  connections Downlink {
    eventLogger.comOut -> socketGroundInterface.comEventIn
    telemetryDatabase.comOut -> socketGroundInterface.comTlmIn
  }

  connections EngineeringTelemetry {
    commandDispatcher.tlmOut -> engineeringTelemetrySplitter.tlmIn
    commandSequencer.tlmOut -> telemetryDatabase.tlmIn
    engineeringRateGroup.tlmOut -> engineeringTelemetrySplitter.tlmIn
    engineeringTelmetryConverter.comTlmOut -> engineeringTelemetryLogger.comTlmIn
    engineeringTelemetrySplitter.tlmOut -> engineeringTelemetryConverter.tlmIn
    engineeringTelemetrySplitter.tlmOut -> telemetryDatabase.tlmIn
  }

  connections RateGroups {
    engineeringRateGroup.schedOut -> commandSequencer.schedIn
    engineeringRateGroup.schedOut -> telemetryDatabase.schedIn
    rateGroupDriver.cycleOut -> engineeringRateGroup.cycleIn
  }

  connections Uplink {
    socketGroundInterface.comCmdOut -> commandDispatcher.comCmdIn
  }

}
----

*Example 2.*

[source,fpp]
----
@ Attitude control topology
topology AttitudeControl {

  # ----------------------------------------------------------------------
  # Imported topologies
  # ----------------------------------------------------------------------

  instance CDH

  # ----------------------------------------------------------------------
  # Public instances
  # ----------------------------------------------------------------------

  instance acsRateGroup
  instance attitudeControl
  instance socketGroundInterface
  ...

  # ----------------------------------------------------------------------
  # Connection patterns
  # ----------------------------------------------------------------------

  command connections instance commandDispatcher
  event connections instance eventLogger
  time connections instance timeSource


  # ----------------------------------------------------------------------
  # Connection graphs
  # ----------------------------------------------------------------------

  connections AttitudeTelemetry {
    ...
  }

  connections Downlink {
    eventLogger.comOut -> socketGroundInterface.comEventIn
    telemetryDatabase.comOut -> socketGroundInterface.comTlmIn
  }

  connections EngineeringTelemetry {
    acsRateGroup.tlmOut -> engineeringTelemetrySplitter.tlmIn
    ...
  }

  connections RateGroups {
    acsRateGroup.schedOut -> attitudeControl.schedIn
  }

  connections Uplink {
    socketGroundInterface.comCmdOut -> commandDispatcher.comCmdIn
  }

}
----

*Example 3.*

[source,fpp]
----
@ Release topology
topology Release {

  # ----------------------------------------------------------------------
  # Imported topologies
  # ----------------------------------------------------------------------

  instance AttitudeControl
  instance CDH
  instance Communication
  ...

  # Connecting subtopologies together
  connections CDH {
    Communication.uplink -> CDH.dataUp
    CDH.dataDown -> Communication.downlink
  }

}
----

*Example 4.*

[source,fpp]
----
topology A {

  instance a
  instance b
  instance c

  connections C1 {
    a.p1 -> c.p
  }

  connections C2 {
    b.p -> c.p
  }

}

topology B {

  instance A

  instance d
  instance e
  instance f

  connections C1 {
    a.p1 -> d.p
  }

  connections C2 {
    a.p2 -> e.p
  }

  connections C3 {
    a.p3 -> f.p
  }

}
----

After importing, topology `B` is equivalent to this topology:

[source,fpp]
----
topology B {

  instance a
  instance b
  instance c
  instance d
  instance e
  instance f

  connections C1 {
    a.p1 -> c.p
    a.p2 -> d.p
  }

  connections C2 {
    a.p2 -> e.p
  }

  connections C3 {
    a.p3 -> f.p
  }

}
----

Note the following:

* The connections from topologies `A` and `B` are merged graph by graph.

*Example 5.*

Here is the topology that results from automatic numbering of ports
applied to topology `B` in Example 3.

[source,fpp]
----
topology B {

  instance a
  instance c
  instance d
  instance e
  instance f

  connections C1 {
    a.p1[0] -> c.p[0]
    a.p1[1] -> d.p[0]
  }

  connections C2 {
    a.p2[0] -> e.p[0]
  }

  connections C3 {
    a.p3[0] -> f.p[0]
  }

}
----