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