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                 // IF DEBUG: System.out.print("\n[" + path + "]");
  54                 params = new HashMap<String,Integer>();
  55                 if(path!=null) {
  56                         String[] pa = path.split("/");
  57                         values = new byte[pa.length][];
  58                         vars = new Integer[pa.length];
  59
  60                         int val = 0;
  61                         String key;
  62                         for(int i=0;i<pa.length && !wildcard;++i) {
  63                                 if(pa[i].startsWith(":")) {
  64                                         if(pa[i].endsWith("*")) {
  65                                                 val = i | pa.length<<16; // load end value in high order bits
  66                                                 key = pa[i].substring(0, pa[i].length()-1);// remove *
  67                                                 wildcard = true;
  68                                         } else {
  69                                                 val = i;
  70                                                 key = pa[i];
  71                                         }
  72                                         params.put(key,val); //put in :key
  73                                         params.put(key.substring(1,key.length()), val); // put in just key, better than adding a missing one, like Spark
  74                                         // values[i]=null; // null stands for Variable
  75                                         vars[i]=val;
  76                                 } else {
  77                                         values[i]=pa[i].getBytes();
  78                                         if(pa[i].endsWith("*")) {
  79                                                 wildcard = true;
  80                                                 if(pa[i].length()>1) {
  81                                                         /* remove * from value */
  82                                                         int newlength = values[i].length-1;
  83                                                         byte[] real = new byte[newlength];
  84                                                         System.arraycopy(values[i],0,real,0,newlength);
  85                                                         values[i]=real;
  86                                                 } else {
  87                                                         vars[i]=0; // this is actually a variable, if it only contains a "*"
  88                                                 }
  89                                         }
  90                                         // vars[i]=null;
  91                                 }
  92                         }
  93                 }
  94         }
  95
  96         /*
  97          * This is the second of the param evaluation functions.  First, we look up to see if there is
  98          * any reference by key in the params Map created by the above.
  99          *
 100          * The resulting Integer, if not null, is split high/low order into start and end.
 101          * We evaluate the string for '/', rather than splitting into  String[] to avoid the time/mem needed
 102          * We traverse to the proper field number for slash, evaluate the end (whether wild card or no),
 103          * and return the substring.
 104          *
 105          * The result is something less than .003 milliseconds per evaluation
 106          *
 107          */
 108         public String param(String path,String key) {
 109                 Integer val = params.get(key); // :key or key
 110                 if(val!=null) {
 111                         int start = val & 0xFFFF;
 112                         int end = (val >> 16) & 0xFFFF;
 113                         int idx = -1;
 114                         int i;
 115                         for(i=0;i<start;++i) {
 116                                 idx = path.indexOf('/',idx+1);
 117                                 if(idx<0)break;
 118                         }
 119                         if(i==start) {
 120                                 ++idx;
 121                                 if(end==0) {
 122                                         end = path.indexOf('/',idx);
 123                                         if(end<0)end=path.length();
 124                                 } else {
 125                                         end=path.length();
 126                                 }
 127                                 return path.substring(idx,end);
 128                         } else if(i==start-1) { // if last spot was left blank, i.e. :key*
 129                                 return "";
 130                         }
 131                 }
 132                 return null;
 133         }
 134
 135         public boolean match(String path) {
 136                 if(path==null|| path.length()==0 || "/".equals(path) ) {
 137                         if(values==null)return true;
 138                         switch(values.length) {
 139                                 case 0: return true;
 140                                 case 1: return values[0].length==0;
 141                                 default: return false;
 142                         }
 143                 }
 144                 boolean rv = true;
 145                 byte[] pabytes = path.getBytes();
 146                 int field=0;
 147                 int fieldIdx = 0;
 148
 149                 int lastField = values.length;
 150                 int lastByte = pabytes.length;
 151                 boolean fieldMatched = false; // = lastByte>0?(pabytes[0]=='/'):false;
 152                 // IF DEBUG: System.out.println("\n -- " + path + " --");
 153                 for(int i=0;rv && i<lastByte;++i) {
 154                         if(field>=lastField) { // checking here allows there to be a non-functional ending /
 155                                 rv = false;
 156                                 break;
 157                         }
 158                         if(values[field]==null) { // it's a variable, just look for /s
 159                                 if(wildcard && field==lastField-1) return true;// we've made it this far.  We accept all remaining characters
 160                                 Integer val = vars[field];
 161                                 int start = val & 0xFFFF;
 162                                 int end = (val >> 16) & 0xFFFF;
 163                                 if(end==0)end=start+1;
 164                                 int k = i;
 165                                 for(int j=start; j<end && k<lastByte; ++k) {
 166                                         // IF DEBUG: System.out.print((char)pabytes[k]);
 167                                         if(pabytes[k]=='/') {
 168                                                 ++field;
 169                                                 ++j;
 170                                         }
 171                                 }
 172
 173                                 if(k==lastByte && pabytes[k-1]!='/')++field;
 174                                 if(k>i)i=k-1; // if we've incremented, have to accommodate the outer for loop incrementing as well
 175                                 fieldMatched = false; // reset
 176                                 fieldIdx = 0;
 177                         } else {
 178                                 // IF DEBUG: System.out.print((char)pabytes[i]);
 179                                 if(pabytes[i]=='/') { // end of field, eval if Field is matched
 180                                         // if double slash, check if supposed to be empty
 181                                         if(fieldIdx==0 && values[field].length==0) {
 182                                                 fieldMatched = true;
 183                                         }
 184                                         rv = fieldMatched && ++field<lastField;
 185                                         // reset
 186                                         fieldMatched = false;
 187                                         fieldIdx = 0;
 188                                 } else if(values[field].length==0) {
 189                                         // double slash in path, but content in field.  We check specially here to avoid
 190                                         // Array out of bounds issues.
 191                                         rv = false;
 192                                 } else {
 193                                         if(fieldMatched) {
 194                                                 rv =false; // field is already matched, now there's too many bytes
 195                                         } else {
 196                                                 rv = pabytes[i]==values[field][fieldIdx++]; // compare expected (pabytes[i]) with value for particular field
 197                                                 fieldMatched=values[field].length==fieldIdx; // are all the bytes match in the field?
 198                                                 if(fieldMatched && (i==lastByte-1 || (wildcard && field==lastField-1)))
 199                                                         return true; // last field info
 200                                         }
 201                                 }
 202                         }
 203                 }
 204                 if(field!=lastField || pabytes.length!=lastByte) rv = false; // have we matched all the fields and all the bytes?
 205                 return rv;
 206         }
 207
 208         public Set<String> getParamNames() {
 209                 return params.keySet();
 210         }
 211 }