Anubis / Anubis

                            The Anubis Project. 
                            
                     An efficient find and replace tool. 

   Author: Alain Prouté 2015/07/15


   *** Introduction.
   
   This file contains a 'multiple find and replace' tool. By 'multiple'
   we mean that we use a dictionary in the form of a list of pairs (key,value)
   and that the occurrences of any key are replaced (within a given text) by 
   the corresponding value. 
   
   A key can be part of another key, but the function replaces the longuest
   possible occurrence. For example, if 'ab' and abc' are two keys in the 
   dictionary, and if the text contains 'abc', the function replaces 'abc' 
   by the corresponding value, not 'ab'.
   
   In order to be efficient, we compile the dictionary into an automaton
   and the automaton is executed by a syscall (defined in predefined.anubis) 
   on the given text. The dictionary can be compiled in advance and the 
   automaton used any number of times. 
   
   The purpose of the program in this file is mainly to compile the dictionary
   into an automaton. The find and replace operation itself is performed by the
   syscall. 
   
   
   *** Dictionaries. 
   
   The type below defines a single entry in the dictionary. It is designed so that
   you can put either a String or a ByteArray as the key and/or the value. 
   
public type FR_DictEntry:    
   entry (String      key,    String       value), 
   entry (String      key,    ByteArray    value), 
   entry (ByteArray   key,    String       value), 
   entry (ByteArray   key,    ByteArray    value).  
   
   The dictionary itself is of type 'List(FR_DictEntry)'. 
   
   
   *** Compiling a dictionary. 
   
   The result of compiling a dictionary is a datum of type 'FR_CompiledDict'.   
   
public type FR_CompiledDict:...      (an opaque type)
   
   You can compile your dictionary as follows: 
   
public define FR_CompiledDict
   compile
   (
      List(FR_DictEntry)   dictionary
   ). 
   
   The type 'FR_CompiledDict' is serializable. Hence you can store the automaton
   into a file or transmit it over the network, etc...
   
   
   *** Finding and replacing.
   
   Once your dictionary is commpiled, you can use it for performing 'find and replace'
   operations by using one of:
   
public define macro String       find_and_replace(FR_CompiledDict dict,   String     text).   
public define macro String       find_and_replace(FR_CompiledDict dict,   ByteArray  text).   
public define macro ByteArray    find_and_replace(FR_CompiledDict dict,   String     text).   
public define macro ByteArray    find_and_replace(FR_CompiledDict dict,   ByteArray  text).   
   
   These fonctions are deterministic, because the 'text' is not altered. The result
   is always a new datum. This is why we can call them 'functions' (by opposition
   to 'commands'). 

   
   *** Using this tool with streams. 
   
   It can be convenient to use this tool with streams (files, connections,...) instead
   of strings or byte arrays. For example, you may want to copy a file into another one, 
   or into a network connection, replacing keys by values. To that end, we provide
   the following:
                    
read tools/connections.anubis
   
public define Bool         find_and_replace(FR_CompiledDict   dict, 
                                            Connection        source, 
                                            Connection        target, 
                                            Int               chunk_size). 
                    
   which returns true if no error occured. 
   
   This command will do the job by reading the source connection by chunks of size 
   'chunk_size'. Of course, it is writen in such a way that it handles correctly
   keys which span across two consecutive chunks.
   
                    
   *** Remarks. 
   
   The syscalls which performs the find and replace operation use Boyer-Moore-like 
   techniques for searching. We have tried to produce a tool as efficient in speed 
   as possible. 
   
   
   
   
   --- That's all for the public part ! -----------------------------------------
   
   
read tools/basis.anubis   
   

   *** Uniform dictionary entry suitable for our computations. 
   
type DictE:
   e(List(Word8)    key, 
     ByteArray      value). 
     
     
   *** Transformation of the original dictionary.   
     
define List(Word8)
   explode
   (
      ByteArray   ba,
      Int         i,
      Int         n, 
      List(Word8) so_far
   ) =
   if i > n then reverse(so_far) else
   if nth(i,ba) is 
   {
     failure    then reverse(so_far), 
     success(c) then explode(ba,i+1,n,[c . so_far])
   }. 
     
   
   The entries must be sorted by increasing key length. 
     
