1 : /******************************************************************************
2 : * $Id: ogrfeaturequery.cpp 23961 2012-02-12 20:33:41Z rouault $
3 : *
4 : * Project: OpenGIS Simple Features Reference Implementation
5 : * Purpose: Implementation of simple SQL WHERE style attributes queries
6 : * for OGRFeatures.
7 : * Author: Frank Warmerdam, warmerdam@pobox.com
8 : *
9 : ******************************************************************************
10 : * Copyright (c) 2001, Frank Warmerdam <warmerdam@pobox.com>
11 : *
12 : * Permission is hereby granted, free of charge, to any person obtaining a
13 : * copy of this software and associated documentation files (the "Software"),
14 : * to deal in the Software without restriction, including without limitation
15 : * the rights to use, copy, modify, merge, publish, distribute, sublicense,
16 : * and/or sell copies of the Software, and to permit persons to whom the
17 : * Software is furnished to do so, subject to the following conditions:
18 : *
19 : * The above copyright notice and this permission notice shall be included
20 : * in all copies or substantial portions of the Software.
21 : *
22 : * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS
23 : * OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
24 : * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
25 : * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
26 : * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
27 : * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
28 : * DEALINGS IN THE SOFTWARE.
29 : ****************************************************************************/
30 :
31 : #include <assert.h>
32 : #include "swq.h"
33 : #include "ogr_feature.h"
34 : #include "ogr_p.h"
35 : #include "ogr_attrind.h"
36 :
37 : CPL_CVSID("$Id: ogrfeaturequery.cpp 23961 2012-02-12 20:33:41Z rouault $");
38 :
39 : /************************************************************************/
40 : /* Support for special attributes (feature query and selection) */
41 : /************************************************************************/
42 :
43 : const char* SpecialFieldNames[SPECIAL_FIELD_COUNT]
44 : = {"FID", "OGR_GEOMETRY", "OGR_STYLE", "OGR_GEOM_WKT", "OGR_GEOM_AREA"};
45 : const swq_field_type SpecialFieldTypes[SPECIAL_FIELD_COUNT]
46 : = {SWQ_INTEGER, SWQ_STRING, SWQ_STRING, SWQ_STRING, SWQ_FLOAT};
47 :
48 : /************************************************************************/
49 : /* OGRFeatureQuery() */
50 : /************************************************************************/
51 :
52 608 : OGRFeatureQuery::OGRFeatureQuery()
53 :
54 : {
55 608 : poTargetDefn = NULL;
56 608 : pSWQExpr = NULL;
57 608 : }
58 :
59 : /************************************************************************/
60 : /* ~OGRFeatureQuery() */
61 : /************************************************************************/
62 :
63 608 : OGRFeatureQuery::~OGRFeatureQuery()
64 :
65 : {
66 608 : delete (swq_expr_node *) pSWQExpr;
67 608 : }
68 :
69 : /************************************************************************/
70 : /* Parse */
71 : /************************************************************************/
72 :
73 982 : OGRErr OGRFeatureQuery::Compile( OGRFeatureDefn *poDefn,
74 : const char * pszExpression )
75 :
76 : {
77 : /* -------------------------------------------------------------------- */
78 : /* Clear any existing expression. */
79 : /* -------------------------------------------------------------------- */
80 982 : if( pSWQExpr != NULL )
81 : {
82 374 : delete (swq_expr_node *) pSWQExpr;
83 374 : pSWQExpr = NULL;
84 : }
85 :
86 : /* -------------------------------------------------------------------- */
87 : /* Build list of fields. */
88 : /* -------------------------------------------------------------------- */
89 : char **papszFieldNames;
90 : swq_field_type *paeFieldTypes;
91 : int iField;
92 982 : int nFieldCount = poDefn->GetFieldCount() + SPECIAL_FIELD_COUNT;
93 :
94 : papszFieldNames = (char **)
95 982 : CPLMalloc(sizeof(char *) * nFieldCount );
96 : paeFieldTypes = (swq_field_type *)
97 982 : CPLMalloc(sizeof(swq_field_type) * nFieldCount );
98 :
99 5732 : for( iField = 0; iField < poDefn->GetFieldCount(); iField++ )
100 : {
101 4750 : OGRFieldDefn *poField = poDefn->GetFieldDefn( iField );
102 :
103 4750 : papszFieldNames[iField] = (char *) poField->GetNameRef();
104 :
105 4750 : switch( poField->GetType() )
106 : {
107 : case OFTInteger:
108 1164 : paeFieldTypes[iField] = SWQ_INTEGER;
109 1164 : break;
110 :
111 : case OFTReal:
112 1198 : paeFieldTypes[iField] = SWQ_FLOAT;
113 1198 : break;
114 :
115 : case OFTString:
116 2214 : paeFieldTypes[iField] = SWQ_STRING;
117 2214 : break;
118 :
119 : case OFTDate:
120 : case OFTTime:
121 : case OFTDateTime:
122 162 : paeFieldTypes[iField] = SWQ_TIMESTAMP;
123 162 : break;
124 :
125 : default:
126 12 : paeFieldTypes[iField] = SWQ_OTHER;
127 : break;
128 : }
129 : }
130 :
131 982 : iField = 0;
132 6874 : while (iField < SPECIAL_FIELD_COUNT)
133 : {
134 4910 : papszFieldNames[poDefn->GetFieldCount() + iField] = (char *) SpecialFieldNames[iField];
135 4910 : paeFieldTypes[poDefn->GetFieldCount() + iField] = SpecialFieldTypes[iField];
136 4910 : ++iField;
137 : }
138 :
139 : /* -------------------------------------------------------------------- */
140 : /* Try to parse. */
141 : /* -------------------------------------------------------------------- */
142 982 : OGRErr eErr = OGRERR_NONE;
143 : CPLErr eCPLErr;
144 :
145 982 : poTargetDefn = poDefn;
146 : eCPLErr = swq_expr_compile( pszExpression, nFieldCount,
147 : papszFieldNames, paeFieldTypes,
148 982 : (swq_expr_node **) &pSWQExpr );
149 982 : if( eCPLErr != CE_None )
150 : {
151 0 : eErr = OGRERR_CORRUPT_DATA;
152 0 : pSWQExpr = NULL;
153 : }
154 :
155 982 : CPLFree( papszFieldNames );
156 982 : CPLFree( paeFieldTypes );
157 :
158 :
159 982 : return eErr;
160 : }
161 :
162 : /************************************************************************/
163 : /* OGRFeatureFetcher() */
164 : /************************************************************************/
165 :
166 913660 : static swq_expr_node *OGRFeatureFetcher( swq_expr_node *op, void *pFeatureIn )
167 :
168 : {
169 913660 : OGRFeature *poFeature = (OGRFeature *) pFeatureIn;
170 913660 : swq_expr_node *poRetNode = NULL;
171 :
172 913660 : switch( op->field_type )
173 : {
174 : case SWQ_INTEGER:
175 : case SWQ_BOOLEAN:
176 : poRetNode = new swq_expr_node(
177 158270 : poFeature->GetFieldAsInteger(op->field_index) );
178 158270 : break;
179 :
180 : case SWQ_FLOAT:
181 : poRetNode = new swq_expr_node(
182 4670 : poFeature->GetFieldAsDouble(op->field_index) );
183 4670 : break;
184 :
185 : default:
186 : poRetNode = new swq_expr_node(
187 750720 : poFeature->GetFieldAsString(op->field_index) );
188 : break;
189 : }
190 :
191 913660 : poRetNode->is_null = !(poFeature->IsFieldSet(op->field_index));
192 :
193 913660 : return poRetNode;
194 : }
195 :
196 : /************************************************************************/
197 : /* Evaluate() */
198 : /************************************************************************/
199 :
200 913420 : int OGRFeatureQuery::Evaluate( OGRFeature *poFeature )
201 :
202 : {
203 913420 : if( pSWQExpr == NULL )
204 0 : return FALSE;
205 :
206 : swq_expr_node *poResult;
207 :
208 : poResult = ((swq_expr_node *) pSWQExpr)->Evaluate( OGRFeatureFetcher,
209 913420 : (void *) poFeature );
210 :
211 913420 : if( poResult == NULL )
212 0 : return FALSE;
213 :
214 913420 : CPLAssert( poResult->field_type == SWQ_BOOLEAN );
215 :
216 913420 : int bLogicalResult = poResult->int_value;
217 :
218 913420 : delete poResult;
219 :
220 913420 : return bLogicalResult;
221 : }
222 :
223 : /************************************************************************/
224 : /* EvaluateAgainstIndices() */
225 : /* */
226 : /* Attempt to return a list of FIDs matching the given */
227 : /* attribute query conditions utilizing attribute indices. */
228 : /* Returns NULL if the result cannot be computed from the */
229 : /* available indices, or an "OGRNullFID" terminated list of */
230 : /* FIDs if it can. */
231 : /* */
232 : /* For now we only support equality tests on a single indexed */
233 : /* attribute field. Eventually we should make this support */
234 : /* multi-part queries with ranges. */
235 : /************************************************************************/
236 :
237 20 : static int CompareLong(const void *a, const void *b)
238 : {
239 20 : return (*(const long *)a) - (*(const long *)b);
240 : }
241 :
242 694 : long *OGRFeatureQuery::EvaluateAgainstIndices( OGRLayer *poLayer,
243 : OGRErr *peErr )
244 :
245 : {
246 694 : swq_expr_node *psExpr = (swq_expr_node *) pSWQExpr;
247 :
248 694 : if( peErr != NULL )
249 0 : *peErr = OGRERR_NONE;
250 :
251 : /* -------------------------------------------------------------------- */
252 : /* Do we have an index on the targetted field? */
253 : /* -------------------------------------------------------------------- */
254 694 : if ( poLayer->GetIndex() == NULL )
255 64 : return NULL;
256 :
257 630 : int nFIDCount = 0;
258 630 : return EvaluateAgainstIndices(psExpr, poLayer, nFIDCount);
259 : }
260 :
261 : /* The input arrays must be sorted ! */
262 : static
263 2 : long* OGRORLongArray(long panFIDList1[], int nFIDCount1,
264 : long panFIDList2[], int nFIDCount2, int& nFIDCount)
265 : {
266 2 : int nMaxCount = nFIDCount1 + nFIDCount2;
267 2 : long* panFIDList = (long*) CPLMalloc((nMaxCount+1) * sizeof(long));
268 2 : nFIDCount = 0;
269 :
270 2 : int i1 = 0, i2 =0;
271 12 : for(;i1<nFIDCount1 || i2<nFIDCount2;)
272 : {
273 12 : if (i1 < nFIDCount1 && i2 < nFIDCount2)
274 : {
275 4 : long nVal1 = panFIDList1[i1];
276 4 : long nVal2 = panFIDList2[i2];
277 4 : if (nVal1 < nVal2)
278 : {
279 4 : if (i1+1 < nFIDCount1 && panFIDList1[i1+1] <= nVal2)
280 : {
281 2 : panFIDList[nFIDCount ++] = nVal1;
282 2 : i1 ++;
283 : }
284 : else
285 : {
286 0 : panFIDList[nFIDCount ++] = nVal1;
287 0 : panFIDList[nFIDCount ++] = nVal2;
288 0 : i1 ++;
289 0 : i2 ++;
290 : }
291 : }
292 2 : else if (nVal1 == nVal2)
293 : {
294 2 : panFIDList[nFIDCount ++] = nVal1;
295 2 : i1 ++;
296 2 : i2 ++;
297 : }
298 : else
299 : {
300 0 : if (i2+1 < nFIDCount2 && panFIDList2[i2+1] <= nVal1)
301 : {
302 0 : panFIDList[nFIDCount ++] = nVal2;
303 0 : i2 ++;
304 : }
305 : else
306 : {
307 0 : panFIDList[nFIDCount ++] = nVal2;
308 0 : panFIDList[nFIDCount ++] = nVal1;
309 0 : i1 ++;
310 0 : i2 ++;
311 : }
312 : }
313 : }
314 4 : else if (i1 < nFIDCount1)
315 : {
316 0 : long nVal1 = panFIDList1[i1];
317 0 : panFIDList[nFIDCount ++] = nVal1;
318 0 : i1 ++;
319 : }
320 4 : else if (i2 < nFIDCount2)
321 : {
322 4 : long nVal2 = panFIDList2[i2];
323 4 : panFIDList[nFIDCount ++] = nVal2;
324 4 : i2 ++;
325 : }
326 : }
327 :
328 2 : panFIDList[nFIDCount] = OGRNullFID;
329 :
330 2 : return panFIDList;
331 : }
332 :
333 : /* The input arrays must be sorted ! */
334 : static
335 4 : long* OGRANDLongArray(long panFIDList1[], int nFIDCount1,
336 : long panFIDList2[], int nFIDCount2, int& nFIDCount)
337 : {
338 4 : int nMaxCount = MAX(nFIDCount1, nFIDCount2);
339 4 : long* panFIDList = (long*) CPLMalloc((nMaxCount+1) * sizeof(long));
340 4 : nFIDCount = 0;
341 :
342 4 : int i1 = 0, i2 =0;
343 16 : for(;i1<nFIDCount1 && i2<nFIDCount2;)
344 : {
345 8 : long nVal1 = panFIDList1[i1];
346 8 : long nVal2 = panFIDList2[i2];
347 8 : if (nVal1 < nVal2)
348 : {
349 6 : if (i1+1 < nFIDCount1 && panFIDList1[i1+1] <= nVal2)
350 : {
351 2 : i1 ++;
352 : }
353 : else
354 : {
355 2 : i1 ++;
356 2 : i2 ++;
357 : }
358 : }
359 4 : else if (nVal1 == nVal2)
360 : {
361 4 : panFIDList[nFIDCount ++] = nVal1;
362 4 : i1 ++;
363 4 : i2 ++;
364 : }
365 : else
366 : {
367 0 : if (i2+1 < nFIDCount2 && panFIDList2[i2+1] <= nVal1)
368 : {
369 0 : i2 ++;
370 : }
371 : else
372 : {
373 0 : i1 ++;
374 0 : i2 ++;
375 : }
376 : }
377 : }
378 :
379 4 : panFIDList[nFIDCount] = OGRNullFID;
380 :
381 4 : return panFIDList;
382 : }
383 :
384 842 : long *OGRFeatureQuery::EvaluateAgainstIndices( swq_expr_node *psExpr,
385 : OGRLayer *poLayer,
386 : int& nFIDCount )
387 : {
388 : OGRAttrIndex *poIndex;
389 :
390 : /* -------------------------------------------------------------------- */
391 : /* Does the expression meet our requirements? */
392 : /* -------------------------------------------------------------------- */
393 842 : if( psExpr == NULL ||
394 : psExpr->eNodeType != SNT_OPERATION )
395 0 : return NULL;
396 :
397 842 : if ((psExpr->nOperation == SWQ_OR || psExpr->nOperation == SWQ_AND) &&
398 : psExpr->nSubExprCount == 2)
399 : {
400 206 : int nFIDCount1 = 0, nFIDCount2 = 0;
401 206 : long* panFIDList1 = EvaluateAgainstIndices( psExpr->papoSubExpr[0], poLayer, nFIDCount1 );
402 : long* panFIDList2 = panFIDList1 == NULL ? NULL :
403 206 : EvaluateAgainstIndices( psExpr->papoSubExpr[1], poLayer, nFIDCount2 );
404 206 : long* panFIDList = NULL;
405 206 : if (panFIDList1 != NULL && panFIDList2 != NULL)
406 : {
407 6 : if (psExpr->nOperation == SWQ_OR )
408 : panFIDList = OGRORLongArray(panFIDList1, nFIDCount1,
409 2 : panFIDList2, nFIDCount2, nFIDCount);
410 4 : else if (psExpr->nOperation == SWQ_AND )
411 : panFIDList = OGRANDLongArray(panFIDList1, nFIDCount1,
412 4 : panFIDList2, nFIDCount2, nFIDCount);
413 :
414 : }
415 206 : CPLFree(panFIDList1);
416 206 : CPLFree(panFIDList2);
417 206 : return panFIDList;
418 : }
419 :
420 636 : if( !(psExpr->nOperation == SWQ_EQ || psExpr->nOperation == SWQ_IN)
421 : || psExpr->nSubExprCount < 2 )
422 68 : return NULL;
423 :
424 568 : swq_expr_node *poColumn = psExpr->papoSubExpr[0];
425 568 : swq_expr_node *poValue = psExpr->papoSubExpr[1];
426 :
427 568 : if( poColumn->eNodeType != SNT_COLUMN
428 : || poValue->eNodeType != SNT_CONSTANT )
429 50 : return NULL;
430 :
431 518 : poIndex = poLayer->GetIndex()->GetFieldIndex( poColumn->field_index );
432 518 : if( poIndex == NULL )
433 458 : return NULL;
434 :
435 : /* -------------------------------------------------------------------- */
436 : /* OK, we have an index, now we need to query it. */
437 : /* -------------------------------------------------------------------- */
438 : OGRField sValue;
439 : OGRFieldDefn *poFieldDefn;
440 :
441 60 : poFieldDefn = poLayer->GetLayerDefn()->GetFieldDefn(poColumn->field_index);
442 :
443 : /* -------------------------------------------------------------------- */
444 : /* Handle the case of an IN operation. */
445 : /* -------------------------------------------------------------------- */
446 60 : if (psExpr->nOperation == SWQ_IN)
447 : {
448 : int nLength;
449 20 : long *panFIDs = NULL;
450 : int iIN;
451 :
452 40 : for( iIN = 1; iIN < psExpr->nSubExprCount; iIN++ )
453 : {
454 20 : switch( poFieldDefn->GetType() )
455 : {
456 : case OFTInteger:
457 10 : if (psExpr->papoSubExpr[iIN]->field_type == SWQ_FLOAT)
458 6 : sValue.Integer = (int) psExpr->papoSubExpr[iIN]->float_value;
459 : else
460 4 : sValue.Integer = psExpr->papoSubExpr[iIN]->int_value;
461 10 : break;
462 :
463 : case OFTReal:
464 10 : sValue.Real = psExpr->papoSubExpr[iIN]->float_value;
465 10 : break;
466 :
467 : case OFTString:
468 0 : sValue.String = psExpr->papoSubExpr[iIN]->string_value;
469 0 : break;
470 :
471 : default:
472 0 : CPLAssert( FALSE );
473 0 : return NULL;
474 : }
475 :
476 20 : panFIDs = poIndex->GetAllMatches( &sValue, panFIDs, &nFIDCount, &nLength );
477 : }
478 :
479 20 : if (nFIDCount > 1)
480 : {
481 : /* the returned FIDs are expected to be in sorted order */
482 0 : qsort(panFIDs, nFIDCount, sizeof(long), CompareLong);
483 : }
484 20 : return panFIDs;
485 : }
486 :
487 : /* -------------------------------------------------------------------- */
488 : /* Handle equality test. */
489 : /* -------------------------------------------------------------------- */
490 40 : switch( poFieldDefn->GetType() )
491 : {
492 : case OFTInteger:
493 28 : if (poValue->field_type == SWQ_FLOAT)
494 2 : sValue.Integer = (int) poValue->float_value;
495 : else
496 26 : sValue.Integer = poValue->int_value;
497 28 : break;
498 :
499 : case OFTReal:
500 4 : sValue.Real = poValue->float_value;
501 4 : break;
502 :
503 : case OFTString:
504 8 : sValue.String = poValue->string_value;
505 8 : break;
506 :
507 : default:
508 0 : CPLAssert( FALSE );
509 0 : return NULL;
510 : }
511 :
512 40 : int nLength = 0;
513 40 : long *panFIDs = poIndex->GetAllMatches( &sValue, NULL, &nFIDCount, &nLength );
514 40 : if (nFIDCount > 1)
515 : {
516 : /* the returned FIDs are expected to be in sorted order */
517 12 : qsort(panFIDs, nFIDCount, sizeof(long), CompareLong);
518 : }
519 40 : return panFIDs;
520 : }
521 :
522 : /************************************************************************/
523 : /* OGRFieldCollector() */
524 : /* */
525 : /* Helper function for recursing through tree to satisfy */
526 : /* GetUsedFields(). */
527 : /************************************************************************/
528 :
529 12 : char **OGRFeatureQuery::FieldCollector( void *pBareOp,
530 : char **papszList )
531 :
532 : {
533 12 : swq_expr_node *op = (swq_expr_node *) pBareOp;
534 :
535 : /* -------------------------------------------------------------------- */
536 : /* References to tables other than the primarily are currently */
537 : /* unsupported. Error out. */
538 : /* -------------------------------------------------------------------- */
539 12 : if( op->eNodeType == SNT_COLUMN )
540 : {
541 4 : if( op->table_index != 0 )
542 : {
543 0 : CSLDestroy( papszList );
544 0 : return NULL;
545 : }
546 :
547 : /* -------------------------------------------------------------------- */
548 : /* Add the field name into our list if it is not already there. */
549 : /* -------------------------------------------------------------------- */
550 : const char *pszFieldName;
551 :
552 4 : if( op->field_index >= poTargetDefn->GetFieldCount()
553 : && op->field_index < poTargetDefn->GetFieldCount() + SPECIAL_FIELD_COUNT)
554 2 : pszFieldName = SpecialFieldNames[op->field_index - poTargetDefn->GetFieldCount()];
555 2 : else if( op->field_index >= 0
556 : && op->field_index < poTargetDefn->GetFieldCount() )
557 : pszFieldName =
558 2 : poTargetDefn->GetFieldDefn(op->field_index)->GetNameRef();
559 : else
560 : {
561 0 : CSLDestroy( papszList );
562 0 : return NULL;
563 : }
564 :
565 4 : if( CSLFindString( papszList, pszFieldName ) == -1 )
566 4 : papszList = CSLAddString( papszList, pszFieldName );
567 : }
568 :
569 : /* -------------------------------------------------------------------- */
570 : /* Add in fields from subexpressions. */
571 : /* -------------------------------------------------------------------- */
572 12 : if( op->eNodeType == SNT_OPERATION )
573 : {
574 12 : for( int iSubExpr = 0; iSubExpr < op->nSubExprCount; iSubExpr++ )
575 : {
576 8 : papszList = FieldCollector( op->papoSubExpr[iSubExpr], papszList );
577 : }
578 : }
579 :
580 12 : return papszList;
581 : }
582 :
583 : /************************************************************************/
584 : /* GetUsedFields() */
585 : /************************************************************************/
586 :
587 : /**
588 : * Returns lists of fields in expression.
589 : *
590 : * All attribute fields are used in the expression of this feature
591 : * query are returned as a StringList of field names. This function would
592 : * primarily be used within drivers to recognise special case conditions
593 : * depending only on attribute fields that can be very efficiently
594 : * fetched.
595 : *
596 : * NOTE: If any fields in the expression are from tables other than the
597 : * primary table then NULL is returned indicating an error. In succesful
598 : * use, no non-empty expression should return an empty list.
599 : *
600 : * @return list of field names. Free list with CSLDestroy() when no longer
601 : * required.
602 : */
603 :
604 4 : char **OGRFeatureQuery::GetUsedFields( )
605 :
606 : {
607 4 : if( pSWQExpr == NULL )
608 0 : return NULL;
609 :
610 :
611 4 : return FieldCollector( pSWQExpr, NULL );
612 : }
613 :
614 :
615 :
|
