/** Ċ Ġ* ĠCopyright Ġ( C ) Ġ 2 0 2 0 ĠDr . ĠDavid ĠH . ĠA keh ur st Ġ( http :// dr . david . h . ake hur st . net ) Ċ Ġ* Ċ Ġ* ĠLicensed Ġunder Ġthe ĠApache ĠLicense , ĠVersion Ġ 2 . 0 Ġ( the Ġ" License "); Ċ Ġ* Ġyou Ġmay Ġnot Ġuse Ġthis Ġfile Ġexcept Ġin Ġcompliance Ġwith Ġthe ĠLicense . Ċ Ġ* ĠYou Ġmay Ġobtain Ġa Ġcopy Ġof Ġthe ĠLicense Ġat Ċ Ġ* Ċ Ġ* ĠĠĠĠĠĠĠĠ Ġhttp :// www . apache . org / licenses / LICENSE - 2 . 0 Ċ Ġ* Ċ Ġ* ĠUnless Ġrequired Ġby Ġapplicable Ġlaw Ġor Ġagreed Ġto Ġin Ġwriting , Ġsoftware Ċ Ġ* Ġdistributed Ġunder Ġthe ĠLicense Ġis Ġdistributed Ġon Ġan Ġ" AS ĠIS " ĠBASIS , Ċ Ġ* ĠWITHOUT ĠWARRANTIES ĠOR ĠCONDITIONS ĠOF ĠANY ĠKIND , Ġeither Ġexpress Ġor Ġimplied . Ċ Ġ* ĠSee Ġthe ĠLicense Ġfor Ġthe Ġspecific Ġlanguage Ġgoverning Ġpermissions Ġand Ċ Ġ* Ġlimitations Ġunder Ġthe ĠLicense . Ċ Ġ*/ Ċ Ċ package Ġnet . ake hur st . language . ag l . autom aton Ċ Ċ import Ġnet . ake hur st . language . ag l . runtime . structure .* Ċ import Ġnet . ake hur st . language . api . processor . Automaton Kind Ċ import Ġkotlin . test . Test Ċ import Ġkotlin . test . assertEquals Ċ Ċ internal Ġclass Ġtest _ left Recursive Ġ: Ġtest _ Automaton Abstract () Ġ{ ĊĊĠĠĠ Ġ// ĠS Ġ= Ġ Ġ' a ' Ġ| ĠS 1 ĊĠĠĠ Ġ// ĠS 1 Ġ= ĠS Ġ' a ' ĊĊĠĠĠ Ġprivate Ġcompanion Ġobject Ġ{ ĊĊĠĠĠĠĠĠĠ Ġval Ġr rs Ġ= Ġruntime Rule Set Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġchoice (" S ", ĠRuntime Rule Choice Kind . LON GEST _ PRIORITY ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġliteral (" a ") ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġref (" S 1 ") ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġconcat enation (" S 1 ") Ġ{ Ġref (" S "); Ġliteral (" a ") Ġ} ĊĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠ Ġval ĠS Ġ= Ġr rs . find Runtime Rule (" S ") ĊĠĠĠĠĠĠĠ Ġval ĠSM Ġ= Ġr rs . fetch State Set For ( S , ĠAutom aton Kind . LOOK A HEAD _ 1 ) ĊĠĠĠĠĠĠĠ Ġval ĠG Ġ= ĠSM . start State . runtime Rules . first () ĊĠĠĠĠĠĠĠ Ġval ĠS 1 Ġ= Ġr rs . find Runtime Rule (" S 1 ") ĊĠĠĠĠĠĠĠ Ġval Ġa Ġ= Ġr rs . find Runtime Rule ("' a '") ĊĊĠĠĠĠĠĠĠ Ġval Ġs 0 Ġ= ĠSM . start State ĊĠĠĠĠĠĠĠ Ġval Ġs 1 Ġ= ĠSM . states [ listOf ( RP ( a , Ġ 0 , ĠE OR ))] ĊĠĠĠĠĠĠĠ Ġval Ġs 2 Ġ= ĠSM . states [ listOf ( RP ( S , Ġ 0 , ĠE OR ))] ĊĠĠĠĠĠĠĠ Ġval Ġs 3 Ġ= ĠSM . states [ listOf ( RP ( S 1 , Ġ 0 , ĠE OR ))] ĊĠĠĠĠĠĠĠ Ġval Ġs 4 Ġ= ĠSM . states [ listOf ( RP ( S 1 , Ġ 0 , Ġ 1 ))] ĊĠĠĠĠĠĠĠ Ġval Ġs 5 Ġ= ĠSM . states [ listOf ( RP ( G , Ġ 0 , ĠE OR ))] ĊĠĠĠĠĠĠĠ Ġval Ġs 6 Ġ= ĠSM . states [ listOf ( RP ( S , Ġ 1 , ĠE OR ))] ĊĊĠĠĠĠĠĠĠ Ġval Ġlhs _ a Ġ= ĠSM . create Look ahead Set ( set Of ( a )) ĊĠĠĠĠĠĠĠ Ġval Ġlhs _ a U Ġ= ĠSM . create Look ahead Set ( set Of ( a , ĠUP )) ĊĠĠĠ Ġ} ĊĠĠĠ Ġ@ Test ĊĠĠĠ Ġoverride Ġfun Ġfirst Of () Ġ{ ĊĠĠĠĠĠĠĠ ĠlistOf ( ĊĠĠĠĠĠĠĠĠĠĠĠ ĠTrip le ( RP ( G , Ġ 0 , ĠS OR ), Ġlhs _ U , Ġset Of ( a )), Ġ// ĠG Ġ= Ġ. ĠS ĊĠĠĠĠĠĠĠĠĠĠĠ ĠTrip le ( RP ( G , Ġ 0 , ĠE OR ), Ġlhs _ U , Ġset Of ( UP )), Ġ// ĠG Ġ= ĠS Ġ. ĊĠĠĠĠĠĠĠĠĠĠĠ ĠTrip le ( RP ( S , Ġ 0 , ĠS OR ), Ġlhs _ U , Ġset Of ( a )), Ġ// ĠS Ġ= Ġ. Ġa ĊĠĠĠĠĠĠĠĠĠĠĠ ĠTrip le ( RP ( S , Ġ 0 , ĠE OR ), Ġlhs _ U , Ġset Of ( UP )), Ġ// ĠS Ġ= Ġa Ġ. ĊĠĠĠĠĠĠĠĠĠĠĠ ĠTrip le ( RP ( S 1 , Ġ 0 , ĠS OR ), Ġlhs _ U , Ġset Of ( a )), Ġ// ĠS 1 Ġ= Ġ. ĠS Ġa ĊĠĠĠĠĠĠĠĠĠĠĠ ĠTrip le ( RP ( S 1 , Ġ 1 , ĠS OR ), Ġlhs _ U , Ġset Of ( a )), Ġ// ĠS 1 Ġ= ĠS Ġ. Ġa ĊĠĠĠĠĠĠĠĠĠĠĠ ĠTrip le ( RP ( S 1 , Ġ 0 , ĠE OR ), Ġlhs _ U , Ġset Of ( UP )) Ġ// ĠS 1 Ġ= ĠS Ġa Ġ. ĊĠĠĠĠĠĠĠ Ġ). test All Ġ{ Ġrp , Ġlhs , Ġexpected Ġ-> ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġactual Ġ= ĠSM . build Cache . first Of ( rp , Ġlhs ) ĊĠĠĠĠĠĠĠĠĠĠĠ ĠassertEquals ( expected , Ġactual , Ġ" failed Ġ$ rp ") ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠ Ġ} ĊĠĠĠ Ġ@ Test ĊĠĠĠ Ġoverride Ġfun Ġs 0 _ width Into () Ġ{ ĊĠĠĠĠĠĠĠ Ġval Ġs 0 Ġ= ĠSM . start State ĊĠĠĠĠĠĠĠ Ġval Ġactual Ġ= Ġs 0 . width Into ( null ). toList () ĊĊĠĠĠĠĠĠĠ Ġval Ġexpected Ġ= ĠlistOf ( ĊĠĠĠĠĠĠĠĠĠĠĠ ĠWidth Info ( RP ( a , Ġ 0 , ĠE OR ), Ġlhs _ a U ) ĊĠĠĠĠĠĠĠ Ġ) ĊĠĠĠĠĠĠĠ ĠassertEquals ( expected . size , Ġactual . size ) ĊĠĠĠĠĠĠĠ Ġfor Ġ( i Ġin Ġ 0 Ġuntil Ġactual . size ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ ĠassertEquals ( expected [ i ], Ġactual [ i ]) ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġ@ Test ĊĠĠĠ Ġfun Ġs 0 _ transitions () Ġ{ ĊĠĠĠĠĠĠĠ Ġval Ġactual Ġ= Ġs 0 . transitions ( null ) ĊĊĠĠĠĠĠĠĠ Ġval Ġexpected Ġ= ĠlistOf ( ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ ĠTransition ( s 0 , Ġs 1 , ĠTransition . Parse Action . WIDTH , Ġlhs _ a U , ĠLook ahead Set . EMPTY , Ġnull ) Ġ{ Ġ_, Ġ_ Ġ-> Ġtrue Ġ} ĊĠĠĠĠĠĠĠ Ġ). toList () ĊĠĠĠĠĠĠĠ ĠassertEquals ( expected . size , Ġactual . size ) ĊĠĠĠĠĠĠĠ Ġfor Ġ( i Ġin Ġactual . indices ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ ĠassertEquals ( expected [ i ], Ġactual [ i ]) ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġ@ Test ĊĠĠĠ Ġfun Ġs 1 _ height Or G raft Into _ s 0 () Ġ{ ĊĊĠĠĠĠĠĠĠ Ġval Ġactual Ġ= Ġs 1 . height Or G raft Into ( s 0 ). toList () ĊĊĠĠĠĠĠĠĠ Ġval Ġexpected Ġ= ĠlistOf ( ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ ĠHeight G raft Info ( ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ ĠlistOf ( RP ( S , Ġ 0 , Ġ 0 )), ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ ĠlistOf ( RP ( S , Ġ 0 , ĠE OR )), ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġlhs _ a U , ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġlhs _ U ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ) ĊĠĠĠĠĠĠĠ Ġ) ĊĠĠĠĠĠĠĠ ĠassertEquals ( expected , Ġactual ) ĊĊĠĠĠ Ġ} ĊĊĠĠĠ Ġ@ Test ĊĠĠĠ Ġfun Ġs 1 _ transitions _ s 0 () Ġ{ ĊĠĠĠĠĠĠĠ Ġval Ġactual Ġ= Ġs 1 . transitions ( s 0 ) ĊĊĠĠĠĠĠĠĠ Ġval Ġexpected Ġ= ĠlistOf < Transition >( ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ ĠTransition ( s 1 , Ġs 2 , ĠTransition . Parse Action . HEIGHT , Ġlhs _ a U , ĠLook ahead Set . UP , Ġnull ) Ġ{ Ġ_, Ġ_ Ġ-> Ġtrue Ġ} Ċ // ĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ ĠTransition ( s 1 , Ġs 3 , ĠTransition . Parse Action . GR AFT , Ġlhs _ a U , Ġnull ) Ġ{ Ġ_, Ġ_ Ġ-> Ġtrue Ġ} ĊĠĠĠĠĠĠĠ Ġ) ĊĠĠĠĠĠĠĠ ĠassertEquals ( expected . size , Ġactual . size ) ĊĠĠĠĠĠĠĠ Ġfor Ġ( i Ġin Ġactual . indices ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ ĠassertEquals ( expected [ i ], Ġactual [ i ]) ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġ@ Test ĊĠĠĠ Ġfun Ġs 2 _ height Or G raft Into _ s 0 () Ġ{ ĊĠĠĠĠĠĠĠ Ġval Ġactual Ġ= Ġs 2 . height Or G raft Into ( s 0 ) ĊĊĠĠĠĠĠĠĠ Ġval Ġexpected Ġ= Ġset Of ( ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ ĠHeight G raft Info ( ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ ĠlistOf ( RP ( G , Ġ 0 , Ġ 0 )), ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ ĠlistOf ( RP ( G , Ġ 0 , ĠE OR )), ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġlhs _ U , ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġlhs _ U ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ), ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ ĠHeight G raft Info ( ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ ĠlistOf ( RP ( S 1 , Ġ 0 , Ġ 0 )), ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ ĠlistOf ( RP ( S 1 , Ġ 0 , Ġ 1 )), ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġlhs _ a , ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġlhs _ a U ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ) ĊĠĠĠĠĠĠĠ Ġ) ĊĠĠĠĠĠĠĠ ĠassertEquals ( expected , Ġactual ) ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġ@ Test ĊĠĠĠ Ġfun Ġs 2 _ transitions _ s 0 () Ġ{ ĊĊĠĠĠĠĠĠĠ Ġval Ġactual Ġ= Ġs 2 . transitions ( s 0 ) ĊĊĠĠĠĠĠĠĠ Ġval Ġexpected Ġ= ĠlistOf < Transition >( ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ ĠTransition ( s 2 , Ġs 4 , ĠTransition . Parse Action . HEIGHT , Ġlhs _ a , Ġlhs _ a , Ġnull ) Ġ{ Ġ_, Ġ_ Ġ-> Ġtrue Ġ}, ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ ĠTransition ( s 2 , Ġs 5 , ĠTransition . Parse Action . GR AFT , Ġlhs _ U , Ġlhs _ U , Ġnull ) Ġ{ Ġ_, Ġ_ Ġ-> Ġtrue Ġ} ĊĠĠĠĠĠĠĠ Ġ) ĊĠĠĠĠĠĠĠ ĠassertEquals ( expected , Ġactual ) ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġ@ Test ĊĠĠĠ Ġfun Ġs 4 _ width Into _ s 0 () Ġ{ ĊĠĠĠĠĠĠĠ Ġ// Ġs 4 Ġ| ĠS 1 Ġ= ĠS Ġ. Ġa ĊĠĠĠĠĠĠĠ Ġval Ġactual Ġ= Ġs 4 . width Into ( s 0 ). toList () ĊĊĠĠĠĠĠĠĠ Ġval Ġexpected Ġ= ĠlistOf ( ĊĠĠĠĠĠĠĠĠĠĠĠ ĠWidth Info ( RP ( a , Ġ 0 , ĠE OR ), Ġlhs _ a U ) ĊĠĠĠĠĠĠĠ Ġ) ĊĠĠĠĠĠĠĠ ĠassertEquals ( expected , Ġactual ) ĊĊĠĠĠ Ġ} ĊĊĠĠĠ Ġ@ Test ĊĠĠĠ Ġfun Ġs 4 _ transitions _ s 0 () Ġ{ ĊĊĠĠĠĠĠĠĠ Ġval Ġactual Ġ= Ġs 4 . transitions ( s 0 ) ĊĠĠĠĠĠĠĠ Ġval Ġexpected Ġ= ĠlistOf < Transition >( ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ ĠTransition ( s 4 , Ġs 1 , ĠTransition . Parse Action . WIDTH , Ġlhs _ a U , Ġlhs _ a U , Ġnull ) Ġ{ Ġ_, Ġ_ Ġ-> Ġtrue Ġ} ĊĠĠĠĠĠĠĠ Ġ) ĊĠĠĠĠĠĠĠ ĠassertEquals ( expected . size , Ġactual . size ) ĊĠĠĠĠĠĠĠ Ġfor Ġ( i Ġin Ġactual . indices ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ ĠassertEquals ( expected [ i ], Ġactual [ i ]) ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠ Ġ} ĊĊĊĠĠĠ Ġ@ Test ĊĠĠĠ Ġfun Ġs 1 _ height Or G raft Into _ s 4 () Ġ{ ĊĊĠĠĠĠĠĠĠ Ġval Ġactual Ġ= Ġs 1 . height Or G raft Into ( s 4 ). toList () ĊĊĠĠĠĠĠĠĠ Ġval Ġexpected Ġ= ĠlistOf ( ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ ĠHeight G raft Info ( ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ ĠlistOf ( RP ( S 1 , Ġ 0 , Ġ 1 )), ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ ĠlistOf ( RP ( S 1 , Ġ 0 , ĠE OR )), ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġlhs _ a U , ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġlhs _ U ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ) ĊĠĠĠĠĠĠĠ Ġ) ĊĠĠĠĠĠĠĠ ĠassertEquals ( expected , Ġactual ) ĊĊĠĠĠ Ġ} ĊĊĠĠĠ Ġ@ Test ĊĠĠĠ Ġfun Ġs 1 _ transitions _ s 4 () Ġ{ ĊĊĠĠĠĠĠĠĠ Ġval Ġactual Ġ= Ġs 1 . transitions ( s 4 ) ĊĠĠĠĠĠĠĠ Ġval Ġexpected Ġ= ĠlistOf < Transition >( ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ ĠTransition ( s 1 , Ġs 3 , ĠTransition . Parse Action . GR AFT , Ġlhs _ a U , Ġlhs _ a U , Ġnull ) Ġ{ Ġ_, Ġ_ Ġ-> Ġtrue Ġ} ĊĠĠĠĠĠĠĠ Ġ) ĊĠĠĠĠĠĠĠ ĠassertEquals ( expected . size , Ġactual . size ) ĊĠĠĠĠĠĠĠ Ġfor Ġ( i Ġin Ġactual . indices ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ ĠassertEquals ( expected [ i ], Ġactual [ i ]) ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġ@ Test ĊĠĠĠ Ġfun Ġs 3 _ transitions _ s 0 () Ġ{ ĊĊĠĠĠĠĠĠĠ Ġval Ġactual Ġ= Ġs 3 . transitions ( s 0 ) ĊĊĠĠĠĠĠĠĠ Ġval Ġexpected Ġ= ĠlistOf < Transition >( ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ ĠTransition ( s 3 , Ġs 6 , ĠTransition . Parse Action . HEIGHT , Ġlhs _ a U , Ġlhs _ a U , Ġnull ) Ġ{ Ġ_, Ġ_ Ġ-> Ġtrue Ġ} ĊĠĠĠĠĠĠĠ Ġ) ĊĠĠĠĠĠĠĠ ĠassertEquals ( expected . size , Ġactual . size ) ĊĠĠĠĠĠĠĠ Ġfor Ġ( i Ġin Ġactual . indices ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ ĠassertEquals ( expected [ i ], Ġactual [ i ]) ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠ Ġ} ĊĊĊĠĠĠ Ġ@ Test ĊĠĠĠ Ġfun Ġs 6 _ transitions _ s 0 () Ġ{ ĊĊĠĠĠĠĠĠĠ Ġval Ġactual Ġ= Ġs 6 . transitions ( s 0 ) ĊĊĠĠĠĠĠĠĠ Ġval Ġexpected Ġ= ĠlistOf < Transition >( ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ ĠTransition ( s 6 , Ġs 4 , ĠTransition . Parse Action . HEIGHT , Ġlhs _ a , Ġlhs _ a , Ġnull ) Ġ{ Ġ_, Ġ_ Ġ-> Ġtrue Ġ}, ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ ĠTransition ( s 6 , Ġs 5 , ĠTransition . Parse Action . GR AFT , Ġlhs _ U , Ġlhs _ U , Ġnull ) Ġ{ Ġ_, Ġ_ Ġ-> Ġtrue Ġ} ĊĠĠĠĠĠĠĠ Ġ) ĊĠĠĠĠĠĠĠ ĠassertEquals ( expected . size , Ġactual . size ) ĊĠĠĠĠĠĠĠ Ġfor Ġ( i Ġin Ġactual . indices ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ ĠassertEquals ( expected [ i ], Ġactual [ i ]) ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠ Ġ} Ċ }