14. Micro KDM
This chapter describes the foundation for KDM models with precise semantics, referred to as the L1 MICRO KDM compliance point (“micro KDM”).
Let’s use the term KDM “macro Action” to refer to an ActionElement with under specified semantics, whose role in a KDM meta-model is to represent certain existing behavior corresponding to one or more statements in the existing software system. The term “macro action” should not be confused with the preprocessor directives common to certain programming languages.
A KDM “macro action” represents the endpoint of the action relationships, and can own a SourceRef element, which links it to the artifacts of the existing software system. KDM L0 compliance point does not specify the semantics of a KDM “macro action” leaving it u to implementers to design the mapping from the programming languages involved in the artifacts of the existing software systems and KDM.
In order to use the KDM Program Element layer for control- and data-flow analysis applications, as well as for providing more precision for the Resource Layer and the abstraction Layer, additional semantics constraints are required to coordinate producers and consumers of KDM models. The micro KDM compliance point serves this purpose. It constrains the granularity of the leaf action elements, and their meaning by providing the set of micro actions with predefined semantics.
According to the “micro KDM” approach, the original “macro action” is treated as a container that owns certain “micro actions” with predefined semantics and thus precise semantics of the “macro action” is defined. As the result micro KDM constrains the patterns of how to map the statements of the existing system as determined by the programming language into KDM. This is similar to the mapping performed by a compiler into the Java Virtual Machine or Microsoft .NET.
From a compiler technology perspective, KDM micro actions provide the so-called Intermediate Representation (IR) for control and data flow analysis. Micro KDM is a rather high-level IR. Micro KDM actions are aligned with the ISO 11404 datatypes (operations on primitive datatypes and access to complex datatypes) as well as with the KDM patterns for representing program elements.
Separation into a “macro action” and “micro actions” allows:
- the flexibility of selecting the “macro action element” as the point for linking it to the existing artifacts, for example to a source file or to an AST, providing a meaningful source ref (a macro action can still represent one or more statements in the original existing system); and
- provides precise representation of the original “macro action” through a mapping to micro actions with predefined semantics.
Micro actions are the actual endpoints of the KDM relationships. The original “macro action element” (the one that owns the micro actions) aggregates these relationships through the uniform semantics of KDM aggregated relationships. The micro actions fit into the existing flow semantics, which makes it possible to use KDM representations for precise control and data flow analysis.
According to the “encapsulated relationship pattern” of KDM, each action element should own the ActionRelationships that originate from this action element. A KDM relationship originates from an element, if the “from” property of the relationship is equal to the identity of the element. The encapsulated relationship pattern is described in the Code KDM section. The collection of action relationships owned by an element is ordered. From the KDM perspective, the owned ActionRelationships represent the parameters to the action element.
Each micro KDM action has the following 5 parts.
Action Kind, Inputs, Outputs, Control and Extras
- Action Kind – is nature of the operation performed by the micro action. This is represented as a “kind” attribute to the micro action. The action kind may designate certain outgoing relationship as part of the Control. For example, the “call” micro action designated the Calls outgoing relationship as part of Control
- Outputs – represented by the owned outgoing Writes relationship, which usually represents the result of the micro action. This part is optional.
- Inputs – Ordered outgoing Reads and/or Addresses relationships that are owned by the action element, the order of the relationships represent the order of the arguments for a micro action.
- Control part – owned outgoing control flow relationships for the action.
- Extras part – owned relationships other than Reads, Writes and not designated as part of Control by the action Kind. For example, these can be interface compliance relation “CompliesTo” or any extended action relationships.
- every leaf action element of the KDM model should be a micro KDM action, where the operation performed by the action is designated by the value of the action kind, specified in the list of the micro actions in Appendix 1.
- implementers shall capture the meaning of the existing artifacts as determined by the programming languages and runtime platform and map it into connected graphs of micro actions; the meaning of the resulting micro KDM model is determined by the semantics of the micro actions
Semantics of KDM micro actions is defined in Appendix 1. “Semantics of the micro KDM action elements”.
z=1+f(x,y); *d[x+3]=1; d[y+3]=&z; y=*d[x+3];
function foo does not comply to micro KDM semantic constraints;
function bar complies to micro KDM
<?xml version="1.0" encoding="UTF-8"?> <kdm:Segment xmi:version="2.1" xmlns:xmi="http://www.omg.org/XMI" xmlns:action="http://kdm.omg.org/action" xmlns:code="http://kdm.omg.org/code" xmlns:kdm="http://kdm.omg.org/kdm" name="Micro KDM Example"> <model xmi:id="id.0" xmi:type="code:CodeModel"> <codeElement xmi:id="id.1" xmi:type="code:CodeAssembly"> <codeElement xmi:id="id.2" xmi:type="code:CallableUnit" name="foo" kind="regular"> <entryFlow xmi:id="id.3" to="id.4" from="id.2"/> <codeElement xmi:id="id.4" xmi:type="action:ActionElement" name="f1" kind="unknown"> <source xmi:id="id.5" language="C" snippet="z=1+f(x,y)"/> <actionRelation xmi:id="id.6" xmi:type="action:Calls" to="id.107" from="id.4"/> <actionRelation xmi:id="id.7" xmi:type="action:Reads" to="id.97" from="id.4"/> <actionRelation xmi:id="id.8" xmi:type="action:Reads" to="id.98" from="id.4"/> <actionRelation xmi:id="id.9" xmi:type="action:Writes" to="id.99" from="id.4"/> <actionRelation xmi:id="id.10" xmi:type="action:Reads" to="id.105" from="id.4"/> <actionRelation xmi:id="id.11" xmi:type="action:Flow" from="id.4"/> </codeElement> <codeElement xmi:id="id.12" xmi:type="action:ActionElement" name="f2" kind="unknown"> <source xmi:id="id.13" language="C" snippet="*d[x+3]=1;d[y+3]=&z;y=*d[x+3];"/> <actionRelation xmi:id="id.14" xmi:type="action:Reads" to="id.97" from="id.12"/> <actionRelation xmi:id="id.15" xmi:type="action:Addresses" to="id.100" from="id.12"/> <actionRelation xmi:id="id.16" xmi:type="action:Reads" to="id.106" from="id.12"/> <actionRelation xmi:id="id.17" xmi:type="action:Reads" to="id.105" from="id.12"/> <actionRelation xmi:id="id.18" xmi:type="action:Addresses" to="id.100" from="id.12"/> <actionRelation xmi:id="id.19" xmi:type="action:Reads" to="id.98" from="id.12"/> <actionRelation xmi:id="id.20" xmi:type="action:Reads" to="id.106" from="id.12"/> <actionRelation xmi:id="id.21" xmi:type="action:Addresses" to="id.99" from="id.12"/> <actionRelation xmi:id="id.22" xmi:type="action:Writes" to="id.98" from="id.4"/> <actionRelation xmi:id="id.23" xmi:type="action:Addresses" to="id.100" from="id.12"/> <actionRelation xmi:id="id.24" xmi:type="action:Reads" to="id.97" from="id.12"/> <actionRelation xmi:id="id.25" xmi:type="action:Reads" to="id.106" from="id.12"/> </codeElement> </codeElement> <codeElement xmi:id="id.26" xmi:type="code:CallableUnit" name="bar" kind="regular"> <entryFlow xmi:id="id.27" to="id.28" from="id.26"/> <codeElement xmi:id="id.28" xmi:type="action:ActionElement" name="b1" kind="compound"> <source xmi:id="id.29" language="C" snippet="z=1+f(x,y)"/> <codeElement xmi:id="id.30" xmi:type="code:StorableUnit" name="t1" type="id.112" kind="register"/> <codeElement xmi:id="id.31" xmi:type="action:ActionElement" name="b1.1" kind="Call"> <actionRelation xmi:id="id.32" xmi:type="action:Calls" to="id.107" from="id.28"/> <actionRelation xmi:id="id.33" xmi:type="action:Reads" to="id.97" from="id.28"/> <actionRelation xmi:id="id.34" xmi:type="action:Reads" to="id.98" from="id.28"/> <actionRelation xmi:id="id.35" xmi:type="action:Writes" to="id.30" from="id.31"/> <actionRelation xmi:id="id.36" xmi:type="action:Flow" from="id.31"/> </codeElement> <codeElement xmi:id="id.37" xmi:type="action:ActionElement" name="b1.2" kind="Add"> <actionRelation xmi:id="id.38" xmi:type="action:Reads" to="id.105" from="id.37"/> <actionRelation xmi:id="id.39" xmi:type="action:Reads" to="id.30" from="id.37"/> <actionRelation xmi:id="id.40" xmi:type="action:Writes" to="id.99" from="id.37"/> </codeElement> <actionRelation xmi:id="id.41" xmi:type="action:Flow" to="id.31" from="id.28"/> </codeElement> <codeElement xmi:id="id.42" xmi:type="action:ActionElement" name="b2" kind="compound"> <source xmi:id="id.43" language="C" snippet="*d[x+3]=1;d[y+3]=&z;y=*d[x+3];"/> <codeElement xmi:id="id.44" xmi:type="code:StorableUnit" name="t2" type="id.103" kind="register"/> <codeElement xmi:id="id.45" xmi:type="code:StorableUnit" name="t3" type="id.112" kind="register"/> <codeElement xmi:id="id.46" xmi:type="code:StorableUnit" name="t4" type="id.112" kind="register"/> <codeElement xmi:id="id.47" xmi:type="code:StorableUnit" name="t5" type="id.103" kind="register"/> <codeElement xmi:id="id.48" xmi:type="code:StorableUnit" name="t6" type="id.112" kind="register"/> <codeElement xmi:id="id.49" xmi:type="code:StorableUnit" name="t7" type="id.103" kind="register"/> <codeElement xmi:id="id.50" xmi:type="action:ActionElement" name="b2.1" kind="Add"> <actionRelation xmi:id="id.51" xmi:type="action:Reads" to="id.97" from="id.50"/> <actionRelation xmi:id="id.52" xmi:type="action:Reads" to="id.106" from="id.50"/> <actionRelation xmi:id="id.53" xmi:type="action:Writes" to="id.44" from="id.50"/> <actionRelation xmi:id="id.54" xmi:type="action:Flow" to="id.55" from="id.50"/> </codeElement> <codeElement xmi:id="id.55" xmi:type="action:ActionElement" name="b2.2" kind="ArraySelect"> <actionRelation xmi:id="id.56" xmi:type="action:Addresses" to="id.100" from="id.55"/> <actionRelation xmi:id="id.57" xmi:type="action:Reads" to="id.102" from="id.55"/> <actionRelation xmi:id="id.58" xmi:type="action:Reads" to="id.44" from="id.55"/> <actionRelation xmi:id="id.59" xmi:type="action:Writes" to="id.45" from="id.55"/> <actionRelation xmi:id="id.60" xmi:type="action:Flow" from="id.55"/> </codeElement> <codeElement xmi:id="id.61" xmi:type="action:ActionElement" name="b2.3" kind="PtrReplace"> <actionRelation xmi:id="id.62" xmi:type="action:Reads" to="id.45" from="id.61"/> <actionRelation xmi:id="id.63" xmi:type="action:Reads" to="id.105" from="id.61"/> <actionRelation xmi:id="id.64" xmi:type="action:Writes" to="id.104" from="id.61"/> <actionRelation xmi:id="id.65" xmi:type="action:Flow" to="id.66" from="id.61"/> </codeElement> <codeElement xmi:id="id.66" xmi:type="action:ActionElement" name="b2.4" kind="Add"> <actionRelation xmi:id="id.67" xmi:type="action:Reads" to="id.98" from="id.12"/> <actionRelation xmi:id="id.68" xmi:type="action:Reads" to="id.106" from="id.12"/> <actionRelation xmi:id="id.69" xmi:type="action:Writes" to="id.46" from="id.66"/> <actionRelation xmi:id="id.70" xmi:type="action:Flow" to="id.71" from="id.66"/> </codeElement> <codeElement xmi:id="id.71" xmi:type="action:ActionElement" name="b2.5" kind="Ptr"> <actionRelation xmi:id="id.72" xmi:type="action:Addresses" to="id.99" from="id.12"/> <actionRelation xmi:id="id.73" xmi:type="action:Writes" to="id.47" from="id.71"/> <actionRelation xmi:id="id.74" xmi:type="action:Flow" to="id.75" from="id.71"/> </codeElement> <codeElement xmi:id="id.75" xmi:type="action:ActionElement" name="b2.6" kind="ArrayReplace"> <actionRelation xmi:id="id.76" xmi:type="action:Addresses" to="id.100" from="id.12"/> <actionRelation xmi:id="id.77" xmi:type="action:Reads" to="id.46" from="id.75"/> <actionRelation xmi:id="id.78" xmi:type="action:Reads" to="id.47" from="id.75"/> <actionRelation xmi:id="id.79" xmi:type="action:Writes" to="id.102" from="id.75"/> <actionRelation xmi:id="id.80" xmi:type="action:Flow" from="id.75"/> </codeElement> <codeElement xmi:id="id.81" xmi:type="action:ActionElement" name="b2.7" kind="Add"> <actionRelation xmi:id="id.82" xmi:type="action:Reads" to="id.97" from="id.12"/> <actionRelation xmi:id="id.83" xmi:type="action:Reads" to="id.106" from="id.12"/> <actionRelation xmi:id="id.84" xmi:type="action:Writes" to="id.48" from="id.81"/> <actionRelation xmi:id="id.85" xmi:type="action:Flow" from="id.81"/> </codeElement> <codeElement xmi:id="id.86" xmi:type="action:ActionElement" name="b2.8" kind="ArraySelect"> <actionRelation xmi:id="id.87" xmi:type="action:Addresses" to="id.100" from="id.12"/> <actionRelation xmi:id="id.88" xmi:type="action:Reads" to="id.48" from="id.86"/> <actionRelation xmi:id="id.89" xmi:type="action:Reads" to="id.102" from="id.86"/> <actionRelation xmi:id="id.90" xmi:type="action:Writes" to="id.49" from="id.86"/> <actionRelation xmi:id="id.91" xmi:type="action:Flow" to="id.92" from="id.86"/> </codeElement> <codeElement xmi:id="id.92" xmi:type="action:ActionElement" name="b2.9" kind="PtrSelect"> <actionRelation xmi:id="id.93" xmi:type="action:Reads" to="id.49" from="id.92"/> <actionRelation xmi:id="id.94" xmi:type="action:Reads" to="id.104" from="id.92"/> <actionRelation xmi:id="id.95" xmi:type="action:Writes" to="id.98" from="id.92"/> </codeElement> <actionRelation xmi:id="id.96" xmi:type="action:Flow" to="id.50" from="id.42"/> </codeElement> </codeElement> <codeElement xmi:id="id.97" xmi:type="code:StorableUnit" name="x" type="id.112"/> <codeElement xmi:id="id.98" xmi:type="code:StorableUnit" name="y" type="id.112"/> <codeElement xmi:id="id.99" xmi:type="code:StorableUnit" name="z" type="id.112"/> <codeElement xmi:id="id.100" xmi:type="code:StorableUnit" name="d" type="id.101"> <codeElement xmi:id="id.101" xmi:type="code:ArrayType" name=""> <itemUnit xmi:id="id.102" name="d[]" type="id.103"> <codeElement xmi:id="id.103" xmi:type="code:PointerType"> <itemUnit xmi:id="id.104" name="*d[]" type="id.112"/> </codeElement> </itemUnit> </codeElement> </codeElement> <codeElement xmi:id="id.105" xmi:type="code:Value" name="1" type="id.112"/> <codeElement xmi:id="id.106" xmi:type="code:Value" name="3" type="id.112"/> <codeElement xmi:id="id.107" xmi:type="code:CallableUnit" name="f" type="id.108"> <codeElement xmi:id="id.108" xmi:type="code:Signature"> <parameterUnit xmi:id="id.109" name="a" type="id.112" pos="1"/> <parameterUnit xmi:id="id.110" name="b" type="id.112" pos="2"/> <parameterUnit xmi:id="id.111" type="id.112" kind="return"/> </codeElement> </codeElement> </codeElement> <codeElement xmi:id="id.112" xmi:type="code:IntegerType" name="int"/> </model> </kdm:Segment>