issue-#134 interface change not detected

[Josef Templ]

Based on a related (but in a different context) report from Oleg N. Cher I have created
http://redmine.blackboxframework.org/issues/134.

For a specific pattern an interface change is not detected by the compiler.
For example, changing 1 to 2 in the following module is not reported in the log window
as it would be expected.

MODULE Test;
TYPE A* = POINTER TO ARRAY 1 OF CHAR;
END Test.

This is a challenging puzzle.
I think I know a surprisingly simple solution but if anybody else wants to analyze it independently I will
wait with the presentation.

- Josef

[cfbsoftware]

ARRAY 1 OF CHAR is a private anonymous type. Why should the interface change if it changes?

Try it with private / public named types instead and see what happens.

[luowy]

DevCPT.FPrintStr

Code: Select all

...
IF f = Pointer THEN
  strobj := typ.strobj; bstrobj := btyp.strobj;
  IF (strobj = NIL) OR (strobj.name = null) OR (bstrobj = NIL) OR (bstrobj.name = null) THEN
    FPrintStr(btyp); DevCPM.FPrint(pbfp, btyp.idfp(*pbfp*)); pvfp := pbfp
 ...

use "idfp" instead "pbfp", but the comments here confused me.

[Josef Templ]

ARRAY 1 OF CHAR is a private anonymous type. Why should the interface change if it changes?

Try it with private / public named types instead and see what happens.

Note that A is exported. The type of A is shown in the interface.
This information is not private. It can be used in an importing module for accessing
the pointer base type, i.e. the array elements.

- Josef

[Josef Templ]

DevCPT.FPrintStr

Code: Select all

...
IF f = Pointer THEN
  strobj := typ.strobj; bstrobj := btyp.strobj;
  IF (strobj = NIL) OR (strobj.name = null) OR (bstrobj = NIL) OR (bstrobj.name = null) THEN
    FPrintStr(btyp); DevCPM.FPrint(pbfp, btyp.idfp(*pbfp*)); pvfp := pbfp
 ...

use "idfp" instead "pbfp", but the comments here confused me.

good guess but not an explanation what really happens.
It would also change many fingerprints, which must be avoided for 1.7.1.

[cfbsoftware]

Yes - I know that A is exported but I only expected it to be visible (i.e. as a hidden pointer), not that its structure would be known.

So then I tried the following experiment but did not get the result I would have expected:

Code: Select all

MODULE TestAnon;

TYPE 
  A2* = ARRAY 2 OF CHAR;
  A3 = ARRAY 3 OF CHAR;
  
  P2* = POINTER TO A2;
  P3* = POINTER TO A3;

END TestAnon.

MODULE TestAnonClient;

IMPORT TestAnon;

VAR
  a: TestAnon.P2;
  b: TestAnon.P3;
BEGIN
  NEW(a);
  NEW(b);
  a[1] := "x";
  b[1] := "y"
END TestAnonClient.

I thought that the second assignment should fail as A3 is not visible but the compiler allowed it

[luowy]

It would also change many fingerprints, which must be avoided for 1.7.1.

yes,check this one:
DevCPT.FPrintStr

Code: Select all

IF f = Pointer THEN
  strobj := typ.strobj; bstrobj := btyp.strobj;
  IF (strobj = NIL) OR (strobj.name = null) OR (bstrobj = NIL) OR (bstrobj.name = null) THEN
  FPrintStr(btyp); DevCPM.FPrint(pbfp, btyp.pbfp); 
  IF (btyp.comp = Array)&((bstrobj = NIL) OR (bstrobj.name = null)) THEN FPrint(pbfp,btyp.n); END; (* add this line*)
  pvfp := pbfp
  (* else use idfp as pbfp and as pvfp, do not call FPrintStr(btyp) here, else cycle not broken *)
END

[Josef Templ]

even closer.
Can you EXPLAIN what is going on here?

[luowy]

no, the peice of code has a "magic",

Code: Select all

FPrintStruct(btyp); FPrint(pbfp, btyp.pbfp);

it work wired, it stumble me.

[Josef Templ]

My interpretation of the observed anomaly is this:

Background: The compiler uses so-called fingerprints for efficiently comparing
the equality of types (for technical reasons, i.e. avoiding endless recursion
and providing stable results independent from the evaluation order)
it even uses multiple fingerprints per type, an identifier fingerprint idfp (stops on named types),
a public fingerprint pbfp (everything exported), and a private fingerprint pvfp (everything).)
A fingerprint is a 32-bit hash code that results from
applying a function (DevCPM.FPrint) to each structural property of a type
and its elements. By using a 32-bit value it is possible that there are collisions,
i.e. two different types can produce the same fingerprint. This is a rare situation
but in the original ETH Oberon compiler there was some potential and this was well known to ominc.
Therefore they used an improved FPrint function (CRC32, see comment in FPrint)
instead of the original simpler function. This eliminated many collisions, but not all.

In our example, what happens is that we not only have two examples that produce a collision
but a pattern, where every instance produces a collision. The effect of the array length
on the fingerprint calculation is canceled out by the sequence of fingerprint update steps because it is effectively
applied twice and just by accident that effect occurs.
The compiler does not have a real bug. It just happens that there is a pattern that systematically leads to a collision.

Even more surprisingly the same pattern produces a collision also with the original FPrint function of the
ETH Oberon compiler. But not every FPrint function necessarily has this behavior. A very simple function,
INC(fp, val) would not have it in this example. Also a much more complex function such as
SHA would probably not have it.

A simple fix to destroy the pattern is to add a constant before applying btyp.pbfp to pbfp.
Using a constant like 12345 affects a lot of bits and seems to destroy the pattern reliably.
But adding btyp.n also seems to work. Adding btyp.n has the disadvantage that for a reader
of the code it looks as if it is important to use the number of array elements but in fact it is irrelevant.
The number of array elements is already fingerprinted in both pbfp and btyp.pbfp.
It is only a particular bit pattern and FPrint function that cancels the effect of the length in
the result of FPrint(pbfp, btyp.pbfp) unless btyp.pbfp is modified somehow.

Code: Select all

  FPrintStr(btyp); 
  IF (btyp.comp = Array) & ((bstrobj = NIL) OR (bstrobj.name = null)) THEN DevCPM.FPrint(pbfp, btyp.pbfp + 12345)
  ELSE DevCPM.FPrint(pbfp, btyp.pbfp)
  END;
  pvfp := pbfp

- Josef