    001    /*
    002     * Licensed to the Apache Software Foundation (ASF) under one or more
    003     * contributor license agreements.  See the NOTICE file distributed with
    004     * this work for additional information regarding copyright ownership.
    005     * The ASF licenses this file to You under the Apache License, Version 2.0
    006     * (the "License"); you may not use this file except in compliance with
    007     * the License.  You may obtain a copy of the License at
    008     *
    009     *     http://www.apache.org/licenses/LICENSE-2.0
    010     *
    011     * Unless required by applicable law or agreed to in writing, software
    012     * distributed under the License is distributed on an "AS IS" BASIS,
    013     * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
    014     * See the License for the specific language governing permissions and
    015     * limitations under the License.
    016     */
    017    package org.apache.commons.scxml;
    018
    019    import java.io.StringWriter;
    020    import java.util.HashSet;
    021    import java.util.IdentityHashMap;
    022    import java.util.Iterator;
    023    import java.util.List;
    024    import java.util.Map;
    025    import java.util.Set;
    026
    027    import org.apache.commons.logging.Log;
    028    import org.apache.commons.logging.LogFactory;
    029    import org.apache.commons.scxml.model.Data;
    030    import org.apache.commons.scxml.model.Datamodel;
    031    import org.apache.commons.scxml.model.Parallel;
    032    import org.apache.commons.scxml.model.Path;
    033    import org.apache.commons.scxml.model.State;
    034    import org.apache.commons.scxml.model.Transition;
    035    import org.apache.commons.scxml.model.TransitionTarget;
    036    import org.apache.commons.scxml.semantics.ErrorConstants;
    037    import org.w3c.dom.CharacterData;
    038    import org.w3c.dom.Node;
    039    import org.w3c.dom.Text;
    040
    041    /**
    042     * Helper class, all methods static final.
    043     *
    044     */
    045    public final class SCXMLHelper {
    046
    047        /**
    048         * Return true if the string is empty.
    049         *
    050         * @param attr The String to test
    051         * @return Is string empty
    052         */
    053        public static boolean isStringEmpty(final String attr) {
    054            if (attr == null || attr.trim().length() == 0) {
    055                return true;
    056            }
    057            return false;
    058        }
    059
    060        /**
    061         * Checks whether a transition target tt (State or Parallel) is a
    062         * descendant of the transition target context.
    063         *
    064         * @param tt
    065         *            TransitionTarget to check - a potential descendant
    066         * @param ctx
    067         *            TransitionTarget context - a potential ancestor
    068         * @return true iff tt is a descendant of ctx, false otherwise
    069         */
    070        public static boolean isDescendant(final TransitionTarget tt,
    071                final TransitionTarget ctx) {
    072            TransitionTarget parent = tt.getParent();
    073            while (parent != null) {
    074                if (parent == ctx) {
    075                    return true;
    076                }
    077                parent = parent.getParent();
    078            }
    079            return false;
    080        }
    081
    082        /**
    083         * Creates a set which contains given states and all their ancestors
    084         * recursively up to the upper bound. Null upperBound means root
    085         * of the state machine.
    086         *
    087         * @param states The Set of States
    088         * @param upperBounds The Set of upper bound States
    089         * @return transitive closure of a given state set
    090         */
    091        public static Set getAncestorClosure(final Set states,
    092                final Set upperBounds) {
    093            Set closure = new HashSet(states.size() * 2);
    094            for (Iterator i = states.iterator(); i.hasNext();) {
    095                TransitionTarget tt = (TransitionTarget) i.next();
    096                while (tt != null) {
    097                    if (!closure.add(tt)) {
    098                        //tt is already a part of the closure
    099                        break;
    100                    }
    101                    if (upperBounds != null && upperBounds.contains(tt)) {
    102                        break;
    103                    }
    104                    tt = tt.getParent();
    105                }
    106            }
    107            return closure;
    108        }
    109
    110        /**
    111         * Checks whether a given set of states is a legal Harel State Table
    112         * configuration (with the respect to the definition of the OR and AND
    113         * states).
    114         *
    115         * @param states
    116         *            a set of states
    117         * @param errRep
    118         *            ErrorReporter to report detailed error info if needed
    119         * @return true if a given state configuration is legal, false otherwise
    120         */
    121        public static boolean isLegalConfig(final Set states,
    122                final ErrorReporter errRep) {
    123            /*
    124             * For every active state we add 1 to the count of its parent. Each
    125             * Parallel should reach count equal to the number of its children and
    126             * contribute by 1 to its parent. Each State should reach count exactly
    127             * 1. SCXML elemnt (top) should reach count exactly 1. We essentially
    128             * summarize up the hierarchy tree starting with a given set of
    129             * states = active configuration.
    130             */
    131            boolean legalConfig = true; // let's be optimists
    132            Map counts = new IdentityHashMap();
    133            Set scxmlCount = new HashSet();
    134            for (Iterator i = states.iterator(); i.hasNext();) {
    135                TransitionTarget tt = (TransitionTarget) i.next();
    136                TransitionTarget parent = null;
    137                while ((parent = tt.getParent()) != null) {
    138                    HashSet cnt = (HashSet) counts.get(parent);
    139                    if (cnt == null) {
    140                        cnt = new HashSet();
    141                        counts.put(parent, cnt);
    142                    }
    143                    cnt.add(tt);
    144                    tt = parent;
    145                }
    146                //top-level contribution
    147                scxmlCount.add(tt);
    148            }
    149            //Validate counts:
    150            for (Iterator i = counts.entrySet().iterator(); i.hasNext();) {
    151                Map.Entry entry = (Map.Entry) i.next();
    152                TransitionTarget tt = (TransitionTarget) entry.getKey();
    153                Set count = (Set) entry.getValue();
    154                if (tt instanceof Parallel) {
    155                    Parallel p = (Parallel) tt;
    156                    if (count.size() < p.getChildren().size()) {
    157                        errRep.onError(ErrorConstants.ILLEGAL_CONFIG,
    158                            "Not all AND states active for parallel "
    159                            + p.getId(), entry);
    160                        legalConfig = false;
    161                    }
    162                } else {
    163                    if (count.size() > 1) {
    164                        errRep.onError(ErrorConstants.ILLEGAL_CONFIG,
    165                            "Multiple OR states active for state "
    166                            + tt.getId(), entry);
    167                        legalConfig = false;
    168                    }
    169                }
    170                count.clear(); //cleanup
    171            }
    172            if (scxmlCount.size() > 1) {
    173                errRep.onError(ErrorConstants.ILLEGAL_CONFIG,
    174                        "Multiple top-level OR states active!", scxmlCount);
    175            }
    176            //cleanup
    177            scxmlCount.clear();
    178            counts.clear();
    179            return legalConfig;
    180        }
    181
    182        /**
    183         * Finds the least common ancestor of transition targets tt1 and tt2 if
    184         * one exists.
    185         *
    186         * @param tt1 First TransitionTarget
    187         * @param tt2 Second TransitionTarget
    188         * @return closest common ancestor of tt1 and tt2 or null
    189         */
    190        public static TransitionTarget getLCA(final TransitionTarget tt1,
    191                final TransitionTarget tt2) {
    192            if (tt1 == tt2) {
    193                return tt1; //self-transition
    194            } else if (isDescendant(tt1, tt2)) {
    195                return tt2;
    196            } else if (isDescendant(tt2, tt1)) {
    197                return tt1;
    198            }
    199            Set parents = new HashSet();
    200            TransitionTarget tmp = tt1;
    201            while ((tmp = tmp.getParent()) != null) {
    202                parents.add(tmp);
    203            }
    204            tmp = tt2;
    205            while ((tmp = tmp.getParent()) != null) {
    206                //test redundant add = common ancestor
    207                if (!parents.add(tmp)) {
    208                    parents.clear();
    209                    return tmp;
    210                }
    211            }
    212            return null;
    213        }
    214
    215        /**
    216         * Returns the set of all states (and parallels) which are exited if a
    217         * given transition t is going to be taken.
    218         * Current states are necessary to be taken into account
    219         * due to orthogonal states and cross-region transitions -
    220         * see UML specs for more details.
    221         *
    222         * @param t
    223         *            transition to be taken
    224         * @param currentStates
    225         *            the set of current states (simple states only)
    226         * @return a set of all states (including composite) which are exited if a
    227         *         given transition is taken
    228         */
    229        public static Set getStatesExited(final Transition t,
    230                final Set currentStates) {
    231            Set allStates = new HashSet();
    232            if (t.getTargets().size() == 0) {
    233                return allStates;
    234            }
    235            Path p = (Path) t.getPaths().get(0); // all paths have same upseg
    236            //the easy part
    237            allStates.addAll(p.getUpwardSegment());
    238            TransitionTarget source = t.getParent();
    239            for (Iterator act = currentStates.iterator(); act.hasNext();) {
    240                TransitionTarget a = (TransitionTarget) act.next();
    241                if (isDescendant(a, source)) {
    242                    boolean added = false;
    243                    added = allStates.add(a);
    244                    while (added && a != source) {
    245                        a = a.getParent();
    246                        added = allStates.add(a);
    247                    }
    248                }
    249            }
    250            if (p.isCrossRegion()) {
    251                for (Iterator regions = p.getRegionsExited().iterator();
    252                        regions.hasNext();) {
    253                    Parallel par = ((Parallel) ((State) regions.next()).
    254                        getParent());
    255                    //let's find affected states in sibling regions
    256                    for (Iterator siblings = par.getChildren().iterator();
    257                            siblings.hasNext();) {
    258                        State s = (State) siblings.next();
    259                        for (Iterator act = currentStates.iterator();
    260                                act.hasNext();) {
    261                            TransitionTarget a = (TransitionTarget) act.next();
    262                            if (isDescendant(a, s)) {
    263                                //a is affected
    264                                boolean added = false;
    265                                added = allStates.add(a);
    266                                while (added && a != s) {
    267                                    a = a.getParent();
    268                                    added = allStates.add(a);
    269                                }
    270                            }
    271                        }
    272                    }
    273                }
    274            }
    275            return allStates;
    276        }
    277
    278        /**
    279         * According to the UML definition, two transitions
    280         * are conflicting if the sets of states they exit overlap.
    281         *
    282         * @param t1 a transition to check against t2
    283         * @param t2 a transition to check against t1
    284         * @param currentStates the set of current states (simple states only)
    285         * @return true if the t1 and t2 are conflicting transitions
    286         * @see #getStatesExited(Transition, Set)
    287         */
    288        public static boolean inConflict(final Transition t1,
    289                final Transition t2, final Set currentStates) {
    290            Set ts1 = getStatesExited(t1, currentStates);
    291            Set ts2 = getStatesExited(t2, currentStates);
    292            ts1.retainAll(ts2);
    293            if (ts1.isEmpty()) {
    294                return false;
    295            }
    296            return true;
    297        }
    298
    299        /**
    300         * Whether the first argument is a subtype of the second.
    301         *
    302         * @param child The candidate subtype
    303         * @param parent The supertype
    304         * @return true if child is subtype of parent, otherwise false
    305         */
    306        public static boolean subtypeOf(final Class child, final Class parent) {
    307            if (child == null || parent == null) {
    308                return false;
    309            }
    310            for (Class current = child; current != Object.class;
    311                    current = current.getSuperclass()) {
    312                if (current == parent) {
    313                    return true;
    314                }
    315            }
    316            return false;
    317        }
    318
    319        /**
    320         * Whether the class implements the interface.
    321         *
    322         * @param clas The candidate class
    323         * @param interfayce The interface
    324         * @return true if clas implements interfayce, otherwise false
    325         */
    326        public static boolean implementationOf(final Class clas,
    327                final Class interfayce) {
    328            if (clas == null || interfayce == null || !interfayce.isInterface()) {
    329                return false;
    330            }
    331            for (Class current = clas; current != Object.class;
    332                    current = current.getSuperclass()) {
    333                Class[] implementedInterfaces = current.getInterfaces();
    334                for (int i = 0; i < implementedInterfaces.length; i++) {
    335                    if (implementedInterfaces[i] == interfayce) {
    336                        return true;
    337                    }
    338                }
    339            }
    340            return false;
    341        }
    342
    343        /**
    344         * Set node value, depending on its type, from a String.
    345         *
    346         * @param node A Node whose value is to be set
    347         * @param value The new value
    348         */
    349        public static void setNodeValue(final Node node, final String value) {
    350            switch(node.getNodeType()) {
    351                case Node.ATTRIBUTE_NODE:
    352                    node.setNodeValue(value);
    353                    break;
    354                case Node.ELEMENT_NODE:
    355                    //remove all text children
    356                    if (node.hasChildNodes()) {
    357                        Node child = node.getFirstChild();
    358                        while (child != null) {
    359                            if (child.getNodeType() == Node.TEXT_NODE) {
    360                                node.removeChild(child);
    361                            }
    362                            child = child.getNextSibling();
    363                        }
    364                    }
    365                    //create a new text node and append
    366                    Text txt = node.getOwnerDocument().createTextNode(value);
    367                    node.appendChild(txt);
    368                    break;
    369                case Node.TEXT_NODE:
    370                case Node.CDATA_SECTION_NODE:
    371                    ((CharacterData) node).setData(value);
    372                    break;
    373                default:
    374                    String err = "Trying to set value of a strange Node type: "
    375                        + node.getNodeType();
    376                    //Logger.logln(Logger.E, err);
    377                    throw new IllegalArgumentException(err);
    378            }
    379        }
    380
    381        /**
    382         * Retrieve a DOM node value as a string depending on its type.
    383         *
    384         * @param node A node to be retreived
    385         * @return The value as a string
    386         */
    387        public static String getNodeValue(final Node node) {
    388            String result = "";
    389            if (node == null) {
    390                return result;
    391            }
    392            switch(node.getNodeType()) {
    393                case Node.ATTRIBUTE_NODE:
    394                    result = node.getNodeValue();
    395                    break;
    396                case Node.ELEMENT_NODE:
    397                    if (node.hasChildNodes()) {
    398                        Node child = node.getFirstChild();
    399                        StringBuffer buf = new StringBuffer();
    400                        while (child != null) {
    401                            if (child.getNodeType() == Node.TEXT_NODE) {
    402                                buf.append(((CharacterData) child).getData());
    403                            }
    404                            child = child.getNextSibling();
    405                        }
    406                        result = buf.toString();
    407                    }
    408                    break;
    409                case Node.TEXT_NODE:
    410                case Node.CDATA_SECTION_NODE:
    411                    result = ((CharacterData) node).getData();
    412                    break;
    413                default:
    414                    String err = "Trying to get value of a strange Node type: "
    415                        + node.getNodeType();
    416                    //Logger.logln(Logger.W, err );
    417                    throw new IllegalArgumentException(err);
    418            }
    419            return result.trim();
    420        }
    421
    422        /**
    423         * Clone data model.
    424         *
    425         * @param ctx The context to clone to.
    426         * @param datamodel The datamodel to clone.
    427         * @param evaluator The expression evaluator.
    428         * @param log The error log.
    429         */
    430        public static void cloneDatamodel(final Datamodel datamodel,
    431                final Context ctx, final Evaluator evaluator,
    432                final Log log) {
    433            if (datamodel == null) {
    434                return;
    435            }
    436            List data = datamodel.getData();
    437            if (data == null) {
    438                return;
    439            }
    440            for (Iterator iter = data.iterator(); iter.hasNext();) {
    441                Data datum = (Data) iter.next();
    442                Node datumNode = datum.getNode();
    443                Node valueNode = null;
    444                if (datumNode != null) {
    445                    valueNode = datumNode.cloneNode(true);
    446                }
    447                // prefer "src" over "expr" over "inline"
    448                if (!SCXMLHelper.isStringEmpty(datum.getSrc())) {
    449                    ctx.setLocal(datum.getId(), valueNode);
    450                } else if (!SCXMLHelper.isStringEmpty(datum.
    451                        getExpr())) {
    452                    Object value = null;
    453                    try {
    454                        ctx.setLocal(NAMESPACES_KEY, datum.getNamespaces());
    455                        value = evaluator.eval(ctx, datum.getExpr());
    456                        ctx.setLocal(NAMESPACES_KEY, null);
    457                    } catch (SCXMLExpressionException see) {
    458                        if (log != null) {
    459                            log.error(see.getMessage(), see);
    460                        } else {
    461                            Log defaultLog = LogFactory.getLog(SCXMLHelper.class);
    462                            defaultLog.error(see.getMessage(), see);
    463                        }
    464                    }
    465                    ctx.setLocal(datum.getId(), value);
    466                } else {
    467                    ctx.setLocal(datum.getId(), valueNode);
    468                }
    469            }
    470        }
    471
    472        /**
    473         * Escape XML strings for serialization.
    474         * The basic algorithm is taken from Commons Lang (see oacl.Entities.java)
    475         *
    476         * @param str A string to be escaped
    477         * @return The escaped string
    478         */
    479        public static String escapeXML(final String str) {
    480            if (str == null) {
    481                return null;
    482            }
    483
    484            // Make the writer an arbitrary bit larger than the source string
    485            int len = str.length();
    486            StringWriter stringWriter = new StringWriter(len + 8);
    487
    488            for (int i = 0; i < len; i++) {
    489                char c = str.charAt(i);
    490                String entityName = null; // Look for XML 1.0 predefined entities
    491                switch (c) {
    492                    case '"':
    493                        entityName = "quot";
    494                        break;
    495                    case '&':
    496                        entityName = "amp";
    497                        break;
    498                    case '\'':
    499                        entityName = "apos";
    500                        break;
    501                    case '<':
    502                        entityName = "lt";
    503                        break;
    504                    case '>':
    505                        entityName = "gt";
    506                        break;
    507                    default:
    508                }
    509                if (entityName == null) {
    510                    if (c > 0x7F) {
    511                        stringWriter.write("&#");
    512                        stringWriter.write(Integer.toString(c));
    513                        stringWriter.write(';');
    514                    } else {
    515                        stringWriter.write(c);
    516                    }
    517                } else {
    518                    stringWriter.write('&');
    519                    stringWriter.write(entityName);
    520                    stringWriter.write(';');
    521                }
    522            }
    523
    524            return stringWriter.toString();
    525        }
    526
    527        /**
    528         * Discourage instantiation since this is a utility class.
    529         */
    530        private SCXMLHelper() {
    531            super();
    532        }
    533
    534        /**
    535         * Current document namespaces are saved under this key in the parent
    536         * state's context.
    537         */
    538        private static final String NAMESPACES_KEY = "_ALL_NAMESPACES";
    539
    540    }
    541