1 /*
2 *
3 ***** BEGIN LICENSE BLOCK *****
4
5 Copyright (C) 2009-2019 Olof Hagsand
6 Copyright (C) 2020 Olof Hagsand and Rubicon Communications, LLC(Netgate)
7
8 This file is part of CLIXON.
9
10 Licensed under the Apache License, Version 2.0 (the "License");
11 you may not use this file except in compliance with the License.
12 You may obtain a copy of the License at
13
14 http://www.apache.org/licenses/LICENSE-2.0
15
16 Unless required by applicable law or agreed to in writing, software
17 distributed under the License is distributed on an "AS IS" BASIS,
18 WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
19 See the License for the specific language governing permissions and
20 limitations under the License.
21
22 Alternatively, the contents of this file may be used under the terms of
23 the GNU General Public License Version 3 or later (the "GPL"),
24 in which case the provisions of the GPL are applicable instead
25 of those above. If you wish to allow use of your version of this file only
26 under the terms of the GPL, and not to allow others to
27 use your version of this file under the terms of Apache License version 2, indicate
28 your decision by deleting the provisions above and replace them with the
29 notice and other provisions required by the GPL. If you do not delete
30 the provisions above, a recipient may use your version of this file under
31 the terms of any one of the Apache License version 2 or the GPL.
32
33 ***** END LICENSE BLOCK *****
34
35 * Clixon XML XPATH 1.0 according to https://www.w3.org/TR/xpath-10
36 * See XPATH_LIST_OPTIMIZE
37 */
38
39 #ifdef HAVE_CONFIG_H
40 #include "clixon_config.h" /* generated by config & autoconf */
41 #endif
42
43 #include <stdio.h>
44 #include <stdlib.h>
45 #include <unistd.h>
46 #include <errno.h>
47 #include <string.h>
48 #include <limits.h>
49 #include <stdint.h>
50 #include <assert.h>
51 #include <syslog.h>
52 #include <fcntl.h>
53 #include <math.h> /* NaN */
54
55 /* cligen */
56 #include <cligen/cligen.h>
57
58 /* clicon */
59 #include "clixon_err.h"
60 #include "clixon_log.h"
61 #include "clixon_string.h"
62 #include "clixon_queue.h"
63 #include "clixon_hash.h"
64 #include "clixon_handle.h"
65 #include "clixon_yang.h"
66 #include "clixon_xml.h"
67 #include "clixon_xml_vec.h"
68 #include "clixon_xml_sort.h"
69 #include "clixon_xpath_ctx.h"
70 #include "clixon_xpath.h"
71 #include "clixon_xpath_optimize.h"
72
73 #ifdef XPATH_LIST_OPTIMIZE
74 static xpath_tree *_xmtop = NULL; /* pattern match tree top */
75 static xpath_tree *_xm = NULL;
76 static xpath_tree *_xe = NULL;
77 static int _optimize_enable = 1;
78 static int _optimize_hits = 0;
79 #endif /* XPATH_LIST_OPTIMIZE */
80
81 /* XXX development in clixon_xpath_eval */
82 int
xpath_list_optimize_stats(int * hits)83 xpath_list_optimize_stats(int *hits)
84 {
85 #ifdef XPATH_LIST_OPTIMIZE
86 *hits = _optimize_hits;
87 _optimize_hits = 0;
88 #endif
89 return 0;
90 }
91
92 /*! Enable xpath optimize
93 * Cant replace this with optin since there is no handle in xpath functions,...
94 */
95 int
xpath_list_optimize_set(int enable)96 xpath_list_optimize_set(int enable)
97 {
98 #ifdef XPATH_LIST_OPTIMIZE
99 _optimize_enable = enable;
100 #endif
101 return 0;
102 }
103
104 void
xpath_optimize_exit(void)105 xpath_optimize_exit(void)
106 {
107 #ifdef XPATH_LIST_OPTIMIZE
108 if (_xmtop)
109 xpath_tree_free(_xmtop);
110 #endif
111 }
112
113 #ifdef XPATH_LIST_OPTIMIZE
114 /*! Initialize xpath module
115 * XXX move to clixon_xpath.c
116 * @see loop_preds
117 */
118 int
xpath_optimize_init(xpath_tree ** xm,xpath_tree ** xe)119 xpath_optimize_init(xpath_tree **xm,
120 xpath_tree **xe)
121 {
122 int retval = -1;
123 xpath_tree *xs;
124
125 if (_xm == NULL){
126 /* Initialize xpath-tree */
127 if (xpath_parse("_x[_y='_z']", &_xmtop) < 0)
128 goto done;
129 /* Go down two steps */
130 if ((_xm = xpath_tree_traverse(_xmtop, 0, 0, -1)) == NULL)
131 goto done;
132 /* get nodetest tree (_x) */
133 if ((xs = xpath_tree_traverse(_xm, 0, -1)) == NULL)
134 goto done;
135 xs->xs_match++;
136 /* get predicates [_y=_z][z=2] */
137 if ((xs = xpath_tree_traverse(_xm, 1, -1)) == NULL)
138 goto done;
139 xs->xs_match++;
140 /* get expression [_y=_z] */
141 if ((_xe = xpath_tree_traverse(xs, 1, -1)) == NULL)
142 goto done;
143 /* get keyname (_y) */
144 if ((xs = xpath_tree_traverse(_xe, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -1)) == NULL)
145 goto done;
146 xs->xs_match++; /* in loop_preds get name in xs_s1 XXX: leaf-list is different */
147 /* get keyval (_z) */
148 if ((xs = xpath_tree_traverse(_xe, 0, 0, 1, 0, 0, 0, 0, -1)) == NULL)
149 goto done;
150 xs->xs_match++; /* in loop_preds get value in xs_s0 or xs_strnr */
151 }
152 *xm = _xm;
153 *xe = _xe;
154 retval = 0;
155 done:
156 return retval;
157 }
158
159
160 /*! Recursive function to loop over all EXPR and pattern match them
161 *
162 * @param[in] xt XPath tree of type PRED
163 * @param[in] xepat Pattern matching XPath tree of type EXPR
164 * @param[out] cvk Vector of <keyname>:<keyval> pairs
165 * @retval -1 Error
166 * @retval 0 No match
167 * @retval 1 Match
168 * @see xpath_optimize_init
169 */
170 static int
loop_preds(xpath_tree * xt,xpath_tree * xepat,cvec * cvk)171 loop_preds(xpath_tree *xt,
172 xpath_tree *xepat,
173 cvec *cvk)
174 {
175 int retval = -1;
176 int ret;
177 xpath_tree *xe;
178 xpath_tree **vec = NULL;
179 size_t veclen = 0;
180 cg_var *cvi;
181
182 if (xt->xs_type == XP_PRED && xt->xs_c0){
183 if ((ret = loop_preds(xt->xs_c0, xepat, cvk)) < 0)
184 goto done;
185 if (ret == 0)
186 goto ok;
187 }
188 if ((xe = xt->xs_c1) && (xe->xs_type == XP_EXP)){
189 if ((ret = xpath_tree_eq(xepat, xe, &vec, &veclen)) < 0)
190 goto done;
191 if (ret == 0)
192 goto ok;
193 if (veclen != 2)
194 goto ok;
195 if ((cvi = cvec_add(cvk, CGV_STRING)) == NULL){
196 clicon_err(OE_XML, errno, "cvec_add");
197 goto done;
198 }
199 cv_name_set(cvi, vec[0]->xs_s1);
200 if (vec[1]->xs_type == XP_PRIME_NR)
201 cv_string_set(cvi, vec[1]->xs_strnr);
202 else
203 cv_string_set(cvi, vec[1]->xs_s0);
204 }
205 retval = 1;
206 done:
207 if (vec)
208 free(vec);
209 return retval;
210 ok: /* no match, not special case */
211 retval = 0;
212 goto done;
213 }
214
215 /*! Pattern matching to find fastpath
216 *
217 * @param[in] xt XPath tree
218 * @param[in] xv XML base node
219 * @param[out] xvec Array of found nodes
220 * @param[out] xlen Len of xvec
221 * @param[out] key
222 * @param[out] keyval
223 * @retval -1 Error
224 * @retval 0 No match - use non-optimized lookup
225 * @retval 1 Match
226 * XPath:
227 * y[k=3] # corresponds to: <name>[<keyname>=<keyval>]
228 */
229 static int
xpath_list_optimize_fn(xpath_tree * xt,cxobj * xv,clixon_xvec * xvec)230 xpath_list_optimize_fn(xpath_tree *xt,
231 cxobj *xv,
232 clixon_xvec *xvec)
233 {
234 int retval = -1;
235 xpath_tree *xm = NULL;
236 xpath_tree *xem = NULL;
237 char *name;
238 yang_stmt *yp;
239 yang_stmt *yc;
240 cvec *cvv = NULL;
241 xpath_tree **vec = NULL;
242 size_t veclen = 0;
243 xpath_tree *xtp;
244 int ret;
245 cvec *cvk = NULL; /* vector of index keys */
246 cg_var *cvi;
247 int i;
248
249 /* revert to non-optimized if no yang */
250 if ((yp = xml_spec(xv)) == NULL)
251 goto ok;
252 /* or if not config data (state data should not be ordered) */
253 if (yang_config_ancestor(yp) == 0)
254 goto ok;
255 /* Check yang and that only a list with key as index is a special case can do bin search
256 * That is, ONLY check optimize cases of this type:_x[_y='_z']
257 * Should we extend this simple example and have more cases (all cases?)
258 */
259 xpath_optimize_init(&xm, &xem);
260 /* Here is where pattern is checked for equality and where variable binding is made (if
261 * equal) */
262 if ((ret = xpath_tree_eq(xm, xt, &vec, &veclen)) < 0)
263 goto done;
264 if (ret == 0)
265 goto ok; /* no match */
266 if (veclen != 2)
267 goto ok;
268 name = vec[0]->xs_s1;
269 /* Extract variables */
270 if ((yc = yang_find(yp, Y_LIST, name)) == NULL)
271 #ifdef NOTYET /* leaf-list is not detected by xpath optimize detection */
272 if ((yc = yang_find(yp, Y_LEAF_LIST, name)) == NULL) /* XXX */
273 #endif
274 goto ok;
275 /* Validate keys */
276 if ((cvv = yang_cvec_get(yc)) == NULL)
277 goto ok;
278 xtp = vec[1];
279 if ((cvk = cvec_new(0)) == NULL){
280 clicon_err(OE_YANG, errno, "cvec_new");
281 goto done;
282 }
283 if ((ret = loop_preds(xtp, xem, cvk)) < 0)
284 goto done;
285 if (ret == 0)
286 goto ok;
287
288 if (cvec_len(cvv) != cvec_len(cvk))
289 goto ok;
290 i = 0;
291 cvi = NULL;
292 while ((cvi = cvec_each(cvk, cvi)) != NULL) {
293 if (strcmp(cv_name_get(cvi), cv_string_get(cvec_i(cvv,i))))
294 goto ok;
295 i++;
296 }
297 /* Use 2a form since yc allready given to compute cvk */
298 if (clixon_xml_find_index(xv, yp, NULL, name, cvk, xvec) < 0)
299 goto done;
300 retval = 1; /* match */
301 done:
302 if (vec)
303 free(vec);
304 if (cvk)
305 cvec_free(cvk);
306 return retval;
307 ok: /* no match, not special case */
308 retval = 0;
309 goto done;
310 }
311 #endif /* XPATH_LIST_OPTIMIZE */
312
313 /*! Identify XPATH special cases and if match, use binary search.
314 *
315 * @retval -1 Error
316 * @retval 0 Dont optimize: not special case, do normal processing
317 * @retval 1 Optimization made, special case, use x (found if != NULL)
318 * XXX Contains glue code between cxobj ** and clixon_xvec code
319 */
320 int
xpath_optimize_check(xpath_tree * xs,cxobj * xv,cxobj *** xvec0,int * xlen0)321 xpath_optimize_check(xpath_tree *xs,
322 cxobj *xv,
323 cxobj ***xvec0,
324 int *xlen0)
325 {
326 #ifdef XPATH_LIST_OPTIMIZE
327 int ret;
328 clixon_xvec *xvec = NULL;
329
330 if (!_optimize_enable)
331 return 0; /* use regular code */
332 if ((xvec = clixon_xvec_new()) == NULL)
333 return -1;
334 /* Glue code since xpath code uses (old) cxobj ** and search code uses (new) clixon_xvec */
335 if ((ret = xpath_list_optimize_fn(xs, xv, xvec)) < 0)
336 return -1;
337 if (ret == 1){
338 if (clixon_xvec_extract(xvec, xvec0, xlen0) < 0)
339 return -1;
340 clixon_xvec_free(xvec);
341 _optimize_hits++;
342 return 1; /* Optimized */
343 }
344 else{
345 clixon_xvec_free(xvec);
346 return 0; /* use regular code */
347 }
348 #else
349 return 0; /* use regular code */
350 #endif
351 }
352
353