Coverage Report - org.simpleframework.xml.util.Resolver
 
Classes in this File Line Coverage Branch Coverage Complexity
Resolver
83%
50/60
84%
42/50
2.895
Resolver$1
N/A
N/A
2.895
Resolver$Cache
100%
3/3
N/A
2.895
Resolver$Stack
100%
9/9
N/A
2.895
Resolver$Stack$Sequence
90%
9/10
75%
3/4
2.895
 
 1  
 /*
 2  
  * Resolver.java February 2001
 3  
  *
 4  
  * Copyright (C) 2001, Niall Gallagher <niallg@users.sf.net>
 5  
  *
 6  
  * Licensed under the Apache License, Version 2.0 (the "License");
 7  
  * you may not use this file except in compliance with the License.
 8  
  * You may obtain a copy of the License at
 9  
  *
 10  
  *     http://www.apache.org/licenses/LICENSE-2.0
 11  
  *
 12  
  * Unless required by applicable law or agreed to in writing, software
 13  
  * distributed under the License is distributed on an "AS IS" BASIS,
 14  
  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or 
 15  
  * implied. See the License for the specific language governing 
 16  
  * permissions and limitations under the License.
 17  
  */
 18  
  
 19  
 package org.simpleframework.xml.util;
 20  
 
 21  
 import java.util.AbstractSet;
 22  
 import java.util.ArrayList;
 23  
 import java.util.Iterator;
 24  
 import java.util.LinkedList;
 25  
 import java.util.List;
 26  
 
 27  
 /**
 28  
  * This is used to store <code>Match</code> objects, which can then be
 29  
  * retrieved using a string by comparing that string to the pattern of
 30  
  * the <code>Match</code> objects. Patterns consist of characters
 31  
  * with either the '*' or '?' characters as wild characters. The '*'
 32  
  * character is completely wild meaning that is will match nothing or
 33  
  * a long sequence of characters. The '?' character matches a single
 34  
  * character.
 35  
  * <p>
 36  
  * If the '?' character immediately follows the '*' character then the
 37  
  * match is made as any sequence of characters up to the first match 
 38  
  * of the next character. For example "/*?/index.jsp" will match all 
 39  
  * files preceeded by only a single path. So "/pub/index.jsp" will
 40  
  * match, however "/pub/bin/index.jsp" will not, as it has two paths.
 41  
  * So, in effect the '*?' sequence will match anything or nothing up
 42  
  * to the first occurence of the next character in the pattern.
 43  
  * <p>
 44  
  * A design goal of the <code>Resolver</code> was to make it capable
 45  
  * of  high performance. In order to achieve a high performance the 
 46  
  * <code>Resolver</code> can cache the resolutions it makes so that if
 47  
  * the same text is given to the <code>Resolver.resolve</code> method 
 48  
  * a cached result can be retrived quickly which will decrease the 
 49  
  * length of time and work required to perform the match.
 50  
  * <p>
 51  
  * The semantics of the resolver are such that the last pattern added
 52  
  * with a wild string is the first one checked for a match. This means
 53  
  * that if a sequence of insertions like <code>add(x)</code> followed
 54  
  * by <code>add(y)</code> is made, then a <code>resolve(z)</code> will
 55  
  * result in a comparison to y first and then x, if z matches y then 
 56  
  * it is given as the result and if z does not match y and matches x 
 57  
  * then x is returned, remember if z matches both x and y then y will 
 58  
  * be the result due to the fact that is was the last pattern added.
 59  
  *
 60  
  * @author Niall Gallagher
 61  
  */
 62  60
 public class Resolver<M extends Match> extends AbstractSet<M> {
 63  
 
 64  
    /**
 65  
     * Caches the text resolutions made to reduce the work required.
 66  
     */        
 67  
    protected final Cache cache;
 68  
 
 69  
    /**
 70  
     * Stores the matches added to the resolver in resolution order.
 71  
     */ 
 72  
    protected final Stack stack;
 73  
 
 74  
    /**
 75  
     * The default constructor will create a <code>Resolver</code>
 76  
     * without a large cache size. This is intended for use when 
 77  
     * the requests for <code>resolve</code> tend to use strings
 78  
     * that are reasonably similar. If the strings issued to this
 79  
     * instance are dramatically different then the cache tends 
 80  
     * to be an overhead rather than a bonus.
 81  
     */
 82  9
    public Resolver(){
 83  9
       this.stack = new Stack();
 84  9
       this.cache = new Cache(); 
 85  9
    }
 86  
 
 87  
    /**
 88  
     * This will search the patterns in this <code>Resolver</code> to
 89  
     * see if there is a pattern in it that matches the string given.
 90  
     * This will search the patterns from the last entered pattern to
 91  
     * the first entered. So that the last entered patterns are the
 92  
     * most searched patterns and will resolve it first if it matches.
 93  
     *
 94  
     * @param text this is the string that is to be matched by this
 95  
     *
 96  
     * @return this will return the first match within the resolver
 97  
     */
 98  
    public M resolve(String text){
 99  18
       List<M> list = cache.get(text);
 100  
       
 101  18
       if(list == null) {
 102  17
          list = resolveAll(text);
 103  
       }
 104  18
       if(list.isEmpty()) {
 105  2
          return null;
 106  
       }
 107  16
       return list.get(0);
 108  
    }
 109  
    
 110  
    /**
 111  
     * This will search the patterns in this <code>Resolver</code> to
 112  
     * see if there is a pattern in it that matches the string given.
 113  
     * This will search the patterns from the last entered pattern to
 114  
     * the first entered. So that the last entered patterns are the
 115  
     * most searched patterns and will resolve it first if it matches.
 116  
     *
 117  
     * @param text this is the string that is to be matched by this
 118  
     *
 119  
     * @return this will return all of the matches within the resolver
 120  
     */
 121  
    public List<M> resolveAll(String text){
 122  17
       List<M> list = cache.get(text);
 123  
       
 124  17
       if(list != null) {
 125  0
          return list;
 126  
       }
 127  17
       char[] array = text.toCharArray();
 128  
   
 129  17
       if(array == null) {
 130  0
          return null;
 131  
       }
 132  17
       return resolveAll(text, array);
 133  
    }
 134  
    
 135  
    /**
 136  
     * This will search the patterns in this <code>Resolver</code> to
 137  
     * see if there is a pattern in it that matches the string given.
 138  
     * This will search the patterns from the last entered pattern to
 139  
     * the first entered. So that the last entered patterns are the
 140  
     * most searched patterns and will resolve it first if it matches.
 141  
     *
 142  
     * @param text this is the string that is to be matched by this
 143  
     * @param array this is the character array of the text string
 144  
     *
 145  
     * @return this will return all of the matches within the resolver
 146  
     */
 147  
    private List<M> resolveAll(String text, char[] array){
 148  17
       List<M> list = new ArrayList<M>();
 149  
       
 150  17
       for(M match : stack) {
 151  4113
          String wild = match.getPattern();
 152  
 
 153  4113
          if(match(array, wild.toCharArray())){
 154  22
             cache.put(text, list);
 155  22
             list.add(match);
 156  
          }
 157  4113
       }
 158  17
       return list;
 159  
    }
 160  
 
 161  
    /**
 162  
     * This inserts the <code>Match</code> implementation into the set
 163  
     * so that it can be used for resolutions. The last added match is
 164  
     * the first resolved. Because this changes the state of the 
 165  
     * resolver this clears the cache as it may affect resolutions.
 166  
     *
 167  
     * @param match this is the match that is to be inserted to this
 168  
     *
 169  
     * @return returns true if the addition succeeded, always true
 170  
     */ 
 171  
    public boolean add(M match) {
 172  2065
       stack.push(match);
 173  2065
       return true;
 174  
    }
 175  
    
 176  
    /**
 177  
     * This returns an <code>Iterator</code> that iterates over the
 178  
     * matches in insertion order. So the first match added is the
 179  
     * first retrieved from the <code>Iterator</code>. This order is
 180  
     * used to ensure that resolver can be serialized properly.
 181  
     *
 182  
     * @return returns an iterator for the sequence of insertion
 183  
     */ 
 184  
    public Iterator<M> iterator() {
 185  11
       return stack.sequence();
 186  
    }
 187  
 
 188  
    /**
 189  
     * This is used to remove the <code>Match</code> implementation
 190  
     * from the resolver. This clears the cache as the removal of
 191  
     * a match may affect the resoultions existing in the cache. The
 192  
     * <code>equals</code> method of the match must be implemented.
 193  
     *
 194  
     * @param match this is the match that is to be removed
 195  
     *
 196  
     * @return true of the removal of the match was successful
 197  
     */ 
 198  
    public boolean remove(M match) {
 199  0
       cache.clear();
 200  0
       return stack.remove(match);
 201  
    }
 202  
 
 203  
    /**
 204  
     * Returns the number of matches that have been inserted into 
 205  
     * the <code>Resolver</code>. Although this is a set, it does 
 206  
     * not mean that matches cannot used the same pattern string.
 207  
     *
 208  
     * @return this returns the number of matches within the set
 209  
     */ 
 210  
    public int size() {
 211  5
       return stack.size();           
 212  
    }
 213  
    
 214  
    /**
 215  
     * This is used to clear all matches from the set. This ensures
 216  
     * that the resolver contains no matches and that the resolution 
 217  
     * cache is cleared. This is used to that the set can be reused
 218  
     * and have new pattern matches inserted into it for resolution.
 219  
     */ 
 220  
    public void clear() {
 221  0
       cache.clear();      
 222  0
       stack.clear();
 223  0
    }
 224  
 
 225  
    /**
 226  
     * This acts as a driver to the <code>match</code> method so that
 227  
     * the offsets can be used as zeros for the start of matching for 
 228  
     * the <code>match(char[],int,char[],int)</code>. method. This is
 229  
     * also used as the initializing driver for the recursive method.
 230  
     *
 231  
     * @param text this is the buffer that is to be resolved
 232  
     * @param wild this is the pattern that will be used
 233  
     */
 234  
    private boolean match(char[] text, char[] wild){
 235  4113
       return match(text, 0, wild, 0);
 236  
    }
 237  
 
 238  
    /**
 239  
     * This will be used to check to see if a certain buffer matches
 240  
     * the pattern if it does then it returns <code>true</code>. This
 241  
     * is a recursive method that will attempt to match the buffers 
 242  
     * based on the wild characters '?' and '*'. If there is a match
 243  
     * then this returns <code>true</code>.
 244  
     *
 245  
     * @param text this is the buffer that is to be resolved
 246  
     * @param off this is the read offset for the text buffer
 247  
     * @param wild this is the pattern that will be used
 248  
     * @param pos this is the read offset for the wild buffer
 249  
     */
 250  
    private boolean match(char[] text, int off, char[] wild, int pos){
 251  5572
       while(pos < wild.length && off < text.length){ /* examine chars */
 252  4446
          if(wild[pos] == '*'){
 253  149
             while(wild[pos] == '*'){ /* totally wild */
 254  87
                if(++pos >= wild.length) /* if finished */
 255  9
                   return true;
 256  
             }
 257  62
             if(wild[pos] == '?') { /* *? is special */
 258  2
                if(++pos >= wild.length)                    
 259  0
                   return true;
 260  
             }
 261  1416
             for(; off < text.length; off++){ /* find next matching char */
 262  689
                if(text[off] == wild[pos] || wild[pos] == '?'){ /* match */
 263  58
                   if(wild[pos - 1] != '?'){
 264  56
                      if(match(text, off, wild, pos))
 265  10
                         return true;
 266  
                   } else {
 267  
                      break;                          
 268  
                   }
 269  
                }
 270  
             }
 271  52
             if(text.length == off)
 272  50
                return false;
 273  
          }
 274  4377
          if(text[off++] != wild[pos++]){
 275  2974
             if(wild[pos-1] != '?')
 276  2974
                return false; /* if not equal */
 277  
          }
 278  
       }
 279  1126
       if(wild.length == pos){ /* if wild is finished */
 280  16
           return text.length == off; /* is text finished */
 281  
       }
 282  1110
       while(wild[pos] == '*'){ /* ends in all stars */
 283  0
          if(++pos >= wild.length) /* if finished */
 284  0
             return true;
 285  
       }
 286  1110
       return false;
 287  
    }
 288  
 
 289  
 
 290  
    /**
 291  
     * This is used to cache resolutions made so that the matches can
 292  
     * be acquired the next time without performing the resolution.
 293  
     * This is an LRU cache so regardless of the number of resolutions
 294  
     * made this will not result in a memory leak for the resolver.
 295  
     * 
 296  
     * @author Niall Gallagher
 297  
     */ 
 298  
    private class Cache extends LimitedCache<List<M>> {
 299  
 
 300  
       /**
 301  
        * Constructor for the <code>Cache</code> object. This is a
 302  
        * constructor that creates the linked hash map such that 
 303  
        * it will purge the entries that are oldest within the map.
 304  
        */ 
 305  9
       public Cache() {      
 306  9
          super(1024);              
 307  9
       }
 308  
    }
 309  
 
 310  
    /**
 311  
     * This is used to store the <code>Match</code> implementations in
 312  
     * resolution order. Resolving the match objects is performed so
 313  
     * that the last inserted match object is the first used in the
 314  
     * resolution process. This gives priority to the last inserted.
 315  
     * 
 316  
     * @author Niall Gallagher
 317  
     */ 
 318  18
    private class Stack extends LinkedList<M> {     
 319  
 
 320  
       /**
 321  
        * The <code>push</code> method is used to push the match to 
 322  
        * the top of the stack. This also ensures that the cache is
 323  
        * cleared so the semantics of the resolver are not affected.
 324  
        *
 325  
        * @param match this is the match to be inserted to the stack
 326  
        */            
 327  
       public void push(M match) {
 328  2065
          cache.clear();
 329  2065
          addFirst(match);                       
 330  2065
       }
 331  
 
 332  
       /**
 333  
        * The <code>purge</code> method is used to purge a match from
 334  
        * the provided position. This also ensures that the cache is
 335  
        * cleared so that the semantics of the resolver do not change.
 336  
        *
 337  
        * @param index the index of the match that is to be removed
 338  
        */ 
 339  
       public void purge(int index) {
 340  1
          cache.clear(); 
 341  1
          remove(index);         
 342  1
       }
 343  
 
 344  
       /**
 345  
        * This is returned from the <code>Resolver.iterator</code> so
 346  
        * that matches can be iterated in insertion order. When a
 347  
        * match is removed from this iterator then it clears the cache
 348  
        * and removed the match from the <code>Stack</code> object.
 349  
        * 
 350  
        * @return returns an iterator to iterate in insertion order
 351  
        */ 
 352  
       public Iterator<M> sequence() {
 353  11
          return new Sequence();              
 354  
       }
 355  
 
 356  
       /**
 357  
        * The is used to order the <code>Match</code> objects in the
 358  
        * insertion order. Iterating in insertion order allows the
 359  
        * resolver object to be serialized and deserialized to and
 360  
        * from an XML document without disruption resolution order.
 361  
        *
 362  
        * @author Niall Gallagher
 363  
        */
 364  9
       private class Sequence implements Iterator<M> {
 365  
 
 366  
          /**
 367  
           * The cursor used to acquire objects from the stack.
 368  
           */               
 369  
          private int cursor;
 370  
 
 371  
          /**
 372  
           * Constructor for the <code>Sequence</code> object. This is
 373  
           * used to position the cursor at the end of the list so the
 374  
           * first inserted match is the first returned from this.
 375  
           */ 
 376  11
          public Sequence() {
 377  11
             this.cursor = size();                 
 378  11
          }
 379  
 
 380  
          /**
 381  
           * This returns the <code>Match</code> object at the cursor
 382  
           * position. If the cursor has reached the start of the 
 383  
           * list then this returns null instead of the first match.
 384  
           * 
 385  
           * @return this returns the match from the cursor position
 386  
           */ 
 387  
          public M next() {
 388  84
             if(hasNext()) {
 389  84
                 return get(--cursor);
 390  
             }           
 391  0
             return null;     
 392  
          }    
 393  
 
 394  
          /**
 395  
           * This is used to determine if the cursor has reached the
 396  
           * start of the list. When the cursor reaches the start of
 397  
           * the list then this method returns false.
 398  
           * 
 399  
           * @return this returns true if there are more matches left
 400  
           */ 
 401  
          public boolean hasNext() {
 402  178
             return cursor > 0;
 403  
          }
 404  
 
 405  
          /**
 406  
           * Removes the match from the cursor position. This also
 407  
           * ensures that the cache is cleared so that resolutions
 408  
           * made before the removal do not affect the semantics.
 409  
           */ 
 410  
          public void remove() {                    
 411  1
             purge(cursor);                
 412  1
          }        
 413  
       }
 414  
    } 
 415  
 }