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