issue-#59 IN function with SETs

[Robert]

There has been some discussion of this topic. In summary:

Robert wrote:

The following code returns TRUE; should it, or is this a bug?

VAR
k : INTEGER
BEGIN
k := 33;
RETURN k IN {1}


Doug wrote:

It appears (via simulation) that all values for
k = 2^n + 1, for n= 5, ..., 31
also return TRUE.

33 IN {1} $TRUE
65 IN {1} $TRUE
129 IN {1} $TRUE
257 IN {1} $TRUE
513 IN {1} $TRUE
1025 IN {1} $TRUE
2049 IN {1} $TRUE
4097 IN {1} $TRUE
8193 IN {1} $TRUE
16385 IN {1} $TRUE
32769 IN {1} $TRUE
65537 IN {1} $TRUE
131073 IN {1} $TRUE
262145 IN {1} $TRUE
524289 IN {1} $TRUE
1048577 IN {1} $TRUE
2097153 IN {1} $TRUE
4194305 IN {1} $TRUE
8388609 IN {1} $TRUE
16777217 IN {1} $TRUE
33554433 IN {1} $TRUE
67108865 IN {1} $TRUE
134217729 IN {1} $TRUE
268435457 IN {1} $TRUE
536870913 IN {1} $TRUE
1073741825 IN {1} $TRUE
-2147483647 IN {1} $TRUE


Robert wrote:

My guess would be that it only considers (k MOD 32), but should it?

Incidentally (k IN {1}) is a compile time error if k is a CONSTant of 33.


Doug wrote:

I've found an example of the thought processes used but not
the inner guts of IN. See Dialog.In

PROCEDURE (VAR s: Selection) In* (index: INTEGER): BOOLEAN, NEW;
BEGIN
IF s.l.items = NIL THEN Init(s.l); s.len := s.l.len END;
IF s.sel # NIL THEN RETURN (index MOD 32) IN (s.sel[index DIV 32]) ELSE RETURN FALSE END
END In;

I agree with you and yes if k is a constant the compiler finds it.
32 < k should fail for k IN set, for all sets.
Now we need to find where in the code MOD 32 operation is
being applied when it shouldn't.


Robert wrote:

Does “fail” mean return FALSE, or TRAP?


Doug wrote:

I think it should be FALSE.

[Robert]

I think that

Code: Select all

k IN set

should TRAP for k < 0, and return FALSE for k >= 32.

I think this behaviour should apply to both CONSTant k and VARiable k.

[luowy]

Hi Robert,

I make a patch for your question:

k IN set

should TRAP for k < 0, and return FALSE for k >= 32.

only the DevCPC486.In procedure modified:

Code: Select all

	PROCEDURE In* (VAR x, y: DevCPL486.Item);
		VAR c:DevCPL486.Item;L1:DevCPL486.Label;
	BEGIN
		IF y.form = Set THEN CheckRange(x, 0, 31) END;
		IF x.mode = Con THEN 
			DevCPL486.GenBitOp(BT, x, y); 
		ELSE 
			L1:=DevCPL486.NewLbl;
			DevCPL486.MakeConst(c, 0, x.form); DevCPL486.GenComp(c, x);
			DevCPL486.GenAssert(ccNS, ranTrap);
			DevCPL486.MakeConst(c, 32, x.form); DevCPL486.GenComp(c, x);
			DevCPL486.GenJump(ccAE,L1,TRUE);
			DevCPL486.GenBitOp(BT, x, y); 
			DevCPL486.SetLabel(L1);
		END;
		Free(x); Free(y);
		SetCC(x, lss, FALSE, FALSE); (* carry set *) 
	END In;

luowy

[Ivan Denisov]

Robert and Luowe, I am suggesting you to try the bug fixing pipeline.

[Robert]

Robert and Luowe, I am suggesting you to try the bug fixing pipeline.

Ok, I accept that comment in principal.

But this is only a potential bug, and wants discussion & concensus before being accepted as an actual bug.

The language report says

x IN s stands for "x is an element of s". x must be an integer in the range 0..MAX(SET), and s of type SET.

(thanks to Gérard Meunier for pointing this out).

Hence our code should not rely on out of range k returning FALSE.

Maybe (and I mean maybe) it would be better to have run time bounds checks to TRAP, and be the same as the compile time checks?

Maybe it would be better (for efficiency reasons) not to have run-time checks?

Maybe it is simply better to leave the compiler as it is and not risk any backward compatibility issues?

[cfbsoftware]

Maybe (and I mean maybe) it would be better to have run time bounds checks to TRAP, and be the same as the compile time checks?

Maybe it would be better (for efficiency reasons) not to have run-time checks?

Maybe it is simply better to leave the compiler as it is and not risk any backward compatibility issues?

1. No.
2. Yes, Yes.
3. YES, YES, YES.

You have the option of programming defensively wherever it might be a real risk e.g.

ASSERT((k >= 0) AND (k <= MAX(SET)));
RETURN k IN {1};

[luowy]

Maybe it is simply better to leave the compiler as it is and not risk any backward compatibility issues?

3. YES, YES, YES.

no runtime error,out of range[0,31] return false.

