safe_iterator.h revision 132720
1// Safe iterator implementation -*- C++ -*- 2 3// Copyright (C) 2003, 2004 4// Free Software Foundation, Inc. 5// 6// This file is part of the GNU ISO C++ Library. This library is free 7// software; you can redistribute it and/or modify it under the 8// terms of the GNU General Public License as published by the 9// Free Software Foundation; either version 2, or (at your option) 10// any later version. 11 12// This library is distributed in the hope that it will be useful, 13// but WITHOUT ANY WARRANTY; without even the implied warranty of 14// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 15// GNU General Public License for more details. 16 17// You should have received a copy of the GNU General Public License along 18// with this library; see the file COPYING. If not, write to the Free 19// Software Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307, 20// USA. 21 22// As a special exception, you may use this file as part of a free software 23// library without restriction. Specifically, if other files instantiate 24// templates or use macros or inline functions from this file, or you compile 25// this file and link it with other files to produce an executable, this 26// file does not by itself cause the resulting executable to be covered by 27// the GNU General Public License. This exception does not however 28// invalidate any other reasons why the executable file might be covered by 29// the GNU General Public License. 30 31#ifndef _GLIBCXX_DEBUG_SAFE_ITERATOR_H 32#define _GLIBCXX_DEBUG_SAFE_ITERATOR_H 1 33 34#include <bits/stl_pair.h> 35#include <debug/debug.h> 36#include <debug/formatter.h> 37#include <debug/safe_base.h> 38#include <bits/cpp_type_traits.h> 39 40namespace __gnu_debug 41{ 42 using std::iterator_traits; 43 using std::pair; 44 45 /** Iterators that derive from _Safe_iterator_base but that aren't 46 * _Safe_iterators can be determined singular or non-singular via 47 * _Safe_iterator_base. 48 */ 49 inline bool __check_singular_aux(const _Safe_iterator_base* __x) 50 { return __x->_M_singular(); } 51 52 /** \brief Safe iterator wrapper. 53 * 54 * The class template %_Safe_iterator is a wrapper around an 55 * iterator that tracks the iterator's movement among sequences and 56 * checks that operations performed on the "safe" iterator are 57 * legal. In additional to the basic iterator operations (which are 58 * validated, and then passed to the underlying iterator), 59 * %_Safe_iterator has member functions for iterator invalidation, 60 * attaching/detaching the iterator from sequences, and querying 61 * the iterator's state. 62 */ 63 template<typename _Iterator, typename _Sequence> 64 class _Safe_iterator : public _Safe_iterator_base 65 { 66 typedef _Safe_iterator _Self; 67 68 /** The precision to which we can calculate the distance between 69 * two iterators. 70 */ 71 enum _Distance_precision 72 { 73 __dp_equality, //< Can compare iterator equality, only 74 __dp_sign, //< Can determine equality and ordering 75 __dp_exact //< Can determine distance precisely 76 }; 77 78 /// The underlying iterator 79 _Iterator _M_current; 80 81 /// Determine if this is a constant iterator. 82 bool 83 _M_constant() const 84 { 85 typedef typename _Sequence::const_iterator const_iterator; 86 return __is_same<const_iterator, _Safe_iterator>::value; 87 } 88 89 typedef iterator_traits<_Iterator> _Traits; 90 91 public: 92 typedef _Iterator _Base_iterator; 93 typedef typename _Traits::iterator_category iterator_category; 94 typedef typename _Traits::value_type value_type; 95 typedef typename _Traits::difference_type difference_type; 96 typedef typename _Traits::reference reference; 97 typedef typename _Traits::pointer pointer; 98 99 /// @post the iterator is singular and unattached 100 _Safe_iterator() : _M_current() { } 101 102 /** 103 * @brief Safe iterator construction from an unsafe iterator and 104 * its sequence. 105 * 106 * @pre @p seq is not NULL 107 * @post this is not singular 108 */ 109 _Safe_iterator(const _Iterator& __i, const _Sequence* __seq) 110 : _Safe_iterator_base(__seq, _M_constant()), _M_current(__i) 111 { 112 _GLIBCXX_DEBUG_VERIFY(! this->_M_singular(), 113 _M_message(__msg_init_singular) 114 ._M_iterator(*this, "this")); 115 } 116 117 /** 118 * @brief Copy construction. 119 * @pre @p x is not singular 120 */ 121 _Safe_iterator(const _Safe_iterator& __x) 122 : _Safe_iterator_base(__x, _M_constant()), _M_current(__x._M_current) 123 { 124 _GLIBCXX_DEBUG_VERIFY(!__x._M_singular(), 125 _M_message(__msg_init_copy_singular) 126 ._M_iterator(*this, "this") 127 ._M_iterator(__x, "other")); 128 } 129 130 /** 131 * @brief Converting constructor from a mutable iterator to a 132 * constant iterator. 133 * 134 * @pre @p x is not singular 135 */ 136 template<typename _MutableIterator> 137 _Safe_iterator( 138 const _Safe_iterator<_MutableIterator, 139 typename std::__enable_if< 140 _Sequence, 141 (std::__are_same<_MutableIterator, 142 typename _Sequence::iterator::_Base_iterator>::_M_type) 143 >::_M_type>& __x) 144 : _Safe_iterator_base(__x, _M_constant()), _M_current(__x.base()) 145 { 146 _GLIBCXX_DEBUG_VERIFY(!__x._M_singular(), 147 _M_message(__msg_init_const_singular) 148 ._M_iterator(*this, "this") 149 ._M_iterator(__x, "other")); 150 } 151 152 /** 153 * @brief Copy assignment. 154 * @pre @p x is not singular 155 */ 156 _Safe_iterator& 157 operator=(const _Safe_iterator& __x) 158 { 159 _GLIBCXX_DEBUG_VERIFY(!__x._M_singular(), 160 _M_message(__msg_copy_singular) 161 ._M_iterator(*this, "this") 162 ._M_iterator(__x, "other")); 163 _M_current = __x._M_current; 164 this->_M_attach(static_cast<_Sequence*>(__x._M_sequence)); 165 return *this; 166 } 167 168 /** 169 * @brief Iterator dereference. 170 * @pre iterator is dereferenceable 171 */ 172 reference 173 operator*() const 174 { 175 176 _GLIBCXX_DEBUG_VERIFY(this->_M_dereferenceable(), 177 _M_message(__msg_bad_deref) 178 ._M_iterator(*this, "this")); 179 return *_M_current; 180 } 181 182 /** 183 * @brief Iterator dereference. 184 * @pre iterator is dereferenceable 185 * @todo Make this correct w.r.t. iterators that return proxies 186 * @todo Use addressof() instead of & operator 187 */ 188 pointer 189 operator->() const 190 { 191 _GLIBCXX_DEBUG_VERIFY(this->_M_dereferenceable(), 192 _M_message(__msg_bad_deref) 193 ._M_iterator(*this, "this")); 194 return &*_M_current; 195 } 196 197 // ------ Input iterator requirements ------ 198 /** 199 * @brief Iterator preincrement 200 * @pre iterator is incrementable 201 */ 202 _Safe_iterator& 203 operator++() 204 { 205 _GLIBCXX_DEBUG_VERIFY(this->_M_incrementable(), 206 _M_message(__msg_bad_inc) 207 ._M_iterator(*this, "this")); 208 ++_M_current; 209 return *this; 210 } 211 212 /** 213 * @brief Iterator postincrement 214 * @pre iterator is incrementable 215 */ 216 _Safe_iterator 217 operator++(int) 218 { 219 _GLIBCXX_DEBUG_VERIFY(this->_M_incrementable(), 220 _M_message(__msg_bad_inc) 221 ._M_iterator(*this, "this")); 222 _Safe_iterator __tmp(*this); 223 ++_M_current; 224 return __tmp; 225 } 226 227 // ------ Bidirectional iterator requirements ------ 228 /** 229 * @brief Iterator predecrement 230 * @pre iterator is decrementable 231 */ 232 _Safe_iterator& 233 operator--() 234 { 235 _GLIBCXX_DEBUG_VERIFY(this->_M_decrementable(), 236 _M_message(__msg_bad_dec) 237 ._M_iterator(*this, "this")); 238 --_M_current; 239 return *this; 240 } 241 242 /** 243 * @brief Iterator postdecrement 244 * @pre iterator is decrementable 245 */ 246 _Safe_iterator 247 operator--(int) 248 { 249 _GLIBCXX_DEBUG_VERIFY(this->_M_decrementable(), 250 _M_message(__msg_bad_dec) 251 ._M_iterator(*this, "this")); 252 _Safe_iterator __tmp(*this); 253 --_M_current; 254 return __tmp; 255 } 256 257 // ------ Random access iterator requirements ------ 258 reference 259 operator[](const difference_type& __n) const 260 { 261 _GLIBCXX_DEBUG_VERIFY(this->_M_can_advance(__n) 262 && this->_M_can_advance(__n+1), 263 _M_message(__msg_iter_subscript_oob) 264 ._M_iterator(*this)._M_integer(__n)); 265 266 return _M_current[__n]; 267 } 268 269 _Safe_iterator& 270 operator+=(const difference_type& __n) 271 { 272 _GLIBCXX_DEBUG_VERIFY(this->_M_can_advance(__n), 273 _M_message(__msg_advance_oob) 274 ._M_iterator(*this)._M_integer(__n)); 275 _M_current += __n; 276 return *this; 277 } 278 279 _Safe_iterator 280 operator+(const difference_type& __n) const 281 { 282 _Safe_iterator __tmp(*this); 283 __tmp += __n; 284 return __tmp; 285 } 286 287 _Safe_iterator& 288 operator-=(const difference_type& __n) 289 { 290 _GLIBCXX_DEBUG_VERIFY(this->_M_can_advance(-__n), 291 _M_message(__msg_retreat_oob) 292 ._M_iterator(*this)._M_integer(__n)); 293 _M_current += -__n; 294 return *this; 295 } 296 297 _Safe_iterator 298 operator-(const difference_type& __n) const 299 { 300 _Safe_iterator __tmp(*this); 301 __tmp -= __n; 302 return __tmp; 303 } 304 305 // ------ Utilities ------ 306 /** 307 * @brief Return the underlying iterator 308 */ 309 _Iterator 310 base() const { return _M_current; } 311 312 /** 313 * @brief Conversion to underlying non-debug iterator to allow 314 * better interaction with non-debug containers. 315 */ 316 operator _Iterator() const { return _M_current; } 317 318 /** Attach iterator to the given sequence. */ 319 void 320 _M_attach(const _Sequence* __seq) 321 { 322 _Safe_iterator_base::_M_attach(const_cast<_Sequence*>(__seq), 323 _M_constant()); 324 } 325 326 /** Invalidate the iterator, making it singular. */ 327 void 328 _M_invalidate(); 329 330 /// Is the iterator dereferenceable? 331 bool 332 _M_dereferenceable() const 333 { return !this->_M_singular() && !_M_is_end(); } 334 335 /// Is the iterator incrementable? 336 bool 337 _M_incrementable() const { return this->_M_dereferenceable(); } 338 339 // Is the iterator decrementable? 340 bool 341 _M_decrementable() const { return !_M_singular() && !_M_is_begin(); } 342 343 // Can we advance the iterator @p __n steps (@p __n may be negative) 344 bool 345 _M_can_advance(const difference_type& __n) const; 346 347 // Is the iterator range [*this, __rhs) valid? 348 template<typename _Other> 349 bool 350 _M_valid_range(const _Safe_iterator<_Other, _Sequence>& __rhs) const; 351 352 // The sequence this iterator references. 353 const _Sequence* 354 _M_get_sequence() const 355 { return static_cast<const _Sequence*>(_M_sequence); } 356 357 /** Determine the distance between two iterators with some known 358 * precision. 359 */ 360 template<typename _Iterator1, typename _Iterator2> 361 static pair<difference_type, _Distance_precision> 362 _M_get_distance(const _Iterator1& __lhs, const _Iterator2& __rhs) 363 { 364 typedef typename iterator_traits<_Iterator1>::iterator_category 365 _Category; 366 return _M_get_distance(__lhs, __rhs, _Category()); 367 } 368 369 template<typename _Iterator1, typename _Iterator2> 370 static pair<difference_type, _Distance_precision> 371 _M_get_distance(const _Iterator1& __lhs, const _Iterator2& __rhs, 372 std::random_access_iterator_tag) 373 { 374 return std::make_pair(__rhs.base() - __lhs.base(), __dp_exact); 375 } 376 377 template<typename _Iterator1, typename _Iterator2> 378 static pair<difference_type, _Distance_precision> 379 _M_get_distance(const _Iterator1& __lhs, const _Iterator2& __rhs, 380 std::forward_iterator_tag) 381 { 382 return std::make_pair(__lhs.base() == __rhs.base()? 0 : 1, 383 __dp_equality); 384 } 385 386 /// Is this iterator equal to the sequence's begin() iterator? 387 bool _M_is_begin() const 388 { return *this == static_cast<const _Sequence*>(_M_sequence)->begin(); } 389 390 /// Is this iterator equal to the sequence's end() iterator? 391 bool _M_is_end() const 392 { return *this == static_cast<const _Sequence*>(_M_sequence)->end(); } 393 }; 394 395 template<typename _IteratorL, typename _IteratorR, typename _Sequence> 396 inline bool 397 operator==(const _Safe_iterator<_IteratorL, _Sequence>& __lhs, 398 const _Safe_iterator<_IteratorR, _Sequence>& __rhs) 399 { 400 _GLIBCXX_DEBUG_VERIFY(! __lhs._M_singular() && ! __rhs._M_singular(), 401 _M_message(__msg_iter_compare_bad) 402 ._M_iterator(__lhs, "lhs") 403 ._M_iterator(__rhs, "rhs")); 404 _GLIBCXX_DEBUG_VERIFY(__lhs._M_can_compare(__rhs), 405 _M_message(__msg_compare_different) 406 ._M_iterator(__lhs, "lhs") 407 ._M_iterator(__rhs, "rhs")); 408 return __lhs.base() == __rhs.base(); 409 } 410 411 template<typename _Iterator, typename _Sequence> 412 inline bool 413 operator==(const _Safe_iterator<_Iterator, _Sequence>& __lhs, 414 const _Safe_iterator<_Iterator, _Sequence>& __rhs) 415 { 416 _GLIBCXX_DEBUG_VERIFY(! __lhs._M_singular() && ! __rhs._M_singular(), 417 _M_message(__msg_iter_compare_bad) 418 ._M_iterator(__lhs, "lhs") 419 ._M_iterator(__rhs, "rhs")); 420 _GLIBCXX_DEBUG_VERIFY(__lhs._M_can_compare(__rhs), 421 _M_message(__msg_compare_different) 422 ._M_iterator(__lhs, "lhs") 423 ._M_iterator(__rhs, "rhs")); 424 return __lhs.base() == __rhs.base(); 425 } 426 427 template<typename _IteratorL, typename _IteratorR, typename _Sequence> 428 inline bool 429 operator!=(const _Safe_iterator<_IteratorL, _Sequence>& __lhs, 430 const _Safe_iterator<_IteratorR, _Sequence>& __rhs) 431 { 432 _GLIBCXX_DEBUG_VERIFY(! __lhs._M_singular() && ! __rhs._M_singular(), 433 _M_message(__msg_iter_compare_bad) 434 ._M_iterator(__lhs, "lhs") 435 ._M_iterator(__rhs, "rhs")); 436 _GLIBCXX_DEBUG_VERIFY(__lhs._M_can_compare(__rhs), 437 _M_message(__msg_compare_different) 438 ._M_iterator(__lhs, "lhs") 439 ._M_iterator(__rhs, "rhs")); 440 return __lhs.base() != __rhs.base(); 441 } 442 443 template<typename _Iterator, typename _Sequence> 444 inline bool 445 operator!=(const _Safe_iterator<_Iterator, _Sequence>& __lhs, 446 const _Safe_iterator<_Iterator, _Sequence>& __rhs) 447 { 448 _GLIBCXX_DEBUG_VERIFY(! __lhs._M_singular() && ! __rhs._M_singular(), 449 _M_message(__msg_iter_compare_bad) 450 ._M_iterator(__lhs, "lhs") 451 ._M_iterator(__rhs, "rhs")); 452 _GLIBCXX_DEBUG_VERIFY(__lhs._M_can_compare(__rhs), 453 _M_message(__msg_compare_different) 454 ._M_iterator(__lhs, "lhs") 455 ._M_iterator(__rhs, "rhs")); 456 return __lhs.base() != __rhs.base(); 457 } 458 459 template<typename _IteratorL, typename _IteratorR, typename _Sequence> 460 inline bool 461 operator<(const _Safe_iterator<_IteratorL, _Sequence>& __lhs, 462 const _Safe_iterator<_IteratorR, _Sequence>& __rhs) 463 { 464 _GLIBCXX_DEBUG_VERIFY(! __lhs._M_singular() && ! __rhs._M_singular(), 465 _M_message(__msg_iter_order_bad) 466 ._M_iterator(__lhs, "lhs") 467 ._M_iterator(__rhs, "rhs")); 468 _GLIBCXX_DEBUG_VERIFY(__lhs._M_can_compare(__rhs), 469 _M_message(__msg_order_different) 470 ._M_iterator(__lhs, "lhs") 471 ._M_iterator(__rhs, "rhs")); 472 return __lhs.base() < __rhs.base(); 473 } 474 475 template<typename _Iterator, typename _Sequence> 476 inline bool 477 operator<(const _Safe_iterator<_Iterator, _Sequence>& __lhs, 478 const _Safe_iterator<_Iterator, _Sequence>& __rhs) 479 { 480 _GLIBCXX_DEBUG_VERIFY(! __lhs._M_singular() && ! __rhs._M_singular(), 481 _M_message(__msg_iter_order_bad) 482 ._M_iterator(__lhs, "lhs") 483 ._M_iterator(__rhs, "rhs")); 484 _GLIBCXX_DEBUG_VERIFY(__lhs._M_can_compare(__rhs), 485 _M_message(__msg_order_different) 486 ._M_iterator(__lhs, "lhs") 487 ._M_iterator(__rhs, "rhs")); 488 return __lhs.base() < __rhs.base(); 489 } 490 491 template<typename _IteratorL, typename _IteratorR, typename _Sequence> 492 inline bool 493 operator<=(const _Safe_iterator<_IteratorL, _Sequence>& __lhs, 494 const _Safe_iterator<_IteratorR, _Sequence>& __rhs) 495 { 496 _GLIBCXX_DEBUG_VERIFY(! __lhs._M_singular() && ! __rhs._M_singular(), 497 _M_message(__msg_iter_order_bad) 498 ._M_iterator(__lhs, "lhs") 499 ._M_iterator(__rhs, "rhs")); 500 _GLIBCXX_DEBUG_VERIFY(__lhs._M_can_compare(__rhs), 501 _M_message(__msg_order_different) 502 ._M_iterator(__lhs, "lhs") 503 ._M_iterator(__rhs, "rhs")); 504 return __lhs.base() <= __rhs.base(); 505 } 506 507 template<typename _Iterator, typename _Sequence> 508 inline bool 509 operator<=(const _Safe_iterator<_Iterator, _Sequence>& __lhs, 510 const _Safe_iterator<_Iterator, _Sequence>& __rhs) 511 { 512 _GLIBCXX_DEBUG_VERIFY(! __lhs._M_singular() && ! __rhs._M_singular(), 513 _M_message(__msg_iter_order_bad) 514 ._M_iterator(__lhs, "lhs") 515 ._M_iterator(__rhs, "rhs")); 516 _GLIBCXX_DEBUG_VERIFY(__lhs._M_can_compare(__rhs), 517 _M_message(__msg_order_different) 518 ._M_iterator(__lhs, "lhs") 519 ._M_iterator(__rhs, "rhs")); 520 return __lhs.base() <= __rhs.base(); 521 } 522 523 template<typename _IteratorL, typename _IteratorR, typename _Sequence> 524 inline bool 525 operator>(const _Safe_iterator<_IteratorL, _Sequence>& __lhs, 526 const _Safe_iterator<_IteratorR, _Sequence>& __rhs) 527 { 528 _GLIBCXX_DEBUG_VERIFY(! __lhs._M_singular() && ! __rhs._M_singular(), 529 _M_message(__msg_iter_order_bad) 530 ._M_iterator(__lhs, "lhs") 531 ._M_iterator(__rhs, "rhs")); 532 _GLIBCXX_DEBUG_VERIFY(__lhs._M_can_compare(__rhs), 533 _M_message(__msg_order_different) 534 ._M_iterator(__lhs, "lhs") 535 ._M_iterator(__rhs, "rhs")); 536 return __lhs.base() > __rhs.base(); 537 } 538 539 template<typename _Iterator, typename _Sequence> 540 inline bool 541 operator>(const _Safe_iterator<_Iterator, _Sequence>& __lhs, 542 const _Safe_iterator<_Iterator, _Sequence>& __rhs) 543 { 544 _GLIBCXX_DEBUG_VERIFY(! __lhs._M_singular() && ! __rhs._M_singular(), 545 _M_message(__msg_iter_order_bad) 546 ._M_iterator(__lhs, "lhs") 547 ._M_iterator(__rhs, "rhs")); 548 _GLIBCXX_DEBUG_VERIFY(__lhs._M_can_compare(__rhs), 549 _M_message(__msg_order_different) 550 ._M_iterator(__lhs, "lhs") 551 ._M_iterator(__rhs, "rhs")); 552 return __lhs.base() > __rhs.base(); 553 } 554 555 template<typename _IteratorL, typename _IteratorR, typename _Sequence> 556 inline bool 557 operator>=(const _Safe_iterator<_IteratorL, _Sequence>& __lhs, 558 const _Safe_iterator<_IteratorR, _Sequence>& __rhs) 559 { 560 _GLIBCXX_DEBUG_VERIFY(! __lhs._M_singular() && ! __rhs._M_singular(), 561 _M_message(__msg_iter_order_bad) 562 ._M_iterator(__lhs, "lhs") 563 ._M_iterator(__rhs, "rhs")); 564 _GLIBCXX_DEBUG_VERIFY(__lhs._M_can_compare(__rhs), 565 _M_message(__msg_order_different) 566 ._M_iterator(__lhs, "lhs") 567 ._M_iterator(__rhs, "rhs")); 568 return __lhs.base() >= __rhs.base(); 569 } 570 571 template<typename _Iterator, typename _Sequence> 572 inline bool 573 operator>=(const _Safe_iterator<_Iterator, _Sequence>& __lhs, 574 const _Safe_iterator<_Iterator, _Sequence>& __rhs) 575 { 576 _GLIBCXX_DEBUG_VERIFY(! __lhs._M_singular() && ! __rhs._M_singular(), 577 _M_message(__msg_iter_order_bad) 578 ._M_iterator(__lhs, "lhs") 579 ._M_iterator(__rhs, "rhs")); 580 _GLIBCXX_DEBUG_VERIFY(__lhs._M_can_compare(__rhs), 581 _M_message(__msg_order_different) 582 ._M_iterator(__lhs, "lhs") 583 ._M_iterator(__rhs, "rhs")); 584 return __lhs.base() >= __rhs.base(); 585 } 586 587 // _GLIBCXX_RESOLVE_LIB_DEFECTS 588 // According to the resolution of DR179 not only the various comparison 589 // operators but also operator- must accept mixed iterator/const_iterator 590 // parameters. 591 template<typename _IteratorL, typename _IteratorR, typename _Sequence> 592 inline typename _Safe_iterator<_IteratorL, _Sequence>::difference_type 593 operator-(const _Safe_iterator<_IteratorL, _Sequence>& __lhs, 594 const _Safe_iterator<_IteratorR, _Sequence>& __rhs) 595 { 596 _GLIBCXX_DEBUG_VERIFY(! __lhs._M_singular() && ! __rhs._M_singular(), 597 _M_message(__msg_distance_bad) 598 ._M_iterator(__lhs, "lhs") 599 ._M_iterator(__rhs, "rhs")); 600 _GLIBCXX_DEBUG_VERIFY(__lhs._M_can_compare(__rhs), 601 _M_message(__msg_distance_different) 602 ._M_iterator(__lhs, "lhs") 603 ._M_iterator(__rhs, "rhs")); 604 return __lhs.base() - __rhs.base(); 605 } 606 607 template<typename _Iterator, typename _Sequence> 608 inline _Safe_iterator<_Iterator, _Sequence> 609 operator+(typename _Safe_iterator<_Iterator,_Sequence>::difference_type __n, 610 const _Safe_iterator<_Iterator, _Sequence>& __i) 611 { return __i + __n; } 612} // namespace __gnu_debug 613 614#ifndef _GLIBCXX_EXPORT_TEMPLATE 615# include <debug/safe_iterator.tcc> 616#endif 617 618#endif 619