define List(DictE)
   to_Dict
   (
       List(FR_DictEntry)   d
   ) =
   with sd = map((FR_DictEntry en) |-> if en is 
          {
             entry(k,v) then e(explode(k),to_byte_array(v)), 
             entry(k,v) then e(explode(k),v), 
             entry(k,v) then e(explode(k,0,length(k),[]),to_byte_array(v)), 
             entry(k,v) then e(explode(k,0,length(k),[]),v)
          },d), 
   merge_sort(sd,(DictE e1, DictE e2) |-> length(key(e1)) < length(key(e2))). 
     
          
          
     
   *** Formal automaton (first form). 
   
type AutoState1:
   init        (Word16       id, 
                Word16       jmp, 
                Word16       next_state), 
   reject      (Word16       id, 
                Word16       disp, 
                Word8        char, 
                Word16       jmp_match,
                Word16       next_match, 
                Word16       jmp_nomatch,
                Word16       next_nomatch), 
   accept      (Word16       id, 
                Word16       kid,               // key identifier
                Word16       disp, 
                Word8        char, 
                Word16       jmp_nomatch,
                Word16       next_nomatch),
   reject_exit (Word16       id, 
                Word16       disp, 
                Word8        char, 
                Word16       jmp_match,
                Word16       next_match), 
   accept_exit (Word16       id, 
                Word16       kid,
                Word16       disp, 
                Word8        char).    
                
                
   
                
   *** Single key automaton. 
   
define (
          List(AutoState1),       // the automaton
          Word16                  // next available state id
       )
   single_key_auto_aux
   (
     Word16         id,           // first available state id
     Word16         kid, 
     List(Word8)    key,
     Word16         disp
   ) =
   if key is 
   {
     [ ]      then ([ ],id),  
     [h . t]  then 
       since single_key_auto_aux(id+1,kid,t,disp-1) is (rest,next_id), 
       ([
          if t is [ ] 
          then accept_exit(id,kid,disp,h)
          else reject_exit(id,disp,h,-1,id+1)
          . rest], next_id)
   }.
                
   
   Some convenience functions for mixed Int/Word16 arithmetics: 
   
define Word16 truncate(Int n) = low(truncate_to_Word32(n)).   
define Word16   Int n + Word16 w = truncate(n)+w. 
define Word16   Int n - Word16 w = truncate(n)-w. 
                

   Making a type 1 single key automaton. 

define (
          List(AutoState1),       // the automaton
          Word16                  // next available state id
       )
   single_key_auto
   (
     Word16         id,           // first available state id
     Word16         kid,          // key identifier
     List(Word8)    key
   ) =
   since single_key_auto_aux(id+1,kid,reverse(key),length(key)-1) is (auto,next_id), 
   ([init(id,length(key)-1,id+1) . auto],next_id). 
                
           
   
   *** Many keys automaton. 
   
   
define AutoState1 -> AutoState1
   glue_state   
   (
     Word16    target_id, 
     Word16    init_disp
   ) =
   (AutoState1 s) |-> 
     if s is 
     {
       init(id,jmp,next_state)  then 
         s,
       reject(id,disp,char,jmp_match,next_match,jmp_nomatch,next_nomatch)  then 
         s,
       accept(id,kid,disp,char,jmp_nomatch,next_nomatch)  then 
         s, 
       reject_exit(id,disp,char,jmp_match,next_match)  then 
         reject(id,disp,char,jmp_match,next_match,init_disp-disp,target_id),
       accept_exit(id,kid,disp,char)  then 
         accept(id,kid,disp,char,init_disp-disp,target_id)
     }. 
   
define (
          Word16,   // id
          Word16,   // initial displacement
          Word16    // next state
       )
  init_state
  (
    List(AutoState1)   l
  ) = 
  if l is 
  {
    [ ] then should_not_happen((0,0,0)), 
    [h . t] then 
      if h is init(id,j,n) then (id,j,n)
      else init_state(t)
  }.
     
     
   Glueing a many keys automaton on a single key automaton. 
   
define List(AutoState1)
   glue_auto
   (
     List(AutoState1)    auto_many,
     List(AutoState1)    auto_single
   ) =
   since init_state(auto_single) is (id,disp,next), 
   map(glue_state(next,disp),auto_many) + auto_single. 
   
