Re: [gforth] ORDER bug

[Anton Ertl]

On Thu, Nov 17, 2011 at 07:07:23PM +0100, Bernd Paysan wrote:
> This here should be better, this checks if the cfa points into the code for 
> primitives or is a code word.  It also give special treatment to aliases 
> (when 
> the alias-mask bit is cleared), and checks if the name consists of printable 
> characters only.
> 
> : new-head? ( addr -- f )
> \G heuristic check whether addr is a name token; may deliver false
> \G positives; addr must be a valid address
>     dup dup aligned <>
>     if
>         drop false exit \ heads are aligned
>     then
>     dup cell+ @ alias-mask and 0= >r
>     name>string dup $20 $1 within if
>         rdrop 2drop false exit \ realistically the name is short
>     then
>     cfaligned 2dup bounds ?do \ should be a printable string
>       i c@ bl < if
>           2drop unloop rdrop false exit
>       then
>     loop
>     + r> if \ check for valid aliases
>       @ dup forthstart here within
>       over ['] noop ['] lit-execute 1+ within or
>       over dup aligned = and
>       0= if
>           drop false exit
>       then
>     then \ check for cfa - must be code field or primitive
>     dup @ tuck 2 cells - = swap
>     docol:  ['] lit-execute @ 1+ within or ;

This works pretty well, and only produces three false positives that
hybrid-head? did not also produce.

I have again applied the idea of checking the link field to this new
head?, resulting in:

: hybrid-head? ( addr -- f )
\G heuristic check whether addr is a name token; may deliver false
\G positives; addr must be a valid address; returns 1 for
\G particularly unsafe positives
    \ we follow the link fields and check for plausibility; two
    \ iterations should catch most false addresses: on the first
    \ iteration, we may get an xt, on the second a code address (or
    \ some code), which is typically not in the dictionary.
    \ we added a third iteration for working with code and ;code words.
    3 0 do
        dup new-head? 0= if
            drop false unloop exit
        endif
        dup @ dup 0= if
            2drop 1 unloop exit
        else
            dup rot forthstart within if
                drop false unloop exit
            then
        then
    loop
    drop true ;

This eliminates the three known false positives.  Now we see:

[~/gforth:76535] gforth xxx.fs -e "hashpop ? testhybrid . cr bye"
2989 3014 

So there are 25 words that are recognized but are not in the hash
table.  Maybe we have that many words in plain linked lists, or maybe
there are still false positives; I did not find any suspicious words
among the recognized ones, though.

Anyway, I have added this method to our HEAD? check.

> This should be a pretty strict test, and at least it won't do any harm to do 
> a 
> .name on it, even if it still is a false positive.

The problem is that the invalid memory access occurred in name>int
(IIRC), which might still trip over a false positive, unless your CFA
test excludes this possibility.

- anton

Here's the test program:

: new-head? ( addr -- f )
\G heuristic check whether addr is a name token; may deliver false
\G positives; addr must be a valid address
    dup dup aligned <>
    if
        drop false exit \ heads are aligned
    then
    dup cell+ @ alias-mask and 0= >r
    name>string dup $20 $1 within if
        rdrop 2drop false exit \ realistically the name is short
    then
    cfaligned 2dup bounds ?do \ should be a printable string
        i c@ bl < if
            2drop unloop rdrop false exit
        then
    loop
    + r> if \ check for valid aliases
        @ dup forthstart here within
        over ['] noop ['] lit-execute 1+ within or
        over dup aligned = and
        0= if
            drop false exit
        then
    then \ check for cfa - must be code field or primitive
    dup @ tuck 2 cells - = swap
    docol:  ['] lit-execute @ 1+ within or ;

: hybrid-head? ( addr -- f )
\G heuristic check whether addr is a name token; may deliver false
\G positives; addr must be a valid address; returns 1 for
\G particularly unsafe positives
    \ we follow the link fields and check for plausibility; two
    \ iterations should catch most false addresses: on the first
    \ iteration, we may get an xt, on the second a code address (or
    \ some code), which is typically not in the dictionary.
    \ we added a third iteration for working with code and ;code words.
    3 0 do
        dup new-head? 0= if
            drop false unloop exit
        endif
        dup @ dup 0= if
            2drop 1 unloop exit
        else
            dup rot forthstart within if
                drop false unloop exit
            then
        then
    loop
    drop true ;

: my-.name ( nt -- )
    name>string dup ." len=" .
    16 min dump ;

: test
    here forthstart do
        i new-head? 0<> i hybrid-head? 0<> over <> if
            cr if
                ." new"
            else
                ." hybrid"
            then
            ."  accepts as head: " i hex. i my-.name
        else
            drop
        then
    loop ;

: testhybrid.
    0 here forthstart do
        i hybrid-head? dup if cr 5 .r space i hex. i .name else drop then
    loop ;

: testhybrid
    0 here forthstart do
        i hybrid-head? 0<> -
    loop ;