auth/auth-core/src/main/java/org/onap/aaf/auth/rserv/Match.java

   1 /**
   2  * ============LICENSE_START====================================================
   3  * org.onap.aaf
   4  * ===========================================================================
   5  * Copyright (c) 2018 AT&T Intellectual Property. All rights reserved.
   6  * ===========================================================================
   7  * Licensed under the Apache License, Version 2.0 (the "License");
   8  * you may not use this file except in compliance with the License.
   9  * You may obtain a copy of the License at
  10  *
  11  *      http://www.apache.org/licenses/LICENSE-2.0
  12  *
  13  * Unless required by applicable law or agreed to in writing, software
  14  * distributed under the License is distributed on an "AS IS" BASIS,
  15  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  16  * See the License for the specific language governing permissions and
  17  * limitations under the License.
  18  * ============LICENSE_END====================================================
  19  *
  20  */
  21
  22 package org.onap.aaf.auth.rserv;
  23
  24 import java.util.HashMap;
  25 import java.util.Map;
  26 import java.util.Set;
  27
  28 /**
  29  * This path matching algorithm avoids using split strings during the critical transactional run-time.  By pre-analyzing the
  30  * content at "set Param" time, and storing data in an array-index model which presumably is done once and at the beginning,
  31  * we can match in much less time when it actually counts.
  32  *
  33  * @author Jonathan
  34  *
  35  */
  36 public class Match {
  37     private Map<String, Integer> params;
  38     private byte[][] values;
  39     private Integer[] vars;
  40     private boolean wildcard;
  41
  42
  43     /*
  44      * These two methods are pairs of searching performance for variables Spark Style.
  45      * setParams evaluates the target path, and sets a HashMap that will return an Integer.
  46      * the Keys are both :key and key so that there will be no string operations during
  47      * a transaction
  48      *
  49      * For the Integer, if the High Order is 0, then it is just one value.  If High Order >0, then it is
  50      * a multi-field option, i.e. ending with a wild-card.
  51      */
  52     public Match(String path) {
  53         params = new HashMap<>();
  54         if (path!=null) {
  55             String[] pa = path.split("/");
  56             values = new byte[pa.length][];
  57             vars = new Integer[pa.length];
  58
  59             int val = 0;
  60             String key;
  61             for (int i=0;i<pa.length && !wildcard;++i) {
  62                 if (pa[i].startsWith(":")) {
  63                     if (pa[i].endsWith("*")) {
  64                         val = i | pa.length<<16; // load end value in high order bits
  65                         key = pa[i].substring(0, pa[i].length()-1);// remove *
  66                         wildcard = true;
  67                     } else {
  68                         val = i;
  69                         key = pa[i];
  70                     }
  71                     params.put(key,val); //put in :key
  72                     params.put(key.substring(1,key.length()), val); // put in just key, better than adding a missing one, like Spark
  73                     // values[i]=null; // null stands for Variable
  74                     vars[i]=val;
  75                 } else {
  76                     values[i]=pa[i].getBytes();
  77                     if (pa[i].endsWith("*")) {
  78                         wildcard = true;
  79                         if (pa[i].length()>1) {
  80                             /* remove * from value */
  81                             int newlength = values[i].length-1;
  82                             byte[] real = new byte[newlength];
  83                             System.arraycopy(values[i],0,real,0,newlength);
  84                             values[i]=real;
  85                         } else {
  86                             vars[i]=0; // this is actually a variable, if it only contains a "*"
  87                         }
  88                     }
  89                 }
  90             }
  91         }
  92     }
  93
  94     /*
  95      * This is the second of the param evaluation functions.  First, we look up to see if there is
  96      * any reference by key in the params Map created by the above.
  97      *
  98      * The resulting Integer, if not null, is split high/low order into start and end.
  99      * We evaluate the string for '/', rather than splitting into  String[] to avoid the time/mem needed
 100      * We traverse to the proper field number for slash, evaluate the end (whether wild card or no),
 101      * and return the substring.
 102      *
 103      * The result is something less than .003 milliseconds per evaluation
 104      *
 105      */
 106     public String param(String path,String key) {
 107         Integer val = params.get(key); // :key or key
 108         if (val!=null) {
 109             int start = val & 0xFFFF;
 110             int end = (val >> 16) & 0xFFFF;
 111             int idx = -1;
 112             int i;
 113             for (i=0;i<start;++i) {
 114                 idx = path.indexOf('/',idx+1);
 115                 if (idx<0)break;
 116             }
 117             if (i==start) {
 118                 ++idx;
 119                 if (end==0) {
 120                     end = path.indexOf('/',idx);
 121                     if (end<0)end=path.length();
 122                 } else {
 123                     end=path.length();
 124                 }
 125                 return path.substring(idx,end);
 126             } else if (i==start-1) { // if last spot was left blank, i.e. :key*
 127                 return "";
 128             }
 129         }
 130         return null;
 131     }
 132
 133     public boolean match(String path) {
 134         if (path==null|| path.length()==0 || "/".equals(path) ) {
 135             if (values==null)return true;
 136             switch(values.length) {
 137                 case 0: return true;
 138                 case 1: return values[0].length==0;
 139                 default: return false;
 140             }
 141         }
 142         boolean rv = true;
 143         byte[] pabytes = path.getBytes();
 144         int field=0;
 145         int fieldIdx = 0;
 146
 147         int lastField = values.length;
 148         int lastByte = pabytes.length;
 149         boolean fieldMatched = false;
 150         for (int i=0;rv && i<lastByte;++i) {
 151             if (field>=lastField) { // checking here allows there to be a non-functional ending /
 152                 rv = false;
 153                 break;
 154             }
 155             if (values[field]==null) { // it's a variable, just look for /s
 156                 if (wildcard && field==lastField-1) return true;// we've made it this far.  We accept all remaining characters
 157                 Integer val = vars[field];
 158                 int start = val & 0xFFFF;
 159                 int end = (val >> 16) & 0xFFFF;
 160                 if (end==0)end=start+1;
 161                 int k = i;
 162                 for (int j=start; j<end && k<lastByte; ++k) {
 163                     if (pabytes[k]=='/') {
 164                         ++field;
 165                         ++j;
 166                     }
 167                 }
 168
 169                 if (k==lastByte && pabytes[k-1]!='/')++field;
 170                 if (k>i)i=k-1; // if we've incremented, have to accommodate the outer for loop incrementing as well
 171                 fieldMatched = false; // reset
 172                 fieldIdx = 0;
 173             } else {
 174                 if (pabytes[i]=='/') { // end of field, eval if Field is matched
 175                     // if double slash, check if supposed to be empty
 176                     if (fieldIdx==0 && values[field].length==0) {
 177                         fieldMatched = true;
 178                     }
 179                     rv = fieldMatched && ++field<lastField;
 180                     // reset
 181                     fieldMatched = false;
 182                     fieldIdx = 0;
 183                 } else if (values[field].length==0) {
 184                     // double slash in path, but content in field.  We check specially here to avoid
 185                     // Array out of bounds issues.
 186                     rv = false;
 187                 } else {
 188                     if (fieldMatched) {
 189                         rv =false; // field is already matched, now there's too many bytes
 190                     } else {
 191                         rv = pabytes[i]==values[field][fieldIdx++]; // compare expected (pabytes[i]) with value for particular field
 192                         fieldMatched=values[field].length==fieldIdx; // are all the bytes match in the field?
 193                         if (fieldMatched && (i==lastByte-1 || (wildcard && field==lastField-1)))
 194                             return true; // last field info
 195                     }
 196                 }
 197             }
 198         }
 199         if (field!=lastField || pabytes.length!=lastByte) rv = false; // have we matched all the fields and all the bytes?
 200         return rv;
 201     }
 202
 203     public Set<String> getParamNames() {
 204         return params.keySet();
 205     }
 206 }