define (
          List(AutoState1),        // the automaton
          Word16                   // next available state id
       ) 
   many_keys_auto
   (
     Word16               id,            // first available id
     List(List(Word8))    keys, 
     Word16               kid_count      // this is where we put ids for keys (kid = key identifier)
   ) = 
   if keys is
   {
     [ ] then ([ ],id), 
     [key1 . others] then 
       since single_key_auto(id,kid_count,key1) is (auto1,id1), 
       since many_keys_auto(id1,others,kid_count+1) is (auto_rest,next_id), 
       (glue_auto(auto_rest,auto1), next_id)
   }.
   
   
   
   
   *** Formal automaton (second form). 
   
type PatternChar:               // a character at a given position
  known  (Word8     char,
          Word16    disp). 
   
define List(PatternChar)
   add
   (
     Word8                char, 
     Word16               disp,
     List(PatternChar)    pattern
   ) =
   with e = known(char,disp), 
   if e:pattern
   then pattern
   else [e . pattern]. 
          
   
type AutoState2:
   init        (Word16               id, 
                List(PatternChar)    pattern, 
                Word16               jmp, 
                Word16               next_state), 
   reject      (Word16               id, 
                List(PatternChar)    pattern, 
                Word16               disp, 
                Word8                char, 
                Word16               jmp_match,
                Word16               next_match, 
                Word16               jmp_nomatch,
                Word16               next_nomatch), 
   accept      (Word16               id, 
                Word16               kid,
                List(PatternChar)    pattern, 
                Word16               disp, 
                Word8                char, 
                Word16               jmp_nomatch,
                Word16               next_nomatch),
   reject_exit (Word16               id, 
                List(PatternChar)    pattern, 
                Word16               disp, 
                Word8                char, 
                Word16               jmp_match,
                Word16               next_match), 
   accept_exit (Word16               id, 
                Word16               kid,
                List(PatternChar)    pattern, 
                Word16               disp, 
                Word8                char).    
                
 
define AutoState1
   by_id
   (
     List(AutoState1)   l, 
     Word16             i
   ) =
   if l is 
   {
     [ ] then should_not_happen(init(0,0,0)), 
     [h . t] then 
       if id(h) = i then h else by_id(t,i)
   }.
                
   
   
define (
          List(AutoState2),     // resulting tree
          Word16                // next available state id
       )
   unfold
   (
     List(AutoState1)     auto,
     AutoState1           root,
     Word16               root_id,
     List(PatternChar)    pattern
   ) =
   if root is 
   {
     init(id,jmp,next_state)  then 
       if unfold(auto,by_id(auto,next_state),root_id+1,pattern) is (tree,next_id) then 
       ([init(root_id,pattern,jmp,root_id+1)
         . tree],next_id),  
       
     reject(id,disp,char,jmp_match,next_match,jmp_nomatch,next_nomatch)  then 
       if unfold(auto,by_id(auto,next_match),root_id+1,add(char,disp,pattern)) is (left,nid1) then  
       if unfold(auto,by_id(auto,next_nomatch),nid1,pattern) is (right,nid2) then 
       ([reject(root_id,pattern,disp,char,jmp_match,root_id+1,
                     jmp_nomatch,nid1)
         . left+right], nid2), 
     
     accept(id,kid,disp,char,jmp_nomatch,next_nomatch)  then 
       if unfold(auto,by_id(auto,next_nomatch),root_id+1,pattern) is (right,nid1) then 
       ([accept(root_id,kid,pattern,disp,char,jmp_nomatch,root_id+1)
         . right], nid1), 
     
     reject_exit(id,disp,char,jmp_match,next_match)  then 
       if unfold(auto,by_id(auto,next_match),root_id+1,add(char,disp,pattern)) is (left,nid1) then 
       ([reject_exit(root_id,pattern,disp,char,jmp_match,root_id+1)
         . left], nid1), 
     
     accept_exit(id,kid,disp,char)  then    
       ([accept_exit(root_id,kid,pattern,disp,char)],root_id+1)
   }. 
   
   
define Maybe(Word8)
   find
   (
     Word16              d,
     List(PatternChar)   l
   ) =  
   if l is 
   {
     [ ] then failure, 
     [h . t] then if h is known(c,d1) then 
       if d = d1
       then success(c)
       else find(d,t)
   }.

   
   
   
