1 ///
2 /// Convert a filter into a list of queries based on a list of capabilities.
3 /// @file querylist.cpp - pianod
4 /// @author Perette Barella
5 /// @date 2015-01-21
6 /// @copyright Copyright 2015-2017 Devious Fish. All rights reserved.
7 ///
8
9 #include <config.h>
10
11 #include <exception>
12 #include <stdexcept>
13
14 #include "querylist.h"
15
16 namespace Query {
17 using namespace std;
18
19 /** Create a new query and calculate its quality. */
Details(Filter::Field filter_field,Filter::Field field,SearchMethod method,const char * val)20 Details::Details (Filter::Field filter_field,
21 Filter::Field field, SearchMethod method, const char *val)
22 : filterField (filter_field), searchField (field),
23 searchMethod (method), value (val) {
24 assert (method != SearchMethodNone);
25
26 // For less exacting comparison methods, string length matters more.
27 float good_length = (method == ExactCompare ? 1 :
28 method == MatchBeginning ? 6 : 20);
29 // Assess string length, but give some bonus for using a specified field.
30 quality = ((float (value.length()) / good_length) *
31 (field == Filter::Field::Search ? 3.0 : 1.0));
32 if (quality > 1.0f) quality = 1.0f;
33 }
34
35 /** Determine field preference for a query list.
36 Preference is the sum of the field preferences. */
preference(const Constraints & con) const37 unsigned DetailList::preference (const Constraints &con) const {
38 unsigned pref = 0;
39 for (auto const &item: *this) {
40 pref += con.fieldPreference [item.filterField];
41 }
42 return pref;
43 }
44
45 /** Calculate quality for a details list.
46 Quality improves the more specific it is. */
quality() const47 float DetailList::quality() const {
48 if (empty())
49 return 99999.0; // Very specific: never return anything.
50 float qual = 0.0;
51 for (auto const &item: *this) {
52 qual += item.quality;
53 }
54 if (qual > 1.0f) qual = 1.0f;
55 return qual;
56 }
57
58
59
60 /** Determine field preference for a query list.
61 Preference is the highest-preference query detail list. */
preference(const Constraints & con) const62 unsigned Queries::preference(const Constraints &con) const {
63 unsigned pref = 0;
64 for (auto const &item: *this) {
65 unsigned this_pref = item.preference (con);
66 if (this_pref > pref) {
67 pref = this_pref;
68 }
69 }
70 return pref;
71 }
72
73 /** Calculate quality for a query list.
74 Quality declines the less specific it is;
75 i.e., more queries is bad. */
quality() const76 float Queries::quality() const {
77 if (empty())
78 return 99999.0; // Very specific: never return anything.
79 float qual = 1.0f;
80 for (auto const &item: *this) {
81 qual *= item.quality();
82 }
83 return qual;
84 }
85
86
87 /** Determine the best method of querying for a field, taking
88 into account the source's capabilities. */
findMethodForField(SearchMethod requestedMethod,Filter::Field field)89 SearchMethod List::findMethodForField (SearchMethod requestedMethod,
90 Filter::Field field) {
91
92 if (requestedMethod == ExactCompare &&
93 capabilities.canExactCompare [field]) {
94 return ExactCompare;
95 }
96
97 if ((requestedMethod == ExactCompare ||
98 requestedMethod == MatchBeginning) &&
99 capabilities.canMatchBeginning [field]) {
100 return MatchBeginning;
101 }
102
103 if (capabilities.canSubstringMatch [field]) {
104 return SubstringMatch;
105 }
106
107 return SearchMethodNone;
108 }
109
110
interpretComparison(const Filter::Operation * filter)111 Details List::interpretComparison (const Filter::Operation *filter) {
112 // Special case of YEAR = n.
113 if (filter->field == Filter::Field::Year &&
114 filter->action == Filter::Action::Equal &&
115 capabilities.canExactCompare [Filter::Field::Year]) {
116 return Details (Filter::Field::Year, Filter::Field::Year,
117 SearchMethod::ExactCompare,
118 to_string (filter->value.numeric).c_str());
119 }
120
121
122 if (!Filter::Operation::isStringField (filter->field))
123 throw impossible();
124
125 // Filter match length is set to strlen + 1 for exact match
126 // (Ensuring null byte checked.)
127 // fa_equal && match_length == strlen (value) is wildcard (beginning) search.
128 // fa_equal && match_length
129 // fa_match -> substring search.
130
131 // First see if we support the thing natively.
132 SearchMethod requestedMethod;
133 switch (filter->action) {
134 case Filter::Action::Equal:
135 requestedMethod = (strlen (filter->value.string.value) < filter->value.string.match_length
136 ? ExactCompare : MatchBeginning);
137 break;
138 case Filter::Action::Match:
139 requestedMethod = SubstringMatch;
140 break;
141 default:
142 {
143 throw impossible();
144 }
145 }
146
147 SearchMethod actualMethod = findMethodForField (requestedMethod, filter->field);
148 if (actualMethod != SearchMethodNone) {
149 return Details (filter->field, filter->field, actualMethod, filter->value.string.value);
150 }
151
152 if (!capabilities.fieldInGeneralSearch [filter->field])
153 throw impossible();
154
155 actualMethod = findMethodForField (requestedMethod, Filter::Field::Search);
156 return Details (filter->field, Filter::Field::Search, actualMethod, filter->value.string.value);
157 };
158
159
interpretAnd(const Filter::Operation * filter)160 Queries List::interpretAnd (const Filter::Operation *filter) {
161 Queries left (interpret (filter->value.nodes.l_eval));
162 Queries right (interpret (filter->value.nodes.r_eval));
163
164 // We can't handle ORs within ANDs. Avoid them.
165 if (left.size() > 1 && right.size() >> 1)
166 return Queries {};
167 if (left.size() != 1) return right;
168 if (right.size() != 1) return left;
169
170 // If we have AND capabilities, assemble them.
171 if (capabilities.andCapable) {
172 for (const Details &details: right [0]) {
173 left [0].push_back (details);
174 }
175 return left;
176 }
177
178 // If certain queries are preferred, use those.
179 int pref = (left.preference(capabilities) -
180 right.preference (capabilities));
181 if (pref)
182 return pref > 0 ? left : right;
183
184 // If no preference, subjectively pick the "best"
185 // query of the two (based on specificity of queries).
186 return (left.quality() < right.quality()
187 ? right : left);
188 }
189
interpret(const Filter::Operation * filter)190 Queries List::interpret (const Filter::Operation *filter) {
191 switch (filter->action) {
192 case Filter::Action::And:
193 {
194 return interpretAnd (filter);
195 }
196 case Filter::Action::Or:
197 {
198 Queries left (interpret (filter->value.nodes.l_eval));
199 // Impossible; need both for OR
200 if (left.empty())
201 return left;
202
203 Queries right (interpret (filter->value.nodes.r_eval));
204 left.insert (left.begin(), right.begin(), right.end());
205 return left;
206 }
207 case Filter::Action::Noop:
208 // False or compilation checks; these queries never return anything
209 return Queries();
210 default:
211 {
212 Queries results;
213 try {
214 DetailList details;
215 details.push_back (interpretComparison (filter));
216 results.push_back (details);
217 return results;
218 } catch (const impossible &) {
219 return results;
220 }
221 }
222 }
223 }
224
225 /** Build a query directly from a permuted filter. */
interpretFuzzy(const PermutedFilter & filter)226 Queries List::interpretFuzzy (const PermutedFilter &filter) {
227 assert (filter.parsetree);
228 Filter::Field target = filter.target_field;
229 if (!capabilities.participatesInFuzzy [target] &&
230 capabilities.fieldInGeneralSearch [target]) {
231 target = Filter::Field::Search;
232 }
233 if (capabilities.participatesInFuzzy [target]) {
234 Queries queries;
235 for (auto const phrase : filter.phrases) {
236 DetailList detail_list;
237 detail_list.push_back (Details { filter.target_field, target, Fuzzy, phrase.c_str() });
238 queries.push_back (detail_list);
239 }
240 return queries;
241 }
242 return interpret (filter.parsetree.get());
243 }
244
245
List(const Filter & filter,const Constraints & constraints)246 List::List (const Filter &filter, const Constraints &constraints)
247 : capabilities (constraints) {
248 Queries queries {
249 typeid (filter) == typeid (PermutedFilter) ?
250 interpretFuzzy (static_cast <const PermutedFilter &> (filter)) :
251 interpret(filter.parsetree.get()) };
252
253 if (queries.empty())
254 throw impossible();
255 insert (begin(), queries.begin(), queries.end());
256 }
257
258 }
259
260
261
262 #ifdef FILTER_TEST
main(int argc,char ** argv)263 int main (int argc, char **argv) {
264 Filter filter_search("'art of noise'");
265 Filter filter_and ("artist = \"madonna\" && albumname =~ 'like a virgin'");
266 Filter filter_or("artist='aqua' || artist =~ 'ace of bass'");
267
268 Query::Constraints noCapability;
269
270 Query::Constraints broadSearchOnly;
271 broadSearchOnly.canSubstringMatch [Filter::ff_search] = true;
272 broadSearchOnly.fieldInGeneralSearch [Filter::ff_author] = true;
273 broadSearchOnly.fieldInGeneralSearch [Filter::ff_title] = true;
274
275 Query::Constraints canSpecificSearch;
276 canSpecificSearch.canExactCompare [Filter::ff_author] = true;
277 canSpecificSearch.canExactCompare [Filter::ff_title] = true;
278 canSpecificSearch.canSubstringMatch [Filter::ff_author] = true;
279 canSpecificSearch.canSubstringMatch [Filter::ff_title] = true;
280 canSpecificSearch.canSubstringMatch [Filter::ff_albumname] = true;
281 canSpecificSearch.canSubstringMatch [Filter::ff_search] = true;
282 canSpecificSearch.fieldInGeneralSearch [Filter::ff_search] = true;
283 canSpecificSearch.fieldInGeneralSearch [Filter::ff_author] = true;
284 canSpecificSearch.fieldInGeneralSearch [Filter::ff_title] = true;
285 canSpecificSearch.fieldInGeneralSearch [Filter::ff_albumname] = true;
286
287 Query::List search_none (filter_search, noCapability);
288 assert (search_none.empty());
289
290 Query::List and_none (filter_and, noCapability);
291 assert (search_none.empty());
292
293 Query::List or_none (filter_or, noCapability);
294 assert (or_none.empty());
295
296
297
298
299 Query::List search_broad (filter_search, broadSearchOnly);
300 assert (!search_broad.empty());
301
302 Query::List and_broad (filter_and, broadSearchOnly);
303 assert (!search_broad.empty());
304
305 Query::List or_broad (filter_or, broadSearchOnly);
306 assert (!or_broad.empty());
307
308
309
310 Query::List search_specific (filter_search, canSpecificSearch);
311 assert (!search_specific.empty());
312
313 Query::List and_specific (filter_and, canSpecificSearch);
314 assert (!search_specific.empty());
315
316 Query::List or_specific (filter_or, canSpecificSearch);
317 assert (!or_specific.empty());
318
319
320
321
322 return 0;
323 }
324 #endif
325