schema/automaton/DFACreator.java

/**************************************************************
*
* Licensed to the Apache Software Foundation (ASF) under one
* or more contributor license agreements.  See the NOTICE file
* distributed with this work for additional information
* regarding copyright ownership.  The ASF licenses this file
* to you 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 org.apache.openoffice.ooxml.schema.automaton;

import java.util.Collection;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Map;
import java.util.Map.Entry;
import java.util.Queue;
import java.util.Set;
import java.util.TreeMap;
import java.util.TreeSet;
import java.util.Vector;

import org.apache.openoffice.ooxml.schema.model.attribute.Attribute;
import org.apache.openoffice.ooxml.schema.model.base.Location;
import org.apache.openoffice.ooxml.schema.model.base.QualifiedName;

/** Convert an NFA into a DFA via the powerset construction (also called subset
 *  construction).
 */
public class DFACreator
{
    /** For a given non-deterministic finite automaton create an equivalent
     *  deterministic finite automaton.
     */
    public static FiniteAutomaton CreateDFAforNFA (
        final StateContainer aDFAStateContainer,
        final StateContext aNFAStateContext,
        final Vector<Attribute> aAttributes,
        final QualifiedName aTypeName,
        final Location aLocation)
    {
        final DFACreator aCreator = new DFACreator(aDFAStateContainer, aNFAStateContext, aTypeName);
        aCreator.CreateDFAforNFA();
        return new FiniteAutomaton(
            aCreator.maDFAStateContext,
            aAttributes,
            aLocation);
    }


    private DFACreator (
        final StateContainer aDFAStateContainer,
        final StateContext aNFAStateContext,
        final QualifiedName aTypeName)
    {
        maNFAStateContext = aNFAStateContext;

        // Create the set of state sets where each element corresponds to a
        // state in the DFA.
        maNFASetToDFAStateMap = new TreeMap<>();
        maDFAStateContext = new StateContext(
            aDFAStateContainer,
            aTypeName == null
                ? "<TOP-LEVEL>"
                : aTypeName.GetStateName());

        maDFATransitions = new HashSet<>();
        maAcceptingDFAStates = new Vector<>();
    }


    private void CreateDFAforNFA ()
    {
        final State aNFAStartState = maNFAStateContext.GetStartState();

        // Initialize the creation process by adding the epsilon closure of the
        // original start state to the work list.
        final StateSet aStartSet = GetEpsilonClosure(new StateSet(aNFAStartState));
        maNFASetToDFAStateMap.put(aStartSet, maDFAStateContext.GetStartState());

        PropagateStateFlags(aStartSet, maDFAStateContext.GetStartState());

        final Queue<StateSet> aWorklist = new LinkedList<>();
        aWorklist.add(aStartSet);

        while ( ! aWorklist.isEmpty())
        {
            final Collection<StateSet> aAdditionalWorkList = ProcessTransitionFront(
                aWorklist.poll());

            aWorklist.addAll(aAdditionalWorkList);
        }
    }


    private Collection<StateSet> ProcessTransitionFront (
        final StateSet aSet)
    {
        final Set<StateSet> aLocalWorklist = new TreeSet<>();

        // Find all regular transitions that start from any state in the set.
        final Map<String,Vector<Transition>> aTransitions = GetTransitionFront(aSet);

        // Create new state sets for states that are reachable via the same element and
        // the following epsilon transitions.
        for (final Entry<String,Vector<Transition>> aEntry : aTransitions.entrySet())
        {
            // Create new state sets for both the end state of the transition.
            final StateSet aEpsilonClosure = GetEpsilonClosure(GetEndStateSet(aEntry.getValue()));

            // When these are new state sets then add them to the worklist
            // and the set of sets.
            State aDFAState = maNFASetToDFAStateMap.get(aEpsilonClosure);
            if (aDFAState == null)
            {
                aLocalWorklist.add(aEpsilonClosure);
                aDFAState = aEpsilonClosure.CreateStateForStateSet(maDFAStateContext);
                PropagateStateFlags(aEpsilonClosure, aDFAState);
                maNFASetToDFAStateMap.put(aEpsilonClosure, aDFAState);
                if (aDFAState.IsAccepting())
                    maAcceptingDFAStates.add(aDFAState);
            }

            final State aStartState = maNFASetToDFAStateMap.get(aSet);
            final QualifiedName aElementName = GetElementName(aEntry.getValue());
            final String sElementTypeName = GetElementTypeName(aEntry.getValue());
            assert(aElementName != null);
            final Transition aTransition = new Transition(
                aStartState,
                aDFAState,
                aElementName,
                sElementTypeName);
            aStartState.AddTransition(aTransition);
            maDFATransitions.add(aTransition);
        }

        return aLocalWorklist;
    }