define Bool      // tests if a key can match part of a pattern 
   can_match_at
   (
     List(PatternChar)    pattern,
     List(Word8)          key,
     Word16               i      // starting position in pattern
   ) =
   if key is 
   {
     [ ]           then true, 
     [c . others]  then if find(i,pattern) is 
       {
         failure      then can_match_at(pattern,others,i+1), 
         success(c1)  then if c = c1
                           then can_match_at(pattern,others,i+1)
                           else false
       }
   }.
   
   
define Word16
   pattern_jmp1
   (
     List(PatternChar)         pattern,
     List(Word8)               key, 
     Word16                    i
   ) =
   if can_match_at(pattern,key,i)
   then i
   else pattern_jmp1(pattern,key,i+1). 
   
define macro Word16 
   unsigned_min
   (
     Word16    x, 
     Word16    y
   ) =
   if x +< y then x else y. 
   
define Word16
   pattern_jmp
   (
     List(PatternChar)          pattern, 
     List(List(Word8))          keys, 
     Word16                     max
   ) =
   if keys is
   {
     [ ] then max, 
     [h . t] then 
       unsigned_min(pattern_jmp1(pattern,h,1),pattern_jmp(pattern,t,max))
   }.
   
   
define Word16
   max_key_length
   (
     List(List(Word8))   keys
   ) =
   truncate(max(map(length,keys),0)).
   
   
   
   
   *** Formal automaton (third form). 
   
type AutoState3:
   init         (Word16              id, 
                 Word16              jmp, 
                 Word16              next), 
   accept       (Word16              id,
                 Word16              kid,
                 Word8               char,
                 Word16              jmp_nomatch,
                 Word16              next_nomatch),
   continue     (Word16              id,
                 Word8               char,
                 Word16              jmp_match,
                 Word16              next_match,
                 Word16              jmp_nomatch,
                 Word16              next_nomatch).

   
define (
          Word16       id, 
          Word16       jmp,
          Word16       next 
       )
   init_state_info
   (
     List(AutoState2)   l
   ) =
   if l is 
   {
     [ ] then should_not_happen((0,0,0)),
     [h . t] then if h is init(id,_,j,n) 
                  then (id,j,n)
                  else init_state_info(t)
   }.
                 
   

define List(AutoState3)
   finalize_aux
   (
     List(AutoState2)   auto,
     Word16             initial_jmp,
     Word16             after_init_state,
     List(List(Word8))  keys,
     Word16             max
   ) =
   if auto is 
   {
     [ ] then [ ], 
     [h . t] then [if h is 
       {
         init(id,pattern,jmp,next_state)  then 
           init(id,jmp,next_state), 
           
         reject(id,pattern,disp,char,jmp_match,next_match,jmp_nomatch,next_nomatch)  then 
           continue(id,char,jmp_match,next_match,jmp_nomatch,next_nomatch), 
           
         accept(id,kid,pattern,disp,char,jmp_nomatch,next_nomatch)  then 
           accept(id,kid,char,jmp_nomatch,next_nomatch), 
         
         reject_exit(id,pattern,disp,char,jmp_match,next_match)  then
           continue(id,
                    char,
                    jmp_match,
                    next_match,
                    pattern_jmp(pattern,keys,max)+initial_jmp,
                    after_init_state), 
         
         accept_exit(id,kid,pattern,disp,char)  then 
           accept(id,
                  kid,
                  char,
                  pattern_jmp(pattern,keys,max)+initial_jmp,
                  after_init_state)
       } . finalize_aux(t,initial_jmp,after_init_state,keys,max)]
   }.

   
define List(AutoState3)
   finalize
   (
     List(AutoState2)   auto,
     List(List(Word8))  keys
   ) =                 
   if init_state_info(auto) is (_,j,n) then finalize_aux(auto,j,n,keys,max_key_length(keys)). 
   
   
   
   
   *** Encoded automaton. 
   
   We now encode a type 3 automaton into a byte array. Each state is encoded as a sequence
   of 12 bytes as follows: 
   
           +----+----+---------+---------+---------+---------+---------+
           | st | ch |   kid   |    jm   |   nm    |   jnm   |   nnm   | 
           +----+----+---------+---------+---------+---------+---------+
  offset:  0    1    2         4         6         8         10           
   
  where:    st    (1 byte)  (state type)           0 = continue, 1 = accept (init is continue)
            ch    (1 byte)  (character)   
            kid   (2 bytes) (key identifier)       meaningful only for accepting states
            jm    (2 bytes) (jump if match)        number of bytes of jump in the text if character matches
            nm    (2 bytes) (next if match)        next state if character matches
            jnm   (2 bytes) (jump if no match)     number of bytes of jump in the text if character does'nt match
            nnm   (2 bytes) (next if match)        next state if character does'nt match
            
   The character is not meaningful for the initial state, but we dont have to worry about that because
   in this state (coded as a 'continue' state) jm = jnm and nm = nnm. 
   
   
