]> git.openstreetmap.org Git - nominatim.git/blob - lib-php/Geocode.php
Merge remote-tracking branch 'upstream/master'
[nominatim.git] / lib-php / Geocode.php
1 <?php
2 /**
3  * SPDX-License-Identifier: GPL-2.0-only
4  *
5  * This file is part of Nominatim. (https://nominatim.org)
6  *
7  * Copyright (C) 2022 by the Nominatim developer community.
8  * For a full list of authors see the git log.
9  */
10
11 namespace Nominatim;
12
13 require_once(CONST_LibDir.'/PlaceLookup.php');
14 require_once(CONST_LibDir.'/Phrase.php');
15 require_once(CONST_LibDir.'/ReverseGeocode.php');
16 require_once(CONST_LibDir.'/SearchDescription.php');
17 require_once(CONST_LibDir.'/SearchContext.php');
18 require_once(CONST_LibDir.'/SearchPosition.php');
19 require_once(CONST_LibDir.'/TokenList.php');
20 require_once(CONST_TokenizerDir.'/tokenizer.php');
21
22 class Geocode
23 {
24     protected $oDB;
25
26     protected $oPlaceLookup;
27     protected $oTokenizer;
28
29     protected $aLangPrefOrder = array();
30
31     protected $aExcludePlaceIDs = array();
32
33     protected $iLimit = 20;
34     protected $iFinalLimit = 10;
35     protected $iOffset = 0;
36     protected $bFallback = false;
37
38     protected $aCountryCodes = false;
39
40     protected $bBoundedSearch = false;
41     protected $aViewBox = false;
42     protected $aRoutePoints = false;
43     protected $aRouteWidth = false;
44
45     protected $iMaxRank = 20;
46     protected $iMinAddressRank = 0;
47     protected $iMaxAddressRank = 30;
48     protected $aAddressRankList = array();
49
50     protected $sAllowedTypesSQLList = false;
51
52     protected $sQuery = false;
53     protected $aStructuredQuery = false;
54
55
56     public function __construct(&$oDB)
57     {
58         $this->oDB =& $oDB;
59         $this->oPlaceLookup = new PlaceLookup($this->oDB);
60         $this->oTokenizer = new \Nominatim\Tokenizer($this->oDB);
61     }
62
63     public function setLanguagePreference($aLangPref)
64     {
65         $this->aLangPrefOrder = $aLangPref;
66     }
67
68     public function getMoreUrlParams()
69     {
70         if ($this->aStructuredQuery) {
71             $aParams = $this->aStructuredQuery;
72         } else {
73             $aParams = array('q' => $this->sQuery);
74         }
75
76         $aParams = array_merge($aParams, $this->oPlaceLookup->getMoreUrlParams());
77
78         if ($this->aExcludePlaceIDs) {
79             $aParams['exclude_place_ids'] = implode(',', $this->aExcludePlaceIDs);
80         }
81
82         if ($this->bBoundedSearch) {
83             $aParams['bounded'] = '1';
84         }
85
86         if ($this->aCountryCodes) {
87             $aParams['countrycodes'] = implode(',', $this->aCountryCodes);
88         }
89
90         if ($this->aViewBox) {
91             $aParams['viewbox'] = join(',', $this->aViewBox);
92         }
93
94         return $aParams;
95     }
96
97     public function setLimit($iLimit = 10)
98     {
99         if ($iLimit > 50) {
100             $iLimit = 50;
101         } elseif ($iLimit < 1) {
102             $iLimit = 1;
103         }
104
105         $this->iFinalLimit = $iLimit;
106         $this->iLimit = $iLimit + max($iLimit, 10);
107     }
108
109     public function setFeatureType($sFeatureType)
110     {
111         switch ($sFeatureType) {
112             case 'country':
113                 $this->setRankRange(4, 4);
114                 break;
115             case 'state':
116                 $this->setRankRange(8, 8);
117                 break;
118             case 'city':
119                 $this->setRankRange(14, 16);
120                 break;
121             case 'settlement':
122                 $this->setRankRange(8, 20);
123                 break;
124         }
125     }
126
127     public function setRankRange($iMin, $iMax)
128     {
129         $this->iMinAddressRank = $iMin;
130         $this->iMaxAddressRank = $iMax;
131     }
132
133     public function setViewbox($aViewbox)
134     {
135         $aBox = array_map('floatval', $aViewbox);
136
137         $this->aViewBox[0] = max(-180.0, min($aBox[0], $aBox[2]));
138         $this->aViewBox[1] = max(-90.0, min($aBox[1], $aBox[3]));
139         $this->aViewBox[2] = min(180.0, max($aBox[0], $aBox[2]));
140         $this->aViewBox[3] = min(90.0, max($aBox[1], $aBox[3]));
141
142         if ($this->aViewBox[2] - $this->aViewBox[0] < 0.000000001
143             || $this->aViewBox[3] - $this->aViewBox[1] < 0.000000001
144         ) {
145             userError("Bad parameter 'viewbox'. Not a box.");
146         }
147     }
148
149     private function viewboxImportanceFactor($fX, $fY)
150     {
151         if (!$this->aViewBox) {
152             return 1;
153         }
154
155         $fWidth = ($this->aViewBox[2] - $this->aViewBox[0])/2;
156         $fHeight = ($this->aViewBox[3] - $this->aViewBox[1])/2;
157
158         $fXDist = abs($fX - ($this->aViewBox[0] + $this->aViewBox[2])/2);
159         $fYDist = abs($fY - ($this->aViewBox[1] + $this->aViewBox[3])/2);
160
161         if ($fXDist <= $fWidth && $fYDist <= $fHeight) {
162             return 1;
163         }
164
165         if ($fXDist <= $fWidth * 3 && $fYDist <= 3 * $fHeight) {
166             return 0.5;
167         }
168
169         return 0.25;
170     }
171
172     public function setQuery($sQueryString)
173     {
174         $this->sQuery = $sQueryString;
175         $this->aStructuredQuery = false;
176     }
177
178     public function getQueryString()
179     {
180         return $this->sQuery;
181     }
182
183
184     public function loadParamArray($oParams, $sForceGeometryType = null)
185     {
186         $this->bBoundedSearch = $oParams->getBool('bounded', $this->bBoundedSearch);
187
188         $this->setLimit($oParams->getInt('limit', $this->iFinalLimit));
189         $this->iOffset = $oParams->getInt('offset', $this->iOffset);
190
191         $this->bFallback = $oParams->getBool('fallback', $this->bFallback);
192
193         // List of excluded Place IDs - used for more accurate pageing
194         $sExcluded = $oParams->getStringList('exclude_place_ids');
195         if ($sExcluded) {
196             foreach ($sExcluded as $iExcludedPlaceID) {
197                 $iExcludedPlaceID = (int)$iExcludedPlaceID;
198                 if ($iExcludedPlaceID) {
199                     $aExcludePlaceIDs[$iExcludedPlaceID] = $iExcludedPlaceID;
200                 }
201             }
202
203             if (isset($aExcludePlaceIDs)) {
204                 $this->aExcludePlaceIDs = $aExcludePlaceIDs;
205             }
206         }
207
208         // Only certain ranks of feature
209         $sFeatureType = $oParams->getString('featureType');
210         if (!$sFeatureType) {
211             $sFeatureType = $oParams->getString('featuretype');
212         }
213         if ($sFeatureType) {
214             $this->setFeatureType($sFeatureType);
215         }
216
217         // Country code list
218         $sCountries = $oParams->getStringList('countrycodes');
219         if ($sCountries) {
220             foreach ($sCountries as $sCountryCode) {
221                 if (preg_match('/^[a-zA-Z][a-zA-Z]$/', $sCountryCode)) {
222                     $aCountries[] = strtolower($sCountryCode);
223                 }
224             }
225             if (isset($aCountries)) {
226                 $this->aCountryCodes = $aCountries;
227             }
228         }
229
230         $aViewbox = $oParams->getStringList('viewboxlbrt');
231         if ($aViewbox) {
232             if (count($aViewbox) != 4) {
233                 userError("Bad parameter 'viewboxlbrt'. Expected 4 coordinates.");
234             }
235             $this->setViewbox($aViewbox);
236         } else {
237             $aViewbox = $oParams->getStringList('viewbox');
238             if ($aViewbox) {
239                 if (count($aViewbox) != 4) {
240                     userError("Bad parameter 'viewbox'. Expected 4 coordinates.");
241                 }
242                 $this->setViewBox($aViewbox);
243             } else {
244                 $aRoute = $oParams->getStringList('route');
245                 $fRouteWidth = $oParams->getFloat('routewidth');
246                 if ($aRoute && $fRouteWidth) {
247                     $this->aRoutePoints = $aRoute;
248                     $this->aRouteWidth = $fRouteWidth;
249                 }
250             }
251         }
252
253         $this->oPlaceLookup->loadParamArray($oParams, $sForceGeometryType);
254         $this->oPlaceLookup->setIncludeAddressDetails($oParams->getBool('addressdetails', false));
255     }
256
257     public function setQueryFromParams($oParams)
258     {
259         // Search query
260         $this->setStructuredQuery(
261             $oParams->getString('amenity'),
262             $oParams->getString('street'),
263             $oParams->getString('city'),
264             $oParams->getString('county'),
265             $oParams->getString('state'),
266             $oParams->getString('country'),
267             $oParams->getString('postalcode')
268         );
269         if (!$this->sQuery) {
270             $sQuery = $oParams->getString('q');
271
272             if ($sQuery) {
273                 $this->setQuery($sQuery);
274             }
275         }
276     }
277
278     public function loadStructuredAddressElement($sValue, $sKey, $iNewMinAddressRank, $iNewMaxAddressRank, $aItemListValues)
279     {
280         $sValue = trim($sValue);
281         if (!$sValue) {
282             return false;
283         }
284         $this->aStructuredQuery[$sKey] = $sValue;
285         if ($this->iMinAddressRank == 0 && $this->iMaxAddressRank == 30) {
286             $this->iMinAddressRank = $iNewMinAddressRank;
287             $this->iMaxAddressRank = $iNewMaxAddressRank;
288         }
289         if ($aItemListValues) {
290             $this->aAddressRankList = array_merge($this->aAddressRankList, $aItemListValues);
291         }
292         return true;
293     }
294
295     public function setStructuredQuery($sAmenity = false, $sStreet = false, $sCity = false, $sCounty = false, $sState = false, $sCountry = false, $sPostalCode = false)
296     {
297         $this->sQuery = false;
298
299         if ($sAmenity || $sStreet || $sCity || $sCounty || $sState || $sCountry || $sPostalCode) {
300             // Reset
301             $this->iMinAddressRank = 0;
302             $this->iMaxAddressRank = 30;
303             $this->aAddressRankList = array();
304
305             $this->aStructuredQuery = array();
306             $this->sAllowedTypesSQLList = false;
307
308             $this->loadStructuredAddressElement($sAmenity, 'amenity', 26, 30, false);
309             $this->loadStructuredAddressElement($sStreet, 'street', 26, 30, false);
310             $this->loadStructuredAddressElement($sCity, 'city', 14, 24, false);
311             $this->loadStructuredAddressElement($sCounty, 'county', 9, 13, false);
312             $this->loadStructuredAddressElement($sState, 'state', 8, 8, false);
313             $this->loadStructuredAddressElement($sPostalCode, 'postalcode', 5, 11, array(5, 11));
314             $this->loadStructuredAddressElement($sCountry, 'country', 4, 4, false);
315
316             if (!empty($this->aStructuredQuery)) {
317                 $this->sQuery = join(', ', $this->aStructuredQuery);
318                 if ($this->iMaxAddressRank < 30) {
319                     $this->sAllowedTypesSQLList = '(\'place\',\'boundary\')';
320                 }
321             }
322         }
323     }
324
325     public function fallbackStructuredQuery()
326     {
327         $aParams = $this->aStructuredQuery;
328
329         if (!$aParams || count($aParams) == 1) {
330             return false;
331         }
332
333         $aOrderToFallback = array('postalcode', 'street', 'city', 'county', 'state');
334
335         foreach ($aOrderToFallback as $sType) {
336             if (isset($aParams[$sType])) {
337                 unset($aParams[$sType]);
338                 $this->setStructuredQuery(@$aParams['amenity'], @$aParams['street'], @$aParams['city'], @$aParams['county'], @$aParams['state'], @$aParams['country'], @$aParams['postalcode']);
339                 return true;
340             }
341         }
342
343         return false;
344     }
345
346     public function getGroupedSearches($aSearches, $aPhrases, $oValidTokens)
347     {
348         /*
349              Calculate all searches using oValidTokens i.e.
350              'Wodsworth Road, Sheffield' =>
351
352              Phrase Wordset
353              0      0       (wodsworth road)
354              0      1       (wodsworth)(road)
355              1      0       (sheffield)
356
357              Score how good the search is so they can be ordered
358          */
359         foreach ($aPhrases as $iPhrase => $oPhrase) {
360             $aNewPhraseSearches = array();
361             $oPosition = new SearchPosition(
362                 $oPhrase->getPhraseType(),
363                 $iPhrase,
364                 count($aPhrases)
365             );
366
367             foreach ($oPhrase->getWordSets() as $aWordset) {
368                 $aWordsetSearches = $aSearches;
369
370                 // Add all words from this wordset
371                 foreach ($aWordset as $iToken => $sToken) {
372                     $aNewWordsetSearches = array();
373                     $oPosition->setTokenPosition($iToken, count($aWordset));
374
375                     foreach ($aWordsetSearches as $oCurrentSearch) {
376                         foreach ($oValidTokens->get($sToken) as $oSearchTerm) {
377                             if ($oSearchTerm->isExtendable($oCurrentSearch, $oPosition)) {
378                                 $aNewSearches = $oSearchTerm->extendSearch(
379                                     $oCurrentSearch,
380                                     $oPosition
381                                 );
382
383                                 foreach ($aNewSearches as $oSearch) {
384                                     if ($oSearch->getRank() < $this->iMaxRank) {
385                                         $aNewWordsetSearches[] = $oSearch;
386                                     }
387                                 }
388                             }
389                         }
390                     }
391                     // Sort and cut
392                     usort($aNewWordsetSearches, array('Nominatim\SearchDescription', 'bySearchRank'));
393                     $aWordsetSearches = array_slice($aNewWordsetSearches, 0, 50);
394                 }
395
396                 $aNewPhraseSearches = array_merge($aNewPhraseSearches, $aNewWordsetSearches);
397                 usort($aNewPhraseSearches, array('Nominatim\SearchDescription', 'bySearchRank'));
398
399                 $aSearchHash = array();
400                 foreach ($aNewPhraseSearches as $iSearch => $aSearch) {
401                     $sHash = serialize($aSearch);
402                     if (isset($aSearchHash[$sHash])) {
403                         unset($aNewPhraseSearches[$iSearch]);
404                     } else {
405                         $aSearchHash[$sHash] = 1;
406                     }
407                 }
408
409                 $aNewPhraseSearches = array_slice($aNewPhraseSearches, 0, 50);
410             }
411
412             // Re-group the searches by their score, junk anything over 20 as just not worth trying
413             $aGroupedSearches = array();
414             foreach ($aNewPhraseSearches as $aSearch) {
415                 $iRank = $aSearch->getRank();
416                 if ($iRank < $this->iMaxRank) {
417                     if (!isset($aGroupedSearches[$iRank])) {
418                         $aGroupedSearches[$iRank] = array();
419                     }
420                     $aGroupedSearches[$iRank][] = $aSearch;
421                 }
422             }
423             ksort($aGroupedSearches);
424
425             $iSearchCount = 0;
426             $aSearches = array();
427             foreach ($aGroupedSearches as $aNewSearches) {
428                 $iSearchCount += count($aNewSearches);
429                 $aSearches = array_merge($aSearches, $aNewSearches);
430                 if ($iSearchCount > 50) {
431                     break;
432                 }
433             }
434         }
435
436         // Revisit searches, drop bad searches and give penalty to unlikely combinations.
437         $aGroupedSearches = array();
438         foreach ($aSearches as $oSearch) {
439             if (!$oSearch->isValidSearch()) {
440                 continue;
441             }
442
443             $iRank = $oSearch->getRank();
444             if (!isset($aGroupedSearches[$iRank])) {
445                 $aGroupedSearches[$iRank] = array();
446             }
447             $aGroupedSearches[$iRank][] = $oSearch;
448         }
449         ksort($aGroupedSearches);
450
451         return $aGroupedSearches;
452     }
453
454     /* Perform the actual query lookup.
455
456         Returns an ordered list of results, each with the following fields:
457             osm_type: type of corresponding OSM object
458                         N - node
459                         W - way
460                         R - relation
461                         P - postcode (internally computed)
462             osm_id: id of corresponding OSM object
463             class: general object class (corresponds to tag key of primary OSM tag)
464             type: subclass of object (corresponds to tag value of primary OSM tag)
465             admin_level: see https://wiki.openstreetmap.org/wiki/Admin_level
466             rank_search: rank in search hierarchy
467                         (see also https://wiki.openstreetmap.org/wiki/Nominatim/Development_overview#Country_to_street_level)
468             rank_address: rank in address hierarchy (determines orer in address)
469             place_id: internal key (may differ between different instances)
470             country_code: ISO country code
471             langaddress: localized full address
472             placename: localized name of object
473             ref: content of ref tag (if available)
474             lon: longitude
475             lat: latitude
476             importance: importance of place based on Wikipedia link count
477             addressimportance: cumulated importance of address elements
478             extra_place: type of place (for admin boundaries, if there is a place tag)
479             aBoundingBox: bounding Box
480             label: short description of the object class/type (English only)
481             name: full name (currently the same as langaddress)
482             foundorder: secondary ordering for places with same importance
483     */
484
485
486     public function lookup()
487     {
488         Debug::newFunction('Geocode::lookup');
489         if (!$this->sQuery && !$this->aStructuredQuery) {
490             return array();
491         }
492
493         Debug::printDebugArray('Geocode', $this);
494
495         $oCtx = new SearchContext();
496
497         if ($this->aRoutePoints) {
498             $oCtx->setViewboxFromRoute(
499                 $this->oDB,
500                 $this->aRoutePoints,
501                 $this->aRouteWidth,
502                 $this->bBoundedSearch
503             );
504         } elseif ($this->aViewBox) {
505             $oCtx->setViewboxFromBox($this->aViewBox, $this->bBoundedSearch);
506         }
507         if ($this->aExcludePlaceIDs) {
508             $oCtx->setExcludeList($this->aExcludePlaceIDs);
509         }
510         if ($this->aCountryCodes) {
511             $oCtx->setCountryList($this->aCountryCodes);
512         }
513
514         Debug::newSection('Query Preprocessing');
515
516         $sQuery = $this->sQuery;
517         if (!preg_match('//u', $sQuery)) {
518             userError('Query string is not UTF-8 encoded.');
519         }
520
521         // Do we have anything that looks like a lat/lon pair?
522         $sQuery = $oCtx->setNearPointFromQuery($sQuery);
523
524         if ($sQuery || $this->aStructuredQuery) {
525             // Start with a single blank search
526             $aSearches = array(new SearchDescription($oCtx));
527
528             if ($sQuery) {
529                 $sQuery = $aSearches[0]->extractKeyValuePairs($sQuery);
530             }
531
532             $sSpecialTerm = '';
533             if ($sQuery) {
534                 preg_match_all(
535                     '/\\[([\\w ]*)\\]/u',
536                     $sQuery,
537                     $aSpecialTermsRaw,
538                     PREG_SET_ORDER
539                 );
540                 if (!empty($aSpecialTermsRaw)) {
541                     Debug::printVar('Special terms', $aSpecialTermsRaw);
542                 }
543
544                 foreach ($aSpecialTermsRaw as $aSpecialTerm) {
545                     $sQuery = str_replace($aSpecialTerm[0], ' ', $sQuery);
546                     if (!$sSpecialTerm) {
547                         $sSpecialTerm = $aSpecialTerm[1];
548                     }
549                 }
550             }
551             if (!$sSpecialTerm && $this->aStructuredQuery
552                 && isset($this->aStructuredQuery['amenity'])) {
553                 $sSpecialTerm = $this->aStructuredQuery['amenity'];
554                 unset($this->aStructuredQuery['amenity']);
555             }
556
557             if ($sSpecialTerm && !$aSearches[0]->hasOperator()) {
558                 $aTokens = $this->oTokenizer->tokensForSpecialTerm($sSpecialTerm);
559
560                 if (!empty($aTokens)) {
561                     $aNewSearches = array();
562                     $oPosition = new SearchPosition('', 0, 1);
563                     $oPosition->setTokenPosition(0, 1);
564
565                     foreach ($aSearches as $oSearch) {
566                         foreach ($aTokens as $oToken) {
567                             $aNewSearches = array_merge(
568                                 $aNewSearches,
569                                 $oToken->extendSearch($oSearch, $oPosition)
570                             );
571                         }
572                     }
573                     $aSearches = $aNewSearches;
574                 }
575             }
576
577             // Split query into phrases
578             // Commas are used to reduce the search space by indicating where phrases split
579             $aPhrases = array();
580             if ($this->aStructuredQuery) {
581                 foreach ($this->aStructuredQuery as $iPhrase => $sPhrase) {
582                     $aPhrases[] = new Phrase($sPhrase, $iPhrase);
583                 }
584             } else {
585                 foreach (explode(',', $sQuery) as $sPhrase) {
586                     $aPhrases[] = new Phrase($sPhrase, '');
587                 }
588             }
589
590             Debug::printDebugArray('Search context', $oCtx);
591             Debug::printDebugArray('Base search', empty($aSearches) ? null : $aSearches[0]);
592
593             Debug::newSection('Tokenization');
594             $oValidTokens = $this->oTokenizer->extractTokensFromPhrases($aPhrases);
595
596             if ($oValidTokens->count() > 0) {
597                 $oCtx->setFullNameWords($oValidTokens->getFullWordIDs());
598
599                 $aPhrases = array_filter($aPhrases, function ($oPhrase) {
600                     return $oPhrase->getWordSets() !== null;
601                 });
602
603                 // Any words that have failed completely?
604                 // TODO: suggestions
605
606                 Debug::printGroupTable('Valid Tokens', $oValidTokens->debugInfo());
607                 Debug::printDebugTable('Phrases', $aPhrases);
608
609                 Debug::newSection('Search candidates');
610
611                 $aGroupedSearches = $this->getGroupedSearches($aSearches, $aPhrases, $oValidTokens);
612
613                 if (!$this->aStructuredQuery) {
614                     // Reverse phrase array and also reverse the order of the wordsets in
615                     // the first and final phrase. Don't bother about phrases in the middle
616                     // because order in the address doesn't matter.
617                     $aPhrases = array_reverse($aPhrases);
618                     $aPhrases[0]->invertWordSets();
619                     if (count($aPhrases) > 1) {
620                         $aPhrases[count($aPhrases)-1]->invertWordSets();
621                     }
622                     $aReverseGroupedSearches = $this->getGroupedSearches($aSearches, $aPhrases, $oValidTokens);
623
624                     foreach ($aReverseGroupedSearches as $aSearches) {
625                         foreach ($aSearches as $aSearch) {
626                             if (!isset($aGroupedSearches[$aSearch->getRank()])) {
627                                 $aGroupedSearches[$aSearch->getRank()] = array();
628                             }
629                             $aGroupedSearches[$aSearch->getRank()][] = $aSearch;
630                         }
631                     }
632
633                     ksort($aGroupedSearches);
634                 }
635             } else {
636                 // Re-group the searches by their score, junk anything over 20 as just not worth trying
637                 $aGroupedSearches = array();
638                 foreach ($aSearches as $aSearch) {
639                     if ($aSearch->getRank() < $this->iMaxRank) {
640                         if (!isset($aGroupedSearches[$aSearch->getRank()])) {
641                             $aGroupedSearches[$aSearch->getRank()] = array();
642                         }
643                         $aGroupedSearches[$aSearch->getRank()][] = $aSearch;
644                     }
645                 }
646                 ksort($aGroupedSearches);
647             }
648
649             // Filter out duplicate searches
650             $aSearchHash = array();
651             foreach ($aGroupedSearches as $iGroup => $aSearches) {
652                 foreach ($aSearches as $iSearch => $aSearch) {
653                     $sHash = serialize($aSearch);
654                     if (isset($aSearchHash[$sHash])) {
655                         unset($aGroupedSearches[$iGroup][$iSearch]);
656                         if (empty($aGroupedSearches[$iGroup])) {
657                             unset($aGroupedSearches[$iGroup]);
658                         }
659                     } else {
660                         $aSearchHash[$sHash] = 1;
661                     }
662                 }
663             }
664
665             Debug::printGroupedSearch(
666                 $aGroupedSearches,
667                 $oValidTokens->debugTokenByWordIdList()
668             );
669
670             // Start the search process
671             $iGroupLoop = 0;
672             $iQueryLoop = 0;
673             $aNextResults = array();
674             foreach ($aGroupedSearches as $iGroupedRank => $aSearches) {
675                 $iGroupLoop++;
676                 $aResults = $aNextResults;
677                 foreach ($aSearches as $oSearch) {
678                     $iQueryLoop++;
679
680                     Debug::newSection("Search Loop, group $iGroupLoop, loop $iQueryLoop");
681                     Debug::printGroupedSearch(
682                         array($iGroupedRank => array($oSearch)),
683                         $oValidTokens->debugTokenByWordIdList()
684                     );
685
686                     $aNewResults = $oSearch->query(
687                         $this->oDB,
688                         $this->iMinAddressRank,
689                         $this->iMaxAddressRank,
690                         $this->iLimit
691                     );
692
693                     // The same result may appear in different rounds, only
694                     // use the one with minimal rank.
695                     foreach ($aNewResults as $iPlace => $oRes) {
696                         if (!isset($aResults[$iPlace])
697                             || $aResults[$iPlace]->iResultRank > $oRes->iResultRank) {
698                             $aResults[$iPlace] = $oRes;
699                         }
700                     }
701
702                     if ($iQueryLoop > 30) {
703                         break;
704                     }
705                 }
706
707                 if (!empty($aResults)) {
708                     $aSplitResults = Result::splitResults($aResults);
709                     Debug::printVar('Split results', $aSplitResults);
710                     if ($iGroupLoop <= 4
711                         && reset($aSplitResults['head'])->iResultRank > 0
712                         && $iGroupedRank !== array_key_last($aGroupedSearches)) {
713                         // Haven't found an exact match for the query yet.
714                         // Therefore add result from the next group level.
715                         $aNextResults = $aSplitResults['head'];
716                         foreach ($aNextResults as $oRes) {
717                             $oRes->iResultRank--;
718                         }
719                         foreach ($aSplitResults['tail'] as $oRes) {
720                             $oRes->iResultRank--;
721                             $aNextResults[$oRes->iId] = $oRes;
722                         }
723                         $aResults = array();
724                     } else {
725                         $aResults = $aSplitResults['head'];
726                     }
727                 }
728
729                 if (!empty($aResults) && ($this->iMinAddressRank != 0 || $this->iMaxAddressRank != 30)) {
730                     // Need to verify passes rank limits before dropping out of the loop (yuk!)
731                     // reduces the number of place ids, like a filter
732                     // rank_address is 30 for interpolated housenumbers
733                     $aFilterSql = array();
734                     $sPlaceIds = Result::joinIdsByTable($aResults, Result::TABLE_PLACEX);
735                     if ($sPlaceIds) {
736                         $sSQL = 'SELECT place_id FROM placex ';
737                         $sSQL .= 'WHERE place_id in ('.$sPlaceIds.') ';
738                         $sSQL .= '  AND (';
739                         $sSQL .= "         placex.rank_address between $this->iMinAddressRank and $this->iMaxAddressRank ";
740                         $sSQL .= "         OR placex.rank_search between $this->iMinAddressRank and $this->iMaxAddressRank ";
741                         if ($this->aAddressRankList) {
742                             $sSQL .= '     OR placex.rank_address in ('.join(',', $this->aAddressRankList).')';
743                         }
744                         $sSQL .= ')';
745                         $aFilterSql[] = $sSQL;
746                     }
747                     $sPlaceIds = Result::joinIdsByTable($aResults, Result::TABLE_POSTCODE);
748                     if ($sPlaceIds) {
749                         $sSQL = ' SELECT place_id FROM location_postcode lp ';
750                         $sSQL .= 'WHERE place_id in ('.$sPlaceIds.') ';
751                         $sSQL .= "  AND (lp.rank_address between $this->iMinAddressRank and $this->iMaxAddressRank ";
752                         if ($this->aAddressRankList) {
753                             $sSQL .= '     OR lp.rank_address in ('.join(',', $this->aAddressRankList).')';
754                         }
755                         $sSQL .= ') ';
756                         $aFilterSql[] = $sSQL;
757                     }
758
759                     $aFilteredIDs = array();
760                     if ($aFilterSql) {
761                         $sSQL = join(' UNION ', $aFilterSql);
762                         Debug::printSQL($sSQL);
763                         $aFilteredIDs = $this->oDB->getCol($sSQL);
764                     }
765
766                     $tempIDs = array();
767                     foreach ($aResults as $oResult) {
768                         if (($this->iMaxAddressRank == 30 &&
769                              ($oResult->iTable == Result::TABLE_OSMLINE
770                               || $oResult->iTable == Result::TABLE_TIGER))
771                             || in_array($oResult->iId, $aFilteredIDs)
772                         ) {
773                             $tempIDs[$oResult->iId] = $oResult;
774                         }
775                     }
776                     $aResults = $tempIDs;
777                 }
778
779                 if (!empty($aResults) || $iGroupLoop > 6 || $iQueryLoop > 40) {
780                     break;
781                 }
782             }
783         } else {
784             // Just interpret as a reverse geocode
785             $oReverse = new ReverseGeocode($this->oDB);
786             $oReverse->setZoom(18);
787
788             $oLookup = $oReverse->lookupPoint($oCtx->sqlNear, false);
789
790             Debug::printVar('Reverse search', $oLookup);
791
792             if ($oLookup) {
793                 $aResults = array($oLookup->iId => $oLookup);
794             }
795         }
796
797         // No results? Done
798         if (empty($aResults)) {
799             if ($this->bFallback && $this->fallbackStructuredQuery()) {
800                 return $this->lookup();
801             }
802
803             return array();
804         }
805
806         if ($this->aAddressRankList) {
807             $this->oPlaceLookup->setAddressRankList($this->aAddressRankList);
808         }
809         $this->oPlaceLookup->setAllowedTypesSQLList($this->sAllowedTypesSQLList);
810         $this->oPlaceLookup->setLanguagePreference($this->aLangPrefOrder);
811         if ($oCtx->hasNearPoint()) {
812             $this->oPlaceLookup->setAnchorSql($oCtx->sqlNear);
813         }
814
815         $aSearchResults = $this->oPlaceLookup->lookup($aResults);
816
817         $aRecheckWords = preg_split('/\b[\s,\\-]*/u', $sQuery);
818         foreach ($aRecheckWords as $i => $sWord) {
819             if (!preg_match('/[\pL\pN]/', $sWord)) {
820                 unset($aRecheckWords[$i]);
821             }
822         }
823
824         Debug::printVar('Recheck words', $aRecheckWords);
825
826         foreach ($aSearchResults as $iIdx => $aResult) {
827             $fRadius = ClassTypes\getDefRadius($aResult);
828
829             $aOutlineResult = $this->oPlaceLookup->getOutlines($aResult['place_id'], $aResult['lon'], $aResult['lat'], $fRadius);
830             if ($aOutlineResult) {
831                 $aResult = array_merge($aResult, $aOutlineResult);
832             }
833
834             // Is there an icon set for this type of result?
835             $sIcon = ClassTypes\getIconFile($aResult);
836             if (isset($sIcon)) {
837                 $aResult['icon'] = $sIcon;
838             }
839
840             $sLabel = ClassTypes\getLabel($aResult);
841             if (isset($sLabel)) {
842                 $aResult['label'] = $sLabel;
843             }
844             $aResult['name'] = $aResult['langaddress'];
845
846             if ($oCtx->hasNearPoint()) {
847                 $aResult['importance'] = 0.001;
848                 $aResult['foundorder'] = $aResult['addressimportance'];
849             } else {
850                 if ($aResult['importance'] == 0) {
851                     $aResult['importance'] = 0.0001;
852                 }
853                 $aResult['importance'] *= $this->viewboxImportanceFactor(
854                     $aResult['lon'],
855                     $aResult['lat']
856                 );
857
858                 // secondary ordering (for results with same importance (the smaller the better):
859                 // - approximate importance of address parts
860                 if (isset($aResult['addressimportance']) && $aResult['addressimportance']) {
861                     $aResult['foundorder'] = -$aResult['addressimportance']/10;
862                 } else {
863                     $aResult['foundorder'] = -$aResult['importance'];
864                 }
865                 // - number of exact matches from the query
866                 $aResult['foundorder'] -= $aResults[$aResult['place_id']]->iExactMatches;
867                 // - importance of the class/type
868                 $iClassImportance = ClassTypes\getImportance($aResult);
869                 if (isset($iClassImportance)) {
870                     $aResult['foundorder'] += 0.0001 * $iClassImportance;
871                 } else {
872                     $aResult['foundorder'] += 0.01;
873                 }
874                 // - rank
875                 $aResult['foundorder'] -= 0.00001 * (30 - $aResult['rank_search']);
876
877                 // Adjust importance for the number of exact string matches in the result
878                 $iCountWords = 0;
879                 $sAddress = $aResult['langaddress'];
880                 foreach ($aRecheckWords as $i => $sWord) {
881                     if (grapheme_stripos($sAddress, $sWord)!==false) {
882                         $iCountWords++;
883                         if (preg_match('/(^|,)\s*'.preg_quote($sWord, '/').'\s*(,|$)/', $sAddress)) {
884                             $iCountWords += 0.1;
885                         }
886                     }
887                 }
888
889                 // 0.1 is a completely arbitrary number but something in the range 0.1 to 0.5 would seem right
890                 $aResult['importance'] = $aResult['importance'] + ($iCountWords*0.1);
891             }
892             $aSearchResults[$iIdx] = $aResult;
893         }
894         uasort($aSearchResults, 'byImportance');
895         Debug::printVar('Pre-filter results', $aSearchResults);
896
897         $aOSMIDDone = array();
898         $aClassTypeNameDone = array();
899         $aToFilter = $aSearchResults;
900         $aSearchResults = array();
901
902         foreach ($aToFilter as $aResult) {
903             $this->aExcludePlaceIDs[$aResult['place_id']] = $aResult['place_id'];
904             if (!$this->oPlaceLookup->doDeDupe() || (!isset($aOSMIDDone[$aResult['osm_type'].$aResult['osm_id']])
905                 && !isset($aClassTypeNameDone[$aResult['osm_type'].$aResult['class'].$aResult['type'].$aResult['name'].$aResult['admin_level']]))
906             ) {
907                 $aOSMIDDone[$aResult['osm_type'].$aResult['osm_id']] = true;
908                 $aClassTypeNameDone[$aResult['osm_type'].$aResult['class'].$aResult['type'].$aResult['name'].$aResult['admin_level']] = true;
909                 $aSearchResults[] = $aResult;
910             }
911
912             // Absolute limit on number of results
913             if (count($aSearchResults) >= $this->iFinalLimit) {
914                 break;
915             }
916         }
917
918         Debug::printVar('Post-filter results', $aSearchResults);
919         return $aSearchResults;
920     } // end lookup()
921
922     public function debugInfo()
923     {
924         return array(
925                 'Query' => $this->sQuery,
926                 'Structured query' => $this->aStructuredQuery,
927                 'Name keys' => Debug::fmtArrayVals($this->aLangPrefOrder),
928                 'Excluded place IDs' => Debug::fmtArrayVals($this->aExcludePlaceIDs),
929                 'Limit (for searches)' => $this->iLimit,
930                 'Limit (for results)'=> $this->iFinalLimit,
931                 'Country codes' => Debug::fmtArrayVals($this->aCountryCodes),
932                 'Bounded search' => $this->bBoundedSearch,
933                 'Viewbox' => Debug::fmtArrayVals($this->aViewBox),
934                 'Route points' => Debug::fmtArrayVals($this->aRoutePoints),
935                 'Route width' => $this->aRouteWidth,
936                 'Max rank' => $this->iMaxRank,
937                 'Min address rank' => $this->iMinAddressRank,
938                 'Max address rank' => $this->iMaxAddressRank,
939                 'Address rank list' => Debug::fmtArrayVals($this->aAddressRankList)
940                );
941     }
942 } // end class