    private QualifiedName GetElementName (final Vector<Transition> aTransitions)
    {
        for (final Transition aTransition : aTransitions)
            return aTransition.GetElementName();
        return null;
    }


    private String GetElementTypeName (final Vector<Transition> aTransitions)
    {
        for (final Transition aTransition : aTransitions)
            return aTransition.GetElementTypeName();
        return null;
    }


    /** Return the epsilon closure of the given set of states.
     *  The result is the set of all states that are reachable via zero, one or
     *  more epsilon transitions from at least one state in the given set of
     *  states.
     */
    private StateSet GetEpsilonClosure ( final StateSet aSet)
    {
        final StateSet aClosure = new StateSet(aSet);

        final Queue<State> aWorkList = new LinkedList<>();
        for (final State aState : aSet.GetStates())
            aWorkList.add(aState);

        while( ! aWorkList.isEmpty())
        {
            final State aState = aWorkList.poll();
            for (final EpsilonTransition aTransition : aState.GetEpsilonTransitions())
            {
                final State aEndState = aTransition.GetEndState();
                if ( ! aClosure.ContainsState(aEndState))
                {
                    aClosure.AddState(aEndState);
                    aWorkList.add(aEndState);
                }
            }
        }

        return aClosure;
    }


    /** Return the list of regular transitions (i.e. not epsilon transitions)
     *  that start from any of the states in the given set.
     *  The returned map is a partition of the transitions according to their
     *  triggering XML element.
     */
    private Map<String, Vector<Transition>> GetTransitionFront (final StateSet aSet)
    {
        final Map<String, Vector<Transition>> aTransitions = new HashMap<>();

        for (final State aState : aSet.GetStates())
            for (final Transition aTransition : aState.GetTransitions())
            {
                final String sElementName;
                final QualifiedName aElementName = aTransition.GetElementName();
                if (aElementName != null)
                    sElementName = aElementName.GetDisplayName();
                else
                    sElementName = null; // For skip transitions.

                Vector<Transition> aElementTransitions = aTransitions.get(sElementName);
                if (aElementTransitions == null)
                {
                    aElementTransitions = new Vector<>();
                    aTransitions.put(sElementName, aElementTransitions);
                }
                aElementTransitions.add(aTransition);
            }
        return aTransitions;
    }


    /** Return a state set that contains all end states of all the given transitions.
     */
    private StateSet GetEndStateSet (final Iterable<Transition> aTransitions)
    {
        final StateSet aStateSet = new StateSet();
        for (final Transition aTransition : aTransitions)
            aStateSet.AddState(aTransition.GetEndState());
        return aStateSet;
    }


    /** Propagate accepting state flag and skip data.
     */
    private void PropagateStateFlags (
        final StateSet aNFAStateSet,
        final State aDFAState)
    {
        for (final State aNFAState : aNFAStateSet.GetStates())
            aDFAState.CopyFrom(aNFAState);
    }


    private final StateContext maNFAStateContext;

    private final Map<StateSet,State> maNFASetToDFAStateMap;
    private final StateContext maDFAStateContext;
    private final Set<Transition> maDFATransitions;
    private final Vector<State> maAcceptingDFAStates;
}