define One 
   put16
     (
       ByteArray   ba, 
       Int         i,   // position mesured in bytes from beginning of byte array
       Word16      w
     ) =
   if w is word16(b0,b1) then 
   if system_endianness is 
     {
       little_endian then 
         forget(put(ba,i,b0));
         forget(put(ba,i+1,b1)),
       big_endian then 
         forget(put(ba,i,b1));
         forget(put(ba,i+1,b0))
     }. 
     
define One 
   put32
     (
       ByteArray   ba, 
       Int         i,   // position mesured in bytes from beginning of byte array
       Word32      w
     ) =
   if w is word32(low16,high16) then 
   if low16  is word16(b0,b1) then 
   if high16 is word16(b2,b3) then 
   if system_endianness is 
     {
       little_endian then 
         forget(put(ba,i,b0));
         forget(put(ba,i+1,b1));
         forget(put(ba,i+2,b2));
         forget(put(ba,i+3,b3)),
       big_endian then 
         forget(put(ba,i,b3));
         forget(put(ba,i+1,b2));
         forget(put(ba,i+2,b1));
         forget(put(ba,i+3,b0))
     }. 
     

define One 
   put
   (
     ByteArray b, 
     Int       i, 
     Word8     c
   ) =
   forget((Maybe(One))put(b,i,c)).
   
define ByteArray
   encode_aux
   (
      List(AutoState3) l, 
      Int              i,   // writing index
      ByteArray        result
   ) =
   if l is 
   {
     [ ] then result, 
     [h . t] then 
       if h is 
			 {
				 init(id,jmp,next)  then
					 put(result,i,0);         // 'continue'
					 put(result,i+1,'*');     // dummy char
					 // no kid
					 put16(result,i+4,jmp); 
					 put16(result,i+6,next);
					 put16(result,i+8,jmp); 
					 put16(result,i+10,next), 
					 
				 accept(id,kid,char,jmp_nomatch,next_nomatch)  then 
					 put(result,i,1);         // 'accept'
					 put(result,i+1,char);                        
					 put16(result,i+2,kid); 
					 // no jmp
					 // no next
					 put16(result,i+8,jmp_nomatch); 
					 put16(result,i+10,next_nomatch), 
				 
				 continue(id,char,jmp_match,next_match,jmp_nomatch,next_nomatch)  then 
					 put(result,i,0);         // 'continue'
					 put(result,i+1,char);                        
					 // no kid 
					 put16(result,i+4,jmp_match); 
					 put16(result,i+6,next_match); 
					 put16(result,i+8,jmp_nomatch); 
					 put16(result,i+10,next_nomatch) 
			 }; 
			 encode_aux(t,i+12,result)
   }.
   
   
define ByteArray
   encode
   (
      List(AutoState3) l
   ) =   
   with result = constant_byte_array(12*length(l),0), 
   encode_aux(l,0,result). 
   
   
   
   *** Making the array of values. 
   
   The syscall 'find_and_replace' takes as arguments:
   
      - the encoded automaton constructed above, 
      - an array of values
      - the text where keys are to be replaced by values. 
      
   The array of values is a byte array constructed as follows: 
   
   offset   |   size   |  type    |  content
   -------------------------------------------------------------------------------
   0        |     2    | Word16   | number of entries  (denoted as 'n' below)
   2        |    4*n   | Word32s  | offsets of entries
   4n+2     |     4    | Word32   | size of first value (denoted as 's1' below)
   4n+6     |    s1    | Word8s   | first value
   and similarly for other values ...
   
   
define Int    // offset for first value
   put_offsets
   (
     ByteArray         result, 
     List(ByteArray)   values, 
     Int               i,         // position of pointer
     Int               offset     // value of pointer
   ) = 
   if values is 
   {
     [ ] then i, 
     [h . t] then 
        put32(result,i,truncate_to_Word32(offset)); 
        put_offsets(result,t,i+4,offset+4+length(h))
   }. 
   
