xref: /haiku/headers/private/file_systems/QueryParser.h (revision bb1f240594d1524129ed34853f0c325b1a6a1a43)
1 /*
2  * Copyright 2001-2014, Axel Dörfler, axeld@pinc-software.de.
3  * Copyright 2010, Clemens Zeidler <haiku@clemens-zeidler.de>
4  * Copyright 2011, Ingo Weinhold, ingo_weinhold@gmx.de.
5  * This file may be used under the terms of the MIT License.
6  */
7 #ifndef _FILE_SYSTEMS_QUERY_PARSER_H
8 #define _FILE_SYSTEMS_QUERY_PARSER_H
9 
10 
11 /*!	Query parsing and evaluation. */
12 
13 
14 // The operator precedence is =,!=,>,<,>=,<= .. && .. ||.
15 // Apparently, the "!" (not) can only be used with parentheses.
16 //
17 // If you think that there are too few NULL pointer checks in some places
18 // of the code, just read the beginning of the query constructor.
19 // The API is not fully available, just the Query and the Expression class
20 // are.
21 
22 #ifdef FS_SHELL
23 #	include <new>
24 
25 #	include "fssh_api_wrapper.h"
26 #	include "fssh_auto_deleter.h"
27 #else
28 #	include <dirent.h>
29 #	include <stdlib.h>
30 #	include <string.h>
31 
32 #	include <algorithm>
33 #	include <new>
34 
35 #	include <fs_interface.h>
36 #	include <fs_query.h>
37 #	include <TypeConstants.h>
38 
39 #	include <util/SinglyLinkedList.h>
40 #	include <util/Stack.h>
41 
42 #	include <query_private.h>
43 #endif	// !FS_SHELL
44 
45 #include <file_systems/QueryParserUtils.h>
46 
47 
48 //#define DEBUG_QUERY
49 
50 #ifndef QUERY_RETURN_ERROR
51 #	define QUERY_RETURN_ERROR(error)	return (error)
52 #endif
53 
54 #ifndef QUERY_REPORT_ERROR
55 #	define QUERY_REPORT_ERROR(error)	do {} while (false)
56 #endif
57 
58 #ifndef QUERY_FATAL
59 #	define QUERY_FATAL(message...)		panic(message)
60 #endif
61 
62 #ifndef QUERY_INFORM
63 #	define QUERY_INFORM(message...)		dprintf(message)
64 #endif
65 
66 #ifndef QUERY_D
67 #	define QUERY_D(block)
68 #endif
69 
70 
71 namespace QueryParser {
72 
73 
74 template<typename QueryPolicy> class Equation;
75 template<typename QueryPolicy> class Expression;
76 template<typename QueryPolicy> class Term;
77 template<typename QueryPolicy> class Query;
78 
79 
80 enum ops {
81 	OP_NONE,
82 
83 	OP_AND,
84 	OP_OR,
85 
86 	OP_EQUATION,
87 		// is only used for invalid equations
88 
89 	OP_EQUAL,
90 	OP_UNEQUAL,
91 	OP_GREATER_THAN,
92 	OP_LESS_THAN,
93 	OP_GREATER_THAN_OR_EQUAL,
94 	OP_LESS_THAN_OR_EQUAL,
95 };
96 
97 
98 template<typename QueryPolicy>
99 union value {
100 	int64	Int64;
101 	uint64	Uint64;
102 	int32	Int32;
103 	uint32	Uint32;
104 	float	Float;
105 	double	Double;
106 	char	String[QueryPolicy::kMaxFileNameLength];
107 };
108 
109 
110 template<typename QueryPolicy>
111 class Query {
112 public:
113 			typedef typename QueryPolicy::Entry Entry;
114 			typedef typename QueryPolicy::Index Index;
115 			typedef typename QueryPolicy::IndexIterator IndexIterator;
116 			typedef typename QueryPolicy::Node Node;
117 			typedef typename QueryPolicy::NodeHolder NodeHolder;
118 			typedef typename QueryPolicy::Context Context;
119 
120 public:
121 							Query(Context* context,
122 								Expression<QueryPolicy>* expression,
123 								uint32 flags, port_id port, uint32 token);
124 							~Query();
125 
126 	static	status_t		Create(Context* context, const char* queryString,
127 								uint32 flags, port_id port, uint32 token,
128 								Query<QueryPolicy>*& _query);
129 
130 			status_t		Rewind();
131 	inline	status_t		GetNextEntry(struct dirent* dirent, size_t size);
132 
133 			void			LiveUpdate(Entry* entry, Node* node,
134 								const char* attribute, int32 type,
135 								const uint8* oldKey, size_t oldLength,
136 								const uint8* newKey, size_t newLength);
137 			void			LiveUpdateRenameMove(Entry* entry, Node* node,
138 								ino_t oldDirectoryID, const char* oldName,
139 								size_t oldLength, ino_t newDirectoryID,
140 								const char* newName, size_t newLength);
141 
GetExpression()142 			Expression<QueryPolicy>* GetExpression() const
143 								{ return fExpression; }
144 
Flags()145 			uint32			Flags() const
146 								{ return fFlags; }
147 
148 private:
149 			status_t		_GetNextEntry(struct dirent* dirent, size_t size);
150 			void			_SendEntryNotification(Entry* entry,
151 								status_t (*notify)(port_id, int32, dev_t, ino_t,
152 									const char*, ino_t));
153 
154 private:
155 			Context*		fContext;
156 			Expression<QueryPolicy>* fExpression;
157 			Equation<QueryPolicy>* fCurrent;
158 			IndexIterator*	fIterator;
159 			Index			fIndex;
160 			Stack<Equation<QueryPolicy>*> fStack;
161 
162 			uint32			fFlags;
163 			port_id			fPort;
164 			int32			fToken;
165 			bool			fNeedsEntry;
166 };
167 
168 
169 /*!	Abstract base class for the operator/equation classes.
170 */
171 template<typename QueryPolicy>
172 class Term {
173 public:
174 			typedef typename QueryPolicy::Entry Entry;
175 			typedef typename QueryPolicy::Index Index;
176 			typedef typename QueryPolicy::IndexIterator IndexIterator;
177 			typedef typename QueryPolicy::Node Node;
178 			typedef typename QueryPolicy::NodeHolder NodeHolder;
179 			typedef typename QueryPolicy::Context Context;
180 
181 public:
Term(int8 op)182 						Term(int8 op) : fOp(op), fParent(NULL) {}
~Term()183 	virtual				~Term() {}
184 
Op()185 			int8		Op() const { return fOp; }
186 
SetParent(Term<QueryPolicy> * parent)187 			void		SetParent(Term<QueryPolicy>* parent)
188 							{ fParent = parent; }
Parent()189 			Term<QueryPolicy>* Parent() const { return fParent; }
190 
191 	virtual	status_t	Match(Entry* entry, Node* node,
192 							const char* attribute = NULL, int32 type = 0,
193 							const uint8* key = NULL, size_t size = 0) = 0;
194 	virtual	void		Complement() = 0;
195 
196 	virtual	void		CalculateScore(Index& index) = 0;
197 	virtual	int32		Score() const = 0;
198 
199 	virtual	status_t	InitCheck() = 0;
200 
201 	virtual	bool		NeedsEntry() = 0;
202 
203 #ifdef DEBUG_QUERY
204 	virtual	void		PrintToStream() = 0;
205 #endif
206 
207 protected:
208 			int8		fOp;
209 			Term<QueryPolicy>* fParent;
210 };
211 
212 
213 /*!	An Equation object represents an "attribute-equation operator-value" pair.
214 
215 	Although an Equation object is quite independent from the volume on which
216 	the query is run, there are some dependencies that are produced while
217 	querying:
218 	The type/size of the value, the score, and if it has an index or not.
219 	So you could run more than one query on the same volume, but it might return
220 	wrong values when it runs concurrently on another volume.
221 	That's not an issue right now, because we run single-threaded and don't use
222 	queries more than once.
223 */
224 template<typename QueryPolicy>
225 class Equation : public Term<QueryPolicy> {
226 public:
227 			typedef typename QueryPolicy::Entry Entry;
228 			typedef typename QueryPolicy::Index Index;
229 			typedef typename QueryPolicy::IndexIterator IndexIterator;
230 			typedef typename QueryPolicy::Node Node;
231 			typedef typename QueryPolicy::NodeHolder NodeHolder;
232 			typedef typename QueryPolicy::Context Context;
233 
234 public:
235 						Equation(const char** expression);
236 	virtual				~Equation();
237 
238 	virtual	status_t	InitCheck();
239 
240 			status_t	ParseQuotedString(const char** _start, const char** _end);
241 			char*		CopyString(const char* start, const char* end);
242 	inline	bool		_IsEquationChar(char c) const;
243 	inline	bool		_IsOperatorChar(char c) const;
244 
245 	virtual	status_t	Match(Entry* entry, Node* node,
246 							const char* attribute = NULL, int32 type = 0,
247 							const uint8* key = NULL, size_t size = 0);
248 	virtual void		Complement();
249 
250 			status_t	PrepareQuery(Context* context, Index& index,
251 							IndexIterator** iterator, bool queryNonIndexed);
252 			status_t	GetNextMatching(Context* context,
253 							IndexIterator* iterator, struct dirent* dirent,
254 							size_t bufferSize);
255 
256 	virtual	void		CalculateScore(Index &index);
Score()257 	virtual	int32		Score() const { return fScore; }
258 
259 	virtual	bool		NeedsEntry();
260 
261 #ifdef DEBUG_QUERY
262 	virtual	void		PrintToStream();
263 #endif
264 
265 private:
266 						Equation(const Equation& other);
267 						Equation& operator=(const Equation& other);
268 							// no implementation
269 
270 			status_t	ConvertValue(type_code type, uint32 size);
271 			bool		CompareTo(const uint8* value, size_t size);
Value()272 			uint8*		Value() const { return (uint8*)&fValue; }
273 
274 			char*		fAttribute;
275 			char*		fString;
276 			union value<QueryPolicy> fValue;
277 			type_code	fType;
278 			uint32		fSize;
279 			bool		fIsPattern;
280 
281 			int32		fScore;
282 			bool		fHasIndex;
283 };
284 
285 
286 /*!	The Operator class does not represent a generic operator, but only those
287 	that combine two equations, namely "or", and "and".
288 */
289 template<typename QueryPolicy>
290 class Operator : public Term<QueryPolicy> {
291 public:
292 			typedef typename QueryPolicy::Entry Entry;
293 			typedef typename QueryPolicy::Index Index;
294 			typedef typename QueryPolicy::IndexIterator IndexIterator;
295 			typedef typename QueryPolicy::Node Node;
296 			typedef typename QueryPolicy::Context Context;
297 
298 public:
299 						Operator(Term<QueryPolicy>* left, int8 op,
300 							Term<QueryPolicy>* right);
301 	virtual				~Operator();
302 
303 			Term<QueryPolicy>* Left() const { return fLeft; }
304 			Term<QueryPolicy>* Right() const { return fRight; }
305 
306 	virtual	status_t	Match(Entry* entry, Node* node,
307 							const char* attribute = NULL, int32 type = 0,
308 							const uint8* key = NULL, size_t size = 0);
309 	virtual	void		Complement();
310 
311 	virtual	void		CalculateScore(Index& index);
312 	virtual	int32		Score() const;
313 
314 	virtual	status_t	InitCheck();
315 
316 	virtual	bool		NeedsEntry();
317 
318 #ifdef DEBUG_QUERY
319 	virtual	void		PrintToStream();
320 #endif
321 
322 private:
323 						Operator(const Operator& other);
324 						Operator& operator=(const Operator& other);
325 							// no implementation
326 
327 			Term<QueryPolicy>* fLeft;
328 			Term<QueryPolicy>* fRight;
329 };
330 
331 
332 template<typename QueryPolicy>
333 class Expression {
334 public:
335 			typedef typename QueryPolicy::Entry Entry;
336 			typedef typename QueryPolicy::Index Index;
337 			typedef typename QueryPolicy::IndexIterator IndexIterator;
338 			typedef typename QueryPolicy::Node Node;
339 			typedef typename QueryPolicy::Context Context;
340 
341 public:
342 							Expression();
343 							~Expression();
344 
345 			status_t		Init(const char* expr, const char** position);
346 
347 			Term<QueryPolicy>* Root() const { return fTerm; }
348 
349 protected:
350 			bool			IsOperator(const char** expr, char op);
351 
352 private:
353 							Expression(const Expression& other);
354 							Expression& operator=(const Expression& other);
355 								// no implementation
356 
357 			Term<QueryPolicy>* fTerm;
358 };
359 
360 
361 //	#pragma mark -
362 
363 
364 template<typename QueryPolicy>
365 Equation<QueryPolicy>::Equation(const char** expr)
366 	:
367 	Term<QueryPolicy>(OP_EQUATION),
368 	fAttribute(NULL),
369 	fString(NULL),
370 	fType(0),
371 	fIsPattern(false),
372 	fScore(INT32_MAX)
373 {
374 	const char* string = *expr;
375 	const char* start = string;
376 	const char* end = NULL;
377 
378 	// Since the equation is the integral part of any query, we're just parsing
379 	// the whole thing here.
380 	// The whitespace at the start is already removed in
381 	// Expression::ParseEquation()
382 
383 	if (*start == '"' || *start == '\'') {
384 		// string is quoted (start has to be on the beginning of a string)
385 		if (ParseQuotedString(&start, &end) < B_OK)
386 			return;
387 
388 		// set string to a valid start of the equation symbol
389 		string = end + 2;
390 		skipWhitespace(&string);
391 		if (!_IsEquationChar(string[0])) {
392 			*expr = string;
393 			return;
394 		}
395 	} else {
396 		// search the (in)equation for the actual equation symbol (and for other operators
397 		// in case the equation is malformed)
398 		while (string[0] != 0 && !_IsOperatorChar(string[0])
399 			&& !_IsEquationChar(string[0])) {
400 			if (string[0] == '\\' && string[1] != 0)
401 				string++;
402 			string++;
403 		}
404 
405 		// get the attribute string	(and trim whitespace), in case
406 		// the string was not quoted
407 		end = string - 1;
408 		skipWhitespaceReverse(&end, start);
409 	}
410 
411 	// attribute string is empty (which is not allowed)
412 	if (start > end)
413 		return;
414 
415 	// At this point, "start" points to the beginning of the string, "end"
416 	// points to the last character of the string, and "string" points to the
417 	// first character of the equation symbol
418 
419 	// test for the right symbol (as this doesn't need any memory)
420 	switch (*string) {
421 		case '=':
422 			Term<QueryPolicy>::fOp = OP_EQUAL;
423 			break;
424 		case '>':
425 			Term<QueryPolicy>::fOp = *(string + 1) == '='
426 				? OP_GREATER_THAN_OR_EQUAL : OP_GREATER_THAN;
427 			break;
428 		case '<':
429 			Term<QueryPolicy>::fOp = *(string + 1) == '='
430 				? OP_LESS_THAN_OR_EQUAL : OP_LESS_THAN;
431 			break;
432 		case '!':
433 			if (*(string + 1) != '=')
434 				return;
435 			Term<QueryPolicy>::fOp = OP_UNEQUAL;
436 			break;
437 
438 		// any invalid characters will be rejected
439 		default:
440 			*expr = string;
441 			return;
442 	}
443 
444 	// lets change "start" to point to the first character after the symbol
445 	if (*(string + 1) == '=')
446 		string++;
447 	string++;
448 	skipWhitespace(&string);
449 
450 	// allocate & copy the attribute string
451 
452 	fAttribute = CopyString(start, end);
453 	if (fAttribute == NULL)
454 		return;
455 
456 	start = string;
457 	if (*start == '"' || *start == '\'') {
458 		// string is quoted (start has to be on the beginning of a string)
459 		if (ParseQuotedString(&start, &end) < B_OK)
460 			return;
461 
462 		string = end + 2;
463 		skipWhitespace(&string);
464 	} else {
465 		while (string[0] && !_IsOperatorChar(string[0]) && string[0] != ')')
466 			string++;
467 
468 		end = string - 1;
469 		skipWhitespaceReverse(&end, start);
470 	}
471 
472 	// at this point, "start" will point to the first character of the value,
473 	// "end" will point to its last character, and "start" to the first non-
474 	// whitespace character after the value string
475 
476 	fString = CopyString(start, end);
477 	if (fString == NULL)
478 		return;
479 
480 	// patterns are only allowed for these operations (and strings)
481 	if (Term<QueryPolicy>::fOp == OP_EQUAL
482 		|| Term<QueryPolicy>::fOp == OP_UNEQUAL) {
483 		fIsPattern = isPattern(fString);
484 		if (fIsPattern && isValidPattern(fString) < B_OK) {
485 			// we only want to have valid patterns; setting fString
486 			// to NULL will cause InitCheck() to fail
487 			free(fString);
488 			fString = NULL;
489 		}
490 	}
491 
492 	*expr = string;
493 }
494 
495 
496 template<typename QueryPolicy>
497 Equation<QueryPolicy>::~Equation()
498 {
499 	free(fAttribute);
500 	free(fString);
501 }
502 
503 
504 template<typename QueryPolicy>
505 status_t
506 Equation<QueryPolicy>::InitCheck()
507 {
508 	if (fAttribute == NULL || fString == NULL
509 		|| Term<QueryPolicy>::fOp == OP_NONE) {
510 		return B_BAD_VALUE;
511 	}
512 
513 	return B_OK;
514 }
515 
516 
517 template<typename QueryPolicy>
518 status_t
519 Equation<QueryPolicy>::ParseQuotedString(const char** _start, const char** _end)
520 {
521 	const char* start = *_start;
522 	const char quote = *start++;
523 	const char* end = start;
524 
525 	for (; *end && *end != quote; end++) {
526 		if (*end == '\\')
527 			end++;
528 	}
529 	if (*end == '\0')
530 		return B_BAD_VALUE;
531 
532 	*_start = start;
533 	*_end = end - 1;
534 
535 	return B_OK;
536 }
537 
538 
539 template<typename QueryPolicy>
540 char*
541 Equation<QueryPolicy>::CopyString(const char* start, const char* end)
542 {
543 	// end points to the last character of the string - and the length
544 	// also has to include the null-termination
545 	int32 length = end + 2 - start;
546 	// just to make sure; since that's the max. attribute name length and
547 	// the max. string in an index, it make sense to have it that way
548 	if (length > QueryPolicy::kMaxFileNameLength || length <= 0)
549 		return NULL;
550 
551 	char* copy = (char*)malloc(length);
552 	if (copy == NULL)
553 		return NULL;
554 
555 	// Filter out remaining escaping slashes
556 	for (int32 i = 0; i < length; i++) {
557 		char c = start++[0];
558 		if (c == '\\' && i < length) {
559 			length--;
560 			i--;
561 			continue;
562 		}
563 		copy[i] = c;
564 	}
565 	copy[length - 1] = '\0';
566 
567 	return copy;
568 }
569 
570 
571 template<typename QueryPolicy>
572 bool
573 Equation<QueryPolicy>::_IsEquationChar(char c) const
574 {
575 	return c == '=' || c == '<' || c == '>' || c == '!';
576 }
577 
578 
579 template<typename QueryPolicy>
580 bool
581 Equation<QueryPolicy>::_IsOperatorChar(char c) const
582 {
583 	return c == '&' || c == '|';
584 }
585 
586 
587 template<typename QueryPolicy>
588 status_t
589 Equation<QueryPolicy>::ConvertValue(type_code type, uint32 size)
590 {
591 	// Perform type coercion up-front, so we don't re-convert every time.
592 	if (type == B_MIME_STRING_TYPE)
593 		type = B_STRING_TYPE;
594 	else if (type == B_TIME_TYPE)
595 		type = (size == 4) ? B_INT32_TYPE : B_INT64_TYPE;
596 
597 	// Has the type already been converted?
598 	if (type == fType)
599 		return B_OK;
600 
601 	char* string = fString;
602 
603 	switch (type) {
604 		case B_STRING_TYPE:
605 			strncpy(fValue.String, string, QueryPolicy::kMaxFileNameLength);
606 			fValue.String[QueryPolicy::kMaxFileNameLength - 1] = '\0';
607 			fSize = strlen(fValue.String);
608 			break;
609 		case B_INT32_TYPE:
610 			fValue.Int32 = strtol(string, &string, 0);
611 			fSize = sizeof(int32);
612 			break;
613 		case B_UINT32_TYPE:
614 			fValue.Int32 = strtoul(string, &string, 0);
615 			fSize = sizeof(uint32);
616 			break;
617 		case B_INT64_TYPE:
618 			fValue.Int64 = strtoll(string, &string, 0);
619 			fSize = sizeof(int64);
620 			break;
621 		case B_UINT64_TYPE:
622 			fValue.Uint64 = strtoull(string, &string, 0);
623 			fSize = sizeof(uint64);
624 			break;
625 		case B_FLOAT_TYPE:
626 			fValue.Float = strtod(string, &string);
627 			fSize = sizeof(float);
628 			break;
629 		case B_DOUBLE_TYPE:
630 			fValue.Double = strtod(string, &string);
631 			fSize = sizeof(double);
632 			break;
633 		default:
634 			QUERY_INFORM("query attribute '%s': unsupported value conversion to 0x%x requested!\n",
635 				fAttribute, (int)type);
636 			return B_BAD_TYPE;
637 	}
638 
639 	fType = type;
640 
641 	// patterns are only allowed for string types
642 	if (fType != B_STRING_TYPE && fIsPattern)
643 		fIsPattern = false;
644 
645 	return B_OK;
646 }
647 
648 
649 /*!	Returns true when the key matches the equation. You have to
650 	call ConvertValue() before this one.
651 */
652 template<typename QueryPolicy>
653 bool
654 Equation<QueryPolicy>::CompareTo(const uint8* value, size_t size)
655 {
656 	int32 compare;
657 
658 	// fIsPattern is only true if it's a string type, and fOp OP_EQUAL, or
659 	// OP_UNEQUAL
660 	if (fIsPattern) {
661 		// we have already validated the pattern, so we don't check for failing
662 		// here - if something is broken, and matchString() returns an error,
663 		// we just don't match
664 		compare = matchString(fValue.String, (const char*)value) == MATCH_OK ? 0 : 1;
665 	} else
666 		compare = compareKeys(fType, value, size, Value(), fSize);
667 
668 	switch (Term<QueryPolicy>::fOp) {
669 		case OP_EQUAL:
670 			return compare == 0;
671 		case OP_UNEQUAL:
672 			return compare != 0;
673 		case OP_LESS_THAN:
674 			return compare < 0;
675 		case OP_LESS_THAN_OR_EQUAL:
676 			return compare <= 0;
677 		case OP_GREATER_THAN:
678 			return compare > 0;
679 		case OP_GREATER_THAN_OR_EQUAL:
680 			return compare >= 0;
681 	}
682 	QUERY_FATAL("Unknown/Unsupported operation: %d\n", Term<QueryPolicy>::fOp);
683 	return false;
684 }
685 
686 
687 template<typename QueryPolicy>
688 void
689 Equation<QueryPolicy>::Complement()
690 {
691 	QUERY_D(if (Term<QueryPolicy>::fOp <= OP_EQUATION || Term<QueryPolicy>::fOp > OP_LESS_THAN_OR_EQUAL) {
692 		QUERY_FATAL("op out of range!\n");
693 		return;
694 	});
695 
696 	int8 complementOp[] = {OP_UNEQUAL, OP_EQUAL, OP_LESS_THAN_OR_EQUAL,
697 			OP_GREATER_THAN_OR_EQUAL, OP_LESS_THAN, OP_GREATER_THAN};
698 	Term<QueryPolicy>::fOp = complementOp[Term<QueryPolicy>::fOp - OP_EQUAL];
699 }
700 
701 
702 /*!	Matches the node's attribute value with the equation.
703 	Returns MATCH_OK if it matches, NO_MATCH if not, < 0 if something went
704 	wrong.
705 */
706 template<typename QueryPolicy>
707 status_t
708 Equation<QueryPolicy>::Match(Entry* entry, Node* node,
709 	const char* attributeName, int32 type, const uint8* key, size_t size)
710 {
711 	// get a pointer to the attribute in question
712 	NodeHolder nodeHolder;
713 	union value<QueryPolicy> value;
714 	uint8* buffer = (uint8*)&value;
715 	const size_t bufferSize = sizeof(value);
716 
717 	// first, check if we are matching for a live query and use that value
718 	if (attributeName != NULL && !strcmp(fAttribute, attributeName)) {
719 		if (key == NULL)
720 			return NO_MATCH;
721 		buffer = const_cast<uint8*>(key);
722 	} else if (!strcmp(fAttribute, "name")) {
723 		// if not, check for "fake" attributes ("name", "size", "last_modified")
724 		if (entry == NULL)
725 			return B_ERROR;
726 		buffer = (uint8*)QueryPolicy::EntryGetNameNoCopy(nodeHolder, entry);
727 		if (buffer == NULL)
728 			return B_ERROR;
729 
730 		type = B_STRING_TYPE;
731 		size = strlen((const char*)buffer);
732 	} else if (!strcmp(fAttribute, "size")) {
733 		value.Int64 = QueryPolicy::NodeGetSize(node);
734 		type = B_INT64_TYPE;
735 	} else if (!strcmp(fAttribute, "last_modified")) {
736 		value.Int64 = QueryPolicy::NodeGetLastModifiedTime(node);
737 		type = B_INT64_TYPE;
738 	} else {
739 		// then for attributes
740 		size = bufferSize;
741 		if (QueryPolicy::NodeGetAttribute(nodeHolder, node,
742 				fAttribute, buffer, &size, &type) != B_OK) {
743 			return NO_MATCH;
744 		}
745 	}
746 
747 	// prepare own value for use, if it is possible to convert it
748 	status_t status = ConvertValue(type, size);
749 	if (status == B_OK)
750 		status = CompareTo(buffer, size) ? MATCH_OK : NO_MATCH;
751 
752 	QUERY_RETURN_ERROR(status);
753 }
754 
755 
756 template<typename QueryPolicy>
757 void
758 Equation<QueryPolicy>::CalculateScore(Index &index)
759 {
760 	// As always, these values could be tuned and refined.
761 	// And the code could also need some real world testing :-)
762 
763 	// do we have to operate on a "foreign" index?
764 	if (QueryPolicy::IndexSetTo(index, fAttribute) < B_OK) {
765 		fScore = INT32_MAX;
766 		return;
767 	}
768 
769 	fScore = QueryPolicy::IndexGetSize(index);
770 
771 	if (Term<QueryPolicy>::fOp == OP_UNEQUAL) {
772 		// we'll need to scan the whole index
773 		return;
774 	}
775 
776 	// if we have a pattern, how much does it help our search?
777 	if (fIsPattern) {
778 		const int32 firstSymbolIndex = getFirstPatternSymbol(fString);
779 
780 		// Guess how much of the index we will be able to skip.
781 		const int32 divisor = (firstSymbolIndex > 3) ? 4 : (firstSymbolIndex + 1);
782 		fScore /= divisor;
783 	} else {
784 		// Score by operator
785 		if (Term<QueryPolicy>::fOp == OP_EQUAL) {
786 			// higher than most patterns
787 			fScore /= (fSize > 8) ? 8 : fSize;
788 		} else {
789 			// better than nothing, anyway
790 			fScore /= 2;
791 		}
792 	}
793 }
794 
795 
796 template<typename QueryPolicy>
797 status_t
798 Equation<QueryPolicy>::PrepareQuery(Context* /*context*/, Index& index,
799 	IndexIterator** iterator, bool queryNonIndexed)
800 {
801 	status_t status = QueryPolicy::IndexSetTo(index, fAttribute);
802 
803 	// if we should query attributes without an index, we can just proceed here
804 	if (status != B_OK && !queryNonIndexed)
805 		return B_ENTRY_NOT_FOUND;
806 
807 	type_code type;
808 
809 	// Special case for OP_UNEQUAL - it will always operate through the whole
810 	// index but we need the call to the original index to get the correct type
811 	if (status != B_OK || Term<QueryPolicy>::fOp == OP_UNEQUAL) {
812 		// Try to get an index that holds all files (name)
813 		// Also sets the default type for all attributes without index
814 		// to string.
815 		type = status < B_OK ? B_STRING_TYPE : QueryPolicy::IndexGetType(index);
816 
817 		if (QueryPolicy::IndexSetTo(index, "name") != B_OK)
818 			return B_ENTRY_NOT_FOUND;
819 
820 		fHasIndex = false;
821 	} else {
822 		fHasIndex = true;
823 		type = QueryPolicy::IndexGetType(index);
824 	}
825 
826 	int32 keySize = QueryPolicy::IndexGetKeySize(index);
827 	if (ConvertValue(type, keySize) < B_OK)
828 		return B_BAD_VALUE;
829 
830 	*iterator = QueryPolicy::IndexCreateIterator(index);
831 	if (*iterator == NULL)
832 		return B_NO_MEMORY;
833 
834 	if ((Term<QueryPolicy>::fOp == OP_EQUAL
835 			|| Term<QueryPolicy>::fOp == OP_GREATER_THAN
836 			|| Term<QueryPolicy>::fOp == OP_GREATER_THAN_OR_EQUAL || fIsPattern)
837 		&& fHasIndex) {
838 		// set iterator to the exact position
839 
840 		// At this point, fIsPattern is only true if it's a string type, and fOp
841 		// is either OP_EQUAL or OP_UNEQUAL
842 		if (fIsPattern) {
843 			// let's see if we can use the beginning of the key for positioning
844 			// the iterator and adjust the key size; if not, just leave the
845 			// iterator at the start and return success
846 			keySize = getFirstPatternSymbol(fString);
847 			if (keySize <= 0)
848 				return B_OK;
849 		}
850 
851 		if (keySize == 0) {
852 			// B_STRING_TYPE doesn't have a fixed length, so it was set
853 			// to 0 before - we compute the correct value here
854 			if (fType == B_STRING_TYPE) {
855 				keySize = strlen(fValue.String);
856 
857 				// The empty string is a special case - we normally don't check
858 				// for the trailing null byte, in the case for the empty string
859 				// we do it explicitly, because there can't be keys in the
860 				// B+tree with a length of zero
861 				if (keySize == 0)
862 					keySize = 1;
863 			} else
864 				QUERY_RETURN_ERROR(B_ENTRY_NOT_FOUND);
865 		}
866 
867 		status = QueryPolicy::IndexIteratorFind(*iterator, Value(), keySize);
868 		if (Term<QueryPolicy>::fOp == OP_EQUAL && !fIsPattern)
869 			return status;
870 		else if (status == B_ENTRY_NOT_FOUND
871 			&& (fIsPattern || Term<QueryPolicy>::fOp == OP_GREATER_THAN
872 				|| Term<QueryPolicy>::fOp == OP_GREATER_THAN_OR_EQUAL))
873 			return B_OK;
874 
875 		QUERY_RETURN_ERROR(status);
876 	}
877 
878 	return B_OK;
879 }
880 
881 
882 template<typename QueryPolicy>
883 status_t
884 Equation<QueryPolicy>::GetNextMatching(Context* context,
885 	IndexIterator* iterator, struct dirent* dirent, size_t bufferSize)
886 {
887 	while (true) {
888 		NodeHolder nodeHolder;
889 		union value<QueryPolicy> indexValue;
890 		size_t keyLength;
891 		size_t duplicate = 0;
892 
893 		status_t status = QueryPolicy::IndexIteratorFetchNextEntry(iterator,
894 			&indexValue, &keyLength, (size_t)sizeof(indexValue), &duplicate);
895 		if (status != B_OK)
896 			return status;
897 
898 		// only compare against the index entry when this is the correct
899 		// index for the equation
900 		if (fHasIndex && duplicate < 2 && !CompareTo((uint8*)&indexValue, keyLength)) {
901 			// They aren't equal? Let the operation decide what to do. Since
902 			// we always start at the beginning of the index (or the correct
903 			// position), only some needs to be stopped if the entry doesn't
904 			// fit.
905 			if (Term<QueryPolicy>::fOp == OP_LESS_THAN
906 				|| Term<QueryPolicy>::fOp == OP_LESS_THAN_OR_EQUAL
907 				|| (Term<QueryPolicy>::fOp == OP_EQUAL && !fIsPattern))
908 				return B_ENTRY_NOT_FOUND;
909 
910 			if (duplicate > 0)
911 				QueryPolicy::IndexIteratorSkipDuplicates(iterator);
912 			continue;
913 		}
914 
915 		Entry* entry = NULL;
916 		status = QueryPolicy::IndexIteratorGetEntry(context, iterator,
917 			nodeHolder, &entry);
918 		if (status != B_OK) {
919 			// try with next
920 			continue;
921 		}
922 
923 		// TODO: check user permissions here - but which one?!
924 		// we could filter out all those where we don't have
925 		// read access... (we should check for every parent
926 		// directory if the X_OK is allowed)
927 		// Although it's quite expensive to open all parents,
928 		// it's likely that the application that runs the
929 		// query will do something similar (and we don't have
930 		// to do it for root, either).
931 
932 		// go up in the tree until a &&-operator is found, and check if the
933 		// node matches with the rest of the expression - we don't have to
934 		// check ||-operators for that
935 		Term<QueryPolicy>* term = this;
936 		status = MATCH_OK;
937 
938 		if (!fHasIndex)
939 			status = Match(entry, QueryPolicy::EntryGetNode(entry));
940 
941 		while (term != NULL && status == MATCH_OK) {
942 			Operator<QueryPolicy>* parent
943 				= (Operator<QueryPolicy>*)term->Parent();
944 			if (parent == NULL)
945 				break;
946 
947 			if (parent->Op() == OP_AND) {
948 				// choose the other child of the parent
949 				Term<QueryPolicy>* other = parent->Right();
950 				if (other == term)
951 					other = parent->Left();
952 
953 				if (other == NULL) {
954 					QUERY_FATAL("&&-operator has only one child... "
955 						"(parent = %p)\n", parent);
956 					break;
957 				}
958 				status = other->Match(entry, QueryPolicy::EntryGetNode(entry));
959 				if (status < 0) {
960 					QUERY_REPORT_ERROR(status);
961 					status = NO_MATCH;
962 				}
963 			}
964 			term = (Term<QueryPolicy>*)parent;
965 		}
966 
967 		if (status == MATCH_OK) {
968 			ssize_t nameLength = QueryPolicy::EntryGetName(entry,
969 				dirent->d_name,
970 				(const char*)dirent + bufferSize - dirent->d_name);
971 			if (nameLength < 0) {
972 				// Invalid or unknown name.
973 				nameLength = 0;
974 			}
975 
976 			dirent->d_dev = QueryPolicy::ContextGetVolumeID(context);
977 			dirent->d_ino = QueryPolicy::EntryGetNodeID(entry);
978 			dirent->d_pdev = dirent->d_dev;
979 			dirent->d_pino = QueryPolicy::EntryGetParentID(entry);
980 			dirent->d_reclen = offsetof(struct dirent, d_name) + nameLength;
981 		}
982 
983 		if (status == MATCH_OK)
984 			return B_OK;
985 	}
986 	QUERY_RETURN_ERROR(B_ERROR);
987 }
988 
989 
990 template<typename QueryPolicy>
991 bool
992 Equation<QueryPolicy>::NeedsEntry()
993 {
994 	return strcmp(fAttribute, "name") == 0;
995 }
996 
997 
998 //	#pragma mark -
999 
1000 
1001 template<typename QueryPolicy>
1002 Operator<QueryPolicy>::Operator(Term<QueryPolicy>* left, int8 op,
1003 	Term<QueryPolicy>* right)
1004 	:
1005 	Term<QueryPolicy>(op),
1006 	fLeft(left),
1007 	fRight(right)
1008 {
1009 	if (left)
1010 		left->SetParent(this);
1011 	if (right)
1012 		right->SetParent(this);
1013 }
1014 
1015 
1016 template<typename QueryPolicy>
1017 Operator<QueryPolicy>::~Operator()
1018 {
1019 	delete fLeft;
1020 	delete fRight;
1021 }
1022 
1023 
1024 template<typename QueryPolicy>
1025 status_t
1026 Operator<QueryPolicy>::Match(Entry* entry, Node* node, const char* attribute,
1027 	int32 type, const uint8* key, size_t size)
1028 {
1029 	if (Term<QueryPolicy>::fOp == OP_AND) {
1030 		status_t status = fLeft->Match(entry, node, attribute, type, key,
1031 			size);
1032 		if (status != MATCH_OK)
1033 			return status;
1034 
1035 		return fRight->Match(entry, node, attribute, type, key, size);
1036 	} else {
1037 		// choose the term with the better score for OP_OR
1038 		Term<QueryPolicy>* first;
1039 		Term<QueryPolicy>* second;
1040 		if (fRight->Score() < fLeft->Score()) {
1041 			first = fLeft;
1042 			second = fRight;
1043 		} else {
1044 			first = fRight;
1045 			second = fLeft;
1046 		}
1047 
1048 		status_t status = first->Match(entry, node, attribute, type, key,
1049 			size);
1050 		if (status != NO_MATCH)
1051 			return status;
1052 
1053 		return second->Match(entry, node, attribute, type, key, size);
1054 	}
1055 }
1056 
1057 
1058 template<typename QueryPolicy>
1059 void
1060 Operator<QueryPolicy>::Complement()
1061 {
1062 	if (Term<QueryPolicy>::fOp == OP_AND)
1063 		Term<QueryPolicy>::fOp = OP_OR;
1064 	else
1065 		Term<QueryPolicy>::fOp = OP_AND;
1066 
1067 	fLeft->Complement();
1068 	fRight->Complement();
1069 }
1070 
1071 
1072 template<typename QueryPolicy>
1073 void
1074 Operator<QueryPolicy>::CalculateScore(Index &index)
1075 {
1076 	fLeft->CalculateScore(index);
1077 	fRight->CalculateScore(index);
1078 }
1079 
1080 
1081 template<typename QueryPolicy>
1082 int32
1083 Operator<QueryPolicy>::Score() const
1084 {
1085 	if (Term<QueryPolicy>::fOp == OP_AND) {
1086 		// return the one with the better score
1087 		if (fRight->Score() < fLeft->Score())
1088 			return fRight->Score();
1089 		return fLeft->Score();
1090 	}
1091 
1092 	// for OP_OR, be honest, and return the one with the worse score
1093 	if (fRight->Score() > fLeft->Score())
1094 		return fRight->Score();
1095 	return fLeft->Score();
1096 }
1097 
1098 
1099 template<typename QueryPolicy>
1100 status_t
1101 Operator<QueryPolicy>::InitCheck()
1102 {
1103 	if ((Term<QueryPolicy>::fOp != OP_AND && Term<QueryPolicy>::fOp != OP_OR)
1104 		|| fLeft == NULL || fLeft->InitCheck() < B_OK
1105 		|| fRight == NULL || fRight->InitCheck() < B_OK)
1106 		return B_ERROR;
1107 
1108 	return B_OK;
1109 }
1110 
1111 
1112 template<typename QueryPolicy>
1113 bool
1114 Operator<QueryPolicy>::NeedsEntry()
1115 {
1116 	return ((fLeft && fLeft->NeedsEntry()) || (fRight && fRight->NeedsEntry()));
1117 }
1118 
1119 
1120 //	#pragma mark -
1121 
1122 #ifdef DEBUG_QUERY
1123 
1124 template<typename QueryPolicy>
1125 void
1126 Operator<QueryPolicy>::PrintToStream()
1127 {
1128 	QUERY_D(__out("( "));
1129 	if (fLeft != NULL)
1130 		fLeft->PrintToStream();
1131 
1132 	const char* op;
1133 	switch (Term<QueryPolicy>::fOp) {
1134 		case OP_OR: op = "OR"; break;
1135 		case OP_AND: op = "AND"; break;
1136 		default: op = "?"; break;
1137 	}
1138 	QUERY_D(__out(" %s ", op));
1139 
1140 	if (fRight != NULL)
1141 		fRight->PrintToStream();
1142 
1143 	QUERY_D(__out(" )"));
1144 }
1145 
1146 
1147 template<typename QueryPolicy>
1148 void
1149 Equation<QueryPolicy>::PrintToStream()
1150 {
1151 	const char* symbol = "???";
1152 	switch (Term<QueryPolicy>::fOp) {
1153 		case OP_EQUAL: symbol = "=="; break;
1154 		case OP_UNEQUAL: symbol = "!="; break;
1155 		case OP_GREATER_THAN: symbol = ">"; break;
1156 		case OP_GREATER_THAN_OR_EQUAL: symbol = ">="; break;
1157 		case OP_LESS_THAN: symbol = "<"; break;
1158 		case OP_LESS_THAN_OR_EQUAL: symbol = "<="; break;
1159 	}
1160 	QUERY_D(__out("[\"%s\" %s \"%s\"]", fAttribute, symbol, fString));
1161 }
1162 
1163 #endif	// DEBUG_QUERY
1164 
1165 //	#pragma mark -
1166 
1167 
1168 template<typename QueryPolicy>
1169 Expression<QueryPolicy>::Expression()
1170 	:
1171 	fTerm(NULL)
1172 {
1173 }
1174 
1175 
1176 template<typename QueryPolicy>
1177 status_t
1178 Expression<QueryPolicy>::Init(const char* expr, const char** position)
1179 {
1180 	if (expr == NULL)
1181 		return B_BAD_VALUE;
1182 	if (fTerm != NULL)
1183 		return EALREADY;
1184 
1185 	status_t status = B_OK;
1186 	int32 equations = 0;
1187 	const int32 kMaxEquations = 32;
1188 
1189 	struct ExpressionNode {
1190 		Term<QueryPolicy>* term = NULL;
1191 		bool negated = false;
1192 		ops op = OP_NONE;
1193 	};
1194 	Stack<Stack<ExpressionNode>*> exprsTree;
1195 	Stack<ExpressionNode>* currentExpr = NULL;
1196 	ExpressionNode* current = NULL;
1197 	while (expr != NULL) {
1198 		skipWhitespace(&expr);
1199 
1200 		if (currentExpr == NULL) {
1201 			 currentExpr = new(std::nothrow) Stack<ExpressionNode>;
1202 			 if (currentExpr == NULL) {
1203 				 status = B_NO_MEMORY;
1204 				 break;
1205 			 }
1206 		}
1207 
1208 		const char c = *expr;
1209 		bool complete = false;
1210 
1211 		if (c == ')' || c == '\0') {
1212 			if (currentExpr->IsEmpty())
1213 				break; // Illegal empty expression.
1214 
1215 			complete = true;
1216 		}
1217 
1218 		if (current == NULL && !complete) {
1219 			currentExpr->Push(ExpressionNode());
1220 			current = currentExpr->Array() + (currentExpr->CountItems() - 1);
1221 		}
1222 
1223 		if (c == '(') {
1224 			exprsTree.Push(currentExpr);
1225 			currentExpr = NULL;
1226 			current = NULL;
1227 			expr++;
1228 		} else if (c == '!') {
1229 			skipWhitespace(&expr, 1);
1230 			if (*expr != '(')
1231 				break; // Not allowed.
1232 			current->negated = true;
1233 		} else if (c == '|' || c == '&') {
1234 			if (current->term == NULL)
1235 				break; // Nothing to operate on.
1236 
1237 			ops op = OP_NONE;
1238 			if (IsOperator(&expr, '|'))
1239 				op = OP_OR;
1240 			else if (IsOperator(&expr, '&'))
1241 				op = OP_AND;
1242 			else
1243 				break; // Illegal operator.
1244 
1245 			current->op = op;
1246 			current = NULL;
1247 		} else if (!complete) {
1248 			if (current->term != NULL)
1249 				break; // There already is a term.
1250 			if ((equations + 1) > kMaxEquations) {
1251 				status = E2BIG;
1252 				break;
1253 			}
1254 
1255 			Equation<QueryPolicy>* equation
1256 				= new(std::nothrow) Equation<QueryPolicy>(&expr);
1257 			if (equation == NULL) {
1258 				status = B_NO_MEMORY;
1259 				break;
1260 			}
1261 			if (equation == NULL || equation->InitCheck() != B_OK) {
1262 				status = equation->InitCheck();
1263 				delete equation;
1264 				break;
1265 			}
1266 
1267 			current->term = equation;
1268 			equations++;
1269 		}
1270 		if (!complete)
1271 			continue;
1272 
1273 		if (currentExpr->CountItems() == 1) {
1274 			if (current == NULL)
1275 				break; // Probably an anomalous operator.
1276 		}
1277 
1278 		// First pass: negation.
1279 		for (int32 i = 0; i < currentExpr->CountItems(); i++) {
1280 			current = currentExpr->Array() + i;
1281 			// If the term is negated, we just complement the tree, to get
1282 			// rid of the not, a.k.a. DeMorgan's Law.
1283 			if (current->negated) {
1284 				current->term->Complement();
1285 				current->negated = false;
1286 			}
1287 		}
1288 		// Second & third passes: && and ||.
1289 		int32 nodes = currentExpr->CountItems();
1290 		for (ops op = OP_AND; op <= OP_OR; op = (ops)(op + 1)) {
1291 			for (int32 i = 0; i < (currentExpr->CountItems() - 1); ) {
1292 				ExpressionNode* left = currentExpr->Array() + i;
1293 				if (left->op != op) {
1294 					i++;
1295 					continue;
1296 				}
1297 
1298 				// Find the right-hand expression (may have to jump over now-unused nodes.)
1299 				ExpressionNode* right = NULL;
1300 				for (int32 j = i + 1; j < currentExpr->CountItems(); j++) {
1301 					current = currentExpr->Array() + j;
1302 					if (current->term == NULL)
1303 						continue;
1304 
1305 					right = current;
1306 					break;
1307 				}
1308 				if (right == NULL)
1309 					break; // Invalid expression, somehow.
1310 
1311 				Term<QueryPolicy>* newTerm = new(std::nothrow) Operator<QueryPolicy>(
1312 					left->term, left->op, right->term);
1313 				if (newTerm == NULL) {
1314 					status = B_NO_MEMORY;
1315 					break;
1316 				}
1317 
1318 				left->term = newTerm;
1319 				left->op = right->op;
1320 				right->op = OP_NONE;
1321 				right->term = NULL;
1322 				nodes--;
1323 			}
1324 		}
1325 
1326 		// At this point we should have only one node left.
1327 		if (nodes != 1)
1328 			break;
1329 
1330 		current = currentExpr->Array();
1331 		Term<QueryPolicy>* term = current->term;
1332 
1333 		delete currentExpr;
1334 		currentExpr = NULL;
1335 		if (exprsTree.Pop(&currentExpr)) {
1336 			current = currentExpr->Array() + (currentExpr->CountItems() - 1);
1337 			if (current->term != NULL)
1338 				break; // There already is a term.
1339 			current->term = term;
1340 		} else {
1341 			if (c != '\0')
1342 				break; // Unexpected end of expression.
1343 
1344 			fTerm = term;
1345 			break;
1346 		}
1347 
1348 		expr++;
1349 	}
1350 
1351 	if (position != NULL)
1352 		*position = expr;
1353 
1354 	do {
1355 		if (currentExpr == NULL)
1356 			continue;
1357 
1358 		ExpressionNode item;
1359 		while (currentExpr->Pop(&item))
1360 			delete item.term;
1361 		delete currentExpr;
1362 	} while (exprsTree.Pop(&currentExpr));
1363 
1364 	if (fTerm == NULL && status == B_OK)
1365 		return B_BAD_VALUE;
1366 
1367 	QUERY_D(if (fTerm != NULL) {
1368 		fTerm->PrintToStream();
1369 		QUERY_D(__out("\n"));
1370 		if (*expr != '\0')
1371 			PRINT(("Unexpected end of string: \"%s\"!\n", expr));
1372 	});
1373 
1374 	return status;
1375 }
1376 
1377 
1378 template<typename QueryPolicy>
1379 Expression<QueryPolicy>::~Expression()
1380 {
1381 	delete fTerm;
1382 }
1383 
1384 
1385 template<typename QueryPolicy>
1386 bool
1387 Expression<QueryPolicy>::IsOperator(const char** expr, char op)
1388 {
1389 	const char* string = *expr;
1390 
1391 	if (*string == op && *(string + 1) == op) {
1392 		*expr += 2;
1393 		return true;
1394 	}
1395 	return false;
1396 }
1397 
1398 
1399 //	#pragma mark -
1400 
1401 
1402 template<typename QueryPolicy>
1403 Query<QueryPolicy>::Query(Context* context, Expression<QueryPolicy>* expression,
1404 	uint32 flags, port_id port, uint32 token)
1405 	:
1406 	fContext(context),
1407 	fExpression(expression),
1408 	fCurrent(NULL),
1409 	fIterator(NULL),
1410 	fIndex(context),
1411 	fFlags(flags),
1412 	fPort(port),
1413 	fToken(token),
1414 	fNeedsEntry(false)
1415 {
1416 	// If the expression has a valid root pointer, the whole tree has
1417 	// already passed the sanity check, so that we don't have to check
1418 	// every pointer
1419 	if (context == NULL || expression == NULL || expression->Root() == NULL)
1420 		return;
1421 
1422 	// create index on the stack and delete it afterwards
1423 	fExpression->Root()->CalculateScore(fIndex);
1424 	QueryPolicy::IndexUnset(fIndex);
1425 
1426 	fNeedsEntry = fExpression->Root()->NeedsEntry();
1427 
1428 	Rewind();
1429 }
1430 
1431 
1432 template<typename QueryPolicy>
1433 Query<QueryPolicy>::~Query()
1434 {
1435 	delete fExpression;
1436 }
1437 
1438 
1439 template<typename QueryPolicy>
1440 /*static*/ status_t
1441 Query<QueryPolicy>::Create(Context* context, const char* queryString,
1442 	uint32 flags, port_id port, uint32 token, Query<QueryPolicy>*& _query)
1443 {
1444 	Expression<QueryPolicy>* expression
1445 		= new(std::nothrow) Expression<QueryPolicy>;
1446 	if (expression == NULL)
1447 		QUERY_RETURN_ERROR(B_NO_MEMORY);
1448 
1449 	const char* position = NULL;
1450 	status_t status = expression->Init(queryString, &position);
1451 	if (status != B_OK) {
1452 		QUERY_INFORM("Could not parse query \"%s\", stopped at: \"%s\"\n",
1453 			queryString, position);
1454 
1455 		delete expression;
1456 		QUERY_RETURN_ERROR(status);
1457 	}
1458 
1459 	Query<QueryPolicy>* query = new(std::nothrow) Query<QueryPolicy>(context,
1460 		expression, flags, port, token);
1461 	if (query == NULL) {
1462 		delete expression;
1463 		QUERY_RETURN_ERROR(B_NO_MEMORY);
1464 	}
1465 
1466 	_query = query;
1467 	return B_OK;
1468 }
1469 
1470 
1471 template<typename QueryPolicy>
1472 status_t
1473 Query<QueryPolicy>::Rewind()
1474 {
1475 	// free previous stuff
1476 
1477 	fStack.MakeEmpty();
1478 
1479 	QueryPolicy::IndexIteratorDelete(fIterator);
1480 	fIterator = NULL;
1481 	fCurrent = NULL;
1482 
1483 	// put the whole expression on the stack
1484 
1485 	Stack<Term<QueryPolicy>*> stack;
1486 	stack.Push(fExpression->Root());
1487 
1488 	Term<QueryPolicy>* term;
1489 	while (stack.Pop(&term)) {
1490 		if (term->Op() < OP_EQUATION) {
1491 			Operator<QueryPolicy>* op = (Operator<QueryPolicy>*)term;
1492 
1493 			if (op->Op() == OP_OR) {
1494 				stack.Push(op->Left());
1495 				stack.Push(op->Right());
1496 			} else {
1497 				// For OP_AND, we can use the scoring system to decide which
1498 				// path to add
1499 				if (op->Right()->Score() < op->Left()->Score())
1500 					stack.Push(op->Right());
1501 				else
1502 					stack.Push(op->Left());
1503 			}
1504 		} else if (term->Op() == OP_EQUATION
1505 				|| fStack.Push((Equation<QueryPolicy>*)term) != B_OK)
1506 			QUERY_FATAL("Unknown term on stack or stack error\n");
1507 	}
1508 
1509 	return B_OK;
1510 }
1511 
1512 
1513 template<typename QueryPolicy>
1514 status_t
1515 Query<QueryPolicy>::GetNextEntry(struct dirent* dirent, size_t size)
1516 {
1517 	if (fIterator != NULL)
1518 		QueryPolicy::IndexIteratorResume(fIterator);
1519 
1520 	status_t error = _GetNextEntry(dirent, size);
1521 
1522 	if (fIterator != NULL)
1523 		QueryPolicy::IndexIteratorSuspend(fIterator);
1524 
1525 	return error;
1526 }
1527 
1528 
1529 template<typename QueryPolicy>
1530 void
1531 Query<QueryPolicy>::LiveUpdate(Entry* entry, Node* node, const char* attribute,
1532 	int32 type, const uint8* oldKey, size_t oldLength, const uint8* newKey,
1533 	size_t newLength)
1534 {
1535 	if (fPort < 0 || fExpression == NULL || attribute == NULL)
1536 		return;
1537 
1538 	// TODO: check if the attribute is part of the query at all...
1539 
1540 	// If no entry has been supplied, but the we need one for the evaluation
1541 	// (i.e. the "name" attribute is used), we invoke ourselves for all entries
1542 	// referring to the given node.
1543 	if (entry == NULL && fNeedsEntry) {
1544 		entry = QueryPolicy::NodeGetFirstReferrer(node);
1545 		while (entry) {
1546 			LiveUpdate(entry, node, attribute, type, oldKey, oldLength, newKey,
1547 				newLength);
1548 			entry = QueryPolicy::NodeGetNextReferrer(node, entry);
1549 		}
1550 		return;
1551 	}
1552 
1553 	status_t oldStatus = fExpression->Root()->Match(entry, node, attribute,
1554 		type, oldKey, oldLength);
1555 	status_t newStatus = fExpression->Root()->Match(entry, node, attribute,
1556 		type, newKey, newLength);
1557 
1558 	bool entryCreated = false;
1559 	bool stillInQuery = false;
1560 
1561 	if (oldStatus != MATCH_OK) {
1562 		if (newStatus != MATCH_OK) {
1563 			// nothing has changed
1564 			return;
1565 		}
1566 		entryCreated = true;
1567 	} else if (newStatus != MATCH_OK) {
1568 		// entry got removed
1569 		entryCreated = false;
1570 	} else if ((fFlags & B_ATTR_CHANGE_NOTIFICATION) != 0) {
1571 		// The entry stays in the query
1572 		stillInQuery = true;
1573 	} else
1574 		return;
1575 
1576 	// notify query listeners
1577 	status_t (*notify)(port_id, int32, dev_t, ino_t, const char*, ino_t);
1578 
1579 	if (stillInQuery)
1580 		notify = notify_query_attr_changed;
1581 	else if (entryCreated)
1582 		notify = notify_query_entry_created;
1583 	else
1584 		notify = notify_query_entry_removed;
1585 
1586 	if (entry != NULL) {
1587 		_SendEntryNotification(entry, notify);
1588 	} else {
1589 		entry = QueryPolicy::NodeGetFirstReferrer(node);
1590 		while (entry) {
1591 			_SendEntryNotification(entry, notify);
1592 			entry = QueryPolicy::NodeGetNextReferrer(node, entry);
1593 		}
1594 	}
1595 }
1596 
1597 
1598 template<typename QueryPolicy>
1599 void
1600 Query<QueryPolicy>::LiveUpdateRenameMove(Entry* entry, Node* node,
1601 	ino_t oldDirectoryID, const char* oldName, size_t oldLength,
1602 	ino_t newDirectoryID, const char* newName, size_t newLength)
1603 {
1604 	if (fPort < 0 || fExpression == NULL)
1605 		return;
1606 
1607 	// TODO: check if the attribute is part of the query at all...
1608 
1609 	status_t oldStatus = fExpression->Root()->Match(entry, node, "name",
1610 		B_STRING_TYPE, (const uint8*)oldName, oldLength);
1611 	status_t newStatus = fExpression->Root()->Match(entry, node, "name",
1612 		B_STRING_TYPE, (const uint8*)newName, newLength);
1613 
1614 	if (oldStatus != MATCH_OK || oldStatus != newStatus)
1615 		return;
1616 
1617 	// The entry stays in the query, notify query listeners about the rename
1618 	// or move
1619 
1620 	// We send a notification for the given entry, if any, or otherwise for
1621 	// all entries referring to the node;
1622 	if (entry != NULL) {
1623 		_SendEntryNotification(entry, notify_query_entry_removed);
1624 		_SendEntryNotification(entry, notify_query_entry_created);
1625 	} else {
1626 		entry = QueryPolicy::NodeGetFirstReferrer(node);
1627 		while (entry) {
1628 			_SendEntryNotification(entry, notify_query_entry_removed);
1629 			_SendEntryNotification(entry, notify_query_entry_created);
1630 			entry = QueryPolicy::NodeGetNextReferrer(node, entry);
1631 		}
1632 	}
1633 }
1634 
1635 
1636 template<typename QueryPolicy>
1637 status_t
1638 Query<QueryPolicy>::_GetNextEntry(struct dirent* dirent, size_t size)
1639 {
1640 	// If we don't have an equation to use yet/anymore, get a new one
1641 	// from the stack
1642 	while (true) {
1643 		if (fIterator == NULL) {
1644 			if (!fStack.Pop(&fCurrent)
1645 				|| fCurrent == NULL)
1646 				return B_ENTRY_NOT_FOUND;
1647 
1648 			status_t status = fCurrent->PrepareQuery(fContext, fIndex,
1649 				&fIterator, fFlags & B_QUERY_NON_INDEXED);
1650 			if (status == B_ENTRY_NOT_FOUND) {
1651 				// try next equation
1652 				continue;
1653 			}
1654 
1655 			if (status != B_OK)
1656 				return status;
1657 		}
1658 		if (fCurrent == NULL)
1659 			QUERY_RETURN_ERROR(B_ERROR);
1660 
1661 		status_t status = fCurrent->GetNextMatching(fContext, fIterator, dirent,
1662 			size);
1663 		if (status != B_OK) {
1664 			QueryPolicy::IndexIteratorDelete(fIterator);
1665 			fIterator = NULL;
1666 			fCurrent = NULL;
1667 		} else {
1668 			// only return if we have another entry
1669 			return B_OK;
1670 		}
1671 	}
1672 }
1673 
1674 
1675 template<typename QueryPolicy>
1676 void
1677 Query<QueryPolicy>::_SendEntryNotification(Entry* entry,
1678 	status_t (*notify)(port_id, int32, dev_t, ino_t, const char*, ino_t))
1679 {
1680 	NodeHolder nodeHolder;
1681 	const char* name = QueryPolicy::EntryGetNameNoCopy(nodeHolder, entry);
1682 	if (name != NULL) {
1683 		notify(fPort, fToken, QueryPolicy::ContextGetVolumeID(fContext),
1684 			QueryPolicy::EntryGetParentID(entry), name,
1685 			QueryPolicy::EntryGetNodeID(entry));
1686 	}
1687 }
1688 
1689 
1690 }	// namespace QueryParser
1691 
1692 
1693 #endif	// _FILE_SYSTEMS_QUERY_PARSER_H
1694