ki-fingerprint

Reference Implementation of the KI Fingerprint Algorithm

Install the dependencies:

npm install

Run tests:

npm test

Normalise a KI:

node bin/cli normalise < ki.xml or node bin/cli normalise ki.xml

Fingerprint a KI:

node bin/cli fingerprint < ki.xml or node bin/cli fingerprint ki.xml

Concerns with the implementation.

I do not have sufficient knowledge of KI semantics to be able to be confident that this implementation is correct. The particular areas of concern are:

• The inference of variable Context to identify local variables.
• VarString resolution.
• Potentially Semantically equivalent reordering of child nodes.

Let me elaborate.

1. Context Inference

Custom Context Aliases can be created, and some variable declarations have a "LOCAL:" by default context. However I cannot find documentation listing how variable context resolution is achieved. This makes is difficult to perform the static analysis necessary to rename local variables.

2. VarString Resolution

Because VarString can be nested and used as variable variables, it is difficult to ensure consistent renaming of local ones. I don't know how AutoPilot code currently handles this.

3. Node Reordering

This last one is the case of 2 when blocks in looking like:

<When>
    <Var Name="Var1" Mode="exists" />
    <Var Name="AAA" Mode="exists" />
</When>
<!-- and -->
<When>
    <Var Name="AAA" Mode="exists" />
    <Var Name="Var1" Mode="exists" />
</When>

These are functionally equivalent, but not all node rearrangements are. Identifing the case where we can safely reorder nodes is beyond my KI knowledge, but would be important for fingerprinting.