define One
   copy_bytes
   (
     ByteArray     source, 
     ByteArray     dest, 
     Int           offset,     // in dest
     Int           i
   ) =
   if nth(i,source) is 
   {
     failure then unique, 
     success(c) then 
       put(dest,offset+i,c); 
       copy_bytes(source,dest,offset,i+1)
   }.
   
define One
   put_values
   (
     ByteArray          result, 
     List(ByteArray)    values,
     Int                offset
   ) =
   if values is 
   {
     [ ] then unique, 
     [h . t] then 
       with l = length(h), 
       put32(result,offset,truncate_to_Word32(l)); 
       copy_bytes(h,result,offset+4,0); 
       put_values(result,t,offset+4+l)
   }.
   
define ByteArray
   array_of_values
   (
      List(ByteArray)   values
   ) =
   with     size_vals = sum(map(length,values)),
               n_vals = length(values), 
          result_size = 2 + 8*n_vals + size_vals, 
               result = constant_byte_array(result_size,0),
      put16(result,0,truncate(n_vals));                        // number of entries
      with j = put_offsets(result,values,2,4*n_vals+2),      // table of offsets
      put_values(result,values,j);                           // values
      result. 
               
   

   *** Creating a 'FR_CompliedDict' from a user dictionary. 
   
public type FR_CompiledDict:
  cdict    (ByteArray     auto, 
            ByteArray     values). 
            
   
public define FR_CompiledDict
   compile
   (
     List(FR_DictEntry) l
   ) =
   with     d = to_Dict(l), 
         keys = map(key,d), 
   since many_keys_auto(0,keys,0) is (auto1,_), 
   since init_state(auto1) is (iid,_,_),
   since unfold(auto1,by_id(auto1,iid),0,[]) is (auto2,_),
   with auto3 = finalize(auto2,keys),
   cdict(encode(auto3),
         array_of_values(map(value,d))).
   
   
        
      
      
      

   
   
   *** Testing. 
   
   
   
define String pad2(String s) =
   if length(s) < 2 
   then "0"+s
   else s. 
   
define String
   tds     // produce a decimal representation of x seen as a signed Word16
   (
     Word16   x
   ) =
   if x -< 0
   then "-"+pad2(abs_to_decimal(to_Int(word32(-x,0))))
   else "+"+pad2(abs_to_decimal(to_Int(word32(x,0)))). 
   
   
define String format (AutoState1 a) =
   with      sep = "       |      ", 
          no_jmp = " - ", 
         no_next = " -- ", 
   if a is 
   {  
      init(id,j,n)                then 
        concat([to_hexa(id)," ",tds(j),to_hexa(n),no_jmp,no_next,"init"],sep),  
      reject(id,disp,c,jm,nm,jnm,nnm)  then
        concat([to_hexa(id),implode([c]),tds(jm),to_hexa(nm),tds(jnm),to_hexa(nnm),"reject"],sep), 
      accept(id,kid,disp,c,jnm,nnm)  then 
        concat([to_hexa(id),implode([c]),no_jmp,no_next,tds(jnm),to_hexa(nnm),"accept ("+to_hexa(kid)+")"],sep), 
      reject_exit(id,disp,c,jm,nm)            then
        concat([to_hexa(id),implode([c]),tds(jm),to_hexa(nm),no_jmp,no_next,"reject/exit"],sep), 
      accept_exit(id,kid,disp,c)            then
        concat([to_hexa(id),implode([c]),no_jmp,no_next,no_jmp,no_next,"accept/exit ("+to_hexa(kid)+")"],sep), 
   }. 
                
               
define String
   auto1_banner
   = 
   " state     |     char     |  jmp if match  |  next if match  | jmp if nomatch | next if nomatch |      action\n".
   
define String
   auto1_sep 
   =
   "-----------+--------------+----------------+-----------------+----------------+-----------------+-----------------\n". 
   
define One 
   show
   (
      List(AutoState1)  l
   ) =
   if l is 
   {
     [ ]     then unique, 
     [h . t] then print(format(h)); print("\n"); show(t) 
   }. 
                
     
   
define String to_hexa (List(Word16) l) = "?".    
   
