    001    /* $Id: ExtendedBaseRules.java 729096 2008-12-23 20:35:24Z rahul $
    002     *
    003     * Licensed to the Apache Software Foundation (ASF) under one or more
    004     * contributor license agreements.  See the NOTICE file distributed with
    005     * this work for additional information regarding copyright ownership.
    006     * The ASF licenses this file to You under the Apache License, Version 2.0
    007     * (the "License"); you may not use this file except in compliance with
    008     * the License.  You may obtain a copy of the License at
    009     *
    010     *      http://www.apache.org/licenses/LICENSE-2.0
    011     *
    012     * Unless required by applicable law or agreed to in writing, software
    013     * distributed under the License is distributed on an "AS IS" BASIS,
    014     * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
    015     * See the License for the specific language governing permissions and
    016     * limitations under the License.
    017     */
    018
    019
    020    package org.apache.commons.digester;
    021
    022
    023    import java.util.ArrayList;
    024    import java.util.Collections;
    025    import java.util.Comparator;
    026    import java.util.HashMap;
    027    import java.util.Iterator;
    028    import java.util.List;
    029    import java.util.Map;
    030
    031
    032    /**
    033     * <p>Extension of {@link RulesBase} for complex schema.</p>
    034     *
    035     * <p>This is an extension of the basic pattern matching scheme
    036     * intended to improve support for mapping complex xml-schema.
    037     * It is intended to be a minimal extension of the standard rules
    038     * big enough to support complex schema but without the full generality
    039     * offered by more exotic matching pattern rules.</p>
    040     *
    041     * <h4>When should you use this rather than the original?</h4>
    042     *
    043     * <p>
    044     * This pattern-matching engine is complex and slower than the basic
    045     * default RulesBase class, but offers more functionality:
    046     * <ul>
    047     * <li>Universal patterns allow patterns to be specified which will match
    048     *  regardless of whether there are "better matching" patterns available.</li>
    049     * <li>Parent-match patterns (eg "a/b/?") allow matching for all direct
    050     *  children of a specified element.</li>
    051     * <li>Ancestor-match patterns (eg "a/b/*") allow matching all elements
    052     *  nested within a specified element to any nesting depth.</li>
    053     * <li>Completely-wild patterns ("*" or "!*") allow matching all elements.</li>
    054     * </ul>
    055     * </p>
    056     *
    057     * <h4>Universal Match Patterns</h4>
    058     *
    059     * <p>The default RulesBase pattern-matching engine always attempts to find
    060     * the "best matching pattern", and will ignore rules associated with other
    061     * patterns that match but are not "as good". As an example, if the pattern
    062     * "a/b/c" is associated with rules 1 and 2, and "*&#47;c" is associated with
    063     * rules 3 and 4 then element "a/b/c" will cause only rules 1 and 2 to execute.
    064     * Rules 3 and 4 do have matching patterns, but because the patterns are shorter
    065     * and include wildcard characters they are regarded as being "not as good" as
    066     * a direct match. In general, exact patterns are better than wildcard patterns,
    067     * and among multiple patterns with wildcards, the longest is preferred.
    068     * See the RulesBase class for more information.</p>
    069     *
    070     * <p>This feature of preferring "better" patterns can be a powerful tool.
    071     * However it also means that patterns can interact in unexpected ways.</p>
    072     *
    073     * <p>When using the ExtendedBaseRules, any pattern prefixed with '!' bypasses
    074     * the "best match" feature. Even if there is an exact match or a longer
    075     * wildcard match, patterns prefixed by '!' will still be tested to see if
    076     * they match, and if so their associated Rule objects will be included in
    077     * the set of rules to be executed in the normal manner.</p>
    078     *
    079     * <ul>
    080     * <li>Pattern <code>"!*&#47;a/b"</code> matches whenever an 'b' element
    081     *     is inside an 'a'.</li>
    082     * <li>Pattern <code>"!a/b/?"</code> matches any child of a parent
    083     *     matching <code>"a/b"</code> (see "Parent Match Patterns").</li>
    084     * <li>Pattern <code>"!*&#47;a/b/?"</code> matches any child of a parent
    085     *     matching <code>"!*&#47;a/b"</code> (see "Parent Match Patterns").</li>
    086     * <li>Pattern <code>"!a/b/*"</code> matches any element whose path
    087     *     starts with "a" then "b" (see "Ancestor Match Patterns").</li>
    088     * <li>Pattern <code>"!*&#47;a/b/*"</code> matches any elements whose path
    089     *     contains 'a/b' (see "Ancestor Match Patterns").</li>
    090     * </ul>
    091     *
    092     * <h4>Parent Match Patterns</h4>
    093     *
    094     * <p>
    095     * These will match direct child elements of a particular parent element.
    096     * <ul>
    097     * <li>
    098     *  <code>"a/b/c/?"</code> matches any child whose parent matches
    099     *  <code>"a/b/c"</code>.  Exact parent rules take precedence over Ancestor
    100     *  Match patterns.
    101     * </li>
    102     * <li>
    103     *  <code>"*&#47;a/b/c/?"</code> matches any child whose parent matches
    104     *  <code>"*&#47;a/b/c"</code>.  The longest matching still applies to parent
    105     *  matches but the length excludes the '?', which effectively means
    106     *  that standard wildcard matches with the same level of depth are
    107     *  chosen in preference.
    108     * </li>
    109     * </ul>
    110     * </p>
    111     *
    112     * <h4>Ancestor Match Patterns</h4>
    113     *
    114     * <p>
    115     * These will match elements whose parentage includes a particular sequence
    116     * of elements.
    117     * <ul>
    118     * <li>
    119     *  <code>"a/b/*"</code> matches any element whose path starts with
    120     *  'a' then 'b'. Exact parent and parent match rules take precedence.
    121     *  The longest ancestor match will take precedence.
    122     * </li>
    123     * <li>
    124     *  <code>"*&#47;a/b/*"</code> matches any elements whose path contains
    125     *  an element 'a' followed by an element 'b'. The longest matching still
    126     *  applies but the length excludes the '*' at the end.
    127     * </li>
    128     * </ul>
    129     * </p>
    130     *
    131     * <h4>Completely Wild Patterns</h4>
    132     *
    133     * <p>Pattern <code>"*"</code> matches every pattern that isn't matched by
    134     * any other basic rule.</p>
    135     *
    136     * <p>Pattern <code>"!*"</code> matches every pattern.</p>
    137     *
    138     * <h4>Using The Extended Rules</h4>
    139     *
    140     * <p>By default, a Digester instance uses a {@link RulesBase} instance as
    141     * its pattern matching engine. To use an ExtendedBaseRules instance, call
    142     * the Digester.setRules method before adding any Rule objects to the digester
    143     * instance:
    144     * <pre>
    145     *     Digester digester = new Digester();
    146     *     digester.setRules( new ExtendedBaseRules() );
    147     * </pre></p>
    148     *
    149     * <p>The most important thing to remember when using the extended rules is
    150     * that universal and non-universal patterns are completely independent.
    151     * Universal patterns are never affected by the addition of new patterns
    152     * or the removal of existing ones. Non-universal patterns are never affected
    153     * by the addition of new <em>universal</em> patterns or the removal of
    154     * existing <em>universal</em> patterns. As in the basic matching rules,
    155     * non-universal (basic) patterns <strong>can</strong> be affected by the
    156     * addition of new <em>non-universal</em> patterns or the removal of existing
    157     * <em>non-universal</em> patterns, because only rules associated with the
    158     * "best matching" pattern for each xml element are executed.
    159     *
    160     * <p> This means that you can use universal patterns to build up the simple
    161     * parts of your structure - for example defining universal creation and
    162     * property setting rules. More sophisticated and complex mapping will require
    163     * non-universal patterns and this might mean that some of the universal rules
    164     * will need to be replaced by a series of special cases using non-universal
    165     * rules. But by using universal rules as your backbone, these additions
    166     * should not break your existing rules.</p>
    167     */
    168
    169
    170    public class ExtendedBaseRules extends RulesBase {
    171
    172
    173        // ----------------------------------------------------- Instance Variables
    174
    175        /**
    176         * Counts the entry number for the rules.
    177         */
    178        private int counter = 0;
    179
    180
    181        /**
    182         * The decision algorithm used (unfortunately) doesn't preserve the entry
    183         * order.
    184         * This map is used by a comparator which orders the list of matches
    185         * before it's returned.
    186         * This map stores the entry number keyed by the rule.
    187         */
    188        private Map<Rule, Integer> order = new HashMap<Rule, Integer>();
    189
    190
    191        // --------------------------------------------------------- Public Methods
    192
    193
    194        /**
    195         * Register a new Rule instance matching the specified pattern.
    196         *
    197         * @param pattern Nesting pattern to be matched for this Rule
    198         * @param rule Rule instance to be registered
    199         */
    200        public void add(String pattern, Rule rule) {
    201            super.add(pattern, rule);
    202            counter++;
    203            order.put(rule, counter);
    204        }
    205
    206
    207        /**
    208         * Return a List of all registered Rule instances that match the specified
    209         * nesting pattern, or a zero-length List if there are no matches.  If more
    210         * than one Rule instance matches, they <strong>must</strong> be returned
    211         * in the order originally registered through the <code>add()</code>
    212         * method.
    213         *
    214         * @param pattern Nesting pattern to be matched
    215         */
    216        public List<Rule> match(String namespace, String pattern) {
    217            // calculate the pattern of the parent
    218            // (if the element has one)
    219            String parentPattern = "";
    220            int lastIndex = pattern.lastIndexOf('/');
    221
    222            boolean hasParent = true;
    223            if (lastIndex == -1) {
    224                // element has no parent
    225                hasParent = false;
    226
    227            } else {
    228                // calculate the pattern of the parent
    229                parentPattern = pattern.substring(0, lastIndex);
    230
    231            }
    232
    233
    234            // we keep the list of universal matches separate
    235            List<Rule> universalList = new ArrayList<Rule>(counter);
    236
    237            // Universal all wildards ('!*')
    238            // These are always matched so always add them
    239            List<Rule> tempList = this.cache.get("!*");
    240            if (tempList != null) {
    241                universalList.addAll(tempList);
    242            }
    243
    244            // Universal exact parent match
    245            // need to get this now since only wildcards are considered later
    246            tempList = this.cache.get("!" + parentPattern + "/?");
    247            if (tempList != null) {
    248                universalList.addAll(tempList);
    249            }
    250
    251
    252            // base behaviour means that if we certain matches, we don't continue
    253            // but we just have a single combined loop and so we have to set
    254            // a variable
    255            boolean ignoreBasicMatches = false;
    256
    257
    258            // see if we have an exact basic pattern match
    259            List<Rule> rulesList = this.cache.get(pattern);
    260            if (rulesList != null) {
    261                // we have a match!
    262                // so ignore all basic matches from now on
    263                ignoreBasicMatches = true;
    264
    265            } else {
    266
    267                // see if we have an exact child match
    268                if (hasParent) {
    269                    // matching children takes preference
    270                    rulesList = this.cache.get(parentPattern + "/?");
    271                    if (rulesList != null) {
    272                        // we have a match!
    273                        // so ignore all basic matches from now on
    274                        ignoreBasicMatches = true;
    275
    276                    } else {
    277                        // we don't have a match yet - so try exact ancester
    278                        //
    279                        rulesList = findExactAncesterMatch(pattern);
    280                        if (rulesList != null) {
    281                            // we have a match!
    282                            // so ignore all basic matches from now on
    283                            ignoreBasicMatches = true;
    284                        }
    285                    }
    286                }
    287            }
    288
    289
    290            // OK - we're ready for the big loop!
    291            // Unlike the basic rules case,
    292            // we have to go through for all those universal rules in all cases.
    293
    294            // Find the longest key, ie more discriminant
    295            String longKey = "";
    296            int longKeyLength = 0;
    297
    298            for (String key : this.cache.keySet()) {
    299
    300                // find out if it's a univeral pattern
    301                // set a flag
    302                boolean isUniversal = key.startsWith("!");
    303                if (isUniversal) {
    304                    // and find the underlying key
    305                    key = key.substring(1, key.length());
    306                }
    307
    308
    309                // don't need to check exact matches
    310                boolean wildcardMatchStart = key.startsWith("*/");
    311                boolean wildcardMatchEnd = key.endsWith("/*");
    312                if (wildcardMatchStart || (isUniversal && wildcardMatchEnd)) {
    313
    314                    boolean parentMatched = false;
    315                    boolean basicMatched = false;
    316                    boolean ancesterMatched = false;
    317
    318                    boolean parentMatchEnd = key.endsWith("/?");
    319                    if (parentMatchEnd) {
    320                        // try for a parent match
    321                        parentMatched = parentMatch(key, pattern, parentPattern);
    322
    323                    } else if (wildcardMatchEnd) {
    324                        // check for ancester match
    325                        if (wildcardMatchStart) {
    326                            String patternBody = key.substring(2, key.length() - 2);
    327                            if (pattern.endsWith(patternBody)) {
    328                                ancesterMatched = true;
    329                            } else {
    330                                ancesterMatched = (pattern.indexOf(patternBody + "/") > -1);
    331                            }
    332                        } else {
    333                            String bodyPattern = key.substring(0, key.length() - 2);
    334                            if (pattern.startsWith(bodyPattern))
    335                            {
    336                                if (pattern.length() == bodyPattern.length()) {
    337                                    // exact match
    338                                    ancesterMatched = true;
    339                                } else {
    340                                    ancesterMatched = ( pattern.charAt(bodyPattern.length()) == '/' );
    341                                }
    342                            } else {
    343                                ancesterMatched = false;
    344                            }
    345                        }
    346                    } else {
    347                        // try for a base match
    348                        basicMatched = basicMatch(key, pattern);
    349                    }
    350
    351                    if (parentMatched || basicMatched || ancesterMatched) {
    352                        if (isUniversal) {
    353                            // universal rules go straight in
    354                            // (no longest matching rule)
    355                            tempList = this.cache.get("!" + key);
    356                            if (tempList != null) {
    357                                universalList.addAll(tempList);
    358                            }
    359
    360                        } else {
    361                            if (!ignoreBasicMatches) {
    362                                // ensure that all parent matches are SHORTER
    363                                // than rules with same level of matching.
    364                                //
    365                                // the calculations below don't work for universal
    366                                // matching, but we don't care because in that case
    367                                // this if-stmt is not entered.
    368                                int keyLength = key.length();
    369                                if (wildcardMatchStart) {
    370                                    --keyLength;
    371                                }
    372                                if (wildcardMatchEnd) {
    373                                    --keyLength;
    374                                } else if (parentMatchEnd) {
    375                                    --keyLength;
    376                                }
    377
    378                                if (keyLength > longKeyLength) {
    379                                    rulesList = this.cache.get(key);
    380                                    longKey = key;
    381                                    longKeyLength = keyLength;
    382                                }
    383                            }
    384                        }
    385                    }
    386                }
    387            }
    388
    389
    390            // '*' works in practice as a default matching
    391            // (this is because anything is a deeper match!)
    392            if (rulesList == null) {
    393                rulesList = this.cache.get("*");
    394            }
    395
    396            // if we've matched a basic pattern, then add to the universal list
    397            if (rulesList != null) {
    398                universalList.addAll(rulesList);
    399            }
    400
    401
    402            // don't filter if namespace is null
    403            if (namespace != null) {
    404                // remove invalid namespaces
    405                Iterator<Rule> it = universalList.iterator();
    406                while (it.hasNext()) {
    407                    Rule rule = it.next();
    408                    String ns_uri = rule.getNamespaceURI();
    409                    if (ns_uri != null && !ns_uri.equals(namespace)) {
    410                        it.remove();
    411                    }
    412                }
    413            }
    414
    415
    416            // need to make sure that the collection is sort in the order
    417            // of addition.  We use a custom comparator for this
    418            Collections.sort(
    419                    universalList,
    420                    new Comparator<Rule>() {
    421
    422                        public int compare(Rule r1, Rule r2) throws ClassCastException {
    423                            // Get the entry order from the map
    424                            Integer i1 = order.get(r1);
    425                            Integer i2 = order.get(r2);
    426
    427                            // and use that to perform the comparison
    428                            if (i1 == null) {
    429                                if (i2 == null) {
    430
    431                                    return 0;
    432
    433                                } else {
    434
    435                                    return -1;
    436
    437                                }
    438                            } else if (i2 == null) {
    439                                return 1;
    440                            }
    441
    442                            return (i1.intValue() - i2.intValue());
    443                        }
    444                    });
    445
    446            return universalList;
    447        }
    448
    449        /**
    450         * Matching parent.
    451         */
    452        private boolean parentMatch(String key, String pattern, String parentPattern) {
    453            return parentPattern.endsWith(key.substring(1, key.length() - 2));
    454        }
    455
    456        /**
    457         * Standard match.
    458         * Matches the end of the pattern to the key.
    459         */
    460        private boolean basicMatch(String key, String pattern) {
    461            return (pattern.equals(key.substring(2)) ||
    462                    pattern.endsWith(key.substring(1)));
    463        }
    464
    465        /**
    466         * Finds an exact ancester match for given pattern
    467         */
    468        private List<Rule> findExactAncesterMatch(String parentPattern) {
    469            List<Rule> matchingRules = null;
    470            int lastIndex = parentPattern.length();
    471            while (lastIndex-- > 0) {
    472                lastIndex = parentPattern.lastIndexOf('/', lastIndex);
    473                if (lastIndex > 0) {
    474                    matchingRules = this.cache.get(parentPattern.substring(0, lastIndex) + "/*");
    475                    if (matchingRules != null) {
    476                        return matchingRules;
    477                    }
    478                }
    479            }
    480            return null;
    481        }
    482    }