Code: Select all

       PROCEDURE In* (VAR x, y: DevCPL486.Item);
          VAR c:DevCPL486.Item;L1:DevCPL486.Label;
       BEGIN
          IF y.form = Set THEN CheckRange(x, 0, 31) END;
          IF x.mode = Con THEN
             DevCPL486.GenBitOp(BT, x, y);
          ELSE
             L1:=DevCPL486.NewLbl;
             DevCPL486.MakeConst(c, 32, x.form); DevCPL486.GenComp(c, x);
             DevCPL486.GenJump(ccAE,L1,TRUE);
             DevCPL486.GenBitOp(BT, x, y);
             DevCPL486.SetLabel(L1);
          END;
          Free(x); Free(y);
          SetCC(x, lss, FALSE, FALSE); (* carry set *)
       END In;

does this patch has a risk of any backward compatibility issues?
luowy

[Zinn]

There must be an index out of range trap
as long as the language report says

x IN s stands for "x is an element of s". x must be an integer in the range 0..MAX(SET), and s of type SET.

For example:
We have a trap by accessing arrays a[-1] and a[n+1].
We have a trap in case statement when the case does not exist.
And so on.

Why not here?

[cfbsoftware]

There must be an index out of range trap
as long as the language report says

x IN s stands for "x is an element of s". x must be an integer in the range 0..MAX(SET), and s of type SET.

For example:
We have a trap by accessing arrays x[-1] and x[n+1].
We have a trap in case statement when the case does not exist.
And so on.

Why not here?

I don't agree that There must be an index out of range trap. The action that is taken on errors is up to the implementer of the compiler - that is why such actions are not specified in the report. If there is a problem with BB it is that these actions are not always well documented.
However, there is in fact a trap for this situation but you have to tell the compiler when you compile your code that is what you want. Note that there are several other SET-related cases apart from IN that you might want to trap on e.g.

Code: Select all

i := 99;
IF i IN s THEN END;
s := {0..i};
INCL(s, i);
EXCL(s, i);

If you want SET range errors to be trapped as runtime errors you can compile your source using the compiler option code '+' (i.e. allchecks on). You will then get a value out of range trap when you attempt to run the program. I mentioned one of the ways to do this in an email dated 14 Jun 2006 on the BB mailing list:

http://blackboxframework.org/archive/2006/0822.html

Another way would be to use the CompileModuleList command e.g.

DevCompiler.CompileModuleList TestSet +

where you select the TestSet + part before you execute the command.

[luowy]

then there three options:
1, k<0:runtime trap; k>=32:false

Code: Select all

	PROCEDURE In* (VAR x, y: DevCPL486.Item);
		VAR c:DevCPL486.Item;L1:DevCPL486.Label;
	BEGIN
		(*IF y.form = Set THEN CheckRange(x, 0, 31) END;*)
		IF x.mode = Con THEN 
			DevCPL486.GenBitOp(BT, x, y); 
		ELSE 
			L1:=DevCPL486.NewLbl;
			DevCPL486.MakeConst(c, 0, x.form); DevCPL486.GenComp(c, x); (* <0 *)
			DevCPL486.GenAssert(ccNS, ranTrap);
			DevCPL486.MakeConst(c, 32, x.form); DevCPL486.GenComp(c, x);(* >=32 *)
			DevCPL486.GenJump(ccAE,L1,TRUE); 
			DevCPL486.GenBitOp(BT, x, y); 
			DevCPL486.SetLabel(L1);
		END;
		Free(x); Free(y);
		SetCC(x, lss, FALSE, FALSE); (* carry set *) 
	END In;

2,k out of [0,31]: false

Code: Select all

	PROCEDURE In* (VAR x, y: DevCPL486.Item);
		VAR c:DevCPL486.Item;L1:DevCPL486.Label;
	BEGIN
		(*IF y.form = Set THEN CheckRange(x, 0, 31) END;*)
		IF x.mode = Con THEN 
			DevCPL486.GenBitOp(BT, x, y); 
		ELSE 
			L1:=DevCPL486.NewLbl;
			DevCPL486.MakeConst(c, 32, x.form); DevCPL486.GenComp(c, x);
			DevCPL486.GenJump(ccAE,L1,TRUE);
			DevCPL486.GenBitOp(BT, x, y); 
			DevCPL486.SetLabel(L1);
		END;
		Free(x); Free(y);
		SetCC(x, lss, FALSE, FALSE); (* carry set *) 
	END In;

3, k out of [0,31]: runtime trap

Code: Select all

	PROCEDURE In* (VAR x, y: DevCPL486.Item);
		VAR c:DevCPL486.Item;
	BEGIN
		(*IF y.form = Set THEN CheckRange(x, 0, 31) END;*)
		IF x.mode = Con THEN 
			DevCPL486.GenBitOp(BT, x, y); 
		ELSE 
			DevCPL486.MakeConst(c, 0, x.form); DevCPL486.GenComp(c, x); (* <0*)
			DevCPL486.GenAssert(ccNS, ranTrap);
			DevCPL486.MakeConst(c, 32, x.form); DevCPL486.GenComp(c, x);(* >=32 *)
			DevCPL486.GenAssert(ccB, ranTrap);
			DevCPL486.GenBitOp(BT, x, y); 
		END;
		Free(x); Free(y);
		SetCC(x, lss, FALSE, FALSE); (* carry set *) 
	END In;

which one is better?
I prefer 2