define String 
   format
   (
     List(PatternChar) l,
     Word16            max,
     Word16            i
   ) =
   if i >=+ max then ""
   else if find(i,l) is 
   {
     failure     then "_"+format(l,max,i+1), 
     success(c)  then implode([c])+format(l,max,i+1) 
   }.
   
   
   
define String format (AutoState2         a, 
                      Word16             max,
                      List(List(Word8))  keys) =
   with      sep = "       |      ", 
          no_jmp = " - ", 
         no_next = " -- ", 
   if a is 
   {  
      init(id,p,j,n)                then 
        concat([to_hexa(id)," ",tds(j),to_hexa(n),no_jmp,no_next,"init       ",format(p,max,0),""],sep),  
      reject(id,p,disp,c,jm,nm,jnm,nnm)  then
        concat([to_hexa(id),implode([c]),tds(jm),to_hexa(nm),tds(jnm),to_hexa(nnm),"reject     ",format(p,max,0),""],sep), 
      accept(id,kid,p,disp,c,jnm,nnm)  then 
        concat([to_hexa(id),implode([c]),no_jmp,no_next,tds(jnm),to_hexa(nnm),"accept     ",format(p,max,0),""],sep), 
      reject_exit(id,p,disp,c,jm,nm)            then
        concat([to_hexa(id),implode([c]),tds(jm),to_hexa(nm),no_jmp,no_next,"reject/exit",format(p,max,0),
                                       to_decimal(pattern_jmp(p,keys,max))],sep), 
      accept_exit(id,kid,p,disp,c)            then
        concat([to_hexa(id),implode([c]),no_jmp,no_next,no_jmp,no_next,"accept/exit",format(p,max,0),
                                       to_decimal(pattern_jmp(p,keys,max))],sep), 
   }. 
   
   
   
define One 
   show
   (
      List(AutoState2)  l,
      Word16            max,
      List(List(Word8)) keys
   ) =
   if l is 
   {
     [ ]     then unique, 
     [h . t] then print(format(h,max,keys)); print("\n"); show(t,max,keys) 
   }. 
                
define String
   auto2_banner
   = 
   " state     |     char     |  jmp if match  |  next if match  | jmp if nomatch | next if nomatch |         action         |      pattern     |  loop jmp   \n".
   
define String
   auto2_sep 
   =
   "-----------+--------------+----------------+-----------------+----------------+-----------------+------------------------+------------------+--------------\n". 
   
   
define String
   auto3_banner
   = 
   " state     |     char     |  jmp if match  |  next if match  | jmp if nomatch | next if nomatch |         action        \n".
   
define String
   auto3_sep 
   =
   "-----------+--------------+----------------+-----------------+----------------+-----------------+-----------------------\n". 
   
define String format(AutoState3 a) =
   with      sep = "       |      ", 
          no_jmp = " - ", 
         no_next = " -- ", 
   if a is 
   {
     init(id,jmp,next)  then 
       concat([to_hexa(id),"*",tds(jmp),to_hexa(next),tds(jmp),to_hexa(next),"init"],sep),
       
     accept(id,kid,char,jmp_nomatch,next_nomatch)  then 
       concat([to_hexa(id),implode([char]),no_jmp,no_next,tds(jmp_nomatch),to_hexa(next_nomatch),"accept ("+to_hexa(kid)+")"],sep),
     
     continue(id,char,jmp_match,next_match,jmp_nomatch,next_nomatch)  then 
       concat([to_hexa(id),implode([char]),tds(jmp_match),to_hexa(next_match),tds(jmp_nomatch),to_hexa(next_nomatch),"continue"],sep)

   }. 
   
   
define One
   show
   (
     List(AutoState3)   l
   ) =
   if l is 
   {
     [ ]     then unique, 
     [h . t] then print(format(h)); print("\n"); show(t) 
   }. 
   
   
define List(List(Word8)) mykeys = 
  [
    explode("zt"),
    explode("uvw"),
    explode("abcde")
  ].     
   
   
global define One
   fr_test
   (
      List(String) args
   ) =
   print(auto3_banner); 
   print(auto3_sep); 
   if many_keys_auto(0,mykeys,0) is (auto,next_id) then 
                           if unfold(auto,by_id(auto,7),0,[]) is (auto2,_) then
                              show(finalize(auto2,mykeys)); 
   print(auto3_sep).