diff options
Diffstat (limited to 'src')
| -rw-r--r-- | src/pugixml.cpp | 1183 | ||||
| -rw-r--r-- | src/pugixml.hpp | 20 |
2 files changed, 755 insertions, 448 deletions
diff --git a/src/pugixml.cpp b/src/pugixml.cpp index 415fb24..c57ddae 100644 --- a/src/pugixml.cpp +++ b/src/pugixml.cpp @@ -4711,46 +4711,208 @@ namespace pstd } } -namespace +// Allocator used for AST and evaluation stacks +namespace pugi { - using namespace pugi; + struct xpath_memory_block + { + xpath_memory_block* next; - char_t* duplicate_string(const char_t* string, size_t length) + char data[4096]; + }; + + class xpath_allocator { - char_t* result = static_cast<char_t*>(global_allocate((length + 1) * sizeof(char_t))); - if (!result) return 0; // $$ out of memory + xpath_memory_block* _root; + size_t _root_size; + + public: + static xpath_allocator* create() + { + void* memory = global_allocate(sizeof(xpath_allocator) + sizeof(xpath_memory_block)); + if (!memory) return 0; - memcpy(result, string, length * sizeof(char_t)); - result[length] = 0; + xpath_memory_block* root = reinterpret_cast<xpath_memory_block*>(static_cast<xpath_allocator*>(memory) + 1); + root->next = 0; - return result; - } + return new (memory) xpath_allocator(root); + } + + static void destroy(void* ptr) + { + if (!ptr) return; + + // free all allocated pages + xpath_allocator* alloc = static_cast<xpath_allocator*>(ptr); + + xpath_memory_block* cur = alloc->_root; + assert(cur); + + while (cur->next) + { + xpath_memory_block* next = cur->next; + + global_deallocate(cur); + + cur = next; + } + + // free allocator memory (with the first page) + global_deallocate(alloc); + } + + xpath_allocator(xpath_memory_block* root, size_t root_size = 0): _root(root), _root_size(root_size) + { + } + + void* allocate(size_t size) + { + const size_t block_capacity = sizeof(_root->data); + + // align size so that we're able to store pointers in subsequent blocks + size = (size + sizeof(void*) - 1) & ~(sizeof(void*) - 1); + + if (_root_size + size <= block_capacity) + { + void* buf = _root->data + _root_size; + _root_size += size; + return buf; + } + else + { + size_t block_data_size = (size > block_capacity) ? size : block_capacity; + size_t block_size = block_data_size + offsetof(xpath_memory_block, data); + + xpath_memory_block* block = static_cast<xpath_memory_block*>(global_allocate(block_size)); + if (!block) return 0; // $$ out of memory + + block->next = _root; + + _root = block; + _root_size = size; + + return block->data; + } + } + + void* reallocate(void* ptr, size_t old_size, size_t new_size) + { + // we can only reallocate the last object + assert(static_cast<char*>(ptr) + old_size == _root->data + _root_size); + + // adjust root size so that we have not allocated the object at all + _root_size -= old_size; + bool only_object = (_root_size == 0); + + // allocate a new version (this will obviously reuse the memory if possible) + void* result = allocate(new_size); + if (!result) return 0; // $$ out of memory + + // we have a new block + if (result != ptr) + { + // copy old data + assert(new_size > old_size); + memcpy(result, ptr, old_size); + + // free the previous page if it had no other objects + if (only_object) + { + assert(_root->data == result); + assert(_root->next); - char_t* duplicate_string(const char_t* string) + xpath_memory_block* next = _root->next->next; + + if (next) + { + // deallocate the whole page, unless it was the first one + global_deallocate(_root->next); + _root->next = next; + } + } + } + + return result; + } + + void revert(xpath_allocator& state) + { + // free all new pages + xpath_memory_block* cur = _root; + + while (cur != state._root) + { + xpath_memory_block* next = cur->next; + + global_deallocate(cur); + + cur = next; + } + + // restore state + _root = state._root; + _root_size = state._root_size; + } + }; + + struct xpath_allocator_capture { - return duplicate_string(string, strlength(string)); - } + xpath_allocator_capture(xpath_allocator* alloc): _target(alloc), _state(*alloc) + { + } + + ~xpath_allocator_capture() + { + _target->revert(_state); + } + + xpath_allocator* _target; + xpath_allocator _state; + }; + + struct xpath_stack + { + xpath_allocator* result; + xpath_allocator* temp; + }; +} + +// String class +namespace +{ + using namespace pugi; class xpath_string { const char_t* _buffer; bool _uses_heap; - public: - xpath_string(): _buffer(PUGIXML_TEXT("")), _uses_heap(false) + static char_t* duplicate_string(const char_t* string, size_t length, xpath_allocator* alloc) + { + char_t* result = static_cast<char_t*>(alloc->allocate((length + 1) * sizeof(char_t))); + if (!result) return 0; // $$ out of memory + + memcpy(result, string, length * sizeof(char_t)); + result[length] = 0; + + return result; + } + + static char_t* duplicate_string(const char_t* string, xpath_allocator* alloc) { + return duplicate_string(string, strlength(string), alloc); } - ~xpath_string() + public: + xpath_string(): _buffer(PUGIXML_TEXT("")), _uses_heap(false) { - if (_uses_heap) global_deallocate(const_cast<char_t*>(_buffer)); } - explicit xpath_string(const char_t* str) + explicit xpath_string(const char_t* str, xpath_allocator* alloc) { bool empty = (*str == 0); - _buffer = empty ? PUGIXML_TEXT("") : duplicate_string(str); + _buffer = empty ? PUGIXML_TEXT("") : duplicate_string(str, alloc); _uses_heap = !empty; } @@ -4758,37 +4920,17 @@ namespace { } - xpath_string(const char_t* begin, const char_t* end) + xpath_string(const char_t* begin, const char_t* end, xpath_allocator* alloc) { assert(begin <= end); bool empty = (begin == end); - _buffer = empty ? PUGIXML_TEXT("") : duplicate_string(begin, static_cast<size_t>(end - begin)); + _buffer = empty ? PUGIXML_TEXT("") : duplicate_string(begin, static_cast<size_t>(end - begin), alloc); _uses_heap = !empty; } - xpath_string(const xpath_string& o) - { - _buffer = o._uses_heap ? duplicate_string(o._buffer) : o._buffer; - _uses_heap = o._uses_heap; - } - - xpath_string& operator=(const xpath_string& o) - { - xpath_string temp(o); - swap(temp); - - return *this; - } - - void swap(xpath_string& o) - { - pstd::swap(_buffer, o._buffer); - pstd::swap(_uses_heap, o._uses_heap); - } - - void append(const xpath_string& o) + void append(const xpath_string& o, xpath_allocator* alloc) { // skip empty sources if (!*o._buffer) return; @@ -4806,8 +4948,9 @@ namespace size_t length = target_length + source_length; // allocate new buffer - char_t* result = static_cast<char_t*>(global_allocate((length + 1) * sizeof(char_t))); + char_t* result = static_cast<char_t*>(alloc->allocate((length + 1) * sizeof(char_t))); if (!result) return; // $$ out of memory + // $$ reallocate // append both strings in the new buffer memcpy(result, _buffer, target_length * sizeof(char_t)); @@ -4815,7 +4958,8 @@ namespace result[length] = 0; // finalize - xpath_string(result, true).swap(*this); + _buffer = result; + _uses_heap = true; } } @@ -4829,12 +4973,12 @@ namespace return strlength(_buffer); } - char_t* data() + char_t* data(xpath_allocator* alloc) { // make private heap copy if (!_uses_heap) { - _buffer = duplicate_string(_buffer); + _buffer = duplicate_string(_buffer, alloc); _uses_heap = true; } @@ -4908,7 +5052,7 @@ namespace return static_cast<unsigned int>(ch - 'A') < 26 ? (ch | ' ') : ch; } - xpath_string string_value(const xpath_node& na) + xpath_string string_value(const xpath_node& na, xpath_allocator* alloc) { if (na.attribute()) return xpath_string_const(na.attribute().value()); @@ -4934,7 +5078,7 @@ namespace while (cur && cur != n) { if (cur.type() == node_pcdata || cur.type() == node_cdata) - result.append(xpath_string_const(cur.value())); + result.append(xpath_string_const(cur.value()), alloc); if (cur.first_child()) cur = cur.first_child(); @@ -5185,7 +5329,7 @@ namespace } #endif - xpath_string convert_number_to_string(double value) + xpath_string convert_number_to_string(double value, xpath_allocator* alloc) { // try special number conversion const char_t* special = convert_number_to_string_special(value); @@ -5245,7 +5389,7 @@ namespace assert(s < result + sizeof(result) / sizeof(result[0])); *s = 0; - return xpath_string(result); + return xpath_string(result, alloc); } bool check_string_to_number_format(const char_t* string) @@ -5614,107 +5758,173 @@ namespace } } -namespace pugi +// Internal node set class +#include <algorithm> + +namespace { -#ifndef PUGIXML_NO_EXCEPTIONS - xpath_exception::xpath_exception(const xpath_parse_result& result): _result(result) - { - assert(result.error); - } - - const char* xpath_exception::what() const throw() + using namespace pugi; + + xpath_node_set::type_t xpath_sort(xpath_node* begin, xpath_node* end, xpath_node_set::type_t type, bool reverse) { - return _result.error; + xpath_node_set::type_t order = reverse ? xpath_node_set::type_sorted_reverse : xpath_node_set::type_sorted; + + if (type == xpath_node_set::type_unsorted) + { + pstd::sort(begin, end, document_order_comparator()); + + type = xpath_node_set::type_sorted; + } + + if (type != order) pstd::reverse(begin, end); + + return order; } - const xpath_parse_result& xpath_exception::result() const + xpath_node xpath_first(const xpath_node* begin, const xpath_node* end, xpath_node_set::type_t type) { - return _result; + if (begin == end) return xpath_node(); + + switch (type) + { + case xpath_node_set::type_sorted: + return *begin; + + case xpath_node_set::type_sorted_reverse: + return *(end - 1); + + case xpath_node_set::type_unsorted: + return *pstd::min_element(begin, end, document_order_comparator()); + + default: + assert(!"Invalid node set type"); + return xpath_node(); + } } -#endif - - class xpath_allocator + class xpath_node_set_raw { - struct memory_block - { - memory_block* next; - - char data[4096]; - }; - - memory_block* _root; - size_t _root_size; - + xpath_node_set::type_t _type; + + xpath_node* _begin; + xpath_node* _end; + xpath_node* _eos; + public: - static xpath_allocator* create() + xpath_node_set_raw(): _type(xpath_node_set::type_unsorted), _begin(0), _end(0), _eos(0) { - void* memory = global_allocate(sizeof(xpath_allocator) + sizeof(memory_block)); - if (!memory) return 0; + } - memory_block* root = reinterpret_cast<memory_block*>(static_cast<xpath_allocator*>(memory) + 1); - root->next = 0; + xpath_node* begin() const + { + return _begin; + } - return new (memory) xpath_allocator(root); + xpath_node* end() const + { + return _end; } - static void destroy(void* ptr) + bool empty() const { - if (!ptr) return; - - // free all allocated pages - xpath_allocator* alloc = static_cast<xpath_allocator*>(ptr); + return _begin == _end; + } - memory_block* cur = alloc->_root; - assert(cur); + size_t size() const + { + return static_cast<size_t>(_end - _begin); + } - while (cur->next) + xpath_node first() const + { + return xpath_first(_begin, _end, _type); + } + + void push_back(const xpath_node& node, xpath_allocator* alloc) + { + if (_end == _eos) { - memory_block* next = cur->next; + size_t capacity = static_cast<size_t>(_eos - _begin); - global_deallocate(cur); + // get new capacity (1.5x rule) + size_t new_capacity = capacity + capacity / 2 + 1; - cur = next; + // reallocate the old array or allocate a new one + xpath_node* data = 0; + + if (_begin) + { + data = static_cast<xpath_node*>(alloc->reallocate(_begin, capacity * sizeof(xpath_node), new_capacity * sizeof(xpath_node))); + if (!data) return; // $$ out of memory + } + else + { + data = static_cast<xpath_node*>(alloc->allocate(new_capacity * sizeof(xpath_node))); + if (!data) return; // $$ out of memory + + memcpy(data, _begin, capacity * sizeof(xpath_node)); + } + + + // finalize + _begin = data; + _end = data + capacity; + _eos = data + new_capacity; } - // free allocator memory (with the first page) - global_deallocate(alloc); + *_end++ = node; } - xpath_allocator(memory_block* root, size_t root_size = 0): _root(root), _root_size(root_size) + void sort() { + _type = xpath_sort(_begin, _end, _type, false); } - - void* allocate(size_t size) + + void truncate(xpath_node* pos) { - const size_t block_capacity = sizeof(_root->data); + assert(_begin <= pos && pos <= _end); - // align size so that we're able to store pointers in subsequent blocks - size = (size + sizeof(void*) - 1) & ~(sizeof(void*) - 1); + _end = pos; + } - if (_root_size + size <= block_capacity) - { - void* buf = _root->data + _root_size; - _root_size += size; - return buf; - } - else - { - size_t block_data_size = (size > block_capacity) ? size : block_capacity; - size_t block_size = block_data_size + offsetof(memory_block, data); + void remove_duplicates() + { + if (_type == xpath_node_set::type_unsorted) + pstd::sort(_begin, _end, duplicate_comparator()); + + _end = pstd::unique(_begin, _end); + } - memory_block* block = static_cast<memory_block*>(global_allocate(block_size)); - if (!block) return 0; - - block->next = _root; - - _root = block; - _root_size = size; - - return block->data; - } + xpath_node_set::type_t type() const + { + return _type; + } + + void set_type(xpath_node_set::type_t type) + { + _type = type; } }; +} +namespace pugi +{ +#ifndef PUGIXML_NO_EXCEPTIONS + xpath_exception::xpath_exception(const xpath_parse_result& result): _result(result) + { + assert(result.error); + } + + const char* xpath_exception::what() const throw() + { + return _result.error; + } + + const xpath_parse_result& xpath_exception::result() const + { + return _result; + } +#endif + xpath_node::xpath_node() { } @@ -5774,8 +5984,47 @@ namespace pugi } #endif - xpath_node_set::xpath_node_set(): _type(type_unsorted), _begin(&_storage), _end(&_storage), _eos(&_storage + 1) + void xpath_node_set::_assign(const_iterator begin, const_iterator end) + { + assert(begin <= end); + + size_t size = static_cast<size_t>(end - begin); + + if (size <= 1) + { + // deallocate old buffer + if (_begin != &_storage) global_deallocate(_begin); + + // use internal buffer + if (begin != end) _storage = *begin; + + _begin = &_storage; + _end = &_storage + size; + } + else + { + // make heap copy + xpath_node* storage = static_cast<xpath_node*>(global_allocate(size * sizeof(xpath_node))); + if (!storage) return; // $$ out of memory + + memcpy(storage, begin, size * sizeof(xpath_node)); + + // deallocate old buffer + if (_begin != &_storage) global_deallocate(_begin); + + // finalize + _begin = storage; + _end = storage + size; + } + } + + xpath_node_set::xpath_node_set(): _type(type_unsorted), _begin(&_storage), _end(&_storage) + { + } + + xpath_node_set::xpath_node_set(const_iterator begin, const_iterator end, type_t type): _type(type), _begin(&_storage), _end(&_storage) { + _assign(begin, end); } xpath_node_set::~xpath_node_set() @@ -5783,29 +6032,18 @@ namespace pugi if (_begin != &_storage) global_deallocate(_begin); } - xpath_node_set::xpath_node_set(const xpath_node_set& ns): _type(ns._type), _begin(&_storage), _end(&_storage), _eos(&_storage + 1) + xpath_node_set::xpath_node_set(const xpath_node_set& ns): _type(ns._type), _begin(&_storage), _end(&_storage) { - if (ns.size() == 1) - { - _storage = *ns._begin; - _end = _eos; - } - else - { - append(ns.begin(), ns.end()); - } + _assign(ns._begin, ns._end); } xpath_node_set& xpath_node_set::operator=(const xpath_node_set& ns) { if (this == &ns) return *this; - // clear & append _type = ns._type; - _end = _begin; - - append(ns.begin(), ns.end()); - + _assign(ns._begin, ns._end); + return *this; } @@ -5821,7 +6059,7 @@ namespace pugi bool xpath_node_set::empty() const { - return size() == 0; + return _begin == _end; } const xpath_node& xpath_node_set::operator[](size_t index) const @@ -5830,11 +6068,6 @@ namespace pugi return _begin[index]; } - xpath_node_set::iterator xpath_node_set::mut_begin() - { - return _begin; - } - xpath_node_set::const_iterator xpath_node_set::begin() const { return _begin; @@ -5847,88 +6080,12 @@ namespace pugi void xpath_node_set::sort(bool reverse) { - pstd::sort(_begin, _end, document_order_comparator()); - - if (reverse) pstd::reverse(_begin, _end); - - _type = reverse ? type_sorted_reverse : type_sorted; - } - - void xpath_node_set::push_back(const xpath_node& n) - { - if (_end == _eos) - append(&n, &n + 1); - else - { - *_end = n; - ++_end; - } - } - - void xpath_node_set::append(const_iterator begin, const_iterator end) - { - if (begin == end) return; - - size_t count = end - begin; - size_t size = _end - _begin; - size_t capacity = _eos - _begin; - - if (capacity < size + count) - { - if (capacity < 2) capacity = 2; - - while (capacity < size + count) capacity += capacity / 2; - - xpath_node* storage = static_cast<xpath_node*>(global_allocate(capacity * sizeof(xpath_node))); - if (!storage) return; // $$ out of memory - - memcpy(storage, _begin, size * sizeof(xpath_node)); - - if (_begin != &_storage) global_deallocate(_begin); - - _begin = storage; - _end = storage + size; - _eos = storage + capacity; - } - - memcpy(_end, begin, count * sizeof(xpath_node)); - _end += count; - } - - void xpath_node_set::truncate(iterator it) - { - _end = it; + _type = xpath_sort(_begin, _end, _type, reverse); } xpath_node xpath_node_set::first() const { - if (empty()) return xpath_node(); - - switch (_type) - { - case type_sorted: - return *_begin; - - case type_sorted_reverse: - return *(_end - 1); - - case type_unsorted: - return *pstd::min_element<iterator>(_begin, _end, document_order_comparator()); - - default: - assert(!"Invalid node set type"); - return xpath_node(); - } - } - - void xpath_node_set::remove_duplicates() - { - if (_type == type_unsorted) - { - pstd::sort(_begin, _end, duplicate_comparator()); - } - - truncate(pstd::unique(_begin, _end)); + return xpath_first(_begin, _end, _type); } struct xpath_context @@ -6425,28 +6582,39 @@ namespace pugi xpath_ast_node(const xpath_ast_node&); xpath_ast_node& operator=(const xpath_ast_node&); - template <class Comp> static bool compare_eq(xpath_ast_node* lhs, xpath_ast_node* rhs, const xpath_context& c, const Comp& comp) + template <class Comp> static bool compare_eq(xpath_ast_node* lhs, xpath_ast_node* rhs, const xpath_context& c, const xpath_stack& stack, const Comp& comp) { xpath_value_type lt = lhs->rettype(), rt = rhs->rettype(); if (lt != xpath_type_node_set && rt != xpath_type_node_set) { if (lt == xpath_type_boolean || rt == xpath_type_boolean) - return comp(lhs->eval_boolean(c), rhs->eval_boolean(c)); + return comp(lhs->eval_boolean(c, stack), rhs->eval_boolean(c, stack)); else if (lt == xpath_type_number || rt == xpath_type_number) - return comp(lhs->eval_number(c), rhs->eval_number(c)); + return comp(lhs->eval_number(c, stack), rhs->eval_number(c, stack)); else if (lt == xpath_type_string || rt == xpath_type_string) - return comp(lhs->eval_string(c), rhs->eval_string(c)); + { + xpath_allocator_capture cr(stack.result); + + xpath_string ls = lhs->eval_string(c, stack); + xpath_string rs = rhs->eval_string(c, stack); + + return comp(ls, rs); + } } else if (lt == xpath_type_node_set && rt == xpath_type_node_set) { - xpath_node_set ls = lhs->eval_node_set(c); - xpath_node_set rs = rhs->eval_node_set(c); + xpath_allocator_capture cr(stack.result); - for (xpath_node_set::const_iterator li = ls.begin(); li != ls.end(); ++li) - for (xpath_node_set::const_iterator ri = rs.begin(); ri != rs.end(); ++ri) + xpath_node_set_raw ls = lhs->eval_node_set(c, stack); + xpath_node_set_raw rs = rhs->eval_node_set(c, stack); + + for (const xpath_node* li = ls.begin(); li != ls.end(); ++li) + for (const xpath_node* ri = rs.begin(); ri != rs.end(); ++ri) { - if (comp(string_value(*li), string_value(*ri))) + xpath_allocator_capture cri(stack.result); + + if (comp(string_value(*li, stack.result), string_value(*ri, stack.result))) return true; } @@ -6461,15 +6629,19 @@ namespace pugi } if (lt == xpath_type_boolean) - return comp(lhs->eval_boolean(c), rhs->eval_boolean(c)); + return comp(lhs->eval_boolean(c, stack), rhs->eval_boolean(c, stack)); else if (lt == xpath_type_number) { - double l = lhs->eval_number(c); - xpath_node_set rs = rhs->eval_node_set(c); + xpath_allocator_capture cr(stack.result); - for (xpath_node_set::const_iterator ri = rs.begin(); ri != rs.end(); ++ri) + double l = lhs->eval_number(c, stack); + xpath_node_set_raw rs = rhs->eval_node_set(c, stack); + + for (const xpath_node* ri = rs.begin(); ri != rs.end(); ++ri) { - if (comp(l, convert_string_to_number(string_value(*ri).c_str()))) + xpath_allocator_capture cri(stack.result); + + if (comp(l, convert_string_to_number(string_value(*ri, stack.result).c_str()))) return true; } @@ -6477,12 +6649,16 @@ namespace pugi } else if (lt == xpath_type_string) { - xpath_string l = lhs->eval_string(c); - xpath_node_set rs = rhs->eval_node_set(c); + xpath_allocator_capture cr(stack.result); + + xpath_string l = lhs->eval_string(c, stack); + xpath_node_set_raw rs = rhs->eval_node_set(c, stack); - for (xpath_node_set::const_iterator ri = rs.begin(); ri != rs.end(); ++ri) + for (const xpath_node* ri = rs.begin(); ri != rs.end(); ++ri) { - if (comp(l, string_value(*ri))) + xpath_allocator_capture cri(stack.result); + + if (comp(l, string_value(*ri, stack.result))) return true; } @@ -6494,24 +6670,30 @@ namespace pugi return false; } - template <class Comp> static bool compare_rel(xpath_ast_node* lhs, xpath_ast_node* rhs, const xpath_context& c, const Comp& comp) + template <class Comp> static bool compare_rel(xpath_ast_node* lhs, xpath_ast_node* rhs, const xpath_context& c, const xpath_stack& stack, const Comp& comp) { xpath_value_type lt = lhs->rettype(), rt = rhs->rettype(); if (lt != xpath_type_node_set && rt != xpath_type_node_set) - return comp(lhs->eval_number(c), rhs->eval_number(c)); + return comp(lhs->eval_number(c, stack), rhs->eval_number(c, stack)); else if (lt == xpath_type_node_set && rt == xpath_type_node_set) { - xpath_node_set ls = lhs->eval_node_set(c); - xpath_node_set rs = rhs->eval_node_set(c); + xpath_allocator_capture cr(stack.result); + + xpath_node_set_raw ls = lhs->eval_node_set(c, stack); + xpath_node_set_raw rs = rhs->eval_node_set(c, stack); - for (xpath_node_set::const_iterator li = ls.begin(); li != ls.end(); ++li) + for (const xpath_node* li = ls.begin(); li != ls.end(); ++li) { - double l = convert_string_to_number(string_value(*li).c_str()); + xpath_allocator_capture cri(stack.result); - for (xpath_node_set::const_iterator ri = rs.begin(); ri != rs.end(); ++ri) + double l = convert_string_to_number(string_value(*li, stack.result).c_str()); + + for (const xpath_node* ri = rs.begin(); ri != rs.end(); ++ri) { - if (comp(l, convert_string_to_number(string_value(*ri).c_str()))) + xpath_allocator_capture crii(stack.result); + + if (comp(l, convert_string_to_number(string_value(*ri, stack.result).c_str()))) return true; } } @@ -6520,12 +6702,16 @@ namespace pugi } else if (lt != xpath_type_node_set && rt == xpath_type_node_set) { - double l = lhs->eval_number(c); - xpath_node_set rs = rhs->eval_node_set(c); + xpath_allocator_capture cr(stack.result); - for (xpath_node_set::const_iterator ri = rs.begin(); ri != rs.end(); ++ri) + double l = lhs->eval_number(c, stack); + xpath_node_set_raw rs = rhs->eval_node_set(c, stack); + + for (const xpath_node* ri = rs.begin(); ri != rs.end(); ++ri) { - if (comp(l, convert_string_to_number(string_value(*ri).c_str()))) + xpath_allocator_capture cri(stack.result); + + if (comp(l, convert_string_to_number(string_value(*ri, stack.result).c_str()))) return true; } @@ -6533,12 +6719,16 @@ namespace pugi } else if (lt == xpath_type_node_set && rt != xpath_type_node_set) { - xpath_node_set ls = lhs->eval_node_set(c); - double r = rhs->eval_number(c); + xpath_allocator_capture cr(stack.result); + + xpath_node_set_raw ls = lhs->eval_node_set(c, stack); + double r = rhs->eval_number(c, stack); - for (xpath_node_set::const_iterator li = ls.begin(); li != ls.end(); ++li) + for (const xpath_node* li = ls.begin(); li != ls.end(); ++li) { - if (comp(convert_string_to_number(string_value(*li).c_str()), r)) + xpath_allocator_capture cri(stack.result); + + if (comp(convert_string_to_number(string_value(*li, stack.result).c_str()), r)) return true; } @@ -6551,43 +6741,43 @@ namespace pugi } } - void apply_predicate(xpath_node_set& ns, size_t first, xpath_ast_node* expr) + void apply_predicate(xpath_node_set_raw& ns, size_t first, xpath_ast_node* expr, const xpath_stack& stack) { assert(ns.size() >= first); size_t i = 1; size_t size = ns.size() - first; - xpath_node_set::iterator last = ns.mut_begin() + first; + xpath_node* last = ns.begin() + first; // remove_if... or well, sort of - for (xpath_node_set::iterator it = last; it != ns.end(); ++it, ++i) + for (xpath_node* it = last; it != ns.end(); ++it, ++i) { xpath_context c(*it, i, size); if (expr->rettype() == xpath_type_number) { - if (expr->eval_number(c) == i) + if (expr->eval_number(c, stack) == i) *last++ = *it; } - else if (expr->eval_boolean(c)) + else if (expr->eval_boolean(c, stack)) *last++ = *it; } ns.truncate(last); } - void apply_predicates(xpath_node_set& ns, size_t first) + void apply_predicates(xpath_node_set_raw& ns, size_t first, const xpath_stack& stack) { if (ns.size() == first) return; for (xpath_ast_node* pred = _right; pred; pred = pred->_next) { - apply_predicate(ns, first, pred->_left); + apply_predicate(ns, first, pred->_left, stack); } } - void step_push(xpath_node_set& ns, const xml_attribute& a, const xml_node& parent) + void step_push(xpath_node_set_raw& ns, const xml_attribute& a, const xml_node& parent, xpath_allocator* alloc) { if (!a) return; @@ -6600,17 +6790,17 @@ namespace pugi switch (_test) { case nodetest_name: - if (strequal(name, _data.nodetest)) ns.push_back(xpath_node(a, parent)); + if (strequal(name, _data.nodetest)) ns.push_back(xpath_node(a, parent), alloc); break; case nodetest_type_node: case nodetest_all: - ns.push_back(xpath_node(a, parent)); + ns.push_back(xpath_node(a, parent), alloc); break; case nodetest_all_in_namespace: if (starts_with(name, _data.nodetest)) - ns.push_back(xpath_node(a, parent)); + ns.push_back(xpath_node(a, parent), alloc); break; default: @@ -6618,48 +6808,48 @@ namespace pugi } } - void step_push(xpath_node_set& ns, const xml_node& n) + void step_push(xpath_node_set_raw& ns, const xml_node& n, xpath_allocator* alloc) { if (!n) return; switch (_test) { case nodetest_name: - if (n.type() == node_element && strequal(n.name(), _data.nodetest)) ns.push_back(n); + if (n.type() == node_element && strequal(n.name(), _data.nodetest)) ns.push_back(n, alloc); break; case nodetest_type_node: - ns.push_back(n); + ns.push_back(n, alloc); break; case nodetest_type_comment: if (n.type() == node_comment) - ns.push_back(n); + ns.push_back(n, alloc); break; case nodetest_type_text: if (n.type() == node_pcdata || n.type() == node_cdata) - ns.push_back(n); + ns.push_back(n, alloc); break; case nodetest_type_pi: if (n.type() == node_pi) - ns.push_back(n); + ns.push_back(n, alloc); break; case nodetest_pi: if (n.type() == node_pi && strequal(n.name(), _data.nodetest)) - ns.push_back(n); + ns.push_back(n, alloc); break; case nodetest_all: if (n.type() == node_element) - ns.push_back(n); + ns.push_back(n, alloc); break; case nodetest_all_in_namespace: if (n.type() == node_element && starts_with(n.name(), _data.nodetest)) - ns.push_back(n); + ns.push_back(n, alloc); break; default: @@ -6667,7 +6857,7 @@ namespace pugi } } - template <class T> void step_fill(xpath_node_set& ns, const xml_node& n, T) + template <class T> void step_fill(xpath_node_set_raw& ns, const xml_node& n, xpath_allocator* alloc, T) { const axis_t axis = T::axis; @@ -6676,7 +6866,7 @@ namespace pugi case axis_attribute: { for (xml_attribute a = n.first_attribute(); a; a = a.next_attribute()) - step_push(ns, a, n); + step_push(ns, a, n, alloc); break; } @@ -6684,7 +6874,7 @@ namespace pugi case axis_child: { for (xml_node c = n.first_child(); c; c = c.next_sibling()) - step_push(ns, c); + step_push(ns, c, alloc); break; } @@ -6693,13 +6883,13 @@ namespace pugi case axis_descendant_or_self: { if (axis == axis_descendant_or_self) - step_push(ns, n); + step_push(ns, n, alloc); xml_node cur = n.first_child(); while (cur && cur != n) { - step_push(ns, cur); + step_push(ns, cur, alloc); if (cur.first_child()) cur = cur.first_child(); @@ -6720,7 +6910,7 @@ namespace pugi case axis_following_sibling: { for (xml_node c = n.next_sibling(); c; c = c.next_sibling()) - step_push(ns, c); + step_push(ns, c, alloc); break; } @@ -6728,7 +6918,7 @@ namespace pugi case axis_preceding_sibling: { for (xml_node c = n.previous_sibling(); c; c = c.previous_sibling()) - step_push(ns, c); + step_push(ns, c, alloc); break; } @@ -6743,7 +6933,7 @@ namespace pugi for (;;) { - step_push(ns, cur); + step_push(ns, cur, alloc); if (cur.first_child()) cur = cur.first_child(); @@ -6775,7 +6965,7 @@ namespace pugi else { // leaf node, can't be ancestor - step_push(ns, cur); + step_push(ns, cur, alloc); if (cur.previous_sibling()) cur = cur.previous_sibling(); @@ -6786,7 +6976,7 @@ namespace pugi cur = cur.parent(); if (!cur) break; - if (!node_is_ancestor(cur, n)) step_push(ns, cur); + if (!node_is_ancestor(cur, n)) step_push(ns, cur, alloc); } while (!cur.previous_sibling()); @@ -6804,13 +6994,13 @@ namespace pugi case axis_ancestor_or_self: { if (axis == axis_ancestor_or_self) - step_push(ns, n); + step_push(ns, n, alloc); xml_node cur = n.parent(); while (cur) { - step_push(ns, cur); + step_push(ns, cur, alloc); cur = cur.parent(); } @@ -6820,14 +7010,14 @@ namespace pugi case axis_self: { - step_push(ns, n); + step_push(ns, n, alloc); break; } case axis_parent: { - if (n.parent()) step_push(ns, n.parent()); + if (n.parent()) step_push(ns, n.parent(), alloc); break; } @@ -6837,7 +7027,7 @@ namespace pugi } } - template <class T> void step_fill(xpath_node_set& ns, const xml_attribute& a, const xml_node& p, T v) + template <class T> void step_fill(xpath_node_set_raw& ns, const xml_attribute& a, const xml_node& p, xpath_allocator* alloc, T v) { const axis_t axis = T::axis; @@ -6847,13 +7037,13 @@ namespace pugi case axis_ancestor_or_self: { if (axis == axis_ancestor_or_self && _test == nodetest_type_node) // reject attributes based on principal node type test - step_push(ns, a, p); + step_push(ns, a, p, alloc); xml_node cur = p; while (cur) { - step_push(ns, cur); + step_push(ns, cur, alloc); cur = cur.parent(); } @@ -6865,7 +7055,7 @@ namespace pugi case axis_self: { if (_test == nodetest_type_node) // reject attributes based on principal node type test - step_push(ns, a, p); + step_push(ns, a, p, alloc); break; } @@ -6888,7 +7078,7 @@ namespace pugi if (!cur) break; } - step_push(ns, cur); + step_push(ns, cur, alloc); } break; @@ -6896,7 +7086,7 @@ namespace pugi case axis_parent: { - step_push(ns, p); + step_push(ns, p, alloc); break; } @@ -6904,7 +7094,7 @@ namespace pugi case axis_preceding: { // preceding:: axis does not include attribute nodes and attribute ancestors (they are the same as parent's ancestors), so we can reuse node preceding - step_fill(ns, p, v); + step_fill(ns, p, alloc, v); break; } @@ -6913,44 +7103,44 @@ namespace pugi } } - template <class T> xpath_node_set step_do(const xpath_context& c, T v) + template <class T> xpath_node_set_raw step_do(const xpath_context& c, const xpath_stack& stack, T v) { const axis_t axis = T::axis; bool attributes = (axis == axis_ancestor || axis == axis_ancestor_or_self || axis == axis_descendant_or_self || axis == axis_following || axis == axis_parent || axis == axis_preceding || axis == axis_self); - xpath_node_set ns; - ns._type = (axis == axis_ancestor || axis == axis_ancestor_or_self || axis == axis_preceding || axis == axis_preceding_sibling) ? xpath_node_set::type_sorted_reverse : xpath_node_set::type_sorted; + xpath_node_set_raw ns; + ns.set_type((axis == axis_ancestor || axis == axis_ancestor_or_self || axis == axis_preceding || axis == axis_preceding_sibling) ? xpath_node_set::type_sorted_reverse : xpath_node_set::type_sorted); if (_left) { - xpath_node_set s = _left->eval_node_set(c); + xpath_node_set_raw s = _left->eval_node_set(c, stack); // self axis preserves the original order - if (axis == axis_self) ns._type = s._type; + if (axis == axis_self) ns.set_type(s.type()); - for (xpath_node_set::const_iterator it = s.begin(); it != s.end(); ++it) + for (const xpath_node* it = s.begin(); it != s.end(); ++it) { size_t size = ns.size(); // in general, all axes generate elements in a particular order, but there is no order guarantee if axis is applied to two nodes - if (axis != axis_self && size != 0) ns._type = xpath_node_set::type_unsorted; + if (axis != axis_self && size != 0) ns.set_type(xpath_node_set::type_unsorted); if (it->node()) - step_fill(ns, it->node(), v); + step_fill(ns, it->node(), stack.result, v); else if (attributes) - step_fill(ns, it->attribute(), it->parent(), v); + step_fill(ns, it->attribute(), it->parent(), stack.result, v); - apply_predicates(ns, size); + apply_predicates(ns, size, stack); } } else { if (c.n.node()) - step_fill(ns, c.n.node(), v); + step_fill(ns, c.n.node(), stack.result, v); else if (attributes) - step_fill(ns, c.n.attribute(), c.n.parent(), v); + step_fill(ns, c.n.attribute(), c.n.parent(), stack.result, v); - apply_predicates(ns, 0); + apply_predicates(ns, 0, stack); } // child, attribute and self axes always generate unique set of nodes @@ -7004,52 +7194,59 @@ namespace pugi _right = value; } - bool eval_boolean(const xpath_context& c) + bool eval_boolean(const xpath_context& c, const xpath_stack& stack) { switch (_type) { case ast_op_or: - if (_left->eval_boolean(c)) return true; - else return _right->eval_boolean(c); + return _left->eval_boolean(c, stack) || _right->eval_boolean(c, stack); case ast_op_and: - if (!_left->eval_boolean(c)) return false; - else return _right->eval_boolean(c); + return _left->eval_boolean(c, stack) && _right->eval_boolean(c, stack); case ast_op_equal: - return compare_eq(_left, _right, c, pstd::equal_to()); + return compare_eq(_left, _right, c, stack, pstd::equal_to()); case ast_op_not_equal: - return compare_eq(_left, _right, c, pstd::not_equal_to()); + return compare_eq(_left, _right, c, stack, pstd::not_equal_to()); case ast_op_less: - return compare_rel(_left, _right, c, pstd::less()); + return compare_rel(_left, _right, c, stack, pstd::less()); case ast_op_greater: - return compare_rel(_right, _left, c, pstd::less()); + return compare_rel(_right, _left, c, stack, pstd::less()); case ast_op_less_or_equal: - return compare_rel(_left, _right, c, pstd::less_equal()); + return compare_rel(_left, _right, c, stack, pstd::less_equal()); case ast_op_greater_or_equal: - return compare_rel(_right, _left, c, pstd::less_equal()); + return compare_rel(_right, _left, c, stack, pstd::less_equal()); case ast_func_starts_with: - return starts_with(_left->eval_string(c).c_str(), _right->eval_string(c).c_str()); + { + xpath_allocator_capture cr(stack.result); + + xpath_string lr = _left->eval_string(c, stack); + xpath_string rr = _right->eval_string(c, stack); + + return starts_with(lr.c_str(), rr.c_str()); + } case ast_func_contains: { - xpath_string lr = _left->eval_string(c); - xpath_string rr = _right->eval_string(c); + xpath_allocator_capture cr(stack.result); + + xpath_string lr = _left->eval_string(c, stack); + xpath_string rr = _right->eval_string(c, stack); return find_substring(lr.c_str(), rr.c_str()) != 0; } case ast_func_boolean: - return _left->eval_boolean(c); + return _left->eval_boolean(c, stack); case ast_func_not: - return !_left->eval_boolean(c); + return !_left->eval_boolean(c, stack); case ast_func_true: return true; @@ -7061,7 +7258,9 @@ namespace pugi { if (c.n.attribute()) return false; - xpath_string lang = _left->eval_string(c); + xpath_allocator_capture cr(stack.result); + + xpath_string lang = _left->eval_string(c, stack); for (xml_node n = c.n.node(); n; n = n.parent()) { @@ -7100,14 +7299,22 @@ namespace pugi switch (_rettype) { case xpath_type_number: - return convert_number_to_boolean(eval_number(c)); + return convert_number_to_boolean(eval_number(c, stack)); case xpath_type_string: - return !eval_string(c).empty(); + { + xpath_allocator_capture cr(stack.result); + + return !eval_string(c, stack).empty(); + } case xpath_type_node_set: - return !eval_node_set(c).empty(); - + { + xpath_allocator_capture cr(stack.result); + + return !eval_node_set(c, stack).empty(); + } + default: assert(!"Wrong expression for return type boolean"); return false; @@ -7116,27 +7323,27 @@ namespace pugi } } - double eval_number(const xpath_context& c) + double eval_number(const xpath_context& c, const xpath_stack& stack) { switch (_type) { case ast_op_add: - return _left->eval_number(c) + _right->eval_number(c); + return _left->eval_number(c, stack) + _right->eval_number(c, stack); case ast_op_subtract: - return _left->eval_number(c) - _right->eval_number(c); + return _left->eval_number(c, stack) - _right->eval_number(c, stack); case ast_op_multiply: - return _left->eval_number(c) * _right->eval_number(c); + return _left->eval_number(c, stack) * _right->eval_number(c, stack); case ast_op_divide: - return _left->eval_number(c) / _right->eval_number(c); + return _left->eval_number(c, stack) / _right->eval_number(c, stack); case ast_op_mod: - return fmod(_left->eval_number(c), _right->eval_number(c)); + return fmod(_left->eval_number(c, stack), _right->eval_number(c, stack)); case ast_op_negate: - return -_left->eval_number(c); + return -_left->eval_number(c, stack); case ast_number_constant: return _data.number; @@ -7148,48 +7355,66 @@ namespace pugi return (double)c.position; case ast_func_count: - return (double)_left->eval_node_set(c).size(); + { + xpath_allocator_capture cr(stack.result); + + return (double)_left->eval_node_set(c, stack).size(); + } case ast_func_string_length_0: - return (double)string_value(c.n).length(); + { + xpath_allocator_capture cr(stack.result); + + return (double)string_value(c.n, stack.result).length(); + } case ast_func_string_length_1: - return (double)_left->eval_string(c).length(); + { + xpath_allocator_capture cr(stack.result); + + return (double)_left->eval_string(c, stack).length(); + } case ast_func_number_0: - return convert_string_to_number(string_value(c.n).c_str()); + { + xpath_allocator_capture cr(stack.result); + + return convert_string_to_number(string_value(c.n, stack.result).c_str()); + } case ast_func_number_1: - return _left->eval_number(c); + return _left->eval_number(c, stack); case ast_func_sum: { + xpath_allocator_capture cr(stack.result); + double r = 0; - xpath_node_set ns = _left->eval_node_set(c); + xpath_node_set_raw ns = _left->eval_node_set(c, stack); - for (xpath_node_set::const_iterator it = ns.begin(); it != ns.end(); ++it) - r += convert_string_to_number(string_value(*it).c_str()); + for (const xpath_node* it = ns.begin(); it != ns.end(); ++it) + r += convert_string_to_number(string_value(*it, stack.result).c_str()); return r; } case ast_func_floor: { - double r = _left->eval_number(c); + double r = _left->eval_number(c, stack); return r == r ? floor(r) : r; } case ast_func_ceiling: { - double r = _left->eval_number(c); + double r = _left->eval_number(c, stack); return r == r ? ceil(r) : r; } case ast_func_round: - return round_nearest_nzero(_left->eval_number(c)); + return round_nearest_nzero(_left->eval_number(c, stack)); case ast_variable: { @@ -7206,13 +7431,21 @@ namespace pugi switch (_rettype) { case xpath_type_boolean: - return eval_boolean(c) ? 1 : 0; + return eval_boolean(c, stack) ? 1 : 0; case xpath_type_string: - return convert_string_to_number(eval_string(c).c_str()); + { + xpath_allocator_capture cr(stack.result); + + return convert_string_to_number(eval_string(c, stack).c_str()); + } case xpath_type_node_set: - return convert_string_to_number(eval_string(c).c_str()); + { + xpath_allocator_capture cr(stack.result); + + return convert_string_to_number(eval_string(c, stack).c_str()); + } default: assert(!"Wrong expression for return type number"); @@ -7223,10 +7456,12 @@ namespace pugi } } - xpath_string eval_string_concat(const xpath_context& c) + xpath_string eval_string_concat(const xpath_context& c, const xpath_stack& stack) { assert(_type == ast_func_concat); + xpath_allocator_capture ct(stack.temp); + // count the string number unsigned int count = 1; for (xpath_ast_node* nc = _right; nc; nc = nc->_next) count++; @@ -7238,17 +7473,17 @@ namespace pugi // allocate on-heap for large concats if (count > sizeof(static_buffer) / sizeof(static_buffer[0])) { - buffer = static_cast<xpath_string*>(global_allocate(count * sizeof(xpath_string))); + buffer = static_cast<xpath_string*>(stack.temp->allocate(count * sizeof(xpath_string))); if (!buffer) return xpath_string(); // $$ out of memory - - for (unsigned int i = 0; i < count; ++i) new (&buffer[i]) xpath_string(); } - // compute all strings - _left->eval_string(c).swap(buffer[0]); + // evaluate all strings to temporary stack + xpath_stack swapped_stack = {stack.temp, stack.result}; + + buffer[0] = _left->eval_string(c, swapped_stack); size_t pos = 1; - for (xpath_ast_node* n = _right; n; n = n->_next, ++pos) n->eval_string(c).swap(buffer[pos]); + for (xpath_ast_node* n = _right; n; n = n->_next, ++pos) buffer[pos] = n->eval_string(c, swapped_stack); assert(pos == count); // get total length @@ -7256,7 +7491,7 @@ namespace pugi for (unsigned int i = 0; i < count; ++i) length += buffer[i].length(); // create final string - char_t* result = static_cast<char_t*>(global_allocate((length + 1) * sizeof(char_t))); + char_t* result = static_cast<char_t*>(stack.result->allocate((length + 1) * sizeof(char_t))); if (result) { @@ -7269,21 +7504,13 @@ namespace pugi *ri = 0; } - // deallocate strings - if (buffer != static_buffer) - { - for (unsigned int i = 0; i < count; ++i) buffer[i].~xpath_string(); - - global_deallocate(buffer); - } - // return result if (!result) return xpath_string(); // $$ out of memory return xpath_string(result, true); } - xpath_string eval_string(const xpath_context& c) + xpath_string eval_string(const xpath_context& c, const xpath_stack& stack) { switch (_type) { @@ -7299,7 +7526,9 @@ namespace pugi case ast_func_local_name_1: { - xpath_node_set ns = _left->eval_node_set(c); + xpath_allocator_capture cr(stack.result); + + xpath_node_set_raw ns = _left->eval_node_set(c, stack); xpath_node na = ns.first(); return xpath_string_const(local_name(na)); @@ -7314,7 +7543,9 @@ namespace pugi case ast_func_name_1: { - xpath_node_set ns = _left->eval_node_set(c); + xpath_allocator_capture cr(stack.result); + + xpath_node_set_raw ns = _left->eval_node_set(c, stack); xpath_node na = ns.first(); return xpath_string_const(qualified_name(na)); @@ -7329,61 +7560,87 @@ namespace pugi case ast_func_namespace_uri_1: { - xpath_node_set ns = _left->eval_node_set(c); + xpath_allocator_capture cr(stack.result); + + xpath_node_set_raw ns = _left->eval_node_set(c, stack); xpath_node na = ns.first(); return xpath_string_const(namespace_uri(na)); } case ast_func_string_0: - return string_value(c.n); + return string_value(c.n, stack.result); case ast_func_string_1: - return _left->eval_string(c); + return _left->eval_string(c, stack); case ast_func_concat: - return eval_string_concat(c); + return eval_string_concat(c, stack); case ast_func_substring_before: { - xpath_string s = _left->eval_string(c); - xpath_string p = _right->eval_string(c); + xpath_allocator_capture cr(stack.temp); + + xpath_stack swapped_stack = {stack.temp, stack.result}; + + xpath_string s = _left->eval_string(c, swapped_stack); + xpath_string p = _right->eval_string(c, swapped_stack); const char_t* pos = find_substring(s.c_str(), p.c_str()); - return pos ? xpath_string(s.c_str(), pos) : xpath_string(); + return pos ? xpath_string(s.c_str(), pos, stack.result) : xpath_string(); } case ast_func_substring_after: { - xpath_string s = _left->eval_string(c); - xpath_string p = _right->eval_string(c); + xpath_allocator_capture cr(stack.temp); + + xpath_stack swapped_stack = {stack.temp, stack.result}; + + xpath_string s = _left->eval_string(c, swapped_stack); + xpath_string p = _right->eval_string(c, swapped_stack); const char_t* pos = find_substring(s.c_str(), p.c_str()); - - return pos ? xpath_string(pos + p.length(), s.uses_heap()) : xpath_string(); + if (!pos) return xpath_string(); + + const char_t* result = pos + p.length(); + + return s.uses_heap() ? xpath_string(result, stack.result) : xpath_string_const(result); } case ast_func_substring_2: { - xpath_string s = _left->eval_string(c); - double first = round_nearest(_right->eval_number(c)); + xpath_allocator_capture cr(stack.temp); + + xpath_stack swapped_stack = {stack.temp, stack.result}; + + xpath_string s = _left->eval_string(c, swapped_stack); + size_t s_length = s.length(); + + double first = round_nearest(_right->eval_number(c, stack)); if (is_nan(first)) return xpath_string(); // NaN - else if (first >= s.length() + 1) return xpath_string(); + else if (first >= s_length + 1) return xpath_string(); size_t pos = first < 1 ? 1 : (size_t)first; + assert(1 <= pos && pos <= s_length + 1); + + const char_t* rbegin = s.c_str() + (pos - 1); - return xpath_string(s.c_str() + (pos - 1), s.uses_heap()); + return s.uses_heap() ? xpath_string(rbegin, stack.result) : xpath_string_const(rbegin); } case ast_func_substring_3: { - xpath_string s = _left->eval_string(c); + xpath_allocator_capture cr(stack.temp); + + xpath_stack swapped_stack = {stack.temp, stack.result}; + + xpath_string s = _left->eval_string(c, swapped_stack); size_t s_length = s.length(); - double first = round_nearest(_right->eval_number(c)); - double last = first + round_nearest(_right->_next->eval_number(c)); + double first = round_nearest(_right->eval_number(c, stack)); + double last = first + round_nearest(_right->_next->eval_number(c, stack)); if (is_nan(first) || is_nan(last)) return xpath_string(); else if (first >= s_length + 1) return xpath_string(); @@ -7394,38 +7651,43 @@ namespace pugi size_t end = last >= s_length + 1 ? s_length + 1 : (size_t)last; assert(1 <= pos && pos <= end && end <= s_length + 1); + const char_t* rbegin = s.c_str() + (pos - 1); if (end == s_length + 1) - return xpath_string(s.c_str() + (pos - 1), s.uses_heap()); + return s.uses_heap() ? xpath_string(rbegin, stack.result) : xpath_string_const(rbegin); else - return xpath_string(s.c_str() + (pos - 1), s.c_str() + (end - 1)); + return xpath_string(s.c_str() + (pos - 1), s.c_str() + (end - 1), stack.result); } case ast_func_normalize_space_0: { - xpath_string s = string_value(c.n); + xpath_string s = string_value(c.n, stack.result); - normalize_space(s.data()); + normalize_space(s.data(stack.result)); return s; } case ast_func_normalize_space_1: { - xpath_string s = _left->eval_string(c); + xpath_string s = _left->eval_string(c, stack); - normalize_space(s.data()); + normalize_space(s.data(stack.result)); return s; } case ast_func_translate: { - xpath_string s = _left->eval_string(c); - xpath_string from = _right->eval_string(c); - xpath_string to = _right->_next->eval_string(c); + xpath_allocator_capture cr(stack.temp); + + xpath_stack swapped_stack = {stack.temp, stack.result}; + + xpath_string s = _left->eval_string(c, stack); + xpath_string from = _right->eval_string(c, swapped_stack); + xpath_string to = _right->_next->eval_string(c, swapped_stack); - translate(s.data(), from.c_str(), to.c_str()); + translate(s.data(stack.result), from.c_str(), to.c_str()); return s; } @@ -7445,15 +7707,19 @@ namespace pugi switch (_rettype) { case xpath_type_boolean: - return xpath_string_const(eval_boolean(c) ? PUGIXML_TEXT("true") : PUGIXML_TEXT("false")); + return xpath_string_const(eval_boolean(c, stack) ? PUGIXML_TEXT("true") : PUGIXML_TEXT("false")); case xpath_type_number: - return convert_number_to_string(eval_number(c)); + return convert_number_to_string(eval_number(c, stack), stack.result); case xpath_type_node_set: { - xpath_node_set ns = eval_node_set(c); - return ns.empty() ? xpath_string() : string_value(ns.first()); + xpath_allocator_capture cr(stack.temp); + + xpath_stack swapped_stack = {stack.temp, stack.result}; + + xpath_node_set_raw ns = eval_node_set(c, swapped_stack); + return ns.empty() ? xpath_string() : string_value(ns.first(), stack.result); } default: @@ -7464,84 +7730,89 @@ namespace pugi } } - xpath_node_set eval_node_set(const xpath_context& c) + xpath_node_set_raw eval_node_set(const xpath_context& c, const xpath_stack& stack) { switch (_type) { case ast_op_union: { - xpath_node_set ls = _left->eval_node_set(c); - xpath_node_set rs = _right->eval_node_set(c); + xpath_allocator_capture cr(stack.temp); + + xpath_stack swapped_stack = {stack.temp, stack.result}; + + xpath_node_set_raw ls = _left->eval_node_set(c, swapped_stack); + xpath_node_set_raw rs = _right->eval_node_set(c, stack); // we can optimize merging two sorted sets, but this is a very rare operation, so don't bother - ls._type = xpath_node_set::type_unsorted; + rs.set_type(xpath_node_set::type_unsorted); - ls.append(rs.begin(), rs.end()); + for (const xpath_node* li = ls.begin(); li != ls.end(); ++li) + rs.push_back(*li, stack.result); - ls.remove_duplicates(); + rs.remove_duplicates(); - return ls; + return rs; } case ast_filter: case ast_filter_posinv: { - xpath_node_set set = _left->eval_node_set(c); + xpath_node_set_raw set = _left->eval_node_set(c, stack); // either expression is a number or it contains position() call; sort by document order if (_type == ast_filter) set.sort(); - apply_predicate(set, 0, _right); + apply_predicate(set, 0, _right, stack); return set; } case ast_func_id: - return xpath_node_set(); + return xpath_node_set_raw(); case ast_step: { switch (_axis) { case axis_ancestor: - return step_do(c, axis_to_type<axis_ancestor>()); + return step_do(c, stack, axis_to_type<axis_ancestor>()); case axis_ancestor_or_self: - return step_do(c, axis_to_type<axis_ancestor_or_self>()); + return step_do(c, stack, axis_to_type<axis_ancestor_or_self>()); case axis_attribute: - return step_do(c, axis_to_type<axis_attribute>()); + return step_do(c, stack, axis_to_type<axis_attribute>()); case axis_child: - return step_do(c, axis_to_type<axis_child>()); + return step_do(c, stack, axis_to_type<axis_child>()); case axis_descendant: - return step_do(c, axis_to_type<axis_descendant>()); + return step_do(c, stack, axis_to_type<axis_descendant>()); case axis_descendant_or_self: - return step_do(c, axis_to_type<axis_descendant_or_self>()); + return step_do(c, stack, axis_to_type<axis_descendant_or_self>()); case axis_following: - return step_do(c, axis_to_type<axis_following>()); + return step_do(c, stack, axis_to_type<axis_following>()); case axis_following_sibling: - return step_do(c, axis_to_type<axis_following_sibling>()); + return step_do(c, stack, axis_to_type<axis_following_sibling>()); case axis_namespace: // namespaced axis is not supported - return xpath_node_set(); + return xpath_node_set_raw(); case axis_parent: - return step_do(c, axis_to_type<axis_parent>()); + return step_do(c, stack, axis_to_type<axis_parent>()); case axis_preceding: - return step_do(c, axis_to_type<axis_preceding>()); + return step_do(c, stack, axis_to_type<axis_preceding>()); case axis_preceding_sibling: - return step_do(c, axis_to_type<axis_preceding_sibling>()); + return step_do(c, stack, axis_to_type<axis_preceding_sibling>()); case axis_self: - return step_do(c, axis_to_type<axis_self>()); + return step_do(c, stack, axis_to_type<axis_self>()); } } @@ -7549,11 +7820,12 @@ namespace pugi { assert(!_right); // root step can't have any predicates - xpath_node_set ns; - ns._type = xpath_node_set::type_sorted; + xpath_node_set_raw ns; - if (c.n.node()) ns.push_back(c.n.node().root()); - else if (c.n.attribute()) ns.push_back(c.n.parent().root()); + ns.set_type(xpath_node_set::type_sorted); + + if (c.n.node()) ns.push_back(c.n.node().root(), stack.result); + else if (c.n.attribute()) ns.push_back(c.n.parent().root(), stack.result); return ns; } @@ -7563,14 +7835,25 @@ namespace pugi assert(_rettype == _data.variable->type()); if (_rettype == xpath_type_node_set) - return _data.variable->get_node_set(); + { + const xpath_node_set& s = _data.variable->get_node_set(); + + xpath_node_set_raw ns; + + ns.set_type(s.type()); + + for (xpath_node_set::const_iterator i = s.begin(); i != s.end(); ++i) + ns.push_back(*i, stack.result); + + return ns; + } // fallthrough to type conversion } default: assert(!"Wrong expression for return type node set"); - return xpath_node_set(); + return xpath_node_set_raw(); } } @@ -8532,9 +8815,13 @@ namespace pugi xpath_variable_string* var = static_cast<xpath_variable_string*>(this); // duplicate string - char_t* copy = duplicate_string(value); + size_t size = (strlength(value) + 1) * sizeof(char_t); + + char_t* copy = static_cast<char_t*>(global_allocate(size)); if (!copy) return false; + memcpy(copy, value, size); + // replace old string if (var->value) global_deallocate(var->value); var->value = copy; @@ -8689,7 +8976,12 @@ namespace pugi xpath_context c(n, 1, 1); - return _root->eval_boolean(c); + xpath_memory_block resultblock, tempblock; + xpath_allocator result(&resultblock), temp(&tempblock); + xpath_allocator_capture cr(&result), ct(&temp); + xpath_stack stack = {&result, &temp}; + + return _root->eval_boolean(c, stack); } double xpath_query::evaluate_number(const xpath_node& n) const @@ -8698,7 +8990,12 @@ namespace pugi xpath_context c(n, 1, 1); - return _root->eval_number(c); + xpath_memory_block resultblock, tempblock; + xpath_allocator result(&resultblock), temp(&tempblock); + xpath_allocator_capture cr(&result), ct(&temp); + xpath_stack stack = {&result, &temp}; + + return _root->eval_number(c, stack); } #ifndef PUGIXML_NO_STL @@ -8708,14 +9005,25 @@ namespace pugi xpath_context c(n, 1, 1); - return _root->eval_string(c).c_str(); + xpath_memory_block resultblock, tempblock; + xpath_allocator result(&resultblock), temp(&tempblock); + xpath_allocator_capture cr(&result), ct(&temp); + xpath_stack stack = {&result, &temp}; + + return _root->eval_string(c, stack).c_str(); } #endif size_t xpath_query::evaluate_string(char_t* buffer, size_t capacity, const xpath_node& n) const { xpath_context c(n, 1, 1); - xpath_string r = _root ? _root->eval_string(c) : xpath_string(); + + xpath_memory_block resultblock, tempblock; + xpath_allocator result(&resultblock), temp(&tempblock); + xpath_allocator_capture cr(&result), ct(&temp); + xpath_stack stack = {&result, &temp}; + + xpath_string r = _root ? _root->eval_string(c, stack) : xpath_string(); size_t size = r.length() + 1; @@ -8741,7 +9049,14 @@ namespace pugi xpath_context c(n, 1, 1); - return _root->eval_node_set(c); + xpath_memory_block resultblock, tempblock; + xpath_allocator result(&resultblock), temp(&tempblock); + xpath_allocator_capture cr(&result), ct(&temp); + xpath_stack stack = {&result, &temp}; + + xpath_node_set_raw r = _root->eval_node_set(c, stack); + + return xpath_node_set(r.begin(), r.end(), r.type()); } const xpath_parse_result& xpath_query::result() const diff --git a/src/pugixml.hpp b/src/pugixml.hpp index 07f6308..fbb9fcc 100644 --- a/src/pugixml.hpp +++ b/src/pugixml.hpp @@ -2068,8 +2068,6 @@ namespace pugi */ class PUGIXML_CLASS xpath_node_set { - friend class xpath_ast_node; - public: /// Collection type enum type_t @@ -2089,20 +2087,9 @@ namespace pugi xpath_node* _begin; xpath_node* _end; - xpath_node* _eos; - - typedef xpath_node* iterator; - iterator mut_begin(); - - void push_back(const xpath_node& n); + void _assign(const_iterator begin, const_iterator end); - void append(const_iterator begin, const_iterator end); - - void truncate(iterator it); - - void remove_duplicates(); - public: /** * Default constructor @@ -2111,6 +2098,11 @@ namespace pugi xpath_node_set(); /** + * Constructor from contents + */ + xpath_node_set(const_iterator begin, const_iterator end, type_t type = type_unsorted); + + /** * Destructor */ ~xpath_node_set(); |