"{ Package: 'stx:goodies/petitparser/compiler' }"

"{ NameSpace: Smalltalk }"

Object subclass:#PEGFsaMinimizator
	instanceVariableNames:'fsa joinDictionary'
	classVariableNames:''
	poolDictionaries:''
	category:'PetitCompiler-FSA'
!

!PEGFsaMinimizator methodsFor:'comparison'!

info: info equals: anotherInfo
    (info == anotherInfo) ifTrue: [ ^ true ].
    (info class == anotherInfo class) ifFalse: [ ^ false ].

    "	
        I suppose I don't if someone does not have the priority set.
        Please note that equals is used for minimization, so I try to
        be as liberal as possible to get as small automaton as possible.
    "
    (info hasPriority and: [anotherInfo hasPriority]) ifTrue: [ 	
        (info priority == anotherInfo priority) ifFalse: [ ^ false ].
    ].

    (info isFinal == anotherInfo isFinal) ifFalse: [ ^ false ].
    (info isFsaFailure == anotherInfo isFsaFailure) ifFalse: [ ^ false ].

    ^ true
!

state: state equals: anotherState
    (state == anotherState) ifTrue: [ ^ true ].
    (state class == anotherState class) ifFalse: [ ^ false ].
    
    (state isFinal = anotherState isFinal) ifFalse: [ ^ false ].

    (state stateInfos size == anotherState stateInfos size) ifFalse: [ ^ false ].
    state retvals do: [:retval |
        (self info: (state infoFor: retval) equals: (anotherState infoFor: retval ifAbsent: [ ^ false ])) ifFalse: [ ^ false ]
    ].


    (state transitions size == anotherState transitions size) ifFalse: [ ^ false ].
    anotherState transitions do: [ :anotherStateT | 
        (state transitions contains: [ :stateT | 
            (anotherStateT equals: stateT) or: [
                "this is condition for self reference" 
                (anotherStateT destination == anotherState) and: [ stateT destination == state ]	
            ] ] ) ifFalse: [ ^ false ]
    ].
    
    ^ true
! !

!PEGFsaMinimizator methodsFor:'joining'!

joinInfo: state with: anotherState
    self assert: state stateInfos size == anotherState stateInfos size.

    state stateInfos do: [ :si1 | 
        self assert: (anotherState stateInfos contains: [ :si2 | 
            si1 isFinal == si2 isFinal and: [ si1 isFsaFailure == si2 isFsaFailure  ]
        ])
    ]
!

joinName: state with: anotherState
    state name: state name asString, '+', anotherState name asString.
!

joinState: state with: anotherState
    self assert: state hasZeroPriorityOnly.
    self assert: anotherState hasZeroPriorityOnly.

    self joinName: state with: anotherState.
    self joinInfo: state with: anotherState.
    
! !

!PEGFsaMinimizator methodsFor:'minimization'!

minimize
    | pair |
    pair := fsa statePairs detect:  [ :p | self state: p first equals: p second ] ifNone: [ nil ].

    [ pair isNil not ] whileTrue: [ 
        "Join priorities, because equivalency of priorities does not follow from the `equals:` of states"
        self joinState: pair first with: pair second.
        fsa replace: pair second with: pair first.
        fsa mergeTransitions.

        pair := fsa statePairs detect: [ :p | self state: p first equals: p second ] ifNone: [ nil ].
 	].
!

minimize: anFsa
    fsa := anFsa.

    self minimize.
    fsa checkSanity.
    ^ fsa
! !